Research On Task Allocation Algorithms In Edge Computing

The popularity of smart terminals and the expansion of network coverage promote the further development of emerging industries such as Consumer Internet of Things and Industrial Internet of Things,and a variety of applications have also emerged.However,because of limited computing capacity,these computing tasks that smart terminals and Internet of Things terminals cannot timely handle need to be executed by devices with higher computing capacity.The emergence of Edge Computing(EC)technology makes it possible to solve the above problems.Edge Computing migrates the computing platform to edge devices that generate source data,reducing data transmission latency.Edge devices also provide users data computing and data storage and are particularly suited for task allocation at user terminals.Task allocation can distribute complex computing tasks at user terminals to edge network for execution through wireless network,and complete computing relying on the resource of edge devices,so as to solve problems such as computing power and computing delay of users.Nevertheless,the huge diversity in IOT devices and applications makes it almost impossible for a single computing model to meet all application requirements.In order to solve the problems raised above,we mainly do the following.(1)The research status of EC is analyzed,and the main factors affecting task allocation strategy of EC are introduced in detail.In this paper,the algorithm of task allocation for EC is deeply studied and the existing task allocation methods are comprehensively sorted out through reading a lot of documents.(2)The edge computing scenario is established and the DAG task graph was used as the task model.With the goal of minimizing energy consumption,we establish the task allocation(mixed integer nonlinear programming)model for edge computing that meets the time delay constraint,reliability constraint and energy consumption constraint for a single edge device.In order to solve the optimization problem effectively,the fitness function of the genetic algorithm is combined with the original optimization problem by introducing penalty function,and the optimization problem with constraint conditions is transformed into an unconstrained problem.The optimal solution of the optimization problem is obtained by repeated selection,crossover and mutation until the specified number of iterations.(3)A hybrid algorithm combining the interior point method with the simplified branch and bound method is used to solve the proposed problem,which is NP-hard(non-deterministic polynomial).Firstly,relaxing the optimization problem into a relaxation optimization problem,which is proved to be a convex optimization problem,so we use the interior point method to solve it.In view of the limitations of interior point method in solving specific task allocation,a hybrid algorithm combining interior point method with branch and bound method is proposed.We branch and delimit decision variables continuously based on task allocation attributes,which greatly reduces the computational complexity.(4)By comparing the energy consumption and running time of five algorithms under different parameters,the effectiveness of the proposed method is verified,and the advantages of the algorithms proposed in this paper are highlighted.