System and methods for determining the location dynamics of a portable computing device

• US 7,053,830 B2
• Filed: 07/25/2005
• Issued: 05/30/2006
• Est. Priority Date: 06/30/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Horvitz, Eric J., Krumm, John C.
• Primary Examiner(s): Issing, Gregory C.
• Application Number:
  US11/188,433
• Publication Number:
  US 20050270235A1
• Time in Patent Office: 309 Days
• Field of Search: None
• US Class Current: 342/451
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01S 5/02524 Creating or updating the radio-map
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A location system for locating and determining the motion and velocity of a wireless device. The methods include direct inferences about whether a device is in motion versus static based on a statistical analysis of the variation of radio signal strengths over time. The system is trained according to a sparse set of identified locations from which signal strengths are measured. The system uses the signal properties of the identified locations to interpolate for a new location of the wireless device. The system uses a probabilistic graph where the identified locations of the floor plan, expected walking speeds of pedestrians, and independent inference of whether or not the device is in motion are used to determine the new location of the device.

Claims

1. A method of determining the location of a wireless measurement device, comprising:

developing a computer-based map of locations in which the wireless device will be used;

sparsely populating the map with low-density nodes each of which is associated with a respective location on the map;

training the locations by measuring signal properties received at calibration nodes associated with each of the low-density nodes;

generating signal strength distributions for each of the calibration nodes based upon the received signal properties;

populating the map with high-density nodes that are interspersed among the low-density nodes;

generating a transition probability for each pair of high-density nodes based upon path constraints between the nodes;

generating observation probabilities for each of the low-density location nodes;

processing the signal strength distributions, transition probabilities, and observation probabilities to generate a probability value for each high-density node; and

interpolating the probability that the wireless device is at one or near one of the high-density nodes based upon the probability values of the low-density nodes.

2. The method of claim 1, further comprising generating a transition probability between a high-density node and a low-density node.