Calibration of a device location measurement system that utilizes wireless signal strengths

• US 7,411,549 B2
• Filed: 06/14/2007
• Issued: 08/12/2008
• Est. Priority Date: 04/25/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Platt, John C., Krumm, John C.
• Primary Examiner(s): Issing; Gregory C
• Application Number:
  US11/763,422
• Publication Number:
  US 20070241963A1
• Time in Patent Office: 425 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/02528 Simulating radio frequency fingerprints
• CPC Class Codes: H04W 16/20 for indoor coverage or short range network deployment
• CPC Class Codes: H04W 16/225 for indoor or short range network
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 88/18 Service support devices; Network management devices

Abstract

An architecture for minimizing calibration effort in an IEEE 802.11 device location measurement system. The calibration technique is based upon a regression function that produces adequately accurate location information as a function of signal strength regardless of gaps in the calibration data or minimally available data. The algorithm takes a set of signal strengths from known room locations in a building and generates a function giving (x,y) as a function of signal strength, which function may then be used for the estimation of new locations. Radial basis functions, which are simple to express and compute, are used for regression. The fact that the algorithm maps signal strength to continuous location makes it possible to skip rooms during calibration, yet still evaluate the location in those rooms.

Claims

1. A device location calibration system comprising:

at least three transmitter components that each broadcast a signal;

a receiver component that measures and records a signal characteristic of each of the signals, the signal characteristics are associated with a spatial location that the signal characteristics were measured at, the signal characteristics include at least one of a signal strength, a phase, an autocorrelation, or a spectrum; and

a regression component that generates a regression function, the regression function maps a plurality of signal vectors to a plurality of estimated spatial locations, each signal vector includes at least one measurement of the signal characteristic, wherein the regression function comprises an isotropic Gaussian kernel function that employs the vectors.

2. The system of claim 1, the regression component determines the regression function based at least in part on a training set, the training set includes a spatial location and signal characteristics associated with the spatial location, the spatial location in the training set has a known set of coordinates.

3. The system of claim 1, the isotropic Gaussian kernel function utilizes the difference between a vector of observed signal characteristics and a vector of stored signal characteristics.

4. The system of claim 2, the regression function is a heteroscedastic regression function that weighs an inverse of a variance of uncertainty for a corresponding spatial location in the training set.

5. The system of claim 1, the estimated spatial locations are (x, y, z) coordinates.

6. The system of claim 1, the signal characteristics are of wireless radio signals and the transmitter components are access point transceivers disposed on a network.

7. The system of claim 1, the regression component fills a kernel matrix by clustering signal vectors, the kernel matrix comprises a linear system, based at least in part on measured signal characteristics and associated spatial locations.

8. The system of claim 7, the regression function includes weights, and the regression component comprises a fitting component that fits the regression function to the measured signal characteristics by regulating the weights.

9. The system of claim 8, the fitting component regulates the weights of the regression function by solving the linear system of the kernel matrix utilizing a least squares fit model.

10. The system of claim 1, further comprising:

a display component that demonstrates a graphical floor map representation of the spatial locations and a representation of measured signal characteristics.

11. The system of claim 10, the display component associates signal characteristics with the corresponding spatial location as users select the matching section on the graphical floor map.

12. A method to calibrate a device location system comprising:

receiving at least three signals;

measuring and recording signal characteristics of the signals, the signal characteristics are associated with a spatial location that the signal characteristics were measured at, the signal characteristics include at least one of a signal strength, a phase, an autocorrelation, or a spectrum; and

generating a regression function, the regression function maps a plurality of signal vectors to a plurality of estimated spatial locations, each signal vector includes at least one measurement of the signal characteristics, wherein the regression function comprises an isotropic Gaussian kernel function that employs the vectors.

13. The method of claim 12, further comprising:

developing a training set by locating the receiver to a plurality of calibration points and measuring signal characteristics at the calibration points, a calibration point has known spatial coordinates; and

further generating the regression function based at least in part on the training set.

14. The method of claim 13, further comprising:

filling a kernel matrix including a linear system by clustering signal vectors; and

solving the linear system of the kernel matrix utilizing a least squares fit model.

15. The method of claim 13, developing the training set by measuring signal characteristics multiple times at a single calibration point located within a section.

16. The method of claim 13, developing the training set by determining spatial location to be the centroid of multiple calibration points located within a section.

17. The method of claim 13, the regression function is an isotropic Gaussian kernel function that utilizes the difference between a vector of observed signal characteristics and a vector of stored signal characteristics.

18. A device location calibration system comprising:

means for measuring and recording at least one signal associated with a spatial location that signal characteristics were measured at, the signal characteristics include at least one of a signal strength, a phase, an autocorrelation, or a spectrum; and

means for generating a regression function, the regression function maps a plurality of signal vectors to a plurality of estimated spatial locations, each signal vector includes at least one measurement of the signal characteristic, wherein the regression function comprises an isotropic Gaussian kernel function that employs the vectors.

19. The system of claim 18, further comprising:

means for developing a training set, the training set includes a spatial location and signal characteristics associated with the spatial location, the spatial location in the training set has a known set of coordinates; and

means for further determining the regression function based at least in part on the training set.

20. The system of claim 18, further comprising:

means for filling a kernel matrix including a linear system; and

means for solving the linear system of the kernel matrix utilizing a least squares fit mode.