覆蓋問題是一項重要的研究議題於無線感測網路之中。在本論文中，我們探討了一個新型態的覆蓋問題，我們稱之為目標物防禦線覆蓋問題。目標物防禦線覆蓋問題的目標是在目標物周遭建立一條連續的環狀防禦線，並且根據不同的應用，目標物防禦線與目標物將會有不同的距離限制。當有入侵者入侵時，此距離限制將有助於提供足夠的反應時間。目標物防禦線非常適用於軍事要塞的監控、校園安全的監控、生態保護區的監控等等。我們也透過實驗模擬分析目標物防禦線在不同的目標物數量下及不同的距離限制設定下其所需要的感測器成員數量及控制訊息交換量上的變化。

Coverage problem is one of the most important issue in wireless sensor networks. In this study, we address a new type of coverage problem named target-barrier coverage problem. The goal of target-barrier coverage is to construct a continuous barrier surrounds the target. Moreover, the constructed target-barrier should have a minimum distance from the target. Hence, target-barrier coverage can detect intrusion earlier, thus allowing more time for response. Target-barrier coverage is suitable for stronghold surveillance, campus surveillance, ecological surveillance and etc. In performance evaluation, the variation in the number of target-barrier members required and amount of the control message overhead under different settings are also analyzed through simulation experiments.

Table of Contents
List of figures						V
List of tables						VII
1. Introduction						1
2. Related Work						5
3. Problem Formulation and System Model			8
4. The Concept and Approach				12
4.1 Selection of Target-Barrier Initiators		12
4.2 Selection of Target-Barrier Members			13
4.3 Merge Mechanism for Multiple Targets Scenario	15
5. The Proposed Algorithm				20
5.1 Example of Execution of the Proposed Algorithm	24
6. Simulation Result					27
6.1 Single Target Scenario				28
6.1.1 Experiment 1: single target scenario with varied number of sensors					28
6.1.2 Experiment 2: single target scenario with varied dbound values						31
6.2 Multiple Targets Scenario				34
6.2.1 Experiment 3: multiple target scenario with varied number of targets					35
6.2.2 Experiment 4: multiple target scenario with varied dbound values						38
7. Conclusion						42
Reference						43

List of figures
Figure 1. Illustration of target-barrier coverage	3
Figure 2. An example of WSN with multiple targets (nt =3 and nb =1)	9
Figure 3. Illustration of initiators selection	13
Figure 4. Illustration of partial target-barrier construction	15
Figure 5. Illustration of merge mechanism	19
Figure 6. The pseudo code of the proposed TBC algorithm	24
Figure 7. An example of WSN with 800 sensors and 6 targets	25
Figure 8. Result of executing the TBC algorithm without confirm and merge phase	26
Figure 9. Result of executing the TBC algorithm	26
Figure 10. Comparison on the number of target-barrier members in the single target scenario (varied number of sensors)	29
Figure 11. Comparison on the amount of message exchange in the single target scenario (varied number of sensors)	30
Figure 12. Comparison on the ratio of amount of message exchange relative to the optimal solution in the single target scenario (varied number of sensors)	31
Figure 13. Comparison on the number of target-barrier members in the single target scenario (varied dbound values)	33
Figure 14. Comparison on the amount of message exchange in the single target scenario (varied dbound values)	33
Figure 15. Comparison on the ratio of amount of message exchange relative to the optimal solution in the single target scenario (varied dbound values)	34
Figure 16. Comparison on the number of target-barrier members in the multiple targets scenario (varied number of targets)	36
Figure 17. Comparison on the reduction rate of the number of target-barrier members required with the proposed merge mechanism (varied number of targets)	36
Figure 18. Comparison on the amount of message exchange in the multiple targets scenario (varied number of targets)	38
Figure 19. Comparison on the ratio of amount of message exchange relative to the optimal solution in the multiple targets scenario (varied number of targets)	38
Figure 20. Comparison on the number of target-barrier members in the multiple targets scenario (dbound values)	40
Figure 21. Comparison on the reduction rate of the number of target-barrier members required with the proposed merge mechanism (dbound values)	40
Figure 22. Comparison on the amount of message exchange in the multiple targets scenario (dbound values)	41
Figure 23. Comparison on the ratio of amount of message exchange relative to the optimal solution in the multiple targets scenario (dbound values)	41

List of tables
Table 1. The notations used in the problem formulation	10
Table 2. Functions used in the pseudo code of the proposed TBC algorithm	23
Table 3. Simulation parameters for the single target scenario	28
Table 4. Simulation parameters for the multiple targets scenario	35

