齊 平，李龍澍，李學(xué)俊

（1.安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥230039；2.銅陵學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，安徽 銅陵244000）

云計(jì)算（Cloud computing）是繼并行計(jì)算、分布式計(jì)算和網(wǎng)格計(jì)算后的新型計(jì)算模式［1］.云計(jì)算平臺利用虛擬化技術(shù)將多種計(jì)算資源（包括網(wǎng)絡(luò)、服務(wù)器、存儲、應(yīng)用和服務(wù)等）在云端進(jìn)行整合，對資源進(jìn)行統(tǒng)一管理和調(diào)度，使得這些資源可以根據(jù)負(fù)載的變化動態(tài)配置，以達(dá)到最優(yōu)的資源利用率.研究采用何種資源提供策略對這些大規(guī)模資源進(jìn)行組織和管理，實(shí)現(xiàn)資源提供的高效靈活和按需分配，對云計(jì)算具有重要意義.

近些年，在云計(jì)算資源管理方面已有較多的研究.針對不同的計(jì)算任務(wù)和優(yōu)化目標(biāo)，云資源調(diào)度算法可以分為以下幾類：1）以提高資源利用率和降低任務(wù)完成時(shí)間為目標(biāo)［2-3］；2）以降低云計(jì)算中心能耗為目 標(biāo)［4-6］；3）以 提 高 用 戶 服 務(wù) 質(zhì) 量（quality of service，QoS）為目標(biāo)［7-8］；4）基于經(jīng)濟(jì)學(xué)的云資源管 理 模 型 研 究［9-10］；5） 多 目 標(biāo) 優(yōu) 化 的 混 合算法［11-12］.

由于云環(huán)境中包含著大量分散、異構(gòu)資源，這些資源不僅地理位置分布廣泛，甚至屬于不同的自治系統(tǒng)，這些資源節(jié)點(diǎn)往往具有動態(tài)性、異構(gòu)性、開放性、自愿性、不確定性以及欺騙性等特征.云服務(wù)的可靠性是指用戶提交的服務(wù)被成功完成的概率，是從用戶的角度反映云完成用戶提交服務(wù)的執(zhí)行能力.在擁有無數(shù)資源節(jié)點(diǎn)的云環(huán)境中，節(jié)點(diǎn)的不可靠現(xiàn)象不可避免，因此，如何獲取可信的云資源，并將應(yīng)用任務(wù)分配到值得信任的資源節(jié)點(diǎn)上執(zhí)行成為云資源調(diào)度算法研究中急需解決的關(guān)鍵問題之一.

目前，在國內(nèi)外分布式系統(tǒng)資源管理的相關(guān)研究中，有關(guān)如何獲取可信資源的研究已經(jīng)取得了不少成 果.Dogan 等［13-14］提 出 了RDLS（reliable dynamic level scheduling）算法，研究如何在異構(gòu)分布式系統(tǒng)中獲取可信資源.在此基礎(chǔ)上，Dai等［15］提出了網(wǎng)格服務(wù)可靠性概念，采用最小檔案擴(kuò)展樹對網(wǎng)格服務(wù)可靠性進(jìn)行求解.Levitin［16］針對星型網(wǎng)格，提出了考慮服務(wù)可靠性和服務(wù)性能的信任評估算法.Foster等［17］將云服務(wù)和網(wǎng)格服務(wù)進(jìn)行比較，給出云服務(wù)可靠性的評估方法.上述文獻(xiàn)采用不同的信任模型，從不同角度研究網(wǎng)格服務(wù)、云服務(wù)的可靠性，并給出了相應(yīng)的調(diào)度算法，有效地提高了任務(wù)執(zhí)行的成功率.

自從Blaze［18］首先提出了信任管理概念后，Josang［19-20］等引入證據(jù)空間（evidence space）概念，以描述二項(xiàng)事件后驗(yàn)概率的Beta分布函數(shù)為基礎(chǔ)，將信任分為直接信任和推薦信任，根據(jù)節(jié)點(diǎn)間交互的肯定經(jīng)驗(yàn)和否定經(jīng)驗(yàn)計(jì)算出實(shí)體能夠完成任務(wù)的概率，并以此概率作為實(shí)體信任度的度量.基于證據(jù)的信任模型都是通過量化實(shí)體行為和計(jì)算實(shí)體信任度來評估實(shí)體間的相互信任關(guān)系.在上述研究中，所建立的信任評估模型并未考慮資源節(jié)點(diǎn)本身的行為特性.Wang［21-22］等在此基礎(chǔ)上，綜合考慮時(shí)間、權(quán)重等相關(guān)因素，利用貝葉斯算法構(gòu)造了一個(gè)基于節(jié)點(diǎn)行為的可信度評估模型，并將其引入網(wǎng)格服務(wù)、云服務(wù)的可靠性研究中，分別提出了Trust-DLS（dynamic level scheduling）和Cloud-DLS算法.

在Trust-DLS算法和Cloud-DLS算法中，對于網(wǎng)絡(luò)中的2個(gè)節(jié)點(diǎn)i和j，使用二項(xiàng)事件（交互成功／交互失?。┍硎竟?jié)點(diǎn)間的交互結(jié)果，而信任度被定義為節(jié)點(diǎn)i和j 發(fā)生n 次交互后，第n＋1次交互成功的概率估計(jì).然而，在實(shí)際的云計(jì)算環(huán)境中，由于軟件、硬件以及系統(tǒng)過載等原因，失效問題在軟件系統(tǒng)執(zhí)行過程中不可避免，而失效恢復(fù)機(jī)制作為分布式系統(tǒng)可靠性研究的基礎(chǔ)問題，在分布式計(jì)算、網(wǎng)格計(jì)算的可靠性研究中已經(jīng)得到了廣泛的應(yīng)用［23-24］.

在失效恢復(fù)機(jī)制下，并不是所有失效都可以恢復(fù)，如軟件故障和部分通信鏈路故障就不可恢復(fù)［25］.如圖1所示，當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)間交互結(jié)果為失敗時(shí)，按照物理故障（元件、鏈路失效）或軟件故障（設(shè)計(jì)、交互原因）的分類，可以將其劃分為可恢復(fù)失效和不可恢復(fù)失效.因此，在上述研究中，簡單使用二項(xiàng)事件來描述節(jié)點(diǎn)間的交互結(jié)果使得相應(yīng)的信任評估模型不太適用.

