具有失效恢复机制的云资源调度算法

齐 平，李龙澍，李学俊

（1.安徽大学 计算机科学与技术学院，安徽 合肥230039；2.铜陵学院 数学与计算机科学系，安徽 铜陵244000）

云计算（Cloud computing）是继并行计算、分布式计算和网格计算后的新型计算模式［1］.云计算平台利用虚拟化技术将多种计算资源（包括网络、服务器、存储、应用和服务等）在云端进行整合，对资源进行统一管理和调度，使得这些资源可以根据负载的变化动态配置，以达到最优的资源利用率.研究采用何种资源提供策略对这些大规模资源进行组织和管理，实现资源提供的高效灵活和按需分配，对云计算具有重要意义.

近些年，在云计算资源管理方面已有较多的研究.针对不同的计算任务和优化目标，云资源调度算法可以分为以下几类：1）以提高资源利用率和降低任务完成时间为目标［2-3］；2）以降低云计算中心能耗为目 标［4-6］；3）以 提 高 用 户 服 务 质 量（quality of service，QoS）为目标［7-8］；4）基于经济学的云资源管 理 模 型 研 究［9-10］；5） 多 目 标 优 化 的 混 合算法［11-12］.

由于云环境中包含着大量分散、异构资源，这些资源不仅地理位置分布广泛，甚至属于不同的自治系统，这些资源节点往往具有动态性、异构性、开放性、自愿性、不确定性以及欺骗性等特征.云服务的可靠性是指用户提交的服务被成功完成的概率，是从用户的角度反映云完成用户提交服务的执行能力.在拥有无数资源节点的云环境中，节点的不可靠现象不可避免，因此，如何获取可信的云资源，并将应用任务分配到值得信任的资源节点上执行成为云资源调度算法研究中急需解决的关键问题之一.

目前，在国内外分布式系统资源管理的相关研究中，有关如何获取可信资源的研究已经取得了不少成 果.Dogan 等［13-14］提 出 了RDLS（reliable dynamic level scheduling）算法，研究如何在异构分布式系统中获取可信资源.在此基础上，Dai等［15］提出了网格服务可靠性概念，采用最小档案扩展树对网格服务可靠性进行求解.Levitin［16］针对星型网格，提出了考虑服务可靠性和服务性能的信任评估算法.Foster等［17］将云服务和网格服务进行比较，给出云服务可靠性的评估方法.上述文献采用不同的信任模型，从不同角度研究网格服务、云服务的可靠性，并给出了相应的调度算法，有效地提高了任务执行的成功率.

自从Blaze［18］首先提出了信任管理概念后，Josang［19-20］等引入证据空间（evidence space）概念，以描述二项事件后验概率的Beta分布函数为基础，将信任分为直接信任和推荐信任，根据节点间交互的肯定经验和否定经验计算出实体能够完成任务的概率，并以此概率作为实体信任度的度量.基于证据的信任模型都是通过量化实体行为和计算实体信任度来评估实体间的相互信任关系.在上述研究中，所建立的信任评估模型并未考虑资源节点本身的行为特性.Wang［21-22］等在此基础上，综合考虑时间、权重等相关因素，利用贝叶斯算法构造了一个基于节点行为的可信度评估模型，并将其引入网格服务、云服务的可靠性研究中，分别提出了Trust-DLS（dynamic level scheduling）和Cloud-DLS算法.

在Trust-DLS算法和Cloud-DLS算法中，对于网络中的2个节点i和j，使用二项事件（交互成功／交互失败）表示节点间的交互结果，而信任度被定义为节点i和j 发生n 次交互后，第n＋1次交互成功的概率估计.然而，在实际的云计算环境中，由于软件、硬件以及系统过载等原因，失效问题在软件系统执行过程中不可避免，而失效恢复机制作为分布式系统可靠性研究的基础问题，在分布式计算、网格计算的可靠性研究中已经得到了广泛的应用［23-24］.

在失效恢复机制下，并不是所有失效都可以恢复，如软件故障和部分通信链路故障就不可恢复［25］.如图1所示，当网络中的节点间交互结果为失败时，按照物理故障（元件、链路失效）或软件故障（设计、交互原因）的分类，可以将其划分为可恢复失效和不可恢复失效.因此，在上述研究中，简单使用二项事件来描述节点间的交互结果使得相应的信任评估模型不太适用.

本文旨在构造一种云环境下考虑失效恢复机制的信任评估模型，主要研究内容包括：1）使用三项事件（交互成功／可恢复失效／不可恢复失效）描述节点的行为特性，建立相应的信任评估模型；2）在建模和分析的过程中，评估失效恢复的执行效率和相关参数对系统性能的影响；3）将考虑失效恢复机制的信任评估模型引入传统的DLS算法中，提出考虑失效恢复机制的动态级调度算法.

1 考虑失效恢复机制的信任评估模型

考虑上文中所述失效恢复机制的影响，使用三项事件描述节点的行为特性，对传统使用二项事件描述节点的行为特性的信任评估模型进行扩展，建立考虑失效恢复机制的信任评估模型.

在信任评估模型中，节点间信任关系分为3类.1）直接信任关系.如图1（a）所示，节点i和节点j 之间存在可作为可信度评估依据的直接交互，即可以设法估算出直接交互成功的概率，称为直接信任度评估，用θdt表示直接信任度.2）推荐信任关系.如图1（b）所示，当节点i和节点j 之间不存在可作为可信度评估的直接交互，而节点i可以获取其他节点（如：节点k）关于节点j 的可作为可信度评估依据的交互，这种需要通过第三方来建立的信任关系，称为推荐信任度评估，用θrt表示推荐信任度.3）混合信任关系.当同时存在直接信任关系和推荐信任关系时，节点间的信任关系称为混合信任关系，如图1（c）所示，需要将上述2种信任关系进行合并，得到总体的信任评估.如同在人际关系网络中，当个体之间进行信任评估时，往往既存在直接信任关系也存在推荐信任关系，不同的个体由于其个性、情绪等主观因素不同，具有不同的量化判断标准.本文选择线性函数作为2种信任关系的合并函数：

式中：θ为合并信任度，λ 表示个体对2种信任关系的调节因子，当0＜λ＜0.5时，表示个体更信任推荐信任关系；而当λ＞0.5时，表示个体相信直接交互经验超过其他个体的推荐经验.

图1 节点间的信任关系Fig.1 Trust relationship between nodes

1.1 时间因素

为体现信任评估的动态性，考虑时间因素对信任评估的影响.由人类对历史信息的认知方法可知，不同时期的历史交互信息对信任评估过程产生的影响是不同的，越接近的历史交互信息产生的影响越大，而时间跨度越长的历史交互信息产生的影响越小，直至对评估失去意义而不对其进行考虑.

采用时间分段概念［26］将时间段设置为1d，并引入时间影响力衰减因子η刻画不同时期历史交互信息的重要程度.设2个云资源节点i和节点j，使用三项事件（不可恢复失效／可恢复失效／交互成功）描述节点i和节点j 之间的交互结果.当节点i和节点j之间发生n 次交互时，设其中不可恢复失效的次数为α，可恢复失效的次数为β，交互成功的次数为γ.因此，将其划分为m 个时间段后，设其中第i个时间段的不可恢复失效、可恢复失效和交互成功次数分别为αi、βi 和γi，则考虑时间衰减因子η后的第i个时间段的不可恢复失效α（i）、可恢复失效β（i）和交互成功次数γ（i）如下式所示：

式中：0≤η≤1，η＝0表示只考虑最近一次的历史交互影响；而η＝1表示不考虑时间影响力衰减因子.

1.2 直接信任关系

直接信任是节点根据历史交互经验，对目标节点未来行为的主观期望，在这里运用贝叶斯算法估计直接信任度.

根据经验分析［27］，由不可恢复失效产生的因素可知，在一个时间段内不可恢复失效的概率可以认为是不变的.因此，设第i个时间段的不可恢复失效概率q0为常数：

同时，设第i个时间段内可恢复失效概率为qi，则第i个时间段的成功交互概率可以表示为

对于m 个时间段，设θ＝（θ1，…，θm）为随机变量，其验前分布为均匀分布，则其联合概率密度函数为

式中：Gm为m 维欧氏空间中的点集，Vm为Gm的勒贝格测度.为求得θm的贝叶斯估计，必须先求出｛θ1，…，θm｝的验后联合概率密度以及关于θm的验后边缘概率密度.

设样本集X＝｛X11，X12，X13；X21，X22，X23；…；Xm1，Xm2，Xm3｝，p＝1，2，…，m.其中Xp1表示时间段p 中不可恢复失效次数，Xp2表示时间段p中可恢复失效次数，Xp3表示时间段p 中成功交互次数.设x0为样本集X 的一个观察，且

设f（θ｜x0）为随机变量θ 的验后联合概率密度，p（θm｜x0）为θm的验后边缘概率密度，为θm的贝叶斯估计.

根据贝叶斯公式及式（5）得到验后联合概率密度为

根据上述讨论内容可知，P｛X ＝x0｜θ｝为

将式（7）代入式（6）可得

为计算式（8），引入恒等式：

式中：u和v 为正整数，B（u，v）为参数是u、v 的Beta函数，x 为自变量，0≤a＜1.设n（i）＝β（i）＋γ（i），i＝1，2，…，m，可得

综上可得θ＝｛θ1，…，θm｝的验后联合概率密度f（θ｜x0）为

θm的验后边缘概率密度p（θm｜x0）为

若不对不可恢复失效和可恢复失效进行区分，即把这2种失效都作为交互失败来处理，在这种情况下上面所得结果式（16）验后联合概率密度，式（17）验后边缘概率密度和式（18）贝叶斯估计就与伯努利概率模型中的结果完全吻合.

由式（18）可以看出，直接信任关系的评估与节点间的交互次数有关.虽然通过式（18）可以得到节点间的直接信任度，但是当节点间没有交互或者交互较少时，较少的样本数将不足以评估节点间的直接信任关系.

针对该问题，本文使用区间估计理论［28］对信任度的置信水平进行度量，设（θdt-δ，θdt＋δ）为直接信任度θdt的置信度为γ 的置信区间，δ 为可接受误差，则θdt的置信度为

由于区间估计的置信度与区间估计精度相互制约，因此，选定置信度阈值为γ0，通过增加总的交互次数n提高精度，直到达到可接受水平，即当γ≥γ0时，可以根据这时的直接交互信息进行信任度计算.此时的样本容量n0、可接受误差δ和置信度阈值γ0之间的关系如下：

通过上述分析可知，根据节点间直接交互样本的置信度值，可以将直接信任关系评估作如下设定：1）当节点间不存在直接交互或交互样本置信度值γ＜γ0时，先验分布选择无信息先验分布U（0，1），设定节点间的直接信任度θdt＝1／2；2）当交互样本置信度值γ≥γ0时，节点间的直接信任度θdt按照式（18）计算.

1.3 推荐信任关系

推荐信任关系由2 类或多类直接交互关系形成，由于推荐信任关系涉及多方实体的直接交互关系，对推荐信任关系的评估仍按照上文所述方法，但须考虑多个直接交互信息［29］.

设网络中节点i和节点k、节点j和节点k 之间的交互独立，交互次数分别为n1、n2，其中不可恢复失效次数分别为α1、α2，可恢复失效分别为β1、β2，交互成功次数分别为γ1、γ2.设第i个时间段的不可恢复失效、可恢复失效和交互成功次数分别为α1i、β1i、γ1i和α2i、β2i、γ2i，因而考虑时间衰减因子η 后的第i个时间段的不可恢复失效、可恢复失效和交互成功次数可以设为α（i）1、β（i）1、γ（i）1和α（i）2、β（i）2、γ（i）2.

设样本集的一个观察

取损失函数为二次损失函数，则为θ′m的贝叶斯估计，为节点i和节点j 之间的推荐信任度，即为上文中所述的θrt，满足下式：

节点可以通过搜索整个网络中的其他节点和目标节点的交互历史获得推荐信任度，然而也存在以下问题：1）当推荐交互关系的样本数较少时，无法使用式（26）对推荐信任关系进行评估；2）当推荐节点k不止一个时，搜索过多的推荐交互会增加整个网络的通信开销.对于上述问题，本文通过推荐交互关系的样本置信度进行设定：当推荐交互样本置信度值γ＜γ0时，设定推荐信任度θrt＝1／2，而当γ≥γ0时，即可停止搜索推荐节点，并通过累计不可恢复失效、可恢复失效和成功交互数推广式（26）计算推荐信任度θrt.

2 考虑失效恢复机制的动态级调度算法

根据第1章中讨论的考虑失效恢复机制的信任模型，对传统的DLS算法［30］进行扩展，针对基于有向无环图（directed acyclic graph，DAG）的云资源调度问题，将考虑失效恢复机制的信任评估模型引入传统的DLS算法中，提出考虑失效恢复机制的动态级调度算法.

