一种基于高度角和GDOP贡献值的改进型选星算法

摘 要：对卫星定位误差进行分析，探讨几种常用的选星算法，结合常用选星算法的优缺点及BDS_GPS双系统组合定位的特点，提出一种基于高度角和GDOP贡献值的改进型选星算法。结果表明，该算法在满足运算量较小要求的同时，能够达到较高的定位精度，满足双系统高精度定位的需求。

关键词关键词：卫星导航；选星算法；GDOP；高度角；双系统定位

DOIDOI：10.11907/rjdk.162014

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2016）008-0016-05

0 引言

21世纪初，国内外学者对选星算法的研究主要集中在单个卫星导航定位系统。单系统选星算法包括最小几何精度因子法、最大四面体体积法、最大正交投影法、综合法等[1]。近几年，随着四大卫星导航定位系统的逐渐完善，国内外对于选星算法的研究重心已逐渐由单系统转移到多系统[2]。随着多系统中可见卫星颗数的增加，在提高定位精度及系统稳定性的同时，也会使得定位解算的运算量大大增加。因此，需要考虑在保证一定定位精度时，尽可能减少运算量，而这就是选星所要解决的问题。文献[3]提出了一种组合定位系统的选星算法，先选取可见卫星中仰角最大的一颗卫星，然后利用最大四面体体积法选出其它三颗卫星，再通过简化GDOP的求解过程选出剩余卫星。文献[4]提出了一种基四选星算法，在通过经典四星选择算法选出多个接近最优的四颗卫星，它们组合后仍然是接近最优的。此外，还有基于高度角和方位角的快速选星算法[5]、基于遗传迭代的选星算法[6]以及一种新的基于加权行列式的选星算法[7]等。

这些算法均是在运算量和定位精度之间作一定的取舍，以满足特定应用场景的要求，但将这些算法应用于多系统的联合定位解算时，特别是现阶段对双系统联合定位研究中，运算量与定位精度仍然存在局限性。本文针对双系统联合定位的特点，提出一种适用于双系统联合定位的选星算法，该算法在保证定位精度的同时，可以有效减少解算运算量。

1 选星指标

1.1 定位误差分析

在实际运用中，接收机得到的用户位置、授时精度会受到许多因素的影响而产生一定偏差。定位误差的协方差矩阵：

A是系统的观测矩阵，R是观测误差的协方差矩阵。为了简化定位误差的理论分析，对观测误差的模型作了以下假设：

（1）假设接收机对各颗卫星的观测误差均呈相同的正态分布，且均值为0，方差为σ2UERE，该方差通常又称为用户等效距离误差（UERE）的方差，用户等效距离误差就是从卫星到用户接受机的各部分误差的综合，包括卫星钟差、卫星星历误差、大气层延时误差、多径效应误差等。

（2）假设接收机对不同卫星的观测量之间互不相关。@样，观测误差的协方差矩阵就是对角阵，具体形式如式（2）所示：

其中，I为一个N×N的单位阵，N表示参与解算的卫星的颗数。

在以上两个假设的基础上，可以对式（1）中定位误差的协方差矩阵作进一步简化：

设H=ATA-1，则矩阵H通常称为权系数阵在单系统中是一个4×4的对称阵，在双系统中则是一个5×5的对称阵，从式（3）中可以看出定位误差的方差是权系数阵与观测误差的方差的乘积。可见，卫星的定位精度与以下两个因素有关：

①观测误差：观测误差的方差σ2UERE越大，定位误差的方差就越大；

②卫星的几何分布：由于A是对卫星的观测矩阵，代表参与解算的各颗卫星的方向余弦，故矩阵H和矩阵A都取决于参与解算卫星的颗数与其相对于用户的几何分布。而H矩阵中的元素越小，那么其对于观测误差的放大程度就越小，从而定位误差就越小。

因此，要提高定位精度，需要从两个方面着手：一是降低对卫星的观测误差；二是改善卫星的几何分布。前者一般可以通过提高设备性能、建立数学模型来减小误差，下文将就如何改善卫星的几何分布具体分析。

1.2 GDOP分析

