馬焜，徐玲玉，沈曉萍，龔志城，藍(lán)建平，陳雙喜,4，錢(qián)鈞

云計(jì)算中基于Shapley值改進(jìn)遺傳算法的虛擬機(jī)調(diào)度模型

馬焜1,2，徐玲玉3，沈曉萍1,2，龔志城1,2，藍(lán)建平1,2，陳雙喜1,2,4，錢(qián)鈞5

（1. 嘉興職業(yè)技術(shù)學(xué)院，浙江 嘉興 314036；2. 嘉興市工業(yè)互聯(lián)網(wǎng)安全重點(diǎn)實(shí)驗(yàn)室，浙江 嘉興 314036；3. 嘉興南洋職業(yè)技術(shù)學(xué)院，浙江 嘉興 314031；4. 浙江大學(xué)，浙江 杭州 310058；5. 中國(guó)電信股份有限公司嘉興分公司，浙江 嘉興 314011）

云計(jì)算系統(tǒng)具有服務(wù)器規(guī)模大、用戶范圍廣的特點(diǎn)，但同時(shí)也消耗了大量的能源，導(dǎo)致云供應(yīng)商的高運(yùn)營(yíng)成本和高碳排放等問(wèn)題。云計(jì)算高度虛擬化，如何分配和管理其虛擬資源，從而保證高效的物理資源利用和能耗控制，是一個(gè)多參數(shù)博弈過(guò)程，同時(shí)也是該領(lǐng)域的一個(gè)研究熱點(diǎn)。提出了一種虛擬機(jī)調(diào)度模型及基于Shapley值的遺傳算法（SV-GA），可通過(guò)經(jīng)濟(jì)學(xué)概念Shapley值計(jì)算出參與工作的物理機(jī)貢獻(xiàn)值，并通過(guò)該貢獻(xiàn)值修正遺傳算法中變異步驟的概率參數(shù)，從而完成虛擬機(jī)調(diào)度的任務(wù)。實(shí)驗(yàn)結(jié)果表明，與Max-Min、LrMmt及DE算法相比，SV-GA在虛擬機(jī)調(diào)度過(guò)程中的遷移時(shí)間、次數(shù)、SLA違背率、能耗等多參數(shù)博弈中具有優(yōu)異的表現(xiàn)。

云計(jì)算；多參數(shù)博弈；虛擬機(jī)調(diào)度；Shapley值；遺傳算法

0 引言

云計(jì)算是在網(wǎng)格計(jì)算的基礎(chǔ)上發(fā)展起來(lái)的，是一種新型的業(yè)務(wù)計(jì)算服務(wù)模型，已成為IT領(lǐng)域的研究熱點(diǎn)。在云計(jì)算環(huán)境中，許多虛擬化的動(dòng)態(tài)計(jì)算資源可以通過(guò)網(wǎng)絡(luò)為用戶提供各種計(jì)算和數(shù)據(jù)存儲(chǔ)服務(wù)，以實(shí)現(xiàn)大型異構(gòu)資源的集成和共享，并為外部用戶提供統(tǒng)一的訪問(wèn)接口。云用戶只是通過(guò)網(wǎng)絡(luò)連接云計(jì)算系統(tǒng)環(huán)境，與此同時(shí)，用戶無(wú)須知道分配了哪些虛擬化的資源以及這些資源在哪里部署[1]。虛擬化是一種物理基礎(chǔ)設(shè)施抽象技術(shù)，可為高級(jí)應(yīng)用程序提供虛擬機(jī)（virtual machine，VM）的虛擬化資源[2]。在云計(jì)算中，虛擬化提供了從服務(wù)器集群聚合計(jì)算資源并根據(jù)需要將VM分配到目標(biāo)物理機(jī)（physical machine，PM）的能力。但是，隨著云計(jì)算的發(fā)展和技術(shù)的成熟，云數(shù)據(jù)中心的數(shù)量和規(guī)模不斷擴(kuò)大，云數(shù)據(jù)中心的高能耗問(wèn)題越來(lái)越突出[3]。據(jù)報(bào)道，截至2019年，全球云用戶數(shù)量高達(dá)20億，其中，超過(guò)86%的IT工作負(fù)載在云數(shù)據(jù)中心執(zhí)行[4]。對(duì)云服務(wù)的日益依賴提高了能耗、服務(wù)等級(jí)協(xié)定（service level agreement，SLA）違背率和CO2氣體排放等。一項(xiàng)調(diào)查表明，數(shù)據(jù)中心的信息通信技術(shù)（information and communications technology，ICT）所消耗的電量占據(jù)全球的1.3%[5]，預(yù)計(jì)未來(lái)該項(xiàng)能耗占比將增長(zhǎng)到8%[6]。這意味著如何調(diào)度虛擬機(jī)資源以確保云數(shù)據(jù)中心的總體負(fù)載平衡、能耗及SLA違背率等指標(biāo)，仍然是當(dāng)前的研究熱點(diǎn)。

目前，研究人員在資源調(diào)度和管理領(lǐng)域做了很多研究工作，不同物理資源的性能和定價(jià)均不相同，虛擬資源的分配和請(qǐng)求也互有差異，因此，在虛擬機(jī)和物理資源之間尋找最佳解決方案顯然是一個(gè)NP問(wèn)題?；诖耍S多啟發(fā)式算法被相繼提出并用于求解上述最優(yōu)匹配問(wèn)題的近似解。在虛擬機(jī)調(diào)度等許多任務(wù)調(diào)度策略中，Min-Min和Max-Min方法[7-8]通常用作評(píng)估其他調(diào)度策略性能的基準(zhǔn)。虛擬機(jī)遷移的過(guò)程中有大量不同的參數(shù)指標(biāo)，根據(jù)用戶目標(biāo)的不同，不同指標(biāo)的博弈權(quán)重也大相徑庭，文獻(xiàn)[9]研究了虛擬功能服務(wù)鏈中多虛擬機(jī)動(dòng)態(tài)遷移對(duì)虛擬功能的影響，用統(tǒng)計(jì)和博弈論的方法設(shè)計(jì)了服務(wù)鏈動(dòng)態(tài)調(diào)整算法，以遷移時(shí)間和遷移代價(jià)為指標(biāo)，并依此給出服務(wù)鏈開(kāi)銷函數(shù)。然后基于可遷移概率和博弈信息論方法給出最小開(kāi)銷算法和最小遷移步驟優(yōu)化算法。Ajmera等[10]提出了一種基于人工免疫系統(tǒng)的基于改進(jìn)克隆選擇算法的虛擬機(jī)調(diào)度（virtual machine scheduling using modified clonal selection algorithm，VMS-MCSA）算法，以實(shí)現(xiàn)虛擬機(jī)的能量高效調(diào)度。對(duì)經(jīng)典的克隆選擇算法（clone select algorithm，CSA）的算子進(jìn)行改進(jìn)，使其能夠解決離散優(yōu)化動(dòng)態(tài)虛擬機(jī)調(diào)度問(wèn)題，并提出了隨機(jī)變異算子，該算子在每個(gè)調(diào)度間隔重新調(diào)度虛擬機(jī)，以最小的虛擬機(jī)遷移量處理工作負(fù)載的動(dòng)態(tài)性。針對(duì)SLA和能耗的平衡性，Garg等[11]提出了一種以簡(jiǎn)化SLA為代價(jià)來(lái)提高能效的方法，通過(guò)負(fù)載感知的三齒輪閾值（load aware three-gear THReshold，LATHR）和改進(jìn)的最佳擬合減少（modified best-fit descending）算法，在提高服務(wù)質(zhì)量的同時(shí)，最大限度地降低總能耗。Perumal等[12]考慮到內(nèi)存利用率，提出了一種基于最優(yōu)虛擬機(jī)放置（optimal virtual machine placement，OVMP）的算法。該算法首先查找內(nèi)存利用率低于設(shè)置的閾值的所有計(jì)算節(jié)點(diǎn)，然后集成在這些計(jì)算節(jié)點(diǎn)上運(yùn)行的虛擬機(jī)，并關(guān)閉空閑的計(jì)算節(jié)點(diǎn)，從而實(shí)現(xiàn)物理資源上的內(nèi)存利用率優(yōu)化。Beloglazov等[13]考慮了在現(xiàn)代云計(jì)算框架中跨數(shù)據(jù)中心平衡CPU資源的重要性，提出了一種虛擬機(jī)遷移算法，該算法能通過(guò)平衡數(shù)據(jù)中心CPU資源降低能耗。Jalali等[14]提出了一種新的智能VM遷移方法CLANFIC，該方法利用了改進(jìn)的基于細(xì)胞學(xué)習(xí)自動(dòng)機(jī)的進(jìn)化計(jì)算（cellular learning automata based- evolutionary computing，CLA-EC）和神經(jīng)模糊技術(shù)，最后通過(guò)利用優(yōu)化的布局方法和基于未來(lái)資源需求預(yù)測(cè)的延遲遷移時(shí)間，最小化VM遷移次數(shù)和優(yōu)化能耗。針對(duì)虛擬機(jī)調(diào)度的多種策略的對(duì)比，Ajayi等[15]提出了一種基于遺傳算法的虛擬機(jī)調(diào)度的策略，同時(shí)將該算法和其他4種算法進(jìn)行了對(duì)比，包括最佳擬合下降（best-fit descending）算法、首次擬合下降（first-fit descending）算法、二進(jìn)制搜索最佳匹配（binary-search best-fit）法及穩(wěn)定室友分配（stable roommate allocation）法。

1 基于Shapley改進(jìn)遺傳算法的虛擬機(jī)調(diào)度模型

1.1 虛擬機(jī)調(diào)度工作環(huán)境

云計(jì)算中，虛擬化技術(shù)的一個(gè)核心價(jià)值體現(xiàn)是作為用戶和云供應(yīng)商物理資源之間數(shù)據(jù)和信息交互的橋梁，因此云計(jì)算的結(jié)構(gòu)通?？梢杂?個(gè)層次表述：用戶層、虛擬層、物理層。云計(jì)算層次結(jié)構(gòu)如圖1所示。

圖1 云計(jì)算層次結(jié)構(gòu)

根據(jù)層次的不同，云計(jì)算提供的服務(wù)方式可分為軟件即服務(wù)（software as a service，SaaS）、平臺(tái)即服務(wù)（platform as a service，PaaS）和基礎(chǔ)設(shè)施即服務(wù)（infrastructure as a service，IaaS）?；谝陨?種層次的服務(wù)，云計(jì)算不僅實(shí)現(xiàn)了信息應(yīng)用服務(wù)的整體定制，還實(shí)現(xiàn)了底層邏輯基礎(chǔ)資源、基礎(chǔ)軟件和應(yīng)用的整合，做到“按需即用，隨需應(yīng)變”，從而顛覆性地改變了傳統(tǒng)IT服務(wù)商業(yè)模式。

