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

苏命峰 王国军 李仁发

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

云计算、物联网、车联网、智能电网等技术迅速发展，泛在化、普适化、智能化终端广泛应用，虚拟现实、增强现实、无人驾驶、远程医疗、动态内容交付等新型网络应用对网络和计算的要求越来越高，传统数据、存储、处理集中的云计算模式面临新挑战，出现了雾计算[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 主要符号及其含义

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)综合量化，记为Qus和Ess，O={max(Qus),max(Ess)}.Γ是资源部署与任务调度优化算法.

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

(1)

(2)

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

(3)

(4)

在式(4)中，统计周期内的系统服务消耗为任务执行时间当量t与服务平均能耗系数s的乘积.tC，te分别表示云服务中心、边缘服务器的任务执行时间当量，sC，se分别表示云服务中心、边缘服务器的服务平均能耗系数.能耗系数取决于硬(软)件成本和系统运维成本.前者包括硬(软)件采购成本、折旧损耗成本；后者包括设备电能消耗、空调制冷能耗、管理服务成本.从单量比较分析，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)

(8)

(9)

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

(10)

即

证毕.

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

(11)

4 资源部署与任务调度

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

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

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

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

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

① 任务j∈J分类；

② fore∈Edo

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

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

⑥ forj∈Jdo

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

/*延迟阈值判定*/

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

/*延迟阈值判定*/

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

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

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

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

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

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

① if收到新任务j

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

③ end if

④ if任务集J非空

⑤ 任务j∈J升序排列(数据量)；

⑥ end if

⑦ forj∈Jdo

⑧ forE∪Cdo

⑩ 运用式(2)计算Qus；

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

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

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

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

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.未来的研究，将考虑在边云协同计算环境下进行可扩展的自适应资源部署与任务调度.