Routing and link-layer protocols for multi-channel multi-interface ad hoc wireless networks

ABSTRACT

Wireless technologies, such as IEEE 802.11a, that are used in ad hoc networks provide for multiple non-overlapping channels. Most ad hoc network protocols that are currently available are designed to use a single channel. However, the available network capacity can be increased by using multiple channels. This paper presents new protocols specifically designed to exploit multiple channels. Our protocols simplify the use of multiple channels by using multiple interfaces, although the number of interfaces per host is typically smaller than the number of channels. We propose a link layer protocol to manage multiple channels, and it can be implemented over existing IEEE 802.11 hardware. We also propose a new routing metric for multi-channel multi-interface networks, and the metric is incorporated into an on-demand routing protocol that operates over the link layer protocol. Simulation results demonstrate the effectiveness of the proposed approach in significantly increasing network capacity, by utilizing all the available channels, even when the number of interfaces per host is smaller than the number of channels.

REFERENCES

• 1: IEEE Standard for Wireless LAN-Medium Access Control and Physical Layer Specification, P802.11, 1999.
• 2: Paramvir Bahl , Atul Adya , Jitendra Padhye , Alec Walman, Reconsidering wireless systems with multiple radios, ACM SIGCOMM Computer Communication Review, v.34 n.5, October 2004 [doi>10.1145/1039111.1039122]
• 3: R. Draves, J. Padhye, and B. Zill, "Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks," in ACM Mobicom, 2004.
• 4: P. Kyasanur and N. H. Vaidya, "Capacity of Multi-Channel Wireless Networks: Impact of Number of Channels and Interfaces," in ACM Mobicom, 2005.
• 5: P. Kyasanur and N. H. Vaidya, "Routing and Interface Assignment in Multi-Channel Multi-Interface Wireless Networks," in IEEE WCNC, 2005.
• 6: D. B. Johnson, D. A. Maltz, and Y.-C. Hu, "The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR)," Ietf Manet Working Group (Draft 10), 2004.
• 7: M. Alicherry, R. Bhatia, and L. Li, "Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks," in ACM Mobicom, 2005.
• 8: M. Kodialam and T. Nandagopal, "Characterizing the capacity region in multi-radio multi-channel wireless mesh networks," in ACM Mobicom, 2005.
• 9: A. Nasipuri, J. Zhuang, and S. R. Das, "A Multichannel CSMA MAC Protocol for Multihop Wireless Networks," in IEEE WCNC, 1999.
• 10: N. Jain, S. Das, and A. Nasipuri, "A Multichannel CSMA MAC Protocol with Receiver-Based Channel Selection for Multihop Wireless Networks," in IC3N, 2001.
• 11: 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]
• 12: M. X. Gong and S. F. Midkiff, "Distributed Channel Assignment Protocols: A Cross-Layer Approach," in IEEE WCNC, 2005.
• 13: 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]
• 14: C. Perkins, E. Belding-Royer, and S. Das, "Ad hoc On-Demand Distance Vector (AODV) Routing," in Ietf RFC 3561, July 2003.
• 15: N. Shacham and P. King., "Architectures and Performance of Multichannel Multihop Packet Radio Networks," IEEE Journal on Selected Area in Communication, vol. 5, no. 6, pp. 1013--1025, July 1987.
• 16: J. So and N. H. Vaidya, "A Routing Protocol for Utilizing Multiple Channels in Multi-Hop Wireless Networks with a Single Transceiver," Tech. Rep., UIUC, Oct 2004.
• 17: 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]
• 18: 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]
• 19: A. Raniwala and T. Chiueh, "Architecture and Algorithms for an IEEE 802.11-Based Multi-Channel Wireless Mesh Network," in IEEE Infocom, 2005.
• 20: "Atheros inc," http://www.atheros.com.
• 21: R. Chandra, P. Bahl, and P. Bahl, "MultiNet: Connecting to Multiple IEEE 802.11 Networks Using a SingleWireless Card," in IEEE Infocom, Hong Kong, 2004.
• 22: 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]
• 23: Scalable Network Technologies, "Qualnet simulator version 3.6," http://www.scalablenetworks.com.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
  C.4 PERFORMANCE OF SYSTEMS

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

General Terms:
Algorithms, Design, Performance