Localized Movement-Assisted Sensor Deployment Algorithm for Hole Detection and Healing

One of the fundamental services provided by a wireless sensor network (WSN) is the monitoring of a specified region of interest (RoI). Considering the fact that emergence of holes in the RoI is unavoidable due to the inner nature of WSNs, random deployment, environmental factors, and external attacks, assuring that the RoI is completely and continuously covered is very important. This paper seeks to address the problem of hole detection and healing in mobile WSNs. We discuss the main drawbacks of existing solutions and we identify four key elements that are critical for ensuring effective coverage in mobile WSNs: 1) determining the boundary of the RoI, 2) detecting coverage holes and estimating their characteristics, 3) determining the best target locations to relocate mobile nodes to repair holes, and 4) dispatching mobile nodes to the target locations while minimizing the moving and messaging cost. We propose a lightweight and comprehensive solution, called holes detection and healing (HEAL), that addresses all of the aforementioned aspects. The computation complexity of HEAL is O(upsilon(2)), where v is the average number of 1-hop neighbors. HEAL is a distributed and localized algorithm that operates in two distinct phases. The first identifies the boundary nodes and discovers holes using a lightweight localized protocol over the Gabriel graph of the network. The second treats the hole healing, with novel concept, hole healing area. We propose a distributed virtual forces-based local healing approach where only the nodes located at an appropriate distance from the hole will be involved in the healing process. Through extensive simulations we show that HEAL deals with holes of various forms and sizes, and provides a cost-effective and an accurate solution for hole detection and healing.