# A RSSI-Based Distributed Weighted Search Localization Algorithm for WSNs

Authors: Yingbiao Yao; Qi Han; Xiaorong Xu; Nanlan Jiang
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

In order to solve the node localization problem in wireless sensor networks, we propose a novel distributed weighted search localization algorithm (WSLA) in this paper. The WSLA adopts a modified received signal strength indicator-based range model to estimate the distances between nodes, utilizes the results of a centroid localization algorithm as the search initial point, and employs a new weighted search method to compute the positions of nodes in a distributed and recursive manner. The key ideas of the WSLA include a node localization precision classification scheme, a processing scheme for special nodes, and weight-based searches. Compared with three state-of-art localization algorithms—namely, maximum likelihood estimation (MLE), edge-based second-order cone programming + nonconvex sequential greedy (ESOCP + NCSG), and particle swarm optimization (PSO)—the simulation results show that localization performance of the WSLA is superior to that of MLE, ESOCP + NCSG, and PSO.


---

## Body

## 1. Introduction

A wireless sensor network (WSN) is a wireless ad hoc network that consists of a large number of tiny battery-powered, randomly deployed sensor nodes with limited processing, storage, and communication capacity [1]. Many WSN applications, for example, environmental monitoring, forest fire prevention, search and rescue, target detection, and tracking, require knowledge regarding sensor node positions [2]. Therefore, sensor nodes should have ability to localize their positions in many WSN applications.Today, sensor nodes mainly have two methods of obtaining position information. The first is that sensor nodes are equipped with dedicated localization hardware (e.g., GPS) [3] or are manually configured after deployment. This method is simple and accurate, but it requires higher hardware or deployment costs, which are not acceptable in large-scale WSNs. Therefore, only a few nodes, known as anchor nodes, employ this method. The other method is that sensor nodes localize their positions using software localization techniques. This method has low costs and low energy consumption, with worse localization accuracy than the first method, but it can meet the requirements of most applications. Therefore, the majority of nodes employ this method; these nodes are called normal or unknown nodes.In general, localization algorithms can be divided into two categories: range-based localization and range-free localization. In range-based localization, nodes are able to measure the distances or angles to their neighbors using received signal strength indicator (RSSI), time-of-arrival, time difference of arrival, angle-of-arrival, and so on [4, 5]. In range-free localization, for example, centroid localization, APIT, DV-Hop, and LAEP [6–10], nodes have no ability to measure the distances or angles to their neighbors and instead use connectivity or hop information to compute the positions of the nodes. Range-based localization can provide higher localization accuracy than range-free localization, but the latter is simpler and does not require extra hardware for measurement.Localization algorithms can also be classified as centralized localization and distributed localization [11]. Centralized algorithms can process all range or connectivity information of the nodes from the global optimization angle. Therefore, their results are more accurate than those of distributed algorithms. However, they need to transmit a large amount of range or connectivity information to a fusion node (e.g., base station), which results in large energy communication and bandwidth consumption and shortens the lifespan of the entire network. Therefore, they are not suitable for large-scale resource-constrained WSNs. In contrast to centralized algorithms, distributed algorithms use only the local information available from its neighbors, and they are energy efficient and scalable to the size of a network. Therefore, distributed algorithms are more attractive for large-scale resource-constrained WSNs.In this paper, we propose a distributed weighted search localization algorithm (WSLA) for node localization in WSNs. The WSLA adopts a modified RSSI-based range model to estimate the distances between nodes, and it employs a novel search method to compute node positions. To the best of knowledge, our contributions are as follows:(i)
In order to make the simulation results more consistent with the measured results of RSSI- based range model, we point out that the variance of the Gaussian random variable in the log-normal distribution path loss model should be proportional to the real distance.(ii)
We propose a novel weighted search method, which has a heuristic search process, to solve the node localization problem in WSNs.(iii)
In order to further improve the localization accuracy of our method, we propose a FIFO-based localization precision classification scheme, a processing scheme for localizing the special nodes, and a simple scheme for detecting nodes with a large localization error.(iv)
We have evaluated the performance of the WSLA using extensive simulations, and the simulation results show that the localization performance of the WSLA is superior to that of three state-of-art localization algorithms, namely, maximum likelihood estimation (MLE), edge-based second-order cone programming + nonconvex sequential greedy (ESOCP + NCSG), and particle swarm optimization (PSO).The remainder of this paper is organized as follows. In the next section, we review the related work about range-based localization. The RSSI-based range model in this paper is discussed in Section3. In Section 4, we propose the WSLA in detail. The simulation experiments appear in Section 5, and we conclude this paper in Section 6.


## 2. Related Work

Range-based localization is often modeled as an optimization problem with an objective function that depends on the distances and positions of nodes. In general, even in the absence of range errors, it is possible to have a nonconvex optimization problem with many local minima. Therefore, it is impossible to localize nodes at their true positions with noisy range. The solution to the localization problem can be roughly divided into two categories: one based on mathematical optimization theories and the other based on intelligent search methods.MLE is a simple method for computing the extreme values of math functions with limited computational complexity [12]. MLE and its improvement versions have become the basic methods used for WSN localization. The performance of MLE-based localization is very good in the absence of range errors. However, its localization accuracy deteriorates rapidly with noisy range. Multidimensional scaling (MDS) is another kind of classic range-based algorithm, and a set of localization algorithms based on MDS is proposed in [13]. In [14], Costa et al. proposed distributed weighted MDS for localization, which adopts a weighted cost function, an adaptive neighbor selection method, and a majorization method to achieve node localization.Recently, a number of approaches that relax the original localization nonconvex problem to derive a convex problem have been proposed. After relaxation, the convex problem can be efficiently solved using the currently available optimization techniques, such as the interior point method. Two convex relaxation techniques are involved in these algorithms: semidefinite programming (SDP) relaxation in [15, 16] and second-order cone programming (SOCP) relaxation in [11, 17, 18]. Compared with SDP relaxation, SOCP relaxation, although weaker (and thus less accurate), has a simpler structure and allows for efficient distributed implementation. The drawback of the relaxation methods is that even when the original problem is uniquely localizable, the relaxed problem may not be [19]. In addition, both SDP and SOCP rely on a sophisticated optimization package that cannot be easily implemented on a sensor node with limited resources.Search-based localizations are another kind of WSN localization algorithm, and this kind of algorithm has the potential to achieve relatively high accuracy with relatively low complexity. Zhang et al. achieved localization with genetic algorithm (GA) in [20], which adopts two new genetic operators: single-vertex-neighborhood mutation and descend-based arithmetic crossover. Kulkarni and Venayagamoorthy proposed a distributed particle swarm optimization (PSO) approach for localization in [21]. Shekofteh et al. proposed a localization algorithm based on tabu search (TS) and simulated annealing (SA) in [22], where TS is a dynamic neighbor search technique that drives the search by escaping from local optima and avoiding the cycling. Wang et al. proposed a sequence search (SS) based localization algorithm in [23] that can improve localization accuracy by optimizing the localization sequence. Manjarres et al. proposed a harmony search (HS) localization algorithm in [24] that mimics the improvisation process of musicians seeking the best harmony. The main drawback of these search-based algorithms is that the search points are generated randomly, which results in a very slow convergence process, and they cannot ensure convergence to the global optima.


## 3. Improved RSSI Range Model

The basic idea of the RSSI range model is to estimate the distance between the receiving and the transmitting nodes by measuring the transmitted loss rate of the radio signal, and its key is the path loss model of signal propagation. The most used path loss model in RSSI range is the log-normal distribution model [4], which is as follows:(1)Pr,dBd=Pr,dBd0-10∗np∗log⁡dd0+Xσ,where d0 is the reference distance; d is the distance between the transmitting node and the receiving node; Pr,dB(d0) is the path loss at d0 distance to the transmitting node; np is the path loss constant and usually equals 2~6; and Xσ is a Gaussian random variable with a mean of 0 and a variance of σ. According to (1), the distance d can be obtained as follows: (2)d=d0∗10Pr,dBd0+Xσ-Pr,dBd/10∗np=d0∗10Pr,dBd0+Xσ+PT-PR/10∗np.In (2), PT (dbm) is the power of the transmitting node, and PR (dbm), measured by RSSI, is the power of the receiving node. In the traditional RSSI range model, np and σ are assumed to be a constant value. Using this model, when np = 3, P(d0) = −30 dbm, PT=0 dbm, and σ = 2, the RSSI simulation data are as shown in Figure 1. We find that theoretical RSSI data and the simulated average RSSI data match very well.Figure 1
RSSI simulation data,np = 3, P(d0) = −30 dbm, PT=0 dbm, σ=2.The actual measured RSSI data in [25] are shown in Figure 2. We can see that there exists a visible difference between Figures 1 and 2, which shows that the traditional RSSI-based range model is too optimistic.Figure 2
RSSI measured data in [25].According to the results in [25–27], the features of the measured RSSI data in the open outdoor environment are as follows:(i)
The actual measured RSSI value is close to the estimated value of (1) when the distance is small (e.g., shorter than 10 m) but fluctuates around the estimated value of (1) when the distance is far.(ii)
The actual measured RSSI value is a normal distribution at the same point.(iii)
Range error is proportional to distance, which means the error is small when the distance is short, and longer distances result in more errors.Therefore, in our RSSI range model, we assumenp = 3, P(d0) = −30 dbm, and PT = 0 dbm, but we also assume that σ=nf×d. nf is used to control the total noise level, and d indicates that the range error is proportional to the distance. Using this model, the simulated RSSI data are shown in Figure 3. We can see that Figure 3 is more consistent with Figure 2 compared with Figure 1.Figure 3
The improved RSSI range model,nf=0.5.


## 4. The Proposed WSLA

### 4.1. Localization Problem in WSNs

The WSN can be represented by an undirected graphG=(N,E), where N is the set of all sensors andE is the set of edges. The setN consists of a set of anchors, NA, a set of unknown nodes, NU, and N=NA∪NU. We denote xri as the real coordinates of a node i, and xri is 2-dimension vector. An edge (i,j)∈E if nodes i,j are neighbors; that is, they are in the communication range, R, of each other: drij=xri-xrj≤R, where drij is the real distance between nodes i and j, and · denotes the 2-norm. We denote deij as the estimated distance between nodes i and j and denote D as the set of all available noisy range: D={deij∣(i,j)∈E}. The estimated coordinates of a node i, xei, could be obtained in a distributed manner by solving (3), where Ni is the neighbor set of a node i: Ni={j∣ the node j is the neighbor of node i}. Consider(3)min⁡xei⁡∑j∈Nixei-xej-deij2.


### 4.2. The Basic Search Scheme

The proposed WSLA runs in a round manner to recursively localize the unknown nodes. In each round, it mainly employs a novel heuristic search method to localize the nodes as follows, wherexei(k) denotes the estimated coordinates of the node i at thekth round.Step 1.
Determine the initial search pointxei,0(k). If a node i is not localized before, the WSLA uses the centroid of its neighbors, defined in (4), as the initial search point; otherwise, it uses xei(k-1), the localization position of the last round, as the initial search point(4)xei,0k=1m∑j=1mxejk-1,j∈Ni,m=Ni.Step 2.
TakeN equal interval points from the circle whose center is xei,0(k) and radius issearch_step, which is shown in Figure 4. In our simulations, N is equal to 8, and the coordinates of these N search points are as follows: (5)xei,lk=xei,0k+search_step×cos⁡⁡θl,sin⁡θlT,θl=l-1∗2πN,l=1,2,…,N.Figure 4
The proposed heuristic search scheme.Step 3.
Calculate the value of the objective function, defined in (6), at the above N+1 search points (including the circle center). In (6), w(j) is the weight of the node j, which is defined in (7):(6)fxei,lk=∑j=1mxei,lk-xejk-1-deij2×wj,j∈Ni,l=0,1,…,N.In order to enhance the localization accuracy, the WSLA classifies nodes into four classes—NA (anchor nodes), NH (high-precision nodes), NL (low-precision nodes), and NU (unknown nodes)—and assign a different weight for the different type of nodes, as shown in (7), by extensive simulations. The design guideline is to assign a larger weight to more accurate nodes (e.g., anchor nodes) and to assign a smaller weight to less accurate nodes (e.g., low-precision nodes):(7)wj=1Sjis anchor node0.5Sjis high precision node0.125Sjis low precision node0Sjis unknown nodes.Step 4.
We assume that the pointxei,min⁡(k), defined in (8), is the minimum value in the current search iteration. Then, the WSLA updates xei,0(k) andsearch_step according to (9) and (10) for the next search iteration:(8)fxei,min⁡k=min⁡l=0,1,…,N⁡fxei,lk,(9)xei,0k=xei,min⁡k,(10)search_step=α∗search_step.Step 5.
Repeat Steps  2–4 untilsearch_step is less than stop_th. Finally, the estimated coordinates of a node i are xei,0(k) at the last search iteration, which is called the best estimated point (BEP) of the node i in the current round.Remark 1.
In (10), α is the convergence factor, which can control the convergence speed and belongs to (0,1) in theory; stop_th is the search stopping threshold. The localization accuracy and complexity of the WSLA are mainly determined by α and stop_th, and generally speaking, the smaller stop_th is and the larger α is, the higher the localization accuracy and complexity will be.


### 4.3. The Localization Scheme of Special Nodes

In general, the BEP of a nodei may be not unique if one of the following conditions is satisfied: (1) the number of its known neighbors is less than 3 or (2) its known neighbors are collinear or near collinear. This situation appears frequently in the initial several rounds of the WSLA or when the node is near to the boundary of network. From the angle of improving localization accuracy, the WSLA should ignore these nodes. However, if these nodes cannot be localized, the WSLA maybe cannot run because all nodes may not have three or more known neighbors in the first round. Therefore, to quickly realize higher localization coverage, we propose the following localization methods for these special nodes.(1) A Node with One Known Neighbor. The first special case is that a node i has one known neighbor in the early rounds of the WSLA. In this case, any point on the circle whose center is its known neighbor and whose radius is the range distance between them can satisfy (3) or (8); the WSLA takes the position of its known neighbor as its localization position in the current round. We expect that the localization error of i will decrease with the running of the WSLA when more neighbors become known in the following rounds.(2) A Node with Collinear or Near Collinear Neighbors. The second special case is that a node i has collinear or near collinear neighbors. A typical scene is shown in Figure 5, where node C has two neighbors, A and B, and hence the neighbors of node C are collinear. Both points P1 and P2 are the possible BEP because they both satisfy (3) or (8); P1 is near node C, with a small localization error, andP2 is far from nodeC, with a large localization error. Because we do not know whether the search result in Section 4.2 is P1 or P2, we choose point D as the final BEP to avoid a large localization error. Similar to the first case, we also expect that the localization error of i will decrease with the running of the WSLA when more neighbors become known in the following rounds.Figure 5
Node localization with two neighbors.PointD can be obtained using the following steps:(a)
Make a straight lineAB, the connecting line of points A and B.(b)
Make the vertical line ofAB from P1 or P2.(c)
Take the intersection (pointD) of the two lines as the final BEP of C.We assume that the coordinates ofA, B, P1 (or P2), and D are (xA,yA), (xB,yB), (xP,yP), and (xD,yD), respectively, and then the coordinates of D are as follows:(11)xD=b1-b2k2-k1,yD=k1xD+b1,where(12)k1=yA-yBxA-xB,k2=-1k1,b1=yA-k1xA,b2=yP-k2xP.


### 4.4. Node Localization Precision Classification Scheme

We define a FIFO queueQi with a size of lq for each node i, and we denote qi as the quantity of the elements in Qi. After each round, we put the BEP of node i into queue Qi and calculate the centroid of polygon Ψi which is formed by all elements in queue Qi.At the beginning, there are only anchor nodes and unknown nodes in the networks. During localization algorithm running, the WSLA gradually classifies unknown nodes intoNH and NL according to the following rule:Rule 1.
The WSLA classifies nodei into NH if all following conditions are satisfied:(i)
Its queueQi is full, namely, qi=lq.(ii)
The distance from any element inQi to the centroid of Ψi is not greater than a threshold Td.Rule 2.
The WSLA classifies nodei into NL if any of the following conditions are satisfied:(i)
Its queueQi is not full but not empty, namely, 0<qi<lq.(ii)
The distance from some element inQi to the centroid of Ψi is greater than the threshold Td.An example of node localization precision classification is shown in Figure6. In Figure 6, we assume qi=lq=5; that is to say, Qi is full. Because the distance from any element in Qi to the centroid of Ψi is not greater than Td in Figure 6(a), this node is classified into NH. In Figure 6(b), the distance from (x3,y3) to the centroid is greater than Td; thus, this node is classified into NL.Figure 6
An example of node localization precision classification.In addition, we also observe that the node localization sequence has an obvious influence on the localization accuracy for some localization scenes, as described in [23]. Specifically, in the initial several rounds of the WSLA, if a node with a large localization error takes part in the localization process of other nodes, its localization error may propagate due to the recursive localization method and thus results in a network localization accuracy decline. In order to avoid the emergence of this situation, in the initial several rounds (e.g., the first 30% rounds), the WSLA employs the following method to detect the node with a large localization error.Rule 3.
If the absolute difference value betweendij (network distance) and deij (range distance) from node i to j in Ni is greater than the error threshold err_th, we think that i is not localized accurately, and the WSLA classifies i into NU by 25% probability and NL by 75% probability to avoid or decrease the localization error propagated. Rule 3 is concluded as shown in (13)∀i,∃j∈Ni,dij-deij>err_th,dij=xeik-xejk-1⟹i∈NUp=0.25i∈NLp=0.75.


### 4.5. The Specific Flow of the WSLA

The specific steps of the WSLA in each round are as follows.Step 1 (node broadcasting).
All nodes except unknown nodes broadcast their messages, for example, transmitting power, ID, coordinates, and types, at the beginning of each round.Step 2 (RSSI ranging).
All nodes except anchor nodes receive messages from their neighbors and calculate the range distances according to (2). In our simulations, each node carries out 10 RSSI ranges in each round, and the final range distance is the average results.Step 3 (node localization).
If the number of known neighbors of nodei is larger than 1, the WSLA employs the search method in Section 4.2 to search its BEP.Step 4 (Special node processing).
If nodei is a special node, the WSLA employs the scheme in Section 4.3 to compute its new BEP.Step 5 (node classification).
The WSLA puts the BEP into queueQi and determines the localization type of the current round based on the Rules 1–3 in Section 4.4.In addition, when the position errors of anchor nodes is not zero, the WSLA degrades the anchor nodes into low precision nodes to refine their positions after running 15 rounds.


## 4.1. Localization Problem in WSNs

The WSN can be represented by an undirected graphG=(N,E), where N is the set of all sensors andE is the set of edges. The setN consists of a set of anchors, NA, a set of unknown nodes, NU, and N=NA∪NU. We denote xri as the real coordinates of a node i, and xri is 2-dimension vector. An edge (i,j)∈E if nodes i,j are neighbors; that is, they are in the communication range, R, of each other: drij=xri-xrj≤R, where drij is the real distance between nodes i and j, and · denotes the 2-norm. We denote deij as the estimated distance between nodes i and j and denote D as the set of all available noisy range: D={deij∣(i,j)∈E}. The estimated coordinates of a node i, xei, could be obtained in a distributed manner by solving (3), where Ni is the neighbor set of a node i: Ni={j∣ the node j is the neighbor of node i}. Consider(3)min⁡xei⁡∑j∈Nixei-xej-deij2.


## 4.2. The Basic Search Scheme

The proposed WSLA runs in a round manner to recursively localize the unknown nodes. In each round, it mainly employs a novel heuristic search method to localize the nodes as follows, wherexei(k) denotes the estimated coordinates of the node i at thekth round.Step 1.
Determine the initial search pointxei,0(k). If a node i is not localized before, the WSLA uses the centroid of its neighbors, defined in (4), as the initial search point; otherwise, it uses xei(k-1), the localization position of the last round, as the initial search point(4)xei,0k=1m∑j=1mxejk-1,j∈Ni,m=Ni.Step 2.
TakeN equal interval points from the circle whose center is xei,0(k) and radius issearch_step, which is shown in Figure 4. In our simulations, N is equal to 8, and the coordinates of these N search points are as follows: (5)xei,lk=xei,0k+search_step×cos⁡⁡θl,sin⁡θlT,θl=l-1∗2πN,l=1,2,…,N.Figure 4
The proposed heuristic search scheme.Step 3.
Calculate the value of the objective function, defined in (6), at the above N+1 search points (including the circle center). In (6), w(j) is the weight of the node j, which is defined in (7):(6)fxei,lk=∑j=1mxei,lk-xejk-1-deij2×wj,j∈Ni,l=0,1,…,N.In order to enhance the localization accuracy, the WSLA classifies nodes into four classes—NA (anchor nodes), NH (high-precision nodes), NL (low-precision nodes), and NU (unknown nodes)—and assign a different weight for the different type of nodes, as shown in (7), by extensive simulations. The design guideline is to assign a larger weight to more accurate nodes (e.g., anchor nodes) and to assign a smaller weight to less accurate nodes (e.g., low-precision nodes):(7)wj=1Sjis anchor node0.5Sjis high precision node0.125Sjis low precision node0Sjis unknown nodes.Step 4.
We assume that the pointxei,min⁡(k), defined in (8), is the minimum value in the current search iteration. Then, the WSLA updates xei,0(k) andsearch_step according to (9) and (10) for the next search iteration:(8)fxei,min⁡k=min⁡l=0,1,…,N⁡fxei,lk,(9)xei,0k=xei,min⁡k,(10)search_step=α∗search_step.Step 5.
Repeat Steps  2–4 untilsearch_step is less than stop_th. Finally, the estimated coordinates of a node i are xei,0(k) at the last search iteration, which is called the best estimated point (BEP) of the node i in the current round.Remark 1.
In (10), α is the convergence factor, which can control the convergence speed and belongs to (0,1) in theory; stop_th is the search stopping threshold. The localization accuracy and complexity of the WSLA are mainly determined by α and stop_th, and generally speaking, the smaller stop_th is and the larger α is, the higher the localization accuracy and complexity will be.


## 4.3. The Localization Scheme of Special Nodes

In general, the BEP of a nodei may be not unique if one of the following conditions is satisfied: (1) the number of its known neighbors is less than 3 or (2) its known neighbors are collinear or near collinear. This situation appears frequently in the initial several rounds of the WSLA or when the node is near to the boundary of network. From the angle of improving localization accuracy, the WSLA should ignore these nodes. However, if these nodes cannot be localized, the WSLA maybe cannot run because all nodes may not have three or more known neighbors in the first round. Therefore, to quickly realize higher localization coverage, we propose the following localization methods for these special nodes.(1) A Node with One Known Neighbor. The first special case is that a node i has one known neighbor in the early rounds of the WSLA. In this case, any point on the circle whose center is its known neighbor and whose radius is the range distance between them can satisfy (3) or (8); the WSLA takes the position of its known neighbor as its localization position in the current round. We expect that the localization error of i will decrease with the running of the WSLA when more neighbors become known in the following rounds.(2) A Node with Collinear or Near Collinear Neighbors. The second special case is that a node i has collinear or near collinear neighbors. A typical scene is shown in Figure 5, where node C has two neighbors, A and B, and hence the neighbors of node C are collinear. Both points P1 and P2 are the possible BEP because they both satisfy (3) or (8); P1 is near node C, with a small localization error, andP2 is far from nodeC, with a large localization error. Because we do not know whether the search result in Section 4.2 is P1 or P2, we choose point D as the final BEP to avoid a large localization error. Similar to the first case, we also expect that the localization error of i will decrease with the running of the WSLA when more neighbors become known in the following rounds.Figure 5
Node localization with two neighbors.PointD can be obtained using the following steps:(a)
Make a straight lineAB, the connecting line of points A and B.(b)
Make the vertical line ofAB from P1 or P2.(c)
Take the intersection (pointD) of the two lines as the final BEP of C.We assume that the coordinates ofA, B, P1 (or P2), and D are (xA,yA), (xB,yB), (xP,yP), and (xD,yD), respectively, and then the coordinates of D are as follows:(11)xD=b1-b2k2-k1,yD=k1xD+b1,where(12)k1=yA-yBxA-xB,k2=-1k1,b1=yA-k1xA,b2=yP-k2xP.


## 4.4. Node Localization Precision Classification Scheme

We define a FIFO queueQi with a size of lq for each node i, and we denote qi as the quantity of the elements in Qi. After each round, we put the BEP of node i into queue Qi and calculate the centroid of polygon Ψi which is formed by all elements in queue Qi.At the beginning, there are only anchor nodes and unknown nodes in the networks. During localization algorithm running, the WSLA gradually classifies unknown nodes intoNH and NL according to the following rule:Rule 1.
The WSLA classifies nodei into NH if all following conditions are satisfied:(i)
Its queueQi is full, namely, qi=lq.(ii)
The distance from any element inQi to the centroid of Ψi is not greater than a threshold Td.Rule 2.
The WSLA classifies nodei into NL if any of the following conditions are satisfied:(i)
Its queueQi is not full but not empty, namely, 0<qi<lq.(ii)
The distance from some element inQi to the centroid of Ψi is greater than the threshold Td.An example of node localization precision classification is shown in Figure6. In Figure 6, we assume qi=lq=5; that is to say, Qi is full. Because the distance from any element in Qi to the centroid of Ψi is not greater than Td in Figure 6(a), this node is classified into NH. In Figure 6(b), the distance from (x3,y3) to the centroid is greater than Td; thus, this node is classified into NL.Figure 6
An example of node localization precision classification.In addition, we also observe that the node localization sequence has an obvious influence on the localization accuracy for some localization scenes, as described in [23]. Specifically, in the initial several rounds of the WSLA, if a node with a large localization error takes part in the localization process of other nodes, its localization error may propagate due to the recursive localization method and thus results in a network localization accuracy decline. In order to avoid the emergence of this situation, in the initial several rounds (e.g., the first 30% rounds), the WSLA employs the following method to detect the node with a large localization error.Rule 3.
If the absolute difference value betweendij (network distance) and deij (range distance) from node i to j in Ni is greater than the error threshold err_th, we think that i is not localized accurately, and the WSLA classifies i into NU by 25% probability and NL by 75% probability to avoid or decrease the localization error propagated. Rule 3 is concluded as shown in (13)∀i,∃j∈Ni,dij-deij>err_th,dij=xeik-xejk-1⟹i∈NUp=0.25i∈NLp=0.75.


## 4.5. The Specific Flow of the WSLA

