[AliandH.

Nima
Sayed, Alireza Tarighat,
Khajehnouri]

© DIGITALVISION

Network-Based
Wireless Location
[Challenges faced in developing techniques
for accurate wireless location information]

W
ireless location refers to the geographic coordinates of a mobile subscriber in
cellular or wireless local area network (WLAN) environments. Wireless loca-
tion finding has emerged as an essential public safety feature of cellular sys-
tems in response to an order issued by the Federal Communications
Commission (FCC) in 1996. The order mandated all wireless service providers
to deliver accurate location information of an emergency 911 (E-911) caller to public safety
answering points (PSAPs). The FCC mandate aims to solve a serious public safety problem caused
by the fact that, at present, a large proportion of all 911 calls originate from mobile phones, the
location of which cannot be determined with existing technology. However, many difficulties
intrinsic to the wireless environment make meeting the FCC objective challenging; these chal-
lenges include channel fading, low signal-to-noise ratios (SNRs), multiuser interference, and mul-
tipath conditions. In addition to emergency services, there are many other applications for wireless
location technology, including monitoring and tracking for security reasons, location sensitive
billing, fraud protection, asset tracking, fleet management, intelligent transportation systems,
mobile yellow pages, and even cellular system design and management. This article provides an
overview of wireless location challenges and techniques with a special focus on network-based
technologies and applications.

IEEE SIGNAL PROCESSING MAGAZINE [24] JULY 2005 1053-5888/05/$20.00©2005IEEE

WIRELESS NETWORKS
[TABLE 1] LIST OF ACRONYMS.
Wireless networks are primarily designed for voice and data
communications. The widespread availability of wireless nodes, ACRONYMS DESCRIPTION
2G SECOND GENERATION OF MOBILE SYSTEMS
however, makes it possible to utilize these networks for wireless 3G THIRD GENERATION OF MOBILE SYSTEMS
location purposes as well. It is expected that location-based AOA ANGLE OF ARRIVAL
AP ACCESS POINT
applications will play an important role in future wireless mar- AMPOA AMPLITUDE OF ARRIVAL
kets. While location services are now driven by emergency and BS BASE STATION
CDMA CODE DIVISION MULTIPLE ACCESS
security requirements imposed on the wireless networks, in the E911 ENHANCED 911
future they will be driven by commercial demands for location- FCC FEDERAL COMMUNICATIONS COMMISSION
GPS GLOBAL POSITIONING SYSTEM
motivated products. Increasingly, application-level software will LBS LOCATION BASED SERVICES
incorporate location information into its features to fully utilize ML MAXIMUM LIKELIHOOD
MS MOBILE STATION
such information once it becomes available. For example, asset NLOS NON-LINE-OF-SIGHT
tracking and management software would incorporate location PDA PERSONAL DIGITAL ASSISTANT
PSAP PUBLIC SAFETY ANSWERING POINT
information into a database for enhanced tracking capabilities. rms ROOT MEAN SQUARE
As such, wireless location information will add a new dimension SINR SIGNAL-TO-INTERFERENCE-NOISE RATIO
SNR SIGNAL-TO-NOISE RATIO
to future applications. TDOA TIME DIFFERENCE OF ARRIVAL
Wireless networking devices constitute the main infrastruc- TOA TIME OF ARRIVAL
UMTS UNIVERSAL MOBILE TELECOMMUNICATIONS SYSTEM
ture to be utilized for wireless location finding. A location find- WCDMA WIDEBAND CODE DIVISION MULTIPLE ACCESS
ing system should be able to seamlessly use both cellular and WLAN WIRELESS LOCAL AREA NETWORK
WLANs for location finding by roaming between the networks.
The result would be transparent location coverage for both out- within five years from the effective date of the order, 1
door and indoor environments. Today, the main commercially October 1996 (a deadline that is now well passed), wireless
deployed wireless location finding system is linked to the cellu- service providers must convey to the PSAP the location of
lar network in response to requirements by the FCC for emer- the MS within 100 m of its actual location for at least 67%
gency 911 calls made through cell phones. These requirements of all wireless E911 calls. (The original FCC requirement
are collectively known as the enhanced 911 (E911) mandate. was 125 m and was later tightened to 100 m.) This FCC
The details of the FCC requirements for E911 will be discussed. mandate has motivated considerable research efforts
The purpose of this article is to provide an overview of the towards developing accurate wireless location algorithms
basic challenges facing the wireless techniques that are being for cellular networks and has led to significant enhance-
developed for accurate location information. We start with an ments to the wireless location technology (see, e.g.,
overview of the main applications that serve as the major driving [12]–[25]). According to the latest FCC rules, the new man-
force behind the technology. date and accuracy requirements will be enforced in 2005.
For ease of reference, Table 1 collects the acronyms that are Although the FCC does not have a specific order for indoor
common in this field and used extensively in subsequent sections. environments, a location capability coverage for both indoor
and outdoor emergency situations is desirable.
APPLICATIONS ■ Mobile advertising: Location-specific advertising and mar-
Figure 1 illustrates some of the available market forecasts for keting will benefit once the location information becomes
wireless location technology [1], [2]. It is estimated that loca- available. For example, stores will be able to track customer
tion-based services (LBSs) will generate annual revenues of the locations and attract them by flashing customized coupons
order of US$15 billion worldwide. In the United States alone, on customers’ wireless devices [14]. In addition, a cellular
about 170 million mobile subscribers are expected to become phone or a personal digital assistant (PDA) could act as a
covered by the FCC-mandated location accuracy for emergency handy mobile yellow pages on demand.
services. To illustrate the potential of LBS, we will now provide a
partial list of applications that will be enhanced using wireless
location information [3]. Location-Based Services Estimated
■ E911: Currently, a high percentage of E911 calls originate Annual Revenues for 2006/2007 (US $B)
from mobile phones; the percentage is estimated at one
US$3.3B
third of all 911 calls (170,000 a day) [5], [6]. These wireless US$11.7B
E911 calls do not receive the same quality of emergency
assistance that fixed-network 911 calls enjoy. This is due to
the unknown location of the wireless E911 caller. To face
this problem, the FCC issued an order on 12 July 1996 [5],
US Others
requiring all wireless service providers to report accurate
mobile station (MS) location information to the E911 opera-
tor at the PSAP. In the FCC order, it was mandated that [FIG1] Forecast revenues for location-based services [1], [2].

IEEE SIGNAL PROCESSING MAGAZINE [25] JULY 2005

 α3
46-
E 148 46-
P 147 J
H G F
TOA/AOA r3 r19 N r
3
Estimator C M 46- K
BS3 (x3, y3) MS L 127W
α2 A B M
r2 44- K
128 J N
r1 C D
TOA/AOA A 46-
Estimator 44- 127H 46- 46- Data Fusion
α1 123 B 127 121A
46- B Center
BS2 (x2, y2) 127 B C D E F
A A B C D 46- C
A 121
TOA/AOA r2 r4
Estimator E
43- 46- D
BS1 (x1, y1) 116 132 K
Data Fusion
J F
Center
T I G

(a) (b)

[FIG2] Network-based wireless location finding. (a) Outdoor environment using a cellular network. (b) Indoor environment using a
WLAN.

■ Asset tracking (indoor/outdoor): Wireless location technol- some base stations (BSs) or from the global positioning system
ogy can also assist in advanced public safety applications, (GPS). In GPS-based estimations, the MS receives and measures
such as locating and retrieving lost children, patients, or the signal parameters from at least four satellites of the current
pets. In addition, wireless location technology can be used to network of 24 GPS satellites. The parameter measured by the MS
track personnel/assets in a hospital or a manufacturing site for each satellite is the time the satellite signal takes to reach the
to provide more efficient management of assets and person- MS. GPS systems have a relatively high degree of accuracy, and
nel. One could also consider applications such as smart and they also provide global location information. There is also a
interactive tour guides, smart shopping guides that direct hybrid technique that uses both the GPS technology and the cel-
shoppers based on their location in a store, and traffic con- lular infrastructure. In this case, the cellular network is used to
trols in parking structures that guide cars to free parking aid the GPS receiver embedded in the mobile handset for
slots. Department stores, enterprises, hospitals, manufactur- improved accuracy and/or acquisition time [15].
ing sites, malls, museums, and campuses are some of the Still, embedding a GPS receiver into mobile devices leads to
potential end users to benefit from the technology. increased cost, size, and battery consumption. It also requires
■ Fleet management: Many fleet operators, such as police the replacement of millions of mobile handsets that are already
forces, emergency vehicles, and other services like shuttle and on the market. In addition, the accuracy of GPS measurements
taxi companies, can make use of the wireless location technolo- degrades in urban environments as well as inside buildings. For
gy to track and operate their vehicles in an efficient manner to these reasons, some wireless service providers may be unwilling
minimize response times. In addition, a large number of driv- to embrace GPS fully as the sole location technology.
ers on roads and highways carry cellular phones while driving. Network-based location technology, on the other hand, relies on
The wireless location technology can help track these phones, some existing networks (either cellular or WLAN) to determine the
thus transforming them into sources of real-time traffic infor- position of a mobile user by measuring its signal parameters when
mation that can be used to enhance transportation safety. received at the network BSs. In this technology, the BSs measure
■ Location-based wireless access security: New location- the signals transmitted from an MS and relay them to a central site
based wireless security schemes can be developed to height- for further processing and data fusion to provide an estimate of the
en wireless network security and avoid the interception of MS location. A significant advantage of network-based techniques is
digital information. By using location information, only peo- that the MS is not involved in the location-finding process; thus,
ple at specific physical areas could access certain files or the technology does not require modifications to existing handsets.
databases through a WLAN. However, unlike GPS location systems, many aspects of network-
■ Location sensitive billing: Using the location information based location are not yet fully studied.
of wireless users, wireless service providers can offer variable- The rest of this article focuses on network-based wireless
rate call plans or services that are based on the caller location. location. For location estimation, two operations must be per-
formed at the BSs. The BSs have to measure some signal param-
MOBILE-BASED VERSUS NETWORK-BASED TECHNIQUES eters (such as the time or the angle of arrival) of the received MS
Wireless location technologies fall into two main categories: signals. Then, the measured signal parameters are combined in a
mobile based and network based. In mobile-based location sys- data fusion stage to provide the final estimate for location. Both
tems, the MS determines its location from signals received from of these stages are discussed in the following sections. Figure 2

