李凱鋒 胡 泓 吳海燕 賀莉娜 胡 宇

（1.南瑞集團公司（國網(wǎng)電力科學研究院） 南京 211000）（2.國電南瑞科技股份有限公司 南京 211106）（3.北京市軌道交通運營管理有限公司 北京 100068）

1 引言

隨著互聯(lián)網(wǎng)和信息化技術的不斷進步，越來越多的應用由于其數(shù)據(jù)量指數(shù)級的增長，必須通過借助云資源來實現(xiàn)，云計算［1］的時代已經(jīng)來臨。云服務提供者通過將數(shù)據(jù)中心的多種基礎資源進行深度整合，實現(xiàn)對計算資源、網(wǎng)絡資源、存儲資源的虛擬化和統(tǒng)一化調度管理［2］，并通過調度中心為用戶申請的任務分配資源。

然而，云計算的動態(tài)特性決定了云資源分配時，既要滿足不同任務服務質量［3］（quality of service，QoS）的需求，還要增加云平臺的吞吐量，提高資源利用率。經(jīng)典的遺傳算法［4～7］、模擬退火算法［8～10］、蟻群算法［11～14］和粒子群算法［15～16］等云資源分配算法，主要將注意力集中在如何縮短任務的完成時間，而不注重任務的服務質量需求（包括時間、成本、安全性和可靠性等），這會導致用戶的滿意度降低。蟻群算法雖然可實現(xiàn)群體性的組合優(yōu)化，但由于初期信息素的平均分配，存在過多的盲目搜索行為，影響算法效率。

針對以上不足，本文提出了一種基于服務質量的云資源動態(tài)分配算法，根據(jù)用戶的時間、成本、安全性和可靠性四種服務質量需求建立數(shù)學模型，對云資源動態(tài)分配算法進行約束。將遺傳算法與蟻群算法相結合，利用遺傳算法更新信息素矩陣后，再使用動態(tài)融合策略獲得兩種算法的最優(yōu)融合時間，最后通過蟻群算法求出最優(yōu)解，優(yōu)化了虛擬資源負載，提高了用戶滿意度。

2 服務質量數(shù)學模型

虛擬化的云資源動態(tài)分配就是云服務提供者將計算資源按照用戶的需求分配給用戶的過程。進行虛擬云資源分配需要在符合用戶服務質量需求的前提下，將獨立的任務分配給有效的虛擬資源，讓虛擬資源被高效合理地利用。本文將用戶對服務質量的需求分為時間需求、成本需求、可靠性需求和安全性需求四個方面，并建立了服務質量數(shù)學模型。

設任務集合T={t1,t2,…,tn}，表示當前有n個等待處理的任務在任務隊列中。云資源集合R={r1,r2,…,rm}，表示當前有m個有效資源在資源池內，其中資源是云計算中處理任務的基礎運算單位。

時間歸屬函數(shù)TM(i,j)如式（1）所示：

式（1）中，RTij表示任務ti在資源rj中執(zhí)行的預期執(zhí)行時間，RT(i,j)表示任務ti在資源rj中執(zhí)行的實際執(zhí)行時間。

成本歸屬函數(shù)CM(i,j)如式（2）所示：

式（2）中，Cij表示任務ti在資源rj中生成的預期成本，C(i,j)表示任務ti在資源rj中生成的實際成本。

安全性歸屬函數(shù)SM(i,j)如式（3）所示：

式（3）中，TSij表示任務ti對資源rj的期望安全級別，Sij表示資源rj提供給任務ti的實際安全級別，Smax表示任務的最高安全級別。

可靠性歸屬函數(shù)RM(i,j)如式（4）所示：

式（4）中，TRij表示任務ti對資源rj的期望可靠性，SRij表示該資源rj提供給任務ti的實際可靠性。

服務質量目標函數(shù)如式（5）所示：

在（5）中，λ1、λ2、λ3、λ4分別表示服務質量目標函數(shù)中的時間，成本，安全性和可靠性權重。

3 服務質量約束的遺傳-蟻群資源分配算法

3.1 服務質量約束的遺傳-蟻群算法基本思想

由于遺傳算法的后期運算效率較低，易導致許多的重復迭代。而蟻群算法每條路徑在初始時期的信息素都相同，盲目性較高，浪費了大量搜索時間。因此本文考慮了用戶對服務質量的多種需求指標，將遺傳算法與蟻群算法相結合，提出了服務質量約束的遺傳-蟻群資源分配算法。此算法分為如下三部分：

1）利用遺傳算法的全局快速搜索能力，并將所獲得的全局搜索信息轉化成蟻群算法的初始信息素。

2）判斷遺傳算法和蟻群算法融合的正確時間。

3）利用蟻群算法的正反饋和高效收斂的特性，完成滿足服務質量條件的云資源最優(yōu)分配。

3.2 遺傳算子全局快速搜索

3.2.1 染色體編碼

本文將染色體的長度定義為任務的數(shù)量，并通過編碼處理任務。染色體內的基因值是與其位置相應任務所利用的資源數(shù)量。定義云環(huán)境中的初始系統(tǒng)規(guī)模是S，任務集內n個任務被隨機分發(fā)給m個空閑的資源，n表示染色體的長度，1 與m范圍內的隨機數(shù)則表示單個基因的值。

3.2.2 適應度函數(shù)

適應度主要用來評估群體中個體的質量，本文選擇服務質量目標函數(shù)的倒數(shù)作為適應度函數(shù)。服務質量目標函數(shù)的四個指標系數(shù)滿足λ1+λ2+λ3+λ4=1，可根據(jù)用戶需要設置相應的權重。

3.2.3 選擇、交叉和變異操作

選擇操作使用輪盤賭方式生成選擇算子，選擇概率通過任務調度適應度值占所有任務適應度值的比值進行計算。

使用戴維斯順序交叉法進行交叉操作，設常數(shù)Pc為交叉概率。變異操作則利用逆向變異法，設常數(shù)Pm為變異概率。

3.3 遺傳算法與蟻群算法的融合

遺傳算法和蟻群算法的融合非常困難，一般方法是把遺傳算法設成固定迭代運行，但是運算結束的太早或太晚都會影響算法的效率。因此本文使用動態(tài)的結合方式來保證蟻群算法和遺傳算法在最優(yōu)的時間點進行結合。

1）設置最小遺傳迭代次數(shù)Genemin和最大遺傳迭代次數(shù)Genemax。

2）計算子代群體在遺傳迭代過程中的進化速率，并設置子代種群的最小進化速率為Genemin-impro-ratio。

3）如果后代種群的連續(xù)迭代Genedie(Genemin≤Genedie≤Genemax) 的 進 化 速 率 小 于Genemin-impro-ratio，則可以證明遺傳算法優(yōu)化速度較低，那么系統(tǒng)就可終止遺傳算法流程并進入蟻群算法流程。

3.4 蟻群算子精確求解

3.4.1 初始化信息素

3.4.2 選擇操作

在t時刻，可以將資源j分配給任務i的概率表示為

在式（9）中，τj表示t時刻資源j上信息素的濃度。ηj表示資源的可見性，即啟發(fā)式信息。η=aP+bB，P表示CPU 的處理能力，B表示網(wǎng)絡帶寬，a和b分別表示處理能力和帶寬在資源可見性中的比例系數(shù)。α是信息素因子，體現(xiàn)運動軌跡的重要性；β是啟發(fā)式因子，體現(xiàn)期望值的重要性。

3.4.3 信息素更新

局部信息素更新：當螞蟻完成所有任務的資源分配時，將更新所有分配資源的信息素殘留量。假設τj(t)是t時刻上資源rj的信息素，那么在t+1 時刻，資源rj的信息素更新規(guī)則如下：

