隋占麗

(仰恩大學(xué) 工程技術(shù)學(xué)院，福建 泉州 362014)

云計算是全球信息通訊技術(shù)行業(yè)的發(fā)展核心。隨著技術(shù)的發(fā)展，云服務(wù)慢慢發(fā)展成為“自來水”式的服務(wù)，個人或企業(yè)無需關(guān)心計算存儲資源從何而來，只需按需付費，就可以獲得想要的數(shù)據(jù)存儲處理資源[1]。但是，云資源的有限性和云計算需求的快速增長是當(dāng)前云計算急需解決的問題，云資源不同的分配調(diào)度方法，使云服務(wù)的質(zhì)量也大相徑庭。因此，挖掘更優(yōu)的云資源調(diào)度方法，對于提高云服務(wù)質(zhì)量、提高用戶云服務(wù)體驗具有重要意義。

云計算資源調(diào)度的方法有很多，開始出現(xiàn)先進(jìn)先出調(diào)度方法；爾后以此為基礎(chǔ)，出現(xiàn)了計算資源調(diào)度方法，考慮了資源饑餓度，也就是資源與任務(wù)的比值；公平調(diào)度策略[2]當(dāng)前仍在使用，此方法照顧到小用戶的感受，以用戶為單位分配資源，只是分配資源的多少按用戶任務(wù)量分派；當(dāng)前研究最多的智能調(diào)度算法[3-5]，就是使用智能算法尋求最優(yōu)的資源調(diào)度方法。當(dāng)前的優(yōu)化目標(biāo)大都比較單一，實現(xiàn)某方面優(yōu)化的同時，其他沒有考慮的方面表現(xiàn)較差，本文研究了實現(xiàn)多方面優(yōu)化的資源調(diào)度方法。

粒子群算法原理簡單、收斂較快，但是容易陷入局部最優(yōu)。本文使用混沌系統(tǒng)的遍歷性和雞群算法的多組群優(yōu)勢對粒子群算法進(jìn)行優(yōu)化，使算法容易擺脫局部極值，快速收斂至最優(yōu)點，使任務(wù)能夠在適合的虛擬機上執(zhí)行，同時實現(xiàn)云資源調(diào)度完成時間、負(fù)載均衡和消耗成本的優(yōu)化。

1 粒子群算法分析

粒子群算法是受鳥群覓食行為啟發(fā)得到的群智能算法[6-7]。當(dāng)前許多群智能算法在資源調(diào)度中取得了成功應(yīng)用，包括遺傳算法、粒子群算法、蟻群算法等。其中，遺傳算法具有漢明懸崖問題，遺傳算法中二進(jìn)制編碼比十進(jìn)制編碼搜索能力強，但是，二進(jìn)制之間的漢明懸崖使交叉和突變都難以跨越；蟻群算法適合路徑搜索問題，但是計算開銷大、調(diào)度時間長；粒子群算法規(guī)則簡單、收斂速度快，最適用于全局搜索，本文云資源調(diào)度算法以粒子群算法為基礎(chǔ)算法。

1.1 粒子群算法原理

在粒子群算法中，影響粒子運動的因素有三個：一是自身運動速度；二是自身記憶；三是群體影響[8]。記第i個D維的粒子的位置為xi=(xi1,xi2,…,xiD)，速度為vi=(vi1,vi2,…,viD)，則粒子下一時刻的速度位置更新為：

(1)

式中d∈[1,D]為粒子維數(shù)，k代表時刻，w為慣性因子代表自身速度的慣性，c1、c2為自身學(xué)習(xí)因子和群體學(xué)習(xí)因子，分別牽引粒子朝自身歷史最優(yōu)和群體最優(yōu)運動，r1、r2為(0,1)間的隨機數(shù)，pbest、gbest分別表示個體歷史最優(yōu)和群體最優(yōu)。

從式中可以看出，粒子運動的第一項為自身運動慣性，為粒子搜索提供動力；第二項為自身歷史最優(yōu)影響，牽引粒子朝自身最優(yōu)點運動；第三項為群體最優(yōu)影響，牽引粒子朝群體發(fā)現(xiàn)的最優(yōu)點運動。

1.2 粒子群算法參數(shù)分析及粒子編碼

在粒子群算法中，重要的參數(shù)包括種群規(guī)模C、粒子最大速度Vmax、學(xué)習(xí)因子c1和c2、慣性因子w。

種群規(guī)模C的影響。在粒子群中，每個粒子代表一個可行解，種群規(guī)模越大越容易探尋到最優(yōu)解，但是運算量很大；種群規(guī)模越小，則越不容易找到最優(yōu)解，但是，此時運算量較小。因此，要適當(dāng)選擇種群規(guī)模，一般問題種群規(guī)模為20～40，困難問題種群規(guī)模為100～200。

粒子最大速度Vmax的影響。最大速度代表速度的分辨率，若最大速度較小，粒子速度分辨率高，能夠找到最優(yōu)解，但是難以擺脫局部最優(yōu)解，若最大速度較大，擺脫局部最優(yōu)能力強，但是很容易錯過最優(yōu)解。

學(xué)習(xí)因子c1和c2的影響。學(xué)習(xí)因子代表歷史最優(yōu)和群體最優(yōu)對粒子運動的牽引程度，代表算法設(shè)置時對自身歷史最優(yōu)和群體最優(yōu)的重視程度。

慣性因子w的影響。慣性因子代表粒子自身運動對粒子運動影響的大小，慣性因子越大則算法全局搜索能力越強，但是卻放棄了參考自身最優(yōu)和群體最優(yōu)；慣性因子越小，能夠更加趨向于自身最優(yōu)和歷史最優(yōu)，但是算法變成了局部搜索算法。

粒子編碼方式。若存在N個用戶，M個資源，第t個用戶的任務(wù)數(shù)量為TaskNum(t)，則總?cè)蝿?wù)數(shù)TaskNum為：

(2)

對N個用戶提交的任務(wù)進(jìn)行編號，第i個用戶提交的第j個任務(wù)編號m為：

(3)

通過以上分析可知，染色體長度為TaskNum，每個任務(wù)所在的基因位為m，基因的可取值為[1,M]，基因的取值代表該位置上的任務(wù)由此資源執(zhí)行。

2 混沌粒子群算法

在粒子群算法中，粒子的初始化和進(jìn)化都具有很強的隨機性，粒子搜索過程的隨機性使算法可能難以搜索到最優(yōu)位置，容易陷入局部最優(yōu)。為了解決這些問題，使用混沌系統(tǒng)的遍歷特性，肯定比粒子群算法無順序無目的搜索表現(xiàn)出色，而且一定能夠跳出局部最優(yōu)。

2.1 混沌特性

混沌系統(tǒng)在自然和社會系統(tǒng)中存在較多，是復(fù)雜、隨機而又具有精確內(nèi)部規(guī)則的系統(tǒng)[9]。Logistics方程是典型的混沌系統(tǒng)，以此為例對混沌系統(tǒng)進(jìn)行介紹，即：

Sk+1=μSk(1-Sk)，

(4)

式中μ為管制變量，取值為4。S0取值為0～1間的任意值，就可以得到確定的序列S1,S2,…，此系統(tǒng)即為一個混沌系統(tǒng)。

2.2 混沌粒子群算法

使用混沌特性對粒子群算法的優(yōu)化主要體現(xiàn)在3點：一是對粒子最初位置和速度使用混沌序列設(shè)置，此設(shè)置使算法具有種群多樣性和遍歷性，同時不改變初始設(shè)置隨機化的特性；二是以當(dāng)前種群此刻找到的最佳位置為基礎(chǔ)形成混沌序列，使用混沌序列中的最佳位置代替種群中的一個個體位置，此措施可以使惰性個體擺脫局部極值，同時迅速找到全局最優(yōu)。

由以上分析，給出混沌粒子群算法的步驟為：

(1)給出算法最大循環(huán)次數(shù)和參數(shù)賦值；

(2)對粒子群所有粒子的初始位置和初始速度進(jìn)行混沌設(shè)置；

(3)若粒子i當(dāng)前狀態(tài)好于此粒子歷史最優(yōu)點，則更新粒子歷史最優(yōu)pbesti；若某粒子當(dāng)前狀態(tài)好于群體最優(yōu)值，則更新群體最優(yōu)值gbest；

(4)按照式(1)對粒子速度和位置進(jìn)行更新；

(5)對個體歷史最優(yōu)pbesti進(jìn)行混沌優(yōu)化，計算適應(yīng)度值，找出最佳個體P*；

(6)使用最佳個體替換粒子群中的惰性個體；

(7)若滿足算法結(jié)束條件則算法結(jié)束并輸出群體最優(yōu)值gbest；否則轉(zhuǎn)至Step3。

3 混沌粒子群雞群融合算法

粒子群算法原理簡單、搜索速度快，但是容易陷入局部最優(yōu)；雞群算法是典型的多種群算法，可以有效避免粒子陷入局部最優(yōu)和早熟問題。將混沌粒子群算法和雞群算法相融合，提出了混沌粒子群雞群融合算法。此算法繼承了粒子群算法收斂速度快和雞群算法有效避免局部最優(yōu)的優(yōu)勢，可以使粒子在解空間中實現(xiàn)更加充分的搜索，使云任務(wù)在更加適合的虛擬機上執(zhí)行。

3.1 雞群算法

雞群算法是模擬雞群覓食行為的群智能算法，主要模擬雞群的等級制度和行為習(xí)慣[10]。將雞群進(jìn)行理想化的描述：(1)將雞群分成若干組，每組都由一只公雞、幾只母雞和小雞組成；(2)公雞數(shù)量和組數(shù)一致，種群中適應(yīng)度好的雞被指定為公雞，適應(yīng)度差的雞指定為小雞，其余為母雞，母雞分到哪個組是隨機產(chǎn)生的，小雞和母雞的母子關(guān)系也是隨機產(chǎn)生的；(3)在等級制度下，一個組內(nèi)的支配關(guān)系不變，但是每經(jīng)歷數(shù)代步驟更新一次；(4)每組雞群在頭公雞的引導(dǎo)下尋覓食物，小雞在母親雞周圍尋覓食物，同時雞會偷取其他組發(fā)現(xiàn)的優(yōu)質(zhì)食物。

記種群中公雞、母雞、小雞、母親雞的數(shù)量分別為RN、HN、CN、MN。

在雞群中，公雞的適應(yīng)度越高，則在獲得食物方面越具有優(yōu)先權(quán)，也就是其食物搜索范圍越廣，即：

(5)

式中k為公雞編號且k≠i，Rand(0,σ2)為均值為0、方差為σ2的高斯分布，f為適應(yīng)度函數(shù)值。

母雞在尋覓食物時受公雞和小雞的約束，即：

(6)

式中Rand為(0,1)間的隨機數(shù)，r1為公雞編號，r2為小雞編號。

小雞在母親雞附近尋找食物，即：

(7)

3.2 混沌粒子群雞群速度和位置更新方法

混沌粒子群雞群算法核心思想是：(1)粒子群算法依靠個體的合作與競爭尋優(yōu)，加入雞群算法后，組群之間的信息交流可以使算法以更大概率逃出局部最優(yōu)；(2)從粒子群中選取適應(yīng)度大的粒子引導(dǎo)整個種群的搜索方向，增強全局搜索能力，使云任務(wù)在更合適的虛擬機上執(zhí)行。

參照雞群算法的等級制度，將所有粒子分為3類：A粒子、B粒子、C粒子，分別對應(yīng)雞群算法中的公雞、母雞和小雞。A粒子作為粒子群中的優(yōu)秀個體，其位置和速度的更新方式與式(1)保持不變。

粒子群的每個子群除了具有獨立性特點外，還要有相互的合作，也就是相互交流。基于此思想，B粒子的位置和速度更新方式為：

(8)

式中pbestid、gbestid分別表示粒子個體歷史最優(yōu)和本組群的群體最優(yōu)，xf為其他組群的最優(yōu)位置，c3為組群間學(xué)習(xí)因子，一般取值為[0,4]，在此取值為2，r3為(0,1)間的隨機數(shù)。

C粒子在B粒子周圍搜尋食物，其位置更新方法為：

(9)

3.3 混沌粒子群雞群算法流程

根據(jù)以上分析，給出混沌粒子群雞群融合算法流程為：

(1)建立一個粒子種群并對相關(guān)變量賦值，對粒子初始位置和速度進(jìn)行混沌設(shè)置；

(2)計算粒子的個體適應(yīng)度值和組群適應(yīng)度值；

(3)將粒子群進(jìn)行分組，在A粒子和B粒子間確定隸屬關(guān)系，在B粒子和C粒子間確定母子關(guān)系；

(4)按照粒子分類進(jìn)行速度和位置更新；

(5)若更新后的全局適應(yīng)度值高則位置更新，否則不更新；

