ALCOMFT-TR-02-32

René Beier, Peter Sanders and Naveen Sivadasan
Energy Optimal Routing in Radio Networks Using Geometric Data Structures
MPI. Work package 2. May 2002.

Abstract: Given the current position of n sites in a radio network, we discuss the problem of finding routes between pairs of sites such that the energy consumption for this communication is minimized. Though this can be done using Dijkstra's algorithm on the complete graph in quadratic tim, it is less clear how to do it in near linear time. We present such algorithms for the important case where the transmission cost between two sites is the square of their Euclidean distance plus a constant offset. We give an \Ohknlog n time algorithm that finds an optimal path with at most k hops, and an \Ohn^1+epsilon time algorithm for the case of an unrestricted number of hops. The algorithms are based on geometric data structures ranging from simple 2-dimensional Delaunay triangulations to more sophisticated proximity data structures that exploit the special structure of the problem.

Postscript file: ALCOMFT-TR-02-32.ps.gz (90 kb).