Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2001-08-03
2003-01-07
Cuchlinski, Jr., William A. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C342S357490
Reexamination Certificate
active
06505122
ABSTRACT:
BACKGROUND
1. Field
The present invention relates generally to position determination, and more specifically to a method and apparatus for improving estimating the location of a device under unfavorable dilution of precision (DOP) conditions.
2. Background
A common means by which to locate a device is to determine the amount of time required for signals transmitted from multiple sources at known locations to reach the device. One system that provides signals from a plurality of transmitters of known locations is the well-known Global Positioning Satellite (GPS) system. Satellites in the GPS system are placed in precise orbits according to a GPS master plan. The position of the GPS satellites can be identified by different sets of information transmitted by the satellites themselves. Another system that provides signals from transmitters (i.e., base stations) of known earth-bound locations is a wireless (cellular) communication system.
Signals from satellites and/or base stations may be used to determine the location of a device. By receiving and processing the signals transmitted from these transmitters, the amount of time required for the signals to travel from the transmitters to the device may be measured and used to compute the distances (or ranges) between the transmitters and the device. The signals themselves may further include information indicative of the locations of the transmitters. By accurately measuring the distances from three or more transmitters at known locations, the device can “trilaterate” its position. For example, when range measurements are available, a measurement surface may be determined for each transmitter, with the surface originating at the transmitter's location and having a curvature determined by the range from the transmitter to the device. The intersection of three or more such measurement surfaces would then be the estimated position of the device.
The ranges to the transmitters and their locations are conventionally provided to an algorithm that operates on the data to provide a position estimate for the device. This algorithm is typically a least mean square (LMS) algorithm that performs a number of iterations to arrive at a final solution for the device's position estimate. If provided with “good” range and transmitter location data, the LMS solution asymptotically converges toward a target “optimal” solution with each iteration, and the LMS algorithm may be terminated when the LMS solution is within a particular tolerance of the target solution.
In certain circumstances, the LMS algorithm does not converge toward the target solution. These circumstances typically arise due to a large “dilution of precision” (DOP) around the device location, which may result from having inaccurate range data and/or poor geometry for the transmitter and device locations. As an example, if the transmitters are located in close proximity relative to the distance to the device, then the measurement surfaces for these transmitters may intersect at a small angle (i.e., the surfaces are close to parallel as oppose to being more slanted toward perpendicular). In this case, a small error in the range measurements would result in a large error in the point of intersection, and thus a corresponding large error in the estimated location of the device. In one especially case of very large DOP, the measurement surfaces do not intersect, which then results in bad geometry and large errors at the optimal position estimate for the device.
The likelihood of obtaining bad geometry increases when earth-bound measurements are used (exclusively or in conjunction with satellite measurements) to estimate the position of the device. Earth-bound measurements may be made from signals transmitted from base stations of a wireless communication system and received at the device or signals received at the base stations from the device. The distances from the device to the base stations are shorter than those to the satellites, and the curvature of the earth-bound measurement surfaces is larger, which then increases the likelihood that the measurement surfaces do not intersect.
Conventionally, solutions obtained in cases of bad geometry are discarded. This may be due to a combination of non-convergence by the LMS algorithm and/or reduced likelihood of obtaining the desired accuracy in the LMS solutions. However, in many instances, such as 911 emergency services, these solutions are beneficial and should be reported if they can be obtained.
There is therefore a need in the art for techniques to provide position estimate with improved likelihood of having the desired accuracy in cases of large DOP.
SUMMARY
Aspects of the invention provide techniques to derive an improved position estimate for a receiver device (i.e., a “Device Position Estimate”) in cases of large “dilution of precision” (DOP). The Device Position Estimate, “Actual Measurement Vectors” and “Transmitter Position Estimates” are provided to an iterative algorithm (e.g., an LMS algorithm) that is initially operated in a normal manner. In cases of large DOP, the solutions from the algorithm may not converge toward a target solution, but may instead oscillate (i.e., overshoot) around the target solution. A method and apparatus is disclosed herein to determine when convergence is unlikely and to adjust the algorithm to increase the likelihood of convergence. Accordingly, the disclosed method and apparatus frequently increases the accuracy of the final solutions calculated in cases of large DOP.
A determination that the LMS algorithm is unlikely to converge may be made based on: (1) the number of iterations performed without determining that the algorithm has converged to a final solution (hereafter referred to as the “target solution”), (2) phase reversal in an “Update Vector” used to update the Device Position Estimate, or (3) a combination of these parameters.
One embodiment of the disclosed method determines the Transmitter Position Estimates for a number of transmitters (e.g., GPS satellites and/or base stations) determines an “Actual Measurement Vector” by making measurements, and calculates a “Calculated Measurement Vector” related to the distance between a current device and each transmitter (e.g., the pseudo-ranges to the transmitters that would result from the transmission of signals between the current device and each transmitter). In addition, a “Residual Measurement Error Vector” is calculated. The Residual Measurement Error Vector represents the difference between the Actual Measurement Vector and the Calculated Measurement Vector. An Update Vector for a current Device Position Estimate is then computed based on the Residual Measurement Error Vector, the Transmitter Position Estimates, and a previous Device Position Estimate. A determination is made as to whether convergence of the Device Position Estimate toward a target solution is likely. If convergence is not likely, then the Update Vector is adjusted to increase the likelihood of convergence toward the target solution.
The target solution is defined as that solution that results in the minimum value for a metric calculated as a function of the errors that are included in the Residual Measurement Error Vector.
The criteria are normally dependent on the particular algorithm being used to determine the Device Position Estimate. The current Device Position Estimate is updated based on the Update Vector. It should be noted that in one embodiment of the disclosed method and apparatus, the Update Vector is adjusted prior to being used to update the Device Position Estimate.
The Update Vector may be adjusted by: (1) reducing the magnitude of the Update Vector based on a scaling factor, and/or (2) 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. The scaling factor may be increased (e.g., doubled) with each detected event indicative of non-convergence (possibly except for the first event).
REFERENCES:
patent: 5615116 (1997-
Brown Charles D.
Cheatham Kevin
Cuchlinski Jr. William A.
Hernandez Olga
Qualcomm Incorporated
LandOfFree
Method and apparatus for providing accurate position... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for providing accurate position..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for providing accurate position... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3053415