一种快速解算高维模糊度的LLL分块处理算法     

刘万科  卢立果  单弘煜 《测绘学报》2016,45(2):147-156

由于多频多模GNSS观测数据解算的模糊度具有较高的维数和精度,当采用常规的LLL算法进行模糊度整数估计时,规约耗时显著大于搜索耗时,成为限制高维模糊度解算计算效率的主要因素。针对这一问题,通过分析规约耗时与模糊度维数和精度之间的关系,提出了一种LLL分块处理算法。该算法通过对模糊度方差协方差阵进行分块处理,降低单个规约矩阵的维数,以减少规约耗时,从而提高模糊度解算计算效率。通过两组实测高维模糊度数据对本文提出的分块处理算法进行了效果验证。结果显示,当分块选择合理时,本文提出的算法相对于LLL算法的解算效率分别可提高65.2%和60.2%。  相似文献   

改进的GPS模糊度降相关LLL算法   总被引：2，自引：1，他引：1  

刘志平  何秀凤 《测绘学报》2007,36(3):286-289

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

模糊度降相关应用中的整数正交化过程研究     

范龙  翟国君  柴洪洲 《测绘通报》2012,(12):1-4

为解决格理论中最近向量和最短向量两大难题而提出的经典LLL算法已成功应用到模糊度降相关领域。由于模糊度降相关中对变换矩阵的要求,LLL算法在GS正交化变换过程中加入了取整运算,通过分析发现算法的整数正交过程在取整舍入误差的基础上还会引入新的误差,并且随着变换的进行该误差还会累积,最终影响正交化的效果。在分析的基础上对整数正交化过程进行改进,并且通过计算分析验证改进算法较之前有了很大的改进。  相似文献   

下三角Cholesky分解的整数高斯变换算法   总被引：1，自引：0，他引：1  

卢立果  鲁铁定  吴汤婷  刘万科 《测绘科学》2017,(12):57-62,76

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

GPS模糊度降相关LLL算法的一种改进   总被引：2，自引：0，他引：2  

杨荣华  花向红  李昭  吴继忠 《武汉大学学报(信息科学版)》2010,(1)

针对LLL(Lenstra,Lenstra,Lovasz algorithm)算法的不足,提出了具有自适应性的整数正交变换算法,并采用此算法和升序排序调整矩阵对LLL算法进行了改进。通过LLL算法和改进的LLL算法对随机模拟的600个对称正定矩阵的模糊度方差-协方差阵和30组实测数据进行处理分析,发现改进的LLL算法能够更有效地降低协方差阵的条件数,减小备选模糊度组合数,更有利于整周模糊度的搜索和解算。  相似文献   

Householder正交变换在模糊度降相关算法中的应用     

谢恺  柴洪洲  范龙  明锋 《测绘学院学报》2014,(1)

在GNSS模糊度解算的过程中,由于模糊度之间存在相关性,为减少搜索时间需要对模糊度的协方差矩阵进行降相关处理。降相关算法的优劣将直接影响到模糊度搜索的效率。本文基于Householder正交变换提出了一种新的降相关算法,并利用随机模拟数据和北斗实测数据,从谱条件数、平均相关系数和规约时间3个方面将Householder算法与目前较为流行的LLL算法以及逆整数Cholesky算法进行了对比。通过实验分析得出,Householder算法能够明显改善降相关处理的效果。但是该算法仍存在规约时间较长的不足,需要进一步完善。  相似文献   

基于ICSO的DGPS整周模糊度的求解方法          下载免费PDF全文

欧阳利  黄采伦 《全球定位系统》2020,45(3):41-47

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

GPS降相关算法的比较研究     

夏传甲  徐辉 《全球定位系统》2012,37(5):66-70

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

GNSS模糊度降相关算法及其评价指标研究   总被引：4，自引：0，他引：4  

刘志平  何秀凤  郭广礼  查剑锋 《武汉大学学报(信息科学版)》2011,(3):257-261

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

一种基于排序和乔列斯基分解的模糊度降相关方法     

常志巧  郝金明  陈刘成  穆冬 《测绘科学技术学报》2009,26(6)

通过分析目前存在的逆整数乔列斯基降相关方法--白化变换、基于排序和下三角乔列斯基分解的降相关方法的特点,提出了一种新的模糊度降相关方法.该方法是基于协方差矩阵对角线元素降序排列和上三角乔列斯基分解来达到模糊度降相关的目的.通过实测数据的降相关计算得到:新方法与白化交换相比降相关效果相当,但新方法的效率较高;新方法与基于排序和下三角乔列斯基分解的降相关方法相比降相关效果和效率都相当.  相似文献   

Random simulation and GPS decorrelation   总被引：13，自引：1，他引：13  

Peiliang Xu 《Journal of Geodesy》2001,75(7-8):408-423

 (i) A random simulation approach is proposed, which is at the centre of a numerical comparison of the performances of different GPS decorrelation methods. The most significant advantage of the approach is that it does not depend on nor favour any particular satellite–receiver geometry and weighting system. (ii) An inverse integer Cholesky decorrelation method is proposed, which will be shown to out-perform the integer Gaussian decorrelation and the Lenstra, Lenstra and Lovász (LLL) algorithm, and thus indicates that the integer Gaussian decorrelation is not the best decorrelation technique and that further improvement is possible. (iii) The performance study of the LLL algorithm is the first of its kind and the results have shown that the algorithm can indeed be used for decorrelation, but that it performs worse than the integer Gaussian decorrelation and the inverse integer Cholesky decorrelation. (iv) Simulations have also shown that no decorrelation techniques available to date can guarantee a smaller condition number, especially in the case of high dimension, although reducing the condition number is the goal of decorrelation. Received: 26 April 2000 / Accepted: 5 March 2001  相似文献   

降相关对模糊度解算中搜索效率的影响分析   总被引：1，自引：1，他引：0  

卢立果  刘万科  李江卫 《测绘学报》2015,44(5):481-487

首先理论分析了条件数、正交缺陷度、S(A)等降相关评价指标所表示的几何意义,然后采用LAMBDA算法、LLL规约算法和Seysen规约算法通过模拟和实际数据对模糊度的搜索效果和不同评价指标之间的关系进行了深入计算分析。进一步验证得出"降低模糊度方差分量间的相关性实现最大程度地压缩椭球可以提高搜索效率"的观点是片面的,并通过结果分析表明提高搜索效率的本质在于尽可能地促使基向量按照一定方向排序。  相似文献   

Mixed Integer-Real Valued Adjustment (IRA) Problems: GPS Initial Cycle Ambiguity Resolution by Means of the LLL Algorithm   总被引：4，自引：0，他引：4  

Erik W. Grafarend 《GPS Solutions》2000,4(2):31-44

In order to achieve to GPS solutions of first-order accuracy and integrity, carrier phase observations as well as pseudorange observations have to be adjusted with respect to a linear/linearized model. Here the problem of mixed integer-real valued parameter adjustment (IRA) is met. Indeed, integer cycle ambiguity unknowns have to be estimated and tested. At first we review the three concepts to deal with IRA: (i) DDD or triple difference observations are produced by a properly chosen difference operator and choice of basis, namely being free of integer-valued unknowns (ii) The real-valued unknown parameters are eliminated by a Gauss elimination step while the remaining integer-valued unknown parameters (initial cycle ambiguities) are determined by Quadratic Programming and (iii) a RA substitute model is firstly implemented (real-valued estimates of initial cycle ambiguities) and secondly a minimum distance map is designed which operates on the real-valued approximation of integers with respect to the integer data in a lattice. This is the place where the integer Gram-Schmidt orthogonalization by means of the LLL algorithm (modified LLL algorithm) is applied being illustrated by four examples. In particular, we prove that in general it is impossible to transform an oblique base of a lattice to an orthogonal base by Gram-Schmidt orthogonalization where its matrix enties are integer. The volume preserving Gram-Schmidt orthogonalization operator constraint to integer entries produces “almost orthogonal” bases which, in turn, can be used to produce the integer-valued unknown parameters (initial cycle ambiguities) from the LLL algorithm (modified LLL algorithm). Systematic errors generated by “almost orthogonal” lattice bases are quantified by A. K. Lenstra et al. (1982) as well as M. Pohst (1987). The solution point of Integer Least Squares generated by the LLL algorithm is = (L')⁻¹[L'◯] ∈ ℤ ^m where L is the lower triangular Gram-Schmidt matrix rounded to nearest integers, [L], and = [L'◯] are the nearest integers of L'◯, ◯ being the real valued approximation of z ∈ ℤ ^m , the m-dimensional lattice space Λ. Indeed due to “almost orthogonality” of the integer Gram-Schmidt procedure, the solution point is only suboptimal, only close to “least squares.” ? 2000 John Wiley & Sons, Inc.  相似文献   

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

刘宁 熊永良冯威  徐韶光 《测绘学报》2013,42(2):211-217

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