摘 要： 針對(duì)當(dāng)前廣泛使用的云計(jì)算工作流調(diào)度方法過多側(cè)重于可靠性和節(jié)能等方面的優(yōu)化，而忽略安全性約束要求，基于協(xié)同禁忌算法設(shè)計(jì)了一種能實(shí)現(xiàn)云計(jì)算工作流高效調(diào)度的方法，該方法具有安全性約束。首先對(duì)云計(jì)算工作流調(diào)度的[DAG]圖進(jìn)行定義，形式化描述安全性約束，建立云計(jì)算工作流調(diào)度的數(shù)學(xué)模型；然后基于經(jīng)典的協(xié)同禁忌算法設(shè)計(jì)解的編碼方式、適應(yīng)度函數(shù)、變鄰域結(jié)構(gòu)和雙禁忌表，改進(jìn)了經(jīng)典的協(xié)同禁忌算法；對(duì)基于該協(xié)同禁忌算法實(shí)現(xiàn)對(duì)云計(jì)算工作流調(diào)度的算法進(jìn)行定義；最后基于云計(jì)算仿真環(huán)境Cloud?Sim進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，所設(shè)計(jì)的算法收斂速度較快，且其較快地尋找到了相對(duì)于其他方法更佳的調(diào)度方案，符合安全性約束要求，是一種實(shí)用的調(diào)度方法。

關(guān)鍵詞： 工作流調(diào)度； 虛擬機(jī)； 安全性約束； 云計(jì)算

中圖分類號(hào)： TN915?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）21?0011?04

Cooperative taboo optimization mode based cloud computing workflow

scheduling strategy for strong security constraint

TONG Weiguo1， 2， SHA Xiaoyan1， 2， FENG Demin2

（1. Education Technology and Training Center， Shaanxi Vocational Technical College， Xi’an 710038， China；

2. School of Computer Science， Shaanxi Normal University， Xi’an 710065， China）

Abstract： The widely?used cloud computing workflow scheduling method focuses on the optimization of reliability and energy saving， but ignores the requirement of security constraint， so a method based on cooperative taboo algorithm is proposed here， which can realize the high?efficient cloud computing workflow scheduling， and has security constraint. The DAG of cloud computing workflow scheduling is defined to describe the security constraint with formalization， and establish the mathematical model of the cloud computing workflow scheduling. On the basis of using the classical cooperative taboo algorithm， the coding scheme， fitness function， varying neighbourhood structure and dual taboo tables of the solution are designed， and the classical cooperative taboo algorithm is improved. The cloud computing workflow scheduling algorithm based on an improved cooperative taboo algorithm is defined. The experiment of the algorithm was conducted in the simulation environment Cloud?Sim. The experimental results prove that the designed algorithm has fast convergence speed， can find a much better scheduling scheme than other algorithms can do， meets the requirements of security constraint， and is a practical scheduling method.

Keywords： workflow scheduling； virtual machine； security constraint； cloud computing

0 引 言

云計(jì)算主要是基于并行計(jì)算等形成的[1?3]，到目前為止，相對(duì)于并行系統(tǒng)來說，云計(jì)算可以提供相對(duì)較高的可靠性，然而其仍然面臨許多難題，例如無法在充分確保服務(wù)質(zhì)量的基礎(chǔ)上，減小其運(yùn)行費(fèi)用和能耗，使提供商可以獲得盡可能高的收益[4?6]。

對(duì)于云計(jì)算工作流來說，諸多因素能夠影響到其調(diào)度效率，具體來說，主要包括調(diào)度的可靠性、硬件性能等諸多方面[7]?，F(xiàn)階段，業(yè)界對(duì)其調(diào)度的探討一般集中在可靠性與節(jié)能兩個(gè)層面，例如，文獻(xiàn)[8]在研究過程中以可靠性為基礎(chǔ)，闡明了相應(yīng)的調(diào)度方法，以降低傳輸所需用時(shí)，改善成功率，使其可靠性有所提升。文獻(xiàn)[9]在研究過程中量化了網(wǎng)絡(luò)資源屬性，這樣在調(diào)度過程中可以選取性能相對(duì)較高的資源類簇，能夠進(jìn)一步減少任務(wù)的匹配用時(shí)。文獻(xiàn)[10]在研究過程中通過相關(guān)方法整合任務(wù)路徑優(yōu)化選擇。除此之外，文獻(xiàn)[11]在研究過程中根據(jù)[QQS]需求劃分優(yōu)先級(jí)，將資源分配給高優(yōu)先級(jí)的任務(wù)。

上述理論成果集中在云計(jì)算工作流調(diào)度方面，卻沒有兼顧到安全性約束，鑒于這一方面的原因，本文闡明了基于安全性約束的云計(jì)算流調(diào)度方法，希望能夠?yàn)闃I(yè)界人士提供指導(dǎo)和借鑒。

1 云計(jì)算工作流調(diào)度[DAG]圖

主要通過有向無環(huán)圖（Direct Acirclic Graph，DAG）表示任務(wù)結(jié)構(gòu)，具體見圖1。

通過圖1得知，[DAG]圖能夠通過二元組描述[DAG=T，E]，在這里：

（1） [T=t1，t2，…，tn]用來指代[DAG]里面的節(jié)點(diǎn)集，即子任務(wù)集，[n=T]用來指代任務(wù)數(shù)，[W（ti）]指代[ti]的計(jì)算量；

（2）[E=eij=（ti，tj），eij∈T×T]是有向邊集合，用來指代[ti]與[tj]兩者之間存在的依賴關(guān)系，[tj]一定要等到[ti]結(jié)束以后才可以進(jìn)行處理。

通過[C]指代任務(wù)相互間的通信關(guān)系[C=][cij=（ti，tj），cij∈T×T]，[cij]用來指代[ti]與[tj]分配至資源上時(shí)需要的通信量，如果[ti]與[tj]兩者分配至一個(gè)資源上，在這種情況下則有[cij=0]。

[Pred（ti）=titj∈T，eij∈E，][Succ（ti）=titj∈T，eij∈E，]兩者分別用來指代[ti]的前驅(qū)任務(wù)集與后繼任務(wù)。

2 基于DAG和安全性約束的工作流調(diào)度

2.1 工作安全性約束

按照所用方法的安全性強(qiáng)度，能夠把虛擬機(jī)分成不同級(jí)別的安全性，按照操作的敏感性，主要通過[r?risk]型技術(shù)進(jìn)行控制，具體來說，也就是在調(diào)度工作流過程中，設(shè)置其冒險(xiǎn)水平閾值[τ，]安全等級(jí)比[τ]高的虛擬機(jī)能夠分配資源。接下來進(jìn)行建模，具體如下：

（1） 單一的[ti]符合安全性約束的分配：它的[τi]分配的虛擬機(jī)及其安全性級(jí)別分別是[vj]與[sj，]如果[sj≥τi，]在這種情況下這個(gè)虛擬機(jī)符合相關(guān)條件，能夠向[ti]分配。比如就安全需求是3的操作來說，能夠向[vj≥4]的虛擬機(jī)分配。

（2）[DAG]符合安全性約束的調(diào)度：[T=t1，t2，…，tn]的分配方案的風(fēng)險(xiǎn)概率[P=p1，p2，…，pn]，能夠利用以下公式進(jìn)行求解：

[p（risk）=1-eumi=1m（si-vsi）] （1）

如果[p（risk）]比一切任務(wù)的[τi]大，在這種情況下，[P=p1，p2，…，pn]符合相關(guān)要求。

2.2 數(shù)學(xué)模型的定義

就任何一項(xiàng)任務(wù)來說，它的操作時(shí)間主要包括兩方面內(nèi)容：其一為接收信息的用時(shí)；其二為把任務(wù)向相應(yīng)的虛擬機(jī)分配的用時(shí)。就任何一個(gè)任務(wù)來說，符合相關(guān)要求的虛擬機(jī)集用[M]來指代，它的操作時(shí)間用[Finishi]表示，具體能夠利用以下公式進(jìn)行求解：

[Finishi=maxFinishprei+Cmibanij+LiPi s，tj∈M] （2）

式中：對(duì)于當(dāng)前節(jié)點(diǎn)，[maxFinishprei]用來指代其任何一個(gè)前驅(qū)節(jié)點(diǎn)完成用時(shí)的極值；[Cmi]用來指代其需輸送的數(shù)據(jù)量；[Li]用來指代其工作量；[Pi]用來指代其分配到的虛擬機(jī)的處理速度；[banij]用來指代發(fā)出信息和分配至目的地的兩個(gè)虛擬機(jī)間的帶寬大小。

耗時(shí)最大的任務(wù)用時(shí)是全部任務(wù)完成時(shí)間，也就是：

[FinishDAG=maxFinishi] （3）

3 基于禁忌優(yōu)化算法的工作流調(diào)度

3.1 禁忌優(yōu)化算法

為有效避免算法在運(yùn)行過程中止步于局部最優(yōu)，禁忌優(yōu)化算法主要是通過禁忌表對(duì)那些得到的局部最優(yōu)解進(jìn)行存儲(chǔ)，在此基礎(chǔ)上設(shè)定其禁忌長度，當(dāng)再次進(jìn)行搜索時(shí)，通過表里面存儲(chǔ)的數(shù)據(jù)決定將這些點(diǎn)跳過，最終能夠避免局部最優(yōu)。另一方面，該算法也可以按照藐視準(zhǔn)則將那些被禁忌的優(yōu)良狀態(tài)赦免，選取其中的最優(yōu)解，從而得到全局最優(yōu)解。較具代表性的禁忌算法示意圖，如圖2所示。

3.2 解的編碼方式和適應(yīng)度函數(shù)

通過[P=p1，p2，…，pn]指代當(dāng)前解，其中的各元素[pi]指代[ti]分配的[vi，]所以[DAG]工作流的編碼長度即為該用戶任務(wù)的子任務(wù)總數(shù)[n]。

所謂適應(yīng)度函數(shù)，是指禁忌算法在找尋最優(yōu)解時(shí)最大化目標(biāo)函數(shù)，公式（4）為最小化式（3）重描述的[DAG]的任務(wù)完成時(shí)間：

[Fitness=1FinishDAG] （4）

3.3 鄰域結(jié)構(gòu)設(shè)計(jì)

圖2中，在候選解的生成過程中，必須構(gòu)建鄰域結(jié)構(gòu)，在這里若鄰域解與當(dāng)前解兩者存在明顯的差異，在這種情況下，將變成隨機(jī)搜索，另一方面，變化相對(duì)較小將導(dǎo)致收斂速度下降，或許將止步于局部最優(yōu)，鑒于這一方面，必須提前設(shè)計(jì)科學(xué)有效的鄰域結(jié)構(gòu)，這樣一方面可以充分確保獲得最優(yōu)解，另一方面還可以提高收斂速度。

設(shè)基本鄰域結(jié)構(gòu)如下所示：對(duì)當(dāng)前任務(wù)節(jié)點(diǎn)，任選1個(gè)虛擬機(jī)（符合安全性約束要求），通過這種方式能夠避免陷入隨機(jī)搜索，能夠在科學(xué)有效的區(qū)間尋求新解，為避免陷入早熟，構(gòu)造2種變鄰域結(jié)構(gòu)，在完成設(shè)定的迭代次數(shù)以后，若所獲當(dāng)前解的適應(yīng)度仍然沒有出現(xiàn)大幅的改進(jìn)，在這種情況下將會(huì)分別通過下文中的結(jié)構(gòu)1與2形成新解。

變鄰域結(jié)構(gòu)1：自當(dāng)前解每次形成1個(gè)候選解，能夠利用重復(fù)對(duì)基本鄰域結(jié)構(gòu)進(jìn)行[S]次調(diào)用實(shí)現(xiàn)；

變鄰域結(jié)構(gòu)2：在解釋當(dāng)前解產(chǎn)生鄰域的過程中，必須將其周圍的[2S]區(qū)域中全部節(jié)點(diǎn)的虛擬機(jī)編號(hào)改變。

3.4 基于改進(jìn)禁忌優(yōu)化的工作流調(diào)度算法

具體來說，該種方法的具體過程如下所示：

輸入：[T=t1，t2，…，tn]（用來指代全部任務(wù)集），[rmax]（是指最優(yōu)解最大沒有改變的次數(shù)），[V=v1，v2，…，vn]（用來指代當(dāng)前虛擬機(jī)集合），[S]（參考值），[L]（禁忌表長度），[K]（候選集元素個(gè)數(shù)），[T]（算法最大迭代次數(shù)），[M，][N]（兩者分別用來指代[Sselected]與[Sneighbor]的元素個(gè)數(shù)最大值）；

輸出：全局最優(yōu)解[best?far]；

step1：隨機(jī)產(chǎn)生符合相關(guān)要求的解，將其當(dāng)作當(dāng)前解[xcur，]初始化[best?far=xinitial，]最優(yōu)解未變化次數(shù)[r=1，]當(dāng)前迭代次數(shù)[t=1]；

step2：把[xcur]與移動(dòng)量[（0，0）]分別置于禁忌表[TB]與TW里面，設(shè)定禁忌長度是[L]；

step3：判定[t≤T]成立與否：若[t ≤T]成立，在這種情況下就會(huì)結(jié)束該算法，然后將[best?far]輸出；否則[t=t+1]；

step4：按照在3.3節(jié)中提出的鄰域結(jié)構(gòu)生成[xcur]的[Sneighbor，]一直至[Sneighbor]里面有[N]個(gè)元素結(jié)束，從中取[K] 個(gè)最優(yōu)解，將它們作為候選解，在此基礎(chǔ)上，加入[Sselected；]

step5：把[Sselected]里面的[Sselected?best]和[best?far]進(jìn)行對(duì)比：

[If Fitness（Sselected?best）]>[Fitness（best?far）]

[r=r+1]；

[best?far=Sselected?best]

[xcur=Sselected?best]

假如[Sselected?best]沒在禁忌表里面，在這種情況下，把[Sselected?best]加到TB中，并且設(shè)定它的禁忌長度是[L]，把它的移動(dòng)方式加到TW中，同時(shí)，設(shè)定其余元素的禁忌長度是[-1]；

否則取沒有被禁忌的下一較優(yōu)候選解[4]當(dāng)作[xcur，]然后把它加至禁忌表中，把它的移動(dòng)方式加到TW中，對(duì)其余元素進(jìn)行更新，使其禁忌長度是[-1]；

step6：[t=t+1]，在此基礎(chǔ)上，重新從step3開始。

4 仿真實(shí)驗(yàn)

實(shí)驗(yàn)環(huán)境為[Cloud Sim][12]，圖3為工作流任務(wù)實(shí)例，在這里，為了能夠和文獻(xiàn)[13]的方法進(jìn)行對(duì)比分析，此處選擇的參數(shù)都和文獻(xiàn)[13]的設(shè)置相同，橢圓中是指各子任務(wù)，工作量均勻分布在區(qū)間[[50，500]]中，總共有[4]個(gè)虛擬機(jī)，相互間的帶寬矩陣具體如下：

[Mv=04012080400601001206009080100900] （5）

全部的任務(wù)中，只有第[6]個(gè)[τ]是4，剩下的都是2，安全性等級(jí)依次為：2，2，3，4。

相關(guān)參數(shù)主要包括：[rmax=4，][L=4，][S=1，][N=5，][M=3，][T=200，][K=6。]

以圖3為實(shí)例，通過將本文提出的算法、文獻(xiàn)[11]和[13]提出算法的結(jié)果相對(duì)比，獲得各個(gè)算法的收斂圖，如圖4所示。

通過圖4能夠得知，本文所提出的算法在[140]代收斂，其工作流調(diào)度用時(shí)是[178.4]，后面2個(gè)算法的用時(shí)依次是[195.1]與[210]，文獻(xiàn)[11]提出的算法在仿真過程中均未達(dá)到收斂，但文獻(xiàn)[13]的方法在[180]代達(dá)到收斂，然而并未獲得全局最優(yōu)解，通過對(duì)比可以看出，本文提出的算法一方面其收斂速度相對(duì)較好，另一方面還能夠獲得更優(yōu)解。

