UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Throughput performance of tree collision resolution algorithms with capture Wong, Kenneth K. L.


The effect of capture on tree algorithms in a slotted ALOHA broadcasting network is investigated. Two receiver models are considered: Feedback With Capture (FWC) and Feedback Without Capture (FWOC). In FWC, the receiver is able to distinguish between a success and capture slot, whereas in FWOC it is not. For each model, two collision resolution schemes are examined. The throughput performances of the four schemes using the discrete and continuous capture models are obtained and compared. In the discrete capture model, the transmitters are divided into groups. Only packets from transmitters in a more dominant group have a chance to be captured. The continuous capture model is used to examine the throughput performance on the inbound (mobile-to-base station) channel in a packet radio system consisting of a central base station and a number of mobile user terminals. The use of a dynamic tree (DT) algorithm in a continuous capture environment is also investigated. Expressions for finding the average length of a collision resolution interval (CRI) for each scheme using the static binary tree are derived. These average lengths are used to determine the throughput. Numerical procedures are described which use the static binary tree results in the dynamic tree to estimate the throughput. Simulations are used to verify the maximum achievable throughput in DT which also give plots of the average packet delay against the arrival rate.

Item Media

Item Citations and Data


For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.