# Joint Optimization of Content Placement and User Association in Cache-Enabled Heterogeneous Cellular Networks Based on Flow-Level Models

Authors: Hua Qu; Gongye Ren; Jihong Zhao; Zhenjie Tan; Shuyuan Zhao
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Cache-enabled heterogeneous cellular networks (HCNs) have been investigated extensively to alleviate backhaul congestion and reduce content delivery delay. In this paper, we jointly optimize content placement and user association to minimize the average content delivery delay in cache-enabled HCNs based on flow-level models. This formulation considers (1) different timescales of content placement and content delivery, (2) locality of content popularity, and (3) the heterogeneity of spatial traffic distribution, which are often neglected in existing researches. The joint optimization problem is formulated as a mixed integer nonlinear programming problem in load-non-coupled and load-coupled models, respectively. We decouple this problem into two interrelated subproblems and resolve them individually. For the user association problem under a given content placement situation, we propose a content-level selective association algorithm, which allows the requests for different contents at the same location to connect to different base stations (BSs). In addition, we propose a greedy content caching algorithm to add contents to the caches of BSs in an iterative manner. These two algorithms are alternately executed until the caches of all the BSs are filled to capacity. Simulation results show that the proposed algorithm achieves better performance in terms of average delay and backhaul usage compared with traditional content placement and user association approaches.


---

## Body

## 1. Introduction

Driven by the proliferation of smart devices and abundant applications, the past decade witnesses a sharp rise in mobile data traffic. It is predicted that the global mobile data traffic will reach 49 exabytes per month by 2021 [1]. An effective approach to address the explosively growing data volume is to deploy plenty of low-power small base stations (SBSs) together with traditional macrobase stations (MBSs) to form a heterogeneous cellular network (HCN) [2, 3]. The densely deployed SBSs can meet the huge demand for high-speed data traffic in hot-spots and fill coverage holes of macrocells. However, deploying high-speed backhaul links to connect massive SBSs to core networks brings about huge capital and operational expenditures, which are unaffordable for network operators.Among the huge data traffic, mobile video streaming is expected to account for 78% of the total data traffic in 2021. Many studies have shown that video streaming in wireless networks exhibits significant regularity [4–6]. Particularly, a few popular contents are requested frequently by different users at different times, which is referred to as asynchronous content reuse [7]. Repetitive content transmission raises congestion in backhaul links and core networks, especially at peak hours, which increases the content retrieval delay and decreases the efficiency of content delivery. This issue is further aggravated by the limited-capacity backhaul links of SBSs. Borrowing the concept of information-centric networking in wired networks [8], caching at the wireless edge [9–12] has been proposed to reduce the backhaul usage via equipping BSs and mobile devices with low-cost cache units. In the cache-enabled cellular networks, majority of requested contents can be directly obtained from local storage, nearby devices or BSs, which significantly alleviates the backhaul congestion and reduces the download delay. The implementation of content-centric networking paradigm in HCNs can unleash the potential of HCNs and is an important candidate technology for the fifth generation communication systems [10, 11].


### 1.1. Related Work

Many studies focus on the performance analysis of cache-enabled communication networks. In [13], the performance of a coded caching scheme is analyzed from the perspective of information theory. The work of [14] contrasts the cache-enabled device-to-device (D2D) content delivery with other alternative approaches and demonstrates its superiority. The authors of [15] investigate the scaling law of link rates with respect to some network size parameters in a cache-enabled wireless network and analyze the sustainability of this network. Using tools from stochastic geometry, [16] derives the expressions of outage probability and average delivery rate in a cache-enabled small cell network and analyzes the impacts of some network parameters on the system performance. Likewise, Yanget al. [17] deduce the outage probability and average ergodic rate in cache-enabled HCNs. Reference [18] investigates the energy efficiency of the cache-enabled wireless access networks and analyzes the effects of some factors on it.Generally, the content delivery in cache-enabled networks consists of two phases [13]: content placement phase and content delivery phase. In the content placement phase, some strategic contents are prefetched via backhaul links and cached at BSs during off-peak hours. In the context of D2D networks, contents can also be predownloaded from BSs to devices and cached at devices. The content placement schemes are crucial to the performance of cache-enabled networks and are studied extensively. In [19], the content placement problem is formulated as maximizing a monotone submodular function over matroid constraints and a greedy algorithm is proposed to solve it. Reference [20] proposes a distributed belief propagation algorithm to solve the content placement problem, which is aimed at minimizing the download latency. Taking into account BS cooperation and the propagation delay in backhaul links, Penget al. [21] propose a low-complexity algorithm to optimize the caching placement strategy. The above-mentioned content placement schemes are all implemented in concrete network scenarios, and the outputs of these schemes are caching states of given contents at specific BSs or devices. These schemes are termed deterministic caching policies. Another line of work focuses on the probabilistic caching policy, which optimizes a caching distribution for a group of cache-enabled nodes. These studies often model the networks based on stochastic geometry and find the caching policies that optimize the derived performance metrics. In [22], an optimal probabilistic caching policy is proposed to maximize the content hit probability, which can be defined based on either signal-to-interference-plus-noise ratio (SINR) model or Boolean model. Reference [23] proposes the tier-level content placement policies in HCNs. Taking into consideration millimeter-wave and full-duplex communications, [24] proposes a content dissemination mechanism based on proactive content fetching in cache-enabled full-duplex D2D networks and analyzes its performance from an evolutionary perspective.After contents have been cached at BSs and/or devices, content delivery schemes direct how to deliver the requested contents to users, e.g., routing, resource allocation, transmission schemes, and so on. In [25], the cache-aware user association problem is formulated as a one-to-many game and the objective is to minimize the backhaul usage at each SBS. By leveraging both physical and social characteristics, [26] jointly optimizes user pairing, channel allocation and power control in cache-enabled D2D networks. Chenget al. [27] propose three power allocation algorithms with different objectives in cache-aided small cell networks with limited backhaul. In a given caching situation, [28] proposes a distributed relaxing-rounding algorithm to jointly optimize user association and resource allocation in small cell networks. Reference [29] studies the multicast scheduling in cache-enabled wireless networks. By formulating the optimization problem as a Markov decision process, the authors analyze the structure of the optimal policy and propose a low-complexity suboptimal policy.The performance of content-centric networking paradigm highly depends on the cooperation between content placement and content delivery. Content placement determines the upper bound of the performance of content delivery, and content delivery is implemented in a given content placement situation. Joint optimization of content placement and content delivery takes into account the interaction between these two aspects and can improve the performance dramatically compared with separate approaches. Reference [30] formulates the joint routing and caching problem as a variant of the facility location problem, and proposes an approximation algorithm to solve this NP-hard problem. In [31], the joint optimization of request routing and content caching in a network with given topology is investigated. The authors propose approximate solutions for this problem in congestion-insensitive and congestion-sensitive models, respectively. In [32], the authors develop the optimal cooperative content caching and delivery policy in a network where both BSs and devices have cache capacity. The work in [33] jointly optimizes caching, routing, and channel assignment in a collaborative small cell networks, in which network coding is applied to enable multiple BSs to cooperatively transmit contents to a user. Reference [34] considers multicasting in cache-enabled HCNs and optimizes the content caching at different tiers to maximize the successful transmission probability. The authors of [35] design a probabilistic caching policy and a random scheduling policy to maximize the successful offloading probability in cache-enabled D2D networks.


### 1.2. Motivation, Contributions, and Organization

Although the joint optimization of content placement and content delivery has been investigated extensively in the literature, there are three important issues that are not considered in the state-of-the-art researches, as specified in the following.First, the timescale of content placement is much larger than that of content delivery. The rate of content placement should accord with the variation of content library and the content popularity distribution over it, which can be deemed constant during a few days [7]. The timescale of content delivery, which is affected by user mobility and user activity, ranges from seconds to minutes. Existing works, such as [32, 33, 36, 37], often optimize content placement at the timescale of content delivery; i.e., the content placement is designed based on a snapshot of a network with given user distribution. When user distribution changes, the previously derived content placement scheme is no longer optimal and it should be updated based on the new user distribution. Frequent content replacement due to user mobility and user activity makes the backhaul links congested, and the advantages of caching diminish or even become negative. Moreover, because of the combinatorial characteristic of content placement problems, their solutions often have relatively high complexity, and they are not practicable in a highly dynamic scenario.Second, the local content popularity often differs from the general content popularity. Content popularity distribution is a holistic statistical measure over a large area, and it may obscure meaningful difference in content popularity among small regions. References [38, 39] have verified this point based on analysis of the real YouTube datasets. Most current researches simply assume identical content request probabilities among all the users, and neglect the geographic locality of user interests.Third, the spatial traffic distribution is uneven over a large area. Due to the unequal population sizes in different regions and the difference in user behaviors, the spatial traffic distribution exhibits evident heterogeneity [40, 41]. The traffic demand in hot-spots is much larger than that in suburbs. In existing works, especially the ones in which models are constructed based on stochastic geometry, such as [22–24, 34, 35], the traffic demand is uniformly distributed. This setting differs from real situation and the performance of these approaches will be degraded in practical application.For addressing the above challenges, in this paper, we formulate a framework for joint optimization of content placement and user association in cache-enabled HCNs based on flow-level models [42, 43]. In the flow-level models, networks are modeled as queuing systems, in which BSs correspond to servers and user requests correspond to flows to be served by these servers. Different from traditional snapshot models, flow-level models focus on the spatial traffic demand distribution during a time period instead of the locations and demands of individual users at a certain moment. With the help of flow-level models, we jointly optimize content placement and user association based on the aggregated traffic demand during a long time period rather than instantaneous traffic demand. There are two kinds of flow-level models proposed in the literature: load-non-coupled (LNC) model [42] and load-coupled (LC) model [44]. In the LNC model, the intercell interference is assumed to be static, while, in the LC model, the intercell interference interacts with the loads of other BSs. In this paper, we propose a greedy content caching and content-level selective association (GCC-CSA) algorithm in LNC and LC model, respectively, for joint optimization of content placement and user association in cache-enabled HCNs. The content-level spatial traffic distribution is modeled to simulate the difference in content popularity among different regions. The superposition of all the content-level spatial traffic distributions forms the overall spatial traffic distribution. This joint optimization problem is formulated as a mixed integer nonlinear programming (MINLP) problem and its objective is to minimize the average delay of a typical flow. This formulation takes into account the limited backhaul capacity of SBSs and its effect on the achievable data rate of each content. For tackling this problem, we decouple it into two interrelated subproblems. First, we propose a CSA algorithm to optimize user association in a given content placement situation. The requests for different contents at the same location are allowed to be served by different BSs due to different caching states of these contents at nearby BSs. Second, we propose a GCC algorithm to add the content that yields the maximum reduction in the value of cost function to each BS in a given user association situation. These two algorithms are alternately executed until the caches of all the BSs are filled to capacity. The derived content-level selective user association takes effect unless the content-level spatial traffic distribution changes, which means that user association is optimized at the timescale of content placement.Our main contributions are summarized as follows.(1) We formulate the joint optimization of content placement and user association based on flow-level models. In this formulation, content-level spatial traffic distribution is modeled to simulate the locality of content popularity and the heterogeneity of spatial traffic distribution, and user association is optimized at the timescale of content placement. To the best of our knowledge, this is the first work that addresses all the issues summarized above.(2) We jointly optimize content placement and user association in LNC and LC model, respectively. LNC model and LC model are two typical network models. Most of existing works based on flow-level models focus on the LNC model due to its favorable properties and elegant solution. In addition to the formulation and solution in LNC model, in this paper, we also propose corresponding formulation and solution in LC model.(3) We propose a GCC-CSA algorithm to tackle the joint optimization problem. We decouple the complex MINLP problem into two interrelated subproblems. The CSA algorithm is proposed to find the optimal user association in a given content placement situation and the GCC algorithm is proposed to update the content placement. Some properties of these algorithms are also proved.The rest of this paper is organized as follows. Section2 constructs the LNC and LC models for the cache-enabled HCNs. Section 3 formulates the joint optimization of cache placement and user association as an MINLP problem. In Section 4, we present the GCC-CSA algorithm in LNC and LC models, respectively. Section 5 defines two performance metrics, average delay and occupied backhaul data rates, to evaluate the performance of the GCC-CSA algorithm. In Section 6, we give the implementation details and complexity analysis. Section 7 compares the performance of the proposed algorithm with that of other schemes through simulations. Finally, Section 8 concludes this paper.


## 1.1. Related Work

Many studies focus on the performance analysis of cache-enabled communication networks. In [13], the performance of a coded caching scheme is analyzed from the perspective of information theory. The work of [14] contrasts the cache-enabled device-to-device (D2D) content delivery with other alternative approaches and demonstrates its superiority. The authors of [15] investigate the scaling law of link rates with respect to some network size parameters in a cache-enabled wireless network and analyze the sustainability of this network. Using tools from stochastic geometry, [16] derives the expressions of outage probability and average delivery rate in a cache-enabled small cell network and analyzes the impacts of some network parameters on the system performance. Likewise, Yanget al. [17] deduce the outage probability and average ergodic rate in cache-enabled HCNs. Reference [18] investigates the energy efficiency of the cache-enabled wireless access networks and analyzes the effects of some factors on it.Generally, the content delivery in cache-enabled networks consists of two phases [13]: content placement phase and content delivery phase. In the content placement phase, some strategic contents are prefetched via backhaul links and cached at BSs during off-peak hours. In the context of D2D networks, contents can also be predownloaded from BSs to devices and cached at devices. The content placement schemes are crucial to the performance of cache-enabled networks and are studied extensively. In [19], the content placement problem is formulated as maximizing a monotone submodular function over matroid constraints and a greedy algorithm is proposed to solve it. Reference [20] proposes a distributed belief propagation algorithm to solve the content placement problem, which is aimed at minimizing the download latency. Taking into account BS cooperation and the propagation delay in backhaul links, Penget al. [21] propose a low-complexity algorithm to optimize the caching placement strategy. The above-mentioned content placement schemes are all implemented in concrete network scenarios, and the outputs of these schemes are caching states of given contents at specific BSs or devices. These schemes are termed deterministic caching policies. Another line of work focuses on the probabilistic caching policy, which optimizes a caching distribution for a group of cache-enabled nodes. These studies often model the networks based on stochastic geometry and find the caching policies that optimize the derived performance metrics. In [22], an optimal probabilistic caching policy is proposed to maximize the content hit probability, which can be defined based on either signal-to-interference-plus-noise ratio (SINR) model or Boolean model. Reference [23] proposes the tier-level content placement policies in HCNs. Taking into consideration millimeter-wave and full-duplex communications, [24] proposes a content dissemination mechanism based on proactive content fetching in cache-enabled full-duplex D2D networks and analyzes its performance from an evolutionary perspective.After contents have been cached at BSs and/or devices, content delivery schemes direct how to deliver the requested contents to users, e.g., routing, resource allocation, transmission schemes, and so on. In [25], the cache-aware user association problem is formulated as a one-to-many game and the objective is to minimize the backhaul usage at each SBS. By leveraging both physical and social characteristics, [26] jointly optimizes user pairing, channel allocation and power control in cache-enabled D2D networks. Chenget al. [27] propose three power allocation algorithms with different objectives in cache-aided small cell networks with limited backhaul. In a given caching situation, [28] proposes a distributed relaxing-rounding algorithm to jointly optimize user association and resource allocation in small cell networks. Reference [29] studies the multicast scheduling in cache-enabled wireless networks. By formulating the optimization problem as a Markov decision process, the authors analyze the structure of the optimal policy and propose a low-complexity suboptimal policy.The performance of content-centric networking paradigm highly depends on the cooperation between content placement and content delivery. Content placement determines the upper bound of the performance of content delivery, and content delivery is implemented in a given content placement situation. Joint optimization of content placement and content delivery takes into account the interaction between these two aspects and can improve the performance dramatically compared with separate approaches. Reference [30] formulates the joint routing and caching problem as a variant of the facility location problem, and proposes an approximation algorithm to solve this NP-hard problem. In [31], the joint optimization of request routing and content caching in a network with given topology is investigated. The authors propose approximate solutions for this problem in congestion-insensitive and congestion-sensitive models, respectively. In [32], the authors develop the optimal cooperative content caching and delivery policy in a network where both BSs and devices have cache capacity. The work in [33] jointly optimizes caching, routing, and channel assignment in a collaborative small cell networks, in which network coding is applied to enable multiple BSs to cooperatively transmit contents to a user. Reference [34] considers multicasting in cache-enabled HCNs and optimizes the content caching at different tiers to maximize the successful transmission probability. The authors of [35] design a probabilistic caching policy and a random scheduling policy to maximize the successful offloading probability in cache-enabled D2D networks.


## 1.2. Motivation, Contributions, and Organization

Although the joint optimization of content placement and content delivery has been investigated extensively in the literature, there are three important issues that are not considered in the state-of-the-art researches, as specified in the following.First, the timescale of content placement is much larger than that of content delivery. The rate of content placement should accord with the variation of content library and the content popularity distribution over it, which can be deemed constant during a few days [7]. The timescale of content delivery, which is affected by user mobility and user activity, ranges from seconds to minutes. Existing works, such as [32, 33, 36, 37], often optimize content placement at the timescale of content delivery; i.e., the content placement is designed based on a snapshot of a network with given user distribution. When user distribution changes, the previously derived content placement scheme is no longer optimal and it should be updated based on the new user distribution. Frequent content replacement due to user mobility and user activity makes the backhaul links congested, and the advantages of caching diminish or even become negative. Moreover, because of the combinatorial characteristic of content placement problems, their solutions often have relatively high complexity, and they are not practicable in a highly dynamic scenario.Second, the local content popularity often differs from the general content popularity. Content popularity distribution is a holistic statistical measure over a large area, and it may obscure meaningful difference in content popularity among small regions. References [38, 39] have verified this point based on analysis of the real YouTube datasets. Most current researches simply assume identical content request probabilities among all the users, and neglect the geographic locality of user interests.Third, the spatial traffic distribution is uneven over a large area. Due to the unequal population sizes in different regions and the difference in user behaviors, the spatial traffic distribution exhibits evident heterogeneity [40, 41]. The traffic demand in hot-spots is much larger than that in suburbs. In existing works, especially the ones in which models are constructed based on stochastic geometry, such as [22–24, 34, 35], the traffic demand is uniformly distributed. This setting differs from real situation and the performance of these approaches will be degraded in practical application.For addressing the above challenges, in this paper, we formulate a framework for joint optimization of content placement and user association in cache-enabled HCNs based on flow-level models [42, 43]. In the flow-level models, networks are modeled as queuing systems, in which BSs correspond to servers and user requests correspond to flows to be served by these servers. Different from traditional snapshot models, flow-level models focus on the spatial traffic demand distribution during a time period instead of the locations and demands of individual users at a certain moment. With the help of flow-level models, we jointly optimize content placement and user association based on the aggregated traffic demand during a long time period rather than instantaneous traffic demand. There are two kinds of flow-level models proposed in the literature: load-non-coupled (LNC) model [42] and load-coupled (LC) model [44]. In the LNC model, the intercell interference is assumed to be static, while, in the LC model, the intercell interference interacts with the loads of other BSs. In this paper, we propose a greedy content caching and content-level selective association (GCC-CSA) algorithm in LNC and LC model, respectively, for joint optimization of content placement and user association in cache-enabled HCNs. The content-level spatial traffic distribution is modeled to simulate the difference in content popularity among different regions. The superposition of all the content-level spatial traffic distributions forms the overall spatial traffic distribution. This joint optimization problem is formulated as a mixed integer nonlinear programming (MINLP) problem and its objective is to minimize the average delay of a typical flow. This formulation takes into account the limited backhaul capacity of SBSs and its effect on the achievable data rate of each content. For tackling this problem, we decouple it into two interrelated subproblems. First, we propose a CSA algorithm to optimize user association in a given content placement situation. The requests for different contents at the same location are allowed to be served by different BSs due to different caching states of these contents at nearby BSs. Second, we propose a GCC algorithm to add the content that yields the maximum reduction in the value of cost function to each BS in a given user association situation. These two algorithms are alternately executed until the caches of all the BSs are filled to capacity. The derived content-level selective user association takes effect unless the content-level spatial traffic distribution changes, which means that user association is optimized at the timescale of content placement.Our main contributions are summarized as follows.(1) We formulate the joint optimization of content placement and user association based on flow-level models. In this formulation, content-level spatial traffic distribution is modeled to simulate the locality of content popularity and the heterogeneity of spatial traffic distribution, and user association is optimized at the timescale of content placement. To the best of our knowledge, this is the first work that addresses all the issues summarized above.(2) We jointly optimize content placement and user association in LNC and LC model, respectively. LNC model and LC model are two typical network models. Most of existing works based on flow-level models focus on the LNC model due to its favorable properties and elegant solution. In addition to the formulation and solution in LNC model, in this paper, we also propose corresponding formulation and solution in LC model.(3) We propose a GCC-CSA algorithm to tackle the joint optimization problem. We decouple the complex MINLP problem into two interrelated subproblems. The CSA algorithm is proposed to find the optimal user association in a given content placement situation and the GCC algorithm is proposed to update the content placement. Some properties of these algorithms are also proved.The rest of this paper is organized as follows. Section2 constructs the LNC and LC models for the cache-enabled HCNs. Section 3 formulates the joint optimization of cache placement and user association as an MINLP problem. In Section 4, we present the GCC-CSA algorithm in LNC and LC models, respectively. Section 5 defines two performance metrics, average delay and occupied backhaul data rates, to evaluate the performance of the GCC-CSA algorithm. In Section 6, we give the implementation details and complexity analysis. Section 7 compares the performance of the proposed algorithm with that of other schemes through simulations. Finally, Section 8 concludes this paper.


## 2. System Model

We consider the downlink transmission in a cache-enabled HCN. A geographic areaL
⊂
R
2 is covered by a set of BSs M
=
1,2
,
…
,
M, which includes MBSs and SBSs. M
M and M
S denote the set of MBSs and SBSs, respectively. For alleviating congestion in limited backhaul links, each SBS j
∈
M
S is equipped with a storage unit with capacity s
j to cache strategic contents. Since MBSs are often equipped with high-capacity backhaul links, we do not consider caching at MBSs in this paper. The total transmission bandwidth is W. The transmit power and backhaul capacity of BS i
∈
M are denoted by P
i and B
i, respectively.In a certain time period, all the contents possibly requested by users inL constitute a file library F
=
1,2
,
…
,
F. The size of content f
∈
F is denoted by v
f. According to statistical analysis [5, 6], the probability that a certain content is requested in L can be modeled by Zipf distribution. If these contents are sorted according to their popularity in descending order, the probability that the f-th content is requested is given by(1)
q
f
=
f
-
z
∑
k
=
1
F
k
-
z
,
f
=
1,2
,
…
,
F
,where z
≥
0 characterizes the skewness of Zipf distribution. A large z means that a small number of popular contents account for most content requests. In the sequel, contents and files are used interchangeably.In the flow-level model, requests for contentf are assumed to follow an inhomogeneous Poisson point process with arrival rate per unit area λ
f
x at location x
∈
L. We assume that the Poisson point processes with respect to all the contents are independent from each other. According to superposition theorem, the process characterizing requests generated at x is also a Poisson process, and its intensity is λ
x
=
∑
f
∈
F
λ
f
x. The probability that f is requested at x is obtained as p
f
x
=
λ
f
x
/
λ
x, and the probability that f is requested in L, p
f
,
L, is calculated by(2)
p
f
,
L
=
∫
L
λ
f
x
d
x
∫
L
λ
x
d
x
.Obviously, p
f
,
L follow Zipf distribution. The content request probabilities in a subset L
′
⊂
L also follow Zipf distribution, but the order of contents and (or) the skewness parameter may change because of locality of content popularity. The traffic density of f at x, γ
f
x, is defined as the average required data rate of f at x per unit area, and it is obtained as γ
f
x
=
v
f
λ
f
x. In other words, γ
f
x is the average required amount of data with respect to f at x per unit area per unit time, and it characterizes the content-level spatial traffic distribution. The traffic density at x is simply given by γ
x
=
∑
f
∈
F
γ
f
x and it captures the overall spatial traffic variability.According to Shannon’s formula, the radio link data rate from BSi to a device located at x is c
i
x
=
W
log
2
⁡
1
+
η
i
x. η
i
x denotes the SINR experienced by a device at x with respect to BS i, and it is given by(3)
η
i
x
=
P
i
g
i
x
I
i
x
+
σ
2
,where g
i
x is the channel gain from BS i to location x, I
i
x is the interference received from other BSs except BS i, σ
2 is the power of background noise. Since the data rate is evaluated at the timescale of content placement, which is much larger than the coherence time of wireless channels, fast fading is not contained in g
i
x.When a data flow requesting contentf at location x is served by BS i, the load density of BS i at x with respect to f is defined as(4)
φ
i
,
f
x
=
γ
f
x
c
i
,
f
x
,where(5)
c
i
,
f
x
≜
d
i
,
f
c
i
x
+
1
-
d
i
,
f
min
⁡
c
i
x
,
B
idenotes the achievable data rate of f from BS i to x. d
i
,
f is a binary variable indicating whether BS i stores f. When d
i
,
f
=
1, content f is cached at BS i and it can be transmitted to the receiver without using the backhaul link. In this case, the achievable data rate of f from BS i to x is the data rate in the radio link. If d
i
,
f
=
0, BS i does not store f and content f must be retrieved via the backhaul link. Accordingly, the achievable data rate of f from BS i is limited by backhaul capacity B
i. The physical meaning of φ
i
,
f
x is the fraction of time required to deliver traffic density γ
f
x from BS i to x in unit time.Letδ
i
,
f
x denote the probability that a data flow requesting content f at location x is routed to BS i. Of course we have δ
i
,
f
x
∈
0,1 and ∑
i
∈
M
δ
i
,
f
x
=
1 for any f and x. This definition allows content-level selective association and it contains traditional user association policies that are insensitive to requested contents. Base on φ
i
,
f
x and δ
i
,
f
x, the load of BS i can be expressed as(6)
ρ
i
=
min
⁡
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
x
d
x
,
1
-
ε
=
min
⁡
∑
f
∈
F
∫
L
φ
i
,
f
x
δ
i
,
f
x
d
x
,
1
-
ε
=
min
⁡
∑
f
∈
F
ρ
i
,
f
,
1
-
ε
,where ε is an arbitrarily small positive constant and it is introduced to avoid some intractable and trivial situations in the following formulation and solution. According to the above definition, ρ
i can be interpreted as the total fraction of time needed for BS i to serve all the associated flows in unit time, which cannot be larger than 1.Givenδ
i
,
f
x, the arrival process of data flows to BS i follows Poisson process with arrival rate λ
i
=
∫
L
∑
f
∈
F
λ
f
x
δ
i
,
f
x
d
x. If multiple flows associated with a BS are scheduled in a round robin manner, the BS can be modeled as an M/G/1 multiclass processor sharing (MCPS) queue [45]. Multiclass means that users at different locations receive different data rates depending on channel conditions and caching states, and processor sharing means that the associated flows are scheduled in a round robin manner.


### 2.1. Load-Non-Coupled Model

In the LNC model, the interference received by a device is assumed to be static and it is independent of the activity of other BSs. This assumption is reasonable in a system with fractional frequency reuse or enhanced intercell interference cancellation. When these techniques are applied, the intercell interference itself and its variation is reasonably negligible [42]. In this model, I
i
x can be calculated as I
i
x
=
η
∑
j
≠
i
P
j
g
j
x, where η
∈
0,1 characterizes the average received interference.According to definition in (6), the feasible set of ρ
=
ρ
1
,
ρ
2
,
…
,
ρ
M
T in the LNC model is obtained as(7)
P
N
C
=
ρ
ρ
i
=
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
x
d
x
,
0
≤
ρ
i
≤
1
-
ε
,
∑
i
∈
M
δ
i
,
f
x
=
1
,
0
≤
δ
i
,
f
x
≤
1
,
∀
i
∈
M
,
∀
x
∈
L
,
∀
f
∈
F
.With given routing probabilities δ
i
,
f
x, the load of BS i is independent of the loads of other BSs, thus this model is termed load-non-coupled model. P
N
C has the following property.Lemma 1.
P
N
C is a convex set.Proof.
Assumeρ
1
,
ρ
2
∈
P
N
C and ρ
1
≠
ρ
2. For all i
∈
M, we have ρ
i
1
=
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
1
x
d
x and ρ
i
2
=
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
2
x
d
x. δ
i
,
f
1
x and δ
i
,
f
2
x are corresponding routing probabilities of ρ
1 and ρ
2, respectively. Let ρ be a convex combination of ρ
1 and ρ
2. Given θ
∈
0,1, for all i
∈
M, we have(8)
ρ
i
=
θ
ρ
i
1
+
1
-
θ
ρ
i
2
=
θ
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
1
x
d
x
+
1
-
θ
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
2
x
d
x
=
∫
L
∑
f
∈
F
φ
i
,
f
x
θ
δ
i
,
f
1
x
+
1
-
θ
δ
i
,
f
2
x
d
x
=
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
x
d
x
.
ρ and its routing probabilities δ
i
,
f
x satisfy all conditions in (7). Thus ρ
∈
P
N
C and P
N
C is a convex set.


### 2.2. Load-Coupled Model

In a cellular network with frequency reuse factor of 1, all the BSs work on the same frequency band. In this scenario, the interference received by a user varies considerably depending on the activity of other BSs. It varies at the timescale of flow dynamics and accurately modeling these correlations is intractable [44]. For tackling this issue, Fehskeet al. [46] propose to model the dynamic interference by the time-averaged interference. If the load of BS i is treated as the probability that BS i is transmitting, the SINR can be expressed as(9)
η
i
x
,
ρ
=
P
i
g
i
x
∑
j
∈
M
,
j
≠
i
ρ
j
P
j
g
j
x
+
σ
2
,where ∑
j
∈
M
,
j
≠
i
ρ
j
P
j
g
j
x is the average interference in a long time period and it replaces the instantaneous interference at any moment in this period. Note that η
i
x
,
ρ relates to the loads of all BSs except BS i. The radio link data rate in the LC model is c
i
x
,
ρ
=
W
log
2
⁡
1
+
η
i
x
,
ρ and the load density of BS i at x with respect to f is written as(10)
φ
i
,
f
x
,
ρ
=
γ
f
x
c
i
,
f
x
,
ρ
,where(11)
c
i
,
f
x
,
ρ
≜
d
i
,
f
c
i
x
,
ρ
+
1
-
d
i
,
f
min
⁡
c
i
x
,
ρ
,
B
i
.Similarly, the feasible set of ρ in the LC model is given by(12)
P
C
=
ρ
ρ
i
=
∫
L
∑
f
∈
F
φ
i
,
f
x
,
ρ
δ
i
,
f
x
d
x
,
0
≤
ρ
i
≤
1
-
ε
,
∑
i
∈
M
δ
i
,
f
x
=
1
,
0
≤
δ
i
,
f
x
≤
1
,
∀
i
∈
M
,
∀
x
∈
L
,
∀
f
∈
F
.Since ρ
i is derived based on η
i
x
,
ρ, it is coupled with the loads of all the other BSs. Let S
i
ρ
=
min
⁡
∫
L
∑
f
∈
F
φ
i
,
f
x
,
ρ
δ
i
,
f
x
d
x
,
1
-
ε and S
ρ
=
S
1
ρ
,
S
2
ρ
,
…
,
S
M
ρ
T; then a load vector ρ
∈
P
C must be a fixed point of S
∙; i.e., ρ
=
S
ρ. For given routing probabilities δ
i
,
f
x and caching states d
i
,
f, we can find a unique fixed point in 0,1
M according to Theorem 1 in [46].


## 2.1. Load-Non-Coupled Model

In the LNC model, the interference received by a device is assumed to be static and it is independent of the activity of other BSs. This assumption is reasonable in a system with fractional frequency reuse or enhanced intercell interference cancellation. When these techniques are applied, the intercell interference itself and its variation is reasonably negligible [42]. In this model, I
i
x can be calculated as I
i
x
=
η
∑
j
≠
i
P
j
g
j
x, where η
∈
0,1 characterizes the average received interference.According to definition in (6), the feasible set of ρ
=
ρ
1
,
ρ
2
,
…
,
ρ
M
T in the LNC model is obtained as(7)
P
N
C
=
ρ
ρ
i
=
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
x
d
x
,
0
≤
ρ
i
≤
1
-
ε
,
∑
i
∈
M
δ
i
,
f
x
=
1
,
0
≤
δ
i
,
f
x
≤
1
,
∀
i
∈
M
,
∀
x
∈
L
,
∀
f
∈
F
.With given routing probabilities δ
i
,
f
x, the load of BS i is independent of the loads of other BSs, thus this model is termed load-non-coupled model. P
N
C has the following property.Lemma 1.
P
N
C is a convex set.Proof.
Assumeρ
1
,
ρ
2
∈
P
N
C and ρ
1
≠
ρ
2. For all i
∈
M, we have ρ
i
1
=
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
1
x
d
x and ρ
i
2
=
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
2
x
d
x. δ
i
,
f
1
x and δ
i
,
f
2
x are corresponding routing probabilities of ρ
1 and ρ
2, respectively. Let ρ be a convex combination of ρ
1 and ρ
2. Given θ
∈
0,1, for all i
∈
M, we have(8)
ρ
i
=
θ
ρ
i
1
+
1
-
θ
ρ
i
2
=
θ
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
1
x
d
x
+
1
-
θ
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
2
x
d
x
=
∫
L
∑
f
∈
F
φ
i
,
f
x
θ
δ
i
,
f
1
x
+
1
-
θ
δ
i
,
f
2
x
d
x
=
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
x
d
x
.
ρ and its routing probabilities δ
i
,
f
x satisfy all conditions in (7). Thus ρ
∈
P
N
C and P
N
C is a convex set.


## 2.2. Load-Coupled Model

In a cellular network with frequency reuse factor of 1, all the BSs work on the same frequency band. In this scenario, the interference received by a user varies considerably depending on the activity of other BSs. It varies at the timescale of flow dynamics and accurately modeling these correlations is intractable [44]. For tackling this issue, Fehskeet al. [46] propose to model the dynamic interference by the time-averaged interference. If the load of BS i is treated as the probability that BS i is transmitting, the SINR can be expressed as(9)
η
i
x
,
ρ
=
P
i
g
i
x
∑
j
∈
M
,
j
≠
i
ρ
j
P
j
g
j
x
+
σ
2
,where ∑
j
∈
M
,
j
≠
i
ρ
j
P
j
g
j
x is the average interference in a long time period and it replaces the instantaneous interference at any moment in this period. Note that η
i
x
,
ρ relates to the loads of all BSs except BS i. The radio link data rate in the LC model is c
i
x
,
ρ
=
W
log
2
⁡
1
+
η
i
x
,
ρ and the load density of BS i at x with respect to f is written as(10)
φ
i
,
f
x
,
ρ
=
γ
f
x
c
i
,
f
x
,
ρ
,where(11)
c
i
,
f
x
,
ρ
≜
d
i
,
f
c
i
x
,
ρ
+
1
-
d
i
,
f
min
⁡
c
i
x
,
ρ
,
B
i
.Similarly, the feasible set of ρ in the LC model is given by(12)
P
C
=
ρ
ρ
i
=
∫
L
∑
f
∈
F
φ
i
,
f
x
,
ρ
δ
i
,
f
x
d
x
,
0
≤
ρ
i
≤
1
-
ε
,
∑
i
∈
M
δ
i
,
f
x
=
1
,
0
≤
δ
i
,
f
x
≤
1
,
∀
i
∈
M
,
∀
x
∈
L
,
∀
f
∈
F
.Since ρ
i is derived based on η
i
x
,
ρ, it is coupled with the loads of all the other BSs. Let S
i
ρ
=
min
⁡
∫
L
∑
f
∈
F
φ
i
,
f
x
,
ρ
δ
i
,
f
x
d
x
,
1
-
ε and S
ρ
=
S
1
ρ
,
S
2
ρ
,
…
,
S
M
ρ
T; then a load vector ρ
∈
P
C must be a fixed point of S
∙; i.e., ρ
=
S
ρ. For given routing probabilities δ
i
,
f
x and caching states d
i
,
f, we can find a unique fixed point in 0,1
M according to Theorem 1 in [46].


## 3. Problem Formulation

We aim to find the optimal content placement schemed
i
,
f and user association policy δ
i
,
f
x that minimize the average content delivery delay in a cache-enabled HCN. Although routing probabilities δ
i
,
f
x describe user association in a probabilistic manner, the values of optimal routing probabilities are binary under given caching states, as shown in Section 4. In the M/G/1 MCPS queue, the average number of flows at BS i is given by E
N
i
=
ρ
i
/
1
-
ρ
i [47], and the total number of flows at all BSs is ∑
i
∈
M
ρ
i
/
1
-
ρ
i. According to Little’s formula, minimizing the average number of flows in a BS is equivalent to minimizing the average delay of a typical flow in this BS. For minimizing the average delay of all flows, the joint optimization of content placement and user association can be formulated as(13)
m
i
n
ρ
,
D
f
ρ
=
∑
i
∈
M
1
1
-
ρ
i
s.t.
ρ
∈
P
,
D
v
≤
s
.Because 1
/
1
-
ρ
i
=
ρ
i
/
1
-
ρ
i
+
1, minimizing ∑
i
∈
M
ρ
i
/
1
-
ρ
i is equivalent to minimizing the cost function f
ρ. P denotes P
N
C or P
C depending on whether loads are coupled. D
=
d
i
,
f
M
×
F denotes the caching state of each file at each BS, v
=
v
1
,
v
2
,
…
,
v
F
T and s
=
s
1
,
s
2
,
…
,
s
M
T. The second constraint ensures that the total size of cached files at each BS cannot exceed corresponding cache capacity. Due to the correlation between ρ and δ
i
,
f
x, we can obtain the optimal content-level selective user association during the course of finding the optimal ρ. The details are presented in Section 4Problem (13) belongs to MINLP problems and it is NP-hard. If D is given, however, this problem degenerates into a user association problem, which is similar to the ones studied in [42, 44]. In the following section, we present the proposed GCC-CSA algorithm to solve problem (13) in LNC model and LC model, respectively.


## 4. GCC-CSA Algorithm

In this section, we present the GCC-CSA algorithm in LNC model and LC model, respectively. The GCC-CSA algorithm is an iterative algorithm, and each iteration is composed of two steps: CSA and GCC. In the CSA step, the optimal user association is derived under given caching states. Based on the derived user association results, the GCC step adds the file that yields the maximum cost reduction to each BS. Beginning with empty caches, these two steps are alternately executed until all the caches cannot accommodate any more contents.


### 4.1. Load-Non-Coupled Model

At first, we find the optimal user association under given caching states. In the LNC model, givenD, problem (13) is simplified as the following form:(14)
m
i
n
ρ
f
ρ
=
∑
i
∈
M
1
1
-
ρ
i
s.t.
ρ
∈
P
N
C
.Inspired by the work in [42], we first propose a CSA algorithm to solve problem (14), as shown in Algorithm 1, and then prove its optimality.Algorithm 1:The CSA algorithm for solving problem (14).
Initialization:
D, small positive constant ε and ξ, μ
>
ξ, stepsize β
∈
0,1, ρ
0
∈
0,1
-
ε
M, k
=
0
while
μ
>
ξ
do
for all location x
∈
L and content f
∈
F, the flow requesting f at x connects to BS
i
f
k
x
=
arg
⁡
max
j
∈
M
⁡
c
j
,
f
x
1
-
ρ
j
k
2;
for all BS i
∈
M and content f
∈
F, calculate the coverage area of BS i with respect to f
L
i
,
f
k
=
x
∈
L
∣
i
=
arg
⁡
max
j
∈
M
⁡
c
j
,
f
x
1
-
ρ
j
k
2;
for all BS i
∈
M, calculate its new load T
i
ρ
k
=
min
⁡
∑
f
∈
F
∫
L
i
,
f
k
φ
i
,
f
x
d
x
,
1
-
ε;
ρ
k
+
1
=
β
ρ
k
+
1
-
β
T
ρ
k;
μ
=
ρ
k
+
1
-
ρ
k
2
,
k
≔
k
+
1;
end while
Outputs:the optimal load ρ
∗
=
ρ
k and the optimal coverage area L
i
,
f
∗
=
L
i
,
f
k for all i
∈
M and f
∈
FThe following theorem states the convergence of Algorithm1 and the optimality of the output.Theorem 2.
In the LNC model, the sequenceρ
k derived from Algorithm 1 converges to the fixed point of ρ
=
T
ρ, and it is the unique optimal solution of problem (14).Proof.
We first prove that the fixed point ofρ
=
T
ρ, denoted by ρ
∗, is the unique optimal solution of problem (14). Since P
N
C is a convex set and f
ρ is a convex function, problem (14) is a convex optimization problem. Let δ
i
,
f
∗
x and δ
i
,
f
x be the routing probabilities associated with ρ
∗ and ∀
ρ
∈
P
N
C, respectively; then we have(15)
∇
f
ρ
∗
,
ρ
-
ρ
∗
=
∑
i
∈
M
1
1
-
ρ
i
∗
2
ρ
i
-
ρ
i
∗
=
∑
i
∈
M
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
x
d
x
-
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
∗
x
d
x
1
-
ρ
i
∗
2
=
∑
i
∈
M
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
x
-
δ
i
,
f
∗
x
d
x
1
-
ρ
i
∗
2
=
∫
L
∑
f
∈
F
γ
f
x
∑
i
∈
M
δ
i
,
f
x
-
δ
i
,
f
∗
x
c
i
,
f
x
1
-
ρ
i
∗
2
d
x
.From Algorithm 1, δ
i
,
f
∗
x
=
1
i
=
arg
⁡
max
j
∈
M
⁡
c
j
,
f
x
1
-
ρ
j
∗
2; thus ∇
f
ρ
∗
,
ρ
-
ρ
∗
≥
0. According to the optimality condition of convex optimization problem [48], ρ
∗ is the optimal solution of problem (14). Since f
ρ is a strictly convex function, the optimal solution of (14) is unique, and so is the fixed point of ρ
=
T
ρ.
Following the similar steps in (15), we can conclude ∇
f
ρ
,
T
ρ
-
ρ
<
0 for ∀
ρ
∈
P
N
C and ρ
≠
ρ
∗. In other words, T
ρ gives a descent direction and f
ρ
k
+
1
<
f
ρ
k with proper β. Since f
ρ is a continuous function on a compact set, f
ρ
k must converge to its minimum value f
ρ
∗. If f
ρ
k converges to some value that is larger than f
ρ
∗, T
ρ will generate a descent direction, and the function value will decrease. Thus f
ρ
k must converge to f
ρ
∗, and ρ
k must converge to ρ
∗.Although user association is defined as probabilities in (7), Algorithm 1 shows that the optimal user association is deterministic. L
i
,
f
∗ indicates the coverage area of BS i with respect to content f, and the coverage areas associated with different contents may be different from each other depending on the caching states and backhaul capacity.Given certainD, we can obtain the optimal load ρ
∗ and the optimal coverage area L
i
,
f
∗ according to Algorithm 1. Thus, for any BS i
∈
M, we have(16)
ρ
i
∗
=
∑
f
∈
F
∫
L
i
,
f
∗
γ
f
x
d
i
,
f
c
i
x
+
1
-
d
i
,
f
min
⁡
c
i
x
,
B
i
d
x
=
∑
f
∈
F
ρ
i
,
f
∗
.For a content f with d
i
,
f
=
0, ρ
i
,
f
∗
=
∫
L
i
,
f
∗
(
γ
f
x
/
min
⁡
c
i
x
,
B
i
)
d
x. If d
i
,
f is changed from 0 to 1 and other elements in D remain unchanged, with the same coverage L
i
,
f
∗, the new load of BS i with respect to f is ρ
~
i
,
f
=
∫
L
i
,
f
∗
(
γ
f
x
/
c
i
x
)
d
x. Since min
⁡
c
i
x
,
B
i
≤
c
i
x, we have ρ
~
i
,
f
≤
ρ
i
,
f
∗ and the cost function also decreases. Base on this fact, we propose a GCC algorithm for content placement in an iterative manner, as shown in Algorithm 2. In the GCC algorithm, the content that achieves the maximum cost reduction is added to each BS at each iteration. After all the BSs cache new contents, the content placement scheme D is updated and Algorithm 1 is executed again to obtain the new cell coverage areas associated with the updated D. This process continues until no more contents can be cached in any BSs.Algorithm 2:GCC-CSA algorithm for solving problem (13) in LNC model.
Initialization:
D
0
=
0
M
×
F, s
~
0
=
0
M
×
1, F
-
i
,
0
=
F for all i
∈
M, G
i
,
0
=
F for all i
∈
M, t
=
0
while
i
∈
M
∣
G
i
,
t
≠
⌀
≠
⌀
do
get the optimal ρ
t
∗ and corresponding L
i
,
f
,
t
∗ under D
t according to Algorithm 1;
forall BS i
∈
j
∈
M
∣
G
j
,
t
≠
⌀
do
for all f
∈
G
i
,
t, calculate ρ
i
,
f
,
t
∗
=
∫
L
i
,
f
,
t
∗
(
γ
f
x
/
min
⁡
c
i
x
,
B
i
)
d
x and ρ
~
i
,
f
,
t
=
∫
L
i
,
f
,
t
∗
(
γ
f
x
/
c
i
x
)
d
x;
find f
i
,
t
=
arg
⁡
max
f
∈
G
i
,
t
⁡
ρ
i
,
f
,
t
∗
-
ρ
~
i
,
f
,
t;
s
~
i
,
t
+
1
=
s
~
i
,
t
+
v
f
i
,
t; % update s
~
i
,
t
F
-
i
,
t
+
1
=
F
-
i
,
t
∖
f
i
,
t, d
i
,
t
+
1
=
d
i
,
t, d
i
,
f
i
,
t
,
t
+
1
=
1; % update the cached contents of BS i
G
i
,
t
+
1
=
f
∈
F
-
i
,
t
+
1
∣
s
~
i
,
t
+
1
+
v
f
≤
s
i; % update G
i
,
t
end for
t
≔
t
+
1;
end while
get the optimalρ
t
∗ and corresponding L
i
,
f
,
t
∗ under D
t according to Algorithm 1;
Outputs:the content placement scheme D
∗
=
D
t and corresponding optimal load ρ
∗
=
ρ
t
∗In Algorithm2, s
~
t
=
s
~
1
,
t
,
s
~
2
,
t
,
…
,
s
~
M
,
t
T denotes the occupied cache capacity of these BSs at the beginning of the t-th iteration. F
-
i
,
t denotes the set of noncached contents of BS i at the beginning of the t-th iteration. G
i
,
t denotes the set of contents that can be cached at BS i at the t-th iteration. d
i
,
t denotes the i-th row vector in D
t. With given L
i
,
f
,
t
∗, the loads of a BS with respect to different contents are independent of each other, thus caching f
i
,
t at BS i produces the maximum reduction in its load. Each BS caches the content that produces the maximum reduction in its load, and the cost function f
ρ also achieves the maximum reduction at a single iteration. The following theorem gives the convergence property of Algorithm 2.Theorem 3.
The sequence of cost function valuesf
ρ
t
∗ derived from Algorithm 2 decreases monotonically.Proof.
At thet-th iteration, the optimal load ρ
t
∗ and coverage L
i
,
f
,
t
∗ are derived under D
t. With given L
i
,
f
,
t
∗, for all BS i
∈
j
∈
M
∣
G
j
,
t
≠
⌀, we have ρ
~
i
,
f
i
,
t
,
t
≤
ρ
i
,
f
i
,
t
,
t
∗. Let ρ
~
i
,
t
≜
ρ
~
i
,
f
i
,
t
,
t
+
∑
f
≠
f
i
,
t
ρ
i
,
f
,
t
∗ and ρ
~
t
=
ρ
~
1
,
t
,
ρ
~
2
,
t
,
…
,
ρ
~
M
,
t
T; then ρ
~
i
,
t
≤
ρ
i
,
t
∗ and f
ρ
~
t
≤
f
ρ
t
∗. Note that ρ
~
t is derived based on D
t
+
1 and L
i
,
f
,
t
∗. The optimal load ρ
t
+
1
∗ under D
t
+
1 must obtain the minimum value of f
ρ and f
ρ
t
+
1
∗
≤
f
ρ
~
t. Thus f
ρ
t
+
1
∗
≤
f
ρ
t
∗ and f
ρ
t
∗ is a monotonically decreasing sequence.


### 4.2. Load-Coupled Model

In the LC model with givenD, problem (13) is simplified as follows:(17)
m
i
n
ρ
f
ρ
=
∑
i
∈
M
1
1
-
ρ
i
s.t.
ρ
∈
P
C
.Problem (17) shares the same form with problem (14), and its solution can also be derived from Algorithm 1 with slight modifications that c
j
,
f
x and φ
i
,
f
x are replaced by c
j
,
f
x
,
ρ
k and φ
i
,
f
x
,
ρ
k, respectively. However, for proving the optimality of the solution derived from Algorithm 1 in LC model, P
C must have the following property [44].Property 4 (full convertibility).
P
C is said to have the property of full convertibility if for ∀
ρ
,
ρ
′
∈
P
C, there exist valid δ
~
i
,
f
x that make the following equation hold for all i
∈
M:(18)
ρ
i
=
∫
L
∑
f
∈
F
φ
i
,
f
x
,
ρ
δ
i
,
f
x
d
x
=
∫
L
∑
f
∈
F
φ
i
,
f
x
,
ρ
′
δ
~
i
,
f
x
d
x
.With the property of full convertibility, the following theorem guarantees that the solution derived from Algorithm 1 is also optimal in LC model.Theorem 5.
In the LC model, ifP
C has the property of full convertibility, then the sequence ρ
k derived from Algorithm 1 converges to the fixed point of ρ
=
T
ρ, and it is the unique optimal solution of problem (17).Proof.
This proof is similar to the proof of Theorem2. Denote by ρ
∗ the fixed point of ρ
=
T
ρ. Let δ
i
,
f
∗
x and δ
i
,
f
x be the associated routing probabilities of ρ
∗ and ∀
ρ
∈
P
C; then we have(19)
∇
f
ρ
∗
,
ρ
-
ρ
∗
=
∑
i
∈
M
1
1
-
ρ
i
∗
2
ρ
i
-
ρ
i
∗
=
∑
i
∈
M
∫
L
∑
f
∈
F
φ
i
,
f
x
,
ρ
δ
i
,
f
x
d
x
-
∫
L
∑
f
∈
F
φ
i
,
f
x
,
ρ
∗
δ
i
,
f
∗
x
d
x
1
-
ρ
i
∗
2
=
∑
i
∈
M
∫
L
∑
f
∈
F
φ
i
,
f
x
,
ρ
∗
δ
~
i
,
f
x
d
x
-
∫
L
∑
f
∈
F
φ
i
,
f
x
,
ρ
∗
δ
i
,
f
∗
x
d
x
1
-
ρ
i
∗
2
=
∑
i
∈
M
∫
L
∑
f
∈
F
φ
i
,
f
x
,
ρ
∗
δ
~
i
,
f
x
-
δ
i
,
f
∗
x
d
x
1
-
ρ
i
∗
2
=
∫
L
∑
f
∈
F
γ
f
x
∑
i
∈
M
δ
~
i
,
f
x
-
δ
i
,
f
∗
x
c
i
,
f
x
,
ρ
∗
1
-
ρ
i
∗
2
d
x
.The fourth line applies full convertibility property. Since δ
i
,
f
∗
x
=
1
i
=
arg
⁡
max
j
∈
M
⁡
c
j
,
f
x
,
ρ
∗
1
-
ρ
j
∗
2, so ∇
f
ρ
∗
,
ρ
-
ρ
∗
≥
0. Unlike P
N
C, P
C is not necessarily a convex set. According to the approach proposed in [44], for ∀
ρ
′
,
ρ
′
′
∈
P
C and ∀
θ
∈
0,1, ρ
=
θ
ρ
′
+
1
-
θ
ρ
′
′ satisfies(20)
∇
f
ρ
∗
,
ρ
-
ρ
∗
=
∇
f
ρ
∗
,
θ
ρ
′
+
1
-
θ
ρ
′
′
-
ρ
∗
=
θ
∇
f
ρ
∗
,
ρ
′
-
ρ
∗
+
1
-
θ
∇
f
ρ
∗
,
ρ
′
′
-
ρ
∗
≥
0
.Hence any ρ
∈
C
o
n
v
P
C satisfies ∇
f
ρ
∗
,
ρ
-
ρ
∗
≥
0, and the minimum value of f
ρ is achieved at ρ
∗
∈
C
o
n
v
P
C. Since f
ρ is a convex function and P
C
⊂
C
o
n
v
P
C, the minimum value of f
ρ in P
C is also achieved at ρ
∗. Since f
ρ is a strictly convex function, the optimal solution of (17) is unique, and so is the fixed point of ρ
=
T
ρ. Proving that ρ
k converges to ρ
∗ follows the same steps in the proof of Theorem 2, and they are omitted here.GivenD, the optimal load ρ
∗ and the optimal cell coverage L
j
,
f
∗ satisfies(21)
ρ
j
∗
=
∑
f
∈
F
∫
L
j
,
f
∗
γ
f
x
d
j
,
f
c
j
x
,
ρ
∗
+
1
-
d
j
,
f
min
⁡
c
j
x
,
ρ
∗
,
B
j
d
x
=
∑
f
∈
F
ρ
j
,
f
∗
,
j
=
1,2
,
…
,
M
.If a certain d
i
,
f is changed from 0 to 1, with the same coverage L
j
,
f
∗, ρ
i
∗ will probably change and it further influences the loads of other BSs in the LC model. The new load vector that makes the system stable, ρ
d
i
,
f
=
ρ
1
,
d
i
,
f
,
ρ
2
,
d
i
,
f
,
…
,
ρ
M
,
d
i
,
f
T, is obtained from the following iterative formula:(22)
ρ
j
,
d
i
,
f
k
+
1
=
T
j
ρ
d
i
,
f
k
=
min
⁡
∑
f
∈
F
∫
L
j
,
f
∗
φ
j
,
f
x
,
ρ
d
i
,
f
k
d
x
,
1
-
ε
,
j
=
1,2
,
…
,
M
,in which ρ
d
i
,
f
0
=
ρ
∗. In fact, the loads of all the BSs will decrease or remain unchanged if a new content is added to a BS, as showed later in Proposition 6. This motivates us to design a similar GCC algorithm as in LNC model. At each iteration, each SBS chooses to cache the content that produces the maximum cost reduction and the content placement is updated. The GCC-CSA algorithm in LC model is given in Algorithm 3.Algorithm 3:GCC-CSA algorithm for solving problem (13) in LC model.
Initialization:
D
0
=
0
M
×
F, s
~
0
=
0
M
×
1, F
-
i
,
0
=
F for all i
∈
M, G
i
,
0
=
F for all i
∈
M, t
=
0
while
i
∈
M
∣
G
i
,
t
≠
⌀
≠
⌀
do
get the optimal ρ
t
∗ and corresponding L
i
,
f
,
t
∗ under D
t according to Algorithm 1;
forall BS i
∈
j
∈
M
∣
G
j
,
t
≠
⌀
do
for all f
∈
G
i
,
t, calculate ρ
d
i
,
f
,
t according to (22);
find f
i
,
t
=
arg
⁡
min
f
∈
G
i
,
t
⁡
f
ρ
d
i
,
f
,
t;
s
~
i
,
t
+
1
=
s
~
i
,
t
+
v
f
i
,
t; % update s
~
i
,
t
F
-
i
,
t
+
1
=
F
-
i
,
t
∖
f
i
,
t, d
i
,
t
+
1
=
d
i
,
t, d
i
,
f
i
,
t
,
t
+
1
=
1; % update the cached contents of BS i
G
i
,
t
+
1
=
f
∈
F
-
i
,
t
+
1
∣
s
~
i
,
t
+
1
+
v
f
≤
s
i; % update G
i
,
t
end for
t
≔
t
+
1;
end while
get the optimalρ
t
∗ and corresponding L
i
,
f
,
t
∗ under D
t according to Algorithm 1;
Outputs: the content placement scheme D
∗
=
D
t and corresponding optimal load ρ
∗
=
ρ
t
∗Before proving the convergence property of Algorithm3, we present the following two propositions at first.Proposition 6.
At thet-th iteration, for any BS i
∈
j
∈
M
∣
G
j
,
t
≠
⌀ and any f
∈
G
i
,
t, the sequence ρ
d
i
,
f
,
t
k derived from (22) converges to, say ρ
d
i
,
f
,
t, and f
ρ
d
i
,
f
,
t
≤
f
ρ
t
∗.Proof.
For brevity, we omit the subscript “t” that indicates the number of iterations in this proof. At a certain iteration, for any BS i
∈
j
∈
M
∣
G
j
≠
⌀ and any f
∈
G
i, we have d
i
,
f
=
0 and ρ
i
,
f
∗
=
∫
L
i
,
f
∗
(
γ
f
x
/
min
⁡
c
i
x
,
ρ
∗
,
B
i
)
d
x. If d
i
,
f is changed to 1, according to (22), we have(23)
ρ
i
,
d
i
,
f
1
=
T
i
ρ
∗
=
min
⁡
∑
f
′
∈
F
∖
f
∫
L
i
,
f
′
∗
φ
i
,
f
′
x
,
ρ
∗
d
x
+
∫
L
i
,
f
∗
γ
f
x
c
i
x
,
ρ
∗
d
x
,
1
-
ε
≤
ρ
i
∗
.For other BS j
≠
i,(24)
ρ
j
,
d
i
,
f
1
=
T
j
ρ
∗
=
min
⁡
∑
f
′
∈
F
∫
L
j
,
f
′
∗
φ
j
,
f
′
x
,
ρ
∗
d
x
,
1
-
ε
=
ρ
j
∗
.Since the data rates of flows associated with BS i relate to the loads of other BSs rather than the load of BS i, we have(25)
ρ
i
,
d
i
,
f
2
=
T
i
ρ
d
i
,
f
1
=
min
⁡
∑
f
′
∈
F
∖
f
∫
L
i
,
f
′
∗
φ
i
,
f
′
x
,
ρ
d
i
,
f
1
d
x
+
∫
L
i
,
f
∗
γ
f
x
c
i
x
,
ρ
d
i
,
f
1
d
x
,
1
-
ε
=
ρ
i
,
d
i
,
f
1
≤
ρ
i
∗
.Since ρ
i
,
d
i
,
f
1
≤
ρ
i
∗, for other BS j
≠
i, we have(26)
ρ
j
,
d
i
,
f
2
=
T
j
ρ
d
i
,
f
1
=
min
⁡
∑
f
′
∈
F
∫
L
j
,
f
′
∗
φ
j
,
f
′
x
,
ρ
d
i
,
f
1
d
x
,
1
-
ε
≤
min
⁡
∑
f
′
∈
F
∫
L
j
,
f
′
∗
φ
j
,
f
′
x
,
ρ
∗
d
x
,
1
-
ε
=
ρ
j
,
d
i
,
f
1
.Thus we conclude ρ
d
i
,
f
2
≤
ρ
d
i
,
f
1. Assuming ρ
d
i
,
f
k
≤
ρ
d
i
,
f
k
-
1 for k
=
2,3
,
…, for BS i, we have(27)
ρ
i
,
d
i
,
f
k
+
1
=
T
i
ρ
d
i
,
f
k
=
m
i
n
∑
f
′
∈
F
\
f
∫
L
i
,
f
′
∗
φ
i
,
f
′
x
,
ρ
d
i
,
f
k
d
x
+
∫
L
i
,
f
∗
γ
f
x
c
i
x
,
ρ
d
i
,
f
k
d
x
,
1
-
ε
≤
m
i
n
∑
f
′
∈
F
∖
f
∫
L
i
,
f
′
∗
φ
i
,
f
′
x
,
ρ
d
i
,
f
k
-
1
d
x
+
∫
L
i
,
f
∗
γ
f
x
c
i
x
,
ρ
d
i
,
f
k
-
1
d
x
,
1
-
ε
=
ρ
i
,
d
i
,
f
k
,and for BS j
≠
i, we have(28)
ρ
j
,
d
i
,
f
k
+
1
=
T
j
ρ
d
i
,
f
k
=
min
⁡
∑
f
′
∈
F
∫
L
j
,
f
′
∗
φ
j
,
f
′
x
,
ρ
d
i
,
f
k
d
x
,
1
-
ε
≤
min
⁡
∑
f
′
∈
F
∫
L
j
,
f
′
∗
φ
j
,
f
′
x
,
ρ
d
i
,
f
k
-
1
d
x
,
1
-
ε
=
ρ
j
,
d
i
,
f
k
.So we get ρ
d
i
,
f
k
+
1
≤
ρ
d
i
,
f
k. Since ρ
d
i
,
f
,
t
k is lower-bounded by 0, ρ
d
i
,
f
,
t
k must converge to, say, ρ
d
i
,
f
,
t. Since ρ
d
i
,
f
,
t
≤
ρ
t
∗, f
ρ
d
i
,
f
,
t
≤
f
ρ
t
∗ is obtained.Proposition 7.
At thet-th iteration, after all the BS i
∈
j
∈
M
∣
G
j
,
t
≠
⌀ add a new content to their caches, the load vector ρ
t obtained from (22) under the updated D
t
+
1 and L
i
,
f
,
t
∗ satisfies f
ρ
t
≤
f
ρ
t
∗.Proof.
Assume that there areM
t BSs in the set j
∈
M
∣
G
j
,
t
≠
⌀. These M
t BSs update their cached contents in a certain order. We get ρ
t
,
1 according to (22) after the first BS caches a new content. According to Proposition 6, we have f
ρ
t
,
1
≤
f
ρ
t
∗. Then the second BS caches a new content (a new content has already cached at the first BS), and ρ
t
,
2 is got according to (22) with initial load vector ρ
t
,
1. Similarly, we have f
ρ
t
,
2
≤
f
ρ
t
,
1. Each BS caches a new content after the former BS, and we finally get f
ρ
t
,
M
t
≤
f
ρ
t
,
M
t
-
1. Thus we have f
ρ
t
,
M
t
≤
f
ρ
t
∗. Note that ρ
t
,
M
t is the stable load vector under the updated caching states D
t
+
1 and L
i
,
f
,
t
∗, i.e., ρ
t
,
M
t
=
ρ
t. So we have f
ρ
t
≤
f
ρ
t
∗.Based on Propositions6 and 7, the following theorem gives the convergence property of Algorithm 3.Theorem 8.
The sequencef
ρ
t
∗ derived from Algorithm 3 decreases monotonically.Proof.
At thet-th iteration, the optimal load ρ
t
∗ and coverage L
i
,
f
,
t
∗ are derived under D
t. After all the BS i
∈
j
∈
M
∣
G
j
,
t
≠
⌀ update their cached contents, the stable load vector ρ
t under D
t
+
1 and L
i
,
f
,
t
∗ satisfies f
ρ
t
≤
f
ρ
t
∗ according to Proposition 7. Note that L
i
,
f
,
t
∗ is not the optimal cell coverage associated with D
t
+
1. The optimal load vector ρ
t
+
1
∗ under D
t
+
1 satisfies f
ρ
t
+
1
∗
≤
f
ρ
t. Thus we have f
ρ
t
+
1
∗
≤
f
ρ
t
∗, and f
ρ
t
∗ is a monotonically decreasing sequence.


## 4.1. Load-Non-Coupled Model

