On the Construction of Data Aggregation Tree with Minimum Energy Cost in Wireless Sensor Networks: NP-Completeness and Approximation Algorithms

DOI10.1109/TC.2015.2512862zbMATH Open1360.94501arXiv1402.6457OpenAlexW2343543015MaRDI QIDQ2985262FDOQ2985262

Authors: Tung-Wei Kuo, Kate Ching-Ju Lin, Ming-Jer Tsai 

Publication date: 16 May 2017

Published in: IEEE Transactions on Computers (Search for Journal in Brave)

Abstract: In many applications, it is a basic operation for the sink to periodically collect reports from all sensors. Since the data gathering process usually proceeds for many rounds, it is important to collect these data efficiently, that is, to reduce the energy cost of data transmission. Under such applications, a tree is usually adopted as the routing structure to save the computation costs for maintaining the routing tables of sensors. In this paper, we work on the problem of constructing a data aggregation tree that minimizes the total energy cost of data transmission in a wireless sensor network. In addition, we also address such a problem in the wireless sensor network where relay nodes exist. We show these two problems are NP-complete, and propose O(1)-approximation algorithms for each of them. Simulations show that the proposed algorithms each have good performance in terms of the energy cost.

Full work available at URL: https://arxiv.org/abs/1402.6457

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Applications of graph theory to circuits and networks (94C15)

This page was built for publication: On the Construction of Data Aggregation Tree with Minimum Energy Cost in Wireless Sensor Networks: NP-Completeness and Approximation Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2985262)