Collision avoidance and resolution multiple access
JJ Garcia-Luna-Aceves, Rodrigo Garcés · 1999
Multiple-access interference constitutes a major cause of throughput degradation in wireless networks. The focus of this thesis is the design and analysis of medium access control protocols that mitigate multiple access interference by resolving collisions of small control packets used to avoid the collision of much larger data packets. An upper bound is derived for the average cost of resolving collisions using a deterministic tree-splitting algorithm. This bound is then applied to the computation of the average channel utilization in a fully connected network with a large number of stations. Under light-load conditions, collision avoidance and resolution (CARMA) protocols achieve the same average throughput as floor acquisition multiple access (FAMA) protocols. It is also shown that, as the arrival rate of RTSs increases, the throughput achieved by CARMA protocols is close to the maximum throughput that any FAMA protocol can achieve if propagation delays and the control packets used to acquire the floor are much smaller than the data packet trains sent by stations. We introduce the incremental collision resolution multiple access (ICRMA) protocol, which maintains a distributed queue for the transmission of data packets and a stack for the transmission of control packets used in collision resolution. ICRMA dynamically divides the channel into cycles of variable length; each cycle consists of a contention period and a queue-transmission period. The queue-transmission period is a variable-length train of packets, which are transmitted by stations that have been added to the distributed transmission queue by successfully completing a collision-resolution round in a previous contention period. During the contention period, stations with one or more packets to send compete for the right to be added to the data-transmission queue using a deterministic tree-splitting algorithm. A single round of collision resolution (i.e., a success, and idle or a collision of control packets) is allowed in each contention period. Simulation and analytical results show that ICRMA's throughput is within 5% of the throughput achieved by the ideal channel access protocol based on a distributed transmission queue and incremental collision resolution. We also propose a novel “spectrum etiquette,” to allow systems from different manufacturers with different physical and medium-access control protocols to co-exist, without monitoring the entire band, by means of transmissions over a common, narrow band control channel used to establish collision-free transmission schedules over the channels allocated for data transmission. Because no common physical layer can be assumed among different systems, the control channel is needed for the systems to schedule transmissions in the rest of the band, and the only means by which systems can communicate with one another over the control channel is the duration of each others' transmissions, which are perceived only as noise. A transmission encoding is defined based on this basic feedback to allow systems to ascertain which system can use which data channel at which time without interference. Analytical and simulation results are presented showing that the proposed etiquette is fair to all the co-existing systems, fully utilizes the spectrum, provides bounded delays for data-channel acquisition time by any given system, and provides minimum channel-use guarantees.