计算机科学 ›› 2019, Vol. 46 ›› Issue (6): 135-142.doi: 10.11896/j.issn.1002-137X.2019.06.020

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

MC2ETS:移动云计算中一种能效任务调度算法

叶符明, 李雯婷, 王颖   

  1. (贵州商学院计算机与信息工程学院 贵阳550014)
  • 收稿日期:2018-01-29 发布日期:2019-06-24
  • 通讯作者: 李雯婷(1984-),女,博士,副教授,主要研究领域为大数据分析,E-mail:wendyworkmail@163.com
  • 作者简介:叶符明(1978-),女,硕士,副教授,主要研究领域为大数据、云计算;王 颖(1982-),女,硕士,讲师,主要研究领域为计算机应用。
  • 基金资助:
    贵州省普通高等学校工程研究中心基金项目(黔教合KY字[016]),贵州省教育厅青年科技人才成长项目(黔教合KY字[237])资助。

MC2ETS:An Energy-efficient Tasks Scheduling Algorithm in Mobile Cloud Computing

YE Fu-ming, LI Wen-ting, WANG Ying   

  1. (School of Computer and Information Engineering,Guizhou University of Commerce,Guiyang 550014,China)
  • Received:2018-01-29 Published:2019-06-24

摘要: 移动云计算可以使执行于移动设备上的任务迁移至云端执行,达到降低移动设备能耗、提高任务执行效率的目的。文中研究了移动云计算中DAG模型的任务调度问题,为了解决传统调度算法缺乏对任务完成时间和移动设备能耗的同步优化问题,提出了一种移动云计算的能效任务调度算法MC2ETS(Energy-efficient Tasks Scheduling of Mobile Cloud Computing)。该算法主要包括3个步骤:1)以最小化应用完成时间为目标进行初始调度;2)在满足应用完成时间约束的同时,以最小化能耗为目标进行任务调度迁移;3)通过提出的DVFS(Dynamic Voltage/Frequency Scale)算法进一步降低能耗。通过具体的实例验证了算法的可行性,并分析了算法的时间复杂度。最后,通过与基准算法的系统性实验对比分析,证明了算法在多数情况下可以在调度时间指标与移动设备能耗间实现均衡优化。

关键词: 均衡优化, 能效, 任务调度, 任务迁移, 移动云计算

Abstract: Mobile cloud computing can migrate the tasks scheduled on mobile devices to cloud,which can reduce the ene-rgy consumption of mobile device and improve the tasks execution efficiency.Tasks scheduling problem with Directed Acyclic Graph (DAG) model in mobile cloud computing was studied.Traditional methods for scheduling tasks usually are short of optimizing synchronous both tasks completion time and energy consumption of mobile device,an energy-efficient tasks scheduling algorithm of mobile cloud computing (MC2ETS) was presented in this paper.The algorithm consists of three steps.Firstly,the initial scheduling is carried out to minimize the application completion time.Then the task scheduling migration is conducted based on minimizing the energy consumption,while satisfying the constraint of application completion time.At last,through DVFS(Dynamic Voltage/Frequency Scale) algorithm,the energy consumption is reduced further.The feasibility of the proposed algorithm was verified through the specific example,and the time complexity of the proposed algorithm was analyzed.Finally,through the systemic experimental analysis compared with the baseline algorithms,this paper proved that the proposed algorithm can achieve the trade-off optimization between the scheduling time index and the energy consumption of mobile device in most cases.

Key words: Energy-efficient, Mobile cloud computing, Tasks migration, Tasks scheduling, Trade-off optimization

中图分类号: 

  • TP393
