Ordered packet scheduling in wireless ad hoc networks: mechanisms and performance analysis

ABSTRACT

Wireless emph ad hoc networks based on the IEEE 802.11 protocol can incur severe unfairness even in simple topologies. In particular, two topological properties that we define in a graph-theoretic framework and refer to as information asymmetry and perceived collisions result in significant performance degradations and unfairness. In this paper, we present the design and analysis of Distributed Wireless Ordering Protocol (DWOP), a distributed scheduling and media access algorithm targeted towards ensuring that packets access the medium in an order defined by an ideal reference scheduler such as FIFO, Virtual Clock, or Earliest Deadline First. In this way, DWOP enables QoS differentiation as well as fairness when combined with TCP. Our key technique is piggybacking head-of-line packet priorities in IEEE 802.11 control messages so that nodes can assess the relative priority of their own queued packets. With a graph-theoretic problem formulation, we design DWOP to achieve the exact reference ordering in fully connected graphs, and to have well-characterized deviations from the reference order in more complex topologies. A simple theoretical model indicates that the scheme attains rapid convergence for newly arriving nodes, and extensive simulations indicate that nearly exact reference ordering can be achieved, even in complex asymmetric and perceived collision topologies.

REFERENCES

• 1: Lichun Bao , J. J. Garcia-Luna-Aceves, A new approach to channel access scheduling for Ad Hoc networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.210-221, July 2001, Rome, Italy [doi>10.1145/381677.381698]
• 2: Craig Barrack , Kai-Yeung Siu, A Distributed Scheduling Algorithm for Quality of Service Support in Multiaccess Networks, Proceedings of the Seventh Annual International Conference on Network Protocols, p.245, October 31-November 03, 1999
• 3: 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
• 4: E. Castillo. Extreme Value Theory in Engineering Academic Press, 1988.
• 5: S. Golestani. A self-clocked fair queueing scheme for broadband applications. In Proc. IEEE INFOCOM 1994.
• 6: Pawan Goyal , Harrick M. Vin , Haichen Cheng, Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.690-704, Oct. 1997 [doi>10.1109/90.649569]
• 7: IEEE. IEEE standard 802.11: Wireless LAN medium simuaccess control (MAC) and physical layer (PHY) specifications, 1997.
• 8: V. Kanodia , C. Li , A. Sabharwal , B. Sadeghi , E. Knightly, Distributed multi-hop scheduling and medium access with delay and throughput constraints, Proceedings of the 7th annual international conference on Mobile computing and networking, p.200-209, July 2001, Rome, Italy [doi>10.1145/381677.381697]
• 9: Jinyang Li , Charles Blake , Douglas S.J. De Couto , Hu Imm Lee , Robert Morris, Capacity of Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.61-69, July 2001, Rome, Italy [doi>10.1145/381677.381684]
• 10: Haiyun Luo , Songwu Lu, A topology-independent fair queueing model in ad hoc wireless networks, Proceedings of the 2000 International Conference on Network Protocols, p.325, November 14-17, 2000
• 11: H. Luo and S. Lu, A self-coordinating approach to distributed fair queueing in ad hoc wireless networks. In Proc. IEEE Infocom, 2001.
• 12: Haiyun Luo , Songwu Lu , Vaduvur Bharghavan, A new model for packet scheduling in multihop wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.76-86, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345923]
• 13: Thyagarajan Nandagopal , Tae-Eun Kim , Xia Gao , Vaduvur Bharghavan, Achieving MAC layer fairness in wireless packet networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.87-98, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345925]
• 14: Bob O'Hara , Al Petrick, The IEEE 802.11 Handbook: A Designer's Companion, Standards Information Network IEEE Press, 1999
• 15: T. Ozugur, M. Naghshineh, P. Kermani, and J. Copeland. Fair media access for wireless LANs. In Proc. IEEE GLOBECOM, 1999.
• 16: N. Vaidya and P. Bahl. Fair scheduling in broadcast environments, Aug. 1999. Microsoft Research Tech. Rep. MSR-TR-99--61.
• 17: Nitin H. Vaidya , Paramvir Bahl , Seema Gupta, Distributed fair scheduling in a wireless LAN, Proceedings of the 6th annual international conference on Mobile computing and networking, p.167-178, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345939]
• 18: L. Zhang. A New Architecture for Packet Switched Network Protocols. PhD dissertation, Massachusetts Institute of Technology, July 1989.

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, Performance