夏傳甲

(中國地震局地震研究所，武漢 430071)

GPS整周模糊度搜索算法的可靠性和時效性比較*

夏傳甲

(中國地震局地震研究所，武漢 430071)

研究了GPS載波相位快速靜態(tài)定位中的整周模糊度搜索算法，對實數(shù)編碼的改進遺傳算法和LAMBDA算法進行了對比分析。算例表明：實數(shù)編碼的遺傳算法在搜索效率和可靠性方面和LAMBDA算法相當(dāng)。

整周模糊度;LAMBDA算法;遺傳算法;實數(shù)編碼;模糊度搜索

1 引言

GPS載波相位快速靜態(tài)定位的關(guān)鍵是整周模糊度的固定，這是近年來國內(nèi)外GPS研究中一個非常活躍的領(lǐng)域［1-5］。其核心問題就是整周模糊度搜索算法的可靠性和時效性。算法的可靠性關(guān)系到整周模糊度固定的正確與否，只有固定到正確的整周模糊度，才能將載波相位觀測值轉(zhuǎn)化為高精度的距離觀測值，進而獲得高精度的點位信息;算法的時效性關(guān)系到整周模糊度固定的效率，進而影響GPS快速靜態(tài)定位的效率，因而整周模糊度固定的可靠性和時效性決定了GPS快速靜態(tài)定位的精度和應(yīng)用范圍，具有重要意義［6-10］。

整周模糊度搜索算法的可靠性和時效性與搜索空間［6］及搜索方式［11］有關(guān)，搜索空間的構(gòu)造一定要保證搜索結(jié)果的可靠性，而搜索方式的選擇一定要兼顧搜索的效率，因此搜索空間的構(gòu)造和搜索方式的選擇是相互關(guān)聯(lián)的。本文研究了整周模糊度搜索算法的構(gòu)造空間和搜索方式，分析了其特點并加以分類。并以LAMBDA算法［4，5］和實數(shù)編碼的改進遺傳算法［11］為研究對象，對其可靠性和時效性做了對比分析。

2 整周模糊度的搜索空間

整周模糊度的固定是一個從實數(shù)解到整數(shù)解的映射過程，是多對一的映射模式，由于沒有確定的數(shù)學(xué)解析式來構(gòu)建實數(shù)解和整數(shù)解的關(guān)系，只能將候選值組合帶入目標(biāo)函數(shù)［1］，滿足條件的組合就是所求的整周模糊度。對于目標(biāo)函數(shù)而言，如果對整周模糊度的所有組合不限定條件，搜索的組合數(shù)將非常大，對搜索效率影響很大，因此需要對整周模糊度的組合加以限制，限制的過程就是構(gòu)造搜索空間的過程。構(gòu)造的搜索空間需要滿足兩個條件：

1)在搜索空間上的搜索等于在整個整數(shù)空間搜索，也就是說搜索空間必須包括滿足搜索準(zhǔn)則的那一組整周模糊度，這個條件決定了整周模糊度解算結(jié)果的可靠性。

2)搜索空間必須盡量的小，這個條件決定了整周模糊度搜索的效率。

顯然，搜索算法的可靠性與時效性是相矛盾的。對于每一個整周模糊度的浮點解，構(gòu)造整數(shù)空間［-d+d］，d是任意的大于零的整數(shù)，那么對于n個整周模糊度而言，就是一個以為中心的n維空間多面體，在滿足條件1)的前提下，搜索效率非常低。如果利用整周模糊度浮點解的協(xié)方差陣，則構(gòu)造搜索空間［-σ0qi，+σ0qi］，這是對n維空間多面體的限制，從n維空間變成有限的空間，縮小了搜索的范圍，在保證可靠性的前提下，提高了搜索的效率，因此從統(tǒng)計檢驗的角度出發(fā)，劃定搜索范圍是構(gòu)造搜索空間的一個辦法。在此基礎(chǔ)上，F(xiàn)ARA算法［1-3］通過兩兩模糊度參數(shù)的相容性檢驗，排除不可能的候選值組合，進一步限定搜索的空間，提高了搜索的效率。這種以整周模糊度浮點解為中心，根據(jù)置信區(qū)間構(gòu)造搜索范圍并利用整周模糊度參數(shù)間的相容性來加以限制的方法的思想在其他方法中得到了很多應(yīng)用，比如Cholesky分解法等;遺傳算法［6-10］以整周模糊度的浮點解和協(xié)方差陣條件，利用統(tǒng)計檢驗的方法確定整周模糊度的范圍，完成編碼工作，然后通過選擇，雜交和變異完成遺傳過程; FASF算法［1-3］中，每一個整周模糊度的搜索范圍的確定是在其左邊模糊度序列固定的基礎(chǔ)上平差得到的，也就是說FASF(Fast Ambiguity Search Filter)方法每固定一個整周模糊度，就要平差一次來固定下一個整周模糊度，平差得到整周模糊度的浮點解稱為條件估值，協(xié)方差稱為條件方差，此時以條件估值為中心，以條件方差來劃定置信區(qū)間形成搜索空間。

LAMBDA算法的思路和上述方法都不同。它不是從統(tǒng)計檢驗的角度構(gòu)造搜索空間，而是從目標(biāo)函數(shù)入手。它首先對目標(biāo)函數(shù)設(shè)定了合理的范圍，然后對目標(biāo)函數(shù)進行矩陣分解，得到條件估值和條件方差，形成以條件估值為中心，條件方差來確定半徑的搜索橢球，那么LAMBDA算法就將n維立體空間變成了搜索橢球，縮小了搜索的范圍，提高了搜索效率。

基于上面的分析，對基于模糊度域的搜索算法進行分類(表1)。

表1 基于搜索空間的搜索算法分類Tab.1 Classification of algorithms based on search space

以二維整周模糊度浮點解和協(xié)因數(shù)陣為例，分析了改進遺傳算法和LAMBDA算法在構(gòu)造空間上不同。

通過LAMBDA算法處理后得到(沒有進行降相關(guān)處理)：

圖1 改進的遺傳算法的搜索空間Fig.1 Search space of the improved genetic algorithm

圖2 LAMBDA算法構(gòu)造的搜索空間Fig.2 Search space of the LAMBDA

通過二維實例分析：以置信區(qū)間構(gòu)造的搜索空間是一個矩形，而從目標(biāo)函數(shù)出發(fā)構(gòu)造的搜索空間是一個橢圓。在參數(shù)估計中，一個n維的整周模糊度向量服從正態(tài)分布，以FARA算法為例，每一個整周模糊度的置信度為1-α，也就是取值正確的概率為P=1-α，假設(shè)整周模糊度之間的相關(guān)性為0，整周模糊度向量取值正確的概率為P=(1-α)n＜1，因此根據(jù)置信區(qū)間構(gòu)建的搜索空間取值正確的概率總小于1，但是改進遺傳算法的搜索成功率除了和初始種群有關(guān)，選擇雜交和變異也是重要的影響因子，并且遺傳過程是一個循環(huán)迭代的過程，所以取值正確的概率不是總小于1。

根據(jù)目標(biāo)函數(shù)構(gòu)建的搜索橢球的大小取決于χ2，只要χ2使得搜索橢球至少包含一個整周模糊度向量候選值，那么一定包含滿足目標(biāo)函數(shù)最小的組合，也就是說在搜索橢球的搜索等于在整數(shù)空間內(nèi)的搜索，取值正確的概率總等于1，因此χ2的選擇至關(guān)重要。

3 整周模糊度的搜索方式

在整周模糊度向量的搜索空間確定以后，只是得到了整周模糊度向量的候選值，此時整周模糊度向量的搜索變成了從整數(shù)空間到整數(shù)空間的多對一的映射關(guān)系，函數(shù)關(guān)系仍然沒有變化。