[1] M. Angeles Sema, A. Bermudez, R. Casado, “Circle-based approximation to forest fires with distributed wireless sensor networks,” Proc. IEEE WCNC’13, pp. 4329-4334, 2013.
[2] S. Bhattacharjee, P. Roy, S. Ghosh, S. Misra, M.S. Obaidat, “Wireless sensor network-based fire detection, alarming, monitoring and prevention system for bord-and-pillar coal mines,” J. Syst. Softw., pp. 571-851, 2012.
[3] A. Chen, S. Kumar, T.H. Lai, “Local barrier coverage in wireless sensor networks,” IEEE Trans. Mobile Comput., vol. 9, no. 4, pp. 491-504, 2010.
[4] J. Chen, J. Li, T.H. Lai, “Energy-efficient intrusion detection with a barrier of probabilistic sensors: global and local,” IEEE Trans. Wirel. Commun., vol. 12, no. 9, pp. 4742-4755, 2013.
[5] C.F. Cheng, T.Y. Wu, H.C. Liao, “A density-barrier construction algorithm with minimum total movement in mobile WSNs,” Comp. Netw., vol. 62, pp. 208-220, 2014.
[6] M. Eftekhari, L. Narayanan, J. Opatmy “On multi-round sensor deployment for barrier coverage,” Proc. IEEE MASS’13, pp. 310-318, 2013.
[7] D.W. Gage, “Command control for many-robot systems,” Proc. AUVS’92, pp. 22–24, 1992.
[8] X. Hu, Y. Hu, B. Xu, “Energy-balanced scheduling for target tracking in wireless sensor networks,” ACM Trans. Sensor Netw., vol. 11, no. 1, pp. 21:1-21:29, 2014.
[9] S. Javadi, M.H. Hajiesmaili, A. Khonsari, B. Moshiri, “Temporal-aware rate allocation in mission-oriented WSNs with sum-rate demand guarantee,” Comput. Commun., vol. 59, pp. 52-66, 2015.
[10] J. Jiang, G. Han, H. Guo, L. Shu, J.J.P.C. Rodrigues, “Geographic multipath routing based on geospatial division in duty-cycled underwater wireless sensor networks,” J. Netw. Comput. Appl., vol. 59, pp. 4-13, 2016.
[11] Y.K. Joshi, M. Younis, “Exploiting skeletonization to restore connectivity in a wireless sensor network,” Comput. Commun., vol. 75, pp. 97-107, 2016.
[12] L. Kong, M. Zhao, X.Y. Liu, J. Lu, Y. Liu, M.Y. Wu W. Shu, “Surface coverage in sensor networks,” IEEE Trans. Parallel Distrib. Syst., vol. 25, no. 1, pp. 234-243, 2014.
[13] S. Kumar, T.H. Lai, and A. Arora, “Barrier coverage with wireless sensors,” Proc. ACM MobiCom’05, pp. 284-298, 2005.
[14] S. Lee, M. Younis, M. Lee, “Connectivity restoration in a partitioned wireless sensor network with assured fault tolerance,” Ad Hoc Netw., vol. 24, pp. 1-19, 2015.
[15] H. Li, Y. He, X. Cheng, H. Zhu, L. Sun, “Security and privacy in location for underwater sensor networks,” IEEE Commun. Mag., vol. 53, no. 11, pp. 56-62, 2015.
[16] Z. Liao, J. Wang, S. Zhang, J. Cao, G. Min, “Minimizing movement for target coverage and network connectivity in mobile sensor networks,” IEEE Trans. Parallel Distrib. Syst., vol. 60, no. 10, pp. 2773-2778, 2015.
[17] X. Liu, J. Cao, S. Tang, P. Guo, “A generalized coverage-preserving scheduling in WSNs: a case study in structural health monitoring,” Proc. IEEE INFOCOM’14, pp. 718-726, 2014.
[18] B. Liu, O. Dousse, J. Wang, and A. Saipulla, "Strong barrier coverage of wireless sensor networks," Proc. ACM MobiHoc’08, pp. 411-419, 2008.
[19] Z. Lu, W.W. Li, M. Pan, “Maximum lifetime scheduling for target coverage and data collection in wireless sensor networks,” IEEE Trans. Veh. Technol., vol. 64, no. 2, pp. 714-727, 2015.
[20] C. Maihofer, "A survey of geocast routing protocols," IEEE Commun. Surveys Tuts., vol. 6, no. 2, pp. 32-42, 2004.
[21] N. Patwari, J.N. Ash, S. Kyperountas, A.O. Hero, R.L. Moses, N.S. Correal, “Locating the nodes: cooperative localization in wireless sensor networks,” IEEE Signal Process. Mag., vol. 22, no. 4, pp. 54-69, 2005.
[22] J.H. Seok, J.Y. Lee, W. Kim, J.J. Lee, “A bipopulation-based evolutionary algorithm for solving full area coverage problems,” IEEE Sensors J., vol. 13, no. 12, pp. 4796-4807, 2013.
[23] W.Z. Song, R. Huang, M. Xu, B.A. Shirazi, R. LaHusen, “Design and deployment of sensor network for real-time high-fidelity volcano monitoring,” IEEE Trans. Parallel Distrib. Syst., vol. 21, no. 11, pp. 1658-1674, 2010.
[24] W.M. Tan, S.A. Jarvis, “Heuristic solutions to the target identifiability problem in directional sensor networks,” J. Netw. Comput. Appl., vol. 65, pp. 84-102, 2016.
[25] J. Tian, G. Wang, T. Yan, W. Zhang, “Detect smart intruders in sensor networks by creating network dynamics.” Comp. Netw., vol. 62, pp. 182-196, 2014.
[26] I. Vasilescu, K. Kotay, D. Rus, M. Dunbabin, P. Corke, “Data collection, storage, and retrieval with an underwater sensor network,” Proc. of ACM SenSys 05, San Diego, USA, 2-4 November, pp. 154-165, 2005.
[27] M. Vecchio, R. López-Valcarce, “Improving area coverage of wireless sensor networks via controllable mobile nodes: a greedy approach,” J. Netw. Comput. Appl., vol. 48, pp. 1-13, 2015.
[28] Z. Wang, H. Chen, Q. Cao, H. Qi, Z. Wang, “Fault tolerant barrier coverage for wireless sensor networks,” Proc. IEEE INFOCOM’14, pp. 1869-1877, 2014.
[29] Y.C. Wu, Q. Chaudhari, E. Serpedin, “Clock synchronization of wireless sensor networks,” IEEE Signal Process. Mag., vol. 28, no. 1, pp. 124-138, 2011.
[30] Q. Yang, S. He, J. Li, J. Chen, Y. Sun, “Energy-efficient probabilistic area coverage in wireless sensor networks,” IEEE Trans. Veh. Technol., vol. 64, no. 1, pp. 367-377, 2015.