A Non-Stationary Bandit-Learning Approach to Energy-Efficient Femto-Caching with Rateless-Coded Transmission

To cope with the ever-increasing demand for mobile services, future wireless networks deploy dense small cells to underlay the legacy macro cellular networks [2], where small base stations (SBS) connect to the core network via a backhaul link. This concept takes advantage of low-power short-range base stations that potentially offload the macrocell traffic [3], improve the cell edge performance, and increase the uplink capacity. Moreover, transmission over short-length links enhances power efficiency and mitigates security concerns. However, these advantages come at some cost, and the system designers face several challenges to realize the concept of dense small cell networks. On the one hand, a massive number of devices sharing limited wireless resources in combination with a dense deployment of SBSs results in an excessive cost of information acquisition and computations, rendering centralized control mechanisms infeasible. On the other hand, in a dense small cell network, not all SBSs can access a power grid. Consequently, the SBSs store or harvest the required energy for providing wireless services. Naturally, the SBSs must consume energy efficiently to reduce the cost and the requirement of frequent batteries recharge, also to remain environment-friendly.

Besides, the significant growth in the demand for media streaming in combination with limited backhaul capacity renders developing efficient file-delivery approaches imperative [4]. The mobile data traffic caused by on-demand multimedia transmission exhibits the asynchronous content reuse property [5]; that is, the users request a few popular files at different times, but at relatively small intervals. The concept of wireless caching takes advantage of this property: instead of frequently fetching the popular files from the core network, different network entities store and re-transmit the files upon demand. The three major strategies for wireless caching are as follows: (i) femto-caching, (ii) D2D-caching, and (iii) coded-caching (or, coded-multicast) [6]. In femto-caching, SBSs save popular files to reduce the dependency on the high-speed backhaul. In D2D-caching, small devices store different files locally and provide each other with the files on-demand. Thus, in D2D-caching, the nearby devices share the burdens. The third method combines caching of files on the users’ devices with the common multicast transmission of network-coded data. Despite the great potential to gain resource efficiency while improving the users’ satisfaction levels, there are various challenges associated with caching. A challenging issue is the cache placement problem, which refers to selecting a subset of available files to store.

We study the downlink operation in an underlay cache-enabled small cell network with a set $\mathcal{M}$ of $M$ SBSs. The service area consists of multiple grids with a radius of $d$. The deployment of SBSs is deterministic such that there exists only one SBS in every area with a radius of $d$. All SBSs are connected to a macro base station (MBS), which has access to the core network. Each SBS $m\in\mathcal{M}$ selects its transmission power from a finite set of power-levels $\mathcal{P}$ including $P$ elements belonging to $\left[p_{\min},p_{\max}\right]$. As it is conventional in underlay networks, SBSs use the MBS’s licensed channels if they are idle; thus, provided that the sensing is perfect, there is no interference incurred by- or to the MBS. The SBSs, however, might cause inter-cell interference to each other as they do not coordinate before transmissions.

There exists a random set $\mathcal{N}$ of $N$ users in the network. Users are quasi-static and their geographical arrangement follows a spatial homogeneous Poisson point process (HPPP) with density $\lambda$, which is unknown to the SBSs. We consider a frequency non-selective fading channel model. For a link connecting user $n\in\mathcal{N}$ and SBS $m\in\mathcal{M}$, we denote the random channel coefficient by $H_{nm}$. The channel coefficient follows a Rayleigh distribution with unknown parameter $\frac{1}{\sqrt{2\beta_{nm}}}$. Therefore the channel gain $\left|H_{nm}\right|^{2}$ is exponentially-distributed with unknown parameter $\beta_{nm}$. The MBS, the SBSs, and the users do not have any prior knowledge, even statistical, about the channel quality.¹¹1Rayleigh fading is the most reasonable and widely-applied statistical model for propagation in an urban environment. Therefore, we use the Rayleigh distribution to develop the mathematical formulation and to enable the analysis. Note that it does not contradict our claim of the absence of prior statistical information at SBSs since we do not allow knowledge about the statistical characteristics of the distribution such as the expected value. It is worth noting that the analysis can be performed for any other fading model by following the same lines. Besides, the proposed joint cache placement and resource allocation method is applicable even if there is no mathematical model and analysis. Throughout the paper, we regard interference as noise. For the simplicity of notation and calculus, we neglect the large-scale fading (path loss), assuming that there is an inner power-control loop that compensates the path loss. This simplification does not affect our analysis, and the entire analysis can be performed in the same way also including the path loss.

Let $d_{nm}$ denote the distance between SBS $m\in\mathcal{M}$ and user $n\in\mathcal{N}$. Then user $n$ is associated with SBS $m$ if $d_{nm}=\textup{minimum}\{d_{n1},...,d_{nM}\}$. In words, every user is assigned to the nearest SBS. The distance-based user association is a widely applied association method (see [34] and the references therein) since it is simple and practical. The set of users assigned to every SBS $m\in\mathcal{M}$ is denoted by $\mathcal{X}_{m}$. Recall that (i) users are distributed according to an HPPP with density $\lambda$, and (ii) there is only one SBS in the area of radius $d$. Consequently, the number of users assigned to SBS $m\in\mathcal{M}$ follows the distribution

It is worth mentioning that in ultra-dense small cell networks, a user might be located inside the intersection of the coverage areas of multiple SBSs. Hence, if the SBSs transmit the same file with specific coding constraints, the user benefits from multiple useful signals for rapid file reconstruction. However, we consider a scenario where each user is associated with only one SBS and receives recoverable signals only from that SBS. Therefore, each SBS decides on the files to cache independent of others. Also, note that the channel impairments such as interference can sometimes yield a packet delivery failure for some of the users assigned to an SBS.

Let $\mathcal{F}$ be the finite set of $F$ files to cache. Every file $f\in\mathcal{F}$ consists of $L_{f}$ data blocks of the same size.²²2Depending on the applied standard for wireless transmission, the size of each data block might change from a few Kilobytes (e.g., 1.5 Kilobytes for IPv4) and dozens of Kilobytes (e.g., 64 Kilobytes for IPv6). The exact size of the data block does not play a role in our proposed caching and transmission scheme since, if required, a data block of any size can be further segmented to blocks with a different size (often smaller) that is appropriate for rateless coding and transmission. Naturally, the receiver then re-integrates the blocks to each other as necessary to rebuild the original one. All SBSs apply rateless codes to transmit any file $f\in\mathcal{F}$, as described below.

Every SBS $m\in\mathcal{M}$ first encodes the message at the packet-level using Luby-Transform (LT) rateless code [35]. LT codes are the first practical realization of fountain codes that allow successful recovery of any message with very small overhead. In LT codes, every coded packet is the exclusive-or of $a$ neighbors. The number $a$ is called the degree. It is selected according to some specific probability distribution. After being appended with a cyclic redundancy check (CRC) sequence, each LT-coded packet is encoded by a physical-layer channel code of rate $R$ bits/channel-use and is transmitted over the channel in a time slot. The receiver attempts to decode the packets at the physical layer first. If the CRC is incorrect, the corresponding packet is discarded. We assume that CRC bits are sufficient so that every error can be detected.³³3The overhead of CRC depends on the type being used, or, in other words, the number of CRC checksum bits. The checksum usually consists of 8, 16, or 32 bits in length and is appended to the message. In general, taking both overhead and error detection performance into account, CRC is considered superior to many other error detection codes such as parity check. The accumulation of correctly received packets is used by the decoder to recover the source file. Assume that the receiver desires to successfully reconstruct the message with probability $\delta$. Then it requires to accumulate (at least) any $L^{\prime}_{f}=L_{f}+\nu_{f}(L_{f},\delta)$ LT-coded packets, provided that the number $a$ (i.e., the degree) is selected appropriately [35]. Here, $\nu_{f}$ is the discrete random decoding overhead, rendering $L^{\prime}_{f}$ a random variable as well; nonetheless, for point to point transmission, it can be deterministic. A common value is $\nu_{f}=0.05L_{f}$ so that $L^{\prime}_{f}=1.05L_{f}$ [36]. The receiver then recovers the original message using, for instance, the belief propagation algorithm. It then informs the SBS via an acknowledgment (Ack) packet.⁴⁴4To decode the rateless-coded transmission, a receiver requires to possess channel state information. In our setting, each user receives signal only from one SBS, whereas the SBS transmits to multiple users; as such, it is plausible to assume that the receiver can obtain the CSI whereas the SBS incurs high cost for CSI acquisition. Also, some other articles such as [37] suggest utilizing rateless codes to overcome the channel uncertainty at the transmitter. Moreover, some researchers address the problem of decoding rateless-coded data under imperfect CSI at the receiver. For example, in [38], the authors discuss rateless codes for quasi-static fading channels in conjunction with imperfect CSI at the receiver. If the time and energy are unconstrained, rateless coding results in zero file-reconstruction failure also in fading channels. However, in a realistic scenario, either the energy is limited or the application is delay-sensitive. For example, in [33], the authors apply rateless codes to wireless streaming with a sequence of playback deadlines. We also take such restrictions into account by assuming the following: In every broadcast round, SBS $m\in\mathcal{M}$ generates at most $D_{m,f}\geq L^{\prime}_{f}$ rateless-coded packets to broadcast any file $f\in\mathcal{F}$. Every SBS $m$ selects $D_{m,f}$ as a deterministic value. In essence, $D_{m,f}$ is a deadline for the users interested in file $f\in\mathcal{F}$ to accumulate $L^{\prime}_{f}$ rateless-coded packets while SBS $m$ is broadcasting file $f$. The users with a higher channel quality are more likely to succeed in accumulating $L^{\prime}_{f}$ rateless-coded packets out of $D_{m,f}$ transmitted ones. Naturally, $D_{m,f}$ shall be larger for larger files that consist of more packets. By selecting $D_{m,f}$, SBS $m$ balances the trade-off between the energy consumption for packet transmission on the one hand and the number of successful file reconstructions at the users’ side on the other hand. Thus, the SBS stops transmitting as soon as one of the following events occurs:

• •

  All assigned users that have requested file $f$ recover it.

• •

  $D_{m,f}$ data packets are transmitted.

Let user $n\in\mathcal{N}$ be assigned to some SBS $m\in\mathcal{M}$, and the SBS transmits at some power level $p_{m}\in\mathcal{P}$. Then in the signal-to-interference-plus-noise ratio (SINR) yields

where $p_{0}$ is the power of additive white Gaussian noise. Note that $R_{nm}$ attains a lower-bound in the worst-case scenario, where every SBS $j\in\mathcal{M},j\neq m$, transmits with the maximum power, i.e., $p_{j}=p_{\max}$. The lower-bound, $R_{nm,\min}$, is useful when SBS $m$ is not aware of the transmit power of other SBSs. The pdf of $R_{nm}(p_{m})$, denoted by $f_{R}(r)$, is given by Proposition 1.

For a sufficiently long block length, the outage probability is a good approximation for the packet error probability. Let $u_{n,\min}$ denote the minimum transmission rate required by user $n\in\mathcal{N}$. The outage probability yields

where $F_{R_{nm}}(r)=\int_{0}^{r}f_{R}(r)dr$. In the general case, the solution of this integral at every desired point can be calculated numerically. For special cases, one can also calculate the closed-form solution. For example, for the interference-limited region where the noise power is negligible compared to the interference power, by using (3), we can write (6) as

where $r_{n}=e^{u_{n,\min}}-1$.⁵⁵5Depending on some factors such as the density of small base stations, small cell networks operate in different regions [39]. Naturally, the user experiences the maximum outage probability at $R_{nm,\min}$. A receiver can reconstruct a file $f\in\mathcal{F}$ with probability $\delta$ if it successfully receives at least $L^{\prime}_{f}$ rateless-coded packets out of $D_{m,f}$ packets transmitted by SBS $m$. Hence, for a user $n\in\mathcal{N}$, the probability of successful decoding (file reconstruction) yields

The quality of the wireless channel is random. Therefore, for each user, the required time until receiving enough packets for file reconstruction is a random variable. Moreover, when broadcasting a file $f\in\mathcal{F}$, each SBS $m\in\mathcal{M}$ transmits only a limited number of rateless-coded packets. Such restriction, in combination with random channel quality, renders the number of successful file reconstructions at the users’ side as random. Consequently, the total power required by an SBS to transmit a file is also a random variable. In the following sections, we analyze these random variables.

Every SBS $m\in\mathcal{M}$ has a finite cache size, denoted by $C_{m}$. Moreover, every file $f\in\mathcal{F}$ has a finite size $S_{f}=L_{f}B$. Files are labeled in a way that $S_{1}\leq S_{2}\leq...\leq S_{F}$. To gain access to a file that is not already stored in its cache, every SBS has to fetch it from the MBS. To avoid the energy-cost of fetching and to reduce the backhaul traffic, also to improve the users’ satisfaction level through reducing the delay, the SBSs try to avoid repetitive fetching, by storing the most popular files in their cache. The vast majority of previous works models the file popularity by a Zipf-like distribution with a time-invariant skewness parameter. However, such a model stands in contrast to the regular experience where the popularity of most data files changes over time. For example, as a familiar pattern, the number of requests for a video clip tends to increase initially, remain static for a while and then decrease. Therefore, in our work, we model the file popularity as a piece-wise stationary random variable. Details follow.

For an SBS $m\in\mathcal{M}$ that serves $X_{m}$ users, the number of requests for a file $f\in\mathcal{F}$ follows a Poisson distribution with parameter $\mu_{f,t}X_{m}>0$; that is, the total number of requests for each file is time-variant and depends on the number of users in the small cell. Every user can request multiple files. The SBSs have no prior information about the popularity of each file.⁶⁶6Traditionally, Poisson distribution describes the random arrival process, e.g., user arrival or service demand in a telecommunication network. Therefore, here we use it to model the request arrival for each file, although we consider the general setting in which the parameter of this distribution, i.e., the intensity is unknown. Moreover, it should be emphasized that based on the intensity, Poisson distribution produces values in $\mathcal{N}_{0}$. Let $Q_{f,m,t}$ be the total number of requests for file $f\in\mathcal{F}$ submitted to SBS $m\in\mathcal{M}$ at time instant $t$. Then

where the equality follows by (1) and the definition of Poisson distribution.

The time-variations in the files’ popularity correspond to the notion of concept drift in machine learning [41], which describes the changes in the statistical characteristics or distribution of the problem instances over time. For example, [42] considers this notion. In essence, big data applications are often characterized by concept drift, in which trending topics change over time. Moreover, [43] analyzes and illustrates some examples of concept drift in video streaming. Through data analysis, the authors show that the popularity of a video decreases by moving away from the posting date, or in other words, as the content’s age increases.

If $\psi$ and $\psi^{\prime}$ are intensities before and after the change, we have $\left|\psi^{\prime}-\psi\right|>C$, with $C$ being a sufficiently large constant. Note that the changes in the popularity can be continuous; however, by assuming a step-wise model, we neglect small changes in popularity and tune our algorithm to detect abrupt changes rather than small ones. In such a setting, the change detection performs better, since the tradeoff between a false alarm and misdetection can be balanced easier. Moreover, the complexity of caching reduces as well. More precisely, if even small changes are taken into account, the cache placement problem (knapsack problem) has to be solved unnecessarily very often, which results in excessive complexity. Based on this analytical model, in the following, we define the file type.

We use $\mathcal{A}_{m,\theta}\subseteq\mathcal{F}$ to denote the set of files that are considered to be alive by SBS $m\in\mathcal{M}$, at the beginning of a broadcast round $\theta$. We assume that there always exists at least one alive file, i.e., $A_{m,\theta}\geq 1$ for all $\theta=1,2,...$. Naturally, as we later explain in Section VI, every SBS selects the set of files for storage from the set of alive files, meaning that $\mathcal{L}_{m,\theta}\subseteq\mathcal{A}_{m,\theta}$. Thus, $\alpha_{m}$ is selected by SBS $m\in\mathcal{M}$ based on its cache size $C_{m}$. Intuitively, an SBS with larger storage capacity would have smaller $\alpha_{m}$, implying that it is able to store also some files with low popularity.

Let $f_{m,\theta}\in\mathcal{A}_{\theta}$ and $p_{m,\theta}\in\mathcal{P}$ denote the broadcast file and transmit power of SBS $m$ at broadcast round $\theta$. Then, $E_{m,\theta}\left(f_{m,\theta},p_{m,\theta}\right):=E_{m,f_{m,\theta},p_{m,\theta}}$ is the total energy spent during the broadcast round $\theta$. Moreover, let $K_{m,\theta}\left(f_{m,\theta},p_{m,\theta}\right):=K_{m,f_{m,\theta},p_{m,\theta}}$ be the number of successful file deliveries. We define the utility of SBS $m$ at round $\theta$ as

i.e., in terms of the number of successful reconstructions per energy consumption. Ideally, every SBS performs the cache placement and power allocation jointly. That is, it selects a file to cache, and at the same time it assigns some power to broadcast that file (in future based on the users’ request). Then the optimization problem of every SBS $m\in\mathcal{M}$ can be formulated as follows:

subject to the following constraint

for all $\theta=1,2,...$. Solving the optimization problem in (21) is however not feasible since by the following reasons the objective function is not available: (i) The files’ popularity, the network’s structure (including number of users), and the CSI are not known a priori; (ii) Each SBS is only aware of its own transmit power level as well as the file being broadcast, and not those of other SBSs. In such a scenario, a natural solution would be to incorporate online learning methods that maximize the expected utility, that is,

subject to (22), where the expectation is taken with respect to random utility, as well as any other possible randomness in the decision-making strategy.

In general, efficient learning of the optimal decision involves finding a balance between gathering information about every possible strategy (exploration) on one hand and accumulating utility (exploitation) on the other hand. In other words, it is desired to learn as fast and efficient as possible, to minimize the cost of information shortage. In this sense, the problem formulated in (23) is inefficient to solve due to the following reasons: (i) Each (file, power level) pair, i.e., $(f,p)$, $f\in\mathcal{F},p\in\mathcal{P}$ is defined as an action (strategy), yielding $FP$ actions in total; thus, from the computational point of view, such formulation imposes excessive complexity due to a large number of actions; (ii) To estimate the potential gain of each action, every file $f\in\mathcal{F}$ has to be fetched from the core network and transmitted at various power levels. It is evident that such exploration is very costly in terms of power, not only since fetching is power-consuming, but also since a substantial amount of limited power is wasted during exploration. Moreover, frequent fetching by densely deployed SBSs yields large backhaul traffic; (iii) The dynamic file popularity is not taken into account.

Based on the discussion above and in agreement with many previous works such as [27] and [13], we consider the caching system to work in two consecutive phases: (i) cache placement phase, and (ii) delivery phase. Accordingly, we decompose the cache placement and power control problem into two sub-problems listed below, which are solved repeatedly and in parallel to converge to the optimal solution:

• •

  Cache Placement: During every broadcast round $\theta=1,2,...$, every SBS $m\in\mathcal{M}$ observes the requests for every file $f\in\mathcal{F}$. Then, at the end of each broadcast round, the SBS updates its cache, if necessary. Later in Section VI, we explain that the necessity is defied based on the variations in the files’ popularity.

