# Scaling Performance Analysis and Optimization Based on the Node Spatial Distribution in Mobile Content-Centric Networks

Authors: Jiajie Ren; Demin Li; Lei Zhang; Guanglin Zhang
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Content-centric networks (CCNs) have become a promising technology for relieving the increasing wireless traffic demands. In this paper, we explore the scaling performance of mobile content-centric networks based on the nonuniform spatial distribution of nodes, where each node moves around its own home point and requests the desired content according to a Zipf distribution. We assume each mobile node is equipped with a finite local cache, which is applied to cache contents following a static cache allocation scheme. According to the nonuniform spatial distribution of cache-enabled nodes, we introduce two kinds of clustered models, i.e., the clustered grid model and the clustered random model. In each clustered model, we analyze throughput and delay performance when the number of nodes goes infinity by means of the proposed cell-partition scheduling scheme and the distributed multihop routing scheme. We show that the node mobility degree and the clustering behavior play the fundamental roles in the aforementioned asymptotic performance. Finally, we study the optimal cache allocation problem in the two kinds of clustered models. Our findings provide a guidance for developing the optimal caching scheme. We further perform the numerical simulations to validate the theoretical scaling laws.


---

## Body

## 1. Introduction

During recent years, wireless traffic is undergoing explosively increase due to the subscribers’ enormous data demands (such as video streaming). Content-centric networks (CCNs) [1] have emerged as a promising solution to deal with the increasing traffic, which shifts the traditional host-oriented communication pattern to the novel content-oriented communication pattern. In CCNs, nodes or user terminals are allowed to cache and forward contents based upon their names rather than the host addresses. This enables users request desired contents by local communications, without communicating with backhaul links to the core networks, which also reduces the delivery time of desired contents. In this context, as the number of users continually grows, the scaling performance of content-centric networks has attracted research interests, which is important to help us understand the scalability of CCNs.In the pioneer work of Gupta and Kumar [2], they first study the scaling behavior of large-scale wireless ad hoc networks. In a static unit network consisting of n randomly distributed nodes, Gupta and Kumar [2] shows the asymptotic throughput of each node scales as Θ1/nlogn(Given two nonnegative functions fn and gn: fn=Ogn means there exists a constant c such that fn≤cgn for n large enough; fn=Ωgn if gn=Ofn; fn=Θgn means both fn=Ogn and fn=Ωgn; fn=ogn means limn⟶∞fn/gn=0; and fn=ωgn means limn⟶∞gn/fn=0.), which indicates the poor scalability of wireless networks as the number of nodes increases. In [3], Franceschetti et al. apply the percolation theory to improve the asymptotic performance of wireless networks and per-node throughput is achieved as Θ1/n. Grossglauser and Tse [4] first take the node mobility into consideration, and they propose a two-hop relaying policy to obtain the constant per-node throughput, which costs a vast transmission delay. Subsequently, a series of researches focus on the scaling laws of various wireless ad hoc networks. Talak et al. [5] investigate the broadcast capacity and transmission delay in highly mobile wireless networks. In [6], Lin et al. investigate the optimal throughput-delay tradeoff under the i.i.d mobility model for mobile ad hoc networks. Jia et al. [7] introduce the correlated mobility into the analysis of throughput and delay. They find that strong correlation of node mobility results in poor asymptotic performance. The nature of different mobility models [6–9] affects the network performance remarkably. In addition, there are several technics to improve the performance of wireless networks, such as directional antennas [10–12], infrastructure support [13–15], secrecy analysis [16, 17], and reinforcement learning [18, 19].In light of the asymptotic analysis of traditional wireless ad hoc networks, the throughput and delay scaling behaviors of large-scale cache-enabled content-centric networks have also received wide attention in recent years. In astatic square network, Gitzenis et al. [20] formulate a joint optimization problem for content replication and transmission. They derive the minimum link capacity by utilizing a Zipf popularity law. In [21], by assuming that the content cached time in a node is finite, Azimdoost et al. investigate the throughput and delay of content-centric networks for the static grid network model and the static random network model, respectively. Jeon et al. [22] study the per-node throughput for wireless static device-to-device networks based on a decentralized caching scheme. In [23], Mahdian et al. analyze the scaling laws for pure static content-centric networks and heterogeneous content-centric networks, respectively. The authors further consider the optimal cache strategy for two kinds of networks. Zhang et al. [24] investigate the capacity of static hybrid content-centric wireless networks. In [25, 26], the authors study how the content popularity impact the network throughput. Contrast to the static networks, [27, 28] investigate the optimal throughput-delay tradeoff for mobile content-centric networks. Do et al. in [27] adopt a decoupling approach to achieve the optimal caching allocation in the hybrid mobile content-centric networks. In [29], Alfano et al. investigate the throughput and delay performance of mobile content-centric networks with limited cache space. They find that the stronger mobility degree of nodes results in poor network performance. In [30], Luo et al. introduce fast and slow mobility models into mobile content-centric networks according to different time scales. Then, the authors analyze the asymptotic performance with an arbitrary content popularity distribution.The distribution of all nodes in the aforementioned literatures is uniform regardless of the traditional ad hoc networks or the content-centric networks. However, the node distribution or the mobility degree is nonuniform in the real world. For example, the density of nodes around hot spots or home points is relatively intensive. The mobile terminals are more likely to move around the airports or the tourist attractions. Motivated by the above considerations, the researchers begin to investigate the nonuniform wireless traffic [31–34]. Alfano et al. [31] first analyze the upper bounds to the per-node throughput of inhomogeneous static wireless networks, where the nodes are distributed following a shot-noise cox process. In [32, 33], Garetto et al. investigate the scaling behaviors of heterogeneous mobile ad hoc networks under the assumption that each node moves around a home point. The interesting results in [32, 33] show that the mobility degree directly affects the data exchange among the nodes. In [34], the authors study multicast capacity of heterogeneous sensor networks, jointly analyzing sensor energy efficiency. In contrast with [31–34], Zheng et al. [35] study the asymptotic performance of inhomogeneous static information-centric networks with infrastructure support. However, the mobility of nodes is of great importance in lots of application scenarios like vehicular ad hoc networks. It is meaningful to understand the impact of mobility on the scaling performance in the content-centric networks where node spatial distribution is nonuniform.To this end, we investigate the scaling laws of mobile content-centric networks where node distribution is nonuniform in this paper. Instead of assuming each node moving the network area uniformly and independently, we consider that all nodes move around their corresponding home points, and they spend more time in the proximity of their home points than the network boundary. We assume each mobile node is equipped with a finite local cache and is able to store contents by using a static cache allocation scheme. Each cache-enabled node requests the desired content based on a Zipf popularity distribution. Moreover, we introduce two clustered models based on the spatial distribution of cache-enabled nodes, i.e., the clustered grid model and clustered random model. In each clustered model, we analyze the asymptotic performance according to the proposed scheduling and routing schemes. Finally, we study the optimal cache allocation problem of the two clustered models, respectively. We also perform the numerical simulations to validate the theoretical scaling laws. The main contributions of this paper are summarized as follows:(i)
Firstly, we construct a novel system model in the content-centric networks where each cache-enabled node moves around its corresponding home point. Based on the deployment of home point, we formalize the spatial distribution of nodes into the two clustered model(ii)
Secondly, we devise a cell-partition-based TDMA scheduling scheme to maximize the concurrent transmissions and develop a distributed multihop routing scheme. On this basis, we derive the asymptotic performance of the two kinds of clustered models and further establish the closed form of the throughput-delay tradeoff(iii)
Thirdly, we design the optimal cache allocation and investigate optimal throughput and delay performance by utilizing Lagrangian relaxation method under the assumption of a Zipf content popularity distribution. Moreover, massive numerical simulations are conducted to validate aforementioned theoretical resultsThe rest of the paper is organized as follows. In Section2, we describe the system models and outline some definitions. In Section 3, we analyze the throughput and delay performance in both clustered grid model and clustered random model. In Section 4, we introduce the optimal cache allocation. Finally, we conclude the paper in Section 5.


## 2. System Models and Definitions

In this paper, we study a mobile content-centric network composed ofn mobile nodes. We assume that n nodes move over a square region O of area n with the wrap-condition, to eliminate border effects. Note that, under aforementioned assumption, we adopt an extended network model that the node density over the square area remains constant as the number of mobile nodes increases. In the following subsections, we first describe the mobility model, content request model, and interference model. Then, we give some important definitions and notations used in this paper.


### 2.1. Mobility Model

In this paper, we adopt a bidimensional i.i.d mobility model for each mobile node, and time is divided into slots of equal duration. At the beginning of each slot, every node moves to a new location, which is independent of other nodes, and stays in the new location for the remaining duration of the slot. LetXit denote the location of node i at time t, and dij=Xit−Xjt denotes the distance between node i and node j.To characterize the spatial distribution of nodes, we assume that each nodei is associated with a home point Hi, which is uniformly and independently selected over the square region O. We consider that a node moves independently around its home point following a general ergodic process, which can be described by a rotationally invariant spatial distribution ϕd. Here, d denotes the Euclidean distance between the mobile node and its corresponding home point.We further assume thatϕd is an arbitrary nonincreasing function that decays as a power law of exponent δ, i.e., ϕd~d−δ,δ≥0. We take function sd=min1,d−δ and consider the following normalized probability density function (PDF) over the whole mobility area to avoid convergence problems in proximity of the home point.
(1)ϕd=sd∫Osd=Θsdnδ−2/2,0≤δ<2,Θsdlogn,δ=2,Θsd,δ>2.Exponentδ reflects the mobility degree of nodes, that is, the probability that each node moving to one point of the network area and stay at that point at a given time slot is not uniform. According to the PDF ϕd, it indicates that each node moves in a limited region, differing from the global mobility. In addition, the probability for the node moving in the proximity of its corresponding home point is larger than the probability that the node moves to the relatively far network area.However, exponentδ just describes the individual mobility behavior and cannot reflect the mobile node density over the network area at a time slot. In real mobile world, the mobile node density is tightly related with the number of home points. Mobile nodes are more likely to move around the hotspots [36] or social spots [37]. For example, the density of mobile terminals (e.g., phones and ipads) is relatively dense in the office buildings or the tourist attractions while the density of mobile terminals in the suburb is reversely sparse due to the less home points. That is, the number of home points will affect the spatial distribution of mobile nodes. Motivated by this fact, clustering behavior has been found in [32, 33, 38] based on the long-term observations. In our work, we introduce the clustered model combined with the distribution of home points. First, we assume m clusters and each cluster has a middle point (the center of the cluster), which are distributed over the area O independently. Then, each home point randomly chooses one of the clusters with equal opportunity. Finally, the home points of the same cluster are belonged to a disk of radius R centered at the cluster middle point.Considering the asymptotic performance, we assume thatm=nν, 0<ν<1 and the cluster density over the whole network area ρc=nν/n=nν−1. The average distance between two cluster middle points is dc=n1−ν/2. For the ease of analysis, we do not consider the cluster overlapping behavior. Hence, the cluster radius should be satisfied by R=odc.


### 2.2. Content Request Model

In the mobile content-centric networks, there areM distinct content objects of same size, where M=nγ,0<γ<1. We assume each mobile node is equipped with an equal-sized local cache, which can store K content objects (K is a positive constant). For the problem to be not trivial, we assume K<M, that is, each node has to decide which kinds of content to cache. We refer to a mobile node requesting a desired content k,1≤k≤M at any time slot as the requseter of content k. We call a mobile node carrying a content k in its local cache the holder of content k.In this paper, a caching scheme consists of two phases: content placement and content retrieve [22]. In the content placement phase, each node randomly and independently chooses contents to be stored in its local cache. Let Nk denote the set of nodes that cache content k∈M in their local caches, where Nk=Nk. Thus, the probability that the content k is cached by a mobile node in its local cache is Nk/n. In order to achieve a feasible cache allocation, the total cache constraint should be satisfied.
(2)∑k=1MNk≤nK.In the content retrieve phase, each holder decides whether to deliver the requested content to the corresponding requester. During the retrieve phase, each node requests its desired content independently according to a Zipf popularity distribution [39], i.e., the request probability pk of content k∈M is satisfied by
(3)pk=k−αHαM,where α>0 is the Zipf’s law exponent and HαM=∑k=1Mk−α is a normalization constant and is given by
(4)HαM=Θ1,α>1,ΘlogM,α=1,ΘM1−α,α<1.


### 2.3. Interference Model

In this paper, to avoid multiuser simultaneous transmission interference, we adopt the protocol model in [2]. Moreover, we assume that the transmission range of mobile node i is Ti. If the content k is transmitted from mobile node i to node j successfully, then the following two conditions should be held:
(1)
The distance between the transmitteri and the receiver j is no more than Ti, i.e.,(5)Xit−Xjt≤Ti.(2)
Other transmitterl delivering different contents at the same time slot does not interfere the receiver j, i.e.,(6)Xlt−Xjt≥1+ΔTi.Here,Δ>0 denotes a constant guard factor. Xit denotes the location of a mobile node at the time slot t. ∙ denotes the Euclidean distance between the transmitter and the receiver. We further assume that each mobile node can deliver the contents at a constant rate W bits/sec.


### 2.4. Definitions

Definition 1.
For a given scheduling and routing scheme, letFi,t be the total number of bits of the requested contents received by mobile node i up to time t. We define the long-term throughput of mobile node i is
(7)liminft⟶∞1tFi,t.The average throughput over all nodes is given as(8)1n∑i=1nliminft⟶∞1tFi,t.The throughput is defined as the expectation of the average throughput over all mobile nodes,(9)λn=E1n∑i=1nliminft⟶∞1tFi,t.Definition 2.
The delay of a content retrieve process is the moment the interest packet leaves nodei until the requested content arrives at node i from the closest holder. For a given scheduling and routing scheme, let Di,d be the delay of the dth requested content of mobile node i. We define the long-term delay of mobile node i is
(10)limsupr⟶∞1r∑d=1rDi,d.The average delay over all nodes is given as(11)1n∑i=1nlimsupr⟶∞1r∑d=1rDi,d.The delay is defined as the expectation of the average delay over all mobile nodes.(12)Dn=E1n∑i=1nlimsupr⟶∞1r∑d=1rDi,d.To facilitate the understanding, some important notations applied in this paper are listed in Table1.Table 1
Summary of main notations.
SymbolsDefinitionsnThe number of mobile nodes, the area of network regionOmThe number of clustersMThe number of content objectsKThe size of a node’s local cachedcThe average distance between two cluster middle pointsρcThe cluster density over the whole network areaSaThe area of the cell in the clustered grid modelSa′The area of the cell in the clustered random modelpkThe request probability of contentkTiThe transmission radius of a mobile nodeshThe maximum hops from the requester to the closest holder


## 2.1. Mobility Model

In this paper, we adopt a bidimensional i.i.d mobility model for each mobile node, and time is divided into slots of equal duration. At the beginning of each slot, every node moves to a new location, which is independent of other nodes, and stays in the new location for the remaining duration of the slot. LetXit denote the location of node i at time t, and dij=Xit−Xjt denotes the distance between node i and node j.To characterize the spatial distribution of nodes, we assume that each nodei is associated with a home point Hi, which is uniformly and independently selected over the square region O. We consider that a node moves independently around its home point following a general ergodic process, which can be described by a rotationally invariant spatial distribution ϕd. Here, d denotes the Euclidean distance between the mobile node and its corresponding home point.We further assume thatϕd is an arbitrary nonincreasing function that decays as a power law of exponent δ, i.e., ϕd~d−δ,δ≥0. We take function sd=min1,d−δ and consider the following normalized probability density function (PDF) over the whole mobility area to avoid convergence problems in proximity of the home point.
(1)ϕd=sd∫Osd=Θsdnδ−2/2,0≤δ<2,Θsdlogn,δ=2,Θsd,δ>2.Exponentδ reflects the mobility degree of nodes, that is, the probability that each node moving to one point of the network area and stay at that point at a given time slot is not uniform. According to the PDF ϕd, it indicates that each node moves in a limited region, differing from the global mobility. In addition, the probability for the node moving in the proximity of its corresponding home point is larger than the probability that the node moves to the relatively far network area.However, exponentδ just describes the individual mobility behavior and cannot reflect the mobile node density over the network area at a time slot. In real mobile world, the mobile node density is tightly related with the number of home points. Mobile nodes are more likely to move around the hotspots [36] or social spots [37]. For example, the density of mobile terminals (e.g., phones and ipads) is relatively dense in the office buildings or the tourist attractions while the density of mobile terminals in the suburb is reversely sparse due to the less home points. That is, the number of home points will affect the spatial distribution of mobile nodes. Motivated by this fact, clustering behavior has been found in [32, 33, 38] based on the long-term observations. In our work, we introduce the clustered model combined with the distribution of home points. First, we assume m clusters and each cluster has a middle point (the center of the cluster), which are distributed over the area O independently. Then, each home point randomly chooses one of the clusters with equal opportunity. Finally, the home points of the same cluster are belonged to a disk of radius R centered at the cluster middle point.Considering the asymptotic performance, we assume thatm=nν, 0<ν<1 and the cluster density over the whole network area ρc=nν/n=nν−1. The average distance between two cluster middle points is dc=n1−ν/2. For the ease of analysis, we do not consider the cluster overlapping behavior. Hence, the cluster radius should be satisfied by R=odc.


## 2.2. Content Request Model

In the mobile content-centric networks, there areM distinct content objects of same size, where M=nγ,0<γ<1. We assume each mobile node is equipped with an equal-sized local cache, which can store K content objects (K is a positive constant). For the problem to be not trivial, we assume K<M, that is, each node has to decide which kinds of content to cache. We refer to a mobile node requesting a desired content k,1≤k≤M at any time slot as the requseter of content k. We call a mobile node carrying a content k in its local cache the holder of content k.In this paper, a caching scheme consists of two phases: content placement and content retrieve [22]. In the content placement phase, each node randomly and independently chooses contents to be stored in its local cache. Let Nk denote the set of nodes that cache content k∈M in their local caches, where Nk=Nk. Thus, the probability that the content k is cached by a mobile node in its local cache is Nk/n. In order to achieve a feasible cache allocation, the total cache constraint should be satisfied.
(2)∑k=1MNk≤nK.In the content retrieve phase, each holder decides whether to deliver the requested content to the corresponding requester. During the retrieve phase, each node requests its desired content independently according to a Zipf popularity distribution [39], i.e., the request probability pk of content k∈M is satisfied by
(3)pk=k−αHαM,where α>0 is the Zipf’s law exponent and HαM=∑k=1Mk−α is a normalization constant and is given by
(4)HαM=Θ1,α>1,ΘlogM,α=1,ΘM1−α,α<1.


## 2.3. Interference Model

In this paper, to avoid multiuser simultaneous transmission interference, we adopt the protocol model in [2]. Moreover, we assume that the transmission range of mobile node i is Ti. If the content k is transmitted from mobile node i to node j successfully, then the following two conditions should be held:
(1)
The distance between the transmitteri and the receiver j is no more than Ti, i.e.,(5)Xit−Xjt≤Ti.(2)
Other transmitterl delivering different contents at the same time slot does not interfere the receiver j, i.e.,(6)Xlt−Xjt≥1+ΔTi.Here,Δ>0 denotes a constant guard factor. Xit denotes the location of a mobile node at the time slot t. ∙ denotes the Euclidean distance between the transmitter and the receiver. We further assume that each mobile node can deliver the contents at a constant rate W bits/sec.


## 2.4. Definitions

Definition 1.
For a given scheduling and routing scheme, letFi,t be the total number of bits of the requested contents received by mobile node i up to time t. We define the long-term throughput of mobile node i is
(7)liminft⟶∞1tFi,t.The average throughput over all nodes is given as(8)1n∑i=1nliminft⟶∞1tFi,t.The throughput is defined as the expectation of the average throughput over all mobile nodes,(9)λn=E1n∑i=1nliminft⟶∞1tFi,t.Definition 2.
The delay of a content retrieve process is the moment the interest packet leaves nodei until the requested content arrives at node i from the closest holder. For a given scheduling and routing scheme, let Di,d be the delay of the dth requested content of mobile node i. We define the long-term delay of mobile node i is
(10)limsupr⟶∞1r∑d=1rDi,d.The average delay over all nodes is given as(11)1n∑i=1nlimsupr⟶∞1r∑d=1rDi,d.The delay is defined as the expectation of the average delay over all mobile nodes.(12)Dn=E1n∑i=1nlimsupr⟶∞1r∑d=1rDi,d.To facilitate the understanding, some important notations applied in this paper are listed in Table1.Table 1
Summary of main notations.
SymbolsDefinitionsnThe number of mobile nodes, the area of network regionOmThe number of clustersMThe number of content objectsKThe size of a node’s local cachedcThe average distance between two cluster middle pointsρcThe cluster density over the whole network areaSaThe area of the cell in the clustered grid modelSa′The area of the cell in the clustered random modelpkThe request probability of contentkTiThe transmission radius of a mobile nodeshThe maximum hops from the requester to the closest holder


## 3. Throughput and Delay Analysis

For better understanding of content placement and retrieve process in the clustered random model, we first investigate the throughput and delay performance in the clustered grid model [33] in Section III-A, that is, the home points are placed regularly, which can be considered as a special instance of the distribution of the home points. In the real world, the home points can be deployed regularly, for example, the base stations (BSs) and the road side units (RSUs). In general, the BSs are deployed in the center of the cells, and the RSUs are deployed along the road (i.e., one RSU every 50 meters), which can be regarded as the examples of the grid clustered model. In Section III-B, we analyze the case of clustered random model. Specifically, when δ≤2 and n goes to infinity, the spatial distribution ϕd tends to 0; we leave to the analysis of the network performance in this case for future work.


### 3.1. Clustered Grid Model

In the clustered grid model, we divide the whole network region into equal-sized cells of areaSa=dc2. The distribution of clusters should satisfy following two conditions:
(i)
The middle point of each cluster is located at the center of each cell, and the distance between two adjacent cluster middle points isdc(ii)
The radii of all clusters equal to 0, i.e., the home points of the same cluster are gathered at their corresponding cluster’s middle point (or the cell center).Before introducing scheduling and routing schemes, we premise a necessary lemma that guarantees each cell has at least one mobile node at a time slot and the expected number of nodes in each cell isΘn1−ν which guarantees the network connectivity.Lemma 3.
In the clustered grid model, assumingε=Θloglogn/logn, for any 0<ν<1−ε, each cell has at least one mobile node and the expected number of nodes in each cell Sa is NSa¯=Θn1−ν in a given slot with high probability.Proof.
For an arbitrary cell, in a given slot, the probability that one node moves to any cell isdc2/n, i.e., n−ν. Hence, the probability pc that each cell has at least one mobile node is
(13)pc=1−1−n−νn=1−enlog1−n−ν≥1−e−n1−ν,where the last inequality follows that log1+x≤x for x>−1. Let pc′=1−e−n1−ν and pc≥pc′. By assuming ε=Θloglogn/logn, for any 0<ν<1−ε, we have n1−ν≥logn. Note that when n goes infinity, ε tends to 0; the upper bound of ν is 1. Then, we have
(14)pc′=1−e−n1−ν≥1−e−logn=1−1n,which tends to 1 when n goes infinity. Hence, with high probability, each cell has at least one mobile node in a given slot.
LetNSa denote the number of nodes in the cell Sa, by definition:
(15)NSa=∑i=1nIXi∈Sa,where IXi∈Sa is an i.i.d Bernoullian random variable, and IXi∈Sa=1 if node i is in the cell Sa; otherwise, IXi∈Sa=0. Hence,
(16)ENSa=E∑i=1nIXi∈Sa=∑i=1nEIXi∈Sa=n·San=Sa.
We apply Chernoff bounds and have(17)PNSa<12ENSa≤e−∣Sa∣/8,PNSa>2ENSa≤e−∣Sa∣/3<e−∣Sa∣/8.
Then, lettingε=Θloglogn/logn, for any 0<ν<1−ε, we have ∣Sa∣=n1−ν≥16logn. Thus, we have
(18)P12ENSa≤NSa≤2ENSa≥1−2e−∣Sa∣/8≥1−2e−2logn=1−2n−2,
which tends to 1 whenn goes infinity. Hence, we obtain the expected number of nodes in each cell is Θn1−ν.


#### 3.1.1. Scheduling Schemes

At a given slot, a scheduling scheme enables the contents retrieve between transmitter-receiver pairs not to be interfered. Based on the mobility model and the spatial distribution of mobile node, we adopt a cell-partition-based TDMA scheduling scheme to avoid the multiuser simultaneous transmission interference and to maximize the number of noninterfering transmission pairs at a time slot. Figure1(a) illustrates a general real-world node distribution case, which shows mobile terminals are relatively dense near the home point, and there are fewer mobile terminals far away from home point. Figure 1(b) illustrates home points are deployed regularly and can be regarded as a clustered grid model. Figure 1(c) shows a cell-partition-based TDMA scheduling scheme corresponding to the time slot division, which guarantees multihop transmission in the clustered grid model.Figure 1
(a) A general real-world node distribution case. (b) Home points are deployed regularly and regarded as the clustered grid model. (c) A cell-partition-based TDMA scheduling scheme corresponding to the time slot division (the central cell is divided into 9 squares).We first divide each time slot into two half slots with equal length. Then, in the first half slot, we further divide the first half slot into several subslots with equal length. We partition each cellSa into squares with same area Se (Se will be defined later). We call a square is active if a node in this square can transmit an interest packet or a content during the subslot. Based on the square partition, we assume that a node in a square can transmit an interest packet or a content to the node in the same square or the adjacent eight squares. We define the transmission radius of the node i as Ti=Θdc. Hence, we obtain the following lemma according to the protocol model, which is essential to describe the noninterfering transmission process.Lemma 4.
Each square can be active at most every1+c1 time subslots, and the achievable rate at the active square is W/1+c1.Proof.
According to the interference model, we consider the distance between transmitterXi and receiver Xj is bounded by Ti=Θdc. If there is another simultaneously transmitting node Xl at the same time subslot and the transmission distance between Xl and Xj is less than 2+ΔTi, then Xl will cause the interference with Xj. Hence, the area of the total interference region is bounded by 22+ΔTi+3Ti2. We obtain that each square has at most c1=22+ΔTi+3Ti2/Ti2=22+Δ+32 interference neighbouring squares, which is a constant and independent of n.
Each square gets a noninterfering transmission opportunity and becomes active in every1+c1 time subslots. Since each transmitter-receiver pair can send W bits in a successful transmission, the achievable transmission rate at the active square is W/1+c1.From Lemma4, we can construct 1+c1 subsets of regularly spaced, simultaneously transmitting squares without interference.Next, we calculate the area of each squareSe. From Lemma 3, we obtain the average number of nodes in each cell Sa is Θn1−ν. We assume there exists point A in the cell that the distance between A and the home point is d. The mobility process of each node is independent at each slot, and the probability that the node moves to point A is Θd−δ at each slot according to the node distribution. Hence, when δ>2, the density of nodes at point A is Θn1−ν/dδ at each slot. Applying Lemma 4 in [33], we can obtain the maximum density of achievable transmitter-receiver pairs (T-R pairs) when d=dc/2. Thus, the density of T-R pairs at any point of the network scales as ϕc=Θn1−ν/dcδ=Θn1−ν1−δ/2. Therefore, the area of each square is equal to 1/ϕc, i.e., Se=Θn−1−ν1−δ/2.At a given time slot, each cell can schedule the number of concurrent noninterfering transmissionsχ is
(19)χ=Θdc21+c11/ϕc=Θn1−ν2−δ/2.Since the area of each square isΘn−1−ν1−δ/2, we can acquire that the probability that at least one node in a subcell is a constant by applying Lemma 3.


#### 3.1.2. Routing Schemes

Considering the mobility model of nodes and the clustering behavior, we propose a multihop transmission schemeΠ for the content transmission between the requester-holder pairs. We assume the content request and delivery process of each node is conducted in one time slot. According to the maximum hops (derived in the following section) in the clustered grid model, the value of the one time slot can be set as Ωnν/2 to guarantee the multihop transmission within one time slot.Π-1: according to the TDMA scheduling phase, each time slot is divided into two half slots with equal length.Π-2: during the first half slot, we further divide the first half slot into several subslots with equal length. Each cell is divided into squares with the same area,
(1)
if there is one requested content in the same square (or the same cluster), the requesteri directly forwards an interest packet to the holder(2)
if there is no any requester-holder pair in the same square (or the same cluster), the requesteri sends an interest packet to the relay node in the adjacent square at the beginning of subslot; multihop is used for all relay nodes until the interest packet reached the nearest holder. Furthermore, we assume that the first hop towards the adjacent subcell is on the horizon path (if possible) and then on the vertical pathΠ-3: during the second half slot, we continue dividing the second half slot into several subslots with equal length,(1)if there is one requested content in the same square (or the same cluster), the requested content will be directly forwarded back to the requesteri. In this case, the requested content will be achieved in one hop(2)if there is no any requester-holder pair in the same square (or the same cluster), the nearest holder receives the interest packet in the first half slot, and then, the nearest holder in the second half slot sends the requested content back to its corresponding requester in the reverse directionLemma 5.
In the clustered grid model, for any node requesting contentk, the probability Pk that an interest packet for content k is satisfied by one hop is minΘNkn1−νδ/2−1−1,1.Proof.
For an arbitrary square, the probability that there is at least one requested contentk within the same square or the adjacent squares of the requester is 9Se/n=9n1−νδ/2−1/n=9n1−νδ/2−1−1. Thus,
(20)Pk=1−1−9n1−νδ/2−1−1Nk≤9Nkn1−νδ/2−1−1.
The inequality follows that1+xn≥1+nx for any x>−1. If 9Nkn1−νδ/2−1−1=o1, then Pk=ΘNkn1−νδ/2−1−1; otherwise, Pk=1.In the clustered grid model, due to the transmission radius of each node isΘdc, we can derive the maximum number of hops from a content requester to the closest holder is h=Θnν/2.Lemma 6.
In clustered grid model, for any mobile node requesting contentk, the average number of hops needed to transmit an interest packet along the path from the content requester to the closest content holder, denoted by EHk, is
(21)EHk=Θ1,Nk=Ωn1−1−νδ/2−1,Θ1Nkn1−νδ/2−1−1,Nk=on1−1−νδ/2−1&Nk=Ωn1/2−1−νδ/2−3/2,Θnν/2,Nk=on1/2−1−νδ/2−3/2.Proof.
LetHk denote the number of hops along the requesting path, and we have
(22)EHk=∑i=1h−1i·Pk1−Pki−1+h1−Pkh−1=∑i=1h1−Pki−1=1−1−PkhPk.
Based on Lemma5 and the value of h, we consider three different conditions to further derive EHk.
(1)IfPk=Θ1, then EHk=Θ1.
(2)IfPk=o1 and hPk=Ω1, 1−1−Pkh≥1−e−hPk=Θ1. Hence, we obtain that EHk=Θ1/Pk.
(3)IfPk=o1 and hPk=o1, applying the equivalent infinitesimal, we obtain that 1−1−Pkh≈1−1−hPk≈ΘhPk. Hence, we get that EHk=Θh.
This completes the proof.Theorem 7.
In the clustered grid model, the delay and throughput of each mobile node, denoted byDn and λn, are given by w.h.p.
(23)Dn=Θ∑m=1MpkEHk,(24)λn=Θn1−ν1−δ/2∑m=1MpkEHk.Proof.
First, we consider the delay performance. Based on the scheduling and routing scheme, each square can be active in every1+c1 time subslots, where c1 is a constant. Thus, the time spent in each hop is a constant fraction of time. In Lemma 6, we obtain the average number of hops from a requester to the closest holder for content k is EHk. In addition, the requested content forwarded back to the requester takes the same route as its corresponding interest packet in reverse direction, the total number of hops for content k is 2EHk. Taking the request probability pk for the content k into consideration, we get the delay for all contents over the network as (6).
Next, we derive the throughput performance. Since there areΘnν cells over the network area, and the total number of bits that active squares in a cell can transmit is W/1+c1n1−ν2−δ/2. Lemma 6 indicates the average number of hops for content k is EHk. Considering the request probability pk for the content k, we obtain the average number of bits transmitted in the whole network is nλn∑m=1MpkEHk. Then, we have
(25)nλn∑m=1MpkEHk≤W1+c1n1−ν2−δ/2·nν,λn≤n1−ν1−δ/2∑m=1MpkEHk.
The achievable throughput of each mobile node is determined by the scheduling and routing scheme. Hence, we obtain the throughput performance as (24).Corollary 8.
The throughput and delay tradeoff in the clustered grid model is given by(26)λn=Θn1−ν1−δ/2Dn.


### 3.2. Clustered Random Model

In this section, we analyze the throughput and delay of each node in the clustered random model, where clusters are distributed randomly and independently in the network, that is, the home points are deployed in a random manner.We first introduce an important lemma given in [31]. This lemma indicates the appropriate partition of the whole network area can guarantee that the average number of clusters in each cell is Θlogn, which makes the multihop transmission in the clustered random model possible.Lemma 9.
Consider a set ofm points independently distributed over a bidimensional domain O of area n, with density ρ=m/n. The domain O is partitioned by regular tessellations, and As denotes the tiles over the tessellations with area As≥16logm/ρ, ∀s. Let NAs be the number of nodes falling within the tiles As. Then, uniformly over the tessellation, NAs is contained between ρAs/2 and 2ρAs with high probability, i.e.,
(27)ρAs2<infsNAs≤supsNAs<2ρAs.This lemma can be proved by the Chernoff bound in [40]; we neglect the proof process for simplicity.Considering Lemma9 and the cluster density ρc=nν−1, we partition the whole network into equal-sized cells with area Sa′=16lognν/nν−1=Θn1−νlogn. Note that we choose the equal-sized cell area in the clustered random model in order to make sure that nodes in each cluster has the opportunity to retrieve the content; in fact, we can choose different size area only if Sa′≥Θn1−νlogn. Thus, we can obtain the expected number of clusters in each cell is Θlogn. We assume that the transmission radius of each mobile node in the clustered random model is Tn=Θn1−ν/2logn, which guarantees the nodes can communicate with the nodes in their neighbor cells. Since the maximum distance between the requester and the closest holder is Θn1/2, the maximum number of hops from a content requester to the closest holder is h=Θnν/2/logn.Based on the cell partition, we obtain the following lemma that guarantees the average number of nodes in every cluster isΘn1−ν.Lemma 10.
In the clustered random model, the average number of node in every cluster isΘn1−ν.Proof.
The proof process of this lemma is similar to that in Lemma3 by applying he Chernoff bound.The density of T-S pairs at any point of the network scales asϕ′c=Θn1−ν/nδ1−ν/2logδ/2n=Θn1−ν1−δ/2log−δ/2n. We further partition each cell into squares with area 1/ϕ′c, i.e., S′e=Θn1−νδ/2−1logδ/2n. Hence, each active cell can schedule the number of concurrent noninterfering transmissions χ′ is
(28)χ′=ΘS1+c21/ϕ′c=Θn1−νlognn1−νδ/2−1logδ/2n=Θn1−ν2−δ/2log1−δ/2n.Hence, a noninterference scheduling scheme in the clustered random model can be designed as following steps. First, we divide the whole network into equal-sized cells with areaΘn1−νlogn, which makes the transmission connectivity possible. Then, we partition each cell into equal-sized squares with area Θn1−νδ/2−1logδ/2n, which guarantees the content transmission free from interference. Figure 2 shows the cell partition and the content request process in the clustered random model. Finally, a routing scheme similar with that in the cluster grid model can be utilized to achieve the content multihop transmission at a given slot.Lemma 11.
In the clustered random model, for any node requesting contentk, the probability P′k that an interest packet for content k is satisfied by one hop is minΘNkn1−νδ/2−1−1logδ/2n,1.Proof.
For an arbitrary square, the probability that there is at least one requested contentk is within the same square or the adjacent squares of the requester is 9Se′/n=9n1−νδ/2−1logδ/2n/n=9n1−νδ/2−1−1logδ/2n. Thus, we have
(29)P′k=1−1−9n1−νδ/2−1−1logδ/2nNk≤9Nkn1−νδ/2−1−1logδ/2n.
The inequality follows that1+xn≥1+nx for any x>−1. If 9Nkn1−νδ/2−1−1logδ/2n=o1, then P′k=ΘNkn1−νδ/2−1−1logδ/2n. Otherwise, P′k=1.Lemma 12.
In the clustered random model, for any mobile node requesting contentk, the average number of hops needed to transmit an interest packet along the path from the content requester to the closest content holder, denoted by E′Hk, is
(30)E′Hk=Θ1,Nk=Ωn1−1−νδ/2−1logδ/2n,Θn1/2−1−νδ/2−3/2Nklogδ/2n,Nk=on1−1−νδ/2−1logδ/2n&Nk=Ωn1/2−1−νδ/2−3/2logδ/2n,Θnν/2logn,Nk=on1/2−1−νδ/2−3/2logδ/2n.Proof.
According to Lemma6, we have
(31)E′Hk=1−1−P′khP′k.
Based on the value ofh and P′k, we consider three different conditions to further derive E′Hk.
(1)IfP′k=Θ1, then E′Hk=1
(2)IfP′k=o1 and hP′k=Ω1, 1−1−P′kh≥1−e−hP′k=Θ1. Hence, we obtain that E′Hk=Θ1/P′k=Θn1/2−1−νδ/2−3/2/Nklogδ/2n.
(3)IfP′k=o1 and hP′k=o1, applying the equivalent infinitesimal, we obtain that 1−1−P′kh≈1−e−hP′k≈ΘhP′k. Hence, we get that E′Hk=Θh=Θnν/2/logn.
This completes the proof.Theorem 13.
In the clustered random model, the delay and throughput of each mobile node, denoted byDn and λn, are given by w.h.p.
(32)Dn=Θ∑m=1MpkE′Hk,λn=Θn1−ν1−δ/2log−δ/2n∑m=1MpkE′Hk.Proof.
The proof of delay performance is similar to that of Theorem7, and we do not repeat it for simplicity.
We analyze the throughput performance of each node. Based on the cell partition of the network, we can obtain the total number of cells isΘnν/logn. Considering the scheduling scheme and routing scheme, the total number of bits that active square in a cell can transmit is W/1+c2n1−ν2−δ/2log1−δ/2n. Moreover, Lemma 12 indicates the average number of hops for content k is E′Hk. Since the request probability of the content k is pk, the average number of bits transmitted in the whole network can be calculated as nλn∑m=1MpkE′Hk. The rest proof is similar to the Theorem 7; we neglect it here for simplicity.Figure 2
The cell partition and the content request process in the clustered random model.From Theorem13, we can conclude that the difference of throughput and delay performance between the clustered random model and the clustered grid model is the logarithm factor and the average transmission hops.Corollary 14.
The throughput and delay tradeoff in the clustered random model is given by(33)λn=Θn1−ν1−δ/2Dnlogδ/2n,which differs from Corollary 8 by a factor log−δ/2n.


## 3.1. Clustered Grid Model

In the clustered grid model, we divide the whole network region into equal-sized cells of areaSa=dc2. The distribution of clusters should satisfy following two conditions:
(i)
The middle point of each cluster is located at the center of each cell, and the distance between two adjacent cluster middle points isdc(ii)
The radii of all clusters equal to 0, i.e., the home points of the same cluster are gathered at their corresponding cluster’s middle point (or the cell center).Before introducing scheduling and routing schemes, we premise a necessary lemma that guarantees each cell has at least one mobile node at a time slot and the expected number of nodes in each cell isΘn1−ν which guarantees the network connectivity.Lemma 3.
In the clustered grid model, assumingε=Θloglogn/logn, for any 0<ν<1−ε, each cell has at least one mobile node and the expected number of nodes in each cell Sa is NSa¯=Θn1−ν in a given slot with high probability.Proof.
For an arbitrary cell, in a given slot, the probability that one node moves to any cell isdc2/n, i.e., n−ν. Hence, the probability pc that each cell has at least one mobile node is
(13)pc=1−1−n−νn=1−enlog1−n−ν≥1−e−n1−ν,where the last inequality follows that log1+x≤x for x>−1. Let pc′=1−e−n1−ν and pc≥pc′. By assuming ε=Θloglogn/logn, for any 0<ν<1−ε, we have n1−ν≥logn. Note that when n goes infinity, ε tends to 0; the upper bound of ν is 1. Then, we have
(14)pc′=1−e−n1−ν≥1−e−logn=1−1n,which tends to 1 when n goes infinity. Hence, with high probability, each cell has at least one mobile node in a given slot.
LetNSa denote the number of nodes in the cell Sa, by definition:
(15)NSa=∑i=1nIXi∈Sa,where IXi∈Sa is an i.i.d Bernoullian random variable, and IXi∈Sa=1 if node i is in the cell Sa; otherwise, IXi∈Sa=0. Hence,
(16)ENSa=E∑i=1nIXi∈Sa=∑i=1nEIXi∈Sa=n·San=Sa.
We apply Chernoff bounds and have(17)PNSa<12ENSa≤e−∣Sa∣/8,PNSa>2ENSa≤e−∣Sa∣/3<e−∣Sa∣/8.
Then, lettingε=Θloglogn/logn, for any 0<ν<1−ε, we have ∣Sa∣=n1−ν≥16logn. Thus, we have
(18)P12ENSa≤NSa≤2ENSa≥1−2e−∣Sa∣/8≥1−2e−2logn=1−2n−2,
which tends to 1 whenn goes infinity. Hence, we obtain the expected number of nodes in each cell is Θn1−ν.


### 3.1.1. Scheduling Schemes

At a given slot, a scheduling scheme enables the contents retrieve between transmitter-receiver pairs not to be interfered. Based on the mobility model and the spatial distribution of mobile node, we adopt a cell-partition-based TDMA scheduling scheme to avoid the multiuser simultaneous transmission interference and to maximize the number of noninterfering transmission pairs at a time slot. Figure1(a) illustrates a general real-world node distribution case, which shows mobile terminals are relatively dense near the home point, and there are fewer mobile terminals far away from home point. Figure 1(b) illustrates home points are deployed regularly and can be regarded as a clustered grid model. Figure 1(c) shows a cell-partition-based TDMA scheduling scheme corresponding to the time slot division, which guarantees multihop transmission in the clustered grid model.Figure 1
(a) A general real-world node distribution case. (b) Home points are deployed regularly and regarded as the clustered grid model. (c) A cell-partition-based TDMA scheduling scheme corresponding to the time slot division (the central cell is divided into 9 squares).We first divide each time slot into two half slots with equal length. Then, in the first half slot, we further divide the first half slot into several subslots with equal length. We partition each cellSa into squares with same area Se (Se will be defined later). We call a square is active if a node in this square can transmit an interest packet or a content during the subslot. Based on the square partition, we assume that a node in a square can transmit an interest packet or a content to the node in the same square or the adjacent eight squares. We define the transmission radius of the node i as Ti=Θdc. Hence, we obtain the following lemma according to the protocol model, which is essential to describe the noninterfering transmission process.Lemma 4.
Each square can be active at most every1+c1 time subslots, and the achievable rate at the active square is W/1+c1.Proof.
According to the interference model, we consider the distance between transmitterXi and receiver Xj is bounded by Ti=Θdc. If there is another simultaneously transmitting node Xl at the same time subslot and the transmission distance between Xl and Xj is less than 2+ΔTi, then Xl will cause the interference with Xj. Hence, the area of the total interference region is bounded by 22+ΔTi+3Ti2. We obtain that each square has at most c1=22+ΔTi+3Ti2/Ti2=22+Δ+32 interference neighbouring squares, which is a constant and independent of n.
Each square gets a noninterfering transmission opportunity and becomes active in every1+c1 time subslots. Since each transmitter-receiver pair can send W bits in a successful transmission, the achievable transmission rate at the active square is W/1+c1.From Lemma4, we can construct 1+c1 subsets of regularly spaced, simultaneously transmitting squares without interference.Next, we calculate the area of each squareSe. From Lemma 3, we obtain the average number of nodes in each cell Sa is Θn1−ν. We assume there exists point A in the cell that the distance between A and the home point is d. The mobility process of each node is independent at each slot, and the probability that the node moves to point A is Θd−δ at each slot according to the node distribution. Hence, when δ>2, the density of nodes at point A is Θn1−ν/dδ at each slot. Applying Lemma 4 in [33], we can obtain the maximum density of achievable transmitter-receiver pairs (T-R pairs) when d=dc/2. Thus, the density of T-R pairs at any point of the network scales as ϕc=Θn1−ν/dcδ=Θn1−ν1−δ/2. Therefore, the area of each square is equal to 1/ϕc, i.e., Se=Θn−1−ν1−δ/2.At a given time slot, each cell can schedule the number of concurrent noninterfering transmissionsχ is
(19)χ=Θdc21+c11/ϕc=Θn1−ν2−δ/2.Since the area of each square isΘn−1−ν1−δ/2, we can acquire that the probability that at least one node in a subcell is a constant by applying Lemma 3.


### 3.1.2. Routing Schemes

Considering the mobility model of nodes and the clustering behavior, we propose a multihop transmission schemeΠ for the content transmission between the requester-holder pairs. We assume the content request and delivery process of each node is conducted in one time slot. According to the maximum hops (derived in the following section) in the clustered grid model, the value of the one time slot can be set as Ωnν/2 to guarantee the multihop transmission within one time slot.Π-1: according to the TDMA scheduling phase, each time slot is divided into two half slots with equal length.Π-2: during the first half slot, we further divide the first half slot into several subslots with equal length. Each cell is divided into squares with the same area,
(1)
if there is one requested content in the same square (or the same cluster), the requesteri directly forwards an interest packet to the holder(2)
if there is no any requester-holder pair in the same square (or the same cluster), the requesteri sends an interest packet to the relay node in the adjacent square at the beginning of subslot; multihop is used for all relay nodes until the interest packet reached the nearest holder. Furthermore, we assume that the first hop towards the adjacent subcell is on the horizon path (if possible) and then on the vertical pathΠ-3: during the second half slot, we continue dividing the second half slot into several subslots with equal length,(1)if there is one requested content in the same square (or the same cluster), the requested content will be directly forwarded back to the requesteri. In this case, the requested content will be achieved in one hop(2)if there is no any requester-holder pair in the same square (or the same cluster), the nearest holder receives the interest packet in the first half slot, and then, the nearest holder in the second half slot sends the requested content back to its corresponding requester in the reverse directionLemma 5.
In the clustered grid model, for any node requesting contentk, the probability Pk that an interest packet for content k is satisfied by one hop is minΘNkn1−νδ/2−1−1,1.Proof.
For an arbitrary square, the probability that there is at least one requested contentk within the same square or the adjacent squares of the requester is 9Se/n=9n1−νδ/2−1/n=9n1−νδ/2−1−1. Thus,
(20)Pk=1−1−9n1−νδ/2−1−1Nk≤9Nkn1−νδ/2−1−1.
The inequality follows that1+xn≥1+nx for any x>−1. If 9Nkn1−νδ/2−1−1=o1, then Pk=ΘNkn1−νδ/2−1−1; otherwise, Pk=1.In the clustered grid model, due to the transmission radius of each node isΘdc, we can derive the maximum number of hops from a content requester to the closest holder is h=Θnν/2.Lemma 6.
In clustered grid model, for any mobile node requesting contentk, the average number of hops needed to transmit an interest packet along the path from the content requester to the closest content holder, denoted by EHk, is
(21)EHk=Θ1,Nk=Ωn1−1−νδ/2−1,Θ1Nkn1−νδ/2−1−1,Nk=on1−1−νδ/2−1&Nk=Ωn1/2−1−νδ/2−3/2,Θnν/2,Nk=on1/2−1−νδ/2−3/2.Proof.
LetHk denote the number of hops along the requesting path, and we have
(22)EHk=∑i=1h−1i·Pk1−Pki−1+h1−Pkh−1=∑i=1h1−Pki−1=1−1−PkhPk.
Based on Lemma5 and the value of h, we consider three different conditions to further derive EHk.
(1)IfPk=Θ1, then EHk=Θ1.
(2)IfPk=o1 and hPk=Ω1, 1−1−Pkh≥1−e−hPk=Θ1. Hence, we obtain that EHk=Θ1/Pk.
(3)IfPk=o1 and hPk=o1, applying the equivalent infinitesimal, we obtain that 1−1−Pkh≈1−1−hPk≈ΘhPk. Hence, we get that EHk=Θh.
This completes the proof.Theorem 7.
In the clustered grid model, the delay and throughput of each mobile node, denoted byDn and λn, are given by w.h.p.
(23)Dn=Θ∑m=1MpkEHk,(24)λn=Θn1−ν1−δ/2∑m=1MpkEHk.Proof.
First, we consider the delay performance. Based on the scheduling and routing scheme, each square can be active in every1+c1 time subslots, where c1 is a constant. Thus, the time spent in each hop is a constant fraction of time. In Lemma 6, we obtain the average number of hops from a requester to the closest holder for content k is EHk. In addition, the requested content forwarded back to the requester takes the same route as its corresponding interest packet in reverse direction, the total number of hops for content k is 2EHk. Taking the request probability pk for the content k into consideration, we get the delay for all contents over the network as (6).
Next, we derive the throughput performance. Since there areΘnν cells over the network area, and the total number of bits that active squares in a cell can transmit is W/1+c1n1−ν2−δ/2. Lemma 6 indicates the average number of hops for content k is EHk. Considering the request probability pk for the content k, we obtain the average number of bits transmitted in the whole network is nλn∑m=1MpkEHk. Then, we have
(25)nλn∑m=1MpkEHk≤W1+c1n1−ν2−δ/2·nν,λn≤n1−ν1−δ/2∑m=1MpkEHk.
The achievable throughput of each mobile node is determined by the scheduling and routing scheme. Hence, we obtain the throughput performance as (24).Corollary 8.
The throughput and delay tradeoff in the clustered grid model is given by(26)λn=Θn1−ν1−δ/2Dn.


## 3.1.1. Scheduling Schemes

At a given slot, a scheduling scheme enables the contents retrieve between transmitter-receiver pairs not to be interfered. Based on the mobility model and the spatial distribution of mobile node, we adopt a cell-partition-based TDMA scheduling scheme to avoid the multiuser simultaneous transmission interference and to maximize the number of noninterfering transmission pairs at a time slot. Figure1(a) illustrates a general real-world node distribution case, which shows mobile terminals are relatively dense near the home point, and there are fewer mobile terminals far away from home point. Figure 1(b) illustrates home points are deployed regularly and can be regarded as a clustered grid model. Figure 1(c) shows a cell-partition-based TDMA scheduling scheme corresponding to the time slot division, which guarantees multihop transmission in the clustered grid model.Figure 1
(a) A general real-world node distribution case. (b) Home points are deployed regularly and regarded as the clustered grid model. (c) A cell-partition-based TDMA scheduling scheme corresponding to the time slot division (the central cell is divided into 9 squares).We first divide each time slot into two half slots with equal length. Then, in the first half slot, we further divide the first half slot into several subslots with equal length. We partition each cellSa into squares with same area Se (Se will be defined later). We call a square is active if a node in this square can transmit an interest packet or a content during the subslot. Based on the square partition, we assume that a node in a square can transmit an interest packet or a content to the node in the same square or the adjacent eight squares. We define the transmission radius of the node i as Ti=Θdc. Hence, we obtain the following lemma according to the protocol model, which is essential to describe the noninterfering transmission process.Lemma 4.
Each square can be active at most every1+c1 time subslots, and the achievable rate at the active square is W/1+c1.Proof.
According to the interference model, we consider the distance between transmitterXi and receiver Xj is bounded by Ti=Θdc. If there is another simultaneously transmitting node Xl at the same time subslot and the transmission distance between Xl and Xj is less than 2+ΔTi, then Xl will cause the interference with Xj. Hence, the area of the total interference region is bounded by 22+ΔTi+3Ti2. We obtain that each square has at most c1=22+ΔTi+3Ti2/Ti2=22+Δ+32 interference neighbouring squares, which is a constant and independent of n.
Each square gets a noninterfering transmission opportunity and becomes active in every1+c1 time subslots. Since each transmitter-receiver pair can send W bits in a successful transmission, the achievable transmission rate at the active square is W/1+c1.From Lemma4, we can construct 1+c1 subsets of regularly spaced, simultaneously transmitting squares without interference.Next, we calculate the area of each squareSe. From Lemma 3, we obtain the average number of nodes in each cell Sa is Θn1−ν. We assume there exists point A in the cell that the distance between A and the home point is d. The mobility process of each node is independent at each slot, and the probability that the node moves to point A is Θd−δ at each slot according to the node distribution. Hence, when δ>2, the density of nodes at point A is Θn1−ν/dδ at each slot. Applying Lemma 4 in [33], we can obtain the maximum density of achievable transmitter-receiver pairs (T-R pairs) when d=dc/2. Thus, the density of T-R pairs at any point of the network scales as ϕc=Θn1−ν/dcδ=Θn1−ν1−δ/2. Therefore, the area of each square is equal to 1/ϕc, i.e., Se=Θn−1−ν1−δ/2.At a given time slot, each cell can schedule the number of concurrent noninterfering transmissionsχ is
(19)χ=Θdc21+c11/ϕc=Θn1−ν2−δ/2.Since the area of each square isΘn−1−ν1−δ/2, we can acquire that the probability that at least one node in a subcell is a constant by applying Lemma 3.


## 3.1.2. Routing Schemes

Considering the mobility model of nodes and the clustering behavior, we propose a multihop transmission schemeΠ for the content transmission between the requester-holder pairs. We assume the content request and delivery process of each node is conducted in one time slot. According to the maximum hops (derived in the following section) in the clustered grid model, the value of the one time slot can be set as Ωnν/2 to guarantee the multihop transmission within one time slot.Π-1: according to the TDMA scheduling phase, each time slot is divided into two half slots with equal length.Π-2: during the first half slot, we further divide the first half slot into several subslots with equal length. Each cell is divided into squares with the same area,
(1)
if there is one requested content in the same square (or the same cluster), the requesteri directly forwards an interest packet to the holder(2)
if there is no any requester-holder pair in the same square (or the same cluster), the requesteri sends an interest packet to the relay node in the adjacent square at the beginning of subslot; multihop is used for all relay nodes until the interest packet reached the nearest holder. Furthermore, we assume that the first hop towards the adjacent subcell is on the horizon path (if possible) and then on the vertical pathΠ-3: during the second half slot, we continue dividing the second half slot into several subslots with equal length,(1)if there is one requested content in the same square (or the same cluster), the requested content will be directly forwarded back to the requesteri. In this case, the requested content will be achieved in one hop(2)if there is no any requester-holder pair in the same square (or the same cluster), the nearest holder receives the interest packet in the first half slot, and then, the nearest holder in the second half slot sends the requested content back to its corresponding requester in the reverse directionLemma 5.
In the clustered grid model, for any node requesting contentk, the probability Pk that an interest packet for content k is satisfied by one hop is minΘNkn1−νδ/2−1−1,1.Proof.
For an arbitrary square, the probability that there is at least one requested contentk within the same square or the adjacent squares of the requester is 9Se/n=9n1−νδ/2−1/n=9n1−νδ/2−1−1. Thus,
(20)Pk=1−1−9n1−νδ/2−1−1Nk≤9Nkn1−νδ/2−1−1.
The inequality follows that1+xn≥1+nx for any x>−1. If 9Nkn1−νδ/2−1−1=o1, then Pk=ΘNkn1−νδ/2−1−1; otherwise, Pk=1.In the clustered grid model, due to the transmission radius of each node isΘdc, we can derive the maximum number of hops from a content requester to the closest holder is h=Θnν/2.Lemma 6.
In clustered grid model, for any mobile node requesting contentk, the average number of hops needed to transmit an interest packet along the path from the content requester to the closest content holder, denoted by EHk, is
(21)EHk=Θ1,Nk=Ωn1−1−νδ/2−1,Θ1Nkn1−νδ/2−1−1,Nk=on1−1−νδ/2−1&Nk=Ωn1/2−1−νδ/2−3/2,Θnν/2,Nk=on1/2−1−νδ/2−3/2.Proof.
LetHk denote the number of hops along the requesting path, and we have
(22)EHk=∑i=1h−1i·Pk1−Pki−1+h1−Pkh−1=∑i=1h1−Pki−1=1−1−PkhPk.
Based on Lemma5 and the value of h, we consider three different conditions to further derive EHk.
(1)IfPk=Θ1, then EHk=Θ1.
(2)IfPk=o1 and hPk=Ω1, 1−1−Pkh≥1−e−hPk=Θ1. Hence, we obtain that EHk=Θ1/Pk.
(3)IfPk=o1 and hPk=o1, applying the equivalent infinitesimal, we obtain that 1−1−Pkh≈1−1−hPk≈ΘhPk. Hence, we get that EHk=Θh.
This completes the proof.Theorem 7.
In the clustered grid model, the delay and throughput of each mobile node, denoted byDn and λn, are given by w.h.p.
(23)Dn=Θ∑m=1MpkEHk,(24)λn=Θn1−ν1−δ/2∑m=1MpkEHk.Proof.
First, we consider the delay performance. Based on the scheduling and routing scheme, each square can be active in every1+c1 time subslots, where c1 is a constant. Thus, the time spent in each hop is a constant fraction of time. In Lemma 6, we obtain the average number of hops from a requester to the closest holder for content k is EHk. In addition, the requested content forwarded back to the requester takes the same route as its corresponding interest packet in reverse direction, the total number of hops for content k is 2EHk. Taking the request probability pk for the content k into consideration, we get the delay for all contents over the network as (6).
Next, we derive the throughput performance. Since there areΘnν cells over the network area, and the total number of bits that active squares in a cell can transmit is W/1+c1n1−ν2−δ/2. Lemma 6 indicates the average number of hops for content k is EHk. Considering the request probability pk for the content k, we obtain the average number of bits transmitted in the whole network is nλn∑m=1MpkEHk. Then, we have
(25)nλn∑m=1MpkEHk≤W1+c1n1−ν2−δ/2·nν,λn≤n1−ν1−δ/2∑m=1MpkEHk.
The achievable throughput of each mobile node is determined by the scheduling and routing scheme. Hence, we obtain the throughput performance as (24).Corollary 8.
The throughput and delay tradeoff in the clustered grid model is given by(26)λn=Θn1−ν1−δ/2Dn.


## 3.2. Clustered Random Model

In this section, we analyze the throughput and delay of each node in the clustered random model, where clusters are distributed randomly and independently in the network, that is, the home points are deployed in a random manner.We first introduce an important lemma given in [31]. This lemma indicates the appropriate partition of the whole network area can guarantee that the average number of clusters in each cell is Θlogn, which makes the multihop transmission in the clustered random model possible.Lemma 9.
Consider a set ofm points independently distributed over a bidimensional domain O of area n, with density ρ=m/n. The domain O is partitioned by regular tessellations, and As denotes the tiles over the tessellations with area As≥16logm/ρ, ∀s. Let NAs be the number of nodes falling within the tiles As. Then, uniformly over the tessellation, NAs is contained between ρAs/2 and 2ρAs with high probability, i.e.,
(27)ρAs2<infsNAs≤supsNAs<2ρAs.This lemma can be proved by the Chernoff bound in [40]; we neglect the proof process for simplicity.Considering Lemma9 and the cluster density ρc=nν−1, we partition the whole network into equal-sized cells with area Sa′=16lognν/nν−1=Θn1−νlogn. Note that we choose the equal-sized cell area in the clustered random model in order to make sure that nodes in each cluster has the opportunity to retrieve the content; in fact, we can choose different size area only if Sa′≥Θn1−νlogn. Thus, we can obtain the expected number of clusters in each cell is Θlogn. We assume that the transmission radius of each mobile node in the clustered random model is Tn=Θn1−ν/2logn, which guarantees the nodes can communicate with the nodes in their neighbor cells. Since the maximum distance between the requester and the closest holder is Θn1/2, the maximum number of hops from a content requester to the closest holder is h=Θnν/2/logn.Based on the cell partition, we obtain the following lemma that guarantees the average number of nodes in every cluster isΘn1−ν.Lemma 10.
In the clustered random model, the average number of node in every cluster isΘn1−ν.Proof.
The proof process of this lemma is similar to that in Lemma3 by applying he Chernoff bound.The density of T-S pairs at any point of the network scales asϕ′c=Θn1−ν/nδ1−ν/2logδ/2n=Θn1−ν1−δ/2log−δ/2n. We further partition each cell into squares with area 1/ϕ′c, i.e., S′e=Θn1−νδ/2−1logδ/2n. Hence, each active cell can schedule the number of concurrent noninterfering transmissions χ′ is
(28)χ′=ΘS1+c21/ϕ′c=Θn1−νlognn1−νδ/2−1logδ/2n=Θn1−ν2−δ/2log1−δ/2n.Hence, a noninterference scheduling scheme in the clustered random model can be designed as following steps. First, we divide the whole network into equal-sized cells with areaΘn1−νlogn, which makes the transmission connectivity possible. Then, we partition each cell into equal-sized squares with area Θn1−νδ/2−1logδ/2n, which guarantees the content transmission free from interference. Figure 2 shows the cell partition and the content request process in the clustered random model. Finally, a routing scheme similar with that in the cluster grid model can be utilized to achieve the content multihop transmission at a given slot.Lemma 11.
In the clustered random model, for any node requesting contentk, the probability P′k that an interest packet for content k is satisfied by one hop is minΘNkn1−νδ/2−1−1logδ/2n,1.Proof.
For an arbitrary square, the probability that there is at least one requested contentk is within the same square or the adjacent squares of the requester is 9Se′/n=9n1−νδ/2−1logδ/2n/n=9n1−νδ/2−1−1logδ/2n. Thus, we have
(29)P′k=1−1−9n1−νδ/2−1−1logδ/2nNk≤9Nkn1−νδ/2−1−1logδ/2n.
The inequality follows that1+xn≥1+nx for any x>−1. If 9Nkn1−νδ/2−1−1logδ/2n=o1, then P′k=ΘNkn1−νδ/2−1−1logδ/2n. Otherwise, P′k=1.Lemma 12.
In the clustered random model, for any mobile node requesting contentk, the average number of hops needed to transmit an interest packet along the path from the content requester to the closest content holder, denoted by E′Hk, is
(30)E′Hk=Θ1,Nk=Ωn1−1−νδ/2−1logδ/2n,Θn1/2−1−νδ/2−3/2Nklogδ/2n,Nk=on1−1−νδ/2−1logδ/2n&Nk=Ωn1/2−1−νδ/2−3/2logδ/2n,Θnν/2logn,Nk=on1/2−1−νδ/2−3/2logδ/2n.Proof.
According to Lemma6, we have
(31)E′Hk=1−1−P′khP′k.
Based on the value ofh and P′k, we consider three different conditions to further derive E′Hk.
(1)IfP′k=Θ1, then E′Hk=1
(2)IfP′k=o1 and hP′k=Ω1, 1−1−P′kh≥1−e−hP′k=Θ1. Hence, we obtain that E′Hk=Θ1/P′k=Θn1/2−1−νδ/2−3/2/Nklogδ/2n.
(3)IfP′k=o1 and hP′k=o1, applying the equivalent infinitesimal, we obtain that 1−1−P′kh≈1−e−hP′k≈ΘhP′k. Hence, we get that E′Hk=Θh=Θnν/2/logn.
This completes the proof.Theorem 13.
In the clustered random model, the delay and throughput of each mobile node, denoted byDn and λn, are given by w.h.p.
(32)Dn=Θ∑m=1MpkE′Hk,λn=Θn1−ν1−δ/2log−δ/2n∑m=1MpkE′Hk.Proof.
The proof of delay performance is similar to that of Theorem7, and we do not repeat it for simplicity.
We analyze the throughput performance of each node. Based on the cell partition of the network, we can obtain the total number of cells isΘnν/logn. Considering the scheduling scheme and routing scheme, the total number of bits that active square in a cell can transmit is W/1+c2n1−ν2−δ/2log1−δ/2n. Moreover, Lemma 12 indicates the average number of hops for content k is E′Hk. Since the request probability of the content k is pk, the average number of bits transmitted in the whole network can be calculated as nλn∑m=1MpkE′Hk. The rest proof is similar to the Theorem 7; we neglect it here for simplicity.Figure 2
The cell partition and the content request process in the clustered random model.From Theorem13, we can conclude that the difference of throughput and delay performance between the clustered random model and the clustered grid model is the logarithm factor and the average transmission hops.Corollary 14.
The throughput and delay tradeoff in the clustered random model is given by(33)λn=Θn1−ν1−δ/2Dnlogδ/2n,which differs from Corollary 8 by a factor log−δ/2n.


## 4. Optimal Cache Allocation

In this section, we analyze the optimal throughput and delay performance of the mobile content-centric network with respect to optimal cache allocation strategy. To achieve the optimal goal, we need to select appropriateNkk=1M based on the cache constraints for the clustered grid model and clustered random model, respectively.


### 4.1. Clustered Grid Model

From Corollary8, it indicates that minimizing the transmission delay is equivalent to maximizing the throughput performance. In order to achieve the minimum delay, we formulate the following optimization problem:
(34)minimizeNk∑k=1MpkEHksubjectto∑k=1MNk≤nK,1≤Nk≤n1−1−νδ/2−1,where EHk is given by
(35)EHk=Θ1,Nk=Ωn1−1−νδ/2−1,Θ1Nkn1−νδ/2−1−1,Nk=on1−1−νδ/2−1&Nk=Ωn1/2−1−νδ/2−3/2,Θnν/2,Nk=on1/2−1−νδ/2−3/2.The first constraint in (34) comes from the feasible cache allocation in (2), and the second constraint guarantees that for different types of contents, there is at most one copy content in each square. Note that the second derivatives of the objective function in (34) is always positive, which can be considered as a strictly convex optimization problem. Hence, we apply Lagrangian relaxation method to find the unique optimal solution.Based on the Zipf distribution law, it shows thatpk decreases as k increases and so is Nk. For the convenient and tractable analysis, we first define three sets K1, K2, and K3 according to the size of Nk, respectively. That is,(i)letK1=1,2,⋯,k1−1 be the set of contents such that Nk=n1−1−νδ/2−1(ii)letK2=k1,k1+1,⋯,k2−1 be the set of contents such that n1/2−1−νδ/2−3/2<Nk<n1−1−νδ/2−1(iii)letK3=k2,k2+1,⋯,M be the set of contents such that Nk=1Next, we take the Lagrangian multiplierλ∈R+ for the first constraint in (34) and combine with the second constraint; the necessary conditions for the minimal Dn are given as
(36)∂Dn∂Nk=−pkNk2n1−νδ/2−1−1≤−λ,∀k∈K1,=−λ,∀k∈K2,≥−λ,∀k∈K3.Whenk∈K2, we obtain
(37)Nk=pk1/2λ1/2n1−νδ/4−1/2−1/2.By adding upNk in (37) for k∈K2, we have
(38)λ1/2=n1/2−1−νδ/4−1/2∑k=k1k2−1pk1/2∑k=k1k2−1Nk.Combined (37) and (38), we obtain
(39)Nk=pk1/2∑k=k1k2−1pk1/2∑k=k1k2−1Nk=pk1/2∑k=k1k2−1pk1/2nK′,whereK′=K−k1−1/n1−νδ/2−1−M−k2+1/n. Therefore, we obtain the optimal number of content k, denoted by Nka° (In this paper, we apply symbol a° to denote the optimal value.), i.e.,
(40)Nka°=n1−1−νδ/2−1,∀k∈K1,pk1/2∑k=k1k2−1pk1/2nK′,∀k∈K2,1,∀k∈K3.By substituting (40) into (34), we achieve the minimum delay, denoted by Dna°.
(41)Dna°=Θ∑k=1k1−1pk+∑k=k1k2−1pk1/22n1−νδ/2−1K′+∑k=k2Mnν/2pk.Lemma 15.
In the clustered grid model, forn⟶∞, the values of k1 and k2 is given as follows
(42)k1=Θn1−νδ/2−1,α>2,Θn1−νδ/2−1logM,α=2,minM,Θn2/α1−νδ/2−1M2/α−1,0<α<2.k2=minM+1,Θnα−2/α1−νδ/2−1+2/α,α>2,M+1,α≤2.Proof.
By applying the conditionk1,k2−1∈K2, we derive that
(43)k1k2≃n2/α1−νδ/2−1−2/α.
Whenn⟶∞, we obtain that K′⟶K−k1−1/n1−νδ/2−1. Since k1∈K2, according to (40), we have Nk1<n1−1−νδ/2−1. Hence, it follows that
(44)n1−νδ/2−1K′<k1α/2Hα/2k2−1−Hα/2k1−1.
From the fact thatk1 is the smallest index in set K2 such that Nk1<n1−1−νδ/2−1, we decrease k1 by one, which will result in Nk1−1≥n1−1−νδ/2−1. Hence, we obtain that
(45)n1−νδ/2−1K′≥k1−1α/2Hα/2k2−1−Hα/2k1−2.
Combining (44) and (45), for k1>1, we obtain the approximation value of k1 scales as
(46)n1−νδ/2−1K′≃k1−1α/2Hα/2k2−1−Hα/2k1−1.
Similarly, we can derive the approximation value ofk2. We know that k2 is the smallest index in set K3 such that Nk2<n1/2−1−νδ/2−3/2, which result in
(47)n1/2+1−νδ/2−3/2K′<k2α/2Hα/2k2−Hα/2k1−1,
decreasingk2 by one, we have Nk2−1≥n1/2−1−νδ/2−3/2, which leads to
(48)n1/2+1−νδ/2−3/2K′≥k2−1α/2Hα/2k2−1−Hα/2k1−1.
Therefore, combining (47) and (48), we obtain the approximation value of k2 scales as
(49)n1/2+1−νδ/2−3/2K′≃k2−1α/2Hα/2k2−1−Hα/2k1−1.
The value ofk1 and k2 is determined by the different value of α. Therefore, we have following three conditions.
(1)Forα>2: We can simplify (46) as
(50)n1−νδ/2−1K−k1−1n1−νδ/2−1≃k1−1α/2−k1−11−α/21−α/2,which results in
(51)k1≃1+α−22n1−νδ/2−1K.
According to (43), k2 can be obtained by
(52)k2≃α−22nα−2/α1−νδ/2−1+2/αK.
(2)Forα=2: We assume k2≤M, and (49) can be simplified as
(53)n1/2+1−νδ/2−3/2K−k1−1n1−νδ/2−1≃k2−1logk2,which follows that
(54)k2−11+n1−νδ/2−3/2−1/2logk2≃n1/2+1−νδ/2−3/2logk2K,resulting in k2≃nK. This contradicts k2≤M=nγ,0<γ<1. Thus, we obtain k2=M+1.
Assumingk1>1, we can simplify (46) as
(55)n1−νδ/2−1K−k1−1n1−νδ/2−1≃k1−1logk2,by using (43), we obtain k1=Θn1−νδ/2−1/logM.
(3)For0<α<2: Assuming 1≤k1<k2≤M, we can simplify (49) as
(56)n1/2+1−νδ/2−3/2K−k1−1n1−νδ/2−1≃k2−1α/2k2−11−α/21−α/2,which results in
(57)k2≃n2−α/α1−ν1−δ/2+2/αK.
This contradictsk2≤M. Hence, we have k2=M+1.
By simplifying (46), we have
(58)n1−νδ/2−1K−k1−1n1−νδ/2−1≃k1−1α/2M1−α/2,resulting in k1=Θn2/α1−νδ/2−1/M2/α−1.Theorem 16.
In the clustered grid model, lettingω=1−νδ/2−1, according to the Zipf distribution, the optimal delay and throughput are given by w.h.p.
(59)Dna°=Θ1,α>2,Θlog2Mnω,α=2,ΘM2−αnω,1<α<2,ΘMnωlogM,α=1,ΘMnω,0<α<1,λna°=Θn−ω,α>2,Θ1log2M,α=2,Θ1M2−α,1<α<2,ΘlogMM,α=1,Θ1M,0<α<1.Proof.
We first prove the optimal delay based on the values ofk1 and k2. Then, the optimal throughput can be easily derived by the tradeoff relation given by (26). Substituting the value of pk into (41), we have
(60)Dna°=ΘHαk1−1HαM+Hα/2k2−1−Hα/2k1−12n1−νδ/2−1K′HαM+nν/2HαM−Hαk2−1HαM.
We divide the RHS of (60) into three terms, which are denoted by D1,D2, and D3, respectively. Then, we have following five conditions according to the values of α, k1, and k2.
(1)Forα>2: We have D1=Θ1, and D2=o1. If k2=M+1, we have D3=0, else if k2=Θnα−2/α1−νδ/2−1+2/α, we have D3=o1, when n⟶∞. Hence, we have Da°=Θ1.
(2)Forα=2: We have D1=Θ1, and D2=Θlog2M/n1−νδ/2−1. Since k2=M+1, we have we have D3=0. Hence, we have Da°=Θlog2M/n1−νδ/2−1.
(3)For1<α<2: We have D1=Θ1, and D2=ΘM2−α/n1−νδ/2−1. D3 is same with the condition (2), i.e., D3=0. Hence, we have Da°=ΘM2−α/n1−νδ/2−1.
(4)Forα=1: We have D1=Θ1, and D2=ΘM/n1−νδ/2−1logM. D3 is same with the condition (2), i.e., D3=0. Hence, we have Da°=ΘM/n1−νδ/2−1logM.
(5)For0<α<1: We have D1=Θ1, and D2=ΘM/n1−νδ/2−1. D3 is same with condition (2), i.e., D3=0. Hence, we have Da°=ΘM/n1−νδ/2−1.In Figure3(a), we have plotted the optimal delay performance of the clustered grid model for different values of α according to the Theorem 16. Similarly, the optimal throughput results for various values of α are plotted in Figure 3(b). We adopt ν=0.5 and γ=0.8 for both figures. We observe that the delay curves appear the ascending tendency while the throughput curves present descending tendency as the number of mobile nodes n increases. We further find that when the number of nodes is fixed, the optimal delay shows a decreasing trend while the optimal throughput increases as α increases. From the simulations, we can conclude that the most popular contents are mainly cached and transmitted by mobile nodes when α is large, which reduces the content transmission time and increases the number of simultaneous transmissions. That is, the advantage of caching is more obvious as α increases.Figure 3
Delay and throughput performance of the clustered grid model forν=0.5 and γ=0.8.
(a)
Delay(b)
Throughput


### 4.2. Clustered Random Model

In the clustered random model, we first formulate the optimal delay problem according to Theorem13, and then, we design the optimal cache allocation strategy to achieve the minimum delay. Combining Theorem 13 and the cache constraint, the objective function of minimum delay is given by
(61)minimizeNk∑k=1MpkE′Hksubjectto∑k=1MNk≤nK,1≤Nk≤n1−1−νδ/2−1log−δ/2n,where E′Hk is given by
(62)E′Hk=Θ1,Nk=Ωn1−1−νδ/2−1logδ/2n,Θn1−1−νδ/2−1Nklogδ/2n,Nk=on1−1−νδ/2−1logδ/2n&Nk=Ωn1/2−1−νδ/2−3/2logδ/2n,Θnν/2logn,Nk=on1/2−1−νδ/2−3/2logδ/2n.The optimization process is similar with the clustered grid model. Hence, we give a brief description.We first define three setsK′1, K′2, and K′3 according to the size of Nk, respectively. Let K′1=1,2,⋯,k1−1 be the set of contents such that Nk=n1−1−νδ/2−1/logδ/2n, let K′2=k1,k1+1,⋯,k2−1 be the set of contents such that Nk∈n1/2−1−νδ/2−3/2/logδ/2n,n1−1−νδ/2−1/logδ/2n. And let K′3=k2,k2+1,⋯,M be the set of contents such that Nk=1.Then, we take the Lagrangian multiplierλ∈R+ for the first constraint in (61) and combine with the second constraint; the necessary conditions for the minimal Dn are given as:
(63)∂Dn∂Nk=−pkn1−1−νδ/2−1Nk2logδ/2n≤−λ,∀k∈K′1,=−λ,∀k∈K′2,≥−λ,∀k∈K′3.Next, we apply the similar calculation method to obtain the values ofNka°. Hence, the minimum delay in the clustered random model is given by
(64)Dna°=Θ∑k=1k1−1pk+∑k=k1k2−1pk1/22n1−νδ/2−1K′logδ/2n+∑k=k2Mnν/2pklogn.Before obtaining the minimum delayDna°, we need to estimate the value of k1 and k2 by the following lemma.Lemma 17.
In the clustered random model, forn⟶∞, the values of k1 and k2 is given as follows
(65)k1=Θn1−νδ/2−1logδ/2n,α>2,Θn1−νδ/2−1logδ/2nlogM,α=2,minΘn1−νδ/2−1logδ/2n,ΘMn2/α1−νδ/2−1−2/αlog−δ/2,0<α<2,k2=minM+1,Θnα−2/α1−νδ/2−1+2/αlogδα−2/2αn,α>2,M+1,α=2,minM+1,Θn2−α/α1−ν1−δ/2+2/αlogδα−2/2αn,0<α<2.Proof.
The proof approach of this lemma is similar to that in Lemma15. We omit it for simplicity.Combining Lemma17 and the different values of α, the optimimal delay and throughput in the clustered random model are given as follows:Theorem 18.
In the clustered random model, lettingω=1−νδ/2−1, according to the Zipf distribution, the optimal delay and throughput are given by w.h.p.
(66)Dna°=Θ1,α>2,Θlog2Mnωlogδ/2n,α=2,minΘM2−αnωlogδ/2n,Θn−α2−3α+4/αω+4−2α/αlogδ2−α2+α/2αn,1<α<2,minΘMnωlogδ/2nlogM,Θn21−ν1−δ/2+2logMlogδn,α=1,minΘMnωlogδ/2n,Θn−α2−3α+4/αω+4−2α/αM1−αlogδ2−α2+α/2αn,0<α<1,λna°=Θn−ωlogδ/2n,α>2,Θ1log2M,α=2,maxΘ1M2−α,Θlogδ2−α2/2αnn−α2−4α+4/αω+4−2α/α,1<α<2,maxΘlogMM,ΘlogMlogδ/2nn1−ν1−δ/2+2,α=1,maxΘ1M,ΘM1−αlogδ2−α2/2αnn−α2−4α+4/αω+4−2α/α,0<α<1.Proof.
The proof of this theorem is similar to that in Theorem16. Hence, we neglect it for simplicity.In Figure4, we depict the optimal delay and throughput performance of the clustered random model for different values of α. We also adopt ν=0.5 and γ=0.8 for both figures. In particular, for α<2, we choose the smaller value of the two delay and we choose the larger value of the two throughput. In Figure 5, we plot the comparison results of the scaling performance of the different clustering models for α=1.5. We observe that the delay performance is better in the clustered random model than that in the clustered grid model while the throughput degrades in the clustered random model. This can be explained that the transmission range in the clustered random model is larger than that in the clustered grid model, which leads to the decreased transmission hops in the clustered random model accordingly. On the contrary, the larger transmission range covers more network areas, which results in the decrease concurrent transmissions.Figure 4
Delay and throughput performance of the clustered random model forν=0.5 and γ=0.8.
(a)
Delay(b)
ThroughputFigure 5
Comparisons of scaling performance for the clustered grid model and the clustered random model whenα=1.5.
(a)
Delay(b)
Throughput


## 4.1. Clustered Grid Model

