USOO7474897B2
`
`(12) United States Patent
`Morgan et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7.474,897 B2
`Jan. 6, 2009
`
`(54) CONTINUOUS DATA OPTIMIZATION BY
`FILTERING AND POSITONING SYSTEMS
`
`(75) Inventors: Edward J. Morgan, Needham, MA
`(US); Michael G. Shean, Boston, MA
`(US); Farshid Alizadeh-Shabdiz,
`Wayland, MA (US); Russel K. Jones,
`Roswell, GA (US)
`(73) Assignee: Skyhook Wireless, Inc., Boston, MA
`(US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 491 days.
`
`(*) Notice:
`
`21) Appl. No.: 11/359,271
`(21) Appl. No
`9
`(22) Filed:
`Feb. 22, 2006
`(65)
`Prior Publication Data
`
`US 2006/0240840 A1
`
`Oct. 26, 2006
`
`Related U.S. Application Data
`(63) Continuation-in-part of application No. 1 1/261,988,
`filed on Oct. 28, 2005, now Pat. No. 7,305,245.
`(60) Provisional application No. 60/654,811, filed on Feb.
`22, 2005.
`
`(51) Int. Cl.
`(2006.01)
`H04O 7/20
`(52) U.S. Cl. .............. 455/456.5; 455/456.6:455/4.56.1:
`340/539.13: 701/209
`(58) Field of Classification Search .............. 455/456.5,
`455/4.56.1, 456.3: 340/539.13: 701/209
`See application file for complete search history.
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`8, 2001 Kubota et al.
`6,272.405 B1
`1/2004 Khavakh et al.
`6,678,611 B2
`6,799,049 B1* 9/2004 Zellner et al. ............ 455,456.1
`6,862,524 B1* 3/2005 Nagda et al. ................ TO1,209
`
`5/2005 Eaton et al.
`6,888,811 B2
`6,978,023 B2 12/2005 Dacosta
`7,123,928 B2 10/2006 Moeglein et al.
`7,167,715 B2
`1/2007 Stanforth
`7,167,716 B2
`1/2007 Kim et al.
`7.305,245 B2 12/2007 Alizadeh-Shabdiz et al.
`7,397,424 B2
`7/2008 Houri
`7,403,762 B2
`7/2008 Morgan et al.
`
`(Continued)
`OTHER PUBLICATIONS
`U.S. Appl. No. 1 1/625,450, Alizadeh-Shabdiz.
`(Continued)
`Primary Examiner Danh C Le
`74). Att
`Agent, or Firm—Wilmer Cutler Pickering Hal
`& trig gent, or Firm
`1Imer Uuuer F1cKering Hale
`
`(57)
`
`ABSTRACT
`
`-
`-
`-
`Methods and systems of continuously optimizing data in
`WiFi positioning systems. A location-based services system
`for WiFi-enabled devices calculates the position of WiFi
`enabled devices. A WiFi-enabled device communicates with
`WiFi access points within range of the WiFi-enabled device
`so that observed WiFi access points identify themselves. A
`reference database is accessed to obtain information specify
`ing a recorded location for each observed WiFi access point.
`The recorded location information for each of the observed
`WiFi access points is used in conjunction with predefined
`rules to determine whether an observed WiFi access point
`should be included or excluded from a set of WiFi access
`points. The recorded location information of only the WiFi
`access points included in the set are used and the recorded
`location information of the excluded WiFi access points are
`excluded when calculating the geographical position of the
`WiFi-enabled device.
`
`4 Claims, 6 Drawing Sheets
`
`RSS
`AP Acaddress
`is
`O:11:33:da3:5
`ossaess
`does.c2:1f
`
`Access Point Evaluation: Data Flows
`
`-
`
`-
`
`-
`
`-->
`
`Observed APs compared
`against database
`
`All observed Access Points 501
`AP MAC address
`RSS status
`Latitudelongitude
`0:11:33:das:50-75 Known
`42.5iS471.2453
`300c:41c.24:1f86. Known
`"
`5:06:
`01:33:24.7 known
`f
`
`42.8763.
`
`-----
`
`Suspect Access Points)4
`
`42.8743.34S40
`
`-->
`
`Bad data filtered
`
`9
`42.877-71.24310
`O:40:36:31:48:cis-94 Known
`Known Access Points 502
`
`AP MAC at
`
`88
`20:11:33:0c:ae:10 -83 New
`
`RSS Stati
`
`latitide longitud
`tie dits
`
`A.
`New access points added
`to database
`
`
`
`85 New
`
`73 Ngw
`
`Page 1 of 14
`
`SAMSUNG EX-1059
`
`

`

`US 7,474,897 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`7/2003 Riley et al.
`2003/O125045 A1
`2003/O146835 A1*
`8/2003 Carter ................... 340,539.13
`2003/0225893 A1
`12/2003 Roese et al.
`2004, OO19679 A1
`1/2004 E et al.
`2004/0039520 A1
`2/2004 Khavakh et al.
`2004/OO87317 A1
`5, 2004 Caci
`2004/O124977 A1*
`7/2004 Biffar .................... 340,539.13
`2004/0205234 A1
`10, 2004 Barracket al.
`2005.0020266 A1
`1/2005 Backes et al.
`2/2005 Moeglein et al.
`2005/OO37775 A1
`9/2005 Sheynblat
`2005, 0192024 A1
`2005/0227711 A1* 10, 2005 Orwant et al. ............ 455,456.3
`2006,0009235 A1
`1/2006 Sheynblat et al.
`2006, OO78122 A1
`4/2006 Dacosta
`2006/0092015 A1* 5/2006 Agrawal et al. ........ 340,539.13
`2006/0095348 A1
`5, 2006 Jones et al.
`2006/0095349 A1
`5/2006 Morgan et al.
`2006/0106850 A1
`5/2006 Morgan et al.
`2006/O128397 A1* 6/2006 Choti et al. .............. 455,456.1
`2006/O197704 A1
`9, 2006 Luzzatto et al.
`2006/020O843 A1
`9/2006 Morgan et al.
`2006/0217131 A1
`9, 2006 Alizadeh-Shabdiz et al.
`2006/0240840 A1 10/2006 Morgan et al.
`2007/0097511 A1
`5, 2007 Das et al.
`2007/O126635 A1
`6, 2007 Houri
`2007/O150516 A1
`6/2007 Morgan et al.
`2007/0202888 A1
`8, 2007 Brachet et al.
`2007/0232892 A1 10, 2007 Hirota
`2007/0258408 A1 11/2007 Alizadeh-Shabdiz et al.
`2008, 0008117 A1
`1/2008 Alizadeh-Shabdiz
`2008, 0008118 A1
`1/2008 Alizadeh-Shabdiz
`2008, 0008119 A1
`1/2008 Alizadeh-Shabdiz
`2008, 0008120 A1
`1/2008 Alizadeh-Shabdiz
`2008, 0008121 A1
`1/2008 Alizadeh-Shabdiz
`2008, OO33646 A1
`2/2008 Morgan et al.
`2008. O132170 A1
`6, 2008 Alizadeh-Shabdiz et al.
`2008. O1392.17 A1
`6, 2008 Alizadeh-Shabdiz et al.
`2008. O176583 A1
`7/2008 Brachet et al.
`
`OTHER PUBLICATIONS
`International Search Report, International Application No. PCT/
`US07/62721, mailed Nov. 9, 2007. (3 pages).
`
`LaMarca, A., et al., “Self-Mapping in 802.11 Location Systems.”
`Intel Corporation, 2005.
`U.S. Appl. No. 1 1/261,848, Morgan et al.
`U.S. Appl. No. 1 1/359,154, Morgan et al.
`U.S. Appl. No. 1 1/359,144. Morgan et al.
`U.S. Appl. No. 1 1/359,271, Morgan et al.
`U.S. Appl. No. 1 1/430,079, Alizadeh-Shabdiz et al.
`U.S. Appl. No. 1 1/430,224. Alizadeh-Shabciz et al.
`U.S. Appl. No. 1 1/430,222, Alizadeh-Shabdiz et al.
`U.S. Appl. No. 1 1/429,862, Alizadeh-Shabdiz et al.
`U.S. Appl. No. 1 1/730,064, Alizadeh-Shabdiz et al.
`Hellebrandt, M., et al., “Estimating Position and Velocity of Mobile
`in a Cellular Radio Network.” IEEE Transactions on Vehicular Tech
`nology, vol. 46, No. 1, Feb. 1997.
`"Huffman Coding”, Wikipedia, retrieved from http://en.wikipedia.
`org/wiki/Huffman coding, 2006.
`Kim, M., et al., “Risks of using AP locations discovered through war
`driving.” Lecture Notes in Computer Science, vol. 3968, 2006.
`Krumm, J., et al., "LOCADIO: Inferring Motion and Location from
`Wi-Fi Signal Strengths.” First Annual International Conference on
`Mobile and Ubiquitous Systems: Networking and Services, Aug.
`2004.
`LaMarca, A., et al., “Place Lab: Device Positioning Using Radio
`Beacons in the Wild.” Intel Corporation, 2004.
`“Terminal Equipment and Protocols for Telematic Services: Infor
`mation Technology Digital Compression and Coding of Continu
`ous-Tome Still Images—Requirements and Guidelines. Interna
`tional Telecommunication Union, Sep. 1992.
`Muthukrishnan, K., et al., “Towards Smart Surroundings: Enabling
`Techniques and Technologies for Localization.” Lecture Notes in
`Computer Science, vol. 3479, May 2005.
`Kwan, M., “Graphic Programming Using Odd or Even Points.” Chi
`nese Math. 1, 1962.
`Kirsner, S., “One more way to find yourself.” The Boston Globe, May
`23, 2005, Retrieved from www.boston.com.
`Kawabata, K., “Estimating Velocity. Using Diversity Reception.”
`IEEE, 1994.
`Hazas, M., et al., “Location-Aware Computing Comes of Age.”
`IEEE, vol. 37, Feb. 2004.
`Griswold et al., “ActiveCampus—Sustaining Educational Commu
`nities through Mobile Technology.” UCSD CSE Technical Report
`#CS200-0714, 2002.
`"Delta Encoding”, Wikipedia, retrieved from http://en.wikipedia.
`org/wiki/Delta encoding, 2006.
`* cited by examiner
`
`Page 2 of 14
`
`

