Modified energy-proficient partial coverage methodology for optimizing coverage in WSN

Abstract

In energy-constrained wireless sensor network, one way is to the maximize network lifetime to cover all the targets (full coverage) is to group sensor nodes proficiently in such a way that each subset (called cover set) is capable enough of monitoring all the targets in the given area of interest. In some of WSNs applications, such as average temperature or humidity measurement in an area, neglecting some of the targets do not affects the outcome of the network. By excluding a fraction of targets, network lifetime increases considerably because fewer sensors are required to monitor targets in each cover set. This variant of coverage is called α-Coverage (0 < α < 1) or partial coverage. This paper proposes an energy-proficient heuristic to maximize the network lifetime under α–Coverage scenario. Under α–Coverage constraint, while neglecting a fraction (1-α) of targets, a set of neglected targets may never change. Due to this, some of the targets may face negligible or zero coverage. In order to avoid neglecting the same set of targets over subsequent cover sets, we further propose a minimum coverage bound for each target in the given networks. Simulation results show that the proposed heuristic achieves better solution as compared to the existing approaches while calculating the network lifetime.

1 Introduction

Due to increasing wireless communication development and advancement in embedded micro-sensing technology, wireless sensor networks (WSNs) become emerging requirements in many areas [1]. A wireless sensor network consists of tiny devices called sensors where sensors are embedded with microprocessor (to operate), limited internal memory (to store information) and a small onboard battery. There are various applications that include commercial and military security services, wildlife and battlefield surveillance, indoor monitoring, inventory tracking, biological detection, and smart buildings [16, 22]. There are certain applications, which includes wildlife monitoring, battlefield surveillance, fire detection, it is not possible to replace sensors once they are exhausted due to the limited battery power. Therefore, it becomes a vital need to optimize the sensors’ battery usages to keep alive the deployed network for a longer period. To monitor the provided region, sensor has a certain sensing range and can collect information within this range. The collected information (during monitoring) by each sensor should be forwarded to the base station in time for further processing [15, 21]. In general, coverage problems are widely categorized as area coverage [10, 19, 20, 24, 28] where a certain area is to be covered for the longest possible time, target coverage [2, 5, 11, 14, 18, 26] where a set of targets is covered until network exhausted and finally barrier coverage [6, 9, 25, 27]. The area coverage problem can be easily transformed into a target coverage problem in polynomial time [24]. Therefore, a single solution method for prolonging the network lifetime can be applied to both area and target coverage problems. In this paper, we consider only target coverage and discuss various possibilities and limitations of extending network lifetime with various addressed methodologies.

As discussed in [12, 17, 23], the scared resource in WSNs is sensors’ battery that is the prime constraint while prolonging the network lifetime. To provide the coverage, one can follow the brute force way to keep all the sensors active, so the deployed sensors cover the whole target set. Since the network is densely deployed, each target is generally covered by multiple sensors at a time. Thus, in order to maximize the network lifetime, instead of activating all the sensors, we can activate a group of sensors nodes (called set covers) such that each cover set can fully monitor all the targets. By activating these cover sets sequentially for a fixed amount of time (called cover lifetime), the network lifetime can be sufficiently increased. After finding all the cover sets, the total network lifetime can be calculated by adding all the covers lifetime.

Generally, many WSNs applications needs regular target coverage where each target is to be covered in every cover set for the monitoring purposes. But, there are other WSNs applications where the full (100%) coverage of the monitored region is not required. For example, calculating the average humidity/temperature in the surrounding area hardly has much effect if a small area is left unattended. For such applications, while providing coverage, avoiding a small fraction (1-α) of targets in each cover set can decrease the selected sensor in the cover sets, which in turn results in longer network lifetime [7, 29]. To facilitate this issue, in this paper, we address this variant of target coverage problem (TCP) called α-Coverage or partial coverage, where instead of covering all the targets, neglect a certain fraction (1-α, 0 < α < 1) of targets. By neglecting fractional targets, the lesser number of sensors will be required to cover the desired set of targets. This will increase the number of cover sets which in turn prolong the network lifetime. The generated set covers are now called α–Covers, and their working duration (i.e., lifetime) is known as α-Cover lifetime.

