史雯隽,武继刚,罗裕春.针对移动云计算任务迁移的快速高效调度算法[J].计算机科学,2018,45(4):94-99, 116
针对移动云计算任务迁移的快速高效调度算法
Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading
投稿时间:2017-05-19  修订日期:2017-06-18
DOI:10.11896/j.issn.1002-137X.2018.04.014
中文关键词:  移动云计算,任务迁移,调度,启发式算法
英文关键词:Mobile cloud computing,Task offloading,Scheduling,Heuristic algorithm
基金项目:本文受国家自然科学基金资助
作者单位E-mail
史雯隽 天津工业大学计算机科学与软件学院 天津300387  
武继刚 广东工业大学计算机学院 广州510006 asjgwucn@outlook.com 
罗裕春 广东工业大学计算机学院 广州510006  
摘要点击次数: 258
全文下载次数: 191
中文摘要:
      计算量较大的应用程序由于需要大量的能耗,因此在电池容量有限的移动设备上运行时十分受限。云计算迁移技术是保证此类应用程序在资源有限的设备上运行的主流方法。针对无线网络中应用程序任务图的调度和迁移问题,提出了一种快速高效的启发式算法。该算法将能够迁移到云端的任务都安排在云端完成这种策略作为初始解,通过逐次计算可迁移任务在移动端运行的能耗节省量,依次将节省量最大的任务迁移到移动端,并依据任务间的通讯时间及时更新各个任务的能耗节省量。为了寻找全局最优解,构造了适用于此问题的禁忌搜索算法,给出了相应的编码方法、禁忌表、邻域解以及算法终止准则。构造的禁忌搜索算法以提出的启发式解为初始解进行全局搜索,并实现对启发解的进一步优化。通过 实验 将所提方法与无迁移、随机迁移、饱和迁移3类算法进行对比,结果表明提出的启发式算法能够快速有效地给出能耗更小的解。例如,在宽度为10的任务图上,当深度为8时,无迁移、随机迁移与饱和迁移的能耗分别为5461、3357和2271能量单位,而给出的启发解对应的能耗仅为2111。在此基础上禁忌搜索算法又将其能耗降低到1942, 这进一步说明了提出的启发式算法能够产生高质量的近似解。
英文摘要:
      Running applications of high computation on mobile devices is constrained by limited battery capacity and energy consumption of the devices.Cloud offloading is a main solution for supporting computationally demanding applications on these resource-constrainted devices.This paper proposed a fast and efficient heuristic approach for scheduling and offloading problems of the application task graph in the wireless network.The proposed heuristic approach initially moves the tasks that can be offloaded to the cloud,and then iteratively moves the tasks with highest benefit value to the mobile device.The benefit values are updated in each iteration to cater for the task concurrence.In addition,this paper also constructed a tabu search approach to search for the global optimization solution.It presented and implemented the encoding method,tabu list,neighborhood solutions and the stopping criterion of the proposed tabu search algorithm. The customized tabu search algorithm is with the initial solution generated by the proposed heuristic algorithm.By comparing three algorithms based on non-offloading,full offloading,and random offloading,experimental results show that the proposed heuristic algorithm runs very fast,and the generated heuristic solutions are efficient.For the case of the task graphs with width of 10 and depth of 8,the energy consumption of non-offloading,full offloading,and random offloading are 5461,7 and 2271 respectively,while the proposed heuristic solution is 2111.It is further reduced to 1942 by the customized tabu search.The results confirm that the proposed heuristic algorithm can generate high quality approximate solution for the scheduling and offloading problem in mobile computing.
查看全文  查看/发表评论  下载PDF阅读器