1 Introduction

Wireless Sensor Networks (WSNs) consists of tiny battery operated sensor nodes that are designed to deliver data for applications like environment monitoring, intrusion detection, surveillance systems etc. [1]. These sensor nodes are deployed randomly or manually in a specific target region to collect, process and send the sensed data to remotely situated base station. Some critical applications like battlefield surveillance systems and intrusion detection need fully covered target region to make it work efficiently. During network functioning, some sensor nodes die due to energy depletion that may result in partial breakage of network coverage. We refer it as coverage hole problem of WSNs [2] [3]. These coverage holes affect the overall performance of WSNs. Therefore, an accurate detection and an efficient restoration technique for these coverage holes is highly required.

Several coverage preserving algorithms have been proposed [2,3,4,5] to maximize coverage lifetime of WSNs. Some Coverage aware scheduling algorithms are proposed in [2, 3] to balance energy consumption and intend to prolong coverage lifetime. In [4, 5], some coverage and energy aware clustering algorithms are proposed in which a sensor node with completely overlapped coverage area is selected as cluster head to route the data. Early deaths of these cluster heads do not create any coverage hole in the network as their sensing area is completely covered by their neighbor sensor nodes. However, after going through many transmission rounds some more sensors gets down those results in inescapable coverage holes. Some more coverage preserving algorithms are reported in [6,7,8] but they lack in detection of coverage holes hence missing restoration techniques. Some coverage hole detection techniques proposed by some researchers are reported in [9,10,11,12,13,14,15,16] but they do not provide any restoration strategy.

In this work, we mainly focus on to devise a new algorithm to detect and restore coverage holes in WSNs. We proposed a solution on the basis of Crucial Intersection Points (CIPs) which is a new concept. Our proposed solution can be divided into two parts: (1) A Crucial Intersection Points (CIPs) based localized algorithm for coverage hole detection and (2) A perpendicular bisection method based location calculation algorithm for coverage hole restoration.

The remaining part of this paper is organized as follows: Sect. 2 reviews the related work on coverage hole description, detection and restoration. Section 3 provides a description of problem formulation and terminologies used in this work. In Sect. 4 we propose our coverage hole detection algorithm. Section 5 describes the proposed coverage hole restoration algorithm. Performance is evaluated in Sect. 4 and finally Sect. 5 concludes the paper.

2 Related Work

Many coverage preserving algorithms have been proposed in [2,3,4,5,6,7,8] to maximize the coverage lifetime of WSNs. They are mainly coverage aware clustering and scheduling algorithms. In [2], a dynamic event detection technique called on-demand k-coverage is proposed in which static sensor nodes can adjust their sensing range during transmission time. They analyzed probability of event detection and lifetime of the scheme and conclude that increased network lifetime is achieved. A residual energy based sensor scheduling algorithm is proposed in [3]. Sensors can be put into sleep mode, activated or selected as a CH in this scheme. Main objective of this algorithm is to increase the network lifetime with fully covered target area. Algorithm in [4] is a coverage aware clustering protocol called as CACP. In this algorithm a new coverage aware cost metric is used for cluster head selection and a layered self activation scheme for active nodes selection is proposed. Objective of maximized network lifetime despite death of some sensor nodes is achieved. Another coverage and energy aware algorithm is reported in [5] called as ECDC. In this, they considered residual energy and coverage aware cost metric both for cluster head selection. Other coverage preserving algorithms are reported in [6,7,8]. All the above algorithms are designed with a common objective of maximized coverage lifetime. But, one common drawback of all these is that they do not provide any strategy to detect coverage hole formation in the network and nothing proposed for its restoration.

