计算机科学 ›› 2019, Vol. 46 ›› Issue (6): 135-142.doi: 10.11896/j.issn.1002-137X.2019.06.020
叶符明, 李雯婷, 王颖
YE Fu-ming, LI Wen-ting, WANG Ying
摘要: 移动云计算可以使执行于移动设备上的任务迁移至云端执行,达到降低移动设备能耗、提高任务执行效率的目的。文中研究了移动云计算中DAG模型的任务调度问题,为了解决传统调度算法缺乏对任务完成时间和移动设备能耗的同步优化问题,提出了一种移动云计算的能效任务调度算法MC2ETS(Energy-efficient Tasks Scheduling of Mobile Cloud Computing)。该算法主要包括3个步骤:1)以最小化应用完成时间为目标进行初始调度;2)在满足应用完成时间约束的同时,以最小化能耗为目标进行任务调度迁移;3)通过提出的DVFS(Dynamic Voltage/Frequency Scale)算法进一步降低能耗。通过具体的实例验证了算法的可行性,并分析了算法的时间复杂度。最后,通过与基准算法的系统性实验对比分析,证明了算法在多数情况下可以在调度时间指标与移动设备能耗间实现均衡优化。
中图分类号:
[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 |
|