一种改进的组合导航系统选星算法

冯 彪，柴洪洲，潘宗鹏，王 敏，杨克凡

(信息工程大学，河南 郑州 450000)

一种改进的组合导航系统选星算法

冯 彪，柴洪洲，潘宗鹏，王 敏，杨克凡

(信息工程大学，河南 郑州 450000)

针对GPS，GLONASS，BDS组合导航系统定位中卫星的选择作了相关分析。首先用STK软件进行仿真，分析几何精度因子与卫星数的关系，得出组合导航系统最佳选星数；再根据卫星星座的空间几何分布，基于次优选星算法的成本函数模型，结合各导航系统卫星测量精度的差异性以及次优选星算法的峰值、不稳定特点，构建一种以卫星高度角和载噪比确定的加权成本函数模型，提出一种依据加权成本函数选星的分步次优加权选星算法。实验结果表明，该选星算法能近似到达最优选星算法的效果，计算负荷也相对较小，可满足导航定位解算精度和实时性要求。

组合导航系统；STK；GDOP；加权成本函数模型；分步次优加权选星算法

随着全球卫星导航系统(Global Navigation Satellite System，GNSS)不断发展，不同卫星星座间的组合，提供的可见卫星数目逐渐增多，卫星的几何分布结构也更完善。相对于单星座而言，多星座卫星组合导航系统的精度、完好性、可用性及可靠性都将大大的提高。但由于可见卫星数的成倍增长，会造成冗余信息过多，随之导航定位的计算量将成几十倍增长，严重影响导航定位解算的实时性，也对多模接收机的通道数和处理速度提出更高要求，也大大增加了接收机硬件设计的难度和成本。因此，在保证用户导航定位精度的前提下，减少冗余信息和降低导航定位解算的运算量，均衡地处理两者间的关系，选取分布合理的卫星就显得至关重要。

通常情况下，选星是要找出几何精度因子(Geometric Dilution of Precision, GDOP)最小的卫星组合，关键是综合考虑定位精度和实时性，确定选星数目和设计选星算法[1]。常规选星算法：最小GDOP值法[2]，即最优选星算法，卫星数较多时，运算量巨大；最大多面体体积法[3]、最大行列式法[4]是根据GDOP值随多面体体积与观测矩阵的行列式值的大小成反比原则选星，但GDOP值分别与多面体体积、矩阵行列式大小间的比例关系并不严格单调[5-6]，计算量也较大；基于卫星高度角和方位角选星算法[7]和应用模糊数学理论选星法[8]是根据卫星几何分布选星，需事先知道顶星座和底星座卫星个数，挑选方位角分布均匀的卫星，但卫星间方位角角差近似判断标准不易明确，而运用模糊数学理论过程又太繁琐复杂；组合选星法[9]选星结果最接近最小GDOP值法，但卫星数较多时，行列式计算量仍很大；间接选星法[10]，通过对高、低仰角区卫星数的判断，采用逆向思维反选出不要的卫星，同样存在选星数较多时，计算量大，不易实时应用的问题。

1 几何精度因子GDOP及影响因素

卫星导航系统的定位精度，可以表示为几何精度因子和用户等效距离误差的乘积，即

σP=GDOP·σUERE.

(1)

式中：σP表示定位精度的标准偏差；GDOP表示几何精度因子；σURER表示用户等效距离误差的标准差。GDOP表征用户和可见卫星的空间几何分布情况，反映定位卫星星座的拓扑结构对用户等效距离误差的放大程度，是作为衡量导航系统定位性能的重要指标。

几何精度因子是卫星与用户几何分布的函数，为

(2)

式中：trace( * )表示对矩阵取迹；A为GPS，GLONASS，BDS组合系统的观测矩阵，

(3)

(4)

式中：losj为卫星j与用户的观测向量;n为卫星系统i的卫星数。

(5)

式中：elj，aj分别表示卫星j的高度角和方位角。

由式(2)可知几何精度因子与观测矩阵A相关，取决于接收机与可见星的观测向量的组合。卫星几何分布越佳，A阵条件数越低，GDOP值越小；反之，卫星几何分布越差，A阵条件数越高，GDOP值越大[11]。同时，当可用卫星较少、几何分布又不理想时，A阵甚至可能呈病态，导致GDOP值极大，使解算失效；当可见卫星较多时，A阵为高阶矩阵，求逆矩阵过程中矩阵运算量巨大，冗余信息过量，导致实时性差。因此，导航解算的选星过程必须综合考虑卫星的几何构型和参与解算的最佳选星数目。

关于最佳选星数，本文通过STK(Satellite Tool Kit)软件进行仿真分析，时间为2015-12-09 08:00:00～23:59:30(GPST)，采样间隔30s，可见星截止高度角15°，统计分析GPS，GLONASS，BDS组合系统GDOP值随卫星数的变化，以确定最佳选星数目。用户位置分别选取位于中国区域的IGS(International GNSS Service)台站bjfs，wuhn，xian，shao，kunm，tcms 9个台站，台站位置信息见表1。

