改进K-means聚类的云任务调度算法

doi:10.3969/j.issn.1006-2475.2017.02.001

计算机与现代化

• 算法设计与分析 • 下一篇

改进K-means聚类的云任务调度算法

(北京交通大学计算机与信息技术学院，北京100044)

收稿日期:2016-06-30 出版日期:2017-03-09 发布日期:2017-03-20
作者简介:王欢(1991-)，女，山东聊城人，北京交通大学计算机与信息技术学院硕士研究生，研究方向：云计算，云测试; 李红辉(1964-)，女，研究员，硕士，研究方向：软件测试; 张骏温(1966-)，男，副研究员，博士，研究方向：软件测试，计算机网络。
基金资助:
国家863计划资助项目（2015AA043701）

Cloud Task Scheduling Algorithm Based on Modified K-means Clustering

(School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China)

Received:2016-06-30 Online:2017-03-09 Published:2017-03-20

摘要/Abstract

摘要： 针对云任务调度中存在的效率低、费用高等问题，提出一种基于改进K-means聚类算法的云任务调度算法。依据虚拟资源的硬件属性，使用改进聚类算法对虚拟资源进行聚类划分；计算任务偏好，使不同偏好的任务在不同的聚类中选择资源；考虑到调度费用问题，对每个聚类使用改进后的Min-min算法进行任务调度。针对K-means聚类算法初始聚类中心随机选取，易陷入局部最优解的问题，对聚类算法进行改进。最后，利用云仿真平台CloudSim进行实验，结果表明，与无聚类的调度算法相比，本文提出的算法在执行效率方面有所提高。

关键词: 云计算, K-means聚类, 调度, CloudSim

Abstract: Aiming at the problem of low efficiency and high cost in cloud task scheduling, a new cloud task scheduling algorithm based on modified K-means clustering is proposed. Based on the hardware properties of the virtual resources, the improved clustering algorithm is used to cluster the virtual resources. The task preferences are computed, so that different preferences of the task could select resources in different clusters. Taking into account the scheduling cost problem, the task scheduling is performed on each cluster by using the improved Min-min algorithm. We improve the K-means clustering algorithm aiming at the problem that the initial cluster centers are randomly selected and it is easy to fall into local optimal solution. Finally, the cloud simulation platform CloudSim is used to carry out the experiment, and the results show that the proposed algorithm can improve the efficiency compared with the non-clustering scheduling algorithms.

Key words: cloud computing, K-means clustering, scheduling, CloudSim

中图分类号:

TP399

王欢，李红辉，张骏温. 改进K-means聚类的云任务调度算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2017.02.001.

WANG Huan, LI Hong-hui, ZHANG Jun-wen. Cloud Task Scheduling Algorithm Based on Modified K-means Clustering[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2017.02.001.

参考文献

［1］罗军舟,金嘉晖,宋爱波,等. 云计算:体系架构与关键技术［J］. 通信学报, 2011,32(7):3-21.
［2］陈康,郑纬民. 云计算:系统实例与研究现状［J］. 软件学报, 2009,20(5):1337-1348.
［3］Baride S, Dutta K. A cloud based software testing paradigm for mobile applications［J］. ACM SIGSOFT Software Engineering Notes, 2011,36(3):1-4.
［4］李乔,郑啸. 云计算研究现状综述［J］. 计算机科学, 2011,38(4):32-37.
［5］黄璐. 基于遗传算法的云计算任务调度算法研究［D］. 厦门:厦门大学, 2014.
［6］顾宇隆. 云测试中并行任务的调度实现［D］. 上海:东华大学, 2014.
［7］曹萌萌. 基于云计算的调度算法的研究与改进［D］. 南京:南京邮电大学, 2013.
［8］范宗勤. 云环境下的资源调度算法研究［D］. 北京:北京交通大学, 2014.
［9］Candea G, Bucur S, Zamfir C. Automated software testing as a service［C］// Proceedings of the 1st ACM Symposium on Cloud Computing. 2010:155-160.
［10］Yu Lian, Tsai W T, Chen Xiangji, et al. Testing as a service over cloud［C］// Proceedings of the 5th IEEE International Symposium on Service Oriented System Engineering. 2010:181-188.
［11］李文娟,张启飞,平玲娣,等. 基于模糊聚类的云任务调度算法［J］. 通信学报, 2012,33(3):146-154.
［12］吴夙慧,成颖,郑彦宁,等. Kmeans算法研究综述［J］. 现代图书情报技术, 2011(5):28-35.
［13］雷小锋,谢昆青,林帆,等. 一种基于K-means局部最优性的高效聚类算法［J］. 软件学报, 2008,19(7):1683-1692.
［14］谢娟英,高红超. 基于统计相关性与K-means的区分基因子集选择算法［J］. 软件学报, 2014,25(9):2050-2075.
［15］Kokilavani T, Amalarethinarm G. Load balanced min-min algorithm for static meta-task scheduling in grid computing［J］. International Journal of Computer Applications, 2011,20(2):43-49.
［16］王参参. 基于云平台的软件测试任务的聚类和调度研究［D］. 南京:南京邮电大学, 2014.
［17］郑阳. 云测试中资源调度的研究［D］. 上海:华东理工大学, 2015.
［18］刘驰. 云仿真工具Cloudsim在虚拟机放置中的应用［J］. 计算机与数字工程, 2015,43(4):746-749.

[1]	王宏杰, 徐胜超, 杨波, 毛明扬, 蒋金陵. 基于SRv6技术的云网安全服务链自动编排方法[J]. 计算机与现代化, 2024, 0(01): 1-5.
[2]	何玉鹏, 陶勇, 王必恒, 赵英男. 智能配电网边缘计算研究现状与展望[J]. 计算机与现代化, 2023, 0(08): 87-92.
[3]	杨波, 徐胜超. 基于SRv6服务链的云网专线场景安全防护方法[J]. 计算机与现代化, 2023, 0(08): 107-111.
[4]	王艺成, 张国良, 张自杰, . 基于改进YOLOv5的小目标检测方法[J]. 计算机与现代化, 2023, 0(05): 100-105.
[5]	韩沐枫. 计及需求响应的微电网多时间尺度调度仿真[J]. 计算机与现代化, 2023, 0(03): 102-106.
[6]	周永福, 徐胜超. 基于双层规划的容器云资源动态配置算法[J]. 计算机与现代化, 2022, 0(12): 1-5.
[7]	毛明扬, 徐胜超. 可信赖云计算的通信终端攻击行为识别算法[J]. 计算机与现代化, 2022, 0(11): 37-42.
[8]	田云娜, 田园, 刘雪, 赵彦霖. 一种改进的求解柔性作业车间调度问题的灰狼算法[J]. 计算机与现代化, 2022, 0(08): 78-85.
[9]	曹禹, 李晓辉, 刘忠麟, 贾贺, 费志伟. 云环境大数据工作流编排管理系统研究综述[J]. 计算机与现代化, 2022, 0(01): 41-53.
[10]	徐明, 张剑铭, 陈松航, 陈豪. 柔性作业车间调度问题的多目标优化算法[J]. 计算机与现代化, 2021, 0(12): 1-6.
[11]	郑捷, 潘大志, . 改进的离散型萤火虫优化算法求解柔性作业车间调度问题 [J]. 计算机与现代化, 2021, 0(08): 11-15.
[12]	张晓敏. 基于布隆过滤器属性基的多关键词可搜索方案[J]. 计算机与现代化, 2021, 0(08): 104-111.
[13]	邓斌涛, 徐胜超. 基于动态双子种群的差分进化K中心点聚类算法[J]. 计算机与现代化, 2021, 0(07): 54-59.
[14]	吴君才, 刘雪芳. 基于云计算和深度信念网络的数字资源配置[J]. 计算机与现代化, 2021, 0(05): 78-82.
[15]	张鑫, 张旭, 张入文, 于琪琦, 王玉霞, 韦迎新, 黄宝贵. 无线网络中可靠的链路调度算法设计与分析[J]. 计算机与现代化, 2020, 0(12): 9-12.

改进K-means聚类的云任务调度算法

Cloud Task Scheduling Algorithm Based on Modified K-means Clustering

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价