IBP Based Caching Strategy in D2D

Abstract

Device to Device (D2D) communication is a key technology in 5th generation wireless systems to increase communication capacity and spectral efficiency. Applying caching into D2D communication networks, the device can retrieve content from other devices by establishing D2D communication links. In this way, the backhaul traffic can be significantly reduced. However, most of the existing caching schemes in D2D are proactive caching, which cannot satisfy the requirement of real-time updating. In this paper, we propose an Indian Buffet Process based D2D caching strategy (IBPSC). Firstly, we construct a geographical D2D communication network to provide high quality D2D communications according to physical closeness between devices. Then devices are divided into several social communities. Devices are ranked by their node importance to community in each community. The base station makes caching decisions for devices according to contrition degree. Experimental results show that IBPSC achieves best network performance.

1. Introduction

According to Cisco VNI (Visual Networking Index) report, mobile data traffic will grow 7-fold from 2017 to 2022, and video traffic will be 79% of global mobile data traffic by 2022. It will be a big challenge to current wireless network. To reduce traffic and energy cost of backhaul links, D2D communication has been proposed. Within D2D communication network, device can communicate with nearby device directly by establishing D2D communication link between them. Another potential solution to this challenge is caching, which has been proved can improve network performance of several network scenarios [1,2]. In recent years, caching also has been applied into CN (Core Network) and RAN (Ratio Access Network) of 5th generation wireless systems (5G) to reduce backhaul traffic and network latency [3,4,5,6,7].

Recently, several studies have proved that applying caching strategy into D2D communication network can offload backhaul traffic and improve user experience [8,9]. In D2D caching network, each device is equipped with cache space for caching popular content. Device can receive its desired content from nearby devices instead of BS (Base Station) through one-hop or multi-hop D2D communication. Caching scheme is an important part of D2D caching network and impacts network performance. Most existing D2D caching schemes are proactive caching, i.e., pre-caching popular content to devices before the content being requested during off-peak time. The performance of proactive caching scheme depends on accuracy of prediction.

According to a report released by data provider iResearch, China’s short video mark was valued at 14 billion yuan ($2 billion) in 2018. With the explosive growth of short video mobile apps, proactive caching strategies face a big challenge, since short videos are posed by users in any time, it is impossible to make accurate prediction and update caches in time. Therefore, we propose an IBP based reactive caching strategy. Zhang et al. proved that the influence of user’s content selection by other users can be modeled by Indian Buffet Process (IBP) [10]. IBP defines a probability distribution over equivalence classes of sparse binary matrices with a finite number of rows and an unbounded number of columns [11]. In our model, we firstly construct a reliable D2D communication network according to geographical closeness between devices as in [10]. Then devices in the reliable D2D communication network are grouped into several social communities according to interaction between devices and ranked by their node importance to community. The caching decision is made by BS depending on contribution degree, which is calculated by BS according to IBP. The contributions of this paper are as follows:

• To provide high quality D2D communication links, a reliable D2D communication network is constructed according to physical closeness. Then devices are divided into several social communities according to their interactions and ranked by node importance.
• We propose an IBP based social-aware caching strategy. Within a community, BS makes caching decision for devices according to the contribution of caching content to other devices. Contribution degree is defined to measure the contribution and calculated from IBP.
• Finally, we study the performance of proposed strategy and compare it with other strategies in terms of cache hit ratio and sum rate. The simulation results show that IBPSC strategy achieves better performance, especially in the condition of small cache size and large parameter $\alpha$.

The rest of the paper is organized as follows: We give an overview of related works in Section 2. Section 3 introduces an IBP based socially-aware D2D (IBPSC) caching strategy. Section 4 presents the simulation results. Finally, Section 5 concludes the paper.

2. Related Works

By deploying caching into D2D communication, QoE (Quality of Experience) and QoS (Quality of Service) of users can be significantly improved. The authors have proved that the D2D network with caching performs much better than other solutions [9]. They also proposed a Maximum Distance Separable coding based caching strategy for D2D, each device cache coded block with equal probability, the content can be recovered by obtaining enough coded blocks from other devices [12]. Naderializadeh et al. applied caching into a spectrum sharing mechanism D2D network to improve D2D spectral efficiency [13]. Golrezaei et al. divided the D2D caching network into several clusters, then introduced two caching strategies, deterministic caching strategy and Zipf-Based Random caching strategy. For deterministic caching strategy, each device caches the content with high popularity without duplication. For random caching, the distribution of contents cached by devices randomly and independently follows Zifp distribution [14]. Afshang et al. used Poisson cluster process for modeling locations of devices and proposed a cluster-centric content placement strategy to optimize the performance of the whole cluster [15]. Lee et al. proposed a clustering approach to optimize energy efficiency and throughout for based station assisted D2D caching network [16]. Giatsoglou et al. proposed a D2D-aware caching policy for millimeter-wave network to achieve higher offloading and lower content-retrieval delays [17]. Gregori et al. obtained optimal transmission and caching by formulating caching to a continuous time optimization problem [18]. The authors in [19] proposed a mobility aware caching strategy, the devices with low-speed and high-speed cache most popular content, the other devices cache content with lower popularity. Krishnan et al. proposed a Poisson Point Process based caching strategy for D2D to reduce latency, the locations of devices are modeled by Poisson Point Process, each device randomly caches a portion of content [20]. The authors proposed a probabilistic caching strategy for D2D caching network to maximize the cache hit rate and cache-aided throughput [21]. Chen et al. proposed a user-centric protocol and optimized proactive caching scheme to obtain high offloading gain with low energy cost at helper users [22]. Malak et al. designed a spatially correlated caching scheme, hard-core placement to increase cache hit rate. With the proposed scheme, the devices caching the same content are never closer to each other than the exclusion radius [23]. Recently, social relationship between users has been considered in D2D network. Zhu et al. proposed a socially-aware incentive approach to incentivize users to cache content for others and minimize total cost of the network for retrieving content [24]. A hypergraph framework is proposed by considering social ties, common interests and D2D transmission scheme for caching based D2D communications [25]. Wu et al. defined a notion of socially-aware rate, then proposed a socially-aware rate based content sharing mode selection strategy and modelled it as a maximum weighted mixed matching problem [26]. Wu et al. proposed a D2D relay-aided content caching strategy, which considers the different concentration levels of contents request from different users’ groups and user’s physical link [27].

In summary, most D2D caching schemes are proactive caching and cannot update cached content in time. Moreover, they require accurate prediction of content popularity in future. Several studies focusing on frameworks and incentive schemes are proposed, which have considered social relationships between devices. In this paper, we propose an India Buffet Process based socially-aware caching strategy to improve caching efficiency. Each device determines whether to cache the received content independently according to contribution degree.

3. Method

In this section, we propose an IBP based socially-aware caching strategy for D2D communication network. Physical closeness is used for constructing a reliable D2D communication network. Then the devices are divided into several social communities and ranked by node importance according to their interactions. Within a social community, IBP is used for modeling the influence of other users on user’s selection of content. Caching decision is made by BS according to the contribution of caching the content to other devices within same community.

To provide high quality D2D communication links, a reliable D2D communication network is constructed according to physical closeness between devices. Physical closeness $w_{ij}$ defined by Zhang et al. [10] is the probability of establishing a stable D2D communication link between device i and device j in future, and it ranges from 0 to 1. BS is responsible for collecting devices encounter history and calculating physical closeness $w_{ij}$. In our scheme, we consider the D2D communication network as an undirected graph G(V,E), V is the set of devices, E is the set of edges. The weight of edge between device i and device j is physical closeness $w_{ij}$. Then the reliable D2D communication network, G’(V,E) is constructed according to physical closeness. Within the reliable network, the weight of any edge is larger than a threshold $w_{th}$. In other word, the devices can establish high quality D2D links between them with high probability in future.

In our model, we take social relationships between devices into consideration, i.e., the interactions between devices in history. We construct an interaction matrix $A_{ij}$ to represent the interactions of devices, $a_{ij}=1$, if there was an interaction between device i and j in history; otherwise, $a_{ij}=0$. Given the interaction matrix, the communities can be determined by the method proposed by Chauhan et al. [28], the importance of node k to community can be calculated according to Equation (1) [29].

$$\begin{array}{c}\hfill P_k=({\displaystyle \sum _{i=1}^c\frac{v_{ik}^2}{v_i^T{v}_i}})/c\end{array}$$

(1)

where c is the number of communities, $v_i$ is an eigenvector of interaction matrix A, and $v_{ik}$ is the k-th element of $v_i$. $P_k$ ranges from 0 to 1. Within each community, the device with highest node importance degree will be label as $u_1$ (i.e., the first user) in its community.

