Get 20M+ Full-Text Papers For Less Than $1.50/day. Subscribe now for You or Your Team.

Learn More →

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

Localization Algorithm in Wireless Sensor Networks Based on Multiobjective Particle Swarm... Hindawi Publishing Corporation International Journal of Distributed Sensor Networks Volume 2015, Article ID 716291, 9 pages http://dx.doi.org/10.1155/2015/716291 Research Article Localization Algorithm in Wireless Sensor Networks Based on Multiobjective Particle Swarm Optimization Ziwen Sun, Li Tao, Xinyu Wang, and Zhiping Zhou School of Internet of Things Engineering, Jiangnan University, Lihu Road 1800, Wuxi 214122, China Correspondence should be addressed to Ziwen Sun; sunziwen@jiangnan.edu.cn Received 19 October 2014; Revised 24 January 2015; Accepted 18 February 2015 Academic Editor: Chase Wu Copyright © 2015 Ziwen Sun et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. 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. eTh 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. 1. Introduction quantum mechanics could enhance the global convergence andimprove theaccuracy[6]. However, it always happens The research on localization issues is important to the prac- that the results of estimated nodes’ localizations meet the tical application of wireless sensor networks (WSN) technol- space distance constraint without meeting the geometric ogy. Modern WSN applications pose increasingly complex topology constraint because of ranging errors in some prac- and stringent performance requirements on localization in tical applications. terms of accuracy. However, the localization methods by Recently, some works have proved the effectiveness of using traditional ranging technologies, such as received multiobjective optimization algorithms to solve conflict mul- signal strength indication (RSSI), have the drawback of low tiple objectives [7–14]. It is more reasonable to model the accuracy. Some intelligent algorithms have been used to solve node localization as a multiobjective optimization problem, the problems of localization including the accuracy [1–3]. which can be described as solving a Pareto solution, rather Traditionally, most studies focused on using single-objec- than simply being described as a single-objective optimiza- tive optimization problem to solve localization problems. tion problem. Based on this viewpoint, a multiobjective modelwas adoptedtosolve thenodelocalizationproblem Among these methods, the particle swarm optimization (PSO) algorithm is concerned by many researchers for its with tfi ness functions including the localization accuracy and fast convergence rate and simple implementation. By using the topological constraint, and the optimal solution was particles to imitate the estimated coordinates of unknown achieved by using the genetic algorithm [7]; however, there nodes, some methods model the localization problem as a are still some problems which are not solved. (i) eTh esti- single-objective optimization model with the space distance mation accuracy is affected by the selection and mutation constraint as the only tfi ness function. For example, the operators. (ii) The convergence rate is slow. (iii) The storage PSO localization algorithm based on log-barrier constraint consumption of nodes is very big due to the limitless size of thearchive forstoring theParetooptimal solutions. function could accelerate the convergence speed and save energy [4], the PSO localization adopting crossover operator Multiobjective particle swarm optimization has been and the mutation operator could avoid the premature con- proved with outperformance in the accuracy and the conver- gence. A multiobjective multileader PSO was used to handle vergence [5], and the PSO localization algorithm based on 2 International Journal of Distributed Sensor Networks 2 2 an extra objective by constraint handling method with advan- where 𝑟 = √(𝑥 −𝑥 ) +(𝑦 −𝑦 ) is the actual distance 𝑖 𝑗 𝑖 𝑗 tage in terms of efficiency [ 8]. A bare-bones PSO was com- between the two nodes and 𝑒 is the ranging error of RSSI bined with the sensitivity-based clustering to solve multiob- which follows a zero mean Gaussian distribution with vari- jective reliability redundancy allocation problems as a Pareto ance 𝜎 [7]. optimal solution with high eeff ctiveness [ 9]. Multiobjective The neighbour set 𝑁 and the complement set 𝑁 of node 𝑖 𝑖 PSO algorithm was used to optimize parameters of Stirling 𝑖 are defined as engine with more accurate results than genetic algorithms [10]. eTh multiobjective swarm optimization problem, which 𝑁 = {𝑗 ∈ 1,...,𝑛, 𝑗 =𝑖:𝑟 ̸ ≤𝑅}, selected the global best particle from a set of Pareto optimal (2) solutions to solve the convergence and the diversity of solu- 𝑁 = {𝑗 ∈ 1,...,𝑛, 𝑗 =𝑖:𝑟 ̸ >𝑅}, tions, was solved by combining PSO with charge system search [11]. The multiswarm multiobjective PSO was decom- where 𝑅 is the communication radius of node 𝑖 . posed by multiobjective decomposition to solve problems of The objective function of the space distance constraint is local optimum, convergence, and accuracy of Pareto solu- denoted by tion set [12]. The dynamic constrained multiobjective opti- mization problem was developed by introducing a local 𝑛 search operator based on attraction into PSO to speed up the 𝑓 = ∑ ( ∑ (𝑑 −𝑑 ) ), (3) 𝑖=𝑚+1 𝑗∈𝑁 optimization process or Pareto optimal solutions for obtain- 𝑖 ing a high convergence [13]. eTh main contribution of this paper is to propose a novel where 𝑑 is the estimated distance between node 𝑖 and 𝑗 , algorithm named multiobjective particle swarm optimization denoted by localization algorithm (MOPSOLA) for WSN localization to 2 2 address the issues of the limitless archive and the slow con- { (𝑥̂ −𝑥 ) +(𝑦̂ −𝑦 ) if 𝑗 is an anchor, { 𝑖 𝑗 𝑖 𝑗 vergence exiting in [7]. MOPSOLA constructs a multiob- 𝑑 = (4) jective model with both the space distance constraint and 2 2 (𝑥̂ − 𝑥̂ ) +(𝑦̂ − 𝑦̂ ) otherwise, 𝑖 𝑗 𝑖 𝑗 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 ̂ ̂ ̂ ̂ where (𝑥 ,𝑦 ) and (𝑥 ,𝑦 ) are estimated coordinates of 𝑖 𝑖 𝑗 𝑗 higher localization accuracy, the lower storage consumption, unknown nodes 𝑖 and 𝑗 . and the higher convergence. (i) eTh geometric topology con- eTh objective function of the geometric topology con- straint is considered to reduce the inaccuracy of localization. straint is denoted by (ii) The archive is dynamically maintained and limited in a maximum capacity to save the storage space for storing the 𝑛 𝑓 = ∑ ( ∑ 𝛿 + ∑ (1 − 𝛿 )). (5) Pareto optimal solutions. (iii) The global optimum solution 𝑖=𝑚+1 𝑗∈𝑁 is obtained to accelerate the convergence by adopting the 𝑖 𝑗∈ 𝑁 mechanism of proportion of selection. eTh simulation results eTh geometric topology constraint represents the con- have proved theproposedalgorithm caneeff ctivelyfind the nectivity constraint which dissatisefi s the current estimated multiobjective optimal solutions and achieve both the better positions of nonanchor nodes [7]. And 𝛿 is denoted by convergence speed and the better localization accuracy. 1 if 𝑑 >𝑅, 2. Multiobjective Localization Model 𝛿 = (6) 0 otherwise. The coordinates of unknown nodes need to meet both the space distance constraint and the geometric topology con- The space distance constraint and the geometric topology straint. The purpose of meeting the space distance constraint constraint imply the accuracy of the coordinates of the nodes. is to make the estimated coordinates close to the real values, The high accuracy of estimated coordinates of the unknown and meanwhile the purpose of meeting the geometric topol- nodes consequently lead to the small values of the two ogy constraint is to make the network topology unique to objective functions. er Th efore, estimating coordinates of the avoid forming a topological structure which is not in confor- unknownnodes canbemodeled to search theoptimum mity with the actual situation. solution for the multiobjective optimization issues, which Assume that 𝑛 nodes are deployed in two-dimensional can be obtained by decreasing both values of the objective space 𝑍 of WSN, including 𝑚 anchor nodes and 𝑛−𝑚 functions 𝑓 and 𝑓 . 1 2 unknown nodes with𝑚<𝑛 . Assuming the two nodes 𝑖 and 𝑗 being in the communication radius of each other, the 3. MOPSOLA internode ranging distance 𝑑 canbeobtainedbyRSSI ranging technology and denoted by 3.1. Mathematical Description of MOPSOLA. The optimal solution of multiobjective optimization issues is to n fi d the 𝑑 =𝑟 +𝑒 , (1) Pareto optimal solution [14]. Multiobjective optimization 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 International Journal of Distributed Sensor Networks 3 Population Archive Multiobjective function calculation Individual optimal selection Maintenance of archive Global optimal selection Velocity and localization update New archive New population Final archive Figure 1: Overall framework of the multiobjective PSO. issue with 𝑢 -dimensional decision vectors and V objectives is In MOPSOLA, model the estimated coordinates of𝑛−𝑚 denoted by unknownnodes as thedecisionvectors,and thetwo objective functions defined by (3)–(5) consist of the objective function Minmize F(x) =(𝑓 (x),𝑓 (x),...,𝑓 (x)) 1 2 V F(x). er Th efore, from formulas (3)–(5) and (7),MOPSOLA (7) can be formulated in the optimum mathematical form as s.t. x ∈[x , x ], 𝐿 𝑈 Minmize F(x) =(𝑓 (𝑥̂ ,𝑦̂),𝑓 (𝑥̂ ,𝑦̂)) where x =(𝑥 ,𝑥 ,...,𝑥 )∈𝑋∈𝑅 and F =(𝑓 ,𝑓 , 1 𝑖 𝑖 2 𝑖 𝑖 1 2 𝑢 1 2 ...,𝑓 )∈𝑌∈𝑅 . x is called the decision vector belonging to (8) s.t.(𝑥̂ ,𝑦̂)∈(𝑥̂ ,𝑦̂ ),(𝑥̂ ,𝑦̂ ) 𝑖 𝑖 𝐿 𝐿 𝑈 𝑈 the 𝑢 -dimensional decision space 𝑋 ,which is corresponding to 𝑢 -particles in PSO. x and x are lower and upper bound 𝐿 𝑈 𝑖 = 𝑚+1,𝑚+2,...,𝑛, constraints of the particle range, respectively. F is the objec- tive vector belonging to the V-dimensional objective space 𝑌 . where decision vectors x =(𝑥̂ ,𝑦̂) (𝑖 = 𝑚 + 1,𝑚 + 2,...,𝑛) 𝑖 𝑖 eTh objective function F(x) defines mapping functions from are the estimated coordinates corresponding to particles in thedecisionspace to theobjective space. eTh setofall the ̂ ̂ ̂ ̂ PSO, (𝑥 ,𝑦 )and (𝑥 ,𝑦 )are thelower andupper bound 𝐿 𝐿 𝑈 𝑈 particles meeting the constraints forms the decision space constraint values, 𝑓 is the objective function of the space feasible setΩ={x ∈𝑅 | x ∈[x , x ]}. 𝐿 𝑈 distance constraint, and 𝑓 is the objective function of the Some concepts related with MOPSOLA are described as geometric topology constraint. Therefore the decision space follows. is 𝑢=𝑛 − 𝑚 dimension and the objective space is V =2 dimension; that is, the coordinates of unknown nodes are (i) For two feasible solutions x , x ∈Ω in the processing 𝑎 𝑏 𝑢=𝑛−𝑚 particles,𝑓 and𝑓 are the V =2 objective functions. of PSO, if, ∀𝑖 = 1,2,..., V, 𝑓 (x )≤𝑓 (x )∧∃𝑗 = 1 2 𝑖 𝑏 𝑖 𝑎 Obtaining the multiobjective Pareto optimal solution 1,2,..., V, 𝑓 (x )<𝑓 (x ),thencall x dominate x , 𝑗 𝑏 𝑗 𝑎 𝑏 𝑎 is the ultimate goal of building a multiobjective optimal denoted by x ≺ x ,and keep x as optimization 𝑏 𝑎 𝑏 model for localization issues, which meets both the space results. distance constraint and the geometric topology constraint. (ii) The Pareto optimal solution x∗ is the decision vector Therefore the main essence of MOPSOLA can be described which satisfies ¬∃x ∈Ω: x ≺ x∗. as determining the dominant relationship according to the 󸀠 󸀠 (iii) 𝑆={ x ∈Ω|¬∃x ∈Ω,𝑓 (x )≤𝑓 (x),𝑗 = 1,2,..., V} 𝑗 𝑗 decision space feasible set Ω and the Pareto front F(x )= ∗ ∗ ∗ ∗ ∗ ∗ ∗ constructs the set of Pareto optimal solution obtained {(𝑓 (𝑥̂ ,𝑦̂ ),𝑓 (𝑥̂ ,𝑦̂ )) | x =(𝑥̂ ,𝑦̂ )∈𝑆} ,𝑖 = 𝑚+1,𝑚+ 1 2 𝑖 𝑖 𝑖 𝑖 𝑖 𝑖 𝑖 from all of the Pareto optimal solutions. 2,...,𝑛 , saving Pareto optimal solution set𝑆 in an archive and updating the position and the velocity of multiobjective PSO. (iv) F(x)={F(x∗) = (𝑓 (x∗),𝑓 (x∗),...,𝑓 (x∗)) | x∗∈ 1 2 V 𝑆} forms the Pareto front consisting of the values of objective functions corresponding to the Pareto opti- 3.2. Describing of MOPSOLA mal set. (v) eTh purpose of optimization is to n fi d the Pareto opti- 3.2.1. Overall Framework. Shown as Figure 1,the framework mal solution. of theproposedmultiobjectivePSO algorithmincludes some Iteration 4 International Journal of Distributed Sensor Networks key operators such as maintenance of archive, global opti- deleting some of the members when the maximum capacity mum selection, and the velocity and localization update. eTh is reached. Consequently, a space will be maintained for the particle population relies on an archive to save Pareto optimal new solutions entering into the archive. solutions during the iterative process and selecting the global However, due to nondominated property of Pareto opti- optimum from these solutions, which is the key point that mal solutions, namely, there is no difference between the solu- the multiobjective PSO is dieff rent from the traditional single tions, a concept of intensive distance is introduced to evaluate objective localization. thesolutionquality.Generally thepoint (solution) in asparse eTh refore, the localization issue is modeled as a multiob- area which has bigger intensive distance is better than the jective optimization model in MOPSOLA, and two operators, point in an intensive area in the objective space [15]. which are the dynamic maintenance operator for the archive Den fi ition 1. Given set 𝑆 is the set of Pareto optimal solutions andthe global optimumselection operator basedonpropor- in the archive and 𝑥 ∈𝑆 is a Pareto optimal solution, then tion of selection, aredesignedtobesuitablefor thelimited the intensive distance𝐷𝑖𝑠 of𝑥 is defined as the average value energy and the poor computing power of WSN nodes. 𝑖 𝑖 of the minimum distance 𝑑𝑖𝑠 and the second minimum dis- (i) In the multiobjective function calculation level, func- 2 tance𝑑𝑖𝑠 between𝑥 and other Pareto optimal solutions𝑥 ∈ 𝑖 𝑗 tions as formulas (3)–(5) are calculated according to 1 2 𝑆 in the archive. 𝑑𝑖𝑠 , 𝑑𝑖𝑠 ,and 𝐷𝑖𝑠 are computed as 𝑖 𝑖 𝑖 all particles, that is, all estimated nodes’ coordinates. (ii) In the individual optimal selection level, the personal optimum selection operator works. Based on the con- 𝑑𝑖𝑠 = min{𝐷 |𝑥 ∈𝑆, 𝑥 ∈ ,𝑆 𝑗 = 1,2,...,𝑐, 𝑗 =𝑖̸ }, 𝑖 𝑖 𝑗 cept of Pareto optimality, the 𝑡 of each particle is 2 1 chosen between the particle’s current location and its 𝑑𝑖𝑠 = min{𝐷 |𝐷 >𝑑𝑠𝑖 ,𝑥 ∈𝑆, 𝑥 ∈𝑆, 𝑖 𝑗 𝑖 𝑖 historical 𝑡 dynamically. 𝑗 = 1,2,...,𝑐, 𝑗 =𝑖̸ }, (iii) In the global optimal selection level, the global opti- mum selection operator works. eTh proportion of 1 2 (𝑑 +𝑑𝑠𝑖 ) selection is set for each Pareto optimal solution based 𝑖 𝑖 𝐷𝑖𝑠 = , on intensivedistance, andaglobal optimumfor each particle is selected by proportion of selection. (10) (iv) In the velocity and localization update level, the posi- tion and velocity update operator works for all indi- 2 2 where 𝐷 = √∑ (𝑓 (𝑥 )−𝑓 (𝑥 )) is the objective con- 𝑘=1 𝑘 𝑖 𝑘 𝑗 vidual particles. eTh update processissimilar to the straint distance between 𝑥 and 𝑥 and 𝑓 (𝑘=1,2) is the traditional single objective PSO as 𝑖 𝑗 𝑘 objective function, 𝑐 is the number of solutions. V (𝑡+1 ) =𝜔 V (𝑡 )+𝑐 𝑟 (𝑝𝑏𝑒𝑠𝑡 −ℎ (𝑡 )) 𝑖 𝑖 1 1 𝑖 The intensive distances of Pareto optimal solutions are +𝑐 𝑟 (𝑔𝑏𝑒𝑠𝑡 − ℎ (𝑡 )), (9) sorted and the smaller ones are deleted in order to limit the 2 2 𝑖 number of members in the archive. ℎ (𝑡+1 ) =ℎ (𝑡 ) + V (𝑡+1 ), 𝑖 = 𝑚+1,𝑚+2,...,𝑛, 𝑖 𝑖 𝑖 It is ensuredthatthe membersinthe archivecan be limitedinthe maximumcapacitybythe archivemaintenance where V is the velocity of the 𝑖 th particle, ℎ =(𝑥̂ ,𝑦̂) operator, which avoids the nondominated solutions increas- 𝑖 𝑖 𝑖 𝑖 is the estimated coordinates of the 𝑖 th particle vector, ing inn fi itely to reduce the ecffi iency along with the evolution. 𝑡 is the best solution for the 𝑖 th particle, 𝑡 is At the same time, the most intense individual is deleted, and the best solution for the population, 𝜔 is the inertia the uniform distribution of the Pareto front is ensured by weight, 𝑐 and 𝑐 are constants, and 𝑡 is the iteration saving lots of scattered individuals. 1 2 time. (v) In the maintenance of archive level, the archive main- 3.2.3. Global Optimum Selection Operator. In the traditional tenance operator works. eTh maximum capacity of single objective PSO algorithm, it is tolerable to use the opti- archive is set as 𝑥𝑎𝐴𝑟𝑀𝑐 and the archive is dynami- mal solution with the best tfi ness as the global optimum 𝑡 cally updated according to the density distance in the because the 𝑡 of every particle is the same. However, in objectivespace of theParetooptimal solution to save multiobjective PSO the population generates more than one the storage space. nondominated 𝑡 leading difference among some particle global optimums, which results to necessarily choose the 3.2.2. Archive Maintenance Operator. AmultiobjectivePSO appropriate global optimum. Based on the intensive distance, algorithm does not produce a unique solution but a set of the global optimum is selected for each particle by adopting Pareto optimal solutions at the end of each iteration; therefore the proportion of selection. an archiveisusedtosavethese Pareto optimalsolutions and the members in the archive become the n fi al solution set Den fi ition 2. Given that the number of Pareto optimal solu- when the iteration stops. To adapt to the limited storage space tions in the archive of the current iteration is 𝑐 with 𝑐≤ of a WSN node, the members in an archive are limited by 𝑥𝑎𝐴𝑟𝑀𝑐 , a proportion of selection 𝜉 of a Pareto optimal 𝑔𝑏𝑒𝑠 𝑔𝑏𝑒𝑠 𝑔𝑏𝑒𝑠 𝑔𝑏𝑒𝑠 𝑝𝑏𝑒𝑠 𝑖𝑗 𝑖𝑠 𝑝𝑏𝑒𝑠 𝑖𝑗 𝑖𝑗 𝑝𝑏𝑒𝑠 𝑖𝑗 International Journal of Distributed Sensor Networks 5 solution 𝑥 ∈𝑆 is defined as the rate of its intensive distance 5.5 to the sum of intensive distances in the archive according to 4.5 𝐷𝑖𝑠 𝜉 = , 𝑖 = 1,...,𝑐. (11) 𝑖 𝑐 ∑ 𝐷𝑖𝑠 𝑘=1 3.5 Formula (11) implies that the larger intensive distance a Pareto optimal solution has, the bigger proportion of selec- 2.5 tion it has; therefore it has a bigger proportion to be selected 0 100 200 300 400 500 600 700 800 900 1000 as the global optimum. Iteration PAES MOPSOLA 3.2.4. The Pseudo Code of the MOPSOLA. The main com- ponents of MOPSOLA, including multiobjective function Figure 2: The comparison of convergence rate between MOPSOLA calculation, individual optimal selection, maintenance of and PAES. archive, global optimal selection, and velocity and localiza- tion update, are described as function MopsoFuc with pseu- docode in Algorithm 1.Where thenodeisthe classofnode further applied to evaluate the performance of all the nodes information with four members of 𝑛𝑜𝑑𝑒.𝑥 , 𝑛𝑜𝑑𝑒.𝑦 , 𝑛𝑜𝑑𝑒.𝑖𝑑 , being estimated: and 𝑛𝑜𝑑𝑒.𝑎𝑛𝑐ℎ𝑜𝑟𝑔𝑓 corresponding to the 𝑥 coordinate, 𝑦 coordinate,idnumber, andanchorflag of anode. 𝑡 is the 2 2 ̂ ̂ (𝑥 −𝑥 ) +(𝑦 −𝑦 ) current iteration time and 𝑡 is the maximum iteration 𝑖 𝑖 𝑖 𝑖 (12) max 𝑔𝑙𝑒𝐸𝑟𝑟𝑜𝑟𝑆𝑛𝑖 = × 100%, time.Theother variableshavethe consistent meaningwith thesamenamed variablesaforementioned. 𝑛−𝑚 2 2 ∑ (𝑥̂ −𝑥 ) +(𝑦̂ −𝑦 ) 𝑖=1 𝑖 𝑖 𝑖 𝑖 (13) 𝐴 V = × 100%. (𝑛−𝑚 )×𝑅 4. Simulations and Analysis 4.2. eTh Efficiency of the Tow Objective Functions To validate the performance of the MOPSOLA, the simu- lationshavebeendonetotestMOPSOLA andthe other 4.2.1. eTh Convergence Rate. Figure 2 is the comparison of two algorithms, the traditional PSO and PASE [7], in Matlab objective function 𝑓 about the convergence rate between 2010b. The simulations have been done using MOPSOLA MOPSOLA and PAES. MOPSOLA and PAES start to con- with objective functions 𝑓 and 𝑓 ,and they also have been 1 2 verge at the 400th iteration and 700th iteration, respectively. done using PSO with objective function 𝑓 and using PASE eTh result shows that MOPSOLA retains more outstand- [7] with objective functions 𝑓 and 𝑓 . 1 2 ing individuals to accelerate the algorithm convergence by avoiding the affection of selection and mutation operation on the next generation and adopting dynamic maintenance of 4.1. eTh Simulation and Evaluation Parameters archive combined with selecting the optimum by proportion of selection for maintaining much more outstanding individ- 4.1.1. eTh Simulation Parameters. Total 𝑛 nodes are randomly uals. deployed in 100 m × 100 m area with 𝑚 anchor nodes being randomly generated from these nodes. Assuming that the RSSI ranging error 𝑒 follows a Gaussian distribution with a 4.2.2. eTh Localization Accuracy. The single localization 2 2 2 2 errors of 80 unknown nodes has been simulated to evaluate zero mean and variance 𝜎 , 𝜎 =𝛽 𝑟 , 𝛽 = 0.1 . eTh max- the localization accuracy under the condition of 20% anchor imum capacity of the archive 𝑥𝑎𝐴𝑟𝑀𝑐 is 10 and the max nodes by using MOPSOLA and PSO algorithm. iteration time 𝑡 is 1000. max (i) eTh simulation results show that the maximum and the minimum single localization error are 81.13% 4.1.2. eTh Localization Errors. The localization error is gen- and1.52%,respectively, in MOPSOLAcomparedto erally related to the node communication radius. Based on 94.36% and 5.52%, respectively, in PSO. the communication radius, two kinds of localization errors are defined to evaluate the localization performance of the (ii) The ranges of 𝑔𝑙𝑒𝐸𝑟𝑟𝑜𝑟𝑆𝑛𝑖 are counted to further proposed algorithm. One is the single localization error evaluate the accuracy shown in Table 1.Itcan been 𝑔𝑙𝑒𝐸𝑟𝑟𝑜𝑟𝑆𝑛𝑖 of an unknown node den fi ed by formula (12), seen that 24 nodes’ single localization errors fell into whichisusedtoevaluatethe performanceofeachnode 0∼5% in MOPSOLAcomparedto10nodes’inPSO, being estimated. eTh other is the average localization error and 5 nodes’ single localization errors are over 30% in 𝐴 V of the network defined as formula (13),which is MOPSOLA compared to 31 nodes’ in PSO. Objective function f 𝑒𝑟𝐸𝑟𝑟𝑜𝑟 𝑖𝑗 𝑖𝑗 𝑒𝑟𝐸𝑟𝑟𝑜𝑟 𝑙𝑎 6 International Journal of Distributed Sensor Networks 𝑆 =MopsoFuc( , 𝑛 , 𝑚 , 𝑅 ) node: class of node information 𝑛 : total number of nodes 𝑚 : anchor nodes 𝑅 : node communication radius 𝑆 : set of Pareto optimal solutions in the archive (1) Initialize each parameter, 𝜔 = 0.7298 , 𝑐 =𝑐 = 1.4962, 𝑥𝑎𝐴𝑟𝑀𝑐 =10 1 2 (2) Initialize ℎ and V for each particle randomly then 𝑡 ← (3)While𝑡≤𝑡 Do max // Step 1. Multi-objective Function Calculation (4)ForeachparticleDo (5)Compute .𝑓1 and .𝑓2 using class (6)End // Step 2. Individual Optimal Selection (7)Foreach 𝑡 Do (8)Compute 𝑡 .𝑓1 and 𝑡 .𝑓2 using class (9)If 𝑡 ≺ (10) 𝑡 ← 𝑡 (11)ElseIf ≺ 𝑝𝑡 (12) 𝑡 ← (13)Else 𝑎 ← (14)If𝑎≤ 0.5 then 𝑡 ← 𝑡 (15)Else 𝑡 ← (16)End // Step 3. Maintenance of Archive (17) While Receive 𝑡 Do (18) 𝐴𝑟𝑐𝑝𝑚𝑒𝑇← 𝐴𝑟ℎ𝑐 𝑖 V𝑒∪𝑝𝑠𝑒𝑏𝑡 (19) Delete repetitive solution in𝐴𝑐𝑟𝑝𝑚 (20) For every member in𝐴𝑐𝑟𝑝𝑚 Do (21) IF dominated then Delete (22)End (23) 𝑐← number of TempArc (24)IF𝑐≤𝐴𝑥𝑎𝑀𝑐𝑟 (25) 𝐴𝑟ℎ𝑐 𝑖 V𝑒←𝑇𝐴𝑐𝑟𝑝𝑚𝑒 (26)ElseCompute 𝐷𝑖𝑠 of𝐴𝑐𝑟𝑝𝑚 (27) Descending sort of𝐴𝑐𝑟𝑝𝑚 (28) 𝐴𝑟ℎ𝑐 𝑖 V𝑒←𝑇𝐴𝑐𝑟𝑝𝑚𝑒 (29)End // Step 4. Global Optimal Selection (30) For every member of 𝐴𝑟ℎ𝑐 𝑖 V𝑒 Do (31)Compute 𝐷𝑖𝑠 ; (32)Compute 𝜉 ; (33)End (34)ForeveryparticleDo (35)Usingroulettewheeltochoose 𝑡 according to 𝜉 ; (36)End // Step 5. Velocity and Localization Update (37) V(𝑡 + 1) ← 𝜔 V(𝑡) + 𝑐 𝑟 (𝑝𝑏𝑒𝑠𝑡 − ℎ(𝑡)) + 𝑐 𝑟 (𝑔𝑏𝑒𝑠𝑡 − ℎ(𝑡)) 1 1 2 2 (38) ℎ(𝑡 + 1) ← ℎ(𝑡) + V(𝑡 + 1) (39) End (While) (40)𝑆←𝐴ℎ𝑐𝑟 𝑖 V𝑒 Algorithm 1: eTh proposed MOPSOLA in pseudocode. Table 1: eTh distribution of 𝑔𝑆𝑖𝑛 ranges. 𝑔𝑆𝑖𝑛 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 𝑙𝑒𝐸𝑟𝑟𝑜𝑟 𝑙𝑒𝐸𝑟𝑟𝑜𝑟 𝑔𝑏𝑒𝑠 𝑇𝑒 𝑇𝑒 𝑇𝑒 𝑇𝑒 𝑝𝑏𝑒𝑠 𝑖𝑐𝑙𝑒𝑝𝑎𝑟𝑡 𝑝𝑏𝑒𝑠 𝑝𝑏𝑒𝑠 𝑝𝑏𝑒𝑠 𝑟𝑎𝑛𝑑 𝑖𝑐𝑙𝑒𝑝𝑎𝑟𝑡 𝑝𝑏𝑒𝑠 𝑏𝑒𝑠 𝑖𝑐𝑙𝑒𝑝𝑎𝑟𝑡 𝑝𝑏𝑒𝑠 𝑝𝑏𝑒𝑠 𝑖𝑐𝑙𝑒𝑝𝑎𝑟𝑡 𝑝𝑏𝑒𝑠 𝑛𝑜𝑑𝑒 𝑝𝑏𝑒𝑠 𝑝𝑏𝑒𝑠 𝑝𝑏𝑒𝑠 𝑛𝑜𝑑𝑒 𝑖𝑐𝑙𝑒𝑝𝑎𝑟𝑡 𝑖𝑐𝑙𝑒𝑝𝑎𝑟𝑡 𝑖𝑐𝑙𝑒𝑝𝑎𝑟𝑡 𝑝𝑏𝑒𝑠 𝑛𝑜𝑑𝑒 International Journal of Distributed Sensor Networks 7 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% 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% 40 40 35 35 25 25 20 20 15 15 10 10 60 70 80 90 100 110 120 130 140 150 160 5 10 15 20 25 30 The total number of nodes Anchor nodes proportion (%) PSO PSO PAES PAES MOPSOLA MOPSOLA Figure 3: Localization errors with different node number. Figure 4: Localization errors with different anchor node propor- tion. (iii) From the comparison, it is obvious that the single nodes does little effect on the errors when it is over localization errors by using MOPSOLA are lower than 100. It is obvious that the errors created by using PAES those by using PSO. This is because the geometric and MOPSOLA are lower than the errors created by topology constraint is limited in a reasonable topol- using PSO due to the geometric topology constraint ogy by the objective function 𝑓 ,which decreasesthe being considered by the rfi st two methods. inaccuracy of the localization. (ii) Furthermore, the MOPSOLA algorithm has better performance than PAES due to the estimation accu- 4.3.TheRobustPerformance of theMOPSOLA. The simula- racy being aeff cted by the selection and mutation tions focusing on the average localization errors have been operators in PAES, and the average error reduces done to evaluate the robustness of the MOPSOLA in case of 4.84%, 5.12%, 3.47%, 1.50%, 1.09%, and 2.45%, respec- different situations with varying nodes density, anchor nodes, tively,comparedtoPAESwithnodenumberof60, 80, and network connectivity. 100, 120, 140, and 160. (iii) The further analysis shows that although the network 4.3.1. eTh Eeff ct of the Network Nodes Density. Table 2 and topology changes following the nodes increasing or Figure 3 report the average localization errors, measured decreasing, the MOPSOLA is robustness in terms of under the condition of changing the network nodes density having the average localization errors lower than 15% and the total number of nodes, while holding on the anchor with nodes over 80. node proportion as 20% and the communication radius𝑅= 25 m. 4.3.2. eTh Eeff ct of the Proportion of Anchor Nodes. Table 3 (i) All the average localization errors of three methods and Figure 4 show the relationship between the average reduce as the nodes increasing, and the number of localization errors and the anchor node proportion while Average localization error (%) Average localization error (%) 8 International Journal of Distributed Sensor Networks Table 4: Localization errors with different network connectivity in different algorithms. Communication radius 𝑅 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% holding on the total number of nodes 𝑛 = 100 and com- munication radius𝑅=25 m but with different anchor node proportion. (i) All the average localization errors decrease as the an- chor 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 local- ization algorithm with the same anchor node propor- tion due to the two objective functions being consid- ered in MOPSOLA and PAES compared to only one 10 15 20 25 30 35 objective function being considered in PSO without Node communication radius the topology constraint. For example, the average PSO localization error in MOPSOLA reduces 15.09% and PAES 8.39% compared with the traditional PSO method, MOPSOLA respectively, under the condition of 10% and 20% Figure 5: Localization errors with different network connectivity in anchor node proportion. different algorithms. (iii) MOPSOLA has slightly higher localization accuracy than PAES under the condition of the same anchor node proportions. Compared with PAES, MOPSOLA PAES begins to rising. eTh reason for this phe- reduces the average localization error 1.95% and nomenon is caused by rising of number of the first- 0.05%, respectively under the condition of 10% and level neighbor and the second-level neighbor [7] 20% anchor node proportion. resulting from the bigger communication radios, (iv) MOPSOLA is robust with no performance declining which further leads to increasing of the ranging error in terms of the average localization errors being lower of two classes unknown nodes defined in PAES. than 15% when the anchor node proportion is over (iii) The MOPSOLA is robust with no obvious perfor- 10%. These results prove that varying the anchor node mance decline in terms of the average localization proportion will not affect the robust performance of errors kept lower than 15% when the node commu- MOPSOLA. nication radius is over 20 m. eTh simulation resultsanalyzedinthissection have 4.3.3. eTh Eeff ct of the Network Connectivity. Table 4 and proved that, because the model of multiobjective localization Figure 5 show the relationship between the average localiza- considers the influence of geometric topology constraint 𝑓 , tion errors and the network connectivity while holding the 2 some localization results which violate the constraint will total number nodes 𝑛 = 100 and 20% anchor node pro- be modified to further improve the localization accuracy. portion, but with different communication radius 𝑅 to change Furthermore, the optimum by proportion of selection can the network connectivity. obtain closer result to the real localization and further (i) eTh results show that the localization accuracy of each improve the localization accuracy. algorithm has the trend of rising as the increasing of the node communication radius. This is because the 4.4. eTh Time Complexity of the Algorithm. Table 5 shows the increasing of the communication radius will enable time complexity of three algorithms with unknown nodes the unknown nodes to communicate with more number𝑀=𝑛−𝑚 , the size of particle swarm 𝑁 ,iterations neighbor nodes and further improve the search per- number 𝑡 ,and archivesize 𝑥𝑎𝐴𝑟𝑀𝑐 . eTh time complexity max formance of intelligent optimization algorithms. of MOPSOLA is obviously higher than that of PSO and PAES. (ii) MOPSOLA can keep the average localization errors Table 6 shows the operation times of three algorithms declining when the node communication radius with total nodes 𝑛 = 100 , anchor nodes 𝑚=20 ,and reaches to 30 m, while the localization error using communication radius𝑅=25 .Itcan more clearlybeseen Average localization error (%) International Journal of Distributed Sensor Networks 9 Table 5: e Th time complexity. IEEE Communications Surveys & Tutorials,vol.13, no.1,pp. 68– 96, 2011. Algorithm Time complexity [2] A. F. Assis, L. F. M. Vieira, M. T. R. Rodrigues, and G. L. PSO 𝑂(𝑡 ) Pappa, “A genetic algorithm for the minimum cost localization max PAES 𝑂(𝑡 𝑀⋅𝐴𝑥𝑎)𝑀𝑐𝑟 problem in wireless sensor networks,” in Proceedings of the IEEE max Congress on Evolutionary Computation (CEC ’13),pp. 797–804, MOPSOLA 𝑂(𝑡 + 𝑡 𝑀(𝑁 + 𝑎𝑥)𝐴𝑟 ) max max IEEE, Cancun, ´ Mexico, June 2013. [3] M.Vecchio,R.Lo´pez-Valcarce, and F. Marcelloni, “An effective Table 6: Iterative operation time of different algorithms. metaheuristic approach to node localization in wireless sensor networks,” in Proceedings of the 8th IEEE International Confer- Iterations ence on Mobile Ad-hoc and Sensor Systems (MASS ’11),pp. 143– 1 10 100 1000 number 145, Valencia, Spain, October 2011. 0.338 s 2.192 s 30.492 s 305.680 s PSO [4] H. A. Nguyen, H. Guo, and K.-S. Low, “Real-time estimation of sensor node’s position using particle swarm optimization with 0.106 s 1.170 s 11.434 s 115.965 s PAES log-barrier constraint,” IEEE Transactions on Instrumentation MOPSOLA 2.723 s 65.396 s 559.081 s 6622.944 s and Measurement, vol. 60, no. 11, pp. 3619–3628, 2011. [5] X.Hu, S. Shi, andX.Gu, “Animprovedparticleswarm opti- mization algorithm for wireless sensor networks localization,” that thetimecomplexity of MOPSOLAishigherthanthatof in Proceedings of the 8th International Conference on Wireless the two compared algorithms. Communications, Networking and Mobile Computing (WiCOM eTh reason is that the two main operating levels of archive ’12), pp. 1–4, IEEE, Shanghai, China, September 2012. maintenance operator and global optimum selection operator [6] L. Gong, J. Sun, W. Xu, and J. Xu, “Research and simulation of in MOPSOLA will cost more time to repeatedly calculate and node localization in WSN based on Quantum particle swarm compare the values of two objective functions and delete the optimization,” in Proceedings of the 11th International Sympo- dominated solutions to obtain the elitism archived strategy, sium on Distributed Computing and Applications to Business, which also result in higher time complexity. Engineering and Science (DCABES ’12), pp. 144–148, Guilin, China, October 2012. [7] M. Vecchio, R. Lo´pez-Valcarce, and F. Marcelloni, “A two- 5. Conclusions objective evolutionary approach based on topological con- straints for node localization in wireless sensor networks,” MOPSOLA adopts multiobjective localization with objective Applied Soft Computing Journal ,vol.12,no.7,pp.1891–1901,2012. functions consisting of space distance constraint and geo- [8] M.Shokrianand K. A. High,“Applicationofamultiobjective metric topology constraint and solves optimal solutions by multi-leader particle swarm optimization algorithm on NLP adopting both the dynamic maintenance operator for archive and MINLP problems,” Computers and Chemical Engineering, and global optimal selection operator based on proportion of vol. 60, pp. 57–75, 2014. selection. Compared with traditional PSO localization algo- [9] E.Zhang,Y.Wu, andQ.Chen, “A practicalapproachfor rithm, MOPSOLA can improve the localization accuracy and solving multi-objective reliability redundancy allocation prob- decrease the convergence rate. Compared with similar mul- lems using extended bare-bones particle swarm optimization,” tiobjective localization algorithm PAES, the convergence rate Reliability Engineering and System Safety,vol.127,pp. 65–76, is greatly enhanced and the localization accuracy is slightly increased. Under the premise of ensuring localization accu- [10] C. Duan, X. Wang, S. Shu, C. Jing, and H. Chang, “er Th mo- racy,how to furtherimprove theconvergence rate andreduce dynamic design of Stirling engine using multi-objective particle the energy consumption will be the next research emphasis. swarm optimization algorithm,” Energy Conversion and Man- agement, vol. 84, pp. 88–96, 2014. [11] A. Kaveh and K. Laknejadi, “A novel hybrid charge system Conflict of Interests search and particle swarm optimization method for multi- objective optimization,” Expert Systems with Applications,vol. eTh authors declare that they have no conflict of interests to 38, no. 12, pp. 15475–15488, 2011. this work. [12] H. Peng, R. Li, L. L. Cao, and L. X. Li, “Multiple swarms multi- objective particle swarm optimization based on decomposi- Acknowledgments tion,” Procedia Engineering,vol.15, pp.3371–3375,2011. [13] J.Wei andM.Zhang,“Attraction basedPSO with sphere Thisworkissupported by theNationalNatural ScienceFoun- search for dynamic constrained multi-objective optimization dation of China under Grant no. 61373126, the Natural Sci- problems,” in Proceedings of the 13th Annual Genetic and Evo- ence Foundation of Jiangsu Province of China under Grant lutionary Computation Conference (GECCO ’11),pp. 77–78, no. BK20131107 and the State Scholarship Fund by China IEEE, Dublin, Ireland, July 2011. Scholarship Council. [14] M. G. Gong,L.C.Jiao, D. D. Yang,and W. P. Ma,“Research on evolutionary multi-objective optimization algorithms,” Journal of Software ,vol.20, no.2,pp. 271–289, 2009. References [15] W. Li and X. Zhang, “An improved multi-objective particle [1] R. V. Kulkarni, A. Forster, and G. K. Venayagamoorthy, “Com- swarm optimization algorithm based on pareto,” Computer Sim- putational intelligence in wireless sensor networks: a survey,” ulation,vol.27, pp.96–99,2010. 𝑐𝑀 𝑁𝑀 𝑁𝑀 http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png International Journal of Distributed Sensor Networks SAGE

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

