Asymptotic Analysis on Content Placement and Retrieval in MANETs

Asymptotic Analysis on Content Placement and Retrieval in mANeTs Jingjing Luo',Jinbei Zhangt,Ying Cuit,Li Yut,Xinbing Wang iSchool of Electronic Information and Communications,Huazhong University of Science and Technology,China Department of Electronic Engineering,Shanghai Jiao Tong University,China Email:fluojingjing,hustlyu}@hust.edu.cn,fabelchina,cuiying,xwang8}@sjtu.edu.cn Abstract-Recently,performance analysis for large-scale networks?Content-centric MANETs differ from traditional content-centric mobile ad hoc networks (MANETs)has received user-centric MANETs in the following two aspects.First,in intense attention.In content-centric MANETs,content delivery content-centric MANETs,content delivery is based on content consists of two operations,i.e.,content placement and content retrieval,which may involve different network costs.However, identifiers rather than locations of mobile users.Any user who existing performance studies in content-centric MANETs mainly has a content can act as a server for this content.Second. focus on content retrieval,and hence may not reflect the impact contents have heterogeneous popularity,which brings the need of content placement.In this paper,we investigate the asymptotic to design popularity-aware policies.Therefore,it is important throughput and delay performance by considering the two to understand how these new features fundamentally affect the operations of possibly different network costs.Specifically,we introduce a general weighted sum delay cost of content placement performance of content-centric MANETs. and content retrieval as the delay performance metric.We Recently,some initial work has already considered the consider an arbitrary content popularity distribution and study performance analysis of content-centric wireless networks. two mobility models in different time-scales,i.e.,fast and slow For example,in [13].Gitzenis et al.studied the required mobility.For each mobility model,we characterize the impacts link capacity for a static wireless network,where contents of the network parameters on the network performance.By optimizing the content placement and retrieval for contents of are requested according to a Zipf distribution [14].They different popularity,we design a general near-optimal scheme, demonstrated that caching contents can be beneficial for the the parameters of which reflect the delay weights of the two sustainability of networks expanding in size.This promising phases.We show that the network performance improves as the result suggests that CCN may break the bottleneck of wire- number of cached replicas increases until the number reaches a threshold.Finally,we show that our results are general and can less communications,as the traditional user-centric network incorporate some existing results as special cases. is shown to be non-scalable [15].In [161.the asymptotic throughput of content-centric wireless networks with given content lifetime was studied.It was shown that increasing the I.INTRODUCTION content lifetime with the size of the network may result in Nowadays,instead of being concerned about communi- higher throughput.On the other hand,the impact of mobility cating with specific hosts,users are mainly interested in on content-centric wireless networks was investigated in [17]. obtaining contents they desire.To reflect this change,content- In particular,it was assumed that nodes independently and centric networking (CCN)[1]-[3]is proposed as a promising uniformly visit the network and the cache size of each node architecture for future Internet,which enables efficient content for storing contents is limited.Under this assumption,it was delivery based on content identifiers rather than host address- shown that the best throughput-delay tradeoff is achieved in es.This emerging CCN is currently changing the landscape the quasi-static case and mobility has a negative impact on the of the research for wireline networks.As direct device-to- network performance.This is quite counter-intuitive,as it is device (D2D)data sharing among mobile users is increasingly well known that mobility can improve the performance of the popular,CCN is also showing great potentials in designing traditional user-centric MANETs [61. infrastructure-less mobile environments like MANETs [4].[5]. In content-centric MANETs.content delivery consists of The performance investigation of content-centric MANETs is two operations,i.e.,content placement and content retrieval. therefore of great interest. These two operations may proceed concurrently or at different In traditional user-centric MANETs,the mobility of users periods during which the traffic load may vary significantly, can bring a dramatic improvement in throughput since mobile and hence result in different consumptions of network re- users can store packets and physically carry them while sources.For example,units of transmission costs in peak- moving around the network [6].This improvement comes hour and off-peak hour may be different.However,in wireless at the cost of an excessive delay.Therefore,there exists a CCNs,placement and retrieval are usually considered sepa- tradeoff between throughput and delay,which has been widely rately [13][16][17].Furthermore,in [13][16][17],for ease studied in related work on user-centric MANETs [7]-[12].of analysis,placement is assumed to be given and free,and An interesting question then is:can content-centric MANETs only retrieval cost is considered in the performance analysis. further improve the tradeoff by taking advantage of both These models may be valid when mainly focusing on content user mobility and key features of content-centric wireless retrieval.However,since placement also consumes network

1 Asymptotic Analysis on Content Placement and Retrieval in MANETs Jingjing Luo† , Jinbei Zhang‡ , Ying Cui‡ , Li Yu† , Xinbing Wang‡ †School of Electronic Information and Communications, Huazhong University of Science and Technology, China ‡Department of Electronic Engineering, Shanghai Jiao Tong University, China Email: †{luojingjing, hustlyu}@hust.edu.cn, ‡{abelchina, cuiying, xwang8}@sjtu.edu.cn Abstract—Recently, performance analysis for large-scale content-centric mobile ad hoc networks (MANETs) has received intense attention. In content-centric MANETs, content delivery consists of two operations, i.e., content placement and content retrieval, which may involve different network costs. However, existing performance studies in content-centric MANETs mainly focus on content retrieval, and hence may not reflect the impact of content placement. In this paper, we investigate the asymptotic throughput and delay performance by considering the two operations of possibly different network costs. Specifically, we introduce a general weighted sum delay cost of content placement and content retrieval as the delay performance metric. We consider an arbitrary content popularity distribution and study two mobility models in different time-scales, i.e., fast and slow mobility. For each mobility model, we characterize the impacts of the network parameters on the network performance. By optimizing the content placement and retrieval for contents of different popularity, we design a general near-optimal scheme, the parameters of which reflect the delay weights of the two phases. We show that the network performance improves as the number of cached replicas increases until the number reaches a threshold. Finally, we show that our results are general and can incorporate some existing results as special cases. I. INTRODUCTION Nowadays, instead of being concerned about communi￾cating with specific hosts, users are mainly interested in obtaining contents they desire. To reflect this change, content￾centric networking (CCN) [1]–[3] is proposed as a promising architecture for future Internet, which enables efficient content delivery based on content identifiers rather than host address￾es. This emerging CCN is currently changing the landscape of the research for wireline networks. As direct device-to￾device (D2D) data sharing among mobile users is increasingly popular, CCN is also showing great potentials in designing infrastructure-less mobile environments like MANETs [4], [5]. The performance investigation of content-centric MANETs is therefore of great interest. In traditional user-centric MANETs, the mobility of users can bring a dramatic improvement in throughput since mobile users can store packets and physically carry them while moving around the network [6]. This improvement comes at the cost of an excessive delay. Therefore, there exists a tradeoff between throughput and delay, which has been widely studied in related work on user-centric MANETs [7]–[12]. An interesting question then is: can content-centric MANETs further improve the tradeoff by taking advantage of both user mobility and key features of content-centric wireless networks? Content-centric MANETs differ from traditional user-centric MANETs in the following two aspects. First, in content-centric MANETs, content delivery is based on content identifiers rather than locations of mobile users. Any user who has a content can act as a server for this content. Second, contents have heterogeneous popularity, which brings the need to design popularity-aware policies. Therefore, it is important to understand how these new features fundamentally affect the performance of content-centric MANETs. Recently, some initial work has already considered the performance analysis of content-centric wireless networks. For example, in [13], Gitzenis et al. studied the required link capacity for a static wireless network, where contents are requested according to a Zipf distribution [14]. They demonstrated that caching contents can be beneficial for the sustainability of networks expanding in size. This promising result suggests that CCN may break the bottleneck of wire￾less communications, as the traditional user-centric network is shown to be non-scalable [15]. In [16], the asymptotic throughput of content-centric wireless networks with given content lifetime was studied. It was shown that increasing the content lifetime with the size of the network may result in higher throughput. On the other hand, the impact of mobility on content-centric wireless networks was investigated in [17]. In particular, it was assumed that nodes independently and uniformly visit the network and the cache size of each node for storing contents is limited. Under this assumption, it was shown that the best throughput-delay tradeoff is achieved in the quasi-static case and mobility has a negative impact on the network performance. This is quite counter-intuitive, as it is well known that mobility can improve the performance of the traditional user-centric MANETs [6]. In content-centric MANETs, content delivery consists of two operations, i.e., content placement and content retrieval. These two operations may proceed concurrently or at different periods during which the traffic load may vary significantly, and hence result in different consumptions of network re￾sources. For example, units of transmission costs in peak￾hour and off-peak hour may be different. However, in wireless CCNs, placement and retrieval are usually considered sepa￾rately [13] [16] [17]. Furthermore, in [13] [16] [17], for ease of analysis, placement is assumed to be given and free, and only retrieval cost is considered in the performance analysis. These models may be valid when mainly focusing on content retrieval. However, since placement also consumes network

3 resources,we are thus motivated to jointly consider placement normalized to 1.In each timeslot,each node has at most and retrieval in this paper.In addition,the asymmetric features one opportunity to transmit one content.We consider the (i.e..difference on the units of delay costs)in these two i.i.d.mobility model [19].In particular,at the beginning of operations should also be explored to enrich our understanding each timeslot,each node randomly and uniformly chooses its of content-centric MANETs.Therefore,in this paper,we are location within the unit square.The position of each node interested in addressing the following questions: is independent from timeslot to timeslot,and independent When both the costs of content placement and content of those of the other nodes.Two mobility time scales are retrieval are considered,does the benefit of CCN still considered in this paper,ie.,fast mobiliry [19]and slow exist?What is the optimal throughput and delay tradeoff mobiliry [7].[8].Fast mobility means that nodes move in in content-centric MANETs? the same time scale as content transmissions,i.e..a content When the units of delay costs of content placement can be transmitted over only one-hop in each timeslot.Slow and content retrieval are different,how can we optimize mobility means that nodes move in a much slower time scale content placement and content retrieval to achieve the than content transmissions,i.e.,a content can be transmitted optimal tradeoff? over multiple hops in each timeslot.In general,fast mobility In this paper,we investigate the asymptotic throughput and can model the scenarios where the transmission time of a delay performance in a content-centric MANET by consider- content is on the same order of the time for a node moving ing both content placement and content retrieval of possibly from one location to another,e.g.,vehicle mobility.And slow different network costs.We consider an arbitrary content pop- mobility can model the scenarios where the transmission time ularity distribution and study two mobility models in different of a content is much smaller than the time for a node moving time-scales,i.e.,fast and slow mobility.Our main contributions from one location to another,e.g.,human mobility. are summarized as follows. B.Traffic Pattern We jointly consider content placement (which has been so Assume that initially M contents are randomly and uniform- far neglected in the related studies)and content retrieval, ly stored in n nodes,and each node independently requests K and allow the units of their delay costs to be different.We different contents according to a general distribution of content introduce a weighted sum delay cost of content delivery popularity.We assume that all contents have the same length.! as the delay performance metric,and analyze the optimal We refer to a node requesting a content as a client of this throughput and delay performance.Our general model content.After the initial stage,the contents can be replicated. covers two special cases,i.e.,content placement is free transmitted to other nodes,and stored in their caches.Each and content placement has the same unit of delay cost as node carrying a replica or the original version of a content content retrieval. acts as a server helping the delivery of this content.We say We design a distributed scheme which achieves a a content is successfully delivered if and only if it is received throughput-delay tradeoff close to the optimal one.The by all its clients. parameters in the proposed scheme reflect the two weight- We assume there are I popularity classes of contents.Let s (corresponding to content placement and content re-pi>0 denote the popularity of class i.We allow an arbitrary trieval,respectively)in the weighted sum delay cost. popularity distribution satisfying the following equation: We show that the optimal content placement has a threshold-based structure.In particular,the network per- ∑A=1 (1) formance will improve as the number of cached replicas increases until the number reaches a threshold.Fur- Without loss of generality,we assume pi decreases with i. Each popularity class consists of K=M/I contents.Each thermore,we derive the closed-form expressions of the node independently generates K requests,each of which is thresholds under fast and slow mobilities.From the for a content in class i with probability pi/K.Denote ik as expressions,we can clearly see how the thresholds scale the k-th content in the i-th class and ni as the number of with the network parameters. requests for content ik.Therefore,we have The remainder of this paper is organized as follows.In Section II,we present the network model and some defini- ∑∑m=nk (2) tions.In Section II,we conduct asymptotic throughput and delay analysis under two mobility models,and propose near- Remark:Note that,for ease of illustration,we assume the optimal performance achieving schemes.We further establish number of requests generated by each node is equal to the the fundamental impacts of the cache size on the placement number of contents in each popularity class.Our approach can cost in Section IV.Discussions on the main findings and the be readily applied to more general cases,where the number of comparisons with the existing results are laid out in Section requests generated by each node and the number of contents V.Finally,we conclude this paper in Section VI. in each class are different C.Scheduling Scheme II.NETWORK MODEL AND DEFINITIONS In this part,we give an overview of a class of centralized A.Network and Mobility Model scheduling policies,which we will consider in the analysis We consider a MANET with n nodes moving in a unit Our analytical results can be extended to the case of different content square region.Time is divided into timeslots with slot duration sizes,by splitting each content into segments of unit length

2 resources, we are thus motivated to jointly consider placement and retrieval in this paper. In addition, the asymmetric features (i.e., difference on the units of delay costs) in these two operations should also be explored to enrich our understanding of content-centric MANETs. Therefore, in this paper, we are interested in addressing the following questions: • When both the costs of content placement and content retrieval are considered, does the benefit of CCN still exist? What is the optimal throughput and delay tradeoff in content-centric MANETs? • When the units of delay costs of content placement and content retrieval are different, how can we optimize content placement and content retrieval to achieve the optimal tradeoff? In this paper, we investigate the asymptotic throughput and delay performance in a content-centric MANET by consider￾ing both content placement and content retrieval of possibly different network costs. We consider an arbitrary content pop￾ularity distribution and study two mobility models in different time-scales, i.e., fast and slow mobility. Our main contributions are summarized as follows. • We jointly consider content placement (which has been so far neglected in the related studies) and content retrieval, and allow the units of their delay costs to be different. We introduce a weighted sum delay cost of content delivery as the delay performance metric, and analyze the optimal throughput and delay performance. Our general model covers two special cases, i.e., content placement is free and content placement has the same unit of delay cost as content retrieval. • We design a distributed scheme which achieves a throughput-delay tradeoff close to the optimal one. The parameters in the proposed scheme reflect the two weight￾s (corresponding to content placement and content re￾trieval, respectively) in the weighted sum delay cost. • We show that the optimal content placement has a threshold-based structure. In particular, the network per￾formance will improve as the number of cached replicas increases until the number reaches a threshold. Fur￾thermore, we derive the closed-form expressions of the thresholds under fast and slow mobilities. From the expressions, we can clearly see how the thresholds scale with the network parameters. The remainder of this paper is organized as follows. In Section II, we present the network model and some defini￾tions. In Section III, we conduct asymptotic throughput and delay analysis under two mobility models, and propose near￾optimal performance achieving schemes. We further establish the fundamental impacts of the cache size on the placement cost in Section IV. Discussions on the main findings and the comparisons with the existing results are laid out in Section V. Finally, we conclude this paper in Section VI. II. NETWORK MODEL AND DEFINITIONS A. Network and Mobility Model We consider a MANET with n nodes moving in a unit square region. Time is divided into timeslots with slot duration normalized to 1. In each timeslot, each node has at most one opportunity to transmit one content. We consider the i.i.d. mobility model [19]. In particular, at the beginning of each timeslot, each node randomly and uniformly chooses its location within the unit square. The position of each node is independent from timeslot to timeslot, and independent of those of the other nodes. Two mobility time scales are considered in this paper, i.e., fast mobility [19] and slow mobility [7], [8]. Fast mobility means that nodes move in the same time scale as content transmissions, i.e., a content can be transmitted over only one-hop in each timeslot. Slow mobility means that nodes move in a much slower time scale than content transmissions, i.e., a content can be transmitted over multiple hops in each timeslot. In general, fast mobility can model the scenarios where the transmission time of a content is on the same order of the time for a node moving from one location to another, e.g., vehicle mobility. And slow mobility can model the scenarios where the transmission time of a content is much smaller than the time for a node moving from one location to another, e.g., human mobility. B. Traffic Pattern Assume that initially M contents are randomly and uniform￾ly stored in n nodes, and each node independently requests K different contents according to a general distribution of content popularity. We assume that all contents have the same length.1 We refer to a node requesting a content as a client of this content. After the initial stage, the contents can be replicated, transmitted to other nodes, and stored in their caches. Each node carrying a replica or the original version of a content acts as a server helping the delivery of this content. We say a content is successfully delivered if and only if it is received by all its clients. We assume there are I popularity classes of contents. Let pi ≥ 0 denote the popularity of class i. We allow an arbitrary popularity distribution satisfying the following equation: XI i=1 pi = 1. (1) Without loss of generality, we assume pi decreases with i. Each popularity class consists of K = M/I contents. Each node independently generates K requests, each of which is for a content in class i with probability pi/K. Denote ik as the k-th content in the i-th class and nik as the number of requests for content ik. Therefore, we have XI i=1 XK k=1 nik = nK. (2) Remark: Note that, for ease of illustration, we assume the number of requests generated by each node is equal to the number of contents in each popularity class. Our approach can be readily applied to more general cases, where the number of requests generated by each node and the number of contents in each class are different. C. Scheduling Scheme In this part, we give an overview of a class of centralized scheduling policies, which we will consider in the analysis 1Our analytical results can be extended to the case of different content sizes, by splitting each content into segments of unit length

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)

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.

the inequalities in (33)and (35)in Appendix A are tight). Combining (9)and(35),we have E[M]= √mu (11) 1/3 Given a request state Q and a content class i,the number of requests ni could be different for different k.Denote ni Eni.In the achievable scheme,we will choose a determinist value a) reasing popularity (b) source client servers idle mobile node M= (12) Fig.1:(a)Cell partition in a timeslot of the placement phase 1/3 (b)Cell partition in a timeslot of the retrieval phase. for all Mi,k =1,...,K.Since pi decreases with index i, we have Mi≥M2≥..≥Mi.And it is easy to show that information (carried in control packets)is required,and for all i and k,nis nilogn and E [Mig]Mi logn,with the transmissions in all cells are independent of each other. high probability (w.h.p.).In addition,letting (33)hold with Later,we will show that the proposed scheme can achieve equality,we have performance with a gap from the optimal performance up to a factor of log n. E2[R,d」=EM]Wa1ogn (13) Scheme I for fast mobility: Placement phase:The placement phase consists of Similarly,given a request state Q and a content class i,we 9W log2n timeslots.At the beginning of each timeslot will choose a determinist value Ri for all Ri.d,where Ri of the placement phase,we partition the unit square into is given by cells of possibly different sizes,for contents of different 1 classes.Specifically,we first partition the unit square into Ri=M:W logn (14) cells for class-1 contents,each of area M logn.For each cell which does not contain any unreplicated class- We choose W to be the R.H.S of (9).i.e., 1 contents,we further partition it into smaller cells for (K∑V园 2/3 class-2 contents,each of arealogn.The cell partition = (15) proceeds in this way for I rounds in total.After the log n partition,in each cell of area M logn,randomly select a server of a class-i content that has not been replicated as Then,from (12)and (14).we can obtain a sender.Then the sender broadcasts the class-i content within the cell. 1 (16) Retrieval phase:The retrieval phase consists of ma(∑1V会 9W log2n timeslots.At the beginning of each timeslot of the retrieval phase,we partition the unit square into cells Since pi:decreases with index i,we have R1≤R2≤.≤ of possibly different sizes,for feasible retrieval pairs of R1. different classes.Specifically,we first partition the unit square into cells for feasible class-I pairs,each of area Moreover,as illustrated in Sec.II-C,a scheduling scheme R.For each cell which does not contain any feasible generally consists of two types of operations:content place- class-I pairs,we further partition it into smaller cells ment and content retrieval.Intuitively,it is more efficient for feasible class-(I-1)pairs,each of area R1.The to first replicate contents and transmit the replicas to all cell partition proceeds in this way for I rounds in total. the selected servers and then deliver the replicas to all the After the partition,in each cell of area R2,randomly clients with the help of these servers.The reason is that,in select a feasible class-i pair.Then,the server delivers the this way,there are more servers during content retrieval,i.e., requested class-i content to the client. more opportunities for clients to meet their servers.Therefore, Fig.1 illustrates Scheme I employed in a scenario where we conduct content delivery in two adjacent phases,i.e., contents have heterogeneous popularity.Note that the pro- placement phase and retrieval phase. posed scheme can also be applied in homogeneous popularity scenarios.Specifically,Fig.1(a)shows the cell partition in a timeslot of the placement phase.Since in our scheme,contents Based on the above discussions,we propose the following distributed scheme under fast mobility,for any request state 4 We assume that the size of control packets is much smaller than that Q.Please note that in this distributed scheme,the network of contents,as in [19].The control packets are transmitted within each cell through reserved bandwidth or channels and the transmission costs are not is divided into disjoint cells,in each of which only local accounted in the analysis

5 the inequalities in (33) and (35) in Appendix A are tight). Combining (9) and (35), we have E [Mik ] = Θ… √nnik €PI i=1 PK k=1 È nik /nŠ1/3 . (11) Given a request state Q and a content class i, the number of requests nik could be different for different k. Denote ni , E[nik ]. In the achievable scheme, we will choose a determinist value Mi = Θ… √ nni PI i=1 PK k=1 È ni/n1/3 , (12) for all Mik , k = 1, ..., K. Since pi decreases with index i, we have M1 ≥ M2 ≥ ... ≥ MI . And it is easy to show that for all i and k, nik ≤ ni log n and E [Mik ] ≤ Mi log n, with high probability (w.h.p.). In addition, letting (33) hold with equality, we have E 2 Rik,dik = 1 E [Mik ] W¯ Q log n . (13) Similarly, given a request state Q and a content class i, we will choose a determinist value Ri for all Rik,dik , where Ri is given by Ri = Ê 1 MiW¯ log n . (14) We choose W¯ to be the R.H.S of (9), i.e., W¯ = Θ„€ K PI i=1 √pi Š2/3 log n Ž . (15) Then, from (12) and (14), we can obtain Ri = Θ„ 1 (nni) 1/4 €PI i=1 PK k=1 Èni n Š1/6 Ž . (16) Since pi decreases with index i, we have R1 ≤ R2 ≤ ... ≤ RI . Moreover, as illustrated in Sec. II-C, a scheduling scheme generally consists of two types of operations: content place￾ment and content retrieval. Intuitively, it is more efficient to first replicate contents and transmit the replicas to all the selected servers and then deliver the replicas to all the clients with the help of these servers. The reason is that, in this way, there are more servers during content retrieval, i.e., more opportunities for clients to meet their servers. Therefore, we conduct content delivery in two adjacent phases, i.e., placement phase and retrieval phase. Based on the above discussions, we propose the following distributed scheme under fast mobility, for any request state Q. Please note that in this distributed scheme, the network is divided into disjoint cells, in each of which only local source client servers decreasing popularity idle mobile node (a) (b) Fig. 1: (a) Cell partition in a timeslot of the placement phase. (b) Cell partition in a timeslot of the retrieval phase. information (carried in control packets4 ) is required, and the transmissions in all cells are independent of each other. Later, we will show that the proposed scheme can achieve performance with a gap from the optimal performance up to a factor of log2 n. Scheme I for fast mobility: • Placement phase: The placement phase consists of 9W¯ log2 n timeslots. At the beginning of each timeslot of the placement phase, we partition the unit square into cells of possibly different sizes, for contents of different classes. Specifically, we first partition the unit square into cells for class-1 contents, each of area M1 n log n. For each cell which does not contain any unreplicated class- 1 contents, we further partition it into smaller cells for class-2 contents, each of area M2 n log n. The cell partition proceeds in this way for I rounds in total. After the partition, in each cell of area Mi n log n, randomly select a server of a class-i content that has not been replicated as a sender. Then the sender broadcasts the class-i content within the cell. • Retrieval phase: The retrieval phase consists of 9W¯ log2 n timeslots. At the beginning of each timeslot of the retrieval phase, we partition the unit square into cells of possibly different sizes, for feasible retrieval pairs of different classes. Specifically, we first partition the unit square into cells for feasible class-I pairs, each of area R2 I . For each cell which does not contain any feasible class-I pairs, we further partition it into smaller cells for feasible class-(I − 1) pairs, each of area R2 I−1 . The cell partition proceeds in this way for I rounds in total. After the partition, in each cell of area R2 i , randomly select a feasible class-i pair. Then, the server delivers the requested class-i content to the client. Fig. 1 illustrates Scheme I employed in a scenario where contents have heterogeneous popularity. Note that the pro￾posed scheme can also be applied in homogeneous popularity scenarios. Specifically, Fig. 1(a) shows the cell partition in a timeslot of the placement phase. Since in our scheme, contents 4 We assume that the size of control packets is much smaller than that of contents, as in [19]. The control packets are transmitted within each cell through reserved bandwidth or channels and the transmission costs are not accounted in the analysis.

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)

in Appendix B are tight.From(18)and(48),we have partition,in each cell of areaM logn,randomly select a server of a class-i content that has not been replicated as E[M]=Θ log n a sender.Then the sender broadcasts the class-i content n27 (20) within the cell. Retrieval phase:The retrieval phase consists of Given a request state Q and a content class i,the number of 9W log2n timeslots.At the beginning of each timeslot of requests nik could be different for different k.Denote n the retrieval phase,we partition the unit square into cells Elni.We then choose a determinist value of possibly different sizes,for feasible retrieval pairs of different classes,using the same method as the one in log n M;=0 ∑1n (21) scheme I.After all feasible retrieval pairs are included in =1 the corresponding retrieval cells,we further divide each retrieval cell into hop-cells,each of area ).6 After for all Mi,k=1,...K.Since pi decreases with index i,we the partition,in each retrieval cell of area R2,randomly have M≥M≥.≥Mh.And it is easy to show that for select a feasible class-i retrieval pair.Then the server all i and k,ni ni logn and E [Mi]Mi logn,w.h.p..In is scheduled to deliver the requested class-i content to addition,letting (43)hold with equality,we have the client in a multihop manner along hop-cells in the 1 E[R,d4k」= (22) same retrieval cell.Each hop-cell is active once in every √E[M]Wo log n 9 timeslots.In each active hop-cell,if there exists a server of the requested class-i content,select it as a sender and a Similarly,given a request state Q and a content class i,we random node from its neighboring hop-cells as a receiver. will choose a determinist value Ri for all Rid,where Ri Then the sender forwards the content to the receiver until is given by it is retrieved by the client. 1 Ri=M:W logn (23) Theorem 4:Under Scheme II,the average delay of serving all nk requests is upper bounded by We choose W to be the R.H.S of (18).i.e.,W (K∑p)iogn) .Then,from (21)and (23).we can Proof:Under Scheme II,content delivery delay is com- posed of two parts:placement delay and retrieval delay. obtain Similar to the previous placement analysis,we first show 1 that each content ik will have at least Mi(21)copies at the (24) ogn∑-∑1n2)n end of the placement phase.For a server of a content ik,if it is scheduled to replicate content ik,on average Mi logn Since pi decreases with index i,we have R1≤B2≤…≤ nodes (at least Mi nodes)that reside in the same cell as the RI. server will receive the copies.Hence,according to Scheme Similarly,since it is more efficient to first replicate contents II,on averageM.logn copies over all contents are generated in the placement phase.Since each cell can be and transmit the replicas to all the selected servers and then deliver the replicas to all the clients with the help of these activated once at most every 9 timeslots,there are totally no servers,we conduct content delivery in two adjacent phases, less than an copies generated in each timeslot.It then follows i.e.,placement phase and retrieval phase. that the total time required for the placement phase is no Based on the above discussions,we propose the following greater than (∑)ogm timeslots. distributed scheme under slow mobility,for any request state Second,we show that the requests of all clients will be Q.Later,we will show that the proposed scheme can achieve satisfied at the end of the retrieval phase.It has been proved performance with a gap from the optimal performance up to a factor of log n. that if the area of each cell is no smaller than then each cell has at least one node w.h.p.[20].Therefore, Scheme II for slow mobility: each hop-cell contains at least one node and can guarantee Placement phase:The placement phases consists of the multihop transmissions. 9W log2n timeslots.At the beginning of each timeslot For a client of content ik,the probability that at least of the placement phase,we partition the unit square into one server moves into its retrieval range is 1(1RM cells of possibly different sizes,for contents of different Following a similar approach to the one in the proof of classes.Specifically,we first partition the unit square into Theorem 2,the probability can be approximated as MR?. cells for class-1 contents,each of area logn.For Recall that such kind of pairs are defined as feasible retrieval each cell which does not contain any unreplicated class- pairs of content ik.Once there exists a feasible retrieval pair 1 contents,we further partition it into smaller cells for of content ik in a cell of area R2,with at least probability class-2 contents,each of area Ma logn.The cell partition it is scheduled for transmissions along multiple hop-cells in a proceeds in this way for I rounds in total.After the timeslot.The probability of completing the content delivery of SNote that the placement phase under slow mobility is the same as that Note that we set the hop-cell area equalo)toensure that there under fast mobility.We present it here for the sake of completeness. is at least one node in it w.h.p.as noo [20]

