# Localization Algorithm Based on Iterative Centroid Estimation for Wireless Sensor Networks

Authors: Rui Jiang; Xin Wang; Li Zhang
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

According to the application of range-free localization technology for wireless sensor networks (WSNs), an improved localization algorithm based on iterative centroid estimation is proposed in this paper. With this methodology, the centroid coordinate of the space enclosed by connected anchor nodes and the received signal strength indication (RSSI) between the unknown node and the centroid are calculated. Then, the centroid is used as a virtual anchor node. It is proven that there is at least one connected anchor node whose distance from the unknown node must be farther than the virtual anchor node. Hence, in order to reduce the space enclosed by connected anchor nodes and improve the location precision, the anchor node with the weakest RSSI is replaced by this virtual anchor node. By applying this procedure repeatedly, the localization algorithm can achieve a good accuracy. Observing from the simulation results, the proposed algorithm has strong robustness and can achieve an ideal performance of localization precision and coverage.


---

## Body

## 1. Introduction

Wireless sensor network (WSNs) is comprised of multiple sensor nodes through self-organization. It is considered as an information acquisition system for Internet of Things (IoT). The sensor nodes in WSNs generally fall into two categories: the anchor nodes and the unknown nodes. The anchor node’s location is already known, whereas the unknown node’s location is not. However, the information collected by a sensor is usually nonsense without the sensor’s location information. Hence, an accurate node self-location is one of the fundamental and hot problems in the research of WSNs [1, 2]. A variety of algorithms exist for node self-location. Most of these algorithms can be divided into two categories. One is range-based measurement, which realizes self-location of an unknown node by computing the distance or direction between the unknown node and nearby anchor nodes like the received signal strength indication (RSSI) algorithm [3–5], the time of arrival (TOA) algorithm [6, 7], the time difference of arrival (TDOA) algorithm [8], and so forth [9, 10]. This class shows a very accurate location result but is generally very energy-consuming. Furthermore, the additional hardware is usually required. It also increases the overall cost of WSNs. The other one is range-free measurement, which utilizes the connectivity of WSNs to obtain the location information of an unknown node, such as the centroid localization algorithm [11], the approximate point-in-triangulation test (APIT) algorithm [12, 13], the distance vector-hop (DV-Hop) algorithm [14, 15], and so forth [16]. This class is energy-efficient and does not require any additional hardware. Therefore, the range-free measurement is suitable for WSNs and is widely used in practice for its efficient realization.The number of connected anchor nodes is one of the key factors affecting the performance of localization algorithm, regardless of whether it is range-based measurement or range-free measurement. More connected anchor nodes allow greater location accuracy. However, the methods to improve the location accuracy by increasing the number of connected anchor nodes in WSNs are not available. In order to overcome such difficulty, an improved localization algorithm based on iterative centroid estimation is presented in this paper. Suppose that any two anchor nodes can only be connected by a straight line; the minimal space that can contain all connected anchor nodes is defined as the space enclosed by connected anchor nodes with this methodology. The centroid of this space is deemed as a virtual anchor node to achieve a more accurate localization. First, the centroid coordinate of the space enclosed by connected anchor nodes and the RSSI between the unknown node and the centroid are calculated. With the strict formula derivation, we prove that there exists at least one anchor node, which is further from the unknown node than the centroid. Then, the connected anchor node with the weakest RSSI is replaced with the centroid in order to reduce the space enclosed by the connected anchor nodes. Applying this procedure repeatedly, the localization algorithm can obtain good accuracy. We employ simulation experiments to verify the performance of our methods in terms of the localization precision, coverage, and robustness on RSSI error disturbance.


## 2. Localization Algorithm Based on Iterative Centroid Estimation

### 2.1. Virtual Anchor Nodes

Suppose that there are one unknown nodeSun and N anchor nodes S1S2S3⋯SN which are connected with Sun. For an arbitrary anchor node Sn in S1S2S3⋯SN, it is assumed that the coordinate of Sun is x,y,z and the coordinate of Sn is xn,yn,zn. Therefore the distance between Sn and Sun is(1)dn=xn-x2+yn-y2+zn-z21≤n≤N.We denote byO1 the centroid of the space enclosed by S1S2S3⋯SN. Assume that the coordinate of O1 is xO1,yO1,zO1. Then, we have(2)xO1=1N∑n=1NxnyO1=1N∑n=1NynzO1=1N∑n=1Nzn.The distance between O1 and Sun can be calculated as(3)dO1=xO1-x2+yO1-y2+zO1-z2.Using (2), dO1 can be expressed as(4)dO1=1N∑n=1Nxn-x2+1N∑n=1Nyn-y2+1N∑n=1Nzn-z2=1N∑n=1Nxn-Nx2+∑n=1Nyn-Ny2+∑n=1Nzn-Nz2=1N∑n=1Nxn-x2+∑n=1Nyn-y2+∑n=1Nzn-z2=1N∑n=1Nxn-x2+∑n=1Nyn-y2+∑n=1Nzn-z2+2·∑i=1N-1∑j=i+1Nxi-xxj-x+2·∑i=1N-1∑j=i+1Nyi-yyj-y+2·∑i=1N-1∑j=i+1Nzi-zzj-z.Withi≠j, we have(5)2xi-xxj-x=2xixj-2xix-2xjx+2x2=xi-x2+xj-x2-xi-xj22yi-yyj-y=2yiyj-2yiy-2yjy+2y2=yi-y2+yj-y2-yi-yj22zi-zzj-z=2zizj-2ziz-2zjz+2z2=zi-z2+zj-z2-zi-zj2.From (5), (4) can be simplified as(6)dO1=1NN∑n=1Nxn-x2+N∑n=1Nyn-y2+N∑n=1Nzn-z2-∑i=1N-1∑j=i+1Nxi-xj2-∑i=1N-1∑j=i+1Nyi-yj2-∑i=1N-1∑j=i+1Nzi-zj2=1N∑n=1Ndn2-1N2∑i=1N-1∑j=i+1Nxi-xj2+∑i=1N-1∑j=i+1Nyi-yj2+∑i=1N-1∑j=i+1Nzi-zj2.According to (2) and (6), it is clear that the coordinate of O1 and the distance between O1 and Sun can be calculated relying only on the known parameters of connected anchor nodes. Now, the centroid O1 has the common features of all the connected anchor nodes. Hence, it can be considered as a virtual anchor node.


### 2.2. The Convergence Performance of Iterative Centroid Estimation

We denote the distance betweenSi and Sj as(7)dij=xi-xj2+yi-yj2+zi-zj2i≠j.Then, (4) can be further simplified by rewriting (6) as(8)dO1=1N∑n=1Ndn2-1N2∑i=1N-1∑j=i+1Ndij2.In general, it is assumed that0<d1≤d2≤d3≤⋯≤dN-1≤dN. It is easy to show that(9)1N∑n=1Ndn2≤dN21N2∑i=1N-1∑j=i+1Ndij2>0.From (8)-(9), we can draw the conclusion that dO1<dN. Obviously, there exists at least one connected anchor node SN whose distance from Sun must be farther than dO1. Therefore, the space enclosed by S1S2S3⋯SN-1 and O1 must be smaller than the original space enclosed by S1S2S3⋯SN. In the proposed algorithm, the centroid O1 is deemed as a virtual anchor node. The farthest anchor node SN would be replaced by the virtual anchor node O1 in order to reduce the enclosed space and improve the location precision. The algorithm can achieve a more accurate localization by repeating the described replacement procedure.


### 2.3. The Energy Consumption in Localization Algorithm

Based on the fact that each node in WSNs has only limited energy, it is crucial to control energy consumption in localization algorithm to extend the WSNs lifetime. However, the calculation ofdn will greatly increase the node energy consumption. To solve this problem, RSSI is used directly to represent distance information in proposed localization algorithm. Based on the propagation theory, the relationship between distance and RSSI is mentioned in [17]:(10)P1Pn=dnd1M.Here,Pn refers to RSSI between Sn and Sun. M is a factor of distance attenuation. The value of M is determined according to the working environment of WSNs. A large amount of experimental data evidences that the optimal range of the empirical attenuation factor M is 3.24~4.5. In practical application, the value of M can be further determined by the RSSI and the distance between anchor nodes. Let d1=1; (10) can be rewritten after taking logarithm:(11)10log10Pn=-A+10Mlog10dn,where(12)A=-10log10P1.The parameterA represents the RSSI when the distance to the node is one meter. As well as parameter M, the value of A is determined according to the working environment of WSNs. After parameter M is determined, the value of A can also be further calculated by the RSSI and the distance between anchor nodes. In some practical application such as ZigBee, the optimum A is given empirically from 45 to 49. From (8) and (11), we can derive that RSSI between the virtual anchor node O1 and Sun is(13)PO1=11/N∑n=1NPn-2/M-10A/5M/N2∑i=1N-1∑j=i+1Ndij2M/2.The weaker RSSI is, the farther the distance will be. Using (13), the energy consumption in proposed localization algorithm can be reduced effectively via avoiding the procedure of distance calculation. To improve the location precision, the centroid is used as a virtual anchor node to replace the connected anchor node with the weakest RSSI. Besides, it is noteworthy that the two-dimensional node localization can be viewed as special three-dimensional node localization with the same height across all the nodes. Hence, the proposed algorithm can also be applied to two-dimensional node localization.


### 2.4. The Stopping Criterion of the Localization Algorithm

During thenth iteration, suppose that the N connected anchor nodes are S1S2S3⋯SN. The distance dOn between the centroid On and the unknown node Sun can be determined according to (8), which satisfies(14)dOn2=1N∑n=1Ndn2-1N2∑i=1N-1∑j=i+1Ndij2,where dn is the distance between anchor node Sn and unknown node Sun defined in (1). dij is the distance between anchor node Si and Sj defined in (7). In general, it is assumed that 0<d1≤d2≤d3≤⋯≤dN-1≤dN. Similarly, the distance dOn+1 between the centroid On+1 and the unknown node Sun during the n+1th iteration should satisfy the following equation:(15)dOn+12=1N∑n=1N-1dn2+dOn2-1N2∑i=1N-1∑j=i+1N-1dij2+∑i=1N-1diOn2,where diOn is the distance between anchor node Si and the centroid On derived from the nth iteration. From (8) and (11), we have(16)dOn2-dOn+12=1NdN2-dOn2+1N2∑i=1N-1diOn2-∑i=1N-1diN2=F1+F2;here,(17)F1=1NdN2-dOn2F2=1N2∑i=1N-1diOn2-∑i=1N-1diN2.According to (9), we can easily get the conclusion that F1>0. When the coordinate of Sn is xn,yn,zn, F2 can be expressed as(18)F2=1N2∑i=1N-1∑j=1NxjN-xi2+∑j=1NyjN-yi2+∑j=1NzjN-zi2-∑i=1N-1xN-xi2+yN-yi2+zN-zi2=1N2Fx+Fy+Fz,where(19)Fx=∑i=1N-1∑j=1NxjN-xi2-xN-xi2Fy=∑i=1N-1∑j=1NyjN-yi2-yN-yi2Fz=∑i=1N-1∑j=1NzjN-zi2-zN-zi2.Then,Fx can be further simplified as(20)Fx=∑i=1N-1∑j=1NxjN-xi2-xN-xi2=N-1∑j=1NxjN2-2∑j=1NxjN·∑i=1N-1xi-N-1xN2+2xN·∑i=1N-1xi=-N+1∑j=1NxjN2+2N+1xN∑j=1NxjN-N+1xN2=-N+1∑j=1NxjN-xN2.Similarly,(21)Fy=∑i=1N-1∑j=1NyjN-yi2-yN-yi2=-N+1∑j=1NyjN-yN2.Fz=∑i=1N-1∑j=1NzjN-zi2-zN-zi2=-N+1∑j=1NzjN-zN2From (20)-(21), F2 can be simplified as(22)F2=-N+1N2∑j=1NxjN-xN2+∑j=1NyjN-yN2+∑j=1NzjN-zN2=-N+1N2dNOn2<0;here, dNOn is the distance between anchor node SN and the centroid On derived from the nth iteration. With (16)–(22), we have(23)dOn2-dOn+12=1NdN2-dOn2-N+1N2dNOn2.Obviously, we cannot guarantee the location accuracy of then+1th iteration to be higher than that of the nth iteration. Take two-dimensional node localization as an example; we assume the simplest situation, that is, when the number of connected anchor nodes N=3 to give a more intuitive description of this problem. The relationship of the position between O and original anchor nodes is shown in Figure 1.Figure 1
The relationship of the position between the unknown node and the area enclosed by anchor nodes.
(a) (b) (c)In Figure1, ΔS1S2S3 is an equilateral triangle whose centroid is O1. Based on the algorithm we propose, we replace S1 with O1 to create a new enclosed area because S1 is the farthest node away from the unknown node Sun in the figure. In Figures 1(a) and 1(b), Sun is inside of the area enclosed by the original anchor nodes S1S2S3. We suppose that Sun lies on the line segment O1O2. In Figure 1(a), Sun lies on the upper middle of O1O2, which means that it is closer to the centroid O1. Clearly the location result O2 in the second iteration has higher accuracy than O1 in the first iteration. On the contrary, in Figure 1(b), Sun lies on the lower middle of O1O2, which means that it is closer to the centroid O2. It means that the location accuracy of O2 is even worse than O1. The analysis agrees well with the conclusion of (23). Under this circumstance, the iteration should be stopped when the distance between Sun and the current centroid On is smaller than a certain threshold. Using (13), the stopping criterion of the localization algorithm can be expressed as(24)POn>ε1,where ε1 is the threshold. However, Sun is outside of the area enclosed by the original anchor nodes S1S2S3 in Figure 1(c). The estimated centroid cannot be infinitely close to Sun with the increasing of iterations. In this situation, the stopping criterion of (24) will make the algorithm fall in an endless loop. Hence, the iteration should be stopped when the variation of the location accuracy is smaller than a certain threshold. We have another stopping criterion of the localization algorithm as(25)POn-POn-1<ε2here, ε2 is the threshold.Thus, how to set the stopping criterion of algorithm should depend on the relative position of the unknown nodeSun and the area enclosed by the connected anchor nodes. In order to use fewer iterations to achieve better accuracy and avoid the algorithm falling into an endless loop at the same time, the two sets of stopping criterion are both used simultaneously. The iteration should be stopped when any stopping criterion is satisfied.


### 2.5. Description of the Localization Algorithm

In this section, we will present a detailed description of the algorithm. All the quantities that should be computed to implement the algorithm will be listed in the right order. The concrete implementation steps of the novel localization algorithm are explained as follows:(1)
Set the stopping criterion by (24)-(25).(2)
In practical application, the connected anchor nodes must be confirmed firstly. Then, the RSSI is measured and the distancedij is calculated by (7) between any two connected anchor nodes.(3)
Based on above data in step(2), the empirical factors M and A could be determined by (10)–(12).(4)
Since the coordinates of anchor nodes are known, the centroid coordinate of the space enclosed by connected anchor nodes can be calculated by (2).(5)
After the RSSI between the unknown node and the connected anchor nodePn is measured, the RSSI between the unknown node and the current centroid POn could be calculated by (13).(6)
IfPOn satisfies the stopping criterion in step (1), the current centroid is the estimated position of the unknown node in the proposed algorithm; otherwise, the current centroid is deemed as a virtual anchor node. Then, the connected anchor node with the weakest RSSI is replaced with the virtual anchor node. The distance diOn between the virtual anchor node and the remaining connected anchor nodes is calculated by (7) and the process returns to step (4).The flowchart of the proposed localization algorithm is shown in Figure2.Figure 2
The flowchart of localization algorithm based on iterative centroid estimation.


## 2.1. Virtual Anchor Nodes

Suppose that there are one unknown nodeSun and N anchor nodes S1S2S3⋯SN which are connected with Sun. For an arbitrary anchor node Sn in S1S2S3⋯SN, it is assumed that the coordinate of Sun is x,y,z and the coordinate of Sn is xn,yn,zn. Therefore the distance between Sn and Sun is(1)dn=xn-x2+yn-y2+zn-z21≤n≤N.We denote byO1 the centroid of the space enclosed by S1S2S3⋯SN. Assume that the coordinate of O1 is xO1,yO1,zO1. Then, we have(2)xO1=1N∑n=1NxnyO1=1N∑n=1NynzO1=1N∑n=1Nzn.The distance between O1 and Sun can be calculated as(3)dO1=xO1-x2+yO1-y2+zO1-z2.Using (2), dO1 can be expressed as(4)dO1=1N∑n=1Nxn-x2+1N∑n=1Nyn-y2+1N∑n=1Nzn-z2=1N∑n=1Nxn-Nx2+∑n=1Nyn-Ny2+∑n=1Nzn-Nz2=1N∑n=1Nxn-x2+∑n=1Nyn-y2+∑n=1Nzn-z2=1N∑n=1Nxn-x2+∑n=1Nyn-y2+∑n=1Nzn-z2+2·∑i=1N-1∑j=i+1Nxi-xxj-x+2·∑i=1N-1∑j=i+1Nyi-yyj-y+2·∑i=1N-1∑j=i+1Nzi-zzj-z.Withi≠j, we have(5)2xi-xxj-x=2xixj-2xix-2xjx+2x2=xi-x2+xj-x2-xi-xj22yi-yyj-y=2yiyj-2yiy-2yjy+2y2=yi-y2+yj-y2-yi-yj22zi-zzj-z=2zizj-2ziz-2zjz+2z2=zi-z2+zj-z2-zi-zj2.From (5), (4) can be simplified as(6)dO1=1NN∑n=1Nxn-x2+N∑n=1Nyn-y2+N∑n=1Nzn-z2-∑i=1N-1∑j=i+1Nxi-xj2-∑i=1N-1∑j=i+1Nyi-yj2-∑i=1N-1∑j=i+1Nzi-zj2=1N∑n=1Ndn2-1N2∑i=1N-1∑j=i+1Nxi-xj2+∑i=1N-1∑j=i+1Nyi-yj2+∑i=1N-1∑j=i+1Nzi-zj2.According to (2) and (6), it is clear that the coordinate of O1 and the distance between O1 and Sun can be calculated relying only on the known parameters of connected anchor nodes. Now, the centroid O1 has the common features of all the connected anchor nodes. Hence, it can be considered as a virtual anchor node.


## 2.2. The Convergence Performance of Iterative Centroid Estimation

We denote the distance betweenSi and Sj as(7)dij=xi-xj2+yi-yj2+zi-zj2i≠j.Then, (4) can be further simplified by rewriting (6) as(8)dO1=1N∑n=1Ndn2-1N2∑i=1N-1∑j=i+1Ndij2.In general, it is assumed that0<d1≤d2≤d3≤⋯≤dN-1≤dN. It is easy to show that(9)1N∑n=1Ndn2≤dN21N2∑i=1N-1∑j=i+1Ndij2>0.From (8)-(9), we can draw the conclusion that dO1<dN. Obviously, there exists at least one connected anchor node SN whose distance from Sun must be farther than dO1. Therefore, the space enclosed by S1S2S3⋯SN-1 and O1 must be smaller than the original space enclosed by S1S2S3⋯SN. In the proposed algorithm, the centroid O1 is deemed as a virtual anchor node. The farthest anchor node SN would be replaced by the virtual anchor node O1 in order to reduce the enclosed space and improve the location precision. The algorithm can achieve a more accurate localization by repeating the described replacement procedure.


## 2.3. The Energy Consumption in Localization Algorithm

Based on the fact that each node in WSNs has only limited energy, it is crucial to control energy consumption in localization algorithm to extend the WSNs lifetime. However, the calculation ofdn will greatly increase the node energy consumption. To solve this problem, RSSI is used directly to represent distance information in proposed localization algorithm. Based on the propagation theory, the relationship between distance and RSSI is mentioned in [17]:(10)P1Pn=dnd1M.Here,Pn refers to RSSI between Sn and Sun. M is a factor of distance attenuation. The value of M is determined according to the working environment of WSNs. A large amount of experimental data evidences that the optimal range of the empirical attenuation factor M is 3.24~4.5. In practical application, the value of M can be further determined by the RSSI and the distance between anchor nodes. Let d1=1; (10) can be rewritten after taking logarithm:(11)10log10Pn=-A+10Mlog10dn,where(12)A=-10log10P1.The parameterA represents the RSSI when the distance to the node is one meter. As well as parameter M, the value of A is determined according to the working environment of WSNs. After parameter M is determined, the value of A can also be further calculated by the RSSI and the distance between anchor nodes. In some practical application such as ZigBee, the optimum A is given empirically from 45 to 49. From (8) and (11), we can derive that RSSI between the virtual anchor node O1 and Sun is(13)PO1=11/N∑n=1NPn-2/M-10A/5M/N2∑i=1N-1∑j=i+1Ndij2M/2.The weaker RSSI is, the farther the distance will be. Using (13), the energy consumption in proposed localization algorithm can be reduced effectively via avoiding the procedure of distance calculation. To improve the location precision, the centroid is used as a virtual anchor node to replace the connected anchor node with the weakest RSSI. Besides, it is noteworthy that the two-dimensional node localization can be viewed as special three-dimensional node localization with the same height across all the nodes. Hence, the proposed algorithm can also be applied to two-dimensional node localization.


## 2.4. The Stopping Criterion of the Localization Algorithm

During thenth iteration, suppose that the N connected anchor nodes are S1S2S3⋯SN. The distance dOn between the centroid On and the unknown node Sun can be determined according to (8), which satisfies(14)dOn2=1N∑n=1Ndn2-1N2∑i=1N-1∑j=i+1Ndij2,where dn is the distance between anchor node Sn and unknown node Sun defined in (1). dij is the distance between anchor node Si and Sj defined in (7). In general, it is assumed that 0<d1≤d2≤d3≤⋯≤dN-1≤dN. Similarly, the distance dOn+1 between the centroid On+1 and the unknown node Sun during the n+1th iteration should satisfy the following equation:(15)dOn+12=1N∑n=1N-1dn2+dOn2-1N2∑i=1N-1∑j=i+1N-1dij2+∑i=1N-1diOn2,where diOn is the distance between anchor node Si and the centroid On derived from the nth iteration. From (8) and (11), we have(16)dOn2-dOn+12=1NdN2-dOn2+1N2∑i=1N-1diOn2-∑i=1N-1diN2=F1+F2;here,(17)F1=1NdN2-dOn2F2=1N2∑i=1N-1diOn2-∑i=1N-1diN2.According to (9), we can easily get the conclusion that F1>0. When the coordinate of Sn is xn,yn,zn, F2 can be expressed as(18)F2=1N2∑i=1N-1∑j=1NxjN-xi2+∑j=1NyjN-yi2+∑j=1NzjN-zi2-∑i=1N-1xN-xi2+yN-yi2+zN-zi2=1N2Fx+Fy+Fz,where(19)Fx=∑i=1N-1∑j=1NxjN-xi2-xN-xi2Fy=∑i=1N-1∑j=1NyjN-yi2-yN-yi2Fz=∑i=1N-1∑j=1NzjN-zi2-zN-zi2.Then,Fx can be further simplified as(20)Fx=∑i=1N-1∑j=1NxjN-xi2-xN-xi2=N-1∑j=1NxjN2-2∑j=1NxjN·∑i=1N-1xi-N-1xN2+2xN·∑i=1N-1xi=-N+1∑j=1NxjN2+2N+1xN∑j=1NxjN-N+1xN2=-N+1∑j=1NxjN-xN2.Similarly,(21)Fy=∑i=1N-1∑j=1NyjN-yi2-yN-yi2=-N+1∑j=1NyjN-yN2.Fz=∑i=1N-1∑j=1NzjN-zi2-zN-zi2=-N+1∑j=1NzjN-zN2From (20)-(21), F2 can be simplified as(22)F2=-N+1N2∑j=1NxjN-xN2+∑j=1NyjN-yN2+∑j=1NzjN-zN2=-N+1N2dNOn2<0;here, dNOn is the distance between anchor node SN and the centroid On derived from the nth iteration. With (16)–(22), we have(23)dOn2-dOn+12=1NdN2-dOn2-N+1N2dNOn2.Obviously, we cannot guarantee the location accuracy of then+1th iteration to be higher than that of the nth iteration. Take two-dimensional node localization as an example; we assume the simplest situation, that is, when the number of connected anchor nodes N=3 to give a more intuitive description of this problem. The relationship of the position between O and original anchor nodes is shown in Figure 1.Figure 1
The relationship of the position between the unknown node and the area enclosed by anchor nodes.
(a) (b) (c)In Figure1, ΔS1S2S3 is an equilateral triangle whose centroid is O1. Based on the algorithm we propose, we replace S1 with O1 to create a new enclosed area because S1 is the farthest node away from the unknown node Sun in the figure. In Figures 1(a) and 1(b), Sun is inside of the area enclosed by the original anchor nodes S1S2S3. We suppose that Sun lies on the line segment O1O2. In Figure 1(a), Sun lies on the upper middle of O1O2, which means that it is closer to the centroid O1. Clearly the location result O2 in the second iteration has higher accuracy than O1 in the first iteration. On the contrary, in Figure 1(b), Sun lies on the lower middle of O1O2, which means that it is closer to the centroid O2. It means that the location accuracy of O2 is even worse than O1. The analysis agrees well with the conclusion of (23). Under this circumstance, the iteration should be stopped when the distance between Sun and the current centroid On is smaller than a certain threshold. Using (13), the stopping criterion of the localization algorithm can be expressed as(24)POn>ε1,where ε1 is the threshold. However, Sun is outside of the area enclosed by the original anchor nodes S1S2S3 in Figure 1(c). The estimated centroid cannot be infinitely close to Sun with the increasing of iterations. In this situation, the stopping criterion of (24) will make the algorithm fall in an endless loop. Hence, the iteration should be stopped when the variation of the location accuracy is smaller than a certain threshold. We have another stopping criterion of the localization algorithm as(25)POn-POn-1<ε2here, ε2 is the threshold.Thus, how to set the stopping criterion of algorithm should depend on the relative position of the unknown nodeSun and the area enclosed by the connected anchor nodes. In order to use fewer iterations to achieve better accuracy and avoid the algorithm falling into an endless loop at the same time, the two sets of stopping criterion are both used simultaneously. The iteration should be stopped when any stopping criterion is satisfied.


