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.
Hiroshi MATSUURA
NTT Corporation
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Hiroshi MATSUURA, "Maximizing Lifetime of Data-Gathering Sensor Trees in Wireless Sensor Networks" in IEICE TRANSACTIONS on Communications,
vol. E102-B, no. 12, pp. 2205-2217, December 2019, doi: 10.1587/transcom.2018EBP3334.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.2018EBP3334/_p
Copy
@ARTICLE{e102-b_12_2205,
author={Hiroshi MATSUURA, },
journal={IEICE TRANSACTIONS on Communications},
title={Maximizing Lifetime of Data-Gathering Sensor Trees in Wireless Sensor Networks},
year={2019},
volume={E102-B},
number={12},
pages={2205-2217},
abstract={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.},
keywords={},
doi={10.1587/transcom.2018EBP3334},
ISSN={1745-1345},
month={December},}
Copy
TY - JOUR
TI - Maximizing Lifetime of Data-Gathering Sensor Trees in Wireless Sensor Networks
T2 - IEICE TRANSACTIONS on Communications
SP - 2205
EP - 2217
AU - Hiroshi MATSUURA
PY - 2019
DO - 10.1587/transcom.2018EBP3334
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E102-B
IS - 12
JA - IEICE TRANSACTIONS on Communications
Y1 - December 2019
AB - 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.
ER -