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

Patent metadata

Field	Value
Publication number	US-9554247-B2
Application number	US-201615181057-A
Country	US
Kind code	B2
Filing date	Jun 13, 2016
Priority date	Oct 29, 2004
Publication date	Jan 24, 2017
Grant date	Jan 24, 2017

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.

First claim

What is claimed is:

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 gro

Assignees

• Skyhook Wireless Inc

Inventors

• Jones Russel K
• Alizadeh-Shabdiz Farshid
• Morgan Edward J
• Shean Michael G

Classifications

• G01S5/0226

  Transmitters · CPC title

• H04W64/003 Primary

  locating network equipment · CPC title

• H04W48/16

  Discovering, processing access restriction or access information · CPC title

• G01S5/0284

  Relative positioning · CPC title

• G01S19/14

  specially adapted for specific applications · CPC title