# Multi-cell Content Caching: Optimization for Cost and Information Freshness

Zhanwei Yu, Tao Deng, Yi Zhao, and Di Yuan Z. Yu, Y. Zhao, and D. Yuan are
with the Department of Information Technology, Uppsala University, 751 05
Uppsala, Sweden.
E-mail: {zhanwei.yu; yi.zhao<EMAIL_ADDRESS>T. Deng is with School of
Information Science and Technology, Southwest Jiaotong University, 610032
Sichuan, China.
E-mail<EMAIL_ADDRESS>submitted May 27, 2022. This
article was presented in part at the IEEE Wireless Communications and
Networking Conference Workshops (WCNC WKSHPS) , April 2022 [1].

###### Abstract

In multi-access edge computing (MEC) systems, there are multiple local cache
servers caching contents to satisfy the users’ requests, instead of letting
the users download via the remote cloud server. In this paper, a multi-cell
content scheduling problem (MCSP) in MEC systems is considered. Taking into
account jointly the freshness of the cached contents and the traffic data
costs, we study how to schedule content updates along time in a multi-cell
setting. Different from single-cell scenarios, a user may have multiple
candidate local cache servers, and thus the caching decisions in all cells
must be jointly optimized. We first prove that MCSP is NP-hard, then we
formulate MCSP using integer linear programming, by which the optimal
scheduling can be obtained for small-scale instances. For problem solving of
large scenarios, via a mathematical reformulation, we derive a scalable
optimization algorithm based on repeated column generation. Our performance
evaluation shows the effectiveness of the proposed algorithm in comparison to
an off-the-shelf commercial solver and a popularity-based caching.

###### Index Terms:

Age of information, caching, multi-cell.

##  1 Introduction

For streaming media applications in emerging scenarios, the existing
communication systems face significant challenges in delivering ultra-high
bandwidth, ultra-large storage, and ultra-low latency. Multi-access edge
computing (MEC) is widely accepted as a key technology in this context [2], as
it can provide computation-intensive and caching-intensive infrastructure.

This paper focuses on content caching in multi-cell MEC systems. In each cell,
the local cache server downloads contents from the remote cloud server via a
backhaul link to provide services for users. Moreover, there are overlapping
areas among the cells, thus some users potentially can obtain cached contents
from more than one cell. For user experience in terms of the freshness of
contents, cache servers need to update cached contents frequently. We use the
notion of age of information (AoI), introduced in [3], as the metric of
information freshness. We address optimal scheduling of cache updates with
respect to the trade-off between the freshness of contents and the cost due to
downloading contents.

We consider a finite and time-slotted scheduling horizon. There are two types
of limits in cache servers. Downloading and caching in a time slot are subject
to backhaul and cache capacities, respectively. A request can be satisfied by
a cache if the demanded content is cached, otherwise the content will be
downloaded from the cloud to the user, resulting in a higher cost. We use a
cost function addressing the trade-off between freshness and download cost. To
minimize the overall cost, the updating and caching decisions of cells are
coupled such that we need to coordinate the cells instead of optimizing them
in isolation.

Our work consists of the following contributions for the outlined multi-cell
content scheduling problem (MCSP).

  * •

We provide a complexity analysis for MCSP. Specifically, even for the special
case of uniform content size and single time slot, the problem is NP-hard,
based on a polynomial reduction from Monotone 3-Satisfiability (M3SAT).

  * •

We provide an integer linear programming (ILP) formulation for MCSP. Using
commercial off-the-shelf optimization solvers, the global optimum can be found
within an acceptable amount of time for small-scale instances.

  * •

We derive a mathematical reformulation that enables a scalable solution
approach. Specifically, in the reformulation, sequences are introduced to
represent updating and caching decisions of contents in cache servers over the
time slots.

  * •

We propose a column generation algorithm that can efficiently solve the linear
programming (LP) version of the reformulation. The algorithm keeps augmenting
a small subset of sequences until the optimality condition is satisfied. To
recover integrality, we provide a rounding strategy based on disjunctions. The
column generation and the rounding strategy are alternately applied to deliver
a problem solution.

  * •

Performance evaluation demonstrates the superiority of our proposed algorithm
in comparison to a popularity-based caching and a commercial solver. Moreover,
the algorithm provides an optimality bound, so the performance can be gauged
even if the global optimum is out of reach. Using the bound, our results show
the algorithm consistently yields near-to-optimal solutions that are at most
$2.4\%$ from the global optimum for 3-cell and 7-cell instances.

##  2 Related Work

Edge content caching has been for example addressed in [4, 5, 6, 7].
Leveraging social networks and device-to-device communications, the authors of
[4] propose a proactive caching paradigm that can improve the spectral
efficiency of backhaul as well as the ratio of satisfied users. In [5],
caching is applied to software-defined mobile networks. The work in [6]
proposes a distributed delay optimization algorithm for scenarios where
multiple unmanned aerial vehicles are equipped with cache to serve users. The
authors of [7] investigate multi-layer caching where both base station and
users can cache the contents.

The works in [8, 9, 10, 11, 12, 13, 14, 15] have studied cache content
placement strategies based on popularity. In [8], the authors provide an
optimal content place strategy for large-scale peer-to-peer systems to
maximize the utilization of the uplink bandwidth resources. The authors of [9]
consider the impact of user mobility in device-to-device networks, and propose
a mobility-aware multi-user algorithm to minimize the expected average cost
per user. The work in [10] proposes a strategy for the popular random-
heterogeneous-cellular-network model based on Poisson point processes to
maximize the hit probability over content placement probabilities. By
utilizing network coding, content files are partitioned into multiple coded
segments, and the contents can then be stored with distributed caching. The
work in [11] provides a strategy for the distribution of the coded segments
among multiple cache servers to reduce the content downloading time. The
content placement strategies in [8, 9, 10, 11] primarily focus on pushing
popular content to the network edge. The strategy proposed in [12] jointly
optimizes the caches in edge and core networks to maximize the hit ratio. The
work in [13] studies the joint optimization of cache placement and request
routing in a multi-cell MEC system. In [14] and [15], reinforcement learning
approaches are applied to design cache content placement strategies.

The AoI concept as a metric for information freshness is introduced in [3].
The work in [16] reveals that AoI is significantly different from delay, and
the aspect of AoI in many application scenarios has been addressed in [17, 18,
19, 20, 21]. In [17], the authors propose an algorithm for optimal link
activation to minimize energy consumption subject to AoI constraints in
wireless networks with interference. The work in [18] studies the AoI of
status updates in a general multi-source multi-hop wireless network with the
presence of interference, and the emphasis is on performance bounds. The work
in [19] considers the joint optimization of node assignment and camera
transmission scheduling to minimize AoI in wireless camera networks with fog
computing. In [20], the authors study AoI with respect to orthogonal multiple
access (OMA) and non-orthogonal multiple access (NOMA), and show that NOMA is
not always better than OMA in terms of average AoI. The work in [21]
investigates the bandwidth minimization problem under AoI constraints in
bandwidth-limited Internet of things.

Some works have provided caching strategies accounted for AoI. The authors of
[22] and [23] provide strategies based on both the popularity and the
freshness of contents. In [24], a freshness-aware update scheme is proposed
for the trade-off between the service delay and the freshness of contents. In
[25], the authors optimize content scheduling to address AoI and information
absence. In [26], the authors provide a model-free reinforcement learning
algorithm to minimize the long-term average cost subject to both AoI and
energy consumption constraints.

The scenarios in [23, 24, 25, 26] are different from ours as our paper
considers multi-cell caching. To the best of our knowledge, the work in [27]
is closest to ours as it considers a heterogeneous network where multiple
cache servers are placed in cells to serve users. However, there are
significant differences. Our system model has overlapping areas among the
cells, and the cells are coupled due to such a topology. However, in [27], the
cells are disjoint but coupled due to the shared update frequency. In
addition, the authors of [27] consider minimizing the average AoI of delivered
contents while we jointly minimize the AoI and cost.

##  3 System Scenario and Problem Formulation

###  3.1 System Scenario

The MEC scenario consists of a cloud server and $H$ cells as illustrated in
Fig. 1. There is a cache server in each cell. To model realistic network
topologies, there are overlapping areas among the cells. In this paper, the
terms cell and cache server are used interchangeably. Denote by
$\mathcal{H}=\\{1,2,\dots,H\\}$ the set of cache servers, and $C_{h}$ and
$G_{h}$ the cache capacity and the backhaul capacity of cache server $h$,
respectively. The cache servers download contents from the cloud server via
backhaul links. The contents subject to caching form a set
$\mathcal{I}=\\{1,2,\dots,I\\}$, and $s_{i}$ is the size of content $i$. The
caching system targets satisfying content requests by cached contents, to
reduce the load of core network and the response latency.

Request for uncached contentRequest for cached contentCache server 1Cache
server 3Cache server 2Cloud server24135 Figure 1: An MEC scenario consisting
of a cloud server and local cache servers.

A scheduling horizon consisting of a set of time slots
$\mathcal{T}=\\{1,2,\dots,T\\}$ is considered in this paper111The time slot
duration in our case is at the magnitude of minutes or even an hour [28]..
Denote by $\mathcal{R}=\\{1,2,\dots,R\\}$ the set of the requests222The
requests can be known via for example a prediction model from the work in
[29].. The requests can be divided into two types:

  1. 1.

Multiple-choice requests (MCRs): The requests are from the users located in
the overlapping areas, thus there are multiple candidate cache servers.

  2. 2.

Single-choice requests (SCRs): These are simply the rest of requests that can
be satisfied by only one cache server.

We use $\mathcal{R}^{\text{m}}$ and $\mathcal{R}^{\text{s}}$ to represent the
sets of MCRs and SCRs, respectively. Obviously,
$\mathcal{R}=\mathcal{R}^{\text{m}}\cup\mathcal{R}^{\text{s}}$. Each request
$r$ consists of a tuple $(i_{r},o_{r},d_{r},\mathcal{H}_{r})$ where:

  * •

$i_{r}$ is the content of requested by $r$.

  * •

$o_{r}$ is the time slot of request $r$.

  * •

$d_{r}$ is the time slot that is the deadline of satisfying request $r$.

  * •

$\mathcal{H}_{r}$ is the set of candidate cache server(s) for request $r$.

Our problem consists in making scheduling decisions of content caching and
updating over the time slots. We use AoI to model the freshness of contents. A
content that is just downloaded from the cloud to a cache server has AoI zero,
and the AoI increases by one for every time slot as long as the content is
still cached but not updated. Moreover, for a request, if the requested
content is absent from the candidate cache server(s) by the deadline, the
content will be downloaded from the cloud, and the AoI is zero in this case.

###  3.2 Optimization Variables

Denote by $x_{hita}$ a binary variable that is one if and only if content $i$
is cached with AoI $a$ in cache server $h$ in time slot $t$. Based on the
definition of AoI, the $x$-variables are constrained by the following, that
states how AoI evolves over time.

$\displaystyle x_{hi(t-1)(a-1)}\geq x_{hita},$ $\displaystyle\qquad\ \ \forall
h\in\mathcal{H},i\in\mathcal{I},t\in\mathcal{T}\setminus\\{1\\},a\in\\{1,2,\dots,t-1\\}.$
(1)

We use binary variable $z_{hit}$ that equals one if cache server $h$ caches
content $i$ in time slot $t$. Then

$\sum_{a=0}^{t-1}x_{hita}=z_{hit},\forall
h\in\mathcal{H},i\in\mathcal{I},t\in\mathcal{T}.$ (2)

Binary variable $y_{rha}$ is one if request $r$ is satisfied with AoI $a$ by
cache server $h$. A request needs to be responded to at most once by the cache
servers, hence we have

$\sum_{h\in\mathcal{H}_{r}}\sum_{a=0}^{d_{r}-1}y_{rha}\leq 1,\forall
r\in\mathcal{R}.\\\ $ (3)

Furthermore, request $r$ can be satisfied with AoI $a$ by cache server $h$
only if there exists content $i_{r}$ whose AoI is $a$ in time slots
$t\in\\{o_{r},\dots,d_{r}\\}$ of cache server $h$, i.e.,

$y_{rha}\leq\sum^{d_{r}}_{t=o_{r}}x_{hi_{r}ta},\forall
r\in\mathcal{R},h\in\mathcal{H}_{r},a\in\\{0,1,\dots,d_{r}-1\\}.$ (4)

###  3.3 Cost Model

From a pure AoI standpoint, a naive and extreme setting is that all the
requests are met by the cloud server. However, the costs due to downloading
would be very large. We consider the trade-off between the costs due to
downloading from the cloud (to cache servers and directly by users for
uncached contents) and the performance in AoI. In this paper, we use a joint
cost function to address the trade-off, and our cost function consists of
three components as follows.

####  3.3.1 AoI Cost

Denote by $f_{i}(a)$ $(a\in\mathbb{N})$ a monotonically increasing function to
quantify the impact of AoI of content $i$. A specific candidate function
$f_{i}(a)$ can be, for example, $f_{i}(a)={\rm e}^{a}$ that is the reciprocal
of a utility function with respect to AoI in [30]. The total AoI cost for all
the requests is expressed as

$\displaystyle A(\bm{y})=$
$\displaystyle\sum_{r\in\mathcal{R}}\left[\sum_{h\in\mathcal{H}_{r}}\sum_{a=0}^{d_{r}-1}f_{i_{r}}(a)y_{rha}\\!+\\!f_{i_{r}}(0)\left(1\\!-\\!\sum_{h\in\mathcal{H}_{r}}\sum_{a=0}^{d_{r}-1}y_{rha}\right)\right].$
(5)

The first term in the square brackets is the AoI cost if a request is
satisfied by a cache server, and the second term is for the case where the
content with AoI zero is directly downloaded from the cloud server. Exactly
one of the two cases will occur due to (3).

####  3.3.2 Download Cost

Denote by $\alpha$ the unit download cost when users download from the cloud
server. The total download cost is thus

$D(\bm{y})=\alpha\sum_{r\in\mathcal{R}}s_{i_{r}}(1-\sum_{h\in\mathcal{H}_{r}}\sum_{a=0}^{d_{r}-1}y_{rha}),$
(6)

where $s_{i_{r}}$ is the size of content $i_{r}$. Obviously, for request $r$,
a download cost of $\alpha s_{i_{r}}$ occurs if all the $y$-variables of
request $r$ are zero, i.e., the download cost will occur only if the request
is not satisfied by cache servers.

####  3.3.3 Update Cost

We use $\beta$ $(\beta<\alpha)$ to represent the unit cost when cache servers
download contents via the backhaul from the cloud server. Because $x_{hit0}$
represents that cache server $h$ downloads content $i$ in time slot $t$, the
update cost can be expressed by

$U(\bm{x})=\beta\sum_{h\in\mathcal{H}}\sum_{i\in\mathcal{I}}\sum_{t\in\mathcal{T}}x_{hit0}s_{i}.$
(7)

###  3.4 Problem Complexity

Consider MCSP, subject to the cache capacity and backhaul capacity. We analyze
its complexity in Theorem 1, which implies that no low-complexity and exact
algorithm can be expected for MCSP, unless $\mathcal{P}=\mathcal{NP}$.

######  Theorem 1.

MCSP is NP-hard even if the contents are of uniform size.

###### Proof.

The proof is established by a reduction from M3SAT that is NP-complete [31].
Consider a formula of clauses $\mathcal{F}=\land_{k=1}^{N}\mathcal{C}_{k}$,
where each clause $\mathcal{C}_{k}$ has at most three negated or non-negated
boolean variables. The M3SAT problem is to determine whether or not there
exists an assignment of true/false values to the variables, such that formula
$\mathcal{F}$ is true.

Consider an instance of M3SAT with $N$ clauses and $M$ variables, we construct
a corresponding MCSP instance with $M$ cache servers, $N$ primary requests,
and $2M$ auxiliary requests. We first set some parameters of the network:

  1. 1.

There are only two contents A and B of equal size. Denote the size by $s$.

  2. 2.

There is only one time slot, therefore, the AoI is always zero. Also, the AoI
costs are equal for the two contents, i.e., $f_{A}(0)=f_{B}(0)=f$.

  3. 3.

Each cache server has two auxiliary requests that are SCRs for content A and
B, respectively.

  4. 4.

A primary request might be SCR or MCR. If a primary is MCR, it has at most
three candidate cache servers.

We define the primary requests according to the clauses in $\mathcal{F}$. For
any clause, there is a primary request for content A if all the variables are
negated in the clause. Conversely, there is a primary request for content B if
all the variables are non-negated. For any primary request, its candidate
cache server(s) will be set to correspond to the variable(s) in the clause.

By the construction, because $\alpha$ and $\beta$ are both positive, and
$\alpha>\beta$, with the two auxiliary requests, each cache server must store
content A or B, so the update cost is a constant of $M\beta s$. Moreover,
exactly half of the auxiliary requests are satisfied by cached contents, and
the other half must use the cloud, and, therefore, the sum of AoI and download
costs with respect to auxiliary requests equals $2Mf+M\alpha s$. For the
primary requests, the AoI cost is $Nf$, and zero download cost can be achieved
if and only if all the primary requests are satisfied by the cache servers.
Now, the question is then if the lower bound of $M\beta s+2Mf+M\alpha s+Nf$ on
the overall cost can be achieved. This question can be answered by solving the
defined MCSP instance, and the solution gives the correct answer of M3SAT.
Therefore, MCSP is strongly NP-hard. ∎

###  3.5 Problem Formulation

MCSP can be formulated by integer linear programming (ILP) as follows.

$\displaystyle\underset{\bm{x},\bm{y},\bm{z}\in\\{0,1\\}}{\min}$
$\displaystyle\ \ A(\bm{y})+D(\bm{y})+U(\bm{x})$ (8a) s.t.
$\displaystyle\text{\eqref{ILP_c1}-\eqref{ILP_c5}},$
$\displaystyle\sum_{i\in\mathcal{I}}s_{i}z_{hit}\leq C_{h},\forall
t\in\mathcal{T},h\in\mathcal{H}$ (8b)
$\displaystyle\sum_{i\in\mathcal{I}}s_{i}x_{hit0}\leq G_{h},\forall
t\in\mathcal{T},h\in\mathcal{H}$ (8c)

The objective function (8a) is the overall cost. Constraints (1)-(4) state the
relationship among $\bm{x}$, $\bm{y}$, and $\bm{z}$. Constraints (8b) and (8c)
state the cache and backhaul capacity, respectively. The ILP model can be
solved by solvers e.g., Gurobi [32], though they need significant
computational time. For efficient solution of MCSP, we next provide an
algorithm based on repeated column generation.

##  4 Algorithm Design

###  4.1 Reformulation of MCSP

We first give a reformulation of MCSP. Let us consider any of the cache
servers, and the caching and updating solution for a particular content on the
server. This can be viewed along the time slots, namely that for a time slot,
the content is either cached or not, represented by one or zero, respectively.
In the former case, it is also significant to know if the content gets
updated. Subsequently, we will use the term update to refer to downloading a
content that is either added to the cache or refreshed with respect to AoI. A
sequence that represents the solutions of one content, mathematically, is
called a column.

In other words, a column for any content in a cache server is a vector
representing the caching and updating decisions of the content over all time
slots. We denote by $\mathcal{L}$ the index set of all possible such vectors.
Each column $\ell\in\mathcal{L}$ consists of $T$ tuples
$(q_{t\ell},p_{t\ell})$ over all the time slots, i.e.,
$\ell=\left[(q_{1\ell},p_{1\ell}),(q_{2\ell},p_{2\ell}),\dots,(q_{T\ell},p_{T\ell})\right]^{\mathrm{T}}$,
where $q_{t\ell}$ and $p_{t\ell}$ are one if and only if the status is cached
and updated in time slot $t$, respectively. An example of the columns is given
in Fig. 2. Because updating a content implies it is cached, a tuple
$(q_{t\ell},p_{t\ell})$ has three possible patterns: $(1,1)$, $(1,0)$, and
$(0,0)$. Therefore, the cardinality of set $\mathcal{L}$ is bounded by
$3^{T}$.

$\begin{array}[]{l}\ell=[(q_{1\ell},p_{1\ell}),{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}(}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}q}{\color[rgb]{0,0,0}{}_{2\ell}}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0},p}{\color[rgb]{0,0,0}{}_{2\ell}}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0})},\dots,(q_{T\ell},p_{T\ell})]\\\
\ \ \
=[(1,1),{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}(1,0}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0})}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0},}\dots,(0,0)]\end{array}$Time
slots$1$$1$$0$$1$$0$$0$CacheUpdate$\cdots$$\cdots$${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}(}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}q}{\color[rgb]{0,0,0}{}_{2\ell}}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0},p}{\color[rgb]{0,0,0}{}_{2\ell}}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0})}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}=}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}(}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}1,0}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0})}$
Figure 2: An example of columns and the corresponding caching and updating
decisions. The associated AoI values are directly induced from the caching and
updating decisions.

We use a binary variable $\chi_{hi\ell}$ for column $\ell$, content $i$, and
cache server $h$. This variable is one if and only if column $\ell$ is
selected for content $i$ and cache server $h$. Because a column $\ell$ fully
contains the caching and updating decisions, the associated AoI values are
known for any given column.

Hence, for any given column $\ell$ for content $i$ and cache server $h$, part
of the overall cost of MCSP is determined. This includes

  1. 1.

The update cost of cache server $h$ for content $i$.

  2. 2.

The AoI and download costs of the server’s SCRs. This set of the SCRs can be
expressed by
$\mathcal{R}^{\text{s}}_{hi}=\\{r\in\mathcal{R}^{\text{s}}|(\mathcal{H}_{r}=\\{h\\})\wedge(i_{r}=i)\\}$.

We use $S_{hi\ell}$ to denote the sum of the above costs.

The unknown cost component is related to the $y$-variables, that is, the AoI
and download costs of the MCRs. We use $A^{\text{m}}(\bm{y})$ and
$D^{\text{m}}(\bm{y})$ to represent them, and they can be expressed by
replacing $\mathcal{R}$ with $\mathcal{R}^{\text{m}}$ in (3.3.1) and (6),
respectively.

Accordingly, MCSP can be reformulated as follows.

$\displaystyle\underset{\bm{\chi},\bm{y}\in\\{0,1\\}}{\min}$ $\displaystyle\
\sum_{h\in\mathcal{H}}\sum_{i\in\mathcal{I}}\sum_{\ell\in\mathcal{L}}S_{hi\ell}\chi_{hi\ell}+A^{\text{m}}(\bm{y})+D^{\text{m}}(\bm{y})$
(9a) s.t. $\displaystyle\text{\eqref{ILP_c4}},$ $\displaystyle
y_{rha}\leq\sum_{h\in\mathcal{H}_{r}}\sum_{i\in\mathcal{I}}\sum_{\ell\in\mathcal{L}}B^{\ell}_{rha}\chi_{hi\ell},$
$\displaystyle\qquad\forall
r\in\mathcal{R}^{\text{m}},h\in\mathcal{H}_{r},a\in\\{0,1,\dots,t_{r}-1\\}$
(9b)
$\displaystyle\sum_{i\in\mathcal{I}}\sum_{\ell\in\mathcal{L}}s_{i}q_{t\ell}\chi_{hi\ell}\leq
C_{h},\forall h\in\mathcal{H},t\in\mathcal{T}$ (9c)
$\displaystyle\sum_{i\in\mathcal{I}}\sum_{\ell\in\mathcal{L}}s_{i}p_{t\ell}\chi_{hi\ell}\\!\leq\\!G_{h},\forall
h\in\mathcal{H},t\in\mathcal{T}$ (9d)
$\displaystyle\sum_{\ell\in\mathcal{L}}\chi_{hi\ell}=1,\forall
h\in\mathcal{H},i\in\mathcal{I}$ (9e)

Using the notion of column, we do not need the $x$-variables and the
$z$-variables any more, thus constraints (1) and (2) are dropped. Constraint
(9b) is derived from constraint (4), where $B^{\ell}_{rha}$ is one if and only
if column $\ell$ for content $i$ and cache server $h$ can satisfy request $r$
with AoI $a$. As the columns include all the scheduling information, the
values of $B^{\ell}_{rha}$ are known. Cache and backhaul capacity constraints
are imposed by (9c) and (9d). Constraint (9e) indicate that exactly one of the
columns with respect to content $i$ and cache server $h$ is selected.

###  4.2 Column Generation

There are exponentially many candidate columns. However, the structure of (9)
can be exploited by using column generation. In column generation, the problem
is decomposed into a restricted master problem (RMP) and a subproblem (SP),
and RMP and SP are solved alternately. A new column that has the potential of
improving the objective function is generated in each iteration by solving the
SP. Note that most of the variables $\chi_{hi\ell}$ are zeros at optimum due
to (9e), and consequently only a small number of columns will be generated.

####  4.2.1 Restricted Master Problem

RMP is a linear programming (LP) problem that differs from (9) in the
following:

  1. 1.

The binary variables $\bm{y}$ and $\bm{\chi}$ are relaxed using the continuous
domain $[0,1]$.

  2. 2.

For each content $i$ and server $h$, only a subset of the $\chi$-variables is
present. This is represented by defining $\mathcal{L}^{\prime}_{hi}$,
containing the columns generated so far for $i$ and $h$. Initially,
$\mathcal{L}^{\prime}_{hi}$ only contains the columns representing that
content $i$ is not cached by cache server $h$.

  3. 3.

As the subset of columns in RMP are differed by $i$ and $h$, we use
$B^{i\ell}_{rha}$, $q_{hit\ell}$, and $p_{hit\ell}$ to replace
$B^{\ell}_{rha}$, $q_{t\ell}$, and $p_{t\ell}$ for any column $\ell$ in
individual subtset $\mathcal{L}^{\prime}_{hi}$.

####  4.2.2 Subproblem

At the optimum of RMP, denote by $\pi^{*}_{rha}$, $\mu^{*}_{ht}$,
$\varphi^{*}_{ht}$, and $\lambda^{*}_{hi}$ the corresponding optimal dual
variables of the counterparts of (9b), (9c), (9d), and (9e), respectively. For
any content $i$ and cache server $h$, the LP reduced cost of column $\ell$ is

$\displaystyle
S_{hi\ell}+\sum_{r\in\mathcal{R}}\sum_{a=0}^{t_{r}-1}B^{i\ell}_{rha}\pi^{*}_{rha}-s_{i}\sum_{t\in\mathcal{T}}\left(q_{hit\ell}\mu^{*}_{ht}+p_{hit\ell}\varphi^{*}_{ht}\right)-\lambda^{*}_{hi}.$
(10)

By LP theory, only a column with negative reduced cost may improve the
objective function value. To this end, we would like to find the column
outside $\mathcal{L}^{\prime}_{hi}$ of minimum reduced cost. Obviously, this
SP is decomposed by cache server as well as content. Finding the minimum
reduced cost can be equivalently expressed using variables $\bm{x}$ and
$\bm{z}$ in the SP, formulated below for content $i$ and server $h$.

[SPhi] $\displaystyle\underset{\bm{x},\bm{z}\in\\{0,1\\}}{\min}\ \
S_{hi}(\bm{x},\bm{z})+\sum_{r\in
R_{hi}}\sum_{a=0}^{t_{r}-1}\pi^{*}_{rha}x_{hit_{r}a}$
$\displaystyle\qquad\qquad-
s_{i}\sum_{t\in\mathcal{T}}(\mu^{*}_{ht}z_{hit}+\varphi^{*}_{ht}x_{hit0})-\lambda^{*}_{hi}$
(11a) s.t. $\displaystyle\text{\eqref{ILP_c1}-\eqref{ILP_c3}},$

where we use $S_{hi}(\bm{x},\bm{z})$ to represent that the $S$-value of
content $i$ for cache server $h$ is a function of $\bm{x}$ and $\bm{z}$.

###  4.3 SP as a Shortest Path Problem

$\cdots$$\cdots$$\cdots$Time slot 1Time slot 2Time slot 3Time slot 4AoI $0$AoI
$1$AoI $2$AoI
$3$$\Lambda$$\kappa_{0}^{1}$$\kappa_{0}^{2}$$\kappa_{1}^{2}$$\kappa_{0}^{3}$$\kappa_{1}^{3}$$\kappa_{2}^{3}$$\kappa_{0}^{4}$$\kappa_{1}^{4}$$\kappa_{2}^{4}$$\kappa_{3}^{4}$$\theta_{1}^{1}$$\theta_{1}^{2}$$\theta_{2}^{2}$$\theta_{1}^{3}$$\theta_{2}^{3}$$\theta_{3}^{3}$$\theta_{4}^{3}$$\theta_{1}^{4}$$\theta_{2}^{4}$$\theta_{3}^{4}$$\theta_{4}^{4}$$\theta_{5}^{4}$$\theta_{6}^{4}$$\theta_{7}^{4}$$\Pi$Notcached
Figure 3: The graph for which finding the shortest path gives the optimum of
(11).

We show that SPhi can be solved as a shortest path problem in polynomial time
[33], even though it is stated as an ILP. Consider content $i$ and cache
server $h$. We construct an acyclic directed graph in Fig. 3 in which finding
the shortest path from node $\Lambda$ to node $\Pi$ is equivalent to solving
SPhi. For brevity, we define an auxiliary function

$g_{hi}(o,d,a)=\sum_{r\in\mathcal{R}_{\varsigma}}\pi^{*}_{rha},$ (12)

where
$\mathcal{R}_{\varsigma}=\\{r\in\mathcal{R}^{\text{m}}|(h\in\mathcal{H}_{r})\wedge(i_{r}=i)\wedge(o_{r}=o)\wedge(d_{r}\geq
d)\\}$. A request in set $\mathcal{R}_{\varsigma}$ has the following
properties:

  1. 1.

The request is made for content $i$ in time slot $o$.

  2. 2.

The request is MCR, and it can be satisfied by cache server $h$.

  3. 3.

The deadline of the request is greater than or equal to $d$.

In the figure, the nodes can be divided into upper and lower parts except for
$\Lambda$ and $\Pi$:

  * •

The upper nodes ($\theta$-nodes) represent that the content is not cached. One
can see that we construct multiple nodes instead of only one node to represent
the uncached status in a time slot. The subscripts are used to distinguish
between the nodes in the same time slot. There are $\frac{t^{2}-t+2}{2}$
$\theta$-nodes in time slot $t$, and for these $\theta$-nodes, the
predecessors of the last $(t-1)$ $\theta$-nodes are $\kappa$-nodes, for
example, in time slot $3$, $\kappa^{2}_{0}\rightarrow\theta^{3}_{3}$ and
$\kappa^{2}_{1}\rightarrow\theta^{3}_{4}$. The predecessors of other
$\theta$-nodes are $\theta$-nodes in the previous time slot, for example,
$\theta^{2}_{1}\rightarrow\theta^{3}_{1}$ and
$\theta^{2}_{2}\rightarrow\theta^{3}_{2}$.

  * •

The lower nodes ($\kappa$-nodes) represent that the content is cached.
Similarly, the superscripts of $\kappa$-nodes indicate their associated time
slots. The subscripts are the AoI values of the content (therefore, the
subscripts start with zero).

We have the following types of arcs:

  1. 1.

The gray dashed arcs all terminate at $\theta$-nodes, and they represent that
the content is not cached in the next time slot. For example, arcs
$(\theta_{2}^{2},\theta^{3}_{2})$ and $(\kappa_{0}^{2},\theta^{3}_{3})$ both
mean that the content is not cached in time slot $3$. The weights of these
arcs are zero as the corresponding the $x$-variables and the $z$-variables are
both zero in (11a).

  2. 2.

The orange arcs all terminate at node $\Pi$ and emanate from the nodes that
are in the last time slot. These arcs are relevant to calculating the
corresponding $S_{hi}(\bm{x},\bm{z})$ and constant term $\lambda_{hi}^{*}$ in
(11a). The weight of any of these arcs is

$\left|\mathcal{R}^{\text{s}}_{hi}\right|\left[f_{i}\left(0\right)+\alpha
s_{i}\right]-\lambda_{hi}.$ (13)

The first term of (13) is for all the SCRs in $\mathcal{R}^{\text{s}}_{hi}$.
If some of these requests are met by the cache, the costs in (13) will be
subtracted, see further details below.

  3. 3.

A blue arc connects two adjacent $\kappa$-nodes, both with AoI zero. Such an
arc corresponds to that the content is updated in the two adjacent time slots.
In this case, the corresponding $x$-variables and $z$-variables are both one
in (11a). For arc $(\kappa_{0}^{t-1},\kappa_{0}^{t})$, the weight is

$-\left|\mathcal{R}_{\Xi}\right|\alpha
s_{i}+g_{hi}(t,t,0)-s_{i}(\mu^{*}_{ht}+\varphi^{*}_{ht}),$ (14)

where $\mathcal{R}_{\Xi}=\\{r\in\mathcal{R}^{\text{s}}_{hi}|d_{r}=t\\}$. A
request in $\mathcal{R}_{\Xi}$ is made for content $i$, and it can be
satisfied by cache server $h$ before time slot $t$. Clearly, if we select blue
arc $(\kappa_{0}^{t-1},\kappa_{0}^{t})$, the SCRs in $\mathcal{R}_{\Xi}$ can
be satisfied in time slot $t$ by cache server instead of the cloud server with
AoI zero. Therefore, the first term of (14) has the effect of subtracting the
download costs present in (13). In addition, term $g_{hi}(t,t,0)$ is because
the MCRs in
$\\{r\in\mathcal{R}^{\text{m}}|(h\in\mathcal{H}_{r})\wedge(i_{r}=i)\wedge(o_{r}=t)\wedge(d_{r}\geq
t)\\}$ can be satisfied with AoI zero.

  4. 4.

A black arc emanates from a $\kappa$-node with nonzero AoI value, and
terminates at a $\kappa$-node with zero AoI value. If such a black arc
$(\kappa_{a}^{t-1},\kappa_{0}^{t})$ is selected, it means that the content has
not been updated for $a$ time slots, and it is updated in time slot $t$. In
this case, the MCRs in
$\\{r\in\mathcal{R}^{\text{m}}|(h\in\mathcal{H}_{r})\wedge(i_{r}=i)\wedge(t-a\leq
o_{r}\leq t)\wedge(d_{r}\geq t)\\}$ can be satisfied in time slot $t$ with AoI
zero, so the weight of arc $(\kappa_{a}^{t-1},\kappa_{0}^{t})$ is given by

$-\left|\mathcal{R}_{\Xi}\right|\alpha
s_{i}+\sum_{\tau=t-a}^{t}g_{hi}(\tau,t,0)-s_{i}(\mu^{*}_{ht}+\varphi^{*}_{ht}).$
(15)

  5. 5.

A red arc emanates from a $\theta$-node, and terminates at a $\kappa$-node
with zero AoI. If such a red arc $(\theta_{n}^{t-1},\kappa_{0}^{t})$ is
selected, it means that the content is updated in time slot $t$, and also it
has not been updated for some consecutive time slots. We give the following
recursive function denoted by $\xi(\theta_{n}^{t-1})$ that calculates how many
consecutive time slots the content has not been updated at node
$\theta_{n}^{t-1}$:

$\xi(\theta^{t-1}_{n})=\left\\{\begin{array}[]{lcl}1&&{pre(\theta^{t-1}_{n})=\Lambda}\\\
\xi(\theta^{t-2}_{n})+1&&{pre(\theta^{t-1}_{n})=\theta^{t-2}_{n}}\\\
a+1&&{pre(\theta^{t-1}_{n})=\kappa_{a}^{t-2}}\\\ \end{array}\right.$ (16)

where $pre(\cdot)$ is the predecessor of some node. For example,
$\xi(\theta^{4}_{4})=\xi(\theta^{3}_{4})+1=(1+1)+1=3$ represents the content
has not been updated for three time slots (i.e., time slots $2$, $3$, and
$4$). With the auxiliary function, the weight of arc
$(\theta_{n}^{t-1},\kappa_{0}^{t})$, similar to (15), is given by

$-\left|\mathcal{R}_{\Xi}\right|\alpha
s_{i}+\sum_{\tau=t-\xi(\theta^{t-1}_{n})}^{t}g_{hi}(\tau,t,0)-s_{i}(\mu^{*}_{ht}+\varphi^{*}_{ht}).$
(17)

  6. 6.

The purple arcs represent AoI evolution over time slots when the content is
cached but not updated. For these arcs, the corresponding $x$-variables are
zero, but the corresponding $z$-variables are one. The weight of arc
$(\kappa_{a-1}^{t-1},\kappa_{a}^{t})$ is given by

$\displaystyle\sum_{\tau=0}^{t-1}\sum_{r\in\mathcal{R}_{\Psi}}\left[-f_{i}\left(0\right)-\alpha
s_{i}+f_{i}\left(\max\left\\{0,a-\tau\right\\}\right)\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\quad+g_{hi}(t,t,a)-s_{i}\mu^{*}_{ht},$
(18)

where
$\mathcal{R}_{\Psi}=\\{r\in\mathcal{R}^{\text{s}}_{hi}|(o_{r}=t-\tau)\wedge(d_{r}=t)\\}$,
i.e., the requests in $\mathcal{R}_{\Psi}$ are SCRs made for content $i$ in
time slot $(t-\tau)$, and they can be satisfied by cache server $h$ before
time slot $t$. If arc $(\kappa_{a-1}^{t-1},\kappa_{a}^{t})$ is selected, the
AoI values in the previous $a$ time slots must be $0,1,\dots,a-1$. Thus we
know that the lowest possible AoI value for the SCRs in
$\\{r\in\mathcal{R}^{\text{s}}_{hi}|(o_{r}\leq t-a)\wedge(d_{r}=t)\\}$ must be
zero, and for the SCRs in
$\\{r\in\mathcal{R}^{\text{s}}_{hi}|(o_{r}>t-a)\wedge(d_{r}=t)\\}$, the lowest
possible AoI value must be $a-(d_{r}-o_{r})$, therefore the first term of (6).
In addition, the MCRs in
$\\{r\in\mathcal{R}^{\text{m}}|(h\in\mathcal{H}_{r})\wedge(i_{r}=i)\wedge(o_{r}=t)\wedge(d_{r}\geq
t)\\}$ can be satisfied with AoI $a$, hence $g_{hi}(t,t,a)$.

######  Theorem 2.

For content $i$ and cache server $h$, SPhi can be solved in polynomial time as
a shortest path problem.

###### Proof.

We show that the optimal solution of SPhi can be obtained as the shortest path
in the graph constructed. Suppose the optimal solution of SPhi, i.e.,
$\bm{x}^{*}$ and $\bm{z}^{*}$, is given. A corresponding path is constructed
as follows.

  1. 1.

Starting with time slot one:

     * •

If $z_{hi1}^{*}=0$ and $x_{hi10}^{*}=0$, arc $(\Lambda,\theta^{1}_{1})$ is
selected.

     * •

If $z_{hi1}^{*}=1$ and $x_{hi10}^{*}=1$, arc $(\Lambda,\kappa_{0}^{1})$ is
selected.

  2. 2.

For time slot $t$ $(t>1)$:

     * •

If $z_{hit}^{*}=0$ and $x_{hita}^{*}=0$ $\forall
a\in\left\\{0,1,\dots,t-1\right\\}$, arc $(\theta^{t-1}_{n},\theta^{t}_{n})$
or $(\kappa^{t-1}_{a},\theta^{t}_{n})$ is selected according to which one
applies in the previous time slot.

     * •

If $z_{hit}^{*}=1$ and $x_{hit0}^{*}=1$, arc
$(\theta^{t-1}_{n},\kappa_{0}^{t})$ or $(\kappa_{a}^{t-1},\kappa_{0}^{t})$ is
selected according to the previous time slot.

     * •

If $z_{hit}^{*}=1$ and $x_{hita}^{*}=1$ $(a\neq 0)$, arc
$(\kappa^{t-1}_{a-1},\kappa_{a}^{t})$ is selected.

  3. 3.

Finally, one of the orange arcs $(\theta^{t}_{n},\Pi)$ and
$(\kappa^{t}_{a},\Pi)$ is selected to reach node $\Pi$.

Clearly, a path from node $\Lambda$ to $\Pi$ is constructed in this way.
According to (13)-(6), the cost of the derived path equals the object function
value of SPhi for $\bm{x}^{*}$ and $\bm{z}^{*}$.

Conversely, consider the shortest path. For time slot $t$:

  * •

If the path contains any $\theta$-node in time slot $t$, we set $z_{hit}=0$
and $x_{hita}=0$ $(\forall a\in\\{0,1,\dots,t-1\\})$.

  * •

If the path contains node $\kappa^{t}_{\bar{a}}$ in time slot $t$, we set
$z_{hit}=1$, $x_{hit\bar{a}}=1$, and $x_{hita}=0$ $(a\neq\bar{a})$.

With this variable value setting, the objective function has the same value as
the path length (i.e., total arc weights). One can observe that the solution
constructed in this way satisfies the constraints of the SP because any path
from node $\Lambda$ to $\Pi$ adheres to constraints (1) and (2).

In addition, the shortest path problem in directed acyclic graph can be solved
in polynomial time no matter if the arc costs are negative or not [33]. There
are $\mathcal{O}(T^{3})$ nodes and arcs in the corresponding graph, therefore,
the complexity of solving the shortest path problem is $\mathcal{O}(T^{3})$.
Hence the conclusion. ∎

The column generation algorithm (CGA) is summarized in Algorithm 1. The
algorithm first initializes $\mathcal{L}^{\prime}_{hi}$ $\forall
h\in\mathcal{H},i\in\mathcal{I}$ with all-zero column. Then CGA solves RMP and
obtains the optimal values of its dual variables. For each content $i$ for
cache server $h$, CGA will find the column with minimal reduced cost via
solving the corresponding shortest path problem, and add it to
$\mathcal{L}^{\prime}_{hi}$ if the reduced cost is negative. The algorithm
will terminate if all reduced costs are non-negative.

Input: $\mathcal{H}$, $\mathcal{I}$, $\mathcal{T}$, $C_{h}$, $G_{h}$, $\forall
h\in\mathcal{H}$, $s_{i}$, $f_{i}(a)$, $\forall i\in\mathcal{I}$

Output: $\bm{\chi}^{*}$, $\bm{y}^{*}$, $\mathcal{L}^{\prime}$

1 Initialize $\mathcal{L}^{\prime}$

2 repeat

3 Solve RMP to obtain the optimum $(\bm{\chi}^{*},\bm{y}^{*})$ and dual
optimum $(\bm{\pi}^{*},\bm{\mu}^{*},\bm{\varphi}^{*},\bm{\lambda}^{*})$

4 for  _$h\in\mathcal{H}$ , $i\in\mathcal{I}$ _ do

5 Solve SPhi (11) by a shortest path algorithm

6 if  _the optimum of ( 11a) $<0$_ then

7 Add the corresponding column to $\mathcal{L}^{\prime}$

8

9

10

11until  _ The optimum of (11a) $\geq 0$, $\forall
h\in\mathcal{H},i\in\mathcal{I}$ _

12return _$\bm{\chi}^{*}$ , $\bm{y}^{*}$, $\mathcal{L}^{\prime}$_

Algorithm 1 Column generation algorithm

###  4.4 Rounding Algorithm

We remark that Algorithm 1 ends with a solution (i.e., $\bm{\chi}^{*}$) that
is not necessarily integer. At this stage, the objective function value is a
lower bound (LB) of the global optimum. To obtain an integer solution, a naive
rounding strategy is to fixe some fractional $\chi$-variable to be one or
zero. However, this choice is quite aggressive because the decisions over all
time slots for the corresponding content become all fixed when one
$\chi$-variable is fixed, and thus we have no chance to alter the solution of
this content at all.

We first define two following indicators that can be viewed as the likelihood
of caching and updating content $i$ for cache server $h$ in time slot $t$,
respectively.

$\displaystyle\Gamma_{hit}$
$\displaystyle=\sum_{\ell\in\mathcal{L}^{\prime}}q_{hit\ell}\chi_{hi\ell}^{*},$
(19) $\displaystyle\Omega_{hit}$
$\displaystyle=\sum_{\ell\in\mathcal{L}^{\prime}}p_{hit\ell}\chi_{hi\ell}^{*}.$
(20)

In the light of the use of disjunction in branch-and-bound in solving integer
programs [34], we consider rounding the $\Gamma$-variables and the
$\Omega$-variables instead of the $\chi$-variables. In the following, we prove
a relationship among $\bm{\chi}^{*}$, $\bm{\Gamma}$, and $\bm{\Omega}$, and
then propose a rounding algorithm based on this result.

######  Theorem 3.

$\bm{\chi}^{*}$ is integer if and only if $\bm{\Gamma}$ and $\bm{\Omega}$ are
integers.

###### Proof.

The necessity is obvious by the definition of $\bm{\Gamma}$ and $\bm{\Omega}$.
For sufficiency, assume $\bm{\Gamma}$ and $\bm{\Omega}$ are integer. Suppose
$\bm{\chi}^{*}$ is fractional, i.e., for some $\chi^{*}_{hi\ell}$, we have
$0<\chi^{*}_{hi\ell}<1$. By the counterpart of (9e) in RMP, we know that at
least one more fractional $\chi$-variable for content $i$ and cache server $h$
must exist. Suppose we have two columns
$\ell_{1},\ell_{2}\in\mathcal{L}^{\prime}_{hi}$, and their corresponding
$\chi_{hi\ell_{1}}^{*}$ and $\chi_{hi\ell_{2}}^{*}$ are such that

  * •

$\chi_{hi\ell_{1}}^{*}$ and $\chi_{hi\ell_{2}}^{*}$ are both fractional;

  * •

$\chi_{hi\ell_{1}}^{*}+\chi_{hi\ell_{2}}^{*}=1$.

Then we can infer that

$\Gamma_{hit}=\sum_{\ell\in\mathcal{L}^{\prime}}q_{hit\ell}\chi_{hi\ell}^{*}=q_{hit\ell_{1}}\chi_{hi\ell_{1}}^{*}+q_{hit\ell_{2}}\chi_{hi\ell_{2}}^{*}.$
(21)

Because every column is unique in $\mathcal{L}^{\prime}_{hi}$, we can always
find some time slot $t$ in which $q_{hit\ell_{1}}=1$, $q_{hit\ell_{2}}=0$ or
$q_{hit\ell_{1}}=0$, $q_{hit\ell_{2}}=1$. In this time slot, $\Gamma_{hit}$
equals $q_{hit\ell_{1}}\chi_{hi\ell_{1}}^{*}$ or
$q_{hit\ell_{2}}\chi_{hi\ell_{2}}^{*}$, respectively, and thus $\Gamma_{hit}$
must be fractional, which contradicts the assumption. The argument is easily
generalized to more than two columns. Moreover, the same argument applies to
$\bm{\Omega}$. Hence the conclusion. ∎

By Theorem 3, we can perform rounding on $\bm{\Gamma}$ and $\bm{\Omega}$ after
column generation, instead of $\bm{\chi}^{*}$. That is, we fix some
$\Gamma$-variables and $\Omega$-variables to be zero or one, then the columns
violating these fixed values will be removed from $\mathcal{L}^{\prime}_{hi}$.
This is much less aggressive in rounding than fixing $\chi$-variables because
the decision of only one time slot is made, instead of over all time slots.
The rounding algorithm is summarized in Algorithm 2. More specifically,
Algorithm 2 has four stages:

  1. 1.

Steps 2-2: We first fix the entities that are integer. Namely, if
$\Omega_{hit}=1$, we fix $\Omega_{hit}$ and $\Gamma_{hit}$ to be both one.
Similarly, we fix $\Omega_{hit}$ and $\Gamma_{hit}$ to be both zero if
$\Gamma_{hit}=0$.

  2. 2.

Steps 2-2: For rounding, we first consider fractional $\bm{\Omega}$ as it
impacts both cache and backhaul capacities. We find the
$\Omega_{h\hat{i}\hat{t}}$ $(\hat{i}\in\mathcal{I},\hat{t}\in\mathcal{T})$
that is closest to zero or one (Step 2) for each cache server $h$
$(h\in\mathcal{H})$. In the former case, we fix $\Omega_{h\hat{i}\hat{t}}$ to
be zero. In the latter case, if the remaining capacities admit content size
$s_{\hat{i}}$, we fix both $\Omega_{h\hat{i}\hat{t}}$ and
$\Gamma_{h\hat{i}\hat{t}}$ to be one.

  3. 3.

Steps 2-2: If $\bm{\Omega}$ is integer, we subsequently consider fractional
$\bm{\Gamma}$, if any. Similarly, we first fix the integer entities (Steps
2-2), i.e., fix $\Gamma_{hit}$ to be one if $\Gamma_{hit}=1$. Then we find the
$\Gamma_{h\hat{i}\hat{t}}$ $(\hat{i}\in\mathcal{I},\hat{t}\in\mathcal{T})$
that is closest to being an integer for each cache server $h$
$(h\in\mathcal{H})$, and perform rounding as above.

  4. 4.

Steps 2-2: Finally, we recalculate the remaining backhaul and cache
capacities, and remove all the incompatible columns from
$\mathcal{L}^{\prime}_{hi}$. The incompatible columns include the two
following types:

     * •

The columns violating the rounding decisions, e.g., we need to remove all
$\ell$ in which $p_{123\ell}=0$ if we have fixed $\Omega_{123}$ to be one.

     * •

The columns corresponding to updating or caching a content in some time slot
but this would exceed the backhaul or cache capacity.

Input: $\bm{\chi}^{*}$, $C_{h}$, $G_{h}$, $s_{i}$,
$\mathcal{L}^{\prime}_{hi}$, $\forall h\in\mathcal{H},i\in\mathcal{I}$

Output: $\mathcal{L}^{\prime}_{hi}$, $\forall h\in\mathcal{H},i\in\mathcal{I}$

1 Compute $\bm{\Gamma}$ and $\bm{\Omega}$ by (19) and (20)

2 for  _$h\in\mathcal{H}$ , $i\in\mathcal{I}$, $t\in\mathcal{T}$ _ do

3 if  _$\Omega_{hit}=1$_ then // $\Gamma_{hit}$ must be one

4 Fix both $\Omega_{hit}$ and $\Gamma_{hit}$ to be one

5 Remove all the nodes in time slot $t$ except node $\kappa_{0}^{t}$ and their
arcs from the graph of SPhi

6 if  _$\Gamma_{hit}=0$_ then // $\Omega_{hit}$ must be zero

7 Fix both $\Omega_{hit}$ and $\Gamma_{hit}$ to be zero

8 Remove all the $\kappa$-nodes in time slot $t$ and their arcs from the graph
of SPhi

9

10for  _$h\in\mathcal{H}$ , $t\in\mathcal{T}$ _ do

11 Compute the remaining backhaul and cache capacities, denoted by
$\bar{G}_{ht}$ and $\bar{C}_{ht}$, respectively

12

13

14for  _$h\in\mathcal{H}$_ do

15 if  _$\exists\Omega_{hit}\notin\mathbb{Z}$
$(i\in\mathcal{I},t\in\mathcal{T})$ _ then

16
$(h,\hat{i},\hat{t})\leftarrow\arg\min\\{\Delta_{hit}|(\Delta_{hit}\\!=\\!\min\\{\Omega_{hit},1-\Omega_{hit}\\})\wedge(\Omega_{hit}\notin\mathbb{Z})\wedge(i\in\mathcal{I},t\in\mathcal{T})\\}$

17 if  _$(\Omega_{h\hat{i}\hat{t}} <0.5)\vee(s_{\hat{i}}>\bar{G}_{h\hat{t}})$_
then

18 Fix $\Omega_{h\hat{i}\hat{t}}$ to be zero

19 Remove node $\kappa_{0}^{\hat{t}}$ and its arcs from the graph of
SP${}_{h\hat{i}}$

20 else

21 Fix both $\Omega_{h\hat{i}\hat{t}}$ and $\Gamma_{h\hat{i}\hat{t}}$ to be
one

22 Remove all the nodes in time slot $\hat{t}$ except node
$\kappa_{0}^{\hat{t}}$ and their arcs from the graph of SP${}_{h\hat{i}}$

23

24 else if  _$\exists\Gamma_{hit}\notin\mathbb{Z}$
$(i\in\mathcal{I},t\in\mathcal{T})$_ then

25 for  _$i\in\mathcal{I}$ , $t\in\mathcal{T}$ _ do

26 if  _$\Gamma_{hit}=1$_ then

27 Fix $\Gamma_{hit}$ to be one

28 Remove all the $\theta$-nodes in time slot $t$ and their arcs from the
graph of SPhi

29

30 for  _$t\in\mathcal{T}$_ do

31 Compute $C_{ht}^{\prime}$

32

33

34
$(h,\hat{i},\hat{t})\leftarrow\arg\min\\{\Delta_{hit}|(\Delta_{hit}\\!=\\!\min\\{\Gamma_{hit},1-\Gamma_{hit}\\})\wedge(\Gamma_{hit}\notin\mathbb{Z})\wedge(i\in\mathcal{I},t\in\mathcal{T})\\}$

35 if  _$(\Gamma_{h\hat{i}\hat{t}} <0.5)\vee(s_{\hat{i}}>\bar{C}_{h\hat{t}})$
_ then

36 Fix $\Gamma_{h\hat{i}\hat{t}}$ to be zero

37 Remove all the $\kappa$-nodes in time slot $\hat{t}$ and their arcs from
the graph of SP${}_{h\hat{i}}$

38 else

39 Fix $\Gamma_{h\hat{i}\hat{t}}$ to be one

40 Remove all the $\theta$-nodes in time slot $\hat{t}$ and their arcs from
the graph of SP${}_{h\hat{i}}$

41

42

43

44for  _$h\in\mathcal{H}$ , $t\in\mathcal{T}$ _ do

45 Compute $\bar{G}_{ht}$ and $\bar{C}_{ht}$

46 Remove all incompatible columns from $\mathcal{L}^{\prime}_{hi}\forall
i\in\mathcal{I}$ and the corresponding $\chi$-variables

47

48

49return _$\mathcal{L}^{\prime}_{hi}$ , $\forall
h\in\mathcal{H},i\in\mathcal{I}$_

Algorithm 2 Rouding algorithm

###  4.5 Repeated Column Generation Algorithm

After a rounding operation, there may exist additional columns that will
improve the RMP. Therefore we perform our column generation algorithm and
rounding algorithm alternately to obtain an integer solution. After the
alternative process terminates, all the $\Omega$ and $\Gamma$-variables are
integers, and we can obtain an integer solution $\bm{\chi}^{*}$ by Theorem 3.
Once integer $\bm{\chi}^{*}$ is found, the corresponding optimal values of
binary $y$-variables are determined in constant time
$\mathcal{O}(|\mathcal{R}^{\rm m}|)$.

We name the overall algorithm repeated column generation algorithm (RCGA),
summarized in Algorithm 3. Note that Steps 2, 2, 2, 2, 2, 2, and 2 of
Algorithm 2 are in fact for RCGA. These steps remove some nodes and their arcs
in the graph of SPs such that the columns generated by subsequent SPs comply
to the rounding decisions. As there are $H$ cache servers, $I$ contents, and
$T$ time slots, and at least $H$ elements of the $\Omega$-variables or the
$\Gamma$-variables become integer in each iteration, the process is executed
in at most $I\times T$ iterations.

Input: $\mathcal{H}$, $\mathcal{I}$, $\mathcal{T}$, $C_{h}$, $G_{h}$, $\forall
h\in\mathcal{H}$, $s_{i}$, $f_{i}(a)$, $\forall i\in\mathcal{I}$

Output: $\bm{\chi}^{*}$, $\bm{y}^{*}$, $\mathcal{L}^{\prime}_{hi}$, $\forall
h\in\mathcal{H},i\in\mathcal{I}$

1 Apply Algorithm 1 to obtain $\bm{\chi}^{*}$

2 while  _$\bm{\chi}^{*}\notin\bm{\mathbb{Z}}^{|\mathcal{L}^{\prime}_{hi}|}$_
do

Apply Algorithm 2// rounding operation

3 Apply Algorithm 1 to obtain $\bm{\chi}^{*}$

Obtain $\bm{y}^{*}$ when $\bm{\chi}^{*}$ is given// easy to solve

4 return _$\bm{\chi}^{*}$ , $\bm{y}^{*}$, $\mathcal{L}^{\prime}$_

Algorithm 3 The framework of RCGA

##  5 Performance Evaluation

###  5.1 Preliminaries

In this section, we show performance results of RCGA. We consider MCSP
instances of both three and sevel cells. The requests for contents follow a
binomial distribution $B(I,0.5)$. Let $\rho^{m}\in(0,1)$ be the percentage of
MCRs. In our simulation, the MCRs have either two or three candidate cache
servers. Denote the ratio between the number of MCRs with three candidate
servers to that of two candidate servers by $\rho^{\rm tt}$. We will present
the numerical results for various values of $\rho^{m}$ and $\rho^{\rm tt}$.
The cache capacity is set to be $C_{h}=\frac{1}{2}\sum_{i\in\mathcal{I}}s_{i}$
$(\forall h\in\mathcal{H})$. We are more interested in the impact of backhaul
capacity as it is a bottleneck for AoI, so we set it to be
$G_{h}=G=\rho^{b}\sum_{i\in\mathcal{I}}s_{i}$ $(\forall h\in\mathcal{H})$, and
vary $\rho^{b}$ in interval $[0.1,0.5]$. We take $f_{i}(a)=\mathrm{e}^{a}$
$(a\in\mathbb{N})$ as our AoI cost function, and the function is in fact the
reciprocal of an AoI utility function in [30]. In addition, we set $\alpha=11$
and $\beta=1$. The size of contents is uniformly generated within $[1,10]$.

###  5.2 Benchmarks

In our simulation, we use three benchmark schemes.

####  5.2.1 PBA

We take the cost obtained by a heuristic algorithm named Popularity-based
Algorithm (PBA) [35] as a baseline scheme. In PBA, a content with many
requests has higher priority of being cached and updated, and the cached
contents will be subject to update when its AoI cost has reached half of its
download cost. If the cache or backhaul capacity does not allow a content to
be cached or updated, PBA will consider the next content by the
prioritization.

####  5.2.2 OPT

This baseline scheme is the optimum of ILP (8) obtained by Gurobi optimizer
[32]. With this benchmark, we can accurately measure the deviation of RCGA and
PBA from the optimum. However, it is computationally difficult to obtain
global optimum for the 7-cell instances, so we use it for evaluation only for
3-cell instances.

####  5.2.3 LB

We also take the LB obtained by performing column generation without rounding
as a reference value. It is a valid comparison because the deviation with
respect to the global optimum will never exceed the deviation from the LB. We
will see that, numerically, using the LB remains accurate in gauging the gap
from the optimum.

$25$$50$$75$$100$$125$$150$$0$$1$$2$$3$$\cdot 10^{3}$Cost (3-cell)RCGAPBAOPT

$50$$100$$150$$200$$250$$300$$0$$5$$10$$15$$\cdot 10^{3}$The number of
contents $I$Cost (7-cell)RCGAPBALB

Figure 4: The average cost as function of the number of contents $I$ when
$T=12$, $G=0.3\sum_{i\in\mathcal{I}}s_{i}$, $\rho^{m}=40\%$, and $\rho^{\rm
tt}=1:1$. The numbers of requests $R$ in the 3-cell and 7-cell instances are
$500$ and $2000$, respectively.

$200$$300$$400$$500$$600$$700$$1$$2$$\cdot 10^{3}$Cost (3-cell)RCGAPBAOPT

$500$$1{,}000$$1{,}500$$2{,}000$$2{,}500$$3{,}000$$2$$4$$6$$8$$10$$\cdot
10^{3}$The number of requests $R$Cost (7-cell)RCGAPBALB

Figure 5: The average cost as function of the number of requests $R$ when
$T=12$, $G=0.3\sum_{i\in\mathcal{I}}s_{i}$, $\rho^{m}=40\%$, and $\rho^{\rm
tt}=1:1$. The numbers of contents $I$ in the 3-cell and 7-cell instances are
$100$ and $200$, respectively.

###  5.3 Rounding Strategy Performance

In Section 4.4, we claimed that a naive strategy that directly performs
rounding on the $\chi$-variables might not be satisfactory. Table I shows a
comparison of the solutions obtained by the naive rounding strategy (NRS) and
RCGA for 3-cell and 7-cell scenarios with $100$ instances each. Success rate
represents the percentage instances for which rounding leads to feasible
solutions. It can be seen that NRS has a much lower success rate than RCGA.
Column Gap in the table is the average gap of the feasible solutions from the
optimum/LB. Obviously, RCGA is superior to NRS.

TABLE I: Comparison between NRS and RCGA Method | Scale | Success rate | Gap
---|---|---|---
NRS | 3-cell | $61\%$ | $2.6\%$
7-cell | $48\%$ | $5.2\%$
RCGA | 3-cell | $100\%$ | $0.8\%$
7-cell | $100\%$ | 1$.2\%$

###  5.4 Overall Performance and Analysis

Figs. 4 and 5 show the performance results for various numbers of contents and
requests, respectively. Overall, the numerical results demonstrate that RCGA
can provide very good solutions with at most 2.4% deviation from the
optimum/LB, and outperforms PBA significantly.

The results in Fig. 4 present that the cost obtained by RCGA changes only
slightly when increasing the number of contents, whereas there is a
significant increase for PBA. When the number of contents increases, more
relatively unpopular contents will be requested due to the binomial
distribution, and these requests for result in a higher download cost for PBA.
The solutions offered by RCGA are based on specific requests, so the
increasing number of contents hardly impacts on RCGA when the number of
requests is fixed.

Fig. 5 shows the impact of the number of requests on cost. We can see that the
costs obtained by RCGA and PBA both increase almost linearly with the number
of requests. Thus the relative gap of the solutions offered by both PBA and
RCGA from the optimum/LB actually decreases. The reason is that with larger
number of requests, the cached contents are also requested more often.

###  5.5 Impact of MCRs

We are curious about the impact of the proportion of MCRs on RCGA in the
aspects of the solution time and the optimality gap from the LB, thus we
examine RCGA for the 7-cell instances with different values of $\rho^{\rm m}$
and $\rho^{\rm tt}$. The results are shown in Table II. We can see that RCGA
can efficiently provide good solutions that are at most $1.59\%$ from the LB.
Also, the results in Table II demonstrate that the solution time of RCGA is
hardly impacted by the number of MCRs. This is because the proportion of MCRs
affects the scale of RMP but not the SP, and the time of solving SPs dominates
the overall solution time in RCGA.

TABLE II:  Impact of the proportion of MCRs

[b]  $\bm{\rho}^{\rm\bf m}$ $\bm{\rho}^{\rm\bf tt}$ Time (s) Gap $20\%$ $3:1$
$4.82$ $1.20\%$ $1:1$ $3.23$ $0.97\%$ $1:3$ $5.38$ $1.59\%$ $40\%$ $3:1$
$6.90$ $0.33\%$ $1:1$ $7.22$ $1.38\%$ $1:3$ $3.36$ $0.51\%$ $60\%$ $3:1$
$4.36$ $1.23\%$ $1:1$ $7.36$ $0.43\%$ $1:3$ $8.36$ $0.52\%$

  * $\dagger$

$R=5000$, $T=12$, and $G=0.3\sum_{i\in\mathcal{I}}s_{i}$.

###  5.6 Impact of Backhaul Capacity

$0$$20$$40$$60$$80$$100$Percentage (%)Download costUpdate costAoI
cost$0$$1$$2$$3$$4$$\cdot 10^{5}$Cost (PBA)Cost

0.10.150.20.250.3$0$$20$$40$$60$$80$$100$The scaling factor of backhaul
capacity $\rho^{b}$Percentage (%)$0$$1$$2$$3$$4$$\cdot 10^{5}$Cost (RCGA)

Figure 6: For various backhaul capacity levels in a 7-cell instance, the line
shows the cost (labeled on the left y-axis), and the bars show the proportions
of three types of cost (labeled on the right y-axis) within the overall cost.
The parameters of the instance are $I=200$, $R=5000$, $T=12$, $\rho^{\rm
m}=40\%$, and $\rho^{\rm tt}=1:1$.

In some cases, backhaul capacity will be the bottleneck resulting in a higher
download cost. We evaluate a 7-cell instance under varying backhaul capacity
levels. Fig. 6 shows both the cost and the proportions of three types of cost
within the overall cost. Apparently, the cost decreases by increasing the
backhaul capacity. Moreover, the proportion of download cost also decreases
because more requests can be satisfied with the cached and low-AoI contents,
instead of using the cloud server. There is a saturation effect on PBA when
$\rho^{b}\geq 0.2$, however. We can see that, for PBA, the download cost
always exists no matter how large the backhaul capacity is. This is because
those requests for relatively unpopular contents have to be satisfied by the
cloud server. For RCGA, the download cost can be decreased to zero when
$\rho^{b}\geq 0.25$, as RCGA is request-tailored. In addition, with larger
backhaul capacity, intuitively the proportion of update cost will grow at
optimum, whereas in addition to the download cost, the AoI cost proportion
shall go down due to higher information freshness. This is indeed the case for
RCGA.

##  6 Conclusion

We have considered a content scheduling problem for multi-cell caching where
the multiple cells are coupled with each other due to overlapping coverage
areas. We have proved the NP-hardness of the problem. We formulated the
problem as an integer liner program (ILP). The ILP provides optimal solutions,
but it is not practical to large-scale instances in terms of running time.
Making the use of the structure of this optimization problem, we have proposed
an algorithm based on column generation. The algorithm can efficiently obtain
close-optimal solutions that are within a few percent from global optimality.
These observations together represent a step closer toward deploying large-
scale MEC systems.

## References

  * [1] Z. Yu, T. Deng, Y. Zhao, and D. Yuan, “Multi-cell caching: Fresh information with minimum cost,” in _2022 IEEE Wireless Communications and Networking Conference Workshops (WCNC WKSHPS)_. IEEE, 2022, pp. 327–332.
  * [2] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “A survey on mobile edge computing: The communication perspective,” _IEEE Communications Surveys Tutorials_ , vol. 19, no. 4, pp. 2322–2358, 2017.
  * [3] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?” in _2012 IEEE Conference on Computer Communications (INFOCOM)_. IEEE, 2012, pp. 2731–2735.
  * [4] E. Bastug, M. Bennis, and M. Debbah, “Living on the edge: The role of proactive caching in 5G wireless networks,” _IEEE Communications Magazine_ , vol. 52, no. 8, pp. 82–89, 2014.
  * [5] C. Liang, Y. He, F. R. Yu, and N. Zhao, “Enhancing video rate adaptation with mobile edge computing and caching in software-defined mobile networks,” _IEEE Transactions on Wireless Communications_ , vol. 17, no. 10, pp. 7013–7026, 2018.
  * [6] L. Li, M. Wang, K. Xue, Q. Cheng, D. Wang, W. Chen, M. Pan, and Z. Han, “Delay optimization in multi-UAV edge caching networks: A robust mean field game,” _IEEE Transactions on Vehicular Technology_ , vol. 70, no. 1, pp. 808–819, 2021.
  * [7] T. X. Vu, S. Chatzinotas, and B. Ottersten, “Edge-caching wireless networks: Performance analysis and optimization,” _IEEE Transactions on Wireless Communications_ , vol. 17, no. 4, pp. 2827–2839, 2018.
  * [8] B. Tan and L. Massoulié, “Optimal content placement for peer-to-peer video-on-demand systems,” _IEEE/ACM transactions on networking_ , vol. 21, no. 2, pp. 566–579, 2012.
  * [9] T. Deng, G. Ahani, P. Fan, and D. Yuan, “Cost-optimal caching for D2D networks with user mobility: Modeling, analysis, and computational approaches,” _IEEE Transactions on Wireless Communications_ , vol. 17, no. 5, pp. 3082–3094, 2018.
  * [10] J. Wen, K. Huang, S. Yang, and V. O. Li, “Cache-enabled heterogeneous cellular networks: Optimal tier-level content placement,” _IEEE Transactions on Wireless Communications_ , vol. 16, no. 9, pp. 5939–5952, 2017.
  * [11] L. Chen, L. Song, J. Chakareski, and J. Xu, “Collaborative content placement among wireless edge caching stations with time-to-live cache,” _IEEE transactions on multimedia_ , vol. 22, no. 2, pp. 432–444, 2019.
  * [12] B. Banerjee, A. Kulkarni, and A. Seetharam, “Greedy caching: An optimized content placement strategy for information-centric networks,” _Computer Networks_ , vol. 140, pp. 78–91, 2018.
  * [13] K. Poularakis, J. Llorca, A. M. Tulino, I. Taylor, and L. Tassiulas, “Service placement and request routing in mec networks with storage, computation, and communication constraints,” _IEEE/ACM Transactions on Networking_ , vol. 28, no. 3, pp. 1047–1060, 2020.
  * [14] Z. Yang, Y. Liu, Y. Chen, and N. Al-Dhahir, “Cache-aided NOMA mobile edge computing: A reinforcement learning approach,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 10, pp. 6899–6915, 2020.
  * [15] L. Li, Y. Xu, J. Yin, W. Liang, X. Li, W. Chen, and Z. Han, “Deep reinforcement learning approaches for content caching in cache-enabled D2D networks,” _IEEE Internet of Things Journal_ , vol. 7, no. 1, pp. 544–557, 2020.
  * [16] Y. Sun, E. Uysal-Biyikoglu, R. D. Yates, C. E. Koksal, and N. B. Shroff, “Update or wait: How to keep your data fresh,” _IEEE Transactions on Information Theory_ , vol. 63, no. 11, pp. 7492–7508, 2017.
  * [17] Q. He, G. Dán, and V. Fodor, “On emptying a wireless network with minimum-energy under age constraints,” in _IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , 2019, pp. 668–673.
  * [18] S. Farazi, A. G. Klein, and D. R. Brown, “Fundamental bounds on the age of information in general multi-hop interference networks,” in _IEEE INFOCOM 2019-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_. IEEE, 2019, pp. 96–101.
  * [19] Q. He, G. Dan, and V. Fodor, “Minimizing age of correlated information for wireless camera networks,” in _IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , 2018, pp. 547–552.
  * [20] A. Maatouk, M. Assaad, and A. Ephremides, “Minimizing the age of information: NOMA or OMA?” in _IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , 2019, pp. 102–108.
  * [21] Q. Liu, C. Li, Y. T. Hou, W. Lou, and S. Kompella, “Aion: A bandwidth optimized scheduler with aoi guarantee,” in _IEEE INFOCOM 2021-IEEE Conference on Computer Communications_. IEEE, 2021, pp. 1–10.
  * [22] C. Kam, S. Kompella, G. D. Nguyen, J. E. Wieselthier, and A. Ephremides, “Information freshness and popularity in mobile caching,” in _2017 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2017, pp. 136–140.
  * [23] G. Ahani and D. Yuan, “Accounting for information freshness in scheduling of content caching,” in _ICC 2020-2020 IEEE International Conference on Communications (ICC)_. IEEE, 2020, pp. 1–6.
  * [24] S. Zhang, L. Wang, H. Luo, X. Ma, and S. Zhou, “AoI-delay tradeoff in mobile edge caching with freshness-aware content refreshing,” _IEEE Transactions on Wireless Communications_ , vol. 20, no. 8, pp. 5329–5342, 2021\.
  * [25] G. Ahani, D. Yuan, and S. Sun, “Optimal scheduling of age-centric caching: Tractability and computation,” _IEEE Transactions on Mobile Computing_ , 2020, doi: 10.1109/TMC.2020.3045104.
  * [26] C. Xu, Y. Xie, X. Wang, H. H. Yang, D. Niyato, and T. Q. Quek, “Optimal status update for caching enabled iot networks: A dueling deep r-network approach,” _IEEE Transactions on Wireless Communications_ , vol. 20, no. 12, pp. 8438–8454, 2021.
  * [27] M. Ma and V. W. Wong, “Age of information driven cache content update scheduling for dynamic contents in heterogeneous networks,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 12, pp. 8427–8441, 2020\.
  * [28] Y. Guan, X. Zhang, and Z. Guo, “Prefcache: Edge cache admission with user preference learning for video content distribution,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 31, no. 4, pp. 1618–1631, 2021.
  * [29] N. Zhang, K. Zheng, and M. Tao, “Using grouped linear prediction and accelerated reinforcement learning for online content caching,” in _2018 IEEE International Conference on Communications Workshops (ICC Wkshps)_. IEEE, 2018, pp. 1–6.
  * [30] S. Ioannidis, A. Chaintreau, and L. Massoulie, “Optimal and scalable distribution of content updates over a mobile social network,” in _IEEE INFOCOM 2009_ , 2009, pp. 1422–1430.
  * [31] Monotone 3-satisfiability. [Online]. Available: https://npcomplete.owu.edu/2016/04/15/monotone-3-satisfiability/
  * [32] Gurobi optimizer 9.1. [Online]. Available: https://www.gurobi.com/
  * [33] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, _Network Flows: Theory, Algorithms, and Applications_. Prentice-Hall, Inc., 1993.
  * [34] M. Karamanov and G. Cornuéjols, “Branching on general disjunctions,” _Mathematical Programming_ , vol. 128, no. 1, pp. 403–436, 2011.
  * [35] H. Ahlehagh and S. Dey, “Video-aware scheduling and caching in the radio access network,” _IEEE/ACM Transactions on Networking_ , vol. 22, no. 5, pp. 1444–1462, 2014.


11institutetext: Department of Mathematics “Giuseppe Peano”, University of
Torino, via Carlo Alberto 10, 10123 Torino, Italy
11email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
# Node-Binded Communities for Interpolation on Graphs

Roberto Cavoretto  0000-0001-6076-4115 Alessandra De Rossi
0000-0003-1285-3820 Sandro Lancellotti  0000-0003-4253-3561 Federico
Romaniello  0000-0003-1166-3179

###### Abstract

Partition of unity methods (PUMs) on graphs represent straightforward and
remarkably adaptable auxiliary techniques for graph signal processing. By
relying solely on the intrinsic graph structure, we propose the generation of
a partition of unity through centrality measures and modularity. Subsequently,
we integrate PUMs with a local graph basis function (GBF) approximation
approach to achieve low-cost global interpolation schemes.

###### Keywords:

Partition of unity method (PUM) graph basis functions (GBFs) kernel-based
approximation and interpolation graph signal processing graph theory.

##  1 Introduction

Graph signal processing is a very popular tool when it comes to study the
field of graph signals and, for this reason, several mathematical techniques
such as filtering, compression, noise removal, sampling or decomposition are
deeply investigated in the literature, see [8, 13]. Moreover, graphs naturally
appear in a multitude of problems, as in social networks or traffic maps.
However, in general, they have a complex structure that requires efficient and
fast processing tools for their analysis.
Partition of unity methods (PUMs) allow to perform operations such as signal
reconstruction from samples, classification of nodes, or signal filtering
locally on smaller portions of the graph, and, then, rebuilding the global
signal from the local ones. In meshfree approximation, the combination of
radial basis functions (RBFs) with PUMs yields significantly sparser system
matrices in collocation or interpolation problems, and, therefore, a
considerable speed-up of calculations [1]. In what follows, we will focus on
approximation methods based on generalized translates of a graph basis
function (GBF), see [4] and [5] for more details.
In this article, we provide a more adaptive technique for the selection of the
partitions on the graph than the one presented in [3]. In particular, by using
a process that automatically find an optimal number of subdomain based on
their modularity and on the underlying graph structure, we do not need the
desired number of subdomains as an input for the GBF-PUM algorithm.
In Section 2 we give a brief overview of graph theory and positive definite
GBFs for signal approximation on graphs. A description of our algorithm and
how it can be integrated to the GBF-PUM proposed in [3] is provided in Section
3. In the final Section 4 we conclude with some numerical examples.

##  2 Preliminaries

###  2.1 Graph theory

In this article, we will use connected, simple and undirected graphs. Indeed,
a graph $G$ is defined as $G=(V(G),E(G))$ where:

  * •

$V(G)$ is the _vertex set_ of the graph;

  * •

$E(G)\subseteq V(G)\times V(G)$ is the _edge set_ of the graph containing all
edges of the form $(u,v):u\neq v$.

  * •

A is the _adjacency matrix_ of $G$, where $A_{ij}=1$ if $(v_{i},v_{j})$ is an
edge, zero otherwise;

  * •

A general symmetric graph Laplacian of the form
$\textbf{L}=\textbf{D}-\textbf{A}$, where D is the diagonal matrix with the
degree of the vertices as entries.

A _graph signal_ $x:V(G)\rightarrow\mathbb{R}$ is a function on the vertices
$V$ of $G$. We denote the $n$-dimensional vector space of all graph signals by
$\mathcal{L}(G)$. A graph $H=(V(H),E(H))$ is called a _subgraph_ of
$G=(V(G),E(G))$ if and only if $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$.
A collection of disjoint subgraphs of $G$ which covers $V(G)$ is a _partition_
of $G$ and the subgraphs are called _communities_. Given $u\in V(G)$, the set
$N(u)=\left\\{v\in V(G)|(u,v)\in E(G)\right\\}$ is the _neighbourhood_ of $u$.
Let $u,v\in V(G)$, the _Jaccard similarity index_ $J(u,v)=\frac{|N(u)\cap
N(v)|}{|N(u)\cup N(v)|}$ measures the similarity between two vertices. It can
easily be extended to communities $U,V$ of $G$ as follows:

$J(U,V)=\operatorname*{avg}\limits_{u\in U,v\in V}\left\\{J(u,v)\right\\}.$

The _modularity_ $Q$ of a graph measures the strength of division of a graph
into communities $c_{1},\dots,c_{n}$. Graphs with high modularity have dense
connections between the vertices within communities but sparse connections
between vertices in different communities. It is defined as

$Q=\frac{1}{2m}\sum_{i,j}\left(A_{ij}-\frac{k_{i}k_{j}}{2m}\right)\delta(c_{i},c_{j}),$

where $m$ is the number of edges, $k_{i}$ is the degree of $i$ and
$\delta(c_{i},c_{j})$ is 1 if $i$ and $j$ are in the same community, zero
otherwise. _Katz centrality_ computes the relative influence of a vertex
within a graph by measuring the number of the immediate neighbours and also
all other vertices in the network that connect to the vertex under
consideration through these immediate neighbours. Connections made with
distant neighbours are, however, penalized by an attenuation factor $\alpha$,
usually set as $0.5$. The Katz centrality for vertex $v_{i}$ is:

$C_{Katz}(v_{i})=\sum_{k=1}^{\infty}\sum_{j=1}^{n}\alpha^{k}(A^{k})_{ij}.$

###  2.2 Positive definite GBFs for signal approximation on graphs

GBFs prove to be straightforward and effective instruments for the
interpolation and approximation of graph signals, especially in scenarios
where only a limited number of samples is available. Notably, employing
positive definite GBFs tends to yield superior results. The theoretical
underpinnings closely align with a parallel theory in scattered data
approximation using positive definite RBFs in Euclidean space, as detailed in
[11] and [15]. Within this graph-based methodology, the approximation spaces
are constructed by employing generalized shifts of a GBF, denoted as $f$, and
are articulated in terms of a convolution operator. Numerical examples
presented in Section 4 rely on polyharmonic splines on graphs, which are an
example of a positive definite GBF based on the kernel:

$\textbf{K}_{f_{(\epsilon\textbf{I}_{n}+\textbf{L})^{-s}}}=(\epsilon\textbf{I}_{n}+\textbf{L})^{-s}=\sum_{k=1}^{n}\frac{1}{(\epsilon+\lambda_{k})^{s}}u_{k}u_{k}^{T},$

where $u_{1},\dots,u_{n}$ are the eigenvectors of the Laplacian L which form
an orthonormal basis for the space $\mathcal{L}(G)$. If $\lambda_{1}$ is the
largest eigenvalue of $\mathbf{L}$, this kernel is positive definite for
$\epsilon>-\lambda_{1}$ and $s>0$ (see, [9] and [14]).

##  3 Topology Based Subdomain Detection

Signal interpolation on graphs with PUM requires overlapping subdomains with
the property that at least one vertex of the subdomain is an interpolation
node. In what follows we describe how it is possible to find such subdomains
for PUM on graphs, based on the structural topology of the underlying
structure.

###  3.1 Overlapping communities detection

Communities detection is an edge-cutting topic in graph theory, indeed
different approaches may be used, see [7] for a detailed overview. Our method
is a divisive technique where the centrality of the interpolation nodes is the
main criterion for splitting. In particular, we extend the procedure presented
in [12] allowing overlapping among communities. Our iterative algorithm
repeats the following steps until some conditions on the presence of
interpolation nodes and modularity are satisfied. It can be summarised as
follows:

Algorithm 1 Node-Binded Communities Detection

Input: The graph $G$, the set of interpolation nodes $W$.

Set $C=G$, $Q=-1$, $Q^{\prime}=-\frac{1}{2}$;

while $|C|\leq|W|$ and $Q^{\prime}>Q$: do

For each $c$ in $C$ try to split and update $C$, $Q$ and $Q^{\prime}$;

end while

Merge small communities with the most similar big one and update $C$;

For each $c$ in $C$ expand $c$ to create overlapping subdomain.

Output: The set of overlapping communities $C$.

In detail, in the splitting process we find the two interpolation nodes with
the highest Katz centrality in each community, if they exist, and divide the
community into two sub-components, each one containing one of the samples.
When the splitting process terminates, the _small_ communities containing less
than $2\%$ of vertices are merged with the most similar big community,
according to the Jaccard index. Finally, the overlapping expansion is
performed for each community, where the more edges a community shares with the
others, the more it is augmented.

###  3.2 GBF-PUM approximation on graphs

Partition of unity is a widespread tool used in mesh-free approximation
problems as it sharply reduces the computational cost when related subproblems
are solved [6]. In [2] and [3] this technique has been adapted to graph signal
interpolation and it may be applied to social networks or traffic map problems
because of their underlying graph structure. The algorithm is made of the
following steps:

Algorithm 2 GBF-PUM Approximation on Graphs

Input: The graph $G$, the set of communities $C$, the set of interpolation
nodes $W$.

Construct a partition of unity subordinate to the communities in $C$;

For all subgraphs $c$ in $C$ calculate the local Laplacian $\textbf{L}^{c}$;

For all subgraphs $c$ in $C$ construct the local GBF kernel;

For all subgraphs $c$ in $C$ calculate the local GBF approximant;

Create a global GBF-PUM approximation from the local ones.

Output: GBF-PUM approximant of the signal.

We note that overlapping subdomains are needed for a good PUM. In addition to
this, we remark that the global approximation is a weighted sum of the local
approximants by means of weighted functions defined by each subdomain. Further
details on the error of the global approximant can be found in [3].

##  4 Numerical Examples

In this section our framework is applied on the Minnesota Road Graph [10],
given a signal on its vertex set. This graph has 2642 vertices and 3304 edges;
we test the algorithm on sets of 200, 400, 600 and 800 sampling nodes used as
interpolation nodes. We remark here we do not require the number of
communities as an input and this is the main difference with respect to [2]
and [3].

Figure 1: On top the partition of the vertices in 6 different disjoint subdomains is shown. It is obtained using 200 interpolation points, marked in yellow. On bottom a subdomain is highlighted to show how it is expanded to create the overlap (left to right). N | Communities | RRMSE | time (s)
---|---|---|---
200 | 6 | 1.102e-01 | 1.18e02
400 | 11 | 7.047e-02 | 1.26e02
600 | 6 | 5.456e-02 | 1.26e02
800 | 9 | 4.499e-02 | 1.69e02
Table 1: A summarisation of the numerical results for increasing number of
sampling nodes. The number of communities, RRMSE and computational time are
also shown.

It is worth noting that the numerical results on the Relative Root Mean Square
Error (RRMSE) are of the same order as the ones obtained by the authors in [3]
with 6 subdomains and augmentation of communities with neighbours at distance
2, given as input. We observe here that the number of communities in our
algorithm depends only on the centrality of the interpolation nodes and it is
not given as input. Moreover, our criterion for the augmentation of the
communities depends on the ratio $r(v)$ between the number of neighbours of a
vertex $v$ inside its community and the total number of its neighbours:

  1. 1.

if $r(v)\leq 0.4$: expand with neighbours at distance 2;

  2. 2.

if $0.4<r(v)\leq 0.8$: expand with neighbours at distance 1.

The numerical results are summarised in Table 1. Figure 1 highlights the 6
communities found by our algorithm with the 200 sampling nodes marked in
yellow (top), then we show how one of them is augmented to create the
overlapping (bottom).

All tests were carried out on the infrastructure for high-performance
computing _MathHPC_ , virtual cloud server of the structure _HPC4AI_ (High-
Performance Computing for Artificial Intelligence:
https://www.dipmatematica.unito.it/do/progetti.pl/View?doc=Laboratori_di_ricerca.html).

### Acknowledgments

The authors sincerely thank the reviewers for the careful reading and valuable
comments on the paper. This research has been accomplished within the RITA
“Research ITalian network on Approximation” and the UMI Group
TAA“Approximation Theory and Applications”. This work has been supported by
the INdAM–GNCS 2022 Project “Computational methods for kernel-based
approximation and its applications”, code CUP$\\_$E55F22000270001, and by the
Spoke “FutureHPC & BigData” of the ICSC – National Research Center in ”High-
Performance Computing, Big Data and Quantum Computing”, funded by European
Union – NextGenerationEU. Moreover, the work has been supported by the
Fondazione CRT, project 2022 “Modelli matematici e algoritmi predittivi di
intelligenza artificiale per la mobilit$\grave{\text{a}}$ sostenibile”.

## References

  * [1] R. Cavoretto, A. De Rossi, _Error indicators and refinement strategies for solving Poisson problems through a RBF partition of unity collocation scheme_ , Appl. Math. Comput. 369 (2020), 124824.
  * [2] R. Cavoretto, A. De Rossi, W. Erb, _GBFPUM - A MATLAB Package for Partition of Unity Based Signal Interpolation and Approximation on Graphs_ , Dolomites Res. Notes Approx. 15 (2022), 25–34.
  * [3] R. Cavoretto, A. De Rossi, W. Erb, _Partition of Unity Methods for Signal Processing on Graphs_. J. Fourier Anal. Appl. 27 (2021), Art. 66
  * [4] W. Erb, _Graph Signal Interpolation with Positive Definite Graph Basis Functions_. Appl. Comput. Harmon. Anal. 60 (2022), 368–395.
  * [5] W. Erb, _Semi-Supervised Learning on Graphs with Feature-Augmented Graph Basis Functions_. arXiv:2003.07646 (2020).
  * [6] G.E. Fasshauer, M.J. McCourt, _Kernel-based Approximation Methods Using MATLAB_. World Scientific, Singapore, (2015), 536 pp.
  * [7] M. Newman, _Networks: An Introduction_. OUP Oxford, (2010), 784 pp.
  * [8] A. Ortega, P. Frossard, J. Kovačević, J.M.F. Moura, P. Vandergheynst, _Graph signal processing: overview, challenges, and applications_ , Proc. IEEE 106, 5 (2018), 808–828.
  * [9] I.Z. Pesenson, _Variational splines and Paley-Wiener spaces on combinatorial graphs_. Constr. Approx. 29, 1 (2009), 1–21.
  * [10] R.A. Rossi, N.K. Ahmed, _The Network Data Repository with Interactive Graph Analytics and Visualization_. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (2015), _http://networkrepository.com_.
  * [11] R. Schaback, H. Wendland, _Approximation by Positive Definite Kernels_. In Advanced Problems in Constructive Approximation, Birkhäuser Verlag, Basel (2003), 203–222
  * [12] H. Shin, J. Park, D. Kang, _A Graph-Cut-Based Approach to Community Detection in Networks_. Appl. Sci. (2022), 12, 6218.
  * [13] L. Stanković, L. Daković, E. Sejdić, _Introduction to Graph Signal Processing_. In Vertex-Frequency Analysis of Graph Signals, Springer (2019), 3–108.
  * [14] J.P. Ward, F.J. Narcowich, J.L. Ward. _Interpolating splines on graphs for data science applications_. Appl. Comput. Harm. Anal. 49, 2 (2020), 540–557.
  * [15] H. Wendland, _Scattered Data Approximation_. Cambridge University Press, Cambridge, (2005). 336 pp.