云環(huán)境下基于Bayesian主觀信任模型的動態(tài)級調(diào)度算法＊

齊 平，王福成，朱桂宏

（銅陵學(xué)院數(shù)學(xué)與計算機學(xué)院，安徽 銅陵244000）

1 引言

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

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

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

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

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

在文獻［21，22］所提出的算法中，通常假設(shè)資源分配具有公平性，即在有限的資源條件下，節(jié)點之間不會因為爭奪資源而相互影響，造成損害，任意兩對節(jié)點之間的交互都是獨立的，交互信息都是真實可靠的。然而，在真實的云環(huán)境中，為得到更多的資源，節(jié)點可能會通過需求欺騙、長期占用等手段非法使用資源，成為自私節(jié)點而對資源分配的公平性造成破壞；此外，在非可信網(wǎng)絡(luò)環(huán)境中，節(jié)點也有可能被攻擊而成為惡意節(jié)點，提供虛假的交互信息。這些自私節(jié)點和惡意節(jié)點蠶食系統(tǒng)資源，在破壞資源分配公平性的同時，使得云平臺內(nèi)正常節(jié)點因資源需求無法滿足而不能正常作業(yè)，從而降低系統(tǒng)的可靠性。節(jié)點間交互過程中可能出現(xiàn)的這些威脅，都會導(dǎo)致作為信任值評估證據(jù)的樣本空間不一定完整和可靠，因而現(xiàn)有的信任評估模型不太適用。

Bayesian方法是建立在主觀概率的基礎(chǔ)上，通過對歷史經(jīng)驗、各方面信息等客觀情況的了解，再進行分析推理后得到的對特定事件發(fā)生可能性大小的度量，本文借鑒社會學(xué)中人際關(guān)系信任模型，旨在構(gòu)造一種云環(huán)境下基于Bayesian方法的主觀信任管理模型。本文提出的Bayesian主觀信任模型是在文獻［21，22］基礎(chǔ)上，并對其進行了較大的擴充，主要體現(xiàn)在以下幾點：（1）研究了信任的定義、描述、評估方法和合成、傳遞、推導(dǎo)機制；（2）針對原有信任模型對推薦信任關(guān)系的評估較為簡單的問題，細化了推薦信任關(guān)系及相應(yīng)的評估方法；（3）考慮網(wǎng)絡(luò)中節(jié)點的不確定性、欺騙性等問題，研究風(fēng)險因素，引入了懲罰機制和分級剪枝過濾機制。最后將該模型引入傳統(tǒng)的DLS算法中，提出了基于Bayesian主觀信任管理模型的動態(tài)級調(diào)度算法，仿真實驗結(jié)果表明，提出的BST－DLS 算法能夠以較小的調(diào)度長度為代價，有效地提高云環(huán)境下任務(wù)執(zhí)行的成功率。

2 Bayesian主觀信任模型

人們在生活中進行各種各樣的交易、交互和通信都是基于一個基礎(chǔ)理念——信任。信任本質(zhì)上是一個社會心理關(guān)系，在人際關(guān)系網(wǎng)絡(luò)中，信任是對他人可信行為的評價，而個體的可信與否往往取決于其他個體的推薦。云計算平臺下的資源節(jié)點與人際關(guān)系網(wǎng)絡(luò)中的個體具有很大的相似性，這表現(xiàn)在以下幾點：（1）節(jié)點在和其他資源節(jié)點交互時，會留下反映其行為特征的交互信息；（2）不同的節(jié)點可以通過其不同的主觀判斷標(biāo)準(zhǔn)選擇交互節(jié)點，節(jié)點具備信任的主觀性；（3）節(jié)點之間的交互關(guān)系可以是一對一、一對多，也有可能是多對多或者多對一；（4）和信任關(guān)系類似，節(jié)點間的交互具有一定的傳遞性。因此，云環(huán)境下的資源節(jié)點可以根據(jù)其歷史交互經(jīng)驗進行信任評估。

在信任評估模型中，節(jié)點間信任關(guān)系分為兩類：一類為直接信任關(guān)系，如圖1a所示，當(dāng)節(jié)點i和節(jié)點j之間存在可作為可信度評估依據(jù)的直接交互，即可以設(shè)法估算出直接交互成功的概率，稱為直接信任度評估，用Tdt表示直接信任度；另一類為推薦信任關(guān)系，如圖1b所示，當(dāng)節(jié)點i和節(jié)點j之間不存在可作為可信度評估的直接交互，而節(jié)點i可以獲取其他節(jié)點（例如節(jié)點k）關(guān)于節(jié)點j的可作為可信度評估依據(jù)的交互，這種需要通過第三方來建立的信任關(guān)系，稱為推薦信任度評估，用Trt表示推薦信任度。

Figure 1 Trust relationship among nodes圖1 節(jié)點間信任關(guān)系

當(dāng)同時存在直接信任關(guān)系和推薦信任關(guān)系時，如圖1c所示，為混合信任關(guān)系，需要將上述兩種信任關(guān)系進行合并，得到總體的信任評估。如同在人際關(guān)系網(wǎng)絡(luò)中，當(dāng)個體之間進行信任評估時，往往既存在直接信任關(guān)系也存在推薦信任關(guān)系，不同的個體由于其個性、情緒等主觀因素不同，具有不同的量化判斷標(biāo)準(zhǔn)。本文選擇線性函數(shù)作為兩種信任關(guān)系的合并函數(shù)，如式（1）所示：

其中，λ表示個體對兩種信任關(guān)系的調(diào)節(jié)因子，當(dāng)0＜λ＜0.5時，表示個體更信任推薦信任關(guān)系，而當(dāng)λ＞0.5時，表示個體相信直接交互經(jīng)驗超過其他個體的推薦經(jīng)驗。

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

直接信任是節(jié)點根據(jù)歷史交互經(jīng)驗，對目標(biāo)節(jié)點未來行為的主觀期望，在這里借鑒文獻［23］提出的模型，根據(jù)二項事件后驗概率分布服從Beta分布來求解信任值。設(shè)兩個云資源節(jié)點i和j，使用二項事件（交互成功/交互失?。┟枋鏊鼈冎g的交互結(jié)果；當(dāng)節(jié)點i和j之間發(fā)生n次交互后，其中成功交互的次數(shù)為α，失敗交互的次數(shù)為β；同時假設(shè)隨機變量x為一次交互過程中獲得成功的概率，且x服從（0，1）的均勻分布U（0，1）。定義i對j的直接信任度Tdt為：

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

針對該問題，本文使用區(qū)間估計理論［24］對信任度的置信水平進行度量，設(shè)（Tdt－δ，Tdt＋δ）為直接信任度Tdt的置信度為γ的置信區(qū)間，δ為可接受誤差，則Tdt的置信度γ計算公式如下：

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

通過上述分析可知，根據(jù)節(jié)點間直接交互樣本的置信度值，可以將直接信任關(guān)系評估作如下設(shè)定：（1）當(dāng)節(jié)點間不存在直接交互，或交互樣本置信度值γ＜γ0時，設(shè)定節(jié)點間的直接信任度Tdt＝1/2；（2）當(dāng)交互樣本置信度值γ≥γ0時，節(jié)點間的直接信任度Tdt按照式（2）計算。

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

推薦信任關(guān)系由兩類或多類直接交互關(guān)系形成，由于推薦信任關(guān)系涉及多方實體的交互關(guān)系，因而較難評估，這表現(xiàn)在：（1）根據(jù)推薦節(jié)點之間的相互關(guān)系，可以把推薦信任關(guān)系進一步分為單徑信任推薦關(guān)系和多徑信任推薦關(guān)系；（2）由于惡意節(jié)點和自私節(jié)點的存在，在推薦信任關(guān)系中，并不能保證所有的推薦者都是可信的，也不能確定所有可信的推薦者所推薦的信息都是準(zhǔn)確的。

因此，針對推薦信任關(guān)系的上述特點，借鑒人類接受推薦信息的心理過程，本文利用Bayesian方法模擬人類判斷推薦信息的認知模型，建立抵御惡意節(jié)點推薦的機制，使得信任模型更加合理。

2.2.1 單徑推薦信任關(guān)系

如圖2所示為單徑推薦信任關(guān)系模型，在單徑推薦信任關(guān)系傳遞過程中，推薦信任的傳遞由節(jié)點間的信任關(guān)系和該信任關(guān)系的可靠程度（即信任強度）構(gòu)成。

定義1 信任強度是指在推薦信任傳遞的過程中，節(jié)點間信任關(guān)系的可靠程度；它刻畫了主體節(jié)點對中間推薦節(jié)點和目標(biāo)節(jié)點之間信任關(guān)系的相信程度。信任強度用S表示，且滿足0≤S≤1。

定義2 推薦信任關(guān)系由中間推薦節(jié)點對目標(biāo)節(jié)點的信任關(guān)系和該信任關(guān)系的可靠程度組成，可以表示為推薦信任向量（T，S）。

Figure 2 Recommendation trust relationship（single path）圖2 單徑推薦信任關(guān)系

圖2a為含有三個節(jié)點的二級單徑推薦關(guān)系，設(shè)節(jié)點i對中間推薦節(jié)點k的直接信任度為節(jié)點k對目標(biāo)節(jié)點j的直接信任度為則節(jié)點j向節(jié)點i傳遞的推薦信任向量為（Tkj，Skj）。其中Skj定義為主體節(jié)點i對節(jié)點k傳遞信任信息的相信程度，因此滿足式（5）：

圖2b為含有四個節(jié)點的三級單徑推薦關(guān)系，設(shè)節(jié)點i、s、k、j之間的直接信任度分別為和則節(jié)點j向節(jié)點s和節(jié)點i傳遞的推薦信任向量為（Tkj，Skj）和（Tsj，Ssj），滿足式（6）：

同理可以得到多級單徑推薦關(guān)系的評估方法，當(dāng)存在n個節(jié)點（1，2…，n）的n－1級單徑推薦關(guān)系時，節(jié)點n對節(jié)點1 的推薦信任向量為（T2n，S2n），其中

通過上述公式可以發(fā)現(xiàn)，推薦信任在傳遞的過程中經(jīng)過了若干中間推薦節(jié)點，推薦信任值發(fā)生了衰減。而這正符合人類判斷推薦信息的認知模型，即經(jīng)過多人傳遞的推薦信息，其可信度逐漸降低。

2.2.2 多徑推薦信任關(guān)系

在云平臺中，資源節(jié)點之間常常有多條路徑，圖3所示為兩條路徑的推薦信任關(guān)系模型：包含路徑｛i，k，s，j｝和路徑｛i，d，f，j｝。設(shè)節(jié)點j通過兩條路徑向i傳遞的推薦信任向量分別為（Tkj，Skj）和（Tdj，Sdj），那么節(jié)點i可以根據(jù)式（7）得到節(jié)點j的多徑推薦信任。

其中，ω1和ω2為兩條路徑推薦信任的權(quán)重，有ω1＝Skj/（Skj＋Sdj），ω2＝Sdj/（Skj＋Sdj）。同理可以得到多級（n級）多徑推薦信任關(guān)系模型。設(shè)多條路徑推薦信任向量分別為｛（T1，S1），（T2，S2），…，（Tn，Sn）｝，那么節(jié)點i可以根據(jù)式（8）得到節(jié)點j的多徑推薦信任。

Figure 3 Recommendation trust relationship（multipath）圖3 多徑推薦信任關(guān)系

2.2.3 推薦信任關(guān)系的進一步討論

在實際的云計算平臺中，云資源節(jié)點除正常節(jié)點外，通常同時還存在自私節(jié)點和惡意節(jié)點，因此并不能保證所有推薦節(jié)點傳遞的推薦信息都是非惡意的。同時，當(dāng)推薦路徑中存在惡意節(jié)點時，該推薦路徑傳遞的推薦信息也是不合理的。惡意節(jié)點和惡意推薦往往會提供虛假的交互信息或篡改歷史交互結(jié)果，導(dǎo)致作為信任值評估證據(jù)的樣本空間不一定完整和可靠。

針對上述問題，本文在評估推薦信任關(guān)系之前，首先建立分級剪枝過濾機制，過濾偏離直接信任度過大的推薦和可信度較低的推薦；再通過懲罰機制對多徑推薦信任的終點是同一推薦節(jié)點這一易出現(xiàn)惡意推薦的情況進行討論。

（1）分級剪枝過濾機制。

如前文所述，節(jié)點可以通過搜索網(wǎng)絡(luò)中的其他節(jié)點和目標(biāo)節(jié)點的歷史交互信息獲取推薦信任關(guān)系。在多徑推薦信任關(guān)系模型中，主體節(jié)點和目標(biāo)節(jié)點之間往往會存在多條推薦路徑（推薦路徑可以為一個推薦節(jié)點，也可以由多個推薦節(jié)點組成的多級推薦關(guān)系）。然而，由于惡意節(jié)點的存在，并不是所有的推薦信息都是可靠的，因此需要過濾掉惡意和無用的推薦信息。參照人類接受推薦的認知過程可知：①可信度較低的推薦者的推薦信息參考價值較低；②偏離直接交互經(jīng)驗或心理預(yù)期較大的推薦難以接受。因此，本文使用分級剪枝過濾機制在可選推薦路徑中篩選有用的推薦信息，對推薦信任度較低或推薦偏差較大的推薦進行剪枝過濾。

定義3（推薦偏差） 設(shè)節(jié)點i和節(jié)點j的直接信任度為推薦路徑Pk的推薦信任度為則推薦偏差dk為：

其中，推薦路徑Pk推薦信任度的偏差dk越大，被接受的可能性越小，當(dāng)節(jié)點i和節(jié)點j不存在直接交互時，設(shè)定直接信任度的值為1/2。

對于信任度較高的推薦，如果其推薦偏差較大，在一定的偏差范圍內(nèi)可以接受該推薦，而對于信任度較低的推薦，可接受的偏差范圍則較小。本文使用文獻［25］提出的信任等級劃分方法，對推薦路徑按照其信任度的不同劃分其等級，并提供不同的可接受范圍。信任等級劃分方法如式（10）所示：

其中，x表示信任度，l（x）表示其信任等級。

按照信任度劃分為不同信任等級后，其分級剪枝過濾過程如下：

①對于推薦路徑｛P1，P2，…，Pn｝，根據(jù)路徑推薦信任度將其劃分為l＋1個等級，按照不同的等級包含在不同的推薦路徑集合｛Pk｝l中，對每一信任等級l，其可接受推薦偏差為εl。

②設(shè)0＜m＜l，對于信任等級低于m的較低信任度的推薦路徑集合進行剪枝，排除低信任度的推薦路徑。

③對于剩余推薦路徑集合｛Pk｝（l｜l＞m），推薦路徑Pk的可接受范圍由其推薦偏差決定，如式（11）所示：

（2）懲罰機制。

在多徑推薦信任關(guān)系模型中，當(dāng)多條推薦路徑的終點為同一推薦節(jié)點時，如果該節(jié)點恰好為惡意節(jié)點進行惡意的信任推薦，那么最終得到的評估結(jié)果一定是不合理的。如圖4所示，當(dāng)推薦路徑｛i，k，s｝和｛i，d，f｝的終點為節(jié)點m時，節(jié)點m的信任傳遞對節(jié)點i和節(jié)點j之間的推薦信任評估有著重要意義。針對該問題，本文引入懲罰機制［26］并加以討論。

Figure 4 Punishment mechanism in recommendation trust relationship（multipath）圖4 多徑信任推薦關(guān)系中的懲罰機制

設(shè)多徑推薦信任關(guān)系模型中包含n個節(jié)點，其中含有c個自私節(jié)點和z個惡意節(jié)點，定義I為推薦路徑上第1個推薦節(jié)點是惡意節(jié)點的事件，Hk表示推薦路徑上第一個惡意節(jié)點占據(jù)第k個位置的事件，則從第k個位置開始推薦路徑上存在惡意節(jié)點的事件可以用Hk＋＝Hk∨Hk＋1∨Hk＋2∨…表示。因此，當(dāng)推薦路徑上存在惡意節(jié)點的情況下，設(shè)惡意節(jié)點冒名正常節(jié)點的概率為P（I｜H1＋），滿足式（12）：

針對上述問題，引入懲罰因子ps，用于調(diào)整多徑信任推薦中一些推薦路徑的終點可能是同一個推薦節(jié)點時，該節(jié)點為惡意節(jié)點對推薦信任評估帶來的影響。如圖4所示，當(dāng)兩條推薦路徑的推薦信任向量分別為（Tkj，Skj）和（Tdj，Sdj），且兩條推薦路徑中含有相同的節(jié)點m時，節(jié)點i可以根據(jù)式（13）得到節(jié)點j的新的多徑推薦信任：

其中，ω1和ω2為兩條路徑推薦信任的權(quán)重。

在引入懲罰因子后，惡意節(jié)點冒名正常節(jié)點的概率P′（I｜H1＋）為：

由式（12）和式（14）可以看出，引入懲罰因子ps后，惡意節(jié)點冒名正常節(jié)點的概率減少，能夠在一定程度上提高系統(tǒng)的可靠性。

2.3 時間因素

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

類似文獻［27］，在這里采用時間分段的概念，將時間段設(shè)置為一天，并引入時間影響力衰減因子η刻畫不同時期歷史交互信息的重要程度。因此，對于n個時間段，設(shè)時間段i的成功交互和失敗交互次數(shù)分別為αi和βi，則第n個時間段后總的交互成功次數(shù)和失敗次數(shù)α（n）和β（n）如式（15）所示：

其中，0≤η≤1，η＝0表示只考慮最近一次的歷史交互影響，而η＝1表示不考慮時間影響力衰減因子。

3 基于Bayesian主觀信任模型的動態(tài)級調(diào)度算法

根據(jù)上一節(jié)討論的Bayesian主觀信任模型，本文充分考慮云資源節(jié)點的可信度，針對節(jié)點中存在惡意推薦問題，擴展了傳統(tǒng)的DLS 算法［28］，使得基于有向無環(huán)圖（DAG）的云資源調(diào)度算法更加全面合理。

DLS算法是一種靜態(tài)啟發(fā)式的表調(diào)度算法，主要用于將基于DAG 的應(yīng)用分配到一個異構(gòu)的資源節(jié)點集合上。在調(diào)度的每一步，DLS 算法通過尋找具有最高“動態(tài)級”的任務(wù)vi－資源mj對，從而將任務(wù)vi調(diào)度到資源mj上執(zhí)行，完成任務(wù)分配。任務(wù)－資源（vi－mj）對的動態(tài)級DL（vi，mj）定義如式（16）所示：

其中，SL（vi）為任務(wù)靜態(tài)級，在一個調(diào)度期間內(nèi)為常數(shù)，指DAG 中從任務(wù)vi到終止節(jié)點的最大執(zhí)行時間；表示任務(wù)vi在資源mj上執(zhí)行的時間，表示任務(wù)vi調(diào)度到資源mj上所需輸入數(shù)據(jù)可獲得的時間，表示資源mj空閑時可以用于執(zhí)行任務(wù)vi的時間；Δ（vi，mj）表示資源mj的相對計算性能，為任務(wù)vi在所有資源上的平均執(zhí)行時間與其在資源mj上的執(zhí)行時間之差。