At first, we find the optimal user association under given caching states. In the LNC model, givenD, problem (13) is simplified as the following form:(14)
m
i
n
ρ
f
ρ
=
∑
i
∈
M
1
1
-
ρ
i
s.t.
ρ
∈
P
N
C
.Inspired by the work in [42], we first propose a CSA algorithm to solve problem (14), as shown in Algorithm 1, and then prove its optimality.Algorithm 1:The CSA algorithm for solving problem (14).
Initialization:
D, small positive constant ε and ξ, μ
>
ξ, stepsize β
∈
0,1, ρ
0
∈
0,1
-
ε
M, k
=
0
while
μ
>
ξ
do
for all location x
∈
L and content f
∈
F, the flow requesting f at x connects to BS
i
f
k
x
=
arg
⁡
max
j
∈
M
⁡
c
j
,
f
x
1
-
ρ
j
k
2;
for all BS i
∈
M and content f
∈
F, calculate the coverage area of BS i with respect to f
L
i
,
f
k
=
x
∈
L
∣
i
=
arg
⁡
max
j
∈
M
⁡
c
j
,
f
x
1
-
ρ
j
k
2;
for all BS i
∈
M, calculate its new load T
i
ρ
k
=
min
⁡
∑
f
∈
F
∫
L
i
,
f
k
φ
i
,
f
x
d
x
,
1
-
ε;
ρ
k
+
1
=
β
ρ
k
+
1
-
β
T
ρ
k;
μ
=
ρ
k
+
1
-
ρ
k
2
,
k
≔
k
+
1;
end while
Outputs:the optimal load ρ
∗
=
ρ
k and the optimal coverage area L
i
,
f
∗
=
L
i
,
f
k for all i
∈
M and f
∈
FThe following theorem states the convergence of Algorithm1 and the optimality of the output.Theorem 2.
In the LNC model, the sequenceρ
k derived from Algorithm 1 converges to the fixed point of ρ
=
T
ρ, and it is the unique optimal solution of problem (14).Proof.
We first prove that the fixed point ofρ
=
T
ρ, denoted by ρ
∗, is the unique optimal solution of problem (14). Since P
N
C is a convex set and f
ρ is a convex function, problem (14) is a convex optimization problem. Let δ
i
,
f
∗
x and δ
i
,
f
x be the routing probabilities associated with ρ
∗ and ∀
ρ
∈
P
N
C, respectively; then we have(15)
∇
f
ρ
∗
,
ρ
-
ρ
∗
=
∑
i
∈
M
1
1
-
ρ
i
∗
2
ρ
i
-
ρ
i
∗
=
∑
i
∈
M
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
x
d
x
-
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
∗
x
d
x
1
-
ρ
i
∗
2
=
∑
i
∈
M
∫
L
∑
f
∈
F
φ
i
,
f
x
δ
i
,
f
x
-
δ
i
,
f
∗
x
d
x
1
-
ρ
i
∗
2
=
∫
L
∑
f
∈
F
γ
f
x
∑
i
∈
M
δ
i
,
f
x
-
δ
i
,
f
∗
x
c
i
,
f
x
1
-
ρ
i
∗
2
d
x
.From Algorithm 1, δ
i
,
f
∗
x
=
1
i
=
arg
⁡
max
j
∈
M
⁡
c
j
,
f
x
1
-
ρ
j
∗
2; thus ∇
f
ρ
∗
,
ρ
-
ρ
∗
≥
0. According to the optimality condition of convex optimization problem [48], ρ
∗ is the optimal solution of problem (14). Since f
ρ is a strictly convex function, the optimal solution of (14) is unique, and so is the fixed point of ρ
=
T
ρ.
Following the similar steps in (15), we can conclude ∇
f
ρ
,
T
ρ
-
ρ
<
0 for ∀
ρ
∈
P
N
C and ρ
≠
ρ
∗. In other words, T
ρ gives a descent direction and f
ρ
k
+
1
<
f
ρ
k with proper β. Since f
ρ is a continuous function on a compact set, f
ρ
k must converge to its minimum value f
ρ
∗. If f
ρ
k converges to some value that is larger than f
ρ
∗, T
ρ will generate a descent direction, and the function value will decrease. Thus f
ρ
k must converge to f
ρ
∗, and ρ
k must converge to ρ
∗.Although user association is defined as probabilities in (7), Algorithm 1 shows that the optimal user association is deterministic. L
i
,
f
∗ indicates the coverage area of BS i with respect to content f, and the coverage areas associated with different contents may be different from each other depending on the caching states and backhaul capacity.Given certainD, we can obtain the optimal load ρ
∗ and the optimal coverage area L
i
,
f
∗ according to Algorithm 1. Thus, for any BS i
∈
M, we have(16)
ρ
i
∗
=
∑
f
∈
F
∫
L
i
,
f
∗
γ
f
x
d
i
,
f
c
i
x
+
1
-
d
i
,
f
min
⁡
c
i
x
,
B
i
d
x
=
∑
f
∈
F
ρ
i
,
f
∗
.For a content f with d
i
,
f
=
0, ρ
i
,
f
∗
=
∫
L
i
,
f
∗
(
γ
f
x
/
min
⁡
c
i
x
,
B
i
)
d
x. If d
i
,
f is changed from 0 to 1 and other elements in D remain unchanged, with the same coverage L
i
,
f
∗, the new load of BS i with respect to f is ρ
~
i
,
f
=
∫
L
i
,
f
∗
(
γ
f
x
/
c
i
x
)
d
x. Since min
⁡
c
i
x
,
B
i
≤
c
i
x, we have ρ
~
i
,
f
≤
ρ
i
,
f
∗ and the cost function also decreases. Base on this fact, we propose a GCC algorithm for content placement in an iterative manner, as shown in Algorithm 2. In the GCC algorithm, the content that achieves the maximum cost reduction is added to each BS at each iteration. After all the BSs cache new contents, the content placement scheme D is updated and Algorithm 1 is executed again to obtain the new cell coverage areas associated with the updated D. This process continues until no more contents can be cached in any BSs.Algorithm 2:GCC-CSA algorithm for solving problem (13) in LNC model.
Initialization:
D
0
=
0
M
×
F, s
~
0
=
0
M
×
1, F
-
i
,
0
=
F for all i
∈
M, G
i
,
0
=
F for all i
∈
M, t
=
0
while
i
∈
M
∣
G
i
,
t
≠
⌀
≠
⌀
do
get the optimal ρ
t
∗ and corresponding L
i
,
f
,
t
∗ under D
t according to Algorithm 1;
forall BS i
∈
j
∈
M
∣
G
j
,
t
≠
⌀
do
for all f
∈
G
i
,
t, calculate ρ
i
,
f
,
t
∗
=
∫
L
i
,
f
,
t
∗
(
γ
f
x
/
min
⁡
c
i
x
,
B
i
)
d
x and ρ
~
i
,
f
,
t
=
∫
L
i
,
f
,
t
∗
(
γ
f
x
/
c
i
x
)
d
x;
find f
i
,
t
=
arg
⁡
max
f
∈
G
i
,
t
⁡
ρ
i
,
f
,
t
∗
-
ρ
~
i
,
f
,
t;
s
~
i
,
t
+
1
=
s
~
i
,
t
+
v
f
i
,
t; % update s
~
i
,
t
F
-
i
,
t
+
1
=
F
-
i
,
t
∖
f
i
,
t, d
i
,
t
+
1
=
d
i
,
t, d
i
,
f
i
,
t
,
t
+
1
=
1; % update the cached contents of BS i
G
i
,
t
+
1
=
f
∈
F
-
i
,
t
+
1
∣
s
~
i
,
t
+
1
+
v
f
≤
s
i; % update G
i
,
t
end for
t
≔
t
+
1;
end while
get the optimalρ
t
∗ and corresponding L
i
,
f
,
t
∗ under D
t according to Algorithm 1;
Outputs:the content placement scheme D
∗
=
D
t and corresponding optimal load ρ
∗
=
ρ
t
∗In Algorithm2, s
~
t
=
s
~
1
,
t
,
s
~
2
,
t
,
…
,
s
~
M
,
t
T denotes the occupied cache capacity of these BSs at the beginning of the t-th iteration. F
-
i
,
t denotes the set of noncached contents of BS i at the beginning of the t-th iteration. G
i
,
t denotes the set of contents that can be cached at BS i at the t-th iteration. d
i
,
t denotes the i-th row vector in D
t. With given L
i
,
f
,
t
∗, the loads of a BS with respect to different contents are independent of each other, thus caching f
i
,
t at BS i produces the maximum reduction in its load. Each BS caches the content that produces the maximum reduction in its load, and the cost function f
ρ also achieves the maximum reduction at a single iteration. The following theorem gives the convergence property of Algorithm 2.Theorem 3.
The sequence of cost function valuesf
ρ
t
∗ derived from Algorithm 2 decreases monotonically.Proof.
At thet-th iteration, the optimal load ρ
t
∗ and coverage L
i
,
f
,
t
∗ are derived under D
t. With given L
i
,
f
,
t
∗, for all BS i
∈
j
∈
M
∣
G
j
,
t
≠
⌀, we have ρ
~
i
,
f
i
,
t
,
t
≤
ρ
i
,
f
i
,
t
,
t
∗. Let ρ
~
i
,
t
≜
ρ
~
i
,
f
i
,
t
,
t
+
∑
f
≠
f
i
,
t
ρ
i
,
f
,
t
∗ and ρ
~
t
=
ρ
~
1
,
t
,
ρ
~
2
,
t
,
…
,
ρ
~
M
,
t
T; then ρ
~
i
,
t
≤
ρ
i
,
t
∗ and f
ρ
~
t
≤
f
ρ
t
∗. Note that ρ
~
t is derived based on D
t
+
1 and L
i
,
f
,
t
∗. The optimal load ρ
t
+
1
∗ under D
t
+
1 must obtain the minimum value of f
ρ and f
ρ
t
+
1
∗
≤
f
ρ
~
t. Thus f
ρ
t
+
1
∗
≤
f
ρ
t
∗ and f
ρ
t
∗ is a monotonically decreasing sequence.


## 4.2. Load-Coupled Model

In the LC model with givenD, problem (13) is simplified as follows:(17)
m
i
n
ρ
f
ρ
=
∑
i
∈
M
1
1
-
ρ
i
s.t.
ρ
∈
P
C
.Problem (17) shares the same form with problem (14), and its solution can also be derived from Algorithm 1 with slight modifications that c
j
,
f
x and φ
i
,
f
x are replaced by c
j
,
f
x
,
ρ
k and φ
i
,
f
x
,
ρ
k, respectively. However, for proving the optimality of the solution derived from Algorithm 1 in LC model, P
C must have the following property [44].Property 4 (full convertibility).
P
C is said to have the property of full convertibility if for ∀
ρ
,
ρ
′
∈
P
C, there exist valid δ
~
i
,
f
x that make the following equation hold for all i
∈
M:(18)
ρ
i
=
∫
L
∑
f
∈
F
φ
i
,
f
x
,
ρ
δ
i
,
f
x
d
x
=
∫
L
∑
f
∈
F
φ
i
,
f
x
,
ρ
′
δ
~
i
,
f
x
d
x
.With the property of full convertibility, the following theorem guarantees that the solution derived from Algorithm 1 is also optimal in LC model.Theorem 5.
In the LC model, ifP
C has the property of full convertibility, then the sequence ρ
k derived from Algorithm 1 converges to the fixed point of ρ
=
T
ρ, and it is the unique optimal solution of problem (17).Proof.
This proof is similar to the proof of Theorem2. Denote by ρ
∗ the fixed point of ρ
=
T
ρ. Let δ
i
,
f
∗
x and δ
i
,
f
x be the associated routing probabilities of ρ
∗ and ∀
ρ
∈
P
C; then we have(19)
∇
f
ρ
∗
,
ρ
-
ρ
∗
=
∑
i
∈
M
1
1
-
ρ
i
∗
2
ρ
i
-
ρ
i
∗
=
∑
i
∈
M
∫
L
∑
f
∈
F
φ
i
,
f
x
,
ρ
δ
i
,
f
x
d
x
-
∫
L
∑
f
∈
F
φ
i
,
f
x
,
ρ
∗
δ
i
,
f
∗
x
d
x
1
-
ρ
i
∗
2
=
∑
i
∈
M
∫
L
∑
f
∈
F
φ
i
,
f
x
,
ρ
∗
δ
~
i
,
f
x
d
x
-
∫
L
∑
f
∈
F
φ
i
,
f
x
,
ρ
∗
δ
i
,
f
∗
x
d
x
1
-
ρ
i
∗
2
=
∑
i
∈
M
∫
L
∑
f
∈
F
φ
i
,
f
x
,
ρ
∗
δ
~
i
,
f
x
-
δ
i
,
f
∗
x
d
x
1
-
ρ
i
∗
2
=
∫
L
∑
f
∈
F
γ
f
x
∑
i
∈
M
δ
~
i
,
f
x
-
δ
i
,
f
∗
x
c
i
,
f
x
,
ρ
∗
1
-
ρ
i
∗
2
d
x
.The fourth line applies full convertibility property. Since δ
i
,
f
∗
x
=
1
i
=
arg
⁡
max
j
∈
M
⁡
c
j
,
f
x
,
ρ
∗
1
-
ρ
j
∗
2, so ∇
f
ρ
∗
,
ρ
-
ρ
∗
≥
0. Unlike P
N
C, P
C is not necessarily a convex set. According to the approach proposed in [44], for ∀
ρ
′
,
ρ
′
′
∈
P
C and ∀
θ
∈
0,1, ρ
=
θ
ρ
′
+
1
-
θ
ρ
′
′ satisfies(20)
∇
f
ρ
∗
,
ρ
-
ρ
∗
=
∇
f
ρ
∗
,
θ
ρ
′
+
1
-
θ
ρ
′
′
-
ρ
∗
=
θ
∇
f
ρ
∗
,
ρ
′
-
ρ
∗
+
1
-
θ
∇
f
ρ
∗
,
ρ
′
′
-
ρ
∗
≥
0
.Hence any ρ
∈
C
o
n
v
P
C satisfies ∇
f
ρ
∗
,
ρ
-
ρ
∗
≥
0, and the minimum value of f
ρ is achieved at ρ
∗
∈
C
o
n
v
P
C. Since f
ρ is a convex function and P
C
⊂
C
o
n
v
P
C, the minimum value of f
ρ in P
C is also achieved at ρ
∗. Since f
ρ is a strictly convex function, the optimal solution of (17) is unique, and so is the fixed point of ρ
=
T
ρ. Proving that ρ
k converges to ρ
∗ follows the same steps in the proof of Theorem 2, and they are omitted here.GivenD, the optimal load ρ
∗ and the optimal cell coverage L
j
,
f
∗ satisfies(21)
ρ
j
∗
=
∑
f
∈
F
∫
L
j
,
f
∗
γ
f
x
d
j
,
f
c
j
x
,
ρ
∗
+
1
-
d
j
,
f
min
⁡
c
j
x
,
ρ
∗
,
B
j
d
x
=
∑
f
∈
F
ρ
j
,
f
∗
,
j
=
1,2
,
…
,
M
.If a certain d
i
,
f is changed from 0 to 1, with the same coverage L
j
,
f
∗, ρ
i
∗ will probably change and it further influences the loads of other BSs in the LC model. The new load vector that makes the system stable, ρ
d
i
,
f
=
ρ
1
,
d
i
,
f
,
ρ
2
,
d
i
,
f
,
…
,
ρ
M
,
d
i
,
f
T, is obtained from the following iterative formula:(22)
ρ
j
,
d
i
,
f
k
+
1
=
T
j
ρ
d
i
,
f
k
=
min
⁡
∑
f
∈
F
∫
L
j
,
f
∗
φ
j
,
f
x
,
ρ
d
i
,
f
k
d
x
,
1
-
ε
,
j
=
1,2
,
…
,
M
,in which ρ
d
i
,
f
0
=
ρ
∗. In fact, the loads of all the BSs will decrease or remain unchanged if a new content is added to a BS, as showed later in Proposition 6. This motivates us to design a similar GCC algorithm as in LNC model. At each iteration, each SBS chooses to cache the content that produces the maximum cost reduction and the content placement is updated. The GCC-CSA algorithm in LC model is given in Algorithm 3.Algorithm 3:GCC-CSA algorithm for solving problem (13) in LC model.
Initialization:
D
0
=
0
M
×
F, s
~
0
=
0
M
×
1, F
-
i
,
0
=
F for all i
∈
M, G
i
,
0
=
F for all i
∈
M, t
=
0
while
i
∈
M
∣
G
i
,
t
≠
⌀
≠
⌀
do
get the optimal ρ
t
∗ and corresponding L
i
,
f
,
t
∗ under D
t according to Algorithm 1;
forall BS i
∈
j
∈
M
∣
G
j
,
t
≠
⌀
do
for all f
∈
G
i
,
t, calculate ρ
d
i
,
f
,
t according to (22);
find f
i
,
t
=
arg
⁡
min
f
∈
G
i
,
t
⁡
f
ρ
d
i
,
f
,
t;
s
~
i
,
t
+
1
=
s
~
i
,
t
+
v
f
i
,
t; % update s
~
i
,
t
F
-
i
,
t
+
1
=
F
-
i
,
t
∖
f
i
,
t, d
i
,
t
+
1
=
d
i
,
t, d
i
,
f
i
,
t
,
t
+
1
=
1; % update the cached contents of BS i
G
i
,
t
+
1
=
f
∈
F
-
i
,
t
+
1
∣
s
~
i
,
t
+
1
+
v
f
≤
s
i; % update G
i
,
t
end for
t
≔
t
+
1;
end while
get the optimalρ
t
∗ and corresponding L
i
,
f
,
t
∗ under D
t according to Algorithm 1;
Outputs: the content placement scheme D
∗
=
D
t and corresponding optimal load ρ
∗
=
ρ
t
∗Before proving the convergence property of Algorithm3, we present the following two propositions at first.Proposition 6.
At thet-th iteration, for any BS i
∈
j
∈
M
∣
G
j
,
t
≠
⌀ and any f
∈
G
i
,
t, the sequence ρ
d
i
,
f
,
t
k derived from (22) converges to, say ρ
d
i
,
f
,
t, and f
ρ
d
i
,
f
,
t
≤
f
ρ
t
∗.Proof.
For brevity, we omit the subscript “t” that indicates the number of iterations in this proof. At a certain iteration, for any BS i
∈
j
∈
M
∣
G
j
≠
⌀ and any f
∈
G
i, we have d
i
,
f
=
0 and ρ
i
,
f
∗
=
∫
L
i
,
f
∗
(
γ
f
x
/
min
⁡
c
i
x
,
ρ
∗
,
B
i
)
d
x. If d
i
,
f is changed to 1, according to (22), we have(23)
ρ
i
,
d
i
,
f
1
=
T
i
ρ
∗
=
min
⁡
∑
f
′
∈
F
∖
f
∫
L
i
,
f
′
∗
φ
i
,
f
′
x
,
ρ
∗
d
x
+
∫
L
i
,
f
∗
γ
f
x
c
i
x
,
ρ
∗
d
x
,
1
-
ε
≤
ρ
i
∗
.For other BS j
≠
i,(24)
ρ
j
,
d
i
,
f
1
=
T
j
ρ
∗
=
min
⁡
∑
f
′
∈
F
∫
L
j
,
f
′
∗
φ
j
,
f
′
x
,
ρ
∗
d
x
,
1
-
ε
=
ρ
j
∗
.Since the data rates of flows associated with BS i relate to the loads of other BSs rather than the load of BS i, we have(25)
ρ
i
,
d
i
,
f
2
=
T
i
ρ
d
i
,
f
1
=
min
⁡
∑
f
′
∈
F
∖
f
∫
L
i
,
f
′
∗
φ
i
,
f
′
x
,
ρ
d
i
,
f
1
d
x
+
∫
L
i
,
f
∗
γ
f
x
c
i
x
,
ρ
d
i
,
f
1
d
x
,
1
-
ε
=
ρ
i
,
d
i
,
f
1
≤
ρ
i
∗
.Since ρ
i
,
d
i
,
f
1
≤
ρ
i
∗, for other BS j
≠
i, we have(26)
ρ
j
,
d
i
,
f
2
=
T
j
ρ
d
i
,
f
1
=
min
⁡
∑
f
′
∈
F
∫
L
j
,
f
′
∗
φ
j
,
f
′
x
,
ρ
d
i
,
f
1
d
x
,
1
-
ε
≤
min
⁡
∑
f
′
∈
F
∫
L
j
,
f
′
∗
φ
j
,
f
′
x
,
ρ
∗
d
x
,
1
-
ε
=
ρ
j
,
d
i
,
f
1
.Thus we conclude ρ
d
i
,
f
2
≤
ρ
d
i
,
f
1. Assuming ρ
d
i
,
f
k
≤
ρ
d
i
,
f
k
-
1 for k
=
2,3
,
…, for BS i, we have(27)
ρ
i
,
d
i
,
f
k
+
1
=
T
i
ρ
d
i
,
f
k
=
m
i
n
∑
f
′
∈
F
\
f
∫
L
i
,
f
′
∗
φ
i
,
f
′
x
,
ρ
d
i
,
f
k
d
x
+
∫
L
i
,
f
∗
γ
f
x
c
i
x
,
ρ
d
i
,
f
k
d
x
,
1
-
ε
≤
m
i
n
∑
f
′
∈
F
∖
f
∫
L
i
,
f
′
∗
φ
i
,
f
′
x
,
ρ
d
i
,
f
k
-
1
d
x
+
∫
L
i
,
f
∗
γ
f
x
c
i
x
,
ρ
d
i
,
f
k
-
1
d
x
,
1
-
ε
=
ρ
i
,
d
i
,
f
k
,and for BS j
≠
i, we have(28)
ρ
j
,
d
i
,
f
k
+
1
=
T
j
ρ
d
i
,
f
k
=
min
⁡
∑
f
′
∈
F
∫
L
j
,
f
′
∗
φ
j
,
f
′
x
,
ρ
d
i
,
f
k
d
x
,
1
-
ε
≤
min
⁡
∑
f
′
∈
F
∫
L
j
,
f
′
∗
φ
j
,
f
′
x
,
ρ
d
i
,
f
k
-
1
d
x
,
1
-
ε
=
ρ
j
,
d
i
,
f
k
.So we get ρ
d
i
,
f
k
+
1
≤
ρ
d
i
,
f
k. Since ρ
d
i
,
f
,
t
k is lower-bounded by 0, ρ
d
i
,
f
,
t
k must converge to, say, ρ
d
i
,
f
,
t. Since ρ
d
i
,
f
,
t
≤
ρ
t
∗, f
ρ
d
i
,
f
,
t
≤
f
ρ
t
∗ is obtained.Proposition 7.
At thet-th iteration, after all the BS i
∈
j
∈
M
∣
G
j
,
t
≠
⌀ add a new content to their caches, the load vector ρ
t obtained from (22) under the updated D
t
+
1 and L
i
,
f
,
t
∗ satisfies f
ρ
t
≤
f
ρ
t
∗.Proof.
Assume that there areM
t BSs in the set j
∈
M
∣
G
j
,
t
≠
⌀. These M
t BSs update their cached contents in a certain order. We get ρ
t
,
1 according to (22) after the first BS caches a new content. According to Proposition 6, we have f
ρ
t
,
1
≤
f
ρ
t
∗. Then the second BS caches a new content (a new content has already cached at the first BS), and ρ
t
,
2 is got according to (22) with initial load vector ρ
t
,
1. Similarly, we have f
ρ
t
,
2
≤
f
ρ
t
,
1. Each BS caches a new content after the former BS, and we finally get f
ρ
t
,
M
t
≤
f
ρ
t
,
M
t
-
1. Thus we have f
ρ
t
,
M
t
≤
f
ρ
t
∗. Note that ρ
t
,
M
t is the stable load vector under the updated caching states D
t
+
1 and L
i
,
f
,
t
∗, i.e., ρ
t
,
M
t
=
ρ
t. So we have f
ρ
t
≤
f
ρ
t
∗.Based on Propositions6 and 7, the following theorem gives the convergence property of Algorithm 3.Theorem 8.
The sequencef
ρ
t
∗ derived from Algorithm 3 decreases monotonically.Proof.
At thet-th iteration, the optimal load ρ
t
∗ and coverage L
i
,
f
,
t
∗ are derived under D
t. After all the BS i
∈
j
∈
M
∣
G
j
,
t
≠
⌀ update their cached contents, the stable load vector ρ
t under D
t
+
1 and L
i
,
f
,
t
∗ satisfies f
ρ
t
≤
f
ρ
t
∗ according to Proposition 7. Note that L
i
,
f
,
t
∗ is not the optimal cell coverage associated with D
t
+
1. The optimal load vector ρ
t
+
1
∗ under D
t
+
1 satisfies f
ρ
t
+
1
∗
≤
f
ρ
t. Thus we have f
ρ
t
+
1
∗
≤
f
ρ
t
∗, and f
ρ
t
∗ is a monotonically decreasing sequence.


## 5. Performance Metrics

As shown in (13), the objective of GCC-CSA algorithm is to minimize the average content delivery delay in a cache-enabled HCN. However, the objective function f
ρ in (13) corresponds to the total number of flows at all BSs, and it cannot be used to characterize delay in the flow-level models. For evaluating the performance of GCC-CSA algorithm in terms of delay, in this section, we define the average delay at a given location and the average delay in the whole area. In addition, we also define the occupied backhaul data rates of BSs to demonstrate the advantage of GCC-CSA algorithm in terms of decreasing backhaul load.


### 5.1. Average Delay

For ease of definition and computation, we partition the continuous areaL into massive pixels and user association policy is derived for each pixel. The traffic densities and the radio link parameters at the center of a pixel are viewed as the average traffic densities and average radio link parameters in this pixel. Let pixels be indexed by y, and let Y denote the set of all pixels. In the M/G/1 MCPS queues, the time-averaged throughout of a flow associated with BS i
f
y for content f at location y is given by c
i
f
y
,
f
y
1
-
ρ
i
f
y [49] (In the LC model, this expression is given by c
i
f
y
,
f
y
,
ρ
1
-
ρ
i
f
y). Thus, the average delay for requesting any content at location y can be obtained as(29)
E
D
∣
y
=
∑
f
∈
F
p
f
y
v
f
c
i
f
y
,
f
y
1
-
ρ
i
f
y
.Define a set Y
M
≜
y
∈
Y
∣
i
f
y
∈
M
M
,
∀
f
∈
F, and it denotes the set of locations that only connect to MBSs. The complement of Y
M is denoted by Y
S, and it denotes the set of locations that are probably associated with SBSs for requesting some contents. Apparently, Y
M
∪
Y
S
=
Y and Y
M
∩
Y
S
=
⌀. The average delay of flows at locations in Y
M and Y
S are calculated by D
-
M
=
∑
y
∈
Y
M
E
D
∣
y
/
Y
M and D
-
S
=
∑
y
∈
Y
S
E
D
∣
y
/
Y
S, respectively. The average delay of flows at all locations is calculated by D
-
=
∑
y
∈
Y
E
D
∣
y
/
Y correspondingly.


### 5.2. Occupied Backhaul Data Rates

Backhaul usage can be significantly reduced by proper content placement and user association strategies. In the flow-level models constructed in this paper, the occupied backhaul data rate of BSi is obtained as(30)
B
u
,
i
≜
∑
f
=
1
F
1
-
d
i
,
f
∫
L
i
,
f
γ
f
x
d
x
.The average occupied backhaul data rates of MBSs and SBSs are calculated by B
-
u
,
M
=
∑
i
∈
M
M
B
u
,
i
/
M
M and B
-
u
,
S
=
∑
i
∈
M
S
B
u
,
i
/
M
S, respectively.


## 5.1. Average Delay

For ease of definition and computation, we partition the continuous areaL into massive pixels and user association policy is derived for each pixel. The traffic densities and the radio link parameters at the center of a pixel are viewed as the average traffic densities and average radio link parameters in this pixel. Let pixels be indexed by y, and let Y denote the set of all pixels. In the M/G/1 MCPS queues, the time-averaged throughout of a flow associated with BS i
f
y for content f at location y is given by c
i
f
y
,
f
y
1
-
ρ
i
f
y [49] (In the LC model, this expression is given by c
i
f
y
,
f
y
,
ρ
1
-
ρ
i
f
y). Thus, the average delay for requesting any content at location y can be obtained as(29)
E
D
∣
y
=
∑
f
∈
F
p
f
y
v
f
c
i
f
y
,
f
y
1
-
ρ
i
f
y
.Define a set Y
M
≜
y
∈
Y
∣
i
f
y
∈
M
M
,
∀
f
∈
F, and it denotes the set of locations that only connect to MBSs. The complement of Y
M is denoted by Y
S, and it denotes the set of locations that are probably associated with SBSs for requesting some contents. Apparently, Y
M
∪
Y
S
=
Y and Y
M
∩
Y
S
=
⌀. The average delay of flows at locations in Y
M and Y
S are calculated by D
-
M
=
∑
y
∈
Y
M
E
D
∣
y
/
Y
M and D
-
S
=
∑
y
∈
Y
S
E
D
∣
y
/
Y
S, respectively. The average delay of flows at all locations is calculated by D
-
=
∑
y
∈
Y
E
D
∣
y
/
Y correspondingly.


## 5.2. Occupied Backhaul Data Rates

Backhaul usage can be significantly reduced by proper content placement and user association strategies. In the flow-level models constructed in this paper, the occupied backhaul data rate of BSi is obtained as(30)
B
u
,
i
≜
∑
f
=
1
F
1
-
d
i
,
f
∫
L
i
,
f
γ
f
x
d
x
.The average occupied backhaul data rates of MBSs and SBSs are calculated by B
-
u
,
M
=
∑
i
∈
M
M
B
u
,
i
/
M
M and B
-
u
,
S
=
∑
i
∈
M
S
B
u
,
i
/
M
S, respectively.


## 6. Implementation and Complexity

In this paper, the formulation of joint optimization of content placement and user association is based on the content-level spatial traffic distributionγ
f
x of each content f in a given area L. Time is divided into multiple time periods, which range from several hours to several days. The content-level spatial traffic distribution is assumed to be static during each time period, and it changes when the next time period starts. Before a time period starts, γ
f
x in the forthcoming time period should be estimated in advance. Generally, γ
f
x correlates with the content popularity distribution and spatial traffic distribution. There have been many studies on the prediction of content popularity distribution [50–52] and the analysis of spatial traffic distribution [40, 53]. With the aid of these methods, we can precisely estimate γ
f
x.Onceγ
f
x is obtained, it is imported into the GCC-CSA algorithm to derive the content placement and user association policy that take effect during the next time period. Thus, the GCC-CSA algorithm is an offline algorithm. Although the CSA algorithm is essentially a distributed online algorithm [42, 44], it must be executed at the centralized controller in our scheme. The user association policy i
f
y of each content f at each pixel y can be calculated by parallel computing, e.g., NVIDIA CUDA toolkit, to reduce the running time. The simulations in this paper are conducted by this approach.The associated BSi
f
y of a data flow depends on the requested file f and the location y. Contents can be identified by naming contents at the network layer [8]. With positioning techniques in cellular networks [54], the locations of users can also be easily obtained. Based on these techniques, when a content request arrives, it will be routed to corresponding BS with limited signaling overhead.In the following, we analyze the complexity of the GCC-CSA algorithm in LC model, and the complexity of it in LNC model can be derived similarly. At each iteration in Algorithm1, the number of operations for the first three steps is 3
Y
M
F, and the number of operations for the last two steps is 2
M. Denote by I
m
a
x the number of iterations that makes Algorithm 1 converge, then the total number of operations of Algorithm 1 is C
1
≜
I
m
a
x
3
Y
M
F
+
2
M. Denote by J
m
a
x the number of iterations that makes equation (22) converge; then the total number of operations of (22) is C
2
≜
J
m
a
x
Y
M
F. To capture the essence of the complexity of Algorithm 3, we make two assumptions: (1) all the files have the same size; (2) all the M BSs can cache S files at most. Considering the upper bound of complexity of Algorithm 3, the total number of operations of Algorithm 3 is given by S
C
1
+
M
F
C
2
+
F
M
+
1
+
C
1. After some mathematical manipulations, the complexity of the GCC-CSA algorithm in LC model is obtained as O
max
⁡
I
m
a
x
,
J
m
a
x
Y
S
M
2
F
2.


## 7. Simulation Results

In this section, we validate the performance of the proposed GCC-CSA algorithm based on the spatial traffic distribution derived from a real network. For comparison, we also evaluate the performance of another two schemes: (1) most popular caching and max-SINR association scheme, denoted by MPC-MSA, and (2) most popular caching and content-level selective association scheme, denoted by MPC-CSA. MPC means all the BSs cache the most popular contents in a given area, and it has been considered in [16, 17]. The MPC policy only considers the overall content popularity distribution, and it ignores the heterogeneity of user preference over a large area. MSA is a user association method generally implemented in the current networks, and it serves as a baseline user association scheme.


### 7.1. Simulation Setup

We consider a square area with side length 2km, as shown in Figure1. 7 MBSs and 10 SBSs are located in this area. MBSs are deployed based on hexagonal grid model with an intersite distance of 800 m. SBSs are randomly deployed in this area. The minimum intersite distance between SBS and SBS (MBS) is set to 400 m. The bandwidth is W = 10 MHz, and the noise power spectral density is -174 dBm/Hz. The spatial traffic distribution during a certain time period derived from a network operator [53] is also shown in Figure 1. The content library contains F
=
50 files. For simulating the locality of content popularity distribution, this area is partitioned into 9 regions, and the content popularity distributions in these regions are different. All these regions share the same skewness parameter but differ in the order of content popularity. For example, Content 1 is the most popular content in Region 1, but it is the fifth most popular content in Region 2. Two values of skewness parameter z
∈
0.8,1.2 are considered. All the files are assumed to have the same size, i.e., v
f = 10 MB for all f
∈
F. For conducting the experiments on computers, the whole area is divided into 200 × 200 pixels. Other simulation parameters are given in Table 1.Table 1
Simulation parameters.
Parameters
MBS
SBS
Transmit power
P
M = 43 dBm
P
S = 33 dBm
Path loss model
128.1
+
37.6
l
o
g
10
R
k
m
140.7
+
36.7
l
o
g
10
R
k
m
Backhaul capacity
B
M = 1 Gbps
B
S
∈
1,10,100 Mbps
Cache capacity (the number of contents)
s
M
=
0
s
S
∈
5,10Figure 1
The simulation scenario. Red triangles denote MBSs and red circles denote SBSs.


### 7.2. Illustration of Content-Level Selective Association

Figures2 and 3 illustrate the coverage areas associated with Content 1 and Content 2 derived from GCC-CSA algorithm in LNC model and LC model, respectively. From these figures, we can observe that the coverage areas of SBS1, SBS4 and SBS8 associated with Content 1 and Content 2 are quite different, especially in LC model. The difference in caching state of Content 1 and Content 2 results in the different coverage areas. In these two models, SBS1 and SBS8 cache Content 1 but do not cache Content 2, and SBS4 caches Content 2 but does not cache Content 1. The caching states of these two contents are identical in other SBSs. Taking SBS8 as an example, since it does not cache Content 2, the coverage area with respect to Content 2 must shrink to prevent heavy load.Figure 2
The coverage areas with respect to Content 1 and Content 2 in LNC model.s
S
=
10, z
=
0.8, and B
S = 10 Mbps.
(a)
The cell coverages w. r. t. Content 1
(b)
The cell coverages w. r. t. Content 2Figure 3
The coverage areas with respect to Content 1 and Content 2 in LC model.s
S
=
10, z
=
0.8, and B
S = 10 Mbps.
(a)
The cell coverages w. r. t. Content 1
(b)
The cell coverages w. r. t. Content 2


### 7.3. Statistical Properties of Delay

Tables2 and 3 give the average delay in the three schemes under various network configurations in LNC model and LC model, respectively. D
-
S, D
-
M, and D
- are defined in Section 5.1. We can draw the following conclusions from these tables.Table 2
The average delay in the three schemes in LNC model.
Scenario
B
S   (Mbps)
D
-
S (s)
D
-
M (s)
D
- (s)
GCC-CSA
MPC-MSA
MPC-CSA
GCC-CSA
MPC-MSA
MPC-CSA
GCC-CSA
MPC-MSA
MPC-CSA
s
S
=
5
z
=
0.8
1
12.802
160.54
14.781
2.2614
2.2710
2.2871
3.3414
13.963
3.5848
10
5.5067
6.8358
6.0531
2.1799
2.2710
2.1871
2.5060
2.6082
2.5668
100
2.9788
2.3292
2.9792
2.1559
2.2710
2.1572
2.2358
2.2753
2.2369
s
S
=
5
z
=
1.2
1
9.5583
160.66
12.890
2.2247
2.2710
2.2675
2.9620
13.972
3.3597
10
4.6681
6.1678
5.5866
2.1718
2.2710
2.1837
2.4158
2.5589
2.5176
100
2.9778
2.3284
2.9799
2.1559
2.1710
2.1571
2.2357
2.2753
2.2368
s
S
=
10
z
=
0.8
1
10.340
68.724
11.984
2.2319
2.2710
2.2507
3.0528
7.1803
3.2444
10
4.8670
5.7330
5.3061
2.1739
2.2710
2.1794
2.4373
2.5268
2.4857
100
2.9778
2.3282
2.9797
2.1557
2.2710
2.1571
2.2355
2.2752
2.2368
s
S
=
10
z
=
1.2
1
7.2567
43.406
9.3310
2.2003
2.2710
2.2227
2.7011
5.3099
2.9365
10
4.0710
4.7195
4.6161
2.1664
2.2710
2.1738
2.3521
2.4519
2.4121
100
2.9769
2.3271
2.9788
2.1557
2.2710
2.1571
2.2354
2.2752
2.2367Table 3
The average delay in the three schemes in LC model.
Scenario
B
S   (Mbps)
D
-
S (s)
D
-
M (s)
D
- (s)
GCC-CSA
MPC-MSA
MPC-CSA
GCC-CSA
MPC-MSA
MPC-CSA
GCC-CSA
MPC-MSA
MPC-CSA
s
S
=
5
z
=
0.8
1
7.3088
161.37
8.3352
2.5229
2.7115
2.5873
2.9197
14.433
3.0721
10
4.3990
6.8890
4.7461
2.3257
2.3161
2.3457
2.4889
2.6539
2.5358
100
2.7915
2.5017
2.8042
2.2574
2.2841
2.2643
2.2989
2.3001
2.3063
s
S
=
5
z
=
1.2
1
5.7128
161.55
7.3231
2.4270
2.6568
2.5213
2.6937
14.395
2.9204
10
3.8943
6.2456
4.4253
2.3024
2.3123
2.3370
2.4272
2.6029
2.5022
100
2.7903
2.5009
2.8035
2.2574
2.2841
2.2643
2.2988
2.3001
2.3063
s
S
=
10
z
=
0.8
1
6.0494
69.106
6.8370
2.4427
2.6058
2.4882
2.7361
7.5185
2.8459
10
4.0119
5.8228
4.2879
2.3082
2.3081
2.3263
2.4419
2.5678
2.4811
100
2.7891
2.5007
2.8033
2.2566
2.2841
2.2643
2.2980
2.3001
2.3062
s
S
=
10
z
=
1.2
1
4.6031
43.715
5.5650
2.3578
2.5175
2.4139
2.5367
5.5610
2.6692
10
3.5125
4.8380
3.8622
2.2862
2.3015
2.3092
2.3821
2.4889
2.4312
100
2.7880
2.4997
2.8023
2.2566
2.2840
2.2643
2.2979
2.3000
2.3062(1) Under the same configuration,D
- in GCC-CSA is smaller than that in MPC-MSA and MPC-CSA, especially when B
S is small. The proposed GCC algorithm always makes BSs cache the contents that produce the maximum reduction in average delay, and the CSA algorithm enables flows requesting different contents to connect to different BSs, which reduces the average delay further. When B
S is small, CSA algorithm avoids many flows being associated with the SBSs that do not cache the requested files, and therefore the loads of SBSs decrease tremendously. When B
S is large, however, the caching states of SBSs have minor influence on the loads of SBSs according to (5), and the advantage of GCC-CSA scheme over other schemes diminishes.(2) In the same scenario, the three kinds of average delay in the three schemes decrease asB
S increases (except D
-
M in MPC-MSA scheme in LNC model). When B
S increases, the achievable data rates from SBSs probably increase, and the loads of SBSs and D
-
S decrease accordingly. In the GCC-CSA and MPC-CSA scheme, increased B
S leads to expanded coverage areas of SBSs. Thus, the coverage areas of MBSs shrink and D
-
M decreases. In the LNC model, the radio link data rates provided by MBSs are independent of the loads of other BSs, and thus D
-
M in MPC-MSA remains unchanged as B
S changes. In the LC model, the interference received by flows associated with MBSs is attenuated as the loads of SBSs decrease, and D
-
M in MPC-MSA decreases accordingly.(3) For givenB
S, the three kinds of average delay in GCC-CSA scheme decrease (or remain unchanged) as s
S or z increases. The increase of s
S means that more contents can be cached at SBSs, and the increase of z implies that more requests are aimed at a few popular contents. Both of them increase the probability of finding the requested files at SBSs and reduce the average delay in GCC-CSA scheme. Because of the locality of content popularity distribution, the cached contents in MPC-MSA and MPC-CSA scheme are not always popular in local areas, and the increase of s
S or z possibly enlarges the average delay.(4) In all scenarios,D
-
S in GCC-CSA is smaller than that in MPC-MSA when B
S is small. When B
S is large, however, D
-
S in GCC-CSA is larger than that in MPC-MSA. CSA mechanism restricts the coverage areas of SBSs when B
S is small, which brings about smaller D
-
S compared with MSA mechanism. When B
S becomes large, the data flows that were originally associated with MBSs probably transfer to SBSs to reduce the overall average delay in the GCC-CSA scheme. In this case, D
-
S in GCC-CSA is larger than that in MPC-MSA, but D
- in GCC-CSA is always smaller than that in MPC-MSA.For visually showing the advantages of GCC-CSA scheme in reducing average delay, Figures4 and 5 illustrate the three kinds of average delay in LNC and LC models when B
S = 10 Mbps, respectively. We can observe that D
-
S in GCC-CSA is smaller than that in MPC-MSA and MPC-CSA. The reduction in D
-
S in GCC-CSA compared with the values in MPC-MSA becomes apparent when s
S is small. When s
S
=
5 and z
=
0.8, the proposed scheme achieves a reduction of 19.4% and 36.1% in D
-
S compared with MPC-CSA scheme in LNC and LC models, respectively. When s
S
=
5 and z
=
1.2, the proposed scheme achieves a reduction of 24.3% and 37.6% in D
-
S compared with MPC-CSA scheme in LNC and LC models, respectively. Moreover, D
-
M and D
- in these schemes are almost equal. This is because the coverage areas of MBSs are much larger than those of SBSs and D
-
M in these schemes are close to each other.Figure 4
Comparison of average delay in LNC model whenB
S = 10 Mbps.
(a)
s
S = 5, z = 0.8
(b)
s
S = 5, z = 1.2
(c)
s
S = 10, z = 0.8
(d)
s
S = 10, z = 1.2Figure 5
Comparison of average delay in LC model whenB
S = 10 Mbps.
(a)
s
S = 5, z = 0.8
(b)
s
S = 5, z = 1.2
(c)
s
S = 10, z = 0.8
(d)
s
S = 10, z = 1.2Figures6 and 7 show the cumulative distribution functions (CDFs) of E
D
∣
y under a given network configuration in LNC and LC models, respectively. The CDFs of E
D
∣
y in Y
M in these three schemes almost overlap. However, the distributions of E
D
∣
y in Y
S in GCC-CSA scheme improve significantly compared with those in MPC-MSA and MPC-CSA scheme.Figure 6
The CDFs ofE
D
∣
y in these three schemes in LNC model. s
S
=
10, z
=
0.8, and B
S = 10 Mbps.Figure 7
The CDFs ofE
D
∣
y in these three schemes in LC model. s
S
=
10, z
=
0.8, and B
S = 10 Mbps.


### 7.4. Backhaul Usage

Figures8 and 9 compare B
-
u
,
M and B
-
u
,
S in these schemes in LNC and LC models, respectively. For given s
S and z, B
-
u
,
M and B
-
u
,
S in MPC-MSA do not change with the variation of B
S because MSA method is independent of backhaul capacity. B
-
u
,
M in GCC-CSA and MPC-CSA decrease with the increase of B
S, and B
-
u
,
S in GCC-CSA and MPC-CSA increase with the increase of B
S. As B
S increases, some data flows that originally connected to MBSs are associated with SBSs to lower the overall average delay, which leads to decreased B
-
u
,
M and increased B
-
u
,
S. We specify the advantage of GCC-CSA scheme in backhaul usage based on Figure 8(c), and other subfigures show the same results. When B
S = 1 Mbps, B
-
u
,
S in GCC-CSA is 1722.5 bit/s less than that in MPC-MSA, but B
-
u
,
M in GCC-CSA is only 680.1 bit/s greater than that in MPC-MSA. When B
S = 10 Mbps, B
-
u
,
S and B
-
u
,
M in GCC-CSA are all smaller than those in MPC-MSA. When B
S = 100 Mbps, B
-
u
,
M in GCC-CSA is 2078.5 bit/s less than that in MPC-MSA, but B
-
u
,
S in GCC-CSA is only 320.0 bit/s greater than that in MPC-MSA. On the whole, the proposed scheme occupies less backhaul capacity than MPC-MSA scheme. Furthermore, B
-
u
,
S and B
-
u
,
M in GCC-CSA are always smaller than those in MPC-CSA, which demonstrates the advantage of GCC algorithm. These conclusions can also be drawn in other scenarios in LNC and LC models. The saved backhaul capacity can be used to provide other services, such as live streaming, video calls and online games.Figure 8
The backhaul usage of the three schemes in LNC model.
(a)
s
S = 5, z = 0.8
(b)
s
S = 5, z = 1.2
(c)
s
S = 10, z = 0.8
(d)
s
S = 10, z = 1.2Figure 9
The backhaul usage of the three schemes in LC model.
(a)
s
S = 5, z = 0.8
(b)
s
S = 5, z = 1.2
(c)
s
S = 10, z = 0.8
(d)
s
S = 10, z = 1.2


### 7.5. Optimality of GCC Algorithm

We demonstrate the optimality of GCC algorithm in a simple network as shown in Figure10. The simplified content library contains F
=
10 files and the cache capacity of SBS is s
S
=
2. The four regions separated by dashed lines share the same skewness parameter but differ in the order of content popularity. We compare the GCC algorithm with exhaustive search and MPC policy, and the CSA algorithm is applied together with these content placement schemes. Table 4 lists the obtained cost function values of these schemes under various network configurations. In this simple network, GCC can always find the optimal content placement with much lower complexity than exhaustive search. All these schemes obtain the optimal solutions when s
S = 100 Mbps. This is because the implication of content placement at SBSs becomes weak when the backhaul capacity is large enough according to (5).Table 4
The cost function values of these three content placement schemes.
Backhaul capacity of SBSs
z
=
0.8
z
=
1.2
GCC
Exhaustive search
MPC
GCC
Exhaustive search
MPC
s
S = 1 Mbps
4.5335
4.5335
5.3048
3.7470
3.7470
4.4404
s
S = 10 Mbps
2.2406
2.2406
2.2456
2.2302
2.2302
2.2361
s
S = 100 Mbps
2.1827
2.1827
2.1827
2.1827
2.1827
2.1827Figure 10
The simulation scenario for demonstrating the optimality of the GCC algorithm. Red circles denote the locations of SBSs. The traffic distribution is generated by the method proposed in [41].


## 7.1. Simulation Setup

We consider a square area with side length 2km, as shown in Figure1. 7 MBSs and 10 SBSs are located in this area. MBSs are deployed based on hexagonal grid model with an intersite distance of 800 m. SBSs are randomly deployed in this area. The minimum intersite distance between SBS and SBS (MBS) is set to 400 m. The bandwidth is W = 10 MHz, and the noise power spectral density is -174 dBm/Hz. The spatial traffic distribution during a certain time period derived from a network operator [53] is also shown in Figure 1. The content library contains F
=
50 files. For simulating the locality of content popularity distribution, this area is partitioned into 9 regions, and the content popularity distributions in these regions are different. All these regions share the same skewness parameter but differ in the order of content popularity. For example, Content 1 is the most popular content in Region 1, but it is the fifth most popular content in Region 2. Two values of skewness parameter z
∈
0.8,1.2 are considered. All the files are assumed to have the same size, i.e., v
f = 10 MB for all f
∈
F. For conducting the experiments on computers, the whole area is divided into 200 × 200 pixels. Other simulation parameters are given in Table 1.Table 1
Simulation parameters.
Parameters
MBS
SBS
Transmit power
P
M = 43 dBm
P
S = 33 dBm
Path loss model
128.1
+
37.6
l
o
g
10
R
k
m
140.7
+
36.7
l
o
g
10
R
k
m
Backhaul capacity
B
M = 1 Gbps
B
S
∈
1,10,100 Mbps
Cache capacity (the number of contents)
s
M
=
0
s
S
∈
5,10Figure 1
The simulation scenario. Red triangles denote MBSs and red circles denote SBSs.


## 7.2. Illustration of Content-Level Selective Association

Figures2 and 3 illustrate the coverage areas associated with Content 1 and Content 2 derived from GCC-CSA algorithm in LNC model and LC model, respectively. From these figures, we can observe that the coverage areas of SBS1, SBS4 and SBS8 associated with Content 1 and Content 2 are quite different, especially in LC model. The difference in caching state of Content 1 and Content 2 results in the different coverage areas. In these two models, SBS1 and SBS8 cache Content 1 but do not cache Content 2, and SBS4 caches Content 2 but does not cache Content 1. The caching states of these two contents are identical in other SBSs. Taking SBS8 as an example, since it does not cache Content 2, the coverage area with respect to Content 2 must shrink to prevent heavy load.Figure 2
The coverage areas with respect to Content 1 and Content 2 in LNC model.s
S
=
10, z
=
0.8, and B
S = 10 Mbps.
(a)
The cell coverages w. r. t. Content 1
(b)
The cell coverages w. r. t. Content 2Figure 3
The coverage areas with respect to Content 1 and Content 2 in LC model.s
S
=
10, z
=
0.8, and B
S = 10 Mbps.
(a)
The cell coverages w. r. t. Content 1
(b)
The cell coverages w. r. t. Content 2


## 7.3. Statistical Properties of Delay

Tables2 and 3 give the average delay in the three schemes under various network configurations in LNC model and LC model, respectively. D
-
S, D
-
M, and D
- are defined in Section 5.1. We can draw the following conclusions from these tables.Table 2
The average delay in the three schemes in LNC model.
Scenario
B
S   (Mbps)
D
-
S (s)
D
-
M (s)
D
- (s)
GCC-CSA
MPC-MSA
MPC-CSA
GCC-CSA
MPC-MSA
MPC-CSA
GCC-CSA
MPC-MSA
MPC-CSA
s
S
=
5
z
=
0.8
1
12.802
160.54
14.781
2.2614
2.2710
2.2871
3.3414
13.963
3.5848
10
5.5067
6.8358
6.0531
2.1799
2.2710
2.1871
2.5060
2.6082
2.5668
100
2.9788
2.3292
2.9792
2.1559
2.2710
2.1572
2.2358
2.2753
2.2369
s
S
=
5
z
=
1.2
1
9.5583
160.66
12.890
2.2247
2.2710
2.2675
2.9620
13.972
3.3597
10
4.6681
6.1678
5.5866
2.1718
2.2710
2.1837
2.4158
2.5589
2.5176
100
2.9778
2.3284
2.9799
2.1559
2.1710
2.1571
2.2357
2.2753
2.2368
s
S
=
10
z
=
0.8
1
10.340
68.724
11.984
2.2319
2.2710
2.2507
3.0528
7.1803
3.2444
10
4.8670
5.7330
5.3061
2.1739
2.2710
2.1794
2.4373
2.5268
2.4857
100
2.9778
2.3282
2.9797
2.1557
2.2710
2.1571
2.2355
2.2752
2.2368
s
S
=
10
z
=
1.2
1
7.2567
43.406
9.3310
2.2003
2.2710
2.2227
2.7011
5.3099
2.9365
10
4.0710
4.7195
4.6161
2.1664
2.2710
2.1738
2.3521
2.4519
2.4121
100
2.9769
2.3271
2.9788
2.1557
2.2710
2.1571
2.2354
2.2752
2.2367Table 3
The average delay in the three schemes in LC model.
Scenario
B
S   (Mbps)
D
-
S (s)
D
-
M (s)
D
- (s)
GCC-CSA
MPC-MSA
MPC-CSA
GCC-CSA
MPC-MSA
MPC-CSA
GCC-CSA
MPC-MSA
MPC-CSA
s
S
=
5
z
=
0.8
1
7.3088
161.37
8.3352
2.5229
2.7115
2.5873
2.9197
14.433
3.0721
10
4.3990
6.8890
4.7461
2.3257
2.3161
2.3457
2.4889
2.6539
2.5358
100
2.7915
2.5017
2.8042
2.2574
2.2841
2.2643
2.2989
2.3001
2.3063
s
S
=
5
z
=
1.2
1
5.7128
161.55
7.3231
2.4270
2.6568
2.5213
2.6937
14.395
2.9204
10
3.8943
6.2456
4.4253
2.3024
2.3123
2.3370
2.4272
2.6029
2.5022
100
2.7903
2.5009
2.8035
2.2574
2.2841
2.2643
2.2988
2.3001
2.3063
s
S
=
10
z
=
0.8
1
6.0494
69.106
6.8370
2.4427
2.6058
2.4882
2.7361
7.5185
2.8459
10
4.0119
5.8228
4.2879
2.3082
2.3081
2.3263
2.4419
2.5678
2.4811
100
2.7891
2.5007
2.8033
2.2566
2.2841
2.2643
2.2980
2.3001
2.3062
s
S
=
10
z
=
1.2
1
4.6031
43.715
5.5650
2.3578
2.5175
2.4139
2.5367
5.5610
2.6692
10
3.5125
4.8380
3.8622
2.2862
2.3015
2.3092
2.3821
2.4889
2.4312
100
2.7880
2.4997
2.8023
2.2566
2.2840
2.2643
2.2979
2.3000
2.3062(1) Under the same configuration,D
- in GCC-CSA is smaller than that in MPC-MSA and MPC-CSA, especially when B
S is small. The proposed GCC algorithm always makes BSs cache the contents that produce the maximum reduction in average delay, and the CSA algorithm enables flows requesting different contents to connect to different BSs, which reduces the average delay further. When B
S is small, CSA algorithm avoids many flows being associated with the SBSs that do not cache the requested files, and therefore the loads of SBSs decrease tremendously. When B
S is large, however, the caching states of SBSs have minor influence on the loads of SBSs according to (5), and the advantage of GCC-CSA scheme over other schemes diminishes.(2) In the same scenario, the three kinds of average delay in the three schemes decrease asB
S increases (except D
-
M in MPC-MSA scheme in LNC model). When B
S increases, the achievable data rates from SBSs probably increase, and the loads of SBSs and D
-
S decrease accordingly. In the GCC-CSA and MPC-CSA scheme, increased B
S leads to expanded coverage areas of SBSs. Thus, the coverage areas of MBSs shrink and D
-
M decreases. In the LNC model, the radio link data rates provided by MBSs are independent of the loads of other BSs, and thus D
-
M in MPC-MSA remains unchanged as B
S changes. In the LC model, the interference received by flows associated with MBSs is attenuated as the loads of SBSs decrease, and D
-
M in MPC-MSA decreases accordingly.(3) For givenB
S, the three kinds of average delay in GCC-CSA scheme decrease (or remain unchanged) as s
S or z increases. The increase of s
S means that more contents can be cached at SBSs, and the increase of z implies that more requests are aimed at a few popular contents. Both of them increase the probability of finding the requested files at SBSs and reduce the average delay in GCC-CSA scheme. Because of the locality of content popularity distribution, the cached contents in MPC-MSA and MPC-CSA scheme are not always popular in local areas, and the increase of s
S or z possibly enlarges the average delay.(4) In all scenarios,D
-
S in GCC-CSA is smaller than that in MPC-MSA when B
S is small. When B
S is large, however, D
-
S in GCC-CSA is larger than that in MPC-MSA. CSA mechanism restricts the coverage areas of SBSs when B
S is small, which brings about smaller D
-
S compared with MSA mechanism. When B
S becomes large, the data flows that were originally associated with MBSs probably transfer to SBSs to reduce the overall average delay in the GCC-CSA scheme. In this case, D
-
S in GCC-CSA is larger than that in MPC-MSA, but D
- in GCC-CSA is always smaller than that in MPC-MSA.For visually showing the advantages of GCC-CSA scheme in reducing average delay, Figures4 and 5 illustrate the three kinds of average delay in LNC and LC models when B
S = 10 Mbps, respectively. We can observe that D
-
S in GCC-CSA is smaller than that in MPC-MSA and MPC-CSA. The reduction in D
-
S in GCC-CSA compared with the values in MPC-MSA becomes apparent when s
S is small. When s
S
=
5 and z
=
0.8, the proposed scheme achieves a reduction of 19.4% and 36.1% in D
-
S compared with MPC-CSA scheme in LNC and LC models, respectively. When s
S
=
5 and z
=
1.2, the proposed scheme achieves a reduction of 24.3% and 37.6% in D
-
S compared with MPC-CSA scheme in LNC and LC models, respectively. Moreover, D
-
M and D
- in these schemes are almost equal. This is because the coverage areas of MBSs are much larger than those of SBSs and D
-
M in these schemes are close to each other.Figure 4
Comparison of average delay in LNC model whenB
S = 10 Mbps.
(a)
s
S = 5, z = 0.8
(b)
s
S = 5, z = 1.2
(c)
s
S = 10, z = 0.8
(d)
s
S = 10, z = 1.2Figure 5
Comparison of average delay in LC model whenB
S = 10 Mbps.
(a)
s
S = 5, z = 0.8
(b)
s
S = 5, z = 1.2
(c)
s
S = 10, z = 0.8
(d)
s
S = 10, z = 1.2Figures6 and 7 show the cumulative distribution functions (CDFs) of E
D
∣
y under a given network configuration in LNC and LC models, respectively. The CDFs of E
D
∣
y in Y
M in these three schemes almost overlap. However, the distributions of E
D
∣
y in Y
S in GCC-CSA scheme improve significantly compared with those in MPC-MSA and MPC-CSA scheme.Figure 6
The CDFs ofE
D
∣
y in these three schemes in LNC model. s
S
=
10, z
=
0.8, and B
S = 10 Mbps.Figure 7
The CDFs ofE
D
∣
y in these three schemes in LC model. s
S
=
10, z
=
0.8, and B
S = 10 Mbps.


## 7.4. Backhaul Usage

Figures8 and 9 compare B
-
u
,
M and B
-
u
,
S in these schemes in LNC and LC models, respectively. For given s
S and z, B
-
u
,
M and B
-
u
,
S in MPC-MSA do not change with the variation of B
S because MSA method is independent of backhaul capacity. B
-
u
,
M in GCC-CSA and MPC-CSA decrease with the increase of B
S, and B
-
u
,
S in GCC-CSA and MPC-CSA increase with the increase of B
S. As B
S increases, some data flows that originally connected to MBSs are associated with SBSs to lower the overall average delay, which leads to decreased B
-
u
,
M and increased B
-
u
,
S. We specify the advantage of GCC-CSA scheme in backhaul usage based on Figure 8(c), and other subfigures show the same results. When B
S = 1 Mbps, B
-
u
,
S in GCC-CSA is 1722.5 bit/s less than that in MPC-MSA, but B
-
u
,
M in GCC-CSA is only 680.1 bit/s greater than that in MPC-MSA. When B
S = 10 Mbps, B
-
u
,
S and B
-
u
,
M in GCC-CSA are all smaller than those in MPC-MSA. When B
S = 100 Mbps, B
-
u
,
M in GCC-CSA is 2078.5 bit/s less than that in MPC-MSA, but B
-
u
,
S in GCC-CSA is only 320.0 bit/s greater than that in MPC-MSA. On the whole, the proposed scheme occupies less backhaul capacity than MPC-MSA scheme. Furthermore, B
-
u
,
S and B
-
u
,
M in GCC-CSA are always smaller than those in MPC-CSA, which demonstrates the advantage of GCC algorithm. These conclusions can also be drawn in other scenarios in LNC and LC models. The saved backhaul capacity can be used to provide other services, such as live streaming, video calls and online games.Figure 8
The backhaul usage of the three schemes in LNC model.
(a)
s
S = 5, z = 0.8
(b)
s
S = 5, z = 1.2
(c)
s
S = 10, z = 0.8
(d)
s
S = 10, z = 1.2Figure 9
The backhaul usage of the three schemes in LC model.
(a)
s
S = 5, z = 0.8
(b)
s
S = 5, z = 1.2
(c)
s
S = 10, z = 0.8
(d)
s
S = 10, z = 1.2


## 7.5. Optimality of GCC Algorithm

We demonstrate the optimality of GCC algorithm in a simple network as shown in Figure10. The simplified content library contains F
=
10 files and the cache capacity of SBS is s
S
=
2. The four regions separated by dashed lines share the same skewness parameter but differ in the order of content popularity. We compare the GCC algorithm with exhaustive search and MPC policy, and the CSA algorithm is applied together with these content placement schemes. Table 4 lists the obtained cost function values of these schemes under various network configurations. In this simple network, GCC can always find the optimal content placement with much lower complexity than exhaustive search. All these schemes obtain the optimal solutions when s
S = 100 Mbps. This is because the implication of content placement at SBSs becomes weak when the backhaul capacity is large enough according to (5).Table 4
The cost function values of these three content placement schemes.
Backhaul capacity of SBSs
z
=
0.8
z
=
1.2
GCC
Exhaustive search
MPC
GCC
Exhaustive search
MPC
s
S = 1 Mbps
4.5335
4.5335
5.3048
3.7470
3.7470
4.4404
s
S = 10 Mbps
2.2406
2.2406
2.2456
2.2302
2.2302
2.2361
s
S = 100 Mbps
2.1827
2.1827
2.1827
2.1827
2.1827
2.1827Figure 10
The simulation scenario for demonstrating the optimality of the GCC algorithm. Red circles denote the locations of SBSs. The traffic distribution is generated by the method proposed in [41].


## 8. Conclusions

In this paper, we have proposed a GCC-CSA algorithm for joint optimization of content placement and user association in cache-enabled HCNs based on flow-level models. By modeling cellular networks as queuing systems, we have taken into consideration the discrepancy in the timescales of content placement and user association, the locality of content popularity and the heterogeneity of spatial traffic distribution, which are often neglected in the literature. The objective of joint optimization is to minimize the average delay of data flows, and this problem is formulated as an MINLP problem in LNC and LC models, respectively. Given the contents cached at BSs, we have proposed a CSA algorithm that allows data flows requesting different contents to connect to different BSs. A heuristic GCC algorithm is also proposed to tackle the content placement problem, and its convergence property is proved. Simulation results show that the proposed GCC-CSA algorithm can reduce the average content delivery delay compared with traditional approaches. Especially, when the backhaul capacity of SBSs is stringent, the proposed algorithm can significantly decrease the average content delivery delay in coverage areas of SBSs compared with traditional MPC-MSA scheme. In addition, the proposed algorithm can reserve larger backhaul capacities for transmission of contents that are not reusable.



---

*Source: 1628283-2018-11-19.xml*