(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2006/0095349 A1
`Morgan et al.
`(43) Pub. Date:
`May 4, 2006
`
`US 20060095349A1
`
`(54) METHOD AND SYSTEM FOR BUILDING A
`LOCATION BEACON DATABASE
`
`(75) Inventors: Edward J. Morgan, Needham, MA
`(US); Farshid Alizadeh-Shabdiz,
`Wayland, MA (US); Russel K. Jones,
`Roswell, GA (US); Michael G. Shean,
`Boston, MA (US)
`Correspondence Address:
`WILMER CUTLER PICKERING HALE AND
`DORR LLP
`6O STATE STREET
`BOSTON, MA 02109 (US)
`(73) Assignee: Skyhook Wireless, Inc.
`
`(21) Appl. No.:
`
`11/261,987
`
`(22) Filed:
`
`Oct. 28, 2005
`Related U.S. Application Data
`(60) Provisional application No. 60/623,108, filed on Oct.
`29, 2004.
`
`Publication Classification
`
`(51) Int. Cl.
`(2006.01)
`AIK 5/02
`(52) U.S. Cl. ............................. 705/29: 370/352; 701/300
`(57)
`ABSTRACT
`A location beacon database and server, method of building
`location beacon database, and location based service using
`same. Wi-Fi access points are located in a target geographi
`cal area to build a reference database of locations of Wi-Fi
`access points. At least one vehicle is deployed including at
`least one scanning device having a GPS device and a Wi-Fi
`radio device and including a Wi-Fi antenna system. The
`
`target area is traversed in a programmatic route to avoid
`arterial bias. The programmatic route includes Substantially
`all drivable streets in the target geographical area and solves
`an Eulerian cycle problem of a graph represented by said
`drivable streets. While traversing the target area, periodi
`cally receive the GPS coordinates of the GPS device. While
`traversing the target area, detecting Wi-Fi signals from
`Wi-Fi access points in range of the Wi-Fi device and
`recording identity information of the detected Wi-Fi access
`point in conjunction with GPS location information of the
`vehicle when the detection of the Wi-Fi access point was
`made. The location information is used to reverse triangulate
`the position of the detected Wi-Fi access point; and the
`position of the detected access point is recorded in a refer
`ence database. A user-device having a Wi-Fi radio may be
`located. A reference database of calculated locations of
`Wi-Fi access points in a target area is provided. In response
`to a user application request to determine a location of a
`user-device having a Wi-Fi radio, the Wi-Fi device is
`triggered to transmit a request to all Wi-Fi access points
`within range of the Wi-Fi device. Messages are received
`from the Wi-Fi access points within range of the Wi-Fi
`device, each message identifying the Wi-Fi access point
`sending the message. The signal strength of the messages
`received by the Wi-Fi access points is calculated. The
`reference database is accessed to obtain the calculated
`locations for the identified Wi-Fi access points. Based on the
`number of Wi-Fi access points identified via received mes
`sages, choosing a corresponding location-determination
`algorithm from a plurality of location-determination algo
`rithms, said chosen algorithm being Suited for the number of
`identified Wi-Fi access points. The calculated locations for
`the identified Wi-Fi access points and the signal strengths of
`said received messages and the chosen location-determina
`tion algorithm are used to determine the location of the
`user-device. The database may be modified with newly
`added position information to improve quality of previously
`determined positions, and error prone information is
`avoided.
`
`
`
`
`
`GPS satellite
`
`GPS satellite
`
`PS satellite
`204
`
`
`
`
`
`802.11
`access point
`203
`
`802.11
`access point
`203
`
`Directional
`Atelias
`
`Scanning Device
`202
`Scanning Vehicle
`201
`
`
`
`
`
`
`
`Page 1 of 20
`
`SAMSUNG EX-1066
`
`

`

`Patent Application Publication May 4, 2006 Sheet 1 of 11
`
`US 2006/0095349 A1
`
`
`
`I 9 InãIH
`
`Page 2 of 20
`
`

`

`Patent Application Publication May 4, 2006 Sheet 2 of 11
`
`US 2006/0095349 A1
`
`
`
`
`
`
`
`
`
`
`
`
`
`Z 9.InãIA
`
`Page 3 of 20
`
`

`

`Patent Application Publication May 4, 2006 Sheet 3 of 11
`
`US 2006/0095349 A1
`
`
`
`
`
`
`
`
`
`OITZ08
`
`
`
`109 199J1S
`
`Page 4 of 20
`
`

`

`Patent Application Publication
`
`May 4, 2006 Sheet 4 of 11
`
`US 2006/0095349 A1
`
`
`
`
`
`
`
`
`
`OOf7
`
`
`quod ssobov -
`Co tº •)
`
`I I "Z08
`
`Page 5 of 20
`
`

`

`Patent Application Publication May 4,2006 Sheet 5 of 11
`
`US 2006/0095349 A1
`
`
`
`adurso1pey
`
`JasnJo
`
` Qo1Aop
`
`
`KnautuksJOUdIOJOYJOYoe’y]:¢aNSLy
`
`
`
`Burpyingjeoiskyq
`
`
`
`s}o0.gOI1Qnd
`
`ZOS
`
`parepnajeg
`
`Jouones07]
`
`Josn
`
`£0S
`
`
`
`sjulogssa00y
`
`payepnaeg
`
`jou0nes0}
`
`Page 6 of 20
`
`Page 6 of 20
`
`

`

`Patent Application Publication May 4, 2006 Sheet 6 of 11
`
`US 2006/0095349 A1
`
`
`
`
`
`Page 7 of 20
`
`

`

`Patent Application Publication
`
`May 4, 2006 Sheet 7 of 11
`
`US 2006/0095349 A1
`
`s
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`-
`
`Page 8 of 20
`
`

`

`Patent Application Publication May 4, 2006 Sheet 8 of 11
`
`US 2006/0095349 A1
`
`
`
`
`
`
`
`
`
`JQAJ9S XIONA19N [e]]u3O:3 QJnãIH
`
`
`
`
`
`808
`
`S08
`
`Page 9 of 20
`
`

`

`Patent Application Publication
`
`May 4, 2006 Sheet 9 of 11
`
`US 2006/0095349 A1
`
`
`
`606806L06
`
`uoueooT
`
`906
`
`OVW dn XooT
`
`sassouppe
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`•••••••••••••••••••••••••••••• -----------* ****************************************************>>>••••••••
`
`Page 10 of 20
`
`

`

`Patent Application Publication
`
`US 2006/0095349 A1
`
`
`
`Sd5)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 11 of 20
`
`

`

`Patent Application Publication May 4, 2006 Sheet 11 of 11
`
`US 2006/0095349 A1
`
`
`
`X
`
`X
`
`Page 12 of 20
`
`

`

`US 2006/0095349 A1
`
`May 4, 2006
`
`METHOD AND SYSTEM FOR BUILDING A
`LOCATION BEACON DATABASE
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`0001) This application claims the benefit under 35 U.S.C.
`S119(e) of U.S. Provisional Patent Application No. 60/623,
`108, filed on Oct. 29, 2004, entitled Wireless Data Scanning
`Network for Building Location Beacon Database, which is
`herein incorporated by reference in its entirety.
`0002 This application is related to the following U.S.
`Patent Applications (Nos. TBA), filed on an even date
`herewith, entitled as follows:
`0003 Location Beacon Database;
`0004 Server for Updating Location Beacon Database:
`and
`0005 Location-Based Services that Choose Location
`Algorithms Based on Number of Detected Access Points
`Within Range of User Device.
`
`BACKGROUND
`
`0006)
`1. Field of the Invention
`0007. The invention generally related to location-base
`services and, more specifically, to methods and systems of
`determining locations of Wi-Fi access points and using Such
`information to locate a Wi-Fi-enabled device.
`0008 2. Discussion of Related Art
`0009. 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
`business traveler looks to find the nearest pharmacy to pick
`up a prescription. All of these examples require the indi
`vidual 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.
`0010 Location-based services are an emerging area of
`mobile applications that leverages the ability of new devices
`to calculate 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 trackers, 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 mathematically calculate the user's position
`relative to these reference points. Each of these approaches
`has its strengths and weaknesses based on the radio tech
`nology and the positioning algorithms they employ.
`0011. The Global Positioning System (GPS) operated by
`the US Government leverages dozens of orbiting satellites as
`reference 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.
`0012 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 cellular tower hardware along
`with the issues of multi-path signals and the lack of unifor
`mity in the positioning of cellular towers.
`0013 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.
`0014. 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 Hav
`inga, Towards Smart Surroundings: Enabling Techniques
`and Technologies for Localization, Lecture Notes in Com
`puter 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, Pap005,
`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 perimeter of towers, the system has a
`difficult time providing reasonable 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 calcu
`lated positioning well inland of the user.
`
`Page 13 of 20
`
`

`

`US 2006/0095349 A1
`
`May 4, 2006
`
`Microsoft Corporation and Intel Corporation (via a
`0.015
`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,
`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
`locations. Because individuals Voluntarily Supply the data
`the systems suffer a number of performance and reliability
`problems. First, the data across the databases are not con
`temporaneous; some of the data is new while other portions
`are 34 years old. The age of the access point location is
`important 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 representation of the strength of the signal.
`Each scanning software 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 aggre
`gate around heavily traffic areas. Arterial 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 calcu
`lated 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 for
`mula. 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 bodies of water.
`0016. 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 Tech
`niques 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.) These systems are designed to address asset
`and people tracking within a controlled environment like a
`corporate campus, 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 information 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 communication channel
`
`with 802.11 access points across an entire metropolitan area
`to the extent required by these systems. Most importantly
`outdoor radio propagation is fundamentally different than
`indoor radio propagation rendering these indoor positioning
`algorithms almost useless in a wide-area Scenario.
`0017. There are numerous 802.11 location scanning cli
`ents available that record the presence of 802.11 signals
`along with a GPS location reading. These software applica
`tions are operated manually and produce a log file of the
`readings. Examples of these applications are Netstumber,
`Kismet and Wi-FiFoFum. Some hobbyists use these appli
`cations 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.
`0018 Performance and reliability of the underlying posi
`tioning system are the key drivers to the Successful deploy
`ment of any location based service. Performance refers to
`the accuracy levels that the system achieves for that given
`use case. Reliability refers to the percentage of time that the
`desired performance 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
`0019. The invention provides a location beacon database
`and server, method of building location beacon database,
`and location based service using same.
`0020 Under one aspect of the invention, Wi-Fi access
`points are located in a target geographical area to build a
`reference database of locations of Wi-Fi access points. At
`least one vehicle is deployed including at least one scanning
`device having a GPS device and a Wi-Fi radio device and
`including a Wi-Fi antenna system. The target area is tra
`versed in a programmatic route to avoid arterial bias. The
`programmatic route includes Substantially all drivable
`streets in the target geographical area and solves an Eulerian
`cycle problem of a graph represented by said drivable
`streets. While traversing the target area, periodically receive
`the GPS coordinates of the GPS device. While traversing the
`target area, detecting Wi-Fi signals from Wi-Fi access points
`in range of the Wi-Fi device and recording identity infor
`mation of the detected Wi-Fi access point in conjunction
`with GPS location information of the vehicle when the
`detection of the Wi-Fi access point was made. The location
`information is used to reverse triangulate the position of the
`detected Wi-Fi access point; and the position of the detected
`access point is recorded in a reference database.
`0021. Under another aspect of the invention, the target
`geographic area has a radius on the order of tens of miles.
`
`Page 14 of 20
`
`

`

`US 2006/0095349 A1
`
`May 4, 2006
`
`0022. Under another aspect of the invention, the pro
`grammatic route is determined by using the Chinese post
`man routing algorithm.
`0023. Under another aspect of the invention, when
`detecting Wi-Fi signals, several readings of Wi-Fi signals are
`made for a given Wi-Fi access point so that a set of readings
`is formed for the given Wi-Fi access point and wherein said
`set of readings is used when determining the position of the
`detected Wi-Fi access point.
`0024 Under another aspect of the invention, when
`detecting a Wi-Fi access point signal strength information
`about the signal from the Wi-Fi access point is calculated
`and recorded by the scanning device.
`0.025 Under another aspect of the invention, a given
`Wi-Fi access point is detected from as many different angles
`as possible given the organization of the drivable streets.
`0026. Under another aspect of the invention, a given
`Wi-Fi access point is detected from as many different angles
`as possible given the organization of the drivable streets, and
`wherein a power profile of signal strengths for a given Wi-Fi
`access point is determined and recorded.
`0027. Under another aspect of the invention, the Wi-Fi
`antenna system includes directional antennas and wherein
`the scanning device records a vector of origin of a Wi-Fi
`access point based on different signal strengths received by
`the Wi-Fi access point on the directional antennas.
`0028 Under another aspect of the invention, access
`points are located for a plurality of target areas.
`
`BRIEF DESCRIPTION OF DRAWINGS
`In the drawing,
`0029)
`0030 FIG. 1 depicts certain embodiments of a Wi-Fi
`positioning system;
`0031
`FIG. 2 depicts scanning vehicles including scan
`ning devices according to certain embodiments of the inven
`tion;
`0032 FIG. 3 depicts an example of a scanning scenario
`to illustrate the problem of arterial bias in data collection;
`0033 FIG. 4 depicts an example using a programmatic
`route for a scanning vehicle according to certain embodi
`ments of the invention;
`0034 FIG. 5 depicts an example scenario to illustrate the
`problem of lack of reference symmetry of Wi-Fi access
`points in locating a user device;
`0035 FIG. 6 depicts an example scenario to illustrate
`reference symmetry of Wi-Fi access points in locating a user
`device;
`FIG. 7 depicts scanning vehicles including scan
`0.036
`ning devices according to certain embodiments of the inven
`tion;
`0037 FIG. 8 depicts a central network server including
`a central database of Wi-Fi access points according to
`certain embodiments of the invention;
`0038 FIG. 9 depicts an exemplary architecture of posi
`tioning software according to certain embodiments of the
`invention;
`
`FIG. 10 depicts an exemplary architecture of a
`0.039
`scanning client according to certain embodiments of the
`invention; and
`0040 FIG. 11 compares and contrasts the effects of a
`random scanning model with one using a model from the
`Chinese postman routing algorithm.
`
`DETAILED DESCRIPTION
`0041) Preferred embodiments of the present invention
`provide a system and a methodology for gathering reference
`location data to enable a commercial positioning system
`using public and private 802.11 access points. Preferably, the
`data is gathered in a programmatic way to fully explore and
`cover the Streets of a target region. The programmatic
`approach identifies as many Wi-Fi access points as possible.
`By gathering location information about more access points,
`preferred embodiments not only provide a larger collection
`of location information about access points, but the location
`information for each access point may be calculated with
`more precision. Subsequently this larger set of more precise
`data may be used by location services to more precisely
`locate a user device utilizing preferred embodiments of the
`invention. Certain embodiments use techniques to avoid
`erroneous data in determining the Wi-Fi positions and use
`newly-discovered position information to improve the qual
`ity of previously gathered and determined position informa
`tion. Certain embodiments use location-determination algo
`rithms based on the context of the user device at the time the
`user requests a location. For example, the location-determi
`nation algorithm will be based on the number of Wi-Fi
`access points identified or detected when a location request
`is made, or based on the application making the request.
`0042 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
`computing device 101). Throughout a particular coverage
`area there are fixed wireless access points 102 that broad
`cast information using control/common channel broadcast
`signals. 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
`beacons from the 802.11 access points in range and calcu
`lates the geographic location of the computing device using
`characteristics from the signal beacons. Those characteris
`tics include the unique identifier of the 802.11 access point,
`known as the MAC address, and the strengths of the signal
`reaching the client device. The client software compares the
`observed 802.11 access points with those in its reference
`database 104 of access points, which may or may not
`reside on the device as well. The reference database contains
`the calculated geographic locations or power profile of all
`the access points the gathering system has collected. The
`power profile is a collection of readings that represent the
`power of the signal from various locations. Using these
`known locations, the client software calculates the relative
`position of the user device 101 and determines its geo
`graphic coordinates in the form of latitude and longitude
`readings. Those readings are then fed to location- based
`applications such as friend finders, local search web sites,
`fleet management systems and E911 services.
`0043. The positioning software is described in greater
`detail with reference to FIG. 9, which depict exemplary
`
`Page 15 of 20
`
`

`

