1

Random Caching in Backhaul-Limited
Multi-Antenna Networks: Analysis and Area
Spectrum Efficiency Optimization
arXiv:1709.06278v1 [] 19 Sep 2017

Sufeng Kuang, Student Member, IEEE, Nan Liu, Member, IEEE

Abstract
Caching at base stations is a promising technology to satisfy the increasing capacity requirements
and reduce the backhaul loads in future wireless networks. Careful design of random caching can fully
exploit the file popularity and achieve good performance. However, previous works on random caching
scheme usually assumed single antenna at BSs and users, which is not the case in practical multi-antenna
networks. In this paper, we consider the analysis and optimization in the cache-enabled multi-antenna
networks with limited backhaul. We first derive a closed-form expression and a simple tight upper
bound of the successful transmission probability, using tools from stochastic geometry and a gamma
approximation. Based on the analytic results, we then consider the area spectrum efficiency maximization
by optimizing design parameters, which is a complicated mixed-integer optimization problem. After
analyzing the optimal properties, we obtain a local optimal solution with lower complexity. To further
simplify the optimization, we then solve an asymptotic optimization problem in the high user density
region, using the upper bound as the objective function. Numerical simulations show that the asymptotic
optimal caching scheme achieves better performance over existing caching schemes. The analysis and
optimization results provide insightful design guidelines for random caching in practical networks.

Index Terms
Cache, limited backhaul, multi-antenna, Poisson point process, stochastic geometry

I. I NTRODUCTION
The deployment of small base stations (SBSs) or network densification, is proposed as a key
method for meeting the tremendous capacity increase in 5G networks [1]. Dense deployment of
S.Kuang and N.Liu are with the National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096,
China.(Email: sfkuang@seu.edu.cn and nanliu@seu.edu.cn).

2

small cells can significantly improve the performance of the network by bringing the BSs closer
to the users. On the other hand, MIMO technology, especially the deployment of massive number
of antennas at BSs, is playing an essential role in 5G networks to satisfy the increasing data
requirements of the users. Therefore, the combination of small cells and novel MIMO techniques
is inevitable in 5G networks [2]. However, this approach aggravates the transmission loads of
the backhaul links connecting the SBSs and the core networks.
Caching at BSs is a promising method to alleviate the heavy backhaul loads in small cell
networks [3]. Therefore, jointly deploying cache and multi antennas at BSs is proposed to
achieve 1000x capacity increase for 5G networks [4]–[6]. In [4] and [5], the authors considered
the optimization of the cooperative MIMO for video streaming in cache-enabled networks. In
[6], the authors considered the optimal multicasting beamforming design for cache-enabled cloud
radio access network (C-RAN). Note that the focuses of the above works were on the parameter
optimization for cache-enabled networks under the traditional grid model.
Recently, Poisson point process (PPP) is proposed to model the BS locations to capture the
irregularity and randomness of the small cell networks [7]. Based on the random spatial model,
the authors in [8] and [9] considered storing the most popular files in the cache for small
cell networks and heterogeneous cellular networks (HetNets). In [10], the authors considered
uniformly caching all the files at BSs, assuming that the file request popularity follows a uniform
distribution. In [11] , the authors considered storing different files at the cache in an i.i.d. manner,
in which each file is selected with its request probability. Note that in [8]–[11], the authors did
not consider the optimal cache placement, rather, they analyzed the performance under a given
cache placement, and thus, the results of the papers might not yield the best performance of the
system.
In view of the above problem, random caching strategy is proposed to achieve the optimal
performance [12]–[15]. In [12] and [13], the authors considered the caching and multicasting in
the small cell networks or the HetNets, assuming random caching at SBSs. In [14], the authors
considered the analysis and optimization of the cache-enabled multi-tier HetNets, assuming
random caching for all tiers of the BSs. Note that in [12]–[14], the authors obtained a waterfilling-type optimal solutions in some special cases due to the Rayleigh distribution of the fading.
In [15] and [16], the authors considered the helper cooperation for the small cell networks or
the HetNets, in which the locations of BSs are modeled as Poisson cluster Process.
However, the works mentioned above considered the random caching in networks equipped

3

with a single antenna at BSs and users, which is rarely the case in practical networks. In [17],
the authors considered the cache distribution optimization in HetNets, where multi-antennas are
deployed at the MBSs. However, the authors considered a special case of zero forcing precoding,
i.e., the number of the users is equal to the number of BS antennas, in which the equivalent
channel gains from the BSs to its served users follow the Rayleigh distribution. This property
does not hold for the general MIMO scenario, where the equivalent channel gains from the BSs
to its served users follow the Gamma distribution [18], [19].
The main difficulty of the analysis of the multi-antenna networks stems from the complexity
of the random matrix channel [20]–[22]. In [20], the authors utilized the stochastic ordering to
compare MIMO techniques in the HetNets, but the authors did not comprehensively analyze
the SINR distribution. In [21], the authors proposed to utilize a Toeplitz matrix representation
to obtain a tractable expression of the successful transmission probability in the multi-antenna
small cell networks. In [22]–[24], the authors extended the approach of the Toeplitz matrix
representation to analyze the MIMO mutli-user HetNets, MIMO networks with interference
nulling and millimeter wave networks with directional antenna arrays. However, this expression
involves the matrix inverse, which is difficult for analysis and optimization. In [25], a gamma
approximation [26] was utilized to facilitate the analysis in the millimeter wave networks.
In this paper, we consider the analysis and optimization of random caching in backhaullimited multi-antenna networks. Unlike the previous works [12]–[14] focusing on the successful
transmission probability of the typical user, we analyze and optimize the area spectrum efficiency,
which is a widely-used metric to describe the network capacity. The optimization is over file
allocation strategy and cache placement strategy, where a file allocation strategy dictates which
file should be stored at the cache of the BSs and which file should be transmitted via the
backhaul, and a cache placement strategy is to design the probability vector according to which
the files are randomly stored in the cache of the BSs.
First, we derive an exact expression of the successful transmission probability in cacheenabled multi-antenna networks with limited backhaul, using tools from stochastic geometry
and a Toeplitz matrix representation. We then utilize a gamma approximation to derive a tight
upper bound on the performance metrics to facilitate the parameter design. The exact expression
involves the inverse of a lower triangular Toeplitz matrix and the upper bound is a sum of a
series of fractional functions of the caching probability. These expressions reveal the impacts of
the parameters on the performance metrics, i.e., the successful transmission probability and the

4

area spectrum efficiency. Furthermore, the simple analytical form of the upper bound facilitates
the parameter design.
Next, we consider the area spectrum efficiency maximization by jointly optimizing the file
allocation and cache placement, which is a very challenging mixed-integer optimization problem.
We first prove that the area spectrum efficiency is an increasing function of the cache placement.
Based on this characteristic, we then exploit the properties of the file allocation and obtain a
local optimal solution in the general region, in which the user density is moderate. To further
reduce the complexity, we then solve an asymptotic optimization problem in the high user density
region, using the upper bound as objective function. Interestingly, we find that the optimal file
allocation for the asymptotic optimization is to deliver the most B popular files via the backhaul
and store the rest of the files at the cache, where B is the largest number of files the backhaul
can deliver at same time. In this way, the users requesting the most B popular files are associated
with the nearest BSs, who obtain the most B popular files via the backhaul, and therefore achieve
the optimal area spectrum efficiency.
Finally, by numerical simulations, we show that the asymptotic optimal solution with low
complexity achieves a significant gain in terms of area spectrum efficiency over previous caching
schemes.
II. S YSTEM M ODEL
A. Network Model
We consider a downlink cache-enabled multi-antenna network with limited backhaul, as shown
in Fig. 1, where BSs, equipped with N antennas, are distributed according to a homogeneous
Poisson point process (PPP) Φb with density λb . The locations of the single-antenna users are
distributed as an independent homogeneous PPP Φu with density λu . According to Slivnyak’s
theorem [27], we analyze the performance of the typical user who is located at the origin without
loss of generality. All BSs are operating on the same frequency band and the users suffer intercell
interference from other BSs. We assume that all the BSs are active due to high user density.
We assume that each user requests a certain file from a finite content library which contains
F files. Let F = {1, 2, 3, · · · , F } denotes the set of the files in the network. The popularity of
the requested files is known a priori and is modeled as a Zipf distribution [28]
f −γ
qf = PF −γ ,
i=1 i

(1)

5

Backhaul File

Cache File

BS

User

Cache

Backhhaul

Distance-based Association.

Content-centric Association.

Fig. 1. Illustration of the system model. For the backhaul file, the distance-based association scheme is adopted. For the cached
file, the content-centric association scheme is adopted.

where qf is the probability that a user requests file f and γ is the shape parameter of the Zipf
distribution. We assume that all the files have same size and the size of a file is normalized to
1 for simplicity.
Each BS is equipped with a cache with C segments and the cache can store at most C different
files out of the content library. For the files which are not stored in the cache, the BSs can fetch
them from the core network via backhaul links which can transmit at most B files at same time.
We refer to C as cache size and B as backhaul capability. We assume B + C ≤ F to illustrate
the resource limitation.
B. Caching and Backhaul Delivery
The set of all the files is partitioned into two disjoint sets, and we define the set of files stored
in the cache of all the BSs and the set of files not stored in any of the BSs, i.e., the files in it
must be transmitted via the backhaul, as cached file set and backhaul file set, which are denoted
as Fc and Fb , respectively. The number of files in Fx is Fx , x = c, b. Since Fc and Fb form a
partition of F, we have
Fc

[

Fb = F, Fc

\

Fb = ∅.

(2)

We define the process of designing Fc and Fb as file allocation.
Each BS can cache C different files from a total Fc files via the random caching scheme, in
which the BS stores a certain file i ∈ Fc randomly with probability ti . Let t = (ti )i∈Fc denotes

6

the caching distribution of all the files. Then we have the following constraints
ti ∈ [0, 1], ∀i ∈ Fc ,
X

ti ≤ C.

(3)
(4)

i∈Fc

We refer to the specification of t as cache placement.
For further analysis, we define the BSs that have the cached file f ∈ Fc in the cache as the
f-cached BSs. According to the thinning theory of the PPP, the density of the f -cached BSs is
λfb = tf λb . We denote the set of the f -cached BSs as Φfb and the set of the remaining BSs that
do not have file f in their cache as Φ−f
b . When a user requests the file f out of the cached
file set, the user is associated with the nearest f -cached BSs which will provide the required
file f from its cache. We refer to the BS associated with the typical user as the tagged BS and
this association scheme is called content-centric association scheme. Content-centric association
scheme is different from the traditional distance-based association scheme, where the user is
associated with the nearest BS. We denote the tagged BS as BS 1.
When a user requests a file out of the backhaul file set, the distance-based association is
adopted and the user is associated with the nearest BS. We define the set of backhaul requested
r
files as the set of the backhaul files requested by the users of BS i, which is denoted as Fb,i
⊆ Fb .
r
The number of the backhaul request file is denoted as Fb,i
. If BS i needs to transmit less than
r
r
B backhaul files via backhaul, i.e., Fb,i
≤ B, then BS i gets all Fb,i
files from the backhaul and

transmits all of them to the designated users; otherwise, BS i will randomly select B different
r
files from Fb,i
according to the uniform distribution, where these files will be transmitted from

the backhaul links and then passed on to the designated users.
III. P ERFORMANCE M ETRIC AND P ROBLEM F ORMULATION
A. Performance Metric
In this part, we define the successful transmission probability (STP) and the area spectrum
efficiency (ASE) of the typical user when the single-user maximal ratio combination (MRT)
beamforming is adopted. We consider the single-user MRT beamforming due to the low complexity of the beamforming design, which is suitable for the scenario when a large number
of antennas are deployed at the BSs. For other MIMO scenarios, the equivalent channel gain
follows the gamma distribution with different parameters [18], [19]. Therefore, the method of the

7

analysis here can be extended to the cache-enabled MIMO networks with different precoding and
combining strategies. We assume that the transmitter can get the perfect channel state infomation
(CSI) through the feedback from the users. The BSs do not have the CSI of the other cells due
to the high BS density.
We refer to the typical user as user 0 and it is served by the tagged BS located at x1 . Due to
the assumption of single-user MRT, each BS serves one user per resource block (RB). Hence,
the received signal of the typical user on its resource block is
β

y0f = kx1 k− 2 h∗0,1 w1 s1 +

X

β

kxi k− 2 h∗0,i wi si + n0 ,

(5)

i∈{Φb \1}

where wi is the beamforming vector of BS i to its served user, f is the file requested by the
typical user, xi is the location of BS i, h0,i ∈ CN ×1 is the channel coefficient vector from BS i
to the typical user, si ∈ C1×1 is the transmitting message of BS i and n0 is the additive white
Gaussian noise (AWGN) at the receiver. We assume that E[si ∗ si ] = P for any i and P is the
transmit power of the BS. The elements of the channel coefficient vector h0,i are independent
and identical complex Gaussian random variables, i.e., CN (0, 1). β > 2 is the pathloss exponent.
For single-user MRT, to maximize the channel gain from the BS to its served user, the
beamforming at BS i is wi =

hi
khi k

[29], where hi ∈ CN ×1 is the channel coefficient from

BS i to its served user. Thus the SIR of the typical user requiring file f , whether f is in the
cached file set or the backhaul file set, is given by
SIRf = P
where gi =

kh∗0,i hi k2
khi k2

P kx1 k−β g1
,
−β g
i
i∈{Φb \1} P kxi k

(6)

is the equivalent channel gain (including channel coefficient and the

beamforming) from BS i to the typical user. It is shown that the equivalent channel gain from the
tagged BS to its served user, i.e., g1 ∼ Gamma(N, 1) and gi ∼ Exp(1), ∀i > 1 [29]. In this paper,
we consider SIR for performance analysis rather than SINR due to the dense deployments of the
SBSs. In simulations, we include the noise to illustrate that in dense networks the consideration
of the SIR achieves nearly the same performance as that of the SINR.
For the single-user MRT, the successful transmission probability (STP) of the typical user is
defined as the probability that the SIR is larger than a threshold, i.e.,
Ps (Fc , t) =

X
f ∈Fc

qf P (SIRf > τ ) +

X
f ∈Fb

qf P (SIRf > τ, f transmitted through backhaul) , (7)

8

where τ is the SIR threshold. As mentioned before, f is transmitted by the backhaul if the
r
number of the backhaul requested files of the tagged BS Fb,1
is no more than the backhaul

capability B, or if it is been chosen to be transmitted according to the uniform distribution in
r
r
the event where Fb,1
> B. Note that the STP is related to the random variables Fb,1
and SIRf .

We use the area spectrum efficiency (ASE) as the metric to describe the average spectrum
efficiency per area. The ASE of the single-user MRT is defined as [30], [31]
R(Fc , t) = λb Ps (Fc , t) log2 (1 + τ ).

(8)

where the unit is bit/s/Hz/km2 . Note that the ASE reveals the relationship between the BS density
and the network capacity.
B. Problem Formulation
Under given backhaul capability B and cache size C, the caching strategy, i.e., the file
allocation strategy and the cache placement strategy, fundamentally affects the ASE. We study the
problem of maximizing the ASE via a careful design of file allocation Fc and cache placement
t as follows
max R(Fc , t)
Fc ,t

s.t

(9)

(2), (3), (4).

We will derive the expressions of the STP and the ASE in Section IV and solve the ASE
maximization problem, i.e., the problem in (9), in Section V.
IV. P ERFORMANCE A NALYSIS
In this section, we first derive an exact expression of the STP and ASE under given file
allocation and cache placement strategy, i.e., under given Fc and t. Then we utilize a gamma
distribution approximation to obtain a simpler upper bound of the STP and ASE.
A. Exact Expression
In this part, we derive an exact expression of the STP and the ASE using tools from stochastic
geometry. In general, the STP is related to the number of the backhaul request file of the tagged

9

r
BS, i.e., Fb,1
. Therefore, to obtain the STP, we first calculate the probability mass function (PMF)
r
of Fb,1
.
r
r
Lemma 1. (pmf of Fb,1
) When f ∈ Fb is requested by the tagged BS, the pmf of Fb,1
is given by
r
b
= k = g ({Fb \ f }, k − 1) ,
PF
Fb,1
f

ä

Ä

k ∈ {1, 2, · · · , Fb },

(10)

where g(B, k) is given by
4

X

g (B, k) =

Ç

q i λu
1− 1+
3.5λb

Y

Y∈{X ⊆B:|X |=k} i∈Y

å−4.5 !

Y

Ç

qi λu
1+
3.5λb

i∈B\Y

å−4.5

.

(11)

Proof: See Appendix A.
Based on Lemma 1, we have the following corollary.
r
r
Corollary 1. (The pmf of Fb,1
when λu → ∞). When λu → ∞, the pmf of Fb,1
is




 0,

k = 1, 2, · · · , Fb − 1

 1,

k = Fb

r
b
lim PF
Fb,1
=k =
f
λu →∞


Ä

ä

.

(12)

r
converges to constant Fb in distribution as λu → ∞. The
Corollary 1 interprets that Fb,1

asymptotic result is consistent with the fact that when the user density is high, each BS will
have many users connected to it, and thus, each BS will require all the backhaul files.
We then calculate the STP, which is defined in (7). Base on Lemma 1, we can rewrite the
r
. Therefore, we can obtain the
STP as a combination of the STP conditioned on the given Fb,1

STP in Theorem 1.
Theorem 1. (STP) The STP is given by
Ps (Fc , t) =

X

qf Psf,c (tf ) +

f ∈Fc

X
f ∈F \Fc

qf

Fb
Ä
X
PF b F r

b,1

f

=k

k=1

ä

B
P b,
max (k, B) s

(13)

r
b
where PF
Fb,1
= k is given in (10), qf is given in (1), Psf,c (tf ) and Psb are the STPs of the
f

Ä

ä

cached file f ∈ Fc and the backhaul file f ∈ F \ Fc , which are given by
Psf,c (tf )

tf
=
tf + l0c,f

1
Psb =
1 + l0b,f

τ 2\β
I−
tf + l0c,f

"

τ 2\β
I−
1 + l0b,f

"

#−1

!

D

c,f

,

(14)

1

#−1

!

Db,f

,
1

(15)

10

where k · k1 is the l1 induced matrix norm (i.e, ||B||1 = max1≤j≤n

Pm

i=1

|bij |, B ∈ Rm×n ), I is

an N × N identity matrix, Dc,f and Db,f are N × N Toeplitz matrices of the cached file f ∈ Fc
and the backhaul file f ∈ F \ Fc , which are given by




 n,f
l
1


 n,f
l2


 .
 ..












,








 0


Dn,f =

0
l1n,f

0

..
.

..

.

n ∈ {c, b},

(16)

n,f
n,f
n,f
0
lN
lN
−1, · · · l1

where l0c,f , l0b,f , lic,f and lib,f are given by
l0c,f
l0b,f
lic,f
lib,f

ñ

ô

Ç

2
2
2π
2τ
; 2 − ; −τ + (1 − tf ) csc
= tf
2 F1 1, 1 −
β−2
β
β
β
ñ
ô
2τ
2
2
=
; 2 − ; −τ ,
2 F1 1, 1 −
β−2
β
β
ñ
2τ i−2\β
2 2
2
= (1 − tf ) B( + 1, i − ) + tf
2 F1 i + 1, i −
β β
β
iβ − 2
ñ
ô
2τ i−2\β
2
2
=
; i + 1 − ; −τ , ∀i ≥ 1.
2 F1 i + 1, i −
iβ − 2
β
β

å

2π
τ 2\β ,
β

(17)
(18)

2
2
; i + 1 − ; −τ
β
β

ô

, ∀i ≥ 1, (19)
(20)

Here, 2 F1 (·) is the Gauss hypergeometric function and B(·) is the Beta function.
Proof. Considering the equivalent channel gain g1 ∼ Gamma(N, 1), the STP is a complex n-th
derivative of the interference Laplace transform LI (s) [20]. Utilizing the approach in [21], we
obtain the expressions of the STPs in lower triangular Toeplitz matrix representation as (14) and
(15). For details, please see Appendix B.
According to (8), we then obtain the ASE under given Fc and t
R(Fc , t) = λb Ps (Fc , t) log2 (1 + τ ).

(21)

For backhaul-limited multi-antenna networks, the change of the BS density λb and user density
Ä

ä

r
λu influence Ps (Fc , t) via the pmf of the backhaul request file, i.e., P Fb,1
= k . However, when

λu approaches infinity and λb remains finite, since all the backhaul files are requested by the
r
b
tagged BS (shown in Corollary 1), PF
Fb,1
= k is no longer related to λb . Therefore, when
f

Ä

ä

the user density is high and the design parameter Fc and t are given, deploying more BSs will

11

always increase the ASE.
From Theorem 1 and the definition of the ASE, we can derive a tractable expression of the
ASE for N = 1, i.e., the backhaul-limited single-antenna networks. The ASE of the backhaullimited single-antenna networks is given in the following corollary.
Corollary 2. (ASE of Single-Antenna Networks) The ASE of the cache-enabled single-antenna
networks with limited backhaul is given by
Ñ

RSA (Fc , t) = λb log2 (1 + τ )

Fb
r
b
X X
= k qf B
PF
Fb,1
qf tf
f
+
ζ1 (τ )tf + ζ2 f ∈F \Fc k=1 max (k, B) (ζ1 (τ ) + ζ2 )

ä

Ä

X
f ∈Fc

é

, (22)

where ζ1 (τ ) and ζ2 (τ ) satisfy
ñ

2τ
2
2
ζ1 (τ ) = 1 +
; 2 − ; −τ
2 F1 1, 1 −
β−2
β
β
Ç
å
2π
2π
ζ2 (τ ) =
csc
τ 2\β .
β
β

ô

Ç

å

2π
2π
−
csc
τ 2\β ,
β
β

(23)
(24)

The proof of Corollary 2 is similar to the proof of Theorem 1 except that the equivalent
channel gain g1 ∼ Exp(1).
B. Upper Bound and Asymptotic Analysis
In this part, we first derive an upper bound of the STP under given Fc and t. We then give
the asymptotic analytic results in high user density region. First, we introduce a useful lemma
to present a lower bound of the gamma distribution.
Lemma 2. [26]: Let g be a gamma random variable follows Gamma(M, 1). The probability
P(g < τ ) can be lower bounded by
P(g < τ ) > 1 − e−aτ
î

óM

,

(25)

1

where α = (M !)− M .
Utilizing the above lemma, we then obtain the upper bound of the STP as follows.
Theorem 2. (Upper Bound of STP) The upper bound of the STP is given by
Psu (Fc , t) =

X
f ∈Fc

qf Psu,f,c (tf ) +

X
f ∈F \Fc

qf

Fb
Ä
X
PF b F r
f

k=1

b,1

=k

ä

B
P u,b ,
max (k, B) s

(26)

12

where Psu,f,c (tf ) and Psu,b are the upper bounds of the STPs of the cached file f ∈ Fc and the
backhaul file f ∈ F \ Fc , which are given by
Psu,f,c (tf )
Psu,b

(−1)i+1 Ni tf
=
,
i=1 (θA (i) tf + θC (i))
Ä ä

N
X

(27)

(−1)i+1 Ni
=
,
i=1 (θA (i) + θC (i))
Ä ä

N
X

(28)

where
ñ

ô

2τ
2
2
θA (i) = 1 +
; 2 − ; −iατ
2 F1 1, 1 −
β−2
β
β
Ç
å
2π
2π
θC (i) =
csc
(iατ )2\β .
β
β

Ç

å

2π
2π
−
csc
(iατ )2\β
β
β

(29)
(30)

1

Here, α = (N !)− N is a constant related to the number of BS antennas N .
Proof. The STP of the cached file f ∈ Fc is
Psf,c (tf ) = P g1 > τ Ikx1 kβ
Ä

Ä

(a)

≤ 1 − EIkx1 kβ
=

N
X

=

(−1)

=

1 − exp −ατ Ikx1 k

β

ääN ò

Ä
ä
N
EIkx1 kβ exp −iατ Ikx1 kβ
i
!

i+1

(−1)

i=1
(b)

Ä

!

i+1

i=1
N
X

ïÄ

ää

Ä
ä
N
Ekx1 kβ LI iατ kx1 kβ
i

(−1)i+1

N
X
i=1 tf



2τ
F
β−2 2 1

h

1, 1 − β2 ; 2 − β2 ; −iατ

i

ÄN ä
i

tf



+ 1 + (1 − tf ) 2π
csc
β



2π
β



(iατ )2\β

.

(31)

where (a) follows from g1 ∼ Gamma(N, 1) and Lemma 2, (b) follows from the PDF of kx1 k
fkx1 k (r) = 2πtf λb r exp {−πtf λb r2 } for f ∈ Fc and LI iτ kx1 kβ is given in Appendix B as
Ä



LI iτ kx1 kβ = exp −πλb
Ä

ä



2τ tf
F
β−2 2 1

h

1, 1 − β2 ; 2 − β2 ; −iατ

ä

i

+ (1 − tf ) 2π
csc
β



2π
β







(iατ )2\β kx1 k2 .

1

Here, α = (N !)− N .
Therefore, we obtain an upper bound of Psu,c,f (tf ) , ∀f ∈ Fc . We can obtain the expression
of Psu,b similarly and then finish the proof of Theorem 2.
The upper bound of the STP is a series of fractional functions of the cache placement t.
Comparing with the exact expression of the STP in Theorem 1, the upper bound approximates
the STP in a simpler manner, and therefore facilitates the analysis and further optimization.

13

According to Theorem 2, the upper bound of the ASE is given by
Ru (Fc , t) = λb Psu (Fc , t) log2 (1 + τ ).

(32)

To obtain design insights, we then analyze the upper bound of the ASE in the asymptotic
r
region, i.e., the high user density region. When λu → ∞, the discrete random variable Fb,1
→ Fb

in distribution as shown in Corollary 1. Therefore, we have the following corollary according to
Theorem 2.
Corollary 3. (Asymptotic Upper Bound of ASE) In high user density region, i.e., λu → ∞, the
asymptotic upper bound of the ASE is given by

Ö

Ru,∞ (Fc , t) = λb log2 (1 + τ )

è
X

qf Psu,f,c (tf ) +

f ∈Fc

X
f ∈F \Fc

qf B
P u,b
max (Fb , B) s

,

(33)

where Psu,f,c (tf ) and Psu,b are given in (27) and (28).
We plot Fig. 2 and Fig. 3 to validate the correctness of the analytic results. Fig. 2 plots the
successful transmission probability vs. the number of BS antennas and target SIR. Fig. 2 verifies
Theorem 1 and Theorem 2, and demonstrates the tightness of the upper bound. Fig. 2 also
shows that the successful transmission probability increases with the number of BS antennas
and decreases with the SIR threshold. Moreover, Fig. 2 (a) indicates that when the user density
is large, the increase of the BS density increases the successful transmission probability. Fig. 3
plots the area spectrum efficiency vs. user density by showing that when the user density is larger
than a certain threshold, i.e., 6 × 10−3 m−2 for the single-antenna networks and 4 × 10−3 m−2 for
the multi-antenna networks, the asymptotic upper bound of the ASE is nearly same as the ASE.
V. ASE O PTIMIZATION
A. General ASE Optimization
In this part, we solve the ASE maximization problem, i.e., maximize R(Fc , t) via optimizing
the file allocation Fc and the cache placement t. Based on the relationship between R(Fc , t)
and Ps (Fc , t), the ASE optimization problem is formulated as follows.

14

0.7

λ b =5 × 10 -4 m-2

0.8

0.7

0.6
λ b =10 -4 m-2

0.5

Upper Bound
Theo.
Monte Carlo

0.4

2

3

4

5

6

7

8

9

Theoritical
Monte Carlo

0.5
N=1
0.4
N=2
0.3

0.2

N=3

0.1

0.3
1

Upper Bound

0.6

Successful Transmission Probability

Successful Transmission Probability

0.9

0
-10

10

-5

0

5

10

15

20

SIR Threshold (dB)

The number of BS antennas N

(b) STP vs. SIR threshold τ at λb = 10−4 m−2 .

(a) STP vs. the number of BS antennas N at τ = 0dB.

Fig. 2. STP vs. the number of BS antennas N and SIR threshold τ . λu = 10−3 m−2 , β = 4, F = 8, B = C = 2,

Fb = {1, 2, 3, 4}, Fc = {5, 6, 7, 8}, t = (0.8, 0.6, 0.4, 0.2), γ = 1. In this paper, the transmit power is 6.3W, the
noise power in the Monte Carlo simulation is σn = −97.5dBm [32], the theoretical results are obtained without
consideration of noise. The Monte Carlo results are obtained by averaging over 106 random realizations.

55

Area Spectrum Efficiency(bits/Hz/km 2 )

N=3

Upper Bound
Theo.
Monte Carlo
Asym.

50

45

40
N=2
35
N=1
30

25
1

2

3

4

5

6

User Density λu (m -2 )

7

8

9

10
× 10-3

Fig. 3. The ASE vs. user density λu . λb = 10−4 m−2 , β = 4, F = 8, B = C = 2, Fb = {1, 2, 3, 4}, Fc = {5, 6, 7, 8},
t = (0.8, 0.6, 0.4, 0.2), γ = 1, τ = 0dB.

Problem 1. (ASE Optimization)
R∗ , max λb Ps (Fc , t) log2 (1 + τ )
Fc ,t

s.t.

(34)

(2), (3), (4).

where Ps (Fc , t) is given in (13).
The above problem is a mixed-integer problem to optimize the discrete parameter Fc and the
continuous parameter t. To solve the complex problem, we first explore optimal properties of
the discrete variable Fc and then optimize the continuous variable t. To optimally design the

15

file allocation Fc , we first study the properties of the STPs of the cached file and backhaul file,
i.e., Psf,c (tf ) and Psb . Based on the properties of the lower triangular Toeplitz matrix form in
(14) and (15), we then obtain the following lemma.
Lemma 3. Psf,c (tf ) and Psb have following properties:
1) Psf,c (tf ) is bounded by
tf
tf
≤ Psf,c (tf ) ≤
,
µA tf + νA
µB tf + νB

(35)

where µA , νA , µB and νB are given by
Ç

å

ñ

2π
2τ
2
2
2π
csc
τ 2\β +
; 2 − ; −τ
µA = 1 −
2 F1 1, 1 −
β
β
β−2
β
β
+

N
−1
X
i=1

N −i
2τ i
2
2
; i + 1 − ; −τ
2 F1 i + 1, i −
N
iβ − 2
β
β
ñ

ñ

ô

ô

ô

2 2
2
− B( + 1, i − )τ 2\β , (36)
β β
β

N
−1
X
2π
2π
N −i2 2
2
νA =
csc
τ 2\β −
B( + 1, i − )τ 2\β ,
β
β
N β β
β
i=1

Ç

å

Ç

å

ñ

2π
2π
2τ
2
2
µB = 1 −
csc
τ 2\β +
; 2 − ; −τ
2 F1 1, 1 −
β
β
β−2
β
β
+

N
−1 ñ
X
i=1

2
2
2τ i
; i + 1 − ; −τ
2 F1 i + 1, i −
iβ − 2
β
β
ñ

ô

(37)
ô

ô

2 2
2
− B( + 1, i − )τ 2\β ,
β β
β

N
−1
X
2π
2π
2
2 2
2\β
νB =
csc
τ
−
B( + 1, i − )τ 2\β ).
β
β
β
β
i=1 β

Ç

(38)

å

(39)

Furthermore, νA , νB are positive and µA , µB are no larger than 1.
2) Psf,c (tf ) is an increasing function of tf .
3) Psf,c (tf ) is no larger than Psb and no smaller than 0, i.e., 0 ≤ Psf,c (tf ) ≤ Psb .
Proof: See Appendix C.
Property 1 in Lemma 3 shows that the bounds of Psf,c (tf ) are fractional functions of tf . The
expressions of the bounds are similar to the expression of the STP of the cached file in singleantenna networks given in Theorem 2. Based on the properties of Psf,c (tf ) and Psb , we have the
following theorem to reveal the properties of the optimal file allocation Fc∗ .
Theorem 3. (Property of the Optimal File Allocation Fc∗ ) To optimize cached file set Fc for
Problem 1, we should allocate at least C files and at most F − B files to store in the cache,
that is to say, Fc∗ = {C, C + 2, · · · , F − B}.

16

Proof. We utilize the contradiction to prove Theorem 3. More specifically, we consider the cases
in which we cache less than C files or more than F − B files, and we then prove that the cases
are not optimal in terms of the ASE. For details, please see Appendix D.
The above theorem interprets that for optimal file allocation, the number of cached files
should be larger than the cache size and the number of the backhaul files shoud be larger than
the backhaul capability, indicating that we should make full use of the resources.
Based on Theorem 3, we can reduce the complexity of search for Fc∗ . Otherwise, we have
to check the cases such that Fc < C or Fc > F − B. When B or C is large, Theorem 3 will
largely reduce the complexity. Under given Fc , we optimize the cache placement t. The ASE
optimization over t under given Fc is formulated as follows
Problem 2. (Cache Placement Optimization under Given Fc )
R∗ (Fc ) , max λb
t

s.t.

X

qf Psf,c (tf ) log2 (1 + τ )

(40)

f ∈Fc

(3), (4).

where Psf,c (tf ) is given in (14).
The optimal solution for Problem 2 is denoted as t∗ (Fc ). The above problem is a continuous
optimization problem of a differentiable function over a convex set and we can use the gradient
projection method to obtain a local optimal solution. Under given Fc , we can obtain optimal
cache placement t∗ (Fc ) using Algorithm 1.
Algorithm 1 Optimal Solution to Problem 2
1.
2.
3.
4.
5.
6.

7.
8.

Initialization: n = 1, nmax = 104 and ti (1) = F1c for all i ∈ Fc . Constant lower triangular
Toeplitz matrix ∂B
is given in (55).
∂ti
repeat
CalculateÄDc,i with täi = ti (n) according to (16) for all i ∈ Fc .
Bi (n) = ti (n) + l0c,i I − τ 2\β Dc,i for all i ∈ Fc .
0
−1
∂B −1
ti (n+1) = ti (n)+s(n) B−1
λb log2 (1+τ )qi for all i ∈ Fc .
i (n) − ti (n)Bi (n) ∂ti Bi (n)
1

î

0

ó1

ti (n + 1)
=
ti (n + 1) − u∗ 0 for all i
∈
Fc , where
î
ó
P
0
∗ 1
1
i∈Fc ti (n + 1) − u 0 = C and [x]0 denotes max{min{1, x}, 0}.
n = n + 1.
until Convergence or n is larger than nmax .

u∗

satisfying

17

From Corollary 2, we can easily observe that when N = 1, i.e., in the single-antenna networks,
the objective function of Problem 2 is concave and the Slaters condition is satisfied, implying
that strong duality holds. In this case, we can obtain a closed-form optimal solution to the convex
optimization problem using KKT conditions. After some manipulations, we obtain the optimal
cache placement t∗ under given Fc for single-antenna networks.
Corollary 4. (Optimal Cache Placement of Single-Antenna Networks) When the cached file set
Fc is fixed, the optimal cache placement t∗ of the single-antenna networks is given by


1
t∗f = 
ζ1 (τ )

Ñs

é1

λb log2 (1 + τ )qf ζ2 (τ )
− ζ2 (τ )  , f ∈ Fc ,
u∗

(41)

0

where [x]10 denotes max{min{1, x}, 0} and u∗ is the optimal dual variable for the constraint
∗ ti
i∈FC

P

≤ C, which satisfies


1

f ∈FC ζ1 (τ )
X

Ñs

é1

λb log2 (1 + τ )qf ζ2 (τ )
− ζ2 (τ )  = C.
u∗

(42)

0

Here ζ1 (τ ) and ζ2 (τ ) are given in (23) and (24), respectively.
Finally, combining the analysis of the properties of Fc∗ in Theorem 3 and the optimization of
t under given Fc , we can obtain (Fc∗ , t∗ ) to Problem 1. The process of solving Problem 1 is
summarized in Algorithm 2.
Algorithm 2 Optimal Solution to Problem 1
1. Initialization: R∗ = ∞.
2. for Fc = C : F − B do
3.
Choose Fc ∈ {X ⊆ F : |X | = Fc }.
4.
Obtain the optimal solution t∗ (Fc ) to Problem 2 using Algorithm 1 (when N > 1) or
Corollary 4 (when N = 1).
5.
if R∗ < R (Fc , t∗ (Fc )) then
6.
R∗ = R (Fc , t∗ (Fc )), (Fc∗ , t∗ ) = (Fc , t∗ (Fc )).
7.
end if
8. end for
Algorithm 2 includes two layers. In the outer layer, we search Fc∗ by checking all the possible
PF −B ÄF ä
i=C

