模糊度降相關(guān)的整數(shù)分塊正交化算法

范 龍,翟國君,柴洪洲

1．海軍海洋測繪研究所,天津 300061;2．信息工程大學(xué)地理空間信息學(xué)院,河南鄭州 450052

模糊度降相關(guān)的整數(shù)分塊正交化算法

范 龍1,翟國君1,柴洪洲2

1．海軍海洋測繪研究所,天津 300061;2．信息工程大學(xué)地理空間信息學(xué)院,河南鄭州 450052

隨著模糊度實數(shù)解協(xié)方差矩陣維數(shù)的增加,由于取整運(yùn)算舍入誤差的影響,LLL降相關(guān)算法的成功率低、降相關(guān)效果差。本文引入分塊正交的思想,設(shè)計了整數(shù)分塊Gram-Schmidt正交化算法,同時聯(lián)合LLL算法提出基于整數(shù)分塊正交化的LLL降相關(guān)算法(IBGS-LLL)。利用隨機(jī)模擬的方法分析不同維數(shù)下不同分塊方式的降相關(guān)效果,明確了不同模式下算法的分塊方式。基于模擬和實測的數(shù)據(jù)與改進(jìn)的LLL算法進(jìn)行比較,證明IBGS-LLL算法在模糊度協(xié)方差矩陣降相關(guān)方面具有更優(yōu)的效果和更高的成功率。

整周模糊度;LLL降相關(guān);整數(shù)分塊Gram-Schmidt正交化

1 引 言

基于模糊度域[1-2]進(jìn)行模糊度解算的方法中,由于實數(shù)解之間存在較強(qiáng)的相關(guān)性,導(dǎo)致構(gòu)造出搜索空間的形狀呈扁長的橢球體,這將會嚴(yán)重影響搜索的效率,并且最終可能導(dǎo)致解算失敗。為了改善這種情況,在搜索之前有必要對實數(shù)解進(jìn)行降相關(guān)處理。文獻(xiàn)[3—5]提出最小二乘去相關(guān)算法(LAMBDA),通過構(gòu)造整數(shù)高斯變換矩陣對實數(shù)解進(jìn)行降相關(guān)處理;文獻(xiàn)[6]對LAMBDA算法的整個過程進(jìn)行了詳細(xì)介紹,并提出系統(tǒng)配對的策略來構(gòu)造Z變換矩陣;文獻(xiàn)[7—8]提出基于Cholesky分解的模糊度降相關(guān)算法;文獻(xiàn)[9]提出多次整數(shù)三角分解降相關(guān)的方法;文獻(xiàn)[10]提出利用遞歸的方法直接最小化轉(zhuǎn)換矩陣的對角線元素的方法;文獻(xiàn)[11]提出對模糊度協(xié)方差矩陣的對角線元素進(jìn)行排序的降相關(guān)算法;文獻(xiàn)[12]基于格理論的相關(guān)應(yīng)用,設(shè)計了著名的LLL規(guī)約算法,近年來該算法在格基規(guī)約領(lǐng)域得到了深入的研究和廣泛的應(yīng)用;文獻(xiàn)[13]對LLL規(guī)約算法進(jìn)行轉(zhuǎn)化,將其應(yīng)用到模糊度降相關(guān)中;文獻(xiàn)[14]利用隨機(jī)模擬的方法計算出模糊度協(xié)方差矩陣,對LLL降相關(guān)算法進(jìn)行分析研究,并與整數(shù)高斯變換、整數(shù)Cholesky分解等算法進(jìn)行比較;文獻(xiàn)[15]針對LLL降相關(guān)算法在取整過程中會引入較大的舍入誤差的問題,提出基于矩陣整體進(jìn)行取整的改進(jìn)的LLL算法。以上幾種LLL算法均是基于經(jīng)典的Gram-Schmidt正交化(CGS)。文獻(xiàn)[16]提出基于修正的Gram-Schmidt正交化(MGS)變換[17]的LLL算法。隨著GPS的現(xiàn)代化進(jìn)程、GLONASS的補(bǔ)充更新計劃、Galileo和我國北斗系統(tǒng)的逐步建設(shè)與應(yīng)用,GNSS系統(tǒng)呈現(xiàn)出多模式、多頻段的發(fā)展趨勢,有更多的觀測信息可供用戶使用,進(jìn)而模糊度實數(shù)解協(xié)方差矩陣的維數(shù)也會隨之增大。LLL降相關(guān)算法基于低級的基本線性代數(shù)子程序(basic linear algebra subprograms,BLAS)運(yùn)算[18]。算法對向量逐一循環(huán)進(jìn)行整數(shù)正交變換,由于取整舍入誤差的影響,經(jīng)過變換后向量之間不能完全正交,在對下一個向量進(jìn)行處理時,舍入誤差也會隨著之前經(jīng)過變換的向量代入正交化的過程中,隨著循環(huán)的進(jìn)行,其舍入誤差累積的影響越來越嚴(yán)重。高維情況下,可能會導(dǎo)致降相關(guān)失敗。針對實數(shù)解協(xié)方差矩陣高維情況下降相關(guān)的問題,本文設(shè)計了整數(shù)分塊正交化算法,并將其應(yīng)用到降相關(guān)中,提出基于整數(shù)分塊正交化的LLL降相關(guān)算法(IBGSLLL)。利用隨機(jī)模擬的數(shù)據(jù),分析了不同維數(shù)情況下,不同分塊方式對算法降相關(guān)效果的影響,利用IBGS-LLL算法在靜態(tài)和動態(tài)情況下,分別選用不同的分塊方式與改進(jìn)的LLL算法[15]進(jìn)行比較,結(jié)果表明IBGS-LLL算法的平均相關(guān)系數(shù)和條件數(shù)的改善程度均優(yōu)于改進(jìn)的LLL算法。經(jīng)過IBGS-LLL算法降相關(guān)之后的協(xié)方差矩陣更加接近對角陣,進(jìn)而較好地改善了模糊度的搜索空間。

2 整數(shù)分塊Gram-Schmidt正交化算法

分塊Gram-Schmidt正交化算法(BGS)[18-20]首先將矩陣中所有的列向量分為若干塊,而后對每個分塊矩陣逐一進(jìn)行正交化和重正交化變換,保證了高維情況下算法的效果和穩(wěn)定性。基于模糊度降相關(guān)中對變換矩陣的要求,本文設(shè)計了整數(shù)分塊Gram-Schmidt正交化算法(IBGS)。

BGS算法同CGS算法一樣,都保證了矩陣中的每個列向量經(jīng)過正交化變換。不同的是, CGS算法是對每個向量逐一進(jìn)行變換的一層循環(huán)過程,而分塊正交化算法是包括對每個矩陣塊進(jìn)行遍歷處理和對矩陣塊內(nèi)部所包含的向量逐一進(jìn)行處理的內(nèi)外兩層循環(huán)過程。

首先對每個向量的正交化過程進(jìn)行分析,對于列滿秩矩陣H＝[h1h2…h(huán)n],假設(shè)其前k－1個向量已經(jīng)進(jìn)行了正交變換后得到相互正交的向量q1,q2,…,qk－1,則第k個向量hk首先與q1進(jìn)行正交化變換

該誤差是由于經(jīng)過整數(shù)GS變換后的向量之間不能完全正交而引起的。隨著對其余向量逐一進(jìn)行正交變換,該誤差還會累積,越往后影響越大。依據(jù)標(biāo)準(zhǔn)GS正交變換的原理,對于每個向量,應(yīng)采用如式所示的正交化過程。對于k＝2, 3,…,n

結(jié)合以上討論的對于每個向量的整數(shù)正交化過程和分塊正交算法[18]即可設(shè)計相應(yīng)的IBGS算法。由于矩陣H＝[h1h2…h(huán)n]的n個列向量之間不存在相關(guān)性。將H按其列向量分為m個矩陣塊,每塊由nm個向量組成。

首先展開i＝1,2,…,m的外層循環(huán)過程。與CGS算法不同的是,當(dāng)i＝1時分塊算法對應(yīng)的是一個矩陣塊而不是向量,所以必須對矩陣塊H1＝[h1h2…h(huán)nm]進(jìn)行變換處理,以保證其內(nèi)部向量之間的正交特性和后續(xù)正交化過程的順利進(jìn)行。利用式(10)所示向量的整數(shù)正交化過程進(jìn)行變換,由于取整運(yùn)算舍入誤差的存在,hk經(jīng)過一次整數(shù)正交化變換之后,其與前k－1個向量之間的正交程度還不滿足要求,可以進(jìn)行多次迭代,直到該向量對應(yīng)的所有正交化系數(shù)的實數(shù)值都小于0．5時停止迭代。變換可由矩陣表示為

在保證第1個分塊矩陣完成整數(shù)正交變換之后,即可對其余m－1個分塊矩陣進(jìn)行遍歷處理。本文將每個具體的分塊矩陣進(jìn)行正交化變換的過程分為外變換、內(nèi)變換兩個部分,其中外變換為當(dāng)前第i個分塊矩陣與之前i－1個分塊之間的整數(shù)正交化變換;內(nèi)變換包括當(dāng)前分塊內(nèi)部各向量之間的變換和與之前向量的重正交變換。內(nèi)層j＝1,2,…,nm的循環(huán)過程就在這兩個部分中分別展開。

(2)內(nèi)變換部分:此部分的變換是以實現(xiàn)分塊矩陣內(nèi)部各向量之間相互正交為目的。由于ˉh(i－1)nm＋1在內(nèi)變換過程中作為第1個向量,為了保證后面向量能夠正確的進(jìn)行變換,需要依據(jù)式(12)所示的變換過程,與之前的(i－1)nm個變換后的向量進(jìn)行一次整數(shù)重正交變換并最終得到對于ˉHi中的第j≥2個向量,在分塊內(nèi)部進(jìn)行如下變換

經(jīng)過以上過程之后,當(dāng)前向量已經(jīng)完成與其之前所有分塊矩陣和當(dāng)前分塊中的向量的整數(shù)正交變換,為了進(jìn)一步保證該向量與之前所有向量的正交化程度,再進(jìn)行一次整數(shù)重正交變換

得到能夠滿足近似正交的矩陣H?及相應(yīng)的轉(zhuǎn)換矩陣R,是由若干個滿足降相關(guān)條件的變換矩陣相乘得到的,因此也滿足所有元素為整數(shù)且行列式為1的條件。

3 基于整數(shù)分塊正交化的LLL降相關(guān)算法

基于第2節(jié)提出的算法,本文設(shè)計了基于整數(shù)分塊GS變換的降相關(guān)算法(IBGS-LLL),其具體過程如下:

(1)利用Cholesky分解對模糊度實數(shù)解的協(xié)方差矩陣進(jìn)行分解Q^a＝HTH,得到上三角矩陣H。

(2)考慮到降相關(guān)變換矩陣整數(shù)的特性,為了提高其變換性能,在變換之前需要對矩陣的列向量進(jìn)行重新排列,使其相應(yīng)的正交化向量的高斯范數(shù)能夠盡可能地按照由小到大的順序,參考文獻(xiàn)[21—22],利用系統(tǒng)旋轉(zhuǎn)變換的方式構(gòu)造初等變換矩陣U,并對上三角矩陣進(jìn)行變換＝HU。

經(jīng)過以上3步變換之后,H?中的列向量之間能夠滿足近似的正交,但是由于整數(shù)變換的特點(diǎn),其正交變換還不徹底,為了保證變換之后各向量之間的夾角能夠盡可能接近90°,需要對整個過程進(jìn)行迭代,即對H?再進(jìn)行步驟(2)和步驟(3)的處理。本文引入平均相關(guān)系數(shù)來判斷迭代是否終止。其具體定義為,首先對于一個矩陣H,可定義其相關(guān)矩陣為[23]

每一次整體變換之后都計算出一個γ值,通過試驗分析,經(jīng)過一定次數(shù)的迭代之后實數(shù)解協(xié)方差矩陣的平均相關(guān)系數(shù)不會再發(fā)生變化,因此可將判斷標(biāo)準(zhǔn)設(shè)置為當(dāng)γi＝γi－1時迭代停止。從而步驟(3)可改變?yōu)槔肐BGS算法對重排列之后的H矩陣進(jìn)行整數(shù)正交變換,得到矩陣H?,計算其相應(yīng)的平均相關(guān)系數(shù),判斷其是否等于上次計算的平均相關(guān)系數(shù),若相等則停止迭代否則重復(fù)步驟(2)和步驟(3)。

經(jīng)過k次迭代之后得到最終的整數(shù)轉(zhuǎn)換矩陣Rall＝U1R1…UkRk,由于初等變換矩陣Ui滿足所有元素為整數(shù)且行列式為1的條件,因此Rall滿足降相關(guān)變換矩陣的要求。相應(yīng)的降相關(guān)之后的模糊度實數(shù)解和協(xié)方差矩陣為利用其即可構(gòu)建搜索區(qū)域?qū)δ：冗M(jìn)行固定,得到整數(shù)解向量ˉz,而后再利用整數(shù)變換矩陣將其轉(zhuǎn)換最終的整周模糊度解

4 計算分析

每一組GNSS觀測數(shù)據(jù)都對應(yīng)著一定的觀測模式和特定的衛(wèi)星與測站之間的幾何結(jié)構(gòu)關(guān)系,若只用一組數(shù)據(jù)進(jìn)行計算分析,不能在普遍意義下說明算法的正確性和有效性。為此,本文采用隨機(jī)模擬的方法[14],模擬出模糊度實數(shù)解的協(xié)方差矩陣進(jìn)行計算分析。

IBGS-LLL算法基于分塊正交變換對實數(shù)解的協(xié)方差矩陣進(jìn)行處理,算法通常是先將矩陣按其列向量均勻的分成若干子塊后,再對其進(jìn)行變換。對于不同的觀測數(shù)據(jù),模糊度實數(shù)解協(xié)方差矩陣的維數(shù)并不相同,當(dāng)矩陣的維數(shù)為因數(shù)時,可以將其均勻分塊;當(dāng)為素數(shù)時,最簡單的方法就是將其分成兩個子塊,同時可以更加細(xì)致地將矩陣分為m個子塊,其中每個子塊包含兩個列向量,本文將這兩種分塊方式分別簡稱為B-2和B-m2,在矩陣維數(shù)不確定的情況下,相比較而言這兩種分塊方式在形式上是比較均勻的。不同的分塊方式,算法的計算結(jié)果和效率也不相同,有必要在不同的分塊情況下對算法進(jìn)行分析,從而確定最佳的分塊方式以保證降相關(guān)的順利進(jìn)行。

首先在固定模糊度未知參數(shù)個數(shù)的情況下,模擬維數(shù)分別為n＝9、n＝25和n＝50各200組協(xié)方差矩陣,對各維數(shù)進(jìn)行具體分塊為[m＝5, m＝3,m＝2]、[m＝13,m＝5,m＝2]和[m＝25, m＝10,m＝2],利用IBGS-LLL算法下進(jìn)行分析,模擬的固定維數(shù)下的3種情況,原始的協(xié)方差矩陣的條件數(shù)一般在104～108的范圍內(nèi)變化,矩陣維數(shù)越小,γ越大,模糊度實數(shù)解之間的相關(guān)性越強(qiáng)。對固定維數(shù)情況下的結(jié)果進(jìn)行了統(tǒng)計,計算出相應(yīng)的平均降相關(guān)系數(shù)的平均值ˉγ、條件數(shù)的平均值ˉc和算法耗時的平均值ˉt,如表1所示。

經(jīng)過IBGS-LLL算法處理之后,對于不同的分塊情況,其平均相關(guān)系數(shù)和條件數(shù)都有明顯的改善,都能夠成功地實現(xiàn)降相關(guān)。由于3種情況下的維數(shù)均為因數(shù),都存在除了1和其本身之外可被整除的數(shù),每種維數(shù)情況下都采用了B-2和B-m2的分塊方式,無論在均勻分塊的情況下(如50維),還是在不均勻分塊的情況下(如9維、25維),兩種分塊方式與其他均勻的分塊的計算結(jié)果一致。由表可知,這3種維數(shù)情況下,原始協(xié)方差矩陣的都大于0．3都大于105。

表1 固定維數(shù)情況下不同分塊結(jié)果的統(tǒng)計Tab．1 The statistic of different block result under the fixed dimension condition

不同分塊方式下,其結(jié)果較原來都有明顯的改善。隨著矩陣維數(shù)的增大,結(jié)果的條件數(shù)雖然有所改善,但是卻越來越大;而平均相關(guān)系數(shù)的均值隨著維數(shù)的增大越來越小,在50維的情況下均明顯小于0．1。這是由于原始矩陣的相關(guān)程度隨著維數(shù)的增加而降低,算法迭代的次數(shù)比低維的情況少,并且矩陣的條件數(shù)僅反映最大和最小特征之間的差距,并不能反映整個矩陣的相關(guān)性,從而導(dǎo)致表中所示的結(jié)果。在算法的運(yùn)行時間方面,隨著維數(shù)的增加算法的耗時也相應(yīng)增大,不同分塊方式的耗用時間基本相同,相差最大也僅為毫秒的量級。由此可知,固定維數(shù)的情況下,B-2和B-m2的分塊方式無論能否實現(xiàn)均勻的分塊,都可成功實現(xiàn)降相關(guān),并且效果與其他均勻分塊方式一致。為進(jìn)一步進(jìn)行分析,利用B-2和B-m2的分塊方式在維數(shù)不固定的情況下,分別模擬了低維n∈[4,20]和高維n∈[21,100]兩種情況下各200組數(shù)據(jù)進(jìn)行降相關(guān)變換。對結(jié)果進(jìn)行了統(tǒng)計,如表2所示。

表2反映了原始矩陣及B-m2和B-2兩種分塊方式結(jié)果的平均相關(guān)系數(shù)的均值ˉγ、條件數(shù)的均值ˉc。由這兩個值可知,兩種分塊方式在維數(shù)隨機(jī)的情況下,降相關(guān)的效果明顯。低維情況下B-2方式的平均相關(guān)系數(shù)、條件數(shù)及算法的效率與B-m2相比都略差;高維情況下,兩種方式的平均降相關(guān)系數(shù)是很一致的,同時由于B-2分塊得到的子塊維數(shù)比較大,需要經(jīng)過更多次的迭代,所以耗時比B-m2稍長,但其量級也僅為0．01 s。在條件數(shù)的改進(jìn)方面,B-2明顯優(yōu)于B-m2。這是由于高維情況下細(xì)致的分塊方式,因分塊數(shù)的增多,其累計誤差對正交化的過程影響明顯,而B-2的分塊方式,雖然在每個子塊內(nèi)需要經(jīng)過更多次迭代,但是其受到的累積誤差明顯小于B-m2,所以其綜合效果要好一些。由以上分析可知,低維情況下可以選用B-m2的分塊方式,高維情況下可選用B-2的分塊方式。

表2 維數(shù)隨機(jī)情況下B-m2和B-2分塊方式結(jié)果的統(tǒng)計Tab．2 The statistic of different block result under the random dimension condition

由于文獻(xiàn)[14—15]中提到的LLL降相關(guān)算法受到舍入誤差的影響非常大,其效果和成功率都比較低,在實際降相關(guān)應(yīng)用中很少被使用。文獻(xiàn)[16]通過模擬計算證明了基于矩陣整體變換的改進(jìn)的LLL降相關(guān)算法,對于協(xié)方差矩陣的條件數(shù)和平均相關(guān)系數(shù)的改進(jìn)都明顯優(yōu)于LLL降相關(guān)算法,為了說明IBGS-LLL算法的降相關(guān)效果,本文采用基于改進(jìn)的LLL降相關(guān)算法[15]代替LLL算法(在后面的圖表中以LLL作為其相應(yīng)的標(biāo)識)分別在動態(tài)和靜態(tài)兩種模式下與IBGSLLL算法進(jìn)行分析比較。動態(tài)模式下,由于載體狀態(tài)變化大、觀測時間短,從而可觀測到的衛(wèi)星數(shù)目少,模糊度未知參數(shù)的個數(shù)一般在4～10之間變化;靜態(tài)模式下,由于接收機(jī)狀態(tài)穩(wěn)定,觀測時間長,單系統(tǒng)雙頻情況下模糊度未知參數(shù)在11～50之間變換[14],GNSS多系統(tǒng)下,用戶可接收到不同系統(tǒng)多個頻段的觀測信號,為了充分驗證IBGSLLL算法在GNSS多系統(tǒng)下的有效性和正確性,本文設(shè)動態(tài)情況下模糊未知個數(shù)在4～20之間變化,靜態(tài)情況下在21～100的范圍變化。本文在靜態(tài)選用基于B-2的分塊方式、動態(tài)選用基于B-m2的分塊方式的IBGS-LLL算法。模擬了兩種狀態(tài)下各200組數(shù)據(jù)進(jìn)行計算,結(jié)果如圖1、圖2所示。

圖1 動態(tài)和靜態(tài)模式下的平均降相關(guān)系數(shù)Fig．1 The average correlation coefficient under the kinematic and static mode

圖2 動態(tài)和靜態(tài)模式下的條件數(shù)Fig．2 The condition number under the kinematic and static mode

圖1、圖2顯示了動態(tài)和靜態(tài)兩種情況下, 200組數(shù)據(jù)的原始矩陣、改進(jìn)的LLL降相關(guān)算法和IBGS-LLL算法結(jié)果的平均相關(guān)系數(shù)和條件數(shù),其中左側(cè)為動態(tài)的情況,右側(cè)為靜態(tài)的情況。兩種方法基本都能完成降相關(guān),IBGS-LLL算法的結(jié)果明顯優(yōu)于改進(jìn)的LLL算法。對結(jié)果的平均相關(guān)系數(shù)和條件數(shù)與原始矩陣進(jìn)行比較,當(dāng)兩個指標(biāo)均小于隨機(jī)模擬的原始矩陣,則降相關(guān)成功,否則降相關(guān)失敗。對所有的200組結(jié)果進(jìn)行分析即可計算出降相關(guān)的成功率。在動態(tài)情況下,由于矩陣維數(shù)較低,兩種算法都可保證百分之百降相關(guān)成功;而靜態(tài)情況下,隨著維數(shù)的增加,改進(jìn)的LLL算法的結(jié)果出現(xiàn)了條件數(shù)和平均相關(guān)系數(shù)大于原始矩陣的情況,經(jīng)過變換后協(xié)方差矩陣中元素的量級明顯增大,說明降相關(guān)失敗,靜態(tài)高維情況下其降相關(guān)的成功率為92．5%;而 IBGS-LLL算法的兩種指標(biāo)都有明顯的改善,其成功率則依然可保證100%。

為了進(jìn)一步突出本文所提算法在高維情況下的優(yōu)勢,選取了靜態(tài)情況下的10組數(shù)據(jù),詳細(xì)分析了其相應(yīng)的平均相關(guān)系數(shù)和條件數(shù)的變化以及算法耗時,見表3。

表3 靜態(tài)情況下改進(jìn)的LLL算法與IBGS-LLL算法的比較Tab．3 The comparing of improved LLL algorithm with IBGS-LLL algorithm under static mode

由表3可以看出靜態(tài)情況下,隨著矩陣維數(shù)的不斷增加,改進(jìn)的LLL算法的降相關(guān)能力逐漸降低,當(dāng)高于一定的維數(shù)時就出現(xiàn)了降相關(guān)失敗的情況,而本文提出的IBGS-LLL算法始終保持良好的降相關(guān)性能。同時注意到隨著維數(shù)的增加,兩種算法的耗時也隨之而增加,由于本文提出的IBGS-LLL算法涉及內(nèi)外變換以及重正交的過程,所以其耗時略高于改進(jìn)的LLL算法,但是兩種方法的差別在0．5 s以內(nèi)。

為了進(jìn)一步分析說明算法在模糊度解算中的作用,選取2012-04-26美國連續(xù)運(yùn)行參考站(http:∥www．ngs．noaa．gov/CORS)的GPS單系統(tǒng)雙頻的觀測數(shù)據(jù)進(jìn)行計算。

方案1:選取了scgp和scgt兩個測站24 h的數(shù)據(jù),其采樣間隔為30 s,共包含78個模糊度未知參數(shù)。

方案2:選取了waar和midt兩個測站10個歷元的數(shù)據(jù),其采樣間隔為1 s,模糊度未知參數(shù)的個數(shù)為7。

這兩種方案分別是為了驗證高維情況下和快速定位情況下,算法的效果。在計算出其模糊度實數(shù)解及協(xié)方差矩陣之后,分別在未進(jìn)行降相關(guān)、改進(jìn)的LLL降相關(guān)和本文提出的IBGS-LLL降相關(guān)的情況下,進(jìn)行模糊度搜索固定,統(tǒng)計了3種情況下,矩陣的條件數(shù)和平均相關(guān)系數(shù)。由于降相關(guān)的目的是為了提高搜索的效率和成功率,為了體現(xiàn)算法在這方面的效果,本文還對經(jīng)過降相關(guān)之后的模糊度搜索的時間和結(jié)果進(jìn)行了分析,計算了不同情況下Bootstrapping算法的成功率[24]

表4 基于美國CORS網(wǎng)的實測數(shù)據(jù)對比分析Tab．4 Analyzing and comparing based on measured data of USA CORS

如表4所示,對于實測數(shù)據(jù)來說,其協(xié)方差矩陣的條件數(shù)和平均相關(guān)系數(shù)與本文模擬的情況大體上是一致的,在低維情況的條件數(shù)和平均相關(guān)系數(shù)都大于高維的情況,兩種方案經(jīng)過IBGSLLL和改進(jìn)的LLL降相關(guān)處理之后,條件數(shù)和平均相關(guān)系數(shù)兩種指標(biāo)都有所改進(jìn),并且IBGSLLL算法的優(yōu)化程度優(yōu)于改進(jìn)的LLL算法。方案1高維情況下,原始協(xié)方差矩陣的Bootstrapping算法的成功率非常低;方案2低維情況下,由于模糊度參數(shù)的維數(shù)較低,所以原始協(xié)方差矩陣的成功率比高維的要高。經(jīng)過降相關(guān)變換之后其成功率都得到了改善,并且本文提出的IBGSLLL算法的成功率均優(yōu)于改進(jìn)的LLL降相關(guān)算法。搜索時間方面,方案1基于原始的協(xié)方差矩陣的模糊度搜索時間需要3 min多,方案2快速定位情況下也需要6 s,說明原始矩陣的搜索效率較低;而經(jīng)過改進(jìn)的LLL降相關(guān)之后,雖然兩種評價指標(biāo)得到了改善,但是高維情況下,其計算效率的改善效果并不太明顯,在快速定位情況下,由于模糊度維數(shù)較低改進(jìn)的LLL算法受到舍入誤差影響不明顯,因此還是能夠在1之內(nèi)獲得模糊度的解;基于IBGS-LLL降相關(guān)的方式,明顯提高了搜索的效率,無論針對方案1還是方案2的數(shù)據(jù),都能夠以很快的速度獲得模糊度解,這更加驗證了本文算法的有效性,說明IBGS-LLL算法能夠較好地優(yōu)化模糊度的搜索空間,提高搜索效率。為了進(jìn)一步說明本文算法對于提高模糊度解算效率的作用,列舉了方案2中原始的模糊度的浮點(diǎn)解、固定解和經(jīng)過IBGS-LLL降相關(guān)的浮點(diǎn)解及其相應(yīng)的固定解,如表5所示。

表5 降相關(guān)前后浮點(diǎn)解與固定解的比較Tab．5 Comparing the ambiguity float solution and fixed solution under the condition of original and decorrelation

5 結(jié) 論

本文將分塊正交的思想引入模糊度降相關(guān)中,設(shè)計了整數(shù)分塊正交化算法,與LLL降相關(guān)算法相結(jié)合,提出了基于整數(shù)分塊正交化的LLL降相關(guān)算法(IBGS-LLL),通過比較分析得出了如下結(jié)論:

