3 of fundamental limits.Assume that there is a centralized possible request states is scheduler that has all the information about the current and past status of the network.Based on the information,the 币EWo=>币oP(Q) (4 centralized scheduler can schedule any radio transmission in QER the current and future timeslots. where P(Q)is the probability of being state O. During a timeslot,for each content i not being successfully Throughput:For a given request state QE2,the average delivered and each unserved client dis of content ik,the time to serve K requests for each node is Wo.Hence,the scheduler performs the following operations. throughput for state Q is The average throughput Content Placement:At the beginning of each timeslot, over all possible request states is the scheduler decides whether to replicate content i.If 入Eial=∑oP(Q). (5) so,it chooses one or multiple existing servers of content QEX ik to replicate content ik and one or multiple nodes to become new servers of content ik.It also schedules radio III.PERFORMANCE ANALYSIS UNDER TWO MOBILITY transmissions to forward the replicas from the chosen MODELS servers to the new servers. Content Retrieval:At the beginning of each timeslot. To illustrate the transmission procedure,we first introduce the scheduler decides whether to deliver content ik to some notations.For a given request state Q.denote Misd client di If so,the scheduler selects a server of content as the number of mobile servers carrying replicas of content ik and schedules a radio transmission to forward content ik when content ik reaches the dis-th client,where di= ik from the selected server to client di. 1,...,ni,and denote Mio as the number of mobile servers Please note that this centralized scheduler requires consid- carrying replicas of content ik when content ik is retrieved by erable coordinations among mobile nodes and involves com- its last client.Note thatMi=Mi.Let Wi.d plex controls,and therefore is only adopted for the analysis be the number of timeslots it takes for content ik to reach its of fundamental performance limits.Later,we will consider dis-th client after reaching its (dis-1)-th client.Then,we distributed achievable schemes(for different mobility models), have WWiFor notational simplicity,in which are more practical for real MANETs. this paper.we will omit the subscriptQ inMM RiQ.Rd WsdQW and Wo where there is no confusion.Note that,in the following performance analysis, D.Definitions and Notations we consider the i.i.d.mobility model. Request state space:Note that the number of request- s nis for content ik is a random variable.Define 2A A.Fast Mobility {(ni)i.(2)is satisfied}as the request state space (at In this subsection,we investigate the optimal throughput the initial stage),where {1,.,I}and K1,...K). and delay under fast mobility,and then design a distributed Content placement range:For a given request state O E 2, scheme which achieves a throughput-delay tradeoff close to we define the placement range Ris for content ik as the the optimal one. range within which a replica of content ik can be transmitted 1)Optimal Performance Bound:For different schemes,the to one or multiple nodes in content placement. abovementioned parameters may be different.However,under Content retrieval range:For a given request state 2, fast mobility,any feasible scheme in the class of scheduling we define the retrieval range Rid of client di for content policies illustrated in Sec II-C should satisfy the two funda- ik as the range within which content ik can be retrieved mental inequalities presented in Lemma 1 and Lemma 2,for by client dig in content retrieval.The retrieval region of a a given request state Q=(ni)ieZ,kEK. client for a content is the disk centered at this client with the Lemma I:Under the fast mobility model,any scheduling corresponding retrieval range as the radius. scheme must satisfy the following inequality Feasible retrieval pair:A pair of nodes (v,w)is defined to be a feasible retrieval pair for content ik in a given timeslot,if and only if the following conditions hold:i)node w is a client i=1k=1 i=1k=1d4=1 for content ik;ii)node v is a server for content ik;and iii)v ≤ci Wo logn is in the retrieval range of w for content i in this timeslot. Delay:For a given request state QE2,the delay WiQ (6 of content ik is defined as the time it takes to serve all nik where c>0 is a constant,and Wo is the average number of timeslots it takes to serve all nK requests. requests for content i.The delay of serving all nk requests for request state Q is given by Proof:Since the scheduler performs two types of op- erations (i.e.,content placement and content retrieval),we Wo-pk W.g (3) calculate how many radio resources these two types of trans- missions consume under the i.i.d.mobility model.To account Due to the randomness of the mobility model,for a given for interference among simultaneous transmissions,we employ request state QE2,Wo is a random variable.Denote Wo the protocol model,as in [15].In particular,for concurrent E[Wo].The average delay of serving all nK requests over all transmissions,.disks of radius号（△>0 is a guard factor)3 of fundamental limits. Assume that there is a centralized scheduler that has all the information about the current and past status of the network. Based on the information, the centralized scheduler can schedule any radio transmission in the current and future timeslots. During a timeslot, for each content ik not being successfully delivered and each unserved client dik of content ik, the scheduler performs the following operations. • Content Placement: At the beginning of each timeslot, the scheduler decides whether to replicate content ik. If so, it chooses one or multiple existing servers of content ik to replicate content ik and one or multiple nodes to become new servers of content ik. It also schedules radio transmissions to forward the replicas from the chosen servers to the new servers. • Content Retrieval: At the beginning of each timeslot, the scheduler decides whether to deliver content ik to client dik . If so, the scheduler selects a server of content ik and schedules a radio transmission to forward content ik from the selected server to client dik . Please note that this centralized scheduler requires consid￾erable coordinations among mobile nodes and involves com￾plex controls, and therefore is only adopted for the analysis of fundamental performance limits. Later, we will consider distributed achievable schemes (for different mobility models), which are more practical for real MANETs. D. Definitions and Notations Request state space: Note that the number of request￾s nik for content ik is a random variable. Define A , {(nik )i∈I,k∈K|(2) is satisfied} as the request state space (at the initial stage), where I , {1, ..., I} and K , {1, ..., K}. Content placement range: For a given request state Q ∈ A, we define the placement range Rik,Q for content ik as the range within which a replica of content ik can be transmitted to one or multiple nodes in content placement. Content retrieval range: For a given request state Q ∈ A, we define the retrieval range Rik,dik ,Q of client dik for content ik as the range within which content ik can be retrieved by client dik in content retrieval. The retrieval region of a client for a content is the disk centered at this client with the corresponding retrieval range as the radius. Feasible retrieval pair: A pair of nodes (v, w) is defined to be a feasible retrieval pair for content ik in a given timeslot, if and only if the following conditions hold: i) node w is a client for content ik; ii) node v is a server for content ik; and iii) v is in the retrieval range of w for content ik in this timeslot. Delay: For a given request state Q ∈ A, the delay Wik,Q of content ik is defined as the time it takes to serve all nik requests for content ik. The delay of serving all nK requests for request state Q is given by WQ = max i∈I,k∈K Wik,Q. (3) Due to the randomness of the mobility model, for a given request state Q ∈ A, WQ is a random variable. Denote W¯ Q , E[WQ]. The average delay of serving all nK requests over all possible request states is W¯ , E[W¯ Q] = X Q∈A W¯ QP(Q), (4) where P(Q) is the probability of being state Q. Throughput: For a given request state Q ∈ A, the average time to serve K requests for each node is W¯ Q. Hence, the throughput for state Q is λ¯Q = K W¯ Q . The average throughput over all possible request states is λ¯ , E[λ¯Q] = X Q∈A λ¯QP(Q). (5) III. PERFORMANCE ANALYSIS UNDER TWO MOBILITY MODELS To illustrate the transmission procedure, we first introduce some notations. For a given request state Q, denote Mik,dik ,Q as the number of mobile servers carrying replicas of content ik when content ik reaches the dik -th client, where dik = 1, ..., nik , and denote Mik,Q as the number of mobile servers carrying replicas of content ik when content ik is retrieved by its last client. Note that Mik,Q = Mik,nik ,Q. Let Wik,dik ,Q be the number of timeslots it takes for content ik to reach its dik -th client after reaching its (dik − 1)-th client. Then, we have Wik,Q = Pnik dik =1 Wik,dik ,Q. For notational simplicity, in this paper, we will omit the subscript Q in Mik,Q, Mik,dik ,Q, Rik,Q, Rik,dik ,Q, Wik,dik ,Q, Wik,Q and WQ where there is no confusion. Note that, in the following performance analysis, we consider the i.i.d. mobility model. A. Fast Mobility In this subsection, we investigate the optimal throughput and delay under fast mobility, and then design a distributed scheme which achieves a throughput-delay tradeoff close to the optimal one. 1) Optimal Performance Bound: For different schemes, the abovementioned parameters may be different. However, under fast mobility, any feasible scheme in the class of scheduling policies illustrated in Sec II-C should satisfy the two funda￾mental inequalities presented in Lemma 1 and Lemma 2, for a given request state Q = (nik )i∈I,k∈K. Lemma 1: Under the fast 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 π∆2E R 2 ik,dik 4 ≤ c1W¯ Q log n (6) where c1 > 0 is a constant, and W¯ Q is the average number of timeslots it takes to serve all nK requests. Proof: Since the scheduler performs two types of op￾erations (i.e., content placement and content retrieval), we calculate how many radio resources these two types of trans￾missions consume under the i.i.d. mobility model. To account for interference among simultaneous transmissions, we employ the protocol model, as in [15]. In particular, for concurrent transmissions, disks of radius ∆ 2 (∆ > 0 is a guard factor)