云計算環(huán)境下帶安全約束的工作流調(diào)度問題的研究＊

馬俊波，殷建平

（國防科學技術大學計算機學院，湖南 長沙 410073）

1 引言

云計算作為一種新興的計算模式，以其特有的隨需自助式服務、廣泛的網(wǎng)絡訪問、共享的資源池、快速彈性能力、服務的可度量性等特性［1］，正逐漸地深入到互聯(lián)網(wǎng)生活的各個方面。云服務提供商通過把眾多的計算機軟硬件資源整合為虛擬的資源池為用戶提供服務，并通過與用戶簽訂的服務水平協(xié)議SLA（Service Level Agreement），向用戶承諾服務質(zhì)量QoS（Quality of Service）。用戶可以根據(jù)自身的需要，向云服務提供商申請相應的計算資源，并在使用完畢后釋放這些資源以供其他用戶使用。由于計算資源和用戶規(guī)模巨大，且具有快速彈性變化的特性，使得云平臺下的資源調(diào)度問題一直是該領域研究的熱點問題。

當前對資源調(diào)度問題的研究主要集中在減少完成時間、降低用戶開銷和提高負載均衡等問題上，很少去考慮用戶對安全和隱私等約束條件的需求。然而，云計算平臺從誕生之日起，其安全問題就一直是廣大用戶和云服務提供商們關注的焦點問題之一。因此，在云計算資源調(diào)度的過程中加入安全約束，滿足用戶在資源調(diào)度過程中對安全的QoS需求就具有十分重要的意義。

2 相關工作

云計算中，許多大型的應用程序通常都是由一組有數(shù)據(jù)依賴關系和執(zhí)行順序約束的子任務組成，這類任務通常被抽象為工作流的形式。這種工作流模型在云計算的資源調(diào)度研究中被廣泛地使用［2］。

Abrishami S等人［2］以用戶給定的最后完成期限為主要約束條件，提出了兩個多項式時間復雜度的算法，使它們能夠滿足大規(guī)模的工作流程序的調(diào)度任務，并在實際的科學計算工作流上進行了實驗，取得了很好的性能。Liu K等人［3］則是以任務的花費為主要約束條件，針對實例密集型的工作流任務，在綜合考慮任務的執(zhí)行時間和執(zhí)行開銷的基礎上，提出了一種滿足用戶預算的調(diào)度算法；并且實驗表明，該算法不僅能夠消減任務的平均執(zhí)行成本，還能在滿足用戶預算的條件下縮短任務的平均執(zhí)行時間。Rao J等人［4］充分考慮了云環(huán)境下的動態(tài)變化特性，為了保證Web服務器在給定的響應時間的條件下對虛擬資源進行分配，提出了一種自適應的模糊控制方法；并在此基礎上進一步設計了一個兩層的QoS框架，這個框架在性能和功耗控制方面，對多目標QoS控制和服務差異化管理具有很好的性能優(yōu)勢。Wu Z等人［5］以云計算的這種以市場為導向的業(yè)務模式為基礎，提出了一種以市場為導向的分層調(diào)度策略，以滿足用戶的各項QoS需求；在此基礎上，為服務層提出了一種基于包的隨機調(diào)度算法，并使用了三個具有代表性的智能優(yōu)化算法作為啟發(fā)式，討論了它們的各項性能。Ergu D等人［6］根據(jù)現(xiàn)有的可用資源和用戶偏好，使用成對比較矩陣技術和層次分析方法，為任務劃分了等級，并提出了一種面向任務等級的資源分配模式，給出了在各種任務中算法對資源調(diào)度過程中分配和改善的一致性比率。

這些文獻分別從不同的角度對云環(huán)境下的資源調(diào)度問題進行了深入的研究，提出了資源調(diào)度的方法和策略，但正如前文所提到的，這些研究都很少去考慮用戶對安全的QoS需求。

3 系統(tǒng)模型

3.1 符號與說明

本文使用的相關術語和符號定義如下：

（1）計算資源。

在云計算模型中，實際的物理資源通過虛擬化技術虛擬化為資源池來進行統(tǒng)一的管理和分配，向用戶提供透明的計算服務和數(shù)據(jù)存儲功能，屏蔽了物理層的部署細節(jié)。因此，本文提到的計算資源是由當前云平臺可用虛擬機組成的，即R＝｛vm1，vm2，…，vmn｝，n為虛擬機總數(shù)。每臺虛擬機的屬性包括計算能力MIPS（Million Instructions Per Second）、存儲能力、內(nèi)存、帶寬等。本文只考慮計算能力這一屬性，令計算能力P＝｛Pi｝，其中i∈｛1，2，…，n｝，元素存儲的是第i臺虛擬機對應的計算能力，同時每臺虛擬機都有一個特定的安全等級SR（Security Rank），令SR＝｛srj｝，則第j個虛擬機的安全等級就表示為srj，其中j∈｛1，2，…，n｝。

（2）通信矩陣。

虛擬機之間通過網(wǎng)絡相互連接，兩臺虛擬機之間的最小通信代價記錄在通信矩陣Comu＝［cmij］中，其中i，j∈｛1，2，…，n｝，矩陣中的元素cmij表示從虛擬機vmi到vmj之間傳輸單位數(shù)據(jù)所需的最小時間，并且當i＝j時，令cmij＝0。

（3）計算任務和原子操作。

一個計算任務通常可以分解為一組相互約束的原子操作，即T＝｛O1，O2，…，Om｝，m為原子操作總數(shù)。每個操作通常由一臺虛擬機完成，并有輸入數(shù)據(jù)和輸出數(shù)據(jù)。操作之間有執(zhí)行先后順序的約束，即工作流約束。每個操作都有特定的指令長度MI（Million Instructions），定義指令長度L＝｛Li｝，其中i∈｛1，2，…，m｝，元素Li存儲的是第i個操作對應的指令長度，同時每個操作都有相應的安全等級需求SD（Security Demand），令SD＝｛sdj｝，則第j個操作的安全需求就表示為sdj，其中j∈｛1，2，…，m｝。

（4）工作流約束。

工作流約束一般使用有向無環(huán)圖DAG（Directed Acyclic Graph）來表示，有向無環(huán)圖中的節(jié)點表示子任務，邊表示數(shù)據(jù)的依賴關系和通信的開銷。定義工作流表示為有向無環(huán)圖G（O，E），其中O為節(jié)點集合，對應于計算任務的操作集合，即O＝｛O1，O2，…，Om｝；E為邊的集合，每條邊都有確定的方向和權值，用來表示操作之間的執(zhí)行先后的約束和數(shù)據(jù)傳輸量。

對于邊（Op，Oq）∈E，表示當Op完成并把數(shù)據(jù)傳輸?shù)絆q后，Oq才能開始執(zhí)行，并且從Op輸出并傳輸?shù)絆q的數(shù)據(jù)量為該邊的權值，稱Op是Oq的前驅(qū)節(jié)點，Oq是Op的后繼節(jié)點。如圖1為一個包含了15個操作的工作流約束。

（5）調(diào)度方案。

對于任務T＝｛O1，O2，…，Om｝的調(diào)度方案S＝｛s1，s2，…，sm｝，其中sk表示操作Ok分配到的虛擬機編號，sk∈｛1，2，…，n｝。

Figure 1 A workflow task with 15operations圖1 包含15個操作的工作流任務

3.2 安全約束模型

互聯(lián)網(wǎng)發(fā)展至今，已經(jīng)擁有了一系列的安全技術來應對安全問題，如加密解密技術，認證、授權和審計技術，防火墻技術，安全接入技術等［7］。根據(jù)使用技術的安全強度，以及虛擬機上運行的軟件的安全程度，可以為虛擬機劃分相應的安全等級。同時，根據(jù)操作的敏感程度、訪問控制、操作執(zhí)行所需的環(huán)境以及用戶的需求等，可以為操作劃分相應的安全需求sd。本文把安全定性地劃分為五個等級：

很高→5；高→4；中→3；低→2；很低→1

常見的安全約束模型有三類［8］：

（1）安全型：在進行調(diào)度時，僅把操作分配到能夠滿足安全需求的虛擬機上，即當且僅當sdi≤srj時，把操作Oi分配到虛擬機vmj上，其中i∈｛1，2，…，m｝，j∈｛1，2，…，n｝。

（2）冒險型：在進行調(diào)度時，不考慮安全約束，直接把操作分配到可用的虛擬機上。

（3）r－risky型：在進行調(diào)度時，最多冒r的風險，其中r表示發(fā)生風險的系數(shù)，用來衡量發(fā)生風險的概率。并且當r＝0時，對應于安全型；當r＝1時，對應于冒險型。

冒險型的調(diào)度方式過于激進，而安全型調(diào)度方式一般來講難度較大，并且需要花費較大的代價才能實現(xiàn)，特別是當任務的實時性要求較高時，為了減少任務的完成時間，滿足用戶對任務完成截至期限的需求，一般采用r－risky型調(diào)度方式。這樣一方面保證了任務的安全，另一方面能夠降低調(diào)度的代價，并在一定程度上減少完成任務所需要的時間。

本文定義的安全約束由兩部分組成：

（1）對于單個操作Oi和其分配到的虛擬機vmj，要求sdi－srj≤θ，θ∈｛0，1，2，3，4，5｝，其中θ為安全等級跨度，并且當sdi－srj≤0時，認為該調(diào)度是安全的。例如，當θ＝2時，對于安全需求為4的操作，可以分配到安全等級為2、3、4、5的虛擬機上，并且當把該操作分配到安全等級為4、5的虛擬機上時，認為該調(diào)度是安全的。

（2）對于任務T＝｛O1，O2，…，Om｝的整體調(diào)度方案S＝｛s1，s2，…，sm｝的風險概率由公式（1）求得，并要求該調(diào)度方案的P（risk）≤r：

其中μ為常數(shù)，根據(jù)任務對風險的承受程度適當選擇。

則安全約束就可以表示為一個二元組Secu＝（θ，r）。

3.3 問題定義

由于許多最優(yōu)調(diào)度問題是NP－h(huán)ard問題［2］，一般而言為了簡化和解決調(diào)度問題，會做出一定的假設條件。本文使用的假設條件如下，這些假設也是該領域內(nèi)常用的假設條件：

（1）當前驅(qū)操作完成并把數(shù)據(jù)傳送到后繼操作時，后繼操作立即開始執(zhí)行。

（2）虛擬機每次只能運行一個操作，其余操作進入排隊隊列。

（3）虛擬機創(chuàng)建的時間為零或有統(tǒng)一的時間間隔。

（4）每個操作只能分配到一個虛擬機上。

（5）一旦一個操作分配給了一個虛擬機，那么它將連續(xù)運行，直到操作結束。

（6）操作只在開始和結束的時候產(chǎn)生數(shù)據(jù)通信。

工作流約束G（O，E）可以用工作流矩陣F＝［fpq］來表示，當存在邊（Op，Oq）∈E時，把邊的權值保存到矩陣的元素fpq中，當Op和Oq之間沒有邊連結時，fpq＝0。對于圖1所示的工作流約束，可以表示為如下所示的工作流矩陣F：

任務T＝｛O1，O2，…，Om｝中的操作Oi，其完成時間由兩部分組成，即接收輸入數(shù)據(jù)所需要的時間開銷，和操作在其分配到的虛擬機上運算所需要的時間開銷。當兩個操作部署在同一臺虛擬機上時，數(shù)據(jù)傳輸時間忽略不計，這可以通過把通信矩陣Comu中的對角線元素置0來實現(xiàn)，即當i＝j時，令cmij＝0。對于任務的一個調(diào)度方案S＝｛s1，s2，…，sm｝，定義操作Oi的完成時間為COi，其計算公式如下所示：

定義cvmi為虛擬機vmi執(zhí)行完分配到其中的所有操作所需要的時間，即Cvmi＝∑COk，當且僅當Ok分配在vmi上時。那么整個任務的完成時間就為耗時最長的虛擬機的執(zhí)行時間，即Ccomp＝max｛Cvmi｝。若要使任務的完成時間最小，則是求Ccomp的最小值，則優(yōu)化目標可表示為：f＝min｛Ccomp｝。

那么帶有安全約束的資源調(diào)度問題可定義為：在滿足約束F、Comu、Secu的條件下，把任務T部署到資源R上，并達到優(yōu)化目標f?？尚问交硎緸椤牵剑═，R，F(xiàn)，Comu，Secu，f）。

4 基于變鄰域粒子群算法的調(diào)度策略

4.1 標準的粒子群優(yōu)化算法

粒子群優(yōu)化算法PSO（Particle Swarm Optimization），最早是由Kennedy J等人［9］于1995年提出的，是通過對鳥群捕食行為的研究，抽象出的一種基于迭代的優(yōu)化算法。算法首先隨機地初始化一個包含一定數(shù)量粒子的種群，種群中的每個粒子都代表一個潛在的解，粒子在問題的解空間中移動以找到最優(yōu)或足夠好的解。

在D維空間中，第i個粒子的位置可表示為xi＝（xi1，xi2，…，xiD）T，其速 度可以 表示為vi＝（vi1，vi2，…，viD）T，用pbest表示粒子本身所找到的歷史最優(yōu)解，用gbest表示整個種群找到的歷史最優(yōu)解，每一次迭代中，粒子的速度和位置通過如下兩個公式進行更新：

其中，ω稱為慣性常量，用來限定當前速度對粒子飛行行為的影響；當ω取值較大時，算法具有較強的全局搜索能力；當ω取值較小時，算法具有較強的局部搜索能力。c1是正常量，用來限定個體經(jīng)驗對粒子飛行軌跡的影響。c2是正常量，用來限定群體經(jīng)驗對粒子飛行軌跡的影響。c1，c2被稱為加速系數(shù)或?qū)W習因子，若c1＝0，則粒子只向群體學習，這樣容易陷入局部極值；若c2＝0，則粒子只向自身學習，這樣算法就退化為一個多起點的隨機搜索，通常c1，c2在［0，4］上，一般取c1＝c2＝2。r1和e2是均勻分布在［0，1］區(qū)間的隨機數(shù)，用以維護整個種群的多樣性［10］。

每一維的粒子速度都被限定在最大速度Vmax內(nèi)，每一維的粒子位置都被限定在最大邊界B內(nèi)。即：

并且

Vmax通常由β×B求得，其中0.1≤β≤1.0，并且通常情況下取β＝1。

PSO算法流程如圖2所示。

Figure 2 PSO flow diagram圖2 PSO算法流程圖

PSO算法的終止條件通常有三類［9］：

（1）達到最大迭代次數(shù)；

（2）在給定的迭代次數(shù)內(nèi)結果沒有提升；

（3）目標函數(shù)與最優(yōu)值之間的誤差小于預設值。

4.2 變近鄰粒子群優(yōu)化算法

變近鄰搜索VNS（Variable Neighborhood Search）［11］是一種后啟發(fā)式或構建啟發(fā)式框架，旨在解決組合優(yōu)化問題和全局優(yōu)化問題。VNS通過反復探索不斷擴大規(guī)模的鄰域，并使用抖動策略，以尋求更好的局部最優(yōu)解。VNS通過從gbest的鄰域中抽取的起始點開始啟動局部搜索，通過迭代地增加鄰域的規(guī)模直到找到一個比當前值更好的局部最小值gbest，來逃離當前的局部最小值，重復這一步，直到達到預設的終止條件。變近鄰粒子群優(yōu)化算法VNPSO（Variable Neighborhood Particle Swarm Optimization）就是受VNS啟發(fā)而來的。在粒子群算法中，當一個粒子的速度低于給定的閾值vc時，新的速度由式（6）和式（7）得到［12］：

