PaperlayerView exact revision on arXiv

Source-linked AI summary

Analysis and Optimization of Caching and Multicasting in Large-Scale Cache-Enabled Heterogeneous Wireless Networks

Ying Cui, Dongdong Jiang

arXiv:1604.00645v2cs.ITmath.IT

TL;DR

The paper addresses joint caching and multicasting optimization in backhaul-constrained HetNets. It proposes hybrid tiered caching and multicasting, analyzes successful transmission probability, and reports that its design outperforms three baseline schemes.

  • Problem

    Existing work has focused on small-BS cache placement; this paper addresses joint caching-and-multicasting optimization for backhaul-constrained HetNets, a mixed discrete-continuous design problem.

    Source: §I · p. 2, A. Optimization Problem · p. 16, §IX · p. 25

  • Method

    The authors propose identical macro-tier and random pico-tier caching with corresponding multicasting, derive successful-transmission-probability expressions via stochastic geometry, and use a two-step optimization framework.

    Source: §I · pp. 3–4, §IX · p. 26

  • Results

    Numerical results show the proposed design outperforms all three baseline schemes in successful transmission probability.

    Source: §VIII · p. 25

  • Takeaways & Limitations

    The analysis and optimization results offer design insights for practical cache-enabled HetNets.

    Source: §IX · p. 26

Abstract

from arXiv · show

Heterogeneous wireless networks (HetNets) provide a powerful approach to meet the dramatic mobile traffic growth, but also impose a significant challenge on backhaul. Caching and multicasting at macro and pico base stations (BSs) are two promising methods to support massive content delivery and reduce backhaul load in HetNets. In this paper, we jointly consider caching and multicasting in a large-scale cache-enabled HetNet with backhaul constraints. We propose a hybrid caching design consisting of identical caching in the macro-tier and random caching in the pico-tier, and a corresponding multicasting design. By carefully handling different types of interferers and adopting appropriate approximations, we derive tractable expressions for the successful transmission probability in the general region as well as the high signal-to-noise ratio (SNR) and user density region, utilizing tools from stochastic geometry. Then, we consider the successful transmission probability maximization by optimizing the design parameters, which is a very challenging mixed discrete-continuous optimization problem due to the sophisticated structure of the successful transmission probability. By using optimization techniques and exploring the structural properties, we obtain a near optimal solution with superior performance and manageable complexity. This solution achieves better performance in the general region than any asymptotically optimal solution, under a mild condition. The analysis and optimization results provide valuable design insights for practical cache-enabled HetNets.

I. INTRODUCTION … A. Hybrid Caching

The paper studies joint caching and multicasting for massive content delivery in large-scale HetNets with backhaul constraints. It proposes a hybrid tiered caching design and develops analysis and optimization of successful transmission probability.

I. INTRODUCTION

  • HetNets address mobile traffic growth but require costly backhaul, and prior designs may fail to combine spatial file diversity, popularity awareness, and backhaul constraints.The paper frames its work around how physical-layer and content parameters affect performance and how caching and multicasting can jointly support dissemination.Source: §I · pp. 2–3
  • The proposed framework combines identical macro-tier caching and random pico-tier caching with a corresponding multicast design for efficient content dissemination.The hybrid caching design is intended to provide spatial file diversity while the multicast design exploits the wireless medium's broadcast nature.Source: §I · pp. 3–4
  • The analysis derives tractable successful-transmission-probability expressions for general and asymptotic regions, revealing effects of physical-layer and content-related parameters.It handles different interferer types and uses appropriate approximations and stochastic geometry.Source: §I · p. 4
  • The two-step optimization framework yields a near-optimal solution that outperforms any asymptotically optimal solution in the general region under a mild condition.The method characterizes structural properties of asymptotically optimal solutions before using them to construct the near-optimal solution.Source: §I · p. 4
  • Numerical simulations show that the near-optimal solution significantly increases successful transmission probability over baseline schemes.Source: §I · p. 4

II. NETWORK MODEL

  • The network model is a two-tier downlink HetNet with independently Poisson-distributed macro-BSs, pico-BSs, and users, under backhaul constraints.Files have known popularity shared across users, and each macro-BS has a wireline backhaul link with limited per-slot retrieval capacity.Source: §II · pp. 4–5

III. JOINT CACHING AND MULTICASTING

  • The joint design addresses limited storage and backhaul resources that may leave file requests unsatisfied, while seeking high spatial diversity and efficient dissemination.Source: §III · pp. 5–6

