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.     

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

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

Zero-correlation transformation and threshold for efficient GNSS carrier phase ambiguity resolution

The key point of accurate and precise applications of Global Navigation Satellite Systems lies in knowing how to efficiently obtain correct integer ambiguity. One of the methods in solving the ambiguity resolution problem is applying the ambiguity searching technique coupled with an ambiguity decorrelation technique. Traditionally, an integer-valued limitation of the transformation matrix ensures that the integer characteristic of candidates exists after the inverse transformation, but this also makes the decorrelation imperfect. In this research, the float transformation matrix will be considered. To ensure both the integer characteristic and perfect decorrelation can be reached, the float transformation is used indirectly. To solve the ambiguity resolution problem, the problem is transformed by integer and float transformation matrices. The objective of integer transformation is reducing the number of candidates. The target of float transformation is validating these reduced candidates. A zero correlation domain or a near complete diagonalization covariance matrix can be obtained via the float transformation. A space in this domain will be used as the threshold; hence the zero correlation domain is called the threshold domain. The number of ambiguity candidates based on integer transformation can be reduced once again through the proposed method. The experiments in this paper prove that the method can make the ambiguity resolution become more efficient without any drop in the accuracy.     

单频GPS动态定位中整周模糊度的一种快速解算方法

针对单频GPS动态定位中常用模糊度求解方法存在的问题,提出一种整周模糊度快速解算方法。首先通过对双差观测方程中坐标参数的系数阵进行QR分解变换以消除坐标参数,从而仅对模糊度参数建立Kalman滤波方程进行估计,然后利用排序和双Cholesky分解对滤波得到的模糊度进行降相关处理,并结合收缩模糊度搜索空间的思想来搜索固定整周模糊度。以实测的动态数据为例对该方法进行测试。分析结果表明,该方法不但可以改善模糊度浮点解精度,而且具有良好的模糊度降相关效果,可正确有效地实现整周模糊度的快速解算。     

GNSS模糊度降相关算法及其评价指标研究

针对Gauss、LDL和LLL算法构造整数阵存在的实数阵元素计算、实数至整数阵转换的排序问题,分别研究了相应的元素升序降相关算法和整逆型(先求逆后取整)降相关算法。分析了谱条件数、降相关系数和平均相关系数等降相关算法评价指标的优缺点,提出了等效相关系数评价指标。研究结果表明,等效相关系数较其他3种指标能更有效地评价不同维数方差阵,尤其是高维情况的降相关算法效果;逆整型优于整逆型降相关算法,升序(逆整型)降相关算法更佳,且优劣顺序为升序LDL、升序Gauss和升序LLL算法。     

GPS降相关算法的比较研究

利用矩阵分解理论分别对整数高斯法、联合去相关法、基于矩阵乔里斯基分解的迭代法、逆整数乔里斯基法和LLL法等降相关算法进行了分类和比较。仿真计算表明：逆整数乔里斯基分解法优于联合去相关法,联合去相关法优于LLL法。     

A new approach to GPS ambiguity decorrelation

Ambiguity decorrelation is a useful technique for rapid integer ambiguity fixing. It plays an important role in the least-squares ambiguity decorrelation adjustment (Lambda) method. An approach to multi-dimension ambiguity decorrelation is proposed by the introduction of a new concept: united ambiguity decorrelation. It is found that united ambiguity decorrelation can provide a rapid and effective route to ambiguity decorrelation. An approach to united ambiguity decorrelation, the HL process, is described in detail. The HL process performs very well in high-dimension ambiguity decorrelation tests. Received: 9 March 1998 / Accepted: 1 June 1999     

一种单频单历元BDS／GPS组合整周模糊度解算方法

针对单频单历元组合载波相位差分技术(RTK)定位过程中存在的秩亏及模糊度解算病态等问题,提出了一种模糊度降相关的新方法。该方法引入伪距观测值进行辅助解算。首先采用经验分权法对伪距与载波相位观测值分配权重,并通过加权最小二乘法获得整周模糊度浮点解及协方差。然后通过对整周模糊度浮点解的方差-协方差矩阵进行降序排列和剔除病态模糊度。最后利用修正后的浮点解迭代搜索模糊度的整数解。试验结果表明而且可以起到良好的模糊度降相关的效果定位。      

The least-squares ambiguity decorrelation adjustment: its performance on short GPS baselines and short observation spans

The least-squares ambiguity decorrelation adjustment is a method for fast GPS double-difference (DD) integer ambiguity estimation. The performance of the method will be discussed, and although it is stressed that the method is generally applicable, attention is restricted to short-baseline applications in the present contribution. With reference to the size and shape of the ambiguity search space, the volume of the search space will be introduced as a measure for the number of candidate grid points, and the signature of the spectrum of conditional variances will be used to identify the difficulty one has in computing the integer DD ambiguities. It is shown that the search for the integer least-squares ambiguities performs poorly when it takes place in the space of original DD ambiguities. This poor performance is explained by means of the discontinuity in the spectrum of conditional variances. It is shown that through a decorrelation of the ambiguities, transformed ambiguities are obtained which generally have a flat and lower spectrum, thereby enabling a fast and efficient search. It is also shown how the high precision and low correlation of the transformed ambiguities can be used to scale the search space so as to avoid an abundance of unnecessary candidate grid points. Numerical results are presented on the spectra of conditional variances and on the statistics of both the original and transformed ambiguities. Apart from presenting numerical results which can typically be achieved, the contribution also emphasizes and explains the impact on the method's performance of different measurement scenarios, such as satellite redundancy, single vs dual-frequency data, the inclusion of code data and the length of the observation time span. Received: 31 October 1995 / Accepted: 21 March 1997     

基于格论的GNSS模糊度解算

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

网络RTK参考站间模糊度动态解算的卡尔曼滤波算法研究

提出一种适用于参考站网络的站间模糊度解算方法,该方法使用CA码与相位的电离层无关组合解算宽巷模糊度,利用多路径效应的周期性削弱CA码多路径效应。在宽巷模糊度得到固定后,利用卡尔曼滤波对L1模糊度进行估计,并使用模糊度失相关搜索算法,动态地确定模糊度。这种方法已经应用在自主开发的网络RTK软件上,并以四川GPS综合服务网络SIGN(Sichuan Integrated GPS Network)作为试验网络,进行了试验和分析。     

Precise GRACE baseline determination using GPS

Precision relative navigation is an essential aspect of spacecraft formation flying missions, both from an operational and a scientific point of view. When using GPS as a relative distance sensor, dual-frequency receivers are required for high accuracy at large inter-satellite separations. This allows for a correction of the relative ionospheric path delay and enables double difference integer ambiguity resolution. Although kinematic relative positioning techniques demonstrate promising results for hardware-in-the-loop simulations, they were found to lack an adequate robustness in real-world applications. To overcome this limitation, an extended Kalman Filter modeling the relative spacecraft dynamics has been developed. The filter processes single difference GPS pseudorange and carrier phase observations to estimate the relative position and velocity along with empirical accelerations and carrier phase ambiguities. In parallel, double difference carrier phase ambiguities are resolved on both frequencies using the least square ambiguity decorrelation adjustment (LAMBDA) method in order to fully exploit the inherent measurement accuracy. The combination of reduced dynamic filtering with the LAMBDA method results in smooth relative position estimates as well as fast and reliable ambiguity resolution. The proposed method has been validated with data from the gravity recovery and climate experiment (GRACE) mission. For an 11-day data arc, the resulting solution matches the GRACE K-Band Ranging System measurements with an accuracy of 1 mm, whereby 83% of the double difference ambiguities are resolved.     

改进的GPS模糊度降相关LLL算法

模糊度降相关技术可以有效提高模糊度求解的效率及成功率,LLL(A.K.Lenstra,H.W.Lenstra,L.Lovasz)算法是新出现的模糊度降相关方法。详细分析LLL算法,针对该算法中存在的缺陷,提出逆整数乔勒斯基、整数高斯算法和升序调整矩阵辅助的改进LLL算法。利用谱条件数及平均相关系数为准则,以300个随机模拟的对称正定矩阵作为模糊度方差-协方差矩阵,对LLL算法和改进的LLL算法进行仿真计算。比较与分析结果表明,改进LLL算法模糊度降相关处理更加彻底,能有效地加速整周模糊度搜索及成功解算。     

GNSS模糊度降相关性能的条件方差平稳度评价法

GNSS模糊度降相关通过整数变换优化条件方差的排列顺序,提高搜索效率。降相关和条件方差的关系及其评价是关键问题之一。针对这一问题,本文从理论上分析了排序后模糊度降相关与条件方差之间的数值关系,发现降相关性能与条件方差数值序列的平稳性有关,降相关性能越强,条件方差数值序列越平稳。基于这一理论关系,给出了"条件方差平稳度"定义,并将其作为评价降相关性能的指标。通过模拟和实测数据验证,并采用条件方差变化趋势图和搜索时间来定性和定量评价降相关性能,用以判定条件方差平稳度的合理性。试验结果表明,条件方差平稳度可以较精确直观地衡量模糊度的降相关性能。本文定义的指标揭示了模糊度降相关的本质。     

Performance analysis of triple-frequency ambiguity resolution with BeiDou observations

We investigate triple-frequency ambiguity resolution performance using real BeiDou data. We test four ambiguity resolution (AR) methods which are applicable to triple-frequency observations. These are least squares ambiguity decorrelation adjustment (LAMBDA), GF-TCAR (geometry-free three-carrier ambiguity resolution), GB-TCAR (geometry-based three-carrier ambiguity resolution) and GIF-TCAR (three-carrier ambiguity resolution based on the geometry-free and ionospheric-free combination). A comparison between LAMBDA, GF-TCAR and GB-TCAR was conducted over three short baselines and two medium baselines. The results indicated that LAMBDA is optimal in both short baseline and medium baseline cases. However, the performances of GB-TCAR and LAMBDA differ slightly for short baselines. Compared with GF-TCAR, which uses the geometry-free model, the GB-TCAR using the geometry-based model improves the AR performance significantly. Compared with dual-frequency observations, the LAMBDA AR results show a significant improvement when using triple-frequency observations over short baselines. The performance of GIF-TCAR is evaluated using multi-epoch observations. The results indicated that multi-path errors on carrier phases will have a significant influence on GIF-TCAR AR results, which leads to different GIF-TCAR AR performance for different type of satellites. For GEO (Geostationary Orbit) satellites, the ambiguities can barely be correctly fixed because the multi-path errors on carrier phases are very systematic. For IGSO (Inclined Geosynchronous Orbit) and MEO (Medium Earth Orbit) satellites, when the elevation cutoff angle is set as 30°, several tens to several hundreds of epochs are needed for correctly fixing the narrow lane ambiguities. The comparison of positioning performance between dual-frequency observations and triple-frequency observations was also conducted. The results indicated that a minor improvement can be achieved by using triple-frequency observations compared with using dual-frequency observations.     

整周模糊度去相关的两种实现方法

整周模糊度搜索一直是GPS快速精确定位的关键问题。短时间的观测会导致观测方程和整周模糊度方差、协方差矩阵的高相关性，因而急剧增大整周模糊度的搜索空间，对整周模糊度未知数方差、协方差矩阵进行去相关性处理，可以有效地压缩搜索空间。本文对整周模糊度去相关的迭代法和联合变换法从原理上进行了阐述，并结合实际算倒进行了分析和比较。     

基于ICSO的DGPS整周模糊度的求解方法

针对差分全球定位系统(DGPS)模糊度解算过程中效率低,搜索慢的问题,对鸡群优化算法(CSO)进行适应性改进,并将改进后的鸡群优化算法(ICSO)应用到整周模糊度的快速解算中,利用卡尔曼滤波求出双差模糊度的浮点解和协方差矩阵,采用Lenstra-Lenstra-Lovasz (LLL)降相关算法对模糊度的浮点解和方差协方差矩阵进行降相关处理,以降低模糊度各分量之间的相关性,在基线长度固定的情况下,利用ICSO搜索整周模糊度的最优解. 采用经典算例进行仿真,仿真结果表明,与已有文献相比在整周模糊度的解算过程中改进的鸡群优化算法能有效提高搜索速度和求解成功率.      

差分GPS载波相位整周模糊度快速解算方法

本文提出了一种整周模糊度的快速求解方法,将差分GPS的测量值分配到主要测量值集合和次要测量值集合中,用主要集合中的相位测量值限定简约搜索空间,而次要集合中的相位测量值用来验证候选集合。利用已知的基线长度的约束条件,对搜索空间进行了简约,提高了求解整周模糊度的速度,同时,通过Cholesky分解提高搜索效率。     

Fast integer least-squares estimation for GNSS high-dimensional ambiguity resolution using lattice theory

GNSS ambiguity resolution is the key issue in the high-precision relative geodetic positioning and navigation applications. It is a problem of integer programming plus integer quality evaluation. Different integer search estimation methods have been proposed for the integer solution of ambiguity resolution. Slow rate of convergence is the main obstacle to the existing methods where tens of ambiguities are involved. Herein, integer search estimation for the GNSS ambiguity resolution based on the lattice theory is proposed. It is mathematically shown that the closest lattice point problem is the same as the integer least-squares (ILS) estimation problem and that the lattice reduction speeds up searching process. We have implemented three integer search strategies: Agrell, Eriksson, Vardy, Zeger (AEVZ), modification of Schnorr–Euchner enumeration (M-SE) and modification of Viterbo-Boutros enumeration (M-VB). The methods have been numerically implemented in several simulated examples under different scenarios and over 100 independent runs. The decorrelation process (or unimodular transformations) has been first used to transform the original ILS problem to a new one in all simulations. We have then applied different search algorithms to the transformed ILS problem. The numerical simulations have shown that AEVZ, M-SE, and M-VB are about 320, 120 and 50 times faster than LAMBDA, respectively, for a search space of dimension 40. This number could change to about 350, 160 and 60 for dimension 45. The AEVZ is shown to be faster than MLAMBDA by a factor of 5. Similar conclusions could be made using the application of the proposed algorithms to the real GPS data.