當(dāng)任務(wù)調(diào)度到目標(biāo)節(jié)點上執(zhí)行時，可信度反映目標(biāo)節(jié)點提供服務(wù)的可靠程度，DLS算法考慮資源的異構(gòu)性，能夠適應(yīng)資源異構(gòu)性的特征，但沒有考慮到云資源的可信度對任務(wù)調(diào)度效果的影響。為解決該問題，文獻［22，23］考慮節(jié)點間行為特性和歷史交互信息，提出了可信動態(tài)級調(diào)度算法，并應(yīng)用到網(wǎng)格服務(wù)和云服務(wù)中。然而，該算法假設(shè)資源分配具有公平性，認為各節(jié)點給出的歷史交互信息都是真實可靠的，并未考慮自私節(jié)點和惡意節(jié)點對交互信息和推薦信任評估結(jié)果的影響。因此，本文引入分級剪枝過濾機制和懲罰機制，提出云環(huán)境下基于Bayesian主觀信任模型的動態(tài)級調(diào)度算法（BST－DLS），對于任務(wù)vi和云資源節(jié)點nj，其可信動態(tài)級BST－DL（vi，mj）定義如式（17）所示：

其中，TS（vi，nj）表示云資源節(jié)點ns調(diào)度任務(wù)vi到云資源節(jié)點nj上時對nj可信度的評估，即第2節(jié)中討論的合并信任度T。

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

為驗證提出的信任評估模型和動態(tài)級調(diào)度算法，本文在PlanetLab 環(huán)境［29］中設(shè)計了基于云仿真軟件CloudSim［30］的實驗平臺。分布于全球的計算機群項目PlanetLab始于2003年，由普林斯頓大學(xué)、華盛頓大學(xué)、加州大學(xué)和Intel研究人員共同開發(fā)，其目標(biāo)是提供一個用于開發(fā)下一代互聯(lián)網(wǎng)技術(shù)的開放式全球性測試實驗平臺。在Planet－Lab的網(wǎng)絡(luò)模擬實驗環(huán)境中，設(shè)定節(jié)點數(shù)和節(jié)點之間的鏈路數(shù)預(yù)先給定，鏈路間的數(shù)據(jù)傳輸速度介于［1，10］Mbit/s。

云仿真軟件CloudSim 是一個通用、可擴展的新型仿真框架，它通過在離散事件模擬包SimJava上開發(fā)的函數(shù)庫支持基于數(shù)據(jù)中心的虛擬化建模、仿真功能和云資源管理、云資源調(diào)度的模擬。同時，CloudSim 為用戶提供了一系列可擴展的實體和方法，用戶根據(jù)自身的要求調(diào)用適當(dāng)?shù)腁PI實現(xiàn)自定義的調(diào)度算法。本文所有的仿真實驗中，每組實驗分為10次，最終結(jié)果采用平均值。相關(guān)實驗參數(shù)設(shè)置如下：根據(jù)文獻［22，23］討論，信任關(guān)系調(diào)節(jié)因子λ和時間影響衰減因子η均設(shè)置為0.8；式（3）和式（4）中δ和γ0的取值分別為0.1 和0.95；同時按照式（18）將信任等級劃分如下：

其中，對于信任等級l（x）＝0 的推薦路徑進行剪枝，對于信任等級l（x）＝1 和l（x）＝2 的推薦路徑，其可接受偏差范圍εl分別設(shè)為ε1和ε2。

在實際的云計算平臺中，由于不同類型的惡意節(jié)點通過組合都可以產(chǎn)生一類新的惡意節(jié)點，因此對惡意節(jié)點的刻畫較為困難。為簡化實驗，本文僅對以下幾類節(jié)點進行測試：（1）簡單惡意節(jié)點，這類節(jié)點提供的服務(wù)是不真實的；（2）詆毀惡意節(jié)點，這類節(jié)點詆毀與其交互過的正常節(jié)點，其目的是借此降低其信譽度；（3）合謀惡意節(jié)點，這類節(jié)點通過修改交易信息，夸大同伙節(jié)點的可信度，同時詆毀正常節(jié)點。此外，設(shè)置兩類自私節(jié)點，分別占節(jié)點總數(shù)的10%，它們在分配到任務(wù)時，以80%和50%的概率執(zhí)行任務(wù)失敗。

本文首先對提出的懲罰機制和分級剪枝過濾機制進行討論，主要討論懲罰因子ps以及分級剪枝過濾機制中的參數(shù)對信任度評估的影響。

4.1 信任模型的有效性

（1）懲罰機制ps。

為考察多徑推薦信任關(guān)系中引入懲罰機制的有效性，當(dāng)懲罰因子ps的取值分別為0.3、0.7、1時，對任務(wù)執(zhí)行成功率進行比較。

實驗中相關(guān)參數(shù)設(shè)置如下：云資源節(jié)點數(shù)為200，鏈路數(shù)為200，任務(wù)數(shù)為100，設(shè)定網(wǎng)絡(luò)中存在的惡意節(jié)點為提供不真實服務(wù)的簡單惡意節(jié)點。