• •

  Joint Broadcast File Selection and Power Allocation: At every broadcast round $\theta=1,2,...$, SBS $m\in\mathcal{M}$ selects a file $f_{m,\theta}\in\mathcal{L}_{m,\theta}$ to be transmitted, together with a power $p_{m,\theta}\in\mathcal{P}$ for broadcast.

A summary of cache placement and delivery protocol is provided in Algorithm 1. The approach is also illustrated in Fig. 1. The two problems are described in detail and are solved in Section VI and Section VII, respectively. In Section VII-A, we discuss the effect of decoupling the cache placement and power control problems on the performance.⁷⁷7Note that the frequency of updating the cache (if necessary at all) is not necessarily similar to that of broadcasting. In other words, an SBS can decide to update the cache in some specific intervals, for example, in every $K$ rounds of broadcasting. Our proposed algorithm is also applicable in this case.

As described in Section V, we perform the cache placement based on file popularity, or in other words, the requests. By (23), at every broadcast round, a file is selected from the cache; this implies that the dynamic cache placement is performed, if necessary, at broadcast (delivery) rounds and not at every single transmission round. Let $\mu_{f,\theta}$ be the popularity of file $f\in\mathcal{F}$ at the beginning of the broadcast round $\theta$. For an SBS $m\in\mathcal{M}$, the cache placement problem is stated as follows: Given the set of files $\mathcal{F}$, where each file $f\in\mathcal{F}$ has a size $S_{f}$ and a value $\mu_{f,\theta}$, desired is to decide whether to include the file in cache ($\mathcal{L}_{m,\theta}$) or not, so that the total size of selected files does not exceed the cache capacity $C_{m}$, while the total value is maximized. Note that at every cache updating round, the saved files are selected from the set of alive files. Such a strategy reduces the complexity without affecting the performance adversely. Formally, for $\theta=1,2,...$, the optimization problem yields

Considering each file as an item whose value is defined in terms of popularity, the cache placement problem is a 0-1 knapsack problem, which is a combinatorial optimization problem. Note that in formulating the knapsack problem, the value of every item (file) $f\in\mathcal{F}$ can be also defined in terms of the number of requests; Nonetheless, according to our model, the number of requests is stochastic, which renders the knapsack problem stochastic; Hence, to simplify the problem, we use the intensity of requests for each file $f$, $\mu_{f,\theta}$, as the item’s value, keeping in mind that $\mu_{f,\theta}$ is deterministic, despite changing over time.

Being under intensive investigation, a variety of efficient algorithmic solutions are developed for the knapsack problem [44]. The cache placement problem stated by (24) is however more challenging than the conventional knapsack problem. In particular, according to our system model (see Section IV), (i) the SBSs do not have any prior knowledge on files popularity indicator $\mu_{f,\theta}$, and (ii) files’ popularity is time-varying so that (24) has to be solved sequentially. Against such difficulties, we notice that at every time $t=1,2,...$, every SBS $m\in\mathcal{M}$ receives the requests for every file $f\in\mathcal{F}$. This side-information that every SBS obtains at almost no cost can be used to estimate the file popularity; i.e., to predict how many users would attempt to recover the file if it is broadcast. Let $\hat{\mu}_{f,\theta-1}$ be the estimated value of $\mu_{f,\theta-1}$ at the end of broadcast round $\theta-1$.⁸⁸8It is worth noting that in some previous works, for example, in [27] and [24], the authors assume the following: Every SBS observes the cache hits, i.e., the number of requests for the files in the cache, whereas the number of cache drops, i.e., the number of requests for the files that do not belong to the cache, is not observable. However, such an assumption is unnecessary in many cases, where the users submit the requests for files to the corresponding SBS, while not knowing the cache status of the SBS. Even in the setting where the requests are submitted to some entity other than the SBS, such information can be transferred to the SBS with negligible cost. To update the cache for the broadcast round $\theta$, the SBS uses the historical data. Hence the optimization problem (24) is restated as

For cache placement, we use the SBS’s observations in combination with some statistical tests, as described below.