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

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

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

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

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

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

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

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

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

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

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

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

1.1 基于格的模糊度估計(jì)

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

對(duì)Q?a進(jìn)行Cholesky分解：

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

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

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

1.2 LLL格基規(guī)約

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

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

則稱B為L(zhǎng)LL規(guī)約基，其中第一項(xiàng)稱為尺度規(guī)約，第二項(xiàng)稱為基向量交換。

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

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

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

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

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

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

2 LLL改進(jìn)算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 算法流程

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

圖2 LLL改進(jìn)算法流程圖Fig.2 Flow chart of modified LLL algorithm

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

3 算例分析

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

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

3.1 實(shí)驗(yàn)1

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

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

1）第一組模擬實(shí)驗(yàn)

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

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

2）第二組模擬實(shí)驗(yàn)

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

圖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ù)的增大而呈整體上升趨勢(shì)，其中改進(jìn)后的 DPLLL規(guī)約算法擁有最少的尺度規(guī)約數(shù)和基向量交換數(shù)，且明顯小于HLLL和HELLL算法。

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

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

3.2 實(shí)驗(yàn)2

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

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

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

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

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

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

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

4 結(jié) 論

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

（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]李豹, 許江寧, 曹可勁, 等.改進(jìn) LAMBDA 算法實(shí)現(xiàn)單頻GPS 整周模糊度快速解算[J].中國(guó)慣性技術(shù)學(xué)報(bào),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].測(cè)繪學(xué)報(bào), 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模糊度估計(jì)方法研究[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àn)科, 李江衛(wèi).一種有效的LLL規(guī)約算法[J].武漢大學(xué)學(xué)報(bào)(信息科學(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àn)科，李江衛(wèi).降相關(guān)對(duì)模糊度解算中搜索效率的影響分析[J].測(cè)繪學(xué)報(bào)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]謝愷, 柴洪洲, 范龍, 等.一種改進(jìn)的LLL模糊度降相關(guān)算法[J].武漢大學(xué)學(xué)報(bào)(信息科學(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

國(guó)家自然科學(xué)基金（41674019）；國(guó)家重點(diǎn)研發(fā)計(jì)劃（2016YFB0501701）

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