首页 | 官方网站   微博 | 高级检索  
     

针对移动云计算任务迁移的快速高效调度算法
引用本文:史雯隽,武继刚,罗裕春.针对移动云计算任务迁移的快速高效调度算法[J].计算机科学,2018,45(4):94-99, 116.
作者姓名:史雯隽  武继刚  罗裕春
作者单位:天津工业大学计算机科学与软件学院 天津300387,广东工业大学计算机学院 广州510006,广东工业大学计算机学院 广州510006
基金项目:本文受国家自然科学基金资助
摘    要:计算量较大的应用程序由于需要大量的能耗,因此在电池容量有限的移动设备上运行时十分受限。云计算迁移技术是保证此类应用程序在资源有限的设备上运行的主流方法。针对无线网络中应用程序任务图的调度和迁移问题,提出了一种快速高效的启发式算法。该算法将能够迁移到云端的任务都安排在云端完成这种策略作为初始解,通过逐次计算可迁移任务在移动端运行的能耗节省量,依次将节省量最大的任务迁移到移动端,并依据任务间的通讯时间及时更新各个任务的能耗节省量。为了寻找全局最优解,构造了适用于此问题的禁忌搜索算法,给出了相应的编码方法、禁忌表、邻域解以及算法终止准则。构造的禁忌搜索算法以提出的启发式解为初始解进行全局搜索,并实现对启发解的进一步优化。通过 实验 将所提方法与无迁移、随机迁移、饱和迁移3类算法进行对比,结果表明提出的启发式算法能够快速有效地给出能耗更小的解。例如,在宽度为10的任务图上,当深度为8时,无迁移、随机迁移与饱和迁移的能耗分别为5461、3357和2271能量单位,而给出的启发解对应的能耗仅为2111。在此基础上禁忌搜索算法又将其能耗降低到1942, 这进一步说明了提出的启发式算法能够产生高质量的近似解。

关 键 词:移动云计算  任务迁移  调度  启发式算法
收稿时间:2017/5/19 0:00:00
修稿时间:2017/6/18 0:00:00

Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading
SHI Wen-jun,WU Ji-gang and LUO Yu-chun.Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J].Computer Science,2018,45(4):94-99, 116.
Authors:SHI Wen-jun  WU Ji-gang and LUO Yu-chun
Affiliation:School of Computer Science and Software Engineering,Tianjin Polytechnic University,Tianjin 300387,China,School of Computer,Guangdong University of Technology,Guangzhou 510006,China and School of Computer,Guangdong University of Technology,Guangzhou 510006,China
Abstract: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.
Keywords:Mobile cloud computing  Task offloading  Scheduling  Heuristic algorithm
点击此处可从《计算机科学》浏览原始摘要信息
点击此处可从《计算机科学》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号