一種改進(jìn)的SEVB整數(shù)模糊度搜索算法

劉萬(wàn)科，馬立燁，盧立果，李建龍

1. 武漢大學(xué)測(cè)繪學(xué)院，湖北 武漢 430079； 2. 地球空間信息技術(shù)協(xié)同創(chuàng)新中心，湖北 武漢 430079； 3. 武漢大學(xué)地球空間環(huán)境與大地測(cè)量教育部重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430079； 4. 東華理工大學(xué)測(cè)繪工程學(xué)院，江西 南昌 330013

相位整周模糊度的快速、準(zhǔn)確解算是GNSS實(shí)時(shí)高精度定位的關(guān)鍵問(wèn)題，也是GNSS研究領(lǐng)域中的熱點(diǎn)問(wèn)題。在眾多整周模糊度解算方法中，基于整數(shù)最小二乘法(integer least squares，ILS)的搜索方法由于具有最高的成功率而被廣泛采用[1-5]。ILS搜索是指在給定空間內(nèi)尋找出滿足模糊度殘差二次型最小的一組整數(shù)解，為快速獲得該組整數(shù)解，目前最為流行的是基于震蕩式收縮策略的SEVB(Schnorr-Euchner and Viterbo-Biglieri)算法[6-9]。其中，震蕩式搜索策略是指從Bootstrap估計(jì)點(diǎn)開始向兩側(cè)呈“Z字型”枚舉[10]；收縮策略是指每獲得一組二次型更小的解，則進(jìn)行搜索空間的更新[11-12]。通過(guò)上述兩個(gè)策略，SEVB算法可以迅速減小搜索空間，從而減少搜索節(jié)點(diǎn)數(shù)，實(shí)現(xiàn)模糊度快速估計(jì)，因此該算法也被LAMBDA方法(V3.0)所采用。

采用SEVB算法處理時(shí)，首先將初始搜索空間設(shè)置為無(wú)窮大，以確保獲得的第一組整數(shù)候選解為Bootstrap估計(jì)解，然后基于該組整數(shù)解進(jìn)行搜索空間的收縮和震蕩式枚舉過(guò)程。但是當(dāng)模糊度解算精度較差時(shí)，Bootstrap成功率偏低，此時(shí)獲得的Bootstrap估計(jì)解偏離ILS估計(jì)解較多，求得的搜索空間相對(duì)偏大，需進(jìn)行多次枚舉才能實(shí)現(xiàn)搜索半徑的更新，導(dǎo)致搜索過(guò)程緩慢，耗時(shí)明顯增大。針對(duì)這一問(wèn)題，本文通過(guò)限制初始搜索空間大小和簡(jiǎn)化搜索算法實(shí)現(xiàn)過(guò)程兩個(gè)方面對(duì)SEVB算法進(jìn)行改進(jìn)，以期提高搜索效率。

1 模糊度解算的整數(shù)最小二乘模型

(1)

式中，a為模糊度最優(yōu)整數(shù)解。式(1)也被稱為整數(shù)最小二乘估計(jì)的目標(biāo)函數(shù)。

為加快整數(shù)最小二乘模糊度解算速度，通常需先進(jìn)行整數(shù)變換[13-20]。本文采用LAMBDA方法構(gòu)建整數(shù)變換矩陣Z，對(duì)模糊度解向量和方差陣變換過(guò)程如下

(2)

整數(shù)變換后，式(1)更新為

(3)

2 SEVB搜索算法

(4)

假設(shè)式(3)對(duì)應(yīng)的搜索空間大小為χ2，并考慮式(4)，則有

(5)

(6)

(7)

由式(6)和式(7)即可推導(dǎo)出模糊度搜索過(guò)程，從i=n處開始，有

(8)

由式(8)可知，SEVB算法采用深度優(yōu)先的方法逐層搜索，每一層內(nèi)的搜索區(qū)間大小取決于搜索空間χ2以及該層對(duì)應(yīng)的條件方差di。在第一次搜索時(shí)，χ2被設(shè)置為無(wú)窮大，從第n層到第1層進(jìn)行序貫取整得到第1個(gè)模糊度候選組(稱為Bootstrap估計(jì)解)，將該組解的目標(biāo)函數(shù)值F(z)作為新的搜索空間大小χ′2，之后在更新后的χ′2內(nèi)繼續(xù)搜索，若第1層仍有解則又得到一個(gè)候選組，若無(wú)解則返回第2層的下一個(gè)整數(shù)點(diǎn)。依此類推，每當(dāng)有新候選組的目標(biāo)函數(shù)值小于當(dāng)前空間大小χ′2時(shí)，則更新χ′2值，實(shí)現(xiàn)搜索空間的不斷收縮[6]。

(9)

式中，i為當(dāng)前的層數(shù)；[·]為取整符號(hào)。

由于搜索空間的大小可以不斷收縮，通常SEVB算法具有很高的搜索效率。但當(dāng)模糊度解算的精度較差時(shí)，Bootstrap估計(jì)解與ILS估計(jì)解偏差較大，造成第1次的搜索空間很大，需要多次重復(fù)不必要的節(jié)點(diǎn)枚舉才能將搜索空間縮小到較小的范圍內(nèi)，大大增加了搜索耗時(shí)。因此，本文從簡(jiǎn)化算法實(shí)現(xiàn)和限制初始搜索空間大小兩個(gè)方面對(duì)現(xiàn)有的SEVB算法進(jìn)行改進(jìn)。

3 改進(jìn)的SEVB搜索算法

針對(duì)現(xiàn)有SEVB算法存在的上述不足，本文在其基礎(chǔ)上進(jìn)行了優(yōu)化，增加了兩點(diǎn)改進(jìn)策略，改進(jìn)后的算法稱為MSEVB(Modified SEVB)。

3.1 改進(jìn)策略1

初始搜索空間不再設(shè)為無(wú)窮大，而是首先計(jì)算出一個(gè)空間較小的初值，該初值既要盡可能的小，又要保證搜索空間內(nèi)有整數(shù)解。初值計(jì)算方式分為兩種情形[21-22]：

(2) 如果ncands>n+1，使用橢球體積公式

(10)

式中，En為搜索橢球體積，并有近似關(guān)系intEn=ncands；|·|為取行列式值；Vn為體積函數(shù)，其計(jì)算公式為

(11)

則可得到初始空間大小

(12)

3.2 改進(jìn)策略2

現(xiàn)有SEVB算法采用下式計(jì)算序貫條件估值[6]

(13)

(14)

由式(13)可知，每次計(jì)算條件估值時(shí)均需對(duì)S(k,j),(j=1,2,…,k)重新計(jì)算，而當(dāng)搜索遇到死節(jié)點(diǎn)時(shí)(尤其是在搜索空間較大時(shí)，包含更多的死節(jié)點(diǎn)數(shù))，第1:k-1層的計(jì)算信息實(shí)際上是不必要的，即產(chǎn)生了計(jì)算冗余。改進(jìn)策略2通過(guò)將S(k,j),(j=1,2,…,k)轉(zhuǎn)換為計(jì)算S(k,k)，可以減少不必要的計(jì)算量，從而減少整體搜索耗時(shí)。改進(jìn)后的計(jì)算公式為

(15)

式中，kold為上一次節(jié)點(diǎn)枚舉時(shí)所在的層數(shù)。

綜上所述，MSEVB算法的計(jì)算步驟為：

(4) 當(dāng)重新返回到第n層時(shí)則整個(gè)搜索過(guò)程結(jié)束，最后一次得到的候選組即為最優(yōu)整數(shù)解。

4 試驗(yàn)驗(yàn)證

4.1 仿真分析

圖1 MSEVB算法流程Fig.1 The flow chart of MSEVB algorithm

搜索耗時(shí)的大小隨著模糊度解算精度的降低或模糊度維數(shù)的增加而增大，而模糊度解算精度可用整數(shù)序貫取整成功率Ps_ib來(lái)衡量，當(dāng)解算精度較高時(shí)Ps_ib值較大，反之亦然。Ps_ib定義如下[23-24]

(16)

因此設(shè)計(jì)了兩組試驗(yàn)分別從不同的角度進(jìn)行驗(yàn)證：第1組試驗(yàn)選取特定的模糊度維數(shù)，分析搜索耗時(shí)與Ps_ib的關(guān)系；第2組試驗(yàn)選取特定的Ps_ib，分析搜索耗時(shí)與模糊度維數(shù)的關(guān)系。為提高搜索效率，在執(zhí)行搜索過(guò)程之前都進(jìn)行了相同的降相關(guān)處理。

試驗(yàn)環(huán)境為：基于聯(lián)想電腦(Intel Core i7-3520 CPU，2.90 GHz，4 GB內(nèi)存，Win7系統(tǒng))和MATLAB 2012b軟件進(jìn)行。

4.1.1 試驗(yàn)1

試驗(yàn)1分別采用20、30、40、50維共4組數(shù)據(jù)，檢驗(yàn)SEVB算法和MSEVB算法的搜索耗時(shí)隨Ps_ib變化的關(guān)系。其中Ps_ib的大小可通過(guò)對(duì)方差協(xié)方差陣乘以一個(gè)比例因子來(lái)控制[25]

(17)

由圖2可見，MSEVB和SEVB兩種算法解算耗時(shí)隨著Ps_ib的降低，搜索耗時(shí)逐漸增大，且在較高維時(shí)呈近似于指數(shù)增加的趨勢(shì)；而MSEVB解算效率高于SEVB算法，尤其是在低成功率下具有更加顯著的計(jì)算優(yōu)勢(shì)。該結(jié)果表明，通過(guò)限制初始空間大小(策略1)和優(yōu)化節(jié)點(diǎn)計(jì)算過(guò)程(策略2)可以有效地減少冗余計(jì)算步驟，降低模糊度搜索過(guò)程中的計(jì)算復(fù)雜度，進(jìn)而減少計(jì)算耗時(shí)。

4.1.2 試驗(yàn)2

試驗(yàn)2采用5～50維的模糊度數(shù)據(jù)，并控制Ps_ib取1、0.8、0.6、0.4等4種情況，以進(jìn)一步比較不同維數(shù)下兩種搜索算法的計(jì)算耗時(shí)。每個(gè)維數(shù)下均隨機(jī)生成1000組樣本并進(jìn)行搜索，分別計(jì)算兩種搜索算法的平均耗時(shí)大小，結(jié)果如圖3所示(其中5～20維時(shí)兩種算法圖像基本重合，增加小圖對(duì)該區(qū)域進(jìn)行突出放大)。

圖3為4種不同的Ps_ib情形下，SEVB和MSEVB算法在不同維數(shù)下的平均搜索耗時(shí)變化趨勢(shì)圖。如圖所示，隨著模糊度維數(shù)增加，兩種搜索算法的耗時(shí)整體上呈增大趨勢(shì)，其中SEVB算法耗時(shí)增長(zhǎng)十分迅速且波動(dòng)較大，而MSEVB算法增長(zhǎng)相對(duì)緩慢且更為平穩(wěn)，整體上具有良好的計(jì)算穩(wěn)定性。

綜合圖2和圖3的結(jié)果可知，當(dāng)模糊度解算維數(shù)較高(20維以上)且對(duì)應(yīng)的Ps_ib較低時(shí)，采用常規(guī)的SEVB算法通常需要較多的解算耗時(shí)，此時(shí)MSEVB可以有效地減少模糊度的搜索耗時(shí)，提高模糊度解算效率。

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

(18)

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

模糊度維數(shù)和ADOP值如圖4所示，可以看到模糊度維數(shù)基本在35維以上，ADOP值在0.1左右。

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

由圖5可以看出，在以上4種情形下，MSEVB算法的耗時(shí)均明顯小于SEVB算法，即使當(dāng)解算精度較高時(shí)(Ps_ib=1)MSEVB的整體耗時(shí)也低于SEVB。此外，從圖中可以看到，隨著解算精度降低，SEVB算法的耗時(shí)波動(dòng)范圍越來(lái)越大，而MSEVB算法的整體耗時(shí)波動(dòng)較小，總能維持在較小的范圍內(nèi)，具有更好的穩(wěn)定性。

圖6反映了Ps_ib=0.4情形下SEVB和MSEVB耗時(shí)的概率分布情況?？梢钥吹?，SEVB靠中心右側(cè)的部分較多，而MSEVB靠中心右側(cè)的部分較少，主要集中分布在左側(cè)，且其中心相比于SEVB更小，從另一個(gè)角度展現(xiàn)出MSEVB算法具有更高穩(wěn)定性以及更少的搜索耗時(shí)。

表2統(tǒng)計(jì)了不同Ps_ib下兩種算法在全部歷元內(nèi)的平均及最大搜索耗時(shí)，最后一列“promote”反映了MSEVB算法相比于SEVB算法的提升效率。可以看到在不同解算精度下MSEVB平均耗時(shí)均小于SEVB，且隨精度降低MSEVB耗時(shí)增長(zhǎng)較為緩慢，而SEVB算法耗時(shí)增長(zhǎng)較為明顯，因此Ps_ib越小則MSEVB算法的性能提升越明顯，Ps_ib=0.4時(shí)平均搜索效率可提升33.18%。

表2 兩種算法的搜索耗時(shí)

5 結(jié) 論

現(xiàn)有的SEVB算法在浮點(diǎn)模糊度精度較差時(shí)，由于初始空間設(shè)定為無(wú)窮大，所得到的模糊度初始估計(jì)候選組(Bootstrap估計(jì)解)偏離真值較大，導(dǎo)致模糊度搜索空間難以有效地收縮，且空間內(nèi)包含較多的死節(jié)點(diǎn)造成冗余計(jì)算較多(見式(13))，致使搜索耗時(shí)較大，影響了整周模糊度的整體解算效率。

圖2 不同精度下SEVB及MSEVB算法平均搜索耗時(shí)變化趨勢(shì)圖Fig.2 The trend chart of SEVB and MSEVB average search time under different Ps_ib

圖3 不同維數(shù)下SEVB及MSEVB算法平均搜索耗時(shí)變化趨勢(shì)圖Fig.3 The trend chart of SEVB and MSEVB average search time under different dimensions

圖5 不同精度下SEVB及MSEVB算法平均搜索耗時(shí)隨歷元變化趨勢(shì)圖Fig.5 The trend chart of SEVB and MSEVB average search time under different Ps_ib and epochs

圖4 不同歷元下的模糊度維數(shù)和ADOP值Fig.4 Ambiguity dimensions and ADOP under different epochs

圖6 SEVB及MSEVB算法的耗時(shí)概率分布圖Fig.6 Probability distribution of SEVB and MSEVB search time

針對(duì)這一問(wèn)題，本文在SEVB算法基礎(chǔ)上，從限制初始空間大小和優(yōu)化分層節(jié)點(diǎn)計(jì)算過(guò)程兩個(gè)方面開展了算法改進(jìn)，提出了一種改進(jìn)的SEVB搜索算法(MSEVB算法)。分別基于仿真數(shù)據(jù)和動(dòng)態(tài)車載實(shí)測(cè)數(shù)據(jù)從不同角度對(duì)MSEVB算法進(jìn)行了效果驗(yàn)證與分析，得到以下結(jié)論：

(1) 對(duì)于確定的模糊度維數(shù)來(lái)說(shuō)，隨著模糊度精度的降低，相應(yīng)的成功率Ps_ib減小，SEVB算法的搜索耗時(shí)顯著增加，而改進(jìn)的MSEVB算法耗時(shí)增長(zhǎng)較小，因而具有更高的搜索效率，且Ps_ib越小，MSEVB算法的性能提升效果越明顯。

