A Hierarchical Scheduling Scheme in WSNs Based on Node-Failure Pretreatment

Abstract

One of the most important challenges in designing wireless sensor networks is how to recover a broken network within a very short time as the active nodes are failed or out-of-energy. Focusing on this problem, a hierarchical scheduling scheme based on node-failure pretreatment is proposed, in which the global optimization method is used to find the minimum connected tree and the local multilayer recovery algorithm is used to find a candidate sensor node instead of the failed one. Three highlights of this scheme are as follows: (1) The importance of sensor nodes is defined in terms of their locations in minimum connected tree and coverage acreage. (2) The neighborhood radius of failed sensor node varies with its importance, and then its candidate-node set is dynamically constructed. (3) A novel multilayer recovery strategy including node recovery and regional recovery is presented. Simulation results show that hierarchical scheduling scheme finds the optimal candidate sensor node in less time to make the repaired network with lowest energy consumption. Though the less sensor nodes are activated, the network lifetime is slightly shorter. Moreover, this scheme can be applied in the problem that the communication radius of sensor node is less than two times of its sensing radius.

1. Introduction

Wireless sensor networks (WSNs) are ad hoc networks composed by a large number of tiny and autonomous wireless sensor nodes [1]. These battery-powered nodes endowing with sensing, processing, and wireless communication capabilities are deployed in the detected area to collect monitoring data from the environment and transform them to sink nodes [2]. Now WSNs have been widely applied to environmental monitoring, space exploration, military, and other fields.

Each wireless sensor node has compact size and finite power supply. In particular, sensor nodes placed in dangerous environments are difficult to recharge or replace batteries. So they are cheap and their lifetimes are limited. In order to effectively monitor the detected area as long as possible and against probably exhausted sensor nodes, the robust and fully connected network is composed of the least nodes. We call this network structure as the minimum connected tree (MCT). How to rationally schedule the randomly distributed wireless sensor nodes so as to minimize energy consumption and prolong the operational lifetime of whole network is the key issue in WSNs.

A promising approach for solving this problem is sleep scheduling strategy. That is, a part of sensor nodes keeps running or being active while others called redundant nodes put into low-power sleeping mode. All active nodes form the minimum connected tree, which satisfies the requirement of energy-efficiency coverage and has least communication consumption. Once one of the active nodes runs out of the power, the communication linkages corresponding to this node are broken. In order to recover network as soon as possible, a neighbor sleeping node, which can reform the new minimum connected tree with other active nodes, will wake up instead of the out-of-energy node [3]. This scheduling strategy can effectively decrease the redundant monitoring data and prolong the network lifespan.

Many researches had been done on the sleep scheduling strategy. Some schemes met the needs of coverage, which made the full use of sensor nodes in large-scale network environment by maximizing the amount of alternate-node sets [4–6]. An adaptive sleep scheduling for probing environment was proposed in [7]. The states of sensor nodes were decided in terms of the probing and monitoring mechanism. In these algorithms, with the increasing number of wireless sensor nodes, fewer nodes are activated to reduce energy consumption and ensure a linear increase of network lifetime. A distributed scheduling algorithm was presented to prolong the network lifetime according to the overlapping relationship of coverage acreage between the neighbor nodes [8]. Another distributed algorithm took maximum network lifetime and the coverage rate as the optimization objectives [9]. In the above methods, the obtained wireless sensor networks had the optimal coverage rate. But the active nodes may not be fully connected.

In order to monitor target area effectively and ensure the full connection among the active nodes, Zhang and Hou [10] proved that if the communication radius of sensor node is larger than twice that of its sensing radius, the network satisfying complete coverage consists of fully connected sensor nodes. However, once the above constraint condition cannot be satisfied, how to construct fully connected network with optimal coverage rate is the key issue. Nakamura et al. [11] transformed the full-connection coverage problem into an ILP model and solved it by the commercial optimization package CPLEX [12]. By comparing WSNs’ performances gotten from an ILP model and evolutionary algorithms, Quintão et al. [13] indicated that population-based method could achieve reasonable solutions for WSNs with a considerably lower computational cost. Nevertheless, it only considered the coverage rate of the network as a relevant criterion. The papers [14–16] presented hybrid algorithms based on the density control. They took the relationship among coverage, connectivity, and energy consumption of WSNs into account and focused on finding a sensor node set, which not only met the coverage requirements, but also maximized the network lifetime. A distributed protocol [17], which provided a transition mechanism of sensor nodes’ states, was presented. A sensor node has four states: sleeping, passive, test, and active. Each passive node obtains information and switches to sleeping in test state. Thus, according to the situation of WSNs, sensor nodes can change their states dynamically and reduce the possibility of overlapping coverage with other sensor nodes. However, the rational requirement of the network coverage was not guaranteed.

It is worth noting that the real-time performances of WSNs are highlighted in practice. When an active node is failed, to reconstruct the minimum connected tree by global optimization methods or repair the network by locally calculating all the paths between the failed node and its neighbor nodes are both time-consuming and have the direct influence on the real-time performances of WSNs.

To solve the above problem, Martins et al. [15] presented a dynamic hybrid approach combining the global optimization method with a local online algorithm so as to correct the failures caused by the out-of-energy nodes. The global optimization method was employed for solving the coverage problem by genetic algorithm (GA). The local online algorithm (LOA) was intended to restore the network in terms of the failures of active nodes. However, a new node was chosen from the neighborhood of a failed node to replace the invalid one based on the least sum of the distances from the parent nodes to the sink node and the distances between the son nodes and sink node in this algorithm. Each son node or parent node was derived from the rooted sink node. It is easy to see that the computational cost of this algorithm is greatly affected by the size of the neighborhood radius. When the scale of wireless sensor network is small, the neighborhood of failed node is usually small. It is possible to evaluate all neighbor sensor nodes and choose the optimal one having the least energy consumption and less computation. On the contrary, when the scale of the wireless sensor network is large, there are a lot of sleeping nodes to be evaluated. It will be too expensive and time-consuming to calculate the distances from these sleeping nodes to the parent or son nodes of the failed nodes.

In this paper, a hierarchical scheduling method based on node-failure pretreatment strategy (FPS) is proposed. Its goal is to construct an active-sensor-node set to make the repaired network having the lowest energy consumption and maintaining the better performances, such as the connectivity and the coverage rate, as well. The FPS-based hierarchical scheduling method combines the global optimization method with the local multilayer recovery strategy. The global optimization method rebuilds the network so as to find the minimum connected tree satisfying the requirements of network performances. In FPS-based local multilayer recovery strategy, the neighborhood radius of each sensor node varies with its importance, which is determined by its location in minimum connected tree and coverage acreage. Subsequently, the candidate-node set of this node is gotten by certain rules before the failure of this node. Considering the energy consumption and connectivity of the network, an optimal candidate node is chosen from its candidate-node set by certain rules when an active sensor node is failed. And then this candidate node replaces the failed one by node recovery strategy. Once no rational candidate node can be found, regional recovery strategy is done to repair the invalid region affected by the failed node. The above node recovery strategy and regional recovery strategy are composed of local multilayered recovery strategy.

The remainder of this paper is organized as follows. In Section 2, a mathematical model describing minimum energy consumption based on network connectivity and coverage is formulated. The detailed hierarchical scheduling scheme is illustrated in Section 3. Then in Section 4, the comparative experiments are done and the experimental results are further analyzed. Finally, the conclusions and future work are drawn in Section 5.

2. Problem Analysis

2.1. Problem Description and Assumptions

To obtain a WSN having the longest network lifetime and the best qualities of service, such as connectivity and coverage, by rationally switching the “sleeping” and “active” modes of wireless sensor nodes in the target area is the goal of the scheduling optimization methods. It actually means that only a part of sensor nodes keeps being active, which construct the network with the acceptable performances, and others are put into the low-powered sleeping mode. Once a sensor node cannot be connected to any sink node, which is called the failed node, or the coverage rate is less than a preset threshold, we call it the network failure. In the case of the network failure caused by some invalid sensor nodes, how to make full use of the sleeping nodes nearby the invalid nodes to recover the WSN so as to effectively prolong the network lifespan is a dynamic scheduling problem.

Suppose there are N sensor nodes randomly distributed in the target region. The set of all sensor nodes is expressed as $S=\{s_{\mathrm{1}},s_{\mathrm{2}},\dots ,s_N\}$ .

Some assumptions are considered to construct the mathematical model of scheduling in WSNs.

• (i)

Each sensor node has a unique ID and its position is known.

(ii)

All sensor nodes are homogeneous and have the equal energy.

(iii)

All sensor nodes cannot move after being deployed.

(iv)

The detecting area of each sensor node is assumed to be a circle with the sensing radius $r_s$ . And the communication area of each sensor node is also a circle with the communication radius $r_c$ . Typically, $r_s$ is less than $r_c$ .

(v)

Each sensor node has three states: active, sleeping, and dead. The working nodes keep being active, while the failed nodes are in the dead state. And inactive nodes are in sleeping state, which can be activated as the candidate nodes in some cases and transform to the active state.

(vi)

The energy consumption of a sleeping node is 0. The switching time among different modes of a sensor node is negligible.

2.2. The Measurements of WSNs’ Performances

Four commonly used metrics including the network's lifetime, connectivity, coverage rate, and the communication energy consumption are defined as follows.

2.2.1. The Networks’ Lifetime

The network's operational lifetime is defined as the duration from the beginning of the network operation to the network failure:

$$\begin{array}{cc}& T\left(S\right)=T_{\text{failure}}-T_{\text{beginning}}.\end{array}$$

(1)

2.2.2. The Networks’ Connectivity

The wireless sensor network, in which there is a feasible path between any two sensor nodes in the target area, is called fully connected WSN.

2.2.3. The Coverage Rate

The coverage rate of WSNs is one of the important qualities of service. Based on the binary sensing model of sensor node, the coverage rate of WSNs for the certain target area is defined as follows:

$$\begin{array}{cc}& f_c=\frac{A_{\text{active}}\cap A}{A}\times \mathrm{100}\%.\end{array}$$

(2)

In the above formula, $A_{\text{active}}$ is the acreage of effectively detecting area covered by the minimum connected tree. A stands for the acreage of the target region.