由式（13）可知，懲罰因子ps可以調(diào)節(jié)懲罰機制的影響力，當(dāng)ps＝1 時，未使用懲罰機制，而當(dāng)ps的值越小則懲罰機制的影響力越強。如圖5所示，當(dāng)網(wǎng)絡(luò)中的惡意節(jié)點不超過20%時，ps＝1和ps＝0.3、ps＝0.7的任務(wù)執(zhí)行成功率相似；隨著網(wǎng)絡(luò)中的惡意節(jié)點比例增加，任務(wù)執(zhí)行成功率均有不同程度的降低，而當(dāng)惡意節(jié)點比例超過35%時，未考慮懲罰機制時的任務(wù)執(zhí)行成功率下降速度較快，且數(shù)值明顯低于其他兩類，這充分體現(xiàn)了本文提出的懲罰機制的有效性。

Figure 5 Impact of penalty factor ps on average ratio of successful execution圖5 懲罰因子ps 對平均執(zhí)行成功率的影響

值得一提的是，當(dāng)網(wǎng)絡(luò)中惡意節(jié)點所占比例小于10%時，未使用懲罰機制的任務(wù)執(zhí)行成功率略高于使用懲罰機制的任務(wù)執(zhí)行成功率。這是由于在多徑推薦信任關(guān)系模型中，懲罰機制是針對多條推薦路徑的終點為同一推薦節(jié)點，且該節(jié)點恰好為惡意節(jié)點的情況。因此，如果網(wǎng)絡(luò)中存在較少的惡意節(jié)點或不存在惡意節(jié)點，則該懲罰機制會在一定程度上降低算法選擇最可靠路徑的可能性，從而使得任務(wù)執(zhí)行成功率有一定程度的降低。

（2）分級剪枝過濾機制。

為考察本文提出分級剪枝過濾機制的有效性，對于信任等級l（x）＝1和l（x）＝2的推薦路徑，對其可接受偏差（ε1，ε2）分別?。?.1，0，2）、（0.2，0，4）和不考慮該機制時的任務(wù)執(zhí)行成功率進行比較。為表達清楚，用Ε1、Ε2和Ε3分別表示可接受偏差（ε1，ε2）的取值為（0.1，0，2）、（0.2，0，4）和未使用分級剪枝過濾機制的情況。

其他實驗環(huán)境設(shè)置如下：云資源節(jié)點數(shù)為200，鏈路數(shù)為200，任務(wù)數(shù)為100，懲罰因子ps＝0.7，設(shè)定網(wǎng)絡(luò)中存在的惡意節(jié)點為提供不真實服務(wù)的簡單惡意節(jié)點。

實驗結(jié)果如圖6所示，隨著網(wǎng)絡(luò)中惡意節(jié)點的比例的增加，Ε1、Ε2和Ε3的任務(wù)執(zhí)行成功率均有不同程度的降低，其中未考慮分級剪枝過濾機制的Ε3成功率降低較快，而Ε1和Ε2在惡意節(jié)點比例超過30%時仍然具有相對較高的任務(wù)執(zhí)行成功率，說明了本文提出分級剪枝過濾機制的有效性。

Figure 6 Impact of hierarchical pruning mechanism on average ratio of successful execution圖6 分級剪枝過濾機制對平均執(zhí)行成功率的影響

當(dāng)惡意節(jié)點比例超過40%時，可以看出E1的執(zhí)行成功率略高于E2，說明在惡意節(jié)點比例較大的網(wǎng)絡(luò)環(huán)境中，適合采用更小的可接受范圍以保證任務(wù)執(zhí)行的可靠性。

4.2 各類惡意節(jié)點情況下的比較

該仿真實驗針對網(wǎng)絡(luò)中存在三類典型的惡意節(jié)點，即簡單惡意節(jié)點、詆毀惡意節(jié)點和合謀惡意節(jié)點，比較本文提出的BST－DLS算法、Cloud－DLS算法和傳統(tǒng)的DLS算法在不同類型惡意節(jié)點情況下的性能。實驗相關(guān)參數(shù)設(shè)置如下：云資源節(jié)點數(shù)為200，鏈路數(shù)為200，任務(wù)數(shù)為100，設(shè)置懲罰因子ps為0.7，可接受偏差（ε1，ε2）?。?.1，0，2）。

（1）簡單惡意節(jié)點。圖7為惡意節(jié)點為簡單惡意節(jié)點情況下，BST－DLS算法、Cloud－DLS算法和傳統(tǒng)的DLS算法的任務(wù)執(zhí)行成功率。從圖7可以看出，當(dāng)增加惡意節(jié)點所占比例時，三種算法的任務(wù)執(zhí)行成功率都呈下降趨勢。BST－DLS算法與Cloud－DLS算法、DLS算法相比下降速度最慢，當(dāng)惡意節(jié)點比例達到40%時，Cloud－DLS 算法和DLS算法任務(wù)執(zhí)行成功率分別只有50.9%和18.9%，而BST－DLS算法能夠有效地抵御惡意節(jié)點，任務(wù)執(zhí)行成功率為77.4%，說明BST－DLS 算法能夠有效抑制簡單惡意節(jié)點的攻擊。

