【论文】略读笔记23-前沿-基于模仿学习的在线车载边缘计算任务调度

📖《Imitation Learning Enabled Task Scheduling for Online Vehicular Edge Computing》

🎯需求

• 车载边缘计算（VEC）是一种基于车联网的有前途的范式，可为终端用户提供计算资源，减轻蜂窝网络的繁重流量负担。
  • 随着智慧城市的建立和物联网技术的发展，智慧交通、娱乐资源共享、公共安全、应急等具有位置和时延要求的服务和应用正在迅速增加。每天都有海量数据产生，对灵活的网络管理和计算资源有均衡的需求。车载边缘计算（VEC）有望通过将计算密集型任务迁移到网络边缘来应对车联网（IoV）的挑战。路侧单元（RSU）是一种沿道路部署的基础设施，为各种车辆提供网络接入。
  • 为了建设绿色城市，有效利用能源，为过往车辆提供无缝服务，VEC必须制定节能政策。根据名为SMARTer2030的研究报告，利用信息和通信技术引起的二氧化碳排放量正以平均每年6%的速度增长。到2020年底，它们将占全球排放量的12%。此外，纯电动汽车和混合动力汽车将在不久的将来主导汽车市场。因此，网络运营商和车辆的巨大能源需求促使我们研究VEC网络的节能政策。
  • 目前，VEC的框架可分为 “基于基础设施的VEC” 和 “无基础设施的VEC两种”。
    • 对于前者，VEC 服务器总是与 RSU 合并以缓存内容或提供计算资源。
    • 对于后者，可以探索移动和停放车辆中的闲置资源来支持VEC。由于无基础设施的VEC不需要额外的网络部署，可以有效整合闲置的网络资源，因此近年来越来越受到关注。
  • 尽管无基础设施的VEC可以为道路上的用户提供卸载服务，但在高度动态的车辆网络中应仔细设计任务调度策略。
    • 这是因为车载应用总是需要实时响应，如何满足VEC网络中对延迟敏感的任务，以及如何在服务时间有限的动态服务器之间调度它们，成为一个主要问题。
    • 然而，考虑到动态提供方服务器的服务时间有限，为无基础设施的VEC设计解决方案是相当困难的。一般来说，网络中参与的车辆可以分为两类，即服务提供车辆（SPV）和服务需求车辆（SDV）。前者充当资源提供者，提供计算服务；后者可以访问网络服务并将任务卸载到 SPV。我们交替提及“SPV”和“VEC服务器”这两个术语，因为VEC服务器是由SPV在我们设计的算法中形成的。
• 在本文中，我们考虑了一个具有动态拓扑结构、不稳定连接和不可预测运动的 VEC 网络。
  • 车内车辆可以将计算任务卸载到由车载资源形成的可用相邻 VEC 集群，目的是最大限度地降低系统能耗并满足任务延迟限制。

🚧现状

• 对于在线任务调度，现有的研究要么设计启发式算法，要么利用机器学习，例如深度强化学习（DRL）。然而，这些算法对于大规模网络来说搜索效率低，收敛速度慢，效率不够高。
• 包括多个SPV和SDV在内的无基础设施VEC面临的挑战可以总结如下：
  • 1）现有研究总是允许 SDV 将其任务卸载到相邻的 SPV，或者将多个副本发送到 SPV 进行处理，以保证任务延迟约束。
    • 但一方面，单纯将任务分流给邻居可能会导致 SPV 负担不平衡，资源利用率低。
    • 另一方面，发送多个副本会浪费大量网络资源。因此，如何有效管理 SPV 上的闲置资源亟待深入研究。
  • 2）在无基础设施的 VEC 中，SPV 定期向周围的 SDV 广播其信息，包括位置、速度和移动方向，SDV 根据这些信息安排其任务。
    • 但是，频繁的信息交换会造成较大的通信开销，应减少这种开销以提高通信效率。
  • 3）对于在线任务调度，传统算法总是采用启发式搜索策略。
    • 然而，在这种高度动态的网络拓扑结构中，它们可能具有较低的搜索效率和较高的计算复杂性。
    • 此外，有限的服务时间、不稳定的VEC服务和动态的车辆运动使得在线任务调度具有相当大的挑战性。因此，有必要通过考虑这些不同的参数来找到一种灵活的策略来解决任务调度问题。
  • 4）通常，深度强化学习（DRL）用于解决复杂环境下的任务调度问题。
    • 然而，基于 DRL 的算法通常收敛速度较慢。此外，由于角色不稳定、运动不确定性和车辆数量庞大等原因导致网络状态的频繁演化，导致 DRL 的状态和动作空间超大。学习算法计算延迟大，导致学习过程中数百万步的网络性能极差，这是在线调度所不能接受的。因此，有必要设计一种收敛速度快的基于学习的算法来保证在线系统性能。

