ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (9): 1909-1919.doi: 10.7544/issn1000-1239.2017.20160757

• 软件技术 • 上一篇    下一篇

移动云计算环境下任务调度的多目标优化方法

胡海洋,刘润华,胡华   

  1. (杭州电子科技大学计算机学院 杭州 310018) (复杂系统建模与仿真教育部重点实验室(杭州电子科技大学) 杭州 310018) (huhaiyang@hdu.edu.cn)
  • 出版日期: 2017-09-01
  • 基金资助: 
    国家自然科学基金项目(61572162,61272188);南京大学计算机软件新技术国家重点实验室开放基金项目(KFKT2014B15);江苏省自然科学基金项目(BK20131277)

Multi-Objective Optimization for Task Scheduling in Mobile Cloud Computing

Hu Haiyang, Liu Runhua, Hu Hua   

  1. (College of Computer Science, Hangzhou Dianzi University, Hangzhou 310018) (Key Laboratory of Complex Systems Modeling and Simulation (Hangzhou Dianzi University), Ministry of Education, Hangzhou 310018)
  • Online: 2017-09-01

摘要: 移动云计算技术可帮助移动用户在执行工作流任务时将一些任务迁移至云端服务器执行,从而节省移动设备的电池能耗,并提高计算能力.传统研究工作在进行移动云计算环境中的任务调度时缺乏对能耗和运行时间的联合优化.为了实现有效的任务调度,基于工作流图中任务执行的先后关系,分析了采用动态电压频率调节技术的移动设备处理器执行工作流任务的运行时间与能耗,并考虑了将任务通过无线信道迁移到云端服务器执行所需的时间,给出了能耗与执行时间联合优化的任务调度模型和目标方程.提出基于模拟退火算法的任务调度方法,分析了算法时间复杂度,进行了系统性的对比实验,评估了所提出方法的正确性和有效性.

关键词: 移动云计算, 工作流, 任务调度, 模拟退火, 多目标优化

Abstract: Mobile cloud computing provides effective help for mobile users to migrate their workflow tasks to cloud servers for executing due to the mobile device’s limited hardware capability and battery energy carried. When scheduling workflow tasks between mobile devices and cloud servers, it needs to consider both the energy consumed by the mobile device and the total amount of time needed for the workflow application. Traditional methods for scheduling workflow tasks in mobile cloud computing usually address only one of two issues: saving energy consumption or minimizing the time needed. They fail to provide methods for jointly optimizing the time and energy consumption at the same time. Based on the relations of workflow tasks, the time needed in the workflow application is computed due to the tasks scheduling between the cloud servers and the mobile devices that use the technique of dynamic voltage and frequency scaling. The energy consumption for executing tasks on the cloud server and mobile devices are modeled and computed. The scheduling scheme and objective function for jointly optimizing the time needed and energy consumption are proposed. Algorithms based on the simulated annealing are designed for the mobile devices. Their time complexities are analyzed. Extensive experiments are conducted for comparing the proposed methods with other research works, and the experimental results demonstrate the correctness and effectiveness of our approaches.

Key words: mobile cloud computing, workflow, task scheduling, simulated annealing, multi-objective optimization

中图分类号: