(內蒙古財經大學 計算機信息管理學院，內蒙古 呼和浩特 010070)

云計算是一種以最小的管理代價快速提供按需計算、存儲資源的范式，具有彈性、可擴展等技術優(yōu)勢，可以有效地解決復雜的科學計算問題。云計算所具有的分布式、動態(tài)性和虛擬化的特點，導致服務質量(QoS)受到諸多不確定因素的影響。承擔工作流計算和存儲任務的是運行在物理主機上的多個虛擬機，這些虛擬機共享物理主機的硬件資源，它們之間進行的通信會引發(fā)虛擬機性能指標的波動[1]，使得云實例的性能未達到預期[2]。然而，現(xiàn)有的服務選擇模型和算法較少考慮這類QoS隨時間變化所呈現(xiàn)的不確定性特征，使得模型和算法的選擇結果不準確，因此解決不確定性QoS感知服務組合問題具有現(xiàn)實意義。

當隨機變量的概率分布可以通過計算或者統(tǒng)計的方法獲得時，概率分布是云工作流調度的通用方法。已有學者開始關注這種不確定性建模的問題。近幾年，概率理論和統(tǒng)計方法已經被應用在云計算工作流調度領域中，以處理多種不確定性因素[3]。在這種方法中，諸如運行時間、任務到達時間、中央處理器(CPU)性能等不確定因素都被建模為已知概率分布函數(shù)的隨機變量。文獻[4]中提出了一種最小化工作流執(zhí)行時間的隨機啟發(fā)式調度算法，假設任務的執(zhí)行時間是獨立的、滿足正態(tài)分布的隨機變量。文獻[5]中使用概率數(shù)據(jù)流圖(PDFG)的方法對不確定云計算環(huán)境下工作流調度任務進行建模，使得調度方案能夠在運行時間約束下滿足指定的置信度概率。在不確定的可用網絡帶寬環(huán)境下，文獻[6]中提出了一種不確定帶寬值背景下的調度算法，在保證云工作流運行時間最短的情況下，對于非精確輸入信息具有更好的魯棒性。文獻[7]中基于虛擬服務節(jié)點可用性和負載的不確定性，分別使用Type-Ⅰ和Type-Ⅱ模糊邏輯系統(tǒng)預測資源的可用性和工作負載，提高虛擬數(shù)據(jù)中心的運行效率。文獻[8]中基于歷史數(shù)據(jù)給出了2個度量云工作流執(zhí)行魯棒性的度量指標，在假設已知所有數(shù)據(jù)概率分布的情況下，提出了一種魯棒性工作流調度和資源分配算法。文獻[9]中考慮時間和成本約束下，討論了運行在基礎設施即服務(IaaS)云平臺上具有統(tǒng)一分布的相互之間關聯(lián)的一組工作流不確定性問題。文獻[10]中使用蒙特卡洛方法處理工作流執(zhí)行任務的不確定性。

然而，真實運行的場景不能總是獲得足夠的信息來表征隨機變量參數(shù)的概率分布函數(shù)。需要使用不同的方法對這種不確定進行建模。文獻[11]中提出了一種混沌遺傳算法用以解決存在沖突和依賴關系的Web服務組合問題，該算法應用混沌理論、修復策略、新適應度函數(shù)等解決局部最優(yōu)并加快訓練速度，但該方法并未考慮不確定性問題。文獻[12]中用區(qū)間數(shù)理論建模QoS的不確定性，采用基于分解的非確定性多目標進化算法解決建模的區(qū)間數(shù)多目標優(yōu)化問題。文獻[13]中將區(qū)間數(shù)不確定QoS感知問題轉化為具有全局QoS約束的多目標問題，采用新的遺傳編碼模式解決再編碼問題。文獻[14]中考慮了工作流活動無法精確估計分布情況下執(zhí)行時間的不確定特征，提出了一種包含執(zhí)行時間、費用和魯棒性3個優(yōu)化目標的多目標工作流調度算法(R-MOHEFT)，能夠計算調度方案的帕累托最優(yōu)集，從而減少執(zhí)行時間的波動性的影響。文獻[15]中使用了區(qū)間數(shù)描述云計算環(huán)境的不確定性，提出了一種可以減少不確定性對云數(shù)據(jù)中心任務調度質量影響的新的調度架構和算法，基于工作負荷的情況，采用3種動態(tài)調度資源策略提高云數(shù)據(jù)中心的資源使用效率，減少能源消耗。

盡管目前計算生物學和經濟學決策領域中對于不確定性問題進行了廣泛研究，但是云計算領域的不確定性問題研究內容還比較少，在資源和服務提供以及規(guī)劃模型等問題中的不確定性因素還沒有得到充分地研究[16]。綜合現(xiàn)有的研究成果，云計算環(huán)境下的工作流調度應用中的不確定性因素會對工作流的執(zhí)行結果和效率產生顯著影響，對這種不確定性進行準確建模可以提高云計算環(huán)境下工作流的運行質量。考慮到區(qū)間數(shù)作為不確定性建?？梢圆挥妙A先獲得隨機變量的概率分布函數(shù)的優(yōu)勢，不同于現(xiàn)有研究區(qū)間數(shù)不確定性建模研究，把工作流中的任務集的不確定性看成是獨立、靜態(tài)的過程，本文中基于風險元傳遞理論對這種不確定性的動態(tài)特征進行建模，通過評價不同工作流的調度方案的整體風險，以期獲得更好的云計算工作流調度方案的選擇結果。

1 模型構建

1.1 云工作流模型

定義1 云工作流。云計算環(huán)境下的工作流可以被建模為有向無環(huán)圖(DAG)，可以表示成一個四元組G=〈V,E,t0,tn〉，由下列幾個部分組成：

1)V是節(jié)點的有限集合。每個節(jié)點關聯(lián)云計算環(huán)境下工作流的某個任務ti(0≤i≤n)，當工作流開始運行時，可以選擇分布在不同區(qū)域上的云服務運行。

2)E?V×V是頂點之間關聯(lián)的邊。集合中的每個邊e=〈ti,pi,tj〉∈E可以表示為三元組，代表云工作流中2個任務之間的依賴關系，pi表示2個任務之間的轉移概率，如果某個任務只有一個后繼節(jié)點，則pi=1。

3)t0∈V表示開始任務；tn∈V表示終止任務。

定義2 執(zhí)行路徑和調度方案。對于一個云工作流的規(guī)劃T={t1,t2,…,tm}，其對應的云組合方案S={S1,S2,…,Sm}為m個備選的調度方案。Q={Q1,Q2,…,Qn}為S中n個QoS指標的集合。

定義3 云工作流QoS風險元。云工作流調度方案中所依賴的各項QoS指標會因各種因素而表現(xiàn)為波動的現(xiàn)象，具有不確定性的特征，稱為云工作流QoS風險元。由于該風險元概率分布難于估計，因此采用區(qū)間數(shù)的方法表示風險元的不確定性度量。

1.2 云工作流多風險元傳遞模型

圖形評審技術(GERT)是一種基于計劃評估和審查技術(PERT)通用的隨機網絡分析方法，已經廣泛應用在社會的各個領域。文獻[17]中使用GERT分析方法提出了一種復雜供應鏈的風險分析模型。文獻[18]中基于系統(tǒng)耦合理論和極大熵方法提出了一種危險耦合傳導圖形評審技術改進模型，求解裝備活動中危險耦合傳導的危險度。文獻[19]中構建了可靠性GERT隨機網絡模型以計算多元件復雜系統(tǒng)可靠度?？梢?，GERT不僅可以表征風險、不確定等因素，而且其具備的對系統(tǒng)動態(tài)、傳遞特性計算的優(yōu)點，還可以對云工作流的風險元的動態(tài)特性進行建模。

