6 W.Wang et aL /Computer Communications 83 (2016)45-55 there is a relay deployed at the subway station,this relay can ac- tively search for the content requested by the subscriber and make sure the content can be delivered when the user passes by.Our analysis shows that using one relay with regular contact patterns can be as effective as increasing the number of seeds by a constant D2D ratio. communication An important issue in a relaying system is to allocate storage for content.Because users can choose to statically cache the content or RelaySeed dynamically download new content for their friends,mobile relays Cellular and seeds are actually different roles played by the same group coverace of helpers.In this way,relays and seeds need to share the lim- ited storage resources in mobile helpers and storage allocation be- comes critical to the performance of the offloading system.When Subscriber too many helpers are acting as seeds,there will be an insufficient amount of relays to"ferry"content between seeds and subscribers. Conversely,if there were too few seeds storing the requested con- Fig.1.Illustration of the communication model. tent,it would be difficult for relays to find a seed,making relaying useless.To find the optimal tradeoff point,we introduce the con- Information searching in opportunistic networks:Content of- cept of offloading efficiency to incorporate mobile relays and seeds floading systems focus on reducing the data delivery cost for a in the same optimization framework.We prove that the storage given set of content [5,6,13-16].As contents are cached in a dis- optimization problem is convex for various types of contact pat- tributed way,one important issue in content offloading systems terns and can be efficiently solved in a distributed manner.Our is to search information in a network with dynamic topology and numerical and trace-driven results show that relaying can reduce intermittent connections.User interests and network structures the offloading failure rate by more than 30%in D2D systems. can be used to help the content searching process.SPOON uti- The main contributions of this paper are as follows: lizes interest based searching to improve the performance of P2P file sharing [17].Social contact information is utilized in [18]to 1.We propose a new content download pattern that uses relays in find the optimal caching point based on user interests.Seeker- addition to traditional seeds to improve the scalability of D2D Assisted Searching (SAS)use seekers to help node to search infor- offloading systems. mation,while assuming users with the same interest meets more 2.We introduce a storage optimization framework that can be ap- plied to different types of helpers in D2D offloading systems. frequently [19].Optimal searching strategy in linear opportunistic networks is studied in [201. 3.Assuming constant helper density and Poisson contact pro- Replication optimization in opportunistic networks:The goal cesses,we show that offloading systems with n helpers can of optimal content replication is to maximize the social welfare, support (Vn)pieces of content when using both relays and which is defined as the expected utility gain from offloading seeds,while the amount of content supported by a static Delay-utility models are introduced in [5]to describe the impa- caching system is only 0(1). tience of subscribers.The utility optimization problem is shown 4.We show that the joint storage assignment problem for relays to be NP-hard [5.6].There are several ways to obtain approximate and seeds is convex and can be efficiently solved.Furthermore, solutions,including greedy heuristic algorithms [6.convex relax- our model can be extended to other types of helpers with con- ation [5]and a distributed algorithm based on voting [13.Dis- cave offloading efficiency functions.This leads to a better un- tributed caching in Femtocells is considered in 21.The storage derstanding of storage allocation when the network has multi- allocation problem under this scenario is similar to D2D networks ple types of helpers. with fixed contact patterns.This problem can be formulated as a The rest of this paper is organized as follows:Section 2 reviews set cover problem that is NP-hard [21].Utility based replication al- related works in D2D content dissemination and Section 3 intro- gorithm is used in 22]to distribute mobile videos via human mo- duces the system model used in this paper.Section 4 analyzes the bility between fixed venues.In [23].Chen et al.propose a new file D2D offloading efficiency for relays and shows that on-demand re- replica optimization algorithm that considers both the node stor- lays can asymptotically increase the amount of content supported age and contact frequency. by the system.The storage assignment problem is described in In comparison,we study tradeoffs between using storage for re- Section 5 and the benefits of our scheme are shown by numerical laying and static caching under the D2D scenario.Our model com- results and trace-driven simulations in Section 6.Finally,Section 7 bines static caching systems [5,6]and message relaying methods in presents conclusions of this work. DTN[24].Unlike the traditional DTN routing problems,which only consider cache size in the asymptotical sense [8].we study cache utility with finite storage in the offloading system.In contrast to 2.Related work traditional DTN systems,where the source tries to find a best way to replicate the message,our system adopts a destination centric Message delivery in opportunistic networks:Opportunistic model,where the destination actively searches for the content. networks utilize the intermittent connection between mobile de- vices to transfer data from the source to the destination [7.For 3.Network model message delivery applications,the source first replicates the mes- sage to several relays using short-range links.Relays then deliver 3.1.System overview the message to the destination when they contact the destina- tion [8,9].Most research works in message delivery applications The D2D offloading system studied in this paper combines two consider how to reduce the end-to-end delay under storage con- communication networks:a cellular network and an opportunistic straints in relays [10-12].The content offloading systems studied in network of D2D communication,as shown in Fig 1.The cellular this paper are different to message delivery applications,since the network provides pervasive network coverage and a global com- initial request comes from the destination rather than the source. munication channel for all mobiles.Due to the high cost of cellular46 W. Wang et al. / Computer Communications 83 (2016) 45–55 there is a relay deployed at the subway station, this relay can ac￾tively search for the content requested by the subscriber and make sure the content can be delivered when the user passes by. Our analysis shows that using one relay with regular contact patterns can be as effective as increasing the number of seeds by a constant ratio. An important issue in a relaying system is to allocate storage for content. Because users can choose to statically cache the content or dynamically download new content for their friends, mobile relays and seeds are actually different roles played by the same group of helpers. In this way, relays and seeds need to share the lim￾ited storage resources in mobile helpers and storage allocation be￾comes critical to the performance of the offloading system. When too many helpers are acting as seeds, there will be an insufficient amount of relays to “ferry” content between seeds and subscribers. Conversely, if there were too few seeds storing the requested con￾tent, it would be difficult for relays to find a seed, making relaying useless. To find the optimal tradeoff point, we introduce the con￾cept of offloading efficiency to incorporate mobile relays and seeds in the same optimization framework. We prove that the storage optimization problem is convex for various types of contact pat￾terns and can be efficiently solved in a distributed manner. Our numerical and trace-driven results show that relaying can reduce the offloading failure rate by more than 30% in D2D systems. The main contributions of this paper are as follows: 1. We propose a new content download pattern that uses relays in addition to traditional seeds to improve the scalability of D2D offloading systems. 2. We introduce a storage optimization framework that can be ap￾plied to different types of helpers in D2D offloading systems. 3. Assuming constant helper density and Poisson contact pro￾cesses, we show that offloading systems with n helpers can support (√n) pieces of content when using both relays and seeds, while the amount of content supported by a static caching system is only O(1). 4. We show that the joint storage assignment problem for relays and seeds is convex and can be efficiently solved. Furthermore, our model can be extended to other types of helpers with con￾cave offloading efficiency functions. This leads to a better un￾derstanding of storage allocation when the network has multi￾ple types of helpers. The rest of this paper is organized as follows: Section 2 reviews related works in D2D content dissemination and Section 3 intro￾duces the system model used in this paper. Section 4 analyzes the D2D offloading efficiency for relays and shows that on-demand re￾lays can asymptotically increase the amount of content supported by the system. The storage assignment problem is described in Section 5 and the benefits of our scheme are shown by numerical results and trace-driven simulations in Section 6. Finally, Section 7 presents conclusions of this work. 2. Related work Message delivery in opportunistic networks: Opportunistic networks utilize the intermittent connection between mobile de￾vices to transfer data from the source to the destination [7]. For message delivery applications, the source first replicates the mes￾sage to several relays using short-range links. Relays then deliver the message to the destination when they contact the destina￾tion [8,9]. Most research works in message delivery applications consider how to reduce the end-to-end delay under storage con￾straints in relays [10–12]. The content offloading systems studied in this paper are different to message delivery applications, since the initial request comes from the destination rather than the source. Fig. 1. Illustration of the communication model. Information searching in opportunistic networks: Content of- floading systems focus on reducing the data delivery cost for a given set of content [5,6,13–16]. As contents are cached in a dis￾tributed way, one important issue in content offloading systems is to search information in a network with dynamic topology and intermittent connections. User interests and network structures can be used to help the content searching process. SPOON uti￾lizes interest based searching to improve the performance of P2P file sharing [17]. Social contact information is utilized in [18] to find the optimal caching point based on user interests. Seeker￾Assisted Searching (SAS) use seekers to help node to search infor￾mation, while assuming users with the same interest meets more frequently [19]. Optimal searching strategy in linear opportunistic networks is studied in [20]. Replication optimization in opportunistic networks: The goal of optimal content replication is to maximize the social welfare, which is defined as the expected utility gain from offloading. Delay-utility models are introduced in [5] to describe the impa￾tience of subscribers. The utility optimization problem is shown to be NP-hard [5,6]. There are several ways to obtain approximate solutions, including greedy heuristic algorithms [6], convex relax￾ation [5] and a distributed algorithm based on voting [13]. Dis￾tributed caching in Femtocells is considered in [21]. The storage allocation problem under this scenario is similar to D2D networks with fixed contact patterns. This problem can be formulated as a set cover problem that is NP-hard [21]. Utility based replication al￾gorithm is used in [22] to distribute mobile videos via human mo￾bility between fixed venues. In [23], Chen et al. propose a new file replica optimization algorithm that considers both the node stor￾age and contact frequency. In comparison, we study tradeoffs between using storage for re￾laying and static caching under the D2D scenario. Our model com￾bines static caching systems [5,6] and message relaying methods in DTN [24]. Unlike the traditional DTN routing problems, which only consider cache size in the asymptotical sense [8], we study cache utility with finite storage in the offloading system. In contrast to traditional DTN systems, where the source tries to find a best way to replicate the message, our system adopts a destination centric model, where the destination actively searches for the content. 3. Network model 3.1. System overview The D2D offloading system studied in this paper combines two communication networks: a cellular network and an opportunistic network of D2D communication, as shown in Fig 1. The cellular network provides pervasive network coverage and a global com￾munication channel for all mobiles. Due to the high cost of cellular