`

`U.S. Patent
`
`Jan. 6, 2009
`
`Sheet 1 of 6
`
`US 7474,897 B2
`
`
`
`II '708
`
`
`
`quyod ssºpoe
`
`ZOI
`
`II "Z08
`
`ZOI
`
`I I “ZO8
`
`Page 3 of 14
`
`

`

`U.S. Patent
`
`Jan. 6, 2009
`
`Sheet 2 of 6
`
`US 7474,897 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`uouebo,T
`
`Z 9.InãIH
`
`Page 4 of 14
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jan. 6, 2009
`
`Sheet 3 of 6
`
`US 7474,897 B2
`US 7,474,897 B2
`
`GOZ
`SOc
`
`aseqejeq
`
`
`jusuoduiogasueyoxgeveq
`
`coe
`
`aseqejeq
`
`LOTJONArend
`
`
`
`807UOTIE[NI[e
`
`aUdIaJOY
`
`dv[2907<a
`LOZ1018907]
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`[9poyyOLIUAZDdoTAACT
`
`By
`o
`.
`o
`
`
`
`s]UIOgssa00y
`
`col
`
`yy!
`
`
`
`ZOTZJouURDS
`
`Page 5 of 14
`
`
`
`sajl4yOeqpee4
`
`Z1Z
`
`€UNSWOH]SdAK
`
`
`
`
`(COT)SdtAeq]Wordperqeug
`
`Page 5 of 14
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 6, 2009
`
`Sheet 4 of 6
`
`US 7,474,897 B2
`
`
`
`
`
`J2POyA]OENUADyOMION
`
`
`
`
`
`
`
`TOPSSOVJIDIUTYIOMIONOUIT)-[BIy
`
`dduUaIaJayY
`
`eseqejyeqd
`
`SO¢
`
`
`
`ByeqYorqpee,j
`
`pons]
`
`uoneso’ySd
`
`
`
`(€OL)eolAaqyWal][Dpelqeugq
`
`
`
`
`
`viefy
`ssa00yvy!
`sJUIOg
`
`ZOZ1suuLIS
`
`10Z1038907]
`
`
`
`LOZoutArtpengd
`
`ZN
`
`cOT
`
`COESdVMON
`
`Page 6 of 14
`
`Page 6 of 14
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 6, 2009
`
`Sheet 5 of 6
`
`US 7,474,897 B2
`
`
`
`poredulossqypearasqgQ<<SSS
`¢ons
` yoOs
`
`€0Ss]ulogsseo0ypuno4AON
`
`
`
`
`
`
`
`poppesjutodssacoeMON
`
`oseqeiep0}
`
`
`
`
`
`aseqriepSUIvSE
`
`poloy[yBlepped
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SMO]BIECUOTeNTeAgJUIOgssad0y
`
`
`
`09:68-PO-€6-11-00)
`
`OsePOSTOOF
`§k9C:90:F:90-00)
`
`
`
`
`G8-PO-E6:11-00
`
`
`
`99:72:98:S7:90:00,
`
`62)99:€P88:5¢'90-00)
`
`G72316-1100,
`
`€7:9e-vE-96:0F-00,
`
`
`
`99°97:LE'96-0¥:00,
`
`Page 7 of 14
`
`Page 7 of 14
`
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jan. 6, 2009
`Jan. 6, 2009
`
`Sheet 6 of 6
`Sheet 6 of 6
`
`
`109\\%%
`
`Jos—)\\\4UOTTeD0[poyengyeo+,4\sola
`
`
`
`
`
`
`
`Page 8 of 14
`
`Ta,
`
`US 7474,897 B2
`US 7,474,897 B2
`
`
`
`
`
`
`ThunpremjnospurdxaaZ09sjutogsso00y—09PloysamyL,xe,
`€09Joyoandepya
`
`
`
`
`
`popseuwinurturuyoadsnsse
`
`
`
`
`oY)spadoxeasjutodeaTSpoyYeUloea8uvIsIy}
`
`
`
`
`
`”™.aptsinosyutodssasoySS9008JOaQquINUat}a~.,
`
`QsINSLJ
`
`Page 8 of 14
`
`
`

`

`1.
`CONTINUOUS DATA OPTIMIZATION BY
`FILTERING AND POSITONING SYSTEMS
`
`US 7,474,897 B2
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application claims the benefit under 35 U.S.C. S 119
`(e) to the following Provisional Patent Application, the con
`tents of which are incorporated herein in its entirety by ref
`CCC.
`U.S. Provisional Patent Application No. 60/654,811, filed
`on Feb. 22, 2005, entitled Continuous Data Optimization in
`Positioning System.
`This application is a continuation-in-part of and claims the
`benefit under 35 U.S.C. S 120 to the following application, the
`contents of which are incorporated herein in its entirety by
`reference:
`U.S. patent application Ser. No. 1 1/261.988, filed on Oct.
`28, 2005, entitled Location-Based Services that Choose
`Location Algorithms Based on Number of Detected Access
`Points Within Range of User Device.
`This application is related to the following U.S. patent
`applications, filed on an even date herewith, entitled as fol
`lows:
`U.S. patent application Ser. No. 1 1/359,154 Continuous
`Data Optimization of Moved Access Points. In Positioning
`System; and
`U.S. patent application Ser. No. 1 1/359,144 Continuous
`Data Optimization of New Access Points in Positioning Sys
`temS.
`This application is related to the following U.S. Patent
`Applications filed on Oct. 28, 2005, entitled as follows:
`U.S. patent application Ser. No. 1 1/261,848, Filed on Oct.
`28, 2005, entitled Location Beacon Database;
`U.S. patent application Ser. No. 1 1/261,898, Filed on Oct.
`28, 2005, entitled Server for Updating Location Beacon Data
`base; and
`U.S. patent application Ser. No. 1 1/261,987, Filed on Oct.
`28, 2005, entitled Method and System for Building a Loca
`tion Beacon Database.
`This application is related to U.S. Provisional Patent Appli
`cation No. 60/658,481, filed on Mar. 4, 2005, entitled Encod
`ing and Compressing the Access Point Database.
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`BACKGROUND
`
`1. Field of the Invention
`The invention is generally related to location-based ser
`vices and, more specifically, to methods of continuously opti
`mizing or improving the quality of WiFi location data in Such
`systems.
`2. Discussion of Related Art
`In recent years the number of mobile computing devices
`has increased dramatically creating the need for more
`advanced mobile and wireless services. Mobile email,
`walkie-talkie services, multi-player gaming and call follow
`ing are examples of how new applications are emerging on
`mobile devices. In addition, users are beginning to demand/
`seek applications that not only utilize their current location
`but also share that location information with others. Parents
`wish to keep track of their children, supervisors need to track
`the location of the company’s delivery vehicles, and a busi
`ness traveler looks to find the nearest pharmacy to pick up a
`prescription. All of these examples require the individual to
`know their own current location or that of someone else. To
`date, we all rely on asking for directions, calling someone to
`ask their whereabouts or having workers check-in from time
`to time with their position.
`Location-based services are an emerging area of mobile
`applications that leverages the ability of new devices to cal
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`culate their current geographic position and report that to a
`user or to a service. Some examples of these services include
`local weather, traffic updates, driving directions, child track
`ers, buddy finders and urban concierge services. These new
`location sensitive devices rely on a variety of technologies
`that all use the same general concept. Using radio signals
`coming from known reference points, these devices can math
`ematically calculate the user's position relative to these ref
`erence points. Each of these approaches has its strengths and
`weaknesses based on the radio technology and the position
`ing algorithms they employ.
`The Global Positioning System (GPS) operated by the US
`Government leverages dozens of orbiting satellites as refer
`ence points. These satellites broadcast radio signals that are
`picked up by GPS receivers. The receivers measure the time it
`took for that signal to reach to the receiver. After receiving
`signals from three or more GPS satellites the receiver can
`triangulate its position on the globe. For the system to work
`effectively, the radio signals must reach the received with
`little or no interference. Weather, buildings or structures and
`foliage can cause interference because the receivers require a
`clear line-of-sight to three or more satellites. Interference can
`also be caused by a phenomenon known as multi-path. The
`radio signals from the satellites bounce off physical structures
`causing multiple signals from the same satellite to reach a
`receiver at different times. Since the receiver's calculation is
`based on the time the signal took to reach the receiver, multi
`path signals confuse the receiver and cause Substantial errors.
`Cell tower triangulation is another method used by wireless
`and cellular carriers to determine a user or device's location.
`The wireless network and the handheld device communicate
`with each other to share signal information that the network
`can use to calculate the location of the device. This approach
`was originally seen as a Superior model to GPS since these
`signals do not require direct line of site and can penetrate
`buildings better. Unfortunately these approaches have proven
`to be suboptimal due to the heterogeneous nature of the cel
`lular tower hardware along with the issues of multi-path sig
`nals and the lack of uniformity in the positioning of cellular
`tOWerS.
`Assisted GPS is a newer model that combines both GPS
`and cellular tower techniques to produce a more accurate and
`reliable location calculation for mobile users. In this model,
`the wireless network attempts to help GPS improve its signal
`reception by transmitting information about the clock offsets
`of the GPS satellites and the general location of the user based
`on the location of the connected cell tower. These techniques
`can help GPS receivers deal with weaker signals that one
`experiences indoors and helps the receiver obtain a fix' on the
`closest satellites quicker providing a faster “first reading.
`These systems have been plagued by slow response times and
`poor accuracy—greater than 100 meters in downtown areas.
`There have been some more recent alternative models
`developed to try and address the known issues with GPS,
`A-GPS and cell tower positioning. One of them, known as
`TV-GPS, utilizes signals from television broadcast towers.
`(See, e.g., Muthukrishnan, Maria Lijding, Paul Havinga,
`Towards Smart Surroundings: Enabling Techniques and
`Technologies for Localization, Lecture Notes in Computer
`Science, Volume 3479, Jan 2Hazas, M., Scott, J., Krumm, J.:
`Location-Aware Computing Comes of Age. IEEE Computer,
`37(2):95-97, February 2004 005, Pa()05, Pages 350-362.) The
`concept relies on the fact that most metropolitan areas have 3
`or more TV broadcast towers. A proprietary hardware chip
`receives TV signals from these various towers and uses the
`known positions of these towers as reference points. The
`challenges facing this model are the cost of the new hardware
`receiver and the limitations of using Such a small set of
`reference points. For example, if a user is outside the perim
`eter of towers, the system has a difficult time providing rea
`
`Page 9 of 14
`
`

`

`US 7,474,897 B2
`
`5
`
`35
`
`55
`
`60
`
`3
`sonable accuracy. The classic example is a user along the
`shoreline. Since there are no TV towers out in the ocean, there
`is no way to provide reference symmetry among the reference
`points resulting in a calculated positioning well inland of the
`USC.
`Microsoft Corporation and Intel Corporation (via a
`research group known as PlaceLab) have deployed a Wi-Fi
`Location system using the access point locations acquired
`from amateur scanners (known as “wardrivers’) who submit
`their Wi-Fi scan data to public community web sites. (See, 10
`e.g., LaMarca, A., et. al., Place Lab: Device Positioning
`Using Radio Beacons in the Wild.) Examples include
`WiGLE, Wi-FiMaps.com, Netstumbler.com and NodeIDB.
`Both Microsoft and Intel have developed their own client
`software that utilizes this public wardriving data as reference 15
`locations. Because individuals Voluntarily Supply the data the
`systems suffer a number of performance and reliability prob
`lems. First, the data across the databases are not contempo
`raneous; some of the data is new while other portions are 3-4
`years old. The age of the access point location is important 20
`since over time access points can be moved or taken offline.
`Second, the data is acquired using a variety of hardware and
`software configurations. Every 802.11 radio and antenna has
`different signal reception characteristics affecting the repre
`sentation of the strength of the signal. Each scanning Software 25
`implementation scans for Wi-Fi signals in different ways
`during different time intervals. Third, the user-supplied data
`suffers from arterial bias. Because the data is self-reported by
`individuals who are not following designed scanning routes,
`the data tends to aggregate around heavily traffic areas. Arte- so
`rial bias causes a resulting location pull towards main arteries
`regardless of where the user is currently located causing
`Substantial accuracy errors. Fourth, these databases include
`the calculated position of scanned access points rather than
`the raw scanning data obtained by the 802.11 hardware. Each
`of these databases calculates the access point location differ
`ently and each with a rudimentary weighted average formula.
`The result is that many access points are indicated as being
`located far from their actual locations including some access
`points being incorrectly indicated as if they were located in
`40
`bodies of water.
`There have been a number of commercial offerings of
`Wi-Fi location systems targeted at indoor positioning. (See,
`e.g., Kavitha Muthukrishnan, Maria Lijding, Paul Havinga,
`Towards Smart Surroundings: Enabling Techniques and
`Technologies for Localization, Lecture Notes in Computer 45
`Science, Volume 3479, Jan 2Hazas, M., Scott, J., Krumm, J.:
`Location-Aware Computing Comes of Age. IEEE Computer,
`37(2): 95-97, February 2004 005, Pa005, Pages 350-362.)
`These systems are designed to address asset and people track
`ing within a controlled environment like a corporate campus, 50
`a hospital facility or a shipping yard. The classic example is
`having a system that can monitor the exact location of the
`crash cart within the hospital so that when there is a cardiac
`arrest the hospital staff doesn’t waste time locating the device.
`The accuracy requirements for these use cases are very
`demanding typically calling for 1-3 meter accuracy. These
`systems use a variety of techniques to fine tune their accuracy
`including conducting detailed site Surveys of every square
`foot of the campus to measure radio signal propagation. They
`also require a constant network connection so that the access
`point and the client radio can exchange synchronization infor
`mation similar to how A-GPS works. While these systems are
`becoming more reliable for these indoor use cases, they are
`ineffective in any wide-area deployment. It is impossible to
`conduct the kind of detailed site Survey required across an
`entire city and there is no way to rely on a constant commu- 65
`nication channel with 802.11 access points across an entire
`metropolitan area to the extent required by these systems.
`
`4
`Most importantly outdoor radio propagation is fundamentally
`different than indoor radio propagation rendering these
`indoor positioning algorithms almost useless in a wide-area
`scenario.
`There are numerous 802.11 location scanning clients avail
`able that record the presence of 802.11 signals along with a
`GPS location reading. These software applications are oper
`ated manually and produce a log file of the readings.
`Examples of these applications are Netstumber, Kismet and
`Wi-FiFoFum. Some hobbyists use these applications to mark
`the locations of 802.11 access point signals they detect and
`share them with each other. The management of this data and
`the sharing of the information is all done manually. These
`application do not perform any calculation as to the physical
`location of the access point, they merely mark the location
`from which the access point was detected.
`Performance and reliability of the underlying positioning
`system are the key drivers to the Successful deployment of any
`location based service. Performance refers to the accuracy
`levels that the system achieves for that given use case. Reli
`ability refers to the percentage of time that the desired per
`formance levels are achieved.
`
`Local Search/Advertising
`E911
`Turn-by-turn driving directions
`Gaming
`Friend finders
`Fleet management
`Indoor asset tracking
`
`Performance
`
`Reliability
`
`<100 meters 85% of the time
`<150 meters 95% of the time
`10-20 meters 95% of the time
`<50 meters 90% of the time
`<500 meters 80% of the time
`<10 meters 95% of the time
`<3 meters 95% of the time
`
`SUMMARY
`
`The invention provides methods and systems of continu
`ously optimizing data in WiFi positioning systems. For
`example, data is monitored to infer whether a WiFi access
`point has moved or is new. In this fashion, data is continu
`ously optimized. Likewise, Suspect data may be avoided
`when determining the position of the WiFi-enabled device
`using such a system.
`Under one aspect of the invention, a location-based ser
`vices system for WiFi-enabled devices calculates the position
`of WiFi-enabled devices. A WiFi-enabled device communi
`cates with WiFi access points within range of the WiFi-en
`abled device so that observed WiFi access points identify
`themselves. A reference database is accessed to obtain infor
`mation specifying a recorded location for each observed WiFi
`access point. The recorded location information for each of
`the observed WiFi access points is used in conjunction with
`predefined rules to determine whether an observed WiFi
`access point should be included or excluded from a set of
`WiFi access points. The recorded location information of
`only the WiFi access points included in the set are used and
`the recorded location information of the excluded WiFi
`access points are excluded when calculating the geographical
`position of the WiFi-enabled device.
`Under another aspect of the invention, signal strength
`information for WiFi access points included in the set is
`recorded and the signal strength information is used when
`calculating the geographical position of the WiFi-enabled
`device.
`Under another aspect of the invention, the predefined rules
`include rules to determine a reference point and to compare
`the recorded location information for each of the observed
`WiFi access points to the reference point, and wherein WiFi
`access points having a recorded location within a predefined
`
`Page 10 of 14
`
`

`

`US 7,474,897 B2
`
`5
`threshold distance of the reference point are included in the
`set and wherein WiFi access points having a recorded location
`in excess of the predefined threshold distance of the reference
`point are excluded from the set.
`Under another aspect of the invention, the reference point
`is determined by identifying a cluster of WiFi access points
`and determining an average position of the WiFi access points
`in the cluster.
`
`10
`
`15
`
`BRIEF DESCRIPTION OF DRAWINGS
`
`In the drawing,
`FIG. 1 depicts certain embodiments of a Wi-Fi positioning
`system;
`FIG. 2 depicts an exemplary architecture of positioning
`Software according to certain embodiments of the invention;
`FIG. 3 depicts the data transfer process in certain client
`device centric embodiments;
`FIG. 4 depicts the data transfer process in certain network
`centric embodiments;
`FIG. 5 depicts the data flows for the quality filtering and
`feedback process; and
`FIG. 6 depicts the operation of the Adaptive Filter in certain
`embodiments.
`
`DETAILED DESCRIPTION
`
`25
`
`6
`the current access point locations in the Access Point Refer
`ence Database by comparing the observed readings against
`the recorded readings in the database. If the client determines
`that the observed readings fall outside the bounds of what
`should be expected based on the recorded readings, then the
`access point is marked as Suspect. That Suspect reading is
`logged into a feedback system for reporting back to the cen
`tral location Access Point Reference Database.
`Under another embodiment of the invention, a WPS client
`device filters identified suspect access points out of the trian
`gulation calculation of the WPS client device in real time so as
`not to introduce bad data into the location calculation.
`Under another embodiment of the invention, a WPS client
`device scans for access points to determine the physical loca
`tion of the device and identifies access points that do not exist
`in the current Access Point Reference Database. After the
`known access points are used to calculate the device's current
`location, those newly found access points are recorded back
`to the central location Access Point Reference Database using
`the calculated location of the known access points to help
`determine their position, along with the observed power read
`1ng.
`Under another embodiment of the invention, a device cen
`tric WPS client device periodically connects to the central
`location Access Point Reference Database to download the
`latest access point data. The WPS client device also uploads
`all feedback data about newly observed access points and
`Suspect access points. This data is then fed into the central
`location Access Point Reference Database processing to reca
`librate the overall system.
`Under another embodiment of the invention, a network
`centric WPS client device directly records feedback data
`about newly observed access points and suspect access points
`into the central location Access Point Reference Database in
`real time.
`By enlisting the WPS client device to continuously update
`the Access Point Reference Database with information on
`new and Suspect access points, the WiFi positioning system
`provides higher quality data than a system scanned solely by
`the provider. Over time, WiFi access points are continually
`added and moved. Embodiments of the described invention
`provide systems and methods to ensure that the Access Point
`Reference Database is self-healing and self-expanding, pro
`viding optimal positioning data that continually reflects addi
`tions and changes to available access points. As more user
`client devices are deployed, the quality of the Access Point
`Reference Database improves because information in the
`database is updated more frequently.
`FIG. 1 depicts a portion of a preferred embodiment of a
`Wi-Fi positioning system (WPS). The positioning system
`includes positioning software 103 that resides on a user
`computing device 101. Throughout a particular coverage
`area there are fixed wireless access points 102 that broadcast
`information using control/common channel broadcast sig
`nals. The client device monitors the broadcast signal or
`requests its transmission via a probe request. Each access
`point contains a unique hardware identifier known as a MAC
`address. The client positioning software receives signal bea
`cons or probe responses from the 802.11 access points in
`range and calculates the geographic location of the comput
`ing device using characteristics from the received signal bea
`cons or probe responses.
`The positioning software is described in greater detail with
`reference to FIG. 2, which depicts exemplary components of
`positioning software 103. Typically, in the user device
`embodiment of FIG. 1 there is an application or service 201
`that utilizes location readings to provide some value to an end
`user (for example, driving directions). This location applica
`tion makes a request of the positioning Software for the loca
`tion of the device at that particular moment. The location
`
`Preferred embodiments of the present invention provide a
`system and a methodology for continuously maintaining and
`updating location data in a WiFi positioning system (WPS)
`using public and private 802.11 access points. Preferably,
`clients using location data gathered by the system use tech
`niques to avoid erroneous data in determining the Wi-Fi posi
`tions and use newly-discovered position information to
`improve the quality of previously gathered and determined
`position information. Certain embodiments communicate
`with the central location Access Point Reference Database to
`provide the location of newly discovered access points. Other
`embodiments notify the central location Access Point Refer
`ence Database of access points whose readings fall outside
`the bounds of what should be expected, based on previous
`readings of their location. Access points whose readings fall
`outside of what should be expected can be marked as Suspect
`and filtered out of the triangulation formula so as not to
`introduce bad data into the location calculation.
`Preferred embodiments of the invention build on tech
`niques, systems and methods disclosed in earlier filed appli
`cations, including but not limited to U.S. patent application
`Ser. No. 1 1/261,988, filed on Oct. 28, 2005, entitled Location
`Based Services that Choose Location Algorithms Based on
`Number of Detected Access Points Within Range of User
`Device, the contents of which are hereby incorporated by
`reference in its entirety. Those applications taught specific
`ways to gather high quality location data for WiFi access
`points so that such data may be used in location based services
`to determine the geographic position of a WiFi-enabled
`device utilizing such services. In the present case, new tech
`niques are disclosed for continuously monitoring and
`improving such data, for example by users detecting new
`access points in a target area or inferring that access points
`have moved. The present techniques, however, are not limited
`to systems and methods disclosed in the incorporated patent
`applications. Instead those applications disclose but one
`framework or context in which the present techniques may be
`implemented. Thus, while reference to Such systems and
`applications may be helpful, it is not believed necessary to
`understand the present embodiments or inventions.
`Under one embodiment of the invention, a WPS client
`device scans for access points to determine the physical loca
`tion of the WPS client device, then it calculates the quality of
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Page 11 of 14
`
`

`

`7
`application can be initiated continuously every elapsed period
`of time (every 1 second for example) or one time on demand
`by another application or