1 Introduction

Wireless sensor networks (WSNs) are known for potential applications such as in environment monitoring and surveillance etc. [1]. Sensor nodes are deployed in a target area to sense physical conditions of the area. The sensor nodes collect certain data from the target area, process and send to a special command node called sink. In some applications, such as vehicular tracking or intrusion detection, sensor nodes need to maintain the complete coverage of the target area to fulfill its objective. During the network operation, few sensor nodes die due to energy exhaustion and it may results in breakdown of the network coverage partially. We refer this as coverage hole problem. In this context, we define coverage lifetime or coverage-time is the time until the formation of coverage hole or sensing hole due to death of few sensor nodes. Therefore, there is a need to adopt an efficient coverage technique to prolong coverage lifetime of the network despite death of few sensor nodes.

Many coverage-aware techniques have been proposed [2–15] for WSNs to maximize the coverage lifetime. They are broadly categorized into coverage-aware scheduling and coverage-aware clustering algorithms. In the former [2–6], a subset of sensor nodes is selected in such way that they cover the whole target area completely and other nodes move to sleep state. Quite a few scheduling algorithms have also been reported in the recent years [7–9]. In the latter [10–15], a node is given higher priority to be selected as cluster head (CH) whose sensing area is completely covered by the sensing area of its neighbor nodes. Early death of such CHs does not breach the coverage of the target area since the CHs are overburdened as compared to their member sensor nodes. However, after some rounds coverage hole is inevitable due to death of few more sensor nodes. Coverage hole can be restored by increasing the sensing range of the sensor nodes near the hole subject to maximum sensing range. This can delay the breakdown of the network coverage. Note that, all the above mentioned techniques lack in detecting the coverage hole and therefore they do not have any strategy to restore it.

In this paper, we propose a new algorithm called CHD-CR which attempts to maximize the coverage lifetime by restoring the coverage after detecting a sensing hole in the network. The proposed algorithm mainly consists of two phases, namely coverage hole detection (CHD) and coverage restoration (CR). In CHD, each sensor node independently detects any hole by updating certain information with its neighbor nodes. To restore the coverage, a sensor node with relatively higher residual energy is given priority to cover the hole closer to it by increasing its sensing range up to a maximum limit. We test the performance of the proposed algorithm and compare the simulation results with the existing coverage-aware algorithms such as CPCP-cc (coverage-preserving clustering protocol with coverage cost) [12] and flow-balanced routing (FBR) [13] in terms of coverage lifetime.

The remaining part of the paper is organized as follows. Existing works are reviewed in Section 2. Network model and terminologies of the proposed algorithm are described in Section 3. We present our proposed algorithm in Section 4. Simulation results are discussed in Section 5 and the paper is concluded in Section 6.

2 Related works

Many algorithms [2–11] have been proposed to solve the coverage problem in WSNs. They are mainly divided into two types; i) coverage-aware clustering algorithms and ii) coverage-aware scheduling algorithms which are discussed as follows.

Several coverage-aware clustering algorithms have been reported in [10–15]. The algorithm called CPCHSA (coverage-preserving cluster head selection algorithm) in [10] is modified from the LEACH (low energy adaptive clustering hierarchy) [16] protocol. In this algorithm, different nodes are assigned different probabilities for being a cluster head. The probability depends on the normalized effective sensing area of a node, in order to maximize the network sensing coverage. The normalized effective sensing area is defined as the ratio of the effective sensing area to the maximum sensing area of the node. In [8], a novel centralized algorithm has been proposed for near optimal assignment of sensors’ state. This algorithm computes a near optimal network topology in which each sensor nodes can be activated, put in sleep mode or promoted as CH. Ultimately, the objective of the algorithm is to maximize the network lifetime while ensuring the full coverage of the monitored area and the connectivity of the obtained network topology. In [12], various coverage-aware cost metrics have been proposed for the selection of the CHs, active nodes and routers in order to maintain the full coverage of the target area. In this techniques, both the remaining residual energy of the sensor nodes as well as redundancy in their coverage are considered together to determine the better candidates for CH, active nodes and routers. A new flow-balanced routing (FBR) protocol has been proposed in [13]. In FBR, selection of CHs is determined on the basis of the overlapping degrees of sensor nodes. Some sensor nodes whose sensing areas are covered by others are put to sleep state in order to save the energy. Then a multi-level architecture which consists of CHs has been constructed to route the data to the sink. In [14], a new coverage-aware clustering protocol has been proposed called CACP. The CACP uses a coverage-aware cost metric for CH selection and applies a layered self-activation scheme to emulate the most tessellation for active nodes selection. Other coverage related algorithms are reported in [17–25]. One common objective of these algorithms is to maximize the coverage lifetime despite death of few sensor nodes. However, once common draw is that they cannot detect coverage hole after its formation in the network and therefore no strategies to overcome it.

Numerous coverage-aware scheduling algorithms have also been proposed [2–9]. The algorithm in [2] is an extension of the LEACH. In this algorithm, each sensor node decides to turn off when it discovers that its sensing area is completely monitored by its neighbor nodes. In the algorithm [3], a subset of sensor nodes are activated to monitor the target area with by adjusting their sensing ranges so that the whole area is completely covered and other nodes are moved to sleep mode. Many sensor devices with adjustable sensing ranges are available in the market [26, 27]. In [4] proposed an algorithm called adjustable range set covers (AR-SC). Its objective is to find a maximum number of set of sensor nodes and the sensing ranges associated with sensor nodes, such that each set covers all the targets in the area to be monitored. However, AR-SC is not energy-aware because adjusting sensing range of the nodes depends on the number of targets monitored by them only. A similar problem has also been tackled in [5, 6] using linear programming and Voronoi diagram-based heuristic algorithm. In all the above mentioned techniques, once major common drawback is that they cannot detect the formation of coverage holes in the network and therefore no strategy to overcome it. Coverage restoration is not new in WSNs. In [28], focus on how to schedule mobile sensor nodes and their locations in order to overcome the coverage problem as well as minimize their energy consumption due to mobility. A similar coverage problem has been addressed with mobile nodes in [29]. Recently, yet another algorithm has been proposed based on mobile sensor nodes [30]. However, these techniques are not suitable for static sensor networks.

The proposed CHD-CR algorithm has additional benefits which are summarized as follows

  1. 1).

    Local mechanism for coverage hole detection – each sensor node detects the formation of holes in the network independently and tries to cover the coverage hole upon its detection. Therefore, the proposed algorithm is distributed and scalable.

  2. 2).

    Energy efficient technique for coverage restoration – a sensor node with relatively higher residual energy which has detected the hole is given higher priority to increase its sensing range since the energy consumption of the sensor nodes is also depends on their sensing ranges. This balances energy consumptions of the sensor nodes.

3 Network model and terminologies

In this section, we present the network model of the proposed algorithm followed by definition of some of the terminologies used in the proposed algorithm.

3.1 Network model

We present here some assumptions for the network model used in the proposed algorithm as follows. A set of sensor nodes is deployed in a two-dimensional plane. All the sensor nodes become static once they are deployed. We assume that all the sensor nodes are provisioned with equal amount of energy. We also assume that all sensor nodes are aware about their locations. Initially, sensing range of all the sensor nodes is assumed to be equal, i.e., r s . We consider that each sensor node has the ability to increase its sensing range up to R * maximally where R * > r s . We assume that, with the sensing range R *, the target area is completely and redundantly covered whereas with the sensing r s , the target area is partially covered. It means that, initially coverage holes exist in the network. These holes will cover once the CHD-CR starts running. In other words, sensor nodes starts perform sensing tasks with variable sensing radii.

The energy model of the WSN is adopted from [16] in which both the free space and multi-path fading channels are used depending on the distance between the transmitter and receiver node. If the distance is less than a threshold value d 0, then the free space (fs) model is used, otherwise, the multipath (mp) model is considered. Let ε fs and ε mp be the energy required by amplifier in free space and multipath respectively, α tx and α rx be the energy dissipated in transmitting and receiving one bit respectively. Then the energy consumed by node i to transmit β-bit data packet to node j is given as follows

$$ {E}_{tx}\left(i,j\right)=\left\{\begin{array}{l}\begin{array}{cc}\hfill \left({\alpha}_{tx}+{\varepsilon}_{fs}{D}_{\left(i,j\right)}^2\right)\beta, \hfill & \hfill {D}_{\left(i,j\right)}<{d}_0\hfill \end{array}\kern0.24em \\ {}\begin{array}{cc}\hfill \left({\alpha}_{tx}+{\varepsilon}_{mp}{D}_{\left(i,j\right)}^4\right)\beta, \hfill & \hfill {D}_{\left(i,j\right)}\ge {d}_0\hfill \end{array}\end{array}\right. $$
(1)

where D (i, j) is the Euclidean distance between the node i and j and the energy consumed in receiving the β-bit data by node j is given by

$$ {E}_{rx}(j)={\alpha}_{rx}\beta $$
(2)

We adopt sensing energy model from [3]. The energy consumed by node i due to sensing is given as

$$ {E}_s(i)\propto {r}_s^4(i), $$
(3)

where, r s (i) is the sensing range of node i.

3.2 Terminologies

We use the following terminologies in the design of the proposed algorithm as follows.

Definition 1

(Target area). Let A be the target area to be sensed by the sensor nodes. We assume that the entire target area is organized as n × n virtual square girds called cells. The cell in the x th row and y th column of this area is denoted by c(x, y). For the simplicity and for the sake of designing the algorithm, we assume that the coordinates of the center of the cell c(x, y) is (x, y) and accordingly each cell will be identified by its center coordinate as shown in Fig. 1a. We also assume that each cell c is of size l c  × l c .

Fig. 1
figure 1

a Target area is divided into cells; b complete coverage of the target area; c cell c lies within the sensing range of node s i ; and d cell c lies outside the sensing range of node s i

Full size image

Definition 2

(Complete coverage). Let s 1, s 2, s 3, …, s n be the set of sensor nodes deployed in the target area. The complete coverage of the target area by the sensor nodes will be known by using the formula.

$$ \rho =\frac{\left(A\cap \left({\displaystyle \underset{i=1}{\overset{N}{\cup }}A\left({s}_i\right)}\right)\right)}{A} $$
(4)

If ρ = 1 means that every cell in the target area is covered by at least one sensor node where A(s i ) is the sensing area of the node s i . An example is shown in Fig. 1b.

Definition 3

(Covered cell). A cell c is covered by the sensor node s i if it satisfies the following condition

$$ c\left(x,y\right)\in A\left({s}_i\right)\kern0.36em iff\sqrt{{\left({x}_i\hbox{-} x\right)}^2+{\left({y}_i-y\right)}^2}\le {r}_s(i) $$
(5)

where r s (i) is the sensing range of s i . This is illustrated in Fig. 1c.

Definition 4

(Uncovered cell). A cell c is not covered by the sensor nodes s i if it satisfies the following condition

$$ c\notin A\cap A\left({s}_i\right) $$
(6)

This is illustrated in Fig. 1d in which c is not covered by sensor node s i .

4 Proposed algorithm

The proposed CHD-CR is divided into three phases namely update, coverage hole detection and coverage restoration. The proposed algorithm is not a data gathering algorithm. So, the proposed algorithm depends on certain coverage-aware clustering and routing algorithms, and tries to take advantage of certain control messages exchanged during clustering. So, we adopt CPCP-cc [12] as our data gathering algorithm. The proposed CHD-CR replaces the information update of CPCP-cc as shown in Fig. 2 and we refer it as coverage-aware clustering algorithm (CACA). In other words, last five phases of CACA is same as CPCP-cc. If the performance of CACA is better than CPCP-cc, it means that, this is due to CHD-CR algorithm.

Fig. 2
figure 2

Information update phase of CPCP-cc is replaced with CHD-CR

Full size image

Here, we present the three phases of the proposed CHD-CR algorithm in the following sections subsequently.

4.1 Update

Initially, a sensor node, say s i , finds the cells that fall within its sensing range r s (i). Let all such cells be denoted by Q(i). Let node s i be located at (x i , y i ) in the target area. Then a diameter of size 2r s(i) is drawn horizontally and vertically centered at location (x i , y i ). Divide r s(i) into H parts such that

$$ H=\left\lceil \frac{r_s(i)}{l_c}\right\rceil $$
(7)

The cells with the following co-ordinate points are fall within the sensing range r s(i) of node s i

$$ \begin{array}{l}\;\begin{array}{cc}\hfill {Q}_1=\left({x}_i+{k}_1\times {l}_c,\;{y}_i-{k}_2\times {l}_c\right),\hfill & \hfill {k}_1=0,\kern0.24em 1,\kern0.24em 2,\kern0.24em 3,\kern0.24em \dots, \kern0.24em H-1\hfill \end{array}\\ {}\begin{array}{cc}\hfill {Q}_2=\left({x}_i-{k}_1\times {l}_c,\;{y}_i-{k}_2\times {l}_c\right),\hfill & \hfill {k}_1=0,\kern0.24em 1,\kern0.24em 2,\kern0.24em 3,\kern0.24em \dots, \kern0.24em H-1\hfill \end{array}\\ {}\begin{array}{cc}\hfill {Q}_3=\left({x}_i-{k}_1\times {l}_c,\;{y}_i+{k}_2\times {l}_c\right),\hfill & \hfill {k}_1=0,\kern0.24em 1,\kern0.24em 2,\kern0.24em 3,\kern0.24em \dots, \kern0.24em H-1\hfill \end{array}\\ {}\begin{array}{cc}\hfill {Q}_4=\left({x}_i+{k}_1\times {l}_c,\;{y}_i+{k}_2\times {l}_c\right),\hfill & \hfill {k}_1=0,\kern0.24em 1,\kern0.24em 2,\kern0.24em 3,\kern0.24em \dots, \kern0.24em H-1\hfill \end{array}\end{array} $$

For each value of k 1, the value of k 2 ranges from 0, 1, 2, 3, …, H-1. Then,

$$ Q(i)=\left({\displaystyle \underset{k=1}{\overset{4}{\cup }}\left({Q}_k(i)-{\varphi}_k(i)\right)}\right) $$
(8)

Here, φ 1 ⊂ Q 1(i), i.e., set of cells lying outside the range r s (i) as shown in Fig. 3. Note that, we add some refinement steps in the simulation program to eliminate such cells i.e., φ. In the refinement, each node, say node s i calculates its distance from the cell belong to Q k (i), (1 ≤ k ≤ 4) using Eq. 5. This leads to elimination of all the cells belong to φ k , (1 ≤ k ≤ 4).

Fig. 3
figure 3

Illustrating example how to find set Q

Full size image

Similarly, sensor node s i finds the set of cells, it can cover in the maximum sensing range R *, and let all such cells be denoted by Q *(i) and accordingly

$$ {H}^{*}=\left\lceil \frac{R^{*}}{l_c}\right\rceil $$
(9)

The cells with following co-ordinate points are fall within the sensing range R * of node s i

$$ \begin{array}{cc}\hfill {Q}_1^{*}=\left({x}_i+{k}_1\times {l}_c,\;{y}_i-{k}_2\times {l}_c\right),\hfill & \hfill\;{k}_1=0,\kern0.24em 1,\kern0.24em 2,\kern0.24em 3,\kern0.24em \dots,\;{\left(H-1\right)}^{*}\hfill \\ {}\hfill {Q}_2^{*}=\left({x}_i-{k}_1\times {l}_c,\;{y}_i-{k}_2\times {l}_c\right),\hfill & \hfill {k}_1=0,\kern0.24em 1,\kern0.24em 2,\kern0.24em 3,\kern0.24em \dots,\;{\left(H-1\right)}^{*}\hfill \\ {}\hfill {Q}_3^{*}=\left({x}_i-{k}_1\times {l}_c,\;{y}_i+{k}_2\times {l}_c\right),\hfill & \hfill\;{k}_1=0,\kern0.24em 1,\kern0.24em 2,\kern0.24em 3,\kern0.24em \dots,\;{\left(H-1\right)}^{*}\hfill \\ {}\hfill {Q}_4^{*}=\left({x}_i+{k}_1\times {l}_c,\;{y}_i+{k}_2\times {l}_c\right),\hfill & \hfill\;{k}_1=0,\kern0.24em 1,\kern0.24em 2,\kern0.24em 3,\kern0.24em \dots,\;{\left(H-1\right)}^{*}\hfill \end{array} $$

For each value of k 1, the k 2 value range from 0, 1, 2, 3, …, (H-1)*. Then,

$$ {Q}^{*}(i)=\left({\displaystyle \underset{k=1}{\overset{4}{\cup }}\left({Q}_k^{*}(i)-{\varphi}_k^{*}(i)\right)}\right) $$
(10)

Here, φ *1  ⊂ Q *1 (i), i.e., set of cells lying outside its range R *. Note that, the node s i derives the set Q *(i) only once in the lifetime of the network since R * is fixed. Then the sensor node updates the set Q′(i) as follows

$$ Q^{\prime }(i)={Q}^{*}(i)\hbox{-} Q(i) $$
(11)

Here, Q′(i) represents the set of cells lying outside of the sensing range r s (i) and inside of the sensing range R *. Here, R* is same as R sense of CPCP-cc.

Remark 1

Finding sets Q, Q′ and Q * needs computation rather than communication. In other words, energy consumed due to computation is very less as compared to communication. Hence the proposed update is energy efficient.

Remark 2

In CPCP-cc, it is not shown how to find overlapping areas of the sensor nodes. So, this update phase of CHD-CR can be considered to find overlapping areas in CPCP-cc. Therefore, update phase of CHD-CR is not the additional cost on CACA as compared to CPCP-cc in terms of energy consumption and computation.

4.2 Coverage hole detection

Initially, a sensor node s i broadcasts a control message to all of its neighbor sensor nodes in the range R c where R c  = 2R *. The message includes its identification (ID) number, location information and Q(i). Let N *(i) denote the set of all neighbor sensor nodes of s i which fall within the range R c . If the node s i receives control message from all of its neighbors belonging to N *(i), then the node derives a new set Q ^(i) as follows

$$ {Q}^{\wedge }(i)={Q}^{\prime }(i)-\left({Q}^{\prime }(i)\cap \left({\displaystyle \underset{s_k\in {N}^{*}(i)}{\cup }Q\left({s}_k\right)}\right)\right) $$
(12)

If Q ^(i) = Ø (empty), it means that the cells belonging to the set Q′(i) are covered by the neighbor nodes of s i with their sensing ranges. If Q ^(i) ≠ Ø, it means a coverage hole is formed near the sensing area of the node s i due to death of a few neighbor sensor nodes. An example illustrated in Fig. 4. The flowchart of the coverage hole detection is shown in Fig. 5.

Fig. 4
figure 4

Formation of coverage hole in the network

Full size image
Fig. 5
figure 5

Flow chart of the coverage hole detection

Full size image

4.3 Coverage restoration

In every round, each sensor node, say s i updates its set Q ^ (refer Eq. 12) to detect the coverage hole near to it. Upon detecting the coverage hole, the sensor node s i starts estimating its new sensing range as follows. Let c(x, y) be the farthest uncovered cell belonged to Q ^(i). To cover the cell, the node s i calculates the distance with the cell as follows

$$ {D}_{\left({s}_i,c\right)}=\sqrt{{\left({x}_i\hbox{-} x\right)}^2+{\left({y}_i-y\right)}^2} $$
(13)

Before going to increase its sensing range, the node s i initiates its timers by using the formula

$$ t(i)=\left(\frac{E_m(i)-{E}_r(i)}{E_m(i)}\right){T}_{\max } $$
(14)

where, T max is the maximum allotted time to broadcast a control message, E m (i) and E r (i) are the initial maximum energy and residual energy of the node s i respectively. Once the timer of node s i expires, then the node updates its new sensing range which is equivalent to D (si, c), and then updates Q(i). It then broadcasts a control message in the communication range R c . The message includes its ID and Q(i). A node, say s j , whose timer is already set and receives the control message from node s i , then the node s j makes certain decision based on the following conditions

  1. 1).

    If Q ^(j) ⊆ Q(i), i.e., the node s i has covered all the cells that it intends to cover, then the node s j cancels its timer and maintains its sensing range unchanged. Cancelling timer also indicates that the residual energy of node s i is higher than node s j .

  2. 2).

    If Q ^(j) ⊆ Q(i), i.e., coverage hole is not covered completely by the node s i alone, then the node cancels its timer and updates its set Q ^(j) as follows

    $$ {Q}^{\hat{\mkern6mu} }(j)={Q}^{\hat{\mkern6mu} }(j)-\left({Q}^{\prime }(j)\cap Q(i)\right) $$
    (15)

    If Q ^(j) ≠ ∅ then the node s j starts finding the farthest uncovered cell (using Eq. 13) belonged to Q ^(j) and initializes its timer again. Once its timer expires, then the node updates its new sensing range, Q′(j) and Q ^(j). It then broadcasts a control message in the communication range R c . The flowchart of the coverage restoration is shown in Fig. 6. An example for coverage restoration is shown in Fig. 7.

    Fig. 6
    figure 6

    Flow chart of coverage restoration

    Full size image
    Fig. 7
    figure 7

    An illustrating example for coverage restoration

    Full size image

Remark 3

Note that a node with relatively higher residual energy is likely to increase its sensing range once it detects a coverage hole. This balances the energy consumption of the sensor nodes since the energy consumption is proportional to the sensing range (refer Eq. 3). Therefore, the proposed algorithm is energy-aware.

Remark 4

The coverage hole detection and restoration process starts after the update phase and before the sensor activation phase of CACA. At this point, no sensor nodes are in sleeping state. Therefore, increasing the sensing ranges of sensor nodes is a reasonable option.

Theorem 4.1

To detect a coverage hole in the network, sensor nodes need to broadcast the control message in the range R c where R c ≥ 2R *.

Proof

Let r s (i) and R * be the sensing range and maximum possible sensing range of the node s i respectively. Node s i builds Q(i) and Q ^(i) based on the sensing ranges r s (i) and R * respectively. Consider a situation where the node s j has sensing range r s (j) ≤ R * as shown in Fig. 8.

Fig. 8
figure 8

Illustrating R c = 2R *

Full size image

Let c * be the farthest cell belonged to Q *(i), i.e., the distance between the node s i and c * is R * maximally. If c * belongs to Q(j) of node s j , then the distance between the node s i and s j is not larger than 2R *. If s j is the only node which covers the cell c *, i.e., c * ∈ Q(j) and if s j cannot broadcast the control message in the range R c , then the node s i cannot confirm that the cell is covered by the node s j . Therefore, each node need to broadcasts the control message in the range R c where R c = 2R *.

Remark 5

Note that, communicating in R c is not extra energy consuming as compared to CPCP-cc since R c is equal to 2R sense of CPCP-cc. During the information update phase of CPCP-cc [9], nodes exchange their location information in the communication range which is equal to 2R sense .

Theorem 4.2

The time complexity of the proposed CHD-CR is O(n) for n sensor nodes in the network.

Proof

To find set Q ^, each sensor node needs to process n-1 neighbor nodes in worst case. This takes O(n) time complexity. Once a node detects coverage hole after processing its set Q ^, it sets its timer independently; but it broadcasts a control message in the range R c once its timer expires. This can be done in constant time. Therefore, the time complexity of the proposed algorithm is O(n).

5 Simulation results

In this section, we present the experimental results of the CACA and their comparisons with the two existing algorithms, CPCP-cc [12] and FBR [13]. We incorporate the energy consumed due to sensing in both the existing techniques (refer Eq. 3). We first compare the average energy consumption of CACA and CPCP-cc. Next, we compare CACA and CPCP-cc in terms of coverage lifetime. We also evaluate the impact R* on CACA. Finally, we show the results with similar experiments conducted using FBR as an underlying data gathering algorithm.

The whole target area of size 100 m × 100 m is divided into 1000 × 1000 cells. Sensor nodes are deployed in the target area randomly. Simulation program was written in Dev C++ and Matlab. The parameters and their values used in the simulation are given in Table 1. Here, coverage lifetime is defined as the number of rounds until 100 % coverage of the target is maintained by the sensor nodes with their sensing abilities.

Table 1 Parameters used in simulation
Full size table

5.1 Comparison with CPCP-cc

Here, we first compare the average energy consumption of the sensor nodes of CACA as well as CPCP-cc for various densities of sensor nodes in the same target area. Next, we show comparison of coverage lifetime of the algorithms for the same node densities respectively.

Figure 9a, b, c and d show the average energy consumption of the sensor nodes for 200, 300, 400 and 500 sensor nodes respectively. From these figure we observe that the CACA consume less energy as compared to CPCP-cc. Figure 10a, b, c and d show the coverage lifetime of the sensor nodes for 200, 300, 400 and 500 sensor nodes respectively. From these figures we observe that the CACA performs better than CPCP-cc.

Fig. 9
figure 9

Average energy consumption of sensor nodes

Full size image
Fig. 10
figure 10

Coverage lifetime

Full size image

The reasons for the better performance of the CACA over CPCP-cc are justified as follows

  1. 1.

    According to Remark 2 and Remark 5, CHD-CR is not extra cost on CACA as compared CPCP-cc in terms of energy consumption and computation.

  2. 2.

    Energy consumed due to sensing is high in CPCP, i.e., all the nodes perform sensing in the range R sense (=R * ) whereas in CHD-CR, sensing ranges are r s where r s ≤ R *.

  3. 3.

    Sensor nodes with relative higher residual energy are allowed to increase their sensing ranges to cover the hole. This is not only preserves the coverage but also balances the energy consumption of the sensor nodes.

  4. 4.

    The performance of CACA is better than CPCP-cc. This is due to CHD-CR algorithm since last seven phases of CACA is same as CPCP-cc (refer Fig. 2).

