S.Zhang et aL /Computer Networks 83(2015)184-198 185 through caching:some users intentionally cache cellular The remainder of this paper is organized as follows.We contents,which can be used to satisfy future queries from go over related work and our contributions in Section 2. other users We provide the system model and motivate our work in An important concern of this paradigm is that it may Section 3.Section 4 overviews the proposed framework. incur a long delay.Obviously not all cellular contents could Sections 5 and 6 present the details of our framework. bear long delays.But there are a large body of contents We discuss known issues and extensions in Section 7. (e.g,optional software update,interesting videos)that Before concluding the paper in Section 9,we evaluate the not only permit offloading,but for which it is essential to do performance of the framework in Section 8. so in order to relieve cellular networks and lower users'sub- scription fees.Prior studies mainly focus on placing data items in several selected helpers [5.10.12].so that future 2.Related work and our contributions queries can be responded to without signaling between cellular networks and users.However,if mobile users enter There is a rich heritage of studies on cellular network and leave the target area over time,these strategies would offloading and delay tolerable networks (DTNs)that fail to maintain data availability,since they could not find informed and inspired our design.We describe a subset an appropriate group of helpers that can stay and serve of these related efforts below inside the target area for a sufficiently long period. An MSN can be considered as a type of DTN,which lacks In this paper,we examine the research decisions and persistent end-to-end connectivity,due to low node den- design tradeoffs that arise when offloading cellular traffic in sity and/or unpredictable node mobility.To cope with the such a dynamic area of interest,referred to as a MobiArea. intermittent connectivity.epidemic routing [13]is pro- Our goal is to maximize cellular operators'revenues and posed to deliver packets via flooding:however,this incurs minimize the overhead imposed on mobile devices.We an extremely high forwarding cost.Some later work develop an offloading framework,MobiCache,which caches [14,15]reduces this cost through intelligent relay selec- data in geographical floating circles instead of fixed nodes. tion.Intentional routing16 translates an administrator- When a user requests a data item,the cellular operator offers specified routing metric into per-packet utilities.Social a choice to him/her:obtain the data either from the cellular features are exploited to facilitate DTN routing [17]or network immediately,or from that data's floating circle improve hypertext results [18].A Global Positioning within a predetermined system-specified delay. System (GPS)-assisted geographical routing protocol is Several challenges have to be addressed to realize our developed in 19 for vehicular delay-tolerant networks. goals.How to minimize the computational overhead Prior studies on cellular traffic offloading through imposed on mobile devices to conserve their batteries? device-to-device connections [20]can be categorized into How to route data or queries towards geographical floating two broad types,based on the hop count between cellular circles without incurring too much forwarding cost?When networks and users:single-hop [10]and multi-hop 6,8. two users with limited buffers have a contact,how to per- Most of them [6,8.10]mainly focus on selecting a group form cache replacement to improve cost-effectiveness? of users as bridges between cellular networks and users. How to determine the positions,radii,and lifetimes of Moreover,WiFi throughput prediction is exploited for floating circles,so as to minimize forwarding cost involved vehicular Internet access in [7.Auction-based incentive in circles,as well as the total access delay over all potential mechanisms for offloading are designed in [91. requesters？ Computation offloading is investigated in [11. We investigate techniques to settle these challenges in The problem of placing data copies in nodes with lim- MobiCache,which is generally composed of two parts:the ited memories is investigated in [5,21,22]with different user side and the operator side.On the user side of our sys- goals:maximizing the total size of offloaded data,mini- tem,we propose to cache in floating circles,to overcome mizing total access cost,and maximizing the probability dynamics and develop a ticket-based geographical routing of retrieving a file that contains multiple erasure blocks, scheme for delivering data items and queries;a cache respectively.The publish/subscribe based caching is inves- replacement strategy is also designed to improve caching tigated in [12.Content floating technique [23,24]main- cost-effectiveness.On the operator side,we maintain tains data items through flooding them inside their query history and feedback information collected over respective floating circles and discarding them outside time for every data item,and perform predictions and esti- their respective circles.Theoretical analyses show that mations based on the following principle:similar data the expected data availability can be sufficiently long.pro- attracts similar users.In doing so,the computation-inten- vided that a critical condition is met.A short survey on sive task,ie.,parameter determination,is completed by caching mechanisms for web,ad hoc networks and DTNs cellular operators,which lowers the overhead imposed is presented in 25,which also provides some inspiring on mobile devices and also is convenient for operators to ideas for content caching and retrieval for vehicular maximize their revenues. delay-tolerant networks. Our framework is of course not a panacea.We admit Comparatively,in this paper,we propose to cache in that many challenges remain,e.g,privacy and energy floating circles,instead of fixed users,to cope with the issues.Addressing these concerns is a direction of our dynamics of the target area,and we develop MobiCache future work.While our approach does not generalize to for cellular operators to maximize their revenues,and all scenarios,we hope that our proposal will provide some minimize overhead on mobile devices.Although the idea potential guidelines for future offloading design. of content floating is not new,to the best of our knowledge,through caching: some users intentionally cache cellular contents, which can be used to satisfy future queries from other users. An important concern of this paradigm is that it may incur a long delay. Obviously not all cellular contents could bear long delays. But there are a large body of contents (e.g., optional software update, interesting videos) that not only permit offloading, but for which it is essential to do so in order to relieve cellular networks and lower users’ sub￾scription fees. Prior studies mainly focus on placing data items in several selected helpers [5,10,12], so that future queries can be responded to without signaling between cellular networks and users. However, if mobile users enter and leave the target area over time, these strategies would fail to maintain data availability, since they could not find an appropriate group of helpers that can stay and serve inside the target area for a sufficiently long period. In this paper, we examine the research decisions and design tradeoffs that arise when offloading cellular traffic in such a dynamic area of interest, referred to as a MobiArea. Our goal is to maximize cellular operators’ revenues and minimize the overhead imposed on mobile devices. We develop an offloading framework, MobiCache, which caches data in geographical floating circles instead of fixed nodes. When a user requests a data item, the cellular operator offers a choice to him/her: obtain the data either from the cellular network immediately, or from that data’s floating circle within a predetermined system-specified delay. Several challenges have to be addressed to realize our goals. How to minimize the computational overhead imposed on mobile devices to conserve their batteries? How to route data or queries towards geographical floating circles without incurring too much forwarding cost? When two users with limited buffers have a contact, how to per￾form cache replacement to improve cost-effectiveness? How to determine the positions, radii, and lifetimes of floating circles, so as to minimize forwarding cost involved in circles, as well as the total access delay over all potential requesters? We investigate techniques to settle these challenges in MobiCache, which is generally composed of two parts: the user side and the operator side. On the user side of our sys￾tem, we propose to cache in floating circles, to overcome dynamics and develop a ticket-based geographical routing scheme for delivering data items and queries; a cache replacement strategy is also designed to improve caching cost-effectiveness. On the operator side, we maintain query history and feedback information collected over time for every data item, and perform predictions and esti￾mations based on the following principle: similar data attracts similar users. In doing so, the computation-inten￾sive task, i.e., parameter determination, is completed by cellular operators, which lowers the overhead imposed on mobile devices and also is convenient for operators to maximize their revenues. Our framework is of course not a panacea. We admit that many challenges remain, e.g., privacy and energy issues. Addressing these concerns is a direction of our future work. While our approach does not generalize to all scenarios, we hope that our proposal will provide some potential guidelines for future offloading design. The remainder of this paper is organized as follows. We go over related work and our contributions in Section 2. We provide the system model and motivate our work in Section 3. Section 4 overviews the proposed framework. Sections 5 and 6 present the details of our framework. We discuss known issues and extensions in Section 7. Before concluding the paper in Section 9, we evaluate the performance of the framework in Section 8. 2. Related work and our contributions There is a rich heritage of studies on cellular network offloading and delay tolerable networks (DTNs) that informed and inspired our design. We describe a subset of these related efforts below. An MSN can be considered as a type of DTN, which lacks persistent end-to-end connectivity, due to low node den￾sity and/or unpredictable node mobility. To cope with the intermittent connectivity, epidemic routing [13] is pro￾posed to deliver packets via flooding; however, this incurs an extremely high forwarding cost. Some later work [14,15] reduces this cost through intelligent relay selec￾tion. Intentional routing [16] translates an administrator￾specified routing metric into per-packet utilities. Social features are exploited to facilitate DTN routing [17] or improve hypertext results [18]. A Global Positioning System (GPS)-assisted geographical routing protocol is developed in [19] for vehicular delay-tolerant networks. Prior studies on cellular traffic offloading through device-to-device connections [20] can be categorized into two broad types, based on the hop count between cellular networks and users: single-hop [10] and multi-hop [6,8]. Most of them [6,8,10] mainly focus on selecting a group of users as bridges between cellular networks and users. Moreover, WiFi throughput prediction is exploited for vehicular Internet access in [7]. Auction-based incentive mechanisms for offloading are designed in [9]. Computation offloading is investigated in [11]. The problem of placing data copies in nodes with lim￾ited memories is investigated in [5,21,22] with different goals: maximizing the total size of offloaded data, mini￾mizing total access cost, and maximizing the probability of retrieving a file that contains multiple erasure blocks, respectively. The publish/subscribe based caching is inves￾tigated in [12]. Content floating technique [23,24] main￾tains data items through flooding them inside their respective floating circles and discarding them outside their respective circles. Theoretical analyses show that the expected data availability can be sufficiently long, pro￾vided that a critical condition is met. A short survey on caching mechanisms for web, ad hoc networks and DTNs is presented in [25], which also provides some inspiring ideas for content caching and retrieval for vehicular delay-tolerant networks. Comparatively, in this paper, we propose to cache in floating circles, instead of fixed users, to cope with the dynamics of the target area, and we develop MobiCache for cellular operators to maximize their revenues, and minimize overhead on mobile devices. Although the idea of content floating is not new, to the best of our knowledge, S. Zhang et al. / Computer Networks 83 (2015) 184–198 185