在 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 的效果，有效地延長網路的有效感測時間。

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.

1 Abstract 1
2 Preliminaries 7
2.1 Problem description  8
2.2 Geometry 11
2.3 Basic concept  14
3 Cover Set discovery 17
3.1 Cover Set basic conditions 19
3.2 Cover Set in the establishment  25
3.3 Sensor Nodes of adding time  29
3.4 Algorithm  33
4 Scheduling mechanism 34
5 Simulation 37
5.1 Experiment 1: Special Scene  38
5.2 Experiment 2: normal distribution 44
6 Conclusion 53
Bibliography 55
Appendix 62

List of Figures
Figure 2.1 Voronoi diagram 12
Figure 2.2 Delaunay Triangulation 13
Figure 2.3 Operation time architecture 14
Figure 2.4 Cover Set Schematic 15
Figure 3.1 Coverb Set of the set up 23
Figure 3.2 Cover Set The Ideal point 25
Figure 3.3 Cover Set Member option 27
Figure 3.4 s2 from the establishment of Cover Set 27
Figure 3.5 sensor nodes initiation time 30
Figure 3.6 sensor nodes of adding time 31
Figure 3.7 Cover Set of the set up time 32
Figure 4.1 Initiator active arranged according to the length of time remaining capacity 35
Figure 5.1 Sensor remaining capacity diagram 39
Figure 5.2 Sensor’s power consumption 41
Figure 5.3 Activity points 42
Figure 5.4 Effective working time of sensor (LifeTime) 45
Figure 5.5 Activities per unit of time 46
Figure 5.6 The activities of the general distribution points 48
Figure 5.7 All nodes in the network, the average power 49
Figure 5.8 GAS and FANS in the coverage point of Q the average residual power 50
Figure 5.9 The number can be identified Cover Set 51
Figure 5.10 Composition of Cover Set 52

List of Tables
Table 5.1 Simulation Parameters 38

[1] E. Amaldi, A. Capone, M. Cesana, and I. Filippini, “Coverage planning of wireless sensors for mobile target detection,” in Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), Sep. 2008, pp. 48–57.
[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.
[4] B. Carbunar, A. Grama, J. Vitek, and O. Carbunar, “Coverage preserving redundancy elimination in sensor networks,” in Proceedings of the IEEE International Conference on Sensor and Ad Hoc Communications and Networks (SECON), 2004, pp. 377–386.
[5] M. Cardei, M. T. Thai, Y. Li, and W. Wu, “Energy-efficient target coverage in wireless sensor networks,” in Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, Mar. 2005.
[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.
[7] M. Ding, D. Chen, A. Thaeler, and X. Cheng, “Fault-tolerant target detection in sensor networks,” in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), Mar. 2005.
[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.
[10] C.-F. Huang, L.-C. Lo, Y.-C. Tseng, and W.-T. Chen, “Decentralized energy - conserving and coverage-preserving protocols for wireless sensor networks,” in Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS), 2005.
[11] 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.
[12] ——, “The coverage problem in a wireless sensor network,” ACM Mobile Networks and Applications (MONET), vol. 10, no. 4, pp. 519–528, Aug. 2005.
[13] 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, 2004 Mar.
[14] J. Jiang and W. Dou, “A coverage-preserving node scheduling algorithm for self-organized wireless sensor networks,” in Proceedings of the Grid and Cooperative Computing Workshops (GCC), 2003, pp. 587–596.
[15] K. Kar and S. Banerjee, “Node placement for connected coverage in sensor networks,” in Proceedings of the First Workshop on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), Mar. 2003.
[16] G. Kasbekar, Y. Bejerano, and S. Sarkar, “Lifetime and coverage guarantees through distributed coordinate-free sensor activation,” in Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), 2009, pp. 169–180.
[17] S. Kumar, T. H. Lai, and A. Arora, “Barrier coverage with wireless sensors,” in Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), 2005, pp. 284–298.
[18] S. Kumar, T. H. Lai, and J. Balogh, “On k-coverage in a mostly sleeping sensor network,” in Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), 2004, pp. 144–158.
[19] Q. Li, M. D. Rosa, and D. Rus, “Distributed algorithms for guiding navigation across a sensor network,” in Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), Sep. 2003, p. 313-325.
[20] D. Liu, “Connected area coverage sets in wireless sensor networks,” in Proceeding of Wireless Communications, Networking and Mobile Computing (WiCom), Sep. 2007, pp. 2787–2790.
[21] 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. 2005.
[22] K.-P. Shih, Y.-D. Chen, C.-W. Chiang, and B.-J. Liu, “A distributed active sensor selection scheme for wireless sensor networks,” in Proceedings of the IEEE International Symposium on Computers and Communications (ISCC), Jun. 2006.
[23] K.-P. Shih, D.-J. Deng, R.-S. Chang, and H.-C. Chen, “On connected target coverage for wireless heterogeneous sensor networks with multiple sensing units,” Sensors, vol. 9, no. 7, pp. 5173–5200, Jul. 2009.
[24] D. Tian and N. D. Georganas, “A coverage-preserving node scheduling scheme for large wireless sensor networks,” in Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), 2002, pp. 32–41.
[25] ——, “Location and calculation-free node scheduling schemes in large wireless sensor networks,” Ad Hoc Networks, vol. 2, no. 1, pp. 65–85, Jan. 2004.
[26] C. Vu and Y. Li, “Delaunay-triangulation based complete coverage in wireless sensor networks,” in Pervasive Computing and Communications (PerCom), Mar. 2009, pp. 1–5.
[27] S.-Y.Wang, K.-P. Shih, Y.-D. Chen, and H.-H. Ku, “Preserving target area coverage in wireless sensor networks by using computational geometry,” in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), Apr. 2010.
[28] X. Wang, G. Xinga, Y. Zhang, C. Lu, R. Pless, and C. Gill, “Integrated coverage and connectivity configuration in wireless sensor networks,” in Proceedings of the ACM International Conference on Embedded Networked Sensor Systems (SENSYS), 2003, pp. 28–39.
[29] Y.-C.Wang, C.-C. Hu, and Y.-C. Tseng, “Efficient placement and dispatch of sensors in a wireless sensor network,” IEEE Transactions on Mobile Computing, vol. 7, no. 2, pp. 262–274, Feb. 2008.
[30] T. Yana, T. He, and J. A. Stankovic, “Differentiated surveillance for sensor networks,” in Proceedings of the ACM International Conference on Embedded Networked Sensor Systems (SENSYS), 2003, pp. 51–62.
[31] F. Ye, G. Zhong, S. Lu, and L. Zhang, “PEAS: A robust energy conserving protocol for long-lived sensor networks,” in Proceeding of the 23rd International Conference on Distributed Computing Systems (ICDCS), 2003, pp. 28–37.
[32] H. Zhang and J. C. Hou, “Maintaining sensing coverage and connectivity in large sensor networks,” in Proceeding of NSF International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks, 2004.