A Sleep Scheduling Mechanism with PSO Collaborative Evolution for Wireless Sensor Networks

Abstract

To extend the lifetime of a wireless sensor network and improve the energy efficiency of its nodes, it is necessary to use node collaborative sleep algorithm to reduce the number of redundant nodes in the network. This paper proposes a particle swarm optimization sleep scheduling mechanism for use in wireless sensor networks based on sleep scheduling algorithm. The mechanism adopts the approach of density control and finds the redundant nodes based on the computation results of the network coverage. Experimental results show that the proposed algorithm can ensure adequate coverage under the premise of the ability to close off the redundant nodes, while reducing the total energy consumption of the network.

1. Introduction

Sensor technology as an important access to information technology has been widely applied in the information age. In recent years, wireless communication and embedded computation have developed rapidly, and the generation of wireless sensor networks with sensing, computing, and wireless communicating capabilities brings great changes to human's life. For such reason, wireless sensor network has attracted wide attentions from academic field to industrial field. Wireless sensor networks (WSNs) constructed by cheap and tiny sensor nodes typically have self-organized and task-oriented structure topology. The sensor nodes in a wireless network have functions of sensing, data processing, and communications [1].

The WSNs have its constraints in energy supply and data processing and storage capabilities. Data is transmitted between nodes in a multihop pattern. If one node rejects to transmit data to other nodes for the purpose of saving its energy and extending its life, then the total throughput would drop dramatically, and the overall performance of the network would be undermined consequently [2]. Density control is a common solution, which schedules some redundant nodes into hibernation state when there is adequate network coverage [3]. As the nodes in sleep state hardly consume any energy, the total energy consumption of the network can be reduced. The network coverage is defined by the accuracy to which an object within the network is monitored or tracked by all the nodes in the network [4]. By communicating with neighbor nodes, each node determines whether it should turn into sleep state according to the collected information and the decision results of redundant authenticity policy. The distributed sleep scheduling strategy for nodes in WSNs has its advantages in good scalability, low cost, and easy implementation [5].

The dynamic sleep scheduling problem involves determining when each sensor should be involved in data gathering and when each of them should be put on the “standby” mode, so as to maximize the long-term reliability index of the system. Since the sensors are heavily energy-constrained, activating a sensor whenever possible may not be a good strategy. In order to extend the lifespan of a wireless sensor network and to improve the energy utilization efficiency of its nodes, this paper presents a PSO (particle swarm optimization) sleep scheduling mechanism for use in wireless sensor networks based on clustering algorithms and sleep scheduling algorithm. The mechanism adopts the approach of density control and finds the redundant nodes based on the computation results of the network coverage. Using a binary encoding mechanism and the approach of mutation and crossover operator in genetic algorithm, a discrete particle swarm optimization algorithm is formulated with its object function concerned about network coverage capability and energy consumption. Experimental results show that, by utilizing the proposed algorithm, the network coverage capability can be guaranteed and the redundant nodes can be turned off for sake of saving the network's energy consumption.

In this paper, a sleep scheduling mechanism with PSO collaborative evolution (SSM-PSO) for wireless sensor networks is proposed. The power is reserved by precisely scheduling the sleep control. The major purposes include $(1)$ to save power and increase the lifetime of entire network; $(2)$ to avoid the unbalanced spatial distribution of energy consumption using a clustering node sleep scheduling algorithm based on particle swarm optimization; $(3)$ to maintain network coverage and realize optimization goals of energy consumption reduction.

The paper is organized as follows: related works are briefly reviewed in Section 2; the system model and backbone node selection are described in Section 3; the details of SSM-PSO are presented in Section 4; the experimental simulation results are presented in Section 5; Section 6 finally concludes the paper and discusses some future research directions.

2. Related Works

Energy consumption remains a major bottleneck in the spread of WSNs technology, and how to efficiently use the energy and prolong the entire network's lifetime remains the major issues [6]. There are several kinds of energy consumption in WSNs, besides those corresponding to signal transmission and sensation. $(1)$ Collision [7]: the collision will occur if there are two nodes transferring data to the same node. In this case, both nodes would have to retransmit the data and the energy in the previous transmission process is wasted. $(2)$ Sparse area [8]: the nodes are normally deployed in a random manner; hence there will be sparse areas. The nodes in these areas will consume more energy in data transmission. $(3)$ Overhead [9]: when one node transmits data to the other nodes, its neighbor nodes would also receive the sent data, which is regarded as redundant information in this data transmission process and brings an energy waste.

Actually, the energy consumed by the radio transceiver in the idle state approximates that in the state of data transmission or reception. While the radio transceiver is set into sleep mode, power consumption would be significantly reduced. Thus, the most effective approach for energy saving is to design efficient duty-cycling schemes that have redundant sensors alternating between sleep and wakeup modes. In recent years, a very large number of energy saving schemes for WSNs have been proposed.