本文旨在構(gòu)造一種云環(huán)境下考慮失效恢復(fù)機(jī)制的信任評估模型，主要研究內(nèi)容包括：1）使用三項(xiàng)事件（交互成功／可恢復(fù)失效／不可恢復(fù)失效）描述節(jié)點(diǎn)的行為特性，建立相應(yīng)的信任評估模型；2）在建模和分析的過程中，評估失效恢復(fù)的執(zhí)行效率和相關(guān)參數(shù)對系統(tǒng)性能的影響；3）將考慮失效恢復(fù)機(jī)制的信任評估模型引入傳統(tǒng)的DLS算法中，提出考慮失效恢復(fù)機(jī)制的動態(tài)級調(diào)度算法.

1 考慮失效恢復(fù)機(jī)制的信任評估模型

考慮上文中所述失效恢復(fù)機(jī)制的影響，使用三項(xiàng)事件描述節(jié)點(diǎn)的行為特性，對傳統(tǒng)使用二項(xiàng)事件描述節(jié)點(diǎn)的行為特性的信任評估模型進(jìn)行擴(kuò)展，建立考慮失效恢復(fù)機(jī)制的信任評估模型.

在信任評估模型中，節(jié)點(diǎn)間信任關(guān)系分為3類.1）直接信任關(guān)系.如圖1（a）所示，節(jié)點(diǎn)i和節(jié)點(diǎn)j 之間存在可作為可信度評估依據(jù)的直接交互，即可以設(shè)法估算出直接交互成功的概率，稱為直接信任度評估，用θdt表示直接信任度.2）推薦信任關(guān)系.如圖1（b）所示，當(dāng)節(jié)點(diǎn)i和節(jié)點(diǎn)j 之間不存在可作為可信度評估的直接交互，而節(jié)點(diǎn)i可以獲取其他節(jié)點(diǎn)（如：節(jié)點(diǎn)k）關(guān)于節(jié)點(diǎn)j 的可作為可信度評估依據(jù)的交互，這種需要通過第三方來建立的信任關(guān)系，稱為推薦信任度評估，用θrt表示推薦信任度.3）混合信任關(guān)系.當(dāng)同時(shí)存在直接信任關(guān)系和推薦信任關(guān)系時(shí)，節(jié)點(diǎn)間的信任關(guān)系稱為混合信任關(guān)系，如圖1（c）所示，需要將上述2種信任關(guān)系進(jìn)行合并，得到總體的信任評估.如同在人際關(guān)系網(wǎng)絡(luò)中，當(dāng)個(gè)體之間進(jìn)行信任評估時(shí)，往往既存在直接信任關(guān)系也存在推薦信任關(guān)系，不同的個(gè)體由于其個(gè)性、情緒等主觀因素不同，具有不同的量化判斷標(biāo)準(zhǔn).本文選擇線性函數(shù)作為2種信任關(guān)系的合并函數(shù)：

式中：θ為合并信任度，λ 表示個(gè)體對2種信任關(guān)系的調(diào)節(jié)因子，當(dāng)0＜λ＜0.5時(shí)，表示個(gè)體更信任推薦信任關(guān)系；而當(dāng)λ＞0.5時(shí)，表示個(gè)體相信直接交互經(jīng)驗(yàn)超過其他個(gè)體的推薦經(jīng)驗(yàn).

圖1 節(jié)點(diǎn)間的信任關(guān)系Fig.1 Trust relationship between nodes

1.1 時(shí)間因素

為體現(xiàn)信任評估的動態(tài)性，考慮時(shí)間因素對信任評估的影響.由人類對歷史信息的認(rèn)知方法可知，不同時(shí)期的歷史交互信息對信任評估過程產(chǎn)生的影響是不同的，越接近的歷史交互信息產(chǎn)生的影響越大，而時(shí)間跨度越長的歷史交互信息產(chǎn)生的影響越小，直至對評估失去意義而不對其進(jìn)行考慮.

采用時(shí)間分段概念［26］將時(shí)間段設(shè)置為1d，并引入時(shí)間影響力衰減因子η刻畫不同時(shí)期歷史交互信息的重要程度.設(shè)2個(gè)云資源節(jié)點(diǎn)i和節(jié)點(diǎn)j，使用三項(xiàng)事件（不可恢復(fù)失效／可恢復(fù)失效／交互成功）描述節(jié)點(diǎn)i和節(jié)點(diǎn)j 之間的交互結(jié)果.當(dāng)節(jié)點(diǎn)i和節(jié)點(diǎn)j之間發(fā)生n 次交互時(shí)，設(shè)其中不可恢復(fù)失效的次數(shù)為α，可恢復(fù)失效的次數(shù)為β，交互成功的次數(shù)為γ.因此，將其劃分為m 個(gè)時(shí)間段后，設(shè)其中第i個(gè)時(shí)間段的不可恢復(fù)失效、可恢復(fù)失效和交互成功次數(shù)分別為αi、βi 和γi，則考慮時(shí)間衰減因子η后的第i個(gè)時(shí)間段的不可恢復(fù)失效α（i）、可恢復(fù)失效β（i）和交互成功次數(shù)γ（i）如下式所示：

式中：0≤η≤1，η＝0表示只考慮最近一次的歷史交互影響；而η＝1表示不考慮時(shí)間影響力衰減因子.

1.2 直接信任關(guān)系

直接信任是節(jié)點(diǎn)根據(jù)歷史交互經(jīng)驗(yàn)，對目標(biāo)節(jié)點(diǎn)未來行為的主觀期望，在這里運(yùn)用貝葉斯算法估計(jì)直接信任度.

根據(jù)經(jīng)驗(yàn)分析［27］，由不可恢復(fù)失效產(chǎn)生的因素可知，在一個(gè)時(shí)間段內(nèi)不可恢復(fù)失效的概率可以認(rèn)為是不變的.因此，設(shè)第i個(gè)時(shí)間段的不可恢復(fù)失效概率q0為常數(shù)：

同時(shí)，設(shè)第i個(gè)時(shí)間段內(nèi)可恢復(fù)失效概率為qi，則第i個(gè)時(shí)間段的成功交互概率可以表示為

對于m 個(gè)時(shí)間段，設(shè)θ＝（θ1，…，θm）為隨機(jī)變量，其驗(yàn)前分布為均勻分布，則其聯(lián)合概率密度函數(shù)為

