Constant Time Queries for Energy Efficient Paths in Multi-Hop Wireless Networks
Stefan Funke, Domagoj Matijevic, Peter Sanders
We investigate algorithms for computing
energy efficient paths in ad-hoc radio networks.
We demonstrate how advanced data structures from computational
geometry can be employed to preprocess the position of
radio stations in such a way that approximately
energy optimal paths can be retrieved in constant time, i.e.,
independent of the network size.
We put particular emphasis on actual implementations which
demonstrate that large constant factors hidden in the theoretical
analysis are not a big problem in practice.
PDF