Dynamic Deployment for Hybrid Sensor Networks Based on Potential Field-Directed Particle Swarm Optimization

Abstract

For a hybrid sensor network, the effective coverage rate can be optimized by adjusting the location of the mobile nodes. For many deployments by APF (artificial potential field), due to the common problem of barrier effect, it is difficult for mobile nodes to diffuse by the weaker attraction when the nodes initially distribute densely in some places. The proposed deployment algorithm PFPSO (Potential Field-Directed Particle Swarm Optimization) can overcome this problem and guide the mobile nodes to the optimal positions. Normally the requirement is different for the effective coverage rate between the hotspot area and the ordinary area. On the basis of PFPSO, NPFPSO (Nonuniform PFPSO) algorithm was also proposed to implement nonuniform coverage according to the importance degree of the monitoring area. Simulation result illustrates that PFPSO algorithm can effectively improve the effective coverage rate of the network, and NPFPSO algorithm can obtain a balanced result of effective coverage rate for both hotspot area and ordinary area.

1. Introduction

The wireless sensor network becomes a research hotspot because of its great application value in the military and environmental monitoring. In most applications, manual deployment is nearly impossible because it is hard for human to approach the target field. In traditional deployment strategies, a plenty of fixed nodes including many superfluous nodes are dropped dispersedly on the target area by airplane to guarantee the effective coverage rate; these nodes can be used for targets monitoring and events tracing. In most cases these redundant nodes are involved in the communication of the whole tasks, and it can guarantee the service completed. Apparently this deployment manner will generate a lot of redundant nodes to guarantee effective coverage rate, and it is not an optimal way to complete the tasks. Although sometimes this manner can enhance the service quality of the network, it causes a lot of waste of devices and leads to conflict of communication, energy waste, and shortening network lifetime. As we know, the network with fixed sensor nodes cannot repair the coverage of network by itself due to its poor environmental adaptability. The mobile sensor networks only composed of mobile nodes can increase the coverage rate and improve network service quality by guiding the nodes moving. But, unfortunately, mobile node is a bit too expensive to be suitable for large-scale deployment. The hybrid sensor networks consist of both fixed nodes and mobile nodes, and the mobile nodes can repair the coverage holes where the fixed nodes cannot cover them by adjusting the positions of mobile nodes. It can achieve a better balance between the economy and network service quality.

For wireless sensor networks, a reasonable deployment can save more time and money to set up a network and quickly cover the target area. It can extend the network lifetime by coordination control and adapt to the change of network topology. The network's coverage rate directly affects the accuracy and comprehensiveness of the monitoring result. Deployment optimization problem of hybrid sensor network has been proved to be an NP-hard problem [1]. The deployment for hybrid sensor networks is more complex than the pure mobile sensor networks due to the existence of fixed nodes. Considering the characteristics of the hybrid sensor networks, we proposed the PFPSO (Potential Field-Directed Particle Swarm Optimization) algorithm to optimize the deployment when mobile nodes distribute densely in some places. It can overcome the common defect of APF approach, enhance the convergence speed, and improve the effective coverage rate.

In more realistic environments, such as detecting coastal water quality in drain outlet or harbor areas and searching and rescuing in some sea areas, high surveillance accuracy is required for these hotspot regions and low accuracy for less focal regions. The region which is more important and is with higher event occurrence probability can be regarded as hotspot region. Therefore, according to the importance of the target area, we proposed the NPFPSO (Nonuniform PFPSO) algorithm for nonuniform coverage by modifying the fitness function of PFPSO and velocity components of APF. It can improve the detection probability and effective coverage rate of hotspot areas and get a balanced result of effective coverage rate for both hotspot area and ordinary area.

The rest of this paper is structured as follows: Section 2 introduces some related research work of deployment issues of WSN. The generalized problem of uniform coverage and nonuniform coverage is stated in Section 3. PFPSO and NPFPSO deployment algorithms are stated in detail in Sections 4 and 5. PFPSO performance evaluation and the virtual force acceleration parameter $c_3$ of this algorithm are discussed in Section 6. A set of Pareto solutions in two different situations used to evaluate NPFPSO is shown in Section 7. Finally, Section 8 concludes this paper.

2. Related Works

2.1. Uniform Coverage

There are many deployment strategies in the mobile sensor networks, which can be divided into virtual force, swarm intelligence algorithms, and computational geometry. However, in these common strategies, there is less attention on hybrid sensor networks, and many of the algorithms applied in mobile networks are not applicable for hybrid sensor networks.

Zou and Chakrabarty [2] proposed a Virtual Force Algorithm (VFA) which assumes that repulsion and attraction exist among the sensor nodes. When the distance between two nodes is less than the threshold $d_{\mathrm{t}\mathrm{h}}$ , the nodes will repel each other outward to reduce the redundant coverage area. On the contrary, when the distance between two nodes is greater than the threshold $d_{\mathrm{t}\mathrm{h}}$ , the nodes will aggregate to repair coverage gaps by attractive force. However, the things will be deteriorated by using VFA in hybrid sensor networks. In this case, fixed nodes and mobile nodes have consistency on the coverage effect, and fixed nodes will also have virtual force on mobile nodes, so the mobile nodes are often limited in the region surrounded by fixed nodes to be difficult to diffuse. In addition, many parameters in VFA which have great impact on optimization result of network are all needed to be set up by experiences.

Huang [3] proposed a self-deployment method named as Ion-6. The mobile nodes are modeled as ions which are linked by ionic bonds. The mobile nodes achieve even distribution by forming a regular hexagonal topology. Wang et al. used Voronoi diagrams to detect coverage holes and proposed three protocols: VEC,VOR, and Minimax to control the movement of mobile nodes [4]. Because all these methods do not consider the influence of fixed nodes, these geometry-based deployment strategies cannot be applied in hybrid networks. Wang et al. [1] proposed the bidding protocol based on Voronoi diagram and greedy algorithm which can be used in hybrid sensor network. In this algorithm, the coverage holes will be detected by Voronoi diagram, and then the surrounding mobile nodes will be bidden. Mobile nodes with the highest bidding will be chosen to move to the target point and repair the coverage holes. In this process, mobile nodes can get rid of the constraint from fixed nodes. But obtaining Voronoi diagram needs the global location information of all other nodes in the network. Moreover, it is not flexible enough to find the target position of mobile nodes.

Wu et al. [5] used PSO in ad hoc network deployment optimization to improve network coverage rate. However, the convergence speed of coverage rate goes up slowly due to the velocity of particles in PSO updating randomly, and the computational complexity will rise exponentially as the number of mobile nodes increases. In order to improve the convergence speed and reduce the computational complexity of the algorithm, Wang et al. proposed parallel PSO (PPSO) algorithm [6] and virtual force directed PSO optimization (VFPSO) algorithm [7], and CVFPSO [8]. The algorithms can perform global searching by PSO to overcome the barrier effect of fixed nodes and perform particle acceleration by using the virtual force between the nodes. The VFPSO and CVFPSO algorithms based on virtual force all need to set up the threshold distance $d_{\mathrm{t}\mathrm{h}}$ , attraction coefficient $w_a$ , and the repulsion coefficient $w_r$ , which can adjust the density of nodes indirectly. The adjusting parameters are too complicated to be implemented in practice. Moreover, they cannot directly reflect the detection probability of every point in the monitoring area. So these algorithms can only be used for solving problems of uniform coverage.

2.2. Nonuniform Coverage

When we consider the importance of monitoring area and the factors of event probability of occurrence for nonuniform coverage, these algorithms above are not applicable for the problems. Currently there are few researches on nonuniform coverage. Nonuniform coverage solutions could be divided into two categories, the first achieves different detection probability for the points in the region, and the second makes the node density consistent with the event probability of occurrence in the target area.