本文的主要研究?jī)?nèi)容是虛擬層和物理層之間的資源調(diào)度問(wèn)題。以基于Shapley值的遺傳算法（SV-GA）為核心對(duì)虛擬機(jī)調(diào)度進(jìn)行建模，目標(biāo)在于盡可能合理化地分配物理機(jī)之間的虛擬資源。

1.2 SV-GA虛擬機(jī)調(diào)度模型

如上文所說(shuō)，云計(jì)算技術(shù)為用戶分配可用資源有多種模式。這些模式可以被視為對(duì)云數(shù)據(jù)中心資源池的基于服務(wù)的訪問(wèn)。這些訪問(wèn)的具體實(shí)現(xiàn)形式是使用虛擬機(jī)技術(shù)將云用戶的請(qǐng)求封裝到虛擬機(jī)中進(jìn)行分配和訪問(wèn)。虛擬機(jī)調(diào)度模型的體系結(jié)構(gòu)如圖2所示。

圖2 虛擬機(jī)調(diào)度模型的體系結(jié)構(gòu)

步驟1 虛擬機(jī)提交請(qǐng)求同時(shí)獲取物理資源數(shù)據(jù)，虛擬層發(fā)出要被分配的虛擬機(jī)的請(qǐng)求到資源調(diào)度器，包括虛擬機(jī)的具體參數(shù)，如CPU、帶寬、內(nèi)存等，同時(shí)獲取各臺(tái)物理機(jī)的數(shù)據(jù)。注意，物理機(jī)的數(shù)據(jù)不僅包括對(duì)應(yīng)虛擬機(jī)的參數(shù)，還包括能耗、熱節(jié)點(diǎn)閾值等。

步驟2 處理請(qǐng)求，資源調(diào)度器將虛擬機(jī)和物理機(jī)的相關(guān)參數(shù)整合，使用SV-GA進(jìn)行計(jì)算并得到分配結(jié)果。

步驟3 返回該算法生成的調(diào)度結(jié)果。

步驟4 將虛擬機(jī)分配到物理機(jī)，資源調(diào)度器根據(jù)返回的信息，把虛擬機(jī)調(diào)度到對(duì)應(yīng)的物理機(jī)上，完成虛擬機(jī)的調(diào)度。

2 基于Shapley值改進(jìn)的遺傳算法

2.1 Shapley值在物理機(jī)貢獻(xiàn)中的應(yīng)用

然而在真實(shí)的云計(jì)算環(huán)境下，物理機(jī)個(gè)體的配置存在巨大的差別，從存儲(chǔ)空間到計(jì)算能力，從網(wǎng)絡(luò)帶寬到內(nèi)存大小等，如何根據(jù)用戶多樣化的動(dòng)態(tài)需求來(lái)綜合性評(píng)估每一臺(tái)物理機(jī)所能貢獻(xiàn)的價(jià)值，是一個(gè)非常值得深入研究的問(wèn)題。本文提出引入經(jīng)濟(jì)學(xué)概念——Shapley值[16]計(jì)算物理機(jī)群中各臺(tái)物理機(jī)所能貢獻(xiàn)的價(jià)值。換言之，根據(jù)參與資源提供的物理機(jī)的不同，可以組成多種不同的集合，物理機(jī)∈的貢獻(xiàn)取決于該物理機(jī)可以為整個(gè)調(diào)度模型中的物理機(jī)集合提供多少價(jià)值，可以用(,)來(lái)表示。

物理機(jī)的邊際貢獻(xiàn)（contribution margin，CM）定義如下。

CM()=()?(/{}) （1）

其中，CM()表示物理機(jī)對(duì)集合的邊際貢獻(xiàn)，而/{}表示除物理機(jī)外的所有物理機(jī)形成的集合。Shapley值通過(guò)物理機(jī)的邊際貢獻(xiàn)衡量該物理機(jī)對(duì)集合的改善程度。因此在集合(,)中，可以計(jì)算出每臺(tái)物理機(jī)對(duì)整個(gè)集合的貢獻(xiàn)程度。

基于邊際貢獻(xiàn)，Shapley值定義如下。

在聯(lián)合博弈(P,PM)中，PM表示目標(biāo)總物理機(jī)集合，P表示包含物理機(jī)的各種子集，則物理機(jī)的貢獻(xiàn)值為：

其中，(P)=(|P|?1)!·(?|P|)!/!，表示物理機(jī)形成一個(gè)排列組合的可能性，表示集合PM中物理機(jī)排列組合的數(shù)量，表示一種排列組合下的PM的貢獻(xiàn)值。(|P|?1)!表示物理機(jī)出現(xiàn)之前的排列組合的可能性，(?|P|)!表示出現(xiàn)物理機(jī)之后的排列組合的可能性。

2.2 云計(jì)算拓?fù)渲形锢頇C(jī)的貢獻(xiàn)值計(jì)算

盡管Shapley值的提出為PM的貢獻(xiàn)值計(jì)算提供了一個(gè)強(qiáng)有力的支持，但其精確值的直接計(jì)算同樣是一個(gè)NP問(wèn)題。文獻(xiàn)[17]提出了對(duì)拓?fù)渚W(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的Shapley值的計(jì)算方法，其計(jì)算參數(shù)包括該節(jié)點(diǎn)擁有的相鄰節(jié)點(diǎn)數(shù)量（即邊的數(shù)量）和每條邊的權(quán)重。

在本文所提云計(jì)算中VM到PM的計(jì)算拓?fù)渚W(wǎng)絡(luò)中，PM的單一作用就是被分配VM，并且均可被分配任意VM，因此每臺(tái)PM的邊數(shù)可視為相同，只需要考慮參數(shù)即可。同時(shí)可根據(jù)VM對(duì)不同屬性的需求，動(dòng)態(tài)調(diào)整其權(quán)重的比例，即物理機(jī)的貢獻(xiàn)值deg(pm)，本文定義物理機(jī)有3種屬性：遷移時(shí)間貢獻(xiàn)值degET(pm)、SLA違背率貢獻(xiàn)值degSLA(pm)和遷移能耗貢獻(xiàn)值degEC(pm)，物理機(jī)貢獻(xiàn)值計(jì)算拓?fù)淙鐖D3所示。

圖3 物理機(jī)貢獻(xiàn)值計(jì)算拓?fù)?/p>

以PM1為例，首先獲取PM1和VM1的參數(shù)數(shù)據(jù)，如網(wǎng)絡(luò)帶寬、內(nèi)存，即可通過(guò)簡(jiǎn)單計(jì)算得到VM1分配給PM1的遷移時(shí)間權(quán)重et11，其中帶寬和et11成正比，內(nèi)存和et11成反比。

然后，通過(guò)對(duì)比將VM1分配到PM1前后，PM1負(fù)載是否處于低/高閾值[11]區(qū)間來(lái)判斷其SLA違背率權(quán)重sla11。

情況1：VM1將PM1從處于低閾值區(qū)間變成普通節(jié)點(diǎn)，則sla11= 1。

情況2：VM1將PM1從普通節(jié)點(diǎn)變成熱節(jié)點(diǎn)（處于高閾值區(qū)間），則sla11= ?1。

情況3：VM1對(duì)PM1無(wú)影響（PM1是普通節(jié)點(diǎn)），則sla11= 0。

最后通過(guò)PM1的遷移能耗、帶寬和VM1的內(nèi)存計(jì)算PM1的遷移能耗權(quán)重ec11，內(nèi)存和ec11成正比，帶寬和ec11成正比，遷移能耗和ec11成反比。

以此類推。結(jié)合文獻(xiàn)[17]，VM1分配到PM1的貢獻(xiàn)值為：

degET(pm1)=

1/(1+et11)+1/(1+et21)+…+1/(1+et1) （3）

degSLA(pm1)= 1/(1+sla11)+1/(1+sla21)+…+1/(1+sla1) （4）

degEC(pm1)=

1/(1+ec11)+1/(1+ec21)+…+1/(1+ec1) （5）

其中，et1、sla1、ec1分別表示將VM分配到PM1的遷移時(shí)間權(quán)重、SLA違背率權(quán)重和遷移能耗權(quán)重。

圖3中PM2的計(jì)算方式和PM1相同，可以計(jì)算出其degET(pm2)、degSLA(pm2)、degEC(pm2) ，因此在大規(guī)模網(wǎng)絡(luò)中，可以將衍生的計(jì)算式總結(jié)如下。

deg(pm)=

degET(pm)+degSLA(pm)+degEC(pm) （6）

其中，分別表示遷移時(shí)間、SLA違背率和遷移能耗的權(quán)重參數(shù)。

式（6）的計(jì)算時(shí)間復(fù)雜度為(3·||·||)，其中，表示虛擬機(jī)數(shù)量，表示物理機(jī)數(shù)量。集合deg(pm),∈表示包含臺(tái)PM的集合中每一臺(tái)PM的貢獻(xiàn)值，其為第2.3節(jié)提供了變異步驟中每一臺(tái)PM被選中的概率。

2.3 SV-GA下的VM調(diào)度策略

上文提到，云計(jì)算環(huán)境中的虛擬機(jī)遷移調(diào)度是一個(gè)NP問(wèn)題。當(dāng)物理機(jī)數(shù)量很大時(shí)，很難找到最佳解決方案。通常的方法是應(yīng)用各種智能優(yōu)化算法將得出的相對(duì)最優(yōu)解作為滿意的解決方案。遺傳算法[18]是歷史上最早提出的基于種群的隨機(jī)算法之一，也是獲得近似最優(yōu)解的最典型的進(jìn)化算法之一。本節(jié)將基于Shapley值計(jì)算得到的貢獻(xiàn)值應(yīng)用于遺傳算法，調(diào)整其變異過(guò)程中作為父親被選擇出現(xiàn)的基因（PM）的概率來(lái)優(yōu)化計(jì)算結(jié)果。

2.3.1 初始化

首先，初始化種群并設(shè)置相關(guān)參數(shù)，如種群大小、交叉的概率、突變的概率以及種群中每個(gè)個(gè)體的評(píng)估適應(yīng)性；虛擬機(jī)遷移通常包含遷移的SLA違背率，遷移時(shí)間（execution time，ET）、遷移能耗（energy consumption，EC）、遷移次數(shù)（migration time，MT）、虛擬機(jī)遷移指標(biāo)停機(jī)時(shí)間（downtime）、整體網(wǎng)絡(luò)流量（total network traffic）等參數(shù)[15]，本文提出的SV-GA和第2.2節(jié)中PM的貢獻(xiàn)值的影響因子保持一致，分別為SLA、ET和EC。因此SV-GA的適應(yīng)度函數(shù)定義如下。

其中，'、'和'表示遷移時(shí)間、SLA違背率和遷移能耗的權(quán)重因子，ET=∑ET，ET表示每一臺(tái)VM遷移所需時(shí)間，SLA=熱節(jié)點(diǎn)數(shù)量/所有激活的物理機(jī)數(shù)量，EC=∑EC，EC表示每一臺(tái)激活的物理機(jī)的能耗。

然后將虛擬機(jī)和物理機(jī)之間的匹配轉(zhuǎn)換成遺傳算法中染色體的形式。染色體定義如圖4所示。定義染色體的長(zhǎng)度為，表示一共有臺(tái)VM，1～條染色體分別對(duì)應(yīng)VM1～VM, 將該VM的位置放入目標(biāo)PM，如圖4中位置1和2都被放入PM2，表示VM1和VM2都將被分配到PM2，同理VM3則將被分配到PM4，VM將被分配到PM1。

圖4 染色體定義

2.3.2 選擇

在初始化的隨機(jī)大量染色體序列中，可以使用式（7）計(jì)算出每一條染色體的得分，根據(jù)得分越高染色體越優(yōu)秀的原則，選擇得分高的前30%染色體組成初始化種群，同時(shí)保留少量得分低的染色體，以保證不會(huì)完全摒棄遺傳物質(zhì)。

2.3.3 交叉

在追尋更高適應(yīng)度函數(shù)得分的原則下，從種群中選擇兩個(gè)隨機(jī)染色體A和B作為父母，用于執(zhí)行交叉操作，以產(chǎn)生兩個(gè)新的子染色體A'和B'，交叉過(guò)程如圖5所示。

圖5 交叉過(guò)程

2.3.4 變異

傳統(tǒng)的變異步驟包括高斯變異、均勻變異和非均勻變異[19]等。在這些變異中，僅改變個(gè)體中單個(gè)基因的值以提高其適應(yīng)度。這對(duì)整個(gè)個(gè)體的影響極小，尤其是在人口規(guī)模較大或解決方案接近穩(wěn)定時(shí)。

為了擴(kuò)大搜索范圍從而緩解局部最優(yōu)解的過(guò)早收斂，本文在保留原有變異的基礎(chǔ)上，額外增加一條變異的染色體，但其變異時(shí)不同基因（PM）出現(xiàn)的概率不再是完全隨機(jī)的，而是根據(jù)第2.2節(jié)提出的PM貢獻(xiàn)值，修正不同PM出現(xiàn)的概率。

F=deg(pm)/∑deg(pm) （8）

其中，表示PM的總數(shù)，deg(pm)表示PM的貢獻(xiàn)值，即分子是求解的物理機(jī)的貢獻(xiàn)值，分母是所有物理機(jī)貢獻(xiàn)值的和。因此根據(jù)PM的貢獻(xiàn)度，就可以得出其被選中變異的概率，即F。變異過(guò)程如圖6所示，染色體a經(jīng)過(guò)傳統(tǒng)的突變得到的新染色體為a'，經(jīng)過(guò)變異概率F得到的新染色體為a''。最終同時(shí)保留新染色體a'和a''，從而改善局部最優(yōu)解過(guò)早收斂的問(wèn)題。

圖6 變異過(guò)程

2.3.5 迭代

最終通過(guò)迭代完成算法的進(jìn)化過(guò)程，重復(fù)選擇、交叉和變異步驟，直到觸發(fā)終止條件：達(dá)到設(shè)定的迭代次數(shù)，返回相對(duì)最優(yōu)基因，即虛擬機(jī)調(diào)度結(jié)果，遺傳算法流程如圖7所示。

圖7 遺傳算法流程

3 SV-GA調(diào)度模型下的模擬實(shí)驗(yàn)結(jié)果

3.1 實(shí)驗(yàn)環(huán)境

墨爾本大學(xué)和Gridbus項(xiàng)目小組于2009年發(fā)布了CloudSim[20]，這是一款功能強(qiáng)大的云計(jì)算環(huán)境仿真軟件。CloudSim是基于GridSim中現(xiàn)有的基于Java的離散事件仿真程序包，并且在GridSim的現(xiàn)有體系結(jié)構(gòu)上開(kāi)發(fā)的。本文使用CloudSim進(jìn)行模擬，并使用一個(gè)類似于文獻(xiàn)[21-22]使用的數(shù)據(jù)中心，該數(shù)據(jù)中心由多臺(tái)異構(gòu)PM組成。這些PM分為兩類，其規(guī)格和功耗模型基于真實(shí)服務(wù)器的基準(zhǔn)數(shù)據(jù)，第一類有兩個(gè)CPU核，時(shí)鐘頻率為1 860 MHz，內(nèi)存為4 GB；第二類也有兩個(gè)CPU核，每個(gè)CPU核的時(shí)鐘頻率為2 600 MHz，內(nèi)存為4 GB。本實(shí)驗(yàn)使用的數(shù)據(jù)來(lái)自提交給Google集群和PlanetLab的虛擬機(jī)的匿名工作負(fù)載跟蹤。每個(gè)實(shí)驗(yàn)共使用100個(gè)工作負(fù)載跟蹤和Google Cluster Trace Version1[23]中最小的50條跟蹤來(lái)模擬輕度用戶需求，同時(shí)提取50條負(fù)載最大的記錄作為重度負(fù)載的模擬數(shù)據(jù)。

