Multi-layer Genetic Algorithm for Maximum Disjoint Reliable Set Covers Problem in Wireless Sensor Networks

Abstract

Densely deployment of sensors is generally employed in wireless sensor networks to ensure complete target coverage for a long period of time. Many sensors scheduling techniques have been recently proposed for prolonging the network lifetime. Scheduling sensors into a maximum number of disjoint sets has been modeled, in the literature, as disjoint set covers (DSC) problem which is a well-known NP-hard optimization problem. Unlike other attempts which considers only a simple disk sensing model, this paper addresses the problem of finding the maximum number of set covers while considering a more realistic sensing model to handle uncertainty into the sensors’ target-coverage reliability. The paper investigates the development of a simple multi-layer genetic algorithm (GA) whose main ingredient is to support selection of a minimum number of sensors to be assigned to maximum number of set covers. With the aid of the remaining unassigned sensors, the reliability of DSCs provided by the GA, can further be enhanced by a post-heuristic step. By identifying the upper bound of number of disjoint set covers, the GA can successively construct covers, each of which is of minimal sensor cost. Performance evaluations on solution quality in terms of both number of set covers and coverage reliability are measured and compared through extensive simulations, showing the effectiveness of the proposed GA.

1 Introduction

Recently, many applications, ranging from remote harsh field monitoring to surveillance and smart homes, have been directed towards studying and building their backbones based on Wireless sensor networks (WSNs). The dense ad-hoc deployment of such sensors from an aircraft into the monitoring area can results in network configurations with adequate targets coverage level. However, recharging or replacing a sensor’s battery is generally infeasible. Hence, efficient utilization of the limited energy is one of the critical design considerations in WSNs. Energy-aware mechanism has been substantially pursued by the research community in order to form long lived WSNs. Energy saving techniques can generally be classified in the following categories:

• 1. Energy-efficient data aggregation, gathering and routing;

• 2. Power management by adjusting the transmission and/or sensing range of sensor nodes; and

• 3. Sensor wake-up scheduling to alternate between active and idle state.

In this paper, we will consider the third approach to prolong the WSN lifetime while completely monitoring the targets set. In this class of techniques, sensor activities are scheduled into disjoint sensor subsets, or set covers, and each set cover (hereinafter, interchangeably called, sensor cover) needs to satisfy the coverage constraints. At each interval of the whole WSN’s lifetime, only one sensor cover (active sensor cover) is working to provide the required sensing functionality while the remaining sensor covers, with their sensors, are in the low-energy sleep mode. Once the active sensor cover runs out of energy, another sensor cover will be selected to enter the active mode and provide the functionality continuously. Thus, the more sensor covers we can find, the longer sensor network lifetime will be prolonged. It has been proven that this problem is a generalization of the minimum set cover problem [1] and proves its NP-completeness [2, 3].

Many attempts in the literature have been proposed for solving DSC problem in WSNs using either heuristic or meta-heuristic (like genetic algorithms) approaches. Different scheduling rules determine when sensors change to be active or sleep. In localized and distributed realizations, sensors periodically investigate their neighborhood and decide whether to change their operation modes [4–11].

In [2], a heuristic approach called the “most constrained–minimally constraining covering (MCMCC)” is proposed to select and successively activate mutually exclusive sets of covers, where every set completely covers the entire area. Their method gives priority to sensors which cover a high number of uncovered fields, cover sparsely covered fields and do not cover fields redundantly. This method achieves energy savings by increasing the number of disjoint covers. The DSC problem has been solved in [12] using integer programming. The DSC problem is reduced to a maximum flow problem and solved using mixed integer programming. By a branch and bound method, the maximum covers based on mixed integer programming algorithm (MC-MIP) acts as an implicit exhaustive search to guarantees finding the optimal solution.

The definition of DSC problem has been re-formulated in [3, 13], and [14] to include additional coverage constraints. The definition of DSC problem has been generalized in [3] to a maximum non-disjoint set covers (MSC) problem and solved it using, linear programming, and greedy heuristics. The extended problem in MSC lets the sensors to participate in multiple sets. In [13], the DSC problem has been extended to include connectivity constraint as well. Then, the Connected Set Covers (CSC) problem has as objective finding a maximum number of set covers such that each sensor to be activated should be connected to the base station. In [14], DSC problem has been extended to include sensor coverage-failure probability. Each sensor is associated with sensor’s failure probability (comes from several facts, e.g., manufacture, weather in the monitoring area, interferences to the sensors, or unexpected accidents). The proposed Maximum Reliability Sensor Covers (MRSC) problem has been solved in [14] using a heuristic greedy algorithm to compute the maximal number of set covers that satisfy a user specified coverage-reliability threshold.

The work in [15–17] also provides solutions to the DSC problem in WSNs but using the meta-heuristic framework of evolutionary and genetic algorithms. Like the previous mentioned heuristic methods, the genetic algorithms (GAs) proposed in [15–17] assume simple and common isotropic (i.e., disc) sensing model. Each sensor in this definite range law approximation model is associated with a sensing area which is represented by a circle and it successfully detects anything falling only within its sensing range. In a more realistic scenario, the sensing region of a sensor could be irregular, resulting in imperfect sensor approximation model. The coverage in this case could be expressed in probabilistic terms [18–20]. In probabilistic sensing model, there is a measure of uncertainty in sensor signal-detection being expressed by a value from 0 to 1. For reliable coverage with certainty threshold $c_{th}$, the detection uncertainty of each target should not exceed $1-c_{th}$.

