Keywords

1 Introduction

With the development of Internet and artificial intelligence technology, CPS, a multi-dimensional complex system that integrates computing, network and physical environments, is being widely used in smart cities, smart manufacturing, national defense security and other fields [20]. WSN is located in the data perception layer of the smart city’s technical architecture. It is responsible for the necessary data collection and measurement functions and participates in the important work of realizing the interaction between the CPS system and the physical environment [1].

WSN is composed of a series of sensing nodes and data storage receivers. Coverage awareness service is the main indicator for evaluating WSN service quality. Due to the limitations of some practical application environments, WSN mostly adopts random spraying for initial deployment. Although this method is more convenient, it often causes problems with coverage holes and redundancy. WSN sensing nodes are mainly powered by their own batteries [2]. Therefore, how to reduce and balance the energy consumption of redeployment is an important consideration for improving the working life of WSN.

From the perspective of perception range and energy, WSN redeployment is a multi-objective problem, and all feasible solutions need to be evaluated to determine the optimal solution. Particle swarm algorithm has the advantages of fewer parameters and fast convergence, but it’s easy to fall into a locally optimal state. This paper proposes a multi-objective optimization model of WSN redeployment coverage based on the particle swarm algorithm, which aims to improve the area coverage and balance the mobile energy consumption among nodes, finally extend the overall operation time of the network. The main contributions of this article are as follows.

  • A novel method is proposed to reduce the redeployment coverage problem in the hybrid WSN environment to a multi-objective optimization problem for area coverage rate and moving energy consumption deviation. Simultaneously, based on two randomly distributed scenarios, the above problem is analyzed.

  • A two-stage method is proposed to optimize the multi-objective fitness function. On the premise of high-quality coverage, let as many mobile nodes as possible spread the deployment optimization work equally. At the same time, we regard the node movement as the result of the common action of various forces in a physical filed.

The rest of this paper is structured as follows: Sect. 2 introduces related work. Section 3 describes the WSN coverage analysis model and detailed redeployment optimization problems. Section 4 shows the design and implementation of our proposed algorithm. Section 5 describes the experimental environment settings and comparative experimental analysis. Section 6 summarizes this paper and looks forward to future work.

2 Related Work

Coverage perception is a research hotspot in the field of WSN. WSN can be divided into three states according to the mobility of nodes: static, mobile and hybrid. For different node types, there are different ways of coverage optimization.

The movement constraints of static nodes make it more restrictive in redeployment. Static WSN mostly adopts the node state rotation mechanism to expand the coverage and increase the working life of the network. Semprebom [14] proposed a (m, k)-Gur strategy, which provides a unified coverage monitoring application. The node autonomously performs a self-regulating choice, sends a message to the base station or sleeps to the next period. Habib Mostafaei [12] proposed a PCLA sleep scheduling algorithm that relies on an automatic learning machine to minimize the number of active sensors covering the monitoring area in order to improve the scalability and life cycle of the network. Ying Tian [17] made the nodes which have more remaining energy become work state to achieve the alternation of the multiple coverage sets. J. Sahoo [13] proposed a greedy algorithm based heuristic to schedule the sensors states in order to increase the network lifetime. Riham Elhabyan [5] combined the coverage-aware sleep scheduling with the clustering and proposed an discrete energy consumption model which depends on the status of sensors rather than distance.

Compared with static nodes, there are more research methods for mobile node optimization redeployment. Tongxin Shu [16] proposed a coverage optimization algorithm combining Voronoi Diagram and geometric center to maximize area coverage and minimize energy consumption under the constraints of communication range. Yaobing [10] proposed to adjust virtual force parameters based on the energy of neighbor nodes, and measure the uniformity as an experimental indicator. In addition, biologically heuristic intelligent optimization algorithms have also received extensive attention in this field. Mihoubi [11] proposed an algorithm that uses hybridization to improve the speed of bats and combines the Doppler effect to promote positioning performance. Bin Yu [8] proposed a periodic hybridization method to enhance the global search capability of the PSO algorithm and obtained higher convergence speed and area coverage rate. Amulya Anurag [3] proposed a negative speed PSO algorithm to improve the local search ability and obtain higher coverage efficiency. Tingli Xiang [19] proposed an optimization based on Cuckoo Search (CS) which divided the algorithm into two stages. The former is responsible for improving coverage rate, while the latter aims to reduce the average moving distance of mobile nodes and reduce energy consumption. S.T. Hasson [7] utilized the angle between two adjacent nodes to assign an optimal deployment scheme.

