# Localization Algorithm in Wireless Sensor Networks Based on Multiobjective Particle Swarm Optimization

Authors: Ziwen Sun; Li Tao; Xinyu Wang; Zhiping Zhou
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

Based on multiobjective particle swarm optimization, a localization algorithm named multiobjective particle swarm optimization
localization algorithm (MOPSOLA) is proposed to solve the multiobjective optimization localization issues in wireless sensor networks. The multiobjective functions consist of the space distance constraint and the geometric topology constraint. The optimal solution is found by multiobjective particle swarm optimization algorithm. Dynamic method is adopted to maintain the archive in order to limit the size of archive, and the global optimum is obtained according to the proportion of selection.
The simulation results show considerable improvements in terms of localization accuracy and convergence rate while keeping a limited archive size by a method using  the global optimal selection operator
and dynamically maintaining the archive.


---

## Body

## 1. Introduction

The research on localization issues is important to the practical application of wireless sensor networks (WSN) technology. Modern WSN applications pose increasingly complex and stringent performance requirements on localization in terms of accuracy. However, the localization methods by using traditional ranging technologies, such as received signal strength indication (RSSI), have the drawback of low accuracy. Some intelligent algorithms have been used to solve the problems of localization including the accuracy [1–3].Traditionally, most studies focused on using single-objective optimization problem to solve localization problems. Among these methods, the particle swarm optimization (PSO) algorithm is concerned by many researchers for its fast convergence rate and simple implementation. By using particles to imitate the estimated coordinates of unknown nodes, some methods model the localization problem as a single-objective optimization model with the space distance constraint as the only fitness function. For example, the PSO localization algorithm based on log-barrier constraint function could accelerate the convergence speed and save energy [4], the PSO localization adopting crossover operator and the mutation operator could avoid the premature convergence [5], and the PSO localization algorithm based on quantum mechanics could enhance the global convergence and improve the accuracy [6]. However, it always happens that the results of estimated nodes’ localizations meet the space distance constraint without meeting the geometric topology constraint because of ranging errors in some practical applications.Recently, some works have proved the effectiveness of multiobjective optimization algorithms to solve conflict multiple objectives [7–14]. It is more reasonable to model the node localization as a multiobjective optimization problem, which can be described as solving a Pareto solution, rather than simply being described as a single-objective optimization problem. Based on this viewpoint, a multiobjective model was adopted to solve the node localization problem with fitness functions including the localization accuracy and the topological constraint, and the optimal solution was achieved by using the genetic algorithm [7]; however, there are still some problems which are not solved. (i) The estimation accuracy is affected by the selection and mutation operators. (ii) The convergence rate is slow. (iii) The storage consumption of nodes is very big due to the limitless size of the archive for storing the Pareto optimal solutions.Multiobjective particle swarm optimization has been proved with outperformance in the accuracy and the convergence. A multiobjective multileader PSO was used to handle an extra objective by constraint handling method with advantage in terms of efficiency [8]. A bare-bones PSO was combined with the sensitivity-based clustering to solve multiobjective reliability redundancy allocation problems as a Pareto optimal solution with high effectiveness [9]. Multiobjective PSO algorithm was used to optimize parameters of Stirling engine with more accurate results than genetic algorithms [10]. The multiobjective swarm optimization problem, which selected the global best particle from a set of Pareto optimal solutions to solve the convergence and the diversity of solutions, was solved by combining PSO with charge system search [11]. The multiswarm multiobjective PSO was decomposed by multiobjective decomposition to solve problems of local optimum, convergence, and accuracy of Pareto solution set [12]. The dynamic constrained multiobjective optimization problem was developed by introducing a local search operator based on attraction into PSO to speed up the optimization process or Pareto optimal solutions for obtaining a high convergence [13].The main contribution of this paper is to propose a novel algorithm named multiobjective particle swarm optimization localization algorithm (MOPSOLA) for WSN localization to address the issues of the limitless archive and the slow convergence exiting in [7]. MOPSOLA constructs a multiobjective model with both the space distance constraint and the geometric topology constraint as multiobjective functions and solves the localization problem as a Pareto optimization problem. Three kinds of mechanisms are used to insure the higher localization accuracy, the lower storage consumption, and the higher convergence. (i) The geometric topology constraint is considered to reduce the inaccuracy of localization. (ii) The archive is dynamically maintained and limited in a maximum capacity to save the storage space for storing the Pareto optimal solutions. (iii) The global optimum solution is obtained to accelerate the convergence by adopting the mechanism of proportion of selection. The simulation results have proved the proposed algorithm can effectively find the multiobjective optimal solutions and achieve both the better convergence speed and the better localization accuracy.


## 2. Multiobjective Localization Model

The coordinates of unknown nodes need to meet both the space distance constraint and the geometric topology constraint. The purpose of meeting the space distance constraint is to make the estimated coordinates close to the real values, and meanwhile the purpose of meeting the geometric topology constraint is to make the network topology unique to avoid forming a topological structure which is not in conformity with the actual situation.Assume thatn nodes are deployed in two-dimensional space Z2 of WSN, including m anchor nodes and n-m unknown nodes with m<n. Assuming the two nodes i and j being in the communication radius of each other, the internode ranging distance dij can be obtained by RSSI ranging technology and denoted by (1)dij=rij+eij,where rij=(xi-xj)2+(yi-yj)2 is the actual distance between the two nodes and eij is the ranging error of RSSI which follows a zero mean Gaussian distribution with variance σ2 [7].The neighbour setNi and the complement set Ni¯ of node i are defined as (2)Ni=j∈1,…,n,j≠i:rij≤R,Ni¯=j∈1,…,n,j≠i:rij>R,where R is the communication radius of node i.The objective function of the space distance constraint is denoted by(3)f1=∑i=m+1n∑j∈Nid^ij-dij2,where d^ij is the estimated distance between node i and j, denoted by (4)d^ij=x^i-xj2+y^i-yj2ifjisananchor,x^i-x^j2+y^i-y^j2otherwise,where x^i,y^i and x^j,y^j are estimated coordinates of unknown nodes i and j.The objective function of the geometric topology constraint is denoted by(5)f2=∑i=m+1n∑j∈Niδij+∑j∈Ni¯1-δij.The geometric topology constraint represents the connectivity constraint which dissatisfies the current estimated positions of nonanchor nodes [7]. And δij is denoted by (6)δij=1ifd^ij>R,0otherwise.The space distance constraint and the geometric topology constraint imply the accuracy of the coordinates of the nodes. The high accuracy of estimated coordinates of the unknown nodes consequently lead to the small values of the two objective functions. Therefore, estimating coordinates of the unknown nodes can be modeled to search the optimum solution for the multiobjective optimization issues, which can be obtained by decreasing both values of the objective functionsf1 and f2.


## 3. MOPSOLA

### 3.1. Mathematical Description of MOPSOLA

The optimal solution of multiobjective optimization issues is to find the Pareto optimal solution [14]. Multiobjective optimization issue with u-dimensional decision vectors and v objectives is denoted by (7)MinmizeFx=f1x,f2x,…,fvxs.t.x∈xL,xU,where x=(x1,x2,…,xu)∈X∈Ru and F=(f1,f2,…,fv)∈Y∈RV. x is called the decision vector belonging to the u-dimensional decision space X, which is corresponding to u-particles in PSO. xL and xU are lower and upper bound constraints of the particle range, respectively. F is the objective vector belonging to the v-dimensional objective space Y. The objective function F(x) defines mapping functions from the decision space to the objective space. The set of all the particles meeting the constraints forms the decision space feasible set Ω={x∈Ru∣x∈[xL,xU]}.Some concepts related with MOPSOLA are described as follows.(i)
For two feasible solutionsxa, xb∈Ω in the processing of PSO, if, ∀i=1,2,…,v, fixb≤fixa∧∃j=1,2,…,v, fj(xb)<fj(xa), then call xb dominate xa, denoted by xb≺xa, and keep xb as optimization results.(ii)
The Pareto optimal solutionx* is the decision vector which satisfies ¬∃x∈Ω:x≺x*.(iii)
S={x∈Ω∣¬∃x′∈Ω,fjx′≤fjx,j=1,2,…,v} constructs the set of Pareto optimal solution obtained from all of the Pareto optimal solutions.(iv)
Fx={Fx*=(f1(x*),f2(x*),…,fv(x*))∣x*∈S} forms the Pareto front consisting of the values of objective functions corresponding to the Pareto optimal set.(v)
The purpose of optimization is to find the Pareto optimal solution.In MOPSOLA, model the estimated coordinates ofn-m unknown nodes as the decision vectors, and the two objective functions defined by (3)–(5) consist of the objective function F(x). Therefore, from formulas (3)–(5) and (7), MOPSOLA can be formulated in the optimum mathematical form as(8)MinmizeFx=f1x^i,y^i,f2x^i,y^is.t.x^i,y^i∈x^L,y^L,x^U,y^Ukkkkkkkklli=m+1,m+2,…,n,where decision vectors x=(x^i,y^i)(i=m+1,m+2,…,n) are the estimated coordinates corresponding to particles in PSO, (x^L,y^L) and (x^U,y^U) are the lower and upper bound constraint values, f1 is the objective function of the space distance constraint, and f2 is the objective function of the geometric topology constraint. Therefore the decision space is u=n-m dimension and the objective space is v=2 dimension; that is, the coordinates of unknown nodes are u=n-m particles, f1 and f2 are the v=2 objective functions.Obtaining the multiobjective Pareto optimal solution is the ultimate goal of building a multiobjective optimal model for localization issues, which meets both the space distance constraint and the geometric topology constraint. Therefore the main essence of MOPSOLA can be described as determining the dominant relationship according to the decision space feasible setΩ and the Pareto front Fx*={(f1(x^i*,y^i*),f2(x^i*,y^i*))∣xi*=(x^i*,y^i*)∈S}, i=m+1,m+2,…,n, saving Pareto optimal solution set S in an archive and updating the position and the velocity of multiobjective PSO.


### 3.2. Describing of MOPSOLA

#### 3.2.1. Overall Framework

Shown as Figure1, the framework of the proposed multiobjective PSO algorithm includes some key operators such as maintenance of archive, global optimum selection, and the velocity and localization update. The particle population relies on an archive to save Pareto optimal solutions during the iterative process and selecting the global optimum from these solutions, which is the key point that the multiobjective PSO is different from the traditional single objective localization.Figure 1
Overall framework of the multiobjective PSO.Therefore, the localization issue is modeled as a multiobjective optimization model in MOPSOLA, and two operators, which are the dynamic maintenance operator for the archive and the global optimum selection operator based on proportion of selection, are designed to be suitable for the limited energy and the poor computing power of WSN nodes.(i)
In the multiobjective function calculation level, functions as formulas (3)–(5) are calculated according to all particles, that is, all estimated nodes’ coordinates.(ii)
In the individual optimal selection level, the personal optimum selection operator works. Based on the concept of Pareto optimality, thepbest of each particle is chosen between the particle’s current location and its historical pbest dynamically.(iii)
In the global optimal selection level, the global optimum selection operator works. The proportion of selection is set for each Pareto optimal solution based on intensive distance, and a global optimum for each particle is selected by proportion of selection.(iv)
In the velocity and localization update level, the position and velocity update operator works for all individual particles. The update process is similar to the traditional single objective PSO as(9)vit+1=ωvit+c1r1pbesti-hit+c2r2gbest-hit,hit+1=hit+vit+1,i=m+1,m+2,…,n,wherevi is the velocity of the ith particle, hi=(x^i,y^i) is the estimated coordinates of the ith particle vector, pbesti is the best solution for the ith particle, gbest is the best solution for the population, ω is the inertia weight, c1 and c2 are constants, and t is the iteration time.(v)
In the maintenance of archive level, the archive maintenance operator works. The maximum capacity of archive is set asArcMax and the archive is dynamically updated according to the density distance in the objective space of the Pareto optimal solution to save the storage space.


#### 3.2.2. Archive Maintenance Operator

A multiobjective PSO algorithm does not produce a unique solution but a set of Pareto optimal solutions at the end of each iteration; therefore an archive is used to save these Pareto optimal solutions and the members in the archive become the final solution set when the iteration stops. To adapt to the limited storage space of a WSN node, the members in an archive are limited by deleting some of the members when the maximum capacity is reached. Consequently, a space will be maintained for the new solutions entering into the archive.However, due to nondominated property of Pareto optimal solutions, namely, there is no difference between the solutions, a concept of intensive distance is introduced to evaluate the solution quality. Generally the point (solution) in a sparse area which has bigger intensive distance is better than the point in an intensive area in the objective space [15].Definition 1.
Given setS is the set of Pareto optimal solutions in the archive and xi∈S is a Pareto optimal solution, then the intensive distance Disi of xi is defined as the average value of the minimum distance disi1 and the second minimum distance disi2 between xi and other Pareto optimal solutions xj∈S in the archive. disi1, disi2, and Disi are computed as(10)disi1=min⁡Dij∣xi∈S,xj∈S,j=1,2,…,c,j≠i,disi2=min⁡Dij∣Dij>disi1,xi∈S,xj∈S,kkkkDij∣Dij>disi1,xi∈S,xj∈S,j=1,2,…,c,j≠i,Disi=disi1+disi22,where Dij=∑k=12(fk(xi)-fk(xj))2 is the objective constraint distance between xi and xj and fk(k=1,2) is the objective function, c is the number of solutions.The intensive distances of Pareto optimal solutions are sorted and the smaller ones are deleted in order to limit the number of members in the archive.It is ensured that the members in the archive can be limited in the maximum capacity by the archive maintenance operator, which avoids the nondominated solutions increasing infinitely to reduce the efficiency along with the evolution. At the same time, the most intense individual is deleted, and the uniform distribution of the Pareto front is ensured by saving lots of scattered individuals.


#### 3.2.3. Global Optimum Selection Operator

In the traditional single objective PSO algorithm, it is tolerable to use the optimal solution with the best fitness as the global optimumgbest because the gbest of every particle is the same. However, in multiobjective PSO the population generates more than one nondominated gbest leading difference among some particle global optimums, which results to necessarily choose the appropriate global optimum. Based on the intensive distance, the global optimum is selected for each particle by adopting the proportion of selection.Definition 2.
Given that the number of Pareto optimal solutions in the archive of the current iteration isc with c≤ArcMax, a proportion of selection ξi of a Pareto optimal solution xi∈S is defined as the rate of its intensive distance to the sum of intensive distances in the archive according to(11)ξi=Disi∑k=1cDisk,i=1,…,c.Formula (11) implies that the larger intensive distance a Pareto optimal solution has, the bigger proportion of selection it has; therefore it has a bigger proportion to be selected as the global optimum.


#### 3.2.4. The Pseudo Code of the MOPSOLA

The main components of MOPSOLA, including multiobjective function calculation, individual optimal selection, maintenance of archive, global optimal selection, and velocity and localization update, are described as function MopsoFuc with pseudocode in Algorithm1. Where the node is the class of node information with four members of node.x, node.y, node.id, and node.anchorflag corresponding to the x_coordinate, y_coordinate, id number, and anchor flag of a node. t is the current iteration time and tmax⁡ is the maximum iteration time. The other variables have the consistent meaning with the same named variables aforementioned.Algorithm 1:The proposed MOPSOLA in pseudocode.
S = MopsoFuc(node, n, m, R)
node: class of node information
n: total number of nodes
m: anchor nodes
R: node communication radius
S: set of Pareto optimal solutions in the archive
(1) Initialize each parameter, ω=0.7298, c1=c2=1.4962, ArcMax = 10
(2) Initialize h and v for each particle randomly then pbest←particle
(3) While t≤tmax⁡  Do
//Step 1.Multi-objective Function Calculation
(4)   For each particle Do
(5)    Compute particle.f1 and particle.f2 using class node
(6)   End
//Step 2.Individual Optimal Selection
(7)   For each pbest Do
(8)     Compute pbest.f1 and pbest.f2 using class node
(9)     If pbest≺particle
(10)      pbest←pbest
(11)    ElseIf particle≺pbest
(12)      pbest←particle
(13)    Else a←rand
(14)     If a≤ 0.5 then pbest←pbest
(15)     Else pbest←particle
(16)  End
//Step 3.Maintenance of Archive
(17)  While Receive pbest Do
(18)    TempArc←Archive∪pbest
(19)    Delete repetitive solution in TempArc
(20)    For every member in TempArc Do
(21)     IF dominated then Delete
(22)    End
(23)    c←number of TempArc
(24)    IF c≤ArcMax
(25)      Archive←TempArc
(26)    Else Compute Dis of TempArc
(27)      Descending sort of TempArc
(28)      Archive←TempArc
(29)  End
//Step 4.Global Optimal Selection
(30)  For every member of Archive Do
(31)    Compute Dis;
(32)    Compute ξi;
(33)  End
(34)  For every particle Do
(35)    Using roulette wheel to choose gbest according to ξi;
(36)  End
//Step 5.Velocity and Localization Update
(37)  v(t+1)←ωvt+c1r1pbest-ht+c2r2(gbest-ht)
(38)  h(t+1)←h(t)+v(t+1)
(39) End (While)
(40) S←Archive


## 3.1. Mathematical Description of MOPSOLA

The optimal solution of multiobjective optimization issues is to find the Pareto optimal solution [14]. Multiobjective optimization issue with u-dimensional decision vectors and v objectives is denoted by (7)MinmizeFx=f1x,f2x,…,fvxs.t.x∈xL,xU,where x=(x1,x2,…,xu)∈X∈Ru and F=(f1,f2,…,fv)∈Y∈RV. x is called the decision vector belonging to the u-dimensional decision space X, which is corresponding to u-particles in PSO. xL and xU are lower and upper bound constraints of the particle range, respectively. F is the objective vector belonging to the v-dimensional objective space Y. The objective function F(x) defines mapping functions from the decision space to the objective space. The set of all the particles meeting the constraints forms the decision space feasible set Ω={x∈Ru∣x∈[xL,xU]}.Some concepts related with MOPSOLA are described as follows.(i)
For two feasible solutionsxa, xb∈Ω in the processing of PSO, if, ∀i=1,2,…,v, fixb≤fixa∧∃j=1,2,…,v, fj(xb)<fj(xa), then call xb dominate xa, denoted by xb≺xa, and keep xb as optimization results.(ii)
The Pareto optimal solutionx* is the decision vector which satisfies ¬∃x∈Ω:x≺x*.(iii)
S={x∈Ω∣¬∃x′∈Ω,fjx′≤fjx,j=1,2,…,v} constructs the set of Pareto optimal solution obtained from all of the Pareto optimal solutions.(iv)
Fx={Fx*=(f1(x*),f2(x*),…,fv(x*))∣x*∈S} forms the Pareto front consisting of the values of objective functions corresponding to the Pareto optimal set.(v)
The purpose of optimization is to find the Pareto optimal solution.In MOPSOLA, model the estimated coordinates ofn-m unknown nodes as the decision vectors, and the two objective functions defined by (3)–(5) consist of the objective function F(x). Therefore, from formulas (3)–(5) and (7), MOPSOLA can be formulated in the optimum mathematical form as(8)MinmizeFx=f1x^i,y^i,f2x^i,y^is.t.x^i,y^i∈x^L,y^L,x^U,y^Ukkkkkkkklli=m+1,m+2,…,n,where decision vectors x=(x^i,y^i)(i=m+1,m+2,…,n) are the estimated coordinates corresponding to particles in PSO, (x^L,y^L) and (x^U,y^U) are the lower and upper bound constraint values, f1 is the objective function of the space distance constraint, and f2 is the objective function of the geometric topology constraint. Therefore the decision space is u=n-m dimension and the objective space is v=2 dimension; that is, the coordinates of unknown nodes are u=n-m particles, f1 and f2 are the v=2 objective functions.Obtaining the multiobjective Pareto optimal solution is the ultimate goal of building a multiobjective optimal model for localization issues, which meets both the space distance constraint and the geometric topology constraint. Therefore the main essence of MOPSOLA can be described as determining the dominant relationship according to the decision space feasible setΩ and the Pareto front Fx*={(f1(x^i*,y^i*),f2(x^i*,y^i*))∣xi*=(x^i*,y^i*)∈S}, i=m+1,m+2,…,n, saving Pareto optimal solution set S in an archive and updating the position and the velocity of multiobjective PSO.


## 3.2. Describing of MOPSOLA

### 3.2.1. Overall Framework

Shown as Figure1, the framework of the proposed multiobjective PSO algorithm includes some key operators such as maintenance of archive, global optimum selection, and the velocity and localization update. The particle population relies on an archive to save Pareto optimal solutions during the iterative process and selecting the global optimum from these solutions, which is the key point that the multiobjective PSO is different from the traditional single objective localization.Figure 1
Overall framework of the multiobjective PSO.Therefore, the localization issue is modeled as a multiobjective optimization model in MOPSOLA, and two operators, which are the dynamic maintenance operator for the archive and the global optimum selection operator based on proportion of selection, are designed to be suitable for the limited energy and the poor computing power of WSN nodes.(i)
In the multiobjective function calculation level, functions as formulas (3)–(5) are calculated according to all particles, that is, all estimated nodes’ coordinates.(ii)
In the individual optimal selection level, the personal optimum selection operator works. Based on the concept of Pareto optimality, thepbest of each particle is chosen between the particle’s current location and its historical pbest dynamically.(iii)
In the global optimal selection level, the global optimum selection operator works. The proportion of selection is set for each Pareto optimal solution based on intensive distance, and a global optimum for each particle is selected by proportion of selection.(iv)
In the velocity and localization update level, the position and velocity update operator works for all individual particles. The update process is similar to the traditional single objective PSO as(9)vit+1=ωvit+c1r1pbesti-hit+c2r2gbest-hit,hit+1=hit+vit+1,i=m+1,m+2,…,n,wherevi is the velocity of the ith particle, hi=(x^i,y^i) is the estimated coordinates of the ith particle vector, pbesti is the best solution for the ith particle, gbest is the best solution for the population, ω is the inertia weight, c1 and c2 are constants, and t is the iteration time.(v)
In the maintenance of archive level, the archive maintenance operator works. The maximum capacity of archive is set asArcMax and the archive is dynamically updated according to the density distance in the objective space of the Pareto optimal solution to save the storage space.


### 3.2.2. Archive Maintenance Operator

A multiobjective PSO algorithm does not produce a unique solution but a set of Pareto optimal solutions at the end of each iteration; therefore an archive is used to save these Pareto optimal solutions and the members in the archive become the final solution set when the iteration stops. To adapt to the limited storage space of a WSN node, the members in an archive are limited by deleting some of the members when the maximum capacity is reached. Consequently, a space will be maintained for the new solutions entering into the archive.However, due to nondominated property of Pareto optimal solutions, namely, there is no difference between the solutions, a concept of intensive distance is introduced to evaluate the solution quality. Generally the point (solution) in a sparse area which has bigger intensive distance is better than the point in an intensive area in the objective space [15].Definition 1.
Given setS is the set of Pareto optimal solutions in the archive and xi∈S is a Pareto optimal solution, then the intensive distance Disi of xi is defined as the average value of the minimum distance disi1 and the second minimum distance disi2 between xi and other Pareto optimal solutions xj∈S in the archive. disi1, disi2, and Disi are computed as(10)disi1=min⁡Dij∣xi∈S,xj∈S,j=1,2,…,c,j≠i,disi2=min⁡Dij∣Dij>disi1,xi∈S,xj∈S,kkkkDij∣Dij>disi1,xi∈S,xj∈S,j=1,2,…,c,j≠i,Disi=disi1+disi22,where Dij=∑k=12(fk(xi)-fk(xj))2 is the objective constraint distance between xi and xj and fk(k=1,2) is the objective function, c is the number of solutions.The intensive distances of Pareto optimal solutions are sorted and the smaller ones are deleted in order to limit the number of members in the archive.It is ensured that the members in the archive can be limited in the maximum capacity by the archive maintenance operator, which avoids the nondominated solutions increasing infinitely to reduce the efficiency along with the evolution. At the same time, the most intense individual is deleted, and the uniform distribution of the Pareto front is ensured by saving lots of scattered individuals.


### 3.2.3. Global Optimum Selection Operator

In the traditional single objective PSO algorithm, it is tolerable to use the optimal solution with the best fitness as the global optimumgbest because the gbest of every particle is the same. However, in multiobjective PSO the population generates more than one nondominated gbest leading difference among some particle global optimums, which results to necessarily choose the appropriate global optimum. Based on the intensive distance, the global optimum is selected for each particle by adopting the proportion of selection.Definition 2.
Given that the number of Pareto optimal solutions in the archive of the current iteration isc with c≤ArcMax, a proportion of selection ξi of a Pareto optimal solution xi∈S is defined as the rate of its intensive distance to the sum of intensive distances in the archive according to(11)ξi=Disi∑k=1cDisk,i=1,…,c.Formula (11) implies that the larger intensive distance a Pareto optimal solution has, the bigger proportion of selection it has; therefore it has a bigger proportion to be selected as the global optimum.


### 3.2.4. The Pseudo Code of the MOPSOLA

The main components of MOPSOLA, including multiobjective function calculation, individual optimal selection, maintenance of archive, global optimal selection, and velocity and localization update, are described as function MopsoFuc with pseudocode in Algorithm1. Where the node is the class of node information with four members of node.x, node.y, node.id, and node.anchorflag corresponding to the x_coordinate, y_coordinate, id number, and anchor flag of a node. t is the current iteration time and tmax⁡ is the maximum iteration time. The other variables have the consistent meaning with the same named variables aforementioned.Algorithm 1:The proposed MOPSOLA in pseudocode.
S = MopsoFuc(node, n, m, R)
node: class of node information
n: total number of nodes
m: anchor nodes
R: node communication radius
S: set of Pareto optimal solutions in the archive
(1) Initialize each parameter, ω=0.7298, c1=c2=1.4962, ArcMax = 10
(2) Initialize h and v for each particle randomly then pbest←particle
(3) While t≤tmax⁡  Do
//Step 1.Multi-objective Function Calculation
(4)   For each particle Do
(5)    Compute particle.f1 and particle.f2 using class node
(6)   End
//Step 2.Individual Optimal Selection
(7)   For each pbest Do
(8)     Compute pbest.f1 and pbest.f2 using class node
(9)     If pbest≺particle
(10)      pbest←pbest
(11)    ElseIf particle≺pbest
(12)      pbest←particle
(13)    Else a←rand
(14)     If a≤ 0.5 then pbest←pbest
(15)     Else pbest←particle
(16)  End
//Step 3.Maintenance of Archive
(17)  While Receive pbest Do
(18)    TempArc←Archive∪pbest
(19)    Delete repetitive solution in TempArc
(20)    For every member in TempArc Do
(21)     IF dominated then Delete
(22)    End
(23)    c←number of TempArc
(24)    IF c≤ArcMax
(25)      Archive←TempArc
(26)    Else Compute Dis of TempArc
(27)      Descending sort of TempArc
(28)      Archive←TempArc
(29)  End
//Step 4.Global Optimal Selection
(30)  For every member of Archive Do
(31)    Compute Dis;
(32)    Compute ξi;
(33)  End
(34)  For every particle Do
(35)    Using roulette wheel to choose gbest according to ξi;
(36)  End
//Step 5.Velocity and Localization Update
(37)  v(t+1)←ωvt+c1r1pbest-ht+c2r2(gbest-ht)
(38)  h(t+1)←h(t)+v(t+1)
(39) End (While)
(40) S←Archive


## 3.2.1. Overall Framework

Shown as Figure1, the framework of the proposed multiobjective PSO algorithm includes some key operators such as maintenance of archive, global optimum selection, and the velocity and localization update. The particle population relies on an archive to save Pareto optimal solutions during the iterative process and selecting the global optimum from these solutions, which is the key point that the multiobjective PSO is different from the traditional single objective localization.Figure 1
Overall framework of the multiobjective PSO.Therefore, the localization issue is modeled as a multiobjective optimization model in MOPSOLA, and two operators, which are the dynamic maintenance operator for the archive and the global optimum selection operator based on proportion of selection, are designed to be suitable for the limited energy and the poor computing power of WSN nodes.(i)
In the multiobjective function calculation level, functions as formulas (3)–(5) are calculated according to all particles, that is, all estimated nodes’ coordinates.(ii)
In the individual optimal selection level, the personal optimum selection operator works. Based on the concept of Pareto optimality, thepbest of each particle is chosen between the particle’s current location and its historical pbest dynamically.(iii)
In the global optimal selection level, the global optimum selection operator works. The proportion of selection is set for each Pareto optimal solution based on intensive distance, and a global optimum for each particle is selected by proportion of selection.(iv)
In the velocity and localization update level, the position and velocity update operator works for all individual particles. The update process is similar to the traditional single objective PSO as(9)vit+1=ωvit+c1r1pbesti-hit+c2r2gbest-hit,hit+1=hit+vit+1,i=m+1,m+2,…,n,wherevi is the velocity of the ith particle, hi=(x^i,y^i) is the estimated coordinates of the ith particle vector, pbesti is the best solution for the ith particle, gbest is the best solution for the population, ω is the inertia weight, c1 and c2 are constants, and t is the iteration time.(v)
In the maintenance of archive level, the archive maintenance operator works. The maximum capacity of archive is set asArcMax and the archive is dynamically updated according to the density distance in the objective space of the Pareto optimal solution to save the storage space.


## 3.2.2. Archive Maintenance Operator

A multiobjective PSO algorithm does not produce a unique solution but a set of Pareto optimal solutions at the end of each iteration; therefore an archive is used to save these Pareto optimal solutions and the members in the archive become the final solution set when the iteration stops. To adapt to the limited storage space of a WSN node, the members in an archive are limited by deleting some of the members when the maximum capacity is reached. Consequently, a space will be maintained for the new solutions entering into the archive.However, due to nondominated property of Pareto optimal solutions, namely, there is no difference between the solutions, a concept of intensive distance is introduced to evaluate the solution quality. Generally the point (solution) in a sparse area which has bigger intensive distance is better than the point in an intensive area in the objective space [15].Definition 1.
Given setS is the set of Pareto optimal solutions in the archive and xi∈S is a Pareto optimal solution, then the intensive distance Disi of xi is defined as the average value of the minimum distance disi1 and the second minimum distance disi2 between xi and other Pareto optimal solutions xj∈S in the archive. disi1, disi2, and Disi are computed as(10)disi1=min⁡Dij∣xi∈S,xj∈S,j=1,2,…,c,j≠i,disi2=min⁡Dij∣Dij>disi1,xi∈S,xj∈S,kkkkDij∣Dij>disi1,xi∈S,xj∈S,j=1,2,…,c,j≠i,Disi=disi1+disi22,where Dij=∑k=12(fk(xi)-fk(xj))2 is the objective constraint distance between xi and xj and fk(k=1,2) is the objective function, c is the number of solutions.The intensive distances of Pareto optimal solutions are sorted and the smaller ones are deleted in order to limit the number of members in the archive.It is ensured that the members in the archive can be limited in the maximum capacity by the archive maintenance operator, which avoids the nondominated solutions increasing infinitely to reduce the efficiency along with the evolution. At the same time, the most intense individual is deleted, and the uniform distribution of the Pareto front is ensured by saving lots of scattered individuals.


## 3.2.3. Global Optimum Selection Operator

In the traditional single objective PSO algorithm, it is tolerable to use the optimal solution with the best fitness as the global optimumgbest because the gbest of every particle is the same. However, in multiobjective PSO the population generates more than one nondominated gbest leading difference among some particle global optimums, which results to necessarily choose the appropriate global optimum. Based on the intensive distance, the global optimum is selected for each particle by adopting the proportion of selection.Definition 2.
Given that the number of Pareto optimal solutions in the archive of the current iteration isc with c≤ArcMax, a proportion of selection ξi of a Pareto optimal solution xi∈S is defined as the rate of its intensive distance to the sum of intensive distances in the archive according to(11)ξi=Disi∑k=1cDisk,i=1,…,c.Formula (11) implies that the larger intensive distance a Pareto optimal solution has, the bigger proportion of selection it has; therefore it has a bigger proportion to be selected as the global optimum.


## 3.2.4. The Pseudo Code of the MOPSOLA

The main components of MOPSOLA, including multiobjective function calculation, individual optimal selection, maintenance of archive, global optimal selection, and velocity and localization update, are described as function MopsoFuc with pseudocode in Algorithm1. Where the node is the class of node information with four members of node.x, node.y, node.id, and node.anchorflag corresponding to the x_coordinate, y_coordinate, id number, and anchor flag of a node. t is the current iteration time and tmax⁡ is the maximum iteration time. The other variables have the consistent meaning with the same named variables aforementioned.Algorithm 1:The proposed MOPSOLA in pseudocode.
S = MopsoFuc(node, n, m, R)
node: class of node information
n: total number of nodes
m: anchor nodes
R: node communication radius
S: set of Pareto optimal solutions in the archive
(1) Initialize each parameter, ω=0.7298, c1=c2=1.4962, ArcMax = 10
(2) Initialize h and v for each particle randomly then pbest←particle
(3) While t≤tmax⁡  Do
//Step 1.Multi-objective Function Calculation
(4)   For each particle Do
(5)    Compute particle.f1 and particle.f2 using class node
(6)   End
//Step 2.Individual Optimal Selection
(7)   For each pbest Do
(8)     Compute pbest.f1 and pbest.f2 using class node
(9)     If pbest≺particle
(10)      pbest←pbest
(11)    ElseIf particle≺pbest
(12)      pbest←particle
(13)    Else a←rand
(14)     If a≤ 0.5 then pbest←pbest
(15)     Else pbest←particle
(16)  End
//Step 3.Maintenance of Archive
(17)  While Receive pbest Do
(18)    TempArc←Archive∪pbest
(19)    Delete repetitive solution in TempArc
(20)    For every member in TempArc Do
(21)     IF dominated then Delete
(22)    End
(23)    c←number of TempArc
(24)    IF c≤ArcMax
(25)      Archive←TempArc
(26)    Else Compute Dis of TempArc
(27)      Descending sort of TempArc
(28)      Archive←TempArc
(29)  End
//Step 4.Global Optimal Selection
(30)  For every member of Archive Do
(31)    Compute Dis;
(32)    Compute ξi;
(33)  End
(34)  For every particle Do
(35)    Using roulette wheel to choose gbest according to ξi;
(36)  End
//Step 5.Velocity and Localization Update
(37)  v(t+1)←ωvt+c1r1pbest-ht+c2r2(gbest-ht)
(38)  h(t+1)←h(t)+v(t+1)
(39) End (While)
(40) S←Archive


## 4. Simulations and Analysis

To validate the performance of the MOPSOLA, the simulations have been done to test MOPSOLA and the other two algorithms, the traditional PSO and PASE [7], in Matlab 2010b. The simulations have been done using MOPSOLA with objective functions f1 and f2, and they also have been done using PSO with objective function f1 and using PASE [7] with objective functions f1 and f2.


### 4.1. The Simulation and Evaluation Parameters

#### 4.1.1. The Simulation Parameters

Totaln nodes are randomly deployed in 100 m × 100 m area with m anchor nodes being randomly generated from these nodes. Assuming that the RSSI ranging error eij follows a Gaussian distribution with a zero mean and variance σ2, σ2=β2rij2, β=0.1. The maximum capacity of the archive ArcMax is 10 and the max iteration time tmax⁡ is 1000.


#### 4.1.2. The Localization Errors

The localization error is generally related to the node communication radius. Based on the communication radius, two kinds of localization errors are defined to evaluate the localization performance of the proposed algorithm. One is the single localization errorSingleError of an unknown node defined by formula (12), which is used to evaluate the performance of each node being estimated. The other is the average localization error AverError of the network defined as formula (13), which is further applied to evaluate the performance of all the nodes being estimated:(12)SingleError=x^i-xi2+y^i-yi2R×100%,(13)AverError=∑i=1n-mx^i-xi2+y^i-yi2(n-m)×R×100%.


### 4.2. The Efficiency of the Tow Objective Functions

#### 4.2.1. The Convergence Rate

Figure2 is the comparison of objective function f1 about the convergence rate between MOPSOLA and PAES. MOPSOLA and PAES start to converge at the 400th iteration and 700th iteration, respectively. The result shows that MOPSOLA retains more outstanding individuals to accelerate the algorithm convergence by avoiding the affection of selection and mutation operation on the next generation and adopting dynamic maintenance of archive combined with selecting the optimum by proportion of selection for maintaining much more outstanding individuals.Figure 2
The comparison of convergence rate between MOPSOLA and PAES.


#### 4.2.2. The Localization Accuracy

The single localization errors of 80 unknown nodes has been simulated to evaluate the localization accuracy under the condition of 20% anchor nodes by using MOPSOLA and PSO algorithm.(i)
The simulation results show that the maximum and the minimum single localization error are 81.13% and 1.52%, respectively, in MOPSOLA compared to 94.36% and 5.52%, respectively, in PSO.(ii)
The ranges ofSingleError are counted to further evaluate the accuracy shown in Table 1. It can been seen that 24 nodes’ single localization errors fell into 0~5% in MOPSOLA compared to 10 nodes’ in PSO, and 5 nodes’ single localization errors are over 30% in MOPSOLA compared to 31 nodes’ in PSO.(iii)
From the comparison, it is obvious that the single localization errors by using MOPSOLA are lower than those by using PSO. This is because the geometric topology constraint is limited in a reasonable topology by the objective functionf2, which decreases the inaccuracy of the localization.Table 1
The distribution ofSingleError ranges.
S
i
n
g
l
e
E
r
r
o
r
0~5%
5%~15%
15%~30%
30%~45%
45%~60%
>60%
PSO
10
26
13
7
14
10
MOPSOLA
24
34
17
3
0
2


### 4.3. The Robust Performance of the MOPSOLA

The simulations focusing on the average localization errors have been done to evaluate the robustness of the MOPSOLA in case of different situations with varying nodes density, anchor nodes, and network connectivity.


#### 4.3.1. The Effect of the Network Nodes Density

Table2 and Figure 3 report the average localization errors, measured under the condition of changing the network nodes density and the total number of nodes, while holding on the anchor node proportion as 20% and the communication radius R=25 m.(i)
All the average localization errors of three methods reduce as the nodes increasing, and the number of nodes does little effect on the errors when it is over 100. It is obvious that the errors created by using PAES and MOPSOLA are lower than the errors created by using PSO due to the geometric topology constraint being considered by the first two methods.(ii)
Furthermore, the MOPSOLA algorithm has better performance than PAES due to the estimation accuracy being affected by the selection and mutation operators in PAES, and the average error reduces 4.84%, 5.12%, 3.47%, 1.50%, 1.09%, and 2.45%, respectively, compared to PAES with node number of 60, 80, 100, 120, 140, and 160.(iii)
The further analysis shows that although the network topology changes following the nodes increasing or decreasing, the MOPSOLA is robustness in terms of having the average localization errors lower than 15% with nodes over 80.Table 2
Localization errors with different node number.
Total number of nodes
60
80
100
120
140
160
PSO
37.20%
26.43%
21.02%
19.58%
19.39%
18.38%
PAES
22.52%
21.59%
15.65%
13.77%
12.56%
11.70%
MOPSOLA
17.68%
14.47%
12.15%
12.27%
11.47%
9.25%Figure 3
Localization errors with different node number.


#### 4.3.2. The Effect of the Proportion of Anchor Nodes

Table3 and Figure 4 show the relationship between the average localization errors and the anchor node proportion while holding on the total number of nodes n=100 and communication radius R=25 m but with different anchor node proportion.(i)
All the average localization errors decrease as the anchor node proportion increases due to the increasing of anchor nodes around unknown nodes resulting in localization accuracy being improved.(ii)
MOPSOLA and PAES [7] have better performance in localization accuracy than the traditional PSO localization algorithm with the same anchor node proportion due to the two objective functions being considered in MOPSOLA and PAES compared to only one objective function being considered in PSO without the topology constraint. For example, the average localization error in MOPSOLA reduces 15.09% and 8.39% compared with the traditional PSO method, respectively, under the condition of 10% and 20% anchor node proportion.(iii)
MOPSOLA has slightly higher localization accuracy than PAES under the condition of the same anchor node proportions. Compared with PAES, MOPSOLA reduces the average localization error 1.95% and 0.05%, respectively under the condition of 10% and 20% anchor node proportion.(iv)
MOPSOLA is robust with no performance declining in terms of the average localization errors being lower than 15% when the anchor node proportion is over 10%. These results prove that varying the anchor node proportion will not affect the robust performance of MOPSOLA.Table 3
Localization errors with different anchor node proportion.
Anchor node proportion
5%
10%
15%
20%
20%
30%
PSO
36.57%
28.33%
22.19%
19.94%
18.17%
17.77%
PAES
18.47%
15.19%
12.88%
12.10%
11.87%
11.02%
MOPSOLA
15.57%
13.24%
12.17%
11.55%
10.99%
10.54%Figure 4
Localization errors with different anchor node proportion.


#### 4.3.3. The Effect of the Network Connectivity

Table4 and Figure 5 show the relationship between the average localization errors and the network connectivity while holding the total number nodes n=100 and 20% anchor node proportion, but with different communication radius R to change the network connectivity.(i)
The results show that the localization accuracy of each algorithm has the trend of rising as the increasing of the node communication radius. This is because the increasing of the communication radius will enable the unknown nodes to communicate with more neighbor nodes and further improve the search performance of intelligent optimization algorithms.(ii)
MOPSOLA can keep the average localization errors declining when the node communication radius reaches to 30 m, while the localization error using PAES begins to rising. The reason for this phenomenon is caused by rising of number of the first-level neighbor and the second-level neighbor [7] resulting from the bigger communication radios, which further leads to increasing of the ranging error of two classes unknown nodes defined in PAES.(iii)
The MOPSOLA is robust with no obvious performance decline in terms of the average localization errors kept lower than 15% when the node communication radius is over 20 m.Table 4
Localization errors with different network connectivity in different algorithms.
Communication radiusR
10
15
20
25
30
35
PSO
35.73%
30.94%
24.59%
18.94%
19.76%
17.88%
PAES
29.57%
21.11%
17.20%
12.79%
13.31%
14.01%
MOPSOLA
21.80%
18.36%
14.18%
12.55%
11.25%
10.52%Figure 5
Localization errors with different network connectivity in different algorithms.The simulation results analyzed in this section have proved that, because the model of multiobjective localization considers the influence of geometric topology constraintf2, some localization results which violate the constraint will be modified to further improve the localization accuracy. Furthermore, the optimum by proportion of selection can obtain closer result to the real localization and further improve the localization accuracy.


### 4.4. The Time Complexity of the Algorithm

Table5 shows the time complexity of three algorithms with unknown nodes number M=n-m, the size of particle swarm N, iterations number tmax⁡, and archive size ArcMax. The time complexity of MOPSOLA is obviously higher than that of PSO and PAES.Table 5
The time complexity.
Algorithm
Time complexity
PSO
O
t
max
⁡
N
M
PAES
O
t
max
⁡
M
·
A
r
c
M
a
x
MOPSOLA
O
t
max
⁡
N
M
+
t
max
⁡
M
N
+
A
r
c
M
a
x
2Table6 shows the operation times of three algorithms with total nodes n=100, anchor nodes m=20, and communication radius R=25. It can more clearly be seen that the time complexity of MOPSOLA is higher than that of the two compared algorithms.Table 6
Iterative operation time of different algorithms.
Iterations number
1
10
100
1000
PSO
0.338 s
2.192 s
30.492 s
305.680 s
PAES
0.106 s
1.170 s
11.434 s
115.965 s
MOPSOLA
2.723 s
65.396 s
559.081 s
6622.944 sThe reason is that the two main operating levels of archive maintenance operator and global optimum selection operator in MOPSOLA will cost more time to repeatedly calculate and compare the values of two objective functions and delete the dominated solutions to obtain the elitism archived strategy, which also result in higher time complexity.


## 4.1. The Simulation and Evaluation Parameters

### 4.1.1. The Simulation Parameters

Totaln nodes are randomly deployed in 100 m × 100 m area with m anchor nodes being randomly generated from these nodes. Assuming that the RSSI ranging error eij follows a Gaussian distribution with a zero mean and variance σ2, σ2=β2rij2, β=0.1. The maximum capacity of the archive ArcMax is 10 and the max iteration time tmax⁡ is 1000.


### 4.1.2. The Localization Errors

The localization error is generally related to the node communication radius. Based on the communication radius, two kinds of localization errors are defined to evaluate the localization performance of the proposed algorithm. One is the single localization errorSingleError of an unknown node defined by formula (12), which is used to evaluate the performance of each node being estimated. The other is the average localization error AverError of the network defined as formula (13), which is further applied to evaluate the performance of all the nodes being estimated:(12)SingleError=x^i-xi2+y^i-yi2R×100%,(13)AverError=∑i=1n-mx^i-xi2+y^i-yi2(n-m)×R×100%.


## 4.1.1. The Simulation Parameters

Totaln nodes are randomly deployed in 100 m × 100 m area with m anchor nodes being randomly generated from these nodes. Assuming that the RSSI ranging error eij follows a Gaussian distribution with a zero mean and variance σ2, σ2=β2rij2, β=0.1. The maximum capacity of the archive ArcMax is 10 and the max iteration time tmax⁡ is 1000.


## 4.1.2. The Localization Errors

The localization error is generally related to the node communication radius. Based on the communication radius, two kinds of localization errors are defined to evaluate the localization performance of the proposed algorithm. One is the single localization errorSingleError of an unknown node defined by formula (12), which is used to evaluate the performance of each node being estimated. The other is the average localization error AverError of the network defined as formula (13), which is further applied to evaluate the performance of all the nodes being estimated:(12)SingleError=x^i-xi2+y^i-yi2R×100%,(13)AverError=∑i=1n-mx^i-xi2+y^i-yi2(n-m)×R×100%.


## 4.2. The Efficiency of the Tow Objective Functions

### 4.2.1. The Convergence Rate

Figure2 is the comparison of objective function f1 about the convergence rate between MOPSOLA and PAES. MOPSOLA and PAES start to converge at the 400th iteration and 700th iteration, respectively. The result shows that MOPSOLA retains more outstanding individuals to accelerate the algorithm convergence by avoiding the affection of selection and mutation operation on the next generation and adopting dynamic maintenance of archive combined with selecting the optimum by proportion of selection for maintaining much more outstanding individuals.Figure 2
The comparison of convergence rate between MOPSOLA and PAES.


### 4.2.2. The Localization Accuracy

The single localization errors of 80 unknown nodes has been simulated to evaluate the localization accuracy under the condition of 20% anchor nodes by using MOPSOLA and PSO algorithm.(i)
The simulation results show that the maximum and the minimum single localization error are 81.13% and 1.52%, respectively, in MOPSOLA compared to 94.36% and 5.52%, respectively, in PSO.(ii)
The ranges ofSingleError are counted to further evaluate the accuracy shown in Table 1. It can been seen that 24 nodes’ single localization errors fell into 0~5% in MOPSOLA compared to 10 nodes’ in PSO, and 5 nodes’ single localization errors are over 30% in MOPSOLA compared to 31 nodes’ in PSO.(iii)
From the comparison, it is obvious that the single localization errors by using MOPSOLA are lower than those by using PSO. This is because the geometric topology constraint is limited in a reasonable topology by the objective functionf2, which decreases the inaccuracy of the localization.Table 1
The distribution ofSingleError ranges.
S
i
n
g
l
e
E
r
r
o
r
0~5%
5%~15%
15%~30%
30%~45%
45%~60%
>60%
PSO
10
26
13
7
14
10
MOPSOLA
24
34
17
3
0
2


## 4.2.1. The Convergence Rate

Figure2 is the comparison of objective function f1 about the convergence rate between MOPSOLA and PAES. MOPSOLA and PAES start to converge at the 400th iteration and 700th iteration, respectively. The result shows that MOPSOLA retains more outstanding individuals to accelerate the algorithm convergence by avoiding the affection of selection and mutation operation on the next generation and adopting dynamic maintenance of archive combined with selecting the optimum by proportion of selection for maintaining much more outstanding individuals.Figure 2
The comparison of convergence rate between MOPSOLA and PAES.


## 4.2.2. The Localization Accuracy

The single localization errors of 80 unknown nodes has been simulated to evaluate the localization accuracy under the condition of 20% anchor nodes by using MOPSOLA and PSO algorithm.(i)
The simulation results show that the maximum and the minimum single localization error are 81.13% and 1.52%, respectively, in MOPSOLA compared to 94.36% and 5.52%, respectively, in PSO.(ii)
The ranges ofSingleError are counted to further evaluate the accuracy shown in Table 1. It can been seen that 24 nodes’ single localization errors fell into 0~5% in MOPSOLA compared to 10 nodes’ in PSO, and 5 nodes’ single localization errors are over 30% in MOPSOLA compared to 31 nodes’ in PSO.(iii)
From the comparison, it is obvious that the single localization errors by using MOPSOLA are lower than those by using PSO. This is because the geometric topology constraint is limited in a reasonable topology by the objective functionf2, which decreases the inaccuracy of the localization.Table 1
The distribution ofSingleError ranges.
S
i
n
g
l
e
E
r
r
o
r
0~5%
5%~15%
15%~30%
30%~45%
45%~60%
>60%
PSO
10
26
13
7
14
10
MOPSOLA
24
34
17
3
0
2


## 4.3. The Robust Performance of the MOPSOLA

The simulations focusing on the average localization errors have been done to evaluate the robustness of the MOPSOLA in case of different situations with varying nodes density, anchor nodes, and network connectivity.


### 4.3.1. The Effect of the Network Nodes Density

Table2 and Figure 3 report the average localization errors, measured under the condition of changing the network nodes density and the total number of nodes, while holding on the anchor node proportion as 20% and the communication radius R=25 m.(i)
All the average localization errors of three methods reduce as the nodes increasing, and the number of nodes does little effect on the errors when it is over 100. It is obvious that the errors created by using PAES and MOPSOLA are lower than the errors created by using PSO due to the geometric topology constraint being considered by the first two methods.(ii)
Furthermore, the MOPSOLA algorithm has better performance than PAES due to the estimation accuracy being affected by the selection and mutation operators in PAES, and the average error reduces 4.84%, 5.12%, 3.47%, 1.50%, 1.09%, and 2.45%, respectively, compared to PAES with node number of 60, 80, 100, 120, 140, and 160.(iii)
The further analysis shows that although the network topology changes following the nodes increasing or decreasing, the MOPSOLA is robustness in terms of having the average localization errors lower than 15% with nodes over 80.Table 2
Localization errors with different node number.
Total number of nodes
60
80
100
120
140
160
PSO
37.20%
26.43%
21.02%
19.58%
19.39%
18.38%
PAES
22.52%
21.59%
15.65%
13.77%
12.56%
11.70%
MOPSOLA
17.68%
14.47%
12.15%
12.27%
11.47%
9.25%Figure 3
Localization errors with different node number.


### 4.3.2. The Effect of the Proportion of Anchor Nodes

Table3 and Figure 4 show the relationship between the average localization errors and the anchor node proportion while holding on the total number of nodes n=100 and communication radius R=25 m but with different anchor node proportion.(i)
All the average localization errors decrease as the anchor node proportion increases due to the increasing of anchor nodes around unknown nodes resulting in localization accuracy being improved.(ii)
MOPSOLA and PAES [7] have better performance in localization accuracy than the traditional PSO localization algorithm with the same anchor node proportion due to the two objective functions being considered in MOPSOLA and PAES compared to only one objective function being considered in PSO without the topology constraint. For example, the average localization error in MOPSOLA reduces 15.09% and 8.39% compared with the traditional PSO method, respectively, under the condition of 10% and 20% anchor node proportion.(iii)
MOPSOLA has slightly higher localization accuracy than PAES under the condition of the same anchor node proportions. Compared with PAES, MOPSOLA reduces the average localization error 1.95% and 0.05%, respectively under the condition of 10% and 20% anchor node proportion.(iv)
MOPSOLA is robust with no performance declining in terms of the average localization errors being lower than 15% when the anchor node proportion is over 10%. These results prove that varying the anchor node proportion will not affect the robust performance of MOPSOLA.Table 3
Localization errors with different anchor node proportion.
Anchor node proportion
5%
10%
15%
20%
20%
30%
PSO
36.57%
28.33%
22.19%
19.94%
18.17%
17.77%
PAES
18.47%
15.19%
12.88%
12.10%
11.87%
11.02%
MOPSOLA
15.57%
13.24%
12.17%
11.55%
10.99%
10.54%Figure 4
Localization errors with different anchor node proportion.


### 4.3.3. The Effect of the Network Connectivity

Table4 and Figure 5 show the relationship between the average localization errors and the network connectivity while holding the total number nodes n=100 and 20% anchor node proportion, but with different communication radius R to change the network connectivity.(i)
The results show that the localization accuracy of each algorithm has the trend of rising as the increasing of the node communication radius. This is because the increasing of the communication radius will enable the unknown nodes to communicate with more neighbor nodes and further improve the search performance of intelligent optimization algorithms.(ii)
MOPSOLA can keep the average localization errors declining when the node communication radius reaches to 30 m, while the localization error using PAES begins to rising. The reason for this phenomenon is caused by rising of number of the first-level neighbor and the second-level neighbor [7] resulting from the bigger communication radios, which further leads to increasing of the ranging error of two classes unknown nodes defined in PAES.(iii)
The MOPSOLA is robust with no obvious performance decline in terms of the average localization errors kept lower than 15% when the node communication radius is over 20 m.Table 4
Localization errors with different network connectivity in different algorithms.
Communication radiusR
10
15
20
25
30
35
PSO
35.73%
30.94%
24.59%
18.94%
19.76%
17.88%
PAES
29.57%
21.11%
17.20%
12.79%
13.31%
14.01%
MOPSOLA
21.80%
18.36%
14.18%
12.55%
11.25%
10.52%Figure 5
Localization errors with different network connectivity in different algorithms.The simulation results analyzed in this section have proved that, because the model of multiobjective localization considers the influence of geometric topology constraintf2, some localization results which violate the constraint will be modified to further improve the localization accuracy. Furthermore, the optimum by proportion of selection can obtain closer result to the real localization and further improve the localization accuracy.


## 4.3.1. The Effect of the Network Nodes Density

Table2 and Figure 3 report the average localization errors, measured under the condition of changing the network nodes density and the total number of nodes, while holding on the anchor node proportion as 20% and the communication radius R=25 m.(i)
All the average localization errors of three methods reduce as the nodes increasing, and the number of nodes does little effect on the errors when it is over 100. It is obvious that the errors created by using PAES and MOPSOLA are lower than the errors created by using PSO due to the geometric topology constraint being considered by the first two methods.(ii)
Furthermore, the MOPSOLA algorithm has better performance than PAES due to the estimation accuracy being affected by the selection and mutation operators in PAES, and the average error reduces 4.84%, 5.12%, 3.47%, 1.50%, 1.09%, and 2.45%, respectively, compared to PAES with node number of 60, 80, 100, 120, 140, and 160.(iii)
The further analysis shows that although the network topology changes following the nodes increasing or decreasing, the MOPSOLA is robustness in terms of having the average localization errors lower than 15% with nodes over 80.Table 2
Localization errors with different node number.
Total number of nodes
60
80
100
120
140
160
PSO
37.20%
26.43%
21.02%
19.58%
19.39%
18.38%
PAES
22.52%
21.59%
15.65%
13.77%
12.56%
11.70%
MOPSOLA
17.68%
14.47%
12.15%
12.27%
11.47%
9.25%Figure 3
Localization errors with different node number.


## 4.3.2. The Effect of the Proportion of Anchor Nodes

Table3 and Figure 4 show the relationship between the average localization errors and the anchor node proportion while holding on the total number of nodes n=100 and communication radius R=25 m but with different anchor node proportion.(i)
All the average localization errors decrease as the anchor node proportion increases due to the increasing of anchor nodes around unknown nodes resulting in localization accuracy being improved.(ii)
MOPSOLA and PAES [7] have better performance in localization accuracy than the traditional PSO localization algorithm with the same anchor node proportion due to the two objective functions being considered in MOPSOLA and PAES compared to only one objective function being considered in PSO without the topology constraint. For example, the average localization error in MOPSOLA reduces 15.09% and 8.39% compared with the traditional PSO method, respectively, under the condition of 10% and 20% anchor node proportion.(iii)
MOPSOLA has slightly higher localization accuracy than PAES under the condition of the same anchor node proportions. Compared with PAES, MOPSOLA reduces the average localization error 1.95% and 0.05%, respectively under the condition of 10% and 20% anchor node proportion.(iv)
MOPSOLA is robust with no performance declining in terms of the average localization errors being lower than 15% when the anchor node proportion is over 10%. These results prove that varying the anchor node proportion will not affect the robust performance of MOPSOLA.Table 3
Localization errors with different anchor node proportion.
Anchor node proportion
5%
10%
15%
20%
20%
30%
PSO
36.57%
28.33%
22.19%
19.94%
18.17%
17.77%
PAES
18.47%
15.19%
12.88%
12.10%
11.87%
11.02%
MOPSOLA
15.57%
13.24%
12.17%
11.55%
10.99%
10.54%Figure 4
Localization errors with different anchor node proportion.


## 4.3.3. The Effect of the Network Connectivity

Table4 and Figure 5 show the relationship between the average localization errors and the network connectivity while holding the total number nodes n=100 and 20% anchor node proportion, but with different communication radius R to change the network connectivity.(i)
The results show that the localization accuracy of each algorithm has the trend of rising as the increasing of the node communication radius. This is because the increasing of the communication radius will enable the unknown nodes to communicate with more neighbor nodes and further improve the search performance of intelligent optimization algorithms.(ii)
MOPSOLA can keep the average localization errors declining when the node communication radius reaches to 30 m, while the localization error using PAES begins to rising. The reason for this phenomenon is caused by rising of number of the first-level neighbor and the second-level neighbor [7] resulting from the bigger communication radios, which further leads to increasing of the ranging error of two classes unknown nodes defined in PAES.(iii)
The MOPSOLA is robust with no obvious performance decline in terms of the average localization errors kept lower than 15% when the node communication radius is over 20 m.Table 4
Localization errors with different network connectivity in different algorithms.
Communication radiusR
10
15
20
25
30
35
PSO
35.73%
30.94%
24.59%
18.94%
19.76%
17.88%
PAES
29.57%
21.11%
17.20%
12.79%
13.31%
14.01%
MOPSOLA
21.80%
18.36%
14.18%
12.55%
11.25%
10.52%Figure 5
Localization errors with different network connectivity in different algorithms.The simulation results analyzed in this section have proved that, because the model of multiobjective localization considers the influence of geometric topology constraintf2, some localization results which violate the constraint will be modified to further improve the localization accuracy. Furthermore, the optimum by proportion of selection can obtain closer result to the real localization and further improve the localization accuracy.


## 4.4. The Time Complexity of the Algorithm

Table5 shows the time complexity of three algorithms with unknown nodes number M=n-m, the size of particle swarm N, iterations number tmax⁡, and archive size ArcMax. The time complexity of MOPSOLA is obviously higher than that of PSO and PAES.Table 5
The time complexity.
Algorithm
Time complexity
PSO
O
t
max
⁡
N
M
PAES
O
t
max
⁡
M
·
A
r
c
M
a
x
MOPSOLA
O
t
max
⁡
N
M
+
t
max
⁡
M
N
+
A
r
c
M
a
x
2Table6 shows the operation times of three algorithms with total nodes n=100, anchor nodes m=20, and communication radius R=25. It can more clearly be seen that the time complexity of MOPSOLA is higher than that of the two compared algorithms.Table 6
Iterative operation time of different algorithms.
Iterations number
1
10
100
1000
PSO
0.338 s
2.192 s
30.492 s
305.680 s
PAES
0.106 s
1.170 s
11.434 s
115.965 s
MOPSOLA
2.723 s
65.396 s
559.081 s
6622.944 sThe reason is that the two main operating levels of archive maintenance operator and global optimum selection operator in MOPSOLA will cost more time to repeatedly calculate and compare the values of two objective functions and delete the dominated solutions to obtain the elitism archived strategy, which also result in higher time complexity.


## 5. Conclusions

MOPSOLA adopts multiobjective localization with objective functions consisting of space distance constraint and geometric topology constraint and solves optimal solutions by adopting both the dynamic maintenance operator for archive and global optimal selection operator based on proportion of selection. Compared with traditional PSO localization algorithm, MOPSOLA can improve the localization accuracy and decrease the convergence rate. Compared with similar multiobjective localization algorithm PAES, the convergence rate is greatly enhanced and the localization accuracy is slightly increased. Under the premise of ensuring localization accuracy, how to further improve the convergence rate and reduce the energy consumption will be the next research emphasis.



---

*Source: 716291-2015-08-13.xml*