PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Caching for Data Dissemination in the Downlink of Heterogeneous Networks

Jun Li, Youjia Chen, Zihuai Lin, Wen Chen, Branka Vucetic, Lajos Hanzo

arXiv:2003.12215v1eess.SPcs.ITmath.IT

TL;DR

Limited small-cell storage must serve diverse, repeated content requests while minimizing downloading delay. The paper combines factor-graph-based distributed belief propagation with stochastic-geometry analysis of caching. Simulations report near-optimal delay for belief propagation, good performance at low communication complexity for its heuristic, and improved outage and delay from optimized random caching.

  • Problem

    Caching design must place a large library of popular files in limited small-cell storage while minimizing downloading latency.

    Source: §I · p. 2

  • Method

    The paper uses a factor graph and distributed belief propagation for file placement, and stochastic geometry to analyze random caching and optimize its caching probabilities.

    Source: §I · p. 2, A. Factor Graph Model · p. 4

  • Results

    The distributed BP algorithm approaches exhaustive search within a small margin, while modified BP offers good performance at very low complexity.

    Source: §VIII · p. 12

  • Takeaways & Limitations

    Upper-bound-based optimization of random caching improves both outage and delay over the benchmarks.

    Source: §I · p. 2

    In general, BP convergence and its optimality and convergence rate remain poorly understood and depend on the objective and factor-graph structure.

    Source: C. Convergence to a Fixed Point · p. 6

Abstract

from arXiv · show

Heterogeneous cellular networks (HCN) with embedded small cells are considered, where multiple mobile users wish to download network content of different popularity. By caching data into the small-cell base stations (SBS), we will design distributed caching optimization algorithms via belief propagation (BP) for minimizing the downloading latency. First, we derive the delay-minimization objective function (OF) and formulate an optimization problem. Then we develop a framework for modeling the underlying HCN topology with the aid of a factor graph. Furthermore, distributed BP algorithm is proposed based on the network's factor graph. Next, we prove that a fixed point of convergence exists for our distributed BP algorithm. In order to reduce the complexity of the BP, we propose a heuristic BP algorithm. Furthermore, we evaluate the average downloading performance of our HCN for different numbers and locations of the base stations (BS) and mobile users (MU), with the aid of stochastic geometry theory. By modeling the nodes distributions using a Poisson point process, we develop the expressions of the average factor graph degree distribution, as well as an upper bound of the outage probability for random caching schemes. We also improve the performance of random caching. Our simulations show that (1) the proposed distributed BP algorithm has a near-optimal delay performance, approaching that of the high-complexity exhaustive search method, (2) the modified BP offers a good delay performance at a low communication complexity, (3) both the average degree distribution and the outage upper bound analysis relying on stochastic geometry match well with our Monte-Carlo simulations, and (4) the optimization based on the upper bound provides both a better outage and a better delay performance than the benchmarks.

I. INTRODUCTION

The paper targets delay-aware caching in heterogeneous cellular networks, where repetitive popular-content requests meet limited small-cell storage. It proposes distributed optimization and stochastic-geometry analysis, alongside a model of the network and its download process.

I. INTRODUCTION

  • Caching popular content at small-cell base stations brings it closer to users and can reduce redundant transmissions and backhaul traffic.The paper identifies repeated requests for popular content as a source of redundant streaming.Source: §I · p. 1
  • Prior centralized caching work considered an idealized setting without interference or wireless-channel effects and assumed impractical global channel-state information.The placement problem is also nontrivial because large video libraries compete for limited small-cell memory.Source: §I · p. 2
  • The paper proposes factor-graph-based distributed belief propagation for delay-minimizing file placement, with a heuristic variant to reduce communication complexity.It also reports a fixed point under certain conditions and near-optimal performance relative to exhaustive search.Source: §I · p. 2
  • Stochastic-geometry analysis models network nodes as Poisson point processes, derives factor-graph degree distributions and an outage upper bound, and optimizes random-caching probabilities.The analysis matches Monte Carlo results, and upper-bound-based optimization improves outage and delay over benchmarks.Source: §I · p. 2

II. SYSTEM MODEL

  • The system has one macro base station and K small-cell base stations serving J randomly located mobile users; the macro station preloads small cells over backhaul links.Users try eligible small cells first and turn to the macro station if those cells lack the requested files.Source: §II · p. 3
  • The model uses Rayleigh-fading downlinks and divides Q files into N groups of G files, with each small-cell station storing one group.The library is available at the macro base station, while each small-cell station has storage for G files, with G < Q.Source: §II · p. 3

III. DISTRIBUTED FILE DOWNLOADING RELYING ON CACHING

The paper defines a two-stage caching and downloading process, then formulates delay-minimizing file placement and maps it to a network factor graph. User association depends on which eligible small cells cache the requested group and their download rates.

III. DISTRIBUTED FILE DOWNLOADING RELYING ON CACHING

  • The protocol separates off-peak file placement from user downloading; users retrieve files from adjacent small cells when available and otherwise turn to the macro base station.During placement, the macro station broadcasts file groups to small cells over backhaul links.Source: §III · p. 3

B. MU-SBS Association

  • For a requested file group, a user considers small cells in H(j) that cache it and selects the one with minimum downloading delay; if none cache it, the user uses the macro station.H(j) contains small cells that can provide the user with at least the specified SINR threshold.Source: B. MU-SBS Association · p. 4

C. Optimization Problem Formulation

  • The optimization chooses file placement to minimize average downloading delay, but the integer-programming formulation is NP-complete and centralized minimization requires global channel-state information.The paper therefore seeks a distributed, low-complexity optimization approach.Source: C. Optimization Problem Formulation · p. 4

A. Factor Graph Model

  • The factor graph represents each mobile user as a factor node and each small-cell base station as a variable node, with edges linking pairs that meet the SINR threshold.The graph follows the HCN topology and restricts message passing to neighboring nodes.Source: A. Factor Graph Model · pp. 4–5
  • The graph's factor nodes represent local utility functions derived by decomposing the global objective, with utility defined as the negative of delay.The local utilities are maximized at the corresponding user nodes.Source: 1) Factor Nodes · p. 5

1) Factor Nodes:

The factor graph assigns local utilities to user-related factor nodes and file-placement variables to small-cell-related variable nodes. Belief propagation estimates placement through iteratively exchanged marginal-probability messages.

1) Factor Nodes:

  • Each factor node represents a user's local utility function, and maximizing the global utility is decomposed into maximizing those local functions.The local utility is defined from the negative of the user's delay.Source: 1) Factor Nodes · p. 5

2) Variable Nodes:

  • Each variable node represents a small-cell base station and its row of the placement matrix, whose single 1 identifies the stored file group.The row has N possible placements, and these variables are optimized to maximize the utility.Source: 2) Variable Nodes · p. 5

B. Distributed Belief Propagation

  • Belief propagation estimates marginal distributions of placement variables; messages between user and small-cell nodes iteratively convey the probabilities of each file-group placement.The method decomposes the utility maximization into user-local subproblems and updates marginal PMFs for connected variables.Source: B. Distributed Belief Propagation · p. 5

1) Initialization:

The distributed BP algorithm iteratively exchanges message PMFs between SBSs and mobile users, then selects the file with the highest a posteriori probability. A fixed point exists, but optimality and convergence rate remain open in general.

1) Initialization:

  • The initial distribution for each file variable can be set to the a priori popularity distribution.Source: 1) Initialization · p. 5

2) Variable Node Update:

  • At each iteration, an SBS updates its message to a user using messages from neighboring users other than that user.The update includes N probabilities and uses a normalization factor.Source: 2) Variable Node Update · p. 5

