無線感測網路下之遠距偵測覆蓋空洞演算法

Remote Hole Detection Algorithms for Wireless Sensor Networks

劉喬筠(Chiao-Yun Liu)

指導教授 ： 賴國華

元智大學/資訊學院/資訊工程學系/碩士(2008年)

摘要

在這篇論文裡，我們提出了一個能夠有效率地探測出在無線感測網路上的覆蓋空洞的分散式演算法。在假設每個散佈的感測節點位置都能知道的情況下，我們將整個方法分成兩個階段。第一個階段，我們的目的是檢測出每個包圍在覆蓋空洞旁的節點。我們利用我們提出來的概念-單獨覆蓋弧線(mono-covered arc)，此弧線代表了每個節點的感測圓弧中，沒有被其它節點所重覆覆蓋的部分。在我們的方法中，這些有方向性的單獨覆蓋弧線的右側，就是覆蓋空洞及未完全覆蓋區域。在這樣的觀念之下，我們發展出一個以圖論為基礎的分散式演算法，這個演算法可以在感測節點端有效地分辨出每個覆蓋空洞的位置及型態。甚者，這些圖的資訊可被送到基地台做整合，以辨認出所有存在於網路中的覆蓋空洞的幾何特徵

關鍵字

覆蓋空洞 ； 無線感應網路 ； 分散式演算法

並列摘要

In this thesis, we develop a practical and energy-efficient distributed algorithm for the detection of coverage holes in a wireless sensor network. It assumes the location of sensor nodes is available. We do this in two phases. First we want to identify a set of nodes of which encircle a coverage hole. This is done by introducing a concept of mono-covered arc, which represents the circumference of a non-overlapping region of the sensing disc of a sensor node. That is, a coverage hole or insufficient coverage region will be along the right-hand side of these directed mono-covered arcs. Based on this notion, a graph-theoretic distributed algorithm can then be developed to identify every simple boundary and interior hole locally. Furthermore, these graph-theoretic information can also be forwarded to the sink or base station to recognize the geometric characteristics among these coverage holes existing in the network fabric remotely.

並列關鍵字

Coverage hole ； Wireless sensor network ； Distributed algorithm

參考文獻

[2] Peter Corke, Ron Peterson, and Daniela Rus, Finding holes in sensor networks," cmc.cs.dartmouth.edu

[3] Stefan Funke, Topological hole detection in wireless sensor networks and its applications," in Proceedings of the 2005 joint workshop on Foundations of mobile computing, pp.44-53 , 2005.

[5] S. Ganeriwal, A. Kansal, and M.B. Srivastava, Self aware actuation for fault repair in sensor networks," in IEEE International Conference on Robotics and Automation, Proceedings. ICRA '04, 2004.

[7] Chih-fan Hsin and Mingyan Liu, Randomly duty-cycled wireless sensor networks: dynamics of coverage," in IEEE Transactions on Wireless Communications, 2006.

[8] Chi-Fu Huang and Yu-Chee Tseng, The coverage problem in a wireless sensor network," in Proceedings of the 2nd ACM WSNA'03, pp.115-121, 2003.