Location determination

• US 9,568,323 B2
• Filed: 10/17/2011
• Issued: 02/14/2017
• Est. Priority Date: 10/17/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Li, Fan, Shen, Guo Bin
• Primary Examiner(s): Vu, Thai
• Application Number:
  US13/274,916
• Publication Number:
  US 20130095861A1
• Time in Patent Office: 1,947 Days
• Field of Search: 455/404.2, 455/414.2, 455/457, 455/456.6
• US Class Current: 1/1
• CPC Class Codes: G01S 5/0264 at least one of the systems being a non-radio wave positioning system
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration information
• 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

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.

Claims

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.

17. A device comprising:

one or more processors; and

one or more computer storage media storing computer-executable instructions executable by the one or more processors that, when executed by the one or more processors, cause the one or more processors to perform acts comprising;

obtaining, periodically according to a first period of time, a reading from at least one of an accelerometer or a magnetometer of the device;

determining a motion state of the device based at least in part on a location of the device on a user;

estimating a mobility trace of the device based at least in part on the determined motion state and the reading, 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;

mapping the mobility trace to the map based at least in part on cell tower data identifying a cell tower the device communicated with along the mobility trace, the mobility trace being mapped by searching an area of the map that corresponds to a coverage area of the cell tower and fixing a portion of the mobility trace to a portion of the map that is within the area; and

performing at least one of interpolation or extrapolation to determine the location of the device based at least in part on the mapped mobility trace, 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.

18. One or more computer storage media storing computer-executable instructions executable by one or more processors that, when executed by the one or more processors, cause the one or more processors to perform acts comprising:

obtaining, periodically according to a first period of time, a reading from at least one of an accelerometer or a magnetometer sensor of a device;

estimating 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 the mobility trace to the selected map; and

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

19. The one or more computer storage media of claim 18, 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.

20. The one or more computer storage media of claim 18, wherein the acts further comprise:

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 at least in part on the cell tower data.