金 鵬

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

0 引言

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

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

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

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

1 負載均衡調度原理

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

2 負載均衡調度模型

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

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

設當前云仿真平臺中，仿真子任務Wj的長度為lengthi，虛擬機VMi的CPU運行速度為mipsi，則Wj在VMi上的執(zhí)行時間timeij為：

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

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

2.2 虛擬機集群負載均衡度

本文將虛擬機集群總體負載度的標準差作為虛擬機集群的負載均衡度。

設當前虛擬機VMi所能提供配置資源：

其中，mipsi為VMi的CPU處理速度；memi為VMi的內存大小；bwi為VMi網絡帶寬。

設當前VMi上的子任務所占用的配置資源：

則當前虛擬機VMi的負載度表示為：

其中，μ1+μ2+μ3=1，μ1、μ2、μ3分別為虛擬機VMi的CPU權重、內存權重、網絡帶寬權重，本文取μ1=0.6，μ2=0.3，μ3=0.1。

當前云平臺虛擬機集群的負載均衡度可表示成：

其中，m為云平臺虛擬機數量。

可見，L越小，說明各虛擬機的負載波動越小，負載均衡性越好。

2.3 適應度函數

結合式(3)、式(4)，歸一化處理后建立以下適應度函數：

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

3 云仿真任務調度及遷移流程

調度及遷移步驟如下：

Step1：周期采集每個虛擬機上CPU、內存及網絡帶寬的占用率。

Step2：利用CBPSO算法計算當前各虛擬機的負載度和適應度，云平臺虛擬機集群總的負載均衡度、最大適應度、最小適應度。

Step3：當負載均衡度超出設定閥值時，將適應度最小虛擬機上的子任務遷移到適應度最大的虛擬機上。

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

4 云仿真任務調度算法設計

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

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

4.1 位置及速度的更新

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

其中，vij∈（0，1）。

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

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

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

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

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

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

4.2 混沌搜索策略

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

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

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

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

Step 2：隨機初始化種群，設定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轉換成二進制序列

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

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

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

5 仿真實驗

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

表1 虛擬機配置參數

表2 仿真子任務配置參數

5.1 CBPSO與BPSO收斂速度對比

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

圖1 適應度收斂曲線

5.2 任務總執(zhí)行時間、平均任務響應時間

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

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

圖3 平均任務響應時間

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

5.3 負載度均衡度

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

圖4 負載均衡度

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

6 結論

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