边缘计算中计算卸载与资源分配的博弈论：综述

一、引言

智能移动设备正迅速增长，涌现出增强现实（AR）、在线游戏、多媒体和人脸识别等新应用。这些应用需要密集的计算和高资源消耗。因此，传统云（如亚马逊和微软）被视为一种有前景的范式，因为它可以为终端用户提供无限的能力服务（如存储、内存、能量、带宽（BW）和计算能力）。尽管这有助于改善终端设备的能耗，但将任务卸载到远程云服务器进行处理会带来诸多挑战，例如由于距离较远导致的高延迟。这对于在线高质量视频流等对延迟敏感的应用并不适用。因此，使用可能位于不同大陆的传统云中心无法满足这些应用的超低延迟需求[1]。为此，近年来人们努力引入边缘计算系统以解决这一延迟问题。边缘层是位于终端设备与云服务器之间的层次。它将网络和存储等计算资源推向无线网络边缘，以最小化延迟，同时提供足够的资源来处理从移动终端卸载的数据。这通过使设备摆脱繁重的计算任务，延长了设备的电池寿命。

工作负载。然而，与云数据中心提供的资源相比，这些边缘计算资源是有限的。因此，边缘资源的限制以及终端设备的高动态需求要求高效的资源管理技术[1]。本文考虑了两种资源管理方式，即资源分配和计算卸载。任务分配用于寻找用户与资源之间的最佳关联，而卸载则用于将任务迁移到远程服务器进行处理。设计一个综合考虑设备能力、服务器能力、可用资源、用户需求、用户移动性以及任务随机到达的环境，无法通过传统的优化技术解决。为了实现最优资源管理并满足用户需求，有必要分析用户行为。博弈论是用户交互的数学。因此，它被提出用于分布式决策，旨在找到一种所有用户都达到均衡状态且无人愿意偏离的解决方案[1][2][3]。本文区别于早期调查[1]和[4]至[8]之处在于，重点关注应用博弈论框架来应对边缘计算挑战，以实现计算卸载和资源分配的最新技术。据我们所知，这是第一篇回顾博弈论在边缘计算中用于资源管理的论文。本文其余部分组织如下：第二节简要概述博弈论，展示其定义、优势和示例。第三节概述边缘计算架构、挑战和资源管理技术。第四节全面调查将博弈论应用于边缘计算，以满足系统在不同目标和约束下的需求。第五节总结经验教训和未来研究方向，最后，第六节为结论。

II. 博弈论背景

A. 博弈论定义

博弈论是一种用于建模两个或多个用户之间交互的数学框架。它在通信和网络场景中取得了显著成果。博弈论的主要目标是确保所有用户都能得到满足，即使他们彼此不同且具有冲突目标。它能够获得一种稳定解，在该解中，当其他所有参与者的行为保持不变时，没有人希望改变自己的行为，此时系统处于一种称为纳什均衡（NE）的均衡状态。以下是一些关键要素，在将任何优化问题表述为博弈模型[9]时所需。

1) 参与者 ：他们是在博弈中的决策者。
2) 策略 ：它们是每个参与者在博弈中可采取的行动。
3) 收益 ：它取决于所有参与者所采取的行动，类似于每个参与者在博弈结束时获得的奖励。
4) 信息 ：它是每个参与者可获得的信息，他们可能拥有完全信息或不完全信息。
5) 理性 ：这表明了每个参与者是如何思考的。

B. 博弈论分类

1) 经典博弈 ：在此类博弈中，参与者采取的行为是理性的。它分为两种类型。
a) 合作博弈 ：参与者拥有相同的目标，并以团队的形式协作，从而实现公平的解决方案。
b) 非合作博弈（NC博弈） ：用户同时进行博弈。因此，每个用户都无从知晓其他用户的选择。

2) 进化博弈 ：在这类博弈中，参与者缺少有关可用选择的一些信息，因此他们并非完全理性。

C. 博弈论示例

a) 匹配游戏 ：在此类博弈中，存在两组元素需要相互配对。
b) 势博弈 ：如果一个博弈包含一个势函数，则称其为势博弈。该函数用于分析问题的均衡。
c) 斯塔克尔伯格博弈 ：它由一个领导者和多个追随者组成。博弈按顺序步骤进行，领导者观察追随者的策略后宣布其成本。追随者将根据领导者的行动以及问题的目标函数选择自己的策略。
d) 贝叶斯博弈 ：它是一种不完全信息博弈，因此参与者不了解其他人的偏好。支付函数通过概率分布表示。

III. 边缘计算概述

在本节中，我们将介绍如图1所示的边缘计算架构，该架构由三层组成：用户、边缘层和云数据中心。接着介绍我们需要优化的挑战，然后是用于应对这些挑战的资源管理技术。

A. 架构

1) 用户 ：每个用户都有一个需要执行的任务。每个任务都有一个最长期限需要完成，且一些任务可以拆分为子任务。
2) 边缘服务器 ：它们位于用户附近，因此能够支持对延迟敏感的应用。然而，与云服务器相比，它们的计算资源较少。
3) 云服务器 ：它们位于远离用户的远程数据中心，距离用户可能有数百公里。它们始终拥有充足的计算资源和高存储容量，因此能够满足所有计算需求。

B. 挑战

在移动边缘计算中，有三个主要挑战需要优化，即成本、延迟和能耗。

1) 延迟 ：它是卸载时间加上执行时间，取决于任务的大小、上行链路传输速率和服务器的处理能力。[11]。
2) 成本 ：它是计算的成本加上传输的成本。用户支付的成本与服务提供商获得的收益之间存在权衡，因此一些论文提出了最小化用户支付成本的算法，另一些则试图最大化服务提供商服务的收益，还有一些成功地将这两个目标结合起来，如[12]所示。
3) 能耗 ：能耗等于传输能耗加上执行能耗。它取决于传输功率、每CPU周期能耗成本以及完成任务所需的CPU周期数。[2]

C. 资源管理技术

本文重点关注的两种主要技术是资源分配和计算卸载。

1) 资源分配 ：这是一种调度资源的技术，旨在找到最优关联，以利用所有可用资源并满足每个用户的需求[2]。
2) 计算卸载 ：这是一种将用户任务迁移到边缘服务器或进一步卸载到云服务器进行处理的技术。用户可以选择在本地设备上计算任务，或将任务卸载[3]。

IV. 基于博弈论的边缘计算中计算卸载与资源分配综述

在本节中，我们回顾了基于博弈论方法，通过计算卸载或资源分配或两者结合，以最小化边缘计算中的延迟、成本和能耗的相关工作。

A. 基于最小延迟的资源管理

表I展示了以最小化延迟为目标函数的最先进的研究之间的比较。[13]到[17]的研究使用了计算卸载，而[18][19]则采用了资源分配。[13]的作者对包含多辆车辆和多个移动边缘计算（MEC）服务器的车联网边缘网络进行了建模，他们考虑将任务卸载到边缘或在本地进行计算。他们将博弈建模为势博弈，证明了纳什均衡的存在性，分析了算法的代价系数，并最终将结果与本地计算和随机卸载进行了比较。文献[14]是首个使用非合作博弈方法研究多异构用户和多异构边缘服务器的工作。每个用户具有无限数量的任务，并被建模为 M/G/1排队系统。他们证明了纳什均衡的存在性，并找到每个用户的最佳响应，从而保证边缘计算系统的稳定性。在[15],中，他们考虑了一个带有附属云点的单个无线接入点，用户的任务可以分割为在本地设备和云点上同时执行，根据任务的完成时间最小化延迟，将问题建模为非合作博弈，并将结果与本地计算以及不同卸载比例的情况进行比较。在[16]中，作者使用匹配博弈，在可靠性及缓存能力约束下最小化延迟。用户选择在本地设备上计算任务或将其卸载到云点。他们根据对计算结果的相似兴趣形成云小站集群，每个集群在其云点中缓存计算结果。与两个基线相比，他们的算法取得了更好的结果：第一个基线考虑可靠性约束但不考虑缓存能力；第二个基线既不考虑可靠性也不考虑缓存能力，仅考虑接入无线链路质量。文献[17]中的作者定义了两类手机：卸载者和贡献者。区别在于，卸载者需要访问其他移动设备来执行其任务，而贡献者则与其他移动设备共享计算资源。他们将卸载过程建模为多领导者多跟随者斯塔克尔伯格博弈，对卸载者采用非合作博弈方法，对贡献者采用合作方法。两者之间的映射取决于待执行的计算密集型应用的服务级别协议。他们是首个使用基于多层拍卖的策略来优化响应时间的研究。文献[18]中的问题被建模为一对多匹配博弈，根据每个云点的最大工作负载以及每个物联网节点任务的截止时间进行分配。结果与将物联网节点随机分配给云点的方法进行了比较。文献[19]的目标是在确保雾节点之间负载均衡的同时，最小化依赖于请求大小和通信信道的用户响应时间。该问题被建模为匹配博弈，以将用户分配给不同的雾节点，同时考虑每个雾节点可分配的最小和最大用户数。

B. 基于最小能量的资源管理

表II展示了以最小化能耗为目标函数的最先进的研究之间的比较。[20][21]中的研究采用了计算卸载，而[22]中同时采用了计算卸载和资源分配。[20]中的作者在任务执行的最大可接受延迟约束下最小化能量消耗。他们考虑了一个单任务，该任务可以在本地计算，也可以卸载到边缘服务器或云服务器。他们仅考虑一个 MEC服务器，通过将问题建模为具有势函数的势博弈，证明了纳什均衡的存在性，结果是与其他仅考虑移动设备和边缘服务器的方案相比，[21]中的研究由作为云点的无人机、多个物联网节点和多任务组成，在满足物联网服务质量约束和最大可容忍执行时间的同时最小化能耗。该问题被建模为精确势博弈，并通过与本地计算和随机卸载算法的比较来验证结果。最后，在[22]中，功率分配、任务卸载和频率调节被联合优化，以在满足最大处理时间、最大计算频率、最大可卸载任务数量以及最大传输功率约束的前提下最小化能耗。不同于其他工作，他们考虑了不同类型的计算任务以及这些任务的随机到达。

表I：基于最小延迟的已审阅的最先进方法比较

Ref	方法	系统模型	Main 约束	Game
[13]	卸载	多车辆 MEC 单任务	干扰	潜力 Game
[14]	卸载	多用户 多MEC 多任务	移动 计算 稳定性	NC游戏
[15]	卸载	多用户 单个云朵 多任务	完成时间 任务的	NC游戏
[18]	分配	多物联网 多云点 云服务器	工作负载 任务云朵截止时间 完成	匹配 Game
[19]	分配	多用户 多雾节点 多任务	负载均衡 在雾节点之间 最大 用户数量 每个雾节点	匹配 Game
[16]	卸载	多用户 多个云点 多任务	缓存 能力 延迟队列	匹配 Game
[17]	卸载	多设备 单个云朵	计算 需求 贡献者 最长时间	斯塔克尔伯格博弈

表II：基于最小能量的已审阅的最先进方法比较

Ref	方法	系统模型	Main 约束	Game
[20]	卸载	多用户 单边缘计算 单任务	计算 执行时间 和数量 无线 信道	势博弈
[22]	卸载 分配	多用户 多MEC服务器 多类型任务的	处理 延迟的任务	博弈‐理论的方法
[21]	卸载	多云点 多任务 来自物联网	最大 可容忍的 执行时间 容量	精确 势博弈
## C. 基于最小成本的资源管理

表III展示了以最小化成本为目标函数的现有技术对比。文献[12][23][24][25]采用了计算资源分配方法。在[23]中，作者考虑了多个云服务器与单个云朵的场景，用户之间竞争带宽和电力资源，而云服务器则竞争以最大化其收入。采用逆向方法求解三阶段斯塔克尔伯格博弈：第一阶段，云服务器确定虚拟机（VMs）的价格；第二阶段，云朵决定从云服务器获取的虚拟机需求，并将其分配给用户；第三阶段，移动用户决定自身的带宽需求和功率。在[24]中的分配问题被建模为动态贝叶斯博弈，MEC服务器根据用户行为的贝叶斯概率确定单位功率的价格。该模型未考虑云服务器，仅包含单个MEC服务器，结果证明相较于均匀分配和随机分配性能更优。在[12]中的系统由单边缘服务提供商和多个具有移动区块链应用的移动用户组成，将资源分配问题建模为两阶段斯塔克尔伯格博弈，以最大化移动区块链系统中用户和服务器的收益。第一阶段，边缘服务提供商设定服务价格；第二阶段，用户决定其计算服务需求。通过逆向归纳法推导出用户之间的纳什均衡，并证明了斯塔克尔伯格均衡的唯一性。

