Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/17434
Title: Approximation algorithm for constructing data aggregation trees for wireless sensor networks
Authors: Li, D
Cao, J 
Zhu, Q
Keywords: Approximation algorithm
Data aggregationtree
Distributed algorithm
WSNs
Issue Date: 2009
Publisher: Higher Education Press
Source: Frontiers of computer science in China, 2009, v. 3, no. 4, p. 524-534 How to cite?
Journal: Frontiers of computer science in China 
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.
URI: http://hdl.handle.net/10397/17434
ISSN: 1673-7350
EISSN: 1673-7466
DOI: 10.1007/s11704-009-0039-x
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

2
Last Week
0
Last month
0
Citations as of Aug 18, 2017

WEB OF SCIENCETM
Citations

2
Last Week
0
Last month
0
Citations as of Aug 15, 2017

Page view(s)

42
Last Week
0
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.