何長(zhǎng)杰，白治江

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

0 引 言

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

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

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

1 云計(jì)算任務(wù)調(diào)度

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

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

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

任務(wù)集合TASK={Task1,Task2,…,Taskn}表示當(dāng)前任務(wù)隊(duì)列有n個(gè)任務(wù)，任務(wù)指令長(zhǎng)度用百萬(wàn)指令(million instructions，MI)表示。

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

TASK到VM的分配關(guān)系可以用分配矩陣X表示為：

(1)

(2)

(3)

其中，TaskLengthj表示任務(wù)j的指令長(zhǎng)度；VmMipsi表示虛擬機(jī)i的處理能力。

2 蟻群算法

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

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

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

(4)

(5)

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

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

(6)

(7)

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

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

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

將任務(wù)到虛擬機(jī)的一次分配作為螞蟻搜索對(duì)象[8]，用(Taskj,Vmi)表示一個(gè)節(jié)點(diǎn)，當(dāng)所有任務(wù)分配給虛擬機(jī)之后就形成一系列節(jié)點(diǎn)組成的路徑。

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

(8)

(9)

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

分配完成后，虛擬機(jī)i的任務(wù)指令總長(zhǎng)度需要加上當(dāng)前分配到的任務(wù)j的指令長(zhǎng)度，計(jì)算公式如下：

TotalLengthi=TotalLengthi+TaskLengthj

(10)

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

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

τij(new)=

(11)

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

3.3 定義問(wèn)題解

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

(12)

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

Lk(t)=max{Li}

(13)

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

(14)

3.4 最優(yōu)解獎(jiǎng)勵(lì)改進(jìn)

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

(15)

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

4 實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

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

(16)

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

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

圖2 最大完成時(shí)間

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

圖3為文中算法和ACO算法在不同任務(wù)數(shù)下的不平衡程度比較?？梢钥闯觯闹兴惴ú黄胶獬潭绕毡閮?yōu)于ACO算法，表明新算法更加合理有效地使用資源。隨著任務(wù)數(shù)的增加，云中虛擬機(jī)負(fù)載不平衡程度減小，這是由于任務(wù)之間的指令長(zhǎng)度相對(duì)差異減小，使得虛擬機(jī)上的負(fù)載差異也減小，因此不平衡程度也隨之減小，且隨著任務(wù)增加不平衡程度下降趨于平緩。

圖3 不平衡程度

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

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