Beyond Cut-Set Bounds - The Approximate Capacity of D2D Networks Avik Sengupta Ravi Tandon Hume Center for National Security and Technology Department of Electrical and Computer Engineering Virginia Tech, Blacksburg, VA 24060, USA Email: [email protected] Discovery Analytics Center Department of Computer Science Virginia Tech, Blacksburg, VA 24060, USA Email: [email protected] Abstract—Device-to-Device (D2D) communication is emerging as a viable solution for alleviating the severe capacity crunch in content-centric wireless networks. D2D encourages backhaulfree communication directly between devices with similar content requirements grouped into clusters. In this work, a self-sustaining D2D network is considered, where a set of commonly requested files are completely stored within the collective devices memories in a cluster and file requests from devices are serviced by local inter-device multicast transmissions. For such a network, new information theoretic converse results are developed, in the form of a lower bound on the minimum D2D multicast rate as a function of the storage per device. The proposed converse is then used to characterize the approximate tradeoff between the device storage and D2D multicast rate to within a constant multiplicative gap of 8. I. I NTRODUCTION In recent times, the dynamics of traffic over wireless networks has undergone a paradigm shift to become increasingly content centric with multimedia content distribution holding precedence. This necessitates careful design of content storage and over-the-air distribution schemes within the networks to efficently use scarce spectral resources to handle heavy traffic loads as evidenced by a wealth of recent research [1]–[12]. Device-to-device (D2D) communication systems have been proposed as one of the solutions that could help in alleviating the severe capacity crunch in wireless networks [13]–[16]. D2D uses low-power direct communications within devices grouped into clusters to facilitate large scale frequency reuse thereby freeing up precious spectral resources. We consider a D2D network with K devices, and N files (denoted by F1 , . . . , FN , each of size B units), where the storage of each device is M B units. The base-station populates the devices with functions of files, depending on the number of users and available device storage. The D2D system is self-sustaining i.e., all N files must be recoverable from the collective storage memory of the devices, which is equivalent to the condition KM ≥ N . Once the devices reveal their file requests, all the devices within the cluster transmit multicast messages over the shared link to service the requests. Figure 1 illustrates the system model. The storage/multicast mechanisms must be designed such that any device must be able to decode its requested file using its local storage and the multicast transmissions from other devices. Recently, Maddah-Ali and Niesen have investigated a related caching problem [1]–[4] for which it has been shown that, by jointly designing the content storage and delivery, order-wise improvement in transmission rates can be achieved. The main difference between the caching problem studied in [1,2] and the D2D problem is the distributed nature of multicast transmissions. The caching problem allows for centralized delivery, in which the multicast can be any arbitrary function of all N files. In the D2D problem however, the outgoing multicast from each device can only depend on the content stored at that device. The focus of this work is on the fundamental tradeoff between the device storage and the total multicast transmission rate (referred to as the (M, R) tradeoff) for the D2D problem. In [15,16], Ji et.al. present new storage/delivery mechanisms for the D2D problem. The results in [16] show that for a self-sustaining D2D network, when the devices can use local inter-device multicast transmissions to satisfy the requests of others within the cluster, orderwise rate improvements similar to [1,2] can be achieved. The authors present an achievable scheme as well as a cut-set based argument to obtain upper and lower bounds on the (M, R) tradeoff for the D2D problem. In this work, we develop a new converse (lower bound) on the (M, R) tradeoff for the D2D problem. The new lower bound addresses constraints that are unique to the D2D network, i.e., the local dependence of device multicast on its stored content. We show that the new converse is tighter than the existing one presented in [16, Theorem 2] (which are primarily based on the relaxation of the D2D problem to the centralized caching problem) for all values of problem parameters. Our result shows that the achievable scheme presented in [16] is indeed optimal for the lowest allowable value of storage memory for a self-sustaining D2D network i.e., at M =N/K. Using our new converse result, together with the achievable scheme of [16], we characterize the (M, R) tradeoff for the D2D network to within a maximum constant multiplicative gap of 8 for all values of problem parameters. The paper is organized as follows: Section II outlines the system model. Section III details the analysis of the new lower bound on the storage vs. rate tradeoff for the D2D network, while Section IV illustrates the intuition behind the new bound through an example. Finally, Section V concludes the paper. For the (M, R) D2D scheme, the probability of error is defined as: Pe , max (5) max P(FˆRk ̸= FRk ). (R1 ,...,RK )∈[N ]K k∈[K] Definition 4 (Storage vs. Rate Tradeoff). The storage-rate pair (M, R) is achievable if, for any ϵ > 0, there exists an (M, R) D2D scheme for which Pe ≤ ϵ. The storage vs. rate tradeoff is defined as: (6) R(M ) , inf {R : (M, R) is achievable} . Fig. 1. System Model for device-to-device (D2D) Network. Notation: Let Yi be a random variable. Y[a:b] , where a < b denotes the set of random variables {Yi : i = a, a + 1, . . . , b − 1, b}. Also, Y[a,b] denotes the set {Yi : i = a, b}. Y[n] denotes a set of any n arbitrary random variables Yi such that |Y[n] | = n. N+ denotes the set of natural numbers; the function (x)+ = max(0, x); ⌈x⌉ denotes the ceil function; ⌊x⌋ denotes the floor function. II. S YSTEM M ODEL The D2D network has K users, and a total of N files, denoted by F1 , .., FN , where each file is assumed to be of size B, for some B ∈ N+ . Formally, the files Fn are i.i.d and distributed as : Fn ∼ Unif{1, 2, . . . , 2B }. (1) We next define the key components of the D2D problem: Definition 1 (Storage). The content storage phase consists of K storage functions, which map the files (F1 , . . . , FN ) into the device storage content ( ) Zk , ϕk F1 , . . . , FN , (2) for each user k ∈ {1, 2, . . . , K}. The maximum allowable size of the contents of each device storage, Zk , is M B units. An additional constraint of self-sustainability is enforced i.e., KM ≥ N , which ensures all the files in the system are completely stored within the D2D cluster. Definition 2 (Delivery). In the delivery phase each device k ∈ {1, 2, . . . , K} uses one of N K encoding functions to map its storage contents, Zk , to a multicast transmission: ( ) k X(R , ψ(R1 ,...,RK ) Zk ∀k ∈ {1, 2, . . . , K}. (3) 1 ,...,RK ) over the shared link in response to the requests (R1 , . . . , RK ) ∈ {1, 2, . . . , N K }. Each such transmission has rate RB/K units. The total multicast rate. when all K devices transmit, is RB units. Definition 3 (File Decoding). Once the multicast transmission is received, KN K decoding functions map the received signal 1 K over the shared link X(R , . . . , X(R and the 1 ,...,RK ) 1 ,...,RK ) storage content Zk to ( the estimate ) , . . . , XK , Zk , FˆR , µ(R ,...,R ),k X 1 k 1 K (R1 ,...,RK ) (R1 ,...,RK ) (4) of the requested file FRk for user k ∈ {1, 2, . . . , K}. III. M AIN R ESULTS AND D ISCUSSION We next present our main result which gives a new information theoretic lower bound on the storage vs. rate tradeoff for the D2D problem. Theorem 1. In a D2D system with K devices and N files, with each device having storage size M , and KM ≥ N , the optimal content delivery rate R∗ (M ) is lower bounded by: R∗ (M ) ≥ RLB (M ) , ( ) µ N − sM − s+µ (N − ℓs)+ ( ) max , (7) s∈{1,...,K}, ℓ K−s K ℓ∈{1,...,⌈ N s ⌉} (⌈ ⌉ ) where µ = min N −ℓs , K − s ∀s, ℓ . ℓ Proof. The proof of Theorem 1 is given in Appendix A The expression in Theorem 1 has two parameters - (1) s, which is related to the number of devices and as well as (2) a new parameter ℓ. Compared to [16, Theorem 2], the additional parameter ℓ adds further flexibility to the lower bound expression and better models the file decoding through the interaction of the device storage contents and the multicast transmissions. Considering the cut-set based bound presented in [16, Theorem 2], the first term inside the max(·) function is simply the expression for the centralized caching problem presented in [1, Theorem 2]. Furthermore, setting ℓ = ⌈N/s⌉ in Theorem 1 yields { } N − sM ∗ ⌈ N ⌉ ( K−s ) , R (M ) ≥ max (8) s∈{1,...,K} s K which is greater than the cut-set expression in the first term inside the max(·) function owing to the factor K−s ≤ 1 in K the denominator. The second term inside the max(·) function can be obtained by setting s = 1, ℓ = N in Theorem 1. Thus, the proposed bound is generally tighter than the bound in [16, Theorem 2]. It is to be noted that the bound in [16] is tight only for large values of device storage size M . As shown in the sequel, the new bound in Theorem 1 is tighter for smaller values of M and yields the existing bound as a special case for large values of M . Next, we present our second main result, which establishes the optimal storage vs. rate tradeoff for the D2D network to within a constant multiplicative factor. In [16], the authors propose a D2D content distribution scheme which achieves a rate given by [16, Theorem 1]. Using the result in (7), we show a constant multiplicative gap exists between the new lower bound and the achievable rate in [16, Theorem 1]: Theorem 2. Let RU B (M ) be the achievable rate of the D2D scheme given in [16, Theorem 1] and let RLB (M ) be the lower bound on the optimal rate given in (7). For any K ∈ N+ devices, N ∈ N+ files, and device storage in the range N K ≤ M ≤ N , we have: N =1 M=K N 2 RU B (M ) ≤ 3 K <M ≤ 3 . Gap = (9) 2 RLB (M ) ≤6 3 <M ≤1 ≤8 1≤M ≤N Proof. The proof of Theorem 2 is omitted for brevity. IV. I NTUITION B EHIND P ROOF OF T HEOREM 1 We next present a detailed example to illustrate the intuition behind the proposed converse. Example 1. Consider a D2D system with K = 3 devices, each with a storage memory of M , and N = 3 files A, B, C each of unit size. For this problem, the lower bounds [16, Theorem 2] are given by: R∗ + 3M ≥ 3 (10) 2R∗ + M ≥ 3. (11) In contrast, the proposed bound in Theorem 1 gives following tighter bounds for different choices of s and ℓ: R∗ + 6M ≥ 8, s = 2, ℓ = 1 (12) ∗ 8R + 6M ≥ 15, s = 1, ℓ = 2 (13) 2R∗ + M ≥ 3, s = 1, ℓ = 3, (14) where (14) is the bound in (11). Next, we detail the derivation of the new lower bounds (12) and (13). First, we consider the request vectors (R1 , R2 , R3 ) = (A, B, C) and (R1 , R2 , R3 ) = (B, C, A). The first s = 2 device storage contents Z1 , Z2 ¯ ABC = {X 3 }, X ¯ BCA = along with two transmissions X ABC 3 {XBCA } from the third device corresponding to the two request vectors are able to decode all 3 files. Here each transmission has the rate of 13 R∗ . We upper bound the entropy of ℓ = 1 transmission with this rate, while using the other transmission’s decoding capability (in conjunction with the device storage contents) to derive a tighter bound. We have: ¯ ABC , X ¯ BCA ) 3 ≤ H(Z[1,2] , X (15) ¯ ¯ ≤ H(Z[1,2] ) + H(XABC , XBCA |Z[1,2] ) (16) ¯ ¯ ¯ ≤ 2M + H(XABC ) + H(XBCA |Z[1,2] , XABC ) (17) ∗ R ¯ BCA |Z[1,2] , X ¯ ABC , A, B) ≤ 2M + + H(X 3 R∗ ¯ BCA , Z3 |Z[1,2] , X ¯ ABC , A, B) + H(X ≤ 2M + 3 R∗ ¯ ABC , A, B) ≤ 2M + + H(Z3 |Z[1,2] , X 3 ¯ BCA |Z[1:3] , X ¯ ABC , A, B) + H(X ∗ R ≤ 2M + + H(Z3 |Z[1,2] , A, B) 3 ¯ BCA |Z[1:3] , X ¯ ABC , A, B, C) + H(X ∗ R ≤ 2M + + H(Z3 |Z[1,2] , A, B), 3 (18) (19) (20) (21) (22) where (22) follows from the fact that ¯ BCA |Z[1:3] , XABC , A, B, C) = 0 since XBCA is a H(X function of the files A, B, C which are present inside the conditioning. Considering the term H(Z3 |Z[1,2] , A, B), we have: H(Z3 |Z[1,2] , A, B) = H(Z[1:3] |A, B) − H(Z[1,2] |A, B). (23) Using (23) in (22), we have: R∗ 3 ≤ 2M + + H(Z[1:3] |A, B) − H(Z[1,2] |A, B). (24) 3 Now considering all possible subsets of Z[1:3] having cardinality 2, in the RHS of (24), we have the following: R∗ 3 ≤ 2M + + H(Z[1:3] |A, B) − H(Z[2,3] |A, B). (25) 3 R∗ 3 ≤ 2M + + H(Z[1:3] |A, B) − H(Z[1,3] |A, B). (26) 3 Symmetrizing over the inequalities in (24), (25) and (26), we have: 3 ∑ H(Z[i,j] |A, B) R∗ 3 ≤ 2M + + H(Z[1:3] |A, B) − . 3 3 i,j=1,i̸=j (27) Han’s Inequality: We next state Han’s Inequality [17, Theorem 17.6.1] on subsets of random variables, which we use throughout the paper for deriving the new lower bound. Let {X1 , X2 , . . . , Xn } denote a set of random variables. Further, let X[s] ⊆ {X1 , X2 , . . . , Xn } denote a subset of cardinality s. Then given two subsets X[r] , X[m] where r ≥ m, the statement of Han’s Inequality can ( be) stated as: ( ) ∑ ∑ H X[r] H X[m] 1 1 (n) ( ) ≤ n , r m r m X[r] :|X[r] |=r X[m] :|X[m] |=m (28) where the sums are over all possible subsets of size r, m respectively. Next, consider Z[1:3] as the set of random variables and the subset Z[i,j] ⊆ Z[1:3] : i ̸= j, ∀i, j = 1, 2, 3 of cardinality 2. Applying Han’s Inequality using the conditional entropy of the sets, we have: ( ) ( ) (33) (32) 1 ∑ H Z[1:3] |A, B 1 ∑ H Z[i,j] |A, B (3) ≤ (3) (29) 3 2 3 i=1 2 i,j=1 i̸=j ⇒ ) 1 2 ( H Z[1:3] |A, B ≤ 3 3 Substituting (30) R∗ 3 ≤ 2M + 3 R∗ ≤ 2M + 3 R∗ ≤ 2M + 3 R∗ ≤ 2M + 3 R∗ ≤ 2M + 3 3 ∑ ( ) H Z[i,j] |A, B . (30) 2H(Z[1:3] |A, B) 3 (31) i,j=1,i̸=j into (24), we have: + H(Z[1:3] |A, B) − H(Z[1:3] |A, B) 3 H(Z[1:3] , C|A, B) + 3 H(C|A, B) + H(Z[1:3] |A, B, C) + 3 1 ∗ + ⇒ R + 6M ≥ 8. 3 + (32) (33) (34) (35) 2 9 1.8 8 1.6 7 1.4 6 1.2 Rate (R) Rate (R) New Lower Bound − Theorem 1 Lower Bound in [16] Upper Bound in [16] 1 0.8 0.2 4 3 0.6 0.4 5 2 New Lower Bound − Theorem 1 Lower Bound in [16] Upper Bound in [16] 0 0 0.5 1 1.5 2 Storage per Device (M) 1 2.5 3 (a) Fig. 2. 1 2 3 4 5 6 Storage per Device (M) 7 8 9 10 (b) M vs. R tradeoff for a D2D cluster with (a) N = K = 3 and (b) N = K = 10. Next, we consider s = 1 device storage content, Z1 , and three request vectors (R1 , R2 , R3 ) = (A, B, C), (R1 , R2 , R3 ) = (B, C, A) and (R1 , R2 , R3 ) = (C, A, B) along with 2 3 ¯ ABC ¯ BCA transmissions X = {XABC , XABC }, X = 2 3 2 3 ¯ CAB = {X {XBCA , XBCA }, X , X } which are capaCAB CAB ble of decoding all 3 files. Each composite transmission is of rate 32 R∗ . We upper bound the entropy of ℓ = 2 transmissions with their rate. Thus we have: ¯ ABC , X ¯ BCA , X ¯ CAB ) 3 ≤ H(Z1 , X (36) ¯ ABC , X ¯ BCA , X ¯ CAB |Z1 ) (37) ≤ H(Z1 ) + H(X ¯ ABC , X ¯ BCA |Z1 ) ≤ M + H(X ¯ ¯ ABC , X ¯ BCA ) + H(XCAB |Z1 , X (38) 2R∗ ¯ CAB , Z2 |Z1 , X ¯ ABC , X ¯ BCA ) (39) + H(X 3 4R∗ ¯ ABC , X ¯ BCA , A, B) ≤M+ + H(Z2 |Z1 , X 3 ¯ CAB |Z[1,2] , X ¯ ABC , X ¯ BCA , A, B, C) (40) + H(X ∗ 4R ≤M+ + H(Z2 |Z1 , A, B) (41) 3 ∗ 4R + H(Z[1,2] |A, B) − H(Z1 |A, B), (42) ≤M+ 3 where, (40) follows from the fact that ¯ CAB |Z[1,2] , X ¯ ABC , X ¯ BCA , A, B, C) = 0 since X ¯ CAB H(X is a function of the files A, B, C. Considering all possible subsets of Z[1,2] of cardinality 1 and using a similar symmetrization argument and Han’s Inequality, we get: H(Z[1,2] |A, B) 4R∗ 3≤M+ + H(Z[1,2] |A, B) − (43) 3 2 H(C|A, B) + H(Z[1,2] |A, B, C) 4R∗ ≤M+ + (44) 3 2 1 4R∗ + ≤M+ (45) 3 2 (46) ⇒ 8R∗ + 6M ≥ 15. Finally, considering again, s = 1 device storage content, Z1 , and three request vectors (R1 , R2 , R3 ) = (A, B, C), (R1 , R2 , R3 ) = (B, C, A) and (R1 , R2 , R3 ) = ¯ ABC (C, A, B) along with three transmissions X = ≤M +2· 0 0 2 3 ¯ BCA = {X 2 , X 3 }, X ¯ CAB = {XABC , XABC }, X BCA BCA 2 3 {XCAB , XCAB } which are capable of decoding all 3 files. Each transmission has rate 2R∗ /3. We upper bound the entropy of ℓ = 3 transmissions by their rates. We have: ¯ ABC , X ¯ BCA , X ¯ CAB ) 3 ≤ H(Z1 , X (47) ¯ ABC ) + H(X ¯ BCA ) + H(X ¯ CAB ) (48) ≤ H(Z1 ) + H(X 2 ≤ M + 3 R∗ (49) 3 ⇒ 2R∗ + M ≥ 3. (50) Finally, combining (12), (13) and (14), gives the proposed lower bound on the optimal transmission rate as shown in Figure 2(a). The last bound on the rate given in (50) is tight only in the case when the transmissions are almost independent of each other. The proposed converse is tight at the point M = N K where we show that the achievable point proposed in [16, Theorem 1] is optimal. For increasing N, K we can see from Figure 2(b) that the proposed converse significantly improves on the existing bounds from [16, Theorem 2]. V. C ONCLUSION In this paper, we presented a new information theoretic lower bound for a self-sustaining D2D network. We have leveraged Han’s Inequality to better model the interaction of shared content stored in the device memories and file decoding capability of multicast transmissions to derive new lower bounds which are generally tighter than the existing cut-set based bounds. Using the new lower bound, we characterized the device storage vs. transmission rate tradeoff of the D2D network to within a maximum constant multiplicative factor of 8 for all possible values of problem parameters. A PPENDIX A P ROOF OF T HEOREM 1 Let there be a library of N ∈ N+ files F[1:N ] each of unit size (without loss of generality), and K ∈ N+ devices in the D2D cluster, with storage contents Z[1:K] . The self sustainability condition of the D2D cluster, we have KM ≥ N . Let s be an integer such that s ∈ {1, 2, . . . , K}. Consider the first s device storage contents, Z[1:s] , and a request vector (R1 , R2 , . . . , Rs , Rs+1 , . . . , RK ) = (1, 2, . . . , s, ϕ, . . . , ϕ) i.e., the first s requests are unique files while the remaining K − s can be for arbitrary files. To service this request consider the composite transmissionvector: s+1 X(1,2,...,s,ϕ,...,ϕ) X s+2 ¯ 1 = (1,2,...,s,ϕ,...,ϕ) , X (51) .. . s+K X(1,2,...,s,ϕ,...,ϕ) s+1 = ψ(F[1:s] , F[K−s] ) denotes the mulwhere X(1,2,...,s,ϕ,...,ϕ) ticast transmission from the (s + 1)−th device to service the request of the s devices. Note that the files in the set F[K−s] , denoting the requests of the other K − s devices, are considered arbitrary. For achieving optimal transmission rate R∗ (M ), each device in the D2D cluster multicasts with a rate of R∗ (M )/K. Thus the rate of each composite transmis∗ sion vector is given by K−s K R (M ). Next, we note that the ¯ 1 , composed of (K − s) subcomposite transmission vector X multicast transmissions, along with the contents of s device memories is capable of decoding s files i.e., F[1:s] . Similarly, consider a request vector (R1 , R2 , . . . , Rs , Rs+1 , . . . , RK ) = (s + 1, s + 2, . . . , 2s, ϕ, . . . , ϕ) where the first s requests are again for unique files and rest are arbitrary. A composite transmission vector s+1 X(s+1,s+2,...,2s,ϕ,...,ϕ) X s+2 (s+1,s+2,...,2s,ϕ,...,ϕ) ¯ , X2 = (52) .. . s+K X(s+1,s+2,...,2s,ϕ,...,ϕ) along with device storage contents Z[1:s] , can decode another s files F[s+1:2s] . Considering ⌈N/s⌉ composite transmission ¯ [1:⌈N/s⌉] and s device storage contents Z[1:s] , the vectors X library of files F[1:N ] can be completely decoded. Thus, we have: ( ) ¯ [1:⌊N/s⌋] N ≤ H Z[1:s] , X (53) ( ) ( ) ¯ (54) ≤ H Z[1:s] + H X[1:⌊N/s⌋] |Z[1:s] ( ) ¯ ≤ sM + H X[1:⌊N/s⌋] |Z[1:s] (55) ( ) ( ) ¯ ¯ ¯ ≤ sM + H X[1:ℓ] |Z[1:s] + H X[ℓ+1:⌈N/s⌉] |Z[1:s] , X[1:ℓ] (56) ℓ(K − s)R∗ (M ) ≤ sM + K ) ( ¯ [ℓ+1:⌈N/s⌉] |Z[1:s] , X ¯ [1:ℓ] , F[1:ℓs] +H X (57) ∗ ℓ(K − s)R (M ) ≤ sM + K ) ( ¯ [ℓ+1:⌈N/s⌉] , Z[s+1:s+µ] |Z[1:s] , X ¯ [1:ℓ] , F[1:ℓs] (58) +H X ℓ(K − s)R∗ (M ) ≤ sM + K ( ) ¯ [1:ℓ] , F[1:ℓs] + H Z[s+1:s+µ] |Z[1:s] , X | {z } ,δ ) ( ¯ [ℓ+1:⌈N/s⌉] |Z[1:s+µ] , X ¯ [1:ℓ] , F[1:ℓµ+ℓs] , +H X | {z } ,λ (59) where (57) follows from the fact that each composite trans∗ mission vector has rate K−s K R (M ) and that the device storage contents, Z[1:s] , along with the composite transmission ¯ [1:ℓ] are capable of decoding the files F[1:ℓs] . In vectors X {⌈ ⌉ } , K − s is the number of additional (58), µ = min N −ℓs ℓ ¯ [1:ℓ] device memories which, along with the transmissions X can decode all N files. For s = K, we have: ( ) ¯ [1:⌈N/s⌉] |Z[1:s] = 0, H X (60) and (55) yields the self-sustainability condition KM ≥ N . Upper Bound on δ: We consider the factor δ, from (59): ( ) ¯ [1:ℓ] , F[1:ℓs] δ = H Z[s+1:s+µ] |Z[1:s] , X (61) ( ) ≤ H Z[s+1:s+µ] |Z[1:s] , F[1:ℓs] (62) ) ) ( ( = H Z[1:s+µ] |F[1:ℓs] − H Z[1:s] |F[1:ℓs] . (63) Considering all possible subsets of Z[1:s+µ] having cardinality s, i.e., all possible combination of s device storage contents in (53), and all possible combinations of files in the( set F ) [K−s] for ¯ [1:ℓ] in (57), we can obtain s+µ different each transmission X s inequalities of the form of (63). Symmetrizing over all the inequalities, we have: s+µ (∑ s ) ( ) ( ) 1 ( ) δ ≤ H Z[1:s+µ] |F[1:ℓs] − s+µ H Zi[s] |F[1:ℓs] , s i=1 (64) where, Zi[s] is the i-th size-s subset of Z[1:s+µ] . Next, consider Z[1:s+µ] as a set of random variables and subsets Zi[s] ⊆ ( ) Z[1:s+µ] ∀i = 1, . . . , s+µ s . Applying Han’s Inequality from (28), we have: s+µ ( ) (∑ s+µ) H Z[1:s+µ] |F[1:ℓs] 1 (s+µ) s+µ s+µ i=1 ( ) s+µ (∑ s ) H Zi[s] |F[1:ℓs] 1 ≤ (s+µ) (65) s s i=1 s+µ ) ( ) s 1 ∑ ( i H Z[1:s+µ] |F[1:ℓs] ≤ (s+µ) H Z[s] |F[1:ℓs] . s+µ s i=1 (66) Substituting (66) into (64), we have: ( ) ( ) s δ ≤ H Z[1:s+µ] |F[1:ℓs] − H Z[1:s+µ] |F[1:ℓs] (67) s+µ ( ) µ = H Z[1:s+µ] |F[1:ℓs] (68) s+µ ( ) µ (69) ≤ H Z[1:s+µ] , F[ℓs+1:N ] |F[1:ℓs] s+µ ( ) ( ) µ = H F[ℓs+1:N ] |F[1:ℓs] + H Z[1:s+µ] |F[1:N ] (70) s+µ | {z } ⇒ =0 µ (N − ℓs)+ , (71) s+µ where (70) follows from the fact that the device storage contents are functions of all the N files in the library. Upper Bound on λ: We consider the factor λ, from (59). We have two cases: Case 1: N ≤ ℓs + ℓµ: We consider the case that all N files ≤ can be decoded with µ ≤ K − s additional device storage ¯ [1:ℓ] , within the conditioning in contents and transmissions X the factor λ in (59)i.e., ℓs + ℓµ ≤ N . We have: ) ( ¯ [1:ℓ] , F[1:N ] ¯ [ℓ+1:⌈N/s⌉] |Z[1:s+µ] , X λ=H X ( ) ¯ [ℓ+1:⌈N/s⌉] |Z[1:s+µ] , F[1:N ] ≤H X = 0, (72) which follows from the fact that the transmissions are functions of all N files. Case 2: N > ℓs + ℓµ: We consider the case where µ = K −s additional device storage contents along with the transmissions ¯ [1:ℓ] , cannot decode all N files. We have: X ( ) ¯ [ℓ+1:⌈N/s⌉] |Z[1:K] , X ¯ [1:ℓ] , F[1:Kℓ] λ=H X ( ) ¯ [ℓ+1:⌈N/s⌉] |Z[1:K] = 0, (73) ≤H X which follows from the fact that KM ≥ N i.e., all files are stored within the collective device memories in the D2D cluster and hence all transmissions are functions of all the device storage contents. Thus combining (72) and (73) we have: λ = 0. (74) Substituting (71) and (74) into (59), we have: ℓ(K − s) µ N ≤ sM + · R∗ (M ) + (N − ℓs)+ K s+µ ( ) µ N − sM − s+µ (N − ℓs)+ ( ) ⇒R∗ (M ) ≥ . (75) ℓ K−s K Optimizing over all parameter values of s, ℓ, µ, we have: R∗ (M ) ≥ RLB (M ) , ) ( µ N − sM − s+µ (N − ℓs)+ ( ) max (76) , s∈{1,...,K}, ℓ K−s K N ℓ∈{1,...,⌈ s ⌉} which completes the proof of Theorem 1. R EFERENCES [1] M. A. Maddah-Ali and U. Niesen, “Fundamental Limits of Caching,” IEEE Transactions on Information Theory, vol. 60, no. 5, pp. 2856– 2867, May 2014. [2] M. Maddah-Ali and U. Niesen, “Decentralized Coded Caching Attains Order-Optimal Memory-Rate Tradeoff,” IEEE/ACM Transactions on Networking, April 2014. [3] U. Niesen and M. A. Maddah-Ali, “Coded Caching with Nonuniform Demands,” in IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), April 2014, pp. 221–226. [4] R. Pedarsani, M. Maddah-Ali, and U. Niesen, “Online Coded Caching,” in IEEE International Conference on Communications (ICC), June 2014, pp. 1878–1883. [5] A. Sengupta, R. Tandon, and T. C. Clancy, “Fundamental Limits of Caching with Secure Delivery,” Wireless Physical Layer Security Workshop - IEEE International Conference on Communications (ICC), pp. 771–776, June 2014. [6] ——, “Decentralized Caching with Secure Delivery,” IEEE International Symposium on Information Theory (ISIT), pp. 41–45, July 2014. [7] ——, “Secure Caching with Non-Uniform Demands,” IEEE Global Wireless Summit (GWS), pp. 1–5, May 2014. [8] ——, “Fundamental Limits of Caching with Secure Delivery,” IEEE Transactions on Information Forensics and Security, vol. 10, pp. 355– 370, Feb 2015. [9] A. Sengupta, S. Amuru, R. Tandon, R. M. Buehrer, and T. C. Clancy, “Learning Distributed Caching Strategies in Small Cell Networks,” The Eleventh International Symposium on Wireless Communication Systems (ISWCS), pp. 917–921, Aug 2014. [10] M. Ji, G. Caire, and A. F. Molisch, “Optimal Throughput-Outage Tradeoff in Wireless One-Hop Caching Networks,” in IEEE International Symposium on Information Theory (ISIT), July 2013, pp. 1461–1465. [11] M. Ji, A. M. Tulino, J. Llorca, and G. Caire, “Order Optimal Coded Caching-Aided Multicast under Zipf Demand Distributions,” in The Eleventh International Symposium on Wireless Communication Systems (ISWCS), 2014. [12] N. Golrezaei, K. Shanmugam, A. Dimakis, A. Molisch, and G. Caire, “FemtoCaching: Wireless Video Content Delivery through Distributed Caching Helpers,” IEEE Transactions on Information Theory, vol. 59(12), pp. 8402–8413, Dec. 2013. [13] M. Ji, G. Caire, and A. F. Molisch, “Wireless Device-to-Device Caching Networks: Basic Principles and System Performance,” arXiv : 1305.5216, May 2013. [14] N. Golrezaei, A. G. Dimakis, and A. F. Molisch, “Wireless Device-toDevice Communications with Distributed Caching,” in IEEE International Symposium on Information Theory Proceedings (ISIT), July 2012, pp. 2781–2785. [15] M. Ji, G. Caire, and A. F. Molisch, “Fundamental Limits of Distributed Caching in D2D Wireless Networks,” in IEEE Information Theory Workshop (ITW) 2013, Sept 2013, pp. 1–5. [16] ——, “Fundamental limits of caching in wireless D2D networks,” arXiv:1405.5336, 2014. [Online]. Available: http://arxiv.org/abs/1405. 5336 [17] T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd Edition. Hoboken, NJ, USA: Wiley-Interscience, John Wiley and Sons.

© Copyright 2017 ExploreDoc