Approximating Energy Efficient Paths in Wireless Multi-Hop Networks

Stefan Funke, Domagoj Matijevic, Peter Sanders

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(n\log 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\subseteq\mathbb{Z}^2$ we can report in constant time the cluster pair $(A,B)$ representing $(p,q)$ in a well-separated pair decomposition of $P$.

Proc. 11th Annual European Symposium on Algorithms (ESA) 2003, Budapest (Springer LNCS)