engleski

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 ω(p, q) = |pq|^δ +C_p, for some constant δ > 1 and nonnegative off set 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 δ = 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+α}; ; ; ), where α > 0 can be chosen arbitrarily. If we relax the exactness requirement, we can find an approximate (1+ϵ) 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 ϵ is polynomial in 1/ϵ. One tool we employ might be of independent interest: For any pair of points (p, q) in (PxP) 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

nije evidentirano