Method and system for building a location beacon database

• US 7,403,762 B2
• Filed: 10/28/2005
• Issued: 07/22/2008
• 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: Alizadeh-Shabdiz, Farshid, Morgan, Edward James, Shean, Michael George, Jones, Russel Kipp
• Primary Examiner(s): Pérez-Gutiérrez; Rafael
• Assistant Examiner(s): Patel; Nimesh
• Application Number:
  US11/261,987
• Publication Number:
  US 20060095349A1
• Time in Patent Office: 998 Days
• Field of Search: 455/456.1, 455/404.2, 340/572.4, 708/160, 711/165, 370/315
• US Class Current: 455/404.2
• 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 avoid 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, periodically receive the GPS coordinates of the GPS device. While traversing the target area, detecting Wi-Fi signals from Wi-Fi access points in range of the Wi-Fi device and recording identity information of the detected Wi-Fi access point in conjunction with GPS location information of the vehicle when the detection of the Wi-Fi access point was made. 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. A user-device having a Wi-Fi radio may be located. A reference database of calculated locations of Wi-Fi access points in a target area is provided. In response to a user application request to determine a location of a user-device having a Wi-Fi radio, the Wi-Fi device is triggered to transmit a request to all Wi-Fi access points within range of the Wi-Fi device. Messages are received from the Wi-Fi access points within range of the Wi-Fi device, each message identifying the Wi-Fi access point sending the message. The signal strength of the messages received by the Wi-Fi access points is calculated. The reference database is accessed to obtain the calculated locations for the identified Wi-Fi access points. Based on the number of Wi-Fi access points identified via received messages, choosing a corresponding location-determination algorithm from a plurality of location-determination algorithms, said chosen algorithm being suited for the number of identified Wi-Fi access points. The calculated locations for the identified Wi-Fi access points and the signal strengths of said received messages and the chosen location-determination algorithm are used to determine the location of the user-device. The database may be modified with newly added position information to improve quality of previously determined positions, and error prone information is avoided.

Claims

1. A method of locating Wi-Fi access points in a target geographical area to build a reference database of locations of Wi-Fi access points, comprising:

deploying at least one vehicle including at least one scanning device having a GPS device and a Wi-Fi radio device and including a Wi-Fi antenna system;

traversing the target area in a programmatic route to avoid arterial bias, said programmatic route including substantially all drivable streets in the target geographical area and solving an Eulerian cycle problem of a graph represented by said drivable streets;

while traversing the target area, receiving the GPS coordinates of the GPS device;

while traversing the target area, detecting Wi-Fi signals from Wi-Fi access points in range of the Wi-Fi device and recording identity information of the detected Wi-Fi access point in conjunction with GPS location information of the vehicle when the detection of the Wi-Fi access point was made;

using said location information to reverse triangulate the position of the detected Wi-Fi access point; and

recording the position of the detected access point in a reference database.

2. The method of claim 1 wherein the target geographic area has a radius on the order of tens of miles.

3. The method of claim 1 wherein the programmatic route is determined by using the Chinese postman routing algorithm.

4. The method of claim 1 wherein the reference database is located remotely and position information of Wi-Fi access points is loaded into the reference database via a Wi-Fi access network.

5. The method of claim 1 wherein, when detecting Wi-Fi signals, several readings of Wi-Fi signals are made for a given Wi-Fi access point so that a set of readings is formed for the given Wi-Fi access point and wherein said set of readings is used when determining the position of the detected Wi-Fi access point.

6. The method of claim 1 wherein when detecting a Wi-Fi access point signal strength information about the signal from the Wi-Fi access point is calculated and recorded by the scanning device.

7. The method of claim 1 wherein a given Wi-Fi access point is detected from as many different angles as possible given the organization of the drivable streets.

8. The method of claim 6 wherein a given Wi-Fi access point is detected from as many different angles as possible given the organization of the drivable streets, and wherein a power profile of signal strengths for a given Wi-Fi access point is determined and recorded.

9. The method of claim 1 wherein the Wi-Fi antenna system includes directional antennas and wherein the scanning device records a vector of origin of a Wi-Fi access point based on different signal strengths received by the Wi-Fi access point on the directional antennas.

10. The method of claim 1 wherein the GPS coordinates of the vehicle are monitored about every second with the GPS device operating in continuous mode.

11. The method of claim 1 wherein the Wi-Fi device sends probe requests and records GPS location information about every tenth of a second.

12. The method of claim 1 wherein access points are located for a plurality of target areas.

13. The method of claim 12 wherein the reference database holds position information for the detected access points for the plurality of target areas and wherein the information is organized based on the target area.