A distributed fair MAC flow allocation and scheduling framework for IEEE 802.11 based wireless mesh networks

ABSTRACT

We present a distributed fair MAC flow allocation and scheduling framework for IEEE 802.11 based wireless mesh networks. The framework consists of (1) a modified wireless ad hoc routing protocol to take into account bandwidth requirement, (2) a link information dissemination protocol to propagate local topology information, (3) a cooperative gradient-based iterative algorithm to allocate fairly MAC flow bandwidth and (4) a distributed fair MAC scheduler to coordinate access to the channel according to the allocated bandwidth. We stress the importance of our framework's practicality, such that it is easily deployable in real IEEE 802.11 based devices, and, most importantly, it is extensible to include other services such as QoS routing and admission control. Before carrying out an expensive on-site performance evaluation, we conduct numerous simulations to evaluate our framework, and the fairness index indicates, under extremely high traffic rates, that our framework is fair to more than 90% of the MAC flows in the network.

REFERENCES

• 1: http://core.it.uu.se/core/index.php/AODV-UU (2009-3-29)
• 2: http://www.isi.edu/nsnam/ns/ (2009-3-29)
• 3: IEEE standard for information technology - telecommunications and information exchange between systems-local and metropolitan area networks-specific requirements - part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) specifications. IEEE Std 802.11-2007 (Revision of IEEE Std 802.11-1999), pages C1--1184, June 12 2007.
• 4: W. Almesberger. Linux network traffic control - implementation overview. In EPFL ICA, April 1999.
• 5: B. Bensaou and Z. Fang. A fair mac protocol for IEEE802.11-based ad hoc networks: Design and implementation. IEEE Transactions on Wireless Communications, 6(8):2934--2941, 2007.
• 6: X.L. Huang and B. Bensaou. On max-min fairness and scheduling in wireless ad hoc networks: Analytical framework and implementation. In ACM MOBIHOC, 2001.
• 7: B. Bensaou, D. H. K. Tsang and K. T. Chan. Credit-based fair queueing (cbfq): A simple service-scheduling algorithm for packet-switched networks. IEEE/ACM Trans. Networking, 9(5):591--604, 2001.
• 8: K.T. Chan. Resource Allocation and QoS Quarantee in High Speed Networks. Master's thesis, Dept. of Electrical and Electronic Eng., Hong Kong Univ. of Science and Technology, Kwoloon, October 1996.
• 9: H. L. Chao and W. Liao. Credit-based slot allocation for multimedia mobile ad hoc networks. IEEE Journal on Selected Areas in Communications, 21(10):1642--1651, December 2003.
• 10: D. S. J. D. Couto, D. Aguayo, J. C. Bicket and R. Morris. A high-throughput path metric for multi-hop wireless routing. In MOBICOM, pages 134--146, 2003.
• 11: Z. Fang and B. Bensaou. Fair bandwidth sharing algorithms based on game theory frameworks for wireless ad-hoc networks. In INFOCOM, 2004.
• 12: F. V. Jensen and T. D. Nielsen. Bayesian Networks and Decision Graphs. Springer, 2007
• 13: Y. Jian and S. Chen, Can CSMA/CA networks be made fair? In MOBICOM, pages 235--246, 2008.
• 14: L. Jiang and S. Liew. Proportional fairness in wireless LANs and ad hoc networks. IN WCNC, 2005.
• 15: H. Luo and S. Lu. A topology independent fair queueing model in ad hoc wireless networks. In ICNP pages 325-, 2000.
• 16: C. E. Perkins and E. M. Royer. Ad-hoc on-demand distance vector routing In WMCSA, pages 90--100, 1999.
• 17: A. Rao and I. Stoica, Adaptive distributed time-slot based dcheduling for fairness in multi-hop wireless networks. In ICDCS, pages 874--882, 2008.

INDEX TERMS

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

General Terms:
Design

Keywords:
IEEE 802.11 wmns, fairness, implementation