Forwarding capacity of an infinite wireless network

ABSTRACT

We study the maximal forwarding capacity of a massively dense wireless multi-hop network where a typical path consists of a vast number of hops. In such a network, the macroscopic level, corresponding to the scale of an end-to-end path, and the microscopic level, corresponding to the scale of a single hop, can be separated. At the macroscopic level the task is that of routing, while at the microscopic level the packets are forwarded based on the information received from the macroscopic level. We give a formulation for the forwarding problem and devise simulation algorithms based on an augmentation of the max-flow min-cut theorem for obtaining upper bounds for the maximal forwarding capacity. We compare the upper bounds with feasible forwarding methods and find out that the tightest bound is about three times the highest achieved performance.

REFERENCES

• 1: O. Apilo, P. Lassila, and J. Virtamo. Performance of local forwarding methods for geographic routing in large ad hoc networks. In Proceedings of The Fifth Annual Mediterranean Ad Hoc Networking Workshop (Med-Hoc-Net 2006), 2006.
• 2: F. Baccelli, B. Blaszczyszyn, and P. Muhlethaler. An aloha protocol for multihop mobile wireless networks. IEEE Transactions on Information Theory, 52(2):421--436, 2006.
• 3: Sanjit Biswas , Robert Morris, ExOR: opportunistic multi-hop routing for wireless networks, ACM SIGCOMM Computer Communication Review, v.35 n.4, October 2005
• 4: R. Catanuto, S. Toumpis, and G. Morabito. Opti{c,m}al: Optical/optimal routing in massively dense wireless networks. Proceedings of IEEE INFOCOM, pages 1010--1018, 2007.
• 5: T. Coenen, M. de Graaf, and R.J. Boucherie. An upper bound on multi-hop wireless network performance. In International Teletraffic Congress, volume 4516, pages 335--347, 2007.
• 6: M. Franceschetti, O Dousse, D.N.C. Tse, and P. Thiran. Closing the gap in the capacity of wireless networks via percolation theory. IEEE Transactions on Information Theory, 53(3):1009--1018, 2007.
• 7: P. Gupta and P.R. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2):388--404, 2000.
• 8: Esa Hyytiä , Jorma Virtamo, On traffic load distribution and load balancing in dense wireless multihop networks, EURASIP Journal on Wireless Communications and Networking, v.2007 n.1, p.21-21, January 2007 [doi>10.1155/2007/16932]
• 9: E. Hyytiä and J. Virtamo. On load balancing in a dense wireless multihop network. In NGI 2006, 2nd Conference on Next Generation Internet Design and Engineering, pages 72--79, 2006.
• 10: Lucian Popa , Afshin Rostamizadeh , Richard Karp , Christos Papadimitriou , Ion Stoica, Balancing traffic load in wireless networks with curveball routing, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1288107.1288131]
• 11: H. Takagi and L. Kleinrock. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Transactions on Communications, 32(3):246--257, 1984.
• 12: J.T. Virtamo. A model of reservation systems. IEEE Transactions on Communications, 40(1):109--118, 1992.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design, Performance

Keywords:
flow networks, forwarding capacity, wireless multihop networks