一種矩陣分塊的GNSS相位模糊度快速解算方法

李克昭 朱國(guó)庫(kù)

1 河南理工大學(xué)測(cè)繪與國(guó)土信息工程學(xué)院，河南省焦作市世紀(jì)路2001號(hào)，454003 2 北斗導(dǎo)航應(yīng)用技術(shù)協(xié)同創(chuàng)新中心，鄭州市科學(xué)大道62號(hào)，450001

在目前諸多GNSS定位模糊度求解方法中，以降相關(guān)思想為核心的LAMBDA算法應(yīng)用最為廣泛[1-2]。LAMBDA算法解算模糊度的步驟主要包括：模糊度降相關(guān)、模糊度搜索和模糊度檢驗(yàn)。其中，模糊度降相關(guān)過(guò)程涉及大量矩陣運(yùn)算，耗時(shí)較長(zhǎng)。為此，學(xué)者們進(jìn)行了大量研究：Chang等[3]和Borno等[4]分別利用貪心算法和部分元素降相關(guān)方法對(duì)LAMBDA算法進(jìn)行改進(jìn)；Liu等[5]通過(guò)上下三角過(guò)程構(gòu)造聯(lián)合去相關(guān)算法，降低模糊度之間的相關(guān)性；徐琦等[6]通過(guò)對(duì)比分析認(rèn)為，聯(lián)合去相關(guān)法的處理成功率高于迭代法；Xu[7]使用Cholesky分解構(gòu)建整數(shù)高斯矩陣，結(jié)果表明，在高維情況下分解得到的浮點(diǎn)解協(xié)方差矩陣條件數(shù)最?。魂悩?shù)新[8]以降低協(xié)方差矩陣的條件數(shù)為準(zhǔn)則，提出一種性能更加優(yōu)越的模糊度去相關(guān)算法；Liu等[9]通過(guò)三次差分測(cè)量得到模糊度浮動(dòng)解，通過(guò)降低模糊度協(xié)方差矩陣的維數(shù)對(duì)搜索空間進(jìn)行去相關(guān)處理，克服了Z變換可能帶來(lái)的矩陣病態(tài)分解，減少了20%的解算時(shí)間。還有學(xué)者研究不同的排序算法對(duì)降相關(guān)性能的影響[10-14]。 Hassibi等[15]將格理論中的規(guī)約算法Lenstra-Lenstra-Lovász(LLL)應(yīng)用于模糊度降相關(guān)的研究中，此后大量學(xué)者對(duì)LLL算法進(jìn)行了詳細(xì)研究與分析，并開(kāi)展相應(yīng)的改進(jìn)和優(yōu)化[16-22]。

綜上可知，減少矩陣的復(fù)雜運(yùn)算是提高降相關(guān)效率的重要手段之一。LAMBDA算法的模糊度降相關(guān)過(guò)程主要包括Cholesky分解和矩陣降相關(guān)2個(gè)步驟。其中，傳統(tǒng)Cholesky分解過(guò)程復(fù)雜，會(huì)造成大量計(jì)算冗余；矩陣降相關(guān)過(guò)程主要為條件方差排序計(jì)算，每次排序計(jì)算都需要對(duì)非主對(duì)角元素進(jìn)行降相關(guān)處理，涉及大量復(fù)雜運(yùn)算?；诖?，本文提出一種分塊最小二乘模糊度降相關(guān)(BLAMBDA)算法：采用條件方差分塊算法優(yōu)化降相關(guān)過(guò)程，對(duì)條件方差矩陣進(jìn)行分塊，減少條件方差排序次數(shù)，并在此基礎(chǔ)上對(duì)Cholesky分解公式進(jìn)行整合，減少Cholesky分解過(guò)程中的數(shù)乘運(yùn)算。

1 整數(shù)最小二乘去相關(guān)算法模型

(1)

式中，a為模糊度整數(shù)候選向量。

(2)

(3)

(4)

(5)

(6)

