無線感測器網路的應用，需要維持滿足需求的感測覆蓋率和網路聯通性，以取得環境資訊的完整性，但是感測元件由於能源提供的限制，容易喪失功能導致覆蓋漏洞和聯通性的問題。拓樸控制可以調整感測元件的能源消耗以維持拓樸聯接性，但是對於網路生命期的延長，基於資源的限制下效果是相當有限。失效無線元件的修補方法在本論文中探討，它是維持系統持續運作的主要方法。我們首先以逐步修復失效元件的策略，分析修補過程中元件相關參數如無線元件剩餘能量、數量以及派遣速度的可行性，結果顯示唯有適當條件可以達到修補的效益，維持系統的持續運作。其次探討一個分散式的漏洞修補方法，主要是經由漏洞的邊界節點以分散式的方法導引多餘動態感測器進行漏洞的修補，修補元件均勻分散地來自漏洞的周圍最近的距離，除了降低元件因為移動而產生的能源損耗，進而避免動態節點被過度集中使用。
當多數覆蓋漏洞出現於監視區域內時，漏洞修補的優先順序會影響系統的效能，因此進行修補工作之前的評估是必須的。漏洞本身對於系統效能的影響評估包含漏洞大小，漏洞距離和漏洞對於環境信息傳遞的阻礙程度等。我們將各別因素對於系統效能影響的程度賦予一個權值，經計算每個漏洞總權值後作為修補漏洞選擇及路徑決策的優先順序，其目的在於漏洞修補的同時提供拓僕控制有利的條件，降低環境資料傳遞過程中的時間延遲以維持服務品質，並確保系統的持續運作。

In wireless sensor network applications, it is a fundamental requirement to maintain essential sensing coverage and network connectivity for ensuring the successful operations of sensing environmental information and sending data to the backend center. However, owing to the limitation of energy supply of the sensor devices, it is unavoidable that the failures of sensor devices will result in coverage holes and topology disconnections. Topology control approaches can effectively adjust and balance the energy consumption of sensor devices. However, due to the limitations of energy resources, extending the lifetime of the network is very limited. The healing method for the failure of wireless sensors is discussed in this thesis. The healing approach is the main method we proposed to keep the system continuously working well, and make the wireless sensor network maintain a high sensing coverage rate and good topological connectivity. In this study, we use mathematical methods to analyze the relationship of healing parameters, such as residual energy of sensors, number of redundant nodes and dispatching speed, to gradually repair the failed nodes and analyze the feasibility of proposed strategies to confirm the parameters in the healing process and keep the system be well functioning. A distributed healing method is subsequently proposed in this thesis, which discusses the healing of coverage holes by the mobile sensor nodes that uniformly deployed in the sensing environment. The mobile sensors located around the boundary of a hole will be invited to heal the hole. This approach can reduce the movement distance of a healing device and thus the energy consumption can be also reduced.
When several coverage holes occur in the surveillance field, the priority of the holes to be healed may affect the efficiency of the healing process and the system. Thus, some relevant factors of the holes should be evaluated before the healing process. The evaluation performed in this study is focused on the impact degree of holes on system efficacy, which the factors involves the hole area, distance and influence of the data transmission. Impact degree of each factor on the system efficiency is assigned with a respective weight. After the calculation of the weight for each hole, the total value of weighted degree is used to decide the priority of selecting a hole to heal and the corresponding healing path. It aims to provide the appropriate conditions for topology control and reduce the time delay of data transmission in the wireless sensor network.

[1]. D. Wang, B. Xie and D.P. Agrawal, “Coverage and Lifetime Optimization of Wireless Sensor Networks with Gaussian Distribution”, IEEE Transactions on Mobile Computing, Vol. 7, issue 12, pp.1444-1458, 2008.
[2]. L.-C. Shiu, C.-Y. Lee and C.-S. Yang, “The Divide-and-Conquer Deployment Algorithm Based on Triangles for Wireless Sensor Networks”, IEEE Sensors Journal, Vol. 11, issue 3, pp. 781-790, March 2011.
[3]. F. Ye, Z. Zhong, J. Cheng, S. Lu and L. Zhang, “A Robust Conserving Protocol for Long-lived Sensor Networks”, In Proceedings of the 23rd International conference on Distributed Computing System, 2003.
[4]. M. Yang and J. Liu, “A Maximum Lifetime Coverage Algorithm Based on Linear Programming”, Journal of Information Hiding and Multimedia Signal Processing Vol. 5, No. 2, April, 2014
[5]. Y. Chen and Q. Zhao, “On the Lifetime of Wireless Sensor Networks”, IEEE communications letters, Vol. 9, No. 11, November, 2005.
[6]. I. Kang and R. Poovendran, “Maximizing Network Lifetime of Broadcasting Over Wireless Stationary Ad Hoc Networks”, Mobile Networks and Applications, pp. 879-896, 2005
[7]. A. Vahdat and D. Becker, “Epidemic Routing for Partially-Connected Ad Hoc Networks”, 2000
[8]. E. Jennings and C. Okino, “Topology control for efficient information dissemination in ad-hoc networks”, in International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS), 2002.
[9]. D.M. Blough, M. Leoncini, G. Resta and P. Santi, “The K-Neigh Protocol for Symmetric Topology Control in Ad Hoc Networks”, In Proceedings of the 4th ACM international symposium on Mobile ad hoc networking and computing, Annapolis, Maryland, USA, pp. 141-152, 2003.
[10]. L. C. Shiu, “The Robot Deployment Scheme for Wireless Sensor Networks in the Concave Region”, International Journal of Innovative Computing, Information and Control, Vol. 6, No. 7, pp. 2941-2953, August 2010.
[11]. R. Soua, T. T. ENSI, Tunisia L. Saidane and P. Minet, “Sensors Deployment Enhancement by a Mobile Robot in Wireless Sensor Networks”, Ninth International Conference on Networks (ICN), pp.121-126, April 2010.
[12]. T. W. Sung and C. S. Yang, “A cell-based sensor deployment strategy with improved coverage for mobility-assisted hybrid wireless sensor networks”, International Journal of Ad Hoc and Ubiquitous Computing, Vol. 5, No. 3, 2010.
[13]. G. Wang, G. Cao and T. LaPorta, “A Bidding Protocol for Deploying Mobile Sensors”, In Proceedings of the 11th IEEE International Conference on Network Protocols (ICNP’03), 2003.
[14]. W. R. Heinzelman, A. P. Chandrakasan and H. Balakrishnan, “Energy-Efficient Communication Protocol for Wireless Micro Sensor Networks”, in IEEE Proceedings of the Hawaii International Conference on System Sciences (HICSS), January 2000.
[15]. F. Xu, J. Heidemann and D. Estrin, “Geography-informed energy conservation for ad hoc routing”, in Proc. 7th Annual Int’sConf on Mobile Computing and Networking (MobiCom), Rome, Italy, July 2001.
[16]. M. Chatterjee, S. K. Das and D. Turgut, “WCA: A Weighted Clustering Algorithms for Mobile Ad Hoc Networks”, Cluster Computing, Vol.5, No. 2, 2002.
[17]. C. Bettstetter and S. König, “On the message and time complexity of a distributed mobility-adaptive clustering in wireless ad hoc networks”, in Proceedings European Wireless (EW), Florence, Italy, February 2002.
[18]. V. Kawadia and P. R. Kumar, “Power Control and Clustering in Ad Hoc Networks”, IEEE INFOCOM, 2003.
[19]. P. Chatterjee and N. Das, “Coverage Constrained Non-Uniform Node Deployment in Wireless Sensor Networks for Load Balancing”, Applications and Innovations in Mobile Computing (AIMoC), 2014.
[20]. D. Wang, B. Xie, and D. P. Agrawal, “Coverage and Life-time Optimization of Wireless Sensor Network with Gaussion Distribution”, Mobile Computing, IEEE Transactions, Vol. 7, issue 12, 2008.
[21]. C. F. Wang and C. C. Lee, “The optimization of sensor relocation in wireless mobile sensor networks”, Computer Communications, Vol. 33, issue 7, May 2009.
[22]. Y. Mao, X. Zhou and Y. Zhu, “An Energy-Aware Coverage Control Protocol for Wireless Sensor Network”, Proceedings of the 2008 IEEE International Conference on Information and Automation, June 2008.
[23]. T. Miyazaki, R. Kawano, T. Endo and D. Shitara, “A sensor Network for Surveillance of Disaster-hit Region”, ISWPC 2009 4th International Symposium on Wireless Pervasive Computing, 2009.
[24]. Mr. P. Dineshkumar, “CIP Based BOND for Wireless Sensor Networks”, Journal of Computer Applications (JCA) ISSN: 0974-1925, Vol. 6, Issue 3, 2013.
[25]. S. Funke, “Topological hole detection in wireless sensor networks and its applications”, DIALM­POMC'05, September 2005.
[26]. K. Li and Y. Wang, “Boundary Recognition in Sensor Networks by Building Relative Contours”, IEEE 34th Conference on Local Computer Networks (LCN), October 2009.
[27]. Z. Kang, H. Yu and Q. Xiong, “Detection and Recovery of Coverage Holes in Wireless Sensor Networks”, journal of networks, Vol. 8, No. 4, April 2013.
[28]. P. K. Sahoo, J. Z. Tsai, and H. L. Ke, “Vector Method based Coverage Hole Recovery in Wireless Sensor Networks”, Communication Systems and Networks (COMSNETS) Second International Conference, 2010.
[29]. G. Lin and G. Xue, “Steiner Tree Problem with Minimum Number of Steiner Points and Bounded Edge-Length,” Information Processing Letters, Vol. 69, pp. 53-57, 1999.
[30]. Sookyoung Lee and Mohamed F. Younis, “EQAR: Effective QoS-Aware Relay Node Placement Algorithm for Connecting Disjoint Wireless Sensor Subnetworks”, IEEE Transactions on Computers, Vol. 60, No. 12, December 2011.
[31]. S. Lee and M. Younis, “Optimized Relay Placement to Federate Segments in Wireless Sensor Networks”, IEEE journal on Selected Areas in Communications, Vol. 28, No. 5, June 2010.
[32]. A. Ghosh, “Estimating coverage holes and enhancing coverage in mixed sensor networks”, IEEE International Conference on Local Computer Networks, pp. 68-76, 2004.
[33]. G. Wang, G. Cao, P. Berman and T. L. Porta, “Bidding protocols for deploying mobile sensors”, IEEE Transactions on Mobile Computing, pp. 515-528, March 2007.
[34]. T. W. Sung and C. S. Yang, “Voronoi-based Coverage Improvement Approach for Wireless Directional Sensor Networks”, Journal of Network and Computer Applications, DOI: 10.1016/j.jnca.2013.07.003, 2013.
[35]. T. W. Sung and C. S. Yang, "Distributed Voronoi-based Self-redeployment for Coverage Enhancement in a Mobile Directional Sensor Network", International Journal of Distributed Sensor Networks, Vol. 2013, Article ID 165498, November 2013. DOI: 10.1155/2013/165498.
[36]. S. Babaie and S. S. Pirahesh, “Hole Detection for Increasing Coverage in Wireless Sensor Network Using Triangular Structure”, International Journal of Computer Science Issues (IJCSI), Vol. 9, Issue 1, no 2, January 2012.
[37]. P. Si, C. Wu, Y. Zhang, Z. Xia and L. Cheng, “A Hole Detection and Redeployment Strategy in Wireless Sensor Network”, Journal of Information & Computational Science, Vol. 8, pp. 2577-2585, 2011.
[38]. C. F. Huang and Y. C Tseng, “The Coverage Problem in a Wireless Sensor Network”, In Proc. of ACM WSNA’03, September 2003.
[39]. X. Li, D. K. Hunter and K. Yang, “Distributed Coordinate-free Hole Detection and Recovery”, In Proc. of Globecom ’06, November 2006.
[40]. N. P. Le, B. T. Quan, N. T. Hieu and N. K. Van. “Efficient approximation of routing holes in wireless sensor networks”, In ACM Proc. of the Second Symposium on Information and Communication Technology, 2011.
[41]. S. Zhou, M. Y. Wu and W. Shu, “Finding Optimal Placements for Mobile Sensors: Wireless Sensor Network Topology Adjustment”, IEEE 6th Circuits and Systems Symposium on Emerging Technologies: Mobile and Wireless Communication, pp. 529-532, February 2004.
[42]. X.H. Deng, C. G. Xu, F. Y. Zhao and Y. Liu, “Repair Policies of Coverage Holes Based Dynamic Node Activation in Wireless Sensor Networks”, IEEE/IFIP 8th International Conference (EUC), pp. 368-371, 2010.
[43]. G. Fletcher, X. Li, A. Nayak and I. Stojmenovic, “Randomized Robot-assisted Relocation of Sensors for Coverage Repair in Wireless”, Vehicular Technology Conference Fall (VTC 2010-Fall), 2010 IEEE 72nd, pp. 1-5, 2010.
[44]. L. C. Shiu, F. T. Lin, C. Y. Lee and C. S. Yang, “An Energy-Efficient Topology Construction Algorithm in Wireless Sensor Network”, 2nd International Conference on Machine Learning and Computer Science (IMLCS'2013), August 2013.
[45]. C. Y. Lee, L. C. Shiu, F. T. Lin and C. S. Yang, “Distributed topology control algorithm on broadcasting in wireless sensor network”, Journal of Network and Computer Applications 36, pp. 1186–1195, 2013.
[46]. A. Woo, T. Tong and D. Culler, “Taming the Underlying Challenges of reliable multihop routing in sensor networks,” Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, pp. 14–27, 2003.
[47]. D.J. Cook and S.K. Das, “Wireless Sensor Networks“, Technologies, Protocols, and Applications, John Wiley, New York, 2004.
[48]. G. Wang, G. Cao and T. La Porta, “Movement-Assisted Sensor Deployment”, IEEE Trans. Mobile Computing, Vol. 5, No. 6, pp. 640-652, June 2006.
[49]. M. R. Senouci, A. Mellouk and K. Assnoune, “Localized Movement-Assisted Sensor Deployment Algorithm for Hole Detection and Healing”, IEEE Transactions on Parallel and Distributed System, Vol. 25, No. 5, May 2014.
[50]. C. F. Huang, Y. C. Tseng and H. L. Wu, “Distributed protocols for ensuring both coverage and connectivity of a wireless sensor network, "ACM Trans. Sensor Networks, Vol. 3, No. 1, Article 5, March 2007.
[51]. D. Wang, B. Xie and D. P. Agrawal. “Coverage and Lifetime Optimization of Wireless Sensor Networks with Gaussian Distribution”, IEEE Transactions on Mobile Computing, Vol. 7, No. 12, pp. 1444-1458, December 2008.
[52]. C. F. Huang and Y. C. Tseng, “The Coverage Problem in a Wireless Sensor Network”, ACM Mobile Networks and Applications (MONET) special issue on Wireless Sensor Networks, Vol. 10, No. 4, pp. 519-528, August 2005.
[53]. T. W. Sung and C. S. Yang, “A Cell-based Sensor Deployment Strategy with Improved Coverage for Mobility-Assisted Hybrid Wireless Sensor Networks”, International Journal of Ad Hoc and Ubiquitous Computing, Vol. 5, No.3, pp. 189-198, 2010.
[54]. F. T. Lin, T. W. Sung, C. Y. Lee and C. S. Yang, “A Delivery Time-aware Hole Healing Scheme for Wireless Sensor Networks”, The Fifth International Conference on Ubiquitous Future Networks, Da Nang, Vietnam, July 2013.
[55]. T. W. Sung and C. S. Yang. “Voronoi-based Coverage Improvement Approach for Wireless Directional Sensor Networks”, Journal of Network and Computer Applications, 2013.
[56]. R. S. Chang and S. H. Wang, “Self-Deployment by Density Control in Sensor Networks”, IEEE Transactions on Vehicular Technology, Vol. 57, No. 3, May 2008.
[57]. 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, February 2008.
[58]. C. Y. Lee, L. C. Shiu, F. T. Lin and C. S. Yaug, “The fast scalable sensor efficiency measure in a hybrid sensor network”, Int. J. Ad Hoc and Ubiquitous Computing, Vol. 12, No. 2, 2013
[59]. J. Kanno, J. G. Buchart, R. R. Selmic and V. Phoha, “Detecting Coverage Holes in Wireless Sensor Networks”, 17th Mediterranean Conference on Control & Automation, Makedonia Palace, Thessaloniki, Greece, June 2009.
[60]. K. Y. Hsieh and J. P. Sheu, “Hole Detection and Boundary Recognition in Wireless Sensor Networks”, IEEE 20th International Symposium on Personal, Indoor and Mobile Radio Communications, Tokyo, Japan, September 2009.
[61]. Y. Wang, J. Gao and Joseph S.B. Mitchell, “Boundary recognition in sensor networks by topological methods”, MobiCom’06, Los Angeles, California, USA, September 2006.
[62]. N. Heo and P. K. Varshney, “Energy-Efficient Deployment of Intelligent Mobile Sensor Networks”, IEEE Trans. Systems, Man and Cybernetics Part A, Systems and Humans, Vol. 35, No. 1, pp. 78-92, 2005.
[63]. Y. Zou and K. Chakrabarty, “Sensor Deployment and Target Localization Based on Virtual Forces”, Proc. IEEE INFOCOM, pp. 1293-1303, 2003.
[64]. D. Johnson, D. Maltz and Y-C. Hu, “The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR)”, in The Internet Engineering Task Force (IETF), draft-ietf-manet-dsr-10.txt, July 2004.
[65]. G. J. Pottie, “Wireless Sensor Networks”, Proc. IEEE Information Theory Workshop, Killarney, Ireland, pp. 139-140, 1998.
[66]. I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, “Wireless sensor networks: a survey,” Computer Networks Journal, Vol. 38, pp.393-422, 2002.
[67]. D. Estrin, R. Govindan, J. Heidemann and S. Kumar, “Next century challenges: scalable coordination in sensor networks”, ACM MobiCom, pp. 263-270, 1999.
[68]. T. W. Sung and C. S. Yang, “An Adaptive Joining Mechanism for Improving the Connection Ratio of ZigBee Wireless Sensor Networks”, International Journal of Communication Systems, pp. 231-251, 2010.
[69]. S. Meguerdichian, F. Koushanfar, M. Potkonjak and M. B. Srivastava, “Coverage problems in wireless ad-hoc sensor networks”, Proc. INFOCOM 1383, pp. 1380-1387, 2003.
[70]. C. Zhang, Y. Zhang and Y. Fang, “A Coverage Inference Protocol for Wireless Sensor Networks”, IEEE Transactions on Mobile Computing, Vol. 9, No. 6, pp. 850-864, June 2010.
[71]. Y. Bejerano, “Coverage Verification without Location Information”, IEEE transactions on mobile computing, 2011.
[72]. G. Lin and G. Xue, “Steiner Tree Problem with Minimum Number of Steiner Points and Bounded Edge-Length”, Information Processing Letters, Vol. 69, pp. 53-57, 1999.