Techniques for computing location of a mobile device based on observed Wi-Fi access points

• US 9,554,247 B2
• Filed: 06/13/2016
• Issued: 01/24/2017
• Est. Priority Date: 10/29/2004
• Status: Active Grant

• Current Assignee: Skyhook Wireless Incorporated (Liberty Broadband Corp.)
• Original Assignee: Skyhook Wireless Incorporated (Liberty Broadband Corp.)
• Inventors: Jones, Russel K., Alizadeh-Shabdiz, Farshid, Morgan, Edward J., Shean, Michael G.
• Primary Examiner(s): Patel, Nimesh
• Application Number:
  US15/181,057
• Publication Number:
  US 20160295360A1
• Time in Patent Office: 225 Days
• US Class Current: 1/1
• CPC Class Codes: G01S 19/13 Receivers
• CPC Class Codes: G01S 19/14 specially adapted for specific applications
• CPC Class Codes: G01S 19/46 the supplementary measurement being of a radio-wave signal type
• CPC Class Codes: G01S 5/0205 Details
• CPC Class Codes: G01S 5/021 Calibration, monitoring or correction G01S5/0252 takes precedence
• CPC Class Codes: G01S 5/0226 Transmitters
• CPC Class Codes: G01S 5/0242 Determining the position of transmitters to be subsequently used in positioning G01S5/0289 takes precedence
• CPC Class Codes: G01S 5/02526 using non-dedicated equipment, e.g. user equipment or crowd-sourcing
• CPC Class Codes: G01S 5/0284 Relative positioning
• CPC Class Codes: G06Q 10/0875 Itemisation or classification of parts, supplies or services, e.g. bill of materials
• CPC Class Codes: G08G 1/20 Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles
• CPC Class Codes: H04W 16/18 Network planning tools
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 64/003 locating network equipment
• CPC Class Codes: H04W 84/10 Small scale networks; Flat hierarchical networks
• CPC Class Codes: H04W 84/12 : WLAN [Wireless Local Area Networks]
• CPC Class Codes: H04W 88/06 : adapted for operation in multiple networks or having at least two operational modes, e.g. multi-mode terminals
• CPC Class Codes: H04W 88/08 : Access point devices
• CPC Class Codes: Y10S 707/99936 : Pattern matching access

Abstract

In one embodiment, scanning data is received for wireless access points whose wireless signals were observed by the one or more scanning devices in a target area. For each group of scanning data that shares a common identifier of a Wi-Fi access point, a centroid of the scanning data is determined, a set of scanning data of the group that exceeds a threshold distance from the centroid is designated as having potential error, and a location of the Wi-Fi access point is calculated. The calculated location of the Wi-Fi access point for each group of scanning data is stored in a reference database. Upon receiving a request for a location of a mobile device, an identity of one or more Wi-Fi access points in range of the mobile device is determined, and the location of the mobile device is computed using calculated locations from the reference database.

Claims

1. A method comprising:

receiving, at a server from one or more scanning devices, scanning data for Wi-Fi access points whose Wi-Fi signals were observed by the one or more scanning devices in a target area, wherein the one or more scanning devices each include a radio for observing the Wi-Fi signals;

identifying groups of scanning data that share a common identifier of a Wi-Fi access point;

for each group of scanning data, determining a centroid of the scanning data of the group, designating a set of scanning data of the group that exceeds a threshold distance from the centroid as having potential error, and calculating a location of the Wi-Fi access point by applying a reverse triangulation algorithm to the scanning data of the group that has not been designated as having potential error;

storing the calculated location of the Wi-Fi access point for each group of scanning data in a reference database;

receiving, by client software executing on a mobile device from an application or service on the mobile device that utilizes location readings, a request for a location of the mobile device;

obtaining, by the client software, an identity of one or more Wi-Fi access points in range of the mobile device;

computing the location of the mobile device using calculated locations of the one or more Wi-Fi access points from the reference database; and

returning, by the client software, the computed location of the mobile device to the application or service.

2. The method of claim 1, wherein the centroid is a weighted centroid determined from scanning data weighted based upon age, wherein newer scanning data is assigned a greater weight than older scanning data.

3. The method of claim 1, wherein each item of scanning data includes a location, and the designating the set of scanning data further comprises:

calculating a standard deviation of a distribution of locations of the group of scanning data; and

determining the threshold distance based upon the standard deviation.

4. The method of claim 1, further comprising:

removing the set of scanning data designated as having potential error.

5. The method of claim 1, further comprising:

marking the set of scanning data designated as having potential error; and

storing the marked scanning data in the reference database.

