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

作者：Shan, Feng^*; Liang, Weifa; Luo, Jun; Shen, Xiaojun

来源：Computer Networks, 2013, 57(5): 1063-1077.

DOI：10.1016/j.comnet.2012.12.005

• Wireless sensor networks
• Network lifetime prolongation
• Energy optimization
• Load-balanced spanning tree
• Network flow
• Algorithm design

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.

• 出版日期2013-4-7
• 单位中国人民解放军国防科学技术大学; 东南大学