馬俊波，殷建平

（國防科學(xué)技術(shù)大學(xué)計算機(jī)學(xué)院，湖南 長沙 410073）

1 引言

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

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

2 相關(guān)工作

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

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

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

3 系統(tǒng)模型

3.1 符號與說明

本文使用的相關(guān)術(shù)語和符號定義如下：

（1）計算資源。

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

（2）通信矩陣。

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

（3）計算任務(wù)和原子操作。

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

（4）工作流約束。

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

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

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

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

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

3.2 安全約束模型

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

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

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

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

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

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

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

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

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

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

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

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

3.3 問題定義

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

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

（2）虛擬機(jī)每次只能運(yùn)行一個操作，其余操作進(jìn)入排隊隊列。

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

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

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

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

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

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

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

那么帶有安全約束的資源調(diào)度問題可定義為：在滿足約束F、Comu、Secu的條件下，把任務(wù)T部署到資源R上，并達(dá)到優(yōu)化目標(biāo)f。可形式化表示為∏＝（T，R，F(xiàn)，Comu，Secu，f）。

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

4.1 標(biāo)準(zhǔn)的粒子群優(yōu)化算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法 VNPSO

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

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

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

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

步驟3 把結(jié)果沒有提高的迭代標(biāo)志變量置0，flag＝0；

步驟4 while沒有達(dá)到結(jié)束條件時do：

步驟5t＝t＋1；

步驟6 計算每一個粒子的適應(yīng)度值；

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

步驟8 ifgbest得到改進(jìn)thenflag＝0；

步驟9 elseflag＝flag＋1；

步驟10 fori＝1toN

步驟11 更新pbesti為其歷史最佳位置和當(dāng)

前位置中使適應(yīng)度最小的位置；

步驟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算法，最關(guān)鍵的是要把調(diào)度問題的解映射到粒子空間中。

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

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

每一個位置矩陣表示一個潛在的調(diào)度結(jié)果，而這個結(jié)果直接應(yīng)用的話有可能會與工作流約束沖突，因此在算法開始前，對工作流約束中的操作進(jìn)行拓?fù)渑判?，保證前驅(qū)操作都排在后繼操作之前，并且在計算適應(yīng)度函數(shù)時引入等待機(jī)制，以滿足工作流約束的要求。如前文所示的工作流矩陣就是按拓?fù)渑判蚝蟮牟僮魃傻摹?/p>

5 實(shí)驗(yàn)結(jié)果與分析

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

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

任務(wù)中每個操作的長度隨機(jī)生成，取值范圍為［100，500］，滿足均勻分布，本次實(shí)驗(yàn)中操作長度取值如下，單位是MI：

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

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

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

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

其中，ωmax、ωmin分別為ω的最大值和最小值，iter和itermax分別為當(dāng)前迭代次數(shù)和最大迭代次數(shù)。本文的實(shí)驗(yàn)取ωmax＝0.9，ωmin＝0.4，即隨著迭代的進(jìn)行，ω由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算法的相關(guān)參數(shù)為：蟻群規(guī)模為30，信息啟發(fā)式因子和期望啟發(fā)式因子均取1，信息素?fù)]發(fā)系數(shù)取0.2，最佳解概率取0.005。GA算法的相關(guān)參數(shù)為：種群規(guī)模為30，交叉算子取0.8，變異算子取0.1

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

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

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

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

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

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

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

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

對三個算法在有安全約束和無安全約束的條件下分別進(jìn)行10次獨(dú)立實(shí)驗(yàn)。圖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次獨(dú)立實(shí)驗(yàn)中，每個算法在經(jīng)過1 000次迭代后所求得的完成時間的平均值如圖5所示。

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

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

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

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

6 結(jié)束語

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