# Neighbor Constraint Assisted Distributed Localization for Wireless Sensor Networks

Authors: Longfei Wen; Lingguo Cui; Senchun Chai; Baihai Zhang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Localization is one of the most significant technologies in wireless sensor networks (WSNs) since it plays a critical role in many applications. The main idea in most localization methods is to estimate the sensor-anchor distances that are used by sensors to locate themselves. However, the distance information is always imprecise due to the measurement or estimation errors. In this work,  a novel algorithm called neighbor constraint assisted distributed localization (NCA-DL) is proposed, which introduces the application of geometric constraints to these distances within the algorithm. For example, in the case presented here, the assistance provided by a neighbor will consist in formulating a linear equality constraint. These constraints can be further used to formulate optimization problems for distance estimation. Then through some optimization methods, the imprecise distances can be refined and the localization precision is improved.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) composed of a large number of low-power sensors have been a subject of increased interest in recent years [1–3]. Location information of sensor nodes is vital for location-aware applications such as environmental monitoring, routing, and coverage control [4, 5]. Due to cost limitations and energy consumption, having each one of the sensors locate its position individually via GPS or other similar means is no longer a viable option. Hence, lots of works have focused on the localization algorithms for WSNs [6].Based on the type of information they require, localization algorithms can be divided into two categories: (i) range-based and (ii) range-free [7–10]. For both categories of localization algorithms, the most crucial phase of the process lies in the determination of the distances between the sensor nodes which need to be located and the anchors. In range-based algorithms, the respective distances between sensors and anchors can be obtained via various ranging techniques such as time of arrival (TOA), time difference of arrival (TDOA), and received signal strength indication (RSSI). On the other hand, in range-free algorithms, distances can be estimated through topological or geometric information. DV-Hop is a classical distributed range-free algorithm which determines distances by hop counts [11]. By further combination with ranging techniques, DV-Hop can be extended in order to decrease its localization error; a noteworthy example of these methods is robust position [12–14]. However, no matter which method is used, the acquired distances information to the anchors is usually imprecise compared with the true distances because of ranging and estimation errors [15, 16]. The imprecise distances will result in poor localization performance. Actually, these imprecise distances can be refined since the true distances between nodes should satisfy the geometric relations. In other words, the localization precision can be improved with the help of some geometric constraints.In this work, a novel algorithm called neighbor constraint assisted distributed localization (NCA-DL) is proposed which is effective in refining the distances required for localization. NCA-DL describes the geometric relations among the distances between sensor nodes and anchors as some equality constraints. The core idea behind NCA-DL is to use theCayley-Menger determinant[17, 18] which will be defined in the following section. In NCA-DL, by using an adjacent neighbor which could be a mobile anchor, a linear equality constraint of distance estimation errors can be obtained. Through some optimal solution computation methods that are used to minimize the sum of the squared errors, the distances can be refined and the localization precision can be improved. The major contribution of this paper is twofold. First, the proposed algorithm is distributed so that sensor nodes can estimate their locations by themselves. Second, it introduces the idea of geometric constraints and decreases the distance estimation errors with the help of an adjacent neighbor. In general, the proposed method can largely improve the localization precision.The layout of the paper is organized as follows. In Section2, the preliminaries to the problem are introduced. In Section 3, the geometric relations among sensor nodes are formulated as constraints. In Section 4, the proposed distributed localization method will be described in detail. Section 5 presents the implementation and results of the numerical simulations that were performed to validate the method. Finally, conclusion will be drawn from this research in Section 6.


## 2. Preliminaries

