一種改進的LLL模糊度規約算法

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

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

一種改進的LLL模糊度規約算法

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

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

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

模糊度解算；格基規約；LLL規約；QR分解；尺度規約

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

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

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

1 基本數學模型

1.1 基于格的模糊度估計

基于載波相位測量的GNSS定位模型是一種混合整數模型，通過經典最小二乘可以得到模糊度的實數解及其方差協方差陣Q?a。考慮模糊度的整數約束，則對應的整數最小二乘的估計準則為：

對Q?a進行Cholesky分解：

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

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

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

1.2 LLL格基規約

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

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

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

在實際解算中，為了保證較好的數值穩定性，常基于QR分解來實現LLL規約[18-19]。令基矩陣B=QR，其中，Q為正交矩陣，R為上三角矩陣，且對角線元素則有：

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

為了滿足上述規約條件，通常需要構造變換矩陣進行規約操作。

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

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

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

2 LLL改進算法

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

2.1 延后尺度規約與部分尺度規約

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

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

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

1）延后尺度規約

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

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

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

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

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

2）部分尺度規約

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

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

部分尺度規約針對的是第二類尺度規約，為避免出現數值穩定性問題而選擇部分執行，在不影響基向量交換的基礎上進一步減少了LLL算法的尺度規約數。

2.2 最小列旋轉QR分解

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

通常基于Householder變換實現QR分解，假設對格基B的前i-1個向量進行 Householder變換后得到的矩陣為Ri-1。最小列旋轉QR分解是指在對格基B進行第i步 QR分解之前，找到對應當前子矩陣中列向量長度最小的那一列并構造初等變換矩陣Ui交換Ri-1的第i列和第j列；然后再構造Householder變換矩陣Hi進行常規的第i步 QR分解，實現矩陣的上三角化最小列旋轉QR分解的整體變換過程可以表示為：

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

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

2.3 算法流程

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

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

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

3 算例分析

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

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

3.1 實驗1

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

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

1）第一組模擬實驗

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

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

2）第二組模擬實驗

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

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

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

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

圖4 不同維數下的規約耗時Fig.4 Reduction time in different dimensions

3.2 實驗2

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

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

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

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

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

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

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

4 結 論

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

（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 算法實現單頻GPS 整周模糊度快速解算[J].中國慣性技術學報,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]劉經南, 于興旺, 張小紅.基于格論的GNSS模糊度解算[J].測繪學報, 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].鄭州: 信息工程大學, 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]盧立果, 劉萬科, 李江衛.一種有效的LLL規約算法[J].武漢大學學報(信息科學版), 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]盧立果，劉萬科，李江衛.降相關對模糊度解算中搜索效率的影響分析[J].測繪學報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]盧立果.基于球形搜索的模糊度格基規約方法研究與分析[D].武漢: 武漢大學, 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模糊度降相關算法[J].武漢大學學報(信息科學版), 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

國家自然科學基金（41674019）；國家重點研發計劃（2016YFB0501701）

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