信任驱动的资源调度算法*

王 磊，解 福

（山东师范大学 信息科学与工程学院，山东 济南250014）

当前计算网格中存在调度机制与信任机制分离。将信任机制与资源调度机制有效融合，可以为网格资源安全管理提供保障，使得资源调度更好地在动态、异构、开放的真实网格环境中有效运行。

目前相关的研究中对信任的定义还没有形成一致的见解，在信任的计算方法中不同的作者有不同的思路。其中具有代表性的研究包括：AZZEDIN与MAHESWARAN[1]等人首次将“信任”融入网格资源管理，提出考虑信任因素的作业调度会引入额外负载并设计了负载最小化算法。HUMPHREY[2]等人对具有安全意识的网格计算模型进行了深入研究。ABAWAJY[3]等人提出的DFTS分布式失效容忍调度策略，通过复制作业的多个副本到不同站点保证作业在网格环境下可靠进行。DOGAN[4]和SONG Shan Shan[5]提出了最小化失效率的网格信任调度框架和调度算法。唐小勇[6]等人在Buyya设计的GRACE网格资源管理框架下，提出反映信任值动态变化规律的信任函数，建立基于行为的网格信任机制，并将其应用到网格经济模型中的DBC调度算法中。

本文采用参考文献[7]中给出的信任定义，将信任效益值和最小完成时间作为调度目标函数，对资源进行分配，提出了基于信任的网格资源调度算法Trust Mintime Min-Min算法。

1 概念与问题描述

1.1 信任模型

本文采用的信任定义为：

定义1信任：由信任值表征的客观实体的身份和行为的可信度评估，信任值取决于实体可靠性、诚信和性能等。计算网格信任模型主要由资源信任属性、任务信任属性及其相互间信任关系构成。资源信任属性包含两方面：

（1）安全性。衡量网格资源对任务和数据的真实性、保密性和完整性的保障程度。采用资源安全级别量化资源安全属性。

（2）可靠性。长时间执行的任务有可能因为某个资源失效导致运行失败甚至重启，造成系统资源浪费和系统性能低下。本文量化资源可靠性为单位时间内失效概率。

任务信任属性指网格用户提交任务请求时，对任务运行的安全性和可靠性要求。分别采用任务安全级别与可靠性级别量化任务信任属性。

1.2 信任效益函数

本文采用参考文献[8]定义信任关系为 strong、weak、no的任务Ti在资源Rj上执行的原始安全性效益函数为：

同理，将信任关系为 strong、weak、no的任务 Ti在资源Rj上执行的原始可靠性效益函数定义为：

其中，任务可靠性需求 JRi∈（0，1），而资源可靠性 RRij由任务Ti和资源Rj共同决定。设调度开始时每个计算资源固有失效率为FRj。随着时间增加，失效的概率逐渐增大，可靠度减小。任务 Ti在 Rj上的完成时间为 CTij，则可靠度为 RRij=exp（-CTij×FRj）。

可以定义任务Ti在资源Rj上所获得的信任效益函数如式（7）所示，其中，w1和 w2是安全性和可靠性上的重要性权值。可知，信任效益函数值越大，任务映射后执行越稳定，执行结果愈加可信。

