劉萬(wàn)科,盧立果,單弘煜

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

?

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

劉萬(wàn)科1,2,盧立果1,2,單弘煜1

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

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

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

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

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

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

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

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

(1)

(2)

式中，B為上三角矩陣。

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

(3)

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

1.2基于QR分解的LLL算法

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

tion，GSO)

(4)

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

(5)

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

為提高規(guī)約基向量解算的浮點(diǎn)精度，通常采用基于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]，具體實(shí)現(xiàn)可以參照文獻(xiàn)[16]。當(dāng)對(duì)高維模糊度規(guī)約解算時(shí)，為滿足LLL算法的兩個(gè)規(guī)約條件通常需要多次相鄰基向量間的迭代交換和元素尺度規(guī)約過(guò)程，造成規(guī)約效率低下，因此為實(shí)現(xiàn)高維模糊度方差協(xié)方差陣的快速規(guī)約，本文提出了分塊規(guī)約的處理方法。

2分塊LLL算法

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

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

(10)

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

Ri=[Bi;Bi+1]

(11)

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

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

由于采用LLL算法每次進(jìn)行基向量交換前，需首先對(duì)次對(duì)角線元素進(jìn)行尺度規(guī)約。因此，當(dāng)對(duì)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) 對(duì)傳遞塊Ri按照LLL算法進(jìn)行解算，獲得整數(shù)轉(zhuǎn)換矩陣Zi、正交陣Qi和B(i)，同時(shí)對(duì)Ri塊對(duì)應(yīng)的R中剩余列向量Ric和行向量Rir按照Ric=RicZi和Rir=QiRir進(jìn)行更新。其中

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

(4) 返回過(guò)程(2)。

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

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

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

本文所有的計(jì)算都是在筆者的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ī)約和搜索耗時(shí)的關(guān)系

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

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

(17)

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

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

(18)

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

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

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

3.2試驗(yàn)1

表1　試驗(yàn)1的基本情況

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

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

表2　不同算法的解算耗時(shí)

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

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

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

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

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

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

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

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

3.3試驗(yàn)2

表3　試驗(yàn)2的基本情況

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

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

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

4結(jié)論

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

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

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

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

圖5　m=14時(shí)不同規(guī)約方法的模糊度解算耗時(shí)和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時(shí)不同規(guī)約方法的模糊度解算耗時(shí)和PS,IBFig.7　Ambiguity resolution time and PS,IBin different methods under m=10

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

表4　不同算法的解算耗時(shí)

參考文獻(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]周揚(yáng)眉, 劉經(jīng)南, 劉基余. 回代解算的LAMBDA方法及其搜索空間[J]. 測(cè)繪學(xué)報(bào), 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動(dòng)態(tài)定位中整周模糊度的一種快速解算方法[J]. 測(cè)繪學(xué)報(bào), 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]盧立果, 劉萬(wàn)科, 于興旺. 基于交叉排序算法解算模糊度的新規(guī)約方法[C]∥第五屆中國(guó)衛(wèi)星導(dǎo)航學(xué)術(shù)年會(huì)電子文集. 南京: [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]. 測(cè)繪學(xué)報(bào), 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é)報(bào)(信息科學(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é)報(bào)(信息科學(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]. 測(cè)繪學(xué)報(bào), 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àn)科, 李江衛(wèi). 降相關(guān)對(duì)模糊度解算中搜索效率的影響分析[J]. 測(cè)繪學(xué)報(bào), 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ó)君, 柴洪洲. 模糊度降相關(guān)的整數(shù)分塊正交化算法[J]. 測(cè)繪學(xué)報(bào), 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

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

中圖分類號(hào)：P228

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

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

引文格式：劉萬(wàn)科, 盧立果, 單弘煜.一種快速解算高維模糊度的LLL分塊處理算法[J].測(cè)繪學(xué)報(bào)，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.