The specific steps of the WSLA in each round are as follows.Step 1 (node broadcasting).
All nodes except unknown nodes broadcast their messages, for example, transmitting power, ID, coordinates, and types, at the beginning of each round.Step 2 (RSSI ranging).
All nodes except anchor nodes receive messages from their neighbors and calculate the range distances according to (2). In our simulations, each node carries out 10 RSSI ranges in each round, and the final range distance is the average results.Step 3 (node localization).
If the number of known neighbors of nodei is larger than 1, the WSLA employs the search method in Section 4.2 to search its BEP.Step 4 (Special node processing).
If nodei is a special node, the WSLA employs the scheme in Section 4.3 to compute its new BEP.Step 5 (node classification).
The WSLA puts the BEP into queueQi and determines the localization type of the current round based on the Rules 1–3 in Section 4.4.In addition, when the position errors of anchor nodes is not zero, the WSLA degrades the anchor nodes into low precision nodes to refine their positions after running 15 rounds.


## 5. Simulation Experiments

To prove the localization accuracy of the WSLA, we have carried out extensive simulations using MATLAB software.


### 5.1. Experiment Parameters

The default simulation parameters are as follows: the number of total nodes is 108, including 8 anchor nodes and 100 unknown nodes; the positions of the anchor nodes are fixed and their coordinates are [0.1, 0.1], [0.1, 0.5], [0.1, 0.9], [0.5, 0.1], [0.5, 0.9], [0.9, 0.1], [0.9, 0.5], and [0.9, 0.9]; the unknown nodes are uniformly distributed in a square region of 1 × 1; the communication rangeR=0.22, leading to an average connectivity of the nodes of about 13; and nf=0.3,initial_step=0.75×R,max_round = 60, Td = 0.01R, andstop_th=0.01×R; in addition, we seterr_th=0.005R+0.1×na, and na is the maximum position errors of the anchor nodes; that is, xei-xri≤na, i∈NA, where xri and xei are the real coordinates and the localized coordinates of the node i and the default value of na is 0.2R. The experimental results are the averaged results of 30 experiments, and the range error εr and localization error εl, defined in (14) and (15), respectively, are used as the performance standard:(14)εr=1M∑i,jdeij-drijR,(15)εl=1N∑i=1Nxei-xriR,N=NU.In (14), deij and drij are the range distances and the real distances between nodes i and j; M is the total range time.


### 5.2. The Performance of the WSLA

(1) The Convergence Process of the WSLA. We first examine the convergence performance of the WSLA in the ideal range condition, that is, nf=0, leading to deij=drij. In this experiment, we reset the following parameters:stop_th=0.001×R, Td=0.001R,max_round = 120, nf=0, and na=0. The convergence process of the WSLA is presented in Figure 7.Figure 7
The convergence process of the WSLA.From Figure7, we can observe the following. (1) The WSLA is convergent, and the localization error in the initial several rounds is relatively large because the number of known neighbors of each node is relatively small. (2) Even in ideal conditions, the WSLA cannot converge to 0. In our 30 experiments, the best scene and the worst scene converge to about 0.001R and 0.021R, respectively, and all scenes converge to about 0.006R on average. The reason that the WSLA cannot converge to 0 is because stop_th is not equal to zero, and sometimes the WSLA may fall into the local optima. (3) The convergence process is not strictly monotonic. After the WSLA runs about 60 rounds, the average localization error is near 0.01R, and it decreases only 0.004R during the last 60 rounds. Therefore, in the following experiments, we set that max_round = 60.(2) The Relationship between
ε
l
and stop_th. Second, we examine the relationship between εl and stop_th in the ideal range condition. In this experiment,nf = 0,na = 0, and the other parameters are set to their default values. The relationship between εl and stop_th of the WSLA is presented in Figure 8.Figure 8
The relationship betweenεl and stop_th.From Figure8, we can see that the correlation between εl and stop_th is significant. Specifically, the smaller stop_th is, the lower the localization error will be. However, a small stop_th means more search points and thus the time complexity of the WSLA will increase. In addition, when stop_th equalsR, the WSLA will degrade into a centroid localization algorithm because it cannot search any points. In order to achieve the tradeoff between localization error and complexity, in the following experiments, we set stop_th to 0.01R, which means that the WSLA searches 7 iterations and a total of 57 points in each round. Figure 8 also shows that the WSLA makes a vast improvement compared to the centroid localization algorithm when stop_th = 0.01R.(3) The Relationship between
ε
l
and nf or na. Third, we show the localization performance of the WSLA with the variation ofnf orna, and the results are presented in Figure 9.Figure 9
The relationship of betweenεl andnf orna.
(a)
ε
l with the variation ofnf atna = 0
(b)
ε
l with the variation ofna atnf = 0From Figure9, we can see the following. (1) Both range errors and localization errors increase with the growth ofnf, but range errors increase faster than localization errors. (2) The WSLA is more sensitive tona thannf. Specifically, the change of εl is up to about 0.1R whenna varies from 0 to 0.5R, and by comparison, the change of εl is only about 0.007R whennf varies from 0 to 0.5.(4) The Relationship between
ε
l
and the Node Connectivity. In this experiment, we setnf = 0.3 andna = 0.2R, and vary the node connectivity by changing the number of unknown nodes. The relationship between εl and the connectivity is shown in Figure 10, and we find that (1) εl decreases with the growth of the connectivity, and (2) after the average connectivity of the nodes reaches 22, the change of εl is very small.Figure 10
Localization error versus the number of nodes.(5) The Localization Results of a Typical Scene. Finally, we give the straightforward localization results of one typical scene. In this experiment, all parameters are default values. The reason we choose this scene is that its localization error is slightly larger than the average localization error. In Figure 11, ○ denotes the real position of anchor nodes, × denotes the real position of unknown nodes, and ◊ denotes the localized position of nodes. The green nodes are high-precision nodes and the red nodes are low-precision nodes. By comparing Figures 11(a)–11(c), we can obviously see that the localization error becomes gradually smaller, and from Figure 11(d), we can see that the εl of 88% nodes is less than 0.15R. Therefore, the localization performance of the WSLA is good.Figure 11
The localization results of one typical scene.
(a)
ε
l = 0.203R, rounds = 10
(b)
ε
l = 0.118R, rounds = 30
(c)
ε
l = 0.104R, rounds = 60
(d)
Distribution of localization error


