计算资源受限MEC中任务卸载与资源分配方法

鲜永菊，宋青芸，郭陈榕，刘 闯

(重庆邮电大学通信与信息工程学院，重庆 400065)

E-mail：xianyj@cqupt.edu.cn

1 引 言

移动边缘计算(Mobile Edge Computing，MEC)技术通过将云数据中心下沉至靠近数据源端的接入网一侧，能够近距离为用户提供计算、通信、存储等能力，同时使得移动网络传输成本更低、效率更高、应用复杂度不受终端的限制[1-3]，在AR/VR、物联网(Internet of Things，IoT)、车联网等场景中有着广阔的应用前景.计算卸载技术作为MEC中十分重要的一环[4]，为移动用户带来了海量计算能力，拓展了用户处理任务的能力.

鉴于此，众多学者针对计算卸载展开了研究，其中卸载策略和资源分配是研究重点.Chouhan与Nguyen等人采用部分卸载划分计算任务，使任务同时在多端进行计算，相较于二元卸载，多端并行计算带来了效率的提升[5，6]；Qin等人通过博弈理论对单用户多MEC问题建模[7]，为单个用户提供了多种卸载选择；在Qin等人方案的基础上，Yi等人提出的卸载方案，更加适合时延敏感场景[8]；另外，Zhang等人通过结合机器学习完成了信道和计算资源的分配，并分析了多种分类器学习效果上的差异[9].还有学者联合卸载策略与资源分配提出方案，其中Ren等人考虑了随机任务到达模型，提出JCRM方案，以提高长期网络的稳定性[10]；Hu等人为任务执行过程中的能耗问题提出了解决方案，并设计基于方向交叉的遗传算法，完成联合优化问题[11].由于资源分配与任务卸载往往是紧密联系的，因此与单独的卸载策略或资源分配的方案相比，联合方案往往能获得更佳的效果.

现有的工作大多都假设MEC计算资源是足够的，请求卸载的任务都可以在满足约束条件下完成计算卸载，MEC服务器不担心出现性能瓶颈.但随时间发展，由基站硬件成本限制所导致MEC服务器计算资源有限的问题将日渐明显，尤其在商圈，机场等任务请求密集的网络中，MEC服务器提供的计算资源往往不足以应对大量请求任务[4].现有的一些卸载方案，在计算资源不足时会导致用户需求无法满足，引发多用户竞争有限的MEC计算资源产生“死锁”问题[12]，导致卸载用户数量下降；同时，在资源不足时，已有方案获得的系统效益往往较差.为改善这些的问题，Ning等人与Wu等人的方案均通过多MEC协作的方式扩展计算资源[13，14]，将MEC无法完成的任务通过二次卸载的方式，交给其他仍有计算资源的MEC执行，但多MEC协作实际需满足的条件十分苛刻，实际的应用价值不大；Liu等人提出一种卸载方案，在MEC没有额外计算资源可用时，通过价格制约卸载的方式保证最大化自身收益，并提出了两种定价策略，比较了方案之间的差异[15]；Zhao等人考虑任务主动缓存的方案[16]，这种方案可以缓存热点计算任务，当同类任务请求时，可以快速响应且不占用MEC计算资源，这样可有效改善热点任务的计算，但随着任务种类的增多，缓存策略带来的收益将十分有限.

基于上述存在的问题，本文通过联合价格约束卸载与计算资源分配的方式，在计算资源受限MEC中实现总收益最大化.主要的工作有以下几个方面：

1) 在计算资源受限MEC中通过调整价格制约任务卸载，并通过Stackelberg博弈建模于MEC与用户之间的交互.在博弈模型分析中，将最大化MEC系统收益的联合优化问题分解为多个子问题.

2) 针对上述问题，为计算资源有限MEC提出了一种差异化定价方法，并在此基础上通过多任务卸载算法完成了任务卸载.

3) 提出了一种改进模拟退火算法用于计算资源分配，算法通过控温策略保证广度搜索能力，通过资源重分配保证深度搜索能力.