7 in Appendix B are tight. From (18) and (48), we have E [Mik ] = Θ „ n 1 2 n 2 3 ik log n PI i=1 PK k=1 n 2/3 ik !1/4 Ž . (20) Given a request state Q and a content class i, the number of requests nik could be different for different k. Denote ni , E[nik ]. We then choose a determinist value Mi = Θ„ n 1 2 n 2 3 i log n PI i=1 PK k=1 n 2/3 i !1/4Ž , (21) for all Mik , k = 1, ..., K. Since pi decreases with index i, we have M1 ≥ M2 ≥ ... ≥ MI . And it is easy to show that for all i and k, nik ≤ ni log n and E [Mik ] ≤ Mi log n, w.h.p.. In addition, letting (43) hold with equality, we have E Rik,dik = 1 È E [Mik ] W¯ Q log n . (22) Similarly, given a request state Q and a content class i, we will choose a determinist value Ri for all Rik,dik , where Ri is given by Ri = Ê 1 MiW¯ log n . (23) We choose W¯ to be the R.H.S of (18), i.e., W¯ = Θ  K log n PI i=1 p 2 3 i 3/4 ‹ . Then, from (21) and (23), we can obtain Ri = Θ „ 1 € log n PI i=1 PK k=1 n 2/3 i Š1/4 n 1/3 i Ž . (24) Since pi decreases with index i, we have R1 ≤ R2 ≤ ... ≤ RI . Similarly, since it is more efficient to first replicate contents and transmit the replicas to all the selected servers and then deliver the replicas to all the clients with the help of these servers, we conduct content delivery in two adjacent phases, i.e., placement phase and retrieval phase. Based on the above discussions, we propose the following distributed scheme under slow mobility, for any request state Q. Later, we will show that the proposed scheme can achieve performance with a gap from the optimal performance up to a factor of log2 n. Scheme II for slow mobility: • Placement phase: The placement phase5 consists of 9W¯ log2 n timeslots. At the beginning of each timeslot of the placement phase, we partition the unit square into cells of possibly different sizes, for contents of different classes. Specifically, we first partition the unit square into cells for class-1 contents, each of area M1 n log n. For each cell which does not contain any unreplicated class- 1 contents, we further partition it into smaller cells for class-2 contents, each of area M2 n log n. The cell partition proceeds in this way for I rounds in total. After the 5Note that the placement phase under slow mobility is the same as that under fast mobility. We present it here for the sake of completeness. partition, in each cell of area Mi n log n, randomly select a server of a class-i content that has not been replicated as a sender. Then the sender broadcasts the class-i content within the cell. • Retrieval phase: The retrieval phase consists of 9W¯ log2 n timeslots. At the beginning of each timeslot of the retrieval phase, we partition the unit square into cells of possibly different sizes, for feasible retrieval pairs of different classes, using the same method as the one in scheme I. After all feasible retrieval pairs are included in the corresponding retrieval cells, we further divide each retrieval cell into hop-cells, each of area Θ € log n n Š . 6 After the partition, in each retrieval cell of area R2 i , randomly select a feasible class-i retrieval pair. Then the server is scheduled to deliver the requested class-i content to the client in a multihop manner along hop-cells in the same retrieval cell. Each hop-cell is active once in every 9 timeslots. In each active hop-cell, if there exists a server of the requested class-i content, select it as a sender and a random node from its neighboring hop-cells as a receiver. Then the sender forwards the content to the receiver until it is retrieved by the client. Theorem 4: Under Scheme II, the average delay of serving all nK requests is upper bounded by Θ €€K PI i=1 p 2 3 i Š 3 4 log 5 4 n Š . Proof: Under Scheme II, content delivery delay is com￾posed of two parts: placement delay and retrieval delay. Similar to the previous placement analysis, we first show that each content ik will have at least Mi (21) copies at the end of the placement phase. For a server of a content ik, if it is scheduled to replicate content ik, on average Mi log n nodes (at least Mi nodes) that reside in the same cell as the server will receive the copies. Hence, according to Scheme II, on average PI i=1 PK k=1 Mi log n copies over all contents are generated in the placement phase. Since each cell can be activated once at most every 9 timeslots, 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 n 2 3 i Š3/4 (log n) 5 4 √ n timeslots. Second, we show that the requests of all clients will be satisfied at the end of the retrieval phase. It has been proved that if the area of each cell is no smaller than Θ € log n n Š , then each cell has at least one node w.h.p. [20]. Therefore, each hop-cell contains at least one node and can guarantee the multihop transmissions. For a client of content ik, the probability that at least one server moves into its retrieval range is 1 − ￾ 1 − R2 i
Mi . Following a similar approach to the one in the proof of Theorem 2, the probability can be approximated as MiR2 i . Recall that such kind of pairs are defined as feasible retrieval pairs of content ik. Once there exists a feasible retrieval pair of content ik in a cell of area R2 i , with at least 1 9 probability it is scheduled for transmissions along multiple hop-cells in a timeslot. The probability of completing the content delivery of 6Note that we set the hop-cell area equal to Θ ￾ log n n
, to ensure that there is at least one node in it w.h.p. as n → ∞ [20].

