ñòð. 46 |

B 2 = A 2 + C 2 âˆ’ 2 BC cos(b)

Cosines Rule:

c

B A 2 = B 2 + C 2 âˆ’ 2 BC cos(a)

(c)

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.

8.3 LOCATION DISCOVERY IN THE PRESENCE OF ERRORS

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-

vironment.

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

236 LOCATION DISCOVERY

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,

18].

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

237

8.3 LOCATION DISCOVERY IN THE PRESENCE OF ERRORS

refer to this problem as atomic multilateration, and it can be solved using least squares es-

timation.

2

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

xË†

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:

2

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

where

xi â€“ xu

Ë† yi â€“ yu

Ë†

xi = , yi =

ri ri

(xi â€“ xu)2 + (yi â€“ yu)2

ri = Ë† Ë†

Base Station 1

u

Base Station 3

Base Station 2

Figure 8.2. Example two-dimensional scenario.

238 LOCATION DISCOVERY

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 8.4.2.8. 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)

x

x2 y2

= ,A= and z= 2

r3,u â€“ f (u)

x3 y3

y

3

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

2

x xy

Q0 = 2

xy y

and

22 2

2( â€“ xy)

xy

a2 = (8.4)

2 2 2 22 2 1/2

x+ y â€“ [( xâ€“ y) + 4 xy)]

22 2

2( â€“ xy)

xy

2

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].

239

8.4 AD HOC TECHNIQUES FOR LOCATION DISCOVERY

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

CEP

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 =

r

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

8.4 AD HOC TECHNIQUES FOR LOCATION DISCOVERY

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-

clude:

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-

240 LOCATION DISCOVERY

ñòð. 46 |