# A Distributed Anchor Node Selection Algorithm Based on Error Analysis for Trilateration Localization

Authors: Yingsheng Fan; Xiaogang Qi; Baoguo Yu; Lifang Liu
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

This paper proposes a distributed anchor node selection algorithm based on error analysis for trilateration localization (EATL). The influence of distance measurement error on localization accuracy is discussed from two aspects: condition number of triangle formed by the three anchor nodes and the relative position between the unknown node and the three anchor nodes. Based on the error analysis, three principles for optimizing the selection of anchor nodes are given and then an algorithm for selecting anchor nodes on the ring is proposed.


---

## Body

## 1. Introduction

In a distributed sensor network, for most applications, such as target tracking, environmental monitoring [1], the geographical information of sensor nodes needs to be known. Estimation of node position is a fundamental requirement in distributed sensor networks. One possible solution is to install GPS receiver for each sensor node (or similar system, such as BeiDou Navigation Satellite System), but this scheme is limited by the characteristics of distributed sensor network itself. On the one hand, the cost of node with GPS system will be two orders of magnitude higher than that of ordinary node [2]. On the other hand, according to the different applications, sensor nodes are often deployed in the interior, city buildings, or even forest environment, and satellite signals are easily affected by many factors such as multipath interference and occlusion [3]. The localization accuracy is poor or even affecting its usability.Cooperative localization [4, 5] is a new idea to realize high accuracy positioning in GPS denied environments. The basic idea is to use the following information to assist node localization, such as the distance information obtained from the communication between sensor nodes, the relative velocity information via Doppler shift measurement in the dynamic network. In large-scale distributed networks, due to the limited communication capability, nodes only can interact with their neighbors. All nodes will form a connected multihop network. According to the different application scenarios, coordinates here can be standard coordinates, such as latitude and longitude, or relative coordinate system. On the one hand, arranging a large number of anchor nodes is expensive. On the other hand, in some applications such as battlefield environments, anchor nodes only can be deployed around the network. This does not guarantee that all unknown nodes are adjacent to anchor nodes and obtain enough localization information. Consider an application in a two-dimensional network as shown in Figure 1; anchor nodes are arranged around the network, and unknown nodes are arranged in the network. Initially, anchor nodes broadcast the coordinate information. Due to the limitation of the communication radius, only a few unknown nodes can obtain enough localization information to estimate their own coordinates. The unknown node which has completed its own location will be an anchor node to assist other unknown nodes to be located. Through this kind of information interaction between nodes, cooperative localization of the whole network will be completed.Figure 1
Cooperative localization.Localization techniques of the distributed sensor network can be divided into two categories: range-based localization algorithm and range-free localization algorithm. This paper only considers range-based localization algorithm. This technique includes three main categories: Trilateration-based algorithm [6], Maximum Likelihood-based algorithm [7], and Multidimensional Scaling (MDS)-based algorithm. In Trilateration-based algorithm, unknown nodes measure the distances to three neighbor anchor nodes and then use this information to estimate their locations. The specific mathematical model will be given in the next section. When there are more than three neighbor anchor nodes, the unknown node should choose three to estimate its location. Maximum Likelihood-based algorithm is different from Trilateration-based algorithm. When the unknown node has more than three neighbor anchor nodes, it will utilize the information of all anchor nodes to construct an overdetermined equation and find the least square solution. The MDS algorithm based on distance measurement is divided into two main categories. The first category is classical MDS [8, 9]. This algorithm provides relative coordinate to a seemingly nonconvex localization problem, using only singular value decomposition. Within the classical MDS framework, the complete Euclidean distance matrix is needed, but this matrix is often very difficult to be obtained. The second category is to construct a pressure function [10–12] and use SMACOF [13] algorithm to minimize the pressure function and get the relative coordinate estimate. SMACOF algorithm is an iterative solution which will lead to high computational complexity. Although Trilateration- based algorithm and Maximum Likelihood-based algorithm need a certain number of anchor nodes, their computational complexity is low and they are suitable for cooperative localization of large-scale distributed networks.The main distance measurement techniques of range-based localization algorithm are Received Signal Strength Indication (RSSI) [14], Time-of-Arrival (TOA) [15], and Ultrawideband (UWB) [16]. There is also a tradeoff between device cost and range accuracy. Using RSSI technique is cheap but the accuracy of measurement may be low, using TOA technique needs to guarantee time synchronization, and using UWB technique can achieve accuracies on the order of centimeters, but at the expense of high device and energy costs.It should be noted that even in idealized setups with no obstacles or other external factors, relatively small error from noisy sensor measurements can induce much larger errors in node position estimate [17]. In Trilateration-based algorithms, effect of range measurement error on localization accuracy is mainly related to the selection of anchor node. In [6], an anchor node selection scheme based on the minimum condition number is proposed to improve the localization accuracy. However, this scheme only considers the influence of the distribution of three anchor nodes on localization accuracy. Actually, the relative position between the unknown node and the three anchor nodes will also have a great impact on localization accuracy. In Trilateration-based algorithms, when the unknown node completes the estimation of its location, it will become an anchor node to assist other unknown nodes to be located. In this process, the iterative error will be produced. Accumulation of measurement error will increase rapidly if the anchor nodes are not selected properly. Therefore, the selection of anchor nodes will have an important influence on localization accuracy.The main contributions of this paper are as follows:(1) The influence of distance measurement error on localization accuracy is discussed from two aspects: condition number of triangle formed by the three anchor nodes and the relative position between the unknown node and the three anchor nodes.(2) Based on error analysis, an anchor nodes selection scheme (EATL) is proposed, which can effectively improve the localization accuracy.The rest of the paper is organized as follows. The mathematical model of Trilateration localization is provided in Section2 and error analysis is provide in Section 3. Based on the analysis in Section 3, an anchor nodes selection algorithm is given in Section 4. Simulation analysis is provided in Section 5, while Section 6 concludes the paper.


## 2. Mathematical Model of Trilateration Localization

We useP(x,y) to represent the unknown node as shown in Figure 2; three anchor nodes within the communication radius of P are a1(x1,y1), a2(x2,y2), and a3(x3,y3), respectively.Figure 2
The ideal model of Trilateration.The exact Euclidean distances without any noise betweenP and a1, P and a2, P and a3 are d1, d2, and d3, respectively. The coordinates of P can be obtained by solving (1).(1)x-x12+y-y12=d12x-x22+y-y22=d22x-x32+y-y32=d32We get (2) by using the third formula minus the first formula and the third formula minus the second formula in (1).(2)2x3-x1x+2y3-y1y=…d12-d32+x32-x12+y32-y122x3-x2x+2y3-y2y=…d12-d32+x32-x12+y32-y12In practice, the measured distances are modeled as a noisy version of the actual node distances. For example, the actual distance between anchor nodea2 and P is d2, the measured distance is d2′, and Δd2 denotes the distance measurement error. In this case, the three circles intersect to form an area D as the shaded area shown in Figure 3. In Figure 4, the three circles intersect with one another. From elementary geometry, we know that the lines ab, cd, and ef will intersect at one point. When we solve (2), we get the coordinates of the intersection point actually.Figure 3
Distance measurement error of Trilateration.Figure 4
The actual model of Trilateration.


## 3. Error Analysis

When the distance measurement errorΔd exists, the coordinates of the unknown node P obtained by solving (2) will also be inaccurate. Even if Δd is small, the coordinates of P obtained by inappropriate anchor node combination may also have great errors. See the example in Table 1; (x,y) refers to the coordinates of the three anchor nodes, the third column is the actual distance between the unknown node and the anchor node, and the fourth column is the measurement distance with errors.Table 1
An example of ill-conditioned equation.
(x, y) Actual Distance Measurement Distance Anchor 1 (815.83,10.60) 149.220 149.215 Anchor 2 (836.01,13.08) 151.560 151.500 Anchor 3 (869.17,17.28) 160.724 160.761Based on actual distances, we can get the exact coordinates ofP as (790, 157) by solving (2). But from measurement distances, the solution is (760, 402). It can be seen from Table 1 that the differences between actual distances and measurement distances are negligible, but the differences of solutions, especially ordinates, are several hundred meters. Therefore, it is very important to study which factors will affect the solution of (2). To simplify the analysis, we rewrite (2) as follows:(3)AX=bwhere A is a coefficient matrix, X denotes the coordinates of P, and b is a column vector. We have(4)A=2x3-x12y3-y12x3-x22y3-y2,X=xyandb=d12-d32+x32-x12+y32-y12d12-d32+x32-x12+y32-y12.A is completely described by the coordinates of the three anchor nodes and can also be understood as the distribution of the three anchor nodes in the two-dimensional space. The elements in b are completely determined by the coordinates of the three anchor nodes and the distances from the unknown node to the anchor nodes. That is, the relative position of the unknown node and the three anchor nodes will have a decisive influence on b. In this paper, the error analysis will be made from the distribution of three anchor nodes and the relative positions of the unknown nodes and the three anchor nodes. In Section 3.1.1 we discuss the situation when there is only distance measurement error; that is, we assume that the coordinates of the three anchor nodes a1, a2, and a3 are accurate. In Section 3.1.2 we will discuss the situation when both the anchor nodes position error and the distance measurement error exist. We assume that the distance measurement error Δd is a random variable which obeys uniform distribution, Δd~U(-ε,ε).


### 3.1. The Influence of the Distribution of Anchor Nodes on Localization Accuracy

#### 3.1.1. The Influence of Distance Measurement Error

In this paper, we always assume that a matrix norm· is 2-norm; that is to say, ·2=λmax(ATA). According to the property of matrix norm, we have AB≤A·B.When the distance measurement error exists, the error is mainly reflected on the column vectorb in (3); b can be rewritten as follows:(5)b′=d1+Δd12-d3+Δd32+x32-x12+y32-y12d1+Δd22-d3+Δd32+x32-x12+y32-y12,and, thus, using b′, it follows that(6)AX+ΔX=b+Δbwhere ΔX is the error of solution and(7)Δb=b′-b=2Δd1·d1-2Δd3·d3+Δd12-Δd322Δd2·d2-2Δd3·d3+Δd22-Δd32.Here we assume that the matrixA is nonsingular and we can obtain the following.(8)ΔX=A-1ΔbFrom (3) and (8), we can get 1/X≤A/b and ΔX≤A-1∗Δb. Then(9)ΔXX≤A-1∗AΔbbwhereΔX/X denotes relative error of solution, Δb/b denotes relative error of column vector b, and A-1∗A denotes the condition number of coefficient matrix A, where (10)condA=A-1∗AA - 1 ∗ A and Δb/b will determine the upper bound of ΔX/X.


#### 3.1.2. The Influence of Distance Measurement Error and Anchor Nodes Position Error

When both the anchor nodes position error and the distance measurement error exist, the error is mainly reflected in the coefficient matrixA and the column vector b. Equation (6) should be rewritten as follows.(11)A+ΔAX+ΔX=b+Δb-HereΔb- is expressed as follows.(12)Δb-=2Δd1·d1-2Δd3·d3+Δd12-Δd32+2Δx3·x3-2Δx1·x1+Δx32-Δx12+2Δy3·y3-2Δy1·y1+Δy32-Δy122Δd2·d2-2Δd3·d3+Δd22-Δd32+2Δx3·x3-2Δx2·x2+Δx32-Δx22+2Δy3·y3-2Δy2·y2+Δy32-Δy22We assume thatΔA is small and can satisfy A-1·ΔA<1. If ΔA is very large, the coordinates error of the anchor node itself is very large. Substituting (3) in (11) yields(13)ΔX=A-1Δb--ΔA·X-ΔA·ΔX.Computing the norm we have(14)ΔX≤A-1Δb-+ΔA·X+ΔA·ΔX.And then(15)1-A-1·ΔAΔX≤A-1Δb-+ΔA·X.So we have the following.(16)1-A-1·ΔAΔXX≤A-1A·Δb-b+ΔAFrom inequality (16), we obtain the following.(17)ΔXX≤A·A-11-A·A-1ΔA/AΔb-b+ΔAAIn (17), Δb-/b denotes relative error of column vector b and ΔA/A denotes relative error of coefficient matrix A. When ΔA is small, inequality (17) is similar to (9), and the upper bound of ΔX/X is determined by the condition number of coefficient matrix A and Δb-/b.


#### 3.1.3. The Influence ofcond(A) on Localization Accuracy

From (9) and (17), the upper bound of ΔX/X is dependent on A-1∗A. In (1), we use the third formula minus the first and the second formula, respectively, and then get the coefficient matrix (18)Aa1=2x1-x22y1-y22x1-x32y1-y3.Similarly, we can also use the first formula minus the second and the third formula, respectively. Then we will get (19)Aa2=2x2-x12y2-y12x2-x32y2-y3andAa3=2x3-x12y3-y12x3-x22y3-y2.c o n d ( A a 1 ) + c o n d ( A a 2 ) + c o n d ( A a 3 ) indicates the collinear degree of three anchor nodes. From the theory of ill-conditioned matrix, the greater the condition number of A is, the more sensitive the linear equation with coefficient matrix A is to ΔA and Δb. When three anchor nodes constitute an equilateral triangle, the sum of the condition numbers will obtain a minimal value 5.1963.But in most cases, it is difficult to find three anchor nodes that just form an equilateral triangle. In order to illustrate the influence of the condition number on localization accuracy, we do the experiment as follows. As shown in Figure5, 600 unknown nodes are randomly deployed in a two-dimensional area of size 100∗100. The coordinates of anchor nodes a1 and a2 are (25,25) and (75,25), respectively. The x-coordinate of a3 is 50, and the y-coordinate starts from 27, sampling every 0.5 meters, sampling 100 times, and observing the influence of the condition number of triangles formed by the three anchor nodes on localization accuracy. We assume that each unknown node can communicate directly with any anchor node and distance measurement error Δd obeys the uniform distribution U(-2,2).Figure 5
The distribution of three anchor nodes.The MAE of the location estimates is given by(20)Δi=xi-x^i2+yi-y^i2,Δ¯=∑i=1NΔiN,whereN is the number of unknown nodes, (xi,yi) are the exact coordinates of unknown node i, and (x^i,y^i) are the estimation coordinates. Δi denotes the distance between the estimated position and the real position of unknown node i. Δ¯ denotes MAE.To give a dimensionless form, we defineΔi′ as follows:(21)Δi′=Δi1/3∑13Δdij,Δ′¯=∑i=1NΔi′N,where Δdij denotes the distance measurement error between unknown node i and anchor node j. The relationship between Δ′¯ and the condition number is shown in Figure 6.Figure 6
Δ ′ ¯ for different condition number.As shown in Figure6, Δ′¯ has an increased trend with the increase of condition number, but it is not a completely monotonically increasing relationship. This shows that Δ′¯ is not completely determined by condition number of the triangle formed by the anchor nodes. When the condition number is less than 18, Δ′¯ is less than 3.6. In the process of computer simulation, we find that the condition number of the triangle formed by the three anchor nodes has the following function relationship with the degree of inner angles (α1,α2,α3) of the triangle. (22)condAa1+condAa2+condAa3=cot⁡α12+cot⁡α22+cot⁡α32From this equation, when the condition number is 18, the minimum interior angle is 13°.When the shape of a triangle is determined, its condition number is also determined. As shown in Figure7, the condition number of isosceles right-angle triangle formed by a1, a2, and a3 is 6.2361 and the condition number of isosceles right-angle triangle formed by a1′, a2′, and a3′ is also 6.2361.Figure 7
The condition numbers of two isosceles right-angle triangles.Although condition numbers of the two triangles are the same, their influences on errorΔX are different.From(23)Aa1=2x1-x22y1-y22x1-x32y1-y3,we obtain the following. (24)Aa1-1=12x3-x1y3-y1-2x3-x2y3-y2y3-y2-y3-y1-x3-x2x3-x1Substitutinga1(0,0), a2(2,0), and a3(1,1) in (24) yields Aa1-1=0.2500-0.25000.25000.2500, but when we use a1′(0,0), a2′(20,0), and a3′(10,10), it follows that (Aa1′)-1=0.0250-0.02500.02500.0250=1/10Aa1-1. In the triangle formed by three anchor nodes, the larger the shortest edge, the smaller the elements in A-1.Using the data in Table1, we will get A=106.68613.351866.31828.3877 and cond(A)=1709.6.The large condition number indicates that the matrix is ill-conditioned and very sensitive to disturbances. Further we can obtainA-1=0.8946-1.4241-7.073311.3787. The large elements in A-1 will lead to a large error of location estimate.


### 3.2. Influence of the Relative Positions of the Unknown Nodes and Anchor Nodes on Localization Accuracy

In this section, we only discuss the situation in Section3.1.1; that is, the coordinates of the anchor nodes are precise, and only distance measurement error exists. According to the expression of Δb- in Section 3.1.2, when ΔA is small, the elements in Δb- are mainly affected by the relative position of unknown node and the three anchor nodes. This is similar to the case of Δb.When estimating the coordinates ofp, there are two groups of anchor nodes: a1, a2, a3 and a1′, a2′, a3′ as shown in Figure 8. The triangle a1′a2′a3′ is the expansion of the triangle a1a2a3. We assume that line a1′a2′ is N times as long as line a1a2.Figure 8
Two isosceles right-angle triangles.In the case of fixed distance measurement errorΔd, for triangle a1a2a3, we have(25)Δb=2Δd1·d1-2Δd3·d3+Δd12-Δd322Δd2·d2-2Δd3·d3+Δd22-Δd32andΔX=A-1·2Δd1·d1-2Δd3·d3+Δd12-Δd322Δd2·d2-2Δd3·d3+Δd22-Δd32.For trianglea1′a2′a3′, we have(26)Δb′=N·2Δd1·d1-2Δd3·d3+Δd12-Δd32N·2Δd2·d2-2Δd3·d3+Δd22-Δd32andΔX′=A-1·2Δd1·d1-2Δd3·d3+1NΔd12-Δd322Δd2·d2-2Δd3·d3+1NΔd22-Δd32.AsΔd~U(-ε,ε), the expectation and variance of Δd are E(Δd)=0 and D(Δd)=ε2/3. The expectation of the elements in ΔX and ΔX′ is 0. To compare the variance of the elements in ΔX and ΔX′, we just need to compare D(Δd12-Δd32) and D(1/N(Δd12-Δd32)). As D(Δd12-Δd32)=8/45ε4 and D(1/N(Δd12-Δd32))=8/(45·N2)ε4, the variance of the elements in ΔX′ is smaller than ΔX; we select triangle a1′a2′a3′ to estimate the coordinates of p.In fact, when the positions of the three anchor nodes are determined (that is, matrixA-1 is determined), the elements in Δb are mainly determined by the relative positions of the unknown nodes and the three anchor nodes. In geometry, the Fermat point of a triangle, also called the Torricelli point or Fermat–Torricelli point, is a point such that the total distance from the three vertices of the triangle to the point is the minimum possible. d1, d2, and d3 must be satisfied: d1+d2+d3≥dmin. dmin is the minimum total distance.Since the value ofΔd12-Δd32 is small, we assume (27)Δba3=2Δd1·d1-2Δd3·d32Δd2·d2-2Δd3·d3,and in the same way we have (28)Δba1=2Δd2·d2-2Δd1·d12Δd3·d3-2Δd1·d1andΔba2=2Δd1·d1-2Δd2·d22Δd3·d3-2Δd2·d2.From Δba3 we have Δba3/222=(Δd1·d1-Δd3·d3)2+(Δd2·d2-Δd3·d3)2. In the same way we have Δba1/222 and Δba2/222.Then we obtain the following.(29)EΔba1222+EΔba2222+EΔba3222=43ε2d12+d22+d32To get the minimum value of (29), the problem can be transformed into the following optimization problem.(30)mind12+d22+d32s.t.d1+d2+d3-dmin≥0,d1≥0,d2≥0,d3≥0The objective function of (30) is a convex function, and the inequality constraints are all linear functions, so the K-T point of (30) must be the global optimal solution. The K-T point can be obtained as d1=d2=d3=dmin/3.According to the above analysis, the distances between the three anchor nodes and the unknown node should be as similar as possible.


## 3.1. The Influence of the Distribution of Anchor Nodes on Localization Accuracy

### 3.1.1. The Influence of Distance Measurement Error

In this paper, we always assume that a matrix norm· is 2-norm; that is to say, ·2=λmax(ATA). According to the property of matrix norm, we have AB≤A·B.When the distance measurement error exists, the error is mainly reflected on the column vectorb in (3); b can be rewritten as follows:(5)b′=d1+Δd12-d3+Δd32+x32-x12+y32-y12d1+Δd22-d3+Δd32+x32-x12+y32-y12,and, thus, using b′, it follows that(6)AX+ΔX=b+Δbwhere ΔX is the error of solution and(7)Δb=b′-b=2Δd1·d1-2Δd3·d3+Δd12-Δd322Δd2·d2-2Δd3·d3+Δd22-Δd32.Here we assume that the matrixA is nonsingular and we can obtain the following.(8)ΔX=A-1ΔbFrom (3) and (8), we can get 1/X≤A/b and ΔX≤A-1∗Δb. Then(9)ΔXX≤A-1∗AΔbbwhereΔX/X denotes relative error of solution, Δb/b denotes relative error of column vector b, and A-1∗A denotes the condition number of coefficient matrix A, where (10)condA=A-1∗AA - 1 ∗ A and Δb/b will determine the upper bound of ΔX/X.


### 3.1.2. The Influence of Distance Measurement Error and Anchor Nodes Position Error

When both the anchor nodes position error and the distance measurement error exist, the error is mainly reflected in the coefficient matrixA and the column vector b. Equation (6) should be rewritten as follows.(11)A+ΔAX+ΔX=b+Δb-HereΔb- is expressed as follows.(12)Δb-=2Δd1·d1-2Δd3·d3+Δd12-Δd32+2Δx3·x3-2Δx1·x1+Δx32-Δx12+2Δy3·y3-2Δy1·y1+Δy32-Δy122Δd2·d2-2Δd3·d3+Δd22-Δd32+2Δx3·x3-2Δx2·x2+Δx32-Δx22+2Δy3·y3-2Δy2·y2+Δy32-Δy22We assume thatΔA is small and can satisfy A-1·ΔA<1. If ΔA is very large, the coordinates error of the anchor node itself is very large. Substituting (3) in (11) yields(13)ΔX=A-1Δb--ΔA·X-ΔA·ΔX.Computing the norm we have(14)ΔX≤A-1Δb-+ΔA·X+ΔA·ΔX.And then(15)1-A-1·ΔAΔX≤A-1Δb-+ΔA·X.So we have the following.(16)1-A-1·ΔAΔXX≤A-1A·Δb-b+ΔAFrom inequality (16), we obtain the following.(17)ΔXX≤A·A-11-A·A-1ΔA/AΔb-b+ΔAAIn (17), Δb-/b denotes relative error of column vector b and ΔA/A denotes relative error of coefficient matrix A. When ΔA is small, inequality (17) is similar to (9), and the upper bound of ΔX/X is determined by the condition number of coefficient matrix A and Δb-/b.


### 3.1.3. The Influence ofcond(A) on Localization Accuracy

From (9) and (17), the upper bound of ΔX/X is dependent on A-1∗A. In (1), we use the third formula minus the first and the second formula, respectively, and then get the coefficient matrix (18)Aa1=2x1-x22y1-y22x1-x32y1-y3.Similarly, we can also use the first formula minus the second and the third formula, respectively. Then we will get (19)Aa2=2x2-x12y2-y12x2-x32y2-y3andAa3=2x3-x12y3-y12x3-x22y3-y2.c o n d ( A a 1 ) + c o n d ( A a 2 ) + c o n d ( A a 3 ) indicates the collinear degree of three anchor nodes. From the theory of ill-conditioned matrix, the greater the condition number of A is, the more sensitive the linear equation with coefficient matrix A is to ΔA and Δb. When three anchor nodes constitute an equilateral triangle, the sum of the condition numbers will obtain a minimal value 5.1963.But in most cases, it is difficult to find three anchor nodes that just form an equilateral triangle. In order to illustrate the influence of the condition number on localization accuracy, we do the experiment as follows. As shown in Figure5, 600 unknown nodes are randomly deployed in a two-dimensional area of size 100∗100. The coordinates of anchor nodes a1 and a2 are (25,25) and (75,25), respectively. The x-coordinate of a3 is 50, and the y-coordinate starts from 27, sampling every 0.5 meters, sampling 100 times, and observing the influence of the condition number of triangles formed by the three anchor nodes on localization accuracy. We assume that each unknown node can communicate directly with any anchor node and distance measurement error Δd obeys the uniform distribution U(-2,2).Figure 5
The distribution of three anchor nodes.The MAE of the location estimates is given by(20)Δi=xi-x^i2+yi-y^i2,Δ¯=∑i=1NΔiN,whereN is the number of unknown nodes, (xi,yi) are the exact coordinates of unknown node i, and (x^i,y^i) are the estimation coordinates. Δi denotes the distance between the estimated position and the real position of unknown node i. Δ¯ denotes MAE.To give a dimensionless form, we defineΔi′ as follows:(21)Δi′=Δi1/3∑13Δdij,Δ′¯=∑i=1NΔi′N,where Δdij denotes the distance measurement error between unknown node i and anchor node j. The relationship between Δ′¯ and the condition number is shown in Figure 6.Figure 6
Δ ′ ¯ for different condition number.As shown in Figure6, Δ′¯ has an increased trend with the increase of condition number, but it is not a completely monotonically increasing relationship. This shows that Δ′¯ is not completely determined by condition number of the triangle formed by the anchor nodes. When the condition number is less than 18, Δ′¯ is less than 3.6. In the process of computer simulation, we find that the condition number of the triangle formed by the three anchor nodes has the following function relationship with the degree of inner angles (α1,α2,α3) of the triangle. (22)condAa1+condAa2+condAa3=cot⁡α12+cot⁡α22+cot⁡α32From this equation, when the condition number is 18, the minimum interior angle is 13°.When the shape of a triangle is determined, its condition number is also determined. As shown in Figure7, the condition number of isosceles right-angle triangle formed by a1, a2, and a3 is 6.2361 and the condition number of isosceles right-angle triangle formed by a1′, a2′, and a3′ is also 6.2361.Figure 7
The condition numbers of two isosceles right-angle triangles.Although condition numbers of the two triangles are the same, their influences on errorΔX are different.From(23)Aa1=2x1-x22y1-y22x1-x32y1-y3,we obtain the following. (24)Aa1-1=12x3-x1y3-y1-2x3-x2y3-y2y3-y2-y3-y1-x3-x2x3-x1Substitutinga1(0,0), a2(2,0), and a3(1,1) in (24) yields Aa1-1=0.2500-0.25000.25000.2500, but when we use a1′(0,0), a2′(20,0), and a3′(10,10), it follows that (Aa1′)-1=0.0250-0.02500.02500.0250=1/10Aa1-1. In the triangle formed by three anchor nodes, the larger the shortest edge, the smaller the elements in A-1.Using the data in Table1, we will get A=106.68613.351866.31828.3877 and cond(A)=1709.6.The large condition number indicates that the matrix is ill-conditioned and very sensitive to disturbances. Further we can obtainA-1=0.8946-1.4241-7.073311.3787. The large elements in A-1 will lead to a large error of location estimate.


## 3.1.1. The Influence of Distance Measurement Error

In this paper, we always assume that a matrix norm· is 2-norm; that is to say, ·2=λmax(ATA). According to the property of matrix norm, we have AB≤A·B.When the distance measurement error exists, the error is mainly reflected on the column vectorb in (3); b can be rewritten as follows:(5)b′=d1+Δd12-d3+Δd32+x32-x12+y32-y12d1+Δd22-d3+Δd32+x32-x12+y32-y12,and, thus, using b′, it follows that(6)AX+ΔX=b+Δbwhere ΔX is the error of solution and(7)Δb=b′-b=2Δd1·d1-2Δd3·d3+Δd12-Δd322Δd2·d2-2Δd3·d3+Δd22-Δd32.Here we assume that the matrixA is nonsingular and we can obtain the following.(8)ΔX=A-1ΔbFrom (3) and (8), we can get 1/X≤A/b and ΔX≤A-1∗Δb. Then(9)ΔXX≤A-1∗AΔbbwhereΔX/X denotes relative error of solution, Δb/b denotes relative error of column vector b, and A-1∗A denotes the condition number of coefficient matrix A, where (10)condA=A-1∗AA - 1 ∗ A and Δb/b will determine the upper bound of ΔX/X.


## 3.1.2. The Influence of Distance Measurement Error and Anchor Nodes Position Error

When both the anchor nodes position error and the distance measurement error exist, the error is mainly reflected in the coefficient matrixA and the column vector b. Equation (6) should be rewritten as follows.(11)A+ΔAX+ΔX=b+Δb-HereΔb- is expressed as follows.(12)Δb-=2Δd1·d1-2Δd3·d3+Δd12-Δd32+2Δx3·x3-2Δx1·x1+Δx32-Δx12+2Δy3·y3-2Δy1·y1+Δy32-Δy122Δd2·d2-2Δd3·d3+Δd22-Δd32+2Δx3·x3-2Δx2·x2+Δx32-Δx22+2Δy3·y3-2Δy2·y2+Δy32-Δy22We assume thatΔA is small and can satisfy A-1·ΔA<1. If ΔA is very large, the coordinates error of the anchor node itself is very large. Substituting (3) in (11) yields(13)ΔX=A-1Δb--ΔA·X-ΔA·ΔX.Computing the norm we have(14)ΔX≤A-1Δb-+ΔA·X+ΔA·ΔX.And then(15)1-A-1·ΔAΔX≤A-1Δb-+ΔA·X.So we have the following.(16)1-A-1·ΔAΔXX≤A-1A·Δb-b+ΔAFrom inequality (16), we obtain the following.(17)ΔXX≤A·A-11-A·A-1ΔA/AΔb-b+ΔAAIn (17), Δb-/b denotes relative error of column vector b and ΔA/A denotes relative error of coefficient matrix A. When ΔA is small, inequality (17) is similar to (9), and the upper bound of ΔX/X is determined by the condition number of coefficient matrix A and Δb-/b.


## 3.1.3. The Influence ofcond(A) on Localization Accuracy

From (9) and (17), the upper bound of ΔX/X is dependent on A-1∗A. In (1), we use the third formula minus the first and the second formula, respectively, and then get the coefficient matrix (18)Aa1=2x1-x22y1-y22x1-x32y1-y3.Similarly, we can also use the first formula minus the second and the third formula, respectively. Then we will get (19)Aa2=2x2-x12y2-y12x2-x32y2-y3andAa3=2x3-x12y3-y12x3-x22y3-y2.c o n d ( A a 1 ) + c o n d ( A a 2 ) + c o n d ( A a 3 ) indicates the collinear degree of three anchor nodes. From the theory of ill-conditioned matrix, the greater the condition number of A is, the more sensitive the linear equation with coefficient matrix A is to ΔA and Δb. When three anchor nodes constitute an equilateral triangle, the sum of the condition numbers will obtain a minimal value 5.1963.But in most cases, it is difficult to find three anchor nodes that just form an equilateral triangle. In order to illustrate the influence of the condition number on localization accuracy, we do the experiment as follows. As shown in Figure5, 600 unknown nodes are randomly deployed in a two-dimensional area of size 100∗100. The coordinates of anchor nodes a1 and a2 are (25,25) and (75,25), respectively. The x-coordinate of a3 is 50, and the y-coordinate starts from 27, sampling every 0.5 meters, sampling 100 times, and observing the influence of the condition number of triangles formed by the three anchor nodes on localization accuracy. We assume that each unknown node can communicate directly with any anchor node and distance measurement error Δd obeys the uniform distribution U(-2,2).Figure 5
The distribution of three anchor nodes.The MAE of the location estimates is given by(20)Δi=xi-x^i2+yi-y^i2,Δ¯=∑i=1NΔiN,whereN is the number of unknown nodes, (xi,yi) are the exact coordinates of unknown node i, and (x^i,y^i) are the estimation coordinates. Δi denotes the distance between the estimated position and the real position of unknown node i. Δ¯ denotes MAE.To give a dimensionless form, we defineΔi′ as follows:(21)Δi′=Δi1/3∑13Δdij,Δ′¯=∑i=1NΔi′N,where Δdij denotes the distance measurement error between unknown node i and anchor node j. The relationship between Δ′¯ and the condition number is shown in Figure 6.Figure 6
Δ ′ ¯ for different condition number.As shown in Figure6, Δ′¯ has an increased trend with the increase of condition number, but it is not a completely monotonically increasing relationship. This shows that Δ′¯ is not completely determined by condition number of the triangle formed by the anchor nodes. When the condition number is less than 18, Δ′¯ is less than 3.6. In the process of computer simulation, we find that the condition number of the triangle formed by the three anchor nodes has the following function relationship with the degree of inner angles (α1,α2,α3) of the triangle. (22)condAa1+condAa2+condAa3=cot⁡α12+cot⁡α22+cot⁡α32From this equation, when the condition number is 18, the minimum interior angle is 13°.When the shape of a triangle is determined, its condition number is also determined. As shown in Figure7, the condition number of isosceles right-angle triangle formed by a1, a2, and a3 is 6.2361 and the condition number of isosceles right-angle triangle formed by a1′, a2′, and a3′ is also 6.2361.Figure 7
The condition numbers of two isosceles right-angle triangles.Although condition numbers of the two triangles are the same, their influences on errorΔX are different.From(23)Aa1=2x1-x22y1-y22x1-x32y1-y3,we obtain the following. (24)Aa1-1=12x3-x1y3-y1-2x3-x2y3-y2y3-y2-y3-y1-x3-x2x3-x1Substitutinga1(0,0), a2(2,0), and a3(1,1) in (24) yields Aa1-1=0.2500-0.25000.25000.2500, but when we use a1′(0,0), a2′(20,0), and a3′(10,10), it follows that (Aa1′)-1=0.0250-0.02500.02500.0250=1/10Aa1-1. In the triangle formed by three anchor nodes, the larger the shortest edge, the smaller the elements in A-1.Using the data in Table1, we will get A=106.68613.351866.31828.3877 and cond(A)=1709.6.The large condition number indicates that the matrix is ill-conditioned and very sensitive to disturbances. Further we can obtainA-1=0.8946-1.4241-7.073311.3787. The large elements in A-1 will lead to a large error of location estimate.


## 3.2. Influence of the Relative Positions of the Unknown Nodes and Anchor Nodes on Localization Accuracy

In this section, we only discuss the situation in Section3.1.1; that is, the coordinates of the anchor nodes are precise, and only distance measurement error exists. According to the expression of Δb- in Section 3.1.2, when ΔA is small, the elements in Δb- are mainly affected by the relative position of unknown node and the three anchor nodes. This is similar to the case of Δb.When estimating the coordinates ofp, there are two groups of anchor nodes: a1, a2, a3 and a1′, a2′, a3′ as shown in Figure 8. The triangle a1′a2′a3′ is the expansion of the triangle a1a2a3. We assume that line a1′a2′ is N times as long as line a1a2.Figure 8
Two isosceles right-angle triangles.In the case of fixed distance measurement errorΔd, for triangle a1a2a3, we have(25)Δb=2Δd1·d1-2Δd3·d3+Δd12-Δd322Δd2·d2-2Δd3·d3+Δd22-Δd32andΔX=A-1·2Δd1·d1-2Δd3·d3+Δd12-Δd322Δd2·d2-2Δd3·d3+Δd22-Δd32.For trianglea1′a2′a3′, we have(26)Δb′=N·2Δd1·d1-2Δd3·d3+Δd12-Δd32N·2Δd2·d2-2Δd3·d3+Δd22-Δd32andΔX′=A-1·2Δd1·d1-2Δd3·d3+1NΔd12-Δd322Δd2·d2-2Δd3·d3+1NΔd22-Δd32.AsΔd~U(-ε,ε), the expectation and variance of Δd are E(Δd)=0 and D(Δd)=ε2/3. The expectation of the elements in ΔX and ΔX′ is 0. To compare the variance of the elements in ΔX and ΔX′, we just need to compare D(Δd12-Δd32) and D(1/N(Δd12-Δd32)). As D(Δd12-Δd32)=8/45ε4 and D(1/N(Δd12-Δd32))=8/(45·N2)ε4, the variance of the elements in ΔX′ is smaller than ΔX; we select triangle a1′a2′a3′ to estimate the coordinates of p.In fact, when the positions of the three anchor nodes are determined (that is, matrixA-1 is determined), the elements in Δb are mainly determined by the relative positions of the unknown nodes and the three anchor nodes. In geometry, the Fermat point of a triangle, also called the Torricelli point or Fermat–Torricelli point, is a point such that the total distance from the three vertices of the triangle to the point is the minimum possible. d1, d2, and d3 must be satisfied: d1+d2+d3≥dmin. dmin is the minimum total distance.Since the value ofΔd12-Δd32 is small, we assume (27)Δba3=2Δd1·d1-2Δd3·d32Δd2·d2-2Δd3·d3,and in the same way we have (28)Δba1=2Δd2·d2-2Δd1·d12Δd3·d3-2Δd1·d1andΔba2=2Δd1·d1-2Δd2·d22Δd3·d3-2Δd2·d2.From Δba3 we have Δba3/222=(Δd1·d1-Δd3·d3)2+(Δd2·d2-Δd3·d3)2. In the same way we have Δba1/222 and Δba2/222.Then we obtain the following.(29)EΔba1222+EΔba2222+EΔba3222=43ε2d12+d22+d32To get the minimum value of (29), the problem can be transformed into the following optimization problem.(30)mind12+d22+d32s.t.d1+d2+d3-dmin≥0,d1≥0,d2≥0,d3≥0The objective function of (30) is a convex function, and the inequality constraints are all linear functions, so the K-T point of (30) must be the global optimal solution. The K-T point can be obtained as d1=d2=d3=dmin/3.According to the above analysis, the distances between the three anchor nodes and the unknown node should be as similar as possible.


## 4. Anchor Node Selection Algorithm Based on Error Analysis

### 4.1. Design Principle

The algorithm presented in this paper (EATL) abides by the following three principles:(1) The minimum internal angle of the triangle formed by the three anchor nodes should be larger than 13°.(2) The shortest edge of the triangle formed by the three anchor nodes should be as long as possible.(3) The distances between the three anchor nodes and the unknown node should be as similar as possible.Based on the above principles, we can select the anchor nodes on the ring centered on the unknown node. As shown in Figure9, p is the unknown node, nodes marked in red are anchor nodes, R is communication radius, and r is the inner radius of the ring.Figure 9
Selection of anchor nodes.We only select anchor nodes on the ring shown in Figure9. On the one hand, it reduces the complexity of the algorithm. In Trilateration algorithms, if unknown node selects the optimal combination among all neighbor anchor nodes, CN3 calculations will be performed, where N is the average number of neighbor anchor nodes. If the unknown node only selects anchor nodes on the ring, then N will be reduced to N′=N·R2-r2/R2. On the other hand, it ensures that the distances between the unknown node and the three anchor nodes are as similar as possible, which also satisfies principle (3).The six anchor nodes marked with black circle are available forp in Figure 9. Thus, 6 anchor nodes will have C63=20 combinations. After narrowing down the selection range of anchor nodes, we will select 3 among these 6 anchor nodes according to principle (1) and principle (2).For principle (1), the minimum internal angle of the triangle formed by the three anchor nodes should be larger than 13°. This principle is to reduce the collinearity of the three anchor nodes. In order to guarantee principle (2), we set the shortest side length thresholdthreshold_a, as shown in Table 2. Among all combinations satisfying the threshold, we select the maximum dmin(l), as shown in Table 2.Table 2
Explanation of parameters and variables.
Notation Description n o d e 1 ( i ) Unknown nodei R Communication radius r ring The ring shown in Figure9 n o d e 1 ( i ) . n e i g h b o r Neighbor anchor nodes set of unknown nodei on r ring, recording distance and location information of anchor nodes N ( i ) The number of neighbor anchor nodes of unknown nodei n o d e 1 ( i ) . f l a g 1 Localization flag of unknown nodei. The initial value is 0, update to 1 after localization n o d e 1 ( i ) . f l a g 2 Record the time when the unknown nodei is located θ m i n ( l ) Minimum internal angle of thelth combination of anchor node, l=1⋯CN(i)3 d m i n ( l ) The shortest edge of thelth combination of anchor node, l=1⋯CN(i)3 t h r e s h o l d _ a The shortest edge threshold t Waiting time thresholdIt should be noted that the inner radiusesr and threshold_a are given in Section 5 through simulation experiments, where r=0.6R, threshold_a=0.8R.


### 4.2. Symbol Description

The main parameters and variables used in the algorithm are shown in Table2.


### 4.3. Algorithm Procedure

In the beginning, initial anchor nodes broadcast their location information, and unknown nodes collect the information of neighbor anchor nodes and measure the distance.The unknown node starts executing the anchor nodes selection algorithm. The algorithm flowchart is shown in Figure10. After completing localization procedure, the unknown node updates node1(i).flag1=1 and becomes an anchor node. Then, it will broadcast its own location information. If the unknown node fails to complete the localization procedure, for example, no anchor node information is collected, or the anchor node information does not satisfy requirement of the flowchart, then it will enter the waiting state and wait for receiving enough information to complete the localization procedure.Figure 10
Algorithm flowchart.In a relatively sparse network, some unknown nodes may wait for a long time to find the anchor node information which can satisfy the requirement of the flowchart. Therefore, according to different applications, a waiting time thresholdt may be set. When reaching the waiting time threshold and the localization procedure is still not completed, the conditions in the flowchart can be properly relaxed. For example, the value of r can be reduced. Of course this may reduce localization accuracy.


## 4.1. Design Principle

The algorithm presented in this paper (EATL) abides by the following three principles:(1) The minimum internal angle of the triangle formed by the three anchor nodes should be larger than 13°.(2) The shortest edge of the triangle formed by the three anchor nodes should be as long as possible.(3) The distances between the three anchor nodes and the unknown node should be as similar as possible.Based on the above principles, we can select the anchor nodes on the ring centered on the unknown node. As shown in Figure9, p is the unknown node, nodes marked in red are anchor nodes, R is communication radius, and r is the inner radius of the ring.Figure 9
Selection of anchor nodes.We only select anchor nodes on the ring shown in Figure9. On the one hand, it reduces the complexity of the algorithm. In Trilateration algorithms, if unknown node selects the optimal combination among all neighbor anchor nodes, CN3 calculations will be performed, where N is the average number of neighbor anchor nodes. If the unknown node only selects anchor nodes on the ring, then N will be reduced to N′=N·R2-r2/R2. On the other hand, it ensures that the distances between the unknown node and the three anchor nodes are as similar as possible, which also satisfies principle (3).The six anchor nodes marked with black circle are available forp in Figure 9. Thus, 6 anchor nodes will have C63=20 combinations. After narrowing down the selection range of anchor nodes, we will select 3 among these 6 anchor nodes according to principle (1) and principle (2).For principle (1), the minimum internal angle of the triangle formed by the three anchor nodes should be larger than 13°. This principle is to reduce the collinearity of the three anchor nodes. In order to guarantee principle (2), we set the shortest side length thresholdthreshold_a, as shown in Table 2. Among all combinations satisfying the threshold, we select the maximum dmin(l), as shown in Table 2.Table 2
Explanation of parameters and variables.
Notation Description n o d e 1 ( i ) Unknown nodei R Communication radius r ring The ring shown in Figure9 n o d e 1 ( i ) . n e i g h b o r Neighbor anchor nodes set of unknown nodei on r ring, recording distance and location information of anchor nodes N ( i ) The number of neighbor anchor nodes of unknown nodei n o d e 1 ( i ) . f l a g 1 Localization flag of unknown nodei. The initial value is 0, update to 1 after localization n o d e 1 ( i ) . f l a g 2 Record the time when the unknown nodei is located θ m i n ( l ) Minimum internal angle of thelth combination of anchor node, l=1⋯CN(i)3 d m i n ( l ) The shortest edge of thelth combination of anchor node, l=1⋯CN(i)3 t h r e s h o l d _ a The shortest edge threshold t Waiting time thresholdIt should be noted that the inner radiusesr and threshold_a are given in Section 5 through simulation experiments, where r=0.6R, threshold_a=0.8R.


## 4.2. Symbol Description

The main parameters and variables used in the algorithm are shown in Table2.


## 4.3. Algorithm Procedure

In the beginning, initial anchor nodes broadcast their location information, and unknown nodes collect the information of neighbor anchor nodes and measure the distance.The unknown node starts executing the anchor nodes selection algorithm. The algorithm flowchart is shown in Figure10. After completing localization procedure, the unknown node updates node1(i).flag1=1 and becomes an anchor node. Then, it will broadcast its own location information. If the unknown node fails to complete the localization procedure, for example, no anchor node information is collected, or the anchor node information does not satisfy requirement of the flowchart, then it will enter the waiting state and wait for receiving enough information to complete the localization procedure.Figure 10
Algorithm flowchart.In a relatively sparse network, some unknown nodes may wait for a long time to find the anchor node information which can satisfy the requirement of the flowchart. Therefore, according to different applications, a waiting time thresholdt may be set. When reaching the waiting time threshold and the localization procedure is still not completed, the conditions in the flowchart can be properly relaxed. For example, the value of r can be reduced. Of course this may reduce localization accuracy.


## 5. Performance Evaluation

### 5.1. Simulation Setup

Our experiments are run on various topologies of networks in Matlab R2017a. The 200 unknown nodes are placed randomly with a uniform distribution within a 1000∗1000 square area. The m anchor nodes are placed (a) randomly with a uniform distribution around the square area as shown in Figure 11(a), or (b) randomly with a uniform distribution within the square area as shown in Figure 11(b). In order to observe the influence of network average connectivity on localization accuracy, we change communication radius R between 200 and 300. We assume that Δd~U(-1%R,1%R). The performance of different algorithms is compared using mean absolute error (MAE) of the location estimates. We also calculate error bar defined by standard deviation to compare the stability of the algorithms. The standard deviation is given as follows.(31)σ=1N∑i=1NΔi-Δ¯2Figure 11
Two kinds of anchor nodes arrangement. (a) Around the square area. (b) In the square area.
(a) (b)The performance of the proposed algorithm (EATL) is compared with that of the Maximum Likelihood-based (ML) localization algorithm and the minimum condition number-based (FMMC) localization algorithm [6]. In ML approach, the unknown node to be located requires a minimum of seven neighbor anchor nodes. When comparing the performance of the three algorithms, we mainly do simulation on the network topology shown in Figure 11(a). For this type of network topology, the anchor nodes are placed around the network, the inside unknown nodes require more iterations to complete location which may result in greater iteration error. In many application scenarios, the anchor nodes can only be randomly placed around the network, such as the battlefield environment. It is more practical to simulate the network topology in Figure 11(a).


### 5.2.r and threshold_a

We setm=75, R=200, and Δd~U(-2,2). The network topology is shown in Figure 11(a). We change r from 0.5R to 0.75R, sampling every 0.05R, sampling 6 times. Similarly, threshold_a is changed from 0.6R to 0.8R, sampling every 0.05R, sampling 5 times. Thus, There are a total of 30 combinations of r and threshold_a. We do experiment to solve the MAE of every combination. The value of MAE varies with r and threshold_a is shown in Figure 12.Figure 12
MAE varies withr and threshold_a.From Figure12, with the increase of r and thereshold_a, that is, the constraints becoming more and more stringent, the MAE is generally on a downward trend. For example, when r=0.5R and threshold_a=0.6R, MAE=19.47. When r=0.6R and threshold_a=0.8R, MAE=3.62. However, as r increases, the area where unknown nodes select anchor nodes continuously decreases, which lead to a long waiting time of the unknown nodes to be located. The entire network requires more iteration times. When r=0.7R, it takes more than 10 iteration times to complete the entire network localization. The increase in the number of iterations means the accumulation of iteration errors. From Figure 12, it can also be seen that when r increases to 0.65R, continued increase of r does not significantly reduce the MAE, but the entire network localization time increases significantly. After balancing the localization time and localization accuracy, in the following simulations, if there are no special instructions, we take r=0.6R and threshold_a=0.8R.


### 5.3. MAE Performance

