同衛(wèi)國，沙曉燕，馮德民

（1.陜西職業(yè)技術(shù)學院教育技術(shù)與實訓(xùn)中心，陜西西安710038；2.陜西師范大學計算機學院，陜西西安710065）

基于協(xié)同禁忌優(yōu)化模式的云計算強安全約束工作流調(diào)度策略

同衛(wèi)國1，2，沙曉燕1，2，馮德民2

（1.陜西職業(yè)技術(shù)學院教育技術(shù)與實訓(xùn)中心，陜西西安710038；2.陜西師范大學計算機學院，陜西西安710065）

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

工作流調(diào)度；虛擬機；安全性約束；云計算

0　引言

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

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

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

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

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

圖1　工作流調(diào)度DAG圖

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

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

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

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

Pred(ti)={ti|tj∈T,eij∈E}，Succ(ti)={ti|tj∈T,eij∈E}，兩者分別用來指代ti的前驅(qū)任務(wù)集與后繼任務(wù)。

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

2.1工作安全性約束

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

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

（2）DAG符合安全性約束的調(diào)度：T={t1,t2,…,tn}的分配方案的風險概率P={p1,p2,…,pn}，能夠利用以下公式進行求解：

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

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

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

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

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

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

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

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

圖2　傳統(tǒng)禁忌算法流程框圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

step5：把Sselected里面的Sselected-best和best-far進行對比：

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

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

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

4　仿真實驗

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

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

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

圖3　工作流任務(wù)實例

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

圖4　3種算法收斂曲線對比

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

進一步驗證三者對約束的敏感狀況，具體測試結(jié)果見圖5。

圖5　有無安全性約束的平均完成時間

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

5　結(jié)語

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

[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].現(xiàn)代電子技術(shù)，2013，36（19）：91-94.

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

[4]陳良維.云計算環(huán)境下的網(wǎng)絡(luò)安全估計模型態(tài)勢仿真[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 scheduling 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 computing，2013，73（8）：1106-1115.

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

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

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

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

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

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

Cooperative taboo optimization mode based cloud computing workflow scheduling strategy for strong security constraint

TONG Weiguo1，2，SHA Xiaoyan1，2，F(xiàn)ENG 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）

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.

workflow scheduling；virtual machine；security constraint；cloud computing

TN915-34

A

1004-373X（2016）21-0011-04

10.16652/j.issn.1004-373x.2016.21.003

2016-01-06

國家自然科學基金面上項目（61173190）

同衛(wèi)國（1977—），男，陜西渭南人，工程師。研究方向為云計算與互聯(lián)網(wǎng)應(yīng)用。

沙曉燕（1972—），女，陜西西安人，教授。研究方向為多媒體技術(shù)及應(yīng)用。

馮德民（1955—），男，陜西西安人，教授。研究方向為云計算應(yīng)用。