System and method for locating radio emitters using self-calibrated path loss computation

• US 7,236,128 B2
• Filed: 10/29/2004
• Issued: 06/26/2007
• Est. Priority Date: 06/23/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cognio, Inc. (Cisco Systems, Inc.)
• Inventors: Sugar, Gary L., Tesfai, Yohannes
• Primary Examiner(s): Tarcza; Thomas H.
• Assistant Examiner(s): Mull; Fred H.
• Application Number:
  US10/976,509
• Publication Number:
  US 20050285792A1
• Time in Patent Office: 970 Days
• Field of Search: 342/174, 342463-465
• US Class Current: 342/465
• CPC Class Codes: G01S 5/0226 Transmitters
• CPC Class Codes: G01S 5/02527 Detecting or resolving anomalies in the radio frequency fingerprints of the radio-map

Abstract

Techniques for reducing the complexity and improving the accuracy of receive signal strength based location systems. The system comprises a plurality of radio sensor devices placed at known positions within a space in which devices are to be located. According to one technique, the path loss is measured between all combinations of pairs of radio sensor devices based on a test signal transmitted by each radio sensor device. A path loss model is evaluated to compute modeled path loss data between all combinations of pairs of radio sensor devices. For each measured path loss, a path loss error relative to each radio sensor device is computed by taking the difference between the measured path loss and the modeled path loss. The path loss error relative to each radio sensor device at any candidate position is interpolated from the computed path loss errors. A path loss estimate between a candidate position and each radio sensor device is computed by adding the interpolated path loss error relative to that radio sensor device at the candidate position and path loss data obtained by evaluating the path loss model based on the distance between at each candidate position and the corresponding radio sensor device. When determining the position of a device emitting radio signals (called a target device), the improved path loss estimate is used. According to another technique, for each radio sensor device, parameters are derived for a path loss model function from the measured path loss between that radio sensor device and each of the other radio sensor devices using a minimization computation. Then, a path loss estimate between a position and each radio sensor device is computed by evaluating the path loss model function using the parameters derived for each radio sensor device.

Claims

1. A system for determining a position of a target device that makes radio emissions, the system comprising:

a. a plurality of radio sensor devices at known positions within in an area, each radio sensor device capable of receiving radio emissions;

b. a computing device coupled to the plurality of radio sensor devices and receiving data therefrom that represents strength of signals received by the radio sensor devices from the target device, wherein the computing device estimates a location of the target device by processing receive signal strength data obtained by the plurality of radio sensor devices with respect to path loss estimate data, and wherein the computing device computes the path loss estimated data by;

i. with respect to a test signal transmitted by each radio sensor device, measuring path loss at each of the other radio sensor devices to obtain the path loss between all combinations of pairs of radio sensor devices;

ii. evaluating a path loss model based on the distance between all combinations of pairs of radio sensor devices to produce path loss model data;

iii. computing, relative to each radio sensor device, a path loss error between the measured path loss and the path loss model data when the path loss is measured at each of the other radio sensor positions relative to that radio sensor device;

iv. interpolating a path loss error relative to each radio sensor device at a candidate position from the path loss errors using a multi-dimensional interpolation technique; and

v. computing a path loss estimate between a candidate position and each radio sensor device by adding the interpolated path loss error relative to a radio sensor device at the candidate position to path loss data obtained by evaluating the path loss model based on a distance between a position of the corresponding radio sensor device and the candidate position.

2. The system of claim 1, wherein the computing device interpolates path loss error relative to each radio sensor device at each of a plurality of candidate positions, and computes a path loss estimate between each of the plurality of candidate positions and each radio sensor device by adding the interpolated path loss error relative to a radio sensor device at each candidate position to path loss data obtained by evaluating the path loss model based on a distance between the position of the corresponding radio sensor device and the corresponding candidate position.

3. The system of claim 1, wherein the computing device estimates the position u* of the target device by computing the position

4. The system of claim 3, wherein the computing device estimates the position of the target device based on a sequence r₁, . . . ,r_Nseq of receive signal strength observations from multiple transmissions by the target device, by computing the position

5. The system of claim 3, wherein the computing device estimates the position of the target device based on a sequence r_n of receive signal strength observations from multiple transmissions by the target device, by solving for

6. The system of claim 3, wherein the computing device estimates the position of the target device based on a sequence of {r1_n}, . . . , {rP_n} of receive signal strength observation sequences at P antennas of each radio sensor device.

7. The system of claim 3, wherein the computing device estimates the position u* of the target device by computing

8. The system of claim 3, wherein the computing device estimates the position u* of the target device by computing

9. The system of claim 8, wherein the computing device estimates the position u* of the target device by minimizing over multiple path loss models.

10. The system of claim 9, wherein the computing device estimates the position u* of the target device by computing

11. The system of claim 8, wherein the computing device estimates the position u* of the target device by computing a first position estimate using a first low pass filter and a second position estimate using a second low pass filter, wherein the first low pass filter has a slower response than the second low pass filter and wherein the computing device selects the first position estimate as the position estimate u* of the target device unless a difference between the first position estimate and the second position estimate is greater than a threshold, in which case the computing device selects the second position estimate as the position estimate u* of the target device.

12. The system of claim 3, wherein the computing device estimates the position of the target device by selecting the candidate position u that is closest in Euclidean distance to the receive signal strength observations r with respect to the path loss estimate for each radio sensor device, {circumflex over (L)}(u, u_sens(j)).

13. The system of claim 3, wherein the computing device estimates a position of the target device by, for each candidate position and for a range of candidate transmit powers PT_Tx of the target device:

a. computing {circumflex over (r)}=10 log₁₀ [10<sup>0.1(PTx·

1−

L1)</sup>+10 <sup>0.1·

NF</sup>], where

L1=[{circumflex over (L)}(u,u_sens(1)), . . . , {circumflex over (L)}(u,u_sens(N))]^T is a matrix composed of path loss estimates

{circumflex over (L)}(u,u_sens(1)) to {circumflex over (L)}(u,u_sens(N)) at candidate position u with respect to each radio sensor device position and NF is the noise floor at each radio sensor device;

b. computing a function

14. The system of claim 13, wherein the computing device selects the candidate position in the candidate position/transmit power pair that minimizes the function J(u,P_Tx).

15. The system of claim 14, wherein the computing device generates one or more candidate transmit powers based on prior estimated positions of the target device.

16. The system of claim 15, wherein the computing device generates one or more candidate transmit powers by storing candidate transmit powers for prior estimated positions of the target device, computing a median candidate transmit power from the stored candidate transmit powers for prior estimated positions, and providing a set of candidate transmit powers based on the median.

17. The system of claim 16, wherein the computing device provides a set of candidate transmit powers by providing a plurality of transmit powers that progressively deviate from the median by a desired amount.

18. The system of claim 3, wherein the computing device estimates a position of the target device by, for each candidate position and for a range of candidate transmit powers PT_x of the target device:

a. computing {circumflex over (r)}=10 log₁₀[10<sup>0.1(PTx·

1−

L1)</sup>+10 <sup>0.1·

NF</sup>], where

L1=[{circumflex over (L)}(u,u_sens(1)), . . . , {circumflex over (L)}(u,u_sens(N))]^T is amatrix composed of path loss estimates

{circumflex over (L)}(u,u_sens(1)) to {circumflex over (L)}(u,u_sens(N)) at candidate position u with respect to each sensor position and NF is the noise floor at each sensor;

b. computing a function

19. The system of claim 18, wherein the computing device stores candidate transmit powers for prior estimated positions of the target device and computes the median candidate transmit power from the stored candidate transmit powers for prior estimated positions of the target device.

20. The system of claim 3, wherein the computing device estimates the position u* of the target device by further minimizing over multiple path loss models.

21. The system of claim 3, wherein the computing device applies an iterative multi-dimensional minimization algorithm to the equation

22. The system of claim 1, wherein the computing device computes the path loss estimate in three-dimensions.

23. The system of claim 1, wherein each of the plurality of radio sensor devices comprises a buffer memory that stores raw analog-to-digital converter samples of emissions received from the target device, and wherein the receive signal strength data is derived from the samples.

24. The system of claim 1, wherein the plurality of sensors are deployed on each floor of a multiple floor building, and wherein the computing device selects a subset of the plurality of sensors on a certain number of floors of the building used for computing the estimate of the position of the target device.

25. The system of claim 24, wherein the computing device computes an average power per sensor per floor P_avg(f)=Σ

_kP(f,k)/N(f), wherein N(f) is the number of sensors on floor f and P(f,k) is the power received from the target device at the kth sensor on floor f, and the computing device selects the subset of sensors as those sensors on those floors f having the relatively higher P_avg(f).

26. A method for generating path loss estimate data associated with an area in which a plurality of radio sensor devices are deployed at known positions and used to determine a position of a target device in the area based on emissions received from the target device, the method comprising:

a. with respect to a test signal transmitted by each radio sensor device, measuring path loss at each of the other radio sensor devices to measure the path loss between all combinations of pairs of radio sensor devices;

b. evaluating a path loss model based on the distance between all combinations of pairs of radio sensor devices to produce path loss model data;

c. computing, relative to each radio sensor device, a path loss error between the measured path loss and the path loss model data when the path loss is measured at each of the other radio sensor positions relative to that radio sensor device;

d. interpolating a path loss error relative to each radio sensor device at a candidate position from the corresponding computed path loss errors using a multi-dimensional interpolation technique; and

e. computing a path loss estimate between a candidate position and each radio sensor device by adding the interpolated path loss error relative to a radio sensor device at the candidate position to path loss data obtained by evaluating the path loss model based on a distance between a position of the corresponding radio sensor device and the candidate position.

27. The method of claim 26, wherein interpolating comprises interpolating the path loss error relative to each radio sensor device at each of a plurality of candidate positions, and the step of computing the path loss estimate comprises computing a path loss estimate between each of the plurality of candidate positions and each radio sensor device by adding the interpolated path loss error relative to a radio sensor device at each candidate position to path loss data obtained by evaluating the path loss model based on a distance between the position of the corresponding radio sensor device and the corresponding candidate position.

28. A method for determining a position of a target device based on data pertaining to strength of an emission received from the target device at a plurality of known positions, the method comprising:

a. receiving an emission from the target device at each of a plurality of known positions to produce receive signal strength data; and

b. computing a most likely position over a plurality of candidate positions, a plurality of path loss models and a plurality of candidate transmit powers of the target device based on the receive signal strength data, wherein computing comprises computing the most likely position by minimizing over the plurality of path loss models.

29. The method of claim 28, wherein computing comprises processing received signal strength data obtained at each of the plurality of known positions with respect to estimated path loss data with respect to each known position.

30. The method of claim 29, and further comprising generating path loss estimate data with respect to each known position by:

i. with respect to a test signal transmitted by from each known position, measuring path loss at each of the other known positions to measure the path loss between all combinations of pairs of known positions;

ii. evaluating a path loss model based on the distance between all combinations of pairs of known positions to produce path loss model data;

iii. computing, relative to each known position, a path loss error between the measured path loss and the path loss model data when the path loss is measured at each of the other known positions relative to that known position;

iv. interpolating a path loss error relative to each known position at a candidate position from the corresponding computed path loss errors; and

v. computing a path loss estimate between a candidate position and each known position by adding the interpolated path loss error relative to a known position at the candidate position to path loss data obtained by evaluating the path loss model based on a distance between a known position and the candidate position.

31. The method of claim 30, wherein interpolating comprises interpolating the path loss error relative to each known position at each of a plurality of candidate positions, and computing the path loss estimate comprises computing a path loss estimate between each of the plurality of candidate positions and each known position by adding the interpolated path loss error relative to a known position at each candidate position to path loss data obtained by evaluating the path loss model based on a distance between the known position and the corresponding candidate position.

32. The method of claim 31, wherein interpolating the path loss error comprises interpolating the path loss error relative to each known position at each candidate position using a multi-dimensional interpolation technique.

33. The method of claim 29, and further comprising generating estimated path loss data with respect to each known position by:

a. with respect to a test signal transmitted from each known position, measuring path loss at each of the other known positions to measure the path loss between all combinations of pairs of known positions;

b. for each known position, deriving parameters for a path loss model function from the measured path loss between that known position and each of the other known positions; and

c. computing a path loss estimate between a candidate position and each known position by evaluating the path loss model function using the parameters derived for each known position.

34. The method of claim 33, wherein deriving comprises minimizing a mean squared error between the measured path loss between a known position and each of the other known positions and the path loss model function between that known position and each of the other known positions.

35. The method of claim 34, wherein deriving comprises computing a minimum of a square of a norm of a difference between a vector representing measured path loss between a known position and each of the other known positions and a vector representing the path loss model function based on corresponding distances between the known position and each of the other known positions.

