E. Hyytiä and J. Virtamo, On Optimality of Single-Path Routes in Massively Dense Wireless Multi-Hop Networks, in The 10th ACM International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM), pp. 28-35, 2007, Crete Island, Greece.
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.
Links:
(C) ACM, (2007). This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in the Proceedings of MSWiM'07, (2007) http://doi.acm.org/10.1145/1298126.1298135
BibTeX entry:
@inproceedings{hyytia-mswim-2007,
author = {Esa Hyyti{\"a} and Jorma Virtamo},
title = {On Optimality of Single-Path Routes in Massively Dense Wireless Multi-Hop Networks},
booktitle = {The 10th {ACM} International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems ({MSWiM})},
address = {Crete Island, Greece},
year = {2007},
month = {Oct.},
pages = {28--35},
doiopt = {10.1145/1298126.1298135}
}