IEEE SIGNAL PROCESSING MAGAZINE [26] JULY 2005

illustrates this two-stage procedure (measurement and data [12]. Although this method helps resolve the ambiguity
fusion) for an outdoor environment using a cellular network and between the two solutions resulting from (2) and (3), it does
for an indoor environment using a WLAN. Although the focus of not combine the third measurement r3 in an optimal man-
the article is on network-based location systems, most of the net- ner. Furthermore, it is not possible in this way to combine
work-based location algorithms presented here can be used at TOA measurements from more than three BSs (which would
the MS as well. Therefore, from now on, network-based wireless be useful when the measurements {ri } are subject to inaccu-
location will simply be referred to as wireless location. racies and noise).
This issue can be addressed by combining all the available
DATA FUSION METHODS measurements using a least-squares solution as follows (alterna-
The data fusion step combines measurements from different tive techniques such as maximum likelihood (ML) solution can
BSs to obtain an estimate of the MS location. Let (xm , ym ) be found, e.g, in [49], [50]). Subtracting (2) from (3) gives
denote the MS location coordinates in a Cartesian coordinate
system. Let the coordinates of three BSs (BS1 , BS2 , and BS3 ) r22 − r21 = x22 − 2x2 xm + y22 − 2y2 ym .
be denoted by (x1 , y1 ), (x2 , y2 ), and (x3 , y3 ), respectively. For
simplicity of presentation, only the x and y coordinates are Similarly, subtracting (2) from (4) gives
considered in the derivations and the z coordinate is ignored.
This corresponds to a case where the BSs and the mobile user r23 − r21 = x23 − 2x3 xm + y23 − 2y3 ym .
are located on a relatively flat plane. Without loss of generality,
the origin of the Cartesian coordinate system is set at BS1 , i.e., Rearranging terms, the above two equations can be written
(x1 , y1 ) = (0, 0). Several data fusion techniques have been in matrix form as
introduced in the literature; these techniques depend on what
  
 2 
signal parameters are measured at the BSs [3], [4]. (These are x2 y2 xm K2 − r22 + r21
  1
=  ,
several studies in the literature that compare the performance (5)
2 2 2 2
of different fusion algorithms, e.g. [26], [27].) The most com- x3 y3 ym K3 − r3 + r1
mon signal parameters are the time, angle, and amplitude of
arrival of the MS signal. where

TIME OF ARRIVAL DATA FUSION Ki2 = x2i + y2i . (6)

The time of arrival (TOA) data fusion method is based on com-
bining estimates of the TOA of the MS signal when arriving at Then, (5) can be rewritten as
three different BSs. Since the wireless signal travels at the
speed of light (c = 3 × 108 m/s), the distance between the MS Hx = b, (7)
and BSi is given by where
   
 2 
ri = (ti − t o)c, (1) x2 y2 xm K2 − r22 + r21
1
H= , x =  , b =  .
2 2 2 2
to
where is the time instant at which the MS begins transmis- x3 y3 ym K3 − r3 + r1
sion and ti is the TOA of the MS signal at BS i . The distances
(r1 , r2 , r3 ) can be used to estimate (xm , ym ) by solving the fol- If more than three TOA measurements are available, it can be
lowing set of equations (see Figure 3): verified that (7) still holds with

r21 =x2m + y2m (2)

r22 2
= (x2 − xm ) + (y2 − ym ) 2
(3)
r23 = (x3 − xm )2 + (y3 − ym )2 . (4)

BS3 r2
Without loss of generality, it can be assumed that r1 < r2 < r3 .
(x3, y3) r BS2
One way to solve this overdetermined nonlinear system of 3
(x2, y2)
equations is as follows. First, (2) and (3) are solved for the MS
two unknowns (xm , ym ) to yield two solutions. As shown in (xm, ym)
r1
Figure 3, (2) and (3) each define a locus on which the MS BS1
must lie. Second, the distance between each of the two possi- (0,0)
ble solutions and the circle given by (4) is calculated. The
solution that results in the shortest distance from the circle
(4) is chosen to be an estimate of the MS location coordinates [FIG3] TOA data fusion using three BSs.

IEEE SIGNAL PROCESSING MAGAZINE [27] JULY 2005

 x y2   K2 − r2 + r2 
1 2 
2 2 2 1
    −x2 xm − y2 ym = r21 r1 + r 21 − K 22 .
   2  2
 x3 y3   K − r2 + r2 
   3 3 1
  1 
H= , b=  . (8) Similarly, (4) leads to
x y4  2  K2 − r2 + r2 
 4   4 
1 2 
   4 1 
    −x3 xm − y3 ym = r31 r1 + r 31 − K32 .
.. .. .. 2
. . .
Rewriting these equations in matrix form gives
In this case, the least-squares solution of (7) is given by ([3], [7])
 −1 Hx = r1 c + d, (11)
x̂ = HT H HT b. (9)
where
It is seen that the TOA data fusion method requires accurate
   2 
synchronization between the BSs and MS clocks so that the −r21 K − r221
1 2
measurements {ri } are adequate approximations for the actual c= , d= .
2 2 2
distances. Many of the current wireless system standards only −r31 K3 − r31
mandate tight timing synchronization among BSs (see, e.g.,
[30]). The MS clock itself might have a drift that can reach a few Equation (11) can be used to solve for x in terms of the
microseconds. This drift directly generates an error in the loca- unknown r1 to yield
tion estimate of the TOA method. In the next subsection we
present a data fusion technique that combines time DOA x = r1 H−1 c + H−1 d. (12)
(TDOA) measurements and helps avoid MS clock synchroniza-
tion errors [3], [31], [34]. Substituting this intermediate result into (2) leads to a quadratic
equation in r1 . Solving for r1 and substituting the positive root
TDOA DATA FUSION back into (12) yields the final solution for x.
The TDOA associated with BSi is ti − t1 ; i.e., it is the difference If more than three BSs are involved in the MS location, (11)
between the TOAs of the MS signal at BS i and BS1 . Now we still holds with
define the distance differences
x y2   −r   K2 − r2 
2 21 2 21

     
ri1 = ri − r1      2 
 x3 y3   −r31   K − r2 
     3 31 
= (ti − t o)c − (t1 − t o)c = (ti − t1 )c. (10)     1 
H= , c =  , d =  
x    2  2 2 
 4 y4   −r41   K4 − r41 
     
Note that these differences are not affected by errors in the MS      
.. .. .. ..
clock time (t o ) as it cancels out when subtracting two TOA . . . .
measurements. (3) can be rewritten in terms of the TDOA meas-
urement r21 as which yields the following least-squares intermediate solution
 −1
(r21 + r1 )2 = K22 − 2x2 xm − 2y2 ym + r21 . x̂ = HT H HT (r1 c + d). (13)

Expanding and rearranging terms gives Combining this intermediate result with (2) again, the final esti-
mate for x is obtained. A more accurate solution can be obtained
as in [32] if the second-order statistics of the TDOA measure-
ment errors are known.
MS (xm,ym)
ANGLE OF ARRIVAL DATA FUSION
r2 At the BS, angle of arrival (AOA) estimates can be obtained
r1
using an antenna array. The direction of arrival of the MS sig-
r1 sin α1

r2 sin α2

nal can be calculated by measuring the phase difference

(x1, y1) (x2, y2) between the antenna array elements or by measuring the
α1 α2
power spectral density across the antenna array in what is
BS BS
known as beamforming (see, e.g., [37] and the references
r1 cos α1 r1 cos α2 therein). By combining the AOA estimates of two BSs, an esti-
mate of the MS position can be obtained (see Figure 4). The
[FIG4] Combining AOA measurements. number of BSs needed for the location process is less than that

IEEE SIGNAL PROCESSING MAGAZINE [28] JULY 2005

of the TOA and TDOA meth- the angular orientation of
ods. Another advantage of A LARGE PROPORTION OF ALL 911 the installed antenna
AOA location methods is CALLS ORIGINATE FROM MOBILE PHONES, arrays. The issue of NLOS
that they do not require BS THE LOCATION OF WHICH SHOULD BE is discussed in another sec-
or MS clock synchroniza- DETERMINED WITH SUFFICIENT ACCURACY. tion. For the error in the
tion. However, one disad- angular orientation of the
vantage of the AOA method antenna arrays, some test
is that antenna array structures do not currently exist in sec- measurements can be conducted to calibrate the orientation
ond generation (2G) cellular systems. Still, the use of antenna of the antenna array.
arrays is planned in third generation (3G) cellular systems,
such as UMTS and cdma2000 networks [38], [39]. HYBRID DATA FUSION TECHNIQUES
More generally, assume n BSs estimate the AOA of the MS In TOA, TDOA, and AOA methods, two or more BSs are involved
signal, and the goal is to combine these measurements to esti- in the MS location process. In situations where the MS is much
mate the MS location. As indicated in Figure 4, let α2 denote the closer to one BS (serving site) than the other BSs, the accuracy
AOA of the MS signal at BS2 . Then of these methods can be degraded due to the relatively low SNR
of the received MS signal at one or more BSs. The accuracy is


 further reduced if some type of power control is used, since this
xm r cos α1
= 1 requires that the MS reduce its transmitted power when it
ym r1 sin α1
approaches a BS. In these cases, an alternate data fusion proce-
dure is used to obtain AOA estimates and combine them with
and TOA estimates (see, e.g., [40]). In real scenarios, the accuracy of



 TOA and AOA estimates is usually a function of the environ-
xm x2 r cos α2
= + 2 . ment. For example, in rural areas, AOA measurements can be
ym y2 r2 sin α2
more accurate than TOA measurements if a large-size antenna
array is deployed. On the other hand, TOA measurements are
Likewise, for any other BS i , more accurate than AOA measurements if the BS antenna array
is surrounded by many scatterers. The following is a simple two-



 step hybrid least-squares procedure. Assume n BSs estimate the
xm xi r cos α i
= + i . AOA and TOA of the MS. From (9), the least-squares estimate of
ym yi ri sin α i
(xm , ym ) using TOA measurements is given by

Collecting these relations into a single equation yields

xm −1
= HTTOA HTOA HTTOA bTOA , (16)
ym TOA
Hx = b,
where
where x y2   K2 − r2 + r2 
2 2 2 1
   
1 0  r cos α     2 
1 1  x3 y3   K − r2 + r2 
   3 3 1
0 1  r1 sin α1    1 
    HTOA = , bTOA =  
     .. ..  2 .. 
1 0  x2 + r2 cos α2   . .   . 
 
      
0 1 xm  y2 + r2 sin α2     

H=    . (14)
 , x = ym , b =  
 .. ..   ..  xn yn Kn2 − r2n + r21
. .  . 
   
    and
1 0  x + r cos α 
n n n
0 1 yn + rn sin αn Ki2 = x2i + y2i .

The least-squares solution for x is then Likewise, from (15), the least-squares estimate of (xm , ym )
using only AOA measurements is given by
−1
x̂ = HT H HT b. (15)


xm −1
= HTAOA HAOA HTAOA bAOA (17)
ym AOA
Besides the regular sources of error in AOA measurements,
such as noise and interference, AOA measurements can be
corrupted by non-line-of-sight (NLOS) effects and errors in where

IEEE SIGNAL PROCESSING MAGAZINE [29] JULY 2005

 1 0  r1 cos α1 
measurements α i are corrupted by NLOS effects and by noise.
0 1  r1 sin α1
 Hence, the available measurements are
   
   
1 0  x2 + r2 cos α2 
    ᾱ i =α i + vα i
0 1  y2 + r2 sin α2 
HAOA =

,
 bAOA =

.
 (18) r̄i =ri + vri (20)
 .. ..   .. 
. .  . 
   
    where vα i and vri represent the corruptions to α i and ri . One
1 0  x + r cos α 
n n n scheme for recovering (xm , ym ) from the measurements
0 1 yn + rn sin αn {r̄i , ᾱ i } is based on formulating a constrained optimization
problem that reduces the effect of NLOS conditions on loca-
The final location estimate could be taken as a linear combina- tion accuracy. The constraints will be a reflection of the topol-
tion of the two estimates, say as ogy of the cellular network. Thus, consider the cellular system
shown in Figure 5. The constraints are the distances between


 

 
 the BSs, which are given by
xm xm xm
=η + (1 − η) (19)
ym ym TOA ym AOA
r212 =r21 + r22 − 2r1 r2 cos γ1 (21)
r223 =r22 + r23 − 2r2 r3 cos γ2 (22)
where the positive parameter η is chosen depending on the rela- ..
tive accuracy of the TOA and AOA measurements. .
where the angles {γ i } are functions of {α i , θ i }. This formulation
DATA FUSION WITH NLOS CONDITIONS is easily extendable to the case of n BSs. Then, one could pose
An important source of error in TOA-based and AOA-based the problem of estimating the {α i , ri } by solving
data fusion is the case where there is no line-of-sight from the
mobile station to the BSs. A geometrically constrained data n  2  2
ᾱ i − α i r̄i − ri
fusion scheme could be used to reduce the effect of such NLOS {α̂ i , r̂i }ni=1 = arg min + (23)
{α i ,ri }
i=1
σα i σ ri
conditions [41] (see [8] for other ways to exploit the geometry
of the problem). Figure 5 shows a representation of a cellular
system assuming three BSs. Let the θ i denote the angles subject to
induced by the topology of the BSs. Let also rij denote the dis-
tance between the i th and j th BSs. Likewise, the α i denote
the AOAs of the MS signal at the BSs. In practice, the distance r212 = r21 + r22 − 2r1 r2 cos(π − (α1 + α2 ))
measurements ri in (1) are generally corrupted by NLOS off- r223 = r22 + r23 − 2r2 r3 cos(π − (α3 + (θ2 − α2 )))
sets arising from the presence of obstacles between the MS and ..
the BS, as well as by measurement noise. Similarly, the AOA .

where σ r2i is the variance of the distance error and σα2i is the
variance of the angle error (both at the i th BS). There are some
Base Station
known methods for estimating the variances σ r2i and σα2i (see,
Mobile Station
(x3, y3) e.g., [42]–[44]). These methods generally use the time history of
BS3 the signals, or the scattering model of the environment, to esti-
mate the noise variance, as in
r31
γ3 r α3
3 K−1
γ2 1
σ r2i ≈ (r̄i (n) − µ ri )2 , (24)
r1 γ1 K n=0
α1 θ r23
BS1 1 r2

(0,0) θ2 where
r12
α2 K−1
1
µ ri = r̄i (n) (25)
K n=0
BS2
(x2, y2) for K ≈ 400 and where r̄i (n)is the measurement of ri at experi-
ment n. This is also true for σα2i . Minimizing (23) results in esti-
mates of {ri , α i }. Using the equalized values in (8) or (9) will
[FIG5] A schematic of a cellular network topology with three BSs. result in improved location accuracy.

IEEE SIGNAL PROCESSING MAGAZINE [30] JULY 2005

THE WIRELESS ENVIRONMENT assumed initially to be transmitted over a single path fading
From the previous discussion, it is clear that most wireless loca- channel. A total of K measurements r(n) are collected, which
tion methods depend on combining estimates of the TOA and/or are related to s(n) via
AOA of the received signal at different BSs. Estimating the TOA
and amplitude of arrival (AmpOA) of wireless signals has been r(n) = A h(n) s(n − τ o) + v(n), n = {1, . . . , K }, (26)
studied in many works since it
is required in many wireless where v(n) is additive white
system designs for online signal WIRELESS LOCATION TECHNOLOGIES Gaussian noise with variance
decoding purposes. Yet, esti- FALL INTO TWO MAIN CATEGORIES: σv2 , {h(n)} is the fading channel
mating these same parameters MOBILE BASED AND NETWORK BASED. gain, and A is an unknown
for wireless location purposes is amplitude (real value) that
challenging for several reasons. accounts for the gain of the
■ Low SINR conditions. Cellular systems tend to suffer static channel if fading were not present. The autocorrelation
from high multiple access interference levels that function of h(n) is defined as
degrade the SNR of the received signal. Moreover, the
ability to detect the MS signal at multiple BSs is limited Rh(i ) = Eh(n)h∗ (n − i ). (27)
by the use of power control algorithms, which require
the MS to decrease its transmitted power when it Without loss of generality, we will assume that the sequence
approaches the serving BS. This fact, in turn, decreases h(n) has unit variance, i.e., Rh(0) = 1. The ML estimates of
the received MS signal power level at other BSs. In a typi- {τ o, h(n)} are defined by
cal CDMA IS-95 cellular environment, the received SNR
at the serving BS is in the order of −15 dB. However, the
received SNR at BSs other than the serving BS can be as {τ̂ , ĥ(n)} = arg max [P(r(1) · · · r(K)|τ, h(n))], (28)
τ,h(n)
low as −40 dB, which poses a challenge for wireless loca-
tion in such environments.
■ Channel fading and Doppler frequency. In wireless location where the likelihood function P(r(1) · · · r(K)|τ, h(n)) is of the
applications, the estimation period can be considerably long form
(it might reach several seconds). Thus, in a fading environ-


