在無線感測網路中，Coverage 一直是最重要的問題之一。barrier coverage主要是探討如何找出一群較少的sensor集合，以共同防衛國與國邊界並達到禁止惡意闖入的目的。而k-barrier coverage則定義為在邊界區域中至少有k個sensors 可感應闖入者跨越邊界。本論文考慮在一 Mobile WSN的場景中，假設其最低的防禦能力為k-barrier coverage，為提升此網路的防禦能力與延長其生命期，我們提出一分散式的演算法，以減少sensor總耗電量及平衡sensor電量消耗的考量下，移動少量sensor，使整個網路的防禦能力提昇至k+1-barrier coverage。而實驗數據顯示，本論文所發展的演算法能夠移動較少sensor提升整個網路至k+1-barrier coverage的防禦能力，並可有效延長整個網路的生命期。

The k-barrier coverage problem is known as the problem of detecting the intruders by at least k sensors when the intruder moves along the crossing paths from one boundary to another. This paper considers a mobile WSN with demand of k-barrier coverage. To increase the monitoring quality and reduces and balances the energy consumption for each mobile sensor, this paper designs a distributed algorithm aiming at moving fewer mobile sensors with shorter distance for increasing the monitoring quality from (k-1)-barrier coverage to k-barrier coverage. Performance study reveals that the proposed algorithm can efficiently improve the monitoring quality and extend the network lifetime.

目    錄
目    錄	III
圖 目 錄	V
表 目 錄	VII
第一章、緒論	1
第二章、網路環境與問題描述	3
2.1 網路環境與假設	3
2.2 問題描述及其挑戰性	4
第三章、One Dimensional k-Barrier Coverage Maintenance Protocol(KBCM-1D)	14
3.1 一維場景實做規則	15
3.2 The Algorithm	29
3.3 小結	45
第四章、Two Dimensional k-Barrier Coverage Maintenance Algorithm (KBCM-2D)	46
4.1 場景描述	47
4.2 The Algorithm	50
4.3小結	65
第五章、模擬實驗	67
第六章、結論	76
參考文獻	77
附錄—英文論文	79
圖 目 錄
圖(一)(a) Crossing paths	4
圖(一)(b) Not crossing paths	4
圖(二) 1-barrier coverage示意圖	7
圖(三) 0-barrier coverage表示圖	7
圖(四) 單一管狀的防衛曲線	8
圖(五) 形成分枝之防禦曲線	8
圖(六) 1-barrier coverage場景示意圖	9
圖(七) 漣波效應的產生，sensor s8移動後造成的空洞需要由sensor s7幫助填補	11
圖(八) 一維場景解析圖	13
圖(九) 此監控區防禦能力為2-barrier coverage	16
圖(九)(a)	17
圖(九)(b)	17
圖(十) 防衛能力為1-barrier coverage的防衛線	18
圖(十一) 單一方向單一鄰居可完成空洞的覆蓋	22
圖(十二)(a) 使用接力的移動方法時，s1必須移動距離d1	24
圖(十二)(b) 使用接力的移動方法時，s1必須移動距離d1	25
圖(十二)(c) 使用接力的移動方法時，s2必須移動距離d2	25
圖(十三) 使用單一sensor修復防衛線空洞時，s3必須獨自移動距離d3	25
圖(十四) 欲組成一條完整的防衛線需要七顆sensor	28
圖(十五) 一維狀況下的覆蓋率判斷	30
圖(十六) 整個場景中有三個低於要求標準的覆蓋區	42
圖(十七) sK掃描到空洞，開始尋求幫助	43
圖(十八) sG掃描到空洞，開始尋求幫助	43
圖(十九) 位在場景中間的sensor sH會向左右兩邊蒐集資訊	44
圖(二十) 不同的sensors提供不同的barrier coverage	48
圖(二十一) 額外被覆蓋住的shortest path	48
圖(二十一)(a) sensor sB與sA、sC相鄰並提供1-barrier coverage	54
圖(二十一)(b) sensor sB與sC切斷聯繫，無法提供1-barrier coverage	54
圖(二十二)(a) 包圍mover mA的鄰居	55
圖(二十二)(b) mover mA最遠可移動的一個極值	55
圖(二十二)(c) 四個移動極值m、n、o、p	56
圖(二十三)(a) mover mA最遠可移動的邊界g	57
圖(二十三)(b) mover mA完整可移動距離	57
圖(二十四) PRi,j所畫出的最大可感測範圍	57
圖(二十五)(a) crossing path位於邊界上	60
圖(二十五)(b) crossing path位於中間	60
圖(二十六) 三種演算法在不同sensors數量下的移動距離	68
圖(二十七) 三種演算法在不同sensors數量可達到的coverage數	70
圖(二十八) 三種演算法在不同sensors數量下電量平衡參數	72
圖(二十九) 三種演算法在達到k-barrier coverage 的執行時間	73
圖(三十) 三種演算法在不同sensors數量下生命週期	74
表 目 錄
表(一)：各符號定義	5
表(二)：一維場景下的符號定義	14
表(三)：二維場景下sensor符號定義	46
表(四)：實驗參數表	67

[1]	C. F. Huang and Y. C. Tseng, ”The Coverage Problem in a Wireless Sensor Network,” in International Conference on Wireless Sensor Networks and Applications (WSNA),  pp. 115-121, Sandiago, CA, 2003.
[2]	B. Y. Liu, P. Brass, O. Dousse, P. Nain, and D Towsley, “Mobility Improves Coverage of Sensor Networks,” in Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 300-308, 2005. 
[3]	A. Gallais, J. Carle, and David Simplot-Ryl, “Localized Sensor Area Coverage With Low Communication Overhead,” in Internation Conference on Pervasive Computing and Communications (PerCom),  pp. 2006. 
[4]	Y. Shang, and H. Shi, “Coverage and Energy Tradeoff in Density Control on Sensor Networkd,” in International Conference on Parallel and Distributed Systems (ICPADS), pp. 2005.
[5]	S. Kumar, T. H. Lai, and A. Arora, “Barrier Coverage with Wireless Sensors,” in Proceedings of the 11th annual International Conference on Mobile Computing and Networking (MobiCom), pp. 284-298, 2005. 
[6]	B. Liu, O. Dousse, J. Wang, and A. Saipulla, “Strong Barrier Coverage of Wireless Sensor Networks,” in Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pp. 411-419, May 2008.
[7]	M. Cardi and J. Wu, “Energy-Efficient coverage problems in Wireless Ad Hoc Sensor Networks,” Computer Communication, vol. 29, issue 4, pp. 413-420, Feb. 2006.
[8]	Q. Zhao and M. Gurusamy, “Maximizing Network Lifetime for Connected Target Coverage in Wireless Sensor Networks,” in IEEE International Conference on Wirless and Mobile Computing, Networking and Communications (WiMob), pp.94-101, 2006.
[9]	M. Cardi, T. Thai, Y. Li and W. Wu, “Energy-Efficient Target Coverage in Wirless Sensor Networks,” in Proceedings of IEEE INFOCOM, vol. 3, pp. 1976-1984, 2005.
[10]	Changxiang Shen, Weifang Cheng, Xiangke  Liao, and Shaoliang Peng, “Barrier Coverage with Mobile Sensors”, in Proceedings of ISPAN 2008, PP.99-104, 2008
[11]	Ai Chen, Ten H. Lai, and Dong Xuan, “Measuring and Guaranteeing Quality of Barrier-Coverage in Wireless Sensor Networks”, in proceedings of ACM MobiHoc, 2008.
[12]	Ai Chen, Santosh Kumar, and Ten H. Lai "Designing Localized Algorithms for Barrier Coverage," in proceedings of ACM MobiCom, 2007.