云计算中基于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)