一種自適應(yīng)粒子群算法在云資源調(diào)度中的應(yīng)用

張娟芝,段中興,熊福力

(西安建筑科技大學(xué) 信息與控制工程學(xué)院，西安 710055)

0 引言

隨著物聯(lián)網(wǎng)及5G技術(shù)的快速發(fā)展及大規(guī)模商用，未來時代必定是云計(jì)算的時代。這對云計(jì)算在高速網(wǎng)絡(luò)和高性能計(jì)算系統(tǒng)方面有了更高的要求[1]。云計(jì)算是一種基于虛擬化技術(shù)的新型計(jì)算模式，它將大量用網(wǎng)絡(luò)連接的不同位置及空間的數(shù)據(jù)中心的物理計(jì)算資源構(gòu)成一個虛擬的資源池，并根據(jù)用戶對計(jì)算能力、存儲空間、網(wǎng)絡(luò)帶寬及其他信息服務(wù)的需求而實(shí)現(xiàn)統(tǒng)一的資源調(diào)度。因此，快速對各種計(jì)算資源進(jìn)行合理的調(diào)度是云計(jì)算須處理的關(guān)鍵點(diǎn)及難點(diǎn)所在。

近幾年大數(shù)據(jù)及云計(jì)算產(chǎn)業(yè)在全世界的興起及普及，國內(nèi)外學(xué)者對于云計(jì)算數(shù)據(jù)中心的研究方向已經(jīng)從傳統(tǒng)數(shù)據(jù)中心資源調(diào)度優(yōu)化所關(guān)注的應(yīng)用的穩(wěn)定性、數(shù)據(jù)的安全可靠性等方面[2]。云計(jì)算發(fā)展過程中，資源分配機(jī)制始終是數(shù)據(jù)中心效能優(yōu)化中亟待解決的問題，也是云計(jì)算領(lǐng)域內(nèi)的研究熱點(diǎn)[3]。

目前國內(nèi)外大多數(shù)研究資源調(diào)度算法都是基于蟻群算法(ACO,ant colony algorithm)、QoS(quality of service)網(wǎng)格管理算法、粒子群算法(PSO,particle swarm optimization)、遺傳算法(GA,genetic algorithm)、布谷鳥算法等智能算法[4]。對云計(jì)算而言，合理且高效地調(diào)度高度并發(fā)的任務(wù)十分必要。在這種情況下，分布式計(jì)算(distributed computing)、網(wǎng)格計(jì)算 (grid computing)等混合演進(jìn)形成了現(xiàn)如今較為成熟的云計(jì)服務(wù)模式和商業(yè)模型[5-6]。Keshanchi[7]等人使用改進(jìn)遺傳算法(GA,genetic algorithm)在云環(huán)境中進(jìn)行任務(wù)調(diào)度，其中GA采用精英選擇的方法防止早熟收斂。基于粒子群算法(PSO,particle swarm optimization)等智能算法的云計(jì)算資源調(diào)度與優(yōu)化也成為了研究的熱點(diǎn)[8]。如Mathiyalagan[9]等人引入了適用于網(wǎng)格計(jì)算編程的粒子群優(yōu)化算法以發(fā)展系統(tǒng)的能力；Srikanth[10]通過粒子群群優(yōu)化引入任務(wù)調(diào)度用于生成程序。Pandey[11]等人提出了作為一種可以基于粒子群進(jìn)行優(yōu)化的調(diào)度啟發(fā)式教學(xué)方法，以降低總執(zhí)行成本。該研究對比了PSO和最佳資源選擇(BRS,best resource selection algorithm)算法，PSO與BRS相比節(jié)省了三倍的成本，結(jié)果表明PSO效果更佳。Feng[12]等人簡要介紹了資源分配危機(jī)，計(jì)劃采用粒子群優(yōu)化算法，通過引入帕累托優(yōu)勢理論來解決這個問題。該理論的依據(jù)是每個任務(wù)的總?cè)蝿?wù)執(zhí)行時間，資源預(yù)留和QoS來研究資源的多目標(biāo)優(yōu)化問題。

綜上，雖然粒子群算法在云計(jì)算領(lǐng)域已經(jīng)有所應(yīng)用，但是在解決資源調(diào)度問題中存在易陷入局部尋優(yōu)的缺陷，因此本文對常規(guī)粒子群算法中的個體學(xué)習(xí)因子和社會學(xué)習(xí)因子進(jìn)行自適應(yīng)改進(jìn)得到一種自適應(yīng)粒子群優(yōu)化算法，使得算法全局尋優(yōu)能力明顯提升，且云計(jì)算資源任務(wù)隊(duì)列的總完成時間明顯下降。

1 問題描述與調(diào)度模型

1.1 問題描述

本文所研究的云計(jì)算資源調(diào)度問題以中小型企業(yè)私有云平臺的物理資源配置及小規(guī)模數(shù)量的用戶任務(wù)為研究對象，進(jìn)行私有云平臺的資源調(diào)度優(yōu)化問題的研究。

圖1展示出了云計(jì)算數(shù)據(jù)中心資源調(diào)度中兩階段任務(wù)調(diào)度的模型，其中包括各種類型的客戶終端(智能手機(jī)、PDA、平板電腦、PC等)、web訪問控制服務(wù)器、服務(wù)器集群等。每個客戶端生成一個或多個任務(wù)(例如加載文件)。每個任務(wù)Jj(j=1，2，，m)由兩個操作組成：執(zhí)行和傳輸。這兩種操作都是在同一臺服務(wù)器Mi(i=1，2，，n)上進(jìn)行的。設(shè)Tj(1)是執(zhí)行所需的時間，Tj(2)是傳輸所需的時間。網(wǎng)絡(luò)將所有客戶端通過訪問控制服務(wù)器連接起來。訪問控制服務(wù)器將任務(wù)分配給可用的物理服務(wù)器。根據(jù)任務(wù)規(guī)格，服務(wù)器按特定順序排列。最后服務(wù)器通過網(wǎng)絡(luò)執(zhí)行任務(wù)。

圖1 云數(shù)據(jù)中心資源調(diào)度模型圖

云計(jì)算資源調(diào)度每個階段的步驟和含義可以簡單描述如下：

1)提供虛擬機(jī)請求：在云計(jì)算環(huán)境下，用戶根據(jù)自身需要，將計(jì)算、存儲及帶寬相關(guān)的虛擬機(jī)的任務(wù)需求通過云服務(wù)供應(yīng)商提供的網(wǎng)絡(luò)鏈接將任務(wù)提交給云計(jì)算平臺的資源調(diào)度管理系統(tǒng)，由資源調(diào)度系統(tǒng)根據(jù)客戶任務(wù)需求進(jìn)行調(diào)度。

2)找到最佳資源點(diǎn)：云計(jì)算資源調(diào)度系統(tǒng)根據(jù)資源調(diào)度策略及算法，結(jié)合物理服務(wù)器資源的實(shí)際使用情況和虛擬機(jī)任務(wù)請求的信息，在云數(shù)據(jù)中心找到可以匹配的計(jì)算資源，并將虛擬機(jī)請求分配給該物理資源。

3)執(zhí)行調(diào)度任務(wù)：在匹配到最佳資源后，進(jìn)行對應(yīng)的虛擬機(jī)資源配置，然后由物理服務(wù)器執(zhí)行用戶所需的任務(wù)隊(duì)列，待一項(xiàng)任務(wù)或一個任務(wù)隊(duì)列完成后，物理機(jī)將任務(wù)執(zhí)行結(jié)果及自身狀態(tài)信息反饋給訪問控制器。

1.2 資源調(diào)度模型

資源調(diào)度任務(wù)調(diào)度的目標(biāo)是任務(wù)隊(duì)列的完成時間最小化，它涉及分配以及排序兩個問題。上述問題描述如下：

(1)

其中:M為n臺相同的并行的物理服務(wù)器，J是一組在兩階段任務(wù)調(diào)度中處理的m個任務(wù)。

Jj= {Tj(1),Tj(2)},(Tj(1),Tj(2)≥0,j=1,2,,m)

(2)

將整個計(jì)劃定義為s，其中包兩個部分：分配和排序。為了表示s中的分配關(guān)系，引入了一個分配矩陣A=[Aij]來表示J到M的映射：

(3)

分配矩陣可以表示所有可能的映射，并且每個映射都是唯一表示的。由于每個任務(wù)只能由一臺服務(wù)器處理，如下：

(4)

(5)

實(shí)際上，方程(4)和(5)意味著，在每一列中，只有一個元素的值為1。C(s)是完成任務(wù)執(zhí)行并傳輸?shù)臅r間中最大值，如下：

(6)

(7)

(8)

現(xiàn)在，調(diào)度優(yōu)化問題是：

(9)

(10)

aijtej(1)≤aiktbk(1)oraiktek(1)≤aijtbj(1)

(11)

aijtej(2)≤aiktbk(2)oraiktek(2)≤aijtbj(2)

(12)

i=1，2,n;j,k=1，2m;j≠k

在這個問題中，公式(10)意味著，對于每個任務(wù)，只有在執(zhí)行完成后才開始傳輸；約束(11)和(12)確保服務(wù)器執(zhí)行和傳輸。對于分配給同一臺服務(wù)器的所有任務(wù)，例如，一個新任務(wù)中的(Jk)的執(zhí)行(或傳輸)只在執(zhí)行(或傳輸)f之后才開始，或者以前的工作(Jj)已經(jīng)完成。分析需要兩個假設(shè)：所有服務(wù)器都是相同的，具有相同的網(wǎng)絡(luò)知識和相同的接收請求的機(jī)會[11]。

2 算法設(shè)計(jì)

2.1 粒子群算法

PSO由于其無可比擬性和廣泛利用范圍內(nèi)的充足性而變得流行。該算法基于鳥類的行為而工作。部分應(yīng)用程序利用PSO來處理NP-Hard問題，如調(diào)度和資源分配問題。在PSO中，每個優(yōu)化問題的解都是搜索空間中的一只鳥，稱之為“粒子”。所有的粒子都具有一個位置向量和速度向量，并可以根據(jù)目標(biāo)函數(shù)來計(jì)算當(dāng)前的所在位置的適應(yīng)值[12]。粒子的位置和速度更新如下：

P(j,1:n)=mod(round(p(j,1:n)+vel(j,:)),n1)+1

(13)

v=e*v(i)+k1*A*(pbest_p(i)-p(i))+

k2*B*(gbest_p-p(i))

(14)

式中，e為慣性因子，k1、k2分別為每個粒子的個體學(xué)習(xí)因子和社會學(xué)習(xí)因子，A、B為兩個取值范圍為(0， 1)的隨機(jī)數(shù)，pbest_p(j)為第j個粒子的個體歷史最優(yōu)解，gbest_p為全局最優(yōu)解，p(j)為第j個粒子當(dāng)前解。

2.2 粒子群算法自適應(yīng)改進(jìn)

常規(guī)粒子群算法在算法初期收斂速度快，但在后期收斂速度緩慢，易陷入局部尋優(yōu)的缺陷。本文提出了一種自適應(yīng)改進(jìn)的粒子群算法。在粒子群算法中個體學(xué)習(xí)因子k1和社會學(xué)習(xí)因子k2通過影響粒子的自我認(rèn)知與社會認(rèn)知從而影響粒子的運(yùn)行軌跡等[13]。本文通過對這兩個因子進(jìn)行自適應(yīng)改進(jìn)，從而提高算法的全局探索能力，保存種群多樣性，并不斷迭代更新，直到滿足停止條件。具體自適應(yīng)改進(jìn)如下：

在自適應(yīng)過程中，其取值與目標(biāo)函數(shù)和適應(yīng)度函數(shù)有關(guān)，具體表示如下：

k1=

(15)

k2=

(16)

式(15)、(16)中，F(xiàn)max為最大適應(yīng)度值，F(xiàn)avg為平均適應(yīng)度值，F(xiàn)c為適應(yīng)度中的較大值，F(xiàn)m為適應(yīng)度中的較小值，k1 max、k1 min、k2 max、k2 min分別為個體學(xué)習(xí)因子和社會學(xué)習(xí)因子的上、下限。為了使兩個因子的變化在極點(diǎn)處較為平緩的變化，本文使用了雙曲正切函數(shù)來構(gòu)造兩個學(xué)習(xí)因子的自適應(yīng)律。分別對個體學(xué)習(xí)因子和社會學(xué)習(xí)因子進(jìn)行了自適應(yīng)調(diào)整，使得當(dāng)個體適應(yīng)度趨于最大值時，該自適應(yīng)律可提高個體和社會學(xué)習(xí)因子；當(dāng)個體適應(yīng)度趨于最小值時，該自適應(yīng)律可降低兩個學(xué)習(xí)因子。

