An Improved PSO Algorithm for Distributed Localization in Wireless Sensor Networks

Abstract

Accurate and quick localization of randomly deployed nodes is required by many applications in wireless sensor networks and always formulated as a multidimensional optimization problem. Particle swarm optimization (PSO) is feasible for the localization problem because of its quick convergence and moderate demand for computing resources. This paper proposes a distributed two-phase PSO algorithm to solve the flip ambiguity problem, and improve the efficiency and precision. In this work, the initial search space is defined by bounding box method and a refinement phase is put forward to correct the error due to flip ambiguity. Moreover, the unknown nodes which only have two references or three near-collinear references are tried to be localized in our research. Simulation results indicate that the proposed distributed localization algorithm is superior to the previous algorithms.

1. Introduction

Networks of distributed autonomous nodes that can sense their environment cooperatively are called wireless sensor networks (WSNs) which have great potential for diverse applications in scenarios such as hazardous environment exploration, military target tracking and surveillance, health monitoring, and home automation. In most of these applications, location information of sensor nodes which supports many other network services is critically important.

So far, a wide variety of localization methods have been proposed according to diverse application requirements which can be roughly divided into two types: range-based and range-free. The range-free algorithms mainly use the connectivity between sensor nodes to estimate the locations of unknown nodes without any ranging techniques. The range-based algorithms use some ranging techniques [1] such as Time of Arrival (TOA), Angle of Arrival (AOA), Time Difference of Arrival (TDOA), and Radio Signal Strength (RSS) to measure the distances or angles between unknown nodes and their neighbouring anchor nodes and formulate the localization problem as a multidimensional optimization problem after the ranging information is measured. At the same time, it provides more accurate localization results than range-free algorithms. Compared with the classical optimization methods, bioinspired optimization algorithms such as simulated annealing algorithm (SAA), genetic algorithm (GA), and particle swarm optimization (PSO) solve the localization problem though population-based techniques. They are easier to implement, have faster convergence, and require less computing resources. Hereinto, PSO is an evolutionary computation method based on swarm intelligence without using evolution operators such as crossover and mutation. It is an efficient global optimization algorithm with the advantages of simple operation and avoiding local minima. A lot of literatures apply bioinspired algorithms to implement nodes localization in WSN.

A simulated annealing based localization algorithm in wireless sensor network is proposed in [2] which uses lots of anchor nodes to localize all unknown nodes. The accuracy of this approach is not as good as the PSO algorithm in [3] according to the performance evaluation. A two-phase localization algorithm for WSN presented in [4, 5] is centralized and not feasible for large-scale sensor networks. The localization algorithm which uses a combination of SAA and GA proposed in [4] solves the flip ambiguity problem. An iterative PSO-based algorithm proposed in [6–8] localizes the unknown nodes with three or more neighboring anchors. A new objective function is presented in [9] to evaluate the fitness of particles based on the probabilistic distribution of ranging error. Literature [10] extends the node localization problem to three-dimensional space.

In this paper, we propose a distributed localization algorithm based on PSO which can also extend to large-scale sensor networks. The main contributions of this paper have the following two aspects. (1) It reduces the initial search space by bounding box method to speed up the convergence. (2) It proposes a distributed two-phase PSO algorithm to solve the flip ambiguity problem and localize more target nodes.

The rest of this paper is organized as follows. Section 2 overviews the theory and application of PSO algorithm. Section 3 introduces our improved PSO algorithm for distributed localization in WSNs. Simulation and analysis are presented in Section 4. Section 5 concludes this paper and look forward to the future work in the end.

2. Particle Swarm Optimization Algorithm

2.1. The Theory of PSO Algorithm

Particle swarm optimization (PSO) is a popular bioinspired stochastic global search algorithm proposed by Kennedy and Eberhart [11] that models social behavior of a flock of birds. In this algorithm, all individuals in a population are seen as particles in a multidimensional solution space. First of all, randomly initialize a group of particles in a population. Each of them is a feasible solution and its fitness value is determined by its position in the search space. Each particle moves in the solution space towards the randomly weighted average of the historical personal best position and the historical global best position and finds the current global solution.

Assume that, in an n-dimension objective search space, the population consists of s particles. The position and velocity of the particle i are $X_{id}$ and ${\upsilon }_{id}$ , respectively, $1\le i\le s$ , $1\le d\le n$ . Fitness of a particle is evaluated by an objective function. A particle having smaller fitness value is closer to the global solution than the other particle that is far away. $p{best}_{id}$ is the historical personal best position of particle i where it had the smallest fitness, and $g{best}_d$ is the smallest of all $p{best}_{id}$ , $1\le i\le s$ . At each iteration k, the velocity ${\upsilon }_{id}$ and position $X_{id}$ of each particle are updated using

$$\begin{array}{l}{\upsilon }_{id}\left(k+\mathrm{1}\right)=\omega \times {\upsilon }_{id}\left(k\right)+c_{\mathrm{1}}\times \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{d}}_{\mathrm{1}}\times \left(pbes{t}_{id}-X_{id}\right)\\ +c_{\mathrm{2}}\times \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{d}}_{\mathrm{2}}\times \left(gbes{t}_d-X_{id}\right)\\ X_{id}\left(k+\mathrm{1}\right)=X_{id}\left(k\right)+{\upsilon }_{id}\left(k+\mathrm{1}\right).\end{array}$$

(1)

Here, ω is the inertia weight which denotes the inertia of the particle, $c_1$ and $c_2$ are acceleration constants, and rand₁ and rand₂ are random numbers uniformly distributed in $[0,1]$ . In order to understand this process more clearly, pseudocode is shown in Algorithm 1.

Algorithm 1: Pseudocode of PSO algorithm.

PSO algorithm for minimize the objective function f(⋅)

(1) Initialize ω, $$c_{\mathit{1}}$$ , $$c_{\mathit{2}}$$ , $$X_{\max }$$ , $$X_{\min }$$ , $${\upsilon }_{\max }$$ , $${\upsilon }_{\min }$$

(2) Initialize the maximum number of iteration $$k_{\max }$$

(3) Initialize the target fitness F

(4) Initialize gbest: $$f(gbest)$$ as close to ∞ as possible

(5) for each particle i do

(6)   for each dimension d do

(7)     Initialize $$X_{id}$$ randomly in $$[X_{\min },X_{\max }]$$

(8)     Initialize $${\upsilon }_{id}$$ randomly in $$[{\upsilon }_{\min },{\upsilon }_{\max }]$$

(9)      $$pbes{t}_{id}=X_{id}$$

(10)   end for

(11)   if $$f(X_i)<f(gbest)$$ then

(12)    for each dimension d do

(13)      $$gbes{t}_d=X_{id}$$

(14)    end for

(15)   end if

(16) end for

(17) Initialize $$k=\mathit{1}$$

(18) while ( $$k\le k_{\max }$$ ) AND ( $$f(gbest)>F$$ ) do

(19)    for each particle i do

(20)      for each dimension d do

(21)        if $${\upsilon }_{id}(k)<{\upsilon }_{\min }$$

(22)           $${\upsilon }_{id}(k)={\upsilon }_{\min }$$

(23)        elseif $${\upsilon }_{id}(k)>{\upsilon }_{\text{max}}$$

(24)             $${\upsilon }_{id}(k)={\upsilon }_{\max }$$

(25)        end if

(26)        if $$X_{id}(k)<X_{\min }$$

(27)          $$X_{id}(k)=X_{\min }$$

(28)        elseif $$X_{id}(k)>X_{\max }$$

(29)             $$X_{id}(k)=X_{\max }$$

(30)        end if

(31)      end for

(32)      if $$f(X_i)<f(pbes{t}_i)$$ then

(33)       for each dimension d do

(34)         $$pbes{t}_{id}=X_{id}$$

(35)       end for

(36)      end if

(37)      if $$f(X_i)<f(gbest)$$ then

(38)       for each dimension d do

(39)         $$gbes{t}_d=X_{id}$$

(40)       end for

(41)      end if

(42)    end for

(43)     $$k=k+\mathit{1}$$

(44) end while

2.2. The Application of PSO in WSN Localization

PSO is a kind of optimization algorithm which belongs to range-based methods. That means it needs to measure the distance between the sensor nodes with known locations called beacons and the other sensor nodes which need to be localized, named target nodes. We consider the whole sensor network and sensor nodes as a two-dimensional coordinate system and coordinate points, respectively. Let (x, y) be the coordinate of a target node T, ( $x_i$ , $y_i$ ) the position of its ith neighboring beacon $B_i$ , and ${\widehat{d}}_i$ the measured distance between T and $B_i$ ( $i=\mathrm{1,2},\dots ,P$ ). Then, the problem of localization is regarded as an optimization problem whose purpose is to find the optimal solution (x, y) to minimize the value of the objective function defined in

$$\begin{array}{cc}& f\left(x,y\right)=\frac{\mathrm{1}}{P}{{\displaystyle \sum }}_{i=\mathrm{1}}^P{\left(\sqrt{{\left(x-x_i\right)}^{\mathrm{2}}+{\left(y-y_i\right)}^{\mathrm{2}}}-{\widehat{d}}_i\right)}^{\mathrm{2}}.\end{array}$$

(2)

The target nodes get settled and serve as beacons in the next iteration and the localization process is repeated until either all target nodes get settled or no more nodes can be localized.

The main problem in the process is the flip ambiguity due to near-collinear beacons which have been solved very well in the next section. Moreover, the calculation time has been decreased by reducing the initial search space on the premise of guarantee accuracy.

3. An Improved PSO Algorithm

In this section, a range-based distributed localization algorithm for wireless sensor networks is described. Differences between classical PSO algorithm and our proposed algorithm are reflected in the following four points.

3.1. Define the Initial Search Space by Bounding Box Method

The classical PSO algorithm employs a set of feasible solutions within the search space, called a swarm of particles with random initial locations. In our proposed algorithm, we reduced the initial search space by using a bounding box method.

To facilitate understanding, an example is described in Figure 1. Node n is an unknown node with three beacons or settled nodes $n_1$ , $n_2$ , and $n_3$ in its transmission range. Instead of circles with radius r, we use squares with side length $2r$ to restrict the initial search space of node n in order to avoid floating point operations. The centers of these squares are the nodes $n_1$ , $n_2$ , and $n_3$ , respectively. Therefore, the overlapping portion of these squares (the shaded portion in Figure 1) describes the initial search space of node n. Suppose the coordinate of node $n_i$ is ( $x_i$ , $y_i$ ); then the shaded portion can be expressed as ([max( $x_i-r$ ), min( $x_i+r$ )], [max( $y_i-r$ ), min( $y_i+r$ )]). In our proposed algorithm, every target node has its unique search space determined by the references (beacons or settled nodes) in its transmission range. Comparing with the classical PSO algorithm using the whole solution space as the initial search space for all of the target nodes, the proposed algorithm reduces the computational time and the possibility of flip ambiguity.

Figure 1

Sketch map of bounding box method.

3.2. Anticipation of Nearly Collinear References

An example of flip ambiguity phenomenon is showed in Figure 2. Node A is located by using references B, C, D, and E which are almost collinear and it is possible to estimate A as its flipped location $A^{\prime }$ without making obvious change in the objective function.

Figure 2

Flip ambiguity phenomenon.

The more the references are, the less the probability of flip ambiguity occurrence is. Therefore, when the number of references is small, we should have anticipation about whether these references are near-collinear by using the following rules.

• (i)

If there are only three references, any two of them should not be too close to each other. When the distance between any two references is less than a predefined threshold, these references are judged to be near-collinear.

(ii)

Calculate the distance from any one reference to the straight line which is determined by any two of the rest references. When the value is less than a predefined threshold, these references are judged to be near-collinear.

The above rules can be used in combination to prevent the occurrence of flip ambiguity. When the references of a target node are judged to be near-collinear, the target node will not be localized in this iteration. In the following iteration, the target node may have more references and will be localized until its new references are judged to be non-near-collinear.

3.3. A Refinement Phase to Correct the Error due to Flip Ambiguity

The refinement phase is to relocalize those nodes which still have flip ambiguity problem after the anticipation phase. To inspect whether the flip ambiguity happened, we analyze the relationship between the settled node and its nonneighbor nodes. As seen in Figure 2, if node A is localized in the wrong location $A^{\prime }$ , it will be discovered because $A^{\prime }$ lies within the transmission range of nonneighbor nodes F and G. In the refinement phase, for those localized nodes falls into the wrong neighborhood, an extra term (3) is added to the objective function (2) in order to introduce extra cost for a new estimate. Here, $\delta (·)$ is unit step function; Q is the number of nonneighbor references whose transmission range the estimated position falls within. Consider

$$\begin{array}{cc}& {{\displaystyle \sum }}_{j=\mathrm{1}}^Q\delta \left(r-{\widehat{d}}_j\right){\left(r-{\widehat{d}}_j\right)}^{\mathrm{2}}.\end{array}$$

(3)

3.4. Localize the Target Nodes That Only Have Two References or Three Near-Collinear References

After those target nodes which have at least three non-near-collinear references are all localized, the remaining ones that only have two references or three near-collinear references can be localized by using the refinement phase at last.

3.5. Algorithm Steps

The main purpose of WSN node localization is to estimate the positions of N target nodes as much as possible by using M beacons with known locations in a distributed range-based way. The process of our proposed approach is as follows.

• (i)

N target nodes and M beacons are randomly deployed in a two-dimensional sensor field. The transmission radii of target nodes and beacons are both r. Beacons possess location awareness and transmit their coordinates frequently. The target nodes that get settled at the end of iteration serve as beacons during the next iteration.

(ii)

The target node that falls within the transmission range of three or more non-near-collinear references is considered as a localizable node.

(iii)

The measured distance from a localizable node to each of its neighboring references is simulated as the actual distance plus a Gaussian additive white noise which can be expressed as ${\widehat{d}}_i=d_i+n_i$ . Here, $d_i=\sqrt{{\left(x-x_i\right)}^{\mathrm{2}}+{\left(y-y_i\right)}^{\mathrm{2}}}$ is the actual distance and $(x,y)$ and $(x_i,y_i)$ are the locations of the target node and the ith references, respectively. The measurement noise $n_i$ has a random value uniformly distributed in the range $d_i(1\pm P_n/100)$ . $P_n$ is the percentage noise that affects the result of localization.

(iv)

Each localizable node runs the improved PSO algorithm to localize itself by finding the coordinates (x, y) that minimize the value of the objective function (2).

(v)

In the refinement phase, some of the nodes localized in the previous step should be relocalized by adding an extra term (3) to the objective function (2) owing to their estimated position falls into the wrong neighborhood.

(vi)

Above steps are repeated until either all target nodes are settled or no more nodes can be localized.

(vii)

After those target nodes which have at least three non-near-collinear references are all localized, the remaining ones that only have two references or three near-collinear references can be localized by using the refinement phase at last.

(viii)

The total localization error $E_l$ is computed as the mean of squares of distances between the actual node locations ( $x_i$ , $y_i$ ) and the computed locations $\left({\widehat{x}}_i,{\widehat{y}}_i\right)\hspace{0.17em}\hspace{0.17em}(i=\mathrm{1,2},\dots ,N_L)$ determined by the improved PSO algorithm, as in (4). $N_L$ is the number of the localized nodes. Consider

$$\begin{array}{cc}& E_l=\frac{{\sum }_{i=\mathrm{1}}^{N_L}\left({\left(x_i-{\widehat{x}}_i\right)}^{\mathrm{2}}+{\left(y_i-{\widehat{y}}_i\right)}^{\mathrm{2}}\right)}{N_L}.\end{array}$$

(4)

4. Simulation and Analysis

4.1. Compared with the Classical PSO Algorithm

Simulation was carried out in MATLAB environment. $N=40$ target nodes and $M=8$ beacons are randomly deployed in a sensor field of 100 × 100 square units. Each node has a transmission radius of $r=30$  units.

The parameters of the proposed node localization algorithm are set as follows:

• (i)

population = 30, iterations = 150;

(ii)

acceleration constants $c_1=c_2=2.0$ ;

(iii)

inertia weight ω is decreased linearly from ${\omega }_{\mathrm{m}\mathrm{a}\mathrm{x}}=0.9$ in the first iteration to ${\omega }_{\mathrm{m}\mathrm{i}\mathrm{n}}=0.4$ in the last iteration, as described in (5). Here, k is the number of iterations and $k_{\mathrm{m}\mathrm{a}\mathrm{x}}$ is the maximum number of iterations;

$$\begin{array}{cc}& \omega ={\omega }_{\mathrm{m}\mathrm{a}\mathrm{x}}-\frac{{\omega }_{\mathrm{m}\mathrm{a}\mathrm{x}}-{\omega }_{\mathrm{m}\mathrm{i}\mathrm{n}}}{k_{\mathrm{m}\mathrm{a}\mathrm{x}}}\times k;\end{array}$$

(5)

(iv)

limits on particle positions: $X_{\mathrm{m}\mathrm{a}\mathrm{x}}=100$ and $X_{\mathrm{m}\mathrm{i}\mathrm{n}}=0$ .

In order to show the advantage of our algorithm more intuitively, we made some contrast figures to analyze each step independently as follows.

Firstly, we use methods described in Sections 3.2 and 3.3 to avoid the flip ambiguity phenomenon. An example in a trial shows the different localization results between the experiments with and without methods 3.2 and 3.3.

As shown in Figure 3 (the red circle represents the location of beacon node, the blue circle represents the location of target node, the blue asterisk represents the location estimated by the PSO algorithm, and the blue straight line represents the localization error, that is, the distance between the actual node location and the estimated location), flip ambiguity phenomenon leads to large localization errors. To avoid such problems, we use methods described in Sections 3.2 and 3.3 to reposition. As a result, large localization errors have been corrected in Figure 4.

Figure 3

Result with flip ambiguity phenomenon.

Figure 4

Result without flip ambiguity phenomenon.

Figure 5 directly shows the difference from a purely numerical perspective. The blue curve and red curve which represent the variation tendency of the localization error defined as $E_l$ in (4) with the number of settled nodes $N_L$ gradually increase in a trial with and without methods 3.2 and 3.3, respectively. Obviously, the localization error $E_l$ produced by the first 26 settled nodes is reasonable and almost the same in both curves. However, the localization of the 27th node causes flip ambiguity which leads to the huge localization error in point B. Easy to see, the localization error $E_l$ on the red curve suddenly changes from 0.14 to 98.39. But, on the blue curve, we avoid the huge and unreasonable error with methods 3.2 and 3.3 and receive an acceptable localization error 0.20 in point A instead of B.

Figure 5

Localization error $E_l$ with the number of settled nodes $N_L$ .

Secondly, we reduced the initial search space by using a bounding box method which is described in 3.1. 30 trial experiments are conducted for $P_n=2$ and $P_n=5$ , respectively. Average of computing time for all 30 runs with and without method 3.1 is computed and analyzed comparatively in Figure 6. From this chart we can see that experiments with method 3.1 reduce the computing time for both $P_n=2$ and $P_n=5$ .

Figure 6

Computing time for $P_n=2$ and $P_n=5$ .

Finally, in our algorithm, we localize the target nodes that only have two references or three near-collinear references by using the refinement phase at last which is described in 3.4. 30 trial experiments are conducted for $P_n=2$ and $P_n=5$ , respectively. The percentage of localizable nodes for all 30 runs with and without method 3.4 is computed and the mean value is analyzed comparatively in Figure 7. As we see in this chart, experiments with method 3.4 localize more target nodes for both $P_n=2$ and $P_n=5$ .

Figure 7

Localizable nodes percentage for $P_n=2$ and $P_n=5$ .

4.2. Compared with the HPSO Algorithm

The HPSO method [8] divides the whole swarm into subswarms and the particle with the best fitness in the local swarm is termed as $l{best}_{id}$ . At each iteration k, the velocity ${\upsilon }_{id}$ and position $X_{id}$ of each particle are updated using

$$\begin{array}{l}{\upsilon }_{id}\left(k+\mathrm{1}\right)=\omega \times {\upsilon }_{id}\left(k\right)+c_{\mathrm{1}}\times \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{d}}_{\mathrm{1}}\times \left(pbes{t}_{id}-X_{id}\right)\\ +c_{\mathrm{2}}\times \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{d}}_{\mathrm{2}}\times \left(gbes{t}_d-X_{id}\right)\\ +c_{\mathrm{3}}\times \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{d}}_{\mathrm{3}}\times \left(lbes{t}_{id}-X_{id}\right)\\ X_{id}\left(k+1\right)=X_{id}\left(k\right)+{\upsilon }_{id}\left(k+1\right).\end{array}$$

(6)

The parameters of HPSO node localization algorithm are set as follows:

• (i)

  population = 50, iterations = 150;

• (ii)

  acceleration constants $c_1=c_2=c_3=1.494$ ;

• (iii)

  inertia weight $\omega =0.7$ ;

The parameters of our proposed node localization algorithm are set as follows:

• (i)

  population = 50, iterations = 150;

• (ii)

  acceleration constants $c_1=c_2=2.0$ ;

• (iii)

  inertia weight ω is decreased linearly from ${\omega }_{\mathrm{m}\mathrm{a}\mathrm{x}}=0.9$ in the first iteration to ${\omega }_{\mathrm{m}\mathrm{i}\mathrm{n}}=0.4$ in the last iteration, as described in (5).

In order to compare the three different algorithms, ten trial experiments for each algorithm are conducted in the MATLAB environment. $N=100$ target nodes are randomly deployed in a sensor field of 100 × 100 square units. Each node has a transmission radius of $r=25$ units and the percentage noise $P_n=2$ . Average of localization error and computing time for $M=\mathrm{20,30,40}$ beacons of the three different algorithms are shown in Figures 8 and 9, respectively. Easy to see, the mean localization error reduces with the increasing number of beacons M whatever the method is. Having more beacons is advantageous because it gives more references for the target nodes to localize themselves. However, our method is more precise than the other two methods and saves more computing time.

Figure 8

Localization error $E_l$ with number of beacons M.

Figure 9

Computing time t with number of beacons M.

Average of localization error and computing time for $P_n=\mathrm{1,2},\dots ,5$ are computed and analyzed comparatively in Figures 10 and 11, respectively. As shown in Figures 10 and 11, the effect of $P_n$ , percentage noise in distance measurement, can be clearly seen. The localization error increases with the increasing noise $P_n$ whatever the method is. However, our method is more precise than the other two methods which required significantly more computing time. That is to say, our proposed PSO algorithm provides higher accuracy in less computing time.

Figure 10

Localization error $E_l$ with percentage noise $P_n$ .

Figure 11

Computing time t with percentage noise $P_n$ .

5. Conclusion and Future Work

In this paper, an improved PSO algorithm is proposed to solve the distributed localization problem in WSN, which can be regarded as a multidimensional optimization problem. To improve the localization precision and algorithm efficiency, we present some methods in Section 3 whose effectiveness has been proved by the simulation results. In order to show the advantage of our algorithm more intuitively, we made some contrast figures to analyze each method independently. The experimental results show that our method which can localize more unknown nodes with higher precision in less computing time is superior to the other two methods.

Further, the control of iterative error propagation and energy consumption are potential and significant directions. In this paper, we considered the nodes localization problem in two-dimensional space. However, in real environment, sensor nodes are distributed in three-dimensional space. Some research will be taken on our proposed algorithm in three-dimensional space. Moreover, the proposed algorithm may be extended for nodes localization in mobile wireless sensor network. The effectiveness of these planning works will be validated in experiments in the future.