We setm=75 and R=200 to observe that MAE varies with iteration times of the three algorithms. The network topology is shown in Figure 11(a).As shown in Figure13, The MAE of all three algorithms tends to increase with the number of iterations, which is due to the accumulation of errors. According to the error bar of each iteration, the standard deviation of the proposed algorithm is smaller than that of ML and FMMC, and the proposed algorithm is more stable.Figure 13
MAE for different iteration times.Overall, ML algorithm requires 4 iteration times to complete the localization and the MAE is 5.07. FMMC algorithm requires 5 iteration times and the MAE is 4.12. The proposed algorithm requires 6 iteration times and the MAE is 3.62. Compared with ML and FMMC, the MAE of proposed algorithm decreased by 28.6% and 12.1%, respectively.


### 5.4. Impact of Network Connectivity

We setm=75 and the values of R are 200, 225, 250, 275, and 300, respectively. The network topology is shown in Figure 11(a). Figure 14(a) shows that, with the increase of the communication radius of nodes, the network connectivity increases. From Figure 14(b), we can see that, under different communication radius, the MAE and standard deviation of the proposed algorithm are lower than that of ML algorithm and FMMC algorithm. This shows that the proposed algorithm has good stability and scalability.Figure 14
Impact of network connectivity. (a) Network connectivity for different communication radius. (b) MAE for different network connectivity.
(a) (b)


### 5.5. Impact of Different Number of Anchor Nodes

We setR=200 and the values of m are 20, 25, 30, 35, 40, 45, and 50, respectively. The network topology is shown in Figure 11(b). From Figure 15, with the increase in the number of anchor nodes, the MAE and standard deviation are gradually reduced. When the number of anchor nodes exceeds 30, the increase in the number of anchor nodes has no obvious effect on improving the localization accuracy of the network. When the number of anchor nodes in the network is less than 20, the process takes too long and the localization accuracy is low.Figure 15
Impact of different number of anchor nodes.


## 5.1. Simulation Setup

Our experiments are run on various topologies of networks in Matlab R2017a. The 200 unknown nodes are placed randomly with a uniform distribution within a 1000∗1000 square area. The m anchor nodes are placed (a) randomly with a uniform distribution around the square area as shown in Figure 11(a), or (b) randomly with a uniform distribution within the square area as shown in Figure 11(b). In order to observe the influence of network average connectivity on localization accuracy, we change communication radius R between 200 and 300. We assume that Δd~U(-1%R,1%R). The performance of different algorithms is compared using mean absolute error (MAE) of the location estimates. We also calculate error bar defined by standard deviation to compare the stability of the algorithms. The standard deviation is given as follows.(31)σ=1N∑i=1NΔi-Δ¯2Figure 11
Two kinds of anchor nodes arrangement. (a) Around the square area. (b) In the square area.
(a) (b)The performance of the proposed algorithm (EATL) is compared with that of the Maximum Likelihood-based (ML) localization algorithm and the minimum condition number-based (FMMC) localization algorithm [6]. In ML approach, the unknown node to be located requires a minimum of seven neighbor anchor nodes. When comparing the performance of the three algorithms, we mainly do simulation on the network topology shown in Figure 11(a). For this type of network topology, the anchor nodes are placed around the network, the inside unknown nodes require more iterations to complete location which may result in greater iteration error. In many application scenarios, the anchor nodes can only be randomly placed around the network, such as the battlefield environment. It is more practical to simulate the network topology in Figure 11(a).


## 5.2.r and threshold_a

We setm=75, R=200, and Δd~U(-2,2). The network topology is shown in Figure 11(a). We change r from 0.5R to 0.75R, sampling every 0.05R, sampling 6 times. Similarly, threshold_a is changed from 0.6R to 0.8R, sampling every 0.05R, sampling 5 times. Thus, There are a total of 30 combinations of r and threshold_a. We do experiment to solve the MAE of every combination. The value of MAE varies with r and threshold_a is shown in Figure 12.Figure 12
MAE varies withr and threshold_a.From Figure12, with the increase of r and thereshold_a, that is, the constraints becoming more and more stringent, the MAE is generally on a downward trend. For example, when r=0.5R and threshold_a=0.6R, MAE=19.47. When r=0.6R and threshold_a=0.8R, MAE=3.62. However, as r increases, the area where unknown nodes select anchor nodes continuously decreases, which lead to a long waiting time of the unknown nodes to be located. The entire network requires more iteration times. When r=0.7R, it takes more than 10 iteration times to complete the entire network localization. The increase in the number of iterations means the accumulation of iteration errors. From Figure 12, it can also be seen that when r increases to 0.65R, continued increase of r does not significantly reduce the MAE, but the entire network localization time increases significantly. After balancing the localization time and localization accuracy, in the following simulations, if there are no special instructions, we take r=0.6R and threshold_a=0.8R.


## 5.3. MAE Performance

We setm=75 and R=200 to observe that MAE varies with iteration times of the three algorithms. The network topology is shown in Figure 11(a).As shown in Figure13, The MAE of all three algorithms tends to increase with the number of iterations, which is due to the accumulation of errors. According to the error bar of each iteration, the standard deviation of the proposed algorithm is smaller than that of ML and FMMC, and the proposed algorithm is more stable.Figure 13
MAE for different iteration times.Overall, ML algorithm requires 4 iteration times to complete the localization and the MAE is 5.07. FMMC algorithm requires 5 iteration times and the MAE is 4.12. The proposed algorithm requires 6 iteration times and the MAE is 3.62. Compared with ML and FMMC, the MAE of proposed algorithm decreased by 28.6% and 12.1%, respectively.


## 5.4. Impact of Network Connectivity

We setm=75 and the values of R are 200, 225, 250, 275, and 300, respectively. The network topology is shown in Figure 11(a). Figure 14(a) shows that, with the increase of the communication radius of nodes, the network connectivity increases. From Figure 14(b), we can see that, under different communication radius, the MAE and standard deviation of the proposed algorithm are lower than that of ML algorithm and FMMC algorithm. This shows that the proposed algorithm has good stability and scalability.Figure 14
Impact of network connectivity. (a) Network connectivity for different communication radius. (b) MAE for different network connectivity.
(a) (b)


## 5.5. Impact of Different Number of Anchor Nodes

We setR=200 and the values of m are 20, 25, 30, 35, 40, 45, and 50, respectively. The network topology is shown in Figure 11(b). From Figure 15, with the increase in the number of anchor nodes, the MAE and standard deviation are gradually reduced. When the number of anchor nodes exceeds 30, the increase in the number of anchor nodes has no obvious effect on improving the localization accuracy of the network. When the number of anchor nodes in the network is less than 20, the process takes too long and the localization accuracy is low.Figure 15
Impact of different number of anchor nodes.


## 6. Conclusion

This paper proposes an anchor selection algorithm based on error analysis, starting from an example of ill-conditioned linear equation to show that selecting the right anchor nodes combination will make a big difference in localization accuracy. The influence of distance measurement error on localization accuracy is discussed from two aspects: condition number of triangle formed by the three anchor nodes and the relative position between the unknown node and the three anchor nodes. Then an algorithm of selecting anchor nodes on a ring is proposed. The values ofr and thereshold_a are given through simulation experiments. Simulation also shows that the performance of the proposed algorithm in MAE and standard deviation are better than those of ML algorithm and FMMC algorithm.



---

*Source: 7295702-2018-12-05.xml*