计算机科学 ›› 2018, Vol. 45 ›› Issue (4): 137-142.doi: 10.11896/j.issn.1002-137X.2018.04.022

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

一种基于改进遗传算法的雾计算任务调度策略

韩奎奎,谢在鹏,吕鑫   

  1. 河海大学计算机与信息学院 南京211100,河海大学计算机与信息学院 南京211100,河海大学计算机与信息学院 南京211100
  • 出版日期:2018-04-15 发布日期:2018-05-11
  • 基金资助:
    本文受国家自然科学基金面上项目(61272543),NSFC-广东联合基金重点项目(U1301252)资助

Fog Computing Task Scheduling Strategy Based on Improved Genetic Algorithm

HAN Kui-kui, XIE Zai-peng and LV Xin   

  • Online:2018-04-15 Published:2018-05-11

摘要: 任务的调度与分配一直以来都是云计算技术发展中的关键问题。然而,随着物联网连接设备的爆炸式增长,云计算已不能满足一些任务的调度需求,如健康检测、应急响应等都需要较低的延迟,雾计算应运而生。雾计算将云的服务扩展到网络边缘。雾计算架构下的任务调度与分配目前还是一个较新的研究热点。文中介绍了一种改进的遗传算法(IGA),该算法将适应度判断引入到亲代变异操作中,克服了基本遗传算法(SGA)在变异操作中的盲目性。在雾计算架构下采用该算法调度任务时考虑了服务等级目标(SLO)中响应时间的约束(FOG-SLO-IGA)。实验结果表明,FOG-SLO-IGA调度用户任务时在时延、SLO违规率以及服务提供商的花费上均低于云计算架构下采用IGA的调度(CLOUD-IGA);同时,在雾端调度任务时,IGA算法在执行速度上要快于传统SGA算法和轮询调度算法(RRSA)。

关键词: 任务调度,云计算,雾计算,服务等级目标,遗传算法

Abstract: Task scheduling and assignment has always been a key issue in the development of cloud computing.However,with the explosive growth of internet connection devices,cloud computing has been unable to meet some requirements such as health monitoring,emergency response and so on,which all require low latency.Thus fog computing appears.Fog computing extends the cloud services to the edge of network.Under the fog computing architecture,task scheduling and assignment is still a relatively new research hotspot.This paper introduced an improved genetic algorithm(IGA).The algorithm introduces the fitness judgment into the parental mutation operation which overcomes the blindness of simple genetic algorithm(SGA) in mutation operation.The response time restriction in the service level objective(SLO) is considered when the IGA is used to schedule tasks(FOG-SLO-IGA).The experimental results show that when scheduling user tasks are under the fog computing architecture,FOG-SLO-IGA is superior to the scheduling which uses IGA under cloud computing architecture in latency,SLO violation rate and service provider’s cost.Futhermore,IGA algorithm is superior to the traditional SGA algorithm and the round-robin scheduling algorithm(RRSA) in the execution of the tasks under the fog computing architecture.

Key words: Task scheduling,Cloud computing,Fog computing,Service level objective,Genetic algorithm

[1] LI Q,ZHENG X.A Review of the Present Situation aboutCloud Computing[J].Computer Science,2011,8(4):32-37.(in Chinese) 李乔,郑啸.云计算研究现状综述[J].计算机科学,2011,8(4):32-37.
[2] LAI C F,WANG H,CHAO H C,et al.A Network and Device Aware QoS Approach for Cloud-Based Mobile Streaming[J].IEEE Transactions on Multimedia,2013,5(4):747-757.
[3] RIMAL B P,CHOI E,LUMB I.A Taxonomy and Survey of Cloud Computing Systems[C]∥International Joint Conference on Inc,Ims and IDC.IEEE,2009:44-51.
[4] MarketWatch:‘Cisco delivers vision of fog computing to acce-lerate value from billions of connected devices’.http://www.the-iet.org/resources/journals/research/index.cfm.
[5] BONOMI F,MILITO R,ZHU J,et al.Fog computing and itsrole in the internet of things[C]∥Proceedings of the First Edition of the MCC Workshop on Mobile Cloud Computing.ACM,2012:13-16.
[6] LUAN T H,GAO L,LI Z,et al.Fog computing:Focusing on mobile users at the edge[J].arXiv preprint arXiv:1502.01815,2015.
[7] AAZAM M,HUH E N.Fog computing and smart gatewaybased communication for cloud of things[C]∥2014 InternationalConference on Future Internet of Things and Cloud(FiCloud).IEEE,2014:464-470.
[8] AAZAM M,HUH E N.Fog Computing:The Cloud-IoT/IoE Middleware Paradigm[J].IEEE Potentials,2016,5(3):40-44.
[9] 北京物联远信息技术有限公司.一种面向物联网的雾计算架构:中国,201511019375.3[P/OL].(2016-05-25).http://www.soopat.com/patent/201511019375.
[10] GUPTA H,DASTJERDI A V,GHOSH S K,et al.i-FogSim:A Toolkit for Modeling and Simulation of Resource Management Techniques in Internet of Things,Edge and Fog Computing Environments[J].arXiv preprint arXiv:1606.02007,6.
[11] ZENG D,GU L,GUO S,et al.Joint Optimization of TaskScheduling and Image Placement in Fog Computing Supported Software-Defined Embedded System[J].IEEE Transactions on Computers,2016,5(12):3702-3712.
[12] HE X L,REN Z Y,SHI C H,et al.Cloud and Fog network for Medical Big Data and its Distributed Computing Scheme[J].Journal of Xi’an Jiaotong University,2016,0(10):71-77.(in Chinese) 何秀丽,任智源,史晨华,等.面向医疗大数据的云雾网络及其分布式计算方案[J].西安交通大学学报,2016,50(10):71-77.
[13] CHENG D M,LI Z.Hospital Information Service System Based on Fog Computing[J].Computer Science,2015,2(7):170-190.(in Chinese) 程冬梅,李志.基于雾计算的医院信息服务系统[J].计算机科学,2015,42(7):170-190.
[14] SARKAR S,MISRA S.Theoretical modelling of fog computing:a green computing paradigm to support IoT applications[J].IET Journals,2016,5(2):23-29.
[15] WU L.SLA-based resource provisioning for management ofCloud-based Software-as-a-Service applications[D].The University of Melbourne,2014.
[16] LI J F,PENG J.Task Scheduling Algorithm Based on Improved Genetic Algorithm in Cloud Computing Environment[J].Journal of Computer Application,2011,1(1):184-186.(in Chinese) 李剑锋,彭舰.云环境下基于改进遗传算法的任务调度算法[J].计算机应用,2011,1(1):184-186.
[17] CHIANG M,ZHANG T.Fog and IoT:An Overvi-ew of Research Opportunities[J].IEEE Internet of Things Journal,2016,3(6):854-864.
[18] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1996:18-32.
[19] HE X L.A Generalized Genetic Algorithm for Task Scheduling[J].Computer Engineering,2010,6(17):184-186.(in Chinese) 贺晓丽.一种用于任务调度的广义遗传算法[J].计算机工程,2010,36(17):184-186.
[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 & Experience,2011,41(1):23-50.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 编辑部. 新网站开通,欢迎大家订阅![J]. 计算机科学, 2018, 1(1): 1 .
[2] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[3] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[4] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[5] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[6] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[7] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[8] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[9] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[10] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .