防禦線覆蓋問題(barrier coverage problem)在無線感測網路中是一項非常重要的課題。在本論文中，我們將探討一個新形態的防禦線覆蓋問題，其名稱為強化防禦線覆蓋問題(reinforced barrier coverage problem)。強化防禦線覆蓋與過往的防禦線覆蓋之差別在於過往的防禦線覆蓋只能偵測單一邊界的突破，並無法偵測多邊界的突破。由於過往僅有少數研究針對強化防禦線覆蓋問題做探討，並且都是探討在矩形場景之中。因此在本計畫中我們將放寬此環境假設，探討強化式防禦線覆蓋問題於任意形狀之場景。

The barrier coverage problem is a very important issue in wireless sensing networks. In this thesis, we will explore a new form of barrier coverage problem, which is called the reinforced barrier coverage problem. The difference between the reinforced barrier coverage problem and the classical barrier coverage problem is that the classical barrier coverage problem can only detect breakthroughs on a single boundary, and cannot detect breakthroughs on multiple boundaries. Because only a few studies have focused on the issue of the reinforced barrier coverage problem, and they are all in the rectangular scene. Therefore, in this thesis, we will relax the environmental assumption and address the problem of the reinforced barrier coverage problem in arbitrary shapes.

目錄
圖目錄	IV
表目錄	V
第一章 簡介	1
第二章 相關研究	6
第三章 問題定義以及環境假設	9
第四章 方法概述	11
4.1 集中式演算法CARB (Centralized Algorithm for Reinforced Barrier)	11
4.2 分散式演算法DARB (Distributed Algorithm for Reinforced Barrier)	13
第五章 實驗模擬	14
5.1 集中式比較對象方法：	14
5.2 分散式比較對象方法：	14
第六章 結論	20
參考文獻	21
附錄-英文論文	23
圖目錄
圖 1. 防禦線覆蓋 (Barrier Coverage)	1
圖 2. 十字入口之多種穿越路線	2
圖 3. 強化式防禦線覆蓋	3
圖 4. 以國家當作場景	4
圖 5. 不規則形狀場景(arbitrary shapes)	7
圖 6. 任意多邊形場景	9
圖 7. 比較對象方法示意圖	15
圖 8. 撒落不同節點數量下之防禦線成本(集中式)	16
圖 9. 撒落不同節點數量下之防禦線成本(分散式)	17
圖 10. 不同頂點數量下之防禦線成本(集中式)	18
圖 11. 不同頂點數量下之防禦線成本(分散式)	18
圖 12. 各演算法可建構之強化防禦線組數	19
表目錄
表 1. 防禦線相關研究	4
表 2. 模擬參數設定	15

[1]I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "Wireless sensor Networks: a Survey," Comput. Netw., vol 38, no. 4, pp. 393-422, 2002.
[2]A. Chen, S. Kumar, and T. Lai. "Designing localized algorithms for barrier coverage," In Proc. of ACM MobiCom, 2007.
[3]D. W. Gage, "Command control for many-robot systems," In Proc. of AUVS, 1992.
[4]S. He, J. Chen, X. Li, X. Shen, and Y. Sun. "Cost-effective barrier coverage by mobile sensor networks," In Proc. of IEEE INFOCOM, 2012.
[5]S. He, X. Gong, J. Zhang, J. Chen, Y. Sun, "Barrier coverage in wireless sensor networks: from lined-based to curve-based deployment," In Proc. of IEEE INFOCOM, 2013.
[6]S. He, X. Gong, J. Zhang, J. Chen, Y. Sun, "Curve-based deployment for barrier coverage in wireless sensor networks," IEEE Trans. Wireless Commun., vol. 13, no. 2, pp. 724~735, 2014.
[7]S. Kumar, T. H. Lai, and A. Arora, "Barrier coverage with wireless sensors," In Proc. of ACM MobiCom, 2005.
[8]S. Kumar, T.H. Lai, and A. Arora, "Barrier coverage with wireless sensors," Wirel. Netw., vol. 13, no. 6, 2007.
[9]H. Kim, J.A. Cobb, "Maximum lifetime of reinforced barrier-coverage in wireless sensor networks," In Proc. of IEEE ICON, 2013.
[10]H. Kim, J. Ben-Othman and P. Bellavista, "On construction of collision-free UAV reinforced barrier," In Proc. of IEEE GLOBECOM, 2016.
[11]H. Kim, J. Ben-Othman, "HeteRBar: construction of heterogeneous reinforced barrier in wireless sensor networks," IEEE Commun. Lett., vol. 21, no. 8, pp. 1859-1862, 2017.
[12]B. Liu, O. Dousse, J. Wang, and A. Saipulla. "Strong barrier coverage of wireless sensor networks," In Proc. of ACM MobiHoc, 2008.
[13]L. Li, B. Zhang, X. Shen, J. Zheng and Z. Yao, "A study on the weak barrier coverage problem in wireless sensor networks," Comput. Netw., vol. 55, no. 3, pp. 711-721, 2011.
[14]Y. Wang and G. Cao. "Barrier coverage in camera sensor networks," In Proc. of ACM MobiHoc, 2011.
[15]J. Yick, B. Mukherjee, and D. Ghosal, "Wireless sensor network survey," Comput. Netw., vol. 52, no. 12, pp. 2292-2330, 2008.