最后，[25]中的作者考虑了具有多个MEC服务器的多MEC系统。资源分配问题被建模为三阶段斯塔克尔伯格博弈。每个服务器作为领导者，决定其资源的成本以最大化其收入。用户的收益取决于计算资源的数量和内容质量。结果与三种方案进行了比较：第一种是采用无缓存视频传输算法；第二种是采用无转码视频传输算法；第三种是集中式资源分配方案。

D. 基于最小成本和能耗的资源管理

表IV展示了以最小化成本和能量为目标函数的最先进的研究之间的比较。在[26]中，采用计算卸载来最大化用户和边缘服务器的效用。用户的效用定义为能效和服务的成本，而边缘服务器的效用定义为提供计算资源的收入。他们将卸载问题建模为单领导者多用户斯塔克尔伯格博弈，并将结果与现有的集中式算法进行比较。在[27]中同时使用了数据卸载和任务分配，其中需要执行任务的主设备可以访问附近的设备（从设备）或云朵来处理其任务，而不是将任务发送到远程云服务器。作者在其优化问题中使用了多种类型的成本，如通信成本和计算成本。该问题被建模为两阶段斯塔克尔伯格博弈。首先，从设备提出它们能够提供的数据执行单元数量；其次，主设备为每个从设备设定定价策略。

E. 基于最小延迟和能量的资源管理

表五展示了在以最小化延迟和能耗为目标函数的情况下，对现有最先进的研究进行的比较。[28]到[41]的研究采用了计算卸载。在[28],中，用户选择在本地计算任务，或将任务通过基站卸载到云服务器或边缘服务器，以最小化延迟和能耗。他们考虑了单任务和单边缘计算场景。研究发现，采用不完全信息的贝叶斯博弈比采用完全信息时获得更好的结果。从[29]到[31]，作者考虑了多个MEC服务器，并未考虑云服务器，每个用户有一个需要执行的单任务。他们将优化问题建模为势博弈，并证明了势函数和纳什均衡的存在性。他们考虑了延迟、负载、干扰和能耗约束。[30]中的系统由连接到公共MEC服务器的多个小区组成，用户在自己的设备和MEC服务器之间进行选择，该问题通过自适应动态序贯方法求解，其中部分用户可以观察到其他用户之前采取的动作，并据此确定自己的行为。结果证明优于三种方案：第一种是所有任务都在本地计算；第二种是当用户发现将要卸载任务的用户数量超过可用虚拟机数量时，选择在本地计算任务。最后，使用序贯博弈，但未考虑排队延迟和可用虚拟机。尽管在[32]中他们考虑了单边缘计算，但他们首次在其模型中研究了传输功率控制。他们证明了所建模博弈的纳什均衡以及算法的收敛性。在[33]中，系统由多个MEC服务器组成，其中一些连接到宏基站，另一些连接到小区。用户有四种选择：第一，在本地计算其任务；第二，将任务卸载到直接连接至基站的MEC服务器；第三，将任务卸载到连接至小小区的MEC服务器；第四，通过无线回传链路和回传间接将任务卸载到连接至宏基站的MEC服务器。该问题被建模为势博弈，并将结果首先与仅本地计算的情况进行比较，其次与不考虑小小区的情况进行比较。

表III：基于最小成本的已审阅的最先进方法的比较

Ref	方法	系统模型	Main 约束	Game
[23]	分配	多用户 单个云朵 多云服务器	带宽分配 传输功率	三阶段 斯塔克尔伯格 Game
[24]	分配	多用户 单个 MEC	传输 功率	动态 贝叶斯博弈
[12]	分配	多用户 一个边缘 服务提供商	价格 服务	两阶段 斯塔克尔伯格 Game
[25]	分配	多用户 多MEC 服务器	用户延迟 传输 rate 质量等级	三阶段 斯塔克尔伯格 Game

表IV：基于最小成本和能量的已审阅的最先进方法的比较

Ref	方法	系统模型	Main 约束	Game
[26]	卸载	单多边缘户	容计量算和 资源价格	斯塔克尔伯格 game
[27]	卸分配	多用户	数据数量 处理单元	两阶段 斯塔克尔伯格 game

