基于协同禁忌优化模式的云计算强安全约束工作流调度策略

同卫国，沙晓燕，冯德民

（1.陕西职业技术学院教育技术与实训中心，陕西西安710038；2.陕西师范大学计算机学院，陕西西安710065）

基于协同禁忌优化模式的云计算强安全约束工作流调度策略

同卫国1，2，沙晓燕1，2，冯德民2

（1.陕西职业技术学院教育技术与实训中心，陕西西安710038；2.陕西师范大学计算机学院，陕西西安710065）

针对当前广泛使用的云计算工作流调度方法过多侧重于可靠性和节能等方面的优化，而忽略安全性约束要求，基于协同禁忌算法设计了一种能实现云计算工作流高效调度的方法，该方法具有安全性约束。首先对云计算工作流调度的DAG图进行定义，形式化描述安全性约束，建立云计算工作流调度的数学模型；然后基于经典的协同禁忌算法设计解的编码方式、适应度函数、变邻域结构和双禁忌表，改进了经典的协同禁忌算法；对基于该协同禁忌算法实现对云计算工作流调度的算法进行定义；最后基于云计算仿真环境Cloud-Sim进行了实验，实验结果表明，所设计的算法收敛速度较快，且其较快地寻找到了相对于其他方法更佳的调度方案，符合安全性约束要求，是一种实用的调度方法。

工作流调度；虚拟机；安全性约束；云计算

0　引言

云计算主要是基于并行计算等形成的[1-3]，到目前为止，相对于并行系统来说，云计算可以提供相对较高的可靠性，然而其仍然面临许多难题，例如无法在充分确保服务质量的基础上，减小其运行费用和能耗，使提供商可以获得尽可能高的收益[4-6]。

对于云计算工作流来说，诸多因素能够影响到其调度效率，具体来说，主要包括调度的可靠性、硬件性能等诸多方面[7]。现阶段，业界对其调度的探讨一般集中在可靠性与节能两个层面，例如，文献[8]在研究过程中以可靠性为基础，阐明了相应的调度方法，以降低传输所需用时，改善成功率，使其可靠性有所提升。文献[9]在研究过程中量化了网络资源属性，这样在调度过程中可以选取性能相对较高的资源类簇，能够进一步减少任务的匹配用时。文献[10]在研究过程中通过相关方法整合任务路径优化选择。除此之外，文献[11]在研究过程中根据QQS需求划分优先级，将资源分配给高优先级的任务。

上述理论成果集中在云计算工作流调度方面，却没有兼顾到安全性约束，鉴于这一方面的原因，本文阐明了基于安全性约束的云计算流调度方法，希望能够为业界人士提供指导和借鉴。

1　云计算工作流调度DAG图

主要通过有向无环图（Direct Acirclic Graph，DAG）表示任务结构，具体见图1。

图1　工作流调度DAG图

通过图1得知，DAG图能够通过二元组描述DAG={T,E}，在这里：

（1）T={t1,t2,…,tn}用来指代DAG里面的节点集，即子任务集，n=|T|用来指代任务数，W(ti)指代ti的计算量；

（2）E={} eij=(ti,tj),eij∈T×T是有向边集合，用来指代ti与tj两者之间存在的依赖关系，tj一定要等到ti结束以后才可以进行处理。

通过C指代任务相互间的通信关系C= {cij=(ti,tj),cij∈T×T}，cij用来指代ti与tj分配至资源上时需要的通信量，如果ti与tj两者分配至一个资源上，在这种情况下则有cij=0。

Pred(ti)={ti|tj∈T,eij∈E}，Succ(ti)={ti|tj∈T,eij∈E}，两者分别用来指代ti的前驱任务集与后继任务。

2　基于DAG和安全性约束的工作流调度

2.1工作安全性约束

按照所用方法的安全性强度，能够把虚拟机分成不同级别的安全性，按照操作的敏感性，主要通过r-risk型技术进行控制，具体来说，也就是在调度工作流过程中，设置其冒险水平阈值τ，安全等级比τ高的虚拟机能够分配资源。接下来进行建模，具体如下：

（1）单一的ti符合安全性约束的分配：它的τi分配的虚拟机及其安全性级别分别是vj与sj，如果sj≥τi，在这种情况下这个虚拟机符合相关条件，能够向ti分配。比如就安全需求是3的操作来说，能够向vj≥4的虚拟机分配。

（2）DAG符合安全性约束的调度：T={t1,t2,…,tn}的分配方案的风险概率P={p1,p2,…,pn}，能够利用以下公式进行求解：

如果p(risk)比一切任务的τi大，在这种情况下，P={p1,p2,…,pn}符合相关要求。

2.2数学模型的定义

就任何一项任务来说，它的操作时间主要包括两方面内容：其一为接收信息的用时；其二为把任务向相应的虚拟机分配的用时。就任何一个任务来说，符合相关要求的虚拟机集用M来指代，它的操作时间用Finishi表示，具体能够利用以下公式进行求解：

