(12) United States Patent
`Perez-Breva et al.
`
`USOO63932.94B1
`(10) Patent No.:
`US 6,393,294 B1
`(45) Date of Patent:
`*May 21, 2002
`
`(54) LOCATION DETERMINATION USING RF
`FINGERPRINTING
`(75) Inventors: Luis Perez-Breva, Barcelona (ES);
`Chee-Yee Chong, Los Altos, CA (US);
`Robert M. Dressler, Los Altos Hills,
`CA (US); Padmanabha R. Rao,
`Milpitas, CA (US); Paolo Siccardo, Los
`Altos, CA (US); David S. Spain,
`Portola Valley, CA (US)
`
`(*) Notice:
`
`(73) Assignee: Polaris Wireless, Inc., Santa Clara, CA
`(US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`This patent is Subject to a terminal dis
`claimer.
`(21) Appl. No.: 09/532,418
`(22) Filed:
`Mar 22, 2000
`
`(56)
`
`Related U.S. Application Data
`(63) Continuation-in-part of application No. 09/158,296, filed on
`Sep. 22, 1998.
`(51) Int. Cl. .................................................. H04Q7/20
`(52)
`... 455/456; 455/186.1
`(58) Field of Search ................................. 455/456, 454,
`455/440, 186.1, FOR 100; 342/457
`References Cited
`U.S. PATENT DOCUMENTS
`4,907.290 A 3/1990 Crompton
`5,230,081 A 7/1993 Yamada et al.
`5,293,642 A 3/1994 Lo
`5,293,645 A 3/1994 Sood
`5,327,144 A 7/1994 Stilp et al. .................. 342/387
`5,355,526. A 10/1994 Berninger ................ 455/186.1
`5,390,234 A 2/1995 Bar-Noy et al.
`(List continued on next page.)
`
`EP
`E.
`JP
`JP
`JP
`JP
`
`FOREIGN PATENT DOCUMENTS
`O 930 514 A2
`7/1999
`O
`g
`'so
`O2O44929
`2/1990 ........ 455/FOR 100
`11-178039 A 7/1999
`11-178066
`7/1999
`11-205845 A 7/1999
`(List continued on next page.)
`OTHER PUBLICATIONS
`Gaspard, Ingo et al., “Position assignment in digital cellular
`mobile radio networks (e.g. GSM) derived from measure
`ments at the protocol interface," IEEE (O-7803–3659-3/97)
`(1997), pp. 592–596.
`Hellebrandt, Martin et al., “Estimating position and velocity
`of mobiles in a cellular radio network, IEEE Translations
`on Vehicular Technology, 46(1) Feb. 1997, pp. 65-71.
`Jimenez, J. et al., “Mobile location using coverage informa
`tion: Theoretical analysis and results, European Coopera
`tion in the Field of Scientific and Technical Research (Euro
`Cost) 043 (Apr. 1999), pp. 1-9.
`Koshima, Hiroaki et al., “Personal locator Services emerge,”
`IEEE Spectrum Feb. 2000, pp. 41-48.
`Primary Examiner Marsha D. Banks-Harold
`74) Attorney, Agent, or Firm-Townsend and Townsend
`C Crew p g
`ABSTRACT
`(7)
`Amethod for determining the location of a mobile unit (MU)
`in a wireleSS communication System and presenting it to a
`remote party. The location of a remote MU is determined by
`comparing a Snapshot of a predefined portion of the radio
`frequency (RF) spectrum taken by the MU to a reference
`database containing multiple snapshots taken at various
`locations. The result of the comparison is used to determine
`if the MU is at a specific location. The comparison may be
`made in the MU, or at Some other location situated remotely
`from the MU. In the latter case, Sufficient information
`regarding the captured fingerprint is transmitted from the
`MU to th
`te locati
`The datab
`b
`i d C COC R e database may be pre
`compiled or generated on-line.
`36 Claims, 10 Drawing Sheets
`
`
`
`Mobile Unit
`Location
`Estimate
`
`
`
`Updated
`Probability -> Motion
`Distribution
`
`
`
`
`
`New
`Signature
`Measurement
`
`Predicted
`Probability
`Distribution
`
`
`
`Distribution
`Update
`Procedure
`
`Page 1 of 19
`
`SAMSUNG EX-1010
`
`

`

`US 6,393,294 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`5,423,067 A 6/1995. Manabe
`5,442,684 A 8/1995 Hashimoto et al.
`5,461,365 A 10/1995 Schlager et al. ............ 340/573
`5,493.286 A 2/1996 Grube et al. ..
`... 455/456
`5,508,707 A
`4/1996 LeBlanc et al. ............ 342/457
`5,513.243 A 4/1996 Kage
`5,524,136 A 6/1996 Bar-Noy et al.
`5,539,924. A 7/1996 Grube et al.
`5,548.816. A 8/1996 DeVaney
`5,552,795. A
`9/1996 Tayloe et al. ............... 342/357
`5,570.412 A 10/1996 LeBlanc
`5,592,180 A
`1/1997 Yokev et al. ............... 342/450
`5,596,330 A
`1/1997 Yokev et al. ............... 342/387
`5,600,706 A 2/1997 Dunn et al.
`5,602,903 A 2/1997 LeBlanc et al.
`5,650,770 A
`7/1997 Schlager et al. ............ 340/573
`
`5,657.487 A 8/1997 Doner ........................ 455/456
`5,666,662 A 9/1997 Shibuya ...................... 455/456
`5,675,344. A 10/1997 Tong et al. ................. 342/457
`5,732,354 A 3/1998 MacDonald ...
`... 455/456
`5,736,964 A 4/1998 Ghosh et al. ..
`... 342/457
`5,758,288 A 5/1998 Dunn et al. ....
`... 455/456
`5,787,354 A
`7/1998 Gray et al. .......
`... 455/456
`5,802.473 A 9/1998 Rutledge et al. ............ 455/441
`5,926,765 A 7/1999 Sasaki ..............
`455/456
`5.974,330 A 10/1999 Negishi ...................... 455/456
`6,134,448 A 10/2000 Shoji et al.
`
`
`
`FOREIGN PATENT DOCUMENTS
`
`WO
`WO
`WO
`WO
`
`3/1997
`WO 97/33386 A1
`3/1998
`WO 98/41048 A1
`7/1998
`WO OO/O2408 A1
`WO 99/08909 A1 8/1998
`
`Page 2 of 19
`
`

`

`U.S. Patent
`
`May 21, 2002
`
`Sheet 1 of 10
`
`US 6,393,294 B1
`
`[ '31':[
`
`SZ
`
`
`
`
`
`
`
`
`
`
`
`SSQIQI??Aq}{AA 1?UQ QIQOWN
`
`Page 3 of 19
`
`

`

`U.S. Patent
`U.S. Patent
`
`May 21, 2002
`
`Sheet 2 of 10
`
`US 6,393,294 B1
`US 6,393,294 B1
`
`
`
`AyeINYIOOL
`
`yIOMI9K<_>SSO[OITAABIA
`
`-TUNUWIWIOD
`
`uoyes
`
`yuguodwi0d
`
`quUdiesuly
`
`andes
`
`yuouodui07
`
`NW
`
`
`
`BuUd}Uy
`
`Page 4 of 19
`
`~Sly
`Z '$1H
`
`Page 4 of 19
`
`
`
`
`
`
`

`

`U.S. Patent
`
`May 21, 2002
`
`Sheet 3 of 10
`
`US 6,393,294 B1
`
`908
`
`L09
`
`Klub? JQ?IO 01
`
`1?ULISUBJJ 4-SS900 IJ
`
`
`
`
`
`Page 5 of 19
`
`

`

`U.S. Patent
`
`May 21, 2002
`
`Sheet 4 of 10
`
`US 6,393,294 B1
`
`
`
`@Be1aA0Dpe}oe05
`
`
`
`Aouenbeal|v104sdey\
`
`sjauueUD
`
`psly
`
`dVO4d
`
`SUO!}991I05D
`
`
`
`S9UdJBL9}UIBOUIJOL9}U]
`
`aGeiaaoa
`
`sdeyw
`
`feuy
`
`SUOI]IBHOD dVOd
`
`
`jauueyy-[py404jauueyy-095Jo
`
`UONEIS
`
`oseg
`
`ejeg
`
`UONIPAld
`
`lapow
`
`dd
`
`Page 6 of 19
`
`Page 6 of 19
`
`

`

`U.S. Patent
`
`May 21, 2002
`
`Sheet 5 of 10
`
`US 6,393,294 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`J??nduuOO
`
`SJ??9Uueue)
`
`Page 7 of 19
`
`

`

`U.S. Patent
`
`May 21, 2002
`
`Sheet 6 of 10
`
`US 6,393,294 B1
`
`?unp?OOJA
`
`
`
`
`
`
`
`Page 8 of 19
`
`

`

`U.S. Patent
`
`May 21, 2002
`
`Sheet 7 of 10
`
`US 6,393,294 B1
`
`(a ?e si ?un)qola @)
`
`L ‘???
`
`
`
`(@)(O je s? ?jun)qoud
`
`Page 9 of 19
`
`

`

`U.S. Patent
`
`May 21, 2002
`
`Sheet 8 of 10
`
`US 6,393,294 B1
`
`
`
`se 100S
`
`s|Sau??odÅH
`
`8 (?IA
`
`
`
`sasau?odÅH p??epdn
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 10 of 19
`
`

`

`U.S. Patent
`
`May 21, 2002
`
`Sheet 9 of 10
`
`US 6,393,294 B1
`
`
`
`()
`
`- E
`O E CMO
`. H
`
`rad
`
`()
`b)
`E
`r
`
`s
`
`i
`
`S.
`
`S
`
`5
`
`S.
`
`3.
`
`Page 11 of 19
`
`

`

`US 6,393,294 B1
`US 6,393,294 B1
`
`QO]“Sly
`
`May 21, 2002
`May 21, 2002
`
`Sheet 10 of 10
`Sheet 10 of 10
`
`U.S. Patent
`U.S. Patent
`
`
`
`wuUdiosuty
`
`gseqejeq
`
`[09]
`10S
`
`Page 12 of 19
`
`Page 12 of 19
`
`

`

`1
`LOCATION DETERMINATION USING RF
`FINGERPRINTING
`
`US 6,393,294 B1
`
`2
`FIG. 2 is a high level diagram of the Mobile Unit;
`FIG. 3 is a flow diagram of the position determining
`process employed by this invention;
`FIG. 4 is a block diagram showing the technique for
`implementing corrections for co-channel and adjacent
`channel interference;
`FIG. 5 is a block diagram describing the technique for
`calibrating the predicted fingerprint database using field
`measurements,
`FIG. 6 is a block diagram showing the operation of the
`recursive processing Markov algorithm;
`FIG. 7 describes the Markov transition probabilities;
`FIG. 8 is a block diagram showing the operation of the
`multiple hypothesis testing algorithm;
`FIG. 9 is an illustration of the organization of the finger
`print data; and
`FIG. 10 is an illustration of the organization of the
`fingerprint database.
`
`DESCRIPTION OF SPECIFIC EMBODIMENTS
`The present invention provides a new method for deter
`mining the location estimate of a Mobile Unit (MU in a
`wireleSS communication network.
`FIG. 1 is a high level block diagram of a wireless
`communication network. A Mobile Unit 10 has a connection
`with a wireless network 15, which in turn is connected to an
`Other Party 30. The Other Party may or may not be mobile.
`The location of the MU is of interest to the Other Party for
`Several reasons Such as provisioning of prompt and efficient
`personalized Services, dispatching emergency assistance
`personnel, tracking the movements of the MU, etc.
`There are several different prior art methods for deter
`mining the location of MU 10, as is known to one skilled in
`the art. For example, the MU could be equipped with a GPS
`receiver. Alternatively, the wireless network could be
`equipped to determine the location of MU 10. For example,
`the network could monitor the time of arrival of signals from
`the MU at various nodes and from that information deter
`mine its location. Again, Such techniques are well known to
`one skilled in the art.
`All of the prior art techniques have significant disadvan
`tages. For example, it is well known that GPS receivers do
`not work very well in urban canyons and indoor locations
`where Signal Strength is very low. The network based
`schemes such as TDOA and AOA (both well known prior
`art) are disadvantaged in that they need significant infra
`Structure modifications.
`The present invention provides a new method for deter
`mining the location of MU 10 which (a) works in areas
`where GPS coverage is not typically available, and (b) does
`not require any infrastructure modifications. Thus, the
`present invention complements existing location determin
`ing technologies and, when used in conjunction with them,
`augments their performance.
`The invention is based on the principle that any location
`has a unique Radio Frequency (RF) spectral fingerprint.
`Spectral fingerprint in this context is defined as a predeter
`mined combination of observable RF spectral parameters.
`For instance, observed signal Strength of a predetermined Set
`of Signals in the RF spectrum constitutes a fingerprint.
`Today, Worldwide, practically the entire RF spectrum, up to
`2 GHz and above, is being utilized by several different
`applications. The Signal characteristics vary greatly acroSS
`this spectrum. However, for any given location, it is possible
`
`1O
`
`15
`
`25
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`This application is a continuation-in-part of U.S. patent
`application Ser. No. 09/158,296, filed Sep. 22, 1998, the
`entire disclosure of which is incorporated by reference.
`BACKGROUND OF THE INVENTION
`The present invention relate S generally to
`telecommunications, and more specifically to wireleSS com
`munication Systems.
`In connection with mobile communication Systems, it is
`becoming increasingly important to determine the location
`of the communicating Mobile Unit (MU). Various systems
`for locating are already well known. One Solution that is
`readily available in most modern cellular Systems is to use
`the ID of the cell from which the MU is communicating.
`Typically, this information is accurate to a resolution of
`Several miles. A Second Solution is to compute the location
`of the MU based on the cellular network Signaling param
`eters (angle of arrival or time difference of arrival). This
`information is typically accurate to hundreds of meters. Yet
`another solution is to equip the MU with a GPS receiver
`which then attempts to track the location of the MU as
`accurately as possible. Typically, GPS receivers can com
`pute locations to within Several tens of meters of accuracy.
`When combined with differential corrections, the GPS accu
`racy can be improved.
`As far as reliability is concerned, the cell ID information
`is the most reliable, and is guaranteed to be available as long
`as the cellular network is functioning normally. The network
`Signal based location computations are leSS reliable, Since
`they are dependent on Several conditions being true at the
`35
`time of the call. For example, most schemes require the MU
`to have line-of-sight visibility to multiple cellular base
`stations. This is not always possible. GPS based location
`computation is also not always reliable Since the MU may be
`in an environment where there is no penetration of the GPS
`Satellite Signals.
`SUMMARY OF THE INVENTION
`The present invention provides a method for determining
`the location of a mobile unit (MU) in a wireless communi
`cation System and presenting it to a remote party.
`According to one aspect of the invention location of a
`remote MU is determined by comparing a SnapShot of a
`predefined portion of the radio-frequency (RF) spectrum
`taken by the MU to a reference database containing multiple
`Snapshots taken at various locations. The result of the
`comparison is used to determine if the MU is at a specific
`location. The comparison may be made in the MU, or at
`Some other location situated remotely from the MU. In the
`latter case, Sufficient information regarding the captured
`fingerprint is transmitted from the MU to the remote loca
`tion. The database may be pre-compiled or generated
`on-line.
`The invention also provides methods for generating an RF
`fingerprint database.
`A further understanding of the nature and advantages of
`the present invention may be realized by reference to the
`remaining portions of the Specification and the drawings.
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 shows a representative wireleSS communication
`System;
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Page 13 of 19
`
`

`

`US 6,393,294 B1
`
`15
`
`25
`
`3
`to pre-Select a portion of the Spectrum and a combination of
`Signal parameters in the pre-Selected band that will be
`unique to that location.
`In accordance with the invention MU 10 is equipped with
`circuitry and Software that is capable of capturing informa
`tion from predetermined portions of the RF spectrum. In one
`embodiment the predetermined portions of the RF spectrum
`all fall within or in close proximity to the same band as that
`utilized by the wireleSS communication network. In Such an
`instance the Same hardware circuitry can be used for per
`forming both functions. In another embodiment the prede
`termined portions of the RF spectrum are different from the
`wireleSS communication band and in Such an instance addi
`tional circuitry is required. For example, the MU may use
`signal characteristics from the television UHF band, in
`which case it will require a television tuner capable of
`capturing the appropriate television channels. In another
`example the MU is equipped with a tuner designed to
`capture AM or FM radio broadcasts. In this case the MU is
`equipped with a radio capable of tuning to the appropriate
`radio broadcasting bands.
`FIG. 2 shows the MU containing a component 101 for
`tuning to a predetermined portion of the RF spectrum. Also
`included is a communication component 105 for communi
`cating information with the Other Party over an existing
`wireless infrastructure. Component 101 obtains information
`from the RF spectrum via an Antenna 102. In one embodi
`ment of the System, the communication link between the
`MU and Other Party is through the base stations and base
`station controllers of the cellular network. In another
`embodiment of the System, data is communicated in both
`directions between the MU and Other Party by using the
`Short Messaging System (SMS) of the network. Using SMS
`messages for implementation of this invention has the
`35
`advantage of avoiding potential interference with Voice
`channel network operations.
`In many instances, Other Party 30 is interested in only
`determining if MU 10 is at a particular location or not. The
`resolution of knowing the MU's location is not high.(e.g.,
`Several meters), but much coarser, Such as of the order of
`several tens of meters. For example, Other Party 30 may be
`interested in knowing if MU 10 is inside a particular
`building, or a campus or a block. In Such cases it is not
`necessary to provide very high-resolution information to
`Other Party 30.
`There are other instances where Other Party 30 is desirous
`of knowing the accurate location of MU 10, however, is
`incapable of doing SO. This could be because other location
`determining capabilities in the System, Such as GPS, are not
`functional at the instant when the location information is
`desired. This is typical when the MU is in an area where
`GPS Signals are not available, Such as inside a building. The
`location determining method described in this invention is
`capable of operating in areas where GPS and other location
`technologies are not.
`When a location estimate of the MU is desired (either by
`itself or by the Other Party), it activates component 101
`(FIG. 2), which captures predetermined information from a
`predetermined portion of the RF spectrum. Instructions
`regarding what information to capture and the portion of the
`RF spectrum from which to capture may be either pre
`programmed in the MU, or generated in real time. In the
`latter case, it may be generated in the MU, or downloaded
`into the MU from the Other Party over the wireless network.
`The MU may capture multiple pieces of information or from
`multiple portions of the Spectrum.
`
`4
`The Spectral fingerprint may be generated using many
`different parameters, either individually or in combination.
`In one embodiment, Signal Strength is used. In another
`embodiment, phase information is used. In another
`embodiment, the identity of the received signals (e.g.,
`frequency) is used. In yet another embodiment, the identity
`of the signal Source (e.g., channel number or station code) is
`used. In yet another embodiment, the geographic locations
`of the transmitters from which the Signals originate are used.
`A mobile cellular channel is in general frequency
`Selective, i.e., its properties vary over the bandwidth used.
`The variation depends on the environment, because of
`multipath signals arriving at different delays. For a GSM
`signal with a bandwidth about 250 kHz, the dispersion can
`be felt in urban and hilly environments. It causes inter
`Symbol-interference, which results in digital errors unless
`corrected. The time dispersion is often expressed as the
`delay Spread or the Standard deviation of the impulse
`response. The remedy in a receiver is to have an equalizer,
`typically a transversal filter with Some taps that can be
`adjusted. This filter will remove the intersymbol
`interference. The filter's tap values depend on the environ
`ment and impulse response, and thus in principle add
`additional information to the RF fingerprint. For future
`systems which use W-CDMA (wideband code division
`multiple access), the bandwidth is more than 10 times
`higher, of the order 4-5 MHz. The resolution power is thus
`much higher, and the various filter taps contain much more
`information. In this embodiment of the invention, the Spec
`tral characteristics within the used bandwidth (and not just
`individual center frequencies), as measured by the equalizer
`filter, will be included in the RF fingerprint.
`The MU is equipped with the appropriate circuitry and
`Software to capture the required Signals and their parameters.
`In one embodiment the MU has an antenna that is designed
`to have a bandwidth spanning a large portion of the VHF and
`UHF spectrum, e.g., from 70 MHz to 1 GHz. In another
`embodiment, the MU has an antenna that is designed to
`capture only a narrowband of the spectrum. Such an antenna
`may be cheaper to implement and unobtrusive. In one
`embodiment the MU is equipped with appropriate circuitry
`to determine the Strength of the received signal. In one
`instance the location of the transmitter is broadcast in the
`Signal and is extracted in the MU.
`In one embodiment, the MU is instructed by the Other
`Party to Scan Selected portions of the Spectrum and capture
`Selected parameters from the received signals. The Other
`Party determines which portions of the Spectrum to Scan and
`what parameters to capture based on other information it has
`received or generated regarding the MU. For example, in
`one instance the Other Party knows the approximate location
`of the MU by receiving identity of the (wireless communi
`cation network) cell that the MU is in at that time. By
`looking up a database the Other Party can determine the
`geographic location of the cell. The Other Party then deter
`mines which Signals in the vicinity of Said cell are most
`Suitable for generating a fingerprint. For example, certain
`television Signals may have better coverage of the cell than
`other signals. The Other Party then transmits this informa
`tion (e.g., television channel numbers) to the MU via the
`wireleSS link requesting it to Scan only those Selected
`Signals.
`In another embodiment, the MU determines which por
`tion of the Spectrum to Scan, and what parameters to use for
`generating the fingerprint.
`After the MU captures the appropriate Signals and extracts
`the parameters, it has the basic information for generating
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Page 14 of 19
`
`

`

`US 6,393,294 B1
`
`15
`
`25
`
`35
`
`40
`
`S
`the fingerprint. Some preprocessing may be required to
`refine the raw data. For example, Signal Strengths may have
`to be lower and upper limited to eliminate very weak and
`very Strong Signals.
`Once the fingerprint is generated, its association with a
`certain location has to be determined. According to this
`invention this is done by utilizing a fingerprint database that
`contains a number of fingerprints along with their corre
`sponding location identities. In one embodiment the data
`base is stored in the MU. The generated fingerprint is
`compared with the fingerprints in the database and the
`fingerprint in the database that is closest to the generated
`fingerprint is Selected as the match. The corresponding
`location in the database is then chosen as the location of the
`MU. In one embodiment, the Search algorithm takes more
`than one fingerprint from the database that are closest to the
`generated fingerprint and interpolates the most plausible
`location for the MU from the locations of the chosen
`fingerprints.
`In another embodiment, the fingerprint database is Stored
`at the Other Party and the generated fingerprint (in the MU)
`is transmitted to the Other Party over the wireless link. The
`Search for the closest fingerprint is then done in the Other
`Party from which it determines the location of the MU.
`FIG.3 depicts the flow of events in this case. A request for
`position of the MU is generated, as shown in box 301. The
`request may be generated by the user carrying the MU, or
`remotely by the Other Party. On receipt of the request the
`MU captures the fingerprint of its current location (box303).
`The captured fingerprint is processed appropriately. ProceSS
`ing may include filtering the fingerprint data and reformat
`ting it to reduce its Storage Space. Subsequently the finger
`print is transmitted over the wireless link to the Other Party
`as shown in box 305. The Other Party has a database into
`which it executes a Search for the closest matching
`fingerprint, as shown in box 307. Box309 shows the process
`culminating in the retrieval of the best matching fingerprint
`along with its corresponding location. In one embodiment
`the Search also returns a confidence measure that depicts the
`closeness of the match.
`According to one implementation, the fingerprint data
`base is designed to compensate for any co-channel and
`adjacent-channel interference measured by the mobile unit
`(MU). This channel interference can result from either
`control channels or traffic channels. To improve the
`accuracy, as well as viability, of any algorithm for MU
`location based on measurements of base Station Signal
`Strengths, corrections for channel interference will be
`required. These interference corrections are calculated and
`updated off-line using RF prediction models (the same
`models employed to generate the original fingerprint
`database) and the wireless carrier's frequency/channel allo
`cation plan (FCAP). In one embodiment of the invention, the
`interference corrections are implemented in the fingerprint
`database, which is stored in the Other Party (i.e., Location
`Server).
`FIG. 4 describes the data flow and processing require
`ments for this technique. The data required from the wireleSS
`carrier's FCAP is as follows: cell global identifiers, fre
`quency identifiers for the assigned base Station control
`channels, and frequency identifiers for the assigned traffic
`channels. Co-channel interference Sources are identified
`using the FCAP to identify base Stations that are assigned the
`Same frequency channel; the corrected Signal Strengths in
`each channel are then calculated. Adjacent-channel interfer
`ence sources are identified using the FCAP to identify base
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`Station pairs that are assigned adjacent frequency channels,
`the corrected Signal Strengths are then calculated by also
`using the MU's filter discrimination ratio. The resulting
`interference-corrected fingerprints are Stored in the finger
`print database.
`According to one implementation, the fingerprint data
`base is generated by computer calculations with RF predic
`tion models using certain parameters which depend on the
`type of buildings, terrain features, time of the day, environ
`mental and Seasonal conditions, etc. The calculations are
`based upon theoretical models which have general
`applicability, but can not consider all the details in the real
`World. The accuracy of the fingerprint database can be
`enhanced by comparing the model predictions with field
`measurements as shown in FIG. 5. The adaptation algorithm
`analyzes the nature of the difference between the predicted
`and measured fingerprints and determines the best way of
`changing the model parameters to reduce the difference.
`Since the database consists of multiple frequencies, the
`difference is a multi-dimensional vector. The minimization
`of the difference can use a combination of advanced com
`putational techniques based upon optimization, Statistics,
`computational intelligence, learning, etc.
`The adaptation algorithm also determines what measure
`ments to collect to best calibrate the RF prediction model.
`Instead of collecting ail measurements, only measurements
`that can provide the maximal information to Support reduc
`tion of the prediction errors are collected. The Specific
`choice of measurements to collect is based upon an analysis
`of the nature of the error and the desired accuracy of the
`prediction model. The algorithm determines not just the
`locations for measurement collection, but also the time of
`collection, and the number of measurement Samples needed
`to achieve a certain degree of accuracy based upon Statistical
`considerations.
`To improve the accuracy of the fingerprint database,
`learning/training techniques and methodologies can be
`adopted for this problem. For this embodiment of the
`invention, either Support Vector Machines for Regression or
`Regularized Regression can be used to learn each mapping
`of position versus fingerprint (measured or predicted signal
`strengths). Position will be used as the input value, while
`Signal Strength will be used as the target value. The complete
`grid of locations for the cellular Service area will be used as
`training data. The final result is a learned relationship
`between position and Signal Strength for each mapping So
`that, given an arbitrary position, the corresponding Signal
`Strength is obtained for each particular frequency channel.
`The inputs of the training Step are a Set of positions
`matched with the corresponding Signal Strengths, and the
`fingerprint measurements whose information should be con
`sidered in the learning process are added to the training Set.
`The machine is then re-trained and a new grid is generated
`for the database, to replace the old one. The following list
`Summarizes the major advantages of learning/training tech
`niques: (1) they offer a way to interpolate between grid
`points and reconstruct the grid, together with metrics to
`relate measurements and expected fingerprints; (2) a local
`improvement of the neighboring area results from adding
`one measurement to the training Set, and not only the
`particular location is affected, therefore, there is no need to
`obtain measurements for the complete grid; (3) measure
`ments taken at different times can help to produce Specific
`databases for different times of the day, different weather
`conditions, or different Seasons; and (4) the System can learn
`which are the ambiguous areas with an intelligent agent, and
`collect measurements for them, So the database can be
`continually improved.
`
`Page 15 of 19
`
`

`

`US 6,393,294 B1
`
`15
`
`25
`
`35
`
`40
`
`7
`According to one implementation, the fingerprint data
`base is designed to take into account any dynamic, but
`predetermined, variations in the RF signal characteristics.
`For example, it is not uncommon that Some AM radio
`broadcast Stations lower their transmitter power at night to
`minimize interference with other Stations. In Some countries
`this is mandated by law. If Signal Strength is one of the
`parameters used for generating the fingerprint, then it is
`essential that the, dynamic change in transmitted power be
`taken into consideration before any decision is made.
`According to this aspect of the invention, the fingerprint
`database and the decision algorithms are designed to accom
`modate Such dynamic changes. Since the change pattern in
`Signal characteristics is predetermined, the database is con
`Structed by capturing the fingerprints at different times So as
`to cover all the different patterns in the transmitted Signals.
`The time at which a fingerprint was captured is also Stored
`along with its location identity.
`There are many choices for the Search algorithm that is
`required to determine the closest matching fingerprint, as
`can be appreciated by one skilled in the art of Statistical
`pattern matching. Specifically, the choice of the algorithm is
`a function of what parameters are used to generate the
`fingerprints. In one instance the Search algorithm chooses
`the fingerprint from the database that has the Smallest
`mathematical distance between itself and the captured fin
`gerprint. The mathematical distance is defined as a norm
`between the two data sets. For example, it could be the
`average Squared difference between the two fingerprints.
`There are many different ways to define “closeness”
`between two fingerprints, again, this is dependent on the
`Signal parameters used to generate the fingerprints. In one
`embodiment the Search algorithm also has built in heuristics
`that make the best possible decision in case none of the
`fingerprints in the database matches well with the generated
`fingerprint.
`Mobile unit (MU) location determination that separately
`processes single time samples of the first fingerprints (i.e.,
`measured fingerprints) will herein be referred to as “static
`location', which has been shown to be an inherently inac
`curate Solution. Using a processing approach based on the
`time Series nature of the measured fingerprints, herein
`referred to as "dynamic location', can yield significant
`improvements in location accuracy with respect to Static
`location techniques. In this embodiment of the invention, a
`dynamic location technique, which is based on Markov
`theory and exploits the time history of the measured
`fingerprints, is described in FIGS. 6 and 7. The procedure
`uses a predicted fingerprint model and a time Series of
`fingerprint measurements from the MU to calculate the
`probability distribution of the MU's location. The probabil
`ity distribution is then used to compute an estimate of the
`current location of the MU using one of Several Statistical
`methods.
`AS shown in FIG. 6, the processing algorithm is recursive
`and uses a predefined array of possible locations. When the
`algorithm has processed the time Series of fingerprint mea
`Surements currently available, it will have calculated the
`probability that the MU is at each point in the array of
`possible locations (the updated probability distribution).
`This probability distribution is the basic state of the algo
`rithm that incorporates all of the information that has been
`collected on the MU up to the current time. When a new
`fingerprint measurement becomes available, the algorithm
`uses its knowledge of the possible motions of the MU during
`the time period between the last measurement and the new
`measurement to predict a new location probability distribu
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`tion (the predicted distribution). This prediction algorithm is
`based on a Markov process model, which uses the probabil
`ity that the unit is at each location and the probability that it
`will transition from one location to another to calculate t