式中：Gm為m 維歐氏空間中的點(diǎn)集，Vm為Gm的勒貝格測度.為求得θm的貝葉斯估計(jì)，必須先求出｛θ1，…，θm｝的驗(yàn)后聯(lián)合概率密度以及關(guān)于θm的驗(yàn)后邊緣概率密度.

設(shè)樣本集X＝｛X11，X12，X13；X21，X22，X23；…；Xm1，Xm2，Xm3｝，p＝1，2，…，m.其中Xp1表示時(shí)間段p 中不可恢復(fù)失效次數(shù)，Xp2表示時(shí)間段p中可恢復(fù)失效次數(shù)，Xp3表示時(shí)間段p 中成功交互次數(shù).設(shè)x0為樣本集X 的一個(gè)觀察，且

設(shè)f（θ｜x0）為隨機(jī)變量θ 的驗(yàn)后聯(lián)合概率密度，p（θm｜x0）為θm的驗(yàn)后邊緣概率密度，為θm的貝葉斯估計(jì).

根據(jù)貝葉斯公式及式（5）得到驗(yàn)后聯(lián)合概率密度為

根據(jù)上述討論內(nèi)容可知，P｛X ＝x0｜θ｝為

將式（7）代入式（6）可得

為計(jì)算式（8），引入恒等式：

式中：u和v 為正整數(shù)，B（u，v）為參數(shù)是u、v 的Beta函數(shù)，x 為自變量，0≤a＜1.設(shè)n（i）＝β（i）＋γ（i），i＝1，2，…，m，可得

綜上可得θ＝｛θ1，…，θm｝的驗(yàn)后聯(lián)合概率密度f（θ｜x0）為

θm的驗(yàn)后邊緣概率密度p（θm｜x0）為

若不對不可恢復(fù)失效和可恢復(fù)失效進(jìn)行區(qū)分，即把這2種失效都作為交互失敗來處理，在這種情況下上面所得結(jié)果式（16）驗(yàn)后聯(lián)合概率密度，式（17）驗(yàn)后邊緣概率密度和式（18）貝葉斯估計(jì)就與伯努利概率模型中的結(jié)果完全吻合.

由式（18）可以看出，直接信任關(guān)系的評估與節(jié)點(diǎn)間的交互次數(shù)有關(guān).雖然通過式（18）可以得到節(jié)點(diǎn)間的直接信任度，但是當(dāng)節(jié)點(diǎn)間沒有交互或者交互較少時(shí)，較少的樣本數(shù)將不足以評估節(jié)點(diǎn)間的直接信任關(guān)系.

針對該問題，本文使用區(qū)間估計(jì)理論［28］對信任度的置信水平進(jìn)行度量，設(shè)（θdt-δ，θdt＋δ）為直接信任度θdt的置信度為γ 的置信區(qū)間，δ 為可接受誤差，則θdt的置信度為

由于區(qū)間估計(jì)的置信度與區(qū)間估計(jì)精度相互制約，因此，選定置信度閾值為γ0，通過增加總的交互次數(shù)n提高精度，直到達(dá)到可接受水平，即當(dāng)γ≥γ0時(shí)，可以根據(jù)這時(shí)的直接交互信息進(jìn)行信任度計(jì)算.此時(shí)的樣本容量n0、可接受誤差δ和置信度閾值γ0之間的關(guān)系如下：

通過上述分析可知，根據(jù)節(jié)點(diǎn)間直接交互樣本的置信度值，可以將直接信任關(guān)系評估作如下設(shè)定：1）當(dāng)節(jié)點(diǎn)間不存在直接交互或交互樣本置信度值γ＜γ0時(shí)，先驗(yàn)分布選擇無信息先驗(yàn)分布U（0，1），設(shè)定節(jié)點(diǎn)間的直接信任度θdt＝1／2；2）當(dāng)交互樣本置信度值γ≥γ0時(shí)，節(jié)點(diǎn)間的直接信任度θdt按照式（18）計(jì)算.

1.3 推薦信任關(guān)系

推薦信任關(guān)系由2 類或多類直接交互關(guān)系形成，由于推薦信任關(guān)系涉及多方實(shí)體的直接交互關(guān)系，對推薦信任關(guān)系的評估仍按照上文所述方法，但須考慮多個(gè)直接交互信息［29］.

設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)i和節(jié)點(diǎn)k、節(jié)點(diǎn)j和節(jié)點(diǎn)k 之間的交互獨(dú)立，交互次數(shù)分別為n1、n2，其中不可恢復(fù)失效次數(shù)分別為α1、α2，可恢復(fù)失效分別為β1、β2，交互成功次數(shù)分別為γ1、γ2.設(shè)第i個(gè)時(shí)間段的不可恢復(fù)失效、可恢復(fù)失效和交互成功次數(shù)分別為α1i、β1i、γ1i和α2i、β2i、γ2i，因而考慮時(shí)間衰減因子η 后的第i個(gè)時(shí)間段的不可恢復(fù)失效、可恢復(fù)失效和交互成功次數(shù)可以設(shè)為α（i）1、β（i）1、γ（i）1和α（i）2、β（i）2、γ（i）2.

設(shè)樣本集的一個(gè)觀察

取損失函數(shù)為二次損失函數(shù)，則為θ′m的貝葉斯估計(jì)，為節(jié)點(diǎn)i和節(jié)點(diǎn)j 之間的推薦信任度，即為上文中所述的θrt，滿足下式：

節(jié)點(diǎn)可以通過搜索整個(gè)網(wǎng)絡(luò)中的其他節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的交互歷史獲得推薦信任度，然而也存在以下問題：1）當(dāng)推薦交互關(guān)系的樣本數(shù)較少時(shí)，無法使用式（26）對推薦信任關(guān)系進(jìn)行評估；2）當(dāng)推薦節(jié)點(diǎn)k不止一個(gè)時(shí)，搜索過多的推薦交互會增加整個(gè)網(wǎng)絡(luò)的通信開銷.對于上述問題，本文通過推薦交互關(guān)系的樣本置信度進(jìn)行設(shè)定：當(dāng)推薦交互樣本置信度值γ＜γ0時(shí)，設(shè)定推薦信任度θrt＝1／2，而當(dāng)γ≥γ0時(shí)，即可停止搜索推薦節(jié)點(diǎn)，并通過累計(jì)不可恢復(fù)失效、可恢復(fù)失效和成功交互數(shù)推廣式（26）計(jì)算推薦信任度θrt.

2 考慮失效恢復(fù)機(jī)制的動態(tài)級調(diào)度算法

根據(jù)第1章中討論的考慮失效恢復(fù)機(jī)制的信任模型，對傳統(tǒng)的DLS算法［30］進(jìn)行擴(kuò)展，針對基于有向無環(huán)圖（directed acyclic graph，DAG）的云資源調(diào)度問題，將考慮失效恢復(fù)機(jī)制的信任評估模型引入傳統(tǒng)的DLS算法中，提出考慮失效恢復(fù)機(jī)制的動態(tài)級調(diào)度算法.

DLS算法為靜態(tài)啟發(fā)式的表調(diào)度算法，其原理是：對于任務(wù)vi和資源mj，通過貪心方法查找具有最高動態(tài)級的任務(wù)-資源對，從而將基于DAG 的應(yīng)用任務(wù)分配到異構(gòu)的資源節(jié)點(diǎn)（如：云資源節(jié)點(diǎn)）上執(zhí)行.其中任務(wù)-資源（vi-mj）對的動態(tài)級D（vi，mj）定義如下：

式中：S（vi）為任務(wù)靜態(tài)級，在一個(gè)調(diào)度期間內(nèi)為常數(shù)，指DAG 中從任務(wù)vi到終止節(jié)點(diǎn)的最大執(zhí)行時(shí)間；Max｛tAi，j，tMj｝為資源mj的輸入數(shù)據(jù)時(shí)間與應(yīng)用任務(wù)vi的執(zhí)行時(shí)間之間的較大者；Δ（vi，mj）表示資源mj的相對計(jì)算性能.

當(dāng)任務(wù)調(diào)度到資源節(jié)點(diǎn)上執(zhí)行時(shí)，可信度反映目標(biāo)資源節(jié)點(diǎn)提供服務(wù)的可靠程度.DLS算法充分考慮了資源節(jié)點(diǎn)的異構(gòu)特征，然而并未考慮云資源節(jié)點(diǎn)可信度對調(diào)度結(jié)果的影響.為解決該問題，Wang等［22-23］考慮節(jié)點(diǎn)間行為特性和歷史交互信息，提出了可信動態(tài)級調(diào)度算法（Cloud-DLS算法），并應(yīng)用到網(wǎng)格服務(wù)和云服務(wù)中，其動態(tài)級定義如下：

式中：R（vi，nj）表示云資源節(jié)點(diǎn)調(diào)度任務(wù)vi到云資源節(jié)點(diǎn)nj上時(shí)對nj可信度的評估.

然而，該算法并未考慮云環(huán)境下的失效恢復(fù)機(jī)制.在實(shí)際的云環(huán)境中，當(dāng)某一云資源節(jié)點(diǎn)發(fā)生失效時(shí)，往往會導(dǎo)致整個(gè)任務(wù)的失敗.引入失效恢復(fù)機(jī)制后，對于可恢復(fù)失效（如：網(wǎng)絡(luò)瞬間堵塞、CPU 短時(shí)衰竭等失效問題），云資源節(jié)點(diǎn)可以通過運(yùn)行失效恢復(fù)程序?qū)σ阎兄沟娜蝿?wù)進(jìn)行恢復(fù).節(jié)點(diǎn)執(zhí)行子任務(wù)的過程被分為執(zhí)行過程和恢復(fù)過程2 個(gè)部分.如圖2所示，當(dāng)子任務(wù)i在節(jié)點(diǎn)k 上執(zhí)行時(shí)，第1次失效發(fā)生在t1時(shí)刻，在t2時(shí)刻該失效被恢復(fù)；第2次失效發(fā)生在t3時(shí)刻而在t4時(shí)刻被恢復(fù)，以此類推直至該任務(wù)執(zhí)行完成或者由于失效不可恢復(fù)而終止.

對于網(wǎng)絡(luò)中的節(jié)點(diǎn)k，失效恢復(fù)機(jī)制的相關(guān)參數(shù)如下：

1）失效恢復(fù)率xk.失效恢復(fù)具有一定的概率，為了描述失效的可恢復(fù)能力，定義隨機(jī)變量：當(dāng)節(jié)點(diǎn)k上第j 個(gè)失效可以恢復(fù)時(shí)，設(shè)＝0；當(dāng)節(jié)點(diǎn)k上第j 個(gè)失效不可恢復(fù)時(shí)，設(shè)＝1.

圖2 失效恢復(fù)機(jī)制下子任務(wù)i在節(jié)點(diǎn)k 上的執(zhí)行過程Fig.2 Execution process with fault recovery mechanism

假定節(jié)點(diǎn)k的失效恢復(fù)率恒為xk，則對于任意第j次恢復(fù)過程，都有P｛X（j）k＝0｝＝xk，P｛X（j）k＝1｝＝1-xk.同時(shí)，失效恢復(fù)率xk越高，每一次失效恢復(fù)過程所需的時(shí)間也越長，即較高的失效恢復(fù)率會提高系統(tǒng)的時(shí)間花費(fèi).

2）最大失效恢復(fù)次數(shù)Nk（Nk≥1）.由于失效恢復(fù)程序的執(zhí)行會給資源節(jié)點(diǎn)帶來較大的服務(wù)開銷，在以下3類情況下，資源節(jié)點(diǎn)k 上執(zhí)行的任務(wù)將被終止，即任務(wù)完成、發(fā)生不可恢復(fù)失效或是超過最大失效恢復(fù)次數(shù)Nk.

本文引入失效恢復(fù)機(jī)制，提出云環(huán)境下考慮失效恢復(fù)機(jī)制的動態(tài)級調(diào)度算法（FR-DLS），對于任務(wù)vi和云資源節(jié)點(diǎn)nj，其可信動態(tài)級FR-DL（vi，mj）定義如下：

式中：TS（vi，nj，xk，Nk）表示在考慮失效恢復(fù)機(jī)制參數(shù)的情況下，云資源節(jié)點(diǎn)ns調(diào)度任務(wù)vi到云資源節(jié)點(diǎn)nj上時(shí)對nj可信度的評估，即式（1）中討論的合并信任度θ.