i

choices, and in the inner layer, we utilize Algorithm 1 or Corollary 4 to obtain t∗ (Fc )

under given Fc . We refer to the optimal solution based on Algorithm 2 as Exact Opt..

18

B. Asymptotic ASE Optimization based on the Upper Bound in (33)
In Algorithm 2, we need to consider

PF −B ÄF ä
i=C

i

choices and the complexity is Θ(F F ). When F

is very large, Algorithm 2 is not acceptable due to high complexity. Furthermore, the expression
of Psf,c (tf ) is complex and we need to calculate the matrix inverse to obtain the derivative of
tf . Thus Algorithm 2 requires high complexity if the number of antennas is large. Note that
the upper bound of the STP closely approximates the STP, as illustrated in Fig. 2, therefore we
utilize the upper bound of the STP, i.e., Psu,f,c (tf ) to approximate Psf,c (tf ). To facilitate the
optimization, we formulate the problem of optimizing the asymptotic upper bound of the ASE
to provide insightful guidelines for the parameter design in the high user density region. Based
on the Corollary 3, the asymptotic optimization problem is formulated as follows.
Problem 3. (Asymptotic ASE Optimization)
∗
Ru,∞
, max Ru,∞ (Fc , t)
Fc ,t

s.t

(2), (3), (4).

(43)

The above problem is a mixed-integer problem. By carefully investigating the characteristic
of Ru,∞ (Fc , t), which is a series of fractional functions of t in (33), we obtain the following
lemma to reveal the properties of Ru,∞ (Fc , t).
Lemma 4. Under a given Fc , Ru,∞ (Fc , t) is an increasing function of tf for any f ∈ Fc .
Proof: See Appendix E.
Based on the properties of the asymptotic upper bound Ru,∞ (Fc , t), we then analyze the
properties of the optimal file allocation Fc∗ and obtain Fc∗ as a unique solution.
Theorem 4. (Asymptotic Optimal File Allocaiton) In high user density region, i.e., λu → ∞,
the optimal cached file FC∗ is given by FC∗ = {B + 1, B + 2, · · · , F }.
Proof. We first prove that the number of optimal cached files is F − B and then prove that the
optimal F − B cached files are the least F − B popular files. For details, please see Appendix
F.
Theorem 4 interprets that we should transmit B most popular files via the backhaul and cache
the remaining files when the user density is very large. Compared to the process of checking

Area Spectrum Efficiency(bps/Hz/km 2 )

19

80

70

60
Exact.Opt.
Asym.Opt.

50

40
4
3
2

Number of Antennas N

1

4000

5000

6000

7000

8000

9000

10000

User Density λu (km -2 )

Fig. 4. Comparison between Exact Opt. and Asym. Opt.. λb = 10−4 m−2 , β = 4, F = 6, B = C = 2, γ = 0.6, τ = 0dB.

PF −B ÄF ä
i=C

choices in Algorithm 2, we get a unique optimal solution of file allocation and thus

i

largely reduce the complexity. When Fc∗ is given, we only need to optimize the continuous
variable t. We then use the gradient projection method get the local optimal solution. The
algorithm is summarized in Algorithm 3.
Algorithm 3 Optimal Solution to Problem 3
1.

Initialization: n = 1, nmax = h 104 , Fc∗ = {B + 1, Bi + 2, · · · , F }, ti (1) = F1c for all
2τ
2
2
i ∈ Fc∗ , θA (j) = 1 + β−2
− 2π
csc 2π
(jατ )2\β , θC (j) =
2 F1 1, 1 − β ; 2 − β ; −jατ
β
β


2π
β

2.
3.
4.

5.
6.

csc
repeat

2π
β



(jατ )2\β for all j ∈ {1, 2, · · · , N }.
Ç

0

ti (n + 1) = ti (n) + s(n)
î

0

PN

(−1)j+1 (N
θ (j)
j) C

j=1 (θA (j)ti (n)+θC (j))2
ó
∗ 1

å

λb log2 (1 + τ )qi for all i ∈ Fc .

∈
Fc , where
ti (n + 1)
=
ti (n + 1) − u 0 for all i
î 0
ó
P
∗ 1
1
i∈Fc ti (n + 1) − u 0 = C and [x]0 denotes max{min{1, x}, 0}.
n = n + 1.
until Convergence or n is larger than nmax .

u∗

satisfying

Algorithm 3 is guaranteed to converge because the gradient projection method converges to
a local optimal point for solving a problem whose feasible set is convex. In Algorithm 3, the
calculation of the matrix inverse (Step 5 in Algorithm 1) and the search for Fc∗ (Step 3 in
Algorithm 2 ) are avoided. Therefore, Algorithm 3 achieves lower complexity comparing to
Algorithm 2. We refer to the caching scheme based on Algorithm 3 as Asym. Opt..
Now we utilize simulations to compare the proposed Exact Opt. (the optimal solution obtained
by Algorithm 2) and Asym. Opt. (the asymptotic optimal solution obtained by Algorithm 3). From
Fig. 4, we can see that the performance of Asym. Opt. is very close to that of Exact Opt., even

20

when the user density is low. Therefore, Algorithm 3 with low complexity is applicable and
effective for parameter design in general region.
VI. N UMERICAL R ESULTS
In this section, we compare the proposed asymptotic optimal caching scheme given by Algorithm 3 with three caching schemes, i.e., the MPC (most popular caching) scheme [8], the UC
(uniform caching) scheme [10] and the IID (identical independent distributed caching) scheme
[11]. In the MPC scheme, the BSs cache or use backhaul to deliver the most popular B +C files.
In the IID scheme, the BSs select B + C files to cache or transmit via the backhaul in an i.i.d
manner with probability qi for file i. In the UC scheme, the BSs select B+C files according to the
uniform distribution to cache or deliver via the backhaul. Note that in simulations, we consider the
noise. Unless otherwise stated, our simulation environment parameters are as follows: P = 6.3W,
σn = −97.5dBm, λb = 10−4 m−2 , λu = 5 × 10−3 m−2 , β = 4, F = 500, τ = 0dB.
Fig. 5 and Fig. 6 illustrate the area spectrum efficiency vs. different parameters. We observe
that the proposed asymptotic optimal scheme outperforms all previous caching schemes. In
addition, out of the previous caching schemes, the MPC scheme achieves the best performance
and the UC scheme achieves the worst performance.
Fig. 5 (a) plots the ASE vs. the number of BS antennas. We can see that the ASE of all the
schemes increases with the number of BS antennas. This is because the increase of the number
of BS antennas leads to larger spatial diversity and thus achieves better performance. It is shown
that the increase of the number of BS antennas leads to an increasing gap between the proposed
asymptotic optimal caching scheme and previous caching schemes. This is because the better
performance of a larger number of BS antennas leads to a larger gain when we exploit the file
diversity. Furthermore, for asymptotic optimal caching scheme, the less popular files are more
likely to be stored when the number of BS antennas is large. Fig. 5 (b) plots the ASE vs. the
Zipf parameter γ. We can see that the ASE of the proposed asymptotic optimal caching scheme,
the MPC scheme and the IID scheme increases with the increase of the Zipf parameter γ. This
is because when γ increases, the probability that the popular files are requested increases, and
hence, the users are more likely to require the popular files from the nearby BSs who cache the
files or obtain the files via backhaul. The change of the Zipf parameter γ have no influence to
the ASE of the UC scheme. This is because in the UC scheme, all the files are stored/fetched

40

80

35

70

Area Spectrum Efficiency(bps/Hz/km 2 )

Area Spectrum Efficiency(bps/Hz/km 2 )

21

30

25

20

15
Asym.Opt.
MPC
IID
UC

10

5
1

2

3

4

5

6

7

8

9

60

50

40
Asym.Opt.
MPC
IID
UC

30

20

10
0.3

10

0.4

0.5

0.6

The number of BS antennas N

0.7

0.8

0.9

1

1.1

1.2

Zipf Parameter γ

(a) Number of BS antennas at C = 30, B = 20, γ = 0.6.

(b) Zipf parameter at N = 8, C = 30, B = 20.

Fig. 5. ASE vs. the number of BS antennas N and Zipf parameter γ.

50

60

Area Spectrum Efficiency(bps/Hz/km 2 )

Area Spectrum Efficiency(bps/Hz/km 2 )

55
50
45
40
35
30
25
Asym.Opt.
MPC
IID
UC

20
15
10
10

45
40
35
30
25
20

Asym.Opt.
MPC
IID
UC

15
10

20

30

40

50

60

70

80

90

100

Cache Size C

(a) Cache size at N = 8, B = 20, γ = 0.6.

110

0

5

10

15

20

25

30

35

40

45

50

Backhaul Capacity B

(b) Backhaul capability at N = 8, C = 30, γ = 0.6.

Fig. 6. ASE vs. cache size C and backhaul capability B.

with the same probability, and the change of the file popularity by altering γ has no influence
to the ASE.
Fig. 6 plots the ASE vs. the cache size C or the backhaul capability B. From Fig. 6, we can
see that the ASE of all the schemes increases with the cache size and the backhaul capability
because the probability that a randomly requested file is cached at or delivered via the backhaul
increases. The increase of the cache size leads to the increase of the gap between the proposed
asymptotic optimal caching scheme and the MPC scheme. This is because when the cache size
is small, the ASEs of the proposed caching scheme and the MPC scheme mainly come from the
spectrum efficiency of the backhaul files, which is same for the proposed caching scheme and the
MPC scheme. The increase of the cache size can bring larger gains of caching diversity. However,
the increase of the backhaul capability has no influence to the gap between the proposed caching

22

scheme and the previous caching schemes.
VII. C ONCLUSION
In this paper, we consider the analysis and optimization of random caching in backhaul-limited
multi-antenna networks. We propose a file allocation and cache placement design to effectively
improve the network performance. We first derive an exact expression and an upper bound of the
successful transmission probability, using tools from stochastic geometry. Then, we consider the
area spectrum efficiency maximization problem with continuous variables and integer variables.
We obtain a local optimal solution with reduced complexity by exploring optimal properties,
and we also solve an asymptotic optimization problem in high user density region, utilizing the
upper bound as the objective function. Finally, we show that the proposed asymptotic optimal
caching scheme achieves better performance compared with the existing caching schemes, and
the gains are larger when the number of the antennas is larger and/or the Zipf parameter is
smaller.
A PPENDIX
A. Proof of Lemma 1
According to the thinning theory of the PPP, the density of the users that require file f
is qf λu . We define Pi as the probability that file i is requiring by the BS. Note that Pi is
equivalent to the probability that the number of the users requiring file i is not zero, which is


Pi = 1 − 1 +


qi λu −4.5
3.5λb

according to [33]. When file f is requested by a certain BS, to calculate

r
, we need to consider the rest Fb − 1 files out of {Fb \ f } because file f is always
the pmf of Fb,1

requested by the BS. We define the file from the set {Fb \ f } as rest backhaul file and the file
r
from the set {Fb,1
\ f } as rest backhaul request file. To calculate the probability that the number
r
b
of the rest backhaul request files is k, i.e., PF
Fb,1
− 1 = k , we combine all the probabilities
f

Ä

ä

of the cases when any given k − 1 rest backhaul files are required and the Fb − k rest backhaul
r
b
Fb,1
files are not required. Therefore, PF
= k is given by
f

Ä

r
b
PF
Fb,1
−1=k =
f

Ä

ä

X

ä

Y

Y∈{X ⊆{Fb \f }:|X |=k} i∈X

Therefore we finish the proof of Lemma 1.

Pi

Y
i∈B\X

(1 − Pi ) , k = {0, 1, · · · , Fb − 1}.

(44)

23

B. Proof of Theorem 1
The STP of f ∈ Fc is given by
Ä

Psf,c (tf ) = P SIRf > τ

ä

= P g1 > τ Ikx1 kβ
Ä

(a)

= Ex1

ä

ä
(−1)m τ m kx1 kmβ (m) Ä
LI
τ kx1 kβ ,
m!
m=0

"N −1
X

#

where (a) follows from g1 ∼ Gamma(N, 1), I ,

P

i∈{Φb \1}

(45)

kxi k−β gi , LI (s) , EI [exp(−Is)] is

(m)

the Laplace transform of I, and LI (s) is the mth derivative of LI (s).
Denote s = τ kx1 kβ and ym =

(−1)m sm (m)
LI (s),
m!

guish the the interference, we define I f =

we have Psf,c (tf ) = Ex1

P

i∈Φfb \Bf,0

kx1 k−β gi and I −f =

N −1
m=0

îP

ó

ym . To distin-

P

i∈Φ−f
\Bf,0
b

kx1 k−β gi .

We then have LI (τ kx1 kβ )) = LI f (τ kx1 kβ ))LI −f (τ kx1 kβ )).
Therefore, we can derive the expression of LI f τ kx1 kβ ) as follows
Ä







X



i∈{Φfb \1}

β
LI f τ kx1 kβ ) = E 
exp −τ kx1 k


Ä

ä

"

ä





kxi k−β gi 


1
=
E
1 + τ kx1 kβ kxi k−β
i∈{Φfb \1}

(a)

#

Y

!

Z ∞

!

1
1−
= exp −2πtf λb
rdr
kx1 k
1 + τ kx1 kβ r−β
Ç
ô
ñ
å
2τ
2
2
2
= exp −πtf λb
; 2 − ; −τ kx1 k ,
2 F1 1, 1 −
β−2
β
β

(b)

(46)

where (a) follows from gi ∼ exp(1) due to the random beamforming effect, (b) follows from
the probability generating functional (PGFL) of the PPP [27]. Similarly, we have
LI −f τ kx1 kβ =
Ä

ä

Y

E exp −τ kx1 kβ kxi k−β gi
î

¶

©ó

i∈Φ−f
b

Z ∞

1
= exp −2π(1 − tf )λb
1−
0
1 + τ kx1 kβ r−β
å
Ç
Ç
å
2π
2π
2
2\β
= exp −π(1 − tf )λb csc
τ kx1 k .
β
β

!

!

rdr
(47)

24

Therefore, the expression of LI (τ kx1 kβ )) is given by
Ç

β

ñ

Ç

ô

2
2
2τ
; 2 − ; −τ
tf
2 F1 1, 1 −
β−2
β
β

LI (τ kx1 k )) = exp −πλb

Ç

å

å

To further calculate the STP, we need to calculate the nth derivative of Laplace transform
(n)

LI (s). After some calculations, we can derive the following recursive relationship
(n)

LI (s) =

n−1
X
i=0
n−1
X

+

i=0



!

n−1
(−1)n−i (n − i)! 
πtf λb
i



Z ∞


kx1 k2

v

!

n−1
(−1)n−i (n − i)! 
π(1 − tf )λb
i

n−i

− β2

1 + sv





Z ∞


0

− β2



dv  (i)
n−i+1  LI (s)

β

v− 2

n−i

1 + sv

− β2

dv



 (i)
n−i+1  LI (s).

(48)

According to the definition of yn and s, we have
yn = a

n−1
X
i=0

Ö

where li =

(1 − tf )


R∞
0

β

w− 2

i

β
1+w− 2



n−i
l y,
n n−i i


dw

+ tf

i+1

R∞

τ −2\β



β

w− 2

i
β

1+w− 2

(49)
è

dw

, i = {1, 2, · · · , N − 1} and a =

i+1

πλb kx1 k2 τ 2\β . Note that li can be expressed as the combination of the Gauss hypergeometric
function and the Beta function, which is presented in Theorem 1. Let l0 =
2
; −τ
β

ò

+ (1 − tf ) 2π
csc
β

Å

2π
β

ã

ã

Å

2τ
tf β−2
2 F1

ï

1, 1− β2 ; 2−

τ 2\β and we then have y0 = LI (τ kx1 kβ )) = exp −πλb l0 kx1 k2 .
Ä

ä

To get the expression of yn , we need to solve a series of linear equality. We then construct a
Toeplitz matrix as [21] and after some manipulations, we obtain Psf,c (tf ) as follows


Psf,c (tf )

= Ex1  y0

N
−1
X
i=0



1 i i 
aD
,
i!

(50)

1

where kk1 is the l1 induced matrix norm and the expression of D is






l
 1



 l2


 .
 ..












.








0

D=

0
l1

0

..
.

..

lN lM −2 · · ·

l1

.

å

2π
2π
+ (1 − tf ) csc
τ 2\β kx1 k2 .
β
β

(51)

0

According to the thinning of the PPP, the PDF of the distance of the closest f -cached BS

25

2

to the typical user is 2πtf λb kx1 ke−πtf λb kx1 k . After taking expectation over x1 and utilizing the
Taylor expansion, the STP is given by
Psf,c

"

tf
(tf ) =
tf + l0

τ 2\β
I−
tf + l0

#−1

!

D

.

(52)

1

We can obtain Psb , f ∈ Fb similarly and we omit the details due to space limitation.
C. Proof of Lemma 3
ï

Firstly, we prove the property 1. Let A , I −
tf
tf +l0c,f

Å

τ 2\β
tf +l0c,f

ã

Dc,f

ò

and we have Psf,c (tf ) =

kA−1 k1 . We first derive the lower bound of kA−1 k1 . For any x and y satisfying y = A−1 x,

we have kA−1 k1 ≥

kyk1
kxk1

due to the inequality kyk1 ≤ kA−1 k1 kxk1 . Let y = [1, 1, · · · , 1]T and

then we have
A−1

1

≥

kyk1
=
kxk1
N−

N
τ 2\β
tf +l0c,f

PN −1
i=1

(N − i)lic,f

.

(53)

We then derive the upper bound of kA−1 k1 . Noticing that A−1 = (I − A) A−1 + I and using
the triangle inequality, we have kA−1 k1 ≤ k(I − A)k1 kA−1 k1 + kIk1 . Therefore, we obtain the
upper bound of kA−1 k1 as follows
A−1

1

≤

kIk1
=
1 − k(I − A)k1
1−

1
τ 2\β
tf +l0c,f

PN −1 c,f .

li

i=1

tf
kA−1 k1 , we get the bounds of Psf,c (tf ) as
tf +l0c,f
c,f
lic,f and l0c,f in Theorem 1. It can be shown that li+1,

(54)

Note that Psf,c (tf ) =

(35) after substituting

the expression of

≤ lic,f for i ∈ N and

l0c,f =

c,f
i=1 li , ∀tf

P∞

∈ [0, 1]. Moreover, lic,f decreases with tf for i ∈ N. Therefore, after carefully

checking the properties of νA , µA , νB and µB , we obtain property 1.
Secondly, we prove property 2. We define B , tf + l0c,f A and then we have Psf,c (tf ) =
Ä

ä

ktf B−1 k1 . Furthermore, the derivative of B w.r.t. tf is a lower triangular Toeplitz matrix and




























,








1 − k0

∂B
=
∂tf

k1

1 − k0

k2

k1

..
.

..
.

kN −1

kN −2

1 − k0
...
···

k1 1 − k0

(55)

26

where k0 and ki , i ∈ {1, 2, · · · , N − 1} are given by
Ç

å

ñ

ô

2π
2τ
2
2
2π
csc
τ 2\β −
; 2 − ; −τ ,
(56)
k0 =
2 F1 1, 1 −
β
β
β−2
β
β
ñ
ô
2
2τ 2\β
2
2
2τ i
2
ki =
B( + 1, i − ) −
; i + 1 − ; −τ , 1 ≤ i ≤ N − 1. (57)
2 F1 i + 1, i −
β
β
β
iβ − 2
β
β
Then we derive the derivative of Psf,c (tf ) w.r.t. tf as follows
∂Psf,c (tf )
∂(tf B−1 )
=
∂tf
∂tf

1

∂B −1
B
∂tf

= B−1 − tf B−1
1
≥
tf
≥

1

1
tf B−1
tf

1
tf B−1
=
tf
Note that 1 − k0 +

PN −1
i=1

ki ≤ 1 − k0 +

1
∂Psf,c (tf )
≥
tf B−1
∂tf
tf

−1 ∂B

−1

tf B


1

1

1

1

− tf B
1−

∂tf

!
−1

B tf
1

!

∂B
∂tf

tf B−1

1

1

1 − 1 − k0 +

N
−1
X

!

!
−1

ki

tf B

P∞

i=1

.

1

i=1

(58)

ki = 1, therefore we have

1 − tf B−1


1

=

Ä
ä
1 f,c
Ps (tf ) 1 − Psf,c (tf ) .
tf
∂Psf,c (tf )
∂tf

Note that Psf,c (tf ) ∈ [0, 1], we then finish the proof of property 2 because

(59)
≥0

Finally, we prove property 3. Note that Psf,c (tf ) = Psb if and only if tf = 1. According to
property 2, we have Psf,c (tf ) ≤ Psb . According to property 1, the upper bound and the lower
bound of Psf,c (tf ) are both 0 if tf = 0, therefore we have Psf,c (tf ) = 0 if tf = 0.
D. Proof of Theorem 3
To prove property 1 is equivalent to prove that B ≤ |Fb∗ | ≤ F − C for optimizing Ps (Fc , t).
We first prove that |Fb∗ | ≤ F − C. Suppose that there exists optimal (Fb∗ , t∗ ) to problem 1
0

Ä

0

satisfying |Fb | > F − C. Now we construct a feasible solution Fb , t

ä

to problem 1, where

0

0

Fb is the set of the most popular F − C files of Fb∗ , the elements of t are same as t∗ if
0

0

Ä

0

f ∈ {F \ Fb∗ } and are one if f ∈ {Fb∗ \ Fb }. Due to the fact that Fc ≤ C, Fb , t

0

ä

is a

feasible solution satisfying the constraints. Note that Psf,c (tf ) = Psb if tf = 1 , we then have
0

0

Ps (t , F \ Fb ) − Ps (t∗ , F \ Fb∗ ) =

P



0

f ∈Fb∗ \Fb

qf Psf,c (1) −

PFb

k=1

Ä

r
P Fb,1
=k

ä

B
Pb
max(k,B) s

which contradicts with the optimality of (Fb∗ , t∗ ). Therefore, we prove |Fb∗ | ≤ F − C.



> 0,

27

We then prove that |Fb∗ | ≥ B. Suppose that there exist optimal (Fb∗ , t∗ ) to problem 1 satisfying
0

Ä

0

0

ä

|Fb | < B. Now we construct a feasible solution Fb , t to problem 1, where Fb is the combining
0

0

of Fb∗ and any B − |Fb∗ | files in {F \ Fb∗ }, the elements of t are same as t∗ if f ∈ {F \ Fb }.
When |Fb | ≤ B, Ps (Fc , t) =
0

P

f ∈Fc

qf Psf,c (tf ) +

0

then have Ps (t , F \ Fb ) − ps (t∗ , F \ Fb∗ ) =

P

f ∈F \Fc

P

f ∈Fb, \Fb∗

qf Psb . Note that Psb ≥ Psf,c (tf ) , we

Ä

ä

qf Psb − Psf,c (tf ) ≥ 0, which contradicts

with the optimality of (Fb∗ , t∗ ). Therefore, we prove |Fb∗ | ≥ B.
E. Proof of Lemma 4
To prove Lemma 4 is equivalent to prove Psu,f,c (tf ) is increasing w.r.t. tf for f ∈ Fc .
qf tf
ζ1 (ατ )tf +ζ2 (ατ )

When N = 1, we have Psu,f,c (tf ) =

and it is increasing w.r.t. tf . We then

consider the scenario when N ≥ 2. According to the proof of the upper bound, Psu,f,c (tf ) =
1 − EIkx1 kβ

ïÄ

Ä

1 − exp −ατ Ikx1 k

Psu,f,c (tf ) = 1 − Ekx1 kβ

β

ääN ò

. After taking expectation over I, we have

ïÄ

1 − exp πλb ((1 − ζ1 (ατ )) tf − ζ2 (ατ )) kx1 k2
Ä

ääN ò

,

(60)

where ζ1 (ατ ) and ζ2 (ατ ) are given in (23) and (24).
Let U (tf |x1 ) , 1 − exp πλb ((1 − ζ1 (ατ )) tf − ζ2 (ατ )) kx1 k2
Ä

Ä

ää

and we have

Ä
ä
Ä
ä
∂U N (tf |x1 )
= N πλb kx1 k2 (ζ1 (ατ ) − 1) U N −1 (tf |x1 ) exp πλb ((1 − ζ1 (ατ )) tf − ζ2 (ατ )) kx1 k2 .
∂tf
∂U N (tf |x1 )
∂tf

Note that ζ1 (ατ ) < 1 and ζ2 (ατ ) > 0, we have

< 0 and U N (tf |x1 ) is a decreasing
î

ó

function of tf for any x1 . Therefore, Psu,f,c (tf ) = 1 − Ekx1 kβ U N (tf |x1 ) is an increasing
î

ó

function of tf . This is because Ekx1 kβ U N (tf |x1 ) can be interpreted as a combination of a
series of U N (tf |x1 ) with different x1 and the monotonicity holds.
F. Proof of Theorem 4
To prove Fc∗ = {B + 1, B + 2, · · · , F } is equivalent to prove Fb∗ = {1, 2, · · · , B}.
Firstly we prove that |Fb∗ | ≤ B. Suppose that there exist optimal (Fb∗ , t∗ ) to problem 1
satisfying |Fb∗ | > B and then we have max (Fb∗ , B) = Fb . Now we construct a feasible solution
Ä

0

0

Fb , t

ä

0

to problem 3, where Fb is the set of the most popular B files of Fb∗ , the elements of

0

0

t are same as t∗ if f ∈ {F \ Fb∗ } and are zero if f ∈ {Fb∗ \ Fb }. Note that Psu,f,c (tf ) = 0
0

0

u
u
if and only if tf = 0 , we then have Rs,∞
(t , F \ Fb ) − Rs,∞
(t∗ , F \ Fb∗ ) = λb log2 (1 +

τ)

Å
P

0

f ∈Fb

qf Psu,b
B

−

ã
u,b

P

f ∈Fb∗

qf Ps
Fb

B > 0 because Psu,b > 0, which contradicts with the optimality

of (Fb∗ , t∗ ). Therefore, we can prove |Fb∗ | ≤ B.

28

Secondly we prove that |Fb∗ | ≥ B. Note that Psu,f,c (tf ) increases w.r.t. tf and Psu,f,c (tf ) ≤
Psu,b , therefore we can easily prove |Fb∗ | ≥ B similarly as Appendix D.
Combining the results |Fb∗ | ≤ B and |Fb∗ | ≥ B, we have |Fb∗ | = B. Finally we prove
Fb∗ = {1, 2, · · · , B}. Suppose that there exists optimal (Fb∗ , t∗ ) to problem 1 satisfying |Fb∗ | = B
0

Ä

0

and Fb 6= {1, 2, · · · B}. We construct a feasible solution Fb , t
0

Ä

{1, 2, · · · B}, the elements of t are same as t∗ if f ∈ {F \ Fb∗
0

¶

in order for the rest files, i.e., tfn = t∗fm , fn ∈ Fb∗
¶

n and m denote the order of the file in Fb∗
0

u
Fb ) − Rs,∞
(t∗ , F \ Fb∗ ) = λb log2 (1 + τ )

τ)

P

fn ∈{Fb∗

T

Fc0 } qfn

we then obtain
q fn

Psu,b − Psc,b t∗fm

Ä

Ä

0

0

0

©

P

©

0

fm ∈{Fb

¶

T

to problem 3, where Fb =
S
0

¶

Fc , fm ∈ Fb
0

Fc and Fb

0

ä

Fb } and are same as t∗
T

©

Fc∗ , n = m. Note that
0

©

u
Fc∗ . We then have Rs,∞
(t , F \

T

Fc∗ } qfm

Ä

Ä

Psu,b − Psc,b t∗fm

Ä

ää

ää
Ä

ä

− λb log2 (1 +
0

ä

Psu,b − Psc,b tfn . Note that Psu,b −Psc,b t∗fm = Psu,b −Psc,b tfn if m = n,

0
0
u
u
(t∗ , F \Fb∗ )
(t , F \Fb )−Rs,∞
Rs,∞

Å

ãÅ

Ä

T

T

0

ä

ãã

= λb log2 (1+τ )

Å
P

0 T

m∈{1,2,··· ,|{Fb

Fc∗ }|}

q fm −

> 0. The last inequality is because qfm > qfn if n = m and Psu,b >

ä

Psc,b t∗fm .
R EFERENCES
[1] N. Bhushan, J. Li, D. Malladi, R. Gilmore, D. Brenner, A. Damnjanovic, R. T. Sukhavasi, C. Patel, and S. Geirhofer,
“Network densification: the dominant theme for wireless evolution into 5G,” IEEE Communications Magazine, vol. 52,
no. 2, pp. 82–89, February 2014.
[2] J. G. Andrews, S. Buzzi, W. Choi, S. V. Hanly, A. Lozano, A. C. K. Soong, and J. C. Zhang, “What will 5G be?” IEEE
Journal on Selected Areas in Communications, vol. 32, no. 6, pp. 1065–1082, June 2014.
[3] X. Wang, M. Chen, T. Taleb, A. Ksentini, and V. C. M. Leung, “Cache in the air: exploiting content caching and delivery
techniques for 5G systems,” IEEE Communications Magazine, vol. 52, no. 2, pp. 131–139, February 2014.
[4] A. Liu and V. K. N. Lau, “Cache-enabled opportunistic cooperative MIMO for video streaming in wireless systems,” IEEE
Transactions on Signal Processing, vol. 62, no. 2, pp. 390–402, Jan 2014.
[5] ——, “Exploiting base station caching in MIMO cellular networks: Opportunistic cooperation for video streaming,” IEEE
Transactions on Signal Processing, vol. 63, no. 1, pp. 57–69, Jan 2015.
[6] M. Tao, E. Chen, H. Zhou, and W. Yu, “Content-centric sparse multicast beamforming for cache-enabled cloud RAN,”
IEEE Transactions on Wireless Communications, vol. 15, no. 9, pp. 6118–6131, Sept 2016.
[7] J. G. Andrews, F. Baccelli, and R. K. Ganti, “A tractable approach to coverage and rate in cellular networks,” IEEE
Transactions on Communications, vol. 59, no. 11, pp. 3122–3134, November 2011.
[8] E. Baştuğ, M. Bennis, M. Kountouris, and M. Debbah, “Cache-enabled small cell networks: Modeling and tradeoffs,”
EURASIP Journal on Wireless Communications and Networking, vol. 2015, no. 1, pp. 1–11, 2015.
[9] C. Yang, Y. Yao, Z. Chen, and B. Xia, “Analysis on cache-enabled wireless heterogeneous networks,” IEEE Transactions
on Wireless Communications, vol. 15, no. 1, pp. 131–145, Jan 2016.
[10] S. T. ul Hassan, M. Bennis, P. H. J. Nardelli, and M. Latva-Aho, “Modeling and analysis of content caching in wireless
small cell networks,” in 2015 International Symposium on Wireless Communication Systems (ISWCS), Aug 2015, pp.
765–769.

29

[11] B. B. Nagaraja and K. G. Nagananda, “Caching with unknown popularity profiles in small cell networks,” in 2015 IEEE
Global Communications Conference (GLOBECOM), Dec 2015, pp. 1–6.
[12] Y. Cui, D. Jiang, and Y. Wu, “Analysis and optimization of caching and multicasting in large-scale cache-enabled wireless
networks,” IEEE Transactions on Wireless Communications, vol. 15, no. 7, pp. 5101–5112, July 2016.
[13] Y. Cui and D. Jiang, “Analysis and optimization of caching and multicasting in large-scale cache-enabled heterogeneous
wireless networks,” IEEE Transactions on Wireless Communications, vol. 16, no. 1, pp. 250–264, Jan 2017.
[14] J. Wen, K. Huang, S. Yang, and V. O. K. Li, “Cache-enabled heterogeneous cellular networks: Optimal tier-level content
placement,” IEEE Transactions on Wireless Communications, vol. 16, no. 9, pp. 5939–5952, Sept 2017.
[15] Z. Chen, J. Lee, T. Q. S. Quek, and M. Kountouris, “Cooperative caching and transmission design in cluster-centric small
cell networks,” IEEE Transactions on Wireless Communications, vol. PP, no. 99, pp. 1–1, 2017.
[16] S. Kuang and N. Liu, “Cache-enabled base station cooperation for heterogeneous cellular network with dependence,” in
2017 IEEE Wireless Communications and Networking Conference (WCNC), March 2017, pp. 1–6.
[17] D. Liu and C. Yang, “Caching policy toward maximal success probability and area spectral efficiency of cache-enabled
HetNets,” IEEE Transactions on Communications, vol. PP, no. 99, pp. 1–1, 2017.
[18] X. Yu, C. Li, J. Zhang, and K. B. Letaief, “A tractable framework for performance analysis of dense multi-antenna
networks,” arXiv preprint arXiv:1702.04573, 2017.
[19] L. H. Afify, H. ElSawy, T. Y. Al-Naffouri, and M. S. Alouini, “A unified stochastic geometry model for MIMO cellular
networks with retransmissions,” IEEE Transactions on Wireless Communications, vol. 15, no. 12, pp. 8595–8609, Dec
2016.
[20] H. S. Dhillon, M. Kountouris, and J. G. Andrews, “Downlink MIMO HetNets: Modeling, ordering results and performance
analysis,” IEEE Transactions on Wireless Communications, vol. 12, no. 10, pp. 5208–5222, October 2013.
[21] C. Li, J. Zhang, and K. B. Letaief, “Throughput and energy efficiency analysis of small cell networks with multi-antenna
base stations,” IEEE Transactions on Wireless Communications, vol. 13, no. 5, pp. 2505–2517, May 2014.
[22] C. Li, J. Zhang, J. G. Andrews, and K. B. Letaief, “Success probability and area spectral efficiency in multiuser MIMO
HetNets,” IEEE Transactions on Communications, vol. 64, no. 4, pp. 1544–1556, April 2016.
[23] C. Li, J. Zhang, M. Haenggi, and K. B. Letaief, “User-centric intercell interference nulling for downlink small cell
networks,” IEEE Transactions on Communications, vol. 63, no. 4, pp. 1419–1431, April 2015.
[24] X. Yu, J. Zhang, M. Haenggi, and K. B. Letaief, “Coverage analysis for millimeter wave networks: The impact of directional
antenna arrays,” arXiv preprint arXiv:1702.04493, 2017.
[25] T. Bai and R. W. Heath, “Coverage and rate analysis for millimeter-wave cellular networks,” IEEE Transactions on Wireless
Communications, vol. 14, no. 2, pp. 1100–1114, Feb 2015.
[26] H. Alzer, “On some inequalities for the incomplete gamma function,” Mathematics of Computation of the American
Mathematical Society, vol. 66, no. 218, pp. 771–778, 1997.
[27] M. Haenggi, Stochastic geometry for wireless networks.

Cambridge University Press, 2012.

[28] L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker, “Web caching and Zipf-like distributions: evidence and implications,”
in INFOCOM ’99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings.
IEEE, vol. 1, Mar 1999, pp. 126–134 vol.1.
[29] A. M. Hunter, J. G. Andrews, and S. Weber, “Transmission capacity of ad hoc networks with spatial diversity,” IEEE
Transactions on Wireless Communications, vol. 7, no. 12, pp. 5058–5071, December 2008.
[30] F. Baccelli, B. Blaszczyszyn, and P. Muhlethaler, “An aloha protocol for multihop mobile wireless networks,” IEEE
Transactions on Information Theory, vol. 52, no. 2, pp. 421–436, Feb 2006.

30

[31] W. C. Cheung, T. Q. S. Quek, and M. Kountouris, “Throughput optimization, spectrum allocation, and access control in
two-tier femtocell networks,” IEEE Journal on Selected Areas in Communications, vol. 30, no. 3, pp. 561–574, April 2012.
[32] H. Holma and A. Toskala, LTE for UMTS-OFDMA and SC-FDMA based radio access.

John Wiley & Sons, 2009.

[33] S. Singh, H. S. Dhillon, and J. G. Andrews, “Offloading in heterogeneous networks: Modeling, analysis, and design
insights,” IEEE Transactions on Wireless Communications, vol. 12, no. 5, pp. 2484–2497, May 2013.

