Server for updating location beacon database
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 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 traversed in a programmatic route to reduce 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, Wi-Fi identity information and GPS location information is detected. 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.
1. A system comprising:
computer-implemented logic to derive position information for each of a plurality of Wi-Fi access points in a geographic area having a radius on the order of miles, wherein the position information is derived at least in part by application of a reverse triangulation algorithm to sets of data collected during a comprehensive traversal of the geographic area, each set of data including signal data describing observed characteristics of a signal received from the Wi-Fi access point, the observed characteristics including at least a unique identifier of the Wi-Fi access point and a received signal strength of the signal received from the Wi-Fi access point, and location data characterizing a location at which the signal received from the Wi-Fi access point was observed; and
computer-implemented logic to store the derived position information in a non-transitory computer-readable medium.
2. The system of claim 1 , wherein the geographical area has a radius on the order of at least tens of miles.
3. The system of claim 1 , wherein the computer-implemented logic to store the derived position information includes logic to store the derived position information for a particular Wi-Fi access point in association with data representative of an identifier of that Wi-Fi access point.
4. The system of claim 1 , wherein the comprehensive traversal of the geographic area comprises an exhaustive traversal of accessible thoroughfares of the geographic area.
5. The system of claim 1 , wherein the comprehensive traversal of the geographic area comprises a systematic traversal of accessible thoroughfares of the geographic area.
6. The system of claim 1 , wherein the computer-implemented logic to derive the position information includes logic to derive position information from a combination of newly-collected sets of data and previously-collected sets of data.
7. The system of claim 1 , further comprising:
computer-implemented logic to identify sets of data with potential error.
8. The system of claim 7 , wherein the computer-implemented logic to derive the position information includes logic to exclude the identified sets of data with potential error from the sets of data from which the position information is derived.
9. The system of claim 7 , further comprising:
computer-implemented logic to identify a portion of the geographic area in which the identified sets of data with potential error was collected.
10. The system of claim 1 , further comprising computer-implemented logic to:
identify, as a group, sets of data that share a common identifier of a Wi-Fi access point; and
perform clustering analysis of the sets of data of the identified group, and based on results of the analysis, designate one or more sets of data of the identified group as sets of data with potential error.
11. The system of claim 10 , wherein the logic to perform clustering analysis includes logic to:
determine a first centroid for the Wi-Fi access point based at least in part on the sets of data of the identified group; and
designate a first set of data as a set of data with potential error if a comparison of a distance between the first centroid and the location data of the first set of data exceeds a threshold.
12. The system of claim 10 , wherein the logic to perform clustering analysis includes logic to:
determine a weighted centroid for the Wi-Fi access point based at least in part on the age of the location data of the sets of data of the identified group; and
designate a first set of data as a set of data with potential error if a comparison of a distance between the weighted centroid and the location data of the first set of data exceeds a threshold.
13. The system of claim 1 , further comprising:
a collection of information in the non-transitory computer-readable medium, the collection of information describing the plurality of Wi-Fi access points in the geographic area.
14. The system of claim 13 , wherein the plurality of Wi-Fi access points in the geographic area includes substantially all of the Wi-Fi access points in the geographic area.
15. The system of claim 1 , wherein the sets of data that share a common identifier of a Wi-Fi access point provide reference symmetry when the position information for the Wi-Fi access point is derived.
16. The system of claim 1 , wherein the sets of data that share a common identifier of a Wi-Fi access point reduce arterial bias when the position information for the Wi-Fi access point is derived.
17. The system of claim 1 , further comprising:
computer-implemented logic to identify at least one portion of the geographic area in which no position information for a Wi-Fi access point is derived.
18. A computer-implemented method comprising:
deriving position information for each of a plurality of Wi-Fi access points in a geographic area having a radius on the order of miles, wherein the position information is derived at least in part by application of a reverse triangulation algorithm to sets of data collected during a comprehensive traversal of the geographic area, each set of data including signal data describing observed characteristics of a signal received from the Wi-Fi access point, the observed characteristics including at least a unique identifier of the Wi-Fi access point and a received signal strength of the signal received from the Wi-Fi access point, and location data characterizing a location at which the signal received from the Wi-Fi access point was observed; and
storing the derived position information in a non-transitory computer-readable medium.
19. The method of claim 18 , wherein the geographical area has a radius on the order of at least tens of miles.
20. The method of claim 18 , wherein storing the derived position information includes storing the derived position information for a particular Wi-Fi access point in association with data representative of an identifier of that Wi-Fi access point.
21. The method of claim 18 , wherein the comprehensive traversal of the geographic area comprises an exhaustive traversal of accessible thoroughfares of the geographic area.
22. The method of claim 18 , wherein the comprehensive traversal of the geographic area comprises a systematic traversal of accessible thoroughfares of the geographic area.
23. The method of claim 18 , wherein deriving the position information includes deriving position information from a combination of newly-collected sets of data and previously-collected sets of data.
24. The method of claim 18 , further comprising:
identifying sets of data with potential error.
25. The method of claim 24 , wherein deriving the position information includes excluding the identified sets of data with potential error from the sets of data from which the position information is derived.
26. The method of claim 24 , further comprising:
identifying a portion of the geographic area in which the identified sets of data with potential error was collected.
27. The method of claim 18 , further comprising:
identifying, as a group, sets of data that share a common identifier of a Wi-Fi access point; and
performing clustering analysis of the sets of data of the identified group, and based on results of the analysis, designating one or more sets of data of the identified group as sets of data with potential error.
28. The method of claim 27 , wherein performing clustering analysis includes:
determining a first centroid for the Wi-Fi access point based at least in part on the sets of data of the identified group; and
designating a first set of data as a set of data with potential error if a comparison of a distance between the first centroid and the location data of the first set of data exceeds a threshold.
29. The method of claim 27 , wherein performing clustering analysis includes:
determining a weighted centroid for the Wi-Fi access point based at least in part on the age of the location data of the sets of data of the identified group; and
designating a first set of data as a set of data with potential error if a comparison of a distance between the weighted centroid and the location data of the first set of data exceeds a threshold.
30. The method of claim 28 , wherein the sets of data that share a common identifier of a Wi-Fi access point provide reference symmetry when deriving the position information for the Wi-Fi access point.
31. The method of claim 28 , wherein the sets of data that share a common identifier of a Wi-Fi access point reduce arterial bias when deriving the position information for the Wi-Fi access point.
32. The method of claim 28 , further comprising:
identifying at least one portion of the geographic area in which no position information for a Wi-Fi access point is derived.
33. Software, embodied in a non-transitory computer-readable medium, comprising instructions executable by a processor to:
derive position information for each of a plurality of Wi-Fi access points in a geographic area having a radius on the order of miles, wherein the position information is derived at least in part by application of a reverse triangulation algorithm to sets of data collected during a comprehensive traversal of the geographic area, each set of data including signal data characterizing one or more observed characteristics of a signal received from the Wi-Fi access point, the observed characteristics including at least a unique identifier of the Wi-Fi access point and a received signal strength of the signal received from the Wi-Fi access point, and location data characterizing a location at which the signal received from the Wi-Fi access point was observed; and
store the derived position information in a non-transitory computer-readable medium.
34. Software of claim 33 , wherein the geographical area has a radius on the order of at least tens of miles.
35. Software of claim 33 , wherein the instructions executable by the data processor to derive the position information include instructions to derive position information from a combination of newly-collected sets of data and previously-collected sets of data.
36. Software of claim 33 , wherein the instructions executable by the data processor to derive the position information include instructions to excludes sets of data with potential error from the sets of data from which the position information is derived.