Heinzelman et al. [10] presented a general energy consumption model for communication components in a sensor device and analyzed the cluster-based data gathering scheme. Bhardwaj and Chandrakasan [11] discussed the upper bound of the network lifetime by considering the network topology and the data aggregation scheme. Li et al. [12] proposed an EEUC (energy-efficient unequal clustering) mechanism. This algorithm was designed to relieve energy cost pressure upon nodes near the sink node by assigning distinct sizes to clusters.

Several operational modes of a sensor node, including sleep and active modes, are modeled in [13] as a Markov chain and the energy dissipation level is computed based on stationary probabilities of operational modes. In [14], the authors study lifetime of WSNs with Gaussian-distributed nodes in a two-dimensional space. The main contribution is the identification of the key parameters for lifetime maximization and the proposal of two locating algorithms for the nodes. However, the achieved results can only apply to nodes with their locations conforming to Gaussian distributions and cannot easily be extended to the cases with other kinds of location distributions.

Cheng et al. advocated for the utilization of virtual backbones, in which a few nodes are in charge of collecting data from the remaining network nodes and transmitting them to the sinks [15]. In both approaches, chemical batteries supply power to all the nodes, restricting the network lifetime in case of a single backbone. To solve this problem, Zhao et al. offered solutions based on complicated algorithms, which schedule multiple overlapped backbones [16]. In particular, during the network operation, these algorithms determine the nodes that establish the backbone as a function of metrics, such as the residual energy level. Thereby, these nodes get a new role within the network. Theoretical results obtained by the authors show that virtual backbones balance the network energy consumption among all sensor nodes and considerably increase network lifetime. However, the real implementation of these algorithms in the nodes would entail a larger number of control messages as well as an increase in memory and processing demands, and these issues were not quantified by the authors. It should be mentioned that these findings are consistent with the work presented in this paper, since optimal primary node placement produces topologies similar to virtual backbones (as would be seen later in this paper).

In the same context, but referring to the placement of nodes in the area covered by the network, the work in [17] proposes to study the positioning method of the sensors in WSNs according to the point coverage. In point coverage which is shaped by some goal points, the sensor establishment determines the number of sensors needed for converging the points. In this reference, the point coverage takes place according to the position of the goal and angle of the goal points. Bin et al. [18] used the fish swarm (FS) and PSO algorithms hybrid to study the WSNs coverage problem. PSO algorithm was used in hybrid algorithm for higher efficiency and FS for covering the sensors. The results show that the hybrid algorithm is efficient enough in the deployment of the sensor of network and has solved the coverage problem. In some researches [19], the sensing coverage of a sensor is solved in a specified space for increasing the sensors’ energy utilization efficiency. Wang et al. [20] proposed a virtual force coevolutionary PSO (VFCPSO) for dynamic deployment of nodes to enhance the coverage.

The system model is presented in the third section, in which a discrete particle swarm optimization method is introduced, and then the sleep control mechanism is proposed. The forth section gives the simulation results and shows the assessment of the sleeping mechanism. A conclusion is finally made in the fifth section, in which the future research direction is suggested.

3. System Model

3.1. Network Structure

In this paper, the monitoring area of wireless sensor network is a circular area, with its center locating the converge node. There exists a hierarchical structure between the backbone nodes and ordinary nodes. The backbone node is the intersection of all self-avoiding walks connecting two nodes $p_{\mathrm{1}}$ and $p_{\mathrm{2}}$ of the lattice, which means that if we pass a current between $p_{\mathrm{1}}$ and $p_{\mathrm{2}}$ , the backbone is the set of nodes carrying current; all dangling ends are discarded.

With this structure, the information can be transmitted between ordinary nodes without passing the backbone nodes and the converge nodes.

There are two types of wireless sensor nodes in the network: the lower ordinary nodes and the upper super node. In the cluster structure of the network, the cluster head of the lower layer of the network is a cluster member of the higher layer of the network, and the cluster head of the upper layer is in charge of communicating with the sink node. The lower layer composed of ordinary nodes is resource constrained component, wherein the main task contains a small source node and relay node. A large number of source nodes are data acquisition, processing, and transmission of the relay nodes. The task is data processing and transmission. In the node energy consumption is the largest of the transceiver. The upper layer is composed of resource rich super nodes enlarging the transmission distance of wireless communication network. The super nodes in the larger, higher data transfer ratio area. The super node can therefore cover further tasks including data gathering, transmission, and implementation of complex algorithms.

The heterogeneous network has the following advantages.

• (1)

  Most of the time the ordinary node communication module can be closed or put into dormancy, long distance route will be composed of cluster head super node upper Unicom network transmits data, saving the network energy.

• (2)

  The cluster head fuses ordinary nodes before forwarding data, reducing the amount of data communication.

• (3)

  The common node function is relatively simple, no need to maintain the complex routing information, reducing routing control information and the amount of communication.

• (4)

  Cluster type topology structure is easy to manage and can change a rapid response; the system has good scalability and is suitable for large-scale network deployment.