## 2.5. Description of the Localization Algorithm

In this section, we will present a detailed description of the algorithm. All the quantities that should be computed to implement the algorithm will be listed in the right order. The concrete implementation steps of the novel localization algorithm are explained as follows:(1)
Set the stopping criterion by (24)-(25).(2)
In practical application, the connected anchor nodes must be confirmed firstly. Then, the RSSI is measured and the distancedij is calculated by (7) between any two connected anchor nodes.(3)
Based on above data in step(2), the empirical factors M and A could be determined by (10)–(12).(4)
Since the coordinates of anchor nodes are known, the centroid coordinate of the space enclosed by connected anchor nodes can be calculated by (2).(5)
After the RSSI between the unknown node and the connected anchor nodePn is measured, the RSSI between the unknown node and the current centroid POn could be calculated by (13).(6)
IfPOn satisfies the stopping criterion in step (1), the current centroid is the estimated position of the unknown node in the proposed algorithm; otherwise, the current centroid is deemed as a virtual anchor node. Then, the connected anchor node with the weakest RSSI is replaced with the virtual anchor node. The distance diOn between the virtual anchor node and the remaining connected anchor nodes is calculated by (7) and the process returns to step (4).The flowchart of the proposed localization algorithm is shown in Figure2.Figure 2
The flowchart of localization algorithm based on iterative centroid estimation.


## 3. Experimental Results and Discussion

The performance of the proposed algorithm is evaluated by simulation experiments. Suppose that one thousand nodes are randomly distributed in three-dimensional space with a size of 100 × 100 × 100m3, and K of them are unknown nodes. It is assumed that the empirical factors M=4 and A=47. The plane of the three-dimensional space at z=50 height is used as the two-dimensional space in simulation experiments. The performance of localization algorithm is evaluated by relative localization error, which is defined by(26)ERROR¯=∑i=1KERRORiKR,where(27)ERRORi=x^i-xi2+y^i-yi2+z^i-zi2is the localization error and R refers to the communication radius. xi,yi,zi is the true coordinate of the ith unknown node and x^i,y^i,z^i is the estimation result. It is worth noting that z^i is equal to zi for two-dimensional node localization. We set the stopping criterion in simulation experiments as(28)POn>P1POn-POn-1<0.01P1;here, P1 represents the RSSI when the distance to the node is one meter. With A=47, P1 can be calculated from (12).First of all, the effect of connected anchor nodes on localization precision is investigated in Figure3 by changing anchor ratio and communication radius. The anchor ratio represents the proportion of anchor nodes in the total nodes and the communication radius means the maximum distance between two nodes that can be connected. Note that the larger anchor ratio and the greater communication radius, the more connected anchor nodes. The performance of the proposed algorithm for three-dimensional and two-dimensional node localization is shown in Figures 3(a) and 3(b), respectively. As can be seen, the number of connected anchor nodes determines the location precision in both three-dimensional space and two-dimensional space. The relative localization error decreases with the increasing of connected anchor nodes in general, regardless of differing application characteristics.Figure 3
The effect of connected anchor nodes on localization precision in (a) three-dimensional and (b) two-dimensional space.
(a) (b)In addition to high precise positioning, good robustness of localization algorithm is also particularly important. The RSSI measurement error is an important factor that influences robustness of the algorithm. The impact of RSSI measurement error in the proposed algorithm for three-dimensional and two-dimensional node localization is depicted in Figures4(a) and 4(b), respectively. Different anchor ratios and communication radii are chosen so as to make a comprehensive analysis of the effect of measurement error. The RSSI measurement consists of the actual RSSI value and a shadowing term as commonly assumed [18]. The relationship between the two terms is determined by the signal-to-noise ratio (SNR). SNR is given by(29)SNR=σa2σn2,where σa2 and σn2 refer to the signal and noise energy, respectively. Obviously, the RSSI measurement error increases with the decreasing of SNR.Figure 4
The effect of RSSI measurement error on localization precision in (a) three-dimensional and (b) two-dimensional space.
(a) (b)In the proposed algorithm, the RSSI measurement is used to find the connected anchor node with the weakest RSSI, which should be replaced by the virtual anchor node. The measurement error results in the connected anchor node with the weakest RSSI being remained. This mistake makes the convergence speed of this method reduced, but it has less influence on the ultimate localization precision. Therefore, as we can see in Figure4, with the decreasing of SNR, namely, the increasing of RSSI measurement error, there is almost no effect on localization precision.As one of the most important indexes for localization algorithms, localization coverage of the proposed algorithm is analyzed. The localization coverage is defined by(30)localizationcoverage=KlocalizableK.Here,Klocalizable refers to the number of the unknown nodes that are localizable. K is the total number of unknown nodes defined in (26).In three-dimensional space, an unknown node with no fewer than four connected anchor nodes of different plane is localizable. And an unknown node requires at least three nonlinear connected anchor nodes to realize localization in two-dimensional space. Figures5(a) and 5(b) show the effect of connected anchor nodes on localization coverage in three-dimensional space and two-dimensional space, respectively. The good performance of localization coverage with large number of connected anchor nodes can be clearly identified in Figure 5. Nevertheless, note that the localization coverage with short communication radius and small anchor ratio is unsatisfactory, especially for three-dimensional node localization. When the communication radius is 20 and the anchor ratio is 5%, the results in Figure 5(a) show that only about 30% of unknown nodes in three-dimensional space are localizable.Figure 5
The effect of connected anchor nodes on localization coverage in (a) three-dimensional and (b) two-dimensional space.
(a) (b)Since the proposed algorithm is robust against RSSI measurement error, the early positioned nodes can be upgraded to be new anchor nodes with some positional error. The remaining unknown nodes can be positioned with more anchor nodes in later localization process. Figure6 illustrates the effect of iterative processing on localization coverage. It is favorable to see that the localization coverage can be improved dramatically through multiple iterations. Even with the condition of fewer connected anchor nodes, such as when the communication radius is 20 and the anchor ratio is 5%, the localization coverage can reach almost 100% after four iterations in three-dimensional space, while only two iterations are needed to realize 100% localization coverage in two-dimensional space, which are presented in Figures 6(a) and 6(b), respectively.Figure 6
The effect of iterative processing on localization coverage in (a) three-dimensional and (b) two-dimensional space.
(a) (b)Finally, the performance of the proposed algorithm will be compared to existing competitors. Considering that the centroid coordinate and the RSSI between the unknown node and the centroid are calculated, we compare the algorithmic performance of the centroid localization algorithm [11], the RSSI algorithm [3], and the presented algorithm to show the advantages of the proposed algorithm. With the communication radius of R=35, Figures 7 and 8 depict the algorithmic performance of the three algorithms in three-dimensional space and two-dimensional space, respectively.Figure 7
The performance of the proposed algorithm and its competitors in three-dimensional space with (a) SNR = −10 dB, (b) SNR = 0 dB, and (c) SNR = 10 dB.
(a) (b) (c)Figure 8
The performance of the proposed algorithm and its competitors in two-dimensional space with (a) SNR = −10 dB, (b) SNR = 0 dB, and (c) SNR = 10 dB.
(a) (b) (c)With different SNR, a comprehensive comparison of the three algorithms is given. As one of the range-free measurements, there is no effect of SNR change on localization precision of the centroid localization algorithm. On the contrary, the performance of the RSSI algorithm, which is one of the range-based measurements, sharply drops with SNR decreasing. As can be seen, the RSSI algorithm has the best performance of all in condition of high SNR. However, in condition of low SNR such as SNR = −10 dB, it is even worse than the centroid localization algorithm.The proposed algorithm has similar performance to different SNR. The simulation results also proved that the novel method has robust characteristics. In addition, the presented algorithm achieves better performance than the RSSI algorithm at low SNR in Figures7(a) and 8(a) but is inferior to the RSSI algorithm at high SNR in Figures 7(c) and 8(c). Nevertheless, it is always superior to the centroid localization algorithm because the centroid coordinate is calculated multiple times in the proposed algorithm, each time producing more accurate estimates before the stopping criterion is satisfied.


## 4. Conclusion

An improved localization algorithm based on iterative centroid estimation is proposed in this paper. In this algorithm, the centroid of the space enclosed by connected anchor nodes is considered as a virtual anchor node. It can be proven that there is at least one connected anchor node whose distance from the unknown node must be farther than the centroid. Hence, the connected anchor node with the weakest RSSI will be replaced by the centroid. Good positioning results can be achieved by repeating the replacement procedure. The simulation results prove the effectiveness and robustness of the proposed algorithm for both three-dimensional and two-dimensional node localization.



---

*Source: 5456191-2018-10-08.xml*