云計(jì)算環(huán)境下基于信任主體和效益值的動(dòng)態(tài)任務(wù)調(diào)度算法研究

吳 洲

(廣東松山職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)系，廣東 韶關(guān) 512126)

0 引言

云計(jì)算環(huán)境中各資源實(shí)體是異構(gòu)的、分布式的、相互獨(dú)立的，只有通過相互的信任關(guān)系，實(shí)體之間才能實(shí)現(xiàn)有效的互訪[1]。雖然面向服務(wù)的云計(jì)算資源管理基礎(chǔ)設(shè)施不斷完善，異構(gòu)環(huán)境任務(wù)調(diào)度算法研究逐步深入，但云計(jì)算資源管理系統(tǒng)中任務(wù)調(diào)度機(jī)制往往忽視了資源的安全性和可靠性對(duì)任務(wù)執(zhí)行結(jié)果的影響。

云計(jì)算安全系統(tǒng)的建立依賴于實(shí)體之間存在的各種信任形式。為了使云計(jì)算更安全、更具吸引力，用戶實(shí)體間的訪問控制、互信等問題顯得格外重要[2]。任務(wù)調(diào)度機(jī)制與信任機(jī)制的分離導(dǎo)致當(dāng)前的任務(wù)調(diào)度系統(tǒng)難以在開放、動(dòng)態(tài)真實(shí)的云計(jì)算環(huán)境中有效運(yùn)行[3-4]。因此，研究融入信任機(jī)制的云計(jì)算任務(wù)調(diào)度方法，形成信任驅(qū)動(dòng)的云計(jì)算任務(wù)調(diào)度算法具有重要的理論價(jià)值與現(xiàn)實(shí)意義[5-6]。

1 云計(jì)算的信任模型

信任模型主要是對(duì)資源之間的信任關(guān)系進(jìn)行評(píng)估，提供信任值的計(jì)算或者根據(jù)服務(wù)請(qǐng)求提供合適的應(yīng)用鏈[7-8]。為了更好地描述本文的信任模型，特進(jìn)行以下定義：

定義1：信任。信任可以描述為Trust=(A,L,V)，A={a1,a2,…,ak,…,am}是信任屬性集合，L={l1,l2,…,lk,…,ln}為信任等級(jí)的集合，V={v1,v2,…,vk,…,vm}是信任評(píng)估向量。

定義2：直接信任。其表示在給定的上下文中，一個(gè)資源節(jié)點(diǎn)根據(jù)直接接觸行為的歷史記錄而得出的對(duì)另外一個(gè)資源節(jié)點(diǎn)的信任程度。資源節(jié)點(diǎn)ri的直接信任度表示為Direct_Trust(ri)。

定義3：間接信任。其表示資源節(jié)點(diǎn)之間通過第三者的間接推薦形成的信任度。資源節(jié)點(diǎn)ri的間接信任度表示為Indirect_Trust(ri)。

2 信任度的評(píng)估

2.1 直接信任度

信任度是一個(gè)針對(duì)資源、資源提供者以及資源消費(fèi)者在某一時(shí)間段內(nèi)發(fā)生的交易行為所形成的全局評(píng)價(jià)[9-10]。云計(jì)算資源節(jié)點(diǎn)之間的直接信任度由用戶根據(jù)以往交往的情況計(jì)算[11]。因此，本文引入了衰減函數(shù)att_Trust(i,t)。資源節(jié)點(diǎn)ri對(duì)資源節(jié)點(diǎn)rj的信任度衰減函數(shù)att_Trust(i,t)為：

att_Trust(i,t)=γet-tij

(1)

其中，t是當(dāng)前時(shí)間，tij是最后修改的時(shí)間或節(jié)點(diǎn)ri和節(jié)點(diǎn)rj之間最后交往的時(shí)間。

信任機(jī)制中的信任關(guān)系主要包括兩個(gè)方面：直接信任關(guān)系和間接信任關(guān)系。資源節(jié)點(diǎn)ri的直接可信度公式為：

(2)

2.2 間接信任度

資源節(jié)點(diǎn)ri的間接可信度可以描述為：

Indirect_Trust(i,t)=

(3)

其中，dij是與資源節(jié)點(diǎn)ri與rj均有直接信任關(guān)系的資源數(shù)，di為與資源節(jié)點(diǎn)ri有間接信任關(guān)系的資源數(shù)。節(jié)點(diǎn)rk被視為資源節(jié)點(diǎn)ri與rj的推薦實(shí)體。

對(duì)于間接信任度，由于存在惡意推薦的可能，因此需要設(shè)定一個(gè)信任閾值Th_Trust。計(jì)算出來的間接信任度與信任閾值進(jìn)行比較，如果該值大于信任閾值就認(rèn)為節(jié)點(diǎn)是可信的，否則認(rèn)為是惡意推薦的。

Indirect_Trust(i)=

(4)

2.3 綜合信任度

對(duì)于資源節(jié)點(diǎn)，任務(wù)完成率越高，其可信任程度越高。因此，本文定義信任懲罰函數(shù)，信任懲罰函數(shù)計(jì)算公式為：

(5)

結(jié)合資源的直接信任、間接信任和信任懲罰函數(shù)，得到資源節(jié)點(diǎn)ri的綜合可信度函數(shù)如下：

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

(6)

其中，ST(i)為資源節(jié)點(diǎn)的綜合可信值，ω1、ω2和ω3分別為直接信任、間接信任和信任懲罰函數(shù)的權(quán)重系數(shù)，ω1,ω2,ω3∈[0,1]，ω1>ω2>ω3，且ω1+ω2+ω3=1。

3 基于信任機(jī)制的任務(wù)調(diào)度算法

本文基于信任主體和效益值，提出一種動(dòng)態(tài)信任效益任務(wù)調(diào)度算法(Dynamic Trust Benefit Task Scheduling，DTBTS)。信任效益是指所有被成功調(diào)度的任務(wù)所獲得的信任效益均值，是調(diào)度算法性能系統(tǒng)級(jí)評(píng)價(jià)指標(biāo)，獲得平均信任效益大的調(diào)度算法能夠?yàn)橄到y(tǒng)提供較好的信任服務(wù)。為了更好地設(shè)計(jì)和描述基于信任驅(qū)動(dòng)的云計(jì)算任務(wù)調(diào)度模型，本文特進(jìn)行以下一般性定義：

定義4給定m個(gè)異構(gòu)計(jì)算資源組成的網(wǎng)格計(jì)算系統(tǒng)G={r1,r2,…,ri,…,rm}，n個(gè)獨(dú)立任務(wù)組成的任務(wù)集合S={s1,s2,…,sj,…,sn}。任務(wù)調(diào)度和資源分配的映射關(guān)系為：δ:S→R。

定義5在云計(jì)算系統(tǒng)中，如果任務(wù)sj被調(diào)度到資源ri上，那么δ(i)=j，δ(i,j)=1；否則δ(i,j)=0。

定義6在任務(wù)調(diào)度和資源分配的映射關(guān)系δ下，如果任務(wù)完成率為η，則云計(jì)算的任務(wù)調(diào)度信任效益值B_Trust為：

(7)

4 仿真及結(jié)果分析

由于CloudSim[12]提供了一系列API，可以方便地隨機(jī)生成不同的主機(jī)處理能力、網(wǎng)絡(luò)帶寬、通信延遲、數(shù)據(jù)傳輸量和計(jì)算量等參數(shù)，本文采用CloudSim云計(jì)算任務(wù)調(diào)度模擬器對(duì)DTBTS算法、TD_Max-min算法[5]、TDLAC算法[7]和CCIDTM算法[9]進(jìn)行模擬實(shí)驗(yàn)。仿真實(shí)驗(yàn)考察20～30個(gè)計(jì)算資源組成的云計(jì)算系統(tǒng)對(duì)50～500個(gè)獨(dú)立任務(wù)構(gòu)成的任務(wù)集合的調(diào)度情況，每次實(shí)驗(yàn)平均仿真100次。在實(shí)驗(yàn)中資源數(shù)量和任務(wù)數(shù)量分別用m和n表示。

本節(jié)將從任務(wù)完成時(shí)間、任務(wù)完成率、信任效益值等多個(gè)性能指標(biāo)對(duì)基于信任機(jī)制的DTBTS算法進(jìn)行綜合評(píng)價(jià)。任務(wù)完成率是指調(diào)度過程中能夠成功完成的任務(wù)數(shù)的比率。

表1列舉的是DTBTS算法分別在10個(gè)資源節(jié)點(diǎn)上直接信任度、間接信任度和綜合信任度的值。

表1 DTBTS算法在資源節(jié)點(diǎn)上的信任評(píng)價(jià)

圖1 在不同資源數(shù)和任務(wù)數(shù)時(shí)任務(wù)完成時(shí)間的比較

