On lattice reduction algorithms for solving weighted integer least squares problems: comparative study

Decorrelation or reduction theory deals with identifying appropriate lattice bases that aid in accelerating integer search to find the optimal integer solution of the weighted integer least squares problem. Orthogonality defect has been widely used to measure the degree of orthogonality of the reduced lattice bases for many years. This contribution presents an upper bound for the number of integer candidates in the integer search process. This upper bound is shown to be a product of three factors: (1) the orthogonality defect, (2) the absolute value of the determinant of the inverse of the generator matrix of the lattice, and (3) the radius of the search space raised to the power of the dimension of the integer ambiguity vector. Four well-known decorrelation algorithms, namely LLL, LAMBDA, MLAMBDA, and Seysen, are compared. Many simulated data with varying condition numbers and dimensions as well as real GPS data show that the Seysen reduction algorithm reduces the condition number much better than the other algorithms. Also, the number of integer candidates, before and after the reduction process, is counted for all algorithms. Comparing the number of integer candidates, condition numbers, and orthogonality defect reveals that reducing the condition number and the orthogonality defect may not necessarily result in decreasing the number of integer candidates in the search process. Therefore, contrary to the common belief, reducing the orthogonality defect and condition number do not always result in faster integer least squares estimation. The results indicate that LAMBDA and MLAMBDA perform much better in reducing the number of integer candidates than the other two algorithms, despite having a larger orthogonality defect and condition number in some cases. Therefore, these two algorithms can speed up the integer least squares estimation problem in general and the integer ambiguity resolution problem in particular.     

Integer least-squares theory for the GNSS compass

Global navigation satellite system (GNSS) carrier phase integer ambiguity resolution is the key to high-precision positioning and attitude determination. In this contribution, we develop new integer least-squares (ILS) theory for the GNSS compass model, together with efficient integer search strategies. It extends current unconstrained ILS theory to the nonlinearly constrained case, an extension that is particularly suited for precise attitude determination. As opposed to current practice, our method does proper justice to the a priori given information. The nonlinear baseline constraint is fully integrated into the ambiguity objective function, thereby receiving a proper weighting in its minimization and providing guidance for the integer search. Different search strategies are developed to compute exact and approximate solutions of the nonlinear constrained ILS problem. Their applicability depends on the strength of the GNSS model and on the length of the baseline. Two of the presented search strategies, a global and a local one, are based on the use of an ellipsoidal search space. This has the advantage that standard methods can be applied. The global ellipsoidal search strategy is applicable to GNSS models of sufficient strength, while the local ellipsoidal search strategy is applicable to models for which the baseline lengths are not too small. We also develop search strategies for the most challenging case, namely when the curvature of the non-ellipsoidal ambiguity search space needs to be taken into account. Two such strategies are presented, an approximate one and a rigorous, somewhat more complex, one. The approximate one is applicable when the fixed baseline variance matrix is close to diagonal. Both methods make use of a search and shrink strategy. The rigorous solution is efficiently obtained by means of a search and shrink strategy that uses non-quadratic, but easy-to-evaluate, bounding functions of the ambiguity objective function. The theory presented is generally valid and it is not restricted to any particular GNSS or combination of GNSSs. Its general applicability also applies to the measurement scenarios (e.g. single-epoch vs. multi-epoch, or single-frequency vs. multi-frequency). In particular it is applicable to the most challenging case of unaided, single frequency, single epoch GNSS attitude determination. The success rate performance of the different methods is also illustrated.     

下三角Cholesky分解的整数高斯变换算法

针对全球导航卫星系统(GNSS)载波相位测量中,基于整数最小二乘估计准则解算整周模糊度问题。目前以LAMBDA降相关算法和Lenstra-Lenstra-Lovász(LLL)为代表的规约算法应用最为广泛。由于不同算法采用的模糊度方差-协方差阵的分解方式不同,导致难以合理地进行不同算法性能的比较。该文通过分析LAMBDA算法的降相关特点,从理论上推出基于下三角Cholesky分解多维情形下的整数高斯变换的降相关条件及相应公式,并与分解方式不同的LAMBDA和LLL算法作了对比。实验结果表明,降相关采用的分解方式将会直接影响计算复杂度和解算性能,因此该文推导的整数高斯变换算法便于今后基于下三角Cholesky分解的降相关算法间的合理比较。     

MLAMBDA: a modified LAMBDA method for integer least-squares estimation

The least-squares ambiguity Decorrelation (LAMBDA) method has been widely used in GNSS for fixing integer ambiguities. It can also solve any integer least squares (ILS) problem arising from other applications. For real time applications with high dimensions, the computational speed is crucial. A modified LAMBDA (MLAMBDA) method is presented. Several strategies are proposed to reduce the computational complexity of the LAMBDA method. Numerical simulations show that MLAMBDA is (much) faster than LAMBDA. The relations between the LAMBDA method and some relevant methods in the information theory literature are pointed out when we introduce its main procedures.     

Testing of a new single-frequency GNSS carrier phase attitude determination method: land,ship and aircraft experiments

Global navigation satellite system (GNSS) ambiguity resolution is the process of resolving the unknown cycle ambiguities of the carrier phase data as integers. The sole purpose of ambiguity resolution is to use the integer ambiguity constraints as a means of improving significantly on the precision of the remaining GNSS model parameters. In this contribution, we consider the problem of ambiguity resolution for GNSS attitude determination. We analyse the performance of a new ambiguity resolution method for GNSS attitude determination. As it will be shown, this method provides a numerically efficient, highly reliable and robust solution of the nonlinearly constrained integer least-squares GNSS compass estimators. The analyses have been done by means of a unique set of extensive experimental tests, using simulated as well as actual GNSS data and using receivers of different manufacturers and type as well as different platforms. The executed field tests cover two static land experiments, one in the Netherlands and one in Australia, and two dynamic experiments, a low-dynamics vessel experiment and high-dynamics aircraft experiment. In our analyses, we focus on stand-alone, unaided, single-frequency, single-epoch attitude determination, as this is the most challenging case of GNSS compass processing.     

On the probability density function of the GNSS ambiguity residuals

Integer GNSS ambiguity resolution involves estimation and validation of the unknown integer carrier phase ambiguities. A problem then is that the classical theory of linear estimation does not apply to the integer GPS model, and hence rigorous validation is not possible when use is made of the classical results. As with the classical theory, a first step for being able to validate the integer GPS model is to make use of the residuals and their probabilistic properties. The residuals quantify the inconsistency between data and model, while their probabilistic properties can be used to measure the significance of the inconsistency. Existing validation methods are often based on incorrect assumptions with respect to the probabilistic properties of the parameters involved. In this contribution we will present and evaluate the joint probability density function (PDF) of the multivariate integer GPS carrier phase ambiguity residuals. The residuals and their properties depend on the integer estimation principle used. Since it is known that the integer least-squares estimator is the optimal choice from the class of admissible integer estimators, we will only focus on the PDF of the ambiguity residuals for this estimator. Unfortunately the PDF cannot be evaluated exactly. It will therefore be shown how to obtain a good approximation. The evaluation will be completed by some examples.     

北斗信号体制下三频CIR法模糊度解算方法研究

未来的GNSS系统将广泛使用三个频点的载波信号,极大地推动了利用载波对用户位置和速度等信息进行高精度解算方法的研究。利用载波进行高精度解算的关键是高成功率的确定载波相位整周模糊度。CIR算法基于整数引导估计准则确定载波相位模糊度整数解,算法实现简单,模糊度解算成功率较高,具有很大的实际应用价值。然而目前CIR法在实际应用中主要针对GPS信号体制,在北斗信号体制下是否具有良好的性能还有待验证。本文将CIR法应用于北斗信号体制下三频载波整周模糊度的解算,利用仿真数据对算法进行验证,并将解算结果与GPS信号体制下解算结果进行对比,验证CIR法在北斗信号体制下的可行性,分析不同信号体制下CIR法的解算性能和适用范围。     

基于格论的GNSS模糊度解算

快速、准确地解算整周模糊度是实现GNSS载波相位实时高精度定位的关键,由于模糊度之间的强相关,基于整数最小二乘估计准则时,需要较长的时间才能搜索出最优的整周模糊度向量。为了提高模糊度的搜索效率,本文在扼要介绍格论的理论框架基础上,引入基于格论的模糊度解算方法,通过格基规约来降低模糊度之间的相关性,从而快速搜索出最优的整数模糊度向量。与此同时,将GNSS领域的主要降相关方法统一到格论框架下,探讨了并建议采用Bootstrapping成功率作为格基规约的性能指标之一。最后实验分析了三频多系统长基线相对定位情况下,不同格基规约可获得的性能。     

FirCAR算法的OTF快速定位方法

根据GNSS不同频率间整周模糊度的约束关系,提出一种基于多频整周模糊度间关系约束的模糊度新算法(dual-frequency integer relationship constrained ambiguity resolution,FirCAR)。FirCAR可快速动态解算出高高度角卫星的整周模糊度,将已经固定的整周模糊度视为高精度的伪距观测值应用到下一步的浮点解重算中。结合模糊度搜索算法,如LAMBDA,在模糊度搜索方面的高效性,根据重算后的浮点解进一步解算其他未固定的模糊度解。模糊度固定成功后,即可实现OTF(on the fly)快速定位。实测数据表明,FirCAR算法在静态和动态观测条件下,模糊度初始化所用的平均观测历元数分别为1.04和1.10。与常规的模糊度搜索算法的对比试验表明,结合FirCAR算法模糊度固定所用的观测历元数分别减少了39%和18%。     

Orthogonality defect and reduced search-space size for solving integer least-squares problems

In the context of ambiguity resolution (AR) of global navigation satellite systems (GNSS), decorrelation among entries of an ambiguity vector, integer ambiguity search, and ambiguity validations are three standard procedures for solving integer least-squares problems. This paper contributes to AR issues from three aspects. Firstly, the orthogonality defect is introduced as a new measure of the performance of ambiguity decorrelation methods and compared with the decorrelation number and with the condition number, which are currently used as the judging criterion to measure the correlation of ambiguity variance–covariance matrix. Numerically, the orthogonality defect demonstrates slightly better performance as a measure of the correlation between decorrelation impact and computational efficiency than the condition number measure. Secondly, the paper examines the relationship of the decorrelation number, the condition number, the orthogonality defect, and the size of the ambiguity search space with the ambiguity search candidates and search nodes. The size of the ambiguity search space can be properly estimated if the ambiguity matrix is decorrelated well, which is shown to be a significant parameter in the ambiguity search progress. Thirdly, a new ambiguity resolution scheme is proposed to improve ambiguity search efficiency through the control of the size of the ambiguity search space. The new AR scheme combines the LAMBDA search and validation procedures together, which results in a much smaller size of the search space and higher computational efficiency while retaining the same AR validation outcomes. In fact, the new scheme can deal with the case there are only one candidate, while the existing search methods require at least two candidates. If there are more than one candidate, the new scheme turns to the usual ratio-test procedure. Experimental results indicate that this combined method can indeed improve ambiguity search efficiency for both the single constellation and dual constellations, respectively, showing the potential for processing high-dimension integer parameters in multi-GNSS environment.     

一种机载GNSS高精度定位算法

提出部分模糊度固定的加权电离层模型提高大范围全球卫星导航系统(GNSS)航空定位的精度、可靠性及连续性.该方法的主要思路包括:自适应调整大气扰动等误差影响以实现短基线与长基线两类解算模式之间的灵活切换;施加虚拟电离层观测约束信息,提高基线动态定位的浮点解精度;采用部分模糊度固定方法有效挖掘若干模糊度参数的整周约束.试验表明,提出的方法可提高模糊固定效率与定位精度,克服传统方法有效观测信息利用率不足、定位精度较差、可靠性不高以及连续性较差的问题.实验结果表明,部分模糊度固定算法可在2 min内固定95%以上宽巷模糊度解算与80%以上窄巷模糊度,约20 min后可固定所有模糊度.     

一个新的GNSS模糊度估计类

介绍了一类新的GNSS模糊度估计。因为该类遵循移去一恢复原理，称之为整数等变估计类。本文将说明整数等变估计类较整数估计类和线性无偏估计类的范围要大，同时给出一个相当有用的整数等变估计类的表达式。这个表达式揭示了整数等变估计类的结构，并显示该表达式如何在浮点解的基础上实现整数等变估计。最后还提出最优整数估计。     

GNSS双频整周关系约束模糊度算法研究

根据GNSS双频载波相位观测值间的特定关系,提出了一种基于双频整周关系约束的模糊度解算方法(FirCAR)。该方法在局部整数范围内可将载波相位的等效波长增长,以利于整周模糊度的快速解算。不同长度的基线数据实验证明了该算法的正确性和有效性,并分析了卫星截止高度角对解算结果的影响。     

Integer estimation in the presence of biases

 Carrier phase ambiguity resolution is the key to fast and high-precision GNSS (Global Navigation Satellite System) kinematic positioning. Critical in the application of ambiguity resolution is the quality of the computed integer ambiguities. Unsuccessful ambiguity resolution, when passed unnoticed, will too often lead to unacceptable errors in the positioning results. Very high success rates are therefore required for ambiguity resolution to be reliable. Biases which are unaccounted for will lower the success rate and thus increase the chance of unsuccessful ambiguity resolution. The performance of integer ambiguity estimation in the presence of such biases is studied. Particular attention is given to integer rounding, integer bootstrapping and integer least squares. Lower and upper bounds, as well as an exact and easy-to-compute formula for the bias-affected success rate, are presented. These results will enable the evaluation of the bias robustness of ambiguity resolution. Received: 28 September 2000 / Accepted: 29 March 2001     

Penalized GNSS Ambiguity Resolution

Global Navigation Satellite System (GNSS) carrier phase ambiguity resolution is the process of resolving the carrier phase ambiguities as integers. It is the key to fast and high precision GNSS positioning and it applies to a great variety of GNSS models which are currently in use in navigation, surveying, geodesy and geophysics. A new principle of carrier phase ambiguity resolution is introduced. The idea is to give the user the possibility to assign penalties to the possible outcomes of the ambiguity resolution process: a high penalty for an incorrect integer outcome, a low penalty for a correct integer outcome and a medium penalty for the real valued float solution. As a result of the penalty assignment, each ambiguity resolution process has its own overall penalty. Using this penalty as the objective function which needs to be minimized, it is shown which ambiguity mapping has the smallest possible penalty. The theory presented is formulated using the class of integer aperture estimators as a framework. This class of estimators was introduced elsewhere as a larger class than the class of integer estimators. Integer aperture estimators, being of a hybrid nature, can have integer outcomes as well as non-integer outcomes. The minimal penalty ambiguity estimator is an example of an integer aperture estimator. The computational steps involved for determining the outcome of the minimal penalty estimator are given. The additional complexity in comparison with current practice is minor, since the optimal integer estimator still plays a major role in the solution of the minimal penalty ambiguity estimator.     

基于整数可逆模糊度变换和概率计算的GPS动态数据处理快速算法

在讨论整数可逆模糊度变换对模糊度搜索空间影响及直接取整法成功概率的基础上，结合Kalman滤波技术，提出一种新的GPS动态数据处理快速算法－－基于概率计算的模糊度快速分解技术（Probability Based Fast Ambiguity-resolution Technique,简称PBFAT法）。该算法在取整成功概率大于给定限值时，直接对浮点模糊度取整；若取整概率小于给定的值则进行一定范围的模糊度搜索。试验表明该方法的计算速度高于传统方法，所求的模糊度有一个明确的置信水平。     

一种改进的SEVB整数模糊度搜索算法

针对浮点模糊度精度较差时SEVB算法存在搜索耗时较大的问题,提出一种改进的SEVB算法。该算法通过限制初始搜索空间大小和优化计算过程,能够有效减少模糊度搜索候选点个数和不必要的冗余计算,进而提高搜索效率。试验结果分析表明,当浮点模糊度解算精度较低时,改进算法的搜索效率比SEVB算法明显提高,且其搜索耗时不易受模糊度维数及精度的影响,具有更好的稳定性。     

信噪比的GNSS宽巷模糊度单历元固定算法

针对常规GNSS解算模糊度存在的问题,该文提出了一种新的GNSS宽巷模糊度单历元求解算法。利用单历元双频码伪距观测值和载波相位观测值得到双差宽巷模糊度浮点解,将所有浮点宽巷模糊度分别向上、向下取整建立模糊度搜索空间;将模糊度空间中的所有备选组合代入双差宽巷观测方程中进行最小二乘解算,其中单位权中误差最小的组合就是最优的宽巷模糊度组合;然后对最优组合进行正确性检验以确定宽巷模糊度。确定宽巷模糊度后,可以利用宽巷观测值和载波观测值求出基础模糊度整周解。实验表明,该文提出的模糊度固定方法具有较高的成功率和可靠性,静态数据中模糊度固定成功率达到98.84%,动态数据中模糊度固定成功率达到了99.60%。     

An alternative approach to calculate the posterior probability of GNSS integer ambiguity resolution

When precise positioning is carried out via GNSS carrier phases, it is important to make use of the property that every ambiguity should be an integer. With the known float solution, any integer vector, which has the same degree of freedom as the ambiguity vector, is the ambiguity vector in probability. For both integer aperture estimation and integer equivariant estimation, it is of great significance to know the posterior probabilities. However, to calculate the posterior probability, we have to face the thorny problem that the equation involves an infinite number of integer vectors. In this paper, using the float solution of ambiguity and its variance matrix, a new approach to rapidly and accurately calculate the posterior probability is proposed. The proposed approach consists of four steps. First, the ambiguity vector is transformed via decorrelation. Second, the range of the adopted integer of every component is directly obtained via formulas, and a finite number of integer vectors are obtained via combination. Third, using the integer vectors, the principal value of posterior probability and the correction factor are worked out. Finally, the posterior probability of every integer vector and its error upper bound can be obtained. In the paper, the detailed process to calculate the posterior probability and the derivations of the formulas are presented. The theory and numerical examples indicate that the proposed approach has the advantages of small amount of computations, high calculation accuracy and strong adaptability.     

一种整周模糊度快速求解的改进LAMBDA方法

本文提出了一种改进LAMBDA方法:在确定Z变换后的模糊度时,改变以往对所有历元的模糊度全部进行搜索的做法,而是通过设置合理的条件,将搜索与直接归整有效地结合起来,从而减少了模糊度的解算时间,提高了解的效率。文章最后利用实测GPS数据验证了改进效果。