一种基于算力感知时空拓展图与资源预留的时延确定性天基路由方法及系统

本发明属于卫星通信网络、天基算力网络和确定性路由，具体涉及一种基于算力感知时空拓展图与资源预留的时延确定性天基路由方法及系统。

背景技术：

1、低轨卫星网络由大量高速运动的卫星节点组成，其网络拓扑具有高动态特性。卫星轨道参数、星历信息与通信链路情况等通常可以预先获得，因此，网络拓扑在一定规划时域内具有可预测性。随着星载计算能力提升，卫星节点除承担数据转发外，还可执行图像处理、目标识别和数据压缩等计算任务，使路由决策需要同时考虑通信链路和算力分布。

2、在卫星测控、灾害监测与应急救援等场景中，任务通常具有明确的截止时间，其业务有效性取决于任务数据能否在规定时限内完成传输、计算与结果返回。由于节点排队、带宽竞争及算力负载等均可能导致任务超时，因此需要在任务执行前完成可行性判断，并通过路径规划和分时间片资源预留，为被接纳任务提供确定性时延保障。

3、现有卫星路由方法主要依据链路连通关系、传输时延或链路负载选择传输路径，难以直接处理任务传输与星载计算相互耦合的问题。快照图能够将动态拓扑离散为多个时间片，但对跨时间片的数据缓存和持续计算过程描述不足。传统时空拓展图在快照图基础上，基于通信边连接同一时间片内的可通信节点，并通过存储边连接相邻时间片的同一节点，以描述数据传输和缓存等待过程，但该模型未统一表征卫星节点的异构计算能力、计算服务类型、计算处理时段及相应资源占用。部分研究进一步在时间扩展图中引入计算节点或计算功能，但主要用于描述单一任务流或单次计算过程，对计算服务类型、计算过程的持续时段以及多个任务对通信、计算和存储资源的分时间片占用缺少完整描述。

4、在算力感知调度方面，现有方法主要包括三类：一是将计算时延设为节点权值、传输与传播时延设为链路权值，分别搜索“任务源节点—计算节点—目的节点”的算传路径；二是由meo控制器汇聚链路和算力状态，统一选择计算节点及传输路径；三是采用深度强化学习或图神经网络，根据实时拓扑、节点负载和任务需求生成调度策略。但上述方法多以单任务时延、平均时延或长期收益为优化目标，通常基于当前状态逐任务决策，未明确记录任务在后续时间片对链路带宽、计算和存储资源的持续占用，也缺少已有任务资源预留的继承与释放机制。因此，多任务并发时可能出现资源重复分配，导致规划路径在实际执行阶段无法满足任务时延上限。

5、不同卫星节点配置的处理器类型、存储容量和通信能力存在差异，节点资源利用状态还会随任务执行而变化。仅根据静态资源能力选择计算节点，可能将任务分配至负载较高的节点；仅根据当前资源利用率、任务队列长度等动态状态进行决策，又难以反映节点的基础服务能力。同时，分层卫星网络中的资源分布在不同节点和管理区域，现有方法缺少针对计算服务需求与节点能力映射机制的设计，候选节点筛选范围较大，算力路由效率低。

6、多个任务在同一规划时域内到达时，彼此间将竞争链路带宽、节点计算资源和存储资源。按照任务到达顺序逐一进行路由和计算节点选择，容易使先到任务占用关键资源，导致后续任务无可行路径。若未记录路径在具体时间片内的资源占用，后续决策还可能重复分配已被活动任务使用的资源，使规划路径在实际执行时无法满足确定性时延需求。即使某条路径在生成时满足当前资源约束，若未对其在后续时间片内计划占用的资源实施预留，也无法避免新到任务再次占用同一链路或节点资源，导致原规划路径的传输、等待或计算过程被延迟。

7、因此，本技术设计了一种基于算力感知时空拓展图与资源预留的天基路由方法，将任务传输、计算处理和数据排队过程纳入统一模型，并结合卫星节点服务能力、动态资源状态和已有资源预留进行多任务联合决策，为多任务提供端到端时延保障，以提高天基算力路由的效率和网络资源利用效率。

技术实现思路

1、本发明的目的在于提供一种基于算力感知时空拓展图与资源预留的时延确定性天基路由方法及系统，以解决现有天基路由方法难以统一描述任务传输、计算处理和数据等待过程，且多任务竞争条件下规划路径可执行性不足的问题。

2、一种基于算力感知时空拓展图与资源预留的时延确定性天基路由方法，包括：

3、利用geo卫星层、meo卫星层与leo卫星层，构建基于软件定义网络的分层分域卫星网络架构；基于所述卫星网络架构，获取规划时域内卫星节点的轨道信息、链路状态及资源状态，将所述规划时域离散划分为多个时间片，并以当前决策时间片为起点建立滚动规划窗口；建立面向异构星载算力资源、存储资源以及通信资源的资源度量体系，表征各时间片内的星载资源状态；利用计算服务类型划分服务标识，通过卫星网络架构中卫星节点的静态资源能力与服务匹配结果，为卫星节点生成与所述服务标识对应的绑定标识，并建立服务标识与卫星节点之间的服务能力映射关系；在规划时间窗口内，根据卫星节点在不同时间片下的时间副本，引入计算边、存储边与通信边，构建算力感知时空拓展图；根据到达任务的服务标识，查询具有对应绑定标识的卫星节点，并结合剩余可用资源和时空可达性筛选候选算力节点；基于所述候选算力节点，生成候选算传路径；基于候选算传路径，建立多任务算传联合优化模型；求解所述多任务算传联合优化模型，确定任务接纳结果和候选算传路径选择结果；按照选定的候选算传路径实际占用资源的时间片实施资源预留，并通过资源释放与滚动更新维持资源状态一致性。

4、优选的，所述卫星网络架构中：geo卫星层与meo卫星层分别为一级控制层与二级控制层，leo卫星层为数据层；所述一级控制层用于维护全局网络状态并实施跨域策略协调；所述二级控制层用于汇聚所属区域内leo卫星节点的状态信息，维护区域算力状态表，执行候选路径生成、多任务算传联合优化和资源预留控制；所述leo卫星用于执行任务转发、计算处理和状态通告。

5、优选的，建立资源度量体系的方法包括：将星载资源划分为节点资源与链路带宽资源分别建模；其中，所述节点资源包含算力资源和存储资源，所述算力资源包含通用算力、并行算力、人工智能算力以及可重构算力四类；采用静态指标与动态指标相结合的混合式算力度量方法表征资源状态；其中，所述静态指标用于刻画卫星节点的基础服务能力，包括各类型算力容量、内存容量、存储容量和链路带宽容量；所述动态指标用于刻画各时间片内的资源占用状态，包括各类型算力利用率、内存占用率、存储占用率和带宽占用率；引入资源预留量，用于表征多任务场景下已分配但尚未执行的资源占用量；根据所述静态指标、动态指标和资源预留量，计算各时间片内卫星节点的剩余可用资源和链路的剩余可用带宽，完成资源度量体系的构建。

6、优选的，建立服务标识与卫星节点之间的服务能力映射关系的方法包括：按照计算服务类型划分服务标识，每一服务标识关联核心资源维度、重要资源维度、资源偏好权重、静态资源最低要求和服务能力评分阈值；对于任一卫星节点，当核心资源容量满足所述静态资源最低要求，且根据静态资源能力和所述资源偏好权重确定的服务匹配评分不低于所述服务能力评分阈值时，生成所述卫星节点与对应服务标识之间的绑定标识，并建立服务标识与卫星节点之间的服务能力映射关系。

7、优选的，构建算力感知时空拓展图的方法包括：引入滚动规划窗口，在所述滚动规划窗口内，将卫星节点在不同时间片下的时间副本构成算力感知时空拓展图的点集合；所述点集合中的每个时间副本节点携带有所述卫星节点在对应时间片内的资源状态信息、服务绑定标识信息及卫星基础运行状态信息；在所述点集合的基础上，引入通信边、存储边以及计算边构建算力感知时空拓展图的边集合；其中，所述通信边连接同一时间片内具有可用通信链路的时间副本节点，用于表征节点间的数据传输过程；所述存储边连接同一卫星节点在相邻时间片对应的时间副本节点，用于表征任务数据的跨时间片缓存过程；所述计算边设置于具有对应绑定标识且剩余资源满足任务处理要求的卫星节点，用于表征所述卫星节点提供对应计算服务的过程；通过所述点集合和边集合，构建得到统一描述传输、存储与计算过程的算力感知时空拓展图。

8、优选的，生成候选算传路径的方法包括：获取当前决策时间片内到达的任务，所述任务属性包含源节点、目的节点、服务类型、输入数据量、输出数据量、最大容忍端到端时延、任务计算工作量向量、链路带宽预留需求及计算节点资源需求；根据所述任务的服务类型，在所述算力感知时空拓展图中查询具备所述服务类型对应绑定标识的卫星节点集合，并结合各卫星节点在滚动规划窗口内的剩余可用资源及链路时空可达性进行筛选，剔除不满足任务资源需求或辅助约束指标阈值的节点，得到候选算力节点集合；对于所述候选算力节点集合中的每个候选算力节点，采用dijkstra算法分别搜索所述任务的源节点至候选算力节点的最小时延输入路径，以及候选算力节点至任务目的节点的最小时延输出路径；将所述最小时延输入路径、所述候选算力节点对应的计算处理过程以及所述最小时延输出路径依次连接，生成所述任务的一条候选算传路径；遍历所有候选算力节点，得到所述任务的候选算传路径集合。

9、优选的，建立多任务算传联合优化模型的方法包括：获取当前决策时间片内到达同一路由控制节点的任务集合以及所述任务集合中各任务对应的候选算传路径集合；为每个任务设置路径选择变量和任务接纳变量；所述路径选择变量用于指示所述任务是否选择对应的候选算传路径；所述任务接纳变量用于指示所述任务是否被接纳；根据各任务的候选算传路径的端到端时延及最大容忍端到端时延，计算各候选算传路径的相对时延，并确定被接纳任务中的最大相对时延；以最小化任务拒绝惩罚、最大相对时延与资源匹配代价的加权和为优化目标，建立多任务算传联合优化模型。

10、优选的，所述多任务算传联合优化模型包含如下约束：任务路径唯一性约束，用于保证每个被接纳任务唯一选择一条候选路径，未被接纳任务不选择路径；任务时延确定性约束，用于保证被接纳任务的端到端相对时延不超过1；最大相对时延约束，用于定义被接纳任务的最大相对时延变量，所述最大相对时延不小于任一被接纳任务候选路径的相对时延；通信链路带宽约束，用于保证同一时间片内所有被接纳任务在各链路上的带宽预留总量不超过对应链路的剩余可用带宽；计算节点资源约束，用于保证同一时间片内所有被接纳任务在各卫星节点上的计算资源占用总量不超过对应节点的剩余可用计算资源；节点存储容量约束，用于保证同一时间片内所有被接纳任务在各卫星节点上的存储资源占用总量不超过对应节点的剩余可用存储容量。

11、本发明还提供一种基于算力感知时空拓展图与资源预留的时延确定性天基路由系统，用于实现所述方法，包括：卫星网络架构构建模块，用于利用geo卫星层、meo卫星层与leo卫星层，构建基于软件定义网络的分层分域卫星网络架构；时间片划分模块，用于基于所述卫星网络架构，获取规划时域内卫星节点的轨道信息、链路状态及资源状态，将所述规划时域离散划分为多个时间片，并以当前决策时间片为起点建立滚动规划窗口；资源度量体系构建模块，用于建立面向异构星载算力资源、存储资源以及通信资源的资源度量体系，表征各时间片内的星载资源状态；服务能力映射模块，用于利用计算服务类型划分服务标识，通过卫星网络架构中卫星节点的静态资源能力与服务匹配结果，为卫星节点生成与所述服务标识对应的绑定标识，并建立服务标识与卫星节点之间的服务能力映射关系；时空拓展图构建模块，用于在规划时间窗口内，根据卫星节点在不同时间片下的时间副本，引入计算边、存储边与通信边，构建算力感知时空拓展图；候选算力节点筛选模块，用于根据到达任务的服务标识，查询具有对应绑定标识的卫星节点，并结合剩余可用资源和时空可达性筛选候选算力节点；候选算传路径生成模块，用于基于所述候选算力节点，生成候选算传路径；优化模型构建模块，用于基于候选算传路径，建立多任务算传联合优化模型；模型求解模块，用于求解所述多任务算传联合优化模型，确定任务接纳结果和候选算传路径选择结果；状态更新模块，用于按照选定的候选算传路径实际占用资源的时间片实施资源预留，并通过资源释放与滚动更新维持资源状态一致性。

12、优选的，候选算传路径生成模块、优化模型构建模块、模型求解模块及状态更新模块部署于meo卫星层的二级控制节点；所述二级控制节点用于汇聚所属区域内leo卫星节点的状态信息，维护区域算力状态表，执行候选算传路径生成、多任务算传联合优化及资源预留控制。

13、与现有技术相比，本发明的有益效果为：本发明通过算力感知时空拓展图统一描述任务传输、计算处理和数据等待过程，使候选路径的端到端时延及资源占用能够在路径生成阶段预先确定。本发明通过服务标识与绑定标识建立计算服务和卫星静态能力之间的映射关系，再结合动态资源状态筛选候选节点，能够减小路径搜索范围。本发明在有限候选路径集合上进行多任务联合优化，统一确定任务接纳结果和路径选择结果，能够协调不同任务之间的资源竞争。本发明将链路带宽和节点资源的预留绑定至具体时间片，并通过资源释放、预留继承和局部重规划维持资源状态一致性，从而提高规划路径的可执行性，为被接纳任务提供端到端时延保障。