[1]PEDRAM M.A semi-Markovian decision process based control method for offloading tasks from mobile devices to the cloud[C]∥Proceedings of the 2013 International Conference on Global Communication.IEEE,2013:2885-2890.
[2]ZARE J,ABOLFAZLI S,SHOJAFAR M,et al.Resource Sche-duling in Mobile Cloud Computing:Taxonomy and Open Challenges[C]∥IEEE International Conference on Data Science and Data Intensive Systems.IEEE Computer Society,2015:594-603.
[3]BARBERA M V,KOSTA S,MEI A,et al.To Offload or Not to Offload?The Bandwidth and Energy Costs of Mobile Cloud Computing[J].Proceedings-IEEE INFOCOM,2015,12(11):1285-1293.
[4]ZHOU B,DASTJERDI A V,CALHEIROS R N,et al.A Context Sensitive Offloading Scheme for Mobile Cloud Computing Service[C]∥IEEE,International Conference on Cloud Computing.IEEE,2015:869-876.
[5]ATRE H,RAZDAN K,SAGAR R K.A review of mobile cloud computing[C]∥Cloud System and Big Data Engineering.IEEE,2016:199-202.
[6]BALAMURUGAN M,AKILA V.Effective processor selection on heterogeneous computing[C]∥International Conference on Science Technology Engineering and Management.IEEE,2016:13-16.
[7]FENG B,GAO J.Distributed Parallel Needleman-Wunsch Algorithm on Heterogeneous Cluster System[C]∥International Conference on Network and Information Systems for Compu-ters.IEEE,2016:358-361.
[8]RA M R,SHETH A,MUMMERT L,et al.Odessa:enabling in-teractive perception applications on mobile devices[C]∥International Conference on Mobile Systems,Applications,and Ser-vices.ACM,2011:43-56.
[9]YANG L,CAO J,TANG S,et al.A Framework for Partitioning and Execution of Data Stream Applications in Mobile Cloud Computing[J].Acm Sigmetrics Performance Evaluation Review,2013,40(4):23-32.
[10]TERZOPOULOS G,KARATZA H D.Dynamic Voltage Scaling Scheduling on Power-Aware Clusters under Power Constraints[C]∥IEEE/ACM,International Symposium on Distributed Simulation and Real Time Applications.IEEE,2013:72-78.
[11]GOUDARZI M,ZAMANI M,HAGHIGHAT A T.A fast hybrid multi-site computation offloading for mobile cloud computing[J].Journal of Network & Computer Applications,2017,80(1):219-231.
[12]SARAVANAN S,VENKATACHALAM V.Advance Map Reduce Task Scheduling algorithm using mobile cloud multimedia services architecture[C]∥Sixth International Conference on Advanced Computing.IEEE,2015:21-25.
[13]ELGAZZAR K,MARTIN P,HASSANEIN H S.Cloud-Assisted Computation Offloading to Support Mobile Services[J].IEEE Transactions on Cloud Computing,2016,4(3):279-292.
[14]LIU Z,ZENG X,HUANG W,et al.Framework for Context-Aware Computation Offloading in Mobile Cloud Computing[C]∥International Symposium on Parallel and Distributed Computing.IEEE,2017:172-177.
[15]DESHMUKH N V,DEORANKAR A V.Minimizing energy consumption in transmission efficient wireless sensor network[C]∥International Conference on Advances in Electrical,Electronics,Information,Communication and Bio-Informatics.IEEE,2016:475-479.
[16]LI J,LI X,ZHANG R.Energy-and-Time-Saving Task Scheduling Based on Improved Genetic Algorithm in Mobile Cloud Computing[C]∥International Conference on Collaborative Computing:Networking,Applications and Worksharing.Sprin-ger,Cham,2016:418-428.
[17]KLIAZOVICH D,PECERO J E,TCHERNYKH A,et al.CA-DAG:Communication-Aware Directed Acyclic Graphs for Mo-deling Cloud Computing Applications[C]∥IEEE Sixth International Conference on Cloud Computing.IEEE,2013:277-284.
[1] 田冰川, 田臣, 周宇航, 陈贵海, 窦万春.
减少Hadoop集群中网络队头阻塞的调度算法
Reducing Head-of-Line Blocking on Network in Hadoop Clusters
计算机科学, 2022, 49(3): 11-22. https://doi.org/10.11896/jsjkx.210900117
[2] 谭双杰, 林宝军, 刘迎春, 赵帅.
基于机器学习的分布式星载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
[3] 沈彪, 沈立炜, 李弋.
空间众包任务的路径动态调度方法
Dynamic Task Scheduling Method for Space Crowdsourcing
计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[4] 陈乐, 高岭, 任杰, 党鑫, 王祎昊, 曹瑞, 郑杰, 王海.
基于自适应码率移动增强现实应用的能效优化研究
Adaptive Bitrate Streaming for Energy-Efficiency Mobile Augmented Reality
计算机科学, 2022, 49(1): 194-203. https://doi.org/10.11896/jsjkx.201100107
[5] 王政, 姜春茂.
一种基于三支决策的云任务调度优化算法
Cloud Task Scheduling Algorithm Based on Three-way Decisions
计算机科学, 2021, 48(6A): 420-426. https://doi.org/10.11896/jsjkx.201000023
[6] 程云飞, 田红心, 刘祖军.
NOMA系统异构网络中联合用户关联和功率控制协同优化
Collaborative Optimization of Joint User Association and Power Control in NOMA Heterogeneous Network
计算机科学, 2021, 48(3): 269-274. https://doi.org/10.11896/jsjkx.191100213
[7] 蔡凌峰, 魏祥麟, 邢长友, 邹霞, 张国敏.
故障场景下的边缘计算DAG任务重调度方法
Failure-resilient DAG Task Rescheduling in Edge Computing
计算机科学, 2021, 48(10): 334-342. https://doi.org/10.11896/jsjkx.210300304
[8] 张龙信, 周立前, 文鸿, 肖满生, 邓晓军.
基于异构云计算的成本约束下的工作流能量高效调度算法
Energy Efficient Scheduling Algorithm of Workflows with Cost Constraint in Heterogeneous Cloud Computing Systems
计算机科学, 2020, 47(8): 112-118. https://doi.org/10.11896/jsjkx.200300038
[9] 金小敏, 滑文强.
移动云计算中面向能耗优化的资源管理
Energy Optimization Oriented Resource Management in Mobile Cloud Computing
计算机科学, 2020, 47(6): 247-251. https://doi.org/10.11896/jsjkx.190400020
[10] 孙敏, 陈中雄, 叶侨楠.
云环境下基于HEDSM的工作流调度策略
Workflow Scheduling Strategy Based on HEDSM Under Cloud Environment
计算机科学, 2020, 47(6): 252-259. https://doi.org/10.11896/jsjkx.190400047
[11] 胡锦天, 王高才, 徐晓桐.
移动边缘计算中具有能耗优化的任务迁移策略
Task Migration Strategy with Energy Optimization in Mobile Edge Computing
计算机科学, 2020, 47(6): 260-265. https://doi.org/10.11896/jsjkx.190400074
[12] 王妍, 韩笑, 曾辉, 刘荆欣, 夏长清.
边缘计算环境下服务质量可信的任务迁移节点选择
Task Migration Node Selection with Reliable Service Quality in Edge Computing Environment
计算机科学, 2020, 47(10): 240-246. https://doi.org/10.11896/jsjkx.190900054
[13] 胡俊钦, 张佳俊, 黄引豪, 陈星, 林兵.
边缘环境下DNN应用的计算迁移调度技术
Computation Offloading Scheduling Technology for DNN Applications in Edge Environment
计算机科学, 2020, 47(10): 247-255. https://doi.org/10.11896/jsjkx.190900106
[14] 王瑄, 毛莺池, 谢在鹏, 黄倩.
基于差分进化的推断任务卸载策略
Inference Task Offloading Strategy Based on Differential Evolution
计算机科学, 2020, 47(10): 256-262. https://doi.org/10.11896/jsjkx.190800159
[15] 陈晓杰,周清雷,李斌.
基于FPGA的7-Zip加密文档高能效口令恢复方法
Energy-efficient Password Recovery Method for 7-Zip Document Based on FPGA
计算机科学, 2020, 47(1): 321-328. https://doi.org/10.11896/jsjkx.190100027
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!