The major objectives of the α-Coverage Problem we will address in this paper are following:

• a) Calculate the network’s functional duration (i.e., network lifetime) for α-Coverage. The network lifetime is generally measured as the functional duration until the last α-Cover exists.

• b) Prolong the network lifetime by activating the α-Covers one after another.

• c) Analyze the effect of various α-values over network lifetime.

• d) Analyze the effect of varying sensors over time while achieving network lifetime.

The rest of the paper is organized as follows: In Section 2, we give full insight into the related work done so far on the given problem. Section 3 defines the α-Coverage problem with its working model, discusses the motivation behind the problem selection, and states the α-Coverage problem. Section 4, defines the various definitions required to understand the notations used so far. In section 5, we address the proposed heuristic for the α-Coverage problem. Section 6 shows all the simulation results and comparative analysis of the proposed heuristic with the existing one (Monica et al. [7]). Conclusion and future directions of the proposed research work are given in Section 7.

2 Literature review

There are various variants exists for the well-known target coverage problem in the wireless sensor network. When it comes to provide coverage, we can categorize the target coverage problem as full coverage, Q-Coverage and Partial coverage which is also known as α-Coverage. No. we will give brief overview of these variants of the target coverage.

• a. Target full coverage

During target full coverage, all the targets spread in the network should be covered by each and every cover set formed. In the literature, most of the addressed heuristics/algorithms regarding target full coverage problem in wireless sensor networks can be further divided as disjoint versus non-disjoint approach based on the sensor cover formation strategy. Now, we will give brief on these methodologies in this section.

2.1 Disjoint approach

The nature of selection of sensors in a cover set describes whether the given approach is disjoint or non-disjoint. If a sensor is not allowed to participate in the multiple sensors covers then the said methodologies is called disjoint approach [12, 24]. Slijepcevic et al. [24] compute the disjoint covers iteratively, where they have given priority to those sensors that cover poorly covered targets and covers maximum uncovered targets. Here, authors have restricted the participation of sensors by forming only disjoint cover sets, which in turn result in decreased network lifetime. Similarly, the authors in [12] follow the brute force way to keep all the sensors active, so the deployed sensors cover the whole target set without any failure.

2.2 Non-disjoint approach

If any application can afford to allow the participation of sensors in multiple cover sets then these kinds of methodologies are known as Non-disjoint approach [2, 13, 14, 18]. The Target Coverage Problem (TCP) of finding maximum possible covers in a given network is presented as the Maximum Set Covers (MSC) problem by Cardei et al. [2]. The discussed heuristic in this work is based on the greedy approach while selecting sensors to formulate the cover sets. Authors also proved the MSC problem to be NP-Complete in the same work. Several other works have been done [14, 18] to maximize the network lifetime by generating maximum possible set covers for the TCP. Further, authors in [14, 18] resolved this issue of restricted participation by forming non-disjoint cover sets iteratively to compute the network lifetime. Manju et al. [14] presented an energy-based heuristic where a sensor with highest remaining energy available is chosen first while forming the non-disjoint cover sets. Mini al. [18] proposed another weight-based algorithm where they follow the same methodology as in [14] but also added one more step to minimalize the so far generated cover set. By doing so, authors maximize the number of cover sets, which in turn prolong the total network lifetime. Author in [13] addressed another non-disjoint heuristic for target coverage which is based on the genetic algorithm paradigm. The addressed heuristic proposed a modified mutation operation where mutation operation is customized by keeping poorly covered target in concern because poorly covered targets are the only one who decides the upper bound on the total achievable network lifetime.

Since last few decades, Particle swarm optimization (PSO) algorithms are also introduced with respect to the target coverage problem in wireless sensor networks. The PSO based algorithms are considerably suitable for the optimization problem like target coverage. Wang et al. [26] proposed an energy-efficient full coverage algorithm which is based on the Particle Swarm Optimization (PSO) where they aimed for obtaining a balance between energy cost and coverage rate by adjusting the sensing radius of sensor. Kong et al. [11] also proposed one more heuristic for extending full target coverage with enhanced particle swarm optimization (PSO).

• b. Target Q-Coverage

