包長均

摘 要：近年來，云仿真技術(shù)作為一種新型網(wǎng)絡(luò)化建模與仿真模式受到廣泛關(guān)注，合理配置仿真資源已成為云仿真技術(shù)的核心問題之一。針對傳統(tǒng)仿真系統(tǒng)資源分配中存在的資源重用性低、部署難度大等問題，提出一種改進(jìn)遺傳算法來求解仿真模型與虛擬機之間最優(yōu)映射的算法。實驗結(jié)果表明，該算法是云仿真運行環(huán)境下的一種有效資源調(diào)度算法。

關(guān)鍵詞：云仿真；虛擬化；資源分配；遺傳算法

DOIDOI：10.11907/rjdk.1511009

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號文章編號：16727800（2015）009007105

0 引言

在分布式計算、并行計算和網(wǎng)格計算逐步發(fā)展成熟的基礎(chǔ)上，云計算應(yīng)運而生。 云計算的核心思想是將計算服務(wù)器、存儲服務(wù)器和寬帶等資源通過網(wǎng)絡(luò)連接，形成以“云”形式統(tǒng)一管理，用戶只需根據(jù)自身需求請求資源池資源，由云計算中心負(fù)責(zé)所有資源調(diào)度和管理，保證用戶能夠根據(jù)需要獲取計算力、存儲空間和各種軟件服務(wù)[1]。

李伯虎院士[2]通過引入“云計算”理念，首先提出構(gòu)建新網(wǎng)絡(luò)化建模與仿真平臺——“云仿真平臺”。云仿真平臺通過在虛擬機中部署仿真軟件、服務(wù)、模型等資源組件，為用戶仿真需求提供相應(yīng)的計算資源。類似于云計算服務(wù)模式，云仿真技術(shù)將仿真模型、仿真流程等資源接入到云計算環(huán)境中，通過仿真模型即服務(wù)或仿真流程即服務(wù)模式滿足用戶仿真需求[3]。

隨著云計算網(wǎng)絡(luò)的不斷增大和仿真用戶不斷增多，如何及時、高效對云仿真資源進(jìn)行調(diào)度，提高資源利用率，成為云仿真平臺研究的核心問題之一。本文探討基于遺傳算法的云仿真平臺資源服務(wù)調(diào)度技術(shù)。

云計算服務(wù)中的資源調(diào)度技術(shù)日漸成為學(xué)者關(guān)注的焦點。針對仿真資源最優(yōu)化問題，以往研究中提出了很多有價值解決方案。

文獻(xiàn)[4]提出了基于Shapley值的虛擬化資源分配策略，該理論的基礎(chǔ)是合作博弈論，該方法高效地實現(xiàn)了虛擬化資源分配。 針對資源分配中的利用率問題，文獻(xiàn)[5]提出了基于分類挖掘的網(wǎng)格資源分配算法，通過分類減少資源重新分配次數(shù)，提高資源利用效率。 Prodan等[6]

提出了基于連續(xù)雙向拍賣機制的資源調(diào)度方法，該方法同時兼顧了用戶和服務(wù)提供商的雙方利益；

Martino[7]介紹了一種基于遺傳算法的網(wǎng)格資源調(diào)度算法，在花費一定能耗代價后，能盡可能提高網(wǎng)格資源使用率和負(fù)載均衡能力。文獻(xiàn)[8]針對云計算的編程模型框架，提出了一種具有雙適應(yīng)度遺傳算法，用于解決云計算模型中的資源分配最優(yōu)化問題，該算法不僅能得到總?cè)蝿?wù)完成時間較短的調(diào)度結(jié)果，而且此調(diào)度結(jié)果任務(wù)平均完成時間也較短。文獻(xiàn)[9]在充分考慮云計算環(huán)境動態(tài)異構(gòu)性和大規(guī)模任務(wù)處理特性的基礎(chǔ)上提出了一種改進(jìn)遺傳算法，并通過實驗驗證該算法能較好地適用于云計算環(huán)境中的大規(guī)模任務(wù)資源調(diào)度。 以上文獻(xiàn)提出的各種算法都可為本文提供借鑒意義，但是本文所提出問題情境、問題模型與上述研究均不所相同。

