# Edge Caching for D2D Enabled Hierarchical Wireless Networks with Deep Reinforcement Learning

Authors: Wenkai Li; Chenyang Wang; Ding Li; Bin Hu; Xiaofei Wang; Jianji Ren
Journal: Wireless Communications and Mobile Computing
 (2019)

---

## Abstract

Edge caching is a promising method to deal with the traffic explosion problem towards future network. In order to satisfy the demands of user requests, the contents can be proactively cached locally at the proximity to users (e.g., base stations or user device). Recently, some learning-based edge caching optimizations are discussed. However, most of the previous studies explore the influence of dynamic and constant expanding action and caching space, leading to unpracticality and low efficiency. In this paper, we study the edge caching optimization problem by utilizing the Double Deep Q-network (Double DQN) learning framework to maximize the hit rate of user requests. Firstly, we obtain the Device-to-Device (D2D) sharing model by considering both online and offline factors and then we formulate the optimization problem, which is proved as NP-hard. Then the edge caching replacement problem is derived by Markov decision process (MDP). Finally, an edge caching strategy based on Double DQN is proposed. The experimental results based on large-scale actual traces show the effectiveness of the proposed framework.


---

## Body

## 1. Introduction

With the development of network services and the sharp increasing of mobile devices, severe traffic pressure posed an urgent demand of network operator to explore the effective paradigm towards 5G. Related works show that the requests of top 10% video account for 80% of all traffic, that is, the repeated downloads of the same content [1]. Device-to-Device (D2D) content sharing is an effective method to reduce mobile network traffic. In this way, users can download required content from nearby devices and enjoy data services with low access latency [2], which can improve their service qualities (QoS).In order to design an efficient caching strategy in mobile networks, we need to achieve the statistical information of the user requests and sharing activities by system learning from the extreme volume of mobile traffic. In previous work, some important factors in mobile networks (such as content popularity, mobile models, user preferences, and user behaviour) are assumed to be well known, which is not rigorous [3]. Recently, a learning-based method is proposed to jointly optimize the mobile content sharing and caching [4, 5]. The authors of [6] calculated the minimum unload loss according to user’s request interval and explored content caching of small base station (SBSs). Srinivasan et al. [7] used the Q-learning method to determine the load-based spectrum, optimizing the spectral sharing. However, traditional RL technology is not feasible for the mobile network environment with large state space.Motivated by this, we studied the D2D edge caching strategy in hierarchical wireless network in order to maximize unloading traffic and reduce pressure through D2D communication. And the cache replacement process is modelled by Markov decision process (MDP). Finally, a Double Deep Q-network (Double DQN) based edge caching strategy is proposed. The contributions of this paper are summarized as follows:(i)
We model the D2D sharing activities by considering both online factor (users’ social behaviours) and offline factor (user mobility). The optimization then is proved as NP-hard.(ii)
The cache replacement problem is established by Markov decision process (MDP) to address the continuousness of edge caching problem. And we propose a Double DQN-based edge caching strategy to deal with the challenge of action/state spaces explosion.(iii)
Combined with the theoretical model, real trace evaluation, and simulation experimental platform, the proposed Double DQN-based edge caching strategy achieves better performance than some existing caching algorithms, including the least recently used (LRU), least frequently used (LFU), and first-in first-out (FIFO).The rest of this article is organized as follows. We explained the relevant work in the second part. The third part introduces the system model. The fourth part introduces the cache optimization strategy and raises the relevant problem. The fifth part introduces the details of cache strategy optimization. And in the sixth part, large-scale experiments based on real tracking are carried out.


## 2. Related Work

There are many researches on edge caching in mobile network. For example, it is studied and proposed in [8–10] that adding caching to mobile network is very promising. Femto caching proposed in [11, 12] and AMVS-NDN proposed by [13] are both committed to adding the cache in BS for the purpose of unloading the traffic. The authors of [14–16] proposed a collaborative caching strategy between BS, which greatly improves the QoS of users. In recent years, the application of intelligence in wireless networks is getting more and more attention. Research in [17, 18] shows that enhanced learning (RL) has great potential in the design of BSs content caching schemes. Particularly, the author proposed the base station caching replacement strategy based on Q-learning and used multiarmed bandit (MAB) to place the cache through RL technology [17]. However, considering the extreme complexity of the actual network environment and the maximum of the state space, traditional RL technology is not feasible. Besides, all of the works mentioned above are focused on single-level caching without considering multilevel caching.Multitier caching is widely used to exploit the potential of system infrastructure, especially in web caching systems [19–21] and IPTV systems [22]. Reference [23] focused on the theoretical performance analysis of the content cache in HetNets, which assumes that the content is in the same size. However, [22, 23] do not involve the design of caching policies, which required practical considerations in terms of constraints (for instance, limited front-end/backhaul capacity, diversity of content sizes) and specific characteristics of network topologies.


## 3. System Model

As shown in Figure1, we consider hierarchical network architecture. The core network communicates with N base stations via the backhaul link and the base station communicates with the user via the cellular link.N mobile users are uniformly distributed U={u1,u2,…,uN} with a local buffer size Lu={l1u,l2u,…,lNu}, users can establish direct communications with each other via D2D links, and they can also be served by the BSs via cellular links.M files are stored in the content library F={f1,f2,…,fM}, and their content sizes are denoted as Lf={l1f,l2f,…,lMf}. lf represents the size of the requested content f. The cache state is described by sufc. Here, sufc is binary, where sufc= 1 denotes that the useru caches the contentfwhile sufc= 0 means no caching.Figure 1
Illustration of edge caching architecture in D2D networks.


### 3.1. Content Popularity and User Preference

The popularity of content is often described as the probability of a content from the libraryF which is requested by all the users. Denote an N×M popularity matrix P, where quf=P(qnm) is the probability of user un requests for content fm in the (n,m)th component. In related studies, the content popularity is always described by ZipF distribution as [24].(1)quf=Ruf-β∑i∈FRi-βwhere the Ruf-β is popularity index that user u gives to content f in a descending order and β≥0 is the ZipF exponent.We measured users’ sharing activities by large-scale tracing of D2D sharing based onXender. As shown in Figure 3 [25], in the real world, the matrix P changes over time (we will introduce the tracking in detail in the sixth part). We assume that the matrix remains constant over time, and our caching strategy refreshes with changes of the popularity matrix P. And the period of user sharing activities can be divided into Peak hours and Peak-off hours. The cache replacement action occurs during the Peak-off hours at each period.User preference: the user preference, which is denoted as Puf, is the probability distribution of a user’s request for each content. According to the content popularity matrix P, each row of the matrix denotes a popularity vector of a user which reflects the preference of a user for a certain content in a statistical way. Assuming that the content popularity and user preference are stochastic, we can obtain the relation:(2)Puf=∑u=1Nwuqufwhere wu is the probability of user u∈U sending a request for various contents f∈F, given to a user request distribution W=[w1,w2,…,wN], ∑u=1Nwu=1, wu∈[0,1], which reflects the request active level of each user.


### 3.2. D2D Sharing Model

Under the D2D-aid cellular networks, users can select either D2D links model or cellular links model. In the D2D links model, users can request and receive the content from the others via D2D links (e.g., Wi-Fi or Bluetooth) or request the content from the BSs directly in a cellular links manner. In our model, the users select D2D links model in advance. If the requested content is not in their own buffers (or their neighbours’), the cellular links model is chosen.To model the D2D sharing activities among mobile users, the opportunistic encounter (e.g., user mobility, meeting probability, and geographical distance) and social relationship (e.g., online relations and user preference) are two important factors to be concerned about.(1) Opportunistic Encounter. It is necessary to ensure that the distance between the two users is less than the critical value dc,when the user communicates via the D2D link. Since the devices are carried by humans or vehicles, we use the meeting probability to describe the user mobility.Similar with the prior work [26], we regard λuv as the contact rate of user u and v, which follows the Poisson distribution and the contact event is independent of the user preference. We can obtain the opportunistic delivery as the Poisson process with rate Pufλuv. If user u caches content f in its buffer, we can derive the probability puv that user v receives content f from user u before the content expires at time Tf. For a node pair, we can derive that(3)puv=∫Tf∞Pufλuve-Pufλuvydy=1-e-PufλuvTfHowever, if the content f is not cached in user u, puv=0. Combined with the definition of sufc, we can overwrite (3), as puv=1-e-PufλufTfsufc. Hence, the probability that user v cannot receive content f from all the other user u∈U is ∏u∈U(1-puv). Then the probability of user v receiving content f from user u can be expressed by(4)Puv=1-∏u∈U1-puv=1-e-PufTf∑u∈Uλufsufc(2) Social Relationship. In social relationship among users, mobile users with weak social relationship may not be willing to share the content with the others owing to the security/privacy concerns. On the other hand, users sometimes have additional resource and are willing to share the content with others. However, the sharing activities may fail because of the hardware/bandwidth restriction (the content may be too large or the traffic speed is too slow). Thus, we consider the social relationship mainly depends on user preference and content transmission rate condition.We employ the notion of Cosine Similarity to measure the user preference between two users and the preference similarity factorCuv is defined as(5)Cuv=∑f∈Fqufqvf∑f∈Fquf2∑f∈Fqvf2,∀u,v∈UFinally, based on the opportunistic encounter and social relationship, we can obtain the probability of D2D sharing between user u and v as follows:(6)PuvD2D=Cuv·Puv,,∀u,v∈U,,∀f∈Fwhere ∑v∈UPuvD2D≤1,∀u∈U. The sum of probability of D2D sharing between each user and other users is less than 1.


### 3.3. Association of Users and BSs

Users can ask the content directly from the associated local BS when the requested content cannot be satisfied by D2D sharing. DefinitionPuBS is the cellular serving ratio, which is the average probability that the requests of user u have to be served by local BS via backhaul link rather than D2D communications. Thus, we can obtain PuBS=1-∑v∈UPuvD2D,∀u∈U. In this paper, we consider that the content transmission process can be finished within the user mobility tolerant time, e.g., before the user moves out of the communication range of the local BS. The requested content can be satisfied from the buffer of local BS or obtained from the neighbour BSs via BS-BS link as well as the Internet via backhaul link. Let PuBBS denote the probability of BS n serving user u, then we have(7)PuBBS=∑iTunBSi∑n∈N∑iTunBSiwhere TunBS(i) denote the time period of the i-th cellular serving from BS n to user u during the total sample time Ttot. Therefore, we have the probability PuvBS that user u is served by BS n as follows:(8)PuBnBS=PuBS·PuBBS,∀u∈U,∀n∈NNote that ∑n∈NPunBS+∑u∈UPuvD2D=1, ∀u∈U.


### 3.4. Communication Model

We model the wireless transmission delay between the User and the BS as the ratio between the content size and the downlink data rate. Similar to [27], the downlink data rate from BS n to User u can be expressed as(9)ru,n=wlog2⁡1+qugu,nσ2+∑v∈U∖uqvgv,nwhere w is channel bandwidth, σ2represents the background noise power, qu is transmission power of BS n to User u, and gu,n is the channel gain and is determined by the distance between the User u and the BS n.


### 3.5. Optimization for D2D-Enabled Edge Caching Problem

Mobile users can share the content via D2D communications. User pairu and v can get the requested content f from u if v has the content (e.g.,sufc=1) while v does not under the probability of PuvD2D. Thus, the content offload from the BSs or Internet via D2D link between u and v can be obtained as lfPuvD2D. Whether the user u has the content for not, we can obtain the total content OD2D via D2D sharing as (10)OD2D=∑fϵFlf∑uϵUPuvD2Dsufc1-svfcOur aiming is to maximize the total size of content offload at users via D2D sharing while satisfying all the buffer size constraints of mobile users. Formally, the optimization problem is defined as(11)maxOD2Ds.t.∑f∈Fsufclf≤Lu,∀u∈Usufc∈0,1,∀u∈U,∀f∈Fwhere ∑f∈Fsufclf≤Lu is the buffer size constraint of all the mobile users’ devices and sufc∈0,1 is the caching state in each mobile device.The optimization problem (11) is NP-hard.Proof.
Leteuv,f=sufc1-svfc, and euv,f∈0,1.
Thus, we can rewrite Problem (11) as(12)max∑f∈Flf∑u∈UPuvD2Dsufc1-svfcs.t.∑f∈Fsufclf≤Lu,∀u∈Uevu,f,sufc∈0,1,∀u,v∈U,∀f∈Fwhere ∑f∈Fsufclf≤Lu is the cardinality constant of Lu. It is easy to observe that Problem (11) has the same structure with the problem formulated in [28], which has been proved as NP-hard.


### 3.6. Cache Replacement Model

We model the cache replacement process as an MDP. Besides, we discuss the details of the related state space, action space, and reward function as follows.( 1 ) State Space. We define sufci as the content caching state during each decision epoch i with respect to the content f∈F, which independently picks a value from a state space P. sufci=1 means content f is cached in the user u and sufci=0 means the opposite. In addition, svri is introduced to denote the current requesting content from other usersv in the decision epoch i. The state of an available user during each decision epoch i can be represented by(13)zi=svri,suci∈Z≝1,2,…F××Pf∈F( 2 ) Action Space. The system action with respect to the state zi can be denoted as A(zi). All users possess the same action space A as(14)A=aiD2D,aiBSNamely, the system action A(zi) can be divided into two parts according to their different characters as follows.(a)Requests Handled via D2D link. The available cache control in the adjacent users is represented by aiD2D≝[ai,0D2D,ai,1D2D,…,ai,FD2D], where ai,fD2D∈{0,1}(f∈1,…,F) indicates that whether and which content in the local user should be replaced by the current requesting content, (ai,0D2D∈0,1) represents whether the local user makes replacement; i.e., the content request is handled by the user itself.(b)Requests Handled by BSs.Certainly, each user can get content directly from BSs when the D2D link fails to meet the requirements. aiSP∈0,1 is introduced to represent this kind of action, where aiBS=1 means that the request is chosen to be directly handled by BSs, namely, the User shall fetch the content from BSs.( 3 ) Reward Function. Reward (utility) function R(z,A), which determines the reward fed back to the user when performing the action A(zi) upon the state zi, shall be determined in the interactive wireless environment to lead the DRL agent (we will introduce it later) in users towards achieving ideal performance. Among the QoS metrics, the most important is to improve the hit rate of user-requested content. Our goal is to maximize the hit rate of user requests. Therefore, in our edge caching architecture, we design the reward function as(15)Rzi,Azi=elf,Azi=aiD2De-lf,Azi=aiBSwhere exponential function with respect to the traffic is adopted here to guide the objective of maximizing the traffic.


## 3.1. Content Popularity and User Preference

The popularity of content is often described as the probability of a content from the libraryF which is requested by all the users. Denote an N×M popularity matrix P, where quf=P(qnm) is the probability of user un requests for content fm in the (n,m)th component. In related studies, the content popularity is always described by ZipF distribution as [24].(1)quf=Ruf-β∑i∈FRi-βwhere the Ruf-β is popularity index that user u gives to content f in a descending order and β≥0 is the ZipF exponent.We measured users’ sharing activities by large-scale tracing of D2D sharing based onXender. As shown in Figure 3 [25], in the real world, the matrix P changes over time (we will introduce the tracking in detail in the sixth part). We assume that the matrix remains constant over time, and our caching strategy refreshes with changes of the popularity matrix P. And the period of user sharing activities can be divided into Peak hours and Peak-off hours. The cache replacement action occurs during the Peak-off hours at each period.User preference: the user preference, which is denoted as Puf, is the probability distribution of a user’s request for each content. According to the content popularity matrix P, each row of the matrix denotes a popularity vector of a user which reflects the preference of a user for a certain content in a statistical way. Assuming that the content popularity and user preference are stochastic, we can obtain the relation:(2)Puf=∑u=1Nwuqufwhere wu is the probability of user u∈U sending a request for various contents f∈F, given to a user request distribution W=[w1,w2,…,wN], ∑u=1Nwu=1, wu∈[0,1], which reflects the request active level of each user.


## 3.2. D2D Sharing Model