🛩创新

• 我们提出了一种基于模仿学习的在线任务调度算法，该算法在初始阶段具有接近最优的性能。特别是，专家可以通过离线几个样本求解制定的优化问题来获得最优调度策略。对于在线学习，我们按照专家的演示来训练代理策略，理论上具有可接受的绩效差距。

  • 针对上述挑战，本文提出了一种在线VEC算法，命名为IELTS。
    • 对于第一个挑战，我们建立了VEC模型，并将任务调度问题表述为优化问题。RSU 用于帮助在不同服务器之间调度任务，充当路由器或网关的角色。我们的解决方案仍然没有基础设施，因为它不需要 RSU 来缓存或处理 SDV 的计算任务。在此基础上，分析 SPV 在 RSU 覆盖中的服务能力，并通过整合其闲置资源进行聚类。
    • 为了应对第二个挑战，每个 RSU 都用于维护集群级别信息，而 SPV 级别信息则在其集群内进行维护。因此，SPV 和 RSU 之间的通信开销可以大大降低。
    • 为了解决最后两个挑战，我们设计了一种基于模仿学习的方法，以克服传统算法带来的搜索效率低、收敛速度慢等缺点。实际上，模仿学习是一种机器学习方法，允许智能体模仿参考策略（或专家的演示），这些策略是原始问题的有效解决方案。由于时间复杂度高，参考策略无法直接在线执行。因此，应制定学习政策，以便通过培训过程进行模仿。据我们所知，本文是研究高动态VEC网络中边界仿真学习的在线任务调度问题的早期努力。

• 我们的贡献可以总结如下：

  • 我们首先通过考虑通信和计算资源建立系统模型，并将任务调度问题表述为优化问题。为了解决公式化的问题，我们将其分解为两个子问题，即资源聚合和任务调度，目的是将任务分配给合适的SPV集群。
  • 为了解决第一个子问题，我们分析了本地SPV在RSU覆盖中的服务能力，通过分析，我们发现聚类SPV可以建模为M/G/K/N在服务期间排队系统。在此基础上，可以通过考虑形成的聚类来对所制定的优化问题进行变换。然后，通过模仿专家的策略进行基于集群的任务调度，可以解决第二个子问题，其中收敛时间可以大大缩短。
  • 我们以理论的方式分析了算法的性能，并证明了我们的算法可以达到与专家提供的性能差距。此外，我们还推导了我们设计的任务调度算法的能耗上限。据我们所知，这项工作在通过模仿学习解决VEC网络中的任务调度问题方面做出了早期努力。
  • 我们基于包含真实世界出租车轨迹的数据集进行实验。性能结果表明，该算法在平均能耗、本地SPV任务处理率和平均任务执行延迟方面均有优势，与启发式在VEC服务器和远程云之间调度任务的基准相比，提高了50%以上。

📊效果

• 性能结果表明，我们的解决方案具有显著优势，与基准相比，改进了 50% 以上。

🧠疑问

---

---

• 希望这篇博客对你有帮助！如果你有任何问题或需要进一步的帮助，请随时提问。
• 如果你喜欢这篇文章，欢迎动动小手 给我一个follow或star。

🗺参考文献

[1] X. Wang, Z. Ning, S. Guo and L. Wang, “Imitation Learning Enabled Task Scheduling for Online Vehicular Edge Computing,” in IEEE Transactions on Mobile Computing, vol. 21, no. 2, pp. 598-611, 1 Feb. 2022, doi: 10.1109/TMC.2020.3012509.