Distributed computation of maximum lifetime spanning subgraphs in sensor networks

Reference:

Harri Haanpää, André Schumacher, Thorn Thaler, and Pekka Orponen. Distributed computation of maximum lifetime spanning subgraphs in sensor networks. In H. Zhang, S. Olariu, J. Cao, and D. B. Johnson, editors, Proceedings of the 3rd International Conference on Mobile Ad-Hoc and Sensor Networks (MSN'07, Beijing, China, December 2007), volume 4864 of Lecture Notes in Computer Science, pages 445–456, Berlin Heidelberg, 2007. Springer-Verlag.

Abstract:

We present a simple and efficient distributed method for determining the transmission power assignment that maximises the lifetime of a data-gathering wireless sensor network with stationary nodes and static power assignments. Our algorithm determines the transmission power level inducing the maximum-lifetime spanning subgraph of a network by means of a distributed breadth-first search for minmax-power communication paths starting from a given reference node. The performance of the resulting Maximum Lifetime Spanner (MLS) protocol is validated in a number of simulated networking scenarios. In particular, we study the performance of the protocol in terms of the number of required control messages, and compare it to the performance of a recently proposed Distributed Min-Max Tree (DMMT) algorithm. For all network scenarios we consider, MLS outperforms DMMT significantly. We also discuss bringing down the message complexity of our algorithm by initialising it with the Relative Neighbourhood Graph (RNG) of a transmission graph rather than the full graph, and present an efficient distributed method for reducing a given transmission graph to its RNG.

Keywords:

sensor networks, wireless networks, lifetime maximisation, energy-aware computation, distributed computation, relative neighbourhood graphs

Suggested BibTeX entry:

@inproceedings{HSTO07,
    address = {Berlin Heidelberg},
    author = {Harri Haanp\"a\"a and Andr\'e Schumacher and Thorn Thaler and Pekka Orponen},
    booktitle = {Proceedings of the 3rd International Conference on Mobile Ad-Hoc and Sensor Networks (MSN'07, Beijing, China, December 2007)},
    editor = {H. Zhang and S. Olariu and J. Cao and D. B. Johnson},
    pages = {445--456},
    publisher = {Springer-Verlag},
    series = {Lecture Notes in Computer Science},
    title = {Distributed computation of maximum lifetime spanning subgraphs in sensor networks},
    volume = {4864},
    year = {2007},
}