馬俊波，殷建平

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

1 引言

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

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

2 相關(guān)工作

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

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

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

3 系統(tǒng)模型

3.1 符號(hào)與說(shuō)明

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

（1）計(jì)算資源。

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

（2）通信矩陣。

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

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

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

（4）工作流約束。

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

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

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

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

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

3.2 安全約束模型

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

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

常見(jiàn)的安全約束模型有三類(lèi)［8］：

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

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

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

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

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

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

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

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

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

3.3 問(wèn)題定義

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

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

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

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

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

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

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

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

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

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

那么帶有安全約束的資源調(diào)度問(wèn)題可定義為：在滿(mǎn)足約束F、Comu、Secu的條件下，把任務(wù)T部署到資源R上，并達(dá)到優(yōu)化目標(biāo)f?？尚问交硎緸椤牵剑═，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年提出的，是通過(guò)對(duì)鳥(niǎo)群捕食行為的研究，抽象出的一種基于迭代的優(yōu)化算法。算法首先隨機(jī)地初始化一個(gè)包含一定數(shù)量粒子的種群，種群中的每個(gè)粒子都代表一個(gè)潛在的解，粒子在問(wèn)題的解空間中移動(dòng)以找到最優(yōu)或足夠好的解。

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

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

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

并且

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

PSO算法流程如圖2所示。

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

PSO算法的終止條件通常有三類(lèi)［9］：

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

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

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

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

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

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

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

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

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

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

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

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

算法 VNPSO

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

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

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

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

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

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

步驟5t＝t＋1；

步驟6 計(jì)算每一個(gè)粒子的適應(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)度問(wèn)題中使用PSO算法，最關(guān)鍵的是要把調(diào)度問(wèn)題的解映射到粒子空間中。

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

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

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

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

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

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

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

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

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

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

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

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

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

本文中與VNPSO算法做對(duì)比的是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

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

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

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

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

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

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

Figure 3 VNPSO，MMACO，GA convergence curves圖3 VNPSO、MMACO、GA算法收斂曲線(xiàn)

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

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

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

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

Figure 5 Average makespan of each algorithms圖5 VNPSO、MMACO、GA算法平均完成時(shí)間對(duì)比

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

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

Figure 6 Experience with 200operations and 20virtual machines圖6 200個(gè)操作20臺(tái)虛擬機(jī)下的對(duì)比

6 結(jié)束語(yǔ)

本文對(duì)云環(huán)境下工作流任務(wù)的資源調(diào)度問(wèn)題進(jìn)行了建模，在此基礎(chǔ)上給出了一個(gè)安全約束模型，并使用VNPSO算法對(duì)問(wèn)題進(jìn)行了求解。同時(shí)，在Cloudsim仿真平臺(tái)下，把VNPSO算法與常用的智能優(yōu)化算法進(jìn)行了對(duì)比。實(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.