李涵秋，魏 达，朱建启，肖 庆，马 艳

(1.吉林大学 计算机科学与技术学院，长春 130012；2.西安卫星测控中心，西安 710043)

0 引 言

采用星间链路，导航星座能够在空中组网，可以不依赖地面设备实现所有网络节点的连接，将各颗卫星有机地联结为一个整体[1]。路由是星间互联的核心,路由协议直接决定着星间互联与数据传输性能[2]。卫星导航系统所提供的各类服务都依赖于卫星播发的广播星历、卫星钟差和卫星历书等导航电文，这是由上行数据注入系统负责保障的。上行数据注入系统是卫星导航系统的喉舌，处于极其重要的地位[3]。同时，在导航星座网络中，存在多种不同类型的数据流量传输，星上处理资源以及星间链路资源相对有限。如何应对导航星座网络中的各种问题，充分利用导航星座网络的独特特性，实现高效的数据传输，选取合适的路由成为关键[4]。

针对基于星间链路的卫星星座系统星间路由问题，国内外众多学者已进行了大量的研究工作。文献[4]提出了一种带有指向性天线分时隙通信的导航星座网络的算法。文献[5]提出了一种考虑链路异常状态的路由改进算法，但该算法需要检测结束后对整个星座的链路状态信息进行实时更新，时间和空间上消耗较大。文献[6]提出了一种多层链路拓扑及混合路由设计方案，该方案考虑了链路速率及节点负载，但是没有考虑发送数据总量。文献[7]提出了一种利用星间链路将境外星数据快速回传至境内的路由优化方法。大部分工作在考虑“北斗”系统卫星上行数据上注时，将每颗卫星作为独立的管理对象进行调度。对于地面站可见的卫星直接进行数据上注，对于地面站不可见的卫星通过可见卫星的星间链路进行上注数据转发，数据上注包含地面站到可见卫星、地面站到可见卫星再到不可见卫星两种类型。当可见卫星与不可见卫星所需上注的数据相同时，由于各个卫星上注过程独立，可见卫星向多颗不可见卫星进行转发就需要地面站重新上注多次，既占用了宝贵的信道资源又延长了星座的数据上注完成时间。

本文针对“北斗”导航系统日常管理维护中数据上注时隙表、路由表等数据更新操作中星座各星更新数据一致的特点，考虑链路带宽、更新时限等因素，提出了一种“北斗”导航系统星座数据上注更新路由算法。仿真结果表明，该方法可以有效缩短“北斗”导航星座全网上行注入数据更新的时间。

1 导航链路数据上注

1.1 导航星座建链约束

“北斗”导航系统采用混合型导航星座，星座包括24颗中地球轨道卫星(Medium Earth Orbit，MEO)、3颗倾斜地球同步轨道卫星(Inclined Geo Synchronous Orbit，IGSO)和3颗地球同步轨道卫星(Geostationary Earth Orbit，GEO)。地面控制中心可以通过星间链路的建立经由境内星与境外星建立通信，实现境外星遥测数据的回传和遥控指令的上注[8]。

导航星座建链受到多种限制因素的制约，可归纳为两大类。第一类为可见性约束，包括几何可见约束、天线可视约束和星间距离约束。可见性约束是建立星间链路的前提，导航星座构成了一个拓扑结构不断变化的空间信息网络，所以传输的时效性非常重要，如果两颗卫星在一个可见时段内数据未传输完毕，下个可见时段可能是几十分钟甚至十几个小时之后。所以数据上注的耗时并不是线性的，受星间可见约束的影响会有阶跃式的延长。第二类为功能性能约束，“北斗”导航星座的星间链路需要兼顾星间测量、地面定轨、遥测下传等要求，即使在两颗卫星完全可见的时段内也无法保持两颗卫星之间的长链接，而是为了满足位置精度(Position Dilution of Precision，PDOP)的要求，在一定时间内要一颗卫星保证尽可能多地与其他卫星链接。这就导致了单位时间内指定卫星间的传输容量是有限的，当上注数据量较大时短时间无法完成上注，地面站与卫星及卫星间的可见关系可能发生变化，需要考虑星间链路的拓扑变化情况。

1.2 导航星座数据上注现状

“北斗”全球卫星导航网络由空间段和地面段组成：空间段包括 MEO、IGSO、GEO 星座，是多层卫星网络；地面段主要用于维护空间段诸卫星的正常运转。上行数据注入系统将地面运行控制系统生成的导航电文及载荷管理指令上注到卫星并保持及时更新，是地面运行控制系统有效管理和控制星上业务载荷的有效途径，是保障卫星导航系统服务的“生命线”，其工作直接影响系统服务的连续性和稳定性[3]。

