Distributed algorithms for lifetime maximization in sensor networks via min-max spanning subgraphs

Reference:

Harri Haanpää, André Schumacher, and Pekka Orponen. Distributed algorithms for lifetime maximization in sensor networks via min-max spanning subgraphs. Wireless Networks, 16(3):875–887, 2010.

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{HaSO10,
    author = {Harri Haanpää and André Schumacher and Pekka Orponen},
    journal = {Wireless Networks},
    number = {3},
    pages = {875--887},
    title = {Distributed algorithms for lifetime maximization in sensor networks via min-max spanning subgraphs},
    volume = {16},
    year = {2010},
}