表1 用户位置信息

用STK模拟仿真了多星座组合系统分别选取6～18颗卫星以及所有可见星下其最小GDOP值，相应随卫星数变化曲线如图1所示。6站可见卫星数为22～29颗，均值为23～24 颗。

图1 wuhn站GDOP值随卫星数的变化关系

图2 均值与卫星数SVs关系

2 分步次优加权选星算法

2.1 次优选星算法

次优选星算法[12]是根据卫星的几何分布，通过比较两两卫星观测向量间的夹角大小评估卫星的冗余信息，剔除冗余量大的卫星，选出几何分布较好的卫星。冗余信息通过卫星间的成本函数值估计，成本函数定义为

Cij=cos 2θij.

(6)

式中：θij表示卫星i和卫星j观测向量间的夹角。当两颗卫星之间夹角为0°或±180°时，即两颗卫星与接收机同时处于一条直线上，其成本函数值最大；当两卫星夹角为90°时，也就是两颗卫星与用户构成一个直角三角形时，其成本函数值最小。而为了更准确反映一颗卫星与其它可见星的冗余信息，将这个星与其它所有可见星的成本函数值总和作为其总成本值，关系为

(7)

卫星的成本函数值越大，冗余信息也就越多。

通过分析及文献[13]指出，次优选星算法中，GDOP值变化曲线波动较大，不稳定，易发生跳变；在某些时刻GDOP值跳动很大，出现峰值现象，如图3所示。

图3 次优选星算法GDOP值峰值曲线

通过对峰值点对应选出的卫星及算法分析发现，一是次优选星算法选取的卫星集合中缺少高度角的卫星，从成本函数也可推算知，卫星高度角越大的卫星成本函数值越大，选星过程中越易被排除；二是次优选星算法选星过程仅根据卫星成本函数，以剔除与其它可见星分布结构较差的卫星，而未考虑不同导航系统中卫星信号、测量误差的差异，以致选星结果较差；三是通过再添加筛选排除集合中的卫星，对次优选星算法进行分步，选星结果和峰值现象能得到较大提高和改善。

因此，本文通过对次优选星采用的成本函数进行加权处理，即乘以权因子W，采用加权成本函数模型

(8)

2.2 权函数模型

对于组合系统，由于各卫星系统不同卫星发射的信号质量、传播路径不同，相应的伪距测量精度也不相同，主要与卫星星钟、大气延迟、用户设备和环境等相关。大气延迟误差与卫星高度角相关，随高度角的增大而减小；同时，高度角低的卫星信号质量通常差于高度角高的，低高度角的卫星信号也更容易引起多路径效应。因此，常利用卫星高度角建立随机模型。但是由于高度角随机模型为纯粹的高度角数学函数表达，没有考虑环境以及接收机本身的影响以及多路径效应的复杂性，仅利用高度角定权的效果不是很显著[14]。而信噪比能够有效反映卫星观测信号的质量，是基本的导航信号质量参数，常用载噪比定量表示。特别当信号发生衍射时，信噪比相对高度角更能准确反映用户接收到的卫星信号质量。因此，可以看出单一以高度角或载噪比定权的方式，并不适应于导航定位复杂多变的应用环境。

此外，根据选星的原则：选取卫星几何构型较好的卫星集合，即选取高度角趋于最低或最高的卫星。而高度分布同区域的卫星，高度角差异小，定权效果相当，不易筛选，而结合信噪比定权效果可知，更能反映细微差异；信噪比一定时，结合高度角定权能确保卫星几何分布。因此，提出以高度角el和载噪比C/N0联合构建的权函数模型

(9)

采用式(9)构建的加权成本函数，也说明卫星高度角越高、载噪比越高的卫星加权成本函数越小，越不易被排除，也印证了成本函数选星理论。

2.3 分步次优加权选星算法

通过前2节分析得到改进的次优选星算法，选星过程如下：

1)某一观测历元可见星数n颗(截止高度角15°，非开阔应用环境，如遮挡、城市和峡谷等)，选星数m；

4)重复步骤2)和步骤3)，并根据选星数和组合导航系统个数确定的对应高度角最少卫星数4颗以及大量实验验证分析，得到直至剩余卫星数为m-4；

5)在被排除的卫星集合中依次选取一颗卫星，结合已选卫星，计算所有卫星组合GDOP值，选取最小GDOP值的卫星组合，共循环4次，即为最终选星结果。

针对GDOP值的循环计算过程，涉及矩阵的求逆，本文运用矩阵求逆引理，不需重复计算高阶矩阵的逆矩阵，每次计算仅通过循环使用上次结果，即可求得高阶矩阵的逆，可大大降低运算量，提高实时性。具体计算过程如下[15]：

式中：Aj表示观测向量；i取值取决于卫星系统，见式(3)阵A；Qn-1,j表示除第j颗卫星，前n-1颗卫星求得的未知参数的协方差阵；Qn和GDOPn表示n颗卫星求得的未知参数的协方差阵和最小GDOP值。

3 实验分析

实验数据采用与我国区域星座分布近似的澳大利亚的IGS台站nnor站(116.1927°E,-31.048 7°S,234.984 m H)2015年第343 d 08:00:00～23:23:30的数据，共1 920个历元，与仿真实验采用的武汉站(114.357 3°E,30.5317°N,25.8 m H)的位置相对赤道近似南北颠倒。因此，两台站观测到的卫星星座空间分布近似一致，实验结果可相互验证说明。

通过实验结果对比分析最佳选星数为13颗时，最优选星算法、次优选星算法和分步次优加权选星算法GDOP值以及两种次优算法相对最优选星算法的GDOP差值△GDOP值，如图4、图5所示。

图4 3种选星算法的GDOP值变化曲线

图5 次优、分步次优加权选星算法与最优选星算法的△GDOP值

从图4、图5可知，分布加权次优选星算法GDOP值在1.5～2.5之间，与最优选星算法的GDOP差值△GDOP维持在0.3左右，最小值为0，最大值约为0.8，说明其选星结果可能最大接近于最优选星算法；相对次优选星算法，GDOP值缩小一半，其变化幅度更小，曲线也相对平稳、无峰值点，充分证明分步次优加权选星算法优于次优选星算法，其选星结果更可靠。同时，统计3种选星算法GDOP的最大值、最小值、平均值，如表2所示。

表2 3种选星算法GDOP值

为进一步分析选星算法与最优算法的接近程度，可通过GDOP比值ζ评估[14]，其定义为

(10)

由于最优选星算法选出的卫星组合空间几何构型最好，其GDOP值自然就最小，因此ζ≥1。ζ越接近于1，说明选星算法的结果越符合于最优选星结果，算法性能也就越好；ζ越大，算法效果就越差，结果就越不可靠。

统计比较分步次优加权选星算法、次优选星算法相对最优选星算法的GDOP比值ζ的大小及共计1920个历元对应分布的每个ζ值区间的个数，分步如图6所示。

图6 两种选星算法ζ分步

从图6可看出，分步次优选星算法ζ最小为1，最大为1.6，绝大部分值小于1.2，超过历元总数的70%；而次优选星算法ζ在1.2～2.8之间，均值在1.7附近，多半以上历元数都位于均值区间。更进一步证明上述观点，分步次优选星算法选星效果优于次优选星算法，结果更接近于最优选星算法。

关于选星算法的实时性效果，可通过导航定位解算的计算量反映，主要在于选星过程的循环迭代次数、矩阵计算。矩阵计算快慢主要取决于矩阵维数的高低和求逆次数。以此次试验为例，观测时段内可见星平均数为23颗，选星数为13颗，4种选星算法计算GDOP值涉及的矩阵相乘的维数和求逆计算次数如表3所示。

表3 4种选星算法的运算量

从表3可知，全视野法和次优选星算法计算次数最少，1次。但全视野法，组合系统卫星将达几十颗甚至上百颗，矩阵A的维数随之增长，计算量巨大；而次优选星算法其选星结果GDOP值较大，可靠性较低，不宜应用；分步次优加权选星算法计算量相对较小，仅涉及第一步求两两卫星方向向量间的夹角，23×3维的高阶矩阵计算，后4颗卫星选取只是循环次数较多，但每次仅是低维向量1×6维或6×1维计算，增加量相对最优选星算法，矩阵求逆1 144 066次，计算量大大减少，且其选星结果也接近于最优选星算法，更可靠。除此，分步次优加权选星算法可随用户对精度的要求，随时改变选星数，而计算过程只是第一步求逆矩阵的维数变化，相对原过程以及其他选星算法，计算量及增量仍较少，不影响实时性。因此，分步次优加权选星算法可满足导航系统精度和实时性要求。

4 结 论

本文首先通过STK仿真分析了中国区域GDOP值与卫星数的关系，得出GPS，GLONASS，BDS组合导航系统在可见星较多时，最佳的选星数为13～17颗，并提出基于次优选星算法的分步次优加权选星算法，是根据卫星在空间的几何分布，利用卫星的加权成本函数，选择两两卫星间夹角较大的卫星集合。该算法相对次优选星算法峰值和可靠性低的问题，有以下改进：

1)针对组合系统的各卫星的伪距测量误差精度不同，采用卫星的高度角与信噪比确定权函数，对卫星成本函数进行加权处理，即采用加权成本函数选星；

