Ji Woong Lee and Jean Walrand

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2007-63

May 18, 2007

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-63.pdf

We develop a new kind of fully distributed random backoff algorithm which completely removes collisions in a single channel carrier-sense multiple access based network without any assistance from a centralized coordination function. Based on carefully chosen design objectives, three principles are established to contribute to the design of the zero-collision achieving random backoff algorithm, which is dubbed as ZeroCollision. To find non-colliding access slots, a station learns from its past transmission history and from neighbors' activities. By building sufficient statistics for its access decision, the station is guaranteed to avoid collisions.

By preventing collisions, the network performance is enhanced in terms of primary performance metrics such as throughput and transmission delay in comparison to the generic exponential backoff algorithm. We also analyze the VoIP capacity on top of the IEEE 802.11b PHY/MAC and show that the ZeroCollision algorithm supports maximally 54 users which is approximately 400 percent larger than the exponential backoff algorithm.

---

BibTeX citation:

@techreport{Lee:EECS-2007-63,
    Author= {Lee, Ji Woong and Walrand, Jean},
    Title= {ZeroCollision Random Backoff Algorithm},
    Year= {2007},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-63.html},
    Number= {UCB/EECS-2007-63},
    Abstract= {We develop a new kind of fully distributed random backoff algorithm which completely removes collisions in a single channel carrier-sense multiple access based network without any assistance from a centralized coordination function. Based on carefully chosen design objectives, three principles are established to contribute to the design of the zero-collision achieving random backoff algorithm, which is dubbed as ZeroCollision. To find non-colliding access slots, a station  learns from its past transmission history and from neighbors' activities. By building sufficient statistics for its access decision, the station is guaranteed to avoid collisions.

By preventing collisions, the network performance is enhanced in terms of primary performance metrics such as throughput and transmission delay  in comparison to the generic exponential backoff algorithm. We also analyze the VoIP capacity on top of the IEEE 802.11b PHY/MAC and show that the ZeroCollision algorithm supports maximally 54 users which is approximately 400 percent larger than the exponential backoff algorithm.},
}

EndNote citation:

%0 Report
%A Lee, Ji Woong 
%A Walrand, Jean 
%T ZeroCollision Random Backoff Algorithm
%I EECS Department, University of California, Berkeley
%D 2007
%8 May 18
%@ UCB/EECS-2007-63
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-63.html
%F Lee:EECS-2007-63