Collision Resolution Protocol with Limited Channel Sensing - Finitely Many Users

摘要

In this paper, the authors consider the random-accessing of a single slotted channel by a finite number of independent, data transmitting bursty users. They adopt the assumption that each user monitors the channel only while he is blocked. They also assume that the channel outcomes (visible to each user) are ternary. That is, each channel slot is perceived as either empty or successfully busy, or as a collision slot. Propagation delays are disregarded. For the above model, the authors propose and analyze a collision resolution protocol (CRLS) with tree search characteristics. For identical users with binomial transmission processes, they find lower bounds on the CRLS throughput, and compute upper bounds on the induced delays in transmission. Their results are compared with those induced by the dynamic tree protocol of Capetanakis; where the feedback sensing is continuous in the latter. The CRLS performs surprisingly well. For asymptotically many users, its throughput is higher than the throughput of the nondynamic tree protocol of Capetanakis, and less than 7 percent lower than the throughput of the dynamic form of the latter. The CRLS also compares well in terms of delays, and it is robust in the presence of channel errors.