8 such a feasible retrieval pair is thus at least.It follows average placement delay.Therefore,it is not clear how the that the expected time of reaching a client of content ik is cache size affects the average weighted sum delay,and we are upper bounded by which are the same for all i,after thus motivated to investigate how the network performance plugging in the values of Mi in (21)and Ri in(24).Then,it scales with the cache size no. is easy to show that,each content ik can reach all its clients We first study the average weighted sum delay cost C under 9(②∑)reg四 the fast mobility model.The average weighted sum delay cost within timeslots. Vn C in the following theorem is an extension of the average Combining all the analysis above,we can conclude this delay cost W in Theorem 1. theorem. ◆ Theorem 5:Under the fast mobility model and Assumption 1,for any scheduling scheme with per-node cache size no.the IV.PLACEMENT COST AND CACHE CONSTRAINTS average weighted sum delay cost of serving all nK requests satisfies In this section,we further study the asymptotic delay performance under additional constraints on two important VpK2A2 logn %=P(4)手)，P≠0 factors:cache size and placement cost.The new results are not KA otherwise only more general than the previous results,but also provide √nb log n new insights into the impacts of different network parameters (27) on the network performance. where A=∑1V. From the previous analysis,we can see that the placement Proof:Please refer to Appendix C. ■ cost is captured in the average delay cost.However,one Next,we study the average weighted sum delay cost C concern is that the unit of the placement cost is equal to under the slow mobility model.The average weighted sum that of the retrieval cost,which may not be the case in delay cost C in the following theorem is an extension of the reality.For example,there are peak-traffic time and off-peak average delay cost W in Theorem 3. time.Content placement can take place at off-peak time to Theorem 6:Under the slow mobility model and Assump- reduce the data traffic at peak time.Therefore,the units of tion 1,for any scheduling scheme with per-node cache size the delay costs in the placement and retrieval phases could be nb,the average weighted sum delay cost of serving all nk different in general,and the unit cost for the time consumed requests satisfies in the placement phase may be lower than that in the retrieval phase.These practical concerns motivate us to incorporate the （p() n6=2( KDogn 0 ,p≠0 following assumption in studying content-centric MANETs. KD Assumption 1:The delay cost of a placement timeslot is otherwise lower than that of a retrieval timeslot. (28) We normalize the delay cost of a retrieval timeslot to 1,and where D= denote the delay cost of a placement timeslot as p.Here,p =1 can be treated as the delay cost weight.By Assumption 1,we Proof:Please refer to Appendix D. ■ know that 0<p<1.For a given request state Q,denote the The results in Theorem 5 and Theorem 6 are general and time length of the placement phase and the retrieval phase as hold for any n and p.In particular,the result in Theorem 5 WP.and WR.Q,respectively.Then,for a given request state can cover two special cases under fast mobility,i.e.,content Q,the average weighted sum delay cost of serving all nK placement is free (p=0)[17]and the unit of the placement requests can be expressed as cost is the same as that of the retrieval cost (p 1)in Theorem 1.The result in Theorem 6 can cover the one in Co pWP.Q+WR.Q. (25) Theorem 3(p 1)under slow mobility.Lower bounds on The average weighted sum delay cost C of serving all nK the average weighted sum delay cost C for different cases requests over all possible request states is under fast and slow mobility are presented in Table I and Table II,respectively.The insights into these cases are provided as C≌ECal=CoP(Q): (26) follows. QEX Case 1:When the cost of content placement is not con- where P(O)is the probability of being state O. sidered,i.e.,p =0,the average weighted sum delay cost Moreover,in reality,caches always have limited sizes, solely comes from content retrieval.The total (retrieval)cost which is a main constraint for content placement.Therefore, decreases with the cache size n. we consider that each node is equipped with a cache of the Case 2:When p0 and the cache size is smaller than a same size.Let nb be the cache size of each node,measured threshold,as n increases,the placement cost increases and the in the number of contents it can store.Denote np as the sum retrieval cost decreases.Moreover,the larger the cache size, of the occupied cache memory over all nodes during content the smaller the average weighted sum delay cost. placement.Then,we have np nnb,which sets a constraint Case 3:When p0 and the cache size is larger than on the sum of replicas in the placement phase.Intuitively, a threshold,the placement cost is on the same order of the when the cache size is larger,more replicas can be cached. retrieval cost.In this case,the minimum average weighted sum which results in a smaller average retrieval delay and a larger delay cost)()is achieved under

8 such a feasible retrieval pair is thus at least MiR 2 i 9 . It follows that the expected time of reaching a client of content ik is upper bounded by 9 MiR2 i , which are the same for all i, after plugging in the values of Mi in (21) and Ri in (24). Then, it is easy to show that, each content ik can reach all its clients within 9 €PI i=1 PK k=1 n 2 3 i Š3/4 (log n) 5 4 √ n timeslots. Combining all the analysis above, we can conclude this theorem. IV. PLACEMENT COST AND CACHE CONSTRAINTS In this section, we further study the asymptotic delay performance under additional constraints on two important factors: cache size and placement cost. The new results are not only more general than the previous results, but also provide new insights into the impacts of different network parameters on the network performance. From the previous analysis, we can see that the placement cost is captured in the average delay cost. However, one concern is that the unit of the placement cost is equal to that of the retrieval cost, which may not be the case in reality. For example, there are peak-traffic time and off-peak time. Content placement can take place at off-peak time to reduce the data traffic at peak time. Therefore, the units of the delay costs in the placement and retrieval phases could be different in general, and the unit cost for the time consumed in the placement phase may be lower than that in the retrieval phase. These practical concerns motivate us to incorporate the following assumption in studying content-centric MANETs. Assumption 1: The delay cost of a placement timeslot is lower than that of a retrieval timeslot. We normalize the delay cost of a retrieval timeslot to 1, and denote the delay cost of a placement timeslot as ρ. Here, ρ can be treated as the delay cost weight. By Assumption 1, we know that 0 ≤ ρ ≤ 1. For a given request state Q, denote the time length of the placement phase and the retrieval phase as W¯ P,Q and W¯ R,Q, respectively. Then, for a given request state Q, the average weighted sum delay cost of serving all nK requests can be expressed as C¯Q = ρW¯ P,Q + W¯ R,Q. (25) The average weighted sum delay cost C¯ of serving all nK requests over all possible request states is C¯ , E[C¯Q] = X Q∈A C¯QP(Q), (26) where P(Q) is the probability of being state Q. Moreover, in reality, caches always have limited sizes, which is a main constraint for content placement. Therefore, we consider that each node is equipped with a cache of the same size. Let nb be the cache size of each node, measured in the number of contents it can store. Denote np as the sum of the occupied cache memory over all nodes during content placement. Then, we have np ≤ nnb, which sets a constraint on the sum of replicas in the placement phase. Intuitively, when the cache size is larger, more replicas can be cached, which results in a smaller average retrieval delay and a larger average placement delay. Therefore, it is not clear how the cache size affects the average weighted sum delay, and we are thus motivated to investigate how the network performance scales with the cache size nb. We first study the average weighted sum delay cost C¯ under the fast mobility model. The average weighted sum delay cost C¯ in the following theorem is an extension of the average delay cost W¯ in Theorem 1. Theorem 5: Under the fast mobility model and Assumption 1, for any scheduling scheme with per-node cache size nb, the average weighted sum delay cost of serving all nK requests satisfies C¯ ≥ 8 : Θ  ρ 1 4 € KD log n Š 3 4 ‹ , nb = Ω€€ KD√3 log n ρ Š 3 4 Š , ρ ̸= 0 Θ  KD √3 nblog2n ‹ , otherwise (28) where D = P I i=1 p 2 3 i . Proof: Please refer to Appendix D. The results in Theorem 5 and Theorem 6 are general and hold for any nb and ρ. In particular, the result in Theorem 5 can cover two special cases under fast mobility, i.e., content placement is free (ρ = 0) [17] and the unit of the placement cost is the same as that of the retrieval cost (ρ = 1) in Theorem 1. The result in Theorem 6 can cover the one in Theorem 3 (ρ = 1) under slow mobility. Lower bounds on the average weighted sum delay cost C¯ for different cases under fast and slow mobility are presented in Table I and Table II, respectively. The insights into these cases are provided as follows. Case 1: When the cost of content placement is not con￾sidered, i.e., ρ = 0, the average weighted sum delay cost solely comes from content retrieval. The total (retrieval) cost decreases with the cache size nb. Case 2: When ρ ̸= 0 and the cache size is smaller than a threshold, as nb increases, the placement cost increases and the retrieval cost decreases. Moreover, the larger the cache size, the smaller the average weighted sum delay cost. Case 3: When ρ ̸= 0 and the cache size is larger than a threshold, the placement cost is on the same order of the retrieval cost. In this case, the minimum average weighted sum delay cost Θ €√3 ρK2A2 log n Š (Θ € ρ 1 4 € KD log n Š 3 4 Š ) is achieved under

