Network lifetime maximization for time-sensitive data gathering in wireless sensor networks

Energy-constrained sensor networks have been widely deployed for environmental monitoring and security surveillance purposes. Since sensors are usually powered by energy-limited batteries, in order to prolong the network lifetime, most existing research focuses on constructing a load-balanced routing tree rooted at the base station for data gathering. However, this may result in a long routing path from some sensors to the base station. Motivated by the need of some mission-critical applications that require all sensed data to be received by the base station with minimal delay, this paper aims to construct a routing tree such that the network lifetime is maximized while keeping the routing path from each sensor to the base station minimized. This paper shows that finding such a tree is NP-hard. Thus a novel heuristic called top-down algorithm is presented, which constructs the routing tree layer by layer such that each layer is optimally extended, using a network flow model. A distributed refinement algorithm is then devised that dramatically improves on the load balance for the routing tree produced by the top-down algorithm. Finally, extensive simulations are conducted. The experimental results show that the top-down algorithm with balance-refinement delivers a shortest routing tree whose network lifetime achieves around 85% of the optimum. © 2012 Elsevier B.V. All rights reserved.