Please use this identifier to cite or link to this item:
Title: Construction of optimal data aggregation trees for wireless sensor networks
Authors: Li, D
Cao, J 
Liu, M
Zheng, Y
Keywords: Wireless sensor networks
Data collection and aggregation
Issue Date: 2006
Publisher: IEEE
Source: 15th International Conference on Computer Communications and Networks : Arlington, Virginia USA, 9-11 October 2006 : proceedings, p. 475-480 How to cite?
Abstract: This paper considers the problem of constructing data gathering trees in a wireless sensor network for a group of sensor nodes to send collected information to a single sink node. Sensors form application-directed groups and the sink node communicates with the group members, called source nodes, to gather the desired data using a multicast tree rooted at the sink node [7]. The data gathering tree contains the sink node, all the source nodes, and some other non-source nodes. Our goal of constructing such a data gathering tree is to minimize the number of non-source nodes to be included in the tree so as to save energies of as many non-source nodes as possible. It can be shown that the optimization problem is NP-hard. We first propose an approximation algorithm with a performance ratio of four, and then give a distributed algorithm corresponding to the approximation algorithm. Extensive simulations are performed to study the performance of the proposed algorithm. The results show that the proposed algorithm can find a tree of a good approximation to the optimal tree and has a high degree of scalability.
ISBN: 1424405726
Rights: © 2006 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Appears in Collections:Conference Paper

Files in This Item:
File Description SizeFormat 
optimal-data_06.pdf7.12 MBAdobe PDFView/Open
View full-text via PolyU eLinks SFX Query
Show full item record
PIRA download icon_1.1View/Download Contents


Last Week
Last month
Citations as of Jul 31, 2018


Last Week
Last month
Citations as of Aug 19, 2018

Page view(s)

Last Week
Last month
Citations as of Aug 14, 2018


Citations as of Aug 14, 2018

Google ScholarTM


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