# An Efficient Distributed Coverage Hole Detection Protocol for Wireless Sensor Networks
## 3 System Model
### Definitions  
In this subsection, we define a few terms, which are used throughout the paper to develop our coverage hole detection protocol. **Definition 1 (sensing disc):** The sensing disc of a sensor is the circle with the sensing range as its radius, when it is centered at its own location. Any object present within the sensing disc of a sensor is perfectly detected by it. Throughout the paper, the radius of the sensing disc is refereed to as its sensing range (\(R_{s}\)). **Definition 2 (connecting neighbors):** Two nodes \(A\) and \(B\) are said to be connecting neighbors, if their Euclidean distance \(d(A,B)\leq R_{c}\). As per our assumption, communication range \(R_{c}=2R_{s}\), and  
Figure 2: Example of coverage holes, critical intersection point (CIP) and covered point (CP). therefore, nodes \(A\) and \(B\) are connecting neighbors, as shown in Figure 3. Similarly, nodes \(B\) and \(C\) are the connecting neighbors. From this definition, it is clear that a connecting neighbor is always a one-hop neighbor of a node. **Definition 3 (sensing neighbors):** Two nodes \(A\) and \(B\) are said to be sensing neighbors, if their Euclidean distance \(d(A,B)<2R_{s}\). As shown in Figure 1, nodes \(A\) and \(B\) are sensing neighbors as \(d(A,B)<2R_{s}\). Similarly, nodes \(B\) are \(C\) sensing neighbors as \(d(B,C)\) is \(<2R_{s}\). In order to relate the sensing neighbors with connecting neighbors in our definition, it is clear that sensing discs of the sensing neighbors always overlap with each other, and they must be connecting neighbors, as they are located within one-hop from each other. As shown in Figure 3, nodes \(A\) and \(B\) are the sensing neighbors, as well as connecting neighbors. It is to be noted that throughout the paper, the set of sensing neighbors of any sensor \(S_{i}\) is denoted as \(N_{i}\). **Definitions 4 (bounded/unbounded coverage hole):** If any part of the monitoring region is not covered by the sensing disc of any sensor, there exists a coverage hole. Coverage holes are found in a monitoring region, if some part of it is sparsely deployed. A coverage hole is said to be bounded, if it is enclosed by the sensing discs of the deployed sensors. Otherwise, it is an unbounded coverage hole. As shown in Figure 2, hole \(H_{1}\) is a bounded coverage hole, whereas holes \(H_{2}\)-\(H_{4}\) are unbounded coverage holes. **Definitions 5 (boundary/non-boundary sensors):** Sensors that enclose a bounded coverage hole are called boundary sensors. If \(S_{i}\) is the set of sensors \(\forall\)\(i\)=1,2,3,...,\(m\), for \(m\leq n\), and encloses a coverage hole; then, each element of the set of sensors \(S_{i}\) is a boundary sensor. The sensors that enclose an unbounded coverage hole are called non-boundary sensors. As shown in Figure 2, sensors \(S_{1}\sim S_{10}\) are boundary sensors, as the coverage hole \(H_{1}\) is enclosed by them. Similarly, sensors \(S_{5}\), \(S_{6}\), \(S_{7}\) and \(S_{12}\) are non-boundary sensors, as the coverage hole \(H_{2}\) is enclosed by them. It is to be noted that a sensor could be a boundary, as well as a non-boundary sensor based on the presence of the holes. For example, as shown in Figure 2, sensors \(S_{5}\), \(S_{6}\) and \(S_{7}\) are boundary, as well as non-boundary sensors, as they enclose the bounded coverage hole \(H_{1}\) and unbounded coverage hole \(H_{2}\), respectively. **Definitions 6 (border/non-border sensors):** The sensor \(S_{i}\), \(\forall\)\(i\)=1,2,3,...,\(n\) is said to be a border sensor, if its sensing disc intersects the border of the monitoring region. Otherwise, the sensor must be a non-border sensor. It is to be noted that the equation of each border line can be given as \(y-y_{i}\)\(=(x-x_{i})(\frac{y_{i}-y_{i}}{x_{j}-x_{i}})\), \(\forall\)\(i=1\) and \(j=2\) or \(i=2\) and \(j=3\) or \(i=3\) and \(j=4\) or \(i=1\) and \(j=4\).