孫長亞 王向文

1(上海電力大學計算機科學與技術(shù)學院 上海 200090)2(上海電力大學電子與信息工程學院 上海 200090)

0 引 言

云計算的基礎設施規(guī)模比單一的物理設備大很多，但是其提供的虛擬資源仍然有限，面對龐大的云任務，如何高效地將子任務分配給虛擬資源，進行合理的任務調(diào)度已成為一項必不可缺的研究課題[1-4]。先前解決云計算任務調(diào)度問題的各種努力主要針對完工時間[5-6]。隨著按需付費模式的普及，用戶也會重點關(guān)注執(zhí)行成本，對云服務提供商而言，還需要考慮虛擬機的負載均衡。幾種經(jīng)典的調(diào)度算法雖然實現(xiàn)簡單，但是缺點很明顯，如Min-Min算法[7]、Max-Min算法[8]和先進先出(First In First Out，F(xiàn)IFO)算法[9]。前兩個算法未能有效利用資源，從而容易導致負載不均衡的問題；FIFO算法按任務提交順序安排資源，如果較早提交的任務占用大量計算資源，則后面較小的任務必須等待很長時間。許多研究者使用啟發(fā)式算法解決云計算任務調(diào)度的問題。例如:文獻[10]提出了一種基于粒子群算法(PSO)的云任務調(diào)度方案，用于減少總執(zhí)行時間和任務傳輸時間，并且證明了PSO比遺傳算法運行的更快，有效減少了任務的執(zhí)行時間，但是PSO可能會陷入局部最優(yōu)解，容易導致求解精度下降，進而增加任務的完工時間和執(zhí)行成本；文獻[11]使用改進的蟻群算法進行云計算資源調(diào)度，通過信息素的累積和更新尋找較精確的解決方案，但是由于求解初期信息素匱乏，導致求解速率較慢，這樣可能會占用用戶大量時間，不能很好地滿足用戶的服務質(zhì)量需求；文獻[12]提出了一種基于最早完成時間和PSO的自適應參數(shù)遺傳算法，交叉概率的參數(shù)根據(jù)當前的演化狀態(tài)進行自適應，以促進進化并找到更好的解決方案，缺點是只考慮了最小化完工時間，優(yōu)化的目標過于單一；文獻[13]將遺傳算法和蟻群算法融合用于云計算任務調(diào)度，提高了云計算資源調(diào)度的效率，但是參數(shù)較多，編程實現(xiàn)較為復雜，且沒有考慮云系統(tǒng)的負載均衡，任務過大或過多時，容易導致云系統(tǒng)運行異常。

為了彌補傳統(tǒng)算法用于與計算任務調(diào)度的不足，本文綜合考慮任務完工時間、執(zhí)行成本、云系統(tǒng)負載均衡三個目標，提出了一種混合微生物遺傳粒子群算法(MGA-PSO)用于云計算任務調(diào)度。該算法結(jié)合微生物遺傳算法(MGA)和PSO的長處，在任務調(diào)度前期使用MGA縮小求解空間以提升尋優(yōu)速度；在任務調(diào)度后期使用動態(tài)慣性權(quán)重的PSO進一步尋找并快速收斂到最優(yōu)解。實驗結(jié)果表明，MGA-PSO算法可有效減少完工時間、降低執(zhí)行成本并平衡云數(shù)據(jù)中心虛擬機的負載。

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

云計算利用并行化技術(shù)處理大量任務，在數(shù)據(jù)中心利用虛擬化技術(shù)建立一定數(shù)量的虛擬機，根據(jù)用戶需求，將子任務分配到合適的虛擬機上執(zhí)行。通常采用Map/Reduce編程模型，通過Map(映射)和 Reduce(化簡)兩個階段， 將一個較大的任務分割成為很多較小的子任務，然后分配給若干個虛擬機并行執(zhí)行，最后返回運行結(jié)果。該模型具有良好的擴展性和容錯性，一臺機器宕機時，可以迅速將任務轉(zhuǎn)移到另外一個節(jié)點運行。本文只考慮子任務相互獨立的情況，整個任務調(diào)度框架可簡化為圖1。

