基于博弈论和启发式算法的超密集网络边缘计算卸载

刘振鹏，郭超，王仕磊，陈杰，李小菲

（1.河北大学 电子信息工程学院，河北 保定 071002；2.河北大学 信息技术中心，河北 保定 071002）

0 概述

随着5G 时代的到来，智能终端设备的数量快速增长，许多新应用也随之流行［1-3］。然而诸如增强现实、虚拟现实、智能互联等低时延、高能耗的应用往往需要移动设备具有充足的电池容量和丰富的计算资源［4-5］，这些应用可能会受限于移动设备的性能而无法实现。移动边缘计算（Mobile Edge Computing，MEC）技术［6］可以有效应对该问题，当任务卸载到边缘服务器上时，边缘服务器可以分担用户设备的一部分计算任务，从而降低时延和能耗［7-9］。超密集网络（Ultra-Dense Network，UDN）［10-12］是5G 中的一种关键技术，也被认为是支持未来无线网络部署的最佳方式之一［13-14］。UDN通过在传统的宏蜂窝小区中部署大量低功耗、低成本的微型基站，来形成宏微蜂窝共存网络，在缩短用户接入距离的同时可实现小区内的无缝覆盖，提高数据的传输效率和用户的服务质量［15］。然而UDN 带来的网络致密化虽然提高了服务质量，但是高密度的基站分布会对同一用户进行重复覆盖，用户选择哪个基站进行任务卸载，以及如何选择合适的卸载比例，都是边缘计算卸载中面临的新问题。

针对MEC 网络中用户任务的卸载和资源分配问题，国内外学者进行了大量的研究。CHEN等［16］将任务卸载问题表示为一个随机优化问题，并以降低任务卸载能耗为目标对问题进行了优化，然而该方法没有充分考虑时延对任务卸载造成的影响。LIU等［17-18］将Lyapunov优化框架应用在任务卸载中，研究了多用户进行任务卸载的情况下功率和时延的权衡问题，并在时延和可靠性的约束下，采用Lyapunov 随机优化方法解决该优化问题。GUO等［19］提出了一种计算效率更高的两层博弈论贪婪近似卸载方案，并证明了其优越的性能。ZHOU等［20］通过构建斯塔克伯格博弈模型对带宽资源进行合理分配，同时适当调整任务卸载比例来减少任务的计算时延，然而该方法仅考虑了单服务器的情况，未考虑多用户多服务器场景。LYU等［21］提出了一种启发式卸载决策算法，该算法是半分布式的，能够联合优化卸载决策和通信资源，从而提高系统的性能。针对UDN 环境中的计算卸载问题，CHEN等［22］利用软件定义网络的思想，研究了基于UDN 和MEC 的任务卸载问题，减少了任务的执行时延和能量消耗。DENG等［23］研究了在多服务器边缘计算环境下的卸载决策优化问题，通过启发式算法对资源进行配置并优化决策，有效提高了服务质量，但该方法没有考虑多服务器多用户情况下用户之间的竞争关系对系统性能产生的影响。GUO等［24］将该问题转化为一个混合整数非线性规划问题，结合遗传算法和粒子群算法的优点，设计了分层遗传算法，并证明了该算法的有效性。FENG等［25］提出了一种融合灰狼算法的混合鲸鱼优化算法，该算法考虑了模型中的多个因素，获得了较好的性能。虽然上述研究中提出的系统或算法在能耗和时延方面都具有较优的性能，但主要针对时延或能耗中的某一方面进行优化，且没有考虑在多用户多服务器的UDN 网络环境下的用户卸载对象选取问题。由于UDN 中会出现多个基站的覆盖范围相互重叠的状况，当任务被卸载到不理想的MEC 服务器上时，可能会造成系统能耗过高［26-28］。此外，当大量用户分配到同一MEC 服务器时，会使得该服务器负载过大，对部分用户和全局性能都会造成不利影响，因此，需要一种能够在UDN环境下合理分配用户的卸载选择，并使时延和能耗最小的策略。

本文对超密集网络环境中的卸载决策问题进行建模，将其分为卸载对象选取和卸载比例选取2 个问题。针对卸载对象选取问题，考虑MEC 服务器的邻近性和工作负载对性能的影响，定义偏好度函数，各用户根据偏好度进行博弈，选择最优的服务器进行卸载。为降低问题的复杂度，将卸载到相同服务器的用户分为一组，根据分组结果，将原问题分解成若干个并行的卸载比例选取子问题，采用萤火虫群优化（Glowworm Swarm Optimization，GSO）算法寻找最佳的任务卸载比例，最终得到最优卸载策略。

1 系统模型

当用户设备的计算能力无法满足应用的时延要求时，需要将部分任务卸载到MEC 服务器进行计算。为不失一般性，在5G环境中采用正交频分多址（Orthogonal Frequency Division Multiple Access，OFDMA）技术，为每个基站配备一个计算能力有限的MEC服务器，在MEC服务器中实现具体计算。由于基站和MEC 服务器的距离很小，因此两者之间的传输时延可以忽略。每个用户设备随机分布在各个基站的覆盖范围之内，且每个计算任务可以按一定比例进行分割，将部分任务的数据上传到MEC 服务器进行计算，用户设置在任务卸载期间保持不变。

1.1 网络模型

由于5G 网络的基站部署密度很高，因此基站的覆盖范围可能会存在大量重叠，部分用户可能处于多个基站的覆盖范围之内，如图1 所示。其中，n个用户表示为集合U={u1，u2，…，un}，m个服务器表示为集合S={s1，s2，…，sm}。考虑到用户的移动速度相对于基站的覆盖范围较小，可以假定用户是近似静止的。

图1 5G 网络模型Fig.1 5G network model

1.2 通信模型

通信模型采用正交频分复用技术，服务器sj的分组内总带宽表示为，在同一分组内，基站为每个用户分配相同的带宽，子带数量与该分组内用户设备数量相同，分组内用户数量表示为，代表服务器的工作负载。不同分组之间的用户相互无影响，仅受同组内其他用户的影响。由于用户设备到服务器之间需要通过无线信道传输，根据香农定理，用户ui到服务器sj的数据传输速率Ri，j如式（1）所示：

其中：pi表示用户ui的发射功率；gi，j表示用户ui到服务器sj的信道增益；σ2表示背景噪声的功率。显然，服务器负载与该分组内用户的带宽和信噪比具有很强的关联性，因此，数据上传速率受服务器负载的影响较大。

1.3 时延模型

用户的任务在本地计算和在MEC 服务器上计算具有不同的时延。由于需要将当前任务的一部分数据上传到MEC 服务器上运行，因此需要考虑两类时延：本地完成时延和外部完成时延。

1.3.1 本地完成时延

对于本地完成时延，主要考虑任务在本地设备进行处理的部分，无需考虑数据传输造成的时延，因此仅与计算任务所需周期和用户设备的计算能力有关。本地完成时延的计算公式如式（2）所示：

其中：di表示处理任务的数据量；fc表示处理每比特数据量所需的时钟周期数表示用户ui的本地设备的CPU 周期频率；βi表示用户ui的任务卸载比例，βi∈[0，1]，βi=0 表示任务全部在本地设备完成。

1.3.2 外部完成时延

外部完成时延是指从用户发送数据开始，到结果返回这段过程所产生的时延。用户ui外部完成时延主要包括三部分：任务数据上传时延，MEC 服务器上任务的执行时延，接收计算结果所需的反馈时延。外部完成时延和任务数据上传时延的计算公式如式（3）和式（4）所示：

设MEC 服务器为该组内所有用户设备分配相同的计算资源，则MEC 服务器上任务执行时间的计算公式如式（5）所示：

其中：fs表示MEC 服务器的CPU 周期频率。由于反馈时延远小于上传时延，因此可以忽略反馈时延［29］，则外部完成时延可由式（6）表示：

1.3.3 任务完成时延

由于任务在本地设备和MEC 服务器上的计算是同步进行的，任务实际完成时间应取两者的最大值，因此用户ui的任务完成时延Ti如式（7）所示：

1.4 能耗模型

由于用户的移动设备受电池电量消耗的影响较大，而MEC 服务器具有稳定的供电来源，因此暂不考虑MEC 服务器产生的能耗，而主要考虑用户移动设备产生的能耗。用户ui完成任务所需的能耗主要由两部分组成：用户的本地计算能耗和数据传输到MEC 服务器的能耗本地计算能耗的计算公式如式（8）所示：

其中：Ci是取决于用户设备架构的能量系数。传输能耗的计算公式如式（9）所示：

用户ui完成任务所需总能量Ei的计算公式如式（10）所示：

1.5 问题建模

为平衡用户的时延和能耗，首先对用户进行分组，然后分别计算各组用户的时延和能耗，此处引入用户成本函数Hi，j，用于表示服务器sj的分组内用户ui的综合开销，计算公式如式（11）所示：

其中：αi为调整时延和能量的权重系数，αi∈[0，1]，当αi接近1 时，则该用户更倾向于低时延，当αi接近0 时，则更关注是否满足低能耗，每个用户可根据自己的需求进行设置。因此，优化目标可以表示为式（12）：

2 卸载对象选取策略

为解决用户的卸载对象选取问题，可以先通过计算一个偏好度指标来兼顾基站的距离和负载对用户性能产生的影响［30］，再根据该指标选择卸载对象。用户ui到服务器sj的偏好度如式（13）所示：

其中：表示用户ui到服务器sj的距离；cj表示基站的覆盖范围；表示当前分配给该基站的用户数量；n表示用户总数。偏好度越高，则该基站越有利于用户的任务卸载。为降低原问题的复杂度，在用户确定卸载对象后再对其进行分组，将卸载到相同MEC 服务器的用户分为一组，将原问题分解为多个并行的子问题。

然而当所有用户都选择自己偏好度最大的基站进行卸载时，会存在计算资源和通信资源竞争的问题。假设所有用户同时发送任务卸载请求，每个用户无法得知其他人的卸载选择，都会选择距离最近的基站进行卸载，当大量用户集中在某一基站附近时，如式（1）所示，基站负载的增加会降低该基站内所有用户的性能。当多个用户同时进行任务卸载时，都会为了达到自身的最优而选择卸载对象，但是由于无法及时得到当前基站的负载状态，其他选择反而有可能获得更好的性能，因此，本文考虑采用博弈论的方法得到最优的卸载对象选取策略。

本文使用有限的完全信息非合作博弈策略，每个用户都可以得到自己和其他用户的全部策略信息，由于用户可卸载的基站数量是有限的，因此各用户的策略空间也是有限的。每个用户按顺序进行决策并公开，后决策的用户依据当前状况做出决策，每个用户追求自身最优。

假设用户ui的可选策略集用Xui表示，选择的策略用xi表示，xi∈Xui，其他用户的策略用x-i表示，博弈的最终目标是使网络的全局偏好度最大，全局偏好度ppre*的计算公式如式（14）所示：

其中：U代表所有用户；{}代表用户ui的可选策略集；{(xi x-i)}表示该用户所选策略的偏好度。

由于用户数量和策略空间都是有限的，且每个用户从有限的策略集中选择一个纯策略，使得行动次数也是有限的，因此该卸载对象选取策略中的博弈存在纳什均衡，并可以经过有限次数的迭代后得到均衡点。均衡时的总体最佳策略Xpre*可以表示为：

其中：为用户ui的最佳策略。为获得该平衡点策略，本文提出一种有效的卸载对象选取算法。假设用户能够获取各基站的当前负载、服务器计算能力和基站位置信息。首先，每个用户分别计算到各个服务器的偏好度，服务器初始负载为覆盖范围内的用户数量，用户初始卸载策略为选择偏好度最大的服务器进行卸载；然后，所有用户根据偏好度计算自身是否存在更好的策略，并选取其中能够使全局偏好度最大的策略作为提案与其他用户进行竞争。每次迭代选取对全局偏好度提升最大的用户进行策略更新；最后，将所有用户的偏好度相加得到全局偏好度。

将所有用户提案的更新策略储存到策略更新集Xupdate中，并把全局偏好度更新到偏好度更新集Pupdate中，当Xupdate为空时，表示所有用户已达到当前的最优策略，同时系统达到纳什均衡状态，用户分组算法收敛到全局最优解。卸载对象选取算法的具体步骤如算法1 所示。

算法1卸载对象选取算法

在完成卸载对象选取和用户分组之后，原本多用户多服务器环境下的任务卸载问题被转化为多个并行的多用户单服务器任务卸载问题。由于用户可以将任务的一部分卸载到边缘服务器进行计算，两者是同时进行的，可以显著减少完成任务所需的时间，因此本文采用部分卸载策略对任务进行卸载。然而将任务卸载到服务器上会产生数据上传时延和传输能耗，为了使用户的开销最小化，选择合适的任务卸载比例至关重要。为解决该问题，本文采用萤火虫群优化（GSO）算法来对任务卸载比例进行分配。

GSO 算法是受萤火虫闪烁行为启发提出的算法，各只萤火虫根据适应度函数调整自身荧光素浓度，浓度低的个体向决策范围内浓度高的移动，然后根据决策范围内的萤火虫数量调整决策范围半径，重新在决策范围内寻找更优点进行移动，当达到最大迭代次数时得到最优解。

本文分别对各用户的最优卸载比例进行计算，为每个用户分配一定数量的萤火虫寻找最优解，将卸载比例β∈(0，1)作为萤火虫的移动空间，荧光素浓度通过用户总开销表示。用户ui的第x只萤火虫的荧光素浓度如式（17）所示：

其中：Li，x(a)表示第a次迭代时的荧光素浓度，且Li，x(0)=0；ρ为荧光素挥发系数；η为适应度提取比例；J(βi，x(a))=表示第a次迭代时用户的总开销；βi，x(a)表示第a次迭代时用户ui的第x只萤火虫的初始位置，为(0，1)之间的随机值。

首先根据式（17）计算各萤火虫初始荧光素浓度，由于J(βi，x(a))是关于βi，x(a)的函数，因此可知各萤火虫荧光素初始浓度也为随机值。在此之后，萤火虫个体需要根据决策范围内其他萤火虫的荧光素浓度大小计算移动概率Q，如式（18）所示：

其中：Qx，y(a)表示第x只萤火虫向第y只萤火虫移动的概率，y∈Gx(a)；Gx(a)为a次迭代时第x只萤火虫所有邻居的集合，Gx(a)={y：||βi，y(a)-βi，x(a)||

其中：s为移动步长。萤火虫移动后需要对决策半径进行更新，当决策范围内的邻居密度小于阈值时，扩大决策半径，反之缩小。决策半径的更新方式如式（20）所示：

其中：rs表示萤火虫感知半径；λ表示邻域变化率；ga表示控制萤火虫邻居数的阈值。用户卸载比例算法的具体步骤如算法2 所示。

算法2用户卸载比例算法

3 实验对比

3.1 仿真环境及参数设置

通过Matlab 对实验环境进行仿真，验证所提方案在5G 超密集网络中的实际性能，并与其他同类方案进行对比。仿真所用的相关参数如表1 所示。

表1 仿真参数Table 1 Simulation parameters

为验证本文方案的性能，选择3 种方案进行对比，分别是全本地处理（All-Local Processing，ALP）策略、全卸载策略（All-Offloading Strategy，AOS）和基于粒子群优化（Particle Swarm Optimization，PSO）算法的任务卸载策略。全本地处理策略将全部任务在本地执行，不进行卸载，这种方式避免了数据传输带来的时延和能耗，但会增大用户本地设备处理的成本。全卸载策略将用户的所有任务都卸载到随机可达的边缘服务器，这种方式可以有效减少本地计算带来的能量消耗，但会增加数据上传的能耗，且在传输过程中存在较高的时延。基于PSO 算法的任务卸载策略对任务进行部分卸载，卸载到距离最近的服务器，PSO 算法受到鸟类捕食行为的启发，将任务卸载比例作为优化问题的搜索空间，将每个用户抽象为一个粒子，用于表征问题的一个可行解，这种方式可以快速地找到卸载对象，同时能够对任务的卸载比例进行自适应调整。

3.2 结果分析

根据表1 中的参数进行仿真实验，分别考虑用户数量、用户设备计算能力、权重系数、萤火虫邻域变化率等因素，对所有用户的平均时延和总能耗进行分析，其中平均时延为所有用户时延的总和求平均，而不是所有用户时延的总和，总能耗为所有用户能耗的总和。模拟环境设置在500 m×500 m 的多服务器覆盖场景中，如图2 所示。

图2 模拟超密集网络分布图Fig.2 Distribution diagram of simulated UDN

3.2.1 用户数量对平均时延的影响

用户数量对平均时延的影响如图3 所示。AOS策略的平均时延随着用户数量的增加持续增大，且远高于其他3 种策略，这是因为该策略将全部任务进行卸载，当环境内用户数量增加时，分配给每个用户的带宽资源和计算资源会减少，从而使任务数据上传时延和MEC 服务器的计算时延增加，导致该策略时延过大。ALP 策略将所有任务放在本地执行，平均时延仅与用户设备的计算能力相关，因而不受用户数量变化的影响，由于不存在上传时延和MEC服务器的计算时延，使得平均时延较低，但由于用户移动设备的计算能力比MEC 服务器低，若把全部任务放在本地处理，将会失去计算能力更高的MEC 服务器的协助，进而显著增大本地计算的时延，对总时延造成影响，因此该策略在时延上还存在改进的空间。PSO 和本文策略对部分任务进行卸载，可以根据当前网络状况自适应调节卸载比例，协调本地设备和MEC 服务器同时工作，从而获得更低的平均时延。

3.2.2 不同用户数量对总能耗的影响

不同用户数量对总能耗的影响如图4 所示。ALP 和PSO 策略虽然平均时延较低，但存在着能耗较高的问题，这是因为在不考虑边缘服务器能耗的前提下，能耗主要来自于本地计算能耗和数据上传能耗，ALP 策略将全部任务放在本地执行，会使本地计算量增大，导致能耗迅速增高，而PSO 策略由于所有用户仅选择距离最近的基站进行卸载，导致部分服务器工作负载过大，从而将用户的卸载比例减小，使得本地能耗增加。AOS 和本文策略由于本地计算数据量较小，获得了较低的能耗，然而随着用户数量的增加，分配的带宽资源减少，任务上传速率也会变慢，AOS 策略的传输能耗会随上传时延的增加而迅速增加。根据以上分析，当用户数量增加时，综合时延和能耗两方面来看，本文策略具有更好的表现。

图4 用户数量对总能耗的影响Fig.4 Impact of number of users on total energy consumption

3.2.3 用户计算能力对平均时延的影响

用户计算能力对平均时延的影响如图5 所示。当用户设备的计算能力增强时，由于AOS 策略将全部数据卸载到边缘服务器计算，因而平均时延不受影响，但会导致其上传时延过高。ALP 策略将全部任务放在本地计算，当用户设备的计算能力提升时，平均时延会迅速下降。PSO 和本文策略由于可以根据当前网络状况动态调节卸载比例，因此使得平均时延较小。

图5 用户计算能力对平均时延的影响Fig.5 Impact of user computing power on average delay

3.2.4 用户计算能力对总能耗的影响

用户计算能力对总能耗的影响如图6 所示。AOS策略可以将任务全部卸载到边缘服务器，总能耗不受本地计算能力影响，但导致该策略能耗较高的原因是：虽然仅存在传输能耗，但并不意味着卸载比例越大总能耗越低。本地计算能耗减小的代价是大量数据需要上传到MEC 服务器，使得上传时延远超其他几种策略，而传输能耗和上传时延正相关，使得传输能耗大幅增加，造成总能耗较高。ALP 策略将全部任务在本地执行，总能耗随着用户计算能力的提升迅速增加。PSO策略具有较好的表现但本文所提方法的能耗更低。综上所述，当用户计算能力提升时，本文策略在时延和能耗上的表现更优。

图6 用户计算能力对总能耗的影响Fig.6 Impact of user computing power on total energy consumption

3.2.5 权重系数对时延和能耗的影响

权重系数α可以用来调整用户对能耗和时延的侧重程度，例如在线直播、网络游戏等高实时性应用可以调高该系数，当α接近1 时强调时延对用户的影响，可以有效降低系统平均时延，如图7 所示。对于电池容量有限的移动设备可以减小α，降低系统总能耗，如图8 所示。

图7 权重参数α 对平均时延的影响Fig.7 Impact of weight parameters α on average delay

图8 权重参数α 对总能耗的影响Fig.8 Impact of weight parameters α on total energy consumption

3.2.6 邻域变化率对时延和能耗的影响

邻域变化率是GSO 算法中调整决策范围变化程度的参数。如式（20）所示：当邻域变化率过小时，若决策范围内的邻居数量没有达到领域萤火虫阈值，决策范围不能有效扩大，容易陷入局部最优；当邻域变化率过大且决策范围较大时，萤火虫决策范围内的邻居数量较大，可能会过度减小决策范围，进而陷入局部最优。邻域变化率对时延和能耗的影响如图9、图10 所示，可以看到当邻域变化率接近0.6 左右时效果更好，因此，选择邻域变化率为0.6。

图9 邻域变化率对平均时延的影响Fig.9 Impact of neighborhood change rate on average delay

图10 邻域变化率对总能耗的影响Fig.10 Impact of neighborhood change rate on total energy consumption

4 结束语

本文研究多用户多服务器的超密集网络环境下移动边缘计算的部分任务卸载问题。以最小化所有用户的平均时延和总能耗为目标，将该问题分为卸载对象选取问题和卸载比例选取问题，设计一种基于博弈论和萤火虫群优化算法的卸载策略。针对卸载对象选取问题，综合考虑MEC 服务器到用户的传输距离和MEC 服务器的工作负载，定义偏好度指标。各用户根据偏好度进行博弈，得到最有利于自己和全局的卸载对象选取策略。在此基础上，将选择同一服务器卸载的用户分为一组，使原问题分解为若干个并行的卸载比例选取的子问题。针对卸载比例选取的问题，采用萤火虫群优化算法对各用户的最佳卸载比例进行计算，将任务的卸载比例作为萤火虫的位置，以降低平均时延和总能耗为目标，算法经过多次迭代后得到各用户的最佳卸载比例。仿真实验结果表明，本文策略相比基于PSO 的卸载策略时延降低22%，能耗降低20%，有效提高了系统的运行效率。下一步将考虑服务缓存对应用程序时延和带宽成本的影响，结合缓存决策优化MEC 系统中的任务卸载结构。