9 TABLE I:Lower Bounds on the Costs for Different Cases(Fast Mobility) Case Price Cache Size Placement Cost Retrieval Cost Weighted Sum Delay Cost 1 p=0 Arbitrary nb 0 Θ （ns log n ynslogn KA 2 p≠0 nb=O () 6(） 6(m) 9(dn) 3 p卡0 nb= 2 日 PK2A2 VPK2A2 日 PK2A2 logn logn logn TABLE II:Lower Bounds on the Costs for Different Cases (Slow Mobility) Case Price Cache Size Placement Cost Retrieval Cost Weighted Sum Delay Cost p=0 Arbitrary nb 0 KD KD nolog2元 Vntlog'n 2 p≠0 nb = O(KD@g元 6() KD KD p Vnblog2n nblog2n 3 P≠0 n=2( (KDVlog元 0 (p(品 (p() (p() fast(slow)mobility.Note that the average weighted sum delay cost will not further decrease with the cache size n. In summary,we find that when content placement is not free and the cache size is scalable,the optimal content placement ◆-lower bound -lower bound numencal resu has a threshold-based structure under both fast and slow mo- numencal result upper bound upper bound bility.Specifically,when the number of replicas in the network is below a threshold,the network performance improves with the number of replicas;when the number of replicas is above 0 100120 60 a threshold,the best performance over all n is achieved,and 10120 the network performance will not further improve with the (a)Fast mobility (b)Slow mobility number of replicas. Fig.2:Comparisons of numerical and analytical results. V.SIMULATION AND DISCUSSION In this section,we first present numerical results to verify bound (Theorem 2),and is larger than that of its lower bound our analysis.Then,we compare the obtained throughput-delay (Theorem 1).Figure 2(b)compares the numerical results and tradeoffs with existing results. the analytical results for slow mobility.It can be seen that the slope for the numerical result is smaller than that of its upper A.Simulation bound (Theorem 4),and is larger than that of its lower bound (Theorem 3).In summary,both of these two figures show In this subsection,we conduct numerical simulations to that our theoretical results can accurately bound the numerical verify our theoretical results.The simulation setting is as results. follows.We choose K=1,M=I=n,and the popularity follows Zipf distribution with Zipf parameter a 1.We choose v元=[20：20：140.The numerical results are B.Discussion presented in Figure 2.The numerical curves are obtained by In this subsection,we compare with some existing results averaging over 100 simulation runs.The upper bounds for fast and present some observations. mobility and slow mobility are plotted using the expressions Observation 1:A content-centric network can benefit from in Theorem 2 and Theorem 4.i.e.(K)2/3logn and mobility if the cache size is scalable.The tradeoff result in i=1 the static case [13]is given by epectively.The lower bounds for the 白(1)， a≥是 Doe 合(w),1<a<是. (29) ad(昏∑).repecte,Tey-asiss in the 6(), a≤1 For a fair comparison with the tradeoff in(29),we consider logarithmic scale. Figure 2(a)compares the numerical results and the analyt- the same setting as in [13].Specifically,we set K=1 (i.e., ical results for fast mobility.It can be seen that the slope for the numerical result is smaller than that of its upper 7Here"scalable"means the per-node cache size is not a constant,and may scale as the number of nodes and the number of requests

9 TABLE I: Lower Bounds on the Costs for Different Cases (Fast Mobility) Case Price Cache Size Placement Cost Retrieval Cost Weighted Sum Delay Cost 1 ρ = 0 Arbitrary nb 0 Θ € √ KA nb log n Š Θ € √ KA nb log n Š 2 ρ ̸= 0 nb = O € KA ρ Š2/3 ‹ Θ € ρnb log n Š Θ € √ KA nb log n Š Θ € √ KA nb log n Š 3 ρ ̸= 0 nb = Ω € KA ρ Š2/3 ‹ Θ √3 ρK2A2 log n ‹ Θ √3 ρK2A2 log n ‹ Θ √3 ρK2A2 log n ‹ TABLE II: Lower Bounds on the Costs for Different Cases (Slow Mobility) Case Price Cache Size Placement Cost Retrieval Cost Weighted Sum Delay Cost 1 ρ = 0 Arbitrary nb 0 Θ  KD √3 nblog2n ‹ Θ  KD √3 nblog2n ‹ 2 ρ ̸= 0 nb = O €€ KD√3 log n ρ Š 3 4 Š Θ € ρnb log n Š Θ  KD √3 nblog2n ‹ Θ  KD √3 nblog2n ‹ 3 ρ ̸= 0 nb = Ω€€ KD√3 log n ρ Š 3 4 Š Θ  ρ 1 4 € KD log n Š 3 4 ‹ Θ  ρ 1 4 € KD log n Š 3 4 ‹ Θ  ρ 1 4 € KD log n Š 3 4 ‹ fast (slow) mobility. Note that the average weighted sum delay cost will not further decrease with the cache size nb. In summary, we find that when content placement is not free and the cache size is scalable, the optimal content placement has a threshold-based structure under both fast and slow mo￾bility. Specifically, when the number of replicas in the network is below a threshold, the network performance improves with the number of replicas; when the number of replicas is above a threshold, the best performance over all nb is achieved, and the network performance will not further improve with the number of replicas. V. SIMULATION AND DISCUSSION In this section, we first present numerical results to verify our analysis. Then, we compare the obtained throughput-delay tradeoffs with existing results. A. Simulation In this subsection, we conduct numerical simulations to verify our theoretical results. The simulation setting is as follows. We choose K = 1, M = I = n, and the popularity follows Zipf distribution with Zipf parameter α = 1. We choose √ n = [20 : 20 : 140]. The numerical results are presented in Figure 2. The numerical curves are obtained by averaging over 100 simulation runs. The upper bounds for fast mobility and slow mobility are plotted using the expressions in Theorem 2 and Theorem 4, i.e.,(K P I i=1 √pi) 2/3 log n and € K PI i=1 p 2 3 i Š 3 4 log 5 4 n, respectively. The lower bounds for the fast mobility and slow mobility are plotted using the expres￾sions in Theorem 1 and Theorem 3, i.e., (K PI i=1 √pi) 2/3 log n and ( K log n PI i=1 p 2 3 i ) 3/4 , respectively. The y-axis is in the logarithmic scale. Figure 2(a) compares the numerical results and the analyt￾ical results for fast mobility. It can be seen that the slope for the numerical result is smaller than that of its upper 20 40 60 80 100 120 140 √ n 0 1 2 3 4 5 6 log(Delay) lower bound numerical result upper bound (a) Fast mobility 20 40 60 80 100 120 140 √ n -1 0 1 2 3 4 5 log(Delay) lower bound numerical result upper bound (b) Slow mobility Fig. 2: Comparisons of numerical and analytical results. bound (Theorem 2), and is larger than that of its lower bound (Theorem 1). Figure 2(b) compares the numerical results and the analytical results for slow mobility. It can be seen that the slope for the numerical result is smaller than that of its upper bound (Theorem 4), and is larger than that of its lower bound (Theorem 3). In summary, both of these two figures show that our theoretical results can accurately bound the numerical results. B. Discussion In this subsection, we compare with some existing results and present some observations. Observation 1: A content-centric network can benefit from mobility if the cache size is scalable7 . The tradeoff result in the static case [13] is given by λ¯ = 8 >: Θ (1) ˜ , α ≥ 3 2 Θ˜ € W¯ M3−2α Š , 1 < α < 3 2 Θ˜ € W¯ M Š , α ≤ 1 . (29) For a fair comparison with the tradeoff in (29), we consider the same setting as in [13]. Specifically, we set K = 1 (i.e., 7Here “scalable” means the per-node cache size is not a constant, and may scale as the number of nodes and the number of requests

10 M)and consider Zipf distribution,i.e=,where np=uandIIn this case,each content is requested by a 0 is the exponent of Zipf distribution and H(M)= u clients.Under fast mobility,from Theorem 1,we obtain (∑-) is a normalization constant.From Theorem the optimal throughput and delay tradeoff 1,we obtain the following optimal throughput-delay tradeoff Under slow mobility,from Theorem 3,we obtain the optimal under fast mobility throughput and delay tradeoff).These results 百(1) a≥2 recover the optimal throughput-delay tradeoffs in [10]. Finally,we consider the content-centric case in [17]by 1<a<2 (30) setting pi=and K 1.In this case,the content 0 () a≤1 popularity follows a Zipf distribution.Since [17]assumes free content placement and a limited cache size,we further set Comparing(29)and(30),we find that mobility improves the p 0 and n e(1).From Theorem 5,we obtain the performance when a<1,while it degrades the performance following throughput-delay tradeoffs,which recover the results when a∈(1,2).Fora≥2，it is possible to achieve the best in[17刀]. (1)throughput and (1)delay in both the mobile and static ( 白(1)， a≥2 cases 6(),1<a<2 (32) In addition,from Theorem 3,we obtain the following optimal throughput-delay tradeoff under slow mobility 6(), a≤1 Moreover,we find that even when content placement is not 白(1) a2是 free (i.e.,p 0),our scheme can improve the maximum 1<a<是 (31) throughput up to a factor of when the cache size )： is scalable.This gain demonstrates the benefit of caching in a≤1 content-centric MANETs. From(29),(30)and (31),we find that slow mobility leads to a better performance than both fast mobility and the static case.This is because there are more possible routing VI.CONCLUSION AND FUTURE WORK schemes when nodes move in a much slower time scale than content transmissions.This observation seems to be different from that in [17],which shows that mobility may hurt the In this paper,we investigate the asymptotic performance performance when the cache size is limited.The intuition is of content-centric MANETs.Different from previous work which considers content retrieval cost only,this paper jointly as follows.In the static case,contents are forwarded to clients hop by hop,and the required cache size is constant in the order considers the delay costs in both content placement and con- tent retrieval.We study two mobility models in different time- sense.In the mobile case,contents are delivered to clients using the "store-carry-forward"paradigm,i.e.,contents are scales,i.e.,fast and slow mobility.Under each mobility model, first stored and carried by mobile servers,and then forwarded by optimizing the number of replicas and retrieval ranges to mobile clients by one hop.Therefore,the storage of servers for contents of different popularity,we analyze the optimal throughput and delay,and design a near-optimal scheme. plays a more important role on content delivery in the mobile case.If the cache size is limited (nb =e(1)),the number Furthermore,we introduce a more general weighted sum delay of contents carried by each mobile server is bounded by metric,to capture content placement and content retrieval e(1).Then during the inter-meeting time (larger than e(1)), of possibly different delay costs.Our results provide useful insights into the performance of content-centric MANETs in a mobile server does not always have contents to forward, different scenarios. even though it has a transmission opportunity.Thus mobile servers with limited cache sizes cannot effectively exploit the There are several interesting directions for future research. transmission opportunities. For instance,when energy consumption is considered,there Observation 2:By considering an arbitrary content pop- may exist a tradeoff among energy,throughput and delay.It is thus meaningful to investigate the optimal tradeoff and design ularity distribution,we establish more general results.The following discussions demonstrate that our results can recover an energy-aware scheme which achieves a tradeoff close to the analytical results for the unicast [8],[9]and multicast [10] the optimal one.In addition,if content popularity is time- traffic patterns,and are more general than the results in [17]. varying,the proposed scheduling scheme designed for fixed First,we consider the unicast case in [8].[9]by setting popularity may no longer be effective.This highlights the need for designing dynamic placement and retrieval strategies npi =1 and I=n.In this case,each content is requested by a single client.Under fast mobility,from Theorem 1,we obtain for time-varying popularity.Finally,the proposed scheme can also be generalized to vehicle-to-vehicle (V2V)networks.in the optimal throughput and delay tradeoff入-6（√t), which real time data traffic and inhomogeneous vehicle density Under slow mobility,from Theorem 3,we obtain the optimal should be considered.It is interesting to see how local content throughput and delay tradeoff.These results sharing is affected by high spatial variations of vehicle density recover the optimal throughput-delay tradeoffs in [8].[9]. and how to design efficient scheduling schemes for inter- Second,we consider the multicast case in [10]by setting vehicle content sharing

