2017, Vol. 49
2. 河北省保定市教育考试院 信息处 河北 保定 071000;
3. 河北大学 计算机科学与技术学院 河北 保定 071002
2. Information Department of Baoding Examination Authority, Baoding 071000, China;
3. School of Computer Science and Technology, Hebei University, Baoding 071002, China
云计算是一种新兴的技术趋势，用户可以根据自己的需求从其租用软件、硬件、基础设施和计算资源等[1].近年来，云计算通过互联网扩展了现有的信息技术能力，成为一个低成本、快速的服务交付模式[2].它允许用户访问服务，就像水、电、煤气和电话等公共设施一样，用户既不必考虑在哪里提供服务，也不用去了解他们是如何进行交付的[3].正是因为云计算的取用方便快捷、费用低廉，它越来越备受人们的关注，用户量也日益增多.
云计算系统拥有大量的节点，很难要求所有节点拥有同样的性能[4]，这就导致了云环境的异构性.现在的大数据应用都是非常复杂的，并不能够仅仅通过几个任务来进行描述，故工作流就被用来表示更加复杂的大数据应用.如何将云环境下工作流任务映射并调度到合适的计算节点，成为新的研究方向.工作流调度是通过工作流调度控制，自动分配和管理相关任务在共享资源上的执行[5].在云计算中，工作流调度通过订购各种资源将每个任务分配到相关的云服务以获得满意的服务质量[6].
相比于常规的云任务调度问题，云工作流调度不仅仅要考虑用户服务质量QoS(像执行时间、用户花销等因素)的约束，还需要考虑工作流内各个任务之间相互依赖关系.许多启发式和进化算法被提出用于解决工作流调度问题，如遗传算法[7]、蚁群优化算法[8]、粒子群优化算法[9].本文提出一种基于生物共生演算法的多维QoS约束的工作流调度算法，以有效地提高云环境下工作流调度的效率.
1 问题描述以及数学建模 1.1 云系统模型本文所提出的云系统模型主要包括3个模块，如图 1所示.
|
图 1 云模型结构图 Figure 1 Structure of cloud model |
1) 用户模块多个云用户通过网络将任务提交上传到云端的任务处理单元.
2) 任务处理单元模块该模块负责定时收集用户的任务的执行信息，首先将用户提交的工作流中的子任务进行优先级的确认，并按照降序排列，形成新的任务调度队列；再将数据中心管理器所提交的虚拟机信息收集，根据任务调度策略对任务进行处理，映射到较为合适的虚拟机上，使得任务可以更优化地处理.
3) 数据中心模块一是数据中心管理器，通过它将数据中心的虚拟机信息(如内存、处理速度MIPS等)进行收集，再提交给任务调度器模块；二是基础设施即分布式数据中心集群，其中包括多个数据中心DC.每个数据中心含有多台主机，通过虚拟化技术，每台主机被虚拟化到一系列异构的虚拟机上，即虚拟机集合就分别映射到了主机集合上.
1.2 QoS目标函数由于云计算环境的动态及不确定性，用户服务质量的优化与管理变得至关重要.云环境下工作流调度的QoS目标约束条件(总的执行时间、调度费用、系统的可靠性及安全性等)无一不影响着用户体验和满意度.本文主要考虑工作流完成时间和用户花费两个QoS目标约束条件，则QoS目标约束函数为Minmize(Total_time)和Minmize(Total_cost).
工作流中任务被调度到计算资源，它的实际完成时间Total_time即为出口任务Texit的完成时间.而云工作流中成本花费包括执行成本Execution_cost和通信成本Communication_cost两部分，则执行一个云工作流的成本定义如下:
| $ Total\_\cos t = Execution\_\cos t + Communication\_cost =\\ \sum\limits_{i = 1}^n {{t_i}*Unit\_ecos{t_i}} + \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {Dat{a_{ij}}*} } Unit\_ccos{t_{ij}}, $ |
其中:ti代表任务Ti在被调度到虚拟机上运行的执行时间；Unit_ecosti表示在该虚拟机执行单位时间的花销；Dataij指的是任务Ti和Tj之间的通信数据；Unit_ccostij表示单位通信成本.
2 算法描述本文在生物共生演算法的基础上进行改进，从而来适应云环境的工作流调度的优化问题.针对多维QoS约束的问题，引入非支配解的概念，提出了一种多维QoS约束的工作流调度算法(QoS-SOS)，以解决多目标优化问题.
2.1 生物共生演算法生物共生演算法(symbiotic organisms search, SOS)[10]是一种基于种群的元启发式算法, 它与粒子群等算法相类似，都是模仿的自然现象，其性能优于其他启发式算法(GA，PSO等).它最初是用于解决连续搜索空间数值优化问题.在SOS中，主要包括共生、共栖、寄生3个阶段.在各个阶段中，每一个生物体与其他生物体随机相互作用，并重复这个过程，直到满足终止条件为止.
2.2 非支配解Pareto[11]提出了非支配解(non-dominated set)的概念，也被称作Pareto解.若由符号≺来表示支配，则X2支配X1，X2为非支配解，其对应的数学表达式为:
| $ X1 \prec X2 \Leftrightarrow \exists i\;\;{f_i}\left( {X1} \right) \le {f_i}\left( {X2} \right)\; \wedge \;\forall j\;{f_j}\left( {X1} \right) < {f_j}\left( {X2} \right), $ |
也就是说，对于任意的两个决策变量X1和X2，在任意的目标函数中，X2都优于X1, 或者存在某一目标函数，X2不小于X1，则X2为非支配解(Pareto解).
因此，要解决多个QoS目标约束函数的多目标优化问题，需要找到一组尽可能接近Pareto最优域的解，并希望找到的解能够尽可能分布均匀.然而，多个QoS约束目标之间存在冲突，如时间和成本，降低执行时间的代价务必会增加开销，同样降低成本也必然影响执行的时间.Pareto最优解所对应的目标函数是无法比较其优劣的，在某一个非支配解的基础上改进任何一个目标函数的同时，必然会引起一个或多个其他的目标函数变化.
为了满足用户QoS需求，本文算法中选择使用一个可行的带有权值的适应值函数:
fitness=α*Total_time+β*Total_cost，
其中:α+β=1, 0≤α，β≤1，α、β分别表示时间和成本的权重，体现了用户对时间和成本关注的程度.权重α、β的不同必然会导致本文算法求得的优化解集的不同.
2.3 优先级确定确定优先级的目的，在于通过计算每个子任务的优先级，并且通过优先级的大小将子任务进行合理有序的排列，这样便确定了本文算法中所应用的生物共生演算法中生物体(即任务)的排序，进而可以展开后续的工作，将任务分配到合适的虚拟机上进行处理.通过子任务的平均完成时间和任务之间的通信时间来确定任务优先级，则一个任务的优先级指的是从DAG中的出口任务Texit向上遍历到所求的任务之间所有经过的节点的平均时间和平均通信时间之和，可以表示为
| $ Prior\left( {{T_i}} \right) = \left\{ \begin{array}{l} \overline {ET{C_{{T_{{\rm{exit}}}}}}}, {\rm{if}}\;\;{T_i} = {T_{{\rm{exit}}}}, \\ \overline {ET{C_i}} + \mathop {\max }\limits_{{T_j} \in succ\left( {{T_i}} \right)} \left( {Prior\left( {{T_i}} \right) + \overline {Communication\_tim{e_{ij}}} } \right), {\rm{otherwise}} \end{array} \right. $ | (1) |
其中，
在生物共生演算法的基础上，借鉴离散粒子群算法中的离散化思想来适应云计算离散环境，引入非支配解的思想，来满足多维QoS的多目标约束，从而获得Pareto最优解集.表 1中为基于多维QoS约束的工作流调度伪代码，大致可以分为以下7个步骤.
|
表 1 QoS-SOS伪代码 Table 1 The pseudo code of QoS-SOS |
Step1 确定任务的优先级.根据公式(1) 计算工作流应用DAG中每个子任务的优先级.
Step2 根据step1中所得的任务优先级，对工作流中的任务重新进行排序.因为任务优先级越高，任务越应该优先执行，所以将任务进行降序排列.
Step3 初始化.采用随机的方式对整个生态系统E中的各个生物体进行初始化，也就是说调度方案的随机初始化，计算当前生态系统各个生物体的适应度值.
Step4 添加生态系统中的非支配解到一个外部存档EA中，并删除被该解支配的所有解.
Step5 进行共生、共栖、寄生3个阶段，根据计算新的生物体适应度，判断是否进行更新，当新的生物体适应度大于原来的适应度时，则进行更新替换；否则不发生变化.
Step6 添加生态系统中的非劣解，当生态系统中的E[i]不被EA中的任何解所支配时，就将E[i]加入外部存档，并且删除EA中被E[i]所支配的所有解.
Step7 如果满足循环终止的条件，返回外部存档EA，此时EA则表示是一个调度方案集合；否则跳转至step5继续优化.
本文所提出的算法最终获得的是一个Pareto最优的解集，这个解集就是解决方案的集合.集合中的每个解都是一个调度方案，用户可以通过个人意愿和偏好选择其中某一个解决方案，或者直接选择本算法所推荐的调度方案.
3 仿真实验 3.1 实验参数设置为了对本文所提出的算法进行测试评估，使用基于Cloudsim扩展WorkflowSim[12]平台对QoS-SOS与已有的经典算法HEFT算法、Min_Min、Max-Max进行对比实验.
云服务资源处理能力的不同，就导致了它们价格的不同.一般说来，执行成本和通信成本是反比于执行时间和通信传输时间的，即执行速度和执行的成本是成正比的.因此，假设云环境下拥有4种云服务资源，可依据表 2来为云服务资源进行定价.在WorkflowSim中，搭建一个拥有6组服务资源的云环境，并且每组云资源各拥有4种云服务资源.
|
|
表 2 云服务资源类型 Table 2 Types of cloud services resource |
算法QoS-SOS的参数设置如表 3所示.
|
|
表 3 QoS-SOS算法参数设置 Table 3 The parameter settings of QoS-SOS algorithm |
工作流Montage、Cybershake[13]和Gaussian Elimination[14]等代表了现实世界中的问题，常被作为基准来评估所提出的算法. Cybershake工作流是被南加州地震中心用来确定一个地区的地震灾害危险程度的[15-16].Cybershake是计算密集型和数据密集型工作流，不仅含有任务节点的数量可以不同，而且还可以处理大型的数据集，非常适合来验证本文所提出算法的有效性.
在相同的条件下，对QoS-SOS、HEFT算法、Min_Min、Max-Max在Cybershake不同节点数30、50、100、1 000下分别进行了测试，并观察比较结果.
在QoS-SOS算法中，每次试验所得解是一组解集，由于所得解的数量较多，我们只在对比图中画出了部分解进行对比.由图 2可以看出，QoS-SOS所得的解是一个最优解集，其中的每一个解都不绝对地用简单的优于或劣于其他的解来进行评价，这是由于执行时间的变化影响着执行的成本.此外，还可以看出，QoS-SOS算法产生的解支配HEFT、Min_Min、Max-Min算法产生的解.在不同任务节点的实验中，不论是在时间还是成本上，本算法比其他3种算法具有绝对的优势.这是因为在HEFT算法中只考虑了优化任务执行时间，忽略了任务执行的成本；而QoS-SOS将两个方面的优化目标都进行了考量.其次，相比于Min_Min、Max-Min算法，QoS-SOS算法利用任务优先级严格遵守和保持了任务之间的依赖关系，并且优化了任务的调度次序.
|
图 2 当CyberShake节点为30、50、100、1 000时, 各算法的对比 Figure 2 Comparsion of various algorithms when the CyberShake node is respectively 30, 50, 100, 1 000 |
因此，QoS-SOS算法性能方面表现极为显著，具有一定的有效性，极大程度上优化了工作流调度的时间和成本.
4 结论针对解决云环境下用户服务质量的优化问题，建立了新的工作流调度云系统模型和相应的数学模型，对本文所提出的算法进行了详细的阐述.通过云工作流仿真平台WorkflowSim，对QoS-SOS算法进行了仿真测试，并与HEFT、Min_Min、Max-Min算法进行了对比试验.结果表明QoS-SOS算法不仅可以提供一组解，而且性能明显优于其他3种算法，极大程度上优化了工作流执行时间和总成本.然而，本文仅仅考虑了执行时间和总成本两个优化目标，未来还可以考虑两个或者两个以上的优化目标(如能耗、可靠性等).
| [1] |
HAYES B. Cloud computing[J]. Communications of the ACM, 2008, 51(7): 9-11. DOI:10.1145/1364782 (  0) |
| [2] |
KAUR P D, CHANA I. A resource elasticity framework for QoS-aware execution of cloud applications[J]. Future generation computer systems, 2014, 37(7): 14-25. ( 0) |
| [3] |
杨晓晖, 丁文卿. 云存储环境下基于CP-ASBE数据加密机制[J]. 河北大学学报(自然科学版), 2016, 36(4): 424-431. ( 0) |
| [4] |
NARSIMHA R C H. A CIM (common information model) based management model for clouds[C]//2012 IEEE International Conference on Cloud Computing in Emerging Markets.Honolulu, 2012:1-5. http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=6354585
( 0) |
| [5] |
KAUR N, AULAKH T S, CHEEMA R S. Comparison of workflow scheduling algorithms in cloud computing[J]. International journal of advanced computer science and applications, 2011, 2(10): 9036-9051. ( 0) |
| [6] |
ALKHANAK E N, LEE S P, KHAN S U R. Cost-aware challenges for workflow scheduling approaches in cloud computing environments: taxonomy and opportunities[J]. Future generation computer systems, 2015, 50(C): 3-21. ( 0) |
| [7] |
AHMAD S G, MUNIR E U, NISAR W. PEGA: a performance effective genetic algorithm for task scheduling in heterogeneous systems[C]// High Performance Computing and Communication & 2012 IEEE 9th International Conference on Embedded Software and Systems (HPCC-ICESS).Liverpool, 2012:1082-1087. http://dl.acm.org/citation.cfm?id=2373463
( 0) |
| [8] |
王杰, 李慧慧, 彭金柱. 一种拟随机初始化模拟退火粒子群算法[J]. 郑州大学学报(理学版), 2016, 48(3): 75-81. ( 0) |
| [9] |
TAHERI J, LEE Y C, ZOMAYA A Y, et al. A bee colony based optimization approach for simultaneous job scheduling and data replication in grid environments[J]. Computers and operations research, 2013, 40(6): 1564-1578. DOI:10.1016/j.cor.2011.11.012 ( 0) |
| [10] |
CHENG M Y, PRAYOGO D. Symbiotic organisms search: a new metaheuristic optimization algorithm[J]. Computers and structures, 2014, 139: 98-112. DOI:10.1016/j.compstruc.2014.03.007 ( 0) |
| [11] |
ZITZLER E, THIELE L. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach[J]. IEEE transactions on evolutionary computation, 1999, 3(4): 257-271. DOI:10.1109/4235.797969 ( 0) |
| [12] |
CHEN W, DEELMAN E. WorkflowSim: a toolkit for simulating scientific workflows in distributed environments[C]// IEEE International Conference on E-Science.Chicago, 2012:1-8. http://ieeexplore.ieee.org/document/6404430/
( 0) |
| [13] |
JUVE G, CHERVENAK A, DEELMAN E, et al. Characterizing and profiling scientific workflows[J]. Future generation computer systems, 2013, 29(3): 682-692. DOI:10.1016/j.future.2012.08.015 ( 0) |
| [14] |
ARABNEJAD H, BARBOSA J G. List scheduling algorithm for heterogeneous systems by an optimistic cost table[J]. IEEE transactions on parallel and distributed systems, 2014, 25(3): 682-694. DOI:10.1109/TPDS.2013.57 ( 0) |
| [15] |
GRAVES R, JORDAN T H, CALLAGHAN S, et al. Cybershake: a physics-based seismic hazard model for southern california[J]. Pure & applied geophysics, 2011, 168(3/4): 367-381. ( 0) |
| [16] |
CALLAGHAN S, MAECHLING P, SMALL P, et al. Metrics for heterogeneous scientific workflows: a case study of an earthquake science application[J]. International journal of high performance computing applications, 2011, 25(3): 274-285. DOI:10.1177/1094342011414743 ( 0) |