### 5.3. Performance Comparison with MLE, PSO, and ESOCP + NCSG

In this section, we have compared the localization error of the WSLA with that of MLE [12], ESOCP + NCSG [11], and PSO [21], which are three representatives of state-of-art localization algorithms. Specifically, MLE is representative of a simple localization algorithm, PSO is representative of a search-based localization algorithm, and ESOCP + NCSG is representative of a complex relaxation-based localization algorithm. In this experiment, we use the range model in [11], as shown in (16); the other parameters are the same as the default parameters. The parameters of PSO are set as follows: population = 30, iterations = 60; acceleration constants c1 = c2 = 2.0; inertial weight is decreased linearly from 0.9 in the first iteration to 0.4 in the last iteration. In addition, to better demonstrate the performance of the WSLA, we also show the performance of the basic search localization algorithm (SLA), which does not employ a localization precision classification scheme, a processing scheme for special nodes, and a simple scheme for detecting nodes with large localization errors. The experimental results are shown in Figure 12:(16)deij=drij∗1+nf∗randn,where deij and drij are the range distance and real distance, respectively; nf also represents the error level; rand n is the random variable subjected to standard normal distribution N (0, 1).Figure 12
Performance comparison with other localization algorithms.
(a)
na = 0.2R
(b)
nf = 0.1From Figure12, we can see the following: (1) The localization performance of the WSLA is the best of these five algorithms. (2) MLE and ESOCP + NCSG are more sensitive to range errors than PSO, SLA, and the WSLA. (3) All the algorithms are sensitive to the position errors of anchor nodes. The explanations for the high performance of the WSLA are as follows. (1) Compared with PSO, the WSLA has a heuristic search process and can significantly reduce the number of search points, for example, it searches 57 points per node, while PSO searches 1800 points per node in each round. (2) Compared with ESOCP + NCSG, the WSLA does not carry out its objective function in any form of relaxation. (3) Compared with MLE, the WSLA has better fault tolerance to range errors and the distribution of neighbors. (4) More importantly, the WSLA has integrated three schemes, namely, a FIFO-based localization precision classification scheme, a processing scheme for localizing the special nodes, and a simple scheme for detecting nodes with large localization errors, to further improve its localization accuracy.


## 5.1. Experiment Parameters

The default simulation parameters are as follows: the number of total nodes is 108, including 8 anchor nodes and 100 unknown nodes; the positions of the anchor nodes are fixed and their coordinates are [0.1, 0.1], [0.1, 0.5], [0.1, 0.9], [0.5, 0.1], [0.5, 0.9], [0.9, 0.1], [0.9, 0.5], and [0.9, 0.9]; the unknown nodes are uniformly distributed in a square region of 1 × 1; the communication rangeR=0.22, leading to an average connectivity of the nodes of about 13; and nf=0.3,initial_step=0.75×R,max_round = 60, Td = 0.01R, andstop_th=0.01×R; in addition, we seterr_th=0.005R+0.1×na, and na is the maximum position errors of the anchor nodes; that is, xei-xri≤na, i∈NA, where xri and xei are the real coordinates and the localized coordinates of the node i and the default value of na is 0.2R. The experimental results are the averaged results of 30 experiments, and the range error εr and localization error εl, defined in (14) and (15), respectively, are used as the performance standard:(14)εr=1M∑i,jdeij-drijR,(15)εl=1N∑i=1Nxei-xriR,N=NU.In (14), deij and drij are the range distances and the real distances between nodes i and j; M is the total range time.


## 5.2. The Performance of the WSLA

(1) The Convergence Process of the WSLA. We first examine the convergence performance of the WSLA in the ideal range condition, that is, nf=0, leading to deij=drij. In this experiment, we reset the following parameters:stop_th=0.001×R, Td=0.001R,max_round = 120, nf=0, and na=0. The convergence process of the WSLA is presented in Figure 7.Figure 7
The convergence process of the WSLA.From Figure7, we can observe the following. (1) The WSLA is convergent, and the localization error in the initial several rounds is relatively large because the number of known neighbors of each node is relatively small. (2) Even in ideal conditions, the WSLA cannot converge to 0. In our 30 experiments, the best scene and the worst scene converge to about 0.001R and 0.021R, respectively, and all scenes converge to about 0.006R on average. The reason that the WSLA cannot converge to 0 is because stop_th is not equal to zero, and sometimes the WSLA may fall into the local optima. (3) The convergence process is not strictly monotonic. After the WSLA runs about 60 rounds, the average localization error is near 0.01R, and it decreases only 0.004R during the last 60 rounds. Therefore, in the following experiments, we set that max_round = 60.(2) The Relationship between
ε
l
and stop_th. Second, we examine the relationship between εl and stop_th in the ideal range condition. In this experiment,nf = 0,na = 0, and the other parameters are set to their default values. The relationship between εl and stop_th of the WSLA is presented in Figure 8.Figure 8
The relationship betweenεl and stop_th.From Figure8, we can see that the correlation between εl and stop_th is significant. Specifically, the smaller stop_th is, the lower the localization error will be. However, a small stop_th means more search points and thus the time complexity of the WSLA will increase. In addition, when stop_th equalsR, the WSLA will degrade into a centroid localization algorithm because it cannot search any points. In order to achieve the tradeoff between localization error and complexity, in the following experiments, we set stop_th to 0.01R, which means that the WSLA searches 7 iterations and a total of 57 points in each round. Figure 8 also shows that the WSLA makes a vast improvement compared to the centroid localization algorithm when stop_th = 0.01R.(3) The Relationship between
ε
l
and nf or na. Third, we show the localization performance of the WSLA with the variation ofnf orna, and the results are presented in Figure 9.Figure 9
The relationship of betweenεl andnf orna.
(a)
ε
l with the variation ofnf atna = 0
(b)
ε
l with the variation ofna atnf = 0From Figure9, we can see the following. (1) Both range errors and localization errors increase with the growth ofnf, but range errors increase faster than localization errors. (2) The WSLA is more sensitive tona thannf. Specifically, the change of εl is up to about 0.1R whenna varies from 0 to 0.5R, and by comparison, the change of εl is only about 0.007R whennf varies from 0 to 0.5.(4) The Relationship between
ε
l
and the Node Connectivity. In this experiment, we setnf = 0.3 andna = 0.2R, and vary the node connectivity by changing the number of unknown nodes. The relationship between εl and the connectivity is shown in Figure 10, and we find that (1) εl decreases with the growth of the connectivity, and (2) after the average connectivity of the nodes reaches 22, the change of εl is very small.Figure 10
Localization error versus the number of nodes.(5) The Localization Results of a Typical Scene. Finally, we give the straightforward localization results of one typical scene. In this experiment, all parameters are default values. The reason we choose this scene is that its localization error is slightly larger than the average localization error. In Figure 11, ○ denotes the real position of anchor nodes, × denotes the real position of unknown nodes, and ◊ denotes the localized position of nodes. The green nodes are high-precision nodes and the red nodes are low-precision nodes. By comparing Figures 11(a)–11(c), we can obviously see that the localization error becomes gradually smaller, and from Figure 11(d), we can see that the εl of 88% nodes is less than 0.15R. Therefore, the localization performance of the WSLA is good.Figure 11
The localization results of one typical scene.
(a)
ε
l = 0.203R, rounds = 10
(b)
ε
l = 0.118R, rounds = 30
(c)
ε
l = 0.104R, rounds = 60
(d)
Distribution of localization error


## 5.3. Performance Comparison with MLE, PSO, and ESOCP + NCSG

In this section, we have compared the localization error of the WSLA with that of MLE [12], ESOCP + NCSG [11], and PSO [21], which are three representatives of state-of-art localization algorithms. Specifically, MLE is representative of a simple localization algorithm, PSO is representative of a search-based localization algorithm, and ESOCP + NCSG is representative of a complex relaxation-based localization algorithm. In this experiment, we use the range model in [11], as shown in (16); the other parameters are the same as the default parameters. The parameters of PSO are set as follows: population = 30, iterations = 60; acceleration constants c1 = c2 = 2.0; inertial weight is decreased linearly from 0.9 in the first iteration to 0.4 in the last iteration. In addition, to better demonstrate the performance of the WSLA, we also show the performance of the basic search localization algorithm (SLA), which does not employ a localization precision classification scheme, a processing scheme for special nodes, and a simple scheme for detecting nodes with large localization errors. The experimental results are shown in Figure 12:(16)deij=drij∗1+nf∗randn,where deij and drij are the range distance and real distance, respectively; nf also represents the error level; rand n is the random variable subjected to standard normal distribution N (0, 1).Figure 12
Performance comparison with other localization algorithms.
(a)
na = 0.2R
(b)
nf = 0.1From Figure12, we can see the following: (1) The localization performance of the WSLA is the best of these five algorithms. (2) MLE and ESOCP + NCSG are more sensitive to range errors than PSO, SLA, and the WSLA. (3) All the algorithms are sensitive to the position errors of anchor nodes. The explanations for the high performance of the WSLA are as follows. (1) Compared with PSO, the WSLA has a heuristic search process and can significantly reduce the number of search points, for example, it searches 57 points per node, while PSO searches 1800 points per node in each round. (2) Compared with ESOCP + NCSG, the WSLA does not carry out its objective function in any form of relaxation. (3) Compared with MLE, the WSLA has better fault tolerance to range errors and the distribution of neighbors. (4) More importantly, the WSLA has integrated three schemes, namely, a FIFO-based localization precision classification scheme, a processing scheme for localizing the special nodes, and a simple scheme for detecting nodes with large localization errors, to further improve its localization accuracy.


## 6. Conclusion

The localization technique is one of the key techniques in practical WSN application. On the basis of analyzing the error distribution features of the traditional RSSI-based range model and the measured RSSI data, we improve the RSSI-based range model. We also propose a novel WSLA, which is a range-based heuristic distributed localization algorithm for WSNs. The innovative ideas of the WSLA include a FIFO-based localization precision classification scheme, a processing scheme for special nodes, and a weight-based search. The performance of the WSLA is evaluated by comparing it with three state-of-art localization algorithms, namely, MLE, ESOCP + NCSG, and PSO. The experimental results show that the localization performance of the WSLA is superior to that of MLE, ESOCP + NCSG, and PSO. The features of our algorithm are distributed, low complexity withO(m) (m is the number of one-hop neighbor nodes), easy implementation, and high localization accuracy. Therefore, it has good reference value in engineering practice. Our future works will study the adaptive parameter settings of the WSLA and evaluate its localization performance in real WSNs.



---

*Source: 293403-2015-04-28.xml*