. 46
( 87 .)


B 2 = A 2 + C 2 ’ 2 BC cos(b)
Cosines Rule:
B A 2 = B 2 + C 2 ’ 2 BC cos(a)

Figure 8.1. Geometric methods for location discovery.

ments to landmarks with known locations are required to estimate node locations in two-
dimensional space (four for three-dimensional space). The location of an object lies at the
intersection of three circles with radii equal to the distance between the object and the
landmarks (Figure 8.1a). Alternatively, if one is interested in determining location with a
local frame of reference, then the location can be easily determined using trigonometric
relationships (Figure 8.1b). With angular measurements, position can be determined with
only two reference points (Figure 8.1c). The main problem with these methods is that they
assume ideal noiseless measurements. In reality, this is not the case, however. Transducers
are noisy and several external factors also introduce more sources of error into the mea-
surement system; therefore, the error characteristics of the measurement process need to
be carefully considered before computing node locations.


Location estimation from noisy measurements can be improved if the nature of the error
is known. The types of errors depend on the types of signal used and the surrounding en-

8.3.1 Sources of Error
Multipath Fading and Shadowing. In radio signal strength measurements, multi-
path fading and shadowing causes up to 30“40 dB variation over distances on the order of

half a wavelength. Furthermore, scattering near the receiver will affect AoA measure-
ments, which create problems even when there is a direct line of sight between the receiv-
er and the transmitter. If ToF methods are used, conventional delay estimators based on
correlation are influenced by the presence of multipath fading, which results in a shift in
the peak of the correlation.

Nonline-of-Sight (NLOS). This affects the AoA methods when the AoA from a longer
path is much different from the true AoA. Additionally, in ToF methods, if the direct path
to the receiver is blocked, the NLOS component will make the objects appear further than
they actually are.

Multiple-Access Interference. This is genrally a problem in CDMA systems in
which high-power users may mask the low-power users due to near“far effects. It can also
be a problem in acoustic and ultrasonic systems if transmissions from nearby beacon
nodes collide.

Transducer Calibration Issues. This is the case in systems that use the received sig-
nal strength indicator (RSSI) from low-cost radios to determine range measurements.
Since these systems do not use high-precision precalibrated components, they tend to ex-
hibit significant variation in actual transmit power for the same transmit power level or in
the RSSI measured for the same received signal strength.

Fluctuations in Signal Propagation Speeds. This error is common in acoustic
measurements in which the speed of propagation can be greatly affected by external fac-
tors such as wind and fluctuations in temperature and humidity levels. The errors increase
over long-distance measurements in which the speed of propagation can vary in different
segments of the path. Based on the above errors, a vector of noisy measurements can be
considered as an approximation vector of the real measurement of element X:

X= ( )+E (8.1)

where ( ) is the noiseless measurement vector and E is a random vector with known
probability density function and covariance matrix (see [23] for a more detailed descrip-
tion). The system-measurement model depends on the measurement method used. Two
methods commonly used to deal with the measurement discrepancies when estimating lo-
cations in the presence of errors are least squares (LS) estimation and Bayesian estima-
tion. The former is used when the measurement error distribution is white gaussian,
whereas the latter is used when the error distribution is not gaussian. In this chapter, the
examples illustrate the use of least squares methods for estimating node locations. For ex-
ample location discovery systems that use Bayesian methods, we refer the reader to [5,

8.3.2 Atomic Multilateration
One of the most basic scenarios for estimating location is the one that uses distance mea-
surements to a set of landmarks or beacons. As soon as the measurements are completed,
location is estimated by minimizing the sum of the squares of the residuals between mea-
sured distances and the corresponding distances derived using the location estimates. We

refer to this problem as atomic multilateration, and it can be solved using least squares es-
Considering the two-dimensional scenario in Figure 8.2, the residual f u,i is given by

(xi “ xu)2 + (yi “ yu)2
fu,i = ru,i “ ˆ ˆ (8.2)

where ru,i is the measured distance between node u with unknown location (xu, yu) and
beacon i. Location (ˆ u, yu) represents the estimated position of node x, based on a set of

measurements. The objective function is to calculate a location estimate for node u such
that the residuals between the measured and estimated distances are minimized:

F(xu, yu) = min f u,i

The location of node u in the example scenario can be estimated if at least three dis-
tance measurements from the noncollinear, noncolocated beacons are available.
When these conditions are met, the problem becomes overconstrained, resulting in
three equations, one for each distance measurement and two unknowns [the (xu, yu) coor-
dinates], and the position of node u can be uniquely determined. The solution to this non-
linear optimization problem can be obtained using a suitable gradient-descent method.
One possible method is to linearize the equations by taking the Taylor expansion and then
applying an iterative minimum mean square estimation (MMSE) solution. The linearized
form of the residual from Equation (8.2) is given by

ri,u = f (u) + xi 2
+ yi + O( ) (8.3)
i x y


xi “ xu
ˆ yi “ yu
xi = , yi =
ri ri

(xi “ xu)2 + (yi “ yu)2
ri = ˆ ˆ

Base Station 1
Base Station 3

Base Station 2

Figure 8.2. Example two-dimensional scenario.

and O( 2) denotes the higher-order terms that are excluded from the computation. The
value of f u is given by f u = fi (ˆ u, yu), where xu, yu are some initial estimates for xu, yu. One
xˆ ˆˆ
i i
possible method for obtaining a suitable initial estimate is provided in Section The
equations from these distance measurements can be expressed in matrix form A = z with
r1,u “ f (u)
x1 y1 1
r2,u “ f (u)
x2 y2
= ,A= and z= 2
r3,u “ f (u)
x3 y3

In this form, one can compute using the least squares equation:

= (ATA)“1ATz

in an iterative fashion. At each iteration, provides a correction to the position estimate of
node u, xu = xu + x and yu = yu + y. This process is repeated iteratively until converges
ˆ ˆ ˆ ˆ
to zero. The computation for weighted least squares is similar and includes the error co-
variance matrix R, = [ATR“1A]“1ATR“1z. The associated error covariance matrix Q0 is
given by Q0 = [ATR“1A]“1. This covariance matrix provides the statistics of the final posi-
tion estimates in terms of an error ellipse with semimajor axis a and semiminor axis b.
These are described in [10] as
x xy
Q0 = 2
xy y

22 2
2( “ xy)
a2 = (8.4)
2 2 2 22 2 1/2
x+ y “ [( x“ y) + 4 xy)]

