Energy Optimal Routing in Radio Networks Using Geometric Data Structures

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 G = (V; V \Theta V ) in time O , it is less clear how to do it in sub-quadratic or even 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 possibly a constant offset. We give an O(n log n) time algorithm for the case where offsets can be neglected. This algorithms also works for super-quadratic cost functions and limited transmission ranges