基于交換改進粒子群算法的云計算任務(wù)調(diào)度

陳俊仁 郭一晶

(廈門大學(xué)嘉庚學(xué)院信息科學(xué)與技術(shù)學(xué)院 福建 漳州 363105)

0 引 言

云計算作為一種新型的計算模式,已被互聯(lián)網(wǎng)用戶廣泛使用。它是按需為用戶動態(tài)整合不同計算機虛擬資源以提供數(shù)據(jù)處理的計算服務(wù)系統(tǒng)。對用戶而言,其關(guān)注的是云計算的服務(wù)質(zhì)量。調(diào)查發(fā)現(xiàn),云計算的服務(wù)質(zhì)量最大程度取決于計算服務(wù)系統(tǒng)完成用戶所提交的任務(wù)的耗費時間。所以,提高任務(wù)的處理速度是用戶最關(guān)心的問題。此問題的關(guān)鍵就是尋找一種高效的調(diào)度方案使得用戶提交的任務(wù)處理時間盡量短,實質(zhì)為云計算的任務(wù)調(diào)度,屬于一種組合優(yōu)化問題。文獻[1]已證明云計算任務(wù)調(diào)度問題是一個非確定性多項式(Non-deterministic Polynomial,NP)難題。近年來一些學(xué)者已采用群體智能算法對該問題進行求解。文獻[2]采用遺傳算法并結(jié)合啟發(fā)式規(guī)則求解多優(yōu)先隊列分布式計算系統(tǒng)的任務(wù)調(diào)度問題,實驗證明該方法可以有效獲得可行解,但算法過于復(fù)雜,實現(xiàn)難度較大。文獻[3]針對基本蟻群算法自身存在的缺陷,設(shè)計一種改進蟻群算法,該算法可以減少云計算中任務(wù)執(zhí)行的總完成時間,但算法的迭代過程過于繁雜,其空間復(fù)雜度增加。文獻[4]提出了一種改進螢火蟲算法的云計算作業(yè)調(diào)度機制,實驗證明該方法可以有效減少作業(yè)的執(zhí)行時間,但其目標(biāo)僅僅針對作業(yè)的完成時間,并未考慮資源的使用情況。然而,隨著云計算的需求量日益增多,調(diào)度方案不僅要考慮如何快速完成多用戶提交的云任務(wù),而且還應(yīng)該關(guān)注計算資源的利用率。文獻[5]設(shè)計一種改進的負(fù)載均衡蜜蜂算法,仿真實驗說明該算法可以有效減少任務(wù)的執(zhí)行時間并提升資源的負(fù)載均衡,但蜜蜂算法自身存在進化后期收斂速度慢、共享機制低效等缺點。文獻[6]結(jié)合資源的負(fù)載均衡和任務(wù)的執(zhí)行時間,設(shè)計出一種改進的禁忌搜索啟發(fā)式調(diào)度策略,但算法的整體啟發(fā)規(guī)則較為復(fù)雜,操作相對煩瑣。文獻[7]提出了一種以任務(wù)總完成時間、任務(wù)平均完成時間和資源負(fù)載均衡為目標(biāo)的遺傳算法,實驗結(jié)果證明算法有效,但因為編碼問題,算法進化過程的操作過于繁雜,且可能陷入局部最優(yōu)。與此同時,粒子群算法(PSO)在多個領(lǐng)域已被證明具有記憶能力、參數(shù)少、收斂速度快、實現(xiàn)簡單等特點[8-10],并且在云計算任務(wù)調(diào)度問題上也得到了應(yīng)用。文獻[11]設(shè)計了一種針對云任務(wù)調(diào)度問題的小生境粒子群算法,實驗結(jié)果表明該算法可縮短任務(wù)執(zhí)行時間并使資源負(fù)載均衡。

基于以上考慮,本文根據(jù)云計算任務(wù)資源分配問題的特點,對基本的交換粒子群算法進行改進。引入進制編碼,在其基礎(chǔ)上重新定義運算法則,加入自適應(yīng)概率調(diào)整,改進其適應(yīng)度函數(shù),綜合考慮任務(wù)完成時間和資源負(fù)載均衡等指標(biāo),提出了一種新的云計算任務(wù)調(diào)度算法。

1 云計算任務(wù)調(diào)度描述

1.1 問題定義

現(xiàn)今,主流的云計算平臺大部分采用Map/Reduce的工作方式。該方式適用于處理大規(guī)模的數(shù)據(jù),可將用戶請求的大任務(wù)拆分成若干個子任務(wù),再根據(jù)指定的策略去調(diào)度合適的資源來處理計算這些子任務(wù)。換言之,云計算任務(wù)調(diào)度問題可理解為調(diào)度中心調(diào)度p個虛擬資源來處理計算q個子任務(wù),即建立虛擬資源與任務(wù)之間的映射,使其完成后達到任務(wù)總處理時間最少,資源利用率最高。

為簡化調(diào)度處理流程,現(xiàn)對云計算平臺中用戶提交的任務(wù)及其提供的資源作如下假設(shè):

1) 拆分后的子任務(wù)之間無前后執(zhí)行依賴關(guān)系,并且各子任務(wù)是相互獨立;

2) 一個子任務(wù)只由一個虛擬資源連續(xù)處理,不考慮中斷;

3) 拆分后的子任務(wù)數(shù)量遠遠多于平臺所提供的資源數(shù)量,并且資源處理任務(wù)的成本可知。

云計算任務(wù)調(diào)度的過程如圖1所示。

圖1 云計算任務(wù)調(diào)度過程

1.2 任務(wù)調(diào)度模型

云計算任務(wù)調(diào)度是由子任務(wù)集合、虛擬資源集合以及子任務(wù)與虛擬資源之間分配關(guān)系的集合構(gòu)成。可表示為:

D=(ST,VR,MAP)

式中:D表示一個云計算任務(wù)調(diào)度方案,ST為調(diào)度方案D中子任務(wù)的集合,VR是調(diào)度方案D中虛擬資源的集合,MAP是調(diào)度方案D中子任務(wù)與虛擬資源之間分配關(guān)系的集合。

子任務(wù)集合ST表示為ST={st1,st2,…,stq},其中第i個任務(wù)表示為sti(1≤i≤q,i∈Z)。虛擬資源集合VR表示為VR={vr1,vr2,…,vrp},vrj(1≤j≤p,j∈Z)表示第j個虛擬資源。子任務(wù)與虛擬資源之間分配關(guān)系的集合MAP表示為MAP={…,, …},其中,(1≤i≤q,1≤j≤p,i∈Z,j∈Z)表示第i個子任務(wù)分配到第j個虛擬資源處理。

另外,任務(wù)的衡量指標(biāo)一般采用MI(百萬條指令數(shù)),本文令Numberi表示子任務(wù)sti的待執(zhí)行機器指令條數(shù),即子任務(wù)的大小。資源的指令執(zhí)行速度采用MIPS(每秒執(zhí)行的百萬條指令數(shù))衡量,Speedj代表虛擬資源vrj的計算性能。ti,j代表子任務(wù)sti在虛擬資源vrj上的執(zhí)行時間。

ti,j=Numberi/Speedj

1≤i≤q,1≤j≤p,i∈Z,j∈Z

(1)

再者,p個虛擬資源處理計算q個子任務(wù)的期望計算時間ETC(Expeeted Time to Compute)[12-13]可用矩陣T表示,該矩陣是一個q×p的矩陣,如下:

虛擬資源vrj的執(zhí)行時間ExeTime為該資源處理計算其分配的所有任務(wù)的執(zhí)行時間之和。

(2)

式中:sti→vrj,sti∈ST表示虛擬資源vrj處理的所有任務(wù),k代表在該資源上執(zhí)行的任務(wù)總數(shù)。根據(jù)上文的假設(shè),以及各虛擬資源并行計算的特點,可得任務(wù)調(diào)度方案D的完成時間為最晚完成任務(wù)的虛擬機的執(zhí)行時間[13],表示方式如下:

Makespan=max{ExeTime(j)|j∈Z,1≤j≤p}

(3)

云計算任務(wù)調(diào)度追求的目標(biāo)應(yīng)是尋找一種使總完成時間Makespan最小的調(diào)度方案。

2 改進粒子群算法

2.1 離散粒子群算法

粒子群算法(PSO)是由Eberhart和Kennedy在1995年模擬鳥類群體覓食設(shè)計出的一種自適應(yīng)全局優(yōu)化搜索算法?；玖Ｗ尤核惴ㄝ^適合于求解連續(xù)空間優(yōu)化問題,但對于離散空間優(yōu)化問題,該算法并不適用。2000年Clerc[14]提出了一種以交換離散值向量為基礎(chǔ)的粒子群算法,用于求解離散空間優(yōu)化問題,已被證明成功求解旅行商問題(TSP)。對于本文研究的云計算任務(wù)調(diào)度問題來說,其結(jié)果亦分散在解空間,本質(zhì)上也屬于離散空間組合優(yōu)化問題,性質(zhì)與TSP問題相似,但又有區(qū)別。TSP問題的解為所有城市訪問順序的排列組合,而云計算任務(wù)調(diào)度問題的解則為子任務(wù)與虛擬資源的映射組合。另外,云計算任務(wù)調(diào)度求解過程需要考慮資源的負(fù)載均衡指標(biāo)。因此,本文將結(jié)合所研究的調(diào)度問題特點在基本的交換粒子群算法上做了相應(yīng)的改進。

2.2 粒子編碼

在基本的交換粒子群算法中,粒子是采用整數(shù)編碼方式,用不同的整數(shù)代表不同的城市,并且每個城市只被訪問一次,即訪問次序與城市是一一對應(yīng)。然而,在本文研究的問題中,同一個虛擬資源可以執(zhí)行多個不同的子任務(wù),為一對多的關(guān)系。由此可見,整數(shù)編碼并不適合本文的問題,因此本文結(jié)合云計算任務(wù)調(diào)度的特點,采用“進制編碼”對粒子的編碼方式進行改進。

對于任何包含q個待處理子任務(wù)的云環(huán)境來說,本文按1～q的順序?qū)@q個子任務(wù)進行編號。現(xiàn)假設(shè)數(shù)據(jù)中心代理有p個虛擬資源,且有q個子任務(wù)待計算處理,則本文按表1所示的方式進行p進制編碼。

表1 粒子的進制編碼

其中,虛擬資源的編號為1至p的整數(shù)。一組1至p的組合序列代表該問題解空間里的一個解,即表示一種云計算任務(wù)調(diào)度方案。

2.3 基于交換的運算法則

傳統(tǒng)粒子群算法中的粒子速度和位移更新公式并不適合求解離散空間組合優(yōu)化問題,故本文采用基于交換的運算。然而,運用原始的交換操作求解本文的問題會存在一定缺陷。因為,不同編號的子任務(wù)可能被分配到同一個虛擬資源上執(zhí)行,此時編碼序列中兩個任務(wù)對應(yīng)位置上的進制數(shù)相同,所以互換位置后編碼序列未發(fā)生任何改變,即粒子保持不動,從而降低算法的收斂速度。為解決此問題,本文提出的改進算法將重新定義交換子和交換序,并用其來表示粒子的飛行速度。其中,交換子表示在一種調(diào)度方案中互換兩個子任務(wù)的處理虛擬資源,且要求虛擬資源不為同一個,即交換子對應(yīng)的兩個虛擬資源編號不能相等;交換序則由一個或多個交換子組成。為了實現(xiàn)離散值向量間的交換且同時保留粒子群算法思想,本文采用如式(4)所示的粒子速度更新公式,式(5)為粒子的位置更新公式。

(Pi-Xi)⊕β×(Gb-Xi)

(4)

(5)

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

在粒子群算法中,適應(yīng)度函數(shù)是衡量粒子離目標(biāo)遠近的標(biāo)準(zhǔn),一般稱之為粒子的適應(yīng)值。種群中第i個粒子的適應(yīng)值記為f(Xi)。

由于實際的云計算環(huán)境中,不同虛擬資源的計算能力存在一定差異,經(jīng)常出現(xiàn)算力高的虛擬資源負(fù)載過高,其任務(wù)隊列中等待任務(wù)數(shù)量過多,而其他虛擬資源則處于空閑狀態(tài),因此造成資源使用率不高且負(fù)載不均衡,甚至任務(wù)的總完成時間較長。為了避免該現(xiàn)象發(fā)生,本文對適應(yīng)度函數(shù)做了相應(yīng)改進,在評價粒子適應(yīng)值時引進負(fù)載均衡指標(biāo),即給虛擬資源分配任務(wù)時既要追求完成時間短,同時要考慮各虛擬資源的負(fù)載情況。

虛擬資源vrj的負(fù)載Loadj此處定義為預(yù)分配到其上所有子任務(wù)的預(yù)期執(zhí)行時間,Loadj越大,表明虛擬資源vrj的負(fù)載越高,結(jié)合式(2)可得:

Loadj=ExeTime(j)

(6)

定義所有虛擬資源的預(yù)期執(zhí)行時間均值為Loadavg,公式如下所示:

(7)

式中:p為虛擬資源的個數(shù)。

對任意云計算任務(wù)調(diào)度方案的負(fù)載均衡評價指標(biāo)LB定義為所有虛擬資源的預(yù)期執(zhí)行時間的標(biāo)準(zhǔn)差,公式如下:

(8)

其中,調(diào)度方案的負(fù)載均衡評價指標(biāo)LB越大,表明該調(diào)度方案的負(fù)載均衡情況越差。

結(jié)合式(3)和式(8),本文定義的適應(yīng)度函數(shù)為:

f(X)=ω1Makespan+ω2BL

(9)

式中:ω1和ω2為權(quán)重值,ω1+ω2=1。適應(yīng)度函數(shù)f(X)越小,說明粒子X對應(yīng)的調(diào)度方案越好。

4.1.1 餐飲服務(wù)單位的食品安全管理制度齊全，確保食品原料新鮮、加工過程生熟分開，食品燒熟煮透，其加工時食品中心溫度應(yīng)不低于70℃。主要食品安全管理制度應(yīng)包括但不僅限于以下各項：食品安全崗位責(zé)任制；從業(yè)人員健康管理制度；從業(yè)人員培訓(xùn)管理制度；加工經(jīng)營場所清潔制度；設(shè)施設(shè)備清潔、消毒和維修保養(yǎng)制度；食品采購索證索票制度；食品進貨查驗和臺賬記錄制度；餐廚廢棄物處置管理制度；食品安全突發(fā)事件應(yīng)急處置方案；投訴受理制度等相關(guān)制度。

2.5 自適應(yīng)概率調(diào)整

云計算任務(wù)調(diào)度的求解比TSP問題復(fù)雜很多。首先,要求各個虛擬資源保持負(fù)載均衡;其次,子任務(wù)在不同算力的虛擬資源中執(zhí)行時間差別較大,執(zhí)行子任務(wù)的虛擬資源更換后,可能引起任務(wù)的總完成時間發(fā)生變化,導(dǎo)致尋找負(fù)載均衡且時間短的調(diào)度方案難度加大。與此同時,基本交換粒子群算法容易出現(xiàn)粒子聚集現(xiàn)象,導(dǎo)致算法在進化后期陷入局部最優(yōu)的可能性增加。為此本文引進一種自適應(yīng)的調(diào)整概率對粒子群算法做了改進。算法根據(jù)此概率值決定是否對粒子當(dāng)前所處的位置序列做調(diào)整操作。調(diào)整過程如下:在粒子的位置序列中隨機挑選兩個不在同一臺虛擬機上計算的子任務(wù),然后互換這兩個子任務(wù)的處理虛擬機。若互換后該粒子的適應(yīng)值低于當(dāng)前種群最優(yōu)值,則認(rèn)為此次調(diào)整操作有效并把該位置標(biāo)記成種群當(dāng)前最優(yōu)位置。此外,該概率值是根據(jù)算法迭代次數(shù)、前一代調(diào)整概率以及前一代調(diào)整的成功次數(shù)動態(tài)變化,公式如下:

