淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


系統識別號 U0002-2707201617301600
中文論文名稱 無線感測網路下防禦線覆蓋相關問題之研究
英文論文名稱 Barrier coverage related problem in wireless sensor networks
校院名稱 淡江大學
系所名稱(中) 資訊工程學系全英語碩士班
系所名稱(英) Master’s Program, Department of Computer Science and Information Engineering (English-taught program
學年度 104
學期 2
出版年 105
研究生中文姓名 王辰維
研究生英文姓名 Chen-Wei Wang
學號 603780023
學位類別 碩士
語文別 英文
口試日期 2016-07-05
論文頁數 45頁
口試委員 指導教授-鄭建富
委員-陳建志
委員-潘孟鉉
中文關鍵字 無線感測網路  覆蓋問題  目標物防禦線覆蓋 
英文關鍵字 wireless sensor networks  coverage problem  target-barrier coverage 
學科別分類 學科別應用科學資訊工程
中文摘要 覆蓋問題是一項重要的研究議題於無線感測網路之中。在本論文中,我們探討了一個新型態的覆蓋問題,我們稱之為目標物防禦線覆蓋問題。目標物防禦線覆蓋問題的目標是在目標物周遭建立一條連續的環狀防禦線,並且根據不同的應用,目標物防禦線與目標物將會有不同的距離限制。當有入侵者入侵時,此距離限制將有助於提供足夠的反應時間。目標物防禦線非常適用於軍事要塞的監控、校園安全的監控、生態保護區的監控等等。我們也透過實驗模擬分析目標物防禦線在不同的目標物數量下及不同的距離限制設定下其所需要的感測器成員數量及控制訊息交換量上的變化。
英文摘要 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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2021-08-02公開。
  • 同意授權瀏覽/列印電子全文服務,於2021-08-02起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2486 或 來信