IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

An Analysis of the Binary Exponential Backoff Algorithm in Distributed MAC Protocols

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/11066

Files in this item

File Description Format
PDF An Analysis of ... tributed MAC Protocols.pdf (215KB) (no description provided) PDF
Title: An Analysis of the Binary Exponential Backoff Algorithm in Distributed MAC Protocols
Author(s): Hu, Chunyu; Kim, Hwangnam; Hou, Jennifer C.
Subject(s): algorithms
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 the 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.
Issue Date: 2005-07
Genre: Technical Report
Type: Text
URI: http://hdl.handle.net/2142/11066
Other Identifier(s): UIUCDCS-R-2005-2599
Rights Information: You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).
Date Available in IDEALS: 2009-04-20
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 1655
  • Downloads this Month: 87
  • Downloads Today: 0

Browse

My Account

Information

Access Key