Server for updating location beacon database

• US 8,837,363 B2
• Filed: 09/06/2011
• Issued: 09/16/2014
• 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:
  US13/225,848
• Publication Number:
  US 20110317579A1
• Time in Patent Office: 1,106 Days
• Field of Search: 370/328, 370/347.02, 342/572.4, 455/456.5, 455/456.6, 455/456.1
• US Class Current: 370/328
• 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

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.

Claims

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.