Under the D2D-aid cellular networks, users can select either D2D links model or cellular links model. In the D2D links model, users can request and receive the content from the others via D2D links (e.g., Wi-Fi or Bluetooth) or request the content from the BSs directly in a cellular links manner. In our model, the users select D2D links model in advance. If the requested content is not in their own buffers (or their neighbours’), the cellular links model is chosen.To model the D2D sharing activities among mobile users, the opportunistic encounter (e.g., user mobility, meeting probability, and geographical distance) and social relationship (e.g., online relations and user preference) are two important factors to be concerned about.(1) Opportunistic Encounter. It is necessary to ensure that the distance between the two users is less than the critical value dc,when the user communicates via the D2D link. Since the devices are carried by humans or vehicles, we use the meeting probability to describe the user mobility.Similar with the prior work [26], we regard λuv as the contact rate of user u and v, which follows the Poisson distribution and the contact event is independent of the user preference. We can obtain the opportunistic delivery as the Poisson process with rate Pufλuv. If user u caches content f in its buffer, we can derive the probability puv that user v receives content f from user u before the content expires at time Tf. For a node pair, we can derive that(3)puv=∫Tf∞Pufλuve-Pufλuvydy=1-e-PufλuvTfHowever, if the content f is not cached in user u, puv=0. Combined with the definition of sufc, we can overwrite (3), as puv=1-e-PufλufTfsufc. Hence, the probability that user v cannot receive content f from all the other user u∈U is ∏u∈U(1-puv). Then the probability of user v receiving content f from user u can be expressed by(4)Puv=1-∏u∈U1-puv=1-e-PufTf∑u∈Uλufsufc(2) Social Relationship. In social relationship among users, mobile users with weak social relationship may not be willing to share the content with the others owing to the security/privacy concerns. On the other hand, users sometimes have additional resource and are willing to share the content with others. However, the sharing activities may fail because of the hardware/bandwidth restriction (the content may be too large or the traffic speed is too slow). Thus, we consider the social relationship mainly depends on user preference and content transmission rate condition.We employ the notion of Cosine Similarity to measure the user preference between two users and the preference similarity factorCuv is defined as(5)Cuv=∑f∈Fqufqvf∑f∈Fquf2∑f∈Fqvf2,∀u,v∈UFinally, based on the opportunistic encounter and social relationship, we can obtain the probability of D2D sharing between user u and v as follows:(6)PuvD2D=Cuv·Puv,,∀u,v∈U,,∀f∈Fwhere ∑v∈UPuvD2D≤1,∀u∈U. The sum of probability of D2D sharing between each user and other users is less than 1.


## 3.3. Association of Users and BSs

Users can ask the content directly from the associated local BS when the requested content cannot be satisfied by D2D sharing. DefinitionPuBS is the cellular serving ratio, which is the average probability that the requests of user u have to be served by local BS via backhaul link rather than D2D communications. Thus, we can obtain PuBS=1-∑v∈UPuvD2D,∀u∈U. In this paper, we consider that the content transmission process can be finished within the user mobility tolerant time, e.g., before the user moves out of the communication range of the local BS. The requested content can be satisfied from the buffer of local BS or obtained from the neighbour BSs via BS-BS link as well as the Internet via backhaul link. Let PuBBS denote the probability of BS n serving user u, then we have(7)PuBBS=∑iTunBSi∑n∈N∑iTunBSiwhere TunBS(i) denote the time period of the i-th cellular serving from BS n to user u during the total sample time Ttot. Therefore, we have the probability PuvBS that user u is served by BS n as follows:(8)PuBnBS=PuBS·PuBBS,∀u∈U,∀n∈NNote that ∑n∈NPunBS+∑u∈UPuvD2D=1, ∀u∈U.


## 3.4. Communication Model

We model the wireless transmission delay between the User and the BS as the ratio between the content size and the downlink data rate. Similar to [27], the downlink data rate from BS n to User u can be expressed as(9)ru,n=wlog2⁡1+qugu,nσ2+∑v∈U∖uqvgv,nwhere w is channel bandwidth, σ2represents the background noise power, qu is transmission power of BS n to User u, and gu,n is the channel gain and is determined by the distance between the User u and the BS n.


## 3.5. Optimization for D2D-Enabled Edge Caching Problem

Mobile users can share the content via D2D communications. User pairu and v can get the requested content f from u if v has the content (e.g.,sufc=1) while v does not under the probability of PuvD2D. Thus, the content offload from the BSs or Internet via D2D link between u and v can be obtained as lfPuvD2D. Whether the user u has the content for not, we can obtain the total content OD2D via D2D sharing as (10)OD2D=∑fϵFlf∑uϵUPuvD2Dsufc1-svfcOur aiming is to maximize the total size of content offload at users via D2D sharing while satisfying all the buffer size constraints of mobile users. Formally, the optimization problem is defined as(11)maxOD2Ds.t.∑f∈Fsufclf≤Lu,∀u∈Usufc∈0,1,∀u∈U,∀f∈Fwhere ∑f∈Fsufclf≤Lu is the buffer size constraint of all the mobile users’ devices and sufc∈0,1 is the caching state in each mobile device.The optimization problem (11) is NP-hard.Proof.
Leteuv,f=sufc1-svfc, and euv,f∈0,1.
Thus, we can rewrite Problem (11) as(12)max∑f∈Flf∑u∈UPuvD2Dsufc1-svfcs.t.∑f∈Fsufclf≤Lu,∀u∈Uevu,f,sufc∈0,1,∀u,v∈U,∀f∈Fwhere ∑f∈Fsufclf≤Lu is the cardinality constant of Lu. It is easy to observe that Problem (11) has the same structure with the problem formulated in [28], which has been proved as NP-hard.


## 3.6. Cache Replacement Model

We model the cache replacement process as an MDP. Besides, we discuss the details of the related state space, action space, and reward function as follows.( 1 ) State Space. We define sufci as the content caching state during each decision epoch i with respect to the content f∈F, which independently picks a value from a state space P. sufci=1 means content f is cached in the user u and sufci=0 means the opposite. In addition, svri is introduced to denote the current requesting content from other usersv in the decision epoch i. The state of an available user during each decision epoch i can be represented by(13)zi=svri,suci∈Z≝1,2,…F××Pf∈F( 2 ) Action Space. The system action with respect to the state zi can be denoted as A(zi). All users possess the same action space A as(14)A=aiD2D,aiBSNamely, the system action A(zi) can be divided into two parts according to their different characters as follows.(a)Requests Handled via D2D link. The available cache control in the adjacent users is represented by aiD2D≝[ai,0D2D,ai,1D2D,…,ai,FD2D], where ai,fD2D∈{0,1}(f∈1,…,F) indicates that whether and which content in the local user should be replaced by the current requesting content, (ai,0D2D∈0,1) represents whether the local user makes replacement; i.e., the content request is handled by the user itself.(b)Requests Handled by BSs.Certainly, each user can get content directly from BSs when the D2D link fails to meet the requirements. aiSP∈0,1 is introduced to represent this kind of action, where aiBS=1 means that the request is chosen to be directly handled by BSs, namely, the User shall fetch the content from BSs.( 3 ) Reward Function. Reward (utility) function R(z,A), which determines the reward fed back to the user when performing the action A(zi) upon the state zi, shall be determined in the interactive wireless environment to lead the DRL agent (we will introduce it later) in users towards achieving ideal performance. Among the QoS metrics, the most important is to improve the hit rate of user-requested content. Our goal is to maximize the hit rate of user requests. Therefore, in our edge caching architecture, we design the reward function as(15)Rzi,Azi=elf,Azi=aiD2De-lf,Azi=aiBSwhere exponential function with respect to the traffic is adopted here to guide the objective of maximizing the traffic.


## 4. Edge Caching Policy Discussion

In the hierarchical wireless networks with cache-enabled D2D communications, we explore the maximum capacity of the network based on the mobility and social behaviours of users. The goal is to optimize the network edge caching by offloading the contents to users via D2D communications and reducing the system cost of content exchange between BSs and core network via cellular links.


### 4.1. Problem Formulation

Based on the above analysis and combined with (15), the optimization objective is defined as(16)Rlong=max⁡EAlimI→∞1I∑i=1IRzi,Azi∣z1=zwhich indicates maximizing the expected long-term reward value conditioned on any initial state z1.Nevertheless, in general, a single-agent infinite-horizon MDP with the discounted utility (17) can be used to approximate the expected infinite-horizon undiscounted value when γϵ0,1 approaches 1.(17)Vz,A=EA∑i=1∞γi-1·Rzi,Azi∣z1=zFurther, we can obtain the optimal state value function Vz for any initial state χ as(18)Vz=Vz,A∗,∀z∈ZIn conclusion, each user is expected to learn an optimal control policy A∗ that maximizes Vz,A, with any initial state z. The optimal control policy can be described as follows:(19)A∗=argmaxA⁡Vz,A,∀z∈Z


## 4.1. Problem Formulation

Based on the above analysis and combined with (15), the optimization objective is defined as(16)Rlong=max⁡EAlimI→∞1I∑i=1IRzi,Azi∣z1=zwhich indicates maximizing the expected long-term reward value conditioned on any initial state z1.Nevertheless, in general, a single-agent infinite-horizon MDP with the discounted utility (17) can be used to approximate the expected infinite-horizon undiscounted value when γϵ0,1 approaches 1.(17)Vz,A=EA∑i=1∞γi-1·Rzi,Azi∣z1=zFurther, we can obtain the optimal state value function Vz for any initial state χ as(18)Vz=Vz,A∗,∀z∈ZIn conclusion, each user is expected to learn an optimal control policy A∗ that maximizes Vz,A, with any initial state z. The optimal control policy can be described as follows:(19)A∗=argmaxA⁡Vz,A,∀z∈Z


## 5. Double DQN-Based Edge Cache Strategy

### 5.1. Reinforcement Learning

Reinforcement learning is a machine learning algorithm. In other words, it is a way for an agent to keep trying, to learn from mistakes, and finally to find patterns. RL problems can be described as the optimal control decision making problem in MDP. RL contains many forms, among which Q-learning algorithm based on tabular learning is commonly used. Q-learning is an off-policy learning algorithm that allows an agent to learn through current or past experiences.In our D2D caching architecture, the agent pertains to the user senses and obtains its current cache statezi. Then, the agent selects and carries out an action Azi. Meantime, the environment experiences a transition from zi to a new state zi+1 and obtains a reward Rzi,Azi.According to the Bellman Equation, the optimal Q-value functionQz,A can be expressed as (20), where z=zi is the state at current decision epochi, and the next state is z′=zi+1 after taking the action A=Azi. (20)Qz,A=Rz,A+γ·∑z′Prz′∣z,A·maxA′⁡Qz′,A′The iterative formula of Q-function can be obtained as(21)Qi+1z,A=Qiz,A+αi·Rz,A+γ·maxA′⁡Qiz′,A′-Qiz,Awhere αiϵ0,1 is the learning rate and the statezi will turn to the statezi+1 when the agent chooses actionAzi along with the corresponding rewardRzi,Azi. Based on (21), theQ-Table can be used to store theQ value of each state-action pair when the state and action space dimensions are not high in theQ-Learning algorithm. We conclude the training algorithm based on the Q-Learning in Algorithm 1. The complexity of the Q-learning algorithm depends primarily on the scale of the problem. Updating the Q value in a given state requires determining the maximum Q value for all possible actions in the corresponding state in the table. In a given state, if there are n possible actions, finding the maximum Q value requires n-1 comparisons. In other words, if there are n states, the update of the entire Q-table requires m(n-1) comparison. Hence, the learning process inQ-Learning becomes extremely difficult when the scenarios are with huge network states and action spaces. Therefore, using neural network to generate Q value becomes a potential solution.Algorithm 1:Q-Learning-based content caching algorithm.
Initialization: Q-Table Iteration: 1: for each episode 2: Initialize z 3: for each step of episode 4:  Generate a at random 5:  if a≤ε 6:  randomly select an action 7:  else 8:  choose Az using policy derived from Qz,A 9:  Take action Az 10: Obtain Rz,Az  and  z′ 11: Update Q-Table:Q(z,A)←Q(z,A)+α⋅(R(z,A)+γ⋅maxΦ′⁡Q(z′,A′)-Q(z,A)) 12:z←z′ 13:end for 14:end for


### 5.2. Double Deep Q-Learning

DQN is the first model that successfully combines Deep Learning with Reinforcement Learning. It replaced the Q-table with the neural network, which effectively solved the complicated and high dimensional RL problems. It comes in many variations, the most famous of which is Double DQN [29]. In our model, we use Double DQN to train our DRL agents in users, which is formed as shown in Figure 2. TheQ-function could be approximated to the optimalQ value by updating the parameter τi of neural network as follows:(22)Qz,A≈Qz,A;τiExperience replay is the core component of DQN. It actually is a memory for storing transitions with a finite size Nm, and its stored procedures are overridden by loops. It can effectively eliminate the correlation between training data. The transition sample can be represented as Ti=zi,Azi,Rzi,Azi,zi+1, which represents one state transition. The whole experience pool can be denoted as M=Ti-Nm+1,…,Ti. Note that each DRL agent maintains twoQ networks, namely.Qz,A;τi and Q′z,A;τi′, with networkQ used to choose action and network Q′ to evaluate action. Besides, the counterpart τi of networkQperiodically updates the weight parameters τi′ of network Q′.Figure 2
Illustration of training process.Figure 3
Statistic for all sharing activities [25].Throughout the training process, the DRL agent randomly samples a minibatchM′ from the experience replay M. Then, at each epoch, the networkQ is trained towards the direction of minimizing the loss function as(23)Lτi=Ez,A,Rz,A,z′∈Mi~Rz,A+γ·Q′z,argmaxA′Qz′,A′;τi;τi′-Qz,A;τi2And with (23), the gradient guiding updates of τ can be calculated by ∂Lτi/∂τi. Hence, Stochastic Gradient Descent (SGD) is performed until the convergence ofQ networks for approximating optimal state-actionQ-function. We conclude the training algorithm based on the Double DQN in Algorithm 2.Algorithm 2:Double DQN-based content caching algorithm.
Initialization:Experience replay memory M, main Q network with random weights τ, target Q′ network withτ′=τ, and the period of replacing target Q network ϕ. Iteration: 1: for each episode 2:  Initialize z 3 i←0 4: for each step of episode 5: i←i+1 6:  Randomly generate a 8:  if a≤ε 9:  randomly select an action 10: else 11:Az←arg⁡maxAzQ(z,Az;τi) 12: Take action Azi 13: Obtain Rzi,Azi and z′. 14: Store T←z,Az,Rz,Az,z′ into M. 15: Randomly sample a mini-batch of transitions M′∈M. 16: Update τi with ∂L(τi)/∂τi. 17: if i==ϕ 18: Update τi′ 19:i←0 20:z←z′ 21:end for 22:end forAbout algorithm complexity, it mainly includes collecting transitions and executing backpropagation to train the parameters. Since collecting one transition requiresO(1) computational complexity, the total computational complexity for collecting K transitions into the replay memory is O(K). Let a and b denote the number of layers and the maximum number of units in each layer, respectively. Training parameters with backpropagation and gradient descent requires the computational complexity of O(mabi) wherem andi denote the number of transitions randomly sampled from the replay memory and the number of iterations, respectively. Furthermore, the replay memory and the parameters of the double deep Q-learning model dominate the storage complexity. Specially, storing K transitions needs the about space complexity of O(K) while the parameters need the about space complexity of O(ab).


## 5.1. Reinforcement Learning

Reinforcement learning is a machine learning algorithm. In other words, it is a way for an agent to keep trying, to learn from mistakes, and finally to find patterns. RL problems can be described as the optimal control decision making problem in MDP. RL contains many forms, among which Q-learning algorithm based on tabular learning is commonly used. Q-learning is an off-policy learning algorithm that allows an agent to learn through current or past experiences.In our D2D caching architecture, the agent pertains to the user senses and obtains its current cache statezi. Then, the agent selects and carries out an action Azi. Meantime, the environment experiences a transition from zi to a new state zi+1 and obtains a reward Rzi,Azi.According to the Bellman Equation, the optimal Q-value functionQz,A can be expressed as (20), where z=zi is the state at current decision epochi, and the next state is z′=zi+1 after taking the action A=Azi. (20)Qz,A=Rz,A+γ·∑z′Prz′∣z,A·maxA′⁡Qz′,A′The iterative formula of Q-function can be obtained as(21)Qi+1z,A=Qiz,A+αi·Rz,A+γ·maxA′⁡Qiz′,A′-Qiz,Awhere αiϵ0,1 is the learning rate and the statezi will turn to the statezi+1 when the agent chooses actionAzi along with the corresponding rewardRzi,Azi. Based on (21), theQ-Table can be used to store theQ value of each state-action pair when the state and action space dimensions are not high in theQ-Learning algorithm. We conclude the training algorithm based on the Q-Learning in Algorithm 1. The complexity of the Q-learning algorithm depends primarily on the scale of the problem. Updating the Q value in a given state requires determining the maximum Q value for all possible actions in the corresponding state in the table. In a given state, if there are n possible actions, finding the maximum Q value requires n-1 comparisons. In other words, if there are n states, the update of the entire Q-table requires m(n-1) comparison. Hence, the learning process inQ-Learning becomes extremely difficult when the scenarios are with huge network states and action spaces. Therefore, using neural network to generate Q value becomes a potential solution.Algorithm 1:Q-Learning-based content caching algorithm.
Initialization: Q-Table Iteration: 1: for each episode 2: Initialize z 3: for each step of episode 4:  Generate a at random 5:  if a≤ε 6:  randomly select an action 7:  else 8:  choose Az using policy derived from Qz,A 9:  Take action Az 10: Obtain Rz,Az  and  z′ 11: Update Q-Table:Q(z,A)←Q(z,A)+α⋅(R(z,A)+γ⋅maxΦ′⁡Q(z′,A′)-Q(z,A)) 12:z←z′ 13:end for 14:end for


## 5.2. Double Deep Q-Learning

