Ulllted States Patent [19]
`Hilsenrath et al.
`
`[54] RADIO TRANSMITTER LOCATION
`FINDING FOR WIRELESS
`COMMUNICATION NETWORK SERVICES
`AND MANAGEMENT
`
`[75] Inventors: OlIver HIlsenrath, Alamo; MatI Wax,
`San Ramon, both of Calif.
`
`_
`
`_
`
`_
`
`US006026304A
`[11] Patent Number:
`[45] Date of Patent:
`
`6,026,304
`Feb. 15, 2000
`
`5,768,686
`
`3/1999 Leblanc et al. .
`
`FOREIGN PATENT DOCUMENTS
`0689369A1 6/1995 European Pat. on. .
`
`WO 97/15961 10/1996 WIPO .
`
`OTHER PUBLICATIONS
`
`[73] Assignee: U.S. Wireless Corporation, San
`Ramon, Calif.
`
`[21] Appl. No.: 08/780,565
`_
`_
`[22] Flled-
`
`Jan- 8’ 1997
`
`Derek Gerlach et al., “Spectrum Reuse Using Transmitting
`Antenna Arrays With Feedback”, IEEE, vol. 4, pp. 97—100,
`(1994).
`Derek Gerlach et al., “Adaptive Transmitting Antenna
`Arrays With Feedback,” IEEE Signal Processing Letters,
`V01. 1, NO. 10, pp. 150—152, (1994).
`
`[51] Int. Cl.7 ..................................................... .. H04Q 7/20
`[52] US. Cl. ......................... .. 455/456; 455/457; 455/560
`
`_
`_
`(Llst Connnued 0“ next Page“)
`
`[58] Field of Search ................................... .. 455/456, 457,
`455/560, 63; 370/329, 334, 335; 342/457,
`372 387
`’
`
`[56]
`
`References Cited
`
`472577047
`4313 117
`4’728’959
`7
`7
`4,750,147
`4,799,062
`5,208,756
`5,317,323
`5,327,144
`
`U.S. PATENT DOCUMENTS
`3/1981 Lipsky .
`1/1982 LiPSkY'
`3/1988 Maloney et at _
`6/1988 Roy, III et al. ....................... .. 364/807
`1/1989 Sanderford, Jr. et al. ............ .. 342/450
`5/1993 Song.
`5/1994 Kennedy et a1. ..................... .. 342/457
`7/1994 Stilp et al. ............................ .. 342/387
`211156116”:
`~~
`8/1995 J I; 0 as et a1‘ "
`"" " 342/43
`5’444’451
`4/1996 Librlljflrcl :t :1’ """""""""""" "
`5’5O8’7O7
`-
`'
`'
`’
`’
`4/1996 Herrick ................................. .. 342/387
`5,512,90s
`5/1996 Roy’ III et a1_
`__ 370/95_1
`575157378
`8/1996 Roy, III et a1,
`342/174
`5,546,090
`8/1996 Bustamante
`.... .. 370/18
`5,548,583
`455/456
`5,570,412 10/1996 Leblanc ------- -
`Barratt CI 8.1. ......................... ..
`IS—te_t1’1ant°e1ta1~~
`1p 6 a‘ '
`iirrllzlglrll et al. ......................... .. 455/63
`
`’
`
`’
`
`_
`_
`PmW’y Exam‘4e’—DWaYne D- Bost
`Assistant Examzner—L1nWood C. Scott, Jr.
`Attorney, Agent, or Firm—Lumen Intellectual Property
`Services
`[57]
`
`ABSTRACT
`
`A method and apparatus for location tfindinglin' a Wrdreless
`communication system uses
`tIpat signa s In or er to
`accurately determine a transmitter’s location. Direct path
`and multi ath si nals from a mobile transmitter 74 arrive
`p
`g
`'
`'
`at an antenna array [80, 82, 84] Of a base statlon recelver
`[76]. The base station determines signal signature from 21
`subspace of an array covariance matrix. The signature is
`Compared to a database of Calibrated Signal Signatures and
`corresponding locations, and a location Whose calibrated
`signature best matches the measured signature is selected as
`the most likely transmitter location. The database of cali
`brated si nal si natures and corres ondin locations is en
`g
`g_
`_
`P_
`g
`g
`erated by a calibration procedure In WhlCh a phone [74]
`transmits location data derived from a GPS receiver [88] and
`GPS satellites [90, 92, 94] to the base station [76] Which
`records the location information together With the signal
`Signature of the transmitter
`The location information
`can be used to increase the performance of a cellular
`telephone netWork and provide useful services to cellular
`telephone Customers‘
`
`5,724,660
`5,748,683
`
`3/1998 Kauser et a1. ........................ .. 455/456
`5/1998 Smith et al. .
`
`44 Claims, 14 Drawing Sheets
`
`Apple, Inc. Exhibit 1037 Page 1
`
`

`
`6,026,304
`Page 2
`
`OTHER PUBLICATIONS
`
`Derek Gerlach et a1., “Adaptive Transmitting Antenna Meth
`ods for Multipath Environments”, IEEE, pp. 425—429,
`(1994).
`Derek Gerlach et a1, “Base Station Transrnitter Antenna
`
`Arrays With Mobile to Base Feedback”, IEEE, pp.
`1432—1436, (1993).
`A. Swindlehurst, “Subspace Fitting With Diversely Polar
`iZed Antenna Arrays”, IEEE, vol. 41, No. 12, pp.
`1687—1694, (1993).
`
`Apple, Inc. Exhibit 1037 Page 2
`
`

`
`U.S. Patent
`
`Feb. 15,2000
`
`Sheet 1 0f 14
`
`6,026,304
`
`I
`
`I (I . III! I
`l\
`
`32
`
`Apple, Inc. Exhibit 1037 Page 3
`
`

`
`U.S. Patent
`
`Feb. 15,2000
`
`Sheet 2 0f 14
`
`6,026,304
`
`56
`k V
`BASE
`
`/Q/ \ Y
`BASE
`/
`60
`
`54
`
`K
`62
`
`BASE
`f
`58
`
`FIG. 2
`(PRIOR ART)
`
`Apple, Inc. Exhibit 1037 Page 4
`
`

`
`U.S. Patent
`
`Feb. 15,2000
`
`Sheet 3 0f 14
`
`6,026,304
`
`
`
`"I \
`
`
`
`‘\ 68
`
`72
`\
`
`Y Y
`BASE
`64 J
`
`FIG. 3
`(PRIOR ART)
`
`Y Y Y
`BASE
`
`Apple, Inc. Exhibit 1037 Page 5
`
`

`
`U.S. Patent
`
`Feb. 15,2000
`
`Sheet 4 0f 14
`
`6,026,304
`
`90%
`
`92%
`
`94%
`
`FIG. 4
`
`0;?’ \\
`
`‘\
`
`78
`j
`
`88\ Y
`GPS RX T 74
`#
`MICRO
`PROCESSOR
`86 J
`
`SOKT n2 n4
`BASE
`76)
`
`Apple, Inc. Exhibit 1037 Page 6
`
`

`
`U.S. Patent
`
`Feb. 15,2000
`
`Sheet 5 0f 14
`
`6,026,304
`
`|<-————lms—————>|
`
`FIG. 6
`
`Apple, Inc. Exhibit 1037 Page 7
`
`

`
`U.S. Patent
`
`Feb. 15,2000
`
`Sheet 6 0f 14
`
`6,026,304
`
`A
`
`FIG. 7
`
`Apple, Inc. Exhibit 1037 Page 8
`
`

`
`U.S. Patent
`
`Feb. 15,2000
`
`Sheet 7 0f 14
`
`6,026,304
`
`100
`
`FIG. 8
`
`102
`
`BASE
`
`98
`
`Apple, Inc. Exhibit 1037 Page 9
`
`

`
`U.S. Patent
`
`Feb. 15,2000
`
`Sheet 8 0f 14
`
`6,026,304
`
`108
`
`110
`
`114
`
`118
`
`116
`
`FIG. 9
`
`TIME
`
`Apple, Inc. Exhibit 1037 Page 10
`
`