其中，u是一個取值在［－1，1］中、服從均勻分布的隨機數(shù)，即u～U（－1，1）。

根據(jù)粒子群優(yōu)化算法中速度的特性可知：

（1）當vid＞0且｜vid｜較大的時候，意味著粒子在該維度更傾向于向著該方向飛行，即最優(yōu)解在該速度的方向上；

（2）當vid＜0且｜vid｜較大的時候，意味著粒子在該維度更傾向于向著遠離該方向飛行，即最優(yōu)解在遠離該維度的方向上；

（3）當｜vid｜處于0附近時，說明該維度的局部最優(yōu)解就在粒子當前所在位置附近。

式（7）的目的就是在粒子速度很小的時候，添加一個隨機擾動，讓粒子不再圍繞著當前的局部最優(yōu)解來搜索，而是跳出該鄰域結構，在另外一個區(qū)域開始新的搜索。

算法的性能直接由vc和φ決定，當vc取值較大時，可以減少擺動的周期，但是在同等條件下會增加粒子跳過局部最小值的概率，即大的vc迫使粒子保持較快的飛行狀態(tài)，使其不能收斂到一個解上。φ的值直接影響粒子搜索的可變鄰域。VNPSO算法如下所示：

算法 VNPSO

輸入：算法所需的相關參數(shù)和結束條件。

輸出：全局最優(yōu)位置gbest。

步驟1 初始化粒子群規(guī)模N和其他相關參數(shù)；

步驟2 隨機初始化每個粒子的位置和速度；

步驟3 把結果沒有提高的迭代標志變量置0，flag＝0；

步驟4 while沒有達到結束條件時do：

步驟5t＝t＋1；

步驟6 計算每一個粒子的適應度值；

步驟7 更新gbest為其歷史最佳位置和當前所有粒子中使適應度值最小的位置；

步驟8 ifgbest得到改進thenflag＝0；

步驟9 elseflag＝flag＋1；

步驟10 fori＝1toN

步驟11 更新pbesti為其歷史最佳位置和當

前位置中使適應度最小的位置；

步驟12 forj＝1toN

步驟13 ifflag＜10then

步驟14 使用式（3）～式（5）更新粒子第j維的速度和位置；

步驟15 else

步驟16 使用式（6）、式（7）、式（5）更新粒子第j維的速度和位置；

步驟17 nextj

步驟18 nexti

步驟19 end while

4.3 基于VNPSO算法的求解策略

為了在調(diào)度問題中使用PSO算法，最關鍵的是要把調(diào)度問題的解映射到粒子空間中。

對于本文討論的含有m個原子操作的計算任務T＝｛O1，O2，…，Om｝和含有n個虛擬機的計算資源R＝｛vm1，vm2，…，vmn｝的問題，我們可以將它的一個可能的調(diào)度結果表示成矩陣x＝［xij］，其中i∈｛1，2，…，m｝，j∈｛1，2，…，n｝，當把操作Oi分配到虛擬機vmj上時，令xij＝1，否則令xij＝0。根據(jù)假設條件，一個操作只能分配到一臺虛擬機上，則矩陣x＝［xij］的每一行的元素中有且僅有一個元素值為1，其余元素值為0。同理，可以把每個粒子的速度表示為矩陣v＝［vij］，其中vij∈［－1，1］。

可見，在這樣的定義下粒子的位置是一個離散型的變量，并不能直接使用PSO算法。因此，我們需要對位置更新公式即公式（3）進行改造?？紤]速度矩陣中的元素vij，當vij較大時，表示粒子在該維度更趨向于向該方向飛行；而位置矩陣中的對應元素xij表示操作Oi分配到虛擬機上，由于一個操作只能分配到一臺虛擬機上，即每一行的元素中有且僅有一個元素值為1，則當位置矩陣第i行中第j列速度vij較大時，表示操作Oi更趨向于分配到虛擬機vmj上，那么在更新位置矩陣時可以將該粒子速度矩陣中每一行的最大值對應的元素在位置矩陣中置1，其他值置0：