式中：对于当前节点，max Finishprei用来指代其任何一个前驱节点完成用时的极值；Cmi用来指代其需输送的数据量；Li用来指代其工作量；Pi用来指代其分配到的虚拟机的处理速度；banij用来指代发出信息和分配至目的地的两个虚拟机间的带宽大小。

耗时最大的任务用时是全部任务完成时间，也就是：

3　基于禁忌优化算法的工作流调度

3.1禁忌优化算法

为有效避免算法在运行过程中止步于局部最优，禁忌优化算法主要是通过禁忌表对那些得到的局部最优解进行存储，在此基础上设定其禁忌长度，当再次进行搜索时，通过表里面存储的数据决定将这些点跳过，最终能够避免局部最优。另一方面，该算法也可以按照藐视准则将那些被禁忌的优良状态赦免，选取其中的最优解，从而得到全局最优解。较具代表性的禁忌算法示意图，如图2所示。

图2　传统禁忌算法流程框图

3.2解的编码方式和适应度函数

通过P={p1,p2,…,pn}指代当前解，其中的各元素pi指代ti分配的vi，所以DAG工作流的编码长度即为该用户任务的子任务总数n。

所谓适应度函数，是指禁忌算法在找寻最优解时最大化目标函数，公式（4）为最小化式（3）重描述的DAG的任务完成时间：

3.3邻域结构设计

图2中，在候选解的生成过程中，必须构建邻域结构，在这里若邻域解与当前解两者存在明显的差异，在这种情况下，将变成随机搜索，另一方面，变化相对较小将导致收敛速度下降，或许将止步于局部最优，鉴于这一方面，必须提前设计科学有效的邻域结构，这样一方面可以充分确保获得最优解，另一方面还可以提高收敛速度。

设基本邻域结构如下所示：对当前任务节点，任选1个虚拟机（符合安全性约束要求），通过这种方式能够避免陷入随机搜索，能够在科学有效的区间寻求新解，为避免陷入早熟，构造2种变邻域结构，在完成设定的迭代次数以后，若所获当前解的适应度仍然没有出现大幅的改进，在这种情况下将会分别通过下文中的结构1与2形成新解。

变邻域结构1：自当前解每次形成1个候选解，能够利用重复对基本邻域结构进行S次调用实现；

变邻域结构2：在解释当前解产生邻域的过程中，必须将其周围的2S区域中全部节点的虚拟机编号改变。

3.4基于改进禁忌优化的工作流调度算法

具体来说，该种方法的具体过程如下所示：

输入：T={t1,t2,…,tn}（用来指代全部任务集），rmax（是指最优解最大没有改变的次数），V={v1,v2,…,vn}（用来指代当前虚拟机集合），S（参考值），L（禁忌表长度），K（候选集元素个数），T（算法最大迭代次数），M，N（两者分别用来指代Sselected与Sneighbor的元素个数最大值）；

输出：全局最优解best-far；

step1：随机产生符合相关要求的解，将其当作当前解xcur，初始化best-far=xinitial，最优解未变化次数r=1，当前迭代次数t=1；

step2：把xcur与移动量(0,0)分别置于禁忌表TB与TW里面，设定禁忌长度是L；

step3：判定t≤T成立与否：若t≤T成立，在这种情况下就会结束该算法，然后将best-far输出；否则t=t+1；

step4：按照在3.3节中提出的邻域结构生成xcur的Sneighbor，一直至Sneighbor里面有N个元素结束，从中取K个最优解，将它们作为候选解，在此基础上，加入Sselected；

step5：把Sselected里面的Sselected-best和best-far进行对比：

假如Sselected-best没在禁忌表里面，在这种情况下，把Sselected-best加到TB中，并且设定它的禁忌长度是L，把它的移动方式加到TW中，同时，设定其余元素的禁忌长度是-1；

否则取没有被禁忌的下一较优候选解4当作xcur，然后把它加至禁忌表中，把它的移动方式加到TW中，对其余元素进行更新，使其禁忌长度是-1；

step6：t=t+1，在此基础上，重新从step3开始。

4　仿真实验

实验环境为Cloud Sim[12]，图3为工作流任务实例，在这里，为了能够和文献[13]的方法进行对比分析，此处选择的参数都和文献[13]的设置相同，椭圆中是指各子任务，工作量均匀分布在区间[50,500]中，总共有4个虚拟机，相互间的带宽矩阵具体如下：

全部的任务中，只有第6个τ是4，剩下的都是2，安全性等级依次为：2，2，3，4。

相关参数主要包括：rmax=4，L=4，S=1，N=5，M=3，T=200，K=6。

图3　工作流任务实例

以图3为实例，通过将本文提出的算法、文献[11]和[13]提出算法的结果相对比，获得各个算法的收敛图，如图4所示。

图4　3种算法收敛曲线对比

通过图4能够得知，本文所提出的算法在140代收敛，其工作流调度用时是178.4，后面2个算法的用时依次是195.1与210，文献[11]提出的算法在仿真过程中均未达到收敛，但文献[13]的方法在180代达到收敛，然而并未获得全局最优解，通过对比可以看出，本文提出的算法一方面其收敛速度相对较好，另一方面还能够获得更优解。

进一步验证三者对约束的敏感状况，具体测试结果见图5。

图5　有无安全性约束的平均完成时间

通过图5能够得知，本文所提出的算法与文献[13]提出的方法充分兼顾到安全性约束，另一方面，在有无约束时的平均用时具有相对偏小的差异，值得注意的是，文献[11]提出的方法并未兼顾到相关约束，正是这一方面的原因，所以，该方法无法妥善处理安全型约束的云工作流调度问题。

5　结语

综上所述，为科学调度云计算中的任务，必须妥善处理的第一个环节即工作流调度，针对该问题，本文提出了基于安全型约束的云计算工作流高效调度法。构建了相应的调度模型与目标函数，在此基础上，通过协同禁忌算法进行寻优。最后，本文还在Cloud Sim环境平台下开展相应的仿真实验，结果说明提出的新方法的效果相对较好，一方面其收敛速度相对偏高，另一方面其可以获得相对较优的解。

[1]DU Z H，HU J K，CHEN Y N，et al.Optimized QoS-aware replica placement heuristics and applications in astronomy data grid[J].Journal of systems and software，2011，84（7）：1224-1232.

[2]厉剑.云计算安全问题分析[J].现代电子技术，2013，36（19）：91-94.

[3]刘少伟，孙令梅，任开军，等.云环境下优化科学工作流执行性能的两阶段数据放置与任务调度策略[J].计算机学报，2011，34（11）：2121-2130.

[4]陈良维.云计算环境下的网络安全估计模型态势仿真[J].现代电子技术，2015，38（20）：15-19.

[5]VAQUERO L M，RODERO-MERINO L，MORAN D.Locking the sky：a survey on IaaS cloud security[J].Computing，2011，91（1）：93-118.

[6]MALIK S，HUEF F，CAROMEL D.Reliability aware scheduling in cloud computing[C]//Proceedings of 2012 International Conference for Internet Technology and Secured Transactions.Piscataway：IEEE press，2012：194-200.

[7]KANG Q，HE H，WEI J.An effective iterated greedy algorithm for reliability-oriented task allocation in distributed computing systems[J].Journal of parallel and distributed computing，2013，73（8）：1106-1115.

[8]闫歌，于炯，杨兴耀.基于可靠性的云计算工作流调度策略[J].计算机应用，2014，34（3）：673-677.

[9]储雅，马廷淮，赵立成.云计算资源调度：策略与算法[J].计算机科学，2013，40（11）：8-13.

[10]胡蒙，苑迎春，王雪阳.改进模糊聚类的云任务调度算法[J].计算机工程与设计，2015，36（9）：2437-2441.

[11]孙月，于炯，朱建波.云计算中一种多DAG工作流可抢占式调度策略[J].计算机科学，2014，41（3）：145-148.

[12]王宇宾.基于CloudSim的作业调度算法评价模型设计与实现[J].现代电子技术，2015，38（14）：12-15.

[13]马俊波，殷建平.云计算环境下带安全约束的工作流调度问题的研究[J].计算机工程与科学，2014，36（4）：607-614.

Cooperative taboo optimization mode based cloud computing workflow scheduling strategy for strong security constraint

TONG Weiguo1，2，SHA Xiaoyan1，2，FENG Demin2
（1.Education Technology and Training Center，Shaanxi Vocational&Technical College，Xi’an 710038，China；2.School of Computer Science，Shaanxi Normal University，Xi’an 710065，China）

The widely-used cloud computing workflow scheduling method focuses on the optimization of reliability and energy saving，but ignores the requirement of security constraint，so a method based on cooperative taboo algorithm is proposed here，which can realize the high-efficient cloud computing workflow scheduling，and has security constraint.The DAG of cloud computing workflow scheduling is defined to describe the security constraint with formalization，and establish the mathematical model of the cloud computing workflow scheduling.On the basis of using the classical cooperative taboo algorithm，the coding scheme，fitness function，varying neighbourhood structure and dual taboo tables of the solution are designed，and the classical cooperative taboo algorithm is improved.The cloud computing workflow scheduling algorithm based on an improved cooperative taboo algorithm is defined.The experiment of the algorithm was conducted in the simulation environment Cloud-Sim.The experimental results prove that the designed algorithm has fast convergence speed，can find a much better scheduling scheme than other algorithms can do，meets the requirements of security constraint，and is a practical scheduling method.

workflow scheduling；virtual machine；security constraint；cloud computing

TN915-34

A

1004-373X（2016）21-0011-04

10.16652/j.issn.1004-373x.2016.21.003

2016-01-06

国家自然科学基金面上项目（61173190）

同卫国（1977—），男，陕西渭南人，工程师。研究方向为云计算与互联网应用。

沙晓燕（1972—），女，陕西西安人，教授。研究方向为多媒体技术及应用。

冯德民（1955—），男，陕西西安人，教授。研究方向为云计算应用。