Computational geometry based coverage hole-detection and hole-area estimation in wireless sensor network

Abstract

Now-a-days Wireless Sensor Networks (WSNs) have massive significance in different surveillance related applications where coverage plays an important role. While arranging the sensor nodes in a large scale WSN, covering the region of interest (ROI) is a complicated job and this quality of coverage is compromised in the presence of coverage holes. As holes can cause permanent or temporary interruption in sensing or in communicating task, therefore detection of holes in a coverage area is an essential job. In this paper, we first construct a Delaunay Triangle on the basis of node location information. Then we propose an algorithm based on the property of empty circle to recognize whether coverage hole is present or not in the given ROI of a large scale WSN. Also, we have estimated the area of the coverage-hole based on computational geometry. We have shown the correctness of the algorithm based on the theoretical proofs. Simulations are also conducted to show the effectiveness of the algorithm for coverage-hole detection and area estimation (CHDAE).

Keywords

Wireless sensor networks sensor nodes coverage coverage hole-detection empty circle Delaunay Triangulation

1. Introduction

WSNs have drawn global attention due to a wide range of applications like environmental observation to endangered species recovery, habitat monitoring to home automation, waste management to wine production, medical science to military surveillance. In all such applications one criterion is common, that every point in the ROI must be covered by at least one sensor. Coverage quantifies how well an area is sensed by the nodes they are deployed into where each sensor has to wrap up some sub-region and summing up these entire covered sub-regions one can have a totally covered region in the WSN. But sometimes, a few sub-regions might not be covered by any of the deployed nodes and are termed as coverage holes. As a result, a few nodes might fail to sense data or loss communication with other nodes which ultimately degrades the performance of the network. A sensor network with full coverage is almost impossible to achieve i.e. there might be some holes in the coverage area. In the network,there may be a variety of reasons behind the creation of coverage holes such as: random deployment of nodes in remote places, out of power situation for long duration unattended nodes, ambiguity in the network topology, obstacle in the sensing field etc. Coverage holes are the reason behind the performance deterioration of the sensor network. If there is some coverage hole in the network, then communication becomes weak between the nodes due to the fact that, sensed data is routed along the boundary of the hole repeatedly. Therefore, detection of coverage hole is very important with respect to research challenges in WSNs. Moreover, proximity of coverage holes points to the fact that there are possible uncovered region in the WSN that needs extra sensors to be deployed and hence, the estimation of Coverage-Hole area is also equally important. Detection of hole in a WSN identifies whether a node is fully operational or not and guarantees elongated network lifetime which in turn provides sufficient quality of service in network coverage. Again, with the help of hole area estimation, we can measure the number of extra nodes required to be deployed in the ROI.

In this paper, our aim is to detect the coverage hole in a large scale WSN using the computational geometry based property called empty circle. Therefore, we need to define the network topology by creating the Delaunay Triangulation. After detection of hole, our next target is to estimate the area of the coverage hole. For this we have considered the intersection between two or more disks and thus we have designed the algorithm CHDAE for detection of coverage holes and hole-area estimation.

The rest of the paper is organized as follows: In Section 2, there is a precise literature review about the existing works done in case of coverage hole-detection. In Section 3, we discussed about some preliminary definitions and system models required for coverage hole-detection in sensor network. In Section 4, there is an elaborate description about our coverage hole-detection algorithm along with theoretical proofs. Simulation and result analysis is done in Section 5. And finally, we have concluded in Section 6.

2. Related work

In this section, we are going to discuss about various coverage hole-detection algorithms, especially based on computational geometry. So far we have studied the literature; we found the pioneer work in hole-detection in 2005, by R. Ghrist & A. Muhammad [7] who had proposed a centralized algorithm that detects holes via homology in which prior node location is not obligatory. This algorithm detects only single level coverage holes but unable to detect boundary holes. In 2008, X. Li & D. Hunter [13] proposed one distributed algorithm named 3MeSH (Triangle Mesh Self-Healing) for hole-detection as well as hole-recovery and is useful for large hole-recovery. Another prominent work in this field is from J. Kanno et al. [8] in 2009 who proposed a distributed algorithm that finds out the number of holes alongside their location in a non-planar sensor network. In 2010, Yang and Fei [17] proposed a hole-detection and adaptive geographical routing (HDAR) algorithm to detect coverage holes to solve the local minimum problem. In 2011, F. Yan et al. [16] used the concepts of Rips complex and Cech complex to determine coverage holes and classify them to be triangular or non-triangular. In 2012, S. Babaie & S.S. Pirahesh [2] proposed an algorithm based on triangular structure for coverage hole-detection and calculate its size.

In the most recent literature, W. Li [10] in 2014 has proposed a graph based coverage hole description algorithm. On the basis of empty circle property, first the coverage hole was being detected and then a graphic hole-description method was introduced to show the vulnerable parts in the holes. In 2014, P. Ghosh et al. [6] has proposed two novel distributed algorithms as DVHD (distance vector hole-determination) and GCHD (Gaussian curvature based hole-determination). DVHD calculates the shortest distance path between a pair of nodes in a weighted Delaunay graph utilizing the Bellman–Ford algorithm and GCHD calculates the distributed curvature to detect the number of holes using Gauss–Bonnet theorem. Li and Zhang [12] in 2015 proposed empty circle property based algorithm to detect coverage holes by forming Delaunay triangulation of the network. In 2016, G. Dai et al. [5] proposed Voronoi diagram based coverage hole detection algorithm (VCHDA) that can identify the coverage holes and can label the border nodes of the coverage-hole area. Again in 2016, Li Zhao et al. [18] proposed a novel coverage hole detection algorithm having two phases namely: Distributed Sector Cover Scanning (DSCS), which is used to identify the nodes on hole-borders and the outer boundary of WSN and Directional Walk (DW), which can trace the coverage holes based on the boundary nodes identified with DSCS. P.K. Sahoo et al. [9] in 2016 suggested a distributed coverage hole detection (DCHD) algorithm to detect the bounded or non-bounded coverage holes in the sensor network. Again in 2016, R. Beghdad & A. Lamraoui [3] proposed an algorithm based on Connected Independent Sets (BDCIS) for coverage hole detection. On the basis of neighbor discovery, the independent sets (IS) with specific cardinality are found with the help of the minimum or maximum id in the communication graph. W. Li. & Y. Wu [11] in 2016 has suggested a tree based algorithm for coverage hole-detection and healing. In this algorithm, based on tree concept location, size and shape of the detected coverage hole can be estimated. In 2017, Amgoth and Jana [1] proposed an algorithm having two phases namely: coverage hole-detection (CHD) and coverage restoration (CR). In CHD, each sensor node disjointedly detects hole by updating definite information with its neighbor nodes. For CR, a sensor node with relatively high residual energy is given precedence to cover up the hole closer to it by increasing its sensing range up to a maximum limit. From the above literature, we have found that graph based approaches are very promising for coverage hole-detection. Also, distributed algorithms for coverage hole-detection is much more efficient than centralized one. Further, we had the observation that node location information is the most important prerequisites for coverage hole-detection algorithm.

3. Preliminaries

In this section, we have discussed about the network model and few terminologies required for explaining the proposed hole-detection algorithm.

3.1. Network model

In this paper we have made a few assumptions required to set up the network model. Let $S = s_{1}, s_{2}, \dots, s_{n}$ be the set of n sensor nodes where $S_{i} = (X_{i}, Y_{i})$ with $i = 1, 2, \dots, n$ is the location of each sensor node. The prerequisite to coverage hole-detection is the node location information. For proper hole-detection, the accurate geographic position of nodes is very much essential which may be obtained via GPS. Other than GPS, techniques based on lateration or angulations, Angle of Arrival (AOA), Time difference of Arrival (TDoA), Received Signal Strength Indicator (RSSI) can also be used for node position estimation. In Section 4 we will elaborately discuss node location estimation technique in the neighbor discovery subsection. At the outset, all the static nodes are assumed to be with same initial energy and the links between the nodes are symmetric in nature. Let us consider a wireless sensor network having n number of sensor nodes deployed randomly over a 2D rectangular monitoring area. Due to this random deployment, somewhere nodes may be densely arranged with overlapping sensing range and somewhere sparsely arranged with uncovered regions called holes. In this paper we are considering the coverage holes inside the WSN only. Let the sensor nodes be homogeneous in nature and they have the same sensing and communication range as $R s$ and $R c$ such that $R c = R s$ . Though it is assumed that $R s$ is a disk, but practically it may not be of disk shape due to environmental and hardware aspects [15]. Moreover, sensing efficiency is not same in all routes around a sensor node. This asymmetrical sensing ability [4] of nodes has a lower bound in which $R s$ is set for convenience. As we are assuming $R s$ larger than actual value in the sensing model, thus practical errors caused due to position or angle estimation can be ignored. Therefore, all the transmissions inside $R s$ are assumed to be detected with a probability of 1 for large scale WSNs where $R s$ is very small as compared with the size of ROI.

3.2. Terminologies

Following are the few terminologies required in the subsequent sections:

3.2.1. Sensing disk

It is the circular shaped disk with radius $R s$ for each sensor node and any object inside this disk is detectable by the node. If $(X_{n}, Y_{n})$ be the coordinates of the node $s_{n}$ with the sensing radius as $R_{S}$ , then the sensing disk $s_{d}$ is represented by: $\begin{matrix} (1) & s_{d} = (x, y) | \sqrt{{(x - x_{n})}^{2} + {(y - y_{n})}^{2}} ⩽ R_{S} \end{matrix}$

3.2.2. Communication range

It is the circular shaped disk with radius $R_{C}$ for each sensor node and is equal to the radius of the empty circle. This radius is from the circum-circle which passes through a triangle formed with three points that are the locations of nodes. If A, B and C are the three sides of the triangle and Area of Triangle is $A_{t}$ which can be calculated from the location of the nodes then, $\begin{matrix} (2) & R_{c} = \frac{A * B * C}{4 * A_{t}} \end{matrix}$

3.2.3. Delaunay triangulation

It is a well known tool in computational geometry and can be constructed for a given set of discrete points (sensor nodes) in a 2D plane. A triangulation of a finite point set S is called a Delaunay triangulation, if the circumcircle of every triangle is empty, i.e., there is no point from S in its interior. Figure 1 show a Delaunay triangulation of a set of six points where the circumcircle of each of the five triangles are empty. The circle with the dotted line is not empty but it is not a circumcircle of any triangle. Let us assume a connected WSN where no four sensors are co-circular. Also we have supposed a coordinate free sensor location finding technique which is distributed in nature and is appropriate for large scale WSN. Based on relative positioning of the sensor nodes we have to create the Delaunay triangulation.

