Research And Application Of Intelligent Optimization Algorithm In Mobile Cloud Computing Task Scheduling

With the rapid development of mobile Internet,the number and scale of mobile applications have been explosively increased.However,due to the limited resources of mobile devices,it is difficult to meet the resource requirements of complex applications.By taking advantage of powerful resources of mobile cloud computing(MCC),some tasks can be executed in heterogeneous environments with multiple mobile devices.This thesis aims at investigating the modeling of MCC task scheduling problem and application of solving the scheduling problem by developing intelligent optimization algorithms.According to the characteristics of mobile cloud environment,the task scheduling model is established by using a directed acyclic graph(DAG)to represent the functions and internal logics of the application.This model uses upward rank to determine the priority in task assignment,and uses an interval insertion technique to determine the task duration.The mathematical expression for the makespan of the mobile application is further established and used as the optimization goal of task scheduling.Based on the established MCC scheduling model,an iterated local search scheduling algorithm based on particle swarm optimization(PSO)is proposed.When the PSO search procedure is trapped into local optima,an perturbation operator based on adjacent pairwise interchange is developed to help the search procedure jump out of the local optima in the solution space.Furthermore,by analyzing the characteristics of this scheduling algorithm,an improved iterated local search scheduling algorithm is further proposed.The Simulated Annealing(SA)algorithm,which has lower cost and higher computational efficiency,is used to replace PSO for local search.In addition,a general interchange-based perturbation operator is used to replace the adjacent pairwise interchange-based operator,in order to improve the global optimization ability of scheduling algorithm.The ILS-PSO and ILS-SA algorithms proposed in this thesis can avoid the problem of being trapped into local optima,and therefore can achieve faster convergence rate and can improve the effectiveness and efficiency of scheduling solution.Based on above-mentioned research achievements,a visualized MCC simulator that supports customized DAG task graphs and mobile environments was developed.By selecting different scheduling policies,the scheduling results for user-specified DAGs can be visualized by the simulator.