欢迎访问一起赢论文辅导网
博士论文
当前位置:首页 > 博士论文
考虑信息安全因素的多目标云工作流调度
来源:一起赢论文网     日期:2018-10-28     浏览数:55     【 字体:

  叶 鑫 等:考虑信息安全因素的多目标云工作流调度化调度问题[4]、考虑一定预算约束下的所有工作流实例执行结束时间最小化调度问题[5],以及考虑虚拟机性能约束下的所有工作流实例执行结束时间最小化调度问题[6]。另外,针对某些实际场景,工作流调度也可能需要考虑多个目标,如执行结束时间和费 化[7]、执 小化[8]等。然而,现有的云工作流调度研究中,考虑信息安全与隐私性保护因素的研究较少。由于云计算环境具有复杂性、开放性和动态 性特点,多用户动态租用、共享高度集中的资源且数据的传输完全依赖于网络,当存在不同程度信任关系的用户间动态共享同一计算资源时,可能降低安全的可控性[9];另外,在云计算服务模式下,云服务的透明性使用户失去对数据的控制,数据安全问题成为隐患。因此,某些场景下的云工作流调度问题对信息安全性提出了更高的要求,如何协调多种信任关系、保护用户数据和隐私安全,以及在保证云工作流调度性能的同时降低信息安全风险,值得深入研究。在现有的考虑信息安全与隐私性保护的云工作流调度研究中,Liu等[10]指出每台计算资源有一个安全服务水平等级、工作流中的每个任务也有一个相应的安全需求水平等 级,并提出 种安全模型。在模型中,计算节点提供安全服务时会产生与信息安全有关的时间开销;Xie等[11]认为在异构分布系统环境下,每个任务都有认证性、机密性、完整性 3种安全服务的需求,并提出一种安全驱动的启发式调度算法,使任务在执行过程中尽量满足各自的信息安全需求;白晶晶[9]考虑了云环境下用户的安全需求,提出一种安全和可靠性驱动的云任务调度算法,并将调度过程分为预备和正式调度两个阶段。上述研究作为本文的研究基础,仍存在如下不足需要改进:①多考虑单个目标或将多个目标转化成一个目标,然而多目标优化可以平衡多个目标之间的关系,并能得到多个优化结果,供决策者根据其偏好进行决策,因此采用多目标优化更具实际意义;②在任务执行所产生的信息安全风险概率的衡量方面,没有给出无决策偏好时各信息安全指标的权重确定方法,可以根据任务的安全需求水平和虚拟机能够提供的安全服务水平等客观实际情况,采用熵权法确定各信息安全指标的权重;③多采用启发式算法或元启发式算法进行求解[12-14],当解空间很大时优化效果不甚理想,因此可以将启发式规则融入元启发式算法中形成混合启发式算法[11],以提升优化效果[15]。为解决上述问题,本文首先构建了云计算环境下考虑信息安全因素的工作流调度模型,然后提出两种启发式规则并对应用较广泛的一种多目标优化算法———改进的 非 支 配 排 序 遗 传 算 法 (Non-domi-nated Sorting Genetic Algorithm,NSGA-Ⅱ)进行了改进,最后进行了实验及结果分析。1 考虑信息安全因素的云工作流调度模型考虑云工作流执行过程中的保密性(Confiden-tiality)、完 整 性 (Integrity)和 真 实 性 (Authentica-tion)3个信息安全指标[16],首先给出工作流模型、计算资源模型,以及信息安全服务的时间开销与信息安全风险模型,然后以多工作流实例的所有任务执行结束时间最小化和信息安全风险最小 化为目标,构建云工作流调度模型。1.1 考虑信息安全因素的工作流模型工作流中的任务及其间的偏序关系可用有向无环图(Directed Acyclic Graph,DAG)来描述,即可以抽象为一个三 元 组 G=(T,E,SR)。其 中:T={task1,task2,…,taskq}表示工作流所包含的任务集合,q表示任务的数量。E∈T×T 表示这些任务之间的依赖关系集合,eij∈E 表示taski与taskj之间的依赖关系,即taskj必须在taski执行结束后才能开始执行。具有依赖关系的任务间存在数据传输,若这两个任务被分配在不同计算资源上执行,则存在数据通讯时间,记为 CT(taski,taskj);若这两个任务被分配在同一计算资源上执行,则通讯时间为0。SR={SR1,SR2,…,SRq}表示任务对信息安全需求的集合。此外,没有任何紧前任务的任务称为初始任务,记为taskentry;没有任何紧后任务的任务称为结束任务,记为taskexit。数据偷窥、数据更改和电子欺骗是云计算环境中常见的3种攻击方式,因此工作流中的全部任务或某些任务可能具有保密性、完整性和真实性3种安全需求。一般应用加密算法来实现保密性,应用hash算法来实现完整性,应用数字签名和身份验证来实现真实性[15]。令 SRj=(sraj,srgj ,,srdj)表示任务taskj对 保 密 性、完 整 性 和 真 实 性 的 需 求 水 平。为了便于计算,每个指标的信息安全需求水平取值标准化为[0,1],值越高表示对相应指标的信息安全需求越高。793计算机集成制造系统 第23卷1.2 考虑信息安全因素的计算资源模型虚拟机是云计算环境中工作流及其任务执行的载体,其通过网络连接,具有全连通性。虚拟机集合可以表示为VM ={vm1,vm2,…,vmm},其中 m 为虚拟机的数量。不同的虚拟机可能具备不同的计算能力和安全服务水平。令VMC={vmc1,vmc2,…,vmcm}表示不同虚拟机的计算能力集合,SP={SP1,SP2,…,SPm}表示虚拟机能够提供的安全服务水平集合。其中SPk=(spak,spgk,spdk)表示虚拟机vmk能够提供的保密性、完整性和真实性3个指标的信息安全服务水平。同样,为了便于计算,这些指标也标准化取值为[0,1],取值越大,其所提供的信息安全服务水平越高。1.3 信息安全服务的时间开销与信息安全风险模型(1)信息安全服务的时间开销针对云计算环境下的工作流调度问题,考虑信息 安 全 因 素 将 不 可 避 免 地 带 来 相 应 的 时 间 开销[17-18]。为了不失一般性,保密性、完整性和真实性3种信息安全服务带来的时间开销分别为[19]:SOajk=lj/a(vmk,taskj); (1)SOgjk=lj/g(vmk,taskj); (2)SOdjk=φd(vmk,taskj)。 (3)式中:SOajk,SOgjk和SOdjk分别表示任务j在虚拟机k上执行时的保密性服务、完整性服务和真实性服务的时间开销;lj表示执行任务j时所涉及的需保证保密性、完整性的数据量;a(vmk,taskj),g(vmk,taskj)和φd(vmk,taskj)分别表示任务j在虚拟机k上执行时相应的保密性、完整性和真实性安全服务水平与计算开销的映射关系。任务j在虚拟机k 上执行时的信息安全服务总时间开销SOjk =∑l∈(a,g,d)SOljk(vmk,taskj)。 (4)(2)信息安全风险模型若任务j在虚拟机k 上执行,则当任务j 的安全需求水平大于虚拟机k 能够提供的安全服务水平即srlj>splj,l∈(a,g,d)时,存在一定概率的信息安全风险。令sdljk=srlj-splk表示任务j在虚拟机k 上执行时在信息安全指标l 方面的需求满足程度,则该任务执行的信息安全风险概率pljk可表达为sdljk的函数。假设风险在固定的时间间隔内服从泊松分布,则相应的风险概率可以由一个指数分布表示为pljk=0, srlj ≤splk;1-e-βsdljk, srlj >splk烅烄烆。(5)式中β为风险系数,当srlj>splk时,sdljk的值越大,相应的风险概率越大。任务j在虚拟机k 上执行的总体信息安全风险概率pjk =∑l∈(a,g,d)wlj·pljk。 (6)式中 wlj表示任务j针对信息安全指标l 的风险概率权重,满足0≤wlj≤1且∑l∈(a,g,d)wlj=1。每一个任务在不同虚拟机上执行时,某一信息安全指标下的风险概率可能存在差异。若这一差异较大,则对该任务到虚拟机的分配决策提供的信息价值较大,该指标应赋予较大的权重;若这一差异不大,则对其决策提供的信息价值较小,该指标应赋予较小的权重。熵权法是一种在没有决策偏好的情况下,根据评价指标构成的特征值矩阵来确定指标权 重的方法[20],因此可用熵权法确定 wlj。每个任务 都可以分配在 m 台虚拟机上执行,即有 m 个分配方案。由于每个任务分配至虚拟机上执行时需尽可能满足信息安全需求,可将保密性、完整性和真实性作为分配方案的3个评价指标。某一指标的熵值越大,其权重越小;熵值越小,其权重越大。针对某一任务j,可构建评价方案的特征值矩阵A=(Akl)m3(k=1,2,…,m;l=1,2,3),其中每一列表示该任务在不同虚机上执行时每一个安全指标的需求满足度,每一行表示该任务到虚拟机的一个分配方案。因为srl-spl≤0时虚拟机提供的安全服务水平可满足任务的安全需求、不会产生风险,所以将安全需求满足度为负数的元素均替换成 0,从而得到矩阵A。进一步对矩阵A 进行归一化,得到相对优属矩阵R=(rkl)m3。rkl =sup(Akl)-Aklsup(Akl)-inf(Akl)。 (7)式中sup(Akl)与inf(Akl)分别为矩阵A 中第l列元素的最大值和最小值。信息安全指标l的熵定义为Hl =-∑mk=1fkllnfklln m,fkl =1+rkl∑mk=1(rkl+1)。 (8)则针对任务j,信息安全指标l的权重wlj=1-Hl1-H1 +1-H2 +1-H3。 (9)794 叶 鑫 等:考虑信息安全因素的多目标云工作流调度1.4 云工作流调度模型本文研究的云工作流调度问题可以表示为:有n个工作流实例(I1,I2,…,In),每个工作流实例有q个任务,可在 m 台虚拟机上执行;工作流中的任务间存在一定的偏序关系,每个任务可以在所有的虚拟机上执行;每个任务在不同的虚拟机上执行的时间长度和风险概率有可能不同;若具有偏序关系的两个任务被分配在不同的虚拟机上执行,则这两个任务间的数据传输存在通讯时间;调度的目标是分配所有工作流实例的所有任务到合适的虚拟机上执行,使得所有任务的执行结束时间最小化和信息安全风险概率最小化。本文遵循如下云计算环境下工作流调度问题中最常见的假设条件:(1)若任务被分配到某一台虚拟机上执行,且该任务执行所需数据已到达该虚拟机,则只要该虚拟机空闲,该任务应立即执行,不可以延迟执行。(2)每一台虚拟机在同一时刻只能执行一个任务。(3)每一个工作流实例中的每一个任务只能在一台虚拟机上被执行一次。(4)若某任务开始执行,则在其执行期间不能有间断。(5)若两个任务间存在数据的网络通讯,则其通讯时间是关于传输数据量的函数。相关符号定义如表1所示。表1 符号及其定义符号 含义Ii 第i个工作流实例IiTj 第i个工作流实例的第j 个任务Tjk 任务j在虚拟机k 上的执行时长pre(i,j) IiTj 的紧前任务集合exec(k) 虚拟机k上执行的任务集合VATijk 虚拟机k针对IiTj 的可用时刻DATijk IiTj 执行所需数据到达虚拟机k 的时刻STijk IiTj 在虚拟机k 上开始执行的时刻FTijk IiTj 在虚拟机k 上执行的结束时刻αj′j 存在偏序关系的两个任务间的通讯时间θijk 0-1变量,θijk=1表示IiTj 分配在虚拟机k 上执行LVTk 虚拟机k上最后一个任务的执行结束时刻srlj任务j的第l个安全指标的安全需求水平splk虚拟机k所提供的第l个安全指标的安全服务水平SOjk 任务j在虚拟机k上执行时的信息安全服务的总时间开销plijkIiTj 在虚拟机k 上执行的第l个安全指标的风险概率wlj任务j的第l个安全指标风险概率的权重Pijk IiTj 在虚拟机k 上执行的总风险概率根据上述问题和符号定义,建立云工作流调度优化模型如下:f1 = maxk∈[1,m](LVTk); (10)f2 =∑ni=1∑qj=1∑mk=1θijkPijk; (11)min(f1,f2)。s.t.DATijk=0, taskj=taskentry,maxj′∈pre(i,j)(FTij′k′+αj′j(1-θij′k)),  taskj ≠taskentry烅烄烆 ;(12)VATijk =FTi″j″k; (13)STijk = max(DATijk,VATijk); (14)FTijk =STijk +Tjk +SOjk; (15)plijk=0 srlj ≤splk1-e-β(srlj-splk)srlj >spl烅烄烆 k,l∈ (a,g,d);(16)Pijk =∑l∈(a,g,d)wlj·plijk; (17)∑l∈(a,g,d)wlj=1,0≤ wlj ≤1; (18)∑mk=1θijk =1,θijk=0,1; (19)LVTk = maxe,f∈exec(k)(FTefk)。 (20)其中:式(10)表示所有任务的执行结束时间,其值为所有虚拟机上最后一个任务执行结束时刻 的最大值;式(11)表示调度方案的信息安全风险概率,其值为所有实例所有任务在所分配虚拟机上执行的信息安全风险概率之和;式(12)表示当工作流实例i的任务j被分配在虚拟机k 上执行时,其所需数据到达该虚拟机的时间:若任务j是初始任务即该任务没有前序任务,则其所需数据的传输时间为0;若任务j不是初始任务,则其所需数据到达该虚拟机的时间为所有前序任务集合中每一个任务的执行结束时间和其与任务j的数据通讯时间之和的最大值;若任务j与其某一个前序任务被分配在同一台虚拟机上执 行,则这 两 任务间的数 据 通讯时间 为 0;式(13)表示虚拟机k 可供IiTj(工作流实例i的任务j)执行的最早时间,其中 FTi″j″k表示调度方案中被分配在虚拟机k 上且在IiTj 之前执行的任务Ii″Tj″的执行结束时刻;式(14)表示IiTj 在虚拟机k 上的开始执行时刻,其值为其所需数据到达虚拟机k 的时刻和虚拟机k 针对该任务的可用时刻之间的最大值;式(15)表示IiTj 在 虚 拟 机k 上 的 执 行 结 束 时79506-30;修订日期:2016-08-28。Received 30June 2016;accepted 28Aug.2016.基金项目:中央高校基本科研业务费专项资金资助项目(DUT13JS11)。Foundation item:Project supported by the Fundamental Research Fundsfor the Central Universities,China(No.DUT13JS11).考虑信息安全因素的多目标云工作流调度叶 鑫,梁继伟,尹艳丽(大连理工大学 信息与决策技术研究所,辽宁 大连 116023)摘 要:为了满足云工作流调度需求的多样性,构建了考虑信息安全因素和多实例工作流执行时长的云工作流调度模型。该模型主要考虑了保密性、完整性与真实性3种信息安全因素的时间开销,以及无决策偏好情况下的信息安全风险概率度量。为了提升调度优化效果,提出工作流实例中任务调度的优先级确定规则和考虑信息安全因素的虚拟机分配规则,并将这两个启发式规则与 NSGA-Ⅱ算法相融合,对上述模型进行了优化求解。实验结果表明,所提算法可以较好地实现工作流执行结束时间与信息安全风险概率两个目标的平衡,亦可提高优化结果的质量。关键词:云计算;工作流调度;信息安全;多目标优化中图分类号:TP311   文献标识码:AMulti-objective cloud workflow scheduling considering information security factorsYE Xin,LIANG Jiwei,YIN Yanli(Institute of Information and Decision Technology,Dalian University of Technology,Dalian 116023,China)Abstract:To meet the diverse requirements of cloud workflow scheduling,a cloud workflow scheduling model con-sidering information security factors and execution time of multiple workflow instances was built.The measurementof information security risk probability without decision makerspreference and the time overhead of three securityfactors included confidentiality,integrity and authenticity were researched.For improving scheduling optimizationresult,the priority determination rule of task scheduling in the workflow instance and virtual machine allocation ruleconsidered security factor were proposed.These two heuristic rules and Non-dominated Sorting Genetic Algorithm(NSGA-Ⅱ)algorithm were combined to solve above model.The experiment results showed that the proposed algo-rithm not only could realize the balance of workflow execution time and information security risk probability better,but also improve the quality of optimization result.Keywords:cloud computing;workflow scheduling;information security;multi-objective optimization0 引言作为一种新的计算模式和商业模式,云计算的应用越来越广泛,它通过互联网将分布在不同物理位置的计算资源等共享起来,按需提供给用户使用。在云计算环境下,一些大型的应用通常由多个任务组成,这些任务具有相同的目标,在执行过程中存在时间偏序关系和数据依赖关系,从而构成了云工作流[1]。云工作流调度是指将工作流中的任务合理地分配到云计算资源上执行,同时满足资源约束条件和服务质量需求。近年来,有关云工作流调度的研究呈上升 趋 势,已 经 成 为 学 术 界 和 企 业 界 的 研 究热点[2-3]。目前,在云工作流调度研究中,针对不同场景、不同用户需求,所考虑的调度问题可能会不同,如考虑满足截止时间(deadline)约束下的执行费用最小计算机集成制造系统 第23卷刻,即该任务的开始执行时刻、执行时长和信息安全服务的时间开销之和;式(16)表示IiTj 分配在虚拟机k 上执行时,第l个信息安全指标的风险概率;式(17)表示IiTj 分配在虚拟机k 上执行时总的信息安全风险概率,其值为3种安全指标风险概率的加权求和;式(18)表示任务j的3种安全指标风险概率的权重之和等于1;式(19)表示IiTj 只能在一台虚拟机上执行一次;式(20)表示在虚拟机k 上执行的所有任务的结束时间最大值,即该虚拟机上最后一个执行任务的结束时刻。2 改进的 NSGA-Ⅱ算法云工作流调度问题是一个 NP 难问题[21],适于采用元启发式和混合启发式算法求 解。由 于 NS-GA-Ⅱ是一种基于遗传算法的多目标优化算法,被广泛应用且比较成熟,常用来求解两个目标的优化问题。因此,本文针对 所 提 出 的 调 度 模 型,对 NS-GA-Ⅱ算法进行了如下改进:①对经典 NSGA-Ⅱ算法中的染色体编码和一些操作算子进行了修改,使其满足云计算环境下工作流调度的特点和一些约束条件;②针对前述模型的两个目标函数提出两种启发式规则,即工作流中任务调度的优先级确定规则和考虑信息安全因素的虚拟机分配规则,将这两个启发式规则应用于种群初始化阶段,以提高算法的搜索效率并获得更优的解。2.1 编码与操作算子设计(1)工作流调度中个体的编码设计针对所提出的云工作流调度模型,一个染色体(个体)表示一个可能的调度方案,采用多层整数编码,如图1所示。当有n个工作流实例、每个工作流实例有q个任务分配在m 台虚拟机上执行时,染色体编码的长度为2nq+4。其中,前nq 位编码表示所有工作流实例的所有任务的调度顺序,nq+1~2nq位表示前面相应任务执行的虚拟机编号。染色体后四位分别表示所有任务的执行结束时间(第1个目标函数值)、信息安全风险概率(第2个目标函数值)、染色体所属的 Pareto前沿序号和拥挤距离。(2)基于二元锦标赛(binary tournament)的选择操作对种群进行二元锦标赛选择操作。随机选择两个不重复的个体,针对被选中的两个个体,优先选择前沿序值小的个体;当前沿序值相同时,为了保证种群多样性,保留拥挤距离值大的个体。(3)工作流任务编码的交叉操作在个体的任务编码位置即个体的前nq位,以概率pc对个体进行交叉操作。若对当前个体执行交叉操作,则从种群中随机选择一个个体,且不与当前个体重复,然后随机产生交叉位置pos∈[1,nq],对两个个体的1~pos位编码进行交叉操作。交叉后若某些工作流实例的任务存在冗余或缺失现象,则通过补缺操作来保证每个实例的任务满足相应工作流模型的要求。(4)虚拟机编码的变异操作在个体的虚 拟 机 编 码 位 置 即 个 体 的 nq+1~2nq位的基因,以概率pm发生变异操作。若执行变异操作,则任务以pqm的概率被变异到另一台虚拟机上,其中变异到计算速度快的虚拟机(任务执行时间短的虚拟机)上的概率较大。pqm(jk)=2maxE(j)-Tev(jk)∑k′∈V(2maxE(j)-Tev(jk′))。(21)式中:pqm(jk)表示任务j被变异到虚拟机k 上的概率,maxE(j)表示任务j在计算速度最慢的虚拟机上执行的时间,Tev(jk)表示任务j在虚拟机k 上执行的时间,V 表示任务j 可被分配的虚拟机的集合。2.2 两种启发式规则在经典的 NSGA-Ⅱ算法中,种群初始化是完全随机的。但当调度任务的数量增加时,个体的编码长度将随之变长,解空间也随之变大。此时,元启发式算法的求解效率会降低,而且容易陷入局部最优。因此,针对所提调度模型提出如下两种相互独立的启发式规则,并融入算法的种群初始化阶段,以提高优化结果的质量。(1)工作流实例中任务调度的优先级确定规则由于工作 流 中 的 任 务 之 间 存 在 偏 序 关 系,前序任务 的 执 行 情 况 会 对 后 序 任 务 的 执 行 产 生 影响,从而影 响 整 个 工 作 流 的 执 行 时 长。 在 实 际 的工作流调度中,常使用任务优先调度的规 则,使优先级高的任务先被分配到虚拟机上执行,其 中 BR(bottom rank)值 排 序 法 经 常 被 使 用[22]。BR 值 排序法的主要思想是计算所有任务到结束任 务的最796 叶 鑫 等:考虑信息安全因素的多目标云工作流调度长执行时间路径,然后选择 BR 值大的任务优先进行调度,但 该 方 法 不 能 很 好 地 针 对 具 有 大 量 并 行结构的工作流调度的场景。在具有并行执行关系的任务中,若 任 务i的 后 序 任 务 数 量 多 且 计 算 量大、任务j的后序任务少 且计 算量小,则相对于任务j,任务i应被优先调度。基于这一思想,本文对BR 值排序法进行改进(如式(22)),以使任务调度的优先级确定更合理。PBR(taskj)=1m∑mk=1Tjk,            taskj=taskexit;1m∑mk=1Tjk + sumtaskj′∈subsequent(taskj)1m∑mk=1Tj( )′k,   其他烅烄烆。(22)式中:Tjk表示任务j在虚拟机k 上执行的时间,m表示虚拟机的数量,subsequent(taskj)表示任务j的所有后序任务集合。当前任务的 PBR 值为其本身在各虚拟机上执行的平均时间及其后序所有任务在各虚拟机上执行的平均时间的累加和。PBR 值越大,该任务越应被优先调度。在种群初始化时,以 概 率pb应 用 该 启 发 式 规则,可以将 PBR 值大的任务优先编码,即优先进行调度,从而提升优化效果。(2)考虑信息安全因素的虚拟机分配规则下面针对信息安全风险概率目标越小越好的原则,提出一种考虑信息安全因素的虚拟机分配策略,以提高优化结果的质量和效率。基于所提 出 的 云 工 作 流 调 度 模 型,用 一 个 三元组Sjk=(sdajk,sdgjk,sddjk)表 示 任 务j在 虚 拟 机k上执行时的安全需求满足程度。当Sjk中的元素都大于等于0或者都小于等于0时,该任务的总体安全需求的满足程度可由式(23)直接计算得到。SDjk =∑l∈(a,g,d)wlj.sdljk,l∈ (a,g,d)。 (23)在Sjk中的元素既存在大于0又存在小于0的情况下,若sdljk<0,则令sdljk=0,表示在相应安全指标下不存在安全风险,然后基于式(23)计算任务的总体安全需求的满足程度。当有 m 台虚拟机可供任务执行时,任务j在不同虚拟机上安全需求的满足程 度可用集合SDj={SDj1,SDj2,…,SDjm}表示。为了使提供高安全服务水平的虚拟机不被过度占用,同时有效降低任务执行的信息安全风险,提出如下考虑信息安全因素的虚拟机分配规则:规则1 若 SDj中的元素都大于等于 0,即该任务在任何一台虚拟机上执行都有可能产生风险,则任务j分配到SDj中最小值的虚拟机上执行,以使任务调度的风险概率最低。规则2 若 SDj中的元素都小于等于 0,即该任务在任何一台虚拟机上执行都不会产生风险,则任务j分配至SDj中最大值的虚拟机上执行,以尽可能使提供高安全服务水平的虚拟机不被低安全需求水平的任务占用。规则3 若SDj中既存在大于0的元素又存在小于0的元素,则将SDj中取值小于等于0的元素构成的子集合记为SD′j,然后将任务j分配至SD′j中最大值的虚拟机上执行,以使任务被分配在不产生风险的虚拟机上执行,且不占用提供高安全服务水平的虚拟机。规则4 若SDj中的元素值均相等,则将任务随机分配至任一台虚拟机上执行。在种群 初 始 化 时,以 概 率ps应 用 该 启 发 式规则。2.3 改进算法的时间复杂度NSGA-Ⅱ算法在每一 代 种群 进 化过程 中 均 采用一种快 速 非 支 配 排 序 方 法,将 组 合 种 群 分 成 多层非支配前沿集 F,其时间复杂度为 O(N2),其中N 为 种 群 大 小[23]。 因 为 改 进 算 法 是 在 传 统 NS-GA-Ⅱ算法基础上,在种群初始化阶段加入上述两个启发式规 则,并 采 用 了 与 NSGA-Ⅱ 算 法 相 同 的非支配排序 方 法,所 以 其 时 间 复 杂 度 与 NSGA-Ⅱ算法相同。3 实验与结果分析3.1 实验设计为了比较改进 NSGA-Ⅱ算法与经典 NSGA-Ⅱ算法在优化结果方面的优劣,采用超体积 HV 指标进行评价。超体积是一种解集质量评估方法,可对解集的收敛性、均匀性和广泛性同时进行评价,并给出解集的综合评价结果[24]。在应用超体积评价优化结果的 质 量 时,若 一 个 解 集 S 优 于 另 一 个 解 集S′,则解集 S 的 HV 值应大于S′的 HV 值[25]。参与比较的算法的符号定义如表2所示。797计算机集成制造系统 第23卷表2 算法符号及含义符号标识 含义NSGA-Ⅱ 经典的 NSGA-Ⅱ算法NSGA-Ⅱ(P)结合任务调度的优先级确定规则的改进 NSGA-Ⅱ算法NSGA-Ⅱ(S)结合考虑信息安全因素的虚拟机分配规则的改进 NSGA-Ⅱ算法NSGA-Ⅱ(PS) 结合上述两种启发式规则的改进 NSGA-Ⅱ算法从工作流实例数量和虚拟机台数两个角度考虑云工作流调度场景,共设计9组实验。其中:工作流实例数量分别取值为5,10,20,虚拟机台数分别取值为3,6,9。因为针对不同实例数量的工作流调度算法的收敛速度不同,所以5个工作流实例的最终迭代次数为1 000,10个工作流实例的最终迭代次数为 2 000,20 个 工 作 流 实 例 的 最 终 迭 代 次 数 为3 000,其中每组实验均做了30次。另外,因为遗传算法每一次求解的种群初始化及各算子的执行都具有一定的随机性,采用独立样本t 检 验 的 方 法,分 别 检 验 各 改 进 算 法 与 经 典NSGA-Ⅱ算法求解结果的 HV 值的均值是否具有显著性差异。实验的工作流模型如图2所示。虚拟机的相关参数如表3所示,工作流中任务的相关参数如表4所示,改进的 NSGA-Ⅱ算法涉及的参数如表5所示。表3 虚拟机的相关参数虚拟机编号 1  2  3  4  5  6  7  8  9执行速度 1  2  4  1  2  4  4  2  1spa0.5 0.8 0.6 0.5 0.7 0.7 0.7 0.8  0.6spg 0.6 0.5 0.6 0.8 0.8 0.5 0.6 0.7  0.7spd 0.5 0.6 0.7 0.6 0.9 0.6 0.7 0.8  0.6表4 工作流中任务的相关参数任务编号 1  2  3  4  5  6  7  8  9  10 11 12 13执行时长 2  4  6  4  2  4  4  6  6  8  4  4  6sra0.5 0.7 0.8 0.5 0.6 0.8 0.8 0.6 0.5 0.6 0.5 0.8 0.5srg 0.6 0.7 0.5 0.7 0.6 0.8 0.6 0.5 0.6 0.6 0.8 0.5 0.5srd 0.5 0.8 0.6 0.5 0.6 0.9 0.6 0.7 0.7 0.7 0.6 0.6 0.5表5 改进 NSGA-Ⅱ算法的相关参数参数 pc pm pb ps值 0.800  0.005  1.000  1.000表3中,执行速度取值为1的虚拟机称作标准虚拟机,执行速度取值为2和4的虚拟机分别表示相应虚拟机 的 执 行 速 度 是 标 准 虚 拟 机 的 2 倍 和 4倍;spa,spg和spd表示虚拟机能够提供保密性、完整性和真实性的安全服务水平。表4中,执行时长表示任务 在 标 准 虚 拟 机 上 的 执 行 时 间,sra,srg和srd表示任务对保密性、完整性和真实性3个安全指标的安全需求水平。表5中,相关概率的取值是经过大量调参实验得到的。本实验的硬件设备为Inter酷睿i5处理器,内存为4GB,CPU 3.40GHz,软件环境为 MATLAB R2010b。3.2 实验结果(1)3台虚拟机时的调度优化结果当虚拟机台数为3时,取工作流实例数量分别为5,10和20,比较各算法在不同迭代次数时的 HV均值,如图3所示。从图3中可见,在最后一轮迭代结束后,经t检验,NSGA-Ⅱ(S)和 NSGA-Ⅱ算法求解结果的 HV均值 间 没 有 明 显 差 异;NSGA-Ⅱ (P)和 NSGA-Ⅱ(PS)算 法 求 解 结 果 的 HV 均 值 均 优 于 NSGA-Ⅱ算法。(2)6台虚拟机时的调度优化结果当虚拟机台数为6时,取工作流实例数量分别为5,10和20,比较各算法在不同迭代次数时的 HV均值,如图4所示。从图4中可见,在最后一轮迭代结束后,经t检验,在不同 工 作 流 实 例 数 量 时,NSGA-Ⅱ (P),NS-GA-Ⅱ(S)和 NSGA-Ⅱ(PS)算法求解结果的 HV 均值均优于 NSGA-Ⅱ算法。(3)9台虚拟机时的调度优化结果当虚拟机台数为9时,取工作流实例数量分别为5,10和20,比较各算法在不同迭代次数时的 HV798第5期 叶 鑫 等:考虑信息安全因素的多目标云工作流调度均值,如图5所示。从图5中可见,在最后一轮迭代结束后,经t检验,在不同 工 作 流 实 例 数 量 时,NSGA-Ⅱ (P),NS-GA-Ⅱ(S)和 NSGA-Ⅱ(PS)算法求解结果的 HV 均值均优于 NSGA-Ⅱ算法。(4)改进算法相对于 NSGA-Ⅱ算法求解结果的HV 均值提高率纵观所有实验,针对最大迭代次数的优化结果,改进 的 NSGA-Ⅱ (P),NSGA-Ⅱ (S)和 NSGA-Ⅱ(PS)算 法 相 对 于 传 统 NSGA-Ⅱ 算 法 求 解 结 果 的HV 均值的提高率,如图6所示。3.3 结果分析所有 实 验 结 果 表 明,相 比 于 NSGA-Ⅱ 算 法,NSGA-Ⅱ(P)算法求解结果的 HV 均值都有不同程度的提高。例 如,当虚 拟 机 台 数 为 9 时,改 进 NS-GA-Ⅱ(P)算法相对于传统 NSGA-Ⅱ算法,在实例数量 为 5,10,20 时 分 别 提 升 了 5.1%,3.1% 和2.1%,说明工作流实例中任务调度的优先级确定规799

[返回]
上一篇:面向车联网应用的数据关联性任务调度算法
下一篇:开放式数控系统的低能耗和可靠性调度算法