6. The method of claim 1, wherein the calculating the location of the Wi-Fi access point weights scanning data of the group that has not been designated as having potential error based on a number of observations of the Wi-Fi signals.

7. The method of claim 1, wherein the storing the calculated location of the Wi-Fi access point for each group of scanning data further comprises:

storing a timestamp in the reference database indicating freshness of the calculated location.

8. The method of claim 1, further comprising:

generating a subset of the reference database based upon geography;

downloading the subset to the mobile device; and

performing the receiving the request, the obtaining the identity, and the computing the location by the client software executing on the mobile device based on the subset.

9. The method of claim 1, wherein the target area is a geographic area having a radius of one or more miles, and the Wi-Fi signals were observed by the one or more scanning devices during a traversal of substantially all drivable streets within the geographic area.

10. A system comprising:

a central network server configured to receive scanning data for Wi-Fi access points whose Wi-Fi signals were observed in a target area, identify groups of scanning data that share a common identifier of a Wi-Fi access point, and for each group of scanning data, determine a centroid of the scanning data of the group, designate a set of scanning data of the group that exceeds a threshold distance from the centroid as having potential error, and calculate a location of the Wi-Fi access point by applying a reverse triangulation algorithm to the scanning data of the group that has not been designated as having potential error;

a reference database configured to store the calculated location of the Wi-Fi access point for each group of scanning data; and

a mobile device having client software configured to receive a request for a location of the mobile device from an application or service executing on the mobile device that utilizes location readings, identify one or more Wi-Fi access points in range of the mobile device, compute the location of the mobile device using calculated locations of the one or more Wi-Fi access points from the reference database, and return the computed location of the mobile device to the application or service.

11. The system of claim 10, wherein the centroid is a weighted centroid determined from scanning data weighted based upon age, wherein newer scanning data is assigned a greater weight than older scanning data.

12. A non-transitory computer-readable medium having instructions executable by one or more processors stored thereon, the instructions when executed by the one or more processors operable to:

process scanning data for Wi-Fi access points whose Wi-Fi signals were observed in a target area;

identify groups of scanning data that share a common identifier of a Wi-Fi access point;

for each group of scanning data, determine a centroid of the scanning data of the group, designate a set of scanning data of the group that exceeds a threshold distance from the centroid as having potential error, and calculate a location of the Wi-Fi access point by applying a reverse triangulation algorithm to the scanning data of the group that has not been designated as having potential error; and

store the calculated location of the Wi-Fi access point for each group of scanning data in a reference database of a central network server; and

distribute at least a portion of the reference database from the central network server to a mobile device that is usable by client software executing on the mobile device to compute the location of the mobile device using calculated locations from the at least the portion of reference database of one or more Wi-Fi access points that are in range of the mobile device to be returned to an application or service on the mobile device.

13. The non-transitory computer-readable medium of claim 12, wherein the centroid is a weighted centroid determined from scanning data weighted based upon age, wherein newer scanning data is assigned a greater weight than older scanning data.

14. The non-transitory computer-readable medium of claim 12, wherein each item of scanning data includes a location, and the instructions that when executed are operable to designate the set of scanning data are further operable to:

calculate a standard deviation of a distribution of locations of the group of scanning data; and

determine the threshold distance based upon the standard deviation.

15. The non-transitory computer-readable medium of claim 12, wherein the instructions when executed are further operable to:

remove the set of scanning data designated as having potential error.

16. The non-transitory computer-readable medium of claim 12, wherein the instructions when executed are further operable to:

mark the set of scanning data designated as having potential error; and

store the marked scanning data in the reference database.

17. The non-transitory computer-readable medium of claim 12, wherein the instructions that when executed are operable to calculate the location of the Wi-Fi access point are further operable to:

weight scanning data of the group that has not been designated as having potential error based on observed signal strength of the Wi-Fi signals.

18. The non-transitory computer-readable medium of claim 12, wherein the instructions that when executed are operable to calculate the location of the Wi-Fi access point are further operable to:

weight scanning data of the group that has not been designated as having potential error based on a number of observations of the Wi-Fi signals.

19. The non-transitory computer-readable medium of claim 12, wherein the instructions that when executed are operable to store the calculated location of the Wi-Fi access point for each group of scanning data are further operable to:

store a timestamp in the reference database indicating freshness of the calculated location.

20. The non-transitory computer-readable medium of claim 12, wherein the instructions when executed are further operable to:

receive a request for a location of the mobile device from the application or service on the mobile device that utilizes location readings;

obtain an identity of the one or more Wi-Fi access points in range of the mobile device; and

in response to the request for the location of the mobile device, compute the location of the mobile device using the calculated locations of the one or more Wi-Fi access points from the reference database, and return the computed location of the mobile device to the application or service.