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.