張照勝，李蜀瑜

（陜西師范大學(xué) 計算機(jī)科學(xué)學(xué)院，陜西 西安 710119）

云計算環(huán)境下基于改進(jìn)粒子群算法的任務(wù)調(diào)度

張照勝，李蜀瑜

（陜西師范大學(xué) 計算機(jī)科學(xué)學(xué)院，陜西 西安 710119）

為了優(yōu)化云計算環(huán)境下任務(wù)調(diào)度，考慮調(diào)度過程中任務(wù)的最短完成時間、系統(tǒng)的負(fù)載均衡和經(jīng)濟(jì)成本3個目標(biāo)約束，然而3個目標(biāo)約束之間存在沖突，因此提出了一種使用改進(jìn)粒子群優(yōu)化算法來解決云計算任務(wù)調(diào)度中多目標(biāo)優(yōu)化問題，達(dá)到同時兼顧3個目標(biāo)約束的目的。選擇慣性權(quán)重的模糊自適應(yīng)策略對粒子群算法進(jìn)行改進(jìn)，從而能很好的平衡粒子的全局搜索能力和局部搜索能力，盡量避免過早收斂和陷入局部極值，并且引入移動子和負(fù)載因子的概念，用于實現(xiàn)算法對云計算環(huán)境下的任務(wù)調(diào)度。仿真結(jié)果表明，該算法對多目標(biāo)優(yōu)化問題，具有較好的尋優(yōu)能力。

云計算；任務(wù)調(diào)度；粒子群算法；最短完成時間；負(fù)載均衡；經(jīng)濟(jì)成本

云計算[1]是分布式計算的一種，是網(wǎng)格計算[2]和并行計算的發(fā)展，是這些計算科學(xué)概念的商業(yè)實現(xiàn)。其最基本的概念是，龐大的計算處理任務(wù)透過網(wǎng)絡(luò)被自動拆分成很多較小的子任務(wù)，再交由多部服務(wù)器所組成的龐大系統(tǒng)經(jīng)搜尋、計算分析之后將處理結(jié)果回傳給用戶。

由于云計算所面對的計算任務(wù)數(shù)量十分龐大，任務(wù)調(diào)度和資源分配問題是決定云計算效率的重點與難點。文獻(xiàn)[3]中對云計算的優(yōu)點和面臨的問題進(jìn)行了綜述；文獻(xiàn)[4]中基于文化算法和粒子群算法的混合，進(jìn)行云計算資源的調(diào)度，提高了系統(tǒng)資源的利用率，保持了系統(tǒng)的負(fù)載均衡；文獻(xiàn)[5]中引入動態(tài)多群體協(xié)作和變異粒子逆向飛行的思想與PSO結(jié)合，進(jìn)行云計算服務(wù)集群資源調(diào)度，優(yōu)化系統(tǒng)的負(fù)載均衡；文獻(xiàn)[6]中基于對粒子群算法的慣性權(quán)重進(jìn)行改進(jìn)和引入個體最優(yōu)位置的平均值的概念，依據(jù)云計算中的任務(wù)分配建模過程，優(yōu)化云計算在調(diào)度中任務(wù)派發(fā)速度和資源利用率；文獻(xiàn)[8]中通過對云計算環(huán)境下的數(shù)據(jù)部署進(jìn)行問題描述和建模，構(gòu)造粒子群算法適應(yīng)度函數(shù)，優(yōu)化了傳輸和處理所需的時間和費(fèi)用；文獻(xiàn)[9]中采用粒子群算法，對云計算任務(wù)調(diào)度中的最小任務(wù)完成時間和最快任務(wù)響應(yīng)時間這兩個目標(biāo)約束進(jìn)行優(yōu)化；文獻(xiàn)基于魚群算法中的聚群行為有較強(qiáng)的跳出局部極值的能力，能表現(xiàn)出全局收斂性好等特點，在粒子群算法中建立粒子中心的概念，利用聚群特性進(jìn)行優(yōu)化，進(jìn)而改進(jìn)粒子群算法的全局收斂能力；文獻(xiàn)[10]引入粒子的搜索中心概念，分析搜索中心在全局最優(yōu)解和局部最優(yōu)解之間均勻分布，優(yōu)化粒子群算法的收斂速度和穩(wěn)定性；文獻(xiàn)[11]構(gòu)造了一種對慣性權(quán)重進(jìn)行調(diào)整的非線性函數(shù)，在速度更新公式中增加了動態(tài)的隨機(jī)數(shù)，并引入在一定條件下對粒子位置重新擴(kuò)散機(jī)制，提高群體后期的多樣性，很好的改善了算法的尋優(yōu)性能；文獻(xiàn)[12]引入人工免疫系統(tǒng)中的克隆變異選擇機(jī)制和精英粒子學(xué)習(xí)機(jī)制（柯西分布的精英學(xué)習(xí)策略），增加粒子種群的多樣性和增強(qiáng)粒子逃離局部極值，提高多峰值函數(shù)優(yōu)化時全局尋優(yōu)能力；文獻(xiàn)[13]中基于改進(jìn)的粒子群算法，對云計算環(huán)境下任務(wù)調(diào)度中最短完成時間、經(jīng)濟(jì)成本和能耗3個目標(biāo)約束進(jìn)行優(yōu)化，但沒有考慮負(fù)載均衡這一重要目標(biāo)約束。鑒于以上文獻(xiàn)對云計算的任務(wù)調(diào)度目標(biāo)約束的優(yōu)化僅限于單個或兩個，或未考慮負(fù)載均衡這一重要目標(biāo)約束，以及對粒子群算法改進(jìn)策略的分析研究。

因此，本文中我們考慮3個目標(biāo)約束，即任務(wù)的最短完成時間、負(fù)載均衡和傳輸處理的經(jīng)濟(jì)成本，并采用改進(jìn)的粒子群算法優(yōu)化多目標(biāo)約束條件下的任務(wù)調(diào)度。

1 問題模型

在這個部分，用形式化的方式描述了系統(tǒng)模型。最終期望達(dá)到的目標(biāo)是，既滿足用戶對服務(wù)質(zhì)量的要求，又滿足云服務(wù)提供商的要求。因此，首先描述了云計算任務(wù)調(diào)度模型，其次描述了云計算任務(wù)調(diào)度的最小完成時間、負(fù)載均衡和經(jīng)濟(jì)成本3個目標(biāo)約束。通過對云計算任務(wù)調(diào)度模型和3個目標(biāo)約束的描述，得出要解決的是一個多目標(biāo)優(yōu)化問題。

1.1 云計算任務(wù)調(diào)度

目前，云計算環(huán)境下，Google提出的Map/Reduce編程模式是主流，該模式分為Map（映射）和Reduce（規(guī)約）兩個階段，把一個大任務(wù)拆分成多個較小的子任務(wù)，然后再將子任務(wù)進(jìn)行分配，本文只考慮子任務(wù)相互獨立的情況。通過將子任務(wù)合理的分配到資源結(jié)點上，從而使得任務(wù)的完成時間達(dá)到最小，系統(tǒng)的負(fù)載達(dá)到均衡，經(jīng)濟(jì)成本最少。

在云計算環(huán)境下，將N個相互獨立的子任務(wù)分配給M個資源結(jié)點。其中，任務(wù)集表示為 T={t1，t2，…，tN}，tj（j=1，2…，N）表示第j個子任務(wù)。資源結(jié)點集表示為VM={{vm11，vm12，…，vm1k}，{vm21，vm22，…，vm2k}，…，{vmm1，vmm2，…，vmmk}}vmij（i= 1，2，…，m；j=1，2，…，k）表示第i個虛擬機(jī)上的第j個資源結(jié)點，每個子任務(wù)只能在一個資源結(jié)點上執(zhí)行。任務(wù)集T與虛擬機(jī)上資源結(jié)點集VM的分配關(guān)系可用矩陣X表示為：

1.2 云計算任務(wù)調(diào)度的目標(biāo)約束

1.2.1 最短完成時間

最短完成時間是從提交所有子任務(wù)開始，直到最后一個子任務(wù)執(zhí)行完成所需要的時間。N個子任務(wù)t1，t2，…，tN，可能分布在空間不同的位置，N個子任務(wù)是相互獨立的，m個虛擬機(jī)VM1、VM2、...、VMm，分布在空間不同的位置。N個子任務(wù)發(fā)出請求，任務(wù)調(diào)度器首先會根據(jù)每個任務(wù)當(dāng)前的位置，將任務(wù)分配到距離該任務(wù)最近的一個虛擬機(jī)，該距離表示發(fā)出該任務(wù)請求的用戶與響應(yīng)該任務(wù)請求的虛擬機(jī)之間的地理位置距離。一個虛擬機(jī)表示一個Logical cluster，一個Logical cluster由若干個物理機(jī)組成，一個物理機(jī)表示一個資源結(jié)點[14]，一個子任務(wù)對應(yīng)一個資源結(jié)點。假設(shè)一個虛擬機(jī)包含k個資源結(jié)點，虛擬機(jī)個數(shù)m，系統(tǒng)資源結(jié)點總數(shù)M=m*k。

每個子任務(wù)的數(shù)據(jù)量映射為百萬條指令，order1表示任務(wù)ti需要處理的數(shù)據(jù)量。receivek：k={1，2，...，m}表示虛擬機(jī)k每小時可接收多少百萬條指令，sendk：k={1，2，...，m}表示虛擬機(jī)k每小時可發(fā)送多少百萬條指令，processk：k= {1，2，...，m}表示虛擬機(jī) k每小時可處理多少百萬條指令。

初始分配傳輸時間：初始時刻子任務(wù)j分配到虛擬機(jī)p上的傳輸時間

轉(zhuǎn)移時間：如果子任務(wù)j所分配的虛擬機(jī)p過載，那么需要將該任務(wù)從虛擬機(jī)p轉(zhuǎn)移到未過載的虛擬機(jī)q，轉(zhuǎn)移時間為

執(zhí)行時間：子任務(wù)j在虛擬機(jī)q上的執(zhí)行時間

子任務(wù)j在虛擬機(jī)q上期望完成時間為ECTqj=TTpj+MTpqj+ ETqj，那么max{ECTqj}為總?cè)蝿?wù)的完成時間，Cmax=max{ECTqj}，優(yōu)化目標(biāo)是總?cè)蝿?wù)的完成時間最短。

1.2.2 負(fù)載均衡

當(dāng)分配到某個虛擬機(jī)上的任務(wù)過多，而有些虛擬機(jī)上分配的任務(wù)可能又太少，這就會造成整個系統(tǒng)的資源負(fù)載不均衡、系統(tǒng)的性能下降和資源的浪費(fèi)。因此，為了使得整個系統(tǒng)負(fù)載均衡，本文給出的策略是，將已分配任務(wù)但未過載的虛擬機(jī)和未分配任務(wù)的虛擬機(jī)（任務(wù)數(shù)為0）按分配的任務(wù)量從小到大排列，將過載虛擬機(jī)上多余的任務(wù)移動到未過載或未分配的虛擬機(jī)上。為了表示每個虛擬機(jī)的負(fù)載情況，定義了負(fù)載因子的概念。

虛擬機(jī)vmi上分配的子任務(wù)數(shù)為α，承載子任務(wù)的上限為β，定義負(fù)載因子θi，其中θi=α-β，如果θi>0，那么虛擬機(jī)i就處于過載狀態(tài)，如果θi<0，那么虛擬機(jī)i就處于未過載狀態(tài)。

Then 1.負(fù)載不均衡；2.將過載虛擬機(jī)（θi>0）上多余的子任務(wù)向未過載虛擬機(jī)（θi<0）上轉(zhuǎn)移；3.整個虛擬機(jī)系統(tǒng)的負(fù)載因子

優(yōu)化的目標(biāo)是整個虛擬機(jī)系統(tǒng)的負(fù)載因子θ的值最小。

1.2.3 經(jīng)濟(jì)成本

在負(fù)載均衡模型中，將過載的虛擬機(jī)上的多余的任務(wù)重新分配到未過載的虛擬機(jī)上，在重新分配的過程中，如果采用優(yōu)先選擇未分配或已經(jīng)分配任務(wù)量最少的虛擬機(jī)策略，可能出現(xiàn)的情況是，待分配的任務(wù)與該虛擬機(jī)的距離較遠(yuǎn)，這樣就會增加傳輸時間和傳輸成本，從而增加任務(wù)的總完成時間，同時也增加了經(jīng)濟(jì)成本。基于經(jīng)濟(jì)成本因素的考慮，再重新分配時，優(yōu)先選擇離該任務(wù)最近的虛擬機(jī)。