From Corollary8, it indicates that minimizing the transmission delay is equivalent to maximizing the throughput performance. In order to achieve the minimum delay, we formulate the following optimization problem:
(34)minimizeNk∑k=1MpkEHksubjectto∑k=1MNk≤nK,1≤Nk≤n1−1−νδ/2−1,where EHk is given by
(35)EHk=Θ1,Nk=Ωn1−1−νδ/2−1,Θ1Nkn1−νδ/2−1−1,Nk=on1−1−νδ/2−1&Nk=Ωn1/2−1−νδ/2−3/2,Θnν/2,Nk=on1/2−1−νδ/2−3/2.The first constraint in (34) comes from the feasible cache allocation in (2), and the second constraint guarantees that for different types of contents, there is at most one copy content in each square. Note that the second derivatives of the objective function in (34) is always positive, which can be considered as a strictly convex optimization problem. Hence, we apply Lagrangian relaxation method to find the unique optimal solution.Based on the Zipf distribution law, it shows thatpk decreases as k increases and so is Nk. For the convenient and tractable analysis, we first define three sets K1, K2, and K3 according to the size of Nk, respectively. That is,(i)letK1=1,2,⋯,k1−1 be the set of contents such that Nk=n1−1−νδ/2−1(ii)letK2=k1,k1+1,⋯,k2−1 be the set of contents such that n1/2−1−νδ/2−3/2<Nk<n1−1−νδ/2−1(iii)letK3=k2,k2+1,⋯,M be the set of contents such that Nk=1Next, we take the Lagrangian multiplierλ∈R+ for the first constraint in (34) and combine with the second constraint; the necessary conditions for the minimal Dn are given as
(36)∂Dn∂Nk=−pkNk2n1−νδ/2−1−1≤−λ,∀k∈K1,=−λ,∀k∈K2,≥−λ,∀k∈K3.Whenk∈K2, we obtain
(37)Nk=pk1/2λ1/2n1−νδ/4−1/2−1/2.By adding upNk in (37) for k∈K2, we have
(38)λ1/2=n1/2−1−νδ/4−1/2∑k=k1k2−1pk1/2∑k=k1k2−1Nk.Combined (37) and (38), we obtain
(39)Nk=pk1/2∑k=k1k2−1pk1/2∑k=k1k2−1Nk=pk1/2∑k=k1k2−1pk1/2nK′,whereK′=K−k1−1/n1−νδ/2−1−M−k2+1/n. Therefore, we obtain the optimal number of content k, denoted by Nka° (In this paper, we apply symbol a° to denote the optimal value.), i.e.,
(40)Nka°=n1−1−νδ/2−1,∀k∈K1,pk1/2∑k=k1k2−1pk1/2nK′,∀k∈K2,1,∀k∈K3.By substituting (40) into (34), we achieve the minimum delay, denoted by Dna°.
(41)Dna°=Θ∑k=1k1−1pk+∑k=k1k2−1pk1/22n1−νδ/2−1K′+∑k=k2Mnν/2pk.Lemma 15.
In the clustered grid model, forn⟶∞, the values of k1 and k2 is given as follows
(42)k1=Θn1−νδ/2−1,α>2,Θn1−νδ/2−1logM,α=2,minM,Θn2/α1−νδ/2−1M2/α−1,0<α<2.k2=minM+1,Θnα−2/α1−νδ/2−1+2/α,α>2,M+1,α≤2.Proof.
By applying the conditionk1,k2−1∈K2, we derive that
(43)k1k2≃n2/α1−νδ/2−1−2/α.
Whenn⟶∞, we obtain that K′⟶K−k1−1/n1−νδ/2−1. Since k1∈K2, according to (40), we have Nk1<n1−1−νδ/2−1. Hence, it follows that
(44)n1−νδ/2−1K′<k1α/2Hα/2k2−1−Hα/2k1−1.
From the fact thatk1 is the smallest index in set K2 such that Nk1<n1−1−νδ/2−1, we decrease k1 by one, which will result in Nk1−1≥n1−1−νδ/2−1. Hence, we obtain that
(45)n1−νδ/2−1K′≥k1−1α/2Hα/2k2−1−Hα/2k1−2.
Combining (44) and (45), for k1>1, we obtain the approximation value of k1 scales as
(46)n1−νδ/2−1K′≃k1−1α/2Hα/2k2−1−Hα/2k1−1.
Similarly, we can derive the approximation value ofk2. We know that k2 is the smallest index in set K3 such that Nk2<n1/2−1−νδ/2−3/2, which result in
(47)n1/2+1−νδ/2−3/2K′<k2α/2Hα/2k2−Hα/2k1−1,
decreasingk2 by one, we have Nk2−1≥n1/2−1−νδ/2−3/2, which leads to
(48)n1/2+1−νδ/2−3/2K′≥k2−1α/2Hα/2k2−1−Hα/2k1−1.
Therefore, combining (47) and (48), we obtain the approximation value of k2 scales as
(49)n1/2+1−νδ/2−3/2K′≃k2−1α/2Hα/2k2−1−Hα/2k1−1.
The value ofk1 and k2 is determined by the different value of α. Therefore, we have following three conditions.
(1)Forα>2: We can simplify (46) as
(50)n1−νδ/2−1K−k1−1n1−νδ/2−1≃k1−1α/2−k1−11−α/21−α/2,which results in
(51)k1≃1+α−22n1−νδ/2−1K.
According to (43), k2 can be obtained by
(52)k2≃α−22nα−2/α1−νδ/2−1+2/αK.
(2)Forα=2: We assume k2≤M, and (49) can be simplified as
(53)n1/2+1−νδ/2−3/2K−k1−1n1−νδ/2−1≃k2−1logk2,which follows that
(54)k2−11+n1−νδ/2−3/2−1/2logk2≃n1/2+1−νδ/2−3/2logk2K,resulting in k2≃nK. This contradicts k2≤M=nγ,0<γ<1. Thus, we obtain k2=M+1.
Assumingk1>1, we can simplify (46) as
(55)n1−νδ/2−1K−k1−1n1−νδ/2−1≃k1−1logk2,by using (43), we obtain k1=Θn1−νδ/2−1/logM.
(3)For0<α<2: Assuming 1≤k1<k2≤M, we can simplify (49) as
(56)n1/2+1−νδ/2−3/2K−k1−1n1−νδ/2−1≃k2−1α/2k2−11−α/21−α/2,which results in
(57)k2≃n2−α/α1−ν1−δ/2+2/αK.
This contradictsk2≤M. Hence, we have k2=M+1.
By simplifying (46), we have
(58)n1−νδ/2−1K−k1−1n1−νδ/2−1≃k1−1α/2M1−α/2,resulting in k1=Θn2/α1−νδ/2−1/M2/α−1.Theorem 16.
In the clustered grid model, lettingω=1−νδ/2−1, according to the Zipf distribution, the optimal delay and throughput are given by w.h.p.
(59)Dna°=Θ1,α>2,Θlog2Mnω,α=2,ΘM2−αnω,1<α<2,ΘMnωlogM,α=1,ΘMnω,0<α<1,λna°=Θn−ω,α>2,Θ1log2M,α=2,Θ1M2−α,1<α<2,ΘlogMM,α=1,Θ1M,0<α<1.Proof.
We first prove the optimal delay based on the values ofk1 and k2. Then, the optimal throughput can be easily derived by the tradeoff relation given by (26). Substituting the value of pk into (41), we have
(60)Dna°=ΘHαk1−1HαM+Hα/2k2−1−Hα/2k1−12n1−νδ/2−1K′HαM+nν/2HαM−Hαk2−1HαM.
We divide the RHS of (60) into three terms, which are denoted by D1,D2, and D3, respectively. Then, we have following five conditions according to the values of α, k1, and k2.
(1)Forα>2: We have D1=Θ1, and D2=o1. If k2=M+1, we have D3=0, else if k2=Θnα−2/α1−νδ/2−1+2/α, we have D3=o1, when n⟶∞. Hence, we have Da°=Θ1.
(2)Forα=2: We have D1=Θ1, and D2=Θlog2M/n1−νδ/2−1. Since k2=M+1, we have we have D3=0. Hence, we have Da°=Θlog2M/n1−νδ/2−1.
(3)For1<α<2: We have D1=Θ1, and D2=ΘM2−α/n1−νδ/2−1. D3 is same with the condition (2), i.e., D3=0. Hence, we have Da°=ΘM2−α/n1−νδ/2−1.
(4)Forα=1: We have D1=Θ1, and D2=ΘM/n1−νδ/2−1logM. D3 is same with the condition (2), i.e., D3=0. Hence, we have Da°=ΘM/n1−νδ/2−1logM.
(5)For0<α<1: We have D1=Θ1, and D2=ΘM/n1−νδ/2−1. D3 is same with condition (2), i.e., D3=0. Hence, we have Da°=ΘM/n1−νδ/2−1.In Figure3(a), we have plotted the optimal delay performance of the clustered grid model for different values of α according to the Theorem 16. Similarly, the optimal throughput results for various values of α are plotted in Figure 3(b). We adopt ν=0.5 and γ=0.8 for both figures. We observe that the delay curves appear the ascending tendency while the throughput curves present descending tendency as the number of mobile nodes n increases. We further find that when the number of nodes is fixed, the optimal delay shows a decreasing trend while the optimal throughput increases as α increases. From the simulations, we can conclude that the most popular contents are mainly cached and transmitted by mobile nodes when α is large, which reduces the content transmission time and increases the number of simultaneous transmissions. That is, the advantage of caching is more obvious as α increases.Figure 3
Delay and throughput performance of the clustered grid model forν=0.5 and γ=0.8.
(a)
Delay(b)
Throughput


## 4.2. Clustered Random Model

In the clustered random model, we first formulate the optimal delay problem according to Theorem13, and then, we design the optimal cache allocation strategy to achieve the minimum delay. Combining Theorem 13 and the cache constraint, the objective function of minimum delay is given by
(61)minimizeNk∑k=1MpkE′Hksubjectto∑k=1MNk≤nK,1≤Nk≤n1−1−νδ/2−1log−δ/2n,where E′Hk is given by
(62)E′Hk=Θ1,Nk=Ωn1−1−νδ/2−1logδ/2n,Θn1−1−νδ/2−1Nklogδ/2n,Nk=on1−1−νδ/2−1logδ/2n&Nk=Ωn1/2−1−νδ/2−3/2logδ/2n,Θnν/2logn,Nk=on1/2−1−νδ/2−3/2logδ/2n.The optimization process is similar with the clustered grid model. Hence, we give a brief description.We first define three setsK′1, K′2, and K′3 according to the size of Nk, respectively. Let K′1=1,2,⋯,k1−1 be the set of contents such that Nk=n1−1−νδ/2−1/logδ/2n, let K′2=k1,k1+1,⋯,k2−1 be the set of contents such that Nk∈n1/2−1−νδ/2−3/2/logδ/2n,n1−1−νδ/2−1/logδ/2n. And let K′3=k2,k2+1,⋯,M be the set of contents such that Nk=1.Then, we take the Lagrangian multiplierλ∈R+ for the first constraint in (61) and combine with the second constraint; the necessary conditions for the minimal Dn are given as:
(63)∂Dn∂Nk=−pkn1−1−νδ/2−1Nk2logδ/2n≤−λ,∀k∈K′1,=−λ,∀k∈K′2,≥−λ,∀k∈K′3.Next, we apply the similar calculation method to obtain the values ofNka°. Hence, the minimum delay in the clustered random model is given by
(64)Dna°=Θ∑k=1k1−1pk+∑k=k1k2−1pk1/22n1−νδ/2−1K′logδ/2n+∑k=k2Mnν/2pklogn.Before obtaining the minimum delayDna°, we need to estimate the value of k1 and k2 by the following lemma.Lemma 17.
In the clustered random model, forn⟶∞, the values of k1 and k2 is given as follows
(65)k1=Θn1−νδ/2−1logδ/2n,α>2,Θn1−νδ/2−1logδ/2nlogM,α=2,minΘn1−νδ/2−1logδ/2n,ΘMn2/α1−νδ/2−1−2/αlog−δ/2,0<α<2,k2=minM+1,Θnα−2/α1−νδ/2−1+2/αlogδα−2/2αn,α>2,M+1,α=2,minM+1,Θn2−α/α1−ν1−δ/2+2/αlogδα−2/2αn,0<α<2.Proof.
The proof approach of this lemma is similar to that in Lemma15. We omit it for simplicity.Combining Lemma17 and the different values of α, the optimimal delay and throughput in the clustered random model are given as follows:Theorem 18.
In the clustered random model, lettingω=1−νδ/2−1, according to the Zipf distribution, the optimal delay and throughput are given by w.h.p.
(66)Dna°=Θ1,α>2,Θlog2Mnωlogδ/2n,α=2,minΘM2−αnωlogδ/2n,Θn−α2−3α+4/αω+4−2α/αlogδ2−α2+α/2αn,1<α<2,minΘMnωlogδ/2nlogM,Θn21−ν1−δ/2+2logMlogδn,α=1,minΘMnωlogδ/2n,Θn−α2−3α+4/αω+4−2α/αM1−αlogδ2−α2+α/2αn,0<α<1,λna°=Θn−ωlogδ/2n,α>2,Θ1log2M,α=2,maxΘ1M2−α,Θlogδ2−α2/2αnn−α2−4α+4/αω+4−2α/α,1<α<2,maxΘlogMM,ΘlogMlogδ/2nn1−ν1−δ/2+2,α=1,maxΘ1M,ΘM1−αlogδ2−α2/2αnn−α2−4α+4/αω+4−2α/α,0<α<1.Proof.
The proof of this theorem is similar to that in Theorem16. Hence, we neglect it for simplicity.In Figure4, we depict the optimal delay and throughput performance of the clustered random model for different values of α. We also adopt ν=0.5 and γ=0.8 for both figures. In particular, for α<2, we choose the smaller value of the two delay and we choose the larger value of the two throughput. In Figure 5, we plot the comparison results of the scaling performance of the different clustering models for α=1.5. We observe that the delay performance is better in the clustered random model than that in the clustered grid model while the throughput degrades in the clustered random model. This can be explained that the transmission range in the clustered random model is larger than that in the clustered grid model, which leads to the decreased transmission hops in the clustered random model accordingly. On the contrary, the larger transmission range covers more network areas, which results in the decrease concurrent transmissions.Figure 4
Delay and throughput performance of the clustered random model forν=0.5 and γ=0.8.
(a)
Delay(b)
ThroughputFigure 5
Comparisons of scaling performance for the clustered grid model and the clustered random model whenα=1.5.
(a)
Delay(b)
Throughput


## 5. Conclusions and Future Works

In this paper, we analyzed the throughput and delay performance of mobile content-centric networks, where the node spatial distribution of nodes is not uniform. We adopted a cell-partition TDMA scheduling scheme and proposed a distributed multihop routing scheme to achieve the throughput-delay tradeoff in the clustered grid model and clustered random model, respectively. Moreover, according to the content popularity distribution, we applied Lagrangian relaxation method to optimize the cache allocation in two kinds of clustered models. Finally, we obtained the optimal throughput and delay in the mobile content-centric networks. Our theoretical results were validated by the numerical simulations.There are several problems left for future research, for example, the scaling laws and the caching optimization for mobile content-centric networks with infrastructures support. In addition, the multicast capacity of nonuniform mobile content-centric networks has not been studied. Finally, it is meaningful to optimize cache allocation strategy when the distribution of contents is unknown.



---

*Source: 8880015-2021-01-09.xml*