TCS / Research / Publications / Distributed algorithms for lifetime maximization in sensor networks via min-max spanning subgraphs
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

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, 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},
}

See dx.doi.org ...

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.