[Ali H. Sayed, Alireza Tarighat,
`and Nima Khajehnouri]
`
`© DIGITALVISION
`
`Network-Based
`Wireless Location
`[Challenges faced in developing techniques
`for accurate wireless location information]
`
`Wireless 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
`
`Exhibit 2003 Page 1
`
`IV Exhibit 2003
`FedEx v. IV
`Case IPR2017-00787
`
`

`

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

`

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

`

`[12]. Although this method helps resolve the ambiguity
`between the two solutions resulting from (2) and (3), it does
`not combine the third measurement r3 in an optimal man-
`ner. Furthermore, it is not possible in this way to combine
`TOA measurements from more than three BSs (which would
`be useful when the measurements {ri} are subject to inaccu-
`racies and noise).
`This issue can be addressed by combining all the available
`measurements using a least-squares solution as follows (alterna-
`tive techniques such as maximum likelihood (ML) solution can
`be found, e.g, in [49], [50]). Subtracting (2) from (3) gives
`− r2
`= x2
`− 2x2 xm + y2
`− 2y2 ym.
`
`r2
`2
`
`1
`
`2
`
`2
`
`Similarly, subtracting (2) from (4) gives
`− r2
`= x2
`− 2x3 xm + y2
`− 2y3 ym.
`
`r2
`3
`
`1
`
`3
`
`3
`
`Rearranging terms, the above two equations can be written
`in matrix form as
`
`,
`
`(5)
`
`
`
`2
`
`− r2
`− r2
`
`3
`
`K2
`2
`
`K2
`3
`
`1
`
`+ r2
`+ r2
`
`1
`
`
`
`= 1
`2
`
`
`
`xm
`
`ym
`
`
`
`
`x2
`
`x3
`
`y2
`
`y3
`
`
`
`(6)
`
`(7)
`
`.
`
`
`
`1
`
`+ r2
`+ r2
`
`1
`
`2
`
`− r2
`− r2
`
`3
`
`where
`
`= x2
`
`i
`
`+ y2
`
`i
`
`.
`
`K2
`i
`
`Then, (5) can be rewritten as
`Hx = b,
`
`K2
`2
`
`K2
`3
`
`
`
`, b = 1
`2
`
`
`
`xm
`
`ym
`
`
`
`, x =
`
`
`
`y2
`
`y3
`
`x2
`
`x3
`
`
`
`where
`
`H =
`
`If more than three TOA measurements are available, it can be
`verified that (7) still holds with
`
`illustrates this two-stage procedure (measurement and data
`fusion) for an outdoor environment using a cellular network and
`for an indoor environment using a WLAN. Although the focus of
`the article is on network-based location systems, most of the net-
`work-based location algorithms presented here can be used at
`the MS as well. Therefore, from now on, network-based wireless
`location will simply be referred to as wireless location.
`
`DATA FUSION METHODS
`The data fusion step combines measurements from different
`BSs to obtain an estimate of the MS location. Let (xm, ym)
`denote the MS location coordinates in a Cartesian coordinate
`system. Let the coordinates of three BSs (BS1, BS2, and BS3)
`be denoted by (x1, y1), (x2, y2), and (x3, y3), respectively. For
`simplicity of presentation, only the x and y coordinates are
`considered in the derivations and the z coordinate is ignored.
`This corresponds to a case where the BSs and the mobile user
`are located on a relatively flat plane. Without loss of generality,
`the origin of the Cartesian coordinate system is set at BS1, i.e.,
`(x1, y1) = (0, 0). Several data fusion techniques have been
`introduced in the literature; these techniques depend on what
`signal parameters are measured at the BSs [3], [4]. (These are
`several studies in the literature that compare the performance
`of different fusion algorithms, e.g. [26], [27].) The most com-
`mon signal parameters are the time, angle, and amplitude of
`arrival of the MS signal.
`
`TIME OF ARRIVAL DATA FUSION
`The time of arrival (TOA) data fusion method is based on com-
`bining estimates of the TOA of the MS signal when arriving at
`three different BSs. Since the wireless signal travels at the
`speed of light (c = 3 × 108 m/s), the distance between the MS
`and BSi is given by
`
`ri = (ti − t o)c,
`
`(1)
`
`where to is the time instant at which the MS begins transmis-
`sion and ti is the TOA of the MS signal at BSi. The distances
`(r1, r2, r3) can be used to estimate (xm, ym) by solving the fol-
`lowing set of equations (see Figure 3):
`
`=x2m + y2
`= (x2 − xm)2 + (y2 − ym)2
`= (x3 − xm)2 + (y3 − ym)2 .
`
`m
`
`r2
`1
`r2
`2
`r2
`3
`
`(2)
`(3)
`(4)
`
`Without loss of generality, it can be assumed that r1 < r2 < r3.
`One way to solve this overdetermined nonlinear system of
`equations is as follows. First, (2) and (3) are solved for the
`two unknowns (xm, ym) to yield two solutions. As shown in
`Figure 3, (2) and (3) each define a locus on which the MS
`must lie. Second, the distance between each of the two possi-
`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
`
`BS2
`(x2, y2)
`
`BS3
`(x3, y3)
`
`r3
`MS
`(xm, ym)
`BS1
`(0,0)
`
`r2
`
`r1
`
`[FIG3] TOA data fusion using three BSs.
`
`IEEE SIGNAL PROCESSING MAGAZINE [27]
`
`JULY 2005
`
`Exhibit 2003 Page 4
`
`

`

`−x2 xm − y2 ym = r21 r1 + 1
`2
`
`(cid:7)
`
`(cid:8)
`
`− K 2
`
`2
`
`r 2
`21
`
`.
`
`(8)
`
`Similarly, (4) leads to
`−x3 xm − y3 ym = r31 r1 + 1
`2
`
`(cid:7)
`
`(cid:8)
`
`− K2
`
`3
`
`r 2
`31
`
`.
`
`.
`
`
`
`1
`
`1
`
`+ r2
`+ r2
`+ r2
`
`1
`
`2
`
`3
`
`− r2
`− r2
`− r2
`
`4
`
`...
`
`K2
`2
`
`K2
`3
`
`K2
`4
`
`
`
`b = 1
`2
`
`
`
`,
`
`y2
`
`y3
`
`y4
`
`...
`
`x2
`
`x3
`
`x4
`
`...
`
`
`
`H =
`
`In this case, the least-squares solution of (7) is given by ([3], [7])
`(cid:8)−1
`(cid:7)
`ˆx =
`HTH
`
`HTb.
`
`(9)
`
`Rewriting these equations in matrix form gives
`Hx = r1c + d,
`
`(11)
`
`.
`
`
`
`21
`
`− r2
`− r2
`
`31
`
`K2
`2
`
`K2
`3
`
`
`
`d = 1
`2
`
`,
`
`
`
`−r21
`−r31
`
`
`
`c =
`
`where
`
`It is seen that the TOA data fusion method requires accurate
`synchronization between the BSs and MS clocks so that the
`measurements {ri} are adequate approximations for the actual
`distances. Many of the current wireless system standards only
`mandate tight timing synchronization among BSs (see, e.g.,
`[30]). The MS clock itself might have a drift that can reach a few
`microseconds. This drift directly generates an error in the loca-
`tion estimate of the TOA method. In the next subsection we
`present a data fusion technique that combines time DOA
`(TDOA) measurements and helps avoid MS clock synchroniza-
`tion errors [3], [31], [34].
`
`TDOA DATA FUSION
`The TDOA associated with BSi is ti − t1; i.e., it is the difference
`between the TOAs of the MS signal at BSi and BS1. Now we
`define the distance differences
`
`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
`(r21 + r1)2 = K2
`
`− 2x2 xm − 2y2 ym + r2
`
`1
`
`.
`
`2
`
`Expanding and rearranging terms gives
`
`(x2, y2)
`
`α2
`
`BS
`
`MS
`
`(xm,ym)
`
`r2
`
`r2 sin α2
`r1 sin α1
`
`r1
`
`α1
`
`(x1, y1)
`
`BS
`
`r1 cos α1
`
`r1 cos α2
`
`[FIG4] Combining AOA measurements.
`
`ri1
`
` = ri − r1
`= (ti − t o)c − (t1 − t o)c = (ti − t1)c.
`
`(10)
`
`H =
`
`IEEE SIGNAL PROCESSING MAGAZINE [28]
`
`JULY 2005
`
`which yields the following least-squares intermediate solution
`(cid:8)−1
`(cid:7)
`ˆx =
`HT(r1c + d).
`HTH
`
`(13)
`
`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.
`
`ANGLE OF ARRIVAL DATA FUSION
`At the BS, angle of arrival (AOA) estimates can be obtained
`using an antenna array. The direction of arrival of the MS sig-
`nal can be calculated by measuring the phase difference
`between the antenna array elements or by measuring the
`power spectral density across the antenna array in what is
`known as beamforming (see, e.g., [37] and the references
`therein). By combining the AOA estimates of two BSs, an esti-
`mate of the MS position can be obtained (see Figure 4). The
`number of BSs needed for the location process is less than that
`
`Equation (11) can be used to solve for x in terms of the
`unknown r1 to yield
`
`
`x = r1H
`
`−1c + H−1d.
`
`(12)
`
`Substituting this intermediate result into (2) leads to a quadratic
`equation in r1. Solving for r1 and substituting the positive root
`back into (12) yields the final solution for x.
`If more than three BSs are involved in the MS location, (11)
`still holds with
`
`
`
`21
`
`− r2
`− r2
`− r2
`
`31
`
`41
`
`K2
`2
`
`K2
`3
`
`K2
`4
`
`...
`
`
`
`, d = 1
`2
`
`
`
`−r21
`−r31
`−r41
`...
`
`
`
`, c =
`
`
`
`x2
`
`x3
`
`x4
`
`...
`
`y2
`
`y3
`
`y4
`
`...
`
`
`
`Exhibit 2003 Page 5
`
`

`

`A LARGE PROPORTION OF ALL 911
`CALLS ORIGINATE FROM MOBILE PHONES,
`THE LOCATION OF WHICH SHOULD BE
`DETERMINED WITH SUFFICIENT ACCURACY.
`
`the angular orientation of
`the
`installed antenna
`arrays. The issue of NLOS
`is discussed in another sec-
`tion. For the error in the
`angular orientation of the
`antenna arrays, some test
`measurements can be conducted to calibrate the orientation
`of the antenna array.
`
`of the TOA and TDOA meth-
`ods. Another advantage of
`AOA location methods is
`that they do not require BS
`or MS clock synchroniza-
`tion. However, one disad-
`vantage of the AOA method
`is that antenna array structures do not currently exist in sec-
`ond generation (2G) cellular systems. Still, the use of antenna
`arrays is planned in third generation (3G) cellular systems,
`such as UMTS and cdma2000 networks [38], [39].
`More generally, assume n BSs estimate the AOA of the MS
`signal, and the goal is to combine these measurements to esti-
`mate the MS location. As indicated in Figure 4, let α2 denote the
`AOA of the MS signal at BS2. Then
`(cid:2)
`(cid:1)
`(cid:1)
`
`(cid:2)
`
`=
`
`xm
`ym
`
`r1 cos α1
`r1 sin α1
`
`and
`
`(cid:2)
`
`(cid:1)
`
`=
`
`(cid:1)
`
`xm
`ym
`
`x2
`y2
`
`(cid:2)
`
`(cid:1)
`
`+
`
`r2 cos α2
`r2 sin α2
`
`Likewise, for any other BSi,
`(cid:2)
`(cid:1)
`(cid:1)
`
`=
`
`xm
`ym
`
`(cid:2)
`
`(cid:1)
`
`+
`
`xi
`yi
`
`ri cos αi
`ri sin αi
`
`(cid:2)
`
`(cid:2)
`
`.
`
`.
`
`Collecting these relations into a single equation yields
`Hx = b,
`
`where
`
`HYBRID DATA FUSION TECHNIQUES
`In TOA, TDOA, and AOA methods, two or more BSs are involved
`in the MS location process. In situations where the MS is much
`closer to one BS (serving site) than the other BSs, the accuracy
`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
`requires that the MS reduce its transmitted power when it
`approaches a BS. In these cases, an alternate data fusion proce-
`dure is used to obtain AOA estimates and combine them with
`TOA estimates (see, e.g., [40]). In real scenarios, the accuracy of
`TOA and AOA estimates is usually a function of the environ-
`ment. For example, in rural areas, AOA measurements can be
`more accurate than TOA measurements if a large-size antenna
`array is deployed. On the other hand, TOA measurements are
`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
`AOA and TOA of the MS. From (9), the least-squares estimate of
`(xm, ym) using TOA measurements is given by
`(cid:1)(cid:11) (cid:12)
`(cid:9)
`HT
`TOAHTOA
`
`
`
`xm
`ym
`
`(cid:10)−1
`
`=
`
`HT
`TOAbTOA,
`
`(16)
`
`TOA
`
`where
`
`x2
`
`x3
`
`y2
`
`y3
`
`K2
`2
`
`K2
`3
`
`2
`
`− r2
`− r2
`
`3
`
`1
`
`+ r2
`+ r2
`
`1
`
`
`
`...
`
`K2
`
`n − r2n + r2
`
`1
`
`
`
`bTOA = 1
`2
`
`
`
`,
`
`...
`
`...
`
`xn
`
`yn
`
`
`
`HTOA =
`
`= x2
`
`i
`
`+ y2
`
`i
`
`.
`
`K2
`i
`
`.
`
`(14)
`
`and
`
`
`
`r1 cos α1
`r1 sin α1
`x2 + r2 cos α2
`y2 + r2 sin α2
`...
`xn + rn cos αn
`yn + rn sin αn
`
`
`
`(cid:1)
`
`(cid:2)
`
`xm
`ym
`
`, b =
`
`, x =
`
`
`
`1 0
`0 1
`
`1 0
`0 1
`...
`...
`
`1 0
`0 1
`
`
`
`H =
`
`The least-squares solution for x is then
`(cid:10)−1
`(cid:9)
`HTH
`
`ˆx =
`
`HTb.
`
`(15)
`
`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
`
`
`
`xm
`ym
`
`Likewise, from (15), the least-squares estimate of (xm, ym)
`using only AOA measurements is given by
`(cid:1)(cid:11) (cid:12)
`(cid:9)
`HT
`AOAHAOA
`
`(cid:10)−1
`
`=
`
`HT
`AOAbAOA
`
`(17)
`
`AOA
`
`IEEE SIGNAL PROCESSING MAGAZINE [29]
`
`JULY 2005
`
`Exhibit 2003 Page 6
`
`

`

