Distributed Localization in Sensor Networks with Noisy Distance
Measurements
Fei Wu, Yu-Ping Tian, Bo Wang
School of Automation, Southeast University, Nanjing 210096, Jiangsu, P. R. China
E-mail: w
f email@sina.com, yptian@seu.edu.cn, bowang1988@163.com
Abstract: This paper investigates the distributed localization problem for sensor networks with noisy distance measurements. A
distributed iterative algorithm called ECHO-MN is presented based on the signed barycentric coordinate representation, which
can be calculated by relative distance measurements. The measurement noise model is presented followed by an unbiased
distance estimator which utilizes the past measurement information. Taking advantage of the estimator each sensor node to be
located updates its estimates of internode distances and calculates the barycentric coordinate before localization iteration. To
attenuate the effect of measurement noise, a gain parameter which decay to zero is used in the algorithm. It is proved that ECHO-
MN converges to the exact location of each sensor almost surely under some necessary conditions. Numerical studies illustrate
the proposed localization algorithm.
Key Words: Sensor Network, Distributed Localization, Barycentric Coordinate, Measurements Noise
1 Introduction
Location information of sensor nodes in a wireless sensor
network(WSN) is essential when solving numerous compli-
cated network tasks, such as environment monitoring, target
tracking, intrusion detecting, etc. [1–3]. While in many ap-
plications, for example, sensors in a forest or underwater en-
vironment, the GPS signal is not available for each sensor.
Under these circumstances, developing an efficient localiza-
tion method by utilizing limited resource is necessary.
Existing results on localization can be broadly divided
into centralized and distributed algorithms. In some exist-
ing centralized localization algorithms, [4] uses the maxi-
mum likelihood estimator to achieve the localization, and
[5] presents a multidimensional scaling (MDS) centralized
localization algorithm. However, the amount of communi-
cation and computation near the center node is huge that the
centralized method is not suitable for large-scale networks.
By contrast, the distributed localization algorithms are much
robust and have less communication cost. Up to now, nu-
merous distributed algorithms have been developed to solve
the localization problem. For example, based on gradient
methods, two distributed algorithms are proposed in [6] and
[7], respectively. In [8], a barycentric coordinate based dis-
tributed localization (DILOC) algorithm is presented. This
algorithm requires that all sensor nodes should lie in the con-
vex hull of anchor nodes and each sensor node needs to find
three neighbors such that it lies in the convex hull of these
neighbors. However, in practical scenario, sensors are usual-
ly deployed randomly. Motivated by this consideration, [9]
extends the DILOC algorithm and presents a new distribut-
ed algorithm called Extended Computation scHeme cOor-
dinatate (ECHO). Different from the DILOC algorithm, the
ECHO algorithm uses the signed barycentric coordinate to
achieve the distributed localization and does not require all
sensor nodes lie in the convex hull of anchor nodes.
In practice, various uncertainties can affect the precision
of localization, such as the inaccurate range or bearing mea-
surements. The localization problem with noisy information
This work is supported by National Natural Science Foundation (NNS-
F) of China under Grant 61573105.
has won increasing attention in recent years. When consid-
ering noisy distance measurements, a robust gradient based
localization algorithm is presented in [11], where the local
convergence of the optimal least-square solution can be guar-
anteed. In [12], both range information missing and range
noise are taken into account, and a noise-tolerant localiza-
tion method is given out. However, only a certain degree of
localization accuracy can be guaranteed in these algorithm-
s. [10] extends the DILOC algorithm and develops an al-
gorithm called DILAND algorithm, which can achieve the
accurate localization under measurement noise. However,
the DILAND algorithm also needs to satisfy the same node
deployment condition required by the DILOC algorithm.
In this paper, we consider the distributed localization for
sensor network with noisy distance measurements. Moti-
vated by ECHO algorithm introduced in [9], we intend to
develop a robust and efficient localization algorithm, which
can overcome the influence of measurement noise and reach
the exact position of each sensor. For details, by studying
the noise model we construct a distance estimator to esti-
mate internode distance based on all historical measured da-
ta, which can guarantee that the estimated distance converges
almost surely (a.s.) to the exact distance as t →∞. Then,
a distributed iterative localization algorithm called ECHO-
MN (ECHO with Measurement Noise) is proposed based on
the ECHO algorithm. We further show that the ECHO-MN
algorithm converges to the exact position of each sensor a.s..
The rest of the paper is organized as follows. In Section
2, we briefly introduce some graph notions and recapitulate
the distributed localization algorithm ECHO. Noise model,
localization algorithm and the convergence are given in Sec-
tion 3. We present a detailed proof of our results in Section
4. Section 5 gives some numerical examples to testify the
effectiveness of our algorithm. Finally, conclusion is drawn
in Section 6.
2 Prior Work
2.1 Graph notions
An undirected graph G =(V, E) consists of a non-
empty set V of elements called nodes and a set E of un-
Proceedings of the 36th Chinese Control Conference
Jul
26-28, 2017, Dalian, China
8917