Disclosure of Invention
Aiming at the problems of incomplete resource characteristics and optimization targets considered in the prior art in a dynamic side-end cooperation scene, the invention provides a computational power resource scheduling method adapting to a dynamic environment in the side-end cooperation scene.
In order to achieve the above object, the present invention provides the following technical solutions:
The invention provides a computing power resource scheduling method adapting to dynamic environment in a side-end cooperation scene, which comprises the following steps:
s1, constructing resource assessment models of service requests, edge servers and algorithm units, wherein each resource assessment model is modeled from four dimensions of calculation, communication, storage and memory;
s2, predicting based on the historical service request quantity to obtain future service request quantity, and taking a prediction result as a basis of algorithm unit scheduling;
S3, evaluating the service request, the edge server and the algorithm unit by using resource indexes of four dimensions of calculation, communication, storage and memory, and matching the service request and the edge server according to an evaluation result;
s4, comprehensively predicting the obtained service request quantity, the matching result of the service request and the edge server, and the type of an algorithm unit required by the service request, and formulating a multi-objective optimization problem model by considering time delay, edge layer contribution degree and edge server resource utilization balance degree;
S5, carrying out algorithm unit scheduling based on a deep reinforcement learning algorithm.
Further, in step S1, the service request is modeled as a quad requesti＝(tci,tbi,tsi,tmi),0≤i<Mt, where elements in the quad respectively represent a calculation requirement, a communication requirement, a storage requirement, and a memory requirement of the service, and Mt represents the number of service requests in the current time slot t;
Modeling the edge server as a quadruple Ei＝(Ci,Bi,Si,Mi), wherein i < N is more than or equal to 0, and elements in the quadruple respectively represent computing capacity, communication capacity, storage capacity and memory capacity of the server, and N represents the number of the servers;
the algorithm unit is modeled as a quadruple rk＝(ck,bk,sk,mk), k is more than or equal to 0 and less than or equal to W, wherein elements in the quadruple respectively represent calculation resources, communication resources, storage resources and memory resources which are needed to be occupied by the algorithm unit, and W represents the number of the algorithm unit.
Further, in step S2, the method for predicting based on the historical service request amount is that the service request amount of the t time slot is set as X (t), the time sequence sliding window size d is adopted, and the service request amount of the past d time slots is used for predicting the service request amount of the future 1 time window by adopting a GRU deep learning algorithm.
Further, in step S3, the service request and the edge server are evaluated by using the resource indexes of four dimensions of calculation, communication, storage and memory, and the service request and the edge server data are normalized, which comprises the following steps:
Sequence of computing demands for a serviceNormalizing to obtain normalized resultSimilarly, the communication requirement, the storage requirement and the memory requirement of the service request are normalized, and the calculation, the communication, the storage and the memory resources owned by the edge server are normalized, so that the following results are obtained:
the normalized result of the resource requirement of the request i is expressed as
Representing the normalized result of the resources owned by the server i as
And then, giving different weights Q= (a, b, c, d) to the four indexes to obtain comprehensive evaluation results TRi and ERi, wherein the following formula is shown:
TRi＝GTi·QT
ERi＝GEi·QT
Wherein TRi is a comprehensive evaluation result of the service request i, ERi is a comprehensive evaluation result of the edge server i, GEi is a normalization result of resources owned by the edge server i, GTi is a normalization result of resource requirements of the service request i, and QT is a weight of four resource indexes.
Further, in step S3, the service request and the edge server are classified by a Rank method, and are matched by a Map method according to the classification;
the service request and the edge server are classified by a Rank method, and the method comprises the following steps:
1) Finding the maximum value and the minimum value in the comprehensive evaluation result sequence, and calculating the difference value;
2) Defining a number of levels rankcount to be divided;
3) Dividing the difference between the maximum value and the minimum value in the comprehensive evaluation result by the number of grades to obtain a grade spacing gap, namely, the difference between the maximum value and the minimum value in each grade range is gap;
4) The evaluation result corresponds to the grade interval to obtain a grading result;
The matching method by Map method according to the grade is as follows:
1) Selecting servers with the same grade for the service according to the grade of the service;
2) If the grade of a certain service is r, selecting a server with the grade of r, if the number of the servers with the grade of r is more than 1, selecting a server with the least service number from the servers to be matched with the service, and if the grade of a certain service is r but no server with the grade of r, selecting a server with the closest grade;
3) The final matching result matrix A is obtained and expressed as follows:
Where ai denotes that service i matches server ai.
Further, in step S4, the delay model construction process is as follows:
The service request needs to be transmitted to the server for processing, and is divided into two cases:
If the matched server j has an algorithm unit rk required by the service requesti, namely btj,k =1, the server directly responds to the service request;
if the matched server j does not have the algorithm unit rk required by the service requesti, namely btj,k =0, transmitting the service request to the central cloud;
In case one, the delay from the terminal device to the server isLet the case-time delay beIn the second case, if the response cannot be obtained and needs to be transmitted to the central cloud, the time delay of the second case is tauvc, the time delay of the service i is defined asIs expressed by the following formula:
the average delay is defined as:
Where M represents the number of service requests.
Further, in step S4, the edge layer contribution model construction process is as follows:
By usingIndicating whether the service request i can be responded at the edge layer, setting the server to which the service request i is matched as j, the algorithm unit required by the service request i as k,Is expressed by the following formula:
If the matched server j has an algorithm unit rk required by the service requesti, namely, btj,k =1, the server directly responds to the service request, and if the matched server j has no algorithm unit rk required by the service requesti, namely, btj,k =0, the service request is transmitted to the central cloud;
The contribution degree of the edge layer is expressed as Ht, defined as the ratio of the number of the services responded in the edge layer in the time slot t to the total number of the services, and expressed by the following formula:
Where Mt represents the number of service requests for the current slot t.
Further, in step S4, the edge server resource utilization balance degree model is constructed as follows:
let rcj(yj,zk) denote the percentage of the remaining resources of server j under a certain index, expressed as:
Wherein y epsilon { C, B, S, M } represents the current resource quantity of the server under a certain index, and z epsilon { C, B, S, M } represents the resources which the algorithm unit needs to occupy under a certain index;
The RCt＝{rc1,rc2,...,rcN is used for representing the current comprehensive resource quantity of the server after the algorithm unit is deployed, and the current resource quantity of the server is represented as follows:
The resource utilization balance deltat is defined as 1 minus the standard deviation of the rcj sequence, and represents the balance of the current resources of each server, and the resource utilization balance of the edge server is expressed by the following formula:
Wherein, theRepresenting the mean of the RCt sequence.
Further, the multi-objective optimization problem model of step S4 is constructed as follows:
Wherein, theThe average time delay is represented, Ht represents the contribution degree of the edge layer, deltat represents the resource utilization balance degree of the edge server, and alpha, beta and gamma represent weight coefficients of the time delay, the contribution degree of the edge layer and the resource utilization balance degree respectively.
Further, in step S5, the algorithm unit is deployed on the server by the scheduling method based on deep reinforcement learning, and the result is represented as a matrix Bt:
Wherein bij is a binary variable, if bij is 1, it indicates that algorithm unit j is present on server i, and if bij is 0, it indicates that algorithm unit j is not present on server i.
Compared with the prior art, the invention has the beneficial effects that:
According to the computing power resource scheduling method suitable for the dynamic environment in the side-end cooperation scene, in the dynamic side-end cooperation scene, the service request quantity is predicted, the service request, the edge server and the algorithm unit are evaluated by comprehensively considering multidimensional resources, the service request and the edge server are matched, the problem of scheduling the algorithm unit is solved by using a deep reinforcement learning algorithm, the algorithm unit is suitable for the dynamically changing environment, meanwhile, the time delay, the contribution degree of the edge layer and the resource utilization balance degree of the edge server are optimized, the time delay is optimized, the contribution degree of the edge layer is improved, and the resource utilization rate of the edge server is more balanced. Simulation experiments show that the method provided by the invention can reduce time delay to a certain extent, improve the contribution degree of the edge layer and improve the resource utilization balance degree of the edge server.
Detailed Description
The resources of the edge server are limited, a reasonable algorithm unit scheduling method is formulated, and the limited resources are fully utilized to provide service for the service request. The service request in the environment is dynamically changed, and the scheduling scheme of the algorithm unit is prepared by taking the dynamic characteristics of the environment into consideration, and simultaneously taking the service quality of the user and the resource utilization condition of the edge server into consideration. Therefore, the invention formulates the computing power resource scheduling method adapting to the dynamic environment in the side-end cooperation scene.
In order to better understand the technical solution, the technical solution in the embodiment of the present application will be clearly and completely described below with reference to the accompanying drawings in the embodiment of the present application. It will be apparent that the described examples are only some embodiments, but not all embodiments, of the present application. Based on the embodiments of the present application, all other embodiments obtained by the person skilled in the art based on the present application are included in the scope of protection of the present application.
The computing power resource scheduling method adapting to the dynamic environment in the side-end cooperation scene, as shown in figure 1, comprises the following steps:
S1, constructing resource assessment models of service requests, edge servers and algorithm units, wherein each resource assessment model is modeled from four dimensions of calculation, communication, storage and memory.
Specifically, the service request is modeled as a quad requesti＝(tci,tbi,tsi,tmi),0≤i<Mt, where the elements in the quad represent the computation requirement, communication requirement, storage requirement, and memory requirement of the service, and Mt represents the number of service requests in the current slot t.
Modeling the edge server as a quadruple Ei＝(Ci,Bi,Si,Mi), wherein i < N is more than or equal to 0, and the elements in the quadruple respectively represent the computing capacity, communication capacity, storage capacity and memory capacity of the server, and N represents the number of the servers.
When the algorithm unit is operated, certain calculation, communication, storage and memory resources are occupied, and the resources occupied by the algorithm unit with the type of rk are represented by four-element rk＝(ck,bk,sk,mk), wherein k is more than or equal to 0 and less than or equal to W. Wherein, elements in the quadruple respectively represent calculation resources, communication resources, storage resources and memory resources which are needed to be occupied by the algorithm units, and W represents the number of the algorithm units.
The service request quantity has a certain time characteristic, so that a service prediction model is firstly trained according to the historical data characteristics of the service and is used for predicting the future service request quantity. And adopting a GRU deep learning algorithm to actively predict the service request quantity, and taking a prediction result as a basis of algorithm unit scheduling. Let the traffic request of the t-th time slot be X (t), the time series sliding window size d, and use the traffic request of the past d time slots to predict the traffic request of the future 1 time window. The method comprises the steps of predicting by adopting GRU, in a training stage, a historical observation sample set is X= { X (t-d), (t-d+1),. The use of { X (t-d) }, the use of X (t-1) } as input of a GRU network model, outputting a prediction result X '(t), and adjusting model parameters by comparing X' (t) and X (t), so as to perform model training.
S2, predicting based on the historical service request quantity to obtain the future service request quantity, and taking a prediction result as a basis of algorithm unit scheduling.
The method for predicting based on the historical service request quantity is to set the service request quantity of the t-th time slot as X (t), the time sequence sliding window size d, and the service request quantity of the past d time slots is used for predicting the service request quantity of the future 1 time window by adopting a GRU deep learning algorithm.
The invention formulates a matching method of the service and the server taking the resource as a main consideration factor. Firstly, comprehensively evaluating the service requirements and the server resources to obtain a comprehensive evaluation result. And then classifying the service and the server according to the evaluation result. After grading, the service and the server are matched according to the grade. If the method is not adopted, the service with large resource requirement can be matched with the server with poor performance, so that the service requirement can not be met. By adopting the method, the resources of the server can be more reasonably utilized, and the matching result can also provide effective reference for the subsequent algorithm unit scheduling work.
S3, evaluating the service request, the edge server and the algorithm unit by using resource indexes of four dimensions of calculation, communication, storage and memory, and matching the service request and the edge server according to an evaluation result.
Specifically, the service request and the edge server are evaluated, and the service request and the edge server data are normalized, wherein the process is as follows:
computing demand sequence for all servicesNormalizing to obtain normalized resultSimilarly, the communication requirement, the storage requirement and the memory requirement of the service request are normalized, and the calculation, the communication, the storage and the memory resources owned by the edge server are normalized, so that the following results are obtained:
the normalized result of the resource requirement of the request i is expressed as
Representing the normalized result of the resources owned by the server i as
And then, giving different weights Q= (a, b, c, d) to the four indexes to obtain comprehensive evaluation results TRi and ERi, wherein the following formula is shown:
TRi＝GTi·QT
ERi＝GEi·QT
Wherein TRi is a comprehensive evaluation result of the service request i, ERi is a comprehensive evaluation result of the edge server i, GEi is a normalization result of resources owned by the edge server i, GTi is a normalization result of resource requirements of the service request i, and QT is a weight of four resource indexes.
Then, the service request and the server are classified by a Rank method, are matched by a Map method, and a matching result is defined as a matrix A.
The service request and the edge server are classified by a Rank method, and the method comprises the following steps:
The service and server are classified according to the comprehensive evaluation results TRi and ERi:
Rank(TRi)＝RTRi
Rank(ERi)＝RERi
for the hierarchical Rank, the following is defined:
1) Finding the maximum value and the minimum value in the comprehensive evaluation result sequence, and calculating the difference value;
2) Defining the number of levels rankcount to be divided, for example, to be divided into 5 levels, rankcount =5;
3) Dividing the difference between the maximum value and the minimum value in the comprehensive evaluation result by the number of grades to obtain a grade spacing gap, namely, the difference between the maximum value and the minimum value in each grade range is gap;
4) And (5) corresponding the evaluation result to the grade interval to obtain a grading result.
After grading, the service and the server are matched according to the grades by a Map method, and the method comprises the following steps:
1) Selecting servers with the same grade for the service according to the grade of the service;
2) If the grade of a certain service is r, selecting a server with the grade of r, if the number of the servers with the grade of r is more than 1, selecting a server with the least service number from the servers to be matched with the service, and if the grade of a certain service is r but no server with the grade of r, selecting a server with the closest grade;
3) The final matching result matrix A is obtained and expressed as follows:
Where ai denotes that service i matches server ai.
Different services require different algorithm units to serve them, and the mapping relation NS (requesti)＝rk indicates that the algorithm unit required for service i is rk.
As shown in fig. 2. Firstly, classifying service requests and servers through a comprehensive evaluation method and a classification method to obtain classification results of the service requests and the servers, and then matching the service requests and the servers through a matching method Map according to the classification results.
S4, comprehensively predicting the obtained service request quantity, the matching result of the service request and the edge server, and the type of an algorithm unit required by the service request, and formulating a multi-objective optimization problem model by considering time delay, edge layer contribution degree and edge server resource utilization balance degree.
Specifically, the time delay model construction process is as follows:
The service request needs to be transmitted to the server for processing, and is divided into two cases:
If the matched server j has an algorithm unit rk required by the service requesti, namely btj,k =1, the server directly responds to the service request;
if the matched server j does not have the algorithm unit rk required by the service requesti, namely btj,k =0, transmitting the service request to the central cloud;
In case one, the delay from the terminal device to the server isLet the case-time delay beIn the second case, if the response cannot be obtained and needs to be transmitted to the central cloud, the time delay of the second case is tauvc, the time delay of the service i is defined asIs expressed by the following formula:
the average delay is defined as:
Where M represents the number of service requests.
The edge layer contribution degree model construction process is as follows:
One of the optimization goals of the scheme is to make the service request respond to the matched edge server to the maximum extent so as to maximize the effect of the edge layer. Thus, the edge layer contribution is set. And matching the service with the server by using the matching method, wherein if the server has an algorithm unit required by the service request, the service request can be processed, the service can be responded at the edge layer, otherwise, the service cannot be responded at the edge layer. The edge layer contribution is denoted as Ht and is defined as the ratio of the number of traffic in the edge layer response to the total number of traffic in the time slot t.
By usingIndicating whether the service request i can be responded at the edge layer, setting the server to which the service request i is matched as j, the algorithm unit required by the service request i as k,Is expressed by the following formula:
If the matched server j has an algorithm unit rk required by the service requesti, namely, btj,k =1, the server directly responds to the service request, and if the matched server j has no algorithm unit rk required by the service requesti, namely, btj,k =0, the service request is transmitted to the central cloud;
The contribution degree of the edge layer is expressed as Ht, defined as the ratio of the number of the services responded in the edge layer in the time slot t to the total number of the services, and expressed by the following formula:
Where Mt represents the number of service requests for the current slot t.
The edge server resource utilization balance degree model is constructed as follows:
The algorithm unit needs to occupy the resource space of the server. In order to keep the resource utilization conditions of the servers as balanced as possible, the invention defines the resource utilization balance degree to represent the difference degree of the resource utilization conditions of each server.
Let rcj(yj,zk) denote the percentage of the remaining resources of server j under a certain index, expressed as:
Wherein y epsilon { C, B, S, M } represents the current resource amount of the server under a certain index, z epsilon { C, B, S, M } represents the resources which the algorithm unit needs to occupy under a certain index, and rcj(Cj,ck) represents the current residual resource percentage of the server j under the calculation index.
The RCt＝{rc1,rc2,...,rcN is used for representing the current comprehensive resource quantity of the server after the algorithm unit is deployed, and the current resource quantity of the server is expressed as follows because four indexes have large difference in magnitude order:
The constraint is that none of the four sub-terms in the following formula is less than zero.
The resource utilization balance deltat is defined as 1 minus the standard deviation of the rcj sequence, and represents the balance of the current resources of each server, and the resource utilization balance of the edge server is expressed by the following formula:
Wherein, theThe larger deltat, the more uniform the resource utilization, which represents the mean of the RCt sequence.
From the service perspective, they need to get a response as soon as possible to get a response at the edge server, so the delay is an important evaluation index, and the invention expects a smaller delay. From the perspective of the edge server, the function exerted by the edge layer should be maximized, so that as many service requests as possible are responded at the edge layer, and meanwhile, the resource utilization of each server should be kept balanced as much as possible when the algorithm unit is scheduled. Thus, the present invention formulates a total optimization objective function G as follows.
The multi-objective optimization problem model (comprehensive optimization objective) is constructed as follows:
Wherein, theThe average time delay is represented, Ht represents the contribution degree of the edge layer, deltat represents the resource utilization balance degree of the edge server, and alpha, beta and gamma represent weight coefficients of the time delay, the contribution degree of the edge layer and the resource utilization balance degree respectively.
S5, carrying out algorithm unit scheduling based on a deep reinforcement learning algorithm.
In the deep reinforcement learning algorithm, an agent interacts with the environment to learn, and a scheduling decision is made based on the real-time state of the environment, so that the method can be well adapted to the dynamically-changing environment, and the scheduling problem is solved by adopting the deep reinforcement learning algorithm. In addition, the deployment scene of the invention comprises a plurality of servers and a plurality of algorithm units, the state space and the action space are high in dimensionality, and the high-dimensional problem is difficult to solve by the Q learning method in reinforcement learning, so that the DQN method combining reinforcement learning and deep learning is adopted. The method interacts with the environment, and realizes the dynamic scheduling of the algorithm unit according to the dynamically changed environment information. In addition, in order to prevent the algorithm unit from occupying server resources for a long time, a life cycle is set for the algorithm unit, and the deployed algorithm unit is automatically deleted and corresponding resource space is released after reaching a certain life cycle Tend. The method can dynamically schedule the algorithm units, reduce the time delay to the maximum extent, improve the service response rate and improve the utilization balance of the server resources.
Specifically, the invention deploys the algorithm unit on the server through the scheduling method based on deep reinforcement learning, and the result is represented as a matrix Bt:
Wherein bij is a binary variable, if bij is 1, it indicates that algorithm unit j is present on server i, and if bij is 0, it indicates that algorithm unit j is not present on server i.
The algorithm model training process is as follows:
firstly, defining a state space, an action space and a reward function in an algorithm unit scheduling environment, wherein a Markov model is defined as follows:
The state is that the current algorithm unit on the server has state (t) = [ s0,s1,...,sp,...,sN*W-1],sp epsilon {0,1}, if sp = 1, let p/N = i, p% N = j, wherein N is the number of the servers and W is the number of the algorithm units, namely, the element number p divided by the number of the servers is equal to i by the whole, the remainder is j, and the like, which indicates that the algorithm unit j exists on the server i;
The method comprises the actions that an algorithm unit scheduling decision a (t) = [ ac0,ac1,...,acW-1],0≤aci < N, wherein aci represents that an algorithm unit i is deployed on a server aci, if the algorithm unit exists, the deployment is not repeated, and if the residual resources of the server can not meet the resource requirements of the algorithm unit, the deployment is not performed;
the rewarding function is set as a comprehensive optimization objective function;
R(t)=Gt (16)
Then defining an algorithm unit existence time matrix:
wherein N is the number of servers, W is the number of algorithm units, di.j represents the existing time of the algorithm unit j on the server i, and is used for judging whether the algorithm unit reaches the life cycle limit or not and whether the algorithm unit needs to be deleted or not.
The algorithm unit scheduling algorithm flow based on the deep reinforcement learning is shown in table 1.
Table 1 algorithm unit scheduling algorithm flow based on deep reinforcement learning
And predicting based on the historical service request amount, randomly generating the resource amount of the edge server, the service request and the resource requirement of the algorithm unit, matching the service request and the edge server, and training a scheduling algorithm based on deep reinforcement learning. And setting the weights of the time delay, the edge layer contribution degree and the edge server resource utilization balance degree in the comprehensive optimization objective function to be alpha=1, beta=5 and gamma=1 respectively. And performing algorithm unit scheduling by using a trained algorithm unit scheduling method based on deep reinforcement learning, and comparing the algorithm unit scheduling with a random scheduling method and a greedy scheduling method only optimizing time delay. The comparison results under the three indexes are shown in fig. 3, 4 and 5 respectively. Fig. 3 shows the time delay comparison result, wherein the time delay obtained by the greedy scheduling method only optimizing the time delay is optimal, the scheduling method based on deep reinforcement learning is inferior, and the random scheduling method is worst. Fig. 4 shows the comparison result of the edge layer contribution, wherein the edge layer contribution obtained by the greedy scheduling method only optimizing the time delay is optimal, the scheduling method based on deep reinforcement learning is inferior, and the random scheduling method is worst. Fig. 5 shows the comparison of the degree of resource utilization balance, wherein the time delay obtained by the scheduling method based on deep reinforcement learning is optimal, the random scheduling method is inferior, and the greedy scheduling method only optimizing the time delay is worst. The greedy scheduling method only optimizing the time delay only considers the time delay, and meanwhile, the greedy scheduling method only optimizing the time delay under the two indexes performs optimally because the contribution degree of the edge layer and the time delay are closely related, but the greedy scheduling method ignores other indexes, so that the resource utilization balance degree is the worst. The scheduling method based on deep reinforcement learning comprehensively considers three indexes, and compared with a random scheduling method, the scheduling method based on deep reinforcement learning is optimized to a certain extent. Simulation experiments show that the method provided by the invention can reduce time delay to a certain extent, improve the contribution degree of the edge layer and improve the resource utilization balance degree of the edge server.
The foregoing is merely illustrative of the preferred embodiments and principles of the present invention, and not in limitation thereof. Any modification, equivalent replacement, improvement, etc. which are within the spirit and principle of the present invention, should be considered as the protection scope of the present invention, based on the ideas provided by the present invention, for those skilled in the art.