云计算中基于Shapley值改进遗传算法的虚拟机调度模型

doi:10.11959/j.issn.1000-0801.2022281

电信科学 ›› 2022, Vol. 38 ›› Issue (12): 1-10.doi: 10.11959/j.issn.1000-0801.2022281

• 研究与开发 • 下一篇

云计算中基于Shapley值改进遗传算法的虚拟机调度模型

马焜¹^,², 徐玲玉³, 沈晓萍¹^,², 龚志城¹^,², 蓝建平¹^,², 陈双喜¹^,²^,⁴, 钱钧⁵

¹ 嘉兴职业技术学院，浙江嘉兴 314036
² 嘉兴市工业互联网安全重点实验室，浙江嘉兴 314036
³ 嘉兴南洋职业技术学院，浙江嘉兴 314031
⁴ 浙江大学，浙江杭州 310058
⁵ 中国电信股份有限公司嘉兴分公司，浙江嘉兴 314011

修回日期:2022-11-07 出版日期:2022-12-20 发布日期:2022-12-01
作者简介:马焜（1988- ），男，博士，嘉兴职业技术学院讲师，主要研究方向为云计算、雾计算、边缘计算及数据可视化等
徐玲玉（1991- ），女，嘉兴南洋职业技术学院助教，主要研究方向为区块链技术和网络虚拟化技术
沈晓萍（1982- ），女，嘉兴职业技术学院讲师，主要研究方向为网络通信、5G技术
龚志城（1990- ），男，嘉兴职业技术学院讲师，主要研究方向为网络信息安全
蓝建平（1975- ），男，嘉兴职业技术学院副教授，主要研究方向为大数据、移动应用开发
陈双喜（1980- ），男，浙江大学博士生，嘉兴职业技术学院副教授，主要研究方向为网络空间安全拟态防御
钱钧（1977- ），男，中国电信股份有限公司嘉兴分公司综合管理部主任，主要研究方向为智能数据处理和信息安全
基金资助:
浙江省“尖兵”“领雁”研发攻关计划项目(2022C01243);浙江省科学技术厅重点研发计划项目(2021C01036);浙江省教育厅一般科研项目(Y202044105);嘉兴市科学技术局公益性研究计划项目(2022AY10009);嘉兴市科学技术局公益性研究计划项目(2021AD10003);嘉兴市科学技术局公益性研究计划项目(2019AD32029)

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

Kun MA¹^,², Lingyu XU³, Xiaoping SHEN¹^,², Zhicheng GONG¹^,², Jianping LAN¹^,², Shuangxi CHEN¹^,²^,⁴, Jun QIAN⁵

¹ Jiaxing Vocational Technical College, Jiaxing 314036, China
² Jiaxing Key Laboratory of Industrial Internet Security, Jiaxing 314036, China
³ Jiaxing Nanyang Polytechnic Institute, Jiaxing 314031, China
⁴ Zhejiang University, Hangzhou 310058, China
⁵ Jiaxing Branch of China Telecom Co., Ltd., Jiaxing 314011, China

Revised:2022-11-07 Online:2022-12-20 Published:2022-12-01
Supported by:
Zhejiang Province “Top Soldiers” and “Leading Geese” Research and Development Projects(2022C01243);Key Research and Development Programs of Science Technology Department of Zhejiang Province(2021C01036);General Research and Development Programs Department of Education of Zhejiang Province(Y202044105);Public Welfare Research Program of Kexueju(2022AY10009);Public Welfare Research Program of Kexueju(2021AD10003);Public Welfare Research Program of Kexueju(2019AD32029)

摘要/Abstract

摘要：

云计算系统具有服务器规模大、用户范围广的特点，但同时也消耗了大量的能源，导致云供应商的高运营成本和高碳排放等问题。云计算高度虚拟化，如何分配和管理其虚拟资源，从而保证高效的物理资源利用和能耗控制，是一个多参数博弈过程，同时也是该领域的一个研究热点。提出了一种虚拟机调度模型及基于Shapley 值的遗传算法（SV-GA），可通过经济学概念Shapley 值计算出参与工作的物理机贡献值，并通过该贡献值修正遗传算法中变异步骤的概率参数，从而完成虚拟机调度的任务。实验结果表明，与Max-Min、LrMmt及DE算法相比，SV-GA在虚拟机调度过程中的迁移时间、次数、SLA违背率、能耗等多参数博弈中具有优异的表现。