Let us first consider{
a
1
,
a
2
,
…
,
a
n
} and {
b
1
,
b
2
,
…
,
b
n
} which represent a set of n distinct points, respectively. TheCayley-Menger matrix of these two sets can be defined as
(1)
C
(
a
1
,
a
2
,
…
,
a
n
;
b
1
,
b
2
,
…
,
b
n
)
≜
(
d
2
(
a
1
,
b
1
)
d
2
(
a
1
,
b
2
)
⋯
d
2
(
a
1
,
b
n
)
1
d
2
(
a
2
,
b
1
)
d
2
(
a
2
,
b
2
)
⋯
d
2
(
a
2
,
b
n
)
1
⋮
⋮
⋱
⋮
⋮
d
2
(
a
n
,
b
1
)
d
2
(
a
n
,
b
2
)
⋯
d
2
(
a
n
,
b
n
)
1
1
1
⋯
1
0
)
,
where d
(
a
i
,
b
j
); ∀
(
i
,
j
)
∈
{
1,2
,
…
,
n
} denotes the Euclidean distance between the points a
i and b
j.TheCayley-Menger bideterminant of these two sequences of n points is defined as
(2)
D
(
a
1
,
a
2
,
…
,
a
n
;
b
1
,
b
2
,
…
,
b
n
)
≜
det
⁡
C
(
a
1
,
a
2
,
…
,
a
n
;
b
1
,
b
2
,
…
,
b
n
)
.The above determinant is widely used in distance geometry theory [17]. When the two sequences of points are the same, D
(
a
1
,
a
2
,
…
,
a
n
;
a
1
,
a
2
,
…
,
a
n
) is denoted for convenience by D
(
a
1
,
a
2
,
…
,
a
n
) which is simply called aCayley-Menger determinant.A brief summary of theCayley-Menger determinant is generalized as follows [19].Theorem 1.
Consider an n-tuple of pointsa
1
,
a
2
,
…
,
a
n in m-dimensional space. If n
≥
m
+
2, then the Cayley-Menger matrix C
(
a
1
,
a
2
,
…
,
a
n
) is singular, namely,
(3)
D
(
a
1
,
a
2
,
…
,
a
n
)
=
0
.Theorem 2 (Theorem 112.1 in Blumenthal [17]).
Consider an n-tuple of pointsa
1
,
a
2
,
…
,
a
n in m-dimensional space. If n
≥
m
+
1, the rank of Cayley-Menger matrix C
(
a
1
,
a
2
,
…
,
a
n
) is at most m
+
1.In a 2-dimensional Euclidean space, each node has a set of coordinates(
x
i
,
y
i
). The study of the localization problem applied to WSNs first requires some basic terminology and concepts to be defined.Definition 3 (regular nodes).
Most of the nodes in the network do not know their locations. The whole purpose of localization algorithms is to estimate the coordinates of these nodes.Definition 4 (anchors).
Some of the nodes can know their locations through manual placement or with the help of specific equipment such as GPS. The coordinates of these nodes are used as reference information to assist in the localization procedure.According to the above theorems and definitions, an interesting development of localization is how to use theCayley-Menger determinant to reduce the impact of distance measurement errors [20]. As shown in Figure 1, let d
i
j
=
d
(
a
i
,
a
j
) denote the accurate Euclidean distance between anchors a
i and a
j with i
≠
j, (i
,
j
=
1,2
,
3), which can be inferred from known anchor positions; d
0
i
=
d
(
r
0
,
a
i
) denotes the accurate distances between the regular node r
0 and node a
i with i
=
1,2
,
3 and d
¯
0
i denotes the inaccurate distances acquired by either noisy range measurement or computations. Then the following equation is defined:
(4)
d
¯
0
i
2
=
d
0
i
2
-
ε
i
.Figure 1
A regular node and the anchors.Theorem 5.
The errorsε
i for i
=
1,2
,
3 as defined immediately above satisfy a single algebraic equality which is quadratic though not homogeneous in the ε
i’s:
(5)
ε
T
A
ε
+
ε
T
b
+
c
=
0
,
where
(6)
ε
=
[
ε
1
,
ε
2
,
ε
3
]
T
A
=
(
2
d
23
2
d
12
2
-
d
13
2
-
d
23
2
d
13
2
-
d
23
2
-
d
12
2
d
12
2
-
d
13
2
-
d
23
2
2
d
13
2
d
23
2
-
d
12
2
-
d
13
2
d
13
2
-
d
12
2
-
d
23
2
d
23
2
-
d
12
2
-
d
13
2
2
d
12
2
)
b
1
=
4
d
23
2
d
¯
01
2
+
2
(
d
12
2
-
d
13
2
-
d
23
2
)
d
¯
02
2
+
2
(
d
13
2
-
d
12
2
-
d
23
2
)
d
¯
03
2
+
2
d
23
2
(
d
23
2
-
d
12
2
-
d
13
2
)
b
2
=
4
d
13
2
d
¯
02
2
+
2
(
d
12
2
-
d
13
2
-
d
23
2
)
d
¯
01
2
+
2
(
d
23
2
-
d
12
2
-
d
13
2
)
d
¯
03
2
+
2
d
13
2
(
d
13
2
-
d
12
2
-
d
23
2
)
b
3
=
4
d
12
2
d
¯
03
2
+
2
(
d
13
2
-
d
12
2
-
d
23
2
)
d
¯
01
2
+
2
(
d
23
2
-
d
12
2
-
d
13
2
)
d
¯
02
2
+
2
d
12
2
(
d
12
2
-
d
13
2
-
d
23
2
)
c
=
2
d
12
2
d
13
2
d
23
2
+
2
d
23
2
d
¯
01
4
+
2
d
13
2
d
¯
02
4
+
2
d
12
2
d
¯
03
4
+
2
(
d
12
2
-
d
13
2
-
d
23
2
)
d
¯
01
2
d
¯
02
2
+
2
(
d
13
2
-
d
12
2
-
d
23
2
)
d
¯
01
2
d
¯
03
2
+
2
(
d
23
2
-
d
12
2
-
d
13
2
)
d
¯
02
2
d
¯
03
2
+
2
d
23
2
(
d
23
2
-
d
12
2
-
d
13
2
)
d
¯
01
2
+
2
d
13
2
(
d
13
2
-
d
12
2
-
d
23
2
)
d
¯
02
2
+
2
d
12
2
(
d
12
2
-
d
13
2
-
d
23
2
)
d
¯
03
2
.Proof.
According to Theorem1, we know that D
(
r
0
,
a
1
,
a
2
,
a
3
)
=
0, namely,
(7)
det
⁡
(
0
d
01
2
d
02
2
d
03
2
1
d
01
2
0
d
12
2
d
13
2
1
d
02
2
d
12
2
0
d
23
2
1
d
03
2
d
13
2
d
23
2
0
1
1
1
1
1
0
)
=
0
.
Suppose the anchors are nonlinear,D
(
a
1
,
a
2
,
a
3
)
≠
0. From (7), the following equation can be derived:
(8)
(
d
01
2
d
02
2
d
03
2
1
)
E
-
1
(
d
01
2
d
02
2
d
03
2
1
)
=
0
,
where
(9)
E
=
(
0
d
12
2
d
13
2
1
d
12
2
0
d
23
2
1
d
13
2
d
23
2
0
1
1
1
1
0
)
.
Then according to (4), we can obtain
(10)
(
d
¯
01
2
+
ε
1
d
¯
02
2
+
ε
2
d
¯
03
2
+
ε
3
1
)
E
-
1
(
d
¯
01
2
+
ε
1
d
¯
02
2
+
ε
2
d
¯
03
2
+
ε
3
1
)
=
0
.
Multiplying both sides of (10) by the determinant of E
-
1, we can arrive at (5). This completes the proof.


## 3. Geometric Relations with Neighbor Constraint

In this section, we will focus on the geometric relations among the distances between nodes, which can be transformed to an algebraic constraint of the distance estimation errors. At first, we define another basic term.Definition 6 (neighbors).
Each node in WSNs has a communication range. So, for a nodei in network, the nodes which can communicate with node i directly are the neighbors of node i.As shown in Figure2, r
(
x
0
,
y
0
) represents a regular node which needs to be located, n
(
x
1
,
y
1
) represents a neighbor of node r
′ and a
i
(
x
i
,
y
i
) represents the anchors with i
=
2,3
,
4. Then Let d
i
j
=
d
(
a
i
,
a
j
) denote the accurate Euclidean distance between anchors a
i and a
j with i
≠
j
,
i
,
j
=
2,3
,
4, d
1
i
=
d
(
n
,
a
i
) denote the accurate distances between the neighbor node n and anchor a
i with i
=
2,3
,
4, d
0
i
=
d
(
r
,
a
i
) denote the accurate distances between the regular node r and anchor a
i with i
=
2,3
,
4, and d
01 denote the accurate distance between regular node r and its neighbor node n.Figure 2
Anchors, a regular node, and its neighbor node.In this case, suppose we know the accurate distancesd
1
i (i
=
2,3
,
4) and the accurate distance d
01 by refinement or setting node n as a mobile anchor. Then d
¯
0
i
2
=
d
0
i
2
-
ε
i denote the inaccurate distances squared between node r and anchor a
i with i
=
2,3
,
4 for some error ε
i. That is to say, the true distances represented by the dotted line in Figure 2 cannot be obtained. In this work, we aim to refine these inaccurate distances to trend toward actual values.Theorem 7.
The errorsε
i for i
=
2,3
,
4 as defined immediately above satisfy an algebraic equality in the ε
i’s, and whose coefficients are determined by d
01, d
¯
0
i for i
=
2,3
,
4 and d
i
j for i
,
j
=
1,2
,
3,4 and i
≠
j:
(11)
α
ε
2
+
β
ε
3
+
γ
ε
4
+
δ
=
0
,
where
(12)
α
=
d
34
2
(
d
23
2
+
d
24
2
-
d
34
2
)
-
2
d
34
2
d
12
2
+
d
13
2
(
d
24
2
-
d
23
2
+
d
34
2
)
+
d
14
2
(
d
23
2
-
d
24
2
+
d
34
2
)
β
=
d
24
2
(
d
23
2
-
d
24
2
+
d
34
2
)
-
2
d
24
2
d
13
2
+
d
12
2
(
d
24
2
-
d
23
2
+
d
34
2
)
+
d
14
2
(
d
23
2
+
d
24
2
-
d
34
2
)
γ
=
d
23
2
(
d
24
2
-
d
23
2
+
d
34
2
)
-
2
d
23
2
d
14
2
+
d
12
2
(
d
23
2
-
d
24
2
+
d
34
2
)
+
d
13
2
(
d
23
2
+
d
24
2
-
d
34
2
)
δ
=
d
¯
02
2
(
d
34
2
(
d
23
2
+
d
24
2
-
d
34
2
)
-
2
d
34
2
d
12
2
+
d
13
2
(
d
24
2
-
d
23
2
+
d
34
2
)
+
d
14
2
(
d
23
2
-
d
24
2
+
d
34
2
)
)
+
d
¯
03
2
(
d
24
2
(
d
23
2
-
d
24
2
+
d
34
2
)
-
2
d
24
2
d
13
2
+
d
12
2
(
d
24
2
-
d
23
2
+
d
34
2
)
+
d
14
2
(
d
23
2
+
d
24
2
-
d
34
2
)
)
+
d
¯
04
2
(
d
23
2
(
d
24
2
-
d
23
2
+
d
34
2
)
-
2
d
23
2
d
14
2
+
d
12
2
(
d
23
2
-
d
24
2
+
d
34
2
)
+
d
13
2
(
d
23
2
+
d
24
2
-
d
34
2
)
)
+
d
23
2
d
14
2
(
d
24
2
-
d
23
2
+
d
34
2
)
+
d
24
2
d
13
2
(
d
23
2
-
d
24
2
+
d
34
2
)
+
d
34
2
d
12
2
(
d
23
2
+
d
24
2
-
d
34
2
)
-
2
d
23
2
d
24
2
d
34
2
+
d
01
2
(
d
23
4
+
d
24
4
+
d
34
4
-
2
d
23
2
d
24
2
-
2
d
23
2
d
34
2
-
2
d
24
2
d
34
2
)
.Proof.
According to Theorem1, we know that D
(
r
,
n
,
a
2
,
a
3
,
a
4
)
=
0, namely,
(13)
det
⁡
(
0
d
01
2
d
02
2
d
03
2
d
04
2
1
d
01
2
0
d
12
2
d
13
2
d
14
2
1
d
02
2
d
12
2
0
d
23
2
d
24
2
1
d
03
2
d
13
2
d
23
2
0
d
34
2
1
d
04
2
d
14
2
d
24
2
d
34
2
0
1
1
1
1
1
1
0
)
=
0
.
One can then obtain,
(14)
det
⁡
(
B
11
B
12
B
12
T
B
22
)
=
0
,
where
(15)
B
11
=
(
0
d
01
2
d
01
2
0
)
B
12
=
(
d
02
2
d
03
2
d
04
2
1
d
12
2
d
13
2
d
14
2
1
)
B
22
=
(
0
d
23
2
d
24
2
1
d
23
2
0
d
34
2
1
d
24
2
d
34
2
0
1
1
1
1
0
)
.
Suppose the anchors are nonlinear;D
(
a
2
,
a
3
,
a
4
)
≠
0, so B
22 is nonsingular. From (14), the following equation can be derived:
(16)
det
⁡
(
B
11
-
B
12
B
22
-
1
B
12
T
)
det
⁡
B
22
=
0
.
That is,
(17)
det
⁡
(
0
-
(
b
120
T
B
22
-
1
b
120
)
d
01
2
-
(
b
120
T
B
22
-
1
b
121
)
d
01
2
-
(
b
121
T
B
22
-
1
b
120
)
0
-
(
b
121
T
B
22
-
1
b
121
)
)
=
0
,
where
(18)
b
120
=
(
d
02
2
d
03
2
d
04
2
1
)
T
b
121
=
(
d
12
2
d
13
2
d
14
2
1
)
T
.
According to the proof procedure of Theorem 5, we can obtain b
120
T
B
22
-
1
b
120
=
b
121
T
B
22
-
1
b
121
=
0. Then from (17), we obtain
(19)
b
120
T
B
22
-
1
b
121
=
b
121
T
B
22
-
1
b
120
=
d
01
2
.
This yields
(20)
(
d
¯
02
2
+
ε
2
d
¯
03
2
+
ε
3
d
¯
04
2
+
ε
4
1
)
B
22
-
1
(
d
12
2
d
13
2
d
14
2
1
)
=
d
01
2
.
Multiplying both sides of (20) by the determinant of B
22, we obtain
(21)
(
d
¯
02
2
+
ε
2
d
¯
03
2
+
ε
3
d
¯
04
2
+
ε
4
1
)
B
22
*
(
d
12
2
d
13
2
d
14
2
1
)
=
d
01
2
×
det
⁡
(
B
22
)
,
where(22)
B
22
*
=
(
2
d
34
2
d
23
2
-
d
24
2
-
d
34
2
d
24
2
-
d
23
2
-
d
34
2
d
34
2
(
d
34
2
-
d
23
2
-
d
24
2
)
d
23
2
-
d
24
2
-
d
34
2
2
d
24
2
d
34
2
-
d
23
2
-
d
24
2
d
24
2
(
d
24
2
-
d
23
2
-
d
34
2
)
d
24
2
-
d
23
2
-
d
34
2
d
34
2
-
d
23
2
-
d
24
2
2
d
23
2
d
23
2
(
d
23
2
-
d
24
2
-
d
34
2
)
d
34
2
(
d
34
2
-
d
23
2
-
d
24
2
)
d
24
2
(
d
24
2
-
d
23
2
-
d
34
2
)
d
23
2
(
d
23
2
-
d
24
2
-
d
34
2
)
2
d
23
2
d
24
2
d
34
2
)
.According to (21), we can get (11). This completes the proof.


## 4. Neighbor Constraint Assisted Distributed Localization

Based on the algebraic constraints mentioned in the previous sections, a neighbor constraint assisted distributed localization algorithm (NCA-DL) is hereby proposed as a means of improving the localization precision. The main idea behind NCA-DL is to refine the distances to anchors using a neighbor node. In NCA-DL, the regular nodes estimate the initial distances to the anchors using the method similar to DV-Hop [11]. Then according to the algebraic constraints of the distance estimation errors, Lagrangian multiplier method is introduced in order to obtain the optimal errors and refine the distances. The following section will give a full description of the principles and performance analysis of this novel NCA-DL algorithm.


### 4.1. Principles of the Algorithm

Initially, anchors (setA) are deployed in the sensing field with the regular nodes (set R). We assume each node has the ability of ranging, and for simplicity, the number of the anchors is set to 3. The whole process of NCA-DL is divided into four phases.(A) Distance Estimation. Each regular node is supposed to obtain initial distance estimation to the anchors. So two times of flooding are required to accomplish the process of distance estimation. In the first flooding, the anchors start by propagating their location information. Then all nodes receive the location information from every anchor as well as the hop count to these anchors. When an anchor node receives location information from other anchors, it can calculate the average size of a hop based on their locations and the hop count among them. In the second flooding, the average size of a hop is transmitted in a controlled manner into the network as a correction factor. When a regular node receives the correction, it can be able to estimate the distances to the anchors using the correction and the hop count information received in the previous flooding.(B) Neighbor Node Election. The main purpose of this phase is to choose a proper neighbor for each regular node to assist distance refinement in the next phase. For most ranging technology, when sensors are closer, the distance estimations are more accurate. According to the requirement of Theorem 7, in order to obtain the constraint equation of the distance estimation errors, it is fundamental to choose an adjacent neighbor because the distance between the regular node and its neighbor can be measured accurately. Meanwhile, the distances among the neighbor and the anchors also should satisfy geometry relationship, that is to say, the distances should be refined by the method in [20]. So in this phase, the nearest node of each regular node is chosen as an assistant neighbor and its distances to the anchors obtained in the previous phase are supposed to be refined using Theorem 5.To improve the localization precision of the regular node further, the distances between the neighbor and the anchors need to be estimated accurately. Though the imprecise distances can be refined through Theorem5 which can meet the requirement of Theorem 7, the distances are still imprecise. So in this phase, with the growing research for the mobility of sensors [21], a mobile anchor also can be used to be a “neighbor” of each regular node. The distances between this “neighbor” and the other static anchors can be accurately calculated by the coordinates of these anchors, which definitely meets the requirement of Theorem 7. In this case, the mobile anchor is supposed to move in the sensing field. The aim is just to assist the regular node with localization through the constraint defined in Theorem 7 and it does not need to consider the collinear problems of the anchors. So SCAN [22] could be used for the path planning method, which is the most straightforward one.(C) Distance Refinement. The algebraic equalities that define the errors and relate the distances to the anchors for each regular node have now been fully determined from the previous two phases, as described in Theorems 5 and 7. The next step of the algorithm attempts to quantify these errors in the inaccurate distance estimations between regular nodes and anchors. Let ε
i (∀
i
∈
{
2,3
,
4
}) as defined in (4) be the error in the estimated squared distances between a regular node and the anchors. The goal here is to minimize the sum of the squared errors:
(23)
J
=
ε
2
2
+
ε
3
2
+
ε
4
2
.In (23), J is subjected to a quadratic equality constraint defined in (5) and a linear equality constraint defined in (11). So, to solve the optimization problem with constraints, Lagrangian multiplier method has been implemented in the algorithm. It is a mathematical method used to solve the optimization problem, which can convert the constraints to the seeking of extreme values with the help of Lagrangian multipliers. We can get the following Lagrangian multiplier form:
(24)
H
(
ε
2
,
ε
3
,
ε
4
,
λ
1
,
λ
2
)
=
∑
i
=
2
4
ε
i
2
+
λ
1
f
1
(
ε
2
,
ε
3
,
ε
4
)
+
λ
2
f
2
(
ε
2
,
ε
3
,
ε
4
)
,
where λ
1
,
λ
2 are the Lagrangian multipliers and f
1
,
f
2 are the functions of ε
2
,
ε
3
,
ε
4, whose coefficients can be obtained in (5) and (11).By differentiating the LagrangianH with respect to ε
i (i
=
2,3
,
4) and λ
i (i
=
1,2) and equating the result to zero, five equations can be obtained. Solving these five algebraic equations numerically and discarding all the nonoptimal stationary-point solutions, ε
2
,
ε
3
,
ε
4 can be solved. Then the distances to the anchors for the regular node are refined. The below example demonstrates the steps in this phase.The simplest scenario as depicted in Figure2 is considered, where node r is the regular node that needs to be located. Node r can measure its distances to three anchors a
2
,
a
3
,
a
4 whose coordinates are (10, 10), (90, 10), and (50, 90), respectively. The noisy distance measurements acquired by node r are d
¯
02
=
56.3, d
¯
03
=
65.7, and d
¯
04
=
41.6. The distances between the neighbor node n and other nodes are estimated in the previous phase as d
01
=
5, d
12
=
56.6, d
13
=
56.6, and d
14
=
40. In this case, the goal is to obtain the estimation errors ε
2
,
ε
3
,
ε
4 and refine d
¯
02, d
¯
03, and d
¯
04.Firstly, two equality constraints as described by (5) and (11) will be determined:
(25)
0
=
f
1
(
ε
2
,
ε
3
,
ε
4
)
0
=
(
-
2.5
ε
2
2
-
2.5
ε
3
2
-
2
ε
4
2
+
3
ε
2
ε
3
+
2
ε
2
ε
4
+
2
ε
3
ε
4
+
16597
ε
2

+
7341
ε
3
+
27262
ε
4
+
14159000
-
2.5
ε
2
2
)

×
(
25600
)
-
1
0
=
f
2
(
ε
2
,
ε
3
,
ε
4
)
0
=
0.25
ε
2
+
0.25
ε
3
+
0.5
ε
4
+
310.6
.To determine the optimal values forε
2
,
ε
3
,
ε
4, the following problem needs to be solved:
(26)
min
⁡
⁡
ε
2
2
+
ε
3
2
+
ε
4
2
s
.
t
.
f
1
(
ε
2
,
ε
3
,
ε
4
)
=
0
s
.
t
.
f
2
(
ε
2
,
ε
3
,
ε
4
)
=
0
.By differentiating the LagrangianH defined in (24), we obtain
(27)
∂
H
∂
ε
2
=
2
ε
2
+
0.25
λ
2
+
λ
1
(
3
25600
ε
3
-
ε
2
5120
+
ε
4
12800
+
0.65
)
=
0
∂
H
∂
ε
3
=
2
ε
3
+
0.25
λ
2
+
λ
1
(
3
25600
ε
2
-
ε
3
5120
+
ε
4
12800
+
0.28
)
=
0
∂
H
∂
ε
4
=
2
ε
4
+
0.5
λ
2
+
λ
1
(
ε
2
12800
+
ε
3
12800
-
ε
4
6400
+
1.06
)
=
0
∂
H
∂
λ
1
=
f
1
(
ε
2
,
ε
3
,
ε
4
)
=
0
,
∂
H
∂
λ
2
=
f
2
(
ε
2
,
ε
3
,
ε
4
)
=
0
.Solving the above five algebraic equations above, we get,(28)
ε
2
*
=
-
67.39
,
ε
3
*
=
-
545.76
,
ε
4
*
=
-
314.59
.Correspondingly, the refined distances between regular noder and the three anchors are
(29)
d
^
02
=
d
¯
02
2
+
ε
2
*
=
55.6
d
^
03
=
d
¯
03
2
+
ε
3
*
=
61.4
d
^
04
=
d
¯
04
2
+
ε
4
*
=
37.6
.As shown in Figure3, “.” represents the regular node, “□” represents the anchor, and the radius of the circle is the estimated distance between the regular node and the anchor. In Figure 3(b), the three circles intersect in one point, which proves that the refined distances satisfy the geometric constraints.Locations of anchors and the regular node.
(a)
Performance of noisy distances
(b)
Performance of refined distances(D) Localization. So far, regular nodes have known the refined distances to the anchors according to (29). Based on the above refinement scheme, we know that the refined distances satisfy the geometric constraints. Localization can be carried out by the least square method. r
(
x
,
y
) represents the regular node, a
(
x
i
,
y
i
) (i
=
2,3
,
4) represent the locations of the anchors, and d
^
02
,
d
^
03
,
d
^
04 represent the refined distances between the regular node and the anchors. The coordinate of the regular node can be estimated by
(30)
X
^
=
(
A
T
A
)
-
1
A
T
b
,
where
(31)
A
=
(
2
(
x
2
-
x
4
)
2
(
y
2
-
y
4
)
2
(
x
3
-
x
4
)
2
(
y
3
-
y
4
)
)
,
X
=
(
x
y
)
b
=
(
x
2
2
-
x
4
2
+
y
2
2
-
y
4
2
+
d
^
04
2
-
d
^
02
2
x
3
2
-
x
4
2
+
y
3
2
-
y
4
2
+
d
^
04
2
-
d
^
03
2
)
.Figure4 illustrates the localization of the computational example above with both noisy and refined distances. “*” represents the calculated location. The localization errors in Figures 4(a) and 4(b) are 0.67 m and 0.55 m, respectively.Localization effect of noisy distances and refined distances.
(a)
Localization with noisy distances
(b)
Localization with refined distances


### 4.2. Communication Cost Analysis

For energy cost of NCA-DL, the communication consumption is mainly considered in the distance estimation and refinement phases.n represents the number of the sensors and n
A represents the number of the anchors. Then for the two flooding processes in the distance estimation phase, it gives a bound of O
(
2
×
n
A
×
n
) to the communication cost in this process. While in the refinement phase, each node needs to communicate with its neighbors so the communication cost is O
(
n
). The total communication complexity is O
(
n
×
(
2
×
n
A
+
1
)
). It is known that the communication complexity of DV-Hop is O
(
2
×
n
A
×
n
). Since the method proposed in [20] is just to refine distance estimations with additional calculation, its communication complexity is the same as DV-Hop. So the cost of NCA-DL is in the same order of magnitude as other algorithms while it can largely improve the localization performance.


## 4.1. Principles of the Algorithm

