基于協同禁忌優化模式的云計算強安全約束工作流調度策略

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

關鍵詞： 工作流調度； 虛擬機； 安全性約束； 云計算

中圖分類號： TN915?34 文獻標識碼： A 文章編號： 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 引 言

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

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

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

1 云計算工作流調度[DAG]圖

主要通過有向無環圖（Direct Acirclic Graph，DAG）表示任務結構，具體見圖1。

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

（1） [T=t1，t2，…，tn]用來指代[DAG]里面的節點集，即子任務集，[n=T]用來指代任務數，[W（ti）]指代[ti]的計算量；

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

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

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

2 基于DAG和安全性約束的工作流調度

2.1 工作安全性約束

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

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

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

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

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

2.2 數學模型的定義

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

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

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

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

[FinishDAG=maxFinishi] （3）

3 基于禁忌優化算法的工作流調度

3.1 禁忌優化算法

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

3.2 解的編碼方式和適應度函數

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

所謂適應度函數，是指禁忌算法在找尋最優解時最大化目標函數，公式（4）為最小化式（3）重描述的[DAG]的任務完成時間：

[Fitness=1FinishDAG] （4）

3.3 鄰域結構設計

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

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

變鄰域結構1：自當前解每次形成1個候選解，能夠利用重復對基本鄰域結構進行[S]次調用實現；

變鄰域結構2：在解釋當前解產生鄰域的過程中，必須將其周圍的[2S]區域中全部節點的虛擬機編號改變。

3.4 基于改進禁忌優化的工作流調度算法

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

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

輸出：全局最優解[best?far]；

step1：隨機產生符合相關要求的解，將其當作當前解[xcur，]初始化[best?far=xinitial，]最優解未變化次數[r=1，]當前迭代次數[t=1]；

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

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

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

step5：把[Sselected]里面的[Sselected?best]和[best?far]進行對比：

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

[r=r+1]；

[best?far=Sselected?best]

[xcur=Sselected?best]

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

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

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

4 仿真實驗

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

[Mv=04012080400601001206009080100900] （5）

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

相關參數主要包括：[rmax=4，][L=4，][S=1，][N=5，][M=3，][T=200，][K=6。]

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

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

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

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

5 結 語

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

參考文獻

[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].現代電子技術，2013，36（19）：91?94.

[3] 劉少偉，孫令梅，任開軍，等.云環境下優化科學工作流執行性能的兩階段數據放置與任務調度策略[J].計算機學報，2011，34（11）：2121?2130.

[4] 陳良維.云計算環境下的網絡安全估計模型態勢仿真[J].現代電子技術，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].計算機應用，2014，34（3）：673?677.

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

[10] 胡蒙，苑迎春，王雪陽.改進模糊聚類的云任務調度算法[J].計算機工程與設計，2015，36（9）：2437?2441.

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

[12] 王宇賓.基于CloudSim的作業調度算法評價模型設計與實現[J].現代電子技術，2015，38（14）：12?15.

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