基于服務(wù)質(zhì)量的虛擬化云資源動(dòng)態(tài)分配算法?

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

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

1 引言

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

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

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

2 服務(wù)質(zhì)量數(shù)學(xué)模型

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

設(shè)任務(wù)集合T={t1,t2,…,tn}，表示當(dāng)前有n個(gè)等待處理的任務(wù)在任務(wù)隊(duì)列中。云資源集合R={r1,r2,…,rm}，表示當(dāng)前有m個(gè)有效資源在資源池內(nèi)，其中資源是云計(jì)算中處理任務(wù)的基礎(chǔ)運(yùn)算單位。

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

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

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

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

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

式（3）中，TSij表示任務(wù)ti對(duì)資源rj的期望安全級(jí)別，Sij表示資源rj提供給任務(wù)ti的實(shí)際安全級(jí)別，Smax表示任務(wù)的最高安全級(jí)別。

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

式（4）中，TRij表示任務(wù)ti對(duì)資源rj的期望可靠性，SRij表示該資源rj提供給任務(wù)ti的實(shí)際可靠性。

服務(wù)質(zhì)量目標(biāo)函數(shù)如式（5）所示：

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

3 服務(wù)質(zhì)量約束的遺傳-蟻群資源分配算法

3.1 服務(wù)質(zhì)量約束的遺傳-蟻群算法基本思想

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

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

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

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

3.2 遺傳算子全局快速搜索

3.2.1 染色體編碼

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

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

適應(yīng)度主要用來評(píng)估群體中個(gè)體的質(zhì)量，本文選擇服務(wù)質(zhì)量目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)。服務(wù)質(zhì)量目標(biāo)函數(shù)的四個(gè)指標(biāo)系數(shù)滿足λ1+λ2+λ3+λ4=1，可根據(jù)用戶需要設(shè)置相應(yīng)的權(quán)重。

3.2.3 選擇、交叉和變異操作

選擇操作使用輪盤賭方式生成選擇算子，選擇概率通過任務(wù)調(diào)度適應(yīng)度值占所有任務(wù)適應(yīng)度值的比值進(jìn)行計(jì)算。

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

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

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

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

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

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

3.4 蟻群算子精確求解

3.4.1 初始化信息素

3.4.2 選擇操作

在t時(shí)刻，可以將資源j分配給任務(wù)i的概率表示為

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

3.4.3 信息素更新

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

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

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

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

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

4 仿真實(shí)驗(yàn)與分析

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

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

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

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

4.2 結(jié)果分析

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

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

圖2 資源負(fù)載對(duì)比圖

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

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

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

5 結(jié)語

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