CN109660598B - Cache replacement method and system for transient data of Internet of things - Google Patents

Abstract

The invention discloses a cache replacement method and system for the transient data of the Internet of Things. The deep reinforcement learning method is used to learn the cache strategy of the transient data, the heat trend of the data is mined from the data request history of the edge cache node, and the transient data is combined. Information, as the input of deep reinforcement learning, the immediate reward is set as the inverse of the comprehensive communication cost, using the critic network to learn the value function, the actor network to learn the strategy function, and through the continuous cache replacement operation, adaptively learn the cache strategy, Solve the problem of low efficiency of transient data caching in edge cache nodes under the condition of limited storage resources; incorporate the data freshness of IoT data and the consumption of communication resources into the comprehensive communication cost to minimize the long-term comprehensive cost of acquiring IoT data , which can offload network traffic to the edge of the network, reduce the delay, and solve the problems of large delay and large consumption of communication resources in the massive transient data transmission of the Internet of Things to a certain extent.

Description

A method and system for cache replacement of transient data in the Internet of Things

technical field

The invention belongs to the field of wireless communication, and more particularly, relates to a cache replacement method and system for transient data of the Internet of Things.

Background technique

With the rapid development and wide application of the Internet of Things (IoT) in the fields of smart transportation, smart grid, smart home, and industrial automation, massive IoT data traffic has brought enormous pressure and challenges to today's communication networks. In order to solve the above problems, a common idea is to add an edge cache mechanism to the Internet of Things, using the idle storage resources of network edge cache nodes to cache hot data, and the requester can directly obtain data from the corresponding edge cache nodes data source, thus avoiding a lot of unnecessary end-to-end communication. Edge caching in IoT systems can offload network traffic, reduce network latency, and provide better service quality and user experience. Since the storage capacity of edge cache nodes is generally limited, an efficient cache replacement strategy can improve the cache hit rate, so as to use the cache space more efficiently and offload more network traffic. A large number of applications in the IoT system also have requirements on the timeliness of data. Only data within a certain timeliness is available data. Therefore, the freshness of cached data is also an important consideration for cache replacement. Therefore, the edge cache replacement strategy in the IoT system needs to consider the heat and freshness information of the cached data at the same time, so as to better meet the cache requirements in the IoT scenario.

Traditional cache replacement methods, such as first-in first-out method, least recently used method, least frequently used, etc., have low cache efficiency because they do not consider the hot trend of content and the distribution of user requests. Existing cache replacement strategies for edge caches include: E. Bastug et al. used user-data correlation to predict the hotness of data through collaborative filtering. The cache strategy greedily caches hot data at the beginning until the edge cache node caches. Exhausted, and then perform cache replacement according to the predicted heat information; P. Blasco et al. proposed to solve the problem of data placement in small base stations through the knapsack method (Knapsack), in which the data heat is estimated according to the request rate received by the data. The multi-armed bandit (MAB) method proposed by J.Song et al. combines the data heat with the data caching process; S. Tanzil et al. proposed to estimate the data heat by constructing a neural network , using the mixed integer linear programming method to calculate the location and size of the cache, but the popularity prediction stage of this method needs to use the keyword and classification information of the video content, which is not applicable to general IoT data.

The above methods mainly focus on the edge cache of non-transitory data, and the edge cache node decides whether to cache and how to replace the cache by estimating the heat of the data. On the one hand, due to the assumption that the data heat distribution and user requests obey a specific distribution (such as Poisson distribution), it cannot adapt to the scenario of rapid changes in data heat and user request distribution; on the other hand, it only focuses on the caching of non-transient data , without considering the timeliness of transient data.

SUMMARY OF THE INVENTION

In view of the defects of the prior art, the purpose of the present invention is to solve the problems of large time delay, large consumption of communication resources and limited storage resources in the transmission of massive transient data of the Internet of Things in the prior art, and the efficiency of transient data caching in edge cache nodes under the condition of limited storage resources Not a high technical problem.

In order to achieve the above object, in the first aspect, an embodiment of the present invention provides a cache replacement method for transient data of the Internet of Things. The cache space of the current edge cache node is full, and the method includes the following steps:

S1. The edge cache node receives a new transient data item request sent by the user;

S2. Determine whether the content of the requested transient data item is in the cache of the edge cache node, if so, go to step S3, otherwise, go to step S6;

S3. Determine whether the requested transient data item is fresh data or expired data, if it is fresh data, go to step S4, if it is expired data, go to step S5;

S4. Read the data directly from the buffer area of the edge cache node, and forward the data to the user;

S5. The edge cache node forwards the user request to the data source, reads new data from the data source, replaces the expired data in the cache area of the edge cache node with the new data, and forwards the new data to the user;

S6. The edge cache node forwards the user request to the data source, reads new data from the data source, uses deep reinforcement learning to select the data to be replaced in the buffer area of the edge cache node, replaces the data to be replaced with new data, and This new data is forwarded to the user.