2 BLAMBDA算法求解整周模糊度

為滿足式(4)，LAMBDA算法在條件方差交換時(shí)需按照從后往前的順序排列。當(dāng)遇到判別交換的條件方差dk和dk+1相差過(guò)大時(shí)，dk+1、dk+2及之前的交換過(guò)程可能不再滿足條件，需要對(duì)其進(jìn)行再次交換，此過(guò)程會(huì)發(fā)生大量重復(fù)交換的情況，并增加元素降相關(guān)的運(yùn)算時(shí)間?；诖?，本文對(duì)條件方差矩陣進(jìn)行分塊處理，使條件方差在塊內(nèi)交換，通過(guò)改變交換維數(shù)和方式來(lái)減少條件方差的交換次數(shù)，并對(duì)Cholesky分解過(guò)程進(jìn)行優(yōu)化處理，提出改進(jìn)的LAMBDA算法。

首先，對(duì)式(5)LTDL分解中的D矩陣進(jìn)行分塊處理：

(7)

將n維矩陣D分成m塊(R1,R2,…,Rm)，前(m-1)塊的大小為k,Rm的大小為r=n-(m-1)k,r為不足分塊大小的部分。任意分塊Ri(1≤i≤m)和Rm可表示為：

(8)

(9)

BLAMBDA算法若不滿足式(6)，則僅在各分塊內(nèi)進(jìn)行交換。由于各分塊的維數(shù)較低，因此在分塊內(nèi)更容易滿足式(4)，使得各分塊條件方差交換次數(shù)之和遠(yuǎn)小于LAMBDA算法降相關(guān)過(guò)程中條件方差的交換次數(shù)，減少了大量矩陣運(yùn)算和高斯變換過(guò)程。以di和di+1進(jìn)行一次條件方差交換為例，減少的計(jì)算過(guò)程公式推導(dǎo)如下：

(10)

令

(11)

則有：

(12)

在各分塊內(nèi)完成交換后，需要對(duì)相鄰塊進(jìn)行條件方差交換，完成條件方差的塊傳遞。相鄰塊條件方差交換條件為：

δ(d(i-1)k+1×d(i-1)k+2×…×dik)>

dik+1×dik+2×…×d(i+1)k

(13)

式中，δ為條件約束因子，其大小決定了相鄰塊是否需要使用相鄰塊傳遞的對(duì)稱旋轉(zhuǎn)策略[3]。

當(dāng)相鄰塊不滿足式(13)時(shí)，需要對(duì)Ri的第1個(gè)元素d(i-1)k+1和Ri+1的最后1個(gè)元素d(i+1)k進(jìn)行交換。當(dāng)Ri中的條件方差遠(yuǎn)小于Ri+1時(shí)，需使用一次對(duì)稱旋轉(zhuǎn)策略，此過(guò)程會(huì)使2分塊內(nèi)的條件方差大致按降序排列；否則僅對(duì)Ri和Ri+1的相鄰元素dik和dik+1作比較交換處理，實(shí)現(xiàn)相鄰塊的交換傳遞。交換公式為：

(14)

(15)

雖然在塊之間的傳遞過(guò)程中使用對(duì)稱旋轉(zhuǎn)策略會(huì)增加部分計(jì)算量，但該計(jì)算量遠(yuǎn)小于條件方差交換過(guò)程中減少的計(jì)算量。

為進(jìn)一步減少BLAMBDA算法的矩陣運(yùn)算耗時(shí)，對(duì)LAMBDA算法的分解算法進(jìn)行優(yōu)化，即(ModifyLTDL,MLTDL)。優(yōu)化策略如下：

(16)

式中，

qn=dn，qT=lTdn，l=q/dn

(17)

Q=Q-lTdnl=LTDL

(18)

將式(17)代入式(18)中，得：

Q=Q-qTl=LTDL

(19)

從式(16)～(19)可以看出，該迭代過(guò)程中沒(méi)有開(kāi)平方根運(yùn)算，且式(19)在式(18)的基礎(chǔ)上減少了數(shù)乘運(yùn)算。

3 實(shí)驗(yàn)驗(yàn)證與分析

本文利用MATLAB 2014構(gòu)建算法的仿真實(shí)驗(yàn)平臺(tái)，基于Visual Studio 2019 C語(yǔ)言進(jìn)行實(shí)驗(yàn)的整體解算。計(jì)算機(jī)系統(tǒng)為Windows 10，處理器為8 GB內(nèi)存的Intel(R) Core(TM) i7-8550U CPU@1.80 GHz 1.99 GHz。在實(shí)際解算過(guò)程中，基于RTKLIB進(jìn)行基線解算，短基線的雙差模糊度整體高于中長(zhǎng)、長(zhǎng)基線的雙差模糊度。實(shí)測(cè)實(shí)驗(yàn)以代表性實(shí)測(cè)數(shù)據(jù)(長(zhǎng)、中長(zhǎng)、短基線)為例進(jìn)行深入分析，具有更強(qiáng)的說(shuō)服力。

3.1 仿真實(shí)驗(yàn)分析

仿真實(shí)驗(yàn)的方差協(xié)方差矩陣不依賴于特定衛(wèi)星和接收機(jī)的幾何構(gòu)圖及定權(quán)方式，能更全面地檢驗(yàn)BLAMBDA算法。構(gòu)造方法如下：

(20)

式中，randn(n,1)為隨機(jī)函數(shù)生成的符合正態(tài)分布的n個(gè)隨機(jī)數(shù)。

首先對(duì)2種LTDL分解方法進(jìn)行仿真實(shí)驗(yàn)，仿真維數(shù)為6～40維。為避免偶然性，對(duì)每組仿真數(shù)據(jù)的2種分解方式各模擬100次，求取時(shí)間的平均值。圖1為BLAMBDA算法中改進(jìn)后的MLTDL分解算法與LAMBDA算法中LTDL分解算法的解算時(shí)間對(duì)比。

圖1 2種分解算法的平均運(yùn)行時(shí)間Fig.1 Average running time of two decomposition algorithms

為更直觀地說(shuō)明BLAMBDA算法能夠減少條件方差交換次數(shù)，僅對(duì)條件方差矩陣進(jìn)行分塊處理，模擬方式與圖1相同，實(shí)驗(yàn)結(jié)果如圖2所示。BLAMBDA算法和LAMBDA算法整體降相關(guān)耗時(shí)對(duì)比如圖3所示。

圖2 2種算法條件方差交換次數(shù)對(duì)比Fig.2 Comparison of conditional variance switching times between two algorithms

圖3 2種算法降相關(guān)耗時(shí)對(duì)比Fig.3 Time consumption of decorrelation of two algorithms

由圖1可見(jiàn)，LTDL分解算法具有可行性，說(shuō)明減少矩陣的數(shù)乘可以明顯提高矩陣分解效率。由圖2可見(jiàn)，相較于LAMBDA算法，BLAMBDA分塊算法具有明顯的優(yōu)越性。由圖3可見(jiàn)，總體上看，BLAMBDA算法在去相關(guān)耗時(shí)效率上優(yōu)于LAMBDA算法。

3.2 實(shí)測(cè)實(shí)驗(yàn)

