基于用户QoS预测的任务流调度算法

杨丽蕴，张绍林，韩　宏，秦　科

(1.中国电子技术标准化研究院，北京 100007；2.电子科技大学 计算机科学与工程学院，四川 成都 611731)

基于用户QoS预测的任务流调度算法

杨丽蕴1，张绍林2，韩宏2，秦科2

(1.中国电子技术标准化研究院，北京 100007；2.电子科技大学 计算机科学与工程学院，四川 成都 611731)

摘要:提出在云计算数据中心环境下，节省开销并保障用户QoS的调度算法，用预测的方式来判断QoS走势，用任务流调度开规避不利的QoS情况。通过ARIMA预测模型对任务的QoS进行预测，根据预测结果得到有潜在QoS危险的任务预警，并利用一个粒子群(PSO)和引力搜索(GSA)的混合算法求得最终的调度策略，最后通过任务调度保障用户的QoS，同时在调度算法中根据网络拥塞控制的思想添加了一个保留虚拟机的方案。实验表明该算法能有效保障用户QoS，比原混合算法减少时间开销9.26%。

关键词:云计算数据中心；服务质量；任务流调度；ARIMA预测模型；粒子群优化算法；引力搜索算法

云计算[1-2]打破了传统的计算机和网络资源分配方式，把计算机相关的基础设施服务平台以及软件作为一种服务提供给用户。用户根据自己的需求向提供商购买需要的服务，这种基于订阅的即付模式[3]受到广大消费者的青睐。由于云计算低成本的基础投入以及高效率的应用，云计算的各种应用服务在当前的智慧城市和大数据中心建设、运营及能效管理[4]中起着越来越重要的作用，成为未来主流的应用模式[5]。

云计算的管理是虚拟基础设施管理的一部分，包括对虚拟机管理和对虚拟机测试的管理[6]，它通过软件的形式(比如Open Nebula，OpenStack，Eucalyptus，ECP，Overt等)来实现云计算的资源管理[7-8]。面向企业级设计的传统资源管理解决方案无法满足云计算对于管理的要求，由于云计算环境下的多租户、大规模，云计算的动态性以及其他相关因素，使得云计算的资源管理成为一个十分困难的问题，而资源调度则是资源管理中最重要、最困难的一环。

云计算的调度按照用户需求给用户合理分配资源，实现云系统的负载均衡，正确的调度能够很大程度上提高云系统的资源利用率，提高系统的容错率，保障系统的稳健性。资源调度问题是一个多目标优化的NP难问题[9]，研究主要集中在对多目标约束情况下的基于全局搜索的启发式算法[10-11]。任务调度的早期的工作主要关注于性能和服务质量，目前的调度研究主要转向以经济原则为目标的调度。文献[12-13]把虚拟机动态迁移作为优化目标，以此减少能量消耗。文献[14]挂起优先级相对较低的任务，通过这种方式减少能耗。文献[15]使用了双适应度的粒子群优化算法优化任务的完成时间和成本。文献[16]根据服务器负载均衡关闭不需要的虚拟机来达到节能目的。文献[17]把任务分割成子任务，放入不同优先级的队列中，然后使用改进蚁群算法进行调度，使得任务延迟时间、调度公平性及效率方面性能更好。澳大利亚的Rajkumar Buyya等人提出了面向经济模型的资源调度方式[18]，他们提出通过SLA资源分配器来协商用户和提供商之间的利益，目前这方面的问题还在继续研究之中。

1预测模型和调度算法

用户购买云服务的时候会和服务提供商签订SLA[19]，如果服务提供商违背SLA将会造成不良影响且支付违约金，因此，服务提供商在设计云系统的时候需要用各种手段保障用户的QoS能够按照协议准时完成。由于系统中的用户任务繁多，在分配任务的时候需要选择合适的虚拟机，因此系统将面临任务流调度问题。

1.1ARIMA预测模型

本文提出一种基于用户QoS预测的用户任务流调度，以达到满足用户QoS的目的。预测模型选择ARIMA(Autoregressive Integrated Moving Average Model)模型[20]，根据预测结果进行合适的任务调度，规避不利的预测状态。

在ARIMA(p，d，q)模型里，AR表示自回归，MA表示移动平均，I是差分过程，p代表自回归项，q代表了移动平均项，d对象序列的平稳时期差分次数。

式(1)给出了下一时间点的预测值计算

(1)

式中：c是常数；φ是自回归参数；et是白噪声；θ是移动平均成分。如果在ARIMA(p，d，q)模型中，p，d，q的值能够被确定，那么可以通过式以及监控数据很容易计算出未来的预测值。

1.2粒子群优化算法和引力搜索算法

本文参考了粒子群和引力搜索混合算法(Sahar Mirzayi & Vahid Rafe)[21]，该算法以粒子群算法为基础，在每次迭代粒子群移动的时候加入了粒子之间的引力作用，使得粒子的搜索范围更大，搜索精度更高。

1)粒子群优化算法

算法中的位置向量xi=(xi1,xi2,…,xiD)和速度向量vi=(vi1,vi2,…,viD)，D是空间维度。

(2)

(3)

2)引力搜索算法

引力搜索算法把问题建模成多个粒子，每个粒子受其他粒子的引力作用，引力提供粒子加速度，使得粒子能够在解空间里移动。

粒子群使用Xi来表示

(4)

(5)

(6)

(7)

(8)

式中：k-best表示在某个时间点选取一定数量处于最优位置的粒子，这些粒子将会对其他随机粒子产生引力，导致新一轮的位置变化。新的粒子速度由当前速度加上加速度，加速度由引力计算得出

(9)

(10)

best(t)=minfitj(t)，j∈1,…,N

(11)

worst(t)=maxfitj(t)，j∈1,…,N

(12)

式中：fitj(t)由式计算得出。在某个时刻t，粒子xi的质量用Mi(t)来表示。粒子的质量越大，表示粒子的局部优化越好，越接近最优解，所以对其他粒子的引力越大。质量Mi(t)根据下式计算得出

(13)

(14)

引力算法在迭代过程中是慢慢区域稳定，因此引力常数G(t)是逐渐变小的。式(15)给出了引力常数G(t)的求解

G(t)=Goe-a(1/T)

(15)

式中：初始值Go设置为100；初始值a设置为20；参数T是算法总迭代次数

引力算法的优势是有部分粒子的位置是非常优化的。为了改进提高算法的收敛速度，在每一轮中选取部分优化很好的粒子，这部分粒子将对其他粒子产生引力，选取的数量直接影响着算法性能，由式(16)给出

(16)

式中：p是粒子总的数量；i是当前迭代次数。

2基于用户QoS预测的任务流调度算法

文献[21]介绍的混合算法中没有制定在每次调度前对的虚拟机保留方案。由于过多的保留虚拟机会造成资源浪费，而过少的保留虚拟机会因为虚拟机的连续删除和创建带来很大的系统开销和能源浪费。因此本文在原混合算法的基础上提出了虚拟机的保留方案，虚拟机保留的数量参考了网络拥塞控制算法的思路，而具体保留哪些虚拟机则根据虚拟机的资源利用率来判断。同时为了确保用户的QoS，本文提出一种基于QoS预测的调度模型，通过任务流的调度来满足模型中的指标。

2.1用户QoS预测模型

根据QoS的可浮动范围，将当前用户QoS状态分为了4类，如图1所示：

1)QoS正常区域：用户的任务能够非常及时地得到服务器的响应，用户对当前的服务处于满意状态。

2)QoS预警区域：用户的任务能够得到服务器的及时响应，但是任务的QoS响应时间相对于正常区域的QoS略高，表明用户的QoS处于相对危险的区域。这时候需要预测模块的预测数据来判断用户QoS的走向，如果QoS走向有着严重的下降趋势，那么就需要调度中心对用户的任务进行调度，确保用户的QoS是处于理想区域或者向着理想区域发展。

3)QoS危险区域：用户的任务的响应时间已经快要接近用户制定的底线，这时候如果预测模块的预测数据表明QoS没有处于上升趋势，那么就需要调度中心对用户的任务进行调度，优先给任务分配资源。

4)QoS失败区域：用户的任务没能够得到服务的及时响应，用户任务将无法按期完成，这时候应该按照合同计算对用户产生的损失并且进行赔偿，因此必须确保用户QoS不能到达失败区域。

图1　用户QoS状态图

根据用户QoS的预测结果以及当前的监控值可以计算出用户的QoS变化趋势，通过变化趋势的取值范围把QoS变化趋势分为4个状态：

1)QoS上升：QoS状态向着好的方向变化；

2)QoS缓慢降级：QoS状态恶化，速度低速；

3)QoS中速降级：QoS状态恶化，速度中速；

4)QoS高速降级：QoS状态恶化，速度高速。

然后通过整合QoS状态以及QoS的趋势，可以得到如表1的QoS预警决策。相应决策那里的预警策略可以根据需求进行调整。

表1QoS预警决策

QoS状态QoS趋势相应决策正常区域QoS上升正常运行正常区域QoS缓慢降级正常运行正常区域QoS中速降级正常运行正常区域QoS高速降级预警预警区域QoS上升正常运行预警区域QoS缓慢降级正常运行预警区域QoS中速降级预警预警区域QoS高速降级预警危险区域QoS上升正常运行危险区域QoS缓慢降级预警危险区域QoS中速降级预警危险区域QoS高速降级预警失败区域所有告警

2.2混合粒子群调度算法

2.2.1算法的优化目标

(17)

2.2.2基于PSO和GSA融合算法的改进

文献[21]融合了PSO算法和GSA算法，该融合算法在之前并没有被研究过，算法使用PSO算法完成粒子的全局搜索，然后使用GSA算法完成粒子的局部搜索任务，这两个算法分工明确，能够很好解决全局搜索和局部搜索不能兼顾的问题，并且通过实验表明该融合算法收敛速度快，能够避免局部最优解。但是原文中没有提供调度时段的虚拟机保留方案，下面是本文提出的方案。

在任务流开始任务调度的时候首先有2个表，一个是虚拟机表，一个是待分配任务表，首先需要根据云计算的历史数据从虚拟机表中选择下次调度任务需要保留的虚拟机，这是因为保留虚拟机比删除然后再新建虚拟机节省资源和时间，但是保留过多的虚拟机有可能造成虚拟机资源浪费，并且保留的虚拟机型号也不一定和下一次的任务调度完全匹配，那么势必会造成大量的资源碎片，降低资源利用率，形成浪费。因此需要一个算法策略来决定保留虚拟机的数量以及保留哪些虚拟机。

首先是保留虚拟机的数量，数量不宜过多，也不宜过少。场景需要在一个动态模型中找到一个动态变化的最大值。保留虚拟机数量的算法策略有3种：

1)数量恢复阶段，保留虚拟机的数量以乘积方式递增；

2)数量保持阶段，保留虚拟机的数量以小步长加法的方式增加；

3)数量回落阶段，保留虚拟机的数量以倍减的方式递减。

根据虚拟机的历史数据计算出每个调度轮回中，虚拟机能够保持良好运行状态的虚拟机数量百分比per_vmn，以及最优百分比值opt_vmn，然后根据现阶段虚拟机的数量计算出平均值以及最优值，初始数量设置为平均值数量。为了更好理解，现假设计算出的平均值为200，最优值为733，恢复阶段乘法参数设置为2，回落阶段乘法参数同样为2，保持阶段加法步长为66。虚拟机数量保留策略如图 2所示。确定了保留虚拟机的数量以后需要确定具体保留哪些虚拟机。本文采取的是根据虚拟机负荷来判断，保留负荷高的虚拟机。

图2　虚拟机数量保留策略示意图

2.2.3算法流程

在云计算系统运行过程中，提供商以按需模式向云用户提供服务，并且为了收集分析数据，需要对整个系统进行监控，适时增加虚拟机数量以满足用户请求。调度过程中调度中心会根据历史数据来对任务进行估计，如果现有虚拟机无法满足用户QoS，那么用户任务将被分配到性能更强大的虚拟机上。调度中心根据用户待分配任务列表以及手中的云资源来对任务进行调度。下面是调度的具体流程：

1)根据虚拟机保留方案保留虚拟机；

2)根据任务数量初始化粒子数量；

3)在式(3)中设定粒子群算法初始速度；

4)通过式(3)计算粒子的速度；

5)通过式(2)计算粒子的位置；

6)通过式(13)和(14)计算粒子的质量；

7)通过式(11)找到k_best粒子；

8)通过式(12)选取位置较差的粒子准备下一步；

9)通过式(8)计算粒子的所受引力；

10)通过式(9)更新粒子加速度；

11)通过式(10)更新粒子位置；

12)通过式(15)更新万有引力参数G(t)；

13)通过式(17)找出预测值最优的粒子解集；

14)检测迭代次数是否达到最大，不是则返回第4)步；

15)算法结束。

每一轮迭代都是先通过PSO算法对粒子进行移动，然后再通过GSA对部分粒子进行局部搜索，这样2个算法互相弥补，扩大搜索空间以及提高了搜索精度。

3基于CloudSim的模拟仿真实验分析

本文仿真实验使用CloudSim(Buyya，Ranjan，& Calheiros)[23]。试验中虚拟机的定价方式以及虚拟机的配置参数参照Amazon EC2的标准。输入的任务是一个任务流DAG，每个任务的属性都是一样的，在CloudSim中文件输入大小以及输出大小都设置为1 Gbyte。

针对PSO算法的参数，参考Pandey 在实验中的设置[24]，粒子的数量设置为任务数量的2倍，PSO中粒子初始速度为随机数，最大迭代次数设置为400，粒子的惯性值为0.9。GSA算法中的粒子初始速度设置为0。每次调度时间不能大于100 ms，每个实验运行20次，最终数据取平均值。试验中的一个重要指标参照公式，其中ω1和ω2取值都为0.5。

本文主要是根据历史数据以及系统的监控信息来对用户未来的QoS情况进行预测，然后通过一个启发式的任务流调度算法来对任务进行调度，找出最适合用户QoS的解，并且这个解也要尽量减少系统的成本消耗。首先是测试任务在虚拟机上运行时的消耗，消耗分别是任务的运行消耗，其次是任务的数据传输消耗。本文选择以下对比算法：贪心算法、PSO算法[24]、GSA算法、PSO-GSA融合算法，以及本文的HPSO算法。算法性能指标参照式，主要包括任务的运行成本和数据传输成本。算法的目的是让这个成本越低越好。

从图3可以看出任务的主要消耗是任务的运行消耗，主要是任务占用处理器核心进行计算，运行消耗占用总消耗的80%以上。在调度的时候需要根据任务的消耗对任务进行合理的分配。因为虚拟机的规格不一，消耗较多的任务倾向于分配到较大的虚拟机。

图3　执行任务的代价图

从图4可以看出，贪心算法在任务数量增多以后任务的执行成本有明显增加。引力搜索算法(GSA)的情况比贪心算法是有明显改善。这是由于引力搜索算法的全局搜索能力比较差的缘故。粒子群算法(PSO)虽然全局搜索能力依然有限，但是可以给粒子赋予较高的初始速度来优化全局搜索能力，因此PSO的表现要略优于GSA。P-G融合改进算法因为使用粒子群算法的全局搜索能力，再利用GSA进行每次迭代中的粒子微调，提高具备搜索能力。本文提出的改进算法HPSO因为增加了虚拟机保留方案，在每一轮任务调度的时候对虚拟机的保留数量以及质量进行算法决策，因此能有效减少资源浪费，增加资源利用率。相对于原算法在任务数量较低的时候没有太大变化，当任务达到1 000的时候执行代价降低了9.26%。

图4　执行代价对比图

4结束语

