52 W.Wang et aL/Computer Communications 83 (2016)45-55 Proof.To show E(fs)=-In P(fs)is concave,we have: R9(,f片)/kui=-6/M (33) P,()=(T)- ((T-)dr(0). (23) Note that-v/M is a constant for all content i.When vo is given, o we can separately solve Eqs.(32)and(33)for each content to get Note that(t)is a decreasing function,therefore we the optimal allocation.If the solution has+f1.it is evident have -dX(t)/dt z0.Since exponential functions are log-convex. that content i is so popular that we can simply set=1 (-d(t)/dt)((Tt)is a log-convex function offon ev- and v>0 for content i.Therefore,one way to solve the above problems is to use vo as a global pricing signal [38]to coordinate ery point t[0.T].Taking integral over t preserves log-convexity the distributed storage allocation fsi and fr.i for each content i. 137sot)d(t)is also log-convex.Adding a pos- itive constant X(T)preserves log-convexity.thus Pr(fs)is log- 5.3.Extension of the optimization framework convex and E(fsi)is concave.This directly leads to the convex- ity of the objective function as discussed above.It is clear that In the above discussion,we mainly focus on systems with two all the constraints in the storage assignment optimization problem types of helpers,namely,seeds and relays.The optimization frame- in Egs.(18)-(20)are linear,so the storage assignment problem is work in Section 5.1 can be extended to cases where there are more convex.▣ than two types of helpers. Consider the case where there are WiFi APs or Femtocells act- Corollary 2 shows the convexity of the storage assignment ing as helpers in the D2D offloading system.These APs or Femto- problem.Therefore,the optimal solution for this problem can be cells can provide low cost Internet access to nearby nodes.Thus, found by efficient algorithms such as gradient projection methods. they can be treated as if they were seeds for all content.Sup- pose that there are nA APs in the system.Then,we can change 5.2.Distributed solution Eq.(3)to F(ns.i.n.i.n)=e-ere-A.where E is the of- The Lagrangian of the storage assignment optimization problem floading efficiency of APs which can be calculated through the con- tact patterns between nodes and APs.The offloading efficiency of can be written as: Er is a function of both ns.i and nA in this scenario,because relays L(fs.r,fri.v) can also download from APs or Femtocells.However,the general structure of the problem does not change and the framework of -∑MRF(nf,n)+∑5+-1) Section 5.1 can also be applied.Using our optimization framework, tradeoffs between deploying APs and mobile helpers can be easily characterized. +Vo (h+k) (24) The systems may contain different types of helpers that have different contact patterns or different storage sizes.In these cases, each type of helpers will have its own fraction parameter fh.i for where vi.ie (0.1.....N)are Lagrangian multipliers for the con- content i in the optimization problem and each type of helper may straints. have a different offloading efficiency Eh.By Theorem 2,the general The optimal solutions ff must satisfy the KKT condi- tradeoff point for storage assignment in different types of helpers tions [37].which require can be solved when the offloading efficiency functions are concave. E+f后-1≤0.i=1,,N (25) 5.4.Practical issues ∑(+kf周)-1≤0 (26) The above optimization framework provides a way to allocate i= the storage in an offloading system.Although centralized optimiza- tions in cellular networks are possible,there are several practical 20,i=0,,N (27) issues to be considered in implementation. Number of contents:First,the number of content pieces may be very large in real systems.Therefore,solving fs.i and fr.i for (g+后-1)=0.i=1,,N (28) each content may incur high computational costs.To address this problem.we propose to group contents into a fixed number of content categories based on the popularity of the content.We (+u-）=0 observe that the solutions for different contents only depend (29) on the value of Ri.Therefore,we can aggregate contents with similar request rates into one content category and optimize over content categories to obtain approximate solutions.In practice MR9()++哈=0，i=1,,N (30) content can be grouped into bins with geometric sequences of request rates.e.g..the first bin contains contents with request rate smaller than 0.1 requests per day and the rest bins covers MR9(f)++ku.i哈=0，i=1,,N (31)】 content request rates of 0.1-0.2.0.2-0.4,0.4-0.8.....respectively. Consider the case there are I categories of contents,each with m where(and)By contents of request rate R.We can change the objective function condition Eq.(28).we see that either v=0 orf+=1 must Eq.(17)to MmiRiF(nfs.i.nfri).the constraint in Eq.(18)to be satisfied.Therefore,if we do not allocate all nodes as seeds mi(f+kifr)sI and keep all other constraints unchanged or relays for a specific content i(which meansf+f is smaller to reduce the problem size. than 1).we should have v*=0.Thus except for extremely popular Limited number of friends:Second,when the optimal solution content withf+=1.KKT conditions require: has large fr.i for some pieces of content,the subscriber may not R9(,)=-6M have enough friends with high contact rates.To address this limita- (32) tion,we add constraints,such as nfr.is5.Vi,to limit the number52 W. Wang et al. / Computer Communications 83 (2016) 45–55 Proof. To show Er(fs,i) = − ln Pr(fs,i) is concave, we have: Pr(fs,i) = Xˆ(T ) −  T 0  Yˆ(T − t) n fs,i dXˆ(t). (23) Note that Xˆ(t) is a decreasing function, therefore we have −dXˆ(t)/dt ≥ 0. Since exponential functions are log-convex,  −dXˆ(t)/dtYˆ(T − t) n fs,i is a log-convex function of fs, i on ev￾ery point t ∈ [0, T]. Taking integral over t preserves log-convexity [37], so −  T 0  Yˆ(T − t) n fs,i dXˆ(t) is also log-convex. Adding a pos￾itive constant Xˆ(T ) preserves log-convexity, thus Pr(fs, i) is log￾convex and Er(fs, i) is concave. This directly leads to the convex￾ity of the objective function as discussed above. It is clear that all the constraints in the storage assignment optimization problem in Eqs. (18)–(20) are linear, so the storage assignment problem is convex. Corollary 2 shows the convexity of the storage assignment problem. Therefore, the optimal solution for this problem can be found by efficient algorithms such as gradient projection methods. 5.2. Distributed solution The Lagrangian of the storage assignment optimization problem can be written as: L(fs,r, fr,i, ν) = N i=1 MRiF (n fs,i, n fr,i) +N i=1 νi(fs,i + fr,i − 1) +ν0  N i=1 (fs,i + ku,i fr,i) − I  (24) where νi, i ∈ {0, 1, . . ., N} are Lagrangian multipliers for the con￾straints. The optimal solutions f ∗ s,i , f ∗ r,i , ν∗ i must satisfy the KKT condi￾tions [37], which require f ∗ s,i + f ∗ r,i − 1 ≤ 0, i = 1, . . ., N (25) N i=1  f ∗ s,i + ku,i f ∗ r,i  − I ≤ 0 (26) ν∗ i ≥ 0, i = 0, . . ., N (27) ν∗ i  f ∗ s,i + f ∗ r,i − 1  = 0, i = 1, . . ., N (28) ν∗ 0  N i=1  f ∗ s,i + ku,i f ∗ r,i  − I  = 0 (29) MRiϕs (f ∗ s,i , f ∗ r,i ) + ν∗ i + ν∗ 0 = 0, i = 1, . . ., N (30) MRiϕr(f ∗ s,i , f ∗ r,i ) + ν∗ i + ku,iν∗ 0 = 0, i = 1, . . ., N (31) where ϕs (fs,i, fr,i) = ∂F (n fs,i,n fr,i) ∂ fs,i and ϕr(fs,i, fr,i) = ∂F (n fs,i,n fr,i) ∂ fr,i . By condition Eq. (28), we see that either ν∗ i = 0 or f ∗ s,i + f ∗ r,i = 1 must be satisfied. Therefore, if we do not allocate all nodes as seeds or relays for a specific content i (which means f ∗ s,i + f ∗ r,i is smaller than 1), we should have ν∗ i = 0. Thus except for extremely popular content with f ∗ s,i + f ∗ r,i = 1, KKT conditions require: Riϕs (f ∗ s,i , f ∗ r,i ) = −ν∗ 0/M (32) Riϕr(f ∗ s,i , f ∗ r,i )/ku,i = −ν∗ 0/M. (33) Note that −ν∗ 0/M is a constant for all content i. When ν∗ 0 is given, we can separately solve Eqs. (32) and (33) for each content to get the optimal allocation. If the solution has f ∗ s,i + f ∗ r,i ≥ 1, it is evident that content i is so popular that we can simply set f ∗ s,i + f ∗ r,i = 1 and ν∗ i > 0 for content i. Therefore, one way to solve the above problems is to use ν0 as a global pricing signal [38] to coordinate the distributed storage allocation fs, i and fr, i for each content i. 5.3. Extension of the optimization framework In the above discussion, we mainly focus on systems with two types of helpers, namely, seeds and relays. The optimization frame￾work in Section 5.1 can be extended to cases where there are more than two types of helpers. Consider the case where there are WiFi APs or Femtocells act￾ing as helpers in the D2D offloading system. These APs or Femto￾cells can provide low cost Internet access to nearby nodes. Thus, they can be treated as if they were seeds for all content. Sup￾pose that there are nA APs in the system. Then, we can change Eq. (3) to F (ns,i, nr,i, nA) = e−ns,iEse−nr,iEr e−nAEA , where EA is the of- floading efficiency of APs which can be calculated through the con￾tact patterns between nodes and APs. The offloading efficiency of Er is a function of both ns, i and nA in this scenario, because relays can also download from APs or Femtocells. However, the general structure of the problem does not change and the framework of Section 5.1 can also be applied. Using our optimization framework, tradeoffs between deploying APs and mobile helpers can be easily characterized. The systems may contain different types of helpers that have different contact patterns or different storage sizes. In these cases, each type of helpers will have its own fraction parameter fh, i for content i in the optimization problem and each type of helper may have a different offloading efficiency Eh. By Theorem 2, the general tradeoff point for storage assignment in different types of helpers can be solved when the offloading efficiency functions are concave. 5.4. Practical issues The above optimization framework provides a way to allocate the storage in an offloading system. Although centralized optimiza￾tions in cellular networks are possible, there are several practical issues to be considered in implementation. Number of contents: First, the number of content pieces may be very large in real systems. Therefore, solving fs, i and fr, i for each content may incur high computational costs. To address this problem, we propose to group contents into a fixed number of content categories based on the popularity of the content. We observe that the solutions for different contents only depend on the value of Ri. Therefore, we can aggregate contents with similar request rates into one content category and optimize over content categories to obtain approximate solutions. In practice, content can be grouped into bins with geometric sequences of request rates, e.g., the first bin contains contents with request rate smaller than 0.1 requests per day and the rest bins covers content request rates of 0.1–0.2, 0.2–0.4, 0.4–0.8, . . ., respectively. Consider the case there are l categories of contents, each with mi contents of request rate Ri. We can change the objective function Eq. (17) to l i=1 MmiRiF (n fs,i, n fr,i), the constraint in Eq. (18) to l i=1 mi  fs,i + ku,i fr,i  ≤ I and keep all other constraints unchanged to reduce the problem size. Limited number of friends: Second, when the optimal solution has large fr, i for some pieces of content, the subscriber may not have enough friends with high contact rates. To address this limita￾tion, we add constraints, such as nfr, i ≤ 5, ∀i, to limit the number