GSCF：无人机辅助边缘计算中服务间隙最小化与资源优化的联合调度框架

《Ad Hoc Networks》：GSCF: A joint scheduling framework for service gap minimization and resource optimization in UAV-assisted edge computing

　　

•IISC从突发性任务流中形成可追溯、服务兼容的微集群。•位置依赖型拓扑平衡了接近度、能耗和移动成本。•可行边缘筛选、MCMF分配、KKT分配、验证和修复强制执行耦合约束。

引言

随着物联网设备的快速增长，大量数据需要及时处理和分分析。相关的工作负载包括数据预处理、模型训练、目标识别以及其他特定应用的计算，这些都需要大量的计算资源。然而，由于功耗和计算能力有限，物联网设备难以在本地完成计算密集型和时延敏感型任务。因此，MEC作为一种互补的任务处理范式被引入[1]。通过提供低时延和高带宽，MEC服务器支持了苛刻的应用需求[2]、[3]、[4]，并减少了本地设备的工作负载[5]。然而，传统MEC服务器仍受限于部署成本、连接不稳定和固定服务区域。

无人机辅助MEC将固定的地面网络扩展为空地一体化网络。凭借其高机动性和服务缓存能力[6]、[7]、[8]，无人机可以灵活快速地部署。当地面MEC资源不足时，它们提供计算卸载服务[9]，同时其视距链路可以改善通信可靠性[10]。无人机MEC对于基础设施匮乏的环境尤为相关，包括偏远山区的区域检查和科学考察。在这些环境中，薄弱或不可用的地面基础设施和恶劣的环境条件会降低网络覆盖率，形成通信孤岛。因此，空地协作系统对于保持任务连续性至关重要。

为了研究基础设施匮乏环境中无人机MEC调度，本文考虑大面积森林监测作为代表性应用场景。偏远森林地区通常缺乏连续的地面通信和邻近的边缘计算基础设施。复杂地形、茂密树冠和自然障碍会增加非视距传播和植被穿透损耗的可能性，从而降低空地链路质量并减少可行的无人机卸载路径数量。同时，火灾、烟雾和其他突发事件会同步触发许多邻近传感器，产生具有严格截止时间和高计算需求的突发性监测任务。当本地设备无法完成这些任务，且可达无人机进一步受限于链路质量、计算容量、剩余能量、服务镜像可用性或截止时间时，本地-无人机边缘层可能无法提供可行的执行路径，这使得GBS回退尤为重要。只要其自身的通信、计算、排队和截止时间条件可行，完整的GBS执行就被视为候选方案。只有当本地、无人机和GBS执行路径都不可行时，任务集群才被视为硬丢弃。这种因果链促使了对流聚合、能量感知拓扑规划和资源调度的联合处理。

为无人机辅助MEC系统设计有效的计算卸载方案面临三个耦合挑战：

(1) 突发性任务到达带来调度规模挑战。大面积森林监测表现出强烈的时空突发性。当异常事件发生时，受影响设备会在短时间内产生许多高度相关的任务。许多现有调度算法直接建模离散任务[7]、[11]。在每个决策窗口内为每个原始任务做出完整的卸载和资源分配决策会迅速增加必须处理的调度实体、候选路径和耦合约束的数量。

(2) 能量和移动异质性影响候选服务拓扑。无人机在飞行历史、工作负载、缓存状态和剩余能量水平方面存在差异。剩余能量低或移动成本高的无人机应被分配较小的候选区域，而能量充足且移动成本较低的无人机可以支持较大的区域。由此产生的区域定义了候选无人机路径而非最终执行结果；每个候选路径仍需满足链路、服务镜像、CPU、能量和截止时间条件。因此，无人机覆盖缺口是一种通信或拓扑状态，而非立即的任务失败，因为本地或GBS完整执行可能仍然可行。

(3) 在线决策必须在每个调度时隙内满足显式硬约束。DRL和多智能体学习方法可以在动态环境中学习耦合策略[12]、[13]、[14]、[15]，但其性能依赖于训练分布、样本可用性和动作空间设计，并且显式满足通信、截止时间、缓存、CPU和能量约束通常需要额外机制。启发式方法[16]、[17]避免了训练开销，但可能牺牲全局协调或对初始化和搜索规则变得敏感。因此，结构化的在线方法必须在计算可行性、约束透明度和调度质量之间取得平衡。

鉴于这些挑战，本文专注于减少基础设施匮乏地区的服务缺口并联合调度异构资源。无人机覆盖缺口是指缺乏满足覆盖半径和SNR要求的有效无人机链路，而本地执行和GBS回退仍然是可能的结果。当一个完整的任务集群被分配给GBS回退层时，记录一个服务缺口。这种完成的回退结果会产生额外的服务缺口成本，而硬丢弃是指没有任何完整的本地、无人机或GBS执行路径可行的最终状态。基于这些定义，GSCF联合协调完整的任务卸载、候选服务拓扑和计算资源分配，以减少GBS回退和硬丢弃风险。

GSCF提供了耦合MINLP的结构化近似分解。在每个时隙，服务兼容流聚合将原始任务映射为可追溯的微集群。它们的代表位置和无人机状态随后输入位置依赖型广义拓扑规划器。由此产生的候选无人机区域与本地和GBS模式通过可行边缘筛选相结合，之后MCMF分配、基于KKT的CPU分配、聚合验证和确定性修复产生满足约束的调度方案。

