【作者】 范龙；

【导师】 翟国君；

【作者基本信息】 解放军信息工程大学 ， 大地测量学与测量工程， 2013， 博士

【摘要】 随着卫星导航系统的建设和发展，卫星定位技术的应用领域不断扩大，用户对定位结果的精度和可靠性的要求也越来越高。高精度的定位过程中，整周模糊度的正确解算是保证定位精度的关键因素，本文基于数学中的格理论对整周模糊度的估计方法进行了研究，论文的主要成果和创新点概括如下：1.为了获得最终的位置结果，需要首先将既包含实数未知参数又包含整数未知参数的混合整数模型转化为整数模型进行解算，讨论了基于最小二乘准则和基于Bayesian准则的两种转换过程，并且证明了两类准则下转换得到的整数模型是一致的。2.针对LLL降相关算法利用整数Gram Schmidt变换进行处理，变换过程受取整舍入误差的影响严重，而导致高维情况下出现降相关失败的问题，提出了一种整数分块正交变换法，并且基于这种变换设计了基于整数分块正交变换的LLL降相关算法。通过计算分析，证明了新方法的降相关性能有了很大的提高。3.深入研究了格的定义，特点以及格上的两个著名难题，通过对模糊度解算的整数最小二乘模型的分析，对协方差矩阵进行三角分解即可构造出模糊度解算对应的格，而模糊度搜索固定的问题等价于格上的最近向量问题，在此基础上，提出了基于格的模糊度解算方法。4.分析研究了LLL规约基及两种实现算法。由于格基具有多样性，格基性能的好坏将会影响到格上CVP解算的效率和成功率，对于基于格的模糊度解算来说，需要通过格基规约的方式选择出最适合问题解算的那组基。通过对LLL规约基的分析，掌握了格基规约的原理、过程与根本目标，同时对基于Gram Schmidt变换和基于Householder变换的两种LLL规约基的实现方法进行研究。5.提出了一种扩展的LLL规约基，其长度规约的约束条件要高于LLL规约，可保证在所有的基向量范围内实现长度规约。为了实现E-LLL规约基，首先设计了基于系统旋转的Householder变换，其可在规约开始之前就保证基向量能够按照其正交化向量长度由小到大的顺序排列，从而提高规约的效率，其次基于这种变换方式提出了HE-LLL规约算法，该方法在系统旋转变换的辅助下，对基向量逐一进行大小规约和长度规约处理，最终可保证获得E-LLL规约基。通过利用实测数据进行计算，验证了HE-LLL算法不仅提高规约效果，而且提高了规约的效率。6.提出了一种改进的BKZ规约算法，BKZ规约是在LLL规约的基础上对格基进行进行分块处理，保证每个分块中的基向量能够满足KZ规约的条件，其规约的效果和效率取决于分块的大小，分块越大则效果越好同时效率也越低，为了优化规约的效率，基于HE-LLL进行了改进，通过利用实测和模拟数据的分析，验证了改进的BKZ算法的计算效率要明显优于BKZ规约基，同时其规约效果在理论上也优于HE-LLL规约。7.研究了基于深度优先搜索模式的VB-SD和SE-SD算法，并且对格基规约过程对其搜索空间的影响进行了分析，证明了格基规约的大小规约过程并不能改善搜索空间，而只有长度规约才会对搜索的效率和成功率产生影响，通过利用实测数据在不同情况下的分析证明了以上结论。8.提出了基于HE-LLL规约的K-best搜索算法，基于深度优先的搜索算法由于需要进行复杂的迭代分析，在高维情况下效率较低，以K-best算法为代表的基于广度优先模式的球形搜索算法由于每次只搜索k个候选值，所以具有比较固定的复杂度，但是这导致了它是一种次优的算法。为了满足模糊度解算的精度要求，在格基质量和搜索半径约束两个方面进行了改进，利用实测数据进行了计算分析，结果表明本文提出的方法只需选取较小的k值即可获得模糊度的最优解，并且其效率稳定不会随着维数的增加而产生很大的变化，适用于高维的模糊度解算。9. Voronoi cell作为一种具有对偶性质的凸域几何结构，可用来对格上相关问题进行分析研究。通过对格上向量对应的Voronoi cell的分析，将模糊度CVP求解的问题转化为求解目标向量在原点的Voronoi cell中对应向量的问题。利用Voronoi相关向量来构造原点对应的Voronoi cell，并且在此基础上设计了基于Voronoi cell的模糊度CVP解算方法，利用一组模拟的2维数据，对算法的模糊度解算过程进行了分析，基于其构造的Voronoi cell对结果的可靠性进行评价，同时选取几组实测数据进一步验证了算法的正确性。更多还原

【Abstract】 With the construction and development of satellite navigation system, the application area ofsatellite positioning is enlarging and consumers’ requirements for the precision and reliability ofpositioning results are growing. In the process of high-precision positioning, the correctness ofinteger ambiguity resolution is the key factor in guaranteeing the positioning precision. Thisdissertation studied the integer ambiguity estimation based on the lattice theory in math. Themain achievement and creative points are as follows:1. In order to obtain the final positioning results, the mixed integer model which doesn’t onlycontain unknown parameters of real numbers, but also contains unknown parameters ofinteger numbers should be transformed to integer model first. Then two kinds oftransforming process are discussed based on least squares criterion and Bayesian criterion.And it is proved that the integer models obtained with the two criterions are consistent.2. The LLL decorrelation algorithm uses integer Gram Schmidt transformation to compute.Due to the impact of round-off error, it usually fails to decorrelate in circumstances of highdimensions. To solve this problem, an integer block orthogonal transformation method isproposed and an LLL decorrelation algorithm is designed based on this transformation.With computation and analysis, it proves that the new method can greatly improve thedecorrelation.3. The definition, character and two famous problems of lattice are studied thoroughly. Afteranalyzing the integer least squares model of ambiguity resolution, lattice referring toambiguity resolution can be made to conduct triangular decomposition of covariance matrix.The search and fix of ambiguity is equivalent to the nearest vector problem in lattice. Onthis basis, the ambiguity resolution algorithm based on lattice is proposed.4. The LLL reduction base and two algorithms are studied. Since there is a diversity of latticebase, the quality of lattice base will affect the efficiency and success rate of CVP resolutionin lattice. For the ambiguity resolution based on lattice, a most suitable group should bechose according to lattice reduction. After analyzing the LLL reduction base, the principle,process and ultimate goal are mastered. At the same time, two methods based on LLLreduction base of Gram Schmidt and Householder transformation are studied.5. An extended LLL reduction base is proposed. The restriction of its length reduction isstricter than LLL reduction which can guarantee the realization of length reduction in rangesof all base vectors. For fulfillment of E-LLL reduction, the Householder transformationbased on systematic rotation is designed. It guarantees that the basic vector can be arranged from short to long according to the length of orthogonal vectors which improves thereduction efficiency. Then the HE-LLL reduction algorithm is proposed based on thistransformation. This algorithm conducts size and length reduction of basic vector with theassist of systematic rotation transformation which can guarantee the acquisition of E-LLLreduction base finally. Using observed data for computation, it proves that HE-LLLalgorithm not only improves reduction effect, but also improves the reduction efficiency.6. An improved BKZ reduction algorithm is proposed. BKZ reduction disparts the lattice baseon the basis of LLL reduction and guarantees that basic vector in each block satisfies KZreduction. But the reduction effect relies on the size of blocks. The bigger the blocks, thebetter the effect while the worse the efficiency. In order to promote the efficiency of BKZreduction, the HE-LLL is used to optimize. With analysis of observed and simulated data,the computational efficiency of promoted BKZ algorithm is obviously better than BKZreduction, and the base reduction effect is better the HE-LLL reduction algorithm in theory.7. The VB-SD and SE-SD algorithms based on depth-first searching mode are studied. Andthe impact of lattice reduction process on searching space is analyzed. It proves that theprocess of lattice size reduction cannot improve the searching space, whereas only lengthreduction can affect the searching efficiency and success rate. Analysis with Observed datain different circumstances proves the conclusion above.8. The K-best searching algorithm based on HE-LLL reduction is proposed. Since thedepth-first searching algorithm needs complex iteration process, the efficiency is low inhigh-dimensional circumstance. The sphere searching algorithm based on breadth-firstmode which is represented by K-best algorithm, searches only k candidates, therefore it hasrelatively stable complexity, while leading this to be a suboptimal algorithm. In demand ofambiguity estimation, an improvement has been made on aspects of lattice base quality andsearching radius restriction. Observed data is used for computation analysis. Results haveshown that the method proposed in this paper only requires relatively small value of k toobtain the optimal ambiguity resolution and the efficiency is stable which will not changemuch with the increase of dimensions. It suits for high-dimensional ambiguity resolution.9. Voronoi cell, as a convex geometry structure which has dual concept, can be used to studyand analyze related questions in lattice. After analyzing the corresponding Voronoi cell inlattice vectors, the problem of ambiguity CVP resolution is transformed to resolving thecorresponding vector in the Voronoi cell whose target vector is at the origin. Using theVoronoi-related vector to construct the Voronoi cell correspond to the origin, the ambiguityCVP resolution method based on the Voronoi cell is designed on this basis. Using a set ofsimulated two-dimensional data, the ambiguity resolution process of the algorithm is analyzed and the stability of the results based on the Voronoi cell is estimated. Several setsof observed data is chosen to further prove the correctness of the algorithm.更多还原