3.2 實(shí)驗(yàn)結(jié)果

本文使用Max-Min[24]、LrMmt[25]和DE[26]作為對(duì)比算法，與所提SV-GA進(jìn)行實(shí)驗(yàn)。同時(shí)為了進(jìn)一步驗(yàn)證實(shí)驗(yàn)合理性，本文參考了文獻(xiàn)[15]的實(shí)驗(yàn)環(huán)境，增加了不同負(fù)載情況下（輕度負(fù)載和重度負(fù)載）的4種虛擬機(jī)調(diào)度算法實(shí)驗(yàn)。同時(shí)用SLA違背率、遷移時(shí)間、遷移能耗和遷移次數(shù)4種指標(biāo)評(píng)價(jià)算法性能，4種指標(biāo)的值均遵循越低越好的原則。最后記錄10次計(jì)算的平均值，得到的實(shí)驗(yàn)結(jié)果如下。

首先，本文對(duì)虛擬機(jī)遷移的SLA違背率進(jìn)行了實(shí)驗(yàn)。SLA違背率如圖8所示?？梢钥闯觯谳p度負(fù)載下，DE和SV-GA的SLA違背率差不多，而Max-Min和LrMmt則略高于前兩者。然而在重度負(fù)載下，Max-Min和LrMmt的SLA違背率明顯高于DE和SV-GA。在SLA違背率指標(biāo)上，本文提出的SV-GA具有一定的優(yōu)勢(shì)。

圖8 SLA違背率

其次，本文對(duì)虛擬機(jī)的遷移時(shí)間進(jìn)行了實(shí)驗(yàn)。遷移時(shí)間如圖9所示。可以看出，在輕度負(fù)載下，LrMmt的遷移時(shí)間最小，SV-GA和DE次之，Max-Min的遷移時(shí)間最大。在重度負(fù)載下，整體的遷移時(shí)間都有了明顯提升，但排名并無(wú)變化。因此在遷移時(shí)間的實(shí)驗(yàn)中，LrMmt表現(xiàn)最佳，本文提出的SV-GA次之。

圖9 遷移時(shí)間

再次，本文對(duì)虛擬機(jī)的遷移能耗進(jìn)行了實(shí)驗(yàn)。遷移能耗如圖10所示。可以看出，無(wú)論是在輕度負(fù)載還是重度負(fù)載下，SV-GA的遷移能耗最低，DE次之，Max-Min和LrMmt的遷移能耗則明顯更高。在遷移能耗的實(shí)驗(yàn)中，SV-GA表現(xiàn)最佳。

圖10 遷移能耗

最后，本文對(duì)虛擬機(jī)的遷移次數(shù)進(jìn)行了實(shí)驗(yàn)。遷移次數(shù)如圖11所示?？梢钥闯觯瑢?duì)比圖9和 圖11，二者比較相似。在輕度負(fù)載下，LrMmt的遷移次數(shù)最低，SV-GA和DE次之，Max-Min的遷移次數(shù)最多。在重度負(fù)載下，整體的遷移次數(shù)都有了明顯提升，但排名并無(wú)變化。因此在遷移次數(shù)實(shí)驗(yàn)中，遷移次數(shù)最低的LrMmt表現(xiàn)最佳，本文提出的SV-GA次之。

圖11 遷移次數(shù)

輕度負(fù)載和重度負(fù)載下4種算法的性能對(duì)比分別見(jiàn)表1和表2。其中4種指標(biāo)的優(yōu)化目標(biāo)皆是最小化，因此以SV-GA為基準(zhǔn)，可以看到，輕度負(fù)載下SV-GA在SLA違背率上，分別優(yōu)于Max-Min、LrMmt和DE算法20.54%、30.64%和3.70%；在遷移能耗上，分別優(yōu)于Max-Min、LrMmt和DE算法26.41%、45.76%和3.22%。但值得注意的是，在遷移時(shí)間和遷移次數(shù)上，分別以?21.09%和?11.55%次于LrMmt，排在第二。這是因?yàn)長(zhǎng)rMmt算法犧牲了大量的SLA違背率（30.64%）和遷移能耗（45.76%）。與輕度負(fù)載相比，重度負(fù)載下各指標(biāo)的算法排名順序并無(wú)變化。因此通過(guò)實(shí)驗(yàn)證明，本文所提SV-GA對(duì)虛擬機(jī)調(diào)度和分配起到了積極的作用。

表1 輕度負(fù)載下4種算法的性能對(duì)比

表2 重度負(fù)載下4種算法的性能對(duì)比

4 結(jié)束語(yǔ)