Fig. 1.

Delaunay triangulation with 6 points.

Fig. 2.

Representation of empty circle property.

3.2.4. Empty circle property

Empty Circle or Empty Circumcircle property is used to define the Delaunay Triangulation. The circumcircle of a triangle is the unique circle that passes through the three vertices of the triangle, as shown in Fig. 2.

Here $P (x, y)$ is the centre of the circumcircle whose coordinates are required to be calculated based on relative position of the sensor nodes A, B and C. Let $A (x_{1}, y_{1})$ , $B (x_{2}, y_{2})$ and $C (x_{3}, y_{3})$ are the 3 points (sensors) in the triangle whose coordinates are known. As $P A$ , $P B$ and $P C$ are the radius of the circumcircle, we have: $P A = P B = P C$ . Using the coordinates we have: $\begin{array}{l} (3) & P A = \sqrt{{(x - x_{1})}^{2} + {(y - y_{1})}^{2}} \\ (4) & P B = \sqrt{{(x - x_{2})}^{2} + {(y - y_{2})}^{2}} \\ (5) & P C = \sqrt{{(x - x_{3})}^{2} + {(y - y_{3})}^{2}} \end{array}$

From (3) and (4) we have: $\begin{array}{l} {(x - x_{1})}^{2} + {(y - y_{1})}^{2} = {(x - x_{2})}^{2} + {(y - y_{2})}^{2} \\ So, {(x - x_{1})}^{2} - {(x - x_{2})}^{2} = {(y - y_{2})}^{2} - {(y - y_{1})}^{2} \\ So, (x_{1}^{2} - x_{2}^{2}) - 2 x (x_{1} - x_{2}) = (y_{2}^{2} - y_{1}^{2}) - 2 y (y_{2} - y_{1}) \end{array}$

Therefore, $\begin{matrix} (6) & 2 x (x_{1} - x_{2}) - 2 y (y_{2} - y_{1}) = (x_{1}^{2} - x_{2}^{2}) - (y_{2}^{2} - y_{1}^{2}) \end{matrix}$

From (3) and (5) we have: $\begin{array}{l} {(x - x_{1})}^{2} + {(y - y_{1})}^{2} = {(x - x_{3})}^{2} + {(y - y_{3})}^{2} \\ So, {(x - x_{1})}^{2} - {(x - x_{3})}^{2} = {(y - y_{3})}^{2} - {(y - y_{1})}^{2} \\ So, (x_{1}^{2} - x_{3}^{2}) - 2 x (x_{1} - x_{3}) = (y_{3}^{2} - y_{1}^{2}) - 2 y (y_{3} - y_{1}) \end{array}$

Therefore, $\begin{matrix} (7) & 2 x (x_{1} - x_{3}) - 2 y (y_{3} - y_{1}) = (x_{1}^{2} - x_{3}^{2}) - (y_{3}^{2} - y_{1}^{2}) \end{matrix}$

From (6) and (7) we have the following matrix: $\begin{matrix} 2 [\begin{matrix} (x_{1} - x_{2}) & (y_{1} - y_{2}) \\ (x_{1} - x_{3}) & (y_{1} - y_{3}) \end{matrix}] [\begin{matrix} x \\ y \end{matrix}] = [\begin{matrix} (x_{1}^{2} - x_{2}^{2}) + (y_{1}^{2} - y_{2}^{2}) \\ (x_{1}^{2} - x_{3}^{2}) + (y_{1}^{2} - y_{3}^{2}) \end{matrix}] \end{matrix}$ By solving the above matrix, centre of empty circle $P (x, y)$ is calculated as follows: $\begin{array}{l} X = \frac{(y_{1} - y_{3}) (x_{1}^{2} - x_{2}^{2} + y_{1}^{2} - y_{2}^{2}) - (y_{1} - y_{2}) (x_{1}^{2} - x_{3}^{2} + y_{1}^{2} - y_{3}^{2})}{2 (x_{1} - x_{2}) (y_{1} - y_{3}) - 2 (x_{1} - x_{3}) (y_{1} - y_{2})} \\ Y = \frac{(x_{1} - x_{3}) (x_{1}^{2} - x_{2}^{2} + y_{1}^{2} - y_{2}^{2}) - (x_{1} - x_{2}) (x_{1}^{2} - x_{3}^{2} + y_{1}^{2} - y_{3}^{2})}{2 (x_{1} - x_{3}) (y_{1} - y_{3}) - 2 (x_{1} - x_{2}) (y_{1} - y_{2})} \end{array}$

4. Proposed hole-detection algorithm

In the proposed coverage hole-detection algorithm (CHDAE), we have three phases namely: (1) Constructing the Delaunay Triangle by estimating the position of sensor nodes, (2) Coverage Hole-detection in a large scale WSN and (3) Estimating the area of the detected coverage hole based on computational geometry.

4.1. Node position estimation

It is a prerequisite to hole-detection algorithm. In this step, we have used [14] to find node position and based on their position, the Delaunay Triangle is constructed. For this, we need any arbitrary node as reference node $(N_{r})$ with respect to which neighboring node location information and ID information within the range of $2 R_{C}$ can be found. Let $N_{1}$ and $N_{2}$ are the two nodes and their distance is $d (N_{1}, N_{2})$ , then one-hop or two-hop neighbor information can be as: $\begin{array}{l} \{\begin{matrix} 1-hop neighbor & if d (N_{1}, N_{r}) ⩽ R_{C} \\ 2-hop neighbor & if R_{C} ⩽ d (N_{1}, N_{2}) ⩽ 2 R_{C} \end{matrix} \end{array}$ For our system, among the deployed sensors in the ROI, a reference node $N_{r}$ is selected arbitrarily and it broadcasts a Hello1 message along with its location information. A node say, $N_{1}$ receives this message and calculates $d 1 (N_{1}, N_{r})$ . If $d 1 (N_{1}, N_{r}) ⩽ R_{C}$ then $N_{1}$ is set as 1-hop neighbor of $N_{r}$ and $N_{r}$ receives location information and ID of $N_{1}$ . Again, each 1-hop neighbor broadcasts Hello2 message with location information of $N_{r}$ . Another node, say, $N_{2}$ receives this message and if $d 2 (N_{2}, N_{r}) ⩽ 2 R_{C}$ then $N_{2}$ is set as 2-hop neighbor of $N_{r}$ and $N_{r}$ receives location information and ID of $N_{2}$ . Finally, all the 1-hop and 2-hop neighbor of each node are found with this process. Now when node location information of all sensors is collected with this process, the circum-center and circum-radius of the empty circle can be formulated and the Delaunay Triangle can be constructed. The computational complexity for constructing the Delaunay Triangle is $O (n p)$ , where n is the total number of sensor nodes in the ROI and p is the neighboring node of each sensor node.

4.2. Coverage-hole detection algorithm

For detecting the coverage hole, the following theorem is required to be proved.

Theorem.
If $R_{S}$ and $R_{C}$ are the sensing range of sensor node and radius of the empty circle respectively, then the relation $R_{C} > R_{S}$ implies that there must be some region in the empty circle that is uncovered. Conversely, for some uncovered region in an empty circle, the relation $R_{C} > R_{S}$ must hold.
Proof.
Let us assume, $R c > R s$ in Fig. 3. Therefore, if radius of empty circle is larger, definitely the center of the empty circle is out of coverage of sensing range of any sensor node. Thus, there must be some uncovered region in the empty circle that contains its center. As per definition, this uncovered region is the coverage hole. Hence proved that for $R c > R s$ there is some uncovered region in the empty circle. Conversely, we assume that there is some uncovered region in the empty circle. It implies that the center of the empty circle may be out of coverage of sensing range of any sensor node. It denotes that radius of empty circle must be larger than the sensing range of sensor node. Hence, $R c > R s$ is true. □

In the previous section we have found the procedure to get the location information of each sensor node and its neighbor nodes. On the basis of node location information, Delaunay Triangle is formed from which we studied the empty circle property. Based on the above theorem now we can comment that if radius of empty circle $R_{C}$ is larger than sensing radius $R_{S}$ , i.e., if $R c > R s$ then there must be some uncovered region in the empty circle which implies that the empty circle must contain some coverage hole inside it. On the other hand, if $R c > R s$ there is no coverage-hole in the empty circle. The computational complexity for checking if $R c > R s$ or not $O (n)$ where n is the total number of sensor nodes in the ROI.

Fig. 3.
Uncovered region inside the empty circle.
4.3. Area estimation of coverage-hole

This section is executed only after the evidence of coverage-hole in the empty circle. Here in this paper we are considering the coverage-hole area estimation in special scenario only. We have assumed that area estimation of coverage-hole may be done only when two sensing disks are intersecting among themselves. Before calculating coverage-hole area, we have to find out the area of two intersecting disks. When two circular shaped disks are intersecting among themselves, we will get circular sector from each of the circles. To determine each of the circular segments of the sector, we have to deduct the triangular area of each circle from their sector. Finally the coverage-hole area will be estimated by deducting area of each circular sector and area of two intersecting disks from the area of the Delaunay Triangle.

Fig. 4.

Intersection area of two disks.

4.3.1. Area estimation of two intersecting disks

According to Fig. 4 let us first consider that, $R_{a}$ and $R_{b}$ be the radius of the two intersecting disks with coordinates of centers as: $O_{a} (0, 0)$ and $O_{b} (d, 0)$ respectively. Let the two disks intersect themselves in two points M and N and again $M N$ intersects $O_{a} O_{b}$ at K. Therefore, the distance between the two center is $O_{a} O_{b} = d$ where, let us assume, $O_{a} K = d_{a} = x$ and $O_{b} K = d_{b} = (d - x)$ . Now, we have to evaluate $d_{a}$ and $d_{b}$ in order to calculate the area of each circular sector. From each circular sector, again we have to determine the segment of each circular sector. The segment of circular sector is the difference between the area of each circular sector and the triangular area of each circle.

From the general equation of circle we get: $\begin{array}{l} (8) & x^{2} + y^{2} = R_{a}^{2} \Rightarrow y^{2} = R_{a}^{2} - x^{2} \\ (9) & and, {(x - d)}^{2} + y^{2} = R_{b}^{2} \Rightarrow y^{2} = R_{b}^{2} - {(x - d)}^{2} \end{array}$ From (8) and (9) we get: $R_{a}^{2} - x^{2} = R_{b}^{2} - {(x - d)}^{2} \Rightarrow {(x - d)}^{2} + R_{a}^{2} - x^{2} = R_{b}^{2}$ $\begin{array}{l} (10) & Therefore, x = \frac{d^{2} + R_{a}^{2} - R_{b}^{2}}{2 d} \end{array}$ From (8) we get: $y^{2} = R_{a}^{2} - \frac{{(d^{2} + R_{a}^{2} - R_{b}^{2})}^{2}}{4 d^{2}} \Rightarrow y = \sqrt{\frac{{(2 d R_{a})}^{2} - {(d^{2} + R_{a}^{2} - R_{b}^{2})}^{2}}{4 d^{2}}}$

Therefore, $y = \frac{1}{2 d} \sqrt{(d + R_{a} + R_{b}) (d + R_{a} - R_{b}) (d - R_{a} + R_{b}) (- d + R_{a} + R_{b})}$

As per Fig. 4, $M N = P$ (Assumed) and $P = 2 y$ . Therefore, $\begin{array}{l} M N = \frac{1}{d} \sqrt{(d + R_{a} + R_{b}) (d + R_{a} - R_{b}) (d - R_{a} + R_{b}) (- d + R_{a} + R_{b}))} \\ (11) & Again, d_{a} = x = \frac{(d^{2} + R_{a}^{2} - R_{b}^{2})}{2 d} \\ (12) & And, d_{b} = (d - x) = \frac{(d^{2} - R_{a}^{2} + R_{b}^{2})}{2 d} \end{array}$

