W.Wang et aL /Computer Communications 83 (2016)45-55 subscribers may be different from that between seeds and sub- and relays can deliver contents to the subscriber via short range scribers. links.The efficiency of the seed only depends on the contact pro- We assume that there are n helpers willing to contribute their cess between subscribers and seeds.However,the efficiency of the storage.We assume that the storage contributed by each helper is relay is dependent on the number of seeds,in addition to the con- able to hold I pieces of content.This assumption can be relaxed tact process between subscribers and relays.This is because re- and will be discussed in Section 5.The storage in helpers can be lays need to first download the content from seeds before they can used as either seeds or relays.We use nsi and n.i to represent the transmit it to the subscribers. number of seeds and relays used by offloading sessions for content We first consider the offloading efficiency of a single relay node. When the contact pattern and number of seeds are known,the We define the offloading failure probability as the probability efficiency of the relays can be calculated as follows: that the subscriber cannot discover the content through D2D com- munication within a given time period of T.To evaluate the effi- Theorem 1.Suppose there are ns.i seeds for content i,and the inter- ciency of a single helper,we define the offloading efficiency Es of contact time between seeds and relays follows a Cumulative Distribu- a single seed as follows: tion Function (CDF)of Y(t)with a mean of uy.If the inter-contact time between relay and subscriber follows CDF of X(t)with a mean Es =-In Ps. (1) of ux,then the offloading efficiency of the relay node for content i is where Ps is the probability that the subscriber cannot receive the given by: content from that particular seed.A higher offloading efficiency means that the seed is more efficient in transmitting the content E,=-ln()- (T-t)"dx( (4) through the D2D link.Similarly.we define the efficiency of a relay Er as-In P.where P,is the probability that the subscriber cannot where: receive the content from the given relay.Table 1 summarizes the symbols used in this paper. (t)=1 As the offloading failure probability depends on the size of the (-X()dr/u (5) cache allocated for the given content,it is a function of the number of relays and seeds for content i.We denote the offloading failure probability for content i as Fnn).Therefore,the total amount Y)=1-(1-Y(t)dr1y (6) of traffic offloaded by D2D communication can be written as: Proof.There are two cases that the given relay will fail to deliver N D=>MRi(1-F(ns.i.nr.i)). (2) the content. (i).The relay never meets the subscriber within time T.For non-lattice renewal processes,the CDF of the time between a For example,suppose that the contact process between a seed randomly picked time point t and the next contact is given by and a subscriber is a Poisson process with a rate of As.Then,the (1-X())dr/ux [34].Therefore,the probability that the relay probability that the seed cannot meet the subscriber during the never meets the subscriber within time T is given by time period of T is given by e-T.Consequently.the offloading ef- ficiency of a single seed is Es =AsT. (T)=1- (1-X(t)dt/μx: (7) Offloading fails when all the ns.i seeds and n.i relays are un- 0 able to deliver the content to the subscriber.When contacts be- (ii).The relay meets the subscriber within time T,but it never tween different pairs of nodes are independent,the event that the meets any seed before the last contact with the subscriber.Sup- given seed or relay can successfully deliver the content is also in- pose that last contact between the relay and the subscriber hap- dependent of other relays/seeds.Therefore,we can multiply the pens in(T-t.T-t+dt),with 0<t<T.The CDF of the time du- failure probability of a single seed/relay to get: ration from last contact to the point of request expiration (at time F(ns.i.nr.)=e-nse-nE =p prd (3) T)is the age distribution of the renewal process.Therefore,the probability that the last contact happens in(T-t.T-t+dt)(with Eq.(3)allows us to directly compare the efficiency of relays and seeds.When there are more than two types of helpers,the offload- age of t at the point of request expire)can be given by-dX(t).Be- cause the probability that the relay does not meet any of the ns.i ing failure probability can be written in a similar way.For details, please refer to Section 5.3. seeds before T-t is given by ((T-t))"s.the probability for the Existing studies that use the static caching model are special second failure case is given by: cases of our system model in Eg.(3).When there are only seeds, we have F(ns..)=P.For a Poisson process with a rate of s. (Y(T-t))""dx(t). (8) we have F(ns..0)=e-mT,which is the same as the results of static caching systems 5.6]. Taking the sum of the failure probability of case (i)and (ii) and translating it into offloading efficiency,we get the result of 4.On-demand relaying in D2D systems Theorem1.▣ Similarly.the offloading efficiency of seeds can be written as: 4.1.Offloading efficiency for helpers Es=-InP=-InY(T) (9) We study the offloading efficiency of our relaying scheme in From Theorem 1,we can see that the ratio of Er/Es is bounded this section.In the relaying scheme,the identity of the content above by the number of seeds: that the subscriber is searching for is delivered to relays through the cellular network.Therefore,only two contacts are needed in Corollary 1.The efficiency ratio of Er/Es is bounded above by ns.i our relaying scheme.In contrast,traditional relaying scheme re- quires three contacts with an extra contact between the subscriber Proof.Because both X(t)and Y(t)are Complementary Cumula- and the relay to deliver the identity of the content.Both the seed tive Distribution Function (CCDF)for age distribution of a renewal48 W. Wang et al. / Computer Communications 83 (2016) 45–55 subscribers may be different from that between seeds and sub￾scribers. We assume that there are n helpers willing to contribute their storage. We assume that the storage contributed by each helper is able to hold I pieces of content. This assumption can be relaxed and will be discussed in Section 5. The storage in helpers can be used as either seeds or relays. We use ns, i and nr, i to represent the number of seeds and relays used by offloading sessions for content i. We define the offloading failure probability as the probability that the subscriber cannot discover the content through D2D com￾munication within a given time period of T. To evaluate the effi- ciency of a single helper, we define the offloading efficiency Es of a single seed as follows: Es = − ln Ps, (1) where Ps is the probability that the subscriber cannot receive the content from that particular seed. A higher offloading efficiency means that the seed is more efficient in transmitting the content through the D2D link. Similarly, we define the efficiency of a relay Er as − ln Pr, where Pr is the probability that the subscriber cannot receive the content from the given relay. Table 1 summarizes the symbols used in this paper. As the offloading failure probability depends on the size of the cache allocated for the given content, it is a function of the number of relays and seeds for content i. We denote the offloading failure probability for content i as F(ns, i, nr, i). Therefore, the total amount of traffic offloaded by D2D communication can be written as: D = N i=1 MRi(1 − F (ns,i, nr,i)). (2) For example, suppose that the contact process between a seed and a subscriber is a Poisson process with a rate of λs. Then, the probability that the seed cannot meet the subscriber during the time period of T is given by e−λsT . Consequently, the offloading ef- ficiency of a single seed is Es = λsT. Offloading fails when all the ns, i seeds and nr, i relays are un￾able to deliver the content to the subscriber. When contacts be￾tween different pairs of nodes are independent, the event that the given seed or relay can successfully deliver the content is also in￾dependent of other relays/seeds. Therefore, we can multiply the failure probability of a single seed/relay to get: F (ns,i, nr,i) = e−ns,iEse−nr,iEr = Pns,i s Pnr,i r . (3) Eq. (3) allows us to directly compare the efficiency of relays and seeds. When there are more than two types of helpers, the offload￾ing failure probability can be written in a similar way. For details, please refer to Section 5.3. Existing studies that use the static caching model are special cases of our system model in Eq. (3). When there are only seeds, we have F (ns,i, 0) = P ns,i s . For a Poisson process with a rate of λs, we have F (ns,i, 0) = e−ns,iλsT , which is the same as the results of static caching systems [5,6]. 4. On-demand relaying in D2D systems 4.1. Offloading efficiency for helpers We study the offloading efficiency of our relaying scheme in this section. In the relaying scheme, the identity of the content that the subscriber is searching for is delivered to relays through the cellular network. Therefore, only two contacts are needed in our relaying scheme. In contrast, traditional relaying scheme re￾quires three contacts with an extra contact between the subscriber and the relay to deliver the identity of the content. Both the seed and relays can deliver contents to the subscriber via short range links. The efficiency of the seed only depends on the contact pro￾cess between subscribers and seeds. However, the efficiency of the relay is dependent on the number of seeds, in addition to the con￾tact process between subscribers and relays. This is because re￾lays need to first download the content from seeds before they can transmit it to the subscribers. We first consider the offloading efficiency of a single relay node. When the contact pattern and number of seeds are known, the efficiency of the relays can be calculated as follows: Theorem 1. Suppose there are ns, i seeds for content i, and the inter￾contact time between seeds and relays follows a Cumulative Distribu￾tion Function (CDF) of Y(t) with a mean of μy. If the inter-contact time between relay and subscriber follows CDF of X(t) with a mean of μx, then the offloading efficiency of the relay node for content i is given by: Er = − ln Xˆ(T ) −  T 0  Yˆ(T − t) ns,i dXˆ(t)  , (4) where: Xˆ(t) = 1 −  t 0 (1 − X(τ ))dτ /μx (5) Yˆ(t) = 1 −  t 0 (1 − Y (τ ))dτ /μy. (6) Proof. There are two cases that the given relay will fail to deliver the content. (i). The relay never meets the subscriber within time T. For non-lattice renewal processes, the CDF of the time between a randomly picked time point t and the next contact is given by  t 0 (1 − X(τ ))dτ /μx [34]. Therefore, the probability that the relay never meets the subscriber within time T is given by Xˆ(T ) = 1 −  T 0 (1 − X(τ ))dτ /μx. (7) (ii). The relay meets the subscriber within time T, but it never meets any seed before the last contact with the subscriber. Sup￾pose that last contact between the relay and the subscriber hap￾pens in (T − t, T − t + dt), with 0 ≤ t ≤ T. The CDF of the time du￾ration from last contact to the point of request expiration (at time T) is the age distribution of the renewal process. Therefore, the probability that the last contact happens in (T − t, T − t + dt) (with age of t at the point of request expire) can be given by −dXˆ(t). Be￾cause the probability that the relay does not meet any of the ns, i seeds before T − t is given by  Yˆ(T − t) ns,i , the probability for the second failure case is given by: −  T 0  Yˆ(T − t) ns,i dXˆ(t). (8) Taking the sum of the failure probability of case (i) and (ii) and translating it into offloading efficiency, we get the result of Theorem 1. Similarly, the offloading efficiency of seeds can be written as: Es = − ln Ps = − lnYˆ(T ). (9) From Theorem 1, we can see that the ratio of Er/Es is bounded above by the number of seeds: Corollary 1. The efficiency ratio of Er/Es is bounded above by ns, i. Proof. Because both Xˆ(t) and Yˆ(t) are Complementary Cumula￾tive Distribution Function (CCDF) for age distribution of a renewal