Location Estimation Using a Probability Density Function

• US 20120309428A1
• Filed: 06/03/2011
• Published: 12/06/2012
• Est. Priority Date: 06/03/2011
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Marti, Lukas M., MacGougan, Glenn Donald, Mayor, Robert, Huang, Ronald K., Dere, Jason, Grosman, Yefim
• Granted Patent: US 8,903,414 B2
• Time in Patent Office: Days
• US Class Current: 455/456.5
• 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 based on a density of received location coordinates in each of the geographic regions 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; 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, a longitude, and an altitude.

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 selecting the one or more geographic regions is based on a specified outlier threshold for identifying and excluding one or more outliers in the sets of location coordinates.

6. The method of claim 1, 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.

7. The method of claim 6, 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.

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

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

10. 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.

11. The method of claim 10, 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.

12. The method of claim 10, 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.

13. 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.

14. A computer program product stored on a non-transitory medium and 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 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; and

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

15. The product of claim 14, wherein each set of location coordinates includes a latitude, a longitude, and an altitude.

16. The product of claim 14, wherein the wireless access gateway includes at least one of a cell tower, a wireless router, or a Bluetooth™

device.

17. The product of claim 14, 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.

18. The product of claim 14, wherein selecting the one or more geographic regions is based on a specified outlier threshold for identifying and excluding one or more outliers in the sets of location coordinates.

19. The product of claim 14, 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.

20. The product of claim 19, 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.

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

22. The product of claim 19, 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.

23. The product of claim 14, the operations 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.

24. The product 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.

25. The product 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.

26. The product of claim 14, 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.

27. 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 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; and

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

28. The system of claim 27, wherein each set of location coordinates includes a latitude, a longitude, and an altitude.

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

device.

30. The system of claim 27, 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.

31. The system of claim 27, wherein selecting the one or more geographic regions is based on a specified outlier threshold for identifying and excluding one or more outliers in the sets of location coordinates.

32. The system of claim 27, 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.

33. The system of claim 32, 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.

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

35. The system of claim 32, 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.

36. The system of claim 27, the operations 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.

37. The system of claim 36, 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.

38. The system of claim 36, 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.

39. The system of claim 27, 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.