ment, the channel values can change significantly over the 1  K
2
location estimation period. In this way, the channel values can C1 exp −C2 r(n) − Ah(n)s(n − τ ) (29)
K n=1
no longer be assumed constant during the estimation period.
■ Overlapping multipath. In wireless location systems, the
accurate estimation of the TOA, AOA, and AmpOA of the for some positive constants C1 and C2 that are independent of
first arriving ray of the multipath channel is vital. In gen- the unknowns {τ, h(n)}. Thus, the ML estimates of {τ, h(n)} are
eral, the first arriving (prompt) ray is assumed to corre- given by [25]
spond to the most direct path between the MS and BS.
However, in many wireless propagation scenarios, the
prompt ray is succeeded by a multipath component that {τ̂ , ĥ(n)} = arg max JML(τ, h(n)), (30)
τ,h(n)
arrives at the receiver within a short time of the prompt
ray. If this delay is smaller than the duration of the pulse-
shape used in the wireless system, these two rays overlap, where the cost function JML is given by
causing errors in the prompt ray TOA and AmpOA estima-
tion. These errors degrade the performance of wireless 2A  K

location algorithms; as such, they demand careful consider- J ML (τ, h(n)) = Re[r (n )h ∗ (n )s ∗ (n − τ )]
K n=1
ations (see, e.g., [9]–[11], [28], and [29]).
In the sections that follow, some algorithms for TOA and A2 K
− |h(n)|2 |s(n − τ )|2 .
AOA estimation are described. These algorithms exploit the K n=1
nature of the wireless channel and are robust to low SNR and
fading conditions [25], [51]. This construction requires an infinite dimensional search
over {τ, h(n)} and is not feasible in practice even when τ and
TOA ESTIMATION h(n) are evaluated over a dense grid. To arrive at a feasible
The aim of a TOA estimation scheme is to estimate an unknown algorithm, we assume the channel variations are sufficiently
delay, τ o, of a known sequence {s(n)}. (At the serving site, the slow, namely, that h(n) is piecewise constant over intervals of
MS signal can be decoded with reasonably high accuracy; thus, N samples. The value of N depends on the environmental con-
it can be assumed to be known almost perfectly.) The signal is ditions; an optimal choice for N is discussed later in this

IEEE SIGNAL PROCESSING MAGAZINE [31] JULY 2005

article. Under the slow channel variation assumption, it can where Jo(·) is the first-order Bessel function, Ts is the sampling
be argued that the maximization problem (30) over τ and period of the received sequence {r(n)}, and fD is the maximum
h(n) can be reduced to maximizing the following cost func- Doppler frequency. Therefore, (32) shows that the coherent
tion instead over τ [25]: averaging interval N should be adapted according to the channel
autocorrelation function.
 2
M  
1
1

mN
∗ 
J(τ ) =  r(n)s (n − τ ) , (31) TOA ESTIMATION WITH ANTENNA ARRAY
M m=1  N n=(m−1)N+1

Further improvement in the TOA estimation can be accomplished
by deploying an antenna array at the BS [51]. Thus assume that
where the integers N and M satisfy NM = K. A practical scheme the BS uses an Na-element antenna array. Then, in contrast to
for maximizing (31) over τ is shown in Figure 6 and was derived (26), the received signal at time n is now an Na × 1 vector:
in [25]. The received sequence {r(n)} is correlated with a
delayed replica of the transmitted sequence, {s(n − τ )}, for dif- r(n) = ah(n)s(n − τ o) + v(n), (33)
ferent values of τ . The resulting sequence is averaged coherently
(Note that we are assuming a scat-
tered MS model. Since in a typical cel-
1 N 1 M lular system the mobile station is
N Σ
2
× 1 |.| M Σ
1 usually far from the BS, the reflected
N rays from the scatterers around the
s*(n – τ1)
1 N 2 1 M MS reach the BS at close angles.
× N Σ |.| M Σ max ˆ These reflected rays cause a fading
1 1

N effect in h(n) with almost the same

r (n) s*(n –τ2)
AOA. Moreover, it is assumed that any
bias in the direction or the angle of
1 N 1 M
× N Σ |.|
2
M Σ the arrays can be ignored from the
1 1
derivations through some calibration
N
s*(n –τF) procedures.) where now v(n) is an
Doppler additive white Gaussian noise vector
Estimator with covariance matrix σv2 I, and a is
the array response defined by
[FIG6] A scheme for TOA estimation over fading channels.
 (Na −1)d

a = col 1, e j2π λ sin α , . . . , e j2π λ sin α ,
d
over an interval of N samples and further averaged noncoher- (34)
ently for M samples after squaring to build the power delay pro-
file, J(τ ). The branch that results in the largest value for τ where α is the AOA of the signal measured with respect to the
provides the desired estimate τ̂ . Moreover, the SNR at the out- array, d is the antenna spacing, and λ is the wavelength corre-
put of the searcher is [25] sponding to the carrier frequency. Note that the array response
defined by (34) is valid only for a uniform linear array (ULA).
  This array response could be modified if other array structures,
A2

N−1
2(N − i)Rh(i) such as circular array, are used.
SNR = Rh(0) + .
σv2 i=1
N The ML estimates of τ and α are given by

The optimal value of the coherent averaging period (Nopt ) is {τ̂ , α̂} = arg max [P(r(1) · · · r(K))|τ, α], (35)
τ,α
obtained by maximizing the SNR with respect to N, which leads
to the following expression for finding Nopt :
where the likelihood function is now proportional to
opt −1
N

iRh(i) = 0. (32)
1
K
i=1 exp −C2 r(n) − ah(n)s(n − τ )2 , (36)
K n=1
For a Rayleigh fading channel, Rh(i) is given by
in which . is the Euclidean norm of the vector and C2 is some
  positive constant. Therefore, the ML estimates of {τ, α} can be
Rh(|i|) = Jo 2π fD Ts i ,
found by solving

IEEE SIGNAL PROCESSING MAGAZINE [32] JULY 2005

 {τ̂ , α̂} = arg max JML (τ, α), (37)  
τ,α 1

mN
o 2
p(m) = |s(n − τ )| ,
N n=(m−1)N+1
where
1
K
JML (τ, α) =
r(n) − ah(n)s(n − τ )
2 . and u m refers to the noise term in (40). Collecting (41) into vec-
K n=1
tor form yields
z   p(1)h(N)I  u 
This cost function can be simplified by noting that
a
2 = Na 1 Na×Na 1
and that the entries of a have unit norm, so that      
     
 z2   p(2)h(2N)INa×Na   u2 
     
     
 = a +  . (42)
1
K
 ..   ..   .. 
JML (τ, α) = |a∗ r(n) − h(n)s(n − τ )|2 . (38)  .

 
  . 

 .



K n=1      
zM p(M)h(MN)INa×Na uM
Rather than perform a two-dimensional (2-D) search, the esti- z A
mator can perform the search for τ and α separately as follows.
Assume first that α is known.
Then the term a∗ r(n) in (38) can
be interpreted as the output of a 90
120 1N 1M
beamformer (antenna combiner) 2
× NΣ |.| MΣ
steered to direction α, as shown in × × 1 1
150 N
s*(n –τ1)
Figure 7. The optimization prob- e–j2πfct 1 1N 2 1M
× × × Σ
N 1 |.| MΣ max
lem for τ , given α, then reduces 180 +
1
ˆ
–j2π d sin α N
to the single-antenna case of e–j2πfct e λ s*(n –τ2)
Figure 6 using a beamformer at 210
1N 2 1M
× NΣ |.| MΣ
direction α. 240 × × 1 1
270 N
d s*(n –τF)
e–j2πfct e–j2π(Na –1) λ sin α Doppler
AOA ESTIMATION WITH
Estimator
ANTENNA ARRAY
Now assume τ in (38) is known
and evaluate the correlation [FIG7] TOA estimation over fading channels using an antenna array.

 
1

mN
zm = ∗ o
r(n)s (n − τ ) , m = 1, . . . ,M The channel gains {h(N), h(2N), . . . , h(MN)} can be esti-
N n=(m−1)N+1 mated roughly from (41) by noting that the top entry of a is
(39) unity, so that

ĥ(mN) = z m (1)/p(m).
over intervals of length N, during which h(n) is essentially
invariant. Then, using (33),
The LS estimate can then be obtained as
 
1

mN
z m = ah(mN) |s(n − τ o)|2 â = (A∗ A)−1 A∗ z. (43)
N n=(m−1)N+1
 
1

mN
∗ o
+ v(n)s (n − τ ) . (40) The AOA information can be extracted from the estimated
N n=(m−1)N+1 array response â based only on the phase rotation between the
entries of â (see Figure 8).

In other words, MULTIPATH, MULTIUSER ENVIRONMENT

As mentioned previously, wireless propagation suffers from
z m = p(m)h(mN)a + u m , (41) multipath conditions, in which case the prompt ray may be
succeeded by multipath components that arrive at the receiver
with short delays (e.g., [52]). In this section, we describe one
where p(m) denotes the constant known power term way to perform TOA and AOA estimation under multipath

IEEE SIGNAL PROCESSING MAGAZINE [33] JULY 2005

 and
 
1

mN  
uk,l,m = v(n)s∗k o
n − τk,l (47)
r(n) N n=(m−1)N+1

Collect M Realizations (zm)

Least-Squares Estimation
×
N
∑

Nu

L
ik,l,m = ρk,l,k ,l (m)hk ,l (mN)ak ,l (48)

Array Response
1
s*(n – ) N k =1 l =1
× ∑ â α k = k,l = l
1
s*(n – ) where
N
× ∑
1
1

mN    
s*(n – ) ρk,l,k  ,l  (m) = sk n − τko ,l  s∗k n − τk,l
o
N n=(m−1)N+1

[FIG8] AOA estimation using an antenna array over a single path (49)
fading channel.
represents the correlation between the sequences of user k and
all other users. Collecting M such realizations into a vector zk,l
conditions. First, we modify the channel model (26) to accom- yields
modate a more general multiuser, multipath environment.
   
Assuming the maximum number of channel taps to be L and zk,l,1 pk,l (1)hk,l (N)INa×Na
the number of mobile users to be Nu , the received signal r(n)  zk,l,2   pk,l (2)hk,l (2N)INa×Na 
   
of size Na × 1 is now given by  .  = ..  ak,l
 ..   . 
z p (M)hk,l (MN)INa×Na


Nu

L  k,l,M
   k,l  
o
r(n) = ak,l hk,l (n)sk(n − τk,l ) + v(n), (44) zk,l Ak,l
   
k=1 l=1 ik,l,1 uk,l,1
 ik,l,2   uk,l,2 
   
where sk(n) is the transmitted sequence by the kth user and +  . + . . (50)
 ..   .. 
v(n) is an Na × 1 additive white Gaussian noise vector.
i uk,l,M
Moreover, hk,l (n) and τk,l are the channel gain and delay,  k,l,M
 
respectively, for user i, and ak,l is the array response correspon- ik,l

ding to the l th channel tap from user k to the BS, namely The least-squares estimation of ak,l can be obtained as

 (Na −1)d
  −1
ak,l = col 1, e j2π λ sin αk,l , . . . , e j2π λ sin αk,l , âk,l = A∗k,l Ak,l A∗k,l zk,l .
d
(45) (51)

where αk,l is the AOA for the l th tap and kth user. The AOA information is finally extracted from the estimated
As in the single path case discussed earlier [see (39)], we array response âk,l based only on the phase rotation between the
define the correlation vectors: entries of âk,l according to (45). The above least-squares estima-
tion is repeated for all users and multipaths, k = 1, . . . , Nu ,


mN   l = 1, . . . , L.
1
zk,l,m = r(n)s∗k n − τk,l
o
, As the number of users and multipaths increases, multiple
N n=(m−1)N+1 access interference (MAI) and intersymbol interference (ISI)
in (46) become stronger. For practical scenarios with a large
where N is the coherent correlation length. Then [compare number of active users in a cell, the accuracy of the least-
with (41)] squares estimation of AOA is limited by MAI and ISI. One
solution for reducing the effect of MAI in (46) is to increase
zk,l,m = pk,l (m)hk,l (mN)ak,l + ik,l,m + uk,l,m , (46) the coherent correlation length N, as well as the realization
length M. However, the correlation or estimation length can-
not be increased indefinitely. The correlation length should
where be short enough such that the channel taps can be assumed
  constant during the estimation process.
1

mN  
o 2
pk,l (m) = |sk n − τk,l | We may use joint least-squares estimation followed by multi-
N n=(m−1)N+1 user interference cancellation to provide an accurate AOA

IEEE SIGNAL PROCESSING MAGAZINE [34] JULY 2005

estimation in the presence of interfering users. This joint tech- THE INDOOR ENVIRONMENT
nique takes advantage of the following two facts: Yet, the indoor channel environment is challenging for a num-
■ A BS (in normal operating ber of reasons.
mode) detects and decodes ■ Channel fading. The channel
the signals from all users LOCATION-BASED APPLICATIONS WILL variation as a function of posi-
simultaneously. Therefore, PLAY AN IMPORTANT ROLE IN FUTURE tion due to the scatterer-rich
the BS knows the training WIRELESS MARKETS. nature of indoor environments
sequences used by the users, can be significant. In a scatterer-
i.e., sk(n), k = 1, . . . , Nu . rich environment, the channel
■ The BS performs the channel and array response estima- can be considered correlated only over a distance of λ/2,
tion for all users and multipaths. Therefore, the estimation of where λ is the wavelength corresponding to the carrier fre-
the channel taps (âk,l and hk,l , k = 1, . . . Nu, l = 1, . . . , L) quency. At 2.4 GHz, which is the band of operation for
are available at the BS. IEEE802.11b and IEEE802.11g, λ/2 is less than 10 cm. In
The above information is used in a secondary stage to fur- other words, a movement of about 10 cm in an indoor envi-
ther enhance the accuracy of the estimation process by cancel- ronment can result in significant change in the channel gain.
ing the MAI in (46). The interfering signal is regenerated using ■ Path loss and shadow fading. The distance between the
the known sk(n), the estimated channel gain ĥk,l , and the array access point (AP) and mobile users causes path loss in the
response ak,l . It is then subtracted from the previous correla- signal strength. The path loss in a typical office area is pro-
tion results zk,l , and a new estimate is obtained. The following portional to d−3.5 , where d is the distance between the
steps are performed in the proposed architecture: mobile user and the AP. In addition to the path loss, the
1) Use (46)–(51) to calculate {α̂k,l , ĥk,l (mN)}. shadow fading caused by walls further contributes to atten-
2) Use the estimated channel taps to regenerate (estimate) the uation of the signal strength.
MAI term ik,l,m in (48), i.e., ■ Interference. The 2.4-GHz band is an unlicensed band
where devices such as Bluetooth, cordless phones, and even
microwave ovens operate. The interference from these other



N u L active devices can limit the achievable location accuracy.
îk,l,m = ρk,l,k
,l
(m) ĥk
,l
(mN)âk
,l
. (52)
k
=1 l
=1 AMPOA ESTIMATION
k
= k,l
= l
Some of the older proposed location-aware systems for indoor
environments [53]–[57] require specialized hardware such as
3) Subtract the estimated interference (52) from the correla- ultrasound transmitters, camera, and infrared transmitters.
tion vector in (46). The new zk,l,m becomes But since the IEEE 802.11b and IEEE 802.11g MAC layer soft-
ware provides the signal strength and the SNR, a software-level
location technique could be developed for WLAN networks
z̄k,l,m = zk,l,m − îk,l,m based on the AmpOA at different access points [58]–[66].
Specifically, when an IEEE802.11 wireless network operates in
the infrastructure mode, there are several APs and many end
with the interference term ik,l,m reduced. users within the network. RF-based systems that use the signal
4) Use the z̄k,l,m in (51) to find an improved {α̂k,l , ĥk,l (mN)}. strength for location purposes can monitor the received signal
5) Repeat steps 2–4 for all users and multipaths as necessary. strength from different APs and use the obtained statistics to
The above procedure can be repeated until an AOA estimate build a conditional probability distribution network to esti-
within the desirable range is achieved. mate the location of the mobile client. These schemes usually
work in two phases: the first phase is the offline training and
WLANS data gathering phase, and the second phase is the location
Similar technical challenges also arise for wireless location determination phase using the online signal strength meas-
determination in indoor environments, where WLAN is cur- urements. In the training phase, signal strength measure-
rently the most widely deployed wireless network. WLAN ments are used to build an a priori probability distribution of
standards such as IEEE802.11b, and more recently the received signal strength at the mobile user from all APs.
IEEE802.11g, have been widely adopted in offices, homes, Assume there are N APs in the system and the radio map is
hospitals, restaurants, and schools. WLAN connectivity has created based on measurements from M user locations. The
also become a standard feature for laptop computers and radio map model is described by [55]–[58]
PDAs as well as the new generation of smart cellular phones.

As such, there is an increasing interest in utilizing these net- p(Ai |xj, yj) = the PDF of the received signal strength,
works for location purposes to help provide good coverage for
indoor scenarios. where

IEEE SIGNAL PROCESSING MAGAZINE [35] JULY 2005

 Ai = received signal strength from the i th AP Then, using Bayes’ rule, the probability of having the mobile
(xj, yj) = coordinates of the jth measurement point user at location (xj, yj) given the received signal strengths from
all APs is given by
i = 1, 2, . . . , N, j = 1, 2, . . . , M.


A
= [A
1 , . . . , A
N ]
After constructing a Bayesian network, the online determi-
p(A
|xj, yj)p(xj, yj)
nation phase uses ML estimation to locate the mobile user. p(xj, yj|A
) =
Thus, assume that the mobile user measures the received signal p(A
)



strength from all APs, as in p(xj, yj) N i=1 p(A i |xj, yj)
=

,
p(A )


A
i = measured signal from the ith AP.



where N i=1 p(Ai |xj, yj) is the approximation for the conditional
probability density function of the received signal strength when
the location of the mobile user is given. Thus, the location of
the mobile user can be estimated as

