請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/30069
標題: | 無線感測器網路中關聯性資料收集之雙路由樹近似演算法 A 2-Approximation Double-Tree Algorithm for Correlated Data Gathering in Wireless Sensor Networks |
作者: | Hsien-Cheng Weng 翁憲政 |
指導教授: | 陳健輝(Gen-Huey Chen),吳曉光(Hsiao-Kuang Wu) |
關鍵字: | 無線感測器網路,關聯性資料收集,傳輸結構,雙路由樹,最短路徑樹,最小生成樹,近似演算法, Wireless Sensor Network,Data Gathering,Correlated Data,Double-Tree Routing,Transmission Structure,NP-Complete,Approximation, |
出版年 : | 2007 |
學位: | 碩士 |
摘要: | 在這篇論文中,針對無線感測器網路中關聯性資料收集的問題,我們設計了一個雙路由樹的傳輸結構。在無線感測器網路中,省電是一個非常重要的議題,而雙路由樹正能有效率地利用感測器的能源來達到省電的目的。在傳統的網路路由問題中,單路由樹被視為是有效率且容易建置的一種網路結構,因此被應用在相當多的領域中。但我們證明了在關聯性資料收集的問題中,單路由樹有可能會造成浪費能源的現象。我們把這些現象歸類成路徑多餘問題和逆連結問題。如果能避免這兩種現象,就可以達到更有效率利用能源的目的。根據對這兩種現象的觀察,我們提出了雙路由樹的傳輸結構。把網路中的原始資料跟壓縮過後的資料分別在兩個不同的路由樹傳輸,並採用逆連結的概念,以達到更低的能源消耗量。對每一個網路拓樸而言,因為雙路由樹的解集合會比單路由樹的解集合來得大,所以相對於單路由樹來說,雙路由樹保證可以找到一個較佳解。我們首先定義何為「使用路由樹結構,以期在關聯性資料收集的問題中,達到最低的能源消耗量」的問題。接著證明這樣的問題是一個NP完備 (NP-Complete) 的問題。因為無法在線性時間內找到這個問題的最佳解,所以我們提出了一個雙路由樹近似演算法,保證在任何的網路拓樸中,能源消耗最多不會超過最佳解的 2 倍。在實驗中可以看到,雙路由樹近似演算法的確會比最短路徑樹更能節省感測器能源的消耗。 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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/30069 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-96-1.pdf 目前未授權公開取用 | 649.2 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。