(內(nèi)蒙古財(cái)經(jīng)大學(xué) 計(jì)算機(jī)信息管理學(xué)院，內(nèi)蒙古 呼和浩特 010070)

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

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

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

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

1 模型構(gòu)建

1.1 云工作流模型

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

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

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

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

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

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

1.2 云工作流多風(fēng)險(xiǎn)元傳遞模型

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

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

基于以上分析，提出的云工作流QoS風(fēng)險(xiǎn)元GERT網(wǎng)絡(luò)模型如圖1所示。

Rij表示節(jié)點(diǎn)i與j之間的風(fēng)險(xiǎn)流；pij表示枝線eij的轉(zhuǎn)移概率；是云工作流應(yīng)用中節(jié)點(diǎn)i到j(luò)的n個(gè)相互獨(dú)立的風(fēng)險(xiǎn)元。圖1 云工作流服務(wù)質(zhì)量風(fēng)險(xiǎn)元圖形評(píng)審技術(shù)網(wǎng)絡(luò)模型

定義4 云工作流QoS風(fēng)險(xiǎn)元傳遞GERT網(wǎng)絡(luò)模型(CQRETM)。CQRETM可以定義為一個(gè)三元組。具體的描述為：

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

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

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

1.3 風(fēng)險(xiǎn)元傳遞函數(shù)的構(gòu)建

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

(1)

(2)

根據(jù)GERT網(wǎng)絡(luò)的性質(zhì)，可以得到如下不同性質(zhì)。

性質(zhì)1 當(dāng)CQRETM的2個(gè)節(jié)點(diǎn)之間是串聯(lián)結(jié)構(gòu)的時(shí)候，其等價(jià)傳遞函數(shù)為串聯(lián)結(jié)構(gòu)各活動(dòng)之積，即

性質(zhì)2 當(dāng)CQRETM的2個(gè)節(jié)點(diǎn)之間是并聯(lián)結(jié)構(gòu)的時(shí)候，其等價(jià)傳遞函數(shù)為串聯(lián)結(jié)構(gòu)各活動(dòng)之和，即

性質(zhì)3 CQRETM網(wǎng)絡(luò)自環(huán)結(jié)構(gòu)活動(dòng)的等價(jià)傳遞函數(shù)為

(3)

2 工作流QoS風(fēng)險(xiǎn)元傳遞GERT網(wǎng)絡(luò)模型解析求解

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

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

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

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

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

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

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

根據(jù)風(fēng)險(xiǎn)元矩母函數(shù)的特征可知，當(dāng)sk=0時(shí)，

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

(4)

2.3 風(fēng)險(xiǎn)度的計(jì)算

(5)

本文中的主要目標(biāo)是評(píng)價(jià)云工作流調(diào)度方案的動(dòng)態(tài)風(fēng)險(xiǎn)。下面給出的云工作流調(diào)度方案風(fēng)險(xiǎn)度的概念，可以用來(lái)度量因?yàn)轱L(fēng)險(xiǎn)因素導(dǎo)致的云服務(wù)QoS不確定性的大小。

風(fēng)險(xiǎn)度RS的計(jì)算過(guò)程如下。

首先，分別計(jì)算調(diào)度方案S的風(fēng)險(xiǎn)元一階矩求解期望值

E[R(k)]=

然后，計(jì)算n階矩求解方差

E[R(k)2]=

可以得到調(diào)度方案風(fēng)險(xiǎn)流的方差。

2.4 風(fēng)險(xiǎn)度的比較方法

P(Ri≥Rj)=

(6)

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

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

PM=(Pij)m×m，

式中Pij=P(Ri≥Rj)。

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

(7)

式中m表示可能的調(diào)度方案?jìng)€(gè)數(shù)。得分函數(shù)值越大，說(shuō)明風(fēng)險(xiǎn)元的波動(dòng)區(qū)間越大，意味著更多的不確定性。

3 算例分析

3.1 有效性驗(yàn)證

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

利用區(qū)間數(shù)的除法運(yùn)算法則，可以得到調(diào)度方案S1的風(fēng)險(xiǎn)度R1=[0.01,0.113]。

同理可得

調(diào)度方案圖2 云工作流調(diào)度模擬運(yùn)算結(jié)果

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

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

根據(jù)公式(7)，計(jì)算得各個(gè)風(fēng)險(xiǎn)度區(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。

從而得到各個(gè)方案的風(fēng)險(xiǎn)從大到小排序結(jié)果為R3、R2、R4、R1、R5。

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

3.2 方法對(duì)比

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

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

E-V—均值-方差模型；TOPSIS—逼近理想解排序法；CQRETM—云工作流服務(wù)質(zhì)量風(fēng)險(xiǎn)無(wú)圖形評(píng)審技術(shù)網(wǎng)絡(luò)模型。圖3 不同方法的服務(wù)選擇成功率對(duì)比

4 結(jié)語(yǔ)

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