自適應(yīng)粒子群算法具體步驟如下：

1)粒子編碼：

本文中粒子位置的編碼長度為任務(wù)數(shù)量，即粒子的維度等于調(diào)度的任務(wù)數(shù)。設(shè)有m個任務(wù)，云資源環(huán)境下有n個物理資源，則粒子可編碼為式(17)所示的n維向量：

P={p1，p2，p3pm}

(17)

式中，1≤Pi≤n，(1≤i≤m)，粒子每一維坐標(biāo)表示一個任務(wù)編號，任意一維分量Pi表示分配給該任務(wù)的資節(jié)點(diǎn)編號。

圖2 粒子編碼示意圖

2）種群初始化：

設(shè)粒子種群數(shù)量為Pop，m個待分配任務(wù)數(shù)量，n個物理資源數(shù)量。初始化產(chǎn)生Pop個粒子，每個粒子的位置由向量P表示，第j個粒子為：

Pj={pj1,pj2,pj3pjm}

(18)

式中，1≤Pji≤n，表示任務(wù)j分配到第Pi號物理機(jī)上。初始化時將Pji的值取為1～n之間的隨機(jī)數(shù)。粒子速度由向量v表示：

vj={vj1,vj2,vj3，，vjm}

(19)

式中，1≤j≤Pop， -n≤vji≤n，vji在(-n,n)之間隨機(jī)取值作為初始化值。

3)適應(yīng)度計(jì)算：

根據(jù)模型定義的目標(biāo)函數(shù)，并取目標(biāo)函數(shù)值的倒數(shù)為適應(yīng)度函數(shù)值。根據(jù)式(15)和式(16)設(shè)置個體學(xué)習(xí)因子和社會學(xué)習(xí)因子。

4)位置和速度更新：

根據(jù)式(15)～(16)對粒子進(jìn)行位置和速度的更新。

5)粒子群更新：

對每個粒子，將其適應(yīng)度值與其自身經(jīng)過的最好位置作比較，如果較好，則將其作為當(dāng)前的最好位置pbest；同樣對每個粒子，將其適應(yīng)度值與其自身經(jīng)過的最好速度作比較，如果較好，則將其作為當(dāng)前的最好速度gbest。

自適應(yīng)粒子群算法流程如圖3所示。

圖3 自適應(yīng)粒子群算法示意圖

3 實(shí)驗(yàn)設(shè)計(jì)及分析

3.1 隊(duì)列任務(wù)執(zhí)行時間設(shè)定

3.2 實(shí)驗(yàn)方法及步驟

3.2.1 實(shí)驗(yàn)方法

本文基于Matlab 2016a 平臺，完成了粒子群算法及自適應(yīng)粒子群算法仿真程序的編寫。

在實(shí)驗(yàn)條件既定的情況下，通過兩種算法分別在n(n=10)個相同配置的物理資源、m(m=15、30、45)個隊(duì)列任務(wù)的情況下的算法仿真運(yùn)行結(jié)果進(jìn)行分組記錄及結(jié)果分析。

當(dāng)m=30、45時，待分配的任務(wù)以m=15時，表1給出的各任務(wù)進(jìn)行成倍增加，各任務(wù)的執(zhí)行完成時間保持不變。

表1 各任務(wù)執(zhí)行時間表

3.2.2 實(shí)驗(yàn)步驟

擬通過算法仿真程序的多次運(yùn)行并記錄相關(guān)運(yùn)行數(shù)據(jù)，以降低算法運(yùn)行過程中偶然性的性能優(yōu)劣趨勢，以獲取最優(yōu)的算法最優(yōu)解，分如下幾步進(jìn)行：

1)Matlab 算法仿真程序編寫:根據(jù)算法設(shè)計(jì)及流程圖，采用Matlab編程語言分別進(jìn)行粒子群及自適應(yīng)粒子群算法程序的編寫；

2)粒子群算法仿真數(shù)據(jù)采集:分別在3組不同物理資源及任務(wù)隊(duì)列數(shù)量條件下，粒子群算法仿真程序分別運(yùn)行30次，記錄粒子群算法的目標(biāo)函數(shù)值及迭代次數(shù)；

3)自適應(yīng)粒子群算法仿真數(shù)據(jù)采集:分別在3組不同物理資源及任務(wù)隊(duì)列數(shù)量條件下，自適應(yīng)粒子群算法仿真程序分別運(yùn)行30次，記錄自適應(yīng)粒子群算法的目標(biāo)函數(shù)值及迭代次數(shù)；

4)實(shí)驗(yàn)數(shù)據(jù)整理計(jì)算:計(jì)算粒子群算法、自適應(yīng)粒子群算法30次運(yùn)行數(shù)據(jù)中，目標(biāo)值(即任務(wù)隊(duì)列完成時間)的最大值、最小值及標(biāo)準(zhǔn)偏差。

3.3 實(shí)驗(yàn)對比分析

對粒子群算法和自適應(yīng)粒子群算法的實(shí)驗(yàn)結(jié)果進(jìn)行了分析，表2、表4給出了當(dāng)e=0.6，Pop=50，物理資源數(shù)n=10，待分配任務(wù)數(shù)m分別為15、30、45時分別仿真30次，兩種算法資源調(diào)度中任務(wù)隊(duì)列完成時間，單位為ms；表3、表5給出了兩種算法各個規(guī)模任務(wù)下總目標(biāo)函數(shù)的最大值、最小值、平均值及標(biāo)準(zhǔn)差。

表2 粒子群算法實(shí)驗(yàn)數(shù)據(jù)表

表3 粒子群算法實(shí)驗(yàn)結(jié)果分析表

表4 自適應(yīng)粒子群算法實(shí)驗(yàn)數(shù)據(jù)表

表5 自適應(yīng)粒子群算法實(shí)驗(yàn)結(jié)果分析表

圖5、圖6、圖7分別為粒子群、自適應(yīng)粒子群兩種算法在任務(wù)數(shù)分別為15、30、45的情況下的仿真結(jié)果對比。

從圖4～6中可以看出，當(dāng)物理資源數(shù)量n=10，待分配任務(wù)數(shù)量m分別為15、30、45時，粒子群算法曲線收斂粒子群迭代次數(shù)約20次左右即趨于穩(wěn)定，速度明顯高于自適應(yīng)粒子群算法，表現(xiàn)出了易陷入局部尋優(yōu)的缺點(diǎn)。自適應(yīng)粒子群算法迭代次100次后，逐步趨于穩(wěn)定，在一定程度上提升了算法的搜索能力，實(shí)現(xiàn)全局尋優(yōu)。同時對于目標(biāo)函數(shù)任務(wù)隊(duì)列總完成時間而言，自適應(yīng)粒子群算法資源調(diào)度中任務(wù)隊(duì)列的總的完成實(shí)驗(yàn)平均時間為分別為214.9 ms、264.5 ms、325.7 ms，較粒子群算法的總的完成時間215.9 ms、314.7 ms、405.7 ms，具有大幅度的提升。

圖4 任務(wù)為數(shù)15時算法對比圖

圖5 任務(wù)為數(shù)30時算法對比圖

圖6 任務(wù)為數(shù)45時算法對比圖

4 結(jié)束語

本文基于云資源兩級調(diào)度模型，以兩階段資源調(diào)度為研究對象，設(shè)定了以任務(wù)隊(duì)列完成時間為目標(biāo)的任務(wù)調(diào)度策略及數(shù)學(xué)模型。提出了一種自適應(yīng)粒子群算法用于解決粒子群算法在處理云資源調(diào)度過程中算法過早收斂從而難以全局尋優(yōu)的缺陷。

實(shí)驗(yàn)表明：本文提出的自適應(yīng)粒子群算法不僅具備良好的收斂性和全局尋優(yōu)能力，同時能夠大幅度降低云資源調(diào)度中任務(wù)隊(duì)列的總完成時間，具備良好的性能。用于企業(yè)內(nèi)部私有云或混合云平臺的云資源調(diào)度應(yīng)用中，可以提高任務(wù)執(zhí)行效率并降低云計(jì)算平臺的電力能耗。