Location fingerprinting

• US 8,977,298 B2
• Filed: 12/14/2012
• Issued: 03/10/2015
• Est. Priority Date: 12/14/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Marti, Lukas M., Mayor, Robert, Ma, Shannon M.
• Primary Examiner(s): Sarwar, Babar
• Application Number:
  US13/715,556
• Publication Number:
  US 20140171118A1
• Time in Patent Office: 816 Days
• Field of Search: 455/425, 455/456.1, 455/456.3, 455/456.6, 455/404.2, 455/420, 455/421, 455/433, 455/456.5
• US Class Current: 455/456.3
• CPC Class Codes: G01S 5/0252 Radio frequency fingerprinting
• CPC Class Codes: G01S 5/0278 involving statistical or probabilistic considerations G01S5/0252, G01S5/0294 take precedence
• CPC Class Codes: G01S 5/0294 Trajectory determination or predictive filtering, e.g. target tracking or Kalman filtering
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/38 for collecting sensor information

Abstract

Methods, program products, and systems for using a location fingerprint database to determine a location of a mobile device are described. A mobile device can use a location fingerprint database to determine the location where GPS signals are unavailable. A server can generate location fingerprint data for the database. The server can generate the location fingerprint data using crowd sourcing, using known locations of signal sources, or both. The server can receive, from a sampling device, measurements of environment variables, e.g., signals from a signal source at one or more sampling points. The server can extrapolate, from the received measurements, estimated measurements at one or more locations in a venue. The server can store the extrapolated measurements as location fingerprint data. The server can send the location fingerprint data to a mobile device for determining a location of the mobile device when the mobile device is at the venue.

Claims

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

identifying one or more environment variables to be associated with a venue, each environment variable measuring a signal, the venue comprising a space accessible by a pedestrian and one or more constraints of movement of the pedestrian;

determining a plurality of locations where the signal is detectable by a sensor of a mobile device when the mobile device is located at the venue, the locations being locations at the venue that are accessible by the mobile device and being different from a location of a signal source that produces the signal;

determining location fingerprint data for the venue, the location fingerprint data comprising a fingerprint for each of the locations, the fingerprint including a set of one or more measurements that the mobile device is expected to receive when the mobile device measures the signal at the corresponding location, each measurement in the fingerprint corresponding to a different signal source, the location fingerprint data having a multi-dimensional data structure including an environment variable dimension and a location dimension, wherein;

the environment variable dimension of the location fingerprint data corresponds to the one or more environment variables;

the location dimension of the location fingerprint data corresponds to coordinates of the one or more locations; and

one or more values in the location fingerprint data at a given location and given environment variable corresponds to a probability distribution that includes an expected value and a variance of the environment variable at the given location; and

providing the location fingerprint data and an identifier of the venue to the mobile device for determining a location of the mobile device at the venue.

2. The method of claim 1, wherein:

each environment variable corresponds to a signal source, the signal source including at least one of a wireless access point, a light source, a sound source, a magnetic source, or a heat source,

each of the measurements includes at least one of a received signal strength indication (RSSI), a round-trip time, a magnetic field strength, a temperature, a sound level, or an air pressure level, and

identifying the one or more environment variables comprises receiving an identifier of each signal source from a sampling device.

3. The method of claim 2, wherein determining the locations where the signal is detectable comprises identifying, using a map of the venue, the locations from the space accessible by the pedestrian.

4. The method of claim 1, wherein the location dimension comprises a longitude sub-dimension, a latitude sub-dimension, and an altitude sub-dimension.

5. The method of claim 1, wherein determining the location fingerprint data comprises generating the location fingerprint data based on a survey the venue.

6. The method of claim 5, wherein determining the location fingerprint data comprises:

receiving, from a sampling device, measurements of signals from one or more signal sources at one or more sampling locations;

extrapolating an estimated measurement of the environment variables at each of the locations from the measurement of signals at the one or more sampling locations; and

