An Analysis of the Binary Exponential Backoff Algorithm in Distributed MAC Protocols
Chunyu Hu, Hwangnam Kim, Jennifer C. Hou · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 2005
Abstract — In the paper, we perform an in-depth analytic study of the binary exponential algorithm (BEBA) that is widely used in distributed MAC protocols, for example, IEEE 802.11 DCF. We begin with a generalized framework of modeling BEBA. Then we identify a key difference between BEBA and the commonly-assumed p-persistent model: due to the characteristics of BEBA, the slot succeeding a busy period has a different contention rate from other slots. This causes access to a slot to be non-uniform and dependent on whether or not the slot immediately follows a busy period. We propose a detailed model with the use of a Markov chain to faithfully describe the channel activities governed by BEBA. To reduce the computational complexity, we simplify the model to an approximate one, and conduct an extensive simulation study. The analytical results derived in the proposed model are compared against those obtained from two other representative models. It is demonstrated that the proposed model is an accurate characterization of the BEBA algorithm in a broader range of system configuration. We further investigate the impact of the stochastic property of the backoff time, r, on the performance. It is revealed that in certain circumstances it becomes an important factor that affects the performance. A case study shows that by shifting the distribution range of r merely by 1 slot, substantial degradation in the system throughput may result. I.