Two-Tier Matching Game Design for Wireless Caching in Pico-Cell Networks

Abstract

Wireless caching brings network content close to mobile users (MU), and has been identified as an effective solution for reducing MUs’ transmission delay. In this paper, we concentrate on how to efficiently allocate network files to the storage of pico-cells and associate MUs with the pico-cells. To deal with the series of resource allocation problems, we first separate these problems as two distinct many-to-one matching games. Then, we tackle these problems by proposing different concepts to generate the preference lists respectively. The deferred-acceptance algorithm is designed in this paper to achieve stable matchings in these two separated games. It is shown in numerical results that our proposed design demonstrates a better performance compared to state-of-the-art benchmarks.

1 Introduction

Along with the developments of mobile communication technologies, mobile users (MUs) show growing interests in using various multimedia services [1]. To deal with the explosive growth of demands in high speed data transmissions by MUs, an low-cost and low-power pico-cell access architecture is proposed which can coexist with any wireless technology and can be deployed in any area underlaid on Macro-cell network [2]. But when pico-cell network density increases, backhaul capacity limitations would be a big problem [3].

Content caching is one of the efficient solutions to effectively handling this problem. With observations that a large amount of data traffic is caused by a small portion of popular network contents, i.e., movies, as well as the price of storage medium is relatively cheaper compared to the price of backhaul, caching in network facilities, such as small-cell, femto-cell, pico-cell and D2D nodes, to release backhaul pressure becomes a potential solution in these years [4,5,6].

Specially in [4], a fetmo-cell caching system is proposed for assigning files to the femto-cells, in order to minimize the downloading time. Moreover, the authors of [5] proposed a caching system for D2D based cellular network relaying on the MUs’ caching of popular files, in order to increase the throughput of networks. In addition, the authors of [6] have proposed a distributed caching scheme using Stackelberg game, in order to deal with resource allocation problems in a small cell network. Although many problems have been solved as above, how to effectively allocate resource in pico-cell networks still remains a great challenge to face.

In this paper, we leverage matching game theory to handle resource allocation problems in cache enabled system. As in [7], authors introduce fundamentals and conventional classification of matching theory for future wireless networks, where matching games are split into three kinds, i.e., one-to-one matching games, many-to-one matching games and many-to-many matching games. In [8], authors utilize many-to-one matching games in wireless small cell networks with a combination of context-aware of information about trajectory profile and quality of service requirements of users, in order to maximum satisfaction ratio and reduce downloading delay. Many-to-many matching games has been used in [9] to reduce backhaul loads and the experienced delay in small cell networks. From discussion above, we are motivated to use matching game theory in pico-cell networks to explore the optimal allocation with caching.

In this paper, we concentrate on proposing a two-tier matching game in wireless caching systems to handle the resource allocation problem. We firstly match network contents with pico-cells and then match the pico-cells with mobile users. The key contributions can be summarized as follows.

• 1. We model a pico-cell based caching system with the objective to minimize the system transmission delay.

• 2. We decouple the resource allocation problems into two many-to-one matching games, and address them by using the deferred-acceptance algorithm. We then generate preference lists in the two matching games to obtain a stable matching.

• 3. We demonstrate that the proposed algorithm has near-optimal outcomes with numerical results.

The rest of this paper is organized as follows. We describe the system model and formulate system objective in Sect. 2. We then decouple the optimization problems and propose matching games to solve the optimization problems in Sect. 3. Our numerical results are illustrated in Sect. 4, while our conclusions are draw in Sect. 5.

2 System Model and Problem Formulation

Let us consider a pico-cell based caching network composed of M MUs which have priorities to connect to pico-cells. As shown in Fig. 1, there exists a Macro-cell serving MUs in its coverage assisted by N pico-cells. Also, we define the set of M MUs by $\varvec{\mathcal M}=\{\mathcal M_1,\mathcal M_2,\cdots ,\mathcal M_M\}$ and the set of pico-cell by $\varvec{\mathcal N}=\{\mathcal N_1,\mathcal N_2,\cdots ,\mathcal N_N\}$ which are both randomly located in system. We assume that each pico-cell has the same storage size that could cache only one file.

Fig. 1.

Pico-cells based caching system model

There are two resource allocation problems in this network. In the first stage, files are allocated to pico-cells and then MUs are associated to pico-cells in second stage. In what follows, we will introduce some key concepts to facilitate the problem formulation.

2.1 File Popularity

Firstly, we model the popularity of files. Let us denote the file set by $\varvec{\mathcal V}=\{\mathcal V_1,\mathcal V_2,\cdots ,\mathcal V_V\}$ consisting of V popular files which belong to content providers (CP). Intuitively, the majority of MUs request popular files more frequently than the others. Thus, we assume that the popularity profile of files characterized by the Zipf-like distribution as the requests of any files are inversely proportional to file’s rank in the request table [6]. Then, the popularity distribution $q_{v}$ of $\mathcal V_v$ is characterized as

$$\begin{aligned} q_v=\frac{1/v^\beta }{\sum _{j=1}^{V}1/j^\beta },\quad \forall v, \end{aligned}$$

(1)

where the exponent $\beta$ is a positive skewness parameter and v means v-th file. Also, the file with a small index v corresponds to a high popularity.

2.2 Transmission Rate of MUs

Secondly, we define the transmission rate of each pico-cells to MUs as

$$\begin{aligned} R_{mn}=W\log _2\Bigg (1+ \frac{P_{n}d_{mn}^{-\alpha }h_{mn}^{2}}{\sum _{n'\in \varvec{\mathcal N}\setminus n }P_{n'}d_{mn'}^{-\alpha }h_{mn'}^{2}+\sigma ^{2}}\Bigg ), \end{aligned}$$

(2)

where W means the transmission bandwidth of downlink channels and $P_{n}$ is the transmission power at pico-cell $\mathcal N_n$. $d_{mn}$ represents distance between pico-cell $\mathcal N_n$ and MU $\mathcal M_m$ and $\alpha$ is the path-loss exponent. The random channel between $\mathcal N_n$ and $\mathcal M_m$ is Rayleigh fading, whose coefficient $h_{mn}$ has the average power of one. $\sigma ^{2}$ is the variance of the Gaussian noise.

For the sake of simplicity, we assume that the Macro-cell will support a fixed download rate, denoted by $R_{ma}$, for the MUs in the channels which are orthogonal to those spanning from the pico-cells to MUs.

2.3 Caching Related Issue

Next, we introduce the pico-cell caching system with details. In the first stage, each pico-cell cache one file of $\varvec{\mathcal V}$. The file placement commence during off-peak time on backhaul links. It is clear that MUs show different preferences towards different files. Thus, we could define the preference from MU $\mathcal {M}_{m}$ to file $\mathcal {V}_{v}$ as

$$\begin{aligned} p_{mv}=\alpha _{mv}q_{v}, \end{aligned}$$

(3)

where $\alpha _{mv}$ is a factor that influence MUs’ preferences to file $\mathcal V_v$ and $q_{v}$ is the popularity of the file $\mathcal V_v$. Then, the pico-cells will download a file relying on collecting the serving MUs’ preferences. We define the preference $p_{nv}$ of pico-cell $\mathcal N_n$ to file $\mathcal V_v$ as

$$\begin{aligned} p_{nv}=\frac{1}{\mathcal C_{n}}\sum _{k\in \mathcal {C}_{n}}p_{kv}, \end{aligned}$$

(4)

where k means the k-th serving MU of the pico-cell and $\mathcal C_n$ is the serving MUs set of $\mathcal N_n$. Pico-cells will cache the most preference file of its serving MUs according to (4) during off-peak time.

In the second stage, MUs start to request files. In general, an MU can be covered by multiple pico-cells. When an MU $\mathcal M_m$ request file $\mathcal {V}_{v}$, it tries to connect to the nearest pico-cell which cached file $\mathcal {V}_{v}$. Otherwise, the MU $\mathcal M_m$ will download the requesting file from Macro-cell directly. Thus, the transmission delay $\tau _{ml}^{v}$ of MUs can be represented as follows.