圖1描述的是資源數(shù)分別為20和30 時(shí)，在不同任務(wù)數(shù)量時(shí)四種任務(wù)調(diào)度算法對(duì)應(yīng)的任務(wù)完成時(shí)間比較。圖2描述的是資源數(shù)分別為20和30 時(shí)，在不同任務(wù)數(shù)量時(shí)四種任務(wù)調(diào)度算法對(duì)應(yīng)的任務(wù)完成率比較。從圖1的實(shí)驗(yàn)結(jié)果不難看出：隨著云計(jì)算的任務(wù)數(shù)量不斷增加，系統(tǒng)的任務(wù)完成時(shí)間也在逐漸遞增，在絕大多數(shù)情況下DTBTS算法的任務(wù)完成時(shí)間明顯少于其他三種任務(wù)調(diào)度算法。在圖1(a)中，當(dāng)任務(wù)數(shù)超過400時(shí)，DTBTS算法的優(yōu)勢(shì)表現(xiàn)得非常明顯，其任務(wù)完成時(shí)間比CCIDTM算法、TD_Max-min算法和TDLAC算法分別平均少7.14%、3.81%、2.98%；在圖1(b)中，當(dāng)任務(wù)數(shù)超過220時(shí)，DTBTS算法的優(yōu)勢(shì)表現(xiàn)得非常明顯，其任務(wù)完成時(shí)間比CCIDTM算法、TD_Max-min算法和TDLAC算法分別平均少11.2%、6.54%、4.76%。

從圖2的實(shí)驗(yàn)結(jié)果不難看出：在任務(wù)完成率方面，DTBTS算法表現(xiàn)出來的性能明顯優(yōu)于其他三種任務(wù)調(diào)度算法。在圖2(a)中，當(dāng)系統(tǒng)的任務(wù)數(shù)少于280時(shí)，DTBTS算法的任務(wù)完成率是100%，其最小任務(wù)完成率大約是97.8%，當(dāng)網(wǎng)格系統(tǒng)的任務(wù)規(guī)模少于200時(shí)，四種算法的任務(wù)完成率都是100%，其他三種任務(wù)調(diào)度算法的任務(wù)完成率在算法執(zhí)行期間都維持在96%以上；在圖2(b)中，當(dāng)系統(tǒng)的任務(wù)數(shù)少于350時(shí)，DTBTS算法和TDLAC算法的任務(wù)完成率是100%，DTBTS算法的最小任務(wù)完成率大約是98.7%，當(dāng)系統(tǒng)的任務(wù)規(guī)模少于280時(shí)，四種算法的任務(wù)完成率都是100%，其他三種任務(wù)調(diào)度算法的任務(wù)完成率在算法執(zhí)行期間都維持在97%以上。DTBTS算法的任務(wù)完成率高說明調(diào)度過程中成功匹配的任務(wù)數(shù)多，信任關(guān)系無法滿足而被迫丟棄的任務(wù)數(shù)目較少。

圖3描述的是資源數(shù)分別為20和30 時(shí)，在不同任務(wù)數(shù)量時(shí)DTBTS算法和TD_Max-min算法的信任效益值比較。從圖3的實(shí)驗(yàn)結(jié)果可以看出：在算法獲得的信任效益值方面，本文設(shè)計(jì)的DTBTS算法明顯優(yōu)于TD_Max-min算法,并且DTBTS算法的平均信任效益值要比TD_Max-min算法提高8.72%。DTBTS算法的信任效益值波動(dòng)相對(duì)較小，表明任務(wù)數(shù)的變化對(duì)該算法的信任效益值影響較小。DTBTS算法的平均信任效益值相對(duì)較大，說明這種該任務(wù)調(diào)度算法在任務(wù)映射后執(zhí)行越穩(wěn)定，執(zhí)行結(jié)果愈加可信。

圖2 在不同資源數(shù)和任務(wù)數(shù)時(shí)任務(wù)完成率比較

圖3 DTBTS算法和TD_Max-min算法的信任效益值比較

5 結(jié)論

為解決云計(jì)算的動(dòng)態(tài)性和不確定性帶來的安全問題，提出了云計(jì)算環(huán)境下任務(wù)調(diào)度過程中的信任關(guān)系綜合評(píng)估模型。本文詳細(xì)闡述了云計(jì)算中信任的基本概念，確立了任務(wù)與信任主體之間的直接信任度、間接信任度和綜合信任度，采用信任效益函數(shù)量化不同信任關(guān)系下調(diào)度結(jié)果對(duì)任務(wù)完成時(shí)間與完成率的影響。仿真實(shí)驗(yàn)結(jié)果顯示該算法在任務(wù)完成時(shí)間、任務(wù)完成率、信任效益值等多個(gè)性能方面均優(yōu)于其他傳統(tǒng)的任務(wù)調(diào)度算法。