专利名称：一种卫星导航系统选星方法
技术领域：
本发明属于卫星导航领域，具体涉及一种卫星导航系统选星方法。
背景技术：
近年来，卫星导航系统在导航测量中的作用日益增强，在科学研究、国民经济与国 防建设等方面产生了极大的经济效益和社会效益，对人们生活的各个方面起到了越来越重 要的作用。目前，美国的全球定位系统(Global Positioning System，简称为GPS)和俄罗 斯的全球导航卫星系统(GLObal NAvigation Satellite System，简称为GL0NASS)已发展 成为第二代卫星导航定位系统，欧盟的伽利略(GALILEO)系统和中国的北斗卫星导航系统 (BeiDou/COMPASS Navigation Satellite System，简称为 COMPASS)等正在积极筹建。不久 的将来，这些系统将共同组成全球导航卫星系统(Global Navigation SatelliteSystem， 简称为GNSS)。到那时，全球导航卫星将有一百多颗，多卫星导航系统的组合导航势成必然。 对任意一种卫星导航系统，简称为单系统；对任意两种卫星导航系统的组合系统，简称为双 系统；对任意三种卫星导航系统的组合系统，简称为三系统；对任意四种卫星导航系统的 组合系统，简称为四系统；对双系统及其以上系统统称为多星座卫星导航系统或组合星座 卫星导航系统，简称为多系统。采用多星座卫星导航系统时，可见星数将大幅增加，定位精 度和系统可用性及可靠性均将大大提高，但同时，导航定位的运算量也随之成倍增长，加之 工程上对用户接收机的处理器速度要求提高，特别是对高动态用户而言，为了保证实时处 理的要求，对接收机处理器速度的要求就更是大大提高，因而大大加重了用户接收机的负 担，使其成本上升。而实际上，不可能也不需要采用所有可见星来进行导航定位，只需要选 出满足定位精度要求的少数卫星进行导航定位。因此，在多星座卫星导航定位系统中，选星 便显得迫切而重要。遗传算法(Genetic Algorithm,简称GA)是一种基于生物自然选择与遗传机理的 随机优化搜索算法。它以适应度函数为依据，通过对种群中个体的操作来实现种群内个体 结构的重组，按优胜劣汰的原则来获得优化结果。在遗传算法中，要对解的形式进行编码， 编码后的解也称为个体或染色体，多个个体就成为一个种群。遗传算法是通过对解集的编 码的运算来获得最终结果的。通常，遗传算法从一组随机产生的初始种群开始，然后通过繁 殖、交叉、变异等遗传操作产生新一代更加优良的种群，最后从最终种群中选取最优个体就 能获得最终的解。在卫星导航系统中，影响定位精度的关键因素之一是几何精度因子 (GeometricDilution of Precision，简称为 GD0P)。一般而言，GD0P 越小，定位精度越高。 传统选星方法主要针对GD0P，有GD0P或加权GD0P选星，虽然它能找出在规定选星数目下具 有最小GD0P值的卫星组合，但计算量大，实时性差，特别是对于多星座卫星导航系统而言， 它几乎不可能做到实时选星。目前，针对组合星座卫星导航系统选星问题，出现了一系列为减少计算量而设计 的方法。虽然相对传统的常规选星方法而言其计算量有较大改善，但大部分方法其计算量仍然很大，有的方法则要求定位接收机有较大的内存容量，对实时用户而言，这也难以实 现。有的虽然计算量不太大，但最终选取的卫星数过多，如占所有可见星数的60%以上。因 为定位求解的计算量直接和采用的定位卫星数成倍数关系，所以这就增大了后续的定位解 算的计算量，特别是对高动态用户而言，这也是不现实的。

发明内容
本发明的目的是提出一种适用于多星座卫星导航系统的简单易行的快速选星方 法，它是从所有可见星中选出规定数目的可见星并使所选卫星星座的GD0P值满足限制要 求。本发明提出的一种卫星导航系统选星方法，其技术方案在于从目标优化的角度对 选星问题进行描述，然后以优化搜索方式完成对问题的处理。这里，将选星问题描述为从 所有可见星中选出规定数目的卫星使其GD0P值最小。这就将其转化成了目标优化问题，从 而，在卫星导航系统中，可以采用遗传算法中的一些基本概念和做法来实现选星功能。将选星问题以目标优化方式描述后，再根据该描述的特征采用遗传算法中的一些 概念和做法来获得GD0P值满足限制要求的的星座，达到选星的目的。具体是通过以下步骤 实现的步骤一参数配置。根据定位需要和接收机性能以及组合星座个数，配置所需选取的卫星数ns和星座 的几何精度因子GD0P值的限制要求，配置所需种群大小posjize和最大进化代数G_，确 定交叉操作中所采用的交叉概率P。的大小以及变异操作中的变异概率Pm的大小。步骤二 获取可见星位置。通过卫星星历或历书得到所有当前可见星的位置，同时，要将属于不同卫星系统 的各卫星位置转换至某种选定的坐标系。这里，如果存在接收机自主完整性分析，则根据该 分析结果来剔除故障卫星，保证参与选星的卫星均处于健康状态。步骤三编码。采用二进制串编码方案来表示选星中的卫星组合方案。该方案中将每颗卫星设为 一个基因，这里，基因就是卫星选入与否的标识，它是一个二进制变量。1基因，采用数字1 表示，它表明在最终结果中该卫星被选入；0基因，采用数字0表示，它表明在最终结果中该 卫星未被选入。所有观测卫星按顺序进行编排，最低位表示第1号卫星，第n位表示第n号 卫星。从而，对于由n个可见星组成的选星问题中的卫星组合方案，其二进制串编码长度为 n，这里，选星问题中的一种卫星组合方案的二进制编码串简称为一个解，也称为一个个体。步骤四种群初始化。初始化就是根据编码方案对个体进行初始赋值，对于总可见卫星数为n的卫星导 航系统，种群初始化就是采用随机的方式产生pop_siZe个长为n的二进制串。需要注意的 是，为了满足选星要求，每个二进制串中1基因的个数等于ns。步骤五获取适值。根据适应度函数获取各个体的适值，其中，适值就是适应度函数之值，适应度函数 用来评价个体的优劣。步骤六终止条件判断，获取最终的选星结果。
根据各个体的适值，选出适值最大的个体作为初步选星结果。然后，统计进化迭代 次数gen。如果该个体对应的星座⑶0P值满足限制要求，或者如果gen = Gfflax,则终止整个 选星过程，将该个体作为最终的结果；否则，继续下面的过程，直至满足终止条件。满足终止 条件后，将最终选取的个体进行译码形成选星结果，这样，完成整个选星过程。这里，译码就 是编码的逆过程，它是将所有1基因对应的卫星作为选用卫星组合来使用，而0基因对应的 卫星排除不用。步骤七选择。在本发明的选星方法中，采用正比选择方式从种群中获得进行交叉的种群。在该 方式中，每个个体的选择概率正比于其适值。经p0p_siZe次选择获得用于交叉的种群。步骤八交叉。根据交叉概率p。从交叉种群中选择用于交叉的个体，其中，称用于交叉的两个个 体为双亲或父代。再然后以一定的交叉方式完成交叉操作以形成新的个体，这里，称所产生 的新个体为后代。在本发明中，采用称之为保“1”映射交叉(“OnVMatched Crossover, 简称0MX)或变异交叉(Mutative Crossover，简称为MX)的方式来进行交叉操作，0MX和MX 中的任一种交叉方式都能达到本发明的目的。0MX的操作过程如下a.先根据交叉概率p。选择双亲，然后，随机产生1个1 (ns_l)间的整数n。，由 整数n。定义要进行交叉的所选卫星，双亲中序号较小的n。颗已选卫星进行交叉，其中，已选 卫星标识就是1基因；b.交换双亲中序号较小的n。颗已选卫星标识，产生原始后代；c.根据所交换的卫星间编号对应关系来确定所交换的卫星间的映射关系。如果双 亲1中卫星pl、p2分别与双亲2中卫星p2、ql进行交换，则它们之间的对应关系为内ep2、
因为卫星p2两次进行了交换，从而实际上卫星p2没有进行交换，这样，它们的映射 关系就确定为内，其它情形可按类似方法得到所交换的卫星间的映射关系；d.根据映射关系形成交叉操作的最终后代。如果在双亲1或双亲2中没有参与交 换的卫星出现在映射关系中，就按映射关系在原始后代中将之替换；如在双亲1中卫星ql 没有参与交换，但存在映射关系,那么，就应当将双亲1中的卫星ql在原始后代1中 用卫星pl替换，而参与交换的卫星保持不变。MX的操作过程如下a.先根据交叉概率p。选择双亲，然后，随机产生1个1 (ns_l)间的整数n。，由 整数n。定义要进行交叉的所选卫星，双亲中序号较小的n。颗已选卫星进行交叉，其中，已选 卫星标识就是1基因；b.交换双亲中序号较小的n。颗已选卫星标识，产生原始后代；c.根据原始后代中1基因的个数判断通过交叉所获得的后代是否满足选星中对 卫星数的限制要求；只有当原始后代中1基因的个数等于^时，通过交叉所获得的后代才 满足选星对卫星数的限制要求；如果原始后代均满足限制要求，则不进行进一步操作，所形 成的原始后代是交叉操作所获得的最终后代。否则，根据相差的个数，随机选取相应原始后 代中为“0”的基因，将之变为“ 1”，直至后代个体中“ 1”的个数等于ns为止，就获得了交叉 操作所形成的最终后代。
8
步骤九变异。与交叉操作一样，在选星问题中，变异操作也要保证变异前后个体中的已选卫星 数相同。根据这一要求，在本发明的选星方法中，采用双基因“01”相对变异方式，经变异操 作所形成的个体也称为后代。设总可见星数为n，则双基因“01”相对变异方式的操作过程如下a.根据变异概率pm从交叉操作所形成的种群中随机选取一个欲进行变异的个体 P ；b.随机产生一个1 n间的整数gl ；c.判定个体P中gl位所对应的基因类别，如果该基因为“0”，则随机产生一个1 n间的整数g2，并使gl兴g2，且应保证个体P中与g2对应的基因为“1”，反之，如果gl对 应的基因为“1”，则产生的随机数g2对应的基因应为“0” ；d.将个体P中与gl和g2相对应的基因进行变异，变异就是将“ 1，，和“0”互换。步骤十形成新种群。根据⑶0P值的大小，从所有后代和父代中选取⑶0P最小的p0p_siZe个个体形成 新种群。然后返回步骤五。本发明的优点在于(1)本方法采用目标优化方式来描述卫星导航系统中的选星问题，以优化搜索方 式实现选星，有效解决了传统选星方法操作量大的问题，与传统GD0P最优选星法相比，计 算量改善值在99%以上，同时也克服了现有一些改进方法选星数目过多的缺陷，可以实现 简单、快速选星；(2)本方法以GD0P限制要求为前提按规定卫星数来进行选星，可以根据接收机的 通道跟踪能力来确定选星数，使用灵活，操作简单，并能保证导航精度；(3)本方法适合静态、动态用户进行实时选星。


图1是本发明所述卫星导航系统选星方法的流程图；图2是本发明所述北京十三陵UTC时刻0时选星前后的可见星星空视图；图3是本发明所述北京十三陵一天不同时刻选星后的⑶0P值；图4是本发明所述北京十三陵一天不同时刻选星过程中的进化代数；图5是本发明所述北京十三陵一天不同时刻选星过程中以⑶0P为参考的运算量。
具体实施例方式下面将结合附图和实施例对本发明作进一步的详细说明。本发明是一种卫星导航系统选星方法，所述方法流程图如图1所示。在某一观测历元，接收机可同时观测到多个组合星座中的多颗卫星，现要从中选 出满足定位要求的规定数目的卫星。步骤一参数配置。根据定位需要和接收机性能以及组合星座个数，配置所需选取的卫星数ns和星座 的几何精度因子GD0P值的限制要求，配置所需种群大小p0p_siZe和最大进化代数G_，确定交叉操作中所采用的交叉概率P。的大小以及变异操作中的变异概率Pm的大小。对于所需选取的卫星数~，根据定位需要以及组合星座系统个数及接收机性能来 确定，在没有特别的规定或要求且卫星数足够多的情形下，对于单系统，取为7 8 ；对于双 系统，取为7 9 ；对于三系统，取为8 10 ；对于四系统，取为9 12。对星座的几何精度 因子GD0P值的限制要求，在没有特别要求的情形下，取为不大于6的正数。对于种群大小p0p_siZe，对单系统或双系统，取为8 12 ；对三系统，取为10 16 ；对四系统，取为10 20，实际应用过程中的具体值，采用仿真方式进行调试得到。对于 最大进化代数G_，取为20 100。在本发明所述选星方法中，交叉概率p。的取值范围为0. 3 0. 9，变异概率pm的 取值范围为0. 1 0. 7，实际使用时的具体取值通过仿真调试来确定。步骤二 获取可见星位置。通过卫星星历或历书得到所有当前可见星的位置，同时，要将属于不同卫星系统 的各卫星位置转换至某种选定的坐标系。这里，如果存在接收机自主完整性分析，则根据该 分析结果来剔除故障卫星，保证参与选星的卫星均处于健康状态。步骤三编码。采用二进制串编码方案来表示选星中的卫星组合方案。该方案中将每颗卫星设为 一个基因，这里，基因就是卫星选入与否的标识，它是一个二进制变量。1基因，采用数字1 表示，它表明在最终结果中该卫星被选入；0基因，采用数字0表示，它表明在最终结果中该 卫星未被选入。所有观测卫星按顺序进行编排，最低位表示第1号卫星，第n位表示第n号 卫星。从而，对于由n个可见星组成的选星问题中的卫星组合方案，其二进制串编码长度为 n，这里，选星问题中的一种卫星组合方案的二进制编码串简称为一个解，也称为一个个体。 例如，一个有15颗可见星的选星结果的一种卫星组合方案X，表示为如下形式的二进制字 串X = [101110010110010]这表示由方案X所表征的卫星组合结果中，所选用的卫星其编号分别为15、13、 12、11、8、6、5、2。这里，X表示选星问题的一种卫星组合方案的二进制编码串，也简称为一 个解或一个个体。步骤四种群初始化。初始化就是根据编码方案对个体进行初始赋值，对于总可见卫星数为n的卫星导 航系统，种群初始化就是采用随机的方式产生pop_siZe个长为n的二进制串。需要注意的 是，为了满足选星要求，每个二进制串中1基因的个数等于ns。步骤五获取适值。根据适应度函数获取各个体的适值，其中，适值就是适应度函数之值，适应度函数 用来评价个体的优劣。在本发明中，采用如下形式的适应度函数
u GDOP^ - GDOP(X) + seval(X) =-—-—~~(1
GDOP^ -GDOPmm +s其中，eval(X)是适应度函数，其值就是适值；X是步骤三中所述选星问题的解， 也就是星座组合方案的二进制编码，是种群中的个体；GD0P_表示当前种群中最大的GD0P
10值，⑶0Pmin表示当前种群中最小的⑶0P值；⑶0P⑴表示个体X的⑶0P值；￡是一个(0， 1)区间上小的正实数，它仅是为了避免分母为0而设置的，随机选取。由X的取值根据适应 度函数eval⑴得到适值。步骤六终止条件判断，获取最终的选星结果。根据各个体的适值，选出适值最大的个体作为初步选星结果。然后，统计进化迭代 次数gen。如果该个体对应的星座⑶0P值满足限制要求，或者如果gen = Gfflax,则终止整个 选星过程，将该个体作为最终的结果；否则，继续下面的过程，直至满足终止条件。满足终止 条件后，将最终选取的个体进行译码形成选星结果，这样，完成整个选星过程。这里，译码就 是编码的逆过程，它是将所有1基因对应的卫星作为选用卫星组合来使用，而0基因对应的 卫星排除不用。步骤七选择。在本发明的选星方法中，采用正比选择方式从种群中获得进行交叉的种群。在该 方式中，每个个体的选择概率正比于其适值。经p0p_siZe次选择获得用于交叉的种群。设种群中第k个个体的适值为eValk，这里k = 1，2，…，pop_siZe，按正比选择方 式，其选择概率Pk通过下式获得
/pop ‘ size
^evalj(2)
M其中eval」表示第j个个体的适值，这里j = 1,2.…，pop_size。在获得各个体的选择概率后，再根据选择概率得到各个体的累积概率
kqk = YjPj ,k = \,2,---,pop_size(3)
M其中，qk表示第k个个体的累积概率，Pj表示第j个个体的选择概率。再按如下方法获取交叉种群a.在W，l]区间内随机产生一个均勻分布的实数r。b.如果r彡qi，则选第1个个体；否贝丨」，选择第k个个体，其中，2彡k彡p0p_siZe， 使得 qk-i < r < qk。c.重复上述过程p0p_siZe次，获得用于交叉的种群。步骤八交叉。根据交叉概率p。从交叉种群中选择用于交叉的个体，其中，称用于交叉的两个个 体为双亲或父代。具体说来，选择双亲的方法为首先，在W，l]区间内随机产生一个实数rk，其中k= 1，2，…，p0p_siZe。若rk <P。，则选取第k个个体作为交叉的双亲之一。每选出两个个体就形成一对双亲，对其进行 交叉操作；如果最终选取的个体数为单数，则将最后一个个体剔除不用。选出双亲后，就按一定的交叉方式完成交叉操作以形成新的个体，这里，称所产生 的新个体为后代。在本发明中，采用称之为保“1”映射交叉(“OnVMatched Crossover, 简称0MX)或变异交叉(Mutative Crossover，简称为MX)的方式来进行交叉操作，0MX和MX 中的任一种交叉方式都能达到本发明的目的。0MX的操作过程如下a.先根据交叉概率p。选择双亲，然后，随机产生1个1 (ns_l)间的整数n。，由整数n。定义要进行交叉的所选卫星，双亲中序号较小的n。颗已选卫星进行交叉，其中，已选 卫星标识就是1基因；b.交换双亲中序号较小的n。颗已选卫星标识，产生原始后代；c.根据所交换的卫星间编号对应关系来确定所交换的卫星间的映射关系。如果双 亲1中卫星pl、p2分别与双亲2中卫星p2、ql进行交换，则它们之间的对应关系为树^/^、
因为卫星p2两次进行了交换，从而实际上卫星p2没有进行交换，这样，它们的映射 关系就确定为，其它情形可按类似方法得到所交换的卫星间的映射关系；d.根据映射关系形成交叉操作的最终后代。如果在双亲1或双亲2中没有参与交 换的卫星出现在映射关系中，就按映射关系在原始后代中将之替换；如在双亲1中卫星ql 没有参与交换，但存在映射关系树O㈣，那么，就应当将双亲1中的卫星ql在原始后代1中 用卫星pl替换，而参与交换的卫星保持不变。0MX的操作过程可用如下示例来说明，该示例中，共有16颗可卫星，要求选取8颗卫星。①设随机选择的双亲如下双亲1 :0111100101110000，对应已选星号为15，14，13，12，9，7，6，5 ；双亲2 :0001100101011110，对应已选星号为13，12，9，7，5，4，3，2 ；随机产生的整数为6。②交换双亲中所选卫星中的后6个，产生原始后代原始后代1 :0110000101011110，对应已选星号为:15，14，9，7，5，4，3，2 ；原始后代2 :0001100101110000，对应已选星号为13，12，9，7，6，5 ；③确定映射关系，根据所交换的卫星间编号对应关系可确定如下卫星间的映射关 系 ④由映射关系形成交叉操作的最终后代。由步骤③可知，应将双亲2中不参与交换的卫星13、12在后代2中分别以卫星2、 4替换，而参与交换的卫星不变，得到最终的两个后代如下后代1 :0110000101011110，对应的已选星号为:15，14，9，7，5，4，3，2 ；后代2 :0001100101111010，对应的已选星号为13，12，9，7，6，5，4，2。MX的操作过程如下a.先根据交叉概率p。选择双亲，然后，随机产生1个1 (ns_l)间的整数n。，由 整数n。定义要进行交叉的所选卫星，双亲中序号较小的n。颗已选卫星进行交叉，其中，已选 卫星标识就是1基因；b.交换双亲中序号较小的n。颗已选卫星标识，产生原始后代；c.根据原始后代中1基因的个数判断通过交叉所获得的后代是否满足选星中对 卫星数的限制要求；只有当原始后代中1基因的个数等于^时，通过交叉所获得的后代才 满足选星对卫星数的限制要求；如果原始后代均满足限制要求，则不进行进一步操作，所形
12成的原始后代是交叉操作所获得的最终后代。否则，根据相差的个数，随机选取相应原始后 代中为“0”的基因，将之变为“1”，直至后代个体中“1”的个数等于ns为止，就获得了交叉 操作所形成的最终后代。 MX的操作过程可用如下示例来说明，该示例中，共有16颗可卫星，要求选取8颗卫①设随机选择的双亲如下双亲1 :0111100101110000，对应已选星号为15,14,13,12,9,7,6,5 ；双亲2 :0001100101011110，对应已选星号为13，12，9，7，5，4，3，2 ；随机产生的整数为6。②交换双亲中所选卫星中的后6个，产生原始后代原始后代1 :0110000101011110，对应已选星号为:15，14，9，7，5，4，3，2 ；原始后代2 :0001100101110000，对应已选星号为13，12，9，7，6，5 ；③根据原始后代中1基因的个数判断通过交叉所获得的后代是否满足故障检测 对卫星数的限制要求。由上一步骤可知，原始后代1中1基因的个数为8，是满足条件的解；而原始后代 2中1基因的个数为6，不满足要求，与要求的8个还差2个，故应随机选取2个未选卫星位 置，也就是0基因，使之产生变异。设随机选择的位置为1和16，则形成的最终后代为后代1 :0110000101011110，对应已选星号为:15，14，9，7，5，4，3，2 ；后代2 :1001100101110001，对应已选星号为16，13，12，9，7，6，5，1。步骤九变异。与交叉操作一样，在选星问题中，变异操作也要保证变异前后个体中的已选卫星 数相同。根据这一要求，在本发明的选星方法中，采用双基因“01”相对变异方式，经变异操 作所形成的个体也称为后代。设总可见星数为n，则双基因“01”相对变异方式的操作过程如下a.根据变异概率pm从交叉操作所形成的种群中随机选取一个欲进行变异的个体 P ；b.随机产生一个1 n间的整数gl ；c.判定个体P中gl位所对应的基因类别，如果该基因为“0”，则随机产生一个1 n间的整数g2，并使gl兴g2，且保证个体P中与g2对应的基因为“1”，反之，如果gl对应 的基因为“1”，则产生的随机数g2对应的基因为“0” ；d.将个体P中与gl和g2相对应的基因进行变异，变异就是将“1”和“0”互换。这里，根据变异概率pm选取进行变异的个体的方法为在W，l]区间内随机产生 一个实数rk，这里k = l,2,-,pop_size ；若rk < pm，则交叉操作所形成的种群中的第k个 个体就是欲进行变异的个体。步骤十形成新种群。根据⑶0P值的大小，从所有后代和父代中选取⑶0P最小的p0p_siZe个个体形成 新种群。然后返回步骤五。本发明的选星方法，最终选取的卫星数能根据组合星座个数和接收机性能进行灵 活配置，使用简便，操作量小，且选出的星座GD0P值满足定位需要。为了验证本发明的选星效果和性能，本发明以GPS和COMPASS组成的双系统为例，在全中国范围内，以中国地壳运 动观测网络数据中心的27个GPS基准站为站点进行了仿真分析，图2 图5为部分仿真结^ o图2为北京十三陵地区(BJSH站)协调世界时(Coordinated Universal Time，简 称为UTC)0时选星前后星空视图对比图，其中，左图为选星前星空视图，右图为选星后星空 视图。图中，“G”、“B”分别表示GPS卫星和COMPASS卫星，其后数字表示卫星号，N表示北， E表示东，从里到外的圆分别表示仰角为75°、40°、5°位置，圆心为90°仰角位置，它对 应用户所在位置。由图2可见，选星前，可见卫星数较多，共有17颗，且分布上存在“扎堆” 现象；选星后，可见星散布较好，卫星数较少，这将大大降低接收机的导航处理负担，有利于 接收机的实时快速定位。图3为BJSH站选星后的GD0P曲线。图中横坐标为时间，单位为 小时，纵坐标表示GD0P值。由图3可见，选星后，各时刻GD0P值较小，且变化范围不大，约 在1. 5 3之间。一般，卫星系统可用性的选择规定为位置精度因子PD0P彡6。因为选星 后，有⑶OP ^ 3，而PD0P <⑶0P，这就表明采用本发明的选星方法所获得的结果是能满足 导航定位要求的。图4为BJSH站各选星时刻采用本发明的选星方法选星过程中的进化代数，其中， 纵坐标表示选星过程中的进化代数，横坐标表示时间t，单位为小时h。由图4可见，在绝大 部分情形下，进化代数不会超过2代。经对全部27个基准站的选星结果进行统计，结果表 明，在⑶0P限制为3、种群数为10的情形下，有98. 637%的选星时刻其进化代数不超过2 ； 更进一步的，约有95. 925%的选星时刻在初始化完成后就能获得满足要求的选星结果。因 为在整个选星求解过程中，交叉、变异过程是位操作，主要的操作量体现为获取GD0P值，因 此，选星操作量的大小可以粗略的以获取GD0P值的次数来衡量，图5为BJSH站各选星时刻 以GD0P求解次数为参考的运算量曲线，其中，纵坐标表示以GD0P求解次数为参考的运算 量，横坐标表示时间t，单位为小时h。由图5可知，整体而言，本发明的选星方法操作运算 量不大，对所选参考站，其最大运算量不超过70次GD0P求解的运算量。经对全部27个基 准站的选星结果进行统计，结果表明，平均每个选星时刻不到13次GD0P的求解运算量。而 如果采用传统的最优GD0P方法进行选星，在图2所示的17颗可见星星座状态下，要选取8 颗星座结构最优的卫星，则需进行24310次⑶0P求解，而随着卫星数目的增多，其运算量将 急剧增加，例如，当可见卫星数为18时，⑶0P求解次数将增大至43758，显然，这对于实时选 星是不现实的，而本发明的方法其选星操作的最大运算量不超过70次GD0P求解次数，还不 到传统最优GD0P选星方法的0. 5%，其运算量的改善值超过99%，这就为本发明的选星方 法不管是在静态还是动态条件下的实时、快速选星提供了保证，且选星结果满足导航定位 要求。本发明的卫星导航系统选星方法，以GD0P限制要求为前提，按设定的卫星数进行 选星，有效克服了传统选星方法操作运算量大的缺点，同时，选择的卫星数设置灵活，并能 保证所选星座满足导航定位要求，实现了简单、快速选星。
1权利要求
一种卫星导航系统选星方法，其特征在于，该方法包括以下步骤步骤一参数配置；根据定位需要和接收机性能以及组合星座个数，配置所需选取的卫星数ns和星座的几何精度因子GDOP值的限制要求，配置所需种群大小pop_size和最大进化代数Gmax，确定交叉操作中所采用的交叉概率pc的大小以及变异操作中的变异概率pm的大小；步骤二获取可见星位置；通过卫星星历或历书得到所有当前可见星的位置，同时，要将属于不同卫星系统的各卫星位置转换至某种选定的坐标系；如果存在接收机自主完整性分析，则根据该分析结果来剔除故障卫星，保证参与选星的卫星均处于健康状态；步骤三编码；采用二进制串编码方案来表示选星中的卫星组合方案；将每颗卫星设为一个基因，所有观测卫星按顺序进行编排，最低位表示第1号卫星，第n位表示第n号卫星；对于由n个可见星组成的选星问题中的卫星组合方案，其二进制串编码长度为n；选星问题中的一种卫星组合方案的二进制编码串简称为一个解或一个个体；其中，上述的基因是卫星选入与否的标识，是一个二进制变量；1基因，采用数字1表示，表明在最终结果中该卫星被选入；0基因，采用数字0表示，表明在最终结果中该卫星未被选入；步骤四种群初始化；初始化就是根据编码方案对个体进行初始赋值，对于总可见卫星数为n的卫星导航系统，种群初始化就是采用随机的方式产生pop_size个长为n的二进制串，且二进制串中1基因的个数等于ns；步骤五获取适值；根据适应度函数获取各个体的适值；其中，适值是适应度函数之值；步骤六终止条件判断，获取最终的选星结果；根据各个体的适值，选出适值最大的个体作为初步选星结果；然后，统计进化迭代次数gen；如果该个体对应的星座GDOP值满足限制要求，或者如果gen＝Gmax，则终止整个选星过程，将该个体作为最终的结果；否则，继续下面步骤七至步骤十的过程，直至满足终止条件；满足终止条件后，将最终选取的个体进行译码形成选星结果；这里，译码就是编码的逆过程，它是将所有1基因对应的卫星作为选用卫星组合来使用，而0基因对应的卫星排除不用；当满足终止条件后，完成整个选星过程；步骤七选择；采用正比选择方式从种群中获得进行交叉的种群，每个个体的选择概率正比于其适值；经pop_size次选择获得用于交叉的种群；设种群中第k个个体的适值为evalk，其中k＝1，2，…，pop_size，则按正比选择方式，其选择概率pk为 <mrow><msub> <mi>p</mi> <mi>k</mi></msub><mo>=</mo><msub> <mi>eval</mi> <mi>k</mi></msub><mo>/</mo><munderover> <mi>&Sigma;</mi> <mrow><mi>j</mi><mo>=</mo><mn>1</mn> </mrow> <mrow><mi>pop</mi><mo>_</mo><mi>size</mi> </mrow></munderover><msub> <mi>eval</mi> <mi>j</mi></msub> </mrow>其中evalj表示第j个个体的适值，这里j＝1，2.…，pop_size；在获得各个体的选择概率后，再根据选择概率得到各个体的累积概率qk <mrow><msub> <mi>q</mi> <mi>k</mi></msub><mo>=</mo><munderover> <mi>&Sigma;</mi> <mrow><mi>jj</mi><mo>=</mo><mn>1</mn> </mrow> <mi>k</mi></munderover><msub> <mi>p</mi> <mi>j</mi></msub><mo>,</mo><mi>k</mi><mo>=</mo><mn>1,2</mn><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><mi>pop</mi><mo>_</mo><mi>size</mi> </mrow>其中，qk表示第k个个体的累积概率，pj表示第j个个体的选择概率；根据累计概率qk获得交叉种群；步骤八交叉；根据交叉概率pc从交叉种群中选择出用于交叉的个体，其中，用于交叉的两个个体为双亲或父代；接着，采用保“1”映射交叉OMX或变异交叉MX的方式来进行交叉操作形成新的个体，称交叉操作所形成的新个体为后代；步骤九变异；采用双基因“01”相对变异方式执行变异操作，变异操作所形成的个体也称为后代；步骤十形成新种群；根据GDOP值的大小，从所有后代和父代中选取GDOP最小的pop_size个个体形成新种群；然后返回步骤五。
2.根据权利要求1所述的一种卫星导航系统选星方法，其特征在于步骤一所述的参 数配置，其中所需选取的卫星数ns，根据定位需要以及组合星座系统个数及接收机性能来确定，在 没有特别的规定或要求及卫星数足够多的情形下，对于单系统，所需选取的卫星数ns取为 7 8 ；对于双系统，所需选取的卫星数ns取为7 9 ；对于三系统，所需选取的卫星数ns取 为8 10 ；对于四系统，所需选取的卫星数ns取为9 12 ；对星座的几何精度因子GD0P值的限制要求，在没有特别要求的情形下，取为不大于6 的正数；种群大小pop_siZe，对单系统或双系统，取为8 12 ；对三系统，取为10 16 ；对四系 统，取为10 20 ；对于实际应用过程中的具体值，采用仿真方式进行调试得到； 最大进化代数G_，取为20 100 ；交叉概率P。的取值范围为0. 3 0. 9，变异概率pm的取值范围为0. 1 0. 7，实际使用 时的具体取值通过仿真调试来确定。
3.根据权利要求1所述的一种卫星导航系统选星方法，其特征在于，步骤五中所述的 适应度函数为evaKX) = GDOP^-GDOP^ GDOPmax -GDOP^ +e 其中，eval(X)是适应度函数，其值就是适值；X是步骤三中所述选星问题的解，也就 是星座组合方案的二进制编码，是种群中的个体；GD0P_表示当前种群中最大的GD0P值， ⑶0Pmin表示当前种群中最小的⑶0P值；⑶0P(X)表示个体X的⑶OP值；￡是一个(0，1)区 间上小的正实数，它仅是为了避免分母为0而设置的，随机选取。
4.根据权利要求1所述的一种卫星导航系统选星方法，其特征在于，步骤七中所述的 根据累计概率qk获取交叉种群的方式如下，这里k= 1，2，-,pop_sizea)在W，l]区间内随机产生一个均勻分布的实数r；b)如果r( qi，则选第1个个体；否则，选择第k个个体，其中，2彡k ( pop.size^^ < r s^ qk ；c)重复上述过程p0p_siZe次，获得用于交叉的种群。
5.根据权利要求1所述的一种卫星导航系统选星方法，其特征在于，步骤八中所述的 根据交叉概率P。从交叉种群中选择用于交叉的个体的方法为在W，l]区间内随机产生一 个实数rk，其中k= 1,2,…，p0p_siZe ；若rk<p。，则选取第k个个体作为交叉的双亲之 一；每选出两个个体形成一对双亲，对其进行交叉操作；如果最终选取的个体数为单数，则 将最后一个个体剔除不用。
6.根据权利要求1所述的一种卫星导航系统选星方法，其特征在于，步骤八中所述的 保“ 1 ”映射交叉0MX的操作过程如下a.先根据交叉概率p。选择双亲，然后，随机产生1个1 (ns_l)间的整数n。，由整数 n。定义要进行交叉的所选卫星，双亲中序号较小的n。颗已选卫星进行交叉；其中，已选卫星 标识就是1基因；b.交换双亲中序号较小的n。颗已选卫星标识，产生原始后代；c.根据所交换的卫星间编号对应关系来确定所交换的卫星间的映射关系；如果双亲1 中卫星pi、卫星P2分别与双亲2中卫星p2、卫星ql进行交换，则它们之间的对应关系为 pi e 、P2 ^ ，因为卫星p2两次进行了交换，从而实际上卫星p2没有进行交换，这样，它 们的映射关系就确定为树㈠射,其它情形按类似方法得到所交换的卫星间的映射关系；d.根据映射关系形成交叉操作的最终后代；如果在双亲1或双亲2中没有参与交换的 卫星出现在映射关系中，就按映射关系在原始后代中将之替换；如在双亲1中卫星ql没有 参与交换，但存在映射关系树,那么，就将双亲1中的卫星ql在原始后代1中用卫星pl 替换，而参与交换的卫星保持不变。
7.根据权利要求1所述的一种卫星导航系统选星方法，其特征在于，步骤八中所述的 变异交叉MX的操作过程如下a.先根据交叉概率p。选择双亲，然后，随机产生1个1 (ns_l)间的整数n。，由整数 nc定义要进行交叉的所选卫星，双亲中序号较小的n。颗已选卫星进行交叉，其中，已选卫星 标识就是1基因；b.交换双亲中序号较小的n。颗已选卫星标识，产生原始后代；c.根据原始后代中1基因的个数判断通过交叉所获得的后代是否满足选星中对卫星 数的限制要求；只有当原始后代中1基因的个数等于n。时，通过交叉所获得的后代才满足 选星对卫星数的限制要求；如果原始后代均满足限制要求，则不进行进一步操作，所形成的 原始后代是交叉操作所获得的最终后代；否则，根据相差的个数，随机选取相应原始后代中 为“0”的基因将之变为“1”，直至后代个体中“1”的个数等于n。为止，就获得了交叉操作所 形成的最终后代。
8.根据权利要求1所述的一种卫星导航系统选星方法，其特征在于，步骤九中所述的 双基因“01”相对变异方式的操作过程如下a.根据变异概率pm从交叉操作所形成的种群中随机选取一个欲进行变异的个体P；b.随机产生一个1 n间的整数gl，这里n为总可见卫星数；c.判定个体P中gl位所对应的基因类别，如果该基因为“0”，则随机产生一个1 n 间的整数g2，并使gl兴g2，且保证个体P中与g2对应的基因为“ 1 ”，反之，如果gl对应的 基因为“1”，则产生的随机数g2对应的基因为“0” ；d.将个体P中与gl和g2相对应的基因进行变异，变异就是将“ 1 ”和“0”互换。
全文摘要
本发明公开了一种卫星导航系统选星方法。它以满足导航定位要求为前提按设定的卫星数来进行选星，以达到减少选星操作量和降低导航定位计算量的目的。该方法首先进行参数配置，获取可见星位置，然后采用编码、种群初始化、适值获取、选择、交叉和变异方式来执行选星操作，形成新种群，以选取适值最大的个体作为初始选星结果；当满足终止条件时，根据该个体获得最终的选星结果。本方法有效克服了传统选星方法计算量大的问题，操作灵活，可实现简单、快速选星，适合静态和动态条件下的实时选星需求。
文档编号G01S19/28GK101866010SQ201010194279
公开日2010年10月20日 申请日期2010年5月28日 优先权日2010年5月28日
发明者张晓林, 陈灿辉, 霍航宇 申请人:北京航空航天大学