TY - GEN
T1 - A 2-approximation double-tree algorithm for correlated data gathering in wireless sensor networks
AU - Weng, Hsien Cheng
AU - Chan, Hope
AU - Wu, Eric Hsiao Kuang
AU - Chen, Gen Huey
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=39349116074&partnerID=8YFLogxK
U2 - 10.1109/GLOCOM.2007.173
DO - 10.1109/GLOCOM.2007.173
M3 - 會議論文篇章
AN - SCOPUS:39349116074
SN - 1424410436
SN - 9781424410439
T3 - GLOBECOM - IEEE Global Telecommunications Conference
SP - 898
EP - 902
BT - IEEE GLOBECOM 2007 - 2007 IEEE Global Telecommunications Conference, Proceedings
T2 - 50th Annual IEEE Global Telecommunications Conference, GLOBECOM 2007
Y2 - 26 November 2007 through 30 November 2007
ER -