DQN is the first model that successfully combines Deep Learning with Reinforcement Learning. It replaced the Q-table with the neural network, which effectively solved the complicated and high dimensional RL problems. It comes in many variations, the most famous of which is Double DQN [29]. In our model, we use Double DQN to train our DRL agents in users, which is formed as shown in Figure 2. TheQ-function could be approximated to the optimalQ value by updating the parameter τi of neural network as follows:(22)Qz,A≈Qz,A;τiExperience replay is the core component of DQN. It actually is a memory for storing transitions with a finite size Nm, and its stored procedures are overridden by loops. It can effectively eliminate the correlation between training data. The transition sample can be represented as Ti=zi,Azi,Rzi,Azi,zi+1, which represents one state transition. The whole experience pool can be denoted as M=Ti-Nm+1,…,Ti. Note that each DRL agent maintains twoQ networks, namely.Qz,A;τi and Q′z,A;τi′, with networkQ used to choose action and network Q′ to evaluate action. Besides, the counterpart τi of networkQperiodically updates the weight parameters τi′ of network Q′.Figure 2
Illustration of training process.Figure 3
Statistic for all sharing activities [25].Throughout the training process, the DRL agent randomly samples a minibatchM′ from the experience replay M. Then, at each epoch, the networkQ is trained towards the direction of minimizing the loss function as(23)Lτi=Ez,A,Rz,A,z′∈Mi~Rz,A+γ·Q′z,argmaxA′Qz′,A′;τi;τi′-Qz,A;τi2And with (23), the gradient guiding updates of τ can be calculated by ∂Lτi/∂τi. Hence, Stochastic Gradient Descent (SGD) is performed until the convergence ofQ networks for approximating optimal state-actionQ-function. We conclude the training algorithm based on the Double DQN in Algorithm 2.Algorithm 2:Double DQN-based content caching algorithm.
Initialization:Experience replay memory M, main Q network with random weights τ, target Q′ network withτ′=τ, and the period of replacing target Q network ϕ. Iteration: 1: for each episode 2:  Initialize z 3 i←0 4: for each step of episode 5: i←i+1 6:  Randomly generate a 8:  if a≤ε 9:  randomly select an action 10: else 11:Az←arg⁡maxAzQ(z,Az;τi) 12: Take action Azi 13: Obtain Rzi,Azi and z′. 14: Store T←z,Az,Rz,Az,z′ into M. 15: Randomly sample a mini-batch of transitions M′∈M. 16: Update τi with ∂L(τi)/∂τi. 17: if i==ϕ 18: Update τi′ 19:i←0 20:z←z′ 21:end for 22:end forAbout algorithm complexity, it mainly includes collecting transitions and executing backpropagation to train the parameters. Since collecting one transition requiresO(1) computational complexity, the total computational complexity for collecting K transitions into the replay memory is O(K). Let a and b denote the number of layers and the maximum number of units in each layer, respectively. Training parameters with backpropagation and gradient descent requires the computational complexity of O(mabi) wherem andi denote the number of transitions randomly sampled from the replay memory and the number of iterations, respectively. Furthermore, the replay memory and the parameters of the double deep Q-learning model dominate the storage complexity. Specially, storing K transitions needs the about space complexity of O(K) while the parameters need the about space complexity of O(ab).


## 6. Experiment

In this section, we evaluate the proposed cache policy based on the experimental results of the mobile applicationXender.


### 6.1. DataSet

Xender is a mobile APP that can realize offline D2D communication activities. It provides a new way to share diversified content files users are interested in without accessing 3G/4G cellular mobile networks, largely reducing repeated traffic load and waste of network resources, as a result, achieving resource sharing. CurrentlyXender has around 10 million daily and 100 million monthly active users, as well as about 110 million daily content deliveries.We captureXender’s trace for one month (from 01/08/2016 to 31/08/2016), including 450,786 active mobile users, conveying 153,482 content files, and 271,785,952 content requests [30]. As shown in Figure 4, the content popularity distribution in theXender’s trace can be fitted by MZipf distribution with a plateau factor of −0.88 and a skewness factor of 0.35.Figure 4
Content popularity.


### 6.2. Parameter Settings

In our simulations, four BSs are employed with maximum cover range 250 m,gu,n=30.6+36.7log10⁡lu,n in dB [31] is taken as the channel gain model, and the channel bandwidth of each BS is set as 20 MHz. The delays of D2D link, BS to MNO and MNO to Internet are 5ms, 20ms, and 100ms, respectively. Besides, the total transmit power of BS is 40 W with serving at most 500 Users. With respect to the parameter settings of Double DQN, a single-layer fully connected feed forward neural network, including 200 neurons, is used to serve as the target and the eval Q network. Other parameter values are given in Table 1.Table 1
Parameter Value.
F w [ M H z ] σ 2 [ d B m ] M M ′ γ ϵ α ϕ Range 1000 200 -95 5000 200 0.9 0.1 0.05 250


### 6.3. Evaluation Results

In order to evaluate the performance of our caching strategy, we compared it with three classic cache replacement algorithms.( 1 ) LRU: replace the least recently used content.( 2 ) LFU: replace the least commonly used content first.( 3 ) FIFO: replace the first in content first.Figure5 shows the performance comparison of cache hit ratio, delay, and traffic at F=1000 and C=100M. As we can see, at the beginning of the simulation, the caching strategy we proposed was surely at a great disadvantage among three aspects. But soon the hit rate increased and stabilized eventually. This is because our reward function is used to increase the cache hit rate; thus, our DRL agent is dedicated to maximizing the system hit rate. It can be seen that our caching strategy is significantly 9%, 12%, and 14% higher than LRU, LFU, and FIFO in terms of hit rate, respectively. At the same time, the improvement of the hit rate has a positive impact on the delay, traffic indicators, and other indexes. The delay of our strategy is 12%, 17%, and 21% lower than that of LRU, LFU, and FIFO, respectively. Besides, the traffic saved is 8%, 10%, and 14%, respectively.Figure 5
Performance evaluation in terms of hit rate, delay, and traffic with respect to the time.
(a)
Hit rate (b)
Delay (c)
TrafficIn addition, we explored the effect of content quantity on performance comparison results. We compared the performance when the number of contents is 1000 and 2000. As shown in Figure6, it can be inferred that when the number of contents increases, the convergence of the algorithm changes and the hit rate decreases. However, it cannot change the overall trend of the algorithm. Our caching strategy can still perform optimally in these four algorithms.Figure 6
Performance comparison betweenF=1000, F=2000.
(a)
Hit rate (b)
Delay (c)
TrafficFinally, we explored the effects of learning rate and exploration probability on our algorithm performances. As shown in Figure7, learning rate is 0.5 and 0.05 and exploration probability is 0.1 and 0.5, respectively. It can be seen that both of these factors have a great impact on the cache strategy, mainly manifesting in convergence and performance. Thus large numbers of experiments are performed to find an appropriate learning rate and exploration probability for the proposed edge caching scenarios. Hence, in our setting, α=0.05 and ϵ=0.1 are selected for achieving better performance.Figure 7
Performance of hit rate under different parameters.
(a)
Hit rate underα=0.05,α=0.5 (b)
Hit rate underϵ=0.1,ϵ=0.5