5.2 Impact of R *

Here, we study the impact of R * on CACA. In these experiments, we increase the value of R * form 10 m to 20 m while keeping other parameters remain unchanged. Figure 11 shows the coverage lifetime for 200, 300, 400 and 500 sensor nodes of CACA for different values of R *.

Fig. 11
figure 11

Impact of R * on the coverage lifetime

Full size image
Fig. 12
figure 12

CHD-CR added as an extra phase to FBR

Full size image

From these, we observe that the coverage lifetime of the proposed algorithm start increasing for values of R * ranging from 15 to 18 m and starts decreasing thereupon. This is may be due to maintain of high sensing ranges by the sensor nodes to cover the holes, increase in data redundancy because of higher sensing overlap among the nodes, and other overheads also associated with them. R c also increases since R c = 2R * and it leads to extra energy consumption and thereby reducing the lifetime of the sensor nodes.

5.3 Comparison with FBR

Here, we adopt FBR [13] as data gathering algorithm. The proposed CHD-CR added to FBR as shown in Fig. 12 and we refer it as coverage-aware FBR (CA-FBR). In other words, last four phases of CA-FBR is same as FBR. If the performance of CA-FBR is better than FBR, it means that, this is due to CHD-CR algorithm.

Figure 13a, b, c and d show the average energy consumption of the sensor nodes for 200, 300, 400 and 500 sensor nodes respectively. From these figure we see that CA-FBR consume less energy as compared to FBR. Figure 14a, b, c and d show the coverage lifetime of the sensor nodes for 200, 300, 400 and 500 sensor nodes respectively. From these figure we find that CA-FBR performs better than FBR.

Fig. 13
figure 13

Average energy consumption of sensor nodes

Full size image
Fig. 14
figure 14

Coverage lifetime

Full size image

6 Conclusion

In this paper, we have presented a new distributed algorithm for coverage hole detection and coverage restoration in wireless sensor networks. We have shown that the proposed algorithm detects the coverage hole locally and makes decision independently to restore it. Therefore the proposed algorithm is distributed and scalable. We have also shown that the sensor node which has relatively higher residual energy than the others was preferred to cover the hole by increasing its sensing range. Therefore, the proposed algorithm is also energy-aware. Through analysis and simulation results, we have shown that, adding CHD-CR to the existing algorithms improves their performance in terms of coverage lifetime.