實(shí)測(cè)實(shí)驗(yàn)分為3組：1)短基線組采用1組和芯星通UB4B0-MINI板卡采集的靜態(tài)觀測(cè)數(shù)據(jù)，基線長(zhǎng)89.83 m，采樣間隔為1 s，截取3 000個(gè)歷元進(jìn)行實(shí)驗(yàn)分析； 2)中長(zhǎng)基線組采用武漢大學(xué)IGS數(shù)據(jù)中心下載的香港地區(qū)HKSL和HKWS測(cè)站的IGS數(shù)據(jù)，2站構(gòu)成的基線長(zhǎng)度為42.51 km，采樣間隔為30 s；3)長(zhǎng)基線組采用武漢大學(xué)IGS數(shù)據(jù)中心下載的香港地區(qū)HKSL測(cè)站和上海SHAO測(cè)站的IGS數(shù)據(jù)，2站構(gòu)成的基線長(zhǎng)度為1 216.01 km，采樣間隔為30 s。本文所使用的數(shù)據(jù)包括星歷數(shù)據(jù)和觀測(cè)數(shù)據(jù)，且均為標(biāo)準(zhǔn)RINEX格式。為保證實(shí)驗(yàn)的合理性，BLAMBDA算法和LAMBDA算法均采用SEVB搜索算法進(jìn)行降相關(guān)處理[3]。本實(shí)驗(yàn)基于RTKLIB的源代碼進(jìn)行數(shù)據(jù)處理,實(shí)際解算過(guò)程中對(duì)2種算法的固定模糊度進(jìn)行對(duì)比發(fā)現(xiàn)，二者結(jié)果一致性較高。本文提出的算法與RTKLIB源代碼中的LAMBDA算法具有一致性，在此基礎(chǔ)上采用GPS、BDS、Galileo、GLONASS等多系統(tǒng)數(shù)據(jù)進(jìn)行整周模糊度融合解算，3種基線解算時(shí)間對(duì)比情況如圖4所示，耗時(shí)概率分布如圖5所示。

圖4 3種基線解算時(shí)間對(duì)比Fig.4 Comparison of three baseline calculation time

圖5 3種基線解算時(shí)間耗時(shí)概率對(duì)比分布Fig.5 Probability distribution of three baseline calculation time

由圖4可見(jiàn)，BLAMBDA算法的解算時(shí)間明顯短于LAMBDA算法。由于中長(zhǎng)、長(zhǎng)基線的采樣間隔為30 s，而短基線的時(shí)間間隔為1 s，中長(zhǎng)、長(zhǎng)基線的觀測(cè)時(shí)間長(zhǎng)于短基線，因此圖4(a)的時(shí)間波動(dòng)比圖4(b)、(c)的平緩。此外，短基線的雙差模糊度維數(shù)整體高于中長(zhǎng)、長(zhǎng)基線，雙差模糊度維數(shù)越高，BLAMBDA算法對(duì)時(shí)間效率的提升越明顯。

由圖5(a)可見(jiàn)，LAMBDA算法在0.021～0.035 s內(nèi)的解算耗時(shí)概率明顯高于BLAMBDA算法，BLAMBDA算法的解算耗時(shí)大都集中在0.020 s左右；由圖5(b)、(c)可見(jiàn)，中長(zhǎng)基線和長(zhǎng)基線的BLAMBDA算法解算耗時(shí)與LAMBDA算法相比方差較小，解算耗時(shí)分布更加集中。LAMBDA算法存在高耗時(shí)的現(xiàn)象，而B(niǎo)LAMBDA算法在某種程度上彌補(bǔ)了這一缺陷。由此可以看出，BLAMBDA算法不僅在解算效率上優(yōu)于LAMBDA算法，而且具有更好的穩(wěn)定性。

4 結(jié) 語(yǔ)

為解決LAMBDA算法模糊度去相關(guān)過(guò)程計(jì)算量過(guò)大的問(wèn)題，引入條件方差矩陣分塊方法，并對(duì)分解算法進(jìn)行改進(jìn)，提出BLAMBDA算法。仿真與實(shí)測(cè)實(shí)驗(yàn)結(jié)果表明，BLAMBDA算法求解模糊度的整體效率高于LAMBDA算法。各歷元解算耗時(shí)大小的概率分布表明，BLAMBDA算法的計(jì)算穩(wěn)定性優(yōu)于LAMBDA算法。

在BLAMBDA算法中，對(duì)條件方差矩陣進(jìn)行分塊處理，可以進(jìn)一步提高模糊度的解算效率，這將是BLAMBDA算法下一步的研究重點(diǎn)。