E. Hyytiä and J. Virtamo, Near-Optimal Load Balancing in Dense Wireless Multi-Hop Networks, in NGI 2008, 4th Conference on Next Generation Internet Networks, pp. 181-188, 2008, Kraków, Poland.
Abstract: We consider the load balancing problem in wireless multi-hop networks. In the limit of a dense network, there is a strong separation between the macroscopic and microscopic scales, and the load balancing problem can be formulated as finding continuous curves (``routes'') between all source-destination pairs that minimize the maximum of the so-called scalar packet flux (``traffic load''). In this paper we re-formulate the problem by focusing entirely on the so-called d-flows (vector flow field of packets with a common destination x) and by looking at the equation these flows have to satisfy. The general solution to this equation can be written in terms of a single unknown scalar function, psi(r,x), related to the circulation density of the d-flow, for which function the optimization task can be presented as a problem of variational calculus. In this approach, we avoid completely dealing with systems of paths and calculating the load distribution resulting from the use of a given set of paths. Once the optimal solution for psi(r,x) is found the corresponding paths are obtained as the flow lines of the d-flows. In the example of a unit disk with uniform traffic demands we are able to find a set of paths which is considerably better than any previously published results, yielding a low maximal scalar flux and an extraordinarily flat load distribution. We further illustrate the methodology for a unit square with comparable improvements achieved.
Links:
(C) 2008 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
BibTeX entry:
@inproceedings{hyytia-ngi-2008,
author = {Esa Hyyti{\"a} and Jorma Virtamo},
title = {Near-Optimal Load Balancing in Dense Wireless Multi-Hop Networks},
booktitle = {{NGI} 2008, 4th Conference on Next Generation Internet Networks},
address = {Krak{\'o}w, Poland},
year = {2008},
month = {Apr.},
pages = {181--188},
doiopt = {10.1109/NGI.2008.31}
}