云服務分散在不同地理區(qū)域，通過實現(xiàn)業(yè)務活動的工作流連接在一起，形成了一個復雜的GERT網絡。云工作流QoS風險元依附于工作流中的任務節(jié)點，通過信息關聯(lián)在云工作流之間形成了風險的流動和傳遞。

基于以上分析，提出的云工作流QoS風險元GERT網絡模型如圖1所示。

Rij表示節(jié)點i與j之間的風險流；pij表示枝線eij的轉移概率；是云工作流應用中節(jié)點i到j的n個相互獨立的風險元。圖1 云工作流服務質量風險元圖形評審技術網絡模型

定義4 云工作流QoS風險元傳遞GERT網絡模型(CQRETM)。CQRETM可以定義為一個三元組。具體的描述為：

1)N={n1,n2,…}表示只包含“或”型節(jié)點的風險元傳遞節(jié)點。

2)E={eij|〈vi,vj〉}表示連接頂點的枝線集合。

在圖1所示的模型中，pij是風險元之間傳遞能力的度量，表示風險元之間依賴程度和風險發(fā)生的程度，等同于傳統(tǒng)GERT網絡中活動實現(xiàn)概率。

1.3 風險元傳遞函數(shù)的構建

風險元傳遞函數(shù)在建模云工作流QoS風險的動態(tài)特征方面具有重要作用?；诘葍r的風險元傳遞函數(shù)，等價矩母函數(shù)和重要的相關參數(shù)可以進一步被確定和計算。

(1)

(2)

根據(jù)GERT網絡的性質，可以得到如下不同性質。

性質1 當CQRETM的2個節(jié)點之間是串聯(lián)結構的時候，其等價傳遞函數(shù)為串聯(lián)結構各活動之積，即

性質2 當CQRETM的2個節(jié)點之間是并聯(lián)結構的時候，其等價傳遞函數(shù)為串聯(lián)結構各活動之和，即

性質3 CQRETM網絡自環(huán)結構活動的等價傳遞函數(shù)為

(3)

2 工作流QoS風險元傳遞GERT網絡模型解析求解

2.1 云工作流QoS指標區(qū)間值

隨著云計算中時間約束的應用增多，對服務的執(zhí)行時間的管理的需求也急劇增長[20]。云環(huán)境下，云工作流對于云服務的選擇需要在執(zhí)行時間和其他QoS指標中進行平衡，對執(zhí)行時間的有效控制可以提供更好的服務[21]。根據(jù)云模型理論，逆向云發(fā)生器可以實現(xiàn)定量信息向定性概念的轉換，生成以(Ex,En,He)為數(shù)字特征的定性概念的云模型，其中Ex為時間樣本期望值，En為服務執(zhí)行時間的熵，He為服務執(zhí)行時間的超熵。為了確定云工作流調用服務執(zhí)行時間的區(qū)間范圍，基于云模型理論和切比雪夫不等式，提出如下的時間區(qū)間生成算法。

輸入：服務執(zhí)行時間的樣本數(shù)據(jù){t1,t2,…,tn}。

輸出：服務執(zhí)行時間區(qū)間。

5)根據(jù)切比雪夫不等式，計算置信度為λ的執(zhí)行時間區(qū)間

對于其他QoS指標的區(qū)間值，也可以根據(jù)該算法進行計算。

2.2 等價傳遞概率及等價矩母函數(shù)的建立

根據(jù)風險元矩母函數(shù)的特征可知，當sk=0時，

根據(jù)梅森公式，從節(jié)點u到節(jié)點v的風險元矩母函數(shù)為

(4)

2.3 風險度的計算

(5)

本文中的主要目標是評價云工作流調度方案的動態(tài)風險。下面給出的云工作流調度方案風險度的概念，可以用來度量因為風險因素導致的云服務QoS不確定性的大小。

風險度RS的計算過程如下。

首先，分別計算調度方案S的風險元一階矩求解期望值

E[R(k)]=

然后，計算n階矩求解方差

E[R(k)2]=

可以得到調度方案風險流的方差。

2.4 風險度的比較方法

P(Ri≥Rj)=

