邊界覆蓋(Barrier Coverage)在無線感測網路中是很重要且受到廣泛討論的問題。在多數的研究中，大多假設感測器的感測範圍是二元感測模型(Binary Sensing Model)，然而，在現實監控區域中，機率式感測模型較接近大多數真實的感測器行為，即目標物被感測到之機率會因為其與感測器之距離遠近而有所不同。本論文基於機率式感測模型(Probability Sensing Model)，提出一分散式演算法，探討k-邊界覆蓋(k-Barrier Coverage)之排程技術，在滿足使用者所設定的k-覆蓋機率值門檻之監測品質要求下，形成一條盡可能的延長生命期的防禦曲線。實驗模擬顯示，我們所提出的k-Barrier Coverage演算法具有較長的網路壽命。

In wireless sensor networks, barrier coverage issue has been widely discussed due to its important role. In literatures, the sensing model of the sensor is a binary sensing model which provides large detection probability. However, in reality, the closer the sensor is located to the object, the greater the probability of the object being sensed. This is because of the proximity of the sensor's distance varies. Based on the Probability Sensing Model, this paper proposes a decentralized algorithm method to deploy the sensors by using k-Barrier Coverage Scheduling. In order to meet the k-coverage probability requirements, the amount of sensors should be set by the user to extend the lifetime of the sensors. The simulation shows that the number of sensors used in the proposed k-Barrier Coverage algorithm are minimized in order to provide longer lifetime.

目錄
圖目錄	IV
表目錄	VI
第一章、簡介	1
第二章、網路環境與問題描述	6
2.1	網路環境	6
2.2	機率式感測模型	7
2.3	問題描述	8
第三章、演算法	15
3.1	網路初始化階段	15
3.2	滿足ε之感測器挑選階段	17
3.3	建構防禦曲線	19
3.3.1	感測器權重值計算	19
3.3.2	網格挑選工作	23
第四章、模擬實驗	33
4.1	模擬相關參數與環境	33
4.2	模擬結果	34
第五章、結論	47
參考文獻	48
附錄-英文論文	51

圖目錄
圖 1︰方型區域A的邊界分別是W_east、W_west、L_south、L_north所圍成。	6
圖 2︰Elfes sensing model。	7
圖 3：入侵者入侵路線。	8
圖 4︰非互斥的兩條防禦曲線DB_α^1與DB_β^1，共同合作所產生的問題。	13
圖 5︰網路場景拓樸圖。	16
圖 6︰感測器完整覆蓋的網格及網格的防衛等級。	17
圖 7：感測器的覆蓋長度計算與比較。	20
圖 8：Decision Maker挑選方式。	23
圖 9︰網格連接方式。	28
圖 10︰避免死路問題發生。	30
圖 11：分支優先權。	31
圖 12：欲建立DB^3，從網格g_3,2向g_4,1和g_4,3分支。	32
圖 13：網格大小的設置概念。	34
圖 14︰初始場景圖及結束圖。	35
圖 15︰平均成功建置防禦曲線機率比較圖。	36
圖 16︰感測器數量對偵測入侵者闖入成功捕捉率之影響。	37
圖 17：滿足感測機率下對於建置防禦曲線之影響。	38
圖 18：感測器建置防禦曲線時所消耗的電量比較圖。	39
圖 19：對於平均捕捉率下使用感測器數量比較圖。	40
圖 20：探討在不同感測器數量及作法排序下所滿足k-Barrier Coverage的組數之影響。	41
圖 21：感測器根據不同佈建方式的場景圖。	41
圖 22：在各個Scenarios中成功建置防禦曲線機率比較圖。	42
圖 23：在各個Scenarios中感測器數量對偵測入侵者闖入成功捕捉率之影響。	43
圖 24：在各個Scenarios中滿足感測機率下對於建置防禦曲線之影響。	44
圖 25：在各個Scenarios中的感測器在每個工作中的消耗電量之影響。	45
圖 26：權重值偏好影響。	46

表目錄
表 1：本論文與相關研究比較表	4
表 2：模擬相關參數	34

[1]	B. Liu, O. Dousse, J. Wang, and A. Saipulla, “Strong Barrier Coverage of Wireless Sensor Networks,” ACM MobiHoc, 2008.
[2]	S. Kumar, T. H. Lai, and A. Arora, “Barrier Coverage with Wireless Sensors,” ACM MobiCom, 2005. 
[3]	L. Liu, H. Ma, and X. Zhang, “Analysis for Localization-Oriented Coverage in Camera Sensor Networks,” IEEE WCNC, March 2008. 
[4]	C. F. Huang and Y. C. Tseng, “The Coverage Problem in a Wireless Sensor Network,” ACM WSNA, pp. 115-121, 2003.
[5]	Q. Zhao and M. Gurusamy, “Maximizing Network Lifetime for Connected Target Coverage in Wireless Sensor Networks,” IEEE WiMob, 2006.
[6]	M. Cardi, T. Thai, Y. Li and W. Wu, “Energy-Efficient Target Coverage in Wireless Sensor Networks,” IEEE INFOCOM, 2005.
[7]	G. Yang and D. Qiao, “Barrier information coverage with wireless sensors”, IEEE INFOCOM, 2009.
[8]	J. Li, J. Chen, and T. H. Lai, “Energy-Efficient Intrusion Detection with a Barrier of Probabilistic Sensors”, IEEE INFOCOM, 2012.
[9]	Y. Zou and K. Chakrabarty, “Sensor Deployment and Target Localization in Distributed Sensor Networks,” ACM Transactions Embedded Computing Systems, vol. 3, no. 1, pp.61-91, 2004.
[10]	Y. Zou and K. Chakrabarty, “A Distributed Coverage and Connectivity Centric Technique for Selecting Active Nodes in Wireless Sensor Networks,” IEEE Transactions Computers, vol. 54, no. 8, pp.978-991, 2005.
[11]	N. Ahmed, S. Kanhere, and S. Jha, “Probabilistic Coverage in Wireless Sensor Networks,” IEEE LCN, 2005.
[12]	J. Chen, J. Li, and T. H. Lai, “Trapping Mobile Targets in Wireless Sensor Networks: An Energy-Efficient Perspective”, IEEE Transactions on Vehicular Technology, vol.62, Issue 7, pp.3287-3300, 2013.
[13]	A. Galstyan, B. Krishnamachari, K. Lerman, S. Pattem, “Distributed Online Localization in Sensor Networks Using a Moving Target,” The ACM/IEEE IPSN, Apr. 2004. 
[14]	J. He, and H. Shi, “Finding Barriers with Minimum Number of Sensors In Wireless Sensor Networks,” IEEE ICC, 2010. 
[15]	Y. T. Lin, K. K. Saluja, P. Ramanathan, “Connected Barrier Coverage on A Narrow Band: Analysis and Deployment,” IEEE SECON, 2010.
[16]	S. Kumar, T. H. Lai, M. E. Posner, and P. Sinha, “Maximizing the Lifetime of a Barrier of Wireless Sensors,” IEEE Transactions On Mobile Computing, vol. 9, no. 8, 2010. 
[17]	A. Chen, S. Kumar, and T. H. Lai, “Designing Localized Algorithms for Barrier Coverage,” ACM MobiCom, 2007.
[18]	A. Gallais, J. Carle and D. Simplot-Ryl, “Localized Sensor Area Coverage with Low Communication Overhead,” IEEE PERCOM, 2006. 
[19]	Y. Shang and H. Shi, “Coverage and Energy Tradeoff in Density Control on Sensor Networks,” IEEE ICPADS, 2005. 
[20]	Y. Zou and K. Chakrabarty, “A Distributed Coverage- and Connectivity- Centric Technique for Selecting Active Nodes in Wireless Sensor Networks,” IEEE Transaction on Computers, vol. 54, Issue 8, pp. 978-991, Aug. 2005. 
[21]	M. Cardi and J. Wu, “Energy-Efficient coverage problems in Wireless Ad Hoc Sensor Networks,” Computer Communication, vol. 29, no. 4, pp. 413-420, Feb. 2006.
[22]	M. Cardi and D. Z. Du, “Improving Wireless Sensor Network Lifetime through Power Aware Organization,” Wireless Networks, vol. 11, no. 3, pp. 333-340, May 2005
[23]	A. Hossain, P. K. Biswas and S. Chakrabarti, “Sensing Models and Its Impact on Network Coverage in Wireless Sensor Network”, ICIIS, 2008