Mobility-Aware Routing and Caching in Small Cell Networks using Federated Learning

In the majority of references mentioned above, the popularity profile of content files is either known a prior or modeled as a Zipf-like distribution [30][31]. However, such an assumption is unrealistic in practice, particularly for the dense small-cell networks: (i) The file popularity is often non-stationary due to the dynamic nature of contents; (ii) Perfect knowledge of file popularity is technically difficult to guarantee, especially for intensive instantaneous demands; (iii) File popularity is an outcome of the decisions of a dense population, and very costly to predict [4]. In such a situation, developing a low-cost and effective learning-based approach for estimating the files’ popularity becomes imperative. Besides, to our best knowledge, no research has considered joint routing and cache placement optimization for resource-constrained small-cell networks so far.

Against this background, we focus on developing mobility-aware routing and caching strategies for dynamic small-cell networks under uncertainty. To jointly optimize the routing and cache placement, we first formulate the network cost minimization problem, which is an NP-hard integer programming (NIP) problem. We propose a federated routing and popularity learning (FRPL) approach by which the SBSs learn the popularity of files as a function of the non-stationary pedestrian- and request densities. To avoid unnecessary data retransmission via the backhaul, we develop a novel content transmission protocol that improves the cache-efficiency (CE) performance of SBSs. Besides, we optimize the cache placement using an algorithm that greedily approximates the minimizer of the NIP problem. The contributions of this paper are as follows:

• •

  Motivated by the notion of the one-stop-shop (OSS), we propose an FRPL approach that enables SBSs to complete multiple tasks simultaneously, thus reducing the processing time. That is crucial as the time slot within one global aggregation is limited.

• •

  The proposed FRPL method jointly learns the routing and content popularity considering the influence of both the users’ mobility and the SBSs’ geographical location. Therefore, it is robust against even in a highly dynamic and non-stationary network.

• •

  We design a cache placement approach that exploits the outcome of FRPL method combined with a novel transmission protocol to minimize the network’s content delivery cost by optimizing the cached content and delivery strategy.

• •

  Numerical results show that our cache placement policy guarantees a higher cache hit rate for SBSs compared to the existing schemes, although the MUs’ demand density is a priori unknown. Besides, the proposed greedy cache placement approach reduces the network cost compared to the state-of-the-art research. We also show the effectiveness of the proposed FRPL approach.

In Section II, we present the network model, FL model, and content request model. We then formulate the associated resource-constrained network optimization problem. In Section III, we propose an FRPL approach for multi-task learning. The analysis of the proposed model and solution appear in Section IV. Section V includes the numerical analysis. Section VI concludes the paper.

Notations: Bold lower case letters represent vectors, whereas bold upper case letters denote matrices. $\left[{\cdot}\right]^{T}$, $\left\|{\cdot}\right\|_{0}$, and $\left\|{\cdot}\right\|$ denote transpose, $l_{0}$-norm, and $l_{2}$-norm operations, respectively. Besides, $\mathbb{E}[\cdot]$ is used to denote the statistical expectation operation. $\nabla$ represents the gradient of a function. Table II summarizes the frequently-used variables in the order of appearance in the paper.

We consider a network consisting of $K$ SBSs and one MBS. The network serves $U$ MUs simultaneously. Due to the dense deployment, the coverage areas of the SBSs and the MBS overlap; Hence, at each time, an MU might be in the communication range of multiple entities that can contribute to learning and service delivery (contributors or participants). Before proceeding, we present a definition.

Throughout the paper, we use two time scales: (i) $t=\{1,2,\cdots,\boldsymbol{\theta}\}$. It refers to a learning round (period) in the FRPL method, where $\boldsymbol{\theta}$ is the required time until the global loss function converges; and (ii) $T(\boldsymbol{\theta})=\{1,2,\cdots\}$, which corresponds every instance of the global aggregation. Thus, each global aggregation consists of several learning rounds. The proposed cache placement approach takes several iterations; however, at one time instant (learning period), both the routing strategy and cache placement remain fixed.

FL is the core of the proposed FRPL methodology. The MBS and SBSs collaboratively learn a shared model while each entity retains its training data at its side. The FL model trained at the participant’s side is the local model. The MBS integrates the local models and generates the global model, which improves the local model of each participant. Fig. 1 shows the workflow and details follow.

Consider $I$ participants labeled as $\{1,\cdots,{I}\}$. We denote the input data of participant $i$, $i\in\{1,\cdots,{I}\}$ by $\mathbf{X}_{i}=[\mathbf{x}_{i,1},\cdots,\mathbf{x}_{i,Q_{i}}]$, where $Q_{i}$ indicates the number of the samples. Thus $\mathbf{X}_{i}$ is the entry vector to train the local FL model. The output vector is $\mathbf{y}_{i}=[y_{i,1},\cdots,y_{i,Q_{i}}]^{T}$. The vector $\boldsymbol{\rho}_{i}$ captures the model parameters of the local FL model. Under a linear model assumption, we have $\mathbf{y}_{i}=\mathbf{X}_{i}\boldsymbol{\rho}_{i}+\mathbf{n}$, where $\mathbf{n}$ is measurement noise typically approximated as Gaussian i.i.d. samples. In the standard gradient descent (SGD) methods [32], [33], training and update procedures of the local FL model aims at finding optimal parameters $\boldsymbol{\rho}_{i}$ that minimize the squared error cost function $f(\boldsymbol{\rho}_{i},\mathbf{X}_{i},\mathbf{y}_{i})=||\mathbf{X}_{i}\boldsymbol{\rho}_{i}-\mathbf{y}_{i}||^{2}$. We define a vector $\boldsymbol{\beta}$ to capture the parameters related to the global FL model. The update of the global model therefore is given by $\boldsymbol{\beta}=\;\frac{1}{Q}\sum\nolimits_{i=1}^{{I}}\;Q_{i}\boldsymbol{\rho}_{i}$. Section III provides more details of the FRPL framework.

We consider a content library with $M$ contents. The size of each file $f\in\{1,\cdots,M\}$ is $g_{f}$. The MUs request file $f$ randomly and independently with probability $p_{f}\in[0,1]$ so that $\mathbf{p}=[p_{1},\cdots,p_{M}]^{T}$ is the request probability vector. Traditionally, upon requesting a file within the time deadline $\tau$, an MU obtains it through random caching, local SBS caching, or MBS caching [2]. Nevertheless, such naive caching mechanisms barely guarantee a high cache efficiency for the following reasons: (i) They largely neglect the limited storing capacity and the finite bandwidth; (ii) They often retransmit the data unnecessarily. Therefore, we decompose the cache domain of an MU’s required contents into three categories:

• •

  Local Caching: The MU first checks the local SBS. If the required content is cached, then the MU obtains it directly from there within the time deadline $\tau$. Otherwise, the MU receives it from one of the following sources:

• •

  Intra-Cell Caching: If the local SBS does not have the required content, it can fetch it from other SBSs in the intra-cell domain upon availability so that the MU is served within the deadline $\tau$.

• •

  Inter-Cell Caching: If no SBS in the intra-cell domain has the required content, the local SBS fetches it via the backhaul link, from an external SBS deployed in the other overlapped cells or, in the worst case, from the MBS.

We focus on the following challenges: (i) When MUs migrate into one area, proper retrieving of several requested files over a backhaul while minimizing the cost becomes complicated; (ii) The MUs’ preferences affect the cache efficiency of SBSs. Moreover, distributed caching might result in duplicate files in a small area; (iii) Joint learning and cache placement, also service provisioning, can yield long delays.

Let $\mathbf{C}\in\{0,1\}^{K\times M}$ be a binary caching strategy of the required contents in SBS, where $c_{k,f}=1$ indicates the $k$th SBS stores the file $f$, and $c_{k,f}=0$ indicates otherwise. Let $\sum\nolimits_{k=1}^{K}\sum\nolimits_{f=1}^{M}c_{k,f}\cdot\alpha_{C_{f}}$ denote the SBS’s aggregated cost as a result of caching, where $\alpha_{C_{f}}$ is the cost of caching content $f$. The cost mainly depends on the file size $g_{f}$. The expected cost for retrieving content $f$ from SBS $k\in\{1,\cdots,K\}$ within a global aggregation period can be written as

