Construction of optimal data aggregation trees for wireless sensor networks

Deying Li, Jiannong Cao, Ming Liu, Yuan Zheng

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

18 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationProceedings - 15th International Conference on Computer Communications and Networks 2006, ICCCN 2006
Pages475-480
Number of pages6
DOIs
Publication statusPublished - 1 Dec 2006
Event15th International Conference on Computer Communications and Networks 2006, ICCCN 2006 - Arlington, VA, United States
Duration: 9 Oct 200611 Oct 2006

Conference

Conference15th International Conference on Computer Communications and Networks 2006, ICCCN 2006
CountryUnited States
CityArlington, VA
Period9/10/0611/10/06

Keywords

  • Data collection and aggregation
  • Wireless sensor networks

ASJC Scopus subject areas

  • Computer Science(all)

Cite this