则请求的数据项内容不在边缘缓存节点的缓存中，其中，f_k为数据项请求k对应的数据内容唯一标识符CID，F_k为请求k到达时边缘缓存节点中缓存的数据项对应的CID集合。Specifically, in step S2, if f _k ∈ F _k , the content of the requested data item is in the cache of the edge cache node.

Then the content of the requested data item is not in the cache of the edge cache node, where f _k is the unique identifier CID of the data content corresponding to the data item request k, and F _k is the CID corresponding to the data item cached in the edge cache node when the request k arrives gather.

Specifically, in step S3, if _age (p(f _k ))≤T _life (p(f _k )), the requested data item is fresh data, and if _age (p(f _k ))>T _life (p(f _k )), then the requested data item is expired data, where f _k is the CID corresponding to the data item request k, p( ) is the mapping function from the request content CID to the data item, T _life (· ) is the effective life cycle of the data item, and _age (·) represents the age of the data item.

Specifically, the use of deep reinforcement learning in step S6 to select the data to be replaced in the buffer area of the edge cache node specifically includes:

1) At time n, observe the state information of the edge cache node, and obtain the state s n at time _n ;

2) Select the cache action _an according to the cache policy π(a _n |s _n ) and execute the cache action;

3) After the cache action an is executed, the immediate reward rn _is calculated, and the state information of the edge cache node changes from s _n to s _{n +1} ;

4) Feed back the immediate reward rn to the edge cache node, and use this state transition process <s _n , a _n , rn , s _{n + 1} > as a training sample for training deep reinforcement learning actors-comment Home network, repeat the above process.

Specifically, the calculation formula of the instant reward rn _is as follows:

Among them, Req _n represents the set of all data requests received by the edge cache node between the execution of the cache action an and the next execution of the cache action an _{+ 1} , and C(d _k ) is the comprehensive cost of obtaining the data d _k .

Specifically, the calculation formula of the comprehensive cost C(d _k ) is as follows:

C(d _k )=α·c(d _k )+(1-α)·l(d _k )

Among them, α∈[0, 1] represents the compromise coefficient, c(d _k ) represents the communication cost, l(d _k ) represents the data timeliness cost, c ₁ represents the communication cost of obtaining data directly from the edge cache node, c ₂ Represents the communication overhead of obtaining data from the data source, c ₁ <c ₂ , and both c ₁ and c ₂ are positive numbers; f _k is the CID corresponding to the data item request k, and F _k is the edge cache node when the request k arrives The CID set corresponding to the cached data item, p( ) is the mapping function from the request content CID to the data item, T _life ( ) is the effective life cycle of the data item, and _age ( ) represents the age of the data item.

Specifically, the actor network parameter θ in deep reinforcement learning is updated according to the gradient ascent as follows:

表示梯度算符，策略π(a_n|s_n；θ)表示在状态s_n下，选择缓存替换动作a_n的概率，

为优势函数，γ∈[0，1]表示折扣系数，

表示状态-价值函数；where λ is the learning rate of the actor network,

represents the gradient operator, and the policy π(a _n |s _n ; θ) represents the probability of selecting the cache replacement action _an in the state s _n ,

is the advantage function, γ∈[0,1] represents the discount coefficient,

represents the state-value function;

The network parameters θ _v of the critic network in deep reinforcement learning are updated according to gradient descent as:

where λ′ is the learning rate of the critic network.

Specifically, the actor network parameter θ in deep reinforcement learning is updated according to the gradient ascent as follows:

表示梯度算符，策略π(a_n|s_n；θ)表示在状态s_n下，选择缓存替换动作a_n的概率，

为优势函数，γ∈[0，1]表示折扣系数，

表示状态-价值函数；H(π(·|s_n；θ))是状态s_n下、策略π_θ输出的动作空间的策略熵，β表示探索系数；where λ is the learning rate of the actor network,

represents the gradient operator, and the policy π(a _n |s _n ; θ) represents the probability of selecting the cache replacement action _an in the state s _n ,

is the advantage function, γ∈[0,1] represents the discount coefficient,

represents the state-value function; H(π(·|s _n ; θ)) is the policy entropy of the action space output by the policy π _θ under the state s _n , and β represents the exploration coefficient;

The network parameters θ _v of the critic network in deep reinforcement learning are updated according to gradient descent as:

where λ′ is the learning rate of the critic network.

In a second aspect, an embodiment of the present invention provides a cache replacement system for transient data of the Internet of Things. The cache space of the current edge cache node is full. The system includes: a state judgment module, a reading module, a request forwarding module, and a cache replacement module. ;

The state judging module is used for judging the state of the transient data requested by the user, and the state includes: state 1: the content of the requested transient data item is in the cache of the edge cache node and the requested transient data item is fresh data ; State 2: The content of the requested temporary data item is in the cache of the edge cache node and the requested temporary data item is expired data; State 3: The content of the requested temporary data item is not in the cache of the edge cache node;

