移动边缘计算中基于用户体验的计算卸载方案

杨 天,田 霖,孙 茜,张宗帅,王园园

(1.重庆邮电大学 通信与信息工程学院,重庆 400065;2.中国科学院计算技术研究所 a.无线通信技术研究中心; b.移动计算与新型终端北京市重点实验室,北京 100190)

0 概述

随着5G时代的到来,不断涌现的增强现实[1]、图像识别[2]等新兴应用对计算能力的要求越来越高,但用户设备的计算能力和续航能力限制了用户体验。对此,移动云计算(Mobile Cloud Computing,MCC)[3]可以作为一种有效的解决方案,但其同时给移动回传网络带来了巨大的负载压力,并且存在较高时延。针对这些问题,国内外研究机构与企业提出了移动边缘计算(Mobile Edge Computing,MEC)[4]技术。MEC将云资源下沉到更接近用户的位置,在网络边缘为用户提供云服务。用户可将计算任务卸载至MEC服务器中执行,从而摆脱终端设备计算能力的限制。此外,由于任务数据直接在无线接入网侧进行处理,因此MEC能够减轻回传网络的压力,减小时延[5]。但由于MEC中无线资源与计算资源存在高度共享性,因此为保障用户体验,需要制定合理的计算卸载策略[6-7]。

在MEC计算卸载过程中,时延过高会导致一些应用无法正常使用,而能耗过高则会严重降低移动设备的电池寿命。因此,现有MEC计算卸载方案大多以时延和能耗为优化目标。文献[8]提出一种基于马尔科夫决策过程的时延优化卸载方案,通过分析每个计算任务的平均时延和移动设备的平均功耗并设计一维搜索算法,得到最优任务调度策略。文献[9]设计一种启发式方法对卸载任务进行调度,通过划分用户的计算任务,使所有用户的任务平均完成时间最少。文献[10]提出一种基于遗传算法的次优算法,通过设计一个节能的计算卸载管理方案优化卸载决策、信道分配和计算资源分配过程,从而最小化系统能耗。文献[11]提出一种基于人工鱼群算法的能耗优化方案,从任务执行能耗和通信能耗两方面对卸载问题进行建模,在计算资源和时延的约束下最小化总能耗。

以上研究仅针对单个指标进行优化,没有对时延和能耗进行综合考虑。文献[12]对时延和能耗进行联合优化,将计算卸载问题转换为最小化任务执行开销的多用户卸载博弈问题,通过设计分布式计算卸载算法实现博弈的纳什均衡。文献[13]构建一种计算卸载和干扰管理集成框架,通过最小化任务开销获得最优卸载策略和资源分配。文献[14]将计算卸载问题建模为任务执行成本最小化问题,其中执行成本由时延、能耗以及价格三部分组成,并通过设计分布式势博弈算法和资源分配算法制定计算卸载策略。

在对时延和能耗进行联合优化时,权重因子的设置十分关键。权重因子反映用户对时延和能耗的关注程度,影响卸载策略的制定。上述研究为所有用户统一设置固定的权重因子,表示所有用户对时延和能耗的需求相同。然而在实际场景中,用户需求往往存在差异,因此,统一设置固定的权重因子并不合理,会使制定的卸载策略难以保障用户体验。

针对固定权重因子无法应对用户差异化需求的问题,本文提出一种基于用户体验的计算卸载方案,在多用户移动边缘计算场景下,联合优化时延和能耗。利用用户执行计算任务的时延和能耗性能增益率构建效用函数,将计算卸载问题建模为效用最大化问题,同时通过考虑设备续航能力构建自适应权重因子,对时延和能耗进行权衡。由于所提问题是一个混合整数非线性规划问题(Mixed Integer Nonlinear Programming Problem,MINP),难以直接进行求解,因此将其拆分为卸载决策和资源分配两个子问题,分别通过功率分配算法、计算资源分配算法和计算任务卸载决策算法进行求解,得到最终的计算卸载策略。

1 系统模型

给出一个多用户移动边缘计算场景,如图1所示,其由一个配备有MEC服务器的宏蜂窝小区和多个用户组成。系统带宽划分为N个子信道,每个子信道的带宽为W。用户设备通过OFDMA的方式与基站关联,每个卸载用户占用一条子信道,不同用户设备之间不存在干扰。小区中用户数量为I,用集合Iu={1,2,…,I}表示。假设每个用户都有一个计算任务需要执行,用户i的计算任务表示为Ti={di,ci},其中,di是任务的输入数据量,ci是完成任务所需的CPU周期。参数di和ci都可以通过软件分析得到[8]。

图1 多用户移动边缘计算场景Fig.1 Scenario of multi-user mobile edge computing

用户根据需求可以在本地执行计算任务,也可以将任务卸载到MEC服务器中执行。本文假设所有用户的计算任务是不可分割的,每个用户具有不同的本地计算资源和续航能力,并且无论是本地执行还是卸载执行都可以满足任务的最低时延要求。

1.1 本地计算模型

(1)

对于本地执行能耗的计算,本文使用一种被广泛采用的每周期计算能耗模型ε=κf2[15-16],其中,κ是一个与芯片架构有关的能量因子,此处取κ=10-26。因此,用户i的本地执行能耗为:

(2)

1.2 卸载计算模型

任务卸载执行时,用户通过基站将任务数据发送到MEC服务器,由MEC服务器进行数据处理,并将结果反馈给用户。因此,任务卸载执行的时延包括3个部分,即卸载任务到MEC服务器的上行传输时延、MEC服务器的处理时延和反馈结果的下行传输时延[5]。

用户i的上行传输速率为:

(3)

其中,pi为用户i的上行发射功率,hi为信道增益,σ2为噪声功率。

得到上行速率后,根据已知的输入数据量,可以计算得到用户i的上行传输时延为:

(4)

(5)

由于反馈结果的数据量远小于输入数据(系统设置、程序代码和输入参数)的大小,下行传输的时延在计算卸载研究中往往可以忽略不计[17-18],因此本文不考虑下行传输的时延。用户i任务卸载执行的总时延为:

(6)

对于卸载执行能耗的计算,由于MEC服务器通过电缆供电,因此本文不考虑MEC服务器的执行能耗[10-12]。用户i的卸载执行能耗为:

(7)

2 计算卸载问题

2.1 用户效用

任务卸载执行的目的是获得比本地执行更好的性能表现,从而提升用户使用体验。因此,本文采用时延和能耗的性能增益率作为效用函数。性能增益率[19]表示为:

(8)

其中,Dgr和Egr分别是时延和能耗的增益率。进而用户i的效用定义为:

(9)

2.2 自适应权重因子

(10)

(11)

其中,ε是一个缩放因子,用于调节电量剩余率与权重因子的对应关系。由式(10)和式(11)可知,每个用户的权重因子大小与自身剩余电量相关,高电量用户的时延权重因子更大,低电量用户的能耗权重因子更大。

2.3 问题描述

将计算卸载问题转化为一个资源约束下的系统效用最大化问题,定义为:

s.t.

C1:ai∈{0,1},∀i∈Iu

C3:0

(12)

其中:A表示卸载用户集合;P表示卸载用户的功率分配集合;F表示卸载用户的计算资源分配集合;pmax为用户设备的最大发射功率;fmax为MEC服务器计算资源总量;约束条件C1限制用户的卸载决策变量为二进制整数变量;约束条件C2表示卸载的用户数不得超过子信道数;约束条件C3表示卸载用户设备的发射功率不得大于最大发射功率;约束条件C4保证卸载集合中的用户都能获得MEC服务器分配的计算资源;约束条件C5表示所有卸载用户分配到的计算资源总和不得超过MEC服务器资源总量。

式(12)是一个混合整数非线性规划问题,其为NP难问题。因此,本文将该问题分解为卸载决策子问题和资源优化子问题分别求解。

3 基于用户体验的计算卸载方案

将式(12)改写为如下形式:

s.t. C1～C5

(13)

由于约束条件中卸载决策变量和资源分配变量完全解耦,因此可以将式(13)拆分成资源分配和卸载决策两个子问题分别求解。首先固定卸载决策变量求解资源分配问题,然后在确定资源分配的情况下进行卸载决策求解。

3.1 资源分配

由式(13)拆分出的资源分配子问题为:

s.t. C3～C5

(14)

对于给定的卸载策略,将式(8)和式(9)代入式(14),得到:

(15)

(16)

可以看出,式(15)中减号左侧项为常数,因此,求解式(15)的最大值等价于求解式(16)的最小值。将式(1)～式(7)代入式(16)后,资源分配子问题转化为:

(17)

根据式(17)可进一步将资源分配问题分解为上行发射功率分配问题和计算资源分配问题。

3.1.1 上行发射功率分配

由式(17)拆分出的上行功率优化子问题为:

s.t. 0

(18)

由于g(pi)的二阶导数在定义域中并不总是为正,因此式(18)问题是非凸的。在文献[19]中,该问题已被证明是一个拟凸问题。本文采用文献[20]提出的二分法对其进行求解。

g(pi)的一阶导数为:

(19)

可以看出,g′(pi)的正负完全取决于等号右侧的分子部分,令:

(20)

算法1上行发射功率分配二分法

输入pmax,θi,φi,ni,ε,ei

根据式(20)计算υ(pmax)

ifυ(pmax)≤0 then

else

令ph=0,pt=pmax

repeat

pm=(ph+pt)/2

ifυ(pm)≤0 then

ph=pm

else

pt=pm

end if

until(pt-ph)≤ξ

end if

3.1.2 计算资源分配

由式(17)拆分出的计算资源分配子问题为:

s.t. C3,C4

(21)

(22)

(23)

3.2 卸载决策

由式(13)拆分出的卸载决策子问题为:

s.t. C1,C2

(24)

经过资源分配后,卸载决策子问题转化为:

s.t.|A|≤N

(25)

假设已有卸载用户集合S,记ΔU(S∪i)为用户i加入S后系统效用的增量,则有:

ΔU(S∪i)=U(S∪{i})-U(S)=1-Δ(i)-Δ(i|S)

(26)

可以看出,Δ(i)与卸载决策无关,在得到功率分配后这一项变成常量,且恒大于0。Δ(i|S)是一个与当前卸载用户集合大小有关的变量,其随卸载用户集合规模的增大而增大。因此,ΔU(S∪i)是一个随卸载用户集合增大而减小的单调递减函数。若ΔU(S∪i)>0,则表明将用户i加入当前的卸载用户集合S后系统效用增大。

当S=ø时Δ(i|S)取到最小值0,此时Δ(i)在功率分配后是已知的。因此,当ΔU(S∪i)=1-Δ(i)时ΔU(S∪i)取到最大值,记为ΔU(S∪i)max。若ΔU(S∪i)max≤0,则表明卸载用户i肯定无法使得系统效用增大,那么用户i需要直接在本地执行计算任务。令集合AL表示初始本地执行集合,在分配功率后可以直接筛选出所有ΔU(S∪i)max<0的用户并添加至AL。

如前所述,ΔU(S∪i)随着集合S规模的增大而减小。得到AL后可以求得ΔU(S∪i)的最小值,即ΔU(S∪i)min=ωi-Δ(i)-Δ(i|Smax),其中,Smax=Iu(AL∪{i})。如果ΔU(S∪i)min≥0,则表明将用户i加入卸载集合能够增加系统效用,即使卸载用户集合的规模已经达到上限。令集合AC表示初始卸载用户集合,将所有满足ΔU(S∪i)min≥0的用户筛选出来直接添加至其中。确定AL和AC后,Iu中剩余用户组成集合ARE。

基于以上分析,本文提出一种计算任务卸载决策算法。首先根据最大和最小效用增量进行初始决策,得到AL和AC,然后根据AC中用户数与子信道数的关系进行二次决策。算法描述如下:

算法2计算任务卸载决策算法

输出A,F

初始化AL=ø,AC=ø,ARE=ø,S=Iu

//初始决策

根据ΔU(S∪i)max是否小于0得到AL

根据ΔU(S∪i)min是否大于0得到AC

//二次决策

令A←AC

if|A|≥N then

while|A|>N

update A=A{i}

根据式(22)计算F

end while

else

repeat

//加入效用最大且系统效用增量为正的用户

if ΔU(A∪i)>0

update A=A∪{i}

根据式(22)计算F

end if

until|A|=N or ∑U=max∑U

end if

4 仿真与结果分析

对本文方案进行仿真及分析验证。考虑一个多用户移动边缘计算场景,小区中用户随机分布,信道建模采用l-α,其中,l为用户到基站的距离,α为路径损耗因子,此处取α=3[10]。计算任务为人脸识别任务,输入数据量di为420 KB,所需CPU周期数ci为1 GHz/s[15,20]。其他仿真参数如表1所示。

表1 仿真参数Table 1 Simulation parameters

选用以下方案与本文方案进行对比:

方案1全部本地执行,即小区中所有用户的计算任务在本地执行。

方案2固定时延因子为0.5,即所有用户时延权重因子统一设置为0.5,能耗权重因子设置为0.5。

方案3固定时延因子为0.2,即所有用户时延权重因子统一设置为0.2,能耗权重因子设置为0.8。

方案4固定时延因子为0.8,即所有用户时延权重因子统一设置为0.8,能耗权重因子设置为0.2。

4.1 不同用户总数下的系统性能

各方案在不同用户总数下的卸载用户数对比如图2所示。可以看出,当用户总数小于5时,5个方案中所有用户都完成了卸载执行任务,此后随着用户总数的增加,各方案的卸载用户数出现差异,时延权重因子的值越小,卸载用户数越多。本文方案在相同用户总数的情况下卸载用户数仅次于时延因子设置为0.2的方案,而在全部本地执行的方案下,所有用户本地执行任务,因此卸载用户数为0。

图2 不同用户总数下的卸载用户数Fig.2 Number of offloading users under different total number of users

不同用户总数下各方案的性能对比如图3所示。由图3(a)可以看出:全部本地执行方案系统效用为0;在固定权重因子方案中,时延因子越小系统效用越大;本文方案的系统效用仅低于方案3。由图3(b)可以看出:全部本地执行方案耗费能量最多;在固定时延因子的方案中,时延因子越小能耗越小;本文方案的能耗较低,仅高于方案3。由图3(c)可以看出:时延因子越小时延越高,尤其是在系统效用和能耗指标中处于最好水平的方案3,总时延在各方案中也为最高;全部本地执行方案的总时延处于次优水平;本文方案的总时延小于方案3,但高于其他方案。

综上所述,任务卸载执行能够显著降低能耗。对于时延性能而言,当卸载用户数较少时能够分得充足资源,因此,卸载时延会低于本地执行时延,这也是图3(c)中方案4总时延低于方案1的原因。但是当卸载人数较多时(例如方案3),卸载用户分得的资源变少,此时卸载时延会高于本地执行时延。

图3 不同用户总数下的系统效用、能耗和时延Fig.3 System utility,energy consumption and delay under different total number of users

虽然在系统效用对比中,方案3的系统效用高于本文方案,但对于具有不用剩余电量的用户而言,整体效用的大小不能完全反映实际的用户体验。当用户存在差异化需求时,为追求整体效用可能会牺牲一些用户的体验。下文将对此进行验证。

4.2 不同电量剩余率下的用户任务执行时延和能耗

以电量剩余率作为变量,生成10个具有随机剩余电量的用户,在不同方案下制定卸载策略,通过对比这些用户的任务执行时延和能耗,验证本文方案对于满足用户差异化需求的有效性,其中不同的剩余电量映射不同的用户需求。

本文方案下的用户电量剩余率如图4所示,其中:电量剩余率高于0.7的用户为高电量用户,这些用户的需求为更低时延;电量剩余率低于0.3的用户为低电量用户,这些用户的需求为更低能耗;其余用户属于普通用户,这些用户没有特别明确的某一方面性能要求。由此可见,在10个用户中,用户4及用户6～用户8属于高电量用户,用户2、用户5和用户9属于低电量用户,其余用户属于普通用户。

图4 本文方案下的用户电量剩余率Fig.4 Power remaining rate of users under the proposed scheme

本文方案与方案3、方案4下各用户的卸载决策如图5所示。可以看出:在方案3下,除用户2以外的其他所有用户都卸载执行任务;在方案4下,用户5和用户10选择卸载执行,其中用户5是低电量用户,用户10是普通电量用户,其余低电量用户的任务在本地执行;在本文方案下,用户1、用户2、用户5、用户9和用户10卸载执行,所有低电量用户均选择卸载执行任务,其余卸载用户的电量也相对较低,处于即将进入低电量状态。

图5 3种方案的卸载决策对比Fig.5 Offloading decision comparison of three schemes

本文方案与方案3、方案4的时延和能耗对比如图6和图7所示。可以看出:卸载用户过多,使得每个用户分得计算资源过少,方案3下所有用户的时延较其他方案最高,导致更关注时延的高电量用户(用户4及用户6～用户8)体验较差,但大量用户卸载使得能耗得到降低,低电量用户5和低电量用户9体验良好,而低电量用户2未得到卸载,能耗过高;在方案4下,大量用户本地执行任务,时延较其他方案最低,卸载执行的用户5和用户10获得大量计算资源,得到比本地执行任务更低的时延;然而从能耗上看,方案4下除卸载用户以外其余所有用户能耗都过高,这对低电量用户的体验产生了负面影响;本文方案中卸载执行任务的用户时延较高,但仍低于方案3,并且这些用户都属于低电量用户,更关注能耗,而所有高电量用户都在本地执行任务,时延较低,从而保障了这些用户的体验;从能耗上看,卸载执行的用户能耗大幅度降低,其中包括所有低电量用户以及用户1和用户10这两个即将变为低电量状态的用户,保障了这些用户的体验,用户3、用户4及用户6～用户8的能耗较高,但是由于这些用户电量充足,因此影响不大。由此可知,本文方案制定的卸载策略更为合理。

图6 3种方案的时延对比Fig.6 Delay comparison of three schemes

图7 3种方案的能耗对比Fig.7 Energy consumption comparison of three schemes

综上所述,固定权重因子的方案无法满足差异化的用户需求,而本文提出的计算卸载方案可根据用户实际情况自适应调整权重因子大小,使时延和能耗之间得到有效平衡,能够保障用户的良好体验。

5 结束语

为满足具有不同剩余电量用户的不同计算卸载需求,本文提出一种考虑用户体验的计算卸载方案。通过构造基于电量剩余率的自适应权重因子,描述用户在完成计算任务时对时延和能耗的要求。该方案可根据用户状态制定合理的卸载策略和功率及计算资源分配策略,在满足用户对时延和能耗要求的前提下实现最大的系统效用,提升用户体验同时保证计算卸载的整体性能。本文方案假设计算卸载发生在准静态场景,未考虑用户移动性对计算卸载的影响,并且其仅针对单小区MEC系统制定卸载策略,未考虑多小区场景下的信道分配问题。因此,下一步将对超密集网络场景下的多接入边缘计算卸载方案和动态信道下的计算卸载方案进行研究。