,~ itE§' ~ehicular Techn6logy Con£, Phoenix, AZ May 5-7, 1997
`
`\· ,\~
`
`Wireless Position Location: Fundamentals,
`Implementation Strategies, and Sources of Error
`
`Kevin J. Krizmant, Thomas E. Biedkatt, and Theodore S. Rappaportt
`t Mobile and Portable Radio Research Group +Raytheon E-Systems, Inc.
`Bradley Dept. of Electrical Engineering
`Greenville Division
`Greenville, TX 75403
`Virginia Tech
`Blacksburg, VA 24061
`Invited Paper
`
`Abstract
`
`II. BASIC POSITION LOCATION TECHNIQUES
`
`This paper presents an overview of basiC RF posi(cid:173)
`tion location strategies which are feasible for ubiq(cid:173)
`uitous deployment by cellular-type wireless system
`providers. Limitations on practical ability to locate
`mobile RF transmitters and the effects of real world
`channel degradation on direction-finding and time dif(cid:173)
`ference of arrival systems are also discussed.
`
`I. INTRODUCTION
`
`The ability to locate the source of RF transmissions
`has been of considerable interest for many years. His(cid:173)
`torically, the main interest for wireless position lo(cid:173)
`cation has been for rnilitary, law-enforcement, and
`safety applications - either to find people in distress
`or to isolate and neutralize people who are causing
`distress. More recently, interest has also emerged in
`using wireless position location for Intelligent Trans(cid:173)
`portation System applications such as incident man(cid:173)
`agement, traffic routing, fleet management, and E-911
`telephoneservice (1].
`In this paper, we discuss the fundamental function
`of position location (PL) techniques that are compat(cid:173)
`ible with the existing base of mobile users in a large(cid:173)
`scale (cellular-type) position location system. We also
`consider performance limitations and sources of er(cid:173)
`ror in direction finding (DF) and time-difference-of(cid:173)
`arrival (TDOA) PL techniques. Finally we focus on
`the effects of multipath propagation as a significant
`source of estimation error for cellular-type position
`location and examine some possible methods of miti(cid:173)
`gating the detrimental effects of multipath.
`
`This work was. supported by the MPRG industrial affiliates
`pro~am.
`
`A number of system designs have been proposed as
`feasible solutions to the wireless PL problem [1]. Be(cid:173)
`cause there are over 48 million handsets in use in the
`U.S. alone (as of mid-1997), any widely deployed PL
`system will likely need to be compatible with the ex(cid:173)
`isting base of operational handsets [2], [3], [4]. GPS(cid:173)
`based and other techniques where synchronization
`and/ or calculations must be performed by the mo(cid:173)
`bile transmitter would require replacing most existing
`mobile units with modified handsets. Such replace(cid:173)
`ment may not be feasible in the near term. We there(cid:173)
`fore limit discussion in this paper to those techniques
`which can be used with existing handsets. PL tech(cid:173)
`niques that can be used with existing handsets may be
`classified into one of three basic approaches: beacon
`location techniques, direction finding techniques, and
`time difference of arrival techniques. Each of these
`methods is briefly described below.
`Beacon location methods involve placing a large
`number of simple receivers (beacons) at known loca(cid:173)
`tions in a region of interest. Beacons might be placed
`throughout a city or spread out along roads and high(cid:173)
`ways. Each beacon then listens or "sniffs" for a known
`signal from a mobile transmitter and measures there(cid:173)
`ceived signal strength. The relative link quality be(cid:173)
`tween the beacon and the mobile location is used to
`determine the location of the mobile. The beacon
`which receives the strongest signal fro~ a mobile is
`deemed to be the closest beacon to the mobile. The
`coordinates of that beacon (or perhaps a weighted av(cid:173)
`erage of several nearby beacons) which receives the
`strongest signal from a given mobile then becomes an
`estimate of the mobile location. The advantage of
`beacon-type systems is in the simplicity and low cost
`of implementation. The disadvantage of beacon-type
`
`Apple Inc. Exhibit 1006 Page 1
`
`

`
`systems is that they typically provide poor quality
`position location estimates.
`Under a 1996 FCC Rule Making Order [2], wireless
`service providers are required to provide a cell-site lo(cid:173)
`cation mechanism in their wireless systems by 1997
`as a step toward providing more accurate location of
`cellular and PCS mobile units in the future. This can
`be viewed as a crude type of beacon location system,
`where the individual base-stations are the beacons,
`and a single-site location (SSL) system is used. By
`about 2002, service providers are required to achieve
`the capability to identify the location of a mobile unit
`making a 911 call to within a radius of no more than
`125 meters in 67 percent of all cases.
`In order to
`provide mobile position coordinates with enough pre(cid:173)
`cision to satisfy future requirements, techniques other
`than beacon location will be required.
`Pbssibly the most intuitive PL method uses the
`angle-of-arrival (AOA) of a signal received from a mo(cid:173)
`bile at two or more base stations. From the AOA
`estimate, a line of bearing (LOB) from the base sta(cid:173)
`tion to the mobile transmitter can be drawn. Multi(cid:173)
`ple LOBs, drawn from different base station locations,
`intersect at the estimated location of the mobile. Es(cid:173)
`timation of AOA, commonly referred to as DF, can
`be accomplished either with a mechanically steered
`narrow beamwidth antenna or with an electronically
`steered array of antennas. The accuracy of DF tech(cid:173)
`niques depends on a number of factors (discussed sub(cid:173)
`sequently). The advantages of DF techniques (versus
`TDOA) are that a PL estimate may be determined
`with as few as two base stations (provided the mo(cid:173)
`bile is not on or near a line joining the two base sta(cid:173)
`tions), and that no time synchronization between base
`stations is required. The disadvantages of a DF sys(cid:173)
`tem are that they require relatively large and complex
`hardware, and that the position estimate degrades as
`the mobile moves farther from the base station(s).
`Another PL technique, TDOA, calculates the differ(cid:173)
`ences in time-of-arrival of a mobile signal at multiple
`(two or more) pairs of stations. Each TDOA mea(cid:173)
`surement yields a hyperbolic curve along which the
`mobile may lie. The intersection of these curves then
`yields an estimate of position. Assuming that mul(cid:173)
`tiple base stations receive a signal transmitted by a
`mobile user, and that all of the base stations have
`a synchronized time reference, correlation techniques
`may be employed to estimate the TDOA of the mobile
`sign_al at each. base station.
`
`Given the TDOA, we can calculate the difference
`in propagation distance to each base station, since
`the propagation distance is simply the propagation
`time multiplied by the speed of propagation ( approx(cid:173)
`imately 3 x 108 m/ s ) . Expressing. the relationship
`mathematically (for a two dimensional case),
`
`~,j = cti,j =
`(1)
`.j(xi- x) 2 + (Yi- y)2 - .j(xj- x) 2 + (Yj- y)2
`
`where Xi,j and Yi,j are the (known) coordinates of the
`ith and jth base stations, ti,j is the (estimated) differ(cid:173)
`ence in propagation time from the mobile to the ith
`and jth base stations, c is the propagation speed, Ri,j
`is the (calculated) difference in propagation distance
`from the mobile to the ith and jth base stations, and
`x and y are the (unknown, but desired) coordinates
`of the mobile transmitter.
`From two base stations, we find one equation (a hy(cid:173)
`perbola) with two unknowns (the x, y coordinates of
`the mobile), so another independent TDOA measure(cid:173)
`ment is needed in order to generate a position solu(cid:173)
`tion. Thus, at least three base stations are required
`to perform position location with TDOA. The set of
`equations (1) is nonlinear, but many efficient solution
`methods have been developed, e.g., [1], [5], [6], [7].
`A comment is needed here on the problem of PL
`estimation when no line of sight exists. A basic as(cid:173)
`sumption behind both DF and TDOA techniques is
`that a line-of-sight propagation path exists between
`the mobile and the base stations. Given a line-of-sight
`path, even if multi path is present, we have only to de(cid:173)
`termine which path is the first-arriving path (e.g. by
`cross-correlation) in order to identify the line-of-sight
`path. However, if no line-of-sight exists, PL accuracy
`will suffer. This remains an open problem.
`
`III. DF IMPLEMENTATION ISSUES
`As mentioned earlier, AOA may be measured ei(cid:173)
`ther with a mechanically steered narrow beamwidth
`antenna or with a fixed array of antennas. Clearly the
`more practical approach for the problem here is to use
`an antenna array. A common DF array configuration
`is a uniform linear array (ULA). In ULA, the anten(cid:173)
`nas lie on a straight line and have equal inter-element
`spacing. Typically the inter-element spacing is on the
`order of one-half the wavelength corresponding to the
`received signal carrier frequency. The number of ele(cid:173)
`ments in such an array typically ranges from 4-10.
`
`Apple Inc. Exhibit 1006 Page 2
`
`

`
`In a high performance DF system, each antenna
`feeds a separate receiver, with the mixers and A/D
`converters in all receivers being driven by the same
`oscillators and clocks. This must be done in order
`to preserve coherence between the signals received at
`each antenna. Once the received signals have been
`sampled, they are converted to complex baseband for(cid:173)
`mat. The signals are then passed to DSP hardware,
`where the DF algorithm resides. A wide variety of
`algorithms can be used to estimate AOA, each having
`its own advantages and disadvantages (e.g., see [8]).
`The classical approach to DF is to steer the main
`beam of the array over the region of interest and mea(cid:173)
`sure the received power. This is referred to as the
`beamforming approach. The main drawback of beam(cid:173)
`forming is that the angular resolution is limited by the
`beamwidth of the array. The half-power beamwidth
`of a' 1inear array of antennas is 0 approximately equal
`to 1/ L (in radians,) where L is the array aperture.
`In many situations we must be able to resolve
`closely spaced multipath delays. In flat fading, the
`delay spread is very small relative to the signal
`bandwidth, so the multipath components will all be
`strongly correlated. Since delay spread and angular
`spread are interrelated [9), [10), we must often be able
`to handle small angular spread.
`Resolving closely spaced correlated signals can be
`accomplished using a Maximum Likelihood (ML) DF
`algorithm, such as used in [4). These algorithms re(cid:173)
`quire a multidimensional search, but efficient tech(cid:173)
`niques for performing such a search have been devel(cid:173)
`oped. 0 Another approach is to use spatial smoothing
`followed by some high resolution algorithm such as
`MUSIC [11), [12), (13], (14]. This approach is less
`computationally intensive but does not perform as
`well as an ML technique. Besides the algorithm se(cid:173)
`lected, factors which affect DF accuracy include SNR,
`integration time, number of antennas, hardware non(cid:173)
`idealities, and array calibration error.
`Among the issues in DF implementation, the most
`critical in terms of limiting performance is array cal(cid:173)
`ibration. High resolution DF requires that the ar(cid:173)
`ray response (effectively the array beam pattern) be
`known very precisely. Typically this requires calibrat(cid:173)
`ing the antenna array, since the array will not behave
`ideally because of such effects as antenna coupling,
`near-field scattering, etc. Array calibration must be
`periodically ~pdated as well. Calibrating an array
`mo~nted on a tower in an urban area may be very
`
`difficult and expensive. This, combined with possi(cid:173)
`ble zoning and aesthetic problems associated with in(cid:173)
`stalling an array ofantennas, are impediments to us(cid:173)
`ing DF-based PL systems.
`
`IV. TDOA IMPLEMENTATION ISSUES
`
`The classical approach to estimating TDOA is to
`compute the conventional cross-correlation of a sig(cid:173)
`nal arriving at two base stations. The TDOA esti(cid:173)
`mate is taken as the delay which maximizes the cross(cid:173)
`correlation function. The cross-correlation is also used
`to determine at which base station the signal arrived
`first. These two pieces of information yield an unam(cid:173)
`biguous hyberbolic curve. A key limitation to conven(cid:173)
`tional cross-correlation is that the time resolution of
`the TDOA estimate, in the presence of multipath, is
`limited to approximately 1/ B, where B is the band(cid:173)
`width of the received signal. For example, when re(cid:173)
`ceiving a 1 MHz signal, the time delays can only be
`resolved to within 1p,s, or within 300 meters.
`The temporal resolution limit of conventional cross(cid:173)
`correlation can be explained by analogy with the prob(cid:173)
`lem of resolving closely spaced sinusoids. It is well
`known that a periodogram cannot resolve two sinu(cid:173)
`soids that are more closely spaced in frequency than
`1/N, where N is the number of data samples. In the
`frequency domain, the true spectrum of two sinusoids
`is smeared by convolution with the Fourier transform
`of a rectangular window. Similarly, the true temporal
`characteristics of the channel are smeared by window(cid:173)
`ing in the frequency domain. If the temporal features
`are finer than 1/ B where B is the bandwidth of the
`signal, the temporal features cannot be resolved, at
`least by using cross-correlation.
`Assume for the moment that we cannot resolve mul(cid:173)
`tipath components that arrive within 1 /B seconds of
`each other. Table I shows the distance that a signal
`can propagate in 1/ B seconds. This is the potential
`PL error that can occur if the first arriving compo(cid:173)
`nent is not resolved. Note that even with IS-95 it will
`be necessary to resolve multipath co~ponents that
`are more closely spaced than 1 j B. This illustrates
`the need for high resolution estimation of TDOA. A
`general approach for performing high resolution esti(cid:173)
`mation of TDOA is discussed later, but first we dis(cid:173)
`cuss other other factors which affect the accuracy of
`a TDOA position estimate.
`
`Apple Inc. Exhibit 1006 Page 3
`
`

`
`Standard Bandwidth PL Error - cj B
`10,000 m
`30kHz
`AMPS
`200kHz
`1,500 m
`GSM
`1.25 MHz
`240m
`IS-95
`TABLE I
`PL ERROR WITH MULTIPATH TIME-DELAY RESOLUTION
`LIMITED TO 1/ B.
`
`A. Signal Processing Considerations
`
`The Cramer-Rao Lower Bound ( CRLB) places a
`lower bound on the variance of a parameter estimate
`that can be achieved by any unbiased estimator. The
`CRLB for TDOA estimation depends on SNR, Inte(cid:173)
`gration Time, Signal Bandwidth, and number of mul(cid:173)
`tipath components present. Ho:wever, [3] reports that
`in a practical implementation of a TDOA PL sys(cid:173)
`tem, hardware limitations and channel degradations
`are dominant sources of TDOA estimation error.
`The strength of the signal (SNR) received at each
`base station directly impacts the quality of the TDOA
`estimate and determines the best PL estimate we can
`expect to achieve. In the case of very low SNR sig(cid:173)
`nals, the abiltiy to form good TDOA estimates can
`be significantly impaired. Since cellular-type wire(cid:173)
`less systems are designed to minimize the number
`of base stations receiving a high-strength signal, the
`lack of signals with adequate SNR at multiple base
`staions can cause significant variation in PL accuracy
`in TDOA systems. We should note however that ac(cid:173)
`curate TDOA estimates can be obtained even if only
`one of the base stations receives a signal with high
`SNR.
`Co-channel interference effectively reduces the SNR
`of the signal and thus degrades the quality of the
`TDOA estimate by raising the CRLB. In highly
`crowded RF environments, co-channel interference
`has the potential to be a significant degrading factor
`in PL estimates. However, measurements reported in
`[15] show that ev~n in urban/suburban cellular-type
`radio environments, co-channel interference is not typ(cid:173)
`ically a significant problem.
`
`B. Hardware Requirements
`
`In order to implement a TDOA-based PL system,
`the receivers at all cell-sites must be synchronized.
`Thi~ presents. a disadvantage in complexity as com-
`
`pared to a single or dual site DF system. One way to
`provide synchronization is to derive the timing refer(cid:173)
`ence from GPS. Another approach is to use Rubidium
`or Cesium clocks. It is important that all mixers and
`oscillators in the receiver be derived from exactly that
`same timing reference.
`It also is important that the phase response of the
`receiver be as linear as possible. This is to allow mea(cid:173)
`surement of small phase differences. It might be neces(cid:173)
`sary to compensate for non-linear phase response by
`calibrating the receiver by injecting a known signal
`into the front end.
`
`C. Channel Effects
`
`Mobile radio channels are distinctive for their mul(cid:173)
`tipath propagation characteristics [10]. Multipath re(cid:173)
`duces the accuracy of TDOA estimates in position
`location systems. Multiple copies of the same signal,
`arriving at different times, cause small scale fading
`(possibly leading to reduced SNR) and increase the
`variance of TDOA estimates.
`References [15] and [3] both report that mitiga(cid:173)
`tion of multipath, based on field experience, is a crit(cid:173)
`ical aspect of accurate PL estimates. Among the
`performance-limiting factors discussed above, multi(cid:173)
`path propagation has the potential to be a dominant
`factor for PL estimate degradation in TDOA systems.
`Under many practical, "real world" channel condi- ·
`tions, if steps are not taken to mitigate the effects
`of multipath, it will not be possible to estimate the
`position of the mobile within the limits required for
`many applications.
`It has been noted that the temporal resolution of
`conventional approaches is limited by the autocorre(cid:173)
`lation width of the transmitted signal. However, other
`approaches can be used to achieve better resolution.
`In the area of frequency estimation, it is well known
`that sinusoids which are more closely spaced than 1/T
`where Tis the observation interval cannot be resolved
`by conventional Fourier-based techniques, such as the
`periodogram. Other techniques which make more as(cid:173)
`sumptions about the data can achieve higher resolu(cid:173)
`tion, such as by fitting an autoregressive ( AR) model
`to the data, or by modeling the data as sinusoids in
`white noise (e.g., see [16]). In an analogous fashion
`there exist methods for high resolution estimation of
`multipath delay parameters.
`One approach is to use a high resolution frequency
`estimator with the time-series replaced by an esti-
`
`Apple Inc. Exhibit 1006 Page 4
`
`

`
`~' .'r
`
`mated channel transfer function [17]. Model the chan(cid:173)
`nel impulse response h(t) as a sum of discrete multi(cid:173)
`path components,
`
`M
`
`h(t) = L ai8(t- ri),
`
`i=l
`
`{2)
`
`where .there are M discrete delay components, and
`O:i is the complex amplitude for delay 'Ti· Then the
`Fourier transform of h ( t) yields the transfer function
`
`M
`H(w) = Laie-jwn.
`i=l
`
`(3)
`
`We see that the transfer function consists of a sum of
`M discrete frequency components. Thus any spec(cid:173)
`trum estimator can also be used to estimate time
`delays by replacing the time-series in the frequency
`estimator with the transfer function H ( w). Other
`high resolution approaches can be derived from the
`perspective of Maximum Likelihood, or by exploiting
`more information on the channel or on the transmitted
`signal. For example, see [18] and references therein.
`
`V. SUMMARY
`
`Under the constraint of being compatible with the
`large installed base of cellular-type mobile transmit(cid:173)
`ters, direction finding and/ or TDOA systems emerge
`as practical solutions to the wireless position location
`problem. Each approach has its advantages.
`DF systems have the advantage that they require
`as few as two base stations in order to formulate a PL
`estimate and they do not require inter-base- station
`time synchronization. The disadvantages of DF sys(cid:173)
`tems are relatively expensive hardware and the need
`to compute and maintain accurate array calibration.
`TDOA systems are relatively inexpensive to imple(cid:173)
`ment. However, they require "hear ability" at· a mini(cid:173)
`mum of three base stations, and all base stations must
`be synchonized with each other to nanosecond accu(cid:173)
`racy. Both systems require the resolution of closely
`spaced multipath components in order to provide de(cid:173)
`sired accuracy. It is believed that the cost and mainte(cid:173)
`nance advantages of TDOA-based systems may make
`TDOA-based systems a more attractive PL solution.
`
`REFERENCES
`
`[1] T.S. Rappaport, J.H. Reed, and B.D. Woerner, "Position
`·.location using wireless communications on highways of the
`
`[2]
`
`[4]
`
`[9]
`
`future," IEEE Communications Magazine, vol. 34, no. 10,
`pp. 33-41, Oct 1996.
`"Revision of the commission rules to ensure compatibility
`with enhanced 911 emergency calling systems," CC Docket
`No. 94-102, RM-8143, FCC, Jul. 26, 1996.
`[3] L.A. Stilp, "Time difference of arrival technology for lo(cid:173)
`cating narrowband cellular signals," SP IE Conference on
`Voice, Data, and Video Communication, pp. 134-144, Oct
`1995.
`"Direction finding and
`J. Kennedy and M.C. Sullivan,
`smart antennas using software radio architectures," IEEE
`Commun. Magazine, pp. 62-68, May 1995.
`[5] B.T. Fang, "Simple solutions for a hyperbolic and related
`IEEE 'Jlrans. on Aerosp. and Elect. Sys(cid:173)
`position fixes,"
`tems, vol. 26, no. 5, pp. 748-753, Sept 1990.
`[6] O.J. Smith and J.S. Abel,
`"The spherical interpolation
`method of source localization," Journal of Oceanic Engi(cid:173)
`neering, vol. OE-12, no. 1, pp. 246-252, Jan 1987.
`[7] Y.T. Chan and K.C. Ho, "A simple and efficient estimator
`for hyperbolic location," IEEE 'Jlrans. on Signal Process.,
`vol. 48, no. 2, pp. 1905-1915, Aug 1994.
`[8] H. Krim and M. Viberg, "Two decades of array signal pro(cid:173)
`cessing research - the parametric approach," IEEE Signal
`Processing Magazine, pp. 67-94, July 1996.
`J.C. Liberti and T. S. Rappaport, "A geometrically based
`IEEE
`model for line-of-sight multipath radio channels,"
`Trans. on Vehicular Technology, vol. VT-46, pp. 844-848,
`May 1996.
`[10] T. S. Rappaport, Wireless Communications: Principles
`and Practice, chapter 3 and 4, Prentice-Hall, Englewood
`Cliffs, NJ, 1996.
`[11] G. Xu and H. Lin, "An effective transmission beamform(cid:173)
`ing scheme for frequency-division-duplex digital wireless
`communication systems," Proc. of Inter. Con f. on Acous.,
`Speech, and Signal Process., pp. 1729-1732, 1995.
`[12] T.-J. Shan, M. Wax, and T. Kailath,
`"On spatial
`smoothing for direction-of-arrival estimation of coherent
`signals," IEEE 'Jlrans. Acoust., Speech, Signal Processing,
`vol. ASSP-33, no. 4, pp. 806-811, Aug. 1985.
`[13] R. Muhamed and T.S. Rappaport, "Direction of arrival
`estimation using antenna arrays," Tech. Rep. MPRG-TR-
`96-03, Virginia Tech, Blacksburg, VA, Jan 1996.
`(14] R.O. Schmidt, "Multiple emitter location and signal pa(cid:173)
`rameter estimation," IEEE 'Jlrans. on Antennas and Prop(cid:173)
`agat., vol. AP-34, no. 3, pp. 276-280, March 1986.
`[15] J. Kennedy et al. "Characterization of the cellular radio
`environment," Proc. of 2nd Stanford Workshop on Smart
`Antennas in Wireless Communications, July 1995.
`[16] S. M. Kay, Modern Spectral Estimation: Theory and Ap(cid:173)
`plication, Prentice-Hall, Englewood Cliffs, NJ, 1988.
`[17] M.A. Pallas, N. Martin, and J. Martin, "Time delay es(cid:173)
`timation by autoregressive modelization," Proc. of Inter.
`Conf. on Acous., Speech, and Signal Process.; pp. 455-458,
`1987.
`[18] Z. Kostic, M.I. Sezan, and E.L. Titlebaum, "Estimation of
`the parameters of a multipath channel using set-theoretic
`deconvolution," IEEE 'Jlrans. on Commun., vol. 40, no. 6,
`pp. 1006-1011, June 1992.
`
`Apple Inc. Exhibit 1006 Page 5