一種快速解算高維模糊度的LLL分塊處理算法

劉萬科,盧立果,單弘煜

1. 武漢大學(xué)測繪學(xué)院，湖北 武漢 430079; 2. 地球空間信息技術(shù)協(xié)同創(chuàng)新中心，湖北 武漢 430079

?

一種快速解算高維模糊度的LLL分塊處理算法

劉萬科1,2,盧立果1,2,單弘煜1

1. 武漢大學(xué)測繪學(xué)院，湖北 武漢 430079; 2. 地球空間信息技術(shù)協(xié)同創(chuàng)新中心，湖北 武漢 430079

Foundation support： The National Natural Science Foundation of China (Nos. 41204030；41374034); The National Basic Surveying and Mapping Science and Technology Project (No. 201420); CLP 54 Universities Cooperation Project (No. KX132600031); Pre-research Fund Project (Nos. 9140A24020713JB11342; 51324040103)

摘要：由于多頻多模GNSS觀測數(shù)據(jù)解算的模糊度具有較高的維數(shù)和精度，當(dāng)采用常規(guī)的LLL算法進(jìn)行模糊度整數(shù)估計時，規(guī)約耗時顯著大于搜索耗時，成為限制高維模糊度解算計算效率的主要因素。針對這一問題，通過分析規(guī)約耗時與模糊度維數(shù)和精度之間的關(guān)系，提出了一種LLL分塊處理算法。該算法通過對模糊度方差協(xié)方差陣進(jìn)行分塊處理，降低單個規(guī)約矩陣的維數(shù)，以減少規(guī)約耗時，從而提高模糊度解算計算效率。通過兩組實測高維模糊度數(shù)據(jù)對本文提出的分塊處理算法進(jìn)行了效果驗證。結(jié)果顯示，當(dāng)分塊選擇合理時，本文提出的算法相對于LLL算法的解算效率分別可提高65.2%和60.2%。

關(guān)鍵詞：高維模糊度；格基規(guī)約；分塊LLL；解算效率

為快速、準(zhǔn)確求解載波相位觀測值中的整周模糊度，最常用的處理方法為模糊度域內(nèi)基于整數(shù)變換的整數(shù)最小二乘模糊度降相關(guān)平差(least-squares ambiguity decorrelation adjustment,LAMBDA)算法[1]，其核心思想是通過對模糊度方差協(xié)方差陣進(jìn)行降相關(guān)來減小搜索空間，以提高搜索效率。隨后，許多學(xué)者基于這個準(zhǔn)則提出了各自的降相關(guān)方法[2-7]。從格理論的角度來講，整數(shù)最小二乘模糊度解算可以看作是格上最近向量問題[8-10]，通常采用格基規(guī)約的方式獲得一組長度較短的基向量以快速尋找出一組最優(yōu)整數(shù)解，其中文獻(xiàn)[11—14]共同提出的LLL規(guī)約算法在模糊度解算中得到廣泛應(yīng)用。近來，通過對LLL與LAMBDA之間的關(guān)聯(lián)性分析可知格基規(guī)約與降相關(guān)是同一處理過程的不同表達(dá)[15-18]，而一般卻對降相關(guān)片面理解為“降低模糊度方差分量間的相關(guān)性”，文獻(xiàn)[19—20]分別采用理論和算法對比驗證的方法得出降相關(guān)的實質(zhì)在于通過降低方差分量的相關(guān)性實現(xiàn)條件方差(規(guī)約基)最大程度的交換，也即是規(guī)約性能(降相關(guān))的好壞體現(xiàn)在最終獲得的一組規(guī)約基的長度上。為表述方便，本文將所有基于整數(shù)變換的過程統(tǒng)稱為“格基規(guī)約”(簡稱規(guī)約)。

目前的規(guī)約算法，除文獻(xiàn)[19—21]分別采用部分元素尺度規(guī)約算法和貪心選擇算法在一定程度上降低了規(guī)約算法復(fù)雜度(與規(guī)約耗時成正相關(guān)關(guān)系)外，多是側(cè)重于提高規(guī)約性能以實現(xiàn)模糊度的快速搜索。由于規(guī)約性能的提高通常會增大計算復(fù)雜度，增加規(guī)約耗時，降低規(guī)約效率[8]，而模糊度解算過程是由規(guī)約和搜索兩個部分組成的，因此為獲得較小的整體解算耗時，需要實現(xiàn)規(guī)約復(fù)雜度和規(guī)約性能在解算效率上的均衡，如果單一地追求規(guī)約性能的提高，可能極大地消耗規(guī)約時間，不利于提高整體解算效率，反之亦然。