10 M = I) and consider Zipf distribution, i.e., pi = H(M) iα , where α ≥ 0 is the exponent of Zipf distribution and H(M) = €PM i=1 i −α Š−1 is a normalization constant. From Theorem 1, we obtain the following optimal throughput-delay tradeoff under fast mobility λ¯ = 8 >>>: Θ (1) ˜ , α ≥ 2 Θ˜ È W¯ M2−α  , 1 >>: Θ (1) ˜ , α ≥ 3 2 Θ˜  3 È W¯ M3−2α  , 1 : Θ (1) ˜ , α ≥ 2 Θ˜ € W¯ M2−α Š , 1 < α < 2 Θ˜ € W¯ M Š , α ≤ 1 . (32) Moreover, we find that even when content placement is not free (i.e., ρ ̸= 0), our scheme can improve the maximum throughput up to a factor of Θ˜ €È M W¯ Š when the cache size is scalable. This gain demonstrates the benefit of caching in content-centric MANETs. VI. CONCLUSION AND FUTURE WORK In this paper, we investigate the asymptotic performance of content-centric MANETs. Different from previous work which considers content retrieval cost only, this paper jointly considers the delay costs in both content placement and con￾tent retrieval. We study two mobility models in different time￾scales, i.e., fast and slow mobility. Under each mobility model, by optimizing the number of replicas and retrieval ranges for contents of different popularity, we analyze the optimal throughput and delay, and design a near-optimal scheme. Furthermore, we introduce a more general weighted sum delay metric, to capture content placement and content retrieval of possibly different delay costs. Our results provide useful insights into the performance of content-centric MANETs in different scenarios. There are several interesting directions for future research. For instance, when energy consumption is considered, there may exist a tradeoff among energy, throughput and delay. It is thus meaningful to investigate the optimal tradeoff and design an energy-aware scheme which achieves a tradeoff close to the optimal one. In addition, if content popularity is time￾varying, the proposed scheduling scheme designed for fixed popularity may no longer be effective. This highlights the need for designing dynamic placement and retrieval strategies for time-varying popularity. Finally, the proposed scheme can also be generalized to vehicle-to-vehicle (V2V) networks, in which real time data traffic and inhomogeneous vehicle density should be considered. It is interesting to see how local content sharing is affected by high spatial variations of vehicle density and how to design efficient scheduling schemes for inter￾vehicle content sharing