( x̂m , ŷm ) = arg max p(xj, yj|A
)

xj,yj
j = 1, 2, . . . , M. (53)

TOA/AOA ESTIMATION
The TOA and AOA estimation techniques and the data
fusion schemes presented in the previous sections can be
used for indoor environments as well. However, the accura-
cy desired for indoor applications is higher than that
required for outdoor environments. While an accuracy of 50
[FIG9] An illustration of the UCLA WLAN Location Simulator
interface. The estimated location of a mobile user using different
m is acceptable for many outdoor applications, for indoor
algorithms would be plotted for different realizations. Moreover, applications an accuracy of few meters is desired. Therefore,
the estimated accuracy of the different methods would be the performance of the estimation algorithms should be
shown by circles surrounding the mobile location.
boosted to meet the accuracy requirements. The following
facts will improve the accuracy of location finding algo-
rithms for indoor applications:
■ Higher clocking rates. The clocking rates of WLAN sys-
tems are higher than the ones used in cellular systems; this
is due to the fact that the WLAN physical layers are intend-
ed for higher data rates and occupy a wider bandwidth than
the physical layer of cellular systems. The higher clocking
rate (and, equivalently, the higher sampling rate at the
receiver) translates into higher accuracy in TOA measure-
ments and into more accurate location estimates.
Additionally, the bandwidth per channel used in 3G cellular
networks is about 4 MHz, as opposed to the 11-MHz band-
width in IEEE802.11b and 16-MHz bandwidth in
IEEE802.11a and IEEE802.11g. The higher bandwidth and
clocking rate effectively provide a higher resolution in esti-
mating the TOA of the signals.
[FIG10] An illustration of the UCLA Cellular Location Simulator ■ Higher SNR. WLAN networks operate at higher SNR than
interface. The estimated location of a mobile user using different cellular networks. The higher SNR results in more accurate
algorithms would be plotted for different realizations. Moreover, estimates for TOA and AOA.
the estimated accuracy of the different methods and the FCC
accuracy requirements would be shown by circles surrounding ■ Oversampling at the receiver. The received signal can be
the mobile locations. The design engine allows the user to place oversampled to further increase the resolution of TOA
blocking objects in the simulator environment and to select the estimation. Since the received SNR in WLAN networks is
trajectory of the mobile user such that it experiences different
situations, fadings, and shadowings. The various parameters relatively high, an accurate TOA estimation after oversam-
that control the environment can be adjusted as well. pling is possible.

IEEE SIGNAL PROCESSING MAGAZINE [36] JULY 2005

 ■ Slow-varying channel. The channel variation in indoor shape Doppler spectrum. Moreover, the simulator allows
environments is slower than in outdoor environments. This is the user to define the trajectory of the mobile, and then
due to the range of speeds present in indoor and outdoor tracks the user on the defined trajectory.
environments. The slow-varying channel allows for longer ■ Configuring the environmental parameters and net-
coherent averaging periods at the receiver (the parameter N work geographical structure. One of the factors affect-
used in the derivations), which results in a higher effective ing the performance of the wireless location system is
SNR for TOA and AOA estimation. the environment type (e.g., bad urban, urban, suburban,
■ Power up scheme. Due to the local nature of WLAN net- or rural.) For example, in a bad urban area with many
works, the mobile user can be requested by the network to blocking objects and buildings, NLOS effects play an
raise the level of transmitted power momentarily. This important role in the estimation accuracy. The simulator
instant increase in the level of transmitted power will not enables the user to place an arbitrary number of build-
degrade the network performance as significantly as it ings of different sizes and shapes in the simulation
would for cellular networks. environment. The simulator modifies the channel mod-
For further information on indoor location algorithms, see els to capture the effect of the buildings (shadow fading
[15] and [61]. Moreover, [62] describes localization algorithms and NLOS effects).
in a cooperative sensor network setting.

SIMULATION ENVIRONMENT
To test several of the techniques and algorithms described in the
previous section, a software simulator called the Wireless
Location Simulator has been developed at the UCLA Adaptive BS BS
Systems Laboratory [67]. A high degree of testability and flexi-
bility, along with a user-friendly interface, are designed into the
simulator. Selected snapshots of the Wireless Location
Simulator are shown in Figures 9–12. The simulator consists of
an interface and a location-finding engine. The location engine
performs the following tasks:
■ Data fusion techniques: Different data fusion techniques
are implemented using TOA, AOA, or a combination of both. Mobile User
■ Channel modeling: A multipath, multiuser channel envi- BS BS
ronment is created that models path loss, shadowing,
Rayleigh fading, and Doppler frequency effects. [FIG11] Snapshot of the UCLA Location Simulator. The location
■ Parameter estimation: TOA and AOA estimation algorithms estimation accuracy and the FCC requirements are shown by two
circles in this lateral view generated by the 3-D simulation
are implemented as part of the location finding engine.
visualizer.
Different variations of the algorithms are implemented for
performance and comparison purposes.
Most of the algorithms used in the location-finding engine
are generic in the sense that they could be used for both indoor
and outdoor applications with minimum alteration. The loca-
tion-finding engine and the capabilities listed below make the
simulator usable for both networks.
■ Configuring the physical layer for different wireless net-
works. Adjusting the network physical layer parameters
enables the simulator to be used for different wireless
Attained
networks. Among the programmable parameters are the Accuracy
spreading factor, packet size, training length, constellation
type, modulation technique, carrier frequency, level of
transmitted signal power, and the number of antennas at
the transmitter or receiver. Mobile User FCC Accuracy
Trajectory Requirement
■ Configuring the mobile user conditions. The wireless
channel models depend on the Doppler frequencies present
in the environment. The Doppler frequency depends on the
mobile speed and the carrier frequency of the system. The
[FIG12] Snapshot of the UCLA Location Simulator. The location
simulator accepts different speed and carrier frequencies as estimation accuracy and the FCC requirements are shown by two
input and generates a Rayleigh fading channel with the U- circles in this top view generated by the 3-D simulation visualizer.

IEEE SIGNAL PROCESSING MAGAZINE [37] JULY 2005

 ■ Performance evaluation and monitoring tools. The simu- SOME SIMULATION RESULTS
lator contains different tools to illustrate the results and Some simulation results are shown in Figure 13(a) and (b) for
accuracy of the location procedure, such as a CDMA cellular network with the following parameters:
1) comparing the estimated trajectory with the true tra- CDMA chip rate of 4 MHz, a processing gain of 64, a 3-tap
jectory Rayleigh fading channel with path loss exponent of two, an
2) statistics of the location error, including the 67% and antenna array of size four at the BS, and a Doppler frequency
95% outage values (the 67% and 95% outage values are of corresponding to a maximum speed of 30 mph. The location
interest due to the FCC algorithms are simulated in
requirements) a multi-user environment
3) a three-dimensional A LOCATION FINDING SYSTEM SHOULD BE with a different number of
(3-D) simulator that ABLE TO SEAMLESSLY USE BOTH CELLULAR active users. Figure 13(a)
creates a 3-D virtual AND WLANS FOR LOCATION FINDING BY and (b) shows the resulting
reality environment. ROAMING BETWEEN THE NETWORKS. accuracy outage curves. An
The 3-D viewer has outage curve measures the
different adjustable probabilities that the loca-
camera views from different angles. It provides the user tion estimation errors will be below certain values.
with an interactive 3-D environment that shows the For example, in Figure 13(a), it is seen that for a receiver
movement of the mobile user on the predefined trajecto- employing both TOA and AOA measurements, the location
ry. It also shows the accuracy of the algorithm and com- error is below 100 m 90% of the time. The FCC-mandated
pares it with the FCC standard. requirement for a network-based solution is for the location

100
100
90 90

80 80

70 70
Outage (%)

60
Outage (%)

60
50 50

40 40
FCC Requirement for FCC Requirement for
30 30
Network-Based Location Network-Based Location
20 FCC Requirement For 20 FCC Requirement For
10 Handset-Based Location 10 Handset-Based Location

0 0
0 50 100 150 200 250 300 350 400 0 50 100 150 200 250 300 350 400
Location Error (m) Location Error (m)

Multiple Antenna (TOA)–Section IV-A Multiple Antenna (TOA)–Section IV-A

Multiple Antenna (TOA/AOA)–Section IV-D Multiple Antenna (TOA/AOA)–Section IV-D
Multiple Antenna (TOA/AOA) with IC–Section X

• Number of Base Stations=3

• Number of Active Users=1 • Number of Base Stations=3
• 67% Outage=47 m • Number of Active Users=6
• Number of Antennas=4 • 67% Outage=45 m
• 95% Outage=144 m • Number of Antennas=4
• Number of Multipaths=3 • 95% Outage=128 m
• Maximum Speed=30 mph • Number of Multipaths=3
• Maximum Speed=30 mph

(a) (b)

[FIG13] Outage curves for location accuracy in outdoor environment (IC denotes interference cancellation method). (a) Assuming one
user. (b) Assuming six users.

IEEE SIGNAL PROCESSING MAGAZINE [38] JULY 2005

