Open AccessArticle

Coded Caching for Broadcast Networks with User Cooperation^†

Zhenhao Huang

¹,

Jiahui Chen

¹,

Xiaowen You

¹,

Shuai Ma

² and

Youlong Wu

^1,*

School of Information Science and Technology, ShanghaiTech University, No. 393 Huaxia Middle Road, Pudong, Shanghai 201210, China

Information Processing and Communications Laboratory, Telecom Paris, IP Paris, 91120 Palaiseau, France

Author to whom correspondence should be addressed.

^†

This paper was in part presented at the IEEE Information Theory Workshop, Visby, Gotland, Sweden, 2019 and at the IEEE 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA, 24–27 September 2019.

Entropy 2022, 24(8), 1034; https://doi.org/10.3390/e24081034

Submission received: 22 June 2022 / Revised: 24 July 2022 / Accepted: 25 July 2022 / Published: 27 July 2022

(This article belongs to the Special Issue Information Theoretic Methods for Future Communication Systems)

Download

Browse Figures

Versions Notes

Abstract

Caching technique is a promising approach to reduce the heavy traffic load and improve user latency experience for the Internet of Things (IoT). In this paper, by exploiting edge cache resources and communication opportunities in device-to-device (D2D) networks and broadcast networks, two novel coded caching schemes are proposed that greatly reduce transmission latency for the centralized and decentralized caching settings, respectively. In addition to the multicast gain, both schemes obtain an additional cooperation gain offered by user cooperation and an additional parallel gain offered by the parallel transmission among the server and users. With a newly established lower bound on the transmission delay, we prove that the centralized coded caching scheme is order-optimal, i.e., achieving a constant multiplicative gap within the minimum transmission delay. The decentralized coded caching scheme is also order-optimal if each user’s cache size is larger than a threshold which approaches zero as the total number of users tends to infinity. Moreover, theoretical analysis shows that to reduce the transmission delay, the number of users sending signals simultaneously should be appropriately chosen according to the user’s cache size, and always letting more users send information in parallel could cause high transmission delay.

Keywords:

coded cache; cooperation; device-to-device; transmission delay

1. Introduction

With the rapid development of Internet of Things (IoT) technologies, IoT data traffic, such as live streaming and on-demand video streaming, has grown dramatically over the past few years. To reduce the traffic load and improve the user latency experience, the caching technique has been viewed as a promising approach that shifts the network traffic to low congestion periods. In the seminal paper [1], Maddah-Ali and Niesen proposed a coded caching scheme based on centralized file placement and coded multicast delivery that achieves a significantly larger global multicast gain compared to the conventional uncoded caching scheme.

The coded caching scheme has attracted wide and significant interest. The coded caching scheme was extended to a setup with decentralized file placement, where no coordination is required for the file placement [2]. For the cache-aided broadcast network, ref. [3] showed that the rate–memory tradeoff of the above caching system is within a factor of 2.00884. For the setting with uncoded file placement where each user stores uncoded content from the library, refs. [4,5] proved that Maddah-Ali and Niesen’s scheme is optimal. In [6], both the placement and delivery phases of coded caching are depicted using a placement delivery array (PDA), and an upper bound for all possible regular PDAs was established. In [7], the authors studied a cached-aided network with heterogeneous setting where the user cache memories are unequal. More asymmetric network settings have been discussed, such as coded caching with heterogeneous user profiles [8], with distinct sizes of files [9], with asymmetric cache sizes [10,11,12] and with distinct link qualities [13]. The settings with varying file popularities have been discussed in [14,15,16]. Coded caching that jointly considers various heterogeneous aspects was studied in [17]. Other works on coded caching include, e.g., cache-aided noiseless multi-server network [18], cache-aided wireless/noisy broadcast networks [19,20,21,22], cache-aided relay networks [23,24,25], cache-aided interference management [26,27], coded caching with random demands [28], caching in combination networks [29], coded caching under secrecy constraints [30], coded caching with reduced subpacketization [31,32], the coded caching problem where each user requests multiple files [33], and a cache-aided broadcast network for correlated content [34], etc.

A different line of work is to study the cached-aided networks without the presence of a server, e.g., the device-to-device (D2D) cache-aided network. In [35], the authors investigated coded caching for wireless D2D network [35], where users locate in a fixed mesh topology wireless D2D network. A D2D system with selfish users who do not participate in delivering the missing subfiles to all users was studied in [36]. Wang et al. applied the PDA to characterize cache-aided D2D wireless networks in [37]. In [38], the authors studied the spatial D2D networks in which the user locations are modeled by a Poisson point process. For heterogeneous cache-aided D2D networks where users are equipped with cache memories of distinct sizes, ref. [39] minimized the delivery load by optimizing over the partition during the placement phase and the size and structure of D2D during the delivery phase. A highly dense wireless network with device mobility was investigated in [40].

In fact, combining the cache-aided broadcast network with the cache-aided D2D network can potentially reduce the transmission latency. This hybrid network is common in many practical distributed systems such as cloud network [41], where a central cloud server broadcasts messages to multiple users through the cellular network, and meanwhile users communicate with each other through a fiber local area network (LAN). A potential scenario is that users in a moderately dense area, such as a university, want to download files, such as movies, from a data library, such as a video service provider. It should be noted that the user demands are highly redundant, and the files need not only be stored by a central server but also partially cached by other users. Someone can attain the desired content through both communicating with the central server and other users such that the communication and storage resources can be used efficiently. Unfortunately, there is very little research investigating the coded caching problem for this hybrid network. In this paper, we consider such hybrid cache-aided network where a server consisting of

N \in Z^{+}

files connects with

K \in Z^{+}

users through a broadcast network, and meanwhile the users can exchange information via a D2D network. Unlike the settings of [35,38], in which each user can only communicate with its neighboring users via spatial multiplexing, we consider the D2D network as either an error-free shared link or a flexible routing network [18]. In particular, for the case of the shared link, all users exchange information via a shared link. In the flexible routing network, there exists a routing strategy adaptively partitioning all users into multiple groups, in each of which one user sends data packets error-free to the remaining users in the corresponding group. Let

α \in Z

be the number of groups who send signals at the same time, then the following fundamental questions arise for this hybrid cache-aided network:

How does α affect the system performance?
What is the (approximately) optimal value of α to minimize the transmission latency?
How can communication loads be allocated between the server and users to achieve the minimum transmission latency?

In this paper, we try to address these questions, and our main contributions are summarized as follows:

We propose novel coded caching schemes for this hybrid network under centralized and decentralized data placement. Both schemes efficiently exploit communication opportunities in D2D and broadcast networks, and appropriately allocate communication loads between the server and users. In addition to multicast gain, our schemes achieve much smaller transmission latency than both that of Maddah-Ali and Niesen’s scheme for a broadcast network [1,2] and the D2D coded caching scheme [35]. We characterize a cooperation gain and a parallel gain achieved by our schemes, where the cooperation gain is obtained through cooperation among users in the D2D network, and the parallel gain is obtained through the parallel transmission between the server and users.
We prove that the centralized scheme is order-optimal, i.e., achieving the optimal transmission delay within a constant multiplicative gap in all regimes. Moreover, the decentralized scheme is also optimal when the cache size of each user M is larger than the threshold $N (1 - \sqrt[K - 1]{1 / (K + 1)})$ that is approaching zero as $K \to \infty$ .
For the centralized data placement case, theoretical analysis shows that $α$ should decrease with the increase of the user caching size. In particular, when each user’s caching size is sufficiently large, only one user should be allowed to send information, indicating that the D2D network can be just a simple shared link connecting all users. For the decentralized data placement case, $α$ should be dynamically changing according to the sizes of subfiles created in the placement phase. In other words, always letting more users parallelly send information can cause a high transmission delay.

Please note that the decentralized scenario is much more complicated than the centralized scenario, since each subfile can be stored by

s = 1, 2, \dots, K

users, leading to a dynamic file-splitting and communication strategy in the D2D network. Our schemes, in particular the decentralized coded caching scheme, differ greatly with the D2D coded caching scheme in [35]. Specifically, ref. [35] considered a fixed network topology where each user connects with a fixed set of users, and the total user cache sizes must be large enough to store all files in the library. However, in our schemes, the user group partition is dynamically changing, and each user can communicate with any set of users via network routing. Moreover, our model has the server share communication loads with the users, resulting in an allocation problem on communication loads between the broadcast network and D2D network. Finally, our schemes achieve a tradeoff between the cooperation gain, parallel gain and multicast gain, while the schemes in [1,2,35] only achieve the multicast gain.

The remainder of this paper is as follows. Section 2 presents the system model, and defines the main problem studied in this paper. We summarize the obtained main results in Section 3. Following that is a detailed description of the centralized coded caching scheme with user cooperation in Section 4. Section 5 extends the techniques we developed for the centralized caching problem to the setting of decentralized random caching. Section 6 concludes this paper.

2. System Model and Problem Definition

Consider a cache-aided network consisting of a single server and K users as depicted in Figure 1. The server has a library of N independent files

W_{1}, \dots, W_{N}

. Each file

W_{n}

n = 1, \dots, N

, is uniformly distributed over

[2^{F}] ≜ {1, 2, \dots, 2^{F}},

for some positive integer F. The server connects with K users through a noisy-free shared link but rate-limited to a network speed of

C_{1}

bits per second (bits/s). Each user

k \in [K]

is equipped with a cache memory of size

M F

bits, for some

M \in [0, N]

, and can communicate with each other via a D2D network.

We mainly focus on two types of D2D networks: a shared link as in [1,2] and a flexible routing network introduced in [18]. In the case of a shared link, all users connect with each other through a shared error-free link but rate-limited to

C_{2}

bits/s. In the flexible routing network, K users can arbitrarily form multiple groups via network routing, in each of which at most one user can send error-free data packets at a network speed

C_{2}

bits/s to the remaining users within the group. To unify these two types of D2D networks, we introduce an integer

α_{max} \in {1, ⌊ \frac{K}{2} ⌋}

, which denotes the maximum number of groups allowed to send data parallelly in the D2D network. For example, when

α_{\max} = 1

, the D2D network degenerates into a shared link, and when

α_{\max} = ⌊ \frac{K}{2} ⌋

, it turns to be the flexible network.

The system works in two phases: a placement phase and a delivery phase. In the placement phase, all users will access the entire library

W_{1}, \dots, W_{N}

and fill the content to their caching memories. More specifically, each user k, for

k \in [K]

, maps

W_{1}, \dots, W_{N}

to its cache content:

\begin{matrix} Z_{k} ≜ ϕ_{k} (W_{1}, \dots, W_{N}), \end{matrix}

(1)

for some caching function

\begin{matrix} ϕ_{k} : {[2^{F}]}^{N} \to [⌊ 2^{M F} ⌋] . \end{matrix}

(2)

In the delivery phase, each user requests one of the N files from the library. We denote the demand of user k as

d_{k} \in [N]

, and its desired file as

W_{d_{k}}

. Let

d ≜ (d_{1}, \dots, d_{K})

denotes the request vector. In this paper, we investigate the worst request case where each user makes a unique request.

Once the request vector

d

is informed to the server and all users, the server produces the symbol

\begin{matrix} X ≜ f_{d} (W_{1}, \dots, W_{N}), \end{matrix}

(3)

and broadcasts it to all users through the broadcast network. Meanwhile, user

k \in {1, \dots, K}

produces the symbol (Each user k can produce

X_{k}

as a function of

Z_{k}

and the received signals sent by the server, but because all users can access to the server’s signal due to the fact that the server broadcasts its signals to the network, it is equivalent to generating

X_{k}

as a function

Z_{k}

\begin{matrix} X_{k} ≜ f_{k, d} (Z_{k}), \end{matrix}

(4)

and sends it to a set of intended users

D_{k} \subseteq [K]

through the D2D network. Here,

D_{k}

represents the set of destination users served by node k,

f_{d}

and

f_{k, d}

are some encoding functions

\begin{matrix} f_{d} : {[2^{F}]}^{N} \to [⌊ 2^{R_{1} F} ⌋], f_{k, d} : [⌊ 2^{M F} ⌋] \to [⌊ 2^{R_{2} F} ⌋], \end{matrix}

(5)

where

R_{1}

and

R_{2}

denote the transmission rate sent by the server in the broadcast network and by each user in the D2D network, respectively. Here we focus on the symmetric case where all users have the same transmission rate. Due to the constraint of

α_{\max}

, at most

α_{\max}

users can send signals parallelly in each channel use. The set of

α_{\max}

users who send signals in parallel could be adaptively changed in the delivery phase.

At the end of the delivery phase, due to the error-free transmission in the broadcast and D2D networks, user k observes symbols sent to them, i.e.,

(X_{j} : j \in [K], k \in D_{j})

, and decodes its desired message as

{\hat{W}}_{d_{k}} = ψ_{k, d} (X, (X_{j} : j \in [K], k \in D_{j}), Z_{k}),

where

ψ_{k, d}

is a decoding function.

We define the worst-case probability of error as

\begin{matrix} P_{e} ≜ max_{d \in F^{n}} max_{k \in [K]} \Pr ({\hat{W}}_{d_{k}} \neq W_{d_{k}}) . \end{matrix}

(6)

A coded caching scheme

(M, R_{1}, R_{2})

consists of caching functions

{ϕ_{k}}

, encoding functions

{f_{d}, f_{k, d}}

and decoding functions

{ψ_{k, d}}

. We say that the rate region

(M, R_{1}, R_{2})

is achievable if for every

ϵ > 0

and every large enough file size F, there exists a coded caching scheme such that

P_{e}

is less than

ϵ

Since the server and the users send signals in parallel, the total transmission delay, denoted by T, can be defined as

\begin{matrix} T ≜ max {\frac{R_{1} F}{C_{1}}, \frac{R_{2} F}{C_{2}}} . \end{matrix}

(7)

The optimal transmission delay is

T^{*} ≜ inf {T : T is achievable}

. For simplicity, we assume that

C_{1} = C_{2} = F

, and then from (7) we have

\begin{matrix} T = max {R_{1}, R_{2}} . \end{matrix}

(8)

When

C_{1} \neq C_{2}

, e.g.,

C_{1} : C_{2} = 1 / k

, one small adjustment allowing our scheme to continue to work is multiplying

λ

1 / (k (1 - λ) + λ)

, where

λ

is a devisable parameter introduced later.

Our goal is to design a coded caching scheme to minimize the transmission delay. Finally, in this paper we assume

K \leq N

and

M \leq N

. Extending the results to other scenarios is straightforward, as mentioned in [1].

3. Main Results

We first establish a general lower bound on the transmission delay for the system model described in Section 2, then present two upper bounds of the optimal transmission delay achieved by our centralized and decentralized coded caching schemes, respectively. Finally, we present the optimality results of these two schemes.

Theorem 1

(Lower Bound). For memory size

0 \leq M \leq N

, the optimal transmission delay is lower bounded by

\begin{matrix} T^{*} \geq max & \{\frac{1}{2} (1 - \frac{M}{N}), max_{s \in [K]} (s - \frac{K M}{⌊ N / s ⌋}), max_{s \in [K]} (s - \frac{s M}{⌊ N / s ⌋}) \frac{1}{1 + α_{\max}}\} . \end{matrix}

(9)

Proof.

See the proof in Appendix A. □

3.1. Centralized Coded Caching

In the following theorem, we present an upper bound on the transmission delay for the centralized caching setup.

Theorem 2

(Upper Bound for the Centralized Scenario). Let

t ≜ K M / N \in Z^{+}

, and

α \in Z^{+}

. For memory size

M \in {0, \frac{N}{K}, \frac{2 N}{K}, \dots, N}

, the optimal transmission delay

T^{*}

is upper bounded by

T^{*} \leq T_{central}

, where

\begin{matrix} T_{central} ≜ min_{α \leq α_{max}} K (1 - \frac{M}{N}) \frac{1}{1 + t + α min {⌊ \frac{K}{α} ⌋ - 1, t}} . \end{matrix}

(10)

For general

0 \leq M \leq N

, the lower convex envelope of these points is achievable.

Proof.

See scheme in Section 4. □

The following simple example shows that the proposed upper bound can greatly reduce the transmission delay.

Example 1.

Consider a network described in Section 2 with

K M / N = K - 1

. The coded caching scheme without D2D communication [1] has the server multicast an XOR message useful for all K users, achieving the transmission delay

K (1 - \frac{M}{N}) \frac{1}{1 + t} = \frac{1}{K}

. The D2D coded caching scheme [35] achieves the transmission delay

\frac{N}{M} (1 - \frac{M}{N}) = \frac{1}{K - 1}

. The achievable transmission delay in Theorem 2 equals

\frac{1}{2 K - 1}

by letting

α = 1

, almost twice as short as the transmission delay of previous schemes if K is sufficiently large.

From (10), we obtain that the optimal value of

α

, denoted by

α^{*}

, equals 1 if

t \geq K - 1

and to

α_{\max}

t \leq ⌊ \frac{K}{α_{\max}} ⌋ - 1

. When ignoring all integer constraints, we obtain

α^{*} = \frac{K}{t + 1}

. We rewrite this choice as follows:

α^{*} = \{\begin{matrix} 1, & t \geq K - 1, \\ K / (t + 1), & ⌊ K / α_{\max} ⌋ - 1 < t < K - 1, \\ α_{\max}, & t \leq ⌊ K / α_{\max} ⌋ - 1 . \end{matrix}

(11)

Remark 1.

From (11), we observe that when M is small such that

t \leq ⌊ K / α_{\max} ⌋ - 1

, we have

α^{*} = α_{\max}

. As M is increasing,

α^{*}

becomes

K / (t + 1)

, smaller than

α_{\max}

. When M is sufficiently large such that

M \geq (K - 1) N / K

, only one user should be allowed to send information, i.e.,

α^{*} = 1

. This indicates that letting more users parallelly send information could be harmful. The main reason for this phenomenon is the existence of a tradeoff between the multicast gain, cooperation gain and parallel gain, which will be introduced below in this section.

Comparing

T_{central}

with the transmission delay achieved by Maddah-Ali and Niesen’s scheme for the broadcast network [1], i.e.,

K (1 - \frac{M}{N}) \frac{1}{1 + t}

T_{central}

consists of an additional factor

\begin{matrix} G_{central,c} ≜ \frac{1}{1 + \frac{α}{1 + t} min {⌊ \frac{K}{α} ⌋ - 1, t}}, \end{matrix}

(12)

referred to as centralized cooperation gain, as it arises from user cooperation. Comparing

T_{central}

with the transmission delay achieved by the D2D coded caching scheme [35], i.e.,

\frac{N}{M} (1 - \frac{M}{N})

T_{central}

consists of an additional factor

\begin{matrix} G_{central,p} ≜ \frac{1}{1 + \frac{1}{t} + \frac{α}{t} min {⌊ \frac{K}{α} ⌋ - 1, t}}, \end{matrix}

(13)

referred to as centralized parallel gain, as it arises from parallel transmission among the server and users. Both gains depend on K,

M / N

and

α_{max}

Substituting the optimal

α^{*}

into (12), we have

G_{central,c} = \{\begin{matrix} \frac{1 + t}{K + t}, & t \geq K - 1, \\ \frac{1 + t}{K - \frac{K}{t + 1} + t}, & ⌊ \frac{K}{α_{\max}} ⌋ - 1 < t < K - 1, \\ \frac{1 + t}{α_{\max} t + t + 1}, & t \leq ⌊ \frac{K}{α_{\max}} ⌋ - 1 . \end{matrix}

(14)

When fixing

(K, N, α_{max})

G_{central,c}

in general is not a monotonic function of M. More specifically, when M is small enough such that

t < ⌊ \frac{K}{α_{\max}} ⌋ - 1

, the function

G_{central,c}

is monotonically decreasing, indicating that the improvement caused by introducing D2D communication. This is mainly because relatively larger M allows users to share more common data with each other, providing more opportunities on user cooperation. However, when M grows larger such that

t \geq ⌊ \frac{K}{α_{\max}} ⌋ - 1

, the local and global caching gains become dominant, and less improvement can be obtained from user cooperation, turning

G_{central,c}

to a monotonic increasing function of M,

Similarly, substituting the optimal

α^{*}

into (13), we obtain

G_{central,p} = \{\begin{matrix} \frac{t}{K + t}, & t \geq K - 1, \\ \frac{t}{\frac{t \cdot K}{t + 1} + t + 1}, & ⌊ \frac{K}{α_{\max}} ⌋ - 1 < t < K - 1, \\ \frac{t}{α_{\max} t + t + 1}, & t \leq ⌊ \frac{K}{α_{\max}} ⌋ - 1 . \end{matrix}

(15)

Equation (15) shows that

G_{central,p}

is monotonically increasing with t, mainly due to the fact that when M increases, more content can be sent through the D2D network without the help of the central server, decreasing the improvement from parallel transmission between the server and users.

The centralized cooperation gain (12) and parallel gain (13) are plotted in Figure 2 when

N = 40

K = 20

and

α_{max} = 5

Remark 2.

Larger α could lead to better parallel and cooperation gain (more uses can concurrently multicast signals to other users), but will result in worse multicast gain (signals are multicast to fewer users in each group). The choice of α in (11) is in fact a tradeoff between the multicast gain, parallel gain and cooperation gain.

The proposed scheme achieving the upper bound in Theorem 2 is order-optimal.

Theorem 3.

For memory size

0 \leq M \leq N

\begin{matrix} \frac{T_{central}}{T^{*}} \leq 31 . \end{matrix}

(16)

Proof.

See the proof in Appendix B. □

The exact gap of

T_{central} / T^{*}

could be much smaller. One could apply the method proposed in [3] to obtain a tighter lower bound and shrink the gap. In this paper, we only prove the order optimality of the proposed scheme, and leave the work of finding a smaller gap as the future work.

Figure 3 plots the lower bound (9) and upper bounds achieved by various schemes, including the proposed scheme, the scheme Maddah-Ali 2014 in [1] which considers the broadcast network without D2D communication, and the scheme Ji 2016 in [35], which considers the D2D network without server. It is obvious that our scheme outperforms the previous schemes and approaches closely to the lower bound.

3.2. Decentralized Coded Caching

We exploit the multicast gain from coded caching, D2D communication, and parallel transmission between the server and users, leading to the following upper bound.

Theorem 4

(Upper Bound for the Decentralized Scenario). Define

p ≜ M / N

. For memory size

0 \leq M \leq N

, the optimal transmission delay

T^{*}

is upper bounded by

\begin{matrix} T^{*} \leq T_{decentral} ≜ max \{R_{\emptyset}, \frac{R_{s} R_{u}}{R_{s} + R_{u} - R_{\emptyset}}\}, \end{matrix}

(17)

where

\begin{matrix} R_{\emptyset} ≜ & K {(1 - p)}^{K}, \end{matrix}

(18)

\begin{matrix} R_{s} ≜ & \frac{1 - p}{p} (1 - {(1 - p)}^{K}), \end{matrix}

(19)

\begin{matrix} R_{u} ≜ & \frac{1}{α_{\max}} \sum_{s = 2}^{⌈ \frac{K}{α_{\max}} ⌉ - 1} (\frac{s (\binom{K}{s})}{s - 1} p^{s - 1} {(1 - p)}^{K - s + 1}) + \sum_{s = ⌈ \frac{K}{α_{\max}} ⌉}^{K} (\frac{K (\binom{K - 1}{s - 1})}{f (K, s)} p^{s - 1} {(1 - p)}^{K - s + 1}), \end{matrix}

(20)

with

\begin{matrix} f (K, s) ≜ \{\begin{matrix} ⌊ \frac{K}{s} ⌋ (s - 1), & (K m o d s) < 2, \\ K - 1 - ⌊ K / s ⌋, & (K m o d s) \geq 2 . \end{matrix} \end{matrix}

(21)

Proof.

Here,

R_{\emptyset}

represents the transmission rate of sending contents that are not cached by any user,

R_{s}

and

R_{u}

represent the transmission rate sent by the server via the broadcast network, and the transmission rate sent by users via the D2D network, respectively. Equation (17) balances the communication loads assigned to the server and users. See more detailed proof in Section 5. □

The key idea of the scheme achieving (17) is to partition K users into

⌈ \frac{K}{s} ⌉

groups for each communication round

s \in [K - 1]

, and let each group perform the D2D coded caching scheme [35] to exchange information. The main challenge is that that among all

⌈ \frac{K}{s} ⌉

groups, there are

⌊ \frac{K}{s} ⌋

groups of the same size s, and an abnormal group of size

(K \mod s)

(K \mod s) \neq 0

, leading to an asymmetric caching setup. One may use the scheme [35] for the groups of size s, for the group of size

(K \mod s) \geq 2

, but how to exploit the caching resource and communication capability of all groups while balancing communication loads among the two types of groups to minimize the transmission delay remains elusive and needs to be carefully designed. Moreover, this challenge poses complexities both in establishing the upper bound and in optimality proof.

Remark 3.

The upper bound in Theorem 4 is achieved by setting the number of users that exactly send signals in parallel as follows:

α_{D} = \{\begin{matrix} α_{max}, & case 1, \\ ⌊ \frac{K}{s} ⌋, & case 2, \\ ⌈ \frac{K}{s} ⌉, & case 3 . \end{matrix}

(22)

⌈ \frac{K}{s} ⌉ > α_{max}

, the number of users who send data in parallel is smaller than

α_{\max}

, indicating that always letting more users parallelly send messages could cause higher transmission delay. For example, when

K \geq 4

s = K - 1

and

α_{\max} = ⌊ \frac{K}{2} ⌋

, we have

α_{D} = 1 < α_{\max}

Remark 4.

From the definitions of

T_{decentral}

R_{s}

R_{u}

and

R_{\emptyset}

, it is easy to obtain that

R_{\emptyset} \leq T_{decentral} \leq R_{s}

\begin{matrix} T_{decentral} = \{\begin{matrix} \frac{R_{s} R_{u}}{R_{s} + R_{u} - R_{\emptyset}}, & R_{u} \geq R_{\emptyset}, \\ R_{\emptyset}, & R_{u} < R_{\emptyset}, \end{matrix} \end{matrix}

(23)

T_{decentral}

decreases as

α_{\max}

increases, and

T_{decentral}

increases as

R_{u}

increases if

R_{u} \geq R_{\emptyset}

Due to the complex term

R_{u}

T_{decentral}

in Theorem 4 is hard to evaluate. Since

T_{decentral}

is increasing as

R_{u}

increases (see Remark 4), substituting the following upper bound of

R_{u}

into (17) provides an efficient way to evaluate

T_{decentral}

Corollary 1.

For memory size

0 \leq p \leq 1

, the upper bound of

R_{u}

is given below:

$α_{\max} = 1$ (a shared link):

$\begin{matrix} R_{u} \leq & \frac{1 - p}{p} [1 - \frac{5}{2} K p {(1 - p)}^{K - 1} - 4 {(1 - p)}^{K} + \frac{3 (1 - {(1 - p)}^{K + 1})}{(K + 1) p}]; \end{matrix}$

(24)
$α_{\max} = ⌊ \frac{K}{2} ⌋$ (a flexible network):

$\begin{matrix} R_{u} \leq & \frac{K (1 - p)}{(K - 1)} [1 - {(1 - p)}^{K - 1} - \frac{2 / p}{K - 2} (1 - {(1 - p)}^{K} - K p {(1 - p)}^{K - 1})] . \end{matrix}$

(25)

Proof.

See the proof in Appendix C. □

Recall that the transmission delay achieved by the decentralized scheme without D2D communication [2] is equal to

R_{s}

given in (19). We define the ratio between

T_{decentral}

and

R_{s}

as decentralized cooperation gain:

\begin{matrix} G_{decentral,c} ≜ max {\frac{R_{\emptyset}}{R_{s}}, \frac{R_{u}}{R_{s} + R_{u} - R_{\emptyset}}}, \end{matrix}

(26)

with

G_{decentral,c} \in [0, 1]

because of

R_{\emptyset} \leq R_{s}

. Similar to the centralized scenario, this gain arises from the coordination between users in the D2D network. Moreover, we also compare

T_{decentral}

with the transmission delay

(1 - p) / p

, achieved by the D2D decentralized coded caching scheme [35], and define the ratio between

R_{s}

and

(1 - p) / p

as decentralized parallel gain:

\begin{matrix} G_{decentral,p} ≜ G_{decentral,c} \cdot (1 - {(1 - p)}^{K}), \end{matrix}

(27)

where

G_{decentral,p} \in [0, 1]

arises from the parallel transmission between the server and the users.

We plot the decentralized cooperation gain and parallel gain for the two types of D2D networks in Figure 4 when

N = 20

and

K = 10

. It can be seen that

G_{decentral,c}

and

G_{decentral,p}

in general are not monotonic functions of M. Here

G_{decentral,c}

performs in a way similar to

G_{central,c}

. When M is small, the function

G_{decentral,c}

is monotonically decreasing from value 1 until reaching the minimum. For larger M, the function

G_{decentral,c}

turns to monotonically increase with M. The reason for this phenomenon is that in the decentralized scenario, when M increases, the proportion of subfiles that are not cached by any user and must be sent by the server is decreasing. Thus, there are more subfiles that can be sent parallelly via D2D network as M increases. Meanwhile, the decentralized scheme in [2] offers an additional multicasting gain. Therefore, we need to balance these two gains to reduce the transmission delay.

The function

G_{decentral,p}

behaves differently as it monotonically increases when M is small. After reaching the maximal value, the function

G_{decentral,p}

decreases monotonically until meeting the local minimum (The abnormal bend in parallel gain when

α_{max} = ⌊ \frac{K}{2} ⌋

comes from a balance effect between the

G_{decentral,c}

and

1 - {(1 - p)}^{K}

in (27)), then

G_{decentral,p}

turns to be a monotonic increasing function for large M. Similar to the centralized case, as M increases, the impact of parallel transmission among the server and users becomes smaller since more data can be transmitted by the users.

Theorem 5.

Define

p ≜ M / N

and

p_{th} ≜ 1 - {(\frac{1}{K + 1})}^{\frac{1}{K - 1}}

, which tends to 0 as K tends to infinity. For memory size

0 \leq M \leq N

if $α_{\max} = 1$ (shared link), then

$\frac{T_{decentral}}{T^{*}} \leq 24;$
if $α_{\max} = ⌊ \frac{K}{2} ⌋$ , then

$\begin{matrix} \frac{T_{decentral}}{T^{*}} \leq \{\begin{matrix} max \{6, 2 K {(\frac{2 K}{2 K + 1})}^{K - 1}\}, & p < p_{th}, \\ 6, & p \geq p_{th} . \end{matrix} \end{matrix}$

Proof.

See the proof in Appendix D. □

Figure 5 plots the lower bound in (9) and upper bounds achieved by various decentralized coded caching schemes, including our scheme, the scheme Maddah-Ali 2015 in [2] which considers the case without D2D communication, and the scheme Ji 2016 in [35] which considers the case without server.

4. Coding Scheme under Centralized Data Placement

In this section, we describe a novel centralized coded caching scheme for arbitrary K, N and M such that

t = K M / N

is a positive integer. The scheme can be extended to the general case

1 \leq t \leq K

by following the same approach as in [1].

We first use an illustrative example to show how we form D2D communication groups, split files and deliver data, and then present our generalized centralized coding caching scheme.

4.1. An Illustrative Example

Consider a network consisting of

K = 6

users with cache size

M = 4

, and a library of

N = 6

files. Thus,

t = K M / N = 4

. Divide all six users into two groups of equal size, and choose an integer

L_{1} = 2

that guarantees

\frac{K (\binom{K - 1}{t}) L_{1}}{min {α (⌊ K / α ⌋ - 1), t}}

to be an integer. (According to (11) and (29), one optimal choice could be (

α = 1

L_{1} = 4

λ = 5 / 9

), here we choose (

α = 2

L_{1} = 2

λ = 1 / 3

) for simplicity, and also in order to demonstrate that even with a suboptimal choice, our scheme still outperforms that in [1,35]). Split each file

W_{n}

, for

n = 1, \dots, N

, into

3 (\binom{6}{4}) = 45

subfiles:

W_{n} = (W_{n, T}^{l} : l \in [3], T \subset [6], | T | = 4) .

We list all the requested subfiles uncached by all users as follows: for

l = 1, 2, 3

\begin{matrix} W_{d_{1}, {2, 3, 4, 5}}^{l}, W_{d_{1}, {2, 3, 4, 6}}^{l}, W_{d_{1}, {2, 3, 5, 6}}^{l}, W_{d_{1}, {2, 4, 5, 6}}^{l}, W_{d_{1}, {3, 4, 5, 6}}^{l}; \\ W_{d_{2}, {1, 3, 4, 5}}^{l}, W_{d_{2}, {1, 3, 4, 6}}^{l}, W_{d_{2}, {1, 3, 5, 6}}^{l}, W_{d_{2}, {1, 4, 5, 6}}^{l}, W_{d_{2}, {3, 4, 5, 6}}^{l}; \\ W_{d_{3}, {1, 2, 4, 5}}^{l}, W_{d_{3}, {1, 2, 4, 6}}^{l}, W_{d_{3}, {1, 2, 5, 6}}^{l}, W_{d_{3}, {1, 4, 5, 6}}^{l}, W_{d_{3}, {2, 4, 5, 6}}^{l}; \\ W_{d_{4}, {1, 2, 3, 5}}^{l}, W_{d_{4}, {1, 2, 3, 6}}^{l}, W_{d_{4}, {1, 2, 5, 6}}^{l}, W_{d_{4}, {1, 3, 5, 6}}^{l}, W_{d_{4}, {2, 3, 5, 6}}^{l}; \\ W_{d_{5}, {1, 2, 3, 4}}^{l}, W_{d_{5}, {1, 2, 3, 6}}^{l}, W_{d_{5}, {1, 2, 4, 6}}^{l}, W_{d_{5}, {1, 3, 4, 6}}^{l}, W_{d_{5}, {2, 3, 4, 6}}^{l}; \\ W_{d_{6}, {1, 2, 3, 4}}^{l}, W_{d_{6}, {1, 2, 3, 5}}^{l}, W_{d_{6}, {1, 2, 4, 5}}^{l}, W_{d_{6}, {1, 3, 4, 5}}^{l}, W_{d_{6}, {2, 3, 4, 5}}^{l} . \end{matrix}

The users can finish the transmission in different partitions. Table 1 shows the transmission in four different partitions over the D2D network.

In Table 1, all users first send XOR symbols with superscript

l = 1

. Please note that the subfiles

W_{d_{2}, {1, 3, 4, 5}}^{1}

and

W_{d_{5}, {1, 2, 4, 6}}^{1}

are not delivered at the beginning since

\frac{K (\binom{K - 1}{t})}{α (⌊ K / α ⌋ - 1)}

is not an integer. Similarly, for subfiles with

l = 2

W_{d_{3}, {1, 2, 5, 6}}^{2}

and

W_{d_{4}, {2, 3, 5, 6}}^{2}

remain to be sent to user 3 and 4. In the last transmission, user 1 delivers the XOR message

W_{d_{3}, {1, 2, 5, 6}}^{2} \oplus W_{d_{2}, {1, 3, 4, 5}}^{1}

to user 2 and 3, and user 6 multicasts

W_{d_{5}, {1, 2, 4, 6}}^{1} \oplus W_{d_{4}, {2, 3, 5, 6}}^{2}

to user 5 and 6. The transmission rate in the D2D network is

R_{2} = \frac{1}{3} .

For the remaining subfiles with superscript

l = 3

, the server delivers them in the same way as in [1]. Specifically, it sends symbols

\oplus_{k \in S} W_{d_{k}, S ∖ {k}}^{3}

, for all

S \subseteq [K] : | S | = 5

. Thus, the rate sent by the server is

R_{1} = \frac{2}{15}

, and the transmission delay

T_{central} = max {R_{1}, R_{2}} = \frac{1}{3}

, which is less than the delay achieved by the coded caching schemes for the broadcast network [1] and the D2D communication [35], respectively.

4.2. The Generalized Centralized Coding Caching Scheme

In the placement phase, each file is first split into

(\binom{K}{t})

subfiles of equal size. More specifically, split

W_{n}

into subfiles as follows:

W_{n} = (W_{n, T} : T \subset [K], | T | = t)

. User k caches all the subfiles if

k \in T

for all

n = 1, . . ., N

, occupying the cache memory of

M F

bits. Then split each subfile

W_{n, T}

into two mini-files as

W_{n, T} = (W_{n, T}^{s}, W_{n, T}^{u})

, where

\begin{matrix} | W_{n, T}^{s} | = λ \cdot | W_{n, T} | = λ \cdot \frac{F}{(\binom{K}{t})}, \\ | W_{n, T}^{u} | = (1 - λ) \cdot | W_{n, T} | = (1 - λ) \cdot \frac{F}{(\binom{K}{t})}, \end{matrix}

(28)

with

\begin{matrix} λ = \frac{1 + t}{α min {⌊ \frac{K}{α} ⌋ - 1, t} + 1 + t} . \end{matrix}

(29)

Here, the mini-file

W_{n, T}^{s}

and

W_{n, T}^{u}

will be sent by the server and users, respectively. For each mini-file

W_{n, T}^{u}

, split it into

L_{1}

pico-files of equal size

(1 - λ) \cdot \frac{F}{L_{1} (\binom{K}{t})}

, i.e.,

W_{n, T}^{u} = (W_{n, T}^{u, 1}, \dots, W_{n, T}^{u, L_{1}}),

where

L_{1}

satisfies

\begin{matrix} \frac{K \cdot (\binom{K - 1}{t}) \cdot L_{1}}{α min {⌊ \frac{K}{α} ⌋ - 1, t}} \in Z^{+} . \end{matrix}

(30)

As we will see later, condition (29) ensures that communication loads can be optimally allocated between the server and the users, and (30) ensures that the number of subfiles is large enough to maximize multicast gain for the transmission in the D2D network.

In the delivery phase, each user k requests file

W_{d_{k}}

. The request vector

d = (d_{1}, d_{2}, \dots, d_{K})

is informed by the server and all users. Please note that different parts of file

W_{d_{k}}

have been stored in the user cache memories, and thus the uncached parts of

W_{d_{k}}

can be sent both by the server and users. Subfiles

(W_{d_{k}, T}^{u, 1}, \dots, W_{d_{k}, T}^{u, L_{1}} : T \subset [K], | T | = t, k \notin T)

are requested by user k and will be sent by the users via the D2D network. Subfiles

(W_{d_{k}, T}^{s} : T \subset [K], | T | = t, k \notin T)

are requested by user k and will be sent by the server via the broadcast network.

First consider the subfiles sent by the users. Partition the K users into

α

groups of equal size:

G_{1}, \dots, G_{α},

where for

i, j = 1, \dots, α

G_{i} \subseteq [K] : | G_{i} | = ⌊ K / α ⌋

, and

G_{i} \cap G_{j} = \emptyset

, if

i \neq j

. In each group

G_{i}

, one of

⌊ K / α ⌋

users plays the role of server and sends symbols based on its cached contents to the remaining

(⌊ K / α ⌋ - 1)

users within the group.

Focus on a group

G_{i}

and a set

S \subset [K] : | S | = t + 1

. If

G_{i} \subseteq S

, then all nodes in

G_{i}

share subfiles

(W_{n, T}^{u, l} : l \in [L_{1}], n \in [N], G_{i} \subseteq T, | T | = t) .

In this case, user

k \in G_{i}

sends XOR symbols that contains the requested subfiles useful to all remaining

⌊ K / α ⌋ - 1

users in

G_{i}

, i.e.,

\oplus_{j \in G_{i} ∖ {k}} W_{d_{j}, S ∖ {j}}^{u, l (k, G_{i}, S)},

where

l (k, G_{i}, S) \in [L_{1}]

is a function of

(k, G_{i}, S)

which avoids redundant transmission of any fragments.

S \subseteq G_{i}

, then the nodes in

S

share subfiles

(W_{n, T}^{u, l} : l \in [L_{1}], n \in [N], T \subset S, | T | = t) .

In this case, user

k \in S

sends an XOR symbol that contains the requested subfiles for all remaining

t - 1

users in

S

, i.e.,

\oplus_{j \in S ∖ {k}} W_{d_{j}, S ∖ {j}}^{u, l (k, G_{i}, S)}

. Other groups perform the similar steps and concurrently deliver the remaining requested subfiles to other users.

By changing group partition and performing the delivery strategy described above, we can send all the requested subfiles

\begin{matrix} (W_{d_{k}, T}^{u, 1}, \dots, W_{d_{k}, T}^{u, L_{1}} {: T \subset [K], | T | = t, k \notin T)}_{k = 1}^{K} \end{matrix}

(31)

to the users.

Since

α

groups send signals in a parallel manner (

α

users can concurrently deliver contents), and each user in a group delivers a symbol containing

min {⌊ K / α ⌋ - 1, t}

non-repeating pico-files requested by other users, in order to send all requested subfiles in (31), we need to send in total

\begin{matrix} \frac{K \cdot (\binom{K - 1}{t}) \cdot L_{1}}{α min {⌊ \frac{K}{α} ⌋ - 1, t}} \end{matrix}

(32)

XOR symbols, each of size

\frac{1 - λ}{(\binom{K}{t})} F

bits. Notice that

L_{1}

is chosen according to (30), ensuring that (32) equals to an integer. Thus, we obtain

R_{2}

\begin{matrix} R_{2} & = \frac{K L_{1} \cdot (\binom{K - 1}{t})}{α min {⌊ \frac{K}{α} ⌋ - 1, t}} \cdot \frac{1 - λ}{L_{1} (\binom{K}{t})} \\ = K (1 - \frac{M}{N}) \frac{1}{1 + t + α min {⌊ \frac{K}{α} ⌋ - 1, t}}, \end{matrix}

(33)

where the last equality holds by (29).

Now consider the delivery of the subfiles sent by the server. Apply the delivery strategy as in [1], i.e., the server broadcasts

\oplus_{k \in S} W_{d_{k}, S ∖ {k}}^{s}

to all users, for all

S \subseteq [K] : | S | = t + 1

. We obtain the transmission rate of the server

\begin{matrix} R_{1} = & λ \cdot K (1 - \frac{M}{N}) \cdot \frac{1}{1 + t} \\ = & K (1 - \frac{M}{N}) \frac{1}{1 + t + α min {⌊ \frac{K}{α} ⌋ - 1, t}} . \end{matrix}

(34)

From (33) and (34), we can see that the choice

λ

in (29) guarantees equal communication loads at the server and users. Since the server and users transmit the signals simultaneously, the transmission delay of the whole network is the maximum between

R_{1}

and

R_{2}

, i.e.,

T_{central} = max {R_{1}, R_{2}} = \frac{K (1 - M / N)}{1 + t + α min {⌊ K / α ⌋ - 1, t}}

, for some

α \in [α_{max}]

5. Coding Scheme under Decentralized Data Placement

In this section, we present a novel decentralized coded caching scheme for joint broadcast network and D2D network. The decentralized scenario is much more complicated than the centralized scenario, since each subfile can be stored by

s = 1, 2, \dots, K

users, leading to a dynamic file-splitting and communication strategy in the D2D network. We first use an illustrative example to demonstrate how we form D2D communication groups, split data and deliver data, and then present our generalized coding caching scheme.

5.1. An Illustrative Example

Consider a joint broadcast and D2D network consisting of

K = 7

users. When using the decentralized data placement strategy, the subfiles cached by user k can be written as

\begin{matrix} (W_{n, T} : n \in [N], k \in T, T \subseteq [7]) . \end{matrix}

(35)

We focus on the delivery of subfiles

W_{n, T} : n \in [N], k \in T, | T | = s = 4

, i.e., each subfile is stored by

s = 4

users. A similar process can be applied to deliver other subfiles with respect to

s \in [K] ∖ {4}

To allocate communication loads between the server and users, we divide each subfile into two mini-files

W_{n, T} = (W_{n, T}^{s}, W_{n, T}^{u})

, where mini-files

{W_{n, T}^{s}}

and

{W_{n, T}^{u}}

will be sent by the server and users, respectively. To reduce the transmission delay, the size of

W_{n, T}^{s}

and

W_{n, T}^{u}

need to be chosen properly such that

R_{1} = R_{2}

, i.e., the transmission rate of the server and users are equal; see (37) and (39) ahead.

Divide all the users into two non-intersecting groups

(G_{1}^{r}, G_{2}^{r})

, for

r \in [35]

which satisfies

G_{1}^{r} \subset [K], G_{2}^{r} \subset [K], | G_{1}^{r} | = 4, | G_{2}^{r} | = 3, G_{1}^{r} \cap G_{2}^{r} = \emptyset .

There are

(\binom{7}{4}) = 35

kinds of partitions in total, thus

r \in [35]

. Please note that for any user

k \in G_{i}^{r}

| G_{i}^{r} | - 1

of its requested mini-files are already cached by the rest users in

G_{i}^{r}

, for

i = 1, 2

To avoid repetitive transmission of any mini-file, each mini-file in

(W_{d_{k}, T ∖ {k}}^{u} : T \subseteq [7], k \in [7])

is divided into non-overlapping pico-files

W_{d_{k}, T ∖ {k}}^{u_{1}}

and

W_{d_{k}, T ∖ {k}}^{u_{2}}

, i.e.,

\begin{matrix} W_{d_{k}, T ∖ {k}}^{u} = (W_{d_{k}, T ∖ {k}}^{u_{1}}, W_{d_{k}, T ∖ {k}}^{u_{2}}) . \end{matrix}

The sizes of

W_{n, T}^{u_{1}}

and

W_{n, T}^{u_{2}}

need to be chosen properly to have equal transmission rate of group

G_{1}^{r}

and

G_{2}^{r}

; see (51) and (52) ahead.

To allocate communication loads between the two different types of groups, split each

W_{d_{k}, T ∖ {k}}^{u_{1}}

and

W_{d_{k}, T ∖ {k}}^{u_{2}}

into 3 and two equal fragments, respectively, e.g.,

\begin{matrix} W_{d_{2}, {1, 3, 4}}^{u_{1}} = (W_{d_{2}, {1, 3, 4}}^{u_{1}, 1}, W_{d_{2}, {1, 3, 4}}^{u_{1}, 2}, W_{d_{2}, {1, 3, 4}}^{u_{1}, 3}), \\ W_{d_{2}, {1, 3, 4}}^{u_{2}} = (W_{d_{2}, {1, 3, 4}}^{u_{2}, 1}, W_{d_{2}, {1, 3, 4}}^{u_{2}, 2}) . \end{matrix}

During the delivery phase, in each round, one user in each group produces and multicasts an XOR symbol to all other users in the same group, as shown in Table 2.

Please note that in this example, each group only appears one time among all partitions. However, for some other values of s, each group could appear multiple times in different partitions. For example, when

s = 2

, group

{1, 2}

appears in both partitions

{{1, 2}, {3, 4}, {5, 6, 7}}

and

{{1, 2}, {3, 5}, {4, 6, 7}}

. To reduce the transmission delay, one should balance communication loads between all groups, and between the server and users as well.

5.2. The Generalized Decentralized Coded Caching Scheme

In the placement phase, each user k applies the caching function to map a subset of

\frac{M F}{N}

bits of file

W_{n}, n = 1, . . ., N,

into its cache memory at random:

W_{n} = (W_{n, T} : T \subseteq [K]) .

The subfiles cached by user k can be written as

(W_{n, T} : n \in [N], k \in T, T \subseteq [K]) .

When the size of file F is sufficiently large, by the law of large numbers, the subfile size with high probability can be written by

\begin{matrix} | W_{n, T} | \approx p^{| T |} {(1 - p)}^{K - | T |} . \end{matrix}

(36)

The delivery procedure can be characterized into three different levels: allocating communication loads between the server and user, inner-group coding (i.e., transmission in each group) and parallel delivery among groups.

5.2.1. Allocating Communication Loads between the Server and User

To allocate communication loads between the server and users, split each subfile

W_{n, T}

, for

T \subseteq [K] : T \neq \emptyset

, into two non-overlapping mini-files

W_{n, T} = (W_{n, T}^{s}, W_{n, T}^{u}),

where

\begin{matrix} | W_{n, T}^{s} | = λ \cdot | W_{n, T} |, \\ | W_{n, T}^{u} | = (1 - λ) \cdot | W_{n, T} |, \end{matrix}

(37)

and

λ

is a design parameter whose value is determined in Remark 5.

Mini-files

(W_{d_{k}, T ∖ {k}}^{s} : k \in [K])

will be sent by the server using the decentralized coded caching scheme for the broadcast network [2], leading to the transmission delay

\begin{matrix} λ R_{s} = λ \frac{1 - M / N}{M / N} (1 - {(1 - \frac{M}{N})}^{K}), \end{matrix}

(38)

where

R_{s}

is defined in (19).

Mini-files

(W_{d_{k}, T ∖ {k}}^{u} : k \in [K])

will be sent by users using parallel user delivery described in Section 5.2.3. The corresponding transmission rate is

\begin{matrix} R_{2} = (1 - λ) R_{u}, \end{matrix}

(39)

where

R_{u}

represents the transmission bits sent by each user normalized by F.

Since subfile

W_{d_{k}, \emptyset}

is not cached by any user and must be sent exclusively from the server, the corresponding transmission delay for sending

(W_{d_{k}, \emptyset} : k \in [K])

\begin{matrix} R_{\emptyset} = K {(1 - \frac{M}{N})}^{K}, \end{matrix}

(40)

where

R_{\emptyset}

coincides with the definition in (18).

By (38)–(40), we have

\begin{matrix} R_{1} = R_{\emptyset} + λ R_{s}, R_{2} = (1 - λ) R_{u} . \end{matrix}

(41)

According to (8), we have

T_{decentral} = max {R_{1}, R_{2}}

Remark 5

(Choice of

λ

).The parameter λ is chosen such that

T_{decentral}

is minimized. If

R_{u} < R_{\emptyset}

, then the inequality

R_{2} \leq R_{1}

always holds and

T_{decentral}

reaches the minimum

T_{decentral} = R_{\emptyset}

with

λ = 0

. If

R_{u} \geq R_{\emptyset}

, solving

R_{1} = R_{2}

yields

λ = \frac{R_{u} - R_{\emptyset}}{R_{s} + R_{u}}

and

T_{decentral} = \frac{R_{s} R_{u}}{R_{s} + R_{u} - R_{\emptyset}} .

5.2.2. Inner-Group Coding

Given parameters

(s, G, i, γ)

where

s \in [K - 1]

G \subseteq [K]

i \in {u, u_{1}, u_{2}}

with indicators

u, u_{1}, u_{2}

described in (37) and (51), and

γ \in Z^{+}

, we present how to successfully deliver

(W_{d_{k}, S ∖ {k}}^{i} : \forall S \subseteq [K], | S | = s, G \subseteq S)

to every user

k \in G

via D2D communication.

Split each

W_{d_{k}, S ∖ {k}}^{i}

into

(| G | - 1) γ

non-overlapping fragments of equal size, i.e.,

\begin{matrix} W_{d_{k}, S ∖ {k}}^{i} = (W_{d_{k}, S ∖ {k}}^{i, l} : l \in [(| G | - 1) γ]), \end{matrix}

(42)

and each user

k \in G

takes turn to broadcast XOR symbol

\begin{matrix} X_{k, G, s}^{i} ≜ \oplus_{j \in G ∖ {k}} W_{d_{j}, S ∖ {j}}^{i, l (j, G, S)}, \end{matrix}

(43)

where

l (k, G, S) \in [(| G | - 1) γ]

is a function of

(k, G, S)

which avoids redundant transmission of any fragments. The XOR symbol

X_{k, G, s}^{i}

will be received and decoded by the remaining users in

G

For each group

G

, inner-group coding encodes in total

(\binom{K - | G |}{s - | G |})

W_{d_{k}, S ∖ {k}}^{i}

, and each XOR symbol

X_{k, G, s}^{i}

in (43) contains fragments required by

| G | - 1

users in

G

5.2.3. Parallel Delivery among Groups

The parallel user delivery consists of

(K - 1)

rounds characterized by

s = 2, \dots, K

. In each round s, mini-files

(W_{d_{k}, T ∖ {k}}^{u} : \forall T \subseteq [K], | T | = s, k \in [K])

are recovered through D2D communication.

The key idea is to partition K users into

⌈ \frac{K}{s} ⌉

groups for each communication round

s \in {2, . . ., K}

, and let each group perform the D2D coded caching scheme [35] to exchange information. If

(K \mod s) \neq 0

, there will be

⌊ \frac{K}{s} ⌋

numbers of groups of the same size s, and an abnormal group of size

(K \mod s)

, leading to an asymmetric caching setup. We optimally allocate the communication loads between the two types of groups, and between the broadcast network and D2D network as well.

Based on K, s and

α_{max}

, the delivery strategy in the D2D network is divided into 3 cases:

Case 1: $⌈ \frac{K}{s} ⌉ > α_{max}$ . In this case, $α_{max}$ users are allowed to send data simultaneously. Select $s \cdot α_{max}$ users from all users and divide them into $α_{max}$ groups of equal size s. The total number of such kinds of partition is

$\begin{matrix} β_{1} ≜ \frac{(\binom{K}{s}) (\binom{K - s}{s}) \dots (\binom{K - s (α_{max} - 1)}{s})}{α_{max}!} . \end{matrix}$

(44)

In each partition, $α_{max}$ users, selected from $α_{max}$ groups, respectively, send data in parallel via the D2D network.
Case 2: $⌈ \frac{K}{s} ⌉ \leq α_{max}$ and $(K \mod s) < 2$ . In this case, choose $(⌊ \frac{K}{s} ⌋ - 1) s$ users from all users and partition them into $(⌊ \frac{K}{s} ⌋ - 1)$ groups of equal size s. The total number of such kind partition is

$\begin{matrix} β_{2} ≜ \frac{(\binom{K}{s}) (\binom{K - s}{s}) \dots (\binom{K - s (⌊ \frac{K}{s} ⌋ - 1)}{s})}{⌊ \frac{K}{s} ⌋!} . \end{matrix}$

(45)

In each partition, $(⌊ \frac{K}{s} ⌋ - 1)$ users selected from $(⌊ \frac{K}{s} ⌋ - 1)$ groups of equal size s, respectively, together with an extra user selected from the abnormal group of size $K - s (⌊ \frac{K}{s} ⌋ - 1)$ send data in parallel via the D2D network.
Case 3: $⌈ \frac{K}{s} ⌉ \leq α_{max}$ and $(K \mod s) \geq 2$ . In this case, every s users form a group, resulting in $⌊ \frac{K}{s} ⌋$ groups consisting of $s ⌊ \frac{K}{s} ⌋$ users. The remaining $(K \mod s)$ users form an abnormal group. The total number of such kind of partition is

$\begin{matrix} β_{3} = β_{2} . \end{matrix}$

(46)

In each partition, $⌊ \frac{K}{s} ⌋$ users selected from $⌊ \frac{K}{s} ⌋$ groups of equal size s, respectively, together with an extra user selected from the abnormal group of size $(K \mod s)$ send data in parallel via the D2D network.

Thus, the exact number of users who parallelly send signals can be written as follows:

α_{D} = \{\begin{matrix} α_{max}, & case 1, \\ ⌊ \frac{K}{s} ⌋, & case 2, \\ ⌈ \frac{K}{s} ⌉, & case 3 . \end{matrix}

(47)

Please note that each group

G

re-appears

\begin{matrix} N_{G} ≜ \frac{(\binom{K - s}{s}) \dots (\binom{K - s \cdot (α_{D} - 1)}{s})}{(α_{D} - 1)!} \end{matrix}

(48)

times among

[β_{c}]

partitions.

Now we present the decentralized scheme for these three cases as follows.

Case 1 (

⌈ \frac{K}{s} ⌉ > α_{max}

): Consider a partition

r \in [β_{1}]

, denoted by

G_{1}^{r}, \dots, G_{α_{D}}^{r},

where

| G_{i}^{r} | = s

and

G_{i}^{r} \cap G_{j}^{r} = \emptyset

\forall i, j \in [α_{D}]

and

i \neq j

Since each group

G_{i}^{r}

re-appears

N_{G_{i}^{r}}

times among

[β_{1}]

partitions, and

(| G_{i}^{r} | - 1)

users take turns to broadcast XOR symbols (43) in each group

G_{i}^{r}

, in order to guarantee that each group can send a unique fragment without repetition, we split each mini-file

W_{d_{k}, S ∖ {k}}^{u}

into

(| G_{i}^{r} | - 1) N_{G_{i}^{r}}

fragments of equal size.

Each group

G_{i}^{r}

, for

r \in [β_{1}]

and

i \in [α_{D}]

, performs inner-group coding (see Section 5.2.2) with parameters

(s, G_{i}^{r}, u, N_{G_{i}^{r}}),

for all s satisfying

⌈ \frac{K}{s} ⌉ > α_{max}

. For each round r, all groups

G_{1}^{r}, \dots, G_{α_{D}}^{r}

parallelly send XOR symbols containing

| G_{i}^{r} | - 1

fragments required by other users of its group. By the fact that the partitioned groups traverse every set

T

, i.e.,

T \subseteq {G_{1}^{r} \cup \dots \cup G_{α_{D}}^{r}}_{r = 1}^{β_{1}}, \forall T \subseteq [K] : | T | = s,

and since inner-group coding enables each group

G_{i}^{r}

to recover

(W_{d_{k}, S ∖ {k}}^{u} : \forall S \subseteq [K], | S | = s, G_{i}^{r} \subseteq S, k \in [K]),

we can recover all required mini-files

(W_{d_{k}, T ∖ {k}}^{u} : \forall T \subseteq [K], | T | = s, k \in [K]) .

The transmission delay of Case 1 in round s is thus

\begin{matrix} R_{case 1}^{u} (s) & ≜ \sum_{r \in [β_{1}]} \sum_{k \in G_{i}^{r}} | X_{k, G_{i}^{r}, s}^{u} | \\ \overset{(a)}{=} \frac{K (\binom{K - 1}{s - 1})}{α_{D} (s - 1)} | W_{d_{k}, T ∖ {k}}^{u} | \\ = \frac{K (\binom{K - 1}{s - 1})}{α_{max} (s - 1)} (1 - λ) p^{s - 1} {(1 - p)}^{K - s + 1}, \end{matrix}

(49)

where (a) follows by (44) and (48).

Case 2 (

⌈ \frac{K}{s} ⌉ \leq α_{max}

and

(K \mod s) < 2

): We apply the same delivery procedure as Case 1, except that

β_{1}

is replaced by

β_{2}

and

α_{D} = ⌊ \frac{K}{s} ⌋

. Thus, the transmission delay in round s is

\begin{matrix} R_{case 2}^{u} (s) & = \frac{K (\binom{K - 1}{s - 1})}{α_{D} (s - 1)} | W_{d_{k}, T ∖ {k}}^{u} | \\ = \frac{K (\binom{K - 1}{s - 1})}{⌊ \frac{K}{s} ⌋ (s - 1)} (1 - λ) p^{s - 1} {(1 - p)}^{K - s + 1} . \end{matrix}

(50)

Case 3 (

⌈ \frac{K}{s} ⌉ \leq α_{max}

and

(K \mod s) \geq 2

): Consider a partition

r \in [β_{3}]

, denoted as

G_{1}^{r}, \dots, G_{α_{D}}^{r},

where

G_{i}^{r} \subseteq [K]

G_{i}^{r} \cap G_{j}^{r} = \emptyset

\forall i, j \in [α_{D} - 1]

and

i \neq j

and

G_{α_{D}}^{r} = [K] ∖ (\cup_{i = 1}^{α_{D} - 1} G_{i}^{r})

with

| G_{i}^{r} | = s, | G_{α_{D}}^{r} | = (K \mod s) .

Since group

G_{i}^{r} : i \in [α_{D} - 1]

and

G_{α_{D}}^{r}

have different group sizes, we further split each mini-file

W_{d_{k}, T ∖ {k}}^{u}

into two non-overlapping fragments such that

\begin{matrix} | W_{d_{k}, T ∖ {k}}^{u_{1}} | = λ_{2} | W_{d_{k}, T ∖ {k}}^{u} |, \\ | W_{d_{k}, T ∖ {k}}^{u_{2}} | = (1 - λ_{2}) | W_{d_{k}, T ∖ {k}}^{u} |, \end{matrix}

(51)

where

λ_{2} \in [0, 1]

is a designed parameter satisfying (52).

Split each mini-file

W_{d_{k}, S ∖ {k}}^{u_{1}}

and

W_{d_{k}, S ∖ {k}}^{u_{2}}

into fragments of equal size:

\begin{matrix} W_{d_{k}, S ∖ {k}}^{u_{1}} = & (W_{d_{k}, S ∖ {k}}^{u_{1}, l} : l \in [(s - 1) N_{G_{i}^{r}}]), \\ W_{d_{k}, S ∖ {k}}^{u_{2}} = & (W_{d_{k}, S ∖ {k}}^{u_{2}, l} : l \in [(| G_{α_{D}}^{r} | - 1) (\binom{s - 1}{| G_{α_{D}}^{r} | - 1}) N_{G_{i}^{r}}]) . \end{matrix}

Following the similar encoding operation in (43), group

G_{i}^{r} : i \in [α_{D} - 1]

and group

G_{α_{D}}^{r}

send the following XOR symbols, respectively:

\begin{matrix} {(X_{k, G_{i}^{r}, s}^{u_{1}} : k \in G_{i}^{r})}_{i = 1}^{(α_{D} - 1)}, (X_{k, G_{α_{D}}^{r}, s}^{u_{2}} : k \in G_{α_{D}}^{r}) . \end{matrix}

For each

s \in {2, \dots, K}

, the transmission delay for sending the XOR symbols above by group

G_{i}^{r} : i \in [α_{D} - 1]

and group

G_{⌈ \frac{K}{s} ⌉}^{r}

can be written as

\begin{matrix} R_{case 3}^{u_{1}} (s) = \frac{λ_{2} K (\binom{K - 1}{s - 1})}{(α_{D} - 1) (s - 1)} \cdot | W_{d_{k}, T ∖ {k}}^{u} |, \\ R_{case 3}^{u_{2}} (s) = \frac{(1 - λ_{2}) K (\binom{K - 1}{s - 1})}{(K \mod s) - 1} \cdot | W_{d_{k}, T ∖ {k}}^{u} |, \end{matrix}

respectively. Since

G_{i} : i \in [⌊ \frac{K}{s} ⌋]

and group

G_{⌈ \frac{K}{s} ⌉}

can send signals in parallel, by letting

\begin{matrix} R_{case 3}^{u_{1}} (s) = R_{case 3}^{u_{2}} (s), \end{matrix}

(52)

we eliminate the parameter

λ_{2}

and obtain the balanced transmission delay at users for Case 3:

\begin{matrix} R_{case 3}^{u} (s) ≜ \frac{K (\binom{K - 1}{s - 1})}{K - 1 - ⌊ \frac{K}{s} ⌋} (1 - λ) p^{s - 1} {(1 - p)}^{K - s + 1} . \end{matrix}

(53)

Remark 6.

The condition

⌈ \frac{K}{s} ⌉ > α_{max}

in Case 1 implies that

s \leq ⌈ \frac{K}{α_{max}} ⌉ - 1

. In this regime, the transmission delay is given in (49). If

s \geq ⌈ \frac{K}{α_{max}} ⌉ - 1

and

(K mod s) < 2

, scheme for Case 2 starts to work and the transmission delay is given in (50); If

s \geq ⌈ \frac{K}{α_{max}} ⌉ - 1

and

(K mod s) \geq 2

, scheme for Case 3 starts to work and the transmission delay is given in (53).

In each round

s \in {2, \dots, K}

, all requested mini-files can be recovered by the delivery strategies above. By Remark 6, the transmission delay in the D2D network is

\begin{matrix} R_{2} & = (1 - λ) \frac{1}{α_{\max}} \sum_{s = 2}^{⌈ \frac{K}{α_{\max}} ⌉ - 1} [\frac{s (\binom{K}{s})}{s - 1} p^{s - 1} {(1 - p)}^{K - s + 1}] + (1 - λ) \sum_{s = ⌈ \frac{K}{α_{\max}} ⌉}^{K} [\frac{K (\binom{K - 1}{s - 1})}{f (K, s)} p^{s - 1} {(1 - p)}^{K - s + 1}] \\ = (1 - λ) R_{u}, \end{matrix}

(54)

where

R_{u}

is defined in (20) and

\begin{matrix} f (K, s) ≜ \{\begin{matrix} ⌊ \frac{K}{s} ⌋ (s - 1), & (K m o d s) < 2, \\ K - 1 - ⌊ K / s ⌋, & (K m o d s) \geq 2 . \end{matrix} \end{matrix}

(55)

6. Conclusions

In this paper, we considered a cache-aided communication via joint broadcast network with a D2D network. Two novel coded caching schemes were proposed for centralized and decentralized data placement settings, respectively. Both schemes achieve a parallel gain and a cooperation gain by efficiently exploiting communication opportunities in the broadcast and D2D networks, and optimally allocating communication loads between the server and users. Furthermore, we showed that in the centralized case, letting too many users parallelly send information could be harmful. The information theoretic converse bounds were established, with which we proved that the centralized scheme achieves the optimal transmission delay within a constant multiplicative gap in all regimes, and the decentralized scheme is also order-optimal when the cache size of each user is larger than a small threshold which tends to zero as the number of users tends to infinity. Our work indicates that combining the cache-aided broadcast network with the cache-aided D2D network can greatly reduce the transmission latency.

Author Contributions

Project administration, Y.W.; Writing—original draft, Z.H., J.C. and X.Y.; Writing—review & editing, S.M. All authors have read and agreed to the published version of the manuscript.

Funding

This research was funded by National Natural Science Foundation of China grant number 61901267.

Conflicts of Interest

The authors declare no conflict of interest.

Appendix A. Proof of the Converse

Let

T_{1}^{*}

and

T_{2}^{*}

denote the optimal rate sent by the server and each user. We first consider an enhance system where every user is served by an exclusive server and user, which both store full files in the database, then we are easy to obtain the following lower bound:

\begin{matrix} T^{*} \geq \frac{1}{2} (1 - \frac{M}{N}) . \end{matrix}

(A1)

Another lower bound follows similar idea to [1]. However, due to the flexibility of D2D network, the connection and partitioning status between users can change during the delivery phase, prohibiting the direct application of the proof in [1] into the hybrid network considered in this paper. Moreover, the parallel transmission of the server and many users creates abundant different signals in the networks, making the scenario more sophisticated.

Consider the first s users with cache contents

Z_{1}, . . ., Z_{s}

. Define

X_{1, 0}

as the signal sent by the server, and

X_{1, 1}, \dots, X_{1, α_{\max}}

as the signals sent by the

α_{\max}

users, respectively, where

X_{j, i} \in [⌊ 2^{T_{2}^{*} F} ⌋]

for

j \in [s]

and

i \in [α_{\max}]

. Assume that

W_{1}, \dots, W_{s}

are determined by

X_{1, 0}

X_{1, 1}, \dots, X_{1, α_{\max}}

and

Z_{1}, \dots, Z_{s}

. Additionally, define

X_{2, 0}

X_{2, 1}, \dots, X_{2, α_{\max}}

as the signals which enable the users to decode

W_{s + 1}, . . ., W_{2 s}

. Continue the same process such that

X_{⌊ N / s ⌋, 0}

X_{⌊ N / s ⌋, 1}, \dots, X_{⌊ N / s ⌋, α_{\max}}

are the signals which enable the users to decode

W_{s ⌊ N / s ⌋ - s + 1}, . . ., W_{s ⌊ N / s ⌋}

. We then have

Z_{1}, \dots, Z_{s}

X_{1, 0}, \dots, X_{⌊ N / s ⌋, 0}

, and

X_{1, 1}, \dots, X_{1, α_{\max}}, \dots, X_{⌊ N / s ⌋, 1}, \dots, X_{⌊ N / s ⌋, α_{\max}}

to determine

W_{1}, \dots, W_{s ⌊ N / s ⌋}

. Let

X_{1 : α_{\max}} ≜ (X_{1, 1}, \dots, X_{1, α_{\max}}, \dots, X_{⌊ N / s ⌋, 1}, \dots, X_{⌊ N / s ⌋, α_{\max}}) .

By the definitions of

T_{1}^{*}

T_{2}^{*}

and the encoding function (5), we have

\begin{matrix} H (X_{1, 0}, \dots, X_{⌊ N / s ⌋, 0}) \leq ⌊ N / s ⌋ T_{1}^{*} F, \end{matrix}

(A2)

\begin{matrix} H (X_{1 : α_{\max}}) \leq ⌊ N / s ⌋ α_{\max} T_{2}^{*} F, \end{matrix}

(A3)

\begin{matrix} H (X_{1 : α_{\max}}, Z_{1}, \dots, Z_{s}) \leq K M F . \end{matrix}

(A4)

Consider the cut separating

X_{1, 0}, \dots, X_{⌊ N / s ⌋, 0}

X_{1 : α_{\max}}

, and

Z_{1}, \dots, Z_{s}

from the corresponding s users. By the cut-set bound and (A2), we have

\begin{matrix} ⌊ \frac{N}{s} ⌋ s F & \leq ⌊ \frac{N}{s} ⌋ T_{1}^{*} F + K M F, \end{matrix}

(A5)

\begin{matrix} ⌊ \frac{N}{s} ⌋ s F & \leq ⌊ \frac{N}{s} ⌋ T_{1}^{*} F + s M F + ⌊ \frac{N}{s} ⌋ α_{\max} T_{2}^{*} F . \end{matrix}

(A6)

Since we have

T^{*} \geq T_{1}^{*}

and

T^{*} \geq max {T_{1}^{*}, T_{2}^{*}}

from the above definition, we obtain

\begin{matrix} T^{*} & \geq max_{s \in [K]} (s - \frac{K M}{⌊ N / s ⌋}), \end{matrix}

(A7)

\begin{matrix} T^{*} & \geq max_{s \in [K]} (s - \frac{s M}{⌊ N / s ⌋}) \frac{1}{1 + α_{\max}} . \end{matrix}

(A8)

Appendix B

We prove that

T_{central}

is within a constant multiplicative gap of the minimum transmission delay

T^{*}

for all values of M. To prove the result, we compare them in the following regimes.

If $0.6393 < t < ⌊ K / α ⌋ - 1$ , from Theorem 1, we have

$\begin{matrix} T^{*} & \geq (s - \frac{M s}{⌊ N / s ⌋}) \frac{1}{1 + α_{\max}} \\ \overset{(a)}{\geq} \frac{1}{12} \cdot K (1 - \frac{M}{N}) \frac{1}{1 + t} \cdot \frac{1}{1 + α_{\max}}, \end{matrix}$

(A9)

where (a) follows from [1] [Theorem 3]. Then we have

$\begin{matrix} \frac{T_{central}}{T^{*}} & \leq 12 \cdot \frac{(1 + α_{\max}) (1 + t)}{1 + t + α t} \\ = 12 \cdot \frac{(1 + α_{\max})}{1 + α t / (1 + t)} \\ \leq 12 \cdot \frac{(1 + α_{\max})}{1 + α \cdot 0.6393 / (1 + 0.6393)} \\ \leq 31, \end{matrix}$

(A10)

where the last inequality holds by setting $α = α_{\max}$ .
If $t > ⌊ K / α ⌋ - 1$ , we have

$\begin{matrix} \frac{T_{central}}{T^{*}} & \leq \frac{K (1 - \frac{M}{N}) \frac{1}{1 + t + α (⌊ K / α ⌋ - 1)}}{\frac{1}{2} (1 - \frac{M}{N})} \\ = \frac{2 K}{1 + t + α (⌊ K / α ⌋ - 1)} \\ \overset{(a)}{\leq} \frac{2 K}{K + K M / N} \\ \leq 2, \end{matrix}$

(A11)

where $(a)$ holds by choosing $α = 1$ .
If $t \leq 0.6393$ , setting $s = 0.275 N$ , we have

$\begin{matrix} T^{*} & \geq s - \frac{K M}{⌊ N / s ⌋} \\ \overset{(a)}{\geq} s - \frac{K M}{N / s - 1} \\ = 0.275 N - t \cdot 0.3793 N \\ \geq 0.0325 N > \frac{1}{31} \cdot N, \end{matrix}$

(A12)

where $(a)$ holds since $⌊ x ⌋ \geq x - 1$ for any $x \geq 1$ . Please note that for all values of M, the transmission delay

$T_{central} \leq min {K, N} .$

(A13)

Combining with (A12) and (A13), we have $\frac{T_{central}}{T^{*}} \leq 31 .$

Appendix C

Appendix C.1. Case α_max = $⌊ \frac{K}{2} ⌋$

When

α_{max} = ⌊ \frac{K}{2} ⌋

, we have

\begin{matrix} R_{u} = R_{u-f} ≜ \sum_{s = 2}^{K} \frac{K (\binom{K - 1}{s - 1})}{f (K, s)} p^{s - 1} q^{K - s + 1}, \end{matrix}

(A14)

where

R_{u-f}

denotes the user’s transmission rate for a flexible D2D network with

α_{\max} = ⌊ \frac{K}{2} ⌋

. In the flexible D2D network, at most

⌊ \frac{K}{2} ⌋

users are allowed to transmit messages simultaneously, in which the user transmission turns to unicast.

Please note that in each term of the summation:

\begin{matrix} \frac{K (\binom{K - 1}{s - 1})}{f (K, s)} & \leq \frac{K (\binom{K - 1}{s - 1})}{K - 1 - \frac{K}{s}} \\ = (\frac{K}{K - 1} + \frac{{(\frac{K}{K - 1})}^{2}}{s - \frac{K}{K - 1}}) \cdot (\binom{K - 1}{s - 1}) \\ \leq \frac{K (\binom{K - 1}{s - 1})}{K - 1} + \frac{2 K (\binom{K}{s})}{(K - 1) (K - 2)}, \end{matrix}

(A15)

where the last inequality holds by

s \geq \frac{K}{K - 1} + \frac{K - 2}{K - 1} = 2

and

\begin{matrix} \frac{{(\frac{K}{K - 1})}^{2}}{s - \frac{K}{K - 1}} (\binom{K - 1}{s - 1}) & = \frac{K^{2} (\binom{K - 1}{s - 1})}{(K - 1) (K - 2)} \cdot \frac{\frac{K - 2}{K - 1}}{s - \frac{K}{K - 1}} \\ \leq \frac{K^{2} (\binom{K - 1}{s - 1})}{(K - 1) (K - 2)} \cdot \frac{\frac{K - 2}{K - 1} + \frac{K}{K - 1}}{s - \frac{K}{K - 1} + \frac{K}{K - 1}} \\ = \frac{2 K}{(K - 1) (K - 2)} \cdot (\binom{K}{s}) . \end{matrix}

Therefore, by (A15),

R_{u-f}

can be rewritten as

\begin{matrix} R_{u-f} & \leq \frac{K}{K - 1} \sum_{s = 2}^{K} (\binom{K - 1}{s - 1}) p^{s - 1} q^{K - s + 1} + \frac{2 K}{(K - 1) (K - 2)} \sum_{s = 2}^{K} (\binom{K}{s}) p^{s - 1} q^{K - s + 1} \\ = \frac{K q}{K - 1} \cdot \sum_{i = 1}^{K - 1} (\binom{K - 1}{i}) p^{i} q^{K - 1 - i} + \frac{2 K q / p}{(K - 1) (K - 2)} \cdot \sum_{s = 2}^{K} (\binom{K}{s}) p^{s} q^{K - s} \\ = \frac{K q}{K - 1} (1 - q^{K - 1}) + \frac{2 K q / p}{(K - 1) (K - 2)} \cdot (1 - q^{K} - K p q^{K - 1}) . \end{matrix}

Appendix C.2. Case α_max =1

When

α_{max} = 1

, the cooperation network degenerates into a shared link where only one user acts as the server and broadcasts messages to the remaining

K - 1

users. A similar derivation is given in [35]. In this case,

R_{u}

can be rewritten as

\begin{matrix} R_{u} & = \sum_{s = 2}^{K} \frac{s (\binom{K}{s})}{s - 1} p^{s - 1} q^{K - s + 1} \\ \leq \sum_{s = 2}^{K} (1 + \frac{3}{s + 1}) (\binom{K}{s}) p^{s - 1} q^{K - s + 1} \\ = \sum_{s = 2}^{K} (\binom{K}{s}) p^{s - 1} q^{K - s + 1} + \frac{3}{K + 1} \sum_{s = 2}^{K} (\binom{K + 1}{s + 1}) p^{s - 1} q^{K - s + 1} \\ = \frac{q}{p} (1 - q^{K} - K p q^{K - 1}) + \frac{3 q / p^{2}}{K + 1} (1 - q^{K + 1} - (K + 1) p q^{K} - \frac{K (K + 1)}{2} p^{2} q^{K - 1}) \\ = \frac{q}{p} (1 - \frac{5}{2} K p q^{K - 1} - 4 q^{K} + \frac{3 (1 - q^{K + 1})}{(K + 1) p}), \end{matrix}

where the inequality holds by the fact that

s \geq 2

Appendix D

Appendix D.1. When α_max = $⌊ \frac{K}{2} ⌋$

Recall that

p_{th} ≜ 1 - {(\frac{1}{K + 1})}^{\frac{1}{K - 1}}

, which tends to zero as K goes to infinity. We first introduce the following three lemmas.

Lemma A1.

Given arbitrary convex function

g_{1} (p)

and arbitrary concave function

g_{2} (p)

, if they intersect at two points with

p_{1} < p_{2}

, then

g_{1} (p) \leq g_{2} (p)

for all

p \in [p_{1}, p_{2}]

We omit the proof of Lemma A1 as it is straightforward.

Lemma A2.

For memory size

0 \leq p \leq 1

and

α_{\max} = ⌊ \frac{K}{2} ⌋

, we have

R_{u} \geq R_{\emptyset}, T_{decentral} = \frac{R_{s} R_{u}}{R_{s} + R_{u} - R_{\emptyset}}, for all p \in [p_{th}, 1] .

Proof.

When

α_{max} = ⌊ \frac{K}{2} ⌋

, from Equation (20), we have

\begin{matrix} R_{u} & = \sum_{s = 2}^{K} \frac{K (\binom{K - 1}{s - 1})}{f (K, s)} p^{s - 1} {(1 - p)}^{K - s + 1} \\ \geq \frac{K}{K} \sum_{x = 1}^{K - 1} (\binom{K - 1}{x}) p^{x} {(1 - p)}^{K - x} \\ = (1 - p) (1 - {(1 - p)}^{K - 1}), \end{matrix}

(A16)

where the first inequality holds by letting

x = s - 1

and

\frac{K}{K - 1 - ⌊ \frac{K}{s} ⌋} > \frac{K}{K - 1}

. It is easy to show that

(1 - p) (1 - {(1 - p)}^{K - 1})

is a concave function of p by verifying

\frac{\partial^{2} (1 - p) (1 - {(1 - p)}^{K - 1})}{\partial p^{2}} \leq 0

. □

On the other hand, one can easily show that

R_{\emptyset} = K {(1 - p)}^{K}

is a convex function of p by showing

\frac{\partial^{2} R_{\emptyset} (p)}{\partial p^{2}} \geq 0

. Since the two functions

(1 - p) (1 - {(1 - p)}^{K - 1})

and

R_{\emptyset}

intersect at

p_{th} = 1 - {(\frac{1}{K + 1})}^{\frac{1}{K - 1}}

and

p_{2} = 1

with

p_{th} \leq p_{2}

, from Lemma A1 and (A16), we have

R_{u} \geq (1 - p) (1 - {(1 - p)}^{K - 1}) \geq R_{\emptyset},

for all

p \in [p_{th}, 1]

. From Remark 4, we know that

T_{decentral} = \frac{R_{s} R_{u}}{R_{s} + R_{u} - R_{\emptyset}}

R_{u} \geq R_{\emptyset}

Lemma A3.

For memory size

0 \leq p \leq 1

and

α_{\max} = ⌊ \frac{K}{2} ⌋

, we have

\frac{R_{s} R_{u}}{R_{s} + R_{u} - R_{\emptyset}} \leq 6 T^{*} .

Proof

From (25) and (19), we have

\begin{matrix} R_{u} & \leq \frac{K}{K - 1} \cdot (q - q^{K}) + \frac{2 K}{(K - 1) (K - 2)} \cdot \frac{q}{p} (1 - q^{K} - K p q^{K - 1}) \\ \overset{(a)}{\leq} \frac{K}{K - 1} \cdot (q - q^{K}) + \frac{2 K}{(K - 1) (K - 2)} \cdot \frac{q}{p} (1 - (1 - K p) - K p q^{K - 1}) \\ = \frac{K (3 K - 2)}{(K - 1) (K - 2)} \cdot (q - q^{K}), \end{matrix}

(A17)

\begin{matrix} R_{s} & = \frac{q}{p} (1 - q^{K}) \overset{(b)}{\leq} \frac{q}{p} (1 - (1 - K p)) = K q, \end{matrix}

(A18)

where

(a)

and

(b)

both follow from inequality

\begin{matrix} {(1 - p)}^{K} \geq (1 - K p) . \end{matrix}

(A19)

□

Then, by Remark 4 and (A17), (A18) and definition of

R_{\emptyset}

in (18), if

α_{max} = ⌊ \frac{K}{2} ⌋

, then

\begin{matrix} \frac{R_{s} R_{u}}{R_{s} + R_{u} - R_{\emptyset}} & \leq \frac{K q \cdot \frac{K (3 K - 2)}{(K - 1) (K - 2)} (q - q^{K})}{K q + \frac{K (3 K - 2)}{(K - 1) (K - 2)} (q - q^{K}) - K q^{K}} \\ = (3 - \frac{2}{K}) \cdot q . \end{matrix}

(A20)

From Theorem 1, we have

T^{*} \geq \frac{1}{2} q

. Thus, we obtain

\frac{R_{s} R_{u}}{R_{s} + R_{u} - R_{\emptyset}} \cdot \frac{1}{T^{*}} \leq \frac{(3 - 2 / K) \cdot q}{q / 2} \leq 6 - \frac{4}{K} < 6 .

Next, we use Lemmas A2 and A3 to prove that when

α_{\max} = ⌊ \frac{K}{2} ⌋

\begin{matrix} \frac{T_{decentral}}{T^{*}} \leq \{\begin{matrix} max \{6, 2 K {(\frac{2 K}{2 K + 1})}^{K - 1}\}, & p < p_{th}, \\ 6, & p \geq p_{th} . \end{matrix} \end{matrix}

Appendix D.1.1. Case α_max = $⌊ \frac{K}{2} ⌋$ and p ≥ p_th

In this case, from Lemma A2, we have

T_{decentral} = \frac{R_{s} R_{u}}{R_{s} + R_{u} - R_{\emptyset}} .

Thus, from Lemma A3,

T_{decentral} = \frac{R_{s} R_{u}}{R_{s} + R_{u} - R_{\emptyset}} \leq 6 T^{*} .

Appendix D.1.2. Case α_max = $⌊ \frac{K}{2} ⌋$ and p ≥ p_th

From the definition of

T_{decentral}

in (17), we have

\begin{matrix} \frac{T_{decentral}}{T^{*}} & = max {\frac{R_{\emptyset}}{T^{*}}, \frac{R_{s} R_{u}}{R_{s} + R_{u} - R_{\emptyset}} \cdot \frac{1}{T^{*}}} . \end{matrix}

(A21)

From Lemma A3, we know that

\begin{matrix} \frac{R_{s} R_{u}}{R_{s} + R_{u} - R_{\emptyset}} \cdot \frac{1}{T^{*}} \leq 6, \end{matrix}

(A22)

and thus only focus on the upper bound of

R_{\emptyset} / T^{*}

According to Theorem 1,

T^{*}

has the following two lower bounds:

T^{*} \geq \frac{1 - p}{2}

, and

\begin{matrix} T^{*} \geq max_{s \in [K]} (s - \frac{K M}{⌊ N / s ⌋}) \geq max_{s \in [K]} (s - \frac{K M}{N / (2 s)}) . \end{matrix}

Let

R_{1}^{*} (p) ≜ \frac{1}{2} (1 - p)

and

R_{2}^{*} (p) ≜ (K - 2 K^{2} p)

, then we have

T^{*} \geq max {R_{1}^{*} (p), R_{2}^{*} (p)} .

Here

R_{\emptyset} / R_{1}^{*} (p)

and

R_{\emptyset} / R_{2}^{*} (p)

both are monotonic functions of p according to the following properties:

\begin{matrix} \frac{\partial (R_{\emptyset} / R_{1}^{*} (p))}{\partial p} & = \frac{\partial (2 K {(1 - p)}^{K - 1})}{\partial p} \leq 0, \\ \frac{\partial (R_{\emptyset} / R_{2}^{*} (p))}{\partial p} & = \frac{\partial (q^{K} / (1 - 2 K p))}{\partial p} \\ = \frac{K q^{K - 1} (1 + 2 (K - 1) p)}{{(1 - 2 K p)}^{2}} \geq 0 . \end{matrix}

Additionally, notice that if

p = 0

, then

\frac{R_{\emptyset}}{R_{2}^{*} (p)} = 1 < \frac{R_{\emptyset}}{R_{1}^{*} (p)}

, and if

p = 1

\frac{R_{\emptyset}}{R_{2}^{*} (p)} > \frac{R_{\emptyset}}{R_{1}^{*} (p)} = 1

. Therefore, the maximum value of

R_{\emptyset} / max {R_{1}^{*}, R_{2}^{*}}

is chosen at

p = \frac{1}{2 K + 1}

which satisfying

R_{1}^{*} (\frac{1}{2 K + 1}) = R_{2}^{*} (\frac{1}{2 K + 1})

, implying that

\begin{matrix} \frac{R_{\emptyset}}{T^{*}} \leq \frac{R_{\emptyset} (\frac{1}{2 K + 1})}{R_{1}^{*} (\frac{1}{2 K + 1})} = 2 K {(\frac{2 K}{2 K + 1})}^{K - 1} . \end{matrix}

(A23)

From (A21)–(A23), we obtain the following equality:

\frac{T_{decentral}}{T^{*}} \leq max \{2 K {(\frac{2 K}{2 K + 1})}^{K - 1}, 6\} .

Appendix D.2. When α_max = 1

From Equation (24), we obtain that

\begin{matrix} R_{u} & \leq \frac{q}{p} (1 - \frac{5}{2} K p q^{K - 1} - 4 q^{K} + \frac{3 (1 - q^{K + 1})}{(K + 1) p}) \\ \leq \frac{q}{p} (1 - \frac{5}{2} K p q^{K - 1} - 4 q^{K} + \frac{3 (K + 1) p}{(K + 1) p}) \\ = \frac{q}{p} (4 \cdot (1 - q^{K}) - \frac{5}{2} K p q^{K - 1}) \\ \leq \frac{q}{p} (4 \cdot (1 - q^{K})) \\ = 4 R_{s}, \end{matrix}

(A24)

where the second inequality holds by (A19) and the last equality holds by the definition

R_{s} ≜ \frac{q}{p} (1 - q^{K})

in (19). On the other hand, rewrite the second lower bound of

T^{*}

\begin{matrix} T^{*} \geq max_{s \in [K]} (s - \frac{s M}{⌊ N / s ⌋}) \frac{1}{1 + α_{max}} . \end{matrix}

(A25)

From the result in [2] (Appendix B), we have

\begin{matrix} \frac{R_{s}}{{max}_{s \in [K]} (s - \frac{s M}{⌊ N / s ⌋})} \leq 12 . \end{matrix}

(A26)

Combining (A24)–(A26), we have

\begin{matrix} \frac{R_{s}}{T^{*}} \leq 12 (1 + α_{max}), \frac{R_{u}}{T^{*}} \leq 48 (1 + α_{max}) . \end{matrix}

(A27)

p \leq p_{th}

, by (A27) and since

R_{\emptyset} \leq T_{decentral} \leq R_{s}

(see Remark 4), we have

\begin{matrix} \frac{T_{decentral}}{T^{*}} \leq \frac{R_{s}}{T^{*}} \leq 12 (1 + α_{max}) = 24, \end{matrix}

(A28)

the last equality holds by the fact

α_{max} = 1

p \geq p_{th}

, from Lemma A2, we have

R_{u} \geq R_{\emptyset}

and

\begin{matrix} \frac{T_{decentral}}{T^{*}} & = \frac{\frac{R_{s} R_{u}}{R_{s} + R_{u} - R_{\emptyset}}}{T^{*}} \\ \leq \frac{min {R_{u}, R_{s}}}{T^{*}} \\ \leq min {12 (1 + α_{max}), 48 (1 + α_{max})} \\ = 24, \end{matrix}

(A29)

where the second inequality holds by (A27) and the last equality is from the fact

α_{max} = 1

in this case.

References

Maddah-Ali, M.A.; Niesen, U. Fundamental limits of caching. IEEE Trans. Inf. Theory 2014, 60, 2856–2867. [Google Scholar] [CrossRef]
Maddah-Ali, M.A.; Niesen, U. Decentralized coded caching attains order-optimal memory-rate tradeoff. IEEE/ACM Trans. Netw. 2015, 23, 1029–1040. [Google Scholar] [CrossRef]
Yu, Q.; Maddah-Ali, M.A.; Avestimehr, A.S. Characterizing the Rate-Memory Tradeoff in Cache Networks within a Factor of 2. IEEE Trans. Inf. Theory 2019, 65, 647–663. [Google Scholar] [CrossRef]
Wan, K.; Tuninetti, D.; Piantanida, P. On the optimality of uncoded cache placement. In Proceedings of the IEEE Information Theory Workshop (ITW), Cambridge, UK, 11–14 September 2016; pp. 161–165. [Google Scholar]
Yu, Q.; Maddah-Ali, M.A.; Avestimehr, A.S. The exact rate-memory tradeoff for caching with uncoded prefetching. IEEE Trans. Inf. Theory 2018, 64, 1281–1296. [Google Scholar] [CrossRef]
Yan, Q.; Cheng, M.; Tang, X.; Chen, Q. On the placement delivery array design for centralized coded caching scheme. IEEE Trans. Inf. Theory 2017, 63, 5821–5833. [Google Scholar] [CrossRef]
Zhang, D.; Liu, N. Coded cache placement for heterogeneous cache sizes. In Proceedings of the IEEE Information Theory Workshop (ITW), Guangzhou, China, 25–29 November 2018; pp. 1–5. [Google Scholar]
Wang, S.; Peleato, B. Coded caching with heterogeneous user profiles. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), France, Paris, 7–12 July 2019; pp. 2619–2623. [Google Scholar]
Zhang, J.; Lin, X.; Wang, C.C. Coded caching for files with distinct file sizes. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), Hong Kong, China, 14–19 June 2015; pp. 1686–1690. [Google Scholar]
Ibrahim, A.M.; Zewail, A.A.; Yener, A. Centralized coded caching with heterogeneous cache sizes. In Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), San Francisco, CA, USA, 19–22 March 2017; pp. 1–6. [Google Scholar]
Ibrahim, A.M.; Zewail, A.A.; Yener, A. Coded caching for heterogeneous systems: An Optimization Perspective. IEEE Trans. Commun. 2019, 67, 5321–5335. [Google Scholar] [CrossRef]
Amiri, M.M.; Yang, Q.; Gündüz, D. Decentralized caching and coded delivery with distinct cache capacities. IEEE Trans. Commun. 2017, 65, 4657–4669. [Google Scholar] [CrossRef]
Cao, D.; Zhang, D.; Chen, P.; Liu, N.; Kang, W.; Gündüz, D. Coded caching with asymmetric cache sizes and link qualities: The two-user case. IEEE Trans. Commun. 2019, 67, 6112–6126. [Google Scholar] [CrossRef]
Niesen, U.; Maddah-Ali, M.A. Coded caching with nonuniform demands. IEEE Trans. Inf. Theory 2017, 63, 1146–1158. [Google Scholar] [CrossRef]
Zhang, J.; Lin, X.; Wang, X. Coded caching under arbitrary popularity distributions. IEEE Trans. Inf. Theory 2018, 64, 349–366. [Google Scholar] [CrossRef]
Pedarsani, R.; Maddah-Ali, M.A.; Niesen, U. Online coded caching. IEEE/ACM Trans. Netw. 2016, 24, 836–845. [Google Scholar] [CrossRef]
Daniel, A.M.; Yu, W. Optimization of heterogeneous coded caching. IEEE Trans. Inf. Theory 2020, 66, 1893–1919. [Google Scholar] [CrossRef]
Shariatpanahi, S.P.; Motahari, S.A.; Khalaj, B.H. Multi-server coded caching. IEEE Trans. Inf. Theory 2016, 62, 7253–7271. [Google Scholar] [CrossRef]
Zhang, J.; Elia, P. Fundamental limits of cache-aided wireless BC: Interplay of coded-caching and CSIT feedback. IEEE Trans. Inf. Theory 2017, 63, 3142–3160. [Google Scholar] [CrossRef]
Bidokhti, S.S.; Wigger, M.; Timo, R. Noisy broadcast networks with receiver caching. IEEE Trans. Inf. Theory 2018, 64, 6996–7016. [Google Scholar] [CrossRef]
Sengupta, A.; Tandon, R.; Simeone, O. Cache aided wireless networks: Tradeoffs between storage and latency. In Proceedings of the 2016 Annual Conference on Information Science and Systems (CISS), Princeton, NJ, USA, 15–18 March 2016; pp. 320–325. [Google Scholar]
Tandon, R.; Simeone, O. Cloud-aided wireless networks with edge caching: Fundamental latency trade-offs in fog radio access networks. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain, 10–15 July 2016; pp. 2029–2033. [Google Scholar]
Karamchandani, N.; Niesen, U.; Maddah-Ali, M.A.; Diggavi, S.N. Hierarchical coded caching. IEEE Trans. Inf. Theory 2016, 62, 3212–3229. [Google Scholar] [CrossRef]
Wang, K.; Wu, Y.; Chen, J.; Yin, H. Reduce transmission delay for caching-aided two-layer networks. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), France, Paris, 7–12 July 2019; pp. 2019–2023. [Google Scholar]
Wan, K.; Ji, M.; Piantanida, P.; Tuninetti, D. Caching in combination networks: Novel multicast message generation and delivery by leveraging the network topology. In Proceedings of the IEEE International Conference on Communications (ICC), Kansas City, MO, USA, 20–24 May 2018; pp. 1–6. [Google Scholar]
Naderializadeh, N.; Maddah-Ali, M.A.; Avestimehr, A.S. Fundamental limits of cache-aided interference management. IEEE Trans. Inf. Theory 2017, 63, 3092–3107. [Google Scholar] [CrossRef]
Xu, F.; Tao, M.; Liu, K. Fundamental tradeoff between storage and latency in cache-aided wireless interference Networks. IEEE Trans. Inf. Theory 2017, 63, 7464–7491. [Google Scholar] [CrossRef]
Ji, M.; Tulino, A.M.; Llorca, J.; Caire, G. Order-optimal rate of caching and coded multicasting with random demands. IEEE Trans. Inf. Theory 2017, 63, 3923–3949. [Google Scholar] [CrossRef]
Ji, M.; Tulino, A.M.; Llorca, J.; Caire, G. Caching in combination networks. In Proceedings of the 2015 49th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, USA, 8–11 November 2015. [Google Scholar]
Ravindrakumar, V.; Panda, P.; Karamchandani, N.; Prabhakaran, V. Fundamental limits of secretive coded caching. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain, 10–15 July 2016; pp. 425–429. [Google Scholar]
Tang, L.; Ramamoorthy, A. Coded caching schemes with reduced subpacketization from linear block codes. IEEE Trans. Inf. Theory 2018, 64, 3099–3120. [Google Scholar] [CrossRef]
Cheng, M.; Li, J.; Tang, X.; Wei, R. Linear coded caching scheme for centralized networks. IEEE Trans. Inf. Theory 2021, 67, 1732–1742. [Google Scholar] [CrossRef]
Wan, K.; Caire, G. On coded caching with private demands. IEEE Trans. Inf. Theory 2021, 67, 358–372. [Google Scholar] [CrossRef]
Hassanzadeh, P.; Tulino, A.M.; Llorca, J.; Erkip, E. Rate-memory trade-off for caching and delivery of correlated sources. IEEE Trans. Inf. Theory 2020, 66, 2219–2251. [Google Scholar] [CrossRef]
Ji, M.; Caire, G.; Molisch, A.F. Fundamental limits of caching in wireless D2D networks. IEEE Trans. Inf. Theory 2016, 62, 849–869. [Google Scholar] [CrossRef]
Tebbi, A.; Sung, C.W. Coded caching in partially cooperative D2D communication networks. In Proceedings of the 9th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), Munich, Germany, 6–8 November 2017; pp. 148–153. [Google Scholar]
Wang, J.; Cheng, M.; Yan, Q.; Tang, X. Placement delivery array design for coded caching scheme in D2D Networks. IEEE Trans. Commun. 2019, 67, 3388–3395. [Google Scholar] [CrossRef]
Malak, D.; Al-Shalash, M.; Andrews, J.G. Spatially correlated content caching for device-to-device communications. IEEE Trans. Wirel. Commun. 2018, 17, 56–70. [Google Scholar] [CrossRef]
Ibrahim, A.M.; Zewail, A.A.; Yener, A. Device-to-Device coded caching with distinct cache sizes. arXiv 2019, arXiv:1903.08142. [Google Scholar] [CrossRef]
Pedersen, J.; Amat, A.G.; Andriyanova, I.; Brännström, F. Optimizing MDS coded caching in wireless networks with device-to-device communication. IEEE Trans. Wirel. Commun. 2019, 18, 286–295. [Google Scholar] [CrossRef]
Chiang, M.; Zhang, T. Fog and IoT: An overview of research opportunities. IEEE Internet Things J. 2016, 3, 854–864. [Google Scholar] [CrossRef]

Figure 1. Caching system considered in this paper. A server connects with K cache-enabled users and the users can cooperate through a flexible network.

Figure 2. Centralized cooperation gain and parallel gain when

N = 40

K = 20

and

α_{max} = 5

Figure 2. Centralized cooperation gain and parallel gain when

N = 40

K = 20

and

α_{max} = 5

Figure 3. Transmission delay when

N = 40

K = 20

and

α_{max} = 5

. The upper bounds are achieved under the centralized caching scenario.

Figure 3. Transmission delay when

N = 40

K = 20

and

α_{max} = 5

. The upper bounds are achieved under the centralized caching scenario.

Figure 4. Decentralized cooperation gain and parallel gain when

N = 20

and

K = 10

Figure 4. Decentralized cooperation gain and parallel gain when

N = 20

and

K = 10

Figure 5. Transmission delay when

N = 100

K = 20

and

α_{max} = 3

. The upper bounds are achieved under the decentralized random caching scenario.

Figure 5. Transmission delay when

N = 100

K = 20

and

α_{max} = 3

. The upper bounds are achieved under the decentralized random caching scenario.

Table 1. Subfiles sent by users in different partition,

l = 1, 2

Table 1. Subfiles sent by users in different partition,

l = 1, 2

${1, 2, 3}$	${4, 5, 6}$
user 2: $W_{d_{1}, {2, 3, 4, 5}}^{1} \oplus W_{d_{3}, {1, 2, 4, 5}}^{1}$	user 5: $W_{d_{4}, {2, 3, 5, 6}}^{1} \oplus W_{d_{6}, {2, 3, 4, 5}}^{1}$
user 2: $W_{d_{1}, {2, 3, 4, 6}}^{1} \oplus W_{d_{3}, {1, 2, 4, 6}}^{1}$	user 5: $W_{d_{4}, {1, 2, 5, 6}}^{1} \oplus W_{d_{6}, {1, 2, 4, 5}}^{1}$
user 1: $W_{d_{2}, {1, 3, 4, 6}}^{1} \oplus W_{d_{3}, {1, 2, 5, 6}}^{1}$	user 4: $W_{d_{5}, {2, 3, 4, 6}}^{1} \oplus W_{d_{6}, {1, 3, 4, 5}}^{1}$
user 3: $W_{d_{1}, {2, 3, 5, 6}}^{1} \oplus W_{d_{2}, {1, 3, 5, 6}}^{1}$	user 6: $W_{d_{4}, {1, 3, 5, 6}}^{1} \oplus W_{d_{5}, {1, 3, 4, 6}}^{1}$
${1, 2, 4}$	${3, 5, 6}$
user 2: $W_{d_{1}, {2, 4, 5, 6}}^{l} \oplus W_{d_{4}, {1, 2, 3, 5}}^{l}$	user 5: $W_{d_{3}, {1, 4, 5, 6}}^{l} \oplus W_{d_{6}, {1, 2, 3, 5}}^{l}$
${1, 4, 6}$	${2, 3, 5}$
user 6: $W_{d_{1}, {3, 4, 5, 6}}^{l} \oplus W_{d_{4}, {1, 2, 3, 6}}^{l}$	user 3: $W_{d_{2}, {3, 4, 5, 6}}^{l} \oplus W_{d_{5}, {1, 2, 3, 4}}^{l}$
${1, 2, 5}$	${3, 4, 6}$
user 1: $W_{d_{2}, {1, 4, 5, 6}}^{l} \oplus W_{d_{5}, {1, 2, 3, 6}}^{l}$	user 4: $W_{d_{3}, {2, 4, 5, 6}}^{l} \oplus W_{d_{6}, {1, 2, 3, 4}}^{l}$
${1, 2, 3}$	${4, 5, 6}$
user 3: $W_{d_{1}, {2, 3, 4, 5}}^{2} \oplus W_{d_{2}, {1, 3, 4, 5}}^{2}$	user 4: $W_{d_{5}, {2, 3, 4, 6}}^{2} \oplus W_{d_{6}, {2, 3, 4, 5}}^{2}$
user 3: $W_{d_{1}, {2, 3, 4, 6}}^{2} \oplus W_{d_{2}, {1, 3, 4, 6}}^{2}$	user 4: $W_{d_{5}, {1, 2, 4, 6}}^{2} \oplus W_{d_{6}, {1, 2, 4, 5}}^{2}$
user 2: $W_{d_{1}, {2, 3, 5, 6}}^{2} \oplus W_{d_{3}, {1, 2, 4, 5}}^{2}$	user 5: $W_{d_{4}, {1, 3, 5, 6}}^{2} \oplus W_{d_{6}, {1, 3, 4, 5}}^{2}$
user 1: $W_{d_{3}, {1, 2, 4, 6}}^{2} \oplus W_{d_{2}, {1, 3, 5, 6}}^{2}$	user 6: $W_{d_{4}, {1, 2, 5, 6}}^{2} \oplus W_{d_{5}, {1, 3, 4, 6}}^{2}$
user 1: $W_{d_{3}, {1, 2, 5, 6}}^{2} \oplus W_{d_{2}, {1, 3, 4, 5}}^{1}$	user 6: $W_{d_{5}, {1, 2, 4, 6}}^{1} \oplus W_{d_{4}, {2, 3, 5, 6}}^{2}$

Table 2. Parallel user delivery when

K = 7

s = 4

G_{1}^{r} = 4

and

G_{2}^{r} = 3

r \in [35]

Table 2. Parallel user delivery when

K = 7

s = 4

G_{1}^{r} = 4

and

G_{2}^{r} = 3

r \in [35]

${1, 2, 3, 4}$	${5, 6, 7}$
$user 1 :$ $W_{d_{2}, {1, 3, 4}}^{u_{1}, 1}$ ⊕ $W_{d_{3}, {1, 2, 4}}^{u_{1}, 1}$ ⊕ $W_{d_{4}, {1, 2, 3}}^{u_{1}, 1}$	$user 5 : \underset{x \in {1, 2, 3, 4}}{\cup}$ $W_{d_{6}, {5, 7, x}}^{u_{2}, 1}$ ⊕ $W_{d_{7}, {5, 6, x}}^{u_{2}, 1}$
$user 2 :$ $W_{d_{1}, {2, 3, 4}}^{u_{1}, 1}$ ⊕ $W_{d_{3}, {1, 2, 4}}^{u_{1}, 2}$ ⊕ $W_{d_{4}, {1, 2, 3}}^{u_{1}, 2}$	$user 6 : \underset{x \in {1, 2, 3, 4}}{\cup}$ $W_{d_{5}, {6, 7, x}}^{u_{2}, 1}$ ⊕ $W_{d_{7}, {5, 6, x}}^{u_{2}, 2}$
$user 3 :$ $W_{d_{2}, {1, 3, 4}}^{u_{1}, 2}$ ⊕ $W_{d_{1}, {2, 3, 4}}^{u_{1}, 2}$ ⊕ $W_{d_{4}, {1, 2, 3}}^{u_{1}, 3}$	$user 7 : \underset{x \in {1, 2, 3, 4}}{\cup}$ $W_{d_{6}, {5, 7, x}}^{u_{2}, 2}$ ⊕ $W_{d_{5}, {6, 7, x}}^{u_{2}, 2}$
$user 4 :$ $W_{d_{2}, {1, 3, 4}}^{u_{1}, 3}$ ⊕ $W_{d_{3}, {1, 2, 4}}^{u_{1}, 3}$ ⊕ $W_{d_{1}, {2, 3, 4}}^{u_{1}, 3}$
${1, 2, 3, 5}$	${4, 6, 7}$
$user 1 :$ $W_{d_{2}, {1, 3, 5}}^{u_{1}, 1}$ ⊕ $W_{d_{3}, {1, 2, 5}}^{u_{1}, 1}$ ⊕ $W_{d_{5}, {1, 2, 3}}^{u_{1}, 1}$	$user 4 : \underset{x \in {1, 2, 3, 5}}{\cup}$ $W_{d_{6}, {4, 7, x}}^{u_{2}, y_{(. .)}}$ ⊕ $W_{d_{7}, {4, 6, x}}^{u_{2}, y_{(. .)}}$
$user 2 :$ $W_{d_{1}, {2, 3, 5}}^{u_{1}, 1}$ ⊕ $W_{d_{3}, {1, 2, 5}}^{u_{1}, 2}$ ⊕ $W_{d_{5}, {1, 2, 3}}^{u_{1}, 2}$	$user 6 : \underset{x \in {1, 2, 3, 5}}{\cup}$ $W_{d_{4}, {6, 7, x}}^{u_{2}, 1}$ ⊕ $W_{d_{7}, {4, 6, x}}^{u_{2}, y_{(. .)}}$
$user 3 :$ $W_{d_{2}, {1, 3, 5}}^{u_{1}, 2}$ ⊕ $W_{d_{1}, {2, 3, 5}}^{u_{1}, 2}$ ⊕ $W_{d_{5}, {1, 2, 3}}^{u_{1}, 3}$	$user 7 : \underset{x \in {1, 2, 3, 5}}{\cup}$ $W_{d_{6}, {4, 7, x}}^{u_{2}, y_{(. .)}}$ ⊕ $W_{d_{4}, {6, 7, x}}^{u_{2}, 2}$
$user 5 :$ $W_{d_{2}, {1, 3, 5}}^{u_{1}, 3}$ ⊕ $W_{d_{3}, {125}}^{u_{1}, 3}$ ⊕ $W_{d_{1}, {235}}^{u_{1}, 3}$
${1, 2, 3, 6}$	${4, 5, 7}$
$user 1 :$ $W_{d_{2}, {1, 3, 6}}^{u_{1}, 1}$ ⊕ $W_{d_{3}, {1, 2, 6}}^{u_{1}, 1}$ ⊕ $W_{d_{6}, {1, 2, 3}}^{u_{1}, 1}$	$user 4 : \underset{x \in {1, 2, 3, 6}}{\cup}$ $W_{d_{5}, {4, 7, x}}^{u_{2}, y_{(. .)}}$ ⊕ $W_{d_{7}, {4, 5, x}}^{u_{2}, y_{(. .)}}$
$user 2 :$ $W_{d_{1}, {2, 3, 6}}^{u_{1}, 1}$ ⊕ $W_{d_{3}, {1, 2, 6}}^{u_{1}, 2}$ ⊕ $W_{d_{6}, {1, 2, 3}}^{u_{1}, 2}$	$user 5 : \underset{x \in {1, 2, 3, 6}}{\cup}$ $W_{d_{4}, {5, 7, x}}^{u_{2}, 1}$ ⊕ $W_{d_{7}, {4, 5, x}}^{u_{2}, y_{(. .)}}$
$user 3 :$ $W_{d_{2}, {1, 3, 6}}^{u_{1}, 2}$ ⊕ $W_{d_{1}, {2, 3, 6}}^{u_{1}, 2}$ ⊕ $W_{d_{6}, {1, 2, 3}}^{u_{1}, 3}$	$user 7 : \underset{x \in {1, 2, 3, 6}}{\cup}$ $W_{d_{5}, {4, 7, x}}^{u_{2}, y_{(. .)}}$ ⊕ $W_{d_{4}, {5, 7, x}}^{u_{2}, 2}$
$user 6 :$ $W_{d_{2}, {1, 3, 6}}^{u_{1}, 3}$ ⊕ $W_{d_{3}, {1, 2, 6}}^{u_{1}, 3}$ ⊕ $W_{d_{1}, {2, 3, 6}}^{u_{1}, 3}$
$\dots$ $\dots \dots$	⋯ $\dots \dots$

There should be 35 partitions in total while the table only shows three partitions.

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

© 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Huang, Z.; Chen, J.; You, X.; Ma, S.; Wu, Y. Coded Caching for Broadcast Networks with User Cooperation. Entropy 2022, 24, 1034. https://doi.org/10.3390/e24081034

AMA Style

Huang Z, Chen J, You X, Ma S, Wu Y. Coded Caching for Broadcast Networks with User Cooperation. Entropy. 2022; 24(8):1034. https://doi.org/10.3390/e24081034

Chicago/Turabian Style

Huang, Zhenhao, Jiahui Chen, Xiaowen You, Shuai Ma, and Youlong Wu. 2022. "Coded Caching for Broadcast Networks with User Cooperation" Entropy 24, no. 8: 1034. https://doi.org/10.3390/e24081034

APA Style

Huang, Z., Chen, J., You, X., Ma, S., & Wu, Y. (2022). Coded Caching for Broadcast Networks with User Cooperation. Entropy, 24(8), 1034. https://doi.org/10.3390/e24081034

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Coded Caching for Broadcast Networks with User Cooperation^†

Abstract

1. Introduction

2. System Model and Problem Definition

3. Main Results

3.1. Centralized Coded Caching

3.2. Decentralized Coded Caching

4. Coding Scheme under Centralized Data Placement

4.1. An Illustrative Example

4.2. The Generalized Centralized Coding Caching Scheme

5. Coding Scheme under Decentralized Data Placement

5.1. An Illustrative Example

5.2. The Generalized Decentralized Coded Caching Scheme

5.2.1. Allocating Communication Loads between the Server and User

5.2.2. Inner-Group Coding

5.2.3. Parallel Delivery among Groups

6. Conclusions

Author Contributions

Funding

Conflicts of Interest

Appendix A. Proof of the Converse

Appendix B

Appendix C

Appendix C.1. Case α_max = $⌊ \frac{K}{2} ⌋$

Appendix C.2. Case α_max =1

Appendix D

Appendix D.1. When α_max = $⌊ \frac{K}{2} ⌋$

Appendix D.1.1. Case α_max = $⌊ \frac{K}{2} ⌋$ and p ≥ p_th

Appendix D.1.2. Case α_max = $⌊ \frac{K}{2} ⌋$ and p ≥ p_th

Appendix D.2. When α_max = 1

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

Article Menu

Coded Caching for Broadcast Networks with User Cooperation †

Abstract

1. Introduction

2. System Model and Problem Definition

3. Main Results

3.1. Centralized Coded Caching

3.2. Decentralized Coded Caching

4. Coding Scheme under Centralized Data Placement

4.1. An Illustrative Example

4.2. The Generalized Centralized Coding Caching Scheme

5. Coding Scheme under Decentralized Data Placement

5.1. An Illustrative Example

5.2. The Generalized Decentralized Coded Caching Scheme

5.2.1. Allocating Communication Loads between the Server and User

5.2.2. Inner-Group Coding

5.2.3. Parallel Delivery among Groups

6. Conclusions

Author Contributions

Funding

Conflicts of Interest

Appendix A. Proof of the Converse

Appendix B

Appendix C

Appendix C.1. Case αmax = ⌊ K 2 ⌋

Appendix C.2. Case αmax =1

Appendix D

Appendix D.1. When αmax = ⌊ K 2 ⌋

Appendix D.1.1. Case αmax = ⌊ K 2 ⌋ and p ≥ pth

Appendix D.1.2. Case αmax = ⌊ K 2 ⌋ and p ≥ pth

Appendix D.2. When αmax = 1

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

Coded Caching for Broadcast Networks with User Cooperation^†

Appendix C.1. Case α_max = $⌊ \frac{K}{2} ⌋$

Appendix C.2. Case α_max =1

Appendix D.1. When α_max = $⌊ \frac{K}{2} ⌋$

Appendix D.1.1. Case α_max = $⌊ \frac{K}{2} ⌋$ and p ≥ p_th

Appendix D.1.2. Case α_max = $⌊ \frac{K}{2} ⌋$ and p ≥ p_th

Appendix D.2. When α_max = 1