USOO7346359B2
`
`(12) United States Patent
`Damara et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,346,359 B2
`Mar. 18, 2008
`
`(54)
`(75)
`
`(73)
`
`(*)
`
`(21)
`(22)
`(65)
`
`(60)
`
`(51)
`
`(52)
`
`(58)
`
`(56)
`
`METHOD FOR RF FINGERPRINTING
`
`Inventors: Chanakya Damarla, Pittsburgh, PA
`(US); James Ivers, Pittsburgh, PA (US);
`Mark Pollard, Hudson, MA (US);
`Andrew J. Kompanek, Pittsburgh, PA
`(US); Brian H. Trammell, Pittsburgh,
`PA (US)
`Assignee: Pango Networks, Inc., Framingham,
`MA (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 159 days.
`Appl. No.: 10/902,510
`
`Notice:
`
`Filed:
`
`Jul. 29, 2004
`
`Prior Publication Data
`Feb. 24, 2005
`US 2005/004O968 A1
`Related U.S. Application Data
`Provisional application No. 60/491,379, filed on Jul.
`31, 2003.
`
`Int. Cl.
`(2006.01)
`H04O 7/20
`455/456.1; 455/404.2:
`U.S. Cl. ...............................
`455/456.2:455/456.3:455/456.5; 455/456.6;
`455/457
`Field of Classification Search ..... 455/4.56.1457,
`455/456.3, 414.1–4, 404.2, 432.1, 435.1,
`455/440-441: 701/207,213–214; 340/988:
`342/357.1, 357.06, 357.12,450, 457
`See application file for complete search history.
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,121,126 A *
`5,539,395 A
`5,554.321 A
`
`6/1992 Clagett ....................... 342/419
`7, 1996 Buss et al.
`9/1996 Choy et al.
`
`9, 1996 Theimer et al.
`5,555,376 A
`5,559.520 A * 9/1996 Barzegar et al. ......... 342,357.1
`5,570,085 A 10, 1996 BertSch
`5,572,195 A 11/1996 Heller et al.
`5,579,535 A 11/1996 Orlen et al.
`5,717.406 A * 2/1998 Sanderford et al. ......... 342/457
`5,717,688 A
`2/1998 Belanger et al.
`5,719,584. A * 2/1998 Otto ........................... 342/.465
`5,796,727 A
`8, 1998 Harrison et al.
`5,796,827 A
`8/1998 Coppersmith et al.
`5,812,865 A
`9, 1998 Theimer et al.
`5,898,831 A
`4/1999 Hall et al.
`5,903.548 A
`5/1999 Delamater
`5,909, 183 A
`6/1999 Borgstahl et al.
`
`(Continued)
`FOREIGN PATENT DOCUMENTS
`
`WO
`
`WO 99.483.15
`
`9, 1999
`
`(Continued)
`Primary Examiner Steve M. D’Agosta
`(74) Attorney, Agent, or Firm—Haynes and Boone LLP
`
`(57)
`
`ABSTRACT
`
`The invention provides a novel method for preparing a
`wireless environment for location determination of a wire
`less mobile unit, and for location determination of a wireless
`mobile unit. In preparing the physical environment, the
`invention utilizes novel techniques, including novel tech
`niques to place transmitters, the removal of outlying data in
`the creation of reference RF fingerprints, and algorithms to
`obtain accurate reference RF fingerprints. In determining the
`location of a wireless mobile unit, the invention utilizes
`novel techniques, including novel techniques to select trans
`mitters, the removal of outlying data in the creation of
`reference RF fingerprints, and algorithms to obtain accurate
`reference RF fingerprints.
`
`21 Claims, 10 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Place
`transmitters
`(100)
`
`RF data
`collection
`(200)
`
`Transmitter placement heuristics
`
`Base location algorithms on empirical data
`Base location algorithms on multiple data points
`Baselocation algorithms on multiple orientations
`
`Produce reference
`RF fingerprints
`(300)
`
`Base fingerprints on multiple data points
`Interpret missed transmissions
`Remove outliers
`Select transmitters for reference RF fingerprints
`Hysteresis criteria
`
`Analyze reference
`RF fingerprints
`(400)
`Fingerprint matching algorithm
`Hysteresis criteria
`
`Deploy reference
`RF fingerprints
`(500)
`Tag reference RF fingerprints
`
`
`
`Page 1 of 22
`
`SAMSUNG EX-1028
`
`

`

`US 7,346,359 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`
`
`7/1999 Sasaki ..................... 455,456.1
`5,926,765 A
`5,950,123. A * 9/1999 Schwelb et al. ......... 455/414.4
`5,953,425 A
`9, 1999 Selker
`5,973,643 A * 10/1999 Hawkes et al. ............. 342/457
`5,977,913 A 11, 1999 Christ
`6,026,304. A * 2/2000 Hilsenrath et al. ....... 455,456.2
`6,069,896 A
`5/2000 Borgstahl et al.
`6,091,956 A
`7/2000 Hollenberg
`6,263,208 B1* 7/2001 Chang et al. ............ 455,456.3
`6,269,246 B1
`7/2001 Rao et al.
`6,281,811 B1
`8, 2001 Ranzino
`6,347,095 B1
`2/2002 Tang et al.
`6,393,294 B1* 5/2002 Perez-Breva et al. ... 455/456.5
`6,456,239 B1
`9, 2002 Werb et al.
`6,496,701 B1* 12/2002 Chen et al. .............. 455,456.5
`
`3/2003 Pfeffer et al.
`6,529,728 B1
`3/2003 Waters et al.
`6,535,132 B2
`7/2003 Treyz et al.
`6,587,835 B1
`6,647.269 B2 11/2003 Hendrey et al.
`6,650,902 B1 * 1 1/2003 Richton ................... 455,456.3
`6,674,403 B2
`1/2004 Gray et al.
`6,728,632 B2
`4/2004 Medl
`6,782,265 B2 * 8/2004 Perez-Breva et al. .... 455/4.56.1
`6,898,415 B2
`5/2005 Berliner et al.
`6,992.625 B1* 1/2006 Krumm et al. ............. 342/451
`2002/0169539 A1* 11/2002 Menard et al. ............. TO1,200
`
`WO
`WO
`
`FOREIGN PATENT DOCUMENTS
`WO O1/37597 A1
`5, 2001
`WO O1? 43419 A2
`6, 2001
`
`* cited by examiner
`
`Page 2 of 22
`
`

`

`U.S. Patent
`
`Mar. 18, 2008
`
`Sheet 1 of 10
`
`US 7,346,359 B2
`
`Figure 1
`
`Page 3 of 22
`
`

`

`U.S. Patent
`U.S. Patent
`
`Mar. 18, 2008
`Mar.18, 2008
`
`Sheet 2 of 10
`Sheet 2 of 10
`
`US 7,346,359 B2
`US 7,346,359 B2
`
`
`
`Figure2
`
`i
`
`Page 4 of 22
`
`Page 4 of 22
`
`

`

`U.S. Patent
`U.S. Patent
`
`Mar. 18, 2008
`Mar.18, 2008
`
`Sheet 3 of 10
`Sheet 3 of 10
`
`US 7,346,359 B2
`US 7,346,359 B2
`
`
`
`50a
`
`40a
`
`5
`
`i
`Figure3
`
`Page 5 of 22
`
`Page 5 of 22
`
`

`

`U.S. Patent
`
`Mar. 18, 2008
`
`Sheet 4 of 10
`
`US 7,346,359 B2
`
`SJØ???uusugu)
`
`90 BId
`
`(001)
`
`(009)
`Squ?udu93u? TRI
`
`
`
`
`
`
`
`Page 6 of 22
`
`

`

`U.S. Patent
`
`Mar. 18, 2008
`
`Sheet S of 10
`
`US 7,346,359 B2
`
`uo?09IIoo
`
`(0001)
`
`
`
`
`
`
`
`Page 7 of 22
`
`

`

`U.S. Patent
`U.S. Patent
`
`
`
`Sheet 6 of 10
`Sheet 6 of 10
`
`US 7,346,359 B2
`US 7,346,359 B2
`
`Mar. 18, 2008
`Mar.18, 2008
`
`Figure6
`
`C ,
`
`i
`
`Page 8 of 22
`
`Page 8 of 22
`
`

`

`U.S. Patent
`
`Mar. 18, 2008
`
`Sheet 7 of 10
`
`US 7,346,359 B2
`
`Lemnsty
`
`||p201s9LPOPhEFOIPSPLY0000oum[||
`
`
`WWLPOErOIPSrLy0000own[|_d
`[9pLbObhChOIhSpLp0000
`[|||9sor]s
`oun}Ld ¢901]8
`9LPOPYEPOTYSPLVN000
`9pLVObhCVOTYSPLVO0000
`[OFLe0pbEh0IhSpLp0000
`
`[|__|
`
`|__|
`
`L__|
`oun
`
`Page 9 of 22
`
`|sors
`
`out}
`
`Z9oljs
`
`QUIT}
`
`€201]
`
`Page 9 of 22
`
`