定義：總成本=處理成本+移動成本

子任務(wù)j在虛擬機(jī)q上處理的費(fèi)用pcqj，處理時間為ETqj，單位時間的處理費(fèi)用為pl，其中l(wèi)∈{1，2，…，m}

子任務(wù)的處理成本：

所有任務(wù)的處理成本：

子任務(wù)的移動成本：

所有任務(wù)的移動成本：

總成本AC=PC+TC，優(yōu)化的目標(biāo)是完成全部任務(wù)的總成本AC最少。

2 模糊自適應(yīng)粒子群算法

粒子群算法是1995年Eberhart博士和Kennedy博士受鳥類族群覓食訊息傳遞的啟發(fā)，提出的一種基于群體協(xié)作的隨機(jī)搜索算法，該算法優(yōu)點是實現(xiàn)容易、收斂速度快、求解精度高。但是，標(biāo)準(zhǔn)粒子群算法在搜索過程中，容易過早收斂和陷入局部極值。基于ω起著權(quán)衡局部最優(yōu)能力和全局最優(yōu)能力的作用，本文使用模糊技術(shù)，借鑒文獻(xiàn)[15]提出的慣性權(quán)重模糊自適應(yīng)策略，使用不同的慣性權(quán)重更新同一代種群。

2.1 移動子和操作符

本文采用順序編碼，即虛擬機(jī)的序列編號作為粒子的編碼規(guī)劃，子任務(wù)的數(shù)量決定編碼長度，一個粒子對應(yīng)虛擬機(jī)上子任務(wù)的一個分配序列。假設(shè)子任務(wù)數(shù)N為18，虛擬機(jī)個數(shù)m為4時，粒子（3，1，2，1，1，1，2，1，1，2，4，1，3，1，2，1，1，4）可為一個可行的調(diào)度策略。為了更好地將該算法應(yīng)用于云計算任務(wù)調(diào)度，本文引入了移動子的概念，并對粒子群算法的速度和位置更新公式中的操作符賦予了新的含義。

定義1（移動子），（j，p，q），j∈{1，2，…，N}，p，q∈{1，2，…，m}，if（p=q），doNothing，表示將p號虛擬機(jī)上的子任務(wù)j移動到q號虛擬機(jī)上。

定義2（減法操作（X1-X2））

設(shè)pi，pj為粒子i和j的位置，則pi-pj為粒子i和j的位置減法操作，結(jié)果為一組移動序列。A=（3，1，2，4，1，3，2，1，1，2，4，1，3，4，2，3，2，4），B=（3，1，2，1，1，1，2，1，1，2，4，1，3，1，2，1，1，4），由于A（4）=4，B（4）=1，第一個移動子為（4，1，4），所以最后得 到 的移動 序 列 為 {（4，1，4），（6，1，3），（14，1，4，），（16，1，3），（17，1，2）}

定義3（加法操作（X+V））

將一組移動序列V作用于某個粒子位置X得到新位置。

例如：（3，1，2，1，1，1，2，1，1，2，4，1，3，1，2，1，1，4）+{（4，1，4），（6，1，3），(14，1，4)，（16，1，3），（17，1，2）}=（3，1，2，4，1，3，2，1，1，2，4，1，3，4，2，3，2，4）

定義4（乘法操作（r×V））

r為實數(shù)，取值范圍為[0，1]，k表示速度V的移動子的個數(shù)，r×V表示選取速度V的前r×k（取整）個移動子

例如：0.5×{(4，1，4)，（6，1，3），（14，1，4），（16，1，3）}={（4，1，4），（6，1，3）}

定義5（合并操作（v1⊕v2））

速度v1與v2合并為一個新的速度v。

例 如 ：{（4，1，4），（6，1，3）}⊕{（14，1，4），（16，1，3）}= {（4，1，4），（6，1，3），（14，1，4），（16，1，3）}

根據(jù)上述定義，本文使用如下公式更新粒子

速度更新公式：

位置更新公式：

2.2 自適應(yīng)調(diào)整慣性權(quán)值

為了很好的平衡粒子的全局搜索能力和局部搜索能力，使其不至于過早收斂和陷入局部極值，借鑒文獻(xiàn)[15]慣性權(quán)重的模糊自適應(yīng)策略，應(yīng)用到粒子群優(yōu)化算法中。

隸屬函數(shù)：

其中，di表示第i個粒子的佳粒子距，N為種群規(guī)模，S1、S2為控制參數(shù)，α、β為調(diào)整參數(shù)，滿足條件S10，β>0。

慣性權(quán)重自適應(yīng)調(diào)整函數(shù)：

其中，cIter為當(dāng)前迭代次數(shù)，MaxIter為最大迭代數(shù)，ws、we分別為w的初始值和結(jié)束值。

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

本文考慮了任務(wù)調(diào)度過程中的3個目標(biāo)，即最短完成時間、負(fù)載均衡和經(jīng)濟(jì)成本。用改進(jìn)的pso來解決多目標(biāo)優(yōu)化問題，適應(yīng)度函數(shù)Fitness（i）定義為：

式中，α+β+γ=1，α=0.5，β=0.3，γ=0.2。其中α、β、γ分別表示各目標(biāo)的權(quán)重。

2.4 模糊自適應(yīng)PSO算法

模糊自適應(yīng)PSO的云計算任務(wù)調(diào)度算法的基本執(zhí)行步驟如下：

圖1 模糊自適應(yīng)PSO算法流程

3 實驗與分析

3.1 仿真環(huán)境及算法設(shè)置

建立仿真環(huán)境，測試硬件為：Intel（R）Core（TM）i5-2400 3.10GHz，4.00G RAM，采用亞馬遜EC2的處理定價模式和亞馬遜CloudFront的數(shù)據(jù)傳輸定價模式，實驗采用CloudSim云計算仿真工具對標(biāo)準(zhǔn)PSO算法和M-PSO算法進(jìn)行仿真實驗，并對實驗結(jié)果進(jìn)行分析和對比。表1為實驗初始時的參數(shù)取值。

表1 本文算法主要參數(shù)設(shè)置

其中，達(dá)到最大迭代次數(shù)MaxIter或全局最優(yōu)值連續(xù)50次沒有變化為算法的終止條件。

3.2 實驗結(jié)果與性能分析

我們依據(jù)亞馬遜的收費(fèi)方式對10個虛擬機(jī)進(jìn)行模擬，用PSO方法和M—PSO方法分別對云計算任務(wù)進(jìn)行調(diào)度，仿真結(jié)果如圖2，圖3所示。圖2表示30個粒子，分別使用PSO方法和M—PSO方法，經(jīng)過1000次的迭代后，3個目標(biāo)約束在三維空間中粒子的分布情況，從圖中可以看出，M—PSO方法在系統(tǒng)負(fù)載均衡、最短完成時間和費(fèi)用方面與PSO方法比較，都表現(xiàn)出了較優(yōu)的效果，且粒子分布比較集中，更能找到全局最優(yōu)解。圖3表示PSO方法和M—PSO方法隨著迭代次數(shù)的增加適應(yīng)度值的收斂情況，從圖中可以看到，PSO收斂過早，并且陷入了局部極值，而M—PSO收斂的效果比PSO更好。

圖2 粒子目標(biāo)約束空間的分布

圖3 適應(yīng)度值收斂過程

4 結(jié)論

文中研究了云計算環(huán)境下任務(wù)調(diào)度模型，定義了最短完成時間、負(fù)載均衡和經(jīng)濟(jì)成本3個目標(biāo)約束的模型，采用標(biāo)準(zhǔn)粒子群算法和改進(jìn)的粒子群算法對云計算環(huán)境下多目標(biāo)約束的任務(wù)調(diào)度問題進(jìn)行優(yōu)化，仿真結(jié)果顯示，3個有互相沖突的目標(biāo)約束最終達(dá)到了一種均衡擇中狀態(tài)，并且改進(jìn)的粒子群算法表現(xiàn)的性能優(yōu)于標(biāo)準(zhǔn)粒子群算法。本文只考慮了云計算環(huán)境下任務(wù)調(diào)度的3個目標(biāo)約束和切割后的子任務(wù)間相互獨立的情況，而在實際應(yīng)用中情況比較復(fù)雜，還有其他因素需要考慮，比如QoS約束，節(jié)能約束等，并且子任務(wù)之間并非相互獨立，而是存在密切聯(lián)系的，因此下一步研究的目標(biāo)是在考慮更多的目標(biāo)約束條件和子任務(wù)之間并不是相互獨立的情況下，如何繼續(xù)不斷提高云計算任務(wù)調(diào)度的綜合性能。

[1]李喬，鄭嘯．云計算研究現(xiàn)狀綜述[J]．計算機(jī)科學(xué)，2011，38（4）：32-37．

[2]許元飛．網(wǎng)格計算中任務(wù)調(diào)度算法的仿真研究[J]．計算機(jī)仿真，2011，28(8)：75-78．

[3]Armbrust M，F(xiàn)ox A，Griffith R，et al.Above the Clouds:A Berkeley view of cloud computing[J].Eecs Department University of California Berkeley，2009，53(4):50-58.

[4]孟令璽，李洪亮．基于CA-PSO算法的云計算資源調(diào)度策略[J]．計算機(jī)仿真，2013，30(10)：406-410．

[5]劉萬軍，張孟華，郭文越．基于MPSO算法的云計算資源調(diào)度策略[J]．計算機(jī)工程，2011，37(11)：43-45．

[6]李媛媛，曲雯毓，栗志揚(yáng)，等．一種快速收斂粒子群優(yōu)化算法在云計算中應(yīng)用[J]．華中科技大學(xué)學(xué)報：自然科學(xué)版，2012:34-37．

[7]郭力爭，耿永軍，姜長源，等．云計算環(huán)境下基于粒子群算法的多目標(biāo)優(yōu)化[J]．計算機(jī)工程與設(shè)計，2013，34(7)：2358-2362．

[8]Anju Baby.Load balancing in cloud computing environment using pso algorithm[J].International Journal For Research In Applied Science and Engineering Technology，2014，2（4）：156-163.

[9]李榮鈞，常先英．一種新的混合粒子群優(yōu)化算法[J]．計算機(jī)應(yīng)用研究，2009，26（5）：1700-1702．

[10]吳曉軍，楊戰(zhàn)中，趙明．均勻搜索粒子群算法[J]．電子學(xué)報，2011，39（6）：1261-1266．

[11]任小波，楊忠秀．一種動態(tài)擴(kuò)散粒子群算法[J]．計算機(jī)應(yīng)用，2010，30（1）：159-161．

[12]林國漢，章兢，劉朝華．免疫綜合學(xué)習(xí)粒子群優(yōu)化算法[J]．計算機(jī)應(yīng)用研究，2014，31（11）：3229-3233．

[13]Yassa S，Chelouah R，et al.Multi-objective approach for energy-aware workflow scheduling in cloud computing environments.[J].Scientific world journal，2013，pp:1-13.

[14]E.Pacini，C.Mateos，et al.Dynamic scheduling based on particle swarm optimization for cloud-based scientific experiments[J].Clei Electronic Journal，2014，14（1）：1-14.

[15]郭文忠，陳國龍．求解TSP問題的模糊自適應(yīng)粒子群算法[J]．計算機(jī)科學(xué)，2006，33（6）：161-163．

Task scheduling based on improved particle swarm optimization in cloud computing environment

ZHANG Zhao-sheng，LI Shu-yu
（School of Computer Science，Shaanxi Normal University，Xi’an 710119，China）

For optimizing the task scheduling of cloud computing environment，it processes to consider the shortest completion time，load balancing，system constraints and economic costs of the three objectives，however，there is still have a conflict between these three objectives of constraints，thus we propose a method of using improved Particle swarm optimization（PSO）algorithms to solve the purpose of cloud computing task scheduling for multi-objective optimization problem to consider the three objectives constraints.Improving the global search ability and local search capability by using Fuzzy Adaptive Inertia Weight PSO strategy so that the particles can be well balanced to avoid premature convergence and local extremum，introducing the concept of the moving element and the load factor for the realization of task scheduling algorithm for cloud computing environments.Simulation results show that the algorithm for multi-objective optimization problem has better search capability.

cloud computing；task scheduling；PSO；the shortest completion time；load balancing；economic costs

TN602

A

1674－6236（2016）15-0005-04

2016-01-05 稿件編號：201601020

國家自然科學(xué)基金（41271387）

張照勝（1989—），男，湖北黃岡人，碩士。研究方向：云計算。