Naslov
Energy-Efficient Paths in Radio Networks

Autori
Beier, Rene ; Funke, Stefan ; Matijević, Domagoj ; Sanders, Peter

Izvornik
Algorithmica (0178-4617) 61 (2011), 2; 298-319

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
computational geometry - communication networks

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA