近年來，k-邊界覆蓋(k-Barrier Coverage)在無線感測網路中是很重要且受到廣泛討論的問題。本論文所運作的場景為一無線行動感測網路(Wireless Mobile Sensor Networks，WMSNs)，其中每個感測器(Mobile Sensor，MS)具有移動的能力。在這樣的環境下，本論文擬研發一個分散式的自我佈建機制，使得行動感測器在場景中自我移動以形成一條k值盡可能大的k-邊界覆蓋(k-Barrier Coverage)防禦曲線。在移動的過程中，行動感測器將電量納入考量，使得建構的防禦曲線擁有較長的生命期，並使多個行動感測器不會移動至相同位置，避免產生決策衝突，浪費電量。相較於相關的研究，實驗模擬顯示，本論文所提出的k-Barrier Coverage演算法具有較長的生命期。

The k-Barrier Coverage is known as the problem of detecting the intruders by at least k sensors when the intruders moving along the crossing paths from one boundary to another. This thesis proposes a barrier coverage mechanism for Wireless Mobile Sensor Networks (WMSNs). At the network initialization phase, all mobile sensors move in a distributed manner for constructing the k-Barrier Coverage. The thesis aims at prolonging the barrier lifetime while achieving k-barrier coverage. Experimental study reveals that our proposed k-barrier coverage approach outperforms existing related schemes in terms of the energy consumption of mobile sensors participating in the k-barrier defense curve.

目錄
圖目錄	IV
表目錄	VI
第一章、簡介	1
第二章、網路環境與問題描述	5
2.1	網路環境	5
2.2	問題描述	5
第三章、演算法	10
3.1	網路初始化階段	10
3.2	防禦曲線建立階段	13
3.2.1	Fine-Grain Location Adjustment Task	13
3.2.2	Move Forward & Wait Task	14
3.2.3	Hole Healing Task	17
第四章、模擬實驗	33
4.1	模擬環境	33
4.2	模擬結果	34
第五章、結論	41
參考文獻	42
附錄-英文論文	46

圖目錄
圖 1：入侵路線	6
圖 2：未滿足Disjoint Constraint的兩條 和 共同合作防禦時可能產生的問題	9
圖 3：網路場景拓樸圖和網格大小示意圖	11
圖 4：b0設置位置示意圖	12
圖 5：建構3-barrier coverage的方式	12
圖 6：解決碰撞問題示意圖	16
圖 7：行動感測器皆進入等待或穩定狀態的場景圖	17
圖 8：一條Hole-healing Path示意圖	19
圖 9：移動向量示意圖	20
圖 10：建立之Path個數示意圖	23
圖 11：Muiti-hop Hole Healing Procedure	25
圖 12：Collision Assignment (CA) Problem	26
圖 13：行動感測器si與sj填補hx,y與時間軸的對應關係	28
圖 14：建完防禦曲線發送封包示意圖	29
圖 15：剩餘行動感測器繼續建構Barrier示意圖	30
圖 16：初始場景圖及結束圖	34
圖 17：剩餘電量差比較圖	36
圖 18：平均移動距離比較圖	36
圖 19：防禦曲線生命期比較圖	37
圖 20：行動感測器根據不同佈建方式的場景圖	38
圖 21：剩餘電量差比較圖	39
圖 22：平均移動距離比較圖	39
圖 23：防禦曲線生命期比較圖	40

表目錄
表 1：模擬相關參數	33

[1]	S. Kumar, T. H. Lai and A. Arora, “Barrier Coverage with Wireless Sensors,” ACM International Conference on Mobile Computing and Networking (ACM MobiCOM), 2005. 
[2]	A. Chen, S. Kumar and T. H. Lai, “Local Barrier Coverage in Wireless Sensor Networks,” IEEE Transactions on Mobile Computing , vol. 9, no. 4, Apr. 2010. 
[3]	G. Yang, and D. Qiao, “Barrier Information Coverage with Wireless Sensors,” IEEE International Conference on Computer Communications (IEEE INFOCOM), 2009.
[4]	J. He, and H. Shi, “Finding barriers with minimum number of sensors in wireless sensor networks, ” IEEE International Conference on Communications (IEEE ICC), 2010. 
[5]	Y. T. Lin, K. K. Saluja, P. Ramanathan, “Connected Barrier Coverage on A Narrow Band : Analysis and Deployment, ” IEEE International Conference on Sensing, Communication, and Networking (IEEE SECON), 2010. 
[6]	G. Yang, and D. Qiao, “Multi-Round Sensor Deployment for Guaranteed Barrier Coverage, ” IEEE International Conference on Computer Communications (IEEE INFOCOM), 2010.
[7]	B. Liu, O. Dousse, J. Wang and A. Saipulla, “Strong Barrier Coverage of Wireless Sensor Networks,” ACM International Symposium on Mobile Ad Hoc Networking and Computing (ACM MobiHOC), 2008. 
[8]	A. Saipulla, C. Westphal, B. Liu and J. Wang “Barrier Coverage of Line-Based Deployed Wireless Sensor Networks,” IEEE International Conference on Computer Communications (IEEE INFOCOM), 2009. 
[9]	A. Gallais, J. Carle and D. Simplot-Ryl, “Localized Sensor Area Coverage with Low Communication Overhead,” IEEE International Conference on Pervasive Computing and Communications (IEEE PERCOM), 2006. 
[10]	Y. Shang and H. Shi, “Coverage and Energy Tradeoff in Density Control on Sensor Networks,” IEEE International Conference on Parallel and Distributed Systems (IEEE ICPADS), 2005. 
[11]	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. 
[12]	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.
[13]	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.
[14]	Q. Zhao and M. Gurusamy, “Maximizing Network Lifetime for Connected Target Coverage in Wireless Sensor Networks,” IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (IEEE WiMob), 2006.
[15]	M. Cardi, T. Thai, Y. Li and W. Wu, “Energy-Efficient Target Coverage in Wireless Sensor Networks,” IEEE International Conference on Computer Communications (IEEE INFOCOM), 2005. 
[16]	A. Saipulla, B. Liu, G. Xing, X. Fu, and J. Wang, “Barrier coverage with sensors of limited mobility,” in ACM Mobihoc, 2010.
[17]	B. Bhattacharya, B. Burmester, Y. Hu, E. Kranakis, Q. Shi, and A. Wiese, “Optimal movement of mobile sensors for barrier coverage of a planar region,” Combinatorial Optimization and Applications, 2008.
[18]	A. Saipulla, C. Westphal, B. Liu, and J. Wang, “Barrier Coverage with Line-Based Deployed Mobile Sensors,” Ad Hoc Networks, 2011.
[19]	C. Shen, W. Cheng, X. Liao, and S. Peng, “Barrier coverage with mobile sensors,” in IEEE I-SPAN, 2008.
[20]	T. Cheng and A. Savkin, “A problem of decentralized self-deployment for mobile sensor networks: Barrier coverage between landmarks,” in IEEE ICCA, 2009.
[21]	G. Yang, W. Zhou, and D. Qiao, “Defending against barrier intrusions with mobile sensors,” in IEEE WASA, 2007.
[22]	D. Ban, W. Yang, J. Jiang, J. Wen, and W. Dou, “Energy-Efficient Algorithms for k-Barrier Coverage In Mobile Sensor Networks ,” International Journal of Computers Communications & Control, vol. 5, no. 5, 2010.
[23]	L. Kong, X. Liu, Z. Li, and M. Wu, “Automatic Barrier Coverage Formation with Mobile Sensor Networks,” in IEEE ICC, 2010. 
[24]	S. Silvestri, “MobiBar: Barrier Coverage with Mobile Sensors,” IEEE Global Communications Conference (IEEE Globecom), 2011.