Computer Science ›› 2018, Vol. 45 ›› Issue (4): 94-99, 116.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..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]. 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, 88 .
[3] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[4] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[5] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[6] 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 .
[7] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[8] 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 .
[9] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[10] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .