面向优先级任务的移动边缘计算资源分配方法

董思岐,吴嘉慧,李海龙,屈毓锛,胡 磊

(1.火箭军工程大学 作战保障学院,西安 710025; 2.中国电子科技集团公司第二十八研究所,南京 210007)

0 概述

移动互联网的发展使得移动终端(如手机、平板电脑等)逐渐取代台式设备,成为人们日常处理信息的主要工具。目前,移动终端的通信计算量呈爆炸式增长的趋势,但由于硬件设备条件约束,其在处理大量计算业务时会导致较高的计算时延,并且加速电池的能量消耗,降低用户的体验质量(Quality of Experience,QoE)。传统方法将移动端需要进行计算的任务部署至云服务器,解决了移动设备计算资源有限导致计算时延过高的问题,但是将任务全部传输至距移动端较远的云服务器进行计算,会面临网络负荷和通信链路传输时延增加,以及通信链路带宽有限的问题。对此,研究者提出了移动边缘计算的概念[1]。移动边缘计算整合了距用户移动端较近的边缘网络中的计算资源,能够降低网络负荷和通信链路的传输时延,提高任务分发能力同时优化终端用户的使用体验。但移动边缘网络中的计算资源有限,因此需要设计合理的计算资源分配策略,以降低计算时延和能量消耗。

目前关于计算资源分配的研究,多数按照任务请求计算卸载的时间顺序为其分配计算资源,而在许多实际应用中,任务计算处理的紧迫程度或重要性具有一定区分度,仅依靠任务请求计算卸载的时间顺序对其进行资源分配是不合理的,结合实际需要划分任务的优先级并据此进行计算资源分配,能够更好地满足任务的计算需求。因此,本文提出面向优先级任务的边缘计算资源分配方法,根据任务优先级通过加权法分配相应的计算资源,在保障高优先级任务获取计算资源的同时,减少系统任务的计算时间及能量消耗。

1 相关研究

将计算任务卸载至边缘服务器进行计算,需要通过通信链路将数据传输至边缘服务器端,边缘服务器利用计算资源对任务进行计算,计算完成后再将计算结果传输至移动端。整个过程中涉及的资源主要为通信链路的通信资源及边缘服务器的计算资源。文献[2]提出了基于半定松弛和随机化映射的启发式算法,将最小化时延和能耗问题公式化为非凸约束二次规划问题。实验结果表明,该算法经过少量随机性迭代即可达到最优性能。文献[3]提出利用迭代算法查找上行链路发送的比特数量的最优值,其对文献[2]的卸载策略做了进一步的讨论,论证了信道质量好时执行计算卸载的效率更高。文献[4]通过设置存放计算业务的缓冲区,在缓冲区稳定性约束的基础上构建功耗最小化模型,并利用Lyapunov算法进行传输功率和带宽分配优化。文献[5]提出整合上行链路的传输功率与边缘计算服务器处的计算资源分配,利用凸优化算法实现计算资源分配,设计一种启发式算法解决任务卸载问题。文献[6]提出了基于效益函数模型的资源优化方法增加系统收益,并对多种研究场景进行了讨论分析。文献[7]通过对任务数据进行压缩,构建在通信资源充足而计算资源有限场景下的分段优化模型,达到减少移动端计算时延的目的。文献[8]在增强现实任务的场景下建立凸优化资源求解数学模型,研究在不同时延约束条件下节约能耗的情况。文献[9]通过对博弈算法和匈牙利算法的相互迭代解决资源分配的优化问题,从而降低了计算能耗及时延。文献[10]提出一种能耗感知的卸载方案,将电池剩余电量引入到能量消耗和时间延迟的加权因子中,通过迭代搜索算法优化通信和计算资源的分配。文献[11]构建了移动端的待处理数据具有异构性的能量消耗模型,根据任务的截止时间在调度阶段设定卸载时间间隔。文献[12]通过设计分布式计算卸载算法,对计算时延和能耗指标进行量化,达到了更低的计算时间开销。文献[13]通过二分法寻找需要进行计算卸载的移动设备的最优发射功率和匹配计算资源,提高了用户的任务卸载量,有效减少了系统开销。

由上述研究可以看出,在资源分配方面,研究者主要通过优化移动端的发射功率以及合理分配通信带宽,或结合优化边缘服务器端的计算资源来降低时延及能耗。此外,在移动边缘计算的研究场景中没有区分任务之间的优先级,默认任务之间为平等关系。文献[14]考虑了任务间的优先级关系,在云计算场景下构建符合用户优先级的适应度函数,通过引入重优化判断准则优化了粒子群算法,从而得到全局最优解。

区别于云计算场景下基于任务优先级的资源分配算法、对任务进行部分卸载计算及定义任务优先级的方式,面向移动边缘计算场景,本文提出针对边缘服务器资源的加权分配策略,以任务平均价值量作为任务优先级区分标准,将任务全部卸载到边缘服务器进行计算。

2 场景分析与系统建模

2.1 场景分析

本文策略针对的移动端(任务)与服务器多对一场景如图1所示,其中有多个移动设备终端和一台边缘计算服务器,每个设备终端处包含一个需要进行计算处理的任务。各个移动终端上待处理的任务根据其平均计算价值量划分优先级高低。由于移动终端计算能力有限,若在移动终端进行处理,可能会导致计算时间过长超出任务的处理时间限制,或本地资源不足以支持完成计算。因此,需要将待处理任务卸载至边缘计算服务器上进行计算。通过无线通信链路将任务传输至边缘计算服务器,边缘计算服务器利用自身计算资源完成计算任务后,再由无线通信链路将计算结果传回至移动设备终端。考虑到通信链路带宽及通信资源有限,边缘计算服务器的计算资源也是有限的,本文对边缘服务器端的计算资源优化分配方法进行分析,以期在存在资源和任务优先级约束的条件下降低计算时延与能量消耗。

图1 资源分配场景

2.2 系统建模

基于上述场景分析及任务计算流程,将系统建模分为以下3个部分:

1)任务平均优先级建模。首先需要对任务根据其要处理的平均价值量进行任务的优先级划分。

2)对任务在通信链路上的传输时延进行建模。传输时延为任务数据由移动端发送至边缘服务器过程中消耗的时间与边缘服务器将计算结果回传至移动端消耗的时间之和。由于边缘服务器的发射功率较大,因此在计算时间延迟时可以忽略将数据由边缘服务器回传至移动端的时间消耗,只考虑将任务数据上传至边缘服务器的时间消耗。

3)对任务在边缘服务器端的计算时间进行建模。通过对优先级不同的任务进行加权处理,分配相应的计算资源,服务器同时处理所需计算的任务,完成后即将计算结果发送回对应的移动端,取边缘服务器进行任务计算所需的最长计算时间作为计算时间。

由移动端及边缘服务器构成的系统任务处理流程如图2所示。

图2 任务处理流程

2.2.1 任务优先级加权设定

2.2.2 数据传输时间设定

Vmax=Blb(1+S/N0)

(1)

其中,S/N0为信噪比,S为信道内信号传输功率,N0为信道内噪声功率。任务Tn在通信信道中由移动设备终端传输至边缘计算服务器的传输速率可表示为:

(2)

2.2.3 边缘服务器端计算时间建模

边缘服务器端的具体参数设定如下:边缘网络中有1台服务器,用S1表示。对于S1服务器的相关参数,用集合S1={SW,SC}表示具体的参数配置及服务器状态,其中:SW表示边缘服务器的工作状态,SW=1代表服务器正忙,SW=0代表服务器处于空闲状态;SC表示边缘服务器的计算能力,即单位时间内边缘服务器可提供的计算资源量(以bit/s为单位);SP表示边缘服务器的计算功率。

3 边缘服务器计算资源分配策略

3.1 基于优先级的资源分配方式

边缘服务器的计算资源有限,需要根据任务的优先级进行计算资源分配,分配过程如图3所示。

图3 资源分配过程

(3)

由式(3)可知,λ系数影响对应优先级任务所能获取到的计算资源量,因此,λ需要体现任务的优先级指标作为资源分配的加权系数。假定λ1,λ2,…,λk之间满足以下关系:

(4)

TC=max{TC1,TC2,…,TCk}

(5)

在进行计算的整个过程中,每个任务间的计算是相互独立的,可以将计算事件视为独立离散事件,将最小化时延转化为约束条件下的单目标组合优化性质的问题,因此时间延迟的数学模型可表示为:

min{TC}

(6)

3.2 加权算法描述

本文算法将最小化时延问题转化为加权线性规划问题,首先通过分治思想将时间延迟及能量消耗问题分解为各部分建模模块消耗的时间及能耗的子问题进行求解,结合任务优先级、服务器计算能力及计算资源量的约束,通过线性规划方法为不同任务分配相应加权值的计算资源,降低处理任务计算能耗的时间延迟。

面向优先级任务的加权分配算法执行步骤如下:1)初始化时输入任务的优先级和任务数据数据量等参数;2)根据相关参数及归一化系数设定加权值;3)利用加权值将计算资源分配给各个任务进行计算。算法描述如下:

输入Tn,SC,SW

输出计算结果,计算时延,系统能耗

1)任务传输至边缘服务器端后,将其置于调度队列中,以任务优先级为关键字对任务进行排序。

2)根据任务优先级及任务的期望完成时间,以及边缘服务器的计算能力,按式(4)计算加权值。

3)检测边缘服务器的工作状态SW,若SW=1,则将任务置于调度队列中等待;若SW=0,则按加权数值进行进行资源分配并开始计算,计算完成后将计算结果回传至各任务所对应的移动端。

4)取k个任务中计算时间最大值作为计算时延。

忽略任务进行优先级排序及资源分配所需时间,由移动端与边缘服务器组成的系统完成计算所消耗的总时间t可记为:

t=ttrans+TC

(7)

设定各个移动终端的发射功率及计算功率相同,则由移动端与边缘服务器组成的系统完成计算所消耗的总能量Etotal可记为:

Etotal=Mpn×ttrans+SP×TC

(8)

4 仿真实验

利用Matlab仿真平台对本文方法作实验验证,并与以下3种方法进行对比:将任务全部置于本地移动端进行计算的方法(本地计算方法),将任务卸载至边缘服务器进行计算时平均分配计算资源的方法[18](平均分配方法),按照任务数据量大小分配计算资源的方法[19](按数据量分配方法)。对比的性能指标为计算时延和能耗:将任务置于本地移动设备端进行处理的时延为移动端的计算时延;将任务卸载至边缘服务器进行处理的时延为边缘服务器计算时延与将数据传输至服务器的上传时延之和;将任务置于本地进行处理的能耗为移动端的计算功率与计算时延之积。将任务卸载至边缘服务器进行处理时,由移动端及边缘服务器构成的整体系统的能耗为移动端的待机功率与时延之积、移动端的发射功率与数据传输时延之积、边缘服务器的计算时间与计算功率之积三部分总和。具体数据范围及参数设定如表1所示。

表1 仿真参数设定Fig.1 Simulation parameter setting

本文研究系统中移动端的任务数量范围为10个～100个时,移动端及由移动端和边缘服务器构成的系统所用的时延及能耗的数值。通过本文方法与本地计算及资源平均分配算法的对比,论证本文算法的优越性。根据经验值给出具体的仿真参数范围[8-15],实验中使用的数据值由Matlab在表1范围内生成随机数作为具体参数。给定相同的数据时,移动端与边缘服务器的计算时间如图4所示。

图4 移动端与边缘服务器的计算时间

Fig.4 Calculation time of mobile terminal and edge server

由图4可以看出,在相同的数据量下,将任务置于边缘服务器进行计算所需要的时间远低于在移动端本地进行计算消耗的时间,因此,有必要将任务卸载到边缘服务器进行计算。为进一步降低计算时延,将边缘服务器端的计算资源根据任务的优先级进行合理分配。仿真结果表明:本文算法与平均分配方法相比降低了83.76%的时间消耗,与平均分配方法相比降低了15.05%的时间消耗,与本地计算方法相比降低了99.42%的时间消耗。为便于直观观察不同方法间的性能差异,采用对数纵坐标显示消耗时间的值,4种方法所需时延如图5(a)所示,为进一步显示本文方法与按数据量分配方法的对比,将图5(a)中的虚线框部分放大表示为图5(b)。

图5 4种方法的计算时间对比

在对比计算时延的基础上,对未进行计算卸载时移动端的能量消耗情况与进行计算卸载时由移动端与边缘服务器构成的系统的能量消耗进行对比,如图6所示。仿真实验结果表明:与本地计算方法相比,本文方法能够节约87.69%的计算能耗;与平均分配方法相比,本文方法能够节约84.87%的能量消耗,与按任务数据量分配方法相比,本文方法能够降低17.37%的能量消耗。

图6 4种方法的能耗对比

Fig.6 Comparison of energy consumption of four methods

5 结束语

为解决移动端进行任务计算时时延及能耗高,以及目前研究中利用边缘计算技术处理任务时较少考虑任务优先级的问题,本文提出一种资源加权分配方法,将有限的计算资源在约束条件下合理分配给具有不同优先级的任务。实验结果表明,该方法可以有效降低计算时延与系统能耗。为便于计算,本文设定数据在同一时刻对边缘服务器进行计算卸载请求,数据传输过程中速率恒定,未计算数据的回传时间。下一步将结合实际情况设定任务在不同时刻动态向边缘服务器进行计算卸载请求,同时在数据传输过程中加入干扰因子使传输速率更符合实际传输情景。