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

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.

目錄
第一章、 簡 介 1
第二章、 預備知識 7
第一節、 問題描述 7
第二節、 計算幾何 8
第三節、 基本概念 11
第三章、 COMPANION SET (CP)的尋找 15
第一節、 INITIATOR的選擇 15
第二節、 COMPANION NEIGHBORS的尋找 17
第三節、 擴散至整個網路 24
第四章、 COVER SET (CV) 尋找 31
第五章、 ACTIVITY SCHEDULING SCHEMES 38
第六章、 實驗結果 44
第七章、 結 論 50
參考文獻 52

圖目錄
圖1.Voronoi diagram以及Delaunay Triangulation 10
圖2.Sensor Network運作的時間架構 11
圖3.Companion Set示意圖 13
圖4.Cover Set示意圖 14
圖5.尋找Initiator的示意圖 17
圖6.An example that VC(sj) is not within C(sj) 19
圖7.Companion Neighbors之尋找 21
圖8.s1的Companion Neighbors之間Overlap狀況 22
圖9.Sensor Nodes之間的感測區域呈60O交集 23
圖10.以 為基準距離 24
圖11.Companion Neighbors選擇衝突 25
圖12.由Initiator擴散Rule1 & Rule2 28
圖13.其他擴散Rule3 & Rule4 30
圖14.Selection Zone 1.的証明 35
圖15.Cover Set的找尋 37
圖16.Companion Set成員依據剩餘電量安排Active時間長度 39
圖17.s2記錄一步通訊範圍內，已被指定時間的Sensor Nodes 40
圖18.s2尋找Cover Sets 42
圖19.s2安排每一組Companion Set以及Cover Sets的運作時間 42
圖20.Cover Set基準時間的計算 43
圖21.Active Sensor Nodes個數與時間的比較(1800個Sensor Nodes) 46
圖22.Active Sensor Nodes個數與時間的比較(2700個Sensor Nodes) 46
圖23.Active Sensor Nodes個數與時間的比較(3600個Sensor Nodes) 47
圖24.Average remaining energy(%) (1800個Sensor Nodes) 48
圖25.Average remaining energy(%) (3600個Sensor Nodes) 48
圖26.Average remaining energy(%) (3600個Sensor Nodes) 49

[1]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), Sept. 2003, pp. 313–325.

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

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

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

[5]Q. Cao, T. Abdelzaher, T. He, and J. Stankovic, “Towards optimal sleep scheduling in sensor networks for rare-event detection,” in Proceedings of the IEEE International Symposium on Information Processing in Sensor Networks (IPSN), Apr. 2005.

[6]C. F. Hsin and M. Liu, “Network coverage using low duty-cycled sensors: Random & coordinated sleep algorithms,” in Proceedings of the IEEE International Symposium on Information Processing in Sensor Networks (IPSN), Apr. 2004, pp. 433–442.

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

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

[10]F. Ye, G. Zhong, J. Cheng, S.Lu and L. Zhong, “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.

[11]D. Tian and N. D. Georganas, “A coverage-preserving node scheduling scheme for large wireless sensor networks,” in Proceedings of the ACM 1st International Workshop on Wireless Sensor Networks and Applications (WSNA), 2002, pp. 32-41.

[12]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), 2004, pp. 587-596.

[13]B. Carbunar, A. Grama, J. Vitek, and O. Carbunar, “Coverage Preserving Redundancy Elimination in Sensor Networks”, in Proceedings of the 1st IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON), 2004, pp. 377-386.

[14]X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless and C. Gill, "Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks," in Proceedings of the 1st international conference on Embedded networked sensor systems (SenSys), 2003, pp. 28–39.

[15]H. Zhang and J. C. Hou, “Maintaining sensing coverage and connectivity in large sensor networks,” in NSF International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks, 2004.

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

[17]T. Yan, T. He, and J. A. Stankovic, “Differentiated Surveillance for Sensor Networks,” in ACM International Conference on Embedded Networked Sensor Systems (SenSys), 2003, pp. 51-62

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

[19]D. Tian and N. D. Georganas, “Location and calculation-free nodescheduling schemes in large wireless sensor networks,” Ad Hoc Networks, vol. 2, no. 1, pp. 65–85, Jan. 2004.

[20]T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher, “Range-free localization schemes for large scale sensor networks,” in Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), 2003, pp. 81–95.

[21]D. Niculescu and B. Nath, “Ad hoc positioning system (APS) using AoA,” in Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, Mar. 2003, pp. 1734–1743.

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