Self-calibrated path loss position estimation and zone of impact determination

• US 20050285793A1
• Filed: 06/21/2005
• Published: 12/29/2005
• Est. Priority Date: 06/23/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Sugar, Gary L., Tesfai, Yohannes
• Granted Patent: US 7,317,419 B2
• Time in Patent Office: Days
• US Class Current: 342/465
• CPC Class Codes: G01S 11/06 using intensity measurements
• CPC Class Codes: G01S 5/02525 Gathering the radio frequency fingerprints
• CPC Class Codes: G01S 5/14 Determining absolute distances from a plurality of spaced points of known location

Abstract

A device and method are provided for estimating a position of a target device (e.g., a device emitting radio frequency energy) based on data pertaining to strength of an emission received from the target device. At a mobile device, emissions are received from the target device when the mobile device is at each of a plurality of positions to produce receive signal strength data representative thereof. In addition, at the mobile device, signals are received from each of a plurality of reference devices at a corresponding known position (and transmitted with known transmit powers) when the mobile device is at each of said plurality of positions to produce receive signal strength data representative thereof. The position of the target device is estimated based on receive signal strength data associated with received emissions from the target device and receive signal strength data associated with received signals from the reference devices. Using the estimated position and estimated transmit power of the target device, a zone of impact of the target device is determined with respect to other wireless activity based on the estimated position and estimated transmit power of the target device.

Claims

1. A method for determining an impact of a target device based on data pertaining to strength of an emission received from the target device, the method comprising:

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

b. computing an estimated position and an estimated transmit power of the target device over a plurality of candidate positions and a plurality of candidate transmit powers of the target device based on the receive signal strength data; and

c. determining a zone of impact of the target device with respect to other wireless activity based on the estimated position and estimated transmit power of the target device.

2. The method of claim 1, and further comprising displaying information depicting the zone of impact of the target device with based on its estimated position and estimated transmit power.

3. The method of claim 1, wherein computing comprises computing the estimated position by minimizing over a plurality of path loss models.

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

5. The method of claim 1, and further comprising storing one or more zone of impact parameters for a target device;

processing the estimated position and the estimated transmit power of the target device with respect to the one or more zone of impact parameters; and

displaying information depicting one or more zones of impact of the target device with respect to a map.

6. The method of claim 5, and further comprising receiving user input data associated with the one or more zone of impact parameters.

7. The method of claim 5, wherein storing comprises storing one or more of:

a transmit data rate threshold associated with a transmit data used by a wireless network access point device;

a carrier-to-interference ratio threshold associated with a wireless network access point device; and

transmit power threshold associated with the estimated transmit power of the target device.

8. The method of claim 7, wherein processing comprises determining whether a carrier-to-interference ratio associated with a wireless network access point is below a carrier-to-interference ratio threshold as a result of the estimated position and estimated transmit power of the target device.

9. The method of claim 8, and further comprising displaying on a map an indication of the zone in which the carrier-to-interference ratio is less than the carrier-to-interference ratio threshold as a result of the estimated position and estimated transmit power of the target device.

10. The method of claim 8, wherein processing comprises determining whether a transmit data rate used by a wireless network access point is less than the transmit data rate threshold as a result of the estimated position and estimated transmit power of the target device.

11. The method of claim 9, and further comprising displaying on a map an indication of the zone in which the transmit data rate for the wireless network access point has been reduced to be less than the transmit data rate threshold as a result of the estimated position and estimated transmit power of the target device.

12. The method of claim 11, wherein displaying comprises displaying on the map an indication of a zone in which one or more wireless applications or services are not available as a result of the reduced transmit data rate of the wireless network access point.

13. The method of claim 1, and further comprising generating path loss estimate data with respect to each of the plurality of positions which are known positions, 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 combinations of pairs of known positions;

ii. evaluating a path loss model based on the distance between 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.

14. The method of claim 13, 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.

15. The method of claim 13, 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.

16. The method of claim 1, and further comprising generating estimated path loss data with respect to each of the plurality of positions, which are known positions, 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.

17. The method of claim 16, 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.

18. The method of claim 17, 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.

19. The method of claim 1, 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 positions.

20. The method of claim 1, wherein computing comprises computing a position u*, where

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

22. The method of claim 20, 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

23. The method of claim 20, 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

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

25. The method of claim 24, 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.

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

27. The method of claim 1, 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:

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 a corresponding position which is a known position and NF is the noise floor at each corresponding known position;

b. computing a function

$J<br><br>\left(u,P_{\mathrm{Tx}}\right)=\underset{n=1}{\overset{\mathrm{Nseq}}{\sum <br><br>}}<br><br>\left[{<br><br>{\mathrm{r1}}_n-\hat{r}<br><br>}^2+\mathrm{\cdots <br><br>}+{<br><br>{\mathrm{rP}}_n-\hat{r}<br><br>}^2\right]$