(2) 在相同的模糊度解算精度下，隨著模糊度維數(shù)的增加，MSEVB算法相比于SEVB算法的耗時(shí)增長(zhǎng)更加平緩且波動(dòng)更小，維數(shù)越高，改進(jìn)算法的解算優(yōu)勢(shì)越明顯。

綜上所述，本文的MSEVB算法是基于現(xiàn)有的SEVB算法發(fā)展而來(lái)的，是對(duì)SEVB算法的完善，不僅在低精度、高維模糊度的搜索方面具有更為明顯的效率優(yōu)勢(shì)，而且可以整體上保證模糊度解算效率相對(duì)更加可靠穩(wěn)定。

[1] ABIDIN H Z. On the Construction of the Ambiguity Searching Space for on-the-fly Ambiguity Resolution[J]. Navigation, 1993, 40(3): 321-338.

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

[3] EULER H J, LANDAU H. Fast GPS Ambiguity Resolution on-the-fly for Real-time Application[C]∥Proceedings of the 6th International Geodetic Symposium on Satellite Positioning. Columbus, Ohio: [s.n.], 1992: 650-659.

[4] CHEN Dingsheng. Development of a Fast Ambiguity Search Filtering (FASF) Method for GPS Carrier Phase Ambiguity Resolution[D]. Calgary, Alberta: University of Calgary, 1994.

[5] 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.

[6] 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.

[7] LI Bofeng, VERHAGEN S, TEUNISSEN P J G. GNSS Integer Ambiguity Estimation and Evaluation: LAMBDA and Ps-LAMBDA[M]∥SUN Jiadong, JIAO Wenhai, WU Haitao, et al. China Satellite Navigation Conference (CSNC) 2013 Proceedings. Berlin Heidelberg: Springer, 2013: 291-301.

[8] XU Peiliang, SHI Chuang, LIU Jingnan. Integer Estimation Methods for GPS Ambiguity Resolution: An Applications Oriented Review and Improvement[J]. Survey Review, 2012, 44(324): 59-71.

[9] 于興旺. 多頻GNSS精密定位理論與方法研究[D]. 武漢: 武漢大學(xué), 2011. YU Xingwang. Multi-frequency GNSS Precise Positioning Theory and Method Research[D]. Wuhan: Wuhan University, 2011.

[10] SCHNORR C P, EUCHNER M. Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems[J]. Mathematical Programming, 1994, 66(1-3): 181-199.

[11] VITERBO E, BIGLIERI E. A Universal Decoding Algorithm for Lattice Codes[C]∥Proceedings of Colloques Sur le Traitement du Signal et des Images. Juan-les-Pins: GRETSI, Groupe d’Etudes du Traitement du Signal et des Images, 1993: 611-614.

[12] VITERBO E, BOUTROS J. A Universal Lattice Code Decoder for Fading Channels[J]. IEEE Transactions on Information Theory, 1999, 45(5): 1639-1642.

[13] 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.

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

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

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

[17] 周揚(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.

[18] 劉寧, 熊永良, 馮威, 等. 單頻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.

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

[20] 劉萬(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.

[21] TEUNISSEN P J G, De JONGE P J, TIBERIUS C C J M. The Volume of the GPS Ambiguity Search Space and Its Relevance for Integer Ambiguity Resolution[C]∥Proceedings of the 9th International Technical Meeting of the Satellite Division of the Institute of Navigation (ION GPS 1996). Kansas:[s.n.], 1996: 889-898.

[22] JONGE De P, TIBERIUS C C J M. The LAMBDA Method for Integer Ambiguity Estimation: Implementation Aspects[M]. Delft: Delft Geodetic Computing Centre, 1996: 1-47.

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

[24] TEUNISSEN P J G. An Optimality Property of the Integer Least-squares Estimator[J]. Journal of Geodesy, 1999, 73(11): 587-593.

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

[26] 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.

[27] TEUNISSEN P J G, ODIJK D. Ambiguity Dilution of Precision: Definition, Properties and Application[C]∥Proceedings of the 10th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GPS 1997). Kansas City: [s.n.], 1997: 891-899.