A
DVANCES IN
C
OOPERATIVE
W
IRELESS
N
ETWORKING
Network Localization and
Navigation via Cooperation
Moe Z. Win, Massachusetts Institute of Technology
Andrea Conti, University of Ferrara
Santiago Mazuelas and Yuan Shen, Massachusetts Institute of Technology
Wesley M. Gifford, IBM Thomas J. Watson Research Center
Davide Dardari and Marco Chiani, University of Bologna
A
BSTRACT
Network localization and navigation give rise
to a new paradigm for communications and con-
textual data collection, enabling a variety of new
applications that rely on position information of
mobile nodes (agents). The performance of such
networks can be significantly improved via the
use of cooperation. Therefore, a deep under-
standing of information exchange and coopera-
tion in the network is crucial for the design of
location-aware networks. This article presents an
exploration of cooperative network localization
and navigation from a theoretical foundation to
applications, covering technologies and spatio-
temporal cooperative algorithms.
P
RELIMINARIES AND
A
PPLICATIONS
The availability of real-time high-accuracy loca-
tion-awareness is essential for current and future
wireless applications. Reliable localization and
navigation is a critical component for a diverse
set of applications including logistics, security
tracking, medical services, search and rescue
operations, control of home appliances, automo-
tive safety, and military systems, as well as a
large set of emerging wireless sensor network
(WSN) applications. Other applications that
exploit position information include networking
protocols (geo-routing) and interference avoid-
ance techniques in future cognitive radios. New
market opportunities in real-time location sys-
tem (RTLS) technology have an expected value
of $6 billion in 2017.
1
Network localization and navigation repre-
sent a new paradigm where wireless networks
support data communication, contextual infor-
mation collection, and navigation. The purpose
of such networks is to determine the unknown
positions of agents based on intra- and inter-
node measurements. In conventional approaches
such as the Global Positioning System (GPS),
each agent infers its position using only mea-
surements made with respect to anchors (nodes
1
According to R. Das and
P. Harrop “RFID Fore-
cast, Players and Oppor-
tunities 2007-2017,”
http://www.idtechex.com,
2007.
in the infrastructure with a priori position knowl-
edge). Such systems usually fail in harsh environ-
ments where network coverage is limited and
measurement behavior is highly complex.
Cooperation among peer nodes at the physi-
cal layer improves the performance and extends
the coverage of wireless networks, where nodes
form a virtual array through distributed trans-
mission and signal processing [1]. Recently,
cooperative techniques have been introduced for
localization and navigation to improve the accu-
racy and reliability of position information. Net-
work localization and navigation circumvent the
need for high-power transmitters and high-densi-
ty infrastructure, and offer additional coverage
and improved localization accuracy by enabling
the agents to estimate their positions via cooper-
ation [2–5]. The main components of coopera-
tive location-aware networks involved in RTLS
design are shown in Fig. 1.
The localization and navigation process typi-
cally consists of two phases: (i) a measurement
phase, during which agents make intra- and
inter-node measurements using different sen-
sors; and (ii) a location update phase, during
which agents infer their own positions using an
algorithm that incorporates both prior knowl-
edge of their positions and new measurements.
For instance, an agent can update its position
estimate based on inertial measurements using
an inertial measurement unit (IMU) and dis-
tance measurements with respect to some fixed
anchors using a range measurement unit (RMU).
Localization accuracy strongly depends on the
quality of the measurements, which are affected
by impairments such as network topology, multi-
path propagation, environmental conditions,
interference, noise, and clock drift. In addition
to the underlying technologies used in the mea-
surement phase, localization performance is also
dependent on the specific processing or data
fusion algorithm used in the location-update
phase. Hence, a deep understanding of informa-
tion evolution in different phases of the localiza-
tion process is necessary for the design and
56
0163-6804/11/$25.00 © 2011 IEEE
IEEE Communications Magazine • May 2011
Environmental
monitoring
Navigation
Social networking
Logistics
Applications
Understanding the
fundamentals of
Safety and rescue
network localization
and navigation via
cooperation is
important not only
to provide a
performance
benchmark, but also
to guide algorithm
development and
network design.
Data fusion
Spatio-temporal
cooperation
(localization and
tracking)
Cooperative
location-aware
networks
Inter-node
measurements
(waveform, ranging,
direction)
Intra-node
measurements
(acceleration, angular
velocity, Doppler
effects, orientation)
or
Mobility and
perceptual
models
ith
ms
The
oretical
foundation
Tec
ol
hn
Statistical
inference
Environmental
information
Planning and
infrastructure
Figure 1.
The cycle of cooperative location-aware networks: theoretical foundation and aspects to be con-
sidered for technology, algorithms, and applications.
analysis of localization systems. A theoretical
foundation that addresses these issues is
described later.
The requirements of location-aware networks
are driven by applications. A local performance
metric is the root mean squared error (RMSE)
of position estimates. In particular, the position
estimation error is given by the Euclidean dis-
tance between the estimated position ˆ and the
x
true position
x
as
e(x)
=
⎢
ˆ –
x
⎢
. A global per-
⎢
x
⎢
formance metric evaluated over the entire local-
ization area and time is the localization error
outage (LEO) defined by
P
out
=
P
{e(x) >
e
th
},
where
e
th
is the target (i.e., maximum allowable)
position estimation error, and the probability is
evaluated over the ensemble of all possible spa-
tial positions and time instants. Other require-
ments include localization update rate (i.e., the
number of position estimates computed per sec-
ond) and coverage area of the localization sys-
tem. In particular, localization update rate is
important for navigation (navigation of pedestri-
ans and vehicles typically requires different
localization update rates), which drives algo-
rithm complexity and node cost.
In this article, we provide a snapshot of the
current status of cooperative localization and
navigation technologies, starting from a theoreti-
cal foundation to technological and algorithmic
aspects, respectively. We then conclude this arti-
cle with our remarks.
tion is important not only to provide a perfor-
mance benchmark, but also to guide algorithm
development and network design.
Consider a network with anchors and agents,
where each of the
N
a
agents is equipped with
multiple sensors that can provide intra- and
inter-node measurements (e.g., using IMU and
RMU, respectively) for the purpose of localiza-
tion and navigation. Using these intra- and inter-
node measurements, represented by
z
= [z
self
z
rel
], the agents aim to infer their positions
x
=
[x
1
x
2
⋅⋅⋅
x
N
a
]. The accuracy of location estimates
is inherently limited due to random phenomena
affecting
z,
and fundamental limits of such accu-
racy have been derived using the information
inequality [4].
S
PATIAL
C
OOPERATION
For a static network, or a dynamic network at a
given time instant, only spatial cooperation
among agents can be exploited. By using the
notion of the equivalent Fisher information
matrix (EFIM) [4], the squared position error
for agent
k
is bounded by
⎫
⎧
ˆ
2
≥
tr
⎨⎡
J
e
(
x
)
−
1
⎤ ⎬
,
E
x
k
−
x
k
⎦
x
⎭
(1)
⎩⎣
k
{
T
HEORETICAL
F
OUNDATION
The concept of cooperation has been applied to
WSNs, where distributed sensors work together
to draw a consensus about the environment or to
estimate a spatio-temporal process based on
their local measurements [6]. Analogously, net-
work localization and navigation allow agents to
help each other in estimating their positions,
offering additional benefits such as improved
localization accuracy, resilience to system failure,
increase in coverage, and reduction of cost per
node [2–4]. Understanding the fundamentals of
network localization and navigation via coopera-
where
J
e
(x) is the 2
N
a
×
2
N
a
EFIM for
x
[as
depicted in Fig. 2b],
E{⋅}
and tr{⋅} are the expec-
tation and trace operators, respectively, and [⋅]
x
k
denotes the square submatrix on the diagonal
corresponding to
x
k
. The right side of Eq. 1 is
referred to as the squared position error bound
(SPEB). It can be shown that the EFIM
J
e
(x) is
a sum of two parts, the localization information
from anchors (shown as the block-diagonal
matrices consisting of
Ks
in Fig. 2) and that
from agents’ spatial cooperation (shown as the
structured matrix consisting of
Cs
in Fig. 2).
The basic building blocks of the EFIM
J
e
(x)
represent the localization information between
pairs of nodes in the form
λu
φ
u
T
, where
u
φ
is the
φ
unit vector with direction given by
φ
denoting
the angle from one node to the other, and
λ
is a
positive scalar that characterizes the ranging
information intensity (RII) [4]. The value of
λ
og
y
IEEE Communications Magazine • May 2011
Alg
}
57
The total EFIM con-
sists of two major
components: coop-
eration in space as
well as in time. The
former characterizes
the inter-node
measurements in the
entire network at
each time instant,
and the latter
characterizes the
information from
intra-node measure-
ments and mobility
models at each
individual agent.
K
1
1
–C
1
12
K
1
K
2
K
3
(a)
x
1
z
1
x
2
z
2
x
3
z
3
K
1
–C
12
–C
12
–C
13
K
2
–C
23
K
3
(b)
x
1
z
1
z
12
z
2
z
13
z
23
z
3
Time 2
z
21
x
2
z
31
–C
13
–C
23
z
32
x
3
Time 1
–C
1
–C
1
12
13
K
1
2
–C
1
23
K
1
3
K
2
1
T
12
2
–C
2
12
T
12
1
x
1
T
12
2
T
12
3
–C
2
–C
2
12
13
K
2
2
–C
2
23
K
2
3
(c)
z
1
z
12
z
2
z
13
z
23
z
3
x
1
z
1
z
12
z
21
x
2
z
31
z
13
z
2
z
23
z
3
Time 2
Time 1
z
21
x
2
z
31
–C
1
–C
1
13
23
1
T
12
z
32
x
3
z
11
z
22
z
23
T
12
–C
2
–C
2
3
13
23
z
32
x
3
Figure 2.
EFIM structures and corresponding Bayesian networks for three agents: a) noncooperative local-
ization; b) spatial cooperation; c) spatio-temporal cooperation for two time steps.
depends on the ranging technique as well as the
power and bandwidth of the received waveform,
multipath propagation, and prior statistical chan-
nel knowledge. In particular, the RII is propor-
tional to the square of the effective bandwidth
[4]. Moreover, the localization information from
anchors can be expressed in a canonical form as
a weighted sum of “one-dimensional” informa-
tion from individual anchors; while cooperation
always improves the localization accuracy since it
adds a positive semi-definite matrix to the EFIM
corresponding to noncooperative localization. It
was shown in [4] that the accuracy of localization
is affected by two factors: the quality of point-to-
point measurements, reflected by the expression
of RII, and the network topology, reflected by
the block structure of the matrix
J
e
(x).
In the absence of cooperation, every
C
i,j
corre-
sponding to cooperation between nodes
i
and
j
becomes 0, resulting in a total EFIM
J
e
(x) with
block-diagonal structure, as depicted in Fig. 2a. In
such cases, localization information for different
agents are uncorrelated, and the SPEB can be cal-
culated using only local information at the agents.
navigation. Such information is characterized by
T
matrices in the total EFIM
J
e
(x
(1:t)
) as depict-
ed in Fig. 2c, where
x
(1:t)
consists of the positions
of all agents from time 1 to
t.
Consequently, the
SPEB for each agent at a given time instant can
be obtained by a formula similar to Eq. 1.
Some observations can be drawn from the
structure of the EFIM for cooperative naviga-
tion in Fig. 2c. First, the total EFIM consists of
two major components: cooperation in space as
well as in time. The former characterizes the
localization information from inter-node mea-
surements in the entire network at each time
instant (shown as the diagonal 2
N
a
×
2
N
a
block
matrices), and the latter characterizes the infor-
mation from intra-node measurements and
mobility models at each individual agent (shown
as components
T
outside the main block-diago-
nal). Second, since intra-node measurements
and the mobility models for different agents are
independent, the corresponding
T
matrices form
a block diagonal matrix in the upper-right and
lower-left quarter of the total EFIM. Third, the
T
components can be viewed as the temporal
link that connects localization information from
spatial cooperation of the previous time instant
to the current one. If the temporal link is not
available (i.e.,
T
components are zero), the total
EFIM is block diagonal, implying that position
inference is independent from time to time. The
structure of the EFIM for cooperative naviga-
tion allows a recursive method to calculate the
EFIM at each time instant. This view also pro-
vides insights into the information evolution of
spatio-temporal cooperation in cooperative navi-
gation.
S
PATIO
-T
EMPORAL
C
OOPERATION
Building on the understanding of cooperative
localization, we now discuss the case of coopera-
tive navigation where agents in a dynamic net-
work cooperate in both the space and time
domains. For each time instant, the contribution
of cooperation in space is similar to what we
have seen in cooperative localization. In addi-
tion, another layer of cooperation in time,
exploiting intranode measurements and mobility
(dynamic) models, yields new information for
58
IEEE Communications Magazine • May 2011
T
ECHNOLOGICAL
A
SPECTS
This section describes enabling technologies for
network localization and navigation including
network infrastructure, common signal metrics,
and error mitigation techniques.
N
ETWORK
I
NFRASTRUCTURE
GPS is currently the most important and widely
used technology to provide location awareness
around the globe. Through a constellation of
GPS satellites, it provides positioning accuracy
on the order of meters in open outdoor areas,
but fails in harsh operating environments such as
in buildings and urban canyons. In these GPS-
challenged or even GPS-denied environments,
terrestrial localization systems are increasingly
more important. Such systems are currently
based on cellular networks, wireless local area
networks (WLANs), WSNs, and radio frequency
identification (RFID) networks. Each of them
exhibits different performance and has unique
infrastructure requirements. As a case of interest,
in harsh indoor environments, WLANs typically
suffer impairments from surrounding objects
such as furniture and people, whereas narrow-
band sensors and RFIDs typically require high
node density to achieve the desired accuracy and
coverage. Ultra wideband (UWB) technology
offers high ranging accuracy in harsh environ-
ments due to its ability to resolve multipath and
penetrate obstacles [7, 8]. It is expected that
UWB-based localization will play an important
role in future high-definition situation-aware and
RFID networks. In particular, the IEEE
802.15.4a standard is the first to contemplate
both communication and localization with high
levels of availability and sub-meter accuracy.
Network navigation is based on intra- and
inter-node measurements. The specific types of
measurements available depend on the technolo-
gy employed. Examples of intra-node measure-
ments are acceleration, angular velocity, Doppler
shift, and orientation, while inter-node measure-
ments are waveforms, ranges, and directions. For
instance, an IMU gives the distance traveled and
direction for each time interval, while an agent
with wireless transceivers can infer the distance
with respect to its neighbors based on signal
metrics extracted from exchanged radio frequen-
cy (RF) waveforms.
S
IGNAL
M
ETRICS FOR
I
NTER
-N
ODE
M
EASUREMENTS
Network localization can be classified as range-
based, direction-based, and proximity-based
depending on the type of inter-node measure-
ment. Among them, range-based techniques (i.e.,
based on distance estimates) are more suitable
when both localization accuracy and complexity
are under consideration. The two most widely
used ranging techniques are received signal
strength (RSS)-based and time-based systems.
In RSS-based systems, the receiving node
converts the measured RSS into a distance esti-
mate using theoretical and/or empirical path loss
models. The choice of the model strongly affects
the ranging accuracy. A widely used model is
given by
P
r
(d) =
P
0
– 10
γ
log
10
d
+
S,
where
P
r
(d) (dBm) is the received power,
P
0
is the
received power (dBm) at 1 m,
d
(meters) is the
receiver’s distance from the transmitter,
γ
is the
path loss exponent, and
S
(dB) is the large-scale
fading (shadowing) commonly modeled as a
Gaussian random variable with zero mean and
standard deviation
σ
S
. RSS-based ranging suffers
from mismatch between distance and signal
attenuation leading to inaccurate distance esti-
mates, especially in cluttered environments.
In time-based ranging, the distance between a
pair of nodes is estimated by measuring the sig-
nal propagation delay, or time-of-flight (TOF)
τ
f
=
d/c,
where
d
is the distance between the nodes,
_
and
c
is the speed of electromagnetic waves (c ~
3
×
10
8
m/s). This can be accomplished using
one-way time of arrival (TOA), two-way TOA, or
time difference of arrival (TDOA). Time-based
ranging techniques are mainly affected by noise,
multipath propagation, obstacles, interference,
and clock drift. In particular, in dense multipath
channels the first path is often not the strongest,
making TOA estimation challenging. The maxi-
mum likelihood (ML) TOA estimator is known
to be asymptotically efficient since it achieves the
Cramér-Rao bound (CRB) in the high SNR
region. The implementation of ML estimators
usually requires sampling at the Nyquist sampling
rate or higher, which is impractical for wideband
and UWB signals. Thus, TOA estimation tech-
niques relying on the energy collected at sub-
Nyquist rates are receiving significant attention.
Various TOA estimators based on energy
detection and the effects of impairments are
analyzed in [8]. While the CRB is typically used
as a performance benchmark for many estima-
tion problems, it is not accurate at low and mod-
erate SNRs for TOA estimation. Like all
nonlinear estimators, the performance of the
TOA estimator is characterized by the presence
of a threshold effect with distinct SNR regions
(low, medium, and high SNRs) corresponding to
different modes of operation. At low SNRs (a
priori region),
measurements do not provide sig-
nificant additional information, and the mean
square error (MSE) of the estimator is close to
that obtained solely from the a priori informa-
tion about the TOA. At high SNRs (asymptotic
region),
the MSE of the estimator is accurately
described by the CRB. Between these two
extremes, there may be an additional region
(also known as the
transition
or
ambiguity
region)
where the performance is subject to ambiguities
that are not accounted for by the CRB. There-
fore, other bounds, which are more complicated
but tighter than the CRB, have been proposed
in the literature. The Ziv-Zakai bound (ZZB) [8,
9] can be applied to a wider range of SNRs, and
accounts for both ambiguity effects and a priori
information of the parameter to be estimated.
The performance of
network localization
and navigation
depends mainly on
two factors: (1) the
geometric configu-
ration of the system,
and (ii) the quality of
the waveform and
range
measurements.
R
ANGING
E
RROR
M
ITIGATION
The performance of location-aware networks
depends mainly on two factors: (i) the geometric
configuration of the system (i.e., the deployment of
the anchors relative to the agents), and (ii) the
quality of the waveform and range measurements.
The design of such networks requires a clear
understanding of these phenomena through careful
characterization of involved inter-node measure-
IEEE Communications Magazine • May 2011
59
The characterization
of each possible link,
by means of ranging
and waveform
measurements,
enables the system
designer to under-
stand how to har-
ness environmental
knowledge, identify
LOS and NLOS con-
ditions, take advan-
tage of cooperation,
and choose cooper-
ating nodes.
ments. These measurements are corrupted by
propagation conditions caused by the environment;
for example, partial or complete line-of-sight
(LOS) blockage leads to positively biased range
estimates for time-based ranging techniques. The
localization performance can be improved by dis-
carding or refining unreliable range measurements
based on environmental information. In particular,
regardless of the specific range-based localization
algorithm used, the following three-step procedure
can be adopted: (i) calculate the preliminary posi-
tion estimate
x
(1)
from initial range estimates based
ˆ
on measurements; (ii) correct range estimates
based on
x
(1)
by removing biases according to bias
ˆ
models; and (iii) estimate a refined position ˆ
(2)
x
with the corrected range values.
In the absence of environmental information,
ranging refinement can be made based on other
information, such as non-LOS (NLOS) condi-
tion, extracted from the received waveforms. A
variety of techniques have been proposed in the
literature to identify NLOS conditions. The iden-
tification of signal obstruction is mainly accom-
plished by performing a likelihood ratio test
(LRT) on binary (LOS or NLOS) hypotheses.
This requires the extraction of features that are
significantly affected by the propagation condi-
tions from the received waveform. For example,
the NLOS identification technique in [10] is
based on signal features such as root mean square
(RMS) delay-spread, Kurtosis, and mean excess
delay. Other approaches include regression with
support vector machines and Gaussian processes.
The characterization of each possible link, by
means of ranging and waveform measurements,
enables the system designer to understand how
to harness environmental knowledge, identify
LOS and NLOS conditions, take advantage of
cooperation, and choose cooperating nodes.
modeled by a tractable statistical distribution, for
example a Gaussian distribution. Under the
Gaussian assumption the MMSE and MAP esti-
mators for an agent’s position x coincide and are
the solution of a weighted least squares (WLS)
problem, that is,
ˆ
ˆ
x
MMSE
=
x
MAP
=
arg min
x
2
j
∈
N
b
σ
z
j
∑
1
z
j
−
h
(
x
,
x
j
) ,
2
2
where
N
b
is the set of anchor nodes,
σ
z
j
is the
variance of the noise in each measurement, and
h(x,
x
j
) is a functional of: the distance
⎢
x
–
x
j
⎢
in
⎢
⎢
→
range-based methods, or the angle
∠
xx
j
in direc-
tion-based methods, or both in hybrid schemes.
When the likelihood has a non-Gaussian distri-
bution, the optimization process required for
MMSE and MAP can be complex, in which case
the WLS solution can be used as a tractable sub-
optimal solution.
While each agent determines its belief based
on information obtained from its local measure-
ments in the noncooperative scenario, the local-
ization performance can be improved if agents
incorporate the beliefs of neighbors (spatial
cooperation) and the beliefs obtained in the past
(temporal cooperation).
S
PATIAL
C
OOPERATION
In this setting, a centralized processor can
update the joint belief of all agents by using all
the measurements as well as the prior joint
belief. However, the process of belief updates
and inference is highly complex and inefficient
for the following reasons:
• The joint positional belief of all agents is a
high dimensional distribution.
• The overhead needed to transmit all mea-
surements to a central processor and to
communicate estimated positions back to
agents require an unacceptable usage of
resources.
Furthermore, the centralized solution is not
robust against failure. For these reasons, dis-
tributed algorithms for cooperative localization
are attractive. In a cooperative setting, inferred
node positions are correlated; this fact is evi-
dent from the non-diagonal structure of the
EFIM and the presence of cycles in the
Bayesian network (Fig. 2b). Thus, distributed
algorithms for cooperative localization cannot
achieve the CRB.
A common method to implement distributed
algorithms for cooperative localization is by
means of loopy belief propagation (LBP) [2].
These algorithms assume the positional beliefs
are independent and propagate the beliefs of
each agent through the cooperative network in
an iterative fashion based on the sum-product
algorithm. In the algorithm, the sums (integrals)
and products perform marginalizations and
Bayes’ rule updates, respectively.
An example of two agents in cooperation for
localization is shown in Fig. 3, describing the
position errors before and after cooperation. The
red and blue ellipses in Figs. 3a and 3c represent
the agents’ localization information and errors,
respectively; and the contours in Figs. 3b and 3d
represent the agents’ positional beliefs. As the
L
OCALIZATION AND
N
AVIGATION
A
LGORITHMS
The task of network localization and navigation
algorithms is to determine positions from mea-
surements (observations) and prior knowledge.
From a Bayesian perspective, this task amounts
to determining the posterior distribution
p(x|z),
also referred to as the positional belief. Once this
belief is obtained, point estimates can be com-
puted by determining the mean or mode, leading
to minimum mean square error (MMSE) or max-
imum
a posteriori
(MAP) estimates, respectively.
The primary tools for obtaining such posterior
distributions from measurements and prior
knowledge are Bayes’ rule and marginalization.
Bayes’ rule serves to update beliefs based on new
observations, while marginalization reduces the
dimension of the inference problem.
In noncooperative localization, each agent
individually determines its position by using the
measurements obtained only from anchors (see
the top-right corner in Fig. 2). Each agent can
then independently update its own belief by
using the above mentioned Bayes’ rule and the
likelihood of its position based on new measure-
ments. The belief update as well as the MMSE
or MAP position estimators are easy to deter-
mine when the likelihood can be accurately
60
IEEE Communications Magazine • May 2011
京公网安备 11010802033920号
Copyright © 2005-2024 EEWORLD.com.cn, Inc. All rights reserved
评论