Performance evaluation of backoff algorithms in 802.11 ad-hoc networks

ABSTRACT

Understanding the performances of backoff algorithms in multi-hop ad hoc networks is a key feature to design efficient medium access protocols. The 802.11 binary exponential backoff algorithm and all the enhancements done to this algorithm have been studied in depth in a single hop context. Very few analytical studies are carried out on 802.11 backoff algorithms in a multi-hop context due to the difficulty of modeling. In this paper we propose an analytical study, based on a stochastic process algebra, of four backoff algorithms on two multi-hop scenarios. Performances of each backoff algorithms are computed from efficiency and fairness point of view

REFERENCES

• 1: IEEE standard for wireless LAN medium access control (MAC) and physical layer (PHY) specifications. ISO/IEC 8802-11:1999, Aug. 1999.
• 2: Vaduvur Bharghavan , Alan Demers , Scott Shenker , Lixia Zhang, MACAW: a media access protocol for wireless LAN's, Proceedings of the conference on Communications architectures, protocols and applications, p.212-225, August 31-September 02, 1994, London, United Kingdom
• 3: G. Bianchi. Performance analysis of the IEEE 802.11 DCF. IEEE Journal on Selected Areas in Communications, 18(3):353--547, March 2000.
• 4: P. Chatzimisios, A.C. Boucouvalas, V. Vitsas, A. Vafiadis, A. Oikonomidis, and P. Huang. A simple and effective backoff scheme for the IEEE 802.11 MAC protocol. In CITSA, Orlando, Florida, USA, July 2005.
• 5: Claude Chaudet , Isabelle Guérin Lassous , Eric Thierry , Bruno Gaujal, Study of the impact of asymmetry and carrier sense mechanism in IEEE 802.11 multi-hops networks through a basic case, Proceedings of the 1st ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks, October 04-04, 2004, Venezia, Italy [doi>10.1145/1023756.1023758]
• 6: Michele Garetto , Jingpu Shi , Edward W. Knightly, Modeling media access in embedded two-flow topologies of multi-hop wireless networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080851]
• 7: J. Hillston. A compositional approach to performance modeling. Phd. thesis, The University of Edinburgh, 1994.
• 8: Leï la Kloul , Fabrice Valois, Investigating unfairness scenarios in MANET using 802.11b, Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks, October 10-13, 2005, Montreal, Quebec, Canada [doi>10.1145/1089803.1089805]
• 9: Z. Li, S. Nandi, and A. K. Gupta. Modeling the short-term unfairness of ieee 802.11 in presence of hidden terminals. In NETWORKING, pages 613--625, 2004.
• 10: D. Parker M. Kwiatkowska, G. Norman. Prism: Probabilistic symbolic model checker. In PAPM/PROBMIV'01 Tools Session, Durham, North Carolina, USA, 2001.
• 11: T. Razafindralambo and F. Valois. Stochastic behavior study of backoff algorithms in case of hidden terminalsi. In PIMRC 2006 (to be published), Helsinki, Finland, 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Performance

Keywords:
802.11, ad-hoc networks, backoffs algorithms, performance evaluation