Figure 7 Average execution success ratio（simple malicious nodes）圖7 簡單惡意節(jié)點情況下的平均執(zhí)行成功率

（2）詆毀惡意節(jié)點。圖8為惡意節(jié)點為詆毀惡意節(jié)點情況下，BST－DLS算法、Cloud－DLS算法和傳統(tǒng)的DLS算法的任務(wù)執(zhí)行成功率。詆毀惡意節(jié)點通過提供不真實服務(wù)詆毀與其交易過的可信節(jié)點，通過圖8可以看出，雖然當(dāng)增加惡意節(jié)點比例時，三種算法的任務(wù)執(zhí)行成功率都呈下降趨勢，但是在有40%為詆毀惡意節(jié)點的情況下，BST－DLS算法仍然具有75.7%的任務(wù)執(zhí)行成功率，明顯高于其他兩種算法，較為有效地抑制了詆毀惡意節(jié)點的影響。

Figure 8 Average execution success ratio（denigration malicious nodes）圖8 詆毀惡意節(jié)點情況下的平均執(zhí)行成功率

（3）合謀惡意節(jié)點。圖9為惡意節(jié)點為合謀惡意節(jié)點情況下，BST－DLS算法、Cloud－DLS算法和傳統(tǒng)的DLS算法的任務(wù)執(zhí)行成功率。合謀惡意節(jié)點通過提供不真實服務(wù)信息夸大同伙節(jié)點可信度的同時，也會詆毀與其交易過的可信節(jié)點，試圖降低可信節(jié)點的信任度。由圖9可見，當(dāng)增加合謀惡意節(jié)點的比例時，三種算法的任務(wù)執(zhí)行成功率同樣都呈下降趨勢，在有40%為合謀惡意節(jié)點的情況下，BST－DLS 算 法 具 有72.9%的 任 務(wù) 執(zhí) 行 成 功率，明 顯 高 于Cloud－DLS 算 法 和DLS 算 法 的47.1%和19.6%。

Figure 9 Average execution success ratio（collusion malicious nodes）圖9 合謀惡意節(jié)點情況下的平均執(zhí)行成功率

由上述實驗結(jié)果可以看出，本文提出的BSTDLS算法在網(wǎng)絡(luò)中存在三類典型的惡意節(jié)點的情況下，通過分級剪枝過濾機制和懲罰機制可以有效地抑制惡意節(jié)點，保證任務(wù)執(zhí)行的可靠性。而Cloud－DLS算法和DLS算法由于并未對惡意節(jié)點作任何處理，因此當(dāng)惡意節(jié)點比例增加時，惡意節(jié)點很容易獲得較高的可信度。同時，在網(wǎng)絡(luò)中存在詆毀惡意節(jié)點和合謀惡意節(jié)點的情況下，往往可信節(jié)點的信任度還會由于惡意節(jié)點的詆毀反而變得較低。惡意節(jié)點由此得到大量的交互，并使得這些交互失敗而導(dǎo)致系統(tǒng)可靠性降低。

4.3 不同節(jié)點數(shù)情況下的比較

該仿真實驗在網(wǎng)絡(luò)中具有不同節(jié)點數(shù)的情況下，比較本文提出的BST－DLS 算法、Cloud－DLS算法和DLS算法在任務(wù)執(zhí)行成功率和調(diào)度長度方面的性能。實驗相關(guān)參數(shù)設(shè)置如下：設(shè)定實驗中隨機產(chǎn)生100～1 000個云資源節(jié)點，任務(wù)數(shù)為100，鏈路數(shù)為200；設(shè)置懲罰因子ps為0.7，可接受偏差（ε1，ε2）?。?.1，0，2），設(shè)定網(wǎng)絡(luò)中存在的惡意節(jié)點為提供不真實服務(wù)的簡單惡意節(jié)點，惡意節(jié)點占網(wǎng)絡(luò)中節(jié)點的比例為40%。

Figure 10 Average ratio of successful execution of DLS，Cloud－DLS and BST－DLS algorithms with varying numbers of nodes圖10 不同節(jié)點數(shù)下DLS、Cloud－DLS和BST－DLS的平均執(zhí)行成功率比較

Figure 11 Average schedule length of DLS，Cloud－DLS and BST－DLS algorithms with varying numbers of nodes圖11 不同節(jié)點數(shù)下DLS、Cloud－DLS和BST－DLS的平均調(diào)度長度比較

由圖10、圖11可見，當(dāng)網(wǎng)絡(luò)中惡意節(jié)點比例為40%時，隨著網(wǎng)絡(luò)中總節(jié)點數(shù)的增加，三種算法的任務(wù)執(zhí)行成功率均略有提高，而調(diào)度長度均有不同程度的減少。圖10中，BST－DLS算法的平均任務(wù)執(zhí)行成功率為82.39%，明顯高于Cloud－DLS算法的60.89%和DLS算法的23.48%，充分體現(xiàn)了本文提出BST－DLS算法的有效性。圖11中本文提出的BST－DLS算法的平均調(diào)度長度為1 721.7，高于Cloud－DLS 算 法 的1 447.1 和DLS 算 法 的1 009.6。