進(jìn)一步驗(yàn)證三者對(duì)約束的敏感狀況，具體測(cè)試結(jié)果見圖5。

通過圖5能夠得知，本文所提出的算法與文獻(xiàn)[13]提出的方法充分兼顧到安全性約束，另一方面，在有無約束時(shí)的平均用時(shí)具有相對(duì)偏小的差異，值得注意的是，文獻(xiàn)[11]提出的方法并未兼顧到相關(guān)約束，正是這一方面的原因，所以，該方法無法妥善處理安全型約束的云工作流調(diào)度問題。

5 結(jié) 語

綜上所述，為科學(xué)調(diào)度云計(jì)算中的任務(wù)，必須妥善處理的第一個(gè)環(huán)節(jié)即工作流調(diào)度，針對(duì)該問題，本文提出了基于安全型約束的云計(jì)算工作流高效調(diào)度法。構(gòu)建了相應(yīng)的調(diào)度模型與目標(biāo)函數(shù)，在此基礎(chǔ)上，通過協(xié)同禁忌算法進(jìn)行尋優(yōu)。最后，本文還在Cloud Sim環(huán)境平臺(tái)下開展相應(yīng)的仿真實(shí)驗(yàn)，結(jié)果說明提出的新方法的效果相對(duì)較好，一方面其收斂速度相對(duì)偏高，另一方面其可以獲得相對(duì)較優(yōu)的解。

參考文獻(xiàn)

[1] DU Z H， HU J K， CHEN Y N， et al. Optimized QoS?aware replica placement heuristics and applications in astronomy data grid [J]. Journal of systems and software， 2011， 84 （7）： 1224?1232.

[2] 厲劍.云計(jì)算安全問題分析[J].現(xiàn)代電子技術(shù)，2013，36（19）：91?94.

[3] 劉少偉，孫令梅，任開軍，等.云環(huán)境下優(yōu)化科學(xué)工作流執(zhí)行性能的兩階段數(shù)據(jù)放置與任務(wù)調(diào)度策略[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（11）：2121?2130.

[4] 陳良維.云計(jì)算環(huán)境下的網(wǎng)絡(luò)安全估計(jì)模型態(tài)勢(shì)仿真[J].現(xiàn)代電子技術(shù)，2015，38（20）：15?19.

[5] VAQUERO L M， RODERO?MERINO L， MORAN D. Locking the sky： a survey on IaaS cloud security [J]. Computing， 2011， 91（1）： 93?118.

[6] MALIK S， HUEF F， CAROMEL D. Reliability aware sche?duling in cloud computing [C]// Proceedings of 2012 International Conference for Internet Technology and Secured Transactions. Piscataway： IEEE press， 2012： 194?200.

[7] KANG Q， HE H， WEI J. An effective iterated greedy algorithm for reliability?oriented task allocation in distributed computing systems [J]. Journal of parallel and distributed compu?ting， 2013， 73（8）： 1106?1115.

[8] 閆歌，于炯，楊興耀.基于可靠性的云計(jì)算工作流調(diào)度策略[J].計(jì)算機(jī)應(yīng)用，2014，34（3）：673?677.

[9] 儲(chǔ)雅，馬廷淮，趙立成.云計(jì)算資源調(diào)度：策略與算法[J].計(jì)算機(jī)科學(xué)，2013，40（11）：8?13.

[10] 胡蒙，苑迎春，王雪陽.改進(jìn)模糊聚類的云任務(wù)調(diào)度算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2015，36（9）：2437?2441.

[11] 孫月，于炯，朱建波.云計(jì)算中一種多DAG工作流可搶占式調(diào)度策略[J].計(jì)算機(jī)科學(xué)，2014，41（3）：145?148.

[12] 王宇賓.基于CloudSim的作業(yè)調(diào)度算法評(píng)價(jià)模型設(shè)計(jì)與實(shí)現(xiàn)[J].現(xiàn)代電子技術(shù)，2015，38（14）：12?15.

[13] 馬俊波，殷建平.云計(jì)算環(huán)境下帶安全約束的工作流調(diào)度問題的研究[J].計(jì)算機(jī)工程與科學(xué)，2014，36（4）：607?614.