CN111857976A - A computational migration method for multi-objective optimization based on decomposition - Google Patents

Abstract

The present invention provides a computing migration method based on decomposition and multi-objective optimization in the computer field, comprising the following steps: step S10, creating a target model based on the satisfaction of the end user and the profit of the edge cloud service provider; step S20, using The genetic algorithm and the multi-objective optimization algorithm are used to iteratively evolve the target model; in step S30, the multi-criteria decision-making, the weighting method, and the iteratively evolved target model are used to calculate and migrate. The advantage of the present invention is that the speed of computing migration is greatly improved while comprehensively considering the satisfaction of end users and the benefits of edge cloud service providers.

Description

A computational migration method for multi-objective optimization based on decomposition

technical field

The invention relates to the field of computers, in particular to a calculation migration method based on decomposition and multi-objective optimization.

Background technique

In recent years, IoT technology has been vigorously developed, but the computing power of IoT devices is limited, so a large number of computing-intensive tasks cannot be calculated on local IoT devices. In order to prolong the battery life of IoT devices and meet the computing needs, Mobile Cloud Computing (MCC, Mobile Cloud Computing) came into being, by migrating part of the computing-intensive task request computing to the cloud for processing. Although MCC can effectively reduce the computing overhead and power consumption of IoT devices, at the same time, MCC also faces some new challenges. On the one hand, with the proliferation of IoT devices, more and more task requests significantly increase the computing burden on the cloud; The delay and transmission delay increase, which affects the user experience, and even causes some tasks with strict time constraints to fail.

Mobile Edge Computing (MEC, Mobile Edge Computing) can effectively alleviate the above challenges. MEC uses the computing and storage functions of network devices close to end users and edge side to assist users, and migrates task requests to edge servers closer to end users for execution. , which can provide end users with computing services, storage services and communication services with higher efficiency and lower delay, thereby improving the quality of service (QoS) of end users.

A typical MEC environment includes public cloud service providers, edge cloud service providers, and end users, as shown in Figure 2. Public cloud service providers are used to provide hardware and software resources, complete the construction and maintenance of server clusters, generate a unified resource pool through resource pooling, and provide end users with resources such as computing, storage, and bandwidth. Edge cloud service providers lease server resources from public cloud service providers, and build a service environment according to their own service types to provide end users with services such as image processing, scientific computing, and video encoding and decoding. The end user sends a service request to the edge cloud service provider that can provide the required service, and pays the fee according to the service level agreement (Service-Level Agreement, SLA) and the final return result of the edge server.

In the paper "Energy and Performance Management of Green DataCenters: A Profit Maximization Approach. 2013", Ghamkhar et al. consider factors such as the service level agreements (SLAs) that currently exist between data centers and their customers, and the randomness of data center workloads. , a new optimization-based strategy for data center profit maximization is proposed. The cloud computing revenue optimization model proposed by Li Meng in the document "Research on Cloud Computing Resource-Oriented Revenue Optimization Model and Task Allocation Algorithm. 2015" takes into account the service provider's revenue while taking into account the SLA agreement, and uses queuing theory to estimate the service request. The response time, and the processing time of the request are calculated, and the PAO-ACO algorithm for the cloud resource revenue model is proposed to solve the model, which proves that the algorithm can dynamically find the optimal solution, and when the population size is large, parallel solution can save computation time and improve execution efficiency. Shao Gaoyuan studied the optimal pricing of cloud services and multi-server optimal pricing in the cloud computing environment with the goal of profit maximization in the document "Research on Optimal Service Pricing and Multi-Server System Configuration for Profit Maximization in Cloud Computing Environment. 2017" Regarding the configuration problem, his pricing model can propose a Monetary Reward reward model according to the change of service price under the premise of conforming to the law of user demand in the market environment, and design a low service quality fee compensation algorithm based on service request response time. Zhang Fenghui and others established a Markov game model in the document "Markov Game-Based Cloud Agent and Micro-Cloud Revenue Optimization. 2018" to analyze cloud servers and micro-clouds, and obtained the Nash equilibrium strategy through a reverse iterative algorithm. Finally, It is proved that the use of Markov game can significantly improve the system revenue.

The above literatures are all aimed at optimizing the revenue in the cloud computing environment. However, with the development of MEC, some scholars have begun to study the maximization of the revenue of MEC service providers. For example, Huang Dongyan et al. in the document "Revenue optimization strategy for MEC servers with limited computing resources. 2020", aiming at the revenue optimization problem of MEC servers with limited computing resources, with the optimization goal of maximizing the revenue of MEC servers, a branch-based method is proposed. The algorithm of the delimitation method is used to obtain the optimal access strategy and task execution order. This algorithm can effectively improve the average revenue of the MEC server in the heavy load network.

The methods described in the above-mentioned documents all have the problems of slow computational migration speed and neglect of the satisfaction of end users. Therefore, how to provide a computing migration method based on multi-objective optimization (MOEA/D), which comprehensively considers the satisfaction of end users and the benefits of edge cloud service providers, while improving the speed of computing migration, has become an urgent problem to be solved. question.

SUMMARY OF THE INVENTION

The technical problem to be solved by the present invention is to provide a computing migration method based on decomposition and multi-objective optimization, which can improve the speed of computing migration while comprehensively considering the satisfaction of end users and the benefits of edge cloud service providers.

The present invention is achieved in this way: a computational migration method based on decomposition of multi-objective optimization, comprising the following steps:

Step S10, creating a target model based on the satisfaction of the end user and the income of the edge cloud service provider;

Step S20, using genetic algorithm and multi-objective optimization algorithm to iteratively evolve the target model;

Step S30, using multi-criteria decision-making, weighting method and the target model after iterative evolution to perform calculation migration.

Further, the step S10 is specifically:

Create an end-user satisfaction model:

表示终端用户的满意度；S_max表示最大的用户满意度；T_u表示用户期望完成的时间；T_DDL表示服务请求的截至时间；t_i,j(τ_p,q)表示第i个边缘服务器中第j个虚拟机的平均响应时间；τ_p,q表示终端用户p的第q个服务请求在边缘服务器的完成时间；M表示虚拟机的总数量；u_i,j表示第i个边缘服务器中第j个虚拟机的任务处理速率；λ_i,j表示第i个边缘服务器中第j个虚拟机的任务到达速率；U表示终端用户的总数量；V_p表示服务请求的总数量；w_p,q表示τ_p,q的指令数；B是一个布尔函数，B＝0表示终端用户p的第q个服务请求没有迁移到第i个边缘服务器的第j个虚拟机中，B＝1表示终端用户p的第q个服务请求迁移到第i个边缘服务器的第j个虚拟机中；i、j、M、p、q、U、V_p均为正整数；in,

Represents the end user's satisfaction; S _max represents the maximum user satisfaction; _Tu represents the user's expected completion time; T _DDL represents the service request deadline; t _i,j (τ _p,q ) represents the ith edge server The average response time of the jth virtual machine in τ _p,q represents the completion time of the qth service request of end user p at the edge server; M represents the total number of virtual machines; u _i,j represents the ith edge server The task processing rate of the jth virtual machine in the ith edge server; λ _i,j represents the task arrival rate of the jth virtual machine in the ith edge server; U represents the total number of end users; V _p represents the total number of service requests; w _p,q represents the number of instructions of τ _p,q ; B is a Boolean function, B=0 means the qth service request of end user p is not migrated to the jth virtual machine of the ith edge server, B=1 Indicates that the qth service request of end user p is migrated to the jth virtual machine of the ith edge server; i, j, M, p, q, U, and _Vp are all positive integers;

The formula for calculating the total revenue of edge cloud service providers is as follows:

where R represents the total revenue of the edge cloud service provider; R(τ _p,q ,t _i,j (τ _p,q )) represents the charge of the edge server for processing the qth service request of the end user p; p _m represents each the price of the service request;

The formula for calculating the cost of edge cloud service providers is as follows:

where C represents the cost of the edge cloud service provider; _cm represents the cost of each service request;

The two goals of end-user satisfaction and the benefits of edge cloud service providers are defined as:

stop _p, q∈{0,1,...,N+1};

where o _p,q represents the migration strategy assigned to the qth service request of end user p.

Further, the step S20 specifically includes:

Step S21, based on the target model, randomly generate a population G ₀ with a scale of Q _p in the feasible region Ω:

表示种群G₀中第Q_p个的个体；Q_p为正整数；in

Represents the Q _p -th individual in the population G ₀ ; Q _p is a positive integer;

Step S22, creating Q _p weight vectors σ ^j :

where j is a positive integer, and j=1, 2, ..., Q _p ; k is a positive integer;

Step S23, calculating the Euclidean distances d _i,j between the weight vectors σ ^j in pairs, and generating a distance matrix d based on the Euclidean distances d _i,j ;

Based on the distance matrix d, select Q _nei nearest individuals X ⁱ (i=1, 2,...,Q _p ) to form a neighbor set:

则权重向量σ^j最近的Q_nei个权重向量为:

For every nearest individual, let

Then the nearest Q _nei weight vectors of the weight vector σ ^j are:

Step S24, calculate the objective function value of each individual X ⁱ (i=1, 2,...,Q _p ):

f ₁ (X ⁱ ), f ₂ (X ⁱ ),...,f _k (X ⁱ ),;

Let the ideal point of the objective function value be:

i为正整数；in

i is a positive integer;

Step S25, set the external population O ^* =Φ, the population iteration number is t, and t is a positive integer, and perform iterative evolution for each individual:

将所述新个体

添加到种群G_t中，即

Randomly select two individuals from the neighbor set C _i to generate new individuals

the new individual

added to the population G _t , i.e.

则

Update ideal point y ^* : if

but

Update the neighbor set C _i of each individual:

Let σ ^i,l denote the weight vector of each element in the neighbor set C _i of the individual X ⁱ , l=1,2,...,Q _p ,

则X^i,l＝Xⁱ；like

Then X ^i,l =X ⁱ ;

表示切比雪夫值；F(Xⁱ)表示Xⁱ个体对应的适应度函数值；where X ^i,l represents each element in the neighbor set C _i ;

represents the Chebyshev value; F(X ⁱ ) represents the fitness function value corresponding to the individual X ⁱ ;

Update the outer population O ^* :

支配的解，若存在，则剔除外部种群O^*中被新个体

支配的解；若不存在，则将新个体

加入外部种群O^*中；Determine whether there is a new individual in the outer population O ^*

The dominant solution, if it exists, remove the new individual from the outer population O ^*

the dominant solution; if it does not exist, the new individual

join the outer population O ^* ;

Step S26, select, cross and mutate the population G ₀ to generate a new population, and determine whether the population iteration number t is less than the preset maximum iteration number, if so, go to step S24; if not, go to step S30.

Further, the step S30 is specifically:

Let the practical value of end-user satisfaction be:

The practical value of the benefits of edge cloud service providers is:

The practical value of each individual in population G ₀ is:

The individuals with the greatest practical value are:

where S ^min represents the minimum value of the end user satisfaction; S ^max represents the maximum value of the end user satisfaction; S(X ⁱ ) ^represents the end user satisfaction of the individual Xi; R ^min represents the minimum value of the edge cloud service provider's revenue ; R ^max represents the maximum value of the edge cloud service provider's revenue; R(X ⁱ ) ^represents the edge cloud service provider revenue of the individual Xi; w ₁ represents the weight of the end user satisfaction, w ₂ represents the edge cloud service provider The weight of income, w ₁ +w ₂ =1.

The advantages of the present invention are:

Create a target model based on the satisfaction of end users and the income of edge cloud service providers, and then use genetic algorithm and multi-objective optimization algorithm to iteratively evolve the target model, and finally use multi-criteria decision-making, weighting method and the target model after iterative evolution. Computational migration, that is, to find the individual with the greatest practical value, so that both the end-user satisfaction and the edge cloud service provider's benefit are maximized, that is, to comprehensively consider the end-user's satisfaction and the benefit of the edge cloud service provider, and due to the use of multi-objective The optimization algorithm has lower time complexity, lower time overhead cost, rapid convergence, and high reliability, which greatly improves the speed of computing migration.

Description of drawings

The present invention will be further described below with reference to the accompanying drawings and embodiments.

FIG. 1 is a flow chart of a computational migration method for multi-objective optimization based on decomposition of the present invention.

FIG. 2 is a schematic diagram of the mobile edge computing network architecture of the present invention.

FIG. 3 is a schematic diagram of the coding of the migration strategy of the present invention.

Figure 4 is a schematic diagram of the minimization problem of the present invention.

FIG. 5 is a schematic diagram of the strategy coding crossover according to the present invention.

Detailed ways

Please refer to FIG. 1 to FIG. 5 , one of the embodiments of a decomposition-based multi-objective optimization computational migration method of the present invention includes the following steps:

Step S10, creating a target model based on the satisfaction of the end user and the income of the edge cloud service provider;

Step S20, using genetic algorithm and multi-objective optimization algorithm to iteratively evolve the target model;

Step S30, using multi-criteria decision-making, weighting method and the target model after iterative evolution to perform calculation migration.

Before step S10, an MEC network architecture needs to be built, and the processor performance, the number of virtual machines, and the working power of the mobile devices, edge servers, and cloud servers in the MEC network architecture are set.

The present invention adopts an integer coding method, so that each gene in each chromosome is an integer, takes the satisfaction of the end user and the profit of the edge cloud service provider as the optimization goal, and regards the migration strategy of each group as a For chromosomes composed of multiple genes, when there are N edge servers on the platform, the migration strategy is encoded as 0,1,...,N+1. The migration strategy code is shown in Figure 3. The number 0 means that the task is not migrated, and the calculation is performed on the local device; the number 1 to N means that the task will be migrated to the specified edge server for execution; the number N+1 means that the task will be migrated to the cloud. execute on the server. Before the genetic algorithm starts, parameters such as population size Q _p , weight vector _σ ^j , size of neighbor set Q _nei , maximum number of iterations G _max , and crossover probability pc need to be determined. The ^ith chromosome in a population can be represented as Xi = {o _p,q |p=1,2,...,U;q=1,2,...,V}. Some individuals are selected from the population for subsequent crossover and mutation operations, and based on the individual fitness evaluation, a new population with better fitness is formed.

The step S10 is specifically:

Create an end-user satisfaction model:

表示终端用户的满意度；S_max表示最大的用户满意度；T_u表示用户期望完成的时间；T_DDL表示服务请求的截至时间；t_i,j(τ_p,q)表示第i个边缘服务器中第j个虚拟机的平均响应时间；τ_p,q表示终端用户p的第q个服务请求在边缘服务器的完成时间；M表示虚拟机的总数量；u_i,j表示第i个边缘服务器中第j个虚拟机的任务处理速率；λ_i,j表示第i个边缘服务器中第j个虚拟机的任务到达速率，即j层子请求上每秒钟达到多少MIPS指令；U表示终端用户的总数量；V_p表示服务请求的总数量；w_p,q表示τ_p,q的指令数；B是一个布尔函数，B＝0表示终端用户p的第q个服务请求没有迁移到第i个边缘服务器的第j个虚拟机中，B＝1表示终端用户p的第q个服务请求迁移到第i个边缘服务器的第j个虚拟机中；i、j、M、p、q、U、V_p均为正整数；in,

