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. A. Agarwal and P. R. Kumar. Capacity bounds for ad hoc and hybrid wireless networks. Computer Communication Review, 34(3):71--81, 2004.
2. A. Agarwal and P. R. Kumar. Improved capacity bounds for wireless networks. Wireless Communications and Mobile Computing, 4(3):251--261, 2004.
3. O. Arpacioglu and Z. J. Haas. On the scalability and capacity of wireless networks with omnidirectional antennas. In IPSN, 2004.
4. T. M. Cover and J. A. Thomas. Elements of Information Theory. John Wiley & Sons, Inc., 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, and R. R. Müller. On the transport capacity of gaussian multiple access and broadcast channels. In WiOpt, 2005.
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. A. Keshavarz-Haddad, V. Ribeiro, and R. Riedi. Broadcast capacity in multihop wireless networks. In MobiCom, 2006.
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. P. Kyasanur and N. H. Vaidya. Capacity of multi-channel wireless networks: impact of number of channels and interfaces. In MobiCom, 2005.
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. In INFOCOM, 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. S. Toumpis. Capacity bounds for three classes of wireless networks: asymmetric, cluster, and hybrid. In MobiHoc, 2004.
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

• Networks

  • Network types

    • Mobile networks

    • Wireless access networks

• Security and privacy

  • Cryptography

    • Mathematical foundations of cryptography

• Theory of computation

  • Computational complexity and cryptography

    • Communication complexity