`US 2006/0095349 A1
`
`May 4, 2006
`
`components of positioning software 103. Typically there is
`an application or service 901 that utilizes location readings
`to provide some value to an end user (example, driving
`directions). This location application makes a request of the
`positioning software for the location of the device at that
`particular moment. That request initiates the scanner 902).
`which makes a “scan request' to the 802.11 radio 903 on
`the device. The 802.11 radio sends out a probe request to all
`802.11 access points 904 within range. According to the
`802.11 protocol, those access points in receipt of a probe
`request will transmit a broadcast beacon containing infor
`mation about the access point. That beacon includes the
`MAC address of the device, the network name, the precise
`version of the protocol that it supports and its security
`configuration along with information about how to connect
`to the device. The 802.11 radio collects this information
`from each access point that responds, calculates the signal
`strength of each access point and sends that back to the
`SCa.
`0044) The scanner passes this array of access points to the
`Locator 906 which checks the MAC addresses of each
`observed access point against the Access Point Reference
`Database 905). This database can either be located on the
`device or remotely over a network connection. The Access
`Point Reference Database returns the location data for each
`of the observed access points that are known to the system.
`The Locator passes this collection of location information
`along with the signal characteristics returned from each
`access point to the Bad Data Filter 907). This filter applies
`a number of comparison tests against each access point to
`determine if any of the access points have moved since they
`were added to the access point database. After removing bad
`data records, the Filter sends the remaining access points to
`the Location Calculation component 908). Using the ref
`erence data from the access point database and the signal
`strength readings from the Scanner, the Location Calculation
`component computes the location of the device at that
`moment. Before that location data is sent back to the
`Locator, it is processed by the Smoothing engine 909
`which averages a past series of location readings to remove
`any erratic readings from the previous calculation. The
`adjusted location data is then sent back to the Locator.
`0045. The calculated location readings produced by the
`Locator are communicated to these location-based applica
`tions 901 through the Application Interface 910 which
`includes an application programming interface (API) or via
`a virtual GPS capability 911). GPS receivers communicate
`their location readings using proprietary messages or using
`the location standard like the one developed by the National
`Marine Electronics Association (NMEA). Connecting into
`the device using a standard interface Such as a COM port on
`the machine retrieves the messages. Certain embodiments of
`the invention include a virtual GPS capability that allows
`any GPS compatible application to communicate with this
`new positioning system without have to alter the commu
`nication model or messages.
`0046) The location calculations are produced using a
`series of positioning algorithms intended to turn noisy data
`flows into reliable and steady location readings. The client
`Software compares the list of observed access points along
`with their calculated signal strengths to weight the location
`of user to determine precise location of the device user. A
`variety of techniques are employed including simple signal
`
`strength weighted average models, nearest neighbor models
`combined with triangulation techniques and adaptive
`smoothing based on device velocity. Different algorithms
`perform better under different scenarios and tend to be used
`together in hybrid deployments to product the most accurate
`final readings. Preferred embodiments of the invention can
`use a number of positioning algorithms. The decision of
`which algorithm to use is driven by the number of access
`points observed and the user case application using it. The
`filtering models differ from traditional positioning systems
`since traditional systems rely on known reference points that
`never move. In the model of preferred embodiments, this
`assumption of fixed locations of access points is not made;
`the access points are not owned by the positioning system so
`they may move or be taken offline. The filtering techniques
`assume that some access points may no longer be located in
`the same place and could cause a bad location calculation.
`So the filtering algorithms attempt to isolate the access
`points that have moved since their position was recorded.
`The filters are dynamic and change based on the number of
`access points observed at that moment. The Smoothing
`algorithms include simple position averaging as well as
`advanced bayesian logic including Kalman filters. The
`Velocity algorithms calculate device speed by estimating the
`Doppler effect from the signal strength observations of each
`access point.
`
`Gathering of Scan Data to Build Reference
`Database
`0047 FIG. 2 depicts the components used to gather
`location information for the various access points. A large
`fleet of vehicles 201 is deployed to build the reference
`database (104 of FIG. 1) for the positioning system. These
`vehicles 201 follow a programmatic route through target
`scan areas to gather data in the most optimal fashion
`producing the highest quality data. The target scan areas
`typically represent a large metropolitan area including every
`single drivable street in 15-20 mile radius. These vehicles
`are equipped with scanning devices 202 designed to record
`the locations and characteristics of 802.11 signals while
`traversing the coverage area. The scanning devices track the
`location of the Scanning vehicle every second using signal
`from GPS satellites 204). The scanning device also tracks
`the presence of any 802.11 access point within range and
`records the radio characteristics of that access point signal
`along with the GPS location of the scanning vehicle. The
`quality of the data collected is greatly affected by the
`scanning methodology employed by the scanning vehicles.
`Each model has its own benefits and limitations. One
`approach, known as the Random Model, places scanning
`devices in vehicles as they are conducting daily activities for
`business or personal use. These vehicles could be delivery
`trucks, taxi cabs, traveling salesman or just hobbyists. The
`concept is that over time these vehicles will cover enough
`streets in their own random fashion in order to build a
`reliable reference database. The model does in fact provide
`a simple means to collect data but the quality of the resulting
`data is negatively affected due to issues of “arterial bias’.
`FIG. 3 describes the challenge of the random model. When
`scanning vehicles traverse routes designed to Solve other
`problems than gathering data (e.g. delivering packages,
`people commuting to and from work) they tend to follow
`destinat