期刊
IEEE SENSORS JOURNAL
卷 12, 期 5, 页码 1147-1156出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/JSEN.2011.2162092
关键词
Approximation algorithm; correlated data gathering; double-tree routing scheme; NP-hardness; wireless sensor network
资金
- National Science Council Taiwan [NSC 99-2219-E-002-021, NSC 99-2631-S-008-004]
- Taiwan Education Ministry [995903]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据