The authors in [10] have proved that IBP can model the influence of other users on user’s selection of content. For an IBP with K dishes and N, the customers are labeled in ascending order, $c_1,c_2,\dots .,c_N$. The number of dishes selected by a customer follows Poisson distribution with parameter $\alpha$. The selection on dishes of customer $c_j$ is influenced and only influenced by its prior customers, $c_1,c_2,\dots ,c_{j-1}$, where $j=2,3,\dots ,N$. The probability of customer $c_1$ selecting each dish is $\alpha /K$. The probability of customer $c_j$ selecting dish k, $p(z_{j,k}=1\mid {\mathbf{z}}_{-j,k})$, is given by the following:

$$\begin{array}{c}\hfill p(z_{j,k}=1\mid {\mathbf{z}}_{-j,k})=\left\{\begin{array}{cc}{m}_k^{j-1}/j,\hfill & \hfill {\mathbf{z}}_{-j,k}\ne \mathbf{0}\\ \alpha /(j·K_0^j),\hfill & \hfill {\mathbf{z}}_{-j,k}=\mathbf{0}\end{array}\right.\end{array}$$

(2)

where $\mathbf{Z}$ is a $N\times k$ matrix to describe which customers select which dishes, if the customer $c_n$ has selected dish k, $z_{nk}=1$; otherwise,$z_{nk}=0$. ${\mathbf{z}}_{-j,k}$ is the set of precious customers that have selected dish k. For each customer $c_m$ belonging to ${\mathbf{z}}_{-j,k}$, we have $z_{mk}=1$, and $1⩽m<j$. $m_k^{j-1}$ is the number of precious customers who have selected dish k. $K_0^j$ is the number of dishes which are not tasted by precious customers.

In our model, within each community, devices are labeled in an ascending order according to their node importance $P_k$, the device with highest node importance is labeled as first user, $u_1$, i.e., first customer in IBP. By modeling the influence of other users on content selection, we define contribution degree $\overline{I_{ik}}$ to indicate the contribution of caching content k to device $u_i$ to other users within same community. The contribution degree is given by:

$$\overline{I_{ik}}={\displaystyle \frac{1}{N-1}}\sum _{\begin{array}{c}j=1;\\ j\notin {\mathbf{z}}_{-j,k}\end{array}}^{N}p(z_{j,k}=1\mid {\mathbf{z}}_{-j,k})$$

(3)

where $p(z_{j,k}=1\mid {\mathbf{z}}_{-j,k})$ is the conditional probability of user $u_j$ requesting content k given by Equation (2). High contribution degree indicates content k will be requested by other devices with high probability.

When BS receives a request sent by device $u_i$, firstly checks whether the content is cached by other devices. If the D2D caching network cannot respond to this request, BS will serve the request; otherwise, BS locates content holder with highest physical closeness. BS calculates contribution degree $\overline{I_{ik}}$ according to Equation (3) and makes caching decisions for device $u_i$ by setting caching flag $fq$ ($fq\in \{0,1\}$). If $\overline{I_{ik}}>=I_{th}$, the content can be cached by device $u_i$, i.e., $fq=1$; otherwise, $fq=0$, the content will not be cached by device $u_i$, as described in Algorithm 1. The caching threshold $I_{th}$ is a design number and ranges from 0 to 1.

Algorithm 1 IBPSC strategy

Input: G(V,E), $w_{th}$, $I_{th}$;

Output: fq (caching flag, fq, indicates whether device can cache the content);

Initialize: fq = 0;  1: BS collects encounter and interaction information of devices within the cellular network, calculates closeness $w_{ij}$, constructs reliable D2D communication network G’(V,E);  2: grouping the devices into several social communities and calculating node importance to community of each device by Equation (1);  3: for each community do  4:  labeling devices according to their node importance to community, i.e., $u_1,u_2,\dots \dots ,u_N$;  5: end for  6: BS receives a request for content f sent by device $u_i$  7: BS calculates contribution degree $\overline{I_{if}}$ according to Equation (3);  8: if$\overline{I_{if}}>=I_{th}$then  9:  let $fq=1$; 10: else 11:  let $fq=0$; 12: end if 13: if content f can be retrieved from other devices in the D2D caching network then 14:  BS locates content holder with highest physical closeness and sends caching flag $fq$ to the content holder; 15:  establishing D2D communication to transmit content f with caching flag $fq$; 16: else 17:  BS servers the request directly with content f and caching flag $fq$; 18: end if 19: When device $u_i$ receives content f 20: if$fq\ne 0$then 21:  device $u_i$ caches content f; 22: end if

4. Performance Evaluation

In this section, we investigate the performance of proposed strategy and compare it with other caching strategies for D2D:

• Maximal closeness: BS locates content holder with highest closeness to user [10]. All the content received by device are cached.
• Zipf-based Caching: It is a proactive caching strategy, files are pre-cached into devices according to Zipf distribution [14].
• Most popular caching strategy: It is also a proactive caching strategy, the most popular files are pre-cached into devices according to the predication of content popularity.

In our simulations, devices are randomly distributed on a surface covered by a BS, the radius of BS is 500 m. The max D2D communication distance ranges from 5 m to 50 m. BS is responsible for collecting users’ encounter and interaction history, also locating content holder(s). In our simulation, cellular spectrum is used for both cellular and D2D communications, i.e., underlay inband D2D [30]. Content selections of devices are modeled by IBP. We use cache hit ratio and sum rate [10] to study the performance of four caching schemes. We define cache hit ratio as the rate of requests satisfied by other devices to all the requests sent by devices.

In our strategy, BS determines whether the content can be cached by device according to contribution degree $\overline{I_{ik}}$ and caching threshold $I_{th}$. Firstly, we investigate the influence of caching threshold $I_{th}$ on cache hit ratio under different Poisson parameter $\alpha$ and cache size, as shown in Figure 1 and Figure 2. Parameter $\alpha$ reflects user’s preference; a large $\alpha$ indicates that devices request new content (has not been requested by precious devices) with high probability. Cache hit ratio increases with $I_{th}$ increasing in the first stage, then decreases to zero. This is because, once threshold $I_{th}$ exceeds contrition degrees of all users, none of content can be cached in D2D network.

In Figure 3 and Figure 4, we investigate the performance of all the strategies with different parameter $\alpha$. Parameter $\alpha$ reflects users preference, a large $\alpha$ means devices request new content with high probability, which is not cached by other devices. In this case, the traffic to BS will increase. As shown in Figure 3, with the increasing of parameter $\alpha$, caching hit ratio of all strategies decreases. The proposed IBPSC strategies achieve highest cache hit ratio compared to other schemes, and the advantages of IBPSC are more obvious with larger $\alpha$. With $\alpha$ increasing, the total number of content requested by users increases, therefore the sum rate increases as shown in Figure 4. The proposed IBPSC strategy achieves best performance thanks to its contribution degree based caching strategy. The content cached by devices will be requested by other devices with high probability in future.

With the increasing of cache size, more content can be cached by devices, and more requests can be satisfied through D2D communications. Therefore, the cache hit ratio of all the caching strategies increases with the increasing of cache size as shown in Figure 5. Meanwhile, as more requests are satisfied by devices, the traffic to BS can be reduced. Figure 6 shows that the sum rate of all schemes increases as the cache size is increased. Since the proposed strategy takes probability of establishing D2D communication in future into consideration, any two devices in the D2D communication network we constructed can establish a D2D communication in future with high probability. We also consider the social relationships between devices. Each device makes caching decision independently according to contribution to the community of caching the content. Only the content with high contribution degree can be cached by devices. Thus, the proposed IBPSC strategy performs much better than other three strategies in terms of caching hit ratio and sum rate, especially with small cache size.

Figure 7 and Figure 8 show the performance of four strategies with different number of users. The cache hit ratio and sum rate increase with the number of users increasing, since more caching space is provided. With the increasing of Max D2D communication distance, the number of devices in D2D communication network increase, more caching space will be provided. Therefore the cache hit ratio and sum rate increase, as shown in Figure 9 and Figure 10.

5. Conclusions

In this paper, we introduced an Indian Buffet Process based socially-aware D2D caching strategy (IBPSC). To provide high quality D2D communication links, a reliable D2D communication network is constructed according to physical closeness between devices. Then devices are grouped into several social communities and ranked by their node importance to community. BS calculates contribution degree and makes caching decisions for a device according to IBP. Finally, the experimental results have shown that the proposed IBPSC achieves highest network performance. In our future work, we intend to apply network coding into D2D caching network.