Throughput capacity of random ad hoc networks with infrastructure support

ABSTRACT

In this paper, we consider the transport capacity of ad hoc networks with a random flat topology under the present support of an infinite capacity infrastructure network. Such a network architecture allows ad hoc nodes to communicate with each other by purely using the remaining ad hoc nodes as their relays. In addition, ad hoc nodes can also utilize the existing infrastructure fully or partially by reaching any access point (or gateway) of the infrastructure network in a single or multi-hop fashion. Using the same tools as in [1], we show that the per source node capacity of T(W/log(N)) can be achieved in a random network scenario with the following assumptions: (i) The number of ad hoc nodes per access point is bounded above, (ii) each wireless node, including the access points, is able to transmit at W bits/sec using a fixed transmission range, and (iii) N ad hoc nodes, excluding the access points, constitute a connected topology graph. This is a significant improvement over the capacity of random ad hoc networks with no infrastructure support which is found as T(W/vN log(N)) in [1]. Although better capacity figures may be obtained by complex network coding or exploiting mobility in the network, infrastructure approach provides a simpler mechanism that has more practical aspects. We also show that even when less stringent requirements are imposed on topology connectivity, a per source node capacity figure that is arbitrarily close to T(1) cannot be obtained. Nevertheless, under these weak conditions, we can further improve per node throughput significantly.

REFERENCES

• 1: P. Gupta and P.R. Kumar, "The Capacity of Wireless Networks," IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 388--404, March 2000.
• 2: Joseph P. Macker, Vincent D. Park, and M. Scott Corson, "Mobile and Wireless Internet Services: Putting the Pieces Together," IEEE Communications Magazine, vol. 39, no. 6, pp. 148--155, June 2001.
• 3: Ying-Dar Lin and Yu-Ching Hsu, "Multihop Cellular: A New Architecture for Wireless Communications," in IEEE INFOCOM 2000, March 2000, pp. 1273--1282.
• 4: John W. Noerenberg II, "Bridging Wireless Protocols," IEEE Communications Magazine, vol. 39, no. 11, pp. 90--97, Nov. 2001.
• 5: George Neonakis Aggélou and Rahim Tafazolli, "On the Relaying Capability of Next-Generation GSM Cellular Networks," IEEE Personal Communications, pp. 40--47, Feb. 2001.
• 6: A.N. Zadeh, B. Jabbari, R. Pickholtz, B. Vojcic, "Self-organizing packet radio ad hoc networks with overlay (SOPRANO)," IEEE Communications Magazine, vol. 40, pp. 149--157, June 2002.
• 7: M. Gastpar and M. Vetterli, "On the capacity of wireless networks: The relay case," in Proceedings of the IEEE Infocom, 2002.
• 8: Benyuan Liu, Zhen Liu, and Don Towsley, "On the capacity of hybrid wireless networks," in Proceedings of the IEEE Infocom, 2003.
• 9: Jiang Xie and Ian F. Akyildiz, "A Distributed Dynamic Regional Location Management Scheme for Mobile IP," in Proceedings of IEEE Infocom, June 2002.
• 10: M. Grossglauser and D. Tse, "Mobility increases the capacity of ad-hoc wireless networks," in Proceedings of the IEEE Infocom, 2001.
• 11: P. Gupta and P.R. Kumar, "Towards an information theory of large networks: An achievable rate region," in IEEE Int. Symp. Info. Theory, Washington DC, June 2001.
• 12: Enrique J. Duarte-Melo and Mingyan Liu, "Data-Gathering Wireless Sensor Networks: Organization and Capacity," Uni. of Michigan, Ann Arbor, Tech. Rep., 2002.
• 13: P. Gupta and P.R. Kumar, "Critical power for asymptotic connectivity in wireless networks," Stochastic Analysis, Control, Optimization and Application: A Volume in Honor of W.H. Fleming, March 1998.
• 14: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 15: Athanasios Papoulis, Probability, Random Variables, and Stochastic Processes. McGraw-Hill Inc., 1991.
• 16: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 17: P.T. Olivier Dousse and M. Hasler, "Connectivity in ad-hoc and hybrid networks," in Proceedings of the IEEE Infocom, 2002.
• 18: 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
• 19: Jinyang Li , Charles Blake , Douglas S.J. De Couto , Hu Imm Lee , Robert Morris, Capacity of Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.61-69, July 2001, Rome, Italy [doi>10.1145/381677.381684]

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:
hybrid wireless networks, random ad hoc networks, transport capacity