叶　鑫 等：考虑信息安全因素的多目标云工作流调度化调度问题［４］、考虑一定预算约束下的所有工作流实例执行结束时间最小化调度问题［５］，以及考虑虚拟机性能约束下的所有工作流实例执行结束时间最小化调度问题［６］。另外，针对某些实际场景，工作流调度也可能需要考虑多个目标，如执行结束时间和费 用 最 小 化［７］、执 行 结 束 时 间 和 能 源 消 耗 最 小化［８］等。然而，现有的云工作流调度研究中，考虑信息安全与隐私性保护因素的研究较少。由于云计算环境具有复杂性、开放性和动态 性特点，多用户动态租用、共享高度集中的资源且数据的传输完全依赖于网络，当存在不同程度信任关系的用户间动态共享同一计算资源时，可能降低安全的可控性［９］；另外，在云计算服务模式下，云服务的透明性使用户失去对数据的控制，数据安全问题成为隐患。因此，某些场景下的云工作流调度问题对信息安全性提出了更高的要求，如何协调多种信任关系、保护用户数据和隐私安全，以及在保证云工作流调度性能的同时降低信息安全风险，值得深入研究。在现有的考虑信息安全与隐私性保护的云工作流调度研究中，Ｌｉｕ等［１０］指出每台计算资源有一个安全服务水平等级、工作流中的每个任务也有一个相应的安全需求水平等 级，并提出 ３ 种安全模型。在模型中，计算节点提供安全服务时会产生与信息安全有关的时间开销；Ｘｉｅ等［１１］认为在异构分布系统环境下，每个任务都有认证性、机密性、完整性 ３种安全服务的需求，并提出一种安全驱动的启发式调度算法，使任务在执行过程中尽量满足各自的信息安全需求；白晶晶［９］考虑了云环境下用户的安全需求，提出一种安全和可靠性驱动的云任务调度算法，并将调度过程分为预备和正式调度两个阶段。上述研究作为本文的研究基础，仍存在如下不足需要改进：①多考虑单个目标或将多个目标转化成一个目标，然而多目标优化可以平衡多个目标之间的关系，并能得到多个优化结果，供决策者根据其偏好进行决策，因此采用多目标优化更具实际意义；②在任务执行所产生的信息安全风险概率的衡量方面，没有给出无决策偏好时各信息安全指标的权重确定方法，可以根据任务的安全需求水平和虚拟机能够提供的安全服务水平等客观实际情况，采用熵权法确定各信息安全指标的权重；③多采用启发式算法或元启发式算法进行求解［１２－１４］，当解空间很大时优化效果不甚理想，因此可以将启发式规则融入元启发式算法中形成混合启发式算法［１１］，以提升优化效果［１５］。为解决上述问题，本文首先构建了云计算环境下考虑信息安全因素的工作流调度模型，然后提出两种启发式规则并对应用较广泛的一种多目标优化算法———改进的 非 支 配 排 序 遗 传 算 法 （Ｎｏｎ－ｄｏｍｉ－ｎａｔｅｄ　Ｓｏｒｔｉｎｇ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ，ＮＳＧＡ－Ⅱ）进行了改进，最后进行了实验及结果分析。１　考虑信息安全因素的云工作流调度模型考虑云工作流执行过程中的保密性（Ｃｏｎｆｉｄｅｎ－ｔｉａｌｉｔｙ）、完 整 性 （Ｉｎｔｅｇｒｉｔｙ）和 真 实 性 （Ａｕｔｈｅｎｔｉｃａ－ｔｉｏｎ）３个信息安全指标［１６］，首先给出工作流模型、计算资源模型，以及信息安全服务的时间开销与信息安全风险模型，然后以多工作流实例的所有任务执行结束时间最小化和信息安全风险最小 化为目标，构建云工作流调度模型。１．１　考虑信息安全因素的工作流模型工作流中的任务及其间的偏序关系可用有向无环图（Ｄｉｒｅｃｔｅｄ　Ａｃｙｃｌｉｃ　Ｇｒａｐｈ，ＤＡＧ）来描述，即可以抽象为一个三 元 组 Ｇ＝（Ｔ，Ｅ，ＳＲ）。其 中：Ｔ＝｛ｔａｓｋ１，ｔａｓｋ２，…，ｔａｓｋｑ｝表示工作流所包含的任务集合，ｑ表示任务的数量。Ｅ∈Ｔ×Ｔ 表示这些任务之间的依赖关系集合，ｅｉｊ∈Ｅ 表示ｔａｓｋｉ与ｔａｓｋｊ之间的依赖关系，即ｔａｓｋｊ必须在ｔａｓｋｉ执行结束后才能开始执行。具有依赖关系的任务间存在数据传输，若这两个任务被分配在不同计算资源上执行，则存在数据通讯时间，记为 ＣＴ（ｔａｓｋｉ，ｔａｓｋｊ）；若这两个任务被分配在同一计算资源上执行，则通讯时间为０。ＳＲ＝｛ＳＲ１，ＳＲ２，…，ＳＲｑ｝表示任务对信息安全需求的集合。此外，没有任何紧前任务的任务称为初始任务，记为ｔａｓｋｅｎｔｒｙ；没有任何紧后任务的任务称为结束任务，记为ｔａｓｋｅｘｉｔ。数据偷窥、数据更改和电子欺骗是云计算环境中常见的３种攻击方式，因此工作流中的全部任务或某些任务可能具有保密性、完整性和真实性３种安全需求。一般应用加密算法来实现保密性，应用ｈａｓｈ算法来实现完整性，应用数字签名和身份验证来实现真实性［１５］。令 ＳＲｊ＝（ｓｒａｊ，ｓｒｇｊ ，，ｓｒｄｊ）表示任务ｔａｓｋｊ对 保 密 性、完 整 性 和 真 实 性 的 需 求 水 平。为了便于计算，每个指标的信息安全需求水平取值标准化为［０，１］，值越高表示对相应指标的信息安全需求越高。７９３计算机集成制造系统 第２３卷１．２　考虑信息安全因素的计算资源模型虚拟机是云计算环境中工作流及其任务执行的载体，其通过网络连接，具有全连通性。虚拟机集合可以表示为ＶＭ ＝｛ｖｍ１，ｖｍ２，…，ｖｍｍ｝，其中 ｍ 为虚拟机的数量。不同的虚拟机可能具备不同的计算能力和安全服务水平。令ＶＭＣ＝｛ｖｍｃ１，ｖｍｃ２，…，ｖｍｃｍ｝表示不同虚拟机的计算能力集合，ＳＰ＝｛ＳＰ１，ＳＰ２，…，ＳＰｍ｝表示虚拟机能够提供的安全服务水平集合。其中ＳＰｋ＝（ｓｐａｋ，ｓｐｇｋ，ｓｐｄｋ）表示虚拟机ｖｍｋ能够提供的保密性、完整性和真实性３个指标的信息安全服务水平。同样，为了便于计算，这些指标也标准化取值为［０，１］，取值越大，其所提供的信息安全服务水平越高。１．３　信息安全服务的时间开销与信息安全风险模型（１）信息安全服务的时间开销针对云计算环境下的工作流调度问题，考虑信息 安 全 因 素 将 不 可 避 免 地 带 来 相 应 的 时 间 开销［１７－１８］。为了不失一般性，保密性、完整性和真实性３种信息安全服务带来的时间开销分别为［１９］：ＳＯａｊｋ＝ｌｊ／ａ（ｖｍｋ，ｔａｓｋｊ）； （１）ＳＯｇｊｋ＝ｌｊ／ｇ（ｖｍｋ，ｔａｓｋｊ）； （２）ＳＯｄｊｋ＝φｄ（ｖｍｋ，ｔａｓｋｊ）。 （３）式中：ＳＯａｊｋ，ＳＯｇｊｋ和ＳＯｄｊｋ分别表示任务ｊ在虚拟机ｋ上执行时的保密性服务、完整性服务和真实性服务的时间开销；ｌｊ表示执行任务ｊ时所涉及的需保证保密性、完整性的数据量；ａ（ｖｍｋ，ｔａｓｋｊ），ｇ（ｖｍｋ，ｔａｓｋｊ）和φｄ（ｖｍｋ，ｔａｓｋｊ）分别表示任务ｊ在虚拟机ｋ上执行时相应的保密性、完整性和真实性安全服务水平与计算开销的映射关系。任务ｊ在虚拟机ｋ 上执行时的信息安全服务总时间开销ＳＯｊｋ ＝∑ｌ∈（ａ，ｇ，ｄ）ＳＯｌｊｋ（ｖｍｋ，ｔａｓｋｊ）。 （４）（２）信息安全风险模型若任务ｊ在虚拟机ｋ 上执行，则当任务ｊ 的安全需求水平大于虚拟机ｋ 能够提供的安全服务水平即ｓｒｌｊ＞ｓｐｌｊ，ｌ∈（ａ，ｇ，ｄ）时，存在一定概率的信息安全风险。令ｓｄｌｊｋ＝ｓｒｌｊ－ｓｐｌｋ表示任务ｊ在虚拟机ｋ 上执行时在信息安全指标ｌ 方面的需求满足程度，则该任务执行的信息安全风险概率ｐｌｊｋ可表达为ｓｄｌｊｋ的函数。假设风险在固定的时间间隔内服从泊松分布，则相应的风险概率可以由一个指数分布表示为ｐｌｊｋ＝０， ｓｒｌｊ ≤ｓｐｌｋ；１－ｅ－βｓｄｌｊｋ， ｓｒｌｊ ＞ｓｐｌｋ烅烄烆。（５）式中β为风险系数，当ｓｒｌｊ＞ｓｐｌｋ时，ｓｄｌｊｋ的值越大，相应的风险概率越大。任务ｊ在虚拟机ｋ 上执行的总体信息安全风险概率ｐｊｋ ＝∑ｌ∈（ａ，ｇ，ｄ）ｗｌｊ·ｐｌｊｋ。 （６）式中 ｗｌｊ表示任务ｊ针对信息安全指标ｌ 的风险概率权重，满足０≤ｗｌｊ≤１且∑ｌ∈（ａ，ｇ，ｄ）ｗｌｊ＝１。每一个任务在不同虚拟机上执行时，某一信息安全指标下的风险概率可能存在差异。若这一差异较大，则对该任务到虚拟机的分配决策提供的信息价值较大，该指标应赋予较大的权重；若这一差异不大，则对其决策提供的信息价值较小，该指标应赋予较小的权重。熵权法是一种在没有决策偏好的情况下，根据评价指标构成的特征值矩阵来确定指标权 重的方法［２０］，因此可用熵权法确定 ｗｌｊ。每个任务 都可以分配在 ｍ 台虚拟机上执行，即有 ｍ 个分配方案。由于每个任务分配至虚拟机上执行时需尽可能满足信息安全需求，可将保密性、完整性和真实性作为分配方案的３个评价指标。某一指标的熵值越大，其权重越小；熵值越小，其权重越大。针对某一任务ｊ，可构建评价方案的特征值矩阵Ａ＝（Ａｋｌ）ｍ３（ｋ＝１，２，…，ｍ；ｌ＝１，２，３），其中每一列表示该任务在不同虚机上执行时每一个安全指标的需求满足度，每一行表示该任务到虚拟机的一个分配方案。因为ｓｒｌ－ｓｐｌ≤０时虚拟机提供的安全服务水平可满足任务的安全需求、不会产生风险，所以将安全需求满足度为负数的元素均替换成 ０，从而得到矩阵Ａ。进一步对矩阵Ａ 进行归一化，得到相对优属矩阵Ｒ＝（ｒｋｌ）ｍ３。ｒｋｌ ＝ｓｕｐ（Ａｋｌ）－Ａｋｌｓｕｐ（Ａｋｌ）－ｉｎｆ（Ａｋｌ）。 （７）式中ｓｕｐ（Ａｋｌ）与ｉｎｆ（Ａｋｌ）分别为矩阵Ａ 中第ｌ列元素的最大值和最小值。信息安全指标ｌ的熵定义为Ｈｌ ＝－∑ｍｋ＝１ｆｋｌｌｎｆｋｌｌｎ　ｍ，ｆｋｌ ＝１＋ｒｋｌ∑ｍｋ＝１（ｒｋｌ＋１）。 （８）则针对任务ｊ，信息安全指标ｌ的权重ｗｌｊ＝１－Ｈｌ１－Ｈ１ ＋１－Ｈ２ ＋１－Ｈ３。 （９）７９４ 叶　鑫 等：考虑信息安全因素的多目标云工作流调度１．４　云工作流调度模型本文研究的云工作流调度问题可以表示为：有ｎ个工作流实例（Ｉ１，Ｉ２，…，Ｉｎ），每个工作流实例有ｑ个任务，可在 ｍ 台虚拟机上执行；工作流中的任务间存在一定的偏序关系，每个任务可以在所有的虚拟机上执行；每个任务在不同的虚拟机上执行的时间长度和风险概率有可能不同；若具有偏序关系的两个任务被分配在不同的虚拟机上执行，则这两个任务间的数据传输存在通讯时间；调度的目标是分配所有工作流实例的所有任务到合适的虚拟机上执行，使得所有任务的执行结束时间最小化和信息安全风险概率最小化。本文遵循如下云计算环境下工作流调度问题中最常见的假设条件：（１）若任务被分配到某一台虚拟机上执行，且该任务执行所需数据已到达该虚拟机，则只要该虚拟机空闲，该任务应立即执行，不可以延迟执行。（２）每一台虚拟机在同一时刻只能执行一个任务。（３）每一个工作流实例中的每一个任务只能在一台虚拟机上被执行一次。（４）若某任务开始执行，则在其执行期间不能有间断。（５）若两个任务间存在数据的网络通讯，则其通讯时间是关于传输数据量的函数。相关符号定义如表１所示。表１　符号及其定义符号 含义Ｉｉ 第ｉ个工作流实例ＩｉＴｊ 第ｉ个工作流实例的第ｊ 个任务Ｔｊｋ 任务ｊ在虚拟机ｋ 上的执行时长ｐｒｅ（ｉ，ｊ） ＩｉＴｊ 的紧前任务集合ｅｘｅｃ（ｋ） 虚拟机ｋ上执行的任务集合ＶＡＴｉｊｋ 虚拟机ｋ针对ＩｉＴｊ 的可用时刻ＤＡＴｉｊｋ ＩｉＴｊ 执行所需数据到达虚拟机ｋ 的时刻ＳＴｉｊｋ ＩｉＴｊ 在虚拟机ｋ 上开始执行的时刻ＦＴｉｊｋ ＩｉＴｊ 在虚拟机ｋ 上执行的结束时刻αｊ′ｊ 存在偏序关系的两个任务间的通讯时间θｉｊｋ ０－１变量，θｉｊｋ＝１表示ＩｉＴｊ 分配在虚拟机ｋ 上执行ＬＶＴｋ 虚拟机ｋ上最后一个任务的执行结束时刻ｓｒｌｊ任务ｊ的第ｌ个安全指标的安全需求水平ｓｐｌｋ虚拟机ｋ所提供的第ｌ个安全指标的安全服务水平ＳＯｊｋ 任务ｊ在虚拟机ｋ上执行时的信息安全服务的总时间开销ｐｌｉｊｋＩｉＴｊ 在虚拟机ｋ 上执行的第ｌ个安全指标的风险概率ｗｌｊ任务ｊ的第ｌ个安全指标风险概率的权重Ｐｉｊｋ ＩｉＴｊ 在虚拟机ｋ 上执行的总风险概率根据上述问题和符号定义，建立云工作流调度优化模型如下：ｆ１ ＝ ｍａｘｋ∈［１，ｍ］（ＬＶＴｋ）； （１０）ｆ２ ＝∑ｎｉ＝１∑ｑｊ＝１∑ｍｋ＝１θｉｊｋＰｉｊｋ； （１１）ｍｉｎ（ｆ１，ｆ２）。ｓ．ｔ．ＤＡＴｉｊｋ＝０，　ｔａｓｋｊ＝ｔａｓｋｅｎｔｒｙ，ｍａｘｊ′∈ｐｒｅ（ｉ，ｊ）（ＦＴｉｊ′ｋ′＋αｊ′ｊ（１－θｉｊ′ｋ）），　　ｔａｓｋｊ ≠ｔａｓｋｅｎｔｒｙ烅烄烆 ；（１２）ＶＡＴｉｊｋ ＝ＦＴｉ″ｊ″ｋ； （１３）ＳＴｉｊｋ ＝ ｍａｘ（ＤＡＴｉｊｋ，ＶＡＴｉｊｋ）； （１４）ＦＴｉｊｋ ＝ＳＴｉｊｋ ＋Ｔｊｋ ＋ＳＯｊｋ； （１５）ｐｌｉｊｋ＝０ ｓｒｌｊ ≤ｓｐｌｋ１－ｅ－β（ｓｒｌｊ－ｓｐｌｋ）ｓｒｌｊ ＞ｓｐｌ烅烄烆 ｋ，ｌ∈ （ａ，ｇ，ｄ）；（１６）Ｐｉｊｋ ＝∑ｌ∈（ａ，ｇ，ｄ）ｗｌｊ·ｐｌｉｊｋ； （１７）∑ｌ∈（ａ，ｇ，ｄ）ｗｌｊ＝１，０≤ ｗｌｊ ≤１； （１８）∑ｍｋ＝１θｉｊｋ ＝１，θｉｊｋ＝０，１； （１９）ＬＶＴｋ ＝ ｍａｘｅ，ｆ∈ｅｘｅｃ（ｋ）（ＦＴｅｆｋ）。 （２０）其中：式（１０）表示所有任务的执行结束时间，其值为所有虚拟机上最后一个任务执行结束时刻 的最大值；式（１１）表示调度方案的信息安全风险概率，其值为所有实例所有任务在所分配虚拟机上执行的信息安全风险概率之和；式（１２）表示当工作流实例ｉ的任务ｊ被分配在虚拟机ｋ 上执行时，其所需数据到达该虚拟机的时间：若任务ｊ是初始任务即该任务没有前序任务，则其所需数据的传输时间为０；若任务ｊ不是初始任务，则其所需数据到达该虚拟机的时间为所有前序任务集合中每一个任务的执行结束时间和其与任务ｊ的数据通讯时间之和的最大值；若任务ｊ与其某一个前序任务被分配在同一台虚拟机上执 行，则这 两 任务间的数 据 通讯时间 为 ０；式（１３）表示虚拟机ｋ 可供ＩｉＴｊ（工作流实例ｉ的任务ｊ）执行的最早时间，其中 ＦＴｉ″ｊ″ｋ表示调度方案中被分配在虚拟机ｋ 上且在ＩｉＴｊ 之前执行的任务Ｉｉ″Ｔｊ″的执行结束时刻；式（１４）表示ＩｉＴｊ 在虚拟机ｋ 上的开始执行时刻，其值为其所需数据到达虚拟机ｋ 的时刻和虚拟机ｋ 针对该任务的可用时刻之间的最大值；式（１５）表示ＩｉＴｊ 在 虚 拟 机ｋ 上 的 执 行 结 束 时７９５０６－３０；修订日期：２０１６－０８－２８。Ｒｅｃｅｉｖｅｄ　３０Ｊｕｎｅ　２０１６；ａｃｃｅｐｔｅｄ　２８Ａｕｇ．２０１６．基金项目：中央高校基本科研业务费专项资金资助项目（ＤＵＴ１３ＪＳ１１）。Ｆｏｕｎｄａｔｉｏｎ　ｉｔｅｍ：Ｐｒｏｊｅｃｔ　ｓｕｐｐｏｒｔｅｄ　ｂｙ　ｔｈｅ　Ｆｕｎｄａｍｅｎｔａｌ　Ｒｅｓｅａｒｃｈ　Ｆｕｎｄｓｆｏｒ　ｔｈｅ　Ｃｅｎｔｒａｌ　Ｕｎｉｖｅｒｓｉｔｉｅｓ，Ｃｈｉｎａ（Ｎｏ．ＤＵＴ１３ＪＳ１１）．考虑信息安全因素的多目标云工作流调度叶　鑫，梁继伟，尹艳丽（大连理工大学 信息与决策技术研究所，辽宁　大连　１１６０２３）摘　要：为了满足云工作流调度需求的多样性，构建了考虑信息安全因素和多实例工作流执行时长的云工作流调度模型。该模型主要考虑了保密性、完整性与真实性３种信息安全因素的时间开销，以及无决策偏好情况下的信息安全风险概率度量。为了提升调度优化效果，提出工作流实例中任务调度的优先级确定规则和考虑信息安全因素的虚拟机分配规则，并将这两个启发式规则与 ＮＳＧＡ－Ⅱ算法相融合，对上述模型进行了优化求解。实验结果表明，所提算法可以较好地实现工作流执行结束时间与信息安全风险概率两个目标的平衡，亦可提高优化结果的质量。关键词：云计算；工作流调度；信息安全；多目标优化中图分类号：ＴＰ３１１　　　文献标识码：ＡＭｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｃｌｏｕｄ　ｗｏｒｋｆｌｏｗ　ｓｃｈｅｄｕｌｉｎｇ　ｃｏｎｓｉｄｅｒｉｎｇ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｅｃｕｒｉｔｙ　ｆａｃｔｏｒｓＹＥ　Ｘｉｎ，ＬＩＡＮＧ　Ｊｉｗｅｉ，ＹＩＮ　Ｙａｎｌｉ（Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　ａｎｄ　Ｄｅｃｉｓｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ，Ｄａｌｉａｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｄａｌｉａｎ　１１６０２３，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｔｏ　ｍｅｅｔ　ｔｈｅ　ｄｉｖｅｒｓｅ　ｒｅｑｕｉｒｅｍｅｎｔｓ　ｏｆ　ｃｌｏｕｄ　ｗｏｒｋｆｌｏｗ　ｓｃｈｅｄｕｌｉｎｇ，ａ　ｃｌｏｕｄ　ｗｏｒｋｆｌｏｗ　ｓｃｈｅｄｕｌｉｎｇ　ｍｏｄｅｌ　ｃｏｎ－ｓｉｄｅｒｉｎｇ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｅｃｕｒｉｔｙ　ｆａｃｔｏｒｓ　ａｎｄ　ｅｘｅｃｕｔｉｏｎ　ｔｉｍｅ　ｏｆ　ｍｕｌｔｉｐｌｅ　ｗｏｒｋｆｌｏｗ　ｉｎｓｔａｎｃｅｓ　ｗａｓ　ｂｕｉｌｔ．Ｔｈｅ　ｍｅａｓｕｒｅｍｅｎｔｏｆ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｅｃｕｒｉｔｙ　ｒｉｓｋ　ｐｒｏｂａｂｉｌｉｔｙ　ｗｉｔｈｏｕｔ　ｄｅｃｉｓｉｏｎ　ｍａｋｅｒｓｐｒｅｆｅｒｅｎｃｅ　ａｎｄ　ｔｈｅ　ｔｉｍｅ　ｏｖｅｒｈｅａｄ　ｏｆ　ｔｈｒｅｅ　ｓｅｃｕｒｉｔｙｆａｃｔｏｒｓ　ｉｎｃｌｕｄｅｄ　ｃｏｎｆｉｄｅｎｔｉａｌｉｔｙ，ｉｎｔｅｇｒｉｔｙ　ａｎｄ　ａｕｔｈｅｎｔｉｃｉｔｙ　ｗｅｒｅ　ｒｅｓｅａｒｃｈｅｄ．Ｆｏｒ　ｉｍｐｒｏｖｉｎｇ　ｓｃｈｅｄｕｌｉｎｇ　ｏｐｔｉｍｉｚａｔｉｏｎｒｅｓｕｌｔ，ｔｈｅ　ｐｒｉｏｒｉｔｙ　ｄｅｔｅｒｍｉｎａｔｉｏｎ　ｒｕｌｅ　ｏｆ　ｔａｓｋ　ｓｃｈｅｄｕｌｉｎｇ　ｉｎ　ｔｈｅ　ｗｏｒｋｆｌｏｗ　ｉｎｓｔａｎｃｅ　ａｎｄ　ｖｉｒｔｕａｌ　ｍａｃｈｉｎｅ　ａｌｌｏｃａｔｉｏｎ　ｒｕｌｅｃｏｎｓｉｄｅｒｅｄ　ｓｅｃｕｒｉｔｙ　ｆａｃｔｏｒ　ｗｅｒｅ　ｐｒｏｐｏｓｅｄ．Ｔｈｅｓｅ　ｔｗｏ　ｈｅｕｒｉｓｔｉｃ　ｒｕｌｅｓ　ａｎｄ　Ｎｏｎ－ｄｏｍｉｎａｔｅｄ　Ｓｏｒｔｉｎｇ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ（ＮＳＧＡ－Ⅱ）ａｌｇｏｒｉｔｈｍ　ｗｅｒｅ　ｃｏｍｂｉｎｅｄ　ｔｏ　ｓｏｌｖｅ　ａｂｏｖｅ　ｍｏｄｅｌ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔ　ｒｅｓｕｌｔｓ　ｓｈｏｗｅｄ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏ－ｒｉｔｈｍ　ｎｏｔ　ｏｎｌｙ　ｃｏｕｌｄ　ｒｅａｌｉｚｅ　ｔｈｅ　ｂａｌａｎｃｅ　ｏｆ　ｗｏｒｋｆｌｏｗ　ｅｘｅｃｕｔｉｏｎ　ｔｉｍｅ　ａｎｄ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｅｃｕｒｉｔｙ　ｒｉｓｋ　ｐｒｏｂａｂｉｌｉｔｙ　ｂｅｔｔｅｒ，ｂｕｔ　ａｌｓｏ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｑｕａｌｉｔｙ　ｏｆ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｒｅｓｕｌｔ．Ｋｅｙｗｏｒｄｓ：ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ；ｗｏｒｋｆｌｏｗ　ｓｃｈｅｄｕｌｉｎｇ；ｉｎｆｏｒｍａｔｉｏｎ　ｓｅｃｕｒｉｔｙ；ｍｕｌｔｉ－ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ０　引言作为一种新的计算模式和商业模式，云计算的应用越来越广泛，它通过互联网将分布在不同物理位置的计算资源等共享起来，按需提供给用户使用。在云计算环境下，一些大型的应用通常由多个任务组成，这些任务具有相同的目标，在执行过程中存在时间偏序关系和数据依赖关系，从而构成了云工作流［１］。云工作流调度是指将工作流中的任务合理地分配到云计算资源上执行，同时满足资源约束条件和服务质量需求。近年来，有关云工作流调度的研究呈上升 趋 势，已 经 成 为 学 术 界 和 企 业 界 的 研 究热点［２－３］。目前，在云工作流调度研究中，针对不同场景、不同用户需求，所考虑的调度问题可能会不同，如考虑满足截止时间（ｄｅａｄｌｉｎｅ）约束下的执行费用最小计算机集成制造系统 第２３卷刻，即该任务的开始执行时刻、执行时长和信息安全服务的时间开销之和；式（１６）表示ＩｉＴｊ 分配在虚拟机ｋ 上执行时，第ｌ个信息安全指标的风险概率；式（１７）表示ＩｉＴｊ 分配在虚拟机ｋ 上执行时总的信息安全风险概率，其值为３种安全指标风险概率的加权求和；式（１８）表示任务ｊ的３种安全指标风险概率的权重之和等于１；式（１９）表示ＩｉＴｊ 只能在一台虚拟机上执行一次；式（２０）表示在虚拟机ｋ 上执行的所有任务的结束时间最大值，即该虚拟机上最后一个执行任务的结束时刻。２　改进的 ＮＳＧＡ－Ⅱ算法云工作流调度问题是一个 ＮＰ 难问题［２１］，适于采用元启发式和混合启发式算法求 解。由 于 ＮＳ－ＧＡ－Ⅱ是一种基于遗传算法的多目标优化算法，被广泛应用且比较成熟，常用来求解两个目标的优化问题。因此，本文针对 所 提 出 的 调 度 模 型，对 ＮＳ－ＧＡ－Ⅱ算法进行了如下改进：①对经典 ＮＳＧＡ－Ⅱ算法中的染色体编码和一些操作算子进行了修改，使其满足云计算环境下工作流调度的特点和一些约束条件；②针对前述模型的两个目标函数提出两种启发式规则，即工作流中任务调度的优先级确定规则和考虑信息安全因素的虚拟机分配规则，将这两个启发式规则应用于种群初始化阶段，以提高算法的搜索效率并获得更优的解。２．１　编码与操作算子设计（１）工作流调度中个体的编码设计针对所提出的云工作流调度模型，一个染色体（个体）表示一个可能的调度方案，采用多层整数编码，如图１所示。当有ｎ个工作流实例、每个工作流实例有ｑ个任务分配在ｍ 台虚拟机上执行时，染色体编码的长度为２ｎｑ＋４。其中，前ｎｑ 位编码表示所有工作流实例的所有任务的调度顺序，ｎｑ＋１～２ｎｑ位表示前面相应任务执行的虚拟机编号。染色体后四位分别表示所有任务的执行结束时间（第１个目标函数值）、信息安全风险概率（第２个目标函数值）、染色体所属的 Ｐａｒｅｔｏ前沿序号和拥挤距离。（２）基于二元锦标赛（ｂｉｎａｒｙ　ｔｏｕｒｎａｍｅｎｔ）的选择操作对种群进行二元锦标赛选择操作。随机选择两个不重复的个体，针对被选中的两个个体，优先选择前沿序值小的个体；当前沿序值相同时，为了保证种群多样性，保留拥挤距离值大的个体。（３）工作流任务编码的交叉操作在个体的任务编码位置即个体的前ｎｑ位，以概率ｐｃ对个体进行交叉操作。若对当前个体执行交叉操作，则从种群中随机选择一个个体，且不与当前个体重复，然后随机产生交叉位置ｐｏｓ∈［１，ｎｑ］，对两个个体的１～ｐｏｓ位编码进行交叉操作。交叉后若某些工作流实例的任务存在冗余或缺失现象，则通过补缺操作来保证每个实例的任务满足相应工作流模型的要求。（４）虚拟机编码的变异操作在个体的虚 拟 机 编 码 位 置 即 个 体 的 ｎｑ＋１～２ｎｑ位的基因，以概率ｐｍ发生变异操作。若执行变异操作，则任务以ｐｑｍ的概率被变异到另一台虚拟机上，其中变异到计算速度快的虚拟机（任务执行时间短的虚拟机）上的概率较大。ｐｑｍ（ｊｋ）＝２ｍａｘＥ（ｊ）－Ｔｅｖ（ｊｋ）∑ｋ′∈Ｖ（２ｍａｘＥ（ｊ）－Ｔｅｖ（ｊｋ′））。（２１）式中：ｐｑｍ（ｊｋ）表示任务ｊ被变异到虚拟机ｋ 上的概率，ｍａｘＥ（ｊ）表示任务ｊ在计算速度最慢的虚拟机上执行的时间，Ｔｅｖ（ｊｋ）表示任务ｊ在虚拟机ｋ 上执行的时间，Ｖ 表示任务ｊ 可被分配的虚拟机的集合。２．２　两种启发式规则在经典的 ＮＳＧＡ－Ⅱ算法中，种群初始化是完全随机的。但当调度任务的数量增加时，个体的编码长度将随之变长，解空间也随之变大。此时，元启发式算法的求解效率会降低，而且容易陷入局部最优。因此，针对所提调度模型提出如下两种相互独立的启发式规则，并融入算法的种群初始化阶段，以提高优化结果的质量。（１）工作流实例中任务调度的优先级确定规则由于工作 流 中 的 任 务 之 间 存 在 偏 序 关 系，前序任务 的 执 行 情 况 会 对 后 序 任 务 的 执 行 产 生 影响，从而影 响 整 个 工 作 流 的 执 行 时 长。 在 实 际 的工作流调度中，常使用任务优先调度的规 则，使优先级高的任务先被分配到虚拟机上执行，其 中 ＢＲ（ｂｏｔｔｏｍ　ｒａｎｋ）值 排 序 法 经 常 被 使 用［２２］。ＢＲ 值 排序法的主要思想是计算所有任务到结束任 务的最７９６ 叶　鑫 等：考虑信息安全因素的多目标云工作流调度长执行时间路径，然后选择 ＢＲ 值大的任务优先进行调度，但 该 方 法 不 能 很 好 地 针 对 具 有 大 量 并 行结构的工作流调度的场景。在具有并行执行关系的任务中，若 任 务ｉ的 后 序 任 务 数 量 多 且 计 算 量大、任务ｊ的后序任务少 且计 算量小，则相对于任务ｊ，任务ｉ应被优先调度。基于这一思想，本文对ＢＲ 值排序法进行改进（如式（２２）），以使任务调度的优先级确定更合理。ＰＢＲ（ｔａｓｋｊ）＝１ｍ∑ｍｋ＝１Ｔｊｋ，　　　　　　　　 　 　ｔａｓｋｊ＝ｔａｓｋｅｘｉｔ；１ｍ∑ｍｋ＝１Ｔｊｋ ＋ ｓｕｍｔａｓｋｊ′∈ｓｕｂｓｅｑｕｅｎｔ（ｔａｓｋｊ）１ｍ∑ｍｋ＝１Ｔｊ（ ）′ｋ，　　 其他烅烄烆。（２２）式中：Ｔｊｋ表示任务ｊ在虚拟机ｋ 上执行的时间，ｍ表示虚拟机的数量，ｓｕｂｓｅｑｕｅｎｔ（ｔａｓｋｊ）表示任务ｊ的所有后序任务集合。当前任务的 ＰＢＲ 值为其本身在各虚拟机上执行的平均时间及其后序所有任务在各虚拟机上执行的平均时间的累加和。ＰＢＲ 值越大，该任务越应被优先调度。在种群初始化时，以 概 率ｐｂ应 用 该 启 发 式 规则，可以将 ＰＢＲ 值大的任务优先编码，即优先进行调度，从而提升优化效果。（２）考虑信息安全因素的虚拟机分配规则下面针对信息安全风险概率目标越小越好的原则，提出一种考虑信息安全因素的虚拟机分配策略，以提高优化结果的质量和效率。基于所提 出 的 云 工 作 流 调 度 模 型，用 一 个 三元组Ｓｊｋ＝（ｓｄａｊｋ，ｓｄｇｊｋ，ｓｄｄｊｋ）表 示 任 务ｊ在 虚 拟 机ｋ上执行时的安全需求满足程度。当Ｓｊｋ中的元素都大于等于０或者都小于等于０时，该任务的总体安全需求的满足程度可由式（２３）直接计算得到。ＳＤｊｋ ＝∑ｌ∈（ａ，ｇ，ｄ）ｗｌｊ．ｓｄｌｊｋ，ｌ∈ （ａ，ｇ，ｄ）。 （２３）在Ｓｊｋ中的元素既存在大于０又存在小于０的情况下，若ｓｄｌｊｋ＜０，则令ｓｄｌｊｋ＝０，表示在相应安全指标下不存在安全风险，然后基于式（２３）计算任务的总体安全需求的满足程度。当有 ｍ 台虚拟机可供任务执行时，任务ｊ在不同虚拟机上安全需求的满足程 度可用集合ＳＤｊ＝｛ＳＤｊ１，ＳＤｊ２，…，ＳＤｊｍ｝表示。为了使提供高安全服务水平的虚拟机不被过度占用，同时有效降低任务执行的信息安全风险，提出如下考虑信息安全因素的虚拟机分配规则：规则１　若 ＳＤｊ中的元素都大于等于 ０，即该任务在任何一台虚拟机上执行都有可能产生风险，则任务ｊ分配到ＳＤｊ中最小值的虚拟机上执行，以使任务调度的风险概率最低。规则２　若 ＳＤｊ中的元素都小于等于 ０，即该任务在任何一台虚拟机上执行都不会产生风险，则任务ｊ分配至ＳＤｊ中最大值的虚拟机上执行，以尽可能使提供高安全服务水平的虚拟机不被低安全需求水平的任务占用。规则３　若ＳＤｊ中既存在大于０的元素又存在小于０的元素，则将ＳＤｊ中取值小于等于０的元素构成的子集合记为ＳＤ′ｊ，然后将任务ｊ分配至ＳＤ′ｊ中最大值的虚拟机上执行，以使任务被分配在不产生风险的虚拟机上执行，且不占用提供高安全服务水平的虚拟机。规则４　若ＳＤｊ中的元素值均相等，则将任务随机分配至任一台虚拟机上执行。在种群 初 始 化 时，以 概 率ｐｓ应 用 该 启 发 式规则。２．３　改进算法的时间复杂度ＮＳＧＡ－Ⅱ算法在每一 代 种群 进 化过程 中 均 采用一种快 速 非 支 配 排 序 方 法，将 组 合 种 群 分 成 多层非支配前沿集 Ｆ，其时间复杂度为 Ｏ（Ｎ２），其中Ｎ 为 种 群 大 小［２３］。 因 为 改 进 算 法 是 在 传 统 ＮＳ－ＧＡ－Ⅱ算法基础上，在种群初始化阶段加入上述两个启发式规 则，并 采 用 了 与 ＮＳＧＡ－Ⅱ 算 法 相 同 的非支配排序 方 法，所 以 其 时 间 复 杂 度 与 ＮＳＧＡ－Ⅱ算法相同。３　实验与结果分析３．１　实验设计为了比较改进 ＮＳＧＡ－Ⅱ算法与经典 ＮＳＧＡ－Ⅱ算法在优化结果方面的优劣，采用超体积 ＨＶ 指标进行评价。超体积是一种解集质量评估方法，可对解集的收敛性、均匀性和广泛性同时进行评价，并给出解集的综合评价结果［２４］。在应用超体积评价优化结果的 质 量 时，若 一 个 解 集 Ｓ 优 于 另 一 个 解 集Ｓ′，则解集 Ｓ 的 ＨＶ 值应大于Ｓ′的 ＨＶ 值［２５］。参与比较的算法的符号定义如表２所示。７９７计算机集成制造系统 第２３卷表２　算法符号及含义符号标识 含义ＮＳＧＡ－Ⅱ 经典的 ＮＳＧＡ－Ⅱ算法ＮＳＧＡ－Ⅱ（Ｐ）结合任务调度的优先级确定规则的改进 ＮＳＧＡ－Ⅱ算法ＮＳＧＡ－Ⅱ（Ｓ）结合考虑信息安全因素的虚拟机分配规则的改进 ＮＳＧＡ－Ⅱ算法ＮＳＧＡ－Ⅱ（ＰＳ） 结合上述两种启发式规则的改进 ＮＳＧＡ－Ⅱ算法从工作流实例数量和虚拟机台数两个角度考虑云工作流调度场景，共设计９组实验。其中：工作流实例数量分别取值为５，１０，２０，虚拟机台数分别取值为３，６，９。因为针对不同实例数量的工作流调度算法的收敛速度不同，所以５个工作流实例的最终迭代次数为１　０００，１０个工作流实例的最终迭代次数为 ２　０００，２０ 个 工 作 流 实 例 的 最 终 迭 代 次 数 为３　０００，其中每组实验均做了３０次。另外，因为遗传算法每一次求解的种群初始化及各算子的执行都具有一定的随机性，采用独立样本ｔ 检 验 的 方 法，分 别 检 验 各 改 进 算 法 与 经 典ＮＳＧＡ－Ⅱ算法求解结果的 ＨＶ 值的均值是否具有显著性差异。实验的工作流模型如图２所示。虚拟机的相关参数如表３所示，工作流中任务的相关参数如表４所示，改进的 ＮＳＧＡ－Ⅱ算法涉及的参数如表５所示。表３　虚拟机的相关参数虚拟机编号 １　 ２　 ３　 ４　 ５　 ６　 ７　 ８　 ９执行速度 １　 ２　 ４　 １　 ２　 ４　 ４　 ２　 １ｓｐａ０．５　０．８　０．６　０．５　０．７　０．７　０．７　０．８　 ０．６ｓｐｇ　０．６　０．５　０．６　０．８　０．８　０．５　０．６　０．７　 ０．７ｓｐｄ　０．５　０．６　０．７　０．６　０．９　０．６　０．７　０．８　 ０．６表４　工作流中任务的相关参数任务编号 １　 ２　 ３　 ４　 ５　 ６　 ７　 ８　 ９　 １０　１１　１２　１３执行时长 ２　 ４　 ６　 ４　 ２　 ４　 ４　 ６　 ６　 ８　 ４　 ４　 ６ｓｒａ０．５　０．７　０．８　０．５　０．６　０．８　０．８　０．６　０．５　０．６　０．５　０．８　０．５ｓｒｇ　０．６　０．７　０．５　０．７　０．６　０．８　０．６　０．５　０．６　０．６　０．８　０．５　０．５ｓｒｄ　０．５　０．８　０．６　０．５　０．６　０．９　０．６　０．７　０．７　０．７　０．６　０．６　０．５表５　改进 ＮＳＧＡ－Ⅱ算法的相关参数参数 ｐｃ ｐｍ ｐｂ ｐｓ值 ０．８００　 ０．００５　 １．０００　 １．０００表３中，执行速度取值为１的虚拟机称作标准虚拟机，执行速度取值为２和４的虚拟机分别表示相应虚拟机 的 执 行 速 度 是 标 准 虚 拟 机 的 ２ 倍 和 ４倍；ｓｐａ，ｓｐｇ和ｓｐｄ表示虚拟机能够提供保密性、完整性和真实性的安全服务水平。表４中，执行时长表示任务 在 标 准 虚 拟 机 上 的 执 行 时 间，ｓｒａ，ｓｒｇ和ｓｒｄ表示任务对保密性、完整性和真实性３个安全指标的安全需求水平。表５中，相关概率的取值是经过大量调参实验得到的。本实验的硬件设备为Ｉｎｔｅｒ酷睿ｉ５处理器，内存为４ＧＢ，ＣＰＵ　３．４０ＧＨｚ，软件环境为 ＭＡＴＬＡＢ　Ｒ２０１０ｂ。３．２　实验结果（１）３台虚拟机时的调度优化结果当虚拟机台数为３时，取工作流实例数量分别为５，１０和２０，比较各算法在不同迭代次数时的 ＨＶ均值，如图３所示。从图３中可见，在最后一轮迭代结束后，经ｔ检验，ＮＳＧＡ－Ⅱ（Ｓ）和 ＮＳＧＡ－Ⅱ算法求解结果的 ＨＶ均值 间 没 有 明 显 差 异；ＮＳＧＡ－Ⅱ （Ｐ）和 ＮＳＧＡ－Ⅱ（ＰＳ）算 法 求 解 结 果 的 ＨＶ 均 值 均 优 于 ＮＳＧＡ－Ⅱ算法。（２）６台虚拟机时的调度优化结果当虚拟机台数为６时，取工作流实例数量分别为５，１０和２０，比较各算法在不同迭代次数时的 ＨＶ均值，如图４所示。从图４中可见，在最后一轮迭代结束后，经ｔ检验，在不同 工 作 流 实 例 数 量 时，ＮＳＧＡ－Ⅱ （Ｐ），ＮＳ－ＧＡ－Ⅱ（Ｓ）和 ＮＳＧＡ－Ⅱ（ＰＳ）算法求解结果的 ＨＶ 均值均优于 ＮＳＧＡ－Ⅱ算法。（３）９台虚拟机时的调度优化结果当虚拟机台数为９时，取工作流实例数量分别为５，１０和２０，比较各算法在不同迭代次数时的 ＨＶ７９８第５期 叶　鑫 等：考虑信息安全因素的多目标云工作流调度均值，如图５所示。从图５中可见，在最后一轮迭代结束后，经ｔ检验，在不同 工 作 流 实 例 数 量 时，ＮＳＧＡ－Ⅱ （Ｐ），ＮＳ－ＧＡ－Ⅱ（Ｓ）和 ＮＳＧＡ－Ⅱ（ＰＳ）算法求解结果的 ＨＶ 均值均优于 ＮＳＧＡ－Ⅱ算法。（４）改进算法相对于 ＮＳＧＡ－Ⅱ算法求解结果的ＨＶ 均值提高率纵观所有实验，针对最大迭代次数的优化结果，改进 的 ＮＳＧＡ－Ⅱ （Ｐ），ＮＳＧＡ－Ⅱ （Ｓ）和 ＮＳＧＡ－Ⅱ（ＰＳ）算 法 相 对 于 传 统 ＮＳＧＡ－Ⅱ 算 法 求 解 结 果 的ＨＶ 均值的提高率，如图６所示。３．３　结果分析所有 实 验 结 果 表 明，相 比 于 ＮＳＧＡ－Ⅱ 算 法，ＮＳＧＡ－Ⅱ（Ｐ）算法求解结果的 ＨＶ 均值都有不同程度的提高。例 如，当虚 拟 机 台 数 为 ９ 时，改 进 ＮＳ－ＧＡ－Ⅱ（Ｐ）算法相对于传统 ＮＳＧＡ－Ⅱ算法，在实例数量 为 ５，１０，２０ 时 分 别 提 升 了 ５．１％，３．１％ 和２．１％，说明工作流实例中任务调度的优先级确定规７９９