36. The method of claim 28, wherein receiving comprises receiving one or more emissions from the target device at each of a plurality of antennas at each of the plurality of known positions.

37. A method for determining a position of a target device based on data pertaining to strength of an emission received from the target device at a plurality of known positions, the method comprising:

a. receiving an emission from the target device at each of a plurality of known positions to produce receive signal strength data; and

b. computing a most likely position over a plurality of candidate positions, a plurality of path loss models and a plurality of candidate transmit powers of the target device based on the receive signal strength data, wherein computing comprises computing a position u*, where

38. The method of claim 37, wherein computing comprising applying an iterative multi-dimensional minimization algorithm to the equation

39. The method of claim 37, wherein computing comprises estimating the position of the target device based on a sequence r₁, . . . ,r_Nseq of receive signal strength observations from multiple transmissions by the target device, by computing the position

40. The method of claim 37, wherein computing comprises estimating the position of the target device based on a sequence r_n of receive signal strength observations from multiple transmissions by the target device, by solving for

41. The method of claim 37, wherein computing a position estimate u* of the target device comprises computing

42. The method of claim 41, wherein computing position estimate u* of the target device comprises computing a first position estimate using a first low pass filter and a second position estimate using a second low pass filter, wherein the first low pass filter has a slower response than the second low pass filter and further comprising selecting the first position estimate as the position estimate u* of the target device unless a difference between the first position estimate and the second position estimate is greater than a threshold, otherwise selecting the second position estimate as the position estimate u* of the target device.

43. The method of claim 37, wherein computing a position estimate u* of the target device comprises computing

44. A method for determining a position of a target device based on data pertaining to strength of an emission received from the target device at a plurality of known positions, the method comprising:

a. receiving an emission from the target device at each of a plurality of known positions to produce receive signal strength data; and

b. computing a most likely position over a plurality of candidate positions, a plurality of path loss models and a plurality of candidate transmit powers of the target device based on the receive signal strength data, wherein computing comprises computing a position estimate of the target device by, for each candidate position and for a range of candidate transmit powers PT_x of the target device;

computing {circumflex over (r)}=10 log₁₀[10<sup>0.1(PTx·

1−

L1)</sup>+10<sup>0.1·

NF</sup>], where

L1=[{circumflex over (L)}(u,u_sens(1)), . . . , {circumflex over (L)}(u,u_sens(N))]^T is a matrix composed of path loss estimates

{circumflex over (L)}(u,u_sens(1)) to {circumflex over (L)}(u,u_sens(N)) at candidate position u with respect to a radio sensor device at a corresponding known position and NF is the noise floor at each radio sensor device;

computing a function

45. The method of claim 44, wherein selecting comprises selecting the candidate position in the candidate position/transmit power pair that minimizes the function J(u,P_Tx).

46. The method of claim 45, and further comprising generating one or more candidate transmit powers based on prior estimated positions of the target device.

47. The method of claim 46, wherein generating comprises generating one or more candidate transmit powers by storing candidate transmit powers for prior estimated positions of the target device, computing a median candidate transmit power from the stored candidate transmit powers for prior estimated positions, and providing a set of candidate transmit powers based on the median.

48. The method of claim 47, wherein generating comprises generating a set of candidate transmit powers by providing a plurality of transmit powers that progressively deviate from the median by a desired amount.

49. A method for determining a position of a target device based on data pertaining to strength of an emission received from the target device at a plurality of known positions, the method comprising:

a. receiving an emission from the target device at each of a plurality of known positions to produce receive signal strength data; and

b. computing a most likely position over a plurality of candidate positions, a plurality of path loss models and a plurality of candidate transmit powers of the target device based on the receive signal strength data, wherein computing comprises computing a position estimate of the target device by, for each candidate position and for a range of candidate transmit powers P_Tx of the target device;

computing {circumflex over (r)}=10 log₁₀[10<sup>0.1(PTx·

1−

L1)</sup>+10<sup>0.1·

NF</sup>], where

L1=[{circumflex over (L)}(u,u_sens(1)), . . . , {circumflex over (L)}(u,u_sens(N))]^T is a matrix composed of path loss estimates

{circumflex over (L)}(u,u_sens(1)) to {circumflex over (L)}(u,u_sens(N)) at candidate position u with respect to a radio sensor device at a corresponding known position and NF is the noise floor at a radio sensor device deployed at a corresponding known position;

computing a function

50. The method of claim 49, and further comprising storing candidate transmit powers for prior estimated positions of the target device and computing the median candidate transmit power from the stored candidate transmit powers for prior estimated positions of the target device.

51. A method for determining a position of a target device based on data pertaining to strength of an emission received from the target device at a plurality of known positions, the method comprising:

a. receiving an emission from the target device at each of a plurality of known positions to produce receive signal strength data, wherein the known positions are on each of the floors of a multi-storing building;

b. deriving received power data at each known position from the received radio emissions, where P(f,k) is the power received from the target device at the kth known position on floor f; and

c. computing a most likely position over a plurality of candidate positions and a plurality of candidate transmit powers of the target device based on the receive signal strength data, wherein computing comprises computing an average power per known position per floor P_avg(f)=Σ

_kP(f,k)/N(f), wherein N(f) is the number of known positions on floor f, and estimating that the target device is on floor f₀, where f₀ maximizes P_avg(f) over f.

52. A method for generating path loss estimate data associated with an area in which a plurality of radio sensor devices are deployed at known positions and used to determine a position of a target device in the area based on emissions received from the target device, the method comprising:

a. with respect to a test signal transmitted by each radio sensor device, measuring path loss at each of the other radio sensor devices to measure the path loss between all combinations of pairs of radio sensor devices;

b. for each radio sensor device, deriving parameters for a path loss model function by minimizing a mean squared error between the measured path loss between a radio sensor device and each of the other radio sensor devices and the path loss model function between that radio sensor device and each of the other radio sensor devices; and

c. computing a path loss estimate between a position and each radio sensor device by evaluating the path loss model function using the parameters derived for each radio sensor device.

53. The method of claim 52, wherein deriving comprises computing a minimum of a square of a norm of a difference between a vector representing measured path loss between a radio sensor device and each of the other radio sensor devices and a vector representing the path loss model function based on corresponding distances between the radio sensor device and each of the other radio sensor devices.

54. A system for determining a position of a target device based on data pertaining to strength of an emission received from the target device at a plurality of known positions, the system comprising:

a. a plurality of radio sensor devices at known positions within in an area, each radio sensor device capable of receiving radio emissions; and

b. a computing device coupled to the plurality of radio sensor devices and receive data therefrom that represents strength of signals received by the radio sensor devices from the target device, wherein the computing device estimates a most likely position of the target device over a plurality of candidate positions, a plurality of path loss models and a plurality of candidate transmit powers of the target device based on the receive signal strength data, wherein said computing device computes the most likely position by minimizing over the plurality of path loss models.

55. A method for determining the position of a target device that emits radio signals in a multi-story building, comprising:

a. deploying a plurality of radio sensor devices at known positions on each of the floors of a multi-storing building;

b. receiving radio emissions from the target device at the plurality of radio sensor devices and deriving received power data at each radio sensor device from the received radio emissions, where P(f,k) is the power received from the target device at the kth sensor on floor f;

c. computing an average power per sensor per floor P_avg(f)=Σ

_kP(f,k)/N(f), wherein N(f) is the number of sensors on floor f; and

d. estimating that the target device is on floor f₀, where f₀ maximizes P_avg(f) over f.

56. A method for generating path loss estimate data associated with an area in which radio emissions are received from a target device at a plurality of known positions to determine a position of the target device in the area, the method comprising:

a. with respect to a test signal transmitted by from each known position, measuring path loss at each of the other known positions to measure the path loss between all combinations of pairs of known positions;

b. evaluating a path loss model based on the distance between all combinations of pairs of known positions to produce path loss model data;

c. computing, relative to each known position, a path loss error between the measured path loss and the path loss model data when the path loss is measured at each of the other known positions relative to that known position;

d. interpolating a path loss error relative to each known position at a candidate position from the corresponding computed path loss errors using a multi-dimensional interpolation technique;

e. computing a path loss estimate between a candidate position and each known position by adding the interpolated path loss error relative to a known position at the candidate position to path loss data obtained by evaluating the path loss model based on a distance between a known position and the candidate position; and

f. computing a most likely position of the target device over the plurality of candidate positions.