Approximating Energy Efficient Paths in Wireless Multi-hop Networks

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 require approximate $(1+\epsilon)$ solutions which allows us to derive schemes which 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 used might be of independent interest: For any pair of points $(p,q)\in P\subseteq\mathbb{Z}^2$ report in constant time the cluster pair $(A,B)$ representing $(p,q)$ in a well-separated pair decomposition of $P$