Directional Probability Perceived Nodes Deployment Based on Particle Swarm Optimization

Abstract

Node deployment is the key problem of wireless sensor network technology. For a directional sensor network, the perceived probability model reflects the quality of the network. The problem of the probability node deployment is too little of the distribution of the nodes asymmetrical. In this paper, we study the probability model of directional perceived nodes and propose an improved deterministic deployment algorithm based on particle swarm optimization to increase perceived probability. By analyzing the coverage probability of the monitoring area with different deployment models to obtain more serviceable environmental data of the monitoring areas, experimental results demonstrate that, compared with random deployment, sixteen percent is improved by the proposed algorithm.

1. Introduction

In recent years, with the rapid development of wireless multimedia technology, visual sensor nodes are receiving significant attention [1], which leads to the emergence of directional sensor network [2]. In order to ensure normal operation of the directional sensor network, the sensor nodes in internal target area need to deploy well.

The node deployment is the first step in wireless sensor networks [3]; it is directly related to accuracy, integrity, and effectiveness of the network monitoring information.

According to different methods of nodes deployment, wireless sensor networks can be divided into random deployment and deterministic deployment. When using directional sensing node for monitoring area coverage, it can be divided into Boolean model [4] deployment and probability model [5] deployment according to the node sensing model.

Most of the researches on directional coverage are focused on the Boolean model in random deployment. Gupta et al. [6] addressed the problem of optimal deployment in terms of the number of nodes required to achieve k-coverage in m-connected. The communication is the region over which a node can communicate with others. The object of study was omnidirectional nodes, and the characteristics of directional nodes are different from them. Li et al. [7] derived a variant of perceived direction of nodes and developed a node scheduling rule and distributed algorithm. In the three-dimensional space, Fan et al. [8] presented a distributed 3D localization scheme for an irregular wireless sensor network using multidimensional scaling. Greedy algorithm was proposed in [9] to solve the problem of random area maximum deployment. Sung and Yang [10] utilized the structure and characteristic of Voronoi cells and proposed a new solution for target tracking in visual/camera sensor networks. In [11], an observation correlation coefficient was developed to describe the correlations between images observed by cameras by studying the sensing model and deployment of cameras in the network and proposed a camera sensor activation scheme for target tracking in wireless video sensor networks. The aforementioned algorithms can adjust the location of nodes in random deployment but cannot be applied to deterministic deployment.

The Boolean model is an idealized model. In practical applications, sensor nodes have difficulty achieving full step type sensing; therefore, the probability model is more practical. The deployment of probabilistic sensing model mostly focuses on the random deployment. Jiang et al. [12] proposed a k-coverage distributed algorithm based on probability model to construct k working covers that provided probabilistic k-coverage for the whole target region. Li et al. [13] proposed a direction adjustable linear model, which was basic on the direction adjustable sensing model. A probabilistic sensing model for directional sensor node was designed in [14] based on the existing directional sensing models which were always affected by uncertain sensing ability on their edges of two sides. In [15], a node deployment scheme was presented based on the perceived probability model for the wireless network nodes which were randomly deployed. Sun et al. [16] proposed enhanced coverage algorithm to present the coverage probability of sensor nodes and the solution of expected values for coverage quality. The sector area formed when moving target nodes pass sensor nodes; it cannot be used on the fixed node deployment.

Random deployment is more economical and applicable; however, it cannot cover the monitoring region completely. It is generally applicable to the observation environment which does not strictly demand coverage. For a relatively fixed network status or application environment, node position information, and the node density which is known, the deterministic deployment commonly is used. Currently, there is less study about deterministic deployment of directional sensor. In [17], put forward a method for optimal deterministic deployment of target coverage. The target coverage does not guarantee the monitoring area to be covered completely. In order to obtain the integral monitoring information, area covering deterministic deployment should be investigated. Guo et al. [18] proposed a deterministic sensor node deployment method to use the least nodes to achieve the target coverage, using the least sensing probability with which a node can sense a target as the measure of the whole coverage level. The 0 and 1 were chosen as the limit of the perceived probability, respectively.

At present, little work has been done on probability model of deterministic deployment in area coverage of friendly accessible environment; the normalization algorithm cannot guarantee obtaining complete monitoring information when using probability model, so the study on the probability model of deterministic deployment has an urgent demand. In this paper, on the basis of satisfying the node communication, the deployment of probability perceived model of wireless image sensor node is investigated. In order to obtain effective quality information of the monitoring area, we optimize the limit of the perceived probability and provide an improved algorithm to improve the perceived probability.

The rest of the paper is organized as follows. In Section2, a probability coverage model is established. And a deployment method is selected in Section3. In Section4, the particle swarm optimization is introduced and an improved deterministic deployment algorithm based on the probability model is proposed. In Section5, simulation experiments are carried out and analysis of the main influencing factors is provided. Finally, analysis of the results is given in Section6.

2. Probability Coverage Model

The perceived probability model of directional sensing node [19,20] is usually defined in the two-dimensional space. The perceptive range is a sector with a node as the center and the perceived distance as radius as shown in Figure1. P denotes the position coordinates of nodes; $R_s$ denotes the perceived radius; $R_e$ is the uncertain value in the inductive process and $R_c$ is the communication radius; α is the perspective offset of sensor node, that is, the half of perspective.

Figure 1

Nonrotating sector perceived probability model.

The mathematical expression of the monitoring probability of arbitrary point q in the sensing area is defined [21] as

$$\begin{array}{cc}& p\left(s\right)=\left\{\begin{array}{cc}0,\hfill & R_s\le d\left(s,q\right),\hfill \\ e^{-\lambda {\alpha }^{\beta }},\hfill & R_s-R_e\le d\left(s,q\right)\le R_s,\hfill \\ 1,\hfill & R_s-R_e\ge d\left(s,q\right),\hfill \end{array}\right.\end{array}$$

(1)

where $d(s,q)$ denotes the line distance between the monitoring target s and the node q, $\alpha =d(s,q)-(R_s-R_e)$ , and λ and β are the attenuation coefficient when $d(s,q)$ changes in loop region $(R_s-R_e)~R_s$ .

3. Coverage Model

At present, there are two deployment methods that can achieve real-time complete coverage. One is the circular mode, which combines the sector sensing node into a circle. The other method is the tiled mode in which two relative nodes are a group and two nodes in the same position are a group as shown in Figure2.

Figure 2

The methods of deployment.

Circular mode can use regular coverage algorithm in the monitoring region. The circle which combined with directional sensing nodes was deployed in accordance with the equilateral triangle, square, rhombus, regular hexagon, and unregular equilateral hexagon deployment [22].

In the probability sensing model, to achieve the completely effective perception, single sensor node may not meet the demand. We set the threshold η, and when $p_{{\alpha }_i}>\eta$ , the target is perceived, whereas the target is perceived loss. Here η is set to the initial probability $p_0$ [23,24]:

$$\begin{array}{cc}& \eta =p_0=1-{\left(1-\frac{\alpha r_s^2}{lm}\right)}^n,\end{array}$$

(2)

where l and m denote the length and width of the monitoring area, respectively, and n is the number of the nodes.

For the monitoring area with $l\times m$ pixels, $p_{\mathrm{c}\mathrm{o}\mathrm{v}}(s_i)$ denote whether the ith pixel can be perceived by wireless sensor network:

$$\begin{array}{cc}& p_{\mathrm{c}\mathrm{o}\mathrm{v}}\left(s_i\right)=\left\{\begin{array}{cc}0,\hfill & p\left(s_i\right)<p_0,\hfill \\ 1,\hfill & p\left(s_i\right)\ge p_0.\hfill \end{array}\right.\end{array}$$

(3)

The pixels of monitoring area stack up to the sum of each pixel covered by $s_i$ . The total area of the area covered by the $p_{\text{area}}$ is defined as the ratio of the sum of pixels to the total area of the monitoring area:

$$\begin{array}{cc}& p_{\text{area}}=\frac{{\sum }_{i=1}^{l\times m}{p}_{\mathrm{c}\mathrm{o}\mathrm{v}}\left(s_i\right)}{l\times m}.\end{array}$$

(4)

4. Proposed Algorithm

4.1. Particle Swarm Optimization

The particle swarm optimization algorithm was proposed by Kennedy and Eberhart in 1995, which is based on the social behavior of a flock of birds [25]. It is a new evolution algorithm. The algorithm flowchart is shown in Figure3.

Figure 3

The flowchart of PSO.

The dimension of the search space is D. Therefore, the position of particles in this space is given by a vector $X_i$ ; $X_i=(x_{i1},x_{i2},\dots ,x_{id}{)}^T$ , and the velocity is $V_i$ ; $V_i=(v_{i1},v_{i2},\dots ,v_{id}{)}^T$ . The initial position and velocity of the particles are randomly set according to certain constraints. The position and the velocity of each particle evolve as follows:

$$\begin{array}{c}{v}_{id}^{k+1}=v_{id}^k+c_1{\hspace{0.17em}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}}_1^k\left({\mathrm{p}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}_{id}^k-x_{id}^k\right)\\ +c_2{\hspace{0.17em}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}}_2^k\left({\mathrm{g}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}_d^k-x_{id}^k\right),\end{array}$$

(5)

$$\begin{array}{cc}& x_{id}^{k+1}=x_{id}^k+v_{id}^{k+1},\end{array}$$

(6)

where the current position of i in this space at the kth iterate is given by $v_{id}^k$ , its current velocity is $x_{id}^k$ , and $c_1$ and $c_2$ represent the cognitive factor and social factor which control the motion of the particle to its personal best position and global best position. ${\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}}_{\mathrm{1,2}}$ is an independent random number from 0 to 1. ${\mathrm{p}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}_{id}$ represents the best position ever found for the ith particle and ${\mathrm{g}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}_d$ , respectively, the global best position.

4.2. The Regulative Algorithm of Deterministic Deployment

In order to obtain effective quality information of the monitoring area, it is necessary to increase the number of nodes for cooperative awareness. Furthermore, a regulative algorithm of deterministic deployment is presented.

The algorithm is composed of the following steps:

• (1)

Divide the monitoring region into grid and calculate the number of sensors $n=(S/\pi R_S^2)/⌈2\pi /\alpha ⌉$ and the probability threshold by formula (2).

(2)

Initialize the increased node number $n_1=0$ .

(3)

Determine whether the minimum probability of each grid is less than the threshold probability η. If there is any numerical value less than η, $n_1=n_1+1$ , compare the minimum probability of the grid after increasing the nodes with the probability threshold. If it is still less than η, $n_1=n_1+1$ .

(4)

Output the total number of the nodes in the monitoring area $n_2=n+n_1$ .

(5)

Let $n_2$ be population scale and let the search space be D dimension. Initialize $p_{\mathrm{p}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}=p_0$ , $p_{\mathrm{g}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}=p_0$ , and the position and perceived orientation of increased sensors.

(6)

Calculate $p_{\text{area}}$ by formulas (3) and (4).

(7)

Compare $p_{\text{area}}$ , $p_{{\mathrm{p}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}_i}$ , and $p_{\mathrm{g}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}$ , if $p_{\text{area}}>p_{{\mathrm{p}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}_i}:p_{{\mathrm{p}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}_i}=p_{\text{area}}$ and if $p_{{\mathrm{p}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}_i}>p_{\mathrm{g}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}:p_{\mathrm{g}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}=p_{{\mathrm{p}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}_i}$ .

(8)

Calculate $v_{id}^{k+1}$ by formula (5). Let $v_{\mathrm{m}\mathrm{a}\mathrm{x}}$ be the maximum speed limit, $v_{\mathrm{m}\mathrm{a}\mathrm{x}}=\pi$ ; when $v_{id}^{k+1}$ ( $i=\mathrm{1,2},3$ ) $>v_{\mathrm{m}\mathrm{a}\mathrm{x}}$ , $v_{id}^{k+1}=v_{\mathrm{m}\mathrm{a}\mathrm{x}}$ ; when $v_{id}^{k+1}$ ( $i=\mathrm{1,2},3$ ) $<-v_{\mathrm{m}\mathrm{a}\mathrm{x}}$ , $v_{id}^{k+1}=-v_{\mathrm{m}\mathrm{a}\mathrm{x}}$ . Calculate $x_{id}^{k+1}$ by formula (6) and update the perceived orientation.

(9)

Determine whether the increasing rate of the minimum probability of each grid is 0; if there is any increasing rate that is not equal to 0, jump to Step (6), otherwise output the results.

5. Simulation Results and Analysis

According to [26], when the value of the perceived angle is between 60° and 72°, circular deployment and tiled deployment have the same average overlap area. Therefore, in the experiments, the nodes were isomorphic in which sensing radius is 30 m, the range of communication radius is between 24 m and 60 m, the uncertain value $R_e$ is 16 m, and sensing angle is 60°. A square area of $S=1000\hspace{0.17em}\mathrm{m}\times 1000\hspace{0.17em}\mathrm{m}$ was selected as the experimental scene, simulated in Matlab R2013a.

The number of the nodes according to radius proportion is presented in Figure4. The probability threshold η of different deployment methods is shown in Figure5. $R_c/R_s$ represents the ratio of the communication radius to perceived radius. The higher probabilistic threshold means can get more monitoring information; when $R_c/R_s>1.224$ , the equilateral triangle pattern is the best choice; when $R_c/R_s>1.224$ , the regular hexagon pattern is better.

Figure 4

The number of the nodes according to radius proportion.

Figure 5

The probabilistic threshold according to radius proportion.

The perceived probability of the node to object is shown in Figure6. When the distance of object to node is less than 19.31 m, the perceived probability of the six deployment methods is the same, and when the distance is more than 19.31 m, the perceived probability in regular hexagon deployment mode is lasting 1; therefore, the regular hexagon deployment can achieve the Boolean model coverage (i.e., 0-1 monitoring).

Figure 6

The perceived probability according to different deployment.

According to the improved deterministic deployment algorithm based on probability model, the number of the nodes adjusted by probability threshold according to radius proportion is shown in Figure7. The regular hexagon deployment is greater than the threshold probability, which need not increase nodes. Under the condition of satisfying all the monitoring area which are perceived and nodes which can communicate with each other, when $R_c/R_s>1$ , the number of nodes used by regular hexagon deployment is least; when $1<R_c/R_s<1.205$ the unregular equilateral hexagon deployment uses the least number of nodes to coverage; when $R_c/R_s>1.205$ , the tiled method is with the least number of nodes.

Figure 7

The probability threshold according to radius proportion.

Adjust the position and direction of the node with PSO shown in Figure8(a), compared with random deployment, which is shown in Figure8(b); the proportion of overlapped area is small. When the increase amplitude of perceived probability is 0, the minimum perceived probability of improved PSO is 78.7%, and the initial deployment algorithm is 62.7%.

Figure 8

The comparison of nodes deployment.

For the same numbers of isomorphic nodes, the improved PSO algorithm optimized the probability threshold, according to the inductive characteristics of the probability model, updated the position of the nodes by judging the extremum, and improved the monitoring probability.

6. Conclusion and Further Work

This paper adopted the deterministic deployment of directional perceived nodes to achieve regional coverage. An improved deterministic deployment algorithm based on the PSO was proposed. The proposed algorithm is mainly used in the adjustment of the location and direction of the increased nodes to ensure that the coverage probability in the monitoring area is greater than the probability threshold, thus obtaining better monitoring information. According to the experimental results, the proposed algorithm improves the perceived probability compared with the initial deployment in the monitoring area and the coverage level of the regular hexagonal deployed is the highest. For the future work, we will focus on the convergence rate and positioning accuracy of the deployment algorithm.