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: 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]
• 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: 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]
• 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 , Mart L. Molle, An improved topology discovery algorithm for networks with wormhole routing and directed links, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.1-2, p.79-88, Jan. 14, 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, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.99, August 15-18, 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: Alberto Caprara , Hans Kellerer , Ulrich Pferschy, The Multiple Subset Sum Problem, SIAM Journal on Optimization, v.11 n.2, p.308-319, 2000 [doi>10.1137/S1052623498348481]
• 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: Douglas S. J. De Couto , Daniel Aguayo , John Bicket , Robert Morris, A high-throughput path metric for multi-hop wireless routing, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939000]
• 34: Engim Inc; www.engim.com