error to be below 100 m only 67% of the time. For a mobile- Alireza Tarighat received the B.Sc. degree in electrical
based solution, on the other hand, the FCC requirement engineering from Sharif University of Technology, Tehran,
mandates an outage probability of 67% for 50 m. Both of Iran, in 1998 and the M.Sc. degree in electrical engineering
these requirements are met by the TOA/AOA fusion method from the University of California, Los Angeles (UCLA), in
presented earlier. Figure 13(b) repeats the simulation for the 2001. He is pursuing the Ph.D. degree in electrical engineer-
case of six total users. ing at UCLA. He received the Gold Medal of the National
Physics Olympiad, Iran, 1993, and the Honorable Mention
CONCLUSION Diploma of the 25th International Physics Olympiad, Beijing,
Network-based wireless location poses several interesting prob- China, 1994. His research focuses on signal processing tech-
lems from a signal processing perspective. The estimation algo- niques for communication systems, including MIMO OFDM
rithms must provide accurate parameter estimates under receiver design and multi-user MIMO communications. He is
challenging conditions such as fast fading channels, low SNR, a student member of the IEEE.
multipath effects, and multiuser interference. Small errors in Nima Khajehnouri received the B.Sc. degree in electrical
estimation can lead to large errors in location. For example, in engineering from Sharif University of Technology, Tehran,
3G CDMA, the chip duration is roughly 0.25 µs. An error in TOA Iran, in 2001 and the M.Sc. degree in electrical engineering
estimation of the order of Tc/2 can translate into 37.5 m in loca- from the University of California, Los Angeles (UCLA), in
tion error. Likewise, for a cell with a two-mile radius, an error of 2002 with emphasis on signal processing. Since 2002, he has
1◦ in the AOA measurement can result in a location error of the been pursuing the Ph.D. degree in electrical engineering at
order of 55 m. For this reason, the location estimation algo- UCLA. His research focuses on signal processing techniques
rithms and the data fusion methods must exploit any available for communication systems, including multiuser MIMO com-
information about the environment (e.g., fading conditions, munications, relay networks, and signal processing for sen-
Doppler frequency, and network topology) to attain high accura- sor networks.
cy. In addition, the resulting location searchers need to exhibit a
certain degree of adaptation to changing conditions (e.g., mobile
speed) so as to maintain reliable performance. REFERENCES
[1] “Report on wireless location-based markets,” PELORUS Group, NJ, Tech. Rep.,
2001.
ACKNOWLEDGMENTS [2] “Location-based services: Finding their place in the market,” In-Stat/MDR, San
This work was supported in part by National Science Jose, CA, Tech. Rep., Feb. 2003.

Foundation Grants CCR-0208573 and ECS-0401188. [3] A.H. Sayed and N.R. Yousef, “Wireless location,” in Wiley Encyclopedia of
Telecommunications, J. Proakis, Ed. New York: Wiley, 2003.
[4] F. Gustafsson and F. Gunnarsson, “Mobile positioning using wireless networks,”
IEEE Signal Processing Mag., vol. 22, no. 4, pp. 41–53, July 2005.
AUTHORS [5] “FCC Docket No. 94–102. Revision of the commissions rules to insure compati-
Ali H. Sayed received the Ph.D. degree in electrical engineer- bility with enhanced 911 emergency calling systems,” Federal Communicarions
Commission Tech. Rep. RM-8143, July 1996.
ing in 1992 from Stanford University, Stanford, California. He
[6] “Report on the New Jersey wireless enhanced 911 terms: The first 100 days,”
is currently a professor and vice chair of electrical engineer- State of New Jersey, Tech. Rep., June 1997.
ing at the University of California, Los Angeles. He is also the [7] A.H. Sayed, Fundamentals of Adaptive Filtering. New York: Wiley, 2003.
principal investigator of the UCLA Adaptive Systems [8] J.E. Maloney and J.O. Stevenson, “Robust, efficient, localization system,” U.S.
Laboratory (www.ee.ucla.edu/asl). He has authored over 200 Patent 6 047 192, May 13, 1997.
journal and conference publications and several books includ- [9] O. Hilsenrath and M. Wax, “Radio transmitter location finding for wireless
communication network services and management,” U.S. Patent 6 026 304, Jan. 8,
ing the textbook Fundamentals of Adaptive Filtering (Wiley, 1997.
2003). He has served on the program committees of several [10] M. Wax and O. Hilsenrath. “Signature matching for location determination in
international meetings, and has also consulted with industry. wireless communication systems,” U.S. Patent 6 108 557, Feb. 18, 1998.
His research interests include adaptive and statistical signal [11] J.P. Kennedy, C.D. Roller, and R.W. Hooper. “Passive high accuracy geoloca-
tion system and method,” U.S. Patent 5 317 323, Mar. 5, 1993.
processing, filtering and estimation theories, signal process-
ing for communications, interplays between signal processing [12] J.J. Caffery and G.L. Stuber, “Overview of radiolocation in CDMA cellular sys-
tems,” IEEE Commun. Mag., vol. 36, no. 4, pp. 38–45, Apr. 1998.
and control methodologies, system theory, and fast algo-
[13] J.J. Caffery and G.L. Stuber, “Radio location in urban CDMA microcells, in
rithms for large-scale problems. He has received many Proc. IEEE Int. Symp. Personal, Indoor and Mobile Radio Communications,
Toronto, Canada, Sept. 1995, vol. 2, pp. 858–862.
awards, including the 1996 IEEE Donald G. Fink Award, the
2002 Best Paper Award from the IEEE Signal Processing [14] M. Yunos, J. Zeyu Gao, and S. Shim, “Wireless advertising’s challenges and
opportunities,” IEEE Computer, vol. 36, no. 5, pp. 30–37, May 2003.
Society (SPS), and the 2003 Kuwait Prize in Basic Sciences.
[15] G. Sun, J. Chen, W. Guo, and K.J.R. Liu, “Signal processing techniques in net-
He has held many roles within the IEEE Signal Processing work-aided positioning,” IEEE Signal Processing Mag., vol. 22, no. 4, pp. 12–23,
July 2005.
Society, including a member of the publication and award
boards. He is on the editorial board of IEEE Signal Processing [16] L.A. Stilp, “Carrier and end-user application for wireless location systems,” in
Proc. SPIE, Philadelphia, PA, Oct. 1996, vol. 2602, pp. 119–126.
Magazine and is editor-in-chief of IEEE Transactions on
[17] X. Li and K. Pahlavan, “Super-resolution TOA estimation with diversity for
Signal Processing. He is a Fellow of the IEEE. indoor geolocation,” IEEE Trans. Wireless Commun., vol. 3, pp. 224–234, Jan. 2004.

IEEE SIGNAL PROCESSING MAGAZINE [39] JULY 2005

[18] L. Cong and W. Zhuang, “Hybrid TDOA/AOA mobile user location for wide- [44] S. Al-Jazzar, J. Caffery, and H.R. You. “A scattering model based approach to
band CDMA cellular systems,” IEEE Trans. Wireless Commun., vol. 1, no. 3, pp. NLOS mitigation in TOA location systems,” in Proc. IEEE Vehicular Technology
439–447, July 2002. Conf., Birmingham, AL, 2002, vol. 2, pp. 861–865.

[19] A.J. Weiss, “On the accuracy of a cellular location system based on RSS meas- [45] L.J. Greenstein, V. Erceg, Y.S. Yeh, and M.V. Clark, “A new path-gain/delay-
urements,” IEEE Trans. Veh. Technol., vol. 52, no. 6, pp. 1508–1518, Nov. 2003. spread propagation model for digital cellular channels,” IEEE Trans. Vehicular
Technology, vol. 46, pp. 477–485, May 1997.
[20] I. Paton et al., “Terminal self-location in mobile radio systems,” in Proc. 6th
Int. Conf. Mobile Radio and Personal Communications, Coventry, UK, Dec. 1991, [46] A. Ghosh and R. Love, “Mobile station location in a DS-CDMA system,” in Proc.
vol. 1, pp. 203–207. IEEE Vehicular Technology Conf., Ottawa, Canada, May 1998, vol. 1, pp. 254–258.

[21] J.J. Caffery and G.L. Stuber, “Vehicle location and tracking for IVHS in CDMA [47] K. Kuboi, S. Shirota, S. Sakagami, S. Aoyama, and A. Akeyama, “Vehicle posi-
microcells,” in Proc. IEEE Int. Symp. Personal, Indoor and Mobile Radio tion estimates by multibeam antennas in multipath environments,” IEEE Trans.
Communications, Amsterdam, The Netherlands, Sept. 1994, vol. 4, pp. 1227–1231. Veh. Technol., vol. 41, no. 1, pp. 63–68, Feb. 1992.

