ALCOMFT-TR-03-28

Stefan Funke, Domagoj Matijevic and Peter Sanders
Approximating Energy Efficient Paths in Wireless Multi-Hop Networks
MPI. Work packages 2 and 4. September 2003.

Abstract: Given the positions of n sites in a radio network we consider the problem of finding routes between any pair of sites that minimize energy consumption and do not use more than some constant number k of hops. Known exact algorithms for this problem required Omega(n log n) per query pair (p,q). In this paper we relax the exactness requirement and only compute approximate (1+epsilon) solutions which allows us to guarantee constant query time using linear space and O(nlog n) preprocessing time. The dependence on epsilon is polynomial in 1/epsilon.

One tool we employ might be of independent interest: For any pair of points (p,q)\in P\subseteqZ² we can report in constant time the cluster pair (A,B) representing (p,q) in a well-separated pair decomposition of P.

Postscript file: ALCOMFT-TR-03-28.ps.gz (281 kb).