MEC联合资源分配与计算卸载的效益

杨锦霞，郭荣佐，陈芳莹

(四川师范大学 计算机科学学院，四川 成都 610101)

0 引 言

移动边缘计算(mobile edge computing，MEC)作为5G通信的主要应用之一，在更靠近数据源的网络边缘为物联网设备提供低延迟计算和通信服务，能够有效缓解物联网终端设备自身能力不足的问题[1,2]。在5G环境下，MEC的任务处理时延占整个卸载时延的最大比例[3]。合理分配有限的计算资源对卸载性能有着至关重要的影响。因此，研究MEC构成的物联网的资源分配与计算卸载的系统效益问题，对提高物联网边缘计算的服务质量(quality of service，QoS)是十分必要的。

针对计算资源分配问题Zhang等[4]提出了一个高效的移动边缘云计算网络框架，通过最优定价和云计算资源管理实现MEC和云的利润最大化。该文联合移动云计算有效缓解计算资源不足的问题，但是没有考虑用户卸载效益。Ning等[5]分别研究了单用户和多用户场景下的计算资源分配问题，设计了一种迭代启发式MEC资源分配算法，以动态地做出卸载决策。针对计算卸载与资源分配联合优化问题Wang等[6]提出了一个多层数据流处理系统，将任务分配到多个层次处理。Kiran等[7]构建了一种新的MEC软件定义边缘云框架，提出了基于强化学习算法的方案来解决计算卸载与资源分配问题。

综上所述，这些研究都是非常有意义的，为进一步研究物联网边缘计算的计算卸载决策与计算资源分配的联合优化奠定了坚实基础。首先构建了系统卸载效益模型，提出了保证效益为正的最小计算资源分配阈值，将问题转化为带约束的系统卸载效益最大化问题，并利用罚函数解决约束问题。其次引入了遗传算法优化(genetic algorithm optimization，GAO)，为了适应问题设计了一种两段式染色体结构和遗传算子。最后进行仿真实验，对比分析了随机卸载决策和平均计算资源分配、全部卸载决策和随机计算资源分配等4种策略，GAO无论是在时延还是能耗均优于其它方案。同时还分析得出算法在传输功率、设备数量等重要参数下均具有较好的灵敏性。

1 系统模型

1.1 系统概述

如图1所示，考虑一个资源受限的小型移动边缘计算卸载系统，该系统有多个移动智能设备(smart mobile device，SMD)和一个MEC服务器(mobile edge computing server，MECS)。MECS部署在微蜂窝基站上，基站与MECS通过高带宽有线直接相连，为用户提供计算服务[8]。设备通过无线的方式与基站进行交互，只有在可以建立无线连接的情况下，移动设备才能访问服务器。假设在任意时隙，SMD都有一个计算密集型任务待处理，且任务都具备可分割性，可以部分在本地处理，部分在MECS上处理。MEC服务器可以动态地分配其计算资源来执行从不同的SMD卸载的任务。同时考虑一个准静态信道模型，即信道的状态在各个卸载阶段保持不变，且一旦开始卸载，用户将无法停止直到整个卸载完成[9]。

为了方便分析，设系统有K个移动智能设备，K=[1,2,…,k]， 每个用户的SMD用一个二元组Dk={fk,Pk} 来描述。其中fk， cycles/s表示SMDk的计算能力，Pk表示卸载任务时的传输功率；类似的，每个任务用一个三元组τk={dk,ck,ok} 来刻画。其中dk， bits表示SMDk的任务数据总量，ck表示计算任务1 bit数据需要花费的CPU周期个数，ok∈[0,1] 表任务卸载比例。任务执行的时延由本地计算时延、传输时延以及MECS端计算时延3部分组成。由于MECS有持续不断的供电电源，因此不考虑服务器端的能耗，则能耗仅包含本地执行能耗和数据卸载的传输能耗两部分。

图1 多用户MEC系统

1.2 通信模型

计算卸载过程可以简单描述为：SMD将输入数据由上行链路传输到MECS，MECS执行计算，计算完成后再将计算结果由下行链路传回到SMD上。计算卸载过程产生额外的传输时延和能耗是影响用户QoS的重要因素，而传输时延和传输能耗受数据传输速率的影响。

设移动运营商提供的总带宽为B， MHz，系统的上行链路采用正交频分多址(orthogonal frequency division multiple access，OFDMA)技术，总通信频带均分为K个带宽为B/K， MHz的正交子频带。为减少传输的信道干扰，每个用户在卸载周期内分别占用不同的子频带。根据香农公式可得出任务卸载到服务器的传输速率为

(1)

其中，Bk=B/K，Pk为传输功率，Gk为SMDk与基站之间上行链路的信道增益，σ2为背景噪声功率。传输时延=传输的数据总量/传输速度，根据式(1)可得上行链路的传输时延为

(2)

传输过程中设备能量消耗=传输时间*传输功率，因此根据式(2)的传输时间可得上行链路任务的传输能耗为

(3)

其中，Ln是尾部能量，在数据传输完成之后会继续保持信道状态一段时间，这种尾能量现象在移动蜂窝网络中普遍存在[10]。

1.3 本地计算模型

任务在本地执行产生的时延可以表示为

(4)

CPU每周期能量消耗模型E=∂f2， ∂是与CPU芯片结构相关的能量消耗系数，f， cycles/s是CPU计算频率[11]。则任务在本地执行消耗的能量可以表示为

(5)

1.4 MECS计算模型

(6)

由于每个用户计算的数据量以及其它参数之间的差异，MECS应该给每个任务分配不同数量的计算资源。一般来说，计算结果的大小远小于输入数据，下行链路的数据传输速率也远远大于上行链路。因此，不考虑计算结果回传的时延[14,15]。

MEC服务器由某个运营商操作和维护，将从提供计算卸载服务中收取一定的费用[16]。设用户租用MEC服务器计算资源的代价为线性函数cost=αx+β， 其中α≥0，β为代价函数系数，为了便于分析，令β=0。 则SMDk租用计算资源的代价costk为

costk=αfk

(7)

1.5 卸载实体

卸载产生的总时延Tk为本地执行时延、传输时延和MEC服务器计算时延之和

(8)

由式(2)、式(4)、式(6)可得SMDk的整体时延开销为

(9)

SMDk的总能耗为本地执行能耗和传输能耗之和

(10)

由式(3)、式(5)可得SMDk的整体能耗为

(11)

计算卸载的目的是增强设备的计算能力从而满足用户的时延、能耗需求，此外卸载的费用也影响着用户的QoS。因此将卸载问题转化为联合卸载时延效益、能耗效益以及费用的卸载效益最大化问题。设SMDk的时延效益TRk为

(12)

类似的，能耗效益ERk为

(13)

Uk=ωtTRk+ωeERk+ωccostk

(14)

考虑到效益建模的灵活性，式中ωt、ωe、ωc分别表示时延效益、能耗效益及费用的权重。通过设置权重可分别捕捉用户在这3方面的偏好，以满足用户不同的需求。

1.6 问题制定

(15)

(16)

C2表示每个用户总卸载时延应该小于完全本地计算的时延，以保证用户卸载的有效性，避免计算资源的浪费。由C2可进行如下推导

2 基于改进遗传算法的问题求解

问题P1是一个混合整数非线性(mixed integer nonli-near programming，MINLP)问题，难以用低复杂度算法求得全局最优解。因此，为了便于实验实现，本文引入改进的低复杂度遗传算法对问题求解。遗传算法是一种模仿生物进化论的启发式算法，能很好的在有效性和复杂度之间取得平衡，为NP难问题求得近似最优解。每条染色体对应问题的一个可能解，为了简化编码和解码过程，采用实数编码的方法初始化每条染色体。如图2所示，设计一个两段式的染色体，即每条染色体由两组长度均为K的基因序列OD和RA构成，分别对应K个设备的卸载决策和计算资源分配结果。

图2 染色体结构

遗传算法的一般过程为初始化、个体适应度评估、选择、交叉、变异。下面将描述利用改进的遗传算法求解卸载效益最大化问题的主要过程。

(1)初始化

(2)个体评估

初始化种群后，通过P1对每个个体进行评估。由于该问题含约束条件，可能存在违反约束条件的个体，称这些个体为不可行解。为了解决约束限制，采用了罚函数求解约束优化问题的思想：可行解优于不可行解，对不可行解进行惩罚，为可行域提供搜索方向。定义如下罚函数

CV=CV1+CV2

(17)

(18)

(19)

CV1和CV2分别解决不等式约束C2、C3。适应度值越大，个体越优秀，则对于任意个体cn适应度函数为

fit(cn)=U(cn)-λCV

(20)

λ为惩罚因子。

(3)选择

采用轮盘赌选择方法，该方法根据适应度值大小对个体进行选择，适应度值较大的优秀个体，被选择的概率也更大，从而保证优秀个体能保留下来。首先根据式(20)计算出每个个体的适应度值，再根据适应度值计算每个个体的累积概率pn，pn对应轮盘跨度，跨度越大，个体被选中的概率越大。pn的计算公式为

(21)

产生一个[0,1]之间的随机数r，保留pn>r的第一个个体n。

(4)交叉

(22)

其中，β满足以下的概率密度函数

(23)

式中：随机数μ∈[0,1]，ηc为交叉分布指数。

图3 交叉操作

(5)变异

这一步采用多项式变异算子来产生子代。首先产生一个[0,1]之间的随机数pm， 若pm

(24)

式中：随机数v∈[0,1]，ηm为变异分布指数，对于基因序列OD来说xmax，xmin分别为卸载决策的最大值和最小值，对于基因序列RA来说xmax，xmin则分别为资源分配的最大值和最小值。

图4 变异操作

算法求解的具体过程见表1。

表1 基于改进的GA算法的问题求解

3 实验仿真与结果分析

3.1 实验设置

本节将通过Matlab R2017a仿真，参照已有文献的参数设置模拟MEC系统，分析所提算法的性能。设定服务器的计算能力F=50 GHz，总带宽B=20 MHz，移动设备的个数N=20，设备输入数据量dk为 [500,1000] kbi的随机值，每bit数据的计算强度ck取值范围为[500,100] cycles/bit。设备的计算能力fk为[0.5,2.0] GHz的随机值，传输功率P=100 mW。设备与基站之间的信道增益Gk服从范围[-50,30] dBm的随机分布，噪声功率谱密度-174 dBm/Hz。

3.2 权重设置分析

系统效益由时延效益、能耗效益和费用3部分构成，这3部分的量级各不相同，为了更好了解模型的各个组成部分对系统效益做出的贡献，分析不同权重设置下的系统总效益。设置4种不同的权重：

编号1：ωt=1，ωe=1，ωc=1；

编号2：ωt=10，ωe=1，ωc=1；

编号3：ωt=1，ωe=10，ωc=1；

编号4：ωt=1，ωe=1，ωc=10。

编号1为基准，编号2、编号3、编号4分别测试时延效益、能耗效益以及费用对效益的贡献，由图5可知，能耗的贡献最大，时延次之，费用的变化最小。因此在分析不同参数对系统效益的影响时，需要选择合适的权重设置。

图5 不同权重设置下的系统总效益

3.3 算法收敛性能分析

图6显示出了种群规模大小对算法收敛速度的影响。随着迭代次数的增加，不同的种群规模几乎都能收敛到同一最优值。此外，种群规模越大，收敛所需的迭代次数越少。当个体为50时需要100次左右迭代才收敛，而个体数为100时收敛所需的迭代次数减少到75左右。当个体数量为150和200时，收敛只需要50左右的迭代次数。因此，个体数设为100。

图6 系统效益随迭代次数的变化

3.4 计算资源分配策略对效益的影响

计算资源分配主要影响卸载时延，在该分析中设定时延效益为主要因素，选择编号2的权重设置，令ωt=10。如图7可知，计算资源分配对系统效益的影响十分明显，GAO、随机分配和均分3种资源分配策略均能收敛，但是GAO策略下的系统效益明显高于其它两种方案。这是由于各个设备的性能以及任务的复杂程度等各有差异，GAO能根据这些差异每次进化都保留优秀的个体，从而得到最佳的计算资源分配结果。

图7 计算资源分配策略对效益的影响

3.5 设备数量对系统效益的影响

图8显示了不同策略下设备数量对系统平均效益的影响。可见随着设备数量的增多，系统平均效益减少，原因是边缘服务器的计算资源是有限的，设备数量增多导致分配到的计算资源减少，MEC服务器端的处理时延增大，在本地执行的数据量增多从而时延效益减少。GAO较其它4种方案减少的较为缓慢且效益值最高，能根据当前的设备和服务器的计算资源进行决策调整，做出最佳的策略。

图8 设备数量对效益的影响

3.6 MECS计算资源总量对效益的影响

由于计算资源是影响时延效益的主要因素，为了便于分析，选择编号2的权重设置，令ωt=10。从图9可以看出，在5种不同方案下，系统效益均随着计算资源的增加而增加。当F较小时系统的平均效益很低，这是因为有限的计算资源无法支持大量设备的计算密集型任务，而当F达到35左右后，效益迅速增加，这是因为这个值满足了当前设备数量下最低计算卸载资源量。对比其它4种策略，GAO方案下的系统效益值明显高于其它方案。

图9 MECS计算资源量对效益的影响

3.7 传输功率对效益的影响

传输功率影响能耗和上传时延，而任务的上传时延远小于任务在MEC服务器执行的时延，因此设定能耗效益为主要因素，选择编号3的权重设置，令ωt=10。分析图10可以得知，传输功率越大系统效益越低，原因是传输功率增大，传输能耗增大，能耗效益减少。随着功率均匀增加，总效益变化放缓，与其它参数相比，传输功率对系统总效益的影响较小。

图10 传输功率对效益的影响

4 结束语

针对物联网边缘计算的计算卸载决策与计算资源分配的联合优化卸载效益并保证卸载的有益性，本文提出了以时延效益、能耗效益以及卸载费用加权和的系统卸载效益这一概念，并将问题转化为系统效益最大化问题。引入了针对该问题改进的遗传算法，该算法不仅能在不同参数上有着很好的灵敏性，而且相对于其它卸载决策和资源分配方案能明显提高系统的平均卸载效益。本文考虑的是单个MEC服务器的情况，未来可以考虑多个MEC服务器以及联合计算资源更加丰富的云计算服务器。