6 with higher popularity are allowed to have more replicas,their B.Slow Mobility sources will be assigned with a larger transmission range so that the source can broadcast the content to more servers.For In this subsection,we investigate the optimal throughput example,the most popular content is broadcasted within the and delay performance under slow mobility and then design largest cell,in which its new servers are marked by red.Fig. a general near-optimal scheme which achieves a performance 1(b)shows the cell partition in a timeslot of the retrieval phase. close to the optimal one. Since a more popular content has more servers and clients,its 1)Optimal Performance Bound:When the speed of node clients can meet its servers in a smaller region.For example. mobility is much slower than the transmission rate,in a the most popular content can be retrieved from the red servers retrieval transmission,a content may be transmitted from a in the smallest cell. chosen server to a client over multiple hops.In other words, We now show the achievable performance of Scheme I in multiple relays may be involved in a retrieval process.Denote the following theorem. hikd as the number of hops for content ik to be delivered Theorem 2:Under Scheme I,the average delay of serving from a chosen server to client diDenote as the length ik,din 2/3 of the h-th hop.whereh1.Similar to Lemma all nK requests is upper bounded by(K)logn). 1,the following lemma shows a constraint on radio resource i1 consumptions under slow mobility,given a request state O. Proof:Under Scheme I,contents are transmitted in two phases,i.e.,placement phase and retrieval phase. Lemma 3:Under the slow mobility model,any scheduling scheme must satisfy the following inequality First.we show that each content is will have at least M copies at the end of the placement phase.Note that M:is 5△(LM]-+ the same for all k.For a server of a content ik,if it is =1k=1 4n scheduled to replicate content ik,it is assigned with a cell of arealogn.This area contains M:logn nodes on average. 4 ≤a1 Wo log n, implying containing at least Mi nodes.According to Scheme 1k=1d4k=1h=1 I.on averageM;logn copies across all classes (17) of contents are generated,in the placement phase.Under the The proof of Lemma 3 is similar to that of Lemma 1,and protocol model,the number of cells that may interfere with any is omitted due to page limiation.The average radio resources given cell is upper bounded by a constant which is independent consumed by content placement under slow mobility are the of n and is no greater than 9 [20].Therefore,each cell can be same as the one under fast mobility,which is reflected by activated once at most every 9 timeslots,and there are totally the first term on the left hand side of inequality (17).The no less thann copies generated in each timeslot.It then main difference exists in content retrieval.In particular,here follows that the total time required for the placement phase is we calculate the consumed radio resources of a multi-hop no greater than9(②！1∑1√只)2 otimeslots.. transmission instead of a straight-line single-hop transmission in each retrieval transmission,which is reflected by the second Then,we show that the requests of all clients will be satisfied at the end of the retrieval phase.Note that after term on the left hand side of inequality (17). the placement phase,there are Mi servers for each content Recall that Lemma 2 holds under both the fast and slow ik.For a client of content ik,the probability of finding at mobility models.Based on Lemma 2 and Lemma 3,we can least one server within its retrieval range is 1-(1-2). obtain fundamental performance bounds on the average delay and throughput under the slow mobility model. The term (1infers the probability that no server of Theorem 3:Under the slow mobility model.for any content ig falls in the retrieval range of client di.Similarly, scheduling scheme. the average delay of serving all nk each cell can be activated once at most every 9 timeslots. requests is lower bounded by Therefore,the probability that client di can be served is at least1(1).which can be approximated as (】 (18) MiR?due to R2=o(1)and R2Mi o(1).Then the average time to reach client dik is equal to the inverse of this quantity.After plugging in the values of Mi in(12)and and the corresponding average throughput is upper bounded Rin(16).we can obtain the value of which are the by same for all i.Therefore,it is easy to show that,to serve all ≤ log n (19) the n clients,the average retrieval delay is upper bounded by 9(V) ）logn. Proof:Please refer to Appendix B. ■ Combining the placement delay and the retrieval delay,we can show that the total delay of serving all requests in is 2)Near-Optimal Performance Achieving Scheme:The upper bounded by(Ea1∑k1V-）logn), 23 analysis of Theorem 3 provides guidelines on the design of ■ scheduling schemes for slow mobility.Similar to the approach Note that there exists a gap of logn between the achievable for fast mobility,we first identify the optimal choices of the result and the performance limit,which is mainly due to the two key scheduling parameters for each content ik,by studying randomness of node mobility [8]. the conditions under which the inequalities in(43-45)and(49)6 with higher popularity are allowed to have more replicas, their sources will be assigned with a larger transmission range so that the source can broadcast the content to more servers. For example, the most popular content is broadcasted within the largest cell, in which its new servers are marked by red. Fig. 1(b) shows the cell partition in a timeslot of the retrieval phase. Since a more popular content has more servers and clients, its clients can meet its servers in a smaller region. For example, the most popular content can be retrieved from the red servers in the smallest cell. We now show the achievable performance of Scheme I in the following theorem. Theorem 2: Under Scheme I, the average delay of serving all nK requests is upper bounded by Θ € (K P I i=1 √pi) 2/3 log n Š . Proof: Under Scheme I, contents are transmitted in two phases, i.e., placement phase and retrieval phase. First, we show that each content ik will have at least Mi copies at the end of the placement phase. Note that Mi is the same for all k. For a server of a content ik, if it is scheduled to replicate content ik, it is assigned with a cell of area Mi n log n. This area contains Mi log n nodes on average, implying containing at least Mi nodes. According to Scheme I, on average PI i=1 PK k=1 Mi log n copies across all classes of contents are generated, in the placement phase. Under the protocol model, the number of cells that may interfere with any given cell is upper bounded by a constant which is independent of n and is no greater than 9 [20]. Therefore, each cell can be activated once at most every 9 timeslots, and there are totally no less than 1 9 n copies generated in each timeslot. It then follows that the total time required for the placement phase is no greater than 9 €PI i=1 PK k=1 Èni n Š2/3 log n timeslots. Then, we show that the requests of all clients will be satisfied at the end of the retrieval phase. Note that after the placement phase, there are Mi servers for each content ik. For a client of content ik, the probability of finding at least one server within its retrieval range is 1 − € 1 − R2 i ŠMi . The term € 1 − R2 i ŠMi infers the probability that no server of content ik falls in the retrieval range of client dik . Similarly, each cell can be activated once at most every 9 timeslots. Therefore, the probability that client dik can be served is at least 1 9 € 1 − € 1 − R2 i ŠMi Š , which can be approximated as 1 9MiR2 i due to R2 i = o(1) and R2 i Mi = o(1). Then the average time to reach client dik is equal to the inverse of this quantity. After plugging in the values of Mi in (12) and Ri in (16), we can obtain the value of 9 MiR2 i , which are the same for all i. Therefore, it is easy to show that, to serve all the n clients, the average retrieval delay is upper bounded by 9 €PI i=1 PK k=1 Èni n Š2/3 log n. Combining the placement delay and the retrieval delay, we can show that the total delay of serving all requests in Q is upper bounded by Θ €€PI i=1 PK k=1 Èni n Š2/3 log n Š . Note that there exists a gap of log2 n between the achievable result and the performance limit, which is mainly due to the randomness of node mobility [8]. B. Slow Mobility In this subsection, we investigate the optimal throughput and delay performance under slow mobility and then design a general near-optimal scheme which achieves a performance close to the optimal one. 1) Optimal Performance Bound: When the speed of node mobility is much slower than the transmission rate, in a retrieval transmission, a content may be transmitted from a chosen server to a client over multiple hops. In other words, multiple relays may be involved in a retrieval process. Denote hik,dik as the number of hops for content ik to be delivered from a chosen server to client dik . Denote l h ik,dik as the length of the h-th hop, where h = 1, ..., hik,dik . Similar to Lemma 1, the following lemma shows a constraint on radio resource consumptions under slow mobility, given a request state Q. Lemma 3: Under the slow mobility model, any scheduling scheme must satisfy the following inequality P I i=1 P K k=1 ∆2 (E[Mik ]−nik ) 4n + P I i=1 P K k=1 nPik dik =1 hikP,dik h=1 π∆2E €l h ik,dik Š2 4 ≤ a1W¯ Q log n. (17) The proof of Lemma 3 is similar to that of Lemma 1, and is omitted due to page limiation. The average radio resources consumed by content placement under slow mobility are the same as the one under fast mobility, which is reflected by the first term on the left hand side of inequality (17). The main difference exists in content retrieval. In particular, here we calculate the consumed radio resources of a multi-hop transmission instead of a straight-line single-hop transmission in each retrieval transmission, which is reflected by the second term on the left hand side of inequality (17). Recall that Lemma 2 holds under both the fast and slow mobility models. Based on Lemma 2 and Lemma 3, we can obtain fundamental performance bounds on the average delay and throughput under the slow mobility model. Theorem 3: Under the slow mobility model, for any scheduling scheme, the average delay of serving all nK requests is lower bounded by W¯ ≥ Θ „ K log n X I i=1 p 2 3 i !3/4Ž (18) and the corresponding average throughput is upper bounded by λ¯ ≤ Θ „ K 1 4 log n PI i=1 p 2/3 i !3/4Ž . (19) Proof: Please refer to Appendix B. 2) Near-Optimal Performance Achieving Scheme: The analysis of Theorem 3 provides guidelines on the design of scheduling schemes for slow mobility. Similar to the approach for fast mobility, we first identify the optimal choices of the two key scheduling parameters for each content ik, by studying the conditions under which the inequalities in (43-45) and (49)