边云协同计算中基于预测的资源部署与任务调度优化

苏命峰1,2 王国军3 李仁发4

1(中南大学计算机学院 长沙 410083) 2(湖南商务职业技术学院商务信息技术学院 长沙 410205) 3(广州大学计算机科学与网络工程学院 广州 510006) 4(湖南大学信息科学与工程学院 长沙 410082) (sumingfeng@csu.edu.cn)

摘 要 数据集中处理的云计算模式提供交互迅速、绿色高效的多样化应用服务面临新挑战.将云计算能力扩展到边缘设备,提出了边云协同计算框架;设计了基于任务预测的资源部署算法,在云服务中心通过二维时间序列对任务进行预测,结合分类聚合、延迟阈值判定等优化边缘服务器任务运行所需资源部署;提出了基于帕累托优化的任务调度算法,在边缘服务器分2个阶段进行帕累托渐进比较得到用户服务质量和系统服务效应2个目标曲线的相切点或任一相交点以优化任务调度.实验结果表明:结合基于任务预测的资源部署算法与基于帕累托优化的任务调度算法在提高平均用户任务命中率基础上,其用户平均服务完成时间、系统整体服务效应度、总任务延迟率在不同用户任务规模、不同Zipf分布参数α的应用场景下,均优于基于帕累托优化的任务调度算法和基于FIFO(first input first output)的基准任务调度算法.

关键词 任务调度;资源部署;任务预测;协同计算;边缘计算

云计算、物联网、车联网、智能电网等技术迅速发展,泛在化、普适化、智能化终端广泛应用,虚拟现实、增强现实、无人驾驶、远程医疗、动态内容交付等新型网络应用对网络和计算的要求越来越高,传统数据、存储、处理集中的云计算模式面临新挑战,出现了雾计算[1]、透明计算[2]、边缘计算[3]、移动边缘计算[4]等新型网络计算模式.受分布式计算启发,边云协同计算将云计算能力扩展到边缘设备,聚合云计算与边缘计算各自优势,进行网络高速传输、资源高效分发、任务快速卸载,强化云、边数据协同处理,可以有效减少数据处理延迟,提高系统可扩展性,提升系统服务效应.

和人类生活相关的数据很多具有季节等时空特征[5],在时空维度具有显性或隐性的周期性、趋势性等信息,可以对数据变化进行有效预测[6].在边云协同计算中,借助云服务中心的海量计算能力对端任务的变化趋势进行预测,将预测结果指导边缘层服务器任务运行所需资源的部署,促进资源的高效利用.在边缘层服务器考虑用户与服务供应商需求权衡多个目标优化任务调度,以提升用户服务体验,提高服务供应商整体效益.

为此,本文研究边云协同计算中使用任务预测的资源部署与任务调度优化,主要贡献有3个方面:

1) 提出一种基于任务预测的资源部署算法,在云服务中心从横向和纵向2个时间维度对任务进行综合预测,优化部署边缘服务器的任务运行所需资源,提高平均用户任务命中率;

2) 提出一种基于帕累托优化的任务调度算法,面向用户和服务供应商,在边缘服务器对用户服务质量和系统服务效应这2个目标进行帕累托改进,以优化任务调度;

3) 提出一种边云协同计算框架,搭建实验环境,考虑不同的用户规模和Zipf分布参数α影响,从用户平均服务完成时间、系统整体服务效应度、总任务延迟率等评估分析任务调度算法.

1 相关工作

“互联网+”“智能+”技术快速发展,以网络为媒介,衍生多态网络应用.面对动态、多样、大量的用户服务请求,传统云计算利用虚拟化技术聚集高性能硬件设备,提供集中式的数据计算处理,依托互联网络实现任务按需共享[7].为了提升用户服务质量,云计算需要减少任务完成时间.文献[8]在分布式集群中使用强化学习和神经网络根据特定工作负载设计调度算法,高效调度数据处理作业以最小化平均作业完成时间.文献[9]基于工作预测提出结合数据放置与计算优化的调度方法,减少跨机架的数据传输以降低工作完成时间.文献[10]预测集群中心的尾延迟(stragglers),借助副本机制,考虑数据位置、任务执行时间、任务相互依赖关系在集中和分散式调度中减少任务延迟.文献[11-13]测度云与客户端之间的网络通信,通过提前部署虚拟机映像、预先启动配置实例、将应用程序分解为若干轻量级小粒度服务、增加冗余备份等为用户提供低延迟服务.

为了提升系统服务效应,云计算需要提高资源利用率,降低系统成本.文献[14]在公共IaaS(infra-structure as a service)平台提出一种新的群集调度程序Stratus,动态分配虚拟机实例以提高资源利用率和降低成本.文献[15]在移动云计算中提出一种基于改进遗传算法的任务联合执行策略,减少系统整体能耗.文献[16-17]设计一种服务质量感知任务管理方法和轻量级云管理方法,利用深度强化学习减少共享资源争用防止交互任务调度,在保证服务质量(quality of service, QoS)的同时降低数据中心能耗.文献[18]提出一个基于开放计算语言的异构系统优化框架,利用GPU和FPGA(field programmable gate array)加速器在保障数据中心总体吞吐量的情况下提高能耗均衡性.

数据集中处理的云计算模式提供交互迅速、绿色高效的多样化应用服务面临新挑战.边缘计算将任务部分或全部卸载到边缘计算服务器,将计算能力延伸到边缘层[19-20],可减少数据处理延迟.文献[21]考虑计算和通信提出一种多cloudlet服务器环境下最小化服务延迟的方法,将用户无法运行的任务卸载到网络边缘cloudlet服务器,通过虚拟机迁移、传输功率控制来降低任务的处理延迟和传输延迟.文献[22]提出一种兼顾移动执行CPU周期频率和卸载发射功率的Lyapunov在线算法,考虑移动边缘计算的执行延迟、任务失败执行成本、移动设备电池容量,渐进优化计算密集型工作负载提升用户体验.文献[23]利用混合整数非线性规划方法优化任务派遣和资源分配,解决移动边缘计算超密集网络任务卸载,在考虑设备电池寿命前提下最大限度减少延迟.文献[24]提出一个在线拍卖的激励机制,将边缘用户任务卸载到相邻移动设备以满足低延迟需求.

为提升用户服务质量与系统服务效应,边缘计算需要考虑任务卸载、网络负载、资源分配、传输延迟等[25-27].文献[28]提出一种单变量搜索技术的局部最优算法,在计算卸载中引入动态电压缩放技术,利用变量替换技术寻求最小化移动能耗和应用程序执行延迟的最优解.文献[29]提出一个移动设备到多个边缘设备的任务卸载框架,考虑固定和弹性2种移动设备CPU频率基于半定松弛逼近方法改善任务执行延迟和设备能量消耗.文献[30]提出一种能量感知的计算卸载方案,在能量和延迟受限情况下优化通信资源和计算资源分配,通过迭代搜索算法寻找计算卸载与资源分配的混合非线性整数最优解.文献[31]提出一个联合接入点(access point, AP)能量传输消耗、CPU处理频率、用户卸载文件大小、用户时间分配的最优资源分配方案,考虑计算和无线功率传输取得用户个体计算延迟约束下的最小化AP总能耗.文献[32]在用户设备资源受限的移动边缘计算环境下基于代码分区卸载提出一种分散卸载策略,优化任务的执行位置、CPU频率、传输功率,最小化应用程序执行时间和能耗开销.

由此,将云计算能力扩展到边缘设备提出边云协同计算框架,面向用户和服务供应商研究边云协同计算环境下基于任务预测的资源部署与任务调度优化,提升用户服务质量和系统服务效应.

2 边云协同计算框架与建模

2.1 边云协同计算框架

边云协同计算框架分为云服务层、边缘服务层和端用户层,通过Internet互联互通,如图1所示.边云协同计算可在内容分发网络、工业互联网、智能家庭、智慧交通等场景应用.云服务层包括云服务中心,由若干同构或异构的计算、存储、网络等硬件组成.云服务中心利用虚拟化、软件定义网络、冗余等技术提供高性能、高可靠、可扩展的资源,以支撑用户多样按需服务.云服务层与边缘服务层之间产生控制流(control flow, CF).云服务中心对任务请求进行预测,根据预测结果提前将任务运行所需资源(包括运行任务所需软件及软件依赖,简称任务资源)通过CF推送到边缘服务器.云服务中心实时监测边缘服务器的任务处理和资源使用,并将各边缘服务器的任务处理和资源使用情况汇总,通过CF下发给边缘服务器.

Fig.1 Edge cloud collaborative computing framework
图1 边云协同计算框架

边缘服务层由多个资源受限的边缘服务器组成,向用户提供实时、快速、多样、灵活的网络应用.边缘服务器根据当前资源使用情况,依据调度策略将用户任务决定在本地边缘服务器单独执行,或者将任务细分调度到其他边缘服务器和(或)云服务中心协同执行.在边—边、边—云之间执行任务产生数据流(data flow, DF).边缘服务器通过CF从云服务中心接收并加载任务资源,预先启动任务运行所需环境.边缘服务器将任务处理情况和计算、存储、网络等资源使用情况通过CF上传到云服务中心.边缘服务器之间不相互传递CF,以减少边缘服务器的处理开销和带宽占用.

端用户层由用户拥有的移动设备、计算机、网联汽车、智能家电、智能终端等组成,具有一定算力,可以将任务进行预处理或部分前置处理,向边缘服务器发送任务请求(request data, RD).请求任务在本地边缘服务器单独执行,或者在其他边缘服务器和(或)云服务中心协同执行后,任务执行结果(answer data, AD)将从本地边缘服务器、其他边缘服务器、云服务中心返回至用户端.

Table 1 Meaning of the Main Symbols
表1 主要符号及其含义

符号含义U用户集J任务集E边缘服务器集C云服务中心fje二进制数,1∕0表示边缘服务器e是∕否有任务j资源lju用户u的任务j数据量kju二进制数,1∕0表示用户u是∕否有任务j请求D节点距离系数d(x,y)x,y节点间距离度μ任务执行偏好权重系数p收益指数t任务执行时间当量s服务平均能耗系数

2.2 边云协同计算建模

定义1. 边云协同计算模型.边云协同计算模型(edge cloud collaborative computing model, MEC3)为一个六元组模型MEC3=(U,J,E,C,O,Γ).U为用户集,由n(u)个独立的用户组成,U={u0,u1,…,un(u)-1},用户之间互不干扰,用户提交的各类任务存在时间序列相关性,可以对任务的类型数量进行预测.J为任务集,由n(j)个任务组成,J={j0,j1,…,jn(j)-1},一个用户可以提交不同任务,任务分为时间敏感型和非时间敏感型2类,每类任务包括多种不同任务以满足多样用户需求,任务可以细分为若干子任务.E为边缘服务器集,由n(e)个地理位置分散的边缘服务器组成,E={e0,e1,…,en(e)-1},边缘服务器的计算、存储、网络等硬件资源有限,拥有部分任务资源,能将任务细分并根据决策将任务在本地执行或派遣至远端执行.C为云服务中心,拥有大量的计算、存储、网络等硬件资源,拥有全部任务资源.云服务中心对边缘服务器进行管理和监控,对用户任务进行有效预测,以推送合适任务资源至相关边缘服务器.O为边云协同计算的优化目标,具体由用户服务质量(quality of user service, QUS)和系统服务效用(effect of system service, ESS)综合量化,记为QusEssO={max(Qus),max(Ess)}是资源部署与任务调度优化算法.

定义2. 用户服务质量.QUS主要关注用户在边云协同计算环境中的服务体验与质量.一般来说,用户任务在接收任务的边缘服务器本地执行,用户任务请求的响应时间越小,用户服务质量越高.用户服务质量系数为

(1)

用户服务质量系数与任务数据量和任务执行情况相关.任务数据量具体量化为任务的执行时间.分别表示任务j在接收边缘服务器本地执行、由接收边缘服务器派遣至其他边缘服务器执行、由接收边缘服务器派遣至云服务中心执行的任务占比,其对应的任务执行偏好权重系数为存在节点距离系数考虑任务的发送与接收,与节点间的距离度相关.为任务在接收边缘服务器本地执行的节点距离系数,其值为任务由本地边缘服务器派遣至其他边缘服务器执行的节点距离系数,其值为任务由本地边缘服务器派遣至云服务中心执行的节点距离系数,其值距离度d(x,y)与xy节点之间链路的最小带宽、累积延迟、可靠性相关,其值等于累积延迟除以可靠性与最小带宽之积.节点之间链路的最小带宽越大,累积延迟越小,可靠性越高,其距离度值越小.用户服务质量的目标函数为



(2)

式(2)中,表示用户u有任务j的请求.表示边缘服务器e拥有任务j运行所需资源.为任务由用户递交到云服务中心执行的节点距离系数,其值为非偏好权重系数,μ0=-μe,为负值.从式(2)看出,边缘服务器拥有任务j运行所需资源且在其本地执行的任务占比越大,Qus值越大,边云协同计算的用户服务质量越高.

定义3. 系统服务效应.ESS主要关注服务供应商在边云协同计算中的系统服务收益与系统服务消耗.系统服务收益系数为

(3)

系统服务收益系数与任务数据量和任务收益情况相关.为任务在本地边缘服务器执行的收益指数,为边缘服务器将接收的任务派遣至邻居边缘服务器执行的收益指数,为边缘服务器将接收的任务派遣至云服务中心执行的收益指数.系统服务效用的目标函数为

(4)

在式(4)中,统计周期内的系统服务消耗为任务执行时间当量t与服务平均能耗系数s的乘积.tCte分别表示云服务中心、边缘服务器的任务执行时间当量,sCse分别表示云服务中心、边缘服务器的服务平均能耗系数.能耗系数取决于硬(软)件成本和系统运维成本.前者包括硬(软)件采购成本、折旧损耗成本;后者包括设备电能消耗、空调制冷能耗、管理服务成本.从单量比较分析,sC>se.系统服务收益越高,系统服务消耗越低,则Ess值越大,边云协同计算的系统服务效应越高.

在边云协同计算模型中,用户服务质量与系统服务效应的目标优化涉及资源部署与任务调度.需要对用户任务的类型与数量进行预测,合理推送任务资源至边缘服务器,高效利用边缘服务器的计算、存储、网络等资源;需要优化任务调度,通过本地边缘服务器、其他边缘服务器和云服务中心的任务协同处理,提升用户服务质量,提高系统服务效用.

3 任务预测

对用户任务进行长期监测,从局部看用户任务变化是一个动态随机过程,可以显性或隐性看到一种变化趋势,其任务变化和时间具有很强的关联性;从全局看用户任务与年、月、周、日等时间周期呈现明显自相关.基于纵向和横向时间维度的任务变化规律,可以通过预测找到任务变化趋势.图2(a)为某电商平台集群服务器中部署的任务数量统计图,图2(b)为某高校数据中心外网接口的任务请求统计图.这2个图的任务数随着时间的变化而改变.观察图2(a)连续7天、图2(b)连续3天列出的任务数,发现每天的任务数值在相同时间段的变化趋势相近,总体呈现有规律的周期波动,为边云协同计算的用户任务预测提供参考依据.

Fig.2 Task request statistics
图2 任务请求统计图

根据边云协同计算中用户任务为强周期性、中趋势性和弱随机性的叠加变化趋势,可在云服务中心对用户任务从横向和纵向2个维度进行综合预测,统计分析过去基于时间序列的数据,推测任务的发展变化.预测模型为

L(t)=δx(t)+(1-δ)z(t)+ε(t),

(5)

L(t)为下一个时间序列的任务预测结果;x(t)为横向维度的当前时间序列值,为趋势预测部分;z(t)为纵向维度的当前时间序列值,为周期性统计部分,具体为不同周期的同一时间序列均值;ε(t)为随机噪声;δ为二维时间序列调整因子,取值介于0~1之间.

定理1. 边云协同计算模型基于横向维度的趋势预测任务为

证明. 对实践数据统计分析,从局部看任务数为线性增长或减少趋势,可用线性方程表示任务数变化,表示为

x(t)=∂t+b.

(6)

由此可以得到时间t-n的任务数为

x(t-n)=∂(t-n)+b.

(7)

根据移动平均预测,其时间t的任务数与之前n个时间槽的任务数相关,表示为

(8)

结合式(7),将进行运算得到:





t-∂(n+1)/2+b=∂t+b-∂(n+1)/2.

(9)

根据式(6),将时间t的任务数x(t)=∂t+b代入式(9),得到:

(10)

通过移动平均预测的任务数与实际任务数x(t)存在一个值为∂(n+1)/2的延时偏差,需要进行修正.由此得到基于横向维度的趋势预测任务为

其中∂值可用线性回归公式计算得出,需要指出的是,在统计区间如果任务数处于绝对平稳状态,其∂=0.

证毕.

由此得到基于二维时间序列的任务预测:

L(t)=

(1-δ)z(t)+ε(t).

(11)

4 资源部署与任务调度

边云协同计算的资源部署与任务调度优化,首先需要在云服务中心根据任务预测结果将任务资源推送至合适的边缘服务器,提高用户任务在边缘服务器的本地执行率.其次需要在边缘服务器通过帕累托优化任务调度,提高用户服务质量,提升系统服务效应.

4.1 基于任务预测的资源部署算法

在边云协同计算环境中边缘服务器的硬件资源有限,承载的任务亦有限.云服务中心通过实时监测边缘服务层的任务处理情况,运用基于二维时间序列的任务预测得到任务类型与数量变化趋势,将任务资源推送到边缘服务器.任务运行需要占用硬件资源,本文主要考虑计算资源(computing resource)和存储资源(storage resource)[33],记为vw.边缘服务器e的最大可用资源为边缘服务器e的当前可用资源为任务j的资源消耗为gj={vj+wj}.考虑到边缘服务器承载的任务有限,云服务中心需要将预测任务进行分类聚合,控制推送至边缘服务器的任务资源数,使得边缘服务器的任务负载在合理范围.基于任务预测的资源部署算法(resource deployment algorithm based on task prediction, RDTP)为:

算法1.基于任务预测的资源部署算法RDTP.

输入:边缘服务器集E、任务集J、边缘服务器最大可用资源集A、边缘服务器当前可用资源集K

输出:边缘服务器任务资源部署集X.

① 任务jJ分类;

② for eE do

ae计算最大可用资源、当前可用资源*/

④ 应用式(11)预测任务;

⑤ 任务的分类聚合、降序排列(频次);

⑥ for jJ do

⑦ if时间敏感型任务且在边缘服务器运行

⑧ if

/*延迟阈值判定*/

/*计算当前可用资源*/

⑩ 更新

end if

end if

end for

if

for jJ do

if非时间敏感型任务且在边缘服务器运行

if

/*延迟阈值判定*/

/*计算当前可用资源*/

更新

end if

end if

end for

end if

end for

return X.

在云服务中心进行基于任务预测的资源部署.行①将所有任务分类,分为时间敏感型和非时间敏感型2类.行②③根据监测数据,计算每个边缘服务器的当前可用资源和最大可用资源,包括计算资源和存储资源.行④应用式(11)基于二维时间序列进行任务预测.行⑤根据预测结果对每个边缘服务器的任务分类聚合,并根据出现频次降序排列,减少任务资源的推送数量,降低边缘服务器的资源占用,提升资源紧张情况下的用户任务命中率.行⑥~根据任务分类聚合结果,优先考虑时间敏感型任务资源部署,在边缘服务器有富余可用资源情况下,再考虑非时间敏感型任务所需资源,有利于保障用户服务质量.得到每个边缘服务器部署的任务资源后,更新每个边缘服务器的当前可用资源.为减少任务延迟,进行延迟阈值判定,确保边缘服务器包括计算资源和存储资源的可用资源占比高于任务延迟发生阈值ζ,控制推送至边缘服务器的任务资源数.返回边缘服务器任务资源部署集X,云服务中心将任务资源推送到边缘服务器.基于任务预测的资源部署算法时间复杂度为O(n(En(J)(lb n(J)+1)).

4.2 基于帕累托优化的任务调度算法

边云协同计算环境下的任务调度需要面向用户和服务供应商,综合考虑用户服务质量和系统服务效用2个目标优化.任务调度的单一目标最优不能确保另一目标亦为最优,需要权衡2个目标进行综合优化.为此,引入经济学领域的帕累托优化,通过寻求用户服务质量和系统服务效应这2个目标的帕累托改进,得到边云协同计算的任务调度方案.基于帕累托优化的任务调度算法(task scheduling algorithm based on Pareto improvement, TSPI)为:

算法2. 基于帕累托优化的任务调度算法TSPI.

输入:任务集J,边缘服务器集E,云服务中心C,任务执行偏好权重系数收益指数服务平均能耗系数sCse

输出:任务调度方案集Y.

① if收到新任务j

② 将新任务j加入任务集J

③ end if

④ if任务集J非空

⑤ 任务jJ升序排列(数据量);

⑥ end if

⑦ for jJ do

⑧ for EC do

⑩ 运用式(2)计算Qus

/*第1阶段任务调度方案求解*/

end if

end for

for EC do

运用式(4)计算Ess

/*第2阶段任务调度方案求解*/

end if

end for

Y帕累托优化2个阶段任务调度方案*/

end for

return Y.

在边缘服务器进行基于帕累托优化的任务调度.行①~⑥接收新任务,将其加入到任务集,如果同时有多个用户发起任务请求,将任务按数据量大小升序排列.行⑦~分2个阶段进行任务调度的帕累托优化.行⑧~为第1阶段用户服务质量目标优化,基于随机贪心近似算法分别求解第1阶段m组任务调度方案,运用式(2)分别计算每组的用户服务质量Qus值,从中选择每组中Qus值最大的调度方案,这些方案集可以得到用户服务质量目标曲线.为第2阶段系统服务效应目标优化,基于随机贪心近似算法求解第2阶段m组任务调度方案,通过运用式(4)分别计算每组的系统服务效应Ess值,从中选择每组中Ess值最大的调度方案,这些方案集可以得到系统服务效用目标曲线.将2个阶段得到的任务调度方案进行帕累托渐进比较,选取用户服务质量目标曲线和系统服务效用目标曲线对应的相切点或任一相交点,前者为2个目标唯一最优方案,后者为2个目标任一共优方案,从而得到每个任务的最优调度方案.返回任务调度方案集Y.算法中2个阶段的m组任务调度方案取值应适宜.值过小会导致2个阶段的解集较单一,可能出现无用户服务质量目标曲线与系统服务效用目标曲线相交或相切的情况;值过大会增加任务调度本身的计算开销.基于帕累托优化的任务调度算法时间复杂度为O(n(J)×(lb n(J)+(n(E)+1)×m)).

5 实验及结果分析

本节搭建边云协同计算实验环境,设置实验参数,确定评价指标,对基于任务预测的资源部署算法和基于帕累托优化的任务调度算法进行综合评价.

5.1 实验环境与参数

边云协同计算实验的硬件平台为一台拥有Intel E5-2620V4 CPU,64 GB ECC RAM,3×2 TB STA的x86服务器.软件平台依托CentOS 8.0 x86_64操作系统,采用Python 3.8搭建边云协同计算仿真环境.采用OriginPro 2017软件进行数据分析处理与后期绘图.本实验环境的参数如表2所示.在边云协同计算环境中借鉴阿里云公布的数据集[33-34],设置用户任务的类型、执行时间、CPU资源占用、RAM资源占用.用户任务具有随机无后效性,总体呈现Zipf分布[35],其任务出现的频率与任务热度排名成反比关系,实验中Zipf分布的参数α值缺省为1.0.云服务中心拥有的最大可用资源为10K PE CPU,10 TB RAM,10 PB硬盘.边缘服务器的硬件资源参数如表3所示:

Table 2 Experimental Environment Parameters
表2 实验环境参数

参数值任务类型数600边缘服务器数20μeu,μee,μCe0.5,0.3,0.2peu,pee,pCe0.4,0.4,0.2ζ0.2

Table 3 Hardware Resource Parameters of Edge Servers
表3 边缘服务器硬件资源参数

边缘服务器IDCPU∕PERAM∕GB硬盘∕GBe0~e32~44~8500e4~e74~64~8500e8~e114~68~161000e12~e154~88~161000e16~e194~1616~321000

5.2 实验结果分析

5.2.1 任务预测与资源部署

Fig.3 Prediction of user tasks
图3 用户任务预测

在边云协同计算环境中评估分析基于任务预测的资源部署.以日作为统计周期,每个周期分为24个时间段,每个时间段为1 h.在实验中,云服务中心基于二维时间序列对边缘服务器的任务进行预测,时间槽n=10,根据前期任务预测实验数据,设置二维时间序列调整因子δ=0.78,并忽略随机噪声.将预测结果与边缘服务器实际处理的任务数进行比较分析,如图3所示.边云协同计算环境中用户任务的实际值变化较大,任务的预测值变化相对较平缓.总体看基于二维时间序列的任务预测接近真实值,平均任务数偏差小于5%,任务预测的准确度高,其结果可以指导云服务中心优化边缘服务器的任务资源部署.

采用平均用户任务命中率(average user task hit rate, ATHR)评估基于任务预测的资源部署效果.ATHR指各边缘服务器首次接收用户任务请求,其具备任务运行所需资源并将任务本地执行的占比均值.ATHR高,说明云服务中心基于预测结果推送任务资源的准确率高.在边缘服务器本地执行任务的比率高,有利于提高用户服务质量,提升系统服务效应.在边云协同计算环境中,云服务中心通过基于二维时间序列对用户任务有效预测,根据预测结果分类聚合,优化推送任务资源到各边缘服务器,提高用户任务在边缘服务器本地执行比率,减少边缘服务器因无任务运行所需资源而被动向云服务中心申请任务资源.通过连续15天的实验,实验结果如图4所示,其中横轴di表示第i天,i=1,2,…,15.图4通过基于二维时间序列任务预测部署边缘服务器所需任务资源,边缘服务器的平均用户任务命中率有了很大提高,ATHR达到82.51%~90.92%,远高于无任务预测资源部署不到50%的平均用户任务命中率.

Fig.4 Average user task hit rate of edge servers
图4 边缘服务器平均用户任务命中率

5.2.2 任务调度

在边云协同计算环境中,从用户平均服务完成时间、系统整体服务效应度、总任务延迟率,对基于帕累托优化的任务调度算法TSPI、结合基于任务预测的资源部署算法与基于帕累托优化的任务调度算法(resource deployment algorithm based on task prediction-task scheduling algorithm based on Pareto improvement, RDTP-TSPI)、基于FIFO的基准任务调度算法(benchmark task scheduling algorithm based on FIFO, BA)[36]进行任务调度的性能评估分析.根据任务调度实验数据,将TSPI算法2个阶段的m组任务调度方案值设置为7,可得到用户服务质量和系统服务效用这2个目标的唯一或共优方案,且不过多增加任务调度本身的计算开销.

1) 评估用户平均服务完成时间(average service completion time of users, ASCT).ASCT为统计时间段内所有用户任务的完成时间总和与用户任务数之比.ASCT主要考虑用户的服务体验,其值越小,说明任务平均完成时间越短,用户的服务质量越高.在边云协同计算环境中,用户任务为缺省参数α的Zipf分布,通过改变任务规模比较分析TSPI,RDTP-TSPI,BA这3种算法的ASCT,如图5所示,随着用户任务数的增加,3种算法的ASCT随之增加,呈现近似线性变化趋势.相比较BA算法,RDTP-TSPI算法和TSPI算法的ASCT均明显降低,其中TSPI算法通过对用户服务质量和系统服务效应这2个目标的帕累托改进,有效降低用户平均服务完成时间,其ASCT相比较BA算法平均总体减少38.85%.RDTP-TSPI算法预测用户任务类型数量,提高云服务中心向边缘服务器推送任务所需资源的准确度,在此基础上分2个阶段进行任务调度的帕累托优化,进一步降低用户平均服务完成时间,其ASCT相比较BA算法平均总体减少46.84%.

Fig.5 Average service completion time of users under different tasks
图5 不同任务下用户平均服务完成时间

在用户任务固定情况下,考虑任务Zipf分布参数α的影响,进一步评测TSPI,RDTP-TSPI,BA这3种算法的ASCT.它们的用户平均服务完成时间如图6所示,在边云协同计算环境中将用户任务数设置为5 000个,随着Zipf分布参数α值的增大,用户任务越来越集中于流行度高的任务类型,3种调度算法的ASCT均有不同程度的减小.总体分析,RDTP-TSPI算法对任务类型数量进行预测,提高任务资源推送准确率,提升平均用户任务命中率,再综合用户服务质量和系统服务效用目标进行帕累托优化任务调度,其ASCT最优,相比BA算法平均总体减少40.68%.TSPI算法得益于对用户服务质量和系统服务效用的2阶段帕累托优化,在无任务预测优化资源部署的情况下,其ASCT相比BA算法平均总体减少27.13%.

Fig.6 Average service completion time of users underdifferent Zipf distribution parameters α
图6 不同Zipf分布参数α下用户平均服务完成时间

2) 评估系统整体服务效应度(overall service effectiveness of system, OSES).OSES为统计周期内云服务中心和各边缘服务器的系统服务收益与系统服务消耗之差,是归一化处理的系统服务效应.OSES主要考虑服务供应商的利益,供应商的系统服务收益越高,系统服务消耗越低,其值越大.在边云协同计算环境中,用户任务为缺省参数α的Zipf分布,通过逐渐增加用户任务数来评测TSPI,RDTP-TSPI,BA这3种算法的OSES.它们的系统整体服务效应度如图7所示.随着用户任务数的增加,3种算法的OSES随之增大,呈现近似对数增长变化.相比较BA算法,RDTP-TSPI算法和TSPI算法的OSES有明显提升,其中TSPI算法通过对用户服务质量和系统服务效用目标的帕累托改进优化任务调度,提高了云服务中心和边缘服务器的系统整体服务效应度,其OSES平均总体提升34.78%;RDTP-TSPI算法在云服务中心基于任务类型数量预测,有效推送任务资源,提升平均用户任务命中率,在边缘服务器基于用户服务质量和系统服务效用目标优化任务调度,进一步提升OSES,其OSES平均总体提高49.91%.

Fig.7 Overall service effectiveness of systemunder different tasks
图7 不同任务下系统整体服务效应度

Fig.8 Overall service effectiveness of system underdifferent Zipf distribution parameters α
图8 不同Zipf分布参数α下系统整体服务效应度

同样在用户任务一定情况下,考虑任务Zipf分布参数α的影响,进一步评测TSPI,RDTP-TSPI,BA这3种算法的系统整体服务效应度.它们的OSES变化情况如图8所示,在边云协同计算环境下用户任务数为5 000个,随着Zipf分布参数α值的增大,使得用户任务逐渐趋向流行度高的任务类型,减少边缘服务器的任务资源数,3种算法的OSES有很大提升.总体来说,RDTP-TSPI算法由于对任务类型进行预测,可以提升推送边缘服务器任务运行所需资源的准确度,提高平均用户任务命中率,再通过兼顾用户服务质量和系统服务效用的2阶段综合优化,其OSES最优,相比BA算法平均总体提升46.84%.TSPI算法在无任务预测情况下,通过对用户服务质量和系统服务效用的帕累托渐进优化,其OSES相比BA算法平均总体提高38.85%.

3) 评估总任务延迟率(total task delay rate, TTDR).TTDR为统计时间段内任务响应时间超过同类任务响应时间均值3倍的任务数占比.TTDR影响用户服务质量和系统服务效应[37].TTDR低,有利于降低用户平均服务完成时间,提升用户服务质量;有利于减少系统能耗,提高系统服务效应.在边云协同计算环境中,用户任务为缺省参数α的Zipf分布,通过逐渐增加用户任务数来评测TSPI,RDTP-TSPI,BA这3种算法的总任务延迟率.如图9所示.随着用户任务数的增加,3种算法的TTDR随之增加,总体看RDTP-TSPI算法最优、TSPI算法次之、BA算法最差.RDTP-TSPI算法对任务进行预测、分类聚合减少推送至边缘服务器的任务资源数,在资源部署时进行延迟阈值判定,考虑边缘服务器的可用资源以减少任务延迟发生概率,随着任务数量的增长,其总任务延迟率增长缓慢,TTDR控制在0.10%~4.01%之间.BA算法和TSPI算法在任务调度时都缺少任务预测,没有对可能出现任务延迟的情况进行处理,它们的TTDR偏高,随着任务的增加总任务延迟率亦呈线性增长.BA算法的TTDR最高,为8.03%~36.08%.由于TSPI算法对任务调度进行综合用户服务质量和系统服务效用目标的帕累托优化,能减少任务平均服务完成时间,其TTDR较低,为3.01%~33.02%.

Fig.9 Total task delay rate under different tasks
图9 不同任务下总任务延迟率

同样在用户任务不变情况下,考虑任务Zipf分布参数α的影响,进一步评测TSPI,RDTP-TSPI,BA这3种算法的总任务延迟率.在边云协同计算环境下将用户任务数设置为5 000个,它们的总任务延迟率变化情况如图10所示,随着Zipf分布参数α值增加,用户任务越来越集中于流行度高的任务类型,总体看边缘服务器需要的任务资源类型有所减少,TSPI,RDTP-TSPI,BA这3种算法的总任务延迟率均有不同程度下降.RDTP-TSPI算法对用户任务进行预测和分类聚合,减少推送至边缘服务器所需的任务资源,在资源部署时通过延迟阈值判定以有效降低任务延迟发生,再通过帕累托优化任务调度,使其TTDR始终处在低水平,值为0.11%~4.03%,相比BA算法平均减少18.88%.TSPI算法缺乏用户任务预测,没有优化边缘服务器的任务资源部署,在用户任务调度时综合用户服务质量和系统服务效用进行帕累托优化,其TTDR较高,为11.02%~22.67%,相比BA算法平均减少4.56%.BA算法的TTDR最高,为15.28%~28.37%,均值达到20.22%.

Fig.10 Total task delay rate under different Zipfdistribution parameters α
图10 不同Zipf分布参数α下总任务延迟率

6 结束语

本文面向用户和服务供应商研究边云协同计算中使用任务预测的资源部署与任务调度优化.首先设计边云协同计算框架,提出基于任务预测的资源部署算法RDTP,在云服务中心基于二维时间序列对用户任务进行预测,分类聚合用户任务类型,推送任务资源至边缘服务器,提高平均用户任务命中率,减少服务器资源占用开销.然后提出基于帕累托优化的任务调度算法TSPI,在边缘服务器基于随机贪心近似算法,分别对用户服务质量和系统服务效应这2个目标进行帕累托改进,寻求2个目标曲线的相切点或相交点以优化任务调度.通过实验评估分析,结合基于任务预测的资源部署算法与基于帕累托优化的任务调度算法RDTP-TSPI,在提高平均用户任务命中率基础上,其用户平均服务完成时间、系统整体服务效应度、总任务延迟率,均优于基于帕累托优化的任务调度算法TSPI和基于FIFO的基准任务调度算法BA.未来的研究,将考虑在边云协同计算环境下进行可扩展的自适应资源部署与任务调度.

参考文献

[1]Zhu Jing, Chan D S, Prabhu M S, et al. Improving web sites performance using edge servers in fog computing architecture[C] //Proc of the 17th IEEE Int Symp on Service-Oriented System Engineering. Piscataway, NJ: IEEE, 2013: 320-323.

[2]Zhang Yaoxue, Zhou Yuezhi. Transparent computing: Spatio-temporal extension on von neumann architecture for cloud services[J]. Journal of Tsinghua Science and Technology, 2013, 18(1): 10-21.

[3]Shi Weisong, Cao Jie, Zhang Quan, et al. Edge computing: Vision and challenges[J]. IEEE Internet of Things Journal, 2016, 3(5): 637-646.

[4]Sardellitti S, Scutari G, Barbarossa S, et al. Joint optimization of radio and computational resources for multicell mobile-edge computing[J]. IEEE Transactions on Signal and Information Processing Over Networks, 2015, 1(2): 89-103.

[5]Zhang Jianjin, Wang Yunbo, Long Mingsheng, et al. Predictive recurrent networks for seasonal spatiotemporal data with applications to urban computing[J]. Chinese Journal of Computers, 2020, 43(2): 286-302 (in Chinese)(张建晋, 王韫博, 龙明盛, 等. 面向季节性时空数据的预测式循环网络及其在城市计算中的应用[J]. 计算机学报, 2020, 43(2): 286-302).

[6]Sun Yi, Yin Xiaoqi, Jiang Junchen, et al. CS2P: Improving video bitrate selection and adaptation with data-driven throughput prediction[C] //Proc of the ACM Special Interest Group on Data Communication. New York: ACM, 2016: 272-285.

[7]Lin Chuang, Su Wenbo, Meng Kun, et al. Cloud computing security: Architecture, mechanism and modeling[J]. Chinese Journal of Computers, 2013, 36(9): 1765-1784 (in Chinese)(林闯, 苏文博, 孟坤, 等. 云计算安全:架构、机制与模型评价[J]. 计算机学报, 2013, 36(9): 1765-1784).

[8]Mao Hongzi, Schwarzkopf M, Venkatakrishnan S B, et al. Learning scheduling algorithms for data processing clusters[C] //Proc of the ACM Special Interest Group on Data Communication. New York: ACM, 2019: 270-288.

[9]Jalaparti V, Bodik P, Menache I, et al. Network-aware scheduling for data-parallel jobs: Plan when you can[C] //Proc of the ACM Special Interest Group on Data Communication. New York: ACM, 2015: 407-420.

[10]Ren Xiaoqi, Ananthanarayanan G, Wierman A, et al. Hopper: Decentralized speculation-aware cluster scheduling at scale[C] //Proc of the ACM Special Interest Group on Data Communication. New York: ACM, 2015: 379-392.

[11]Jin Yuche, Renganathan S, Ananthanarayanan G, et al. Zooming in on wide-area latencies to a global cloud provider[C] //Proc of the ACM Special Interest Group on Data Communication. New York: ACM, 2019: 104-116.

[12]Mirhosseini A, West B L, Blake G W, et al. Q-Zilla: A scheduling framework and core microarchitecture for tail-tolerant microservices[C] //Proc of IEEE Int Symp on High Performance Computer Architecture. Piscataway, NJ: IEEE, 2020: 207-219.

[13]Didona D, Zwaenepoel W. Size-aware sharding for improving tail latencies in in-memory key-value stores[C] //Proc of the 16th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2019: 79-93.

[14]Chung A, Park J W, Ganger G R. Stratus: Cost-aware container scheduling in the public cloud[C] //Proc of the ACM Symp on Cloud Computing. New York: ACM, 2018: 121-134.

[15]Liu Xing, Li Jianbin, Yang Zhen, et al. A task collaborative execution policy in mobile cloud computing[J]. Chinese Journal of Computers, 2017, 40(2): 364-377 (in Chinese)(柳兴, 李建彬, 杨震, 等. 移动云计算中的一种任务联合执行策略[J]. 计算机学报, 2017, 40(2): 364-377).

[16]Nishtala R, Petrucci V, Carpenter P, et al. Twig: Multi-agent task management for colocated latency-critical cloud services[C] //Proc of IEEE Int Symp on High Performance Computer Architecture. Piscataway, NJ: IEEE, 2020: 167-179.

[17]Kulkarni N, Qi Feng, Delimitrou C, Pliant: Leveraging approximation to improve datacenter resource efficiency[C] //Proc of IEEE Int Symp on High Performance Computer Architecture. Piscataway, NJ: IEEE, 2019: 159-171.

[18]Wang Shuo, Liang Yun, Zhang Wei. Poly: Efficient heterogeneous system and application management for interactive applications[C] //Proc of IEEE Int Symp on High Performance Computer Architecture. Piscataway, NJ: IEEE, 2019: 199-210.

[19]Chen Xu, Jiao Lei, Li Wenzhong, et al. Efficient multi-user computation offloading for mobile-edge cloud computing[J]. IEEE-ACM Transactions on Networking, 2016, 24(5): 2827-2840.

[20]Wang Tian, Mei Yaxin, Jia Weijia, et al. Edge-based differential privacy computing for sensor-cloud systems[J]. Journal of Parallel and Distributed Computing, 2020, 136: 75-85.

[21]Rodrigues T G, Suto K, Nishiyama H, et al. Hybrid method for minimizing service delay in edge cloud computing through VM migration and transmission power control[J]. IEEE Transactions on Computers, 2016, 66(5): 810-819.

[22]Mao Yuyi, Zhang Jun, Letaief K B. Dynamic computation offloading for mobile-edge computing with energy harvesting devices[J]. IEEE Journal on Selected Areas in Communications, 2016, 34(12): 3590-3605.

[23]Chen Min, Hao Yixue. Task offloading for mobile edge computing in software defined ultra-dense network[J]. IEEE Journal on Selected Areas in Communications, 2018, 36(3): 587-597.

[24]He Junyi, Zhang Di, Zhou Yuezhi, et al. A truthful online mechanism for collaborative computation offloading in mobile edge computing[J]. IEEE Transactions on Industrial Informatics, 2020, 16(7): 4832-4841.

[25]Wang Chenmeng, Liang Chengchao, Yu F R, et al. Computation offloading and resource allocation in wireless cellular networks with mobile edge computing[J]. IEEE Transactions on Wireless Communications, 2017, 16(8): 4924-4938.

[26]Wang Tian, Bhuiyan M Z A, Wang Guojun, et al. Preserving balance between privacy and data integrity in edge-assisted Internet of things[J]. IEEE Internet of Things Journal, 2020, 7(4): 2679-2689.

[27]Yu Bowen, Pu Lingjun, Xie Yuting, et al. Joint task offloading and base station association in mobile edge computing[J]. Journal of Computer Research and Development, 2018, 55(3): 537-550 (in Chinese)(于博文, 蒲凌君, 谢玉婷, 等. 移动边缘计算任务卸载和基站关联协同决策问题研究[J]. 计算机研究与发展, 2018, 55(3): 537-550).

[28]Wang Yanting, Sheng Min, Wang Xijun, et al. Mobile-edge computing: Partial computation offloading using dynamic voltage scaling [J]. IEEE Transactions on Communications, 2016, 64(10): 4268-4282.

[29]Dinh T Q, Tang Jianhua, La Q D, et al. Offloading in mobile edge computing: Task allocation and computational frequency scaling[J]. IEEE Transactions on Communications, 2017, 65(8): 3571-3584.

[30]Zhang Jiao, Hu Xiping, Ning Zhaolong, et al. Energy-latency tradeoff for energy-aware offloading in mobile edge computing networks[J]. IEEE Internet of Things Journal, 2018, 5(4): 2633-2645.

[31]Wang Feng, Xu Jie, Wang Xin, et al. Joint offloading and computing optimization in wireless powered mobile-edge computing systems[J]. IEEE Transactions on Wireless Communications, 2018, 17(3): 1784-1797.

[32]Ding Yan, Liu Chubo, Zhou Xu, et al. A code-oriented partitioning computation offloading strategy for multiple users and multiple mobile edge computing servers[J]. IEEE Transactions on Industrial Informatics, 2020, 16(7): 4800-4810

[33]Ge Zhefeng, Wang Jiwei, Jiang Congfeng, et al. Analysis of resource utilization of co-located clusters[J]. Chinese Journal of Computers, 2020, 43(6): 1103-1122 (in Chinese)(葛浙奉, 王济伟, 蒋从锋, 等. 混部集群资源利用分析[J].计算机学报, 2020, 43(6): 1103-1122).

[34]Aliyun. Aliyun edge node service[OL]. [2020-06-08]. https://www.aliyun.com/product/ens.

[35]Wang Xingwei, Wang Zijian, Li Fuliang. Cache location selected algorithm for information-centric networking[J]. Journal of National University of Defense Technology, 2019, 41(1): 152-160 (in Chinese)(王兴伟, 王子健, 李福亮, 等. 信息中心网络缓存节点位置选择算法[J]. 国防科技大学学报, 2019, 41(1): 152-160).

[36]Su Mingfeng, Wang Guojun, Li Renfa. Multidimensional QoS cloud computing resource scheduling method based on stakeholder perspective[J]. Journal on Communications, 2019, 40(6): 102-115 (in Chinese)(苏命峰, 王国军, 李仁发. 基于利益相关视角的多维QoS云资源调度方法[J]. 通信学报, 2019, 40(6): 102-115).

[37]Lu Qinghua, Xu Xiwei, Bass L, et al. A tail-tolerant cloud API wrapper[J]. IEEE Software, 2015, 32(1): 76-82

Resource Deployment with Prediction and Task Scheduling Optimization in Edge Cloud Collaborative Computing

Su Mingfeng1,2, Wang Guojun3, and Li Renfa4

1(School of Computer Science and Engineering, Central South University, Changsha 410083)2(School of Business Information Technology, Hunan Vocational College of Commerce, Changsha 410205)3(School of Computer Science and Cyber Engineering, Guangzhou University, Guangzhou 510006)4(College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082)

Abstract The cloud computing model of data centralized processing is facing new challenges for providing diversified application services with rapid interaction and green efficiency. In this paper, the cloud computing capability is extended to the edge devices, and an edge cloud collaborative computing framework is proposed. A resource deployment algorithm based on task prediction (RDTP) is designed. The tasks are predicted by two-dimensional time series in cloud service center, and the task resource deployment of edge server is optimized by classification aggregation and delay threshold determination. A task scheduling algorithm based on Pareto improvement (TSPI) is proposed. At the edge servers, the Pareto progressive comparison is conducted in two stages to obtain the tangent point or any intersection point of the two objective curves of quality of user service and effect of system service to optimize task scheduling. The experimental results show that combining the resource deployment algorithm based on task prediction and the task scheduling algorithm based on Pareto improvement (RDTP-TSPI) increases the average user task hit rate. In addition, in the application scenarios of varying user task scales and different Zipf distribution parameters α, the average service completion time of users, the overall service effectiveness of system, and the total task delay rate of RDTP-TSPI are better than the TSPI and BA (benchmark task scheduling algorithm based on FIFO).

Key words task scheduling; resource deployment; task prediction; collaborative computing; edge computing

收稿日期2020-08-14;修回日期: 2021-01-27

基金项目国家自然科学基金重点项目(61632009);湖南省自然科学基金项目(2019JJ70057);广东省自然科学基金项目(2017A030308006);国家重点研发计划项目(2020YFB1005804);中南大学中央高校基本科研业务费专项资金项目(2018zzts180)

This work was supported by the Key Program of the National Natural Science Foundation of China (61632009), the Natural Science Foundation of Hunan Province (2019JJ70057), the Natural Science Foundation of Guangdong Province (2017A030308006), the National Key Research and Development Program of China (2020YFB1005804), and the Fundamental Research Funds for the Central Universities of Central South University (2018zzts180).

通信作者王国军(csgjwang@gzhu.edu.cn)

中图法分类号 TP301.6

Su Mingfeng, born in 1980. PhD candidate, professor. His main research interests include cloud computing, edge computing, and collaboration computing.

苏命峰,1980年生.博士研究生,教授.主要研究方向为云计算、边缘计算和协同计算.

Wang Guojun, born in 1970. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include cloud computing, trusted computing, and cyberspace security.

王国军,1970年生.博士,教授,博士生导师,CCF杰出会员.主要研究方向为云计算、可信计算和网络空间安全.

Li Renfa, born in 1956. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include embedded system, cyber-physical system, and collaboration computing. (lirenfa@hnu.edu.cn)

李仁发,1956年生.博士,教授,博士生导师,CCF高级会员.主要研究方向为嵌入式系统、信息-物理融合系统和协同计算.