Edge Coalition Structure Generation Toward Horizontal Dimension

The emergence of the Internet of Things and the rapid development of new-generation mobile communication technologies such as 5G and 6G have redefined how people interact with the surrounding environment and further extended the physical and logical boundaries of the Internet.As an extension and supplement of cloud computing,edge computing sinks computing resources to the network’s edge close to the user side to meet the requirements of delay-sensitive and critical applications on delay,bandwidth,and real-time performance.However,Edge Infrastructure Providers(EIPs)tend to build privatized edge computing environments in practical applications,which can easily lead to repeated construction and unbalanced utilization of resources.For this reason,it is indispensable and urgent to establish a coalition(or coalition structure)service model among EIPs in the horizontal dimension to share resources compared with cloud-edge collaboration in the vertical dimension.However,there are several problems in the generation of the coalition structure in the horizontal dimension:(1)As a rational individual,EIP tends to cause the instability of the coalition structure to pursue the maximization of interests.Also,there is a lack of resource pricing mechanisms for different EIPs;(2)There are problems such as incomplete coalition structure and vast solution space in the multi-task concurrent environment;(3)The method based on the cooperative game is difficult to obtain the solution of the coalition structure for large-scale micro-suppliers due to problems such as computational complexity.In response to the above challenges,we conduct research from the following aspects:(1)To solve the problems of EIP resource pricing and the generation of stable edge coalitions,we introduce a net profit market price model to help Application Service Providers(ASPs)choose the optimal EIP to provide services.Also,we construct a coalition utility solution model based on mixed integer programming to maximize the utility of the coalition,based on which a distributed coalition structure formation algorithm(DCFA)based on the hedonic games is proposed.The experimental results show that the net profit market price model is more in line with the general market law,and the average utility brought by the coalition is more than twice that of the non-coalition.In addition,the average utility of the coalition structure generated by DCFA is 0.4528,close to 0.4594 generated by the dynamic programming(DP)algorithm.Also,the solution of DCFA has Nash stability,and its running time is half of the DP algorithm.(2)For the problems with vast potential solution space and incomplete coalition structure,we propose a discrete political optimizer algorithm(ADPO)based on the recent past position update strategy,which searches the area where the optimal solution is most likely to appear,and alleviates the contradiction between solution quality and convergence speed.In addition,to solve the problems of slow speed and unstable optimal solution of the heuristic method in solving the coalition structure,a model based on integer programming(IP)is constructed to handle low-latency,high-concurrency tasks.The experimental results show that the average net profit of ADPO is higher than that of M-ary Discrete Particle Swarm Optimization(MDPSO),Stable-matching,and integer programming methods.In the case of large-scale tasks and nodes,the ADPO solution time has an approximately linear relationship with the scale factor,and the maximum solution time is 13.37 seconds,much lower than the IP algorithm’s 889 seconds.(3)We construct an application service allocation model based on mixed integer programming to maximize the coalition utility.Based on it,we propose an adaptive dynamic algorithm based on an evolutionary game(AD-EGT)to solve the coalition structure generation problem for large-scale members.The experimental results show that the method proposed can adaptively and dynamically generate different edge coalition structures under the conditions of different periods and different numbers of applications.Also,the edge coalition structures generated by the AD-EGT are superior to K-EGT(K-means-EGT)and improved EGT-G(EGTGreedy)in utility,number of coalitions,resource occupation rate,and application request completion rate.