(6)

式中P(Ri≥Rj)+P(Rj≥Ri)=1。

計算區(qū)間可能度矩陣

PM=(Pij)m×m，

式中Pij=P(Ri≥Rj)。

下面給出風險度的得分函數(shù)Score(Ri)，以此作為排序的依據(jù)。

(7)

式中m表示可能的調度方案個數(shù)。得分函數(shù)值越大，說明風險元的波動區(qū)間越大，意味著更多的不確定性。

3 算例分析

3.1 有效性驗證

下面模擬小規(guī)模的云工作流調度計劃，共11個節(jié)點，有5個調度方案S={S1,S2,S3,S4,S5}，評價其云工作流QoS風險度。不失一般性，本文中考慮2種QoS指標，即執(zhí)行時間T、服務費用C的不確定性，對于其他云工作流QoS風險元也可以進行擴展。當這些不確定因素發(fā)生時，云工作流服務質量會產生波動影響。模擬運算的結果如圖2所示。

利用區(qū)間數(shù)的除法運算法則，可以得到調度方案S1的風險度R1=[0.01,0.113]。

同理可得

調度方案圖2 云工作流調度模擬運算結果

R2=[0.07,0.180],R3=[0.05,0.279],

R4=[0.03,0.135],R5=[0.03,0.083]。

根據(jù)公式(7)，計算得各個風險度區(qū)間數(shù)的得分為

Score(R1)=0.285 3,Score(R2)=0.313 3,

Score(R3)=0.338 5,Score(R4)=0.295 8,

Score(R5)=0.267 1。

從而得到各個方案的風險從大到小排序結果為R3、R2、R4、R1、R5。

從各個調度方案的數(shù)據(jù)區(qū)間可以看出，S3所有任務節(jié)點的執(zhí)行時間和運行成本區(qū)間范圍都是最大的，計算得到的風險度得分也是最高的。同理，S2和S4的風險度得分也與時間和成本區(qū)間范圍變化一致，說明了本文中提出的方法可以有效地度量區(qū)間波動范圍產生的不確定性。

3.2 方法對比

QoS的不確定性使得服務選擇的結果與最初的期望發(fā)生偏離，最終導致整個工作流任務失敗。本文中選擇均值-方差(E-V)[21]和逼近理想解排序法(TOPSIS)2種模型進行對比，從成功率[22]維度進行比較分析。本文中選擇文獻[23]中所提供的集成Web服務的旅游業(yè)務流為例，業(yè)務流上的每個業(yè)務節(jié)點備選的服務規(guī)模選擇為10～50個服務。每次實驗均進行20次，對結果進行平均值計算，結果如圖3所示。

從圖可以看出，隨著候選服務的數(shù)量增多，本文中提出的CQRETM方法的服務選擇成功率明顯高于E-V方法和TOPSIS方法的，主要原因是通過云模型對云服務歷史數(shù)據(jù)數(shù)字特征的構建，計算整個工作流包含的不確定性，通過選擇不確定性更少的服務組合，提高了整個工作流執(zhí)行的成功率。

E-V—均值-方差模型；TOPSIS—逼近理想解排序法；CQRETM—云工作流服務質量風險無圖形評審技術網絡模型。圖3 不同方法的服務選擇成功率對比

4 結語

隨著云計算基礎設施的完善和應用場景的擴展，越來越多的業(yè)務遷移到云環(huán)境下。云環(huán)境下異構、動態(tài)的特點，使得云工作流的執(zhí)行面臨諸多的風險因素，各項QoS指標包含諸多的不確定性。為了度量這種不確定性，評價各個云工作流的調度方案的風險大小，本文中提出了一種工作流QoS風險元傳遞GERT網絡模型，基于給出的計算QoS指標區(qū)間范圍算法，對提出的網絡模型構建了傳遞函數(shù)，求解了等價傳遞概率和矩母函數(shù)，并給出了計算工作流調度方案風險度的公式及其比較方法，最后案例說明了本文中提出的方法是可行的。