CN111818130A - Joint optimization of cache and computation based on reinforcement learning - Google Patents

Abstract

The embodiment of the present invention discloses the joint optimization of caching and computing in the NOMA-MEC system based on reinforcement learning, which mainly involves the joint caching and unloading problems of the NOMA-MEC system of multi-user and multi-MEC servers. Computational results can be shared among servers by extending the local cache of a single server to a cooperative cache of multiple servers. In order to minimize the delay of the whole system, find the optimal caching and unloading strategy for each user.

Description

Joint optimization of cache and computation based on reinforcement learning

technical field

The invention relates to the field of communication, in particular to a joint optimization based on reinforcement learning cache and calculation.

Background technique

With the development of science and technology, users have higher and higher requirements for the processing speed of mobile communication services. In order to speed up the processing speed of mobile communication services, reduce the delay of data transmission, and improve user experience, the mobile communication industry is discussing the use of wireless access A mobile edge computing server is set at the edge of the network, and the mobile edge computing server can provide computing capability and/or storage capability for users accessing the wireless network.

Both Non-orthogonal Multiple Access (NOMA) and Mobile Edge Computing (MEC) are considered to be very promising technologies in next-generation wireless networks. With the rapid development of intelligent communication, mobile edge computing is increasingly used in the field of future communication. It can improve the computing power of users in applications, and can play an important role in fields such as virtual reality, augmented reality, and unmanned driving. . Unlike using traditional cloud computing systems, mobile edge computing can provide computing power in cloud radio access networks. The basic idea of mobile edge computing is to use the facilities with powerful computing power in the radio network. By using the mobile edge computing server integrated in the base station, users can offload computing tasks to the mobile edge computing server located at the edge of the network, and then use the mobile edge computing server integrated in the base station. Mobile edge computing servers perform task computing. Since mobile edge computing servers can be deployed near users, a network using mobile edge computing can provide users with low-latency and low-energy-consuming task computing services.

In a system combining Mobile Edge Computing (MEC) and Non-Orthogonal Multiple Access (NOMA), offload computing is mainly used to reduce latency and energy consumption. Due to the limited computing capacity of the MEC server, and in the MEC system, the tasks offloaded by different users are often the same. In order to avoid repeated transmission and computation of the same task, caching is an effective solution to reduce latency. For the cache in the NOMA-MEC system, only one MEC server and local cache are considered in the prior art. The cache capacity of a single MEC server is limited, so it is difficult to cache more task computation results. If the types of tasks requested by multiple users are diverse, it will result in a lower hit rate. In this case, the unfinished tasks can only be calculated, so the delay cannot be effectively reduced.

SUMMARY OF THE INVENTION

In order to solve the above technical problems, the embodiments of the present invention provide joint optimization of caching and computing in NOMA-MEC system based on reinforcement learning, which can also be said to be a method based on reinforcement learning, in order to minimize the delay. It mainly involves the joint caching and unloading of NOMA-MEC system with multi-user and multi-MEC server. Computational results can be shared among servers by extending the local cache of a single server to a cooperative cache of multiple servers. In order to minimize the delay of the whole system, it is necessary to find the optimal caching and unloading strategy for each user.

The embodiment of the present invention provides the following technical solutions:

A joint optimization based on reinforcement learning caching and computing, applied to the NOMA-MEC system, jointly optimizes caching and computing, by extending the local cache of a single server to the cooperative cache of multiple servers, multiple servers can share computing As a result, in order to minimize the delay of the entire system and find the optimal caching and unloading strategy for each user, the method includes:

According to the different decision-making methods of users, generate local cache, cooperative cache, local computing and delay functions in offload computing mode;

Considering that the task popularity is dynamic and unknown, a gated recursive unit algorithm is proposed to predict the task popularity, and the calculation results with high popularity are placed on the corresponding mobile edge computing server for caching.

Based on the calculation results cached on the server, the multi-agent deep Q-network algorithm is used to find the optimal caching and unloading decisions;