在相同的硬件設(shè)施下，云計(jì)算可提供的資源在很大程度上取決于采用的資源分配策略。本文針對(duì)云計(jì)算環(huán)境中物理資源和虛擬資源分配的博弈問(wèn)題，提出一種虛擬機(jī)調(diào)度模型，該模型使用基于Shapley值的遺傳算法實(shí)現(xiàn)其虛擬資源調(diào)度模擬，并通過(guò)CloudSim得到的仿真結(jié)果驗(yàn)證了所提算法的有效性。對(duì)于參數(shù)的選取，本文主要以典型性參數(shù)為主，目的在于突出SV-GA的虛擬機(jī)調(diào)度作用，然而真實(shí)情況下的虛擬機(jī)調(diào)度參數(shù)有進(jìn)一步的研究空間，包括預(yù)處理階段、遷移失敗、臟頁(yè)處理等。同時(shí)本文所提模型和算法的重點(diǎn)是資源的分配和調(diào)度，通過(guò)結(jié)合Shapley值與遺傳算法來(lái)解決云計(jì)算中的資源調(diào)度問(wèn)題。這種組合也可以應(yīng)用于其他進(jìn)化算法，如模擬退火算法、免疫算法、粒子群算法等，具有非常強(qiáng)的適配性。因此本文所提模型和算法的延展性是值得期待的，比如應(yīng)用于用戶層和虛擬層之間的任務(wù)調(diào)度、物聯(lián)網(wǎng)終端設(shè)備與云端的節(jié)點(diǎn)選擇、傳感器和霧計(jì)算節(jié)點(diǎn)之間的分配，以及除云計(jì)算外的各種資源分配及博弈論問(wèn)題等。

[1] LAILI Y J, TAO F, ZHANG L, et al. A study of optimal allocation of computing resources in cloud manufacturing systems[J]. The International Journal of Advanced Manufacturing Technology, 2012, 63(5-8): 671-690.

[2] ZHANG Q, CHENG L, BOUTABA R. Cloud computing: state-of-the-art and research challenges[J]. Journal of Internet Services and Applications, 2010, 1(1): 7-18.

[3] 呂廷勤, 魏萌. 基于蟻群優(yōu)化算法的綠色云計(jì)算虛擬機(jī)遷移策略[J]. 西南師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2020, 45(12): 78-84.

LYU T Q, WEI M. Migration strategy of green cloud computing virtual machine based on ant colony optimization algorithm[J]. Journal of Southwest China Normal University (Natural Science Edition), 2020, 45(12): 78-84.

[4] YADAV R, ZHANG W Z, CHEN H, et al. MuMs: energy-aware VM selection scheme for cloud data center[C]//Proceedings of 2017 28th International Workshop on Database and Expert Systems Applications (DEXA). Piscataway: IEEE Press, 2017: 132-136.

[5] GELENBE E, LENT R. Optimising server energy consumption and response time[J]. Theoretical and Applied Informatics, 2012, 24(4).

[6] YADAV R, ZHANG W Z. MeReg: managing energy-SLA tradeoff for green mobile cloud computing[J]. Wireless Communications and Mobile Computing, 2017, 2017: 6741972.

[7] CHAUHAN S S, JOSHI R C. A weighted mean time Min-Min Max-Min selective scheduling strategy for independent tasks on grid[C]//Proceedings of 2010 IEEE 2nd International Advance Computing Conference. Piscataway: IEEE Press, 2010: 4-9.

[8] 劉永, 王新華, 王朕, 等. 節(jié)能及信任驅(qū)動(dòng)的虛擬機(jī)資源調(diào)度[J]. 計(jì)算機(jī)應(yīng)用研究, 2012, 29(7): 2479-2483.

LIU Y, WANG X H, WANG Z, et al. Energy-aware and trust-driven virtual machine scheduling[J]. Application Research of Computers, 2012, 29(7): 2479-2483.

[9] 古英漢, 伊鵬. 多虛擬機(jī)動(dòng)態(tài)遷移情景下的服務(wù)功能鏈調(diào)整方法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2017, 38(5): 1022-1027.

GU Y H, YI P. Method of service function chain adjustment based on multi-VM live migration[J]. Journal of Chinese Computer Systems, 2017, 38(5): 1022-1027.

[10] AJMERA K, TEWARI T K. VMS-MCSA: virtual machine scheduling using modified clonal selection algorithm[J]. Cluster Computing, 2021, 24(4): 3531-3549.

[11] GARG V, JINDAL B. Energy efficient virtual machine migration approach with SLA conservation in cloud computing[J]. Journal of Central South University, 2021, 28(3): 760-770.

[12] PERUMAL V, SUBBIAH S. Power-conservative server consolidation based resource management in cloud[J]. International Journal of Network Management, 2014, 24(6): 415-432.

[13] BELOGLAZOV A, BUYYA R. Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers[J]. Concurrency and Computation: Practice and Experience, 2012, 24(13): 1397-1420.

[14] JALALI MOGHADDAM M, ESMAEILZADEH A, GHAVIPOUR M, et al. Minimizing virtual machine migration probability in cloud computing environments[J]. Cluster Computing, 2020, 23(4): 3029-3038.

[15] AJAYI O O, BAGULA A B, MA K. Fourth industrial revolution for development: the relevance of cloud federation in healthcare support[J]. IEEE Access, 2019(7): 185322-185337.

[16] WINTER E. Chapter 53 the shapley value[M]//Handbook of game theory with economic applications. Amsterdam: Elsevier, 2002: 2025-2054.

[17] MICHALAK T P, AADITHYA K V, SZCZEPANSKI P L, et al. Efficient computation of the shapley value for game-theoretic network centrality[J]. Journal of Artificial Intelligence Research, 2013, 46: 607-650.

[18] MATHEW T V. Genetic algorithm[R]. 2012.

[19] ZHAO X C, GAO X S, HU Z C. Evolutionary programming based on non-uniform mutation[J]. Applied Mathematics and Computation, 2007, 192(1): 1-11.

[20] CALHEIROS R N, RANJAN R, BELOGLAZOV A, et al. CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software: Practice and Experience, 2011, 41(1): 23-50.

[21] HIEU N T, FRANCESCO M D, YL?-J??SKI A. Virtual machine consolidation with multiple usage prediction for energy-efficient cloud data centers[J]. IEEE Transactions on Services Computing, 2020, 13(1): 186-199.

[22] AJAYI O O, OLADEJI F A, UWADIA C O. Multi-class load balancing scheme for QoS and energy conservation in cloud computing[J]. West African Journal of Industrial and Academic Research, 2017, 17(1): 28-36.

[23] PARK K, PAI V S. CoMon: a mostly-scalable monitoring system for PlanetLab[J]. ACM SIGOPS Operating Systems Review, 2016, 40(1): 65-74.

[24] KIM M H, LEE J Y, RAZA SHAH S A, et al. Min-Max exclusive virtual machine placement in cloud computing for scientific data environment[J]. Journal of Cloud Computing, 2021(10): 2.

[25] NAGMA, SINGH J, SIDHU J. Comparative analysis of VM consolidation algorithms for cloud computing[J]. Procedia Computer Science, 2020(167): 1390-1399.

[26] SUN J Y, ZHANG Q F, TSANG E P K. DE/EDA: a new evolutionary algorithm for global optimization[J]. Information Sciences, 2005, 169(3-4): 249-262.

Virtual machine scheduling model based on Shapley value modified genetic algorithm in cloud computing

MA Kun1,2, XU Lingyu2, SHEN Xiaoping1,2, GONG Zhicheng1,2, LAN Jianping1,2, CHEN Shuangxi1,2,4, QIAN Jun5

1. Jiaxing Vocational Technical College, Jiaxing 314036, China 2. Jiaxing Key Laboratory of Industrial Internet Security, Jiaxing 314036, China 3. Jiaxing Nanyang Polytechnic Institute, Jiaxing 314031, China 4. Zhejiang University, Hangzhou 310058, China 5. Jiaxing Branch of China Telecom Co., Ltd., Jiaxing 314011, China

Cloud computing system has the characteristics of large-scale servers and a wide range of users. However, it also consumes a huge number of energy, resulting in high operating costs of cloud providers and high carbon emissions issue. Cloud computing is highly virtualized. How to allocate and manage the virtual resources to ensure efficient physical resource utilization and energy consumption control is a multi-parameter game problem, and it is also a research hotspot in this field. A virtual machine scheduling model and the corresponding SV-GA were proposed, which could calculate the contribution value of the physical machine participating in the work through the Shapley value, and modify the probability parameter of the mutation step in the genetic algorithm through the contribution value, so as to complete the task of virtual machine scheduling. The experimental results show that during the comparison with Max-Min, LrMmt and DE, the SV-GA shows its excellent performance in the multi-parameter game including migration time, times, SLA violation rate and energy consumption in the virtual machine scheduling process.

cloud computing, multi-parameter game, virtual machine scheduling, Shapley value, genetic algorithm

TP393

A

10.11959/j.issn.1000–0801.2022281

2022–07–01；

2022–11–07

浙江省“尖兵”“領(lǐng)雁”研發(fā)攻關(guān)計(jì)劃項(xiàng)目（No. 2022C01243）；浙江省科學(xué)技術(shù)廳重點(diǎn)研發(fā)計(jì)劃項(xiàng)目（No.2021C01036）；浙江省教育廳一般科研項(xiàng)目（No.Y202044105）；嘉興市科學(xué)技術(shù)局公益性研究計(jì)劃項(xiàng)目（No.2022AY10009，No.2021AD10003，No.2019AD32029）

馬焜（1988? ），男，博士，嘉興職業(yè)技術(shù)學(xué)院講師，主要研究方向?yàn)樵朴?jì)算、霧計(jì)算、邊緣計(jì)算及數(shù)據(jù)可視化等。

徐玲玉（1991? ），女，嘉興南洋職業(yè)技術(shù)學(xué)院助教，主要研究方向?yàn)閰^(qū)塊鏈技術(shù)和網(wǎng)絡(luò)虛擬化技術(shù)。

沈曉萍（1982? ），女，嘉興職業(yè)技術(shù)學(xué)院講師，主要研究方向?yàn)榫W(wǎng)絡(luò)通信、5G技術(shù)。

龔志城（1990– ），男，嘉興職業(yè)技術(shù)學(xué)院講師，主要研究方向?yàn)榫W(wǎng)絡(luò)信息安全。

藍(lán)建平（1975? ），男，嘉興職業(yè)技術(shù)學(xué)院副教授，主要研究方向?yàn)榇髷?shù)據(jù)、移動(dòng)應(yīng)用開(kāi)發(fā)。

陳雙喜（1980? ），男，浙江大學(xué)博士生，嘉興職業(yè)技術(shù)學(xué)院副教授，主要研究方向?yàn)榫W(wǎng)絡(luò)空間安全擬態(tài)防御。

錢(qián)鈞（1977? ），男，中國(guó)電信股份有限公司嘉興分公司綜合管理部主任，主要研究方向?yàn)橹悄軘?shù)據(jù)處理和信息安全。

s: Zhejiang Province “Top Soldiers” and “Leading Geese” Research and Development Projects (No. 2022C01243), Key Research and Development Programs of Science Technology Department of Zhejiang Province (No.2021C01036), General Research and Development Programs Department of Education of Zhejiang Province (No.Y202044105), Public Welfare Research Program of Kexueju (No.2022AY10009, No. 2021AD10003, No.2019AD32029)