張 鑫，崔曉偉，馮振明

（清華大學(xué)電子工程系，北京100084）

基于稀疏故障假設(shè)的魯棒定位方法

張 鑫，崔曉偉，馮振明

（清華大學(xué)電子工程系，北京100084）

為了使接收機(jī)在多個(gè)故障偽距存在時(shí)能夠提供魯棒的定位結(jié)果，提出基于稀疏假設(shè)的故障檢測與排除算法.該方法利用定位解算殘差與偽距誤差之間的映射關(guān)系，通過對故障觀測量的個(gè)數(shù)進(jìn)行稀疏約束，使用稀疏算法直接求解所有觀測量的偽距誤差.利用偽距誤差計(jì)算結(jié)果修正初始的定位結(jié)果，實(shí)現(xiàn)魯棒定位.在不同的可見衛(wèi)星數(shù)和不同的故障衛(wèi)星數(shù)下進(jìn)行仿真.仿真結(jié)果表明，當(dāng)可見衛(wèi)星數(shù)量較多時(shí)，使用該算法能夠?qū)Χ鄠€(gè)故障觀測量進(jìn)行有效的檢測，提升定位結(jié)果的準(zhǔn)確性.

多星故障；故障檢測；稀疏約束；魯棒定位

傳統(tǒng)的衛(wèi)星導(dǎo)航接收機(jī)在獲取足夠的衛(wèi)星位置和相應(yīng)的偽距測量信息后，使用最小二乘迭代方法計(jì)算用戶的三維位置和時(shí)間信息.通常情況下，偽距觀測量由用戶到衛(wèi)星之間的真實(shí)距離與接收機(jī)熱噪聲導(dǎo)致的測量誤差疊加而成.由于測量誤差服從零均值高斯分布，最終的定位結(jié)果服從高斯分布[1].定位結(jié)果的期望值位于用戶的真實(shí)位置.當(dāng)測量誤差的方差較小時(shí)，接收機(jī)具有較高的定位精度.

若某顆衛(wèi)星出現(xiàn)星鐘故障，或者該衛(wèi)星信號在傳播過程中受到干擾（如建筑物反射的多徑信號），則使用該顆衛(wèi)星提取的偽距觀測量的誤差將服從非零均值高斯分布.偽距觀測量誤差的均值稱為測距偏差或故障偏差.相應(yīng)地，該偽距觀測量稱為異常觀測量或故障觀測量.故障觀測量的存在使得定位結(jié)果的期望值偏離用戶真實(shí)位置，導(dǎo)致定位結(jié)果不可靠.為了解決該問題，接收機(jī)自主正直性監(jiān)測（RAIM）技術(shù)應(yīng)運(yùn)而生[2-3].RAIM技術(shù)中的故障檢測與排除（FDE）算法可以用于檢測故障觀測量并進(jìn)行剔除，提升定位的準(zhǔn)確性.

目前在RAIM技術(shù)中廣泛使用的FDE算法只可用于對單個(gè)故障觀測量的檢測與識別[3].隨著多個(gè)導(dǎo)航系統(tǒng)的建設(shè)，未來的導(dǎo)航接收機(jī)需要使用更多的可見衛(wèi)星進(jìn)行定位，以獲得更好的定位精度.導(dǎo)航應(yīng)用的普及使得接收機(jī)將面臨更惡劣的應(yīng)用環(huán)境，比如在高樓林立的城市中進(jìn)行定位.這使得多個(gè)故障觀測量同時(shí)出現(xiàn)的概率迅速提升.因此，F(xiàn)DE算法需要進(jìn)行改進(jìn)，以適用于可用衛(wèi)星數(shù)量大幅提升、非單一故障觀測量的使用場景.

與單故障FDE算法不同，在面對多個(gè)故障觀測量時(shí)，需要對所有衛(wèi)星的偽距觀測量的誤差進(jìn)行求解才可進(jìn)行故障檢測.由于問題的欠定性，偽距觀測量的誤差無法直接進(jìn)行求解.改進(jìn)FDE算法的核心思想是考慮如何引入冗余信息或約束條件來求解偽距誤差.目前已有的FDE改進(jìn)方法可以劃分如下.1）將故障分布作為約束條件.基于定位域的改進(jìn)FDE算法限定故障只能發(fā)生在一個(gè)導(dǎo)航系統(tǒng)中，然后對不同導(dǎo)航系統(tǒng)的定位結(jié)果進(jìn)行加權(quán)組合[4]，該算法的適用范圍較窄.2）將故障的不同組合方式作為冗余信息.基于分組檢測的FDE算法通過搜索故障的組合方式實(shí)現(xiàn)對多故障觀測量的檢測[5].隨著可見衛(wèi)星數(shù)的增加，可能的故障組合方式迅速增多，計(jì)算復(fù)雜度的大幅提升限制了該方法的使用.3）從時(shí)域引入冗余信息.聯(lián)合利用不同歷元時(shí)刻測距信息的FDE算法，利用衛(wèi)星結(jié)構(gòu)隨時(shí)間的變化特性構(gòu)造滿秩矩陣求解偽距誤差[6].受限于求解過程中由衛(wèi)星星座結(jié)構(gòu)引入的病態(tài)性，只能實(shí)現(xiàn)對故障偏差為幾百米到幾千米時(shí)的故障檢測，故障檢測能力有限.綜上所述，在多星多故障觀測量場景下，現(xiàn)有的FDE改進(jìn)算法都不能有效地給出對所有偽距誤差的估計(jì).

上述方法沒有充分考慮故障觀測量本身的結(jié)構(gòu)特性.若將接收機(jī)定位解算看成參數(shù)估計(jì)問題，則只有當(dāng)故障觀測量在所有觀測量中稀疏時(shí)，才有可能實(shí)現(xiàn)穩(wěn)健估計(jì).本文將故障觀測量的稀疏特性作為約束條件，構(gòu)造基于稀疏假設(shè)的FDE算法.在該約束條件下，故障觀測量的個(gè)數(shù)不預(yù)先設(shè)定，僅設(shè)定其與觀測量總數(shù)的比例關(guān)系，算法具有較強(qiáng)的靈活性.相比于現(xiàn)有算法，稀疏FDE算法的適用范圍廣，復(fù)雜度低且具有較好的故障檢測能力.仿真分析表明，使用該方法能夠有效地提升定位結(jié)果的準(zhǔn)確性.

1 數(shù)學(xué)模型

1.1 投影方程

定位解算方程的線性化模型可以表示為

式中：列向量x為迭代過程中的增量，包含三維位置和鐘差4個(gè)維度；n×1維列向量y為n個(gè)偽距觀測量和相應(yīng)的偽距預(yù)測值（使用定位結(jié)果反推得到的用戶與衛(wèi)星之間的距離）之間的差；H為n×4維幾何矩陣，由n顆可見衛(wèi)星相對于迭代過程中用戶估計(jì)位置的幾何布局決定；ε為偽距誤差向量，在定位解算中為未知量.

使用最小二乘方法求解式（1），可得

通過若干步迭代后，定位結(jié)果將收斂，即式（2）中的迭代增量xLS將趨于零.得到最終的幾何矩陣G=Hfinal和殘差向量r=yfinal.根據(jù)殘差向量的定義可知，幾何矩陣G和殘差向量r滿足

式中：S為投影矩陣，S=I-G（GTG）-1GT，S將ε映射為r.容易驗(yàn)證，S為冪等矩陣.

1.2 經(jīng)典FDE算法

在經(jīng)典FDE算法中，使用殘差向量構(gòu)造檢驗(yàn)統(tǒng)計(jì)量T=rTr.當(dāng)偽距觀測量中沒有測距故障時(shí)，殘差向量中的元素服從高斯分布.此時(shí)，檢驗(yàn)統(tǒng)計(jì)量T服從中心卡方分布.根據(jù)預(yù)定的虛警概率可以設(shè)定判決門限.當(dāng)T大于該門限時(shí)，判定偽距觀測量中含有故障觀測量.存在如下2種方式識別故障衛(wèi)星[3].

1）進(jìn)行子集搜索.當(dāng)有n顆衛(wèi)星可見時(shí)，從中選出n-1顆衛(wèi)星的觀測量重新進(jìn)行定位解算，并構(gòu)造檢驗(yàn)統(tǒng)計(jì)量進(jìn)行假設(shè)檢驗(yàn).若判決沒有故障觀測量，則認(rèn)為該n-1顆衛(wèi)星的觀測量中沒有異常，使用該組衛(wèi)星的觀測量得到最終的定位結(jié)果.可見，對于單星故障假設(shè)，使用該方法在最壞情況下需要進(jìn)行=n次嘗試，以覆蓋所有的故障模式.雖然該方法可以擴(kuò)展到多星故障檢測，但即使限定故障觀測量只有2個(gè)，為了覆蓋所有的故障組合模式，在最壞情況下需要嘗試=n（n-1）/2次，當(dāng)n較大時(shí)，計(jì)算復(fù)雜度難以達(dá)到實(shí)用需求.

2）采用下式進(jìn)行故障觀測量識別：

式中：ri為殘差向量的第i個(gè)元素，Sii為投影矩陣第i行第i列的元素，F(xiàn)SN為故障觀測量的編號.可見，根據(jù)式（4）能夠找到一顆故障衛(wèi)星，該方法的運(yùn)算量相對較小.在單星故障假設(shè)下，文獻(xiàn)[7]證明了上述2種方法的等價(jià)性.當(dāng)存在多個(gè)故障觀測量時(shí)，無法使用式（4）正確地識別故障衛(wèi)星，這是由式（3）中投影矩陣的不滿秩性導(dǎo)致的[8].

2 稀疏FDE算法

2.1 稀疏約束

式（3）中的投影變換給出了ε和r之間的映射關(guān)系.由于S為非滿秩矩陣，無法由殘差向量和投影矩陣直接求解出誤差向量.事實(shí)上，多星故障FDE算法的基本思想是通過引入冗余信息或約束條件，使得式（3）可解.利用計(jì)算得到的偽距誤差，修正初始的定位結(jié)果，實(shí)現(xiàn)魯棒定位.對于接收機(jī)的定位解算模塊，本質(zhì)是利用衛(wèi)星位置和偽距測量值作為觀測信息，對用戶的位置進(jìn)行估計(jì).只有當(dāng)觀測信息中的異常值較少時(shí)，才有可能實(shí)現(xiàn)穩(wěn)健估計(jì).對故障觀測量的個(gè)數(shù)進(jìn)行約束，并把該約束條件應(yīng)用于式（3）的求解.

對故障觀測量個(gè)數(shù)的約束并非限定于某個(gè)具體數(shù)值，而是假定故障觀測量的個(gè)數(shù)相比于觀測量的總數(shù)盡可能地少，即故障觀測量具有稀疏特性.在該約束條件下求解投影方程，式（3）重新表述如下：

式中：λ為拉格朗日乘子.式（3）的求解問題轉(zhuǎn)化為尋找ε，使得P（ε）最小，并將該向量作為式（3）的解，從而實(shí)現(xiàn)對偽距殘差向量的估計(jì).

該稀疏約束不預(yù)先設(shè)定故障觀測量的個(gè)數(shù)，只假定了故障觀測量個(gè)數(shù)與觀測量總數(shù)的比例關(guān)系.算法具有很強(qiáng)的靈活性.對于給定的觀測量總數(shù)，滿足稀疏假定的故障觀測量的個(gè)數(shù)上限將通過仿真結(jié)果給出.

2.2 稀疏求解方法

對于線性方程組的稀疏求解問題，難以給出解的閉合表達(dá)式.目前，Davis等[9-12]給出稀疏解的迭代搜索方法.在不同的使用環(huán)境（如線性方程規(guī)模、方程組特性、噪聲大小的不同）下，各種稀疏算法的性能不同.對于式（5）中的投影方程，通過仿真比較可知，文獻(xiàn)[12]所述的最小角度回歸（least angle regression，LARS）算法能夠兼顧求解準(zhǔn)確性和運(yùn)行速度，更適用于對衛(wèi)星導(dǎo)航中投影方程的稀疏求解.本文采用LARS算法對P（ε）進(jìn)行優(yōu)化，搜索ε.使用LARS算法求解投影方程的實(shí)現(xiàn)方法如下.

輸入?yún)?shù)：投影矩陣S，殘差向量r，拉格朗日乘子λ初始化：初始k=0，設(shè)定

●ε0=0；

●b0=r-Sε0=r；

●c0=STb0；

●λ0=maix|c0[j]|；

●初始解集Q0={j：c0[j]=|c0[j]|}

迭代：k增加1并依次執(zhí)行

●停止條件：如果λk-1＜λ，停止迭代，否則繼續(xù)執(zhí)行.

●更新εk=εk-1+γΔε，其中γ=+γj.

●更新解集Qk=Qk-1∪{j：γj=γ}.

●bk=r-Sεk.

●ck=STbk.

●λk=λk-1-γ.

輸出：在完成k次迭代后，輸出εk.

輸入?yún)?shù)為S、r和λ.其中投影矩陣和殘差向量可以在定位解算完成后得到，如式（3）所示.λ的選取與偽距觀測量的噪聲方差有關(guān).本文根據(jù)仿真測試，選用經(jīng)驗(yàn)值λ=σ/3，其中σ為偽距測量值中熱噪聲的標(biāo)準(zhǔn)差.

LARS算法執(zhí)行時(shí)，ε的初始值為全零向量.λ0設(shè)置為投影矩陣中各個(gè)列與殘差向量之間相關(guān)值的最大模值，最大模值對應(yīng)列的位置加入初始解集.此后，對解集按照“等角”方向搜索，即Δε的方向，從而使得解集中各個(gè)元素對應(yīng)的投影矩陣列向量與SΔε之間的相關(guān)值的模值全部相等.通過迭代更新εk和λk，直到λk小于預(yù)先設(shè)置的拉格朗日乘子λ，迭代完成.將此時(shí)的向量εk作為輸出結(jié)果，即為式（6）中ε的估計(jì)值.

3 仿真結(jié)果

3.1 仿真設(shè)置

采用IGS提供的多系統(tǒng)星歷文件①http：∥igs.org/mgex/.，仿真中使用GPS、GLONASS和BeiDou 3個(gè)導(dǎo)航系統(tǒng)的星歷數(shù)據(jù)，模擬衛(wèi)星的分布情況.在每個(gè)仿真時(shí)刻，根據(jù)星歷計(jì)算出所有衛(wèi)星的位置以及衛(wèi)星和用戶間的仰角，將仰角大于5°的衛(wèi)星設(shè)為可見星.衛(wèi)星偽距觀測量由衛(wèi)星到用戶的真實(shí)距離和噪聲疊加而成.通過隨機(jī)向某些偽距觀測量中加入偏差來模擬故障觀測量.仿真設(shè)置如下.仿真時(shí)間：72000 s（步長30 s）；使用衛(wèi)星數(shù)目：16，20，24（設(shè)定衛(wèi)星數(shù)目后，從所有可見衛(wèi)星中隨機(jī)選取衛(wèi)星）；熱噪聲標(biāo)準(zhǔn)差：1 m；添加故障個(gè)數(shù)：1～8（設(shè)定故障個(gè)數(shù)后，將故障隨機(jī)添加到偽距觀測量中）；添加故障大?。?150～150 m（為每個(gè)添加的故障隨機(jī)設(shè)定大?。?

3.2 評估方式

多星故障FDE算法的性能評估方式?jīng)]有統(tǒng)一的標(biāo)準(zhǔn).衛(wèi)星總數(shù)與分布、故障數(shù)量、故障偏差和故障分布形式設(shè)定、計(jì)算復(fù)雜度評估方式、檢測概率與虛警概率定義方法的不同，都會導(dǎo)致不同的評估結(jié)果.考慮到FDE算法的最終目的是得到準(zhǔn)確的定位結(jié)果，本文從定位準(zhǔn)確性角度對所提算法進(jìn)行評估.本文采用評估定位結(jié)果準(zhǔn)確性時(shí)常用的圓概率誤差（CEP）方式來檢驗(yàn)所提算法的性能.記錄每個(gè)仿真時(shí)刻的初始定位結(jié)果和使用稀疏FDE算法修正后的定位結(jié)果，將定位結(jié)果與真實(shí)位置進(jìn)行比較，進(jìn)行統(tǒng)計(jì)分析.對2組定位結(jié)果分別處理，按照水平方向和豎直方向，計(jì)算圓半徑r.使得以真實(shí)位置為圓心，r為半徑的圓包含98％的定位結(jié)果①通常CEP評估方式按照50％概率求解圓半徑，本文采用98％概率進(jìn)行計(jì)算，以獲得更精細(xì)的定位準(zhǔn)確性評估結(jié)果..圖1給出在不同衛(wèi)星總數(shù)下的仿真結(jié)果.圖中，Herr為水平方向的定位誤差，Nerr為故障觀測量個(gè)數(shù).

從圖1可以看出，使用本文方法對偽距誤差進(jìn)行估計(jì)并用其修正初始定位結(jié)果后，定位準(zhǔn)確性得到了明顯提升.由于本文方法對故障觀測量的個(gè)數(shù)進(jìn)行了稀疏假設(shè)，當(dāng)故障個(gè)數(shù)相比于觀測量總數(shù)較少時(shí)，獲得了明顯的定位性能改善.如圖1（c）所示，當(dāng)接收機(jī)有24顆可見衛(wèi)星可以用于定位時(shí)，若故障觀測量的總數(shù)不超過8，則在本文算法保障下98％的定位結(jié)果將位于距離真實(shí)位置5 m范圍之內(nèi).當(dāng)僅使用最小二乘方法定位時(shí)，則無法保證定位結(jié)果以較大概率出現(xiàn)在正確位置.

3.3 稀疏性仿真

圖1 稀疏FDE算法性能仿真Fig.1 Performance simulation of sparse FDE algorithm

為了探究該方法對故障觀測量稀疏性的要求，通過仿真方式進(jìn)行分析.首先設(shè)定判決門限，即對定位結(jié)果的準(zhǔn)確性要求.對于指定的觀測量總數(shù)n，如果故障觀測量個(gè)數(shù)k滿足：當(dāng)有k個(gè)故障時(shí)，使用稀疏算法能夠使98％的定位結(jié)果位于真實(shí)位置10 m的范圍內(nèi)；當(dāng)存在k+1個(gè)故障時(shí)，采用稀疏算法無法達(dá)到上述要求.稱k為使用n顆衛(wèi)星定位時(shí)的最大容忍故障數(shù).仿真的統(tǒng)計(jì)結(jié)果如圖2所示.圖中，Nerrm為最大故障數(shù).

圖2 使用n顆衛(wèi)星定位時(shí)的最大容忍故障數(shù)Fig.2 Maximum number of failure under n satellites

如圖2所示，當(dāng)使用16顆衛(wèi)星進(jìn)行定位解算時(shí)，采用稀疏FDE算法可以在故障觀測量個(gè)數(shù)≤4 時(shí)，對定位結(jié)果的準(zhǔn)確性進(jìn)行有效保障.此外，從圖2可以看出，隨著可用衛(wèi)星數(shù)目的增多，采用該方法能夠?qū)Ω嗟墓收嫌^測量進(jìn)行有效的檢測，從而實(shí)現(xiàn)多星多故障應(yīng)用場景下的魯棒定位.

4 結(jié) 語

在未來的地面導(dǎo)航應(yīng)用中，可見的衛(wèi)星數(shù)量將迅速增多，而觀測量同時(shí)存在多個(gè)測距故障的可能性增大，這會降低定位結(jié)果的準(zhǔn)確性.對于這種應(yīng)用環(huán)境，本文對故障觀測量進(jìn)行稀疏假設(shè)，提出使用稀疏算法求解偽距誤差向量的方法.利用偽距誤差向量修正初始定位結(jié)果，實(shí)現(xiàn)多故障觀測量存在下的魯棒定位.通過仿真分析，給出所提算法在不同可見衛(wèi)星總數(shù)下能夠有效處理的最大故障觀測量個(gè)數(shù)，從仿真角度揭示了算法在不同可見星數(shù)目下的可用性.

（

）：

[1]PARKINSON B W.Global positioning system[M].Washington DC，USA：American Institute of Aeronautics and Astronautics，1996.

[2]BROWN A，STURZA M.The effect of geometry on integrity monitoring performance[C]∥Proceedings of ION AM.Atlantic：ION，1990：121-129.

[3]LEE Y C，DYKE K，DECLEENE B.Summary of RTCA SC-159 GPSintegrity working group activities[J].Journal of the Institute of Navigation，1996，43（3）：307-362.

[4]LEE Y C，BRAFF R，F(xiàn)ERNOW J，et al.GPSand Galileo with RAIM or WAAS for vertical guided approaches [C]∥Proceedings of ION GNSS2005.Long Beach：[s.n.]，2005：1801-1825.

[5]SCHROTH G，RIPPL M，ENE A，et al.Enhancements of the range consensus algorithm（RANCO）[C]∥Proceedings of the21st International Technical Meeting of the Satellite Division of the Institute of Navigation.Savannah：ION，2008：93-103.

[6]MARTINI I，HEIN G W.An integrity monitoring technique for multiple failures detection[C]∥Position of IEEE/ION Plans.San Diego：ION，2006：450-467.

[7]OBER P B.Integrity prediction and monitoring of navigation systems[M].Leiden：Integricom Publishers，2003.

[8]MACABIAU C，GERFAULT B，NIKIFOROV I，et al.RAIM performance in presence of multiple range failures [C]∥Proceedings of the National Technical Meeting of the Institute of Navigation.San Diego：ION，2005：779-791.

[9]DAVIS G，MALLAT S，AVELLANEDA N.Adaptive greedy approximations[J].Journal of Constructive Approximation，1997，13（1）：57-98.

[10]DONOHO D L，ELAD M.On the stability of the basis pursuit in the presence of noise[J].Signal Processing，2006，86（3）：57-98.

[11]CHARTRAND R，YIN W.Iteratively reweighted algorithms for compressive sensing[C]∥ICASSP.Las Vegas：IEEE，2008：3869-3872.

[12]EFRON B，HASTIE T，JOHNSTONE I，et al.Least angle regression[J].Annals of Statistics，2004，32（2）：407-499.

Robust positioning technique based on sparse assumption

ZHANG Xin，CUI Xiao-wei，F(xiàn)ENG Zhen-ming

（Department of Electronic Engineering，Tsinghua University，Beijing100084，China）

A new fault detection and elimination algorithm based on sparse assumption was proposed in order to obtain robust positioning results when multiple blunders exist in pseudo-ranges.The algorithm can calculate the error for each range measurement under the sparse constraint on the number of blunders by applying the projection from range error to the residuals.The calculated errors were used to modify the primary positioning result，and the robust positioning result was obtained.Simulations were performed in various numbers of visible satellites as well as blunders.Results show the effectiveness of the proposed method to detect multiple blunders and the ability to improve the positioning accuracy when there are enough visible satellites.

multiple fault；fault detection；sparse constraint；robust positioning

TN 967

A

1008-973X（2015）10-1924-05

2014-01-24.浙江大學(xué)學(xué)報(bào)（工學(xué)版）網(wǎng)址：www.journals.zju.edu.cn/eng

國家自然科學(xué)基金聯(lián)合基金重點(diǎn)資助項(xiàng)目（U1333203）；中科院精密導(dǎo)航定位與定時(shí)技術(shù)重點(diǎn)實(shí)驗(yàn)室開放基金資助項(xiàng)目（2012PNTT12）.

張鑫（1987—），男，博士生，從事衛(wèi)星導(dǎo)航的研究.ORCID：0000-0002-4196-8793.E-mail：zhangxin08.bj@gmail.com

崔曉偉，男，副教授，博導(dǎo).ORCID：0000-0003-0545-7408.E-mail：cxw2005@tsinghua.edu.cn