Probabilistic estimation of location based on wireless signal strength

• US 8,825,078 B1
• Filed: 08/20/2012
• Issued: 09/02/2014
• Est. Priority Date: 08/18/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Mishra, Arunesh
• Primary Examiner(s): SHEDRICK, CHARLES TERRELL
• Application Number:
  US13/589,739
• Time in Patent Office: 743 Days
• Field of Search: 455/456.1, 455/456.5, 455/456.6
• US Class Current: 455/456.1
• CPC Class Codes: G01S 5/0242 Determining the position of transmitters to be subsequently used in positioning G01S5/0289 takes precedence
• 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

According to an embodiment, a method of estimating a location of an access point is provided. The method includes storing a first and a second sample respectively received from a first and a second mobile device, both samples including a location of their respective mobile devices, an access point identifier from the access point, and a value corresponding to a signal strength of a signal from the access point measured at their respective mobile device. The cells of a matrix are populated with probabilities based on mobile device locations and the signal strength values. Finally, the location of the access point is estimated based on the matrix.

Claims

1. A method of estimating a location of an access point, comprising:

storing a first sample received from a first mobile device, the first sample including a first mobile device location, an access point identifier from the access point, and a first value corresponding to a signal strength of a signal from the access point;

populating cells of a matrix with probabilities based on the first mobile device location and the first value;

storing a second sample received from a second mobile device, the second sample including a second mobile device location, an access point identifier from the access point, and a second value corresponding to a signal strength of a signal from the access point;

updating the probabilities in the matrix based on the second mobile device location and the second value; and

estimating the location of the access point based on the matrix.

2. The method of claim 1, wherein estimating the location of the wireless access point comprises estimating the location of the wireless access point based on at least two determined probabilities, each probability associated with a different mobile device.

3. The method of claim 2, further comprising for at least two probabilities in the matrix:

analyzing the at least two probabilities; and

modifying each of the at least two probabilities based on the analyzing of the probabilities.

4. The method of claim 3, wherein analyzing the probabilities comprises, for each probability, determining a minimum probability, a maximum probability or a sum of the at least two probabilities.

5. The method of claim 1, further comprising for a sample, determining a location for another wireless access point based on an access point identifier;

and estimating a distance value for the stored first sample based on the determined another access point location and the first mobile device location value of the sample.

6. The method of claim 1, wherein storing a first sample received from a first mobile device comprises storing the first sample including a location determined by using a global positioning system determination.

7. The method of claim 1, wherein storing a first sample received from a first mobile device comprises storing the first sample including a known mobile device location.

8. A location estimator, comprising:

a sample collector configured to store in memory a plurality of samples received from a plurality of sampled mobile devices, each sample including a mobile device location, an access point location, and a signal strength; and

a probability determiner configured to determine a probability that a mobile device is a distance from an access point based on a value corresponding to the signal strength of the signal received at the mobile device from the access point, and a stored sample, wherein the access point is associated with the stored sample, and

the location estimator is configured to estimate the location of the mobile device based on at least two determined probabilities, each probability being;

determined by the probability determiner, and

associated with a different access point;

a probability analyzer configured to analyze the at least two determined probabilities; and

a probability modifier configured to modify each of the at least two determined probabilities based on the analyzed probabilities;

wherein the probability determiner, the location estimator, the probability analyzer, and the probability modifier are implemented on at least one processor device.

9. The location estimator of claim 8, wherein analyzing, by the probability analyzer, of the probabilities comprises, determining a minimum probability, a maximum probability or a sum of the at least two probabilities.

10. The location estimator of claim 8, further comprising a distance estimator configured to estimate a distance for a stored sample based on the access point location and the mobile device location values of the sample.

11. The location estimator of claim 8, wherein the sample collector is configured to store a sample having a mobile device location determined by using a global positioning system determination.

12. The location estimator of claim 8, wherein the location estimator is configured to populate cells of a matrix with the at least two determined probabilities.

13. A non-transitory computer readable storage medium having computer-executable instructions stored thereon that, when executed by a computing device, cause the computing device to perform a method of estimating a location of a mobile device, the method comprising:

storing a first sample received from a first mobile device, the first sample including a first mobile device location, an access point identifier from the wireless access point, and a first value corresponding to a signal strength of a signal from the wireless access point;

populating cells of a matrix with probabilities based on the first mobile device location, the first platform profile and the first value;

storing a second sample received from a second mobile device, the second sample including a second mobile device location, an access point identifier from the wireless access point, and a second value corresponding to a signal strength of a signal from the wireless access point;

updating the probabilities in the matrix based on the second mobile device location, the second platform profile and the second value; and

estimating the location of the wireless access point based on the matrix.

14. The non-transitory computer readable storage medium of claim 13, wherein estimating the location of the wireless access point comprises estimating the location of the wireless access point based on at least two determined probabilities, each probability associated with a different mobile device.

15. The non-transitory computer readable storage medium of claim 14, further comprising for at least two probabilities in the matrix:

analyzing the at least two probabilities; and

modifying each of the at least two probabilities based on the analyzing of the probabilities.

16. The non-transitory computer readable storage medium of claim 15, wherein analyzing the probabilities comprises, for each probability, determining a minimum probability, a maximum probability or a sum of the at least two probabilities.

17. The non-transitory computer readable storage medium of claim 13, further comprising for a sample, determining a location for another wireless access point based on an access point identifier;

and estimating a distance value for the stored first sample based on the determined another access point location and the first mobile device location value of the sample.

18. The non-transitory computer readable storage medium of claim 13, wherein storing a first sample received from a first mobile device comprises storing the first sample including a location determined by using a global positioning system determination.

19. The non-transitory computer readable storage medium of claim 13, wherein storing a first sample received from a first mobile device comprises storing the first sample including a known mobile device location.