Energy-Efficient Randomized Switching for Maximizing Lifetime in Tree-Based Wireless Sensor Networks


In most wireless sensor network (WSN) applications, data are typically gathered by sensor nodes and reported to a data collection point called sink. To support such a data collection pattern, a tree structure rooted at the sink is defined. Depending on various factors, including the WSN topology and the availability of resources, the energy consumption of nodes in different paths of the data collection tree may vary largely, thus affecting the overall network lifetime. This paper addresses the problem of lifetime maximization of WSNs based on data collection trees. Specifically, we propose a novel and efficient algorithm, called Randomized Switching for Maximizing Lifetime (RaSMaLai), that aims at extending the lifetime of WSNs through load balancing. Given an initial data collection tree, RaSMaLai randomly switches some sensor nodes from their original paths to other paths with lower load. We prove that, under appropriate settings of the operating parameters, RaSMaLai converges with a low time complexity. We further design a distributed version of our algorithm. Through an extensive performance evaluation study that includes simulation of large-scale scenarios and real experiments on a WSN testbed, we show that the proposed RaSMaLai algorithm and its distributed version achieve a longer network lifetime than the state-of-the-art solutions.


Computer Science


This work was supported by the US National Science Foundation (NSF) under Grants CNS-1355505, IIS-1404673, CNS-1404677, and IIP-1242521. Any opinions, findings, and conclusions or recommendations expressed in this work are those of the authors and do not necessarily reflect those of the NSF. The authors are grateful to the anonymous reviewers for their insightful comments and constructive suggestions that allowed them to significantly improve the quality of the manuscript.

Keywords and Phrases

Algorithms; Complex networks; Data acquisition; Energy efficiency; Energy utilization; Network management; Resource allocation; Sensor nodes; Trees (mathematics); Data collection patterns; Data collection trees; Energy efficient; Evaluation study; Lifetime maximization; Network lifetime; Operating parameters; Randomized Algorithms; Wireless sensor networks; Load balancing

International Standard Serial Number (ISSN)

1063-6692; 1558-2566

Document Type

Article - Journal

Document Version


File Type





© 2015 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 Oct 2015