Initially, anchors (setA) are deployed in the sensing field with the regular nodes (set R). We assume each node has the ability of ranging, and for simplicity, the number of the anchors is set to 3. The whole process of NCA-DL is divided into four phases.(A) Distance Estimation. Each regular node is supposed to obtain initial distance estimation to the anchors. So two times of flooding are required to accomplish the process of distance estimation. In the first flooding, the anchors start by propagating their location information. Then all nodes receive the location information from every anchor as well as the hop count to these anchors. When an anchor node receives location information from other anchors, it can calculate the average size of a hop based on their locations and the hop count among them. In the second flooding, the average size of a hop is transmitted in a controlled manner into the network as a correction factor. When a regular node receives the correction, it can be able to estimate the distances to the anchors using the correction and the hop count information received in the previous flooding.(B) Neighbor Node Election. The main purpose of this phase is to choose a proper neighbor for each regular node to assist distance refinement in the next phase. For most ranging technology, when sensors are closer, the distance estimations are more accurate. According to the requirement of Theorem 7, in order to obtain the constraint equation of the distance estimation errors, it is fundamental to choose an adjacent neighbor because the distance between the regular node and its neighbor can be measured accurately. Meanwhile, the distances among the neighbor and the anchors also should satisfy geometry relationship, that is to say, the distances should be refined by the method in [20]. So in this phase, the nearest node of each regular node is chosen as an assistant neighbor and its distances to the anchors obtained in the previous phase are supposed to be refined using Theorem 5.To improve the localization precision of the regular node further, the distances between the neighbor and the anchors need to be estimated accurately. Though the imprecise distances can be refined through Theorem5 which can meet the requirement of Theorem 7, the distances are still imprecise. So in this phase, with the growing research for the mobility of sensors [21], a mobile anchor also can be used to be a “neighbor” of each regular node. The distances between this “neighbor” and the other static anchors can be accurately calculated by the coordinates of these anchors, which definitely meets the requirement of Theorem 7. In this case, the mobile anchor is supposed to move in the sensing field. The aim is just to assist the regular node with localization through the constraint defined in Theorem 7 and it does not need to consider the collinear problems of the anchors. So SCAN [22] could be used for the path planning method, which is the most straightforward one.(C) Distance Refinement. The algebraic equalities that define the errors and relate the distances to the anchors for each regular node have now been fully determined from the previous two phases, as described in Theorems 5 and 7. The next step of the algorithm attempts to quantify these errors in the inaccurate distance estimations between regular nodes and anchors. Let ε
i (∀
i
∈
{
2,3
,
4
}) as defined in (4) be the error in the estimated squared distances between a regular node and the anchors. The goal here is to minimize the sum of the squared errors:
(23)
J
=
ε
2
2
+
ε
3
2
+
ε
4
2
.In (23), J is subjected to a quadratic equality constraint defined in (5) and a linear equality constraint defined in (11). So, to solve the optimization problem with constraints, Lagrangian multiplier method has been implemented in the algorithm. It is a mathematical method used to solve the optimization problem, which can convert the constraints to the seeking of extreme values with the help of Lagrangian multipliers. We can get the following Lagrangian multiplier form:
(24)
H
(
ε
2
,
ε
3
,
ε
4
,
λ
1
,
λ
2
)
=
∑
i
=
2
4
ε
i
2
+
λ
1
f
1
(
ε
2
,
ε
3
,
ε
4
)
+
λ
2
f
2
(
ε
2
,
ε
3
,
ε
4
)
,
where λ
1
,
λ
2 are the Lagrangian multipliers and f
1
,
f
2 are the functions of ε
2
,
ε
3
,
ε
4, whose coefficients can be obtained in (5) and (11).By differentiating the LagrangianH with respect to ε
i (i
=
2,3
,
4) and λ
i (i
=
1,2) and equating the result to zero, five equations can be obtained. Solving these five algebraic equations numerically and discarding all the nonoptimal stationary-point solutions, ε
2
,
ε
3
,
ε
4 can be solved. Then the distances to the anchors for the regular node are refined. The below example demonstrates the steps in this phase.The simplest scenario as depicted in Figure2 is considered, where node r is the regular node that needs to be located. Node r can measure its distances to three anchors a
2
,
a
3
,
a
4 whose coordinates are (10, 10), (90, 10), and (50, 90), respectively. The noisy distance measurements acquired by node r are d
¯
02
=
56.3, d
¯
03
=
65.7, and d
¯
04
=
41.6. The distances between the neighbor node n and other nodes are estimated in the previous phase as d
01
=
5, d
12
=
56.6, d
13
=
56.6, and d
14
=
40. In this case, the goal is to obtain the estimation errors ε
2
,
ε
3
,
ε
4 and refine d
¯
02, d
¯
03, and d
¯
04.Firstly, two equality constraints as described by (5) and (11) will be determined:
(25)
0
=
f
1
(
ε
2
,
ε
3
,
ε
4
)
0
=
(
-
2.5
ε
2
2
-
2.5
ε
3
2
-
2
ε
4
2
+
3
ε
2
ε
3
+
2
ε
2
ε
4
+
2
ε
3
ε
4
+
16597
ε
2

+
7341
ε
3
+
27262
ε
4
+
14159000
-
2.5
ε
2
2
)

×
(
25600
)
-
1
0
=
f
2
(
ε
2
,
ε
3
,
ε
4
)
0
=
0.25
ε
2
+
0.25
ε
3
+
0.5
ε
4
+
310.6
.To determine the optimal values forε
2
,
ε
3
,
ε
4, the following problem needs to be solved:
(26)
min
⁡
⁡
ε
2
2
+
ε
3
2
+
ε
4
2
s
.
t
.
f
1
(
ε
2
,
ε
3
,
ε
4
)
=
0
s
.
t
.
f
2
(
ε
2
,
ε
3
,
ε
4
)
=
0
.By differentiating the LagrangianH defined in (24), we obtain
(27)
∂
H
∂
ε
2
=
2
ε
2
+
0.25
λ
2
+
λ
1
(
3
25600
ε
3
-
ε
2
5120
+
ε
4
12800
+
0.65
)
=
0
∂
H
∂
ε
3
=
2
ε
3
+
0.25
λ
2
+
λ
1
(
3
25600
ε
2
-
ε
3
5120
+
ε
4
12800
+
0.28
)
=
0
∂
H
∂
ε
4
=
2
ε
4
+
0.5
λ
2
+
λ
1
(
ε
2
12800
+
ε
3
12800
-
ε
4
6400
+
1.06
)
=
0
∂
H
∂
λ
1
=
f
1
(
ε
2
,
ε
3
,
ε
4
)
=
0
,
∂
H
∂
λ
2
=
f
2
(
ε
2
,
ε
3
,
ε
4
)
=
0
.Solving the above five algebraic equations above, we get,(28)
ε
2
*
=
-
67.39
,
ε
3
*
=
-
545.76
,
ε
4
*
=
-
314.59
.Correspondingly, the refined distances between regular noder and the three anchors are
(29)
d
^
02
=
d
¯
02
2
+
ε
2
*
=
55.6
d
^
03
=
d
¯
03
2
+
ε
3
*
=
61.4
d
^
04
=
d
¯
04
2
+
ε
4
*
=
37.6
.As shown in Figure3, “.” represents the regular node, “□” represents the anchor, and the radius of the circle is the estimated distance between the regular node and the anchor. In Figure 3(b), the three circles intersect in one point, which proves that the refined distances satisfy the geometric constraints.Locations of anchors and the regular node.
(a)
Performance of noisy distances
(b)
Performance of refined distances(D) Localization. So far, regular nodes have known the refined distances to the anchors according to (29). Based on the above refinement scheme, we know that the refined distances satisfy the geometric constraints. Localization can be carried out by the least square method. r
(
x
,
y
) represents the regular node, a
(
x
i
,
y
i
) (i
=
2,3
,
4) represent the locations of the anchors, and d
^
02
,
d
^
03
,
d
^
04 represent the refined distances between the regular node and the anchors. The coordinate of the regular node can be estimated by
(30)
X
^
=
(
A
T
A
)
-
1
A
T
b
,
where
(31)
A
=
(
2
(
x
2
-
x
4
)
2
(
y
2
-
y
4
)
2
(
x
3
-
x
4
)
2
(
y
3
-
y
4
)
)
,
X
=
(
x
y
)
b
=
(
x
2
2
-
x
4
2
+
y
2
2
-
y
4
2
+
d
^
04
2
-
d
^
02
2
x
3
2
-
x
4
2
+
y
3
2
-
y
4
2
+
d
^
04
2
-
d
^
03
2
)
.Figure4 illustrates the localization of the computational example above with both noisy and refined distances. “*” represents the calculated location. The localization errors in Figures 4(a) and 4(b) are 0.67 m and 0.55 m, respectively.Localization effect of noisy distances and refined distances.
(a)
Localization with noisy distances
(b)
Localization with refined distances


## 4.2. Communication Cost Analysis

For energy cost of NCA-DL, the communication consumption is mainly considered in the distance estimation and refinement phases.n represents the number of the sensors and n
A represents the number of the anchors. Then for the two flooding processes in the distance estimation phase, it gives a bound of O
(
2
×
n
A
×
n
) to the communication cost in this process. While in the refinement phase, each node needs to communicate with its neighbors so the communication cost is O
(
n
). The total communication complexity is O
(
n
×
(
2
×
n
A
+
1
)
). It is known that the communication complexity of DV-Hop is O
(
2
×
n
A
×
n
). Since the method proposed in [20] is just to refine distance estimations with additional calculation, its communication complexity is the same as DV-Hop. So the cost of NCA-DL is in the same order of magnitude as other algorithms while it can largely improve the localization performance.


## 5. Numerical Results

This section we will describe the implementation of the NCA-DL algorithm and evaluate its performance through extensive simulations. The results obtained from these simulations will focus on analysing the distance estimation errors and localization errors and further compare results obtained by NCA-DL, DV-Hop, robust position, and the method proposed in [20] which have been mentioned above.


### 5.1. Simulation Configuration

The basic network setup area is considered to be a 100 m × 100 m square field. The communication radius of the nodes is set to 10 m. In our simulations, sensor nodes are deployed using two models: (i) random placement and (ii) perturbed grid. In the random placement model, sensor nodes are randomly deployed in the network by dropping from an airplane or some other methods. In this case, the topology of the network is likely to be irregular. In the second model, nodes are deployed using perturbed grid where the nodes are perturbed with a random shift from grid. In this situation, nodes will tend to uniformly occupy the field avoiding large concentration of nodes, which also guarantee the regularity of the topology of the network.In all cases, regular nodes have the ability of ranging and the results are averaged over 10 trails. The average localization error is defined as follows:(32)
error
=
1
n
∑
i
=
1
n
∥
x
i
-
x
¯
i
∥
×
1
r
,
where n is the number of the regular nodes, x
i is the actual location of regular node i, x
¯
i is the estimated location of regular node i, and r is the communication radius.


### 5.2. NCA-DL Performance

At first, we focus on the distance estimation error between regular nodes and anchors. In this set of simulations, we varied the number of the nodes (avg. degree) from 124 (4.8) to 628 (14.2). The number of the anchors is set to 3. The average distance estimation errors obtained from these simulations are stated in Table1.Table 1
Average distance estimation error.
Number of nodes(Avg. degree)
Avg. distance estimation error (m)
Random placement
Perturbed grid
DV-Hop
NCA-DL
DV-Hop
NCA-DL
124 (4.8)
12.32
6.13
6.15
4.51
147 (5.8)
8.28
4.70
4.01
2.38
203 (7.5)
5.43
3.71
3.92
2.17
403 (11.1)
3.39
2.35
2.99
1.55
628 (14.2)
3.06
2.04
2.72
1.35As indicated in Table1, we can observe that the distance estimation error of both DV-Hop and NCA-DL under perturbed gird deployment is smaller than that of these two algorithms under random placement. With the increase of the number of nodes (avg. degree), both DV-Hop and NCA-DL can improve the ranging effectiveness. Moreover, DV-Hop suffers large ranging error when the average degree is low while NCA-DL has smaller errors for divers network scales.Now, it has been proved that the NCA-DL algorithm can significantly decrease the distance estimation errors with the help of a collaborating neighbor; both initial deployment model conditions were therefore simulated in order to graphically verify their respective localization performance.Figure5 exemplifies the distance estimation and localization error of NCA-DL against number of nodes in both deployment models. It is demonstrated that the distance estimation error in NCA-DL can be decreased with the increase of the number of nodes. As shown in Figure 5(b), the localization error decreases more obviously when the distance estimation error drops below a critical value (around 2 m).Distance estimation and localization error of NCA-DL.
(a)
Random placement model
(b)
Perturbed grid modelFigure6 exemplifies the localization performance of DV-Hop and NCA-DL. “Δ” represents the anchors, “.” represents the true location, “*” represents the calculated location, and the line between them represents the localization error. In this set of simulations, the number of deployed nodes (avg. degree) is set to 403 (11.1) and the number of the anchors is set to 3. According to the definition of localization error in (32), in the random placement deployment, the average localization error resulting form DV-Hop is around 66% while the error goes down to around 46% in perturbed grid deployment, as shown in Figures 6(a) and 6(c). In Figures 6(b) and 6(d), we can see that NCA-DL decreases the localization error to 38% and 23%, respectively, in the two deployment models. In general, NCA-DL can increase the localization precision about 40% compared with DV-Hop under such network environment.Localization effect in both deployment models.
(a)
DV-Hop in random placement
(b)
NCA-DL in random placement
(c)
DV-Hop in perturbed grid
(d)
NCA-DL in perturbed gridFigure7 illustrates the localization error in both random placement and perturbed grid models. Compared with the other algorithms, NCA-DL has much lower localization error. With the increase of number of nodes, the performance of all the algorithms upgrades. It is also demonstrated that the NCA-DL algorithm can achieve high localization precision in the perturbed grid deployment model when the density of sensors is high, as shown by Figure 7(b).Localization error against number of nodes.
(a)
Random placement model
(b)
Perturbed grid model


## 5.1. Simulation Configuration

The basic network setup area is considered to be a 100 m × 100 m square field. The communication radius of the nodes is set to 10 m. In our simulations, sensor nodes are deployed using two models: (i) random placement and (ii) perturbed grid. In the random placement model, sensor nodes are randomly deployed in the network by dropping from an airplane or some other methods. In this case, the topology of the network is likely to be irregular. In the second model, nodes are deployed using perturbed grid where the nodes are perturbed with a random shift from grid. In this situation, nodes will tend to uniformly occupy the field avoiding large concentration of nodes, which also guarantee the regularity of the topology of the network.In all cases, regular nodes have the ability of ranging and the results are averaged over 10 trails. The average localization error is defined as follows:(32)
error
=
1
n
∑
i
=
1
n
∥
x
i
-
x
¯
i
∥
×
1
r
,
where n is the number of the regular nodes, x
i is the actual location of regular node i, x
¯
i is the estimated location of regular node i, and r is the communication radius.


## 5.2. NCA-DL Performance

At first, we focus on the distance estimation error between regular nodes and anchors. In this set of simulations, we varied the number of the nodes (avg. degree) from 124 (4.8) to 628 (14.2). The number of the anchors is set to 3. The average distance estimation errors obtained from these simulations are stated in Table1.Table 1
Average distance estimation error.
Number of nodes(Avg. degree)
Avg. distance estimation error (m)
Random placement
Perturbed grid
DV-Hop
NCA-DL
DV-Hop
NCA-DL
124 (4.8)
12.32
6.13
6.15
4.51
147 (5.8)
8.28
4.70
4.01
2.38
203 (7.5)
5.43
3.71
3.92
2.17
403 (11.1)
3.39
2.35
2.99
1.55
628 (14.2)
3.06
2.04
2.72
1.35As indicated in Table1, we can observe that the distance estimation error of both DV-Hop and NCA-DL under perturbed gird deployment is smaller than that of these two algorithms under random placement. With the increase of the number of nodes (avg. degree), both DV-Hop and NCA-DL can improve the ranging effectiveness. Moreover, DV-Hop suffers large ranging error when the average degree is low while NCA-DL has smaller errors for divers network scales.Now, it has been proved that the NCA-DL algorithm can significantly decrease the distance estimation errors with the help of a collaborating neighbor; both initial deployment model conditions were therefore simulated in order to graphically verify their respective localization performance.Figure5 exemplifies the distance estimation and localization error of NCA-DL against number of nodes in both deployment models. It is demonstrated that the distance estimation error in NCA-DL can be decreased with the increase of the number of nodes. As shown in Figure 5(b), the localization error decreases more obviously when the distance estimation error drops below a critical value (around 2 m).Distance estimation and localization error of NCA-DL.
(a)
Random placement model
(b)
Perturbed grid modelFigure6 exemplifies the localization performance of DV-Hop and NCA-DL. “Δ” represents the anchors, “.” represents the true location, “*” represents the calculated location, and the line between them represents the localization error. In this set of simulations, the number of deployed nodes (avg. degree) is set to 403 (11.1) and the number of the anchors is set to 3. According to the definition of localization error in (32), in the random placement deployment, the average localization error resulting form DV-Hop is around 66% while the error goes down to around 46% in perturbed grid deployment, as shown in Figures 6(a) and 6(c). In Figures 6(b) and 6(d), we can see that NCA-DL decreases the localization error to 38% and 23%, respectively, in the two deployment models. In general, NCA-DL can increase the localization precision about 40% compared with DV-Hop under such network environment.Localization effect in both deployment models.
(a)
DV-Hop in random placement
(b)
NCA-DL in random placement
(c)
DV-Hop in perturbed grid
(d)
NCA-DL in perturbed gridFigure7 illustrates the localization error in both random placement and perturbed grid models. Compared with the other algorithms, NCA-DL has much lower localization error. With the increase of number of nodes, the performance of all the algorithms upgrades. It is also demonstrated that the NCA-DL algorithm can achieve high localization precision in the perturbed grid deployment model when the density of sensors is high, as shown by Figure 7(b).Localization error against number of nodes.
(a)
Random placement model
(b)
Perturbed grid model


## 6. Conclusions

Location information of sensors is vital in wireless sensor networks. In this paper, a novel distributed localization algorithm called NCA-DL is proposed, which introduces theCayley-Menger determinant as an important tool for formulating the distances between pairs of regular nodes and anchors to algebraic constraints. In NCA-DL, an adjacent neighbor is chosen for each regular node to establish constraint equations. Then the imprecise distances can be refined by using these constraints and an appropriate objective function. Finally, the localization precision is improved.The set of numerical simulations carried out to validate this method demonstrate the scalability of NCA-DL over a range of node numbers. Comparisons have been performed with other known localization algorithms, which show that NCA-DL can largely reduce the localization errors displayed by existing methods. In the considered sensor network cases initialized under random deployment conditions, the NCA-DL algorithm has proven to increase the localization precision by up to 30% compared with the method proposed in [20] and 40% compared with DV-Hop.



---

*Source: 143938-2014-06-22.xml*