Bounds for the capacity of wireless multihop networks imposed by topology and demand

ABSTRACT

Existing work on the capacity of wireless networks predominantly considers homogeneous random networks with random work load. The most relevant bounds on the network capacity, e.g., take into account only the number of nodes and the area of the network. However, these bounds can significantly overestimate the achievable capacity in real world situations where network topology or traffic patterns often deviate from these simplistic assumptions. To provide analytically tractable yet asymptotically tight approximations of network capacity we propose a novel space-based approach. At the heart of our methodology lie simple functions which indicate the presence of active transmissions near any given location in the network and which constitute a tool well suited to untangle the interactions of simultaneous transmissions. We are able to provide capacity bounds which are tighter than the traditional ones and which involve topology and traffic patterns explicitly, e.g., through the length of Euclidean Minimum Spanning Tree, or through traffic demands between clusters of nodes. As an additional novelty our results cover unicast, multicast and broadcast and are asymptotically tight. Notably, our capacity bounds are simple enough to require only knowledge of node location, and there is no need for solving or optimizing multi-variable equations in our approach.

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: Ashish Agarwal , P. R. Kumar, Improved capacity bounds for wireless networks: Research Articles, Wireless Communications & Mobile Computing, v.4 n.3, p.251-261, May 2004 [doi>10.1002/wcm.v4:3]
• 3: Onur Arpacioglu , Zygmunt J. Haas, On the scalability and capacity of wireless networks with omnidirectional antennas, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984648]
• 4: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 5: O. Dousse and P. Thiran. Connectivity vs capacity in dense ad hoc networks. In INFOCOM, 2004.
• 6: M. Franceschetti, O. Dousse, D. Tse, and P. Thiran. On the throughput capacity of random wireless networks. IEEE Transactions on Information Theory, 52(6), 2006.
• 7: M. Gastpar and M. Vetterli. On the capacity of wireless networks: The relay case. In INFOCOM, 2002.
• 8: M. Grossglauser and D. N. C. Tse. Mobility increases the capacity of ad-hoc wireless networks. In INFOCOM, 2001.
• 9: G. A. Gupta , S. Toumpis , J. Sayir , R. R. Muller, On the Transport Capacity of Gaussian Multiple Access and Broadcast Channels, Proceedings of the Third International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, p.10-20, April 04-06, 2005 [doi>10.1109/WIOPT.2005.35]
• 10: P. Gupta and P. Kumar. Internets in the sky: The capacity of three dimensional wireless networks. Communications in Information and Systems, 1(1):33--50, 2001.
• 11: P. Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2):388--404, 2000.
• 12: P. Gupta and P. R. Kumar. Towards an information theory of large networks: an achievable rate region. IEEE Transactions on Information Theory, 49(8):1877--1894, 2003.
• 13: Alireza Keshavarz-Haddad , Vinay Ribeiro , Rudolf Riedi, Broadcast capacity in multihop wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161117]
• 14: A. Keshavarz-Haddad and R. Riedi. On the broadcast capacity of multihop wireless networks: Interplay of power, density and interference. In SECON, 2007.
• 15: S. R. Kulkarni and P. Viswanath. A deterministic approach to throughput scaling in wireless networks. IEEE Transactions on Information Theory, 50(6):1041--1049, 2004.
• 16: 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]
• 17: B. Liu, Z. Liu, and D. F. Towsley. On the capacity of hybrid wireless networks. In INFOCOM, 2003.
• 18: R. Negi and A. Rajeswaran. Capacity of power constrained ad-hoc networks. In INFOCOM, 2004.
• 19: A. Ozgur, O. Leveque, and D. Tse. Hierarchical cooperation achieves linear capacity scaling in ad hoc networks. In INFOCOM, 2007.
• 20: S. Ramanathan, A Unified Framework and Algorithm for (T/F/C)DMA Channel Assignment in Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.900, April 09-11, 1997
• 21: G. Sharma, R. R. Mazumdar, and N. B. Shroff. Delay and capacity trade-offs in mobile ad hoc networks: A global perspective. In INFOCOM, 2006.
• 22: 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]
• 23: S. Toumpis and A. J. Goldsmith. Large wireless networks under fading, mobility, and delay constraints. In INFOCOM, 2004.
• 24: R. Zheng. Information dissemination in power-constrained wireless network. In INFOCOM, 2006.

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:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Formal models of communication

General Terms:
Design, Performance, Theory

Keywords:
capacity of wireless networks, transport capacity