Now we have to find out area of each circular sector. Again from Fig. 4, let us assume that, $∠ M O_{a} N = θ_{a}$ and $∠ M O_{b} N = θ_{b}$ . Therefore, we have, $\begin{array}{l} cos (\frac{θ_{a}}{2}) = \frac{d_{a}}{R_{a}} \Rightarrow θ_{a} = 2 {cos}^{-} 1 (\frac{d_{a}}{R_{a}}) \end{array}$ Similarly, $θ_{b} = 2 {cos}^{-} 1 (\frac{d_{b}}{R_{b}})$ where $d ⩽ R_{a} + R_{b}$

Now, area of circular sector of circle 1 (with center $O_{a}$ ) is: $A = (\frac{θ_{a}}{2}) . R_{a}^{2} = R_{a}^{2} . {cos}^{-} 1 (\frac{d_{a}}{R_{a}})$

And, area of circular sector of circle 2 (with center $O_{b}$ ) is: $B = (\frac{θ_{b}}{2}) . R_{b}^{2} = R_{b}^{2} . {cos}^{-} 1 (\frac{d_{b}}{R_{b}})$

Now the triangular area of each circle can be estimated as following: $\begin{array}{l} Area of △ O_{a} M N = \frac{1}{2} . P . d_{a} and Area of △ O_{b} M N = \frac{1}{2} . P . d_{b} . \end{array}$ Now, the circular segment of each circle, i.e., $A_{s}$ for circle 1 (with center $O_{a}$ ) and $B_{s}$ for circle 2 (with center $O_{b}$ ) can be determined as the difference between area of circular sector and triangular area of circle. Therefore, $\begin{array}{l} A_{s} = R_{a}^{2} . {cos}^{-} 1 (\frac{d_{a}}{R_{a}}) - \frac{1}{2} . P . d_{a} and B_{s} = R_{b}^{2} . {cos}^{-} 1 (\frac{d_{b}}{R_{b}}) - \frac{1}{2} . P . d_{b} \end{array}$ Finally, total area of intersection, $\begin{array}{l} A_{s} + B_{s} \\ = R_{a}^{2} . {cos}^{-} 1 (\frac{d_{a}}{R_{a}}) - \frac{1}{2} . P . d_{a} + R_{b}^{2} . {cos}^{-} 1 (\frac{d_{b}}{R_{b}}) - \frac{1}{2} . P . d_{b} \\ = R_{a}^{2} . {cos}^{-} 1 (\frac{d_{a}}{R_{a}}) + R_{b}^{2} . {cos}^{-} 1 (\frac{d_{b}}{R_{b}}) - \frac{1}{2} . P . d where d = (d_{a} + d_{b}) \end{array}$ Now, using the value of $M N$ and (11) & (12) we have, $\begin{array}{l} A_{s} + B_{s} \\ = R_{a}^{2} . {cos}^{-} 1 (\frac{d^{2} + R_{a}^{2} - R_{b}^{2}}{2 d R_{a}}) + R_{b}^{2} . {cos}^{-} 1 (\frac{d^{2} - R_{a}^{2} + R_{b}^{2}}{2 d R_{b}}) \\ - \frac{1}{2} \sqrt{(d + R_{a} + R_{b}) (d + R_{a} - R_{b}) (d - R_{a} + R_{b}) (- d + R_{a} + R_{b})} \end{array}$

4.3.2. Coverage-hole area with one intersection

In this section we are considering the area estimation of coverage hole when there is exactly one intersection between the sensing disks of the sensor nodes.

Fig. 5.

Coverage-hole created by one intersection of 2 disks (a) $(S_{2} \cap S_{3})$ , (b) $(S_{1} \cap S_{3})$ and (c) $(S_{1} \cap S_{2})$ .

From Fig. 5, in each of the three cases, only one intersection area is found. Let us assume the three sides of the Delaunay Triangle are: a, b and c respectively. So, area of triangle, $\begin{array}{l} A_{t} = \sqrt{s (s - a) (s - b) (s - c)}, where s = \frac{(a + b + c)}{2} \end{array}$ Therefore, $A_{t} = \frac{1}{4} \sqrt{(a + b + c) (b + c - a) (c + a - b) (a + b - c)}$

Let $A_{1}$ , $A_{2}$ and $A_{3}$ are the area of each circular sector with respect to the sensor nodes $S_{1}$ , $S_{2}$ and $S_{3}$ . We know that, $A_{1} + A_{2} + A_{3} = π R_{S}^{2}$ where $R_{S}$ is the sensing radius of each sensor node. Therefore, area of hole, $\begin{array}{l} A_{h} = A_{t} - (A_{1} + A_{2} + A_{3}) - (S_{1} \cap S_{2}) \end{array}$

Now, assuming $R_{a} = R_{b} = R_{S}$ (since each sensor have a sensing radius of $R_{S}$ ) and using the concept of calculation of total area of intersection from Section 4.3.1 we have, $\begin{array}{l} (S_{1} \cap S_{2}) = R_{S}^{2} . {cos}^{-} 1 (\frac{d^{2}}{2 d R_{S}}) + R_{S}^{2} . {cos}^{-} 1 (\frac{d^{2}}{2 d R_{S}}) - \frac{1}{2} . \sqrt{(d + 2 R_{S}) d^{2} (- d + 2 R_{S})} \\ So, (S_{1} \cap S_{2}) = 2 R_{S}^{2} . {cos}^{-} 1 (\frac{d}{2 R_{S}}) - \frac{d}{2} . \sqrt{4 R_{S}^{2} - d^{2}} \end{array}$ Therefore, area of hole, $\begin{array}{l} A_{h} = \frac{1}{4} \sqrt{(a + b + c) (b + c - a) (c + a - b) (a + b - c)} - π R_{S}^{2} - 2 R_{S}^{2} . {cos}^{-} 1 (\frac{d}{2 R_{S}}) - \frac{d}{2} . \sqrt{4 R_{S}^{2} - d^{2}} \end{array}$

Fig. 6.

Coverage-hole created by two intersections: (a) $(S_{1} \cap S_{2})$ and $(S_{2} \cap S_{3})$ , (b) $(S_{3} \cap S_{1})$ and $(S_{1} \cap S_{2})$ and (c) $(S_{1} \cap S_{3})$ and $(S_{3} \cap S_{2})$ .

4.3.3. Coverage-hole area with two intersections

In this case, we are regarding the area estimation of coverage hole when there are two intersections between any two of the sensing disks of the sensor nodes. If we look at Fig. 6, in each of the three scenario, two intersections are visible. Thus, area of hole, $\begin{array}{l} A_{h} = A_{t} - (A_{1} + A_{2} + A_{3}) - (S_{1} \cap S_{2}) - (S_{1} \cap S_{3}) \end{array}$ Hence, we have to compute each intersection area separately. Now, let us assume $d_{1}$ be the distance between the centers of sensors $S_{1}$ and $S_{2}$ . And again $d_{2}$ be the distance between the centers of sensors $S_{1}$ and $S_{3}$ . $\begin{array}{l} Therefore, the area of intersection 1 is: (S_{1} \cap S_{2}) = 2 R_{S}^{2} . {cos}^{-} 1 (\frac{d_{1}}{2 R_{S}}) - \frac{d_{1}}{2} . \sqrt{4 R_{S}^{2} - d_{1}^{2}} \\ Again, the area of intersection 2 is: (S_{1} \cap S_{3}) = 2 R_{S}^{2} . {cos}^{-} 1 (\frac{d_{2}}{2 R_{S}}) - \frac{d_{2}}{2} . \sqrt{4 R_{S}^{2} - d_{2}^{2}} \end{array}$ Therefore, area of hole, $\begin{array}{l} A_{h} = & \frac{1}{4} \sqrt{(a + b + c) (b + c - a) (c + a - b) (a + b - c)} - π R_{S}^{2} - 2 R_{S}^{2} . [{cos}^{-} 1 (\frac{d_{1}}{2 R_{S}}) + {cos}^{-} 1 (\frac{d_{2}}{2 R_{S}})] \\ - \frac{1}{2} . [d_{1} \sqrt{4 R_{S}^{2} - d_{1}^{2}} + d_{2} \sqrt{4 R_{S}^{2} - d_{2}^{2}}] \end{array}$

Fig. 7.

Coverage-hole created by three intersections of all three disks.

4.3.4. Coverage-hole area with three intersections

