基于数据挖掘的混合云作业调度算法
马文+耿贞伟+张莉娜
摘 要： 针对当前云作业调度算法效率低的不足，为了获得理想的云作业调度结果，以便给用户提供更好的服务质量，提出基于数据挖掘的混合云作业调度算法。对混合云作业调度的原理进行分析，指出当前云作业调度算法性能差的原因，建立云作业调度的目标函数，并采用数据挖掘技术找到最理想的混合云作业调度方案。在CloudSim环境下，通过具体混合云作业调度实验对算法的性能进行验证。结果表明，该算法不仅大幅度提高了混合云作业调度的成功率，而且加快了混合云作业完成的时间，具有较好的实际应用价值。
关键词： 云计算系统； 作业调度； 完成时间； 数据挖掘； 服务质量
中图分类号： TN911?34； TP393 文献标识码： A 文章编号： 1004?373X（2017）19?0049?03
Hybrid cloud job scheduling algorithm based on data mining
MA Wen， GENG Zhenwei， ZHANG Lina
（Information Center of Yunnan Power Grid Co.， Ltd.， Kunming 650217， China）
Abstract： Aiming at the low efficiency of the current cloud job scheduling algorithms， a hybrid cloud job scheduling algorithm based on data mining is proposed to obtain the ideal cloud job scheduling results and provide better service quality for users. The principle of the hybrid cloud job scheduling is analyzed. The reason why the current cloud job scheduling algorithm has poor performance is pointed out. The objective function of cloud job scheduling is established. The data mining technology is used to seek out the most ideal hybrid cloud job scheduling scheme. The performance of the algorithm was verified by means of the specific hybrid cloud job scheduling experiment in CloudSim environment. The results show that the proposed algorithm can improve the success rate of the hybrid cloud job scheduling greatly， and speed up the completion time of the hybrid cloud job， which has high practical application value.
Keywords： cloud computing system； job scheduling； completion time； data mining； service quality
0 引 言
云计算是一种新的计算模式，主要用于解决大规模数据处理问题，集成了计算机、通信、模式识别等技术，通过Internet进行资源共享，用户可以通过平台申请自己的资源，完成相应的任务，具有价格低、灵活、通用性强等特点，在许多领域得到了成功的应用[1?2]。根据云规模大小，可以划分为私有云、公有云和混合云三种类型，其中混合云是公有云和私有云的综合，其实际应用价值更高，已经成为云计算将来的发展方向[3]。
在混合云的实际应用中，由于每一类用户对云计算资源的需求不同，如何快速、有效地完成用户提交的混合云作业，为用户提供高质量的服务，显得尤为重要，成为当前云计算系统研究中的热点[4]。为了解决云计算混合云作业调度问题，一些学者进行了深入研究，当前有许多计算作业调度算法[5]。最初采用公平调度算法实现云计算混合云作业调度，对于规模较小的云计算混合云作业调度问题，可以获得理想的云计算混合云作业调度方案，当云计算混合云作业调度问题规模较大时，求解速度很慢，而且难以获得最优的云计算混合云作业调度方案，尤其对于超大规模的云计算混合云作业调度问题，无法顺利求解[6]。为此有学者采用启发式算法，如粒子群算法等，它们将云计算作业调度问题看作启发式算法求解的目标，通过不断搜索找到云计算作业调度最优或者次优方案[7?9]，求解效率明显要高于公平调度算法，然而云计算作业调度属于NP难题，当云计算作业调度问题的规模较大时，它们性能急剧下降，求解时间相当长，无法满足云计算作业在线调度要求，也不能满足用户服务的实时性，同时这些算法只是简单针对公有云和私有云的作业调度问题，当前混合云作业调度的研究很少[10?11]。
针对混合云作业调度问题，提出基于数据挖掘的混合云作业调度算法。首先对云计算系统的作业调度原理进行分析，并描述混合云体系结构；然后建立混合云作业调度的目标函数，采用数据挖掘技术进行求解；最后在CloudSim环境下实现仿真实验，验证其有效性。
1 云计算系统以及混合云的架构
1.1 云计算系统的构架
云计算系统通过Internet将不同地点、不同区域的单台计算机资源连接起来，计算机资源主要包括CPU、存儲器、网络带宽等，它们组成一个庞大的计算机系统，采用分布式方式给用户提供相应的资源，用户通过自己的具体要求分配到相应的资源，从而完成自己的作业，具体架构如图1所示。
1.2 混合云的架构
混合云采用一定技术将私有云和公有云组合在一起，基本架构如图2所示。其中私有云主要控制隐私数据，保密性高，但单一的私有云有其局限性，无法全面提供给用户满意服务，因此公有云是私有云的有益补充，可扩展性更好。
2 混合云作业调度算法
2.1 混合云作业调度的目标函数
在实际应用中，云作业规模很大，单采用一个云计算节点无法正常完成，因此需要对云作业进行分解，划分为多个子作业，根据每一个子作业特点分配相应的资源节点。当全部子作业都完成后，通过管理节点将它们组合在一起，将最终结果反馈给用户。云作业通常采用Map/Reduce模式，通过Map和Reduce函数实现用户作业的调度，Map/Reduce工作原理如图3所示。
Map/Reduce完成混合云作业的步骤如下：
（1） 用户提交作业，每一个作业根据其特点划分为多个子作业（work），那么作业[t]的运行时间[TaskTt]为：
[TaskTt=maxj=1NomWM（i，j）+x=1NorWR（k，x）] （1）
式中：[WM（i，j）]为第[j]个子任务所需的时间；Nom和Nor表示作业在队列中的次序。
（2） 混合云作业调度目标，保证用户提交的作业总完成时间[T1]和平均完成时间[T2]尽可能最小，同时满足用户要求，则有：
[T1=mint=1NumTTaskTt] （2）
[T2=min1NumTt=1NumTTaskTt] （3）
综上可知，混合云作业调度的目标函数可以写为：
[T=mint=1NumTTaskTt+min1NumTt=1NumTTaskTt] （4）
为了给每一子作业分配合理的云资源，尽可能加快作业的完成时间，采用数据挖掘技术对作业完成的时间进行预测，根据预测结果分配相应的云计算资源。
2.2 数据挖掘技术
对于训练样本[xi，yi，]采用数据挖掘对其变化特点进行分析，可以建立如下的回归函数：
[f（x）=ωT?（x）+b] （5）
对式（5）进行适当转换，得到一个如下的约束条件：
[minω2+12Ci=1nξ2i s.t. yi-ωT?（x）+b=eii=1，2，…，n] （6）
式中[ei]为回归偏差。
通过拉格朗日乘子[αi]进行变换，得到其对偶形式为：
[L（ω，b，ζ，α）=minω2+12Ci=1nξ2i+i=1nαiωT?（x）-b+ei-yi] （7）
引入核函数[K（xi，xj）=?T（xi）?（xj）]，使得其可以求解非线性回归问题，核函数定义如下：
[k（xi，xj）=exp-xi-xj22σ2 ] （8）
因此，非线性回归问题的数据挖掘结果为：
[f（x）=i=1Nαiexp-xi-xj22σ2+b] （9）
2.3 数据挖掘技术的混合云作业调度算法
设云计算系统共有[m]个计算机资源[{v1，v2，…，vm}，]不同作业要求的服务不一样，导致需要的资源也不相同，因此本文用数据挖掘技术对作业的需求进行预测，具体工作步骤如下：
（1） 对于一个具体的云计算作业，收集与其相似的历史样本数据。
（2） 对历史样本数据进行聚类分析，选择与待完成云计算作业相似度较高的样本。
（3） 将聚类分析获得的样本输入到数据挖掘算法进行分析，通过学习确定最优参数，得到该云计算作业完成的预估时间。
（4） 根据云计算作业的预估时间，向云计算系统申请相应的资源。
（5） 计算该云计算作业实际完成的时间，并得到预估时间和实际完成时间之间的偏差。
（6） 如果偏差太多，返回步骤（2），直到偏差达到预先设置的要求为止，从而完成云计算作业调度。
3 仿真实验
3.1 仿真平台
为了分析基于数据挖掘的混合云作业算法的有效性，建立混合云实验平台，其参数具体如表1和表2所示，仿真软件采用CloudSim。
3.2 实验结果与分析
不同规模的云作业条件下，作业的平均完成时间和总完成时间如图4所示。对图4的实验结果进行对比分析可以发现，当作业规模增大时，作业完成时间延长，但本文算法的作业完成时间要远远少于公平调度算法，这主要是由于本文算法通过数据挖掘技术对作业完成时间进行预估，可以选择最优云计算资源完成作业，得到更优的云计算作业调度方案，加快云计算作业完成的时间。
文算法更能适应云作业调度问题的求解，具有显著的优越性。
4 结 语
作业调度是云计算系统的一项关键技术，针对当前云作业调度算法效率低的不足，提出基于数据挖掘的混合云作业调度算法。首先建立云作业调度的目标函数，然后采用数据挖掘技术对目标函数进行求解，最后在CloudSim环境下对算法的性能进行验证，实验结果表明，本文算法不仅可以获得使用户满意的混合云作业调度方案，且具有较好的实际应用价值。
参考文献
[1] BUYYA R， YEO C S， VENUGOPAL S， et al. Cloud compu?ting and emerging IT platforms： vision， hype， and reality for delivering computing as the 5th utility [J]. Future generation computer systems， 2009， 25（6）： 599?616.
[2] 张建勋，古志民，郑超.云计算研究进展综述[J].计算机应用研究，2010，27（2）：429?433.
[3] 陈全，邓倩妮.云计算及其关键技术[J].计算机应用，2009，29（9）：2562?2567.
[4] ONCHAGA Richard. Quality of service management framework for dynamic chaining of geographic information services [J]. International journal of applied earth observation and geoinformation， 2006（8）： 137?148.
[5] SOTOMAYOR B， MONTERO R， LLORENTE I， et al. Virtual infrastructure management in private and hybrid clouds [J]. IEEE Internet computing， 2009， 13（5）： 14?22.
[6] CALHEIROS R N， RANJAN R， BELOGLAZOV A， et al. CloudSim： a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms [J]. Software practice & experience， 2011， 41（1）： 23?50.
[7] 左利云，左利锋.云计算中基于预先分类的调度优化算法[J].计算机工程与设计，2012，33（4）：1357?1361.
[8] 李建锋，彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用，2011，31（1）：184?186.
[9] 申丽君，刘丽，陆锐.基于改进免疫进化算法的云计算任务调度[J].计算机工程，2012，38（9）：208?210.
[10] 杨海军.云计算环境下人工蜂群作业调度算法设计[J].数学的实践与认识，2012，42（10）：115?120.
[11] 刘颖，甘泉，王宇.混合云环境中改进的工作负载分配方案[J].电信科学，2015，24（1）：77?81.
摘 要： 针对当前云作业调度算法效率低的不足，为了获得理想的云作业调度结果，以便给用户提供更好的服务质量，提出基于数据挖掘的混合云作业调度算法。对混合云作业调度的原理进行分析，指出当前云作业调度算法性能差的原因，建立云作业调度的目标函数，并采用数据挖掘技术找到最理想的混合云作业调度方案。在CloudSim环境下，通过具体混合云作业调度实验对算法的性能进行验证。结果表明，该算法不仅大幅度提高了混合云作业调度的成功率，而且加快了混合云作业完成的时间，具有较好的实际应用价值。
关键词： 云计算系统； 作业调度； 完成时间； 数据挖掘； 服务质量
中图分类号： TN911?34； TP393 文献标识码： A 文章编号： 1004?373X（2017）19?0049?03
Hybrid cloud job scheduling algorithm based on data mining
MA Wen， GENG Zhenwei， ZHANG Lina
（Information Center of Yunnan Power Grid Co.， Ltd.， Kunming 650217， China）
Abstract： Aiming at the low efficiency of the current cloud job scheduling algorithms， a hybrid cloud job scheduling algorithm based on data mining is proposed to obtain the ideal cloud job scheduling results and provide better service quality for users. The principle of the hybrid cloud job scheduling is analyzed. The reason why the current cloud job scheduling algorithm has poor performance is pointed out. The objective function of cloud job scheduling is established. The data mining technology is used to seek out the most ideal hybrid cloud job scheduling scheme. The performance of the algorithm was verified by means of the specific hybrid cloud job scheduling experiment in CloudSim environment. The results show that the proposed algorithm can improve the success rate of the hybrid cloud job scheduling greatly， and speed up the completion time of the hybrid cloud job， which has high practical application value.
Keywords： cloud computing system； job scheduling； completion time； data mining； service quality
0 引 言
云计算是一种新的计算模式，主要用于解决大规模数据处理问题，集成了计算机、通信、模式识别等技术，通过Internet进行资源共享，用户可以通过平台申请自己的资源，完成相应的任务，具有价格低、灵活、通用性强等特点，在许多领域得到了成功的应用[1?2]。根据云规模大小，可以划分为私有云、公有云和混合云三种类型，其中混合云是公有云和私有云的综合，其实际应用价值更高，已经成为云计算将来的发展方向[3]。
在混合云的实际应用中，由于每一类用户对云计算资源的需求不同，如何快速、有效地完成用户提交的混合云作业，为用户提供高质量的服务，显得尤为重要，成为当前云计算系统研究中的热点[4]。为了解决云计算混合云作业调度问题，一些学者进行了深入研究，当前有许多计算作业调度算法[5]。最初采用公平调度算法实现云计算混合云作业调度，对于规模较小的云计算混合云作业调度问题，可以获得理想的云计算混合云作业调度方案，当云计算混合云作业调度问题规模较大时，求解速度很慢，而且难以获得最优的云计算混合云作业调度方案，尤其对于超大规模的云计算混合云作业调度问题，无法顺利求解[6]。为此有学者采用启发式算法，如粒子群算法等，它们将云计算作业调度问题看作启发式算法求解的目标，通过不断搜索找到云计算作业调度最优或者次优方案[7?9]，求解效率明显要高于公平调度算法，然而云计算作业调度属于NP难题，当云计算作业调度问题的规模较大时，它们性能急剧下降，求解时间相当长，无法满足云计算作业在线调度要求，也不能满足用户服务的实时性，同时这些算法只是简单针对公有云和私有云的作业调度问题，当前混合云作业调度的研究很少[10?11]。
针对混合云作业调度问题，提出基于数据挖掘的混合云作业调度算法。首先对云计算系统的作业调度原理进行分析，并描述混合云体系结构；然后建立混合云作业调度的目标函数，采用数据挖掘技术进行求解；最后在CloudSim环境下实现仿真实验，验证其有效性。
1 云计算系统以及混合云的架构
1.1 云计算系统的构架
云计算系统通过Internet将不同地点、不同区域的单台计算机资源连接起来，计算机资源主要包括CPU、存儲器、网络带宽等，它们组成一个庞大的计算机系统，采用分布式方式给用户提供相应的资源，用户通过自己的具体要求分配到相应的资源，从而完成自己的作业，具体架构如图1所示。
1.2 混合云的架构
混合云采用一定技术将私有云和公有云组合在一起，基本架构如图2所示。其中私有云主要控制隐私数据，保密性高，但单一的私有云有其局限性，无法全面提供给用户满意服务，因此公有云是私有云的有益补充，可扩展性更好。
2 混合云作业调度算法
2.1 混合云作业调度的目标函数
在实际应用中，云作业规模很大，单采用一个云计算节点无法正常完成，因此需要对云作业进行分解，划分为多个子作业，根据每一个子作业特点分配相应的资源节点。当全部子作业都完成后，通过管理节点将它们组合在一起，将最终结果反馈给用户。云作业通常采用Map/Reduce模式，通过Map和Reduce函数实现用户作业的调度，Map/Reduce工作原理如图3所示。
Map/Reduce完成混合云作业的步骤如下：
（1） 用户提交作业，每一个作业根据其特点划分为多个子作业（work），那么作业[t]的运行时间[TaskTt]为：
[TaskTt=maxj=1NomWM（i，j）+x=1NorWR（k，x）] （1）
式中：[WM（i，j）]为第[j]个子任务所需的时间；Nom和Nor表示作业在队列中的次序。
（2） 混合云作业调度目标，保证用户提交的作业总完成时间[T1]和平均完成时间[T2]尽可能最小，同时满足用户要求，则有：
[T1=mint=1NumTTaskTt] （2）
[T2=min1NumTt=1NumTTaskTt] （3）
综上可知，混合云作业调度的目标函数可以写为：
[T=mint=1NumTTaskTt+min1NumTt=1NumTTaskTt] （4）
为了给每一子作业分配合理的云资源，尽可能加快作业的完成时间，采用数据挖掘技术对作业完成的时间进行预测，根据预测结果分配相应的云计算资源。
2.2 数据挖掘技术
对于训练样本[xi，yi，]采用数据挖掘对其变化特点进行分析，可以建立如下的回归函数：
[f（x）=ωT?（x）+b] （5）
对式（5）进行适当转换，得到一个如下的约束条件：
[minω2+12Ci=1nξ2i s.t. yi-ωT?（x）+b=eii=1，2，…，n] （6）
式中[ei]为回归偏差。
通过拉格朗日乘子[αi]进行变换，得到其对偶形式为：
[L（ω，b，ζ，α）=minω2+12Ci=1nξ2i+i=1nαiωT?（x）-b+ei-yi] （7）
引入核函数[K（xi，xj）=?T（xi）?（xj）]，使得其可以求解非线性回归问题，核函数定义如下：
[k（xi，xj）=exp-xi-xj22σ2 ] （8）
因此，非线性回归问题的数据挖掘结果为：
[f（x）=i=1Nαiexp-xi-xj22σ2+b] （9）
2.3 数据挖掘技术的混合云作业调度算法
设云计算系统共有[m]个计算机资源[{v1，v2，…，vm}，]不同作业要求的服务不一样，导致需要的资源也不相同，因此本文用数据挖掘技术对作业的需求进行预测，具体工作步骤如下：
（1） 对于一个具体的云计算作业，收集与其相似的历史样本数据。
（2） 对历史样本数据进行聚类分析，选择与待完成云计算作业相似度较高的样本。
（3） 将聚类分析获得的样本输入到数据挖掘算法进行分析，通过学习确定最优参数，得到该云计算作业完成的预估时间。
（4） 根据云计算作业的预估时间，向云计算系统申请相应的资源。
（5） 计算该云计算作业实际完成的时间，并得到预估时间和实际完成时间之间的偏差。
（6） 如果偏差太多，返回步骤（2），直到偏差达到预先设置的要求为止，从而完成云计算作业调度。
3 仿真实验
3.1 仿真平台
为了分析基于数据挖掘的混合云作业算法的有效性，建立混合云实验平台，其参数具体如表1和表2所示，仿真软件采用CloudSim。
3.2 实验结果与分析
不同规模的云作业条件下，作业的平均完成时间和总完成时间如图4所示。对图4的实验结果进行对比分析可以发现，当作业规模增大时，作业完成时间延长，但本文算法的作业完成时间要远远少于公平调度算法，这主要是由于本文算法通过数据挖掘技术对作业完成时间进行预估，可以选择最优云计算资源完成作业，得到更优的云计算作业调度方案，加快云计算作业完成的时间。
文算法更能适应云作业调度问题的求解，具有显著的优越性。
4 结 语
作业调度是云计算系统的一项关键技术，针对当前云作业调度算法效率低的不足，提出基于数据挖掘的混合云作业调度算法。首先建立云作业调度的目标函数，然后采用数据挖掘技术对目标函数进行求解，最后在CloudSim环境下对算法的性能进行验证，实验结果表明，本文算法不仅可以获得使用户满意的混合云作业调度方案，且具有较好的实际应用价值。
参考文献
[1] BUYYA R， YEO C S， VENUGOPAL S， et al. Cloud compu?ting and emerging IT platforms： vision， hype， and reality for delivering computing as the 5th utility [J]. Future generation computer systems， 2009， 25（6）： 599?616.
[2] 张建勋，古志民，郑超.云计算研究进展综述[J].计算机应用研究，2010，27（2）：429?433.
[3] 陈全，邓倩妮.云计算及其关键技术[J].计算机应用，2009，29（9）：2562?2567.
[4] ONCHAGA Richard. Quality of service management framework for dynamic chaining of geographic information services [J]. International journal of applied earth observation and geoinformation， 2006（8）： 137?148.
[5] SOTOMAYOR B， MONTERO R， LLORENTE I， et al. Virtual infrastructure management in private and hybrid clouds [J]. IEEE Internet computing， 2009， 13（5）： 14?22.
[6] CALHEIROS R N， RANJAN R， BELOGLAZOV A， et al. CloudSim： a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms [J]. Software practice & experience， 2011， 41（1）： 23?50.
[7] 左利云，左利锋.云计算中基于预先分类的调度优化算法[J].计算机工程与设计，2012，33（4）：1357?1361.
[8] 李建锋，彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用，2011，31（1）：184?186.
[9] 申丽君，刘丽，陆锐.基于改进免疫进化算法的云计算任务调度[J].计算机工程，2012，38（9）：208?210.
[10] 杨海军.云计算环境下人工蜂群作业调度算法设计[J].数学的实践与认识，2012，42（10）：115?120.
[11] 刘颖，甘泉，王宇.混合云环境中改进的工作负载分配方案[J].电信科学，2015，24（1）：77?81.