Zou and Chakrabarty [9] proposed the Max-Avg-Cov algorithm to maximize the monitoring points of average coverage and proposed the Max-Min-Cov algorithm to maximize the monitoring points of minimum monitoring probability based on the probabilistic detection model of sensor. Aitsaadi et al. [10] proposed PFDA algorithm and MODA algorithm based on artificial potential field method, which combines artificial potential field method and Tabu search algorithm to perform complete coverage for the target area. However, the nodes deployment strategies above in initialization stage need to be deployed manually, so it is not applicable for the sensor networks with random deployment [11]. The deployment goals of these algorithms above are to have the points in monitoring area achieve the expected measuring probability to meet the coverage requirements.

Koutsougeras et al. [12] used SOM (Self-Organizing Maps) method to distribute sensors for events coverage by utilizing the attraction from events to nodes and the phenomenon of nodes trending to move to the area with high density of events. Xia et al. [13] defined the conception of entropy to evaluate the balance of coverage and effective coverage of events and proposed a fish swarm inspired underwater sensor deployment algorithm: FSSD. He considered the crowed factor of the fish swarm and simulated the behavior of fish swarm. The method can drive the sensors to cover almost all the events and make the density of sensors match the density of the events. All the algorithms above adopt event-driven coverage model and let nodes cover events to optimize detection quality as far as possible. But they do not consider the network connectivity problems, and the events density cannot always correctly express the difference between hotspot area and the ordinary area in practice.

3. Concepts Statement and Precondition Assumption

3.1. Hybrid Sensor Network

Hybrid network is a network which is composed of fixed nodes and mobile nodes. At the beginning of deployment, all nodes are deployed in the region randomly, the fixed nodes will be fixed at a position and never move again, and on the contrary the mobile nodes could even move on. Compared with mobile network, the hybrid network could save more energy efficiently. Compared with fixed network, the hybrid network could save more resource of devices and has more flexibility to adapt to different environment. So it has more significance to be used in reality. But, sometimes, when we optimize hybrid networks by moving mobile nodes with some potential field algorithm (such as APF), it will face the problem of barrier effect which will weaken the effectiveness of the optimization.

3.2. Sensor Detection Model

$S_{\mathrm{o}\mathrm{v}}$ represents the set of sensor nodes deployed on the target area A, and suppose the sensors have the same detection radius r. Considering a sensor node $s_i$ deployed at point $(x_i,y_i)$ , for point p   $(x_p,y_p)$ on A, the Euclidean distance between $s_i$ and p can be denoted as $d\left(s_i,p\right)=\sqrt{{(x_i-x_p)}^2+{(y_i-y_p)}^2}$ . In the binary detection model, if the target point p locates in detection radius of sensor $s_i$ , point p will be detected with probability 1 by sensor $s_i$ . Otherwise, the detection probability $c_p\left(s_i\right)$ will be equal to 0, which means point p cannot be detected by sensor $s_i$ . Its analytical model can be expressed as the following formula:

$$\begin{array}{cc}& c_p\left(s_i\right)=\left\{\begin{array}{cc}\mathrm{1}\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}d\left(s_i,p\right)\le r\hfill \\ \mathrm{0}\hfill & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}.\hfill \end{array}\right.\end{array}$$

(1)

In practical application, due to the terrain, obstacles, and noises, the binary model will not be applicable to describe the situation. In fact, the perception model of sensor nodes is illustrated as a certain probability distribution model. The monitoring probability will decrease with the distance $d\left(s_i,p\right)$ elongating. Considering the factor of electromagnetism and white noises in real situation, the detection probability $c_p\left(s_i\right)$ of sensor $s_i$ on point p can be presented as the following formula [14]:

$$\begin{array}{cc}& c_p\left(s_i\right)=\left\{\begin{array}{cc}\mathrm{1}\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}d\left(s_i,p\right)\le r-r_e\hfill \\ e^{\left(-{\alpha }_{\mathrm{1}}{\lambda }_{\mathrm{1}}^{{\beta }_{\mathrm{1}}}/{\lambda }_{\mathrm{2}}^{{\beta }_{\mathrm{2}}}+{\alpha }_{\mathrm{2}}\right)}\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}r-r_e<d\left(s_i,p\right)\le r+r_e\hfill \\ \mathrm{0}\hfill & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r},\hfill \end{array}\right.\end{array}$$

(2)

where $r_e\hspace{0.17em}\hspace{0.17em}(0<r_e<r)$ is the parameter of detection reliability related to the characters of sensor nodes, ${\alpha }_1$ , ${\alpha }_2$ , ${\beta }_1$ , and ${\beta }_2$ are the parameters related with detection probability of sensors, and ${\lambda }_1$ and ${\lambda }_2$ are the input parameters, and they can be defined as the following formula:

$$\begin{array}{cc}& {\lambda }_{\mathrm{1}}=r_e-r+d\left(s_i,p\right),\\ {\lambda }_{\mathrm{2}}=r_e+r-d\left(s_i,p\right).\end{array}$$

(3)

Figure 1 illustrates the curve of detection probability of sensor nodes changing with the distances.

Figure 1

The curve of detection probability of sensor nodes changing with distance.

3.3. Uniform Coverage Problem in Hybrid Sensor Networks

Suppose that all the nodes are randomly scattered in a two-dimensional monitoring area A while initializing. If point p is within the probabilistic perception of the sensor $s_i$ , the perception range can be expressed as follows: $d\left(s_i,p\right)\le (r+r_e)$ , and the sensor $s_i$ is the neighbor sensor of point p. The detection probability of point p is the union detection probability of all its neighbor sensors within the monitoring area. Considering a grid point p lying in the overlap region sensed by a set of neighbor sensors $S_{\mathrm{n}\mathrm{e}}$ , the detection probability of the point which can be effectively detected by at least one sensor node is denoted as $c_p\left(S_{\mathrm{n}\mathrm{e}}\right)$ . It can be calculated by the following formula:

$$\begin{array}{cc}& c_p\left(S_{\mathrm{n}\mathrm{e}}\right)=\mathrm{1}-{\displaystyle \prod }_{s_i\in S_{\mathrm{n}\mathrm{e}}}\left(\mathrm{1}-c_p\left(s_i\right)\right),\end{array}$$

(4)

where $S_{\mathrm{n}\mathrm{e}}$ is the set of neighbor sensors of point p and $c_p\left(s_i\right)$ is the detection probability of sensor $s_i$ at point p. Suppose $c_{\mathrm{t}\mathrm{h}}$ is the threshold of predefined effective detection probability; the condition that point p can be effectively covered can be expressed as the following formula:

$$\begin{array}{cc}& c_p\left(S_{\mathrm{n}\mathrm{e}}\right)\ge c_{\mathrm{t}\mathrm{h}}.\end{array}$$

(5)

The deployment of a sensor network should both meet the condition of coverage and meet the condition of connectivity. When the node communication radius is more than twice the radius of perception, the coverage problem should only be considered for a sensor network, since this condition can guarantee the connectivity of the network [15–17]. Therefore, in this paper, we assume that there is a sink node which can collect location information of all nodes in the target area, and the communication radius of ordinary nodes meets the following condition: $R_c\ge 2(r+r_e)$ .

To summarize, the uniform deployment of hybrid sensor networks can be described as follows: m fixed nodes and n mobile nodes are scattered randomly in the target area A. We can adjust the position of mobile nodes to maximize the effective coverage of target area. In particular, when $m=0$ , the hybrid sensor network coverage problem is equivalent to the coverage problems of mobile sensor networks.

3.4. Nonuniform Coverage Problem of Hybrid Networks

According to the monitoring requirements for different regions in target environment, sometimes we need to perform the nonuniform coverage in target area. It can pay more attention to some hotspot areas with more nodes and simplify sensor resources for some ordinary areas. Suppose A represents the 2-D target area, $A_{\mathrm{h}\mathrm{o}\mathrm{t}}$ represents the hotspot area in A, and $A_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}$ represents ordinary surveillance area. The relationship of $A_{\mathrm{h}\mathrm{o}\mathrm{t}}$ and $A_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}$ meets the following formula:

$$\begin{array}{cc}& A_{\mathrm{h}\mathrm{o}\mathrm{t}}\cup A_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}=A\\ A_{\mathrm{h}\mathrm{o}\mathrm{t}}\cap A_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}=⌀.\end{array}$$

(6)

$p\_\mathrm{h}\mathrm{o}\mathrm{t}$ and $p\_\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}$ represent the monitoring points in $A_{\mathrm{h}\mathrm{o}\mathrm{t}}$ and $A_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}$ , respectively, and these areas can be covered effectively if the condition meets the following formula:

$$\begin{array}{cc}& c_{p\_\mathrm{h}\mathrm{o}\mathrm{t}}\left(S_{\mathrm{o}\mathrm{v}}\right)\ge c_{\mathrm{t}\mathrm{h}\_\mathrm{h}\mathrm{o}\mathrm{t}}\\ c_{p\_\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}\left(S_{\mathrm{o}\mathrm{v}}\right)\ge c_{\mathrm{t}\mathrm{h}\_\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}},\end{array}$$

(7)

where $c_{\mathrm{t}\mathrm{h}\_\mathrm{h}\mathrm{o}\mathrm{t}}$ and $c_{\mathrm{t}\mathrm{h}\_\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}$ are the predefined effective detection thresholds of coverage probability for $A_{\mathrm{h}\mathrm{o}\mathrm{t}}$ and $A_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}$ according to their important levels, normally $c_{\mathrm{t}\mathrm{h}\_\mathrm{h}\mathrm{o}\mathrm{t}}>c_{\mathrm{t}\mathrm{h}\_\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}$ .

Thus the nonuniform deployment of hybrid sensor networks can be described as follows: m fixed nodes and n mobile nodes are scattered randomly in the target area A. We can adjust the positions of mobile nodes to maximize the effective coverage rate of hotspot region and ordinary surveillance region. In particular, when $A_{\mathrm{h}\mathrm{o}\mathrm{t}}=⌀$ , the nonuniform coverage problem is equivalent to uniform coverage problem.

4. PFPSO Algorithm for Uniform Coverage

For PSO algorithm, the initial position and velocity of the particles are generated randomly. It cannot guide the particles moving effectively only depending on these parameters: the particle velocity, the individual best position, and the global colony best position. On the other hand, by APF algorithm, the mobile nodes can bypass the fixed nodes and repair the coverage holes by the attractive force generated by uncovered grid points. However, sometimes it will meet the problem of barrier effect: when the fixed nodes distribute in some region with high density, the coverage probability will be high in their neighboring regions, and the nearby mobile nodes will be difficult to spread due to the diminishing attraction by the coverage hole. That is to say we cannot obtain an ideal optimal result only depending on any single one of these two algorithms.

The proposed PFPSO algorithm integrates their advantages of artificial potential field and particle swarm optimization organically. It can own two functions: (1) With the direction of the virtual force, the mobile nodes could move towards the better position to heal the coverage holes. (2) Implementing global optimization to make the mobile nodes overcome the barrier effect from the fixed nodes.

4.1. Some Basic Concepts in PFPSO Algorithm

The virtual force derives from artificial potential field, which was originally introduced to robot path planning to avoid obstacles and find the optimal path [10, 18, 19]. Here every node can move under the resultant force by the attractive force from targets and the repulsive force from obstacles. This kind of resultant force $\overrightarrow{F}$ can be given by the following formula:

$$\begin{array}{cc}& \overrightarrow{F}=-\overrightarrow{\nabla }U=\left(\begin{array}{c}\frac{-\partial U}{\partial x_r}\\ \frac{-\partial U}{\partial y_r}\end{array}\right),\end{array}$$

(8)

where U is the potential field function and $(x_r,y_r)$ is the coordinates of the robot.

The deployment optimization problem of hybrid sensor network can be treated as healing coverage holes. The coverage hole will produce an attractive force to the mobile modes. So, in this paper, we assume the point whose detection probability does not meet the condition of detection will generate an attractive potential field to the mobile nodes. The potential field function can be given by the following formula [10]:

$$\begin{array}{cc}& U^a\left(s\right)={\displaystyle \sum }_{p\in A}\left(c_{\mathrm{t}\mathrm{h}}-c_{p/s}\right)·{\mathrm{1}}_{\mathrm{i}\mathrm{f}\left\{c_{p/s}<c_{\mathrm{t}\mathrm{h}}\right\}},\end{array}$$

(9)

where A is the monitoring target area and $c_{p/s}$ is the union detection probability at point p when a sensor is deployed at point s [10]:

$$\begin{array}{cc}& c_{p/s}=\mathrm{1}-\left(\mathrm{1}-c_p\left(s\right)\right){\displaystyle \prod }_{s^{\prime }\in S_{\mathrm{o}\mathrm{v}}\setminus \left\{s\right\}}\left(\mathrm{1}-c_p\left(s^{\prime }\right)\right).\end{array}$$

(10)

The virtual force ${\overrightarrow{F}}_s^a$ of a sensor node received can be deduced as the following formula:

$$\begin{array}{cc}& {\overrightarrow{F}}_s^a=-\overrightarrow{\nabla }{U}^a\left(s\right)=\left(\begin{array}{c}{F}_x^a\\ F_y^a\end{array}\right)=\left(\begin{array}{c}\frac{-\partial U^a\left(s\right)}{\partial x_s}\\ \frac{-\partial U^a\left(s\right)}{\partial y_s}\end{array}\right),\end{array}$$

(11)

where $F_x^a$ and $F_y^a$ represent the acting forces from the x-axis and y-axis directions, respectively. We can put the variables of formulas (2), (9), and (10) into (11) and get the results as formula (12) after differentiation. Consider

$$\begin{array}{cc}& \frac{\partial U^a}{\partial x_s}={\displaystyle \sum }_{p\in A_s}\left[\left(x_s-x_p\right)\left(\frac{{\alpha }_{\mathrm{1}}{\beta }_{\mathrm{1}}{\lambda }_{\mathrm{1}}^{{\beta }_{\mathrm{1}}-\mathrm{1}}}{{\lambda }_{\mathrm{2}}^{{\beta }_{\mathrm{2}}}}+\frac{{\alpha }_{\mathrm{1}}{\beta }_{\mathrm{2}}{\lambda }_{\mathrm{1}}^{{\beta }_{\mathrm{1}}}}{{\lambda }_{\mathrm{2}}^{{\beta }_{\mathrm{2}}+\mathrm{1}}}\right)e^{\left(-{\alpha }_{\mathrm{1}}{\lambda }_{\mathrm{1}}^{{\beta }_{\mathrm{1}}}/{\lambda }_{\mathrm{2}}^{{\beta }_{\mathrm{2}}}+{\alpha }_{\mathrm{2}}\right)}·{\displaystyle \prod }_{s^{\prime }\in S_{\mathrm{o}\mathrm{v}}\setminus \left\{s\right\}}\left(\mathrm{1}-c_p\left(s^{\prime }\right)\right)\right]\\ \frac{\partial U^a}{\partial y_s}={\displaystyle \sum }_{p\in A_s}\left[\left(y_s-y_p\right)\left(\frac{{\alpha }_{\mathrm{1}}{\beta }_{\mathrm{1}}{\lambda }_{\mathrm{1}}^{{\beta }_{\mathrm{1}}-\mathrm{1}}}{{\lambda }_{\mathrm{2}}^{{\beta }_{\mathrm{2}}}}+\frac{{\alpha }_{\mathrm{1}}{\beta }_{\mathrm{2}}{\lambda }_{\mathrm{1}}^{{\beta }_{\mathrm{1}}}}{{\lambda }_{\mathrm{2}}^{{\beta }_{\mathrm{2}}+\mathrm{1}}}\right)e^{\left(-{\alpha }_{\mathrm{1}}{\lambda }_{\mathrm{1}}^{{\beta }_{\mathrm{1}}}/{\lambda }_{\mathrm{2}}^{{\beta }_{\mathrm{2}}}+{\alpha }_{\mathrm{2}}\right)}·{\displaystyle \prod }_{s^{\prime }\in S_{\mathrm{o}\mathrm{v}}\setminus \left\{s\right\}}\left(\mathrm{1}-c_p\left(s^{\prime }\right)\right)\right],\end{array}$$

(12)

where $A_s$ is the set of the points which do not meet the detection probability in the sensor's detection range from ${r-r}_e$ to ${r+r}_e$ :

$$\begin{array}{cc}& A_s=\left\{\forall p\in A\hspace{0.17em}|\hspace{0.17em}{c}_p\left(S_{\mathrm{o}\mathrm{v}}\right)<c_{\mathrm{t}\mathrm{h}}\text{,\hspace{0.17em}\hspace{0.17em}}\left|d\left(s_i,p\right)-r\right|\le r_e\right\}.\end{array}$$

(13)

Then the sensor nodes will update the original location $(x_{\mathrm{o}\mathrm{l}\mathrm{d}},y_{\mathrm{o}\mathrm{l}\mathrm{d}})$ to new location $(x_{\mathrm{n}\mathrm{e}\mathrm{w}},y_{\mathrm{n}\mathrm{e}\mathrm{w}})$ according to the orientation and magnitude of the total virtual force ${\overrightarrow{F}}_s^a$ , and it can be calculated by the following formula:

$$\begin{array}{cc}& x_{\mathrm{n}\mathrm{e}\mathrm{w}}=\left\{\begin{array}{cc}{x}_{\mathrm{o}\mathrm{l}\mathrm{d}},\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}\left|F_s^a\right|=\mathrm{0}\hfill \\ x_{\mathrm{o}\mathrm{l}\mathrm{d}}+\frac{F_x^a}{\left|{\overrightarrow{F}}_s^a\right|}\times MaxStep\times e^{-\mathrm{1}/\left|{\overrightarrow{F}}_s^a\right|},\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}\left|F_s^a\right|\ne \mathrm{0}\hfill \end{array}\right.\\ y_{\mathrm{n}\mathrm{e}\mathrm{w}}=\left\{\begin{array}{cc}{y}_{\mathrm{o}\mathrm{l}\mathrm{d}},\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}\left|F_s^a\right|=\mathrm{0}\hfill \\ y_{\mathrm{o}\mathrm{l}\mathrm{d}}+\frac{F_y^a}{\left|{\overrightarrow{F}}_s^a\right|}\times MaxStep\times e^{-\mathrm{1}/\left|{\overrightarrow{F}}_s^a\right|},\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}\left|F_s^a\right|\ne \mathrm{0},\hfill \end{array}\right.\end{array}$$

(14)

where $MaxStep$ is the predefined maximum step size of mobile nodes, the values of $F_x^a$ , $F_y^a$ can be got by formulas (11) and (12).

Particle swarm optimization is a stochastic global optimization algorithm for seeking the solution by imitating the flocks of bird [20, 21]. Due to fast convergence and less parameters for setting up, it is widely used in solving problems of multidimensional space. Suppose $X_i=\left(x_{i1},x_{i2},\dots ,x_{in}\right)$ is the current position vector of particle i, and $V_i=\left(v_{i1},v_{i2},\dots ,v_{in}\right)$ is the current velocity vector of particle i. $f\left(X\right)$ is the fitness function used to evaluate whether the position of particle is good or not. For the minimized objective function $f\left(X\right)$ , the optimal position $P_i=\left(p_{i1},p_{i2},\dots ,p_{in}\right)$ of particle i can be obtained by the following formula:

$$\begin{array}{cc}& P_i\left(t+\mathrm{1}\right)=\left\{\begin{array}{cc}{P}_i\left(t\right)\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}f\left(X_i\left(t+\mathrm{1}\right)\right)\ge f\left(P_i\left(t\right)\right)\hfill \\ X_i\left(t+\mathrm{1}\right)\hfill & \mathrm{i}\mathrm{f}\hspace{0.17em}\hspace{0.17em}f\left(X_i\left(t+\mathrm{1}\right)\right)<f\left(P_i\left(t\right)\right).\hfill \end{array}\right.\end{array}$$

(15)

The best position of the colony $P_g\left(t\right)=\min \left\{f\left(P_0\left(t\right)\right),f\left(P_i\left(t\right)\right),\dots ,f\left(P_m\left(t\right)\right)\right\}$ . The velocity and position of every generation particle can be updated as formulas (16) and (17), respectively. Consider

$$\begin{array}{cc}& v_{ij}\left(t+\mathrm{1}\right)=w\left(t\right)v_{ij}\left(t\right)+c_{\mathrm{1}}{r}_{\mathrm{1}j}\left(t\right)\left(p_{ij}\left(t\right)-x_{ij}\left(t\right)\right)+c_{\mathrm{2}}{r}_{\mathrm{2}j}\left(t\right)\left(p_{gj}\left(t\right)-x_{ij}\left(t\right)\right)\end{array}$$

(16)

$$\begin{array}{cc}& x_{ij}\left(t+\mathrm{1}\right)=x_{ij}\left(t\right)+v_{ij}\left(t+\mathrm{1}\right),\end{array}$$

(17)

where $c_1$ and  $c_2$ are the weighting factors of local optimization and global optimization, respectively. They can be used to adjust the evolutionary step of local optimization and global optimization of the particle. $r_{1j}$ and $r_{2j}$ are the independent random number in the range of $[\mathrm{0,1}]$ . Subscript i is corresponding to the number i particle, and the subscript j is corresponding to the j dimension of the particle. w is the impact inertial factor indicating the influence of the past value to current value, and usually it can take a value between 0.4 and 0.9. It will gradually decrease with the iteration updating.

4.2. The Principle of PFPSO

In order to enhance the effectiveness of coverage of the network, a kind of central scheduling deployment strategy was proposed, which integrates APF and PSO algorithm and overcomes the disadvantages of the two algorithms in hybrid networks deployment. Suppose a sink node in the target area can collect the information of coordinates for all the nodes; we can perform PFPSO algorithm and inform mobile nodes to move to the designated location directly according to the calculation result. This can reduce the moving distances of the nodes in the process of optimization.

Assuming n mobile nodes and m fixed nodes are randomly deployed in the target area. The position coordinates of n mobile nodes can be regarded as one solution of PFPSO algorithm. The dimension of the searching space $N=2n$ and the position vector of particle i can be expressed as $X_i=\left(x_{i1},x_{i2},{{\dots ,x}_{in},y}_{i1},y_{i2},\dots ,y_{in}\right)$ , where $x_{ij}$ and $y_{ij}$ are the coordinates of mobile node j. The effective coverage of monitoring area can be regarded as the fitness function, and it is expressed as the following formula:

$$\begin{array}{cc}& f\left(X_i\left(t\right)\right)=\frac{\left\{\forall p\in A\hspace{0.17em}|\hspace{0.17em}{c}_p\left(S_{\mathrm{o}\mathrm{v}}\right)\ge c_{\mathrm{t}\mathrm{h}}\right\}}{A}.\end{array}$$

(18)

For PFPSO algorithm, the velocity of each particle is updated according to not only the historical optimal solutions of local and global positions, but also the attractive force exerting on mobile nodes. The influence of attractive force is reflected in the additional last item of formula (19). So the traditional velocity updating formula of PSO has been improved in PFPSO:

$$\begin{array}{cc}& v_{ij}\left(t+\mathrm{1}\right)=w\left(t\right)v_{ij}\left(t\right)+c_{\mathrm{1}}{r}_{\mathrm{1}j}\left(t\right)\left(p_{ij}\left(t\right)-x_{ij}\left(t\right)\right)+c_{\mathrm{2}}{r}_{\mathrm{2}j}\left(t\right)\left(p_{gj}\left(t\right)-x_{ij}\left(t\right)\right)+c_{\mathrm{3}}{r}_{\mathrm{3}j}\left(t\right)g_{ij}\left(t\right),\end{array}$$

(19)

where $c_3$ is the acceleration factor of attractive force and $r_{\mathrm{3}j}$ is also an independent random number in the range of $[\mathrm{0,1}]$ just like $r_{1j}$ and $r_{2j}$ . $g_{ij}$ is the distance effected by the potential field force derived from jth element in the position vector of ith particle, which can be expressed by the following formula:

$$\begin{array}{cc}& g_{ij}\left(t\right)=\left\{\begin{array}{cc}\frac{F_x^{\left(i,j\right)}}{F_{xy}^{\left(i,j\right)}}\times MaxStep\times e^{\mathrm{1}/F_{xy}^{\left(i,j\right)}},\phantom{\frac{F_x^{\left(i,j\right)}}{F_{xy\mathrm{1}/F^{\left(i,j-n\right)}}^{\left(i,j\right)}}}\hfill & j=\mathrm{1,2},\dots ,n\hfill \\ \frac{F_y^{\left(i,j-n\right)}}{F_{xy}^{\left(i,j-n\right)}}\times MaxStep\times e^{\mathrm{1}/F_{xy}^{\left(i,j-n\right)}},\hfill & j=n+\mathrm{1},n+\mathrm{2},\dots ,\mathrm{2}n.\hfill \end{array}\right.\end{array}$$

(20)

The PFPSO algorithm's flow chart is illustrated as Figure 2.

Figure 2

PFPSO algorithm's flow chart.

The pseudo code of PFPSO is as shown in Algorithm 1.

Algorithm 1: PFPSO.

Input:

Mobile nodes original coordinates $(X_m,Y_m)$

Mobile nodes number n

Particle number M

Detection parameters of sensor $r,r_e$

The target field A

Effective detection probability threshold $c_{\text{th}}$

Maximal iteration of PFPSO MaxIter

Output:

The new coordinates of mobile nodes $pgbest$

The effective coverage of the target field $coverage$

(1)    $x(\mathrm{0})\leftarrow (X_m,Y_m)$

(2)   for   $i\leftarrow$ 1 to M  do

(3)     $v_i(\mathrm{0})\leftarrow$ Randomly initializing the velocity of every particle

(4)     $x_i(\mathrm{1})\leftarrow x(\mathrm{0})+v_i(\mathrm{0})$

(5)    Calculate the $f(x_i(\mathrm{1}))$ of particle i

(6)   end for

(7)    $pgbest\leftarrow \max \left\{f\left(x_{\mathrm{1}}(\mathrm{1})\right),f\left(x_{\mathrm{2}}(\mathrm{1})\right),\dots ,f\left(x_M(\mathrm{1})\right)\right\}$

(8)    $coverage\leftarrow f(pgbest)$

(9)   for   $t\leftarrow$ 2 to MaxIter  do

(10)  for   $i\leftarrow$ 1 to M  do

(11)   for   $j\leftarrow$ 1 to n  do

(12)     $A_s\leftarrow \left\{\forall p\in A\hspace{0.17em}|\hspace{0.17em}{c}_p<c_{\text{th}}\text{\hspace{0.17em}\hspace{0.17em}and\hspace{0.17em}\hspace{0.17em}}\left|d(s_j,p)-r\right|\le r_e\right\}$

(13)    Calculate attractive virtual force ${\overrightarrow{F}}_s^a$

( $14$ )   end for

( $15$ )   Compute the velocity $v_i(t)$ of particle i

( $16$ )    $x_i(t)\leftarrow x_i(t-\mathrm{1})+v_i(t)$

( $17$ )   Calculate the $f\left(x_i(t)\right)$ of particle i

( $18$ )   end for

( $19$ )   $pbest\leftarrow \max \left\{f\left(x_{\mathrm{1}}(t)\right),f\left(x_{\mathrm{2}}(t)\right),\dots ,f\left(x_M(t)\right)\right\}$

(20)  if   $f(pgbest)<f(pbest)$

(21)    $pgbest\leftarrow gbest$

(22)  end if

(23)   $coverage\leftarrow f(pgbest)$

(24) end for

5. NPFPSO Algorithm for Nonuniform Coverage

Nonuniform coverage of hybrid sensor network can be regarded as a multiobjective optimization problem. Assume that $f_{\mathrm{h}\mathrm{o}\mathrm{t}}\left(X_i(t)\right)$ and $f_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}\left(X_i(t)\right)$ represent the effective coverage of the hotspot region and the ordinary region, respectively, which can be expressed as formula (21) and formula (22). Consider

$$\begin{array}{cc}& f_{\mathrm{h}\mathrm{o}\mathrm{t}}\left(X_i\left(t\right)\right)=\frac{\left\{\forall p\in A_{\mathrm{h}\mathrm{o}\mathrm{t}}\hspace{0.17em}|\hspace{0.17em}{c}_p\left(S_{\mathrm{o}\mathrm{v}}\right)\ge c_{\mathrm{t}\mathrm{h}\_\mathrm{h}\mathrm{o}\mathrm{t}}\right\}}{A_{\mathrm{h}\mathrm{o}\mathrm{t}}}\end{array}$$

(21)

$$\begin{array}{cc}& f_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}\left(X_i\left(t\right)\right)=\frac{\left\{\forall p\in A_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}\hspace{0.17em}|\hspace{0.17em}{c}_p\left(S_{\mathrm{o}\mathrm{v}}\right)\ge c_{\mathrm{t}\mathrm{h}\_\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}\right\}}{A_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}}.\end{array}$$

(22)

What the nonuniform coverage needs to do is to maximize the objective functions $f_{\mathrm{h}\mathrm{o}\mathrm{t}}\left(X_i(t)\right)$ and $f_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}\left(X_i(t)\right)$ by optimizing the mobile nodes' location. Ordinarily the number of mobile nodes is limited, so there is some conflict between the objective functions $f_{\mathrm{h}\mathrm{o}\mathrm{t}}\left(X_i(t)\right)$ and $f_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}\left(X_i(t)\right)$ , and the solution of this kind of nonuniform coverage is a group of Pareto optimal solutions [22]. In this paper, the target weighting method is adopted by the proposed NPFPSO algorithm [23]; it can integrate $f_{\mathrm{h}\mathrm{o}\mathrm{t}}\left(X_i(t)\right)$ and $f_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}\left(X_i(t)\right)$ with linear fusion, so the problem can be solved by converting into a single objective function. The fitness function of NPFPSO can be calculated as the following formula:

$$\begin{array}{cc}& f\left(X_i\left(t\right)\right)=\alpha f_{\mathrm{h}\mathrm{o}\mathrm{t}}\left(X_i\left(t\right)\right)+\left(\mathrm{1}-\alpha \right)f_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}\left(X_i\left(t\right)\right),\end{array}$$

(23)

where the weighting coefficient $\alpha \in [\mathrm{0,1}]$ and it can be used to make a balanced control for the effective coverage of the hotspot region and ordinary region.

Normally different target areas have different detection thresholds in nonuniform coverage of target environment. In order to make potential field force guide the mobile nodes moving more effectively, we improved formula (13) as the following formula:

$$\begin{array}{cc}& A_s=A_{s\_\mathrm{h}\mathrm{o}\mathrm{t}}\cup A_{s\_\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}},\end{array}$$

(24)

where $A_{s\_\mathrm{h}\mathrm{o}\mathrm{t}}$ and $A_{s\_\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{n}\mathrm{r}\mathrm{y}}$ are the set of the points whose detection probability does not meet the effective detection thresholds in the sensing range of [ ${r-r}_e,{r+r}_e$ ], and they can be expressed as the following formula:

$$\begin{array}{cc}& A_{s\_\mathrm{h}\mathrm{o}\mathrm{t}}=\left\{\forall p\in A_{\mathrm{h}\mathrm{o}\mathrm{t}}\hspace{0.17em}|\hspace{0.17em}{c}_p\left(S_{\mathrm{o}\mathrm{v}}\right)<c_{\mathrm{t}\mathrm{h}\_\mathrm{h}\mathrm{o}\mathrm{t}},\left|d\left(s_i,p\right)-r\right|\le r_e\right\}\\ A_{s\_\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}=\left\{\forall p\in A_{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}\hspace{0.17em}|\hspace{0.17em}{c}_p\left(S_{\mathrm{o}\mathrm{v}}\right)<c_{\mathrm{t}\mathrm{h}\_\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}},\left|d\left(s_i,p\right)-r\right|\le r_e\right\}.\end{array}$$