where $\psi_{k,t}$ represents the pedestrian density at time slot $t$ at the site of SBS $k$. Besides, $\lambda_{f,t}=\psi_{k,t}\cdot p_{f}$ indicates the expected request density (i.e., the number of requests per time slot) of a specific file $f$ at time $t$. Finally, $d_{k,f}=\prod\nolimits_{l\neq k}^{K}(1-c_{l,f})(\beta_{M}+\beta_{M_{k}}+\beta_{S_{k}})$ corresponds to the worst case cost, i.e., when fetching file $f$ from the MBS backhaul. $\beta_{M}$ is a constant cost for retrieving $f$ via an MBS backhaul, $\beta_{M_{k}}$ denotes the cost of retrieving $f$ for SBS $k$ from MBS backhaul, and $\beta_{S_{k}}$ refers to the cost incurred by retrieving $f$ for MUs from the SBS $k$. Besides, $\lambda_{f,t}\cdot c_{k,f}\cdot\beta_{S_{k}}$ is the expected cost for retrieving $f$ from SBS $k$, if available. Minimizing the aggregated cost $J^{t}_{k,f}(\psi_{k,t},p_{f})$ in (1) over the $K$ SBSs, i.e., $\mathop{\text{minimize}}\nolimits_{\{\mathbf{C}\}}\quad\sum\nolimits_{k=1}^{K}J^{t}_{k,f}(\psi_{k,t},p_{f})$, yields the optimal routing strategy for each file. Such content routing strategy stipulates that retrieving file $f$ through the desired SBS $k^{*}=\operatorname*{argmin}\nolimits\quad\sum\nolimits_{k=1}^{K}J^{t}_{k,f}(\psi_{k,t},p_{f})$ leads to a least aggregated cost.

The expected cost ${J_{k,f}^{t}(\psi_{k,t},p_{f})}$ in (1) is valid for the costs for every file request, regardless of the file being cached or not; i.e., it can serve the general transmission cost function for small-cell networks. Besides, it is an upper bound for the transmission cost incurred for retrieving file $f$ from SBS $k$ in a global aggregation period. Note that, in our mobility-aware scenario, a multicase-based caching policy is complex to implement. Indeed, most of the papers in that direction model the requests by a Poisson point process (PPP) across SBSs [23]; however, such assumption is not valid in our case, as the mobility pattern, and, thus, the user-SBS association, is dynamic and unknown.

The optimal mobility-aware routing strategy and cache placement is equivalent to minimizing the network cost per global aggregation. Formally,

where Constraint (2b) means that the total size of cached files cannot exceed the cache capacity of SBS $k$.

Problem (2) is an integer programming problem that is NP-hard. Moreover, the objective function is not available since it involves unknown popularity $p_{f}$ and pedestrian density $\psi_{k,t}$. In particular, there exists $2^{M+K}$ possible caching strategy matrices $\{\mathbf{C}\}$, implying an exponential growth in complexity as a function of $M$ and $K$. Therefore, it is essential to develop an efficient approach to solve the problem (2) while maintaining a low delay.

After learning $\psi^{*}_{k,t}$ and $p_{f}$ using the FRPL method, each SBS $k\in\{1,\cdots,K\}$ knows also $\mathcal{L}^{*}_{k,t}$. Then the optimal cache placement problem is equivalent to minimizing the network cost function $\mathcal{D}(\{c_{k,f}\})$ given by

Thus the optimization problem follows as

Problem (15) is an NP-hard integer programming. Given cache placement policy $\{c_{k,f}\}$, the content retrieval policy is determined based on our content transmission protocol introduced in Section II-C. To solve the problem with low complexity, we develop Algorithm 2, which greedily places the files to a cache and provides an approximate solution.
Let $I_{k}$ be the total size of files that are already cached at SBS $k$ during each iteration of our algorithm. Besides, $\mathcal{L}_{k,f}$ denotes the set of pairs $\{k,f\}$, where SBS $k$ does not store file $f$ yet despite having the sufficient cache capacity. At iteration ${\Theta}$, the algorithm conducts the cache placement by picking the pair $\{k^{*},f^{*}\}\in\mathcal{L}^{\Theta}_{k,f}$ with the lowest $\mathcal{D}(\{c_{k,f}\})$, provided that such cost is lower than the one in the previous iteration. Note that if the algorithm starts with the pair $\{k,f^{*}\}$ that results in the lowest cost $\mathcal{D}(\{c_{k,f^{*}}\})$, then the relative network cost caused by SBS $k$ at each iteration remains fixed. Formally,