为了表示从观测误差到定位误差的放大倍数，人们提出了精度因子（DOP）这一概念，即在具有相同观测误差的条件下，精度因子越大会导致定位误差越大，而较小的精度因子会使定位误差变得更小。

精度因子可以从权系数阵H中得到，式（3）中等式左边是定位误差的协方差矩阵，而其对角线上的元素对应着各个定位误差分量上的误差，以单系统为例，即为σ2x、σ2y、σ2z和σ2δt，为便于分析，用hij表示权系数阵H的第i行第j列元素，因此hij就代表矩阵H的对角阵元素，其中i，j=1，2，3，4。那么，式（3）中等号左右矩阵对角元素的关系如式（4）所示：

则可以通过定位误差的协方差矩阵中的各定位误差分量之和与观测误差σ2UERE之比来确定精度因子。而几何精度因子（GDOP）作为最常用的参数，定义如下：

用tr（H）表示矩阵H的迹，则GDOP还可以表示为：

一定程度上，GDOP反映了定位的精度。而卫星的几何分布会直接影响对应的GDOP值的大小，进而影响到定位误差的大小。

在二维定位中，只要2颗卫星就能确定用户的位置，当然若考虑本地时钟的钟差则需要3颗卫星，为了方便分析、突出重点，假设本地时钟已足够精确。图1中有2组星座排列，每组星座包含2颗卫星，图中粗实线是以卫星为中心、以用户到该卫星的距离为半径的圆弧，而未知的距离观测误差在两条细圆弧线之间。用户接收机的真实位置位于两条粗圆弧线的交点，而阴影部分表示定位误差范围。图1（a）中，两颗卫星在用户接收机的观测矢量相互垂直，所以阴影部分的面积比较小而且集中；图1（b）中，两颗卫星在用户接收机的观测矢量之间夹角比较小，差不多是在用户的同一个方向，但是阴影部分的面积明显增大，定位误差范围增大，而且最大可能的定位误差变得非常大。可见，图1（a）中的卫星分布比图1（b）中的卫星分布要好。

在卫星三维定位中，卫星的几何分布与对应的GDOP的关系也遵循相似的规律。

由以上分析可知，卫星定位结果主要受观测误差和卫星几何分布两方面因素影响，其中卫星的几何分布越好，相应的GDOP越小，在同等条件下得到的定位结果就更准确、精度更高。因此保证参与解算卫星具有好的几何分布十分必要，故需要在定位解算之前进行选星，选出几何分布较好的一组可见卫星用于位置解算，而几何精度因子GDOP值的大小则可以作为选星的一个重要衡量标准。

2 选星算法

2.1 最佳几何精度因子法

根据几何精度因子（GDOP）的定义可知，在用户等效距离误差一定时，GDOP越小，定位误差也越小，故由此可以得出最直接的一种选星算法――最佳几何精度因子法。

设用户可见卫星颗数为N，其中用于解算的卫星颗数为m。那么最佳几何精度因子法可以分为以下两步：

（1）从N颗可见卫星中任选m颗卫星联立得到观测矩阵A，然后利用式（6）求出其几何精度因子GDOP的值，总共有CmN种卫星组合。

（2）在第一步中所有卫星组合中，筛选出一组GDOP最小的卫星作为参与定位的卫星组合。

最佳几何精度因子法总能选出在规定选星数目下GDOP最小的一组卫星，或称为在规定选星数目下几何分布最优的一组卫星，有利于提高定位精度。但是由于该算法本身的遍历特性，每种组合都需要计算一次GDOP，比如在10颗可见卫星中选择4颗卫星用于解算，那么有210种卫星组合，就需要计算210次GDOP。所以该算法的矩阵计算过多，计算量过大，不利于保证系统的实时性，同时也会消耗过多的资源。

2.2 基于高度角和方位角的快速选星法

高度角又称为仰角，是指用户所在位置到卫星位置的矢量在过用户所在位置的地球椭球切面上的投影与该矢量的夹角；方位角又称为幅角，是指该投影与切面上北坐标轴的夹角，取逆时针为正方向。所以，卫星的高度角和方位角都与用户接收机的位置有关。

单个卫星定位系统的观测矩阵可以表示为：

其中，lN、mN、nN表示第N颗定位卫星在以用户位置为原点的ENU坐标系中的方向向量，若设第N颗卫星的高度角为αN、方位角为βN，那么该方向向量又可以用卫星的高度角和方位角来分别表示：

因此，由式（6）、（7）和（8）可知卫星的高度角和方位角对定位系统的GDOP是有影响的，研究表明所选卫星组合中顶座星的高度角越大，对应的GDOP值越小，同时选择高度角越小作为底座星，对应的GDOP值也越小，并且当底座星之间方位角差大于60°时，对应的GDOP值较小[8]。鉴于卫星的高度角和方位角这一特性，有学者提出了基于高度角和方位角的快速选星算法，设选取m+n颗卫星作为用于定位的卫星，则该算法的具体步骤为：

（1）_定用于定位的卫星中顶座星和底座星的颗数，假设顶座星为m颗、底座星为n颗。

（2）计算所有可见卫星的高度角和方位角。

（3）将所有可见卫星按高度角从大到小排序，选择前m颗卫星作为顶座星，选择排在最后的卫星作为第一颗底座星。

（4）在第一颗底座星的方位角上分别加上360n、2×360n、…、n-1×360n，接着在剩余的卫星中选择这些方位角附近的n-1颗卫星，使得这些卫星的方位角与对应的标准角之间的差最小，同时保证这些卫星的高度角也尽可能小。

以上就是一种基于高度角和方位角的快速选星算法原理，该算法降低了选星计算的复杂程度，一定程度上提高了定位系统的实时性，但该算法第四步中基于方位角的选星并不能保证是最优的选择，同时也没有给出所使用的卫星高度角的详细计算方法。

2.3 最大多面体体积法

卫星的几何分布状态可以直接反映出相应GDOP的大小，位置集中的卫星组合所对应的GDOP值要大于位置相对分散的卫星组合所对应的GDOP值。也就是说以某卫星组合中的卫星为顶点构成的多面体体积越大，则该卫星组合的几何就越好，相应的GDOP值就越小。对于通过求解最大体积来选星的方法，许多学者都作了进一步研究，如有学者提出了一种基于多面体体积的BDS_GPS双系统的选星算法[9]，具体步骤为：

（1）计算卫星的坐标、高度角、方位角，并剔除高度角小于5°的卫星，可见星剩余n颗。

（2）在剩下的n颗可见卫星中选出高度角最大和高度最小的卫星作为所选的第一颗和第二颗卫星。

（3）在与第二颗卫星的方位角相差90°和180°的所有可见卫星中选择高度角最小的两颗卫星作为第三颗和第四颗卫星。

（4）以第一颗星为起点，除了第二颗卫星的n-2颗卫星为终点，构造n-2个向量，其中a1、b1分别表示终点为第三颗和第四颗卫星的向量，c1则是剩下n-4个向量中的一个。以第二颗星为起点，除了第一颗卫星的n-2颗卫星为终点，构造n-2个向量，其中a2，b2分别表示终点为第三颗和第四颗卫星的向量，c2则是剩下n-4个向量中的一个。根据式（9）计算每组卫星所组成的多面体体积V，选择使V最大对应的卫星为第五颗卫星。

以上即该算法的主要实现步骤，该算法也是在最大四面体体积法上作的拓展，使其在BDS_GPS双系统下可以运用，因此也具备传统最大四面体体积法的优点和缺点，但该算法没有说明卫星高度角和方位角的求解方法。

3 基于高度角和GDOP贡献值的改进型选星算法

3.1 改进型选星算法设计

虽然以上几种算法都有其选星依据，但总体来说都是围绕如何平衡GDOP值和运算量大小这一问题进行的，这些算法在应用于双系统联合定位时均存在定位精度低、稳定性差的问题。本文针对在BDS_GPS双模系统下的高精度定位状况，提出基于高度角和GDOP贡献值的改进型选星算法，使用计算可见卫星GDOP贡献度的方法来代替计算多面体体积，来提高算法的定位精度。其详细流程设计如图2所示。

