导航卫星网络故障下的拓扑与时空路由快速应急恢复方法

本发明涉及卫星导航网络的动态拓扑控制与时变路由，具体涉及一种导航卫星网络故障下的拓扑与时空路由快速应急恢复方法。本发明尤其适用于如下导航卫星网络：每颗导航卫星配置一个能够在不同时隙间快速切换建链对象的星间测量终端，以时隙作为星间链路建立的基本时间单元，同一导航卫星在同一时隙至多与一个计划对象建立该类星间链路；各导航卫星在多个时隙中可与不同邻接卫星动态建链，并基于预先确定的链路时序计划形成利用不同时隙链路机会的时空路由。

背景技术：

1、全球卫星导航系统（global navigation satellite system，gnss）是提供定位、导航与授时服务的重要空间基础设施。为了降低对地面站连续可见性的依赖，并提高星座自主运行能力，现代导航卫星系统逐步配置星间链路（inter-satellite link，isl），利用星间链路完成卫星间精密测距、时间同步、运行状态与业务数据交换等任务。星间测量数据的数量及几何多样性直接影响导航卫星定轨和全星座时间同步性能，因此，导航卫星通常需要在一定时间范围内尽可能与多个不同的邻接卫星建立星间链路，以获取丰富的星间测量数据。

2、受星上载荷、天线口径、射频通道、功耗及指向控制能力等资源约束，本发明所针对的导航卫星网络中，每颗导航卫星仅配置一个能够快速切换建链对象的星间测量终端，并采用基于时隙的动态建链方式：在一个时隙内，一颗导航卫星至多与一个对象建立该类星间链路；在相邻或后续时隙中，该导航卫星可以切换至其他可见卫星建立链路。通过在连续时隙中动态切换不同建链对象，导航卫星能够提高星间测量对象的数量和几何多样性，从而为精密定轨和全星座时间同步提供更丰富的观测信息。

3、上述建链体制使导航卫星网络具有区别于持续多邻接通信网络的显著时变特征。由于同一导航卫星在任一时隙内至多具有一个建链对象，单个时隙内形成的网络拓扑通常仅包含若干离散星间链路，并不要求在该时隙内形成覆盖所有源节点和目的节点的瞬时端到端多跳连通路径。端到端数据传输可以跨越多个连续时隙逐步完成：数据在某一时隙由当前卫星转发至其当时的建链对象，在后续时隙再随着链路对象切换继续向目的节点传输。因此，同一源节点至同一目的节点的可行时空路径会随时隙变化。

4、在此类时变导航卫星网络中，链路时序计划通常可以根据卫星轨道、可见关系、测距需求、通信需求及终端资源约束预先生成，并进一步据此预先计算时空路由。由于当前时隙的计划建链对象并不一定对应某一目的节点的合适转发方向，即使当前星间链路能够正常建立，面向特定目的节点的数据也可能在该时隙不具备适用的转发机会。此时，数据可以先保存在星上缓存中，等待后续时隙切换至能够继续推进该数据到达目的节点的计划建链对象后再行转发，形成存储-携带-转发（store-carry-forward）的数据传输方式。

5、当导航卫星节点发生故障时，以该故障卫星为计划建链对象的星间链路均无法正常建立；当某一星间链路发生故障时，该链路在故障持续期间同样无法执行原定建链计划。对于本发明所针对的单快速切换星间测量终端场景，健康导航卫星在同一时隙不存在第二条并行的该类星间链路可用于继续执行原计划。因此，无论是对端节点故障还是原计划星间链路自身发生故障，在受影响健康导航卫星的网络层即时处置上，均表现为相关时隙的计划星间链路不可用。由此，原本计划经该链路转发的数据将无法按照原定动作发出；若仍继续执行原转发计划，可能造成无效发送、数据丢失或数据在故障邻接方向持续积压。

6、现有卫星网络故障恢复方法通常采用两类思路：

7、第一类是在故障发生后重新进行全局或较大范围的拓扑规划，并在重构后的拓扑上重新计算源节点至目的节点的路由。该类方法能够面向故障后的网络状态重新获得整体性能较优的拓扑与路由，但通常需要完成较大规模的状态收集、拓扑优化和路由计算，处理时长相对较长，更适合作为故障后的长期恢复手段，而不适合作为故障发生后立即执行的快速应急处置。

8、第二类是在检测到链路或节点故障后，通过局部快速重路由、备份路径切换或增量路径搜索等方式，立即寻找绕开故障对象的新多跳转发路径。该类方法通常依赖同一节点能够同时保持多个邻接链路以及较高的瞬时网络连通度，因此在具有多并行邻接链路的通信卫星网络中具有较强适用性。

9、然而，对于本发明所针对的导航卫星网络而言，上述处理方式并未充分利用其由多样化星间测量需求所形成的跨时隙动态建链特性。一方面，由于每颗导航卫星仅配置一个快速切换星间测量终端，同一时隙内至多存在一个计划建链对象，因此当相关时隙的原计划星间链路失效时，该健康导航卫星在该时隙不存在第二条并行的同类星间链路可用于替代转发，立即在该时隙内寻找新的并行邻接链路不具备物理基础；另一方面，相关时隙的原计划星间链路失效，并不意味着同一源节点至目的节点在后续时隙持续不可达。随着导航卫星在后续时隙切换至其他测量对象，原预先计算时空路由中可能重新出现不经过故障对象的可行转发机会。因此，如果在故障发生后立即对全网时空路由进行重新搜索，会引入较大的星上计算开销，而这些计算在应急阶段并非始终必要。

10、此外，若采用地面集中方式完成全局拓扑和路由重构，还需要经历故障状态回传、全网状态汇聚、全局优化计算、结果上注以及全网同步切换等过程；若由星上直接执行全局优化和全源-全目的路由重算，则会受到星上处理器算力、存储容量及功耗等约束。由此，在故障发生至长期全局优化结果重新可用之间，客观存在一个需要快速维持网络运行的应急处置阶段。

11、因此，有必要针对导航卫星网络的单终端时隙化动态建链特点以及跨时隙时空路由特性，设计一种计算量小、响应快、可由各导航卫星分布式执行并能够保持全网结果一致的故障应急恢复方法，在不立即追求故障后全局最优拓扑和最优路由的情况下，优先阻断不可执行的故障相关转发行为，利用星上缓存等待后续时隙的正常时空路径机会，同时对故障造成的链路空洞进行轻量级拓扑补偿，从而在长期全局恢复完成前尽快维持导航卫星网络的正常运行。

技术实现思路

1、（一）发明目的

2、本发明的目的在于克服现有卫星网络故障恢复方法在导航卫星时隙化星间链路场景下计算开销大、恢复流程长以及未充分利用后续时隙时空路径机会的问题，提供一种导航卫星网络故障下的拓扑与时空路由快速应急恢复方法。

3、本发明并不以故障发生后立即获得全局最优拓扑和全局最优路由为目标，而是面向故障发生至长期全局恢复结果可用之前的应急阶段，在保证未受故障影响的既有链路和路由结果尽量保持不变的前提下，通过对故障相关转发行为进行即时抑制、利用“存储-携带-转发”机制缓存数据、并行执行确定性分布式拓扑增量重构以及在统一时刻启用新增链路，使导航卫星网络以较低的星上计算和控制开销尽快恢复可运行状态，并对故障造成的性能损失进行一定程度补偿。

4、（二）技术方案

5、为实现上述目的，本发明采用如下技术方案。本发明的导航卫星网络故障下的拓扑与时空路由快速应急恢复方法，所述导航卫星网络中的每颗导航卫星配置一个能够快速切换建链对象的星间测量终端，以时隙作为星间链路的建立单元，使每颗导航卫星在同一时隙至多具有一个计划建链对象；所述导航卫星网络在正常状态下具有预先确定的链路时序计划，所述链路时序计划使同一导航卫星在多个时隙中能够与不同邻接导航卫星建立星间链路，并基于所述链路时序计划预先形成利用不同时隙链路机会的时空路由；各导航卫星具有按时隙和目的节点索引的本地路由执行表，所述本地路由执行表由多条路由表项组成。