在式（10）中，1-ρ為信息素殘留因子，ρ表示信息素揮發(fā)因子(0<ρ<1)。?τ(t)可以從式（11）得到，其中L表示資源數(shù)量。

全局信息素更新：當全部的螞蟻都結束一次迭代時，根據(jù)式（5），可以在該次迭代中求解出全局最佳調度方案，并全局更新最佳調度方案中資源的信息素。

基于服務質量的遺傳-蟻群云資源分配算法流程如圖1所示。

圖1 遺傳-蟻群云資源分配算法流程圖

4 仿真實驗與分析

4.1 實驗仿真

為了測試本文設計的算法性能，選擇Cloudsim5.0.3 云仿真平臺對蟻群算法、遺傳算法、遺傳-蟻群算法進行了仿真和結果對比分析。在云仿真平臺Cloudsim5.0.3中配置云環(huán)境的初始條件，包括創(chuàng)建數(shù)據(jù)中心、初始化任務規(guī)模參數(shù)、配置輸入輸出數(shù)據(jù)文件大小及任務大小和創(chuàng)建虛擬機資源，包括CPU、帶寬和內存等。在DatacenterBroker 類中構造遺傳-蟻群算法、遺傳算法和蟻群算法三種算法。

設置服務質量目標函數(shù)權重：λ1=0.2 ，λ2=0.3，λ3=0.22，λ4=0.28。設置選擇參數(shù)的概率：α=0.7，β=0.3，ρ=0.4。表1 所示為遺傳蟻群算法相關仿真參數(shù)。

表1 遺傳-蟻群算法相關仿真參數(shù)

4.2 結果分析

本文的算法將用戶服務質量作為資源分配的約束函數(shù)，結合蟻群算法和遺傳算法的雙重優(yōu)勢，提高了求解的收斂速度。比較分析了遺傳算法、蟻群算法和服務質量約束的遺傳-蟻群算法，并實現(xiàn)了仿真示例。資源負載計算公式如下所示。

式（14）中，Loadj是資源j 的負載，Loadavg是負載的平均值。仿真結果分別如圖2和圖3所示。

圖2 資源負載對比圖

圖3 執(zhí)行時間比較

分析圖2 結果可發(fā)現(xiàn)，隨著任務數(shù)量的增加，三種算法資源的負載率也隨之增加。但是與遺傳算法和蟻群算法相比，基于服務質量的遺傳-蟻群算法的資源負載率變化較小，并且始終保持較低的水平。與遺傳算法和蟻群算法相比，基于服務質量的遺傳-蟻群算法的資源負載率分別提高了28%和24.1%。因此，基于服務質量的遺傳-蟻群算法的虛擬資源分配結果更加趨于高效合理，云平臺的負載均衡度也在不斷提高。

根據(jù)圖3 可發(fā)現(xiàn)，三種算法的任務數(shù)量與執(zhí)行時間之間都存在正相關的關系。當任務數(shù)量大于500 時，隨著任務數(shù)量的增加，三種算法的執(zhí)行時間都有所增加，可見任務數(shù)量的增加會影響算法執(zhí)行的效率。蟻群算法和遺傳算法的執(zhí)行時間都遠多于服務質量約束的遺傳-蟻群算法的執(zhí)行時間，并且執(zhí)行時間保持在較低水平。因此，不論是運算的時間效率還是尋找最佳解的效率，基于服務質量的遺傳-蟻群算法均超過單個的遺傳算法與蟻群算法。

5 結語

本文提出了一種基于服務質量的虛擬云資源動態(tài)分配算法，該算法考慮了多種服務質量指標，通過將遺傳算法和蟻群算法融合并將服務質量指標轉換為歸屬函數(shù)作為遺傳算法的適應度函數(shù)，求得的最優(yōu)解能夠滿足用戶的服務質量需求。在CloudSim云計算平臺進行的仿真結果表明，該算法在資源負載均衡角度和時間花費角度都好于單個遺傳算法與蟻群算法，在最大化云計算資源利用效率的同時，明顯提升了服務質量。