云環(huán)境下基于改進蟻群算法的任務調(diào)度

何長杰，白治江

(上海海事大學 信息工程學院，上海 201306)

0 引 言

云計算是一種商業(yè)計算模型，它將計算任務分配在由大量廉價計算機構成的資源池上，使各種應用系統(tǒng)能夠根據(jù)需要獲取計算力、存儲空間和信息服務[1]。它通過虛擬化技術將軟硬件資源形成一個巨大的資源池[2]，當用戶需要這些資源時，通過某種調(diào)度方式，將資源池中的資源分配給用戶任務，云中的資源就像煤氣、水和電一樣，取用方便，費用低廉。云計算環(huán)境下的資源分配實際上根據(jù)調(diào)度目標將資源分配給云任務[3]，調(diào)度目標不同，采取的分配策略也會不同，如以最優(yōu)跨度、成本最低、服務質(zhì)量、負載均衡等為調(diào)度目標。

目前云計算任務調(diào)度是NP完全問題[4]，不少學者提出一些改進的調(diào)度算法，如Li Kun等[5]提出了LBACO算法，考慮虛擬機的計算能力、帶寬和負載均衡，使得任務執(zhí)行時間少且負載更加均衡。左利云等[6]提出RCMM調(diào)度算法，將任務和資源等級的乘積作為組合值進行Min-Min算法調(diào)度，改進算法負載比原始Min-Min更加均衡。張春艷等[7]提出基于分組多態(tài)蟻群算法，偵察螞蟻負責初始化信息素，搜索螞蟻負責搜索解，使得平均完成時間降低。查英華等[8]提出增強蟻群算法，兼顧任務調(diào)度的最短完成時間和負載均衡，對信息素初始化和局部更新，以及節(jié)點選擇進行改進，減少了算法運行時間，負載更加均衡。王芳等[9]為了解決蟻群算法收斂速度慢和容易陷入局部最優(yōu)解的缺陷，概率選擇時引入混沌擾亂策略，且自適應調(diào)整信息素揮發(fā)因子，實驗表明改進后的算法時間跨度更小。

為了防止蟻群算法陷入局部最優(yōu)解，文中進行了以下改進:對于沒有訪問的路徑不蒸發(fā)信息素，增大其被搜索的概率；獎勵局部最優(yōu)路徑及其近鄰路徑等多條路徑，增大了蟻群搜索空間，防止蟻群算法陷入局部最優(yōu)。

1 云計算任務調(diào)度

云計算調(diào)度模型如圖1所示，分為兩級調(diào)度，分別是云任務調(diào)度和虛擬機調(diào)度。其中云任務調(diào)度表示在理想或者極優(yōu)的資源分配情況下，一個Vm應能以共享模式分配給多個終端用戶的多個任務。虛擬機調(diào)度為Vm尋找合適的Host，再把Vm創(chuàng)建到這個Host上。文中僅僅考慮云任務調(diào)度算法。

圖1 云計算調(diào)度模型

云計算任務調(diào)度問題本質(zhì)是根據(jù)某些調(diào)度目標將n個任務分配到m個虛擬機上，n通常大于m。使得云平臺負載更加均衡，任務完成時間最小，盡可能提高云資源利用率。

任務集合TASK={Task1,Task2,…,Taskn}表示當前任務隊列有n個任務，任務指令長度用百萬指令(million instructions，MI)表示。

虛擬機集合VM={Vm1,Vm2,…,Vmm}表示云中有m個資源節(jié)點。虛擬機處理能力用每秒執(zhí)行的百萬指令數(shù)(million instructions per second，MIPS)表示。

TASK到VM的分配關系可以用分配矩陣X表示為：

(1)

(2)

(3)

其中，TaskLengthj表示任務j的指令長度；VmMipsi表示虛擬機i的處理能力。

2 蟻群算法

蟻群算法是Marco Dorigo在1992年提出的一種元啟發(fā)式仿生算法，模擬蟻群覓食行為過程中發(fā)現(xiàn)最短路徑的現(xiàn)象。螞蟻在覓食中釋放一種稱為信息素(pheromone)的化學物質(zhì)，蟻群之間通過信息素的濃度變化進行信息交流和相互協(xié)作，濃度越高的路徑選擇的概率越大。雖然每個螞蟻個體智能有限，但通過群體的搜索、協(xié)作和涌現(xiàn)現(xiàn)象可以解決單個個體無法解決的問題。這種方法被很多研究者用于求解大多數(shù)NP-Hard優(yōu)化問題，如旅行商(traveling salesman problem，TSP)、二次分配等組合優(yōu)化問題[10]。蟻群算法求解TSP的過程描述如下：

Step1：創(chuàng)建antNum只螞蟻，迭代次數(shù)g，初始化信息素矩陣、可訪問表、禁忌表以及相關參數(shù)。

Step2：隨機將螞蟻分布在n個城市，將初始分配城市節(jié)點加入禁忌表Tabuk，第k只螞蟻從當前城市i選擇下一個城市j。概率選擇公式如下：

(4)

(5)

Step4：antNum只螞蟻都搜索完成各自獲得一條路徑后，對信息素濃度進行更新。信息素更新公式如下：

τij(new)=(1-ρ)τij(old)+Δτij

(6)

(7)

其中，ρ表示信息素的揮發(fā)因子；1-ρ表示信息素的殘留因子。

Step5：若滿足迭代結束條件，則直接打印最優(yōu)路徑結束。否則，重新初始化螞蟻，跳轉(zhuǎn)到Step2。

3 蟻群算法求解云計算任務調(diào)度

將任務到虛擬機的一次分配作為螞蟻搜索對象[8]，用(Taskj,Vmi)表示一個節(jié)點，當所有任務分配給虛擬機之后就形成一系列節(jié)點組成的路徑。

3.1 啟發(fā)式因子設置

(8)

(9)

在TSP問題中，dij表示城市i到城市j的距離，而在云計算任務調(diào)度問題中，dij表示任務j分配給虛擬機i后的完成時間，包括分配之前虛擬機i已經(jīng)執(zhí)行的時間和分配之后任務j在虛擬機i的執(zhí)行時間。TotalLengthi表示已經(jīng)分配給虛擬機i的任務指令總長度[11]。etij表示任務j分配給虛擬機i的執(zhí)行時間，由式3計算可得。

分配完成后，虛擬機i的任務指令總長度需要加上當前分配到的任務j的指令長度，計算公式如下：

TotalLengthi=TotalLengthi+TaskLengthj

(10)

3.2 改進信息素更新規(guī)則

經(jīng)典蟻群算法的信息素更新規(guī)則會對全部路徑進行信息素揮發(fā)，對于螞蟻未經(jīng)過的路徑，該路徑的信息素由于揮發(fā)越來越少，趨近于零，導致之后螞蟻幾乎不會選擇該路徑，降低了蟻群算法的搜索空間[12]。因此文中對信息素更新規(guī)則進行改進，迭代過程中，對于沒有訪問的路徑不再揮發(fā)信息素。信息素更新公式如下：

τij(new)=

(11)

其中，Δτij表示一次迭代過程中根據(jù)各個螞蟻搜索的路徑以及路徑的質(zhì)量進行信息素更新。Δτij=0表明該路徑?jīng)]有信息素更新，亦沒有螞蟻訪問，沒有訪問的路徑不再揮發(fā)信息素。

3.3 定義問題解

所有螞蟻遍歷完成獲得分配方案后，虛擬機i總的執(zhí)行時間即負載定義為：

(12)

TSP問題中將路徑的長度作為解，路徑越短，獲得的解越好。在云計算任務調(diào)度問題中，由于各個虛擬機并行執(zhí)行，更多地考慮所有任務執(zhí)行完成的最大時間[13]，因此t次迭代時第k只螞蟻獲得的解定義如下：

Lk(t)=max{Li}

(13)

迭代過程中最優(yōu)解定義為L*，表示如下：

(14)

3.4 最優(yōu)解獎勵改進

