云计算环境下基于信任主体和效益值的动态任务调度算法研究

吴 洲

(广东松山职业技术学院 计算机系，广东 韶关 512126)

0 引言

云计算环境中各资源实体是异构的、分布式的、相互独立的，只有通过相互的信任关系，实体之间才能实现有效的互访[1]。虽然面向服务的云计算资源管理基础设施不断完善，异构环境任务调度算法研究逐步深入，但云计算资源管理系统中任务调度机制往往忽视了资源的安全性和可靠性对任务执行结果的影响。

云计算安全系统的建立依赖于实体之间存在的各种信任形式。为了使云计算更安全、更具吸引力，用户实体间的访问控制、互信等问题显得格外重要[2]。任务调度机制与信任机制的分离导致当前的任务调度系统难以在开放、动态真实的云计算环境中有效运行[3-4]。因此，研究融入信任机制的云计算任务调度方法，形成信任驱动的云计算任务调度算法具有重要的理论价值与现实意义[5-6]。

1 云计算的信任模型

信任模型主要是对资源之间的信任关系进行评估，提供信任值的计算或者根据服务请求提供合适的应用链[7-8]。为了更好地描述本文的信任模型，特进行以下定义：

定义1：信任。信任可以描述为Trust=(A,L,V)，A={a1,a2,…,ak,…,am}是信任属性集合，L={l1,l2,…,lk,…,ln}为信任等级的集合，V={v1,v2,…,vk,…,vm}是信任评估向量。

定义2：直接信任。其表示在给定的上下文中，一个资源节点根据直接接触行为的历史记录而得出的对另外一个资源节点的信任程度。资源节点ri的直接信任度表示为Direct_Trust(ri)。

定义3：间接信任。其表示资源节点之间通过第三者的间接推荐形成的信任度。资源节点ri的间接信任度表示为Indirect_Trust(ri)。

2 信任度的评估

2.1 直接信任度

信任度是一个针对资源、资源提供者以及资源消费者在某一时间段内发生的交易行为所形成的全局评价[9-10]。云计算资源节点之间的直接信任度由用户根据以往交往的情况计算[11]。因此，本文引入了衰减函数att_Trust(i,t)。资源节点ri对资源节点rj的信任度衰减函数att_Trust(i,t)为：

att_Trust(i,t)=γet-tij

(1)

其中，t是当前时间，tij是最后修改的时间或节点ri和节点rj之间最后交往的时间。

信任机制中的信任关系主要包括两个方面：直接信任关系和间接信任关系。资源节点ri的直接可信度公式为：

(2)

2.2 间接信任度

资源节点ri的间接可信度可以描述为：

Indirect_Trust(i,t)=

(3)

其中，dij是与资源节点ri与rj均有直接信任关系的资源数，di为与资源节点ri有间接信任关系的资源数。节点rk被视为资源节点ri与rj的推荐实体。

对于间接信任度，由于存在恶意推荐的可能，因此需要设定一个信任阈值Th_Trust。计算出来的间接信任度与信任阈值进行比较，如果该值大于信任阈值就认为节点是可信的，否则认为是恶意推荐的。

Indirect_Trust(i)=

(4)

2.3 综合信任度

对于资源节点，任务完成率越高，其可信任程度越高。因此，本文定义信任惩罚函数，信任惩罚函数计算公式为：

(5)

结合资源的直接信任、间接信任和信任惩罚函数，得到资源节点ri的综合可信度函数如下：

ST(i)=ω1×Direct_Trust(i)+ω2×Indirect_Trust(i)+ω3×Penalty_Trust(i)

(6)

其中，ST(i)为资源节点的综合可信值，ω1、ω2和ω3分别为直接信任、间接信任和信任惩罚函数的权重系数，ω1,ω2,ω3∈[0,1]，ω1>ω2>ω3，且ω1+ω2+ω3=1。

3 基于信任机制的任务调度算法

本文基于信任主体和效益值，提出一种动态信任效益任务调度算法(Dynamic Trust Benefit Task Scheduling，DTBTS)。信任效益是指所有被成功调度的任务所获得的信任效益均值，是调度算法性能系统级评价指标，获得平均信任效益大的调度算法能够为系统提供较好的信任服务。为了更好地设计和描述基于信任驱动的云计算任务调度模型，本文特进行以下一般性定义：

定义4给定m个异构计算资源组成的网格计算系统G={r1,r2,…,ri,…,rm}，n个独立任务组成的任务集合S={s1,s2,…,sj,…,sn}。任务调度和资源分配的映射关系为：δ:S→R。

定义5在云计算系统中，如果任务sj被调度到资源ri上，那么δ(i)=j，δ(i,j)=1；否则δ(i,j)=0。

定义6在任务调度和资源分配的映射关系δ下，如果任务完成率为η，则云计算的任务调度信任效益值B_Trust为：

(7)

4 仿真及结果分析

由于CloudSim[12]提供了一系列API，可以方便地随机生成不同的主机处理能力、网络带宽、通信延迟、数据传输量和计算量等参数，本文采用CloudSim云计算任务调度模拟器对DTBTS算法、TD_Max-min算法[5]、TDLAC算法[7]和CCIDTM算法[9]进行模拟实验。仿真实验考察20～30个计算资源组成的云计算系统对50～500个独立任务构成的任务集合的调度情况，每次实验平均仿真100次。在实验中资源数量和任务数量分别用m和n表示。

本节将从任务完成时间、任务完成率、信任效益值等多个性能指标对基于信任机制的DTBTS算法进行综合评价。任务完成率是指调度过程中能够成功完成的任务数的比率。

表1列举的是DTBTS算法分别在10个资源节点上直接信任度、间接信任度和综合信任度的值。

表1 DTBTS算法在资源节点上的信任评价

图1 在不同资源数和任务数时任务完成时间的比较

图1描述的是资源数分别为20和30 时，在不同任务数量时四种任务调度算法对应的任务完成时间比较。图2描述的是资源数分别为20和30 时，在不同任务数量时四种任务调度算法对应的任务完成率比较。从图1的实验结果不难看出：随着云计算的任务数量不断增加，系统的任务完成时间也在逐渐递增，在绝大多数情况下DTBTS算法的任务完成时间明显少于其他三种任务调度算法。在图1(a)中，当任务数超过400时，DTBTS算法的优势表现得非常明显，其任务完成时间比CCIDTM算法、TD_Max-min算法和TDLAC算法分别平均少7.14%、3.81%、2.98%；在图1(b)中，当任务数超过220时，DTBTS算法的优势表现得非常明显，其任务完成时间比CCIDTM算法、TD_Max-min算法和TDLAC算法分别平均少11.2%、6.54%、4.76%。

从图2的实验结果不难看出：在任务完成率方面，DTBTS算法表现出来的性能明显优于其他三种任务调度算法。在图2(a)中，当系统的任务数少于280时，DTBTS算法的任务完成率是100%，其最小任务完成率大约是97.8%，当网格系统的任务规模少于200时，四种算法的任务完成率都是100%，其他三种任务调度算法的任务完成率在算法执行期间都维持在96%以上；在图2(b)中，当系统的任务数少于350时，DTBTS算法和TDLAC算法的任务完成率是100%，DTBTS算法的最小任务完成率大约是98.7%，当系统的任务规模少于280时，四种算法的任务完成率都是100%，其他三种任务调度算法的任务完成率在算法执行期间都维持在97%以上。DTBTS算法的任务完成率高说明调度过程中成功匹配的任务数多，信任关系无法满足而被迫丢弃的任务数目较少。

图3描述的是资源数分别为20和30 时，在不同任务数量时DTBTS算法和TD_Max-min算法的信任效益值比较。从图3的实验结果可以看出：在算法获得的信任效益值方面，本文设计的DTBTS算法明显优于TD_Max-min算法,并且DTBTS算法的平均信任效益值要比TD_Max-min算法提高8.72%。DTBTS算法的信任效益值波动相对较小，表明任务数的变化对该算法的信任效益值影响较小。DTBTS算法的平均信任效益值相对较大，说明这种该任务调度算法在任务映射后执行越稳定，执行结果愈加可信。

图2 在不同资源数和任务数时任务完成率比较

图3 DTBTS算法和TD_Max-min算法的信任效益值比较

5 结论

为解决云计算的动态性和不确定性带来的安全问题，提出了云计算环境下任务调度过程中的信任关系综合评估模型。本文详细阐述了云计算中信任的基本概念，确立了任务与信任主体之间的直接信任度、间接信任度和综合信任度，采用信任效益函数量化不同信任关系下调度结果对任务完成时间与完成率的影响。仿真实验结果显示该算法在任务完成时间、任务完成率、信任效益值等多个性能方面均优于其他传统的任务调度算法。