Distributed Edge Caching via Reinforcement Learning in Fog Radio Access Networks
Liuyang Lu Yanxiang Jiang Mehdi Bennis Zhiguo Ding Fu-Chun Zheng Xiaohu You




























 Distributed Edge Caching via Reinforcement 
 Learning in Fog Radio Access Networks
    Liuyang Lu,
Yanxiang Jiang, Senior Member, IEEE,
Mehdi Bennis, Senior Member, IEEE, 
Zhiguo Ding, Senior Member, IEEE, 
Fu-Chun Zheng, Senior Member, IEEE,
and Xiaohu You, Fellow, IEEE
This work has been accepted by IEEE VTC 2019 Spring.
L. Lu and Y. Jiang are with the National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China,
the State Key Laboratory of Integrated Services Networks, Xidian University, Xi'an 710071, China,
and the Key Laboratory of Wireless Sensor Network & Communication, Shanghai Institute of Microsystem and Information Technology,
Chinese Academy of Sciences, Shanghai 200050, China. (e-mail: yxjiang@seu.edu.cn)
M. Bennis is with the Centre for Wireless Communications, University of Oulu, Oulu 90014, Finland. (e-mail: bennis@ee.oulu.fi)
Z. Ding is with the School of Electrical and Electronic Engineering, University of Manchester, Manchester, UK. (e-mail: zhiguo.ding@manchester.ac.uk)
F. Zheng is with the School of Electronic and Information Engineering, Harbin Institute of Technology, Shenzhen 518055, China, and the National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China. (e-mail: fzheng@ieee.org)
X. You is with the National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China. (e-mail: xhyu@seu.edu.cn)

    Received: 28 September 2018 / Accepted: 5 February 2019
=============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================


In this paper, the distributed edge caching problem in fog radio access networks (F-RANs) is investigated. By considering the unknown spatio-temporal content popularity  and user preference, a user request model based on hidden Markov process is proposed to characterize the fluctuant spatio-temporal traffic demands in F-RANs. Then, the Q-learning method based on the reinforcement learning (RL) framework is put forth to seek the optimal caching policy in a distributed manner, which enables  fog access points (F-APs) to learn and track the potential dynamic process without extra communications cost. Furthermore, we propose a more efficient Q-learning method with value function approximation (Q-VFA-learning) to reduce  complexity and accelerate convergence.
Simulation results show that the performance of our proposed method is superior to those of the traditional methods.


Fog radio access networks, distributed edge caching, Q-learning,  content popularity, user preference.





§ INTRODUCTION



The rapid development of smart devices and mobile applications brings an unprecedented traffic pressure to the wireless networks <cit.>.
To cope with this challenge and meet the stringent quality of service (QoS) standards, significant changes to the cellular infrastructure are required<cit.>.
One promising such change is through the dense deployment of caching resources at   network edges<cit.>.
At this point, fog radio access network (F-RAN) <cit.> has been proposed as an evolution form of heterogeneous cloud radio access networks.
By taking full advantage of computing and storage capabilities in edge devices, F-RANs can effectively reduce the backhaul load by prefetching and caching the most popular contents.
In F-RAN, edge devices with limited resources are fog access points (F-APs).
Due to the resource constraints, distributed caching has been considered as a practical mechanism in F-RANs, which does not require information exchange between neighboring F-APs, thus can reduce the network overhead effectively.
To strategically prefetch contents in a distributed manner, each F-AP must learn how, what and when to cache, while taking into account storage limitations, cache refreshing costs and fluctuant spatio-temporal traffic demands.

There are many traditional distributed caching methods including belief propagation-based algorithm <cit.>, alternation direction method of multipliers algorithm <cit.>, and game theory based algorithm <cit.>.
However, those existing works <cit.> presume that the popularity profile is known in advance and keeps stationary over long time span, which is not practical.
Hence, an increasing number of works in distributed caching have focused on entailing the edge ability of learning content popularity.
In <cit.>, a perturbed version of content popularity was learned in an online fashion to simplify the decentralized cache problem to a multi-armed bandit problem.
The cache content placement problem in single base station was cast into a reinforcement learning (RL) framework and an online method to learn the spatial and temporal content popularity profile was presented in <cit.>.
This method considers the influence of the global popularity towards the requests of a local region, which inevitablely introduces additional information exchanging cost.
To reduce this kind of network overhead, a distributed caching policy based on a game of independent learning automata was proposed in <cit.> to minimize the downloading latency by observing the instantaneous exchanged information between learners and environment.
This policy can  achieve a fully distributed caching procedure which ignores the priori knowledge of regional content popularity, whereas it leads to a slow learning speed.
However, the content popularity considered in <cit.> is not prudent enough to reflect the demand statistic of users at a certain time and region.
Specifically, when there are few users with high mobility in the region, the probability of a particular content being requested is much more likely to depend on the long-term user characteristics <cit.>, while content popularity is more inclined to capture regional features.

Motivated by the aforementioned discussions and considerations, a distributed edge caching method is proposed in this paper to optimize the edge caching policy in F-RANs.
First, we propose a user request model to describe the fluctuant spatio-temporal traffic demands in F-RANs by considering the joint influence of content popularity and user preference.
Then, we cast the edge caching problem of each F-AP into the RL framework by defining a learning environment and designing a suitable reward function.
Furthermore, the Q-learning method is put forth to seek the optimal edge caching policy in a distributed manner, where each F-AP acts independently without extra information exchange.
Finally, we propose a more efficient Q-learning method with value function approximation (Q-VFA-learning) to reduce complexity and accelerate convergence.


The rest of this paper is organized as follows.
In Section II, the system model is elaborately described. The problem formulation and the proposed RL-based distributed edge caching method are presented in Section III.
Simulation results are provided in Section IV, and the main conclusions are drawn in Section V.












§ SYSTEM MODEL




 §.§ Network Model

The considered F-RAN is illustrated in Fig. <ref>, where a large amount of F-APs are deployed.
At the network edge, the F-APs with limited resources are connected to the cloud content center  via the backhaul link.
Let ℱ={1, 2, …, f, …, F} denote the content library, which is located in the cloud content center.
For simplicity, it is assumed that all  contents have the exactly same size and each F-AP can store up to B (B≤ F) contents.
Meanwhile, a time-slotted system  is considered.
Let g_t denote  the user group that consists of  the users served by the F-AP during time slot t.
Assume that there are N users in the user group g_t and let 𝒩={1,2,…,n,…,N} denote the set of the N users.








 §.§ User Request Model


The probability that a certain user requests some certain content is determined by  the spatio-temporal content popularity as well as the  user preference.
The content popularity and the user preference are modeled by using  two independent and identically distributed Markov chains as  shown in Fig. <ref>, where the corresponding information is collected at the beginning of each time slot.
This kind of setting characterizes an environment with   fluctuant spatio-temporal traffic demands.
In the setting, the user group g_t  consists of the dynamically arriving and leaving users, while a certain user's preference  is  fixed.
Meanwhile, the content popularity is variant over time and space.
Let P ={P_1,P_2,…,P_|P|} and Q ={Q_1,Q_2,…,Q_|Q|}
denote the implied state  sets of the content popularity and the user preference.
Specifically, the dimensions of the implied states in the Markov chains are assumed known in advance, while the underlying transition probabilities are considered unknown.



  §.§.§ Content popularity


Let d_f(t) denote the amount of  the instantaneous user requests towards the fth content during time slot t.
Correspondingly, Let p_f(t) denote the regional content popularity of the fth content,
which can be expressed as follows,

    p_f(t)=d_f(t)/∑_f ∈ Fd_f(t).




  §.§.§ User preference


During time slot t, let x_n(t)∈ℝ^M denote the user characteristic vector <cit.> with dimension M describing the preferences of the nth user.
Meanwhile, let y_f(t)∈ℝ^M denote the content feature vector <cit.> with dimension M describing the features of the fth content.
Take video as an example: the user characteristics and content features  can be described in the aspects such as time validity, video type, video resolution.
Without loss of generality, we normalize the various dimensions of x_n(t)∈ [0,1]^M and y_f(t)∈ [0,1]^M.
Then, we  introduce a parameter α  to the  kernel function in <cit.> to  dynamically reflect the correlation between the nth user and  the fth content.
Let g[x_n(t),y_f(t)] denote the kernel function.
Then it  can be expressed as follows,

    g[x_n(t),y_f(t)]=(1-<x_n(t),y_f(t)>)^log (1-α ),

where <,> denotes the   inner product operator.
Note that 0≤α <1.
When α→1^-, we have,

    g[x_n(t),y_f(t)]→{[   0,x_n(t)y_f(t); 1,x_n(t)=y_f(t),;                  ].

which indicates that no user has the same preference.
When α=0, we have g[x_n(t),y_f(t)]=1 for any n and f,
which indicates that the user preferences are the same for every content.
According to (<ref>), we can deduce that g[x_n(t),y_f(t)] takes values in [0,1], and a lower value indicates a higher probability of the corresponding request.
Let q_f(t) denote the user preference of the user group g_t during time slot t for the fth content, which can be expressed as follows,

    q_f(t)=1/N∑_n∈Ng[x_n(t),y_f(t)].




 §.§ Edge Caching Model

The considered  time-slotted system is depicted in Fig. <ref> where a batch of requests arrives at the beginning of each time slot t = 1,2,…,T, where T is considered to be a finite time horizon.
Let a_f(t) denote the cache indicator for the considered F-AP during time slot t.
Specifically, a_f(t)=1 indicates that the fth content is cached during time slot t and a_f(t)=0 otherwise.
Correspondingly, caching decisions are made in the control unit of the considered F-AP.
At the end of  each time slot t, the control unit  changes the current caching indicator a_f(t) to the upcoming  a_f(t+1).




§ THE RL-BASED DISTRIBUTED EDGE CACHING METHOD

In this section, we first formulate the distributed edge caching optimization problem in F-RANs by casting the problem into the RL framework.
Then, the   Q-VFA-learning method is proposed to seek the optimal edge caching policy.

 

 §.§ Problem Formulation   in the RL Framework

Distributed edge caching effectively reduces the   communication overhead since  F-APs are supposed to act independently without extra information exchange.
In the RL framework, the RL agent only uses the evaluative feedback from the environment as a performance measure.
Hence RL is a proper tool to realize the sequential decision problem of the distributed edge caching.
During time slot t, the RL agent receives a state s(t) in the state space S and selects an action a(t) from the action space A with probability P(s'|s,a)=ℙ[s(t+1)=s'|s(t)=s,a(t)=a], where ∑_s' ∈SP(s'|s,a)=1.
The agent's behavior here is a policy π(a|s), which is also considered as a mapping from state s to action a.
The instantaneous reward of taking action a(t) in state s(t) is r(t).
The object of the agent is to find a policy, that minimizes the long-term reward value from each state<cit.>.

To eventually formulate the problem in the RL framework,   the four fundamental elements in the caching optimization problem are to be introduced.
Specifically, the F-AP is the learning agent in this problem.

State Space:
 ∀ f ∈ F, let the user preference q_f(t),  content popularity p_f(t) and the last cached decision a_f(t-1) form the state space of the agent F-AP during time slot t.
For simplification, let  p =[ p_1(t),…,p_f(t),…,p_F(t) ]^T and q =[ q_1(t),…,q_f,…,q_F(t) ]^T denote the current content popularity vector and the current user preference vector.
Let S ={s_1,s_2,…,s_|S|}  denote the state space, where |S| represents the dimension  of the state space.

Action Space:
In order to meet the storage constraint of the F-AP, every possible action in the action set A should satisfy the following condition,

    ∑_f ∈ F a_f(t)=B, a_f(t)∈{0,1}.

Note that the dimension of the action set A is |A|.
Let a(t) = [ a_1(t),…,a_f(t),…,a_F(t) ]^T denote the current action, likewise the upcoming action a(t+1).

Reward:
Cache hit rate is a common measure of the caching performance,  hence it is adopted as  the reward function in the RL framework for this optimization problem.
Let θ(t)   denote the cache hit rate during time slot t,
which can be expressed as follows,

    θ(t)=∑_f ∈ F d_f(t)a_f(t)/∑_f ∈ F d_f(t).

Let r(t) denote the instantaneous reward during time slot t, which can be expressed as follows,

    r(t)=1-θ(t).

The agent can achieve a good performance of the long-term cache hit rate when the average   reward is minimized.

Action Value Function:
Let Q_π(s,a) denote the value function following the policy π.
Then, it can be expressed as follows,

    Q_π(s,a)=𝐸[∑_τ=t ^∞γ^τ -tr(s(τ),a(τ))]_s(τ)=s,a(τ)=a,

where γ∈(0,1] denotes the discount factor.
The discount factor γ reflects to what degree the future reward is affected by the past actions.
Action value function is a prediction of the expected accumulative reward over infinite time horizon, which measures the optimality of  each state-action pair.
In other words, action value function helps to determine which and when the content should be cached.
Due to the Markov property, i.e., the state at the subsequent time slot is only determined by the current state and irrelevant to the former states, the action value function can be decomposed into the Bellman equation
Q_π(s,a)=∑_s'p(s'|s,a)[r+γ∑_a'π(a'|s')Q_π(s',a')].
The optimal action value function  Q^*(s,a)=min_π Q_π(s,a) can be decomposed into the Bellman optimality equation Q^*(s,a)=∑_s'p(s'|s,a)[r+γmin_a' Q^*(s',a') ].
Exploiting the Bellman equation and the Bellman optimality equation, we can use RL to solve the dynamic programming problem<cit.>.
First, the agent  evaluates   Q_π(s,a) for the current policy π.
Then, the policy is updated as follows,

    π'=min_aQ_π(s,a).


The objective of this paper is to determine the optimal policy π^* such that the average reward of any state s can be minimized.
More specifically, the RL-based optimization problem is formulated as follows,


    min_π^*  𝐸[Q_π^*(s,a)], ∀s∈S.




 §.§ Optimal Edge Caching via Q-learning Method and Q-VFA-learning Method



  §.§.§  Q-learning Method

Q-learning is an off-policy control method and an online algorithm in the  RL framework, which is one of the most widely-used strategies to determine the best policy π^*.
By considering the unknown  information of P(s'|s,a), ∀s,a, the Q-learning method is a typical  adaptive dynamic programming method <cit.> that learns and tracks the potential dynamic environment, without the need to estimate   P(s'|s,a), ∀s,a.
The  update rule can be expressed as follows,

    Q(s,a) Q(s,a)+δ_t[r+γmin_a' Q(s',a') -Q(s,a)],

where δ_t is the learning rate.
When the agent observes the environment during the initial iterations,  δ_t should be set relatively large for the agility of the learning process.
While enough observations have been accumulated, δ_t should be set to a small value to maintain the precision and reliability of the learning process.
Hence, we set the learning rate δ_t=1/√(t+2) as  a function of time.
Meanwhile, a probabilistic exploration-exploitation approach is utilized to determine the future actions, which guarantees the convergence of the Q-learning method.


  §.§.§  Q-VFA-learning Method

The original Q-learning method saves the action value function Q_π(s,a) in tabular form.
Despite the simple and comprehensive features,  the applicability of Q-learning in tabular form  faces practical challenges in real networks, since the actual state or action space is large or continuous.
Value function approximation  <cit.> can cope with the case that the state space is unsuited for explicit representation.
With a proper function approximation model, the agent can estimate the state value in the partitioned space that has been visited,   induce the value in cross-region <cit.>, and then directly estimate the value in the corresponding space without requiring every continuous state.
Linear value function approximation <cit.> is a way to generalize the  Q-learning method  in real setting, which is named as Q-VFA-learning method in the following.

We propose a value function approximation model, which considers  the induced backhaul load,  the mismatch cost between the caching decision and the content popularity as well as the consideration of satisfying the user preference.

Let z_1(s,a) denote the induced backhaul load  when the agent refreshes  the former caching decision to a new one.
Then, it can be formulated as follows,

    z_1(s,a)=a^T(1-a̅),

where a̅ is the original caching state during the current time slot.
The corresponding content in this case is cached during the previous time slot  while replaced by a new content.
According to the network model, the new content is sent to the F-AP over the backhaul link from the cloud content center.
Therefore, this type of cost represents the induced backhaul load.

Let z_2(s,a) denote the mismatch cost between the caching decision  and  the local content popularity during time slot t.
Then, it can be formulated as follows,

    z_2(s,a)=(1-a)∘p,

where  ∘ denotes the Hadamard product.
This cost is incurred when the content with high popularity is uncached, which    should be avoided.
Actually, it is reasonable to consider that the local content popularity indicates  the future requests in the region.
The external factors, such as the type of the device  and the location of F-APs, would  have an impact on users' demands, which are captured as the local content popularity.
For instance, in subway or commercial district, users prefer to requesting  short-form videos for entertainment due to the  traffic and battery limits.
While in living quarters, they have more kinds of alternative choices.

Let z_3(s,a) denote the degree of satisfying user preference  during time slot t, which can be formulated as follows,

    z_3(s,a)=(1-a)∘q.

The   corresponding content in this case is not cached but the user preference collected at the moment is relatively higher than those cached.
Minimizing this cost  is beneficial to improve the prudence of the caching strategy  by considering user preference.
Specifically, when there are few users with high mobility in the region, the probability of a particular content being requested is much more likely to depend on the long-term user characteristic, while the content popularity is more inclined to capture regional features.

Given the three costs discussed above,  the cost vector with dimension (2F+1)  can be denoted as z(s,a), which can be expressed as follows,

    z(s,a)=[z_1(s,a), z_2(s,a)^T ,z_3(s,a)^T]^T.

The cost vector  considers  the joint influence of the backhaul   resource, the content popularity and the user preference.
Instead of simple superposition of the different induced costs
described in <cit.>, here we consider more
specific influence of every content.
We propose to train the weight vector
w to reflect the relative importance of every content by
defining the approximate value function Q̂(s,a;w).
Then, it can be expressed as follows,

    Q̂(s,a;w)=z(s,a)^Tw.

According to  the approximate value function Q̂(s,a;w), we can determine the next action  which can minimize the costs.
In order to guarantee convergence,  a probabilistic exploration-exploitation approach is utilized to determine the future actions.


Given    the approximate value function Q̂(s,a;w) introduced above, here we present how to update the weight vector w.
First, let  ε̂ (s,a) denote the instantaneous error during the time slot t, which can be expressed as follows,

    ε̂ (s,a)=[r(s,a)+γa'min Q(s',a';w)-Q(s,a;w)]^2.

Then, the weight vector w can be updated by using stochastic gradient descent method   <cit.> as follows,

    ww+ρ√(ε̂ (s,a))z(s,a),

where  ρ is the step size.
The pseudo code for Q-VFA-learning method is presented in Algorithm 1, where parameter ϵ _t trades off exploration for exploitation during time slot t.


  §.§.§ Complexity Analysis

The complexity of the policy evaluation step of Q-learning method  is O(|S||A|), because the Q values <cit.> are updated for per state-action pair.
Furthermore, given Q(s,a), ∀s,a, the complexity of the policy update step is O(|A|).
Thus, the  complexity of Q-learning per iteration is O(|S||A|).
In Q-VFA-learning, the complexity of the policy evaluation is O(|A| |F|), and the complexity of the  weight vector update is O(|F|).
Notice that |A|=C_F^B, which means that |A|≫ F.
Therefore,  to a certain extent, the Q-VFA-learning method  could resolve the  curse of dimension  problem in traditional Q-learning method.






§ SIMULATION RESULTS

In this section, the performance of the proposed  RL-based edge caching method is evaluated.
We consider the  F-RAN with F=20   and the F-AP with storage capacity  B=5.
The user preference  is modeled by a five-state Markov chain with  different parameters α drawn from the kernel function.
The content popularity  is modeled by a four-state Markov chain drawn from Zipf distributions with different  distribution parameters β.
We choose the Least Recently Used (LRU) method, the Least Frequently Used (LFU)  method, and the  Q-learning method as the benchmark edge caching methods.

Fig. <ref> shows the cache hit rate of our proposed method in comparison with the three benchmark  methods, and the instantaneous cache hit rate  is averaged  for every 100 time slots to avoid contingency.
It can be observed that the performance of the Q-learning method and Q-VFA-learning method are superior to   those of the other methods, and the Q-VFA-learning method achieves the largest cache hit rate.
Moreover, the cache hit rates of the Q-learning method and the Q-VFA-learning method constantly increase until both reach the maximum, while the LRU and  LFU methods show fluctuations
at the beginning  as a result of the inevitable cold-start problem.




In Fig. <ref>, we show the convergence performance of the Q-learning method and the Q-VFA-learning method in term of
the mean discrepancy, where the mean variance of  Q values   is updated in every 100 iterations in order to avoid contingency.
We have set the discount factor γ=0.9 and the step size ρ=0.005 for a relatively fast convergence.
It can be observed that the Q-VFA-learning method converges faster than  the Q-learning method.
The reason is that the Q values in tabular form  must be updated per state-action pair, while Q-VFA-learning method reduces dimension of the problem as updating the learning parameters of  model characteristic per iteration.



In Fig. <ref>, we compare the cache hit rate of the Q-VFA-learning method with different dimensions of the content popularity Markov chain and the user preference Markov chain.
It can be observed that  the  Q-VFA-learning method has better performance with  the increase of  |P| and |Q|.
This reveals that the   our  proposed method can adapt to the complex environment, which contains the fluctuating content popularity and the dynamically arriving and leaving users.


Fig. <ref> shows the cache hit rate  of the Q-VFA-learning method under different library size and storage capacity of the F-AP.
It can be observed that with the increase of |A|, the convergence becomes slower while the performance gets better.
This is due to the fact that the iteration process of the Q-VFA-learning method makes the edge caching policy  sensitive to the dimension of the action set A.
With more explorations, the  F-AP can track and learn a large  content library more intelligently.



§ CONCLUSIONS 


In this paper, we have proposed a RL-based distributed edge caching method  by learning and tracking the potential dynamic process of user requests.
The user request model based on hidden Markov process, which utilizes the joint influence of the local content popularity and the user preference, has been proposed to describe the fluctuant spatio-temporal traffic demands in F-RANs.
The Q-VFA-learning method has been proposed to seek the optimal edge caching policy and accelerate convergence in an online fashion.
Simulation results have shown that our proposed method   can achieve a better caching performance   compared to the  traditional methods.




§ ACKNOWLEDGMENTS


This work was supported in part by
the Natural Science Foundation of China under Grant 61521061,
the Natural Science Foundation of Jiangsu Province under grant
BK20181264,
the Research Fund of the State Key Laboratory of
Integrated Services Networks (Xidian University) under grant ISN19-10,
the Research Fund of the Key Laboratory of Wireless Sensor Network & Communication (Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences) under grant 2017002,
the National Basic Research Program of China
(973 Program) under grant 2012CB316004,
and the U.K. Engineering and Physical Sciences Research Council under Grant EP/K040685/2.



IEEEtran      


