TY - JOUR
T1 - Correlated data gathering with double trees in wireless sensor networks
AU - Weng, Hsien Cheng
AU - Chen, Yu Hsun
AU - Wu, Eric Hsiao Kuang
AU - Chen, Gen Huey
N1 - Funding Information:
Manuscript received September 06, 2010; revised June 29, 2011; accepted July 02, 2011. Date of publication July 14, 2011; date of current version April 11, 2012. This work was supported in part by the National Science Council Taiwan under project NSC 99-2219-E-002-021 and project NSC 99-2631-S-008-004 and in part by the Taiwan Education Ministry under the project No. 995903. A preliminary version of this paper was presented in the Proceedings of IEEE Globecom 2007. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Elliot Brown.
PY - 2012
Y1 - 2012
N2 - The problem of correlated data gathering in wireless sensor networks is studied in this paper. For the sake of efficiency, tree transmission structures are often used for data gathering. Previously, the problem of minimizing the total communication cost with a single-tree transmission structure was shown to be NP-hard. However, when the explicit communication approach is used, the total communication cost can be further reduced, provided a double-tree transmission structure is used and inverse links are allowed. This motivates us to devise a double-tree routing scheme in which two trees are used for data transmission, one carrying raw data and the other carrying encoded data. We show that with the double-tree routing scheme, the problem of minimizing the total communication cost remains NP-hard. A distributed algorithm for solving it is suggested. We show that under the simple correlation model, the algorithm has an approximation ratio of two. Extensive simulations are conducted to verify the effectiveness of the double-tree routing scheme.
AB - The problem of correlated data gathering in wireless sensor networks is studied in this paper. For the sake of efficiency, tree transmission structures are often used for data gathering. Previously, the problem of minimizing the total communication cost with a single-tree transmission structure was shown to be NP-hard. However, when the explicit communication approach is used, the total communication cost can be further reduced, provided a double-tree transmission structure is used and inverse links are allowed. This motivates us to devise a double-tree routing scheme in which two trees are used for data transmission, one carrying raw data and the other carrying encoded data. We show that with the double-tree routing scheme, the problem of minimizing the total communication cost remains NP-hard. A distributed algorithm for solving it is suggested. We show that under the simple correlation model, the algorithm has an approximation ratio of two. Extensive simulations are conducted to verify the effectiveness of the double-tree routing scheme.
KW - Approximation algorithm
KW - NP-hardness
KW - correlated data networkgathering
KW - double-tree routing scheme
KW - wireless sensor
UR - http://www.scopus.com/inward/record.url?scp=84859995273&partnerID=8YFLogxK
U2 - 10.1109/JSEN.2011.2162092
DO - 10.1109/JSEN.2011.2162092
M3 - 期刊論文
AN - SCOPUS:84859995273
SN - 1530-437X
VL - 12
SP - 1147
EP - 1156
JO - IEEE Sensors Journal
JF - IEEE Sensors Journal
IS - 5
M1 - 5954130
ER -