【论文】略读笔记7-前沿-基于图的工作流卸载

📖《A Novel Graph-Based Computation Offloading Strategy for Workflow Applications in Mobile Edge Computing》

🎯需求

• 移动边缘计算（MEC）正被越来越多研究者关注。
  • 随着各种智能终端设备计算能力的不断提高，越来越多的智能应用部署在智能物流等移动终端设备上。同时，终端设备提交的大量计算请求可以卸载到云数据中心。但是，带宽有限的公共网络会导致明显的延迟，这对于许多延迟敏感的应用程序来说是不可接受的。如今，移动边缘计算（MEC）已被广泛用于提供从网络边缘到终端设备的计算资源，以减少响应延迟。终端设备上的计算任务可以卸载到边缘服务器，通过低成本和高带宽传输（如5G和WIFI网络）执行。计算卸载通过减少终端设备的响应延迟和能耗，在有效提高基于 MEC 的应用的服务质量 （QoS） 方面发挥着关键作用。
• 随着移动边缘计算 （MEC） 的快速发展，对在边缘运行复杂应用程序的需求不断增加。这些复杂的应用程序可以表示为显式指定任务依赖项的工作流。
  • 例如，在基于UAV（无人机）的智能交付系统中，有许多复杂的应用，例如动态路线规划，障碍物检测和面部识别。
  • 本文重点介绍以数据为中心的科学工作流。具体来说，表示为每个任务的输入数据或是否执行的任务依赖关系取决于前一个任务的执行结果。
• 为了实现更好的服务质量（QoS），计算卸载在MEC环境中被广泛使用。
  • 例如，无人机受到其计算能力和电池寿命的限制，无法执行上述计算密集型任务。在MEC环境中，通过计算卸载技术可以有效降低无人机的能耗和任务响应时间。

🚧现状

• 然而，许多现有的计算卸载策略只关注独立的计算任务，而忽略了任务依赖关系。
• 一般来说，所有实际应用都可以用线性（即顺序）和非线性（即并行、选择性和迭代）结构工作流的混合来表示。它需要计算卸载策略应该能够同时处理线性和非线性结构。
  • 贪婪类型的策略已被广泛用于在短时间内获得可行的解决方案，但它们无法产生最佳的卸载决策。
  • 为了提高决策的质量，许多研究采用粒子群优化（PSO）和遗传算法（GA）等搜索算法，通过迭代过程搜索最佳卸载决策，这可能会产生大量的时间开销。
    • 这些基于搜索算法的算法通常很耗时，因此不适合MEC中许多对时延敏感的复杂应用。
  • 目前，大多数计算卸载策略要么简单但不够好，要么太耗时而不适合对时滞敏感的复杂应用。
• 因此，在我们最近的工作中提出了一种高效的基于图的策略，但它只能处理具有线性（即顺序）结构的简单工作流应用程序。

🛩创新

• 该文针对MEC中的工作流应用提出了一种基于图分区技术的计算卸载策略。
  • 考虑了复杂任务依赖关系对计算卸载决策的影响，并在给定的期限约束下有效地优化了终端设备的能耗。
    • 请注意，本文不考虑边缘服务器的能耗。这是因为边缘服务器通常连接到电网，因此它们的能耗不被视为MEC环境中的限制因素。
  • 具体来说，
    • 这种策略可以处理具有非线性（即并行、选择性和迭代）结构的复杂工作流应用程序。
    • 同时，利用基于图的划分技术，可以找到截止时间约束下终端设备能耗最低的卸载决策方案。
• 本文的贡献总结如下：
  1. 该文针对基于MEC的复杂应用提出了一种新颖的非线性工作流程模型。该模型基于 WDG（工作流依赖关系图），它既考虑了复杂的任务依赖关系，又考虑了降低终端设备能耗的目标。
  2. 我们提出了一种基于WDG的新型基于图的计算卸载策略，名为Graph4Edge-非线性，该策略可以在给定的期限内以最小的终端设备能耗找到最佳的计算卸载决策。它的性能明显优于流行的基于搜索算法的策略。
  3. 介绍了真实世界无人机交付系统的案例研究，以及在基于MEC的工作流程应用的FogWorkflowSim平台上的广泛仿真实验。实验结果表明，所提策略的有效性，以及优于其他代表性策略的整体性能，特别是在策略运行时间方面。

📊效果

• 我们已经全面评估了我们在FogWorkflowSim平台上针对复杂工作流程应用程序的策略。大量数值结果表明，与PSO和GA相比，所提策略可有效降低终端设备能耗7.81%和9.51%。同时，策略运行时间分别为PSO和GA的1%和0.2%。

🧠疑问

1. 具体使用了什么图划分算法？

🗺参考文献

[1] X. Li, T. Chen, D. Yuan, J. Xu and X. Liu, “A Novel Graph-Based Computation Offloading Strategy for Workflow Applications in Mobile Edge Computing,” in IEEE Transactions on Services Computing, vol. 16, no. 2, pp. 845-857, 1 March-April 2023, doi: 10.1109/TSC.2022.3180067.