Resolving time ambiguity in GPS using over-determined navigation solution

[0002] This application claims priority under 35 U. S. C. §119(e) of U.S. Provisional Patent Application No. 60/232,738, filed Sep. 15, 2000, entitled “RESOLVING TIME AMBIGUITY IN GPS USING OVER-DETERMINED NAVIGATION SOLUTION,” by Mangesh M. Chansarkar, which application is incorporated by reference herein.

[0003] 1. Field of the Invention

[0004] The present invention relates in general to Global Positioning System (GPS) receivers, and in particular to resolving time ambiguity in GPS using an over-determined navigation solution.

[0005] 2. Description of the Related Art

[0006] In GPS, there are four variables, namely, position determined by x, y, and z coordinates, and time (x, y, z, and t). These variables are determined by using triangulation techniques and accurate system clocks to determine the location of a GPS receiver through range, range-rate, and pseudo-range measurements made by or at the GPS receiver.

[0007] To accurately determine the x, y, z, and t variables, four GPS satellite signals are typically required to provide four simultaneous equations that are solved for the four variables. However, in many environments, such as urban canyons, in buildings, or other weak-signal environments, only three satellites are visible from the GPS receiver. As such, one of the variables must be empirically determined.

[0008] It can be seen, then, that there is a need in the art for a method to empirically determine at least one of the GPS variables. It can also be seen, then that there is a need in the art for an apparatus for empirically determining at least one of the GPS variables.

[0009] To minimize the limitations in the prior art, and to minimize other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses methods and apparatuses for determining time in a GPS system by overdetermining the position of a mobile GPS receiver. By overdetermining the position to very accurate measurements, the time ambiguity can be resolved to lower error limits than possible without the overdetermination algorithm.

[0010] A method for resolving a variable ambiguity in a global positioning system receiver in accordance with the present invention comprises determining a plurality of pseudoranges to a plurality of Global Positioning System satellites, determining a range for each of the pseudoranges, wherein the range gives a maximum and a minimum for each of the pseudoranges, and minimizing a distance from an estimate of user position to the maximum and minimum for the plurality of pseudoranges.

[0011] It is an object of the present invention to provide a method to empirically determine at least one of the GPS variables. It is a further object of the present invention to provide an apparatus for empirically determining at least one of the GPS variables.

[0012] Referring now to the drawings in which like reference numbers represent corresponding parts throughout:

[0013] FIG. 1 illustrates the principles used in the Global Positioning System to determine user location;

[0014] FIG. 2 illustrates the principles used in the Global Positioning System wherein noise and other real-life effects are included in the positioning calculations;

[0015] FIG. 3A shows the trajectory for a given GPS satellite as used in the present invention;

[0016] FIG. 3B illustrates another frame of reference for the Global Positioning System in accordance with the present invention; and

[0017] FIG. 4 illustrates the position area determined by the Global Positioning System in accordance with the present invention.

[0018] In the following description of the preferred embodiment, reference is made to the accompanying drawings which form a part hereof, and in which is shown by way of illustration a specific embodiment in which the invention may be practiced. It is to be understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the present invention.

[0019] In a GPS receiver, initially, none of the four variables has any accuracy associated with the measurement of the variable because nothing is known about the position of the receiver. However, once a satellite or multiple satellites are acquired, and the code tracking of one or more satellites commences, the system time can be accurately resolved within 1 ms (the code repetition rate). When the bit synchronization of the code is complete, system time can be resolved within 20 ms (bit period).

[0020] Once code tracking and bit synchronization have occurred, a consistent measurement set (e.g., a set of x, y, z, and t measurements) can be constructed if the user position is known to within a few tens of Kilometers (km) and time is known to within a few tens of seconds. This approach gives a consistent set of pseudorange measurements, but all these measurements have a unknown clock bias which cannot be resolved in the navigation (NAV) solution directly. The NAV solution will compute the clock bias, but the position solution will be in error due to incorrect satellite location computation.

[0021] For example, if the pseudoranges have an ambiguity of 1 second then the satellite positions have an error of approximately 3 Km (which is equivalent to the orbital speed of the GPS satellites) and this will show up as an error in the position computation. If the solution is exactly determined (4 measurements only) then this cannot be resolved unless external information is used (for example surface of the earth or known altitude of the satellites), but if the solution is over determined then this ambiguity can be resolved autonomously.

[0022] FIG. 1 illustrates the principles used in the Global Positioning System to determine user location.

[0023] To more easily illustrate how GPS works, a two dimensional example is described herein. As additional dimensions, e.g., the z-direction, and time, are added, similar computations and figures will result, but for ease of explanation, two dimensions are presented herein.

[0024] System 100 shows GPS satellite SV1102, and user 104. User 104 receives signals from SV1102, and computes a pseudorange 106 to SV1102. At this point, pseudorange 106 tells user 104 that user 104 is a given distance from SV1102, shown as circle 108.

[0025] Similarly, and at the same time, user 104 receives signals from SV2110, and computes pseudorange 112. Again, pseudorange 112 tells user 104 that user 104 is a given distance away from SV2110, shown as circle 114. Thus, when computations are made with both pseudoranges 106 and 112, two possible solutions are given, namely the user 104 can be at position 116 or position 118.

[0026] For a single location to be determined, signals from satellite SV3120 are received and processed at the same time as the signals from SV1102 and SV2110. Pseudorange 122 is calculated from the signals emanating from SV3120, which generate circle 124. The intersection of circles 108, 114, and 124 only intersect at one point, namely, position 118, which is user 104's position.

[0027] FIG. 2 illustrates the principles used in the Global Positioning System wherein noise and other real-life effects are included in the positioning calculations.

[0028] The calculations and pseudoranges calculated as described in FIG. 1 are for a GPS system without any noise introduced into the system. However, multipath problems, time inaccuracies, and other noise problems will create uncertainties in the pseudorange calculation. As such, each pseudorange calculation will generate a range of pseudorange values. So, for each GPS satellite used in the position calculation, multiple circles will be generated for each received signal. For a given satellite, e.g., SV1102, a range of pseudoranges will be calculated, namely between pseudorange 202 and pseudorange 204, because of noise and other uncertainties in the system. These pseudoranges 202 and 204 then generate two different distance circles, namely circle 206 and circle 208. In a similar fashion, SV2110 will generate a range of pseudoranges, which will generate distance circles 210 and 212, and SV3120 will generate a third range of pseudoranges, which will generate distance circles 214 and 216.

[0029] The intersection of the areas between the distance circles 206 and 208, 210 and 212, and 214 and 216, is area 218. It is in this area, not at this point, that user 104 is located. Current GPS receivers determine the best estimate of where user 104 is, based on area 218 and minimizing the distance from the estimated position of user 104 to the boundaries of area 218, and/or minimizing the distance from the estimated position to the boundaries of all satellites that are used for the position determination.

[0030] FIG. 3A shows the trajectory for a given GPS satellite as used in the present invention.

[0031] System 300 shows trajectory 302, where a given satellite in the constellation travels from point 304 at a first time to point 306 at a second time. At each point along the trajectory, each satellite will generate different distance circles for a given user location, and the noise associated with the distance circles generated can change from time to time, because at position 304, the satellite may be in clear view, whereas at position 306, the satellite can be blocked or in a multipath condition for the user. As such, each position along the trajectory 302 will have different distance circles and different noise values, as shown by distance circles 308 and 310 associated with position 304, and distance circles 312 and 314 associated with position 306.

[0032] FIG. 3B illustrates another frame of reference for the Global Positioning System in accordance with the present invention.

[0033] System 300, as a GPS system, determines the location of a user 104 by determining distances from the user 104 to satellites in the GPS constellation. As shown in FIG. 3A, those distances are not exactly determinable because of noise and other factors, and are represented as concentric distance circles from each satellite, which results in uncertainties for the user position. From the user perspective, shown in FIG. 3B, the user determines distances to each satellite, which have.some uncertainties, and, thus, the user cannot determine exactly where user 104 is.

[0034] For example, user 104 determines first pseudoranges 314, 316, and 318 at a first time, for three satellites on estimated trajectories 320, 322, and 324, respectively. However, because of noise, clock bias, and other uncertainties in the GPS system, user 104 is unsure of each measurement by some factor, which means that first pseudorange 314 may have to add in factor 326, which, in effect, means that that given GPS satellite may be on trajectory 328. Similarly, noise and other effects may add factor 330 to the second pseudorange 316, placing the GPS satellite on trajectory 332, and may add factor 334 to pseudorange 318 placing third GPS satellite on trajectory 336. This means that there is uncertainty in the user 104 position in every direction because of the factors 326, 330, and 334, which creates area 338 as to where the user 104 is likely located.

[0035] At a second time, the user 104 determines pseudoranges 340, 342, and 344. Again, because of noise, clock bias, or other uncertainties in the system, each pseudorange 340, 342, and 344 has uncertainties associated with it, and therefore each pseudorange 340, 342, and 344 must have factors 346, 348, and 350, respectively, potentially added to the pseudoranges 340-344, to properly determine the user 104 location. These uncertainties translate into an area 352, which may or may not be the same area as area 338, where user 104 is most likely located.

[0036] The present invention is used to determine where, in areas 338 and/or 352, user 104 is most likely located.

[0037] FIG. 4 illustrates the position area determined by the Global Positioning System in accordance with the present invention.

[0038] Graph 400 illustrates area 402, which is bounded by lines 404-414. Lines 404 and 406 are determined by the pseudorange measurement to SV1102, and the distance between lines 404 and 406 is determined by the uncertainty in the pseudorange measurement to SV1102. Similarly, lines 408 and 410 are determined by the pseudorange measurement to SV2110, and the distance between lines 408 and 410 is determined by the uncertainty in the pseudorange measurement to SV2110. Lines 412 and 414 are determined by the pseudorange measurement to SV3120, and the distance between lines 412 and 414 is determined by the uncertainty in the pseudorange measurement to SV2120. Other satellites can also be used in the positioning determination, which can generate lines 416 and 418, which may or may not intersect any of lines 404-414.

[0039] Once all of the lines that bound area 402 are determined, and any additional lines such as lines 416 and 418 are determined, the present invention uses a minimization routine to minimize the distance from the best estimate of user position to each of the lines 404-418 that was determined by the user. This will minimize the effects of errors in each of the pseudorange measurements.

[0040] The following procedure can be used to resolve the clock ambiguity and compute the correct clock bias and user position.

[0041] Let Pxi, Pyi and Pzi denote the satellite locations for the i^thGPS satellite computed for use in the NAV solution. These are computed at a wrong time due to the clock ambiguity. Let Vxi, Vyi and Vzi be the GPS satellite velocities computed for use in the NAV solution. Let Pri be the pseudorange for the i^thsatellite. Let X, Y, Z, and B be the computed user position and clock bias, respectively.

[0042] The residual Zi for the i^thsatellite is computed as follows:

[0043] Zi=Pri−[(Pxi+ΔT Vxi−X)²+(Pyi+ΔT Vyi−Y)²+(Pzi+ΔT Vzi−Z)²]−B

[0044] where ΔT is the time ambiguity to be resolved. If there are more than 4 measurements available then this can be resolved by minimizing the quantity ΣZi². The summation is carried over the number of measurements. This is a multivariable minimization problem where ΣZi²must be minimized with respect to ΔT, X, Y, Z, B. For analytical simplicity this can be broken down in two separate minimizations where the quantity ΣZi²is minimized with respect to ΔT and then the user Position and clock bias is computed thus minimizing the cost function (ΣZi²) with respect to X, Y, Z, B.

[0045] The minimization with respect to ΔT can be accomplished by setting the derivative with respect to ΔT equal to 0 as follows.

[0046] δΣZi²/ΔT=0

[0047] A simple reorganization of terms leads to a liner equation in ΔT which can be solved easily.

[0048] ΔT=−Σ(Ri*LOSVi)/Σ(SVVi²)

[0049] where

[0050] Ri=Geometric Range to i^thsatellite from the estimated user location.

[0051] SVVi=Speed of i^thGPS satellite.

[0052] LOSVi=Line of sight speed of i^thGPS satellite based on estimated user location.

[0053] If there are only 4 measurements and the user location and clock bias are computed using the least squares criterion then the ΔT in the above expression goes to 0 as each of the residuals computed will be identically equal to 0 for ΔT=0.

[0054] This value of ΔT minimizes the sum squares of residuals from the estimated user location (which may be in error). Hence this procedure must be recursively performed to refine the time and position estimate till consecutive solutions are within acceptable errors with respect to one another.

[0055] This technique can be used to determine other variables other than time, e.g., if there is an external, highly-accurate clock available, the clock bias is reduced to zero without using the iterative process, but other variables, e.g., the z variable, may not be resolvable using the pseudorange measurements. Therefore, overdetermination of the x, y, and t variables will assist in the determination of the z variable, however, different mathematical techniques may have to be used.

[0056] The present invention is embodied in hardware and/or software that is used to perform the computations described above. Different embodiments of the invention may be used to perform different types of calculations, e.g., a single integrated circuit or piece of software can be used to perform the time ambiguity calculation, a second integrated circuit or piece of software can be used to perform the z-direction ambiguity calculation, or a single integrated circuit or piece of software can be used to perform all calculations described by the present invention. The apparatus is not limiting to the applications of the present invention.

[0057] The foregoing description of the preferred embodiment of the invention has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Many modifications and variations are possible in light of the above teaching. It is intended that the scope of the invention not be limited by this detailed description.