2.2.4. The Energy Consumption

According to the communication structure of minimum connected tree in WSNs, when a packet with k bits is transmitted from $s_i$ to $s_j$ , the energy consuming by $s_i$ is defined as follows:

$$\begin{array}{cc}& E_{ij}\left(k\right)=k\left(\mathrm{2}{E}_{\text{elec}}+E_{\text{amp}}\times d_{ij}^{\mathrm{2}}\right).\end{array}$$

(3)

$E_{\text{elec}}$ is the energy consumption of communication for a transmitter or receiver. $E_{\text{amp}}$ is the energy consumption of communication for an amplifier. $d_{ij}$ is the quadratic distance between $s_i$ and $s_j$ .

If the distance between two active sensor nodes is larger than the communication radius of the sensor node, the whole wireless sensor network is not fully connected. Because the sensor nodes are randomly deployed, it is difficult to ensure WSNs fully connected by arbitrarily selecting the active nodes. Considering the above situations, the energy consumption of $s_i$ is modified as follows:

$$\begin{array}{cc}& E_{ij}\left(k\right)=\left\{\begin{array}{cc}k\times \left(\mathrm{2}{E}_{\text{elec}}+E_{\text{amp}}\times d_{ij}^{\mathrm{2}}\right),\hfill & d_{ij}\le r_c,\hfill \\ k\times \left(\mathrm{2}{E}_{\text{elec}}+E_{\text{amp}}\times d_{ij}^{\mathrm{10}}\right),\hfill & d_{ij}>r_c.\hfill \end{array}\right.\end{array}$$

(4)

According to the above formula, if the distance between two sensor nodes is larger than the communication radius of sensor node, the required energy consumption of $s_i$ is far more than others.

The energy consumption of communication for the WSN is defined as the sum energy consumption that all active nodes send a data packet with k bits to the sink nodes [18]:

$$\begin{array}{cc}& E={\displaystyle \sum }_{i\in S^{\prime }}\left({\displaystyle \sum }_{\text{arc}(j,h)\in p^i}k\times \left(\mathbf{2}{E}_{\text{elec}}+E_{\text{amp}}\times d_{jh}^{\mathrm{2}}\right)-E_{\text{elec}}\right).\end{array}$$

(5)

In the above formula, $S^{\prime }$ is the active-node set. $p^i$ is the shortest path from $s_i$ to sink nodes. $d_{ik}$ is the quadratic distance between $s_j$ and $s_h$ .

The goal of the scheduling method is to keep the least sensor nodes active, which satisfies the monitoring and communication requirements with the minimum energy consumption, and put others into low-powered sleeping state. Hence the objective function of the scheduling optimization problem is shown as follows:

$$\begin{array}{l}\min \hspace{1em}E+p_c\times \left(\mathrm{1}-f_c\right)\\ \phantom{\text{i}}\text{s}.\text{t}.\phantom{\text{WI}}{f}_c>f_{\theta },\end{array}$$

(6)

where $f_{\theta }$ is the preset threshold of the network's coverage rate. $p_c$ is the penalty factor, which is used to penalize the acreage of the target region not covered by WSNs. From the above formula, we know that aforesaid model is in essence to find the fully connected minimum connected tree having minimum energy consumption and maximum coverage rate at the same time.

3. The Hierarchical Scheduling Scheme

The hierarchical scheduling scheme is in essence a multilayer dynamic scheduling strategy based on the node-failure pretreated strategy (FPS).

At first, the global optimization method is adopted to determine which sensor nodes are chosen from the nodes randomly deployed in the target area and activated so as to construct the minimum connected tree, in which all sensor nodes are fully connected and the coverage rate of corresponding network is larger than the preset threshold.

Secondly, when an active node is out-of-energy or failed, the full connectivity of the wireless sensor network is broken and its coverage rate for the target area is decreased. This invalid WSN must be restored in a very short time. For the sake of prolonging the network lifetime, the sleeping nodes need to be evaluated so as to find one being activated instead of the failed node rapidly. This process is called the recovery process of the WSN. In this paper, a dynamic multilayer recovery strategy is proposed to restore the broken WSN and ensure that the recovered network is fully connected, which keeps larger coverage rate than the preset threshold.

In a word, this dynamic hierarchical scheduling scheme combines the global optimization method with local multilayer recover strategy based on the node-failure pretreatment. The highlight of this scheme is the local multilayer recover strategy.

3.1. Finding Minimum Connected Tree by Global Optimization Method

It is difficult to find a fully connected active-node set, which has the least energy consumption and satisfies the requirement of coverage rate by the random selection method. In particular, it is time-consuming and no optimal solutions can be found for the WSN containing enormous sensor nodes. In order to efficiently obtain the minimum connected tree, genetic algorithm (GA) is adopted as the global optimization method.

Each individual is encoded as a binary vector representing a set of active nodes. The objective function expressed by (6) is defined as the fitness function of GA. The single point crossover operation and flip mutation operators are adopted during the evolution process. The pseudocode of the global optimization method is listed in Algorithm 1.

Algorithm 1: Global optimization.

input: A set of sensor nodes, sensing radius and communication

   radius of sensor node, size of the target area, preset threshold of

   coverage rate and other parameters

(1) Initialize the population;

(2) Evaluate initial population;

(3) while NOT stop condition do

(4) Single point crossover operation in terms of probability $$p_c$$ ;

(5) Flip mutation operation with mutation probability $$p_m$$ ;

(6) Roulette wheel select operation;

(7) Create the minimum spanning tree by Dijkstra algorithm;

(8) Evaluate new population;

(9) end while

From (4), we know that when the distance between two active nodes is larger than the communication radius, its energy consumption for sending data is set a large value. Subsequently, in the evolution of GA, the individuals containing disconnected sensor nodes will have the higher energy consumption and then cannot be selected into the offspring. Through the above definition and evolutionary operation, this algorithm can guarantee the full connectivity of active nodes in the WSN.

The optimal solution found by GA is the full-connected active-node set, which is having the lowest energy consumption and larger coverage rate than the preset threshold. If a sink node is regarded as the root of a minimum connected tree, these active nodes are connected by the minimum spanning tree and shortest path algorithms. Here, the shortest path between the sink node and each active node is calculated so as to build the minimum connected tree.

3.2. Local Multilayer Recovery Strategy

By the above global optimization method, the minimum connected tree of the WSN is established based on the shortest path between each sensor node and sink node. When an active sensor node is out-of-energy or failed, a local multilayer recovery strategy is proposed so as to find an optimal substitution node to repair the invalid network. The key issue of this strategy is how to measure the candidate nodes lying in the neighborhood of failed node according to some specific criteria and how to recover the invalid network as soon as possible. Consequently, the node's importance is defined to evaluate the sensor node and decide the size of neighborhood. And then a multilayer recovery strategy is proposed to repair the network step by step with less time-consumption in terms of certain rules.

3.2.1. The Definition of the Sensor Nodes’ Importance

The loss of the wireless sensor network caused by the failed sensor node is quite different. Several sensor nodes lying in the communication linkage of minimum connected tree are the articulation points. The failure of these nodes may result in the invalid linkage or disconnection from one or more other nodes to the sink node [19].

In order to rationally measure the destroyed degree of a failed sensor node to the whole WSN, the importance of sensor node is defined as a weighted sum of various losses caused by the failed node. Suppose $s_i$ is the failed node; $\text{C}{\text{R}}_i$ denotes the variation of the network's coverage rate caused by $s_i$ . $\text{A}{\text{R}}_i$ stands for the number of input and output paths associated with $s_i$ , which reflects the variation of the network's connectivity. α and β represent the weights of $\text{C}{\text{R}}_i$ and $\text{A}{\text{R}}_i$ , respectively. Consider

$$\begin{array}{l}{W}_i=\alpha {\text{CR}}_i+\beta {\text{AR}}_i\\ \text{s}.\text{t}.\hspace{1em}\alpha +\beta =\mathrm{1}.\end{array}$$

(7)

(A) Accumulative the Loss Function of the Coverage Rate. When a sensor node is failed, one or more nodes may be disconnected from the sink node. That means both the failed node and subsequently disconnected nodes cannot provide the valid monitoring information. Their coverage for the detecting area is blank [20]. So the variation of the network's coverage acreage caused by $s_i$ , expressed by $\text{CA}{\text{R}}_i$ , is defined as the sum of the acreage covered by the failed node and the cumulative acreage detected by all disconnected sensor nodes. Consider

$$\begin{array}{l}\text{CA}{\text{R}}_i={\displaystyle \sum }_{j=\mathrm{1}}^{\left|N_{S_i}\right|}A\left(s_j\right)-{\displaystyle \sum }_{j<k}A\left(s_j\right)\cap A\left(s_k\right)\\ +{\displaystyle \sum }_{j<k<l}A\left(s_j\right)\cap A\left(s_k\right)\cap A\left(s_l\right)\\ +\cdots +{\left(-\mathrm{1}\right)}^{n+\mathrm{1}}{\displaystyle \bigcap }_{j=1}^{\left|N_{S_i}\right|}A\left(s_j\right)-A_{\text{overlap}}\hspace{1em}{s}_j,s_k,s_l\in N_{s_i},\end{array}$$

(8)

where $N_{s_i}$ indicates a set of sensor nodes, which are disconnected from the sink node caused by $s_i$ . $A_{\text{overlap}}$ represents the overlapping acreage monitored by the failed sensor node and its neighbor nodes. Consequently, the variation of the network's coverage rate, caused by $s_i$ expressed by ${\text{CR}}_i$ , is defined as follows:

$$\begin{array}{cc}& \text{C}{\text{R}}_i=\frac{\text{CA}{\text{R}}_i}{A}.\end{array}$$

(9)

(B) The Loss Function of Connectivity. According to the location of each sensor node in the minimum connected tree, it is available in the distribution topology of its neighbor nodes. Thus, the sensor nodes in the minimum connected tree can be classified into two kinds as follows: boundary nodes and internal nodes. The boundary nodes are in the convex boundary of the minimum connected tree. There are no son nodes and only parent nodes for them. The internal nodes lie in the communication path between the sink node and the boundary nodes. Their neighbor nodes are normally more than one and there are both parent and son nodes for them. The classification of an active sensor node is judged by the distribution of its neighbor nodes within its communication radius.

Let $B_s$ be the boundary-node set and let $R_s$ be the internal-node set. $I_{s_i}$ represents the number of the input paths for $s_i$ , which is equal to the number of son nodes associated with $s_i$ . $O_{s_i}$ denotes the number of the output paths for $s_i$ , which has the same number as parent nodes associated with $s_i$ . As shown in Figure 1, $I_{s_{\mathrm{1}}}=\mathbf{2}$ and $O_{s_{\mathrm{1}}}=\mathbf{1}$ .

Figure 1

The son and parent nodes of $s_1$ .

Subsequently, the number of connected linkages associated with $s_i$ is defined as follows:

$$\begin{array}{cc}& n\left(s_i\right)=\left\{\begin{array}{cc}\left|I_{s_i}\right|\hfill & s_i\in B_s\hfill \\ \left|I_{s_i}\right|+\left|O_{s_i}\right|\hfill & s_i\in R_s.\hfill \end{array}\right.\end{array}$$

(10)

When a sensor node is failed, its connected linkages are all broken. So the loss function of connectivity denoted by $\text{A}{\text{R}}_i$ is as follows:

$$\begin{array}{cc}& \text{A}{\text{R}}_i=\mathbf{1}-e^{-n\left(s_i\right)}.\end{array}$$

(11)

In a word, the losing coverage acreage or the broken linkage is more after a sensor node is failed, and this node is more important.

3.2.2. The Neighborhood Radius

When a sensor node is failed, the most rational sensor node that reconstructs the WSN instead of the invalid one will be selected from its neighborhood. The size of neighborhood radius has the direct influence on the computation cost of this selection operation. According to the importance of sensor nodes, the neighborhood radius of a sensor node is defined as follows:

$$\begin{array}{cc}& n_r=\lambda r_c,\\ \lambda =\frac{W_i}{\max W_i}.\end{array}$$

(12)

It is obvious that the more important sensor node with larger $W_i$ , the larger neighborhood radius. That means more sensor nodes in the sleeping state are chosen into corresponding neighborhood of $s_i$ . Let $d(s_i,s_j)$ be the distance between $s_i$ and $s_j$ . Corresponding neighborhood of $s_i$ is obtained:

$$\begin{array}{cc}& N\left(s_i\right)=\left\{s_j\hspace{0.17em}|\hspace{0.17em}d\left(s_i,s_j\right)\le n_r,\hspace{0.17em}\hspace{0.17em}{s}_j\in S,\hspace{0.17em}\hspace{0.17em}{s}_j\ne s_i\right\}.\end{array}$$

(13)

Compared with LOA in hybrid algorithm, the proposed method based on the importance of sensor nodes can effectively shrink the searching range and save the computation time. Moreover, the optimum substitution node can be found by this algorithm as the same.

3.2.3. Constructing the Candidate-Node Set

It is necessary to choose a sleeping sensor node from the neighborhood of the failed node as a candidate so as to maintain the network's performances. Suppose $\text{CS}(s_i)$ is the candidate-node set of $s_i$ . $\text{Parent}(s_i)$ and $\text{Child}(s_i)$ stand for the parent-node set and son-node set of $s_i$ , respectively. The candidate sensor node $s_j\in \text{CS}(s_i)$ will meet the following conditions:

$$\begin{array}{l}d(s_j,s_i)\le n_r,\\ d\left(s_j,s_m\right)\le r_c\hspace{1em}\forall s_m\in \text{Parent}\left(s_i\right),\\ d\left(s_j,s_k\right)\le r_c\hspace{1em}\forall s_k\in \text{Child}\left(s_i\right).\end{array}$$

(14)

Each candidate sensor node for a failed node is marked in accordance with its coverage acreage and energy consumption. The feasible solution is chosen from the candidate-node set by taking account of the candidate node's location in the target area and the coverage requirements of the WSN. Consequently, we know when the sleeping sensor node will be activated and how it is connected with the whole wireless sensor network.

Taking Figure 2 as an example, many wireless sensor nodes have been randomly deployed in a 100 m × 100 m square detecting area. The minimum connected tree shown in Figure 2 is constructed by GA.

Figure 2

The minimum connected tree.

Furthermore, number 6 sensor node is deeply analyzed as an example. Its neighborhood radius is determined in terms of its importance. Subsequently, the candidate-node set of number 6 is constructed as shown in Figure 3. In Figure 4, all sensor nodes in the intersection of four areas such as circle domain, searching neighborhood of number 6, and the feasible communication area of parent nodes and son nodes form the candidate-node set of number 6 node. Any sensor node in the candidate-node set of number 6 can be connected to its parent nodes and son nodes.

Figure 3

Searching the neighborhood nodes based on the importance of number 6 node.

Figure 4

The candidate-node set of number 6 node.

3.2.4. Multilayer Recovery Strategy

When a wireless sensor network is invalid because of the failed nodes, the dynamic recovery strategy is proposed to repair the wireless sensor network as soon as possible. Its goal is to prolong the network lifetime and meet the requirements of the network's performances as well. The proposed multilayer recovery strategy consists of two phases.

In the first phase, the candidate-node set of each active node is established in terms of the neighborhood radius and the importance of the sensor node. As the failed sensor node happens, the whole network cannot work properly. At that time, an optimal sleeping node is selected from the candidate-node set of the failed node and then activated. This process is called node recovery strategy. However, if no sleeping sensor node can be found from the candidate-node set to replace the failed node, the local region associated with the failed node is considered as the repaired region. We call it regional recovery strategy in the second phase. Obviously, this multilayer recovery method adopts the principle of proximity to reduce the computation cost and improve the recovery speed for the broken WSN.

(A) Node Recovery Strategy. After a period of time, some active or working nodes may be failed or out-of-energy. Thus the whole wireless sensor network's performances, such as connectivity and coverage, will be affected. It is necessary to repair the faulted network by replacing the failed nodes in a short time. An optimal substitution sensor node is directly selected from the candidate-node set of the failed node and is activated later.

The optimal substitution node selected from candidate-node set will be a sleeping sensor node with the lowest loss of coverage efficient and full connectivity. That is, the following objective should be satisfied when a failed node $s_i$ is replaced by an optimal substitution node $s_j$ :

$$\begin{array}{cc}& \min \left|f_c\left(S_a\right)-f_c\left(S_a\cup s_j\setminus s_i\right)\right|+\left|f_e\left(S_a\right)-f_e\left(S_a\cup s_j\setminus s_i\right)\right|.\end{array}$$

(15)

In the above formula, $S_a$ is an active-node set. $f_c(S_a)$ is the coverage rate of the active nodes in original wireless sensor network before the failed sensor node occurs. $f_c(S_a\cup s_j\setminus s_i)$ is the coverage rate of repaired network, in which the failed sensor node $s_i$ is replaced by the candidate node $s_j$ . $f_e(S_a)$ is the overall communication energy consumption of the original network. $f_e(S_a\cup s_j\setminus s_i)$ is the overall communication energy consumption of the repaired network.

It is obvious that the necessary assumptions for node recovery strategy are that there exists an optimal sleeping sensor node chosen from the candidate-node set when a sensor node $s_i$ is failed. This candidate node will be activated and join the original minimum connected tree instead of $s_i$ so as to maintain the normal operation of the WSN. In such way, the requirements of the network's performances, such as the connectivity and coverage rate, must be satisfied.

(B) Regional Recovery Strategy. As time goes by, the number of failed nodes is gradually increased. After the candidate-node set is used several times for selecting the optimal substitution node, insufficient sensor nodes in candidate-node set can be found to satisfy the network's performances by the node recovery strategy. It is necessary to enlarge the recovered part in the minimum connected tree. Thus, a regional recovery strategy is done to find all of parent and son nodes of the failed node. The region needed to be repaired is determined by the largest distance of communication linkage from the failed node. The radius of the regional recovered region is defined as

$$\begin{array}{cc}& n_p=\max \left\{d_{s_p{s}_i},d_{s_q{s}_i}\right\}.\end{array}$$

(16)

In the above formula, $s_i$ is a failed node. $d_{s_p{s}_i}$ is the distance between $s_i$ and its parent node $s_p$ . $d_{s_q{s}_i}$ is the distance between $s_i$ and its son node $s_q$ .

By regional recovery strategy, the local minimum connected tree is repaired by selecting the valid sensor nodes in the recovered region, which connect the sensor nodes within two hops of the failed node and maintain the satisfied coverage rate with the lowest energy consumption.

The combination of local minimum connected trees in each region ensures full connectivity and efficient coverage requirement of the whole network. According to the regional recovery strategy, if no local minimum connected tree can make sure that the wireless sensor network is working properly, it is necessary to restart the global optimization for the rest sleeping sensor nodes.

The pseudocode of the local multilayer recovery strategy based on node-failure pretreatment is listed as Algorithm 2.

Algorithm 2: Local multilayer recovery strategy.

input: A connected coverage set $$S_a$$ obtained by Algorithm 1

(1) for all $$s_i\in S_a$$   do

(2) Evaluate the node's importance $$W_i$$ ;

(3) Decide the size of neighborhood $$n_r$$ ;

(4) Create its candidate-node set $$CS(s_i)$$ ;

(5) end

(6) if the network is broken by a failed node $$s_i\in S_a$$

(7)   if nodes in $$CS(s_i)$$ can replace $$s_i$$ in terms of (15)

(8)   Select an optimal node from $$CS(s_i)$$ ;

(9)   else if local MCT of $$s_i$$ satisfies the network's performance

(10)     Decide the radius of the regional recovered region;

(11)      Find the recovery region;

(12)   else

(13)     Restart global optimization /^*Algorithm 1^*/;

(14)  end if

(15) end if

(16) end if

4. Simulation Results

In order to evaluate the validity of the proposed scheduling method, a comparative study on the network's performance obtained from three kinds of algorithms is carried out. In addition to FPS, two other algorithms are hybrid algorithm [16] and GOD periodic algorithm [21]. Hybrid algorithm combined a global optimization strategy with a local recovery strategy. It provided the solution for reestablishing the network on the basis of the neighborhood of the failed node. The GOD periodic algorithm implemented the global optimization method periodically when the network is invalid. The proposed algorithm in this paper has the same structure as the hybrid algorithm. The difference between them is the local recovery strategy. The recovery radius or the neighborhood of the failed node is fixed in hybrid algorithm. However, the neighborhood of the failed node in the proposed local multilayer recovery strategy based on FPS varies with the importance of the failed node.

In order to analyze the rationality of the proposed local recovery strategy, FPS-based multilayer recovery strategy is compared with LOA in hybrid algorithm. In the experiments, the same number of sensor nodes and the same size of target area are used. The simulation results are the mean of 20 run times so as to ignore the disturbance caused by the contingency in the experiments.

Suppose the sensor nodes have been randomly placed in a 100 m × 100 m square area. Some important parameters shown as follows are used in the simulation experiments:

• (i)

the sensing radius: 15 m;

(ii)

the communication radius: 25 m;

(iii)

the energy consumption of the transmitter or receiver: 50 mAh;

(iv)

the energy consumption of the amplifier: 100 mAh.

Taking number 6 node as an example, the neighborhood of this node can be constructed according to two different strategies, respectively. As shown in Figures 5-6, different scales of neighborhoods are gotten by LOA-based hybrid algorithm and FPS-based hierarchical scheduling scheme, respectively. It is obvious that the neighborhood radius of number 6 gotten by FPS-based hierarchical scheduling scheme is much smaller than that obtained from LOA-based hybrid algorithm. The former is decided in terms of the importance of sensor nodes, whereas this latter is the communication radius in essence. However, no matter which kind of local recovery strategy is adopted, the optimal sensor nodes instead of the failed node are the same. That means when a sensor node is failed, the dynamic FPS-based local recovery strategy can find the optimal substitution node from the smaller neighborhood with the less computation cost. And the stability of the optimal solution is not affected simultaneously.

Figure 5

The neighborhood of number 6 node in hybrid algorithm.

Figure 6

The neighborhood of number 6 node in FPS.

Another experiment is done to compare the algorithms’ performances among the proposed FPS-based hierarchical scheduling scheme, hybrid algorithm, and GOD periodic algorithm. The performances of different strategies are evaluated with respect to the coverage rate, the number of active sensor nodes, consumed energy, residual energy, the network lifetime and the repair time of network, and so forth. The parameters used in GA are setting as follows:

• (i)

population size: 300;

(ii)

the number of generations: 150;

(iii)

the crossover probability: 0.7;

(iv)

the mutation probability: 0.02;

(v)

the coverage threshold: 0.9.

The coverage rate, the number of active nodes, the consumed energy, and the residual energy during the network lifespan are shown in Figures 7–10, respectively.

Figure 7

The network's coverage rate during the network lifespan.

Figure 8

The number of active nodes during the network lifespan.

Figure 9

The consumed energy during the network lifespan.

Figure 10

The residual energy during the network lifespan.

From the network's coverage rate during the network lifespan shown in Figure 7, we can see that the coverage rate obtained by FPS-based hierarchical scheduling method nearly keeps being the largest and exhibits the best stability compared to the other two algorithms before the failed sensor node occurs. The reason for that is that the multilayer recovery strategy in FPS-based hierarchical scheduling method finds the optimal substitution node directly from the candidate-node set and repairs the network by the regional recovery strategy when the local node recovery strategy is invalid. This recovery strategy can ensure the network's coverage rate above the preset threshold during the repair process and maintain the stable coverage to the target area.

From Figure 8, less sensor nodes are activated during the network lifespan by FPS-based hierarchical scheduling method, whereas the GOD periodic algorithm triggers the most active sensor nodes. For LOA-based hybrid algorithm, the same number of sensor nodes works in the WSN as FPS-based hierarchical scheduling method in the former phase. But the fluctuation of its quantity happens in the latter phase. In a word, the amount of active sensor nodes needed in FPS-based hierarchical scheduling method is most stable and the largest active-node set is only 8. When some active sensor nodes are in failure, the FPS-based local recovery strategy is adopted to repair the failed network by the candidate-node sets. The scale of the minimum connected trees remains constant during the node recovery process. Once the regional recovery strategy is done, the size of active-node set changes to the certain extent and remains stable.

For comparison on the consumed energy of three algorithms shown in Figure 9, we see that the energy consumption of the active network in FPS-based hierarchical scheduling method during the early network lifespan is slowly increased and then suddenly decreased when the continuous repair operation of the network is carried out. The reason for that is that the candidate node of the failed node considering both the connectivity and coverage rate may be not the optimal sensor node keeping the lowest energy consumption in the repaired network.

The residual energy shown in Figure 10 is basically a linear function of the network lifespan. GOD periodic algorithm makes the residual energy falling fastest whereas other algorithms decline slowly. That means FPS-based hierarchical scheduling method and LOA-based hybrid algorithm can make use of energy effectively. Furthermore, FPS-based hierarchical scheduling method is more efficient in energy because of the lower energy consumption and more residual energy during the network lifetime.

Comparisons on the performances, such as the network lifetime and the total repair time of network, are shown in Table 1. Here, the total repair time of network describes the sum of the running time of recovery operations in the scheduling algorithm. When a sensor node is out-of-energy or failed, the recovery operation will be done once. The running time of each recovery operation denotes the time interval from the time that the failed sensor node occurs to the time that the optimal candidate sensor node becomes active.

Table 1

Comparison of the network's performance.

Coverage threshold	Algorithms	Lifetime (s)	Repair time (s)
0.90	GOD	183925	1042.6
	Hybrid	199197	224.8
	FPS	172841	104.3
0.95	GOD	158488	1170.1
	Hybrid	159720	269.3
	FPS	146601	141.5
0.85	GOD	198151	887.1
	Hybrid	190962	235.3
	FPS	212683	133.3

The network lifetime of FPS-based hierarchical scheduling method is slightly lower than other algorithms because less candidate nodes can be found so as to ensure the repaired network satisfying certain performances as time goes by. And parts of the active sensor nodes having been working for a long time will be out-of-energy. But FPS-based hierarchical scheduling method has the shortest repair time compared to other algorithms. For example, in the condition that the threshold of coverage rate is 0.9, the repair time needed by FPS-based hierarchical scheduling method is 104.3 s, while the time intervals of hybrid algorithm and GOD periodic algorithm are 224.8 s and 1042.6 s, respectively. It is obvious that GOD periodic algorithm needs the most repair time because its global optimization process that searches for minimum active-node net is very time-consuming. For LOA-based hybrid algorithm, it is time-consuming for finding the optimal substitution node because the neighborhood radius is large. However, the FPS-based hierarchical scheduling method constructs the candidate-node set for each active sensor node in advance. If any active node is failed, the local node recovery strategy can find the optimal candidate node to repair invalid network in a short time or implement the regional recovery strategy in small area without doing the global optimization regularly. For this reason, FPS-based hierarchical scheduling method can quickly find the optimal substitution node for recovering invalid network and avoid the time-consuming searching work for finding the optimal candidate node in the larger neighborhood of the failed node in hybrid algorithm.

Finally, several experiments are done to compare the WSN's performances under different parameters or detecting conditions. The simulation results under various communication radii of sensor node, the size of target area, and the number of sensor nodes are shown in Table 2. Here, the threshold of the coverage rate is 0.9.

Table 2

Stability analysis of the proposed scheme.

$$r_c$$	The size of target area	The number of sensor nodes	Lifetime (s)	Repair time (s)
15	50 × 50	81	232959	516.4
20	50 × 50	81	190356	206.4
25	50 × 50	81	172841	104.3
25	50 × 50	100	219235	404.7
25	50 × 50	200	260230	547.7
25	60 × 60	81	160513	380.9
25	70 × 70	81	109602	485.4

When the communication radius of sensor node becomes larger, the network lifetime is effectively prolonged and the repair time of network is less. The reason for that is that the sensor nodes with larger communication radius need to consume more energy for transmit of the data. For the WSN with larger scale, its lifetime and repair time are gradually increased. It shows that there are more sensor nodes, which can be used to improve the network lifetime.

From Table 2, we know that WSNs obtained from the propose scheme have the relatively stable performances and are better suited to realities under different conditions. Therefore, the proposed scheduling algorithm can be adapted to different requirements of the network.

5. Conclusion

Being different from the traditional algorithms, a novel hierarchical scheduling scheme based on node-failure pretreatment is proposed in this paper. It adopts the same hybrid strategy as the LOA-based hybrid algorithm, in which the global optimization method is combined with the local online algorithm. The former is used to find the minimum connected tree, whereas the goal of the latter is to find a candidate sensor node instead of the failed one. In LOA, the candidate sensor node is in the neighborhood with the fixed radius. The unreasonable neighborhood radius makes the searching process time-consuming. To solve this problem, FPS-based local recovery strategy is proposed in this paper. Three highlights of this scheme are as follows: (1) The importance of sensor nodes is defined in terms of their location in the minimum connected tree and coverage acreage. (2) The neighborhood radius of failed sensor node varies with its importance, and then its candidate-node set is dynamically constructed. (3) A novel multilayer recovery strategy including node recovery and regional recovery is presented. The former two highlights are so-called node-failure pretreatment.

Simulation results show that FPS-based hierarchical scheduling method makes full use of the sensor nodes and prolong the network lifetime efficiently while quality of services of the network is guaranteed effectively. Compared with LOA-based hybrid algorithm and GOD periodic algorithm, the proposed FPS-based hierarchical scheduling method is superior to the others with respect to the repair time of the WSN and the scale of the active sensor nodes, but the network lifetime is slightly lower than two other algorithms. It is benefited from local multilayered recovery strategy based on the importance of sensor nodes and their candidate-node set. Moreover, the FPS-based hierarchical scheduling method can be applied in the problem that the communication radius of the sensor node is less than two times of its sensing radius, which means that the wireless sensor network is not fully connected in the target region while satisfying complete coverage. Hence, the proposed algorithm more fits for the practical scheduling of the WSNs. In the future, the dynamic scheduling approach with the larger network lifetime is still an interesting area of our works.