# An Efficient Distributed Coverage Hole Detection Protocol for Wireless Sensor Networks
## 4 Proposed Hole Detection Protocol
### Determination of CP
### Detection of Coverage Holes

In this section, the CIP are organized to detect the hole based on their location either above or below the line connecting to the location of any two neighboring sensors. The points that are below the connecting lines form a set of points as set \(CIP_{L}\), whereas the points above the line form a set \(CIP_{U}\). Then, in each set, those points are arranged in a clockwise fashion to check whether the nature of the hole is bounded or unbounded. By arranging the points either in the set \(CIP_{L}\) or \(CIP_{U}\) in the clockwise direction, a bounded coverage hole is detected if all elements of those sets form a loop, _i.e._, if the initial and terminal points are the same. However, an unbounded coverage hole is detected, if all elements of a set do not form a loop. It is to be noted that whether the coverage hole is bounded or unbounded is determined by the sensors that enclose them. The DCHD algorithm is run in each node to find the CIP and to detect the hole in collaboration with its one-hop neighbors. Once the hole detection procedure is terminated by the sensors, the information is transmitted to the sink by the sensor that has initiated this procedure. It could be possible that a node may be adjacent to more than one hole. In this case, the hole does not prevent the sensor from sending data to the sink. The node has to send information about the presence of both holes along with the nature of the holes to the sink. In our protocol, it is assumed that coverage holes are created due to the death of the nodes, and the role of the DCHD protocol is to detect the holes instead of detecting whether a node is dead or not. However, it is obvious that a node cannot have sensing overlapping with its one-hop neighbors, if a node is dead, and therefore, CIP is calculated and the hole detection done in the network. In order to explain the detection of the coverage hole, let us take an example as shown in Figure 4. As discussed in the above subsection, the CIP are classified into two different sets based on their position. After calculating the position of each CIP either above or below the lines connecting to the centers of each sensing disc, two sets of points can be classified as sets \(CIP_{L}\) and \(CIP_{U}\). Thus, for the sensors \(S_{1}\sim S_{10}\), the set \(CIP_{L}=\{p_{1},p_{2},p_{3},p_{4},p_{5},p_{6},p_{7},p_{8},p_{9},p_{10},p_{1}\}\), where \(p_{1}\) is revisited, which implies that these points can form a loop, and therefore, a bounded coverage hole exists in between those sensors. Similarly, for the sensors \(S_{2}\), \(S_{13}\), \(S_{3}\), \(S_{4}\), \(S_{5}\) and \(S_{15}\), the set \(CIP_{U}=\{p_{11},p_{12},p_{13},p_{14},p_{15},p_{16}\}\), where no point is revisited, which implies that though there is a coverage hole, the hole must be unbounded. It is to be noted that as shown in Figure 4, by connecting sensors \(S_{17}\), \(S_{18}\), \(S_{6}\), \(S_{8}\) and \(S_{7}\), though those connecting lines can form a loop, no CIP is localized below those lines. This implies that all points of intersection between those sensors below the lines are detected as CP, and therefore, no coverage hole can be detected there. Taking all of the phases of the coverage hole detection procedure, the complete flow of the DCHD protocol can be shown as in Figure 5, and the DCHD algorithm is given in Algorithm. 4. Figure 5: Flow chart of the complete coverage hole detection procedure.