Multi-stage dead reckoning for crowd sourcing

Patent metadata

Field	Value
Publication number	US-10184798-B2
Application number	US-201113284128-A
Country	US
Kind code	B2
Filing date	Oct 28, 2011
Priority date	Oct 28, 2011
Publication date	Jan 22, 2019
Grant date	Jan 22, 2019

Abstract

A device identifies signals it receives at a particular point in time, such as Wi-Fi signals and cell tower signals. The device records data indicating these identified signals, as well as data used to determine the position of the device at that particular point in time. The position of the device is determined using dead reckoning, which is separated into two stages. In the first stage, a distance and direction of movement is determined at the device based on data from various inertial sensors of the device. In the second stage, various filters, maps, and/or other techniques are used at another device (e.g., a crowd sourcing data service) thus alleviating the device of the burden of performing the second stage.

First claim

What is claimed is:

1. A mobile device comprising:
an accelerometer configured to provide accelerometer data reflecting movement of the mobile device;
a processing device; and
a storage device storing computer-executable instructions which, when executed by the processing device, cause the processing device to:
collect the accelerometer data from the accelerometer; and
determine a position of the mobile device cooperatively with a remote server by:
performing a first stage of dead reckoning locally on the mobile device, the first stage of dead reckoning comprising:
evaluating the accelerometer data to detect linear runs when a user of the mobile device takes multiple steps without changing direction more than a specified amount; and
creating respective movement records for the linear runs, the respective movement records including respective movement distances and movement directions for the linear runs;

sending the respective movement records for the linear runs from the mobile device to the remote server, the remote server performing a second stage of dead reckoning using the respective movement records to obtain a position of the mobile device; and
receiving, from the remote server, the position of the mobile device as determined by the remote server.

2. The mobile device as recited in claim 1 , wherein the computer-executable instructions further cause the processing device to:
detect individual steps taken by the user by identifying peaks in the accelerometer data.

3. The mobile device as recited in claim 2 , wherein the computer-executable instructions further cause the processing device to:
determine respective lengths of the individual steps based at least on respective times between the peaks in the accelerometer data.

4. The mobile device as recited in claim 1 , wherein the computer-executable instructions further cause the processing device to:
send a known starting position of the mobile device from the mobile device to the remote server for use in the second stage of dead reckoning.

5. The mobile device as recited in claim 4 , wherein the computer-executable instructions further cause the processing device to:
determine the known starting position based at least on information received from a beacon.

6. The mobile device as recited in claim 4 , further comprising a global navigation satellite system module configured to determine the known starting position.

7. The mobile device as recited in claim 1 , wherein the computer-executable instructions further cause the processing device to:
determine respective direction changes between individual steps taken by the user;
compare the respective direction changes to a threshold; and
for a group of steps having respective direction changes below the threshold, designate the group of steps as an individual linear run.

8. The mobile device as recited in claim 1 , wherein the computer-executable instructions further cause the processing device to:
determine an amount of power that would be consumed by one or more components of the mobile device in performing the second stage of dead reckoning;
based at least on the determined amount of power, determine whether to perform the second stage of dead reckoning locally on the mobile device or to send the respective movement records to the remote server; and
in at least one instance, use the respective movement records for the linear runs to perform the second stage of dead reckoning locally at the mobile device instead of sending the respective movement records to the remote server.

9. The mobile device as recited in claim 8 , wherein, in the at least one instance, the determined amount of power to be consumed by the one or more components of the mobile device is less than another amount of power that would be consumed by transferring the respective movement records to the remote server.

10. A mobile device, comprising:
one or more inertial sensors configured to provide inertial sensor data reflecting movement of the mobile device;
a processing device; and
a storage device storing computer-executable instructions which, when executed by the processing device, cause the processing device to:
collect the inertial sensor data from the one or more inertial sensors; and
determine a position of the mobile device by:
performing a first stage of dead reckoning locally on the mobile device using the inertial sensor data obtained from the one or more inertial sensors, the first stage of dead reckoning comprising:
evaluating the inertial sensor data to detect linear runs when a user of the mobile device takes multiple steps without changing direction more than a specified amount; and
creating respective movement records for the linear runs, the respective movement records including respective distances and movement directions for the linear runs;

making a determination, based at least on an amount of data in the respective movement records, whether to perform a second stage of dead reckoning locally on the mobile device or send the respective movement records to a second device; and
in at least one instance, based at least on the determination:
sending the respective movement records from the mobile device to the second device, the second device performing the second stage of dead reckoning based at least on the respective movement records, the second stage of dead reckoning resulting in the position of the mobile device, and
receiving, from the second device, the position of the mobile device as determined remotely by the second device.

11. The mobile device as recited in claim 10 , wherein the computer-executable instructions further cause the processing device to:
in at least one other instance, determine the position of the mobile device by performing the second stage of dead reckoning locally at the mobile device.

12. A method for determining a position of a mobile device, the method comprising:
collecting accelerometer data from an accelerometer of the mobile device, the accelerometer data reflecting movement of the mobile device;
performing, by the mobile device, a first stage of dead reckoning using the accelerometer data collected from the accelerometer of the mobile device, the first stage of dead reckoning comprising:
evaluating the accelerometer data to detect linear runs when a user of the mobile device takes multiple steps without changing direction more than a specified amount; and
creating respective movement records for the linear runs, the respective movement records including respective movement distances and movement directions for the linear runs;

in at least one instance, sending the respective movement records for the linear runs from the mobile device to a remote second device that performs a second stage of dead reckoning based at least on the respective movement records, the second stage of dead reckoning resulting in the position of the mobile device; and
receiving, at the mobile device from the remote second device, the position of the mobile device as determined by the remote second device.

13. The method as recited in claim 12 , further comprising:
recording crowd sourcing data as the respective movement records are created.

14. The method as recited in claim 13 , further comprising:
sending the crowd sourcing data from the mobile device to the remote second device, the crowd sourcing data including an indication of identifiers of wireless access points or cell transceivers from which signals are received by the mobile device when the respective movement records are created.

15. The method as recited in claim 12 , further comprising:

Assignees

• Sidhu Gursharan S
• Agarwal Sharad
• Microsoft Technology Licensing Llc

Inventors

• Sidhu Gursharan S
• Agarwal Sharad

Classifications

• G01C21/16 Primary

  by integrating acceleration or speed, i.e. inertial navigation · CPC title

• G01C21/188 Primary

  for accumulated errors, e.g. by coupling inertial systems with absolute positioning systems · CPC title