3) Factor Node Update:

  • Each user updates the message sent to an SBS using messages from its neighboring SBSs other than the recipient.The factor-node messages are calculated according to the marginal PMF.Source: 3) Factor Node Update · p. 5

4) Final Solution:

  • After T iterations, each SBS chooses the file with the maximum a posteriori probability for storage.Source: 4) Final Solution · p. 6

C. Convergence to a Fixed Point

  • A fixed point of convergence exists for the proposed distributed BP algorithm.The message mapping is continuous.Source: C. Convergence to a Fixed Point · p. 6
  • The fixed-point result does not establish optimality or convergence rate, which remain open challenges for BP in general.These properties depend on the objective function and factor-graph scale, sparsity, and cycles.Source: C. Convergence to a Fixed Point · p. 6

V. A HEURISTIC BP WITH REDUCED COMPLEXITY

The heuristic BP changes the format of the beliefs exchanged while retaining the belief-propagation approach. Users send sampled file indices, and SBSs aggregate those indices into counts for broadcast.

V. A HEURISTIC BP WITH REDUCED COMPLEXITY

  • The heuristic retains the classic belief-propagation concept but uses a different format for beliefs.Source: §V · p. 6
  • The heuristic replaces each N-probability message with a randomly selected file index sent from a user to an SBS.The index is sampled according to the probabilities in the message.Source: §V · p. 6
  • An SBS aggregates received file indices into counts indicating how many neighboring users selected each file.Source: §V · p. 6
  • Instead of sending N probabilities to each neighboring user, an SBS broadcasts N integer counts.Users use the broadcast counts to calculate probabilities for their updates.Source: §V · p. 6

1) Initialization:

The heuristic BP initializes and updates file-selection counts through sampled file indices, while the stochastic-geometry analysis derives average factor-graph degrees under Poisson node deployments. The degree results show parameter independence in specified cases, and the noise-free approximations are reported as accurate for dense HCN deployments.

1) Initialization:

  • At initialization, an SBS generates independent file indices according to the popularity distribution and counts how many indices correspond to each file.Source: 1) Initialization · p. 6

4) Final Solution:

  • After T iterations, the SBS selects a file for storage based on its final count.Source: 4) Final Solution · p. 7
  • In each iteration, an SBS broadcasts N integer counts rather than N|H(k)| real numbers, while each user sends |H(j)| integers rather than N|H(j)| real numbers.SBS computation is O(N) for HBP versus O(N|H(k)|^2) for original BP; user computation is O(|H(j)|N |H(j)|) for both.Source: 4) Final Solution · p. 7

VI. PERFORMANCE ANALYSIS BASED ON STOCHASTIC GEOMETRY

  • The stochastic-geometry analysis averages degree and downloading performance over Rayleigh fading and independent Poisson point processes for users and SBSs.It assumes equal SBS transmission power.Source: §VI · p. 7

A. Average Degree Distributions of the Factor Graph

  • The factor-graph analysis distinguishes factor-node degree |H(j)| from variable-node degree |H(k)| by their respective neighboring-node counts.Source: A. Average Degree Distributions of the… · p. 7
  • Under the noise-free approximation, the average factor- and variable-node degree expressions simplify, and the approximations are reported as significantly accurate for dense HCN deployments.The analysis attributes this accuracy to dominant interference effects.Source: A. Average Degree Distributions of the… · p. 7
  • The average factor-node degree ζU is independent of the MU and SBS intensities and SBS transmission power, while the average variable-node degree ζB is independent of transmission power.The factor-node result is attributed to signal and interference increasing together as node intensities or SBS power increase.Source: A. Average Degree Distributions of the… · p. 7

B. Downloading Performance of Random Caching

Because BP-based caching is difficult to analyze in closed form, the section evaluates random caching using stochastic geometry and derives an upper bound on outage probability. It relates the bound to caching fraction and path-loss parameter, then obtains average delay from average outage.

