Location estimation using a probability density function

• US 8,903,414 B2
• Filed: 06/03/2011
• Issued: 12/02/2014
• Est. Priority Date: 06/03/2011
• Status: Expired due to Fees

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Marti, Lukas M., MacGougan, Glenn Donald, Mayor, Robert, Huang, Ronald K., Dere, Jason, Grosman, Yefim
• Primary Examiner(s): KIM, WESLEY LEO
• Application Number:
  US13/153,069
• Publication Number:
  US 20120309428A1
• Time in Patent Office: 1,278 Days
• Field of Search: 455/404.1, 455/404.2, 455/414.1, 455/456.1, 342/357.43, 342/357.66, 342/450
• US Class Current: 455/456.1
• CPC Class Codes: G01S 5/0278 involving statistical or probabilistic considerations G01S5/0252, G01S5/0294 take precedence
• CPC Class Codes: H04W 64/003 locating network equipment

Abstract

Methods, program products, and systems of location estimation using a probability density function are disclosed. In general, in one aspect, a server can estimate an effective location of a wireless access gateway using harvested data. The server can harvest location data from multiple mobile devices. The harvested data can include a location of each mobile device and an identifier of a wireless access gateway that is located within a communication range of the mobile device. The server can calculate an effective location of the wireless access gateway using a probability density function of the harvested data. The probability density function can be a sufficient statistic of the received set of location coordinates for calculating an effective location of the wireless access gateway. The server can send the effective location of the wireless access gateway to other mobile devices for estimating locations of the other mobile devices.

Claims

1. A method performed by one or more computers, comprising:

receiving a plurality of sets of location coordinates from one or more mobile devices, each set of location coordinates being associated with a wireless access gateway;

mapping the sets of location coordinates to a plurality of geographic regions;

selecting one or more geographic regions from the plurality of geographic regions, wherein selecting the one or more geographic regions comprises;

determining, for each geographic region and using a probability density function, an expected value based on a relative probability that a received set of location coordinates is located within the geographic region, the probability density function including a sufficient statistic of the received set of location coordinates for calculating an effective location of the wireless access gateway; and

selecting the one or more geographic regions upon determining that a measurement of the expected value corresponding to the one or more geographic regions satisfies an outlier threshold; and

determining the effective location of the wireless access gateway using sets of location coordinates in the selected one or more geographic regions.

2. The method of claim 1, wherein each set of location coordinates includes a latitude coordinate, a longitude coordinate, and an altitude coordinate.

3. The method of claim 1, wherein the wireless access gateway includes at least one of a cell tower, a wireless router, or a Bluetooth™

device.

4. The method of claim 1, wherein each geographic region is a bin of a geographic grid comprising multiple bins, the geographic grid being a geographic area associated with the wireless access gateway.

5. The method of claim 1, wherein each set of the location coordinates is associated with a weight, the weight indicating a degree of certainty of the set of location coordinates;

and

determining the expected value includes determining the expected value based on the relative probability and the weight.

6. The method of claim 5, comprising determining the weight based on at least one of a received signal strength indication (RSSI) or a bit error rate.

7. The method of claim 1, comprising determining that the measurement satisfies the outlier threshold when a sum of the corresponding expected value equals one minus the outlier threshold.

8. The method of claim 1, comprising:

selecting one or more sets of location coordinates from the selected one or more geographic regions based on an estimated movement of the wireless access gateway, wherein determining the effective location of the wireless access gateway includes determining the effective location of the wireless access gateway using the selected sets of location coordinates.

9. The method of claim 8, wherein selecting one or more sets of location coordinates from the selected one or more geographic regions based on the estimated movement of the wireless access gateway comprises:

determining that at least one set of location coordinates is obsolete when a variation of sets of location coordinates exceeds a threshold, indicating that the wireless access gateway has moved; and

selecting the one or more sets of location coordinates by excluding the obsolete set of location coordinates.

10. The method of claim 8, wherein:

each set of location coordinates corresponds to a time of measurement; and

selecting the one or more sets of location coordinates comprises excluding a collection of one or more sets of location coordinates in a geographic region when a span of the corresponding time of measurements of the sets in the collection satisfies a threshold time.

11. The method of claim 1, comprising sending the effective location of the wireless access gateway to a mobile device located within a communication range of the wireless access gateway for determining a location of the mobile device.

12. A non-transitory medium storing a computer program product configured to cause one or more computers to perform operations comprising:

receiving a plurality of sets of location coordinates from one or more mobile devices, each set of location coordinates being associated with a wireless access gateway;

mapping the sets of location coordinates to a plurality of geographic regions;

selecting one or more geographic regions from the plurality of geographic regions based on a density of received location coordinates in each of the geographic regions represented using a probability density function, the probability density function including a sufficient statistic of the received set of location coordinates for calculating an effective location of the wireless access gateway;

selecting one or more sets of location coordinates from the selected one or more geographic regions based on an estimated movement of the wireless access gateway; and

