计算机科学 ›› 2018, Vol. 45 ›› Issue (4): 94-99, 116.doi: 10.11896/j.issn.1002-137X.2018.04.014

• 2017年全国理论计算机科学学术年会 • 上一篇    下一篇

针对移动云计算任务迁移的快速高效调度算法

史雯隽,武继刚,罗裕春   

  1. 天津工业大学计算机科学与软件学院 天津300387,广东工业大学计算机学院 广州510006,广东工业大学计算机学院 广州510006
  • 出版日期:2018-04-15 发布日期:2018-05-11
  • 基金资助:
    本文受国家自然科学基金资助

Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading

SHI Wen-jun, WU Ji-gang and LUO Yu-chun   

  • Online:2018-04-15 Published:2018-05-11

摘要: 计算量较大的应用程序由于需要大量的能耗,因此在电池容量有限的移动设备上运行时十分受限。云计算迁移技术是保证此类应用程序在资源有限的设备上运行的主流方法。针对无线网络中应用程序任务图的调度和迁移问题,提出了一种快速高效的启发式算法。该算法将能够迁移到云端的任务都安排在云端完成这种策略作为初始解,通过逐次计算可迁移任务在移动端运行的能耗节省量,依次将节省量最大的任务迁移到移动端,并依据任务间的通讯时间及时更新各个任务的能耗节省量。为了寻找全局最优解,构造了适用于此问题的禁忌搜索算法,给出了相应的编码方法、禁忌表、邻域解以及算法终止准则。构造的禁忌搜索算法以提出的启发式解为初始解进行全局搜索,并实现对启发解的进一步优化。通过 实验 将所提方法与无迁移、随机迁移、饱和迁移3类算法进行对比,结果表明提出的启发式算法能够快速有效地给出能耗更小的解。例如,在宽度为10的任务图上,当深度为8时,无迁移、随机迁移与饱和迁移的能耗分别为5461、3357和2271能量单位,而给出的启发解对应的能耗仅为2111。在此基础上禁忌搜索算法又将其能耗降低到1942, 这进一步说明了提出的启发式算法能够产生高质量的近似解。

关键词: 移动云计算,任务迁移,调度,启发式算法

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.

Key words: Mobile cloud computing,Task offloading,Scheduling,Heuristic algorithm

[1] DINH H T,LEE C,NIYATO D,et al.A survey of mobile cloud computing:architecture,applications,and approaches [J].Wireless Communications & Mobile Computing,2013,13(18):1587-1611.
[2] BARBAROSSA S,SARDELLITTI S,LORENZO P D.Communicating While Computing:Distributed mobile cloud computing over 5G heterogeneous networks [J].IEEE Signal Processing Magazine,2014,31(6):45-55.
[3] KUMAR K,LU Y H.Cloud Computing for Mobile Users:Can Offloading Computation Save Energy? [M].IEEE Computer Society Press,2010.
[4] VALLINA-RODRIGUEZ N,CROWCROFT J.Energy Management Techniques in Modern Mobile Handsets [J].IEEE Communications Surveys & Tutorials,2013,15(1):179-198.
[5] KEPHART J O,CHESS D M.The Vision of Autonomic Computing [J].Computer,2003,36(1):41-50.
[6] SHU P,LIU F,JIN H,et al.eTime:Energy-efficient transmission between cloud and mobile devices[C]∥INFOCOM,2013 Proceedings IEEE.IEEE,2013:195-199.
[7] LIN Y D,CHU T H,LAI Y C,et al.Time-and-Energy-Aware Computation Offloading in Handheld Devices to Coprocessors and Clouds [J].IEEE Systems Journal,2015,9(2):393-405.
[8] ZHANG W,WEN Y,GUAN K,et al.Energy-Optimal Mobile Cloud Computing under Stochastic Wireless Channel [J].IEEE Transactions on Wireless Communications,2013,12(9):4569-4581.
[9] MAHMOODI S E,SUBBALAKSHMI K P,SAGAR V.Cloudoffloading for multi-radio enabled mobile devices[C]∥IEEE International Conference on Communications.IEEE,2015:5473-5478.
[10] WU H,WANG Q,WOLTER K.Tradeoff between performance improvement and energy saving in mobile cloud offloading systems[C]∥IEEE Conference on Communications Workshops.IEEE,2013:728-732.
[11] CUERVO E,BALASUBRAMANIAN A,CHO D K,et al.MAUI:making last longer with code offload[C]∥International Conference on Mobile Systems,Applications,and Services.DBLP,2010:49-62.
[12] KOSTA S,AUCINAS A,HUI P,et al.ThinkAir:Dynamic resource allocation and parallel execution in the cloud for mobile code offloading[C]∥INFOCOM,2012 Proceedings IEEE.IEEE,2012:945-953.
[13] ZHANG W,WEN Y,WU D O.Collaborative Task Execution in Mobile Cloud Computing Under a Stochastic Wireless Channel [J].IEEE Transactions on Wireless Communications,2015,14(1):81-93.
[14] HUANG D,WANG P,NIYATO D.ADynamic Offloading Algorithm for Mobile Computing [J].IEEE Transactions on Wireless Communications,2012,11(6):1991-1995.
[15] CHUN B G,IHM S,MANIATIS P,et al.Clone Cloud:elastic execution between mobile device and cloud[C]∥Conference on Computer Systems.ACM,2011:301-314.
[16] MAHMOODI S E,SUBBALAKSHMI K P,SAGAR V.Cloud offloading for multi-radio enabled mobile devices[C]∥IEEE International Conference on Communications.IEEE,2015:5473-5478.
[17] MAHMOODI S E,UMA R N,SUBBALAKSHMI K P.Optimal Joint Scheduling and Cloud Offloading for Mobile Applications[J].IEEE Transactions on Cloud Computing,2016,PP(99):1.
[18] BALAKRISHNAN P,THAM C K.Energy-Efficient Mappingand Scheduling of Task Interaction Graphs for Code Offloading in Mobile Cloud Computing[C]∥IEEE/ACM International Conference on Utility and Cloud Computing.IEEE,2014:34-41.
[19] KOVACHEV D,YU T,KLAMMA R.Adaptive ComputationOffloading from Mobile Devices into the Cloud[C]∥International Symposium on Parallel and Distributed Processing with Applications.IEEE,2012:784-791.
[20] NIR M,MATRAWY A,ST-HILAIRE M.An energy optimizing scheduler for mobile cloud computing environments[C]∥IEEE INFOCOM 2014-IEEE Conference on Computer Communications Workshops.IEEE,2014:404-409.
[21] BARBAROSSA S,SARDELLITTI S,LORENZO P D.Computation offloading for mobile cloud computing based on wide cross-layer optimization[C]∥Future Network and Mobile Summit.IEEE,2013:1-10.
[22] RUBIN P..http://orinanobworld.blogspot.de/2010/10/binary-variables-and-quadratic-terms.html.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 编辑部. 新网站开通,欢迎大家订阅![J]. 计算机科学, 2018, 1(1): 1 .
[2] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[3] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[4] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[5] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[6] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[7] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[8] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[9] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[10] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .