呂 浩，呂志平，翟樹峰，鄺英才，王福林

（1.信息工程大學(xué) 地理空間信息學(xué)院，鄭州 450000；2.61287部隊，昆明 650000）

一種改進的LLL模糊度規(guī)約算法

呂 浩1，呂志平1，翟樹峰1，鄺英才1，王福林2

（1.信息工程大學(xué) 地理空間信息學(xué)院，鄭州 450000；2.61287部隊，昆明 650000）

整周模糊度的高效解算是GNSS高精度數(shù)據(jù)處理中的關(guān)鍵，基于格論進行GNSS模糊度估計時需要通過格基規(guī)約來實現(xiàn)最優(yōu)整周模糊度向量的快速搜索。針對高維情況下常規(guī)LLL規(guī)約算法輔助整周模糊度解算存在規(guī)約耗時較長和規(guī)約性能有限的問題，引入最小列旋轉(zhuǎn)QR分解技術(shù)對基向量進行預(yù)排序，采用延后尺度規(guī)約和部分尺度規(guī)約來減少規(guī)約過程中的冗余尺度規(guī)約，以改善LLL算法的執(zhí)行效果。分別通過模擬和實測數(shù)據(jù)進行實驗，結(jié)果表明：改進后的LLL算法可以明顯降低格基規(guī)約耗時，實測環(huán)境下其規(guī)約效率相比于傳統(tǒng)方法提高了約 10倍，且能夠保證較好的規(guī)約性能，從而有效提升高維模糊度的解算效率。

模糊度解算；格基規(guī)約；LLL規(guī)約；QR分解；尺度規(guī)約

在GNSS精密定位數(shù)據(jù)處理中，相位整周模糊度的快速、精確解算是保證定位精度和可靠性的關(guān)鍵，也是GNSS研究領(lǐng)域中的熱點問題和難點問題。在眾多的模糊度解算方法中，基于模糊度域內(nèi)的LAMBDA算法應(yīng)用最為廣泛[1]，該方法以整數(shù)最小二乘原理為基礎(chǔ)，通過降低模糊度方差分量間的相關(guān)性來壓縮搜索空間，提高搜索效率。隨后，針對模糊度降相關(guān)問題的多種方法被相繼提出[2-5]。

模糊度解算作為一個整數(shù)最小二乘問題，實際上等價于格理論中的最近向量問題（CVP）[6-7]。由于格的特殊性質(zhì)，為保證高效、精確地求解CVP，首先要對格基進行規(guī)約處理，其中以LLL規(guī)約算法最為流行[8-9]。文獻[10]最早將格基規(guī)約的思想引入到 GNSS整周模糊度解算當(dāng)中；文獻[11]從理論上證明了 LLL規(guī)約算法和LAMBDA降相關(guān)之間的等價性；文獻[12]指出單純的尺度規(guī)約過程對搜索空間和搜索效率沒有影響，并提出了部分尺度規(guī)約；文獻[13]通過改變尺度規(guī)約順序來降低LLL算法計算復(fù)雜度；文獻[14-15]分別采用最小列旋轉(zhuǎn)技術(shù)和貪心算法來減少規(guī)約過程中的基向量交換次數(shù)。近來的研究進一步指出，為提高模糊度搜索效率，格基規(guī)約的本質(zhì)在于盡可能促使基向量按照一定方向排序[16-17]。已有的格基規(guī)約算法主要是圍繞基向量交換條件和尺度規(guī)約的有效性來尋求單一的規(guī)約計算復(fù)雜度的降低或規(guī)約性能的改善，而提高規(guī)約性能往往會導(dǎo)致計算復(fù)雜度的增大，因此需要對兩者進行平衡來減少整體解算耗時。

在解決高維模糊度參數(shù)時，由于規(guī)約耗時通常遠大于搜索耗時，因而減少規(guī)約耗時對于提高模糊度整體解算效率影響顯著。鑒于此，本文在分析LLL規(guī)約算法的基礎(chǔ)上，對該算法進行優(yōu)化改進，在降低規(guī)約復(fù)雜度的同時兼顧規(guī)約性能，并結(jié)合模擬和實測數(shù)據(jù)進行了驗證與分析。

1 基本數(shù)學(xué)模型

1.1 基于格的模糊度估計

基于載波相位測量的GNSS定位模型是一種混合整數(shù)模型，通過經(jīng)典最小二乘可以得到模糊度的實數(shù)解及其方差協(xié)方差陣Q?a?？紤]模糊度的整數(shù)約束，則對應(yīng)的整數(shù)最小二乘的估計準則為：

對Q?a進行Cholesky分解：

其中，B為上三角矩陣。則式(1)可以表示為：

式中，y=B-T為常量。該式在格理論中被稱為最近向量問題，B為基于Q?a獲得的格基。

于是，模糊度解算過程即可轉(zhuǎn)化為求解與目標向量y最近的格上向量，常采用LLL規(guī)約算法來處理此類問題。

1.2 LLL格基規(guī)約

采用經(jīng)典 LLL規(guī)約算法對上述問題進行處理時還需要對基矩陣B進行分解：

若矩陣B*和U中的元素滿足以下條件[8]：

則稱B為LLL規(guī)約基，其中第一項稱為尺度規(guī)約，第二項稱為基向量交換。

在實際解算中，為了保證較好的數(shù)值穩(wěn)定性，?；赒R分解來實現(xiàn)LLL規(guī)約[18-19]。令基矩陣B=QR，其中，Q為正交矩陣，R為上三角矩陣，且對角線元素則有：

于是，LLL算法的規(guī)約條件可以改寫為：

為了滿足上述規(guī)約條件，通常需要構(gòu)造變換矩陣進行規(guī)約操作。

式中，[ ]int為取整操作，利用其右乘基矩陣B即可實現(xiàn)對應(yīng)元素的尺度規(guī)約，同時更新上三角矩陣R。

2）基向量交換（Swap變換）：若不滿足式(6)中條件2的要求，即時，則構(gòu)造初等變換矩陣來調(diào)換的順序，并對上三角矩陣R進行更新。

基于QR分解的LLL規(guī)約同經(jīng)典LLL規(guī)約本質(zhì)上是相同的，但僅基于上三角陣進行變換操作，較為簡便，且擁有更高的浮點精度。

2 LLL改進算法

根據(jù)LLL規(guī)約算法定義可知，其主要由尺度規(guī)約和基向量交換兩部分構(gòu)成，其中：尺度規(guī)約對模糊度搜索效率并無直接影響[14]，而是為了促使基向量得以充分交換；LLL規(guī)約的核心正是通過基向量交換來實現(xiàn)模糊度快速搜索。因此，本文基于規(guī)約效率和規(guī)約性能的平衡這一目的，對LLL算法進行改進。

2.1 延后尺度規(guī)約與部分尺度規(guī)約

在引入新的尺度規(guī)約手段之前，首先對常規(guī)LLL算法中尺度規(guī)約的特點和有效性進行分析。將LLL算法中的尺度規(guī)約分為兩類：第一類是次對角線元素的尺度規(guī)約；第二類是當(dāng)基向量交換條件（Swap條件）不滿足時，對列向量中其余元素進行尺度規(guī)約。這兩類尺度規(guī)約的計算過程如圖1所示。

圖1 LLL算法尺度規(guī)約過程Fig.1 Process of LLL size reduction

由圖1可知，LLL算法中尺度規(guī)約的執(zhí)行是根據(jù)是否滿足Swap條件，在第k層、第max(k-1, 2)層和第k+1層三個規(guī)約層之間循環(huán)往復(fù)，因而相同的規(guī)約層由于基向量交換的影響，必然會導(dǎo)致部分第一類尺度規(guī)約和第二類尺度規(guī)約的重復(fù)執(zhí)行。

1）延后尺度規(guī)約

根據(jù)LLL算法尺度規(guī)約的特點，由于同一規(guī)約層存在重復(fù)規(guī)約，所以只有當(dāng)規(guī)約后能夠進行基向量交換時，第一類規(guī)約才是必需的；除此以外的第一類和第二類規(guī)約均可在規(guī)約基B完成所有基向量交換后再執(zhí)行。

將第一類尺度規(guī)約和基向量交換步驟進行合并，此時的基向量交換條件如下：

其中2維矩陣P表示如下：

利用變換矩陣Zi對格基B和上三角矩陣R進行更新，用Zi右乘R，同時消去R的對角線以下元素。

該過程即為規(guī)約后基向量交換，在對B完成所有上述操作后可以將剩余的第一類和第二類尺度規(guī)約延遲到算法最后執(zhí)行。需要說明的是，延后尺度規(guī)約僅消除LLL算法中基向量交換引起的冗余尺度規(guī)約，不改變基向量交換策略。

2）部分尺度規(guī)約

對于常規(guī)LLL算法，文獻[12]從幾何角度說明了尺度規(guī)約不改變規(guī)約基的施密特正交化向量長度，因而其對于搜索效率并不構(gòu)成影響?？紤]到基向量交換對搜索效率改善的作用，一般僅對次對角線元素進行尺度規(guī)約，亦即第一類尺度規(guī)約；但為了保證算法的有效性和穩(wěn)定性，還需要有選擇性地進行第二類尺度規(guī)約。

在延后尺度規(guī)約中，不影響基向量交換的第一類和第二類尺度規(guī)約被置于算法最后一步。因此，采用部分尺度規(guī)約，對于其中的第二類尺度規(guī)約只在滿足一定條件下進行。

部分尺度規(guī)約針對的是第二類尺度規(guī)約，為避免出現(xiàn)數(shù)值穩(wěn)定性問題而選擇部分執(zhí)行，在不影響基向量交換的基礎(chǔ)上進一步減少了LLL算法的尺度規(guī)約數(shù)。

2.2 最小列旋轉(zhuǎn)QR分解

已有的研究表明，格基規(guī)約的目的是為了使基向量按照特定方向排序[17]。除了尺度規(guī)約的個數(shù)，基向量交換的次數(shù)也會對格基規(guī)約的效率產(chǎn)生影響，且基向量的排序直接影響到規(guī)約基性能的好壞。因此，考慮在正式的格基規(guī)約前可以按照某種準則對規(guī)約基向量進行預(yù)排序，進而減少規(guī)約過程中的基向量交換。

通?；贖ouseholder變換實現(xiàn)QR分解，假設(shè)對格基B的前i-1個向量進行 Householder變換后得到的矩陣為Ri-1。最小列旋轉(zhuǎn)QR分解是指在對格基B進行第i步 QR分解之前，找到對應(yīng)當(dāng)前子矩陣中列向量長度最小的那一列并構(gòu)造初等變換矩陣Ui交換Ri-1的第i列和第j列；然后再構(gòu)造Householder變換矩陣Hi進行常規(guī)的第i步 QR分解，實現(xiàn)矩陣的上三角化最小列旋轉(zhuǎn)QR分解的整體變換過程可以表示為：

顯然，在第i步最小列旋轉(zhuǎn)QR分解完成后，R中的元素滿足如下條件：

根據(jù)Householder變換的性質(zhì)，對矩陣Ri-1Ui進行上三角化并不改變矩陣列向量長度。式(12)表明，通過以上策略能夠保證每一步變換后得到的對角線元素ri,i小于子矩陣中其它列向量長度。

2.3 算法流程

將上述基于LLL算法的改進策略進行整合，主要從尺度規(guī)約和基向量交換兩個方面對算法進行優(yōu)化處理，具體流程見圖2。

圖2 LLL改進算法流程圖Fig.2 Flow chart of modified LLL algorithm

如圖2所示，改進后算法的處理步驟主要包括：基于模糊度方差協(xié)方差陣Q?a構(gòu)造格基B，對原始格基進行最小列旋轉(zhuǎn)QR分解得到上三角陣R；設(shè)定初始的規(guī)約層k，根據(jù)式(8)的基向量交換條件進行判斷，如果成立則進行規(guī)約后基向量交換，即對應(yīng)式(9)的第一類尺度規(guī)約與基向量交換的合并操作，并更新規(guī)約層否則直接進入規(guī)約層k=k+1；若規(guī)約層k≤n，則重復(fù)上步操作直到循環(huán)結(jié)束；最后在第一類尺度規(guī)約的基礎(chǔ)上，根據(jù)當(dāng)前次對角元素是否滿足進行部分第二類尺度規(guī)約。

3 算例分析

文獻[7]提出的基于Householder變換的LLL規(guī)約（HLLL規(guī)約）其實就是基于QR分解的LLL規(guī)約；文獻[20]提出的 HELLL規(guī)約算法實際上是基于最小列旋轉(zhuǎn)和全部尺度規(guī)約的迭代操作。本文將基于延后尺度規(guī)約技術(shù)和QR分解的LLL規(guī)約稱為DLLL算法，將圖2中對應(yīng)的LLL改進算法稱為DPLLL算法。

為了評估 LLL改進算法在模糊度解算中的應(yīng)用效果，分別基于模擬和實測數(shù)據(jù)結(jié)合不同指標對LLL、HLLL、DLLL、HELLL和DPLLL算法進行驗證比較和統(tǒng)計分析。在模糊度解算過程中，模糊度的搜索部分統(tǒng)一采用目前廣泛應(yīng)用的SE-VB算法[5]。實驗環(huán)境為：華碩PC機（Intel Core i7-6700 CPU，2.60GHz，內(nèi)存 8.0GB，64位 Windows10 操作系統(tǒng)），軟件MATLAB R2014a（8.3.0.532）。

3.1 實驗1

利用文獻[2]的隨機模擬方法構(gòu)建模糊度協(xié)方差陣，具體構(gòu)造如下：

式中：U為單位正交矩陣，通過 Givens旋轉(zhuǎn)原理進行構(gòu)造；Λ為對角陣，其元素為矩陣Q?a的特征值的升序排列。當(dāng)Q?a的維數(shù)大于20時，條件數(shù)對數(shù)值取值范圍為[3, 4.5]；低維情況下條件數(shù)對數(shù)值取值范圍為[0, 4.5]。條件數(shù)按照均勻分布在取值范圍內(nèi)隨機產(chǎn)生，特征值也按照均勻分布隨機產(chǎn)生，且最大值λmax與最小值λmin滿足與條件數(shù)c的關(guān)系：在實驗1中，本文分兩組方案進行模擬數(shù)據(jù)實驗。

1）第一組模擬實驗

由式(13)生成10、20、30、40維的仿真數(shù)據(jù)，每一維構(gòu)造100組數(shù)據(jù)，分別采用LLL、HLLL和DLLL算法對每一維數(shù)據(jù)進行模糊度規(guī)約處理，并計算 100組數(shù)據(jù)的平均尺度規(guī)約個數(shù)和平均規(guī)約耗時，結(jié)果如表1所示。由表1可以看出，隨著維數(shù)的增加，模糊度規(guī)約過程中的尺度規(guī)約個數(shù)和規(guī)約耗時均逐漸增加，HLLL與LLL相比僅基于上三角陣操作，其規(guī)約耗時更少但尺度規(guī)約數(shù)不變，而DLLL在HLLL基礎(chǔ)上引入延后尺度規(guī)約技術(shù)，其規(guī)約耗時和尺度規(guī)約數(shù)均明顯小于 HLLL。此外，三種規(guī)約算法的基向量交換部分的步驟相同，因而其處理后的規(guī)約基是一致的。

表1 不同維數(shù)下的尺度規(guī)約數(shù)和規(guī)約耗時Tab.1 Numbers of size reduction and the reduction time in different dimensions

2）第二組模擬實驗

利用隨機模擬方法構(gòu)建 3～40維的模糊度方差協(xié)方差陣，同樣每一維構(gòu)造100組數(shù)據(jù)，分別采用HLLL、HELLL和DPLLL算法對其進行規(guī)約處理。圖3(a)和圖3(b)分別為三種算法對應(yīng)100組數(shù)據(jù)的平均尺度規(guī)約數(shù)和平均基向量交換數(shù)隨不同維數(shù)的變化趨勢。圖4為對應(yīng)不同維數(shù)下的平均規(guī)約耗時的情況。

圖3 不同維數(shù)下的尺度規(guī)約數(shù)和基向量交換數(shù)Fig.3 Numbers of size reduction and base vectors swapping in different dimensions

從圖3中可以看出，三種算法的尺度規(guī)約數(shù)和基向量交換數(shù)均與維數(shù)成正相關(guān)關(guān)系，即隨著維數(shù)的增大而呈整體上升趨勢，其中改進后的 DPLLL規(guī)約算法擁有最少的尺度規(guī)約數(shù)和基向量交換數(shù)，且明顯小于HLLL和HELLL算法。

從圖4中可以看出，三種算法的規(guī)約耗時均隨著維數(shù)的增加而變大，其中：HELLL在低維（10維以下）可能存在耗時大于HLLL的情況，隨著維數(shù)增加HELLL規(guī)約時間要小于HLLL算法；而DPLLL則由于大大減少了尺度規(guī)約和基向量交換的操作次數(shù)，所需要的規(guī)約耗時最少。

圖4 不同維數(shù)下的規(guī)約耗時Fig.4 Reduction time in different dimensions

3.2 實驗2

為進一步驗證改進后算法的有效性，采用HLLL、HELLL和DPLLL算法基于實測GNSS數(shù)據(jù)進行實驗。實驗選取基線長約為10.5 km的GPS+BeiDou雙頻數(shù)據(jù)單歷元處理后的模糊度及其方差協(xié)方差陣，接收機型號為Trimble NETR9，采樣間隔為30 s，歷元數(shù)為200，模糊度維數(shù)均在30維以上。

圖5為三種規(guī)約算法200個歷元下的規(guī)約耗時情況，從圖中可以看出，DPLLL算法的規(guī)約耗時最小，而HELLL與HLLL算法的規(guī)約時間在實測環(huán)境下無明顯大小差異規(guī)律，這可能與HELLL算法迭代操作過程有關(guān)，其中DPLLL算法的平均規(guī)約耗時僅為傳統(tǒng)算法的1/10。

圖5 不同歷元下的規(guī)約耗時Fig.5 Reduction time in different epochs

進一步地，鑒于格基規(guī)約的本質(zhì)在于促使基向量按特定方向排序，以規(guī)約得到的規(guī)約基的施密特正交化向量長度排列趨勢來衡量不同規(guī)約算法的性能[7]，如圖6所示。從圖6中可以看出：HLLL算法規(guī)約后的正交化向量長度排列抖動較大；DPLLL算法由于采用最小列旋轉(zhuǎn)QR分解進行預(yù)排序，其排列趨勢明顯改善；而HELLL算法通過迭代處理可獲得滿足式(12)的更強的規(guī)約基，其正交化向量長度排列最為平緩，從而說明其規(guī)約后的性能要優(yōu)于HLLL和DPLLL算法。這里 HELLL算法可獲得性能最優(yōu)的規(guī)約基，但由圖4和圖5可知，相比于DPLLL算法，HELLL算法并不能有效提高規(guī)約效率。

圖6 單歷元規(guī)約后正交化向量長度變化趨勢Fig.6 Trend of the length of orthogonal vectors after reduction in single epoch

圖7(a)和圖7(b)分別對應(yīng)三種算法不同歷元下的搜索耗時和模糊度整體解算耗時。由圖 7(a)可知，HELLL算法的搜索耗時小于其他兩種算法，這與圖6的分析是一致的，即HELLL算法獲得的規(guī)約基性能最優(yōu)，DPLLL算法次之。但在高維模糊度解算中，搜索耗時占模糊度整體解算耗時的比例很小，減少模糊度整體解算耗時的關(guān)鍵在于提高規(guī)約效率，而不是單一地追求性能最優(yōu)，因此考慮結(jié)合規(guī)約耗時來比較三種算法對模糊度解算效果的影響。根據(jù)圖7(b)可以發(fā)現(xiàn)，同時顧及模糊度規(guī)約和搜索過程時，本文提出的DPLLL算法的整體解算耗時最小，即模糊度處理整體效率最高。

圖7 不同歷元下的搜索耗時和整體解算耗時Fig.7 Search time and entire computation time in different epochs

4 結(jié) 論

本文在分析 LLL規(guī)約算法的流程和特點的基礎(chǔ)上，通過引入最小列旋轉(zhuǎn)QR分解、延后尺度規(guī)約和部分尺度規(guī)約技術(shù)對常規(guī)LLL算法進行改進，提出了DPLLL規(guī)約算法，并基于仿真和實測數(shù)據(jù)進行了驗證分析。從實驗結(jié)果可以看出，改進后的算法可以有效減少格基規(guī)約過程中的尺度規(guī)約數(shù)和基向量交換數(shù)，并且能夠獲得較好的規(guī)約性能，顯著改善了LLL算法的規(guī)約效果。利用 DPLLL算法處理的規(guī)約效率和模糊度整體解算效率都得到了明顯提高，從而有利于模糊度解算的快速實現(xiàn)。同時，隨著組合系統(tǒng)定位和觀測頻率的增加，如何更好地平衡高維模糊度解算過程中的規(guī)約效率和規(guī)約性能將是下一步研究的重點。

（References）：

[1]Li B, Verhagen S, Teunissen P J G.GNSS integer ambiguity estimation and evaluation: LAMBDA and Ps-LAMBDA[C]//Proceedings of China Satellite Navigation Conference.Wuhan, 2013: 291-301.

[2]Xu P L.Random simulation and GPS decorrelation[J].Journal of Geodesy, 2001, 75: 408-423.

[3]Chang X, Yang X, Zhou T.MLAMBDA: a modified LAMBDA method for integer least-squares estimation[J].Journal of Geodesy, 2005, 79(9): 552-565.

[4]Xu P L.Parallel cholesky-based reduction for the weighted integer least squares problem[J].Journal of Geodesy,2012, 86(1): 35-52.

[5]李豹, 許江寧, 曹可勁, 等.改進 LAMBDA 算法實現(xiàn)單頻GPS 整周模糊度快速解算[J].中國慣性技術(shù)學(xué)報,2013, 21(3): 365-368.Li B, Xu J N, Cao K J, et al.Fast resolution of single frequency GPS integer ambiguity realized by improved LAMBDA algorithm[J].Journal of Chinese Inertial Technology, 2013, 21(3): 365-368.

[6]劉經(jīng)南, 于興旺, 張小紅.基于格論的GNSS模糊度解算[J].測繪學(xué)報, 2012, 41(5): 636-645.Liu J N, Yu X W, Zhang X H.GNSS ambiguity resolution using lattice theory[J].Acta Geodaetica et Cartographica Sinica, 2012, 41(5): 636-645.

[7]范龍.基于格理論的 GNSS模糊度估計方法研究[D].鄭州: 信息工程大學(xué), 2013.Fan L.Research on method of integer ambiguity estimation with lattice theory[D].Zhengzhou: Information Engineering University, 2013.

[8]Aliev I, Henk M.LLL-reduction for integer knapsacks[J].Journal of Combinatorial Optimization, 2012, 24(4): 613-626.

[9]Neumaier A, Stehle D.Faster LLL-type reduction of lattice bases[C]//Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation.Canada, 2016: 373-380.

[10]Hassibi A, Boyed S.Integer parameter estimation in linear models with applications to GPS[J].IEEE Transactions on Signal Processing, 1998, 46(11): 2938-2952.

[11]Lannes A.On the theoretical link between LLL-reduction and Lambda-decorrelation[J].Journal of Geodesy, 2013,87(4): 323-335.

[12]Cong L, Howgrave-graham N.Effective LLL reduction for lattice decoding[C]//IEEE International Symposium on Information Theory.Nice, France, 2007: 196-200.

[13]Luo Y X, Qiao S Z.A parallel LLL algorithm[C]//Proceedings of the Fourth International C* Conference on Computer Science and Software Engineering.Montreal.Quebec, Canada, 2011: 93-101.