`measurements αi are corrupted by NLOS effects and by noise.
`Hence, the available measurements are
`¯αi =αi + vαi
`¯ri =ri + vri
`
`(20)
`
`.
`
`(18)
`
`
`
`r1 cos α1
`r1 sin α1
`x2 + r2 cos α2
`y2 + r2 sin α2
`...
`xn + rn cos αn
`yn + rn sin αn
`
`
`
`bAOA =
`
`,
`
`
`
`1 0
`0 1
`
`1 0
`0 1
`...
`...
`
`1 0
`0 1
`
`
`
`HAOA =
`
`The final location estimate could be taken as a linear combina-
`tion of the two estimates, say as
`(cid:1)(cid:7) (cid:8)
`(cid:1)(cid:7) (cid:8)
`
`
`
`xm
`ym
`
`= η
`
`
`
`xm
`ym
`
`
`+ (1 − η)
`
`(cid:1)(cid:7) (cid:8)
`
`xm
`ym
`
`TOA
`
`AOA
`
`(19)
`
`where vαi and vri represent the corruptions to αi and ri. One
`scheme for recovering (xm, ym) from the measurements
`{¯ri, ¯αi} is based on formulating a constrained optimization
`problem that reduces the effect of NLOS conditions on loca-
`tion accuracy. The constraints will be a reflection of the topol-
`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
`=r2
`+ r2
`=r2
`+ r2
`...
`where the angles {γi} are functions of {αi, θi}. This formulation
`is easily extendable to the case of n BSs. Then, one could pose
`the problem of estimating the {αi, ri} by solving
`(cid:7) ¯αi − αi
`(cid:8)2 +
`(cid:7) ¯ri − ri
`n(cid:9)
`i=1
`
`{ˆαi, ˆri}n
`i=1
`
`= arg min{αi,ri}
`
`σαi
`
`σri
`
`(cid:8)2
`
`(23)
`
`r2
`12
`r2
`23
`
`1
`
`2
`
`− 2r1 r2 cos γ1
`− 2r2 r3 cos γ2
`
`2
`
`3
`
`(21)
`(22)
`
`where the positive parameter η is chosen depending on the rela-
`tive accuracy of the TOA and AOA measurements.
`
`DATA FUSION WITH NLOS CONDITIONS
`An important source of error in TOA-based and AOA-based
`data fusion is the case where there is no line-of-sight from the
`mobile station to the BSs. A geometrically constrained data
`fusion scheme could be used to reduce the effect of such NLOS
`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
`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
`measurements ri in (1) are generally corrupted by NLOS off-
`sets arising from the presence of obstacles between the MS and
`the BS, as well as by measurement noise. Similarly, the AOA
`
`Base Station
`Mobile Station
`
`(x3, y3)
`BS3
`
`r31
`
`γ3
`
`α3
`r3
`γ2
`
`BS1
`(0,0)
`
`r1
`
`α1
`
`θ1
`
`r12
`
`γ1
`r2
`θ2
`
`r23
`
`α2
`
`BS2
`(x2, y2)
`
`[FIG5] A schematic of a cellular network topology with three BSs.
`
`subject to
`
`r2
`12
`r2
`23
`
`= r2
`= r2
`
`1
`
`2
`
`+ r2
`+ r2
`
`2
`
`3
`
`− 2r1 r2 cos(π − (α1 + α2))
`− 2r2 r3 cos(π − (α3 + (θ2 − α2)))
`...
`
`where σ 2ri is the variance of the distance error and σ 2αi is the
`
`
`variance of the angle error (both at the i th BS). There are some
`
`
`known methods for estimating the variances σ 2ri and σ 2αi (see,
`e.g., [42]–[44]). These methods generally use the time history of
`the signals, or the scattering model of the environment, to esti-
`mate the noise variance, as in
`K−1(cid:9)
`(¯ri(n) − µri
`n=0
`
`)2,
`
`(24)
`
`σ 2
`ri
`
`≈ 1
`K
`
`where
`
`µri
`
`= 1
`K
`
`¯ri(n)
`
`(25)
`
`K−1(cid:9)
`n=0
`for K ≈ 400 and where ¯ri(n)is the measurement of ri at experi-
`ment n. This is also true for σ 2
`αi. Minimizing (23) results in esti-
`mates of {ri, αi}. Using the equalized values in (8) or (9) will
`result in improved location accuracy.
`
`
`
`IEEE SIGNAL PROCESSING MAGAZINE [30]IEEE SIGNAL PROCESSING MAGAZINE [30]
`
`
`
`JULY 2005JULY 2005
`
`Exhibit 2003 Page 7
`
`

`

`where v(n) is additive white
`Gaussian noise with variance
`v , {h(n)} is the fading channel
`σ 2
`gain, and A is an unknown
`amplitude (real value) that
`accounts for the gain of the
`static channel if fading were not present. The autocorrelation
`function of h(n) is defined as
`∗(n − i ).
`Rh(i ) = Eh(n)h
`
`(27)
`
`Without loss of generality, we will assume that the sequence
`h(n) has unit variance, i.e., Rh(0) = 1. The ML estimates of
`{τ o, h(n)} are defined by
`
`{ˆτ , ˆh(n)} = arg max
`
`τ,h(n)
`
`[P(r(1)··· r(K)|τ, h(n))],
`
`(28)
`
`where the likelihood function P(r(1)··· r(K)|τ, h(n)) is of the
`form
`(cid:3)
`(cid:1)
`−C2
`
`K(cid:2)
`n=1
`
`1 K
`
`C1 exp
`
`(cid:2)r(n) − Ah(n)s(n − τ )(cid:2)2
`
`(29)
`
`for some positive constants C1 and C2 that are independent of
`the unknowns {τ, h(n)}. Thus, the ML estimates of {τ, h(n)} are
`given by [25]
`
`{ˆτ , ˆh(n)} = arg max
`
`τ,h(n)
`
`JML(τ, h(n)),
`
`(30)
`
`where the cost function JML is given by
`K(cid:2)
`Re[r (n)h∗(n)s∗(n − τ )]
`JML(τ, h(n)) = 2A
`K
`n=1
`K(cid:2)
`− A2
`K
`n=1
`
`|h(n)|2|s(n − τ )|2.
`
`This construction requires an infinite dimensional search
`over {τ, h(n)} and is not feasible in practice even when τ and
`h(n) are evaluated over a dense grid. To arrive at a feasible
`algorithm, we assume the channel variations are sufficiently
`slow, namely, that h(n) is piecewise constant over intervals of
`N samples. The value of N depends on the environmental con-
`ditions; an optimal choice for N is discussed later in this
`
`THE WIRELESS ENVIRONMENT
`From the previous discussion, it is clear that most wireless loca-
`tion methods depend on combining estimates of the TOA and/or
`AOA of the received signal at different BSs. Estimating the TOA
`and amplitude of arrival (AmpOA) of wireless signals has been
`studied in many works since it
`is required in many wireless
`system designs for online signal
`decoding purposes. Yet, esti-
`mating these same parameters
`for wireless location purposes is
`challenging for several reasons.
`■ Low SINR conditions. Cellular systems tend to suffer
`from high multiple access interference levels that
`degrade the SNR of the received signal. Moreover, the
`ability to detect the MS signal at multiple BSs is limited
`by the use of power control algorithms, which require
`the MS to decrease its transmitted power when it
`approaches the serving BS. This fact, in turn, decreases
`the received MS signal power level at other BSs. In a typi-
`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
`low as −40 dB, which poses a challenge for wireless loca-
`tion in such environments.
`■ Channel fading and Doppler frequency. In wireless location
`applications, the estimation period can be considerably long
`(it might reach several seconds). Thus, in a fading environ-
`ment, the channel values can change significantly over the
`location estimation period. In this way, the channel values can
`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
`first arriving ray of the multipath channel is vital. In gen-
`eral, the first arriving (prompt) ray is assumed to corre-
`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
`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,
`causing errors in the prompt ray TOA and AmpOA estima-
`tion. These errors degrade the performance of wireless
`location algorithms; as such, they demand careful consider-
`ations (see, e.g., [9]–[11], [28], and [29]).
`In the sections that follow, some algorithms for TOA and
`AOA estimation are described. These algorithms exploit the
`nature of the wireless channel and are robust to low SNR and
`fading conditions [25], [51].
`
`TOA ESTIMATION
`The aim of a TOA estimation scheme is to estimate an unknown
`delay, τ o, of a known sequence {s(n)}. (At the serving site, the
`MS signal can be decoded with reasonably high accuracy; thus,
`it can be assumed to be known almost perfectly.) The signal is
`
`assumed initially to be transmitted over a single path fading
`channel. A total of K measurements r(n) are collected, which
`are related to s(n) via
`r(n) = A h(n) s(n − τ o) + v(n), n = {1, . . . , K },
`
`(26)
`
`WIRELESS LOCATION TECHNOLOGIES
`FALL INTO TWO MAIN CATEGORIES:
`MOBILE BASED AND NETWORK BASED.
`
`
`
`IEEE SIGNAL PROCESSING MAGAZINE [31]IEEE SIGNAL PROCESSING MAGAZINE [31]
`
`
`
`JULY 2005JULY 2005
`
`Exhibit 2003 Page 8
`
`

`

`where Jo(·) is the first-order Bessel function, Ts is the sampling
`period of the received sequence {r(n)}, and fD is the maximum
`Doppler frequency. Therefore, (32) shows that the coherent
`averaging interval N should be adapted according to the channel
`autocorrelation function.
`
`TOA ESTIMATION WITH ANTENNA ARRAY
`Further improvement in the TOA estimation can be accomplished
`by deploying an antenna array at the BS [51]. Thus assume that
`the BS uses an Na-element antenna array. Then, in contrast to
`(26), the received signal at time n is now an Na × 1 vector:
`r(n) = ah(n)s(n − τ o) + v(n),
`
`(33)
`
`max
`
`ˆ
`
`(Note that we are assuming a scat-
`tered MS model. Since in a typical cel-
`lular system the mobile station is
`usually far from the BS, the reflected
`rays from the scatterers around the
`MS reach the BS at close angles.
`These reflected rays cause a fading
`effect in h(n) with almost the same
`AOA. Moreover, it is assumed that any
`bias in the direction or the angle of
`the arrays can be ignored from the
`derivations through some calibration
`pro