Represents the end user's satisfaction; S _max represents the maximum user satisfaction; _Tu represents the user's expected completion time; T _DDL represents the service request deadline; t _i,j (τ _p,q ) represents the ith edge server The average response time of the jth virtual machine in τ _p,q represents the completion time of the qth service request of end user p at the edge server; M represents the total number of virtual machines; u _i,j represents the ith edge server the task processing rate of the _jth virtual machine in V _p represents the total number of service requests; w _p,q represents the number of instructions of τ _p,q ; B is a Boolean function, B=0 indicates that the qth service request of end user p is not migrated to the ith In the jth virtual machine of the edge server, B=1 indicates that the qth service request of end user p is migrated to the jth virtual machine of the ith edge server; i, j, M, p, q, U , V _p are positive integers;

The formula for calculating the total revenue of edge cloud service providers is as follows:

where R represents the total revenue of the edge cloud service provider; R(τ _p,q ,t _i,j (τ _p,q )) represents the charge of the edge server for processing the qth service request of the end user p; p _m represents each the price of the service request;

The formula for calculating the cost of edge cloud service providers is as follows:

where C represents the cost of the edge cloud service provider; _cm represents the cost of each service request; the benefit of the edge cloud service provider is equal to the total input minus the cost;

The two goals of end-user satisfaction and the benefits of edge cloud service providers are defined as:

stop _p, q∈{0,1,...,N+1};

where o _p,q represents the migration strategy assigned to the qth service request of end user p.

The step S20 specifically includes:

Step S21, based on the target model, randomly generate a population G ₀ with a scale of Q _p in the feasible region Ω:

表示种群G₀中第Q_p个的个体；Q_p为正整数；in

Represents the Q _p -th individual in the population G ₀ ; Q _p is a positive integer;

Step S22, creating Q _p weight vectors σ ^j :

where j is a positive integer, and j=1, 2, ..., Q _p ; k is a positive integer;

Step S23, calculating the Euclidean distances d _i,j between the weight vectors σ ^j in pairs, and generating a distance matrix d based on the Euclidean distances d _i,j ;

Based on the distance matrix d, select Q _nei nearest individuals X ⁱ (i=1, 2,...,Q _p ) to form a neighbor set:

Q_nei代表C_i的规模大小；

Q _nei represents the scale of C _i ;

则权重向量σ^j最近的Q_nei个权重向量为:

For every nearest individual, let

Then the nearest Q _nei weight vectors of the weight vector σ ^j are:

Step S24, calculate the objective function value of each individual X ⁱ (i=1, 2,...,Q _p ):

f ₁ (X ⁱ ), f ₂ (X ⁱ ),...,f _k (X ⁱ ),;

Let the ideal point of the objective function value be:

i为正整数；过程如图4所示；in

i is a positive integer; the process is shown in Figure 4;

Step S25, set the external population O ^* =Φ, the population iteration number is t, and t is a positive integer, and perform iterative evolution for each individual:

将所述新个体

添加到种群G_t中，即

Randomly select two individuals from the neighbor set C _i to generate new individuals

the new individual

added to the population G _t , i.e.

For example, randomly select two serial numbers a and b from B(i), use the genetic operators X ^a and X ^b to generate a new individual X ^c , and then use the repair and improvement inspiration based on the test problem to generate a new individual X ^c .

则

Update ideal point y ^* : if

but

Update the neighbor set C _i of each individual:

Let σ ^i,l denote the weight vector of each element in the neighbor set C _i of the individual X ⁱ , l=1,2,...,Q _p ,

则X^i,l＝Xⁱ；like

Then X ^i,l =X ⁱ ;

表示切比雪夫值；F(Xⁱ)表示Xⁱ个体对应的适应度函数值；where X ^i,l represents each element in the neighbor set C _i ;

represents the Chebyshev value; F(X ⁱ ) represents the fitness function value corresponding to the individual X ⁱ ;

Update the outer population O ^* :

支配的解，若存在，则剔除外部种群O^*中被新个体

支配的解；若不存在，则将新个体

加入外部种群O^*中；Determine whether there is a new individual in the outer population O ^*

The dominant solution, if it exists, remove the new individual from the outer population O ^*

