李克昭 田晨冬

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

目前應(yīng)用最廣泛的模糊度固定方法是基于整數(shù)最小二乘原則在模糊度域中確定模糊度的最小二乘模糊度去相關(guān)算法LAMBDA[1]。LAMBDA算法主要包括3個(gè)步驟:模糊度降相關(guān)、模糊度搜索、模糊度檢驗(yàn)。其中,模糊度降相關(guān)涉及大量矩陣運(yùn)算,耗時(shí)較長(zhǎng),因此有必要對(duì)其降相關(guān)過(guò)程進(jìn)行研究,提高計(jì)算效率。國(guó)內(nèi)外學(xué)者對(duì)降相關(guān)過(guò)程進(jìn)行了大量研究:Liu等[2]基于上下三角過(guò)程構(gòu)造聯(lián)合去相關(guān)算法;Xu[3]使用Cholesky分解法構(gòu)建整數(shù)高斯矩陣,在高維情況下分解得到條件數(shù)最小的浮點(diǎn)解協(xié)方差矩陣;陳樹(shù)新[4]提出一種以降低協(xié)方差矩陣條件數(shù)為準(zhǔn)則的模糊度去相關(guān)算法;Liu等[5]克服了Z變換可能帶來(lái)的矩陣病態(tài)分解,減少了20%的解算時(shí)間;安向東等[6]根據(jù)頻間偏差率范圍,采用搜索方法和線性模型去除相位頻間偏差對(duì)寬窄巷模糊度的影響;邱蕾等[7]提出在位移值較大的情況下通過(guò)多種載波相位組合方法解算短基線GPS整周模糊度。自從Hassibi等[8]將格理論中的規(guī)約算法Lenstra-Lenstra-Lovász(LLL)應(yīng)用于模糊度降相關(guān)以來(lái),諸多學(xué)者從格基規(guī)約理論出發(fā)分析LLL的降相關(guān)性能:Xu[9]提出一種性能優(yōu)于整數(shù)高斯去相關(guān)算法和LLL算法的逆整數(shù)Cholesky去相關(guān)方法;范龍[10]基于分塊Gram-Schmidt正交化算法改進(jìn)LLL算法;謝愷等[11]基于系統(tǒng)旋轉(zhuǎn)的Houscholder正交變換對(duì)LLL算法進(jìn)行改進(jìn);盧立果[12]采用分塊降維方法改進(jìn)LLL算法。

上述方法中,Cholesky去相關(guān)法效果較好,但也存在一定的缺陷:1)L、D、LT子矩陣的形成過(guò)程過(guò)于復(fù)雜;2)在實(shí)際編程計(jì)算中,L、D、LT矩陣元素需要較多的存儲(chǔ)矩陣;3)各矩陣元素只能按順序求出;4)未能有效利用各子矩陣元素之間的關(guān)系?；诖?本文提出一種改進(jìn)的M-Cholesky分解法,用合成矩陣取代L、D、LT矩陣,簡(jiǎn)化了L、D、LT子矩陣的關(guān)系;之后,利用高斯算法中的四角規(guī)則計(jì)算各子矩陣元素,提升分解時(shí)的解算效率,可減少約40%的計(jì)算元素個(gè)數(shù)。

1 基于Cholesky分解的模糊度去相關(guān)模型

GNSS觀測(cè)方程的模型求解可以等價(jià)于求解下式的最小值問(wèn)題:

(1)

由于模糊度分量之間通常具有很高的相關(guān)性,因此搜索效率較低。為了使求解過(guò)程更高效,可以通過(guò)整數(shù)高斯變換(Z變換)將其轉(zhuǎn)化為新的最小二乘問(wèn)題:

(2)

(3)

式中,Z為幺模矩陣,即矩陣的行列式為1。矩陣Z的元素均為整數(shù)。

(4)

(5)

式中,I為n維單位矩陣,η為對(duì)L矩陣的第i行第j列的元素取整,ei和ej為單位坐標(biāo)向量。

2 M-Cholesky分解算法

