# An Efficient Distributed Coverage Hole Detection Protocol for Wireless Sensor Networks
## 4 Proposed Hole Detection Protocol
### Determination of CP
Based on the initial point and terminal points of each arc, finally, they are connected with each other to construct the coverage hole by which, the shape of the hole can be known. For example, as shown in Figure 7, taking \(S_{1}\) as the starting sensor, the arcs \(\widehat{p_{1}p_{2}}\), \(\widehat{p_{2}p_{3}}\), \(\widehat{p_{3}p_{4}}\), \(\widehat{p_{4}p_{5}}\), \(\sim\widehat{p_{10}p_{1}}\) marked in red are connected to each other, which can form a hole. Thus, these uncovered arcs enclose the bounded coverage hole \(H_{1}\). Similarly, as shown in Figure 7, coverage holes \(H_{2}\), \(H_{3}\) and \(H_{4}\) are enclosed by the arcs marked in red. Figure 6: Construction of covered and uncovered arcs. Figure 7: Formation of coverage holes using the uncovered arcs. ## 5 Performance Evaluation

In this section, the performance of our proposed DCHD protocol is evaluated in terms of control packet overhead, power consumption to detect the holes and time to detect the holes. Besides, our protocol is also compared to similar coverage hole detection protocols, such as the localized Voronoi polygon (LVP) [18] and the vector method [23]. The detailed description of the simulation setups and results is given as follows. ### Simulation Setup

In our simulation, a rectangular monitoring region of a size of \(500\times 400\) m\({}^{2}\) is considered. About 100 to 1500 sensor nodes are deployed randomly over the monitoring region, and the algorithms are simulated using ns-2.29 [35]. The sensing range of each sensor is taken to be 20 m, and communication range is fixed at 40 m, as we have considered that the communication range is twice the sensing range. The simulation parameters are setup according to the IEEE 802.15.4 MAC/PHY specification and the radio characteristics of IEEE 802.15.4 compliant product CC2420 [36] along with the AODV (_ad hoc_ on-demand distance vector routing) protocol [37] and two-ray ground propagation model [38]. The initial energy of each node is assumed to have a fixed amount of 50 J of reserved energy, and the energy cost due to forwarding of each control packet is taken to be 0.3 J. Holes are generated randomly among the multi-hop and fully-connected nodes, so that they can form different groups of disjoint sets of nodes. Location information is given to all nodes, so that they can know about their one-hop sensing neighbors' set and can find the point of intersection with the sensing disc of their neighbors. The data rate is kept as 250 Kbps, and the control packets are sent every 2 s to detect the neighbors, which is continued till 20 s to get the final list of one-hop neighbors of each node. ### Simulation Result

In this section, first, we simulate our protocol for different numbers of coverage holes to evaluate the hole detection time, energy consumption and control packet overhead to detect the holes. Besides, we have also simulated our protocol to compare to other similar protocols in terms of control packet overhead, hole detection time and energy consumption with different numbers of holes and sensors. As shown in Figure 8, we have simulated the average hole detection time for different numbers of deployed sensors with the fixed number of coverage holes with 15, 30 and 45 present in the monitored region. It is observed that the average hole detection time is increased with the increase in the number of deployed sensors, which is quite reasonable. It is to be noted that the number of sensing neighbors of a node increases if the number of deployed nodes in the monitoring region is increased, which increases the hole detection time, as a node has to find its CIP and CP with its neighbors before detecting a hole. Figure 8: Average hole detection time in DCHD with different numbers of coverage holes. As shown in Figure 9, the control packet overhead is simulated with the number of deployed sensors. This simulation is carried out for different numbers of holes in the monitored region. We observe that the control packet overhead is increased, if the number of deployed sensors is increased.