基于稀疏故障假设的鲁棒定位方法

张 鑫，崔晓伟，冯振明

（清华大学电子工程系，北京100084）

基于稀疏故障假设的鲁棒定位方法

张 鑫，崔晓伟，冯振明

（清华大学电子工程系，北京100084）

为了使接收机在多个故障伪距存在时能够提供鲁棒的定位结果，提出基于稀疏假设的故障检测与排除算法.该方法利用定位解算残差与伪距误差之间的映射关系，通过对故障观测量的个数进行稀疏约束，使用稀疏算法直接求解所有观测量的伪距误差.利用伪距误差计算结果修正初始的定位结果，实现鲁棒定位.在不同的可见卫星数和不同的故障卫星数下进行仿真.仿真结果表明，当可见卫星数量较多时，使用该算法能够对多个故障观测量进行有效的检测，提升定位结果的准确性.

多星故障；故障检测；稀疏约束；鲁棒定位

传统的卫星导航接收机在获取足够的卫星位置和相应的伪距测量信息后，使用最小二乘迭代方法计算用户的三维位置和时间信息.通常情况下，伪距观测量由用户到卫星之间的真实距离与接收机热噪声导致的测量误差叠加而成.由于测量误差服从零均值高斯分布，最终的定位结果服从高斯分布[1].定位结果的期望值位于用户的真实位置.当测量误差的方差较小时，接收机具有较高的定位精度.

若某颗卫星出现星钟故障，或者该卫星信号在传播过程中受到干扰（如建筑物反射的多径信号），则使用该颗卫星提取的伪距观测量的误差将服从非零均值高斯分布.伪距观测量误差的均值称为测距偏差或故障偏差.相应地，该伪距观测量称为异常观测量或故障观测量.故障观测量的存在使得定位结果的期望值偏离用户真实位置，导致定位结果不可靠.为了解决该问题，接收机自主正直性监测（RAIM）技术应运而生[2-3].RAIM技术中的故障检测与排除（FDE）算法可以用于检测故障观测量并进行剔除，提升定位的准确性.

目前在RAIM技术中广泛使用的FDE算法只可用于对单个故障观测量的检测与识别[3].随着多个导航系统的建设，未来的导航接收机需要使用更多的可见卫星进行定位，以获得更好的定位精度.导航应用的普及使得接收机将面临更恶劣的应用环境，比如在高楼林立的城市中进行定位.这使得多个故障观测量同时出现的概率迅速提升.因此，FDE算法需要进行改进，以适用于可用卫星数量大幅提升、非单一故障观测量的使用场景.

与单故障FDE算法不同，在面对多个故障观测量时，需要对所有卫星的伪距观测量的误差进行求解才可进行故障检测.由于问题的欠定性，伪距观测量的误差无法直接进行求解.改进FDE算法的核心思想是考虑如何引入冗余信息或约束条件来求解伪距误差.目前已有的FDE改进方法可以划分如下.1）将故障分布作为约束条件.基于定位域的改进FDE算法限定故障只能发生在一个导航系统中，然后对不同导航系统的定位结果进行加权组合[4]，该算法的适用范围较窄.2）将故障的不同组合方式作为冗余信息.基于分组检测的FDE算法通过搜索故障的组合方式实现对多故障观测量的检测[5].随着可见卫星数的增加，可能的故障组合方式迅速增多，计算复杂度的大幅提升限制了该方法的使用.3）从时域引入冗余信息.联合利用不同历元时刻测距信息的FDE算法，利用卫星结构随时间的变化特性构造满秩矩阵求解伪距误差[6].受限于求解过程中由卫星星座结构引入的病态性，只能实现对故障偏差为几百米到几千米时的故障检测，故障检测能力有限.综上所述，在多星多故障观测量场景下，现有的FDE改进算法都不能有效地给出对所有伪距误差的估计.

上述方法没有充分考虑故障观测量本身的结构特性.若将接收机定位解算看成参数估计问题，则只有当故障观测量在所有观测量中稀疏时，才有可能实现稳健估计.本文将故障观测量的稀疏特性作为约束条件，构造基于稀疏假设的FDE算法.在该约束条件下，故障观测量的个数不预先设定，仅设定其与观测量总数的比例关系，算法具有较强的灵活性.相比于现有算法，稀疏FDE算法的适用范围广，复杂度低且具有较好的故障检测能力.仿真分析表明，使用该方法能够有效地提升定位结果的准确性.

1 数学模型

1.1 投影方程

定位解算方程的线性化模型可以表示为

式中：列向量x为迭代过程中的增量，包含三维位置和钟差4个维度；n×1维列向量y为n个伪距观测量和相应的伪距预测值（使用定位结果反推得到的用户与卫星之间的距离）之间的差；H为n×4维几何矩阵，由n颗可见卫星相对于迭代过程中用户估计位置的几何布局决定；ε为伪距误差向量，在定位解算中为未知量.

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

通过若干步迭代后，定位结果将收敛，即式（2）中的迭代增量xLS将趋于零.得到最终的几何矩阵G=Hfinal和残差向量r=yfinal.根据残差向量的定义可知，几何矩阵G和残差向量r满足

式中：S为投影矩阵，S=I-G（GTG）-1GT，S将ε映射为r.容易验证，S为幂等矩阵.

1.2 经典FDE算法

在经典FDE算法中，使用残差向量构造检验统计量T=rTr.当伪距观测量中没有测距故障时，残差向量中的元素服从高斯分布.此时，检验统计量T服从中心卡方分布.根据预定的虚警概率可以设定判决门限.当T大于该门限时，判定伪距观测量中含有故障观测量.存在如下2种方式识别故障卫星[3].

1）进行子集搜索.当有n颗卫星可见时，从中选出n-1颗卫星的观测量重新进行定位解算，并构造检验统计量进行假设检验.若判决没有故障观测量，则认为该n-1颗卫星的观测量中没有异常，使用该组卫星的观测量得到最终的定位结果.可见，对于单星故障假设，使用该方法在最坏情况下需要进行=n次尝试，以覆盖所有的故障模式.虽然该方法可以扩展到多星故障检测，但即使限定故障观测量只有2个，为了覆盖所有的故障组合模式，在最坏情况下需要尝试=n（n-1）/2次，当n较大时，计算复杂度难以达到实用需求.

2）采用下式进行故障观测量识别：

式中：ri为残差向量的第i个元素，Sii为投影矩阵第i行第i列的元素，FSN为故障观测量的编号.可见，根据式（4）能够找到一颗故障卫星，该方法的运算量相对较小.在单星故障假设下，文献[7]证明了上述2种方法的等价性.当存在多个故障观测量时，无法使用式（4）正确地识别故障卫星，这是由式（3）中投影矩阵的不满秩性导致的[8].

2 稀疏FDE算法

2.1 稀疏约束

式（3）中的投影变换给出了ε和r之间的映射关系.由于S为非满秩矩阵，无法由残差向量和投影矩阵直接求解出误差向量.事实上，多星故障FDE算法的基本思想是通过引入冗余信息或约束条件，使得式（3）可解.利用计算得到的伪距误差，修正初始的定位结果，实现鲁棒定位.对于接收机的定位解算模块，本质是利用卫星位置和伪距测量值作为观测信息，对用户的位置进行估计.只有当观测信息中的异常值较少时，才有可能实现稳健估计.对故障观测量的个数进行约束，并把该约束条件应用于式（3）的求解.

对故障观测量个数的约束并非限定于某个具体数值，而是假定故障观测量的个数相比于观测量的总数尽可能地少，即故障观测量具有稀疏特性.在该约束条件下求解投影方程，式（3）重新表述如下：

式中：λ为拉格朗日乘子.式（3）的求解问题转化为寻找ε，使得P（ε）最小，并将该向量作为式（3）的解，从而实现对伪距残差向量的估计.

该稀疏约束不预先设定故障观测量的个数，只假定了故障观测量个数与观测量总数的比例关系.算法具有很强的灵活性.对于给定的观测量总数，满足稀疏假定的故障观测量的个数上限将通过仿真结果给出.

2.2 稀疏求解方法

对于线性方程组的稀疏求解问题，难以给出解的闭合表达式.目前，Davis等[9-12]给出稀疏解的迭代搜索方法.在不同的使用环境（如线性方程规模、方程组特性、噪声大小的不同）下，各种稀疏算法的性能不同.对于式（5）中的投影方程，通过仿真比较可知，文献[12]所述的最小角度回归（least angle regression，LARS）算法能够兼顾求解准确性和运行速度，更适用于对卫星导航中投影方程的稀疏求解.本文采用LARS算法对P（ε）进行优化，搜索ε.使用LARS算法求解投影方程的实现方法如下.

输入参数：投影矩阵S，残差向量r，拉格朗日乘子λ初始化：初始k=0，设定

●ε0=0；

●b0=r-Sε0=r；

●c0=STb0；

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

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

迭代：k增加1并依次执行

●停止条件：如果λk-1＜λ，停止迭代，否则继续执行.

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

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

●bk=r-Sεk.

●ck=STbk.

●λk=λk-1-γ.

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

输入参数为S、r和λ.其中投影矩阵和残差向量可以在定位解算完成后得到，如式（3）所示.λ的选取与伪距观测量的噪声方差有关.本文根据仿真测试，选用经验值λ=σ/3，其中σ为伪距测量值中热噪声的标准差.

LARS算法执行时，ε的初始值为全零向量.λ0设置为投影矩阵中各个列与残差向量之间相关值的最大模值，最大模值对应列的位置加入初始解集.此后，对解集按照“等角”方向搜索，即Δε的方向，从而使得解集中各个元素对应的投影矩阵列向量与SΔε之间的相关值的模值全部相等.通过迭代更新εk和λk，直到λk小于预先设置的拉格朗日乘子λ，迭代完成.将此时的向量εk作为输出结果，即为式（6）中ε的估计值.

3 仿真结果

3.1 仿真设置

采用IGS提供的多系统星历文件①http：∥igs.org/mgex/.，仿真中使用GPS、GLONASS和BeiDou 3个导航系统的星历数据，模拟卫星的分布情况.在每个仿真时刻，根据星历计算出所有卫星的位置以及卫星和用户间的仰角，将仰角大于5°的卫星设为可见星.卫星伪距观测量由卫星到用户的真实距离和噪声叠加而成.通过随机向某些伪距观测量中加入偏差来模拟故障观测量.仿真设置如下.仿真时间：72000 s（步长30 s）；使用卫星数目：16，20，24（设定卫星数目后，从所有可见卫星中随机选取卫星）；热噪声标准差：1 m；添加故障个数：1～8（设定故障个数后，将故障随机添加到伪距观测量中）；添加故障大小：-150～150 m（为每个添加的故障随机设定大小）.

3.2 评估方式

多星故障FDE算法的性能评估方式没有统一的标准.卫星总数与分布、故障数量、故障偏差和故障分布形式设定、计算复杂度评估方式、检测概率与虚警概率定义方法的不同，都会导致不同的评估结果.考虑到FDE算法的最终目的是得到准确的定位结果，本文从定位准确性角度对所提算法进行评估.本文采用评估定位结果准确性时常用的圆概率误差（CEP）方式来检验所提算法的性能.记录每个仿真时刻的初始定位结果和使用稀疏FDE算法修正后的定位结果，将定位结果与真实位置进行比较，进行统计分析.对2组定位结果分别处理，按照水平方向和竖直方向，计算圆半径r.使得以真实位置为圆心，r为半径的圆包含98％的定位结果①通常CEP评估方式按照50％概率求解圆半径，本文采用98％概率进行计算，以获得更精细的定位准确性评估结果..图1给出在不同卫星总数下的仿真结果.图中，Herr为水平方向的定位误差，Nerr为故障观测量个数.

从图1可以看出，使用本文方法对伪距误差进行估计并用其修正初始定位结果后，定位准确性得到了明显提升.由于本文方法对故障观测量的个数进行了稀疏假设，当故障个数相比于观测量总数较少时，获得了明显的定位性能改善.如图1（c）所示，当接收机有24颗可见卫星可以用于定位时，若故障观测量的总数不超过8，则在本文算法保障下98％的定位结果将位于距离真实位置5 m范围之内.当仅使用最小二乘方法定位时，则无法保证定位结果以较大概率出现在正确位置.

3.3 稀疏性仿真

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

为了探究该方法对故障观测量稀疏性的要求，通过仿真方式进行分析.首先设定判决门限，即对定位结果的准确性要求.对于指定的观测量总数n，如果故障观测量个数k满足：当有k个故障时，使用稀疏算法能够使98％的定位结果位于真实位置10 m的范围内；当存在k+1个故障时，采用稀疏算法无法达到上述要求.称k为使用n颗卫星定位时的最大容忍故障数.仿真的统计结果如图2所示.图中，Nerrm为最大故障数.

图2 使用n颗卫星定位时的最大容忍故障数Fig.2 Maximum number of failure under n satellites

如图2所示，当使用16颗卫星进行定位解算时，采用稀疏FDE算法可以在故障观测量个数≤4 时，对定位结果的准确性进行有效保障.此外，从图2可以看出，随着可用卫星数目的增多，采用该方法能够对更多的故障观测量进行有效的检测，从而实现多星多故障应用场景下的鲁棒定位.

4 结 语

在未来的地面导航应用中，可见的卫星数量将迅速增多，而观测量同时存在多个测距故障的可能性增大，这会降低定位结果的准确性.对于这种应用环境，本文对故障观测量进行稀疏假设，提出使用稀疏算法求解伪距误差向量的方法.利用伪距误差向量修正初始定位结果，实现多故障观测量存在下的鲁棒定位.通过仿真分析，给出所提算法在不同可见卫星总数下能够有效处理的最大故障观测量个数，从仿真角度揭示了算法在不同可见星数目下的可用性.

（

）：

[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，FERNOW 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，FENG 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.浙江大学学报（工学版）网址：www.journals.zju.edu.cn/eng

国家自然科学基金联合基金重点资助项目（U1333203）；中科院精密导航定位与定时技术重点实验室开放基金资助项目（2012PNTT12）.

张鑫（1987—），男，博士生，从事卫星导航的研究.ORCID：0000-0002-4196-8793.E-mail：zhangxin08.bj@gmail.com

崔晓伟，男，副教授，博导.ORCID：0000-0003-0545-7408.E-mail：cxw2005@tsinghua.edu.cn