Method and apparatus for location estimation
First Claim
Patent Images
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 having unknown locations to obtain a signal measurement;
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; and
estimating locations for the first and second wireless devices based at least in part on the optimized function.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
45 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 having unknown locations to obtain a signal measurement;
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; and
estimating locations for the first and second wireless devices based at least in part on the optimized function. - View Dependent Claims (2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 36, 37)
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.
-
-
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:
-
where (x′
i, y′
i, z′
i) is a set of coordinates for an ith reference device determined by using a reference location technology,(xi, yi, zi) is a set of postulated coordinates for an ith wireless device, R is a sub-set of wireless devices involved in determining each others location that are equipped with a reference location technology, and σ
x σ
y, σ
z are respectively, the standard deviations with which the reference location technology is able to measure x, y, and z coordinates of the reference devices.
-
-
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:
-
where, d′
i,j is the distance between the an ith device and a jth device, as determined from a signal power measurement,(x′
i, y′
i, z′
i) is a set of coordinates for an ith reference device determined by using a reference location technology,(xi, yi, zi) is a set of postulated coordinates for an ith wireless device, σ
x σ
y, σ
z are respectively, the standard deviations with which the reference location technology is able to measure x, y, and z coordinates of the reference devices,σ
dB is a standard deviation ascribed to a measurement process used to make signal power measurements, anddth is the distance separating a receiving wireless device from a transmitting wireless device at which a signal received will be at a threshold level for detection.
-
-
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:
-
where xi is a postulated x coordinate of an ith device yi is a postulated y coordinate of the ith device xs is an x coordinate of a device equipped with a smart antenna, ys is an y coordinate of the device equipped with the smart antenna, θ
i is the angle to the ith device measured by the smart antenna DOA algorithm, andσ
θ
is the standard deviation that characterizes the error in the measurement of θ
m.
-
-
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:
-
where, angle_meas(i,j,k) is the difference measured using a smart antenna at an ith device between a direction toward a jth device and the direction toward a kth device, σ
angle is a standard deviation of the error in measuring angle_meas(i,j,k),m(i) is a number of wireless devices within range of the ith device, angle_post(i,j,k) is found using the law of cosines to be;
where
where(Xi,Yi,Zi) (Xj,Yj,Zj) (Xk,Yk,Zk) are postulated coordinates of the ith, jth and kth wireless devices respectively.
-
-
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;
do is a reference distance used to make a reference measurement, where Pi,j is a power in decibels predicted to reach the first device from the second device, Po is a power meassurement at the calibration distance,
where(Xi,Yi,Zi) is a set of postulated coordinates for the first device, and (Xj,Yj,Zj) 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;
wheredo is a reference distance used to make a reference measurement, Pi,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,
where(Xi,Yi,Zi) is a set of postulated coordinates for the ith device, (Xj,Yj,Zj) 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, Xl is the attenuation of an Ith type of barrier in the environment, Ai,jl is the number of barriers of the Ith 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 Ai,jl 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.
-
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:
-
where i is a first index that denotes an ith wireless devices involved in a location estimation calculation, j is a second index that denotes a jth wireless devices involved in a location estimation calculation, N is a number of wireless devices involved in estimating each other'"'"'s location, Hi is a set of all wireless devices that are in range of an ith wireless device, P′
i,j is a measurement of power transmitted between the ith device and a jth wireless device,Pi,j is an estimate of P′
i,j based on a channel attenuation model, and postulated coordinates for the ith and jth devices, andσ
dB is a standard deviation ascribed to a measurement process used to measure P′
i,j.
-
-
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:
-
where (x′
i, y′
i, z′
i) is a set of coordinates for an ith reference device determined by using a reference location technology,(xi, yi, zi) is a set of postulated coordinates for an ith wireless device, R is a sub-set of wireless devices involved in determining each others location that are equipped with a reference location technology, and σ
x σ
y, σ
z are respectively, the standard deviations with which the reference location technology is able to measure x, y, and z coordinates of the reference devices.
-
-
3. 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;
wherein the step of optimizing the function comprises the sub-step of optimizing a function that includes a sub-expression of the form;
wherei is a first index that denotes an ith wireless devices involved in a location estimation calculation, j is a second index that denotes a jth wireless devices involved in a location estimation calculation, N is a number of wireless devices involved in estimating each other'"'"'s location, Hi is a set of all wireless devices that are in range of an ith wireless device, device, Pi,j is an estimate of P′
i,j based on a channel attenuation model, and postulated coordinates for the ith and jth devices, andσ
dB is a standard deviation ascribed to a measurement process used to measure P′
i,j, andPthresh is the threshold power which can be detected by a wireless device.
-
-
33. 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;
wherein the step of optimizing the function comprises the sub-step of;
optimizing a function that includes a sub-expression of the form;
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, Hi is a number of device within range of the ith device, di,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.- View Dependent Claims (34, 35)
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.
-
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. - View Dependent Claims (39)
an external system communication interface system.
-
-
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 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 having unknown locations to obtain a signal measurement;
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; and
estimating locations for the first and second wireless devices based at least in part on the optimized function. - View Dependent Claims (42, 43, 44, 45)
optimizing a function that depends on a standard deviation of the signal measurement.
-
-
43. The computer readable medium according to claim 41 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.
-
44. The computer readable medium according to claim 41 further including programming instructions for:
receiving a measurement of a second signal transmitted between the second device and a first reference device.
-
45. The computer readable medium according to claim 41 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.
Specification