綜上可知，BST－DLS算法與DLS算法相比平均執(zhí)行成功率和平均調(diào)度長度的增加分別為250.89%和70.53%，與Cloud－DLS算法相比平均執(zhí)行成功率和平均調(diào)度長度的增加分別為35.3%和18.97%?？梢?，本文提出的BST－DLS 算法雖然能夠顯著地提高系統(tǒng)的可靠性，但在獲得較高的任務(wù)執(zhí)行成功率的同時，也犧牲了一定的調(diào)度長度，且該算法在可靠性方面性能的提高遠高于所增加的調(diào)度長度。

5 結(jié)束語

本文深入研究云環(huán)境下節(jié)點間直接信任及推薦信任的傳遞與合成問題，針對云環(huán)境中存在自私節(jié)點和惡意節(jié)點的情況，引入懲罰機制和分級剪枝過濾機制，通過對云環(huán)境下節(jié)點可信度的評估，提出一種云環(huán)境下基于Bayesian方法的主觀信任模型和相應(yīng)的可信動態(tài)級調(diào)度算法。該算法作為一種有效的評價分析和推導(dǎo)工具，能夠為云環(huán)境中主體節(jié)點的信任決策提供有效的支持，使得應(yīng)用任務(wù)在值得信賴的環(huán)境下運行。本文的下一步工作將考慮云環(huán)境中的相關(guān)安全機制與時間花費、價格花費等服務(wù)質(zhì)量因素相結(jié)合，滿足不同用戶的服務(wù)質(zhì)量要求。

［1］ Rajkumar B，Shin Y C，Broberg V 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 bagof－tasks applications with deadline constraints on DVS－enabled clusters［C］∥Proc of the 7th IEEE International Symposium on Cluster Computing and the Grid，2007：541－548.

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

［7］ Li M S，Yang S B，F(xiàn)u Q F，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，Hua 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 Experience，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］∥Proc of Grid and Pervasive Computing Conference，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.Reliable matching and scheduling of precedence constrained tasks in heterogeneous distributed computing［C］∥Proc of the 29th International Conference on Parallel Processing，2000：307－314.

［14］ Dogan A，Ozguner F.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 Yuan－sun，Xie Min.Reliability of grid service systems［J］.Computers and Industrial Engineering，2006，50（1/2）：130－147.

［16］ Levitin G ，Dai Yuan－sun.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［J］.IEEE Grid Computing Environments（GCE 2008），2008：1.

［18］ Blaze M，F(xiàn)eigenbaum J，Lucy J.Decentralized trust management［C］∥Proc of the IEEE Computer Society Symposium on Research in Security and Privacy，1996：164－173.

［19］ Josang A.Trust－based decision making for electronic transactions［C］∥Proc of the 4th Nordic Workshop on Secure Computer Systems（NORDSEC’99），1999：1.

［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］∥Proc of the 9th Pacific Rim International Workshop on Multi－Agents，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］ Mui L，Mohtashemi M，Halberstadt M.A computational model of trust and reputation［C］∥Proc of the 35th Hawaii International Conference on System Sciences，2002：1.

［24］ Thomas L，John S J.Bayesian methods：An analysis of statisticians and interdisciplinary［M］.New York：Cambridge University Press，1999.

［25］ Jameel H，Hung L X，Kalim U，et al.A trust model for ubiquitous systems based on vectors of trust values［C］∥Proc of the 7th IEEE International Symposium on Multimedia，2005：674－679.

［26］ Shi Jin－qiao，Cheng Xiao－ming.Research on penalty mechanism against selfish behaviors in anonymous communication system［J］.Journal on Communication，2006，27（2）：80－86.（in Chinese）

［27］ Josang A，Ismail R.The beta reputation system［C］∥Proc of the Bled Conference on Electronic Commerce，2002：1.

［28］ Sih G C，Lee E A.A compile－time scheduling heuristic for interconnection－constraint heterogeneous processor architectures［J］.IEEE Transactions on Parallel and Distributed Systems，1993，4（2）：175－187.

［29］ Peterson L，Bavier A，F(xiàn)iuczynski M，et al.Towards a comprehensive PlanetLab architecture［R］.Technical Report PDN－05－030.New Jersey：PlanetLab Consortium，2005.

［30］ Calheiros R N，Ranjan R，De Rose C A F，et al.CloudSim：A novel framework for modeling and simulation of cloud computing infrastructures and services［R］.Technical Report GRIDS－TR－2009－1.Australia：Grid Computing and Distributed Systems Laboratory，The University of Melbourne，2009.

附中文參考文獻：

［26］ 時金橋，程曉明.匿名通信系統(tǒng)中自私行為的懲罰機制研究［J］.通信學(xué)報，2006，27（2）：80－86.