無線感測網路是將多台感測器放在特定的區域，目的是用來監控環境狀況，在許多情況下，監控應用有嚴格的壽命要求，其要求網絡要在固定的週期內操作。感測器覆蓋和網絡生命週期之間的權衡已經在感測器網路文獻廣泛研究。一個感測器是絕對不夠覆蓋整個環境的目標物，和由於感測器的電量是固定的，有些目標物到最後都不會被感測器所覆蓋，目標物被覆蓋的比率在WSN 運行的其間隨著時間而減少。因此本篇論文的目標就是找一個排程去延長網路的運行時間，維持一定比例的目標物被感測器所覆蓋，我提出最小化能量消耗的排程去達成生命週期的延長。

Wireless sensor network (WSN) consists of more than one sensor deployed in a particular area.Typical usage of WSNs is to monitor environmental conditions, in such case, there are strict requirements of lifetime in monitoring applications, which demands the network to operate for at least a designated period of time The trade-off between sensor coverage and network lifetime has been studied extensively in the sensor network literature. One sensor is unable to cover the entire target environment. And due to the limited battery power, some targets will not be covered by any sensor eventually. The proportion of targets covered during the operation of WSN is a decreasing function of time.
Thus, the aim of this paper is to find a scheduling scheme that extends the network operating time while maintaining a certain ratio of targets covered by some sensors. we propose a minimal energy-consuming schedule that accomplishes lifetime extension.

Acknowledgements ......................ii
論文提要...............................iii
Abstract ...............................iv
第一章 緒論...............................1
1.1 前言. . . . . . . . . . . . . .. 1
1.2 研究動機. . . . . . . . . . . . . 2
1.3 研究方法. . . . . . . . . . . . . 3
1.4 論文架構. . . . . . . . . . . . . 4
第二章 背景知識與相關研究...................5
2.1 背景知識. . . . . . . . . . . . . 5
2.2 相關研究. . . . . . . . . . . . . 6
第三章 系統模型和問題描述...................8
第四章 方法解析...........................12
4.1 初步假設. . . . . . . . . . . . . .  12
4.2 演算法說明. . . . . . . . . . . . .  15
第五章 模擬評估...........................21
5.1 演算法介紹. . . . . . . . . . . . .  21
5.2 模擬環境. . . . . . . . . . . . . .  21
5.3 模擬結果. . . . . . . . . . . . . .  22
第六章 結論..................................24
參考文獻................................25
附錄英文論文.............................28

圖目錄
1.1 簡單場景. . . . . . . . . . . . . .  3
3.1 網路生命週期為10，每台感測器的壽命為6 小時的網路場景.. 9
3.2 時間區段. . . . . . . . . . . . . . 9
4.1 每時間區段內的排程(ON 排程) . . . . . 13
4.2 最大有效覆蓋時間場景圖. . . . . . . . 14
4.3 最大有效覆蓋時間排程舉例. . . . . . . 14
4.4 最佳時間排程. . . . . . . . . . . .  15
4.5 同樣場景，不同物件權重值的環境圖. . .  17
4.6 圖4.5 環境圖中的時間排程. . . . . . . 17
4.7 情況1 場景圖. . . . . . . . . . . .  18
4.8 失誤率說明圖. . . . . . . . . . . .  19
5.1 目標物被覆蓋時間VS 目標物個數. . . .  22

[1] T. Banka, G. Tandon, and A. P. Jayasumana, “Zonal rumor routing for wireless sensor
networks”, in International Conference on Information Technology, 2005.
[2] P. Berman, G. Calinescu, C. Shah, and A. Zelikovsly, “Efficient energy management in
sensor networks”, 2005.
[3] D. Braginsky and D. Estrin, “Rumor routing algorithm for sensor networks”, in Proceedings
of the 1st ACM International Workshop on Wireless Sensor Networks and Applications.
[4] M. Cardei, M. Thai, Y. Li, and J. Wu, “Energy-efficient target coverage in wireless sensor
networks”, in Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer
and Communications Societies., 2005.
[5] T. W. Chim, “Along across algorithm for routing events and queries in wireless sensor
networks”, in International Symposium on Intelligent Signal Processing and Communication
Systems, 2005.
[6] C.-F. Chou, J.-J. Su, and C.-Y. Chen, “Straight line routing for wireless sensor networks”,
in 10th IEEE Symposium on Computers and Communications, 2005.
[7] S. Funkey, A. Kesselman, F. Kuhn, and Z. Lotker, “Improved approximation algorithms
for connected sensor cover”, in Wirel Netw., 2007.
[8] M. Hefeeda and H. Ahmadi, “An integrated protocol for maintaining connectivity and
coverage under probabilistic models for wireless sensor networks”, in Proceedings of the
1st International Conference on Embedded Networked Sensor Systems, 2009.
[9] G. S. Kasbekar, Y. Bejerano, and S. Sarkar, “Lifetime and coverage guarantees through
distributed coordinate-free sensor activation”, in IEEE/ACM Transactions on Networking,
2009.
[10] S. Kumar, T. H. Lai, and J. Balogh, “On k-coverage in a mostly sleeping sensor network”,
in IEEE Transactions on Computers, 2004.
[11] B. Liu, O. Dousse, J. Wang, and A. Saipulla, “Strong barrier coverage of wireless sensor
networks”, in Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc
Networking and Computing, 2008.
[12] C. Liu and G. Cao, “Distributed critical location coverage in wireless sensor networks
with lifetime constraint”, in INFOCOM, 2012 Proceedings IEEE, 2012.
[13] H. Liu, P. Wan, C.-W. Yi, X. Jia, S. Makki, and P. Niki, “Maximal lifetime scheduling
in sensor surveillance networks”, in Proceedings IEEE 24th Annual Joint Conference of
the IEEE Computer and Communications Societies., 2005.
[14] A. Saipulla, C. Westphal, B. Liu, and J. Wang, “Barrier coverage of linebased deployed
wireless sensor networks”, in INFOCOM 2009,IEEE, 2009.
[15] M. Scholar, “Wireless sensor network mac protocol: Smac tmac”, in 19th IEEE International
Parallel and Distributed Processing Symposium, 2013.
[16] T. H. T. Yan and J. A. Stankovic, “Differentiated surveillance for sensor networks”, in
Proceedings of the 1st International Conference on Embedded Networked Sensor Systems,
2003.
[17] D. Tian and N. Georganas, “A coverage-preserving node scheduling scheme for large
wireless sensor networks”, in Proceedings of the 1st ACM International Workshop on
Wireless Sensor Networks and Applications, 2002.
[18] 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, 2003.
[19] Y. Wang and G. Cao, “On full-view coverage in camera sensor networks”, in INFOCOM,
2011 Proceedings IEEE, 2011.
[20] H. Zhang and J. C. Hou, “Maintaining sensing coverage and connectivity in large sensor
networks”, 2005.
[21] T. Zheng, S. Radhakrishnan, and V. Sarangan, “Pmac: An adaptive energy-efficient mac
protocol for wireless sensor networks”, in 19th IEEE International Parallel and Distributed
Processing Symposium, 2005.
[22] Y. Zou and K. Chakrabarty, “A distributed coverage and connectivity centric technique
for selecting active nodes in wireless sensor networks”, in IEEE Transactions on Computers,
2005.