云計算中基于Shapley值改進遺傳算法的虛擬機調度模型

馬焜，徐玲玉，沈曉萍，龔志城，藍建平，陳雙喜,4，錢鈞

云計算中基于Shapley值改進遺傳算法的虛擬機調度模型

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

（1. 嘉興職業技術學院，浙江 嘉興 314036；2. 嘉興市工業互聯網安全重點實驗室，浙江 嘉興 314036；3. 嘉興南洋職業技術學院，浙江 嘉興 314031；4. 浙江大學，浙江 杭州 310058；5. 中國電信股份有限公司嘉興分公司，浙江 嘉興 314011）

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

云計算；多參數博弈；虛擬機調度；Shapley值；遺傳算法

0 引言

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

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

1 基于Shapley改進遺傳算法的虛擬機調度模型

1.1 虛擬機調度工作環境

云計算中，虛擬化技術的一個核心價值體現是作為用戶和云供應商物理資源之間數據和信息交互的橋梁，因此云計算的結構通常可以用3個層次表述：用戶層、虛擬層、物理層。云計算層次結構如圖1所示。

圖1 云計算層次結構

根據層次的不同，云計算提供的服務方式可分為軟件即服務（software as a service，SaaS）、平臺即服務（platform as a service，PaaS）和基礎設施即服務（infrastructure as a service，IaaS）。基于以上3種層次的服務，云計算不僅實現了信息應用服務的整體定制，還實現了底層邏輯基礎資源、基礎軟件和應用的整合，做到“按需即用，隨需應變”，從而顛覆性地改變了傳統IT服務商業模式。

本文的主要研究內容是虛擬層和物理層之間的資源調度問題。以基于Shapley值的遺傳算法（SV-GA）為核心對虛擬機調度進行建模，目標在于盡可能合理化地分配物理機之間的虛擬資源。

1.2 SV-GA虛擬機調度模型

如上文所說，云計算技術為用戶分配可用資源有多種模式。這些模式可以被視為對云數據中心資源池的基于服務的訪問。這些訪問的具體實現形式是使用虛擬機技術將云用戶的請求封裝到虛擬機中進行分配和訪問。虛擬機調度模型的體系結構如圖2所示。

圖2 虛擬機調度模型的體系結構

步驟1 虛擬機提交請求同時獲取物理資源數據，虛擬層發出要被分配的虛擬機的請求到資源調度器，包括虛擬機的具體參數，如CPU、帶寬、內存等，同時獲取各臺物理機的數據。注意，物理機的數據不僅包括對應虛擬機的參數，還包括能耗、熱節點閾值等。

步驟2 處理請求，資源調度器將虛擬機和物理機的相關參數整合，使用SV-GA進行計算并得到分配結果。

步驟3 返回該算法生成的調度結果。

步驟4 將虛擬機分配到物理機，資源調度器根據返回的信息，把虛擬機調度到對應的物理機上，完成虛擬機的調度。

2 基于Shapley值改進的遺傳算法

2.1 Shapley值在物理機貢獻中的應用

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

物理機的邊際貢獻（contribution margin，CM）定義如下。

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

其中，CM()表示物理機對集合的邊際貢獻，而/{}表示除物理機外的所有物理機形成的集合。Shapley值通過物理機的邊際貢獻衡量該物理機對集合的改善程度。因此在集合(,)中，可以計算出每臺物理機對整個集合的貢獻程度。

基于邊際貢獻，Shapley值定義如下。

在聯合博弈(P,PM)中，PM表示目標總物理機集合，P表示包含物理機的各種子集，則物理機的貢獻值為：

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

2.2 云計算拓撲中物理機的貢獻值計算

盡管Shapley值的提出為PM的貢獻值計算提供了一個強有力的支持，但其精確值的直接計算同樣是一個NP問題。文獻[17]提出了對拓撲網絡中每個節點的Shapley值的計算方法，其計算參數包括該節點擁有的相鄰節點數量（即邊的數量）和每條邊的權重。

在本文所提云計算中VM到PM的計算拓撲網絡中，PM的單一作用就是被分配VM，并且均可被分配任意VM，因此每臺PM的邊數可視為相同，只需要考慮參數即可。同時可根據VM對不同屬性的需求，動態調整其權重的比例，即物理機的貢獻值deg(pm)，本文定義物理機有3種屬性：遷移時間貢獻值degET(pm)、SLA違背率貢獻值degSLA(pm)和遷移能耗貢獻值degEC(pm)，物理機貢獻值計算拓撲如圖3所示。

圖3 物理機貢獻值計算拓撲

以PM1為例，首先獲取PM1和VM1的參數數據，如網絡帶寬、內存，即可通過簡單計算得到VM1分配給PM1的遷移時間權重et11，其中帶寬和et11成正比，內存和et11成反比。

然后，通過對比將VM1分配到PM1前后，PM1負載是否處于低/高閾值[11]區間來判斷其SLA違背率權重sla11。

情況1：VM1將PM1從處于低閾值區間變成普通節點，則sla11= 1。

情況2：VM1將PM1從普通節點變成熱節點（處于高閾值區間），則sla11= ?1。

情況3：VM1對PM1無影響（PM1是普通節點），則sla11= 0。

最后通過PM1的遷移能耗、帶寬和VM1的內存計算PM1的遷移能耗權重ec11，內存和ec11成正比，帶寬和ec11成正比，遷移能耗和ec11成反比。

以此類推。結合文獻[17]，VM1分配到PM1的貢獻值為：

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的遷移時間權重、SLA違背率權重和遷移能耗權重。

圖3中PM2的計算方式和PM1相同，可以計算出其degET(pm2)、degSLA(pm2)、degEC(pm2) ，因此在大規模網絡中，可以將衍生的計算式總結如下。

deg(pm)=

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

其中，分別表示遷移時間、SLA違背率和遷移能耗的權重參數。

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

2.3 SV-GA下的VM調度策略

上文提到，云計算環境中的虛擬機遷移調度是一個NP問題。當物理機數量很大時，很難找到最佳解決方案。通常的方法是應用各種智能優化算法將得出的相對最優解作為滿意的解決方案。遺傳算法[18]是歷史上最早提出的基于種群的隨機算法之一，也是獲得近似最優解的最典型的進化算法之一。本節將基于Shapley值計算得到的貢獻值應用于遺傳算法，調整其變異過程中作為父親被選擇出現的基因（PM）的概率來優化計算結果。

2.3.1 初始化

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

其中，'、'和'表示遷移時間、SLA違背率和遷移能耗的權重因子，ET=∑ET，ET表示每一臺VM遷移所需時間，SLA=熱節點數量/所有激活的物理機數量，EC=∑EC，EC表示每一臺激活的物理機的能耗。

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

圖4 染色體定義

2.3.2 選擇

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

2.3.3 交叉

在追尋更高適應度函數得分的原則下，從種群中選擇兩個隨機染色體A和B作為父母，用于執行交叉操作，以產生兩個新的子染色體A'和B'，交叉過程如圖5所示。

圖5 交叉過程

2.3.4 變異

傳統的變異步驟包括高斯變異、均勻變異和非均勻變異[19]等。在這些變異中，僅改變個體中單個基因的值以提高其適應度。這對整個個體的影響極小，尤其是在人口規模較大或解決方案接近穩定時。

為了擴大搜索范圍從而緩解局部最優解的過早收斂，本文在保留原有變異的基礎上，額外增加一條變異的染色體，但其變異時不同基因（PM）出現的概率不再是完全隨機的，而是根據第2.2節提出的PM貢獻值，修正不同PM出現的概率。

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

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

圖6 變異過程

2.3.5 迭代

最終通過迭代完成算法的進化過程，重復選擇、交叉和變異步驟，直到觸發終止條件：達到設定的迭代次數，返回相對最優基因，即虛擬機調度結果，遺傳算法流程如圖7所示。

圖7 遺傳算法流程

3 SV-GA調度模型下的模擬實驗結果

3.1 實驗環境

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

3.2 實驗結果

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

首先，本文對虛擬機遷移的SLA違背率進行了實驗。SLA違背率如圖8所示。可以看出，在輕度負載下，DE和SV-GA的SLA違背率差不多，而Max-Min和LrMmt則略高于前兩者。然而在重度負載下，Max-Min和LrMmt的SLA違背率明顯高于DE和SV-GA。在SLA違背率指標上，本文提出的SV-GA具有一定的優勢。

圖8 SLA違背率

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

圖9 遷移時間

再次，本文對虛擬機的遷移能耗進行了實驗。遷移能耗如圖10所示。可以看出，無論是在輕度負載還是重度負載下，SV-GA的遷移能耗最低，DE次之，Max-Min和LrMmt的遷移能耗則明顯更高。在遷移能耗的實驗中，SV-GA表現最佳。

圖10 遷移能耗

最后，本文對虛擬機的遷移次數進行了實驗。遷移次數如圖11所示。可以看出，對比圖9和 圖11，二者比較相似。在輕度負載下，LrMmt的遷移次數最低，SV-GA和DE次之，Max-Min的遷移次數最多。在重度負載下，整體的遷移次數都有了明顯提升，但排名并無變化。因此在遷移次數實驗中，遷移次數最低的LrMmt表現最佳，本文提出的SV-GA次之。

圖11 遷移次數

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

表1 輕度負載下4種算法的性能對比

表2 重度負載下4種算法的性能對比

4 結束語

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

[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] 呂廷勤, 魏萌. 基于蟻群優化算法的綠色云計算虛擬機遷移策略[J]. 西南師范大學學報(自然科學版), 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] 劉永, 王新華, 王朕, 等. 節能及信任驅動的虛擬機資源調度[J]. 計算機應用研究, 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]. 小型微型計算機系統, 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

浙江省“尖兵”“領雁”研發攻關計劃項目（No. 2022C01243）；浙江省科學技術廳重點研發計劃項目（No.2021C01036）；浙江省教育廳一般科研項目（No.Y202044105）；嘉興市科學技術局公益性研究計劃項目（No.2022AY10009，No.2021AD10003，No.2019AD32029）

馬焜（1988? ），男，博士，嘉興職業技術學院講師，主要研究方向為云計算、霧計算、邊緣計算及數據可視化等。

徐玲玉（1991? ），女，嘉興南洋職業技術學院助教，主要研究方向為區塊鏈技術和網絡虛擬化技術。

沈曉萍（1982? ），女，嘉興職業技術學院講師，主要研究方向為網絡通信、5G技術。

龔志城（1990– ），男，嘉興職業技術學院講師，主要研究方向為網絡信息安全。

藍建平（1975? ），男，嘉興職業技術學院副教授，主要研究方向為大數據、移動應用開發。

陳雙喜（1980? ），男，浙江大學博士生，嘉興職業技術學院副教授，主要研究方向為網絡空間安全擬態防御。

錢鈞（1977? ），男，中國電信股份有限公司嘉興分公司綜合管理部主任，主要研究方向為智能數據處理和信息安全。

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)