# An Efficient Distributed Coverage Hole Detection Protocol for Wireless Sensor Networks
## 4 Proposed Hole Detection Protocol
### Determination of CP
We find that the control packet overhead is almost similar for less deployed nodes (100 to 800 sensors) irrespective of the number of coverage holes, which is obvious due to the lesser density of the nodes around a coverage hole. However, control packet overhead shows a significant difference for different numbers of holes, when he number of deployed sensors is more than 800, as the node density increases around each hole. The analysis of the average energy consumption for different numbers of holes with different deployed sensors is presented in Figure 10. Let \(k\) be the number of neighbors of a sensor \(S_{i}\) and \(E_{t}\) and \(E_{r}\) be the energy consumed by the sensor to transmit and receive data from its \(k\) neighbors. Since node \(S_{i}\) has to broadcast its location information and has to receive location information from its \(k\) neighbors, the typical amount of energy consumption of a node in our DCHD protocol could be \(Ec_{DCHD}=E_{t}+kE_{r}\). As shown in Figure 10, it is observed that the average energy consumption is affected by different numbers of deployed sensors. This experiment is carried out for different number of holes, and it is found that the energy consumption is increased with the number of holes. This situation occurs as the degree of neighbors that enclose coverage holes increases due to the increase in the different numbers of holes. \[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}\]0 Energy consumption in DCHD to detect different numbers of coverage holes. \[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}\]1 Control packet overhead in DCHD with different numbers of coverage holes. Figure 11 shows the average number of neighbors required to detect a coverage hole in LVP, the vector method and the DCHD algorithm, which is simulated with a fixed number of 15 holes in the monitoring region. When the number of sensors is 200, the average degree of neighbors is around 3.52, and therefore, the number of nodes required in hole detection is almost similar in all three protocols. However, when the number of sensor is increased to 800, the average degree of neighbors is around 27.31. Obviously, the average number of required nodes to detect the holes in the vector method is increased. However, in our DCHD and LVP algorithms, only a fixed number of nodes is used to detect the hole. However, in the DCHD algorithm, the average number of nodes needed for hole detection is 4.62, whereas an average of 6.02 nodes can participate in the LVP algorithm to detect the hole. From the simulation results depicted in Figure 11, we can infer that the execution time to find the hole in the vector method and the LVP algorithm is more than the DCHD algorithm. It is to be noted that the performance of DCHD is a little better than LVP in terms of the average number of nodes required for the hole detection. In LVP, the coverage hole is detected by taking the number of nearest neighbors, similarly to DCHD. According to their protocol, the communication range of each sensor is divided into four quadrants to find the number of nearest sensors of each sensor. In LVP, the number of neighbors that participate in the coverage hole detection procedure is a little more (6.02 nodes) than ours. Hence, the performance of DCHD over LVP is a little better in terms of the average number of nodes for the hole detection. Figure 12 shows the simulation result of average hole detection time with different numbers of holes for different protocols. It is noticed that the average hole detection time in DCHD is least as compared to LVP and the vector method. It is obvious from the results that DCHD outperforms LVP and the vector method, as fewer nodes in DCHD participate to detect the coverage holes.