6、进一步地，所述本地路由执行表的单条路由表项包括时隙标识、目的节点标识、计划建链对象标识和转发标志；对于同一导航卫星的同一时隙，在存在计划建链对象时，不同目的节点对应相同的计划建链对象，且所述转发标志分别指示面向各目的节点的数据是否经所述计划建链对象发送；所述转发标志采用二值编码时，禁止转发状态以0表示，允许转发状态以1表示。

7、s1、获取故障状态信息，将节点故障和星间链路故障统一映射为相关时隙的计划星间链路不可用。

8、进一步地，所述故障状态信息利用故障发生前仍可用的链路时序计划中的星间链路逐跳传播至参与应急恢复的健康导航卫星；各参与应急恢复的健康导航卫星根据所述故障状态信息中携带的故障对象标识，以及故障事件参考时刻和故障状态版本号中的至少一种，确定一致的故障输入。

9、进一步地，对于节点故障，将以故障节点为计划建链对象的计划星间链路标记为不可用，并将所述故障节点从应急阶段的有效中继节点集合、候选建链对象集合和有效目的节点集合中移除；对于星间链路故障，将发生故障的计划星间链路在相应故障持续时隙内标记为不可用；当相关时隙的计划星间链路的对端为故障导航卫星，或者所述计划星间链路自身发生故障时，对该时隙面向各有效目的节点的转发行为采用相同的故障抑制处理。

10、s2、在参与应急恢复的健康导航卫星获得所述故障状态信息后，并行执行路由应急处置和确定性分布式拓扑增量重构。

11、所述路由应急处置包括：对于计划星间链路受所述节点故障和星间链路故障影响而不可用的受影响时隙，在不重新计算新的多跳时空路由的情况下，将所述受影响时隙内面向有效目的节点的对应转发标志设置为禁止转发状态，并将待发送数据保存在本地缓存中，同时保持未受所述节点故障和星间链路故障影响的原路由表项不变。

12、所述确定性分布式拓扑增量重构包括：参与应急恢复的健康导航卫星基于一致的链路时序计划、故障状态信息和候选链路可行性信息，按照相同的确定性重构规则独立进行计算，保持未受所述节点故障和星间链路故障影响的原计划星间链路不变，对因故障而失去原计划建链对象的健康导航卫星执行替代建链对象选择，并在存在满足建链条件的候选导航卫星时形成应急新增星间链路，获得一致的应急拓扑。

13、进一步地，针对因所述节点故障和星间链路故障而失去原计划建链对象的健康导航卫星构造替代建链候选集合，所述替代建链候选集合由满足以下全部条件的候选导航卫星组成：与所述健康导航卫星在对应时隙具备星间链路建立条件；不属于故障节点；其所配置的快速切换星间测量终端在所述对应时隙未被占用；不是所述健康导航卫星自身。

14、进一步地，各参与应急恢复的健康导航卫星按照相同的受影响时隙处理顺序和受影响导航卫星处理顺序，当所述替代建链候选集合非空时，对所述替代建链候选集合采用确定性候选选择规则获得唯一替代建链对象。所述确定性候选选择规则基于以下性能补偿因素进行排序：增加测距邻居多样性、增加跨对地能力类别的星间链路、恢复原故障时隙的有效星间链路；在所述性能补偿因素相同时，采用预先约定的节点标识顺序进行确定性消歧。

15、进一步地，当从所述替代建链候选集合中选择候选导航卫星作为替代建链对象，并与所述健康导航卫星形成应急新增星间链路后，将所述健康导航卫星和所述替代建链对象均标记为对应时隙已占用，使后续确定性分布式拓扑增量重构不再将二者作为所述对应时隙的空闲候选建链对象。

16、s3、对于形成应急新增星间链路的受影响时隙，根据所述应急拓扑更新计划建链对象；当所述应急新增星间链路的对端节点为所述本地路由执行表中的目的节点时，将对应转发标志设置为允许转发状态，通过所述应急新增星间链路进行一跳直达转发；当所述应急新增星间链路的对端节点不是所述目的节点时，不利用所述应急新增星间链路推导新的多跳路由，并保持对应数据的缓存状态。

17、s4、在应急拓扑统一生效时刻启用所述应急新增星间链路及对应的一跳直达转发关系，所述应急拓扑统一生效时刻对齐至所述导航卫星网络的预定同步切换边界。

18、进一步地，所述应急拓扑统一生效时刻依据故障事件参考时刻以及预设的故障状态传播上界、拓扑增量重构计算上界和同步保护余量确定；所述预定同步切换边界包括统一时隙边界和帧边界；将所述转发标志设置为禁止转发状态的操作在各参与应急恢复的健康导航卫星获得相应故障状态信息后即时生效，所述应急新增星间链路和对应的一跳直达转发关系在所述应急拓扑统一生效时刻生效。

19、s5、在所述应急拓扑生效后，对于仍处于缓存状态的数据，当时间推进至后续时隙，且所述本地路由执行表中该后续时隙的原路由表项指示的计划建链对象处于正常状态、所述原路由表项的转发标志处于允许转发状态时，按照所述原路由表项继续逐跳转发步骤s2中保存在本地缓存中的待发送数据。

20、进一步地，在执行所述快速应急恢复方法的同时，将所述故障状态信息提供给地面计算设备和具备全局计算能力的星上计算节点中的至少一者，执行长期全局链路时序计划重构和基于重构后链路时序计划的完整时空路由重计算；在所述长期全局链路时序计划和所述完整时空路由计算完成并分发后，在长期全局恢复统一生效时刻将所述导航卫星网络由应急状态切换至长期全局恢复状态。

21、（三）有益效果

22、（1）本发明充分利用导航卫星为获取多样化星间测量数据而在连续时隙间动态切换建链对象的运行特性。相关时隙的计划星间链路失效时，不将其等同于源节点与目的节点长期不可达，而是通过缓存等待后续时隙的正常时空路径机会，从而避免在应急阶段进行路径重算。

23、（2）本发明在路由侧仅需对故障相关计划建链对象进行匹配、修改转发标志并管理缓存数据，不需要重新执行全源-全目的多跳时空路由搜索；在拓扑侧仅针对故障影响范围增量补充星间链路，而保持未受影响链路不变，从而显著降低故障应急恢复的星上计算量。

24、（3）本发明在导航卫星获得故障状态信息后即可立即将故障相关转发标志设置为禁止转发，能够在拓扑补链尚未统一生效以及长期全局重构尚未完成之前及时阻断无效发送，降低数据丢失和故障方向数据持续积压的风险。

25、（4）本发明采用一致输入、统一处理顺序和确定性候选选择规则，使各导航卫星能够独立执行拓扑增量重构而得到相同的全网应急拓扑，降低故障后新增链路逐一协商所需的控制开销，并适合星上分布式运行。

26、（5）本发明的拓扑增量重构在故障相关链路失效的基础上，保持所有未受故障影响的计划星间链路不变，仅针对故障造成的链路空洞新增替代星间链路。因此，未受故障影响链路所对应的原有时空路由无需随拓扑重构而改变；路由侧仅需对故障相关路由表项进行转发抑制，并对应急新增星间链路两端之间可直接确定的一跳转发关系进行增量更新，不利用新增链路在应急阶段重新推导复杂多跳路由。由此，拓扑重构本身不会触发全网路由的大规模变更，在对故障造成的连接能力损失进行一定程度补偿的同时，进一步降低路由应急恢复的计算量和修改范围。

27、（6）本发明将“收到故障信息后的即时路由保护”和“统一生效时刻后的应急拓扑切换”分离，使各卫星能够尽早停止错误转发，同时保证应急新增星间链路两端在同一时间边界执行一致的建链动作。

28、（7）本发明所述快速应急恢复与后续全局拓扑优化及完整时空路由重计算不冲突，能够作为长期全局恢复结果可用之前的过渡运行机制，在优先保证网络尽快恢复正常运行的同时，为后续全局性能优化保留接口。