夏傳甲

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

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

夏傳甲

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

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

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

1 引言

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

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

2 整周模糊度的搜索空間

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

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

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

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

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

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

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

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

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

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

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

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

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

3 整周模糊度的搜索方式

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

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

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

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

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

4 搜索算法的可靠性分析

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

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

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

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

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

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

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

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

5 搜索算法的時(shí)效性分析

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

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

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

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

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

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

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

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

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

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

6 結(jié)語(yǔ)

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

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

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

3 劉大杰.全球定位系統(tǒng)的原理與數(shù)據(jù)處理［M］.上海：同濟(jì)大學(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］.測(cè)繪學(xué)院學(xué)報(bào)，2004，21(1)：11-13.

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

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

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

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

11 夏傳甲.GPS短基線整周模糊度搜索算法的研究與實(shí)現(xiàn)［D］.中國(guó)地震局地震研究所，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

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

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

P207

A