Service Placement Optimization In Fog Computing Based On Evolutionary Algorithm

With the rapid development of the Internet of Things,traditional cloud computing has been unable to meet the needs of applications for low latency,real-time interaction and mobility-aware.In order to make up for the shortcomings of cloud computing,Cisco proposed the concept of fog computing.Fog computing,as an emerging distributed computing paradigm,provides capabilities similar to traditional cloud computing at network edge closer to users.Migrating applications from the cloud to the edge of the network can effectively diminish the latency of users waiting for applications.However,placing services on fog devices that are resource-constrained,heterogeneous and geographically distributed is a challenging issue,and the diversity of user expectations and Io T devices characteristics also complexify the placement problem.Existing research has proved that the service placement problem in fog computing is an NP-hard problem and it has become a hot trend to use heuristic algorithms to solve the fog service placement problem.This paper focuses on the service placement problem in fog computing,and studies the mod-eling and optimization of the fog service placement problem.The main contents of this paper are summarized as follows:(1)This paper builds a model of the service placement problem in the fog computing en-vironment.The service placement problem in fog computing is abstracted into a constrained multi-objective optimization problem,and the system model of fog computing is established,and an Io T application model based on microservice is proposed.Then,based on these two models,a mathematical model of network latency,resource utilization and service cost is constructed,and the constraint of fog service placement problem is that the resources con-sumed by the service allocated to the fog device does not exceed the available resources of the device.(2)This paper introduces three multi-objective evolutionary algorithms to optimize the fog service placement problem.Firstly,the multi-objective fog service placement problem is transformed into a single-objective optimization problem,and the same weight coefficients is assigned to each optimization goal.Then,the fog service placement optimization algo-rithm based on the Weighted Sum Genetic Algorithm(WSGA)is proposed? secondly,the fast Non-dominated Sorting Genetic Algorithm(NSGA-II)with elite strategy is used to solve the multi-objective fog service placement optimization problem and the NSGA-II-based fog service placement optimization algorithm is proposed? thirdly,this paper uses the Multi-objective Evolutionary Algorithm Based on Decomposition(MOEA/D)to study the multi-objective fog service placement problem.This multi-objective problem is decomposed into a series of scalar subproblems by Chebychev Approach and optimized them at the same time,and the MOEA/D-based fog service placement optimization algorithm is proposed.(3)The performance of three optimization schemes proposed in this paper is evaluated and compared through simulation experiments.The simulation trials demonstrate that the WSGA-based fog service placement optimization algorithm has the least execution time,and the so-lution output by this algorithm has the least number of services deployed in the fog layer? the NSGA-II-based fog service placement optimization algorithm achieved the highest optimiza-tions of the objectives;the MOEA/D-based fog service placement optimization algorithm has the fastest convergence speed and the Pareto optimal solution set obtained by this algo-rithm has the best performance.