對于目標(biāo)函數(shù)而言，沒有確定的數(shù)學(xué)解析式，無法完成整周模糊度向量從整數(shù)空間到整數(shù)空間的多對一的映射。在FARA算法中，在確定整周模糊度向量的搜索范圍后，整周模糊度的候選值候選值將有sum＞mn個組合，將其逐一帶入目標(biāo)函數(shù)，滿足條件的組合就是所求的整周模糊度向量。在LAMBDA算法中，將目標(biāo)函數(shù)進行矩陣分解得到條件估值和條件方差，然后按照序貫條件平差得到整周模糊度向量的搜索范圍，從第n個整周模糊度的固定開始一直到第一個整周模糊度，前面的整周模糊度的選擇影響了后面的整周模糊度的搜索中心和搜索范圍，通過這種序貫方式滿足條件的組合就是所求的整周模糊度向量。在FASF算法中，從第一個整周模糊度開始，每固定一個整周模糊度后，帶回整數(shù)最小二乘估計中，得到新的整周模糊度向量的條件估值和條件方差，以條件估值為中心，條件方差為置信區(qū)間構(gòu)建搜索空間得到第二個整周模糊度的候選值，再固定第二個整周模糊度，以此類推通過這種回歸算法，滿足條件的組合就是所求的整周模糊度向量。

遺傳算法屬于人工智能的實現(xiàn)算法中的一種，它模仿生物優(yōu)勝劣汰的進化機制進行逐次，并行的迭代。遺傳算法經(jīng)過編碼和解碼過程，實際上是將由置信區(qū)間構(gòu)建的整周模糊度向量轉(zhuǎn)化為染色體，此時對整周模糊度的搜索實際上是對染色體上基因的選擇問題，然后通過選擇、雜交和變異等過程產(chǎn)生新的染色體，此時滿足評價標(biāo)準(zhǔn)的染色體就是所求的新一代，然后通過不斷地循環(huán)得到最終的染色體，經(jīng)過解碼后得到整周模糊度向量。

根據(jù)搜索方式對基于模糊度域的搜索算法進行了簡單的分類(表2)。

表2 基于搜索方式的搜索算法分類Tab.2 Classification of algorithms based on search pattern

4 搜索算法的可靠性分析

實驗數(shù)據(jù)來自于2010年4月9號在武漢地震計量檢定與測量工程中心采集的4個小時的采樣率是1 s的靜態(tài)觀測數(shù)據(jù)。數(shù)學(xué)模型采用短基線載波相位雙差定位模型，這種模型可以消除與距離有關(guān)的誤差項。實驗中比較了LAMBDA算法和實數(shù)編碼的改進遺傳算法的可靠性和時效性。

利用teqc對原始數(shù)據(jù)進行預(yù)處理，數(shù)據(jù)采樣率為10 s，衛(wèi)星高度角是15°，每隔10分鐘截取一段數(shù)據(jù)，每段數(shù)據(jù)取6個歷元為一小段進行計算。選用L1觀測值，總計40次，前24次共有7個衛(wèi)星對，后16次共有5個衛(wèi)星對(表3)。

由表3可知，LAMBDA算法和改進遺傳算法大部分都能固定整周模糊度，但是也有少數(shù)例外：

1)LAMBDA算法搜索到了橢球區(qū)間內(nèi)的錯誤的整周模糊度組合，這說明LAMBDA算法所采用的基于目標(biāo)函數(shù)構(gòu)建的搜索橢球沒有包含正確的整周模糊度組合，這也說明了雖然理論上在搜索橢球的搜索等于在整數(shù)空間內(nèi)的搜索，搜索成功的概率等于1，但是由于χ2設(shè)置問題，并不能保證搜索橢球一定包含正確的整周模糊度向量候選值，這就導(dǎo)致了LAMBDA算法固定了錯誤的整周模糊度組合。

2)改進的遺傳算法搜索到了置信區(qū)間內(nèi)的錯誤的整周模糊度組合，這表明在置信區(qū)間內(nèi)的搜索不等于在整數(shù)空間內(nèi)的搜索，F(xiàn)ARA算法，F(xiàn)ASF算法和遺傳算法的實例已經(jīng)說明了這點［11］。