(6)迭代次數(shù)是否達(dá)到上限，若是則算法結(jié)束輸出全局最優(yōu)值，否則依據(jù)適應(yīng)度值判斷是否對等級進(jìn)行重新劃分，如需要則更新等級，否則轉(zhuǎn)至(3)。

3.4 評價函數(shù)

本文作出以下假設(shè)：(1)任務(wù)是由若干大任務(wù)分解成的一批小任務(wù)，且子任務(wù)劃分粒度相同；(2)任務(wù)量遠(yuǎn)遠(yuǎn)超過虛擬機數(shù)量。記N為任務(wù)總數(shù)，Ti為第i個子任務(wù)，M為虛擬機數(shù)量，VMj代表第j個虛擬機，RCU(VMj)為虛擬機VMj運行單元時間的成本。第j個虛擬機完成系統(tǒng)交給的所有子任務(wù)時間記為vmTime(VMj)，則：

(10)

式中Time(Ti,VMj)表示子任務(wù)Ti在虛擬機VMj上的執(zhí)行時間，n為分派到VMj上的子任務(wù)數(shù)量。

總?cè)蝿?wù)執(zhí)行時間評價函數(shù)定義為所有虛擬機所用時間最長的一個，即：

completeTime=max(vmTime(VMj))j∈[1,M] ，

(11)

負(fù)載均衡度DLB評價函數(shù)使用完成時間的比值來度量，即：

(12)

此式的含義是：各虛擬機完成任務(wù)所用時間與總?cè)蝿?wù)完成時間越相近則負(fù)載越均衡，那么DLB值越大則負(fù)載均衡度越高。

使用每個虛擬機完成任務(wù)的時間和單位時間的成本消耗，可以給出所有任務(wù)完成的總成本為：

3.5 基于融合算法的云資源調(diào)度流程

通過以上分析，給出混沌粒子群雞群融合算法的云資源調(diào)度流程如圖1所示。

圖1 基于融合算法的云資源調(diào)度流程圖

4 實驗驗證

使用CloudSim云計算平臺仿真模擬器對本文提出的優(yōu)化算法進(jìn)行調(diào)度效果驗證。模擬器參數(shù)為：1個數(shù)據(jù)中心(包含兩臺主機)，虛擬機數(shù)量為5，虛擬機大小為2048MB，帶寬為1000bit，1個虛擬機只有1個PE，PE處理能力為100-300MIPS；任務(wù)總量設(shè)置為10-50，任務(wù)長度為15000-50000MI。

為了與本文提出的混沌粒子群雞群融合算法進(jìn)行對比，本文分別使用輪詢算法、粒子群算法、混沌粒子群算法和混沌粒子群雞群融合算法對云計算資源進(jìn)行分配，統(tǒng)計各調(diào)度策略的任務(wù)執(zhí)行時間、負(fù)載均衡度、消耗成本，結(jié)果分別如圖2、圖3、圖4所示。

圖2 各調(diào)度策略任務(wù)完成時間

圖3 各調(diào)度策略負(fù)載均衡度

圖4 各調(diào)度策略資源消耗對比

從圖2可以看出，在任務(wù)量為10～50的情況下，混沌粒子群雞群融合算法的任務(wù)完成時間最少，而且隨著任務(wù)量的增加，耗時上的差距越來越明顯，使用外推的思想，若任務(wù)量繼續(xù)增大則混沌粒子群雞群算法的用時優(yōu)勢會更加明顯；從圖3可以看出，基于混沌粒子群雞群算法的調(diào)度策略資源分配最公平，負(fù)載均衡度最高(接近于1)，說明各虛擬機時間消耗相近，分配最為合理；從圖4可以看出，基于混沌粒子群雞群算法的能量消耗最少，而且隨著任務(wù)量增加，耗能差別也在拉大。

綜合圖2、圖3、圖4，可以發(fā)現(xiàn)以下規(guī)律：(1)三種評價策略下，調(diào)度算法優(yōu)異程度排序為：混沌粒子群雞群算法、混沌粒子群算法、粒子群算法和輪詢算法，這是因為使用混沌系統(tǒng)優(yōu)化粒子群算法時，混沌系統(tǒng)具有遍歷性，可以促進(jìn)粒子群算法擺脫局部極值而搜索全局最優(yōu)；而在混沌粒子群算法基礎(chǔ)上融入雞群算法，就實現(xiàn)了將粒子群進(jìn)行分組，每個組群作為一個小團(tuán)隊在搜索最優(yōu)位置，而且團(tuán)隊之間具有最優(yōu)位置的信息交流，不僅使粒子群算法盡快擺脫局部極值，而且能夠在解空間實現(xiàn)充分細(xì)致的搜索，使云任務(wù)能夠找到最合適的虛擬機執(zhí)行；(2)在耗時和耗能上，任務(wù)量越大，耗時和耗能優(yōu)勢越明顯，這是因為在任務(wù)量較小的情況下，虛擬機計算能力與云任務(wù)計算需求之間的矛盾較小，劣質(zhì)的調(diào)度策略就能夠在一定程度上滿足調(diào)度要求，使得優(yōu)質(zhì)調(diào)度策略的優(yōu)勢不是很明顯；而當(dāng)任務(wù)量較大時，所有虛擬機都在執(zhí)行任務(wù)，此時計算資源供應(yīng)和需求之間的矛盾突出，使用優(yōu)質(zhì)算法進(jìn)行合理的資源調(diào)度優(yōu)勢就會凸顯出來。

綜上所述，混沌粒子群雞群融合算法在任務(wù)耗時、負(fù)載均衡度和消耗成本上均具有優(yōu)勢，且任務(wù)量越大，耗時和耗能的優(yōu)勢越明顯。

5 結(jié)語

本文以云計算資源調(diào)度中的耗時、負(fù)載均衡、耗能為優(yōu)化目標(biāo)，提出了混沌粒子群雞群融合算法，具體工作為：

(1)使用混沌系統(tǒng)的遍歷性和雞群算法的多組群性優(yōu)化粒子群算法，使粒子群算法能夠擺脫局部最優(yōu)，在全局范圍內(nèi)細(xì)致搜索；

(2)雞群算法作為多組群算法，融入到混沌粒子群算法中，將粒子群進(jìn)行分組，組內(nèi)粒子又分等級，組群在搜索最優(yōu)位置的同時，也實現(xiàn)了組群間的最優(yōu)位置交流；

(3)使用CloudSim軟件對算法進(jìn)行驗證，結(jié)果表明混沌粒子群雞群算法在耗能、負(fù)載均衡度和耗能上均具有優(yōu)勢。

參考文獻(xiàn)：

[1] 杜偉. 分布式結(jié)構(gòu)化存儲調(diào)度服務(wù)器的設(shè)計與實現(xiàn)[D]. 成都：電子科技大學(xué), 2013.

[2] 楊洋. 基于資源狀況的延時等待公平調(diào)度算法的研究[D]. 沈陽：東北大學(xué), 2014.

[3] 卓濤, 詹穎. 改進(jìn)人工蜂群算法的云計算資源調(diào)度模型[J]. 微電子學(xué)與計算機, 2014(7):147-150.

[4] 袁浩, 李昌兵. 基于社會力群智能優(yōu)化算法的云計算資源調(diào)度[J]. 計算機科學(xué), 2015, 42(4):206-208.

[5] 嵇可可. 基于動態(tài)趨勢預(yù)測蟻群算法的云計算資源調(diào)度優(yōu)化研究[J]. 科技通報, 2016, 32(1):187-190.

[6] 李擎, 張超, 陳鵬,等. 一種基于粒子群參數(shù)優(yōu)化的改進(jìn)蟻群算法[J]. 控制與決策, 2013(6):873-878.

[7] 王東風(fēng), 孟麗, 趙文杰. 基于自適應(yīng)搜索中心的骨干粒子群算法[J]. 計算機學(xué)報, 2016, 39(12):2652-2667.

[8] Mehdinejad M, Mohammadi-Ivatloo B, Dadashzadeh-Bonab R, et al. Solution of optimal reactive power dispatch of power systems using hybrid particle swarm optimization and imperialist competitive algorithms [J]. International Journal of Electrical Power & Energy Systems, 2016, (83):104-116.

[9] Cai P, Yuan Z Z. Hopf bifurcation and chaos control in a new chaotic system via hybrid control strategy [J]. Chinese Journal of Physics, 2017, 55(1):64-70.

[10] 李振璧, 王康, 姜媛媛. 基于模擬退火的改進(jìn)雞群優(yōu)化算法[J]. 微電子學(xué)與計算機, 2017, 34(2):30-33.