The reading module is configured to directly read the data from the buffer area of the edge cache node and forward the data to the user when the state determination module determines that the result is state one;

The request forwarding module is configured to forward the user request to the data source and read new data from the data source when the judgment result of the status judgment module is status 2 or 3;

The cache replacement module is configured to replace the expired data in the cache area of the edge cache node with the new data read by the request forwarding module when the state judgment module determines that the result is state two, and forward the new data To the user; when the judgment result of the state judgment module is state three, use deep reinforcement learning to select the data to be replaced in the buffer area of the edge cache node, and replace the data to be replaced with the new data read by the request forwarding module , and forward this new data to the user.

In a third aspect, an embodiment of the present invention provides a computer-readable storage medium, where a computer program is stored on the computer-readable storage medium, and when the computer program is executed by a processor, the cache replacement method described in the first aspect above is implemented.

In general, compared with the prior art, the above technical solutions conceived by the present invention have the following beneficial effects:

1. The present invention considers the effective life cycle of the transient data, and incorporates the data freshness of the IoT data and the consumption of communication resources into the comprehensive communication cost, thereby providing the goal of the IoT transient data caching strategy: minimizing the acquisition of IoT data Long-term combined cost of data. By caching transient data in the edge cache nodes of the network, network traffic can be offloaded to the network edge, reducing the delay, and to a certain extent, it solves the problems of large delay and large consumption of communication resources in the transmission of massive transient data in the Internet of Things .

2. The present invention uses the method of deep reinforcement learning to learn the caching strategy of transient data. Specifically, the cache replacement problem is modeled as a Markov process, and the heat trend information of the data is mined from the data request history of the edge cache node, combined with Transient data lifetime and data freshness information as input to the environment state for deep reinforcement learning. The short-term reward is set as the inverse of the comprehensive communication cost. Using the critic network to learn the value function and the actor network to learn the policy function, through the continuous cache replacement operation, the cache strategy is adaptively learned, and the long-term reward is maximized, thereby minimizing the long-term comprehensive cost of acquiring transient data in the Internet of Things, solving the problem of It solves the problem of low efficiency of transient data caching in edge cache nodes under the condition of limited storage resources.

Description of drawings

FIG. 1 is a flowchart of a cache replacement method for transient data of the Internet of Things according to an embodiment of the present invention.

Detailed ways

In order to make the objectives, technical solutions and advantages of the present invention clearer, the present invention will be further described in detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present invention, but not to limit the present invention.

First, some terms used in the present invention are explained.

An edge cache node refers to a network node with caching capability that is close to the user side in the Internet of Things.

The freshness of data is equal to the ratio of the remaining valid time of the data to the valid life cycle. The larger the ratio, the more timely the data is used, and the higher the freshness of the data.

Data timeliness refers to the time interval and efficiency from the generation of data by the data source to the acquisition of the data by the client. The shorter the acquisition time interval, the stronger the timeliness.

Data popularity indicates the popularity of data, that is, the number of times it is requested within a certain period of time. The higher the number, the higher the data popularity.

Transient data refers to data that requires timeliness of data.

The concept of the present invention is as follows: First, in order to study the comprehensive cost of transient data caching, the comprehensive cost of acquiring IoT data is divided into two parts: communication cost (including bandwidth consumption, delay, etc.) and data timeliness cost. The goal of cache replacement in IoT edge cache nodes is to minimize the long-term comprehensive cost of acquiring data, that is, considering both the communication cost and the data timeliness cost. Then, the cache replacement problem is modeled as a Markov process problem, and a cache strategy based on Deep Reinforcement Learning (DRL) is constructed. Learn caching strategies to minimize the long-term overall cost of acquiring IoT data.

As shown in Figure 1, a cache replacement method for transient data of the Internet of Things, the cache space of the current edge cache node is full, and the method includes the following steps:

S1. The edge cache node receives a new transient data item request sent by the user;

S2. Determine whether the content of the requested transient data item is in the cache of the edge cache node, if so, go to step S3, otherwise, go to step S6;

S3. Determine whether the requested transient data item is fresh data or expired data, if it is fresh data, go to step S4, if it is expired data, go to step S5;

S4. Read the data directly from the buffer area of the edge cache node, and forward the data to the user;

S5. The edge cache node forwards the user request to the data source, reads new data from the data source, replaces the expired data in the cache area of the edge cache node with the new data, and forwards the new data to the user;

S6. The edge cache node forwards the user request to the data source, reads new data from the data source, uses deep reinforcement learning to select the data to be replaced in the buffer area of the edge cache node, replaces the data to be replaced with new data, and This new data is forwarded to the user.

Step S1. The edge cache node receives a new transient data item request sent by the user.

The data item d in the Internet of Things is uniquely identified by CID (Content ID), and each data item contains two fields: the generation time t _gen (d) and the effective life cycle T _life (d). At time t, the age of data item d is expressed as t _age (d) = tt _gen (d). If the age of the data item d is less than its valid life cycle, that is, t _age (d) < T _life (d), then the data item d is said to be fresh data within the valid life cycle; otherwise, the data item d is said to be expired data , the expiration date has expired.

缓存的数据项对应的CID集合为

其中，I表示边缘缓存节点的最大缓存数据项容量。映射函数

将请求内容的CID信息

与缓存的数据项

联系起来。The data item request from the IoT client is denoted as k, the CID corresponding to the content of the requested data item is f _k , and the arrival time of the request is t _k . At time _tk , the set of data items cached in the IoT edge cache node is recorded as

The CID set corresponding to the cached data item is

Among them, I represents the maximum cache data item capacity of the edge cache node. mapping function

CID information of the content that will be requested

with cached data items

Get in touch.

When the data item request k arrives, the IoT edge cache node first checks whether there is a fresh cached data item with CID f _k in the cache. Three situations are considered:

Case 1: f _k ∈ F _k and t _age (p(f _k ))≤T _life (p(f _k )), that is, the content of the requested data item is in the cache, and the cache item is fresh and meets the timeliness Require. Therefore, the edge cache node directly returns the cached data item p(f _k ) to the data requester.

Case 2: f _k ∈ F _k and _age (p(f _k ))>T _life (p(f _k )), that is, the content of the requested data item is in the cache, and the cache item has expired. Therefore, the edge cache node obtains new data from the data source and returns it to the data requester, and replaces the expired data in the cache with the newly obtained data.

即请求的数据项内容不在缓存中。因此，边缘缓存节点从数据源处获取新的数据返回给数据请求者，同时使用深度增强学习选择边缘缓存节点的缓存区中待替换的数据，用新数据替换该待替换的数据。Scenario 3:

That is, the content of the requested data item is not in the cache. Therefore, the edge cache node obtains new data from the data source and returns it to the data requester, and at the same time uses deep reinforcement learning to select the data to be replaced in the buffer area of the edge cache node, and replaces the data to be replaced with new data.

Through the analysis of the above three situations, after the user sends the request k, the received returned data item d _k can be expressed as:

Among them, f _k is the CID corresponding to the data item request k, p( ) is the mapping function from the request content CID to the data item, F _k is the CID set corresponding to the data item cached in the edge cache node when the request k arrives, t _age (d) represents the age of data item d, and T _life (d) represents the effective life cycle of data item d.

Step S2. Determine whether the content of the requested transient data item is in the cache of the edge cache node, if so, go to step S3, otherwise, go to step S6.

表明请求的数据项内容不在边缘缓存节点的缓存中。f _k ∈ F _k indicates that the content of the requested data item is in the cache of the edge cache node,

Indicates that the content of the requested data item is not in the cache of the edge cache node.

Step S3. Determine whether the requested transient data item is fresh data or expired data, if it is fresh data, go to step S4, if it is expired data, go to step S5.

t _age (p(f _k ))≤T _life (p(f _k )) indicates that the requested data item is fresh data, and t _age (p(f _k ))>T _life (p(f _k )) indicates that the requested data item is fresh data The data item is expired data.

In terms of the cache replacement strategy of edge cache nodes, initially edge cache nodes greedily cache all incoming data items until the cache space is full. When the cache is full, if a new request arrives, corresponding to case 1, there is no need to perform cache replacement; for case 2, since it is known that the cached data corresponding to the current request has expired, the expired data is directly replaced with the newly obtained data That is, corresponding to case 3, when new data arrives, a cache replacement method is required to decide whether to replace the cached data item in the cache area with the new data item, and if so, which cached data item to replace.

位置对应的缓存项。当缓存区执行缓存替换动作a_k以后，D_k和F_k将变成D_k+1和F_k+1。Specifically, the caching action given by the data item d _k caching strategy is denoted as _ak , and the action space is A={a ⁰ , a ¹ , . . . , a ^I }. a _k =a ⁰ means not to perform cache replacement, a _k =a ⁱ (1≤i≤I) means to replace the cache area with the fresh data item d _k obtained from the data source

The cache entry corresponding to the location. After the cache area performs the cache replacement action a _k , D _k and F _k will become D _k+1 and F _k+1 .

Step S6. The edge cache node forwards the user request to the data source, reads new data from the data source, uses deep reinforcement learning to select the data to be replaced in the buffer area of the edge cache node, and replaces the data to be replaced with new data, and forward that new data to the user.

Step S6 corresponds to Scenario 3, using deep reinforcement learning to select the data to be replaced in the buffer area of the edge cache node, and defining the comprehensive cost C(d _k ) for obtaining the transient data item d _k .

The comprehensive cost C(d _k ) of acquiring the transient data item d _k is divided into two parts, one part is the communication cost c(d _k ), and the other part is the data timeliness cost l(d _k ).

The calculation formula of the communication cost c(d _k ) is as follows:

Among them, c ₁ represents the communication overhead of acquiring data directly from the edge cache node, c ₂ represents the communication overhead of acquiring data from the data source, c ₁ <c ₂ , and both c ₁ and c ₂ are positive numbers.

The calculation formula of data timeliness cost l(d _k ) is as follows:

The formula for calculating the comprehensive cost C(d _k ) is as follows:

C(d _k )=α·c(d _k )+(1-α)·l(d _k )

Among them, α∈[0, 1] represents the compromise coefficient, which weights the importance of the two costs. A larger α indicates that the user is more concerned about the communication loss, otherwise, the user is more concerned about the data timeliness.

In order to optimize the comprehensive cost of acquiring data in IoT, the cache replacement problem is modeled as a Markov process problem. Corresponding to the previous cache case 1 and case 2 are deterministic rules, therefore, only the cache replacement action in case 3 needs to be optimized.

The Markov process problem can be defined by {S, A, M(s _n + ₁ |s _n , a _n ), R(s _n , a _n )}, where S represents the state set of the edge cache nodes of the IoT system , sn represents the state of the edge cache node at time _n ; A represents the action set of the cache replacement strategy, a _n represents the cache action at time n; M(s _{n +1} |s _n , a _n ) represents that after the action an The state transition probability matrix of edge cache node from s _n to s _{n +1} , R(s _n , a _n ) represents the immediate reward function, the system reward feedback after performing action an in state s _n . Therefore, the entire cache replacement process can be expressed as:

1) At time n, the edge cache node observes the system state information and obtains the state s _n ∈ S of the system at time n.

2) The edge cache node selects the cache action _an according to the cache policy π(a _n |s _n ) and executes it.

3) After executing the cache action an, the system returns an instant reward _rn =R( _sn ,an), and the system state _is transferred from _sn to sn _{+ 1} .

4) The immediate reward rn _is fed back to the edge cache node, and the current state transition process <s _n , a _n , rn , s _{n +1} > is added as a training sample to the experience pool of deep reinforcement learning for training the actor- Critic network, repeat the above process.

Among them, the cache policy π(a _n |s _n ) represents the probability of selecting the cache replacement action an in the state _sn , which can _be abbreviated as π.

其中，γ∈[0，1]是折扣系数，决定了将来的奖励对现阶段缓存决策的影响程度。因此，本发明的目标是，找到最优的缓存策略π^*，最大化所有状态下的长期累积奖励期望：

其中，E[R_n|π]表示缓存策略π的长期累积奖励R_n的期望。The long-term accumulation reward of the whole process is recorded as

Among them, γ∈[0, 1] is the discount coefficient, which determines the degree of influence of future rewards on the cache decision at the current stage. Therefore, the goal of the present invention is to find the optimal caching policy π ^* that maximizes the long-term cumulative reward expectation in all states:

where E[R _n |π] represents the expectation of the long-term cumulative reward R _n of the caching policy π.

In order to measure the pros and cons of the caching strategy π, the value function V ^π (s _n )=E[R _n |s _n ; π] is defined to represent the expectation of the long-term accumulation reward R _n of the caching strategy π in the state _sn . The optimal cost function in state _sn can be expressed as V ^* ( _sn )=max _π V ^π ( _sn ).

From the Markov property, V ^π (s _n ) is brought into the Bellman equation, and we get:

Among them, p(s _{n +1} , r _n |s _n , a _n ) represents the probability of transferring to the state s _{n +1} and getting the system instant reward rn after performing the action an in the state s _n , γ∈[ 0, 1] represents the discount coefficient. This formula gives the iterative calculation method of the value function in the Markov process.

If the state transition probability matrix M(s _n+1 |s _n , a _n ) of the Markov process is given, the optimal policy can be solved by the method of dynamic programming. However, in the process of replacing the edge cache, the state transition probability matrix is unknown. Therefore, the present invention uses the deep reinforcement learning method to intelligently mine information from historical data, and uses the deep neural network to learn and fit the state-value function, so as to obtain the optimal Cache replacement strategy.

The present invention uses a deep reinforcement learning method to adaptively learn an efficient caching strategy, taking the actor-critic deep reinforcement learning method as an example, but is not limited to the actor-critic method, and introduces the method of the present invention. technical details. in:

作为深度神经网络的输入。其中，

表示当前请求数据项d_n的特征向量，

表示边缘缓存节点的缓存区中第i个数据项的特征向量。特征向量

表示过去J组请求中，每一组中对数据项内容

的请求次数，该特征向量反映了该数据项的热度。

表示数据项内容

的有效生命周期，

表示数据项内容

的新鲜度，新鲜度等于数据项内容