就多頻多模GNSS觀測數(shù)據(jù)處理來說，衛(wèi)星冗余觀測數(shù)據(jù)的增多，不僅增大了模糊度解算維數(shù)而且提高了模糊度的解算精度[22]。由于規(guī)約耗時不受模糊度解算精度的影響而只與解算維數(shù)成正相關(guān)關(guān)系，搜索耗時在很大程度上取決于解算精度[8]。因此，在高維整周模糊度解算中規(guī)約耗時通常遠(yuǎn)大于搜索耗時，此時規(guī)約耗時成為限制模糊度解算計算效率的主要因素。如前所述，規(guī)約耗時取決于模糊度解算的維數(shù)，如果對模糊度方差協(xié)方差陣進(jìn)行分塊處理降低單個規(guī)約矩陣維數(shù)，是否可以提高規(guī)約效率，實現(xiàn)快速規(guī)約進(jìn)而減少模糊度解算的整體耗時呢？文獻(xiàn)[23—24]首次提出了分塊思想并給出了分塊處理方法，但因為滿足基向量交換的限制條件較多導(dǎo)致規(guī)約過程相對復(fù)雜致使該方法較難應(yīng)用。近來，文獻(xiàn)[25]提出了分塊正交化算法，其基本思路是通過分塊策略對基向量進(jìn)行內(nèi)外規(guī)約變換改變基向量間的規(guī)約次序，且在每次內(nèi)外變換后再整體變換，因此該分塊正交算法主要用以提高基向量的規(guī)約性能，而不是降低規(guī)約復(fù)雜度提高規(guī)約效率。

針對高維模糊度的解算特點，本文將研究LLL分塊處理算法，即通過對LLL算法進(jìn)行分塊處理，降低單個規(guī)約矩陣的維數(shù)，并適當(dāng)弱化分塊基向量的交換條件，減少規(guī)約耗時，提高高維模糊度解算計算效率。因此，本文在闡述基本的理論方法基礎(chǔ)之上，將重點討論什么時候需要分塊，如何分塊處理，并對分塊處理算法和效果進(jìn)行研究分析。

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

1.1整數(shù)最小二乘原理

(1)

(2)

式中，B為上三角矩陣。

將式(2)代入式(1)，可得

(3)

式(3)在格理論上也被稱為最近向量問題，因此通常采用LLL等算法進(jìn)行規(guī)約處理[9-10]。

1.2基于QR分解的LLL算法

假定b1、b2、…、bn是上述矩陣B的一組基，采用施密特正交化(Gram-Schimidt orthogonaliza-

tion，GSO)

(4)

經(jīng)典的LLL算法滿足如下兩個規(guī)約條件[26]

(5)

式中，第1式稱為尺度規(guī)約；第2式為基向量交換。

為提高規(guī)約基向量解算的浮點精度，通常采用基于QR分解的LLL規(guī)約算法。令

B*=Q×D=[q1q2…qn]×

(6)

將式(6)代入式(4)，可得QR分解的表達(dá)式

B=Q×D×U=Q×R=

(7)

根據(jù)式(6)和式(7)，式(5)可以進(jìn)一步寫為

(8)

(9)

式(8)和式(9)即為基于QR分解的LLL算法的規(guī)約條件[27-28]，具體實現(xiàn)可以參照文獻(xiàn)[16]。當(dāng)對高維模糊度規(guī)約解算時，為滿足LLL算法的兩個規(guī)約條件通常需要多次相鄰基向量間的迭代交換和元素尺度規(guī)約過程，造成規(guī)約效率低下，因此為實現(xiàn)高維模糊度方差協(xié)方差陣的快速規(guī)約，本文提出了分塊規(guī)約的處理方法。

2分塊LLL算法

分塊LLL算法是通過將規(guī)約矩陣均勻分割成一定數(shù)目的子矩陣塊，利用LLL算法對每個子矩陣塊進(jìn)行規(guī)約，并通過相鄰分塊間的交換條件實現(xiàn)所有基向量交換的一種快速規(guī)約算法。以下對分塊LLL算法的解算原理和實現(xiàn)流程給予詳細(xì)介紹。

如圖1所示，將R陣分為m塊(B1,B2,…,Bm)，每塊大小為k，且滿足n=mk+r，其中r為不足分塊大小的部分。則任一分塊大小Bi,1≤i≤m可以表示為

(10)

由于每個分塊之間是相互獨立的，如果單純地對各個分塊進(jìn)行規(guī)約，不能實現(xiàn)各分塊間的基向量交換。為確保各分塊間的基向量能夠進(jìn)行交換，則需要對相鄰分塊進(jìn)行疊加，構(gòu)成公共交叉塊實現(xiàn)基向量長度的傳遞，即對分塊B1、B2、…、Bm進(jìn)行組合形成新的傳遞塊R1、R2、…、Rm-1，其中每個傳遞塊大小Ri(1≤i≤m-1)可以表示為

Ri=[Bi;Bi+1]

(11)

從式(11)可以看到Ri是一個方陣且相鄰傳遞塊(Ri,Ri+1)包含分塊Bi+1，因此當(dāng)分別對Ri和Ri+1內(nèi)部進(jìn)行LLL規(guī)約時，通過Bi+1實現(xiàn)了(Ri,Ri+1)基向量間長度的傳遞。但如果依次對傳遞塊進(jìn)行規(guī)約，僅能滿足分塊之間一次性的傳遞，基向量交換效果較差，因而仍需給出分塊之間的交換條件，下面對分塊之間滿足的交換條件進(jìn)行簡要推導(dǎo)。

圖1　LLL算法分塊示意圖Fig.1　The schematic of Block LLL algorithm

由于采用LLL算法每次進(jìn)行基向量交換前，需首先對次對角線元素進(jìn)行尺度規(guī)約。因此，當(dāng)對ri-1,i進(jìn)行規(guī)約后，即滿足

(12)

將式(12)代入式(9)，可得弱化的交換條件

(13)

由式(13)可得

(14)

因此

(15)

則相鄰傳遞塊(Ri,Ri+1)之間的一般交換條件為

B(i)≤δk2B(i+1)

(16)

基于以上分析，分塊LLL的處理流程可概括為：

(1) 給定分塊數(shù)m(考慮(Ri,Ri+1)間的交換，一般m≥3)，獲得分塊大小k及余數(shù)r，并設(shè)置i=1。

(2) 對傳遞塊Ri按照LLL算法進(jìn)行解算，獲得整數(shù)轉(zhuǎn)換矩陣Zi、正交陣Qi和B(i)，同時對Ri塊對應(yīng)的R中剩余列向量Ric和行向量Rir按照Ric=RicZi和Rir=QiRir進(jìn)行更新。其中

(3) 當(dāng)i≥2時，判斷B(i-1)≤δk2B(i)是否成立。如果不等式成立令i=i+1，直到i=m時退出規(guī)約過程；否則令i=i-1。

(4) 返回過程(2)。

以上即為分塊LLL算法(block LLL,BLLL)的解算原理及具體處理步驟。根據(jù)上述過程可以看出，BLLL算法分塊間的基向量交換強(qiáng)度要弱于相鄰基向量間的交換強(qiáng)度，同時對傳遞塊Ri進(jìn)行處理時有效地避免了對Ric中元素的尺度規(guī)約過程。

3試驗數(shù)據(jù)分析

為驗證前文提出的BLLL算法的有效性，并探討不同塊數(shù)對解算效率的影響，筆者采用LLL算法和文獻(xiàn)[25]提出的IBGS(針對高維數(shù)據(jù)選擇性能最優(yōu)的B-2策略)解算結(jié)果作為對比。分別采用規(guī)約耗時、搜索耗時和整體解算耗時評價3種方法的解算效率。其中，搜索算法采用當(dāng)前效率最高的SE-VB算法[21](是由Schnorr和Euchner兩位學(xué)者提出的SE算法與Viterbo和Boutros兩位學(xué)者提出的VB算法相結(jié)合的一種搜索算法)。整體解算耗時為規(guī)約耗時與搜索耗時二者之和。

本文所有的計算都是在筆者的PC機(jī)上基于Matlab 2012b軟件進(jìn)行的，其軟硬件配置為Intel Core i7-3520 CPU，2.90 GHz，4 GB內(nèi)存，win7系統(tǒng)(64位)。

3.1模糊度方差陣與規(guī)約和搜索耗時的關(guān)系

為說明采用分塊處理的合理性，本節(jié)首先分析模糊度方差陣與規(guī)約和搜索耗時之間的關(guān)系。其中，模糊度方差陣的特性主要體現(xiàn)在模糊度維數(shù)、精度以及解算成功率3個方面。

為衡量載波相位模糊度解算的精度，通常采用模糊度精度因子(ambiguity dilution of precision，ADOP)作為評價指標(biāo)[29]，其定義如下[30]

(17)

式中，n為模糊度的維數(shù)。

當(dāng)模糊度的方差協(xié)方差陣確定時，其整數(shù)最小二乘成功率(integer least square success rate,PS,ILS)是一個定值，而PS,ILS無法從理論上精確給出，通常采用序貫取整的成功率(bootstrapping success rate,PS,IB)作為其最優(yōu)下邊界[31-33]，其定義如下[34]

(18)

由PS,IB計算公式可知其數(shù)值取決于條件方差(規(guī)約基)的大小。當(dāng)采用的算法規(guī)約性能較優(yōu)時，可以獲得一組相對較短的規(guī)約基，此時解算的PS,IB數(shù)值較大從而更接近PS,ILS。因此，為較精確地衡量PS,ILS，通常采用規(guī)約性能較強(qiáng)的算法(比如LAMBDA或者LLL算法)計算PS,IB。由于PS,IB可以反映基向量的規(guī)約程度，因而PS,IB又被用作評價不同規(guī)約算法規(guī)約性能的指標(biāo)[15,20]。

圖2給出了不同維數(shù)下采用LLL算法解算的規(guī)約耗時、搜索耗時和PS,IB與模糊度精度的關(guān)系。其中，PS,IB用來近似替代最小二乘的成功率。從圖中可以看出：PS,IB值隨著ADOP的增大而減小，說明模糊度解算的精度越高此時模糊度固定成功的概率越大；規(guī)約耗時隨著維數(shù)的增大而增大(比如，維數(shù)等于30時規(guī)約時間約為0.02 s，而當(dāng)維數(shù)增大為60時規(guī)約時間相應(yīng)地增大為0.11 s左右)但并不受精度的影響；搜索耗時的大小取決于模糊度解算的維數(shù)和精度，其大小隨著維數(shù)的增大或精度的降低而增大。同時，對比規(guī)約耗時和搜索耗時與精度之間的相互關(guān)系可以發(fā)現(xiàn)：當(dāng)精度較高(尤其是ADOP小于0.2)時，搜索耗時明顯小于規(guī)約耗時，反之亦然。

由于多頻多系統(tǒng)下衛(wèi)星冗余觀測數(shù)據(jù)的增多，不僅可以提高模糊度解算的精度而且增大了模糊度解算維數(shù)。根據(jù)圖2結(jié)果可知，此時采用LLL算法的規(guī)約耗時較大且遠(yuǎn)大于搜索耗時。因此，規(guī)約耗時成為制約高維模糊度快速解算的主要因素，則有必要通過降低規(guī)約復(fù)雜度，減少規(guī)約耗時。本文在前面所提出的分塊處理算法即是通過適當(dāng)?shù)亟档鸵?guī)約耗時在總解算時間中的比重，提高模糊度解算整個過程的計算效率。因此，下文采取兩組高維實測數(shù)據(jù)對其效果進(jìn)行分析驗證，其中為減少計算環(huán)境變化對解算時間造成的影響，每組試驗中分別對每種處理算法重復(fù)進(jìn)行3次試驗，并以重復(fù)試驗結(jié)果的平均值作為評估依據(jù)。

3.2試驗1

表1　試驗1的基本情況

圖3是模糊度維數(shù)和ADOP隨歷元的變化趨勢圖。從圖中可以看到，模糊度維數(shù)變化范圍為41~51，ADOP數(shù)值維持在0.012以下。依據(jù)圖2的結(jié)果分析可知，此時模糊度的解算精度較高且維數(shù)較大，模糊度的規(guī)約耗時明顯大于搜索耗時，有必要采用分塊處理策略。從ADOP和維數(shù)的變化趨勢上可以看出兩者并沒有呈現(xiàn)非常明確的相關(guān)性，主要是由于ADOP值取決于3個衛(wèi)星系統(tǒng)的模糊度維數(shù)、站星幾何關(guān)系和載波相位觀測值精度等原因，導(dǎo)致ADOP并不嚴(yán)格和維數(shù)是一一對應(yīng)關(guān)系。

表2統(tǒng)計了分別采用LLL、IBGS和不同分塊數(shù)的BLLL算法進(jìn)行處理時規(guī)約耗時、搜索耗時和整體解算耗時的歷元平均值和最大值，其中m=3~14代表BLLL的分塊數(shù)分別為3~14。從表中可以看到LLL和IBGS解算耗時差異較??；BLLL規(guī)約耗時隨著分塊數(shù)的增大而逐次降低，搜索耗時除在分塊數(shù)為14(個別歷元出現(xiàn)了躍變)外，增長趨勢緩慢，因此整體解算耗時也基本呈現(xiàn)隨分塊數(shù)增大而遞減的趨勢，尤其是在分塊數(shù)達(dá)到13時，采用BLLL的模糊度解算計算效率相對于LLL算法提高了約65.2%。

表2　不同算法的解算耗時

圖2　不同維數(shù)和精度下的Bootstrapping成功率、規(guī)約耗時和搜索耗時的變化趨勢圖Fig.2　The trend chart of Bootstrapping success rate, reduction time and search time under different dimensions and ADOP

由表2結(jié)果可知，分塊數(shù)并非越多越好，因此下文分別對塊數(shù)為13和14兩種情形下的解算結(jié)果進(jìn)行分析。

圖4給出了LLL、IBGS和BLLL(m=13)不同歷元下的解算結(jié)果。圖4(a)是3種方法的解算時間變化圖；圖4(b)是三者的PS,IB的變化圖。

從LLL和IBGS解算結(jié)果對比可知，兩者解算耗時差異較小，但是IBGS的PS,IB小于LLL算法，說明IBGS的規(guī)約性能要弱于LLL算法，與文獻(xiàn)[25]結(jié)論不符，其主要原因在于該文獻(xiàn)中比較的“LLL算法”更側(cè)重于降低基向量間的相關(guān)性， 有別于本文的LLL算法。從BLLL與LLL的結(jié)果對比可以看到，BLLL由于采用式(11)和式(16)進(jìn)行分塊處理時減少了分塊矩陣外的元素尺度規(guī)約個數(shù)和分塊矩陣間的基向量交換強(qiáng)度，因此較為顯著地減小了規(guī)約耗時和PS,IB數(shù)值，故而規(guī)約復(fù)雜度和規(guī)約性能較低，導(dǎo)致規(guī)約耗時和PS,IB均減小。需要說明的是此處PS,IB僅用來反映規(guī)約性能的好壞，并不改變實際解算的整數(shù)最小二乘成功率PS,ILS的數(shù)值大小。從兩者搜索耗時的差異較小來看，當(dāng)在滿足一定規(guī)約強(qiáng)度時已經(jīng)可以獲得較小的模糊度搜索空間，此時提高規(guī)約性能對搜索空間的改善效果不太明顯。因此，在進(jìn)行模糊度解算時適當(dāng)?shù)胤謮K以降低PS,IB，可以獲得相對較優(yōu)的解算效果。

圖3　不同歷元下的模糊度維數(shù)與ADOP值Fig.3　Ambiguity dimensions and the value of ADOP under different epoches

圖4　m=13時不同規(guī)約方法的模糊度解算耗時和PS,IBFig.4　Ambiguity resolution time and PS,IBin different methods under m=13

圖5給出了LLL、IBGS和BLLL(m=14)不同歷元下的解算結(jié)果。其中，圖5(a)是3種方法的解算時間變化圖；圖5(b)是三者的PS,IB的變化圖。對比圖5和圖4可以看出，盡管分塊數(shù)的增加可以獲得更小的規(guī)約耗時，但是在歷元1641處的搜索耗時相對于LLL和IBGS出現(xiàn)了躍變，此時BLLL的PS,IB大小為0.46且低于LLL和IBGS，說明當(dāng)采用算法的規(guī)約性能較差且獲得的PS,IB相對較小時有可能導(dǎo)致部分歷元處解算的搜索耗時出現(xiàn)不穩(wěn)定的現(xiàn)象。同時，可以發(fā)現(xiàn)BLLL算法在其他歷元處的PS,IB普遍較小且存在部分歷元處的PS,IB要小于躍變點處的PS,IB，但是搜索耗時均較穩(wěn)定。筆者分析其原因主要是由不同歷元處的模糊度信息(包括維數(shù)和精度等因素)不一致導(dǎo)致的。因為當(dāng)對不同歷元處的模糊度進(jìn)行搜索時，除考慮模糊度的規(guī)約性能，還需顧及每個歷元處的模糊度信息，此時即使各個歷元間的PS,IB差異不大，也會因模糊度信息的差異而導(dǎo)致搜索耗時的不同。在模糊度實際解算中，會發(fā)現(xiàn)有些模糊度可能對規(guī)約強(qiáng)度要求較低，即使PS,IB很小也能快速搜索出整數(shù)模糊度；反之，則對模糊度的規(guī)約性能要求較高。因此，躍變點處的模糊度對規(guī)約性能可能要求較高，此時對BLLL進(jìn)行較多的分塊導(dǎo)致性能較差，超出了對規(guī)約性能的允許程度，導(dǎo)致耗時較大。

因此，如何選擇合適的分塊數(shù)以滿足一定的規(guī)約性能并保證搜索耗時的穩(wěn)定也是分塊時要考慮的問題。

3.3試驗2

表3　試驗2的基本情況

圖6是模糊度維數(shù)和ADOP隨歷元的變化趨勢圖。從圖中可以看到模糊度維數(shù)在30~70維之間變化；ADOP值小于0.014。

表4統(tǒng)計了分別采用LLL、IBGS和不同分塊數(shù)的BLLL算法進(jìn)行處理時的規(guī)約耗時、搜索耗時和整體解算耗時的歷元平均值和最大值，其中m=3~10代表BLLL的分塊數(shù)分別為3~10。從表中可以看到IBGS相對于LLL算法的解算效率略有提高；BLLL隨著分塊數(shù)的增大平均規(guī)約耗時逐次降低，搜索耗時除在分塊數(shù)為10(個別歷元出現(xiàn)了躍變)外，增長趨勢緩慢，因此整體解算耗時也基本呈現(xiàn)逐次遞減趨勢；當(dāng)分塊數(shù)為9時，采用BLLL的模糊度解算計算效率相對于LLL算法提高了約60.2%。

同理，為分析BLLL算法在分塊等于10時，搜索耗時不穩(wěn)定的原因，圖7給出了LLL、IBGS和BLLL(m=10)不同歷元下的解算結(jié)果。圖7(a)是3種方法的解算時間變化圖；右圖是三者的PS,IB的變化圖。從圖中黑色虛線部分可以看出在歷元234處BLLL的搜索耗時為1.789 3 s時，對應(yīng)的PS,IB等于0.73。對于圖中的結(jié)果與分析可以參考圖5。