2 系统模型

考虑在任务密集区域(如商圈，机场，学校等)的多用户单MEC网络，在一个卸载周期内，有大量用户通过无线链路请求计算卸载，区域内的MEC服务器负责接收请求的计算任务，完成计算后，将计算结果返回用户端.为简化问题，假设每个用户只请求一个计算任务，任务可以按位任意划分，使得任务可以在本地与MEC端并行运算.另外，假设卸载过程中每个用户拥有相同的信道带宽，且每个用户的信道占用不重叠的频率以同时将数据卸载到MEC服务器上，任务卸载时考虑准静态信道模型，信道在卸载周期内保持恒定不变，但可以在不同任务的卸载周期间发生变化，并假设卸载任务将在一定时间内完成计算.

以N={1，2，…，N}表示N个用户的集合，用户i的任务通过二元组Ti(bi，di)表示，其中bi表示任务的总数据量，di表示计算1bit该任务数据所需要的CPU周期数；用户i卸载任务数据量的比例为λi，λi∈[0，1]，即λibi数据量的任务会被卸载到MEC服务器进行计算，使用集合V={λ1，λ2，…，λN}表示N个用户卸载比例集合.用户本地计算能力为floc，i，MEC服务器为多任务提供有限的计算资源fmec，使用集合W={fmec，1，fmec，2，…，fmec，N}表示MEC为N个用户分配的计算资源集合.

为了确保卸载至MEC的任务可以在卸载周期内完成计算，现考虑一个实际的限制条件：设定MEC服务器在每个卸载周期内用于计算接收数据的总CPU周期上限为F[15]，设定F可以确保在计算资源不足的情况下有序地处理到来的任务，F值越大，对应的卸载周期越长.该约束条件为：

∑Ni=1λidibi≤F

(1)

需要注意这里的F和fmec分别是MEC服务器对于卸载CPU周期的总量与计算频率上限.

首先考虑用户与MEC之间的通信，任务的上传速率为：ri=Blog2(1+Ptra，igi/BNo)，其中Ptra，i表示用户i的发送功率，gi表示用户i与MEC服务器之间的信道增益，No表示信道单位噪声与干扰的功率谱密度.

其次，当任务卸载时，用户i本地执行部分任务花费的时间为：tloc，i=(1-λi)bidi/floc，i；任务在MEC服务器端计算部分任务花费的时间为：tmec，i=ttra，i+texe，i，其中ttra，i=λibi/ri，表示用户向MEC上传任务产生的时延，texe，i=λibidi/fmec，i代表任务在MEC端的执行产生的时延；由于MEC向用户回传的计算结果数据量很小，因此回传时间忽略不计.最终用户i完成任务总时延为：

ti=max(tloc，i，tmec，i)

(2)

最后，用户i在本地执行部分任务消耗的能量为：eloc，i=κibidi(1-λi)(floc，i)2，其中κi是与移动用户的硬件架构相关的常数；用户i向MEC服务器发送任务需要的能耗为：etra，i=Ptra，i·ttra，i=λiPtrabi/ri.最终用户i完成该任务的总能耗为：

ei=etra，i+eloc，i

(3)

3 优化问题分析及求解

3.1 Stackelberg博弈分析

在MEC任务执行过程中，用户占用了MEC服务器的计算资源来处理任务，而MEC服务器必须确保其用于计算总卸载数据的可用CPU周期低于F.为了调整计算资源的需求和供给，MEC服务器可对每个用户i的卸载数据的CPU周期bidi收费，以出售自身有限的资源.

对此，Stackelberg博弈可用于建模MEC与用户之间的交互，Stackelberg博弈模型是一种产量领导模型，可以反应非对称竞争关系，并将竞争者角色定为领导者与跟随者.本文将MEC服务器视为领导者，而用户视为跟随者.领导者先对跟随者的CPU周期制定价格；然后，跟随者将依据领导者制定的价格，独立计算其用于卸载的CPU周期，以分别进行本地计算和卸载.

将MEC给用户i单位CPU周期的价格定义为μi，U={μ1，μ2，…，μN}表示所有用户的单价集合，MEC最大化收益问题表示为(主问题)：

P1：maxQ(U，V，W)=∑Ni=1μiλidibi

s.t. C1：μi>0

C2：∑Ni=1fmec，i≤fmec

C3：∑Ni=1λidibi≤F

(4)

式(4)中约束条件C1确保MEC服务器提供的价格为正数，C2确保MEC在并行运算时为每个用户分配的频率不大于总频率，C3确保MEC接收CPU总周期小于上限值.对于用户而言，其主要目的是降低完成任务所需要付出的成本.成本由完成任务付出的时延、能耗以及费用的加权和表示[15].这个问题表示为(从问题)：

P2：minUi(λi)=αiti+βiei+γiμiλidibi

s.t. C1：0≤λi≤1

C2：αi+βi+γi=1

(5)

其中αi、βi和γi分别表示用户i对于执行任务产生的时延、能耗以及费用成本的权重，不同用户权重不同.Stackelberg博弈中的问题P1和P2以一种复杂的方式耦合在一起，即MEC的定价策略与资源分配会影响用户的卸载，而用户卸载又会反过来影响边缘云的收益.

考虑问题中MEC与用户之间的博弈，每个用户都可通过给定价格μi以及fmec，i求解问题P2，独立决定其卸载比例.知道了每个用户的卸载比例，MEC通过求解问题P1来设置其最佳单价集合U、卸载比例集合V以及资源分配集合W，以上过程称为逆向归纳.由于问题是多目标优化，为降低求解难度，将原问题分为3个子问题，分别求解定价策略、卸载策略以及资源分配问题.

3.2 差异化定价策略

本节分析MEC的定价策略，假设分配给用户i的fmec，i已知.先分析跟随者的行为，根据式(5)，用户i的总成本可写为λi的分段函数：

Ui=(γiμidi+βiPtra，iri-βiκidif2loc，i-
αidifloc，i)λibi+αidibifloc，i+βiκibidif2loc，i0≤λi≤φi
(γiμidi+αiri+αidifmec，i+βiPtra，iri-
βiκidif2loc，i)λibi+βiκibidif2loc，iφi<λi≤1

(6)

其中φi=1/(1+floc，i/diri+floc，i/fmec，i)，是在区间[0，1]内的一个卸载比例.公式(6)的前半段表示用户在本地计算的时延较长，后半段表示卸载至MEC服务器的计算时延较长.当λi=φi时表示本地与卸载计算时延相等.为了求解P2，对Ui一阶求导，可得卸载比例与单价的关系，由(7)式给出：

λi=10≤μi≤G1，i
φiG1，i<μi≤G2，i
0G2，i<μi

(7)

此时得到的λi为用户i的最佳卸载比例，用户将根据该比例卸载任务，其中：

G1，i=-βiPtra，iγiridi+βiκif2loc，iγi-αiγiridi-αiγifmec，i

(8)

G2，i=-βiPtra，iγiridi+βiκif2loc，iγi+αiγifloc，i

(9)

此外，式(7)将作为博弈中的反应函数，被领导者观察到.

接着分析MEC服务器行为，领导者根据观察到的反应函数调整μi，MEC的定价策略由定理1给出：

定理1.为使收益最大化，计算资源受限MEC需将μi定为G2，i或正无穷.

证明：为了最大化MEC系统的利润，MEC服务器应在保证用户卸载量不变的情况下，尽可能提高售价，因此MEC服务器应将单价定在反应函数每个分段右界.当满足式(7)第1段时，μi应为G1，i，此时单价较小，用户全部卸载；同理，当满足第2段时，μi应为G2，i，此时单价较大，用户的卸载比例为φi；当定价位于第3段时，μi应为正无穷，此时用户不卸载.显然，定价为G1，i不适合计算资源有限系统；同时，在信道资源充足时，用于传输任务的能耗将小于本地计算该任务带来的能耗[11]，因此G2，i为正数，保证了定价的合理性.故计算资源受限MEC应将价格定在G2，i或无穷高.

