Method and system for selecting and providing a relevant subset of Wi-Fi location information to a mobile client device so the client device may estimate its position with efficient utilization of resources

• US 8,369,264 B2
• Filed: 12/28/2007
• Issued: 02/05/2013
• Est. Priority Date: 10/28/2005
• Status: Active Grant

• Current Assignee: Skyhook Wireless Incorporated (Liberty Broadband Corp.)
• Original Assignee: Skyhook Wireless Incorporated (Liberty Broadband Corp.)
• Inventors: Brachet, Nicolas, Alizadeh-Shabdiz, Farshid, Jones, Russel K., Nelson, Joel N.
• Primary Examiner(s): Patel, Nimesh
• Application Number:
  US11/966,673
• Publication Number:
  US 20080176583A1
• Time in Patent Office: 1,866 Days
• Field of Search: 370/328, 340/572.4, 342/357.02, 455/456.1, 455/456.5, 455/456.6, 707/6, 707/16, 711/165, 708/160
• US Class Current: 370/328
• CPC Class Codes: G01S 5/0236 Assistance data, e.g. base station almanac
• CPC Class Codes: G01S 5/0295 Proximity-based methods, e.g. position inferred from reception of particular signals
• CPC Class Codes: H04L 67/5683 Storage of data provided by user terminals, i.e. reverse caching
• CPC Class Codes: H04W 16/18 Network planning tools
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/024 Guidance services
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration 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/14 using user query or user detection
• CPC Class Codes: H04W 48/20 Selecting an access point
• 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 8/005 Discovery of network devices, e.g. terminals
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]

Abstract

Methods and systems for selecting and providing a relevant subset of Wi-Fi location information to a mobile client device so the client device may estimate its position with efficient utilization of resources.

A method of providing a relevant subset of information to a client device is based in part on scanning for Wi-Fi access points within range of the client device, using a Wi-Fi database that covers a large target region to retrieve information about these access points, using this information to estimate the position of the mobile client device, selecting a limited region in the vicinity of the estimated location of the client device, and providing information about Wi-Fi access points within this limited region to the client. For efficient transfer and maintenance of data, the target region may be divided into a hierarchy of fixed geographical tiles.

Claims

1. In a Wi-Fi positioning system comprising a reference database of Wi-Fi access point information recorded in a computer-readable medium and containing information about Wi-Fi access points within a large target region, a method of selecting and providing, to at least one mobile client device equipped with Wi-Fi communication logic, a subset of Wi-Fi access point information from said reference database to be used by the client device to estimate its position, wherein the subset is tailored to include information about Wi-Fi access points in a subdivision of the large target region based on the proximity of the client device to the selected subdivision, the method comprising:

providing a set of geographical regions, each geographical region being a subdivision of the large target region, and each geographical region containing a plurality of the Wi-Fi access points;

selecting at least one relevant geographical region from the set of geographical regions based on the proximity of the mobile device to the relevant geographical region;

selecting from the reference database a subset of Wi-Fi access points that are contained in the at least one relevant geographic region; and

providing to the mobile client device information from said reference database about the subset of Wi-Fi access points that are located within the at least one relevant geographical region, the information including identifiers for corresponding Wi-Fi access points in the relevant geographical region and including estimated geographic locations of the corresponding Wi-Fi access points so the mobile client device may subsequently estimate its position using the estimated geographic location of at least one of the Wi-Fi access points in the relevant geographical region.

2. The method according to claim 1 further including partitioning the target region into the set of geographical regions according to a prearranged scheme.

3. The method according to claim 2 wherein the prearranged partitioning scheme divides the target area into a set of geometrically similar, polygonal tiles.

4. The method according to claim 3 wherein the polygonal tiles form a hierarchy in which smaller tiles are nested within larger tiles.

5. The method according to claim 3 further including selecting a maximum number of Wi-Fi access points that may be contained within a single polygonal tile, and choosing the size of the polygonal tiles such that no tile contains more than said maximum.

6. The method according to claim 3 that further includes storing, for each of the polygonal tiles, a time of a most recent update to reference database records corresponding to Wi-Fi access points within the tile, and using this information to determine whether the Wi-Fi access point data stored on the client device is up-to-date.

7. The method according to claim 1 further including estimating the speed and direction of the client device, and using said estimates in selecting the at least one relevant geographical region.

8. The method according to claim 1 further including predicting a route along which the client device is traveling, and using this predicted route in selecting the at least one relevant geographical region.

9. The method according to claim 1 wherein the client device has allocated a limited amount of memory for storing Wi-Fi access point data, and the at least one relevant geographical region is selected according to the amount of memory that has been allocated by the client device.

10. The method according to claim 1 wherein the transfer of information between the client device and the access point reference database may not exceed a certain maximum speed, and the at least one relevant geographical region is selected according to this maximum speed of communication between the client device and the reference database.

11. The method according to claim 1 wherein the estimation of the location of the mobile client device is performed by the mobile client device.

12. The method according to claim 1 wherein the mobile client device is equipped with information about an initial set of Wi-Fi access points that are located within a specified geographical region.

13. The method according to claim 1 further comprising:

extracting information from the detected signals from at least one Wi-Fi access point currently in range of the mobile client device and detected by the mobile client device identifying the at least one Wi-Fi access point;

wherein the selection of the at least one relevant geographical region is based on the at least one identified Wi-Fi access point.

14. The method according to claim 1 further comprising:

estimating the location of the mobile client device;

wherein the selection of the at least one relevant geographical region is based on the estimated location of the mobile client device.

15. The method according to claim 14, the estimating the location of the mobile client device including:

identifying at least one Wi-Fi access point that is currently within range of the client device and detected by the mobile client device;

obtaining Wi-Fi access point information for the identified Wi-Fi access points; and

estimating the location of the mobile client device using the obtained information.

16. The method of claim 1, further comprising determining the set of geographical regions by subdividing at least a portion of the large target region, the subdividing being based on criteria independent of the coverage area of Wi-Fi access points.

17. The method of claim 1, further comprising determining the set of geographical regions by subdividing at least a portion of the large target region, the subdividing being based on at least one of a density of Wi-Fi access points in the geographical regions, a total number of Wi-Fi access points in the geographical regions, a memory capacity of the mobile client device, and a mode of communication of the mobile client device.