假設有t個相互獨立的任務，如：A={α1,α2,…,αt},其中αi(0≤i≤t)表示第i個任務, 每個任務的大小為SIZEi；另假設云系統(tǒng)由p個高速互聯(lián)的虛擬機組成，如：B={β1,β2,…,βp}，其中βj(0≤j≤p)代表第j個虛擬機，每個虛擬機具備一定的處理能力MIPSj，使用MGA-PSO算法將個任務調(diào)度到p個虛擬機上以非搶占方式執(zhí)行(t>p)。

任務i在虛擬機j上執(zhí)行時間的計算公式如下：

Tij=SIZEi/MIPSj

(1)

虛擬機j的釋放時間RTj初始化為0，當有任務執(zhí)行時其更新公式如下：

RTj=RTj+Tij

(2)

任務i是虛擬機j上的第一個任務時，其開始執(zhí)行時間定義為0，否則定義為虛擬機j的釋放時間RTj。

STij=RTj

(3)

任務i的完成時間為任務i在虛擬機j上的開始執(zhí)行時間與執(zhí)行時間之和，其公式如下：

FTij=STij+Tij

(4)

任務的最大完工時間為所有虛擬機釋放時間的最大值，其更新公式如下：

Makespan=max{RTj|?βj∈B}

(5)

云環(huán)境的負載均衡定義為所有虛擬機釋放時間的標準差，其公式表示如下：

(6)

給云數(shù)據(jù)中心的內(nèi)存、帶寬、處理器和存儲空間設置一定的單位價格，通過統(tǒng)計任務調(diào)度過程中各資源的使用量計算執(zhí)行成本Cost。

云任務的調(diào)度過程是多目標優(yōu)化問題，所以本文定義適應度函數(shù)為任務完工時間、執(zhí)行成本及云環(huán)境負載均衡的加權(quán)和，用于衡量云計算任務調(diào)度的性能，其公式表示如下：

fitness=λ1×Makespan+λ2×LB+λ3×Cost

(7)

式中：λ1+λ2+λ3=1，可以根據(jù)任務需求靈活地調(diào)整各權(quán)重的值。任務調(diào)度的最終目標是最小化適應度函數(shù)的值。

2 混合微生物遺傳粒子群算法

2.1 微生物遺傳算法

John Holland教授于1975年提出了基于種群進化機制的遺傳算法(GA)，該算法提出了一個自然選擇的過程，隨著時間的推移會產(chǎn)生更好的解決方案，具有并行搜索、群體尋優(yōu)的特點，適用于大型空間的求解問題。

GA存在無法保留“好父母”的缺點：無論父母染色體多么優(yōu)秀，都不會保留，只能進行交叉變異操作生成新的個體，但是新個體并不一定優(yōu)于父母，容易導致解的精度不夠。為克服此缺點，借鑒微生物遺傳算法(MGA)[14]的思想，在種群每次迭代過程中，隨機抽取兩個染色體作為父染色體并比較其適應度，適應度好的父染色體不做任何處理，只對適應度差的父染色體進行改進的交叉操作和變異操作。如果變異后的子染色體適應度優(yōu)于其父染色體，則將其與適應度好的父染色體作為下一代置于新種群上，否則，保留原種群。這樣，可以有效保留種群中適應度好的父代染色體，大大提高了求解的精度。

MGA流程如圖2所示。首先，通過隨機創(chuàng)建染色體對種群進行初始化；其次，根據(jù)適應度值進行選擇操作，選擇一些染色體以創(chuàng)建新的種群；接著，隨機選擇兩個父代染色體進行改進的交叉操作，在適應度好的父染色體上隨機截取一個基因交叉點i，將第1到i個基因片段替代適應度差的父染色體對應位置；然后，對改進的交叉操作產(chǎn)生的子染色體進行基本位變異操作，即隨機選擇一個新基因去替換原有基因；最后，計算染色體的適應度，如果變異后的子染色體適應度更好，則將其取代適應度差的父染色體置于新種群上，否則，兩個父代染色體仍置于新種群上。整個過程持續(xù)進行，直到滿足終止條件，選擇適應度最好的染色體作為最優(yōu)解。

圖2 MGA流程

2.2 改進的粒子群算法

2.2.1標準粒子群算法

粒子群算法(PSO)[15]是一種基于群體智能的優(yōu)化算法，算法中的粒子類似于搜尋食物過程中飛行的鳥群，各個鳥群信息共享，它們總是搜索目前離食物最近鳥的周圍區(qū)域，根據(jù)飛行經(jīng)驗去尋找食物。PSO的設計思想就是基于這種信息共享機制，任意時刻每個粒子位置都受個體最佳位置和問題空間中全局最佳位置的影響。PSO中粒子的性能可通過適應度函數(shù)來測量，根據(jù)適應度值判斷粒子的好壞在每一次迭代中對粒子進行優(yōu)化。為描述粒子群算法，相關(guān)參數(shù)定義見表1，算法中粒子速度和位置的更新公式如下：

表1 粒子群算法相關(guān)參數(shù)定義

(8)

(9)

式(8)右側(cè)可以拆分為三部分：1) “慣性”，即粒子前一次迭代時速度的經(jīng)驗；2) “自我認知”，表示粒子當前位置與自身最佳位置的距離；3) “群體經(jīng)驗”，表示粒子當前位置與種群整體最佳位置的距離。PSO沒有MGA的交叉、變異操作，需要設置的參數(shù)較少，編程實現(xiàn)簡單且收斂速度快，可以用來加快求解速度。

2.2.2動態(tài)慣性權(quán)重的粒子群算法

慣性權(quán)重ω的取值影響PSO的性能。ω的值較大，有利于全局搜索，可以加快求解速度；ω的值較小，有利于局部搜索，能夠提高解的精度。標準PSO中慣性權(quán)重ω的取值固定，不利于在算法運行過程中實現(xiàn)全局搜索和局部搜索的平衡。

在PSO運行的早期，粒子相對分散，具有較好的多樣性，這時應該保持較大的慣性權(quán)重值，以增強算法的全局搜索能力；在算法運行的后期，粒子越來越聚集，這時應該保持較小的慣性權(quán)重值，以改善算法的局部搜索能力。很多算法將慣性權(quán)重設置為隨迭代次數(shù)的增加線性遞減，在一定程度上提高了算法的性能，但是線性遞減策略對于動態(tài)系統(tǒng)的效果并不理想。因此，提出一種隨迭代次數(shù)非線性遞減的動態(tài)慣性權(quán)重策略，其數(shù)學公式描述為：

(10)

式中：ωmax表示慣性權(quán)重的最大值；ωmin表示慣性權(quán)重的最小值；n為當前迭代次數(shù)；N為最大迭代次數(shù)；α1、α2、α3為控制因子，對慣性權(quán)重進行調(diào)節(jié)，保證算法運行前期具有較大的權(quán)重值，加強全局搜索，從而加快求解速度，在算法運行后期，使權(quán)重值快速減小，加強局部搜索，從而提高解的精度。

2.3 混合微生物遺傳粒子群算法

本文將MGA和改進的PSO融合，形成混合微生物遺傳粒子群算法(MGA-PSO)用于云計算任務調(diào)度。在任務調(diào)度前期，使用MGA處理初始種群，因為MGA找到較精確的解需要訓練很長的時間，所以本文提出：只迭代較少的次數(shù)以縮小求解范圍，無須找到較精確的解決方案。在任務調(diào)度后期，利用PSO快速收斂到最優(yōu)解的優(yōu)點，使用改進的PSO對上一階段產(chǎn)生的解決方案進一步優(yōu)化，找到最優(yōu)的解決方案，這一階段可以迭代多次，從而提高解的精度。MGA全局搜索能力強的優(yōu)點，可大大縮小求解范圍，提高解的精度，避免PSO在進一步優(yōu)化解決方案時陷入局部最優(yōu)解。而PSO快速收斂到最優(yōu)解的優(yōu)點，減少了云計算任務調(diào)度的時間，彌補了MGA需要較長時間找到精確解的缺點。