4結(jié)論

本文針對多頻多模情況下GNSS模糊度維數(shù)和精度較高、規(guī)約耗時明顯大于搜索耗時的特點，提出了LLL分塊處理算法(BLLL)，可減少矩陣尺度規(guī)約的個數(shù)和弱化分塊矩陣間基向量交換的強(qiáng)度，降低規(guī)約計算復(fù)雜度，以達(dá)到減小規(guī)約耗時的目的。通過兩組實測高維數(shù)據(jù)，對BLLL算法進(jìn)行了效果驗證與分析，并與LLL和IBGS算法的計算結(jié)果進(jìn)行了對比，可以得出以下幾點結(jié)論：

(1) 當(dāng)模糊度的維數(shù)較高且精度因子ADOP較小時，基于經(jīng)典的LLL算法進(jìn)行模糊度解算的規(guī)約耗時明顯大于搜索耗時，此時可以采用分塊處理的方法減少規(guī)約耗時，以提高模糊度解算整個過程的計算效率。

(2) 分塊數(shù)與規(guī)約耗時呈現(xiàn)負(fù)相關(guān)關(guān)系，即在一定的塊數(shù)范圍內(nèi)，當(dāng)分塊數(shù)越多，規(guī)約強(qiáng)度越低(PS,IB越小)，規(guī)約耗時越小。因此，當(dāng)分塊選擇合理時，此時搜索耗時相對穩(wěn)定，可以獲得較高的模糊度解算計算效率。

(3) 對于本文的兩組實測高維數(shù)據(jù)而言，IBGS相對于LLL算法的解算效率略有提高，而本文提出的BLLL算法在分塊數(shù)分別為13和9時相對于LLL算法的解算效率可以提高65.2%和60.2%。

圖5　m=14時不同規(guī)約方法的模糊度解算耗時和PS,IBFig.5　Ambiguity resolution time and PS,IBin different methods under m=14

圖6　不同歷元下的模糊度維數(shù)與ADOP值Fig.6　Ambiguity dimensions and the value of ADOP under different epoches

圖7　m=10時不同規(guī)約方法的模糊度解算耗時和PS,IBFig.7　Ambiguity resolution time and PS,IBin different methods under m=10

此外，從本文的計算分析也可以看到，分塊數(shù)的增加會造成規(guī)約性能變差(PS,IB減小)，有可能導(dǎo)致極個別歷元搜索耗時增大，出現(xiàn)解算不穩(wěn)定現(xiàn)象，因此后續(xù)有必要進(jìn)一步分析ADOP和PS,IB的取值與搜索效率的關(guān)系進(jìn)而來選擇合適的分塊數(shù)。初步思路為：首先根據(jù)模糊度維數(shù)和ADOP值確定分塊數(shù)大小，當(dāng)完成規(guī)約后采用合適的PS,IB閾值判斷分塊是否合理，以保障模糊度解算計算效率的穩(wěn)定性。

表4　不同算法的解算耗時

參考文獻(xiàn)：

[1]TEUNISSEN P J G. The Least-squares Ambiguity Decorrelation Adjustment: A Method for Fast GPS Integer Ambiguity Estimation[J]. Journal of Geodesy, 1995, 70(1-2): 65-82.

[2]LIU L T, HSU H T, ZHU Y Z, et al. A New Approach to GPS Ambiguity Decorrelation[J]. Journal of Geodesy, 1999, 73(9): 478-490.

[3]XU Peiliang. Random Simulation and GPS Decorrelation[J]. Journal of Geodesy, 2001, 75(7-8): 408-423.

[4]XU Peiliang. Parallel Cholesky-based Reduction for the Weighted Integer Least Squares Problem[J]. Journal of Geodesy, 2012, 86(1): 35-52.

[5]ZHOU Yangmei. A New Practical Approach to GNSS High-dimensional Ambiguity Decorrelation[J]. GPS Solutions, 2011, 15(4): 325-331.

[6]周揚眉, 劉經(jīng)南, 劉基余. 回代解算的LAMBDA方法及其搜索空間[J]. 測繪學(xué)報, 2005, 34(4): 300-304.

ZHOU Yangmei, LIU Jingnan, LIU Jiyu. Return-calculating LAMBDA Approach and Its Search Space[J]. Acta Geodaetica et Cartographica Sinica, 2005, 34(4): 300-304.

[7]劉寧, 熊永良, 馮威, 等. 單頻GPS動態(tài)定位中整周模糊度的一種快速解算方法[J]. 測繪學(xué)報, 2013, 42(2): 211-217.

