[Paper] 精确、高效且可靠的多目标多约束 IoT 工作流调度在 Edge‑Hub‑Cloud 赛博物理系统中

Source: arXiv - 2604.24340v1

概述

本文提出了一种 精确的多目标调度算法，用于跨越边缘设备、枢纽和云端的物联网工作流。通过将问题建模为连续时间混合整数线性规划（MILP），作者在满足一整套真实约束（截止时间、内存、存储、处理能力等）的同时，同时最小化延迟、能耗和可靠性损失。他们的结果显示，相较于最先进的启发式方法有显著提升，即使在实际工作流规模下也能实现可接受的运行时间。

关键贡献

• 整体 MILP 公式，联合优化边缘‑枢纽‑云工作流的三项冲突目标（延迟、能耗、可靠性）。
• 全面的约束处理：显式建模截止时间、可靠性阈值、CPU/内存/存储限制以及异构多核能力。
• 选择性任务复制策略，在不产生盲目复制开销的情况下提升可靠性。
• 扩展的基准启发式，实现与精确方法的公平正面对比。
• 广泛评估：在真实物联网工作流和合成图（任务数达数十）上，跨多种系统配置进行实验，展示每个目标约 30 % 的提升。
• 可扩展性验证：对典型 CPS 部署相关的问题规模，求解时间保持在秒到分钟级别。

方法论

1. 问题建模 – 将每个工作流表示为有向无环图（DAG），其中节点是任务，边表示数据依赖。
2. 决策变量 – 二元变量决定每个任务在 何处（边缘、枢纽、云）运行以及 是否 创建副本。连续变量捕捉开始时间和资源使用情况。
3. 目标函数 – 三个指标的加权和：
   • 延迟（工作流的完成时间）
   • 能耗（所有设备的 CPU + 通信能耗）
   • 可靠性惩罚（任务失败概率，复制可降低该概率）
     权重可以调节，以反映开发者的优先级。
4. 约束条件 –
   • 时序：任务开始时间必须遵守前置关系并满足全局截止时间。
   • 资源：每个节点的 CPU、内存、存储上限；多核调度通过容量约束建模。
   • 可靠性：整体失败概率必须低于用户定义的阈值。
   • 复制控制：限制副本数量，以避免不必要的开销。
5. 求解技术 – 使用商业或开源优化器（如 CPLEX、Gurobi）求解 MILP。由于模型采用连续时间，避免了基于时间槽的调度器常见的离散化误差。
6. 基准启发式 – 将现有的列表调度启发式算法扩展以满足相同约束，提供用于比较的基准。

结果与发现

• 运行时间：对于任务数约 30 的工作流，MILP 在标准工作站上 ≤ 2 分钟内求解完毕——可接受的离线部署规划时间。
• 可扩展性：合成测试显示求解时间随规模近线性增长至测试上限；超过约 50 个任务后运行时间急剧上升，建议对更大的 DAG 采用混合方法。
• 敏感性：通过调整目标权重，开发者可在不重新设计模型的前提下优先考虑延迟（如实时控制）或能耗（如电池供电传感器）。

实际意义

• 部署规划工具 – 云/边缘编排平台可以将 MILP 嵌入为“假设”优化器，在运行前生成最优放置图。
• 边缘 AI 流水线 – 对于必须满足严格延迟和能耗预算的推理任务，调度器可以决定哪些层在本地运行，哪些在枢纽/云端运行，同时自动为安全关键阶段添加冗余。
• 服务水平协议 (SLA) – 运营商可以通过将 SLA 参数直接输入目标权重和约束，保证延迟和可靠性阈值。
• 能耗感知固件更新 – 在向异构边缘设备群部署更新时，模型可以调度下载、验证和安装任务，以最小化峰值功耗。
• 混合边缘‑枢纽‑云架构 – 该工作验证了对实际 CPS 规模进行精确优化是可行的，鼓励设计者超越仅使用启发式方法的解决方案。

限制与未来工作

• 可扩展性上限 – 对于超过 50 任务的工作流，MILP 计算量变大；未来研究可以探索分解、列生成或学习引导的启发式方法，以在更大规模下保持最优性保证。
• 静态工作流 – 当前模型假设事先已知 DAG。将模型扩展到处理动态任务到达或运行时重新调度（例如节点故障）将提升适用性。
• 网络可变性 – 通信延迟/能耗使用固定参数建模；引入随机网络条件或自适应带宽分配可以提升真实性。
• 硬件异构性 – 虽然已捕获多核异构，但新兴加速器（TPU、FPGA）未显式建模；将加速器特定约束纳入是自然的下一步。

结论：通过提供一个精确的、多目标调度器，能够兼顾边缘‑枢纽‑云的全部约束，该工作为开发者提供了构建可靠、低延迟和能效高的物联网应用的强大新工具——前提是工作流规模保持在已验证的最佳范围内。

作者

• Andreas Kouloumpris
• Georgios L. Stavrinides
• Maria K. Michael
• Theocharis Theocharides

论文信息

• arXiv ID: 2604.24340v1
• 分类: cs.DC
• 发布日期: 2026年4月27日
• PDF: 下载 PDF