MGA-PSO算法用于云計算任務調(diào)度之前，需要建立云計算任務調(diào)度的解決方案與算法中染色體和粒子的對應關(guān)系。假設云系統(tǒng)有8個任務和3個虛擬機，在使用MGA階段，每個染色體由代表虛擬機的一些基因組成，染色體的長度等于云任務的數(shù)量，該階段可以定義染色體的長度為8，基因的種類為3。在使用改進的PSO階段，粒子是要分配的任務，粒子的維度是要分配的任務數(shù)，分配給粒子的每個維度的值是虛擬機編號，該階段可以定義粒子的維度為8，每個維度的值只能取0、1或2。

圖3展示了這種對應關(guān)系，它既可以表示一條染色體，又可以表示一個粒子。當表示一條染色體時，第0個基因的值為1，代表任務0被分配給虛擬機1；第3個基因的值為2，代表任務3被分配給虛擬機2。當表示為一個粒子時，第1維取值為0，代表任務1被分配給虛擬機0；第7維取值為2，代表任務7被分配給虛擬機2。

圖3 一條染色體或一個粒子

MGA-PSO算法用于云計算任務調(diào)度的流程如圖4所示，其執(zhí)行步驟總結(jié)如下。

圖4 MGA-PSO算法流程

1) 生成隨機種群并指定迭代次數(shù)，種群表示任務調(diào)度的一系列解決方案，每個解決方案是云任務在可用虛擬機上的分布。

2) 使用MGA縮小求解范圍，云計算任務調(diào)度的解決方案在這里被稱為染色體，通過MGA算子(即選擇、交叉、變異)在每次迭代中保留適應度較好的染色體，將得到的染色體傳遞給改進的PSO。

3) 使用改進的PSO進一步優(yōu)化解決方案，來自MGA的染色體被稱為粒子，在每次迭代中通過式(8)-式(10)逐漸增強粒子。

4) 根據(jù)式(7)選擇具有最佳適應度的粒子作為云計算任務調(diào)度的解決方案。

3 仿真實驗與性能分析

3.1 實驗環(huán)境及參數(shù)設置

為了評估MGA-PSO算法的性能，使用墨爾本大學開發(fā)的CloudSim[16]云仿真平臺進行仿真實驗，其運行的硬件環(huán)境為Intel i7處理器，16 GB DDR4內(nèi)存，1 TB硬盤空間，Windows 10系統(tǒng)。CloudSim支持云計算的研究與開發(fā)，用戶編寫的算法可以在此平臺上測試運行，減少了搭建云平臺的時間和成本。本文的仿真實驗將MGA-PSO算法用于云計算任務調(diào)度并與現(xiàn)有的云任務調(diào)度算法作比較，它們是GA和PSO。另外編寫一個和本文算法原理相同的GA-PSO算法，驗證對GA和PSO改進的必要性。

實驗中四個算法各自運行22次，去除實驗結(jié)果的最大值和最小值，取剩下20次實驗結(jié)果的平均值作為有效比較數(shù)據(jù)。算法中的相關(guān)參數(shù)設置見表2。

表2 算法的相關(guān)參數(shù)

續(xù)表2

3.2 性能分析

圖5顯示了四種算法用于云計算任務調(diào)度時的尋優(yōu)效果，任務數(shù)設置為500?？梢钥闯?，GA和PSO用于云計算任務調(diào)度的尋優(yōu)效果一般，過早的陷入了局部最優(yōu)。GA-PSO算法和MGA-PSO算法的適應度有一段時間沒有變化，可能陷入了局部最優(yōu)，但是隨著迭代次數(shù)的增加，都能迅速跳出局部最優(yōu)，并且能夠快速找到最優(yōu)解。本文MGA-PSO算法最終的適應度最低，尋優(yōu)效果最好，具有較強的全局搜索能力。

圖5 四種算法用于云計算任務調(diào)度的尋優(yōu)曲線

圖6和圖7顯示了小規(guī)模任務下四種算法完工時間和執(zhí)行成本的對比效果，任務數(shù)設置為20、40、60、80、100。從圖6可以看出，GA和PSO用于云計算任務調(diào)度會花費較多的時間，當任務數(shù)增加時，GA的完工時間增幅最快。整體上MGA-PSO算法的完工時間低于GA-PSO算法，該結(jié)果是因為所提出MGA在迭代過程中保留了適應度好的父代染色體，提高了解的精度，能以更好的方式收斂到解決方案。從圖7可以看出，GA的執(zhí)行成本最高，可能原因是發(fā)生了“早熟”收斂；MGA-PSO算法和GA-PSO算法及PSO用于小規(guī)模任務調(diào)度的執(zhí)行成本相差不大，這種微小的差異是由于所提出的混合算法主要依賴于PSO將解決方案收斂到最優(yōu)解，任務規(guī)模越小差異越小。

圖6 小規(guī)模任務四種算法的完工時間

圖7 小規(guī)模任務四種算法的執(zhí)行成本

圖8和圖9顯示了大規(guī)模云任務下四種算法完工時間和執(zhí)行成本的對比效果，任務數(shù)設置為200、400、600、800、1 000。從圖8可以看出，進行大規(guī)模云任務調(diào)度時， MGA-PSO算法和GA-PSO算法在完工時間方面具有較大優(yōu)勢，隨著任務規(guī)模的增加，MGA-PSO算法的完工時間明顯低于GA-PSO算法。這是由于任務規(guī)模變大，生成的初始種群更加隨機，在MGA-PSO算法前期能保留較多優(yōu)秀的父代染色體，大大提高了解的精度。從圖9可以看出，在執(zhí)行成本方面，當任務調(diào)度時，任務規(guī)模越大，MGA-PSO算法優(yōu)勢越明顯。這是因為動態(tài)慣性權(quán)重的PSO的改進有效平衡了算法的全局搜索能力和局部搜索能力，能夠找到更為合適的解決方案。

圖8 大規(guī)模任務四種算法的完工時間

圖9 大規(guī)模任務四種算法的執(zhí)行成本

圖10為四種算法用于云計算任務調(diào)度時的虛擬機負載均衡對比效果，任務數(shù)設置為20、80、200、1 000?？梢钥闯鯩GA-PSO算法的負載均衡效果比GA和PSO好很多，這是因為MGA-PSO算法將任務完工時間、執(zhí)行成本、云系統(tǒng)負載均衡三個目標作為任務執(zhí)行時虛擬機選擇的依據(jù)，總是選擇最合適的虛擬機來執(zhí)行任務，而不僅僅關(guān)注虛擬機的處理能力，這可能會選擇處理能力稍弱的虛擬機處理云任務，并減慢云任務的整體執(zhí)行速度(即增加完工時間)，但是在其他方面會有改善，例如虛擬機負載更加均衡，執(zhí)行成本更低。靈活地調(diào)整適應度函數(shù)中各權(quán)重的值可以滿足不同方面的需求。

圖10 虛擬機負載均衡效果對比

無論是在完工時間、執(zhí)行成本還是虛擬機負載均衡效果方面，MGA-PSO算法的調(diào)度性能都優(yōu)于同種思想的GA-PSO算法，可見對GA和PSO的改進提升了云計算任務調(diào)度的性能。

4 結(jié) 語

針對GA和PSO各自的優(yōu)缺點，本文將MGA(“升級版”GA)與改進的PSO組合成MGA-PSO算法用于云計算任務調(diào)度。該算法充分考慮了體現(xiàn)用戶服務質(zhì)量的完工時間、執(zhí)行成本和云系統(tǒng)負載均衡三個目標，并根據(jù)這些目標建立適應度函數(shù)作為算法運行時虛擬機選擇的依據(jù)。仿真結(jié)果表明，MGA-PSO算法在完工時間、執(zhí)行成本和負載均衡方面都優(yōu)于GA、PSO和GA-PSO算法，能夠滿足用戶的服務質(zhì)量需求，有效提高云計算任務調(diào)度的效率。