Location fingerprinting for transit systems

• US 9,758,183 B2
• Filed: 09/30/2014
• Issued: 09/12/2017
• Est. Priority Date: 09/30/2014
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Millman, David Benjamin, Bergerengen, Johan Olav, Mayor, Robert, Smith, Brian Stephen
• Primary Examiner(s): MOTT, ADAM R
• Application Number:
  US14/502,653
• Publication Number:
  US 20160091593A1
• Time in Patent Office: 1,078 Days
• CPC Class Codes: B61L 15/0027 Radio-based, e.g. using GSM-R
• CPC Class Codes: B61L 25/025 Absolute localisation, e.g. providing geodetic coordinates
• CPC Class Codes: B61L 27/70 Details of trackside communication
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01S 5/02522 The radio-map containing measured values of non-radio values
• CPC Class Codes: G01S 5/02524 Creating or updating the radio-map
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/024 Guidance services
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• 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 building a location fingerprint database for a transit system are described. The transit system can be a subway system including underground train stations and routes where location determination using GPS signals is difficult or impossible. A sampling device can measure signals, e.g., radio frequency (RF) signals detected at the stations or on the routes. A location server can construct a location fingerprint for each of the stations and the routes. Each location fingerprint can represent expected signal measurements by a user device if the user device is located at the respective station or route. The location server can provide the location fingerprint to a user device for the user device to determine a location of the user device within the station or on the route.

Claims

1. A method comprising:

receiving, by one or more computer processors and from a sampling device, a plurality of sensor readings, each of the sensor readings corresponding to a reading of an attribute of an environment at a portion of a transit system, the portion comprising a station of the transit system or at least a portion of a route of the transit system,

the sensor readings including measurements of strength of radio frequency (RF) signals of signal sources that are detectable at the portion of the transit system, each measurement of strength being associated with a respective identifier of a corresponding signal source;

the sensor readings also including accelerometer readings from the sampling device;

identifying, among the sensor readings, received signal strength indication peaks each associated with a respective corresponding signal source, at least two of the received signal strength indication peaks being associated with a temporal distance;

determining, based on at least a portion of the accelerometer readings, that acceleration along a travel direction of the sampling device meets a threshold of detectable acceleration;

accounting for the acceleration along the travel direction of the sampling device by calculating an adjusted temporal distance between the two received signal strength indication peaks;

determining, from the sensor readings, an environment profile for the portion of the transit system, the environment profile comprising a distribution of frequency of a number of occurrences of each particular value among the sensor readings over values of the readings;

determining, from the sensor readings, whether the environment profile corresponds to a station of the transit system or a moving vehicle of the transit system;

determining, from the environment profile, a location fingerprint for the portion of the transit system, the location fingerprint comprising projected readings of sensors of a mobile device when the mobile device is located at the portion of the transit system; and

providing the location fingerprint to a user device for determining a location of the user device when the user device is in the transit system.

2. The method of claim 1, wherein:

the transit system is a subway system where signals from a global positioning satellite system are unavailable or inaccurate for location determination, and

the sensor readings received by the sampling device include readings from at least one of an accelerometer, a magnetometer, a barometer, a gyroscope, a light sensor, a sound pressure sensor, or a radio receiver coupled to the sampling device.

3. The method of claim 1, wherein:

at least one of the signal sources includes a cell site of a cellular communications network, a wireless access point, or a Bluetooth™

low energy (BLE) beacon.

4. The method of claim 1, wherein:

the portion of the transit system comprises a plurality of platforms of the station of the transit system,

the sensor readings comprise a plurality of measurements taken at each of the platforms and associated with an identifier of the station and an identifier of the platform where the measurements are taken.

5. The method of claim 1, wherein:

the portion of the transit system comprises a section of a rail of the transit system; and

each of the sensor readings is associated with a tag indicating whether a surveyor carrying the sampling device is in a train and remains stationary relative to the train, whether the surveyor is walking on the train, whether the train is moving along the rail, whether the train is accelerating or decelerating, and whether the train has stopped at a station.

6. The method of claim 1, wherein the environment profile is representable by at least one of:

a discrete representation of one or more histograms each corresponding to a signal source, each histogram having bins of measured signal strengths of the corresponding signal source and frequencies corresponding to occurrences of measurements at each signal strength, or

a continuous probability density representation.

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

determining, from each histogram in the environment profile, a number of modes, each mode corresponding to a local maximum number of occurrences at a corresponding signal strength measured from the corresponding signal source;

selecting an algorithm optimized for single mode statistical filtering upon determining that the histogram has one mode, or selecting an algorithm optimized for multimode statistical filtering upon determining that the histogram has a plurality of modes; and

determining the location fingerprint at least in part by applying the selected algorithm to the respective histogram.

8. The method of claim 1, wherein the location fingerprint is associated with an identifier of an operator of the transit system and at least one of a name of the station or geographic coordinates of a portion of the route.

9. The method of claim 8 wherein providing the location fingerprint to a user device comprises:

receiving a request from the user device for location fingerprint data of the transit system, the request includes the identifier of the operator of the transit system; and

in response to the request, providing the location fingerprint to the user device.

10. A system comprising:

a mobile device;

a non-transitory computer-readable medium storing instructions operable to cause the mobile device to perform operations comprising;

receiving, by one or more computer processors and from a sampling device, a plurality of sensor readings, each of the sensor readings corresponding to a reading of an attribute of an environment at a portion of a transit system, the portion comprising a station of the transit system or at least a portion of a route of the transit system,

the sensor readings including measurements of strength of radio frequency (RF) signals of signal sources that are detectable at the portion of the transit system, each measurement of strength being associated with a respective identifier of a corresponding signal source;

the sensor readings also including accelerometer readings from the sampling device;

identifying, among the sensor readings, received signal strength indication peaks each associated with a respective corresponding signal source, at least two of the received signal strength indication peaks being associated with a temporal distance;

determining, based on at least a portion of the accelerometer readings, that acceleration along a travel direction of the sampling device meets a threshold of detectable acceleration;

accounting for the acceleration along the travel direction of the sampling device by calculating an adjusted temporal distance between the two received signal strength indication peaks;

determining, from the sensor readings, an environment profile for the portion of the transit system, the environment profile comprising a distribution of frequency of a number of occurrences of each particular value among the sensor readings over values of the readings;

determining, from the sensor readings, whether the environment profile corresponds to a station of the transit system or a moving vehicle of the transit system;

determining, from the environment profile, a location fingerprint for the portion of the transit system, the location fingerprint comprising projected readings of sensors of a mobile device when the mobile device is located at the portion of the transit system; and

providing the location fingerprint to a user device for determining a location of the user device when the user device is in the transit system.

11. The system of claim 10, wherein:

the transit system is a subway system where signals from a global positioning satellite system are unavailable or inaccurate for location determination, and

the sensor readings received by the sampling device include readings from at least one of an accelerometer, a magnetometer, a barometer, a gyroscope, a light sensor, a sound pressure sensor, or a radio receiver coupled to the sampling device.

12. The system of claim 10, wherein:

at least one of the signal sources includes a cell site of a cellular communications network, a wireless access point, or a Bluetooth™

low energy (BLE) beacon.

13. The system of claim 10, wherein:

the portion of the transit system comprises a plurality of platforms of the station of the transit system,

the sensor readings comprise a plurality of measurements taken at each of the platforms and associated with an identifier of the station and an identifier of the platform where the measurements are taken.

14. The system of claim 10, wherein:

the portion of the transit system comprises a section of a rail of the transit system; and

each of the sensor readings is associated with a tag indicating whether a surveyor carrying the sampling device is in a train and remains stationary relative to the train, whether the surveyor is walking on the train, whether the train is moving along the rail, whether the train is accelerating or decelerating, and whether the train has stopped at a station.

15. The system of claim 10, wherein the environment profile is representable by at least one of:

a discrete representation of one or more histograms each corresponding to a signal source, each histogram having bins of measured signal strengths of the corresponding signal source and frequencies corresponding to occurrences of measurements at each signal strength, or

a continuous probability density representation.

16. The system of claim 15, wherein determining the location fingerprint comprises:

determining, from each histogram representing the environment profile, a number of modes, each mode corresponding to a local maximum number of occurrences at a corresponding signal strength measured from the corresponding signal source;

selecting an algorithm optimized for single mode statistical filtering upon determining that the each histogram has one mode, or selecting an algorithm optimized for multimode statistical filtering upon determining that the each histogram has a plurality of modes; and

determining the location fingerprint at least in part by applying the selected algorithm to the respective histogram.

17. The system of claim 10, wherein the location fingerprint is associated with an identifier of an operator of the transit system and at least one of a name of the station or geographic coordinates of a portion of the route.

18. The system of claim 17 wherein providing the location fingerprint to a user device comprises:

receiving a request from the user device for location fingerprint data of the transit system, the request includes the identifier of the operator of the transit system; and

in response to the request, providing the location fingerprint to the user device.

19. A non-transitory computer-readable medium storing instructions operable to cause one or more processors to perform operations comprising:

receiving, by the one or more computer processors and from a sampling device, a plurality of sensor readings, each of the sensor readings corresponding to a reading of an attribute of an environment at a portion of a transit system, the portion comprising a station of the transit system or at least a portion of a route of the transit system,

the sensor readings including measurements of strength of radio frequency (RF) signals of signal sources that are detectable at the portion of the transit system, each measurement of strength being associated with a respective identifier of a corresponding signal source;

the sensor readings also including accelerometer readings from the sampling device;

identifying, among the sensor readings, received signal strength indication peaks each associated with a respective corresponding signal source, at least two of the received signal strength indication peaks being associated with a temporal distance;

determining, based on at least a portion of the accelerometer readings, that acceleration along a travel direction of the sampling device meets a threshold of detectable acceleration;

accounting for the acceleration along the travel direction of the sampling device by calculating an adjusted temporal distance between the two received signal strength indication peaks;

determining, from the sensor readings, an environment profile for the portion of the transit system, the environment profile comprising a distribution of frequency of a number of occurrences of each particular value among the sensor readings over values of the readings;

determining, from the sensor readings, whether the environment profile corresponds to a station of the transit system or a moving vehicle of the transit system;

determining, from the environment profile, a location fingerprint for the portion of the transit system, the location fingerprint comprising projected readings of sensors of a mobile device when the mobile device is located at the portion of the transit system; and

providing the location fingerprint to a user device for determining a location of the user device when the user device is in the transit system.

20. The non-transitory computer-readable medium of claim 19, wherein:

the transit system is a subway system where signals from a global positioning satellite system are unavailable or inaccurate for location determination, and

the sensor readings received by the sampling device include readings from at least one of an accelerometer, a magnetometer, a barometer, a gyroscope, a light sensor, a sound pressure sensor, or a radio receiver coupled to the sampling device.

21. The non-transitory computer-readable medium of claim 19, wherein:

at least one of the signal sources includes a cell site of a cellular communications network, a wireless access point, or a Bluetooth™

low energy (BLE) beacon.

22. The non-transitory computer-readable medium of claim 19, wherein:

the portion of the transit system comprises a plurality of platforms of the station of the transit system,

the sensor readings comprise a plurality of measurements taken at each of the platforms and associated with an identifier of the station and an identifier of the platform where the measurements are taken.

23. The non-transitory computer-readable medium of claim 19, wherein:

the portion of the transit system comprises a section of a rail of the transit system; and

each of the sensor readings is associated with a tag indicating whether a surveyor carrying the sampling device is in a train and remains stationary relative to the train, whether the surveyor is walking on the train, whether the train is moving along the rail, whether the train is accelerating or decelerating, and whether the train has stopped at a station.

24. The non-transitory computer-readable medium of claim 19, wherein the environment profile is representable by at least one of:

a discrete representation of one or more histograms each corresponding to a signal source, each histogram having bins of measured signal strengths of the corresponding signal source and frequencies corresponding to occurrences of measurements at each signal strength, or

a continuous probability density representation.

25. The non-transitory computer-readable medium of claim 24, the operations comprising:

determining, from each histogram representing the environment profile, a number of modes, each mode corresponding to a local maximum number of occurrences at a corresponding signal strength measured from the corresponding signal source;

selecting an algorithm optimized for single mode statistical filtering upon determining that the each histogram has one mode, or selecting an algorithm optimized for multimode statistical filtering upon determining that the each histogram has a plurality of modes; and

determining the location fingerprint at least in part by applying the selected algorithm to the respective histogram.

26. The non-transitory computer-readable medium of claim 19, wherein the location fingerprint is associated with an identifier of an operator of the transit system and at least one of a name of the station or geographic coordinates of a portion of the route.

27. The non-transitory computer-readable medium of claim 26 wherein providing the location fingerprint to a user device comprises:

receiving a request from the user device for location fingerprint data of the transit system, the request includes the identifier of the operator of the transit system; and

in response to the request, providing the location fingerprint to the user device.