The heterogeneous wireless sensor network can be considered as a spanning tree, and all the leaf nodes from the root node to the spanning tree can be used for data transmission. The leaf node (source node) data transfer to the super node; leaf nodes and super nodes such as jurisdiction can form a subtree, with the cluster head (super node) as its root, and the root of the whole tree (sink node) gathers all data. We defined that from the source node to the sink direction is called the downstream node and from the sink node to the source node direction is called the upstream nodes. Assume that the network has the following characteristics: $(1)$ H-WSNS is a static network; each node in the postdeployment is no longer mobile; $(2)$ each node knows its position, the cluster head super node position, and sink node location. Location information can be obtained by GPS or location protocol node position estimation based on transmission; $(3)$ energy of the super nodes can be adjusted according to the distance to the adjacent transceiver, in order to maintain the low power nodes; $(4)$ each node that obtains hop nodes adjacent to it by a periodic broadcast can be widely applied.

3.2. Backbone Node Selection

The residual energy, energy cost of communication, and connectivity of every node are taken in to consideration in selecting the backbone nodes. Each node i is assigned a weight function $T(i)$ , which reflects the node's priority of being selected as a backbone node. The bigger the value of $T(i)$ , the higher the priority of node i. The presentation of $T(i)$ is given as

$$\begin{array}{cc}& T\left(i\right)=w_{\mathrm{1}}\times \frac{E_{\text{res}}\left(i\right)}{E_{\text{init}}}+w_{\mathrm{2}}\times \frac{\text{neighbor}\left(i\right)}{{\text{neighbor}}_{\max }}+w_{\mathrm{3}}\times \frac{{\text{cost}}_{\max }}{\text{cost}\left(i\right)},\end{array}$$

(1)

where $E_{\text{res}}(i)$ denotes the residual energy of node i, $\text{neighbor}(i)$ denotes the number of neighbor nodes of node i, $\text{cost}(i)$ denotes the energy cost of nodes i for communication, ${\text{neighbor}}_{\max }$ and ${\text{cost}}_{\max }$ denote the maximal values of number of $\text{neighbor}(i)$ and the $\text{cost}(i)$ , respectively, and $w_1$ , $w_2$ , and $w_3$ are weighting factors selected according to actual situation, $w_1+w_2+w_3=1$ . Consider the fact that the higher the quality of the communication links between nodes, the more the residual energy of the directly connected nodes and the lower the information retransmitted rate of the network and the energy cost during communication.

This paper adopts the first-order wireless communication model [3] to quantify the energy cost in transmitting and receiving messages:

$$\begin{array}{cc}& E_{Tx}(l,d)=\left\{\begin{array}{cc}l{E}_{\text{elec}}+l{\epsilon }_{\text{fs}}{d}^{\mathrm{2}},\hfill & d\le d_{\mathrm{0}},\hfill \\ l{E}_{\text{elec}}+l{\epsilon }_{\text{amp}}{d}^{\mathrm{4}},\hfill & d>d_{\mathrm{0}},\hfill \end{array}\right.\\ E_{Rx}\left(l\right)=l{E}_{\text{elec}},\end{array}$$

(2)

where l denotes the bit size of the message to transmit or receive, d denotes the distance between the transmitting node and the receiving node, $d_{\mathrm{0}}$ is the threshold value of l, $E_{\text{elec}}$ denotes the energy cost of the node in transmitting or receiving one bit of the message, and ${\epsilon }_{\text{fs}}$ and ${\epsilon }_{\text{amp}}$ denote the energy cost of the amplify circuit in transmitting one bit of the message, corresponding to the free-space model and the multipath fading channel model, respectively.

The energy cost of a node during its communication with its $\text{neighbor}(i)$ neighbor nodes can be calculated by the following equations:

$$\begin{array}{cc}& \text{cost}\left(i\right)={\displaystyle \sum }_{j=\mathrm{1}}^{\text{neighbor}\left(i\right)}\sqrt{\frac{E_{Tx}\left(i\right)\times E_{\text{init}}}{Q(i,j)\times E_{\text{res}}\left(j\right)}},\\ E_{Tx}\left(i\right)=E_{\text{elec}}+{\epsilon }_{\text{fs}}{d}_i^{\mathrm{2}},\\ Q\left(i,j\right)=\text{RS}\left(i,j\right),\end{array}$$

(3)

where j denotes the index of the node directly communicating with node i, $Q(i,j)$ denotes the transmission quality between node i and node j, and $E_{Tx}(i)$ denotes the energy cost of node i in transmitting one bit of message. $\text{RS}(i,j)$ reflects the intensity of the signal received by node j from node i.

According to the measurement criterion of communication link quality, there is a relationship that the received signal strength indicator (RSSI) is proportional to the packet reception rate, and once the RSSI gets to certain threshold values, the packet reception rate of expected value can be obtained [8]. Based on this fact, the link's communication quality Q can be quantified by RSSI.

Algorithm 1.

Detailed procedures of selecting backbone nodes are as follows.

Step 1.

The algorithm's initialization: mark a random node as a white node according to the node's characteristics; select the converging node as the connection-dominating tree and mark it as a black node.

Step 2.

Let the black node be the father node and rank its neighbor nodes in a descending order according to their weight. Choose the first N nodes as the subnodes of the father nodes and mark these nodes as black nodes. The unselected nodes are marked as grey nodes.

Step 3.

Let the selected black nodes be subject to procedure 2 until all the nodes in the network are marked as black nodes or grey nodes.

Step 4.

A black node should be marked as grey node when there are no white nodes in its neighborhood.

Step 5.

Once the construction of the connection dominating tree is completed, all the black nodes would form a virtual backbone network. After some time the virtual backbone network engages into its working state; there would be deaths of nodes for energy exhaust.

The repair method for the dead nodes can be referred to as Algorithm 2.

Algorithm 2.

The repair of the dominating tree is as follows.

Step 1.

When there is a backbone node dead, all its neighbor grey nodes come into the state of candidate backbone nodes.

Step 2.

A candidate node should be marked as a backbone node if it is capable of connecting two backbone nodes which are not interconnected previously.

Step 3.

A candidate node should be marked as backbone node if it is capable of connecting one backbone node and other candidate nodes.

Step 4.

A candidate node should be marked as backbone node if it is capable of connecting two candidate nodes which are not interconnected previously.

Step 5.

A candidate node would switch into sleep state if it does not have any subnodes.

Step 6.

The repair process is completed once the connection of the virtual backbone network at dead nodes is recovered.

4. The Proposed SSM-PSO Algorithm

Coevolutionary algorithm evolves on the basis of the evolutionary algorithm, which is usually an adaptation algorithm that depends on the relationship between the individuals. Coevolutionary algorithm is widely used, especially for resolving complex and distributed problems, such as distributed computing, quantum computing, and automatic programming [21]. With the adoption of coevolutionary algorithm, which has implementation availability, computation efficiency and a variety of optimization problems (i.e., function optimization, multiobjective optimization, dynamic optimization, network optimization, and dynamic scheduling) can be addressed. Meanwhile, some coevolutionary algorithms are being designed to solve NP problems. In wireless sensor networks, coevolution is mainly used in the calculation of data fusion, network coverage, distributed computing, multiobjective optimization, robustness and fault tolerance, node inquirer mechanism, multi-agent-based routing transmission problems, low power consumption, and other research fields, and it achieved certain results.

PSO algorithm was first introduced by Kennedy and Eberhart in 1995 [22]. By inspiring the social behavior of the birds, PSO is a simulation of the birds’ behavior of search for food. None of the birds have information about the place of the food but they know in each stage how far they are from the food. On this basis, the best procedure to find food is to follow the nearest bird to the food. PSO algorithm is a population algorithm in which a number of the particles which are the solutions for a function or problem shape a population. PSO is an optimization algorithm which provides a search based on the population in which any particle changes its position by the time. In PSO algorithm the particles move in a searching space of multidimension including the possible solutions. In this space an evaluation factor is defined and the quality evaluation of the solutions of the problem takes place by it. Any change of a particle in a group is affected by the self's or other's experience and the searching behavior of a particle is affected by the other particles. This simple behavior causes finding optimized areas of the searching space. So, in PSO algorithm, any particle which finds the optimized situation informs the other particles in a suitable manner and any particle decides for the cost function according to the achieved values and searching takes place using the ex-knowledge of the particles. This causes the particles to not get near each other more than the normal and solve the optimization problem effectively. It is iterative optimization tools based on the system, which is initialized to a group of random solutions. Through iterative search for the optimal solution and in high-dimensional problem space, each particle is trying to track the optimal solution space. It provides a solution of complex problems without comprehensive control and global model. Compared with the GA (genetic algorithm) and other genetic algorithms, PSO is simple and easy to implement, in which there is not much to adjust the parameters, and does not require gradient information.

4.1. Encoding

Consider the case of implementing sleep schedule on a cluster with n members. Let a particle represent a feasible solution for the sleep scheduling problem; then its position at a given time can be described by an n-dimensional string with each component being 0 or 1. In other words, the position of particle i at time t can be expressed by a vector $X_i^t=(x_{i1}^t,x_{i2}^t,\dots ,x_{in}^t)$ , with $x_{ik}^t$ ( $k=\mathrm{1,2},\dots ,n$ ) the bit state of the member node k. Each element of the vector has its state reflected by its value, with 1 representing the node in working state and 0 representing the node in sleep state.

4.2. Initialization Phase

The node state bit of each particle is set to 0 or 1, and its value depends on whether the node can be covered by its neighbors when it is shut down. It is assumed in [21] that a sensor can always detect an event happening at the point with distance 0 from the sensor and the sensing accuracy is attenuated as the distance increases. Based on this assumption, a sensing accuracy model is formulated:

$$\begin{array}{cc}& \text{Cov}(s,p)=\frac{\mathrm{1}}{{\left[\mathrm{1}+\rho \text{DS}\left(s,p\right)\right]}^{\mathrm{2}}},\hspace{1em}d(s,p)\le R,\\ \text{Cov}\left(s,p\right)=\mathrm{0},\hspace{1em}d\left(s,p\right)>R,\end{array}$$

(4)

where $\text{Cov}(s,p)$ is the sensing accuracy of sensor s at point p, $\text{DS}(s,p)$ is the distance between sensor s and point p, and ρ is a constant used as an adjustment parameter. When the point p and the position of sensor node s coincide exactly with each other (i.e., $\text{DS}(s,p)=\mathrm{0}$ ), the node coverage probability is equal to 1. Coverage probability at any point is a number between 0 and 1, and if the point p falls into the overlap region, the coverage probability of point p would be influenced by the neighbor nodes. Assuming that there are N nodes $n_{\mathrm{1}},n_{\mathrm{2}},\dots ,n_N$ in the neighborhood of node s, with $R(n_{\mathrm{1}}),R(n_{\mathrm{2}}),\dots ,R(n_N)$ denoting the sensing area of each node, respectively, then the entire overlapping area of those nodes can be given as $\text{Mixed}\_\text{area}=R(n_{\mathrm{1}})\cap R(n_{\mathrm{2}})\cap \cdots \cap R(n_N)$ . According to the probability function, the coverage probability of any point in this overlapping area is

$$\begin{array}{cc}& {\text{Cov}}_p\left(P\right)=\mathrm{1}-\left[\mathrm{1}-S\left(s,p\right)\right]{\displaystyle \prod }_{i=\mathrm{1}}^N\left[\mathrm{1}-S\left(n_i,p\right)\right],\end{array}$$

(5)

where $S(s,p)$ and $S(n_i,p)$ are the coverage probability that the point p is situated in the sensing area of nodes s and $n_i$ , respectively, when there exist no adjacent nodes.

Once the distance between a sensor and a point is beyond a threshold distance, the sensing accuracy of the sensor at the point is negligible [23, 24]. The coverage probability of each node in the network is defined by a threshold value, which is the minimum probability of the node being monitored. Since the objective situates in the sensing area, the coverage of the sensor network at this point is

$$\begin{array}{cc}& {\text{Cov}}_{\text{node}}\left(s\right)=\min \left[{\text{Cov}}_p\left(p\right)\right],\hspace{1em}\forall p\in R\left(s\right),\end{array}$$

(6)

where p is the arbitrary point within the range R of sensor s.

Therefore, sensor network's coverage over the entire area can be calculated by taking the sum of network coverage of all points in the covered area

$$\begin{array}{cc}& {\text{Cov}}_n\left(N\right)=\min \left[{\text{Cov}}_{\text{node}}\left(s\right)\right],\hspace{1em}\forall s\in N,\end{array}$$

(7)

where ${\text{Cov}}_n(N)$ denotes the network coverage probability and s is a sensor node in the network. If the sensor in sleep state does not affect the coverage probability of the entire network, the node will be regarded as a redundant node, otherwise not. For the area covered by the node or its neighbor nodes, the coverage probability of this area can be calculated as

$$\begin{array}{ll}& {\text{Cov}}_{\text{node}}\left(s\right)\\ \hspace{1em}\hspace{1em}=\min \{\mathrm{1}-[\mathrm{1}-\text{DS}(s,p)]{\displaystyle \prod }_{i=\mathrm{1}}^N[\mathrm{1}-\text{DS}(n_i,p)]\}.\end{array}$$

(8)

After the node s turns into sleep state, the sensing area will be covered by its neighbor nodes. Then, the coverage probability of the area can be estimated via

$$\begin{array}{cc}& {\text{Cov}}_{\text{node}}{\left(s\right)}^{*}=\min \{\mathrm{1}-{\displaystyle \prod }_{i=\mathrm{1}}^N[\mathrm{1}-\text{DS}(n_i,p)]\}.\end{array}$$

(9)

If $C_{\text{node}}{\left(s\right)}^{*}<C_{\text{node}}(s)$ , the value of coverage probability of network nodes is $C_{\text{node}}(s{)}^{*}$ as some sensor nodes are put into the sleep state. It will result in a falling down of the coverage probability, and the node would not be redundant. On the contrary, if $C_{\text{node}}(s{)}^{*}\ge C_{\text{node}}(s)$ , which demonstrates that node s put into sleep state will not influence the coverage probability of the entire network, then whether a node is a redundant one would depend on whether the coverage probability is greater than the initial coverage probability after some nodes turn off.

4.3. Fitness Function

It is crucial to take into consideration the residual energy and the overlapped area, when choosing active nodes to achieve balance in energy consumption, and to reduce the area of network being perceived repeatedly. In the following, as far as the sleep nodes were concerned, redundant degrees of coverage would be considered as a key factor [25]. The overlapped coverage area, uniformity of coverage, and the residual energy are crucial for active nodes [26] and are defined as fitness functions, which have the following representations, respectively:

$$\begin{array}{c}f\left(X_i^t\right)=\alpha f_{\mathrm{1}}\left(X_i^t\right)+\beta f_{\mathrm{1}}\left(X_i^t\right)+\delta f_{\mathrm{1}}\left(X_i^t\right),\\ f_{\mathrm{1}}\left(X_i^t\right)=\mathrm{1}-\frac{{\sum }_{j=\mathrm{1}}^n{E}_{\text{res}}\left(j\right)\times X_{ij}^t}{{\sum }_{j=\mathrm{1}}^n{E}_{\text{init}}\left(j\right)},\end{array}$$

(10)

$$\begin{array}{c}{f}_{\mathrm{2}}\left(X_i^t\right)={\displaystyle \sum }_{j=\mathrm{1}}^n\sqrt{\frac{\mathrm{1}}{\text{neighbour}\left(j\right)}\times {\displaystyle \sum }_{i=\mathrm{1}}^{\text{neighbour}\left(j\right)}{\left(\text{DS}\left(i,j\right)-D_j\right)}^{\mathrm{2}}},\\ f_{\mathrm{3}}\left(X_i^t\right)=\frac{{\sum }_{j=\mathrm{1}\&\&X_{ij}^t==\mathrm{1}}^n{S}_j}{{{\displaystyle \bigcup }}_{j=\mathrm{1}\&\&X_{ij}^t==\mathrm{1}}^n{S}_j},\end{array}$$

(11)

where n represents the number of the members in a cluster and α, β, and δ are the weighting factors. There are 3 subfunctions constructing the whole fitness function. Here, $f_{\mathrm{1}}(X_i^t)$ denotes the ratio of the active nodes’ residual energy with respect to the total initial energy. Obviously, the ratio is inversely proportional to the total energy of the active nodes. $f_{\mathrm{2}}(X_i^t)$ denotes the centered degree, and a node closer to the center can cover a larger range of the area. $f_{\mathrm{3}}(X_i^t)$ is a measurement function measuring the redundant degree of the area which is monitored by active nodes. $S_i$ represents the sensing area of node i.

4.4. Scheme for Updating Particle's Location and Velocity

Traditional PSO algorithm is not suitable for solving this combinatorial optimization problem. In the proposed algorithm, the construction method for discrete PSO is adopted, and the mutation operators from genetic algorithms theory are used instead of normal formula for particles updating. The function can be defined as

$$\begin{array}{cc}& A_i^t=F_{\mathrm{1}}(X_i^{t-\mathrm{1}},w)=\left\{\begin{array}{cc}M\left(X_i^{t-\mathrm{1}}\right),\hfill & r_{\mathrm{1}}<w,\hfill \\ X_i^{t-\mathrm{1}},\hfill & \text{otherwise},\hfill \end{array}\right.\end{array}$$

(12)

where M is the mutation operator, $X_i^{t-\mathrm{1}}$ denotes the $t-\mathrm{1}$ generation solution for ith particle, $r_{\mathrm{1}}$ is a random number between 0 and 1, and w is the inertia weight which controls the present speed with the next one and creates a balanced state between the ability of the algorithm in local and global searching and then reaches the answer in a shorter time. Therefore, for optimized operation of the algorithm in the searching space, parameter w is defined as

$$\begin{array}{cc}& w=\exp (-\left|\frac{f_i-f_{gd}}{f_i-f_{id}}\right|)+w_{\min }.\end{array}$$

(13)

In the above formula, $w_{\min }$ is the final value of inertia weight in algorithm execution time and $f_i$ is the value of fitness function particle i. Besides, $f_{id}$ and $f_{gd}$ are partial extreme value and global extreme value for particle i, respectively.

Inertia weight value changes from 0.9 to 0.4 linearly during the program's execution process. Assigning large values to w leads to the global search while assigning small values leads to local search. To balance the local and global search, it is necessary to reduce the inertia weight during the algorithm's execution.

Secondly, according to the self-awareness and social consciousness, the particle updates its position and velocity by using a crossover operator:

$$\begin{array}{cc}& B_i^t=F_{\mathrm{2}}(A_i^t,c_{\mathrm{1}})=\left\{\begin{array}{cc}{C}_p\left(A_i^t\right),\hfill & r_{\mathrm{2}}<c_{\mathrm{1}},\hfill \\ A_i^t,\hfill & \text{otherwise},\hfill \end{array}\right.\\ X_i^t=F_{\mathrm{3}}(B_i^t,c_{\mathrm{2}})=\left\{\begin{array}{cc}{C}_g\left(B_i^t\right),\hfill & r_{\mathrm{3}}<c_{\mathrm{2}},\hfill \\ B_i^t,\hfill & \text{otherwise},\hfill \end{array}\right.\end{array}$$

(14)

where $C_p$ and $C_g$ are the functions for the crossover operator. The former function conducts a crossover operation of $A_i^t$ and the optimal solution for the particle i. While the latter one conducts a crossover operation of $B_i^t$ and the optimal solution for all particles. Besides, $r_{\mathrm{2}}$ and $r_{\mathrm{3}}$ are a random number between 0 and 1, and $c_1$ and $c_2$ are accelerating factors.

From (12) to (14), the update formula for particle i can be obtained as

$$\begin{array}{cc}& X_i^t=F_{\mathrm{3}}(F_{\mathrm{2}}(F_{\mathrm{1}}(X_i^{t-\mathrm{1}},w),c_{\mathrm{1}}),c_{\mathrm{2}}).\end{array}$$

(15)

In mutation stage, three vectors which differ from each other are selected randomly. For a vector x in population, a new answer in each repeated cycle is created according to (10). Crossover operator causes an increase in the population's diversity. This operator is similar to the crossover operator in genetic algorithm theory. To select the vectors of the highest priority, the vectors created by the mutation and crossover operators are compared with each other and the ones holding more suitability would be transferred to the next generation.

5. Simulation Results

In this section, the performance of the proposed approach is evaluated by related simulations. A simulator is designed and implemented in MATLAB in order to investigate the efficiency of the mentioned protocols. In addition, this paper takes the same parameter configuration as that in [27]. The simulation parameters and their values used in each experiment are given in Table 1.

Table 1

Experimental parameters.

Parameters	Value
Simulation area (m $$\times$$ m)	400 $$\times$$ 400
The station of base station	(200, 200)
Initial energy	2 J
$$E_{\text{fs}}$$	10 PJ/bit/m2
k	1000 bits
$$E_{\text{DA}}$$	5 nJ/bit/signal
$$E_{\text{elec}}$$	50 nJ/bit
$$E_{\text{amp}}$$	0.0013 PJ/bit/m4
$$d_{\mathit{0}}$$	90 m
n	300
$$\alpha$$	0.35
$$\beta$$	0.45
$$\delta$$	0.2
$$w_{\min }$$	0.4

We assess the performance of SSM-PSO under stationary operating conditions and compare it with other traditional sleep schedule schemes, that is, DPECC [28] and PSO-FS [29]. Assume that all sensor nodes are uniformly distributed within a circular region, and the sink node without any energy constraint is situated in the geometric center of the area. Periodically, all nodes will generate a data packet and send it to the Sink node. In order to improve the accuracy of the experiments, we have repeated the random deployment of sensors for 10 times, which can arrange different network topologies. Subsequently, the algorithm can be executed three times in case of each topology, and the average value is calculated as the final simulation result.

Figure 1 shows the energy consumption fluctuation as the distance from the virtual backbone nodes to the sink node increases. It can be seen from Figure 1 that the weight value of cost function has a relatively high impact on the energy consumption of the backbone nodes. Besides, sensor nodes close to the data sink consume more energy due to its responsibility for not only sensing but also forwarding data from its neighbor nodes. Therefore, those nodes that died earlier may affect the sensing area of the entire sensor network. Thus, minimizing the energy consumption can extend the life of the nodes and even the whole network.

Figure 1

The average energy consumption in SSM-PSO with different parameters.

Figure 2 shows the relationship between the energy consumption and the distance from backbone nodes to the sink, as far as different algorithms are concerned. It can be seen from Figure 2 that the energy distribution of virtual backbone nodes is relatively much higher in DPECC algorithm. Hence, high energy consumption at the certain nodes will result in hot-spot problem prematurely, which will seriously affect the life of the network. However, the probability is comparatively low in our method due to the optimization of density control factor. Variable rate optimization ensures that the residual energy of peripheral nodes can be utilized effectively, which extend the life of the network greatly.

Figure 2

The average energy consumption in DPECC, PSO-FS, and SSM-PSO.

Considering the impact of a collected data on forwarding delays, data generated periodically by all nodes may be of large size and cause considerable forwarding delays. Based on the analysis result on this kind of delay, the node-to-sink delay can be precisely estimated. Assume that all virtual backbone nodes use the same transmission rate $u=b\times C_r$ , where $C_r$ indicates the code rate of the transmitted data. Let the amount of data generated by each node in any ring area be denoted by ${\text{Data}}_m$ ; the maximum delay can be given as $T_m={\text{Data}}_m/(b\times C_r)$ . Thereby, the total delay of a packet transmitted from the ring m to the sink is equal to the sum of the m relay nodes; that is, $\sum T_m={\sum }_{j=\mathrm{1}}^m{T}_j={\sum }_{j=\mathrm{1}}^m({\text{Data}}_j/(b\times C_r))$ .

Figure 3 shows the average latency from virtual backbone nodes to the sink with different weighting factors being selected. It can be seen from Figure 3 that the backbone nodes near the sink node, especially the ones which can communicate with the sink node in one hop distance, can obtain the minimum end-to-end delay. On the other hand, the larger the data transmission rate, the smaller the transmission delay.

Figure 3

The average latency of the nodes in SSM-PSO with different parameters.

The comparison between DPECC, PSO-FS, and our scheme also concentrates on average latency, in other words, delay at nodes challenges with the real-time requirements of some systems. The variance of SSM-PSO in Figure 4 is much smaller than that of the other methods. The reason for this phenomenon is that the density control factor can optimize the data transmission rate so as to reduce the delay time at a certain place of backbone nodes. In SSM-PSO, the data forwarding maintains high quality of service performance and then implies good performance in balancing energy consumption for each hop routing.

Figure 4

The average latency of the nodes in DPECC, PSO-FS, and SSM-PSO.

Figure 5 shows the survival rate of nodes in DPECC, PSO-FS, and SSM-PSO as network scales change. The horizontal line corresponds to the number of rounds. We can see that the number of dead sensor nodes in PSO-FS is much greater than that in DPECC and SSM-PSO. This is because all nodes can only transmit data to the cluster head node indirectly, which makes the transmission distance from the common node to sink much shorter and therefore extends the network lifetime. These graphs show that the 5~10% lived nodes, 10~15% lived nodes, and last lived node die earlier in case of DPECC and PSO-FS, compared with SSM-PSO. We also find that SSM-PSO can obtain comparatively higher survival rate than other protocols in most rounds. From further investigation, it is found that SSM-PSO may survive longer than others in terms of the different deployment of nodes, and by utilizing SSM-PSO good scalability can be obtained.

Figure 5

Nodes survival ratio.

To investigate the sensor's performance in terms of energy consumption, we compare the energy consumption of the nodes in DPECC, PSO-FS, and SSM-PSO during the simulation runs. As can be seen from Figure 6, it is obvious that SSM-PSO can obtain much less energy consumption ratio compared to other protocols, which is mainly due to the sleep scheduling mechanism based on particle swarm optimization and sleep scheduling method. The energy consumption ratio of the nodes in DPECC is much greater than other protocols in most rounds, and this is because many nodes are required to possess geographic information that is obtained with difficulty in wireless sensor networks since the devices that operate via the geographic positioning system consume a large amount of power. Therefore, it has been clearly shown that SSM-PSO performs more energy-efficiently and is better in prolonging network lifetime and balancing energy consumption compared to PSO-FS and DPECC.

Figure 6

Energy consumption ratio.

Figures 7(a)–7(c) also compare the performance of these protocols in case of the failure probability of the nodes in the cluster when $P_{\text{node}}$ = 0.02, 0.04, and 0.08. It can be observed that there is a downward trend in the packet transmission rates as the failure probability increases. This phenomenon indicates that the performance declines as the failure nodes increase. The curve corresponding to the packet transmission degree of SSM-PSO is much smoother than that corresponding to PSO-FS and DPECC, which reflects that the SSM-PSO has better fault tolerance. The proposed algorithm can improve the particle swarm optimization's responsiveness and efficiency in the search space of high-quality solutions.

Figure 7

Packet delivery ratio.

The bar graph displayed in Figure 8 represents summary statistics for the analysis of nodes’ sleep degree. As can be seen from the result, RS and ENS sleep maintain a low rate and keep a stable trend as the network size changes. Although NS has a relatively high rate of sleep, it does not increase as the network scale grows. However, sleep rate of SSM-PSO increases with the sustainable growth of the network scale. This is consistent with the actual situation, in which the increase of the network's size does not affect the monitoring region. It can be seen that SSM-PSO algorithm not only has a higher rate of sleep nodes, but also makes the variation of sleep degree suitable for the actual applications.

Figure 8

Comparison of sleep rate.

Figure 9 compares the coverage rate of those protocols. It can be seen that SSM-PSO maintains a higher coverage rate than other protocols, and NS shows the worst performance in spite of a rather high sleep rate of nodes. It is noted that there is no balance between raising network coverage and reducing active nodes for NS; this will affect the overall performance of the network. It can be observed from Figure 9 that low-cost sleep rate can enlarge the coverage of these two algorithms but is not conducive in reducing network energy consumption. Then, it can be found that SSM-PSO can also maintain high coverage with a high sleep rate in the meantime. Figure 10 compares the overlapping coverage rate of those protocols. The overlapping coverage rate of SSM-PSO is relatively lower than that of the other algorithms, which indicates that SSM-PSO improves the effectiveness of the network energy consumption and has better performance in maintaining the network coverage.

Figure 9

Comparison of coverage rate.

Figure 10

Comparison of overlapping coverage rate.

Through the above experimental results, it can be observed that the energy distribution of virtual backbone nodes is very even in SSM-PSO algorithm, and the data forwarding maintains high quality of service performance and then implies good performance in balancing energy consumption for each hop routing. Thus, the SSM-PSO algorithm not only has a higher rate of sleep nodes, but also makes the variation of sleep degree suitable for the actual applications.

6. Conclusions

Scale and density of deployment, environmental uncertainties, and constraints in energy, memory, bandwidth, and computing resources present great challenges to the developers of WSNs. Meanwhile, issues of node deployment, localization, energy-aware clustering, and coverage are often formulated as optimization problems. In this paper, a sleep scheduling mechanism with PSO collaborative evolution is proposed for use in wireless sensor networks. In SSM-PSO, the binary encoding mechanism is adopted, and mutation and crossover operators from the genetic algorithm are introduced into the proposed algorithm. The maintenance of network coverage and the optimization goals of the reduction of energy consumption are taken into account, and a corresponding discrete particle swarm optimization method is constructed. Simulation results show that SSM-PSO improves the effectiveness of the network energy consumption and has better performance in maintaining the network coverage.