臺灣博碩士論文加值系統

無線感測器網路通常佈署在人類不易到達或接觸到的地區，無法避免天災或物理損壞等原因造成的節點死亡及所產生的覆蓋漏洞。由於此現象會影響監測區域的完整性，所以覆蓋漏洞修復一直是重要的研究議題。因此，本論文提出一個覆蓋漏洞修復策略(Coverage Hole Repair Mechanism, CHRM)。此策略分為兩個部分，分別為使所有節點分佈更為均勻的全域佈建方法，以及因應突發性節點死亡的區域覆蓋率修復方法。
針對覆蓋漏洞形狀較難預測的多顆感測器節點同時死亡時情況，本論文提出一種利用基因演算法修復覆蓋漏洞方法(Genetic Algorithm Coverage hole Repair mechanism, GACR)。利用覆蓋漏洞區域內的覆蓋率、所有參與修復節點的總移動距離以及最低剩餘能量作為適應函數的參考指標，結合GA的演化機制找出所有參與修復節點的最佳移動方式。因為考慮到參與修復節點的剩餘能量，所以可以改善低剩餘能量的參與修復節點移動距離過長或是在移動過程中因能量耗盡而死亡的情形。除此之外，對於傳統全域修復方法未考量節點剩餘能量的缺點，本論文提出一種全域佈建方法VVF_GA(Vertex Virtual Forces strategy with Genetic Algorithm)透過基因演算法考量節點的剩餘能量，藉此選出一組適合參與修復的節點集合，從而避免節點在移動過程中出現能量耗盡的情形。
最後，為了驗證CHRM方法的有效性，本論文分別對區域覆蓋率修復機制GACR以及VVF_GA+GACR的演算法組合進行隨機多顆節點死亡場景模擬。模擬結果顯示，考慮到多顆節點死亡的情況下，GACR和DCHR、NIBP_VVF以及未考慮到多顆節點死亡的NIFP相比較，在維持90%以上的網路覆蓋率時間、節點的總移動距離以及最低節點剩餘能量等指標評估下，GACR均有較優異表現。而CHRM和VVF(Vertex Virtual Forces strategy)+GACR的演算法組合相比較，CHRM可以有效減少修復過程中不必要的節點移動距離，並且更能適應異質初始能量的節點。

Wireless sensor networks are usually deployed in areas that are difficult for humans to reach or contact, and cannot avoid node deaths (malfunctions) and coverage holes caused by natural disasters or physical damage. Since this phenomenon affects the integrity of the monitoring area, the coverage hole repair has always been an important research topic. Therefore, this thesis proposes a Coverage Hole Repair Mechanism (CHRM). This strategy consists of two folds, a global deployment method that makes all nodes more evenly distributed, and a regional coverage repair method that responds to sudden node deaths.
In view of the fact that the shapes of coverage holes are difficult to predict when simultaneously multiple sensor nodes die, this thesis proposes a Genetic Algorithm Coverage Hole Repair Mechanism (GACR). Using the coverage ratio in the coverage area, the total moving distance and lowest residual energy of all participating repair nodes as reference indicators of the fitness function, the proposed method uses GA to find the best moving policy of all participating repair nodes by way of the evolution mechanism. Since the method considers the remaining energies of participating repair nodes, it is possible to improve the situation in which the low residual energy node participates in the repair to move too long or to die due to energy exhaustion during the movement. In addition, as the traditional global repair method does not consider the shortcomings of the remaining energy of the node, this thesis proposes a Vertex Virtual Forces strategy with Genetic Algorithm (VVF_GA) to take into account the residual energy of the node in genetic algorithm. The selected set of nodes is thus suitable for involving in the repair and avoids the situation that the node runs out of energy during the movement.
Finally, in order to verify the effectiveness of the CHRM method, this thesis simulates the random multi-node death scenario of the regional coverage repair mechanism GACR and the VVF_GA+GACR algorithm combination respectively, and compares the performance with other coverage hole repair methods. The simulation results show that considering the multiple node deaths the GACR is superior to DCHR, NIBP_VVF, and NIFP that do not take into account the death of multiple nodes. In the metrics of maintaining more than 90% of network coverage time, total moving distance of nodes, and minimum node residual energy, the GACR outperforms. Moreover, comparing with CHRM with the combination of VVF+GACR algorithm, CHRM can effectively reduce unnecessary node movement distance during repair and is more suitable for wireless sensor networks with heterogeneous initial node energies.

摘　要 i
ABSTRACT iii
誌 謝 v
目錄 vi
表目錄 viii
圖目錄 ix
第一章 緒論 1
1.1研究背景 1
1.2研究動機及目的 2
1.3文獻探討 2
1.4 論文架構 5
1.5 論文貢獻 6
第二章 無線感測器網路覆蓋率維護技術與基因演算法介紹 7
2.1前言 7
2.2無線感測器網路覆蓋率維護技術 7
2.3 基因演算法 12
2.3.1 基因演算法 12
2.3.2 改良式基因演算法 17
2.4 結語 17
第三章 全域佈建與區域覆蓋率修復策略設計 19
3.1 前言 19
3.2 CHRM介紹 19
3.3 GACR設計 21
3.3.1 GACR介紹 23
3.3.2 GACR適應函數設計 24
3.3.3 基因演算法突變率改善 26
3.4 VVF_GA介紹 31
3.4.1 改良式VVF 32
3.4.2 VVF_GA設計 33
3.5 結語 37
第四章 CHRM模擬驗證與分析 39
4.1 前言 39
4.2 區域覆蓋率修復模擬與分析 39
4.3 全域佈建模擬與分析 46
4.4 全域佈建模擬複雜度分析 54
4.5 結語 56
第五章 結論與未來研究方向 58
5.1 結論 58
5.2 未來方向 58
參考文獻 60

1.J. M. Kahn, R. H. Katz and K. S. J. Pister, "Next century challenges: mobile networking for smart dust," Proceedings of the International Conference on Mobile Computing and Networking, 1999, pp. 271-278.
2.B. Arunachalam, D. S. Arjun, R. B. B. Prahlada, H. Pasupuleti and V. Dwarakanath, "Sensing service framework for climate alert system using WSN-cloud infrastructure," 2015 9th International Conference on Sensing Technology (ICST), 2015, pp. 671-676.
3.E. Aguirre, P. Lopez-Iturri, L Azpilicueta, A. Redondo, J. J. Astrain, J. Villadangos and A. Bahillo, "Design and implementation of context aware applications with wireless sensor network support in urban train transportation environments," IEEE Sensors Journal, vol. 17, no. 1, 2017, pp. 169-178.
4.M. Brandi, J. Grabner, K. Kellner, F. Seifert, J. Nicolics, S. Grabner and G. Grabner, "A low-cost wireless sensor system and its application in dental retainers," IEEE Sensors Journal, vol. 9, no. 3, 2009, pp. 255-262.
5.Q. Luo, S. Li, J. Wu and Y. Sun, "Energy-saving coverage algorithm of WSN," 2009 Chinese Control and Decision Conference, Guilin, 2009, pp. 3622-3627.
6.B. Khalifa, Z. Al Aghbari, A. M. Khedr and J. H. Abawajy, "Coverage hole repair in WSNs using cascaded neighbor intervention," IEEE Sensors Journal, vol. 17, no. 21, 2017, pp. 7209-7216.
7.J. Wang, "The placement scheme for static nodes in a circular WSN area based on the analysis of density and energy," 2010 International Conference on Multimedia Information Networking and Security, Nanjing, Jiangsu, 2010, pp. 208-212.
8.Y. C. Wang, C. C. Hu and Y. C. Tseng, "Efficient placement and dispatch of sensors in a wireless sensor network," IEEE Transactions on Mobile Computing, vol. 7, no. 2, 2008, pp. 262-274.
9.M. M. Singh, A. Singh and J. K. Mandal, "Preventing node replication attack in static wireless sensor networks," Proceedings of 3rd International Conference on Reliability, Infocom Technologies and Optimization, Noida, 2014, pp. 1-5.
10.M. Abo-Zahhad, S. M. Ahmed, N. Sabor and S. Sasaki, "Utilisation of multi-objective immune deployment algorithm for coverage area maximisation with limit mobility in wireless sensors networks," IET Wireless Sensor Systems, vol. 5, no. 5, 2015, pp. 250-261.
11.L. Wang and S. S. Kulkarni, "Sacrificing a little coverage can substantially increase network lifetime," 2006 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks, Reston, VA, 2006, pp. 326-335.
12.S. Ganeriwal, A. Kansal and M. B. Srivastava, "Self aware actuation for fault repair in sensor networks," IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA '04. 2004, New Orleans, LA, USA, 2004, pp. 5244-5249.
13.D. Tian and N. D. Georganas, "A coverage-preserving node scheduling scheme for large wireless sensor networks," ACM Int. Workshop Wireless Sen. Netw. Appl., 2002, pp. 32-41.
14.G. Vaishali and M. K. Nighot, "An efficient ACO scheme for mobile-sink based WSN," 2016 International Conference on Inventive Computation Technologies (ICICT), Coimbatore, 2016, pp. 1-5.
15.X. Chen, L. Wang and Y. Zhan, "Detection and revocation of replica nodes in WSN by using mobile sink," 2012 8th International Conference on Wireless Communications, Networking and Mobile Computing, Shanghai, 2012, pp. 1-4.
16.Y. Gu, L. Zhao, D. Jing and J. Guo, "A novel routing protocol for mobile nodes in WSN," 2012 International Conference on Control Engineering and Communication Technology, Liaoning, 2012, pp. 624-627.
17.A. Soundarya and V. Santhi, "An efficient algorithm for coverage hole detection and healing in wireless sensor networks," 2017 1st International Conference on Electronics, Materials Engineering and Nano-Technology (IEMENTech), Kolkata, 2017, pp. 1-5.
18.X. Deng, C. Xu, F. Zhao and Y. Liu, "Repair policies of coverage holes based dynamic node activation in wireless sensor networks," 2010 IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, Hong Kong, 2010, pp. 368-371.
19.Erdun Zhao, Juan Yao, Hao Wang and Yating Lv, "A coverage hole detection method and improvement scheme in WSNs," 2011 International Conference on Electric Information and Control Engineering, Wuhan, 2011, pp. 985-988.
20.X. Liu, Y. Feng, Q. Lv and T. Zhao, "Cascaded movement strategy for repairing coverage holes in wireless sensor networks," 2011 International Conference of Information Technology, Computer Engineering and Management Sciences, Nanjing, Jiangsu, 2011, pp. 108-111.
21.B. A. White, A. Tsourdos, I. Ashokaraj, S. Subchan and R. Zbikowski, "Contaminant cloud boundary monitoring using network of UAV sensors," IEEE Sensors Journal, vol. 8, no. 10, 2008, pp. 1681-1692.
22.J. Grigulo and L. B. Becker, "Experimenting Sensor Nodes Localization in WSN with UAV Acting as Mobile Agent," 2018 IEEE 23rd International Conference on Emerging Technologies and Factory Automation (ETFA), Turin, 2018, pp. 808-815.
23.G. Subramanian, "Application of WSN in UAV," 2018 3rd International Conference for Convergence in Technology (I2CT), Pune, 2018, pp. 1-5.
24.S. Mahmoud, I. Jawhar, N. Mohamed and Jie Wu, "UAV and WSN softwarization and collaboration using cloud computing," 2016 3rd Smart Cloud Networks & Systems (SCNS), Dubai, 2016, pp. 1-8.
25.Huiyong Wang, Minglu Zhang and Jingyang Wang, "Design and implementation of an Emergency Search and Rescue System based on mobile robot and WSN," 2010 2nd International Asia Conference on Informatics in Control, Automation and Robotics (CAR 2010), Wuhan, 2010, pp. 206-209.
26.S. János and I. Matijevics, "Implementation of potential field method for mobile robot navigation in greenhouse environment with WSN support," IEEE 8th International Symposium on Intelligent Systems and Informatics, Subotica, 2010, pp. 319-323.
27.M. Chovanec and P. Šarafín, "Real-time schedule for mobile robotics and WSN aplications," 2015 Federated Conference on Computer Science and Information Systems (FedCSIS), Lodz, 2015, pp. 1199-1202.
28.Y. Zou and K. Chakrabarty, "Sensor deployment and target localization based on virtual forces," IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No.03CH37428), San Francisco, CA, vol. , 2003, pp. 1293-1303.
29.T. Lin, H. A. Santoso and K. Wu, "Global sensor deployment and local coverage-aware recovery schemes for smart environments," IEEE Transactions on Mobile Computing, vol. 14, no. 7, 2015, pp. 1382-1396.
30.H. Mahboubi and A. G. Aghdam, "Distributed deployment algorithms for coverage improvement in a network of wireless mobile sensors: relocation by virtual force," IEEE Transactions on Control of Network Systems, vol. 4, no. 4, 2017, pp. 736-748.
31.S. T. Hasson and A. A. R. Finjan, "A suggested angles-based sensors deployment algorithm to develop the coverages in WSN," 2018 2nd International Conference on Inventive Systems and Control (ICISC), Coimbatore, 2018, pp. 547-552.
32.A. M. Khedr, W. Osamy and A. Salim, "Distributed coverage hole detection and recovery scheme for heterogeneous wireless sensor networks," Computer Communications, vol. 124, no. 21, 2018, pp. 61-75.
33.https://en.wikipedia.org/wiki/Smallest-circle_problem, accessed on July 2019
34.https://en.wikipedia.org/wiki/Voronoi_diagram, accessed on July 2019
35.R. Sujee and K. E. Kannammal, "Energy efficient adaptive clustering protocol based on genetic algorithm and genetic algorithm inter cluster communication for wireless sensor networks," 2017 International Conference on Computer Communication and Informatics (ICCCI), Coimbatore, 2017, pp. 1-6.
36.C. K. Ng, C. H. Wu, W. H. Ip and K. L. Yung, "A smart bat algorithm for wireless sensor network deployment in 3-D environment," IEEE Communications Letters, vol. 22, no. 10, 2018, pp. 2120-2123.
37.D. S. Deif and Y. Gadallah, "An ant colony optimization approach for the deployment of reliable wireless sensor networks," IEEE Access, vol. 5, 2017, pp. 10744-10756.
38.Y. Zhou, N. Wang and W. Xiang, "Clustering hierarchy protocol in wireless sensor networks using an improved PSO algorithm," IEEE Access, vol. 5, 2017, pp. 2241-2253.
39.https://zh.wikipedia.org/wiki/%E6%97%85%E8%A1%8C%E6%8E%A8%E9%94%80%E5%91%98%E9%97%AE%E9%A2%98, accessed on July 2019
40.P. Huang, L. Xu, Z. Kang, C. Liu and F. Lin, "GA-based sweep coverage scheme in WSN," 2016 7th International Conference on Cloud Computing and Big Data (CCBD), Macau, 2016, pp. 254-259.
41.J. G. Moreno-Torres, X. Llorà and D. E. Goldberg, "Binary representation in gene expression programming: Towards a better scalability," 2009 Ninth International Conference on Intelligent Systems Design and Applications, Pisa, 2009, pp. 1441-1444.
42.M. Kubicki and D. Figurowski, "An introduction to a novel crossover operator for real-value encoded genetic algorithm: Gaussian crossover operator," 2018 International Interdisciplinary PhD Workshop (IIPhDW), Swinoujście, 2018, pp. 85-90.
43.P. Hartono, S. Hashimoto and M. Wahde, "Labeled-GA with adaptive mutation rate," Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No.04TH8753), Portland, OR, USA, 2004, pp. 1851-1858.
44.H. Komari Alaei and M. Khademi, "Partial mutation in GA a novel proposed algorithm to solving complex problem," 2010 International Conference on Intelligent Computing and Cognitive Informatics, Kuala Lumpur, 2010, pp. 304-307.
45.C. Chen and J. Luo, "Hybrid optimal control of robot motor based on improved genetic algorithm and fuzzy logic," 2017 International Conference on Robotics and Automation Sciences (ICRAS), Hong Kong, 2017, pp. 53-57.
46.S. M. Kwon and J. S. Kim, "Coverage ratio in the wireless sensor networks using Monte Carlo simulation," 2008 Fourth International Conference on Networked Computing and Advanced Information Management, Gyeongju, 2008, pp. 235-238.
47.https://en.wikipedia.org/wiki/Sigmoid_function, accessed on July 2019