A 2-approximation double-tree algorithm for correlated data gathering in wireless sensor networks

Hsien Cheng Weng, Hope Chan, Eric Hsiao Kuang Wu, Gen Huey Chen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Scopus citations


In this paper, we design a novel transmission structure called a double-tree for correlated data gathering problem for wireless sensor networks, where the goal is to minimize the total transmission cost of information collected by all sensor nodes, to the sink node. It is well-known that a tree structure is often adopted for network routing problems. However, the traditional tree transmission structure for network routing may not be an optimal structure while data correlation factors are being considered. For a given wireless sensor network, some nodes send their raw data directly to the sink, and some nodes send their encoded data based on information received from other nodes; therefore, there are two types of data in the network. Without the help of decoding/re-coding at the intermediate node, the purpose of encoded data routing is to directly send to the sink, but the purpose of raw data routing is not only to send to the sink, but also to spread raw data to other nodes as side information in encoding operations. The difference from one data type makes traditional tree structure unsuitable for the correlated data gathering problem. Therefore according to our observations, we propose a new transmission double-tree structure, which uses one tree for raw data routing, and uses another tree for encoded data routing. By employing the double-tree structure, the network can achieve lower transmission cost of gathering sensing data. Furthermore the adoption of double-tree structure always outperforms the traditional tree structure in correlated data gathering problem. We first formulate the optimization problem with a double-tree transmission structure in the general case, and prove NP-Hardness of simplified version of this problem. Then we present a 2-approximation algorithm MST+ SPT that guarantees the upper bound of total transmission cost compared to the optimal solution.

Original languageEnglish
Title of host publicationIEEE GLOBECOM 2007 - 2007 IEEE Global Telecommunications Conference, Proceedings
Number of pages5
StatePublished - 2007
Event50th Annual IEEE Global Telecommunications Conference, GLOBECOM 2007 - Washington, DC, United States
Duration: 26 Nov 200730 Nov 2007

Publication series

NameGLOBECOM - IEEE Global Telecommunications Conference


Conference50th Annual IEEE Global Telecommunications Conference, GLOBECOM 2007
Country/TerritoryUnited States
CityWashington, DC


Dive into the research topics of 'A 2-approximation double-tree algorithm for correlated data gathering in wireless sensor networks'. Together they form a unique fingerprint.

Cite this