【论文】略读笔记31-经典-去中心化调度

📖《Multi-Agent Imitation Learning for Pervasive Edge Computing： A Decentralized Computation Offloading Algorithm》

🎯需求

• 普适边缘计算是指仅依靠具有感知、存储和通信能力的边缘设备，实现点对点卸载，无需集中管理的一种边缘计算。
  • 边缘计算通过利用网络边缘的计算和存储资源来扩展传统的云计算架构。云可以安排任务由边缘设备在本地处理，而无需远程传输。
  • 随着5G和网络技术的发展，终端设备已经演进，具有强大的感知、计算和存储能力，为实现普适边缘计算（无处不在的边缘计算，Pervasive Edge Computing）铺平了道路。实际上，它是一种新颖的边缘计算，它只是利用边缘设备进行计算和存储，而无需集中管理。
  • 传统的边缘计算是云计算的补充，云计算和存储资源由边缘服务器提供，决策在后端做出。相比之下，普适边缘计算允许数据存储、处理和调度决策全部在网络边缘执行。因此，传统的边缘计算策略并不适合普适边缘计算环境，需要以完全去中心化的方式进行新的算法设计。
  • 普适边缘计算与传统边缘计算相比带来的优势可以归纳为四个方面。
    • 1）首先，它无需基础设施即可部署和维护专用云后端。
    • 2）其次，无需与云端通信，因为数据可以在用户附近处理，大大降低了传输延迟。
    • 3）此外，它通过在对等设备之间实现通信而不需要互联网连接，从而独立于连接。
    • 4）最后，不需要中央机构，设备可以自由地决定如何与他人协作，以及以何种方式实现可行和多样化的网络应用程序。
  • 普适边缘计算的应用从娱乐到工业的广泛应用。
    • 例如，在现场篮球比赛的现场，坐在不同位置的观众可以通过点对点通信从他们的角度与他人分享他们录制的视频。然后，通过聚合不同的片段，可以形成一个多角度观看的游戏视频。不同地点的观众可以全景观看现场比赛。另一个例子是协同驾驶，基于短距离通信技术，道路状况和事故现场的实时视频流可以直接在车辆之间共享。

🚧现状

• 尽管普适边缘计算可以为用户带来各种优势和便利，但通过考虑普适边缘计算网络中多个设备的效用公益，设计可行的计算卸载算法具有挑战性。挑战可归纳如下：
  • 1）与传统边缘计算相比，普适边缘计算允许设备在网络边缘做出决策，而无需集中管理。设备很难仅依靠点对点通信来获取整个网络状态。因此，对于他们来说，选择合适的边缘服务器（由其他设备组成）来根据部分观察来卸载任务是具有挑战性的。受此影响，如果没有合理的任务分配策略，很难保证任务完成时间。
  • 2）在多设备环境中，每个设备都打算最大限度地提高自己的效用。现有的研究总是开发博弈论模型来计算纳什均衡。对于每个设备，它都会根据系统状态的全局知识与其他设备讨价还价。然而，在无处不在的边缘计算网络中，设备无法获取全局信息，因此如何在完全去中心化的环境中保证设备的公平性值得研究。
  • 3）在局部观察下，它适用于设计基于学习的方法，通过与环境的交互来获得良好的策略。但一方面，现有的无模型学习方法在起步阶段的性能总是较差，不适合在线调度。另一方面，它们的收敛速度很慢，尤其是在具有多个智能体的部分可观测环境中。因此，有必要设计一种收敛速度快且可以分散方式执行的学习方法。

🛩创新

• 针对上述挑战，该文提出一种基于终端智能体的计算卸载算法MILP，旨在最小化设备的平均任务完成时间。它们可以将任务卸载到其他设备进行计算，也可以在本地处理它们，完全取决于他们自己的观察和决策。
  • 据我们所知，本文是研究基于多智能体模仿学习的普适边缘计算计算卸载问题的早期努力。
    • 一般来说，模仿学习是一种机器学习方法，它允许学习主体模仿专家策略，可以有效解决原始问题，但由于其时间复杂度高，无法以在线方式进行。因此，设计了一个培训过程，通过实现专家的模仿来学习代理策略。
    • 此外，多智能体模仿学习允许多个智能体模仿相应专家的行为，并且可以在智能体之间达到纳什均衡。
• 具体而言，我们的贡献可以总结如下：
  • 1）通过考虑边缘设备的通信和计算能力，将普适边缘计算环境中的任务调度问题表述为优化问题。为了解决这一问题，我们通过指定博弈要素，如进化的玩家、状态和状态转换可能性，建立原始优化问题与随机博弈之间的关系，并将优化问题转化为奖励最大化问题。
  • 2）为了解决奖励最大化问题，我们放宽了普适边缘计算网络带来的约束，提出了一种基于多智能体模仿学习的计算卸载算法，该算法允许多个学习智能体模仿相应专家的行为，以获得良好的调度策略。据我们所知，这是第一个将多智能体广义对抗模仿学习（GAIL）与普适边缘计算相结合以解决流量调度问题的工作。
  • 3）为了形成专家策略，我们采用Actor-Critic和Kronecker-factored Trust Region（ACKTR）算法，在对系统状态的充分观察的基础上找到专家的最优策略。对于智能体策略，提出了一种基于部分观测值的每种设备的新神经网络模型。它全面集成了卷积神经网络（CNN）、生成对抗网络（GAN）和ACKTR来接近专家性能，并且可以在线方式执行。
  • 4）我们从理论和实验两个角度证明了该算法的优越性。理论结果表明，该算法能够保证器件的公平性，并在完全和部分观测的基础上达到纳什均衡。性能结果表明，该算法在平均任务完成时间、收敛时间和卸载率方面均具有优势。

📊效果

• 我们从理论和实验两个角度证明了该算法的优越性。理论结果表明，该算法能够保证器件的公平性，并在完全和部分观测的基础上达到纳什均衡。性能结果表明，该算法在平均任务完成时间、收敛时间和卸载率方面均具有优势。

🧠疑问

1. 算法调度时间多少？看起来需要多次迭代，应该速度不快？单任务执行时间又只有零点几秒，这个情况如何解释？

---

---

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

🗺参考文献

[1] X. Wang, Z. Ning and S. Guo, “Multi-Agent Imitation Learning for Pervasive Edge Computing: A Decentralized Computation Offloading Algorithm,” in IEEE Transactions on Parallel and Distributed Systems, vol. 32, no. 2, pp. 411-425, 1 Feb. 2021, doi: 10.1109/TPDS.2020.3023936.