Capacity of multi-channel wireless networks: impact of number of channels and interfaces

ABSTRACT

This paper studies how the capacity of a static multi-channel network scales as the number of nodes, n, increases. Gupta and Kumar have determined the capacity of single-channel networks, and those bounds are applicable to multi-channel networks as well, provided each node in the network has a dedicated interface per channel.In this work, we establish the capacity of general multi-channel networks wherein the number of interfaces, m, may be smaller than the number of channels, c. We show that the capacity of multi-channel networks exhibits different bounds that are dependent on the ratio between c and m. When the number of interfaces per node is smaller than the number of channels, there is a degradation in the network capacity in many scenarios. However, one important exception is a random network with up to O(log n) channels, wherein the network capacity remains at the Gupta and Kumar bound of Θ(W√noverlog n) bits/sec, independent of the number of interfaces available at each node. Since in many practical networks, number of channels available is small (e.g., IEEE 802.11 networks), this bound is of practical interest. This implies that it may be possible to build capacity-optimal multi-channel networks with as few as one interface per node. We also extend our model to consider the impact of interface switching delay, and show that in a random network with up to O(log n) channels, switching delay may not affect capacity if multiple interfaces are used.

REFERENCES

• 1: Ashish Agarwal , P. R. Kumar, Capacity bounds for ad hoc and hybrid wireless networks, ACM SIGCOMM Computer Communication Review, v.34 n.3, July 2004 [doi>10.1145/1031134.1031143]
• 2: 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]
• 3: N. Bansal and Z. Liu. Capacity, delay and mobility in wireless ad-hoc networks. In Infocom, pages 1553--1563, 2003.
• 4: S. Diggavi, M. Grossglauser, and D. Tse. Even one-dimensional mobility increases adhoc wireless capacity. Technical report, UC Berkeley, 2003.
• 5: C. H. Doan, S. Emami, D. A. Sobel, A. M. Niknejad, and R. W. Brodersen. Design considerations for 60 GHz CMOS radios. IEEE Communications Magazine, 42(132--140), Dec 2004.
• 6: 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]
• 7: A. E. Gamal, J. Mammen, B. Prabhakar, and D. Shah. Throughput-delay trade-off in wireless networks. In Infocom, 2004.
• 8: M. Gastpar and M. Vetterli. On the capacity of wireless networks: The relay case. In Infocom, pages 1577--1586, New York, USA, June 2002.
• 9: M. Grossglauser and D. Tse. Mobility increases the capacity of ad-hoc wireless networks. In Infocom, 2001.
• 10: P. Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2):388--404, March 2000.
• 11: IEEE Standard for Wireless LAN-Medium Access Control and Physical Layer Specification, P802.11, 1999.
• 12: Ula? C. Kozat , Leandros Tassiulas, Throughput capacity of random ad hoc networks with infrastructure support, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938992]
• 13: P. Kyasanur and N. H. Vaidya. Routing in multi-channel multi-interface ad hoc wireless networks. Technical report, University of Illinois at Urbana-Champaign, December 2004.
• 14: P. Kyasanur and N. H. Vaidya. Capacity of multi-channel wireless networks: Impact of number of channels and interfaces. Technical report, University of Illinois at Urbana-Champaign, March 2005.
• 15: P. Kyasanur and N. H. Vaidya. Routing and interface assignment in multi-channel multi-interface wireless networks. In WCNC, 2005.
• 16: J. Li, Z. J. Haas, , and M. Sheng. Capacity evaluation of multi-channel multi-hop ad hoc networks. In International Conference on Personal Communications, 2002.
• 17: B. Liu, Z. Liu, and D. Towsley. On the capacity of hybrid wireless networks. In Infocom, 2003.
• 18: A. Nasipuri, J. Zhuang, and S. Das. A multichannel CSMA MAC protocol for multihop wireless networks. In WCNC, September 1999.
• 19: R. Negi and A. Rajeswaran. Capacity of power constrained ad-hoc networks. In Infocom, 2004.
• 20: E. Perevalov and R. Blum. Delay limited capacity of ad hoc networks: Asymptotically optimal transmission and relaying strategy. In Infocom, 2003.
• 21: Martin Raab , Angelika Steger, "Balls into Bins" - A Simple and Tight Analysis, Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.159-170, October 08-10, 1998
• 22: A. Raniwala and T. Chiueh. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network. In Infocom, 2005.
• 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 and N. H. Vaidya. Routing and channel assignment in multi-channel multi-hop wireless networks with single-nic devices. Technical report, University of Illinois at Urbana-Champaign, December 2004.
• 25: J. So and N. H. Vaidya. A routing protocol for utilizing multiple channels in multi-hop wireless networks with a single transceiver. Technical report, University of Illinois at Urbana-Champaign, October 2004.
• 26: Stavros Toumpis, Capacity bounds for three classes of wireless networks: asymmetric, cluster, and hybrid, 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.989477]
• 27: S. Toumpis and A. J. Goldsmith. Large wireless networks under fading, mobility, and delay constraints. In Infocom, 2004.
• 28: Vladimir Vapnik, Estimation of Dependences Based on Empirical Data: Springer Series in Statistics (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 29: V. N. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264--280, 1971.
• 30: D. B. West. Introduction to Graph Theory. Prentice Hall, 2 edition, 2001.
• 31: Su Yi , Yong Pei , Shivkumar Kalyanaraman, On the capacity improvement of ad hoc wireless networks using directional antennas, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778429]
• 32: H. Zhang and J. C. Hou. Capacity of wireless ad-hoc networks under ultra wide band with power constraint. In Infocom, 2005.

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

Keywords:
ad hoc networks, capacity, mesh networks, multiple channels, multiple interfaces