(25)

The NPFPSO algorithm's flow chart is illustrated as Figure 3.

Figure 3

NPFPSO algorithm's flow chart.

The pseudo code of NPFPSO algorithm is as shown in Algorithm 2.

Algorithm 2: NPFPSO.

Input:

Mobile nodes original coordinates $(X_m,Y_m)$

Mobile nodes number n

Particle number M

Detection parameters of sensor $r,r_e$

The important regions $A_{\text{hot}}$

The ordinary regions $A_{\text{ordinary}}$

Important effective detection probability threshold $c_{\text{th}\_\text{hot}}$

Ordinary effective detection probability threshold $c_{\text{th}\_\text{ordinary}}$

Weight coefficient α

Maximal iteration of NPFPSO MaxIter

Output:

The new coordinates of mobile nodes $pgbest$

The effective coverage of the important region $coverag{e}_{\text{hot}}$

The effective coverage of the ordinary region $coverag{e}_{\text{ordinary}}$

(1)    $x(\mathrm{0})\leftarrow (X_m,Y_m)$

(2)   for   $i\leftarrow$ 1 to M  do

(3)     $v_i(\mathrm{0})\leftarrow$ Randomly initializing the velocity of every particle

(4)     $x_i(\mathrm{1})\leftarrow x(\mathrm{0})+v_i(\mathrm{0})$

(5)    Calculate the $f\left(x_i(\mathrm{1})\right)$ of particle i

(6)   end for

(7)    $pgbest\leftarrow \max \left\{f\left(x_{\mathrm{1}}(\mathrm{1})\right),f\left(x_{\mathrm{2}}(\mathrm{1})\right),\dots ,f\left(x_M(\mathrm{1})\right)\right\}$

(8)   coverage  $\leftarrow f(pgbest)$

(9)   for   $t\leftarrow$ 2 to MaxIter  do

(10)  for   $i\leftarrow$ 1 to M  do

(11)   for   $j\leftarrow$ 1 to n  do

(12)     $A_{s\_\text{hot}}\leftarrow \left\{\forall p\in A_{\text{hot}}\hspace{0.17em}|\hspace{0.17em}{c}_p<c_{\text{th}\_\text{hot}}\text{\hspace{0.17em}\hspace{0.17em}and\hspace{0.17em}\hspace{0.17em}}\left|d(s_j,p)-r\right|\le r_e\right\}$

(13)     $A_{s\_\text{ordinary}}\leftarrow \left\{\forall p\in A_{\text{ordinary}}\hspace{0.17em}|\hspace{0.17em}{c}_p<c_{\text{th}\_\text{ordinary}}\text{\hspace{0.17em}\hspace{0.17em}and\hspace{0.17em}\hspace{0.17em}}\left|d(s_j,p)-r\right|\le r_e\right\}$

(14)    Calculate attractive virtual force ${\overrightarrow{F}}_s^a$

(15)   end for

(16)   Compute the velocity $v_i(t)$ of particle i

(17)    $x_i(t)\leftarrow x_i(t-\mathrm{1})+v_i(t)$

(18)   Compute the $f_{\text{hot}}\left(x_i(t)\right)$ and $f_{\text{ordinary}}\left(x_i(t)\right)$ of particle i

(19)    $f\left(x_i(t)\right)\leftarrow \alpha \times f_{\text{hot}}\left(x_i(t)\right)+(\mathrm{1}-\alpha )\times f_{\text{ordinary}}\left(x_i(t)\right)$

(20)   end for

(21)   $pbest\leftarrow \max \left\{f\left(x_{\mathrm{1}}(t)\right),f\left(x_{\mathrm{2}}(t)\right),\dots ,f\left(x_M(t)\right)\right\}$

(22)  if   $f(pgbest)<f(pbest)$

(23)    $pgbest\leftarrow gbest$

(24)  end if

(25)   $coverag{e}_{\text{hot}}\leftarrow f_{\text{hot}}(pgbest)$

(26)   $coverag{e}_{\text{ordinary}}\leftarrow f_{\text{ordinary}}(pgbest)$

(27) end for

6. The Simulation Testing of PFPSO and Performance Analysis

To investigate the performance of PFPSO in the deployment optimization, we simulate the algorithms in the simulation platform MATLAB2009. In this simulation, the problems of energy consumption and routings of the network are not involved. Supposing the monitoring target area is a 2-D square region with area of 200 m × 200 m, 100 ordinary nodes are scattered randomly on this square target region which are composed of m fixed nodes and n mobile nodes. In order to expediently evaluate the effective coverage of wireless sensor network, the target region is divided into 40000 grids with each area of 1 m × 1 m. We can calculate the detection probability of each grid, and the proportion of these grids which meet formula (5) is the effective coverage rate of the network. Some simulation results indicated that the absolute deviation between calculated value and the precise value of the coverage measure will be in the range of 0.1%–0.5% when the granularity (the distance between grid points) is as the scale of 0.25%–4% relative to the size of the target monitoring area [13]. The parameters of probabilistic detection model are set as ${\alpha }_1=1$ , ${\alpha }_2=0$ , ${\beta }_1=1$ , and ${\beta }_2=1.5$ . The detection radius of each node is $r=14$  m, the reliability parameter of measurement is $r_e=7$  m, and the communication radius is $R_c=2\left(r+r_e\right)=42$  m. The effective detection threshold is $c_{\mathrm{t}\mathrm{h}}=0.9$ and the maximum movement step of mobile nodes is $MaxStep=1$  m.

6.1. The Effectiveness of PFPSO Compared with Other Typical Algorithms

Suppose in some cases the mobile nodes are initially distributed in dense state, and we want to make them scatter out in the target area for an optimal coverage. For example, 60 fixed nodes are randomly deployed uniformly in the region of 200 m × 200 m 2-D area and 40 mobile nodes randomly distributed in the central square region with the area of 100 m × 100 m. The initial coverage diagram is shown as Figure 4. In this figure, the red regions represent the detection probability of 100%, the blue regions mean the detection probability does not reach the threshold, and the transitional color shows that the detection probability of the point is higher than the threshold but lower than 100%.

Figure 4

Initial coverage state for uniform coverage testing.

Figures 5(a) and 5(b) show the coverage diagram by APF algorithm with running 50 iterations and the corresponding trajectories of mobile nodes, respectively. Apparently there are more uncovered regions with blue color in Figure 5(a), and the mobile nodes are almost bounded in the central area as shown in Figure 5(b). Figure 5(b) illustrates the moving status of mobile nodes from the original position “•” to the terminal position “o,” and “∗” represents the fixed node distributed randomly. Apparently APF algorithm cannot achieve the desired optimization of coverage when mobile nodes are influenced by the barrier effect due to the smaller attractive force generated by uncovered grid points acting on the mobile nodes.

Figure 5

Simulation results of APF algorithm when mobile nodes are influenced by barrier effect.

In order to verify the effectiveness of PFPSO, suppose the local and global optimum values in PSO and the virtual force exerting on mobile nodes generate the same impact on the position optimization of mobile nodes, which is to set the acceleration factors as follows: $c_1=c_2=c_3=1$ . The maximum iterations $Maxiter$ is taken as 100 times, the number of particles is $M=20$ , and the inertia coefficient is taken as $w=0.9-0.5\times (1-t/Maxiter)$ according to experiences. In the same initial coverage state as Figure 3, the coverage result by PFPSO after 100 iterations is shown as Figure 6.

Figure 6

Simulation results of PFPSO algorithm when mobile nodes are influenced by barrier effect.