[14]Xie X, Chang X W.Borno M A.Partial LLL reduction[C]//Proceeding of IEEE GLOBECOM.Houston, USA, 2011.

[15]盧立果, 劉萬科, 李江衛(wèi).一種有效的LLL規(guī)約算法[J].武漢大學(xué)學(xué)報(信息科學(xué)版), 2016, 41(8):1118-1124.Lu L, Liu W K, Li J W.An effective LLL reduction algorithm[J].Geomatics and Information Science of Wuhan University, 2016, 41(8): 1118-1124.

[16]Borno M A, Chang X W, Xie X H.On decorrelation in solving integer least-squares for ambiguity determination[J].Survey Review, 2014, 46: 37-49.

[17]盧立果，劉萬科，李江衛(wèi).降相關(guān)對模糊度解算中搜索效率的影響分析[J].測繪學(xué)報2015, 44(5)：481-487.Lu L G, Liu W K, Li J W.Impact of decorrelation on search efficiency of ambiguity resolution[J].Acta Geodaetica et Cartographica Sinica, 2015, 44(5): 481-487.

[18]盧立果.基于球形搜索的模糊度格基規(guī)約方法研究與分析[D].武漢: 武漢大學(xué), 2013.Lu L G.The research and analysis based on sphere search for ambiguity on reduction[D].Wuhan: Wuhan University,2013.

[19]Jazaerl S, Amiri-Simkooei A R, Sharifi M A.Fast integer least-squares estimation for GNSS high-dimensional ambiguity resolution using lattice theory[J].Journal of Geodesy,2012, 86: 123-136.

[20]謝愷, 柴洪洲, 范龍, 等.一種改進的LLL模糊度降相關(guān)算法[J].武漢大學(xué)學(xué)報(信息科學(xué)版), 2014, 39(11):1363-1368.Xie K, Chai H Z, Fan L, et al.An improved LLL ambiguity decorrelation algorithm[J].Geomatics and Information Science of Wuhan University, 2014, 39(11): 1363-1368.

[21]Wu M K, He J, Wang H C.Reliable single epoch ambiguity resolution for precise attitude determination using BeiDou triple-frequency observations[J].Journal of Chinese Inertial Technology, 2016, 24(5): 624-631.

Improved LLL ambiguity reduction algorithm

LYU Hao1, LYU Zhi-ping1, ZHAI Shu-feng1, KUANG Ying-cai1, WANG Fu-lin2
(1.Institute of Geography and Spatial Information, Information Engineering University,Zhengzhou 450000, China; 2.Unit 61287 of PLA, Kunming 650000, China)

Efficient ambiguity resolution is the key of GNSS data processing with high precision.Based on the lattice theory, the computational efficiency of searching the optimal integer ambiguity vector can be improved by using lattice reduction.According to the fact that the routine LLL reduction algorithm for ambiguity resolution under high-dimensional case has long reduction time and limited reduction performance, the QR factorization with minimum column pivoting was introduced to preorder the reduction base vectors, and the algorithms of delayed size reduction and partial size reduction were used to reduce the number of redundant size reduction.These methods were optimally combined to improve the implementation effects of LLL reduction algorithm.Experiments with simulated and real GNSS data were executed,respectively.The consequence shows that the modified LLL algorithm can effectively reduce the reduction time and provide better performance than those of current reduction methods.The computing efficiency of lattice reduction using the proposed method with real data is improved by nearly 10 times than those of traditional algorithms.Therefore the computational efficiency of ambiguity resolution under high-dimensional case can be improved significantly by using the proposed algorithm.

ambiguity resolution; lattice reduction; LLL reduction; QR decomposition; size reduction

P228.1

A

1005-6734(2017)05-0611-07

10.13695/j.cnki.12-1222/o3.2017.05.010

2017-07-25；

2017-09-10

國家自然科學(xué)基金（41674019）；國家重點研發(fā)計劃（2016YFB0501701）

呂浩（1989—），男，博士研究生，從事測量數(shù)據(jù)處理理論與方法研究。E-mail: lyangeo@126.com