# Localization of Large-Scale Wireless Sensor Networks Using Niching Particle Swarm Optimization and Reliable Anchor Selection

Authors: Huanqing Cui; Yongquan Liang; Chuanai Zhou; Ning Cao
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Due to uneven deployment of anchor nodes in large-scale wireless sensor networks, localization performance is seriously affected by two problems. The first is that some unknown nodes lack enough noncollinear neighbouring anchors to localize themselves accurately. The second is that some unknown nodes have many neighbouring anchors to bring great computing burden during localization. This paper proposes a localization algorithm which combined niching particle swarm optimization and reliable reference node selection in order to solve these problems. For the first problem, the proposed algorithm selects the most reliable neighbouring localized nodes as the reference in localization and using niching idea to cope with localization ambiguity problem resulting from collinear anchors. For the second problem, the algorithm utilizes three criteria to choose a minimum set of reliable neighbouring anchors to localize an unknown node. Three criteria are given to choose reliable neighbouring anchors or localized nodes when localizing an unknown node, including distance, angle, and localization precision. The proposed algorithm has been compared with some existing range-based and distributed algorithms, and the results show that the proposed algorithm achieves higher localization accuracy with less time complexity than the current PSO-based localization algorithms and performs well for wireless sensor networks with coverage holes.


---

## Body

## 1. Introduction

Recently, wireless sensor networks (WSNs) have been applied in various applications, where the sensor nodes’ location information helps us to understand the sensed data in spatial context, and it is also useful for the other protocols including coverage, deployment, and routing [1, 2]. However, sensor nodes are usually randomly deployed by a vehicle robot or aircraft, so they have no prior knowledge of their locations. A simple solution is to equip each sensor node with a global positioning system (GPS) device, but the weakness of high cost and energy consumption makes it is infeasible for large-scale deployment. Therefore, the determination of sensor nodes’ positions, which is referred to aslocalization, is one of key technologies of WSNs.The development of microelectronic, wireless communication leads to applications of large-scale WSNs containing hundreds even thousands of sensor nodes deployed in a prohibitively large region. For example, CitySee [3] project deployed 1,200 sensor nodes in an urban area, and LAINet [4] is deployed in a whole forest. Because distributed localization approach allows each sensor node to estimate its own location without any central control or computation unit, which alleviates large communication overhead, so they are more suitable for localization of large-scale WSNs than centralized methods. Further, because many applications require absolute positions such as longitude and latitude, the localization algorithm should beanchors based[5, 6], whereanchors are the sensor nodes knowing their global positions, and the rest sensor nodes, referred to asunknown nodes, are localized based on beacon messages broadcasted by anchors. The localization procedure is often iterative because anchors are significantly less than unknown nodes, so some unknown nodes are localized by their neighbour localized unknown nodes instead of anchors. Both the anchors and localized unknown nodes are referred to asreference nodes in this paper.Due to random deployment of WSNs, the anchors are not evenly distributed, so localization performance is seriously affected by two problems. The first is that some unknown nodes lack enough noncollinear neighbouring anchors to localize themselves accurately. The second is that some unknown nodes have many neighbouring anchors to bring great computing burden during localization. This paper proposes an algorithm combining niching particle swarm optimization (PSO) and reliable references selection to conquer the above problems, in order to localize as many unknown nodes as possible with high localization precision. The main contributions contain the following:(i)
It proposes a reliable reference node selection approach based on localization precision, distance to unknown node, and degree of collinearity among reference nodes, in order to obtain a minimum and sufficient set of the best neighbouring references to localize an unknown node.(ii)
It presents a niching PSO algorithm to localize an unknown node and selects the best parameters and stop criteria of PSO according to localization precision and number of iterations, in order to conquer ambiguous localization and improve localization precision.(iii)
It presents localization algorithms for unknown nodes with less than three neighbour reference nodes, in order to localize as many unknown nodes as possible while guaranteeing localization precision.The organizations of the rest of this paper are as follows. Section2 briefly reviews existing localization algorithms for WSNs. Section 3 introduces localization problem and PSO algorithm and presents basic idea of the proposed algorithm. Sections 4, 5, and 6 propose details of our localization algorithm, namely, reliable reference node selection, niching PSO-based localization, and localization algorithms for unknown nodes with less than three neighbour reference nodes. Section 7 analyses time and communication complexities of the proposed algorithm in theory and compares the proposed algorithm with the other algorithms by simulations. The conclusion and future works are given in Section 8.


## 2. Related Works

Lots of localization algorithms have been developed, and most of them consist of two stages: measurement of geographical information between sensor nodes and estimation of positions of unknown nodes. According to different geographical information used in localization, these algorithms can be classified intorange-free andrange-based.Typical range-free algorithms include centroid, MDS (Multidimensional Scaling), and DV-hop (Distance-Vector hop). Centroid uses the centroid [7] or weighted centroid [8] of positions of neighbour reference nodes as position estimation of an unknown node. These methods rely heavily on number of anchors, and their localization errors are large [9]. MDS [10] computes all pair-wise shortest path between sensor nodes and then applies MDS to get an initial map. Centralized computation is used to estimate positions of sensor nodes, which imposes heavy communication burden on WSNs. MDS can also be applied by each sensor nodes itself in a distributed scheme [11], but the distributed version requires a procedure of local maps combination to determine the entire layout, which increases complexity and is impossible to complete combination if there are many disjoint patches in a given WSN [10]. DV-hop [12] consists of two message flooding phases to determine average hop length between two anchors, and an unknown node estimates its position by trilateration when it receives at least three anchor messages. There is much room to improve localization accuracy of DV-hop, and many enhancements have been proposed, such as checkout DV-hop [13], selective 3-anchor DV-hop [13], DV-hop algorithm based on locally weighted linear regression [14], etc., but they also need flood messages through WSNs. Both MDS and DV-hop are based on the shortest path between sensor nodes, but this path is often zigzag especially in WSNs with coverage holes. To cope with this problem, new methods are utilized to estimate distances between sensor nodes in two-stage centralized range-free localization algorithm [9] and connectivity-based anchor-free three-dimensional localization algorithm [15], but they still need message flooding. Hence, range-free algorithms consume a considerable amount of power when they are applied to large-scale WSNs. Moreover, these algorithms perform satisfactorily when the network has a relatively even node distribution, but their performance is poor for the network of nonuniform node distribution [15].Range-based algorithms need equip additional hardware to measure distance or angle. The popular ranging techniques include RSS (Received Signal Strength), ToA (Time of Arrival), TDoA (Time Difference of Arrival), and AoA (Angle of Arrival) [16]. After obtaining range information between an unknown node and its neighbour reference nodes, equations about the location of this unknown node can be gained, and they can be solved by an optimization method, such as maximum likelihood [17], least-square calibration [18], second-order cone programming [19], etc. Because evolutionary algorithms require less computational efforts than traditional optimization algorithms, which are more suitable for implementation on individual sensor node [20], they have been pervasively applied to localization problems, such as artificial neural network [21], genetic algorithm [22], and fuzzy logic and extreme learning machines [23].PSO algorithm performs better in terms of localization accuracy, computational complexity and/or convergence speed compared with the other optimization methods [24–30]. PSO and BFA (Bacterial Foraging Algorithm) are applied to localize a WSN deployed by an unmanned aerial vehicle in [24], and simulation results showed that PSO is faster than BFA. The proposed method in [25] divides unknown nodes into two modes: sensor nodes with at least three neighbour reference nodes and sensor nodes with less than three neighbour reference nodes. For an unknown node of the second mode, it utilizes a similar DV-Distance [12] approach to estimate the distance to a multihop anchor and then applies PSO to localize. Gauss-Newton algorithm (GNA) and PSO are applied to localize the sparse WSNs in [26], and simulation results showed that PSO outperforms GNA with large pedometer error. H-best PSO (HPSO) proposed by [27] divides the swarm of particle into several subswarms, and each particle updates according to global and local best fitness. The hybrid PSO proposed in [28] replaces positions of a half of particles with positions close to the best particle, leading to faster convergence than standard PSO. The fuzzy-extreme learning machine with PSO [29] uses resultant force to move approximate node location closer to actual position. PSO-based improved DV-hop algorithm [30] uses PSO to correct estimated positions after DV-hop.Generally, localization algorithms utilize all neighbour reference nodes to estimate location of an unknown node, which may lead to high localization error, so a reliable anchor selection process is needed. The methods proposed in [31] select three anchors based on minimal hop counts to an unknown node. The selective 3-anchor DV-hop algorithm [13] selects any three noncollinear anchors to form a 3-anchor group and correspondingly generates a 3-anchor estimated position. Reliable anchor pair selection method [32] selects reliable anchor pairs by observing their average hop progresses and estimates the distances to the reliable anchors by geometric approximation of the node. These methods are DV-based, so they are not feasible for range-based localization algorithms. A concept ofconfidence value is introduced in [33] to alleviate error propagation effect in localization of underwater WSNs, and this value is defined as a decreasing function of localization error, but it does not consider other factors, such as collinearity of anchors and distances to unknown node.


## 3. Background and Basic Idea of Proposed Localization Algorithm

### 3.1. Localization Problem Statement

Definition 1 (anchors).
The sensor nodes whose positions are known before localization are calledanchors. The set of anchors of a WSN is denoted by AS=Ai∣i=1,2,⋯,M, where M is the number of anchors. The position of anchor Ai is denoted by xai,yai.Definition 2 (unknown nodes, actual position).
The sensor nodes that need to be located by a certain localization algorithm are calledunknown nodes. The set of unknown nodes of a WSN is denoted by US=Ui∣i=1,2,⋯,N-M, where N-M is the number of unknown nodes. Theactual positions of Ui is denoted by xui,yui, which is not known in real application.Definition 3 (neighbour).
LetR be the radius of communication range of sensor nodes. Given two sensor nodes C and D, if C is located in the radio range of D, C is referred to as aneighbour of D. Because all sensor nodes have the same communication range, D is also a neighbour of C.Definition 4 ((range-based) localization).
Give a WSN consists ofN sensor nodes, including M anchors and N-M unknown nodes, the distances between any pair of neighbour nodes can be measured. The (range-based) localization problem is to localize the unknown nodes using the positions of anchors and distances between neighbour nodes.Definition 5 (estimated position).
If an unknown node is localized during localization, it will get anestimated position, and it becomes alocalized unknown node. The estimated position of Ui is denoted by x^ui,y^ui.
Obviously, the purpose of localization is to makex^ui,y^ui=xui,yui for Ui.Definition 6 (reference nodes).
During localization, both anchors and localized unknown nodes are calledreference nodes. The set of reference nodes is denoted by RS=Bi∣i=1,2,⋯,M′,N≥M′≥M. The position of reference node Bi is denoted by xbi,ybi. Obviously, if Bi is anchor Aj, xbi,ybi=xaj,yaj; if Bi is localized unknown nodes Uk, xbi,ybi=x^uk,y^uk.Definition 7 (actual distance, measured distance, and estimated distance).
An unknown nodeUi and a reference node Bj have three types of distances:(i)
Actual distance: distance between the actual positions of Ui and Bj. It is denoted by dij.(ii)
Measured distance: distance measured by a certain technique. It is denoted by d~ij. Because any measurement technique has error e to some extent, we assume d~ij=dij+N0,dije, where N0,dije is a Gaussian distribution.(iii)
Estimated distance: distance between the estimated position of Ui and Bj. It is denoted by d^ij.
Figure1 shows an example of these types of distances between Ui and Bj.
Suppose unknown nodeUi has n neighbour reference nodes B1,B2,⋯,Bn, we can solve the following equations to get x^ui,y^ui:(1)d~ij=x-xbj2+y-ybj2j=1,2,⋯,nwhere x,y is unknown quantity to solve and xbj,ybj is position of Bj. Due to the distance measurement error e, x^ui,y^ui≠xui,yui, i.e., we cannot get the actual position of Bj in general case. Using estimated position x^ui,y^ui, the estimated distance d^ij is(2)d^ij=x^ui-xbj2+y^ui-ybj2
Since the actual distancedij is not known, the objective of localization is to minimize the difference between d^ij and d~ij. Therefore, the problem of localizing Ui is formulated as(3)min⁡fx,y=∑j=1nwjd^ij-d~ij2=∑j=1nwjx-xbj2+y-ybj2-d~ij2s.t.1-DOIR≤x-xbj2+y-ybj2≤R0≤x,y≤Lj=1,2,⋯,nwhere wj=1/d~ij/∑i=1n1/d~ij, which gives more influence to those reference nodes nearer to Ui, DOI represents thedegree of irregularity of the communication range of sensor nodes, and L is the side length of the deployment region of WSN. In real applications, the communication range of sensor nodes is not a perfect circle due to multipath fading, unstable signal propagation, and noise, so DOI is introduced in (3). Given DOI, the communication range of a sensor node varies randomly in different directions between an upper bound R and a lower bound 1-DOIR [34].
The first constraint guarantees the solution locates within the communication range of all neighbouring reference nodes, and the second constraint guarantees the solution locates within the deployment region. The third constraint denotesUi has n neighbour reference nodes.
Due to the distance measurement errore, f(x,y) in (3) is often a multimodal function, so we have to use optimization algorithm to solve it. It has been proved that PSO can solve this problem well in related references; this paper tries to improve its performance further.Figure 1
Three types of distances between sensor nodes.Definition 8 (localization error).
The distance between the actual and estimated positions ofUi is called itslocalization error, which is denoted by LEi. Obviously, (4)LEi=1Rx^ui-xui2+y^ui-yui2
Localization error is an important criterion to evaluate a localization algorithm.


### 3.2. Particle Swarm Optimization Algorithm

PSO is a popular multidimensional optimization algorithm, which models the behaviour of a flock of birds searching for corn [35]. In PSO, a swarm ofparticles explores in aD-dimensional hyperspace to search the global solution of anobjective/fitness function. ThreeD-dimensional vectors are used to describe a particle i: (1) current location Xi; (2) the previous location Pbesti of the best fitness; and (3) current velocity Vi. Besides, Gbest denotes the position of the best particle so far. The basic procedure of PSO is shown in Algorithm 1.Algorithm 1:Basic procedure of PSO algorithm.
( 1 ) Initialize a swarm of particles in the given search space with random positions and velocities. ( 2 ) while stop criteria are not met do ( 3 )  Compute the fitness values of all particles. ( 4 )  Compute Pbesti for all particles, and Gbest. ( 5 )  Update particle i according to the following formula: V i = ω V i + c 1 φ 1 P b e s t i - X i + c 2 φ 2 G b e s t - X i, Xi=Xi+Vi 5 ( 6 ) end whileIn5, c1 and c2 are, respectively, cognitive and social acceleration coefficients, φ1 and φ2 are random numbers uniformly distributed in (0,1), and ω is inertia weight defined as6ω=ωmax-ωmax-ωmintmaxtwhere tmax is maximum number of allowable iterations and ωmax and ωmin are, respectively, maximum and minimum weight. Further, velocities are bounded within -Vmax,Vmax to prevent particles from exceeding the search space. The stop criteria in line 2 used in existing PSO-based localization algorithms are7fX≤fopt∨t>tmaxwhere fopt is the acceptable minimal (also the optimal) value of f.Most of the existing PSO-based localization algorithms are based on the above PSO version, and we call itstandard PSO (SPSO). This paper also investigates CPSO (PSO with constriction coefficient) [36], which appliesconstriction coefficientχ to prevent explosion, ensure convergence, and eliminate the arbitrary Vmax parameter. The update formula of CPSO is8Vi=χVi+c1φ1Pbesti-Xi+c2φ2Gbest-XiXi=Xi+Viwhere χ=2/2-c-c2-4c, c=c1+c2>4.0.


### 3.3. Basic Idea of Proposed Localization Algorithm

The localization procedure is distributed and iterative. The anchors broadcast beacon messages, including its identifier, coordinate, and information to measure distance, to its neighbour sensor nodes, and the unknown nodes receiving at least three beacon messages are localized. These localized unknown nodes become new reference nodes to provide beacon messages to their neighbours. This procedure is repeated until none of unlocalized unknown nodes can receive at least three beacon messages. If some unknown nodes are not localized yet, they request beacon messages of reference nodes in two and three hops to assist their localization. Therefore, an unknown node may appear as one of the following modes during localization:(i)
Mode1: it has at least three neighbour anchors.(ii)
Mode2: it has less than three neighbour anchors, but it has at least three neighbour reference nodes.(iii)
Mode3: it has less than three neighbour reference nodes.The unknown node of Mode 1 and Mode 2 selects reliable reference nodes before estimating its location by niching PSO algorithm, and the unknown node of Mode 3 needs special localization algorithm. These algorithms are presented in the next three sections.


## 3.1. Localization Problem Statement

Definition 1 (anchors).
The sensor nodes whose positions are known before localization are calledanchors. The set of anchors of a WSN is denoted by AS=Ai∣i=1,2,⋯,M, where M is the number of anchors. The position of anchor Ai is denoted by xai,yai.Definition 2 (unknown nodes, actual position).
The sensor nodes that need to be located by a certain localization algorithm are calledunknown nodes. The set of unknown nodes of a WSN is denoted by US=Ui∣i=1,2,⋯,N-M, where N-M is the number of unknown nodes. Theactual positions of Ui is denoted by xui,yui, which is not known in real application.Definition 3 (neighbour).
LetR be the radius of communication range of sensor nodes. Given two sensor nodes C and D, if C is located in the radio range of D, C is referred to as aneighbour of D. Because all sensor nodes have the same communication range, D is also a neighbour of C.Definition 4 ((range-based) localization).
Give a WSN consists ofN sensor nodes, including M anchors and N-M unknown nodes, the distances between any pair of neighbour nodes can be measured. The (range-based) localization problem is to localize the unknown nodes using the positions of anchors and distances between neighbour nodes.Definition 5 (estimated position).
If an unknown node is localized during localization, it will get anestimated position, and it becomes alocalized unknown node. The estimated position of Ui is denoted by x^ui,y^ui.
Obviously, the purpose of localization is to makex^ui,y^ui=xui,yui for Ui.Definition 6 (reference nodes).
During localization, both anchors and localized unknown nodes are calledreference nodes. The set of reference nodes is denoted by RS=Bi∣i=1,2,⋯,M′,N≥M′≥M. The position of reference node Bi is denoted by xbi,ybi. Obviously, if Bi is anchor Aj, xbi,ybi=xaj,yaj; if Bi is localized unknown nodes Uk, xbi,ybi=x^uk,y^uk.Definition 7 (actual distance, measured distance, and estimated distance).
An unknown nodeUi and a reference node Bj have three types of distances:(i)
Actual distance: distance between the actual positions of Ui and Bj. It is denoted by dij.(ii)
Measured distance: distance measured by a certain technique. It is denoted by d~ij. Because any measurement technique has error e to some extent, we assume d~ij=dij+N0,dije, where N0,dije is a Gaussian distribution.(iii)
Estimated distance: distance between the estimated position of Ui and Bj. It is denoted by d^ij.
Figure1 shows an example of these types of distances between Ui and Bj.
Suppose unknown nodeUi has n neighbour reference nodes B1,B2,⋯,Bn, we can solve the following equations to get x^ui,y^ui:(1)d~ij=x-xbj2+y-ybj2j=1,2,⋯,nwhere x,y is unknown quantity to solve and xbj,ybj is position of Bj. Due to the distance measurement error e, x^ui,y^ui≠xui,yui, i.e., we cannot get the actual position of Bj in general case. Using estimated position x^ui,y^ui, the estimated distance d^ij is(2)d^ij=x^ui-xbj2+y^ui-ybj2
Since the actual distancedij is not known, the objective of localization is to minimize the difference between d^ij and d~ij. Therefore, the problem of localizing Ui is formulated as(3)min⁡fx,y=∑j=1nwjd^ij-d~ij2=∑j=1nwjx-xbj2+y-ybj2-d~ij2s.t.1-DOIR≤x-xbj2+y-ybj2≤R0≤x,y≤Lj=1,2,⋯,nwhere wj=1/d~ij/∑i=1n1/d~ij, which gives more influence to those reference nodes nearer to Ui, DOI represents thedegree of irregularity of the communication range of sensor nodes, and L is the side length of the deployment region of WSN. In real applications, the communication range of sensor nodes is not a perfect circle due to multipath fading, unstable signal propagation, and noise, so DOI is introduced in (3). Given DOI, the communication range of a sensor node varies randomly in different directions between an upper bound R and a lower bound 1-DOIR [34].
The first constraint guarantees the solution locates within the communication range of all neighbouring reference nodes, and the second constraint guarantees the solution locates within the deployment region. The third constraint denotesUi has n neighbour reference nodes.
Due to the distance measurement errore, f(x,y) in (3) is often a multimodal function, so we have to use optimization algorithm to solve it. It has been proved that PSO can solve this problem well in related references; this paper tries to improve its performance further.Figure 1
Three types of distances between sensor nodes.Definition 8 (localization error).
The distance between the actual and estimated positions ofUi is called itslocalization error, which is denoted by LEi. Obviously, (4)LEi=1Rx^ui-xui2+y^ui-yui2
Localization error is an important criterion to evaluate a localization algorithm.


## 3.2. Particle Swarm Optimization Algorithm

PSO is a popular multidimensional optimization algorithm, which models the behaviour of a flock of birds searching for corn [35]. In PSO, a swarm ofparticles explores in aD-dimensional hyperspace to search the global solution of anobjective/fitness function. ThreeD-dimensional vectors are used to describe a particle i: (1) current location Xi; (2) the previous location Pbesti of the best fitness; and (3) current velocity Vi. Besides, Gbest denotes the position of the best particle so far. The basic procedure of PSO is shown in Algorithm 1.Algorithm 1:Basic procedure of PSO algorithm.
( 1 ) Initialize a swarm of particles in the given search space with random positions and velocities. ( 2 ) while stop criteria are not met do ( 3 )  Compute the fitness values of all particles. ( 4 )  Compute Pbesti for all particles, and Gbest. ( 5 )  Update particle i according to the following formula: V i = ω V i + c 1 φ 1 P b e s t i - X i + c 2 φ 2 G b e s t - X i, Xi=Xi+Vi 5 ( 6 ) end whileIn5, c1 and c2 are, respectively, cognitive and social acceleration coefficients, φ1 and φ2 are random numbers uniformly distributed in (0,1), and ω is inertia weight defined as6ω=ωmax-ωmax-ωmintmaxtwhere tmax is maximum number of allowable iterations and ωmax and ωmin are, respectively, maximum and minimum weight. Further, velocities are bounded within -Vmax,Vmax to prevent particles from exceeding the search space. The stop criteria in line 2 used in existing PSO-based localization algorithms are7fX≤fopt∨t>tmaxwhere fopt is the acceptable minimal (also the optimal) value of f.Most of the existing PSO-based localization algorithms are based on the above PSO version, and we call itstandard PSO (SPSO). This paper also investigates CPSO (PSO with constriction coefficient) [36], which appliesconstriction coefficientχ to prevent explosion, ensure convergence, and eliminate the arbitrary Vmax parameter. The update formula of CPSO is8Vi=χVi+c1φ1Pbesti-Xi+c2φ2Gbest-XiXi=Xi+Viwhere χ=2/2-c-c2-4c, c=c1+c2>4.0.


## 3.3. Basic Idea of Proposed Localization Algorithm

The localization procedure is distributed and iterative. The anchors broadcast beacon messages, including its identifier, coordinate, and information to measure distance, to its neighbour sensor nodes, and the unknown nodes receiving at least three beacon messages are localized. These localized unknown nodes become new reference nodes to provide beacon messages to their neighbours. This procedure is repeated until none of unlocalized unknown nodes can receive at least three beacon messages. If some unknown nodes are not localized yet, they request beacon messages of reference nodes in two and three hops to assist their localization. Therefore, an unknown node may appear as one of the following modes during localization:(i)
Mode1: it has at least three neighbour anchors.(ii)
Mode2: it has less than three neighbour anchors, but it has at least three neighbour reference nodes.(iii)
Mode3: it has less than three neighbour reference nodes.The unknown node of Mode 1 and Mode 2 selects reliable reference nodes before estimating its location by niching PSO algorithm, and the unknown node of Mode 3 needs special localization algorithm. These algorithms are presented in the next three sections.


## 4. Reliable Reference Node Selection

Reliability of a reference node is based on its localization error and distance to an unknown node. Localization error cannot be computed in real applications due to the absence of actual positions of unknown nodes, but the sequence of iterative localization andGbest of PSO-based localization algorithm represent localization error to a great extent. Therefore, the reliability of reference node Bi to localize an unknown node U is defined as9confi=αgLseqi+βgd~i+γgFitiwhere Lseqi, d~i, and Fiti are, respectively, the sequence of iterative localization of Bi, measured distance between Bi and U, and fitness of Bi. α, β, and γ are weights of different parts of conf. Lseqi is defined as10Lseqi=1,ifBiis  an  anchor∞,ifBiis  localized  by  Algorithm51+maxj⁡LseqCj,otherwirewhere Cj is a reference node to localize Bi. Fiti is defined as11Fiti=fx^bi,y^bi,ifBiis  localized  by  Algorithm30,ifBiis  an  anchormaxj⁡fx^cj,y^cj,ifBiis  localized  by  Algorithm4or5where x^cj,y^cj is the estimated location of Cj to localize Bi.Further,g(x) of 9 is a normalization function to map variable x∈xmin,xmax to g(x)∈[0,1], which is defined as12gx=1,ifxmax=xmin1-x-xminxmax-xmin,ifxmax≠xmin∧x<∞0,ifx=∞Note thatxmax and xmin are derived from the corresponding variables (i.e., Lseqi, d~i, or Fiti) of all neighbour reference nodes of U, instead of all reference nodes of whole WSN. Moreover, xmin≥0 according to the definition of each variable.Reference node with the largestconf is chosen as the first reliable one. If there are several reference nodes have the same conf, each of them can be selected as the first reliable reference node. The second one is chosen based on the following value:13confi′=αgLseqi+γgFitiThe reason of removing the second part of9 is illustrated in Figure 2(a). Suppose U has 6 neighbour reference nodes Bi(i=1,2,⋯,6), and conf and conf′ are shown in Table 1. B1 is chosen as the first one. If we still use conf to select the second one, B2 is the best choice. Whichever reference node we choose as the third one, the triangle formed by these chosen reference nodes will be too narrow and long to judge whether they are collinear or not.Table 1
conf and conf′ and dc of Bi in Figure 1.
B 1 B 2 B 3 B 4 B 5 B 6 c o n f 1.54 1.32 0.85 0.93 1.25 0.43 c o n f ′ 1.37 1.19 0.79 0.88 1.21 0.40 d c - - 0.05 0.07 0.06 0.02Figure 2
Selection of reliable reference nodes.
(a)
Choosing B1 and B2 (b)
Choosing B1, B5, and B4Reference node with the largestconf′ is chosen as the second, so B5 is chosen in Figure 2. If several reference nodes have the same conf′, the farthest to the first chosen reference node is selected. After selecting two reference nodes, the rest reliable reference nodes are chosen based on conf and degree of collinearity among reference nodes. Any three reference nodes can form a triangle, and we utilize the minimal internal angle dc of this triangle to measure degree of collinearity of these reference nodes. If dc is smaller than a predefined threshold δ, the observed reference node is nonreliable. As shown in Figure 2(b), B2 cannot be chosen after B1 and B5 if δ=0.1, although conf of B2 is the second largest. B4 is chosen as the third one. This process is repeated until all neighbour reference nodes of U are investigated.The detailed selection algorithm is presented in Algorithm2. This algorithm takes the set of all neighbour reference node RS of an unknown node U as input and returns the set of reliable reference nodes SRS. Lines 1 and 2 choose the first reliable reference node RB1, and lines 3-5 choose the second one RB2. Line 9 removes reference nodes being collinear with current set of reliable reference nodes SRS. Line 10 computes dc. Line 12 appends reference nodes with dc≥δ into SRS. Note that SRS may contain only two reference nodes according to this algorithm. If so, U is localized by Algorithm 4 with RB1 and RB2 as inputs.Algorithm 2:Reliable reference nodes selection.
Input: unknown node U and its neighbour references set RS, RS>2 Output: selected reference nodes set SRS ( 1 ) Compute  conf for all Bi∈RS ( 2 ) RB1←arg⁡maxi⁡confi∣Bi∈RS ( 3 ) Compute conf′ for all  Bi∈RS-RB1 ( 4 ) CRS←arg⁡maxi⁡confi′∣Bi∈RS-RB1 ( 5 ) RB2←arg⁡maxi⁡DistRB1,Bi∣Bi∈CRS ( 6 ) SRS←RB1,RB2,  RS←RS-RB1,RB2 ( 7 ) whileRS>0  do ( 8 )  CRB←arg⁡maxi⁡confi∣Bi∈RS ( 9 )  ifCRB  is not collinear with any two elements of SRSthen ( 10 )  dc←minimalinternalangleoftrianglesformedbyCRBandanytwoelementsinSRS ( 11 )  if  dc≥δ  then ( 12 )    SRS←SRS∪CRB ( 13 )  end if ( 14 )  end if ( 15 )  RS←RS-CRB ( 16 ) end while ( 17 ) returnSRS


## 5. Niching PSO-Based Localization Algorithm

### 5.1. Choice of Stop Criteria of PSO

The stop criteria of PSO determine number of iterations and consequently determine time complexity of localization algorithm. There are three types of stop criteria: a prespecified maximum number of iterations, achievement of a specified acceptable solution, and lack of change in a certain successive iteration [35]. The existing PSO-based localization methods utilize 7, which is the combination of the first two criteria.Obviously,d~ij=dij if e=0, so fopt=0, then 7 is feasible. However, e>0 in real applications, and it is difficult to give a feasible fopt. If we observe the curves of f(Gbest), as shown in Figure 3 taking three test cases as examples, we can find that f(Gbest) drops significantly before the first 100 iterations, and it keeps the same during the last 300 iterations. We also perform simulations with 1,200 different test cases using PSO-based localization algorithm and count the maximum number of iterations of the same continuous Gbest. The results are illustrated in Figure 4. There are more than 99.08% test cases keeping the same Gbest during 200 continuous iterations. On the contrary, the first iteration to achieve the final Gbest does not obey any rule, as shown in Figure 5.Figure 3
f ( G b e s t ) of each iteration.Figure 4
The maximum number of iterations of the same continuousGbest.Figure 5
The first iteration achieving the finalGbest.Therefore, iftmax is very large, it may waste many iterations when the same Gbest repeats continuously; but if tmax is small, it may not achieve the best fitness. We adopt the combination of above-mentioned three stop criteria instead of 7, as shown in Algorithm 3.Algorithm 3:Niching PSO-based localization algorithm.
Input: unknown node U and the set of selected neighbour references SRS Output: estimated position of Ux^u,y^u ( 1 ) Initialize the search space sp, and divide sp into K disjoint parts ( 2 ) Evaluate the distances of U to each B∈SRS ( 3 ) Generate a group of particles in each region ( 4 ) Evaluate the fitness values of all particles ( 5 ) Evaluate  Pbest of all particles, and Sbestj  of particles group j ( 6 ) preSbestj←Sbestj, repTimesj←0, j=1,2,⋯,K ( 7 ) isContinuej←TRUE, j=1,2,⋯,K ( 8 ) for  i←1  to  tmax  do ( 9 )  for  j←1  to  K  do ( 10 )   if  isContinuej  then ( 11 )    Update particles of group j ( 12 )    Re-evaluate the fitness of these particles ( 13 )    Update Pbest and Sbestj ( 14 )    iffSbestj<fopt  then ( 15 )     return  x^u,y^u←Sbestj ( 16 )    else  if  fSbestj-fpreBestj<ξ  then ( 17 )     repTimesj←repTimesj+1 ( 18 )    else ( 19 )     preSbestj←Sbestj,repTimesj←0 ( 20 )    end if ( 21 )    if  repTimesj>λ1∧fSbestj>μ∨repTimesj>λ2  then ( 22 )     isContinuej←FALSE ( 23 )    end if ( 24 )   end if ( 25 )   end for ( 26 )   if  ⋁j=1KisContinuej=FALSEthen ( 27 )    return  x^u,y^u←arg⁡minj⁡fSbestj ( 28 )   end if ( 29 )  end for ( 30 )  return  x^u,y^u←arg⁡minj⁡fSbestjAlgorithm 4:Localize the unknown node with two neighbour references.
Input: unknown node U and its neighbour references B1,B2 Output: estimated position of Ux^u,y^u if U can be localized ( 1 ) d~i←measured distances of U to Bi(i=1,2) ( 2 ) xbi,ybi← positions of Bi ( 3 ) xj,yj← roots of d~i2=x-xbi2+y-ybi2,i,j=1,2 ( 4 ) if  x1,y1=x2,y2  then ( 5 )  return  x^u,y^u←x1,y1 ( 6 ) else ( 7 )  TwoRS←neighbourreferencesofB1andB2-B1,B2 ( 8 )   ifTwoRS = Φ  then ( 9 )   return  U  cannot be localized ( 10 )   end  if ( 11 )   Scj←∑kconfbk∣Bk∈TwoRS∧Distxj,yj,xbk,ybk>R ( 12 )  if  Sc1≠Sc2  then ( 13 )   return  x^u,y^u←xj,yjifScj>Sc3-j ( 14 )   else ( 15 )   CTwoRS←commonneighbourreferencenodesofB1andB2∩TwoRS ( 16 )   ifCTwoRS≠Φthen ( 17 )    B3←arg⁡maxB⁡confB∣B∈CTwoRS ( 18 )   else ( 19 )    B3←arg⁡maxB⁡confB∣B∈TwoRS ( 20 )   end if ( 21 )   x3,y3←solution of Algorithm 3 using B1,B2,B3 as inputs ( 22 )   return  x^u,y^u←xj,yjifxj,yjisnearertox3,y3thanx3-j,y3-j ( 23 )  end if ( 24 ) end if


### 5.2. Niching PSO-Based Localization Algorithm

We investigate the unknown node with low localization accuracy and find that these sensor nodes are often localized at the symmetric positions of their true coordinates, which is referred to asflexible ambiguity in rigid theory [37]. Although localization algorithms based on rigid theory can cope with this problem, they need identify global-rigid patches [38, 39]. In this paper, niching technique is utilized to cope with this problem. Niching is an important technique for multimodal optimization, and lots of existing niching PSO algorithms require a niching parameter based on Euclidean distance or topology among particles [40, 41], where each particle still searches for the optima in entire space.In the proposed algorithm, particles are divided into several subswarms, and each group searches for different subregions of the whole search space of PSO. The final result is the best particle of all subswarms. Because the reference nodes chosen by Algorithm2 are noncollinear, this method can achieve a unique and best estimation. Moreover, the particles are constricted in a fixed subregion, so it does not need a niching parameter based on the calculation of Euclidean distance. The detailed localization algorithm is shown in Algorithm 3.In Algorithm3, the radio range of sensor nodes is represented by its circumscribed square. For an anchor, the side length of the square is R. For a localized unknown node, the side length is 2R, because the localization error of unknown node is less than R, according to simulation results of Section 7.4. In first, the algorithm generates search space sp of particles based on the following method (line 1):(i)
Case1. If U has at least two neighbour references and SRS=Bi∣i=1,2,⋯,n,n>1, sp is defined as14gx=sp.left=maxi⁡0,xbi-kRsp.rght=mini⁡L,xbi+kRsp.bott=maxi⁡0,ybi-kRsp.top=mini⁡L,ybi+kRwhere(sp.left,sp.top) and (sp.rght,sp.bott) are, respectively, coordinates of the top left and bottom right corners of sp, k=1 if Bi∈AS, otherwise k=2.(ii)
Case2, If U has only one neighbour reference node B1, sp is the circumscribed square of the communication range of B1.s p is divided into K≥4 equal and disjoint subregions further. The distance d-i of U to Bi is evaluated in line 2. It is calculated as follows:(i)
Case 1. If Bi is a neighbour reference node, d-i=d~i.(ii)
Case 2. If Bi is B3 selected by line 17 in Algorithm 4, the distance is15d-3=12d~1+d~2+d^b13+d^b23whered~1(d~2) is measured distance between U and B1(B2) and d^b13(d^b23) is estimated distance from B1(B2) to B3.(iii)
Case 3. If Bi is B3 selected by line 19 in Algorithm 4, the distance is16d-3=d~1+d^b13ifB3is  a  neighbour  node  ofB1d~2+d^b23ifB3is  a  neighbour  node  ofB2(iv)
Case 4. If Bi is B2 or B3 generated by line 8 or 10 in Algorithm 5, the distance is17d-i=d~1+d^b1i,i=2,3(v)
Case 5. If Bi is B3 obtained by line 15 in Algorithm 5, the distance is18d-3=d~1+d^b13Algorithm 5:Localize the unknown node with one neighbour references.
Input: unknown node U and its neighbour reference B1 Output: estimated position of Ux^u,y^u if U can be localized ( 1 ) d~1←measured distances of U to B1 ( 2 ) xb1,yb1← positions of B1 ( 3 ) TwoRS←neighbourreferencesofB1 ( 4 ) ifTwoRS=Φ  then ( 5 )  return  U cannot be localized ( 6 ) end if ( 7 ) if  TwoRS>1  then ( 8 )  B2,B3←arg⁡maxB⁡confB∣B∈TwoRS ( 9 ) else ( 10 )  B2←B∈TwoRS ( 11 )  ThrRS←{neighbourreferencesofB2}-{B1} ( 12 )  if  ThrRS=Φ  then ( 13 )   return  Ucannot be localized ( 14 )  end if ( 15 )  B3←arg⁡maxB⁡confB∣B∈ThrRS ( 16 ) end if ( 17 ) return  x^u,y^u← solution of Algorithm 3 using B1,B2,B3 as inputsLines 3-7 generate a group of particles in each search region and initialize some variables.Sbestj is the local best position of particle group j, repTimesj records the number of successive iterations with same Sbestj, and isContinuej decides whether particle group j continues to update or not. Lines 8-29 are main iteration process of niching PSO. There are four thresholds:(i)
ξ judges the difference between current and previous Sbestj.(ii)
λ1 and λ2 decide the maximum repeated times of the same Sbestj, and λ1<λ2.(iii)
μ determines the degree of acceptance of Sbestj. For particle group j, if an unacceptable fSbestj>μ repeats more than λ1 times, or a nearly acceptable fSbestj≤μ repeats more than λ2 times, the particles of this group will stop evolution.This algorithm returns results under one of the following conditions:(i)
It reaches the maximum number of iterationstmax (line 8).(ii)
One group of particles achieves an acceptable fitnessfopt (line 15).(iii)
All groups of particles stop updating (line 26).


## 5.1. Choice of Stop Criteria of PSO

The stop criteria of PSO determine number of iterations and consequently determine time complexity of localization algorithm. There are three types of stop criteria: a prespecified maximum number of iterations, achievement of a specified acceptable solution, and lack of change in a certain successive iteration [35]. The existing PSO-based localization methods utilize 7, which is the combination of the first two criteria.Obviously,d~ij=dij if e=0, so fopt=0, then 7 is feasible. However, e>0 in real applications, and it is difficult to give a feasible fopt. If we observe the curves of f(Gbest), as shown in Figure 3 taking three test cases as examples, we can find that f(Gbest) drops significantly before the first 100 iterations, and it keeps the same during the last 300 iterations. We also perform simulations with 1,200 different test cases using PSO-based localization algorithm and count the maximum number of iterations of the same continuous Gbest. The results are illustrated in Figure 4. There are more than 99.08% test cases keeping the same Gbest during 200 continuous iterations. On the contrary, the first iteration to achieve the final Gbest does not obey any rule, as shown in Figure 5.Figure 3
f ( G b e s t ) of each iteration.Figure 4
The maximum number of iterations of the same continuousGbest.Figure 5
The first iteration achieving the finalGbest.Therefore, iftmax is very large, it may waste many iterations when the same Gbest repeats continuously; but if tmax is small, it may not achieve the best fitness. We adopt the combination of above-mentioned three stop criteria instead of 7, as shown in Algorithm 3.Algorithm 3:Niching PSO-based localization algorithm.
Input: unknown node U and the set of selected neighbour references SRS Output: estimated position of Ux^u,y^u ( 1 ) Initialize the search space sp, and divide sp into K disjoint parts ( 2 ) Evaluate the distances of U to each B∈SRS ( 3 ) Generate a group of particles in each region ( 4 ) Evaluate the fitness values of all particles ( 5 ) Evaluate  Pbest of all particles, and Sbestj  of particles group j ( 6 ) preSbestj←Sbestj, repTimesj←0, j=1,2,⋯,K ( 7 ) isContinuej←TRUE, j=1,2,⋯,K ( 8 ) for  i←1  to  tmax  do ( 9 )  for  j←1  to  K  do ( 10 )   if  isContinuej  then ( 11 )    Update particles of group j ( 12 )    Re-evaluate the fitness of these particles ( 13 )    Update Pbest and Sbestj ( 14 )    iffSbestj<fopt  then ( 15 )     return  x^u,y^u←Sbestj ( 16 )    else  if  fSbestj-fpreBestj<ξ  then ( 17 )     repTimesj←repTimesj+1 ( 18 )    else ( 19 )     preSbestj←Sbestj,repTimesj←0 ( 20 )    end if ( 21 )    if  repTimesj>λ1∧fSbestj>μ∨repTimesj>λ2  then ( 22 )     isContinuej←FALSE ( 23 )    end if ( 24 )   end if ( 25 )   end for ( 26 )   if  ⋁j=1KisContinuej=FALSEthen ( 27 )    return  x^u,y^u←arg⁡minj⁡fSbestj ( 28 )   end if ( 29 )  end for ( 30 )  return  x^u,y^u←arg⁡minj⁡fSbestjAlgorithm 4:Localize the unknown node with two neighbour references.
Input: unknown node U and its neighbour references B1,B2 Output: estimated position of Ux^u,y^u if U can be localized ( 1 ) d~i←measured distances of U to Bi(i=1,2) ( 2 ) xbi,ybi← positions of Bi ( 3 ) xj,yj← roots of d~i2=x-xbi2+y-ybi2,i,j=1,2 ( 4 ) if  x1,y1=x2,y2  then ( 5 )  return  x^u,y^u←x1,y1 ( 6 ) else ( 7 )  TwoRS←neighbourreferencesofB1andB2-B1,B2 ( 8 )   ifTwoRS = Φ  then ( 9 )   return  U  cannot be localized ( 10 )   end  if ( 11 )   Scj←∑kconfbk∣Bk∈TwoRS∧Distxj,yj,xbk,ybk>R ( 12 )  if  Sc1≠Sc2  then ( 13 )   return  x^u,y^u←xj,yjifScj>Sc3-j ( 14 )   else ( 15 )   CTwoRS←commonneighbourreferencenodesofB1andB2∩TwoRS ( 16 )   ifCTwoRS≠Φthen ( 17 )    B3←arg⁡maxB⁡confB∣B∈CTwoRS ( 18 )   else ( 19 )    B3←arg⁡maxB⁡confB∣B∈TwoRS ( 20 )   end if ( 21 )   x3,y3←solution of Algorithm 3 using B1,B2,B3 as inputs ( 22 )   return  x^u,y^u←xj,yjifxj,yjisnearertox3,y3thanx3-j,y3-j ( 23 )  end if ( 24 ) end if


## 5.2. Niching PSO-Based Localization Algorithm

We investigate the unknown node with low localization accuracy and find that these sensor nodes are often localized at the symmetric positions of their true coordinates, which is referred to asflexible ambiguity in rigid theory [37]. Although localization algorithms based on rigid theory can cope with this problem, they need identify global-rigid patches [38, 39]. In this paper, niching technique is utilized to cope with this problem. Niching is an important technique for multimodal optimization, and lots of existing niching PSO algorithms require a niching parameter based on Euclidean distance or topology among particles [40, 41], where each particle still searches for the optima in entire space.In the proposed algorithm, particles are divided into several subswarms, and each group searches for different subregions of the whole search space of PSO. The final result is the best particle of all subswarms. Because the reference nodes chosen by Algorithm2 are noncollinear, this method can achieve a unique and best estimation. Moreover, the particles are constricted in a fixed subregion, so it does not need a niching parameter based on the calculation of Euclidean distance. The detailed localization algorithm is shown in Algorithm 3.In Algorithm3, the radio range of sensor nodes is represented by its circumscribed square. For an anchor, the side length of the square is R. For a localized unknown node, the side length is 2R, because the localization error of unknown node is less than R, according to simulation results of Section 7.4. In first, the algorithm generates search space sp of particles based on the following method (line 1):(i)
Case1. If U has at least two neighbour references and SRS=Bi∣i=1,2,⋯,n,n>1, sp is defined as14gx=sp.left=maxi⁡0,xbi-kRsp.rght=mini⁡L,xbi+kRsp.bott=maxi⁡0,ybi-kRsp.top=mini⁡L,ybi+kRwhere(sp.left,sp.top) and (sp.rght,sp.bott) are, respectively, coordinates of the top left and bottom right corners of sp, k=1 if Bi∈AS, otherwise k=2.(ii)
Case2, If U has only one neighbour reference node B1, sp is the circumscribed square of the communication range of B1.s p is divided into K≥4 equal and disjoint subregions further. The distance d-i of U to Bi is evaluated in line 2. It is calculated as follows:(i)
Case 1. If Bi is a neighbour reference node, d-i=d~i.(ii)
Case 2. If Bi is B3 selected by line 17 in Algorithm 4, the distance is15d-3=12d~1+d~2+d^b13+d^b23whered~1(d~2) is measured distance between U and B1(B2) and d^b13(d^b23) is estimated distance from B1(B2) to B3.(iii)
Case 3. If Bi is B3 selected by line 19 in Algorithm 4, the distance is16d-3=d~1+d^b13ifB3is  a  neighbour  node  ofB1d~2+d^b23ifB3is  a  neighbour  node  ofB2(iv)
Case 4. If Bi is B2 or B3 generated by line 8 or 10 in Algorithm 5, the distance is17d-i=d~1+d^b1i,i=2,3(v)
Case 5. If Bi is B3 obtained by line 15 in Algorithm 5, the distance is18d-3=d~1+d^b13Algorithm 5:Localize the unknown node with one neighbour references.
Input: unknown node U and its neighbour reference B1 Output: estimated position of Ux^u,y^u if U can be localized ( 1 ) d~1←measured distances of U to B1 ( 2 ) xb1,yb1← positions of B1 ( 3 ) TwoRS←neighbourreferencesofB1 ( 4 ) ifTwoRS=Φ  then ( 5 )  return  U cannot be localized ( 6 ) end if ( 7 ) if  TwoRS>1  then ( 8 )  B2,B3←arg⁡maxB⁡confB∣B∈TwoRS ( 9 ) else ( 10 )  B2←B∈TwoRS ( 11 )  ThrRS←{neighbourreferencesofB2}-{B1} ( 12 )  if  ThrRS=Φ  then ( 13 )   return  Ucannot be localized ( 14 )  end if ( 15 )  B3←arg⁡maxB⁡confB∣B∈ThrRS ( 16 ) end if ( 17 ) return  x^u,y^u← solution of Algorithm 3 using B1,B2,B3 as inputsLines 3-7 generate a group of particles in each search region and initialize some variables.Sbestj is the local best position of particle group j, repTimesj records the number of successive iterations with same Sbestj, and isContinuej decides whether particle group j continues to update or not. Lines 8-29 are main iteration process of niching PSO. There are four thresholds:(i)
ξ judges the difference between current and previous Sbestj.(ii)
λ1 and λ2 decide the maximum repeated times of the same Sbestj, and λ1<λ2.(iii)
μ determines the degree of acceptance of Sbestj. For particle group j, if an unacceptable fSbestj>μ repeats more than λ1 times, or a nearly acceptable fSbestj≤μ repeats more than λ2 times, the particles of this group will stop evolution.This algorithm returns results under one of the following conditions:(i)
It reaches the maximum number of iterationstmax (line 8).(ii)
One group of particles achieves an acceptable fitnessfopt (line 15).(iii)
All groups of particles stop updating (line 26).


## 6. Localization of Unknown Nodes of Mode 3

The unknown node belonging to Mode 3 is localized in a way similar to DV-Distance [12] in [21], which utilizes multihop anchors to avoid error accumulation. However, if the multihop anchor is far from the unknown node to be localized, the estimated distance between them is highly unreliable [42]. Therefore, the reference nodes chosen to localize an unknown node U should be as near as possible.


### 6.1. Localization of Unknown Node with Two Neighbour References

Unknown nodeU with only two neighbour reference nodes B1 and B2 is localized by Algorithm 4. After getting positions and measured distances of these two references (lines 1-2), it solves equations in line 3. If there is only one solution, line 5 returns it as a result. Otherwise, line 7 decides its position by two-hop neighbour references TwoRS. U cannot be localized if TwoRS=Φ (line 9). Otherwise, line 11 computes distances between each solutions xj,yjj=1,2 and each Bk∈TwoRS by function Dist() and calculates two sums Scj, which is the sum of conf (see 9) of all Bk whose distance to xj,yj is larger than R. Line 13 returns the solution with the largest Sc as a result. If these two sums are the same, line 15 obtains the common neighbours CTwoRS of B1 and B2. If CTwoRS≠Φ, line 17 chooses B3∈CTwoRS with the largest conf; otherwise, line 19 chooses B3∈TwoRS with the largest conf. Next, line 21 estimates a position x3,y3 using Algorithm 3, and line 22 returns the coordinate which is nearer to x3,y3 than the other as a result.


### 6.2. Localization of Unknown Node with One Neighbour Reference

IfU has only one neighbour reference B1, it is localized by Algorithm 5. The first two lines are similar to those of Algorithm 4. Line 3 obtains two-hop reference nodes TwoRS. If TwoRS has at least two members, line 8 selects two of them B2 and B3 which have the largest conf. If TwoRS has only one element, line 10 chooses this element as B2. Line 11 obtains three-hop neighbour reference nodes ThrRS, and line 15 selects B3∈ThrRS of the largest conf as B3. Finally, line 17 computes position of U by Algorithm 3 with B1,B2,B3 as inputs. If TwoRS or ThrRS is empty, U cannot be localized (line 5 and 13).If an unknown node with less than three neighbour reference nodes cannot be localized by Algorithms4 and 5, it is abandoned localization because its estimated location is highly unreliable if it utilizes reference nodes in more than three hops to localize itself [38].


## 6.1. Localization of Unknown Node with Two Neighbour References

Unknown nodeU with only two neighbour reference nodes B1 and B2 is localized by Algorithm 4. After getting positions and measured distances of these two references (lines 1-2), it solves equations in line 3. If there is only one solution, line 5 returns it as a result. Otherwise, line 7 decides its position by two-hop neighbour references TwoRS. U cannot be localized if TwoRS=Φ (line 9). Otherwise, line 11 computes distances between each solutions xj,yjj=1,2 and each Bk∈TwoRS by function Dist() and calculates two sums Scj, which is the sum of conf (see 9) of all Bk whose distance to xj,yj is larger than R. Line 13 returns the solution with the largest Sc as a result. If these two sums are the same, line 15 obtains the common neighbours CTwoRS of B1 and B2. If CTwoRS≠Φ, line 17 chooses B3∈CTwoRS with the largest conf; otherwise, line 19 chooses B3∈TwoRS with the largest conf. Next, line 21 estimates a position x3,y3 using Algorithm 3, and line 22 returns the coordinate which is nearer to x3,y3 than the other as a result.


## 6.2. Localization of Unknown Node with One Neighbour Reference

IfU has only one neighbour reference B1, it is localized by Algorithm 5. The first two lines are similar to those of Algorithm 4. Line 3 obtains two-hop reference nodes TwoRS. If TwoRS has at least two members, line 8 selects two of them B2 and B3 which have the largest conf. If TwoRS has only one element, line 10 chooses this element as B2. Line 11 obtains three-hop neighbour reference nodes ThrRS, and line 15 selects B3∈ThrRS of the largest conf as B3. Finally, line 17 computes position of U by Algorithm 3 with B1,B2,B3 as inputs. If TwoRS or ThrRS is empty, U cannot be localized (line 5 and 13).If an unknown node with less than three neighbour reference nodes cannot be localized by Algorithms4 and 5, it is abandoned localization because its estimated location is highly unreliable if it utilizes reference nodes in more than three hops to localize itself [38].


## 7. Performance Analysis and Comparisons

Because our algorithm is range-based, anchor-based, and distributed, we compare it with the algorithms of same type, which are iterative multilateration, DV-Distance [9], SPSO-based localization [21, 22], HPSO [23], and hybrid PSO [24].


### 7.1. Complexity Analysis

We analyse the time complexity of algorithms in first. Suppose all the input data have the same number of binary digits, then the time complexity can be calculated in terms of times of basic arithmetic operations in an algorithm, such as addition, subtraction, multiplication, and division.Both multilateration and DV-Distance use standard least-square approach to estimate position of an unknown node. Based on (1), the estimation is19x^ui,y^ui=ATA-1ATBwhere20A=-2xb1-xbnyb1-ybn⋮⋮xb,n-1-xbnxb,n-1-xbnB=d~1j2-d~nj2-xb12+xbn2-yb12+ybn2⋮d~n-1,j2-d~nj2-xb,n-12+xbn2-yb,n-12+ybn2In20, matrix A needs 2(n-1) subtractions and 2(n-1) multiplications; matrix B needs 5(n-1) multiplications, 3(n-1) subtractions, and 2(n-1) additions.Equation19 needs 3 matrix multiplications and 1 matrix inversion. If Algorithm 6 is applied to calculate matrix multiplication, it needs pqr additions and pqr multiplications. Further, matrices A and B are, respectively, n-1×2 and n-1×1, so C=ATA needs 4n-12 additions and 4n-12 multiplications, D=CAT needs 8n-1 additions and 8n-1 multiplications, and E=DB needs 2n-12 additions and 2n-12 multiplications. Suppose C=abcd and ad-bc≠0, C-1=ATA-1=1/ad-bcd-b-ca, so it needs 6 multiplications, 1 division, and 1 subtraction.Algorithm 6:Matrix multiplication.
Input: two matrices Ap×q and Bq×r Output: C=A×B ( 1 ) for  i←1  to  p ( 2 )  for  j←1  to  r ( 3 )   Cij←0 ( 4 )   for  k←1  to  q ( 5 )    Cij←Cij+Aik×Bkj ( 6 )   end for ( 7 )  end for ( 8 ) end forIn total,19 and 20 need 6n-12+15n-1+6=6n2+3n-3 multiplications, 1 division, 6n-12+10n-1=6n2-2n-4 additions, and 5n-1+1=5n-4 subtractions. Hence, the time complexity of multilateration and DV-Distance is On2.The time complexities of PSO algorithms stem from the evaluation of fitness and update of particles. For each iteration, HPSO updates each particle with the local best fitness, global best fitness, and previous individual best fitness, so its complexity is higher than SPSO. Reference [24] has already showed that the complexity of each iteration of hybrid PSO is higher than SPSO. Based on (3), 5, and 8, CPSO and SPSO have the same time complexity in each iteration.Letm be the number of particles in CPSO. During each iteration, CPSO uses (3) to calculate the particles’ fitness, which needs n+2 divisions and n-1 additions to get wj and mn extractions of square root, 4mn multiplications, 3mn subtractions, and 2mn-m additions to get f(x,y). Equation 8 needs 5m multiplications, 3m additions, and 2m subtractions to update particles. During each iteration of Algorithm 3, it needs 5 comparisons in lines 14, 16, and 21, and it also needs 2m-K comparisons to get Pbest of each particle and Sbest of each group of particles (line 13). It also needs n comparisons to get sp. Let Itr be the number of iterations, Algorithm 3 needs (n+2)Itr divisions, (4mn+5m)Itr multiplications, (2mn+2m+n-1)Itr additions, (3mn+2m)Itr subtractions, (mn)Itr extractions of square root, and 2m-K+5Itr+n comparisons. Hence, the time complexity of Algorithm 3 is O(mn×Itr). Generally, m,n≪Itr, so it is important to decrease Itr.For multilateration and Algorithm3, n is the number of neighbouring reference nodes, so n2<mn×Itr. DV-Distance uses all anchors to localize each unknown node, so its time complexity OM2. Generally, M<m×Itr. Therefore, the time complexity sequence is multilateration<DV-Distance<CPSO=SPSO<hybrid  PSO,  HPSO.As for communication complexity, multilateration requires each sensor node to broadcast one package, including its positions and information to assist the receiver to measure distance, to its neighbour nodes, so its communication cost isO(N). DV-Distance needs three message flooding stages in whole network, so its communication complexity is O(N3). The communication cost of existing PSO-based localization algorithm is the same as multilateration. The proposed localization algorithm needs transmit a few more packages than multilateration, because our algorithm requires unknown nodes localized by Algorithms 4 and 5 to obtain information of two- and three-hop neighbour reference nodes.


### 7.2. Parameter Selection of PSO Algorithm

The performance of PSO-based localization algorithms is greatly impacted by the PSO’s parameters. Given the possible scopes of these parameters, a comprehensive performance comparison under each combination of parameters is presented in [43]. Table 2 presents the best parameters achieving the optimal performance in [43].Table 2
Parameter selection of PSO-based localization algorithm.
parameter candidate scope best selection SPSO CPSO V m a x 0.1 R to 2R at step of 0.1R 0.1 R - Swarm Size 5 to 100 at step of 5 30 10 ω m a x 1.4 to 0.9 at step of-0.1 0.9 - ω m i n 0.4 to 0 at step of-0.1 0 - c 1 , c 2 1.5 to 2.5 at step of 0.05 1.7 / 1.8 2.45 / 2.5


### 7.3. Choice ofδ in Algorithm 2

In Algorithm2, δ decides the degree of collinearity of reference nodes, so we perform simulations to choose a feasible value. As shown in Figure 6, we deploy 3 reference nodes on a circle of radius R, and an unknown node U at the centre of the circle. B1 and B2 are fixed at -Rcosπ/3,±Rcosπ/3, and B3 changes its position in θ∈0,π along the blue arc, where θ is the angle between line UB3- and positive direction of axis x. The other setups are the same as Section 7.2. The results are shown in Figure 7. We can see that LE increases as θ increases from 0 to 2π/3, and it decreases as θ decreases from 2π/3 to π. Moreover, different e generates different varying trends. In the proposed algorithm, we utilize δ=(100e+5)π/180 as the threshold to decide the collinearity of anchors.Figure 6
Positions of reference nodes to analyse the collinearity.Figure 7
Average localization error of different angle.


### 7.4. Comparison of Different Localization Algorithms

The simulations are performed on MATLAB 2012a, and PSO is implemented in C language. The configurations of WSNs are as follows:N is 2000 to 3000 at step of 200, M/N is 0.1 to 0.4 at step of 0.05, DOI is 0 to 0.2 at step of 0.05, R is 100 to 200 at step of 20, and e is 0 to 0.2 at step of 0.05. Both anchors and unknown nodes are deployed in the given region randomly.The parameters of SPSO and CPSO are chosen based on Table2. According to corresponding references, parameters of HPSO are ω=0.7, c1=c2=1.494; parameters of hybrid PSO are ω=1, c1=c2=2.0. CPSO has K=4 groups of particles and each group has 10 particles. For Algorithms 2 and 3, α=β=γ=1 to give the same weight for each part of conf (see 9). δ=(100e+5)π/180 according to Section 7.3. λ1=200, λ2=300 according to the analysis in Section 5.1. ξ=10-4,μ=1 to make the algorithm iterate as many times as possible. Algorithm 3 utilizes niching CPSO to localize an unknown node.The average and standard deviation ofLE are, respectively, denoted by LE- and σLE; and those of Itr are, respectively, denoted by Itr- and σItr. Moreover, the number of unknown nodes with LE>1 is denoted by NFL(NFL represents “number of fail localized unknown nodes”), and the LE and Itr of these nodes are excluded when analysing LE and Itr. Simulation results are shown in Table 3, and we can see that(i)
LE-, σLE, and NFL of DV-Distance are the largest among all localization methods. DV-Distance utilizes all anchors of a WSN to localize each unknown node, and some anchors may be collinear, so matrix A of 19 may be singular, which leads to high localization error.(ii)
LE- and σLE of SPSO and multilateration are almost the same, but SPSO localizes more unknown nodes than multilateration.(iii)
Both HPSO and hybrid PSO outperform SPSO in terms ofLE and Itr, but HPSO needs more iterations than hybrid PSO. On the other hand, NFL of HPSO and hybrid PSO is larger than SPSO. Further, LE- and NFL of hybrid PSO are larger than HPSO, because the replacement strategy of hybrid PSO leads to premature convergence. However, hybrid PSO uses less iterations than HPSO and SPSO.(iv)
Niching CPSO performs better than the other algorithms in terms ofLE-, σLE, and Itr-. In particular, LE- of niching CPSO is 71.75%, 65.98%, 38.24%, 38.04%, and 4.19% of that of hybrid PSO, HPSO, SPSO, multilateration, and DV-Distance, respectively. Moreover, only seldom unknown nodes cannot be localized by niching CPSO.Table 3
Comparison of four localization algorithms.
Algorithm L E σ L E I t r - σ I t r N F L SPSO [21, 22] 0.0581 0.0542 475.8757 13.6372 8.1257 Niching CPSO 0.0221 0.0189 208.3633 33.6333 0.2206 HPSO [23] 0.0335 0.0511 281.6785 21.5868 17.6117 hybrid PSO [24] 0.0408 0.0510 223.8209 14.1587 20.4287 multilateration 0.0578 0.0530 - - 21.5019 DV-Distance 0.5272 0.1912 - - 90.1234We further compare cumulative distribution functions (CDF) ofLE and Itr of localization algorithms, as shown in Figures 8 and 9, from which we can draw the following conclusions:(i)
LE of DV-Distance is the worst. Its LE distributes in 0.01-1 uniformly, and only 33.4% unknown nodes have LE<0.01.(ii)
For niching CPSO localization algorithm,LE of more than 90% unknown nodes are less than 0.06, which is the best among all localization algorithms. Moreover, its largest Itr is 416, and Itr of more than 87% unknown nodes is less than 300. Therefore, niching CPSO achieves the highest localization precision with the smallest number of iterations among all algorithms.(iii)
There are about 63.4% and 67.4% unknown nodes whoseLE≤0.06 using SPSO and multilateration. Although their CDFs are almost the same, the number of unknown nodes with LE>0.01 of SPSO is less than multilateration, so LE- of multilateration is larger than SPSO.(iv)
LE of HPSO and hybrid PSO are between SPSO and niching CPSO, but their Itr are smaller than SPSO.Figure 8
Localization error of four localization algorithms.Figure 9
Number of iterations of PSO-based localization algorithms.


### 7.5. Impacts of Different Setups on Niching PSO-Based Localization

Based on the best parameters of SPSO and CPSO presented in Section7.2, we compare the performance of Algorithm 3 using SPSO and CPSO with different network setups.


#### 7.5.1. Impacts ofN and M

Generally, the more anchors in a WSN obtain the more accurate localization. Figure10 shows that niching PSO-based methods obey this rule, but the impacts of N and M on niching CPSO are less than those on SPSO, because the variation of niching SPSO is more obvious than niching CPSO. This figure also denotes that LE of niching SPSO is larger than niching CPSO. LE- of niching CPSO and niching SPSO, respectively, belong to 0.0196-0.0280 and 0.0488-0.0772, and their σLE, respectively, belong to 0.0152-0.0280 and 0.0424-0.0806.Figure 10
Impacts ofN and M on LE of niching PSO-based methods.The impacts ofN and M on Itr of both niching PSO methods are little, as shown in Figure 11. Itr- of niching SPSO is 469.68-485.33, and that of niching CPSO is 206.96-210.98. On the contrary, σItr of niching SPSO is 11.99-15.22, and that of niching CPSO is 132.52-137.24, so the varying range of Itr of niching CPSO is larger than niching SPSO.Figure 11
Impacts ofN and M on Itr of niching PSO-based methods.


#### 7.5.2. Impacts of DOI ande

Figure12 shows that DOI has little impacts on LE, while LE becomes larger as e increases. When e=0, LE- of niching CPSO and niching SPSO is, respectively, 0.001 and 0.0131. When e>0, LE- of niching CPSO is about 26.9%-45.2% of niching SPSO, and σLE of niching CPSO is about 25.2%-44.1% of niching SPSO.Figure 12
Impacts ofDOI and e on LE of niching PSO-based methods.Figure13 shows that Itr is almost the same under different DOI and same e. Both niching CPSO and niching SPSO have the minimal Itr under e=0, which is, respectively, 133.33 and 379.38. However, niching CPSO and niching SPSO exhibit different variation when e>0. Itr- of niching SPSO is 500 for all e>0. Itr- of niching CPSO is 254.13 when e=0.05, which is the largest, and it is, respectively, 221.93, 216.43, and 216 when e=0.1, 0.15, and 0.2. On the contrary, σItr of niching SPSO is about 68.63 when e=0, and it is 0 when e>0. σItr of niching CPSO is 120.69-148.08, and it is the largest when e=0.05.Figure 13
Impacts ofDOI and e on Itr of niching PSO-based methods.


#### 7.5.3. Impacts of Coverage Holes

We compare the impacts of coverage holes of WSNs on niching CPSO-based localization algorithm and DV-Distance, because the former is the best one among all PSO-based localization algorithms according to the above simulations, and the latter relies on connectivity information among sensor nodes.Figure14 illustrates the simulation region with three coverage holes, and the other setups as the same as above. Figures 15 and 16 show that the impacts of coverage holes on DV-Distance are more obvious than those on niching CPSO. The difference of LE- (σLE) between WSNs with holes and without hole is located in [0,0.2763] ([0.0018,0.1593]) using DV-Distance, while that of niching CPSO is located in [0,0.0074] ([0,0.0286]). Moreover, all the above differences become larger and larger with the increase of e and DOI.Figure 14
A WSN with coverage holes. The blue blocks, stars (“∗”), and red lines are, respectively, coverage holes, sensor nodes, and connectivity relations.Figure 15
Impacts of coverage hole onLE-.Figure 16
Impacts of coverage hole onσLE.


## 7.1. Complexity Analysis

We analyse the time complexity of algorithms in first. Suppose all the input data have the same number of binary digits, then the time complexity can be calculated in terms of times of basic arithmetic operations in an algorithm, such as addition, subtraction, multiplication, and division.Both multilateration and DV-Distance use standard least-square approach to estimate position of an unknown node. Based on (1), the estimation is19x^ui,y^ui=ATA-1ATBwhere20A=-2xb1-xbnyb1-ybn⋮⋮xb,n-1-xbnxb,n-1-xbnB=d~1j2-d~nj2-xb12+xbn2-yb12+ybn2⋮d~n-1,j2-d~nj2-xb,n-12+xbn2-yb,n-12+ybn2In20, matrix A needs 2(n-1) subtractions and 2(n-1) multiplications; matrix B needs 5(n-1) multiplications, 3(n-1) subtractions, and 2(n-1) additions.Equation19 needs 3 matrix multiplications and 1 matrix inversion. If Algorithm 6 is applied to calculate matrix multiplication, it needs pqr additions and pqr multiplications. Further, matrices A and B are, respectively, n-1×2 and n-1×1, so C=ATA needs 4n-12 additions and 4n-12 multiplications, D=CAT needs 8n-1 additions and 8n-1 multiplications, and E=DB needs 2n-12 additions and 2n-12 multiplications. Suppose C=abcd and ad-bc≠0, C-1=ATA-1=1/ad-bcd-b-ca, so it needs 6 multiplications, 1 division, and 1 subtraction.Algorithm 6:Matrix multiplication.
Input: two matrices Ap×q and Bq×r Output: C=A×B ( 1 ) for  i←1  to  p ( 2 )  for  j←1  to  r ( 3 )   Cij←0 ( 4 )   for  k←1  to  q ( 5 )    Cij←Cij+Aik×Bkj ( 6 )   end for ( 7 )  end for ( 8 ) end forIn total,19 and 20 need 6n-12+15n-1+6=6n2+3n-3 multiplications, 1 division, 6n-12+10n-1=6n2-2n-4 additions, and 5n-1+1=5n-4 subtractions. Hence, the time complexity of multilateration and DV-Distance is On2.The time complexities of PSO algorithms stem from the evaluation of fitness and update of particles. For each iteration, HPSO updates each particle with the local best fitness, global best fitness, and previous individual best fitness, so its complexity is higher than SPSO. Reference [24] has already showed that the complexity of each iteration of hybrid PSO is higher than SPSO. Based on (3), 5, and 8, CPSO and SPSO have the same time complexity in each iteration.Letm be the number of particles in CPSO. During each iteration, CPSO uses (3) to calculate the particles’ fitness, which needs n+2 divisions and n-1 additions to get wj and mn extractions of square root, 4mn multiplications, 3mn subtractions, and 2mn-m additions to get f(x,y). Equation 8 needs 5m multiplications, 3m additions, and 2m subtractions to update particles. During each iteration of Algorithm 3, it needs 5 comparisons in lines 14, 16, and 21, and it also needs 2m-K comparisons to get Pbest of each particle and Sbest of each group of particles (line 13). It also needs n comparisons to get sp. Let Itr be the number of iterations, Algorithm 3 needs (n+2)Itr divisions, (4mn+5m)Itr multiplications, (2mn+2m+n-1)Itr additions, (3mn+2m)Itr subtractions, (mn)Itr extractions of square root, and 2m-K+5Itr+n comparisons. Hence, the time complexity of Algorithm 3 is O(mn×Itr). Generally, m,n≪Itr, so it is important to decrease Itr.For multilateration and Algorithm3, n is the number of neighbouring reference nodes, so n2<mn×Itr. DV-Distance uses all anchors to localize each unknown node, so its time complexity OM2. Generally, M<m×Itr. Therefore, the time complexity sequence is multilateration<DV-Distance<CPSO=SPSO<hybrid  PSO,  HPSO.As for communication complexity, multilateration requires each sensor node to broadcast one package, including its positions and information to assist the receiver to measure distance, to its neighbour nodes, so its communication cost isO(N). DV-Distance needs three message flooding stages in whole network, so its communication complexity is O(N3). The communication cost of existing PSO-based localization algorithm is the same as multilateration. The proposed localization algorithm needs transmit a few more packages than multilateration, because our algorithm requires unknown nodes localized by Algorithms 4 and 5 to obtain information of two- and three-hop neighbour reference nodes.


## 7.2. Parameter Selection of PSO Algorithm

The performance of PSO-based localization algorithms is greatly impacted by the PSO’s parameters. Given the possible scopes of these parameters, a comprehensive performance comparison under each combination of parameters is presented in [43]. Table 2 presents the best parameters achieving the optimal performance in [43].Table 2
Parameter selection of PSO-based localization algorithm.
parameter candidate scope best selection SPSO CPSO V m a x 0.1 R to 2R at step of 0.1R 0.1 R - Swarm Size 5 to 100 at step of 5 30 10 ω m a x 1.4 to 0.9 at step of-0.1 0.9 - ω m i n 0.4 to 0 at step of-0.1 0 - c 1 , c 2 1.5 to 2.5 at step of 0.05 1.7 / 1.8 2.45 / 2.5


## 7.3. Choice ofδ in Algorithm 2

In Algorithm2, δ decides the degree of collinearity of reference nodes, so we perform simulations to choose a feasible value. As shown in Figure 6, we deploy 3 reference nodes on a circle of radius R, and an unknown node U at the centre of the circle. B1 and B2 are fixed at -Rcosπ/3,±Rcosπ/3, and B3 changes its position in θ∈0,π along the blue arc, where θ is the angle between line UB3- and positive direction of axis x. The other setups are the same as Section 7.2. The results are shown in Figure 7. We can see that LE increases as θ increases from 0 to 2π/3, and it decreases as θ decreases from 2π/3 to π. Moreover, different e generates different varying trends. In the proposed algorithm, we utilize δ=(100e+5)π/180 as the threshold to decide the collinearity of anchors.Figure 6
Positions of reference nodes to analyse the collinearity.Figure 7
Average localization error of different angle.


## 7.4. Comparison of Different Localization Algorithms

The simulations are performed on MATLAB 2012a, and PSO is implemented in C language. The configurations of WSNs are as follows:N is 2000 to 3000 at step of 200, M/N is 0.1 to 0.4 at step of 0.05, DOI is 0 to 0.2 at step of 0.05, R is 100 to 200 at step of 20, and e is 0 to 0.2 at step of 0.05. Both anchors and unknown nodes are deployed in the given region randomly.The parameters of SPSO and CPSO are chosen based on Table2. According to corresponding references, parameters of HPSO are ω=0.7, c1=c2=1.494; parameters of hybrid PSO are ω=1, c1=c2=2.0. CPSO has K=4 groups of particles and each group has 10 particles. For Algorithms 2 and 3, α=β=γ=1 to give the same weight for each part of conf (see 9). δ=(100e+5)π/180 according to Section 7.3. λ1=200, λ2=300 according to the analysis in Section 5.1. ξ=10-4,μ=1 to make the algorithm iterate as many times as possible. Algorithm 3 utilizes niching CPSO to localize an unknown node.The average and standard deviation ofLE are, respectively, denoted by LE- and σLE; and those of Itr are, respectively, denoted by Itr- and σItr. Moreover, the number of unknown nodes with LE>1 is denoted by NFL(NFL represents “number of fail localized unknown nodes”), and the LE and Itr of these nodes are excluded when analysing LE and Itr. Simulation results are shown in Table 3, and we can see that(i)
LE-, σLE, and NFL of DV-Distance are the largest among all localization methods. DV-Distance utilizes all anchors of a WSN to localize each unknown node, and some anchors may be collinear, so matrix A of 19 may be singular, which leads to high localization error.(ii)
LE- and σLE of SPSO and multilateration are almost the same, but SPSO localizes more unknown nodes than multilateration.(iii)
Both HPSO and hybrid PSO outperform SPSO in terms ofLE and Itr, but HPSO needs more iterations than hybrid PSO. On the other hand, NFL of HPSO and hybrid PSO is larger than SPSO. Further, LE- and NFL of hybrid PSO are larger than HPSO, because the replacement strategy of hybrid PSO leads to premature convergence. However, hybrid PSO uses less iterations than HPSO and SPSO.(iv)
Niching CPSO performs better than the other algorithms in terms ofLE-, σLE, and Itr-. In particular, LE- of niching CPSO is 71.75%, 65.98%, 38.24%, 38.04%, and 4.19% of that of hybrid PSO, HPSO, SPSO, multilateration, and DV-Distance, respectively. Moreover, only seldom unknown nodes cannot be localized by niching CPSO.Table 3
Comparison of four localization algorithms.
Algorithm L E σ L E I t r - σ I t r N F L SPSO [21, 22] 0.0581 0.0542 475.8757 13.6372 8.1257 Niching CPSO 0.0221 0.0189 208.3633 33.6333 0.2206 HPSO [23] 0.0335 0.0511 281.6785 21.5868 17.6117 hybrid PSO [24] 0.0408 0.0510 223.8209 14.1587 20.4287 multilateration 0.0578 0.0530 - - 21.5019 DV-Distance 0.5272 0.1912 - - 90.1234We further compare cumulative distribution functions (CDF) ofLE and Itr of localization algorithms, as shown in Figures 8 and 9, from which we can draw the following conclusions:(i)
LE of DV-Distance is the worst. Its LE distributes in 0.01-1 uniformly, and only 33.4% unknown nodes have LE<0.01.(ii)
For niching CPSO localization algorithm,LE of more than 90% unknown nodes are less than 0.06, which is the best among all localization algorithms. Moreover, its largest Itr is 416, and Itr of more than 87% unknown nodes is less than 300. Therefore, niching CPSO achieves the highest localization precision with the smallest number of iterations among all algorithms.(iii)
There are about 63.4% and 67.4% unknown nodes whoseLE≤0.06 using SPSO and multilateration. Although their CDFs are almost the same, the number of unknown nodes with LE>0.01 of SPSO is less than multilateration, so LE- of multilateration is larger than SPSO.(iv)
LE of HPSO and hybrid PSO are between SPSO and niching CPSO, but their Itr are smaller than SPSO.Figure 8
Localization error of four localization algorithms.Figure 9
Number of iterations of PSO-based localization algorithms.


## 7.5. Impacts of Different Setups on Niching PSO-Based Localization

Based on the best parameters of SPSO and CPSO presented in Section7.2, we compare the performance of Algorithm 3 using SPSO and CPSO with different network setups.


### 7.5.1. Impacts ofN and M

Generally, the more anchors in a WSN obtain the more accurate localization. Figure10 shows that niching PSO-based methods obey this rule, but the impacts of N and M on niching CPSO are less than those on SPSO, because the variation of niching SPSO is more obvious than niching CPSO. This figure also denotes that LE of niching SPSO is larger than niching CPSO. LE- of niching CPSO and niching SPSO, respectively, belong to 0.0196-0.0280 and 0.0488-0.0772, and their σLE, respectively, belong to 0.0152-0.0280 and 0.0424-0.0806.Figure 10
Impacts ofN and M on LE of niching PSO-based methods.The impacts ofN and M on Itr of both niching PSO methods are little, as shown in Figure 11. Itr- of niching SPSO is 469.68-485.33, and that of niching CPSO is 206.96-210.98. On the contrary, σItr of niching SPSO is 11.99-15.22, and that of niching CPSO is 132.52-137.24, so the varying range of Itr of niching CPSO is larger than niching SPSO.Figure 11
Impacts ofN and M on Itr of niching PSO-based methods.


### 7.5.2. Impacts of DOI ande

Figure12 shows that DOI has little impacts on LE, while LE becomes larger as e increases. When e=0, LE- of niching CPSO and niching SPSO is, respectively, 0.001 and 0.0131. When e>0, LE- of niching CPSO is about 26.9%-45.2% of niching SPSO, and σLE of niching CPSO is about 25.2%-44.1% of niching SPSO.Figure 12
Impacts ofDOI and e on LE of niching PSO-based methods.Figure13 shows that Itr is almost the same under different DOI and same e. Both niching CPSO and niching SPSO have the minimal Itr under e=0, which is, respectively, 133.33 and 379.38. However, niching CPSO and niching SPSO exhibit different variation when e>0. Itr- of niching SPSO is 500 for all e>0. Itr- of niching CPSO is 254.13 when e=0.05, which is the largest, and it is, respectively, 221.93, 216.43, and 216 when e=0.1, 0.15, and 0.2. On the contrary, σItr of niching SPSO is about 68.63 when e=0, and it is 0 when e>0. σItr of niching CPSO is 120.69-148.08, and it is the largest when e=0.05.Figure 13
Impacts ofDOI and e on Itr of niching PSO-based methods.


### 7.5.3. Impacts of Coverage Holes

We compare the impacts of coverage holes of WSNs on niching CPSO-based localization algorithm and DV-Distance, because the former is the best one among all PSO-based localization algorithms according to the above simulations, and the latter relies on connectivity information among sensor nodes.Figure14 illustrates the simulation region with three coverage holes, and the other setups as the same as above. Figures 15 and 16 show that the impacts of coverage holes on DV-Distance are more obvious than those on niching CPSO. The difference of LE- (σLE) between WSNs with holes and without hole is located in [0,0.2763] ([0.0018,0.1593]) using DV-Distance, while that of niching CPSO is located in [0,0.0074] ([0,0.0286]). Moreover, all the above differences become larger and larger with the increase of e and DOI.Figure 14
A WSN with coverage holes. The blue blocks, stars (“∗”), and red lines are, respectively, coverage holes, sensor nodes, and connectivity relations.Figure 15
Impacts of coverage hole onLE-.Figure 16
Impacts of coverage hole onσLE.


## 7.5.1. Impacts ofN and M

Generally, the more anchors in a WSN obtain the more accurate localization. Figure10 shows that niching PSO-based methods obey this rule, but the impacts of N and M on niching CPSO are less than those on SPSO, because the variation of niching SPSO is more obvious than niching CPSO. This figure also denotes that LE of niching SPSO is larger than niching CPSO. LE- of niching CPSO and niching SPSO, respectively, belong to 0.0196-0.0280 and 0.0488-0.0772, and their σLE, respectively, belong to 0.0152-0.0280 and 0.0424-0.0806.Figure 10
Impacts ofN and M on LE of niching PSO-based methods.The impacts ofN and M on Itr of both niching PSO methods are little, as shown in Figure 11. Itr- of niching SPSO is 469.68-485.33, and that of niching CPSO is 206.96-210.98. On the contrary, σItr of niching SPSO is 11.99-15.22, and that of niching CPSO is 132.52-137.24, so the varying range of Itr of niching CPSO is larger than niching SPSO.Figure 11
Impacts ofN and M on Itr of niching PSO-based methods.


## 7.5.2. Impacts of DOI ande

Figure12 shows that DOI has little impacts on LE, while LE becomes larger as e increases. When e=0, LE- of niching CPSO and niching SPSO is, respectively, 0.001 and 0.0131. When e>0, LE- of niching CPSO is about 26.9%-45.2% of niching SPSO, and σLE of niching CPSO is about 25.2%-44.1% of niching SPSO.Figure 12
Impacts ofDOI and e on LE of niching PSO-based methods.Figure13 shows that Itr is almost the same under different DOI and same e. Both niching CPSO and niching SPSO have the minimal Itr under e=0, which is, respectively, 133.33 and 379.38. However, niching CPSO and niching SPSO exhibit different variation when e>0. Itr- of niching SPSO is 500 for all e>0. Itr- of niching CPSO is 254.13 when e=0.05, which is the largest, and it is, respectively, 221.93, 216.43, and 216 when e=0.1, 0.15, and 0.2. On the contrary, σItr of niching SPSO is about 68.63 when e=0, and it is 0 when e>0. σItr of niching CPSO is 120.69-148.08, and it is the largest when e=0.05.Figure 13
Impacts ofDOI and e on Itr of niching PSO-based methods.


## 7.5.3. Impacts of Coverage Holes

We compare the impacts of coverage holes of WSNs on niching CPSO-based localization algorithm and DV-Distance, because the former is the best one among all PSO-based localization algorithms according to the above simulations, and the latter relies on connectivity information among sensor nodes.Figure14 illustrates the simulation region with three coverage holes, and the other setups as the same as above. Figures 15 and 16 show that the impacts of coverage holes on DV-Distance are more obvious than those on niching CPSO. The difference of LE- (σLE) between WSNs with holes and without hole is located in [0,0.2763] ([0.0018,0.1593]) using DV-Distance, while that of niching CPSO is located in [0,0.0074] ([0,0.0286]). Moreover, all the above differences become larger and larger with the increase of e and DOI.Figure 14
A WSN with coverage holes. The blue blocks, stars (“∗”), and red lines are, respectively, coverage holes, sensor nodes, and connectivity relations.Figure 15
Impacts of coverage hole onLE-.Figure 16
Impacts of coverage hole onσLE.


## 8. Conclusions

Due to random deployment of large-scale WSNs, anchors are not evenly distributed, so some unknown nodes may have not enough neighbouring anchors to localize itself, while some others may have overmuch neighbouring anchors to give a great burden to localize. Therefore, this paper presents a distributed, range-based, anchor-based localization algorithm using niching PSO with constriction coefficient and reliable references selection. This algorithm consists of three phases:(i)
Reliable references selection based on distance to unknown node, angle between reference nodes, and localization precision of reference nodes.(ii)
Generation and division of search space.(iii)
Position estimation using niching PSO.This algorithm uses a new stop criterion to decrease number of iterations, and a comprehensive method to choose the most reliable references to improve localization accuracy. It also presents localization algorithm for the unknown nodes with less than three neighbour reference nodes. Theoretical analysis shows that the proposed method has low complexity compared with the other PSO-based localization algorithms. Simulation results show that niching CPSO utilizes less iteration to achieve higher localization precision, and it is impacted less by number of sensor nodes, number of anchors, and degree of irregularity compared to the other algorithms.Nowadays, the large-scale WSNs are applied to three-dimensional (3D) region more and more, and new PSO variants such as Enhanced leader PSO (ELPSO) [44] are developed recently, so we will study the application of recent PSO variants in 3D WSNs in future.



---

*Source: 2473875-2018-12-02.xml*