Paper Info
Title
A 2-Approximation Double-Tree Algorithm for Correlated Data Gathering in Wireless Sensor Networks
Abstract
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.
Year
DOI
Venue
2007
10.1109/GLOCOM.2007.173
GLOBECOM
Keywords
Field
DocType
2-approximation double-tree algorithm,optimisation,encoded data routing,trees (mathematics),approximation theory,wireless sensor network,encoding,correlated data gathering problem,optimization problem,transmission structure,wireless sensor networks,telecommunication network routing,correlation methods,network routing,data type,tree structure,upper bound
Data collection,Computer science,Computer network,Raw data,Destination-Sequenced Distance Vector routing,Algorithm,Data type,Tree structure,Wireless sensor network,Optimization problem,Distributed computing,Whippletree
Conference
ISSN
ISBN
Citations 
1930-529X
978-1-4244-1043-9
1
PageRank 
References 
Authors
0.36
7
4
Name
Order
Citations
PageRank
Hsien-cheng Weng110.36
Hope Chan2211.41
Wu, E.H.-K.333939.53
Gen-Huey Chen497989.32