(河海大学计算机与信息学院,南京 211100)
以虚拟现实、现实增强、网络游戏、图像识别等为代表的一批新应用不断涌现,其产生的移动数据流量与日俱增,思科预计,从2016—2021 年,虚拟现实和现实增强产生的流量将增长为原来的20倍[1]。这些应用的任务通常是计算密集型和时延敏感型的任务,计算量相对较大,同时对时延的要求较高。然而当前移动设备的计算能力非常有限,在移动设备本地执行这些任务根本无法满足时延的要求;同时,移动设备的电力存储也非常有限,当自身完成这些计算量较大的任务时,会带来高额的能源消耗,不利于移动设备的长久工作。因此,这些应用任务给移动设备带来了极大的挑战。
移动云计算(Mobile Cloud Computing,MCC)[2]曾经被认为是一种很有前途的减轻计算任务负担的方法,远程云拥有强大的计算能力和充足的计算资源,可以为用户提供充足的资源,还可以节约任务在本地计算的能耗。然而,通常情况下移动设备与远程云在空间上距离较远,将任务卸载到云服务器会导致高额的通信开销。对于时延敏感性的任务,会给用户造成糟糕的体验,无法满足用户需求。
为了弥补MCC 在时延问题上的不足,提出了移动边缘计算(Mobile Edge Computing,MEC)[3]。移动边缘计算的核心思想是将服务器的计算和存储等资源下沉到网络边缘以及用户附近,通过边缘服务器为用户提供计算、存储等服务,解决移动云计算中高额通信时延的问题。移动边缘计算通过计算卸载技术将任务卸载到MEC 服务器上,解决由移动设备计算能力不足带来的一些问题。
如图1 所示,当有用户设备(User Equipment,UE)请求任务卸载时,通过无线网络直接将相关数据发送到部署在基站附近的MEC 服务器。MEC 服务器根据当前资源情况与用户任务需求,决定将用户任务卸载到MEC 服务器上来计算完成。用户任务不再需要经核心网络发送给远程云,极大了减少了传输时延。但是,MEC 服务器的资源相较于远程云来说是极为有限的,很难在所有时间段为用户提供满意的服务,因此如何有效地分配MEC 服务器中的计算资源,提出满足用户需求的任务卸载决策,成为了一个新的挑战。
图1 用户任务卸载示例Fig.1 Example of user task unloading
本文考虑以最小化时延为单一目标的卸载策略难以满足用户需求,针对独立任务场景下多用户任务卸载问题,使用博弈论中稳定匹配的理论,把任务卸载过程比作是相互匹配的一个过程。针对以最小化时延为单一目标的卸载策略难以满足用户需求的问题,在综合考虑时延与能耗基础上通过对问题进行建模分析,提出了基于稳定匹配的多用户任务卸载策略(Multi-User Task Offloading strategy based on Stable Allocations,MUTOSA),在保证用户时延的要求下达到能耗最小化,保证更多用户的需求。
MEC 是一种将服务下沉到网络边缘的一种计算模型[4-5]。通过任务卸载技术将任务卸载到合适的服务器上计算,解决移动设备因其计算能力有限带来的高能耗、高时延等问题。
任务卸载过程中不同的场景会有不同的卸载策略。
1)按照用户设备数量划分,卸载策略可以分为单用户卸载和多用户卸载。Mao 等[6]研究在单用户设备场景下卸载决策问题。以执行时延和任务失败的执行成本为性能指标,提出了一种基于低复杂度在线Lyapunov 优化的动态计算卸载算法。Li等[7]致力用无人机作为移动边缘节点为多个用户提供计算任务卸载服务。该策略的目标是在无人机上以有限的能量最大化用户任务的迁移吞吐量。Zhang 等[8]针对5G 异构网络中的多个移动设备,提出了一个在满足时延约束的同时系统能耗最小化的节能优化问题,设计了一个三阶段的计算卸载方案。在实际应用场景中,基本都是多用户的情况,因此在本文中,考虑的是多个用户的任务卸载问题。
2)按照卸载目标划分,任务卸载可以分为面向时延的任务卸载、面向能耗的任务卸载、权衡时延和能耗的任务卸载。Guo 等[9]提出了一种混合整数规划的卸载策略,研究如何将移动应用的计算密集型任务从资源稀缺的移动设备动态地转移到位于边缘网络的服务器上,以最小化平均任务完成时延为目标。Alameddine 等[10]关注对延迟敏感的计算任务卸载,提出了一种基于逻辑的曲向分解方法。Huang 等[11]研究的是多个无线设备选择将计算任务卸载到边缘服务器的场景。综合考虑能耗和响应时延,提出了一种适用于MEC 网络分布式的基于深度学习的卸载算法。Zhang 等[12]考虑边缘人工智能场景中能耗和时延的加权优化问题,提出了一种退潮算法来求解该模型。在实际场景中,时延直接影响的用户体验,终端能耗决定了用户设备的工作时长。现有卸载策略多以最小化时延为单一目标,难以满足用户需求的问题。
本文综合考虑时延和能耗,对多用户场景下的独立任务卸载问题进行建模,提出了基于稳定匹配的多用户任务卸载策略,卸载目标是在满足用户时延情况下最小化能耗,不仅给用户带来良好的体验,还可以保证用户设备的长久工作。
图2 展示了网络模型。用户设备将卸载请求发送到基站,基站将任务卸载到MEC 服务器或远程云服务器。终端UE 通过无线网络直接连接的边缘服务器计算节点称为服务节点,本文假设服务节点为一个。每个UE有一个或者多个独立任务,该任务不可分割。任意两个MEC 服务器可以进行通信,来相互帮助完成超额的任务。若所有MEC 服务器仍不能满足用户任务需求,MEC 服务器可以将任务提交到远程云计算。
图2 多任务卸载场景Fig.2 Multi-task unloading scenario
假设在一个时隙内有N个用户任务请求。所有UE 在通信过程中,不存在用户间的干扰。总带宽B被分成H个信道。用户通过正交频分多址将请求和数据上传到基站,其中同一信道中的每个用户与其他用户正交,并且每个信道只能分配给一个用户。每个用户任务Ui由三元组{datai,cyclesi,delayi}表示,其中datai表示任务i的输入数据规模,cyclesi表示完成计算任务所需的CPU 周期数,delayi表示完成任务i的最大容忍时延。
2.2.1 时延模型
完成任务i的响应时延ti由两部分组成,分别为计算时延和通信时延。即:
1)计算时延。假设有M个MEC 服务器,设任务i所在的UE 本地计算能力为LCi(1 ≤i≤N),MEC 服务器k的计算能力为ECk(1 ≤k≤M),远程云的计算能力为RC。由此可以得到任务在每个计算节点的计算时延。
当任务i在本地计算,计算时延为:
当任务卸载到第MEC服务器k中,计算时延为:
每个用户任务Ui为一个三元组,且是不可分割的一个原子任务,因此用户任务只能由本地设备、MEC 服务器和远程云三者中其中一个节点来完成计算。αi、βi、γi表示每个任务都有可能在本地、MEC 服务器或者远程云服务器上计算。αi+βi+γi=1,αi,βi,γi∈{0,1}保证每个任务只能由三者中的一个来处理。
2)通信时延。基站通常位于本地区域的MEC 服务器附近,因此忽略基站到MEC 服务器的通信时延。此外,由于计算结果的输出数据规模远小于从UE 发送到远程服务器的输入数据规模,所以忽略反向链路的通信开销。
本文主要关注从UE到基站、基站到基站和基站到远程云的上行链路通信开销。用户任务i到MEC 服务器k的传输速率ri,k可以用式(6)[13]表示:
其中:ω表示带宽,因为总带宽B被分成H个信道,所以ω=表示用户任务i的UE 传输功率。采用阴影衰落系数为σc和噪声功率为N0的瑞利信道模型。信道模型中的参数Γ表示保证最小误码率的信噪比。假设信道系数hi是完美估计,并且在整个传输周期中信道衰落是恒定的。λ是路径损耗指数。d表示用户任务i与服务节点k的距离。
当需要卸载到非服务节点的MEC 服务器时,需要服务节点做转发工作。多个MEC 服务器的拓扑结构为全连接[14],即两两相连,如图3 所示。每个边缘服务器节点可以直接和其他所有的节点进行通信。两者的通信速率可以表示为:
其中:j,k表示不相同的两个MEC 服务器;为MEC 服务器k的传输功率;dk,j表示服务节点k与其他MEC 服务器j的距离;hk为信道系数,假设其为完美估计,并且在整个传输周期中信道衰落是恒定的。
图3 服务器的拓扑结构Fig.3 Topology of servers
如果卸载决策将任务卸载到远程云中时,服务节点也需要做转发工作,假设πk为MEC 服务器k将计算数据发送到远程云的传输速率。综合式(6)和式(7)可以得到通信时延为:
其中:βE表示任务是卸载到服务节点还是其他MEC 服务器,当卸载在服务节点时为1,卸载到其他MEC服务器时为0。若在本地执行,通信时延为0。
2.2.2 能耗模型
在本文中,能耗仅考虑UE端。因为UE能量有限,为保持长久工作,提高用户体验,能耗是不可忽略的重要因素。UE端能耗主要有两个方面:计算能耗与通信能耗。当用户任务在本地计算时,只存在计算能耗;当用户任务卸载服务器上计算时,则只有通信能耗。因此能耗ei可以表示为:
当任务不在本地计算时,传输能耗仅仅由用户i到MEC服务器k的传输时间决定,与其他的因素无关。
本文的目标函数是满足用户延时的前提下,使得用户终端能耗最小,最大化所有用户的满意度(Degree of Satisfaction,DoS)。单个用户满意度定义为:
其中:DoSi表示用户满意度,任务响应时延小于等于最大容忍时延为1,否则为0。对于满足时延的用户,最小化用户终端能耗。对于无法满足时延的用户,优先选择时延最小的节点来计算任务,不考虑能耗问题。综上,最大化所有用户满意度的目标函数可以表示为:
本文运用博弈论中双边匹配的知识来解决上述问题。所谓双边匹配就是一个集合中的元素与另一个集合中的元素进行一对一、多对一或者多对多的匹配。把所有用户任务看作是一个集合,所有计算节点看作是另一个集合。任务卸载过程可以看作是一个或者多个用户任务匹配一个计算节点的双边匹配。稳定匹配是双边匹配中达到纳什均衡的一种状态以及博弈理论[15]。当双方达到稳定匹配的状态时,总体的收益最高。
定义1偏序关系。令X是一个集合,X上的偏好关系是一个双向关系,满足:
1)对每个x≠y,有x≻y或者y≻x,关系是完备的。
2)x≻x不成立,关系是非自反的,即x不会优于自身。
3)如果x≻y且y≻z,那么x≻z,关系是传递的。
定义2匹配问题。一个匹配问题可描述为:存在两个集合,任务集合T和服务器集合M。自然数n表示两个集合中元素的数量(假设任务和服务器的数量一样多)。
每个服务器在任务的集合上有一个偏好关系。一个任务t认为服务器m1优于服务器m2,这个关系表示为:
定义3双边匹配。就是以双边匹配为研究对象,研究具有稳定偏好的不相交的双方的匹配过程。本文中的匹配是一个从任务集到服务器集的双射。
等价的匹配n个配对{(t1,m1),(t2,m2),…,(tn,mn)},使得{m1,m2,…,mn}=M和{t1,t2,…,tn}=T成立。对于一个配对(t1,m1)被包含在了一个匹配中,就说任务t1匹配给了服务器m1。后面用大写字母A、B或C等表示一个匹配。
定义4匹配反对。一个服务器和一个任务反对一个匹配,条件是:它们认为对方存在一个个体优于自己在当前匹配下被匹配给的个体。一个匹配是稳定的条件是:不存在这样的反对。
定义5稳定匹配。匹配A是稳定的条件是,当一个服务器认为另一个任务优于在A匹配下的他的伴侣,而这个任务认为在A匹配下,自己所匹配的服务器优于其他服务器。
定理1稳定匹配永远存在[16]。
证明 当没有任务被服务器拒绝时,算法终止。假设本地和远程云中心没有资源限制,因此最终所有任务都会被匹配到。假设此时得到的匹配是不稳定,那么至少存在一个任务和一个服务器,称为T0和M0,它们认为对方优于在算法下配给自己的伴侣。假设算法把T0匹配给了M1,把M0匹配给了T1,因为T0认为M0优于M1,那么T0在向M1匹配前,一定向M0匹配过,M0匹配T1,M0认为T1优于T0。这就跟T0和M0反对这个匹配的假定矛盾,所以此时的匹配是稳定匹配。因此稳定匹配永远存在。
定义6形式化的稳定匹配。如果按照偏好赋予一定的权值,那么一个稳定的匹配一定是权值最大的匹配(默认权值按照偏好依次从大到小赋值)。
定理2对于稳定匹配,存在两个集合M和T,如果由M方发起匹配,则最后形成的匹配,对于集合M中所有元素来说是利益最大的匹配结果;反之,对于T集合亦然。
证明 设一个稳定的匹配C是由M和T两个集合中M发起匹配形成的,因为每一次M中的元素都是选择偏好最优的,如果被拒绝,再选择偏好顺序中的下一个,所以最后形成的匹配,对于M中的每一个元素来说,一定是当前可选择情况下最好的选择,那么相对应的M集合所有元素得到的总权值一定是所有稳定匹配中最大的。
在进行双边匹配时,双边的各个元素都会有对边所有元素的一个偏好排序,首先要制定这个排序规则。本文最终目标是在用户时延允许内的能耗最小,因此分为两种情况:满足时延要求和不满足时延要求。
1)满足时延要求。如果三者中存在可以满足用户要求的计算节点,那么可能会出现多种情况。这里假设用户为0,边缘节点为1,远程云为2,满足时延的情况会有23-1种,这里去掉了空集的情况(即不满足的情况)。最终的7 种情况如表1所示。
表1 满足时延情况下的能耗对比Tab.1 Comparison of energy consumption in case of satisfying delay
2)不满足时延要求。如果出现了三者都不能满足要求的情况,那么选择三方中时延最低的,按照延时升序排序。这种情况不考虑能耗。
在本文中假设远程云的最大计算资源限制是无限大的。计算节点对任务的偏序规则是按照任务的时延要求升序排序,时延要求越小,则优先级越高。假设边缘节点会有最大计算资源限制,允许几个任务在当前节点同时运算但会限制任务计算量,远程云的这个最大计算资源限制设为∞。多用户任务卸载算法是迭代进行的。
本文提出的基于联盟博弈的服务器联盟形成策略如算法1所示。
算法1 基于稳定匹配的多用户任务卸载策略(MUTOSA)。
输入:Ui,LCi,ECk,RC,D,ω,σc,N0,λ,Γ,PTi,PTk;
输出:用户满意度。
算法主要步骤如下所示:
1)任务选择自己偏好中优先级最高的计算节点(14)~16)行代码)。
2)每个计算节点从选择它的任务中,按照每个自身对任务的偏好选择最大计算资源限制允许范围内的多个任务留在该节点,拒绝余下的超过最大计算资源限制的任务(17)~20)行代码),然后通过3)、4)不断地迭代。
3)在前面阶段被计算节点拒绝的每个任务,从没有拒绝它的计算节点中选择偏好最优的一个节点(22)~25)行代码)。
4)每个计算节点从选择它的任务中,按照偏好关系,选择最大计算资源限制允许范围内的多个任务留下,拒绝余下的超过最大计算资源限制的任务(26)~29)行代码)。
5)没有任务被节点拒绝时,算法终止。
在算法终止时,所达到的就是一个稳定的匹配,一个稳定的匹配就是双边中的元素对这个匹配都没有异议,可以在用户允许时延要求下实现能耗最小,达到最大的用户满意度。
通过计算机仿真实验评估基于稳定匹配的多用户任务卸载策略的有效性,实验平台为IDEA。实验仿真参数[13,17-20]如表2所示。
评估的指标分别为用户满意度、策略执行时间和用户总能耗3 个主要方面。用户满意度表示的是能够在容忍时延内完成的任务数量与总任务数量的比值;策略执行时间是每种卸载策略对各种信息综合处理,得出卸载决策计算所用的时间;用户总能耗表示的是执行卸载决策所有用户所消耗的能量总和。
为了评估基于博弈论稳定匹配任务卸载策略的有效性,实验比较了以下卸载策略的用户满意度。
1)本地运行策略(Local Computing,LC):所有任务都在移动设备运行。
2)远程云卸载策略(Remote Cloud,RC):任务全部卸载到远程云中心运行。
3)基于Lyapunov 优化的在线算法(Online Algorithm based on Lyapunov Optimization,OALO)。
4)基于遗传算法的启发式卸载策略(Heuristic Offloading Strategy Based on Genetic Algorithm,HOSBGA):运用启发式算法(本文采用遗传算法)来求得较优解。HOSBGA 实验参数:种群规模60,交叉概率0.5,变异概率0.1。
5)基于稳定匹配的多用户任务卸载策略(MUTOSA):通过结合博弈论中的稳定匹配来对任务进行卸载判断,选择合适的计算节点。
表2 主要参数设置Tab.2 Main parameter setting
4.2.1 用户满意度
用户满意度是本文中最重要的评估指标,是能够在容忍时延内完成的任务数量与总任务数量的比值。图4 显示了在五种策略下任务数量对用户满意度的影响情况。由图4 可以看出,在不进行任务卸载时,即在本地运行,LC 策略的用户满意度一直维持在45%左右,此时影响用户满意度的主要因素为UE 本地设备的计算能力。而相较于LC 策略,RC 策略是把所有的任务全都卸载到远程云,通信时延比较大。相较于LC和RC 策略,OALA、HOSBGA 和MUTOSA 都有着比较高的用户满意度。随着用户任务数量的增多,OALA、HOSBGA 和MUTOSA 的满意度都呈现下降趋势;但是MUTOSA 的下降趋势比较缓慢,当任务数量达到140 的时候,仍能保持用户满意度90%以上。具体而言,相较于OALA 和HOSBGA,当用户任务数量增多时,MUTOSA 分别可以最高提高15个百分点和10个百分点的用户满意度。
图4 任务数量对用户满意度的影响Fig.4 Effect of task number on user satisfaction
图5显示了MEC服务器最大资源限制在五种策略下对用户满意度的影响。由图5 可以看出,LC 与RC 两种策略与MEC 最大资源限制是不相关的。OALA、HOSBGA 和MUTOSA 三种策略满意度都会随着MEC 服务资源增加而提高。
图5 MEC容量对用户满意度的影响Fig.5 Effect of MEC capacity on user satisfaction
同时,当最大资源限制在12 之前时,满意度的提升明显;当超过12 时,满意度的提升减缓。三者相比较,MUTOSA 的上升趋势较小,这是由于MUTOSA 策略达到当前场景下最大的用户满意度,未能满足的用户任务数量相较于总数较小,因此提升幅度较小。相较于OALA 和HOSBGA 策略,MUTOSA策略分别提高了约8%和10%的用户满意度。
4.2.2 策略执行时间
图6 显示了任务数量对于策略执行时间的影响。策略执行时间指的是从获得任务、服务器信息开始,计算出任务卸载结果的时间。由图6 可以看出,因为LC 卸载策略和RC 卸载策略自身策略性质,所以它们的执行时间都是0,不予考虑。OALA 策略、HOSBGA 策略和MUTOSA 策略随着任务数量的增多,两者的执行时间也随之变长。相较于HOSBGA,当任务数量较少时,MUTOSA 可以节省约60 ms 的执行时间,随着任务数量的增多,可以达到节省约100 ms 的效果。这是因为HOSBGA 算法需要从全局去搜索较优解,收敛速度较慢。MUTOSA 中任务总是选择当前条件下在最优选择,被拒绝后选择次优选择,时间复杂度是线性相关的。相较于OALA 策略,MUTOSA 可以节省约30 ms 的执行时间。在执行时间上,MUTOSA 优势明显,因此对于时延敏感应用可以有效提高用户体验。
图6 任务数量对卸载策略执行时间影响Fig.6 Effect of task number on execution time of offloading strategy
4.2.3 能耗消耗
基于稳定匹配的多用户任务卸载策略可以分为两种:一种为考虑能耗的计算卸载策略MUTOSA-C(Multi-User Task Offloading based on Stable Allocations-Considering energy consumption);一种为不考虑能耗的计算卸载策略MUTOSA-N(Multi-User Task Offloading based on Stable Allocations-Not considering energy consumption)。在能耗方面,指标为所有用户的总能耗。
图7显示了传输数据规模对总能耗的影响。由图7(a)可以看出,LC、OALA、HOSBGA、MUTOSA-N 以及MUTOSA-C 都随着传输数据的增大总能耗也随着增大。LC 策略任务只在本地运算,传输数据量的大小与其能耗无关。RC策略总能耗虽然一直处于最小的情况,但是RC策略所能达到的用户满意度比较低。因此在图7(b)去除LC与RC策略。
图7 传输数据规模与总能耗关系Fig.7 Relationship between transmission data scale and total energy consumption
从图7(b)中可以看出,策略HOSBGA 与MUTOSA-N 策略在能耗方面比较接近,OALA 比HOSBGA 和MUTOSA-N 要低一些,但是OALA 和HOSBGA 所能达到的用户满意度低于MUTOSA-N 策略。相较于前三种策略,MUTOSA-C 方法的能耗是最低的。在用户满意度方面,与MUTOSA-N 策略相同。相较于MUTOSA-N、OALA 和HOSBGA,MUTOSA-C 方法可以节省大约50%的能耗,最大限度地减少用户端设备的能源消耗。
图8 显示了任务数量对总能耗的影响。由于从图7 可以看出LC策略总能耗明显比其他几种策略能耗要高出很多,因此忽略LC 策略。此外,五种策略都随着用户任务数量增多,总能耗升高。五种策略中,RC 策略是能耗最小的,这是由于假设任务类型为计算密集型任务。但是由于RC 策略的低用户满意度,因此仅作为参考数据。OALA、HOSBGA 和MUTOSA-N 三种策略,在用户任务数量达到60 之前,两者的总能耗比较接近;当用户任务数量超过60 时,MUTOSA-N 总能耗超过HOSBGA 策略的总能耗,OALA 总能耗低于HOSBGA 和MUTOSA-N 策略。相较于前三者,MUTOSA-C 策略的总能耗一直处于最低的水平,而且增长趋势比较缓慢。这表明MUTOSA-C 策略为用户节省了大量的能耗,给用户设备长久工作提供了有利条件。
图8 任务数量与总能耗关系Fig.8 Relationship between task number and total energy consumption
图9 显示了任务数量对卸载比例的影响。L、E 和R 分别表示的是本地(Local,L)、边缘MEC 服务器(Egde,E)和远程云(Remote,R)。可以看出,E 所占比例总是最多的,这表明大多数的任务被卸载到了MEC服务器上。
图9 卸载比例与任务数量关系Fig.9 Relationship between offloading proportion and task number
HOSBGA 与MUTOSA-N 两者策略,E 所占比例比较接近,这说明两者在利用MEC 服务器方面所达到的利用率相接近。MUTOSA-C 策略相较于前两者,E 所占比例明显要多了大约10%的比例,这表明MUTOSA-C 策略更能充分地利用MEC 服务器的能力。综合来说,MUTOSA-C 策略能更大限度地利用MEC 服务器资源,并能根据任务性质选择最有利于用户的卸载节点。
上述实验结果表明,本文提出的基于稳定匹配的多用户任务卸载策略能够实现高达约95%的用户满意度,满足绝大多数的用户时延要求,并能有效地减少终端能耗,解决多用户任务卸载问题。
本文针对单个MEC 服务器计算能力有限的问题,不仅联合多个边缘MEC 服务器,还联合本地用户设备与远程云,通过对三方面任务执行过程进行建模,提出了基于稳定匹配的多用户任务卸载策略,解决多用户的计算任务卸载问题。仿真实验表明,与本地卸载策略、远程云卸载策略和启发式卸载策略相比,基于稳定匹配的多用户任务卸载策略能够实现平均约93%的用户需求,实现较高的用户满意度,而且执行时间比启发式算法大幅度减少,对于时延敏感型应用任务可以有效地提高用户体验。后续的研究将从以下方面展开。首先,在计算任务卸载决策和资源分配问题中,多个用户进行任务卸载时,对通信和计算资源都会产生竞争问题,这将是未来值得研究的工作之一。其次,用户的移动性是移动边缘计算的重要特点,这往往会导致用户和边缘服务器的网络连接不稳定,造成任务卸载失败。在实际场景中,通过挖掘用户的移动规律制定高效的卸载决策对提高任务的执行成功率具有重要意义。