LOCATION-BASED SERVICES THAT CHOOSE LOCATION ALGORITHMS BASED ON NUMBER OF DETECTED ACCESS POINTS WITHIN RANGE OF USER DEVICE

• US 20080132170A1
• Filed: 12/04/2007
• Published: 06/05/2008
• Est. Priority Date: 10/29/2004
• Status: Active Grant

• Current Assignee: Skyhook Wireless Incorporated (Liberty Broadband Corp.), Skhyook Wireless Incorporated
• Original Assignee: Skyhook Wireless Incorporated (Liberty Broadband Corp.)
• Inventors: MORGAN, Edward James, JONES, Russel Kipp, SHEAN, Michael G., ALIZADEH-SHABDIZ, Farshid
• Granted Patent: US 7,769,396 B2
• Time in Patent Office: Days
• US Class Current: 455/41.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.

Claims

1. A method of locating a user-device having a Wi-Fi radio, comprising:

providing a reference database of Wi-Fi access point information about Wi-Fi access points in a target area;

in response to a user application request to determine a location of a user-device having a Wi-Fi radio, receiving messages from Wi-Fi access points within range of the Wi-Fi device, each message identifying the Wi-Fi access point sending the message;

determining attributes of the messages received by the Wi-Fi radio;

accessing the reference database to obtain information about 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; and

using the information about the identified Wi-Fi access points and the determined attributes of said received messages and the chosen location-determination algorithm to determine the location of the user-device.

2. The method of claim 1, wherein a first location-determination algorithm of the plurality of location-determination algorithms uses a first set of information about the identified Wi-Fi access points and a second location-determination algorithm of the plurality of location-determination algorithms uses a second set of information about the identified Wi-Fi access points, the first set of information differing from the second set of information.

3. The method of claim 1 wherein the information about the identified Wi-Fi access points are filtered to determine if the corresponding Wi-Fi access points have moved since the time the information about the Wi-Fi access points was included in the reference database.

4. The method of claim 1 wherein the reference database is located locally relative to the user-device.

5. The method of claim 1 wherein the reference database is located remotely relative to the user-device.

6. The method of claim 1 wherein the location of the user device is provided with latitude and longitude coordinates.

7. The method of claim 1 wherein the plurality of location-determination algorithms includes a simple signal strength weighted average model.

8. The method of claim 1 wherein the plurality of location-determination algorithms includes a nearest neighbor model.

9. The method of claim 1 wherein the plurality of location-determination algorithms includes a triangulation technique.

10. The method of claim 1 wherein the plurality of location-determination algorithms includes an adaptive smoothing technique based on the device velocity.

11. The method of claim 1 wherein the choice of location-determination algorithm is further based on the user application making the location request.

12. The method of claim 1 wherein the information about at least one of the Wi-Fi access points of the reference database includes signal fingerprint information of the Wi-Fi access point, the signal fingerprint information including a plurality of expected signal strength readings of messages transmitted by the Wi-Fi access point at a corresponding plurality of expected locations where the messages are received.

13. The method of claim 12 wherein the plurality of location-determination algorithms includes a technique based on signal fingerprints for more than one Wi-Fi access point.

14. The method of claim 13 wherein the technique includes determining a location by:

calculating the signal strength of messages received by the Wi-Fi radio;

comparing the calculated signal strength with the expected signal strengths of the signal fingerprint information for the more than one Wi-Fi access point to find expected signal strengths that most closely match the calculated signal strength; and

determining the location of the user-device based on expected locations that correspond to the expected signal strengths most closely matching the calculated signal strength.

15. The method of claim 1 wherein more than one location-determination algorithm from the plurality of location-determination algorithms is used to determine the location of the user-device.