Capacity bounds for three classes of wireless networks: asymmetric, cluster, and hybrid

ABSTRACT

We present capacity results for three classes of wireless ad hoc networks, using a general framework that allows their unified treatment. The results hold with probability going to 1 as the number of nodes in the network approaches infinity, and under a general model for channel fading.We first study asymmetric networks that consist of n source nodes and around n^d destination nodes, communicating over a wireless channel. Each source node creates data traffic that is directed to a destination node chosen at random. When ½ ‹ d ‹ 1, an aggregate throughput that increases with n as n^½ is achievable. If, however, 0 ‹ d ‹ ½, bottlenecks are formed and the aggregate throughput can not increase faster than n^d.We also consider cluster networks, that consist of n client nodes and around n^d cluster heads, communicating over a wireless channel. Each of the clients wants to communicate with one of the cluster heads, but the particular choice of cluster head is not important. In this setting, the maximum aggregate throughput is on the order of n^d, and it can be achieved with no transmissions taking place between client nodes.We conclude with the study of hybrid networks. These consist of n wireless nodes and around n^d access points. The access points are equipped with wireless transceivers, but are also connected with each other through an independent network of infinite capacity. Their only task is to support the operation of the wireless nodes. When ½ ‹ d ‹ 1, an aggregate throughput on the order of n^d is achievable, through the use of the infrastructure. If, however, 0 ‹ d ‹ ½, using the infrastructure offers no significant gain, and the wireless nodes can achieve an aggregate throughput on the order of n^½ by using the wireless medium only.

REFERENCES

• 1: N. Bansal and Z. Liu. Capacity, delay and mobility in wireless ad-hoc networks.In Proc. IEEE INFOCOM, pages 1553--1563, San Francisco, CA, April 2003.
• 2: T. ElBatt and A. Ephremides. Joint scheduling and power control for wireless ad hoc networks.In Proc. IEEE INFOCOM, volume 2, pages 976--985, New York, NY, June 2002.
• 3: J. Eriksson, M. Faloutsos, and S. Krishnamurthy. Scalable ad hoc routing: The case of dynamic addressing. In Proc. IEEE INFOCOM, Hong Kong, China, Mar 2004.
• 4: M. V. Eyoboǧlu and J. G. D. Forney. Trellis precoding: Combined coding, precoding and shaping for intersymbol interference channels. IEEE Trans. Inform. Theory, 38(2):301--314, 1992.
• 5: W. Feller. An Introduction to Probability Theory and its Applications, volume I. New York, NY: John Wiley and Sons, 3rd edition, 1975.
• 6: A. E. Gamal, J. Mammen, B. Prabhakar, and D. Shah. Throughput-delay trade-off in wireless networks. In Proc. IEEE INFOCOM, Hong Kong, China, Mar 2004.
• 7: M. Grossglauser and D. Tse. Mobility increases the capacity of ad-hoc wireless networks. In Proc. IEEE INFOCOM, volume 3, pages 1360--1369, Anchorage, L, Apr. 2001.
• 8: P. Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Trans. Inform. Theory, 46(2):388--404, Mar. 2000.
• 9: 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]
• 10: B. Liu, Z. Liu, and D. Towsley. On the capacity of hybrid wireless networks. In Proc. IEEE INFOCOM, volume 2, pages 1543--1552, San Francisco, CA, April 2003.
• 11: W. Lou, W. Liu, and Y. Fang. SPREAD: Enhancing data confidentiality in mobile ad hoc networks. In Proc. IEEE INFOCOM, Hong Kong, China, Mar 2004.
• 12: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 13: R. Negi and A. Rajeswaran. Capacity of power constrained ad-hoc networks. In Proc. IEEE INFOCOM, Hong Kong, China, Mar 2004.
• 14: Christina Peraki , Sergio D. Servetto, On the maximum stable throughput problem in random networks with 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.778426]
• 15: T. Salonidis, Bhagwat, L. Tassiulas, and R. LaMaire. Distributed topology construction of bluetooth personal area networks. In Proc. IEEE INFOCOM, volume 3, pages 1577--1586, Anchorage, AL, Apr. 2001.
• 16: S. Toumpis and A. J. Goldsmith. Large wireless networks under fading, mobility, and delay constraints. In Proc. IEEE INFOCOM, Hong Kong, China, Mar 2004.
• 17: S. Toumpis, A. J. Goldsmith, and J. Sayir. Capacity results for asymmetric wireless networks. In Proc. Int. Zurich Sem., pages 180--183, Zurich, Switzerland, Feb. 2004.

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

Keywords:
asymmetric traffic, capacity, cluster networks, hybrid networks, infrastructure support, mobile ad hoc networks, wireless access