times the transmission range centered at the senders should the binomial expansion of (1it is easy to be disjoint.Therefore,we can measure the radio resources prove that consumed by each transmission through the area of its corre- sponding disk. 1-1-4)≤dMud (8) Consider a particular content ik.First,we calculate the area consumed by content retrieval.Under the fast mobility Therefore,the probability that the di-th client retrieves model,a chosen server will reach client dik in a single hop within a timeslot.This content delivery consumes an area content ik is no larger than (nd+1)id Mis.d of Under the iid.model,by summing the The retrieval time is thus no less than the inverse of this consumed areas over all ni clients,the average area required quantity.Note that ]之R4,4E,4 Since no scheduling scheme can improve the tradeoff by more for completing the retrieval transmissions for content ik can be bounded by∑ △2ER,4 than a factor of czlog n due to mobility randomness [8],we can finally obtain the inequality in(7). ■ d4=1 Remark:Lemma 2 shows that the average time for content Then,we calculate the area consumed by content placement. ik to reach the dis-th client after reaching the (di-1)-th client For content placement,broadcast is more efficient since it can is inversely proportional to the number of unserved clients make more replicas within the same placement range.Since nik-di+1,the average area of the corresponding retrieval the positions of nodes within a timeslot are i.i.d.,on average no region,which is reflected by term E.and the average greater than Rn nodes can receive the replicas of content number of its servers E[Mid.Note that Lemma 2 holds ik if a server of content ik broadcasts the content within the under both the fast and slow mobility models. placement rangeRiwhich consumes an area of From these two lemmas,we can derive the average delay Hence,to produce E[Mi]-nix replicas for content ik,it Wo for a given state Q.Averaging over the state space 2,we requires no less thanplacement transmissions can obtain fundamental performance bounds on the average delay and throughput under the fast mobility model,which are under the i.i.d.model.By summing the consumed areas over summarized in the following theorem.We use Knuth notation3 all these transmissions,we can show that for content ik,the in this paper. average area consumed in the placement phase is bounded by △2(EM]-n Theorem I:Under the fast mobility model,for any sch- 刀 eduling scheme,the average delay of serving all nk requests Given that all contents can be delivered within Wo timeslots is lower bounded by and the network is of unit area.the total area consumed by 2/3 content placement and content retrieval should be no greater than Wo.Moreover,since no scheduling scheme can improve ≥Θ (K∑1V (9) log n the tradeoff by more than a factor2 of ci log n due to mobility randomness,we can finally obtain the inequality in(6). and the corresponding average throughput is upper bounded Remark:The first term on the left hand side of(6)is the by average radio resources consumed by content placement,and the second term on the left hand side of(6)is the average radio x≤ Klog n 2/3 (10) resources consumed by content retrieval.Here,we measure ∑V) the radio resource consumed by each transmission through the Proof:Please refer to Appendix A. ■ required area for each transmission. Remark:The fundamental limits of performance in terms Lemma 2:Any scheduling scheme must satisfy the follow- ing inequality of throughput and delay mainly depend on two factors:the content popularity distribution and the number of requests c2 lognE Wi,dk」≥ generated by each node.Surprisingly,Theorem 1 indicates (ns-d+1)E2 Rix.dEMo.dog that delay scales non-linearly with the number of requests K, (7) which is counter-intuitive. where c2>0 is a constant. 2)Near-Optimal Performance Achieving Scheme:From the Proof:Conditioned on the event that Miservers hold analysis of Theorem 1,we find that the performance of the the replicas of content ik,the probability that the di-th client class of scheduling policies in Sec.II-C is affected by two retrieves content ik is constituted by:(a)the probability that at key parameters,i.e.,the average number of replicas E[Mi least one server moves into the retrieval region of client di is (1and (b)each of the unreached of each content ik,and the average retrieval range E of each content ik and its client dis.We now derive the optimal di+1 clients of content ik is equally likely. parameters at which the optimal performance is achieved(i.e., Since for any content ik and any of its clients dis,the retrieval area consumed by Mid servers must be smaller 3Given two functions f(n)and g(n):f(n)=O(g(n))means than the network area,we haveM1.Using lim f(n)/g(n)=c<oo;if g(n)=O(f(n)).f(n)=2(g(n)) w.h.p.:if both f(n)=2(g(n))and f(n)=O(g(n)).f(n)=e(g(n)): 2The proof of clogn is similar to that in Proposition 3 of []and omitted f(n)=o(g(n))means lim f(n)/g(n)=0.f(n)=e(g(n))means here due to page limitation. f(n)=e(g(n))when logarithmic terms are ignored.4 times the transmission range centered at the senders should be disjoint. Therefore, we can measure the radio resources consumed by each transmission through the area of its corre￾sponding disk. Consider a particular content ik. First, we calculate the area consumed by content retrieval. Under the fast mobility model, a chosen server will reach client dik in a single hop within a timeslot. This content delivery consumes an area of π∆2E[R 2 ik,dik ] 4 . Under the i.i.d. model, by summing the consumed areas over all nik clients, the average area required for completing the retrieval transmissions for content ik can be bounded by nPik dik =1 π∆2E R 2 ik,dik 4 . Then, we calculate the area consumed by content placement. For content placement, broadcast is more efficient since it can make more replicas within the same placement range. Since the positions of nodes within a timeslot are i.i.d., on average no greater than πR2 ik n nodes can receive the replicas of content ik if a server of content ik broadcasts the content within the placement range Rik , which consumes an area of π∆2R 2 ik 4 . Hence, to produce E [Mik ] − nik replicas for content ik, it requires no less than E[Mik ]−nik πR2 ik n placement transmissions under the i.i.d. model. By summing the consumed areas over all these transmissions, we can show that for content ik, the average area consumed in the placement phase is bounded by ∆2 (E[Mik ]−nik ) 4n . Given that all contents can be delivered within W¯ Q timeslots and the network is of unit area, the total area consumed by content placement and content retrieval should be no greater than W¯ Q. Moreover, since no scheduling scheme can improve the tradeoff by more than a factor2 of c1 log n due to mobility randomness, we can finally obtain the inequality in (6). Remark: The first term on the left hand side of (6) is the average radio resources consumed by content placement, and the second term on the left hand side of (6) is the average radio resources consumed by content retrieval. Here, we measure the radio resource consumed by each transmission through the required area for each transmission. Lemma 2: Any scheduling scheme must satisfy the follow￾ing inequality c2 log nE Wik,dik ≥ 1 (nik −dik +1)E2 Rik,dik E Mik,dik (7) where c2 > 0 is a constant. Proof: Conditioned on the event that Mik,dik servers hold the replicas of content ik, the probability that the dik -th client retrieves content ik is constituted by: (a) the probability that at least one server moves into the retrieval region of client dik is 1− € 1 − R2 ik,dik ŠMik,dik , and (b) each of the unreached nik− dik + 1 clients of content ik is equally likely. Since for any content ik and any of its clients dik , the retrieval area consumed by Mik,dik servers must be smaller than the network area, we have R2 ik,dik Mik,dik < 1. Using 2The proof of c1 log n is similar to that in Proposition 3 of [8], and omitted here due to page limitation. the binomial expansion of € 1 − R2 ik,dik ŠMik,dik , it is easy to prove that 1 − € 1 − R 2 ik,dik ŠMik,dik ≤ R 2 ik,dik Mik,dik . (8) Therefore, the probability that the dik -th client retrieves content ik is no larger than (nik − dik + 1) R2 ik,dik Mik,dik . The retrieval time is thus no less than the inverse of this quantity. Note that E[ 1 R2 ik,dik ·Mik,dik ] ≥ 1 E2[Rik,dik ]E[Mik,dik ] . Since no scheduling scheme can improve the tradeoff by more than a factor of c2log n due to mobility randomness [8], we can finally obtain the inequality in (7). Remark: Lemma 2 shows that the average time for content ik to reach the dik -th client after reaching the (dik−1)-th client is inversely proportional to the number of unserved clients nik − dik + 1, the average area of the corresponding retrieval region, which is reflected by term E 2 [Rik,dik ], and the average number of its servers E[Mik,dik ]. Note that Lemma 2 holds under both the fast and slow mobility models. From these two lemmas, we can derive the average delay W¯ Q for a given state Q. Averaging over the state space A, we can obtain fundamental performance bounds on the average delay and throughput under the fast mobility model, which are summarized in the following theorem. We use Knuth notation3 in this paper. Theorem 1: Under the fast mobility model, for any sch￾eduling scheme, the average delay of serving all nK requests is lower bounded by W¯ ≥ Θ „€ K PI i=1 √pi Š2/3 log n Ž (9) and the corresponding average throughput is upper bounded by λ¯ ≤ Θ „ √3 K log n €PI i=1 √pi Š2/3 Ž . (10) Proof: Please refer to Appendix A. Remark: The fundamental limits of performance in terms of throughput and delay mainly depend on two factors: the content popularity distribution and the number of requests generated by each node. Surprisingly, Theorem 1 indicates that delay scales non-linearly with the number of requests K, which is counter-intuitive. 2) Near-Optimal Performance Achieving Scheme: From the analysis of Theorem 1, we find that the performance of the class of scheduling policies in Sec. II-C is affected by two key parameters, i.e., the average number of replicas E [Mik ] of each content ik, and the average retrieval range E Rik,dik of each content ik and its client dik . We now derive the optimal parameters at which the optimal performance is achieved (i.e., 3Given two functions f(n) and g(n): f(n) = O(g(n)) means lim n→∞ f(n)/g(n) = c < ∞; if g(n) = O(f(n)), f(n) = Ω(g(n)) w.h.p.; if both f(n) = Ω(g(n)) and f(n) = O(g(n)), f(n) = Θ(g(n)); f (n) = o (g (n)) means lim n→∞ f (n) /g (n) = 0. f(n) = Θ( e g(n)) means f(n) = Θ(g(n)) when logarithmic terms are ignored.