[34]中的系统由位于本地区域和邻近区域的多接入边缘计算服务器组成。该问题被建模为一个势博弈，并基于雅可比算法采用分布式卸载策略进行求解。实验结果与本地计算以及未考虑计算资源不足的卸载算法进行了比较。文献[35]中的作者考虑了同质和异质移动用户。每个用户都有一个需要处理的任务。存在单个云朵，任务可以卸载到该云朵上。他们证明了在同质用户算法情况下纳什均衡的存在性，并将异质用户问题建模为精确势博弈以证明纳什均衡的存在性。他们的结果与本地计算和随机卸载进行了比较。文献[36]中考虑了车载雾计算，其中车辆资源位于靠近移动用户的边缘。用户的应用由其最大等待时间类型和优先级表征。该问题被建模为势博弈，决策基于需求优先级、计算能力和每辆车的当前能量。在[37]中，作者将问题建模为基于前景理论的NC游戏，其中用户行为可能偏离传统的理性假设。卸载决策依赖于一个限制卸载用户总数的阈值。在[38]中，作者考虑了一个联合MEC卸载和D2D系统，用户可以将其任务卸载到MEC服务器或分布式计算节点。该问题被建模为一个序贯博弈，并证明了纳什均衡的存在。结果表明，与仅进行本地计算或将任务卸载到MEC服务器而不使用分布式节点相比，该方法表现更优。在[39]中提出的算法被证明是可行的、最优的且高效的。在包含多个用户、Wi‐Fi接入点、多个边缘云和单个云朵的实际模型场景中，延迟和能耗被最小化。该问题的约束包括每个应用的截止时间、完成卸载过程的连接时间以及每个边缘服务器可服务的最大数量。作者在[40]中研究了非正交多址接入与移动边缘计算的结合，因为两者的结合能够降低能耗和整体延迟。他们仅考虑了一个MEC服务器。通过协作联盟博弈解决卸载问题，并将结果与三种方案进行比较：仅本地计算、仅边缘卸载以及启发式正交卸载算法。最后，在[42]中提出了一种自下而上的非合作博弈论任务分配方法，以寻找实时社交感知任务与非合作异构边缘服务器之间的最佳关联。该方法解决了两个主要挑战：第一，应用与边缘节点之间的目标冲突；第二，应用对边缘节点的不完全信息。

F. 基于最小延迟和成本的资源管理

表VI展示了对现有最先进的研究进行比较，这些研究以最小化延迟和成本作为目标函数。文献[43][44]采用了计算卸载。文献[43]中的作者同时考虑了云服务器和边缘服务器，并将它们分别建模为M/M/∞和M/M/1。两个服务器通过采用两阶段斯塔克尔伯格博弈，同时竞争确定其服务价格。在第一阶段，服务器向用户提供其资源的价格；在第二阶段，用户选择将任务卸载至其中一个服务器。该问题通过逆向归纳法达到均衡。在[44]中考虑了单边缘计算服务器，且未考虑云。该问题的目标是最小化每个用户由延迟和支付成本构成的成本。服务器根据用户的不同需求提供不同的价格。该问题被建模为斯塔克尔伯格博弈，结果表明，与本地计算模型以及对所有需求提供统一价格的卸载方式相比，该方法表现更优。文献[45]的研究旨在通过计算卸载和资源分配，最小化移动设备上的延迟和货币成本。该系统包含一个基站、一个MEC服务器、多个用户，且每个用户具有单任务。同时考虑了上行链路和下行链路的频谱资源。该问题被建模为一个势博弈，并与三种场景进行了比较：第一，本地计算；第二，随机卸载；第三，不考虑下行链路频谱资源。

G. 基于最小成本、能量和延迟的资源管理

表VII展示了将延迟、能量和成本同时最小化作为目标函数的最先进的研究之间的比较。文献[46]提出了进化博弈，并利用复制动态方法获得进化均衡。该系统由宏基站、小基站以及具有多任务的多个用户组成。资源分配用于优化延迟、能量和货币成本，其中货币成本包括计算成本和通信成本。在[47]和[48]中均提出了一种联合资源分配和计算卸载的优化算法。该问题被建模为势博弈，并证明了纳什均衡的存在性。两者之间的区别在于[48]仅考虑单任务，而[47]考虑多个任务。

表五：基于最小延迟和能耗的已审阅的最先进方法比较

Ref	方法	系统模型	Main 约束	Game
[28]	卸载	多用户 单边缘计算 单任务	距离和 信道增益	协作 Game 贝叶斯博弈
[29]	卸载	多设备 多MEC 单任务	load 干扰	势博弈
[42]	分配	多用户 多服务器 多边缘 节点	任务完成 time	自下而上的NC 任务分配 game
[30]	卸载	多用户 单边缘计算 单任务	处理 时间和 能量 消耗	自适应 动态 顺序 Game
[31]	卸载	多用户 多MEC 单任务	干扰， 时间和 能量	势博弈
[32]	卸载	多用户 单边缘计算 单任务	传输 功率 控制	功率控制 基于博弈 理论
[33]	卸载	多用户 多MEC 单任务	频率 信道	势博弈
[34]	卸载	多用户 本地和 邻近区域 服务器	任务成本， MEC服务器 容量和 资源	NC潜力 game
[35]	卸载	多用户 单个 云朵 单任务	…的成本 计算 当前负载 和带宽	势博弈
[36]	卸载	多设备 车载雾 云	应用 type 最大 等待时间	势博弈
[37]	卸载	多设备 单边缘计算 单任务	数量 卸载 用户	NC游戏
[38]	卸载	多用户 单边缘计算 多任务	干扰 传输 rate	顺序 game
[39]	卸载	多用户 多边缘 云 多任务	应用 完成 截止时间 最大 数量 设备	博弈论 方法
[40]	卸载	多用户 单边缘计算	二进制 卸载	联盟博弈
[41]	卸载	多用户 多服务器 单任务	二进制 卸载	势博弈

表VI：基于最小延迟和成本的已审阅的最先进方法比较

Ref	方法	系统模型	Main 约束	Game
[43]	卸载	多用户 公有云 边缘云 单任务	边缘收益 和公有云 是相等的	两阶段 斯塔克尔伯格 game
[44]	卸载	多用户 单边缘计算	计算 容量	斯塔克尔伯格 Game
[45]	卸载 分配	多用户 单边缘计算 单个基站 单任务	计算 上行资源链路和 下行链路 频谱资源	潜力 game

表VII：基于最小延迟、成本和能量的已审阅的最先进方法比较

Ref	方法	系统模型	Main 约束	Game
[46]	分配	多用户 多任务 多云点	最大时延	进化 博弈
[47]	卸载 分配	多用户 单边缘计算 多个 任务	最大处理 MEC的能力 和上行链路 传输功率	潜力 game
[48]	卸载 分配	多用户 单边缘计算 单任务	云完成时间 上行传输 功率 处理能力 MEC服务器的	潜力 game

V. 经验教训与未来研究方向

由于日常生活中人类活动的变化导致终端设备需求多样化，边缘计算环境是动态的。由于博弈论基于数学模型构建，这需要大量时间且要求环境静态不变，因此建议将机器学习技术与博弈论相结合。将数据卸载到边缘服务器可带来低延迟优势，但资源数量有限；而云服务器虽提供丰富的资源池，但由于距离较远导致服务延迟较高。目前仅有少数论文在同一模型中同时考虑了云服务器和边缘服务器，因此建议在同一模型中同时考虑多边缘服务器和多云服务器。大多数论文将任务整体处理，要么在本地计算，要么选择将其完全卸载到边缘服务器或云服务器。因此，建议将任务拆分为多个部分，然后决定哪些部分在本地计算，哪些部分进行卸载。大多数论文仅选择计算卸载或资源分配方法之一来优化问题，因此建议联合使用这两种方法来解决优化问题。与其他现有算法相比，博弈论在边缘计算资源管理问题上取得了显著成果，因此建议将博弈论模型部署到其他边缘计算问题中，如缓存和安全。

VI. 结论

边缘计算将云资源推向网络边缘，靠近用户。这最小化了延迟并延长了终端设备的电池寿命。然而，它受限于有限的计算和通信资源。因此，寻找满足用户需求的方法被认为是网络提供商面临的主要挑战之一。博弈论已在许多领域证明了其最优性和公平性。它能够找到使所有用户都满意的解决方案。本文综述了在边缘计算系统中应用博弈论的最新技术。针对每个优化问题，提供了资源管理方法、目标函数、约束、系统模型以及所使用博弈之间的比较。