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

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.