每一個位置矩陣表示一個潛在的調(diào)度結果，而這個結果直接應用的話有可能會與工作流約束沖突，因此在算法開始前，對工作流約束中的操作進行拓撲排序，保證前驅(qū)操作都排在后繼操作之前，并且在計算適應度函數(shù)時引入等待機制，以滿足工作流約束的要求。如前文所示的工作流矩陣就是按拓撲排序后的操作生成的。

5 實驗結果與分析

本文的實驗使用的是云模擬平臺Cloud－Sim［13］，版本號為3.0.2。CloudSim是澳大利亞墨爾本大學的網(wǎng)格實驗室和Gridbus項目組推出的云計算仿真軟件，它實現(xiàn)了云計算區(qū)別于其他分布式系統(tǒng)的主要特征，即將各類異構的計算資源虛擬化為資源池，屏蔽了物理層的部署細節(jié)，特別是其中的NetworkCloudSim組件，使其對應用程序中消息的傳遞和工作流約束等擁有良好的仿真能力，并能夠更準確地評估資源調(diào)度和配置策略。

對圖1所示的工作流任務，其相關參數(shù)的取值如下：

任務中每個操作的長度隨機生成，取值范圍為［100，500］，滿足均勻分布，本次實驗中操作長度取值如下，單位是MI：

計算資源中虛擬機個數(shù)為4，計算能力取值為P＝｛4，6，8，10｝，單位是MIPS。虛擬機之間的通信矩陣如下所示，單位為ms（millisecond）：

對圖1所示的工作流任務，其工作流矩陣如前文所示。

對于操作的安全需求，令第六個操作的安全等級需求為4，其余操作均為2，即sd6＝4。對于虛擬機的安全等級取值為SR＝｛2，2，3，4｝。對于安全約束，本次實驗取最大風險跨度θ＝1，最大風險概率r＝0.2，即Secu＝（1，0.2），并且式（1）中的風險常數(shù)μ＝2。

VNPSO算法的相關參數(shù)取值如下：種群規(guī)模N＝30，加速系數(shù)c1＝c2＝1.4，最大速度Vmax＝1，對于慣性常數(shù)ω，采用常用的線性調(diào)整策略：

其中，ωmax、ωmin分別為ω的最大值和最小值，iter和itermax分別為當前迭代次數(shù)和最大迭代次數(shù)。本文的實驗取ωmax＝0.9，ωmin＝0.4，即隨著迭代的進行，ω由0.9線性遞減到0.4。

對于式（7）中的參數(shù)φ和vc，其取值在前3／4的迭代中取2和0.001，在剩下的迭代中取5和1e－5。

本文中與VNPSO算法做對比的是Max－Min蟻群算法MMACO（Max－Min Ant Colony Optimization）［14］和 遺 傳 算 法GA（Genetic Algorithm）［15］。

MMACO算法的相關參數(shù)為：蟻群規(guī)模為30，信息啟發(fā)式因子和期望啟發(fā)式因子均取1，信息素揮發(fā)系數(shù)取0.2，最佳解概率取0.005。GA算法的相關參數(shù)為：種群規(guī)模為30，交叉算子取0.8，變異算子取0.1

三個算法的終止條件均為迭代1 000次后終止。

實驗中，三個算法的種群規(guī)模相同，都是30，因此這三個算法的收斂速度都取決于種群對問題空間的搜索能力。

由式（3）可以看出，在PSO算法中，粒子的速度受兩大因素的影響：首先，在慣性常量ω的作用下，沿著原速度方向?qū)栴}空間進行搜索，ω的大小就決定了粒子沿著原速度方向運動的步長，所以當ω越大，該粒子對問題空間搜索的速度就越快；其次，在pbest和gbest的共同影響下，粒子會對速度的方向進行調(diào)整，逐漸向最優(yōu)解的方向進行搜索；最后，由隨機數(shù)r1和r2保證了粒子種群的多樣性。通過分析可以看出，由于每次迭代時種群絕大部分的粒子都會向著最優(yōu)解的方向?qū)ψ陨砦恢眠M行調(diào)整，因此每次迭代后，PSO算法都能對問題空間中更多潛在解進行搜索，所以PSO算法具有很好的全局搜索能力。

