Research On Optimal Coalition Structure Generation Strategy In Multi-Task Concurrent Edge Computing Environment

With the rapid development of Io T and 5G technologies,the massive amount of data generated by the explosive growth in the number of its devices sent to the cloud for processing can lead to a host of problems such as high latency and low bandwidth.Mobile edge computing,a new computing paradigm,deploys computing and storage resources at the edge of the network to process and analyze data at a physical location closer to the data source to meet the demand for real-time computing on end devices.In the edge computing environment,edge nodes often need to face the computing scenario of multiple tasks arriving at the same time,but due to limited node resources,it is difficult for a single edge node to meet the computing needs of all tasks at the same time,so the cooperation between nodes to solve the multi-task concurrency problem in this environment becomes a proven solution.Coalition structures as a classical model for solving cooperation problems have been widely used by research scholars.However,the optimal coalition structure generation problem in the edge computing environment is complex due to the number of edge nodes,computational power,optimization objectives,and constraints,and it is difficult for traditional methods to guarantee both optimization speed and optimal solution quality when solving this problem.Firstly,to address the problem that when the original M-ary particle swarm optimization algorithm solves the coalition structure generation problem,the algorithm easily falls into local optimal solutions and its running time cannot meet the demand of delay-sensitive tasks,We propose a discrete recent past-position updating strategy based M-ary discrete particle swarm optimization for optimal coalition structure search.First,the resource scheduling problem in the edge computing environment is transformed into an optimization problem model with key elements such as optimization objectives,decision variables,and constraints,and a new coalition structure is constructed to describe the scheduling scheme of resources.Secondly,an index-based coding approach is proposed to encode the coalition structure.By analyzing the multi-objective problem and specifying different weight coefficients,the multi-objective problem is transformed into a single total objective function.And an update method based on the discrete recent past-position updating strategy is proposed to improve the M-ary discrete particle swarm optimization algorithm.Finally,it is demonstrated through simulation experiments that the algorithm proposed in this chapter,compared with the M-ary discrete particle swarm optimization algorithm and the genetic algorithm,has substantially reduced algorithm running time and improved coalition structure effectiveness,equilibrium,and edge nodes’ efficiency in completing tasks.Secondly,to address the prominent problem that intelligent heuristic algorithms search for coalition structures that cannot guarantee their stability and are prone to fall into local optimum solutions when searching for multi-objective problems;and that individual tasks may not be able to meet the latency requirements when the concurrent task load is heavy.An optimal coalition structure generation method based on stable and satisfactory task-node matching is proposed.Firstly,the optimal coalition structure generation problem in the edge computing environment is modeled as a task-node matching model,and the resource scheduling problem in the edge computing environment is rationalized from the perspective of task-node matching.Secondly,a task-node matching scheme considering preference ranking is proposed,and the evaluation index of the model is established using the by affiliation function method to transform this task-node matching problem into a multi-objective optimization problem with the objectives of ensuring stability and satisfaction.Finally,a multi-objective evolutionary algorithm-based bilateral matching solution method is proposed.The proposed algorithm is compared with the multi-decimal discrete particle swarm optimization algorithm and the integer programming algorithm.The proposed algorithm improves the resource utilization of the edge nodes and optimizes the task completion time.