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

張 鑫，崔曉偉，馮振明

（清華大學電子工程系，北京100084）

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

張 鑫，崔曉偉，馮振明

（清華大學電子工程系，北京100084）

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

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

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

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

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

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

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

1 數(shù)學模型

1.1 投影方程

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

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

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

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

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

1.2 經(jīng)典FDE算法

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

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

2）采用下式進行故障觀測量識別：

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

2 稀疏FDE算法

2.1 稀疏約束

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

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

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

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

2.2 稀疏求解方法

對于線性方程組的稀疏求解問題，難以給出解的閉合表達式.目前，Davis等[9-12]給出稀疏解的迭代搜索方法.在不同的使用環(huán)境（如線性方程規(guī)模、方程組特性、噪聲大小的不同）下，各種稀疏算法的性能不同.對于式（5）中的投影方程，通過仿真比較可知，文獻[12]所述的最小角度回歸（least angle regression，LARS）算法能夠兼顧求解準確性和運行速度，更適用于對衛(wèi)星導航中投影方程的稀疏求解.本文采用LARS算法對P（ε）進行優(yōu)化，搜索ε.使用LARS算法求解投影方程的實現(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)驗值λ=σ/3，其中σ為偽距測量值中熱噪聲的標準差.

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

3 仿真結(jié)果

3.1 仿真設(shè)置

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

3.2 評估方式

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

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

3.3 稀疏性仿真

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

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

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

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

4 結(jié) 語

在未來的地面導航應用中，可見的衛(wèi)星數(shù)量將迅速增多，而觀測量同時存在多個測距故障的可能性增大，這會降低定位結(jié)果的準確性.對于這種應用環(huán)境，本文對故障觀測量進行稀疏假設(shè)，提出使用稀疏算法求解偽距誤差向量的方法.利用偽距誤差向量修正初始定位結(jié)果，實現(xiàn)多故障觀測量存在下的魯棒定位.通過仿真分析，給出所提算法在不同可見衛(wèi)星總數(shù)下能夠有效處理的最大故障觀測量個數(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.浙江大學學報（工學版）網(wǎng)址：www.journals.zju.edu.cn/eng

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

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

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