Correlated data gathering with double trees in wireless sensor networks

Hsien Cheng Weng, Yu Hsun Chen, Eric Hsiao Kuang Wu, Gen Huey Chen

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

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.

Original languageEnglish
Article number5954130
Pages (from-to)1147-1156
Number of pages10
JournalIEEE Sensors Journal
Volume12
Issue number5
DOIs
StatePublished - 2012

Keywords

  • Approximation algorithm
  • correlated data networkgathering
  • double-tree routing scheme
  • NP-hardness
  • wireless sensor

Fingerprint

Dive into the research topics of 'Correlated data gathering with double trees in wireless sensor networks'. Together they form a unique fingerprint.

Cite this