Then, if $I^{{\Theta}}_{k^{*}}<C^{S}_{k^{*}}$, the algorithm updates $I^{{\Theta+1}}_{k^{*}}=I^{{\Theta}}_{k^{*}}+c_{k^{*},f^{*}}\cdot g_{f^{*}}$ and $\mathcal{L}^{{\Theta+1}}_{k,f}=\mathcal{L}^{\Theta}_{k,f}\backslash\{k^{*},f^{*}\}$; Otherwise, when $I^{\Theta}_{k^{*}}=C^{S}_{k^{*}}$ implies that the cache of SBS $k^{*}$ is full, the algorithm excludes all pairs $\{k^{*},f\}$ from $\mathcal{L}^{\Theta}_{k,f}$, and stops the cache placement for SBS $k^{*}$. The algorithm terminates when all the caches are full. Algorithm 2 summarizes the described greedy cache placement.

Let $B_{(k)_{u},f}$ be a binary variable that indicates whether SBS $k$ caches a file $f$ requested by MU $u\in\mathcal{L}^{*}_{k,t}$. We observe that the approximation ratio of our proposed cache policy is proportional to the number of MUs that an SBS serves at each global aggregation [37] when neglecting the normalized cost for retrieving files from MBS.⁴⁴4Numerical analyses show that the normalized cost parameter for retrieving files from MBS backhaul has only a limited influence on the network cost minimization. To support this conclusion, we present the following results.

Based on the optimization criterion given by (16), the computational complexity of cache placement using Algorithm 2 at SBS $k$ is polynomial time $\mathcal{O}\left(n\cdot\left\|\mathcal{L}_{k,f}\right\|_{0}\right)$, with $n$ being the required number of iterations to solve problem (16). As $\mathcal{L}_{k,f}$ is the set of all possible (SBS, file) pairs that impose the lowest ${\mathcal{D}}(\{c_{k,f}\})$ to fill the cache of SBS $k$, the total computational complexity of the cache placement policy yields $\mathcal{O}\left(\sum\nolimits_{k=1,\cdots,K}n\cdot\left\|\mathcal{L}_{k,f}\right\|_{0}\right)$. Hence the proposed policy has a linear complexity in the number of (SBS, file) pair.

We use a real-world dataset, namely, MovieLens 1M [38], to evaluate our proposed learning and caching strategies. Similar to [19], we assume that the movie rating process in the datasets is a streaming request. The MovieLens 1M datasets consist of (i) the users’ demographic information given in the format of <user ID*, age (in 7 categories), gender (in 2 categories), occupation (in 21 categories), Zip-code>; (ii) the rating information given in the format of <user ID*, movie ID, rating (in 5 categories), timestamp>.
To predict the request density, in the experiments, we merge the data of users’ demographic- and rating information based on the label of the user ID*. Against this join-type dataset, we pick the attributes of <movie ID, user ID*, their gender, age, Zip-code, and occupation> as the context dimensions. Table III gathers the most important parameters of our experiments.

We evaluate the average caching efficiency (the average ratio of cache hits within one global aggregation period compared to the total requests) of our proposals in comparison with the following cache placement approaches:

• •

  Optimal with Full Information: This scheme has full information about the users’ demands; thus, it has the potential of providing the best caching performance;

• •

  $\boldsymbol{\epsilon}$-Greedy: The policy selects a set of $m$ files uniformly at random with probability $\epsilon\ll 1$, while with probability $1-\epsilon$, it selects the $m$ files with the highest estimated popularity so far;

• •

  Least-Recently-Used (LRU): It fetches the requested files from the potential contributor (i.e., MBS backhaul) and caches it when a cache miss event occurs. If an item exceeds the cache capacity of SBS, it removes the file in the cache that has been least recently used;

• •

  Random: This scheme selects a random set of files to cache in each time slot.

