MANAGING A LOCATION DATABASE FOR NETWORK-BASED POSITIONING SYSTEM

• US 20110176523A1
• Filed: 01/15/2010
• Published: 07/21/2011
• Est. Priority Date: 01/15/2010
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Pylappan, Seejo, Huang, Ronald K., Fischer, Markus
• Granted Patent: US 8,433,334 B2
• Time in Patent Office: Days
• US Class Current: 370/338
• CPC Class Codes: G01S 5/02 using radio waves using satellite radio beacon systems for determining position G01S19/00
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

Methods, program products, and systems for managing a location database are described. A server computer can receive location information from location-aware mobile devices (e.g., GPS-enabled devices) located within a communication range of access points of a wireless communications network. The server computer can calculate average geographic locations using the received locations for each access point. Based on the average geographic locations, the server computer can assign the access points to cells of a geographic grid. The server computer can filter the access points in each cell based on popularity, stability, longevity, and freshness of the access point and the received data. When a second mobile device connects to an access point in a cell, the server computer can transmit locations of the access points in the cell and in neighboring cells to the second mobile device such that a location of the second mobile device can be estimated.

Claims

1. A method executed by a computer, comprising:

receiving a set of locations from first mobile devices that are located within a communication range of an access point of a wireless communications network;

determining a geographic location associated with the access point based on an average of the received set of locations;

assigning the access point and the geographic location associated with the access point to a cell on a geographic grid based on a number of locations in the received set and a longevity of the locations in the received set; and

providing the geographic location associated with the access point and geographic locations of access points assigned to cells neighboring the cell on the geographic grid to a second mobile device.

2. The method of claim 1, where the access point is identified by a Media Access Control (MAC) address of the access point, the MAC address being associated with the set of locations.

3. The method of claim 1, where the wireless communications network is a Wireless Local Area Network (WLAN) using Institute of Electrical and Electronics Engineers (IEEE) 802.11 based protocols.

4. The method of claim 1, where determining the geographic location associated with the access point includes:

applying a multi-pass analysis on the received set of locations, including excluding at least one location from the set in each pass.

5. The method of claim 4, where applying the multi-pass analysis includes:

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

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

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

(d) repeating (a), (b), and (c) until an exit condition is satisfied; and

(e) designating a geographic location associated with the access point using a circle having the average geographic location as a center and a radius based on at least one calculated distance.

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

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

8. The method of claim 1, where the cell of the geographic grid includes a substantially rectangular geographic area identifiable on the geographic grid by a latitude and a longitude of an identifying point of the geographic area.

9. The method of claim 1, where the geographic grid defines a three-dimensional space, and the cell includes a three-dimensional enclosure identifiable in the geographic grid by a latitude, a longitude, and an altitude of an identifying point in the enclosure.

10. A system, comprising:

one or more computers configured to perform operations comprising;

receiving a set of locations from first mobile devices that are located within a communication range of an access point of a wireless communications network;

determining a geographic location associated with the access point based on an average of the received set of locations;

assigning the access point and the geographic location associated with the access point to a cell on a geographic grid based on a number of locations in the received set and a longevity of the locations in the received set; and

providing the geographic location associated with the access point and geographic locations of access points assigned to cells neighboring the cell on the geographic grid to a second mobile device.

11. The system of claim 10, where the access point is identified by a Media Access Control (MAC) address of the access point, the MAC address being associated with the set of locations.

12. The system of claim 10, where the wireless communications network is a Wireless Local Area Network (WLAN) using Institute of Electrical and Electronics Engineers (IEEE) 802.11 based protocols.

13. The system of claim 10, where determining the geographic location associated with the access point includes:

applying a multi-pass analysis on the received set of locations, including excluding at least one location from the set in each pass.

14. The system of claim 13, where applying the multi-pass analysis includes:

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

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

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

(d) repeating (a), (b), and (c) until an exit condition is satisfied; and

(e) designating a geographic location associated with the access point using a circle having the average geographic location as a center and a radius based on at least one calculated distance.

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

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

17. The system of claim 10, where the cell of the geographic grid includes a substantially rectangular geographic area identifiable on the geographic grid by a latitude and a longitude of an identifying point of the geographic area.

18. The system of claim 10, where the geographic grid defines a three-dimensional space, and the cell includes a three-dimensional enclosure identifiable in the geographic grid by a latitude, a longitude, and an altitude of an identifying point in the enclosure.

19. A computer program product tangibly stored on a storage device, operable to cause data processing apparatus to perform operations comprising:

receiving a set of locations from first mobile devices that are located within a communication range of an access point of a wireless communications network;

determining a geographic location associated with the access point based on an average of the received set of locations;

assigning the access point and the geographic location associated with the access point to a cell on a geographic grid based on a number of locations in the received set and a longevity of the locations in the received set; and

providing the geographic location associated with the access point and geographic locations of access points assigned to cells neighboring the cell on the geographic grid to a second mobile device.

20. The product of claim 19, where the access point is identified by a Media Access Control (MAC) address of the access point, the MAC address being associated with the set of locations.

21. The product of claim 19, where the wireless communications network is a Wireless Local Area Network (WLAN) using Institute of Electrical and Electronics Engineers (IEEE) 802.11 based protocols.

22. The product of claim 19, where determining the geographic location associated with the access point includes:

applying a multi-pass analysis on the received set of locations, including excluding at least one location from the set in each pass.

23. The product of claim 22, where applying the multi-pass analysis includes:

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

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

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

(d) repeating (a), (b), and (c) until an exit condition is satisfied; and

(e) designating a geographic location associated with the access point using a circle having the average geographic location as a center and a radius based on at least one calculated distance.

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

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

26. The product of claim 19, where the cell of the geographic grid includes a substantially rectangular geographic area identifiable on the geographic grid by a latitude and a longitude of an identifying point of the geographic area.

27. The product of claim 19, where the geographic grid defines a three-dimensional space, and the cell includes a three-dimensional enclosure identifiable in the geographic grid by a latitude, a longitude, and an altitude of an identifying point in the enclosure.