# An Efficient Distributed Coverage Hole Detection Protocol for Wireless Sensor Networks
## 2 Related Work  
Hole detection is one of the important research issues in WSNs [10], which can be classified as coverage holes, routing holes, jamming holes, sink/black holes and worm holes. Due to the random deployment of the sensors, some part of the monitoring region is not covered by the sensing disc of a sensor, which is called a coverage hole. The studies on coverage can be divided into two categories. The first category comprises probabilistic approaches for calculating the required node density for ensuring appropriate coverage [17], though these studies do not prove the hole detection solutions. The second category utilizes computational geometry approaches to discover the coverage holes. In this category, the detected holes problem, which is also called the connected coverage boundary detection problem, is addressed in [18]. Such a connected coverage boundary detection problem is classified into polygon-based and perimeter-based approaches. In the polygon-based approach, a Voronoi diagram is used for the coverage boundary detection. Briefly speaking, the VP of a node set \(V\) is the partition of the Euclidean space into polygons, called Voronoi polygons (VPs). According to the closeness property, if some portion of the VP is not covered by the nodes inside the VP, it will not be covered by any other node, which implies a coverage hole. However, it has been shown that the VPs of the boundary nodes cannot be locally computed, and the VP-based approach is not a real localized solution. The paper in [18] proposes a localized Voronoi polygon (LVP) to find the holes locally. The first localized boundary node detection algorithm for the perimeter-based approach is proposed in [19], which is based on the information about the coverage of the perimeter of each node's sensing disk. According to the perimeter-based approach, if a node \(i\) is the boundary node that exists at one point \(j\) on the circle, then point \(j\) is not covered by any one of the node \(i\)'s neighborhood sensors. The paper [20] proposes to check the intersection point by the node \(i\) and \(i\)'s neighborhood sensors not covered by other sensors. In [21], a coverage configuration protocol (CCP) based on the perimeter-based approach is presented to calculate the degree of the intersection points and to use this degree of intersection to maintain the \(k\)-coverage. In this paper, we define these special intersection points as hole points. However, the perimeter-based approach has two flaws. First, each node needs to check the positions and status of all of its neighbors, which is inefficient when the sensor nodes are densely deployed, and every time when a node dies, all of its neighbors need to check the coverage of their perimeters to update the existing coverage. Secondly, this approach is not efficient for using this information only to check the boundary nodes. In [22], the authors propose algorithms to construct two sets \(P\) and \(Q\) using the perimeter-based approach, where \(P\) is the end point set and \(Q\) is the edge point set, and the hole exists if two consecutive end points are found in the counterclockwise direction. However, it has two problems. The first problem is it needs more memory to store this information, and the second problem is it cannot solve the flaws of the perimeter-based approach. In [23], the authors propose a vector method to use the perimeter-based approach to group the hole points and to recover the coverage holes. Though they use the hole point information to recover the coverage holes, they do not consider the redundant sensors to recover them. The formation of holes in the target field is quite common and is unavoidable due to the nature of the WSN and random deployment. This is very important to ensure that the target field is completely and continuously covered. In [24], the authors propose an approach called the hybrid hole detection and healing (HHDH) protocol that detects and heals the coverage holes effectively with minimum sensor movements.