LIU Ning, XIONG Yongliang, FENG Wei, et al. An Algorithm for Rapid Integer Ambiguity Resolution in Single Frequency GPS Kinematical Positioning[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(2): 211-217.

[8]盧立果, 劉萬科, 于興旺. 基于交叉排序算法解算模糊度的新規(guī)約方法[C]∥第五屆中國衛(wèi)星導(dǎo)航學(xué)術(shù)年會電子文集. 南京: [s.n.], 2014.

LU Liguo, LIU Wanke, YU Xingwang. A New Reduction Method for Ambiguity Resolution Based on Cross Sorting Algorithm[C]∥The Fifth China Satellite Navigation Conference (CSNC). Nanjing: [s.n.], 2014.

[9]于興旺. 多頻GNSS精密定位理論與方法研究[D]. 武漢: 武漢大學(xué), 2011.

YU Xingwang. Multi-frequency GNSS Precise Positioning Theory and Method Research[D]. Wuhan: Wuhan University, 2011.

[10]JAZAERI S, AMIRI-SIMKOOEI A R, SHARIFI M A. Fast Integer Least-squares Estimation for GNSS High Dimensional Ambiguity Resolution Using the Lattice Theory[J]. Journal of Geodesy, 2012, 86(2): 123-136.

[11]HASSIBI A, BOYD S. Integer Parameter Estimation in Linear Models with Applications to GPS[J]. IEEE Transactions on Signal Processing, 1998, 46(11): 2938-2952.

[12]劉志平, 何秀鳳. 改進(jìn)的GPS模糊度降相關(guān)LLL算法[J]. 測繪學(xué)報, 2007, 36(3): 286-289.

LIU Zhiping, HE Xiufeng. An Improved LLL Algorithm for GPS Ambiguity Solution[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3): 286-289.

[13]楊榮華, 花向紅, 李昭, 等. GPS模糊度降相關(guān)LLL算法的一種改進(jìn)[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2010, 35(1): 21-24.

YANG Ronghua, HUA Xianghong, LI Zhao, et al. An Improved LLL Algorithm for GPS Ambiguity Solution[J]. Geomatics and Information Science of Wuhan University, 2010, 35(1): 21-24.

[14]謝愷, 柴洪洲, 范龍, 等. 一種改進(jìn)的LLL模糊度降相關(guān)算法[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2014, 39(11): 1363-1368.

XIE Kai, CHAI Hongzhou, FAN Long, et al. An Improved LLL Ambiguity Decorrelation Algorithm[J]. Geomatics and Information Science of Wuhan University, 2014, 39(11): 1363-1368.

[15]劉經(jīng)南, 于興旺, 張小紅. 基于格論的GNSS模糊度解算[J]. 測繪學(xué)報, 2012, 41(5): 636-645.

LIU Jingnan, YU Xingwang, ZHANG Xiaohong. GNSS Ambiguity Resolution Using Lattice Theory[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(5): 636-645.

[16]盧立果. 基于球形搜索的模糊度格基規(guī)約方法研究與分析[D]. 武漢: 武漢大學(xué), 2013.

LU Liguo. The Research and Analysis Based on Sphere Search for Ambiguity on Reduction[D]. Wuhan: Wuhan University, 2013.

[17]LANNES A. On the Theoretical Link between LLL-reduction and LAMBDA-decorrelation[J]. Journal of Geodesy, 2013, 87(4): 323-335.

[18]LEICA A, RAPOPORT L, TATARNIKOV D. GPS Satellite Surveying[M]. 4th ed. New York: Wiley, 2015: 324-356.

[19]BORNO M A, CHANG X W, XIE X H. On “Decorrelation” in Solving Integer Least-squares Problems for Ambiguity Determination[J]. Survey Review, 2014, 46(334): 37-49.

[20]盧立果, 劉萬科, 李江衛(wèi). 降相關(guān)對模糊度解算中搜索效率的影響分析[J]. 測繪學(xué)報, 2015, 44(5): 481-487. DOI: 10.11947/j.AGCS.2015.20140311.

LU Liguo, LIU Wanke, LI Jiangwei. Impact of Decorrelation on Search Efficiency of Ambiguity Resolution[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(5): 481-487. DOI: 10.11947/j.AGCS.2015.20140311.

[21]CHANG X W, YANG X, ZHOU T. MLAMBDA: A Modified LAMBDA Method for Integer Least-squares Estimation[J]. Journal of Geodesy, 2005, 79(9): 552-565.

[22]TEUNISSEN P J G, ODOLINSKI R, ODIJK D. Instantaneous BeiDou+GPS RTK Positioning with High Cut-off Elevation Angles[J]. Journal of Geodesy, 2014, 88(4): 335-350.

[23]KOY H, SCHNORR C P. Segment LLL-reduction of Lattice Bases[M]∥SILVERMAN J H. Cryptography and Lattices, Lecture Notes in Computer Sciences. Berlin: Springer, 2001, 2146: 67-80.

[24]KOY H, SCHNORR C P. Segment LLL-reduction with Floating Point Orthogonalization[M]∥SILVERMAN J H. Cryptography and Lattices, Lecture Notes in Computer Sciences. Berlin: Springer, 2001, 2146: 81-96.

[25]范龍, 翟國君, 柴洪洲. 模糊度降相關(guān)的整數(shù)分塊正交化算法[J]. 測繪學(xué)報, 2014, 43(8): 818-826. DOI: 10.13485/j.cnki.11-2089.2014.0094.

FAN Long, ZHAI Guojun, CHAI Hongzhou. Ambiguity Decorrelation Algorithm with Integer Block Orthogonalization Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(8): 818-826. DOI: 10.13485/j.cnki.11-2089.2014.0094.

[26]LENSTRA A K, LENSTRA H W, LOVASZ L. Factoring Polynomials with Rational Coefficients[J]. Mathematische Annalen, 1982, 261(4): 515-534.

[27]LUK F T, TRACY D M. An Improved LLL Algorithm[J]. Linear Algebra and Its Applications, 2007, 428(2-3): 441-452.

[28]NGUYEN P Q, VALLEE B. The LLL Algorithm: Survey and Applications (Information Security and Cryptography) [M]. Paris: Springer, 2010: 145-178.

[29]ODIJK D, TEUNISSEN P J G. ADOP in Closed form for a Hierarchy of Multi-frequency Single-Baseline GNSS Models[J]. Journal of Geodesy, 2008, 82(8): 473-492.

[30]TEUNISSEN P J G, ODIJK D. Ambiguity Dilution of Precision: Definition, Properties and Application[C]∥Proceedings of ION GPS-97. Kansas City: [s.n.], 1997: 891-899.

[31]VERHAGEN S. On the Approximation of the Integer Least-squares Success Rate: Which Lower or Upper Bound to Use?[J]. Journal of Global Positioning Systems, 2003, 2(2): 117-124.

[32]FENG Yanming, WANG Jun. Computed Success Rates of Various Carrier Phase Integer Estimation Solutions and Their Comparison with Statistical Success Rates[J]. Journal of Geodesy, 2011, 85(2): 93-103.

[33]VERHAGEN S, LI Bofeng, TEUNISSEN P J G. Ps-LAMBDA: Ambiguity Success Rate Evaluation Software for Interferometric Applications[J]. Computers & Geosciences, 2013, 54: 361-376.

[34]TEUNISSEN P J G. Success Probability of Integer GPS Ambiguity Rounding and Bootstrapping[J]. Journal of Geodesy, 1998, 72(10): 606-612.

(責(zé)任編輯：叢樹平)

A New Block Processing Algorithm of LLL for Fast High-dimension Ambiguity Resolution

LIU Wanke1, 2,LU Liguo1,SHAN Hongyu1

1. School of Geodesy and Geomatics, Wuhan University, Wuhan 430079, China; 2. Collaborative Innovation Center of Geospatial Technology, Wuhan 430079, China

Abstract：Due to high dimension and precision for the ambiguity vector under GNSS observations of multi-frequency and multi-system, a major problem to limit computational efficiency of ambiguity resolution is the longer reduction time when using conventional LLL algorithm. To address this problem, it is proposed a new block processing algorithm of LLL by analyzing the relationship between the reduction time and the dimensions and precision of ambiguity. The new algorithm reduces the reduction time to improve computational efficiency of ambiguity resolution, which is based on block processing ambiguity variance-covariance matrix that decreased the dimensions of single reduction matrix. It is validated that the new algorithm with two groups of measured data. The results show that the computing efficiency of the new algorithm increased by 65.2% and 60.2% respectively compared with that of LLL algorithm when choosing a reasonable number of blocks.

Key words：high-dimension ambiguity; lattice basis reduction; block LLL; resolution efficiency

基金項目：國家自然科學(xué)基金(41204030;41374034)；國家基礎(chǔ)測繪科技項目(201420)；中電集團(tuán)54所高校合作項目(KX132600031)；預(yù)研基金項目(9140A24020713JB11342；51324040103)

中圖分類號：P228

文獻(xiàn)標(biāo)識碼：A

文章編號：1001-1595(2016)02-0147-10

引文格式：劉萬科, 盧立果, 單弘煜.一種快速解算高維模糊度的LLL分塊處理算法[J].測繪學(xué)報，2016,45(2)：147-156.DOI:10.11947/j.AGCS.2016.20150370.

LIU Wanke, LU Liguo, SHAN Hongyu.A New Block Processing Algorithm of LLL for Fast High-dimension Ambiguity Resolution[J]. Acta Geodaetica et Cartographica Sinica,2016,45(2):147-156.DOI:10.11947/j.AGCS.2016.20150370.