B. Downloading Performance of Random Caching

  • Random caching selects ΩFn·K SBSs from the K SBSs to cache file group Fn, enabling stochastic-geometry performance analysis.The selection fraction satisfies 0 ≤ ΩFn ≤ 1.Source: B. Downloading Performance of Random… · p. 7
  • Theorem 3 upper-bounds the outage probability of downloading a file in Fn, where outage means an MU cannot find Fn in neighboring SBSs.The analysis ignores noise effects because interference is treated as the dominant factor predetermining network performance.Source: B. Downloading Performance of Random… · p. 7
  • A higher path-loss parameter δ raises Pr(Qn), while a higher caching fraction ΩFn lowers it.The passage attributes the δ relationship to fewer potentially eligible serving SBSs.Source: B. Downloading Performance of Random… · p. 8
  • The average outage probability is weighted by file popularity, and average delay is obtained from that average outage probability.Average delay is defined over the PPP and channel fading; the SBS-download component is challenging to calculate and lacks a closed form in PPP analysis.Source: B. Downloading Performance of Random… · p. 8
  • Minimizing the upper bound on outage probability is used to optimize the caching fraction because average delay has no closed-form expression.The optimization selects ΩFn using the bound; the stated solution is constrained by ΩFn ≥ 0.Source: B. Downloading Performance of Random… · p. 8

VII. SIMULATION RESULTS

Simulations compare factor-graph degree predictions and random-caching performance across network conditions. Optimized random caching (ORC) improves average delay and outage over file-popularity-based random caching (FPRC), while analytical degree and outage results match simulations.

B. Average Downloading Performance of Random Caching

A. Average Degree Distributions of Factor Graph

B. Average Downloading Performance of Random Caching

C. Delay Performance of Distributed BP algorithms

Across the evaluated networks, BP approaches exhaustive-search performance, while heuristic BP (HBP) offers good delay at reduced communication complexity. In the large-scale case, BP and HBP nearly overlap, and the conclusion reports that stochastic-geometry analysis matches Monte Carlo simulations.

C. Delay Performance of Distributed BP algorithms

  • In the 8-SBS, 4-MU scenario, BP is near optimal; HBP loses about 5% or 20 seconds to BP but beats ORC by about 10% or 40 seconds.FPRC has the worst delay among the compared caching schemes.Source: C. Delay Performance of Distributed BP… · p. 11
  • With 50 SBSs and 25 MUs, BP performs best in both storage cases; HBP loses around 3% versus BP while reducing communication complexity.ORC has a 5% performance loss versus HBP but is less complex; greater per-SBS storage in Case1 gives lower delay than Case2.Source: C. Delay Performance of Distributed BP… · p. 11
  • Table I reports average iteration counts by s for the two scenarios; HBP uses more iterations than BP, but its overall communication complexity is lower.Per iteration, HBP broadcasts N integers and transmits |H(j)| integers, whereas BP transmits N|H(k)| and N|H(j)| real numbers.Source: C. Delay Performance of Distributed BP… · p. 11, Table I · p. 11

D. Delay Performance in a Large Scale Network

  • For 1,000 files, 50 SBSs, and 100 MUs, HBP is about 1% worse than BP; their performance gap shrinks with network scale and nearly vanishes in the largest case.Both BP algorithms outperform random caching schemes in the large-scale evaluation.Source: D. Delay Performance in a Large Scale… · p. 11

VIII. CONCLUSIONS

  • BP approaches exhaustive-search performance, while modified BP offers good delay at very low complexity; stochastic-geometry averages match Monte Carlo simulations.The conclusion also reports a fixed point for distributed BP and better performance than benchmark for optimization based on the outage upper bound.Source: §VIII · pp. 11–12

APPENDIX A PROOF OF LEMMA 1

The proof establishes continuity of the message update mapping and uses a fixed-point theorem to show convergence. The factor-node degree is interpreted as the number of SBSs meeting the typical MU’s SINR threshold.

