無線視覺感測器網路（WVSNs）由許多視覺感測器組成。市面上有許多類型的視覺感測器已被廣泛應用在物聯網應用中。這些類型的視覺感測器包括：紅外感測器，微波感測器，超聲波感測器，照相機和雷達。與全向感測器相比，視覺感測器擁有更好的性能，因為它可以進一步回傳入侵者的方向。然而，大多現有的邊界覆蓋機制皆只考量在全向性的無線感測器網路(WSNs)中，因此不能有效地應用在無線視覺感測器網路，而原因在於視覺感測器的感測區域為扇形感測區域。有鑑於此，本論文研究在無線視覺感測器網路中，提出具監控效能提升之邊界覆蓋技術。該技術有三種演算法，分別是：基礎演算法(BA)，回溯演算法(BTA)和分支演算法(BRA)，旨在建構出數量最大且彼此不相交集之防禦屏障，其中，每條建構出的防禦屏障亦能支持k-邊界覆蓋監控品質之需求，如此將能夠確保入侵者的任意入侵路線，皆能夠被視覺感測器偵測至少k次，以提升監控可靠性。
針對本論文所提出之邊界覆蓋技術，我們除了以理論的角度分析其性能外，亦透過實驗模擬與其他現有相關論文進行多維度的比較。而分析與實驗結果皆顯示本論文所提出之邊界覆蓋技術實現了與最優解相似的性能，且具有較少的控制封包數量。除此之外，與現有論文相比，本論文所提出之分支演算法不僅在控制封包數量上具有絕對優勢外，在防禦屏障建構的數量上更具有較佳的性能。

A wireless visual sensor network (WVSN) consists of a number of visual sensors. Many types of visual sensors have been widely applied in constructing a wireless sensor network for the IoT application. These types of sensors include infrared sensor, microwave sensor, ultrasonic sensor, camera, and radar. Compared with the omni-directional visual sensor, the visual sensor can achieve better performance because it can further report the direction of the intruder. Unfortunately, most existing barrier-coverage mechanisms considered the omni-directional sensor networks. They cannot be efficiently applied to WVSNs because the sensing area of each visual sensor is fan-shaped. This dissertation investigates the surveillance service problem which supports surveillance quality of k-barrier coverage in WVSNs. Three algorithms, called BA, BTA and BRA, are proposed aiming at finding a maximal number of different defense barriers, each of which supports k-coverage. As a result, the intruders intending to cross the monitoring area can be detected by at least k visual sensors. 
Performance analyses of the proposed algorithms are conducted in chapter 3.3.3 to verify the performance improvement from the theoretic point of view. In performance study, the proposed algorithms are compared with other existing works. Experimental study shows that the proposed k-barrier coverage algorithm achieves similar performance to the optimal solution but has fewer control packets. Furthermore, the proposed BRA achieves better performance in terms of the numbers of control packets and constructed defense barriers, as compared with the existing works.

Contents
List of Figures	IV
List of Tables	V
Chapter 1: Introduction	1
Chapter 2: Related Works	7
2.1 Barrier Coverage in WSNs	7
2.2 Barrier Coverage in directional WSNs	8
Chapter 3: QoS Guaranteed Surveillance Algorithms	11
3.1 Network Environment	11
3.2 Problem Formulation	12
3.3 k-Barrier Coverage Construction Mechanism (k-BCC)	16
3.3.1 Initialization Phase	16
3.3.2 Barrier Construction (BC) Phase	18
3.3.2.1 Basic Approach (BA)	21
3.3.2.2 Backtracking Approach (BTA)	28
3.3.2.3 Branch Approach (BRA)	30
3.3.3 Analyses of k-BCC	35
3.3.3.1 Analysis of Message Complexity	35
3.3.3.2 Analysis of Efficiency	36
3.4 Simulation	49
Chapter 4: Full-View Guaranteed Surveillance Algorithms	63
4.1 Background	63
4.2 Network Environment and Problem Formulations	70
4.2.1 Network Environment	70
4.2.2 Problem Formulations	72
4.3 Full-View Barrier Construction Algorithm (FBCA)	74
4.3.1 Region Partitioning Phase	75
4.3.2 Grid Excluding Phase	77
4.3.3 Grid Verification Phase	79
4.3.4 Full-View Barrier Construction Phase	85
4.3.5 Construction of Full-View Barrier	89
4.4 Simulation	91
4.4.1 Simulation Model	91
4.4.2 Simulation Results	91
Chapter 5: Conclusion	92
References	93

List of Figures
Fig. 1. Grid-based partition.	16
Fig. 2. The fully covered grids of va and vb.	16
Fig. 3. An example for illustrating the construction of a DB2 by applying BA.	25
Fig. 4. An example for illustrating the construction of a DB2 by applying BTA.	28
Fig. 5. Priority table.	32
Fig. 6. A running example by applying the BRA.	32
Fig. 7. An example that k-BCC misses to construct the existed defense barrier bun.	37
Fig. 8. The calculation of the number of partially covered grids of vi.	45
Fig. 9. A snapshot of the simulation environment.	50
Fig. 10. Performance comparison of BA, BTA, BRA, CoBRA, D-TriB, and MDP in terms of control overheads with different number of visual sensors.	53
Fig. 11. Performance comparison of BA, BTA, BRA, CoBRA, D-TriB, and MDP in terms of average number of DBk by varying the number of visual sensors.	55
Fig. 12. Performance evaluation on plose with different FoV	56
Fig. 13. Performance comparison of BA, BTA, BRA, CoBRA, D-TriB and MDP in terms of average number of visual sensors needed for constructing a DB3	57
Fig. 14. Performance comparison of MDP, BA, BTA, and BRA in terms of the success ratio of a DB2 construction by varying both of the size of grid and degree of FoV.	58
Fig. 15. Performance comparison of BA, BTA, BRA, and their combinations including BTA+BRA and BRA+BTA in terms of average number of DB2 by varying the number of visual sensors.	59
Fig. 16. Performance comparison of BA, BTA, BRA, CoBRA, D-TriB, MDP, and MNBG in terms of the average number of control packets per constructing a DB2.	61
Fig. 17. Performance comparison of BA, BTA, BRA, CoBRA, D-TriB, MDP, and MNBG in terms of the average number of control packets per constructing a DB3	62
Fig. 18. The sensing model and the full-view coverage model.	71
Fig. 19. Grid-based partition.	75
Fig. 20. The fully covered grids of sa and sb.	75
Fig. 21. Weighted Grid Matrix (WGM).	76
Fig. 22. An example of applying the Minimal Number Condition.	79
Fig. 23. Construction of reliable zone.	81
Fig. 24. Construction of safe region.	82
Fig. 25. Evaluation of Oij.	84
Fig. 26. Example of Reliable zone.	85
Fig. 27. Example of cover group G(ψ).	87
Fig. 28. Construction of weighted graph.	88

List of Tables
Table I	48
Table II	48
Table III	91

[1]	R. Holman, J. Stanley, and T. Ozkan-Haller, “Applying Video Sensor Networks to Nearshore Environment Monitoring,” IEEE Trans. on Pervasive Computing, Vol.2, no. 4, pp.14–21, Oct.-Dec. 2003. 
[2]	W. Feng, B. Code, E. Kaiser, M. Shea, and W. Feng, Panoptes: Scalable Low-power Video Sensor Networking Technologies, Proc. ACM MM, 2003. 
[3]	P. Kulkarni, D. Ganesan, P. Shenoy, and Q. Lu, “SensEye: A Multitier Camera Sensor Network,” Proc. ACM MM, 2005. 
[4]	Department of Homeland Security [Online]. Available: http://www.dhs.gov/securing-and-managing-our-borders.
[5]	R. C. Archibold (2007). 28-mile virtual fence is rising along the border. New York Times [Online]. Available http://www.nytimes.com/2007/06/26/us/26fence.html?_r=0.
[6]	S. Kumar, T. H. Lai, and A. Arora, “Barrier Coverage with Wireless Sensors,” Proc. ACM MobiCom, 2005.
[7]	S. Kumar, T. H. Lai, M. E. Posner, and P. Sinha, “Maximizing the Lifetime of a Barrier of Wireless Sensors,” IEEE Trans. Mobile Comput., vol. 9, no. 8, pp. 1161–1172, Aug. 2010.
[8]	A. Chen, S. Kumar, and T. H. Lai, “Local Barrier Coverage in Wireless Sensor Networks,” IEEE Trans. Mobile Comput., vol. 9, no. 4, pp. 491–504, Apr. 2010.
[9]	C. F. Huang and Y. C. Tseng, “The Coverage Problem in a Wireless Sensor Network,” Proc. ACM WSNA, 2003.
[10]	G. Yang and D. Qiao, “Multi-Round Sensor Deployment for Guaranteed Barrier Coverage,” Proc. IEEE INFOCOM, 2010.
[11]	B. Liu, O. Dousse, J. Wang, and A. Saipulla, “Strong Barrier Coverage of Wireless Sensor Networks,” Proc. ACM MobiHoc, 2008.
[12]	A. Chen, T. H. Lai, and D. Xuan, “Measuring and Guaranteeing Quality of Barrier Coverage for General Belts with Wireless Sensors,” ACM Trans. Sens. Netw., vol. 6, no. 1, Dec. 2009.
[13]	S. He, X. Gong, J. Zhang, J. Chen, and Y. Sun, “Barrier Coverage in Wireless Sensor Networks: From Lined-based to Curve-based Deployment,” Proc. IEEE INFOCOM, Turin, Italy, Apr. 2013.
[14]	S. He, X. Gong, J. Zhang, J. Chen, and Y. Sun, “Curve-Based Deployment for Barrier Coverage in Wireless Sensor Networks,” IEEE Trans. Wireless Commun., vol. 13, no. 2, pp. 724–735, Feb. 2014.
[15]	H. Ma and Y. Liu, “Some Problems of visual sensor Networks,” J. Sensor Networks, vol. 2, no. 1/2, pp. 44–52, Apr. 2007.
[16]	L. Zhang, J. Tang, and W. Zhang, “Strong Barrier Coverage with visual sensors,” Proc. IEEE GlobeCom, 2009.
[17]	K. P. Shih, C. M. Chou, C. I. Liu, and C. C. Li, “On Barrier coverage in wireless camera sensor networks,” Proc. IEEE AINA, 2010.
[18]	D. Tao, S. Tang, H. Zhang, X. Mao, and H. Ma, “Strong barrier coverage in visual sensor networks,” Comptu. Commun., vol. 35, no. 8, pp. 895–905, May 2012.
[19]	C. F. Cheng and K. T. Tsai, “Distributed Barrier Coverage in Wireless Visual Sensor Networks with β-QoM,” IEEE Sensors J., vol. 12, no. 6, pp. 1726–1735, Jun. 2012.
[20]	Z. Wang, J. Liao, Q. Cao, H. Qi, and Z. Wang, “Barrier Coverage in Hybrid visual sensor Networks,” Proc. IEEE MASS, 2013.
[21]	Z. Wang, J. Liao, Q. Cao, H. Qi, and Z. Wang, “Achieving  -barrier Coverage in Hybrid visual sensor Networks,” IEEE Trans. Mobile Comput., vol. 13, no. 7, pp. 1443–1455, Jul. 2014.
[22]	D. Tao, and T. Y. Wu, “A Survey on Barrier Coverage Problem in visual sensor Networks,” IEEE Sens. J., vol. 15, no. 2, pp. 876–885, Feb. 2015.
[23]	A. Schrijver, “Combinatorial Optimization: Polyhedra and efficiency,” Springer, ISBN 978-3-540-44389-6, 2003.
[24]	W. H. R. Chan, P. F. Zhang, I. Nevat, S. G. Nagarajan, A. C. Valera, H. X. Tan, and N. Gautam, “Adaptive Duty Cycling in Sensor Networks With Energy Harvesting Using Continuous-Time Markov Chain and Fluid Models,” IEEE J. Sel. Areas Commun., vol. 33, no. 12, pp. 2687–2700, Dec. 2015.
[25]	R. Holman, J. Stanley, and T. Ozkan-Haller, “Applying Video Sensor Networks to Nearshore Environment Monitoring,” IEEE Trans. on Pervasive Computing, Vol.2, no. 4, pp.14–21, Oct.-Dec. 2003. 
[26]	W. Feng, B. Code, E. Kaiser, M. Shea, and W. Feng, Panoptes: Scalable Low-power Video Sensor Networking Technologies, Proc. ACM MM, 2003. 
[27]	P. Kulkarni, D. Ganesan, P. Shenoy, and Q. Lu, “SensEye: A Multitier Camera Sensor Network,” Proc. ACM MM, 2005. 
[28]	Department of Homeland Security [Online]. Available: http://www.dhs.gov/securing-and-managing-our-borders.
[29]	R. C. Archibold (2007). 28-mile virtual fence is rising along the border. New York Times [Online]. Available http://www.nytimes.com/2007/06/26/us/26fence.html?_r=0.
[30]	S. Kumar, T. H. Lai, and A. Arora, “Barrier Coverage with Wireless Sensors,” Proc. ACM MobiCom, 2005.
[31]	S. Kumar, T. H. Lai, M. E. Posner, and P. Sinha, “Maximizing the Lifetime of a Barrier of Wireless Sensors,” IEEE Trans. Mobile Comput., vol. 9, no. 8, pp. 1161–1172, Aug. 2010.
[32]	A. Chen, S. Kumar, and T. H. Lai, “Local Barrier Coverage in Wireless Sensor Networks,” IEEE Trans. Mobile Comput., vol. 9, no. 4, pp. 491–504, Apr. 2010.
[33]	C. F. Huang and Y. C. Tseng, “The Coverage Problem in a Wireless Sensor Network,” Proc. ACM WSNA, 2003.
[34]	G. Yang and D. Qiao, “Multi-Round Sensor Deployment for Guaranteed Barrier Coverage,” Proc. IEEE INFOCOM, 2010.
[35]	B. Liu, O. Dousse, J. Wang, and A. Saipulla, “Strong Barrier Coverage of Wireless Sensor Networks,” Proc. ACM MobiHoc, 2008.
[36]	A. Chen, T. H. Lai, and D. Xuan, “Measuring and Guaranteeing Quality of Barrier Coverage for General Belts with Wireless Sensors,” ACM Trans. Sens. Netw., vol. 6, no. 1, Dec. 2009.
[37]	S. He, X. Gong, J. Zhang, J. Chen, and Y. Sun, “Barrier Coverage in Wireless Sensor Networks: From Lined-based to Curve-based Deployment,” Proc. IEEE INFOCOM, Turin, Italy, Apr. 2013.
[38]	S. He, X. Gong, J. Zhang, J. Chen, and Y. Sun, “Curve-Based Deployment for Barrier Coverage in Wireless Sensor Networks,” IEEE Trans. Wireless Commun., vol. 13, no. 2, pp. 724–735, Feb. 2014.
[39]	H. Ma and Y. Liu, “Some Problems of Directional Sensor Networks,” J. Sensor Networks, vol. 2, no. 1/2, pp. 44–52, Apr. 2007.
[40]	L. Zhang, J. Tang, and W. Zhang, “Strong Barrier Coverage with Directional Sensors,” Proc. IEEE GlobeCom, 2009.
[41]	K. P. Shih, C. M. Chou, C. I. Liu, and C. C. Li, “On Barrier coverage in wireless camera sensor networks,” Proc. IEEE AINA, 2010.
[42]	D. Tao, S. Tang, H. Zhang, X. Mao, and H. Ma, “Strong barrier coverage in directional sensor networks,” Comptu. Commun., vol. 35, no. 8, pp. 895–905, May 2012.
[43]	C. F. Cheng and K. T. Tsai, “Distributed Barrier Coverage in Wireless Visual Sensor Networks with β-QoM,” IEEE Sensors J., vol. 12, no. 6, pp. 1726–1735, Jun. 2012.
[44]	Z. Wang, J. Liao, Q. Cao, H. Qi, and Z. Wang, “Barrier Coverage in Hybrid Directional Sensor Networks,” Proc. IEEE MASS, 2013.
[45]	Z. Wang, J. Liao, Q. Cao, H. Qi, and Z. Wang, “Achieving  -barrier Coverage in Hybrid Directional Sensor Networks,” IEEE Trans. Mobile Comput., vol. 13, no. 7, pp. 1443–1455, Jul. 2014.
[46]	D. Tao and T. Y. Wu, “A Survey on Barrier Coverage Problem in Directional Sensor Networks,” IEEE Sens. J., vol. 15, no. 2, pp. 876–885, Feb. 2015.
[47]	A. Schrijver, “Combinatorial Optimization: Polyhedra and efficiency,” Springer, ISBN 978-3-540-44389-6, 2003.
[48]	W. H. R. Chan, P. F. Zhang, I. Nevat, S. G. Nagarajan, A. C. Valera, H. X. Tan, and N. Gautam, “Adaptive Duty Cycling in Sensor Networks With Energy Harvesting Using Continuous-Time Markov Chain and Fluid Models,” IEEE J. Sel. Areas Commun., vol. 33, no. 12, pp. 2687–2700, Dec. 2015.
[49]	Y. Wang and G. Cao, “On Full-View Coverage in Camera Sensor Networks,” Proc. IEEE INFOCOM, 2011.
[50]	Y. Wang and G. Cao, “Barrier Coverage in Camera Sensor Networks,” Proc. ACM MobiHoc, 2011.
[51]	H. Ma, M. Yang, D. Li, Y. Hong, and W. Chen, “Minimum Camera Barrier Coverage in Wireless Camera Sensor Networks,” Proc. IEEE INFOCOM, 2012.
[52]	Y. Zhang, S. He, and J. Chen, “Data Gathering Optimization by Dynamic Sensing and Routing in Rechargeable Sensor Networks,” IEEE/ACM Trans. Netw., vol. PP, no. 99, pp. 1–15, Jun. 2015.