Investigating the two figures, Figures 5(a) and 6(a), we can find the coverage rate by performing PFPSO has been improved a lot comparing with APF method. We also test the pure PSO algorithm under the same initial coverage state, and the whole testing results of coverage rate for these three methods are shown in Table 1. Figure 6(b) illustrates the displacement of mobile nodes from their original position “•” to the terminal position “o” and the “∗” represents the fixed node distributed randomly. As Figure 6(b) illustrates, apparently the mobile nodes can diffuse from the original central area to all the other areas uniformly for repairing the coverage holes. Duo to adding an item of velocity component caused by virtual force in the velocity update calculating as formula (19), the velocity of the mobile nodes in PFPSO is higher than the velocity in APF and PSO algorithm. It has been advantageous to make the nodes spread rapidly, and it is more useful to overcome the barrier effect of fixed nodes encapsulated.

Table 1

Coverage comparison for these three algorithms.

Coverage rate	Initialization	PSO	APF	PFPSO
After running 50 iterations	60.17%	79.93%	80.97%	89.97%
After running 100 iterations	60.17%	79.57%	84.67%	91.03%

Figure 7 and Table 1 illustrate the raising curve of effective coverage and the final coverage rate after 100 iterations for APF, PSO, and PFPSO, respectively. In Figure 7 we can find that the two coverage curves of PSO and PFPSO rise rapidly and almost overlap in the first 10 iterations. It indicates that the mobile nodes are mainly guided by the velocity component of PSO in the preliminary stage of optimization of PFPSO. With increasing of iterations, the curve of PSO increases slowly in later period, and it is exceeded by APF at the 28th rounds of iteration. During 10 to 50 rounds of iteration, the slopes of the curve of PFPSO and APF are roughly similar which indicates that the mobile nodes are mainly guided to optimal position by the attractive force. In addition, as shown in Figure 7 and Table 1, we can find that the convergence speed of PFPSO algorithm is obviously higher than APF and PSO. So PFPSO can effectively overcome the barrier effect from the fixed nodes as using potential field method, and it can achieve a higher coverage rate for performing optimization.

Figure 7

Effective coverage curves of the three algorithms.

6.2. Discussion Regarding Parameter $c_{\mathrm{3}}$ Evaluation

For formula (19), when $c_3=0$ , PFPSO and PSO algorithm are the same, and when $c_1=c_2=0$ , PFPSO and APF algorithm are the same. So PSO and APF algorithm can be regarded as the special forms of the proposed PFPSO algorithm. The parameter $c_3$ directly controls the weight of position optimization for mobile nodes by the virtual force in the performing period, and it influences the convergence speed and searching result of PFPSO. We analyzed the movement of the mobile nodes during the algorithm execution. At the beginning, the mobile nodes are gathered in the center, and only fewer points which do not meet the detection threshold will generate attractive force to the mobile nodes. By the initial velocity generated randomly by PSO in the early stage, the mobile nodes can diffuse from the density state in the original centre position. In the middle and later periods, with the mobile nodes diffusing, the virtual force components in the velocity updating of particles become the main driving factor for mobile nodes guiding. According to the analysis above, considering the change rule of inertial coefficient w, three changing circumstances will be validated for the parameter $c_3$ . The first is the constant, and it means $c_3$ will be the same value during all the process. The second means $c_3$ will rise monotonically, and it indicates the influence of potential field force rises up gradually. The third one means $c_3$ will rise up in the first half stage and falls off in the later half stage. The three lines $l_1$ , $l_2$ , and $l_3$ represent the typical three kinds of changing circumstances of $c_3$ :

$$\begin{array}{cc}& l_{\mathrm{1}}\text{:\hspace{0.17em}\hspace{0.17em}}y=\mathrm{1}\\ l_{\mathrm{2}}\text{:\hspace{0.17em}\hspace{0.17em}}y=\frac{\mathrm{2}t}{Maxiter}\\ l_{\mathrm{3}}\text{:\hspace{0.17em}\hspace{0.17em}}y=\mathrm{4}\times \left(\frac{\mathrm{1}}{\mathrm{2}}-\left|\frac{t}{Maxiter}-\frac{\mathrm{1}}{\mathrm{2}}\right|\right).\end{array}$$

(26)

The three lines are shown in Figure 8 where $Maxiter$ is the maximum iterations, t is the current iteration, and y is the value of $c_3$ . The regions of enclosed shape surrounded by line $l_i$ ( $i=\mathrm{1,2},3$ ), x-axis, and the line of $x=Maxiter$ have the same area. It means the integrals to x-axis in the range of $[0,Maxiter]$ for these three lines are equivalent, and these integral areas have the same size: $Maxiter$ . It means that the virtual forces generated by APF make the same working capacity for the mobile nodes during the execution. When $c_3$ takes the changing value with the curves of $l_1$ , $l_2$ , and $l_3$ , respectively, and the other conditions remain unchanged, the effective coverage of performing PFPSO is shown in Figure 8 accordingly ( $Maxiter=50$ ).

Figure 8

Three changing lines of parameter $c_3$ .

In Figure 9, effective coverage rates corresponding to $l_1$ , $l_2$ , and $l_3$ are very close to each other during the early process of 1st to 10th iteration. During the interval of 15th to 38th iteration, the effective coverage rate of $l_3$ is a little higher than the one of $l_2$ and $l_1$ . After 40 iterations, the search result of PFPSO algorithm approaches the optimal solution. During the whole execution of algorithm, when the work done by the calculated virtual forces on the mobile nodes is the same, the final optimal results of coverage rate by PFPSO are roughly the same. Their rising speeds of the curves of effective coverage rate are slightly different. For these three types of changing lines, the rising of $l_1$   is the slowest, the fastest is the one of $l_3$ , and the middle is the one of $l_2$ .

Figure 9

Effective coverage curves by performing PFPSO based on three changing lines of $c_3$ .

This phenomenon can be explained that in the early state it is difficult to diffuse for the mobile nodes densely gathered in the centre region due to the fixed nodes blocking as a barrier. At this time the coverage probability will be high in their neighboring regions, so the mobile nodes will be difficult to spread due to the lower attraction by the coverage holes. In this state the mobile nodes mainly depend on the local and global optimization factors of the particles to update their positions. With the mobile nodes no longer gathering in a dense state, the parameter $c_3$ also increases in larger way; the weight of potential field force effect on the mobile nodes becomes larger and larger. So in the next stage the mobile nodes will be mainly guided by the virtual force of potential field. Testing results indicate that if we start to weaken the effect of potential field in the later half stage gradually, a better convergence speed will be achieved. So the better strategy of $c_3$ changing is just like the variation trend of $l_3$ . Apparently, in the early half stage of the algorithm implementing, with the mobile nodes scattering out gradually, the effect of the potential field force acting on the mobile nodes should increase accordingly and the value of parameter $c_3$ should be improved to enhance the influence of the velocity component of potential field force. This can accelerate the convergence speed of PFPSO algorithm effectively. In order to get a steady convergence, in the late half stage of performing, the value of parameter $c_3$ should be decreased gradually.

So two conclusions could be achieved: (i) The convergence speed will be different if the changing trend of $c_3$ is different. (ii) During the PFPSO performing, in order to get rid of the barrier effect and get a better convergence speed, the local and the global optimization factors of the particles should take active role to guide the mobile nodes to update their location at the beginning stage, and the virtual force generated by attractive field of the coverage holes should take a main role to guide the mobile nodes to update location in the middle stage. In the late stage, the effect of potential field should be restrained gradually.

7. NPFPSO Performance Analysis

Assuming the target environment is a square region with the area of 200 m × 200 m the hotspot region $A_{\mathrm{h}\mathrm{o}\mathrm{t}}$ is a square area with 100 m × 100 m, and the rest is the ordinary region. At the initial stage, 100 sensor nodes consisting of 60 fixed nodes and 40 mobile nodes are deployed randomly in the target area. The detection radius of each node is $r=14$  m, the parameter of detection reliability of sensor nodes is $r_e=7$  m, and communication radius is $R_c=2\left(r+r_e\right)=42$  m. The maximum moving step of velocity component of potential field in formula (20) is $MaxStep=1$  m. The other parameters of probabilistic detection model are set as follows: ${\alpha }_1=1$ , ${\alpha }_2=0$ , ${\beta }_1=1$ , and ${\beta }_2=1.5$ . The effective detection thresholds of hotspot region and ordinary region are $c_{\mathrm{t}\mathrm{h}\_\mathrm{h}\mathrm{o}\mathrm{t}}=0.95$ and $c_{\mathrm{t}\mathrm{h}\_\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}=0.75$ , respectively. The coverage diagram of initial state is shown as Figure 10.