本文研究了如何利用历史数据以及监控数据来预测用户的QoS，然后从用户的任务调度入手来确保用户的QoS，同时也降低了系统的资源浪费。本文首先研究了一个用户QoS的预测模型ARIMA，通过该模型对用户QoS的状态进行预测，然后根据预测结果以及当前状态的监控数据对结果进行分类，当用户的QoS状态处于预警状态或者危险状态时通过云计算资源管理中心对用户任务进行调度，分配更合适的资源。其中使用的调度算法是一个改进的PSO和GSA混合算法，本文弥补了原混合算法在保留虚拟机方案方面的空缺，通过实验证明方案非常成功。

ARIMA模型作为预测模型是可行的，但是在预测模型中并没有考虑云计算数据中心用户任务数据的周期性，以及用户的QoS偏好属性，因此在预测的准确性方面还有不小的提升空间。本文对PSO和GSA融合算法的改进缺少大量实际任务流数据的支撑，因此在虚拟机保留方案中并没能很好地考虑任务流调度中的数据特性而采取响应的策略，添加的虚拟机保留方案只是不断地试探虚拟机的最佳保留数量，并在该数量附近区间内不断循环，没能维持在最佳数量。

参考文献：

[1]BUYYA K，YEO C S，VENUGOPAL S， et al. Cloud computing and e merging IT platforms： vision， hype， and reality for delivering computing as the 5th utility[J]. Future veneration computer systems，2009，25(6)：599-616.

[2]ARMBRUST M， FOX A， GRIFFITH R， et al. Above the clouds： a berkeley view of cloud computing[R].Berkeley：UCB/EECS，2009.

[3]LOMBARDI F，DI PIETRO R. Secure virtualization for cloud computing[J]. Journal of network and computer applications，2011，34(4)：1113-1122.

[4]李海波，王洁萍，王卫国，等.数据中心能效分析及标准化建议[J].信息技术与标准化，2012(5)：32-35.

[5]LIN W W，QI D Y. Research on resource self-oranizing model for cloud computing[C]//2010 International Conference on Internet Technology and Applications.[S.l.]：IEEE， 2010：1-5.

[6]余凤，徐晓钟，李建军.基于云计算IaaS产品测试技术的研究[J].电视技术，2014，38(15)：272-276.

[7]CERBELAUD D， GARG S， HUYLEBROECK J. Opening the clouds： qualitative overview of the state-of-the-art open source VM-based cloud management platforms[C]// Acm/ifip/usenix International Conference on MIDDLEWARE. New York：Springer-Verlag，2009：1821-1829.

[8]WEN X， GU G， LI Q， et al. Comparison of open-source cloud management platforms： OpenStack and OpenNebula[C]//2012 9th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD).[S.l.]：IEEE，2012：2457-2461.

[9]ZHU X， YOUNG D， WATSON B J， et al. 1000 islands： an integrated approach to resource management for virtualized data centers[J]. Cluster computing， 2009， 12(1)：45-57.

[10]LI B， LI J， HUAI J， et al. EnaCloud： an energy-saving application live placement approach for cloud computing environments[C]//Proc. 2009 IEEE International Conference on Cloud Computing. [S.l.]：IEEE， 2009：17-24.

[11]张雨， 李芳， 周涛. 云计算环境下基于遗传蚁群算法的任务调度研究[J]. 计算机工程与应用， 2014， 50(6)：51-55.

[12]WANG X R， WANG Y F. Coordanating power control and performance management for virtualized server clusters[J]. IEEE transactions on parallel and distributed systems， 2011， 22(2)： 245-259.

[13]JUNG G， HILTUNEN M A， JOSHI K R， et al. Mistral： dynamically managing power， performance， and adaptation cost in cloud infrastructures[C]//Proc. 2010 IEEE 30th International Conference on Distributed Computing Systems. [S.l.]：IEEE， 2010：62-73.

[14]SOTOMAYOR B， KEAHEY K， FOSTER I， et al. Enabling cost-effective resource leases with virtual machines[C]//Hot Topics Session in ACM/IEEE International Symposium on High Performance Distributed Computing. [S.l.]：IEEE， 2007：237-240.

[15]封良良， 张陶， 贾振红，等. 云计算环境下基于改进粒子群的任务调度算法[J]. 计算机工程， 2013， 39(5)：183-186.

