基于一种不规则三角网的卫星导航选星算法研究

李克昭，王宁，魏金本，石俊鹏

(1.河南理工大学 测绘与国土信息工程学院，河南 焦作 454000；2.北斗导航应用技术协同创新中心，河南 郑州 450052；3.郑州信大先进技术研究院，河南 郑州 450052)

0 引 言

2018年12月27日下午，北斗卫星导航系统管理办公室宣布北斗三号基本系统建成，开始提供全球服务[1]。截至目前，地面测站可接收的北斗/GNSS可见星数量为30颗左右。当GPS/GLONASS现代化完成，及北斗三号和Galileo系统完全建成后，近地空间目标导航的可见星数量将增至40～50颗[2-4]。若可见星全部参与解算，将导致数据处理难度大、导航时效低。如何既保证导航定位解算精度，又保证其解算速率和稳定性，是未来多系统卫星导航定位首要解决的关键问题之一[5-6]。

最大多面体体积法、行列式最小法等[7-10]是当前选星的主要算法。ZHANG M等[11]给出了最大四面体体积选星算法严格的数学证明，但对于5星、6星，甚至更多的可见星，无法给出严密的数学证明；汪文雯等[12]通过固定若干颗卫星位置进行仿真试验,认为最大多面体体积选星算法在多星定位时存在着不可用的情况;WEI M等[13]认为最大多面体体积选星算法依然可作为选星准则。但是，当可见卫星数量达到40～50颗时，若其观测星全部参与导航定位解算将降低计算速度，并且容易造成矩阵维数灾难而使程序崩溃。但如果只选其中4颗卫星，将其余数据抛弃，也会造成有效观测数据浪费，不利于进一步改善导航定位精度和可靠性能。

针对多系统多可见导航卫星的导航定位问题，本文提出了一种基于不规则三角网进行分割多面体的等效评价方法，并利用实测数据进行计算，验证了该等效评价方法的正确性，可为多系统多可见星的选星问题提供思路和方法。

1 基于不规则三角网的多面体体积选星方法

1.1 空间几何精度指标GDOP

实践证明，除空间导航卫星、接收机硬件精度指标及观测信号传播路径等外部因素外，可见导航星的空间几何分布是决定导航定位精度的另外一个重要因素。GDOP是评价导航星空间几何分布的精度指标。因此，下面给出GDOP值的计算公式，并给出其与导航定位精度的关系。

参考文献[14]给出GNSS伪距观测方程，即

(1)

其中，

(Ys(t)-Yi)2+(Zs(t)-Zi)2]1/2，

(2)

当GNSS接收机追踪到的卫星数量大于4，观测历元个数为nτ时，误差矩阵方程为

(3)

(4)

由GDOP定义可推出GDOP与多面体体积V之间的关系：

(5)

(6)

再由四面体体积与行列式间的关系得

(7)

式中，V为4颗定位卫星与用户之间的单位矢量端点所构成的四面体体积。

由式(6)～(7)得

(8)

由式(8)可知，利用体积V与行列式的关系，可以避免复杂的矩阵运算。

GNSS系统中，定位精度可用观测精度和几何精度因子的乘积表示，即

σA=δ0·GDOP，

(9)

由几何精度因子的定义可以看出，当观测精度δ0确定时，几何精度因子越小，定位精度越高。

1.2 基于不规则三角网的多面体体积计算

计算参与解算的可见导航星所构成的多面体体积是最大多面体体积选星法的首要问题。GNSS系统卫星数量大量增加，使可视卫星构成的网线更加密集。利用不规则三角网中的Delaunay三角网特性，即“最小角最大化”和“任意三角形不共面”特性，可使构成的三角网唯一。文献[15-18]证明了基于最大多面体体积法与GDOP值的相关性，基于此，基于Delaunay三角网构建最大多面体体积选星法的思路为：首先，以测站点为原点建立一个空间直角坐标系，将卫星至测站点的距离单位化，以便多面体体积的计算；然后，在选取的可见卫星中挑选出高度角最大的卫星作为“种子星”，将剩余卫星投影到XOY平面上；其次,利用这些投影点生成Delaunay三角网，将Delaunay三角网中每个三角形顶点代表的卫星分别与“种子星”组成四面体，构成对应的Hamilon通路；最后,将所有四面体体积相加，得到选取的可见星所构成的多面体体积。

如图1所示，假设在某个历元有6颗可见卫星A，B，C，D，E，F。将高度角最大的卫星A作为“种子星”,然后将剩余卫星投影到XOY平面上，得B′，C′，D′，E′，F′点，将投影点构成Delaunay三角网，得三角形B′E′F′，三角形B′E′D′和三角形C′D′E′，进而得到四面体ABEF，ABED和ACDE，这样，就将多面体ABDCEF的体积求解问题转化为易求解的3个四面体体积之和的问题。

图1 卫星分布图Fig.1 Distribution diagrams of satellites

四面体ABEF体积公式可表示为

(8)

同理计算出VABED与VACDE，进而计算出多面体ABDCEF的体积。

2 试验与结果分析

试验设备为海星达H32全能型GNSS接收机1台,试验地点为河南理工大学荷花池试验基地。试验时间为2018年10月11日,接收可见星数量为GPS，BDS，GLONASS卫星，共26颗。利用26颗可见星的观测数据，进一步进行验证基于不规则三角网的选星算法。

2.1 试验计算结果

利用MATLAB软件进行编程，遍历某一历元所有可见星组合，计算基于不规则三角网得到的多面体体积及其对应的GDOP值。顾及后续导航解算问题，本试验只给出5～14颗星组合的计算结果。由于体积过小时GDOP值达到102量级，为了更好地显示多面体体积与GDOP值之间的对应关系，剔除体积小于0.02的卫星组合，计算结果如图2所示。图2中依次为由5～14星组成的多面体体积与对应的GDOP值之间的关系，横轴为卫星组成的多面体体积，纵轴为相应的GDOP值。

比较图2中多面体体积和GDOP值的关系，可发现如下现象。

(1)在5～14颗星的多星组合中，随着多面体体积的增大，对应的GDOP值呈现一种递减的趋势。

图2 GDOP值与多面体体积的关系Fig.2 Relationship between GDOP values and polyhedral volume

(2)从11颗星组合开始至14颗星组合，局部的GDOP值随体积增大而减小的趋势并不明显，且11颗星组合的定位精度已达到十分准确的程度。

为了更好地显示所选卫星数目与对应GDOP值之间的关系，表1与图3给出了选择卫星数目固定时，GDOP值小于3及GDOP小于5时的卫星组合与对应所有卫星组合的比例关系，同时，表1也给出了各组合相应的计算耗时(计算机主要参数CPU为i7 8700k；内存为骇客神条 8 G)。

从表1可知，随着组合星数的增加，GDOP值小于3和小于5的概率也随之增加；当组合卫星数达到11颗时，GDOP值小于3和GDOP值小于5的概率可达到96%；计算耗时从3.101 s增加到932.978 s，这是遍历其相应星数最优组合的耗时。

表1 GDOP值分布Tab.1 Distribution of GDOP values

图3GDOP值分布情况

Fig.3 Distribution ofGDOPvalues

2.2 结果分析

综合分析图2、图3和表1的结果，可得出如下结论：

(1)在多系统多可见星的选星问题中，多面体体积最大法仍然是一种较优的选星准则。

(2)适当的增加参与解算的导航卫星，可以提高导航定位的精度。

(3)选取11颗星组合进行导航定位解算，具有兼顾精度和效率的优势。

3 结 语

本文给出了一种基于不规则三角网(Delaunay三角网)的选星方法，并利用MATLAB平台，通过Delaunay三角网投影法计算多面体体积，分析多面体体积与GDOP值间的变化关系，得到了多面体体积最大法仍然是一种较优的选星准则和适当增加导航解算卫星数量提高定位精度的结论，其中11颗星组合建议为后续北斗/GNSS多系统多星选星算法研究提供了一定的思路。但是，通过遍历全部组合寻找最优组合的方法耗时较大，难以满足实时导航定位的工程需求，通过卫星的轨道先验信息或合理分类等方法，减少遍历耗时，提高选星效率，是高精度实时导航需要进一步考虑和研究的问题。