证毕

3.3 多用户卸载策略

定价策略决定后，MEC需限制多用户卸载的总CPU周期小于F，通过引入二进制决策变量集合x用来表示用户的卸载决策：

λi=φixi

(10)

其中二进制数xi定义为：

xi=0G2，i<μi
10≤μi≤G2，i

(11)

此时问题P1被重写为：

P3：maxQ(x，U)=∑Ni=1μiφixibidi

s.t. C1：∑Ni=1φixidibi≤F

(12)

根据定理1，当xi=1时，最优价格由G2，i给出.最优价格与用户任务的信息相关，这些信息可以在当用户向MEC服务器发起卸载请求时获取.问题P3可转化为：

P3′：maxQ(x)=∑Ni=1G2，iφixibidi

s.t. C1：∑Ni=1φixidibi≤F

(13)

问题P3′可等效为重量为φibidi，价值为G2，iφibidi，重量限制为F的非整数二元背包问题，该问题是NP-complete的.对问题的求解分为两步，首先设置一个较大的步长Fd，将重量与F进行近似处理，将非整数0-1背包问题转化为整数0-1背包问题，同时减小了问题的规模；接着，通过动态规划思想对问题求解，多用户卸载决策算法实现步骤如下所示.

算法1.多用户卸载决策算法

输入：用户集N，定价策略集G2，CPU周期上限为F，步长Fd

初始化：L=F/Fd；

fori=1：N

forj=1：L

if(j<φibidi/Fd)

V(i，j)=V(i-1，j)；

else

if(V(i-1，j)>V(i-1，j-φibidi/Fd)+G2，iφibidi)

V(i，j)=V(i-1，j)；

else

V(i，j)=V(i-1，j-φibidi)+G2，iφibidi；

end if

end if

end for

end for

最大收益Q*=V(N，L)

输出：最大收益Q*，卸载决策变量x

3.4 基于模拟退火思想的计算资源分配

3.2节与3.3节中的定价策略以及卸载策略均是在计算资源分配已告知用户的条件下得出的，接下来分析计算资源分配问题.

计算资源分配的难点在于多任务决策变量与资源分配变量是耦合在一起的.一方面决策变量需要计算资源分配的结果；另一方面，MEC实际只需为决策变量x中值为1的用户分配计算资源，资源分配同样依赖决策变量的结果.由于以上原因，本文通过模拟退火算法随机寻优的方式完成计算资源分配.模拟退火算法是依靠随机数方法迭代求解的寻优算法，伴随着算法中温度不断下降，解状态会逐渐稳定，这个过程中有概率发生突跳，使得解状态重新进入不稳定状态.

在最大化收益问题中，由于部分用户不卸载，MEC服务器不需要为这些用户分配计算资源，其计算资源分配应为0.含0计算资源分配解极易导致模拟退火算法陷入局部最优解[17]，并很难在有限的迭代中跳出局部最优解.为解决该问题，对模拟退火算法做出两点改进：

1) 计算资源集合W作为算法的解状态，算法中决策变量确定后，需对决策变量中值为1的用户进行计算资源重分配，通过求解凸优化问题解决.

2) 算法加入控温策略，并且算法只考虑基于温度的单层循环，当温度下降至小于1，算法停止.

改进1)可确保解的精度，假设根据卸载策略确定卸载的用户集合M={1，2，…，M}，j∈M代表其中第j个用户，W′={fmec，1，fmec，2，…，fmec，M}表示M个用户的计算资源的集合.此时用户j将以卸载比例φj卸载任务，问题P1可重写为：

P4：maxQ(W′)=∑Mj=1μj11+floc，jdjrj+floc，jfmec，jbjdj

s.t. C1：μj>0

C2：∑Mj=1fmec，j=fmec

C3：∑Mj=111+floc，jdjrj+floc，jfmec，jbjdj≤F

(14)

优化问题P4是分数规划问题，对其进行变量替换，令Yj=fmec，j/[(1+floc，j/rjbj)fmec，j+floc，j]，同时令Zj=1/[(1+floc，j/rjbj)fmec，j+floc，j]，得到集合Y={Y1，Y2，…，YM}.将原问题P4转化为：

P4′：maxQ(Y)=∑Mj=1μjbjdjYj

s.t. C1：μj>0

C2：∑Mj=1Yj=Zjfmec

C3：∑Mj=1Yjbjdj≤F

(15)

C4：Zj≥0

C5：(1+floc，jrjdj)Yj+floc，jZj=1

问题P4′的函数式与约束条件均为凸函数，所以问题P4′是一个凸优化问题，考虑到约束条件里有不等式约束，可通过内点法对其求解[18].

改进2)可降低算法搜索次数，同时增加算法解空间的广度搜索能力.只考虑基于温度的单层循环，将大幅减少迭代次数，但这并没有丢失模拟退火算法的核心思想.

此外，根据Metropolis准则，当前解向一次较差解的移动的概率随着温度的变化而变化，根据这一特征，算法从较大的温度开始，采用相对平缓的温度下降公式Tk=Tk-1×η，(η为降温系数)保证了算法开始有较大的概率接受差解.控温策略是当解没有更新时，以Tk/2T0>random[0，1)的概率保持温度不变，保持算法接受较差解的概率，提高算法的广度搜索能力.改进模拟退火算法的具体步骤如下所示.

算法2.改进模拟退火算法

输入：用户信息，初始资源分配集合W0，初始温度T0

初始化：k←0，σ0←0；

repeat

k←k+1；

While (true)

随机产生置乱集合σk；

Wk←Wk-1+σk；

if (Wk内元素满足约束C2)

break；

end if

end while

根据定理一得到单价集合Uk，多用户卸载决策算法得到xk；

对xk中值为1的用户通过求解凸优化得到计算资源集W′k；

计算目标函数q′；

根据Metropolis准则与控温策略调整解状态Wk，温度Tk.

if (q′>q)

Wbest←W′k，q←q′；

end if

untilT≤1

输出：资源分配Wbest，总收益q

伴随着温度下降，算法在每次迭代中，首先通过随机置乱产生一组资源分配变量；接着根据公式(9)以及算法1多用户卸载决策算法得到卸载决策变量；最后通过求解(15)式的凸优化问题完成计算资源再分配.直至温度下降小于1，迭代结束，否则更新资源分配变量进入下一次迭代.

根据控温策略与温度下降公式，温度可在常数时间内下降至1，即迭代次数k为常数；多用户卸载决策算法需要遍历整个二维数组，时间复杂度为O(NL)；解向量更新的时间复杂度为O(N).故改进模拟退火算法总的时间复杂度为O(kNL+kN).

4 仿真分析

本文仿真分析基于MATLAB平台，参考文献[15]的仿真参数设置：信道总带宽B=1MHz，信道噪声与干扰的功率谱密度为-174dBm/HZ，信道增益在 [-50，-30]dBm内均匀分布.用户i本地的CPU频率floc，i在[0.1，1]GHz中随机取值；任务的数据大小bi在 [100，500]KB中随机取值；单位任务计算量di在[500，1500]cycles/bit中随机取值.默认状态下，算法的初始温度为40，用户数量N=40，用户i的发射功率Ptra，i=0.1W，系数κ=10-27， MEC服务器提供的CPU频率fmec=100GHz，CPU周期上限为F=6×109cycles/slot，降温系数η=0.97.

首先验证本文对模拟退火算法的改进对问题解的影响，图1、图2分别是受初始温度的影响，算法迭代次数与问题解的变化情况.仿真对比了与传统模拟退火算法以及文献[19]中遗传模拟退火算法.由于本文算法增加了控温策略，整体迭代次数多于传统模拟退火算法，但在可接受的范围内.关于算法解质量的对比，本文算法可在较低的初始温度达到解的稳定，并且解的质量较优；传统算法容易陷入局部最优解，解的质量较差；遗传退火算法在模拟退火算法中加入适应性替换方法，可以改善算法过早收敛的问题，但对本文问题的求解效果并不是很理想.因此，改进算法在处理本文联合优化问题有较好的效果.

图1 初始温度对迭代次数的影响Fig.1 Relationship between initial temperature and number of iterations

图2 初始温度对总收益的影响Fig.2 User requests and the actual number of users to uninstall relations

图3 请求用户数对实际卸载用户数的影响Fig.3 User requests and the actual number of users to uninstall relations

图4 CPU周期上限对实际卸载用户数的影响Fig.4 Effect of the upper limit of CPU cycleson the actual number of users uninstalled

图5 用户数量对总收益的影响Fig.5 Number of users relationship with total revenue

图6 CPU周期上限对总收益的影响Fig.6 Relationship between the upper limit of CPU cycles and total revenue

资源有限MEC中所面临的问题主要是由于“死锁”导致卸载用户数量降低，以及解的质量不佳两个问题，接下来分别验证两点，并与基于贪心的卸载算法以及文献[15]中提出的统一卸载算法、非统一卸载算法进行对比.

图3表示总卸载用户数与请求卸载用户数量的关系.当请求卸载用户数量较少时，多数算法都能保证所有用户完成卸载.随着请求卸载的用户数量上升，总卸载用户数也呈上升趋势.由于受到F的限制，实际卸载用户数量到达30左右时，将无法容纳更多用户完成卸载.本文算法联合卸载与资源分配，有利于调整多用户的卸载行为，避免多用户竞争资源引发问题，提高了实际卸载的用户数量，而贪心算法与非统一算法不同程度受到“死锁”问题的影响，用户卸载数量较低，统一算法通过价格限制了很多用户的卸载，因此卸载用户数量最低.

图4表示F值变化对MEC实际卸载用户数量的影响，随着F的增加，实际卸载的用户数量也随之增加.当F值较低时，本文算法相比其他算法卸载用户数提升较明显，这是因为本文算法结合了计算资源分配，计算资源影响用户的卸载量，使得更多用户卸载执行.随着F值增加，4种算法基本都可以满足所有用户卸载.

图5表示请求用户数量与MEC系统收益的关系.仿真结果表示随着请求卸载的用户数增加，4种算法得到的总收益呈上升趋势.当用户数量小于30，收益上升的趋势近似线性增长，这是因为用户数量较小时，MEC服务器所提供的计算资源可以满足所有的用户都进行卸载.当用户数量增多时，4种策略的总收益上升趋势趋于平缓，这是由于用户任务的计算量达到了F上限，限制了一些用户任务的卸载，本文算法中联合了定价、卸载与计算资源分配，优化了用户卸载比例，可以得到最佳用户卸载组合，获得最大的收益.

图6表示F值变化对MEC系统总收益的影响.随着F的增加，可以卸载到边缘云的任务数量也随之增加，4种算法得到的总收益都呈现整体上升的趋势.当F值较低时，本文算法相较其他3种算法的提升比较明显，随着F值的增加，本文算法、贪心算法与非统一算法都获得较好的收益，但本文算法为多用户提供了更合理的计算资源，有最高的总收益.另外统一算法只考虑单一定价方案，导致任务卸载门限变高，因此总收益最低.

5 结 论

本文分析了计算资源有限MEC中任务卸载和资源分配问题.通过价格约束的方法限制部分用户的卸载，同时为MEC设定CPU周期接收上限以保证任务可持续执行，在这基础上解决了最大化MEC系统总收益的联合优化问题：首先通过Stackelberg博弈来模拟MEC与用户之间的交互，通过改进模拟退火算法完成计算资源分配，并在每次迭代中对用户制定差异化定价、卸载决策以及计算资源重分配.最终，算法通过迭代，高效地得到了最佳卸载与资源分配方案，最大程度提高了卸载用户数量，同时有效提高了MEC系统的总收益.