Method and apparatus for location estimation

• US 20020122003A1
• Filed: 01/05/2001
• Published: 09/05/2002
• Est. Priority Date: 01/05/2001
• Status: Active Grant

• Current Assignee: Motorola Solutions, Inc.
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Perkins, Matthew R., Allen, Vernon A., Bourgeois, Monique J., Patwari, Neal K., OʼDea, Robert J.
• Granted Patent: US 6,473,038 B2
• Time in Patent Office: Days
• US Class Current: 342/450
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01S 11/02 using radio waves G01S19/00 takes precedence
• CPC Class Codes: G01S 13/84 for distance determination by phase measurement
• CPC Class Codes: G01S 2205/002 for traffic control, mobile tracking, guidance, surveillance or anti-collision
• CPC Class Codes: G01S 5/0018 Transmission from mobile station to base station
• CPC Class Codes: G01S 5/0072 Transmission between mobile stations, e.g. anti-collision systems
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks

Abstract

A system for locating a number of devices (112-130) by measuring signals transmitted between known location devices (112-118, 134-138, 214-218, 224-228) and unknown location devices (120-130, 222), and signals transmitted between pairs of unknown location devices (120-130, 222), entering signal measurements into a graph function that includes a number of first sub-expressions, a number of which include signal measurement prediction sub-expressions, and have extrema when a predicted signal measurement is equal to an actual signal measurement, and optimizing the graph function.

Claims

1. A method of estimating unknown locations of wireless devices, the method including the steps of:

receiving a measurement of a first signal transmitted between the first and the second wireless devices to obtain a signal measurement, and

optimizing a function that depends on the signal measurement, a set of postulated coordinates for the first wireless device, and a set of postulated coordinates for the second wireless devices.

2. The method according to claim 1 wherein the step of receiving a measurement of a signal includes the sub-step of:

receiving a measurement of an offset time that depends on a difference between a first time at which a second signal was sent from the first device to a second device and a second time at which the first signal was received at the first device after being sent by the second device in response to the second signal.

3. The method according to claim 1 wherein the step of optimizing the function comprises the sub-step of optimizing a function that includes a sub-expression of the form:

4. The method according to claim 1 wherein the step of optimizing the function comprises the sub-step of optimizing a function that includes a sub-expression of the form:

5. The method according to claim 1 wherein the step of optimizing the function comprises the sub-step of optimizing a function that includes a sub-expression of the form:

6. The method according to claim 1 wherein the step of optimizing the function comprises the sub-step of optimizing a function that includes a sub-expression of the form:

7. The method according to claim 1 wherein the step of optimizing the function comprises the sub-step of optimizing a function that includes a sub-expression of the form:

8. The method of claim 1 further comprising the steps of:

detecting a signal from an accelerometer, and

initiating a step of measuring a signal and the step of optimizing in response to detecting the signal.

9. The method according to claim 1 further comprising a step of:

calculating a distance between the first and second wireless devices based on the measurement.

10. The method according to claim 1 wherein the step of optimizing includes a sub-step of:

optimizing a function that depends on a statistical model parameter.

11. The method according to claim 10 wherein the step of optimizing includes a sub-step of:

optimizing a function that depends on a standard deviation of the signal measurement.

12. The method of claim 1 further comprising the step of:

Determining that a third device and the first device are out of range of each other,

13. The method according to claim 12 wherein the step of optimizing comprises the sub-step of:

optimizing a function that includes a sub-expression that depends on a distance between the first and third devices, that is determined based on a set of postulated coordinates for the set of postulated coordinates for the first device, and is a monotonic function of the distance between the first and third devices.

14. The method according to claim 13 wherein the step of optimizing comprises the sub-step of:

optimizing a function that includes a sub-expression that depends on a distance between the first and third devices, that is determined based on a set of postulated coordinates for the set of postulated coordinates for the first device, and asymptotically approaches a fixed value as the distance between the first and third devices increases.

15. The method according to claim 12 wherein the step of optimizing comprises the sub-step of:

optimizing a function that includes a sub-expression that depends on a distance between the first and third devices, that is determined based on a set of postulated coordinates for the set of postulated coordinates for the first device, and has an extremum at a distance greater than a threshold distance for communication between the first and third devices.

16. The method according to claim 1 wherein the step of optimizing a function comprises the sub-step of:

optimizing a function that includes a first sub-expression that depends on the postulated coordinates of the first device, and a second sub-expression that depends on the postulated coordinates of the first device.

17. The method according to claim 16 wherein the step of optimizing a function comprises the sub-step of:

optimizing a function that includes a first sub-expression that depends on the postulated coordinates of the first device, and the postulated coordinates of the second device, and a third sub-expression that depends on the postulated coordinates of the second device.

18. The method according to claim 1 further comprising the step of:

receiving a measurement of a second signal transmitted between the second device and a first reference device.

19. The method according to claim 18 wherein the step of optimizing the function includes the sub-step of:

optimizing a function including a sub-expression that depends on a set of postulated coordinates for the first reference device.

20. The method according to claim 19 wherein the step of receiving a measurement of the first signal transmitted between the second device and the first reference device includes the sub-step of:

receiving a measurement of an angle at which the signal arrives at the first reference device to obtain a first angle measurement, and

wherein the step of optimizing the function includes the sub-step of;

optimizing a function including a sub-expression that depends on the set of postulated coordinates for the second device and the first angle measurement.

21. The method according to claim 20 wherein the step of receiving a measurement of a signal comprises the sub-step of:

receiving a measurement of a first angle at which the first signal arrives at the first device from the second device to obtain a first angle measurement.

22. The method according to claim 21 further comprising the step of:

receiving a measurement of a second angle at which a second signal arrives at the first device from a third device to obtain a second angle measurement.

23. The method according to claim 22 herein the step of optimizing the function comprises the sub-step of:

optimizing a function that depends on a difference between the first angle measurement and the second angle measurement, and postulated coordinates for the first, second, and third devices.

24. The method according to claim 1 wherein the step of optimizing the function comprises the sub-step of:

optimizing a function that includes a first sub-expression that gives a predicted signal measurement based on the postulated coordinates.

25. The method according to claim 24 wherein the step of optimizing the function comprises the sub-step of:

optimizing a function that includes a second sub-expression that includes the first sub-expression and has an extrememum when the signal measurement equals the predicted signal measurement.

26. The method according to claim 25 wherein the step of optimizing the function comprises the sub-step of:

optimizing a function that includes a channel model that predicts the signal measurement based on the postulated coordinates.

27. The method according to claim 26 further comprising the steps of:

making a signal measurement at a reference device to obtain a reference measurement,

obtaining a location estimate for the reference device, and

selecting channel model parameters by fitting the channel model to data that includes the location estimate and the reference measurement.

28. The method according to claim 27 wherein the step of optimizing the function that includes a channel attenuation model comprises the sub-step of:

optimizing a function that includes a channel attenuation model sub-expression of the form;

$P_{i,j}=P_o<br><br>\left(d_0\right)-10<br><br>n<br><br>\text{\hspace{1em}<br><br>}<br><br>\log <br><br>\left(\frac{d_{i,j}}{d_o}\right)<br><br>\left(\mathrm{CH\_A}<br><br>\_<br><br>1\right)$

do is a reference distance used to make a reference measurement,

where

P_i,j is a power in decibels predicted to reach the first device from the second device,

Po is a power measurement at the calibration distance,

d_i,j={square root}{square root over ((X_i−

X_j)²+(Y_i−

Y_j)²+(Z_i−

Z_j)²)}

where

(X_i,Y_i,Z_i) is a set of postulated coordinates for the first device, and

(X_j,Y_j,Z_j) is a set of postulated coordinates for the second device, and

n is an experimentally determined parameter for a given environment, that characterizes a loss in power as a function of distance.

29. The method of claim 28 further comprising the steps of:

receiving a measurement of the power transmitted between a first reference device and a second reference device to obtain a first power measurement,

obtaining location estimates for the first and second reference devices,

selecting the value of n by fitting the channel attenuation model to first power measurement, and the location estimates for the first and second reference devices.

30. The method according to claim 26 wherein the step of optimizing the function that includes a channel attenuation model comprises the sub-step of:

optimizing a function that includes a channel attenuation model of the form;

$P_{i,j}=P_o<br><br>\left(d_0\right)-10<br><br>n<br><br>\text{\hspace{1em}<br><br>}<br><br>\log <br><br>\left(\frac{d_{i,j}}{d_o}\right)-\underset{l=1}{\overset{M}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>X_l<br><br>A_{i,j}^l$

where

do is a reference distance used to make a reference measurement,

P_i,j is a power in decibels predicted to reach an ith device from a jth device,

Po is a power measurement at the calibration distance,

d_i,j={square root}{square root over ((X_i−

X_j)²+(Y_i−

Y_j)²+(Z_i−

Z_j)²)}

where

(X_i,Y_i,Z_i) is a set of postulated coordinates for the ith device,

(X_j,Y_j,Z_j) is a set of postulated coordinates for the jth device, and

n is an experimentally determined parameter for a given environment, that characterizes a loss in power as a function of distance,

M is the number of types of barriers in the particular environment,

X_l is the attenuation of an lth type of barrier in the environment,

A_i,^l_j is the number of barriers of the lth type that are intercepted by a line between postulated positions of the ith and jth devices.

31. The method of claim 30 further comprising the steps of:

performing a plurality of signal measurements between reference devices to obtain a plurality of reference signal measurements,

obtaining location estimates for reference devices involved in the plurality of signal measurements, and

determining values for A_i,^l_j and n by fitting the channel attenuation model to the plurality of reference signal measurements and location estimates.

32. The method of claim 31 wherein the step of performing a plurality of measurements includes the sub-step of:

performing a least M+2 signal measurements between reference devices to obtain a plurality of reference signal measurements.

33. The method according to claim 1 wherein the step of optimizing the function comprises the sub-step of:

optimizing a function that includes a sub-expression of the form;

$\mathrm{Sub\_Exp}<br><br>\_<br><br>11=\underset{i=1}{\overset{N}{\prod <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{j\in <br><br>H_i,j\ne <br><br>i}{\overset{\text{\hspace{1em}<br><br>}}{\prod <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left\{\exp <br><br>\left[-\frac{1}{2}<br><br>{\left(\frac{d_{i,j}-d_{i,j}^{,}}{{\mathrm{\sigma <br><br>}}_d}\right)}^2\right]\right\}$

where,

i denotes an ith wireless device involved in a location estimation calculation,

j denotes a jth wireless devices involved in a location estimation calculation,

N is a number of devices involved in a location estimate,

H_i is a number of device within range of the ith device,

d_i,j is a distance between the ith and the jth device in terms of postulated coordinates,

d′

_i,j depends on the measurement of distance separating the ith and jth devices that is deduced from the signal measurement, and

σ

_d is a is an uncertainty that characterizes the signal measurement.

34. The method according to claim 33 further comprising the step of:

calculating a value of d′

_i,j by operating on a measured distance using a formula that returns a value which is less than the measured distance.

35. The method according to claim 33 further comprising the steps of:

calculating a value of d′

_i,j by subtracting a predetermined value from a measured distance.

36. The method according to claim 1 wherein the step of optimizing the function comprises the sub-step of optimizing a function that includes a sub-expression of the form:

37. The method according to claim 36 wherein the step of optimizing the function comprises the sub-step of optimizing a function that includes a sub-expression of the form:

39. The processing node according to claim 38 further comprising:

an external system communication interface system.

38. A processing node comprising:

a receiver for receiving a first result of a first signal measurement of a first signal transmitted between a first unknown location device and a second unknown location device, and

a second result of a second signal measurement of a second signal transmitted between the second unknown location device and a known location device,

a processor for optimizing a function of the first signal measurement, the second signal measurement, postulated coordinates of the first unknown location device, and the second unknown location device in terms of postulated coordinates of the first unknown location device, and the second unknown location device,

whereby locations of the first and second unknown location devices are estimated.

40. A location estimation system comprising:

a plurality of wireless devices, each comprising;

a signal measurer, and

a transmitter for transmitting a signal measurement, and

a processing node comprising;

a receiver for receiving

a first result of a first signal measurement of a first signal transmitted between a first unknown location device and a second unknown location wireless device,

a second result of a second signal measurement of a second signal transmitted between the second unknown location wireless device and a known location device, and

a processor for optimizing a function of the first signal measurement, the second signal measurement, postulated coordinates of the first unknown location device, and the second unknown location device in terms of postulated coordinates of the first unknown location device, and the second unknown location device.

41. A method of responding to a two-way time of arrival signal the method comprising the steps of:

receiving a pseudo random sequence having a first duration,

phase locking a clock to a frequency of the pseudo random sequence,

waiting a random multiple of the first duration as measured using the clock, and

transmitting the pseudo random sequence.

42. A method of measuring a distance to a remote transceiver, the method comprising the steps of:

transmitting a pseudo random sequence of a first duration at a first time,

receiving the pseudo random sequence after a second duration counted from the first time that is larger than the first duration, and

comparing the phase of a received pseudo random sequence to the phase of a locally generated pseudo random sequence.

44. The transceiver according to claim 42 wherein the means for measuring comprises a signal strength measurer.

45. The transceiver according to claim 42 wherein the means for measuring comprises:

a pseudo random number generator,

a modulator electrically coupled to the pseudo random generator,

an antenna electrically coupled to the modulator,

a demodulator electrically coupled to the antenna,

a correlator electrically coupled to the pseudo random number generator, and the demodulator, and

a phase measurer coupled to the correlator.

46. The transceiver according to claim 42 further comprising:

a base band phase locked loop electrically coupled to the demodulator.

48. The computer readable medium according to claim 47 wherein the programming instructions for optimizing includes programming instructions for:

optimizing a function that depends on a standard deviation of the signal measurement.

49. The computer readable medium according to claim 47 wherein the programming instructions for optimizing a function include programming instructions for:

optimizing a function that includes a first sub-expression that depends on the postulated coordinates of the first device, and a second sub-expression that depends on the postulated coordinates of the first device.

50. The computer readable medium according to claim 47 further including programming instructions for:

receiving a measurement of a second signal transmitted between the second device and a first reference device.

51. The computer readable medium according to claim 47 wherein the programming instructions for optimizing the function include programming instructions for:

optimizing a function including a sub-expression that depends on a set of postulated coordinates for the first reference device.

43. A transceiver comprising:

a means for measuring a plurality of signals received form a plurality of transceivers to obtain a plurality of signal measurement;

a means for communicatively coupling the plurality of signal measurement to a processing node.

47. A computer readable medium containing programming instructions for of estimating locations of a set of wireless devices including a first wireless device and a second wireless device the locations of which are unknown, the computer readable medium including programming instructions for:

receiving a measurement of a first signal transmitted between the first and the second wireless devices to obtain a signal measurement, and

optimizing a function that depends on the signal measurement, a set of postulated coordinates for the first device, and a set of postulated coordinates for the second wireless devices.