基于K均值聚类的新型选星算法

董天宝，唐 健，曾芳玲

(国防科技大学电子对抗学院，安徽 合肥 230037)

1 引言

目前，随着各国卫星系统的不断发展与更新，天空中可利用的卫星数量不断增加，使得用户对可见卫星的可选择性增加，为导航定位提供了便利，但是同时也对选星的准确性和时效性提出了新的挑战，也大大提高了接收机数据处理的负载能力。在利用卫星进行导航定位时，影响定位精度的因素主要有两个：一是，接收机精度及环境因素产生的观测误差；二是，可见卫星的空间几何分布[1]。卫星导航定位的第一个步骤就是选取空间分布较好的卫星，只有选取的卫星组合适当，才能提高导航定位的精度。因此，研究选取空间分布较好的可见卫星在导航定位方面具有很大的意义。

当前国内外选星的研究对象大多是针对单个卫星系统，传统的选星算法主要有四种[2]：最佳几何精度因子法、最大矢端四面体体积法、最大正交投影法和综合法。这四种选星算法都是对所有的可见卫星进行遍历来计算出最佳的卫星组合，因此它们的计算量都非常大，导致选星的时效性有所欠缺，所以没有被应用到实际的工程应用中。随着研究的不断深入，针对传统选星算法的不足又发展出了多种选星算法，文献[3]提出的基于高度角和方位角的快速选星算法通过对不同数量的卫星的仰角和方位角进行分析，然后进行选星，计算了卫星组合的GDOP值，并研究总结了顶座卫星和底座卫星的选取方法；文献[4]通过研究GDOP与卫星几何布局的关系，提出了几何布局选星法，选星的时效性较好，但是存在GDOP值偏离较大的问题；文献[5，6]在选取仰角最大和最小的卫星的基础上，通过判断剩余可见卫星对GDOP值的贡献值进行选星，避免了矩阵的求逆运算，算法运算量大幅减小，选星的时效性有所提高，但选星的精度有待进一步提高。此外，还有模糊选星法[7]、六星选星法[8]、组合系统的快速选星算法[9]和基于空间均匀分区的快速旋转分割的选星算法[10]等。这些算法或多或少都存在不足之处，有的算法过于复杂导致选星时效性较差，有的算法的精确性略差。比如文献[3]中提到的快速选星算法在利用方位角进行选星时，在第1颗底座卫星方位角的基础上强制性地加上固定的角度作为选星的标准，就会存在“扎堆”现象(存在多颗距离相距较近且分布相对集中的卫星，且没有分布在相对应的方位角，从而只有少量卫星分布在预定角度附近)，这就会导致只有少量的卫星参与选星。

本文针对上述问题，兼顾算法的时效性和精确性，提出了一种基于K均值聚类的新型选星算法，该算法将可见卫星的方位角进行聚类，从每一类的卫星中选取一颗卫星，重点解决了卫星的“扎堆”现象，大幅度降低了选星算法的运算量，选星的时效性和准确性都能够满足用户的导航定位的要求。

2 基于GDOP的选星算法原理

卫星的定位精度可以表示为用户测量的伪距误差的标准差与几何精度因子GDOP值的乘积[11]，即

Δx=Δρ·GDOP

(1)

其中，Δx表示用户定位精度的误差的标准差；Δρ表示用户测量的伪距误差的标准差；GDOP表示几何精度因子。从上式可以看出，在Δρ已知时，Δx∝Δρ。因此，选星时选取GDOP值最小的卫星组合更有利于定位精度的提高。文献[12]指出，只有当卫星组合的GDOP值小于6的情况下才能够满足用户的定位要求。也就是说天空中的卫星分布相对分散的情况下，定位才够准确，卫星的仰角必须大于5°，因为如果卫星的仰角太小，会由于大气层的折射等因素的影响，造成多径效应，导致测量伪距存在差异，从而影响定位精度。

卫星导航系统GDOP的表达式为

(2)

其中，H为卫星导航系统的观测矩阵。

观测矩阵H可以表示为

(3)

其中，cosα、cosβ和cosγ是用户到卫星连线的三个方向角的余弦值如图1所示。

图1 卫星相对于用户的分布位置

对于单系统而言，当选取的卫星数量为4颗时，GDOP还可以表示为[13，14]

(4)

3 新型选星算法

3.1 算法原理分析

K均值(K-means)聚类算法是最著名的一种聚类算法，它是一种以距离为评判标准的数据分析方法，可以根据N个数据对象D={x1，x2，…，xN}的属性划分为K个簇Gk(m=1，2，…，K)。其中，K

(5)

其中，Ji表示第i簇的目标函数。从上式中可以看出，Ji的值取决于Gi的几何特性和ck的几何位置。对于xk和ci的欧氏距离可以表示为

(6)

则式(5)可以表示为

(7)

其中，ci为第i簇的均值向量

(8)

同时可以定义二维隶属矩阵uik∈{0，1}。如果第k个数据对象xk属于第i簇，则uik=1；否则，uik=0。并且，uik满足以下条件

(9)

对于GPS卫星系统，地球某一地点任意时刻天空中可见卫星数量平均为十几颗，数量较少，将其仰角作为数据对象计算速度较快，适用于K均值聚类算法。具体的选星流程分为以下几步：

对于GPS卫星系统，地球某一地点任意时刻天空中可见卫星数量平均为十几颗，数量较少，将其仰角作为数据对象计算速度较快，适用于K均值聚类算法。具体的选星流程分为以下几步：

1) 确定选星的相关参数。根据实际的定位需求确定选星的数量，并兼顾仰角的限定值，防止仰角过小造成测量的伪距差变大。假设共需要K(K

2) 计算卫星仰角和方位角。读取卫星的星历文件，根据轨道参数计算所有卫星的位置，并根据卫星与用户的位置计算出卫星的方位角A={a1，a2，….aN}及仰角E={e1，e2，….eN}，其中N为所有GPS卫星的数量；

3) 选取第一颗卫星。选取仰角E大于5°的卫星作为可见卫星(设共有n颗可见卫星)，并将仰角E最大的卫星作为第一颗卫星；

4) 利用K均值聚类算法从剩余可见卫星中选取K-1颗卫星。将剩余可见卫星的方位角A组成向量集D={a1，a2，….an-1}。具体可以分为以下几个步骤：

a) 从数据对象集D中随机选择K-1个样本作为初始的K-1个聚类中心C={c1，c2，…，cK-1}；

b) 计算数据对象ai(i=1，2，…，l-1)和各个聚类中心ck(k=1，2，…，K-1)的距离d(ai，ck)，找到距离聚类中心ck最近的ai，并将其放入簇Gk，此时便将卫星共划分为K-1个簇Gi(i=1，2，…K-1)；

c) 对于簇G中的数据对象重新计算新的聚类中心ck(k=1，2，…，K-1)，并更新簇Gk；

d) 计算每个样本数据到聚类中心最小距离平方和：

(10)

如果S收敛，则终止计算，并输出簇Gk。否则，返回第二步循环计算，一般循环3～4次即可达到终止条件；

e) 从K-1个簇中分别选取一颗卫星，最后共选出K颗卫星；

5) 计算该卫星组合的GDOP值。

选星结束后，将该卫星组合的GDOP值与最佳GDOP法比较，判断选星的准确性。假设需选取K颗卫星用户定位，新型选星算法的流程图如图2所示。

图2 新型选星算法流程图

3.2 算法原理分析

为了使选星算法更具说服性，实验利用MATLAB软件，通过读取三个时刻的GPS广播星历文件进行卫星的位置的解算，排除仰角小于5°的卫星后再进行选星。仿真结果显示，位处合肥市(31.86°N，117.27°E)的用户在三个卫星参考时刻分别可以接收到的卫星数量为7颗、10颗和10颗，三个星历参考时刻分别是2020年2月25日0时(时刻1)、2020年2月26日0时(时刻2)和2020年2月27日0时(时刻3)。如表1、表2和表3所示为三个卫星参考时刻卫星仰角和方位角的信息。

表1 时刻1可见卫星的仰角及方位角

表2 时刻2可见卫星的仰角及方位角

表3 时刻3时可见卫星的仰角及方位角

根据上述三个时刻卫星的方位角和仰角，利用本选星算法将可见卫星的方位角进行聚类，在三个时刻分别选取4颗卫星用于导航定位，并利用MATLAB软件进行仿真，计算卫星组合的GDOP值并记录算法的运行时间，如表4所示为本选星算法和最佳GDOP值法两种选星算法的比较，如图3～图5所示为本选星算法的选星仿真图。

综合选星过程和仿真结果对本选星算法进行性能分析，结合表4可以看出：

1) 定位精度高。时刻1两种算法的选星编号相同，时刻2和时刻3选取的卫星中均只有一颗选星编号不同，虽然两种算法计算的GDOP值略有不同，但两者差异很小。所选卫星组合得GDOP值虽然不是最佳的，但是GDOP值的最大偏离度不超过5%，且GDOP都小于6，定位精度能够满足用户的定位的需求。

3) 本算法同样适用于多卫星系统。对于单卫星系统而言，可见卫星的数量还是相对较少，卫星的可选择性较差。对于多卫星系统而言，卫星的可选择性增加，K均值聚类算法的聚类对象增加，从而选星的精度相对于单系统会大大提高，而算法的运算量几乎没有变化，可以大大减少选星时间。

图3～图5为三个时刻的选星仿真结果图，图中标注的数字为排除仰角最大卫星后剩余可见卫星的PRN号，由于在利用K均值算法进行选星时，只对卫星的方位角进行聚类，所以图中只显示了卫星的方位角信息。选星时，选取仰角大于5°的卫星作为可见卫星，将可见卫星的仰角划分为3个簇，从每一簇中分别选出一颗仰角最低的卫星。从这三张图中可以看出，当可见卫星存在空间分布不均匀的现象时，通过本算法进行选星后，卫星分布较分散，降低了卫星“扎堆”现象对选星造成的影响。

表4 两种选星算法的比较

图3 时刻1选星仿真图

图4 时刻2选星仿真图

图5 时刻3选星仿真图

4 总结

本文在卫星空间分布的基础上通过对可见卫星的方位角进行聚类划分，提出了一种基于K均值聚类的新型选星算法，并给出了具体的选星步骤。该算法以提供尽可能小的GDOP值的卫星组合为原则，利用K均值聚类算法对三个时刻的可见卫星的方位角进行划分，最后利用MATLAB软件进行仿真。仿真结果表明，该算法得到的几何精度因子与最佳GDOP法得到的几何精度因子相差很小，能够满足用户的定位需求；该算法的运算量大大较小，避免了传统选星算法需要大量的矩阵乘法和矩阵求逆的问题，运行时间大大减少，降低了算法的复杂度，提高了选星的时效性，所以该算法有较好的选星性能，可以快速准确地选星，同时该算法适用于多卫星系统选星。