Maximizing Lifetime of Data-Gathering Sensor Trees in Wireless Sensor Networks

Hiroshi MATSUURA  

IEICE TRANSACTIONS on Communications   Vol.E102-B   No.12   pp.2205-2217
Publication Date: 2019/12/01
Publicized: 2019/06/10
Online ISSN: 1745-1345
DOI: 10.1587/transcom.2018EBP3334
Type of Manuscript: PAPER
Category: Network
data gathering tree,  data aggregation,  network lifetime,  wireless sensor networks,  

Full Text: PDF>>
Buy this Article

Sensor-data gathering using multi-hop connections in a wireless sensor network is being widely used, and a tree topology for data gathering is considered promising because it eases data aggregation. Therefore, many sensor-tree-creation algorithms have been proposed. The sensors in a tree, however, generally run on batteries, so long tree lifetime is one of the most important factors in collecting sensor data from a tree over a long period. It has been proven that creating the longest-lifetime tree is a non-deterministic-polynomial complete problem; thus, all previously proposed sensor-tree-creation algorithms are heuristic. To evaluate a heuristic algorithm, the time complexity of the algorithm is very important, as well as the quantitative evaluation of the lifetimes of the created trees and algorithm speed. This paper proposes an algorithm called assured switching with accurate graph optimization (ASAGAO) that can create a sensor tree with a much longer lifetime much faster than other sensor-tree-creation algorithms. In addition, it has much smaller time complexity.