Location determination

Patent metadata

Field	Value
Publication number	US-9568323-B2
Application number	US-201113274916-A
Country	US
Kind code	B2
Filing date	Oct 17, 2011
Priority date	Oct 17, 2011
Publication date	Feb 14, 2017
Grant date	Feb 14, 2017

Abstract

Techniques for determining a location of a device include estimating a mobility trace of the device, mapping the mobility trace to a map, and determining the location of the device based on the mapped mobility trace. The mobility trace may be estimated based on a reading obtained from the device, which may be a reading from an accelerometer and/or magnetometer sensor. The determined location of the device may correspond to a location on the mapped mobility trace.

First claim

The invention claimed is:

1. A method implemented by a device, comprising:
obtaining, periodically according to a first period of time, a reading from at least one of an accelerometer or a magnetometer sensor of the device;
estimating, by the device, a mobility trace of the device based at least in part on the reading, the estimating occurring according to a second period of time that is longer than the first period of time, the mobility trace including a plurality of segments, at least one of the plurality of segments being a closed-ended segment, and at least one of the plurality of segments being an open-ended segment;
selecting a map from a plurality of maps based at least in part on a type of transportation associated with the device, each map of the plurality of maps being associated with a different type of transportation route than other maps of the plurality of maps;
mapping, by the device, the mobility trace to the selected map; and
determining, by the device, a geographic location of the device based at least in part on the mapped mobility trace, the determining including performing at least one of interpolation or extrapolation, the interpolation being based at least in part on the closed-ended segment, and the extrapolation being based at least in part on the open-ended segment.

2. The method of claim 1 , wherein the mobility trace further includes a plurality of turns, the turns being between the plurality of segments, each of the plurality of segments being associated with a speed of the device and having a distance and a direction, the distance corresponding to a traveled distance of the device in a corresponding direction.

3. The method of claim 2 , wherein the estimating includes:
estimating at least one of speeds based on integration of an acceleration, the acceleration being based on the reading;
estimating at least one of distances based on double integration of the acceleration; and
estimating at least one of directions based on an angle between a heading vector and an orientation vector, the heading vector being obtained from a difference between two accelerometer readings, and the orientation vector being obtained from a magnetometer reading.

4. The method of claim 2 , wherein the estimating includes:
estimating at least one of speeds based on a pedaling frequency, the pedaling frequency being based on the reading;
estimating at least one of distances based on the at least one of the speeds and a duration of time associated with the at least one of the speeds; and
estimating at least one of directions based on a magnetometer reading, the magnetometer reading corresponding to a minimum magnitude of acceleration, the minimum magnitude of acceleration being a minimum magnitude among a plurality of magnitudes of acceleration.

5. The method of claim 2 , wherein the estimating includes:
estimating at least one of distances based on a number of steps a user of the device has traveled and an average stride length of the user for each of the steps;
estimating at least one of speeds based on the at least one of the distances and a traveling time of the device for the at least one of the distances; and
estimating at least one of the directions based on a magnetometer reading, the magnetometer reading corresponding to a minimum magnitude of acceleration, the minimum magnitude of acceleration being a minimum magnitude among a plurality of magnitudes of acceleration.

6. The method of claim 1 , further comprising:
performing motion state detection to determine a motion state of the device based on the reading, the motion state comprising a state in which the device is moving or a state in which the device is still,
wherein the estimating includes estimating the mobility trace based on the determined motion state.

7. The method of claim 1 , further comprising:
obtaining wireless access point data that identifies at least one wireless access point, the wireless access point data being obtained by the device at a location on the mobility trace,
wherein the mapping includes fixing the mobility trace to the selected map based on the wireless access point data.

8. The method of claim 1 , further comprising:
obtaining cell tower data that identifies at least one cell tower, the cell tower data being obtained by the device at a location on the mobility trace,
wherein the mapping includes fixing the mobility trace to the selected map based on the cell tower data.

9. The method of claim 8 , wherein
the mobility trace further includes a plurality of turns;
the map includes a plurality of road segments and turns; and
the mapping includes fixing the plurality of segments and turns of the mobility trace to the plurality of road segments and turns of the map.

10. The method of claim 8 , wherein the fixing includes utilizing Viterbi decoding based on a Hidden Markov Model to determine a sequence of segments that the device traveled, the sequence of segments including segments from the selected map.

11. The method of claim 10 , wherein the Hidden Markov Model includes at least one of a hidden state, an observation, an emission probability, and/or a transition probability, the hidden state being a span of road segments of the map, the observation including an angle of a turn within the mobility trace, a distance between two turns within the mobility trace, or the cell tower data.

12. The method of claim 10 , wherein the Hidden Markov Model includes hidden states and the Viterbi decoding determines a sequence of the hidden states, the sequence of the hidden states corresponding to the sequence of segments that the device traveled.

13. The method of claim 1 , wherein:
the performing at least one of interpolation or extrapolation includes performing at least one of interpolation or extrapolation to determine the geographic location of the device based at least in part on the mapped mobility trace and a speed of the device on at least one of the plurality of segments.

14. The method of claim 13 , further comprising:
receiving a location query from a location-based service or application, the location query including a time of a requested location of the device,
wherein the speed is a speed of the device on the closed-ended segment, and the determining includes:
determining that the time of the requested location is within a time duration of the closed-ended segment, the time duration indicating a traveling duration of the device on the closed-ended segment; and
performing the interpolation in response to determining that the time is within the time duration of the closed-ended segment, the interpolation being performed based on the speed and the time of the requested location.

15. The method of claim 13 , further comprising:
receiving a location query from a location-based service or application, the location query including a time of a requested location of the device,
wherein the speed is a speed of the device on the open-ended segment, and
the determining includes:
determining that the time of the requested location is within a time duration of the open-ended segment, the time duration indicating a traveling duration of the device on the open-ended segment; and
performing the extrapolation in response to determining that the time is within the time duration of the open-ended segment, the interpolation being performed based on the speed and the time of the requested location.

16. The method of claim 1 , further comprising:
detecting a turn based on the reading,
wherein the mapping includes mapping the mobility trace in response to detecting the turn.

Assignees

• Li Fan
• Shen Guo Bin
• Microsoft Technology Licensing Llc

Inventors

• Li Fan
• Shen Guo Bin

Classifications

• G01S5/0264

  at least one of the systems being a non-radio wave positioning system · CPC title

• G01C21/32 Primary

  Structuring or formatting of map data · CPC title

• H04W64/00

  Locating users or terminals {or network equipment} for network management purposes, e.g. mobility management · CPC title

• H04W4/027

  using movement velocity, acceleration information · CPC title

• H04W4/028

  Electricity · mapped topic