Bowen Zhou
Rodrigo N. Calheiros
Skip Abstract Section
Abstract
Mobile cloud computing is emerging as a promising approach to enrich user experiences at the mobile device end. Computation offloading in a heterogeneous mobile cloud environment has recently drawn increasing attention in research. The computation offloading decision making and tasks scheduling among heterogeneous shared resources in mobile clouds are becoming challenging problems in terms of providing global optimal task response time and energy efficiency. In this article, we address these two problems together in a heterogeneous mobile cloud environment as an optimization problem. Different from conventional distributed computing system scheduling problems, our joint offloading and scheduling optimization problem considers unique contexts of mobile clouds such as wireless network connections and mobile device mobility, which makes the problem more complex. We propose a context-aware mixed integer programming model to provide off-line optimal solutions for making the offloading decisions and scheduling the offloaded tasks among the shared computing resources in heterogeneous mobile clouds. The objective is to minimize the global task completion time (i.e., makespan). To solve the problem in real time, we further propose a deterministic online algorithm—the Online Code Offloading and Scheduling (OCOS) algorithm—based on the rent/buy problem and prove the algorithm is 2-competitive. Performance evaluation results show that the OCOS algorithm can generate schedules that have around two times shorter makespan than conventional independent task scheduling algorithms. Also, it can save around 30% more on makespan of task execution schedules than conventional offloading strategies, and scales well as the number of users grows.
- Farhan Azmat Ali, Pieter Simoens, Tim Verbelen, Piet Demeester, and Bart Dhoedt. 2016. Mobile device power models for energy efficient dynamic offloading at runtime. Journal of Systems and Software 113 (2016), 173--187. Google Scholar
Digital Library
- Alison Doig Alisa Land. 1960. An automatic method of solving discrete programming problems. Econometrica 28, 3 (1960), 497--520.Google ScholarCross Ref
- Niranjan Balasubramanian, Aruna Balasubramanian, and Arun Venkataramani. 2009. Energy consumption in mobile phones: A measurement study and implications for network applications. In Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement Conference (IMC’09). ACM, New York, NY, 280--293. Google ScholarDigital Library
- Sergio Barbarossa, Stefania Sardellitti, and Paolo Di Lorenzo. 2013. Joint allocation of computation and communication resources in multiuser mobile cloud computing. In Proceedings of the IEEE 14th Workshop on Signal Processing Advances in Wireless Communications. IEEE, 26--30.Google ScholarCross Ref
- Marco Barbera, Sokol Kosta, Alessandro Mei, and Julinda Stefa. 2013. To offload or not to offload? The bandwidth and energy costs of mobile cloud computing. In Proceedings of IEEE INFOCOM Student Poster Session. 1285--1293. 0743-166XGoogle ScholarCross Ref
- Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis. Cambridge University Press, New York, NY. Google ScholarDigital Library
- Tracy D. Braun, Howard Jay Siegel, Noah Beck, Ladislau L. Blni, Muthucumaru Maheswaran, Albert I. Reuther, James P. Robertson, Mitchell D. Theys, Bin Yao, Debra Hensgen, and Richard F. Freund. 2001. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J. Parallel and Distrib. Comput. 61, 6 (2001), 810--837. Google ScholarDigital Library
- Chao Chen, Weidong Bao, Xiaomin Zhu, Haoran Ji, Wenhua Xiao, and Jianhong Wu. 2015. AGILE: A terminal energy efficient scheduling method in mobile cloud computing. Transactions on Emerging Telecommunications Technologies 26, 12 (2015), 1323--1336.Google ScholarCross Ref
- Shuang Chen, Yanzhi Wang, and M. Pedram. 2013. A semi-Markovian decision process based control method for offloading tasks from mobile devices to the cloud. In Proceedings of the IEEE Global Communications Conference.Google Scholar
- Xu Chen. 2015. Decentralized computation offloading game for mobile cloud computing. IEEE Transactions on Parallel and Distributed Systems 26, 4 (2015), 974--983.Google ScholarDigital Library
- Byung-Gon Chun, Sunghwan Ihm, Petros Maniatis, Mayur Naik, and Ashwin Patti. CloneCloud: Elastic execution between mobile device and cloud. In Proceedings of 6th Conference on Computer Systems. ACM, New York, NY. Google ScholarDigital Library
- Eduardo Cuervo, Aruna Balasubramanian, Dae-ki Cho, Alec Wolman, Stefan Saroiu, Ranveer Chandra, and Paramvir Bahl. 2010. MAUI: Making smartphones last longer with code offload. In Proceedings of the 8th International Conference on Mobile Systems, Applications, and Services. ACM, New York, NY, 14. Google ScholarDigital Library
- Shuiguang Deng, Longtao Huang, J. Taheri, and A. Y. Zomaya. 2015. Computation offloading for service workflow in mobile cloud computing. IEEE Transactions on Parallel and Distributed Systems 26, 12 (Dec 2015), 3317--3329. Google ScholarDigital Library
- Hoang T. Dinh, Chonho Lee, Dusit Niyato, and Ping Wang. 2013. A survey of mobile cloud computing: Architecture, applications, and approaches. Wireless Communications and Mobile Computing 13, 18 (2013), 1587--1611.Google ScholarCross Ref
- Xiaobo Fan, Carla S. Ellis, and Alvin R. Lebeck. 2005. The Synergy Between Power-Aware Memory Systems and Processor Voltage Scaling. Springer, Berlin, Germany, 164--179. Google ScholarDigital Library
- Huber Flores and Satish Srirama. 2014. Mobile cloud middleware. Journal of Systems and Software 92 (2014), 82--94.Google ScholarCross Ref
- Michael R. Garey and David S. Johnson. 1990. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Co., New York, NY. Google ScholarDigital Library
- Bo Hong and Viktor Prasanna. 2007. Adaptive allocation of independent tasks to maximize throughput. IEEE Transactions on Parallel and Distributed Systems 18, 10 (Oct. 2007), 1420--1435. Google ScholarDigital Library
- Dong Huang, Ping Wang, and Dusit Niyato. 2012. A dynamic offloading algorithm for mobile computing. IEEE Transactions on Wireless Communications 11, 6 (June 2012), 1991--1995.Google Scholar
- Oscar H. Ibarra and Chul E. Kim. 1977. Heuristic algorithms for scheduling independent tasks on nonidentical processors. Journal of the ACM (JACM) 24, 2 (1977), 280--289. Google ScholarDigital Library
- Anna R. Karlin, Mark S. Manasse, Lyle A. McGeoch, and Susan Owicki. 1990. Competitive randomized algorithms for non-uniform problems. In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 301--309. Google ScholarDigital Library
- Anna R. Karlin, Mark S. Manasse, Larry Rudolph, and Daniel D. Sleator. 1986. Competitive snoopy caching. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science. 244--254. Google ScholarDigital Library
- Sokol Kosta, Andrius Aucinas, Pan Hui, Richard Mortier, and Xinwen Zhang. 2012. ThinkAir: Dynamic resource allocation and parallel execution in the cloud for mobile code offloading. In Proceedings of the 31st IEEE International Conference on Computer Communications. 0743-166XGoogle ScholarCross Ref
- David Kotz, Tristan Henderson, Ilya Abyzov, and Jihwang Yeo. 2009. CRAWDAD dataset dartmouth/campus (v. 2009-09-09). Retrieved from http://crawdad.org/dartmouth/campus/20090909/syslog.Google Scholar
- Dejan Kovachev, Tian Yu, and Ralf Klamma. 2012. Adaptive computation offloading from mobile devices into the cloud. In Proceedings of the 2012 IEEE 10th International Symposium on Parallel and Distributed Processing with Applications. 784--791. Google ScholarDigital Library
- P. Venkata Krishna, Sudip Misra, D. Nagaraju, V. Saritha, and Mohammad S. Obaidat. 2016. Learning automata based decision making algorithm for task offloading in mobile cloud. In Proceedings of the 2016 International Conference on Computer, Information and Telecommunication Systems (CITS). 1--6.Google Scholar
- Karthik Kumar and Yung-Hsiang Lu. 2010. Cloud computing for mobile users: Can offloading computation save energy? Computer 43, 4 (April 2010), 51--56. Google ScholarDigital Library
- Kunfeng Lai, Hong Tang, Haiyang Wang, Shengyong Ding, and Dan Wang. 2013. Cloud offloading on customer-provided resources. In Proceedings of the 2013 IEEE Wireless Communications and Networking Conference (WCNC). 4695--4700.Google Scholar
- Jerald F. Lawless. 2011. Statistical Models and Methods for Lifetime Data. Vol. 362. John Wiley 8 Sons.Google Scholar
- JongHyuk Lee, SungJin Choi, Taeweon Suh, HeonChang Yu, and JoonMin Gil. 2010. Group-based scheduling algorithm for fault tolerance in mobile grid. In Security-Enriched Urban Computing and Smart Grid. Springer, 394--403.Google Scholar
- Kaiyang Liu, Jun Peng, Heng Li, Xiaoyong Zhang, and Weirong Liu. 2016. Multi-device task offloading with time-constraints for energy efficiency in mobile cloud computing. Future Generation Computer Systems 64 (2016), 1--14. Google ScholarDigital Library
- Xiaoqiang Ma, Yuan Zhao, Lei Zhang, Haiyang Wang, and Limei Peng. 2013. When mobile terminals meet the cloud: Computation offloading as the bridge. IEEE Network 27, 5 (September 2013), 28--33.Google ScholarCross Ref
- Yucen Nan, Wei Li, Wei Bao, Flavia C. Delicato, Paulo F. Pires, and Albert Y. Zomaya. 2016. Cost-effective processing for delay-sensitive applications in cloud of things systems. In Proceedings of the IEEE 15th International Symposium on Network Computing and Applications (NCA). 162--169.Google Scholar
- Nectar. 2015. URL: https://nectar.org.au/research-cloud/ (2015).Google Scholar
- Gurobi Optimization and others. 2015. Gurobi optimizer reference manual. URL: http://www. gurobi. com (2015).Google Scholar
- MReza Rahimi, Nalini Venkatasubramanian, and Athanasios Vasilakos. 2013. MuSIC: Mobility-aware optimal service allocation in mobile cloud computing. In Proceedings of 6th IEEE International Conference on Cloud Computing. 75--82. Google ScholarDigital Library
- Horst Rinne. 2008. The Weibull Distribution: A Handbook. CRC Press.Google Scholar
- Mahadev Satyanarayanan, Paramvir Bahl, Ramn Caceres, and Nigel Davies. 2009. The case for VM-based cloudlets in mobile computing. IEEE Pervasive Computing 8, 4 (Oct. 2009), 14--23. Google ScholarDigital Library
- Haluk Topcuoglu, Salim Hariri, and Min-you Wu. 2002. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems 13, 3 (2002), 260--274. Google ScholarDigital Library
- Shangguang Wang, Tao Lei, Lingyan Zhang, Ching-Hsien Hsu, and Fangchun Yang. 2016. Offloading mobile data traffic for QoS-aware service provision in vehicular cyber-physical systems. Future Generation Computer Systems 61 (2016), 118--127. Google ScholarDigital Library
- Yonggang Wen, Weiwen Zhang, and Haiyun Luo. 2012. Energy-optimal mobile application execution: Taming resource-poor mobile devices with cloud clones. In Proceedings of the 31st IEEE International Conference on Computer Communications (INFOCOM).Google ScholarCross Ref
- Weiwen Zhang, Yonggang Wen, Kyle Guan, Dan Kilper, Haiyun Luo, and Dapeng Oliver Wu. 2013. Energy-optimal mobile cloud computing under stochastic wireless channel. IEEE Transactions on Wireless Communications 12, 9 (2013), 4569--4581.Google ScholarCross Ref
- Bowen Zhou, Amir Vahid Dastjerdi, Rodirgo Calheiros, Satish Srirama, and Rajkumar Buyya. 2015. mCloud: A context-aware offloading framework for heterogeneous mobile cloud. IEEE Transactions on Services Computing 10, 5 (2015), 797--810.Google ScholarCross Ref
Index Terms
- An Online Algorithm for Task Offloading in Heterogeneous Mobile Clouds
Recommendations
Adaptive code offloading for mobile cloud applications: exploiting fuzzy sets and evidence-based learning
MCS '13: Proceeding of the fourth ACM workshop on Mobile cloud computing and servicesMobile cloud computing is arising as a prominent domain that is seeking to bring the massive advantages of the cloud to the resource constrained smartphones, by following a delegation or offloading criteria. In a delegation model, a mobile device ...
Adaptive code offloading for mobile cloud applications: exploiting fuzzy sets and evidence-based learning
MCS '13: Proceeding of the fourth ACM workshop on Mobile cloud computing and servicesMobile cloud computing is arising as a prominent domain that is seeking to bring the massive advantages of the cloud to the resource constrained smartphones, by following a delegation or offloading criteria. In a delegation model, a mobile device ...
An auction-based incentive mechanism for heterogeneous mobile clouds
Highlights- Heterogeneous mobile cloud forms a shared resource network for task offloading.
AbstractTraditional mobile cloud computing (MCC) adopts a onefold mobile device and public cloud paradigm. As the mobile device capabilities continue to develop, their opportunistic utilization in MCC has recently gained popularity. The new ...
Comments