A. Hybrid Caching

  • The hybrid design stores non-overlapping file sets across tiers, with every macro-BS caching the same Kc_1 files and each pico-BS randomly caching Kc_2 files from the pico-tier set.The design is specified by the macro-tier file set, pico-tier file set, and probabilities for selecting pico-tier combinations.Source: A. Hybrid Caching · pp. 6–7

B. Multicasting … A. Performance Analysis in General Region

The paper combines content-centric association and multicast scheduling with a successful-transmission metric for a cache-enabled HetNet. It derives a general-region expression for that metric from file-load and SINR analyses, using approximations where needed.

B. Multicasting

  • Macro-users associate with the nearest macro-BS, while pico-users associate with the nearest pico-BS storing their requested file; one multicast transmission serves users requesting the same file.This content-centric association differs from connection-based association and can improve wireless-medium utilization compared with unicast.Source: B. Multicasting · pp. 7–8
  • Macro-BSs serve cached requests and at most K_b1 different uncached files under the backhaul constraint, selecting uniformly when requests exceed that limit.Each selected uncached file is served through the multicast scheduling design.Source: B. Multicasting · pp. 7–8

IV. PERFORMANCE METRIC

  • Successful transmission probability measures whether a requested file is decoded at the threshold rate and depends on both physical-layer and content-design parameters.Unlike traditional rate coverage probability, it also reflects popularity, cache sizes, and caching-design parameters.Source: §IV · p. 9

V. PERFORMANCE ANALYSIS

  • The performance analysis first treats the general region and then considers asymptotic transmission probability in the high-SNR and user-density region.The analysis is for given caching and multicasting design parameters.Source: §V · p. 10

A. Performance Analysis in General Region

  • The analysis neglects dependence between file load and SINR, although larger association regions tend to have higher loads and lower SINR.It analyzes load and SINR distributions separately for tractability.Source: A. Performance Analysis in General… · p. 10
  • For pico-tier file loads, the analysis approximates an unknown Voronoi-cell-size distribution using a tractable approximation to obtain the load probability mass function.The resulting load distribution is stated in Lemma 2.Source: A. Performance Analysis in General… · p. 11
  • SINR analysis distinguishes two interferer types for macro-users and three for pico-users, including pico-BSs that do and do not store the requested file.The paper derives the SINR distribution by handling these different transmitter-location distributions.Source: A. Performance Analysis in General… · pp. 11–12
  • Theorem 1 gives the successful transmission probability q(F_c^1, F_c^2, p) of u0; the accompanying definitions identify the load pmfs and functions used in its expression.The pmfs of K_c^1,n,0, K_b^1,n,0, and K_c^2,n,0 are given by Lemmas 1 and 2; f1,k and f2,k(Tn) are given by (16) and (17), and Tn by (4).Source: A. Performance Analysis in General… · p. 12

B. Performance Analysis in Asymptotic Region

In the high-SNR and high-user-density region, successful transmission probability separates into macro- and pico-tier contributions, and its asymptotic expression can approximate the probability in those regimes. The analysis also identifies how backhaul capacity and caching design affect success, with a symmetric-path-loss case that separates physical-layer and design parameters.

B. Performance Analysis in Asymptotic Region

  • Lemma 3 expresses asymptotic successful transmission probability as the sum of macro-tier and pico-tier contributions.The macro contribution covers files in the macro cache or backhaul set, while the pico contribution is for files cached at pico-BSs.Source: B. Performance Analysis in Asymptotic… · p. 13
  • With sufficient backhaul capacity, macro caching and backhaul retrieval yield the same success probability, whereas with limited capacity, storing the file at a macro-BS is better.The comparison concerns a file in the backhaul set versus a file stored at a macro-BS.Source: B. Performance Analysis in Asymptotic… · pp. 13–14
  • A file with a higher probability of being cached at a pico-BS has higher successful transmission probability.The asymptotic pico-tier success function is increasing in its argument.Source: B. Performance Analysis in Asymptotic… · p. 14
  • When α1 = α2 = α, the asymptotic expression separates the impact of physical-layer parameters from that of design parameters, facilitating optimization.The physical-layer impact is captured by ωk, θ1,K and θ2,K.Source: B. Performance Analysis in Asymptotic… · p. 14
  • Fig. 2 supports the accuracy of the approximations and shows that the asymptotic expression provides a simple, good approximation at high transmit SNR (e.g., N0 ≥100 dB) and high user density (e.g., λu ≥3 × 10−5).The figure plots successful transmission probability versus transmit SNR and user density.Source: B. Performance Analysis in Asymptotic… · p. 14, Figure 2 · p. 15

VI. OPTIMIZATION PROBLEM FORMULATION

This section formulates caching and multicasting design problems that maximize the successful transmission probability, including a mixed discrete-continuous problem and an asymptotic problem for the high-SNR and user-density region.

VI. OPTIMIZATION PROBLEM FORMULATION

  • The primary design problem jointly optimizes caching and multicasting to maximize q, a mixed discrete-continuous optimization problem.The objective is q(F c 1, F c 2, p).Source: §VI · p. 15
  • A second problem optimizes caching and multicasting to maximize the asymptotic successful transmission probability in the high-SNR and user-density region.This formulation is intended to facilitate the solution of the challenging optimization problem in the next section.Source: §VI · p. 15

A. Optimization Problem … A. Asymptotically Optimal Solution

The paper formulates caching and multicasting design as a successful-transmission-probability optimization, then uses asymptotic solution structure to develop a near-optimal approach for the general region. The optimization is challenging because it combines discrete cache choices with continuous random-caching distributions.

A. Optimization Problem

  • The design objective is to maximize successful transmission probability by optimizing the caching and multicasting design parameters.Source: A. Optimization Problem · p. 15
  • The optimization is mixed discrete-continuous: it selects stored-file sets for both tiers and a continuous random-caching distribution for the second tier.Source: A. Optimization Problem · p. 16
  • An equivalent formulation subdivides the original problem according to the discrete cache-set choices and continuous caching-distribution choice.Source: A. Optimization Problem · p. 16
  • The equivalent optimization remains difficult: it is generally non-convex with many variables, and its discrete subproblem is NP-complete.Source: A. Optimization Problem · p. 16

B. Asymptotic Optimization Problem

  • The asymptotic optimization targets successful transmission probability in the high-SNR and user-density region, using a simpler expression than the general probability.Source: B. Asymptotic Optimization Problem · p. 16
  • For a given second-tier cache set, optimal random-caching distributions form a convex polyhedron whose vertices can be found by the simplex method, with other optima formed by convex combinations.Source: B. Asymptotic Optimization Problem · p. 17

VII. NEAR OPTIMAL SOLUTION

  • A two-step framework first characterizes asymptotically optimal solutions, then uses their structure to obtain a near-optimal general-region solution with manageable complexity and superior performance.Source: §VII · p. 17

A. Asymptotically Optimal Solution

  • The asymptotically optimal solution is studied through the continuous and discrete parts of the optimization to gain design insights for the general-region solution.Source: A. Asymptotically Optimal Solution · p. 17

1) Continuous Optimization:

The paper develops a gradient-projection method for continuous caching optimization and characterizes the optimal caching structure. In the symmetric high-SNR and high-user-density regime, the solution has a reverse water-filling form that favors more popular files.

1) Continuous Optimization:

  • Because the objective has a complex structure, a closed-form optimum is difficult to obtain in the general continuous optimization.The optimization is over a convex feasible set, but the objective's convexity is generally difficult to establish.Source: 1) Continuous Optimization · p. 18
  • A diminishing-step gradient-projection algorithm converges to a stationary point, and to the optimum when the relevant c.d.f. is concave.In that case the objective is concave in the caching variables, making the optimization a convex problem [26, pp. 229].Source: 1) Continuous Optimization · pp. 18–19
  • For given F c 2, when α1 = α2, N0 → ∞, and λu → ∞, the optimal solution to optimization (27) has a reverse water-filling structure.Source: 1) Continuous Optimization · p. 19
  • Files with higher popularity receive more second-tier storage, while sufficiently less popular files may receive zero caching probability.For a heavy-tailed popularity distribution, more distinct files can be stored in the second tier.Source: 1) Continuous Optimization · p. 20

2) Discrete Optimization: · B. Near Optimal Solution in General Region

The paper reduces discrete cache-design search using optimal structural properties, then combines structured discrete search with continuous optimization to construct a near-optimal solution. Under a mild convexity condition, that solution achieves successful-transmission probability at least as high as any asymptotically optimal solution.

2) Discrete Optimization:

  • An optimal discrete choice exists with Fc2 in a bounded range and cache-file sets arranged in consecutive blocks determined by nc1.Source: 2) Discrete Optimization · p. 20
  • Restricting choices to Theorem 2’s structure greatly reduces the search relative to Θ(NN) without losing optimality.Source: 2) Discrete Optimization · p. 21
  • In special cases, Lemma 7 sets nc1 = 1 in one case and nc1 ≥ 2 when f1,Kc1,∞ < f2,Kc2,∞.Source: 2) Discrete Optimization · p. 21
  • Under the respective threshold conditions, the tier with relatively higher receive power is intended to multicast the most popular files: macro-BSs in one case and pico-BSs in the other.Source: 2) Discrete Optimization · p. 21

B. Near Optimal Solution in General Region

VIII. NUMERICAL RESULTS · IX. CONCLUSION

The proposed caching and multicasting design outperforms the three simulated baselines, and the paper develops a near-optimal optimization framework for maximizing successful transmission probability in cache-enabled HetNets.

VIII. NUMERICAL RESULTS

  • The proposed design outperforms all three baselines; Baselines 2 and 3 also outperform Baseline 1 by providing file diversity under limited storage and backhaul.The comparison is shown in Fig. 5.Source: Figure 5 · p. 24, §VIII · p. 25
  • Baseline 2 can waste storage and backhaul by caching or fetching multiple copies of the same file at a base station.This follows from its i.i.d. file-selection design.Source: §VIII · p. 24
  • Successful transmission probability increases with macro- and pico-tier cache sizes because more files can be stored and requested content is more likely to be cached nearby.This trend is reported for all schemes.Source: §VIII · p. 25
  • As the Zipf exponent increases, performance rises faster for the proposed design and Baselines 1 and 2 than for Baseline 3.For Baseline 3, the increase comes only from lower average network file load; for the other schemes, nearby caching also becomes more likely.Source: §VIII · p. 25
  • Successful transmission probability decreases with user density because cached files are more likely to be requested by at least one user.The trend applies to all schemes.Source: §VIII · p. 25

IX. CONCLUSION

  • The paper proposes hybrid caching and corresponding multicasting to provide high spatial file diversity and efficient content dissemination, and analyzes successful transmission probability in general and asymptotic regions.The analysis uses stochastic geometry.Source: §IX · p. 25
  • A two-step optimization framework yields a near-optimal solution with superior performance and manageable complexity for maximizing successful transmission probability.The optimization jointly selects design parameters in a mixed discrete-continuous problem.Source: §IX · pp. 25–26

APPENDIX A: PROOF OF LEMMA 1 · APPENDIX B: PROOF OF LEMMA 2 · APPENDIX C: PROOF OF THEOREM 1

The appendices prove the two lemmas by modeling requested files through Voronoi-cell loads, then establish Theorem 1 by calculating macro- and pico-user success probabilities under their respective interference structures.

APPENDIX A: PROOF OF LEMMA 1

  • Lemma 1 defines a binary indicator for whether another file is requested by users served by the macro-BS, conditioned on the requested file.Source: Appendix A · p. 26
  • Lemma 1 obtains the indicator’s probability mass function from the serving macro-BS Voronoi-cell size distribution using Lemma 3 of.Source: Appendix A · p. 26

APPENDIX B: PROOF OF LEMMA 2

  • Lemma 2 defines a binary indicator for whether another file is requested by users served by a pico-BS storing a specified combination.Source: Appendix B · p. 26
  • Because the relevant pico-BS Voronoi-cell distribution conditioned on its cached combination is unknown, Lemma 2 approximates it using the randomly chosen user’s cell-size distribution and Lemma 3 of.Source: Appendix B · p. 27

APPENDIX C: PROOF OF THEOREM 1

  • For macro-users, Theorem 1’s proof accounts for interference from other macro-BSs and all pico-BSs, deriving conditional success probability through their interference transforms.Source: Appendix C · pp. 27–28
  • Theorem 1’s proof removes conditioning on serving distance, averages over the stated distance distributions, and applies the file-load cases to obtain the success-probability expressions.Source: Appendix C · pp. 28, 30
  • For pico-users, the proof separates interfering pico-BSs storing the desired file from those without it, alongside macro-BSs; random caching and independent thinning yield PPPs, including density λ2Tn for desired-file pico-BSs [27].Source: Appendix C · p. 29

APPENDIX D: PROOF OF LEMMA 3 AND LEMMA 4

The appendix proof uses limiting expressions for f1 and f2, then evaluates integrals in (18) and (19) using a stated exponential-integral identity.

APPENDIX D: PROOF OF LEMMA 3 AND LEMMA 4

  • The proof states limiting expressions for f1 and f2 as the relevant parameter tends to infinity.The displayed expressions include 1 + min{Kb 1, F b 1} in the limit for f1 and a limiting form for f2,Kc 2(x).Source: Appendix D · p. 30
  • The proof identifies ωk, θ1,k, and θ2,k with the quantities given by equations (20), (21), and (22), respectively.Source: Appendix D · p. 31
  • Using that identity, the proof evaluates the integrals in (18) and (19) and proceeds by Lemma 3.The supplied passage does not expose the resulting expressions.Source: Appendix D · p. 31

APPENDIX E: PROOF OF LEMMA 5 · APPENDIX F: PROOF OF LEMMA 6

Appendix E proves Lemma 5 by contradiction, using a monotonicity property and the optimality of a candidate solution. Appendix F proves Lemma 6 through KKT conditions and complementary slackness.

APPENDIX E: PROOF OF LEMMA 5

  • A preliminary fact for Lemma 5 is that ya decreases with a when y ∈ (0, 1) and a ∈ (0, ∞).Source: Appendix E · p. 31
  • The proof of Lemma 5 uses the fact that f2,k,∞(x) is increasing in x.Source: Appendix E · p. 31
  • Under the assumption an1 > an2, the Lemma 5 argument uses optimality and a modified solution to derive a contradiction.Source: Appendix E · p. 31

APPENDIX F: PROOF OF LEMMA 6

  • For Lemma 6, strong duality lets primal and dual optima satisfy KKT conditions, including primal feasibility, dual feasibility, complementary slackness, and stationarity.Source: Appendix F · p. 32
  • The Lemma 6 proof applies complementary slackness and stationarity to distinguish the case Tn = 0 from the interior case 0 < Tn < 1.Source: Appendix F · p. 32
  • Combining the KKT conditions with constraint (29) completes the proof of Lemma 6.Source: Appendix F · p. 32

APPENDIX G: PROOF OF THEOREM 2

The proof establishes structural properties of optimal solutions to Problem 3: bounds on the file sets and a consecutive-popularity arrangement for the macro-cached and backhaul-delivered files.

Property (i) of Theorem 2

  • Property (i) bounds F_b1* by K_b1 and places F_c2* between N−K_c1−K_b1 and N−K_c1.The proof rules out an optimal solution with F_b1* > K_b1.Source: Appendix G · p. 32

Property (ii) of Theorem 2

  • Property (ii) guarantees an optimal solution in which the files in F_c1* ∪ F_b1* are consecutive in popularity order.The proof considers an intervening file and constructs alternatives to obtain a consecutive arrangement.Source: Appendix G · p. 33
  • Whether a file in F_c1* ∪ F_b1* belongs to F_c1* or F_b1* does not change the optimal successful transmission probability.This invariance is used to establish property (ii).Source: Appendix G · p. 33

APPENDIX H: PROOF OF LEMMA 7

Appendix H proves two conditional placement properties for the most popular file and connects them to cache-count conclusions in Theorem 2(ii).

Proof of Property (i) of Lemma 7

  • When f1,Kc^(1+Kb1,∞) > f2,Kc^(2,∞)(1), file 1 belongs to F_c1* ∪ F_b1* in every optimum, and Theorem 2(ii) has nc1 = 1.The proof uses a feasible cache reassignment and contradiction to establish the placement property.Source: Appendix H · p. 34

Proof of Property (ii) of Lemma 7

  • Under Property (ii)'s condition, file 1 belongs to F_c2* in every optimum, and Theorem 2(ii) has nc1 ≥ 2.The supplied passages do not fully preserve the condition's expression.Source: Appendix H · p. 34
  • For Property (ii), the proof swaps files 1 and n2 between cache assignments, sets T'_1 = T*_{n2}, and invokes Lemma 3 to obtain a contradiction.Here n2 is the most popular file in F_c2*; Lemma 5 supplies the transmission-time ordering used in the construction.Source: Appendix H · p. 34
Loading 1604.00645v2…