在無線感測網路上以幾何學為基礎之分散式工作排程機制

Geo-BASS: Distributed Geometric-Based Activity Scheduling Schemes for Wireless Sensor Networks

江俊緯(Chun-Wei Chiang)

指導教授 ： 黃心嘉 ； 石貴平

淡江大學/工學院/資訊工程學系碩士班/碩士(2005年)

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

摘要

在Wireless Sensor Networks (WSNs)中，要如何安排Sensor Nodes成為Active模式並進行感測任務，而有效地延長使WSN的工作時間，是一個非常重要的議題。本篇論文提出一個以幾何學為基礎之分散式工作排程機制(Geometric-base activity scheduling scheme, Geo-BASS)。Geo-BASS為一個分散式排程方法，透過計算幾何學中Voronoi Diagram以及Delaunay Triangulation理論基礎的設計，Sensor Nodes可以自我決定何時可以進入睡眠狀態，或是為了維持Coverage的需求而進入Active狀態。Geo-BASS在某些時間中，可以找到數量盡量少的Sensors Nodes來負責感測任務。然而，我們可以知道尋求Sensor Nodes的最佳數量是一個組合最佳化(Combinatorial Optimization)的問題，而此問題是一個NP-Complete的問題。因此，我們提出一些heuristic methods，來解決這個問題。實驗模擬結果顯示，Geo-BASS能有效地規畫Sensor Nodes何時在Active以及Sleep模式之間做切換，而當Sensor Nodes分布不平均時，更能顯示出Geo-BASS的效果，有效地延長網路的存活時間。

關鍵字

無線感測網路 ； 計算幾何學 ； Voronoi Diagram ； Delaunay Triangulation ； 工作排程

並列摘要

The activity scheduling of sensors to alternatively wake up for sensing obligation such that the network lifetime can be efficiently prolonged is a very important issue in wireless sensor networks (WSNs). The paper proposes three geometric-based activity scheduling schemes, named Geo-BASS, for WSNs, under the requirement of complete coverage of a sensing field. Geo-BASS is a distributed scheme. By means of computational geometry, such as Voronoi diagram and Delaunay triangulation, the sensor can self-determine when to sleep or wake up while preserving the sensing coverage. Geo-BASS can find as less number of sensors as possible to be in charge of the sensing task for some time instance. Since the optimization is a combinatorial optimization problem, which has been shown to be an NP-complete problem. Therefore, some heuristic methods are proposed. In addition, Geo-BASS can also be extended to deal with the activity scheduling problems under different requirements, such as target coverage or patrol coverage requirements. Simulation results show that Geo-BASS can efficiently schedule the sensor when to switch between active and sleeping modes, especially when the sensors are deployed unbalanced. Furthermore, the network lifetime can be protracted significantly in comparison with the state-of-the-art schemes.

並列關鍵字

Wireless Sensor Networks ； Computational Geometry ； Voronoi Diagram ； Delaunay Triangulation

參考文獻

[22]C.-F. Huang and Y.-C. Tseng, “The coverage problem in a wireless sensor network,” in Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), 2003, pp. 115 – 121.

[2]Q. Huang, C. Lu, and G.-C. Roman, “Reliable mobicast via face-aware routing,” in Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, Mar. 2004.

[4]S. Megerian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava, “Worst and best-case coverage in sensor networks,” IEEE Transactions on Mobile Computing, vol. 4, no. 1, pp. 84–92, Jan./Feb. 2005.

[8]M. Cardei and D.-Z. Du, “Improving wireless sensor network lifetime through power aware organization,” ACM Wireless Networks, vol. 11, no. 3, pp. 333–340, May 2005.

[9]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.