54 W.Wang et aL /Computer Communications 83 (2016)45-55 static 女optimal 0.6 0.6 06 0.5 0.g ◇limited friends 0.4 0-0-0-000-0-0-0-00-0 20.4 0000 公 女relay 0.3 relay 0-0-0-0 02 o-unifor uniform 0.9 0. ostatic 0.1 static 0.2 0.4 0.6 0.8 20 Nun2otcateg8ries 60 80 100 Normalize (a)Different offloading schemes (b)Different number of content categories (c)Different requesting rates 10 ☆relav 女Relay 08 uniform -Relay with friend limit ostatic Static O-static 出0 10 8 0.4 0.2 50 n(numof nodes) 150 200 10 102 0 10 120 n(num of nodes) 10 40 (hours 100 (d)Different number of helpers (e)Amount of content supported by different (f)Performance for MIT reality traces schemes (Offloading failure probability=0.2). Fig.5.Offloading failure probability performances. performance when the number of helpers increases.The offload- T>80.Comparing Fig.5(a)-(f),we observe that the trace-driven ing failure probability deceases in a much faster speed in the relay results have trends similar to those in the numerical results,while case than in the static and uniform case. the trace-driven result is worse than that predicted by theory.This Fig.5(e)considers the amount of content that an offloading sys- may be caused by the limited choices of relays in the trace-driven tem can support when the network size increases as discussed simulation. in Section 4.3.The number of helpers n increases from 100 to 100,000 and we use convex optimization to find the amount of 7.Conclusion content that the system can offload with a failure probability smaller than 20%.We observe that the static system can only of- In this paper,we proposed a novel relay-based storage assign- fload a constant amount of content while in the relaying case,the ment framework for D2D systems.Instead of using storage as static amount of content increases with n.We also evaluate the case content cache,our scheme uses on-demand relaying to enhance where subscribers have less than 10 friends.In this case,we ob- the storage utilization.We demonstrated the usefulness of this serve that the relay system can support 10 times more content relaying framework through both theoretical analysis and trace than the static caching system.However,the amount of content driven simulations.To further improve our system,one important that the system can support converges after the number of helpers future research direction is to study the incentives of the helpers exceeds 5000.This implies that supporting larger amounts of con- so that more users will participate in the offloading system. tent will likely require multi-hop relaying or common relays de- ployed by the network operator for all subscribers. Acknowledgment 6.2.Trace-driven simulations This work is partially supported by NSFC Grants (No.61373129. No.91218302.No.61321491,No.61472185).JiangSu NSF(No. We use MIT reality traces [35]to verify the performance of our BK20151390).and EU FP7 IRSES MobileCloud Project Grant (No. scheme in real networks.The trace is collected by 100 students 612212). and faculties who carries smart phones for more than 9 months to collect Bluetooth devices in proximity [35.The Bluetooth trace References are collected by 100 internal devices which have discovered ap- proximately 20,000 external devices in total.Therefore,we only [1]Cisco.Cisco Visual Networking Index:Global Mobile Data Traffic Forecast Up- have a partial view of the entire contact process.The average con- date,Cisco White Paper,2014,pp.2013-2018. 2]3GPP,Feasibility study for proximity services.SA1 TR 28.803(2012). tact rate for users is 31.44 per day,after removing empty days,i.e. [3]K.Doppler.M.Rinne.C.Wijting.C.Ribeiro,K Hugl,Device-to-device commu- days with no contacts.Based on the estimation of average contact nication as an underlay to LTE-advanced networks.Commun.Mag.IEEE 47 rate,we allocate storage to 100 Zipf distributed pieces of content 12)(2009)42-49. [4]B.Han.P.Hui,V.A.Kumar.M.V.Marathe,J.Shao.A.Srinivasan,Mobile data using our optimization algorithm,while assuming that each node offloading through opportunistic communications and social participation.IEEE can store two pieces of contents.Only the 100 internal devices is Trans.Mobile Comput.11 (5)(2012)821-834. selected as relays in the simulation,while all devices can be seeds 5].Reich.A.Chaintreau.The age of impatience:optimal replication schemes for opportunistic networks,in:Proceedings of ACM CoNEXT,2009. Fig.5(f)depicts the offloading failure probabilities under dif- [6]Y.Li,G.Su,P.Hui.D.Jin,L Su,L Zeng.Multiple mobile data offloading through ferent schemes.We observe that both the static and relay scheme delay tolerant networks.in:Proceedings of ACM CHANTS,2011. outperform the uniform scheme.The offloading failure probability 17]M.Conti,M.Kumar,Opportunities in opportunistic computing.Computer 43 (1)(2010)42-50. of the relay scheme is similar to the static scheme when T is small. [8]A.Balasubramanian,B.Levine.A.Venkataramani.DTN routing as a resource However,the failure probability is reduced by more than 30%when allocation problem,in:Proceedings of ACM SIGCOMM.2007.54 W. Wang et al. / Computer Communications 83 (2016) 45–55 Fig. 5. Offloading failure probability performances. performance when the number of helpers increases. The offload￾ing failure probability deceases in a much faster speed in the relay case than in the static and uniform case. Fig. 5(e) considers the amount of content that an offloading sys￾tem can support when the network size increases as discussed in Section 4.3. The number of helpers n increases from 100 to 100,000 and we use convex optimization to find the amount of content that the system can offload with a failure probability smaller than 20%. We observe that the static system can only of- fload a constant amount of content while in the relaying case, the amount of content increases with n. We also evaluate the case where subscribers have less than 10 friends. In this case, we ob￾serve that the relay system can support 10 times more content than the static caching system. However, the amount of content that the system can support converges after the number of helpers exceeds 5000. This implies that supporting larger amounts of con￾tent will likely require multi-hop relaying or common relays de￾ployed by the network operator for all subscribers. 6.2. Trace-driven simulations We use MIT reality traces [35] to verify the performance of our scheme in real networks. The trace is collected by 100 students and faculties who carries smart phones for more than 9 months to collect Bluetooth devices in proximity [35]. The Bluetooth trace are collected by 100 internal devices which have discovered ap￾proximately 20,000 external devices in total. Therefore, we only have a partial view of the entire contact process. The average con￾tact rate for users is 31.44 per day, after removing empty days, i.e., days with no contacts. Based on the estimation of average contact rate, we allocate storage to 100 Zipf distributed pieces of content using our optimization algorithm, while assuming that each node can store two pieces of contents. Only the 100 internal devices is selected as relays in the simulation, while all devices can be seeds. Fig. 5(f) depicts the offloading failure probabilities under dif￾ferent schemes. We observe that both the static and relay scheme outperform the uniform scheme. The offloading failure probability of the relay scheme is similar to the static scheme when T is small. However, the failure probability is reduced by more than 30% when T > 80. Comparing Fig. 5(a)–(f), we observe that the trace-driven results have trends similar to those in the numerical results, while the trace-driven result is worse than that predicted by theory. This may be caused by the limited choices of relays in the trace-driven simulation. 7. Conclusion In this paper, we proposed a novel relay-based storage assign￾ment framework for D2D systems. Instead of using storage as static content cache, our scheme uses on-demand relaying to enhance the storage utilization. We demonstrated the usefulness of this relaying framework through both theoretical analysis and trace driven simulations. To further improve our system, one important future research direction is to study the incentives of the helpers so that more users will participate in the offloading system. Acknowledgment This work is partially supported by NSFC Grants (No. 61373129, No. 91218302, No. 61321491, No. 61472185), JiangSu NSF (No. BK20151390), and EU FP7 IRSES MobileCloud Project Grant (No. 612212). References [1] Cisco, Cisco Visual Networking Index: Global Mobile Data Traffic Forecast Up￾date, Cisco White Paper, 2014, pp. 2013–2018. [2] 3GPP, Feasibility study for proximity services, SA1 TR 28.803 (2012). [3] K. Doppler, M. Rinne, C. Wijting, C. Ribeiro, K. Hugl, Device-to-device commu￾nication as an underlay to LTE-advanced networks, Commun. Mag., IEEE 47 (12) (2009) 42–49. [4] B. Han, P. Hui, V.A. Kumar, M.V. Marathe, J. Shao, A. Srinivasan, Mobile data offloading through opportunistic communications and social participation, IEEE Trans. Mobile Comput. 11 (5) (2012) 821–834. [5] J. Reich, A. Chaintreau, The age of impatience: optimal replication schemes for opportunistic networks, in: Proceedings of ACM CoNEXT, 2009. [6] Y. Li, G. Su, P. Hui, D. Jin, L. Su, L. Zeng, Multiple mobile data offloading through delay tolerant networks, in: Proceedings of ACM CHANTS, 2011. [7] M. Conti, M. Kumar, Opportunities in opportunistic computing, Computer 43 (1) (2010) 42–50. [8] A. Balasubramanian, B. Levine, A. Venkataramani, DTN routing as a resource allocation problem, in: Proceedings of ACM SIGCOMM, 2007