`
`U.S Patent
`
`Feb. 15,2000
`
`Sheet90f 14
`
`6,026,304
`
`130
`
`r _______________ "1 _________________ I COMPOSITE BASE STATION
`
`
`
`;
`
`‘
`
`
`v 7 7 L, BASE I
`
`
`LOCATION i FINDING
`
`128/
`5
`E APPARATUS
`L28. _____________________________ _.=
`
`FIG. 10A
`
`130
`:
`
`r _______________ A _________________ : COMPOSITE BASE STATION
`
`i
`i Y Y Y
`Y Y Y I
`I LOCATION
`BASE
`I
`I FINDING
`128)
`5
`APPARATUS
`:___1_2_@_¥_ ____________________________ -I
`
`I
`
`I
`
`FIG. 10B
`
`130
`
`r _______________ “1 _________________ : COMPOSITE BASE STATION
`
`i V V Y
`I LOCATION
`i FINDING
`APPARATUS
`
`:
`i
`Y Y Y I
`BASE
`i
`128 j
`
`FIG. 10C
`
`Apple, Inc. Exhibit 1037 Page 11
`
`

`
`U.S. Patent
`
`Feb. 15,2000
`
`Sheet 10 0f 14
`
`6,026,304
`
`128
`
`%w v {mmllv
`
`E4 6 _
`
`g \v m
`:m I 1 u _ _
`
`mm m
`
`no _
`“c m 1 n
`_|_ H
`
`II 00 n I
`.A 4 _ F
`_| n G
`
`n W R "
`
`_ _
`
`"Aw m .G Irv “m E mi “
`m Y m “wm " _ 2 _ "T E ,b_ n M_ m
`
`mm m 1 n A
`
`_ m m
`
`128
`
`1
`
`BASE STATION
`134
`E, V
`V
`
`:l>
`"o _
`:;>
`“I o n .M W R w u "C n
`mm _ w M n
`_|_ "
`
`1 up _ “Am _
`mm m i m 1m M n % mm _ m
`ND 1 @ n “m 60 n
`"m E <0J_ 5- R “
`"s 2 H
`
`W Y m
`
`I I I I I I I l I I I I I I I I I I | I I l I | l I I I I I I l I l I I I I I I.
`
`_ W R H
`
`_ 4 u
`
`TX
`7
`
`I
`a
`
`FIG. 11B
`
`Apple, Inc. Exhibit 1037 Page 12
`
`

`
`U.S. Patent
`
`Feb. 15,2000
`
`Sheet 11 0f 14
`
`6,026,304
`
`911
`
`411
`
`3RD PARTY
`SERVICE
`CENTERS
`
`_J_________________
`
`WIRELESS ARENA MANAGEMENT (WAM) HUB
`142
`
`METRO HUB m METRO HUB m
`
`METRO HUB E
`
`BASE STATIONS
`138
`
`138
`
`FIG. 12
`
`Apple, Inc. Exhibit 1037 Page 13
`
`

`
`U.S. Patent
`
`Feb. 15,2000
`
`Sheet 12 0f 14
`
`6,026,304
`
`1 O
`
`CHANNEL USAGE EFFICIENCY
`
`0.1 -
`
`Om __
`
`SECTOHED
`SCHEME 160
`
`0001 __
`
`Y
`
`0.0001
`
`0.0
`
`g
`0.2
`
`g
`0.4
`
`g
`0.6
`
`162
`
`OMNI-POOL
`TRUNKING
`SCHEME
`g
`0.8
`
`1.0
`
`FIG. 13
`
`Apple, Inc. Exhibit 1037 Page 14
`
`

`
`U.S. Patent
`
`Feb. 15,2000
`
`Sheet 13 0f 14
`
`6,026,304
`
`FIG. 14
`(PRIOR ART)
`
`Apple, Inc. Exhibit 1037 Page 15
`
`

`
`U.S. Patent
`
`Feb. 15,2000
`
`Sheet 14 0f 14
`
`6,026,304
`
`B
`
`E
`
`FIG. 15
`
`Apple, Inc. Exhibit 1037 Page 16
`
`

`
`1
`RADIO TRANSMITTER LOCATION
`FINDING FOR WIRELESS
`COMMUNICATION NETWORK SERVICES
`AND MANAGEMENT
`
`FIELD OF THE INVENTION
`
`This invention relates generally to methods for passively
`determining the location of a radio transmitter. More
`particularly, it relates to methods for determining the loca
`tion of cellular telephones in severe multipath urban envi
`ronments and applications of such methods to cellular
`telephone netWork services and management.
`
`BACKGROUND OF THE INVENTION
`
`A long standing problem in radio communications is
`accurately determining the location of a mobile radio trans
`mitter. Precise location information in a cellular telephone
`netWork is desirable for various reasons that have been
`recogniZed in the prior art. For example, US. Pat. No.
`5,515,378 to Roy, III et al. discloses the application of
`location information to mitigating the hand-off problem,
`increasing signal sensitivity, reducing crosstalk, and increas
`ing cell capacity. Also disclosed is the use of location
`information to dynamically track the trajectories of mobiles.
`This source tracking makes use of an eXtended Kalman ?lter,
`and can include the tracking of velocities and accelerations
`as Well as positions, and the tracking of multiple mobiles
`Whose trajectories cross. US. Pat. No. 5,512,908 to Herrick
`mentions the application of cellular location information to
`911 dispatching, tracking unauthoriZed cell phone usage,
`and tracking or locating commercial and/or government
`vehicles. US. Pat. No. 5,327,144 to Stilp et al. also mentions
`various applications of mobile location information, such as
`locating lost or stolen vehicles, assisting lost motorists, and
`dispatching emergency vehicles. These applications have
`yet to be realiZed, hoWever, because they require accurate
`location information and no adequate method of providing
`such information has yet been developed.
`Multipath is the greatest obstacle to prior art methods of
`solving the location ?nding problem. As shoWn in FIG. 1,
`multipath is typically caused by the re?ection of signals
`from objects in the environment, such as buildings, hills, and
`other structures. A signal transmitted from a cellular phone
`30, for example, is re?ected from structures 32, 34, and 36,
`resulting in three multipath signals arriving at a base station
`38 in addition to a direct path signal. Due to the multipath
`signals, it appears from the perspective of base station 38
`that three additional cellular phones 40, 42, and 44 are
`transmitting similar signals from different locations. In some
`cases, signals from a phone 50 can arrive at base station 38
`from nearly opposite directions, one from actual phone 50
`and another from a “ghost” phone 52. Moreover, because the
`path lengths of the multipath signals differ from that of the
`direct path signal, the multipath signals have differential
`time delays With respect to the direct path signal. In an urban
`environment Where severe multipath is present, sometimes
`no direct path eXists and the base station receives only
`multipath signals. For eXample, phone 46 has no direct path
`signal to base 38. Consequently, it appears from base 38 that
`a unique signal is originating from a “ghost” phone 48 Which
`has a very different location from actual phone 46. Clearly,
`multipath signi?cantly complicates the communication of
`signals, and, in particular, complicates the problem of accu
`rately determining the true location of a transmitter. Since a
`large proportion of cellular phone usage is in urban envi
`ronments Which have severe multipath, it is especially
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`6,026,304
`
`2
`important to solve this problem. All prior art methods,
`hoWever, have failed to provide consistent and accurate
`location information in multipath environments.
`As illustrated in FIG. 2, a common prior art approach to
`determining the position of a mobile phone 52 involves
`measuring temporal information, eg time of arrival (TOA)
`or time difference of arrival (TDOA), at three or more
`synchroniZed base stations 56, 58, and 60. By communicat
`ing this temporal information betWeen the base stations over
`a communication line 62, the transmitter location can be
`determined. This type of approach is disclosed, for eXample,
`in US. Pat. No. 5,548,583 to Bustamante, US. Pat. No.
`5,512,908 to Herrick, US. Pat. No. 5,327,144 to Stilp et al.,
`US. Pat. No. 5,317,323 to Kennedy et al., and US. Pat. No.
`4,799,062 to Sanderford, Jr. et al. These methods have the
`disadvantage that they require several base stations, and that
`signals from cellular phone 54 be received by all base
`stations 56, 58, and 60 simultaneously. Additionally, eXpen
`sive high accuracy clocks are required at the base stations
`and eXpensive high bandWidth communication lines 62 are
`required betWeen the base stations in order to alloW accurate
`temporal correlation of their received signals from phone 54.
`More signi?cantly, this approach encounters serious dif?
`culties in urban environments since multipath causes tem
`poral delays and creates “ghost” transmitters. Consequently,
`it fails to determine positions accurately and consistently in
`many cases.
`Although the prior art does disclose several techniques for
`location ?nding that attempt to mitigate multipath effects,
`they all fail in the presence of severe multipath. Bustamante
`does not acknoWledge problems due to severe multipath.
`Herrick teaches a method for mitigating inaccuracies due to
`multipath by averaging over several TOA measurements at
`differing frequencies. Stilp teaches a method of compensat
`ing for multipath through the use of algorithms that can
`distinguish direct path from multipath signals and eliminate
`or ignore the latter. Kennedy also teaches the mitigation of
`multipath through algorithms that distinguish multipath sig
`nals from direct signals by determining angles of arrival,
`times of arrival, and signal strength. Sanderford teaches a
`method for multipath mitigation using spread-spectrum
`(frequency hopping) transmissions from the mobiles. These
`techniques are all characteriZed by an attempt to cope With
`multipath by circumvention or discrimination of multipath
`signals from direct path signals. In cases of severe multipath,
`hoWever, there often is no direct path signal at all. In such
`cases, these approaches fail. Moreover, averaging tech
`niques are based on assumptions about the distribution of
`multipath that are not generally valid, especially in severe
`multipath environments. Even in cases Where such assump
`tions do hold, these averaging techniques do not yield
`accurate position information.
`Stilp discloses a method for location ?nding Which
`involves creating a grid of theoretical signal delay values.
`The calculation of the theoretical values incorporates biases
`at the base station sites due to mechanical, electrical, or
`environmental factors. The biases for the base station sites
`are determined by measuring the signals from reference
`transmitters having knoWn locations. Any variance betWeen
`the knoWn position and the calculated position is assumed to
`be caused by site biases. It is further assumed that these same
`biases Will affect other cellular phones at other unknoWn
`locations, ie the site biases are assumed to depend only on
`the site and not on the mobile locations. Dues to these
`assumptions, the method can not account for biases due to
`severe multipath, Which changes dramatically in dependence
`upon the mobile location. Moreover, since this technique is
`
`Apple, Inc. Exhibit 1037 Page 17
`
`

`
`6,026,304
`
`3
`based upon TDOA measurements, it is problematic for the
`additional reasons already discussed.
`As illustrated in FIG. 3, another prior art approach deter
`mining the location of a phone 68 makes use of antenna
`arrays 64 and 66 for direction ?nding. For example, US.
`Pat. No. 5,515,378 to Roy, III et al. discloses a method and
`apparatus for estimating positions and velocities of mobiles
`from antenna array measurements of their signals. As is
`Well-knoWn in the art, a processor forms an average cova
`riance matrix from a collection of array vectors received at
`each antenna array and performs spatial smoothing and/or
`forWard/backWard temporal averaging as appropriate. Sig
`nal and noise subspaces are then calculated using an eigen
`decomposition of the resulting covariance matrix. Signal
`detection is then accomplished by a statistical technique
`such as Weighted subspace ?tting (WSF) detection. A maxi
`mum likelihood estimator is employed to then obtain the
`signal parameter estimates, such as the direction of arrival
`(DOA). When an estimate of location is made based only on
`the directional information from a single base station, such
`an estimate has a very poor accuracy. To obtain more
`accurate location estimation, the DOA parameters must be
`supplemented by TOA measurements and/or parameter mea
`surements sent over a communication line 72 from other
`base stations. Even in this case, hoWever, the estimates are
`still not sufficient to accurately determine a correct location
`since a direct path may not exist at all, as in severe multipath
`environments. For example, since no direct path exists from
`phone 68 to either base station 64 or 66, phone 68 Will
`appear to be located at the location of a false “ghost” phone
`70.
`Other more recent Work in mobile communications has
`attempted to cope With severe multipath, albeit not for
`location determination applications. For example, Gerlach et
`al. in “Adaptive Transmitting Antenna Methods for Multi
`path Environments” discloses a base station beamforming
`method Which uses feedback from a mobile to determine a
`characteristic subspace of the mobile’s instantaneous chan
`nel vector. Although the instantaneous channel vector can
`change rapidly in a strong multipath environment, Gerlach
`et al. point out that it is normally restricted to a characteristic
`subspace that is much more stable in time. By tracking this
`channel subspace rather than the channel vector, much loWer
`feedback rates are required. A collection of instantaneous
`channel vectors are measured, and the sum of their outer
`products is taken to produce a channel matrix. The eigen
`vectors having large eigenvalues de?ne a subspace of this
`matrix Which is a more stable representation of the receiv
`er’s channel. This subspace is then used in beamforming at
`the base station to minimiZe crosstalk and maximiZe the
`desired signal at the mobiles. Although this approach
`reduces the amount of feedback required for beamforming in
`severe multipath environments, it does not have obvious
`application to location ?nding.
`US. Pat. No. 4,799,062 to Sanderford, Jr. et al. proposes
`an approach to location ?nding using a differential multipath
`signal technique. They point out that When the positions of
`tWo mobiles are close to each other, their multipath signals
`should be nearly the same. Consequently, if a reference
`signal from a knoWn transmitter location near the mobile
`Were subtracted from the mobile’s signal, the multipath
`effects should cancel and the differential position betWeen
`the tWo could be determined. The disclosure, hoWever, does
`not explain in detail hoW such a method might be imple
`mented. Moreover, in severe multipath environments the
`approach outlined fails. Since the multipath components of
`the signal can change signi?cantly over distances on the
`
`4
`order of 10 meters or less, the differential position Will be
`accurate only in cases Where the mobile is already Within
`sight of the mobile, therefore defeating the purpose of the
`technique. Even in cases of less severe multipath, the need
`for a reference signal makes the technique unattractive to
`implement.
`
`OBJECTS AND ADVANTAGES OF THE
`INVENTION
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`Accordingly, it is a primary object of the present invention
`to provide a method for accurately determining the position
`of a mobile radio transmitter, even in severe multipath
`environments. It is another object of the invention to provide
`such a method for location ?nding that requires only a single
`base station. Another object of the invention is to provide for
`the realiZation of many cellular netWork services and man
`agement applications that have heretofore been unattainable
`due to the absence of accurate and consistent location
`?nding techniques. Accordingly, it is another object of the
`invention to use location information to provide sophisti
`cated tools and techniques for intelligently managing cellu
`lar netWorks and for providing improved service to cellular
`netWork users.
`It is an object of the invention to provide a system for
`tracking and locating all cellular telephone traf?c from a
`single base station. It is also an object to provide such a
`system that does not require a calibrated antenna array, does
`not require the phones to be responsive or cooperative, and
`does not require line-of-sight communication betWeen the
`array and the phones. These and other advantages Will
`become apparent from the folloWing description and accom
`panying draWings.
`
`SUMMARY OF THE INVENTION
`
`In contrast With all prior art location ?nding methods
`Which attempt to eliminate or avoid multipath signals, the
`present invention advantageously uses multipath signals in
`order to accurately determine a transmitter’s location. More
`speci?cally, signals from a mobile transmitter are sent to an
`antenna array of a base station receiver Which is part of a
`Wireless communication system such as a cellular telephone
`netWork. Based upon the signals received at the antenna
`array, the base station determines a signal signature. In
`general, the signal signature is any location-dependent fea
`ture derived from the set of direct and multipath signals
`received at the antenna array of a single base station from a
`transmitter at a given location. The signature may be derived
`from any combination of amplitude, phase, delay, direction,
`and polariZation information of the signals. Preferably, the
`signature is substantially invariant With respect to all vari
`ables unrelated to transmitter position, such as noise. One
`embodiment of the invention includes determining a sub
`space of an array covariance matrix and using the subspace
`as the signal signature.
`After the signal signature has been determined, it is then
`compared to a database of calibrated signal signatures and
`corresponding locations. In one aspect of the invention, the
`database of calibrated signal signatures and corresponding
`locations is generated by a calibration procedure in Which
`GPS location data of a calibration mobile is associated With
`the signal signature of the mobile. By searching such a
`database, a location Whose calibrated signature best matches
`the measured signature is selected as the most likely loca
`tion. In this manner, the location of the transmitter can be
`accurately determined from a signal received at a single base
`station, even in a severe multipath environment.
`
`Apple, Inc. Exhibit 1037 Page 18
`
`

`
`6,026,304
`
`5
`Surprisingly, in contrast to other techniques of location
`?nding, the present technique is characterized by improved
`accuracy in multipath environments. The invention,
`therefore, provides a unique and surprising solution to the
`location ?nding problem Which has heretofore remained
`unsolved. Moreover, the present invention provides a
`method of location ?nding Which, in contrast to other
`methods, can accurately determine a location from a single
`base station. This feature of the invention distinguishes it
`from prior techniques Which either require multiple base
`stations or provide only very inaccurate or imprecise loca
`tion information.
`
`DESCRIPTION OF THE FIGURES
`
`FIG. 1 shoWs several phones and a base station in a typical
`urban environment Where severe multipath is present.
`FIG. 2 illustrates a prior art method of locating phones
`based on temporal information shared betWeen multiple base
`stations.
`FIG. 3 illustrates a prior art method of locating phones
`based on direction ?nding from multiple base stations.
`FIG. 4 illustrates locating a phone using a GPS receiver
`and transmitting this information to a base station in a
`calibration phase of the present invention.
`FIG. 5 is a graph of a 1 ms sampling interval containing
`100 samples according to the present invention.
`FIG. 6 is a graph of a 5 s interval containing 100 of the
`1 ms sampling intervals of FIG. 5, spaced at 50 ms intervals,
`according to a sampling technique of the invention.
`FIG. 7 is a graph of several array vectors sWeeping out a
`signal subspace, according to the invention.
`FIG. 8 illustrates a moving phone and the changing signal
`path lengths in a multipath environment.
`FIG. 9 is a graph of several tracks representing possible
`locations of a phone according to the present invention.
`FIGS. 10A, 10B, and 10C are block diagrams of three
`Ways of connecting an apparatus of the present invention to
`an existing base station.
`FIGS. 11A and 11B are block diagrams of the major
`components of an apparatus of the present invention in
`connection With those of an existing base station.
`FIG. 12 is a schematic diagram of the system architecture
`of a cellular netWork management system according to the
`present invention.
`FIG. 13 is a graph of channel usage efficiency for tWo
`trunkpool schemes.
`FIG. 14 is a schematic diagram illustrating a cell divided
`into sectors, as is knoWn in the art.
`FIG. 15. is a schematic diagram illustrating a cell divided
`into subcells according to the present invention.
`
`DETAILED DESCRIPTION
`
`Although the folloWing detailed description contains
`many speci?cs for the purposes of illustration, anyone of
`ordinary skill in the art Will appreciate that many variations
`and alterations to the folloWing details are Within the scope
`of the invention. Accordingly, the folloWing preferred
`embodiment of the invention is set forth Without any loss of
`generality to, and Without imposing limitations upon, the
`claimed invention.
`A preferred embodiment of the invention comprises a
`system and method for determining the locations of mobile
`transmitters, such as cellular telephones, in a Wireless com
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`6
`munications system such as a cellular telephone netWork. In
`addition to location determination, the preferred embodi
`ment also comprises various techniques for using and apply
`ing location information Within such a communications
`system to improve system capacity and performance.
`In a communication system according to a preferred
`embodiment of the invention, a cellular telephone 74 trans
`mits a signal in the vicinity of a cellular telephone base
`station 76, as shoWn in FIG. 4. Typically, in addition to a
`direct path signal from phone 74 to base 76, there may be
`additional multipath signals re?ected from various environ
`mental objects, for example, from object 78. Base station 76
`is equipped to receive signals With an antenna array, multiple
`receivers, and signal processors, as described beloW in
`relation to FIG. 11A. In general, the antenna array has a
`number p of antennas. For illustrative purposes, hoWever,
`the array is shoWn in FIG. 4 as having three antennas 80, 82,
`and 84. The p antennas are used to receive complex signal
`envelopes x1(t), x2(t), .
`.
`.
`, xp(t), respectively, Which are
`conventionally grouped together to form a p-dimensional
`array vector x(t)=[x1(t), x2(t), .
`.
`.
`xp(t)]T. In general, the
`dimension of the array vector x(t) is equal to p, the number
`of antennas in the array.
`In order to obtain robustness and to reduce noise, the array
`vector x(t) is preferably produced by sampling the antennas
`many times during a short time interval and averaging the
`samples. In the preferred embodiment the averaging is done
`by selecting the vector x(t) to be the dominant eigenvector
`of the pxp correlation matrix of the samples. As illustrated
`in FIG. 5, a sample may be taken every 10 microseconds
`over an interval of 1 millisecond. The 100 samples are then
`used to produce a single array vector
`As illustrated in
`FIG. 6, a collection of M array vectors x(tl), .
`.
`.
`, x(tM) is
`produced by performing this sampling at regular intervals.
`In a preferred embodiment, array vectors are sampled at
`50 millisecond intervals to produce a collection of 100
`vectors. Since array vectors are sampled only once every 50
`milliseconds, and each sample requires only 1 millisecond,
`there is suf?cient time using this technique to sample up to
`50 separate channels in parallel. Although the present
`description is focused upon the processing of one signal, in
`the preferred embodiment, the techniques described herein
`can be applied in parallel to signals on up to 50 channels. It
`Will be recogniZed by those skilled in the art that although
`this sampling procedure is appropriate for the AMPS cellular
`standard it can be adapted to various other modulation
`schemes as Well. Appropriate techniques for demodulation,
`demultiplexing, signal separation, sampling and averaging
`in various modulation schemes are Well-knoWn in the art.
`For example, the present invention may be adapted for, but
`is not limited to, any of the common Wireless standards, such
`as AMPS, NAMPS, NMT 900, TACS, ETACS, NMT 450,
`C-450, RTMS, JTACS, NTACS, DAMPS (TDMA, IS-54,
`IS-136), GSM, DCS 1800, PCS (PCS 1800 and PCS 1900),
`PHS, CDMA (narroWbands, Widebands, 800 MHZ, 1.8 GHZ
`or 1.9 GHZ), iDen (aka MIRS), EDACS, FHMA, JDC,
`TETRA, APCO-25, and MPT-1327.
`In the preferred embodiment, the collection of M array
`vectors are analyZed to determine a signal subspace.
`Although the array vector changes over the course of time
`due to noise, movement of the mobile, and other effects, to
`a good approximation the vector is con?ned to a subspace
`Which is spanned by a set of q linearly independent array
`response vectors, a1, .
`.
`. , aq, Where q is the dimension of the
`subspace. For example, FIG. 7 illustrates a tWo-dimensional
`signal subspace in a case Where p=3. (The case p=3 is chosen
`for simplicity of illustration only.) The tWo array response
`
`Apple, Inc. Exhibit 1037 Page 19
`
`

`
`6,026,304
`
`7
`vectors a1 and a2 are a spanning set for the 2-dimensional
`signal subspace to Which the array vectors x(t1), .
`.
`. , x(tM)
`are approximately con?ned. The vector a1 may be physically
`interpreted as representing the response of array 76 in the
`direction of the direct path signal from phone 74, as shoWn
`in FIG. 4. Similarly, a2 is the array response in the direction
`of the multipath signal re?ected from object 78.
`Since the location of phone 74 determines not only the
`particular value of a1 associated With direct path, but also the
`value of a2 associated With multipath, the signal subspace
`depends on a combination of these tWo vectors Which are, in
`turn, dependent upon the speci?c location of phone 74.
`Consequently, the signal subspace may be regarded as a
`signal signature associated With each location. Moreover,
`since each multipath signal normally contributes an extra
`dimension to the subspace, the subspace signature Will have
`an increased dependence upon location in the presence of
`severe multipath. Accordingly, as the present inventors have
`recogniZed, the location of an unknoWn transmitter can be
`determined by measuring its signal signature, and compar
`ing it With a database containing calibrated signal signatures
`paired With their associated locations.
`The signal subspace may be determined from the collec
`tion of M array vectors by several techniques that are
`Well-known in the art. According to one method, the outer
`products of the M vectors are added together to form a pxp
`signal covariance matrix, R=1/M [x(t1)x(t1)H+. .
`. +x (tM X
`(tM)H]. The eigenvalues of R Whose magnitudes exceed a
`predetermined threshold determine a set of dominant eigen
`vectors. The signal subspace is the space spanned by these
`dominant eigenvectors. Equivalently, the subspace can be
`de?ned as the subspace spanned by the dominant left
`singular vectors obtained from a singular value decomposi
`tion of a pxM data matrix X generated from the
`p-dimensional array vectors x(t1), .
`.
`.
`, x(tM).
`It should be noted that, if a transmitter is stationary and if
`the differential time delays are much smaller than the
`reciprocal of the signal bandWidth, then the multipath and
`direct path signals Will be coherent, ie they Will differ only
`by a complex scalar factor. In this case, the measured signal
`subspace Will be one-dimensional since the multipath signal
`does not contribute an additional dimension to the signal
`subspace. A moving transmitter, on the other hand, Will
`decorrelate the direct and multipath signals over a distance
`of several Wavelengths. For example, FIG. 8 shoWs a
`moving transmitter 96 and a base station 98 receiving tWo
`multipath signals re?ected from objects 100 and 102. As
`phone 96 moves to subsequent positions 104 and 106,