Various coverage hole detection algorithms are proposed in [9,10,11,12,13,14,15,16]. Algorithm [9] is a computational geometry based hole detection protocol for self organized WSNs. It can be applied for all kind of irregular polygons. In [10], two types of simplicial complexes are adopted to spot the coverage holes. Limitation of this algorithm is that it can detect only non triangular holes. In [11], a triangular oriented diagram is proposed for detection and calculation of coverage hole size. For healing purpose, they used circumcircle or in circle type to determine target localization for mobile sensors. But this algorithm does not provide full restoration with optimal number of nodes. Similar problem is tackled in [12] by using Delaunay triangulation based method. They used the properties of empty circle for detection of coverage hole. A boundary nodes clustering algorithm is also provided in it to identify different kind of coverage holes. In [13], a homology based approach for coverage hole detection is proposed. The relationship between cech complex and rips complex is analyzed in terms of coverage hole under different ratios between sensing radius and communication radius of a node. Simulation shows that this algorithm cannot localize all kind of coverage holes. In [14], a distributed protocol for coverage hole detection is proposed. They simply calculated the intersection points of nodes and filtered them into covered and non-covered. Then these intersection points are used to detect the coverage holes in network. In [15], an algorithm is presented for the same problem by using simple distance calculation and minimizing the number of transmitted messages. Each node determines whether it is a boundary node or not by verifying its intersection points. Similar problem is tackled in [16], in which a solution based on hop count measures is presented. The most alluring feature of this protocol is that it uses only basic data traffic information to detect coverage holes in the network. But the major shortcoming is that It is not suitable for large scaled randomly deployed wireless sensor networks. All the above discussed techniques contains one common drawback that they do not propose any strategy to overcome this coverage hole problem.

Several other algorithms for coverage hole restoration are also proposed in [17,18,19,20,21,22,23,24]. In [17], they proposed an algorithm for coverage hole detection and patching by using simplicial complexes. They used perpendicular bisection method to patch the coverage holes. It can work even if only partial coordinate information of sensor node is available. But the Number of nodes required for patching are not optimal because of redundant deployment of patching nodes. Similar problem is tackled in [18, 19] using mobile sensor nodes. But these solutions are not suitable for purely static wireless sensor network. In [20], an algorithm based on intersection points between sensors is proposed. They proposed a hole patching strategy based on perpendicular bisector of line between those intersection points. But they ignored the scenario of non-convex holes in the network and the required nodes for restoration are also not optimal. In [21, 22] a rearrangement method based algorithm are proposed but they are not suitable for static wireless sensor networks. In [23], they proposed a solution by increasing sensing range of sensor nodes. They divided whole target region into covered and uncovered cells. A sensor node with higher residual energy has been given priority to recover by increasing its sensing range. But this algorithm will not work where the nodes are deployed at its maximum sensing range. In [24], a tree-based method is proposed to detect the existing coverage holes. After detection of hole they also proposed a method to dissect a large hole into several smaller holes and then determine the optimal patch position for each sub-coverage hole. Drawback of this algorithm is that they Ignored the effects of small coverage holes on the overall performance of a network and also Ignored the scenario of non-convex holes. All these techniques do not present an optimum solution for coverage hole detection as well as restoration.

The proposed algorithm (CHDR) has following additional benefits:

  1. 1.

    A localized coverage hole detection mechanism in which each node tries to detect the coverage hole in network and after that sends the information to base station. Hence, it is scalable and distributable.

  2. 2.

    It can detect and restore both convex and non-convex holes efficiently.

3 Network Model and Terminologies

The Network model and some definitions of related terminologies used in this paper are presented in this section.

3.1 Network Model

The network model we assumed for the proposed algorithm is as follows: A set of sensor nodes deployed randomly over a 2-dimensional target region R and they are fixed after deployment. Every sensor node knows geographic location of itself and its neighbors via GPS or any other location information system. We consider that the sensing range (Rs) and communication rang (Rc) of each node is equal (Rs = Rc) and are immutable after deployment. If any area r in target region R is not covered by at least one sensor node then this unattended area will be called as coverage hole. We consider binary communication model, which means sensor is detectable inside the circle of communication range Rc or undetectable when outside. Sensing model is also considered binary, which means the area can be sensed inside the circle of sensing range Rs, or cannot be sensed when outside.