关键词: 云计算, 多参数博弈, 虚拟机调度, Shapley值, 遗传算法

Abstract:

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.

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

中图分类号:

TP393

马焜, 徐玲玉, 沈晓萍, 龚志城, 蓝建平, 陈双喜, 钱钧. 云计算中基于Shapley值改进遗传算法的虚拟机调度模型[J]. 电信科学, 2022, 38(12): 1-10.

Kun MA, Lingyu XU, Xiaoping SHEN, Zhicheng GONG, Jianping LAN, Shuangxi CHEN, Jun QIAN. Virtual machine scheduling model based on Shapley value modified genetic algorithm in cloud computing[J]. Telecommunications Science, 2022, 38(12): 1-10.

图/表 13

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

表1

轻度负载下4种算法的性能对比"

对比项	Max-Min	LrMmt	DE	SV-GA
SLA违背率	20.54%	30.64%	3.70%	0
迁移时间	9.02%	$- 21 . 09 %$	2.10%	0
迁移能耗	26.41%	45.76%	3.22%	0
迁移次数	12.74%	$- 11 . 55 %$	3.56%	0

表1

表2

重度负载下4种算法的性能对比"

对比项	Max-Min	LrMmt	DE	SV-GA
SLA违背率	10.27%	20.55%	0.92%	0
迁移时间	22.74%	$- 19 . 64 %$	2.58%	0
迁移能耗	37.54%	51.42%	6.94%	0
迁移次数	19.31%	$- 19 . 24 %$	4.43%	0

表2

参考文献 26

[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 Re-search 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 Com-puter 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.

云计算中基于Shapley值改进遗传算法的虚拟机调度模型

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

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 26

相关文章 15

Metrics

推荐阅读 0

[1]	韩雪. 基于电力大数据的电力骨干通信网络毁伤韧性评估方法[J]. 电信科学, 2023, 39(5): 136-143.
[2]	刘璐, 杨丹, 陈睿杰, 李嘉, 周熹. 基于KPCA-GA-BP神经网络的POI质量预测研究[J]. 电信科学, 2023, 39(1): 108-116.
[3]	邢文娟, 雷波, 赵倩颖. 算力基础设施发展现状与趋势展望[J]. 电信科学, 2022, 38(6): 51-61.
[4]	邓平科, 张同须, 施南翔, 张童, 邵天竺, 郑韶雯. 星算网络——空天地一体化算力融合网络新发展[J]. 电信科学, 2022, 38(6): 71-81.
[5]	邬江兴. 论网络技术体制发展范式的变革——网络之网络[J]. 电信科学, 2022, 38(6): 3-12.
[6]	章鹏, 金小萍, 陈东晓. 一种面向RDSM系统的基于遗传算法优化色散矩阵的方法[J]. 电信科学, 2022, 38(12): 46-55.
[7]	金小萍, 刘家瑜, 蒋晨, 郭强. 基于改进遗传算法的STSK系统色散矩阵和3D星座的联合优化[J]. 电信科学, 2021, 37(9): 86-94.
[8]	刘志勇, 何忠江, 阮宜龙, 单俊峰, 张超. 大数据安全特征与运营实践[J]. 电信科学, 2021, 37(5): 160-169.
[9]	许剑,靳莉. 一种可量化的云计算平台安全评估模型[J]. 电信科学, 2020, 36(7): 163-167.
[10]	姚晓辉,李青,孙焜焜. 一种域适配混合遗传算法及在安全服务链编排中的验证[J]. 电信科学, 2020, 36(5): 16-24.
[11]	罗斯宁,王化龙,李弘宇,彭蔚. 基于改进蚁群算法的云计算用户任务调度算法[J]. 电信科学, 2020, 36(2): 95-100.
[12]	胡文玉,王文举. 我国信息通信技术创新扩散效应及预测实证研究[J]. 电信科学, 2020, 36(1): 66-76.
[13]	雷波, 刘增义, 王旭亮, 杨明川, 陈运清. 基于云、网、边融合的边缘计算新方案：算力网络[J]. 电信科学, 2019, 35(9): 44-51.
[14]	高永梅,程冠杰. 基于边缘计算的数据密集型服务部署[J]. 电信科学, 2019, 35(7): 87-99.
[15]	鲁泽霖,李强治. 电子商务平台的演化逻辑和运营机理[J]. 电信科学, 2019, 35(7): 152-158.