Task Scheduling Model And Algorithm In Complex Network Environment Of Mobile Cloud

With the aid of mobile cloud computing technology,complex applications executed on mobile devices can be divided into multiple parts and distributed over mobile devices and multiple server devices for execution,in order to address the issue of limited resources on mobile devices.Task scheduling is a key procedure in mobile cloud computing,aiming to reduce the execution time and energy consumption of mobile applications,and in turn to ensure the quality-of-service(Qo S)of mobile cloud computing.The research tasks of this thesis is oriented toward the task scheduling problem in the mobile cloud complex network environment.Based upon the characteristics of mobile cloud complex network environment,this thesis takes into account the constraints imposed by the complex cloud network environment,and accordingly constructs the mathematical model of task scheduling problem.We use directed acyclic graph workflow models to represent the precedence relations among tasks of mobile applications,and use undirected graph models to represent the mobile cloud complex network environment.Then,we establish a task scheduling optimization model,aiming to minimize the makespan of applications under the constraint of limited power.Specifically,we formulate the task scheduling model in the mobile cloud complex network environment as follows.Due to the constraints of devices' power as well as dependencies between tasks in the workflow and network connectivity,there are a significant number of infeasible solutions in the solution space of the scheduling problem,leading to the low efficiency of traditional heuristic algorithms.To address this limitation,we propose a heuristic scheduling algorithm based on improved greedy search,which can quickly find a higher quality feasible solution in the solution space.First,we classify the tasks nodes in the complex network,and design the corresponding search strategy for each individual node type.When processing a given task,the algorithm can always search for devices that have sufficient power and are reachable by the device executing its predecessor task.Therefore,the algorithm can efficiently obtain a scheduling solution while satisfying the constraints of power and connectivity.By analyzing the characteristics of the above-mentioned algorithms,we propose a double-layer heuristic scheduling optimization algorithm.Based on an inter-net optimization strategy and the intra-net optimization strategy,this algorithm optimizes the feasible solution by a heuristic search procedure.It uses the feasible solution obtained by the heuristic scheduling algorithm based on improved greedy search as the initial solution and performs the inter-net and intra-net double-layer optimization algorithm,for the purpose of improving the quality of the solution.We design extensive simulation experiment to verify the performance of the proposed heuristic scheduling algorithm based on improved greedy search and inter-net and intra-net double-layer heuristic scheduling optimization algorithm.Experimental results demonstrate that the two proposed scheduling algorithms can efficiently generate a feasible scheduling solution under the constraints of complex networks as well as to effectively reduce the makespan of applications.Therefore,the scheduling algorithms proposed in this thesis are capable of coping with task scheduling problem in complex network environments,and are beneficial for improving the Qo S of mobile devices in mobile cloud computing.