摘 要： 针对当前网格资源管理中任务与资源匹配的缺陷，基于信任效益函数和最小完成时间，提出了基于信任的Trust Mintime Min-Min算法。分析了传统的Min-Min算法，考虑Min-Min算法负载不平衡，对其在调度策略方面进行了改进。仿真实验表明，该算法不但可以有效地平衡负载，而且可以提高任务的完成率，兼顾计算的有效性和可靠性。
关键词： 网格计算；信任模型；资源调度；信任关系
当前计算网格中存在调度机制与信任机制分离。将信任机制与资源调度机制有效融合，可以为网格资源安全管理提供保障，使得资源调度更好地在动态、异构、开放的真实网格环境中有效运行。
目前相关的研究中对信任的定义还没有形成一致的见解，在信任的计算方法中不同的作者有不同的思路。其中具有代表性的研究包括：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）可靠性。长时间执行的任务有可能因为某个资源失效导致运行失败甚至重启，造成系统资源浪费和系统性能低下。本文量化资源可靠性为单位时间内失效概率。
任务信任属性指网格用户提交任务请求时，对任务运行的安全性和可靠性要求。分别采用任务安全级别与可靠性级别量化任务信任属性。
定义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上的预测执行时间。
(2)CSTART(j)：资源j最早可用时间。
以上这些数据可以通过网格中NWS(Network Weather Service)和MDS(Monitoring and Discovery Service)组件来获取。
定义MCT(i，j)的计算公式为:
MCT(i，j)=ETC(i，j)+CSTART(j) (9)
2 算法
首先将具有强信任关系和弱信任关系的任务各分为一类，把无信任关系的任务归为第三类；然后，先对有信任关系的任务进行调度，计算有信任关系的每个任务在各网格计算资源上的最大信任效益函数值，选择信任效益最大的任务—资源对进行映射；再计算无信任关系的任务在各网格计算资源上的最小完成时间，选择完成时间最小的任务―资源对进行映射。算法描述为：
Trust Mintime Min-Min()
输入：任务和资源信任信息，ETC矩阵
输出：任务映射方案map
初始化：令T为所有任务的集合，M为所有资源的集合，集合TR=?覫保存任务―资源对，变量k用于计数。
根据信任关系（strong、weak 、no）将任务集合T分为三个不相交的子集合class1，class2，classno
令k=1;
Repeat
if(classk不为空)
TR置为空；
for classk中每一个任务ti
for M中每一个资源mj
if资源mj能满足任务ti的信任需求
计算ti在mj上的信任效益
TrustUtil(i，j)；
endif
endfor
if所有资源均无法满足任务ti的信任需求
将ti从T中删除；
else 找出使任务的信任效益值最大的资源，
将此任务—资源对保存到TR中
endfor
从TR中找出信任值最大任务资源对(ti，mj)；
将ti分配到mj任务队列末尾，从classk中删除ti;
endif
if(classk为空)
K=k+1;
endif
until (k>2)
if (classno不为空)
for classno中的每个任务ti
for资源M中的每一个资源mj
计算MCT(i，j)
endfor
找到使任务的最小完成时间MCT最小的资
源，将此任务—资源对保存到TR中;
endfor
从TR中找出MCT最小的任务资源对(ti,mj);
将ti分配到mj任务队列末尾，从classno中删
除ti;
endif
until(classno为空)
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算法。
由于考虑了信任关系，将任务提交到信任度较高的资源上执行，如图2所示，Trust Mintime Min-Min算法大大提高了任务提交的成功率，资源也得到有效的利用。
图3和图4分别给出了在网格环境中正常运行和有10%的任务存在恶意请求的情况下的两种算法的Makespan。从图中可以明显看出，随着任务数目的增加，本文提出的Trust Mintime Min-Min算法在任务总的执行时间越来越少于Min-Min算法，特别是在网格环境中存在恶意行为的情况下更为明显。
仿真结果证明Trust Mintime Min-Min算法在资源负载、任务总的执行时间等方面较经典的Min-Min算法有所提高。考虑到信任关系，在一定程度上提高了网格系统的安全性和可靠性，保证了网格系统的正常运行。
参考文献
[1] AZZEDIN F，MAHESWARAN M.Integrating trust into gridresource 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 19th IEEE 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.