Computer Science ›› 2018, Vol. 45 ›› Issue (4): 94-99.doi: 10.11896/j.issn.1002-137X.2018.04.014

Previous Articles     Next Articles

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

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..

No related articles found!
Full text



[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[3] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[5] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .