Interference-aware topology control and QoS routing in multi-channel wireless mesh networks

ABSTRACT

The throughput of wireless networks can be significantly improved by multi-channel communications compared with single-channel communications since the use of multiple channels can reduce interference influence. In this paper, we study interference-aware topology control and QoS routing in IEEE 802.11-based multi-channel wireless mesh networks with dynamic traffic. Channel assignment and routing are two basic issues in such networks. Different channel assignments can lead to different network topologies. We present a novel definition of co-channel interference. Based on this concept, we formally define and present an effective heuristic for the minimum INterference Survivable Topology Control (INSTC) problem which seeks a channel assignment for the given network such that the induced network topology is interference-minimum among all K-connected topologies. We then formulate the Bandwidth-Aware Routing (BAR) problem for a given network topology, which seeks routes for QoS connection requests with bandwidth requirements. We present a polynomial time optimal algorithm to solve the BAR problem under the assumption that traffic demands are splittable. For the non-splittable case, we present a maximum bottleneck capacity path routing heuristic. Simulation results show that compared with the simple common channel assignment and shortest path routing approach, our scheme improves the system performance by 57% on average in terms of connection blocking ratio.

REFERENCES

• 1: Ian F. Akyildiz , Xudong Wang , Weilin Wang, Wireless mesh networks: a survey, Computer Networks and ISDN Systems, v.47 n.4, p.445-487, 15 March 2005 [doi>10.1016/j.comnet.2004.12.001]
• 2: Atul Adya , Paramvir Bahl , Jitendra Padhye , Alec Wolman , Lidong Zhou, A Multi-Radio Unification Protocol for IEEE 802.11 Wireless Networks, Proceedings of the First International Conference on Broadband Networks (BROADNETS'04), p.344-354, October 25-29, 2004 [doi>10.1109/BROADNETS.2004.8]
• 3: P. Bahl, Opportunities and challenges of community mesh networking, Keynote Presentation @ MICS Workshop in ETH Zurich, 2004.
• 4: V. Bahl, A. Adya, J. Padhye, A. Wolman. Reconsidering the wireless LAN platform with multiple radios, Workshop on Future Directions in Network Architecture, 2003.
• 5: Paramvir Bahl , Ranveer Chandra , John Dunagan, SSCH: slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless 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.1023742]
• 6: John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
• 7: Martin Burkhart , Pascal von Rickenbach , Roger Wattenhofer , Aaron Zollinger, Does topology control reduce interference?, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989462]
• 8: 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]
• 9: S. Even, An algorithm for determining whether the connectivity of a graph is at least k, SIAM Journal of Computing Vol. 4(1975), pp. 393--396.
• 10: S. Guo, O. Yang, QoS-aware minimum energy multicast tree construction in wireless ad hoc networks, Elsevier Journal of Ad Hoc Networks, Vol. 2(2004), pp. 217--229.
• 11: P. Gupta, P. R. Kumar, The capacity of wireless networks, IEEE Transactions on Information Theory, Vol. 46(2000), pp. 388--404.
• 12: IEEE 802.11 Working Group, Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, 1997.
• 13: IEEE 802.11a Working Group, Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications - Amendment 1: High-speed Physical Layer in the 5 GHz band, 1999.
• 14: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938993]
• 15: P. Kyasanur, N. H. Vaidya, Routing and interface assignment in multi-channel multi-interface wireless networks, Proceedings of WCNC'2005.
• 16: W. H. Liao, Y. C. Tseng, K. P. Shih, A TDMA-based bandwidth reservation protocol for QoS routing in a wireless mobile ad hoc network, Proceedings of IEEE ICC'2002, pp. 3186--3190.
• 17: C. R. Lin, J. S. Liu, QoS routing in ad hoc wireless networks, IEEE Journal on Selected Areas in Communications Vol. 17(1999), pp. 1426--1438.
• 18: H. Liu, X. Jia, D. Li, C. H. Lee, Bandwidth guaranteed call admission in TDMA/CDMA ad hoc wireless networks, Elsevier Journal of Ad Hoc Networks(2005), In press.
• 19: K. Moaveninejad, X. Y. Li, Low-interference topology control for wireless ad hoc networks, Journal of Ad Hoc and Sensor Wireless Networks(2005), Accepted for publication.
• 20: C. E. Perkins, E. M. Royer, S. R. Das, Quality of service for ad hoc on-demand distance vector routing (work in progress), IETF Internet Draft, 2000.
• 21: A. Raniwala, T. Chiueh, Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network, Proceedings of IEEE INFOCOM'2005.
• 22: Ashish Raniwala , Kartik Gopalan , Tzi-cker Chiueh, Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.8 n.2, April 2004 [doi>10.1145/997122.997130]
• 23: Jungmin So , Nitin H. Vaidya, Multi-channel mac for ad hoc networks: handling multi-channel hidden terminals using a single transceiver, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989487]
• 24: J. So, N. H. Vaidya, A routing protocol for utilizing multiple channels in multi-hop wireless networks with a single transceiver, UIUC Technical Report, 2004. Available at: http://www.crhc.uiuc.edu/wireless/groupPubs.html
• 25: Qi Xue , Aura Ganz, Ad hoc QoS on-demand routing (AQOR) in mobile ad hoc networks, Journal of Parallel and Distributed Computing, v.63 n.2, p.154-165, February 2003 [doi>10.1016/S0743-7315(02)00061-8]
• 26: H. Zhai, J. Wang, Y. Fang, Distributed packet scheduling for multihop flows in ad hoc networks,Proceedings of IEEE WCNC'2004, pp. 1081--1086.
• 27: C. Zhu, S. Corson, QoS routing for mobile ad hoc networks, Proceedings of IEEE INFOCOM'2002, pp. 958--967.

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:
Algorithms, Design, Performance

Keywords:
QoS routing, channel assignment, topology control, wireless mesh network