DLS算法为静态启发式的表调度算法，其原理是：对于任务vi和资源mj，通过贪心方法查找具有最高动态级的任务-资源对，从而将基于DAG 的应用任务分配到异构的资源节点（如：云资源节点）上执行.其中任务-资源（vi-mj）对的动态级D（vi，mj）定义如下：

式中：S（vi）为任务静态级，在一个调度期间内为常数，指DAG 中从任务vi到终止节点的最大执行时间；Max｛tAi，j，tMj｝为资源mj的输入数据时间与应用任务vi的执行时间之间的较大者；Δ（vi，mj）表示资源mj的相对计算性能.

当任务调度到资源节点上执行时，可信度反映目标资源节点提供服务的可靠程度.DLS算法充分考虑了资源节点的异构特征，然而并未考虑云资源节点可信度对调度结果的影响.为解决该问题，Wang等［22-23］考虑节点间行为特性和历史交互信息，提出了可信动态级调度算法（Cloud-DLS算法），并应用到网格服务和云服务中，其动态级定义如下：

式中：R（vi，nj）表示云资源节点调度任务vi到云资源节点nj上时对nj可信度的评估.

然而，该算法并未考虑云环境下的失效恢复机制.在实际的云环境中，当某一云资源节点发生失效时，往往会导致整个任务的失败.引入失效恢复机制后，对于可恢复失效（如：网络瞬间堵塞、CPU 短时衰竭等失效问题），云资源节点可以通过运行失效恢复程序对已中止的任务进行恢复.节点执行子任务的过程被分为执行过程和恢复过程2 个部分.如图2所示，当子任务i在节点k 上执行时，第1次失效发生在t1时刻，在t2时刻该失效被恢复；第2次失效发生在t3时刻而在t4时刻被恢复，以此类推直至该任务执行完成或者由于失效不可恢复而终止.

对于网络中的节点k，失效恢复机制的相关参数如下：

1）失效恢复率xk.失效恢复具有一定的概率，为了描述失效的可恢复能力，定义随机变量：当节点k上第j 个失效可以恢复时，设＝0；当节点k上第j 个失效不可恢复时，设＝1.

图2 失效恢复机制下子任务i在节点k 上的执行过程Fig.2 Execution process with fault recovery mechanism

假定节点k的失效恢复率恒为xk，则对于任意第j次恢复过程，都有P｛X（j）k＝0｝＝xk，P｛X（j）k＝1｝＝1-xk.同时，失效恢复率xk越高，每一次失效恢复过程所需的时间也越长，即较高的失效恢复率会提高系统的时间花费.

2）最大失效恢复次数Nk（Nk≥1）.由于失效恢复程序的执行会给资源节点带来较大的服务开销，在以下3类情况下，资源节点k 上执行的任务将被终止，即任务完成、发生不可恢复失效或是超过最大失效恢复次数Nk.

本文引入失效恢复机制，提出云环境下考虑失效恢复机制的动态级调度算法（FR-DLS），对于任务vi和云资源节点nj，其可信动态级FR-DL（vi，mj）定义如下：

式中：TS（vi，nj，xk，Nk）表示在考虑失效恢复机制参数的情况下，云资源节点ns调度任务vi到云资源节点nj上时对nj可信度的评估，即式（1）中讨论的合并信任度θ.

3 仿真实验及结果分析

为验证所提出的信任评估模型和动态级调度算法，在PlanetLab 环境［31］中设计基于云仿真软件CloudSim［32］的实验平台.分布全球的计算机群项目PlanetLab始于2003 年，由普林斯顿大学、华盛顿大学、加州大学和Intel研究人员共同开发，其目标是提供一个用于开发下一代互联网技术的开放式全球性测试实验平台.云仿真软件CloudSim 是一个通用、可扩展的新型仿真框架，通过在离散事件模拟包SimJava上开发的函数库支持基于数据中心的虚拟化建模、仿真功能和云资源管理、云资源调度模拟.同时，CloudSim 为用户提供了一系列可扩展的实体和方法，用户根据自身的要求调用适当的API实现自定义的调度算法.

本文所有的仿真试验中，每组实验分为10次，最终结果采用平均值.相关实验参数设置如下：在PlanetLab的网络模拟实验环境中，节点数和节点之间的链路数预先给定，链路间的数据传输速度介于1～10 Mbit／s；由于算法的性能与应用任务的大小和通信／计算比rCC（communication to computation ratio）［32］有关，任务类型按照通信／计算比给出，rCC＞1表示该任务为通信密集型，而0＜rCC＜1则表示该任务为计算密集型.同时，设定用户任务在资源节点上的执行时间介于10～100s.其他实验参数设置如 下：λ＝0.8，η＝0.8［22-23］，δ＝0.1，γ0＝0.95.同时设置2 类恶意节点，分别占节点总数的20%和30%，在分配到任务时，2类恶意节点分别以80%和50%的概率执行任务失败.

3.1 失效恢复机制

在以下实验中，讨论失效恢复机制及其参数对信任评估的影响，并在不同任务数和不同节点数的情况下，比较DLS 算法、Cloud-DLS算法和本文所提出的FR-DLS算法的性能.

为考察失效恢复机制的有效性，对于不同类型的用户任务（rCC分别取0.1、1.0、10.0），讨论失效恢复率xk、最大失效恢复次数Nk对任务执行成功率ra（average ratio of successful execution）和任务完成时间ta（average completion time）的影响.实验环境参数设置如下：云资源节点数为200，链路数为200，任务数为50.

3.1.1 失效恢复率xk对于rCC分别取0.1、1.0、10.0的不同类型任务，讨论在不考虑最大失效恢复次数Nk的情况下，失效恢复率xk对任务执行成功率的影响.实验结果如图3 所示，当失效恢复率xk＝0时，表示未使用失效恢复机制，任务执行成功率相对较低.随着失效恢复率xk的增加，3 种类型任务的执行成功率都相应提高；而当失效恢复率xk＝1时，任务执行成功率相对较高，充分体现了失效恢复机制的有效性.

当失效恢复率xk＝1时，任务执行成功率并未达到100%.这是由于在不设置最大失效恢复次数的情况下，虽然可恢复失效可以通过恢复程序的不断执行得以恢复，使得任务执行完成，但如通信链路故障、软件故障等不可恢复失效并不能够被失效恢复机制所恢复.

讨论在设置最大失效恢复次数Nk＝3时，失效恢复率xk对任务执行成功率的影响，实验结果如图4所示.由图可见，随着失效恢复率xk的增加，3种类型任务的执行成功率增长速率较不限制最大失效恢复次数时缓慢.此外，rCC＝10.0时的任务执行成功率明显低于rCC＝0.1时，这是由于通信密集型任务有着较高的失效率，因此对于不同类型的任务，选取合适的失效恢复率十分重要.

图3 不同失效恢复率下平均任务执行成功率的比较（Nk 无约束）Fig.3 Comparison of average success rates of task execution under varying recoverability probability（Nk without constraint）

图4 不同失效恢复率下平均任务执行成功率的比较（Nk＝3）Fig.4 Comparison of average success rates of task execution under varying recoverability probability（Nk＝3）

图5 不同失效恢复率下平均任务完成时间的比较（Nk＝3）Fig.5 Comparison of average task completion time under varying recoverability probability（Nk＝3）

失效、恢复过程会给节点带来较大的服务开销，而提高失效恢复率也会使恢复过程所需的时间增加.为研究失效恢复率xk对任务完成时间的影响，比较随着xk逐步增长，不同类型任务的完成时间，设置最大失效恢复次数Nk＝3，实验结果如图5所示.当0＜xk＜0.6时，任务完成时间的增长速率较缓；而当xk＞0.6时，任务完成时间的增长速率相对较快；当xk＝1.0时，3种类型任务的完成时间急剧增长.可见，选择较高的失效恢复率在提高任务执行成功率的同时，也带来了较大的时间花费.

3.1.2 最大失效恢复次数Nk如前文所述，每一次失效、恢复都会给节点带来较大的服务开销.在某些情况下（见图2），失效恢复过程被不断执行多次，直至任务完成.这对系统的可用性有较大影响，因此有必要限定节点的失效恢复次数.本实验对于rCC分别为0.1、1.0和10.0的不同类型任务，考察最大失效恢复次数Nk对任务执行成功率和任务完成时间的影响，在以下实验中，失效恢复率xk设置为0.6.如图6所示，随着最大失效恢复次数Nk的增加，3种类型任务的执行成功率都有不同程度的提高.当Nk≤4时，执行成功率增长的较快；而当5≤Nk≤10时，执行成功率增长较缓，这说明大部分可恢复失效可以在最多执行4 次失效恢复过程后恢复.

图6 不同失效恢复次数下平均任务执行成功率的比较（xk＝0.6）Fig.6 Comparison of average success rates of task execution under varying number of recoverable failures（xk＝0.6）

如图7所示为随着最大失效恢复次数Nk的增加，rCC分别为0.1、1.0和10.0的不同类型任务的任务完成时间.由图可见，随着最大失效恢复次数Nk的增加，3种类型任务的完成时间都有不同程度的提高.当Nk≤5时，任务完成时间的增长速率较快；而当Nk趋向于10 时，任务完成时间的增长趋向平缓.该实验从另一方面证实了大部分可恢复失效可以在执行4～5次失效恢复过程后被恢复.

图7 不同失效恢复次数下平均任务完成时间的比较（xk＝0.6）Fig.7 Comparison of average task completion time under varying number of recoverable failures（xk＝0.6）

由上述实验结果可见，失效恢复机制可以显著地提高任务执行成功率，充分体现了失效恢复机制的有效性.与此同时，失效恢复机制也给系统带来了一定的服务开销和时间花费，因此，对于不同类型的任务，应当按照需要选择合适的失效恢复率和最大失效恢复次数.

3.2 不同任务数情况下的比较

本实验在网络中具有不同任务数的情况下，比较FR-DLS算法、Cloud-DLS算法和传统的DLS算法在任务执行成功率、平均调度长度la（average schedule length）和任务完成时间方面的性能.其中，xk和Nk分别被设置为0.6和3.实验环境参数设置如下：设定rCC＝1.0，云资源节点数为200，链路数为200，并随机产生拥有10～100个子任务数nt（number of tasks）的任务图.

图8 不同任务数下DLS、Cloud-DLS和FR-DLS的平均任务执行成功率比较Fig.8 Comparison of average success rates of task execution of DLS，Cloud-DLS and DLS-FR algorithms with varying numbers of tasks

图9 不同任务数下DLS、Cloud-DLS和FR-DLS的平均调度长度比较Fig.9 Comparison of average schedule lengths of DLS，Cloud-DLS and DLS-FR algorithms with varying numbers of tasks

图10 不同任务数下DLS、Cloud-DLS和FR-DLS的平均任务完成时间比较Fig.10 Comparison of average task completion time of DLS，Cloud-DLS and DLS-FR algorithms with varying numbers of tasks

实验结果如图8～10所示，由图可见，随着任务数的增加，3种算法的任务执行成功率都略有降低，而调度长度和任务完成时间则有不同程度的提高.其中，FR-DLS算法的调度长度和任务完成时间略高于Cloud-DLS 算法和DLS 算法.由图8 可以看出，FR-DLS算法的执行成功率远高于Cloud-DLS算法和DLS算法.结果表明：失效恢复机制在较小的服务开销和时间花费下可以有效地提高任务执行成功率.

3.3 不同节点数情况下的比较

本实验在网络中具有不同节点数的情况下，比较FR-DLS算法、Cloud-DLS算法和传统的DLS算法在任务执行成功率、调度长度和任务完成时间方面的性能.实验环境参数设置如下：设定rCC＝1，链路数为200，任务数为100，并随机产生拥有100～1 000个节点数nr（number of resource nodes）的随机网络.

实验结果如图11～13所示，由图可见，在不同节点数的情况下，可以得到与不同任务数时相类似的结论：在牺牲一定完成时间和调度长度的代价下，失效恢复机制可以显著地提高任务执行成功率，体现了该机制的有效性.

在不同任务数和不同节点数情况下，如表1所示为FR-DLS算法相对于Cloud-DLS算法和DLS算法在调度长度、任务执行时间和任务执行成功率方面的改善情况.

通过表1可以看出：1）任务调度在调度长度、执行时间和执行成功率方面存在权衡，无法达到多方面服务质量的同时提高，而是以某一部分服务质量为代价换取另一部分更高的服务需求；2）本文所提出FR-DLS算法的性能与云计算环境下的节点数、任务数和任务类型（rCC的取值）有关.其中，随着云环境中节点数增加，FR-DLS算法在可靠性方面提升的性能远高于其在任务完成时间和调度长度代价方面的所提升的性能，显示了FR-DLS算法在云计算环境下对于大规模任务的实用性.

图11 不同节点数下DLS、Cloud-DLS和FR-DLS的平均任务执行成功率比较Fig.11 Comparison of average success rates of task execution of DLS，Cloud-DLS and DLS-FR algorithms with varying numbers of resource nodes

表1 FR-DLS算法相对Cloud-DLS算法和DLS算法在调度长度、任务执行时间和任务执行成功率方面的增加情况（不同任务数和不同节点数）Tab.1 Comparison of Cloud-DLS algorithm and DLS algorithm in scheduling lengths，completion time and success rates of task execution with FR-DLS algorithm（varying numbers of tasks and resource nodes）%

图12 不同节点数下DLS、Cloud-DLS和FR-DLS的平均调度长度比较Fig.12 Comparison of average schedule lengths of DLS，Cloud-DLS and DLS-FR algorithms with varying numbers of resource nodes

图13 不同节点数下DLS、Cloud-DLS和FR-DLS的平均任务完成时间比较Fig.13 Comparison of average task completion time of DLS，Cloud-DLS and DLS-FR algorithms with varying numbers of resource nodes

4 结 语

本文将节点失效可恢复的情况引入到云服务可靠性分析中，在此基础上将原有的以二项事件（成功／失败）描述节点间交互结果的信任模型扩展为以三项事件（成功／可恢复失效／不可恢复失效）描述交互结果的信任评估模型，并提出了考虑失效恢复机制的可信动态级调度算法.仿真实验证实该算法能够为云环境中主体节点的信任决策提供有效的支持，有效地提高云服务的可靠性.同时，该算法允许资源所有者自行调节资源失效恢复次数限制和失效恢复率，从而增加了失效恢复机制的灵活性.

本文的进一步工作是将考虑云计算环境中的相关安全机制与时间花费、价格花费等服务质量因素相结合，同时将如链路故障、节点故障和云节点本身安全软件的部署等安全因素相结合，提出相应的任务调度算法，从不同角度满足用户对云服务可靠性、服务质量和服务花费的多方面要求.

（

）：

［1］BUYYA R，YEO C S.VENUGOPAL S，et al.Cloud computing 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］DARBHA S，AGRAWAL D P.Optimal scheduling algorithm for distributed memory machines ［J］.IEEE Transactions on Parallel and Distributed Systems，2002，9（1）：87-95.

［3］LEE Y C，ZOMAYA A Y.A novel state transition method for metaheuristic-based scheduling in heterogeneous computing systems［J］.IEEE Transactions on Parallel and Distributed Systems，2008，19（9）：1215-1223.

［4］ZHU D，MOSSE D，MELHEM R.Power-aware scheduling for and／or graphs in real-time systems［J］.IEEE Transactions on Parallel and Distributed Systems，2004，15（9）：849-864.

［5］KIM K H，BUYYA R，KIM J.Power aware scheduling of bag-of-tasks applications with deadline constraints on DVS-enabled clusters ［C］∥Proceedings of the 7th IEEE International Symposium on Cluster Computing and the Grid.Rio de janeiro：IEEE，2007：541-548.

［6］BUNDE D P.Power-aware scheduling for makespan and flow［J］.Journal of Scheduling，2009，12（5）：489-500.

［7］李茂胜，杨寿保，付前飞，等.基于赔偿的网格资源交易模型［J］.软件学报，2006，17（3）：472-480.LI Mao-sheng，YANG Shou-bao，FU Qian-fei，et al.A grid resource transaction model based on compensation［J］.Journal of Software，2006，17（3）：472-480.

［8］XU B M，ZHAO C Y，HU E Z，et al.Job scheduling algorithm based on Berger model in cloud environment［J］.Advances in Engineering Software，2011，42（3）：419-425.

［9］BUYYA R，MURSHED M M，ABRAMSON D，et al.Scheduling parameter sweep applications on global grids：a deadline and budget constrained cost-time optimization algorithm ［J］.Software Practice and Experi-ence，2005，35（5）：491-512.

［10］BLANCO C V，HUEDO E，MONTERO R S，et al.Dynamic provision of computing resources from grid infrastructures and cloud providers［C］∥Grid and Pervasive Computing Conference，Geneva：IEEE，2009：113-120.

［11］TOPCUOGLU H，HARIRI S，WU M Y.Performance-effective and low complexity task scheduling for heterogeneous computing ［J］.IEEE Transactions on Parallel and Distributed Systems，2002，13（3）：260-274.

［12］MEZMAZ M，MELAB N，KESSACI Y，et al.A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems［J］.Journal of Parallel and Distributed Computing，2011，71（10）：1497-1508.

［13］DOGAN A，OZGUNER，F.Reliable matching and scheduling of precedence constrained tasks in heterogeneous distributed computing［C］∥Proceedings of the 29th international conference on parallel processing，Toronto：IEEE，2000：307-314.

［14］DOGAN A，OZGUNER，F.Matching and scheduling algorithms for minimizing execution time and failure probability of applications in heterogeneous computing［J］.IEEE Transactions on Parallel and Distributed Systems，2002，13（3）：308-323.

［15］DAI Y S，XIE M.Reliability of grid service systems［J］.Computers and Industrial Engineering，2006，50（1／2）：130-147.

［16］LEVITIN G，DAI Y S.Service reliability and performance in grid system with star topology［J］.Reliability Engineering and System Safety，2007，92（1）：40-46.

［17］FOSTER I，ZHAO Y，RAICU I，et al.Cloud Computing and Grid Computing 360-Degree Compared［M］.Texa：IEEE Grid Computing Environments，2008：1014-1017.

［18］BLAZE M.Toward a broader view of security protocols［C］∥12th Cambridge International Workshop on Security Protocols，Cambridge：IEEE，2004：1014-1017.

［19］JOSANG A，OZGUNER F.Matching and scheduling of minimizing execution time and failure probability of applications in heterogeneous computing ［J］.IEEE Transactions on Parallel and Distributed Systems，2002，13（3）：308-323.

［20］JOSANG A.A logic for uncertain probabilities［J］.International Journal of Uncertainty，Fuzziness and Knowledge-Based Systems，2001，9（3）：279-311.

［21］WANG W，ZENG G S，YUAN L L.A reputation multi-agent system in semantic web［C］∥Proceedings of the 9th Pacific Rim International Workshop on Multi-Agents.Guilin：PRIMA，2006：211-219.

［22］WANG W，ZENG G S，TANG D Z，et al.Cloud-DLS：dynamic trusted scheduling for cloud computing［J］.Expert Systems with Applications，2012，39（5）：2321-2329.

［23］DAI Y S，WANG X L.Optimal resource allocation on grid systems for maximizing service reliability using a genetic algorithm［J］.Reliability Engineering and System Safety，2006，91（9）：1071-1082.

［24］TREASTER M.A survey of fault-tolerance and faultrecovery techniques in parallel systems ［R］.ACM Computing Research Repository（CoRR），2005：1-11.

［25］ABAWAJY J H.Fault-tolerant scheduling policy for grid computing systems［C］∥Proceedings of the 19th IEEE International conference on Parallel and Distributed Processing Symposium，New York：IEEE，2004：50-58.

［26］JOSANG A，ISMAIL R.The beta reputation system［C］∥Proceedings of the 15th Bled Conference on Electronic Commerce，Slovenia：Bled EC，2002：2502-2511.

［27］GUO S C，HUANG H Z，LIU Y.Modeling and analysis of grid service reliability considering fault recovery［J］.New Generation Computing，2011，29（4）：345-364.

［28］THOMAS L，JOHN S J.Bayesian methods：an analysis of statisticians and interdisciplinary ［M］.New York：Cambridge University Press，1999：341-355.

［29］SULISTIO A，CIBEJ U，VENUGOPAL S，et al.A tutorial for modeling and simulating data grids：an extension to Gridsim ［J］.Concurrency and Computation：Practice and Experience，2008，20（13）：1591-1609.

［30］ZHU M，GUO W，XIAO S L，et al.Availability-driven scheduling for real-time directed acyclic graph applications in optical grid［J］.Journal of Optical Communications and Networking，2010，2（7）：469-480.

［31］PETERSON L，BAVIER A，FIUCZYNSK M，et al.Towards a comprehensive PlanetLab architecture technical report PDN-05-030［R］.Sydney：PlanetLab Consortium，2005.

［32］CALHEIROS R N，RANJAN R，ROSE D，et al.CloudSim：a novel framework for modeling and simulation of cloud computing infrastructures and services［R］.Melbourne：Grid Computing and Distributed Systems Laboratory，the University of Melbourne，2009.