云計算環(huán)境下基于信任主體和效益值的動態(tài)任務調度算法研究

吳 洲

(廣東松山職業(yè)技術學院 計算機系，廣東 韶關 512126)

0 引言

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

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

1 云計算的信任模型

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

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

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

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

2 信任度的評估

2.1 直接信任度

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

att_Trust(i,t)=γet-tij

(1)

其中，t是當前時間，tij是最后修改的時間或節(jié)點ri和節(jié)點rj之間最后交往的時間。

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

(2)

2.2 間接信任度

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

Indirect_Trust(i,t)=

(3)

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

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

Indirect_Trust(i)=

(4)

2.3 綜合信任度

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

(5)

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

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

(6)

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

3 基于信任機制的任務調度算法

本文基于信任主體和效益值，提出一種動態(tài)信任效益任務調度算法(Dynamic Trust Benefit Task Scheduling，DTBTS)。信任效益是指所有被成功調度的任務所獲得的信任效益均值，是調度算法性能系統(tǒng)級評價指標，獲得平均信任效益大的調度算法能夠為系統(tǒng)提供較好的信任服務。為了更好地設計和描述基于信任驅動的云計算任務調度模型，本文特進行以下一般性定義：

定義4給定m個異構計算資源組成的網格計算系統(tǒng)G={r1,r2,…,ri,…,rm}，n個獨立任務組成的任務集合S={s1,s2,…,sj,…,sn}。任務調度和資源分配的映射關系為：δ:S→R。

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

定義6在任務調度和資源分配的映射關系δ下，如果任務完成率為η，則云計算的任務調度信任效益值B_Trust為：

(7)

4 仿真及結果分析

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

本節(jié)將從任務完成時間、任務完成率、信任效益值等多個性能指標對基于信任機制的DTBTS算法進行綜合評價。任務完成率是指調度過程中能夠成功完成的任務數(shù)的比率。

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

表1 DTBTS算法在資源節(jié)點上的信任評價

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

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

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

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

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

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

5 結論

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