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$.
PDF