In this case, we are considering the coverage-hole area when there are three intersections between any two of the sensing disks of the sensor nodes. In Fig. 7, there are three intersections formed with two sensing disks. Let us assume $d_{1}$ be the distance between the centers of sensors $S_{1}$ and $S_{2}$ , $d_{2}$ be the distance between the centers of sensors $S_{2}$ and $S_{3}$ and $d_{3}$ be the distance between the centers of sensors $S_{3}$ and $S_{1}$ . Then the three intersections are as follows: $\begin{array}{l} Intersection 1, (S_{1} \cap S_{2}) = 2 R_{S}^{2} . {cos}^{-} 1 (\frac{d_{1}}{2 R_{S}}) - \frac{d_{1}}{2} . \sqrt{4 R_{S}^{2} - d_{1}^{2}} \\ Intersection 2, (S_{2} \cap S_{3}) = 2 R_{S}^{2} . {cos}^{-} 1 (\frac{d_{2}}{2 R_{S}}) - \frac{d_{2}}{2} . \sqrt{4 R_{S}^{2} - d_{2}^{2}} \\ Intersection 3, (S_{1} \cap S_{3}) = 2 R_{S}^{2} . {cos}^{-} 1 (\frac{d_{3}}{2 R_{S}}) - \frac{d_{3}}{2} . \sqrt{4 R_{S}^{2} - d_{3}^{2}} \\ Thus, area of hole, A_{h} = A_{t} - (A_{1} + A_{2} + A_{3}) - (S_{1} \cap S_{2}) - (S_{2} \cap S_{3}) - (S_{1} \cap S_{3}) \end{array}$

Therefore, $\begin{array}{l} A_{h} = & \frac{1}{4} \sqrt{(a + b + c) (b + c - a) (c + a - b) (a + b - c)} - π R_{S}^{2} \\ - 2 R_{S}^{2} . [{cos}^{-} 1 (\frac{d_{1}}{2 R_{S}}) + {cos}^{-} 1 (\frac{d_{2}}{2 R_{S}}) + {cos}^{-} 1 (\frac{d_{3}}{2 R_{S}})] \\ - \frac{1}{2} . [d_{1} \sqrt{4 R_{S}^{2} - d_{1}^{2}} + d_{2} \sqrt{4 R_{S}^{2} - d_{2}^{2}} + d_{3} \sqrt{4 R_{S}^{2} - d_{3}^{2}}] \end{array}$ In a nutshell, the pseudo code for CHDAE algorithm is given in Fig. 8.

Fig. 8.

Pseudo code for CHDAE algorithm.

5. Simulation and result analysis

In this section we have presented some simulations to check the correctness of hole-detection algorithm. In the simulation, empty circle based hole-detection was implemented and for this first the Delaunay Triangles are being detected.

Fig. 9.

Detection of coverage-hole with varying sensor nodes and sensing range: $R_{S} = 50 m$ (a) 450 nodes (b) 650 nodes (c) 900 nodes, $R_{S} = 35 m$ (d) 1200 nodes (e) 1500 nodes (f) 2000 nodes and $R_{S} = 25 m$ (g) 2300 nodes (h) 2600 nodes (k) 3000 nodes.

Also we have analyzed a few properties while detecting the coverage holes. For simulation purpose we have used MATLAB as it is a widely accepted platform to design computational geometry based hole-detection.

The simulations are conducted with different parameters such as: number of nodes, size of ROI, dimension of sensing radius etc. Here we have used three different sizes of ROI varying from 400 m to 1500 m and the number of sensor nodes varying from 400 to 3000. Apparently, the sensing radius also varies between 25 m to 50 m. While detecting the coverage hole, a few properties related with holes like: number of Delaunay Triangle, number of holes and run time are being considered. As the nodes are deployed randomly, hence arrangement of nodes changes frequently which in turn changes these properties. Therefore, we have executed each simulation for on an average 20 times and taken the average values. In Fig. 9, simulation shows the detection of coverage-hole using empty circle property with different sensing range and different number of nodes. With the increasing no. of nodes, the number of Delaunay Triangles also gets increased, so does the run time of simulation and the number of holes gets lower.

Fig. 10.

Run time for detection of coverage-hole with varying sensor nodes and sensing range.

Figure 10 shows the different run time for varying sensing range along with different number of sensor nodes. To obtain the above mentioned graph we have reduced the sensing range with the increasing number of sensor nodes. From the graph we can comment that run time will increase drastically with increasing number of nodes and decreasing sensing range.

Fig. 11.

Number of delaunay triangle with varying sensor nodes and sensing range.

Figure 11 shows the number of Delaunay Triangle (DT) created for hole-detection with varying sensing range and different number of sensor nodes. From the above mentioned graph it is found that number of DT rapidly increases with the increasing number of nodes and decreasing sensing range.

Fig. 12.

Number of coverage-holes with varying sensor nodes and sensing range.

Again Fig. 12 depicts the number of coverage-holes created with varying sensing range and different number of sensor nodes. In that figure we can find that the number of coverage-holes decreases with the increasing number of sensor nodes. As the increasing number of nodes enlarges the node density in the ROI, hence holes decreases.

5.1. Discussions

Here we are discussing about some assumptions that are required while applying our CHDAE algorithm to a real life WSN system. It is obvious that the design complexity of WSN is purely application dependent while the application requirements may be the number of nodes, type of deployment, power consumption, sensing time etc. CHDAE is suitable to be applied on surveillance related applications where coverage-holes can cause permanent or temporary interruptions in the monitoring task. In fact, quality of surveillance depends on the fact that whether every point in the ROI is covered by at least one sensor or not. As full coverage is almost impossible to achieve, there must be some coverage-hole in the ROI and by assuming the existence of holes in the WSN, CHDAE is primarily applied.

Again, in a WSN, a coverage hole primarily occurs due to the failure of the sensor nodes, where distance between nodes or energy consumption can accelerate the node-failure. If the distance between nodes are much higher, a sophisticated quality of transmission is required which in turn needs high energy consumption. Hence, if certain node in the ROI fail to operate, then a technique is required that can quickly organize the rest of the nodes for coverage control. To obtain this autonomous self-organizing coverage control, hole-area is required to be calculated because it gives an idea about how much area is still uncovered. Therefore, in a surveillance system, based on hole-area size, more sensors can be deployed on an urgent basis in a larger hole-area.

6. Concluding remarks

As WSN is very much application specific, hence to support those multidisciplinary applications, sensor node deployment should be arranged properly. At the time of node deployment in the ROI, QoS can be at risk due to the occurrence of holes. That’s why, in this paper, we have tried to detect any kind of coverage hole present in the ROI using empty circle property. Also, we have calculated the area of hole while there is intersection between the sensing disks. In this work we have not merged those empty circles falling in the boundary of the same coverage holes, therefore we may try to keep it as our future scope of work. Simulation shows the correctness of the algorithm as well as we have shown the dependability of number of holes, number of DT and run time with respect to number of nodes being deployed along with sensing range.

References

Amgoth and

P.K.

Jana, Coverage hole detection and restoration algorithm for wireless sensor networks, Peer-to-Peer Networking and Applications 10(1) (2017), 66–78. doi:10.1007/s12083-015-0407-2.

Babaie and

S.S.

Pirahesh, Hole detection for increasing coverage in wireless sensor network using triangular structure, Preprint, arXiv:1203.3772, 2012.

Beghdad and

Lamraoui, Boundary and holes recognition in wireless sensor networks, Journal of Innovation in Digital Ecosystems 3(1) (2016), 1–14. doi:10.1016/j.jides.2016.04.001.

Boukerche and

Fei, A coverage-preserving scheme for wireless sensor network with irregular sensing range, Ad hoc networks 5(8) (2007), 1303–1316. doi:10.1016/j.adhoc.2007.02.020.

Dai,

Lv,

Chen,

Zhou and

Xu, A novel coverage holes discovery algorithm based on Voronoi diagram in wireless sensor networks, International Journal of Hybrid Information Technology 9(3) (2016), 273–282. doi:10.14257/ijhit.2016.9.3.25.

Ghosh,

Gao,

Gasparri and

Krishnamachari, Distributed hole detection algorithms for wireless sensor networks, in: Mobile Ad Hoc and Sensor Systems (MASS), 2014 IEEE 11th International Conference on, 2014, IEEE, pp. 257–261. doi:10.1109/MASS.2014.25.

Ghrist and

Muhammad, Coverage and hole-detection in sensor networks via homology, in: Information Processing in Sensor Networks, 2005. IPSN 2005. Fourth International Symposium on, 2005, IEEE, pp. 254–260. doi:10.1109/IPSN.2005.1440933.

Kanno,

R.R.

Selmic and

Phoha, Detecting coverage holes in wireless sensor networks, in: Control and Automation, 2009. MED’09. 17th Mediterranean Conference on, 2009, IEEE, pp. 452–457. doi:10.1109/MED.2009.5164583.

Kumar Sahoo,

M.-J.

Chiang and

S.-L.

Wu, An efficient distributed coverage hole detection protocol for wireless sensor networks, Sensors 16(3) (2016), 386. doi:10.3390/s16030386.

10.

Li, A novel graphic coverage hole description in wireless sensor networks, IEEE Communications Letters 18(12) (2014), 2205–2208. doi:10.1109/LCOMM.2014.2366094.

11.

Li and

Wu, Tree-based coverage hole detection and healing method in wireless sensor networks, Computer Networks 103 (2016), 33–43. doi:10.1016/j.comnet.2016.04.005.

12.

Li and

Zhang, Coverage hole and boundary nodes detection in wireless sensor networks, Journal of network and computer applications 48 (2015), 35–43. doi:10.1016/j.jnca.2014.10.011.

13.

Li and

D.K.

Hunter, Distributed coordinate-free hole recovery, in: Communications Workshops, 2008. ICC Workshops’ 08. IEEE International Conference on, 2008, IEEE, pp. 189–194. doi:10.1109/ICCW.2008.41.

14.

H.-C.

Ma,

P.K.

Sahoo and

Y.-W.

Chen, Computational geometry based distributed coverage hole detection protocol for the wireless sensor networks, Journal of network and computer applications 34(5) (2011), 1743–1756. doi:10.1016/j.jnca.2011.06.007.

15.

Tan,

Xing,

Liu,

Wang and

Jia, Exploiting data fusion to improve the coverage of wireless sensor networks, IEEE/ACM Transactions on networking 20(2) (2012), 450–462. doi:10.1109/TNET.2011.2164620.

16.

Yan,

Martins and

Decreusefond, Connectivity-based distributed coverage hole detection in wireless sensor networks, in: Global Telecommunications Conference (GLOBECOM 2011), 2011 IEEE, 2011, IEEE, pp. 1–6.

17.

Yang and

Fei, HDAR: Hole detection and adaptive geographic routing for ad hoc networks, in: ICCCN, 2010, pp. 1–6.

18.

L.-H.

Zhao,

Liu,

Lei,

Zhang and

Tan, Detecting boundary nodes and coverage holes in wireless sensor networks, Mobile Information Systems 2016 (2016).