傳統(tǒng)Cholesky分解模型復(fù)雜,且需要4個(gè)數(shù)組分別存放Q、LT、D、L矩陣。本文通過(guò)研究矩陣間各元素的相應(yīng)關(guān)系,引入合成矩陣來(lái)減少計(jì)算所需的數(shù)組,并結(jié)合高斯算法中的四角規(guī)則提出一種改進(jìn)的M-Cholesky分解法。

以4階矩陣Q為例,給出其Cholesky分解:

(6)

將LT、D、L矩陣整合得到的合成矩陣與Q矩陣各元素進(jìn)行比較,合成矩陣與Q矩陣的對(duì)應(yīng)元素關(guān)系如式(7)中的合成矩陣所示:

(7)

可以看出: 1)利用式(7)進(jìn)行Cholesky分解時(shí),可在Q矩陣的基礎(chǔ)上直接計(jì)算得到合成矩陣,僅需要1個(gè)數(shù)組即可存放原本需要3個(gè)數(shù)組存儲(chǔ)的內(nèi)存;2)合成矩陣中的元素lij與lji關(guān)于主對(duì)角線元素對(duì)稱(chēng)相等,因此在進(jìn)行Cholesky分解時(shí),可以僅計(jì)算對(duì)角線元素以上的lij元素,lji=lij。

在上述分析的基礎(chǔ)上,利用四角規(guī)則給出M-Cholesky算法中合成矩陣元素的計(jì)算步驟:

1)基于dii對(duì)第i行元素進(jìn)行規(guī)約化處理,得到lij元素;

3)將第i行的lij賦值給第i列的lji元素;

4)對(duì)(i-1),(i-2),…,1行依次循環(huán),完成所有計(jì)算。

其中,步驟2)中參與計(jì)算的元素為:

(8)

由式(8)可以看出,每次參與合成矩陣計(jì)算的4個(gè)元素均位于矩形的4個(gè)角上,因此稱(chēng)之為四角規(guī)則。在M-Cholesky算法計(jì)算過(guò)程中,所有計(jì)算元素轉(zhuǎn)換為相應(yīng)的對(duì)角元素、交叉元素和消元元素時(shí),最多只用到3個(gè)元素,因此可以將該計(jì)算過(guò)程視為規(guī)約化后的消元計(jì)算。M-Cholesky算法與Cholesky算法在計(jì)算過(guò)程中所需的計(jì)算元素個(gè)數(shù)如表1所示。

表1 M-Cholesky算法與Cholesky算法所需計(jì)算元素個(gè)數(shù)對(duì)比Tab.1 Comparison of numbers of computing elements required by M-Cholesky algorithm and Cholesky algorithm

由表1可見(jiàn),M-Cholesky算法可減少約40%的計(jì)算元素,提高了計(jì)算效率,且不影響計(jì)算結(jié)果的精度。

3 實(shí)驗(yàn)驗(yàn)證

解算精度與時(shí)間效率是判斷一個(gè)模糊度解算算法是否可行的關(guān)鍵,但由于本文所提出的M-Cholesky算法僅改變了計(jì)算元素,并不影響定位精度,因此僅采用仿真數(shù)據(jù)與實(shí)測(cè)數(shù)據(jù)對(duì)Cholesky算法與M-Cholesky算法的運(yùn)行時(shí)間進(jìn)行比較。

本文基于Microsoft Visual Studio 2019,利用C語(yǔ)言進(jìn)行M-Cholesky算法的程序設(shè)計(jì),并進(jìn)行數(shù)值模擬測(cè)試。所有計(jì)算均在Windows 10操作系統(tǒng)的電腦平臺(tái)上進(jìn)行,處理器為16 GB內(nèi)存的Intel(R) Core(TM) i7-8750H CPU@ 2.20 Hz。

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

參照文獻(xiàn)[13]的仿真參數(shù)進(jìn)行仿真實(shí)驗(yàn),仿真維數(shù)為5～40。為避免偶然情況的出現(xiàn),每次仿真實(shí)驗(yàn)取100次均值。2種算法的平均運(yùn)行時(shí)間如圖1所示,所有情況下40維的平均運(yùn)行時(shí)間如表2所示。