Wherein, according to the different decision-making methods of users, generating local cache, collaborative cache, local computing and offloading computing mode of delay function, specifically includes:

1) For users who choose local caching, its latency is negligible compared to cooperative caching and offloading computation.

2) In the cooperative cache mode, the delay of processing tasks is mainly the delay T _m,n generated by the transmission between servers:

where r _m,n represents the download rate of the local server m and the cooperative server n, and M _j represents the size of the calculation result of task j.

在 MEC服务器上的处理时延

和回传时延

三部分组成。由于回传时延较小，一般可以忽略。3) If the user chooses to offload the calculation, in order to improve the spectrum utilization rate and further reduce the transmission delay, the NOMA technology is used to transmit the information to the local base station. The latency of processing tasks is determined by the offload latency

Processing Latency on MEC Server

and return delay

It consists of three parts. Since the return delay is small, it can generally be ignored.

其中W_j表示处理任务j总的CPU周期数，

是用户i在本地计算阶段的计算容量。For users who choose local computing, the local execution delay is

where W _j represents the total number of CPU cycles for processing task j,

is the computing capacity of user i in the local computing phase.

Among them, considering that the task popularity is dynamic and unknown, a gated recursive unit algorithm is proposed to predict the task popularity, and the calculation results with high popularity are placed on the corresponding mobile edge computing server for caching, specifically including:

1) Collect the tasks requested by the user at historical moments and the calculation results of different tasks, and perform the following operations.

2) Input the popularity of the historical period {S _j (1), S _j (2),...S _j (T _M )}, where S _j (t) represents the popularity of task j at time t. After the GRU unit, the predicted popularity {S _j (T _M +1), S _j (T _M +2), ··· S _j (T _M +T _N )} of length T _N is obtained.

通过不断调整参数，使损失函数变小。3) Calculate the loss function between the predicted popularity q(j) and the real popularity p(j) when the predicted moment arrives

By continuously adjusting the parameters, the loss function becomes smaller.

4) Stop training until the loss function no longer changes, otherwise, return to 1).

Due to the limited cache space of the server, it is difficult to store the results of all tasks. Considering the cache capacity of the server and the size of the calculation results, the calculation results of the tasks are cached on the server in descending order of popularity, so that as many as possible Cache the calculation results of the task locally. In this way, other servers also use the GRU algorithm to cache the corresponding calculation results. These servers have placed the computation results of popular tasks before all users request tasks, which is beneficial for hitting local caches and cooperative caches.

Wherein, based on the calculation results cached on the server, the multi-agent deep Q network algorithm is used to find the optimal caching and unloading decisions, specifically including:

In a multi-agent system, each user in the same base station is considered an agent. Each agent is unaware of the behavior of other agents before making a decision. Based on the state information of the environment, the agent chooses its own actions. Before choosing an action, you need to judge the hit situation. Based on the state information and the task requested by the user, the user can know whether the local cache or the cooperative cache was hit. The user can choose a caching decision only when the cache is hit. After the agent obtains state information and makes an action choice, the environment will feed back reward information to the agent for judging the quality of the action. Considering the reward value, the agent continuously adjusts its behavior to maximize the reward. The specific process of the MADQN algorithm is as follows:

等变量。1) Initialize state s _i , action a _i , reward _ri , current Q network Q(s, a; θ) and target Q network

etc. variables.

其中μ(t)是在时间t上，存储在所有服务器上任务的序号。

表示用户i在本地服务器m上的时延。

是MEC服务器剩余的计算容量。ξ(t)代表在同一基站中N个用户可利用的能耗。2) For each agent, observe the initial state

where μ(t) is the sequence number of the task stored on all servers at time t.

Indicates the delay of user i on the local server m.

is the remaining computing capacity of the MEC server. ξ(t) represents the energy consumption available to N users in the same base station.

代理以高概率1-ε选择最优的决策。否则，它将以ε的概率随机的选择缓存和卸载决策。其中

是任务卸载决策，

表示本地计算决策，

分别表示本地缓存和协作缓存决策，ε为影响因子。3) Choose action according to greedy algorithm

