Approximation algorithm for constructing data aggregation trees for wireless sensor networks |
| |
Authors: | Deying Li Jiannong Cao and Qinghua Zhu |
| |
Affiliation: | (1) University of Madrid, Spain;(2) ATHENA / I.S.I. Research and Innovation Center in Information, Communication, and Knowledge Technologies, Greece;(3) M?todos y Tecnolog?a de Sistemas y Procesos (MTP), Madrid, Spain |
| |
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. |
| |
Keywords: | |
本文献已被 万方数据 SpringerLink 等数据库收录! |
|