ENERGY-EFFICIENT AND DEADLINE-SATISFIED TASK SCHEDULING IN MOBILE CLOUD COMPUTING
Due to some inherent defects of mobile devices, such as limited battery energy, insufficient storage space, mobile applications are confronted with many challenges in mobility management, quality of service (QoS) insurance, energy management and security issues, which has stimulated the emergence of many computing paradigms, such as Mobile Cloud Computing (MCC), Fog Computing, etc. These computation paradigms allow to offload some tasks to the cloud for execution, which makes task scheduling crucial both at the mobile device and in the mobile cloud. In this paper, we models this problem as an energy consumption optimization problem, while taking into account task dependency, data transmission and some constraint conditions such as response time deadline and cost, and further solve it by genetic algorithms. A series of simulation experiments are conducted to evaluate the performance of the algorithm and the results are efficient and acceptable.
Keywords- Energy-efficient; Mobile cloud computing; Task
scheduling; Genetic algorihtms
Mobile cloud computing (MCC), which combines wireless network and cloud computing and aims at improving the performance of mobile applications hosted at mobile devices such as PDAs and smartphones, has developed very fast in the past few years. Due to some inherent defects of mobile devices, e.g. low CPU speed, limited battery energy, insufficient storage space, and inadequate sensing capacities, mobile applications are confronted with many challenges in mobility management, quality of service (QoS) insurance, energy management and security issues. As a solution to these shortcomings, MCC succeeds in offloading some computing modules to be executed on powerful nodes in the cloud, which brings a few benefits against the traditional mobile services. For example, with regards to some energy or resource-intensive mobile applications hosted in the mobile devices, offloading some parts of them to the remote cloud saves energy consumption greatly for the devices. Many mobile applications such as e-commerce, health-care, and computer games are developed under mobile cloud computing concept. However, task offloading is not always efficient, since it depends on several factors, such as transmission bandwidth of the wireless channel, the energy consumption on task offloading at mobile devices, energy consumption on task execution at the cloud and so on. For example, mobility as the inherent attribute of the mobile devices may force mobile users to change the access point (AP) frequently when users move from one place to another. This kind of dynamics sometimes makes the wireless connection unavailable, thus rendering the waiting time longer than the expected, which may degrade users’ Quality of Experience (QoE), even leading to users’ refusal to accept the response time especially for the urgent tasks. Besides, energy consumption is another important factor, which imposes great influence on offloading decision. For example, if the energy consumption caused by task offloading at mobile device and data transmission via wireless channel were larger than task execution locally without offloading, it would make no sense for tasks execution at cloud side remotely, from the viewpoint of saving power consumption for mobile devices.
In this section, we view some current works about task scheduling problem in MCC. Usually, in order to save power consumption, speed up the execution of an application, or save storage space, the mobile application is partitioned into several pieces, knows as tasks, and then these tasks are partially scheduled onto the nodes for execution in the mobile cloud. The optimization objective mainly falls into two categories, either minimizing the total execution time also called, makespan, or minimizing the energy consumption. Since the task scheduling problem is NP-hard, most works adopt heuristic approaches to solve this problem, which cannot guarantee to find the optimal solution, but it can find almost optimal solution. In, authors propose a task scheduling approach to guarantee a better accessibility to cloud network and speed up the processing time in MCC, taking into consideration some constraints such as the network bandwidth and cost for cloud usage. However, the details on how to obtain some metrics such as earliest start time or earliest finish time of tasks are not offered, and the algorithm complexity is unknown. Some works pay attention to the kinds of resources which the nodes in the MCC can provide, and chedule the tasks to the nodes in MCC combining it and the information on the amount and kinds of requested resources tasks need for execution, so as to find the most appropriate scheduling scheme. Authors in proposed a task scheduling algorithm based on the quality of service (QoS) metrics, such as load balancing, average execution, and makespan. First, according to the QoS, they calculate the priorities of the tasks, and then tasks with higher priority are scheduled first on the nodes. Authors in proposed an efficient task scheduling algorithm for workflow allocation based on the availability of network bandwidth. For other methods, authors adopted Min-Min and Min-Max algorithms
to assign tasks to each node in the cloud based on a nonlinear programming model. For the tasks obtained by partitioning the application, some are appropriate to be uploaded to the MCC while some are not. How to select suitable tasks to upload and guarantee that the task-precedence requirements and the application completion time constraint are satisfied has obtained a lot of ttention in the past few years. Authors presented an algorithm, which started from a minimal-delay scheduling solution and then performs energy reduction by applying the
dynamic voltage and frequency scaling technique.
Task scheduling in MCC is known as an NP-hard problem, which has attracted lots of attention in the past few years. We in this paper models this problem as an energy consumption optimization problem, while taking into account task dependency, data transmission and some
constraint conditions such as response time deadline and cost, and further solve it by genetic algorithms. For the future work, we will test the performance of algorithms with much larger task graphs and devise more efficient heuristic algorithms to solve this task scheduling problem.
 Conti, Marco, et al. : Research challenges towards the Future Internet. Computer Communications, 34(18), 2115–2134 (2011).
 Kumar, Karthik, and Y. H. Lu. :Cloud Computing for Mobile Users: Can Offloading Computation Save Energy? Computer , 43(4), 51-56 (2010).
 Satyanarayanan, Mahadev, et al.: The Case for VM-Based Cloudlets in Mobile Computing. IEEE Pervasive Computing, 8(4), 14- 23(2009).
 Xia, Qiufen, W. Liang, and W. Xu.:Throughput maximization for online request admissions in mobile cloudlets. In: the 38th IEEE Conference on Local Computer Networks (LCN), pp. 589-596. Sydney(2013).
 M.R. Garey and D. S. Johnson, : Computers and intractability:a guide to the theory of NP-Completeness. New York: W.H. Freeman, 1979
 Hung P P, Bui T A, Huh E N.: A New Approach for Task Scheduling Optimization in Mobile Cloud Computing. Lecture Notes in Electrical Engineering, 301, pp.211-220 (2014).
 Zhao Y, Chen L, Li Y, et al. RAS: A Task Scheduling Algorithm Based on Resource Attribute Selection in a Task Scheduling Framework. In: the International Conference on Internet and Distributed Computing Systems, pp. 106-119, Berlin (2013).
 Deng S, Huang L, Wu H, et al.: Constraints-Driven Service Composition in Mobile Cloud Computing. In: IEEE International Conference on Web Services, pp. 228-235, San Francisco (2016).
 Wang J, Tang J, Xue G, et al.: Towards energy-efficient task scheduling on smartphones in mobile crowd sensing systems. Computer Networks, 115(C), pp.100-109 (2017).
 Awad, A.I., El-Hefnawy, N.A., Abdelkader, H.M.: Enhanced Particle Swarm Optimization for Task Scheduling in Cloud Computing Environments. Procedia Comput. Sci. 65, pp. 920–929 (2015).
 Chen, H., Zhu, X., Guo, H., Zhu, J., Qin, X., Wu, J.: Towards energy efficient scheduling for real-time tasks under uncertain cloud computing environment. J. Syst. Softw., 99, pp. 20–35(2015).