Distributed algorithms for lifetime maximization in sensor networks via Min–Max spanning subgraphs |
| |
Authors: | Harri Haanpää André Schumacher Pekka Orponen |
| |
Institution: | (1) Department of Information and Computer Science, Helsinki University of Technology TKK, Helsinki, Finland |
| |
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: | |
本文献已被 SpringerLink 等数据库收录! |
|