的剩余有效时间与有效生命周期的比值。除了这些数据请求信息，输入的信息里还可以包含场景信息、边缘网络信息等。Input: In the process of the edge cache node continuously processing user requests, situation 3 occurs, that is, when the content of the requested data item is not in the cache, the edge cache node obtains the requested data item d _n from the data source by forwarding the request . At this point, the caching policy agent (Agent) observes the current environment state

as the input to the deep neural network. in,

represents the feature vector of the current request data item d _n ,

The feature vector representing the ith data item in the buffer of the edge cache node. Feature vector

Indicates the content of the data item in each group in the past J group requests

The number of requests, the feature vector reflects the popularity of the data item.

Indicates the content of the data item

the effective life cycle of ,

Indicates the content of the data item

The freshness of the data item is equal to the freshness

The ratio of the remaining effective time to the effective life cycle. In addition to these data request information, the input information can also include scene information, edge network information, and so on.

Strategy: The present invention replaces strategy π _θ (a _n |s _n ) with actor network representation, which can also be expressed as π(a _n |s _n ; θ), which can be abbreviated as π _θ , and the actor network parameter is θ. The input of the actor network is the state information s _n of the edge cache node at time n, and the output of the actor network is the probability of selecting each cache action. Deep reinforcement learning finally selects the cache replacement action according to the policy π _θ (a _n |s _n ), that _is , executes the replacement action an for the data at the buffer location with the highest probability of selecting each cache action. For example, there are 3 buffers in the edge cache node (marks 1, 2, 3, and then use 0 to indicate no replacement). The probability of the actor network output is (0.1, 0.1, 0.7, 0.1), and then the replacement position is selected according to this probability. Here, the output is very likely to be a ² , so the No. 2 buffer is replaced. The goal of the actor network is to output the corresponding cache replacement action according to the learned cache policy, thereby maximizing the long-term cumulative reward expectation E[R _n |π _θ ].

评论家网络参数为θ_v。评论家网络的输入是n时刻边缘缓存节点的状态信息s_n，评论家网络的输出是该状态在当前策略π_θ下所表示的价值。评论家网络的目标是，尽可能准确的估计出策略π_θ下状态s_n的价值。State-value function: The present invention uses a network of critics to characterize the state-value function

The critic network parameter is θ _v . The input of the critic network is the state information s _n of the edge cache node at time n, and the output of the critic network is the value represented by the state under the current policy π _θ . The goal of the critic network is to estimate the value of state _sn under policy _πθ as accurately as possible.

Policy training: every time a cache replacement action an _is performed, the system feeds back an instant reward rn to the intelligent decision _- making module of the cache policy:

Among them, Req _n represents the set of all data requests received by the edge cache node between the execution of the cache action an and the next execution of the cache action an _{+ 1} , and C(d _k ) is the comprehensive cost of obtaining the data d _k . Since the goal is to minimize the long-term combined cost of acquiring the data, a minus sign is added to the front of the cost.

According to the Bellman equation and the state transition trajectory of the Markov process, the expectation of the long-term total reward can be estimated, so that the network parameters can be learned by means of gradient update. The gradient of the expected total reward with respect to the actor network parameter θ can be calculated as:

To maximize the expectation of the total reward, the gradient-ascent update of the actor network parameter θ is:

表示梯度算符；优势函数

衡量了在状态s_n下，选择动作a_n有多好。Among them, λ is the learning rate of the actor network, which can be adjusted according to the actual situation;

Represents the gradient operator; the advantage function

It measures how good the choice action an _is in the state _sn .

与目标值

的平方误差。评论家网络的网络参数θ_v依照梯度下降更新为：The critic network can be trained by the time difference method, and the loss function is set as the output of the critic network

with the target value

the squared error. The network parameters θ _v of the critic network are updated according to gradient descent as:

表示梯度算符。Among them, λ′ is the learning rate of the critic network, which can be adjusted according to the actual situation;

Represents the gradient operator.

In order to solve the "exploration-exploitation dilemma" in reinforcement learning, "exploitation" means to take the optimal action that has been learned so far, while "exploration" attempts to fully explore the action by taking the current non-optimal action space. In order to prevent the learning strategy from falling into the local optimum, this technical solution realizes the “exploration” by adding the entropy of the strategy (the action probability distribution output by the actor network) in the form of a regular term to the update process of the actor network parameter θ. Process encouragement:

表示梯度算符。具体计算为：Among them, H(π(·|s _n ; θ)) is the policy entropy of the action space output by the policy π _θ under the state s _n , β is the exploration coefficient,

Represents the gradient operator. The specific calculation is:

With the gradient ascent method, θ is updated in the direction of increasing entropy, encouraging the "exploration" process. The exploration coefficient β is a positive number that balances the degree of "exploration" and "exploitation". The larger the β value, the more "exploration" is encouraged, and it can be adjusted as needed in the specific implementation.

The caching strategy supports both online learning and offline learning. Online learning can be directly deployed to edge cache nodes. According to the IoT request data processed by edge cache nodes, network parameters are periodically updated to learn caching strategies. Offline learning first pre-trains the cache policy offline, and then deploys it to the edge cache node, which remains unchanged.

The invention provides a cache replacement system for the transient data of the Internet of Things, which comprises: a state judgment module, a reading module, a request forwarding module and a cache replacement module;

The state judging module is used for judging the state of the transient data requested by the user, and the state includes: state 1: the content of the requested transient data item is in the cache of the edge cache node and the requested transient data item is fresh data ; State 2: The content of the requested temporary data item is in the cache of the edge cache node and the requested temporary data item is expired data; State 3: The content of the requested temporary data item is not in the cache of the edge cache node;

The reading module is configured to directly read the data from the buffer area of the edge cache node and forward the data to the user when the state determination module determines that the result is state one;

The request forwarding module is configured to forward the user request to the data source and read new data from the data source when the judgment result of the status judgment module is status 2 or 3;

The cache replacement module is configured to replace the expired data in the cache area of the edge cache node with the new data read by the request forwarding module when the state judgment module determines that the result is state two, and forward the new data To the user; when the judgment result of the state judgment module is state three, use deep reinforcement learning to select the data to be replaced in the buffer area of the edge cache node, and replace the data to be replaced with the new data read by the request forwarding module , and forward this new data to the user.

The system also includes a training module for collecting the cache replacement action, the instant reward brought by the replacement action, and the status of the edge cache nodes before and after the replacement, and training the cache replacement based on the above parameters when the cache replacement action is performed. Network parameters for deep reinforcement learning in the module.

The above are only the preferred embodiments of the present application, but the protection scope of the present application is not limited to this. Any person skilled in the art can easily think of changes or replacements within the technical scope disclosed in the present application, All should be covered within the scope of protection of this application. Therefore, the protection scope of the present application should be subject to the protection scope of the claims.

Claims (7)

1. A cache replacement method for transient data of the Internet of things is characterized in that the cache space of a current edge cache node is full, and the method comprises the following steps:

s1, an edge cache node receives a new transient data item request sent by a user;

s2, judging whether the content of the transient data item of the request is in the cache of the edge cache node, if so, entering a step S3, otherwise, entering a step S6;

s3, judging whether the transient data item of the request is fresh data or expired data, if so, entering a step S4, and if so, entering a step S5;

s4, directly reading the data from the cache region of the edge cache node, and forwarding the data to a user;

s5, the edge cache node forwards the user request to a data source, reads new data from the data source, replaces the expired data in a cache region of the edge cache node with the new data, and forwards the new data to the user;

s6, the edge cache node forwards the user request to a data source, reads new data from the data source, selects data to be replaced in a cache region of the edge cache node by using depth-enhanced learning, replaces the data to be replaced by the new data, and forwards the new data to the user;

in step S6, the selecting data to be replaced in the cache region of the edge cache node using depth-enhanced learning specifically includes:

1) at the moment n, observing the state information of the edge cache node to obtain the state s at the moment n_n；

2) According to a cache strategy pi (a)_n|s_n) Select cache action a_nAnd executing the caching action;

3) performing a caching action a_nThen, calculate the instant prize r_nThe edge cache node state information is represented by s_nBecomes s_n+1；

4) Will award r immediately_nFeeding back to the edge cache node and converting the state<s_n,a_n,r_n,s_n+1>As a training sample, training an actor-critic network for deep reinforcement learning, and repeating the process;

the network parameter θ of the actor in the deep reinforcement learning is updated according to the gradient rise as follows:

wherein λ is the learning rate of the mobile network,

representing gradient operators, strategy pi (a)_n|s_n(ii) a θ) is shown in state s_nNext, select cache replace action a_nThe probability of (a) of (b) being,

for the merit function, γ ∈ [0, 1]]The discount factor is represented by a number of discount factors,

representing a state-cost function; network parameter theta of critic network in deep reinforcement learning_vUpdate according to gradient descent is:

wherein λ' is the learning rate of the critic network;

or, the actor network parameter θ in the deep reinforcement learning is updated according to the gradient rise as:

wherein λ is the learning rate of the mobile network,

representing gradient operators, strategy pi (a)_n|s_n(ii) a θ) is shown in state s_nNext, select cache replace action a_nThe probability of (a) of (b) being,

for the merit function, γ ∈ [0, 1]]The discount factor is represented by a number of discount factors,

representing a state-cost function; h (pi (· | s)_n(ii) a θ)) is the state s_nStrategy n_θstrategy entropy of output action space, beta represents exploration coefficient, and network parameter theta of critic network in deep reinforcement learning_vUpdate according to gradient descent is:

where λ' is the learning rate of the critic network.

2. The cache replacement method according to claim 1, wherein in step S2, if f is greater than f_k∈F_kThe requested data item content is in the cache of the edge cache node, if so

The requested data item content is not in the cache of the edge cache node, where f_kRequesting for a data item a corresponding data content unique identifier CID, F_kAnd the CID set corresponding to the data item cached in the edge cache node when the request k arrives.