3.2 Terminologies

Following terminologies are used during designing of this algorithm:

Definition 1

(Target region): We defined a target region Tr that is required to be sensed by sensor nodes. If all the points inside Tr are covered by sensor nodes it means the region has no coverage holes. For simplification we used rectangular target region in this paper.

Definition 2

(Neighbor nodes): Nodes that comes under the sensing range of a node S are called as neighbor nodes of S denoted as Nn(S).

$$\{ {\text{S}}_{\text{i}}\in{\text{N}}_{\text{n}} \left( {\text{S}} \right)\left| {\left| {{\text{S}}_{\text{i}} {\text{S}}} \right| < 2{\text{R}}_{\text{s}} } \right|\}$$

Definition 3

(Intersection points): A point P is called as an intersection point if

  1. (1)

    It lies on the boundary of two sensor nodes Si and Sj, i.e. |PSi| = |PSj| = Rs

OR

  1. (2)

    It lies on the boundary of a sensor node Si and target region Tr

(a) Intersection points between two sensors (Fig. 1):-

$${\mathbf{O}}_{{\mathbf{1}}} {\mathbf{I}} \, = \, {\mathbf{R}}_{{\mathbf{s}}}$$
$${\mathbf{O}}_{{\mathbf{1}}} {\mathbf{O}}_{{\mathbf{2}}} = \sqrt {(a_{2} - a_{1} )^{2} + (b_{2} - b_{1} )^{2} }^{{}}$$
Fig. 1
figure 1

Intersecting sensor nodes S1 and S2

Full size image

Intersection points exists only if O1O2 < 2Rs and O1O2 ≠ 0

Equation of sensor node S1 and S2 will be:

$$\left( {{\mathbf{X}} - {\mathbf{a}}_{{\mathbf{1}}} } \right)^{{\mathbf{2}}} + \, \left( {{\mathbf{Y}} - {\mathbf{b}}_{{\mathbf{1}}} } \right)^{{\mathbf{2}}} = \, {\mathbf{R}}_{{\mathbf{s}}}^{{\mathbf{2}}}$$
$${\text{and}} \quad \left( {{\mathbf{X}} - {\mathbf{a}}_{{\mathbf{2}}} } \right)^{{\mathbf{2}}} + \, \left( {{\mathbf{Y}} - {\mathbf{b}}_{{\mathbf{2}}} } \right)^{{\mathbf{2}}} = \, {\mathbf{R}}_{{\mathbf{s}}}^{{\mathbf{2}}}$$

Using these equations we will find out the intersection points between two sensors.

(b) Intersection points between sensor nodes and boundary line of the region:-

Line’s equation using two points (X1, Y1) and (X2, Y2) is –

$${\mathbf{Y}} \, = \, {\mathbf{mX}} \, + \, {\mathbf{b}}$$

where \({\mathbf{m}} \, = \frac{(Y_2 - Y_1)}{(X_2 - X_1)}\) and b is the intersection point over Y-axis.

Sensing circle’s equation will be –

$$\left( {{\mathbf{X}} \, {-} \, {\mathbf{a}}} \right)^{{\mathbf{2}}} + \, \left( {{\mathbf{Y}} \, {-} \, {\mathbf{b}}} \right)^{{\mathbf{2}}} = \, {\mathbf{R}}_{{\mathbf{s}}}^{{\mathbf{2}}}$$

where (a, b) is coordinates of sensor node and Rs is sensing radius.

Using these equations we will find out the intersection points between sensor and target region’s boundary line.

Definition 4

(Crucial Intersection Points(CIP)): An intersection point P is said to be Crucial Intersection Point (CIP) if it is not covered by any of the deployed sensor nodes.

Definition 5