generating the location fingerprint data based on the received measurements, the extrapolated measurements, and the corresponding locations.

7. The method of claim 6, wherein extrapolating the estimated measurement comprises determining an attenuation of the measurements of signals based on the constraints, wherein the constraints comprise one or more walls, floors, or columns.

8. The method of claim 1, comprising determining the location fingerprint data by prediction.

9. The method of claim 8, wherein determining the location fingerprint data by prediction comprises:

receiving location coordinates of a signal source;

determining transmission characteristics of the signal source;

for each of the locations, determining an expected measurement and variance of a signal from the signal source based on a location of the signal source, spaces and barriers between the signal source and the location, an estimated propagation pattern of the signal from the signal source in the spaces, and an estimated propagation pattern of the signal from the signal source in the barriers; and

storing the expected measurements, the variance, an identifier of the signal source, and the corresponding location as the location fingerprint data.

10. The method of claim 1, wherein providing the location fingerprint data to the mobile device occurs upon an entrance of the mobile device into the venue.

11. A non-transitory storage device storing instructions operable to cause one or more computers to perform operations comprising:

identifying one or more environment variables to be associated with a venue, each environment variable measuring a signal, the venue comprising a space accessible by a pedestrian and one or more constraints of movement of the pedestrian;

determining a plurality of locations where the signal is detectable by a sensor of a mobile device when the mobile device is located at the venue, the locations being locations at the venue that are accessible by the mobile device and being different from a location of a signal source that produces the signal;

determining location fingerprint data for the venue, the location fingerprint data comprising a fingerprint for each of the locations, the fingerprint including a set of one or more measurements that the mobile device is expected to receive when the mobile device measures the signal at the corresponding location, each measurement in the fingerprint corresponding to a different signal source, the location fingerprint data having a multi-dimensional data structure including an environment variable dimension and a location dimension, wherein;

the environment variable dimension of the location fingerprint data corresponds to the one or more environment variables;

the location dimension of the location fingerprint data corresponds to coordinates of the one or more locations; and

one or more values in the location fingerprint data at a given location and given environment variable corresponds to a probability distribution that includes an expected value and a variance of the environment variable at the given location; and

providing the location fingerprint data and an identifier of the venue to the mobile device for determining a location of the mobile device at the venue.

12. The non-transitory storage device of claim 11, wherein:

each environment variable corresponds to a signal source, the signal source including at least one of a wireless access point, a light source, a sound source, a magnetic source, or a heat source,

each of the measurements includes at least one of a received signal strength indication (RSSI), a round-trip time, a magnetic field strength, a temperature, a sound level, or an air pressure level, and

identifying the one or more environment variables comprises receiving an identifier of each signal source from a sampling device.

13. The non-transitory storage device of claim 12, wherein determining the locations where the signal is detectable comprises identifying, using a map of the venue, the locations from the space accessible by the pedestrian.

14. The non-transitory storage device of claim 11, wherein the location dimension comprises a longitude sub-dimension, a latitude sub-dimension, and an altitude sub-dimension.

15. The non-transitory storage device of claim 11, wherein determining the location fingerprint data comprises generating the location fingerprint data based on a survey the venue.

16. The non-transitory storage device of claim 15, wherein determining the location fingerprint data comprises:

receiving, from a sampling device, measurements of signals from one or more signal sources at one or more sampling locations;

extrapolating an estimated measurement of the environment variables at each of the locations from the measurement of signals at the one or more sampling locations; and

generating the location fingerprint data based on the received measurements, the extrapolated measurements, and the corresponding locations.

17. The non-transitory storage device of claim 16, wherein extrapolating the estimated measurement comprises determining an attenuation of the measurements of signals based on the constraints, wherein the constraints comprise one or more walls, floors, or columns.

18. The non-transitory storage device of claim 11, the operations comprising determining the location fingerprint data by prediction.

19. The non-transitory storage device of claim 18, wherein determining the location fingerprint data by prediction comprises:

receiving location coordinates of a signal source;

determining transmission characteristics of the signal source;

for each of the locations, determining an expected measurement and variance of a signal from the signal source based on a location of the signal source, spaces and barriers between the signal source and the location, an estimated propagation pattern of the signal from the signal source in the spaces, and an estimated propagation pattern of the signal from the signal source in the barriers; and

storing the expected measurements, the variance, an identifier of the signal source, and the corresponding location as the location fingerprint data.

20. The non-transitory storage device of claim 11, wherein providing the location fingerprint data to the mobile device occurs upon an entrance of the mobile device into the venue.

21. A system comprising:

one or more computers; and

a non-transitory storage device storing instructions operable to cause the one or more computers to perform operations comprising

identifying one or more environment variables to be associated with a venue, each environment variable measuring a signal, the venue comprising a space accessible by a pedestrian and one or more constraints of movement of the pedestrian;

determining a plurality of locations where the signal is detectable by a sensor of a mobile device when the mobile device is located at the venue, the locations being locations at the venue that are accessible by the mobile device and being different from a location of a signal source that produces the signal;

determining location fingerprint data for the venue, the location fingerprint data comprising a fingerprint for each of the locations, the fingerprint including a set of one or more measurements that the mobile device is expected to receive when the mobile device measures the signal at the corresponding location, each measurement in the fingerprint corresponding to a different signal source, the location fingerprint data having a multi-dimensional data structure including an environment variable dimension and a location dimension, wherein;

the environment variable dimension of the location fingerprint data corresponds to the one or more environment variables;

the location dimension of the location fingerprint data corresponds to coordinates of the one or more locations; and

one or more values in the location fingerprint data at a given location and given environment variable corresponds to a probability distribution that includes an expected value and a variance of the environment variable at the given location; and

providing the location fingerprint data and an identifier of the venue to the mobile device for determining a location of the mobile device at the venue.

22. The system of claim 21, wherein:

each environment variable corresponds to a signal source, the signal source including at least one of a wireless access point, a light source, a sound source, a magnetic source, or a heat source,

each of the measurements includes at least one of a received signal strength indication (RSSI), a round-trip time, a magnetic field strength, a temperature, a sound level, or an air pressure level, and

identifying the one or more environment variables comprises receiving an identifier of each signal source from a sampling device.

23. The system of claim 22, wherein determining the locations where the signal is detectable comprises identifying, using a map of the venue, the locations from the space accessible by the pedestrian.

24. The system of claim 21, wherein the location dimension comprises a longitude sub-dimension, a latitude sub-dimension, and an altitude sub-dimension.

25. The system of claim 21, wherein determining the location fingerprint data comprises generating the location fingerprint data based on a survey the venue.

26. The system of claim 25, wherein determining the location fingerprint data comprises:

receiving, from a sampling device, measurements of signals from one or more signal sources at one or more sampling locations;

extrapolating an estimated measurement of the environment variables at each of the locations from the measurement of signals at the one or more sampling locations; and

generating the location fingerprint data based on the received measurements, the extrapolated measurements, and the corresponding locations.

27. The system of claim 26, wherein extrapolating the estimated measurement comprises determining an attenuation of the measurements of signals based on the constraints, wherein the constraints comprise one or more walls, floors, or columns.

28. The system of claim 21, operations comprising determining the location fingerprint data by prediction.

29. The system of claim 28, wherein determining the location fingerprint data by prediction comprises:

receiving location coordinates of a signal source;

determining transmission characteristics of the signal source;

for each of the locations, determining an expected measurement and variance of a signal from the signal source based on a location of the signal source, spaces and barriers between the signal source and the location, an estimated propagation pattern of the signal from the signal source in the spaces, and an estimated propagation pattern of the signal from the signal source in the barriers; and

storing the expected measurements, the variance, an identifier of the signal source, and the corresponding location as the location fingerprint data.

30. The system of claim 21, wherein providing the location fingerprint data to the mobile device occurs upon an entrance of the mobile device into the venue.