`

`U.S. Patent
`U.S. Patent
`
`Mar. 18, 2008
`Mar.18, 2008
`
`Sheet 8 of 10
`Sheet 8 of 10
`
`US 7,346,359 B2
`US 7,346,359 B2
`
`
`
`Figure8
`
`i
`
`Page 10 of 22
`
`Page 10 of 22
`
`

`

`U.S. Patent
`U.S. Patent
`
`Mar. 18, 2008
`Mar.18, 2008
`
`Sheet 9 of 10
`Sheet 9 of 10
`
`US 7,346,359 B2
`US 7,346,359 B2
`
`
`
`Figure9
`
`i
`
`Page 11 of 22
`
`Page 11 of 22
`
`

`

`U.S. Patent
`
`Mar. 18, 2008
`
`Sheet 10 of 10
`
`US 7,346,359 B2
`
`
`
`too solo soloiosolo
`
`2
`
`50 50 50 50 50 50
`50
`
`
`
`FIGURE 10
`
`Page 12 of 22
`
`

`

`US 7,346,359 B2
`
`1.
`METHOD FOR RF FINGERPRINTING
`
`CLAIM OF PRIORITY
`
`Pursuant to 35 U.S.C. 119(e), this application claims the
`benefit of U.S. Provisional Application No. 60/491,379 filed
`Jul. 31, 2003.
`
`FIELD OF THE INVENTION
`
`The claimed invention relates to location of mobile units
`in a wireless environment. Further, the claimed invention is
`a method for preparing a physical environment for location
`of a mobile unit.
`
`BACKGROUND OF THE INVENTION
`
`10
`
`15
`
`2
`measuring device is insufficient to distinguish between the
`RF fingerprints at the locations. It can also happen because
`the RSSI data at one or more of the locations is relatively
`unstable. This means that the signal strength changes in
`unpredictable ways (e.g., a signal strength that is often +/-4
`dBm different than recorded in the RF fingerprint).
`The prior art does not address unpredictable variation, as
`opposed to predictable variation, such as a transmitter that
`powers down at the same time every day. Unpredictable
`variation can have many causes, such as: 1) multipath
`effects; 2) transitory obstacles between the MU and a
`transmitter (e.g., a person walking by); and 3) temporary
`environmental changes (e.g., a door opening and closing).
`Another cause for an RF environment to be ambiguous
`relates to the placement of transmitters which can result in
`aliasing problems. Two distinct locations can have the same
`RF fingerprint given a particular transmitter placement. See
`FIG. 1 for an example. FIG. 1 is an illustration of an aliasing
`problem. A MU at each location on the ring around trans
`mitter 1 receives the same strength signal from transmitter 1,
`each location on the ring is an alias (i.e., has the same RF
`signature) of all other locations on the ring. Likewise for a
`MU at each location around transmitter 2 with respect to
`transmitter 2. While adding a second transmitter usually
`clears up Such ambiguities, not all are necessarily removed.
`At the two locations 3 and 4, the RF environment is
`indistinguishable, even with two transmitters.
`There also exists a need to improve RF fingerprinting for
`real-time MU location determination. Real-time location
`determination attempts to keep track of a MU as it moves
`about in an environment. This has many useful applications,
`such as being able to offer location specific directions as a
`MU user moves around in an unfamiliar environment. To
`offer real-time location determination, location estimates
`must be produced relatively often (e.g., close to once per
`second as opposed to a couple of times per minute).
`This introduces two new problems to basic RF finger
`printing techniques. First, when gathering data to generate
`an RF fingerprint, signals may not be observable from all
`transmitters used in generating the fingerprint. This can have
`several meanings, none of which are distinguishable at the
`MU. For instance, 1) the signal from the transmitter is too
`weak to be observed by the MU at its current location; 2) the
`transmitter may not be transmitting as often as the MU is
`observing (e.g., if a MU produces an RF signature once per
`second and a transmitter used in producing RF fingerprints
`only transmits once per second, then Some RF fingerprints
`will not include new data for that transmitter); and 3) the
`transmitter may be transmitting often enough, but the signal
`may collide with another transmission and not be observed.
`Therefore, when each RF fingerprint is generated, some
`interpretation must be assigned to transmitters from which
`no signal was observed since the last RF fingerprint was
`generated.
`For example, consider the following sequence of signal
`strength measurements for a particular transmitter: 47, 45.
`41, 0, 43, 44, 0, 47 and 46. There are two time slices at which
`no signal can be observed for the transmitter (denoted by
`Zeros for the signal strength measurement). Looking at the
`data before and after these time slices (and assuming that
`signals are being sampled relatively quickly), the inventors
`of the present invention, unlike the prior art, can deduce that
`the transmitter signal is not likely to be too weak to be
`observed in these time slices. In contrast to the prior art, the
`present invention takes into account that it is more likely that
`some intermittent problem has temporarily prevented the
`transmitter's signal from being observed.
`
`RF fingerprinting is a method for locating the position of
`a mobile unit (MU) in a wireless communication network.
`RF fingerprinting is described generally in U.S. Pat. No.
`6,269,246.
`RF fingerprinting is particularly useful in indoor settings
`where technologies such as GPS are typically not reliable. It
`works with information already available in indoor settings,
`Such as the received signal strength indicator (RSSI or signal
`strength) obtainable from an IEEE 802.11 network installed
`to provide wireless connectivity, and does not require any
`additional hardware. As such, RF fingerprinting is a good
`technique for determining MU location in a wireless envi
`ronment without requiring the installation of additional
`hardware.
`There are several known variations in RF fingerprinting
`technology. Prominent examples include: 1) selection of
`what portion of the RF spectrum to scan; 2) different
`techniques for generating the RF fingerprint database; and 3)
`different search algorithms for determining the closest
`matching fingerprint.
`The resolution of location determination is largely con
`trolled by how far apart the fingerprint samples are taken.
`The closer they are, the higher the resolution. Of course, a
`person skilled in the art can appreciate that the resolution is
`limited by the sensitivity of the fingerprint measuring
`device. In addition, if two fingerprints for different locations
`look too much alike (e.g., due to insufficient sensitivity in
`the measuring device), then accuracy is lessened.
`Thus, there exists a need for a method for extending RF
`fingerprinting to provide real-time, high resolution location
`estimates of a MU in a wireless communication environ
`ment. For purposes of this disclosure, “real-time” means the
`production of location estimates close to once per second.
`“High resolution” means resolution on the order of distin
`guishing between office cubicles (i.e., 2-3 meters) rather
`than between buildings. There also exists a need for a
`method to cope with ambiguous RF environments in which
`two locations that should be distinguishable are not.
`Techniques included in that method should include the
`following: 1) techniques for preprocessing raw RF samples
`to derive an RF fingerprint; 2) techniques for searching for
`RF fingerprint matches; and 3) techniques for filtering
`multiple RF fingerprint matches and presenting a single best
`estimate.
`As stated before, there exists a need to improve RF
`fingerprinting in ambiguous RF environments. An RF envi
`ronment is ambiguous for the purposes of location determi
`nation when two distinct locations cannot be distinguished,
`based on their RF fingerprints, with a desired probability of
`Success. This can happen because the sensitivity of the
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Page 13 of 22
`
`

`

`US 7,346,359 B2
`
`3
`On the other hand, consider the following sequence: 20,
`18, 0, 16, 14, 0, 0, 5, 0, 0, 0 and 0. While the inventors of
`the present invention could similarly deduce that the first
`time slice in which the signal could not be observed is likely
`to be due to an intermittent problem, the subsequent time
`slices in which the signal could not be observed are more
`likely to be due to the transmitter's signal being too weak.
`The present inventors base this conclusion on the consistent
`weakening of the signal, which is likely to represent move
`ment away from the transmitter, and the longer sequence of
`consecutive time slices in which the transmitter's signal
`could not be observed. Such techniques are not described in
`the prior art.
`The second problem related to producing frequent loca
`tion estimates is that producing a new location estimate each
`time a new RF fingerprint is generated can result in a jittery
`series of estimates. When a rapid series of changing location
`estimates is presented to a user, the user's confidence in the
`estimates drops significantly. Two examples of Such jitter
`problems are shown in FIG. 2 and FIG. 3. In FIG. 2, a user
`is standing between locations 10 and 20. In such a situation,
`a bad series of estimates would jitter between 10 and 20,
`with no stability at either location. In FIG. 3, the user is
`standing near locations 10a and 30a. This is similar to FIG.
`2 in which jitter between 10 and 20 would be unreliable, but
`user confidence would be even lower because it is physically
`impossible to move back and forth through the wall 40a
`having a door 50a separating the locations. Thus, there exists
`a great need to resolve said jittery estimates.
`
`5
`
`10
`
`15
`
`25
`
`30
`
`4
`ematical function is described partially above and in the
`detailed description of the preferred embodiment below. The
`method of determining a location of a mobile unit in an area
`configured for wireless location determination of said
`mobile unit further comprises selecting RF samples based on
`a rule. Those rules will be described below and are embodied
`within the scope of the appended claims.
`It is an object of the present invention to prepare a
`physical environment for location determination of a mobile
`unit in Such a way that will increase the accuracy of
`reference fingerprints used to provide location estimates for
`a mobile unit.
`It is a further object of the invention to accurately report
`the location of a mobile unit in a wireless environment.
`Other objects and embodiments of the invention are
`described below. It is to be understood, however, that the
`invention is not to be limited to the disclosed embodiments,
`but on the contrary is intended to cover various modifica
`tions and equivalent arrangements included within the spirit
`of the Scope of the appended claims.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is an illustration of an aliasing problem solved by
`the present invention.
`FIGS. 2 and 3 show examples of inaccurate location
`estimation caused by jitter problems, which are solved by
`the present invention.
`FIG. 4 shows a high-level overview of the survey process
`used to prepare a physical environment for location deter
`mination according to an embodiment the present invention.
`FIG. 5 shows a high level overview of the run-time
`process used to estimate the location of a MU in a wireless
`enabled physical environment according to an embodiment
`of the present invention.
`FIG. 6 shows the implications of poor wireless access
`point placment, which are remedied by the present inven
`tion.
`FIG. 7 illustrates the application of an algorithm designed
`to provide for more accurate reference RF fingerprints and
`location estimates according to an embodiment of the
`present invention.
`FIG. 8 shows a sample physical environment.
`FIG. 9 shows the results of setting different cut-offs for
`location determination according to an embodiment of the
`present invention.
`FIG. 10 shows transition matrix according to an embodi
`ment of the present invention.
`
`DETAILED DESCRIPTION OF THE
`PRESENTLY PREFERRED EMBODIMENT
`
`The claimed invention is directed to location of mobile
`units in a wireless environment and to preparing a physical
`environment for location of a mobile unit. The preparation
`of the physical environment is referred to herein as the
`survey process, while the actual location of the mobile unit
`in the physical environment is referred to as the run-time
`process. In each of these processes, the claimed invention
`provides techniques. Some techniques are particular to the
`Survey process, while others are particular to the run-time
`process, while still other techniques are relevant to both the
`Survey process and the run-time process.
`A high-level overview of the survey process used to
`prepare a physical environment for location determination is
`shown in FIG. 4. Each step is annotated with the techniques
`that are applied during that step in the Survey process.
`
`SUMMARY AND OBJECT OF THE INVENTION
`
`In a preferred embodiment, the invention is a method of
`preparing an area for location determination of a mobile unit
`which provides at least two transmitters that are consistently
`detectable by a mobile unit at locations in the area. In
`another embodiment, the invention is a method for preparing
`an area for location determination of a mobile unit by
`providing at least two transmitters that are located along
`different axes with respect to a plurality of locations in said
`aca.
`Another step in the method is collecting RF data of the
`mobile unit at said locations in said area. The invention
`assigns a unique reference RF fingerprint for each of the
`locations based on the collected RF data for each of said
`locations. In another embodiment, reference RF fingerprints
`are also created for a specific orientation.
`The above method applies mathematical functions to
`collected RF data in assigning reference RF fingerprints, for
`example, the invention provides for the averaging of the
`collected data respective to each location to obtain an
`average and assigning a reference RF fingerprint respective
`to each location based each respective average.
`The invention provides a novel step by interpreting the RF
`data for missed transmissions and assigning unique refer
`ence RF fingerprints based on the interpreted data. The
`method also determines if any of the collected data is
`outlying. If so, the invention may not consider said outlying
`data in creating a reference RF fingerprint.
`The invention uses similar techniques to determine a
`location of a mobile unit in an area configured for wireless
`location determination of said mobile unit. The invention
`does so by collecting samples of RF data of a mobile unit at
`said location; applying a mathematical function to said
`samples to obtain a value that is used as an RF fingerprint;
`and determining the similarity of said RF fingerprint to
`location specific data. The novel application of said math
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Page 14 of 22
`
`

`

`5
`As shown in FIG. 4, the first step is to place transmitters
`100. Typically when placing transmitters to wirelessly
`enable an environment (e.g., when placing IEEE 802.11
`access points or APs), the primary concern is coverage.
`When only coverage is considered, a MU should be able to
`receive a signal from at least one AP anywhere within the
`environment. For location determination, placement of a
`minimal number of APS that ensures coverage is usually
`insufficient.
`Once transmitters are placed, RF data collection 200 is
`performed. AMU is taken to various planned locations in the
`environment. At each location, RF samples are taken and
`recorded. Each sample records information about the RF
`environment (e.g., signal strength of transmissions from
`various sources) and is associated with a timestamp and
`location.
`The data is then used to produce RF fingerprints 300. 300
`cleans up the data that was gathered in RF data collection
`200 and produces an amalgam of the data. Then a selection
`is made as to which transmitters found in the data are best
`Suited to represent the location. For example, two actual
`physical locations may exhibit RF data from the same AP. If
`the two locations exhibit the same or highly similar RF data
`from that AP, that RF data is not useful in distinguishing the
`locations. But if the locations exhibit distinguishable RF
`data for the same AP, that data will be selected to represent
`one or both of the locations. The result is a set of data
`corresponding to a subset of the observable transmitters that
`are associated with the location. RF fingerprints produced in
`this process are called reference RF fingerprints.
`Once reference RF fingerprints have been produced, algo
`rithms are run to analyze the RF fingerprints 400. The
`fingerprints are compared to a set of data that is also
`associated with locations. A run-time location determination
`algorithm is simulated against the data set. The results are
`compared to the locations associated with the fingerprints.
`This results in accuracy and resolution statistics for the
`reference RF fingerprints as compared to the data set used in
`analysis. The data set can be that which was used in
`producing the reference RF fingerprints, or an independent
`set of data. This analysis has obvious benefits: changes to RF
`fingerprints can be tested quickly without affecting a live
`deployment. And, iterative techniques that apply a change
`and measure the results can be automated and do not require
`Successive changes to an installed RF environment, multiple
`trips back and forth to a physical environment for testing, or
`multiple system restarts to reload RF fingerprint data.
`If the accuracy and resolution statistics do not meet
`location determination requirements, several options are
`available depending on how well or poorly the analysis
`results match the requirements. Those options are as fol
`lows: 1) producing a new set of reference RF fingerprints
`using the same data set and a different set of configuration
`parameters; 2) collecting a new set of data, or collecting
`additional data to add to the existing data set, or 3) adding
`or removing transmitters.
`When satisfied with the results of the analysis, the refer
`ence RF fingerprints are deployed 500 to the computing
`infrastructure used to Support location determination in the
`environment. This infrastructure could be a server that
`delivers reference RF fingerprint information to MUs, or it
`could be the MUs themselves.
`Over time, changes in the RF environment may require
`revisiting this process. For example, if a permanent envi
`ronment change affecting RF propagation were made (e.g.,
`taking down a wall or moving a large metal shelf), then the
`RF data collection step should be repeated, possibly fol
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 7,346,359 B2
`
`6
`lowed by the Subsequent steps. In general, however, this
`process will be conducted infrequently.
`A high level overview of the run-time process used to
`estimate the location of a MU in a wireless-enabled physical
`environment is shown in FIG. 5. Each step is annotated with
`the techniques that are applied during that step in the
`run-time process. This process represents an iterative pro
`cess that is conducted as long as a MU is in a wireless
`environment and location determination is desired. Each
`iteration is referred to as a time slice. It begins each time the
`MU begins observing the RF activity in its environment and
`concludes when a location estimate is made for the MU.
`As shown in FIG. 5, the first step is to collect RF data
`1000. The MU observes the RF environment for some
`period of time to gather signal strength data. This is the same
`type of data that is gathered in the Survey process. It is
`important to note that in many cases a MU cannot always
`observe the RF environment. For example, a MU equipped
`with an 802.11 radio can only use the radio for one purpose
`at a time. It can either transmit information or receive
`information. When it receives information, such as periodic
`beacons from APs, it records information (like received
`signal strength) that can be used for location determination.
`In each time slice, the MU gathers one measurement for
`each transmitter that it observes during that time slice.
`For each time slice, the data is used to produce a MURF
`fingerprint 2000. Some preprocessing is performed to clean
`up the data, Some of which is dependent on data from
`previous time slices. This RF fingerprint, unlike the refer
`ence RF fingerprints produced in the Survey process, pref
`erably retains information for all observable transmitters. An
`RF fingerprint produced at run-time is called a MU RF
`fingerprint.
`The MU RF fingerprint is compared or matched to the
`reference RF fingerprints 3000 produced in the survey
`process. A set of location estimates is determined based on
`the reference fingerprints and criteria associated with them.
`Finally, some additional filtering 4000 may be performed
`to refine the set of location estimates that has been produced,
`depending on the needs of the application using the location
`estimates. Two techniques included in this method are:
`using a location transition graph to define which transi
`tions are more probable and which are impossible; and
`using a time based voting algorithm to pick a single best
`estimate.
`Whether additional filtering 4000 is performed or not, at
`the end of each time slice a set of location estimates is
`provided to the party requesting location determination
`information.
`The following subsections describe the techniques
`applied during either the Survey process, the run-time pro
`cess, or both.
`The invention comprises techniques to place wireless
`transmitters or access points. This technique is used only in
`the Survey process. To enhance location accuracy and sta
`bility, “strong signals from at least two or three wireless
`access points should be detectable at each location in the
`environment. "Strong signals are those which are consis
`tently detectable (i.e., missed transmissions, discussed in the
`below section, are infrequent). Ideally, wireless access
`points should be located along different axes with respect to
`as many locations as possible to cope with aliasing. Such a
`placement results in the strength of the signals from one of
`the access points increasing and the strength of signals from
`other access points decreasing as a MU moves.
`FIG. 6 shows the implications of poor wireless access
`point placment. Wireless access points are shown as Solid
`
`Page 15 of 22
`
`

`

`7
`circles; MU locations are shown as solid diamonds. Due to
`poor placment, MUs at locations A and B are indistinguish
`able (aliases of each other) as the distance to each of the
`three access points is indentical (implying a corresponding
`relationship to RF data at the locations). A similar problem
`will exist for MUs at locations C and D, or any other pair of
`locations equidistant from the axis along which the wireless
`access points are deployed.
`In the Survey process, location estimates are based on
`empirical RF data collected using a MU at the physical
`environment. Each set of RF data is associated with specific
`locations in the physical environment. Interpolation and RF
`signal propagation models are not used to estimate what RF
`data should look like at locations at which data was not
`collected. This is due to the relative instability of RF data
`over short distances due to issues such as multipath effects.
`Additionally, in an embodiment where the invention targets
`locations placed relatively close together (i.e., 2-3 meters
`apart), intermediate locations vary little from mapped loca
`tions and the difference plus or minus the RF variation
`would make interpolated intermediate locations indistin
`guishable.
`RF data is expressed in terms of received signal strength
`indicators (“RSSI) in a wireless environment. More spe
`cifically, the strength of signals received from wireless
`access points located in the physical environment is the
`source of RF data. This is due to several practical reasons,
`Some of which are as follows: 1) wireless access points are
`already deployed in the environment, lowering deployment
`cost; 2) wireless access points are non-mobile, installed at
`known locations, and are moved infrequently; and 3) RSSI
`data can be easily gathered using the same types of MUs
`whose locations are to be estimated, resulting in data that
`most closely matches that observed by MUs at run-time
`(e.g., because the same type of antenna is used).
`One technique for dealing with relatively unstable RF
`environments that is used in both the Survey and run-time
`processes is basing a fingerprint on multiple data samples.
`Averaging signal strength over the last N samples results in
`a more typical signal strength reading, for a large enough N.
`This technique deals with small scale, brief variation.
`When gathering data for reference RF signatures, a com
`paratively large number of samples (e.g., 15-30) is taken at
`each location. During the preprocessing step, these values
`will be averaged (preferably after outliers are removed and
`missed transmissions are interpreted). By gathering more
`data, representing the location over a longer period of time,
`a more characteristic reading can be produced. For example,
`the effects of a pedestrian walking by while gathering data
`will be averaged out.
`When gathering data for MU RF signatures, the same
`technique is applied, but over a smaller number of samples
`(e.g., 2-4). Averaging is performed to deal with the same
`small scale, brief variations. The number of samples is
`typically smaller, however, since the MU may be moving.
`For a moving MU, each additional sample included in the
`average introduces a lag effect. For example, if six samples
`were included in an average, and samples were collected
`once per second, then a given location estimate would
`include data for where the MU was located six seconds ago.
`In a highly mobile setting, this degree of lag may be
`intolerable.
`The number of samples averaged in each process is
`configurable, and may vary in different settings and for
`different use cases. The value of N is based on the antici
`pated MU movement rate for the physical environment in
`which location estimates are desired. The choice of N is a
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 7,346,359 B2
`
`10
`
`15
`
`8
`tradeoff between how quickly a new location is estimated
`once a MU moves there, and how unstable (inaccurate or
`frequent location estimate changes) the location estimates
`are. If MUs move quickly, a small N may be u