防禦線覆蓋問題在無線感測網路當中是一個非常重要的研究議題。確認式防禦線建立方式（Deterministic Barrier Deployment）是一種防禦線的建立方式，經由計算規劃好每一個感測器將要擺放的位置，然後將這些感測擺放上去用來建立防禦線。由於確認式建立方式是事先決定要如何擺放感測器，因此在部署感測器的時候會大幅的減少使用到的感測器數量。過往研究在探討防禦線覆蓋問題皆假設其環境場景為矩形，因此對於入侵者而言，其入侵時之進入面將被簡化為一條水平或者垂直的直線。然而，此假設忽略了在真實環境下的場景有可能為不規則形狀，此時若是以單一直線的方式來建構防禦線將有可能出現橫越場景的問題存在。為了解決這個問題，我們改由透過多條直線來建立防禦線的方式來處理。我們提出了一種確認式防禦線建立方式叫做Arbitrary Shape Barrier Construction（ASBC），這個方法更適合於真實的不規則場景。

The barrier coverage problemis an important research issue in Wireless SensorNetworks. Deterministic deployment is an efficient way to construct a barrier. Calculate the location where each sensor will be placed, and place these sensors to build a barrier. Since the deterministic deployment is established in advance to determine how the sensor is to be placed, the number of sensors used is greatly reduced when the sensor is deployed. In the previous result, the region ofthe barrier coverage problem was assumed to be a rectangular shape. The entry surface was simplified as a horizontal or vertical line. However, the assumption is not practical for the real-world environment. In general, the shape of the region is arbitrary. Using a single line to build a barrier may have intersections with the region. To solve this problem, we have to deal with it by establishing a barrier through multiple barrier linesegments. We propose analgorithm for establishing a barrier called Arbitrary Shape Barrier Construction (ASBC), which is more suitable for the real world.

目錄
圖目錄	IV
表目錄	V
第一章　簡介	1
第二章　相關研究	4
第三章　問題定義及環境假設	7
第四章　演算法設計概念和方法	10
4.1凸包	10
4.2凸多邊形之邊所形成之防禦線	11
第五章　Arbitrary Shape Barrier Construction演算法	12
5.1建立凸包	14
5.2修正線段	14
第六章實驗模擬	16
6.1實驗1:控制EL當作變因	17
6.2實驗2:控制DE當作變因	21
第七章結論	26
參考文獻	27
附錄-英文論文	31
圖目錄
圖1.不規則場景由上往下入侵方式示意圖	2
圖2.不規則場景環境假設示意圖	7
圖3.進入面示意圖	8
圖4.凸包與凸多邊形示意圖	11
圖5.防禦線沒有與場景邊界相交的情況	14
圖6.（a）防禦線與進入面AB曲線發生相交情況（b）進行線段修正動作之細節圖	15
圖7.模擬場景示意圖	17
圖8.與mGB、mLB和ECL方法比較，固定DE深度為Width的1/3單位長度，EL的長度為Length的1/3單位長度。	18
圖9.與mGB、mLB和ECL方法比較，固定DE深度為Width的1/3單位長度，EL的長度為Length的1/2單位長度。	19
圖10.與mGB、mLB和ECL方法比較，固定DE深度為Width的1/3單位長度，EL的長度為Length的2/3單位長度。	19
圖11.與CSD方法比較，固定DE深度為Width的1/3單位長度，EL的長度為Length的1/3單位長度。	20
圖12.與CSD方法比較，固定DE深度為Width的1/3單位長度，EL的長度為Length的1/2單位長度。	20
圖13.與CSD方法比較，固定DE深度為Width的1/3單位長度，EL的長度為Length的2/3單位長度。	21
圖14.與mGB、mLB和ECL方法比較，固定EL深度為Length的1/3單位長度，DE的長度為Width的1/4單位長度。	22
圖15.與mGB、mLB和ECL方法比較，固定EL深度為Length的1/3單位長度，DE的長度為Width的1/3單位長度。	22
圖16.與mGB、mLB和ECL方法比較，固定EL深度為Length的1/3單位長度，DE的長度為Width的1/2單位長度。	23
圖17.與CSD方法比較，固定EL深度為Length的1/3單位長度，DE的長度為Width的1/4單位長度。	24
圖18.與CSD方法比較，固定EL深度為Length的1/3單位長度，DE的長度為Width的1/3單位長度。	24
圖19.與CSD方法比較，固定EL深度為Length的1/3單位長度，DE的長度為Width的1/2單位長度。	25
表目錄
表1.問題正規化使用參數表	8
表2. Arbitrary Shape Barrier Construction（ASBC）演算法	13
表3.模擬參數	17

參考文獻
[1]	A. Boubrima, W. Bechkit, and H. Rivano, "Optimal WSN deployment models for air pollution monitoring," IEEE Transactions on Wireless Communications, vol. 16, no.5, pp.  2723-2735, May. 2017.
[2]	V.Jelicic, M.Magno, D.Brunelli, G.Paci, andL.Benini, "Context-Adaptive multimodal wireless sensor network for energy-efficient gas monitoring,"IEEE Sensors Journal, vol. 13, no. 1, pp.  328-338, Jan. 2013.
[3]	E.A.Kadir,S.L. Rosa, and A.Yulianti, "Application of WSNs for detection land and forest fire in Riau province Indonesia,"IEEEInternational Conference on Electrical Engineering and Computer Science (ICECOS), Indonesia, Oct. 2018.
[4]	B. Kadri,B. Bouyeddou, and D. Moussaoui,"Early fire detection system using wireless sensor networks,"IEEE International Conference on Applied Smart Systems (ICASS), Algeria, Nov. 2018.
[5]	A. Bhawiyuga, and W. Yahya,"MA LPWAN based wireless sensor node for aquaculture water quality nonitoringsystem,"IEEE International Conference on Sustainable Information Engineering and Technology (SIET), Indonesia, Nov.2018.
[6]	D. Pant, S.Verma, and P.Dhuliya, "A study on disaster detection and management using WSN in Himalayan region of Uttarakhand,"IEEE International Conference on Advances in Computing,Communication & Automation (ICACCA), India, Sept. 2017.
[7]	P.S. Kumar, L. Xie, B. Soong, and M.Y.Lee, "Feasibility for utilizing IEEE 802.15.4 compliant radios inside rotating electrical machines for wireless condition monitoring applications," IEEE Sensors Journal, vol. 18, no. 10, pp. 4293-4302, May. 2018.
[8]	D. Wu, D. Chatzigeorgiou, K. Youcef-Toumi, and R. Ben-Mansour, "Node localization in robotic sensor networks for pipeline inspection,"IEEE Transactions on Industrial Informatics, vol. 12, no. 2, pp. 809-819, Apr. 2016.
[9]	D. Thomas, R.Shankaran, M.Orgun, M.Hitchen, and W. Ni, "Energy-efficient military surveillance: coverage meets connectivity," IEEE Sensors Journal, vol. 19, no. 10, pp.3902-3911, Jan. 2019.
[10]	Z. Sun, Y. Xu, G. Liang, and Z. Zhou, "An intrusion detection model for wireless sensor networks with an improved V-Detector algorithm,"IEEE Sensors Journal, vol. 18, no. 5, pp. 1971-1984, Mar.2018.
[11]	J. Chen, B. Wang,W. Liu, L.T. Yang, and X. Deng, "Rotating directional sensors to mend barrier gaps in a line-based deployed directional sensor network," IEEE Systems Journal, vol. 11, no. 2, pp. 1027-1038, Jun. 2017.
[12]	R. Han, L. Zhang, and W. Yang, "Maximizing strong barriers in lifetime-heterogeneous directional sensor network,"IEEE International Symposium on Wireless Communication Systems (ISWCS), Poland, Sept. 2016.
[13]	F. Subhan, M. Noreen, M. Imran, M. Tariq, A. Khan, and M.Shoaib, "Impact of node deployment and routing for protection of critical infrastructures,"IEEE Access, vol. 7, pp. 11502-11514, Jan. 2019.
[14]	J.Rezazadeh, M.Moradim, K.Sandrasegaran, and R.Farahbakhsh, "Transmission power adjustment scheme for mobile beacon-assisted sensor localization,"IEEE Transactions on Industrial Informatics, vol. 15, no. 5, pp. 2859-2689, May. 2019.
[15]	J.Guo, and H.Jafarkhani, "Movement-efficient sensor deployment in wireless sensor networks with limited communication range," IEEE Transactions on Wireless Communications,vol. 18, no. 7, pp. 3469-3484, Jul. 2019.
[16]	H. Zhou, T. Jiang, C. Gong, and Y. Zhou, "Optimal estimation in wireless sensor networks with energy harvesting,"IEEE Transactions on Vehicular Technology, vol. 65, no. 11, pp. 9386-9396, Nov. 2016
[17]	S. Kumar, T.H. Lai, and A. Arora, "Barrier coverage with wireless sensors,"in Proc. 11th Annual International Conference on Mobile Computing and Networking, pp. 284–298, Germany, Aug. 2005.
[18]	A. Chen, S. Kumar, and T.H. Lai, "Local barrier coverage in wireless sensor networks,"IEEE Transactions on Mobile Computing, vol. 9, no. 4,pp. 491-504, Apr. 2010.
[19]	X. Zhang, M.L. Wymore, andD.Qiao, "An iterative method for strong barrier coverage under practical constraints,"IEEE International Conference on Communications (ICC), Malaysia, May. 2016.
[20]	T.G. Nguyen, C. So-In, and N.G.Nguyenm, "Maximum barrier coverage deployment algorithms in wireless sensor networks,"IEEE International Joint Conference on Computer Science and Software Engineering (JCSSE), Thailand, Jul. 2016.
[21]	H. Huang, T. Gong, R. Zhang, L.L. Yang, J. Zhang, and F. Xiao, "Intrusion detection based on k-coverage in mobile sensor networks with empowered intruders," IEEE Transactions on Vehicular Technology, vol. 67, no. 12, pp. 12109-12123, Dec. 2018.
[22]	M.Hammoudeh, F. Al-Fayez, H. Lloyd, R. Newman, B.Adebisi, A.Bounceur, and A.Abuarqoub, "A wireless sensor network border monitoring system: deployment issues and routing protocols,"IEEE Sensors Journal, vol. 17, no. 8, pp. 2572-2582, Apr. 2017.
[23]	H. Kim, and J. Ben-Othman, "HeteRBar: construction of heterogeneous reinforced barrier in wireless sensor networks,"IEEE Communications Letters, vol. 21, no. 8, pp. 1859-1862, Aug. 2017.
[24]	T.G. Nguyen, and C. So-In, "Distributed deployment algorithm for barrier coverage in mobile sensor networks,"IEEE Access, vol. 6, pp. 21042-21052, Apr. 2018.
[25]	D. Kim, W. Wang, J. Son, W. Wu, W. Lee, and A.O. Tokuta, "Maximum lifetime combined barrier-coverage of weak static sensors and strong mobile sensors," IEEE Transactions on Mobile Computing, vol. 16, no. 7, pp. 1956-1966, Jul. 2017
[26]	S. He, X. Gong, J. Zhang, J. Chen, and Y. Sun, " Curve-Based Deployment for Barrier Coverage in Wireless Sensor Networks," IEEE Transactions on Wireless Communications, vol. 13, no. 2, pp. 724-735, Jan. 2014.