3. The cache replacement method according to claim 1, wherein in step S3, if t is the case_age(p(f_k))≤T_life(p(f_k) The requested data item is fresh data if t)_age(p(f_k))＞T_life(p(f_k))，The requested data item is stale data, where f_kRequesting k the corresponding CID for the data item, p (-) a mapping function from the request content CID to the data item, T_life(. is) the effective lifecycle of the data item, t_age(. cndot.) represents the age of the data item.

4. The cache replacement method of claim 1, wherein an instant prize r_nThe calculation formula of (a) is as follows:

wherein, Req_nRepresenting a caching action a_nAfter execution, the action a is cached until the next execution_n+1All data request sets received by the edge cache nodes in between, C (d)_k) For obtaining data d_kThe comprehensive cost of (2).

5. The cache replacement method of claim 4, wherein the combined cost C (d)_k) The calculation formula of (a) is as follows:

C(d_k)＝α·c(d_k)+(1-α)·l(d_k)

wherein, α ∈ [0, 1]]Representing the compromise coefficient, c (d)_k) Denotes the communication cost, l (d)_k) Representing the data timeliness cost, c₁Representing the communication overhead of data taken directly from the edge cache node, c₂Representing the communication overhead for obtaining data from a data source, c₁＜c₂And c is and c₁、c₂Are all normal numbers; f. of_kRequesting k the corresponding CID, F for the data item_kCaching in edge cache nodes for request k arrivalP (-) is a mapping function from the request content CID to the data item, T_life(. is) the effective lifecycle of the data item, t_age(. cndot.) represents the age of the data item.

6. A cache replacement system for transient data of the Internet of things is characterized in that the cache space of a current edge cache node is full, and the system comprises: the device comprises a state judgment module, a reading module, a request forwarding module and a cache replacement module;

the state judgment module is configured to judge a state of transient data requested by a user, where the state includes: the first state: the requested transient data item content is in the cache of the edge cache node and the requested transient data item is fresh data; and a second state: the requested transient data item content is in the cache of the edge cache node and the requested transient data item is stale data; and a third state: the transient data item content of the request is not in the cache of the edge cache node;

the reading module is used for directly reading the data from the cache region of the edge cache node and forwarding the data to the user when the judgment result of the state judgment module is that the state is one;

the request forwarding module is used for forwarding the user request to the data source by the edge cache node when the judgment result of the state judgment module is the state two or three, and reading new data from the data source;

the cache replacement module is configured to replace the expired data in the cache area of the edge cache node with the new data read by the request forwarding module and forward the new data to the user when the determination result of the state determination module is state two; when the judgment result of the state judgment module is state three, selecting data to be replaced in the cache region of the edge cache node by using deep reinforcement learning, replacing the data to be replaced by the new data read by the request forwarding module, and forwarding the new data to the user;

the selecting of the data to be replaced in the cache region of the edge cache node by using the deep reinforcement learning specifically includes:

1) at the moment n, observing the state information of the edge cache node to obtain the state s at the moment n_n；

2) According to a cache strategy pi (a)_n|s_n) Select cache action a_nAnd executing the caching action;

3) performing a caching action a_nThen, calculate the instant prize r_nThe edge cache node state information is represented by s_nBecomes s_n+1；

4) Will award r immediately_nFeeding back to the edge cache node and converting the state<s_n,a_n,r_n,s_n+1>As a training sample, training an actor-critic network for deep reinforcement learning, and repeating the process;

the network parameter θ of the actor in the deep reinforcement learning is updated according to the gradient rise as follows:

wherein λ is the learning rate of the mobile network,

representing gradient operators, strategy pi (a)_n|s_n(ii) a θ) is shown in state s_nNext, select cache replace action a_nThe probability of (a) of (b) being,

for the merit function, γ ∈ [0, 1]]The discount factor is represented by a number of discount factors,

representing a state-cost function; network parameter theta of critic network in deep reinforcement learning_vUpdate according to gradient descent is:

wherein λ' is the learning rate of the critic network;

or, the actor network parameter θ in the deep reinforcement learning is updated according to the gradient rise as:

wherein λ is the learning rate of the mobile network,

representing gradient operators, strategy pi (a)_n|s_n(ii) a θ) is shown in state s_nNext, select cache replace action a_nThe probability of (a) of (b) being,

for the merit function, γ ∈ [0, 1]]The discount factor is represented by a number of discount factors,

representing a state-cost function; h (pi (· | s)_n(ii) a θ)) is the state s_nStrategy n_θstrategy entropy of output action space, beta represents exploration coefficient, and network parameter theta of critic network in deep reinforcement learning_vUpdate according to gradient descent is:

where λ' is the learning rate of the critic network.

7. A computer-readable storage medium, having stored thereon a computer program which, when executed by a processor, implements the cache replacement method of any one of claims 1 to 5.

Images