The agent chooses the optimal decision with high probability 1-ε. Otherwise, it randomly chooses cache and unload decisions with probability ε. in

is the task offloading decision,

represents a local computing decision,

represent local cache and cooperative cache decisions, respectively, and ε is the impact factor.

4) Update reward r _i (t)=T _i (t-1)-T _i (t), where T _i (t) and T _i (t-1) represent user i at time t and t-1, respectively delay.

5) Store the experience e _i (t) of agent i at time t into the experience playback unit D(t), and extract a small batch of transfer sequences from it during training.

6) Use stochastic gradient descent to update the loss function L(t).

7) Update the next state s(t+1)←s(t).

8) Stop training until the parameter θ converges.

According to the above method, the selection of buffering and unloading decisions can be performed among users of other base stations. Since the delay of the whole system is composed of the delays of multiple base stations, the delay of the whole system can be minimized by reducing the delay of different base stations. delay to achieve.

Compared with the prior art, the above technical solution has the following advantages:

The embodiments of the present invention provide joint optimization of caching and computing in the NOMA-MEC system based on reinforcement learning, which can also be said to be a method based on reinforcement learning to jointly optimize the caching and computing in the NOMA-MEC system. First, considering the problems of calculation result caching and task offloading among multiple servers, the cache hit rate is improved by means of cooperative caching among multiple services. Secondly, considering the more reasonable situation that task popularity is dynamic and unknown, we propose a novel task popularity prediction method called Gated Recurrent Unit, which is used for the first time for task popularity. predict. Using this algorithm to predict the popularity of tasks, for the popularity that changes dynamically over time, it can predict more accurately by appropriately increasing the learning rate. Finally, based on the predicted popularity, a multi-agent deep Q-network algorithm is used to autonomously select caching and offloading decisions, which can minimize latency through continuous training.

Description of drawings

In order to illustrate the embodiments of the present invention or the technical solutions in the prior art more clearly, the following briefly introduces the accompanying drawings that need to be used in the description of the embodiments or the prior art. Obviously, the drawings in the following description are For some embodiments of the present invention, for those of ordinary skill in the art, other drawings can also be obtained according to these drawings without creative efforts.

FIG. 1 is a schematic diagram of joint optimization based on reinforcement learning caching and computing provided by an embodiment of the present invention.

Detailed ways

As mentioned in the background section, for the cache in the NOMA-MEC system, only one MEC server and local cache are considered in the prior art. The cache capacity of a single MEC server is limited, so it is difficult to cache more task computation results. If the types of tasks requested by multiple users are diverse, it will result in a lower hit rate. In this case, the unfinished tasks can only be calculated, so the delay cannot be effectively reduced.

In view of the deficiencies of the prior art, this application proposes a joint optimization of caching and computing based on reinforcement learning, which is applied in the NOMA-MEC system, which mainly involves the joint caching and unloading of the NOMA-MEC system with multiple users and multiple MEC servers. . Computational results can be shared among servers by extending the local cache of a single server to a cooperative cache of multiple servers. In order to minimize the delay of the whole system, it is necessary to find the optimal caching and unloading strategy for each user.

As shown in Figure 1, this application proposes a joint optimization based on reinforcement learning caching and computing, which is applied in the NOMA-MEC system. By extending the local cache of a single server to the cooperative cache of multiple servers, multiple servers can Sharing the calculation results, in order to minimize the delay of the entire system, find the optimal caching and unloading strategy for each user, including:

The first step is to generate local cache, cooperative cache, local computing and offload computing mode delay functions according to different decision-making methods of users.

1) For users who choose local caching, its latency is negligible compared to cooperative caching and offloading computation.

2) In the cooperative cache mode, the delay of processing tasks is mainly the delay T _m,n generated by the transmission between servers:

where r _m,n represents the download rate of the local server m and the cooperative server n, and M _j represents the size of the calculation result of task j.

在 MEC服务器上的处理时延

和回传时延

三部分组成。由于回传时延较小，一般可以忽略。3) If the user chooses to offload the calculation, in order to improve the spectrum utilization rate and further reduce the transmission delay, the NOMA technology is used to transmit the information to the local base station. The latency of processing tasks is determined by the offload latency

Processing Latency on MEC Server

and return delay

It consists of three parts. Since the return delay is small, it can generally be ignored.

其中W_j表示处理任务j总的CPU周期数，f_i ^l是用户i在本地计算阶段的计算容量。For users who choose local computing, the local execution delay is

where W _j represents the total number of CPU cycles for processing task j, and f _i ^l is the computing capacity of user i in the local computing phase.

The second step is to decide what to cache on the MEC server. Considering that the task popularity is dynamic and unknown, a Gated Recurrent Unit (GRU) algorithm is proposed to predict the task popularity, and the calculation results with high popularity are placed on the corresponding server. The specific process is as follows:

1) Collect the tasks requested by the user at historical moments and the calculation results of different tasks, and perform the following operations.

2) Input the popularity of the historical period {S _j (1), S _j (2),...S _j (T _M )}, where S _j (t) represents the popularity of task j at time t. After the GRU unit, the predicted popularity {S _j (T _M +1), S _j (T _M +2), ··· S _j (T _M +T _N )} of length T _N is obtained.

通过不断调整参数，使损失函数变小。3) Calculate the loss function between the predicted popularity q(j) and the real popularity p(j) when the predicted moment arrives

By continuously adjusting the parameters, the loss function becomes smaller.

4) Stop training until the loss function no longer changes, otherwise, return to 1).

Due to the limited cache space of the server, it is difficult to store the results of all tasks. Considering the cache capacity of the server and the size of the calculation results, the calculation results of the tasks are cached on the server in descending order of popularity, so that as many as possible Cache the calculation results of the task locally. In this way, other servers also use the GRU algorithm to cache the corresponding calculation results. These servers have placed the computation results of popular tasks before all users request tasks, which is beneficial for hitting local caches and cooperative caches.

In the third step, based on the calculation results cached on the server, the Multi-agent Deep-Q-network (MADQN) algorithm is used to find the optimal caching and unloading decisions.

In a multi-agent system, each user in the same base station is considered an agent. Each agent is unaware of the behavior of other agents before making a decision. Based on the state information of the environment, the agent chooses its own actions. Before choosing an action, you need to judge the hit situation. Based on the state information and the task requested by the user, the user can know whether the local cache or the cooperative cache was hit. The user can choose a caching decision only when the cache is hit. After the agent obtains state information and makes an action choice, the environment will feed back reward information to the agent for judging the quality of the action. Considering the reward value, the agent continuously adjusts its behavior to maximize the reward. The specific process of the MADQN algorithm is as follows:

等变量。1) Initialize state s _i , action a _i , reward _ri , current Q network Q(s, a; θ) and target Q network

etc. variables.

其中μ(t)是在时间t上，存储在所有服务器上任务的序号。

表示用户i在本地服务器m上的时延。

是MEC服务器剩余的计算容量。ξ(t)代表在同一基站中N个用户可利用的能耗。2) For each agent, observe the initial state

where μ(t) is the sequence number of the task stored on all servers at time t.

Indicates the delay of user i on the local server m.

is the remaining computing capacity of the MEC server. ξ(t) represents the energy consumption available to N users in the same base station.

代理以高概率1-ε选择最优的决策。否则，它将以ε的概率随机的选择缓存和卸载决策。其中

是任务卸载决策，

表示本地计算决策，

分别表示本地缓存和协作缓存决策，ε为影响因子。3) Choose action according to greedy algorithm

The agent chooses the optimal decision with high probability 1-ε. Otherwise, it randomly chooses cache and unload decisions with probability ε. in

is the task offloading decision,

represents a local computing decision,

represent local cache and cooperative cache decisions, respectively, and ε is the impact factor.

4) Update reward r _i (t)=T _i (t-1)-T _i (t), where T _i (t) and T _i (t-1) represent user i at time t and t-1, respectively delay.

