W.Wang et aL/Computer Communications 83(2016)45-55 communication,it is mainly used for control message exchange Section 4.2.Relays are notified through the cellular network and content delivery traffic is offloaded through D2D communi- when they are selected.Each relay then reserves relay storage cation.D2D communication leverages opportunistic short-range segments for this downloading session and starts searching for links formed between nearby mobiles to reduce content delivery the given content.As the notification is sent through the cellu- cost.The links used for D2D communication can be WiFi Direct. lar network,the delay of the notification process can be ignored Bluetooth,LTE/LTE-A,etc.Compared to directly communicating compared to the delay of D2D offloading. with the base station,these short-range links are usually faster, 2.Relays try to replicate the requested content in the reserved re- consumes less energy and free of mobile data charges.For exam- lay storage when contact a seed.The content is replicated to ple,LTE only provides 300 Mbps shared transmission rate,while the relay via short range D2D links. the 802.11ac protocol used by WiFi provides transmission rate 3.When the subscriber contacts a seed or a relay that has already higher than 500 Mbps [25.Real-world measurements also show replicated the content,the subscriber can download the content that WiFi is 14.5 times and 23 times more energy efficient than through D2D links.We call this as an offloading success. 3G and LTE,respectively [26].However,these D2D links have short 4.If the subscriber becomes impatient before reaching any seed communication ranges.For example,WiFi only has communication or relay with the requested content,he/she will directly down- range up to 100 m.Therefore,short-range links only exist when load the content through the cellular network.We call this as mobiles move close to each other,and subscribers may become an offloading failure. impatient before they can find a D2D transmission opportunity[5] 5.Relays receive notifications when the offloading process suc- One important issue for D2D systems is to encourage nodes to ceeds or fails.The storage reserved for the downloading session act as helpers.Helpers contribute their storage as content caches is then released. and allow other nodes to download content from them through D2D links.Therefore,users should have motivations to contribute The advantage of the above on-demand relaying scheme is that storage and battery power of their devices.Helpers may come from it only uses the cellular network to deliver a small amount of con- two sources:mobile devices provided by users and special devices trol information,while the content replications are delivered by deployed by the network operator.The incentive for mobile helpers D2D links between seeds and relays,so the overall relaying cost may come from discounts or other benefits provided by the net- is negligible.Mobile helpers acting as relays also do not consume work operator.Such mechanisms have been well studied in exist- significantly more energy or bandwidth than those acting as seeds, ing work,e.g.[27].In D2D system.it is also possible to utilize because the only extra cost for relays is to receive the control social connections to provide incentives for helpers.For example, message.Note that our relaying scheme is different from relaying users may ask their friends to help them in content downloading. schemes in traditional DTN networks [8.10-12].which mainly fo- Note that incentive schemes developed for traditional D2D offload- cus on point-to-point message delivery rather than content distri- ing systems can be directly applied to our system,as our system bution. do not incur higher storage and energy cost to helpers than tradi tional offloading schemes. 3.2.System model Network operators are also willing to deploy helpers to offload the traffic of cellular systems so that they do not need to contin- We assume that content in the system is divided into segments uously deploy more base stations to handle the increasing traf- with lengths of M.Such a segmentation mechanism is commonly fic.These helpers can be mobile nodes mounted on buses [28 used in streaming and content delivery systems [29].Typical val- or fixed caching points on Femtocells [21].As D2D helpers do ues for segment lengths are 1 to 2 M Bytes.Segments of the same not need high-throughput backhaul,deployment of D2D helpers is file are treated as if they are independent pieces of content,so we much easier than deploying small base stations,e.g,microcells or use the term "content"instead of segments in the rest of this pa- picocells.The advantage of these specialized helpers is that they per.Therefore,it is possible that the user downloads some of the can provide heterogeneous mobility patterns,and it is easier for segments of a given file using the offloading system,while other network operators to optimize the content distribution process on segments of the same file are directly downloaded from the cellu- specialized devices lar network. Different types of helpers can coexist in D2D offloading sys- We assume that there are N pieces of content in the system and tems.Helpers with different mobility patterns,storage sizes or de- that each content i has a mean request rate of Ri.We further as- livery strategies may lead to different performance tradeoffs.In sume that the contact duration between nodes is long enough so this paper,we mainly focus on two types of helpers:Firstly,seeds that at least one segment can be downloaded during the contact are stable content caches that serve for all requests to a given period.As short-range links normally have high transmission rate content.The system allocates a certain number of seeds for each e.g.WiFi has transmission rates from 54-500 Mbps and Bluetooth piece of content to ensure the availability of content.Secondly,re- has rate of 24 Mbps,it takes less than one second to transmit a lays are temporary storage allocated for a specific request.They single segment.Thus,the duration for content transmission is neg- are selected according to the information of the given request to ligible compared to the durations of the contacts,which have av- enhance storage utility.The content cached in relays may dynami- erage length of 370 s [30].Systems with limited contact durations cally change due to arrival or completion of relaying requests.Note can be further optimized using schemes described in [31. that a single node may act as different roles at the same time:it Contacts between nodes are assumed to be independent non- may have part of its storage used as seeds and part of its storage lattice renewal processes.Our model covers most of the existing used as relays. mobility models,which assume that the contact patterns are Pois- Relaying procedure: son processes or have power-law inter-contact times [5,321.In the The content downloading process for a system with both seeds later part of this paper,we may further limit the contact processes and relays is described as follows: to be only Poisson processes,which have been verified by real- world traces [33]as well as theoretical analysis [32].To verify our 1.A subscriber sends a content request to the cellular operator. model in real systems,we also use real-world traces in our exper- Either the operator or the subscriber can select some relays iments,see Section 6.2.In real-world,contact processes between among all available relays to help the subscriber downloading different types of nodes can have different inter-contact time dis- the content.Detailed relay selection procedure is described in tributions.For example,the contact process between relays andW. Wang et al. / Computer Communications 83 (2016) 45–55 47 communication, it is mainly used for control message exchange and content delivery traffic is offloaded through D2D communi￾cation. D2D communication leverages opportunistic short-range links formed between nearby mobiles to reduce content delivery cost. The links used for D2D communication can be WiFi Direct, Bluetooth, LTE/LTE-A, etc. Compared to directly communicating with the base station, these short-range links are usually faster, consumes less energy and free of mobile data charges. For exam￾ple, LTE only provides 300 Mbps shared transmission rate, while the 802.11ac protocol used by WiFi provides transmission rate higher than 500 Mbps [25]. Real-world measurements also show that WiFi is 14.5 times and 23 times more energy efficient than 3G and LTE, respectively [26]. However, these D2D links have short communication ranges. For example, WiFi only has communication range up to 100 m. Therefore, short-range links only exist when mobiles move close to each other, and subscribers may become impatient before they can find a D2D transmission opportunity [5]. One important issue for D2D systems is to encourage nodes to act as helpers. Helpers contribute their storage as content caches and allow other nodes to download content from them through D2D links. Therefore, users should have motivations to contribute storage and battery power of their devices. Helpers may come from two sources: mobile devices provided by users and special devices deployed by the network operator. The incentive for mobile helpers may come from discounts or other benefits provided by the net￾work operator. Such mechanisms have been well studied in exist￾ing work, e.g., [27]. In D2D system, it is also possible to utilize social connections to provide incentives for helpers. For example, users may ask their friends to help them in content downloading. Note that incentive schemes developed for traditional D2D offload￾ing systems can be directly applied to our system, as our system do not incur higher storage and energy cost to helpers than tradi￾tional offloading schemes. Network operators are also willing to deploy helpers to offload the traffic of cellular systems so that they do not need to contin￾uously deploy more base stations to handle the increasing traf- fic. These helpers can be mobile nodes mounted on buses [28] or fixed caching points on Femtocells [21]. As D2D helpers do not need high-throughput backhaul, deployment of D2D helpers is much easier than deploying small base stations, e.g., microcells or picocells. The advantage of these specialized helpers is that they can provide heterogeneous mobility patterns, and it is easier for network operators to optimize the content distribution process on specialized devices. Different types of helpers can coexist in D2D offloading sys￾tems. Helpers with different mobility patterns, storage sizes or de￾livery strategies may lead to different performance tradeoffs. In this paper, we mainly focus on two types of helpers: Firstly, seeds are stable content caches that serve for all requests to a given content. The system allocates a certain number of seeds for each piece of content to ensure the availability of content. Secondly, re￾lays are temporary storage allocated for a specific request. They are selected according to the information of the given request to enhance storage utility. The content cached in relays may dynami￾cally change due to arrival or completion of relaying requests. Note that a single node may act as different roles at the same time: it may have part of its storage used as seeds and part of its storage used as relays. Relaying procedure: The content downloading process for a system with both seeds and relays is described as follows: 1. A subscriber sends a content request to the cellular operator. Either the operator or the subscriber can select some relays among all available relays to help the subscriber downloading the content. Detailed relay selection procedure is described in Section 4.2. Relays are notified through the cellular network when they are selected. Each relay then reserves relay storage segments for this downloading session and starts searching for the given content. As the notification is sent through the cellu￾lar network, the delay of the notification process can be ignored compared to the delay of D2D offloading. 2. Relays try to replicate the requested content in the reserved re￾lay storage when contact a seed. The content is replicated to the relay via short range D2D links. 3. When the subscriber contacts a seed or a relay that has already replicated the content, the subscriber can download the content through D2D links. We call this as an offloading success. 4. If the subscriber becomes impatient before reaching any seed or relay with the requested content, he/she will directly down￾load the content through the cellular network. We call this as an offloading failure. 5. Relays receive notifications when the offloading process suc￾ceeds or fails. The storage reserved for the downloading session is then released. The advantage of the above on-demand relaying scheme is that it only uses the cellular network to deliver a small amount of con￾trol information, while the content replications are delivered by D2D links between seeds and relays, so the overall relaying cost is negligible. Mobile helpers acting as relays also do not consume significantly more energy or bandwidth than those acting as seeds, because the only extra cost for relays is to receive the control message. Note that our relaying scheme is different from relaying schemes in traditional DTN networks [8,10–12], which mainly fo￾cus on point-to-point message delivery rather than content distri￾bution. 3.2. System model We assume that content in the system is divided into segments with lengths of M. Such a segmentation mechanism is commonly used in streaming and content delivery systems [29]. Typical val￾ues for segment lengths are 1 to 2 M Bytes. Segments of the same file are treated as if they are independent pieces of content, so we use the term “content” instead of segments in the rest of this pa￾per. Therefore, it is possible that the user downloads some of the segments of a given file using the offloading system, while other segments of the same file are directly downloaded from the cellu￾lar network. We assume that there are N pieces of content in the system and that each content i has a mean request rate of Ri. We further as￾sume that the contact duration between nodes is long enough so that at least one segment can be downloaded during the contact period. As short-range links normally have high transmission rate, e.g., WiFi has transmission rates from 54–500 Mbps and Bluetooth has rate of 24 Mbps, it takes less than one second to transmit a single segment. Thus, the duration for content transmission is neg￾ligible compared to the durations of the contacts, which have av￾erage length of 370 s [30]. Systems with limited contact durations can be further optimized using schemes described in [31]. Contacts between nodes are assumed to be independent non￾lattice renewal processes. Our model covers most of the existing mobility models, which assume that the contact patterns are Pois￾son processes or have power-law inter-contact times [5,32]. In the later part of this paper, we may further limit the contact processes to be only Poisson processes, which have been verified by real￾world traces [33] as well as theoretical analysis [32]. To verify our model in real systems, we also use real-world traces in our exper￾iments, see Section 6.2. In real-world, contact processes between different types of nodes can have different inter-contact time dis￾tributions. For example, the contact process between relays and