Determining a location of a mobile device using a location database

• US 8,200,251 B2
• Filed: 01/15/2010
• Issued: 06/12/2012
• Est. Priority Date: 01/15/2010
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Huang, Ronald K.
• Primary Examiner(s): Tran, Congvan
• Application Number:
  US12/688,788
• Publication Number:
  US 20110177831A1
• Time in Patent Office: 879 Days
• Field of Search: 455/404.2, 455/456.1, 455/456.3, 455/456.6, 455/457, 455436-439, 370/331, 370/332
• US Class Current: 455/457
• CPC Class Codes: G01S 5/02524 Creating or updating the radio-map
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

Methods, program products, and systems for determining a location of a mobile device using a location database are described. The mobile device can host the location database, which can store locations associated with access points. The locations can be distributed in a group of cells of a geographic grid. When the mobile device moves and connects to an access point associated with a location that is outside the group of cells, the mobile device can request an update of the location database. The mobile device can calculate a current location of the mobile device using current access points that are within a communication range of the mobile device by performing a lookup in the location database using identifiers of the current access points. The mobile device can calculate the current location using the locations corresponding to the current access points in the location database.

Claims

1. A computer-implemented method executed by a mobile device, comprising:

identifying a current access point within a communication range of which the mobile device is located;

requesting, from a server, an update of a location database of the mobile device using an identifier of the current access point, the location database storing first locations associated with first access points;

receiving a set of second locations associated with second access points, the second locations distributed in a center cell of a geographic grid and cells neighboring the center cell of the geographic grid, the current access point corresponding to a location within the center cell, the center cell and cells neighboring the center cell covering a predetermined geographic area;

updating the location database using the received set of locations; and

calculating a current location of the mobile device using the location database.

2. The method of claim 1, where calculating a current location of the mobile device using the location database comprises:

(a) receiving identifiers of access points that are within a communication range of the mobile device;

(b) identifying a set of third locations associated with the access points from the location database of the mobile device;

(c) calculating an average geographic location using the set of third locations;

(d) calculating distances between the average geographic location and third locations in the set;

(e) excluding at least one third location from the set based on a distance between the average geographic location and the at least one third location;

(f) repeating (c), (d), and (e) until an exit condition is satisfied; and

(g) designating the current location of the mobile device using a circle having the average geographic location as a center and a radius based on at least one calculated distance.

3. The method of claim 2, where excluding the at least one third location from the set includes:

determining a threshold percentage of third locations to be excluded; and

excluding the threshold percentage of third locations that are located farthest from the average geographic location.

4. The method of claim 2, where the exit condition is satisfied when a number of repetitions reaches a threshold number.

5. The method of claim 2, where the exit condition is satisfied when the radius of the circle reaches below a threshold radius.

6. The method of claim 2, where each of the third locations in the set includes a latitude, a longitude, and an altitude.

7. The method of claim 1, further comprising displaying the current location of the mobile device on a map display of the mobile device.

8. The method of claim 1, where the identifiers of the access points include Media Access Control (MAC) addresses of the access points.

9. A system, comprising:

a mobile device configured to perform operations comprising;

identifying a current access point within a communication range of which the mobile device is located;

requesting, from a server, an update of a location database of the mobile device using an identifier of the current access point, the location database storing first locations associated with first access points;

receiving a set of second locations associated with second access points, the second locations distributed in a center cell of a geographic grid and cells neighboring the center cell of the geographic grid, the current access point corresponding to a location within the center cell, the center cell and cells neighboring the center cell covering a predetermined geographic area;

updating the location database using the received set of locations; and

calculating a current location of the mobile device using the location database.

10. The system of claim 9, where calculating a current location of the mobile device using the location database comprises:

(a) receiving identifiers of access points that are within a communication range of the mobile device;

(b) identifying a set of third locations associated with the access points from the location database of the mobile device;

(c) calculating an average geographic location using the set of third locations;

(d) calculating distances between the average geographic location and third locations in the set;

(e) excluding at least one third location from the set based on a distance between the average geographic location and the at least one third location;

(f) repeating (c), (d), and (e) until an exit condition is satisfied; and

(g) designating the current location of the mobile device using a circle having the average geographic location as a center and a radius based on at least one calculated distance.

11. The system of claim 10, where excluding the at least one third location from the set includes:

determining a threshold percentage of third locations to be excluded; and

excluding the threshold percentage of third locations that are located farthest from the average geographic location.

12. The system of claim 10, where the exit condition is satisfied when a number of repetitions reaches a threshold number.

13. The system of claim 10, where the exit condition is satisfied when the radius of the circle reaches below a threshold radius.

14. The system of claim 10, where each of the third locations in the set includes a latitude, a longitude, and an altitude.

15. The system of claim 9, the operations further comprising displaying the current location of the mobile device on a map display of the mobile device.

16. The system of claim 9, where the identifiers of the access points include Media Access Control (MAC) addresses of the access points.

17. A computer program product tangibly stored on a storage device, operable to cause a mobile device to perform operations comprising:

identifying a current access point within a communication range of which the mobile device is located;

requesting, from a server, an update of a location database of the mobile device using an identifier of the current access point, the location database storing first locations associated with first access points;

receiving a set of second locations associated with second access points, the second locations distributed in a center cell of a geographic grid and cells neighboring the center cell of the geographic grid, the current access point corresponding to a location within the center cell, the center cell and cells neighboring the center cell covering a predetermined geographic area;

updating the location database using the received set of locations; and

calculating a current location of the mobile device using the location database.

18. The product of claim 17, where calculating a current location of the mobile device using the location database comprises:

(a) receiving identifiers of access points that are within a communication range of the mobile device;

(b) identifying a set of third locations associated with the access points from the location database of the mobile device;

(c) calculating an average geographic location using the set of third locations;

(d) calculating distances between the average geographic location and third locations in the set;

(e) excluding at least one third location from the set based on a distance between the average geographic location and the at least one third location;

(f) repeating (c), (d), and (e) until an exit condition is satisfied; and

(g) designating the current location of the mobile device using a circle having the average geographic location as a center and a radius based on at least one calculated distance.

19. The product of claim 18, where excluding the at least one third location from the set includes:

determining a threshold percentage of third locations to be excluded; and

excluding the threshold percentage of third locations that are located farthest from the average geographic location.

20. The product of claim 18, where the exit condition is satisfied when a number of repetitions reaches a threshold number.

21. The product of claim 18, where the exit condition is satisfied when the radius of the circle reaches below a threshold radius.

22. The product of claim 18, where each of the third locations in the set includes a latitude, a longitude, and an altitude.

23. The product of claim 17, the operations further comprising displaying the current location of the mobile device on a map display of the mobile device.

24. The product of claim 17, where the identifiers of the access points include Media Access Control (MAC) addresses of the access points.