Now researchers are not only pursuing high coverage rate, but also tend to consider redeployment problem from the perspective of energy consumption. This paper describes the redeployment coverage problem as a multi-objective optimization, and proposes an improved virtual force particle swarm algorithm based on the characteristics of WSN mobile nodes. This paper uses weight coefficients to balance the goals, aiming to increase coverage rate and reduce mobile energy consumption deviation, so as to improve the coverage perception ability and network running time of WSN.

Fig. 1.
figure 1

The system architecture

Full size image

3 Analysis Model and Problem Statement

3.1 Network Model

For the convenience of research, this paper divides the two-dimensional monitoring area into \(L_x \times L_y\) grids, and analyzes the N mobile nodes and M static nodes scattered in the binomial disc model shown in Fig. 1. Except for mobility, other properties of sensing nodes are the same. The perceived probability of nodes \(S_i\) to grid point q is shown in Eq. (1).

$$\begin{aligned} C(S_i,q)= \left\{ \begin{array}{lr} 1 &{} {d(S_i,q) \le r}\\ 0 &{} {d(S_i,q) \&{}gt;r} \end{array} \right. \end{aligned}$$
(1)

Where r is the perception radius. \(d(S_i,q)\) is the Euclidean distance \(S_i\) to the grid nodes q. Therefore, the node perception coverage rate Cov of the monitoring area is shown in Eq. (2).

$$\begin{aligned} Cov= \sum _{q=1}^{L_x\times L_y}\sum _{i=1}^{N+M}{\frac{C(S_i,q)}{L_x\times L_y}} \end{aligned}$$
(2)

The moving distance deviation of all nodes is expressed as:

$$\begin{aligned} Std\_S= \sqrt{\frac{(\sum _{i=1}^{N}(dis_i-avg\_dis)^2)}{N\times (N-1)}} \end{aligned}$$
(3)

\(dis_i\) is the moving distance of node \(S_i\), \(avg\_dis\) is the average moving distance of all nodes in the monitoring area. This paper focuses on the coverage optimization of hybrid WSN redeployment, which aims to improve area coverage rate and reduce the energy consumption deviation of nodes. Reference [10] knows that the energy consumption of a node movement is directly related to its distance. Therefore, the problem of moving energy consumption deviation can be converted into a moving distance deviation. Now, the multi-objective optimization model is shown in Eq. (4).

$$\begin{aligned} \left\{ \begin{array}{lr} max\_Cov(x)\\ min\_Std\_dis(x)\\ x \in L \end{array} \right. \end{aligned}$$
(4)

In Eq. (4), the former two terms are respectively the maximum optimization of area coverage rate and the minimum optimization of movement deviation. The last one represents the boundary constraints of node movement. We refer to [6] normalize the targets value and utilize \(\alpha \) to balance their weight. Based on the calculation of coverage rate and movement deviation in the redeployment optimization process, the fitness function of our algorithm is shown in Eq. (5).

$$\begin{aligned} fitness(x)=\alpha \times f(Cov(x))+(1-\alpha )\times f(Std\_dis(x)) \end{aligned}$$
(5)

We consider the WSN redeployment coverage that maximizes the fitness function fitness(x) under boundary constraints.

3.2 Problem Statement

Based on the above analysis model, we mean to find a WSN redeployment scheme x that maximizes the fitness under boundary constraints. The problem is described formally by Eq. (6).

$$\begin{aligned} \left\{ \begin{array}{lr} find\quad x=(x_1,x_2 \cdots ,x_N)\\ which\, max(\alpha \!\times \! f((Cov(x))+(1-\alpha )\!\times \! f(Std\_dis(x))\\ s.t.\quad x_i \in L \end{array} \right. \end{aligned}$$
(6)

This is a D-dimensional decision vector. The model parameters and corresponding descriptions are summarized as shown in Table 1.

Table 1. Summary of model parameters
Full size table

4 Multi-objective Two-Stage PSO Algorithm

4.1 Algorithm Parameters in WSN Deployment

Although there are many other swarm intelligence algorithms. They have some inapplicability based on the current scene. For example, cuckoo search algorithm(CS) [19] uses Levy flight mechanism for birds, which is a random walk consisting of short-distance flight with small step length and occasional long-distance flight with large step length. So it is easy to appear in the area around the global optimal shock phenomenon, lower algorithm efficiency, etc. Besides, genetic algorithm (GA) is also a common swarm intelligence algorithm. However, it need coding and has crossover, mutation operation. So GA has many parameters and is complicated to implement [4].

Based on the observation of animal by individuals in the group to make the swarm activity behaviors, the particle swarm algorithm (PSO) uses the sharing of information movement of the entire group produce an evolutionary process from disorder to order in the problem solving space to obtain the global optimal solution [15]. On the one hand, PSO algorithm may converge to the optimal solution more rapidly. On the other hand, it does not need coding, does not have many parameters, only through the current search to share information, and uses internal speed to update, the principle is simpler, and the implementation is easier. Last but not least, PSO algorithm is mainly applied to continuous problem. Therefore, PSO algorithm is suitable for WSN redeployment coverage problem.

$$\begin{aligned} \begin{aligned} {V_i}^k=w\times {V_i}^{k-1}+c_1\times r_1\times (pbest_i-{X_i}^{k-1})+c_2\times r_2\times (gbest_i-{x_i}^{k-1}) \end{aligned} \end{aligned}$$
(7)
$$\begin{aligned} {X_i}^k={X_i}^{k-1}+{V_i}^k \end{aligned}$$
(8)

This paper mainly analyzes the coverage problem of mobile node redeployment in the two-dimensional monitoring area. Assuming that the population size Num is the number of candidate schemes, the search space dimension is related to the coordinate dimension of mobile nodes in the monitoring area. The speed and position update equation of the particle swarm algorithm are shown in Eq. (7) and Eq. (8) which represent the nodes’ movement change and the redeployment scheme currently. In Eq. (7), \(c_1\) and \(c_2\) are the weight coefficients of the particle tracking the historical local and global optimization redeployment solution respectively. In the original particle swarm algorithm, the inertia weight decreases linearly with the number of the iterations increases, as shown in Eq. (9). Maxiter is the maximum number of iterations, and k is the current number of iterations.

$$\begin{aligned} w^k=w_{max}-(w_{max}-w_{min})\times {\frac{k}{Maxiter}} \end{aligned}$$
(9)

4.2 Algorithm Design

The original particle swarm algorithm is prone to fall into the dilemma of local optimal. Therefore, it must be improved to obtain the global optimal solution. This paper refers to the idea of [19] and divides the important into two parts. Firstly, set the inertia weight to a non-linear decreasing form to better balance the global and local optimization capabilities of searching particles. Secondly, abstract the monitoring area as a physical field, and introduce a virtual force mechanism to promote the uniformity of node distribution. The algorithm model is shown in Fig. 2.

Fig. 2.
figure 2

The architecture of our algorithm

Full size image

Non-inertial Weight

$$\begin{aligned} w=w_{min}+(w_{max}-w_{min})\times exp(-20\times (\frac{k}{Maxiter})^5) \end{aligned}$$
(10)

Because the slope of the linearly decreasing inertia weight is fixed, the change of speed always remains at the same level. If the initial iteration does not produce good results, then as the iteration increases and the speed decays, it is likely to fall into a local optimum in the end. As shown the w1 in Fig. 3, the nonlinear inertia weight proposed in this paper has a larger parameter value in the early stage, which improves the global search ability. Keeping a smaller value in the later stage is beneficial to local search and accelerate the convergence of the algorithm.

Fig. 3.
figure 3

The change of inertia weight with the number of iterations

Full size image

Virtual Force Mechanism. This paper abstracts the entire monitoring area as a physical field, and the change of node location is regarded as the result of force objects under the influence of various forces. It refers to [18] to calculate the repulsive force of a mobile node by its neighbor nodes and the attractive force of surrounding uncovered grid points. The specific force analysis is shown in Eq. (11).

$$\begin{aligned} \mathbf {F}_{ij}= \left\{ \begin{array}{lr} W_a\times d_{ij},\alpha _{ij}&{} D_{th}<d_{ij}<R\\ 0,&{}d_{ij}=D_{th}||d_{ij}>R\\ W_r\times d_{ij},\alpha _{ij}+\pi &{} otherwise \end{array} \right. \end{aligned}$$
(11)

Among them, \(W_a\) is the attractive coefficient, \(W_r\) is the repulsive coefficient, \(D_{th}\) is the distance threshold, and \(\alpha \) is the orientation of the line segment from mechanical object i to applying object j. Although static nodes will not move, they still exert force on mobile nodes. Under the action of virtual force, the location change of mobile nodes in the horizontal and vertical directions is shown in Eq. (12).

$$\begin{aligned} \left\{ \! \begin{array}{lr} x_i(k+1)=x_i(k)+\frac{F_x}{F_{xy}}\times MaxStep\times e^{\frac{-1}{F_{xy}}},F_x\ne 0\\ y_i(k+1)=y_i(k)+\frac{F_y}{F_{xy}}\times MaxStep\times e^{\frac{-1}{F_{xy}}},F_y\ne 0\\ \end{array} \right. \end{aligned}$$
(12)

Among them, \(x_i(k)\) and \(y_i(k)\) are the original position coordinates of node \(S_i\) before the change, \(F_x\) and \(F_y\) are the horizontal and vertical components of the resultant force on node \(S_i\). When the calculation result of the node position change exceeds the scope of the monitoring area, the latest position is set as the boundary value closest to the result, as shown in Eq. (13).

$$\begin{aligned} \left\{ \begin{array}{lr} x_i(k+1)=L_x,&{}x_i(k+1)\notin L_x\\ y_i(k+1)=L_y,&{}y_i(k+1)\notin L_y \end{array} \right. \end{aligned}$$
(13)

Compared with other interference strategies [8], the virtual force method calculates the moving distance and direction of the target node by analyzing the relative distance between the target nodes and other nodes and uncovered grid points within the communication range. The movement distance is small and the overall coverage tends to increase.

4.3 Algorithm Implementation

figure a

Based on the above-mentioned inertial weight improvement and virtual force mechanism, we design a Multi-Objective Two-Stage PSO algorithm, which can be abbreviated as MTPSO, to reduce WSN deployment coverage problem. The specific implementation is shown in the pseudo code of Algorithm 1. MTPSO firstly initializes the position of the particles (that is the randomly distributed node deployment plan), speed and other necessary parameter settings (see 1). Then it utilizes a two-stage iterative optimization within the Maxiter iterations constraint, of which the first stage is updating the speed and position, providing candidate target deployment (see 4–6); the second stage is adjusting the relative position among nodes according to the virtual force mechanism to optimize the candidate target position (see 8–10). Finally, it updates the global optimal deployment plan of the current particle swarm, according to the value of fitness (see 11).

5 Experimental Evaluation

5.1 Environment Parameter

The experimental environment of this article uses MATLAB 2014R. The size of the monitoring area is \(L_x\times L_y=20\times 20\), where the grid size is \(px\times py=1\times 1\), the node perception radius r=3, and the communication radius \(R=2\times r\). In practical applications, the initial deployment of WSN nodes affected by the physical environment mostly presents the data characteristics of Gaussian distribution [9]. This paper analyzes two initial deployments: Gaussian randomness and uniform randomness. Experiment parameters are shown in Table 2.

Table 2. Summary of model parameters
Full size table

5.2 Determination of Target Weight

To determine \(\alpha \) in Eq. (5), which ranges in 0.1–0.9. We conduct comparative experiments for different values of \(\alpha \) when the proportion of mobile nodes is 1. The experimental results are obtained by 50 independent replicates, as shown in Table 3. It is obtained through experiments that when the coverage rate is used for single-objective optimization, the worst \(Std\_dis\) of the MVFA algorithm is 9.0647. Therefore, 10 is regarded as the empirical maximum value of the movement deviation. It can be seen from Table 3 that with the coverage rate target coefficient increases, the value of fitness gradually increases.

Table 3. Summary of model parameters
Full size table
Fig. 4.
figure 4

Changes in fitness and optimization goals under different weights

Full size image

As the weight coefficient \(\alpha \) increases, the optimization target value of the coverage rate in the fitness function becomes more and more important, while the importance of the moving distance deviation decreases. Both targets tend to be optimized with larger weight coefficients. However, two targets cannot be maximized at the same time. The variance of the coverage rate is 0.0060, while the variance of the movement distance deviation is 0.5140, indicating that as the weight increases, the coverage rate fluctuates less than the deviation as shown in Fig. 4. In order to obtain the near-optimal solution, we set a largest weight for the coverage rate target, which is 0.9.

5.3 Algorithm Comparison

We compare MTPSO with typical coverage optimization algorithms, including OPSO, EPSO in [8] and MVFA in [10]. OPSO is the original particle swarm algorithm, and its inertia weight decreases linearly with the increase of iterations. EPSO uses periodic mutation to improve the global search ability. MVFA is based on a traditional virtual force algorithm, which adjusts the attractive force coefficients.

Comparison of Goals and Fitness Values. The performance of the four algorithms is developed from multiple perspectives: fitness, \(Std\_dis\) and Cov. In addition, the energy consumption in the redeployment process is directly related to the movement of the node. Therefore, we also compare the total moving distance and the deviation of the moving distance among nodes. We present experimental configurations of five different scale networks with a ratio of mobile nodes ranging from 0.2 to 1 with an interval of 0.2 under two different initial deployments.

Fig. 5.
figure 5

The influence of the proportion of mobile nodes on the fitness function

Full size image

It can be seen from Fig. 5 that as the proportion of mobile nodes Pr increases, the value of fitness increases rapidly in the early stage, and tends to stabilize in the later stage. This shows that the mobility of the node has a very positive effect on the optimization, but the final effect will gradually decrease with the increase of Pr. Since the target weight \(\alpha \) selected in this experiment is 0.9, the change trend of fitness and Cov is roughly same as shown in Fig. 5 and Fig. 6. At the same time, MTPSO has the best coverage rate under both random initial deployments as shown in Fig. 6.

Fig. 6.
figure 6

The influence of the proportion of mobile nodes on coverage

Full size image
Fig. 7.
figure 7

The influence of the proportion of mobile nodes on movement deviation

Full size image
Fig. 8.
figure 8

The influence of the proportion of mobile nodes on the total moving distance

Full size image

It can be seen from Fig. 7 that the movement deviations \(Std\_dis\) of MTPSO, EPSO and OPSO are all lower than 3, and when Pr=0.2, the \(Std\_dis\) value of MTPSO is only 0.1986, indicating that the energy consumption among mobile nodes is relatively balanced. In general, the particle swarm algorithm is more suitable for the global optimization than the MVFA algorithm. It can be seen from Fig. 7 that the type of initial deployment has a great impact on the movement distance deviation \(Std\_dis\), especial for MVFA and EPSO. Although the \(Sum\_dis\) of MVFA indicators are both maximum in both types, but the one in Gaussian is much smaller than that in the uniform type. However, the \(Std\_dis\) of EPSO performs better in uniform initial deployment. This is because of the two optimization measures are based on different objects. MVFA uses local virtual force to promote the local optimization, while EPSO directly uses random arrangement of the global mutation.

As shown in Fig. 8, the total moving distance \(Sum\_dis\) of MVFA is largest. Other algorithms are always kept at 350 or less. When Pr=1, the \(Sum\_dis\) of EPSO is 305.9710. Under the premise that the \(Sum_dis\) difference of particle swarm-based algorithms is small. So, the smaller the value of \(Std\_dis\), the more balance of the moving energy consumption, and the coverage holes are less likely to occur.

Fig. 9.
figure 9

The influence of the proportion of mobile nodes on RD

Full size image

Performance Optimization Comparison. In this paper, the index RD is used to compare the coverage efficiency of the redeployment scheme, which is the ratio of the coverage rate to the average moving distance, shown in Eq. (14).

$$\begin{aligned} RD=\frac{Cov}{Sum\_dis/(NM\times Pr)} \end{aligned}$$
(14)

Under the premise that other conditions remain unchanged, the coverage efficiency RD will increase as the proportion of mobile nodes Pr increases, but the RD change trend of different algorithms is different. As shown in Fig. 9, MTPSO has the best coverage efficiency when \(Pr<0.8\). However, as Pr increases in the later stage, the algorithm advantage will gradually decrease.

Figure 10 shows the fitness value changes of algorithms with the number of iterations increase, when \(Pr = 0.8\). We can find that in different initial deployments, MTPSO both have largest fitness and convergence speed. Although the initial value of fitness under Gaussian deployment is lower, after Maxiter iterations of optimization, the final fitness values are basically same. This also indirectly explains why the RD values of the four algorithms, under the Gaussian initial deployment are all smaller than that in uniform initial deployment. In addition, MVFA’s fitness appears decline in Uniform, because it has no fitness protection mechanism. With the increase of iteration, coverage rate tends to increase, but its value of movement deviation has a greater influence.

Fig. 10.
figure 10

The changes in fitness with the number of iterations

Full size image

We calculate the performance improvement rate Imp of MTPSO compared with OPSO, EPSO and MVFA, as shown in Eq. (15). It is demonstrated that MTPSO has a significant improvement on algorithms, as shown in Table 4. The experiments demonstrate its effectiveness for hybrid WSN’s multi-objective coverage optimization.

$$\begin{aligned} \begin{aligned} Imp_{(other,obj)}= \left\{ \begin{array}{lr} \frac{value_{other,obj}-value_{(ours,obj)}}{value_{(other,obj)}}\quad obj=Std\_dis\\ \frac{value_{ours,obj}-value_{(other,obj)}}{value_{(other,obj)}}\,~obj=Cov||Fitness \end{array} \right. \end{aligned} \end{aligned}$$
(15)
Table 4. The performance improvement rate of this algorithm compared with other algorithms
Full size table

6 Summary

In this paper, the redeployment problem based on hybrid WSN is described as a multi-objective optimization problem, and a two-stage coverage optimization algorithm is proposed to reduce it, which improves the area coverage rate and reduce the moving energy consumption deviation of nodes. Meanwhile, in order to reduce the problem that PSO is easy to fall into the local optimum and promote the convergence speed, MTPSO utilizes the nonlinear inertia weight as shown in Eq. (10) to balance the global and local search capabilities and obtain better candidate target positions. Then it introduces the virtual force mechanism to adjust the relative position among nodes. It can be found from Table 4 that compared with OPSO, EPSO and MVFA algorithms, it performs better in most cases, which proves its effectiveness for solving multi-objective redeployment coverage problem in hybrid WSN. In the future, we plan to take other optimization targets into consideration and analyze the hybrid WSN redeployment coverage problem with obstacles and hot spots, in order to optimize redeployment performance based on the above scenarios.