Distributed Algorithms for Lifetime Maximization in Sensor Networks via Min-Max Spanning Subgraphs

The authors 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, they 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. They 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.