In Fig. 4, we compare the performance of different caching approaches using the same dataset, so that the file set remains constant. The figure shows that our proposed algorithm achieves a gain significantly higher than that of the random- and $\epsilon$-greedy approaches under different $\epsilon$. The gain grows as the cache size increases. The reason is that the proposed algorithm greedily places the cache to SBSs after learning the expected request densities of files by Algorithm 1.
Besides, our proposed approach exhibits superior performance compared to the LRU approach for large storage space. Also, by comparison between the proposed and optimal approaches, we deduce that the proposed algorithm provides a near-optimal solution while pursuing a minimum network cost.

Fig. 5 shows the cumulative request density of the cached files up to time slot $T$ with $C_{k}^{S}=200$ MB. The cumulative request density is the sum of request densities of desired files at each round. The figure shows that the proposed algorithm achieves larger cumulative request density than $\epsilon$-greedy and random caching methods. In particular, at time slot $T=2500$, the cumulative request density achieved by the proposed greedy algorithm is $1.65$, $1.87$, $1.93$, $3.76$, and $10.31$ times the cumulative request density achieved by LRU, $\epsilon$-greedy (for $\epsilon=0.01,0.1,0.8$), and random placement, respectively.

In Fig. 6, we evaluate the network cost of the proposed FRPL- and local caching methods. It can be seen from Fig. 6(a) that the cost of our cache placement solution is less than that of local caching. The figure also shows that, compared to the local caching, the FRPL approach requires fewer iterations to arrive at a given level of network cost. This is because the FRPL approach accurately learns the expected request density from the context of observed files’ rating and users’ features. Fig. 6(b) depicts the network cost of the proposed FRPL approach ($\alpha$ = 10) for distinct cache sizes. We assume that the caching entity (i.e., the SBS) updates its cache content every 4-hours. Fig. 6(b) then shows that expanding the cache from 5$\%$ to 32.5$\%$ reduces the network cost of the FRPL approach. The reason is that enlarging the cache size expands the solution space of problem (15).

Fig. 7(a) and Fig. 7(b) show the network cost of different placement methods as a function of the cache size ($\%$ of file library) and the transmission cost ratio $\beta_{M_{k}}/\beta_{S_{k}}$, respectively. Fig. 7(a) shows that the proposed algorithm reduces the network cost compared to $\epsilon$-greedy ($\epsilon=0.1,0.8$), and local caching approaches for cache sizes varying from 10$\%$ to 50$\%$. The result in Fig. 7(a) is consistent with that in Fig. 6(a). Besides, Fig. 7(b) shows that the transmission cost ratio $\beta_{M_{k}}/\beta_{S_{k}}$ dramatically influences the cost performance of different methods. In particular, when increasing $\beta_{M_{k}}/\beta_{S_{k}}$ from 1 to 5, the cost of different placement approaches falls abruptly. Indeed, the parameter of normalized cost of file retrieval from the SBSs affects the performance more than that from the MBS over a backhaul.

In Fig. 8(a)-8(c), we evaluate the normalized network cost versus the average caching efficiency as a function of the transmission cost ratio $\beta_{M_{k}}/\beta_{S_{k}}$ and the cost of caching content $f$ for different placement approaches. We utilize movie rating data collected from MovieLens 1M [38] associated with distinct cache content update intervals. To model the user demand process, we synthesize two datasets with cache content update intervals equal to 15 hours (Fig. 8(a)) and 20 hours (Fig. 8(b) and Fig. 8(c)). Fig. 8(a) shows that: (i) with the decreasing cost of caching content $f$, i.e., $\alpha_{C_{f}}$, the proposed placement approach reduces the normalized network cost; (ii) with the increasing transmission cost ratio $\beta_{M_{k}}/\beta_{S_{k}}$ and for a given $\alpha_{C_{f}}$, our approach improves the cost performance. Besides, Fig. 8(b) shows that when facing ultra-high request traffic, our approach reduces the normalized network cost. Finally, Fig. 8(c) reveals that the proposed placement approach reduces the network cost compared to the $\epsilon$-greedy ($\epsilon=0.1,0.8$) and local caching methods. The reason is that our proposal accurately predicts the expected request density of each file particularly for high-dimensional datasets.