Figure 10

Initial coverage state for ununiform coverage testing.

The acceleration factors in NPFPSO are set as follows: $c_1=c_2=c_3=1$ , the maximum iterations $Maxiter=50$ , the number of particles is $M=20$ , and the inertia coefficient is set as $w=0.9-0.5\times (1-t/Maxiter)$ according to the experiences.

We can verify the nonuniform deployment algorithm with two types of hotspot region distribution: (i) The hotspot region is in the center of target area. (ii) The hotspot region is in the left bottom corner of target area.

7.1. Hotspot Region in the Center

Figure 11 illustrates the coverage state, displacement of mobile nodes, and coverage curves when NPFPSO algorithm is performed for 50 iterations with weight parameter $\alpha =0.6$ in formula (23).

Figure 11

Nonuniform coverage by NPFPSO with hotspot region in the center ( $\alpha =0.6$ , fixed nodes : mobile nodes = 60 : 40).

The region of dotted frame in Figure 11(b) is the hotspot area. The mobile nodes moved from the original “•” to the terminal “o.” We can find that originally all the nodes distribute randomly in the target area. With NPFPSO performing, the number of mobile nodes in dotted frame increases. After optimization, the number of increased mobile nodes in the centre frame is 7, and the effective coverage rate of hotspot region increases 38.61% compared to its initial state. The red line in Figure 11(c) represents the effective coverage rate of hotspot areas and the blue line represents the effective coverage rate of ordinary area.

A set of Pareto optimal solutions with different weight parameter α is given in Table 2. The effective coverage of hotspot area and ordinary area is listed inside.

Table 2

Comparison table of effective coverage with different weight parameter α when hotspot region is in the center of the target area.

Fixed nodes : mobile nodes	Coverage of hotspot region			Coverage of ordinary region
	$$\alpha =\mathit{0.5}$$	$$\alpha =\mathit{0.6}$$	$$\alpha =\mathit{0.7}$$	$$\alpha =\mathit{0.5}$$	$$\alpha =\mathit{0.6}$$	$$\alpha =\mathit{0.7}$$
60 : 40	$$\mathit{90.65}\%$$	$$\mathit{99.22}\%$$	$$\mathit{97.11}\%$$	$$\mathit{96.89}\%$$	$$\mathit{97.31}\%$$	$$\mathit{96.44}\%$$
50 : 50	$$\mathit{98.20}\%$$	$$\mathit{99.59}\%$$	$$\mathit{98.90}\%$$	$$\mathit{97.97}\%$$	$$\mathit{97.53}\%$$	$$\mathit{98.23}\%$$

Comparing the two circumstances above, adjusting the value of α can change the effective coverage when the number of mobile nodes is 40. When $\alpha \in [\mathrm{0.6,0.7}]$ , the effective coverage of the two regions will approach a high level. When the number of mobile nodes is 50, the regulation effect of parameter α is no longer obvious and the coverage of two regions will all approach a high level.

7.2. Hotspot Region in the Left Bottom Corner

Figure 12 illustrates the coverage state, displacement of mobile nodes, and coverage curves when NPFPSO algorithm is performed for 50 iterations with weight parameter $\alpha =0.4$ in formula (23).

Figure 12

Nonuniform coverage of NPFPSO with hotspot region in the left bottom corner ( $\alpha =0.4$ , fixed nodes : mobile nodes = 60 : 40).

As Figure 12(b) is illustrating, with NPFPSO performed, the number of mobile nodes in left bottom dotted frame increases, and the increased number of mobile nodes is 9. The effective coverage rate of hotspot region increases 43.84% compared to its initial state. The red line in Figure 12(c) represents the effective coverage rate of hotspot areas and the blue line represents the effective coverage rate of ordinary area.

A set of Pareto optimal solutions with weight parameter α taking 3 different values is listed in Table 3.

Table 3

Comparison table of effective coverage with different weight parameter α when hotspot region is in the left bottom of the target area.

Fixed nodes : mobile nodes	Coverage of hotspot region			Coverage of ordinary region
	$$\alpha =0.3$$	$$\alpha =0.4$$	$$\alpha =0.5$$	$$\alpha =0.3$$	$$\alpha =0.4$$	$$\alpha =0.5$$
60 : 40	$$\mathit{76.29}\%$$	$$\mathit{99.95}\%$$	$$\mathit{99.93}\%$$	$$\mathit{97.31}\%$$	$$\mathit{96.78}\%$$	$$\mathit{94.58}\%$$
50 : 50	$$\mathit{87.79}\%$$	$$\mathit{99.91}\%$$	$$\mathit{99.93}\%$$	$$\mathit{98.40}\%$$	$$\mathit{94.35}\%$$	$$\mathit{96.25}\%$$

Comparing the circumstances above, when the hotspot region is at the left bottom corner, mobile nodes will concentrate more in this hotspot region. Effective coverage of two kinds of regions will all approach a better state while the weight parameter $\alpha \in [0.4,0.5]$ .

Since the algorithm presented in the paper is a centralized algorithm, the sensor nodes do not need to move with each iteration of the algorithm. The positions of sensor nodes are only updated at the end of the whole iteration process. So the movement trajectory of a node is nearly a straight line. As a result, compared with the distributed algorithms in which the locations of the nodes will be updated with each iteration, the calculation of energy consumption of sensor nodes here is not so crucial in this case. We just suppose all the mobile nodes have the ability to move to the optimal positions for normal operation within the target area. Regarding the problem of energy efficiency, we had presented other papers to study and analyze it particularly.

8. Conclusion

Deployment algorithm of network is one of the core technologies of wireless sensor networks. Position optimization for mobile nodes can improve the effective coverage rate of hybrid sensor networks. This paper proposed the PFPSO algorithm which improves the typical PSO with the potential field to enhance the convergence speed of optimization, and it can overcome the barrier effect from fixed nodes for the deployment of hybrid sensor networks. The method can drive mobile nodes with dense state to spread to the coverage holes rapidly under the performing of global optimization in the early stage, and then the virtual force generated by potential field can direct the particles updating towards the optimal position. The proposed method can improve the network coverage rate significantly in hybrid sensor networks. On the basis of PFPSO, NPFPSO algorithm was proposed to solve the nonuniform coverage problem by converting the multiobjective optimization problem into a single objective optimization problem. Attractive force generated by potential field can accelerate the convergence speed of the algorithm. The fitness function can be regulated by adjusting the weighting factor α to direct the mobile nodes gathering to the hotspot region. NPFPSO can achieve an optimal result to effective coverage for both hotspot region and ordinary region in hybrid sensor networks.

In more marine realistic situations, the sensor-carried buoys or shallow buoys could be regarded as the fixed detecting nodes, and the AUVs or other boats with sensor-carried could be regarded as the mobile detecting nodes in marine environment. If we just need to gather information for a target region on the sea, and some of the detecting nodes are mobile nodes, the PFPSO algorithm is applicable to be used for optimizing the deployment of the sensor network. However, sometimes we need to do the key monitoring for some key regions. For marine application, we need to emphatically detect the coastal water quality in drain outlet or harbor areas and search and rescue people in some key areas of ocean in which the accidents happen frequently, and also we need to focus on the region with high event occurrence probability in the ocean. For all these circumstances above, the NPFPSO algorithm is suitable to be used for optimizing the effective coverage for hotspot region and ordinary region. Clearly accurate surveillance is required for these hotspot regions and low accuracy surveillance for less focal regions. Anyway, the proposed algorithms could be of more significance to solve these kinds of optimal problems of deployment of sensor networks in practice.