determining the effective location of the wireless access gateway using the one or more sets of location coordinates.

13. The non-transitory medium of claim 12, wherein each set of location coordinates includes a latitude coordinate, a longitude coordinate, and an altitude coordinate.

14. The non-transitory medium of claim 12, wherein the wireless access gateway includes at least one of a cell tower, a wireless router, or a Bluetooth ™

device.

15. The non-transitory medium of claim 12, wherein each geographic region is a bin of a geographic grid comprising multiple bins, the geographic grid being a geographic area associated with the wireless access gateway.

16. The non-transitory medium of claim 12, wherein selecting the one or more geographic regions comprises:

determining, for each geographic region and using the probability density function, an expected value based on a relative probability that a received set of location coordinates is located within the geographic region; and

selecting the one or more geographic regions when a measurement of the expected value corresponding to the one or more geographic regions satisfies an outlier threshold.

17. The non-transitory medium of claim 16, wherein

each set of the location coordinates is associated with a weight, the weight indicating a degree of certainty of the set of location coordinates;

and

determining the expected value includes determining the expected value based on the relative probability and the weight.

18. The non-transitory medium of claim 17, the operations comprising determining the weight based on at least one of a received signal strength indication (RSSI) or a bit error rate.

19. The non-transitory medium of claim 16, the operations comprising determining that the measurement satisfies the outlier threshold when a sum of the corresponding expected value equals one minus the outlier threshold.

20. The product of claim 12, wherein selecting one or more sets of location coordinates from the selected one or more geographic regions based on the estimated movement of the wireless access gateway comprises:

determining that at least one set of location coordinates is obsolete when a variation of sets of location coordinates exceeds a threshold, indicating that the wireless access gateway has moved; and

selecting the one or more sets of location coordinates by excluding the obsolete set of location coordinates.

21. The product of claim 12, wherein:

each set of location coordinates corresponds to a time of measurement; and

selecting the one or more sets of location coordinates comprises excluding a collection of one or more sets of location coordinates in a geographic region when a span of the corresponding time of measurements of the sets in the collection satisfies a threshold time.

22. The product of claim 12, the operations comprising sending the effective location of the wireless access gateway to a mobile device located within a communication range of the wireless access gateway for determining a location of the mobile device.

23. A system, comprising:

one or more computers configured to perform operations comprising;

receiving a plurality of sets of location coordinates from one or more mobile devices, each set of location coordinates being associated with a wireless access gateway;

mapping the sets of location coordinates to a plurality of geographic regions;

selecting one or more geographic regions from the plurality of geographic regions based on;

a density of received location coordinates in each of the geographic regions represented using a probability density function, the probability density function including a sufficient statistic of the received set of location coordinates for calculating an effective location of the wireless access gateway

selecting one or more sets of location coordinates from the selected one or more geographic regions based on an estimated movement of the wireless access gateway; and

determining the effective location of the wireless access gateway using the one or more sets of location coordinates.

24. The system of claim 23, wherein each set of location coordinates includes a latitude coordinate, a longitude coordinate, and an altitude coordinate.

25. The system of claim 23, wherein the wireless access gateway includes at least one of a cell tower, a wireless router, or a Bluetooth™

device.

26. The system of claim 23, wherein each geographic region is a bin of a geographic grid comprising multiple bins, the geographic grid being a geographic area associated with the wireless access gateway.

27. The system of claim 23, wherein selecting the one or more geographic regions comprises:

determining, for each geographic region and using the probability density function, an expected value based on a relative probability that a received set of location coordinates is located within the geographic region; and

selecting the one or more geographic regions when a measurement of the expected value corresponding to the one or more geographic regions satisfies an outlier threshold.

28. The system of claim 27, wherein

each set of the location coordinates is associated with a weight, the weight indicating a degree of certainty of the set of location coordinates;

and

determining the expected value includes determining the expected value based on the relative probability and the weight.

29. The system of claim 28, the operations comprising determining the weight based on at least one of a received signal strength indication (RSSI) or a bit error rate.

30. The system of claim 27, the operations comprising determining that the measurement satisfies the outlier threshold when a sum of the corresponding expected value equals one minus the outlier threshold.

31. The system of claim 23, wherein selecting one or more sets of location coordinates from the selected one or more geographic regions based on the estimated movement of the wireless access gateway comprises:

determining that at least one set of location coordinates is obsolete when a variation of sets of location coordinates exceeds a threshold, indicating that the wireless access gateway has moved; and

selecting the one or more sets of location coordinates by excluding the obsolete set of location coordinates.

32. The system of claim 23, wherein:

each set of location coordinates corresponds to a time of measurement; and

selecting the one or more sets of location coordinates comprises excluding a collection of one or more sets of location coordinates in a geographic region when a span of the corresponding time of measurements of the sets in the collection satisfies a threshold time.

33. The system of claim 23, the operations comprising sending the effective location of the wireless access gateway to a mobile device located within a communication range of the wireless access gateway for determining a location of the mobile device.