22 2
2( “ xy)
b= (8.5)
2 2 2 22 2 1/2
x+ y + [( x“ y) + 4 xy)]

Subsequent sections in this chapter will use this basic form of atomic multilateration as
a building block for more elaborate ad hoc localization schemes.
Finally, we note that besides least squares, other optimization methods can also be used
to solve the same localization problem. One popular approach is to model the problem as
a mass spring problem. An example of such an approach is described in [12]. In this prob-
lem, distance measurements between nodes are represented as springs having an associat-
ed energy component. The aim of this problem is to find a set of poses such that the sum
of energies for each spring is minimized.

8.3.3 Localization Accuracy Metrics
The accuracy for of the computed mean square error location is typically evaluated by
comparison with the corresponding Cram©r“Rao bound (CR bound). The CR bound is a
classical result from statistics that gives a lower bound on the error covariance matrix for
an unbiased estimate of an estimated parameter. This is obtained by taking the inverse of
the Fisher information matrix as defined in [33]. An example of how this bound is derived
and used can be found in [23].

Other metrics of accuracy are the circular error probability (CEP) and geometric dilu-
tion of precision (GDOP). CEP is a function of the error covariance matrix of estimated
locations that can be approximated by

(3/4) a2 + b2

where a and b are the axes of the error ellipse described in Equations (8.4) and (8.5).
GDOP measures the effect of the geometric configuration of the reference points on the
location estimates and it is defined as the ratio of the rms error in position estimate and
the rms distance measurement error:
2 2 2
+ +
x y z

GDOP is also related to CEP by CEP (0.75 r)GDOP.


The highly dynamic nature of mobile wireless devices calls for the development of local-
ization techniques for ad hoc setups. In many situations, it is very hard to provide for in-
frastructure support that guarantees the availability of beacon nodes or other landmarks at
all times. It is therefore very desirable to develop ad hoc location discovery techniques
that will operate in the same set of dynamic conditions as ad hoc communication proto-
cols. Some setups that motivate the development of ad hoc localization techniques in-

Randomly deployed nodes. In the sensor network domain, it is often the case that
GPS does not work in all places or its use may be prohibitive due to cost and power
requirements. Under these constraints, ad hoc localization techniques are more suit-
able for determining the position of sensor nodes.
Rapid infrastructure installation. In infrastructure settings, there is usually con-
siderable cost and delay associated with the installation and calibration of a local-
ization system. By using ad-hoc location discovery techniques, the system could
self-calibrate, thus reducing cost and delay overheads.
Localization in the presence of obstacles in highly dynamic environments. infra-
structure environments, ad hoc techniques can also play an important role by assist-
ing localization in the presence of obstacles in highly dynamic systems. For exam-
ple, the ultrasonic signals used in many indoor localization systems cannot
penetrate matter and, thus, cannot make measurements if they do not have direct
line of sight with a set of beacons. Ad hoc location discovery techniques can allevi-
ate this problem by allowing the localization of objects using indirect line of sight
measurement information.

8.4.1 Challenges in Ad Hoc Localization Systems
Despite its several advantages, ad hoc location discovery also imposes a new set of chal-
lenges that need to be addressed. First, from an algorithmic perspective, the solution is of-


. 46
( 87 .)