“北斗”导航系统采用空时分多址(Space Time Division Multiple Access，STDMA)接入模式用于星间链路卫星组网。在该接入模式下，卫星之间按照预先安排的时隙有秩序的建立链接。将连续的卫星轨道时间划分成多个超帧T，每个超帧T内认为星座间的可见关系固定，作为是一个链路分配的基本操作单元。同时超帧T由多组相等的时隙组成，每个时隙作为星间链路的建立和维护的基本单元，星间链路的切换等操作都是在各个时隙之间转换完成[9]。

“北斗”星间链路数据上注一般过程如图1所示，地面站分别对M11、M21和M31星进行数据上注。当各星上注数据不同时考虑的是三颗星之间的上注操作顺序；而当上注数据是全网统一的时隙表等数据时，图1中作为中转节点的M11就会接收到相同的数据MX1Data三次，同时整个天地网络仍有三次完整的建链过程。如果考虑只向M11发送一遍数据，而后由M11在后续时隙中向M21和M31发送数据，将极大地降低数据占用整个信道的带宽，同时也能显著缩短整个星座的数据更新时间。此时，需要考虑的问题是向M11星发送数据的时机以及M11向M21和M31转发数据的时机。

图1 数据上注过程示意图

2 动态链路树路由方法

为了解决全网统一更新相同数据时，每颗卫星分别建链造成的对整个天地网络的信道冗余占用，本文提出了一种动态链路树的上行路由改进算法。下面先介绍需要引入的相关概念，然后对算法步骤进行描述。

2.1 动态链路树概念

“北斗”导航系统的星间链路在一个超帧T内可见关系及路由关系固定，一个超帧时段对应一张路由表，下一超帧时段卫星可见关系发生变化，就对应另一张新的路由表。为简化说明问题，选取某一超帧内包含1个地面节点和4个卫星节点的前8个时隙构成的路由表，如图2所示，在第二个时隙地面站与M01星直接链接，地面站不直接与M02星、M03星和M04星链接，而是通过M01星转发进行通信。为了描述改进路由策略，需要将图2中所示的路由表转换为一种边可扩展的动态树形式。

图2 星间链路局部路由表

下面对动态链路树进行定义。

定义1 动态链路树是由星间链路路由表生成的树，其中树的根节点为星间链路中的地面节点或控制中心；树的节点是星间链路中建立链接的各个节点，同时按照从根节点几跳可达作为树的层数，对其余节点进行排列；树中的边表示两个节点可以建立直接链接，边的值为两个节点之间建链时隙的列表。

选取一个超帧T内的路由表，由图2所示的星间链路路由表生成的动态链路树如图3所示，树中总共包含5个节点，地面站为根节点，一跳可与地面站建立链接的M01星为第一层，两跳可与地面站建立链接的M02、M03、M04星为第二层，同时M01与地面站之间边的值为一个动态扩展的序列。在第一组时隙中M01星与地面站在第二个时隙建链，设一组时隙包含的时隙总数为n，则在第二组时隙中M01星与地面站是在2+n的相对时隙建立链接，同理在一个超帧T内M01星与地面站按照分组时隙周期性的建链，建链的相对时隙组成扩展的边序列[2,2+1n,2+2n,2+3n,…]，直到该超帧时间结束。其他边同理为星间链路两节点间建立链接的动态扩展时隙序列。

图3 星间链路局部动态链路树

建立了动态链路树后，需要对全网上行注入的效果进行评价，引入两个评价指标,即链路占用总时隙数量和链路最后更新时隙。下面结合动态链路树进行定义。

定义2 链路占用总时隙数量是数据上注完成整个链路所有节点数据更新所占用的时隙数量的总和，为动态链路树中所有叶节点中每个叶节点实际用于传输的最大时隙的总和。

图3中地面站在第二个时隙与M01星链接，然后M01星在第七个时隙与M02星链接，看似这个链接过程只有第二时隙和第七时隙两个时隙，然后实际上数据转发到M01星时，M01星无法立即与M02星建立链接，而是需要在星上暂存数据到第七个时隙然后再向M02星转发。由于星上存储等资源的限制，该次上注到M02星的过程实际消耗为7个时隙。因此，图3中的链路占用总时隙数量为M02星、M03星和M04星从地面站到各节点实际用于传输的最大时隙的总和。

定义3 链路最后更新时隙为星间链路所有完成数据上注更新的最后相对时隙数，为链路中各节点实际用于数据上注时隙中的最大值。

图3中，假设M01星在第二个时隙完成数据更新，M02星在第七个时隙完成数据更新，M03星在第四个时隙完成数据更新，M04星在第六个时隙完成数据更新，则四个节点中的最大时隙数为7，整个链路的最后更新时隙就是7，这代表了从数据上注开始，经历7个时隙该网络中的所有节点都能够完成数据更新。

2.2 动态链路树路由方法

通过将星间链路路由表转换成动态链路树，将“北斗”系统星间链路的全网数据更新问题转化为树的遍历问题。与一般遍历树算法不同之处在于，节点之间的连接受到建链时隙的边权值约束。具体体现在当前节点与下一级节点的建链时隙一定要大于当前节点与父节点的建链时隙；当前节点有多个子节点时，各子节点之间的遍历顺序为各节点最近与当前节点的可建链时刻进行排列。下面给出动态链路树路由算法的伪代码:

算法名称：updateBDLinks #上行路由改进算法

算法输入：nodeTree #动态树

rootStr #根节点名称

rootValue #根节点权值

算法输出：edgeListDic #动态边序列

subNodes=list(nodeTree.Subs) #获得所有子节点

For item in subNodes:

IfrootStr!=‘Root’: #如果不是根节点

edgeKey=rootStr+item #形成两节点的键值

linkList=edgeListDic[edgeKey]

#获得两节点间时隙序列

searchValue=next(x for x in linkList if x>rootValue)

#找到比根节点权值大的第一个时隙

rootValue=searchValue #更新根节点权值

linkList[edgeKey][searchValueIndex]=0

#标记使用时隙

subtree=nodeTree[item] #当前节点子节点

updateBDLinks(subtree,item,rootValue)

#递归调用

算法描述中，动态边序列集合edgeListDic为字典结构，Key为建链两个节点卫星的名称组合，Value为这两个卫星的建链时隙列表。最后遍历实际使用的时隙序号也在edgeListDic中的各时隙列表中进行了标记。

3 仿真验证

3.1 仿真场景设置

将“北斗”三代导航星座中的24颗MEO卫星标记为M01～M24，3颗GEO卫星标记为G01～G03，3颗IGSO卫星标记为I01～I03。根据“北斗”导航系统星座公开的TLE轨道数据，选取地面站坐标为北京站，计算2020年11月1日一天24 h的可见性及路由表，共形成24个超帧T1～T24，每个超帧时长为1 h，一个超帧内卫星间可见性及路由表不变。

由“北斗”三代导航星座超帧T1时段内的路由表生成的动态链路树如图4所示。从图4中可知，由地面站作为根节点，树的层数就是根节点到该层各节点的跳数。在该超帧内最多跳数为3跳，1跳可达第一层的M04、I03等卫星，2跳可达第二层的M06、M02等卫星，最大跳转3次就能到达该星座的所有卫星。以图4中I03节点构成的子树为例，如果地面站对该子树的所有节点依次进行数据上注更新，需要进行地面站-I03、地面站-I03-M05、地面站-I03-M15、地面站-I03-M18共4次上注，由于地面站与I03在一组时隙中只有第二个时隙相链接，则在更新M05星、M15星和M18星需要分别在三组时隙中进行，导致更新时间过长。

图4 生成的动态链路树图

3.2 仿真结果比对分析

由于每个超帧内星间可见性及路由表都会发生变化，分别按照逐星更新的上行数据注入方法和动态链路树路由方法，对“北斗”星座星间链路全天24 h的24个超帧进行结果比对。

比较链路占用总时隙数量如图5所示，逐星更新路由方法平均上注占用时隙数量为312个时隙，动态链路树路由方法平均上注占用时隙数量为215个时隙，占用整个星座的时隙数量降低了31%。链路占用总时隙数表征占用整个星间链路容量资源的大小，动态链路树路由算法能显著降低整个星座数据上注更新过程的资源占用。

图5 链路占用总时隙数量比对

在数据上注过程中更为重要的是上注总时长，图6对两种方法的链路最后更新时隙进行了对比。逐星更新路由方法平均链路最后更新时隙为105，动态链路树路由方法平均链路最后更新时隙为27，仅为逐星更新路由方法的25.7%，也就是相同的数据上注更新过程，动态链路树路由方法完成的时间为逐星更新路由方法的1/4，较大幅度地提高了完成数据上注任务速度，缩短了数据上注时间。

图6 链路最后更新时隙比对

4 结束语

本文针对目前“北斗”导航系统星间链路星座维护中频繁进行的更新时隙表、路由表等数据上注操作，提出了一种动态链路树路由算法，在星座各星上注数据一致的情况下显著降低了整个星座数据上注更新过程的资源占用，并较大幅度地提高了完成数据上注任务速度，缩短了数据上注时间。但算法未考虑设备状态切换时间因素的影响，将该因素纳入算法模型是下一步改进和完善的重点。