3)當(dāng)衛(wèi)星數(shù)目發(fā)生變化時直接導(dǎo)致模糊度浮點解發(fā)生波動從而影響兩種算法不能固定整周模糊度。這主要是估計參數(shù)的精度受到觀測條件的影響，例如衛(wèi)星接收機幾何條件變化、觀測值類型、衛(wèi)星數(shù)目、采樣率等。

4)兩種算法的實驗對比來看，雖然LAMBDA算法從理論上來說優(yōu)于改進的遺傳算法，也就說在橢球內(nèi)的搜索優(yōu)于在置信區(qū)間內(nèi)的搜索，但是由于改進的遺傳算法是一種全局最優(yōu)化搜索算法，在編碼和搜索方式上的特點導(dǎo)致了和LAMBDA算法的搜索效果相當(dāng)。

表3 兩種算法處理結(jié)果對比Tab.3 Comparison between the results from two algorithms

5 搜索算法的時效性分析

利用teqc對原始數(shù)據(jù)進行預(yù)處理，數(shù)據(jù)采樣率為10 s，衛(wèi)星高度角為15°，參考衛(wèi)星為15，其余分別為18、21、22、24、26和27。利用單歷元模型，選用L1觀測值，總計50個歷元(表4和圖3)。

表4 兩種算法搜索時間的比較Tab.4 Comparison of search time between two algorithms

圖3 LAMBDA算法和改進遺傳算法搜索時間變化圖Fig.3 Search time of LAMBDA and an Improved algorithm based on real coding

根據(jù)實驗結(jié)果的統(tǒng)計分析，可以得出：

從搜索時間的統(tǒng)計意義上來看，LAMBDA算法和改進遺傳算所需時間相當(dāng)。

從搜索時間的穩(wěn)定性來看，LAMBDA算法的穩(wěn)定性稍好于改進的遺傳算法。

通過分析可以得到搜索算法的時效性受到下列因素的影響：

1)搜索算法的時效性與搜索空間的大小有關(guān)。對LAMBDA算法而言，經(jīng)過整周模糊度降相關(guān)處理后，其相關(guān)性被降低，條件數(shù)被減小。由目標(biāo)函數(shù)確定的橢球的大小取決于χ2，通過控制χ2的大小可以控制搜索橢球包含候選值的個數(shù)，所以LAMBDA算法的搜索時間大致相等，并且比較快;對于改進的遺傳算法而言，利用浮點數(shù)編碼使得所求的參數(shù)沒有增加，且占用計算機內(nèi)存少，并且在雜交過程中巧妙地利用雜交前后兩個整周模糊度向量之和不變，且子代的最值為父代取或的值，最小值為父代取與的值的特點，在這個最大最小范圍內(nèi)隨機產(chǎn)生一個子代，另一個子代則利用它們之和不變的性質(zhì)來確定，從而代替二進制中的雜交，提高了雜交過程的效率，所以改進的遺傳算法的搜索時間和LAMBDA算法相當(dāng)并且也比較穩(wěn)定。

基于以上分析，我們可以得到：基于目標(biāo)函數(shù)的Cholesky分解構(gòu)造搜索空間的LAMBDA算法，可以從整體上控制模糊度候選值的個數(shù)，從而使搜索時間保持穩(wěn)定的水平;基于置信區(qū)間的改進遺傳算法，雖然初始種群變化較大，但是利用浮點數(shù)編碼大大縮小參數(shù)個數(shù)，并且利用了雜交過程中特點使得搜索時間整體波動不大。

2)搜索算法的時效性與搜索方式有關(guān)。LAMBDA算法的搜索方式是序貫平差，前面的部分模糊度參數(shù)的選擇，通過參數(shù)估計直接影響了后面的模糊度參數(shù)的搜索范圍，這就是LAMBDA算法構(gòu)造的以條件參數(shù)為中心，由條件方差和決定大小的搜索橢球，條件參數(shù)的確定利用了模糊度參數(shù)間相關(guān)性，充分考慮了前面模糊度參數(shù)對后面模糊度參數(shù)的綜合影響，這樣使得搜索橢球的中心更加精確，同時條件方差和原始方差相比也大大減小。改進遺傳算法的搜索方式是人工智能，通過選擇，雜交和變異等遺傳過程形成下一代的種群，這是模仿生物優(yōu)勝劣汰的進化機制。這種搜索方法綜合考慮了各種因素，是一種優(yōu)化搜索方式，它不僅考慮了模糊度參數(shù)間的相關(guān)性，而且考慮了各種偶然因素，因此改進的遺傳算法和LAMBDA算法的執(zhí)行效果是相當(dāng)?shù)摹?/p>

6 結(jié)語

在函數(shù)模型和隨機模型相同時，不同的搜索方法可能得到不同的整周模糊度整數(shù)解。通過對搜索空間和搜索方式的分析得到：基于目標(biāo)函數(shù)構(gòu)建搜索空間的LAMBDA算法的可靠性優(yōu)于基于置信區(qū)間構(gòu)建搜索空間的FARA和FASF算法［6］，基于序貫方式的LAMBDA算法的時效性優(yōu)于基于逐一帶入方式的FARA算法和基于回歸方式的FASF算法［6］，而實數(shù)編碼的改進遺傳算法在可靠性和時效性方面和LAMBDA算法相當(dāng)，本文研究表明以目標(biāo)函數(shù)構(gòu)造搜索范圍的搜索算法的可靠性和時效性不一定優(yōu)于基于置信區(qū)間的搜索算法。

1 劉基余.GPS衛(wèi)星導(dǎo)航定位原理與方法［M］.北京：科學(xué)出版社，2006.

2 李征航.GPS測量與數(shù)據(jù)處理［M］.武漢：武漢大學(xué)出版社，2005.

3 劉大杰.全球定位系統(tǒng)的原理與數(shù)據(jù)處理［M］.上海：同濟大學(xué)大學(xué)出版社，2003.

4 Teunissen P J G.Theleast-squares ambiguity decorrel-ation adjustment：a method for fast GPS integer ambiguity estimation［J］.Journal of Geodesy，1995，70：65-82.

5 Jonge de，The LAMBDA method for integer ambiguity estimation：implementation aspects［J］.Delf Geodetic Computing CentreLGR Series，1996，(12)：562.

6 李淑慧，等.基于搜索空間構(gòu)造模糊度搜索方法的可靠性［J］.測繪學(xué)院學(xué)報，2004，21(1)：11-13.

7 劉智敏，等.遺傳算法解算GPS短基線整周模糊度的編碼方法研究［J］.武漢大學(xué)學(xué)報(信息科學(xué)版)，2006，31 (6)：607-610.

8 劉智敏，等.基于遺傳算法的高精度GPS相對定位解算研究［J］.測繪通報，2007，6：1-3.

9 劉智敏，等.基于遺傳算法的GPS單歷元單點定位方法研究［J］.武漢大學(xué)學(xué)報(信息科學(xué)版)，2007，32(1)：35 -38.

10 LiZuofa.Efficient ambiguity search using genetic algorithms［C］.ION GPS-95，California，1995.

11 夏傳甲.GPS短基線整周模糊度搜索算法的研究與實現(xiàn)［D］.中國地震局地震研究所，2011.

COMPARATIVE ANALYSIS OF RELIABILITY AND EFFICIENCY OF GPS AMBIGUITY ALGORITHM

Xia Chuanjia
(Institute of Seismology，CEA，Wuhan 430071)

The carrier phase ambiguity of GPS fast static positioning technique is studied，and the comparative analysis of LAMBDA and the improved real-coded genetic algorithm is made.The computation results show that the two algorithms have similar performance.

integer ambiguity;LAMBDA(Leact-squares Ambiguity Decorrection Adjustment)algorithm;genetic algorithm;real-coded;ambiguity search

1671-5942(2011)Supp.-0077-05

2011-01-26

國家自然科學(xué)基金(40974011);中國大陸構(gòu)造環(huán)境監(jiān)測網(wǎng)絡(luò)

夏傳甲，男，1984年生，碩士，主要研究方向為GPS算法的研究及其在大地測量學(xué)中的應(yīng)用.E-mail：xiachuanjia@163.com

P207

A