Distributed dynamic scheduling for end-to-end rate guarantees in wireless ad hoc networks

ABSTRACT

We present a framework for the provision of deterministic end-to-end bandwidth guarantees in wireless ad hoc networks. Guided by a set of local feasibility conditions, multi-hop sessions are dynamically offered allocations, further translated to link demands. Using a distributed Time Division Multiple Access (TDMA) protocol nodes adapt to the demand changes on their adjacent links by local, conflict-free slot reassignments. As soon as the demand changes stabilize, the nodes must incrementally converge to a TDMA schedule that realizes the global link (and session) demand allocation.We first derive sufficient local feasibility conditions for certain topology classes and show that trees can be maximally utilized.We then introduce a converging distributed link scheduling algorithm that exploits the logical tree structure that arises in several ad hoc network applications.Decoupling bandwidth allocation to multi-hop sessions from link scheduling allows support of various end-to-end Quality of Service (QoS) objectives. We focus on the max-min fairness (MMF) objective and design an end-to-end asynchronous distributed algorithm for the computation of the session MMF rates. Once the end-to-end algorithm converges, the link scheduling algorithm converges to a TDMA schedule that realizes these rates.We demonstrate the applicability of this framework through an implementation over an existing wireless technology. This implementation is free of restrictive assumptions of previous TDMA approaches: it does not require any a-priori knowledge on the number of nodes in the network nor even network-wide slot synchronization.

REFERENCES

• 1: NS notes and documentation. In http://www.isi.edu/vint/nsnam.
• 2: E. Arikan. Some complexity results about packet radio networks. Proc. IEEE Transactions on Information Theory, 30:681--685, July 1984.
• 3: D. Baker and A. Ephremides. The architectural organization of a packet radio network via a distributed algorithm. Proc. IEEE Transactions on Communications, 29:1694--1701, 1981.
• 4: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 5: BluetoothSIG. Specification of the Bluetooth system, version 1.2. In www.bluetooth.com.
• 6: C. Cheng , I. Cimet , S. Kumar, A protocol to maintain a minimum spanning tree in a dynamic topology, Symposium proceedings on Communications architectures and protocols, p.330-337, August 16-18, 1988, Stanford, California, United States
• 7: Z. Cao and E. Zegura. Utility Max-Min: An Application-Oriented Bandwidth Allocation Scheme. In Proc. IEEE INFOCOM, New York, NY, March 1999.
• 8: A. Charny. An algorithm for rate allocation in a packet switching network with feedback, M.Sc. Thesis, May 1994.
• 9: L. Chen, S. Low, and J. Doyle. Joint Congestion Control and Media Access Control Design for Ad Hoc Wireless Networks .InProc. IEEE INFOCOM, Miami, FL, USA, 2005.
• 10: S. Chen and C. Nahrstedt. Distributed Quality of Service Routing in ad hoc networks. Proc. IEEE Journal on Selected Areas in Communications, 17, August 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: Richard Draves , Jitendra Padhye , Brian Zill, Routing in multi-radio, multi-hop wireless mesh networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023732]
• 13: J. Edmonds. Maximum matching and a polyhedron with 0,1 vertices. In Proc. Journal of Research National Bureau of Standards, 69(B), 1965.
• 14: Z. Fang and B. Bensaou. Fair Bandwidth Sharing Algorithms based on Game Theory Frameworks for Wireless Ad-hoc Networks. In Proc. IEEE INFOCOM, Hong Kong, March 2004.
• 15: Violeta Gambiroza , Bahareh Sadeghi , Edward W. Knightly, End-to-end performance and fairness in multihop wireless backhaul networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023749]
• 16: J. Garcia-Luna-Aceves and J. Raju. Distributed Assignment of Codes for multi-hop Packet Radio Networks. In Proc. MILCOM, Monterey, CA, USA, October 1997.
• 17: Mario Gerla , Jack Tzu-Chieh Tsai, Multicluster, mobile, multimedia radio network, Wireless Networks, v.1 n.3, p.255-265, 1995 [doi>10.1007/BF01200845]
• 18: R. Guerin, J. Rank, S. Sarkar, and E. Vergetis. Forming Connected Topologies in Bluetooth Adhoc Networks. In Proc. International Teletraffic Congress (ITC), Berlin, Germany, September 2003.
• 19: 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]
• 20: B. Hajek and G. Sasaki. Link Scheduling in Polynomial Time. Proc. IEEE Transactions on Information Theory, 34:910--917, September 1988.
• 21: I. Holyer. The NP-completeness of edge coloring. Proc. SIAM Journal of Computing, 10:169--197, 1981.
• 22: Xiao Long Huang , Brahim Bensaou, On max-min fairness and scheduling in wireless ad-hoc networks: analytical framework and implementation, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501445.501447]
• 23: IBMResearch. BlueHoc: Bluetooth Performance Evaluation Tool. In http://oss.software.ibm.com/bluehoc/.
• 24: M. Inc. Fostering Disruptive Technologies. In www.meshnetworks.com, Maitland, FL, USA, January 2002.
• 25: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 26: Lampros Kalampoukas , Anujan Varma, Congestion management in high-speed networks, 1997
• 27: Shivkumar Kalyanaraman , Raj Jain , Sonia Fahmy , Rohit Goyal , Bobby Vandalore, The ERICA switch algorithm for ABR traffic management in ATM networks, IEEE/ACM Transactions on Networking (TON), v.8 n.1, p.87-98, Feb. 2000 [doi>10.1109/90.836480]
• 28: F. Kelly, A. Maulloo, and D. Tan. Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 49:237--252, 1998.
• 29: Murali Kodialam , Thyaga Nandagopal, Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938991]
• 30: C. Lin. On-demand QoS routing in Multihop mobile networks. In Proc. IEEE INFOCOM, Anchorage, AK, April 2001.
• 31: U. K. N. Johansson and L. Tassiulas. A distributed scheduling algorithm for a Bluetooth scatternet. In Proc. International Teletraffic Congress (ITC), Salvador da Bahia, Brazil, September 2001.
• 32: 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]
• 33: M. Post, A. Kershenbaum, and P. Sarachik. A Distributed Evolutionary Algorithm for Reorganizing Network Communications. In Proc. MILCOM, Boston, MA, October 1985.
• 34: M. Post, P. Sarachik, and A. Kershenbaum. A Biased Greedy Algorithm for Scheduling Multihop Radio Networks. In Proc. Annual Conference on Information Sciences and Systems (CISS), Johns Hopkins Univ., March 1985.
• 35: Raghupathy Sivakumar , Bevan Das , Vaduvur Bharghavan, Spine routing in ad hoc networks, Cluster Computing, v.1 n.2, p.237-248, 1998 [doi>10.1023/A:1019045801829 ]
• 36: T. Salonidis and L. Tassiulas. Asynchronous TDMA ad hoc networks: Scheduling and Performance. Proc. European Transactions In Telecommunications (ETT), 3, May-June 2004.
• 37: T. Salonidis and L. Tassiulas. Distributed dynamic scheduling for end-to-end rate guarantees in wireless ad hoc networks. Technical report, TR 2004-7, Institute of Systems Research (ISR), University of Maryland, College Park, MD, USA, 2004.
• 38: T. Salonidis and L. Tassiulas. Distributed on-line schedule adaptation for balanced slot allocation in wireless ad hoc networks. In Proc. IEEE International Workshop on Quality of Service (IWQoS), Montreal,Canada, June 2004.
• 39: S. Sarkar and L. Tassiulas. End-to-end bandwidth guarantees through fair local spectrum share in wireless ad-hoc networks. In Control and Decision Conference (CDC), Maui, HI, USA, December 2003.
• 40: C. Shannon. A theorem on colouring lines of a network. J. Math. Phys., 39:148--151, 1948.
• 41: J. Silvester. Perfect Scheduling in Multihop Broadcast Networks. In Proc. International Conference on Computer Communications (ICC), London, England, Sepmteber 1982.
• 42: G. Tan, A. Miu, J. Guttag, and H. Balakrishnan. An Efficient Scatternet Formation Algorithm for Dynamic Environments. In Proc. IASTED Communications and Computer Networks (CCN), Cambridge, MA, November 2002.
• 43: L. Tassiulas and S. Sarkar. Maxmin Fair Scheduling in Wireless Networks. In Proc. IEEE INFOCOM, New York, NY, USA, June 2002.
• 44: J. Wieselthier, G. Nguyen, and A. Ephremides. On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks. In Proc. IEEE INFOCOM,Tel Aviv, Israel, April 2000.
• 45: K. N. Y. Xue, B. Li. Price-based Resource Allocation in Wireless Ad Hoc Networks. In Proc. 11th International Workshop on Quality of Service (IWQoS), Monterey, CA, USA, June 2003.
• 46: Y. Yi and S. Shakkottai. Hop-by-hop Congestion Control over a Wireless Multi-hop Network. In Proc. IEEE INFOCOM, Hong Kong, March 2004.
• 47: G. Zaruba, S. Basagni, and I. Chlamtac. Bluetrees -scatternet formation to enable Bluetooth-based ad hoc networks. In Proc. International Conference on Computer Communications (ICC), St. Petersburg, Russia, June 2001.
• 48: W. Zhang and G. Cao. Optimizing Tree Reconfiguration for Mobile Target Tracking in Sensor Networks. In Proc. IEEE INFOCOM, Hong Kong, March 2004.
• 49: C. Zhu and M. Corson. QoS routing for mobile ad hoc networks. In Proc. IEEE INFOCOM, New York, NY, June 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Design, Performance

Keywords:
ad hoc networks, distributed, rate control, scheduling