Managing a location database for network-based positioning system

• US 8,433,334 B2
• Filed: 01/15/2010
• Issued: 04/30/2013
• Est. Priority Date: 01/15/2010
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Huang, Ronald K., Fischer, Markus, Pylappan, Seejo
• Primary Examiner(s): SAMS, MATTHEW C
• Application Number:
  US12/688,806
• Publication Number:
  US 20110176523A1
• Time in Patent Office: 1,201 Days
• Field of Search: 4554561-457, 701/214, 701/469, 3423572-35778, 342450-463
• US Class Current: 455/456.1
• 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 plurality of sets of locations from first mobile devices that are each located within a communication range of an access point of a wireless communications network, each set of locations corresponding to a distinct access point;

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

assigning the geographic location associated with each access point to a cell on a geographic grid;

for each cell on the geographic grid, ranking geographic locations assigned to the cell based on a number of locations in the received set of the corresponding access point, wherein a geographic location corresponding to an access point associated with a larger set of locations receives a higher ranking;

filtering the geographic locations assigned to each cell, including preserving a group of one or more of geographic locations that include the highest ranking geographic location for the cell; 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 connected to the access point.

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 1, where ranking geographic locations assigned to each cell is further based on at least one of a stability, a longevity, or a freshness of locations in the set associated to each of the access points corresponding to each geographic location.

6. The method of claim 5, where the stability of an access point corresponds to a stability of the geographic location associated with the access point as determined at different time, the longevity of an access point corresponds to a length of time the access point has existed, and the freshness of the access point corresponds to a latest location received from a first device that is located within communication range of the access point.

7. The method of claim 1, where the providing occurs upon detecting that the second mobile device is moving out of a geographic area.

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 plurality of sets of locations from first mobile devices that are each located within a communication range of an access point of a wireless communications network, each set of locations corresponding to a distinct access point;

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

assigning the geographic location associated with each access point to a cell on a geographic grid;

for each cell on the geographic grid, ranking geographic locations assigned to the cell based on a number of locations in the received set of the corresponding access point, wherein a geographic location corresponding to an access point associated with a larger set of locations receives a higher ranking;

filtering the geographic locations assigned to each cell, including preserving a group of one or more of geographic locations that include the highest ranking geographic location for the cell; 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 connected to the access point.

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 10, where ranking geographic locations assigned to each cell is further based on at least one of a stability, a longevity, or a freshness of locations in the set associated to each of the access points corresponding to each geographic location.

15. The system of claim 14, where the stability of an access point corresponds to a stability of the geographic location associated with the access point as determined at different time, the longevity of an access point corresponds to a length of time the access point has existed, and the freshness of the access point corresponds to a latest location received from a first device that is located within communication range of the access point.

16. The system of claim 10, where the providing occurs upon detecting that the second mobile device is moving out of a geographic area.

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 plurality of sets of locations from first mobile devices that are within a communication range of an access point of a wireless communications network, where each set of locations corresponding to a distinct access point;

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

assigning the geographic location associated with each access point to a cell on a geographic grid;

for each cell on the geographic grid, ranking geographic locations assigned to the cell based on a number of locations in the received set of the corresponding access point, wherein a geographic location corresponding to an access point associated with a larger set of locations receives a higher ranking;

filtering the geographic locations assigned to each cell, including preserving a group of one or more of geographic locations that include the highest ranking geographic location for the cell; 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 connected to the access point.

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 19, where ranking geographic locations assigned to each cell is further based on at least one of a stability, a longevity, or a freshness of locations in the set associated to each of the access points corresponding to each geographic location.

24. The product of claim 23, where the stability of an access point corresponds to a stability of the geographic location associated with the access point as determined at different time, the longevity of an access point corresponds to a length of time the access point has existed, and the freshness of the access point corresponds to a latest location received from a first device that is located within communication range of the access point.

25. The product of claim 19, where the providing occurs upon detecting that the second mobile device is moving out of a geographic area.

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.