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

Y2 - 26 November 2007 through 30 November 2007

ER -