(12) United States Patent
`Rao et al.
`
`USOO6269246B1
`(10) Patent No.:
`US 6,269,246 B1
`(45) Date of Patent:
`*Jul. 31, 2001
`
`5,548,816
`5,552.795
`
`(54) LOCATION DETERMINATION USING RF
`FINGERPRINTING
`(75) Inventors: Padmanabha R. Rao, Milpitas; Paolo
`L. Siccardo, Los Altos, both of CA
`US
`(US)
`(73) Assignee: PPM, Inc., Los Altos Hills, CA (US)
`(*) Notice:
`This patent issued on a continued pros-
`ecution application filed under 37 CFR
`1.53(d), and is subject to the twenty year
`patent term provisions of 35 U.S.C.
`154(a)(2).
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/158,296
`(22) Filed:
`Sep. 22, 1998
`(51) Int. Cl." ................................................... H04Q 7/20
`(52)
`455/456; 455/186.1
`(58) Field of Search ..................................... 455,410, 440,
`455/456, 454, 186.1, FOR 100; 342/457
`References Cited
`
`(56)
`
`8/1996 DeVaney.
`9/1996 Tayloe et al. ........................ 342/357
`(List continued on next page.)
`FOREIGN PATENT DOCUMENTS
`02044929
`2/1990 (JP) ............................. 455/FOR 100
`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.
`66
`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.
`cited by examiner
`Primary Examiner Marsha D. Banks-Harold
`(74) Attorney, Agent, or Firm Townsend and Townsend
`and Crew LLP
`ABSTRACT
`(57)
`U.S. PATENT DOCUMENTS
`The location of a mobile unit (MU) in a wireless commu
`nication System is determined by comparing a Snapshot of a
`E. 3.19. SNE
`predefined portion of the radio-frequency (RF) spectrum
`5,293.642
`3/1994 ama a C a
`taken by the MU to a reference database containing multiple
`5,293.645
`3/1994 Sood.
`Snapshots taken at various locations. The result of the
`5,327,144
`7/1994 Stilp et al. ........................... 342,387
`comparison is used to determine if the MU is at a specific
`5,355,526 * 10/1994 Berninger .......................... 455/186.1
`location. The comparison may be made in the MU, or at
`5,390,234
`2/1995 Bar-Noy et al..
`Some other location situated remotely from the MU. In the
`5,423,067
`6/1995. Manabe.
`latter case, Sufficient information regarding the captured
`5,442,684
`8/1995 Hashimoto et al..
`S. : 10/1995 Shige al. ..................... E. fingerprint is transmitted from the MU to the remote loca
`
`:: 20 S.E.M. E. in the database may be pre-compiled or generated on the
`
`5,513,243
`5,524,136
`5,539,924
`
`4/1996 Kage.
`6/1996 Bar-Noy et al..
`7/1996 Grube et al. .
`
`y.
`
`19 Claims, 5 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Request Position
`
`MU Capture
`Fingerprint
`
`Process+Transmit
`to Other Party
`
`Search
`Database
`
`Pick Best Matching
`Fingerprint and Location
`
`301
`
`303
`
`305
`
`307
`
`309
`
`Page 1 of 11
`
`SAMSUNG EX-1005
`
`

`

`US 6,269,246 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`5,570,412
`5,592,180
`5,596,330
`5,600,706
`5,602,903
`5,650,770
`5,657,487
`
`10/1996 LeBlanc.
`1/1997 Yokev et al. ........................ 342/450
`1/1997 Yokev et al. ........................ 342/387
`2/1997 Dunn et al. .
`2/1997 LeBlanc et al. .
`7/1997 Schlager et al. ..................... 340/573
`8/1997 Doner ................................... 455/456
`
`
`
`9/1997 Shibuya ............................... 455/456
`5,666,662
`10/1997 Tong et al.
`... 342/457
`5,675,344
`3/1998 MacDonald ..
`... 455/456
`5,732,354
`4/1998 Ghosh et al.
`... 342/457
`5,736,964
`5/1998 Dunn et al. .......................... 455/456
`5,758,288
`7/1998 Gray et al. ........................... 455/456
`5,787,354
`9/1998 Rutledge et al. .................... 455/441
`5,802,473
`7/1999 Sasaki .................................. 455/456
`5,926,765
`5.974,330 * 10/1999 Negishi ................................ 455/456
`
`Page 2 of 11
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jul. 31, 2001
`Jul. 31, 2001
`
`Sheet 1 of 5
`Sheet 1 of 5
`
`US 6,269,246 B1
`US 6,269,246 B1
`
`S3
`30
`
`Other Party
`
`
`
`3 a
`Bx
`CD O
`a oO
`5 is 5
`oe
`= @
`e 2
`sz
`
`FIG.1
`
`Page 3 of 11
`
`Page 3 of 11
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jul. 31, 2001
`Jul. 31, 2001
`
`Sheet 2 of 5
`Sheet 2 of 5
`
`US 6,269,246 B1
`US 6,269,246 B1
`
`YIOMION
`
`
`
`Á?ued 10?IO 01
`
`SSOjOIMBIA<Aued
`19410OL
`ssºle||Me|A ?---)
`
`UOIJEdIUNWUWO)
`juauodwoy
`
`oOld
`Z '0|+
`
`Ol
`
`NW
`
`
`
`
`
`Page 4 of 11
`
`my
`
`juudsabul4
`
`aunides
`
`juau0dwoy
`
`BUUa]UY
`
`Page 4 of 11
`
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jul. 31, 2001
`
`Sheet 3 of 5
`
`US 6,269,246 B1
`US 6,269,246 B1
`
`LO
`
`0
`
`S0€
`
`LOE
`
`609
`60€
`
`€€ €Dl
`uolye007pueyudiebuls
`Buiyoyey)18g49lq
`
`}Wsuel|+SS80014
`
`UOIISO,Jsenbay
`
`AuedJ2UIO0}
`
`ainydeyNW
`
`juudiebul4
`
`youeas
`
`aseqeleq
`
`
`
`Page 5 of 11
`
`Page 5 of 11
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jul. 31, 2001
`Jul. 31, 2001
`
`Sheet 4 of 5
`Sheet 4 of 5
`
`US 6,269,246 B1
`US 6,269,246 Bl
`
`ralrae|oefsa]—sm nisl[son
`
`
`fay|ee
`
`Ln Psi
`
` Fingerprint
`
`ec
`raferai
`Structure
`Fe
`ALce
`
`
`TransmitterLocation:
`
`
`Strengthm:
`TuningParameters:
`
`Signal
`
`SignalStrength1:
`
`SignalStrength2:
`
`TimeofCapture:
`i
`Frequency:
`
` StationID:
`
`
`
`400
`
`©=
`
`Page 6 of 11
`
`FIG.4
`
`
`
`
`3.
`409
`
`s
`411
`
`s
`413
`
`s
`415
`
`417
`
`_—
`
`s 3 3 S.
`407
`405
`403
`
`Page 6 of 11
`
`

`

`U.S. Patent
`
`Jul. 31, 2001
`
`Sheet 5 of 5
`
`US 6,269,246 B1
`
`
`
`CD
`t
`(VS
`O
`Sl
`CVS
`O
`und
`C
`u
`Ol h
`CD
`O)
`.
`
`-
`
`-
`
`s
`
`Page 7 of 11
`
`

`

`1
`LOCATION DETERMINATION USING RF
`FINGERPRINTING
`
`US 6,269,246 B1
`
`2
`FIG. 5 is an illustration of the organization of the finger
`print 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 methods for determining 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 determine 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
`Structural 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 infrastructural 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
`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
`
`BACKGROUND OF THE INVENTION
`The present invention relate S generally to
`telecommunications, and more specifically to wireleSS mes
`Saging 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, time delay of arrival, signal strength,
`etc.). This information is typically accurate to Several tens 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
`compute locations to within Several tens of meters of accu
`racy. When combined with differential corrections, the accu
`racy can be improved to less than 10 meters with a high
`degree of probability.
`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
`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 in a wireleSS communication
`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 the
`fly.
`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;
`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 an illustration of the organization of the finger
`print data; and
`
`5
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Page 8 of 11
`
`

`

`3
`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 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.
`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.
`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
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,269,246 B1
`
`4
`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 of the invention, the MU deter
`mines which portion 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
`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 of the invention, the search algo
`rithm 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 aspect of this invention the fingerprint
`database 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 that dynamic change in transmitted power be
`
`Page 9 of 11
`
`

`

`US 6,269,246 B1
`
`15
`
`35
`
`40
`
`25
`
`S
`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.
`The complexity of the Search can be greatly reduced if an
`approximate estimate of the MU's location is already avail
`able. For example, if the identity of the cell in which the MU
`is located is known, then according to this invention, the
`Search algorithm will limit its Search to only those finger
`prints that correspond to locations contained within said cell.
`Similarly, the Search complexity is reduced by noting the
`time at which the location information is requested. AS
`previously mentioned, not all fingerprints in the database are
`valid for all times in the day. Knowing the time at which the
`request is received, the database engine limits the Search to
`the appropriate fingerprints.
`FIG. 4 illustrates a structure 400 of the fingerprint in one
`embodiment of this invention. AS mentioned previously
`there are Several possible methods for defining the finger
`print. FIG. 4 is but an example. The time at which the
`fingerprint is captured is Stored in the fingerprint Structure,
`as shown by box 401. In one embodiment the UTC format
`is used to Store time. There are Several fields in the Structure,
`Some of which are optionally filled by the MU. Some other
`fields are optionally filled by the Other Party. It is not
`necessary that all fields be filled Since the necessary fields
`can be predetermined based on System parameters.
`The fingerprint comprises characteristics of received Sig
`nals at multiple frequencies. Each column in FIG. 4 is
`information pertaining to a particular frequency or carrier. A
`Station ID field 403 indicates the unique identifying code of
`55
`a broadcasting Station from which the Signal emanated. This
`field is optional. In one embodiment this field is filled by the
`MU using information received in the Signal. In another
`embodiment 45 this field is filled by the Other Party to
`indicate to the MU as to which signals to capture for the
`fingerprint. A Frequency field 405 is the unique frequency
`value at which a signal is captured. Either the Station ID
`field or the Frequency field is mandatory since without both
`it is not possible to identify the Signal. A Tuning Parameter
`field 407 is used when the MU requires additional informa
`tion to tune to a particular carrier. In one embodiment this
`field is supplied by the Other Party with information con
`
`45
`
`50
`
`60
`
`65
`
`6
`taining the modulation characteristics of the Signal. This
`field is optional. In one embodiment a Transmitter Location
`field 409 is used to characterize the received signals. In
`another embodiment this field is filled by the Other Party.
`The MU may optionally use this information to determine if
`it wants to capture the Signal emanating from a particular
`transmitter. Finally, Signal Strength fields 411,413, are filled
`by the MU based on the signal strengths of the received
`carriers. In one embodiment the Signal Strength is Sampled
`multiple times for each frequency in order to Smooth out any
`variations. At least one of the Signal Strength fields is
`required to be filled by the MU.
`FIG. 5 shows the high level structure of the fingerprint
`database 501 in one embodiment. As one skilled in the art
`can appreciate, there are many methods for building, man
`aging and Searching databases. The purpose of FIG. 5 is
`merely to illustrate the Structure of the database in one
`embodiment. Each row in database 501 corresponds to one
`fingerprint. The Lat and Long fields indicate the latitude and
`longitude of the location to which the fingerprint corre
`sponds. In one instance the fingerprint corresponds not to
`one exact Spot on the Surface of the earth, but instead to a
`Small area. The Lat and Long fields in this embodiment
`indicate a position inside the area, preferably the center
`point. The Time column indicates the time at which the
`fingerprint was captured. In one embodiment the UTC time
`format is used to indicate this time. The Fingerprint column
`contains the actual fingerprint data. In one embodiment the
`Structure depicted in FIG. 4 is used to Store the fingerprint
`data. Finally, the Description column contains a short
`description of the location corresponding to the fingerprint.
`For example, it may indicate a Street address, or an inter
`Section. This field is optional.
`Generation of the fingerprint database is another aspect of
`this invention. In one embodiment the database is built by
`taking off-line Snapshots of fingerprints at various locations.
`The fingerprint information along with the coordinates of the
`location are entered into the database. The more the
`locations, the richer the database. The resolution of location
`determination is also controlled by how far apart the fin
`gerprint Samples are taken. The closer they are, the higher
`the resolution. Of course, a perSon Skilled in the art can
`appreciate that the resolution of the database is limited by
`the Sensitivity of the fingerprint measuring device. In one
`embodiment the fingerprints are taken using very Sensitive
`Signal measuring devices that enable locations that are very
`close to each other to have distinct fingerprints.
`In another embodiment the database is built by taking
`fingerprint measurements at predetermined locations and
`using intelligent algorithms that interpolate the fingerprints
`at all locations in between the Sampled locations. This
`method has the advantage of not requiring a great many
`physical measurements to be made, however, it does Suffer
`from Some loSS in accuracy. This is because, however clever,
`the interpolating algorithms will not be as accurate as
`making the actual measurements.
`In yet another embodiment the database is generated on
`the fly using Smart algorithms that can predict the finger
`prints in a local area. This Scheme is effective in instances
`where an approximate idea of the MU is already available.
`For example, this could be the cell in which the MU is.
`Conclusion
`In conclusion, it can be seen that this invention has two
`Significant improvements over prior art location techniques.
`One, it can be be implemented without requiring any modi
`fications to existing This invention has two significant
`improvements utilized in areas where GPS coverage is not
`
`Page 10 of 11
`
`

`

`7
`available. This is because the fingerprints are generated by
`using portions of the RF Spectrum that typically have
`Superior coverage and in-building penetration than GPS
`Signals. Second, it can infrastructure.
`While the above is a complete description of specific
`embodiments of the invention, various modifications, alter
`native constructions, and equivalents may be used.
`Therefore, the above description should not be taken as
`limiting the Scope of the invention as defined by the claims.
`What is claimed is:
`1. A method for locating the position of a mobile unit in
`a wireleSS communication network, Said method comprising
`the following Steps:
`capturing a first fingerprint of the RF Spectrum in the
`mobile unit and Storing there with a time of capture;
`comparing Said first fingerprint with a multiplicity of
`fingerprints, each of Said multiplicity of fingerprints
`having an associated location, wherein Said multiplicity
`of fingerprints is designed, by including for at least
`Some fingerprints of Said multiplicity of fingerprints
`respective indications of time of capture to take into
`account a dynamic, but predetermined, change in Signal
`power as a function of time for Some signal frequencies
`in the RF spectrum;
`Selecting a Second fingerprint from Said multiplicity of
`fingerprints as the closest matching fingerprint to Said
`first fingerprint, wherein Said closest matching finger
`print is Selected based on the combination of Said
`indications of time of capture for Said multiplicity of
`fingerprints and Said time of capture for Said first
`fingerprint So as to account for Said dynamic, but
`predetermined change in Signal power as a function of
`time for Some signal frequencies in the RF spectrum;
`and
`assigning a location corresponding to Said Second finger
`print to Said mobile unit.
`2. The method of claim 1 wherein said first and second
`fingerprints are generated using a predetermined portion of
`the RF spectrum.
`3. The method of claim 2 wherein said predetermined
`portion of the RF spectrum overlaps with the portion of the
`RF spectrum utilized by the WireleSS communication net
`work.
`4. The method of claim 2 wherein said predetermined
`portion of the RF spectrum overlaps with the portion of the
`Spectrum utilized by commercial FM radio broadcasting
`Stations.
`5. The method of claim 1 wherein said first and second
`fingerprints are generated using a predetermined Set of
`Signal parameters.
`6. The method of claim 1 wherein said multiplicity of
`fingerprints is Stored in the mobile unit.
`7. The method of claim 6 wherein said location assign
`ment is performed by the mobile unit.
`8. The method of claim 1 wherein said multiplicity of
`fingerprints is stored in an Other Party that is linked to the
`mobile unit via the wireleSS communication network.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`US 6,269,246 B1
`
`8
`9. The method of claim 8 wherein said first fingerprint is
`processed and transmitted over the wireleSS communication
`network to the Other Party.
`10. The method of claim 9 wherein said location assign
`ment is performed by the Other Party.
`11. A method for locating the position of a mobile unit in
`a wireleSS communication network, Said method comprising
`the following Steps:
`capturing a first fingerprint of the RF Spectrum in the
`mobile unit and Storing there with a time of capture;
`comparing Said first fingerprint with a fingerprint
`database, each entry in Said fingerprint database having
`an associated location, wherein Said fingerprint data
`base is designed, by including for at least Some of the
`entries in the fingerprint database respective indications
`of time of capture to take into account a dynamic, but
`predetermined, change in Signal power as a function of
`time for at least Some Signal frequencies in the RF
`Spectrum,
`Selecting a Second fingerprint from Said fingerprint data
`base as the closest matching fingerprint to Said first
`fingerprint, wherein Said closest matching fingerprint is
`Selected based on the combination of Said indications of
`time of capture for each entry Stored in Said fingerprint
`database and Said time of capture for Said first finger
`print So as to account for Said dynamic, but predeter
`mined change in Signal power as a function of time for
`at least Some signal frequencies in the RF spectrum;
`and
`assigning a location corresponding to Said Second finger
`print to said mobile unit.
`12. The method of claim 11 wherein said first and second
`fingerprints are generated using a predetermined portion of
`the RF spectrum.
`13. The method of claim 11 wherein said multiplicity of
`fingerprints is St