城市中往往高楼林立、地面情况复杂，信号在传播过程中多径效应比较明显、信号衰落也较空旷地区明显很多。因此在本文的选星算法中，尽量在保证定位精度的条件下降低选星定位过程的运算量。而为了减少多径效应带来的噪声所造成的误差，在选星时首先要剔除可见卫星中高度角过低的卫星，一般卫星高度角的阈值设为5° 。

由前述对于卫星高度角的分析可知，参与定位卫星高度角的大小与卫星组合对应GDOP值的大小存在着很大的相关性，并且在卫星组合中处于最上面位置的卫星的高度角越大，对应的GDOP值越小，同时若处于最下面位置的卫星的高度角越小，对应的GDOP值也会越小[10]。可见，在最优的卫星组合中一般会包含高度角最大的卫星和高度角最小的卫星。所以，在剔除高度角过低和信号强度太弱的卫星后剩下的可见卫星中，选出高度角最大的卫星和高度角最小的卫星作为定位解算卫星组合中的第一颗和第二颗卫星。

在m颗定位卫星中第i颗卫星对m颗卫星组合整体的几何精度因子的贡献ΔGmi是一个正实数：

ΔGmi值越大表明去除第i颗卫星后的m-1颗卫星组合的GDOP值增大得就越多，也就说明卫星i对GDOPm的贡献越大。所以，接下来计算经前两步选星后剩余可见卫星组合中每颗卫星对该卫星组合对应GDOP值的贡献值，然后按照贡献值大小排序，选出贡献度最大的4颗卫星作为用于定位解算的卫星组合中的第三颗至第六颗卫星。

本算法中首先排除了部分受多径效应影响严重的观测卫星，减少了部分因定位数据源质量问题导致的误差，然后结合卫星高度角对于GDOP值的影响，以及不同卫星对于整个卫星组合GDOP值的贡献大小来完成选星。因此，本选星算法是一种基于卫星的高度角及其对可选卫星组合的GDOP贡献值的BDS_GPS双系统的选星算法。

3.2 改进型选星算法运算量分析

双系统联合定位时选星数目选为6颗，设可见卫星颗数为颗，则最佳GDOP选星算法需要求解C6N种卫星组合的GDOP值，并找出GDOP最小的一组卫星组合。根据式（6）可知，求解一次GDOP值需要进行一次矩阵乘法运算以及一次矩阵求逆运算，其中矩阵求逆的运算量一般要远大于矩阵乘法的运算量。

在本文所提出的改进选星算法中，首先需要计算剔除高度角过低的卫星后剩下的n（n≤N）颗星组合的权系数矩阵Hn，其中包括一次矩阵间乘法运算以及一次矩阵求逆运算，与计算一次GDOP值的运算量相当。然后计算n-2颗卫星的GDOP贡献值，只涉及矩阵乘法运算，其运算量会小于计算一次GDOP值的运算量。因此，本文的所提出的改进选星算法的运算量会小于计算n-1次GDOP值的运算量。

使用同一组静态采集的NovAtel OEM6格式的原始数据，分别对最小GDOP选星算法、本文改进的选星算法、最大多面体体积选星算法这3种算法的运算量和定位精度进行测试。其中最小GDOP选星算法的运算量测试结果如图3所示。图中的点表示在指定的可见卫星颗数中完成一次选星所消耗的时间。

可以看出，随着可见卫星颗数的增加，最小GDOP选星算法的耗时（即运算量）基本呈现指数增长趋势，与该算法的特征是一致的，表明测试环境以及测试数据是有效的。

本文改进选星算法与最大多面体体积选星算法的运算量测试结果如图4所示。可得到以下两点结论：

（1）本文改进选星算法和最大体积法，在可见卫星颗数相同条件下，它们的选星定位耗时都小于1毫秒，其运算量要远小于最佳GDOP法的运算量，在运算量上双系统实时定位的要求。

（2）本文改进选星算法的运算量要略大于最大体积法，其计算平均耗时比最大体积法耗时增加了22%。

根据GDOP的定义以及定位误差的协方差公式可知，当观测误差一定时，GDOP值越小，定位误差越小，定位精度越高。所以，通常通过GDOP值的大小来衡量选星定位的精度。

最小GDOP选星算法、本文改进的选星算法、最大多面体体积选星算法3种算法的定位精度（即参与定位解算卫星组合对应的GDOP值）测试结果如图5所示。其中GDOP值最小的曲线代表最小GDOP算法用于定位时GDOP值的变化，与该算法在相同条件下选星结果最优的特征相符。一方面进一步证明了该测试环境和测试数据的有效性；另一方面，表明最小GDOP选星算法的定位精度测试结果可以作为评价其它两种选星算法精度的标准，即越接近最小GDOP选星算法的GDOP曲线，表示该算法的精度越高。

将改进的选星算法以及最大多面体体积选星算法的GDOP值分别与对应的最小GDOP选星算法的GDOP值测试结果作差，结果如图6所示。其中横坐标表示定位的历元，纵坐标表示算法对应的GDOP值相比同一历元的最小GDOP选星算法的GDOP值的偏离程度。较低的曲线表示改进选星算法的GDOP值与最优的GDOP值之差，而较高曲线表示基于最大体积法的GDOP。

从图6可以看出，本文改进选星算法对应的GDOP差值都比较小，其中90%都在0.5以下。而且通过计算可知其GDOP偏差的均值为0.174，可见其定位精度十分接近最小GDOP法的定位精度。而最大多面体体积选星算法对应的GDOP差值则比较大，其偏差的均值为1.349，均方误差为1.658，可见该算法的结果不稳定，有些部分存在较大阶跃。这是因为该算法在确定第三颗和第四颗星时本身就具有很大的波动性，比如剩余可见卫星的都分布在与第二颗卫星的方位角相差小于90°的区域内，那么第四颗卫星就不会在与第二颗卫星的方位角相差180°的位置，进而最后选出的卫星组合的几何分布可能比较差。

综上所述，本文的改进选星算法在满足运算量较小要求的同时，能够达到较高的定位精度，满足双系统高精度定位的需求。

4 结语

本文分析了几种选星算法的优缺点，并对影响定位误差的各个因素进行了分析，结合BDS_GPS组合定位系统的特点以及常用选星算法的优缺点，提出了一种基于高度角和GDOP贡献值的改进型选星算法，并对该选星算法的定位精度与运算量进行了比较分析。结果表明，本文提出的改进算法可以有效改善定位运算量，提高定位精度。

参考文献：

[1]韩天祥.GNSS多系统选星策略的研究[D].上海：上海交通大学，2014.

[2]MA Z，YANG L，JIA X，et al.Optimal satellite selecting algorithm in GPS/BDS navigation system and Its implementation[M].Berlin Heidelberg：Springer，2015：117-127.

[3]黄继拯，刘红，赵艳，等.GPS/北斗的组合选星算法研究[J].舰船电子工程，2011，31（8）：81-83.

[4]杨蓝，王祖林，尚佳栋，等.卫星导航系统基四选星算法[J].电光与控制，2015（7）：61-65.

[5]LI W，ZHU L.A novel satellite selecting algorithm for BeiDou navigation satellite system[C].2015 International Conference，IEEE，2015：1-4.

[6]士君，李金金，刘卫，等.BD-2/GPS组合导航系统选星算法及定位分析[J].上海海事大学学报，2013，34（2）：1-4.

[7]田安红，付承彪，孔德剑.一种新的基于加权行列式的选星算法[J].弹箭与制导学报，2014，34（4）：155-157.

[8]胡小毛，刘飞，翁海娜.MSINS/GPS全组合系统可观测性分析[J].中国惯性技术学报，2011，19（1）：38-45.

[9]KONG JH，MAO X，LI S.BDS_GPS satellite selection algorithm based on polyhedron volumetric method[C].2014 IEEE/SICE International Symposium IEEE，2014：340-345.

[10]曹昌龙.北斗二代定位算法优化设计与应用[D].合肥：中国科学技术大学，2014.