Energy-Efficient Paths in Radio Networks
We consider a radio network consisting of n stations represented as the complete graph on a set of n points in the Euclidean plane with edge weights omega(p,q)=|pq| (delta) +C (p) , for some constant delta > 1 and nonnegative offset costs C (p) . Our goal is to find paths of minimal energy cost between any pair of points that do not use more than some given number k of hops. We present an exact algorithm for the important case when delta=2, which requires O(kn log n) time per query pair (p, q). For the case of an unrestricted number of hops we describe a family of algorithms with query time O(n(1+alpha)), where alpha > 0 can be chosen arbitrarily. If we relax the exactness requirement, we can find an approximate (1 + epsilon) solution in constant time by querying a data structure which has linear size and which can be build in O(n log n) 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) epsilon (P x P) we can report in constant time the cluster pair (A, B) representing (p, q) in a well-separated pair decomposition of P.
computational geometry communication networks