$$\begin{aligned} \tau _{ml}^{v}= \left\{ \begin{array}{lcl} \tau _{ma}^{v}=\frac{S}{R_{ma}} &{}\text {if}&{}\text {MU connects to Macro-cell}, \\ \\ \tau _{mn}^{v}=\frac{S}{R_{mn}} &{}\text {if}&{}\text {MU connects to pico-cell}, \end{array} \right. \end{aligned}$$

(5)

where S is the file size.

2.4 Problem Formulation

In this subsection, we formulate the file allocation problem to minimize the transmission delay of MUs. The problem can be formulated as

$$\begin{aligned} \mathop {\min }\limits _{X,Y}&\sum _{n \in \mathcal {N}}\sum _{m \in \mathcal {M}}\sum _{v \in \mathcal {V}}x_{nv}y_{nm}\tau _{ml}^{v},\nonumber \\ \text {s.t.}&(a)\sum _{v\in \mathcal {V}}x_{nv} \le 1\nonumber ,\\&(b)\sum _{n\in \mathcal {N}}y_{nm} \le 1 \nonumber ,\\&(c)\sum _{n\in \mathcal {N}}x_{nv} \le Q_{1}\nonumber ,\\&(d)\sum _{m\in \mathcal {M}}y_{nm} \le Q_{2}\nonumber ,\\&(e)x_{nv},y_{nm}\in \{0,1\}, \end{aligned}$$

(6)

where $x_{nv}$ is the element of matrix X and $x_{nv}=1$ represents the pico-cell $\mathcal N_n$ caches the file $\mathcal {V}_{v}$, otherwise $x_{nv}=0$. $y_{nm}$ is the element of matrix Y, and $y_{nm}=1$ denotes that the pico-cell $\mathcal N_n$ is serving MU $\mathcal M_m$, if not $y_{nm}=0$. Condition (a) guarantees that each pico-cell could only cache one file, condition (b) states a user will be served by one pico-cell, condition (c) concerning file variety is to make sure that file $\mathcal {V}_{v}$ could only be cached $Q_{1}$ duplication in this network, condition (d) assures that each pico-cell can serve $Q_{2}$ MUs at most, and condition (e) states that the values of $x_{nv}$ and $y_{nm}$ can be neither 0 or 1.

3 Proposed Matching Algorithm

3.1 Decoupling the Optimization Problem

The optimization in (6) is a generalized knapsack problem which is proved to be an NP-hard combinatorial problem [10]. It is hard to find a global optimal solution for these association problems. Hence, to solve the optimization problem in (6), we resort to a suboptimal approach and split the optimization problem into two independent sub-problems: (i) optimal file selection problem, (ii) optimal pico-cell selection problem.

Optimal File Selection Problem

$$\begin{aligned} \mathop {\min }\limits _{X}&\sum _{n \in \mathcal {N}}\sum _{v \in \mathcal {V}}x_{nv}\tau _{ml}^{v}, \nonumber \\ \text {s.t.}&(a)\sum _{v\in \mathcal {V}}x_{nv} \le 1, \nonumber \\&(b)\sum _{n\in \mathcal {N}}x_{nv} \le Q_{1}, \nonumber \\&(c)x_{nv}\in \{0,1\}. \end{aligned}$$

(7)

Optimal Pico-Cell Selection Problem

$$\begin{aligned} \mathop {\min }\limits _{Y}&\sum _{n \in \mathcal {N}}\sum _{m \in \mathcal {M}}y_{nm}\tau _{ml}^{v},\nonumber \\ \text {s.t.}&(a)\sum _{n\in \mathcal {N}}y_{nm} \le 1, \nonumber \\&(b)\sum _{m\in \mathcal {M}}y_{nm} \le Q_{2},\nonumber \\&(c)y_{nm}\in \{0,1\}, \end{aligned}$$

(8)

These two suboptimal problems are still NP-hard combinatorial problems [10]. Since they both contain one binary variable, they can be modeled as two distinct many-to-one matching problems respectively [11].

3.2 Matching Related Definition

Matching has been introduced in [12] as a effective way to solve the allocate resource problem. These resources will be divided into two finite and disjoint sets of players. Different sets of players have different preferences over the opposite sets. To construct the preference lists in our model, we use the symbol $\succ$ to represent that the players prefer one player to another player in the opposite set. For example, when a pico-cell $\mathcal N_{n}$ shows $\mathcal V_{1}\succ \mathcal V_{2}$ in its preference lists, it means that $\mathcal N_{n}$ prefers file $\mathcal V_{1}$ than file $\mathcal V_{2}$. In this paper, we use $\mu _{1}$ to represent the first many-to-one matching of sub-problem 1.

For $\mathcal V_{v} \in \varvec{\mathcal V}$ and $\mathcal N_{n} \in \varvec{\mathcal N}$, a matching $\mu _1$ is $\mathcal V\bigcup \mathcal N\rightarrow 2^{\mathcal V\bigcup \mathcal N}$, which satisfies

• 1. $\mu _1(\mathcal N_{n})\in \varvec{\mathcal V}$ and $\vert \mu _1(\mathcal N_{n})\vert \le 1$,

• 2. $\mu _1(\mathcal V_{v})\in \varvec{\mathcal N}$ and $\vert \mu _1(\mathcal V_{v})\vert \le Q_{1}$,

• 3. $\mu _1(\mathcal V_{v})=\mathcal N_{n} \Longleftrightarrow \mu _1(\mathcal N_{n})=\mathcal V_{v}$.

The second many-to-one matching $\mu _{2}$ of sub-problem 2 has the following properties.

For $\mathcal M_{m} \in \varvec{\mathcal M}$ and $\mathcal N_{n} \in \varvec{\mathcal N}$, a matching $\mu _2$ is $\mathcal M\bigcup \mathcal N\rightarrow 2^{\mathcal M\bigcup \mathcal N}$, which satisfies

• 1. $\mu _2(\mathcal M_{m})\in \varvec{\mathcal N}$ and $\vert \mu _2(\mathcal M_{m})\vert \le 1$,

• 2. $\mu _2(\mathcal N_{n})\in \varvec{\mathcal M}$ and $\vert \mu _2(\mathcal N_{n})\vert \le Q_{2}$,

• 3. $\mu _2(\mathcal M_{m})=\mathcal N_{n} \Longleftrightarrow \mu _2(\mathcal N_{n})=\mathcal M_{m}$.

3.3 File Selection Algorithm

Next, Deferred Acceptance (DA) algorithm [11] is proposed to solve these two many-to-one matching games. We first focus on modeling the preference lists in the first matching.

Definition 1

For MUs $\mathcal {C} \subseteq \varvec{\mathcal {M}}$, the corresponding pico-cell’s preference over file $\mathcal V_v \in \varvec{\mathcal {V}}$ is

$$\begin{aligned} \mathbf {\Gamma }^{v}=p_{nv}, \end{aligned}$$

(9)

where $\mathbf {\Gamma }^{v} \in \mathbb {C}^{N*V}$ is pico-cells’ preference matrix over files.

Also, the files of CPs have certain preference towards different pico-cells considering their transmission delay. A pico-cell can serve $\mathcal {C}$ MUs so that we take the average transmission delay of $\mathcal {C}_{n}$ serving MUs as CP’s preference over this pico-cell. We define it as follows.

Definition 2

For $\mathcal V_v \in \varvec{\mathcal {V}}$, its preference over pico-cell $\mathcal N_n \in \varvec{\mathcal {N}}$ can be given as

$$\begin{aligned} \mathbf {\Gamma }^{n}=\frac{1}{\mathcal C_{n}}\sum _{k\in \mathcal {C}_{n}} \tau _{kn}, \end{aligned}$$

(10)

where $\mathbf {\Gamma }^{n} \in \mathbb {C}^{V*N}$ is the files’ preference matrix over pico-cells.

The detailed algorithm of sub-problem 1 is shown in Algorithm 1. We propose a distributed algorithm where both files and pico-cells selfishly and rationally interact in a way that the MUs sum-transmission delay is minimized. As shown in Algorithm 1, we use $\mathbf {\Gamma }^{v}$ and $\mathbf {\Gamma }^{n}$ as preference lists. We assume that the number of files is far more larger than the number of pico-cells. At first, the pico-cells send their first choices according to their preference lists. Since a file can be cached in $Q_{1}$ pico-cells, we need judge whether the requests from pico-cells for a file are more than the quota $Q_{1}$. If there are more than $Q_{1}$ pico-cells requesting the same file, CP will select its most preferred $Q_{1}$ pico-cells. If the requests for a file are less than or equal to the quota $Q_{1}$, files accept these requests all. Then, the remaining pico-cells will be rejected and continue to take part in next round of offers until each pico-cell gets a file to cache.

3.4 Pico-Cell Selection Algorithm

After the file allocation problem solved by Algorithm 1, we turn- to handle the pico-cell selection problem. The transmission delay from the pico-cell to each MU is employed to construct the preference of this pico-cell. Thus, the preference of pico-cell over MU is written as follows.

Definition 3

For a pico-cell $\mathcal N_n \in \varvec{\mathcal {N}}$, its preference over MU $\mathcal M_m \in \varvec{\mathcal {M}}$ can be given as

$$\begin{aligned} \mathbf {\Gamma }^{m}=\tau _{mn}^{v}, \end{aligned}$$

(11)

where $\mathbf {\Gamma }^{m} \in \mathbb {C}^{N*M}$ is the pico-cells’ preference matrix over MUs.

Moreover, the preference over pico-cells by MUs will be effected by sub-problem 1. When the pico-cells cached files, they broadcasts information about the cached files to all serving MUs. Accordingly, the MUs’ preference over pico-cell is also based on $p_{mv}$, since different files have different attraction for MUs. Then, the MU’s preference over pico-cells is written as follows.

Definition 4

For $\mathcal M_m \in \varvec{\mathcal {M}}$, its preference over pico-cell $\mathcal N_n \in \varvec{\mathcal {N}}$ can be given as

$$\begin{aligned} \mathbf {\Gamma }^{n'}=\tau _{mn}^{v}{p_{mv}}, \end{aligned}$$

(12)

where $\mathbf {\Gamma }^{n'} \in \mathbb {C}^{M*N}$ is the MUs’ matrix preference over pico-cells.

The specific algorithm of sub-problem 2 is shown in Algorithm 2. The distributed Algorithm 2 has been proposed to minimize sum-transmission delay by allocate the MUs to pico-cells effectively. The distributed Algorithm 2 progresses as MUs send their offers to most select pico-cells. Then, if the requests for a pico-cell are more than the quota $Q_{2}$, the pico-cell will decide to accept the more preferred MUs according to preference lists, and reject the others. Else, pico-cells will accept all requests. The rejected MUs remove the most select pico-cells and continue to take part in progress till all pico-cells could not construct more links to MUs. At the last, if there still exists a MU without links, it will connect to Macro-cell.

3.5 Stability of Matching

At last, it is critical to find a stable matching between two opposite sides, because it guarantees that none of players have motivations to change their matched players. Since the matching $\mu _{1}$ obeys the similar matching rules with $\mu _{2}$, we will analysis the stability of the second matching $\mu _{2}$ for brevity.

We prove it by contradiction. Given a blocking pair $(\mathcal M_{1},\mathcal N_{1})$ for $\mu _{2}$. In this case, $\mathcal N_{1}$ prefers $\mathcal M_{1}$ to $\mu _{2}(\mathcal N_{1})$ and $\mathcal M_{1}$ prefers $\mathcal N_{1}$ to at least one element in $\mu _{2}(\mathcal M_{1})$, i.e., the MU matches with another pico-cell which is in a higher order in preference list than its previous matched player, and hence both opposite sides will improve their outcomes. But it is contrary to the original definition of matching, i.e., the opposite two sides will change its order in preference list firstly in order to get a better outcome. Thus, there exists no blocking pair in matching games and $\mu _{2}$ is proved to be a stable matching.

4 Numerical Results

In this section, we evaluate the performance of the proposed two algorithms by some numerical results. We assume the quota of $\varvec{\mathcal V}$ is 20 and $Q_{1}=2$. Moreover, the quota of $\varvec{\mathcal M}$ is $\in [16,34]$ and the quota of $\varvec{\mathcal N}$ is $\in [8,20]$. In this simulations, we assume all MUs and pico-cells are randomly located and the physical layer parameters are set to be practical. The transmit power of a pico-cell is typically 2W, the pass loss $\alpha$ is 4 and the noise power is set to $10^{-10}$.

In the following figures, we compare our proposed algorithms with no caching, random allocation and exhaustive searching algorithms. In the no caching algorithm, the pico-cell caches no file. If MUs connect to the pico-cells, the pico-cells would download the requesting files via backhaul channels firstly and then transmit the files to MUs. Thus, no caching algorithm will lead to high latency. In the random allocation algorithm, we assign that files are randomly cached. In the exhaustive searching algorithm, the problems are addressed by centralized solution with high complexity.

Fig. 2.

Average delay vs Number of pico-cells

Fig. 3.

Average delay vs Number of MUs

In Fig. 2, the number of MUs is 60 and the pico-cell number varies from 8 to 20 with each pico-cell serving at most 2 MUs. As observed from Fig. 2, with the increasing of pico-cell number, the average delay of both the exhaustive searching algorithm curve and proposed algorithm curve have a decreasing trend. Though the exhaustive searching algorithm shows better performance to the proposed one, the proposed algorithm has less computation complexity $\mathcal {O}(\mathcal M \times \mathcal N)$ while the exhaustive searching algorithm complexity increases exponentially over network size. It is easy to verify that with low complexity, the proposed algorithm will reduce a big cost of server processing power. Also, it can be observed that no caching algorithm’s average downloading delay is fixed with the 0.5 s delay. And we find that random allocation algorithm exhibits a inferior performance compared with proposed algorithm.

In Fig. 3, we fix the pico-cell number to be 10 and vary the MUs’ number from 16 to 34. Figure 3 displays that the proposed one has similar delay performance with the exhaustive searching algorithm, and they both descend as the increase of MUs’ numbers. In random allocation algorithm, it shows inferior performance compared with proposed algorithm.

5 Conclusion

In this paper, we solve the resource allocation problems in a pico-cell based caching network. The problems are firstly decoupled into two sub-problems. Then, we construct the preference lists of pico-cells, MUs and CPs, respectively. Then, two algorithms is proposed to find stable matchings in these two matching games. At last, simulation results are shown to demonstrate that the proposed algorithm has similar performance with the exhaustive searching algorithm in reducing average transmission delay and shows better performance than the random allocation and no caching algorithms.