圖1 平均運(yùn)行時(shí)間Fig.1 Average running time

表2 40維解算時(shí)間對(duì)比Tab.2 Comparison of 40 dimensional solution time

由圖1可見(jiàn),在觀測(cè)維數(shù)為5～40的情況下,2種方法的計(jì)算時(shí)間雖然偶爾有波動(dòng),但整體上都隨維數(shù)的增加而增加,其中M-Cholesky算法計(jì)算時(shí)間總體低于Cholesky算法,且計(jì)算效率也隨維數(shù)的增加而提升。由表2可見(jiàn),M-Cholesky算法的計(jì)算時(shí)間更短,相比于Cholesky算法,情況1～7中,M-Cholesky算法計(jì)算時(shí)間分別提升10.6%、13.5%、12.5%、16%、15.7%、13.5%、20.3%。

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

實(shí)測(cè)實(shí)驗(yàn)分為3組:1)短基線組采用和芯星通UB4B0-MINI板卡采集的靜態(tài)觀測(cè)數(shù)據(jù),基線長(zhǎng)89.83 m,采樣間隔1 s,截取3 000個(gè)歷元對(duì)解算時(shí)間和結(jié)果進(jìn)行分析;2)中長(zhǎng)基線組采用武漢大學(xué)IGS數(shù)據(jù)中心下載的香港地區(qū)HKSL和HKWS站的IGS數(shù)據(jù),2站構(gòu)成的基線長(zhǎng)度為42.51 km,采樣間隔30 s;3)長(zhǎng)基線組采用武漢大學(xué)IGS數(shù)據(jù)中心下載的香港地區(qū)HKSL和武漢地區(qū)JFNG站的IGS數(shù)據(jù),2站構(gòu)成的基線長(zhǎng)度為903.26 km,采樣間隔30 s。所使用的數(shù)據(jù)均為標(biāo)準(zhǔn)RINEX格式數(shù)據(jù),包括星歷數(shù)據(jù)和觀測(cè)數(shù)據(jù)。

采用GPS、BDS、Galileo、GLONASS多系統(tǒng)數(shù)據(jù)進(jìn)行整周模糊度融合解算,3種基線解算時(shí)間對(duì)比情況如圖2～4所示。

圖2 短基線解算時(shí)間對(duì)比Fig.2 Comparison of short baseline solution time

由圖2可見(jiàn),Cholesky算法的解算時(shí)間大致在(1.6～1.8)×104μs之間,而本文提出的M-Cholesky算法解算時(shí)間大致在(1.5～1.7)×104μs之間,所需解算時(shí)間較少,且M-Cholesky算法的整周模糊度解算結(jié)果相對(duì)穩(wěn)定。由圖3、4也可以看出,M-Cholesky算法在解算時(shí)間和解算穩(wěn)定性上表現(xiàn)更好。需要說(shuō)明的是,短基線實(shí)驗(yàn)結(jié)果是從觀測(cè)到的17 570個(gè)歷元中截取的3 000個(gè)歷元,采樣間隔為1 s,而中長(zhǎng)、長(zhǎng)基線的觀測(cè)時(shí)段長(zhǎng)于短基線,采樣間隔均為30 s,因此圖2解算時(shí)間曲線較圖3、4更平緩。

圖3 中長(zhǎng)基線解算時(shí)間對(duì)比Fig.3 Comparison of medium baseline solution time

圖4 長(zhǎng)基線解算時(shí)間對(duì)比Fig.4 Comparison of long baseline solution time

4 結(jié) 語(yǔ)

本文分析影響Cholesky算法計(jì)算效率的因素,引入四角規(guī)則,提出一種改進(jìn)的M-Cholesky算法。實(shí)驗(yàn)結(jié)果表明,相對(duì)于Cholesky算法,M-Cholesky算法求解模糊度的計(jì)算時(shí)間減少約15%,提高了整周模糊度固定的效率,且解算精度與Cholesky算法一致。

如何處理四角規(guī)則中分母為0或接近0時(shí)的特殊情況,是完善M-Cholesky算法需要進(jìn)一步考慮的問(wèn)題。