云仿真平臺任務(wù)負(fù)載均衡優(yōu)化調(diào)度研究

金 鵬

（遼寧工程職業(yè)學(xué)院 信息中心，鐵嶺 112008）

0 引言

在工程及制造行業(yè)中，通常利用大型CAE軟件進(jìn)行工程數(shù)值分析、結(jié)構(gòu)與過程優(yōu)化設(shè)計、強(qiáng)度與壽命評估、運(yùn)動、動力學(xué)仿真，以此驗(yàn)證未來工程、產(chǎn)品的可用性與可靠性[1]。隨著設(shè)計模型越來越復(fù)雜，網(wǎng)格劃分越來越精細(xì)，單機(jī)版的CAE軟件運(yùn)行效率低下，無法滿足系統(tǒng)計算要求[2]。當(dāng)前，為提高仿真效率，通常需要通過多臺服務(wù)器搭建云仿真平臺，利用CAE并行模塊將仿真任務(wù)分割為若干個并行子任務(wù)，再根據(jù)任務(wù)調(diào)度算法將這些子任務(wù)分配到多個虛擬計算資源節(jié)點(diǎn)同時并行仿真，利用云仿真平臺高速的并行運(yùn)算速度完成仿真分析。

不同的任務(wù)調(diào)度算法都會對仿真任務(wù)的執(zhí)行時間和仿真系統(tǒng)的負(fù)載平衡造成不同的影響，進(jìn)而影響云仿真平臺的性能。當(dāng)前，云仿真任務(wù)調(diào)度算法已成為云仿真的一個研究重點(diǎn)與熱點(diǎn)[1]。

求解云仿真任務(wù)最優(yōu)調(diào)度方案就是尋找云仿真子任務(wù)與云平臺虛擬機(jī)的最優(yōu)組合匹配關(guān)系。當(dāng)前云仿真任務(wù)調(diào)度算法的研究大多先采用連續(xù)空間的智能優(yōu)化算法（粒子群、蟻群、遺傳等算法）求解調(diào)度方案，再對解值向量中的編碼進(jìn)行取整求余后得到十進(jìn)制編碼，如文獻(xiàn)[3,4]。這種近似編碼勢必降低結(jié)果的精確度。

本文根虛擬機(jī)與子任務(wù)的兩種組合關(guān)系為“匹配”與“不匹配”，用編碼“1”代表“匹配”，編碼“0”代表“不匹配”。將云平臺中所有子任務(wù)與虛擬機(jī)的組合關(guān)系構(gòu)造為離散二進(jìn)制粒子群，利用混沌離散粒子群算法（CBPSO）搜索子任務(wù)與虛擬機(jī)的最優(yōu)組合，即滿足使適應(yīng)度達(dá)到全局最優(yōu)值，且各子任務(wù)與虛擬機(jī)匹配關(guān)系都為“1”。

1 負(fù)載均衡調(diào)度原理

云仿真平臺的調(diào)度分為兩個層次，第一個層次是任務(wù)調(diào)度，將負(fù)載過重虛擬機(jī)上的子任務(wù)動態(tài)調(diào)度到負(fù)載較輕的虛擬機(jī)上，使云平臺的虛擬機(jī)集群整體上負(fù)載均衡；第二個層次是虛擬機(jī)調(diào)度，將負(fù)載過重物理主機(jī)上的虛擬機(jī)遷移到負(fù)載較輕的物理主機(jī)[3]。本文主要研究的是第一個層次的調(diào)度問題，即求解云仿真任務(wù)的最優(yōu)調(diào)度方案。求解云仿真任務(wù)最優(yōu)調(diào)度方案就是尋找云平臺上的m個虛擬機(jī)與n個子任務(wù)（m＜n）的最優(yōu)組合匹配關(guān)系。

2 負(fù)載均衡調(diào)度模型

為保證云平臺的性能及穩(wěn)定性，又保證仿真用戶的仿真效率需求，本文將綜合任務(wù)總執(zhí)行時間和負(fù)載均衡度建立總的適應(yīng)度函數(shù)Fitness，在解集空間內(nèi)，利用混沌離散粒子群算法（CBPSO）搜尋使Fitness達(dá)到最大值的最優(yōu)位置，即當(dāng)前云平臺中虛擬機(jī)與仿真子任務(wù)為最優(yōu)組合。

2.1 云仿真任務(wù)總執(zhí)行時間

設(shè)當(dāng)前云仿真平臺中，仿真子任務(wù)Wj的長度為lengthi，虛擬機(jī)VMi的CPU運(yùn)行速度為mipsi，則Wj在VMi上的執(zhí)行時間timeij為：

其中，1≤i≤m，1≤j≤n，m和n分別是云仿真平臺上虛擬機(jī)總數(shù)和仿真任務(wù)總數(shù)。

設(shè)分配到VMi的子任務(wù)（1個或多個）集合為k，則分配到節(jié)點(diǎn)V Mi上的所有子任務(wù)的執(zhí)行時間為由于所有子任務(wù)并行運(yùn)算，則當(dāng)前云仿真任務(wù)總的執(zhí)行時間為：

2.2 虛擬機(jī)集群負(fù)載均衡度

本文將虛擬機(jī)集群總體負(fù)載度的標(biāo)準(zhǔn)差作為虛擬機(jī)集群的負(fù)載均衡度。

設(shè)當(dāng)前虛擬機(jī)VMi所能提供配置資源：

其中，mipsi為VMi的CPU處理速度；memi為VMi的內(nèi)存大小；bwi為VMi網(wǎng)絡(luò)帶寬。

設(shè)當(dāng)前VMi上的子任務(wù)所占用的配置資源：

則當(dāng)前虛擬機(jī)VMi的負(fù)載度表示為：

其中，μ1+μ2+μ3=1，μ1、μ2、μ3分別為虛擬機(jī)VMi的CPU權(quán)重、內(nèi)存權(quán)重、網(wǎng)絡(luò)帶寬權(quán)重，本文取μ1=0.6，μ2=0.3，μ3=0.1。

當(dāng)前云平臺虛擬機(jī)集群的負(fù)載均衡度可表示成：

其中，m為云平臺虛擬機(jī)數(shù)量。

可見，L越小，說明各虛擬機(jī)的負(fù)載波動越小，負(fù)載均衡性越好。

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

結(jié)合式(3)、式(4)，歸一化處理后建立以下適應(yīng)度函數(shù)：

其中，Tmax，Tmin分別為子任務(wù)總執(zhí)行時間的最大值與最小值，Lmax，Lmin分別為虛擬機(jī)集群負(fù)載均衡度的最大值與最小值；α為執(zhí)行時間權(quán)重，β為負(fù)載均衡度權(quán)重，且滿足α+β=1，這里取α=0.75，β=0.25。當(dāng)Fitness全局最大值時，云平臺同時具有較短任務(wù)執(zhí)行時間和較小負(fù)載均衡度。

3 云仿真任務(wù)調(diào)度及遷移流程

調(diào)度及遷移步驟如下：

Step1：周期采集每個虛擬機(jī)上CPU、內(nèi)存及網(wǎng)絡(luò)帶寬的占用率。

Step2：利用CBPSO算法計算當(dāng)前各虛擬機(jī)的負(fù)載度和適應(yīng)度，云平臺虛擬機(jī)集群總的負(fù)載均衡度、最大適應(yīng)度、最小適應(yīng)度。

Step3：當(dāng)負(fù)載均衡度超出設(shè)定閥值時，將適應(yīng)度最小虛擬機(jī)上的子任務(wù)遷移到適應(yīng)度最大的虛擬機(jī)上。