for each candidate position u and candidate transmit power P_Tx, where {r1n}, . . . ,{rPn}, n=1, . . . ,Nseq, are receive signal strength observations on P antennas of each of the plurality of known positions; and

c. selecting the candidate position that minimizes the function J(U,P_Tx) over all candidate positions and transmit powers.

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

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

30. The method of claim 28, 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.

31. The method of claim 28, 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.

32. The method of claim 1, 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:

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 a corresponding position which is known position and NF is the noise floor at the corresponding known position;

b. computing a function

$J<br><br>\left(u,P_{\mathrm{Tx}}\right)=\underset{n=1}{\overset{\mathrm{Nseq}}{\sum <br><br>}}<br><br>\left[{<br><br>{\mathrm{r1}}_n-\hat{r}<br><br>}^2+\mathrm{\cdots <br><br>}+{<br><br>{\mathrm{rP}}_n-\hat{r}<br><br>}^2\right]$

for each candidate position u and candidate transmit power P_Tx,, where {r1n}, . . . ,{rPn}, n=1, . . . , Nseq, are receive signal strength observations on P antennas of each of the plurality of known positions;

c. selecting a set of candidate position/candidate transmit power pairs that are the N minimum of the function J(u,P_Tx); and

d. selecting the candidate position/transmit power pair in the set of candidate position/candidate transmit power pairs that minimizes an absolute value of the difference between the candidate transmit power and a median of candidate transmit powers for the target device at prior estimated positions, wherein the candidate position in the selected candidate position/candidate transmit power pair is the position estimate of the target device.

33. The method of claim 32, 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.

34. The method of claim 1, wherein (a) receiving, (b) computing and (c) determining are performed in a mobile device that moves to each of the plurality of positions when receiving emissions from the target device.

35. A method for estimating a position of a target device based on data pertaining to strength of an emission received from the target device, the method comprising:

a. receiving at a mobile device an emission from the target device when the mobile device is at each of a plurality of positions and producing receive signal strength data representative thereof;

b. receiving at the mobile device a signal from each of a plurality of reference devices at a corresponding position when the mobile device is at each of said plurality of positions and producing receive signal strength data representative thereof, and

c. estimating a position of the target device based on receive signal strength data associated with receive emissions from the target device and received signal strength data associated with received signals from the reference devices.

36. The method of claim 35, wherein estimating comprises computing a most likely position of the target device over a plurality of candidate positions.

37. The method of claim 36, wherein estimating further comprises computing a most likely transmit power of the target device over a plurality of candidate transmit powers.

38. The method of claim 37, and further comprising determining a zone of impact of the target device with respect to other wireless activity based on the estimated position and estimated transmit power of the target device.

39. The method of claim 38, and further comprising displaying information depicting the zone of impact of the target device based on its estimated position and estimated transmit power.

40. The method of claim 35, wherein estimating comprises computing the estimated position by minimizing over a plurality of path loss models.

41. The method of claim 35, wherein estimating comprises generating path loss estimate data with respect to each measurement position where the mobile device makes measurements from signals received from the reference devices by:

a. measuring path loss at each mobile device measurement position with respect to the positions of each of the reference devices;

b. evaluating a path loss model based on the distance between all combinations of pairs of mobile device measurement positions and reference device positions to produce path loss model data;

c. computing, relative to each mobile device measurement position, a path loss error between the measured path loss and the path loss model data;

d. interpolating a path loss error relative to each mobile device measurement position at a candidate position from the corresponding computed path loss errors; and

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

42. The method of claim 41, wherein interpolating the path loss error comprises interpolating the path loss error relative to each mobile device measurement position at each candidate position using a multi-dimensional interpolation technique.

43. The method of claim 35, wherein estimating comprises computing a position u*, where

44. The method of claim 35, wherein estimating comprises computing the most likely position over a plurality of candidate positions, a plurality of candidate transmit powers and a plurality of path loss models.

45. The method of claim 35, wherein estimating further comprises computing the most likely position by minimizing over a plurality of path loss models.

46. The method of claim 35, wherein computing comprises processing received signal strength data obtained at each of the plurality of mobile device measurement positions with respect to estimated path loss data with respect to each mobile device measurement positions position.

47. The method of claim 35, wherein computing comprises computing a position u*, where

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

49. The method of claim 47, 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

50. The method of claim 47, 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

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

52. The method of claim 51, 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.

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

54. The method of claim 35, 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:

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 a mobile device measurement position and NF is the noise floor at each mobile device measurement position;

