# An Efficient Distributed Coverage Hole Detection Protocol for Wireless Sensor Networks
## 4 Proposed Hole Detection Protocol
### Determination of CP
```
1:Input:
2:\(N_{i}\): Set of all sensing neighbors of node \(S_{i}\);
3:\(CIP_{L}\): Set of CIP below the connecting line;
4:\(CIP_{U}\): Set of CIP above the connecting line;
5:Output:
6: Type of coverage holes;
7:Detection of coverage holes:
8: Select any sensor \(S_{i}\);
9: Select another sensor \(S_{j}\) from the set \(N_{i}\);
10: Find points of intersection between \(S_{i}\) and \(S_{j}\); Let it be \(P_{ij}\) and \(P_{ji}\);
11: Select another sensor \(S_{k}\) from the set \(N_{i}\);
12: Check \(P_{ij}\) and \(P_{ji}\) are covered by \(S_{k}\) or not;
13:if (\(P_{ij}\) and \(P_{ji}\) are not covered by \(S_{k}\))
14:\(\{\)
15: Assign \(CIP_{ij}\gets P_{ij}\), \(CIP_{ji}\gets P_{ji}\);
16: Execute Algorithm 3;
17: Function call: Hole_Type();
18:\(\}\)
19:if (\(P_{ij}\mid\mid P_{ji}\) is a CIP) (ex: Let \(P_{ij}\) be a CIP)
20:\(\{\)
21: Assign \(CIP_{ij}\gets P_{ij}\);
22: Execute Algorithm 3;
23: Function call: Hole_Type();
24:\(\}\)
25:if (both \(P_{ij}\) and \(P_{ji}\) are covered)
26:\(\{\)
27: Assign \(CP\gets P_{ij}\) and \(P_{ji}\);
28: The network is fully covered;
29: Terminate the hole detection procedure;
30:\(\}\)
31:Hole_Type0
32: Arrange all points of \(CIP_{L}\) and \(CIP_{U}\) in clock-wise;
33:if (initial point == terminal point)
34: Hole is bounded;
35: Else: Hole is unbounded;
```

**Algorithm 4** Distributed coverage hole detection (DCHD) procedure. ### Construction of Covered and Uncovered Arcs

As discussed in the previous subsections, the presence of a coverage hole is detected by using the critical intersection points and after knowing their locations. However, it is essential to know the shape of the bounded or unbounded coverage holes. In this section, we propose a mechanism for how to get the shape of the hole by constructing covered and uncovered arcs. As shown in Figure 6, let \(S_{2}\), \(S_{3}\), \(S_{4}\), \(S_{5}\) and \(S_{6}\) be the sensing neighbors of the node \(S_{1}\). Here, \(p_{1}\), \(p_{2}\), \(p_{3}\) and \(p_{4}\) are the CIP of the sensor \(S_{1}\). As discussed in the above subsection, it can be determined that \(p_{1}\) and \(p_{2}\) are located at one side of its sensing disc, whereas \(p_{3}\) and \(p_{4}\) are located at the other side of the sensing disc. It is to be noted that the location of all CIP and the position of each sensor are known. Since the locations of the one-hop neighbors of a sensor are known, we can connect the location of one sensor to another. Thus, as shown in Figure 6, first, the lines \(\overline{S_{1}S_{2}}\), \(\overline{S_{1}S_{3}}\),..., \(\overline{S_{1}S_{6}}\) are drawn, and the arcs are constructed as follows. After locating the CIP, we have to construct the arcs along the circumference of the sensing disc of the sensor \(S_{1}\). For this reason, first consider the points \(p_{1}\)\(p_{2}\) to draw the vectors \(\overrightarrow{S_{1}p_{1}}\) and \(\overrightarrow{S_{1}p_{2}}\) from the position of the sensor \(S_{1}\). Let \(\alpha\) be the angle between these two vectors, which can be calculated using the formula \(\alpha=\arccos\left(\frac{\overrightarrow{S_{1}p_{1}}\bullet\overrightarrow{S_ {1}p_{2}}}{\overrightarrow{\|S_{1}p_{1}\|}\|S_{1}p_{2}\|}\right)\). Then, the arc length of the arc can be calculated as \(\widehat{p_{1}p_{2}}=\alpha\times R_{s}\). Thus, the arcs \(\widehat{p_{2}p_{3}}\), \(\widehat{p_{3}p_{4}}\) and \(\widehat{p_{4}p_{1}}\) are calculated. However, if any of those arcs intersect with the \(\overrightarrow{S_{1}S_{2}}\), \(\overrightarrow{S_{1}S_{3}}\),..., \(\overrightarrow{S_{1}S_{6}}\), they are considered as _covered arcs_ and, therefore, are omitted for constructing the coverage hole. Based on this rule, as shown in the figure, only arcs \(\widehat{p_{1}p_{2}}\) and \(\widehat{p_{3}p_{4}}\) are considered as the _uncovered arcs_ and are separated, as they do not intersect any of those connecting lines. Since arcs \(\widehat{p_{1}p_{2}}\) and \(\widehat{p_{3}p_{4}}\) are at different sides of the sensing disc, they are separated into two sets.