Distributed multi-hop scheduling and medium access with delay and throughput constraints

ABSTRACT

Providing quality of service in random access multi-hop wireless networks requires support from both medium access and packet scheduling algorithms. However, due to the distributed nature of ad hoc networks, nodes may not be able to determine the next packet that would be transmitted in a (hypothetical) centralized and ideal dynamic priority scheduler. In this paper, we develop two mechanisms for QoS communication in multi-hop wireless networks. First, we devise distributed priority scheduling a technique that piggybacks the priority tag of a node's head-of-line packet onto handshake and data packets; e.g., RTS/DATA packets in IEEE 802.11. By monitoring transmitted packets, each node maintains a scheduling table which is used to assess the node's priority level relative to other nodes. We then incorporate this scheduling table into existing IEEE 802.11 priority back-off schemes to approximate the idealized schedule. Second, we observe that congestion, link errors, and the random nature of medium access prohibit an exact realization of the ideal schedule. Consequently, we devise a scheduling scheme termedmulti-hop coordinationso that downstream nodes can increase a packet's relative priority to make up for excessive delays incurred upstream. We next develop a simple analytical model to quantitatively explore these two mechanisms. In the former case, we study the impact of the probability of overhearing another packet's priority index on the scheme's ability to achieve the ideal schedule. In the latter case, we explore the role of multi-hop coordination in increasing the probability that a packet satisfies its end-to-end QoS target. Finally, we perform a set of ns-2 simulations to study the scheme's performance under more realistic conditions.

REFERENCES

• 1: I. Aad and C. Castelluccia. Differentiation mechanisms for IEEE 802.11. In Proceedings of IEEE INFOCOM'01, Anchorage, Alaska, April 2001.
• 2: M. Andrews and L. Zhang. Minimizing end-to-end delay in high-speed networks with a simple coordinated schedule. In Proceedings of IEEE INFOCOM '99, New York, NY, March 1999.
• 3: 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
• 4: P. Bhagwat, P. Bhattacharya, A. Krishna, and S. Tripathi. Enhancing throughput over wireless LANs using channel state dependent packet scheduling. In Proceedings of IEEE INFOCOM'96, San Francisco, CA, March 1996.
• 5: G. Bianchi. Performance analysis of the IEEE 802.11 distributed coordination function. IEEE Journal on Selected Areas in Communications, 18(3):535-547, March 2000.
• 6: David D. Clark , Scott Shenker , Lixia Zhang, Supporting real-time applications in an Integrated Services Packet Network: architecture and mechanism, Conference proceedings on Communications architectures & protocols, p.14-26, August 17-20, 1992, Baltimore, Maryland, United States
• 7: IEEE. IEEE standard 802.11: Wireless LAN medium access control (MAC) and physical layer (PHY) specifications, 1997.
• 8: D. Johnson and D. Maltz. Mobile Computing, chapter Dynamic source routing in Ad Hoc wireless networks. Kluwer Academic, 1996.
• 9: Chengzhi Li , E. W. Knightly, Coordinated network scheduling: a framework for end-to-end services, Proceedings of the 2000 International Conference on Network Protocols, p.69, November 14-17, 2000
• 10: Songwu Lu , Vaduvur Bharghavan , R. Srikant, Fair scheduling in wireless packet networks, IEEE/ACM Transactions on Networking (TON), v.7 n.4, p.473-489, Aug. 1999 [doi>10.1109/90.793003]
• 11: 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
• 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: T. Ng, I. Stoica, and H. Zhang. Packet fair queueing algorithms for wireless networks with location dependent errors. In Proceedings of IEEE INFOCOM'98, San Francisco, CA, May 1998.
• 15: Bob O'Hara , Al Petrick, The IEEE 802.11 Handbook: A Designer's Companion, Standards Information Network IEEE Press, 1999
• 16: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• 17: S. Shenker. Fundamental design issues for the future Internet. IEEE Journal on Selected Areas in Communications, 13(7):1176-1188, September 1995.
• 18: Ion Stoica , Hui Zhang, Providing guaranteed services without per flow management, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.81-94, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 19: N. Vaidya and P. Bahl. Fair scheduling in broadcast environments, August 1999. Microsoft Research Tech. Rep. MSR-TR-99-61.
• 20: 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]
• 21: L. Zhang. A New Architecture for Packet Switched Network Protocols. Ph.D. dissertation, Massachusetts Institute of Technology, July 1989.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Cellular architecture (e.g., mobile)
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design, Experimentation