• 我们提出了一种面向突发性任务调度的服务兼容增量流聚合机制。IISC将??个活跃原始任务聚合为??个可追溯微集群，其中??≤??，同时保持总数据量、总CPU周期需求、最早成员截止时间、唯一服务类型以及通信、拓扑和调度模块所需的数据加权代表位置。原始成员映射仍然可用于执行和追溯。

• 我们开发了一种位置依赖型能量感知广义拓扑规划机制。位置依赖权重????(??,??)将移动后的投影剩余能量与区域迁移惩罚相结合，广义距离????(??,??)平衡了这种有效服务能力与空间接近度。较低的有效能量或较高的移动成本会增大广义距离，倾向于收缩候选区域，而相反状态则倾向于扩大区域。由此产生的分区提供候选无人机路径，但不替代后续的执行可行性检查。

• 我们设计了一条约束一致的联合资源决策流水线。模式特定的边缘生成排除了单独不可行的本地、无人机和GBS路径。MCMF在启用图上最小化完整候选分配的可分代理成本，KKT条件为固定分配分配无人机CPU资源，聚合验证和确定性修复执行剩余的耦合资源条件。有限边缘删除和有界外循环保证终止，因此返回的调度方案满足流水线检查的所有约束。

当前模型假设飞行高度??在每个独立的调度运行之前预设，并在该运行期间保持固定。在线决策仅更新二维水平位置，而??继续决定三维空地距离、仰角、路径损耗和传输速率。这种设置适用于具有预定义飞行层或受控空域的任务。在线高度优化、垂直运动能量和三维障碍物规避不在当前模型范围内。当任务位置、数据量、截止时间、服务类型和计算需求可用，且链路和资源状态可估计时，该框架可适应其他无人机MEC应用。

本文其余部分组织如下。第2节回顾了无人机辅助边缘计算、基于几何的拓扑规划和资源调度。第3节介绍了三层森林监测系统及其通信、计算、队列、缓存和能量模型。第4节建立了完整卸载和资源优化问题。第5节开发了服务兼容IISC聚合、位置依赖型广义拓扑规划、可行边缘筛选、MCMF分配、KKT分配、验证和修复，以及有限终止和复杂度分析。第6节在考虑的设置下评估了调度可靠性、能量平衡、可扩展性和适用性边界。第7节总结了论文并讨论了局限性和未来工作。

节段摘录

相关工作

本节回顾了复杂动态环境中的无人机MEC研究，重点关注服务提供、基于几何的拓扑控制和联合资源调度。表1从核心算法、目标和关键特性方面比较了代表性研究。

最近的MEC研究已扩展到静态城市网络之外，进入基础设施匮乏和高度动态的环境。Chen等人[18]研究了低地球轨道（LEO）之间的协作卸载

系统模型

图1展示了用于大面积森林监测的无人机辅助MEC系统。该系统在离散时间槽??∈??={1,…,??}中运行，包含三个协作层。

(1) 地面层：密集部署的异构物联网设备收集图像、环境测量和地理空间信息。突发事件可能同步触发邻近设备并产生高度相关的原始任务。第??个不可分任务定义为????=?????,????,????,????,?????，其中????是...

问题构建

当微集群??被分配给GBS回退执行时，记录一个服务缺口。GBS卸载会产生额外的服务缺口成本但仍然成功，而硬丢弃是指没有任何可行的本地、无人机或GBS执行路径的最终失败状态。无人机覆盖缺口是链路级条件，其调度影响反映在三种执行路径的可用性上。为了将时延、任务能量、无人机激活、负载均衡和回退可靠性统一为一个...

整体GSCF工作流程

问题P1将完整的离散卸载与连续水平位置、CPU分配、队列、缓存状态、有限能量预算和模式特定截止时间耦合在一起。因此直接的整体优化在计算上是困难的。如图2所总结，GSCF将在线信息流分离为三个连接的阶段。这些阶段产生计算可行且约束一致的近似调度方案。(1) 服务兼容流聚合阶段：IISC...

仿真设置

仿真研究在大面积森林监测场景中评估GSCF。本节首先描述环境和参数，然后定义性能指标和基线算法，最后呈现实验设计和结果。

结论与未来工作

本文开发了GSCF，用于基础设施匮乏无人机辅助边缘计算系统中的服务缺口最小化和协调资源调度。该框架连接了服务兼容IISC聚合、位置依赖型能量感知广义拓扑规划，以及包含可行边缘构建、MCMF候选分配、基于KKT的无人机CPU分配、聚合验证和确定性修复的约束一致资源决策流水线。三个模块交换...

CRediT作者贡献声明

Xin Gao：撰写 - 原稿、可视化、验证、方法论、调查、形式分析、数据整理、概念化。Yi Hong：撰写 - 审阅与编辑、监督、项目管理、方法论、调查、资金获取、形式分析、概念化。Chuanwen Luo：撰写 - 审阅与编辑、监督、项目管理、方法论、调查、资金获取。Xin Fan：撰写 - 审阅与编辑、验证、监督、...

利益冲突声明

作者声明他们没有任何已知的竞争性财务利益或个人关系，这些利益或关系可能会影响本论文中报告的工作。

致谢

本工作得到了中国国家自然科学基金的资助（项目编号：62572058、62002022和U24A20244）。

Xin Gao|Yi Hong|Chuanwen Luo|Xin Fan