Method and apparatus for providing accurate position estimates in instances of severe dilution of precision

• US 6,505,122 B1
• Filed: 08/03/2001
• Issued: 01/07/2003
• Est. Priority Date: 06/25/2001
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Vayanos, Alkinoos H.
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Hernandez, Olga
• Application Number:
  US09/922,472
• Publication Number:
  US 20030004640A1
• Time in Patent Office: 522 Days
• Field of Search: 701/213, 701/215, 701/225, 701/200, 342/357.01, 342/357.02, 342/357.06, 342/357.08, 342/357.11
• US Class Current: 701/213
• CPC Class Codes: G01S 19/46 the supplementary measurement being of a radio-wave signal type
• CPC Class Codes: G01S 19/48 by combining or switching between position solutions derived from the satellite radio beacon positioning system and position solutions derived from a further system
• CPC Class Codes: G01S 5/14 Determining absolute distances from a plurality of spaced points of known location

Abstract

Techniques for providing an improved position estimate for a device in instances of relatively large dilution of precision. In a method, position estimates for a number of transmitters (e.g., GPS satellites and/or base stations) and a set of initial measurements (e.g., pseudo-ranges) are initially received. An Update Vector for a current device position estimate is computed. Non-convergence of the current device position estimate toward a target position estimate is detected and, if true, the Update Vector is adjusted (e.g., reduced in magnitude by a scaling factor) to increase the likelihood of convergence to the target position estimate. The current device position estimate is then updated based on the (possibly adjusted) Update Vector. Non-convergence may be detected based on the number of iterations performed without reaching the target position estimate and/or phase reversal in two consecutive Update Vectors. The scaling factor may be increased with each detected event indicative of non-convergence.

Claims

1. A method for determining an accurate device position estimate, comprising:

executing an iterative algorithm to provide a device position estimate, wherein the iterative algorithm is based on an initial device position estimate, transmitter position estimates for a plurality of transmitters, and an actual measurement vector;

determining whether convergence of the iterative algorithm is likely;

if convergence of the iterative algorithm is unlikely, adjusting at least one parameter of the iterative algorithm to increase the likelihood of convergence;

calculating an update vector for a current device position estimate based on a Residual Measurement Error Vector, the Transmitter Position Estimates, and the most recent Device Position Estimate calculated by the iterative algorithm;

calculating the norm of the update vector; and

wherein convergence is determined to be unlikely based on the value of the norm of the update vector.

2. A method for determining an accurate device position estimate, comprising:

executing an iterative algorithm to provide a device position estimate, wherein the iterative algorithm is based on an initial device position estimate, transmitter position estimates for a plurality of transmitters, and an actual measurement vector;

determining whether convergence of the iterative algorithm is likely;

if convergence of the iterative algorithm is unlikely, adjusting at least one parameter of the iterative algorithm to increase the likelihood of convergence;

calculating an update vector for a current device position estimate based on a Residual Measurement Error Vector, the Transmitter Position Estimates, and the most recent Device Position Estimate calculated by the iterative algorithm, wherein a function of the Residual Measurement Vector is included in a metric;

calculating the norm of the update vector; and

wherein convergence is determined to be unlikely based on the value of the norm of the update vector.

3. A method for determining an accurate device position estimate, comprising:

executing an iterative algorithm to provide a device position estimate, wherein the iterative algorithm is based on an initial device position estimate, transmitter position estimates for a plurality of transmitters, and an actual measurement vector;

determining whether convergence of the iterative algorithm is likely;

if convergence of the iterative algorithm is unlikely, adjusting at least one parameter of the iterative algorithm to increase the likelihood of convergence;

calculating an update vector for a current device position estimate based on a Residual Measurement Error Vector, the Transmitter Position Estimates, and the most recent Device Position Estimate calculated by the iterative algorithm, wherein a function of the Residual Measurement Vector is included in a metric and wherein the function is linear;

calculating the norm of the update vector; and

wherein convergence is determined to be unlikely based on the value of the norm of the update vector.

4. A method for determining an accurate device position estimate, comprising:

executing an iterative algorithm to provide a device position estimate, wherein the iterative algorithm is based on an initial device position estimate, transmitter position estimates for a plurality of transmitters, and an actual measurement vector;

determining whether convergence of the iterative algorithm is likely;

if convergence of the iterative algorithm is unlikely, adjusting at least one parameter of the iterative algorithm to increase the likelihood of convergence;

calculating an update vector for a current device position estimate based on a Residual Measurement Error Vector, the Transmitter Position Estimates, and the most recent Device Position Estimate calculated by the iterative algorithm, wherein a function of the Residual Measurement Vector is included in a metric and wherein the function is quadratic;

calculating the norm of the update vector; and

wherein convergence is determined to be unlikely based on the value of the norm of the update vector.

5. A method for determining a device position estimate, comprising:

determining transmitter position estimates for a plurality of transmitters and measuring an actual measurement vector for the transmitters;

determining an initial device position estimate;

determining a calculated measurement vector based on the transmitter position estimates and the initial device position estimate;

revising the device position estimate based on the difference between the calculated measurement vector, and the actual measurement vector;

determining that convergence of the current device position estimate toward a final device position estimate is unlikely; and

if convergence is determined to be unlikely, adjusting the manner in which the revised device position estimate is determined to increase the likelihood of convergence.

6. The method of claim 5, wherein the revised device position estimate is calculated using a least mean square (LMS) algorithm.

7. The method of claim 5, wherein the difference between the calculated measurement vector, and the actual measurement vector is a residual measurement vector, and the manner for determining the revised device position estimate is adjusted by scaling a value derived from the residual measurement error vector.

8. The method of claim 7, wherein the value derived from the residual measurement error vector is an update vector.

9. The method of claim 5, further comprising:

determining a geometry matrix based on the current device position estimate and the transmitter position estimate; and

determining a measurement covariance matrix, and

wherein the adjustment is further based on the geometry matrix and the measurement covariance matrix.

10. The method of claim 5, further comprising:

repeating the steps of claim 5 iteratively until either the iterative algorithm converges to a final device position estimate, or a determination is made that convergence is unlikely.

11. The method of claim 5, wherein the step of adjusting the device position estimate includes:

determining a scaling factor which effects the amount of the adjustment to the device position estimate.

12. The method of claim 11, wherein the scaling factor is increased with each iteration during which convergence is determined to be unlikely.

13. The method of claim 12, wherein the convergence is determined to be unlikely based on phase reversals in the update vector.

14. The method of claim 12, wherein the scaling factor is not increased in response to the first predetermined number of iterations resulting in a determination that convergence is unlikely.

15. The method of claim 8, further including:

limiting the magnitude of the update vector based on the magnitude of a residual measurement error vector as computed when a determination has been made that convergence is unlikely.

16. The method of claim 10, wherein non-convergence is detected based in part on the number of iterations performed without reaching the target position estimate.

17. The method of claim 16, wherein non-convergence is further detected based on the update vector.

18. The method of claim 17, wherein non-convergence is detected if the number of iterations exceeds a first threshold and a phase difference between two consecutive updates for two iterations is less than a second threshold.

19. The method of claim 18, wherein the phase difference between two consecutive updates is derived by performing a dot product on the two consecutive updates.

20. The method of claim 10, further comprising:

providing the current device position estimate as a final position estimate for the device if one or more criteria for termination are met.

21. The method of claim 20, wherein the one or more criteria for termination are met if the number of iterations exceeds a first threshold.

22. The method of claim 20, wherein the one or more criteria for termination are met if magnitude of the update is within a second threshold.

23. The method of claim 5, wherein the actual measurement vector corresponds to pseudo-ranges indicative of distances between the device and the transmitters.

24. The method of claim 5, wherein the transmitters are satellites in a Global Positioning Satellite (GPS) system.

25. The method of claim 5, wherein the transmitters include base stations in a wireless communication system.

26. The method of claim 25, wherein the wireless communication system is a CDMA system.

27. A computer program product for determining the location of a device, comprising:

code for receiving position estimates for a plurality of transmitters and initial measurements for the transmitters;

code for computing an update for a current device position estimate based on the Transmitter Position Estimates, the current device position estimate, and the initial measurements, wherein the current device position estimate is initially set to an initial estimate for the location of the device;

code for detecting non-convergence of the current device position estimate toward a target position estimate;

code for, if non-convergence is detected, adjusting the update to increase likelihood of convergence to the target position estimate;

code for updating the current device position estimate based on the update; and

a data storage medium configured to store the codes.

28. A receiver device comprising:

at least one receiver unit configured to receive and process a plurality of signals from a plurality of transmitters to derive initial measurements for the transmitters; and

a processor coupled to the at least one receiver unit and configured to

receive the initial measurements and position estimates for the transmitters,

compute an update for a current device position estimate based on the transmitters position estimates, the current device position estimate, and the initial measurements, wherein the current device position estimate is initially set to an initial estimate for the location of the device,

detect non-convergence of the current device position estimate toward a target position estimate,

if non-convergence is detected, adjust the update to increase likelihood of convergence to the target position estimate,

update the current device position estimate based on the update, and

repeat the compute, detect, adjust, and update for a plurality of iterations.

29. The receiver device of claim 28, wherein the processor is further configured to

scale the update by a scaling factor to reduce magnitude of the update, wherein the scaling factor is increased based on detected events indicative of non-convergence.