基于Map-Reduce模型的云资源调度方法研究

摘要/Abstract

摘要： 为提高Map-Reduce模型资源调度问题的求解效能,分别考虑Map和Reduce阶段的调度过程,建立带服务质量(QoS)约束的多目标资源调度模型,并提出用于模型求解的混沌多目标粒子群算法。算法采用信息熵理论来维护非支配解集,以保持解的多样性和分布均匀性；在利用Sigma方法实现快速收敛的基础上,引入混沌扰动机制,以提高种群多样性和算法全局寻优能力,避免算法陷入局部最优。实验表明,算法求解所需的迭代次数少,得到的非支配解分布均匀。Map-Reduce资源调度问题的求解过程中,在收敛性和解集的多样性方面,所提算法均明显优于传统多目标粒子群算法。

关键词: 云计算,Map-Reduce,资源调度,粒子群算法,信息熵,混沌扰动

Abstract: To improve the computing efficiency of Map-Reduce resource scheduling,a multi-objective resource scheduling model with QoS restriction was built.The model considers the scheduling problem of both Map and Reduce phase.A chaotic multi-objective particle swarm algorithm was proposed to solve the model.The algorithm uses the information entropy theory to maintain non-dominated solution set so as to retain the diversity of solution and the uniformity of distribution.On the basis of using Sigma methods to achieve fast convergence,chaotic disturbance mechanism was introduced to improve the diversity of population and the ability of algorithm global optimization,which can avoid the algorithm to fall into local extremism.The experiments show that the number of iteration in the algorithm obtaining solutions is little and non-dominated solutions distribute equably.It indicates that the astringency and the diversity of solution set of this algorithm are better than the traditional multi-objective particle swarm algorithm in solving Map-Reduce resource scheduling problems.

Key words: Cloud computing,Map-Reduce,Resource scheduling,Particle swarm algorithm,Information entropy,Chaotic disturbance

张恒巍,韩继红,卫波,王晋东. 基于Map-Reduce模型的云资源调度方法研究[J]. 计算机科学, 2015, 42(8): 118-123. https://doi.org/

ZHANG Heng-wei, HAN Ji-hong, WEI Bo and WANG Jin-dong. Research on Cloud Resource Scheduling Method Based on Map-Reduce[J]. Computer Science, 2015, 42(8): 118-123. https://doi.org/

参考文献

[1] Buyya R,Yeo C S,Venugopal S,et al.Cloud computing and emerging IT platforms:vision,hype,and reality for delivering computing as the 5th utility [J].Future Generation Computer Systems,2009,25(6):599-616
[2] Armbrust M,Fox A,Griffith R,et al.A view of cloud computing [J].Communications of the ACM,2010,53(4):50-58
[3] 罗军舟,金嘉晖,宋爱波,等.云计算:体系架构与关键技术[J].通信学报,2011,2(7):3-21 Luo Jun-zhou,Jin Jia-hui,Song Ai-bo.et al.Cloud computing:architecture and key technologies[J].Journal on Communications,2011,2(7):3-21
[4] 王鹏.云计算的关键技术与应用实例[M].北京:科学出版社,2010:11-13 Wang Peng.Key technology and application example of cloud computing [M].Beijing:Science Press,2010:11-13
[5] Dean J,Ghemawat S.MapReduce:simplified data processing on large cluster[C]∥Proc of the 6th Conference on Symposium on Operating System Design and Implementation(SOSDI 2004).New York:ACM Press,2004:137-150
[6] 张春艳,刘清林,孟珂.基于云计算环境的蚁群优化计算资源分配[J].计算机应用,2012,2(5):1418-1420 Zhang Chun-yan,Liu qing-lin,Meng Ke,et al.Task allocation based on ant colony optimization in cloud computing [J].Journal of Computer Applications,2012,32(5):1418-1420
[7] 李建锋,彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用,2011,31(1):184-186 Li Jian-feng,Peng Jian.Task scheduling algorithm based on improved genetic algorithm in cloud computing environment[J].Journal of Computer Applications,2011,31(1):184-186
[8] 孙黎阳,林剑柠,毛少杰.基于改进粒子群优化算法的网络化仿真任务共同体服务选择[J].兵工学报,2012,33(11):1393-1403 Sun Li-yang,Lin Jian-ning,Mao Shao-jie,et al.Service Selection of Network Simulation Task Community Based on Improved Particle Swarm Optimization Algorithm[J].Acta Armamentarii,2012,33(11):1393-2002
[9] 梁静,许波,葛宇.基于改进蛙跳策略的Map-Reduce作业调度算法[J].计算机应用研究,2013,30(7):1999-2002 Liang Jing,Xu Bo,Ge Yu.Map-Reduce job scheduling algorithm based on improved shuffled frog leaping strategy[J].Application Research of Computers,2013,30(7):1999-2002
[10] 陆路.云环境下作业调度算法的研究[D].南京:南京理工大学,2013 Lu Lu.Research of job scheduling algorithms under cloud computing environment[D].Nanjing:Nanjing University of Science and Technology,2013
[11] 孙大为,常桂然,李凤云,等.一种基于免疫克隆的偏好多维QoS云资源调度优化算法[J].电子学报,2011,9(8):1824-1831 Sun Da-wei,Chang Gui-ran,Li Feng-yun,et al.Optimizing multi-dimensional QoS cloud resource scheduling by immune clonal with preference[J].Acta Electronica Sinica,2011,39(8):1824-1831
[12] 张伟星.基于粒子群优化算法的动态多目标优化算法研究及应用[D].郑州:郑州大学,2013 Zhang Wei-xing.The Research and Application of Dynamic Multi-objective Optimization Based on Particle Swarm Optimization[D].Zhengzhou:Zhengzhou University,2013
[13] 裴胜玉,周永权.一种基于混沌变异的多目标粒子群优化算法[J].山东大学学报(理学版),2010,45(7):18-23 Pei Sheng-yu,Zhou Yong-quan.A mult-objective particle swarm optimization algorithm based on the chaotic mutation [J].Journal of Shandong University(Natural Science),2010,45(7):18-23
[14] 郑金华.多目标进化算法及其应用[M].北京:科学出版社,2007:4-6 Zheng Jin-hua.Multi-objective evolution algorithm and its applications[M].Beijing:Science Press,2007:4-6
[15] Mostaghim S,Teich J.Strategies for finding good local guides in multi-objective particle swarm optimization[C]∥Proceeding of the 2003 IEEE Swarm Intelligence Symposium Indianapolis.Dallas:ACM Press,2003:26-33
[16] Fang Yi-qiu,Wang Fei,Ge Jun-wei.A task scheduling algorithm based on load balancing in cloud computing[C]∥Proceedings of the 2th International Conference on Web Information Systems and Mining.Berlin,Germany:Springer-Verlag,2010:156-162
[17] The Cloud Lab.Cloudsim[EB/OL].2011-08-15.http://www.cloudbus.org/cloudsim
[18] 2013 China Web Service Cup.Experiment Data Lab 2012.10.21.[EB/OL].http://debs.ict.ac.cn/2013

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed