Delay aware link scheduling for multi-hop TDMA wireless networks

ABSTRACT

Time division multiple access (TDMA) based medium access control (MAC) protocols can provide QoS with guaranteed access to the wireless channel. However, in multi-hop wireless networks, these protocols may introduce scheduling delay if, on the same path, an outbound link on a router is scheduled to transmit before an inbound link on that router. The total scheduling delay can be quite large since it accumulates at every hop on a path. This paper presents a method that finds conflict-free TDMA schedules with minimum scheduling delay.

We show that the scheduling delay can be interpreted as a cost, in terms of transmission order of the links, collected over a cycle in the conflict graph. We use this observation to formulate an optimization, which finds a transmission order with the min-max delay across a set of multiple paths. The min-max delay optimization is NP-complete since the transmission order of links is a vector of binary integer variables. We devise an algorithm that finds the transmission order with the minimum delay on overlay tree topologies and use it with a modified Bellman-Ford algorithm, to find minimum delay schedules in polynomial time. The simulation results in 802.16 mesh networks confirm that the proposed algorithm can find effective min-max delay schedules.

REFERENCES

• 1: P. Djukic and S. Valaee, "Link scheduling for minimum delay in spatial re-use TDMA," in Proc. IEEE INFOCOM, 2007, pp. 28-36.
• 2: IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed Broadband Wireless Access Systems, 802.16, 2004.
• 3: IEEE P802.11s/D1.01, Draft 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 Amendment: ESS Mesh Networking, 802.11s, 2006.
• 4: X. Lin, N. B. Shroff, and R. Srikant, "A tutorial on cross-layer optimization in wireless networks," IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 1452-1463, Aug. 2006.
• 5: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Wireless Networks, v.11 n.4, p.471-487, July 2005 [doi>10.1007/s11276-005-1769-9]
• 6: S. Ramanathan, A unified framework and algorithm for channel assignment in wireless networks, Wireless Networks, v.5 n.2, p.81-94, March 1999 [doi>10.1023/A:1019126406181]
• 7: Subramanian Ramanathan , Errol L. Lloyd, Scheduling algorithms for multihop radio networks, IEEE/ACM Transactions on Networking (TON), v.1 n.2, p.166-177, April 1993 [doi>10.1109/90.222924]
• 8: B. Hajek and G. Sasaki, "Link scheduling in polynomial time," IEEE Trans. Inf. Theory, vol. 34, no. 5, pp. 910-917, Sep. 1988.
• 9: Theodoros Salonidis , Leandros Tassiulas, Distributed dynamic scheduling for end-to-end rate guarantees in wireless ad hoc networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062709]
• 10: Murali Kodialam , Thyaga Nandagopal, Characterizing achievable rates in multi-hop wireless mesh networks with orthogonal channels, IEEE/ACM Transactions on Networking (TON), v.13 n.4, p.868-880, August 2005 [doi>10.1109/TNET.2005.852873]
• 11: Gaurav Sharma , Ravi R. Mazumdar , Ness B. Shroff, On the complexity of scheduling in wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161116]
• 12: S. Gandham, M. Dawande, and R. Prakash, "Link scheduling in sensor networks: Distributed edge coloring revisited," in Proc. IEEE INFOCOM, 2005, vol. 4, pp. 2492-2501.
• 13: S. Sarkar and K. Kar, "Achieving 2/3 throughput approximation with sequential maximal scheduling under primary interference contraints," in Proc. 44th Annu. Allerton Conf. Communication, Control and Computing , 2006, online.
• 14: M. Sanchez, J. Zander, and T. Giles, "Combined routing and scheduling for spatial TDMA in multihop ad hoc networks," in Proc. WPMC, 2003, vol. 2, pp. 781-785.
• 15: H.-Y. Wei, S. Ganguly, R. Izmailov, and Z. Haas, "Interference-aware IEEE 802.16 WiMax mesh networks," in Proc. IEEE VTC Spring'05, 2005, vol. 5, pp. 3102-3106.
• 16: Bo Han , Weijia Jia , Lidong Lin, Performance evaluation of scheduling in IEEE 802.16 based wireless mesh networks, Computer Communications, v.30 n.4, p.782-792, February, 2007 [doi>10.1016/j.comcom.2006.10.001]
• 17: S. J. Golestani, "A framing strategy for congestion management," IEEE J. Sel. Areas Commun., vol. 9, no. 7, pp. 1064-1077, Sep. 1991.
• 18: R. Nelson and L. Kleinrock, "Spatial TDMA: A collision-free multihop channel access protocol," IEEE Trans. Commun., vol. COM-33, pp. 934-944, Sep. 1985.
• 19: N. B. Salem and J. Hubaux, "A fair scheduling for wireless mesh networks," in Proc. Wimesh, 2005, http://www.cs.ucdavis.edu/~prasant/ wimesh.
• 20: C. E. Shannon, "A theorem on coloring the lines of a network," J. Math. Phys., vol. 28, pp. 148-151, 1949.
• 21: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 22: P. Djukic and S. Valaee, "Distributed link scheduling for TDMA mesh networks," in Proc. IEEE ICC, 2007, pp. 3823-3828.
• 23: G. Narlikar, G. Wilfong, and L. Zhang, "Designing multihop wireless backhaul networks with delay guarantees," in Proc. IEEE INFOCOM, 2006, pp. 1-12.
• 24: 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]
• 25: Leonidas Georgiadis , Roch Guérin , Vinod Peris , Kumar N. Sivarajan, Efficient network QoS provisioning based on per node traffic shaping, IEEE/ACM Transactions on Networking (TON), v.4 n.4, p.482-501, Aug. 1996 [doi>10.1109/90.532860]
• 26: IEEE Standard for Local and Metropolitan Area Networks Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, 802.11, 1999.
• 27: P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Trans. Inf. Theory, vol. 46, no. 2, pp. 388-404, Mar. 2000.
• 28: Leonardo Badia , Michele Mastrogiovanni , Chiara Petrioli , Stamatis Stefanakos , Michele Zorzi, An optimization framework for joint sensor deployment, link scheduling and routing in underwater sensor networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.11 n.4, October 2007 [doi>10.1145/1347364.1347374]
• 29: P. Serafini , W. Ukovich, A mathematical for periodic scheduling problems, SIAM Journal on Discrete Mathematics, v.2 n.4, p.550-581, Nov. 1989 [doi>10.1137/0402049]
• 30: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 31: R. T. Rockafellar, Network Flows and Monotropic Optimization. New York: Wiley, 1984.
• 32: Petar Djukic, Scheduling algorithms for tdma wireless multihop networks, University of Toronto, Toronto, Ont., Canada, 2008
• 33: G. J. Minty, "A theorem on n-coloring the points of a linear graph," Amer. Math. Month., vol. 67, pp. 623-624, 1962.
• 34: Zsolt Tuza, Graph coloring in linear time, Journal of Combinatorial Theory Series B, v.55 n.2, p.236-243, July, 1992 [doi>10.1016/0095-8956(92)90042-V]
• 35: Haiyun Luo , Songwu Lu , Vaduvur Bharghavan , Jerry Cheng , Gary Zhong, A packet scheduling approach to QoS support in multihop wireless networks, Mobile Networks and Applications, v.9 n.3, p.193-206, June 2004 [doi>10.1145/1012113.1012117]
• 36: Jitendra Padhye , Victor Firoiu , Donald F. Towsley , James F. Kurose, Modeling TCP Reno performance: a simple model and its empirical validation, IEEE/ACM Transactions on Networking (TON), v.8 n.2, p.133-145, April 2000 [doi>10.1109/90.842137]
• 37: P. Djukic and S. Valaee, "Quality-of-service provisioning in multi-service TDMA mesh networks," in Proc. 20th Int. Teletraffic Congr., 2007, pp. 841-852.
• 38: L. A. Wolsey, Integer Programming. New York: Wiley-Interscience, 1998.
• 39: P. Djukic and S. Valaee, "Scheduling algorithms for 802.16 mesh networks," in WiMax/MobileFi: Advanced Research and Technology, Y. Xiao, Ed. New York: Auerbach, 2007, pp. 267-288.
• 40: Min Cao , Wenchao Ma , Qian Zhang , Xiaodong Wang , Wenwu Zhu, Modelling and performance analysis of the distributed scheduler in IEEE 802.16 mesh mode, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062701]

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.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Minimax approximation and algorithms

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Performance

Keywords:
TDMA scheduling algorithms, scheduling delay, stop-and-go queueing