Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks

ABSTRACT

Multi-hop infrastructure wireless mesh networks offer increased reliability, coverage and reduced equipment costs over their single-hop counterpart, wireless LANs. Equipping wireless routers with multiple radios further improves the capacity by transmitting over multiple radios simultaneously using orthogonal channels. Efficient channel assignment and routing is essential for throughput optimization of mesh clients. Efficient channel assignment schemes can greatly relieve the interference effect of close-by transmissions; effective routing schemes can alleviate potential congestion on any gateways to the Internet, thereby improving per-client throughput. Unlike previous heuristic approaches, we mathematically formulate the joint channel assignment and routing problem, taking into account the interference constraints, the number of channels in the network and the number of radios available at each mesh router. We then use this formulation to develop a solution for our problem that optimizes the overall network throughput subject to fairness constraints on allocation of scarce wireless capacity among mobile clients. We show that the performance of our algorithms is within a constant factor of that of any optimal algorithm for the joint channel assignment and routing problem. Our evaluation demonstrates that our algorithm can effectively exploit the increased number of channels and radios, and it performs much better than the theoretical worst case bounds.

REFERENCES

• 1: Chaska wireless solutions. http://www.chaska.net/.
• 2: ILOG CPLEX mathematical programming optimizers. http://www.ilog.com/products/cplex/.
• 3: Meshdynamics inc. http://www.meshdynamics.com/.
• 4: 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]
• 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: Yigal Bejerano, Efficient integration of multi-hop wireless and wired networks with QoS constraints, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570672]
• 7: Yigal Bejerano , Seung-Jae Han , Li (Erran) Li, Fairness and load balancing in wireless LANs using association control, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023751]
• 8: R. Bhatia and M. Kodialam. On power efficient communication over multi-hop wireless networks: Joint routing, scheduling and power control. In Proc. IEEE INFOCOM, pages 1457--1466, 2004.
• 9: Ranveer Chandra , Lili Qiu , Kamal Jain , Mohammad Mahdian, Optimizing the Placement of Internet TAPs in Wireless Neighborhood Networks, Proceedings of the Network Protocols, 12th IEEE International Conference on (ICNP'04), p.271-282, October 05-08, 2004
• 10: 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]
• 11: P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Transactions on Information Theory, IT-46(2):388--404, Mar. 2000.
• 12: 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]
• 13: 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]
• 14: Murali Kodialam , Thyaga Nandagopal, Characterizing the capacity region in multi-radio multi-channel wireless mesh networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080837]
• 15: S. Kravitz. Packing cylinders into cylindrical containers. In Math. Mag., volume 40, pages 65--70, 1967.
• 16: V. S. Anil Kumar , Madhav V. Marathe , Srinivasan Parthasarathy , Aravind Srinivasan, Algorithmic aspects of capacity in wireless networks, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 17: Pradeep Kyasanur , Nitin H. Vaidya, Capacity of multi-channel wireless networks: impact of number of channels and interfaces, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080835]
• 18: A. Raniwala and T.-C. Chiueh. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network. In Proc. IEEE INFOCOM, 2005.
• 19: 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]

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, Theory

Keywords:
approximation algorithm, graph theory, mathematical programming, wireless mesh networks