1 仿真運行環(huán)境動態(tài)構(gòu)建中遺傳算法應(yīng)用

1.1 問題提出

本文研究仿真運行環(huán)境構(gòu)建3層映射模型[2]，如圖1所示。構(gòu)建仿真運行環(huán)境，分步將仿真模型動態(tài)部署到虛擬機，將虛擬機部署到物理機，并分別實現(xiàn)N：1映射關(guān)系。 由于虛擬機與物理機兩者之間的映射過程（第二步）與仿真模型和虛擬機兩者之間的映射過程（第一步）基本相同，只是獲取虛擬機與物理機最優(yōu)映射約束條件略有不同，因此本文對第二步不作討論，只探討仿真模型與虛擬機之間的映射最優(yōu)化問題。

針對仿真模型與虛擬機之間最優(yōu)化映射問題，關(guān)鍵是如何將與仿真任務(wù)有關(guān)的仿真模型映射到不等量虛擬機中，以保證提供的運行環(huán)境能滿足仿真模型的解算和通訊需求，并且使仿真任務(wù)執(zhí)行效率達(dá)到最優(yōu)。

圖1 仿真運行環(huán)境的三層構(gòu)建模型

1.2 問題數(shù)學(xué)模型及形式化定義

為方便研究，本文將仿真模型性能需求和虛擬機提供性能配置折算為計算性能和通信性能[1]，并分別用Wworkload和Wcom表示。 計算性能由節(jié)點計算能力和內(nèi)存大小決定，而通信性能受限于網(wǎng)絡(luò)帶寬和網(wǎng)絡(luò)延遲。如式（1）所示：

根據(jù)仿真模型與虛擬機數(shù)量的大小關(guān)系又有不同映射：（1）若仿真模型數(shù)量小于或等于虛擬機數(shù)量，則在給虛擬機分配仿真模型時，將一個虛擬機上所有資源都占滿再去分配其它虛擬機，直到將所有滿足其計算需求和通信需求的仿真任務(wù)分配完畢，這樣得到的映射關(guān)系使多個虛擬機上是沒有仿真模型，通過關(guān)閉沒有仿真任務(wù)的虛擬機，從而達(dá)到節(jié)約能耗的目的。 該分配方式簡單易操作，本文不再贅述。 （2）若仿真模型數(shù)量大于虛擬機數(shù)量，則可以采用本節(jié)所介紹的映射模型，根據(jù)該方法得到的仿真模型到虛擬機間的映射，使得每臺虛擬機資源最大使用率最小，進(jìn)而使整個系統(tǒng)具有更大的靈活性。 下面介紹遺傳算法以實現(xiàn)本節(jié)中所提出的映射模型。

2 改進(jìn)遺傳算法求解最優(yōu)映射

遺傳算法（Genetic Algorithm， GA）是美國Michigan大學(xué)J.H.Holland教授于1975年受Darwin進(jìn)化論思想的啟發(fā)而提出。 其核心思想是生物進(jìn)化過程從簡單到復(fù)雜、從低級到高級，這本身就是穩(wěn)健適應(yīng)自然、適者生存的優(yōu)化過程。 相較于傳統(tǒng)窮舉法、微分法等優(yōu)化算法，遺傳算法不僅具有自組織、自適應(yīng)、自學(xué)習(xí)的特性，而且具有高魯棒性和廣泛適用性，能突破問題性質(zhì)限制，有效處理傳統(tǒng)優(yōu)化算法難以解決的復(fù)雜問題。 遺傳算法的主要優(yōu)勢在于是一種全局優(yōu)化算法。 搜索空間是問題解的結(jié)合，因而其搜索覆蓋面更大，范圍更廣，并能進(jìn)行多點并行搜索，使得遺傳算法能同時對多個解進(jìn)行處理、評估，搜索廣度和隨機性更優(yōu)，能避免陷入局部某個單峰最優(yōu)解，同時有利于較快收斂到全局最優(yōu)解。

2.1 染色體編碼方式

遺傳算法中的染色體編碼有很多種，如采用對任務(wù)執(zhí)行狀態(tài)的直接編碼和間接編碼。本文采用二進(jìn)制染色體編碼方式：M個仿真模型和N個虛擬機，M個仿真模型對應(yīng)M個表示單元，而每個表示單元由若干個二進(jìn)制位表示；每個表示單元的二進(jìn)制位數(shù)k由虛擬機數(shù)量N決定，即2k-1

