Partition-based Caching in Large-Scale SIC-Enabled Wireless Networks

Existing designs for content dissemination do not fully explore and exploit potential caching and computation capabilities in advanced wireless networks. In this paper, we propose two partition-based caching designs, i.e., a coded caching design based on Random Linear Network Coding and an uncoded caching design. We consider the analysis and optimization of the two caching designs in a large-scale successive interference cancelation (SIC)-enabled wireless network. First, under each caching design, by utilizing tools from stochastic geometry and adopting appropriate approximations, we derive a tractable expression for the successful transmission probability in the general file size regime. To further obtain design insights, we also derive closed-form expressions for the successful transmission probability in the small and large file size regimes, respectively. Then, under each caching design, we consider the successful transmission probability maximization in the general file size regime, which is an NP-hard problem. By exploring structural properties, we successfully transform the original optimization problem into a Multiple-Choice Knapsack Problem (MCKP), and obtain a near optimal solution with 1/2 approximation guarantee and polynomial complexity. We also obtain closed-form asymptotically optimal solutions. The analysis and optimization results show the advantage of the coded caching design over the uncoded caching design, and reveal the impact of caching and SIC capabilities. Finally, by numerical results, we show that the two proposed caching designs achieve significant performance gains over some baseline caching designs.


I. INTRODUCTION
The rapid proliferation of smart mobile devices has triggered an unprecedented growth of the global mobile data traffic. Recently, caching at base stations (BSs) has been proposed as a promising approach for massive content delivery by reducing the distance between popular files and their requesters [1]- [3]. As the cache size is limited in general, designing caching strategies appropriately is a prerequisite for efficient content dissemination. The performance of a caching design is highly affected by the file diversity it provides. In [4]- [7], the authors consider large-scale wireless network models where the stochastic nature of geographic locations of BSs and users is characterized using stochastic geometry. In particular, in [4], the authors consider caching the most popular files at each BS, which does not provide file diversity. In [5], the authors consider random caching with files being stored at each BS in an i.i.d. manner, which may store multiple copies of a file at one BS and yield storage waste. In [6], [7], the authors consider random caching and multicasting on the basis of file combinations consisting of different files, and analyze and optimize the joint design. Note that the random caching designs in [5]- [7] can provide file diversity. However, in [5]- [7], a file transmission may not make full use of the file diversity provided by the random caching designs, when the serving BS of the file is not close to the file requester. In addition, the caching designs proposed in [4]- [7] require storing entire files at each BS, which may restrict file diversity and limit the potential of caching.
To further improve file diversity, in [8]- [12], files are partitioned into multiple subfiles, and each BS stores an uncoded or coded subfile of a file. For instance, in [8] and [9], the authors propose network coding-based caching designs, and analyze the cache miss probability [8] and minimize the occupied storage space [9], respectively. In [10] and [11], the authors propose MDS code-based caching designs, and minimize the backhaul rate [10] and average delay [11], respectively. In [12], the authors propose a partition-based uncoded caching design, and analyze the successful content delivery probability. Note that the network coding-based caching designs in [8], [9] are restricted to a single file and cannot be directly applied to practical networks with multiple files. In addition, the coded caching designs in [8]- [11] do not consider the delivery of the cached files, and hence may not yield good user experience. Compared to coded caching designs, the uncoded caching design in [12] may not sufficiently exploit storage resources. But [12] considers the delivery of the cached files, where successive interference cancelation (SIC) is employed at each user to decode all the uncoded subfiles of its desired file transmitted at the same time over the same frequency band. Given computational capability at users, applying SIC can facilitate the exploitation of file diversity, and hence improve the performance of the caching design.
SIC is a promising technique to improve the performance of wireless networks with relatively small additional computational complexity. The idea of SIC is to decode multiple signals sequentially by subtracting interference due to the decoded signals before decoding other signals.
The use of SIC hinges on the imbalance of the received powers of different signals, which come from transmitters at different locations in some cases. Conventional performance analysis of SIC is for wireless networks with transmitters residing at given locations [13]. To capture the impact of the spatial distribution of transmitters, recent studies attempt to reveal the gain of SIC in large-scale wireless networks utilizing tools from stochastic geometry [14]- [17]. In this context, approximations are often used due to the well-acknowledged challenge in tracking the problem directly. For instance, in [14], the authors characterize the performance of SIC using a guardzone based approximation, where the interferers inside a guard-zone centered at the receiver are assumed canceled, and the size of the guard-zone is used to model the SIC capability. In [15], the authors consider SIC based on power order, i.e., from the stronger signals to the weaker signals, and derive tractable bounds on the successful decoding probability. In [16] and [17], the authors consider SIC based on distance order, i.e., from the nearer transmitters to the farther transmitters, and obtain closed-form expressions for the coverage probabilities in heterogeneous networks and D2D networks, respectively, assuming independence between decoding events. Note that [13]- [17] focus on performance analysis of SIC in large-scale wireless networks without caching capability.
In summary, further studies are required to understand the fundamental impacts of communication, caching and computation (e.g., SIC) capabilities on network performance. In this paper, we shall shed some light on the essential problem. We consider multiple files and a large-scale SIC-enabled wireless network with random channel fading as well as stochastic locations of BSs and users. Our main contributions are summarized below.
• First, we propose two general partition-based caching designs, i.e., a coded caching design based on Random Linear Network Coding (RLNC) [18] and an uncoded caching design, which incorporate any deterministic and identical (same at all BSs) caching of entire files as a special case. Correspondingly, we transmit multiple coded or uncoded subfiles of a requested file at the same time over the same frequency band, and adopt SIC to decode February 7, 2017 DRAFT these subfiles for recovering the requested file.
• Then, we analyze the successful transmission probability. The challenge in analyzing partitionbased caching and SIC is commonly recognized. By utilizing tools from stochastic geometry and adopting appropriate approximations, under each caching design, we derive a tractable expression for the successful transmission probability in the general file size regime. We also show that the coded caching design outperforms the uncoded caching design in the general file size regime. To further obtain design insights, under each caching design, we derive closed-form expressions for the successful transmission probabilities in the small and large file size regimes, respectively, utilizing series expansion of some special functions.
These expressions reveal the impacts of caching and SIC capabilities. From the asymptotic analysis, we know that under each caching design, the successful transmission probability increases linearly as the file size decreases to zero, and decreases exponentially to zero as the file size increases to infinity.
• Next, we consider the successful transmission probability maximization by optimizing a design parameter. In the general file size regime, under each caching design, by exploring structural properties of the optimization problem which is NP-hard, we successfully transform the original optimization problem into a Multiple-Choice Knapsack Problem (MCKP), and obtain a near optimal solution with 1 2 approximation guarantee and polynomial complexity [19]. Under the coded caching design, we also obtain closed-form asymptotically optimal solutions in the small and large file size regimes, respectively. Under the uncoded caching design, we obtain a near optimal solution in the small file size regime and a closed-form asymptotically optimal solution in the large file size regime, respectively. From the asymptotic optimization results, we know that in the small file size regime, the optimal successful transmission probability under the coded caching design increases with the cache size and the SIC capability. While, in the large file size regime, the optimal successful transmission probabilities under both caching designs increase with the cache size and are not affected by the SIC capability. The asymptotic optimization results also demonstrate the advantage of the coded caching design over any deterministic and identical caching of entire files in the small file size regime.
• Finally, by numerical results, we show that the proposed coded caching design achieves a significant performance gain in the successful transmission probability in the general file size regime over the proposed uncoded caching design and some baseline caching designs.

A. Network Model
We consider a large-scale wireless network, as shown in Fig. 1. The locations of the base stations (BSs) are spatially distributed as a two-dimensional homogeneous Poisson point process We focus on a typical user u 0 , which we assume without loss of generality (w.l.o.g.) to be located at the origin. The BSs are labeled in ascending order of distance from u 0 . Let d i denote the distance between BS i ∈ Φ b and u 0 . Thus, we have d 1 ≤ d 2 ≤ · · · .
We consider the downlink transmission. Each BS has one transmit antenna and transmits with power P over bandwidth W . User u 0 has one receive antenna. Consider a discrete-time system with time being slotted. The duration of each time slot is T seconds. We study one slot of the network. We consider both path loss and small-scale fading. Specifically, due to path loss, transmitted signals with distance d are attenuated by a factor d −α , where α > 2 is the path loss exponent. For small-scale fading, we assume Rayleigh fading, i.e., each small-scale channel Let N {1, 2, · · · , N} denote the set of N files in the network. For ease of illustration, we assume that all files have the same size of S bits. Each file is of certain popularity. User u 0 randomly requests one file, which is file n ∈ N with probability a n ∈ (0, 1), where n∈N a n = 1.
Thus, the file popularity distribution is given by a (a n ) n∈N , which is assumed to be known apriori. In addition, w.l.o.g., we assume a 1 > a 2 . . . > a N .

B. Caching Designs
The network consists of cache-enabled BSs. In particular, each BS is equipped with a cache of size K ≥ 1 (in files), i.e., KS (in bits). Assume each BS cannot store all files in N due to the limited storage capacity, i.e., K < N. Now, we propose two caching designs, i.e., a coded caching design based on Random Linear Network Coding (referred to as RLNC caching design) [18] and an uncoded caching design (referred to as UC caching design), as illustrated in Fig. 1. Both are partition-based and are parameterized by s (s n ) n∈N , where s n ∈ {0} ∪ 1 m m ∈ N + , n ∈ N represents the amount of storage (in files) allocated to file n ∈ N at each BS. Here, N + denotes the set of positive integers. In particular, for any file n ∈ N , consider the following three cases.
(i) If s n = 0, file n is not stored at any BS. (ii) If s n = 1, file n is stored at each BS. (iii) If s n ∈ { 1 m |m = 2, 3, · · · }, file n is partitioned into 1 sn subfiles, each of s n S bits. In Case (i) and Case (ii), the two caching designs coincide. In Case (iii), the two caching designs differentiate with each other as follows.
• RLNC Caching Design in Case (iii): Each BS forms a random linear combination of all the 1 sn subfiles of file n (i.e., a coded subfile of file n which is of s n S bits) using RLNC, and stores it in its cache. We consider RLNC over a large field, and assume that file n can be decoded from any 1 sn coded subfiles of file n stored in the network [18]. • UC Caching Design in Case (iii): Each BS selects a random subfile from the 1 sn subfiles of file n according to the uniform distribution, and stores it in its cache.
The design parameter s of a feasible RLNC or UC caching design satisfies the following constraint n∈N s n ≤ K.
(1) caching designs, as illustrated in Fig. 1. The file transmission under the RLNC caching design is determined by parameter s only. While, the file transmission strategy under the UC caching design depends on parameter s and another parameter m (m n ) n∈N , where m n ∈ { 1 sn , 1 sn + 1, · · · } represents the number of (nearest) BSs serving the request for file n. Specifically, consider the following three cases. (i) If s n = 0, u 0 cannot obtain file n from a cache of the network under either caching design. 1 In this case, we set m n = 0 for the UC cachign design. (ii) If s n = 1, the nearest BS transmits file n to u 0 under both caching designs. In this case, we set m n = 1 for the UC cachign design. (iii) If s n ∈ { 1 m |m = 2, 3, · · · }, each of the 1 sn nearest BSs transmits the stored coded subfile of file n to u 0 under the RLNC caching design, and each of the m n nearest BSs transmits the stored uncoded subfile of file n to u 0 under the UC caching design.
Note that in Cases (ii) and (iii), the subfile transmission of each serving BS is over the whole bandwidth and time slot.
In Case (iii), for the RLNC caching design, file n can be decoded from the 1 sn coded subfiles of file n stored in the 1 sn nearest BSs; for the UC caching design, file n may not be successfully decoded from the m n uncoded subfiles of file n stored in the m n nearest BSs, as the m n subfiles may not cover the 1 sn different subfiles (due to the random placement of the 1 sn different subfiles under the UC caching design). For the UC caching design, let I j n ∈ N + denote the nearest BS storing the jth subfile of file n, where j ∈ {1, 2, · · · , 1 sn }, and denote I u n max I 1 n , I 2 n , · · · , I 1 sn n ∈ { 1 sn , 1 sn + 1, · · · }. Note that I j n , j ∈ {1, 2, · · · , 1 sn } and I u n are random variables with the randomness induced by the random subfile placement, and the probability mass functions (p.m.f.s) of I j n , j ∈ {1, 2, · · · , 1 sn } and I u n depend on s n . In particular, if I u n ≤ m n , file n can be decoded from the subfiles of file n stored in the m n nearest BSs; otherwise file n cannot be decoded. For ease of illustration, we also set I u n = ∞ in Case (i) (i.e., s n = 0) and I u n = 1 in Case (ii) (i.e., s n = 1). In this paper, we consider an interference-limited network and neglect the background thermal noise. We assume all BSs are active for serving their own users. Thus, the received signals of u 0 under the RLNC caching design and the UC caching design, denoted as y c n and y u n respectively, are given by where d i is the distance between BS i and u 0 , h i d ∼ CN (0, 1) is the small-scale channel between BS i and u 0 , x i is the transmit signal from BS i. The first sums in (2) and (3) represent the desired signals, and the second sums in (2) and (3) represent the interferences.
To extract multiple signals under each caching design, we adopt SIC. As in [16], we consider the distance-based decoding and cancelation order. 2 In particular, when decoding the signal from BS i, all signals from the nearer BSs in {1, 2, · · · , i − 1} need to be successfully decoded and canceled, where i ∈ {1, 2, · · · , 1 sn } for the RLNC caching design and i ∈ {1, 2, · · · , I u n } for the UC caching design. 3 The signal-to-interference ratio (SIR) of the signal from BS i after successfully decoding and canceling the signals from the nearer BSs in {1, 2, · · · , i − 1} is given where T , u 0 can successfully decode (and cancel) the signal from BS i. Due to the limited computational capability and the delay constraint, as in [16], we assume that u 0 has limited SIC capability M, which is a system parameter. That is, u 0 can perform decoding and cancelation at most M times to obtain its desired signals.
M} . Given SIC capability M, for the two proposed caching designs to be meanful, we require where (5) is for the RLNC caching design, and (6) is for the UC caching design. Note that when M = 1, (5) and (6)

D. Performance Metric
Requesters are mostly concerned about whether their desired files can be successfully received.
Therefore, in this paper, we consider the successful transmission probability of a file randomly requested by u 0 as the network performance metric. According to the file transmission and reception discussed in Section II-C, the successful transmission probabilities of file n ∈ N requested by u 0 under the RLNC caching design and the UC caching design, denoted as q c n (s n ) and q u n (s n , m n ) respectively, are given by where SIR i is given by (4). According to the total probability theorem, the successful transmission probabilities of a file randomly requested by u 0 under the RLNC caching design and the UC caching design, denoted as q c (s) and q u (s, m) respectively, are given by 4 q c (s) = n∈N a n q c n (s n ), s ∈ S N , q u (s, m) = n∈N a n q u n (s n , m n ), (s, m) ∈ U N .

