Path progression matching for indoor positioning systems

• US 8,565,783 B2
• Filed: 11/24/2010
• Issued: 10/22/2013
• Est. Priority Date: 11/24/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yang, Zongxiang, Frick, Henry, Curlander, John Charles, Gail, William B., Agarwal, Sharad, Sriram, Janani C.
• Primary Examiner(s): AJIBADE AKONAI, OLUMIDE
• Application Number:
  US12/954,545
• Publication Number:
  US 20120129546A1
• Time in Patent Office: 1,063 Days
• Field of Search: 455/67.11, 4554561-4566, 370/328, 370/338
• US Class Current: 455/456.1
• CPC Class Codes: G01S 5/0252 Radio frequency fingerprinting
• CPC Class Codes: G01S 5/0294 Trajectory determination or predictive filtering, e.g. target tracking or Kalman filtering
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

A path progression matching system and method that uses path progression to find a current position of a mobile device in an indoor environment and a path history to find the path of the mobile device to get to the current position. Embodiments of the system and method use path history information, constraints, and optimization measures such as the use of received signal strength indicator (RSSI) weighted correlation coefficients. Embodiments of the system and method include a unified probabilistic model that uses path history and allows multiple constraints to be applied simultaneously. Embodiments of the system and method also include a path progression module having a first-stage progression module, which finds a starting location for the path progression matching, a second-stage module, which begins building a path history, and a third-stage progression module, which uses the path history to find the current position and path.

Claims

1. A method, implemented on a computer processing unit, of finding a position and a path of a mobile device, the method comprising:

obtaining a first set of received signal strength (RSS) data at a first time;

finding a first position of the mobile device using the first set of RSS data;

obtaining a second set of RSS data at a second time that is later than the first time;

finding a second position of the mobile device at the second time using the second set of RSS data;

calculating a first most probable path between the first position and the second position;

adding the first most probable path to a path history list;

using the path history list to find a current position of the mobile device at another time and another most probable path taken to get to the current position; and

scoring a probability that the mobile device is in the current position using the first most probable path.

2. The method of claim 1, further comprising outputting the first position to an application for tracking of the mobile device in an indoor environment.

3. The method of claim 1, further comprising:

obtaining a third set of RSS data at a third time that is later than the second time;

finding a third position of the mobile device at the third time using the third set of RSS data; and

calculating a second most probable path between the second position and the third position using paths stored in the path history list.

4. The method of claim 3, further comprising adding the second most probable path to the path history list.

5. The method of claim 1, further comprising:

finding a first approximate initial position using the first set of RSS data;

computing a first-stage network distance;

determining a first-stage network distance circle around the first approximate initial position, where the first-stage network distance circle has a radius of the first-stage network distance; and

selecting neighboring points around the first approximate initial position that lie within the first-stage network distance circle.

6. The method of claim 5, further comprising:

selecting a top N number of the neighboring points within the first-stage network distance circle;

computing a received signal strength indicator (RSSI) weight for each of the top N number of the neighboring points; and

computing an RSSI weighted correlation coefficient for each of the top N number of the neighboring points from the RSSI weight.

7. The method of claim 6, further comprising designating as FromNodes the top N number of points having an N number of highest RSSI weight correlation coefficients.

8. The method of claim 7, further comprising selecting as the first position at the first time a point from the top N number of points having a highest RSSI weight correlation coefficient.

9. The method of claim 1, further comprising:

obtaining a maximum walking speed;

computing a maximum traversable distance based on an elapsed time between the first time and the second time and the maximum walking speed;

finding a second approximate position at the second time based on the maximum traversable distance;

computing a second-stage network distance; and

determining a second-stage network distance circle around the second approximate position, where the second-stage network distance circle has a radius of the second-stage network distance.

10. The method of claim 9, further comprising:

selecting a top N number of points within the second-stage network distance circle based on a received signal strength indicator (RSSI) weight correlation coefficient for each of the top N number of points;

selecting points from the top N number of points as ToNodes for potential paths from the first position to the second position; and

selecting neighboring points around the first position as FromNodes for the potential paths.

11. The method of claim 10, further comprising:

computing a path weight for each of the potential paths; and

designating one of the potential paths having a highest path weight as the first most probable path.

12. The method of claim 11 further comprising designating a ToNode of the first most probable path as the second position at the second time.

13. The method of claim 10, further comprising:

designating the ToNodes of the potential paths from the first position to the second position as current FromNodes;

setting a weight of each of the current FromNodes to a maximum path weight of a sum of paths that led to the current FromNodes; and

selecting ToNodes at a third time that is later than the second time based on the second position at the second time and the maximum traversable distance.

14. The method of claim 13, further comprising:

computing ToNode weights using corresponding RSSI weighted correlation coefficients;

computing a path weight of potential paths at the third time as a product of the FromNode weight and the ToNode weight;

designating one of the potential paths at the third time having a highest path weight as a second most probable path at the third time; and

designating a ToNode of the second most probable path as a third position at the third time.

15. A system comprising:

a processing unit; and

one or more computer storage media storing computer readable instructions that, when executed by the processing unit, configure the processing unit to;

find a first potential location of a mobile device;

build a path history that includes a first path taken from the first potential location of the mobile device to a second potential location of the mobile device;

use the path history to find a potential current location of the mobile device and a second path taken to reach the potential current location; and

score a probability that the mobile device is at the potential current location using the first path and the second path.

16. The system of claim 15, wherein the computer readable instructions further configure the processing unit to:

apply constraints to find the potential current location, the constraints including;

a network distance constraint that uses a person'"'"'s walking speed to indicate a distance that a person is likely to walk in a given time; and

a physical constraint that indicates which areas of an indoor environment are inaccessible.

17. The system of claim 15, embodied as a device other than the mobile device.

18. A volatile or nonvolatile computer storage media storing computer readable instructions that, when executed by a processor, cause the processor to perform acts for determining a position and a path of a mobile device in an indoor environment, the acts comprising:

receiving a plurality of received signal strength (RSS) data at different times, the RSS data representing strength of signals received by the mobile device;

using a first set of RSS data from the plurality of RSS data to find a first approximate initial position of the mobile device;

computing a first-stage network distance circle having a radius equal to a first-stage network distance and a center at the first approximate initial position;

computing a received signal strength indicator (RSSI) weight for points within the first-stage network distance circle;

computing an RSSI weighted correlation coefficient for each of the points using the RSSI weights;

selecting one of the points having a highest RSSI weighted correlation coefficient as a first position at the first time;

using a second set of RSS data from the plurality of RSS data to find a second position of the mobile device at a second time;

designating the points within the first-stage network distance circle as FromNodes and the second position as a ToNode;

computing potential paths from the FromNodes to the ToNode;

calculating one of the potential paths as a first most probable path between the first position and the second position; and

adding the first most probable path to a path history list.

19. The volatile or nonvolatile computer storage media of claim 18, the acts further comprising:

using a third set of RSS data from the plurality of RSS data to find a third position of the mobile device at a third time;

designating ToNodes at the second time as current FromNodes at the third time;

computing weights for the current FromNodes as a maximum path weight of a sum of paths leading to the current FromNodes;

selecting ToNodes at the third time based on the second position;

computing weights for the ToNodes at the third time using RSSI weighted correlation coefficients;

finding potential paths from the FromNodes to the ToNodes;

computing a path weight for each of the potential paths as a product of the FromNode weight and the ToNode weight; and

designating one of the potential paths having a highest path weight as a second most probable path at the third time.

20. The volatile or nonvolatile computer storage media of claim 19, the acts further comprising:

computing a maximum path weight at each stage of path progression;

determining that the maximum path weight for a stage is less than a threshold;

multiplying path weights of each of the potential paths for the individual stage by a factor equal to one divided by the threshold to obtain modified path weights; and

using the modified path weights in the path progression.