A 2-Approximation Double-Tree Algorithm for Correlated Data Gathering in Wireless Sensor Networks
Date Issued
2007
Date
2007
Author(s)
Weng, Hsien-Cheng
DOI
zh-TW
Abstract
In this thesis, we design a novel transmission structure, called a double-tree for correlated data gathering problem in wireless sensor networks, where the goal is to minimize the total transmission cost of information collected by all sensor nodes. 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. We found that applying a tree structure is not energy efficient for explicit communication approach in some network topologies. Further, these energy inefficient conditions are defined as path redundancy problem and inverse link problem. Therefore according to our observation, 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 outperforms the traditional tree structure in correlated data gathering problem. We first formulate the optimization problem with a double-tree transmission structure, and prove NP-Complete under a simple correlation model. Then we present a 2-approximation algorithm called MST+SPT that guarantees the upper bound of total transmission cost compared to the optimal solution.
Subjects
無線感測器網路
關聯性資料收集
傳輸結構
雙路由樹
最短路徑樹
最小生成樹
近似演算法
Wireless Sensor Network
Data Gathering
Correlated Data
Double-Tree Routing
Transmission Structure
NP-Complete
Approximation
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-96-R94922026-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):a1f162ef618f222a33109a10295dae62