III. PERFORMANCE ANALYSIS AND OPTIMIZATION OF RLNC CACHING DESIGN
In this section, we consider the performance analysis and optimization of the RLNC caching design. First, we analyze the successful transmission probabilities in the general file size regime, the small file size regime and the large file size regime, respectively. Then, we optimize the successful transmission probabilities in these regions.
As in [16], for the tractability of the analysis, we assume the independence between the events W log(1 + SIR j ) > snS T , j ∈ {1, 2, · · · , i}. Then, we have the following lemma.
where B ′ (x, y, z) Therefore, we have the successful transmission probability under the RLNC caching design, as summarized below.

Theorem 1 (Performance of RLNC in General File Size Regime):
The successful transmission probability q c (s) under the RLNC caching design is given by where q c n (s n ) is given by (10). From Theorem 1, we can see that q c (s) is a decreasing function of S. The impact of s on q c (s) is not obvious. Fig. 2 plots q c (s) versus S at different s. To further obtain design insights, in the following, we analyze the asymptotic successful transmission probabilities in the small file size regime and the large file size regime, respectively.

2) Performance Analysis in Small File Size Regime:
Utilizing series expansion of some special functions, from Theorem 1, we derive the asymptotic successful transmission probability in the small file size regime (i.e., S → 0) as follows.  1 General Here, 1[·] denotes the indicator function.
Proof: Please refer to Appendix B.
From Lemma 2, we know that lim S→0 q c (s) = n∈N a n 1 [s n = 0], and q c 0 (s) increases linearly to n∈N a n 1 [s n = 0] as S decreases to 0. In addition, s affects the asymptotic behavior of q c 0 (s) by affecting lim S→0 q c (s) and the coefficient of S. Fig. 3 (a) plots q c 0 (s) versus S in the small file size regime. We see from Fig. 3 (a) that when S decreases, the gap between each "General" curve, which is plotted using Theorem 1, and the corresponding "Asymptotic" curve, which is plotted using Lemma 2, decreases. Thus, Fig. 3 (a) verifies Lemma 2.

3) Performance Analysis in Large File
Size Regime: Utilizing series expansion of some special functions, from Theorem 1, we derive the asymptotic successful transmission probability in the large file size regime (i.e., S → ∞) as follows.

Lemma 3 (Performance of RLNC in Large File Size Regime):
Here, s max max{s n |n ∈ N } and B(x, y) From Lemma 3, we know that lim S→∞ q c (s) = 0, and q c ∞ (s) decreases exponentially to 0 as S increases to ∞. In addition, s affects the asymptotic behavior of q c ∞ (s) via s max only. Fig. 3 (b) plots q c ∞ (s) versus S in the large file size regime. We see from Fig. 3 (b) that when S increases, the gap between each "General" curve, which is plotted using Theorem 1, and the corresponding "Asymptotic" curve, which is plotted using Lemma 3, decreases. Thus, Fig. 3 verifies Lemma 3.

B. Performance Optimization of RLNC Caching Design 1) Performance Optimization in General File Size Regime:
The caching design affects the successful transmission probability q c (s) via design parameter s. We would like to maximize q c (s) by carefully optimizing s.

Problem 1 (RLNC Caching Design in General File Size Regime):
where q c (s) is given by (11). Let s * denote the optimal solution.
When M = 1, we have s n ∈ {0, 1} for all n ∈ N , and the proposed RLNC caching design degenerates to deterministic and identical caching of entire files. Based on structural properties of q c (s), we know that the optimal caching design is to store the most K popular entire files at each BS. When M ≥ 2, Problem 1 is a challenging discrete optimization problem with a complex objective function. The number of possible choices for s is given by O (M + 1) N .
Thus, a brute-force solution to Problem 1, i.e., exhaustive search, is not acceptable when N and M are large. In the following, we consider M ≥ 2. We aim to obtain a low-complexity solution with superior performance, by carefully exploiting structural properties of Problem 1. First, we convert Problem 1 into an MCKP, which is a generalization of the ordinary knapsack problem. In particular, there are N mutually disjoint classes C 1 , C 2 , · · · , C N , each containing M +1 items, to be packaged into a knapsack of capacity K. Item m ∈ M {1, 2, · · · , M} in class C n represents that the amount of storage allocated to file n is 1 m , and item M + 1 in class C n represents that the amount of storage allocated to file n is 0. The profit p n,m and weight w n,m of item m ∈ M + {1, 2, · · · , M + 1} in class C n are given by Note that w n,m , n ∈ N are the same for all m ∈ M + . Let x n,m ∈ {0, 1} represent whether item m in class C n is packaged into the knapsack, where x n,m = 1 indicates that item m in class C n is packaged into the knapsack. Thus, the profit sum is given by and the weight sum is given by n∈N m∈M+ w n,m x n,m .
Therefore, Problem 1 can be transformed into the following MCKP, which chooses exactly one item from each class such that the profit sum in (16) is maximized without exceeding the capacity K in the corresponding weight sum in (17). where q c (x) is given by (16). Let x * denote the optimal solution.

Problem 2 (Equivalent Problem of Problem 1 (MCKP)):
MCKP is an NP-hard problem, which can be easily shown by reduction from the ordinary knapsack problem. Like other Knapsack Problem variants, MCKP can be solved optimally using two approaches, i.e., the branch-bound method and dynamic programming, with non-polynomial complexity [20]. The increase in the number of items will cause the optimization complexity to increase rapidly. Thus, approximate solutions of polynomial complexity are widely adopted. For instance, the dynamic programming-based approximate solution proposed in [21] can achieve a performance that is no less than 1 − ǫ times the optimal value with running time polynomial to 1 ǫ , where ǫ ∈ (0, 1). Due to the integer requirement (i.e., both the weights and the profits must be positive integers), the dynamic programming-based approximate solution in [21] cannot be applied to Problem 2. In addition, the greedy solution proposed in [19] can achieve a performance that is no less than 1 2 times the optimal value with complexity O((M + 1)Nlog((M + 1)N)). In the following, we adopt the greedy method in [19] to obtain a near optimal solution to Problem 2 with 1 2 approximation guarantee. Before adopting the greedy solution in [19], we first introduce some key definitions.
Definition 1: [19] If two items i and j in the same class C n satisfy w n,i ≤ w n,j and p n,i ≥ p n,j , then item j is dominated by item i. If three items i, j, k in the same class C n with w n,i < w n,j < w n,k and p n,i < p n,j < p n,k satisfy p n,k −p n,j w n,k −w n,j ≥ p n,j −p n,i w n,j −w n,i , then item j is LP-dominated by items i and k.
By (14) and (15) Based on these optimality properties, a greedy method is proposed in [19] to solve MCKP. We adopt this greedy method to solve Problem 2, as summarized in Algorithm 1. The complexity of + 1)N)). The feasible solution x † to Problem 2 obtained by Algorithm 1 achieves a performance that is no less than 1 2 times the optimal value to Problem 2, i.e., q c (x † ) ≥ q c * 2 . Note that Step 1 can be conducted using the prune and search method proposed in [22]. In Step 2, as an initialization, we choose the lightest item M + 1 for each class. In 5: while W + w n,m ≤ K do 6: Set x n,m = 1, x n,m + = 0, and update W = W + w n,m − w n,m + and P = P + p n,m − p n,m + .

7:
Update l = l + 1. Let n, m be the indices satisfying λ n,m = λ(l).  Construct a feasible solution x (x i,j ) i∈N ,j∈M+ to Problem 2 by setting x n,m = 1, x i,j = 0 for i ∈ N , i = n or j ∈ M + , j = m.
14: end if optimal solution to Problem 2. Otherwise, x † is a feasible solution to Problem 2 with worst-case performance 1 2 .

2) Performance Optimization in Small File Size Regime:
In this part, we consider the optimization of the asymptotic successful transmission probability q c 0 (s) in the small file size regime.

Problem 3 (RLNC Caching Design in Small File Size Regime):
where q c 0 (s) is given by (12). By exploring structural properties of q c 0 (s), we can obtain the optimal caching design in the small file size regime.

Lemma 4 (Optimal Solution to Problem 3):
Suppose KM ≤ N. There exists S 0 > 0, such that for all S < S 0 , the optimal solution to Problem 3 is given by and the optimal value to Problem 3 is given by Proof: Please refer to Appendix D.
Lemma 4 indicates that in the small file size regime, when KM ≤ N, it is optimal to allocate the storage of each BS equally to the most KM popular files. That is, each of the most KM popular files is partitioned into M subfiles (each of S M bits), and each BS stores a coded subfile of each of the most KM popular files. The reason is as follows. In the small file size regime, the probability that u 0 can decode the signal from each of the M nearest BSs is high, and allocating the storage of each of the M nearest BSs equally to KM files maximizes the number of files that can be successfully decoded by u 0 . Thus, storing the most KM popular files obviously maximizes the successful transmission probability. In addition, Lemma 4 reveals that in the small file size regime, the optimal successful transmission probability increases with the product of the cache size and SIC capability, i.e., KM.

3) Performance Optimization in Large File Size Regime:
In this part, we consider the optimization of the asymptotic successful transmission probability q c ∞ (s) in the large file size regime.

Problem 4 (RLNC Caching Design in Large File Size Regime):
where q c ∞ (s) is given by (13). By exploring structural properties of q c ∞ (s), we can obtain the optimal caching design in the large file size regime.

Lemma 5 (Optimal Solution to Problem 4):
There exists S ∞ > 0, such that for all S > S ∞ , the optimal solution to Problem 4 is given by and the optimal value to Problem 4 is given by Proof: Please refer to Appendix E.
Lemma 5 indicates that in the large file size regime, it is optimal to allocate the storage of each BS equally to the most K popular files. That is, each BS stores each of the most K popular (entire) files. The reason is as follows. In the large file size regime, the probability that u 0 can decode the signal from any BS besides the nearest one is very small. Allocating the storage of the nearest BS to K uncoded files maximizes the number of files that can be successfully decoded by u 0 . Storing the most K popular files obviously maximizes the successful transmission probability. In addition, Lemma 5 reveals that in the large file size regime, the optimal successful transmission probability increases with cache size K and is not affected by SIC capability M.
Now, we use a numerical example to compare the optimal solution obtained by exhaustive search and the proposed near optimal solution obtained by Algorithm 1 in both successful transmission probability and computational complexity. We also use this example to verify the asymptotically optimal solutions obtained in Lemmas 4 and 5 in the asymptotic file size regimes. Fig. 4 plots the successful transmission probability versus file size S. We can see that the successful transmission probability of the proposed near optimal solution is very close to that of the optimal solution. While, the average computation time for the optimal solution is 3136 times of that for the near optimal solution. This demonstrates the applicability and effectiveness of the near optimal solution. In addition, we can see that the successful transmission probabilities of the asymptotically optimal solutions obtained by Lemmas 4 and 5 approach those of the optimal solutions in the small and large file size regimes, respectively, verifying Lemmas 4 and 5.

IV. PERFORMANCE ANALYSIS AND OPTIMIZATION OF UC CACHING DESIGN
In this section, we consider the performance analysis and optimization of the UC caching design. First, we analyze the successful transmission probabilities in the general file size regime, the small file size regime and the large file size regime, respectively. Then, we optimize the successful transmission probabilities in these regions.

A. Performance Analysis of UC Caching Design 1) Performance Analysis in General File Size Regime:
According to the total probability theorem, from (8) where h(s n , i) is given by (9). To calculate q u n (s n , m n ), it remains to calculate the p.m.f. of I u n . Collecting 1 sn different subfiles of file n under the UC caching design can be viewed as a classical Coupon Collector's Problem, where 1 sn distinct objects (i.e., coupons) are repeatedly drawn (with replacement) from an urn with probability s n of picking an object at each trial until each of the 1 sn objects is picked at least once. In particular, 1 sn different subfiles of file n can be regarded as 1 sn different objects in the Coupon Collector's Problem. The subfile of file n stored at BS i ∈ {1, 2, · · · , m n } can be regarded as the object drawn at the i-th trial in the Coupon Collector's Problem. Recovering file n (i.e., obtaining 1 sn different subfiles of file n) from the subfiles of file n stored at the i nearest BSs is equivalent to collecting all 1 sn types of objects within i trials in the Coupon Collector's Problem. Thus, I u n can be regarded as the minimum number of trials needed to get all 1 sn distinct objects in the Coupon Collector's Problem. From the results of the Coupon Collector's Problem [23], we have From (8), (9), (22) and (23)   Therefore, we have the successful transmission probability under the UC caching design, as summarized below.

Theorem 2 (Performance of UC in General File Size Regime):
The successful transmission probability q u (s, m) under the UC caching design is given by where q u n (s n , m n ) is given by (24). From Theorem 2, we can see that q u (s, m) is a decreasing function of S and an increasing function of m n for all n ∈ N . The impact of s on q u (s, m) is not obvious. By comparing Theorem 1 and Theorem 2, we have the following corollary.

Corollary 1 (Performance Comparison between RLNC and UC Caching Designs):
Given any caching design parameter s ∈ S N , the successful transmission probability under the RLNC caching design is greater than or equal to that under the UC caching design, i.e., q c (s) ≥ q u (s, m) for all m such that (s, m) ∈ U N , where the equality holds when s n ∈ {0, 1} for all n ∈ N .
2) Performance Analysis in Small File Size Regime: From Theorem 2, we derive the asymptotic successful transmission probability in the small file size regime (i.e., S → 0) as follows. Here, p(·, ·) is given by (23).
Proof: Lemma 6 can be proved in a similar way to Lemma 2. We omit the details due to page limitation.
From Lemma 6, we know that lim S→0 q u (s, m) = n∈N a n mn i= 1 sn p (s n , i), which represents the success probability of collecting all different subfiles of a randomly requested file, and q u 0 (s, m) increases linearly to n∈N a n mn i= 1 sn p (s n , i) as S decreases to 0. In addition, s affects the asymptotic behavior of q u 0 (s, m) by affecting lim S→0 q u (s, m) and the coefficient of S. Fig. 6 (a) plots q u 0 (s, m) versus S in the small file size regime. We see from Fig. 6 (a) that when S decreases, the gap between each "General" curve, which is plotted using Theorem 2, and the corresponding "Asymptotic" curve, which is plotted using Lemma 6, decreases. Thus, Fig. 6 (a) verifies Lemma 6.

3) Performance Analysis in Large File
Size Regime: From Theorem 2, we derive the asymptotic successful transmission probability in the large file size regime (i.e., S → ∞) as follows.

Lemma 7 (Performance of UC in Large File Size Regime):
For all (s, m) ∈ U N , we have q u (s, m) Here, p(·, ·) is given by (23).
Proof: Lemma 7 can be proved in a similar way to Lemma 3. We omit the details due to page limitation.
Note that q u ∞ (s) does not depend on m. From Lemma 7, we know that lim S→∞ q u (s, m) = 0, and q u ∞ (s) decreases exponentially to 0 as S increases to ∞. In addition, s affects the asymptotic behavior of q u ∞ (s) in the form of s max only. By comparing Lemma 3 and Lemma 7, we can see that in the large file size regime, the successful transmission probability under the UC caching design is p(s max , 1 smax ) of that under the RLNC caching design. Fig. 6 (b) plots q u ∞ (s) versus S in the large file size regime. We see from Fig. 6 (b) that when S increases, the gap between each "General" curve, which is plotted using Theorem 2, and the corresponding "Asymptotic" curve, which is plotted using Lemma 7, decreases. Thus, Fig. 6 (b) verifies Lemma 7. W = 10MHz, T = 1ms, M = 3, and a n = n −γ n∈N n −γ with γ = 1.

B. Performance Optimization of UC Caching Design
Note that q u (s, m) is an increasing function of m n for all n ∈ N . In the following, to study the optimal successful transmission probability under the UC caching design, we set Specifically, in the general file size regime, we focus on optimizing q u (s) n∈N a n q u n (s n , m n ) over s ∈ S N , where m is given by (28). In the small file size regime, we focus on optimizing q u 0 (s) q u 0 (s, m) over s ∈ S N , where m is given by (28). In the large file size regime, we focus on optimizing q u ∞ (s) over s ∈ S N . 1) Performance Optimization in General File Size Regime: The caching design affects the successful transmission probability q u (s) via design parameter s. We would like to maximize q u (s) by carefully optimizing s.

Problem 5 (UC Caching Design in General File Size Regime):
where q u (s) is given by (25). Let s * denote the optimal solution.
When M = 1, we have s n ∈ {0, 1} for all n ∈ N , and the proposed UC caching design degenerates to deterministic and identical caching of entire files. Based on structural properties of q u (s), we know that the optimal caching design is to store the most K popular entire files at each BS. When M ≥ 2, as Problem 1, Problem 5 can also be converted into an MCKP and solved with 1 2 approximation guarantee using the greedy method in [19].

2) Performance Optimization in Small File Size Regime:
In this part, we consider the optimization of the asymptotic successful transmission probability q u 0 (s) in the small file size regime.
Problem 6 (UC Caching Design in Small File Size Regime): where q u 0 (s) is given by (26). Similarly, Problem 6 can also be converted into an MCKP and solved with 1 2 approximation guarantee using the greedy method in [19].

3) Performance optimization in large file size regime:
In this part, we consider the optimization of the asymptotic successful transmission probability q u ∞ (s) in the large file size regime.

Problem 7 (UC Caching Design in Large File Size Regime):
where q u ∞ (s) is given by (27). By exploring structural properties of q u ∞ (s), we can obtain the optimal caching design in the large file size regime.
Lemma 8 (Optimal Solution to Problem 7): There exists S ∞ > 0, such that for all S > S ∞ , the optimal solution to Problem 7 is given by and the optimal value to Problem 7 is given by Lemma 8 indicates that in the large file size regime, it is optimal to allocate the storage of each BS equally to the most K popular files. That is, each BS stores each of the most K popular files. Note that the optimal UC caching design is the same as the optimal RLNC caching design in the large file size regime. This indicates that the advantage of the RLNC caching design over the UC caching design vanishes in the large file size regime.

V. NUMERICAL RESULTS
In this section, we compare the proposed near optimal RLNC caching design with the proposed near optimal UC caching design and three baselines in the existing literature. Baseline 1 refers to the caching design in which the most K popular entire files are stored at each BS (i.e., s n = 1 for n ∈ {1, 2, · · · , K}, and s n = 0 for n ∈ {K + 1, K + 2, · · · , N}) [4]. Baseline 2 refers to the random caching design in which all files in N are randomly stored at each BS with equal caching probability K N [24]. Baseline 3 refers to the random caching design in which file n ∈ N is stored at a BS with caching probability T n = min{a n K + µ, 1}, where c satisfies n∈N min{a n K +µ, 1} = K. 7 Under Baselines 1, 2 and 3, u 0 requesting file n is associated with the nearest BS which stores file n [6]. In the simulation, the popularity follows Zipf distribution, i.e., a n = n −γ n∈N n −γ , where γ is the Zipf exponent. We choose N = 1000, α = 4, W = 10MHz and T = 1ms. Fig. 7 illustrates the successful transmission probability versus different system parameters.
We can observe that the proposed RLNC caching design significantly outperforms the proposed UC caching design and the three baseline designs, and its performance increases much faster with the SIC capability and the cache size. This is because the proposed RLNC caching design wisely exploits SIC capability and storage resource. In addition, the two proposed partition-based caching designs have better performance than the three baseline designs, which focus on storing entire files. This is because the partition-based caching designs achieve higher file diversities than the caching designs storing entire files.
Specifically, Fig. 7 (a) illustrates the successful transmission probability versus the file size S. We can see that the performance gaps between the proposed RLNC caching design and the other caching designs are relative large at small S. This is because when S is small, the success probability of sequentially decoding multiple signals using SIC is relatively large, and hence, the benefit of high file diversity offered by the proposed RLNC caching design can be seen more clearly. under the three baseline designs, which store entire files, the successful transmission probability of an entire file from the nearest BS does not change with M. In addition, note that when M = 1, the successful transmission probabilities of the proposed RLNC and UC caching designs and Baseline 1 are the same. This is because as discussed in Sections III-B1 and IV-B1, the optimal RLNC and UC caching designs degenerate to Baseline 1, when M = 1. Fig. 7 (c) illustrates the successful transmission probability versus the cache size K. We can see that the performance of all the caching designs increases with K. This is because as K increases, each BS can store more files, and the probability that a randomly requested file can be obtained from the nearby BSs increases. Fig. 7 (d) illustrates the successful transmission probability versus the Zipf exponent γ. We can see that the performance of the proposed RLNC and UC caching designs, Baseline 1 and Baseline 3 increases with γ. This is because when γ increases, the probability that a requested file is a popular one increases. These popularity-aware caching designs store more popular files in the network, while Baseline 2 allocates the same storage resource to all the files.

VI. CONCLUSION
In this paper, we proposed two partition-based caching designs, i.e., a RLNC caching design and an UC caching design, and analyzed and optimized the two caching designs in a large-scale SIC-enabled wireless network. First, by utilizing tools from stochastic geometry and adopting appropriate approximations, we analyzed the successful transmission probabilities in the general file size regime and the two asymptotic file size regimes. We also showed that the RLNC caching design outperforms the UC caching design in the general file size regime, and the successful transmission probability of each proposed caching design decreases linearly with the file size in the small file size regime, and decreases exponentially with the file size in the large file size regime. Then, for each proposed caching design, by exploring structural properties, we successfully transformed the original caching optimization problem, which is NP-hard, into an MCKP problem, and obtained a near optimal solution with 1 2 approximation guarantee and polynomial complexity in the general file size regime. We also obtained closedform asymptotically optimal solutions. The asymptotic optimization results show that in the small file size regime, the optimal successful transmission probability under the RLNC caching design increases with the cache size and the SIC capability. While, in the large file size regime, the optimal successful transmission probability of each proposed caching design increases with the cache size and is not affected by the SIC capability.
APPENDIX A: PROOF OF LEMMA 1 First, the conditional probability of successfully decoding the subfile of file n stored at BS j after successfully decoding and canceling the signals from the nearer BSs in {1, 2, · · · j − 1}, conditioned on d j = x, is given by where (a) is obtained based on (4), and (b) is obtained by noting that |h j | 2 d ∼ exp (1). To calculate p n,j,d j (s n , x) using (31), we only need to calculate L I j (s, x). The expression of L I j (s, x) is calculated as follows where (c) is obtained by utilizing the probability generating functional of PPP [25, Page 235], and (d) is obtained by first replacing s − 1 α r with t, and then replacing 1 1+t −α with w. Substituting s = 2 snS W T − 1 x α into (32), we have Next, we calculate the probability of successfully decoding the signal from BS j after successfully decoding and canceling the signals from the nearer BSs in {1, 2, · · · j − 1}, denoted as p n,j (s n ), by removing the condition of p n,j,d j (s n , x) on d j = x. Note that we have the p.d.f. of d j as Finally, by assuming the independence between the events W log(1+SIR j ) > snS T , j ∈ {1, 2, · · · , i} [16], we have h(s n , i) = i j=1 p n,j (s n ) = 1 We complete the proof of Lemma 1.

APPENDIX B: PROOF OF LEMMA 2
Consider any file n ∈ N . When s n = 0, we have q c n (s n ) = 0 as S → 0. It remains to calculate q c n (s n ) as S → 0 for s n ∈ S \ {0}. We note that B Thus, as S → 0, we have 8 q c n (s n ) = h s n , where (a) is due to (33), (b) is due to 2 x − 1 = (ln2)x + o(x) as x → 0, (c) is due to ∼ q c 0 (s). Therefore, we complete the proof of Lemma 2.
APPENDIX C: PROOF OF LEMMA 3 Consider any file n ∈ N . When s n = 0, we have q c n (s n ) = 0 as S → ∞. It remains to calculate q c n (s n ) as S → ∞ for s n ∈ S \ {0}. We note that B ′ (a, b, z) = B(a, b) − z a a + o(z a ), as z → 0. Thus, as S → ∞, we have In addition, from (9) and (10) Substituting feasible solution s * given in (20) into (13), we have q c ∞ (s * ) = n∈N a n 1[s * On the other hand, for any feasible solution s to Problem 4, we have q c ∞ (s) = n∈N a n 1[s n = s max ] Thus, we have q c ∞ (s) q c ∞ (s * ) = n∈N a n 1[s n = s max ] n∈N a n 1[s * n = 1] For any feasible solution s = s * to Problem 4, we show q c ∞ (s) q c ∞ (s * ) < 1 for large S by considering the following three cases. (i) If s max = 1, based on (41), we have q c ∞ (s) q c ∞ (s * ) = n∈N a n 1[s n = 1] n∈N a n 1[s * n = 1] .