# An Efficient Distributed Coverage Hole Detection Protocol for Wireless Sensor Networks
## 4 Proposed Hole Detection Protocol
### Determination of CP  
It is assumed that each node knows its _sensing neighbors set_ (\(N\)). Taking the set of sensing neighbors set \(N\) as the input, each sensor can find out if the point of intersection with its one-hop neighbor is a CP or not. The details of the procedure for calculating a point as CP or not is given in Algorithm 2. ```
1:Input:\(N_{i}\): Set of all sensing neighbors of node \(i\);
2:Output:\(C_{i}\): Set of covered points of node \(i\);
3:Calculation Procedure of CP set:
4: Select any node \(i\) randomly;
5: Initialize \(C_{i}=\phi\);
6:if(\(N_{i}\
eq\phi\))
7:\(\{\)
8: Scan all members of \(N_{i}\);
9:if(\(i\) is a non-border sensor)
10:\(\{\)
11: Find intersection point of node \(i\) with \(j\), which is one member of \(N_{i}\);
12: Check if the point \(p\) is covered by a sensor \(k\), which is another member of \(N_{i}\) and \(j\
eq k\);
13:if(\(p\) is covered by \(k\))
14:\(p\) is a CP;
15:else
16:\(\{\)
17:\(p\) is a CIP or a border point;
18: Execute Algorithm 1 to find CIP;
19:\(\}\)
20:\(\}\)
21:else
22:\(\{\)
23:\(i\) is a border sensor;
24: Find point of intersection \(b\) of node \(i\) with border line of the monitoring region \(R\);
25: Check if point \(b\) is covered by any neighbors of \(i\);
26:if(point \(b\) is covered)
27:\(b\) is a CP;
28:else
29: Execute Algorithm 1 to find CIP;
30:\(\}\)
31:\(\}\)
32:else
33:\(i\) is an isolated sensor;
34: \begin{table}
\begin{tabular}{c c c} \hline \hline
**Node** & **Neighbors** & **Corresponding CIP** \\ \hline \multirow{3}{*}{\(S_{7}\)} & \(S_{6}\) & \(P_{6}\), \(P_{21}\) \\  & \(S_{12}\) & \(P_{22}\) \\  & \(S_{8}\) & \(P_{7}\) \\ \hline \multirow{3}{*}{\(S_{8}\)} & \(S_{7}\) & \(P_{7}\) \\  & \(S_{12}\) & \(P_{25}\) \\  & \(S_{9}\) & \(P_{8}\), \(P_{26}\) \\ \hline \multirow{3}{*}{\(S_{9}\)} & \(S_{8}\) & \(P_{8}\), \(P_{26}\) \\  & \(S_{13}\) & \(P_{27}\) \\  & \(S_{10}\) & \(P_{9}\) \\ \hline \multirow{3}{*}{\(S_{10}\)} & \(S_{1}\) & \(P_{10}\) \\  & \(S_{9}\) & \(P_{9}\) \\ \cline{1-1}  & \(S_{11}\) & No \\ \hline \hline \end{tabular}
\end{table} 
Table 1: _Cont._



disc of sensors \(S_{i}\) and \(S_{j}\). Let \(p_{ij}\)=\((X_{1},Y_{1})\) and \(p_{ji}\)=\((X_{2},Y_{2})\) be the two points of intersection between the sensors \(S_{i}\) and \(S_{j}\). Then,

\[X_{1}:\frac{x_{i}+x_{j}}{2}+\frac{y_{j}-y_{i}}{2d_{ij}}\sqrt{(4R_{s}^{2}-d_{ij} ^{2})},Y_{1}:\frac{y_{i}+y_{j}}{2}-\frac{x_{j}-x_{i}}{2d_{ij}}\sqrt{(4R_{s}^{2} -d_{ij}^{2})} \tag{1}\]

\[X_{2}:\frac{x_{i}+x_{j}}{2}-\frac{y_{j}-y_{i}}{2d_{ij}}\sqrt{(4R_{s}^{2}-d_{ij} ^{2})},Y_{2}:\frac{y_{i}+y_{j}}{2}+\frac{x_{j}-x_{i}}{2d_{ij}}\sqrt{(4R_{s}^{2} -d_{ij}^{2})} \tag{2}\]

\[S_{i}:(x-x_{i})^{2}+(y-y_{i})^{2}=R_{s}^{2},S_{j}:(x-x_{j})^{2}+(y-y_{j})^{2}=R _{s}^{2} \tag{3}\]

Considering the location of each sensor and CIP, as given in the above equations, the procedure for localizing each CIP is given in Algorithm 3. ```
1:Input:
2:\(N_{i}\): Set of all sensing neighbors of node \(S_{i}\);
3:\(S_{j}\in N_{i}\): Any sensing neighbor of node \(S_{i}\);
4:\(CIP_{ij}\) and \(CIP_{ji}\): CIP between sensors \(S_{i}\) and \(S_{j}\);
5:\(L_{ij}\): Set of all lines connecting to the location of sensor \(S_{i}\) to location of \(S_{j}\);
6:Output:
7:\(CIP_{L}\): Set of CIP below the line \(L_{ij}\);
8:\(CIP_{U}\): Set of CIP above the line \(L_{ij}\);
9:Localization of CIP
10: Initialize \(CIP_{L}=\phi\) and \(CIP_{U}=\phi\);
11:Do: for all CIP between sensors \(S_{i}\) and \(S_{j}\);
12:\(\{\)
13: Select any sensor \(S_{i}\);
14: Select another sensor \(S_{j}\) from the set \(N_{i}\);
15: Check location of \(CIP_{ij}\) with respect to the line \(L_{ij}\);
16:if (\(CIP_{ij}\) is above \(L_{ij}\))
17:\(\{\)
18: Assign \(CIP_{U}\gets CIP_{ij}\);
19: Update \(CIP_{U}\);
20:\(\}\)
21:else
22:\(\{\)
23: Assign \(CIP_{L}\gets CIP_{ij}\);
24: Update \(CIP_{U}\);
25:\(\}\)
26:\(\}\)
```
**Algorithm 3** Localization of CIP.