Rapid determination of an unknown position

A system for rapid determination of an unknown position includes an interface and a processor. The interface is configured to receive carrier phase information and code information from a global navigation satellite system signal. The processor is configured to receive double-difference phase information generated using carrier phase information and code information; and calculate an accurate position based at least in part on a most likely integer solution for the carrier phase ambiguity based at least in part on the double-difference phase information.

BACKGROUND OF THE INVENTION

Global navigation satellite systems (GNSS) use both code phase and carrier phase measurements for accurate positioning. Because carrier phase measurements are made at a much higher frequency than code phase measurements, they provide a much more accurate reference for localization. However, because the carrier phase is highly regular, using carrier phase measurements to calculate position suffers from ambiguities in the choice of phase alignment. As a result, one of the central design goals of a reliable GNSS is to effectively and efficiently estimate the unknown cycle ambiguities of double-difference carrier phase data and turn the carrier phase measurements into accurate pseudo-range measurements. Resolving the carrier phase ambiguity makes it possible to achieve centimeter-level positioning. Although centimeter-level relative positioning with carrier phase is now routine in fields such as surveying, geophysics, and geodesy, the challenge of estimating the integer phase ambiguity quickly and correctly for precise positioning in real time is an unsolved problem. Given the increasing demand for precise navigation in applications such as fast-moving vehicles or unmanned aerial vehicles, estimating the integer phase ambiguity quickly and correctly is critical because a real-time position estimate often needs to be made using only a single epoch of data from the global navigation satellite system.

DETAILED DESCRIPTION

A system for rapid determination of an unknown position using Global Navigation Satellite System (GNSS) code phase and carrier phase measurements is disclosed. The system includes a receiving system for GNSS carrier phase information and code information. The receiving system includes an interface and a position processor. The interface is configured to receive the carrier phase information and the code information receiver. The interface is configured to receive information from a GNSS memory. Double-difference phase measurement information is determined from the carrier phase information and/or the code information. The input interface is configured to receive GNSS data including the satellite position matrix from the GNSS memory. The position processor is configured to calculate the accurate position based at least in part on the most likely integer solution for the carrier phase ambiguity based at least in part on the double difference phase information and the GNSS data.

A system for rapid determination of an unknown position using Global Navigation Satellite System (GNSS) comprises a number of satellites or other sources that transmit data about the state of the GNSS system via a carrier signal and a receiver system that receives carrier phase information and GNSS code information and sends this information to a position processor which outputs a highly accurate position estimate. The position processor comprises an unconstrained localization calculator, an integer-constrained phase calculator, and a baseline coordinate re-estimator. Within the unconstrained localization calculator, all the unknown parameters for determining the unknown position are estimated without consideration of the special integer phase ambiguity constraints using least squares estimation. The result is passed onto the integer-constrained phase calculator and the baseline coordinate re-estimator. Within the integer-constrained phase calculator, the solution from the unconstrained localization calculator is used to search for the most likely integer solution. The baseline coordinate re-estimator then uses the integer solution determined by the integer-constrained phase calculator to re-estimate the position. An output interface receives baseline coordinate information from the baseline coordinate re-estimator and outputs an accurate position.

In contrast to traditional GNSS systems that use carrier phase to perform centimeter-level relative positioning, the disclosed system for rapid determination of an unknown position improves on the typical GNSS and is able to quickly and correctly calculate precise positioning in real time. For real-time applications, estimating the integer phase ambiguity quickly and correctly is critical because a position estimate often needs to be made using only a single epoch of data from a global navigation satellite system. The disclosed method is also applicable to other systems that require resolving phase difference ambiguities such as the next-generation triple-frequency systems (e.g. European Galileo) as well as solving phase-unwrapping problems encountered in Interferometric Synthetic Aperture Radar.

FIG. 1is a block diagram illustrating an embodiment of a system for rapid determination of an unknown position using Global Navigation Satellite System (GNSS) code phase and carrier phase measurements. In the example shown, a system for rapid determination of an unknown position100receives GNSS code phase and carrier phase measurements from a number of satellites (e.g., satellite102, satellite104, or satellite106) via antenna108and processes the measurements to output an accurate position. Carrier phase information receiver110receives information about the phase of the GNSS carrier from antenna108and sends carrier phase information to receiver input interface114. Code information receiver112receives GNSS code information via antenna108and sends GNSS code information to receiver input interface114. Receiver interface114stores GNSS code information including a satellite position matrix G, ionospheric and tropospheric parameter matrix A, and measurement noise covariance Vein GNSS data storage116. In some embodiments, random samples xnare stored in a separate random access memory that is only accessible by position processor118. Receiver interface114processes GNSS code phase and carrier phase measurements and sends double-difference phase measurements to position processor118. Position processor118receives double-difference phase measurements y from receiver interface114and GNSS data from GNSS data storage116and outputs accurate baseline coordinates to output interface128. Output interface128receives baseline coordinates from position processor118and outputs accurate position from system for rapid determination of an unknown position100.

Unconstrained localization calculator120is configured to receive double-difference phase measurements y, satellite position matrix G, ionospheric and tropospheric parameter matrix A, and measurement noise covariance Vefrom receiver input interface114and GNSS data storage116. Unconstrained localization calculator120is further configured to solve the linear localization equation: y=Φz+e, where Φ=[G|A] (concatenation of G and A matrices), z=[lT|xT] (concatenation of l and x vectors), and e is Gaussian noise with known covariance matrix Ve. Unconstrained localization calculator120calculates the maximum likelihood estimate of z that contains the jointly unknown parameters l and x (baseline coordinates and continuous phase ambiguities, respectively) for the localization equation. The maximum likelihood estimator of z is calculated from:
{circumflex over (z)}=(ΦTVe−1Φ)−1ΦTVe−1y
where the covariance of z is calculated from:
Vz=(ΦTVe−1Φ)−1,
which can also be written in the form:

Unconstrained localization calculator120sends the resulting vector z and the covariance matrix Vzto the solution splitter122.

Solution splitter122separates the solution z into its components l and x as well as the covariance matrix Vzinto its components Vxxand Vxl. Solution splitter122sends the components (x, Vxx) to integer-constrained phase calculator124and baseline coordinate re-estimator126. Solution splitter122sends the components (l, Vlx) to baseline coordinate re-estimator126.

Integer-constrained phase calculator124receives the unconstrained solution components (x, Vxx) and calculates an integer-constrained solution for x. Integer-constrained phase calculator124sends the integer solution to baseline coordinate re-estimator126.

Baseline coordinate re-estimator126receives unconstrained solution components (x, Vxx) from solution splitter122, integer {circumflex over (x)} solution from integer-constrained phase calculator124, and unconstrained solution components (l, Vlx) from solution splitter122and re-estimates the baseline coordinates to produce an accurate position output. The baseline coordinate re-estimator sends {circumflex over (l)} to output interface128where it outputs an accurate position output from the system for rapid determination of an unknown position100.

FIG. 2is a block diagram illustrating an embodiment of an integer-constrained phase calculator for calculating an integer-constrained solution for the ambiguity vector x. In some embodiments, integer-constrained phase calculator200is used to implement integer-constrained phase calculator124ofFIG. 1. In the example shown, integer-constrained phase calculator200receives unconstrained ambiguity vector and covariance matrix and calculates an integer-constrained solution of x. For example, integer-constrained phase calculator200receives continuous ambiguity vector and covariance (x, Vxx) from an unconstrained localization calculator. Phase distribution sample generator202receives ambiguity vector and covariance (x, Vxx) and generates random samples with a Gaussian distribution. For example, phase distribution sample generator202generates independent and identically distributed random samples drawn from a Gaussian probability distribution with mean x and covariance Vxx. Gaussian random samples are received by sample discretizer204, which rounds the samples to the closest integer value. For example, sample discretizer204computes round(xi) for all Gaussian samples xiand computes the set of all unique integer values. For each unique value, sample discretizer204records all samples that are discretized to the same integer value. Proximity set counter206receives rounded set from sample discretizer204and counts the number of set samples that fall within a radius r of each unique integer member of the set. Qualified sets are recorded for sets with a sufficient number of neighboring samples. Set distance calculator208receives qualified sets from proximity set counter206and scores each member of the set using the Euclidian distance between the set member and its k'th nearest neighbors. Solution chooser210receives the scored sets from set distance calculator208and chooses the best integer solution. For example, solution chooser210chooses the solution with the minimum Euclidian distance of its k'th nearest neighbor. Integer-constrained phase calculator200outputs optimal integer solution. For example, integer-constrained phase calculator200outputs integer solution to baseline coordinate re-estimator126ofFIG. 1.

FIG. 3is a pseudo code illustrating an embodiment of an algorithm for performing integer quadratic minimization with bootstrapping to determine the integer-constrained ambiguity vector {circumflex over (x)}. In some embodiments, Algorithm1ofFIG. 3is used to implement integer-constrained phase calculator124ofFIG. 1. In the example shown, the input to Algorithm1comprises an unconstrained ambiguity vector x, covariance matrix Vxx, boost size n, neighbor radius r, and number of nearest neighbors k. The output of Algorithm1is the most likely integer solution. For example, integer-constrained phase calculator124ofFIG. 1receives ambiguity vector and covariance (x, Vxx) from an unconstrained localization calculator and uses Algorithm1to determine the most likely integer solution. Steps1-2of Algorithm1generate independent and identically distributed random samples drawn from a Gaussian probability distribution with mean x and covariance Vxx. The random samples xi, . . . , xnare generated using phase distribution sample generator202ofFIG. 2. Random samples xnare stored in a random access memory116ofFIG. 1accessible by position processor118. In some embodiments, random samples xnare stored in a separate random access memory that is only accessible by position processor118. Steps3-7of Algorithm1create rounded sets by rounding the samples generated in steps1-2of Algorithm1to the nearest integer value. In some embodiments, sample discretizer204ofFIG. 2rounds samples. Steps8-9of Algorithm1determine which of the unique integer points qualify as a possible solution by counting the number of samples that fall within a radius r of a unique integer point. In some embodiments, proximity set counter206ofFIG. 2counts samples within a radius r of unique integer points. Steps10-11of Algorithm1test if an integer solution can be determined by the number of samples within a given radius r without further analysis. Steps12-14of Algorithm1score the qualified sets from steps8-9to determine the best integer solution. In some embodiments, set distance calculator208ofFIG. 2scores qualified sets. Steps15-16of Algorithm1choose the best integer solution. In some embodiments, solution chooser210ofFIG. 2chooses best integer solution.

FIG. 4is a pseudocode illustrating an embodiment of an algorithm for performing integer quadratic minimization with bootstrapping to determine the integer-constrained ambiguity vector {circumflex over (x)}. In some embodiments, Algorithm2ofFIG. 4is used to implement integer-constrained phase calculator124ofFIG. 1. Algorithm2differs from Algorithm1in that a set of pre-screened candidate integers is identified instead of only one value. In addition, instead of using the k-nearest neighbor strategy of Algorithm1, the weighted mean-squared error is computed for each candidate ambiguity vector x and the one with the lowest error is chosen. Algorithm2serves to enhance the performance for high dimensional ambiguity vector x and covariance Vxxat the cost of more computation. In the example shown, the input to Algorithm2comprises an unconstrained ambiguity vector x, covariance matrix Vxx, boost size n, neighbor radius r, and threshold of votes L. The output of Algorithm2is the most likely integer solution. For example, integer-constrained phase calculator receives ambiguity vector and covariance (x, Vxx) from an unconstrained localization calculator and uses Algorithm2to determine the most likely integer solution. Steps1-2of Algorithm2generate independent and identically distributed random samples drawn from a Gaussian probability distribution with mean x and covariance Vxx. The random samples xi, . . . , xnare generated using a phase distribution sample generator of an integer-constrained phase calculator. Random samples x1, . . . , xnare stored in a random access memory accessible by a position processor. In some embodiments, random samples xi, . . . , xnare stored in a separate random access memory that is only accessible by the position processor. Steps3-7of Algorithm2create rounded sets (R(x)) in the random access memory by rounding the samples generated in steps1-2of Algorithm2to the nearest integer value. The sample discretizer rounds samples. Steps8-9of Algorithm2determine which of the unique integer points qualify as a possible solution by counting the number of samples that fall within a radius r of a unique integer point. A proximity set counter counts samples within a radius r of unique integer points and stores the count in the random access memory. Steps10-14of Algorithm2create a set of integer points with sufficient neighboring samples by tabulating the number of votes for the solution passing a threshold. This set is then used to score the qualified sets from steps8-9to determine the best integer solution using the mean-squared error ex in step13. Set distance calculator scores qualified sets. Steps15-16of Algorithm2choose the best integer solution and output the integer-constrained ambiguity vector x along with its mean-squared error ex. Solution chooser chooses best integer solution.

FIG. 5is a pseudocode illustrating an embodiment of an algorithm for performing integer quadratic minimization with bootstrapping to determine the integer-constrained ambiguity vector {circumflex over (x)}. In some embodiments, Algorithm3ofFIG. 5is used to implement integer-constrained phase calculator124ofFIG. 1. In the example shown, input to Algorithm3comprises an unconstrained ambiguity vector x, covariance matrix Vxx, boost size n, neighbor radius r, and number of layers L. The output of Algorithm3is the most likely integer solution. For example, integer-constrained phase calculator receives ambiguity vector and covariance (x, Vxx) from an unconstrained localization calculator and uses Algorithm3to determine the most likely integer solution. Algorithm3is used to enhance the performance for high dimension and ill-conditioned covariance matrix Vxx. It is an extension of Algorithm2and is especially suitable for situations where generating random numbers is costly and where fast computation is the main concern. Algorithm3replaces the scheme of generating Gaussian random variables with a more complex multi-layer scheme, which successively generates truncated Gaussian random variables for each layer using Algorithm4ofFIG. 6. By performing the solution search for each layer, Algorithm3more efficiently explores the space of potential solutions in order to quickly find the global optimum. Steps1-3of Algorithm3define partitions P1for each sampling layer and initialize the local variable v0for tracking the current mean-squared error ex of the solution x. Partitions Piare truncated Gaussian probability functions parameterized by truncation thresholds Ti where 0<=τ1<=τ2< . . . . Steps4-6of Algorithm3apply Algorithm2to each layer Pi. Truncated Gaussian distributions are generated by Algorithm4and used as input to Algorithm2. Algorithm2calculates the optimal integer solution and returns the optimal integer solution together with its associated mean-squared error. The mean squared error is stored in the variable vi. Steps7-9choose the integer solution. If the current mean-squared error vifor layer i is less than prior solutions v0, then the current integer solution is chosen as the best solution.

FIG. 6is a pseudocode illustrating an embodiment of an algorithm for performing truncated Gaussian sampling. In some embodiments, Algorithm4ofFIG. 6is used to implement phase distribution sample generator ofFIG. 2. In the example shown, input to Algorithm4comprises a mean vector y, covariance matrix Vxx, sample size n, layer level T, and number of layers L. The output of Algorithm4is a set S containing n samples xi, . . . , xndistributed according to a truncated Gaussian distribution with threshold T. Step1of Algorithm4initializes the sample set S. Steps2-5generate samples from a truncated Gaussian by transforming a uniform distribution into a truncated Gaussian distribution and adding them to set S.