(1)LLL算法中整數(shù)正交變換的向量正交化過程,在取整舍入誤差的基礎(chǔ)上還會受到向量之間不能完全正交而引起誤差的影響,該誤差隨著正交化的進(jìn)行會逐漸累積,最終影響降相關(guān)的效果。在對該誤差分析的基礎(chǔ)上,依據(jù)標(biāo)準(zhǔn)的向量正交化過程,對向量的整數(shù)正交化算法進(jìn)行了明確,而后結(jié)合分塊正交算法,設(shè)計了IBGS算法。該算法不但避免了由于向量不完全正交而在正交化過程中引起的誤差,同時通過分塊處理減弱了舍入誤差的影響。

(2)通過在幾種固定維數(shù)下,對不同分塊情況的計算分析發(fā)現(xiàn),無論能否均勻分塊,B-2和B-m2的分塊方式都能夠?qū)崿F(xiàn)與其他均勻分塊方式相當(dāng)?shù)慕迪嚓P(guān)效果。在維數(shù)隨機(jī)的情況下,B-m2在動態(tài)(低維)模式下的降相關(guān)效果略優(yōu)于B-2的分塊方式,而靜態(tài)(高維)模式下,B-2的綜合效果略優(yōu)。

(3)利用IBGS-LLL降相關(guān)在動態(tài)和靜態(tài)模式下,分別選用B-m2和B-2的分塊方式與改進(jìn)的LLL降相關(guān)算法進(jìn)行分析比較,結(jié)果表明改進(jìn)的LLL算法在靜態(tài)矩陣維數(shù)較高的情況下,出現(xiàn)了降相關(guān)失敗的情況,而經(jīng)過IBGS-LLL算法變換之后矩陣的平均相關(guān)系數(shù)、條件數(shù)均優(yōu)于改進(jìn)的LLL降相關(guān)算法,在高維情況下可百分之百實現(xiàn)降相關(guān)。同時基于一組實測數(shù)據(jù)分析了3種情況下搜索的效率,結(jié)果表明IBGS-LLL算法的效果非常明顯,可有效地改善搜索空間,提高搜索效率。

致謝:感謝美國國家海洋和大氣管理局(NOAA)下屬的國家大地測量機(jī)構(gòu)(NGS)提供的CORS數(shù)據(jù)。

[1] HATCH R,EULER H J．Comparison of Several AROF Kinematic Techniques[C]∥Proceedings of IEEE Symposium on Position,Location and Navigation．Salt Lake City: IEEE,1994:363-369．

[2] FREI E,BEUTLER G．Rapid Static Positioning Based on the Fast Ambiguity Resolution Approach“FARA”: Theory and First Results[J]．Manuscripta Geotaetica, 1990,15(4):325-356．

[3] 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．

[4] TEUNISSEN P J G．The Success Rate and Precision of GPS Ambiguity[J]．Journal of Geodesy,2000,74(3-4): 321-326．

[5] TEUNISSEN P J G,JONGE P D,TIBERIUS C C．The Least-squares Ambiguity Decorrelation Adjustment:Its Performance on Short GPS Baselines and Short Observation Spans[J]．Journal of Geodesy,1997,71(10):589-602．

[6] JONGE P D,TIBERIUS C．The LAMBDA Method for Integer Ambiguity Estimation:Implementation Aspects:LGR Series 12[R]．Delft:Delft University of Technology,1996．

[7] TEUNISSEN P J G．A New Method for Fast Carrier Phase Ambiguity Estimation[C]∥Proceedings of IEEE PLANS’94．Las Vegas:IEEE,1994:562-573．

[8] ZHOU Yangmei,LIU Jingnan,LIU Jiyu．Return-calculating LAMBDA Approach and Its Search Space[J]．Acta Geodaetica et Cartographica Sinca,2005,34(4):300-304．(周揚(yáng)眉,劉經(jīng)南,劉基余．回代解算的LAMBDA方法及其搜索空間[J]．測繪學(xué)報,2005,34(4):300-304．)

[9] RIZOS C,HAN S．A New Method for Constraining Multisatellite Ambiguity Combinations for Improved Ambiguity Resolution[C]∥Proceedings of ION:GPS-95．Palm Springs:ION,1995:1145-1153．

[10] LI Z,GAO Y．A Method for Construction of High Dimension Transformation Matrices in LAMBDA[J]．Geomatica, 1998,52:433-439．

[11] 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．

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

[13] GRAFAREND E．Mixed Integer-real Adjustment(IRA) Problems:GPS Initial Cycle Ambiguity Resolution by Means of the LLL Algorithm[J]．GPSSolution,2000,4(2):31-44．

[14] XU P．Random Simulation and GPS Decorrelation[J]．Journal of Geodesy,2001,75(7-8):408-423．

