On optimality of single-path routes in massively dense wireless multi-hop networks

ABSTRACT

We consider the load balancing problem in large wireless multi-hop networks, often referred to as massively dense wireless multi-hop networks. A network is considered to be massively dense if there are nodes practically everywhere and a typical distance between two nodes is much larger than the transmission range necessitating communication over a large number of hops. The task is to choose the routes in such a way that the maximum relayed traffic load in the network is minimized. In fixed networks the multi-path routes generally yield a lower congestion and thus allow higher throughput. In contrast, we show that in the case of massively dense wireless multi-hop networks the optimal load balancing can be achieved by single-path routing. In particular, we show how any given multi-path routing can be transformed to a single-path routing with at least the same level of performance. The concepts are illustrated by numerical examples where the network nodes are assumed to reside inside a unit disk with uniform traffic demands. The shortest path routes, corresponding to straight line segments, yield a maximum traffic load of 0.637, whereas the single-path routes obtained by numerical optimization yield 0.343, corresponding to 46% reduction in the traffic load.

REFERENCES

• 1: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 2: S. Toumpis and L. Tassiulas, ''Optimal deployment of large wireless sensor networks,'' IEEE Trans. Information Theory, vol. 52, no. 7, pp. 2935--2953, 2006.
• 3: M. Kalantari and M. Shayman, ''Routing in wireless ad hoc networks by analogy to electrostatic theory,'' in IEEE International Conference on Communications (ICC'04), Paris, France, June 2004, pp. 4028--4033.
• 4: Philippe Jacquet, Geometry of information propagation in massively dense ad hoc networks, 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.989479]
• 5: S. Toumpis, ''Optimal design and operation of massively dense wireless networks,'' in ACM Inter-Perf '06, Oct. 2006.
• 6: Roberto Catanuto and Giacomo Morabito, ''Optimal routing in dense wireless multihop networks as a geometrical optics solution to the problem of variations,'' in IEEE International Conference on Communications (ICC'06), Istanbul, Turkey, June 2006.
• 7: Roberto Catanuto, Stavros Toumpis, and Giacomo Morabito, ''Opti{c,m}al: Optical/optimal routing in massively dense wireless networks,'' in Proc. of IEEE Infocom '07, Anchorage, Alaska, May 2007.
• 8: Ness Shroff and Sungoh Kwon, ''Paradox of shortest path routing for large multi-hop wireless networks,'' in Proc. of IEEE Infocom '07, Anchorage, Alaska, May 2007.
• 9: Peter P. Pham and Sylvie Perreau, ''Performance analysis of reactive shortest path and multi-path routing mechanism with load balance,'' in Proc. of IEEE Infocom '03, San Francisco, USA, March-April 2003, vol. 1, pp. 251--259.
• 10: Yashar Ganjali and Abtin Keshavarzian, ''Load balancing in ad hoc networks: Single-path routing vs. multi-path routing,'' in Proc. of IEEE Infocom '04, Hong Kong, Mar. 2004.
• 11: Esa Hyytiä , Pasi Lassila , Aleksi Penttinen , János Roszik, Traffic load in a dense wireless multihop network, Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks, October 10-13, 2005, Montreal, Quebec, Canada [doi>10.1145/1089803.1089806]
• 12: 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]
• 13: I. Sneddon, Elements of partial differential equations, McGraw-Hill Book Company, 1957.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms, Performance, Theory

Keywords:
load balancing, multi-path, single-path, wireless multi-hop network