[22] J.J. Caffery, Wireless location in CDMA cellular radio systems. Norwell, MA: [48] G.P. Yost and S. Panchapakesan, “Automatic location identification using a
Kluwer, 2000. hybrid technique,” in Proc. IEEE Vehicular Technology Conf., Ottawa, Canada,
May 1998, vol. 1, pp. 264–267.
[23] K.W. Cheung, H.C. So, W.K. Ma, and Y.T. Chan, “Least squares algorithms for
time-of-arrival-based mobile location,” IEEE Trans. Signal Processing, vol. 52, no. [49] X. Wang, Z. Wang, and B. O’Dea, “A TOA-based location algorithm due to
4, pp. 1121–1130, Apr. 2004. NLOS propagation,” IEEE Trans. Veh. Technol., vol. 52, no. 1, pp. 112–116, Jan.
2003.
[24] J.J. Caffery and G.L. Stuber, “Subscriber location in CDMA cellular networks,”
IEEE Trans. Veh. Technol., vol. 47, no. 2, pp. 406–416, May 1998. [50] M. McGuire, K.N. Plataniotis, and A.N. Venetsanopoulos, “Location of mobile
terminals using time measurements and survey points,” IEEE Trans. Veh.
[25] N.R. Yousef, A.H. Sayed, and L.M.A. Jalloul, “Robust wireless location over fad- Technol., vol. 52, no. 4, pp. 999–1011, July 2003.
ing channels,” IEEE Trans. Veh. Technol., vol. 52, no. 1, pp. 117–126, Jan. 2003.
[51] A. Tarighat, N. Khajehnouri, and A.H. Sayed, “CDMA location using multiple
[26] M.A. Spirito, “On the accuracy of cellular mobile station location estimation,” antennas and interference cancellation,” in Proc. IEEE Vehicular Technology
IEEE Trans. Veh. Technol., vol. 50, no. 3, pp. 674–685, May 2001. Conf., Apr. 2003, vol. 4, pp. 2711–2715.

[27] A.J. Weiss, “On the accuracy of a cellular location system based on RSS meas- [52] C. Botteron, A. Hst-Madsen, and M. Fattouche, “Cramer-Rao bounds for the esti-
urements,” IEEE Trans. Veh. Technol., vol. 52, no. 6, pp. 1508–1518, Dec. 2003. mation of multipath parameters and mobiles’ positions in asynchronous DS-CDMA
systems,” IEEE Trans. Signal Processing, vol. 52, no. 4, pp. 862–875, Apr. 2004.
[28] N.R. Yousef and A.H. Sayed, “Detection of fading overlapping multipath com-
ponents for mobile-positioning systems,” in Proc. Int. Conf. Communications, [53] J. Krumm, S. Harris, B. Meyers, B. Brumitt, M. Hale, and S. Shafer, “Multi-
Helsinki, Finland, June 2001, vol. 10, pp. 3102–3106. camera multi-person tracking for EasyLiving,” in Proc. 3rd IEEE Int. Workshop
Visual Surveillance, Dublin, Ireland, July 2000, pp. 3–10.
[29] J. Friedmann, R. Raich, J. Goldberg, and H. Messer, “Bearing estimation for a
distributed source of nonconstant modulus—Bounds and analysis,” IEEE Trans. [54] N. Priyantha, A. Miu, H. Balakrishman, and S. Teller, “The Cricket compass for
Signal Processing, vol. 51, no. 12, pp. 3027–3035, Dec. 2003. context-aware mobile applications,” in Proc. ACM/IEEE Int. Conf. Mobile
Computing and Networking (MOBICOM 2001), Rome, Italy, July 2001, pp. 1–14.
[30] “The CDMA2000 ITU-R RTT candidate submission V0.18,”
Telecommunications Industry Association, July 1998. [55] A. Ward, A. Jones, and A. Hopper, “A new location technique for the active
office,” IEEE Trans. Personal Communications, vol. 4, pp. 42–47, Oct. 1997.
[31] K.C. Ho and Y.T. Chan, “Solution and performance analysis of geolocation by
TDOA,” IEEE Trans. Aerosp. Electron. Syst., vol. 29, no. 4, pp. 1311–1322, Oct. [56] R. Want, A. Hopper, V. Falco, and J. Gibbons, “The Active Badge Location
1993. System,” Proc. ACM Trans. Inform. Syst., vol. 10, no. 1, pp. 91–102, Jan. 1992.

[32] Y.T. Chan and K.C. Ho, “A simple and efficient estimator for hyperbolic loca- [57] R.J. Orr and G.D. Abowd, “The Smart Floor: A mechanism for natural user
tion,” IEEE Trans. Signal Processing, vol. 42, no. 8, pp. 1905–1915, Aug. 1994. identification and tracking,” Proc. Conf. Human Factors in Computing Systems
(CHI 2000), The Netherlands, Apr. 2000, pp. 1–6.
[33] R. Schmidt, “Least squares range difference location,” IEEE Trans. Aerosp.
Electron. Syst., vol. 32, no. 1, pp. 234–242, Jan. 1996. [58] P. Bahl and V.N. Padmanabhan, “RADAR: An in-building RF-based user loca-
tion and tracking system,” in Proc. IEEE Conf. INFOCOM 2000, Tel Aviv, Israel,
[34] B.T. Fang, “Simple solutions for hyperbolic and related position fixes,” IEEE Mar. 2000, vol. 2, pp. 775–784.
Trans. Aerosp. Electron. Syst., vol. 26, no. 5, pp. 748–753, Sept. 1990.
[59] M. Youssef, A. Agrawala, and A.U. Shankar, “WLAN location determination via
[35] M. Hellebrandt and R. Mattar, “Location tracking of mobiles in cellular radio clustering and probability distributions,” Proc. IEEE Conf. PerCom 2003,
nets, IEEE Trans. Veh. Technol., vol. 48, no. 5, pp. 1558–1562, Sept. 1999. Mar. 2003, pp. 143–150.

[36] M. McGuire and K.N. Plataniotis, “Dynamic model based filtering for mobile [60] P. Castro, P. Chiu, T. Kremenek, and R. Muntz, “A probabilistic location service
terminal location,” IEEE Trans. Veh. Technol., vol. 52, no. 4, pp. 1012–1031, July for wireless network environments,” in Proc. Ubiquitous Computing 2001,
2003. Portugal, Sept. 2001.

[37] H. Krim and M. Viberg, “Two decades of array signal processing research: The [61] S. Gezici, Z. Tian, G.B. Giannakis, H. Kobayashi, A.F. Molisch, H.V. Poor, and
parametric approach,” IEEE Signal Processing Mag., vol. 13, no. 4, pp. 67–94, July Z. Sahinoglu, “Localization via ultra-wideband radios,” IEEE Signal Processing
1996. Mag., vol. 22, no. 4, pp. 70–84, July 2005.

[38] T. Ojanpera and R. Prasad, Wideband CDMA for Third Generation Mobile [62] N. Patwari, A.O. Hero III, J. Ash, R.L. Moses, S. Kyperountas, and N.S. Correal,
Communications. Boston, MA: Artech House, 1998. “Locating the nodes,” IEEE Signal Processing Mag., vol. 22, no. 4, pp. 54–69, July
2005.
[39] R. Prasad, W. Mohr, and W. Konhauser. Third Generation Mobile
Communication Systems. Boston, MA: Artech House, 2000. [63] T. Ross, P. Myllymaki, and H. Tirri, “A statistical modeling approach to loca-
tion estimation,” IEEE Trans. Mobile Comput., vol. 1, no. 1, pp. 59–69, Jan. 2002.
[40] K.J. Krizman, T.E. Biedka, and T.S. Rappaport. “Wireless position location:
Fundamentals, implementation strategies, and sources of error,” in Proc. IEEE [64] M. Youssef and A.K. Agrawala, “Continuous space estimation for WLAN loca-
Vehicular Technology Conf., New York, NY, May 1997, vol. 2, pp. 919–923. tion determination systems,” in Proc. IEEE 13th Int. Conf. Computer
Communications and Networks, Chicago, IL, Oct. 11–13, 2004, pp. 143–150.
[41] N. Khajehnouri and A.H. Sayed, “A non-line-of-sight equalization scheme for
wireless cellular location,” in Proc. ICASSP, Hong Kong, Apr. 2003, vol. VI, pp. [65] T. Roos, P. Myllymaki, H. Tirri, P. Misikangas, and J. Sievanen, “A probabilistic
549–552. approach to WLAN user location estimation,” Proc. Int. J. Wireless Informat.
Networks, vol. 9, no. 3, July 2002, pp. 155–164.
[42] M.P. Wylie and J. Holtzman, “The non-line of sight problem in mobile location
estimation,” in Proc. IEEE Int. Conf. Universal Personal Communications, 1996, [66] A.M. Ladd, K. Bekris, A. Rudys, G. Marceau, L.E. Kavraki, and D.S. Wallach,
vol. 2, pp. 827–831. “Robotics-based location sensing using wireless ethernet,” Proc. IEEE 8th ACM
MOBICOM, Atlanta, GA, Sept. 2002, pp. 189–204.
[43] S.S. Woo, H.R. You, and J.S. Koh, “The NLOS mitigation technique for posi-
tion location using IS-95 CDMA networks,” in Proc. Vehicular Technology Conf., [67] UCLA Adaptive Systmes Laboratory [Online]. Electrical Engineering Department,
Boston, MA, 2000, vol. 6, pp. 2556–2560. Univ. California, Los Angeles, CA. Available: http://www.ee.ucla.edu/asl [SP]

IEEE SIGNAL PROCESSING MAGAZINE [40] JULY 2005