Location determination using cached location area codes

• US 8,655,371 B2
• Filed: 01/15/2010
• Issued: 02/18/2014
• Est. Priority Date: 01/15/2010
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Huang, Ronald K.
• Primary Examiner(s): SAMS, MATTHEW C
• Application Number:
  US12/688,805
• Publication Number:
  US 20110177825A1
• Time in Patent Office: 1,495 Days
• Field of Search: 4554561-457, 701/300, 701482-485, 701/469, 701/573, 3423572-35778, 342450-463
• US Class Current: 455/456.1
• CPC Class Codes: G01S 5/0295 Proximity-based methods, e.g. position inferred from reception of particular signals
• 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 location determination using cached location area codes are described. A server computer can receive location information from location-aware mobile devices (e.g., GPS-enabled devices) located in a location area of a cellular communications network. The server computer can also receive from the mobile device the location area code associated with the location area in which the mobile devices are located. The server computer can estimate a coarse geographic location of the location area, as well as a number of cells encompassed by the location area using the received information. The server computer can store the estimated geographic locations associated with sufficiently large location areas (e.g., location areas having more than a certain number of cells). The server computer can provide the stored geographic locations to second mobile devices that are not GPS-enabled for estimating current locations of the second mobile devices.

Claims

1. A method executed by a computer, comprising:

receiving, from a set of first mobile devices;

at least one location area code (LAC) of a cellular communications network, wherein each LAC is associated with a unique location area;

cell identifiers of the cellular communication network; and

a set of geographic locations of the set of first mobile devices, each of the geographic locations corresponding to one of the first mobile devices;

calculating an estimated size of the location area of each received LAC, the estimated size being represented as an estimated number of cells included in the location area, wherein the estimated number of cells is determined based on the cell identifiers received from the set of first mobile devices;

selecting at least one LAC based on the estimated size of the location area of the LAC reaching or exceeding a specified threshold;

determining, for each selected LAC, an estimated LAC location of the selected LAC using the set of geographic locations;

associating each selected LAC with the estimated LAC location based on the determining; and

providing at least one selected LAC and the estimated LAC location associated with the at least one selected LAC to a second mobile device for estimating a current location of the second mobile device.

2. The method of claim 1, where the geographic locations comprise an altitude coordinate.

3. The method of claim 1, where selecting the LAC comprises:

ranking the at least one LAC based on the estimated size of the LAC; and

selecting LACs that are top-ranked.

4. The method of claim 1, where the geographic locations comprise latitude and longitude coordinates.

5. The method of claim 1, where determining the estimated LAC location comprises:

calculating an average geographic location using the set of locations;

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

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

repeating the operations of calculating the average geographic location, calculating the distances, and excluding at least one geographic location until an exit condition is satisfied; and

designating as the LAC location 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 reach a threshold number.

7. The method of claim 5, where excluding the at least one location from the set includes:

determining a threshold distance to the average geographic location within which a percentage of the locations in the set are located; and

excluding the at least one location from the set when the distance between the average geographic location and the at least one location exceeds the threshold distance.

8. A system, comprising:

one or more computers configured to perform operations comprising;

receiving, from a set of first mobile devices;

at least one location area code (LAC) of a cellular communications network, wherein each LAC is associated with a unique location area;

cell identifiers of the cellular communication network; and

a set of geographic locations of the set of first mobile devices, each of the geographic locations corresponding to one of the first mobile devices;

calculating an estimated size location area of each received LAC, the estimated size being represented as a number of cells included in the location area, wherein the estimated number of cells is determined based on the cell identifiers received from the set of first mobile devices;

selecting at least one LAC based on the estimated size of the location area of the LAC reaching or exceeding a specified threshold;

determining, for each selected LAC, an estimated LAC location of the selected LAC using the set of geographic locations;

associating each selected LAC with the estimated LAC location based on the determining; and

providing at least one selected LAC and the estimated LAC location associated with the at least one selected LAC to a second mobile device for estimating a current location of the second mobile device.

9. The system of claim 8, where the geographic locations comprise an altitude coordinate.

10. The system of claim 8, where selecting the LAC comprises:

ranking the at least one LAC based on the estimated size of the LAC; and

selecting LACs that are top-ranked.

11. The system of claim 8, where the geographic locations comprise latitude and longitude coordinates.

12. The system of claim 8, where determining the estimated LAC location comprises:

calculating an average geographic location using the set of locations;

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

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

repeating the operations of calculating the average geographic location, calculating the distances, and excluding at least one geographic location until an exit condition is satisfied; and

designating as the LAC location a circle having the average geographic location as a center and a radius based on at least one calculated distance.

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

14. The system of claim 12, where excluding the at least one location from the set includes:

determining a threshold distance to the average geographic location within which a percentage of the locations in the set are located; and

excluding the at least one location from the set when the distance between the average geographic location and the at least one location exceeds the threshold distance.

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

receiving, from a set of first mobile device;

at least one location area code (LAC) of a cellular communications network, wherein each LAC is associated with a unique location area;

cell identifiers of the cellular communication network; and

a set of geographic locations of the set of first mobile devices, each of the geographic locations corresponding to one of the first mobile devices;

calculating an estimated size of the location area of each received LAC, the estimated size being represented as a number of cells included in the location area, wherein the estimated number of cells is determined based on the cell identifiers received from the set of first mobile devices;

selecting at least one LAC based on the estimated size of the location area of the LAC reaching or exceeding a specified threshold;

determining, for each selected LAC an estimated LAC location of the selected LAC using the set of geographic locations;

associating each selected LAC with the estimated LAC location based on the determining; and

providing at least one selected LAC and the estimated LAC location associated with the at least one selected LAC to a second mobile device for estimating a current location of the second mobile device.

16. The product of claim 15, where the geographic locations comprise an altitude coordinate.

17. The product of claim 15, where selecting the LAC comprises:

ranking the at least one LAC based on the estimated size of the LAC; and

selecting LACs that are top-ranked.

18. The product of claim 15, where the geographic locations comprise latitude and longitude coordinates.

19. The product of claim 15, where determining the estimated LAC location comprises:

calculating an average geographic location using the set of locations;

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

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

repeating the operations of calculating the average geographic location, calculating the distances, and excluding at least one geographic location until an exit condition is satisfied; and

designating as the LAC location a circle having the average geographic location as a center and a radius based on at least one calculated distance.

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

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

determining a threshold distance to the average geographic location within which a percentage of the locations in the set are located; and

excluding the at least one location from the set when the distance between the average geographic location and the at least one location exceeds the threshold distance.