APPENDIX A PROOF OF LEMMA 1

  • The proof bounds changes in the message mapping and concludes that Γ is continuous.It uses the inequality that exp(µFi(Λ)) lies in (0, 1] because Fi(Λ) is non-positive and µ is positive.Source: Appendix A · p. 12

APPENDIX B PROOF OF THEOREM 1

  • Because the message-set mapping is continuous on a convex, closed, bounded set, Schauder’s fixed point theorem gives a fixed point.The proof identifies Θ as a mapping from the collection of message sets to itself.Source: Appendix B · p. 12

A. The Average Degree of Factor Nodes

  • A factor node’s average degree counts SBSs whose received SINR at a typical MU meets the threshold δ.The analysis assumes exponentially distributed fading and a distance-based path-loss function, with network nodes modeled by a Poisson point process.Source: A. The Average Degree of Factor Nodes · pp. 12–13

B. The Average Degree of Variable Nodes

The average degree of a variable node counts the MUs that can receive a sufficiently strong signal from a typical SBS. Under a stationary Poisson point process, the distance distribution used in the derivation does not depend on the MU’s location.

B. The Average Degree of Variable Nodes

  • A variable node’s average degree is the number of MUs receiving SINR at least δ from a typical SBS.The analysis considers a typical SBS at the origin and an MU at xU.Source: B. The Average Degree of Variable Nodes · p. 13
  • The variable-node degree calculation counts MUs meeting the SINR threshold despite interference from other SBSs.The interfering SBS locations are denoted by xk.Source: B. The Average Degree of Variable Nodes · p. 13
  • Stationarity of the Poisson point process makes the distribution of distance to interfering SBSs independent of the MU location, yielding results analogous to the earlier derivation.Combining the stated equations completes the proof.Source: B. The Average Degree of Variable Nodes · p. 13

APPENDIX D PROOF OF COROLLARY 1

The appendices derive a corollary under a noise-ignoring condition and prove an outage-probability upper bound for random caching. That bound relies on associating a typical MU with its nearest SBS caching the requested file.

APPENDIX D PROOF OF COROLLARY 1

  • Ignoring the noise, the authors substitute the above expression into equations (17) and (16), obtaining equations (20) and (21), respectively, and thereby complete the proof.Source: Appendix D · p. 13

APPENDIX E PROOF OF THEOREM 3

  • The outage analysis assumes the typical MU associates with its nearest SBS caching the requested file, making the derived outage probability an upper bound.The bound neglects cases where the nearest SBS misses the SINR threshold but the second-nearest SBS would meet it.Source: Appendix E · p. 13
  • With random caching, SBSs caching a given file group are modeled as a Poisson point process, and success depends on the nearest such SBS meeting the SINR threshold.The interference is split between SBSs caching other groups and those caching the requested group, excluding the serving SBS.Source: Appendix E · pp. 13–14

APPENDIX F PROOF OF LEMMA 2

The proof reduces to k = 1 and establishes a bound on the difference between two-factor products. It develops this estimate through cases and extends it to longer products iteratively.

APPENDIX F PROOF OF LEMMA 2

  • The proof assumes k = 1 without loss of generality before applying (29).It states that (29) then becomes the expression used in the proof.Source: Appendix F · p. 14
  • Under |aK−1 − ˜aK−1| ≥ |aK −˜aK|, the proof establishes |aK−1aK −˜aK−1˜aK| ≤ 2|aK−1 −˜aK−1| and discusses five cases: one with both terms greater than or equal to their counterparts, plus mixed orderings split by product comparison.Source: Appendix F · p. 14
  • The case analysis establishes |aK−1aK −˜aK−1˜aK| ≤ 2|aK−1 −˜aK−1|.The proof then uses this estimate to obtain a corresponding bound for a three-factor product and repeats the argument iteratively.Source: Appendix F · p. 14
Loading 2003.12215v1…