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