Reference:
Harri Haanpää, André Schumacher, and Pekka Orponen. Distributed algorithms for lifetime maximization in sensor networks via min-max spanning subgraphs. Wireless Networks, to appear. Published online 8 April 2009.
Abstract:
We consider the problem of static transmission-power assignment for lifetime maximization of a wireless sensor network with stationary nodes operating in a data-gathering scenario. Using a graph-theoretic approach, we propose two distributed algorithms, MLS and BSpan, that construct spanning trees with minimum maximum (minmax) edge cost. MLS is based on computation of minmax-cost paths from a reference node, while BSpan performs a binary search over the range of power levels and exploits the wireless broadcast advantage. We also present a simple distributed method for pruning a graph to its Relative Neighborhood Graph, which reduces the worst-case message complexity of MLS under natural assumptions on the path-loss. In our network simulations both MLS and BSpan significantly outperform the recently proposed Distributed Min-Max Tree algorithm in terms of number of messages required.
Keywords:
lifetime maximization, minimum spanning tree, Min-Max spanning tree relative neighborhood graph, distributed algorithm
Suggested BibTeX entry:
@article{HaSO09,
author = {Harri Haanp\"a\"a and Andr\'e Schumacher and Pekka Orponen},
journal = {Wireless Networks},
note = {Published online 8 April 2009},
title = {Distributed algorithms for lifetime maximization in sensor networks via min-max spanning subgraphs},
year = {to appear},
}
|