2)针对高度角的卫星成本函数较大，易被排除的问题，可通过再分步选择优化，即在利用加权成本函数排除的卫星集合中再选择几颗卫星，根据最小GDOP值选取；

关于常规选星算法涉及高阶矩阵、循环迭代等运算问题，计算量十分巨大，耗时长、实时性差，而该选星算法运用矩阵求逆引理，采用循环递推，避免大量高阶矩阵的运算，提高解算速率，实时性较好。

[1] 丛丽，谈展中. 提高卫星导航定位精度和实时性的选星算法[J]. 系统工程与电子技术, 2008, 30(10):1914-1917.

[2] MILLIKEN R J,ZOLLER C J. Principle of operation of NAVSTAR and characteristics[J]. Navigation,1978,25(2):96-106.

[3] 张贵明，黄顺吉. 一种新的GPS导航卫星选择算法[J]. 电子科技大学学报,2009,29(3):221-224.

[4] 陈浩，范胜林，刘建业. GPS/Galileo组合导航定位系统中的选星算法[J]. 弹箭与制导报学报,2009,29(4).

[5] ZU Miaoyan, JUN Z.A Fast Satellite Selection Algorithm: Beyond Four Satellites[J].Selected Topics in Signal Processing, IEEE Journal,2009,3(5): 740-747.

[6] ANHONG T. A new satellite selection algorithm in GNSS[C]. Information Management, Innovation Management and Industrial Engineering (ICIII), 2013 6th International Conference,2013.

[7] 吴瑞祥，蔡体菁. 基于高度角和方位角的选星方法[J]. 舰船电子工程, 2009, 29(11): 73-75.

[8] ZHANG L, DENG Z, YANG L. An improved satellite selection algorithm based on fuzzy comprehensive evaluation method and the entropy method for determining the weight of evaluation indicators[C]. Broadband Network and Multimedia Technology (IC-BNMT), 2011 4th IEEE International Conference on. IEEE, 2011:652-655.

[9] 张强，张晓林，李宏伟,等. 组合卫星接收机中的选星算法[J]. 北京航空航天大学学报，2007，33(12):1424-1427.

[10] 金玲, 黄智刚, 李锐,等. 多卫导组合系统的快速选星算法研究[J]. 电子学报,2009, 37(9):1931-1936.

[11] 杨迪. GNSS多星座组合导航关键技术研究[D]. 南京：南京航空航天大学, 2012.

[12] CHAN-WOO P, HOW J P.Quasi-optimal Satellite Selection Algorithm for Real-time Applications1[C].Proceedings of the 14th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GPS 2001), Salt Lake City, UT, September,2001:3018-3028.

[13] WEI M. An improved satellite selection algorithm. Signal Processing (ICSP), 2012 IEEE 11th International Conference,2012.

[14] 张小红, 丁乐乐. 北斗二代观测值质量分析及随机模型精化[J]. 武汉大学学报(信息科学版), 2013,38(7):832-836.

[15] PHATAK M S. Recursive method for optimum GPS satellite selection[J]. Aerospace & Electronic Systems IEEE Transactions on, 2001, 37(2):751-754.

An improved satellite selection algorithm for integrated navigation system

FENG Biao, CHAI Hongzhou, PAN Zongpeng, WANG Min, YANG Kefan

(Information Engineering University, Zhengzhou 45000, China)

This paper analyzes the selection of satellites for GPS, GLONASS and BDS integrated navigation system. Firstly, the relationship between the geometric dilution of precision GDOP and the number of satellites is analyzed with STK simulation to obtain the best SVs selection. Secondly, according to the spatial distribution of satellite constellation, based on the cost function of quasi-optimal satellite selection algorithm, and combined with the difference in measurement precision of satellites for integrated satellite system, the peak value and unstable characteristics of quasi-optimal satellite selection algorithm, a weighted cost function model is built determined by the satellite elevation angle and signal to noise ratio. And a step-by-step quasi-optimal weighted satellite selection algorithm is proposed based on the weighted cost function. Experimental result shows that the proposed algorithm can approximate the effect of the optimal selection algorithm, and the computational load is relatively small, which can satisfy the accuracy and real-time requirements of navigation and positioning solution.

integrated navigation system; STK; GDOP; weighted cost function model; step-by-step quasi-optimal weighted satellite selection algorithm

2016-11-14

国家自然科学基金资助项目(41574010;41274045)

冯 彪(1990-)，男，硕士研究生.

著录：冯彪，柴洪洲，潘宗鹏，等.一种改进的组合导航系统选星算法[J].测绘工程，2018，27(2)：26-31.

10.19349/j.cnki.issn1006-7949.2018.02.005

P228.4

A

1006-7949(2018)02-0026-06

张德福]