利用計算幾何學解決無線感測網路之目標區域覆蓋問題

Preserving Target Area Coverage in Wireless Sensor Networks by Using Computational Geometry

古欣惠(Hsin-Hui Ku)

指導教授 ： 石貴平

淡江大學/工學院/資訊工程學系資訊網路與通訊碩士班/碩士(2010年)

https://doi.org/10.6846/TKU.2010.00606

摘要

在 Wireless Sensor Networks (WSNs)中，要如何安排Sensor Nodes 成為Active模式，進行感測重要區域的任務，並有效地延長WSNs 的工作時間，是一個非常重要的議題。本篇論文提出一個以計算幾何學中Voronoi Diagram 以及 Delaunay Triangulation 為理論基礎， 所設計之分散式工作排程機(Geometric-Base Activity Scheduling Scheme，GAS)。Sensor Nodes 可以自我決定何時進入Sleep 狀態，或是為了維持Coverage 的需求而進入Active 狀態。在GAS中，可以找到數量盡量少的Sensor Nodes 來負責維持感測任務。然而，我們可以知道尋求Sensor Nodes 的最少數量，是一個組合最佳化(Combinatorial Optimization)的問題，而此問題又是一個NP-Complete 的問題。最後透過實驗模擬結果顯示，GAS 能有效地規畫Sensor Nodes 何時在Active 以及Sleep 模式之間做切換，且當Sensor Nodes 分布不平均時，更能顯示出GAS 的效果，有效地延長網路的有效感測時間。

關鍵字

目標區域 ； Voronoi 圖 ； Delaunay Triangulation ； 覆蓋集

並列摘要

The activity scheduling of sensors to alternately wake up for sensing obligation such that the network lifetime can be efficiently prolonged is a very important issue in wireless sensor networks (WSNs). Target area coverage is a new coverage problem in wireless sensor networks. The paper addresses the target area coverage problem and schedules sensors to alternatively wake up to collaboratively cover and sense the target area.
A geometric-based activity scheduling scheme, named GAS scheme, for WSNs to fully cover a target area is proposed. By means of computational geometry, the sensors can self-determine when to sleep or wake up while preserving the sensing coverage. GAS is able to find as few sensors as possible to cover the target area, which is termed a cover set. In addition, GAS can find as many number of cover sets as possible to be alternately in charge of the sensing task. Simulation results show that GAS can efficiently schedule the sensor when to switch between active and sleep modes. Furthermore, the network lifetime can be prolonged significantly in comparison with the state-of-the-art schemes.

並列關鍵字

Target area coverage ； Voronoi Diagram ； Delaunay Triangulation ； Cover Set

參考文獻

[6] J. Choi, J. Hahn, and R. Ha, “A fault-tolerant adaptive node scheduling scheme for wireless sensor networks,” Journal of Information Science and Engineering, vol. 25, pp. 273–287, 2009.

[2] F. Aurenhammer, “Voronoi diagrams-a survey of a fundamental geometric data structure,” ACM Computing Survey, vol. 23, no. 3, pp. 345–405, 1991.

[3] X. Bai, Z. Yun, D. Xuan, T. Lai, andW. Jia, “Deploying four-connectivity and full-coverage wireless sensor networks,” in Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, Apr. 2008, pp. 296–300.

[8] C. Gui and P. Mohapatra, “Virtual patrol: A new power conservation design for suveillance using sensor networks,” in Proceedings of the IEEE International Symposium on Information Processing in Sensor Networks (IPSN), Apr. 2005.

[9] H. Gupta, S. R. Das, and Q. Gu, “Connected sensor cover : self-organization of sensor networks for efficient query execution,” in Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), 2003, pp. 189–200.