基于遺傳算法的云任務(wù)調(diào)度改進算法

任金霞， 黃藝培， 鐘小康

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

0 引 言

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

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

1 問題描述

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

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

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

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

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

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

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

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

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

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

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

圖1 算法流程

2.2 編碼方式

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

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

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

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

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

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

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

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

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

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

2.4 改進變異操作

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

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

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

定義1：第k臺虛擬機相對適應(yīng)度VRFk為：

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

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

2.4.2 改進后變異操作過程

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

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

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

3 仿真實驗與分析

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

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

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

圖2 IGA算法和GA算法的收斂情況對比

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

實驗二：當虛擬機數(shù)量為100臺不變，任務(wù)的數(shù)量從100個開始，每次增加100個，一直到500個時.重復(fù)10次實驗取平均值，三種算法任務(wù)完成時間比較如圖3所示，虛擬機負載均衡標準差的比較如圖4所示.

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

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

圖4 三種算法虛擬機負載均衡標準差比較

實驗三：當任務(wù)數(shù)為500個不變，虛擬機的數(shù)量從50臺開始，每次增加50臺，一直到250臺時.同樣反復(fù)10次實驗取其平均值，三種算法任務(wù)完成時間比較如圖5所示，虛擬機負載均衡標準差的比較如圖6所示.

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

圖6 三種算法虛擬機負載均衡標準差的比較

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

4 結(jié) 論

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

[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]劉鵬.云計算（第二版）[M].北京:電子工業(yè)出版社，2011.

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

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

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

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

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

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

[10]崔雪嬌，曾成，徐占然，等.基于貪心算法的云計算資源調(diào)度策略[J].微電子學(xué)與計算機，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.