定义2信任驱动的网格资源调度问题[7]：给定m个异构计算资源组成的网格环境 M={m1，m2，…，mm}，n个元任务构成的任务集合 T={t1，t2，…，tn}，求映射方案map=(a，s)(其中 a：T→M为表示资源分配的映射，a(i)=j表示将 ti分配到 mj上，s：{(i，a(i))|i∈T}→N={1，2，3，…}表示在资源上的任务调度函数，s(i，j)=k表示在计算资源mj上第k个执行的任务是 ti），使得：

比如傅雷翻译巴尔扎克的长篇小说的书名《La Cousine Bette》、《Le Pere Goriot》，本来，前者应译为《表妹贝德》或《堂妹贝德》,后者译为《高里奥老爹》或《高里奥大伯》。傅雷考虑到中文名字的特点，仔细揣摩了全书内容后，把前者译为《贝姨》，后者译为《高老头》，改译后在文字表达上符合中文读者的文化背景，从而缩短了译语读者与译作的距离，而且还传递了主人公在作品中扮演的特定角色，堪称有意识误译的成功佳例。

定义3信任关系：根据调度过程中任务对资源信任值的要求，二者之间的信任关系可以分为强信任关系、弱信任关系和无信任关系。

（1）强信任关系指调度时任务的安全性和可靠性需求级别必须高于所分配资源的固有属性值。如果不存在满足条件的资源，则此任务将被放弃。其最终效益值或者为最大，或者为零。

（2）弱信任关系指调度算法尽量保证任务信任属性值高于资源的信任属性值，此时可获得最大效益；否则，可以降低任务的信任需求，但是其信任效益值随之下降。

（3）无信任关系指在调度过程中不考虑任务和资源间的信任关系，仅以完成时间最小为目标。

定义4资源调度的最小完成时间计算：在网格环境中，考虑任务之间没有通信和数据依赖的集合，即元任务。那么要将 m个资源 M={m1，m2，…，mm}以合理的方式调度到 n个元任务 T={t1，t2，…，tn}的过程中，目的是得到尽可能小的总执行时间(makespan)。n个元任务在m个资源的预测执行时间ETC(Expected Time to Compute)是一个m×n的矩阵，矩阵中的每一行代表某一个任务在m个资源上的不同时间，每一列代表某一资源上的m个任务的不同执行时间。

第i个任务在第j个资源上的预测最小完成时间(Minimum Completion Time)记 为 MCT(i，j)， 则 n 个 元 任务在m个资源上的预测最小完成时间也是一个 m×n的矩阵，笔者仅考虑以下决定因素：

(1)ETC(i，j)：任务 i在资源 j上的预测执行时间。

以上这些数据可以通过网格中NWS(Network Weather Service)和MDS(Monitoring and Discovery Service)组件来获取。

定义 MCT(i，j)的计算公式为：

2 算法

首先将具有强信任关系和弱信任关系的任务各分为一类，把无信任关系的任务归为第三类；然后，先对有信任关系的任务进行调度，计算有信任关系的每个任务在各网格计算资源上的最大信任效益函数值，选择信任效益最大的任务—资源对进行映射；再计算无信任关系的任务在各网格计算资源上的最小完成时间，选择完成时间最小的任务―资源对进行映射。算法描述为：

Trust Mintime Min-Min()

输入：任务和资源信任信息，ETC矩阵

输出：任务映射方案map

初始化：令T为所有任务的集合，M为所有资源的集合，集合TR=Ø保存任务―资源对，变量k用于计数。

根据信任关系（strong、weak、no）将任务集合 T分为三个不相交的子集合class1，class2，classno

令k=1;

3 仿真实验

3.1 实验内容与设置

仿真试验考察了20～50个计算资源组成的网格系统对1～200个独立任务构成集合调度的情况。

资源安全级别JR和任务安全级别JS在这4个级别{poor，low，medium，high}内随机产生。资源的单位时间失效率FR在区间[0.000 1，0.001 5]上随机生成。任务需求级别JR在强、弱信任关系的情况下根据公式JR=(0.9+0.1×rand)×exp(10-4×任务数/主机数)生成。 根据参考文献[8]中方案取 μtask=μmach=100，Vtask=Vmach=0.6。 设置变量1≤Vq≤4控制任务与资源间的信任关系，生成一个[0，1]间随机数，如果该数小于 0.25 Vq，则称两者具有强信任关系；该数小于0.5 Vq为弱信任关系；否则为无信任关系。信任效益函数式(7)中w1和w2均取值为0.5。

3.2 实验结果和性能分析

设置200个独立任务在50个异构资源进行调度。如图1所示，显示了30个资源负载情况，可以看出本文提出的Trust Mintime Min-Min算法负载平衡性明显优于传统的Min-Min算法。

图1 资源负载平衡

由于考虑了信任关系，将任务提交到信任度较高的资源上执行，如图2所示，Trust Mintime Min-Min算法大大提高了任务提交的成功率，资源也得到有效的利用。

图2 任务提交成功率

图3和图4分别给出了在网格环境中正常运行和有10%的任务存在恶意请求的情况下的两种算法的Makespan。从图中可以明显看出，随着任务数目的增加，本文提出的Trust Mintime Min-Min算法在任务总的执行时间越来越少于Min-Min算法，特别是在网格环境中存在恶意行为的情况下更为明显。

仿真结果证明Trust Mintime Min-Min算法在资源负载、任务总的执行时间等方面较经典的Min-Min算法有所提高。考虑到信任关系，在一定程度上提高了网格系统的安全性和可靠性，保证了网格系统的正常运行。

图3 不存在恶意任务请求的Makespan

图4 存在10%的恶意任务请求的Makespan

[1]AZZEDIN F，MAHESWARAN M.Integrating trust into grid resource management systems[C].2002 International Conference on Parallel Processing(ICPP 2002).Canada：IEEE Press 2002：47-54.

[2]HUMPHREY M，THOMPSON M R.Security implication of typical grid computing usage scenario[C].IEEE Proc HPDC.USA：IEEE Press，2001：95-103.

[3]ABAWAJY J H.Fault-tolerant scheduling policy for grid computing systems[C].Proc IPDPS 2004.USA：IEEE Press，2004：50-58.

[4]DOGAN A，OZGUNER F.Matching and scheduling algorithms for minimizing execution time and failure probalitity of applications in heterogeneous computing[J].IEEE Trans on Parallel and Distributed Systems，2002，13(3)：308-323.

[5]SONG S，KWOK Y K，HWANG K.Trusted job scheduling in open computional grids：Security-driven heuristics and a fast genetic algorithm[C].proceedings of the 19thIEEE International parallel&Distributed Proceessing Symposium(IPDPS-2005).Denver，CO，USA：IEEE Press，2005：33-40.

[6]唐小勇，李肯立.网格经济模型中基于信任机制的调度算法[J].计算机应用研究，2008，25(8)：2357-2361.

[7]张伟哲，刘欣然，云小春，等.信任驱动的网格作业调度算法[J].通信学报，2006，27(2)：73-79.

[8]SHOUKAT A，HOWARD J S，MUTHUCUMARU M，et al.Task execution time modeling for heterogeneous computing systems[C].IPDPS Workshop on Heterogeneous Computing.Cancun，Mexic：IEEE Press，2000：185-199.