[16]CHEN Y， DAS A， QIN W， et al. Managing server energy and operational costs in hosting centers[C]//ACM SIGMETRICS Performance Evaluation Review. [S.l.]：ACM， 2005： 303-314.

[17]魏赟， 陈元元. 基于改进蚁群算法的云计算任务调度模型[J]. 计算机工程， 2015，41(2)：12-16.

[18]BUYYA R， YEO C S， VENUGOPAL S. Market-oriented cloud computing： vision， hype， and reality for delivering it services as computing utilities[C]//Proc. 10th IEEE International Conference on High Performance Computing and Communications. Dalian：IEEE，2008：26-32.

[19]王洁萍，李海波，高林.云计算模式下服务水平协议标准化研究[J].信息技术与标准化，2012(10)：22-24.

[20]REHMAN Z U， HUSSAIN O K， HUSSAIN F K， et al. User-side QoS forecasting and management of cloud services[J]. World wide web-internet & web information systems， 2015， 18(6)：1677-1716.

[21]MIRZAYI S， RAFE V. A hybrid heuristic workflow scheduling algorithm for cloud computing environments[J]. Journal of experimental & theoretical artificial intelligence， 2015， 27(6)：721-735.

[22]RASHEDI E， HOSSEIN N，SARYAZDI S. GSA： a gravitational search algorithm[C]// 2012 2nd International Conference on Computer and Knowledge Engineering (ICCKE). [S.l.]：IEEE，2012：2232-2248.

[23]BUYYA R， RANJAN R， CALHEIROS R N. Modeling and simulation of scalable cloud computing environments and the CloudSim toolkit： challenges and opportunities[C]//International Conference on High PERFORMANCE Computing & Simulation. [S.l.]：IEEE， 2009：1-11.

[24]PANDEY S， WU L， GURU S M， et al. A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments[C]//2010 24th IEEE International Conference on Advanced Information Networking and Applications. [S.l.]：IEEE， 2010：400-407.

杨丽蕴(1981— )，女，学士，主要研究方向为云计算；

张绍林(1985— )，硕士生，主要研究方向为云计算、大数据；

韩宏(1972— )，副教授、博士，主要研究方向为云计算、信息安全；

秦科(1980— )，副教授、博士，主要研究方向为云计算、大数据。

责任编辑：时雯

Workflow scheduling algorithm based on forecast of users’ QoS

YANG Liyun1，ZHANG Shaolin2，HAN Hong2，QIN Ke2

(1.SoftwareEngineeringandEvaluationCenter，ChinaElectronicsStandardizationInstitute，Beijing100007，China；(2.SchoolofComputerScience&Engineering，UniversityofElectronicsScience&TechnologyofChina，Chengdu611731，China)

Abstract:Presenting a model to save the consumption and assure the users QoS in the data center environment of cloud computing. It analyzes the current state of the running tasks according to the results of the QoS prediction assigned by the ARIMA forecasting model. The scheduling policy with the algorithm combined particle swarm optimization(PSO) and gravitational search algorithm(GSA) is calculated according to the analyses of QoS status. A retaining virtual machine algorithm on the basis of the original algorithm is proposed. The retaining algorithm takes the reference to the network congestion control algorithm. Experiment shows that the algorithm could reduce the energy consumption of 9.26% than the original hybrid algorithm.

Key words:data center of cloud computing；QoS；workflow scheduling；ARIMA；PSO；GSA

中图分类号：TP312

文献标志码：A

DOI：10.16280/j.videoe.2016.06.017

基金项目：工信部智能制造专项(工业云服务模型标准化与试验验证系统)

作者简介：

收稿日期：2016-05-19

文献引用格式：杨丽蕴，张绍林，韩宏，等.基于用户QoS预测的任务流调度算法[J].电视技术，2016，40(6)：91-97.

YANG L Y，ZHANG S L，HAN H，et al. Workflow scheduling algorithm based on forecast of users’QoS [J].Video engineering，2016，40(6)：91-97.