A new model for packet scheduling in multihop wireless networks

ABSTRACT

The goal of packet scheduling disciplines is to achieve fair and maximum allocation of channel bandwidth. However, these two criteria can potentially be in conflict in a generic-topology multihop wireless network where a single logical channel is shared among multiple contending flows and spatial reuse of the channel bandwidth is possible. In this paper, we propose a new model for packet scheduling that addresses this conflict. The main results of this paper are the following: (a) a two-tier service model that provides a minimum “fair” allocation of the channel bandwidth for each packet flow and additionally maximizes spatial reuse of bandwidth, (b) an ideal centralized packet scheduling algorithm that realizes the above service model, and (c) a practical distributed backoff-based channel contention mechanism that approximates the ideal service within the framework of the CSMA/CA protocol.

REFERENCES

• 1: C. Chang, J. Chang, K. Chen and M. You, "Guaranteed quality-of-service wireless access to ATM," IEEE JSA C, 1997.
• 2: Ji-Her Ju , Victor O. K. Li, An optimal topology-transparent scheduling method in multihop packet radio networks, IEEE/ACM Transactions on Networking (TON), v.6 n.3, p.298-306, June 1998 [doi>10.1109/90.700893]
• 3: 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]
• 4: Imrich Chlamtac , András Faragó, Making transmission schedules immune to topology changes in multi-hop packet radio networks, IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.23-29, Feb. 1994 [doi>10.1109/90.282605]
• 5: Sunghyun Choi , Kang G. Shin, Predictive and adaptive bandwidth reservation for hand-offs in QoS-sensitive cellular networks, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.155-166, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 6: Anup Kumar Talukdar , B. R. Badrinath , Arup Acharya, Rate adaptation schemes in networks with mobile hosts, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.169-180, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288278]
• 7: I. Chlamtac and A. Lerner, "Fair algorithms for maximal link activation in multihop radio networks," IEEE Trans. Communications, 35(7), July 1987.
• 8: 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
• 9: S. Lu, T. Nandagopal, and V. Bharghavan, "Fair scheduling in wireless packet networks," A CM MOBL COM'98, October 1998.
• 10: Z. Tang and J.J. Garacia-Luna-Aceves, "A protocol for topology-dependent transmission scheduling in wireless networks," WCNC'99, September 1999.
• 11: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 12: A. Parekh, "A generalized processor sharing approach to flow control in integrated services networks," PhD Thesis, MIT Laboratory for Information and Decision Systems, Technical Report LIDS-TR-2089, 1992.
• 13: P. Crescenzi and V. Kann, "A compendium of NP optimization problems," http ://www. nada.kth.se/ viggo/indez-en.html.
• 14: V. Bharghavan, "A new protocol for medium access in wireless packet networks," online document, 1999.
• 15: Magnús Halldórsson , Jaikumar Radhakrishnan, Greed is good: approximating independent sets in sparse and bounded-degree graphs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.439-448, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195221]
• 16: J. Kuri and S. Kasera, "Reliable multicast in multiaccess wireless LANs," IEEE INFOCOM'99, 1999.
• 17: J.C.R. Bennett and H. Zhang, "WF2Q: Worst-case fair weighted fair queueing," IEEE INFOCOM'96, 1996.
• 18: Pawan Goyal , Harrick M. Vin , Haichen Chen, Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.157-168, August 28-30, 1996, Palo Alto, California, United States
• 19: T.S. Ng, I. Stoica and H. Zhang, "Packet fair queueing algorithms for wireless networks with location-dependent errors," IEEE INFOCOM'98, March 1998.
• 20: Parameswaran Ramanathan , Prathima Agrawal, Adapting packet fair queueing algorithms to wireless networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.1-9, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288239]
• 21: N. H. Vaidya and P. Bahl, "Fair scheduling in broadcast environments," Microsoft Research Tech. Rep. MSR-TR- 99-61.
• 22: 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]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

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