[15] LIU Zhiping,HE Xiufeng．An Improved LLL Algorithm for GPS Ambiguity Resolution[J]．Acta Geodaetica et Cartographica Sinca,2007,36(3):286-289．(劉志平,何秀鳳．改進(jìn)的GPS模糊度降相關(guān)LLL算法[J]．測繪學(xué)報,2007,36(3):286-289．)

[16] YANG Ronghua,HUA Xianghong,LI Zhao,et al．An Improves LLL Algorithm for GPS Ambiguity Solution[J]．Geomatics and Information Science of Wuhan University, 2010,35(1):21-24．(楊榮華,花向紅,李昭,等．GPS模糊度降相關(guān)LLL算法的一種改進(jìn)[J]．武漢大學(xué)學(xué)報:信息科學(xué)版,2010,35(1):21-24．)

[17] ZHANG Xianda．Matrix Analysis and Applications[M]．Beijing:Tsinghua University Press,2004．(張賢達(dá)．矩陣分析與應(yīng)用[M]．北京:清華大學(xué)出版社,2004．)

[18] ZHAO Tao,JIANG Jinrong．A Block Gram-Schmidt Algorithm with Its Application[J]．Journal of the Graduate School of the Academy of Sciences,2009,26(2):224-228．(趙韜,姜金榮．分塊Gram-Schmidt正交化算法及其應(yīng)用[J]．中國科學(xué)院研究生院學(xué)報,2009,26(2):224-228．)

[19] JALHY W,PHILIPPE B．Stability Analysis and Improvement of the Block Gram-Schmidt Algorithm[J]．SIAM Journal on Scientific and Statistical Computing,1991,12(5):1058-1073．[20] STATHOPOULOS A,WU K．A Block Orthogonalization Procedure with Constant Sysnchronization Requirements [J]．S SIAM Journal on Scientific and Statistical Computing, 2002,23(6):2165-2182．

[21] LIU Jingnan,YU Xingwang,ZHANG Xiaohong．GNSS Ambiguity Resolution Using the Lattice Theory[J]．Acta Geodaetica et Cartographica Sinca,2012,41(5):636-645．(劉經(jīng)南,于興旺,張小紅．基于格論的GNSS模糊度解算[J]．測繪學(xué)報,2012,41(5):636-645．)

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

[23] LIU Zhiping,HE Xiufeng,GUO Guangli,et al．Decorrelation Algorithms and Its Evaluation Indexes for GNSS Ambiguity Solution[J]．Geomatics and Information Science of Wuhan University,2011,36(3):257-261．(劉志平,何秀鳳,郭廣禮,等．GNSS降相關(guān)算法及其評價性指標(biāo)研究[J]．武漢大學(xué)學(xué)報:信息科學(xué)版,2011:36(3):257-261．)

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

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

Ambiguity Decorrelation with Integer Block Orthogonalization Algorithm

FAN Long1,ZHAI Guojun1,CHAI Hongzhou2
1．Naval Institute of Hydrographic Surveying and Charting,Tianjin 300061,China;2．Institute of Geospatial Information,Information Engineering University,Zhengzhou 450052,China

Since the round-off error affects the effect and the success rate of the down correlation along with the increase of the matrix’s dimension,the idea of block Gram-Schmidt orthogonalization is introduced,and the integer block Gram-Schmidt orthogonalization algorithm is designed,meanwhile,the IBGS-LLL decorrelation algorithm is proposed combined with the LLL algorithm．The decorrelation effect of different block style is analyzed with different dimension by using the random simulation method．It is confirmed the block manner of different measuring mode．Comparison of the IBGS-LLL algorithm with the improved LLL algorithm based on simulated and measured data shows that the IBGS-LLL decorrelation algorithm possessing has better effect and higher success rate of ambiguity decorrelation．

integer ambiguity;LLL decorrelation;integer block Gram-Schmidt orthogonalization

FAN Long(1984－),male,PhD,majors in GNSS precise positioning theory,algorithm and application．

P228

A

1001-1595(2014)08-0818-09

國家863計劃(2009AA121405);國家自然科學(xué)基金(41274045;61071006);國家重大科學(xué)儀器設(shè)備開發(fā)專項基金(2011YQ12004503);國家海洋局海底科學(xué)重點(diǎn)實驗室開放基金(KLSG1002)

2012-06-18

范龍(1984—),男,博士,研究方向為GNSS精密定位理論、算法與應(yīng)用。

E-mail:fl19841108＠gmail．com

FAN Long,ZHAI Guojun,CHAI Hongzhou．Ambiguity Decorrelation with Integer Block Orthogonalization Algorithm[J]．Acta Geodaetica et Cartographica Sinica,2014,43(8):818-826．(范龍,翟國君,柴洪洲．模糊度降相關(guān)的整數(shù)分塊正交化算法[J]．測繪學(xué)報,2014,43(8):818-826．)

10．13485/j．cnki．11-2089．2014．0094

修回日期:2013-11-07