無線感測器網路中關聯性資料收集之雙路由樹近似演算法

在這篇論文中，針對無線感測器網路中關聯性資料收集的問題，我們設計了一個雙路由樹的傳輸結構。在無線感測器網路中，省電是一個非常重要的議題，而雙路由樹正能有效率地利用感測器的能源來達到省電的目的。在傳統的網路路由問題中，單路由樹被視為是有效率且容易建置的一種網路結構，因此被應用在相當多的領域中。但我們證明了在關聯性資料收集的問題中，單路由樹有可能會造成浪費能源的現象。我們把這些現象歸類成路徑多餘問題和逆連結問題。如果能避免這兩種現象，就可以達到更有效率利用能源的目的。根據對這兩種現象的觀察，我們提出了雙路由樹的傳輸結構。把網路中的原始資料跟壓縮過後的資料分別在兩個不同的路由樹傳輸，並採用逆連結的概念，以達到更低的能源消耗量。對每一個網路拓樸而言，因為雙路由樹的解集合會比單路由樹的解集合來得大，所以相對於單路由樹來說，雙路由樹保證可以找到一個較佳解。我們首先定義何為「使用路由樹結構，以期在關聯性資料收集的問題中，達到最低的能源消耗量」的問題。接著證明這樣的問題是一個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.

並列關鍵字

Wireless Sensor Network ； Data Gathering ； Correlated Data ； Double-Tree Routing ； Transmission Structure ； NP-Complete ； Approximation

參考文獻

[1] Z. Yujie, V. Ramanuja, P. Seung-Jong, and S. Raghupathy, A scalable correlation aware aggregation strategy for wireless sensor networks," in First International Conference on Wireless Internet, 2005.

[2] R. Cristescu, B. Beferull-Lozano, M. Vetterli, and R. Wattenhofer, Network correlated data gathering with explicit communication: Np-completeness and algorithms," Networking, IEEE/ACM Transactions on, vol. 14, no. 1, pp. 41{54, 2006.

[5] G. J. Pottie and W. J. Kaiser, Wireless integrated network sensors," Commun. ACM, vol. 43, no. 5, pp. 51{58, 2000.

[6] A. Jindal and K. Psounis, Modeling spatially-correlated sensor network data," in Sensor and Ad Hoc Communications and Networks, 2004, pp. 162{171.

[7] J. Acimovic, B. Beferull-Lozano, and R. Cristescu, Adaptive distributed algorithms for power-e±cient data gathering in sensor networks," in Wireless Networks, Communications and Mobile Computing, 2005 International Conference on, vol. 2, 2005, pp. 946{951 vol.2.

國際替代計量

無線感測器網路中關聯性資料收集之雙路由樹近似演算法

全文下載

主題瀏覽