2.2 初始種群生成

由上節(jié)可知，本文染色體表示仿真模型到虛擬機的映射。 每一個染色體是一種仿真模型與虛擬機的映射方式，且每一個染色體表示一個種群中的個體。 本文初始種群為隨機生成，初始種群數(shù)量設(shè)為Num。 算法是在這Num個種群中進(jìn)行選擇、交叉、變異，從而生成種群下一代。

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

遺傳算法是通過適應(yīng)度函數(shù)值進(jìn)行下一代的選擇，從而尋找問題最優(yōu)解。 因此，適應(yīng)度函數(shù)選取相當(dāng)重要，關(guān)系到算法收斂速度與所得解的優(yōu)劣。 根據(jù)問題模型，要想達(dá)到仿真模型與虛擬機之間的最優(yōu)映射，則必須滿足目標(biāo)函數(shù)，遺傳算法適應(yīng)度函數(shù)：

f（x）=max（v_cpu[x][j]，v_com[x][j][k]）∑Numi=1max（v_cpu[i][j]，v_com[i][j][k]）（6）

其中，二維數(shù)組v_cpu[x][j]表示x號染色體中j號虛擬機計算資源的使用率； 三維數(shù)組v_com[x][j][k]表示x號染色體上虛擬機j和虛擬機k上已經(jīng)部署的仿真模型之間通信量之和占虛擬機j與虛擬機k通信總量的比例。 適應(yīng)度函數(shù)值越小，映射性能越優(yōu)，越容易被選擇。

2.4 選擇、交叉、變異操作

2.4.1 選擇

在遺傳算法中需對種群中的個體按照一定比例進(jìn)行選擇，該比例由適應(yīng)度函數(shù)值決定，選擇的目的是將擁有更好基因的個體直接遺傳到下一代或?qū)⑼ㄟ^配對交叉產(chǎn)生的新個體遺傳到下一代。 本文使用輪盤賭選擇方式將優(yōu)秀個體挑選出來，通過適應(yīng)度值計算出每個個體的選擇概率：

ps（i）=1-f（i）∑Numj=1（1-f（j））（7）

其中，f（i）表示第i個染色體的適應(yīng)度值，ps（i）即為i號染色體被選擇的概率。

2.4.2 交叉

交叉是遺傳算法中最主要的搜索算子，其模仿自然界有性繁殖基因重組過程，將原有優(yōu)良基因遺傳給下一代個體，并生成包含更優(yōu)良基因結(jié)構(gòu)的新個體。 交叉是產(chǎn)生后代并區(qū)別于父代的主要方式，其以較大概率選擇兩個個體進(jìn)行基因位交換，交換后子代既保留了父代大部分基因，也具有自己新的基因特色，整個種群基因會發(fā)生相應(yīng)改變，從而保證種群向最優(yōu)化方向發(fā)展。

2.4.3 變異

所謂變異，是指將基因座上特定值進(jìn)行改變。當(dāng)遺傳算法通過交叉算子已經(jīng)接近最優(yōu)解時，利用變異可以加速種群向最優(yōu)解收斂。 變異算子pm通常在0.000 1～0.1間取值，適當(dāng)取值可保持種群多樣性，同時防止未成熟收斂現(xiàn)象。本文所述遺傳算法變異操作是對種群中的每個個體以pm的變異概率檢查其是否發(fā)生變異，對進(jìn)行變異的個體隨機選擇變異位并改變變異位的值。

2.5 算法終止條件

本文采用的終止條件包括進(jìn)化的代數(shù)G和閾值r，一旦算法執(zhí)行的進(jìn)化代數(shù)達(dá)到G次或在下一代所得到的δ（d）與上一代計算得到的δ（d）的差值小于r時，算法均終止。 此時得到的結(jié)果是最優(yōu)解或趨近于最優(yōu)解。最優(yōu)解種群中對應(yīng)的max（v_cpu[x][j]，v_com[x][j][k]）為最小的染色體，即為最優(yōu)映射。

2.6 模擬退火算法引入

模擬退火算法思想最先由Metropolis等于1953年提出，并在1983年被Kirkpatrick等成功引入組合優(yōu)化領(lǐng)域。 模擬退火算法可以看作一個物理模擬過程：從某個較高初始溫度出發(fā)，先將固體加熱至高溫狀態(tài)，此時固體分子間不斷發(fā)生碰撞，呈無序狀態(tài)，具有較高的內(nèi)能； 然后讓高溫固體慢慢冷卻，固體分子將隨著熱運動的逐漸減弱而恢復(fù)到穩(wěn)定、有序狀態(tài)。在這個過程中，固體內(nèi)部粒子在每個溫度下都能達(dá)到平衡態(tài)，最終在常溫時達(dá)到基態(tài)[10]。 模擬退火算法采用Metropolis接受準(zhǔn)則能避免過早達(dá)到局部最優(yōu)范圍，從而保證所求解的質(zhì)量。 該接受準(zhǔn)則是指當(dāng)固體處于較高溫度狀態(tài)時，接受新狀態(tài)可能性較大，而當(dāng)固體處于較低溫度狀態(tài)時，接受新狀態(tài)可能性隨之降低。最終，當(dāng)溫度趨于0時，任何使內(nèi)能小于0的新狀態(tài)都不能被接受。

經(jīng)典遺傳算法的早熟現(xiàn)象是指算法過早陷入局部最優(yōu)，很難跳出局部走向全局最優(yōu)。已有研究表明，由于群體規(guī)模限制，當(dāng)該種群進(jìn)化若干代后，具有較高平均適應(yīng)度的指數(shù)級增長模式將在種群中占有絕對優(yōu)勢，也就是在自然界優(yōu)勝劣汰中占據(jù)統(tǒng)治地位。 如果不加以調(diào)整控制，算法中的選擇、交叉、變異操作將逐漸因為種群高度一致性而失去作用，整個種群的模式種類將越來越單一，最終導(dǎo)致算法陷入局部最優(yōu)解[11]。 將模擬退火算法引入遺傳算法中，既能避免遺傳算法存在的“早熟”問題，大大降低遺傳算法陷入局部最優(yōu)解的可能性，又能增強算法全局收斂特性，提高算法收斂速度。

因此，首先采用遺傳算法框架進(jìn)行最優(yōu)化問題求解，再引入模擬退火算法優(yōu)化遺傳算法中選擇下一代種群的操作，根據(jù)Metropolis接受準(zhǔn)則以一定概率接受壞解，從而在進(jìn)化過程中保持種群多樣性，最終得到最優(yōu)解。

2.6.1 Metropolis接受準(zhǔn)則

設(shè)當(dāng)前狀態(tài)下溫度值為T，根據(jù)粒子當(dāng)前所處的相對位置，設(shè)固體初始狀態(tài)為i，對應(yīng)內(nèi)能為Ei；隨后隨機選取其中的某個粒子，按隨機產(chǎn)生的偏移向量使粒子發(fā)生偏移，設(shè)偏移后的狀態(tài)為j，此時內(nèi)能為Ej。 若Ejβ ，則接受該新狀態(tài)，否則拒絕改變狀態(tài)。 通過重復(fù)上述過程，系統(tǒng)能量將逐漸降低，最終達(dá)到平衡狀態(tài)。

2.6.2 模擬退火算法參數(shù)

（1）溫度控制初始值t0。該值選取不宜過大或過小。過大的選擇將導(dǎo)致退火算法收斂緩慢，失去可操作性；過小的選擇會導(dǎo)致退火算法陷入局部搜索。

（2）溫度控制終值tf。該值決定模擬退火算法終止條件，即溫度達(dá)到某個充分小的值表明算法收斂到某個近似解。本文采取判斷算法求解的近似性決定是否終止，若迭代若干次后得到的解沒有變化，說明算法解的質(zhì)量無法進(jìn)一步提高，從而宣告算法終止。

（3）溫度衰減函數(shù)f（tk） 。本文取一種常用的衰減函數(shù)f（tk）：tk+1=μtk，u∈[0.5，1）。

2.6.3 改進(jìn)遺傳算法流程

本文提出的SAGA算法（Simulated Annealing Genetic Algorithm）分兩個階段：在遺傳操作階段，利用選擇、交叉和變異過程對初始種群Gi 進(jìn)行遺傳操作，產(chǎn)生進(jìn)化后的種群i；在模擬退火操作階段，將種群i作為輸入，釆用模擬退火操作，通過Metropolis準(zhǔn)則對i中的個體進(jìn)行篩選，產(chǎn)生新一代種群Gi+1。具體操作步驟如下：Step 1：初始化種群。 根據(jù)仿真模型與虛擬機的數(shù)量采用隨機方式生成初始種群，初始種群規(guī)模記作Mg。 設(shè)定進(jìn)化迭代參數(shù)i為0；

Step 2：計算目標(biāo)函數(shù)與自適應(yīng)函數(shù)。首先計算當(dāng)前種群適應(yīng)度函數(shù)f（i）和最優(yōu)映射值δ（d）；

Step 3：終止條件判斷。 當(dāng)進(jìn)化代數(shù)達(dá)到預(yù)定最大進(jìn)化代數(shù)或在下一代所得到的δ（d）與上一代計算得到的δ（d）差值小于r時算法終止，輸出搜索結(jié)果，否則繼續(xù)執(zhí)行；

Step 4：選擇操作。 采用輪盤賭法對種群進(jìn)行選擇操作，根據(jù)式（7）得到的ps概率來選擇適應(yīng)性較強的個體，形成新群體，進(jìn)行下一步交叉操作；

Step 5：交叉操作。釆用交叉方法，從經(jīng)過選擇操作產(chǎn)生的群體中隨機選擇2個個體進(jìn)行交叉操作，產(chǎn)生2個新個體；

Step 6：變異操作。釆用變異操作方法對被選中個體進(jìn)行變異操作，將符合要求的新個體放入種群；

Step 7：在溫度ti下，計算遺傳操作后種群中每個個體的適應(yīng)度值；

Step 8：根據(jù)適應(yīng)度函數(shù)和Metropolis接受準(zhǔn)則，判斷是否接受當(dāng)前遺傳算法產(chǎn)生的新個體；

Step 9：更新進(jìn)化迭代計數(shù)i=i+l，轉(zhuǎn)到Step 2。

3 實驗測試

CloudSim是一款云計算仿真工具，是用于實現(xiàn)對云計算基礎(chǔ)設(shè)施和應(yīng)用服務(wù)進(jìn)行模擬的開源框架。 本文使用CloudSim中的DataCenterBroker方法實現(xiàn)算法調(diào)度策略。

3.1 實驗條件設(shè)定

算法參數(shù)設(shè)置如表1所示。本實驗中仿真模型數(shù)量取值為1k、2k、3k、4k、5k，逐漸增大。 虛擬機數(shù)量設(shè)為500。 仿真模型計算資源需求量取值范圍為[1，20]，數(shù)值越大表示對計算資源的需求越大。虛擬機可以提供的計算資源取值范圍為[100，300]。 設(shè)仿真模型間所需通信性能取值范圍為[1，20]，虛擬機間可用通信性能取值范圍為[100，300]。 限定任何一個虛擬機上面部署的仿真模型計算資源需求量之和都不能超過此虛擬機提供的計算資源。

3.2 與經(jīng)典算法對比

在相同實驗條件下，將本文提出的SAGA算法與經(jīng)典GA算法（遺傳算法）、RA算法（隨機分配算法）分別進(jìn)行比較。 實驗結(jié)果如圖2所示。

圖2 算法執(zhí)行時間對比

由圖2可知，隨著仿真模型數(shù)量的增加，染色體長度越長，染色體就越復(fù)雜，相應(yīng)的交叉、突變也越復(fù)雜，因此要得到最優(yōu)解或接近最優(yōu)解的部署，算法需要的運算時間越多。 當(dāng)僅有少量仿真模型時，傳統(tǒng)的GA算法和SAGA算法都能夠迅速收斂，執(zhí)行時間差別不大，而RA算法由于隨機性較大，花費時間稍多。 當(dāng)仿真模型數(shù)量較多時，傳統(tǒng)GA算法收斂代數(shù)急劇增加，搜索效率大大降低，而隨著任務(wù)量的增大，SAGA算法的優(yōu)勢越來越明顯，SAGA算法能保持群體多樣性，推動群體穩(wěn)定進(jìn)化，從而所需時間隨著仿真模型數(shù)量增加而變化更加平滑。 傳統(tǒng)RA算法隨著搜索空間越來越大，性能下降很明顯，可見RA并不適用于云環(huán)境下大規(guī)模仿真數(shù)據(jù)處理。

圖3顯示不同數(shù)量仿真模型算法分派資源最大占用率，該值越小則算法性能越優(yōu)。 總體而言，隨著仿真模型增多，3種算法計算資源最大占用率都在增大，RA算法由于采取完全隨機分配策略，在仿真模型不斷增多后表現(xiàn)最差，最后一組實驗資源利用率已近90%，負(fù)載提升空間不大。GA算法和SAGA算法都表現(xiàn)出能根據(jù)虛擬機運算能力合理分配資源特性，算法傾向于使計算能力強的虛擬機分配到更多任務(wù)。雖然傳統(tǒng)GA算法在問題規(guī)模較小時性能較好，但容易陷入局部最優(yōu)解，反而導(dǎo)致性能下降。本文提出SAGA算法能有效避免算法早熟，隨著資源利用率提升，能夠提供更好負(fù)載均衡效果。

圖3 算法資源最大占用率對比

4 結(jié)語

隨著大數(shù)據(jù)時代到來，傳統(tǒng)仿真技術(shù)越來越難以滿足日益復(fù)雜的用戶仿真需求，而云仿真技術(shù)采用云計算理念能夠很好地解決這一問題。 針對云仿真運行環(huán)境資源分配最優(yōu)化問題，本文提出了基于改進(jìn)遺傳算法的求解方法，該算法綜合考慮了計算性能、通信性能、機器負(fù)載等因素。 實驗證明，該算法在任務(wù)完成時間和負(fù)載均衡方面均表現(xiàn)出很強的優(yōu)勢，能較好地適用于云計算環(huán)境中大規(guī)模仿真任務(wù)資源調(diào)度。

參考文獻(xiàn)參考文獻(xiàn)：

[1] 劉鵬.云計算的定義和特點[EB/OL].http：//www.chinacloud.cn/show.aspx？cid=17&id=741.

[2] 李伯虎，柴旭東，侯寶存，等.一種基于云計算理念的網(wǎng)絡(luò)化建模與仿真平臺——”云仿真平臺”[J].系統(tǒng)仿真學(xué)報，2009，21（17）：52925299.

[3] 胡春生，許承東，張鵬飛，等.云計算環(huán)境下仿真模型資源虛擬化研究[J].華中科技大學(xué)學(xué)報，2012，40（1）：135140.

[4] 張小慶，李春林，錢瓊芬，等.基于合作博弈的虛擬化資源效用分配策略[J].計算機科學(xué)，2012，39（6）：5153.

[5] 劉林東.基于分類挖掘的網(wǎng)格資源分配研究[J].計算機應(yīng)用研究，2013，30（2）：371373.

[6] PRODAN R，WIECZOREK M，F(xiàn)ARD H M.Double auctionbased scheduling of scientific applications in distributed grid and cloud environments[J].Journal of Grid Computing，2011，9（4）：531548.

[7] DI MARTINO V，MILILOTTI M.Sub optimal scheduling in a grid using genetic algorithms[J].Parallel Computing，2004，30（5）：553565.

[8] 李建鋒，彭艦.云計算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法[J].計算機應(yīng)用，2011，31（1）：184186.

[9] 劉愉，趙志文.云計算環(huán)境中優(yōu)化遺傳算法的資源調(diào)度策略[J].北京師范大學(xué)學(xué)報：自然科學(xué)版，2012，48（4）：378383.

[10] 龐峰.模擬退火算法的原理及算法在優(yōu)化問題上的應(yīng)用[D].長春市：吉林大學(xué)，2006.

[11] 付旭輝，康玲.遺傳算法的早熟問題探究[J].華中科技大學(xué)學(xué)報：自然科學(xué)版，2003，31（7）：5354.

[12] ZHANG Y B，CHAI X D，HOU B C，et al.Research on virtual simulation resource modeling in cloud simulation[C].Proc.of the International Conference on Information Security and Artificial Intellignce，2010：394398.

責(zé)任編輯（責(zé)任編輯：陳福時）