Step4：當(dāng)仿真子任務(wù)遷移完成后，重新計算當(dāng)前云平臺虛擬機(jī)集群總的負(fù)載均衡度。若負(fù)載均衡度未超出設(shè)定閥值，則證明調(diào)度成功，在下一個信息采集周期重復(fù)上述過程；若負(fù)載均衡度超出閥值，返回Step3。

4 云仿真任務(wù)調(diào)度算法設(shè)計

求解子任務(wù)與虛擬機(jī)最優(yōu)的組合方式即為：在離散二進(jìn)制粒子群中，利用CBPSO算法搜索使適應(yīng)度函數(shù)Fitness達(dá)到最大值的全局最優(yōu)位置向量Pg：

其中，xr,j=1，rj代表與任務(wù)j匹配的虛擬機(jī)，n為仿真子任務(wù)數(shù)量。

4.1 位置及速度的更新

在BPSO中，粒子位置更新就是位置向量xij在“0”和“1”之間的轉(zhuǎn)換，速度vij的大小代表xij下一步轉(zhuǎn)變?yōu)椤?”的概率[5]。為了使vij代表粒子的位置轉(zhuǎn)變概率，引入限制函數(shù)sig，使速度vij位于（0,1）之間[5]，其公式為式(6)。

其中，vij∈（0，1）。

粒子的位置與速度更新公式為：

Step 3：根據(jù)式(5)計算每個粒子的個體適應(yīng)度fi，進(jìn)而確定種群個體的歷史極值位置Pi和全局最優(yōu)位置Pg。

Step 4：按式(6)～式(8)迭代更新粒子位置、速度。計算新一代粒子的適應(yīng)度，更新Pi和Pg。

Step 5：依據(jù)式(11)求出當(dāng)前種群的適應(yīng)度方差σ2，若σ2小于閥值（設(shè)閥值為0.1），即認(rèn)定當(dāng)前粒子群收斂到全局最優(yōu)解或陷入局部極小解，轉(zhuǎn)Step 6。

其中：k為迭代次數(shù)，pij為粒子個體局部最優(yōu)位置，pgj為種群全局最優(yōu)位置，c1和c2為學(xué)習(xí)因子，rand( )為[0,1]之間的隨機(jī)數(shù)。

通過式(6)、式(7)可以看出：在迭代初期，粒子的速度較大，粒子位置編碼以大概率向“1”轉(zhuǎn)變，BPSO算法在種群內(nèi)快速搜索；在迭代后期，當(dāng)多數(shù)粒子位置編碼轉(zhuǎn)變?yōu)椤?”后，粒子位置的轉(zhuǎn)變概率不斷減小；當(dāng)算法搜索到最優(yōu)位置向量pg時，轉(zhuǎn)變概率為“0”，算法搜索結(jié)束。

4.2 混沌搜索策略

BPSO和其他智能算法一樣，同樣具有易于陷入局部極值的缺點(diǎn)。為避免BPSO算法過早收斂于局部最優(yōu)值，出現(xiàn)早熟現(xiàn)象，將BPSO算法與Logistic混沌算法結(jié)合，利用Logistic混沌映射初始化種群中粒子的位置和速度，使粒子隨機(jī)、均勻的散布到解空間；一旦BPSO算法陷入局部極小值，利用Logistic混沌映射在局部極小值附近進(jìn)行局部擾動，使算法快速逃離局部極值。Logisti映射公式如下[6]：

其中：μ為混沌映射因子，μ=4。

加入Logistic混沌搜索的BPSO算法流程如下：

Step 1：初始化粒子群參數(shù)，種群規(guī)模Q，維度n，學(xué)習(xí)算子c1、c2，最大迭代次數(shù)Zmax等。

Step 2：隨機(jī)初始化種群，設(shè)定n維初始化位置序列X1=[x12，x11，…，x1n]，x1i∈[0，1]，n維初始化速度序列V1=[v12，v11，…，v1n]，v1i∈[0，1]；利用Logisti映射公式(9)對序列X1、V1迭代k-1次得到位置序列Xk=[xk2，xk1，…，xkn]，xki∈[0，1]速度序列Vk=[vk2，vk1，…，vkn]，vki∈[0，1]。

由于BPSO中，粒子位置只能為0或1，通過式(10)將Xk轉(zhuǎn)換成二進(jìn)制序列

其中：fi為粒子適應(yīng)度值，為當(dāng)前粒子群適應(yīng)度的平均值，Q為種群規(guī)模 。

Step 6：如果算法迭代次數(shù)達(dá)到Zmax，尋優(yōu)結(jié)束，返回全局最優(yōu)解位置Pg及適應(yīng)度值Fitness，否則跳至Step 7。

Step 7：選取20%Q個適應(yīng)度值最高的粒子，按照Step 2的方法執(zhí)行局部混沌擾動更新Zmax，重新執(zhí)行Step 1～6。

5 仿真實(shí)驗(yàn)

本文在云仿真軟件CloudSim上進(jìn)行仿真實(shí)驗(yàn)，在相同的實(shí)驗(yàn)環(huán)境下對CBPSO、BPSO和CloudSim自帶的貪心算法進(jìn)行仿真對比。分析不同算法對任務(wù)總執(zhí)行時間、平均任務(wù)響應(yīng)時間、負(fù)載均衡度的影響。實(shí)驗(yàn)中，設(shè)定最大迭代次數(shù)Zmax=200，總?cè)阂?guī)模Q=100，學(xué)習(xí)因子c1=c2=2，各虛擬機(jī)和仿真子任務(wù)的配置信息如表1～表2所示。

表1 虛擬機(jī)配置參數(shù)

表2 仿真子任務(wù)配置參數(shù)

5.1 CBPSO與BPSO收斂速度對比

圖1為CBPSO和BPSO的適應(yīng)度收斂曲線。可見，CBPSO收斂速度更快，全局尋優(yōu)能力更強(qiáng)。BPSO迭代116次后陷入局部極值。

圖1 適應(yīng)度收斂曲線

5.2 任務(wù)總執(zhí)行時間、平均任務(wù)響應(yīng)時間

任務(wù)總執(zhí)行時間代表所有子任務(wù)執(zhí)行完成所使用的時間。平均任務(wù)響應(yīng)時間表示從所有子任務(wù)到達(dá)虛擬機(jī)至子任務(wù)在虛擬機(jī)上執(zhí)行完成并提交給用戶所用的平均時間。三種算法的任務(wù)執(zhí)行時間對比如圖2所示，平均任務(wù)響應(yīng)時間對比如圖3所示。

圖2 任務(wù)總執(zhí)行時間

圖3 平均任務(wù)響應(yīng)時間

圖2、圖3表明，CBPSO的任務(wù)總執(zhí)行時間和平均任務(wù)響應(yīng)時間比其他兩種算法都短，系統(tǒng)的運(yùn)行效率更高。

5.3 負(fù)載度均衡度

三種算法的負(fù)載均衡度對比如圖4所示。

圖4 負(fù)載均衡度

從圖4可以看出，貪婪算法的負(fù)載均衡度最大，且波動性比較大。BPSO算法下，云仿真平臺的平均負(fù)載均衡度為0.278。CBPSO算法下，云仿真平臺的平均負(fù)載均衡度為0.212，說明此算法下，虛擬機(jī)集群負(fù)載均衡性最好。

6 結(jié)論

仿真實(shí)驗(yàn)證明，基于CBPSO算法的云仿真任務(wù)調(diào)度策略在任務(wù)總執(zhí)行時間、平均任務(wù)響應(yīng)時間、負(fù)載均衡度方面的性能指標(biāo)都高于BPSO和貪心算法。同時也證明混沌算法可彌補(bǔ)BPSO易于陷入局部極值的不足。