the dominant solution; if it does not exist, the new individual

join the outer population O ^* ;

Step S26, select, cross and mutate the population G ₀ to generate a new population, as shown in Figure 3 and Figure 5, determine whether the population iteration number t is less than the preset maximum iteration number, if so, go to step S24; if not, go to step S24; Then go to step S30.

The step S30 is specifically:

Let the practical value of end-user satisfaction be:

The practical value of the benefits of edge cloud service providers is:

The practical value of each individual in population G ₀ is:

The individuals with the greatest practical value are:

where S ^min represents the minimum value of the end user satisfaction; S ^max represents the maximum value of the end user satisfaction; S(X ⁱ ) ^represents the end user satisfaction of the individual Xi; R ^min represents the minimum value of the edge cloud service provider's revenue ; R ^max represents the maximum value of the edge cloud service provider's revenue; R(X ⁱ ) ^represents the edge cloud service provider revenue of the individual Xi; w ₁ represents the weight of the end user satisfaction, w ₂ represents the edge cloud service provider The weight of income, w ₁ +w ₂ =1.

The second embodiment of the decomposition-based multi-objective optimization computing migration method of the present invention assumes that there are 4 edge servers and 1 cloud server in the MEC network architecture, and considers the situation that some task requests of end users are executed locally.

Suppose a set of mobile users U={u _1,1 ,u _1,2 ,…,u _1,q ,u _2,1 ,u _2,2 ,…,u _2,q ,…,up _,1 ,u _p,2 ,…,up _p,q }, where up _p,q represents the qth application of the pth user; o _p,q represents the migration strategy assigned to the qth request of the pth user, o _p,q =1,2,...,N indicates that the application is migrated to the edge server for execution, o _p,q =N+1 indicates that the application is migrated to the cloud for execution; τ _p,q indicates the qth service request of user p; t (τ _p,q ) represents the completion time of the qth service request of user p; R(τ _p,q ,t(τ _p,q )) represents the charge of the qth service request of user p; N represents is the set of edge servers in the system; M is the number of edge server virtual machines in the system; w _p,q is the number of instructions of τ _p,q ; p _m is the price of each instruction; c _m Represented as the cost of each instruction; Tu represents the completion time expected by the user; T _DDL represents the deadline for service requests; S _τp,q represents the user satisfaction of τ _p,q ; _u represents the task processing rate; λ is the task arrival rate; S _max is the maximum user satisfaction.

Suppose that the case where the task request is not migrated is marked as up _{, q} = 0, and the case of migration to the 1st to 4th edge servers is marked as up _{, q} = 1, up _{, q} = 2, up _{, q} = 3 and up _,q =4, the case of migration to the cloud is marked as up _,q =5. As shown in the migration strategy code in Figure 3, each migration situation is marked as a gene in a chromosome, and a large number of genes are converted into a chromosome, and the operations of crossover and compilation are performed in the subsequent evolution process.

According to queuing theory, calculating the processing time model, the average response time of τ _p,q in the jth virtual machine in the ith server is:

Among them, u _i,j is the task processing rate of the j-th virtual machine in the i-th edge server; λ _i,j is the task arrival rate of the j-th virtual machine in the i-th edge server, i.e. How many MIPS instructions are reached per second on the request, the calculation formula is:

Among them, B is a Boolean function, B=0 means that the qth service subrequest of user p is not migrated to the jth virtual machine of the ith server; B=1 means that the qth service subrequest of user p is migrated to the jth virtual machine of the ith server.

Therefore, the completion time of the qth service request of user p in the ith server is:

描述用户p的第q个服务请求，可求得在不同的服务请求完成时间内所对应的满意度。其计算公式如下：From the processing time calculation model of the above formula, use

Describing the qth service request of user p, the satisfaction corresponding to different service request completion times can be obtained. Its calculation formula is as follows:

Let R(τ _p,q ,t(τ _p,q )) denote the charge of the edge server for processing the qth service request of user p, then the total revenue R of the edge server provider is:

And the calculation formula of R(τ _p,q ,t(τ _p,q )) is:

The cost of the edge server is denoted by C, and the revenue of the edge cloud service provider is obtained by subtracting the cost from the revenue of the edge server, which is simplified and calculated as:

All in all, the overall goal of computing migration studied in the present invention is to maximize user satisfaction and maximize the benefits of edge cloud service providers while meeting the task requirements of mobile users, where the multi-objective optimization problem can be defined as:

stop _p, q∈{0,1,2,3,4,5};

Each chromosome contains the migration situation of each user's task request, and the migration coding strategy is substituted into the relationship between the user satisfaction and the edge cloud service provider's income in the above formula to obtain the fitness value, and the evolution operation is performed.

When the evolutionary algebra reaches the maximum, there are individuals with population size Q _p in the population P _tmax , each individual represents the calculation migration strategy of the optimal solution, and the gene value of the chromosome is brought into the model established above, and the goal of the optimal solution will be obtained. value, but some individuals may be different in the optimal solution. In this case, multi-criteria decision-making and simple weighting method should be used to select the optimal solution. X ⁱ represents the ith individual in the optimal solution population, and its practical value is defined as:

LB ^max and LB ^min are expressed as the maximum and minimum target values of user satisfaction in the optimal solution population.

^Tmax and ^Tmin are denoted as the maximum and minimum benefits of edge servers in the optimal solution population.

The satisfaction of the practical value of each individual in the optimal solution population is calculated by the weight w, where w ₁ +w ₂ =1:

After finding the practical value of each individual, it is necessary to select the individual with the greatest practical value from the population, and the individual with the greatest practical value is the optimal solution individual:

To sum up, the advantages of the present invention are:

Create a target model based on the satisfaction of end users and the income of edge cloud service providers, and then use genetic algorithm and multi-objective optimization algorithm to iteratively evolve the target model, and finally use multi-criteria decision-making, weighting method and the target model after iterative evolution. Computational migration, that is, to find the individual with the greatest practical value, so that both the end-user satisfaction and the edge cloud service provider's benefit are maximized, that is, to comprehensively consider the end-user's satisfaction and the benefit of the edge cloud service provider, and due to the use of multi-objective The optimization algorithm has lower time complexity, lower time overhead cost, rapid convergence, and high reliability, which greatly improves the speed of computing migration.

Although the specific embodiments of the present invention are described above, those skilled in the art should understand that the specific embodiments we describe are only illustrative, rather than used to limit the scope of the present invention. Equivalent modifications and changes made by a skilled person in accordance with the spirit of the present invention should be included within the scope of protection of the claims of the present invention.

Claims (4)

1. a computational migration method based on the multi-objective optimization of decomposition, is characterized in that: comprise the steps: Step S10, creating a target model based on the satisfaction of the end user and the income of the edge cloud service provider; Step S20, using genetic algorithm and multi-objective optimization algorithm to iteratively evolve the target model; Step S30, using multi-criteria decision-making, weighting method and the target model after iterative evolution to perform calculation migration. 2. a kind of calculation migration method based on the multi-objective optimization of decomposition as claimed in claim 1, is characterized in that: described step S10 is specifically: Create an end-user satisfaction model:

in,

Represents the end user's satisfaction; S _max represents the maximum user satisfaction; _Tu represents the user's expected completion time; T _DDL represents the service request deadline; t _i,j (τ _p,q ) represents the ith edge server The average response time of the jth virtual machine in τ _p,q represents the completion time of the qth service request of end user p at the edge server; M represents the total number of virtual machines; u _i,j represents the ith edge server The task processing rate of the jth virtual machine in the ith edge server; λ _i,j represents the task arrival rate of the jth virtual machine in the ith edge server; U represents the total number of end users; V _p represents the total number of service requests; w _p,q represents the number of instructions of τ _p,q ; B is a Boolean function, B=0 means the qth service request of end user p is not migrated to the jth virtual machine of the ith edge server, B=1 Indicates that the qth service request of end user p is migrated to the jth virtual machine of the ith edge server; i, j, M, p, q, U, and _Vp are all positive integers; The formula for calculating the total revenue of edge cloud service providers is as follows:

where R represents the total revenue of the edge cloud service provider; R(τ _p,q ,t _i,j (τ _p,q )) represents the charge of the edge server for processing the qth service request of the end user p; p _m represents each the price of the service request; The formula for calculating the cost of edge cloud service providers is as follows:

where C represents the cost of the edge cloud service provider; _cm represents the cost of each service request; The two goals of end-user satisfaction and the benefits of edge cloud service providers are defined as:

stop _p, q∈{0,1,...,N+1}; where o _p,q represents the migration strategy assigned to the qth service request of end user p. 3. The computational migration method of a decomposition-based multi-objective optimization as claimed in claim 1, wherein the step S20 specifically comprises: Step S21, based on the target model, randomly generate a population G ₀ with a scale of Q _p in the feasible region Ω:

in

Represents the Q _p -th individual in the population G ₀ ; Q _p is a positive integer; Step S22, creating Q _p weight vectors σ ^j :

where j is a positive integer, and j=1, 2, ..., Q _p ; k is a positive integer; Step S23, calculating the Euclidean distances d _i,j between the weight vectors σ ^j in pairs, and generating a distance matrix d based on the Euclidean distances d _i,j ; Based on the distance matrix d, select Q _nei nearest individuals X ⁱ (i=1, 2,...,Q _p ) to form a neighbor set:

For every nearest individual, let

Then the nearest Q _nei weight vectors of the weight vector σ ^j are:

Step S24, calculate the objective function value of each individual X ⁱ (i=1, 2,...,Q _p ): f ₁ (X ⁱ ), f ₂ (X ⁱ ),...,f _k (X ⁱ ),; Let the ideal point of the objective function value be:

in

i is a positive integer; Step S25, set the external population O ^* =Φ, the population iteration number is t, and t is a positive integer, and perform iterative evolution for each individual: Randomly select two individuals from the neighbor set C _i to generate new individuals

the new individual

added to the population G _t , i.e.

Update ideal point y ^* : if

but

Update the neighbor set C _i of each individual: Let σ ^i,l denote the weight vector of each element in the neighbor set C _i of the individual X ⁱ , l=1,2,...,Q _p , If g ^te (X ⁱ |σ ^i,l ,y ^* )≤g ^te (X ^i,l |σ ^i,l ,y ^* ), then X ^i,l =X ⁱ ; where X ^i,l represents each element in the neighbor set C _i ;

represents the Chebyshev value; F(X ⁱ ) represents the fitness function value corresponding to the individual X ⁱ ; Update the outer population O ^* : Determine whether there is a new individual in the outer population O ^*

The dominant solution, if it exists, remove the new individual from the outer population O ^*

the dominant solution; if it does not exist, the new individual

join the outer population O ^* ; Step S26, select, cross and mutate the population G ₀ to generate a new population, and determine whether the population iteration number t is less than the preset maximum iteration number, if so, go to step S24; if not, go to step S30. 4. a kind of computing migration method based on decomposition-based multi-objective optimization as claimed in claim 3, is characterized in that: described step S30 is specifically: Let the practical value of end-user satisfaction be:

The practical value of the benefits of edge cloud service providers is:

The practical value of each individual in population G ₀ is:

The individuals with the greatest practical value are:

where S ^min represents the minimum value of the end user satisfaction; S ^max represents the maximum value of the end user satisfaction; S(X ⁱ ) ^represents the end user satisfaction of the individual Xi; R ^min represents the minimum value of the edge cloud service provider's revenue ; R ^max represents the maximum value of edge cloud service provider revenue; R(X ⁱ ) ^represents the edge cloud service provider revenue of individual Xi; w ₁ represents the weight of end user satisfaction, w ₂ represents edge cloud service provider The weight of income, w ₁ +w ₂ =1.

Images