5) Store the experience e _i (t) of agent i at time t into the experience playback unit D(t), and extract a small batch of transfer sequences from it during training.

6) Use stochastic gradient descent to update the loss function L(t).

7) Update the next state s(t+1)←s(t).

8) Stop training until the parameter θ converges.

According to the above method, the selection of buffering and unloading decisions can be performed among users of other base stations. Since the delay of the whole system is composed of the delays of multiple base stations, the delay of the whole system can be minimized by reducing the delay of different base stations. delay to achieve.

It can be seen that the embodiments of the present invention provide joint optimization of caching and computing in NOMA-MEC system based on reinforcement learning, which can also be said to be a method based on reinforcement learning to jointly optimize caching and computing in NOMA-MEC system. First, considering the problems of calculation result caching and task offloading among multiple servers, the cache hit rate is improved by means of cooperative caching among multiple services. Secondly, considering the more reasonable situation that task popularity is dynamic and unknown, we propose a novel task popularity prediction method called Gated Recurrent Unit, which is used for the first time for task popularity. predict. Using this algorithm to predict the popularity of tasks, for the popularity that changes dynamically over time, it can predict more accurately by appropriately increasing the learning rate. Finally, based on the predicted popularity, a multi-agent deep Q-network algorithm is used to autonomously select caching and offloading decisions, which can minimize latency through continuous training.

To sum up, the present application has the following advantages:

(1) By extending the local cache of a single server to the cooperative cache of multiple servers, the calculation results can be shared among multiple servers. Comparing the local cache of a single server, the cooperative cache among multiple servers can improve the cache hit rate. That is to say, the present application takes into account the problems of calculation result caching and task offloading among multiple servers, and improves the cache hit rate by means of cooperative caching among multiple services.

(2) The calculation result caching method combining NOMA and MEC is proposed to solve the problem of limited computing resources and spectrum resources.

(3) Consider the more plausible case that task popularity is dynamic and unknown. In response to this more reasonable situation, this application proposes a novel task popularity prediction method called GRU, which uses the GRU algorithm to predict the task popularity. For the popularity that changes dynamically over time, by appropriately increasing the learning rate, it predicts more accurate. And the algorithm is the first to be used for task popularity prediction.

(4) Based on the predicted popularity, the MADQN algorithm is proposed to optimize the caching and unloading decisions. It can find the optimal caching and unloading strategy in the case of a large state-action space, so as to minimize the system delay. The MADQN algorithm is used to autonomously select cache and unload decisions, and through continuous training, it can achieve the goal of minimizing latency.

Each part in this specification is described in a progressive manner, and each part focuses on the differences from other parts, and it is sufficient to refer to each other for the same and similar parts among the various parts.

The above description of the disclosed embodiments enables any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be implemented in other embodiments without departing from the spirit or scope of the invention. Thus, the present invention is not intended to be limited to the embodiments shown herein, but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

Claims (1)

1. Based on the joint optimization of reinforcement learning cache and calculation, it is characterized in that, applied in the NOMA-MEC system, by extending the local cache of a single server to the cooperative cache of multiple servers, the calculation results can be shared between multiple servers, In order to minimize the delay of the whole system and find the optimal caching and unloading strategy for each user, the method includes: The first step is to generate local cache, cooperative cache, local computing and offload computing mode delay functions according to different decision-making methods of users. In the second step, considering that the task popularity is dynamic and unknown, a gated recursive unit algorithm is proposed to predict the task popularity, and the calculation results with high popularity are placed on the corresponding mobile edge computing server for caching. In the third step, based on the calculation results cached on the server, the multi-agent deep Q-network algorithm is used to find the optimal caching and unloading decisions. Wherein, according to the different decision-making methods of users, generating local cache, collaborative cache, local computing and offloading computing mode of delay function, specifically includes: 1) For users who choose local caching, its latency is negligible compared to cooperative caching and offloading computation. 2) In the cooperative cache mode, the delay of processing tasks is mainly the delay T _m,n generated by the transmission between servers:

where r _m,n represents the download rate of the local server m and the cooperative server n, and M _j represents the size of the calculation result of task j. 3) If the user chooses to offload the calculation, in order to improve the spectrum utilization rate and further reduce the transmission delay, the NOMA technology is used to transmit the information to the local base station. The latency of processing tasks is determined by the offload latency

Processing Latency on MEC Server

and return delay

It consists of three parts. Since the return delay is small, it can generally be ignored. For users who choose local computing, the local execution delay is

where W _j represents the total number of CPU cycles for processing task j, and f _i ^l is the computing capacity of user i in the local computing phase. Among them, considering that the task popularity is dynamic and unknown, a gated recursive unit algorithm is proposed to predict the task popularity, and the calculation results with high popularity are placed on the corresponding mobile edge computing server for caching, specifically including: 1) Collect the tasks requested by the user at historical moments and the calculation results of different tasks, and perform the following operations. 2) Input the popularity of the historical period {S _j (1), S _j (2),...S _j (T _M )}, where S _j (t) represents the popularity of task j at time t. After the GRU unit, the predicted popularity {S _j (T _M +1), S _j (T _M +2), ... S _j (T _M +T _N )} of length T _N is obtained. 3) Calculate the loss function between the predicted popularity q(j) and the real popularity p(j) when the predicted moment arrives

By continuously adjusting the parameters, the loss function becomes smaller. 4) Stop training until the loss function no longer changes, otherwise, return to 1). Due to the limited cache space of the server, it is difficult to store the results of all tasks. Considering the cache capacity of the server and the size of the calculation results, the calculation results of the tasks are cached on the server in descending order of popularity, so that as many as possible Cache the calculation results of the task locally. In this way, other servers also use the GRU algorithm to cache the corresponding calculation results. These servers have placed the computation results of popular tasks before all users request tasks, which is beneficial for hitting local caches and cooperative caches. Wherein, based on the calculation results cached on the server, the multi-agent deep Q network algorithm is used to find the optimal caching and unloading decisions, specifically including: In a multi-agent system, each user in the same base station is considered an agent. Each agent is unaware of the behavior of other agents before making a decision. Based on the state information of the environment, the agent chooses its own actions. Before choosing an action, you need to judge the hit situation. Based on the state information and the task requested by the user, the user can know whether the local cache or the cooperative cache was hit. The user can choose a caching decision only when the cache is hit. After the agent obtains state information and makes an action choice, the environment will feed back reward information to the agent for judging the quality of the action. Considering the reward value, the agent continuously adjusts its behavior to maximize the reward. The specific process of the MADQN algorithm is as follows: 1) Initialize state s _i , action a _i , reward _ri , current Q network Q(s, a; θ) and target Q network

etc. variables. 2) For each agent, observe the initial state

where μ(t) is the sequence number of the task stored on all servers at time t.

Indicates the delay of user i on the local server m.

is the remaining computing capacity of the MEC server. ξ(t) represents the energy consumption available to N users in the same base station. 3) Choose action according to greedy algorithm

The agent chooses the optimal decision with high probability 1-ε. Otherwise, it randomly chooses cache and unload decisions with probability ε. in

is the task offloading decision,

represents a local computing decision,

and

represent local cache and cooperative cache decisions, respectively, and ε is the impact factor. 4) Update reward r _i (t)=T _i (t-1)-T _i (t), where T _i (t) and T _i (t-1) represent user i at time t and t-1, respectively delay. 5) Store the experience e _i (t) of agent i at time t into the experience playback unit D(t), and extract a small batch of transfer sequences from it during training. 6) Use stochastic gradient descent to update the loss function L(t). 7) Update the next state s(t+1)←s(t). 8) Stop training until the parameter θ converges. According to the above method, the selection of buffering and unloading decisions can be performed among users of other base stations. Since the delay of the whole system is composed of the delays of multiple base stations, the delay of the whole system can be minimized by reducing the delay of different base stations. delay to achieve.

Images