b. computing a function

$J<br><br>\left(u,P_{\mathrm{Tx}}\right)=\underset{n=1}{\overset{\mathrm{Nseq}}{\sum <br><br>}}<br><br>\left[{<br><br>r<br><br>\text{\hspace{1em}<br><br>}<br><br>1_n-\hat{r}<br><br>}^2+\mathrm{\dots <br><br>}+{<br><br>r<br><br>\text{\hspace{1em}<br><br>}<br><br>P_n-\hat{r}<br><br>}^2\right]$

for each candidate position u and candidate transmit power P_Tx, where {r1n}, . . . ,{rPn}, n=1, . . . ,Nseq, are receive signal strength observations on P antennas of the mobile device at each mobile device measurement position; and

c. selecting the candidate position that minimizes the function J(u,P_Tx) over all candidate positions and transmit powers.

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

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

57. The method of claim 56, 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.

58. The method of claim 57, 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.

59. A radio device comprising:

a. a radio receiver that receives radio frequency energy;

b. an analog-to-digital converter that converts the radio frequency energy to digital signals representative thereof;

c. a processor coupled to the analog-to-digital converter, wherein the processor;

i. generates receive signal strength data representing strength of signals received from a target device to be located when the radio device is at each of a plurality of positions;

ii. generates receive signal strength data representing strength of signals received from each of a plurality of reference devices at a corresponding known position when the radio device is at each of said plurality of positions; and

iii. estimates a position of the target device based on the receive signal strength data associated with received emissions from the target device and receive signal strength data associated with received signals from the reference devices.

60. The radio device of claim 59, wherein the processor estimates the position of the target device by generating path loss estimate data with respect to each measurement position where the device receives a reference signal from a reference device, by:

i. measuring path loss at each measurement position with respect to the positions of each of the reference devices, wherein each measurement position is a known position;

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

iii. computing, relative to each measurement position, a path loss error between the measured path loss and the path loss model data;

iv. interpolating a path loss error relative to each measurement 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 measurement position by adding the interpolated path loss error relative to a measurement position at the candidate position to path loss data obtained by evaluating the path loss model based on a distance between a measurement position and the candidate position.

61. The radio device of claim 60, wherein the processor interpolates the path loss error by interpolating the path loss error relative to each measurement position at each of a plurality of candidate positions, and the processor computes the path loss estimate by computing a path loss estimate between each of the plurality of candidate positions and each measurement position by adding the interpolated path loss error relative to a measurement position at each candidate position to path loss data obtained by evaluating the path loss model based on a distance between the mobile device positions and the corresponding candidate position.

62. The radio device of claim 60, wherein the processor interpolates the path loss error using a multi-dimensional interpolation technique.

63. The radio device of claim 60, wherein the processor estimates the position of the target device by computing a position u*, where

64. The radio device of claim 59, wherein the processor further estimates a transmit power of the target device.

65. The radio device of claim 64, wherein the processor determines a zone of impact of the target device with respect to other wireless activity based on the estimated position and estimated transmit power of the target device.

66. The radio device of claim 64, wherein the processor generates display information depicting the zone of impact by the target device based on the estimated position and estimated transmit power.

67. The radio device of claim 64, and further comprising a memory that stores one or more zone of impact parameters for a target device, wherein the processor processes the estimated position and the estimated transmit power of the target device with respect to the one or more zone of impact parameters generates display information depicting one or more zones of impact of the target device with respect to a map.

68. The radio device of claim 67, wherein the memory stores one or more of:

(a) a transmit data rate threshold associated with a transmit data used by a wireless network access point device;

(b) a carrier-to-interference ratio threshold associated with a wireless network access point device; and

transmit power threshold associated with the estimated transmit power of the target device.

69. The radio device of claim 59, wherein the processor estimates the position of the target device using information pertaining to an aspect ratio of the region of interest in which measurements are made.

70. The radio device of claim 69, wherein the processor estimates the position of the target device using the information pertaining to the aspect ratio of the region, and wherein the measurement positions may be unknown positions.

71. A radio device comprising:

a. a radio receiver that receives radio frequency energy;

b. an analog-to-digital converter that converts the radio frequency energy to digital signals representative thereof;

c. a processor coupled to the analog-to-digital converter, wherein the processor;

i. produces receive signal strength data from an emission received from the target device at each of a plurality of known positions to produce receive signal strength data

ii. computes an estimated position and an estimated transmit power of the target device over a plurality of candidate positions and a plurality of candidate transmit powers of the target device based on the receive signal strength data; and

iii. determines a zone of impact of the target device with respect to other wireless activity based on the estimated position and estimated transmit power of the target device.