(12) United States Patent
`Perez-Breva et al.
`
`USOO6782265B2
`(10) Patent No.:
`US 6,782,265 B2
`(45) Date of Patent:
`Aug. 24, 2004
`
`(54) LOCATION DETERMINATION USING RF
`FINGERPRINTING
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`(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)
`(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.
`
`(*) Notice:
`
`(21) Appl. No.: 10/128,128
`(22) Filed:
`Apr. 22, 2002
`(65)
`Prior Publication Data
`US 2003/0008668 A1 Jan. 9, 2003
`Related U.S. Application Data
`(63) Continuation of application No. 09/532,418, filed on Mar.
`22, 2000, now Pat. No. 6,393.294, which is a continuation
`in-part of application No. 09/158,296, filed on Sep. 22,
`1998, now Pat. No. 6,269,246.
`(51) Int. Cl." .................................................. H04Q 7/20
`(52) U.S. Cl. .................................. 455/4.56.1; 455/456.5
`(58) Field of Search ................................. 455/456, 457,
`455/4.56.1-456.6; 342/357.01, 457
`
`5,717.406 A 2/1998 Sanderford et al.
`6,026,304 A 2/2000 Hilsenrath et al.
`6,263,208 B1 * 7/2001 Chang et al. ............... 455/456
`6,393.294 B1 * 5/2002 Perez-Breva et al. ....... 455/456
`6,496,701 B1 * 12/2002 Chen et al. ................. 455/456
`FOREIGN PATENT DOCUMENTS
`O982964 A3
`1/2000
`EP
`O982964 A2
`1/2000
`EP
`2.329.801 A 3/1999
`GB
`* cited by examiner
`Primary Examiner-Charles Appiah
`ASSistant Examiner-James K Moore
`(74) Attorney, Agent, or Firm-DeMont & Breyer, LLC
`(57)
`ABSTRACT
`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 the remote location. The database may be pre
`compiled or generated on-line.
`
`10 Claims, 10 Drawing Sheets
`
`Mobile Unit
`Location
`Estimate
`
`
`
`New
`Signature
`Measurement
`
`Markov
`Updated
`Probability --> Motion
`Distribution
`Model
`
`
`
`
`
`Predicted
`Probability
`Distribution
`
`
`
`Distribution
`Update
`Procedure
`
`
`
`Page 1 of 17
`
`SAMSUNG EX-1009
`
`

`

`U.S. Patent
`U.S. Patent
`
`Aug. 24, 2004
`Aug. 24, 2004
`
`Sheet 1 of 10
`Sheet 1 of 10
`
`US 6,782,265 B2
`US 6,782,265 B2
`
`
`
`SSO[DILM,
`
`yIOMION
`
`
`
`YIMHUE)STIqoW]
`
`
`
`ainjdeyyuLidiosuty
`
`Ayyiqedey
`
`|‘S14
`
`Page 2 of 17
`
`Page 2 of 17
`
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Aug.24, 2004
`
`Sheet 2 of 10
`
`US 6,782,265 B2
`US 6,782,265 B2
`
`
`
`AylegIYOOO],
`
`SSO[OIIMABIA
`
`-TUNUNUIOZ)
`
`oman
`yuouodui07)
`
`uoyes
`
`CTSty
`
`Z * 31. I
`
`
`
`juLIdasuLy
`
`oinjdes
`
`yusuoduio,7)
`
`NIN
`
`
`
`euuajUy
`
`Page 3 of 17
`
`Page 3 of 17
`
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Aug. 24, 2004
`Aug.24, 2004
`
`Sheet 3 of 10
`Sheet 3 of 10
`
`US 6,782,265 B2
`US 6,782,265 B2
`
`L09
`LOE
`
`60€
`
`yoreas
`
`aseqeyeqd
`
`§ 31-I
`
`10€ €“SI
`uones0']2juUdiesuly
`SUIEY]SIGYOId
`
`JIUISUBIT+SSI90Ig
`
`uoltsogjsonbay
`
`AyreJ9YIQ0}
`
`c0e
`
`SOt
`
`omnjdegNW
`
`yutidia3Uut.J
`
`
`
`Page 4 of 17
`
`Page 4 of 17
`
`
`

`

`U.S. Patent
`
`Aug. 24, 2004
`
`Sheet 4 of 10
`
`US 6,782,265 B2
`
`
`
`
`
`36eJaaoO pa?o?JJOO
`
`
`
`ÁOuenbeu-; IIV Jo- sdeW
`
`
`
`
`
`Page 5 of 17
`
`

`

`U.S. Patent
`
`Aug. 24, 2004
`
`Sheet 5 of 10
`
`US 6,782,265 B2
`
`
`
`
`
`J??nduOO
`
`SJ???Uueue)
`
`Page 6 of 17
`
`

`

`U.S. Patent
`
`Aug. 24, 2004
`
`Sheet 6 of 10
`
`US 6,782,265 B2
`
`?unp000Jeff
`
`
`
`
`
`
`
`
`
`Page 7 of 17
`
`

`

`U.S. Patent
`
`Aug. 24, 2004
`
`Sheet 7 of 10
`
`US 6,782,265 B2
`
`
`
`(a les llun)qola @)
`
`
`
`(8 qe sÁe?s ??un)qOJE
`
`/ 31 H
`
`
`
`@)(\/ qe s? ?un)qOJ)
`
`(@) (a le si ?un)qola
`
`Page 8 of 17
`
`

`

`U.S. Patent
`
`Aug.24, 2004
`
`Sheet 8 of 10
`
`US 6,782,265 B2
`
`
`
`sasauyjodAHpayepdn
`
`sisayjodA}
`
`juewaBbeueyy
`
`sisayjodApy
`
`uonjenjeay
`
`siseujodAy
`
`uoHeJauasy
`
`
`
`sisayjodAYuo}e007Jyun
`
`
`
`$8109SsasayjodAy
`
`sjuswainseayy
`
`Page 9 of 17
`
`8“SI
`
`PeypIpald
`
`ainyeuBis
`
`eseqejeg
`
`Page 9 of 17
`
`
`
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Aug. 24, 2004
`Aug.24, 2004
`
`Sheet 9 of 10
`Sheet 9 of 10
`
`US 6,782,265 B2
`US 6,782,265 B2
`
`
`
`Fn Pa|
`
`F3
`
`fa
`
`z
`
`Frequency:
`
`F2pufeof.[omPete
`
`|—pepefe
`pre]es suf
`E.
`
`TransmitterLocation:
`
`TuningParameters:
`
`
`
`
`
`
`
`StationID:
`
`
`
`
`
`SignalStrength1:
`
`
`
`
`
`SignalStrength2:
`
`
`
`SignalStrengthm:
`
`S
`403
`
`S
`405
`
`s
`407
`
`3.
`409
`
`All
`
`413
`
`415
`
`417
`
`TimeofCapture:
`
`
`
`s
`401
`
`
`
`oO=
`BoO
`
`EY
`
`)
`~~
`=tol
`ciD)
`oN
`
`Ap
`
`y
`
`
`
`
`
`
`
`C
`d
`r
`
`400
`
`Page 10 of 17
`
`Page 10 of 17
`
`

`

`U.S. Patent
`U.S. Patent
`
`Aug. 24, 2004
`Aug. 24, 2004
`
`Sheet 10 of 10
`Sheet 10 of 10
`
`US 6,782,265 B2
`US 6,782,265 B2
`
`
`
`Juudissury
`
`aseqeieq
`
`OT‘sly
`OI ‘???
`
`[09]
`10S
`
`Page 11 of 17
`
`Page 11 of 17
`
`

`

`1
`LOCATION DETERMINATION USING RF
`FINGERPRINTING
`
`US 6,782,265 B2
`
`2
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 shows a representative wireleSS communication
`System;
`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
`
`25
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`This application is a continuation of U.S. patent applica
`tion Ser. No. 09/532,418, filed Mar. 22, 2000, now U.S. Pat.
`No. 6,393,294, which was a continuation-in-part of U.S.
`patent application Ser. No. 09/158,296, filed Sep. 22, 1998,
`now U.S. Pat. No. 6,269,246, both of which are incorporated
`by reference.
`BACKGROUND OF THE INVENTION
`The present invention relate S generally to
`15
`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
`time of the call. For example, most schemes require the MU
`40
`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.
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Page 12 of 17
`
`

`

`US 6,782,265 B2
`
`15
`
`25
`
`3
`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
`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
`35
`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
`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
`
`4
`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.
`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 inter-symbol
`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.
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Page 13 of 17
`
`

`

`US 6,782,265 B2
`
`15
`
`40
`
`45
`
`S
`After the MU captures the appropriate Signals and extracts
`the parameters, it has the basic information for generating
`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
`25
`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 (box 303).
`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
`50
`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
`
`35
`
`55
`
`60
`
`65
`
`6
`each channel are then calculated. Adjacent-channel interfer
`ence sources are identified using the FCAP to identify base
`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 all 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
`
`Page 14 of 17
`
`

`

`15
`
`7
`which are the ambiguous areas with an intelligent agent, and
`collect measurements for them, So the database can be
`continually improved.
`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
`60
`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
`
`45
`
`50
`
`55
`
`65
`
`US 6,782,265 B2
`
`25
`
`35
`
`40
`
`8
`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
`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 the
`probability that it will be at each location at the next
`measurement time (see FIG. 7). Next, the algorithm uses the
`predicted Signature model and the new signature measure
`ment to calculate a location probability distribution based on
`the new measurement alone. This probability distribution is
`then combined with the predicted distribution to produce a
`new updated distribution that now incorporates the infor
`mation provided by the new measurement.
`Before any measurements are available, the algorithm
`starts with an initial probability distribution that assumes
`that the MU is equally likely to be at any location in the cell
`for the base station handling the call. The location probabil
`ity distribution (either updated or predicted) may be used to
`compute an estimate of the MU's location whenever such an
`estimate is needed. The basic algorithm calculates both the
`expected location and the most probable location, but other
`location Statistics (as deemed appropriate) could also be
`calculated from the location probability distribution. The
`location estimate may be calculated for either the time of the
`last fingerprint measurement (which yields a filtered
`estimate) or for Some time before the last fingerprint mea
`surement (which yields a smoothed estimate). The smoothed
`estimate is more accurate tha