According to [21], the upper bound, $ub$, of the maximum number of disjoint complete set covers depends on the size of the target area, the total number of sensors, the sensors’ locations, and their sensing ranges. $ub$ can be estimated as the minimum number of sensors covering the most sparsely covered target, and thus can be computed by polynomial-time algorithms. It has been shown that for the same deployment of sensors and targets, $ub$ can be increased by enlarging the sensing radius of each sensor [15–17, 21]. However, under probabilistic sensing models, the certainty threshold $c_{th}$ should also effect on the number of sensors reliably covering the most sparsely covered target. As more reliability degree to cover a target is required, $ub$ becomes smaller.

Unlike other related works, this paper concerns with the applicability of the genetic algorithm for solving the DSC problem while assuming a probabilistic sensing model to reflect the uncertainty in sensor readings. The main contributions of this paper are as follows:

• 1. With the de-facto definition of the simple genetic algorithm, up to $ub$ covers can be identified gradually, each of which should maintain low cost in terms of number of sensors to completely cover the targets within the specified certainty threshold.

• 2. With the incorporation of unassigned sensors, the coverage reliability of each set cover, and hence, the total network’s coverage reliability can be further improved. A post-heuristic operator weighs each assigned and/or unassigned sensor to the membership of each set cover.

In what follow we first briefly describe the DSC problem in WSNs and its related system model. Then, in Sect. 3, we introduce the proposed multi-layered genetic algorithm and a post-heuristic operator tailored for solving DSC problem in WSNs. The results of the proposed genetic algorithm are then compared with a related work in Sect. 4. Finally, Sect. 5 concludes the current work and hints some further ramifications.

2 DSC Problem in WSNs

In order to model the system, we will assume that the investigated WSNs have 2D sensing area $\mathcal{A}$ with known $\hbox {size }(X_{max} ,Y_{max} )$. We will also assume that $\mathcal{A}$ has a set $\mathcal{T}$ (i.e., target set) of $n$ targets with known locations, i.e., $\mathcal{T}=\{\left( {x_{t1} ,y_{t1} } \right) ,\left( {x_{t2} ,y_{t2} } \right) ,\ldots ,(x_{tn} ,y_{tn} )\}$. There are $m$ homogenous sensors $\mathcal{S}=\{\left( {x_{s1} ,y_{s1} } \right) ,\left( {x_{s2} ,y_{s2} } \right) ,\ldots ,(x_{sm} ,y_{sm} )\}$ having the same sensing range $R_s$. All the sensors are dropped randomly in $\mathcal{A} \quad (1\le \forall i\le m | \left( {x_{si} ,y_{si} } \right) =([0,X_{max} ],[0,Y_{max} ]))$. Depending on the sensing range $R_s$, each sensor will be responsible for sensing and covering a part of $\mathcal{A}$. We will consider a probabilistic sensing model [19, 20] to define the notion of the probabilistic coverage of a target $\mathcal{T}_j =\left( {x_{tj} ,y_{tj} } \right)$ by a sensor $s_i$.

$$\begin{aligned} Coverage\left( {s_i ,t_j } \right) =\left\{ {{\begin{array}{ll} 0 &{} {if \,\,R_s +R_u \le d(s_i ,t_j )} \\ {e^{-\lambda a^{\beta }}}&{} {if \,\, R_s -R_u <d(s_i ,t_j )} \\ 1 &{} {if \,\, R_s -R_u \ge d(s_i ,t_j )} \\ \end{array}}} \right. <R_s +R_u \end{aligned}$$

(1)

where $R_u$ is a measure of the uncertainty in sensor detection. $d\left( {s_i ,t_j } \right)$ is the Euclidean distance $\sqrt{(x_{si} -x_{tj} )^{2}+(y_{si} -y_{tj} )^{2}}$ between sensor $s_i$ and target $t_j$. $a=d(s_i ,t_j )-(r_s -r_u )$, and $\lambda$ and $\beta$ are probabilistic detection parameters to measure detection strength when a target point lies within the interval $\{R_s -R_u ,R_s +R_u \}$. It causes coverage value to exponentially decrease as the distance increase. All points that lie within a distance of $R_s -R_u$ from the sensor are said to be 1-covered. Beyond the distance $R_s +R_u$, all the points have 0-coverage by this sensor (see Fig. 1).

Fig. 1

Probabilistic sensing model

To save energy and prolong WSN’s lifetime, sensors in the sensor set $\mathcal{S}$ should be divided into duty-cycling sensor cover subsets, each of which can cover all the interested targets in $\mathcal{T}$. In the literature and under the traditional Boolean sensing model (Eq. 2),

$$\begin{aligned} Coverage\left( {s_i ,t_j } \right) =\left\{ {{\begin{array}{l@{\quad }l} 1 &{} if \,\, d\left( {s_i ,t_j } \right) \le R_s \\ 0 &{} otherwise \\ \end{array} }} \right. \end{aligned}$$

(2)

the definition of the sensor cover could be formulated as:

Definition 1

(Sensor Cover). Given a WSN consists of target set $\mathcal{T}$ and sensor set $\mathcal{S}$, where each sensor $s_i \in S$ can be represented as a subset $\mathcal{T}_i \subset \mathcal{T}$, such that $tj\in \mathcal{T}_i$ if and only if $Coverage\left( {s_i ,t_j } \right) =1$. Any subset $\mathcal{S}_i \subset \mathcal{S}$ that can completely cover all the target set $\mathcal{T}$ is termed as a sensor cover.

According to the above definition, the disjoint (sensor/set) cover problem (DSC) can be formulated as:

Definition 2

(Disjoint Sensor Covers Problem-DSC). Given a finite collection $C$ of subsets of a target set $T$, find the family of the maximum number of disjoint sensor covers $\mathcal{S}_1 , \mathcal{S}_2 , \ldots , \mathcal{S}_{max}$ for $T$. Every sensor cover $C_i$ is a subset of $C$, $C_i \subseteq C$, such that every target element $t_k$ of $T$ belongs to at least one sensor member of $C_i$, and for any two sensor covers $C_i$ and $C_j,\, C_i \cap C_j =\emptyset$.

However, considering probabilistic sensing model, the definition of the traditional sensor cover needs to be re-formulated, here, as:

Definition 3

(Reliable Sensor Cover). Given a WSN consists of target set $\mathcal{T}$ and sensor set $\mathcal{S}$, where each sensor $s_i \in S$ can be represented as a subset $\mathcal{T}_i \subset \mathcal{T}$, such that $tj\in \mathcal{T}_i$ if and only if $Coverage\left( {s_i ,t_j } \right) \ge c_{th}$. Any subset $\mathcal{S}_i \subset \mathcal{S}$ that can satisfy a user coverage constraint $c_{th}$ to cover all the targets in $\mathcal{T}$ is termed as a reliable sensor cover or reliable set cover. Formally speaking:

$$\begin{aligned} Cover\left( {\mathcal{S}_i ,\mathcal{T}} \right) =\left\{ {{\begin{array}{l@{\quad }l} 1 &{} if\,\, \forall t\in \mathcal{T}\rightarrow \exists s\in \mathcal{S}_i |Coverage\left( {s,t} \right) \ge c_{th} \\ 0 &{} otherwise \\ \end{array}}} \right. \end{aligned}$$

(3)

Now, the problem of finding the maximum number of disjoint set covers (DSC) could be turned into the problem of finding the maximum number of disjoint reliable sensor covers (DRSC), and can be formulated as:

Definition 4

(Disjoint Reliable Sensor Covers Problem-DRSC). Given a collection $\mathcal{S}$ of reliable subsets of a finite set $\mathcal{T}$, find the maximum number of disjoint reliable covers for $\mathcal{T}$. Every cover $\mathcal{S}_i$ is a subset of $\mathcal{S},\, \mathcal{S}_i \subseteq \mathcal{S}$, such that every element $tj$ of $\mathcal{T}$ belongs to at least one member of $\mathcal{S}_i$, and for any two covers $\mathcal{S}_i$ and $\mathcal{S}_j,\, \mathcal{S}_i \mathop \cap \nolimits ^ \mathcal{S}_j =\emptyset$. Now, the upper bound $ub$ of the maximum number of disjoint reliable covers is determined by the most sparsely covered target and can be calculated as:

$$\begin{aligned} ub=\left| {\mathcal{C}\mathcal{S}} \right| =\mathop {\arg \;\;\;\; min}\limits _{i=1,2,\ldots ,n} (\left| {\mathcal{S}_i } \right| ) \end{aligned}$$

(4)

where $\mathcal{C}\mathcal{S}$ denotes the set of sensors (called Critical sensors Set) covering target $ti$ with certainty equal to or larger than a user specified threshold $c_{th}$. As the most sparsely covered target only covered by $ub$ sensors, the maximum number of disjoint reliable covers $N$ is no larger than $ub$ (i.e., $N\le ub$).

3 The Proposed Multi-layer Genetic Algorithm

The GA simulates the biological processes of natural selection, reproduction, and mutation to iteratively evolve species of individual solutions to become more and more adapted to the problem environment. The proposed GA can be described as a process formulated in multi-layered fashion. Let $\mathcal{S}_{sleep}^0 =\mathcal{S},\, \mathcal{S}_{active}^0 =\emptyset$ and $GA^{i}:\mathcal{S}_{sleep}^{i-1} \rightarrow \{\mathcal{S}_{sleep}^i ,\mathcal{S}_{active}^i \},\, i=1,2,\ldots ,ub$ be the $i$th GA process that iteratively evolves a population $\rho$ of solutions, using genetic operators, toward the $i$th best set cover solution in terms of minimum number of sensors that reliably cover all targets. Thus, the objective function $\Phi$ of the $i$th GA can be defined as:

$$\begin{aligned} \Phi ^{i}:Minimize \left| {\mathcal{S}_{active}^i} \right| \end{aligned}$$

(5)

where $\mathcal{S}_{sleep}^i$ denotes the set of alive sensors that has no sensing functionality in the $i$th interval of the network’s lifetime.

Since no more than $ub$ set covers can be generated, then we have no more than $ub$ GA-layers (see Eq. 6). The $i$th layer (also called the $i$th GA) only explores the solution space of the unassigned (i.e., sleep) sensors set resulted from the $i-1$th GA. For the $1^{st}$ GA, the number of unassigned sensors is the whole set of sensors $\mathcal{S}$.

$$\begin{aligned} \mathbb {GA}=GA^{1 \circ }GA^{2 \circ }\ldots ^{\circ }GA^{l}| l\le ub \end{aligned}$$

(6)

where:

$$\begin{aligned} l=\left\{ {{\begin{array}{l@{\quad }l} ub &{} if \left| {\mathcal{S}_{sleep}^{ub-1} } \right| >0 \wedge Cover\left( {\mathcal{S}_{sleep}^{ub-1} ,\mathcal{T}} \right) =1 \\ <ub &{} otherwise \\ \end{array} }} \right. \end{aligned}$$

(7)

3.1 Space and Solution Configurations

The choice of a good solution representation is a critical issue for the applicability and performance of evolutionary algorithm. Solution representation is highly problem dependent and related to the evolution operations. In our algorithm design, each individual solution $\mathbb {P}^{i}$ of $GA^{i}$ is represented as a fixed-length vector of size $m^{i}=\left| {\mathcal{S}_{sleep}^{i-1}} \right|$, where each $gene_j$ controls the active/sleep scheduling of the corresponding $j$th sensor in $\mathcal{S}_{sleep}^{i-1}$. Formally speaking, for population $i$ of $K$ individuals, each of $m^{i}$ genes,

$$\begin{aligned} \forall k&\in \left\{ {1,\ldots ,K} \right\} \,\,and\,\, \forall j\in \{1,\ldots ,m^{i}\}: \nonumber \\ \mathbb {P}_k^i&= \left( {\mathbb {P}_{k,1}^i ,\mathbb {P}_{k,2}^i ,\ldots ,\mathbb {P}_{k,m^{i}}^i } \right) s.t. : \nonumber \\ \mathbb {P}_{k,j}^i&= \left\{ {{\begin{array}{l@{\quad }l} 1, &{} if \, s_j \, is \, active \\ 0, &{} if \, s_j \, is \, sleep \\ \end{array} }} \right\} \end{aligned}$$

(8)

Then, the whole configuration space $\delta ^{i}$ for the $i$th GA can be created by the Cartesian product of activation/inactivation of all $m^{i}$ unassigned sensors being resulted from in the $i-1$th GA:

$$\begin{aligned} \delta ^{i}={\mathop \prod \limits _{i=1}^{m^{i}}} \left( {\left\{ {0,1} \right\} } \right) =2^{m^{i}} \end{aligned}$$

(9)

where 0 means inactive (i.e., unassigned) sensor, while $1$ means active (i.e., assigned) sensor. Let us to consider that $GA^{i,1\le i\le ub}$ handles only $K\ll \delta ^{i}$ different individual solutions at a time. It starts with an initial random population $\rho _0 \subset \delta ^{i},\left| {\rho _0} \right| =K$ and continues until a maximum number of generations $max_{gen}$ has been reached. Each generation $\Psi ^{i}:\rho \rightarrow \rho {\prime }$ consists of four main operators: individual repair, parent selection, crossover, and mutation. Thus, $\Psi$ can be decomposed into:

$$\begin{aligned} \Psi ^{i}=\Psi _{rep}^i \circ \Psi _{sel}^i \circ \Psi _x^i \circ \Psi _{mu}^i \end{aligned}$$

(10)

3.2 Repair Operator and the Fitness Function

Before evaluating each individual, infeasible set cover solutions should be transformed into feasible ones by means of a problem-specific repair operator. Infeasible solutions are those which suffer from either the existence of coverage-holes or let the targets to be over-covered by more than need sensors. The main idea of the repair operator is to make hole-free targets coverage with as less number of sensors as possible. The process of the proposed repair operator $\Psi _{rep}^i$ of the $i$th GA is presented next (see Algorithm 1).

$$\begin{aligned} \Psi _{rep}^i :\mathbb {P}_k^{i} \rightarrow \mathbb {P}_k^i {\prime } \end{aligned}$$

(11)

It takes as input the individual $\mathbb {P}_k^i , 1\le k\le K$ and the set of unassigned sensors $\mathcal{S}_{sleep}^{i-1}$ resulted from the previous GA layer. First, it check whether the active sensors set $\mathcal{S}_k$ selected by $\mathbb {P}_k^i$ (i.e.,$\mathcal{S}_k =\{s_j | \quad \mathbb {P}_{kj}^i =1\})$ forms coverage-hole or dense-coverage under the user-specified reliability threshold. In case of coverage-hole, $\Psi _{rep}^i$ will randomly draw from $\mathcal{S}_{sleep}^{i-1}$ set one sensor at a time and collect it with $\mathcal{S}_k$ (i.e., $\mathcal{S}_k =\mathcal{S}_k \cup s|s\in \mathcal{S}_{sleep}^{i-1}$ and $\mathcal{S}_{sleep}^{i-1} =\mathcal{S}_{sleep}^{i-1} -s$) until the new set form hole-free set cover. On the other hand, if $\mathcal{S}_k$ forms dense-coverage, $\Psi _{rep}^i$ will randomly deactivate one sensor at a time (i.e., $\mathcal{S}_k =\mathcal{S}_k -s|s\in \mathcal{S}_k$ and $\mathcal{S}_{sleep}^{i-1} =\mathcal{S}_{sleep}^{i-1} +s$) until it can form complete coverage with less number of sensors.

Then, to evaluate each individual solution $\mathbb {P}_k^i$, the fitness function $\Phi$ simply sums the number of active sensors being selected by the corresponding solution.

$$\begin{aligned} \forall k&\in [1,K] \nonumber \\ \Phi \left( {\mathbb {P}_k^i } \right)&= \mathop {\sum }\limits _{j=1}^{m^{i}= \left| \mathcal{S}_{sleep}^{i-1}\right| } \mathbb {P}_{kj}^i \end{aligned}$$

(12)

3.3 Selection, Crossover, and Mutation Operators

The remaining genetic operators follow the de-facto standard operators found in the simple genetic algorithms.. The binary tournament selection operator is used to choose one of two random individuals $\mathbb {P}_1$ and $\mathbb {P}_2$. A proportion $p_c =0.6$ of pairs of parents are then selected for crossover. Two cut points $r1, r2\sim \{1,\ldots ,m^{i}-1\}$, are randomly selected, and the participating parent individuals, $\mathbb {P}_1 \hbox { and } \mathbb {P}_2$ are then swapped at $gene_j \big |{r1\le j\le r2}$. Each $gene_{j} \big | {1\le j\le m^{i}}$. in the new individuals is then mutated with small probability $p_m =0.1$.

$$\begin{aligned}&\forall k\in \left\{ {1,\ldots ,K} \right\} \nonumber \\&\Psi _{sel} :\{\mathbb {P}_{k1} ,\mathbb {P}_{k2} \}\rightarrow \mathbb {P}_k \end{aligned}$$

(13)

$$\begin{aligned}&\forall k\in \left\{ {1,\ldots ,K/2} \right\} \nonumber \\&\Psi _x :\{\mathbb {P}_{k1} ,\mathbb {P}_{k2} \}\rightarrow \{\mathbb {P}_{k1}^{\prime },\mathbb {P}_{k2}^{\prime }\} \nonumber \\&\mathbb {P}_{k1}^{\prime }=\left( {\mathbb {P}_{k1,1} ,\ldots ,\mathbb {P}_{k1,r1} ,\mathbb {P}_{k2,r1+1} ,\ldots ,\mathbb {P}_{k2,r2} ,\mathbb {P}_{k1,r2+1} ,\ldots ,\mathbb {P}_{k1,m^{i}} } \right) \nonumber \\&\mathbb {P}_{k2}^{\prime }=\left( {\mathbb {P}_{k2,1} ,\ldots ,\mathbb {P}_{k2,r1} ,\mathbb {P}_{k1,r1+1} ,\ldots ,\mathbb {P}_{k1,r2} ,\mathbb {P}_{k2,r2+1} ,\ldots ,\mathbb {P}_{k2,m^{i}}} \right) \end{aligned}$$

(14)

$$\begin{aligned}&\forall k\in \left\{ {1,\ldots ,K} \right\} \wedge \forall j\in \{1,\ldots ,m^{i}\} \nonumber \\&\Psi _{mu} :\mathbb {P}_k \rightarrow \mathbb {P}_{k}^{\prime } \nonumber \\&\mathbb {P}_{k,j} =\left\{ {{\begin{array}{l@{\quad }l} \quad \mathbb {P}_{k,j} &{} if \,\, r>p_m \\ 1-\mathbb {P}_{k,j} &{} if \,\, r\le p_m \\ \end{array}}} \right. \end{aligned}$$

(15)

The mechanisms of the genetic operators being defined by repair, fitness evaluation, selection, crossover and mutation transform a complete population of solutions into another complete population and after a specified number of generations $max_{gen}$, the best individual solution (in terms of minimum $\Phi )$ will be produced. The definition of the best individual of the $i$th GA can be formulated as:

$$\begin{aligned} Best\mathbb {P}^{i}: \Longleftrightarrow \not \exists \,\mathbb {P}^{i}\in \rho _{max_{gen}} | \Phi \left( {\mathbb {P}^{i}} \right) < \Phi (Best\mathbb {P}^{i}) \end{aligned}$$

(16)

3.4 Post-heuristic Operator

The best solution set $\mathbb {BestP}=\{Best\mathbb {P}^{i} |i=1,\ldots ,l\}$ provided by $\mathbb {GA}$ can further be improved in terms of coverage reliability by forwarding it to a post-heuristic operator dedicated for this purpose. Algorithm 2 presents the steps of this heuristic. It operates iteratively layer followed by layer (line 1), improving the reliability of each layer $i$ by exploiting the existing unassigned sensors (being gathered in $\mathcal{S}_{sleep}^l )$ and/or replacing the existing active sensors (being gathered in $Best\mathbb {P}^{i})$.

4 Performance Evaluations

In this section we will measure the performance of the proposed multi-layer GA (denoted hereinafter as mlGA) for solving DRSC problem. The evaluation is presented in terms of number of set covers obtained, set covers’ coverage reliability, and sensors cost. The results are obtained after setting WSNs and algorithm parameters into the following. The simulation area is square-shaped with side length $X_{max} =1{,}000$ m of 10 randomly distributed targets. The simulation is mainly divided into nine groups according to nine different settings of sensor density: $25,50,75,\ldots ,225$. For each group, we will vary the sensing range of the sensor nodes $R_s$ to five different values $\{400, 500,600, 700,800\}$, to get a different test instance (i.e., we have 45 different test instances). Each test instance $TI^{i}, i=1,\ldots ,45$ includes 10 random WSNs with different configurations. Thus the overall simulation examines a total of 450 random network configurations. As we have random WSN configurations, we may get different value for the upper bound of set covers $ub$, for the same parameter settings. Thus in each test instance, the presented results also indicate the average number of upper bound of set covers (denoted by $\overline{{ub}}$). In other words, $\overline{{ub}}$ is used to represents the maximum network’s lifetime. Uncertainty level $R_u$ is set to $R_s *0.5$ units, both $\lambda$ and $\beta$ are set to 0.5, and $c_{th}$ is set to 0.001. The setting of the probabilistic coverage parameters also influences the overall network’s coverage reliability. As studying the impact of varying these parameters is out of the scope of this paper, we fixed these parameters to one setting and evaluate the average coverage reliability $\overline{{r}}$ (i.e., the average signal strength being detected from all the targets) of all network configurations in each test instance. Population size is set to 50 and will be allowed to evolve 500 times.

The performance of the proposed mlGA has been compared with the performance of Genetic Algorithm for Maximum Disjoint Set Covers (GAMDSC). GAMDSC has been proposed in [15] to extend the lifetime of WSNs. GAMDSC also is simple genetic algorithm but uses integer representation for chromosome representation (like all GA related work in the literature, e.g., [16] and [17]), traditional uniform crossover, traditional creep mutation, and a proposed scatter operator to evolve their chromosome solutions. The fitness function of GAMDSC has been devoted to maximize number of complete set covers in each chromosome. The performance of GAMDSC has been compared in [15] against the most constrained-minimum constraining heuristic (MCMCC) [2] and the exhaustive heuristic of Maximum Covers using Mixed Integer Programming (MCMIP) [12] for solving the DSC problem in WSNs. Simulation results in [15] show that GAMDSC can get near-optimal solutions and improve the performance of MCMCC by 16 % in terms of the obtained sensor covers. As compared with the exhaustive search of MCMIP, GAMDSC can get results with acceptable computation time.

4.1 Solution Quality of Multi-layer GA Versus GAMDSC

First, results are presented in Tables 1, 2 and 3 to compare the quality of results obtained by GAMDSC, and our algorithm. Tables 1, 2 and 3 quantitatively present the number of set covers (denoted by $ub$) being obtained by both algorithms. To examine the quality of solutions, we present $\overline{{ub}}$ as reference value. Unlike work in [15], which evaluates the performance of GAMDSC for small values of $\overline{{ub}}$ ranged from 5 to 39, the results here evaluate both GAMDSC and mlGA for larger setting of $\overline{{ub}}$ ranges from 3.7 to 92.1. In the tables, the solution providing the closest value to $\overline{{ub}}$ in each test instance has been bolded. Figures 2, 3 and 4 qualitatively depict the performance of GAMDSC and mlGA. Moreover, Figs. 5, 6 and 7 depict the accuracy percentage of obtained number of set covers of each algorithm. For further qualitative comparison, Fig. 8 depicts the obtained $ub$ for three different settings of sensor density, i.e., $m=25,125$ and 225 and the five settings of sensing range. Additionally, Fig. 9 depicts $ub$ for the two extremes of sensing range $R_s =\{400,800\}$, and the nine different settings of sensor density.

Fig. 2

Maximum number of the generated Set Covers for GAMDSC: left versus mlGA: right where $number \, of \, sensors\, m=\{25,50,75\} \quad \hbox {and} \quad R_s =\{400,500,\ldots ,800\}$

Fig. 3

Maximum number of the generated Set Covers for GAMDSC: left versus mlGA: right where $number \, of \, sensors \,m=\{100,125,150\} \quad \hbox {and} \quad R_s =\{400,500,\ldots ,800\}$

Fig. 4

Maximum number of the generated Set Covers for GAMDSC: left versus mlGA: right where $number \,of \,sensors \,m=\{175,200,225\} \quad \hbox {and} \quad R_s =\{400,500,\ldots ,800\}$

Fig. 5

Accuracy percentage of the generated Set Covers for GAMDSC: left versus mlGA: right where $number \,of \,sensors \,m=\{25,50,75\} \quad \hbox {and} \quad R_s =\{400,500,\ldots ,800\}$

Fig. 6

Accuracy percentage of the generated Set Covers for GAMDSC: left versus mlGA: right where $number \,of \,sensors \,m=\{100,125,150\} \quad \hbox {and} \quad R_s =\{400,500,\ldots ,800\}$

Fig. 7

Accuracy percentage of the generated Set Covers for GAMDSC: left versus mlGA: right where $number \,of \,sensors \,m=\{175,200,225\} \quad \hbox {and} \quad R_s =\{400,500,\ldots ,800\}$

Fig. 8

Average number of set covers of $GAMDSC$ (+ sign) and $mlGA$ (filled circle). The simulation is experimented under 150 networks with $number \,of \,sensors=\{25,125,225\}$ and $R_s =\{400,500,600,700,800\}$

Fig. 9

Average number of set covers of $GAMDSC$ (+ sign) and $mlGA$ (filled circle). The simulation is experimented under 180 networks with $number \,of \,sensors=\{25,50,\ldots ,225\}$ and $R_s =\{400,800\}$

Table 1 Comparison of the maximum number of the generated Set Covers for 10 WSNs in each test instance with number of sensors $\,=\{25,50,75\} \quad \hbox {and} \quad R_s =\{400,500,\ldots ,800\}$

Table 2 Comparison of the maximum number of the generated Set Covers for 10 WSNs in each test instance with number of sensors $=\{100,125,150\} \hbox { and } R_s =\{400,500,\ldots ,800\}$

Table 3 Comparison of the maximum number of the generated set covers for 10 WSNs in each test instance with number of sensors $=\{175,200,225\} \quad \hbox {and} \quad R_s =\{400,500,\ldots ,800\}$

Results in Tables 1, 2, 3 and Figs. 2, 3, 4, 5, 6, 7 reveal that the proposed ml GA significantly outperforms GAMDSC in terms of finding near optimal number of set covers. For $\overline{{ub}}>8.8$ (i.e., in $TI^{7}$ to $TI^{45})$, the performance of GAMDSC deteriorates, while mlGA continues in getting solutions very slightly less than the optimal values. In almost all of the network configurations of these test instances, mlGA reaches the optimal solution. In other words, we can say that increasing $\overline{{ub}}$ restricts the ability of GAMDSC and constraints the usefulness of its components (mainly characterized by the integer-based chromosome representation and the scatter operator) to find optimal or near optimal $ub$ solutions. On the other hand, the characteristic components of the proposed mlGA (being specified mainly by the chromosome binary representation and the proposed repair operator) is found to be more robust to find very near optimal or even optimal $ub$ solutions.

For small values of set covers (i.e. $\overline{ub} \le 8.8$), both GAMDSC and mlGA attained nearly an equal number of set covers. In test instances $TI^{1}$ to $TI^{3}$ both GAMDSC and mlGA get optimal number of set covers, while in $TI^{4}$ to $TI^{6}$ GAMDSC finds slightly more covers than mlGA. However, in all these test instances (i.e., $TI^{1}$ to $TI^{6})$, we cannot say that both algorithm have an equal performance. As will be seen in Table 4 of the next section, the active sensors cost percentage $SC\%$ used by GAMDSC is more than that of mlGA. While mlGA (in $TI^{1}$ to $TI^{6}$) costs only 47.6–68.8 % of the total number of sensors, GAMDSC costs more than 99.0 % of the total number of sensors.

Table 4 Comparison of sensors cost percentage for 10 WSNs in each test instance with $number \,of \,sensors=\{25,50,75\} \quad \hbox {and} \quad R_s =\{400,500,\ldots ,800\}$

As expected from the qualitative results depicted in Figs. 8 and 9, increasing sensor density and/or sensing range provides algorithms with more alternatives for constructing complete and reliable set covers. Moreover, as evident from the figures that increasing sensor density and/or sensing range further discriminates between the performance of both algorithms in terms of finding maximum number of set covers. The full results of both GAMDSC and mlGA are projected in 3D space in Figs. 10 and 11, respectively.

Fig. 10

3D projection of the results of $GAMDSC$ ($x$-coordinate: sensing range, $y$-coordinate: number of sensors, $z$-coordinate: average number of set covers). The simulation is experimented under 450 networks with $number \,of \, sensors=\{25,50,\ldots ,225\}$ and $R_s=\{400,500,\ldots ,800\}$

Fig. 11

3D projection of the results of $ml$GA ($x$-coordinate: sensing range, $y$-coordinate: number of sensors, $z$-coordinate: average number of set covers). The simulation is experimented under 450 networks with $number \,of \, sensors=\{25,50,\ldots ,225\}$ and $R_s =\{400,500,\ldots ,800\}$

4.2 Comparison of Sensors Cost of Multi-layer GA Versus GAMDSC

In this section, we want to compare the performance of the proposed mlGA and GAMDSC in terms of active sensors cost used in the generated DSCs (see Tables 4, 5, 6). The goal is to achieve the highest number of set covers possible with the fewest number of active sensors. Here, sensors cost percentage $SC\%$ is defined as the ratio between the number of active sensors used in the generated best individual solution $\mathbb {BestP}$ and the total number of sensor nodes $m$, i.e.,:

$$\begin{aligned} SC=\frac{\left| {\bigcup _{s\in {\mathbb {BestP}}} s=1} \right| }{m}*100\,\% \end{aligned}$$

(17)

Also, here in the tables, the solution providing the smallest $SC\%$ in each test instance has been bolded. Figures 12, 13 and 14 qualitatively depict the sensors cost percentage $SC\%$ for GAMDSC and $mlGA$.

Fig. 12

Sensors Cost percentage for the generated Set Covers for GAMDSC: left versus mlGA: right where $number \,of \,sensors \, m=\{25,50,75\} \hbox { and } R_s =\{400,500,\ldots ,800\}$

Fig. 13

Sensors Cost percentage for the generated Set Covers for GAMDSC: left versus mlGA: right where $number \,of \,sensors \, m=\{100,125,150\}\hbox { and } R_s =\{400,500,\ldots ,800\}$

Fig. 14

Sensors Cost percentage for the generated Set Covers for GAMDSC: left versus mlGA: right where $number \,of \,sensors \, m=\{175,200,225\} \hbox { and} R_s =\{400,500,\ldots ,800\}$

Table 5 Comparison of sensors cost percentage for 10 WSNs in each test instance with $number \,of \,sensors=\{100,125,150\} \quad \hbox {and} \quad R_s =\{400,500,\ldots ,800\}$

Table 6 Comparison of sensors cost percentage for 10 WSNs in each test instance with $number \,of \,sensors=\{175,200,225\} \quad \hbox {and} \quad R_s =\{400,500,\ldots ,800\}$

The results presented in Tables 4, 5, 6 and Figs. 12, 13, 14 clearly signify the superiority of mlGA over GAMDSC for activating less number of sensors for a large number of set covers (i.e., for a longer lived networks). In almost all of the 45 test instances (i.e., in 450 different network configurations), GAMDSC consumes more than 80 % of the total number of sensors to achieve networks’ lifetime less than that achieved by mlGA. For the purpose of a detailed comparison between the performance of the proposed mlGA versus GAMDSC under various sensor density and range settings, we will also here refer to the results depicted in Figs. 5, 6, 7 and $\overline{{ub}}$ values presented in Tables 1, 2 and 3. For small lived network instances of $T^{1}-T^{15}$ in Table 4 (where average lifetime, i.e., upper bound of set covers $\overline{{ub}}$ ranges from 3.7 to 30.8 as presented in Table 1), GAMDSC consumes more than 90 % of the total sensors to achieve network’s lifetime accuracy above 85 % (as shown in Fig. 5). On the other hand, mlGA sacrifices no more than 77 % sensors to achieve lifetime very near to the expected $\overline{{ub}}$ value (with accuracy more than 94.5 % as shown in Fig. 5). For small to moderate lived networks of instances $T^{16}-T^{30}$ in Table 5, the expected $\overline{{ub}}$ value, in Table 2, ranges from 21.0 to 53.4. In these instances, more than 85 % of the total sensor density is activated by GAMDSC to extend the network’s lifetime to no more than 82 % of its upper bound (as shown in Fig. 6). However, for the same instance cases, mlGA continues to perform very properly, activating no more than 74 % of the total sensor density to achieve lifetime bound accuracy no less than 93 %. Finally, for the moderate to long lived networks of instances $T^{31}-T^{45}$ in Table 6, we can see that the upper bound of network lifetime $\overline{{ub}}$ (as shown in Table 3) should range from 35.2 to 92.1. In these instances, GAMDSC costs more than 75.7 % sensors to get no more than 80.7 % of $\overline{{ub}}$ accuracy. On the other hand, mlGA is once again sufficient. It costs up to 77 % sensors to get quite accurate number of set covers with 96.6 % accuracy.

On overall, the results reflect that many sensors are redundantly scheduled by GAMDSC to form complete set covers. On the other hand, mlGA has the ability to correctly schedule as less number of sensors as necessary to form as more as possible number of complete set covers.

4.3 Impact of Post-heuristic Operator

The performance of the proposed mlGA is presented, here, before and after performing the post-heuristic operator with names $mlGA^{-}$ and $mlGA^{+}$, respectively. Tables 7, 8 and 9 present the average covers reliability $r$ of the whole set covers solution of GAMDSC, $mlGA^{-}$ and $mlGA^{+}$. Here, $\overline{{r}}$ is presented as reference value. The solution providing the closest value to $\overline{{r}}$ in each test instance has been bolded. Moreover, Figs. 15, 16 and 17 depict the sensors cost percentage $SC\%$ being resulted from GAMDSC and $mlGA^{+}$.

$$\begin{aligned} r=\frac{\mathop \sum \nolimits _{i=1}^l rDSC_i }{l} \end{aligned}$$

(18)

where $l$ is the maximum number of set covers and the coverage reliability of the $i$th set cover, $rDSC_i$, can be formulated as:

$$\begin{aligned} rDSC_i =\frac{\mathop \sum \nolimits _{j=1}^n { }_{k=1,2,\ldots ,m} \mathop {\arg \;max}\limits _{s_k \in DSC_i} (Coverage(s_k ,t_j ))}{n} \end{aligned}$$

(19)

Table 7 Comparison of covers reliability for 10 WSNs in each test instance with $number \,of \,sensors=\{25,50,75\} \quad \hbox {and} \quad R_s =\{400,500,\ldots ,800\}$

Table 8 Comparison of covers reliability for 10 WSNs in each test instance with $number \,of \,sensors=\{100,125,150\} \quad \hbox {and} \quad R_s =\{400,500,\ldots ,800\}$

Table 9 Comparison of covers reliability for 10 WSNs in each test instance with $number \,of \,sensors=\{175,200,225\} \quad \hbox {and} \quad R_s =\{400,500,\ldots ,800\}$

Fig. 15

Sensors Cost percentage for the generated Set Covers for GAMDSC: left versus $mlGA^{+}$: right where $number \,of \,sensors \,m=\{25,50,75\} \quad \hbox {and} \quad R_s =\{400,500,\ldots ,800\}$

Fig. 16

Sensors Cost percentage for the generated Set Covers for GAMDSC: left versus $mlGA^{+}$: right where $number \,of \,sensors \, m=\{100,125,150\} \quad \hbox {and} \quad R_s =\{400,500,\ldots ,800\}$

Fig. 17

Sensors Cost percentage for the generated Set Covers for GAMDSC: left versus $mlGA^{+}$: right where $number \,of \,sensors \, m=\{175,200,225\} \quad \hbox {and} \quad R_s =\{400,500,\ldots ,800\}$

By comparing the results of $mlGA^{-}$ against $mlGA^{+}$ in Tables 7, 8 and 9, we can see that $mlGA^{+}$ can exploit the existence of the redundant sensors to improve its covers reliability. Also, the results verify that $mlGA^{+}$ can achieve covers reliability more or less than that achieved by GAMDSC. Again, this is expected as GAMDSC forms only a small number of complete set covers with many redundant sensors (as shown in Sects. 4.1, 4.2). This also demonstrates that there should be a tradeoff between the two contradictory criteria of getting maximum number of complete set covers and high covers reliability.

4.4 Comparison of Worst Case Time Complexity

Here we will compare the worst-case computational complexity of GAMDSC algorithm and the proposed multi-layer GA solving Disjoint Reliable Sensor Covers Problem (DRSC). Without loss of generality, the computational complexity of any single-objective genetic algorithms is $O(max_i \times K)$ where $K$ is the size of solutions to be evolved, via certain evolution operators, for $max_i$ iterations.

Now, let us consider the computation time needed for the most critical parts of the above algorithms when applied for solving DRSC problem. It is stated in [15] that in each generation of GAMDSC, the fitness function is the most critical part which represents the computation time bottleneck. The evaluation of the fitness function is linearly related to the number of sensors and the number of targets. Thus, the worst-case time complexity of GAMDSC is:

$$\begin{aligned} O\left( {GAMDSC} \right) =max_i \times K\times \left| n \right| \times \left| m \right| \end{aligned}$$

(20)

where $\left| n \right|$ is the number of targets and $\left| m \right|$ is the number of sensors. On the other hand, for the multi-layer GA, the proposed repair operator (Algorithm 1) costs the most computation time and in the worst-case time it linearly related to the maximum number of sensors and targets. Also, the multi-layer GA has to repeat its whole operations for at most $ub$ layers, and in the worst-case time it linearly related to the upper bound of sensor covers $ub$. Thus, the worst-case time complexity of the proposed multi-layer GA can be formally described in Eq. 21. Shortly speaking, $O\left( {mlGA} \right) =O\left( {GAMDSC} \right) \times \left| {ub} \right|$.

$$\begin{aligned} O\left( {mlGA} \right) =max_i \times K\times \left| n \right| \times \left| m \right| \times \left| {ub} \right| \end{aligned}$$

(21)

5 Conclusions

In this paper, we have addressed WSNs lifetime extension problem as a maximum Disjoint Set Covers (DSC) problem while introducing the concept of probabilistic coverage as a more realistic coverage model for constructing the set covers. A multi-layer genetic algorithm is proposed to maximize the number of set covers, where the total number of sensors used in each set cover is to be minimized. The result of multi-layer GA is then forwarded to a post-heuristic operator to improve the coverage reliability of each cover set. The performance of the proposed genetic algorithm is investigated in this paper under different simulation setting. The results of the simulations reveal that the proposed genetic algorithm outperforms GAMDSC in terms of number of disjoint set covers, covers reliability and sensors cost. The results of this paper currently motivate us to investigate the possibility of applying multi-objective evolutionary algorithms (like MOEA/D, NSGA-II, and MOPSO [22–25]) to the combined optimization problem of both disjoint set covers and covers reliability and handling both objective functions simultaneously instead of applying consecutive optimization mechanisms. Also, as a scope of further work, another quality of service (QoS) merit could be used to constraint the defined DRSC problem. For example, different targets may need different priority of sensing quality and thus the optimization problem should reflect this diversified QoS coverage constraint in its formulation.