λ=b·[1-nsuc/(apt·m)]

(10)

apt+1=r^(1-t/G)λ

(11)

式中:ap表示調(diào)整概率;m表示種群大小;nsuc表示前一代調(diào)整的成功次數(shù);b是常數(shù),本文取值為3;λ為調(diào)整權(quán)重;t為當(dāng)前的迭代數(shù);G為總迭代次數(shù)(進化代數(shù));r∈[0.2,0.5]。從式(10)和式(11)可以看出,迭代初期ap值較小以保持算法的收斂速度;迭代后期ap值增大,交換操作的次數(shù)將逐步增多,以此保持粒子的多樣性,從而降低陷入局部最優(yōu)的概率。

2.6 算法流程

本文提出的基于交換的改進粒子群算法,主要包括初始化種群、粒子移動、選擇和自適應(yīng)調(diào)整四個過程。具體操作步驟如下。

Step1初始化:輸入算法參數(shù),并在問題解空間里隨機產(chǎn)生m個粒子的位置序列和速度交換序。

Step2評價粒子:通過適應(yīng)度函數(shù)評價每一個粒子的適應(yīng)值。

Step3更新極值:1) 比較粒子的適應(yīng)值和個體本身歷史最優(yōu)值,若前者優(yōu)于后者,則將個體自身歷史最優(yōu)位置替換成粒子當(dāng)前的位置序列;2) 比較粒子的適應(yīng)值和種群當(dāng)前最優(yōu)值,如果前者好于后者,則將群體最優(yōu)位置替換成粒子當(dāng)前的位置序列。

Step5調(diào)整:根據(jù)調(diào)整概率調(diào)整粒子的位置序列,如果新的適應(yīng)值比種群當(dāng)前最優(yōu)值更優(yōu),則把種群最優(yōu)位置設(shè)為粒子調(diào)整后的位置序列。

Step6終止:重復(fù)Step2～Step5,直至滿足算法終止條件。

Step7輸出:輸出種群最優(yōu)位置對應(yīng)的調(diào)度方案。

3 仿真實驗與分析

為了驗證基于交換的改進粒子群算法(Improved Discrete PSO,IDPSO)對云計算任務(wù)調(diào)度的有效性和可行性,本文使用開源的CloudSim云仿真平臺進行實驗,并在同等實驗條件下與Min-Min調(diào)度算法、基本的離散粒子群算法(PSO)和基于交換運算法則的粒子群算法(Discrete PSO,DPSO)進行對比實驗。

3.1 實驗環(huán)境

仿真實驗環(huán)境具體信息如下:處理器為Inter(R) Core(TM) i5-6267U CPU @ 2.90 GHz,內(nèi)存為8 GB,操作系統(tǒng)為Windows 10,軟件平臺為Eclipse、CloudSim,編程語言為Java。

CloudSim是一款由Java編寫的基于事件的仿真框架,可在一臺主機上模擬大規(guī)模的集群及任務(wù)調(diào)度,只需在框架中實現(xiàn)其調(diào)度算法并重寫相關(guān)類,即可完成仿真工作。另外,IDPSO本身具有粒子群算法參數(shù)少、迭代流程簡便的特點,并且本文采用的進制編碼、交換子、交換序及交換操作均可使用基本類型數(shù)組存儲與運算,總體上實現(xiàn)相對簡便。

3.2 參數(shù)設(shè)置

在云仿真平臺中設(shè)置虛擬資源的個數(shù)為10,其計算能力參數(shù)范圍為1 024～2 048。子任務(wù)數(shù)量范圍為[100,400],子任務(wù)的待執(zhí)行機器指令條數(shù)范圍為1 000～10 000。

上述算法中設(shè)置的主要參數(shù)有,種群大小m為50,慣性權(quán)重ω為0.85,學(xué)習(xí)因子c1和c2均為2,ω1和ω2分別為0.6和0.4。

3.3 結(jié)果分析

實驗分為4種不同子任務(wù)數(shù),任務(wù)數(shù)分別為100、200、300和400,與之對應(yīng)的迭代數(shù)分別為500、700、1 000和1 500。每組各做50次獨立重復(fù)實驗,取其平均值。實驗結(jié)果如圖2和圖3所示。

圖2 不同任務(wù)數(shù)的適應(yīng)度函數(shù)值對比

圖3 不同任務(wù)數(shù)在不同迭代次數(shù)下取得的適應(yīng)值對比

圖2為Min-Min算法、PSO、DPSO和IDPSO在相同仿真環(huán)境和參數(shù)下的適應(yīng)度函數(shù)值對比圖。由圖可知,在任務(wù)數(shù)為100和200的情況下,IDPSO取得的結(jié)果最好,但其優(yōu)勢仍不夠明顯。在任務(wù)數(shù)為300和400時,IDPSO體現(xiàn)出更好的性能,其得到的適應(yīng)度函數(shù)值比DPSO低更多,且都好于Min-Min算法和PSO。特別在400個任務(wù)時,其優(yōu)勢更加突出。因此可得,IDPSO總體上取得的結(jié)果都優(yōu)于其他算法,隨著任務(wù)數(shù)增加,其效果越明顯,即更適合任務(wù)數(shù)較多的場景。換句話說,IDPSO在任務(wù)數(shù)較多時更能找到任務(wù)總完成時間短、資源負(fù)載均衡的調(diào)度方案。

圖3中的實驗是針對基于交換運算法則的粒子群算法改進前后的收斂對比。可以看出,不同任務(wù)數(shù)的求解過程中,IDPSO的收斂速度均比DPSO快,在任務(wù)數(shù)較少時效果較為明顯。由此可見,本文采用的進制編碼和重新定義的粒子更新運算法則具有一定的優(yōu)勢。同時可得,算法在迭代初期自適應(yīng)調(diào)整概率較小時,不會導(dǎo)致收斂速度變慢。還有,從算法取得的結(jié)果來看,DPSO尋優(yōu)過程較易陷入局部最優(yōu),加入自適應(yīng)概率調(diào)整后,IDPSO收斂速度在任務(wù)數(shù)多的情況下與DPSO相當(dāng),但其得到的適應(yīng)度函數(shù)更優(yōu),可見自適應(yīng)概率調(diào)整可有效促使IDPSO跳出局部最優(yōu)。另外,從圖3亦可發(fā)現(xiàn)IDPSO在不同任務(wù)數(shù)下的收斂適應(yīng)值均更小,可見具有魯棒性。由此可得,IDPSO在云計算任務(wù)調(diào)度中表現(xiàn)出更快的收斂速度,以及更強的全局搜索能力。

4 結(jié) 語

本文在交換的粒子群算法基礎(chǔ)上,通過重新定義交換子及粒子的運算法則,引入自適應(yīng)概率調(diào)整,并且以任務(wù)調(diào)度的總完成時間和資源的負(fù)載情況為適應(yīng)度函數(shù)來衡量調(diào)度方案的優(yōu)劣,以此進行云計算任務(wù)調(diào)度方案優(yōu)化。仿真實驗采用開源的CloudSim平臺,并在此平臺上進行實例分析。實驗結(jié)果表明本文提出的算法能夠有效地找出云計算任務(wù)調(diào)度結(jié)果,以完成較好的任務(wù)調(diào)度。通過多組實驗對比,可以得出改進后的算法具有收斂速度快和魯棒性強等特點。然而,本文提出的算法并未對速度更新公式中的幾個參數(shù)做動態(tài)調(diào)整,后續(xù)的工作中可以對這些參數(shù)進行自適應(yīng)改進,以期更好地提升算法性能,尋找到更優(yōu)的調(diào)度方案。另外,在實際云計算應(yīng)用中,不僅要考慮任務(wù)的總完成時間,還應(yīng)綜合考慮計算成本、帶寬、能耗等因素,這將是今后研究的重點。