There are certain scenarios where an application performs well under the regular coverage such that all the targets are covered by at least one sensor in each cover set. But, another application may require a different level of coverage (i.e., targets need to be covered by multiple sensors in a single cover set). Such type of quality-based monitoring is called Q-Coverage, where targets are covered by fixed Q-number of sensors in each cover set [5, 18]. Mini et al. [18] presented a heuristic for target Q-Coverage where each target is said covered only if it is covered by at least Q-number of sensors in each set cover. In order to form a cover set, this method chooses sensors based on weight probability calculated with the remaining energy of the sensor and its coverage. Once the set cover is formed, it will further go under one more step of minimization where extra sensors are removed. Authors in [5] also propose an energy-based heuristic for solving the target Q-Coverage where sensors with higher remaining energy are given priority over the rest of the sensor set. The currently constituted sensor cover is further minimalized to prolong the network lifetime as redundant sensors get removed in this process.

• c. Target α -Coverage (Partial Coverage)

Under α-Coverage, the objective is not to cover all the targets in the given field but to prolong the network lifetime, a fraction of targets (1-α) can be left uncovered in each α-Cover. By neglecting a small fraction of targets in each cover set, we have to choose fewer sensors in each cover, which results in longer network lifetime. Zhang et al. [29] defined the problem in terms of area coverage and presented a greedy heuristic to find an optimal solution. To form a cover set, this greedy method selects sensors with higher remaining energy. Monica et al. [7] presented the α-Coverage problem in a detailed way and gave a solution heuristic, which has two-fold criteria to assign priority to each sensor for taking part in the α-Cover. The first is to assign higher priorities to those sensors which have high remaining energy and cover the maximum uncovered target, and the second is that sensor should also cover the critical target(s). A target is said to be critical if the sum of those entire sensors’ battery covering it is minimum amongst all the targets in the given set of targets. While avoiding a fraction of the targets during coverage, it might be the case that the set of neglected targets never changes. Therefore, these neglected targets will never be covered, which might lead to some serious issues in many applications like crucial security services, fire detection and many more. To overcome this problem, Monica et al. [7] address regular α–Coverage problem and presented a minimum coverage threshold value for each target such that every target should be covered by that much unit of a lifetime in total. Carrabs et al. [3] presented another energy-efficient heuristic based on a genetic algorithm to improve the network lifetime for partial coverage. Authors in [4] addressed two-fold solutions for α–Coverage where firstly, they addressed the coverage problem in the form of Binary Integer Linear Programming (BILP) and then an energy based proficient Genetic Algorithm (GA) based heuristic is designed. The addressed GA based approach is concerned with achieving formulation of efficient covers’ scheduling which can be executed with minimal time complexity. Another work [8] also discuss partial coverage methodology based on Roman Dominating Sets. In the literature, Roman domination is a technique of colouring a graph’s vertices with three different labels (0, 1, 2), such that all the vertices with label 0 have an adjacent vertex with label 2, while the sum of the labels of nodes is minimized. Based on this formulation, a simple greedy algorithm is proposed to construct such a structure supported by three theorems.

In this paper, our focus is on maximizing the network lifetime by concerning poorly covered targets (called critical target) which are those covered by minimum number of the sensors in a homogenous network. These targets are the one which becomes uncovered first in the network and makes the network dysfunctional. So, if one can prolong the coverage of these critical targets in a proficient way, the network lifetime can be enhanced further. None of the work [3, 4, 7, 8, 29] has done so far on the α-Coverage problem, which considers these targets while forming cover sets.

Therefore, to enhance network lifetime for the α-Coverage, in this paper, we propose a new energy-efficient heuristic that provides better network α–lifetime than that in [3, 7]. In our work, we basically keep alive those sensors which are covering critical targets in order to maintain minimum coverage bound on individual targets so that the network lifetime can be enhanced further.

3 α-Coverage problem

In this section of the paper, the author first discusses the motivation behind the problem selection, give the working model, and then define the α-Coverage problem with its linear programming formulation.

3.1 Motivation

In order to illustrate the importance of the α-Coverage, consider an example (Fig. 1) consisting of 4 sensors (s₁, …,s₄) and 4 targets (t₁,…,t₄). Sensors’ coverage is shown in a circular dotted disk around it, and sensors are assumed to have 1 unit of battery life.

Fig. 1

Wireless network

By following the generic greedy methodology, we can find two cover sets under full target coverage (where α = 1) scenario. The first cover set consists of 2 sensors {s₁, s₂} with 1 unit set cover working duration, and the second cover set consists of {s₃, s₄} again with 1unit lifetime. Thus, the network lifetime for this scenario is 2 units in total. Now, allow each sensor cover to neglect at most one target (α = 0.75) to show the effect of α-Coverage. This time, three α-Covers are generated which are {s₁, s₂}, {s₃} and {s₄} each of 1unit lifetime, which results in 3 unit of total network lifetime. Thus, avoiding even one target in each cover set in this example, the total network lifetime is increased by 50%. The increment in network lifetime will be significantly more in the dense networks where sensors and targets are deployed in huge amounts.

α-Coverage is considerably better choice when certain application does not require complete coverage. For example, if anyone needs to calculate soil humidity or temperature in certain enclosed area then the partial coverage (α-Coverage) would be a great help. As we know that in the closed proximity, all the deployed sensors will capture almost the same reading of soil humidity and temperature. Hence, by avoiding few sensors’ data, one can maximize the coverage by deactivating these unnecessary sensor nodes. As we have already explained in above example (Fig. 1) that by avoiding only 25% of total targets, one can maximize the total network functional duration by 50%. This percentage increase in lifetime will be more when we can afford more targets to be neglected.

3.2 System model

Let S = {s₁,…, s_n} be the set of n sensors and T = {t₁,…, t_m} be the set of m targets which are deployed randomly. Each sensor s_i is assigned with sensing range R. Since we follow deterministic deployment, sensors and target locations are known in advance. Initially, each sensor s_i is assigned with battery b_i, and it will be functional until the battery is exhausted. For each sensor s_iϵS, let Ts_i ⊆ T is the set of all the targets covered by sensor s_i. Similarly, for each target t_jϵT, let St_j ⊆ S is set of all the sensors covering target t_j. As sensors and targets are fixed, and their locations are known in advance, Ts_i, ∀s_i and St_j, and ∀t_j are also known beforehand.

3.3 α-Coverage problem

Given S = {s₁,…s_n}, set of n sensors and T = {t₁,…t_m}, set of m targets randomly deployed in the fixed area of size M × M (where M is predefined). All the sensors are of fixed sensing range R and are initially loaded with 1 unit battery (b_i) to monitor targets in the given proximity. A target t_j, 1 ≤ j ≤ m, is said to be covered if it is falling within the sensing range of at least one sensor s_i, 1 ≤ i ≤ n.

For a given α ϵ [0,1], our objective is to find maximum possible α-Covers C^α_k, X(C^α_k), k = 1,…,p, (where C^α is a α–Cover and X(C^α_k) is α-Cover lifetime) such that the sum of the α-lifetimes (definition 5) can be maximized and none of the sensors is used beyond its assigned battery b_i. The mathematical formulation of the addressed α-Coverage Problem can be expressed as follows:

Let C^α₁,…,C^α_p be the set of all the feasible α-Covers for the given wireless sensor networks, and X₁,…,X_p be their respective α-Cover lifetimes in the same networks. For each sensor s_i, i = 1,…,n and for each α-Cover C^α_k, k = 1,…,p, we set a binary variable a_ik equal to 1, if sensor s_i is part of α-Cover C^α_k otherwise a_ik is 0. We assume the battery of sensor s_i is equals to b_i units. Thus, the network lifetime maximization problem can be written as follows:

$$ \mathit{\operatorname{Max}}\sum \limits_{k=1}^p{X}_k $$

(1)

$$ s.t.\sum \limits_{k=1}^p{a}_{ik}{X}_k\le {b}_i\kern0.5em \forall \mathrm{i}=1,\dots \mathrm{n} $$

(2)

$$ {X}_k>0,\forall \mathrm{k}=1,\dots, \mathrm{p} $$

(3)

The total network α-lifetime can be calculated from (1). The constraints in (2) ensure that none of the sensors should be used beyond its initial battery life assigned to it, and constraint (3) makes sure that each α-Cover should be meaningful (with non-zero α-Cover lifetime).

As addressed earlier, α-Coverage is superior over full coverage (α = 1) where the total network lifetime can be significantly increased by avoiding some fraction (1-α) of targets and only covering T_α targets. In the worst-case scenario, each α-Cover avoids the same set of targets; therefore, it may be the case that the individual target coverage for those avoided targets is very less or negligible. To overcome this problem, we propose to put a minimum coverage bound, called X_min, on the coverage of each target such that every target should have coverage not less than this threshold (X_min).

4 Definitions and notations

As we have discussed in Section 2, consider S = {s₁,…, s_n} be the set of n sensors and T = {t₁,…, t_m} be the set of m targets which are deployed randomly. Each sensor s_i is assigned with sensing range R and sensors are initially assigned battery (b_i) to monitor targets in the given proximity. A target t_j, 1 ≤ j ≤ m, is said to be covered if it is falling within the sensing range of at least one sensor s_i, 1 ≤ i ≤ n.

In this section, we will discuss some basic terminology used in the rest of the paper and the required definitions to explain the α-Coverage problem in WSNs.

Definition 1: Sensor-cover (C)

A sensor cover C is a set of sensors such that all the targets in T are covered by them. Therefore, we can say that C ⊆ S such that T_C ≡ T, where T_C is the set of targets covered by sensors in C.

Definition 2: α-cover (C^α)

For a given α, 0 < α < 1, the α-Cover C^α is a subset of sensors that covers at least T_α targets such that |T_C^α| ≥ T_α, where T_α = m × α. Thus, we can say that C^α ⊆ S s.t. T_C^α ⊆ T. To illustrate this case, consider 5 targets in T. If we set the value of α such that T_α = 4, then α-Cover, C^α should cover at least 4 targets out of 5. Therefore, we can also say that for given α = 1, every sensor cover C is C^α.

Definition 3: Minimal α-cover

The α-Cover, C^α, is a minimal if for any α-Cover C^α’, C^α’ ⊆ C^α if and only if C^α’ = C^α.

Definition 4: α-cover lifetime (X (C^α))

The maximum lifetime which can be assigned to α-Cover C^α is the smallest available battery lifetime of sensors which are part of it. Thus:

$$ X\left({C}^{\alpha}\right)\equiv {\mathit{\operatorname{Min}}}_{s_i\in {C}^{\alpha }}\left({b}_i\right) $$

Definition 5: α-lifetime (N^α)

As discussed earlier, α-Covers are activated sequentially, one after the other. Thus, the total networks α-lifetime is the sum of all the α-Covers lifetime (X(C^α)) generated is:

$$ {N}^a=\sum \limits_{k=1}^pX\left({C}^a\right) $$

Definition 6: Minimum coverage bound (X_min)

The minimum coverage bound for any target in the α-Coverage problem should be equal to the upper bound on total network lifetime in full coverage (where α = 1). Therefore, we can say that:

$$ {\boldsymbol{X}}_{\boldsymbol{min}}={\min}_j{\varSigma}_i{R}_{ij}{b}_i. $$

Where R_n × m is the sensor–target matrix which is defined as follows:

$$ {R}_{ij}=\left\{\begin{array}{c}1, if\ \mathrm{sensor}\ {s}_i\ \mathrm{covers}\ \mathrm{target}\ {t}_j\\ {}0,\kern7.5em otherwise\end{array}\right. $$

(4)

Since sensors and target locations are fixed in the given wireless sensor network, the sensor-target matrix R (4) can be calculated beforehand at the time of network deployment. Now, the minimum coverage bound for a given α- Coverage can be used as a constraint on the total coverage of a target as follows:

$$ \sum \limits_{k\mid t\in {T}_{C_k^{\alpha }}}{X}^k\ge {X}_{\min_{\forall \mathrm{t}\upepsilon \mathrm{T}}} $$

(5)

The constraints in (5) ensure that none of the targets should be covered less than X_min units in total by a given set of α-Covers. In the next section, we address the proposed algorithm to solve the α-Coverage problem in the given WSNs.

Definition 7: Upper bound (U)

The optimal upper bound is directly depends on the critical target coverage value. As we have already discussed in section 2 of the manuscript that critical target is poorly covered target(s) amongst all the targets in the network. To calculate the upper bound on the network lifetime, one has to sum-up the sensors’ batteries which are covering critical target. The following example illustrates how the upper bound is calculated [8].

Illustration

Consider 3 targets, M1, M2, and M3 and 4 sensors, namely N1, N2, N3 and N4. The sensors-target coverage matrix (4) is given below. We also assume unit battery (bi) assigned to each sensor.

	M1	M2	M3
N1	1	0	1
N2	1	1	0
N3	1	0	1
N4	1	1	1

As shown in the above matrix, M2 target is the critical target here (i.e. summation of covering sensors’ batteries is 2). Hence, for this scenario, the upper bound is of 2 units in total. So, none of the heuristics designed so far can achieve network lifetime more than 2 units for this given network.

Lemma 1

The optimal solution of α–Coverage problem is bounded above by the upper bound (U).

The full target coverage problem (Cardei et al. [2]) is NP-complete and we also observed that the α–Coverage problem is a special case of full target coverage problem. So, it is straight forward to conclude that α–Coverage problem is also NP-complete. Hence, we have the following theorem.

Theorem 1: α–Coverage problem is NP–complete

As shown in the above Illustration, one can observe that the upper bound calculation is completely dependent on the coverage of critical target(s). Thus, in order to prolong the total achievable network lifetime, one has to prolong the coverage of such critical targets. We have observed that in the literature, the methodologies discussed in [2, 5, 11, 14, 18, 26] do not consider prolonging the critical target which in turn results in decreased network lifetime. In the next section, we discuss the proposed heuristic where we consider α–Coverage of targets and the proposed heuristic tries to prolong the coverage of th critical targets in order to maximize the total achievable network lifetime.

5 A heuristic for maximizing α–lifetime

This section describes the proposed heuristic for solving the α-Coverage Problem in the WSNs. It is said that during the full coverage (α = 1), a given network is said to be exhausted when a single target in the network becomes uncovered. Similarly, in the case of α–Coverage, the network will exhaust when more than (1-α) fraction of targets becomes uncovered at any point in time. Further, in the worst case, the set of avoided targets never changes in many α-Covers. Due to this, the individual target coverage becomes negligible, which is not acceptable in many crucial applications. In order to avoid such problem, we propose a new energy-efficient heuristic (call it α-Critical) in which the minimum coverage of each target is maintained. Since the critical targets become uncovered first, we propose to keep alive those sensors (critical sensors) for the longest possible time which are covering the critical targets. The proposed heuristic (α-Critical) consists of the following major steps.

• Step I: Generate α-Covers

In order to form α-Covers iteratively, we first identify all the critical targets and respective critical sensors. Then, we select the minimum number of critical sensors such that all the critical targets are covered by them collectively. For the rest of the targets, we try to avoid selecting critical sensors in the current α-Cover.

• Step II: Assign α-Cover Lifetime (X (C^α)

In this step, we assign a fractional lifetime (Definition-4) to the α-Cover generated in Step-1. Our proposed algorithm assigns a small (X (Cα) units of lifetime to the cover set generated so far. By assigning a small constant fraction of total battery (b), we try avoiding the consumption of the total energy of sensors and make these sensors available for the consecutive α-Cover.

• Step III: Update the batteries of sensors

In order to avoid the repeated generation of the same α-Cover in consecutive iterations, the priority of a sensor reduces once it is used in a α-Cover and as a result the consecutive construction of α-Cover in the next iteration tries to avoid repeating the same sensor as in previous step α-Cover.

The complete process followed in the proposed heuristic (α-Critical) is presented in the following pseudocode.

A detailed outline of the proposed heuristic is given in α-Critical: Line 1 finds out all the critical targets critical sensors and based on the chosen α, T^α (T^α = n × α) is also calculated. The α-Cover is generated in lines 2 through 19. In order to prolong the α-lifetime of the network, the proposed heuristic first select a minimum number of sensors those covering the critical targets (line 5–10). After selecting the minimum number of these sensors, more sensors with the highest remaining energy, which are covering the maximum number of uncovered targets (out of T^α) are selected in the α-Cover generated so far (line 13–19). In a dense network, it might be the case that generated α-Cover may not be minimal, so by using Minimal_Cover, α-Cover is minimized (line 20). The α-lifetime of generated α-Cover is calculated, and batteries for those sensors in C^α are updated (lines 21–24).

Time complexity analysis

In line 4 (α-Critical Algorithm), the selection of the critical target and sensor requires to check the residual energy of the covering sensors of each candidate target and the sensor contribution evaluation considers for each sensor the coverage time so far of its targets: therefore, each of these operations require O(nm) time at most. Every other operation requires either O(n) or O(m) time at most. Thus, the overall time complexity of the proposed algorithms is O(n²m²). When we compare the time complexity of the existing similar work [7], we find the there is no much difference between both the methodology when it come so execute the overall procedure.

In the next section, the detailed simulation results are discussed to prove the effectiveness of the proposed heuristic.

6 Performance analysis

In this section, we carried out several sets of the simulations to claim the superiority of our heuristic (α-Critical). All simulations have been performed in MATLAB (R2016) on a core i3 processor with 2.10GHz processor and 4GB RAM system. For experimentation, a fixed square area of size 200 M*200 M is taken in which 15 targets and a varying number of sensors (50–150) are randomly deployed. A pseudo-random number generator function is used to generate sensors’ coordinates. We assume the homogenous sensors ranging from 25 to 150 with fixed sensing range R_s = 70 M. In the simulation, each value is an average of 50 instances on randomly generated test cases. We assign each sensor a unit battery life, and for each α-Cover lifetime, we take X(C^α) = 0.50 unit. We put regularity conditions on every target’s coverage by considering the value of X_min (Definition 6), which is calculated in every problem instance. Therefore, in our heuristic, none of the targets will have coverage less than that of X_min.

6.1 Experiment 1

Here, we considered α = 1, 0.85, 0.75, 0.5, so, each α-Cover must contain T^α = 15, 13, 11 and 8 targets respectively. Now, we compare the optimal network lifetime achieved by the proposed heuristic (α-Critical) under full coverage (α = 1) and α–Coverage. We simulated for different values of α to show the importance of neglecting a fraction of targets over network lifetime achieved.

Table 1 shows the network lifetime achieved by α-Critical for various values of α and sensors (S). As shown in Table 1, the α-Coverage has a significant impact on network lifetime achieved by the proposed heuristic (α-Critical). For α = 0.85 (T_α = 13), the improvement in an achieved lifetime is from 46.80% (S = 25) to 98.67% (S = 150) as compared to the network lifetime achieved under full coverage (α = 1). This improvement in network lifetime achieved by α-Critical is more when the number of neglected targets (T_α = 11, 8) increases. For a given set of sensors (S = 50), the achieved network lifetime by α-Critical largely improve from 62.68% (α = 0.85, T_α = 13) to 195.52% (α = 0.50, T_α = 8) as compared to the network lifetime achieved under full coverage (α = 1). Thus, by neglecting a fraction (1-α) of targets, the total network lifetime can be hugely improved by the proposed method (α-Critical) for the α-Coverage.

Table 1 Network lifetime achieved by the proposed heuristic (α-Critical) under various values of α and the number of sensors (S)

We can also observe from the above table that the network lifetime achieved by the proposed heuristic increases with an increase in number of sensors in the network. This is due to the fact that the same number of targets are now covered by a greater number of sensors in the same terrain which in turn increases the number for α-covers. Since, the total network lifetime is summation of all the α-lifetimes, we obtain prolonged network lifetime.

6.2 Experiment 2

In this section, we compare the network lifetime achieved by proposed heuristic α-Critical and α-Greedy by Monica et al. [7] for the α-Coverage under various values of α (1, 0.85, 0.75, and 0.50). We simulated for a fixed set of targets that equals 15 and varies sensors from 25 to 150. Table 2 shows the network lifetime achieved by both the heuristics. Each value in the Table 2 is an average of 50 instances.

Table 2 α-lifetime achieved by proposed algorithm α-Critical and α-Greedy by Monica et al. [7]

Table 2 depicts the percentage improvement in network α-lifetime achieved by α-Greedy [7] heuristic and our proposed heuristic (α-Critical) with various α and varying sensors 50 to 150. It is clearly shown that network α-lifetime achieved by α-Critical is greater than those achieved by α-Greedy for all the sensor sets. The percentage gaps between α–network lifetimes achieved by both the heuristics increases as we increase the number of targets to be neglected.

As shown in Table 2, by varying α from α = 0.85 (T^α = 13) to α = 0.50 (T^α = 8) and S = 150, the improvement in lifetime achieved by α-Critical is 13.09% to 25.67% as compared to α-Greedy. It can be observed that there is a significant improvement in total α–network lifetime achieved by our algorithm as compared to the α-Greedy. This is due to the fact that our heuristic tries to keep alive those sensors which are covering critical targets for a longer period by selecting the only minimal number of such critical sensors in each α-Cover. The α-Critical selects more sensors till the rest of the targets are covered. By doing so, it might be the case that in generated α-Cover, some of the targets may be redundantly covered. Therefore, in order to remove these extra sensors, we propose to minimize (Minimal_Cover) the generated α-Cover in each iteration of α-Critical. Thus, our heuristic outperforms the heuristic by Monica et al. [7] while achieving α-lifetime for α-Coverage. Simulation results clearly prove our claims. The result obtained by our heuristic (α-Critical) and the α-Greedy by Monica et al. [7] is also depicted in Fig. 2.

Fig. 2

α-lifetime achieved by α-Critical and α-Greedy [7] with varying sensors and α

As depicted in Fig. 2, the total α-lifetime achieved by our algorithm is always better than those achieved by Monica et al. [7] approach under various values of α. One can also observe from Fig. 2 that gap between the α-lifetimes achieved by our α-Critical and α-Greedy [7] increases as an increase in the number of sensors in the networks. This is due to the fact that when increasing number of sensors in the same sized area, coverage of targets is also increasing. This in turn prolong the total achieved network lifetime by both the proposals. Further, the gap in network lifetime achieved by both the heuristics also increases because of the nature of selection of sensors in cover set by the proposed α-Critical.

6.3 Experiment 3

Figure 3 shows the α-lifetimes calculated under various values of α (i.e., α = 1, 0.85, 0.75, and 0.50) and sensors between 25 and 150. We have taken an average of 50 instances for each value. It is clearly depicted in Fig. 3 that the network lifetime achieved by the proposed heuristic is prolonged with a lesser value of α. This is due to the fact that, with a lesser value of α, this approach discards more targets in each cover set, which in turn results in the increased network lifetime.

Fig. 3

α-lifetime achieved by proposed heuristic under various values of α and varying sensors

As observed throughout simulations, it is depicted in all the experiments that the proposed heuristic performs better when compared with the existing method [7]. Further, it is clearly depicted that the smaller α results in a better network lifetime. This happens so because, with a smaller value of α, more number of targets can be left unattended in cover sets, which in turn prolong the achieved network lifetime. The value of α can be decided wisely depending on the application requirement.

7 Conclusion and future work

In this paper, we have discussed an emerging variant of the target coverage problem called α-Coverage. This variant is useful for those WSNs applications where keeping a fraction of targets does not affect the compound result. To maximize the lifetime gain, this work discusses an energy-efficient algorithm for the α-Coverage that maximizes the network lifetime by keeping alive those sensors that covers critical targets as they will get left uncovered first. Thus, the network α-lifetime can be maximized only by limiting the usages of those sensors covering critical targets. The proposed algorithm outperforms the existing heuristic [7]. In order to avoid the same set of targets to be neglected in each iteration, this work also proposed a minimum coverage bound for each target by covering it at least X_min times.

In the future, this work can be extended for other variants of the coverage problem which includes, target connected coverage, target connected with adjustable sensing ranges, target K-Coverage and many more. Further, we also plan to design meta-heuristic for some of the variants as meta-heuristics-based algorithms proven to better for an optimization problem.