(Coverage hole): If an area r of target region R is not covered by at least one sensor node then this unattended area is called as coverage hole. Coverage holes can be classified into two types—close coverage hole and open coverage hole. Close coverage hole is completely surrounded by sensor nodes whereas in case of open coverage hole at least one of its edge is surrounded by boundary line of target region R (Fig. 2).

Fig. 2
figure 2

WSN with coverage holes

Full size image

In the above Fig. 2, it is shown that sensor nodes {S1,S2,S3,…….,S17} are randomly deployed over a target region R. Neighbor nodes of S1 are S2 and S5 because |S1, S2| and |S1, S5| are less than 2Rs where Rs is sensing range of a node. Intersection points {c1,c2,c3,…….,c8} and {c9,c10,c11} are the Crucial Intersection Points (CIPs) because they are uncovered by any other node other than their corresponding intersecting sensor nodes. Intersection points {c1,c2,c3,…….,c8} form a closed coverage hole and {c9,c10,c11} form an open coverage hole.

4 Proposed Strategy

In this section, we present our strategy for coverage hole detection and restoration using Crucial Intersection Points (CIPs). Our first strategy is for coverage hole detection using CIPs and after that in second strategy we find out the position for new patching node using perpendicular bisection method of a line.

4.1 Coverage Hole Detection

For detection of coverage holes in network we used crucial intersection points based method to detect the exact region which is not covered by any node other than the intersecting ones. First of all, each sensor node find out the crucial intersection points between neighbor nodes and itself. After that, on the basis of these intersection points it will find out the uncovered regions of the network called coverage holes. Detailed procedure is given below (Fig. 3).

Fig. 3
figure 3

Flow chart of coverage hole detection algorithm

Full size image

Pseudo code for Coverage hole detection:-

  1. 1.

    Initialize Sensor node list (S) to a predefined integer value.

  2. 2.

    Initialize Crucial Intersection Point (CIP) list (C) to NULL.

  3. 3.

    Select a sensor node S i from Sensor node list (S) and obtain a set of adjacent sensing neighbors N n (S i ).

  4. 4.

    Create a list of node’s sensing neighbors and sort them in clockwise.

  5. 5.

    Create a list of intersection points (P i ) with its sensing neighbors and the target region.

  6. 6.

    Check all intersection points (P i ) for Crucial Intersection Point and remove the non-crucial intersection points.

  7. 7.

    If Crucial Intersection Point found

    figure c
  8. 8.

    Continue this procedure until the Sensor node list (S) is NULL.

4.2 Coverage Hole Restoration

After detection of coverage hole in network we have to restore those holes by deploying new nodes over optimum locations. To detect the location of new node we used bisection method for straight line. The line is drawn between two crucial intersection points which are situated at maximum stored distance. The detailed procedure is given below (Fig. 4).

Fig. 4
figure 4

Flow chart of coverage hole restoration algorithm

Full size image

Pseudo code for Coverage hole restoration:-

  1. 1.

    Initialize Euclidian distances set(D ij ) to zero.

  2. 2.

    Input a point Ci from CIP list (C).

  3. 3.

    Select the next adjacent point C j in clockwise.

  4. 4.

    Calculate the Euclidian distance from C i to C j.

  5. 5.

    If Euclidian distance between |C i , C j | is less than or equal to 2R s

    figure d
  6. 7.

    Select node S n and run Coverage Hole Detection strategy from step 4–8.

5 Conclusion and Future Work

In this paper, we proposed a solution for detection and restoration of coverage holes in the wireless sensor networks. Our algorithm uses intersection points based approach for detection as well as restoration of coverage holes. It is expected that this algorithm can detect coverage holes accurately. It is also expected that our proposed restoration algorithm will require less number of patching nodes for restoration. This algorithm will outperform over other methods for convex and non convex holes restoration. It can be applied to any kind of polygon shaped area. Further simulation will use our algorithm and compare with the existing available approaches. In future, we will work on to reduce the complexity of this algorithm.