计算机科学 ›› 2019, Vol. 46 ›› Issue (6A): 295-299.

• 网络与通信 • 上一篇    下一篇

基于博弈论的云资源调度算法

徐飞1,2, 王少昌1, 杨卫霞1   

  1. 西安工业大学计算机科学与工程学院 西安7100211;
    西北工业大学航海学院 西安7100722
  • 出版日期:2019-06-14 发布日期:2019-07-02
  • 作者简介:徐 飞(1980-),男,博士,副教授,主要研究方向为中间件、分布式计算,E-mail:29112462@qq.com;王少昌(1991-),男,硕士生,主要研究方向为云机器人;杨卫霞(1993-),女,硕士生,主要研究方向为云机器人。
  • 基金资助:
    本文受国家自然科学基金(51179156),陕西省教育厅科学研究项目计划(15JK1364)资助。

Cloud Resource Scheduling Algorithm Based on Game Theory

XU Fei1,2, WANG Shao-chang1, YANG Wei-xia1   

  1. School of Computer Science and Engineering,Xi'an Technological University,Xi'an710021,China1;
    School of Marine Engineering,Northwestern Polytechnical University,Xi'an 710072,China2
  • Online:2019-06-14 Published:2019-07-02

摘要: 在云环境下的大数据中心中,虚拟机数目和虚拟机的负载会随着用户和应用的需求而时常发生变化。虚拟机需要进行动态资源调整,及时移除系统中的热点资源,从而达到整个系统的负载均衡。通过对云资源分配的理论研究,获取到First-Fit贪心算法和Round Robin轮询算法等。将它们应用到一些云系统中虽然能够在短时间内解决问题,但存在资源利用率和负载均衡等方面的问题。文中提出一种基于博弈论的FUTG(Fairness-Utilization Tradeoff Gme)云资源调度算法。该算法打破了固定数量的资源分配瓶颈,将QoS因素纳入考量范围,解决了资源利用率以及资源分配的公平性这两个优化目标的资源调度问题。仿真实验结果表明,FUTG算法能够显著提高动态资源调度的有效性和动态负载下资源使用的执行效率。

关键词: FUTG, 博弈论, 动态负载, 服务质量, 云资源调度

Abstract: In a large data center in a cloud environment,the number of virtual machines and the load of virtual machines change frequently with the needs of users and applications.The virtual machines need to make dynamic resource adjustments to remove hotspot resources in the system in time and implement load banlancing for the entire system.Now through theoretical research on cloud resource allocation,we have obtained such applications as First-Fit greedy algorithm and Round Robin polling algorithm that can be applied to some cloud systems to solve problems in a short time,but they have the problems of resource utilization and load.Therefore,this paper proposed a fuzzy-future-memory tradeoff (GMO) cloud resource scheduling algorithm based on game theory.The algorithm breaks a fixed number of resource allocation bottlenecks,takes QoS into consideration,and solves problems of resource utilization and resource allocation fairness.Simulation results show that FUTG algorithm can significantly improve the effectiveness of dynamic resource scheduling and the efficiency of resource usage under dynamic load.

Key words: Cloud resources dispatch, Dynamic load, FUTG, Game theory, QoS

中图分类号: 

  • TP18
[1]XIN J,KWONG K Y,YONG Y.Competitive Cloud Resource Procurements via Cloud Brokerage[C]∥Proceedings of the 5th IEEE International Conference on Cloud Computing Technology and Science.IEEE,2016:355-362.
[2]OSORIO I,ZAVERI H,FREI MG,et al.Epilepsy:the intersection-of-neurosciences,biology,mathematics,engineering and physics [M].CRC,2015.
[3]CARROLL T E,GROSU D.Formation of virtual organizations in grids:a game-theoretic approach[J].Concurrency and Computation:PracticeandExperience,2017,22(14):1972-1989.
[4]HASSAN M,SONG B,HUB E N.Game-based distributed re-source allocation in horizontal dynamic cloud federation platform[M]∥Algorithms and Architectures for Parallel Processing.Berlin:Springer,2011:194-205.
[5]张晞.云计算环境下改进的虚拟机资源调度算法研究[J].科技通报,2018,34(2):155-158 [6]丁丁,艾丽华,罗四维,等.基于用户行为反馈的云资源调度机制[J].系统工程与电子技术,2018,40(1):209-216.
[7]史宝鹏,段迅,孔广黔,等.医疗云平台资源调度策略研究[J].计算机工程,2017,43(8):44-48,55.
[8]MITTAL A,KAUR P D.Genetic based QoS task scheduling in cloud-upgrade genetic algorithm[J].International Journal of Grid and Distributed Computing,2015,8(4):145-152.
[9]PANDITD,CHATTOPADHYAYS,CHATTOPADHYAY M,et al.Resource allocation in cloud using simulated annealing[C]∥Proc. of the International Conference on Applications and Innovations in Moble Computing.2014:21-27.
[10]张永强,徐宗昌,呼凯凯,等.基于私有云和改进粒子群算法的约束优化求解[J].系统工程与电子技术,2016,38(5):1086-1092.
[11]SINGH J,MISHRA S.Improved ant colony load balancing algorithm in cloud computing[J].International Journal of Compu-ters and Technology,2015,4(3):5636-5644.
[12]李智勇,陈少淼,杨波,等.异构云环境多目标Memetic优化任务调度方法[J].计算机学报,2016,39(2):377-390.
[13]WANG W,LI B,LIANG B.Dominant resource fairness in cloud computing systems with heterogeneous servers[J].arXiv:1308.0083,2013.
[14]MATTHEWS J N,ANDERSON T E.22nd symposium on Operating systems principles[C]∥ACM Symposium on Operating Systems.Principles,ACM,2009:261-276.
[15]齐平,王福成,王必晴.一种基于图模型的可信云资源调度算法[J].山东大学学报(理学版),2018,53(1):63-74.
[16]王涛,杨喆.数据中心中云计算资源调度算法的浅入分析[J].自动化技术与应用,2018,37(1):47-48,59.
[17]王琛,汤红波,游伟,等.一种5G网络低时延资源调度算法[J].西安交通大学学报,2018(4):1-7.
[18]徐昕.基于博弈论的云计算资源调度方法研究[D].上海:华东理工大学,2015.
[19]李超,戴炳荣,旷志光,等.云计算环境下基于改进遗传算法的多维约束任务调度研究[J].小型微型计算机系统,2017,38(9):1945-1949.
[20]张素芹,徐飞.多目标约束条件的云计算资源调度算法仿真[J].价值工程,2017,36(22):216-218.
[1] 姜洋洋, 宋丽华, 邢长友, 张国敏, 曾庆伟.
蜜罐博弈中信念驱动的攻防策略优化机制
Belief Driven Attack and Defense Policy Optimization Mechanism in Honeypot Game
计算机科学, 2022, 49(9): 333-339. https://doi.org/10.11896/jsjkx.220400011
[2] 方韬, 杨旸, 陈佳馨.
D2D辅助移动边缘计算下的卸载策略优化
Optimization of Offloading Decisions in D2D-assisted MEC Networks
计算机科学, 2022, 49(6A): 601-605. https://doi.org/10.11896/jsjkx.210200114
[3] 胥昊, 曹桂均, 闫璐, 李科, 王振宏.
面向铁路集装箱的高可靠低时延无线资源分配算法
Wireless Resource Allocation Algorithm with High Reliability and Low Delay for Railway Container
计算机科学, 2022, 49(6): 39-43. https://doi.org/10.11896/jsjkx.211200143
[4] 杨玉丽, 李宇航, 邓岸华.
面向个性化需求的云制造服务可信评价模型
Trust Evaluation Model of Cloud Manufacturing Services for Personalized Needs
计算机科学, 2022, 49(3): 354-359. https://doi.org/10.11896/jsjkx.210200116
[5] 谭双杰, 林宝军, 刘迎春, 赵帅.
基于机器学习的分布式星载RTs系统负载调度算法
Load Scheduling Algorithm for Distributed On-board RTs System Based on Machine Learning
计算机科学, 2022, 49(2): 336-341. https://doi.org/10.11896/jsjkx.201200126
[6] 姚娟, 邢镔, 曾骏, 文俊浩.
云制造服务组合研究综述
Survey on Cloud Manufacturing Service Composition
计算机科学, 2021, 48(7): 245-255. https://doi.org/10.11896/jsjkx.200800173
[7] 孙明玮, 司维超, 董琪.
基于多维度数据的网络服务质量的综合评估研究
Research on Comprehensive Evaluation of Network Quality of Service Based on Multidimensional Data
计算机科学, 2021, 48(6A): 246-249. https://doi.org/10.11896/jsjkx.200900131
[8] 郑增乾, 王锟, 赵涛, 蒋维, 孟利民.
带宽和时延受限的流媒体服务器集群负载均衡机制
Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster
计算机科学, 2021, 48(6): 261-267. https://doi.org/10.11896/jsjkx.200400131
[9] 刘邦邦, 易国洪, 黄祖源.
面向Docker容器的动态负载算法
Dynamic Loading Algorithm for Docker Container
计算机科学, 2021, 48(6): 276-281. https://doi.org/10.11896/jsjkx.200500152
[10] 陆懿帆, 曹芮浩, 王俊丽, 闫春钢.
一种基于微服务的检察业务服务封装方法
Method of Encapsulating Procuratorate Affair Services Based on Microservices
计算机科学, 2021, 48(2): 33-40. https://doi.org/10.11896/jsjkx.191100152
[11] 蒋建峰, 尤澜涛.
基于MPLS-TE的数据中心网络QoS优化
QoS Optimization of Data Center Network Based on MPLS-TE
计算机科学, 2021, 48(11A): 485-489. https://doi.org/10.11896/jsjkx.210900190
[12] 杨章林, 谢钧, 张耕强.
基于定向天线的飞行自组网定向路由协议综述
Review of Directional Routing Protocols for Flying Ad-Hoc Networks Based on Directional Antennas
计算机科学, 2021, 48(11): 334-344. https://doi.org/10.11896/jsjkx.210400182
[13] 魏礼奇, 赵志宏, 白光伟, 沈航.
基于生成对抗网络的位置隐私博弈机制
Location Privacy Game Mechanism Based on Generative Adversarial Networks
计算机科学, 2021, 48(10): 266-271. https://doi.org/10.11896/jsjkx.200900021
[14] 毛莺池, 周彤, 刘鹏飞.
基于延迟接受的多用户任务卸载策略
Multi-user Task Offloading Based on Delayed Acceptance
计算机科学, 2021, 48(1): 49-57. https://doi.org/10.11896/jsjkx.200600129
[15] 包峻波, 闫光辉, 李俊成.
结合非完全信息博弈的SIR传播模型
SIR Propagation Model Combing Incomplete Information Game
计算机科学, 2020, 47(6): 230-235. https://doi.org/10.11896/jsjkx.190400164
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!