Approximation algorithm for constructing data aggregation trees for wireless sensor networks

Deying Li, Jiannong Cao, Qinghua Zhu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)

Abstract

This paper considers the problem of constructing data aggregation trees in wireless sensor networks (WSNs) for a group of sensor nodes to send collected information to a single sink node. The data aggregation tree contains the sink node, all the source nodes, and some other non-source nodes. Our goal of constructing such a data aggregation tree is to minimize the number of non-source nodes to be included in the tree so as to save energies. We prove that the data aggregation tree problem is NP-hard and then propose an approximation algorithm with a performance ratio of four and a greedy algorithm. We also give a distributed version of the approximation algorithm. Extensive simulations are performed to study the performance of the proposed algorithms. The results show that the proposed algorithms can find a tree of a good approximation to the optimal tree and has a high degree of scalability.
Original languageEnglish
Pages (from-to)524-534
Number of pages11
JournalFrontiers of Computer Science in China
Volume3
Issue number4
DOIs
Publication statusPublished - 1 Dec 2009

Keywords

  • Approximation algorithm
  • Data aggregationtree
  • Distributed algorithm
  • WSNs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this