【论文】略读笔记32-经典-边缘博弈用户分配
📖《A Game-Theoretical Approach for User Allocation in Edge Computing Environment》
🎯需求
在过去的十年中，移动和物联网 （IoT） 设备，包括手机、可穿戴设备、平板电脑等，变得越来越流行。
- 根据爱立信的报告，预计到2023年将有约200亿台移动和物联网设备。
移动和物联网设备的快速增长和进步推动了移动和物联网应用程序（以下统称为应用程序）的多样性和复杂性。
- 许多应用程序资源密集、计算密集型和高能耗。
由于计算能力和电池电量有限，移动和物联网设备运行此类应用程序变得越来越困难和不切实际。为了解决这个问题，移动和物联网设备可以将计算任务卸载到云端，以利用其可配置且强大的计算能力。
近年来，出现了需要低延迟的应用程序，例如人脸识别、自然语言处理、互动游戏等。
- 由于通常不可预测的网络延迟和昂贵的带宽，云通常无法满足此类延迟敏感型应用程序的严格要求。这是云计算范式的一个明显弱点，因为人类对延迟非常敏感，这在广域网规模上很难减少。
边缘计算作为促进5G移动网络的关键技术，允许将计算任务从移动和物联网设备转移到具有类似云计算能力的边缘服务器。
- 这些边缘服务器由一台或多台物理机提供支持，部署在地理位置靠近应用用户的基站上。
- 应用程序用户可以将计算任务卸载到附近的边缘服务器，而不是云端。边缘计算范式为需要低延迟的应用程序铺平了道路。
在过去的几年里，人们对边缘计算环境中的计算卸载进行了广泛的研究。
虽然现有的研究侧重于从边缘基础设施提供商或移动和物联网设备的角度减少延迟和/或节能，但本文从移动和物联网应用程序供应商的角度研究了一个关键问题。
- 边缘计算范式允许移动和物联网应用程序供应商（称为应用程序供应商）在边缘基础设施提供商（例如 AT&T、Telstra 等）的边缘服务器上租用计算能力，例如 CPU、内存、带宽。然后，可以将他们的服务部署在这些边缘服务器上，以低延迟为附近的应用程序用户提供服务。
- 通常，边缘服务器覆盖特定的地理区域，以便其覆盖范围内的应用程序用户可以通过无线访问连接到它。
- 因此，边缘服务器以分布式方式部署 - 通常在蜂窝基站附近 - 以便它们可以覆盖不同的地理区域。
- 相邻边缘服务器的覆盖区域通常相交，以避免任何边缘服务器未覆盖的空白区域。
- 位于交叉区域的应用用户可以连接到附近具有足够计算容量（容量限制）（如 CPU、内存和带宽）的边缘服务器之一（邻近限制）。
- 给定特定区域中的多个应用用户，可以通过多种方式将他们分配给覆盖该区域的边缘服务器。
- 不适当的分配可能会导致大量应用用户未分配到任何边缘服务器。
- 因此，从应用供应商的角度来看，一个直接而重要的目标是最大限度地增加分配给边缘服务器的用户数量。
- 按照即用即付定价模式，应用供应商为从边缘基础设施提供商处租用的边缘服务器的计算能力付费。因此，应用程序供应商的另一个重要目标是最大限度地降低为应用程序用户提供服务的整体系统成本。
- 此问题称为边缘用户分配 （EUA） 问题。
🚧现状
- 云计算范式支持多租户，能够基于单个应用程序实例同时为多个租户提供服务。它允许多个租户比单租户更有效地共享计算资源，即为每个租户运行一个应用程序实例。
- 例如，在相同的工作负载下，多租户 Web 应用程序比单租户 Web 应用程序实现更高的吞吐量，因为用户工作负载的整合通常可以实现高服务器利用率。
- 边缘计算继承了云计算范式的多租户，因此允许应用程序供应商在边缘计算环境中为其EUA问题实现具有成本效益的解决方案。关键是要充分利用多租户，即将最大数量的应用用户分配给最少数量的边缘服务器。
- 在边缘计算环境中，应用程序供应商通常需要在特定区域容纳大量应用程序用户。因此，由于上述EUA问题的邻近性和容量限制，寻找集中式最优解决方案将具有高度的复杂性。而博弈论在分布式计算领域得到了广泛的应用。它是设计去中心化机制的有力工具。
🛩创新
在本文中，我们介绍了EUAGame，这是一种寻找EUA问题解决方案的博弈论方法。
- EUAGame 通过为应用程序用户单独做出分配决策来减轻集中优化的负担，同时实现集体满意的分配解决方案。
- 此外，EUAGame 允许应用程序用户在不同的计算能力维度上指定他们的个人（通常是差异化的）兴趣。
- EUAGame 将应用供应商的 EUA 问题建模为 EUA 博弈。在这个博弈中，每个应用程序用户都被模拟为游戏中的玩家，他们找到附近的边缘服务器来卸载其计算任务。然后，EUAGame 采用去中心化算法为应用程序用户做出分配决策，以实现博弈的纳什均衡。
本文的主要贡献如下：
- 我们首先将EUA问题建模为约束优化问题，并证明找到集中最优解是NP困难的。
- 为了以分布式方式解决EUA问题，我们将其表述为一个博弈，其中考虑了应用程序用户的利益，多租户的利益和整体系统成本。该博弈的目的是最大限度地增加分配的应用程序用户数量，并最大限度地降低整体系统成本，同时满足所有邻近限制和容量限制。
- 我们分析了EUA博弈，并证明这是一个承认纳什均衡的潜在博弈。
- 我们提出了一种去中心化算法，用于在EUA博弈中找到纳什均衡。
- 我们从理论和实验上分析了该算法的性能。
📊效果
- 效率是否过低？
- 希望这篇博客对你有帮助！如果你有任何问题或需要进一步的帮助，请随时提问。
- 如果你喜欢这篇文章，欢迎动动小手 给我一个follow或star。
🗺参考文献
- 标题: 【论文】略读笔记32-经典-边缘博弈用户分配
- 作者: Fre5h1nd
- 创建于 : 2024-03-20 21:03:55
- 更新于 : 2024-03-20 22:08:49
- 链接: https://freshwlnd.github.io/2024/03/20/literature/literatureNotes32/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论