On the construction of data aggregation tree with minimum energy cost in wireless sensor networks: NP-completeness and approximation algorithms

Tung Wei Kuo, Ching-Ju Lin, Ming Jer Tsai

Research output: Contribution to journalArticlepeer-review

43 Scopus citations

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 and consider the cases where the link quality is not perfect. We show that these problems are NP-complete and propose O(1) -approximation algorithms for each of them. Simulations show that the proposed algorithms have good performance in terms of energy cost.

Original languageEnglish
Article number7366759
Pages (from-to)3109-3121
Number of pages13
JournalIEEE Transactions on Computers
Volume65
Issue number10
DOIs
StatePublished - 1 Oct 2016

Keywords

  • Approximation algorithms
  • approximation methods
  • relays
  • routing
  • wireless sensor networks

Fingerprint Dive into the research topics of 'On the construction of data aggregation tree with minimum energy cost in wireless sensor networks: NP-completeness and approximation algorithms'. Together they form a unique fingerprint.

Cite this