## 6.1. DataSet

Xender is a mobile APP that can realize offline D2D communication activities. It provides a new way to share diversified content files users are interested in without accessing 3G/4G cellular mobile networks, largely reducing repeated traffic load and waste of network resources, as a result, achieving resource sharing. CurrentlyXender has around 10 million daily and 100 million monthly active users, as well as about 110 million daily content deliveries.We captureXender’s trace for one month (from 01/08/2016 to 31/08/2016), including 450,786 active mobile users, conveying 153,482 content files, and 271,785,952 content requests [30]. As shown in Figure 4, the content popularity distribution in theXender’s trace can be fitted by MZipf distribution with a plateau factor of −0.88 and a skewness factor of 0.35.Figure 4
Content popularity.


## 6.2. Parameter Settings

In our simulations, four BSs are employed with maximum cover range 250 m,gu,n=30.6+36.7log10⁡lu,n in dB [31] is taken as the channel gain model, and the channel bandwidth of each BS is set as 20 MHz. The delays of D2D link, BS to MNO and MNO to Internet are 5ms, 20ms, and 100ms, respectively. Besides, the total transmit power of BS is 40 W with serving at most 500 Users. With respect to the parameter settings of Double DQN, a single-layer fully connected feed forward neural network, including 200 neurons, is used to serve as the target and the eval Q network. Other parameter values are given in Table 1.Table 1
Parameter Value.
F w [ M H z ] σ 2 [ d B m ] M M ′ γ ϵ α ϕ Range 1000 200 -95 5000 200 0.9 0.1 0.05 250


## 6.3. Evaluation Results

In order to evaluate the performance of our caching strategy, we compared it with three classic cache replacement algorithms.( 1 ) LRU: replace the least recently used content.( 2 ) LFU: replace the least commonly used content first.( 3 ) FIFO: replace the first in content first.Figure5 shows the performance comparison of cache hit ratio, delay, and traffic at F=1000 and C=100M. As we can see, at the beginning of the simulation, the caching strategy we proposed was surely at a great disadvantage among three aspects. But soon the hit rate increased and stabilized eventually. This is because our reward function is used to increase the cache hit rate; thus, our DRL agent is dedicated to maximizing the system hit rate. It can be seen that our caching strategy is significantly 9%, 12%, and 14% higher than LRU, LFU, and FIFO in terms of hit rate, respectively. At the same time, the improvement of the hit rate has a positive impact on the delay, traffic indicators, and other indexes. The delay of our strategy is 12%, 17%, and 21% lower than that of LRU, LFU, and FIFO, respectively. Besides, the traffic saved is 8%, 10%, and 14%, respectively.Figure 5
Performance evaluation in terms of hit rate, delay, and traffic with respect to the time.
(a)
Hit rate (b)
Delay (c)
TrafficIn addition, we explored the effect of content quantity on performance comparison results. We compared the performance when the number of contents is 1000 and 2000. As shown in Figure6, it can be inferred that when the number of contents increases, the convergence of the algorithm changes and the hit rate decreases. However, it cannot change the overall trend of the algorithm. Our caching strategy can still perform optimally in these four algorithms.Figure 6
Performance comparison betweenF=1000, F=2000.
(a)
Hit rate (b)
Delay (c)
TrafficFinally, we explored the effects of learning rate and exploration probability on our algorithm performances. As shown in Figure7, learning rate is 0.5 and 0.05 and exploration probability is 0.1 and 0.5, respectively. It can be seen that both of these factors have a great impact on the cache strategy, mainly manifesting in convergence and performance. Thus large numbers of experiments are performed to find an appropriate learning rate and exploration probability for the proposed edge caching scenarios. Hence, in our setting, α=0.05 and ϵ=0.1 are selected for achieving better performance.Figure 7
Performance of hit rate under different parameters.
(a)
Hit rate underα=0.05,α=0.5 (b)
Hit rate underϵ=0.1,ϵ=0.5


## 7. Conclusions

In this paper, we study the edge caching strategy of layered wireless networks. Specifically, we use the Markov decision process and Deep Reinforcement Learning in the proposed edge cache replacement strategy. The experimental results based on actual tracking show that our proposed strategy is superior to LRU, LFU, and FIFO in terms of hit rate, delay and traffic offload. Finally, we also explored the impact of learning rate and exploration probability on algorithm performance.In the future, we’ll focus more on the user layer’s impact on cache replacement. (1) In the existing D2D model, the transmission process of files is not persistent, and complex user movement will lead to the interruption of content delivery. In the future, we will consider this factor in the reward function; (2) The cache replacement process requires additional costs, such as latency and energy consumption, all of which should be considered, but how to quantify these factors in the simulation experiment still needs to be explored. (3) The computing resources of user devices are limited. Although Deep Reinforcement Learning can solve the problem of dimensional explosion, it still requires a lot of computing resources. Therefore, we will explore the application of more lightweight learning algorithms in D2D-aid cellular networks.



---

*Source: 2561069-2019-02-27.xml*