3 仿真實(shí)驗(yàn)及結(jié)果分析

為驗(yàn)證所提出的信任評估模型和動態(tài)級調(diào)度算法，在PlanetLab 環(huán)境［31］中設(shè)計(jì)基于云仿真軟件CloudSim［32］的實(shí)驗(yàn)平臺.分布全球的計(jì)算機(jī)群項(xiàng)目PlanetLab始于2003 年，由普林斯頓大學(xué)、華盛頓大學(xué)、加州大學(xué)和Intel研究人員共同開發(fā)，其目標(biāo)是提供一個(gè)用于開發(fā)下一代互聯(lián)網(wǎng)技術(shù)的開放式全球性測試實(shí)驗(yàn)平臺.云仿真軟件CloudSim 是一個(gè)通用、可擴(kuò)展的新型仿真框架，通過在離散事件模擬包SimJava上開發(fā)的函數(shù)庫支持基于數(shù)據(jù)中心的虛擬化建模、仿真功能和云資源管理、云資源調(diào)度模擬.同時(shí)，CloudSim 為用戶提供了一系列可擴(kuò)展的實(shí)體和方法，用戶根據(jù)自身的要求調(diào)用適當(dāng)?shù)腁PI實(shí)現(xiàn)自定義的調(diào)度算法.

本文所有的仿真試驗(yàn)中，每組實(shí)驗(yàn)分為10次，最終結(jié)果采用平均值.相關(guān)實(shí)驗(yàn)參數(shù)設(shè)置如下：在PlanetLab的網(wǎng)絡(luò)模擬實(shí)驗(yàn)環(huán)境中，節(jié)點(diǎn)數(shù)和節(jié)點(diǎn)之間的鏈路數(shù)預(yù)先給定，鏈路間的數(shù)據(jù)傳輸速度介于1～10 Mbit／s；由于算法的性能與應(yīng)用任務(wù)的大小和通信／計(jì)算比rCC（communication to computation ratio）［32］有關(guān)，任務(wù)類型按照通信／計(jì)算比給出，rCC＞1表示該任務(wù)為通信密集型，而0＜rCC＜1則表示該任務(wù)為計(jì)算密集型.同時(shí)，設(shè)定用戶任務(wù)在資源節(jié)點(diǎn)上的執(zhí)行時(shí)間介于10～100s.其他實(shí)驗(yàn)參數(shù)設(shè)置如 下：λ＝0.8，η＝0.8［22-23］，δ＝0.1，γ0＝0.95.同時(shí)設(shè)置2 類惡意節(jié)點(diǎn)，分別占節(jié)點(diǎn)總數(shù)的20%和30%，在分配到任務(wù)時(shí)，2類惡意節(jié)點(diǎn)分別以80%和50%的概率執(zhí)行任務(wù)失敗.

3.1 失效恢復(fù)機(jī)制

在以下實(shí)驗(yàn)中，討論失效恢復(fù)機(jī)制及其參數(shù)對信任評估的影響，并在不同任務(wù)數(shù)和不同節(jié)點(diǎn)數(shù)的情況下，比較DLS 算法、Cloud-DLS算法和本文所提出的FR-DLS算法的性能.

為考察失效恢復(fù)機(jī)制的有效性，對于不同類型的用戶任務(wù)（rCC分別取0.1、1.0、10.0），討論失效恢復(fù)率xk、最大失效恢復(fù)次數(shù)Nk對任務(wù)執(zhí)行成功率ra（average ratio of successful execution）和任務(wù)完成時(shí)間ta（average completion time）的影響.實(shí)驗(yàn)環(huán)境參數(shù)設(shè)置如下：云資源節(jié)點(diǎn)數(shù)為200，鏈路數(shù)為200，任務(wù)數(shù)為50.

3.1.1 失效恢復(fù)率xk對于rCC分別取0.1、1.0、10.0的不同類型任務(wù)，討論在不考慮最大失效恢復(fù)次數(shù)Nk的情況下，失效恢復(fù)率xk對任務(wù)執(zhí)行成功率的影響.實(shí)驗(yàn)結(jié)果如圖3 所示，當(dāng)失效恢復(fù)率xk＝0時(shí)，表示未使用失效恢復(fù)機(jī)制，任務(wù)執(zhí)行成功率相對較低.隨著失效恢復(fù)率xk的增加，3 種類型任務(wù)的執(zhí)行成功率都相應(yīng)提高；而當(dāng)失效恢復(fù)率xk＝1時(shí)，任務(wù)執(zhí)行成功率相對較高，充分體現(xiàn)了失效恢復(fù)機(jī)制的有效性.

當(dāng)失效恢復(fù)率xk＝1時(shí)，任務(wù)執(zhí)行成功率并未達(dá)到100%.這是由于在不設(shè)置最大失效恢復(fù)次數(shù)的情況下，雖然可恢復(fù)失效可以通過恢復(fù)程序的不斷執(zhí)行得以恢復(fù)，使得任務(wù)執(zhí)行完成，但如通信鏈路故障、軟件故障等不可恢復(fù)失效并不能夠被失效恢復(fù)機(jī)制所恢復(fù).

討論在設(shè)置最大失效恢復(fù)次數(shù)Nk＝3時(shí)，失效恢復(fù)率xk對任務(wù)執(zhí)行成功率的影響，實(shí)驗(yàn)結(jié)果如圖4所示.由圖可見，隨著失效恢復(fù)率xk的增加，3種類型任務(wù)的執(zhí)行成功率增長速率較不限制最大失效恢復(fù)次數(shù)時(shí)緩慢.此外，rCC＝10.0時(shí)的任務(wù)執(zhí)行成功率明顯低于rCC＝0.1時(shí)，這是由于通信密集型任務(wù)有著較高的失效率，因此對于不同類型的任務(wù)，選取合適的失效恢復(fù)率十分重要.

圖3 不同失效恢復(fù)率下平均任務(wù)執(zhí)行成功率的比較（Nk 無約束）Fig.3 Comparison of average success rates of task execution under varying recoverability probability（Nk without constraint）

圖4 不同失效恢復(fù)率下平均任務(wù)執(zhí)行成功率的比較（Nk＝3）Fig.4 Comparison of average success rates of task execution under varying recoverability probability（Nk＝3）

圖5 不同失效恢復(fù)率下平均任務(wù)完成時(shí)間的比較（Nk＝3）Fig.5 Comparison of average task completion time under varying recoverability probability（Nk＝3）

失效、恢復(fù)過程會給節(jié)點(diǎn)帶來較大的服務(wù)開銷，而提高失效恢復(fù)率也會使恢復(fù)過程所需的時(shí)間增加.為研究失效恢復(fù)率xk對任務(wù)完成時(shí)間的影響，比較隨著xk逐步增長，不同類型任務(wù)的完成時(shí)間，設(shè)置最大失效恢復(fù)次數(shù)Nk＝3，實(shí)驗(yàn)結(jié)果如圖5所示.當(dāng)0＜xk＜0.6時(shí)，任務(wù)完成時(shí)間的增長速率較緩；而當(dāng)xk＞0.6時(shí)，任務(wù)完成時(shí)間的增長速率相對較快；當(dāng)xk＝1.0時(shí)，3種類型任務(wù)的完成時(shí)間急劇增長.可見，選擇較高的失效恢復(fù)率在提高任務(wù)執(zhí)行成功率的同時(shí)，也帶來了較大的時(shí)間花費(fèi).

3.1.2 最大失效恢復(fù)次數(shù)Nk如前文所述，每一次失效、恢復(fù)都會給節(jié)點(diǎn)帶來較大的服務(wù)開銷.在某些情況下（見圖2），失效恢復(fù)過程被不斷執(zhí)行多次，直至任務(wù)完成.這對系統(tǒng)的可用性有較大影響，因此有必要限定節(jié)點(diǎn)的失效恢復(fù)次數(shù).本實(shí)驗(yàn)對于rCC分別為0.1、1.0和10.0的不同類型任務(wù)，考察最大失效恢復(fù)次數(shù)Nk對任務(wù)執(zhí)行成功率和任務(wù)完成時(shí)間的影響，在以下實(shí)驗(yàn)中，失效恢復(fù)率xk設(shè)置為0.6.如圖6所示，隨著最大失效恢復(fù)次數(shù)Nk的增加，3種類型任務(wù)的執(zhí)行成功率都有不同程度的提高.當(dāng)Nk≤4時(shí)，執(zhí)行成功率增長的較快；而當(dāng)5≤Nk≤10時(shí)，執(zhí)行成功率增長較緩，這說明大部分可恢復(fù)失效可以在最多執(zhí)行4 次失效恢復(fù)過程后恢復(fù).

圖6 不同失效恢復(fù)次數(shù)下平均任務(wù)執(zhí)行成功率的比較（xk＝0.6）Fig.6 Comparison of average success rates of task execution under varying number of recoverable failures（xk＝0.6）

如圖7所示為隨著最大失效恢復(fù)次數(shù)Nk的增加，rCC分別為0.1、1.0和10.0的不同類型任務(wù)的任務(wù)完成時(shí)間.由圖可見，隨著最大失效恢復(fù)次數(shù)Nk的增加，3種類型任務(wù)的完成時(shí)間都有不同程度的提高.當(dāng)Nk≤5時(shí)，任務(wù)完成時(shí)間的增長速率較快；而當(dāng)Nk趨向于10 時(shí)，任務(wù)完成時(shí)間的增長趨向平緩.該實(shí)驗(yàn)從另一方面證實(shí)了大部分可恢復(fù)失效可以在執(zhí)行4～5次失效恢復(fù)過程后被恢復(fù).

圖7 不同失效恢復(fù)次數(shù)下平均任務(wù)完成時(shí)間的比較（xk＝0.6）Fig.7 Comparison of average task completion time under varying number of recoverable failures（xk＝0.6）

由上述實(shí)驗(yàn)結(jié)果可見，失效恢復(fù)機(jī)制可以顯著地提高任務(wù)執(zhí)行成功率，充分體現(xiàn)了失效恢復(fù)機(jī)制的有效性.與此同時(shí)，失效恢復(fù)機(jī)制也給系統(tǒng)帶來了一定的服務(wù)開銷和時(shí)間花費(fèi)，因此，對于不同類型的任務(wù)，應(yīng)當(dāng)按照需要選擇合適的失效恢復(fù)率和最大失效恢復(fù)次數(shù).

3.2 不同任務(wù)數(shù)情況下的比較

本實(shí)驗(yàn)在網(wǎng)絡(luò)中具有不同任務(wù)數(shù)的情況下，比較FR-DLS算法、Cloud-DLS算法和傳統(tǒng)的DLS算法在任務(wù)執(zhí)行成功率、平均調(diào)度長度la（average schedule length）和任務(wù)完成時(shí)間方面的性能.其中，xk和Nk分別被設(shè)置為0.6和3.實(shí)驗(yàn)環(huán)境參數(shù)設(shè)置如下：設(shè)定rCC＝1.0，云資源節(jié)點(diǎn)數(shù)為200，鏈路數(shù)為200，并隨機(jī)產(chǎn)生擁有10～100個(gè)子任務(wù)數(shù)nt（number of tasks）的任務(wù)圖.

圖8 不同任務(wù)數(shù)下DLS、Cloud-DLS和FR-DLS的平均任務(wù)執(zhí)行成功率比較Fig.8 Comparison of average success rates of task execution of DLS，Cloud-DLS and DLS-FR algorithms with varying numbers of tasks

圖9 不同任務(wù)數(shù)下DLS、Cloud-DLS和FR-DLS的平均調(diào)度長度比較Fig.9 Comparison of average schedule lengths of DLS，Cloud-DLS and DLS-FR algorithms with varying numbers of tasks

圖10 不同任務(wù)數(shù)下DLS、Cloud-DLS和FR-DLS的平均任務(wù)完成時(shí)間比較Fig.10 Comparison of average task completion time of DLS，Cloud-DLS and DLS-FR algorithms with varying numbers of tasks

實(shí)驗(yàn)結(jié)果如圖8～10所示，由圖可見，隨著任務(wù)數(shù)的增加，3種算法的任務(wù)執(zhí)行成功率都略有降低，而調(diào)度長度和任務(wù)完成時(shí)間則有不同程度的提高.其中，F(xiàn)R-DLS算法的調(diào)度長度和任務(wù)完成時(shí)間略高于Cloud-DLS 算法和DLS 算法.由圖8 可以看出，F(xiàn)R-DLS算法的執(zhí)行成功率遠(yuǎn)高于Cloud-DLS算法和DLS算法.結(jié)果表明：失效恢復(fù)機(jī)制在較小的服務(wù)開銷和時(shí)間花費(fèi)下可以有效地提高任務(wù)執(zhí)行成功率.

3.3 不同節(jié)點(diǎn)數(shù)情況下的比較

本實(shí)驗(yàn)在網(wǎng)絡(luò)中具有不同節(jié)點(diǎn)數(shù)的情況下，比較FR-DLS算法、Cloud-DLS算法和傳統(tǒng)的DLS算法在任務(wù)執(zhí)行成功率、調(diào)度長度和任務(wù)完成時(shí)間方面的性能.實(shí)驗(yàn)環(huán)境參數(shù)設(shè)置如下：設(shè)定rCC＝1，鏈路數(shù)為200，任務(wù)數(shù)為100，并隨機(jī)產(chǎn)生擁有100～1 000個(gè)節(jié)點(diǎn)數(shù)nr（number of resource nodes）的隨機(jī)網(wǎng)絡(luò).

實(shí)驗(yàn)結(jié)果如圖11～13所示，由圖可見，在不同節(jié)點(diǎn)數(shù)的情況下，可以得到與不同任務(wù)數(shù)時(shí)相類似的結(jié)論：在犧牲一定完成時(shí)間和調(diào)度長度的代價(jià)下，失效恢復(fù)機(jī)制可以顯著地提高任務(wù)執(zhí)行成功率，體現(xiàn)了該機(jī)制的有效性.

在不同任務(wù)數(shù)和不同節(jié)點(diǎn)數(shù)情況下，如表1所示為FR-DLS算法相對于Cloud-DLS算法和DLS算法在調(diào)度長度、任務(wù)執(zhí)行時(shí)間和任務(wù)執(zhí)行成功率方面的改善情況.

通過表1可以看出：1）任務(wù)調(diào)度在調(diào)度長度、執(zhí)行時(shí)間和執(zhí)行成功率方面存在權(quán)衡，無法達(dá)到多方面服務(wù)質(zhì)量的同時(shí)提高，而是以某一部分服務(wù)質(zhì)量為代價(jià)換取另一部分更高的服務(wù)需求；2）本文所提出FR-DLS算法的性能與云計(jì)算環(huán)境下的節(jié)點(diǎn)數(shù)、任務(wù)數(shù)和任務(wù)類型（rCC的取值）有關(guān).其中，隨著云環(huán)境中節(jié)點(diǎn)數(shù)增加，F(xiàn)R-DLS算法在可靠性方面提升的性能遠(yuǎn)高于其在任務(wù)完成時(shí)間和調(diào)度長度代價(jià)方面的所提升的性能，顯示了FR-DLS算法在云計(jì)算環(huán)境下對于大規(guī)模任務(wù)的實(shí)用性.

圖11 不同節(jié)點(diǎn)數(shù)下DLS、Cloud-DLS和FR-DLS的平均任務(wù)執(zhí)行成功率比較Fig.11 Comparison of average success rates of task execution of DLS，Cloud-DLS and DLS-FR algorithms with varying numbers of resource nodes

表1 FR-DLS算法相對Cloud-DLS算法和DLS算法在調(diào)度長度、任務(wù)執(zhí)行時(shí)間和任務(wù)執(zhí)行成功率方面的增加情況（不同任務(wù)數(shù)和不同節(jié)點(diǎn)數(shù)）Tab.1 Comparison of Cloud-DLS algorithm and DLS algorithm in scheduling lengths，completion time and success rates of task execution with FR-DLS algorithm（varying numbers of tasks and resource nodes）%

圖12 不同節(jié)點(diǎn)數(shù)下DLS、Cloud-DLS和FR-DLS的平均調(diào)度長度比較Fig.12 Comparison of average schedule lengths of DLS，Cloud-DLS and DLS-FR algorithms with varying numbers of resource nodes

圖13 不同節(jié)點(diǎn)數(shù)下DLS、Cloud-DLS和FR-DLS的平均任務(wù)完成時(shí)間比較Fig.13 Comparison of average task completion time of DLS，Cloud-DLS and DLS-FR algorithms with varying numbers of resource nodes

4 結(jié) 語

本文將節(jié)點(diǎn)失效可恢復(fù)的情況引入到云服務(wù)可靠性分析中，在此基礎(chǔ)上將原有的以二項(xiàng)事件（成功／失敗）描述節(jié)點(diǎn)間交互結(jié)果的信任模型擴(kuò)展為以三項(xiàng)事件（成功／可恢復(fù)失效／不可恢復(fù)失效）描述交互結(jié)果的信任評估模型，并提出了考慮失效恢復(fù)機(jī)制的可信動態(tài)級調(diào)度算法.仿真實(shí)驗(yàn)證實(shí)該算法能夠?yàn)樵骗h(huán)境中主體節(jié)點(diǎn)的信任決策提供有效的支持，有效地提高云服務(wù)的可靠性.同時(shí)，該算法允許資源所有者自行調(diào)節(jié)資源失效恢復(fù)次數(shù)限制和失效恢復(fù)率，從而增加了失效恢復(fù)機(jī)制的靈活性.

本文的進(jìn)一步工作是將考慮云計(jì)算環(huán)境中的相關(guān)安全機(jī)制與時(shí)間花費(fèi)、價(jià)格花費(fèi)等服務(wù)質(zhì)量因素相結(jié)合，同時(shí)將如鏈路故障、節(jié)點(diǎn)故障和云節(jié)點(diǎn)本身安全軟件的部署等安全因素相結(jié)合，提出相應(yīng)的任務(wù)調(diào)度算法，從不同角度滿足用戶對云服務(wù)可靠性、服務(wù)質(zhì)量和服務(wù)花費(fèi)的多方面要求.

（

）：

［1］BUYYA R，YEO C S.VENUGOPAL S，et al.Cloud computing and emerging IT platforms：vision，hype，and reality for delivering computing as the 5th utility［J］.Future Generation Computer Systems，2009，25（6）：599-616.

［2］DARBHA S，AGRAWAL D P.Optimal scheduling algorithm for distributed memory machines ［J］.IEEE Transactions on Parallel and Distributed Systems，2002，9（1）：87-95.

［3］LEE Y C，ZOMAYA A Y.A novel state transition method for metaheuristic-based scheduling in heterogeneous computing systems［J］.IEEE Transactions on Parallel and Distributed Systems，2008，19（9）：1215-1223.

［4］ZHU D，MOSSE D，MELHEM R.Power-aware scheduling for and／or graphs in real-time systems［J］.IEEE Transactions on Parallel and Distributed Systems，2004，15（9）：849-864.

［5］KIM K H，BUYYA R，KIM J.Power aware scheduling of bag-of-tasks applications with deadline constraints on DVS-enabled clusters ［C］∥Proceedings of the 7th IEEE International Symposium on Cluster Computing and the Grid.Rio de janeiro：IEEE，2007：541-548.

［6］BUNDE D P.Power-aware scheduling for makespan and flow［J］.Journal of Scheduling，2009，12（5）：489-500.

［7］李茂勝，楊壽保，付前飛，等.基于賠償?shù)木W(wǎng)格資源交易模型［J］.軟件學(xué)報(bào)，2006，17（3）：472-480.LI Mao-sheng，YANG Shou-bao，F(xiàn)U Qian-fei，et al.A grid resource transaction model based on compensation［J］.Journal of Software，2006，17（3）：472-480.

［8］XU B M，ZHAO C Y，HU E Z，et al.Job scheduling algorithm based on Berger model in cloud environment［J］.Advances in Engineering Software，2011，42（3）：419-425.

［9］BUYYA R，MURSHED M M，ABRAMSON D，et al.Scheduling parameter sweep applications on global grids：a deadline and budget constrained cost-time optimization algorithm ［J］.Software Practice and Experi-ence，2005，35（5）：491-512.

［10］BLANCO C V，HUEDO E，MONTERO R S，et al.Dynamic provision of computing resources from grid infrastructures and cloud providers［C］∥Grid and Pervasive Computing Conference，Geneva：IEEE，2009：113-120.

［11］TOPCUOGLU H，HARIRI S，WU M Y.Performance-effective and low complexity task scheduling for heterogeneous computing ［J］.IEEE Transactions on Parallel and Distributed Systems，2002，13（3）：260-274.

［12］MEZMAZ M，MELAB N，KESSACI Y，et al.A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems［J］.Journal of Parallel and Distributed Computing，2011，71（10）：1497-1508.

［13］DOGAN A，OZGUNER，F(xiàn).Reliable matching and scheduling of precedence constrained tasks in heterogeneous distributed computing［C］∥Proceedings of the 29th international conference on parallel processing，Toronto：IEEE，2000：307-314.

［14］DOGAN A，OZGUNER，F(xiàn).Matching and scheduling algorithms for minimizing execution time and failure probability of applications in heterogeneous computing［J］.IEEE Transactions on Parallel and Distributed Systems，2002，13（3）：308-323.

［15］DAI Y S，XIE M.Reliability of grid service systems［J］.Computers and Industrial Engineering，2006，50（1／2）：130-147.

［16］LEVITIN G，DAI Y S.Service reliability and performance in grid system with star topology［J］.Reliability Engineering and System Safety，2007，92（1）：40-46.

［17］FOSTER I，ZHAO Y，RAICU I，et al.Cloud Computing and Grid Computing 360-Degree Compared［M］.Texa：IEEE Grid Computing Environments，2008：1014-1017.

［18］BLAZE M.Toward a broader view of security protocols［C］∥12th Cambridge International Workshop on Security Protocols，Cambridge：IEEE，2004：1014-1017.

［19］JOSANG A，OZGUNER F.Matching and scheduling of minimizing execution time and failure probability of applications in heterogeneous computing ［J］.IEEE Transactions on Parallel and Distributed Systems，2002，13（3）：308-323.

［20］JOSANG A.A logic for uncertain probabilities［J］.International Journal of Uncertainty，F(xiàn)uzziness and Knowledge-Based Systems，2001，9（3）：279-311.

［21］WANG W，ZENG G S，YUAN L L.A reputation multi-agent system in semantic web［C］∥Proceedings of the 9th Pacific Rim International Workshop on Multi-Agents.Guilin：PRIMA，2006：211-219.

［22］WANG W，ZENG G S，TANG D Z，et al.Cloud-DLS：dynamic trusted scheduling for cloud computing［J］.Expert Systems with Applications，2012，39（5）：2321-2329.

［23］DAI Y S，WANG X L.Optimal resource allocation on grid systems for maximizing service reliability using a genetic algorithm［J］.Reliability Engineering and System Safety，2006，91（9）：1071-1082.

［24］TREASTER M.A survey of fault-tolerance and faultrecovery techniques in parallel systems ［R］.ACM Computing Research Repository（CoRR），2005：1-11.

［25］ABAWAJY J H.Fault-tolerant scheduling policy for grid computing systems［C］∥Proceedings of the 19th IEEE International conference on Parallel and Distributed Processing Symposium，New York：IEEE，2004：50-58.

［26］JOSANG A，ISMAIL R.The beta reputation system［C］∥Proceedings of the 15th Bled Conference on Electronic Commerce，Slovenia：Bled EC，2002：2502-2511.

［27］GUO S C，HUANG H Z，LIU Y.Modeling and analysis of grid service reliability considering fault recovery［J］.New Generation Computing，2011，29（4）：345-364.

［28］THOMAS L，JOHN S J.Bayesian methods：an analysis of statisticians and interdisciplinary ［M］.New York：Cambridge University Press，1999：341-355.

［29］SULISTIO A，CIBEJ U，VENUGOPAL S，et al.A tutorial for modeling and simulating data grids：an extension to Gridsim ［J］.Concurrency and Computation：Practice and Experience，2008，20（13）：1591-1609.

［30］ZHU M，GUO W，XIAO S L，et al.Availability-driven scheduling for real-time directed acyclic graph applications in optical grid［J］.Journal of Optical Communications and Networking，2010，2（7）：469-480.

［31］PETERSON L，BAVIER A，F(xiàn)IUCZYNSK M，et al.Towards a comprehensive PlanetLab architecture technical report PDN-05-030［R］.Sydney：PlanetLab Consortium，2005.

［32］CALHEIROS R N，RANJAN R，ROSE D，et al.CloudSim：a novel framework for modeling and simulation of cloud computing infrastructures and services［R］.Melbourne：Grid Computing and Distributed Systems Laboratory，the University of Melbourne，2009.