基于精英的蟻群算法對最優(yōu)路徑進行額外獎勵，雖然能夠加快收斂速度，卻容易陷入局部最優(yōu)解，這是由于精英蟻群算法僅僅獎勵局部最優(yōu)解路徑這一條路徑，導致這一條路徑上的信息素偏高。云計算環(huán)境中許多虛擬機的處理能力相當，因此這些虛擬機之間處理相同的任務集所需的執(zhí)行時間也相當。文中對最優(yōu)解路徑上的Vm*搜索與之處理能力相當?shù)奶摂M機，交換兩個虛擬機上的任務集得到新的路徑，此時的路徑定義為近鄰路徑，對最優(yōu)路徑和近鄰路徑多條路徑進行信息素獎勵，有利于發(fā)現(xiàn)近鄰解，擴大搜索范圍。同時給予其他路徑很少的獎勵，防止最優(yōu)解的路徑與其他路徑的信息素差異太大，陷入局部最優(yōu)。獎勵公式如下：

(15)

其中，VmMipsi虛擬機i的處理能力；VmMips*是最優(yōu)解L*中Taskj分配到的Vm*的處理能力；VmMaxMips是所有虛擬機中處理能力的最大值。

4 實驗及結果分析

文中選擇墨爾本大學Gridbus項目組提出的云計算仿真軟件Cloudsim[14]3.0進行仿真實驗，構造螞蟻類Ant和蟻群類ACO，重載DatacenterBroker類。云仿真器的參數(shù)設置如表1所示。

表1 CloudSim中云環(huán)境的參數(shù)設置

為了保證實驗的準確性，將任務數(shù)據(jù)和虛擬機數(shù)據(jù)保存在文件中，進行實驗時從文件中讀取。蟻群算法α值越大，搜索易過早陷入局部最優(yōu)，β值越大越接近貪婪規(guī)則，α一般取值為1，β一般取值為5。蟻群算法參數(shù)設置如表2所示。

表2 蟻群參數(shù)設置

定義云中資源不平衡程度(degree of imbalance，DI)：

(16)

其中，Lmax是任務分配完成之后集群中最大的虛擬機負載；Lmin是集群中最小的虛擬機負載；Lavg是虛擬機平均負載。DI值越小，集群中的負載就越均衡。

將文中算法和精英蟻群算法進行實驗對比。由于蟻群算法的不穩(wěn)定性，記錄十次實驗求平均值分別對最大完成時間和不平衡程度兩個維度進行比較。

圖2 最大完成時間

圖2為文中算法和ACO算法在不同任務數(shù)下的最大完成時間比較?？梢钥闯觯闹兴惴ū華CO算法求得的最大完成時間更小，這是由于新算法對沒有訪問的路徑不再揮發(fā)其信息素，增大其被訪問的概率，其次獎勵了最優(yōu)路徑及其近鄰路徑等多條路徑，同時減小了最優(yōu)路徑與其他路徑信息素的差異，擴大了搜索空間，防止蟻群算法陷入局部最優(yōu)解。

圖3為文中算法和ACO算法在不同任務數(shù)下的不平衡程度比較?？梢钥闯?，文中算法不平衡程度普遍優(yōu)于ACO算法，表明新算法更加合理有效地使用資源。隨著任務數(shù)的增加，云中虛擬機負載不平衡程度減小，這是由于任務之間的指令長度相對差異減小，使得虛擬機上的負載差異也減小，因此不平衡程度也隨之減小，且隨著任務增加不平衡程度下降趨于平緩。

圖3 不平衡程度

5 結束語

元啟發(fā)式算法相比較啟發(fā)式算法，雖然求解精度高，但運行時間長?；诰⒉呗缘南伻核惴軌蚣涌焓諗克俣?，卻容易陷入局部最優(yōu)。文中對精英蟻群算法進行了改進，首先對迭代過程中沒有訪問的路徑不蒸發(fā)信息素，防止該路徑信息素越減越少，增大其被訪問的概率，擴大蟻群的搜索空間。其次在最優(yōu)路徑獎勵時，對最優(yōu)路徑和近鄰路徑等多條路徑進行獎勵，增加了獎勵路徑的數(shù)目，擴大了蟻群搜索空間，同時降低最優(yōu)路徑和其他路徑的信息素差值，既增強了最優(yōu)路徑又防止蟻群算法陷入局部最優(yōu)解。實驗證明，該算法在最大完成時間和不平衡程度下能求得更優(yōu)的解，提高了云資源利用率。