任金霞， 黃藝培， 鐘小康

（江西理工大學(xué)電氣工程與自動(dòng)化學(xué)院，江西 贛州341000）

0 引 言

隨著信息化時(shí)代的到來，云計(jì)算[1—3]的商業(yè)化越來越火熱.它是集合大量的計(jì)算儲(chǔ)存等資源具有信息化時(shí)代特征的新型計(jì)算方式，是信息化時(shí)代以來的又一次巨變.它使用先進(jìn)的虛擬化技術(shù)抽象計(jì)算儲(chǔ)存等物理資源并通過專門軟件實(shí)現(xiàn)自動(dòng)管理，用戶通過租賃的方式提交業(yè)務(wù)申請(qǐng)能夠按照業(yè)務(wù)的需要獲得各類服務(wù).云服務(wù)提供商根據(jù)用戶提交的任務(wù)申請(qǐng)通過調(diào)度中心為其分配資源，然而，在云計(jì)算環(huán)境下，復(fù)雜的云計(jì)算資源及云任務(wù)的多樣性使得云任務(wù)的調(diào)度成為困擾云服務(wù)提供商的一個(gè)難題.

由于在復(fù)雜的云計(jì)算環(huán)境中，云任務(wù)的調(diào)度本身是一個(gè)NP難問題，而各種智能算法被普遍認(rèn)為是解決NP難問題[4]的一種較先進(jìn)的算法，能夠在一定條件下得到較優(yōu)的解決方案，甚至最佳解決方案.因此，很多研究學(xué)者使用啟發(fā)式智能算法來處理云任務(wù)調(diào)度的難題，繼而出現(xiàn)了各種基于改進(jìn)智能算法（遺傳算法[5]、匈牙利算法[6]、蟻群算法[7]、粒子群算法[8,9]）的任務(wù)調(diào)度策略，當(dāng)然，也有經(jīng)典的方法，像基于貪心思想的調(diào)度策略[10]等.不管何種云任務(wù)調(diào)度策略,在云計(jì)算商品化的過程中滿足用戶要求盡可能快地完成任務(wù)的同時(shí)還應(yīng)兼顧云平臺(tái)的效率，均衡虛擬機(jī)的負(fù)載來提高資源的利用率.因此，文中針對(duì)云任務(wù)的調(diào)度問題提出一種改進(jìn)的遺傳算法，同時(shí)對(duì)任務(wù)執(zhí)行的完成時(shí)間和虛擬機(jī)負(fù)載的均衡情況進(jìn)行優(yōu)化，以達(dá)到提高系統(tǒng)吞吐量和資源利用率的目的.

1 問題描述

云環(huán)境下，通過虛擬化技術(shù)從大批物理資源中抽象出不同性能的虛擬機(jī)；云平臺(tái)出于各種因素的考慮，針對(duì)特定的任務(wù)集將若干臺(tái)虛擬機(jī)集合到一起構(gòu)造出一個(gè)虛擬資源集；再通過云平臺(tái)特有調(diào)度策略把任務(wù)集中的所有待處理的任務(wù)提交到該虛擬資源集中的虛擬計(jì)算節(jié)點(diǎn)上處理.這個(gè)過程對(duì)每個(gè)用戶來說都感覺是自己獨(dú)自占用一臺(tái)計(jì)算機(jī)，對(duì)云服務(wù)提供商來說為了充分發(fā)揮云平臺(tái)的性能，按照哪一種調(diào)度策略來分配任務(wù)是至關(guān)重要的.

為使仿真研究工作更為方便，對(duì)具有復(fù)雜性和多變性的云計(jì)算提出如下假設(shè)：

1）忽略帶寬、數(shù)據(jù)傳輸?shù)葘?duì)任務(wù)執(zhí)行時(shí)間的影響，假定一個(gè)任務(wù)所需的執(zhí)行時(shí)間等于該任務(wù)的長(zhǎng)度除以運(yùn)行該任務(wù)的虛擬機(jī)的執(zhí)行速度.

2）云平臺(tái)是每隔一段時(shí)間形成一個(gè)任務(wù)集并對(duì)其進(jìn)行資源分配，每個(gè)任務(wù)是相互獨(dú)立的，且多個(gè)任務(wù)分配在同一臺(tái)虛擬機(jī)時(shí)，按先進(jìn)先出原則執(zhí)行任務(wù).

3）云任務(wù)和虛擬機(jī)資源的表示如下所述.

T={t0,t1,…,tn-1}表示云計(jì)算的任務(wù)集；其中n為云任務(wù)的數(shù)量.ti={tid,tlength,tdata,trres}表示第i個(gè)任務(wù)的屬性，tid表示任務(wù)的ID，tlength表示任務(wù)的總長(zhǎng)度，tdata表示任務(wù)處理所需的相關(guān)數(shù)據(jù)，trres表示任務(wù)希望獲得的資源屬性情況，主要包括資源的計(jì)算能力、內(nèi)存、帶寬，由此可量化任務(wù)的QoS性能需求.

V={v0,v1,…,vm-1}表示云平臺(tái)為相應(yīng)任務(wù)集提供的虛擬機(jī)集合，即虛擬資源集；其中m為虛擬機(jī)的數(shù)量.vi={vid,vmip,vram,vbw}表示第i臺(tái)虛擬機(jī)的性能，vid表示虛擬機(jī)的序號(hào)，vmip表示虛擬機(jī)的計(jì)算能力，vram表示虛擬機(jī)的內(nèi)存，vbw表示虛擬機(jī)的帶寬.在同一臺(tái)虛擬機(jī)上執(zhí)行的任務(wù)遵循先進(jìn)先出原則.任務(wù)集中的所有任務(wù)執(zhí)行完后，云平臺(tái)收回其對(duì)應(yīng)的虛擬資源集中的虛擬機(jī)以便下一次的調(diào)度.

2 云任務(wù)調(diào)度改進(jìn)算法

遺傳算法是由美國J.Holland教授借鑒生物界進(jìn)化規(guī)律在1975年提出的一類隨機(jī)搜索算法；通過選擇、交叉、變異來實(shí)現(xiàn)尋優(yōu)，具備較強(qiáng)的全局搜索能力、前期搜索效率高，但局部搜索能力較差、后期對(duì)可行解的搜索速度非常慢、容易產(chǎn)生過早收斂的現(xiàn)象.文中主要對(duì)遺傳算法的變異操作及變異算子進(jìn)行改進(jìn)加快算法收斂速度，搜索最優(yōu)解.

2.1 云任務(wù)調(diào)度改進(jìn)算法的具體描述

采用雙精英保留策略對(duì)遺傳算法進(jìn)行比例選擇操作，引入虛擬機(jī)相對(duì)適應(yīng)度，改進(jìn)遺傳算法的變異操作加強(qiáng)全局搜索能力及加快搜索速度，利用公式（5）評(píng)價(jià)個(gè)體的優(yōu)劣，對(duì)整個(gè)解空間進(jìn)行迭代搜索，直到滿足迭代終止條件找到適應(yīng)度值最大的個(gè)體，輸出最優(yōu)解.算法流程圖如圖1所示.

圖1 算法流程

2.2 編碼方式

將遺傳算法傳統(tǒng)的0，1編碼方式改為實(shí)數(shù)直接編碼方式；每個(gè)個(gè)體的染色體有多少個(gè)基因取決于任務(wù)集的任務(wù)數(shù)量，每個(gè)基因的基因值就表示該虛擬資源集中虛擬機(jī)的序號(hào).在種群中有若干個(gè)個(gè)體，每一個(gè)個(gè)體對(duì)應(yīng)著一個(gè)任務(wù)集的分配方案，例如：假定虛擬機(jī)數(shù)量為4臺(tái)，任務(wù)數(shù)為8個(gè)，則其個(gè)體的基因個(gè)數(shù)為8個(gè)，基因值為4臺(tái)虛擬機(jī)所對(duì)應(yīng)序號(hào)的其中一個(gè)；若有編碼為（2，0，3，3，1，2，2，1）的個(gè)體，則解碼得：0號(hào)虛擬機(jī)執(zhí)行任務(wù)1，1號(hào)虛擬機(jī)執(zhí)行任務(wù)4和7，2號(hào)虛擬機(jī)執(zhí)行任務(wù)0、5和6，3號(hào)虛擬機(jī)執(zhí)行任務(wù)2和3.

2.3 適應(yīng)度函數(shù)

對(duì)某個(gè)個(gè)體的染色體進(jìn)行解碼可得到一個(gè)任務(wù)集的分配方案，每臺(tái)虛擬機(jī)上執(zhí)行的任務(wù)各不相同，設(shè)第j臺(tái)虛擬機(jī)上分配了w個(gè)任務(wù)，則第j臺(tái)虛擬機(jī)完成其分配到的任務(wù)所用的時(shí)間F（j）為：

其中表示第j臺(tái)虛擬機(jī)執(zhí)行分配在該機(jī)上的第i個(gè)任務(wù)所用的時(shí)間.

由公式（1）可得出：所有任務(wù)總的執(zhí)行完成時(shí)間TF為：

其中m表示虛擬機(jī)的數(shù)量.

TF越小，用戶的評(píng)價(jià)越好.同時(shí)，對(duì)云服務(wù)提供商來說，虛擬機(jī)資源的負(fù)載均衡性也非常重要，文中按文獻(xiàn)[9]中所提的方法用虛擬機(jī)完成其所分配到的任務(wù)所用的時(shí)間F（j）來表示虛擬機(jī)j的負(fù)載量，則虛擬資源集的平均負(fù)載量AL和負(fù)載均衡標(biāo)準(zhǔn)差BL分別為：

其中 F（j）可由公式（1）計(jì)算得到；m 表示虛擬機(jī)的數(shù)量.由此可知，BL理想值為0，BL越小，各虛擬機(jī)的負(fù)載量越接近，調(diào)度策略越合理，資源利用率就越高，同時(shí)公式（2）中的所有任務(wù)總的執(zhí)行完成時(shí)間TF也會(huì)越小.

基于以上分析可得出用來評(píng)價(jià)個(gè)體優(yōu)劣的適應(yīng)度函數(shù)為：

其中 BL 由公式（4）求得，TF 由公式（2）求得，適應(yīng)度函數(shù)值越大說明個(gè)體越優(yōu)秀.

2.4 改進(jìn)變異操作

設(shè)計(jì)自適應(yīng)變異算子，根據(jù)定義的虛擬機(jī)相對(duì)適應(yīng)度以輪盤賭選擇的方式來進(jìn)行變異操作.

2.4.1 虛擬機(jī)相對(duì)適應(yīng)度

在虛擬資源集中有m臺(tái)可用的虛擬機(jī)；它們之間的配置（參數(shù)）都不可能完全一樣，而虛擬機(jī)的執(zhí)行速度是影響虛擬機(jī)處理任務(wù)最主要的性能.

定義1：第k臺(tái)虛擬機(jī)相對(duì)適應(yīng)度VRFk為：

其中表示虛擬資源集中第k臺(tái)虛擬機(jī)的執(zhí)行速度,TVmips表示虛擬資源集中全部虛擬機(jī)的執(zhí)行速度之和,m表示虛擬機(jī)的總數(shù).

由公式（6）可知：執(zhí)行速度快的虛擬機(jī)其相對(duì)適應(yīng)度也要大，且所有虛擬機(jī)相對(duì)適應(yīng)度之和等于1.

2.4.2 改進(jìn)后變異操作過程

如果變異算子設(shè)置的較大，變異操作就可以看成是對(duì)局部可行解進(jìn)行隨機(jī)搜索更優(yōu)解的一個(gè)過程，這使得遺傳算法的整體性能和全局搜索能力在迭代開始都會(huì)嚴(yán)重退化；如果設(shè)置的太小，則在迭代后期會(huì)失去局部搜索能力和群體的多樣性.因此，對(duì)于變異算子的設(shè)定應(yīng)根據(jù)需要隨迭代過程自適應(yīng)，變異算子mutateRate為：

其中i為迭代次數(shù).

設(shè)定好變異算子后對(duì)變異操作進(jìn)行改進(jìn)：要對(duì)哪一個(gè)基因進(jìn)行變異操作采取隨機(jī)選擇的方式選定，以虛擬機(jī)相對(duì)適應(yīng)度VRF為基礎(chǔ)構(gòu)建輪盤，采用輪盤賭方式選擇；執(zhí)行變異操作后基因值就變成了輪盤賭選定的VRF所對(duì)應(yīng)的虛擬機(jī)序號(hào).VRF值越大虛擬機(jī)的性能就越好，被輪盤賭選中的概率也越大.例如：假定VRF0=0.1,VRF1=0.2,VRF2=0.3,VRF3=0.4，對(duì)虛擬機(jī)4臺(tái)任務(wù)數(shù)6個(gè)，染色體編碼為（2，0，3，1，2，1）的個(gè)體進(jìn)行變異；若隨機(jī)選擇要變異的基因?yàn)榈?個(gè)，輪盤賭選到VRF3；則變異后個(gè)體染色體編碼為（3，0，3，1，2，1）.

3 仿真實(shí)驗(yàn)與分析

采用澳大利亞墨爾本大學(xué)Rajkumar Buyya教授領(lǐng)導(dǎo)團(tuán)隊(duì)開發(fā)的云仿真器CloudSim3.0[11]來進(jìn)行仿真實(shí)驗(yàn).用Java編程語言在MyEclipse10.7軟件下對(duì)CloudSim平臺(tái)的DatacenterBroker類進(jìn)行擴(kuò)展，寫入一個(gè)新方法：bindCloudletsToVms IGA()，調(diào)用該方法來實(shí)現(xiàn)根據(jù)文中算法定義的云任務(wù)調(diào)度策略的模擬，以及進(jìn)行相關(guān)測(cè)試和實(shí)驗(yàn).在云任務(wù)調(diào)度仿真實(shí)驗(yàn)中，文中算法（Improved Genetic Algorithm，IGA）與傳統(tǒng)遺傳算法（Genetic Algorithm，GA）及經(jīng)典的Min-Min算法在任務(wù)完成時(shí)間和負(fù)載均衡情況兩個(gè)方面進(jìn)行比較，驗(yàn)證文中算法的性能.

通過隨機(jī)發(fā)生器隨機(jī)產(chǎn)生任務(wù)集和虛擬資源集，任務(wù)長(zhǎng)度在 [1000,6000)區(qū)間，虛擬機(jī)執(zhí)行速度在 [100,500)區(qū)間.IGA算法的種群規(guī)模size=80，最大迭代次數(shù)L=500，交叉算子crossoverRate=0.75.GA算法的變異算子mutateRate=0.1，其余參數(shù)與IGA算法一致.

實(shí)驗(yàn)一：虛擬機(jī)的數(shù)量為100臺(tái)不變，任務(wù)的數(shù)量為500個(gè)不變，重復(fù)10次實(shí)驗(yàn)取平均值，得到如圖2所示隨算法迭代次數(shù)的增加IGA算法和GA算法在任務(wù)完成時(shí)間方面收斂情況的對(duì)比結(jié)果.

圖2 IGA算法和GA算法的收斂情況對(duì)比

結(jié)果分析：從圖2中可以看出，與GA算法相比改進(jìn)后的IGA算法能夠更快地達(dá)到收斂效果，且任務(wù)完成時(shí)間的收斂值降低了約10%.

實(shí)驗(yàn)二：當(dāng)虛擬機(jī)數(shù)量為100臺(tái)不變，任務(wù)的數(shù)量從100個(gè)開始，每次增加100個(gè)，一直到500個(gè)時(shí).重復(fù)10次實(shí)驗(yàn)取平均值，三種算法任務(wù)完成時(shí)間比較如圖3所示，虛擬機(jī)負(fù)載均衡標(biāo)準(zhǔn)差的比較如圖4所示.

結(jié)果分析：當(dāng)虛擬機(jī)數(shù)量一定時(shí)，在任務(wù)完成時(shí)間方面從圖3中可知，文中算法效果最好，并且隨著任務(wù)數(shù)的增加優(yōu)勢(shì)慢慢加大.在負(fù)載均衡標(biāo)準(zhǔn)差方面，從圖4中可以看出，文中算法取得的效果是最好，隨著任務(wù)數(shù)的增加文中算法都能夠穩(wěn)定在10以下，GA算法基本在30以上，且很不穩(wěn)定，而Min-Min算法則在25左右.由此可知，當(dāng)虛擬機(jī)數(shù)量不變而任務(wù)數(shù)不斷增加時(shí)，文中算法在任務(wù)完成時(shí)間和負(fù)載均衡標(biāo)準(zhǔn)差上都比另外兩種算法取得更好的效果.

圖3 三種算法任務(wù)完成時(shí)間的比較

圖4 三種算法虛擬機(jī)負(fù)載均衡標(biāo)準(zhǔn)差比較

實(shí)驗(yàn)三：當(dāng)任務(wù)數(shù)為500個(gè)不變，虛擬機(jī)的數(shù)量從50臺(tái)開始，每次增加50臺(tái)，一直到250臺(tái)時(shí).同樣反復(fù)10次實(shí)驗(yàn)取其平均值，三種算法任務(wù)完成時(shí)間比較如圖5所示，虛擬機(jī)負(fù)載均衡標(biāo)準(zhǔn)差的比較如圖6所示.

圖5 三種算法任務(wù)完成時(shí)間的比較

圖6 三種算法虛擬機(jī)負(fù)載均衡標(biāo)準(zhǔn)差的比較

結(jié)果分析：從圖5和圖6中可以看出，當(dāng)任務(wù)數(shù)一定時(shí)，文中算法的任務(wù)完成時(shí)間一直保持著一定的優(yōu)勢(shì)，在負(fù)載均衡標(biāo)準(zhǔn)差方面，一開始就保持著一定優(yōu)勢(shì)，隨著虛擬機(jī)數(shù)量的不斷增加，文中算法一直穩(wěn)定在5附近，而GA算法為25左右，Min-Min算法在20左右，且都不穩(wěn)定.因此，當(dāng)存在很多云任務(wù)時(shí)，文中算法會(huì)取得更好的效果，這正是實(shí)際云環(huán)境的特點(diǎn).

4 結(jié) 論

文章針對(duì)云環(huán)境下任務(wù)調(diào)度問題，以任務(wù)完成時(shí)間和虛擬機(jī)負(fù)載均衡為目標(biāo)，提出了一種改進(jìn)遺傳算法的云任務(wù)調(diào)度改進(jìn)算法.通過虛擬機(jī)執(zhí)行速度的不同，引入虛擬機(jī)相對(duì)適應(yīng)度的概念，促使變異操作直接朝更優(yōu)的方向發(fā)展來優(yōu)化結(jié)果.通過仿真實(shí)驗(yàn)證明該算法比改進(jìn)前及Min-Min算法都有更好的效果，應(yīng)用于云平臺(tái)中是可行的.文中算法優(yōu)化目標(biāo)主要考慮的是影響系統(tǒng)吞吐量的任務(wù)集完成時(shí)間，并沒有考慮到與用戶體驗(yàn)密切相關(guān)的QoS需求.服務(wù)質(zhì)量QoS是衡量用戶對(duì)所使用云服務(wù)滿意程度的標(biāo)準(zhǔn)，含有用戶時(shí)間需求、性能需求、費(fèi)用需求和能耗需求等，不同用戶的需求各不相同.后續(xù)將對(duì)如何保證系統(tǒng)吞吐量的同時(shí)又能夠最大程度的滿足用戶QoS需求進(jìn)行研究.

[1]Armbrust M,Fox A,Griffith R,et al.A view of cloud computing[J].Communications of the ACM,2010,53(4):50-58.

[2]Endo P T,Rodrigues M,Goncalves G E,et al.High availability in clouds:systematic review and research challenges[J].Journal of Cloud Computing,2016,5(1):16.

[3]劉鵬.云計(jì)算（第二版）[M].北京:電子工業(yè)出版社，2011.

[4]Kiselyov O.Scheduling algorithms and NP-complete problems[J].Dr Dobbs Journal,1997,22(2):107-109.

[5]李建峰，彭艦.云計(jì)算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用，2011，31(1):182-187.

[6]任金霞，何富江.快速降階匈牙利算法的云計(jì)算任務(wù)分配模型[J].江西理工大學(xué)學(xué)報(bào)，2014，35(3):63-67.

[7]張春艷，劉清林，孟珂.基于蟻群優(yōu)化算法的云計(jì)算任務(wù)分配[J].計(jì)算機(jī)應(yīng)用，2012，32(5):1418-1420.

[8]王波，張曉磊.基于粒子群遺傳算法的云計(jì)算任務(wù)調(diào)度研究[J].計(jì)算機(jī)工程與應(yīng)用，2015，51(6):84-88.

[9]馮小靖，潘郁.云計(jì)算環(huán)境下的DPSO資源負(fù)載均衡算法[J].計(jì)算機(jī)工程與應(yīng)用，2013，49(6):105-108.

[10]崔雪嬌，曾成，徐占然，等.基于貪心算法的云計(jì)算資源調(diào)度策略[J].微電子學(xué)與計(jì)算機(jī)，2016，33(6):41-44.

[11]Rodrigo N.Calheiros,Rajiv Ranjan,Anton Beloglazov,et al.CloudSim:a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J].Software:Practice and Experience,2011,41:23-50.