在ACO算法中，由于初始狀態(tài)下各個節(jié)點的信息素含量相同，均為初始值，此時蟻群中的每只螞蟻都會隨機地選取前進的路徑；隨著迭代次數(shù)的增加，每只螞蟻在選擇前進路徑的時候，會依信息素分布的強弱，依概率選擇較好的路徑，這樣一方面使尋找的路徑逐漸向目前發(fā)現(xiàn)的最優(yōu)路徑上靠攏，另一方面這種依概率的選擇也保證了蟻群的多樣性。特別是在Max－Min蟻群算法中，只有迭代最優(yōu)的螞蟻或全局最優(yōu)的螞蟻會對信息素進行更新，這樣就更加保證了算法對問題空間的的全局搜索能力。因此，蟻群算法在前期會有一個較為平緩的收斂過程，但隨著迭代的進行，信息素逐漸積累起來，算法會迅速向最優(yōu)解的方向收斂。

在GA算法中，由于對種群的更新的主要操作是交叉和變異，而變異操作概率較低，交叉操作在上一步選取的編碼相對優(yōu)秀的基因中隨機配對進行，所以每次迭代后對種群中產(chǎn)生的新的個體數(shù)量與前兩種算法相比所占比例較小，并且多樣性與前兩種算法相比略顯不足，因此相對而言，GA算法需要較多的迭代次數(shù)后才能達到與前兩種算法相同的結果。

在如前所給定的相關參數(shù)下，三個算法隨迭代次數(shù)的增加，其收斂情況如圖3所示。由于這三個算法的初始種群都是隨機生成的，故初始種群的質(zhì)量對算法的收斂有很大的影響。圖3中的數(shù)據(jù)是經(jīng)過多次獨立實驗后，選取的一組有相近起始時間的數(shù)據(jù)進行的對比。

Figure 3 VNPSO，MMACO，GA convergence curves圖3 VNPSO、MMACO、GA算法收斂曲線

從圖3中可以看出，VNPSO算法由于起始時慣性常量設置較大，因此具有較強的全局搜索能力，故前期搜索收斂速度很快，但由于PSO算法的特性，當?shù)竭_一個極值點后很難脫離，這時VNS策略的引入，讓算法能夠在極值點周圍震蕩，使搜索能夠繼續(xù)進行，讓算法逐漸向最優(yōu)解靠近；對于MMACO算法，由于迭代起始階段信息素較少，故算法收斂速度較慢，但隨著算法的進行，ACO算法良好的尋優(yōu)能力逐漸顯現(xiàn)出來，使算法逐漸向最優(yōu)解靠近；由于GA算法的全局搜索對交叉操作和變異操作依賴較大，故其全局搜索速度較其他兩個算法略顯不足。

對三個算法在有安全約束和無安全約束的條件下分別進行10次獨立實驗。圖4所示為有安全約束的條件下，每個算法在首次取得低于250ms的解時所需要的迭代次數(shù)，其中，VNPSO平均需要223次，MMACO平均需要348次，GA算法平均需要598次。

Figure 4 Iteration times of each algorithm’s makespan first reaching 250ms圖4 首次取得低于250ms的解時所需要的迭代次數(shù)

可以看出，三個算法中VNPSO算法具有較高的收斂速度。10次獨立實驗中，每個算法在經(jīng)過1 000次迭代后所求得的完成時間的平均值如圖5所示。

Figure 5 Average makespan of each algorithms圖5 VNPSO、MMACO、GA算法平均完成時間對比

可以看出，由于本實驗的安全約束較為寬松，故安全約束對平均完成時間的影響并不大。

在此基礎上，本文對200個操作20臺虛擬機的情況做了進一步的實驗。對安全約束做如下定義：從200個操作中隨機抽取20個并把它們的安全需求設置為4，其他操作安全需求設置為2；從20臺虛擬機中隨機抽取4臺并把它們的安全等級設置為4，再隨機抽取4臺并把它們的安全等級設置為3，其余設置為2。實驗取最大風險跨度θ＝2，最大風險概率r＝0.2，即Secu＝（2，0.2），并且式（1）中的風險常數(shù)μ＝3。實驗結果如圖6所示。

Figure 6 Experience with 200operations and 20virtual machines圖6 200個操作20臺虛擬機下的對比

6 結束語

本文對云環(huán)境下工作流任務的資源調(diào)度問題進行了建模，在此基礎上給出了一個安全約束模型，并使用VNPSO算法對問題進行了求解。同時，在Cloudsim仿真平臺下，把VNPSO算法與常用的智能優(yōu)化算法進行了對比。實驗表明，VNPSO算法是有效的，并且由于在全局搜索和局部搜索之間進行了良好的平衡，使得該算法具有很好的尋優(yōu)能力。

［1］ Mell P，Grance T.The NIST definition of cloud computing（draft）［S］.NIST Special Publication 800－145，2011.

［2］ Abrishami S，Naghibzadeh M，Epema D H J.Deadline－constrained workflow scheduling algorithms for infrastructure as a service clouds［J］.Future Generation Computer Systems，2013，29（1）：158－169.

［3］ Liu K，Jin H，Chen J，et al.A compromised－time－cost scheduling algorithm in swindew－c for instance－intensive cost－constrained workflows on a cloud computing platform［J］.International Journal of High Performance Computing Applications，2010，24（4）：445－456.

［4］ Rao J，Wei Y，Gong J，et al.QoS guarantees and service differentiation for dynamic cloud applications［J］.IEEE Transactions on Network and Service Management，2013，10（1）：43－55.

［5］ Wu Z，Liu X，Ni Z，et al.A market－oriented hierarchical scheduling strategy in cloud workflow systems［J］.The Journal of Supercomputing，2013，63（1）：256－293.

［6］ Ergu D，Kou G，Peng Y，et al.The analytic hierarchy process：Task scheduling and resource allocation in cloud computing environment［J］.The Journal of Supercomputing，2013，64（3）：1－14.

［7］ Hamlen K，Kantarcioglu M，Khan L，et al.Security issues for cloud computing［J］.International Journal of Information Security and Privacy（IJISP），2010，4（2）：36－48.

［8］ Song S，Hwang K，Kwok Y K.Risk－resilient heuristics and genetic algorithms for security－assured grid job scheduling［J］.IEEE Transactions on Computers，2006，55（6）：703－719.

［9］ Kennedy J，Eberhart R.Particle swarm optimization［C］∥Proc of IEEE International Conference on Neural Networks，1995：1942－1948.

［10］ Shi Y，Eberhart R C.Parameter selection in particle swarm optimization［C］∥Proc of the 7th International Conference on Evolutionary Programming VII，1998：591－600.

［11］ Hansen P，Mladenovic N.Variable neighborhood search：Principles and applications［J］.European Journal of Operational Research，2001，130（3）：449－467.

［12］ Liu H，Abraham A，Choi O，et al.Variable neighborhood particle swarm optimization for multi－objective flexible jobshop scheduling problems［C］∥Proc of the 6th International Conference on Simulated Evolution and Learning，2006：197－204.

［13］ Garg S K，Buyya R.NetworkCloudSim：Modelling parallel applications in cloud simulations［C］∥Proc of the 4th IEEE International Conference on Utility and Cloud Computing（UCC），2011：105－113.

［14］ Pitakaso R，Almeder C，Doerner K F，et al.A MAX－MIN ant system for unconstrained multi－level lot－sizing problems［J］.Computers ＆Operations Research，2007，34（9）：2533－2552.

［15］ Omara F A，Arafa M M.Genetic algorithms for task scheduling problem［J］.Journal of Parallel and Distributed Computing，2010，70（1）：13－22.