Loading next page...
 
/lp/sage/localization-algorithm-in-wireless-sensor-networks-based-on-CIKxrYlITb

References (16)

Publisher
SAGE
Copyright
© 2015 Ziwen Sun et al.
ISSN
1550-1329
eISSN
1550-1477
DOI
10.1155/2015/716291
Publisher site
See Article on Publisher Site

Abstract

Hindawi Publishing Corporation International Journal of Distributed Sensor Networks Volume 2015, Article ID 716291, 9 pages http://dx.doi.org/10.1155/2015/716291 Research Article Localization Algorithm in Wireless Sensor Networks Based on Multiobjective Particle Swarm Optimization Ziwen Sun, Li Tao, Xinyu Wang, and Zhiping Zhou School of Internet of Things Engineering, Jiangnan University, Lihu Road 1800, Wuxi 214122, China Correspondence should be addressed to Ziwen Sun; sunziwen@jiangnan.edu.cn Received 19 October 2014; Revised 24 January 2015; Accepted 18 February 2015 Academic Editor: Chase Wu Copyright © 2015 Ziwen Sun et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. 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. eTh 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. 1. Introduction quantum mechanics could enhance the global convergence andimprove theaccuracy[6]. However, it always happens The research on localization issues is important to the prac- that the results of estimated nodes’ localizations meet the tical application of wireless sensor networks (WSN) technol- space distance constraint without meeting the geometric ogy. Modern WSN applications pose increasingly complex topology constraint because of ranging errors in some prac- and stringent performance requirements on localization in tical applications. terms of accuracy. However, the localization methods by Recently, some works have proved the effectiveness of using traditional ranging technologies, such as received multiobjective optimization algorithms to solve conflict mul- signal strength indication (RSSI), have the drawback of low tiple objectives [7–14]. It is more reasonable to model the accuracy. Some intelligent algorithms have been used to solve node localization as a multiobjective optimization problem, the problems of localization including the accuracy [1–3]. which can be described as solving a Pareto solution, rather Traditionally, most studies focused on using single-objec- than simply being described as a single-objective optimiza- tive optimization problem to solve localization problems. tion problem. Based on this viewpoint, a multiobjective modelwas adoptedtosolve thenodelocalizationproblem Among these methods, the particle swarm optimization (PSO) algorithm is concerned by many researchers for its with tfi ness functions including the localization accuracy and fast convergence rate and simple implementation. By using the topological constraint, and the optimal solution was particles to imitate the estimated coordinates of unknown achieved by using the genetic algorithm [7]; however, there nodes, some methods model the localization problem as a are still some problems which are not solved. (i) eTh esti- single-objective optimization model with the space distance mation accuracy is affected by the selection and mutation constraint as the only tfi ness function. For example, the operators. (ii) The convergence rate is slow. (iii) The storage PSO localization algorithm based on log-barrier constraint consumption of nodes is very big due to the limitless size of thearchive forstoring theParetooptimal solutions. function could accelerate the convergence speed and save energy [4], the PSO localization adopting crossover operator Multiobjective particle swarm optimization has been and the mutation operator could avoid the premature con- proved with outperformance in the accuracy and the conver- gence. A multiobjective multileader PSO was used to handle vergence [5], and the PSO localization algorithm based on 2 International Journal of Distributed Sensor Networks 2 2 an extra objective by constraint handling method with advan- where 𝑟 = √(𝑥 −𝑥 ) +(𝑦 −𝑦 ) is the actual distance 𝑖 𝑗 𝑖 𝑗 tage in terms of efficiency [ 8]. A bare-bones PSO was com- between the two nodes and 𝑒 is the ranging error of RSSI bined with the sensitivity-based clustering to solve multiob- which follows a zero mean Gaussian distribution with vari- jective reliability redundancy allocation problems as a Pareto ance 𝜎 [7]. optimal solution with high eeff ctiveness [ 9]. Multiobjective The neighbour set 𝑁 and the complement set 𝑁 of node 𝑖 𝑖 PSO algorithm was used to optimize parameters of Stirling 𝑖 are defined as engine with more accurate results than genetic algorithms [10]. eTh multiobjective swarm optimization problem, which 𝑁 = {𝑗 ∈ 1,...,𝑛, 𝑗 =𝑖:𝑟 ̸ ≤𝑅}, selected the global best particle from a set of Pareto optimal (2) solutions to solve the convergence and the diversity of solu- 𝑁 = {𝑗 ∈ 1,...,𝑛, 𝑗 =𝑖:𝑟 ̸ >𝑅}, tions, was solved by combining PSO with charge system search [11]. The multiswarm multiobjective PSO was decom- where 𝑅 is the communication radius of node 𝑖 . posed by multiobjective decomposition to solve problems of The objective function of the space distance constraint is local optimum, convergence, and accuracy of Pareto solu- denoted by tion set [12]. The dynamic constrained multiobjective opti- mization problem was developed by introducing a local 𝑛 search operator based on attraction into PSO to speed up the 𝑓 = ∑ ( ∑ (𝑑 −𝑑 ) ), (3) 𝑖=𝑚+1 𝑗∈𝑁 optimization process or Pareto optimal solutions for obtain- 𝑖 ing a high convergence [13]. eTh main contribution of this paper is to propose a novel where 𝑑 is the estimated distance between node 𝑖 and 𝑗 , algorithm named multiobjective particle swarm optimization denoted by localization algorithm (MOPSOLA) for WSN localization to 2 2 address the issues of the limitless archive and the slow con- { (𝑥̂ −𝑥 ) +(𝑦̂ −𝑦 ) if 𝑗 is an anchor, { 𝑖 𝑗 𝑖 𝑗 vergence exiting in [7]. MOPSOLA constructs a multiob- 𝑑 = (4) jective model with both the space distance constraint and 2 2 (𝑥̂ − 𝑥̂ ) +(𝑦̂ − 𝑦̂ ) otherwise, 𝑖 𝑗 𝑖 𝑗 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 ̂ ̂ ̂ ̂ where (𝑥 ,𝑦 ) and (𝑥 ,𝑦 ) are estimated coordinates of 𝑖 𝑖 𝑗 𝑗 higher localization accuracy, the lower storage consumption, unknown nodes 𝑖 and 𝑗 . and the higher convergence. (i) eTh geometric topology con- eTh objective function of the geometric topology con- straint is considered to reduce the inaccuracy of localization. straint is denoted by (ii) The archive is dynamically maintained and limited in a maximum capacity to save the storage space for storing the 𝑛 𝑓 = ∑ ( ∑ 𝛿 + ∑ (1 − 𝛿 )). (5) Pareto optimal solutions. (iii) The global optimum solution 𝑖=𝑚+1 𝑗∈𝑁 is obtained to accelerate the convergence by adopting the 𝑖 𝑗∈ 𝑁 mechanism of proportion of selection. eTh simulation results eTh geometric topology constraint represents the con- have proved theproposedalgorithm caneeff ctivelyfind the nectivity constraint which dissatisefi s the current estimated multiobjective optimal solutions and achieve both the better positions of nonanchor nodes [7]. And 𝛿 is denoted by convergence speed and the better localization accuracy. 1 if 𝑑 >𝑅, 2. Multiobjective Localization Model 𝛿 = (6) 0 otherwise. The coordinates of unknown nodes need to meet both the space distance constraint and the geometric topology con- The space distance constraint and the geometric topology straint. The purpose of meeting the space distance constraint constraint imply the accuracy of the coordinates of the nodes. is to make the estimated coordinates close to the real values, The high accuracy of estimated coordinates of the unknown and meanwhile the purpose of meeting the geometric topol- nodes consequently lead to the small values of the two ogy constraint is to make the network topology unique to objective functions. er Th efore, estimating coordinates of the avoid forming a topological structure which is not in confor- unknownnodes canbemodeled to search theoptimum mity with the actual situation. solution for the multiobjective optimization issues, which Assume that 𝑛 nodes are deployed in two-dimensional can be obtained by decreasing both values of the objective space 𝑍 of WSN, including 𝑚 anchor nodes and 𝑛−𝑚 functions 𝑓 and 𝑓 . 1 2 unknown nodes with𝑚<𝑛 . Assuming the two nodes 𝑖 and 𝑗 being in the communication radius of each other, the 3. MOPSOLA internode ranging distance 𝑑 canbeobtainedbyRSSI ranging technology and denoted by 3.1. Mathematical Description of MOPSOLA. The optimal solution of multiobjective optimization issues is to n fi d the 𝑑 =𝑟 +𝑒 , (1) Pareto optimal solution [14]. Multiobjective optimization 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 𝑖𝑗 International Journal of Distributed Sensor Networks 3 Population Archive Multiobjective function calculation Individual optimal selection Maintenance of archive Global optimal selection Velocity and localization update New archive New population Final archive Figure 1: Overall framework of the multiobjective PSO. issue with 𝑢 -dimensional decision vectors and V objectives is In MOPSOLA, model the estimated coordinates of𝑛−𝑚 denoted by unknownnodes as thedecisionvectors,and thetwo objective functions defined by (3)–(5) consist of the objective function Minmize F(x) =(𝑓 (x),𝑓 (x),...,𝑓 (x)) 1 2 V F(x). er Th efore, from formulas (3)–(5) and (7),MOPSOLA (7) can be formulated in the optimum mathematical form as s.t. x ∈[x , x ], 𝐿 𝑈 Minmize F(x) =(𝑓 (𝑥̂ ,𝑦̂),𝑓 (𝑥̂ ,𝑦̂)) where x =(𝑥 ,𝑥 ,...,𝑥 )∈𝑋∈𝑅 and F =(𝑓 ,𝑓 , 1 𝑖 𝑖 2 𝑖 𝑖 1 2 𝑢 1 2 ...,𝑓 )∈𝑌∈𝑅 . x is called the decision vector belonging to (8) s.t.(𝑥̂ ,𝑦̂)∈(𝑥̂ ,𝑦̂ ),(𝑥̂ ,𝑦̂ ) 𝑖 𝑖 𝐿 𝐿 𝑈 𝑈 the 𝑢 -dimensional decision space 𝑋 ,which is corresponding to 𝑢 -particles in PSO. x and x are lower and upper bound 𝐿 𝑈 𝑖 = 𝑚+1,𝑚+2,...,𝑛, constraints of the particle range, respectively. F is the objec- tive vector belonging to the V-dimensional objective space 𝑌 . where decision vectors x =(𝑥̂ ,𝑦̂) (𝑖 = 𝑚 + 1,𝑚 + 2,...,𝑛) 𝑖 𝑖 eTh objective function F(x) defines mapping functions from are the estimated coordinates corresponding to particles in thedecisionspace to theobjective space. eTh setofall the ̂ ̂ ̂ ̂ PSO, (𝑥 ,𝑦 )and (𝑥 ,𝑦 )are thelower andupper bound 𝐿 𝐿 𝑈 𝑈 particles meeting the constraints forms the decision space constraint values, 𝑓 is the objective function of the space feasible setΩ={x ∈𝑅 | x ∈[x , x ]}. 𝐿 𝑈 distance constraint, and 𝑓 is the objective function of the Some concepts related with MOPSOLA are described as geometric topology constraint. Therefore the decision space follows. is 𝑢=𝑛 − 𝑚 dimension and the objective space is V =2 dimension; that is, the coordinates of unknown nodes are (i) For two feasible solutions x , x ∈Ω in the processing 𝑎 𝑏 𝑢=𝑛−𝑚 particles,𝑓 and𝑓 are the V =2 objective functions. of PSO, if, ∀𝑖 = 1,2,..., V, 𝑓 (x )≤𝑓 (x )∧∃𝑗 = 1 2 𝑖 𝑏 𝑖 𝑎 Obtaining the multiobjective Pareto optimal solution 1,2,..., V, 𝑓 (x )<𝑓 (x ),thencall x dominate x , 𝑗 𝑏 𝑗 𝑎 𝑏 𝑎 is the ultimate goal of building a multiobjective optimal denoted by x ≺ x ,and keep x as optimization 𝑏 𝑎 𝑏 model for localization issues, which meets both the space results. distance constraint and the geometric topology constraint. (ii) The Pareto optimal solution x∗ is the decision vector Therefore the main essence of MOPSOLA can be described which satisfies ¬∃x ∈Ω: x ≺ x∗. as determining the dominant relationship according to the 󸀠 󸀠 (iii) 𝑆={ x ∈Ω|¬∃x ∈Ω,𝑓 (x )≤𝑓 (x),𝑗 = 1,2,..., V} 𝑗 𝑗 decision space feasible set Ω and the Pareto front F(x )= ∗ ∗ ∗ ∗ ∗ ∗ ∗ constructs the set of Pareto optimal solution obtained {(𝑓 (𝑥̂ ,𝑦̂ ),𝑓 (𝑥̂ ,𝑦̂ )) | x =(𝑥̂ ,𝑦̂ )∈𝑆} ,𝑖 = 𝑚+1,𝑚+ 1 2 𝑖 𝑖 𝑖 𝑖 𝑖 𝑖 𝑖 from all of the Pareto optimal solutions. 2,...,𝑛 , saving Pareto optimal solution set𝑆 in an archive and updating the position and the velocity of multiobjective PSO. (iv) F(x)={F(x∗) = (𝑓 (x∗),𝑓 (x∗),...,𝑓 (x∗)) | x∗∈ 1 2 V 𝑆} forms the Pareto front consisting of the values of objective functions corresponding to the Pareto opti- 3.2. Describing of MOPSOLA mal set. (v) eTh purpose of optimization is to n fi d the Pareto opti- 3.2.1. Overall Framework. Shown as Figure 1,the framework mal solution. of theproposedmultiobjectivePSO algorithmincludes some Iteration 4 International Journal of Distributed Sensor Networks key operators such as maintenance of archive, global opti- deleting some of the members when the maximum capacity mum selection, and the velocity and localization update. eTh is reached. Consequently, a space will be maintained for the particle population relies on an archive to save Pareto optimal new solutions entering into the archive. solutions during the iterative process and selecting the global However, due to nondominated property of Pareto opti- optimum from these solutions, which is the key point that mal solutions, namely, there is no difference between the solu- the multiobjective PSO is dieff rent from the traditional single tions, a concept of intensive distance is introduced to evaluate objective localization. thesolutionquality.Generally thepoint (solution) in asparse eTh refore, the localization issue is modeled as a multiob- area which has bigger intensive distance is better than the jective optimization model in MOPSOLA, and two operators, point in an intensive area in the objective space [15]. which are the dynamic maintenance operator for the archive Den fi ition 1. Given set 𝑆 is the set of Pareto optimal solutions andthe global optimumselection operator basedonpropor- in the archive and 𝑥 ∈𝑆 is a Pareto optimal solution, then tion of selection, aredesignedtobesuitablefor thelimited the intensive distance𝐷𝑖𝑠 of𝑥 is defined as the average value energy and the poor computing power of WSN nodes. 𝑖 𝑖 of the minimum distance 𝑑𝑖𝑠 and the second minimum dis- (i) In the multiobjective function calculation level, func- 2 tance𝑑𝑖𝑠 between𝑥 and other Pareto optimal solutions𝑥 ∈ 𝑖 𝑗 tions as formulas (3)–(5) are calculated according to 1 2 𝑆 in the archive. 𝑑𝑖𝑠 , 𝑑𝑖𝑠 ,and 𝐷𝑖𝑠 are computed as 𝑖 𝑖 𝑖 all particles, that is, all estimated nodes’ coordinates. (ii) In the individual optimal selection level, the personal optimum selection operator works. Based on the con- 𝑑𝑖𝑠 = min{𝐷 |𝑥 ∈𝑆, 𝑥 ∈ ,𝑆 𝑗 = 1,2,...,𝑐, 𝑗 =𝑖̸ }, 𝑖 𝑖 𝑗 cept of Pareto optimality, the 𝑡 of each particle is 2 1 chosen between the particle’s current location and its 𝑑𝑖𝑠 = min{𝐷 |𝐷 >𝑑𝑠𝑖 ,𝑥 ∈𝑆, 𝑥 ∈𝑆, 𝑖 𝑗 𝑖 𝑖 historical 𝑡 dynamically. 𝑗 = 1,2,...,𝑐, 𝑗 =𝑖̸ }, (iii) In the global optimal selection level, the global opti- mum selection operator works. eTh proportion of 1 2 (𝑑 +𝑑𝑠𝑖 ) selection is set for each Pareto optimal solution based 𝑖 𝑖 𝐷𝑖𝑠 = , on intensivedistance, andaglobal optimumfor each particle is selected by proportion of selection. (10) (iv) In the velocity and localization update level, the posi- tion and velocity update operator works for all indi- 2 2 where 𝐷 = √∑ (𝑓 (𝑥 )−𝑓 (𝑥 )) is the objective con- 𝑘=1 𝑘 𝑖 𝑘 𝑗 vidual particles. eTh update processissimilar to the straint distance between 𝑥 and 𝑥 and 𝑓 (𝑘=1,2) is the traditional single objective PSO as 𝑖 𝑗 𝑘 objective function, 𝑐 is the number of solutions. V (𝑡+1 ) =𝜔 V (𝑡 )+𝑐 𝑟 (𝑝𝑏𝑒𝑠𝑡 −ℎ (𝑡 )) 𝑖 𝑖 1 1 𝑖 The intensive distances of Pareto optimal solutions are +𝑐 𝑟 (𝑔𝑏𝑒𝑠𝑡 − ℎ (𝑡 )), (9) sorted and the smaller ones are deleted in order to limit the 2 2 𝑖 number of members in the archive. ℎ (𝑡+1 ) =ℎ (𝑡 ) + V (𝑡+1 ), 𝑖 = 𝑚+1,𝑚+2,...,𝑛, 𝑖 𝑖 𝑖 It is ensuredthatthe membersinthe archivecan be limitedinthe maximumcapacitybythe archivemaintenance where V is the velocity of the 𝑖 th particle, ℎ =(𝑥̂ ,𝑦̂) operator, which avoids the nondominated solutions increas- 𝑖 𝑖 𝑖 𝑖 is the estimated coordinates of the 𝑖 th particle vector, ing inn fi itely to reduce the ecffi iency along with the evolution. 𝑡 is the best solution for the 𝑖 th particle, 𝑡 is At the same time, the most intense individual is deleted, and the best solution for the population, 𝜔 is the inertia the uniform distribution of the Pareto front is ensured by weight, 𝑐 and 𝑐 are constants, and 𝑡 is the iteration saving lots of scattered individuals. 1 2 time. (v) In the maintenance of archive level, the archive main- 3.2.3. Global Optimum Selection Operator. In the traditional tenance operator works. eTh maximum capacity of single objective PSO algorithm, it is tolerable to use the opti- archive is set as 𝑥𝑎𝐴𝑟𝑀𝑐 and the archive is dynami- mal solution with the best tfi ness as the global optimum 𝑡 cally updated according to the density distance in the because the 𝑡 of every particle is the same. However, in objectivespace of theParetooptimal solution to save multiobjective PSO the population generates more than one the storage space. nondominated 𝑡 leading difference among some particle global optimums, which results to necessarily choose the 3.2.2. Archive Maintenance Operator. AmultiobjectivePSO appropriate global optimum. Based on the intensive distance, algorithm does not produce a unique solution but a set of the global optimum is selected for each particle by adopting Pareto optimal solutions at the end of each iteration; therefore the proportion of selection. an archiveisusedtosavethese Pareto optimalsolutions and the members in the archive become the n fi al solution set Den fi ition 2. Given that the number of Pareto optimal solu- when the iteration stops. To adapt to the limited storage space tions in the archive of the current iteration is 𝑐 with 𝑐≤ of a WSN node, the members in an archive are limited by 𝑥𝑎𝐴𝑟𝑀𝑐 , a proportion of selection 𝜉 of a Pareto optimal 𝑔𝑏𝑒𝑠 𝑔𝑏𝑒𝑠 𝑔𝑏𝑒𝑠 𝑔𝑏𝑒𝑠 𝑝𝑏𝑒𝑠 𝑖𝑗 𝑖𝑠 𝑝𝑏𝑒𝑠 𝑖𝑗 𝑖𝑗 𝑝𝑏𝑒𝑠 𝑖𝑗 International Journal of Distributed Sensor Networks 5 solution 𝑥 ∈𝑆 is defined as the rate of its intensive distance 5.5 to the sum of intensive distances in the archive according to 4.5 𝐷𝑖𝑠 𝜉 = , 𝑖 = 1,...,𝑐. (11) 𝑖 𝑐 ∑ 𝐷𝑖𝑠 𝑘=1 3.5 Formula (11) implies that the larger intensive distance a Pareto optimal solution has, the bigger proportion of selec- 2.5 tion it has; therefore it has a bigger proportion to be selected 0 100 200 300 400 500 600 700 800 900 1000 as the global optimum. Iteration PAES MOPSOLA 3.2.4. The Pseudo Code of the MOPSOLA. The main com- ponents of MOPSOLA, including multiobjective function Figure 2: The comparison of convergence rate between MOPSOLA calculation, individual optimal selection, maintenance of and PAES. archive, global optimal selection, and velocity and localiza- tion update, are described as function MopsoFuc with pseu- docode in Algorithm 1.Where thenodeisthe classofnode further applied to evaluate the performance of all the nodes information with four members of 𝑛𝑜𝑑𝑒.𝑥 , 𝑛𝑜𝑑𝑒.𝑦 , 𝑛𝑜𝑑𝑒.𝑖𝑑 , being estimated: and 𝑛𝑜𝑑𝑒.𝑎𝑛𝑐ℎ𝑜𝑟𝑔𝑓 corresponding to the 𝑥 coordinate, 𝑦 coordinate,idnumber, andanchorflag of anode. 𝑡 is the 2 2 ̂ ̂ (𝑥 −𝑥 ) +(𝑦 −𝑦 ) current iteration time and 𝑡 is the maximum iteration 𝑖 𝑖 𝑖 𝑖 (12) max 𝑔𝑙𝑒𝐸𝑟𝑟𝑜𝑟𝑆𝑛𝑖 = × 100%, time.Theother variableshavethe consistent meaningwith thesamenamed variablesaforementioned. 𝑛−𝑚 2 2 ∑ (𝑥̂ −𝑥 ) +(𝑦̂ −𝑦 ) 𝑖=1 𝑖 𝑖 𝑖 𝑖 (13) 𝐴 V = × 100%. (𝑛−𝑚 )×𝑅 4. Simulations and Analysis 4.2. eTh Efficiency of the Tow Objective Functions To validate the performance of the MOPSOLA, the simu- lationshavebeendonetotestMOPSOLA andthe other 4.2.1. eTh Convergence Rate. Figure 2 is the comparison of two algorithms, the traditional PSO and PASE [7], in Matlab objective function 𝑓 about the convergence rate between 2010b. The simulations have been done using MOPSOLA MOPSOLA and PAES. MOPSOLA and PAES start to con- with objective functions 𝑓 and 𝑓 ,and they also have been 1 2 verge at the 400th iteration and 700th iteration, respectively. done using PSO with objective function 𝑓 and using PASE eTh result shows that MOPSOLA retains more outstand- [7] with objective functions 𝑓 and 𝑓 . 1 2 ing individuals to accelerate the algorithm convergence by avoiding the affection of selection and mutation operation on the next generation and adopting dynamic maintenance of 4.1. eTh Simulation and Evaluation Parameters archive combined with selecting the optimum by proportion of selection for maintaining much more outstanding individ- 4.1.1. eTh Simulation Parameters. Total 𝑛 nodes are randomly uals. deployed in 100 m × 100 m area with 𝑚 anchor nodes being randomly generated from these nodes. Assuming that the RSSI ranging error 𝑒 follows a Gaussian distribution with a 4.2.2. eTh Localization Accuracy. The single localization 2 2 2 2 errors of 80 unknown nodes has been simulated to evaluate zero mean and variance 𝜎 , 𝜎 =𝛽 𝑟 , 𝛽 = 0.1 . eTh max- the localization accuracy under the condition of 20% anchor imum capacity of the archive 𝑥𝑎𝐴𝑟𝑀𝑐 is 10 and the max nodes by using MOPSOLA and PSO algorithm. iteration time 𝑡 is 1000. max (i) eTh simulation results show that the maximum and the minimum single localization error are 81.13% 4.1.2. eTh Localization Errors. The localization error is gen- and1.52%,respectively, in MOPSOLAcomparedto erally related to the node communication radius. Based on 94.36% and 5.52%, respectively, in PSO. the communication radius, two kinds of localization errors are defined to evaluate the localization performance of the (ii) The ranges of 𝑔𝑙𝑒𝐸𝑟𝑟𝑜𝑟𝑆𝑛𝑖 are counted to further proposed algorithm. One is the single localization error evaluate the accuracy shown in Table 1.Itcan been 𝑔𝑙𝑒𝐸𝑟𝑟𝑜𝑟𝑆𝑛𝑖 of an unknown node den fi ed by formula (12), seen that 24 nodes’ single localization errors fell into whichisusedtoevaluatethe performanceofeachnode 0∼5% in MOPSOLAcomparedto10nodes’inPSO, being estimated. eTh other is the average localization error and 5 nodes’ single localization errors are over 30% in 𝐴 V of the network defined as formula (13),which is MOPSOLA compared to 31 nodes’ in PSO. Objective function f 𝑒𝑟𝐸𝑟𝑟𝑜𝑟 𝑖𝑗 𝑖𝑗 𝑒𝑟𝐸𝑟𝑟𝑜𝑟 𝑙𝑎 6 International Journal of Distributed Sensor Networks 𝑆 =MopsoFuc( , 𝑛 , 𝑚 , 𝑅 ) node: class of node information 𝑛 : total number of nodes 𝑚 : anchor nodes 𝑅 : node communication radius 𝑆 : set of Pareto optimal solutions in the archive (1) Initialize each parameter, 𝜔 = 0.7298 , 𝑐 =𝑐 = 1.4962, 𝑥𝑎𝐴𝑟𝑀𝑐 =10 1 2 (2) Initialize ℎ and V for each particle randomly then 𝑡 ← (3)While𝑡≤𝑡 Do max // Step 1. Multi-objective Function Calculation (4)ForeachparticleDo (5)Compute .𝑓1 and .𝑓2 using class (6)End // Step 2. Individual Optimal Selection (7)Foreach 𝑡 Do (8)Compute 𝑡 .𝑓1 and 𝑡 .𝑓2 using class (9)If 𝑡 ≺ (10) 𝑡 ← 𝑡 (11)ElseIf ≺ 𝑝𝑡 (12) 𝑡 ← (13)Else 𝑎 ← (14)If𝑎≤ 0.5 then 𝑡 ← 𝑡 (15)Else 𝑡 ← (16)End // Step 3. Maintenance of Archive (17) While Receive 𝑡 Do (18) 𝐴𝑟𝑐𝑝𝑚𝑒𝑇← 𝐴𝑟ℎ𝑐 𝑖 V𝑒∪𝑝𝑠𝑒𝑏𝑡 (19) Delete repetitive solution in𝐴𝑐𝑟𝑝𝑚 (20) For every member in𝐴𝑐𝑟𝑝𝑚 Do (21) IF dominated then Delete (22)End (23) 𝑐← number of TempArc (24)IF𝑐≤𝐴𝑥𝑎𝑀𝑐𝑟 (25) 𝐴𝑟ℎ𝑐 𝑖 V𝑒←𝑇𝐴𝑐𝑟𝑝𝑚𝑒 (26)ElseCompute 𝐷𝑖𝑠 of𝐴𝑐𝑟𝑝𝑚 (27) Descending sort of𝐴𝑐𝑟𝑝𝑚 (28) 𝐴𝑟ℎ𝑐 𝑖 V𝑒←𝑇𝐴𝑐𝑟𝑝𝑚𝑒 (29)End // Step 4. Global Optimal Selection (30) For every member of 𝐴𝑟ℎ𝑐 𝑖 V𝑒 Do (31)Compute 𝐷𝑖𝑠 ; (32)Compute 𝜉 ; (33)End (34)ForeveryparticleDo (35)Usingroulettewheeltochoose 𝑡 according to 𝜉 ; (36)End // Step 5. Velocity and Localization Update (37) V(𝑡 + 1) ← 𝜔 V(𝑡) + 𝑐 𝑟 (𝑝𝑏𝑒𝑠𝑡 − ℎ(𝑡)) + 𝑐 𝑟 (𝑔𝑏𝑒𝑠𝑡 − ℎ(𝑡)) 1 1 2 2 (38) ℎ(𝑡 + 1) ← ℎ(𝑡) + V(𝑡 + 1) (39) End (While) (40)𝑆←𝐴ℎ𝑐𝑟 𝑖 V𝑒 Algorithm 1: eTh proposed MOPSOLA in pseudocode. Table 1: eTh distribution of 𝑔𝑆𝑖𝑛 ranges. 𝑔𝑆𝑖𝑛 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 𝑙𝑒𝐸𝑟𝑟𝑜𝑟 𝑙𝑒𝐸𝑟𝑟𝑜𝑟 𝑔𝑏𝑒𝑠 𝑇𝑒 𝑇𝑒 𝑇𝑒 𝑇𝑒 𝑝𝑏𝑒𝑠 𝑖𝑐𝑙𝑒𝑝𝑎𝑟𝑡 𝑝𝑏𝑒𝑠 𝑝𝑏𝑒𝑠 𝑝𝑏𝑒𝑠 𝑟𝑎𝑛𝑑 𝑖𝑐𝑙𝑒𝑝𝑎𝑟𝑡 𝑝𝑏𝑒𝑠 𝑏𝑒𝑠 𝑖𝑐𝑙𝑒𝑝𝑎𝑟𝑡 𝑝𝑏𝑒𝑠 𝑝𝑏𝑒𝑠 𝑖𝑐𝑙𝑒𝑝𝑎𝑟𝑡 𝑝𝑏𝑒𝑠 𝑛𝑜𝑑𝑒 𝑝𝑏𝑒𝑠 𝑝𝑏𝑒𝑠 𝑝𝑏𝑒𝑠 𝑛𝑜𝑑𝑒 𝑖𝑐𝑙𝑒𝑝𝑎𝑟𝑡 𝑖𝑐𝑙𝑒𝑝𝑎𝑟𝑡 𝑖𝑐𝑙𝑒𝑝𝑎𝑟𝑡 𝑝𝑏𝑒𝑠 𝑛𝑜𝑑𝑒 International Journal of Distributed Sensor Networks 7 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% 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% 40 40 35 35 25 25 20 20 15 15 10 10 60 70 80 90 100 110 120 130 140 150 160 5 10 15 20 25 30 The total number of nodes Anchor nodes proportion (%) PSO PSO PAES PAES MOPSOLA MOPSOLA Figure 3: Localization errors with different node number. Figure 4: Localization errors with different anchor node propor- tion. (iii) From the comparison, it is obvious that the single nodes does little effect on the errors when it is over localization errors by using MOPSOLA are lower than 100. It is obvious that the errors created by using PAES those by using PSO. This is because the geometric and MOPSOLA are lower than the errors created by topology constraint is limited in a reasonable topol- using PSO due to the geometric topology constraint ogy by the objective function 𝑓 ,which decreasesthe being considered by the rfi st two methods. inaccuracy of the localization. (ii) Furthermore, the MOPSOLA algorithm has better performance than PAES due to the estimation accu- 4.3.TheRobustPerformance of theMOPSOLA. The simula- racy being aeff cted by the selection and mutation tions focusing on the average localization errors have been operators in PAES, and the average error reduces done to evaluate the robustness of the MOPSOLA in case of 4.84%, 5.12%, 3.47%, 1.50%, 1.09%, and 2.45%, respec- different situations with varying nodes density, anchor nodes, tively,comparedtoPAESwithnodenumberof60, 80, and network connectivity. 100, 120, 140, and 160. (iii) The further analysis shows that although the network 4.3.1. eTh Eeff ct of the Network Nodes Density. Table 2 and topology changes following the nodes increasing or Figure 3 report the average localization errors, measured decreasing, the MOPSOLA is robustness in terms of under the condition of changing the network nodes density having the average localization errors lower than 15% and the total number of nodes, while holding on the anchor with nodes over 80. node proportion as 20% and the communication radius𝑅= 25 m. 4.3.2. eTh Eeff ct of the Proportion of Anchor Nodes. Table 3 (i) All the average localization errors of three methods and Figure 4 show the relationship between the average reduce as the nodes increasing, and the number of localization errors and the anchor node proportion while Average localization error (%) Average localization error (%) 8 International Journal of Distributed Sensor Networks Table 4: Localization errors with different network connectivity in different algorithms. Communication radius 𝑅 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% holding on the total number of nodes 𝑛 = 100 and com- munication radius𝑅=25 m but with different anchor node proportion. (i) All the average localization errors decrease as the an- chor 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 local- ization algorithm with the same anchor node propor- tion due to the two objective functions being consid- ered in MOPSOLA and PAES compared to only one 10 15 20 25 30 35 objective function being considered in PSO without Node communication radius the topology constraint. For example, the average PSO localization error in MOPSOLA reduces 15.09% and PAES 8.39% compared with the traditional PSO method, MOPSOLA respectively, under the condition of 10% and 20% Figure 5: Localization errors with different network connectivity in anchor node proportion. different algorithms. (iii) MOPSOLA has slightly higher localization accuracy than PAES under the condition of the same anchor node proportions. Compared with PAES, MOPSOLA PAES begins to rising. eTh reason for this phe- reduces the average localization error 1.95% and nomenon is caused by rising of number of the first- 0.05%, respectively under the condition of 10% and level neighbor and the second-level neighbor [7] 20% anchor node proportion. resulting from the bigger communication radios, (iv) MOPSOLA is robust with no performance declining which further leads to increasing of the ranging error in terms of the average localization errors being lower of two classes unknown nodes defined in PAES. than 15% when the anchor node proportion is over (iii) The MOPSOLA is robust with no obvious perfor- 10%. These results prove that varying the anchor node mance decline in terms of the average localization proportion will not affect the robust performance of errors kept lower than 15% when the node commu- MOPSOLA. nication radius is over 20 m. eTh simulation resultsanalyzedinthissection have 4.3.3. eTh Eeff ct of the Network Connectivity. Table 4 and proved that, because the model of multiobjective localization Figure 5 show the relationship between the average localiza- considers the influence of geometric topology constraint 𝑓 , tion errors and the network connectivity while holding the 2 some localization results which violate the constraint will total number nodes 𝑛 = 100 and 20% anchor node pro- be modified to further improve the localization accuracy. portion, but with different communication radius 𝑅 to change Furthermore, the optimum by proportion of selection can the network connectivity. obtain closer result to the real localization and further (i) eTh results show that the localization accuracy of each improve the localization accuracy. algorithm has the trend of rising as the increasing of the node communication radius. This is because the 4.4. eTh Time Complexity of the Algorithm. Table 5 shows the increasing of the communication radius will enable time complexity of three algorithms with unknown nodes the unknown nodes to communicate with more number𝑀=𝑛−𝑚 , the size of particle swarm 𝑁 ,iterations neighbor nodes and further improve the search per- number 𝑡 ,and archivesize 𝑥𝑎𝐴𝑟𝑀𝑐 . eTh time complexity max formance of intelligent optimization algorithms. of MOPSOLA is obviously higher than that of PSO and PAES. (ii) MOPSOLA can keep the average localization errors Table 6 shows the operation times of three algorithms declining when the node communication radius with total nodes 𝑛 = 100 , anchor nodes 𝑚=20 ,and reaches to 30 m, while the localization error using communication radius𝑅=25 .Itcan more clearlybeseen Average localization error (%) International Journal of Distributed Sensor Networks 9 Table 5: e Th time complexity. IEEE Communications Surveys & Tutorials,vol.13, no.1,pp. 68– 96, 2011. Algorithm Time complexity [2] A. F. Assis, L. F. M. Vieira, M. T. R. Rodrigues, and G. L. PSO 𝑂(𝑡 ) Pappa, “A genetic algorithm for the minimum cost localization max PAES 𝑂(𝑡 𝑀⋅𝐴𝑥𝑎)𝑀𝑐𝑟 problem in wireless sensor networks,” in Proceedings of the IEEE max Congress on Evolutionary Computation (CEC ’13),pp. 797–804, MOPSOLA 𝑂(𝑡 + 𝑡 𝑀(𝑁 + 𝑎𝑥)𝐴𝑟 ) max max IEEE, Cancun, ´ Mexico, June 2013. [3] M.Vecchio,R.Lo´pez-Valcarce, and F. Marcelloni, “An effective Table 6: Iterative operation time of different algorithms. metaheuristic approach to node localization in wireless sensor networks,” in Proceedings of the 8th IEEE International Confer- Iterations ence on Mobile Ad-hoc and Sensor Systems (MASS ’11),pp. 143– 1 10 100 1000 number 145, Valencia, Spain, October 2011. 0.338 s 2.192 s 30.492 s 305.680 s PSO [4] H. A. Nguyen, H. Guo, and K.-S. Low, “Real-time estimation of sensor node’s position using particle swarm optimization with 0.106 s 1.170 s 11.434 s 115.965 s PAES log-barrier constraint,” IEEE Transactions on Instrumentation MOPSOLA 2.723 s 65.396 s 559.081 s 6622.944 s and Measurement, vol. 60, no. 11, pp. 3619–3628, 2011. [5] X.Hu, S. Shi, andX.Gu, “Animprovedparticleswarm opti- mization algorithm for wireless sensor networks localization,” that thetimecomplexity of MOPSOLAishigherthanthatof in Proceedings of the 8th International Conference on Wireless the two compared algorithms. Communications, Networking and Mobile Computing (WiCOM eTh reason is that the two main operating levels of archive ’12), pp. 1–4, IEEE, Shanghai, China, September 2012. maintenance operator and global optimum selection operator [6] L. Gong, J. Sun, W. Xu, and J. Xu, “Research and simulation of in MOPSOLA will cost more time to repeatedly calculate and node localization in WSN based on Quantum particle swarm compare the values of two objective functions and delete the optimization,” in Proceedings of the 11th International Sympo- dominated solutions to obtain the elitism archived strategy, sium on Distributed Computing and Applications to Business, which also result in higher time complexity. Engineering and Science (DCABES ’12), pp. 144–148, Guilin, China, October 2012. [7] M. Vecchio, R. Lo´pez-Valcarce, and F. Marcelloni, “A two- 5. Conclusions objective evolutionary approach based on topological con- straints for node localization in wireless sensor networks,” MOPSOLA adopts multiobjective localization with objective Applied Soft Computing Journal ,vol.12,no.7,pp.1891–1901,2012. functions consisting of space distance constraint and geo- [8] M.Shokrianand K. A. High,“Applicationofamultiobjective metric topology constraint and solves optimal solutions by multi-leader particle swarm optimization algorithm on NLP adopting both the dynamic maintenance operator for archive and MINLP problems,” Computers and Chemical Engineering, and global optimal selection operator based on proportion of vol. 60, pp. 57–75, 2014. selection. Compared with traditional PSO localization algo- [9] E.Zhang,Y.Wu, andQ.Chen, “A practicalapproachfor rithm, MOPSOLA can improve the localization accuracy and solving multi-objective reliability redundancy allocation prob- decrease the convergence rate. Compared with similar mul- lems using extended bare-bones particle swarm optimization,” tiobjective localization algorithm PAES, the convergence rate Reliability Engineering and System Safety,vol.127,pp. 65–76, is greatly enhanced and the localization accuracy is slightly increased. Under the premise of ensuring localization accu- [10] C. Duan, X. Wang, S. Shu, C. Jing, and H. Chang, “er Th mo- racy,how to furtherimprove theconvergence rate andreduce dynamic design of Stirling engine using multi-objective particle the energy consumption will be the next research emphasis. swarm optimization algorithm,” Energy Conversion and Man- agement, vol. 84, pp. 88–96, 2014. [11] A. Kaveh and K. Laknejadi, “A novel hybrid charge system Conflict of Interests search and particle swarm optimization method for multi- objective optimization,” Expert Systems with Applications,vol. eTh authors declare that they have no conflict of interests to 38, no. 12, pp. 15475–15488, 2011. this work. [12] H. Peng, R. Li, L. L. Cao, and L. X. Li, “Multiple swarms multi- objective particle swarm optimization based on decomposi- Acknowledgments tion,” Procedia Engineering,vol.15, pp.3371–3375,2011. [13] J.Wei andM.Zhang,“Attraction basedPSO with sphere Thisworkissupported by theNationalNatural ScienceFoun- search for dynamic constrained multi-objective optimization dation of China under Grant no. 61373126, the Natural Sci- problems,” in Proceedings of the 13th Annual Genetic and Evo- ence Foundation of Jiangsu Province of China under Grant lutionary Computation Conference (GECCO ’11),pp. 77–78, no. BK20131107 and the State Scholarship Fund by China IEEE, Dublin, Ireland, July 2011. Scholarship Council. [14] M. G. Gong,L.C.Jiao, D. D. Yang,and W. P. Ma,“Research on evolutionary multi-objective optimization algorithms,” Journal of Software ,vol.20, no.2,pp. 271–289, 2009. References [15] W. Li and X. Zhang, “An improved multi-objective particle [1] R. V. Kulkarni, A. Forster, and G. K. Venayagamoorthy, “Com- swarm optimization algorithm based on pareto,” Computer Sim- putational intelligence in wireless sensor networks: a survey,” ulation,vol.27, pp.96–99,2010. 𝑐𝑀 𝑁𝑀 𝑁𝑀

Journal

International Journal of Distributed Sensor NetworksSAGE

Published: Aug 13, 2015

There are no references for this article.