Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks

Abstract

The IEEE 802.11 Wireless LAN standards allow multiple non-overlapping frequency channels to be used simultaneously to increase the aggregate bandwidth available to end-users. Such bandwidth aggregation capability is routinely used in infrastructure mode operation, where the traffic to and from wireless nodes is distributed among multiple interfaces of an access point or among multiple access points to balance the traffic load. However, bandwidth aggregation is rarely used in the context of multi-hop 802.11-based LANs that operate in the ad hoc mode. Most past research efforts that attempt to exploit multiple radio channels require modifications to the MAC protocol and therefore do not work with commodity 802.11 interface hardware. In this paper, we propose and evaluate one of the first multi-channel multi-hop wireless ad-hoc network architectures that can be built using standard 802.11 hardware by equipping each node with multiple network interface cards (NICs) operating on different channels. We focus our attention on wireless mesh networks that serve as the backbone for relaying end-user traffic from wireless access points to the wired network. The idea of exploiting multiple channels is particularly appealing in wireless mesh networks because of their high capacity requirements to support backbone traffic. To reap the full performance potential of this architecture, we develop a set of centralized channel assignment, bandwidth allocation, and routing algorithms for multi-channel wireless mesh networks. A detailed performance evaluation shows that with intelligent channel and bandwidth assignment, equipping every wireless mesh network node with just 2 NICs operating on different channels can increase the total network goodput by a factor of up to 8 compared with the conventional single-channel ad hoc network architecture.

References

1. K. Jain, J. Padhye, V. N. Padmanabhan, L. Qiu; "Impact of interference on multi-hop wireless network performance"; MobiCom, 2003.
2. "IEEE 802.11b Standard"; standards.ieee.org/getieee802/download/802.11b-1999.pdf
3. "IEEE 802.11a Standard"; standards.ieee.org/ getieee802/download/802.11a-1999.pdf
4. A. Muir and J. J. Garcia-Luna-Aceves; "A Channel Access Protocol for Multihop Wireless Networks with Multiple Channels"; IEEE ICC 98.
5. J. So and N. Vaidya; "Multi-Channel MAC for Ad Hoc Networks: Handling Multi-Channel Hidden Terminals Using a Single Transceiver"; ACM MobiHoc, May 2004.
6. Wing-Chung Hung, K. L. Eddie Law, A. Leon-Garcia; "A Dynamic Multi-Channel MAC for Ad-Hoc LAN"; 21st Symp. on Comm. '02
7. Asis Nasipuri and Samir R. Das; "A Multichannel CSMA MAC Protocol for Mobile Multihop Networks"; Proc. of IEEE WCNC 1999.
8. R. Garces, J. G. L. Aceves; "Collision Avoidance and Resolution Multiple Access for Multichannel Wireless Networks,"; Infocom 2000.
9. J. So, N. H. Vaidya. "A Multi-Channel MAC Protocol for Ad Hoc Wireless Networks"; UIUC Tech Report, Jan 2003.
10. Ying-Yi Huang, and Mart L. Molle; "An improved topology discovery algorithm for networks with wormhole routing and directed link"; IEEE Computer Networks, 1999.
11. R. Chandra, C. Fetzer, K. Hogstedt; "Adaptive Topology Discovery in Hybrid Wireless Networks"; Informatics '02
12. K. C. Claffy, H. W. Braun, G. C. Polyzos; "A parameterizable methodology for Internet traffic flow profiling"; IEEE JSAC, 1995.
13. Y. J. Lin, M. C. Chan; "A Scalable monitoring approach based on aggregation and refinement"; IEEE JSAC, 2002.
14. A. Iwata, C.-C. Chiang, G. Pei, M. Gerla, and T.-W. Chen. "Scalable Routing Strategies for Ad-hoc Wireless Networks."; IEEE JSAC, 1999
15. E. M. Royer and C-K Toh.; "A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks"; IEEE Personal Communications, April 1999.
16. Mesh Networks Inc; www.meshnetworks.com
17. Nokia Inc.; "Nokia RoofTop Wireless Routing"; www.americasnetwork.com/americasnetwork/data/articlebrief/americasnetwork/412002/34898/article.pdf
18. Radiant Networks; www.radiantnetworks.com
19. R. Karrer, A. Sabharwal, E. Knightly; "Enabling Large-scale Wireless Broadband: A Case for TAPs"; HotNets '03
20. P. Bhagwaty, B. Ramanz, D. Sanghi; "Turning '03 802.11 Inside-Out"; HotNets
21. FireTide Inc.; www.firetide.com
22. Strix Networks Inc.; www.strixsystems.com
23. S. Lee and M. Gerla; "Split Multipath Routing with Maximally Disjoint Paths in Ad Hoc Networks"; IEEE ICC '01.
24. Kui Wu, Janelle Harms; "Performance Study of a Multipath Routing Method for Wireless Mobile Ad Hoc Networks"; MASCOTS, 2001.
25. Lianfang Zhang, Zenghua Zhao, Yantai Shu, Lei Wang, and Oliver W. W. Yang; "Load Balancing of Multipath Source Routing in Ad Hoc Networks"; Proc. of IEEE ICC 2002.
26. S. Bak, J. A. Cobb, E. L. Leiss; "Load-Balanced Routing via Randomization"; PDCS, 1999.
27. K. Gopalan; "Efficient Network Resource Allocation with QoS Guarantees"; TR #133, ECSL, SUNY-SB.
28. A. Caprara, H. Kellerer, U. Pferschy; "The Multiple Subset Sum Problem"; SIAM Journal on Optimization, V '0011.
29. V. Bahl, A. Adya, J. Padhye, A. Wolman. "Reconsidering the Wireless LAN Platform with Multiple Radios"; Workshop on Future Directions in Network Architecture '03.
30. P. H. Hsiao, A. Hwang, H. T. Kung, and D. Vlah; "Load-Balancing Routing for Wireless Access Networks"; Proc. of IEEE INFOCOM 2001.
31. I. Katzela and M. Naghshineh; "Channel assignment schemes for cellular mobile telecommunication systems: a comprehensive survey"; IEEE Personal Comm. June '96.
32. T. R. Jensen, B. Toft; "Graph Coloring Problems"; Wiley Interscience, New York, 1995.
33. D. Couto, et. al.; "A High-Throughput Path Metric for Multi-Hop Wireless Routing"; MobiCom, 2003.
34. Engim Inc; www.engim.com