Computer Networks 83(2015)184-198 Contents lists available at ScienceDirect Computer Computer Networks Networks ELSEVIER journal homepage:www.elsevier.com/locate/comnet MobiCache:Cellular traffic offloading leveraging cooperative CrossMark caching in mobile social networks Sheng Zhang3*,Jie Wu b,Zhuzhong Qian3,Sanglu Lu State Key Laboratory for Novel Software Technology.Nanjing University.China PDepartment of Computer and Information Sciences,Temple University.USA ARTICLE INFO ABSTRACT Article history: Offloading cellular traffic through mobile social networks has arisen as a promising way for Received 3 November 2014 relieving cellular networks.Prior studies mainly focused on caching data in a number of Received in revised form 10 February 2015 pre-selected helpers.However,such a strategy would fail when mobile users enter and Accepted 2 March 2015 leave the target area over time.In this paper,we examine the research decisions and design Available online 20 March 2015 tradeoffs that arise when offloading cellular traffic in such a dynamic area of interest, referred to as a MobiArea,and we design an offloading framework,MobiCache,for maximiz- Keywords: Cellular traffic offloading ing cellular operators'revenues and minimizing the overhead imposed on mobile devices. Content floating On the user side,we propose a content floating-based cooperative caching strategy that Cooperative caching caches data in geographical floating circles.instead of selected helpers in previous studies. Mobile social networks to cope with the dynamics.A geographical routing scheme is designed for delivering data and queries towards floating circles.We also develop a cache replacement scheme to improve caching cost-effectiveness inside floating circles.On the operator side.query his- tory and feedback are maintained for cellular operators to optimize framework parameters that maximize their revenues.Extensive trace-driven simulations show that,compared with a state-of-the-art scheme,MobiCache offloads up to 52%more traffic with 15%shorter delay and 6%less forwarding cost. 2015 Elsevier B.V.All rights reserved. 1.Introduction already made several measures for throttling its customers [2].One straightforward solution to tackling this problem The past few years have witnessed the explosive popu- would be deploying more base stations to expand cellular larity of smart-phones and tablets.According to Cisco network capacity [3].which is limited,however,since it Visual Networking Index (VNI)[1,the mobile data traffic requires high financial input but gets low and diminishing generated in 2014 was nearly 30 times the size of the returns.Addressing this problem needs some paradigm-al- entire global Internet in 2000,and global mobile traffic will tering approaches. grow at a compound annual growth rate of 57 percent Due to the inherent proximity-based sharing ability of from 2014 to 2019;in other words,it will increase 10-fold mobile devices and the delay-tolerant nature of many cel- and reach 24.3 exabytes per month by 2019.This huge lular contents,offloading cellular traffic through mobile amount of data traffic,as a consequence,has degraded ser- social networks (MSNs)[4]has arisen recently as a promis- vice quality and created immense pressure on the limited ing method for relieving cellular networks [5-11].When spectrum of cellular networks.For example,AT&T has users are rewarded with proper incentives [9.10],it is very likely that they will be willing to wait for a predetermined Corresponding author.TeL:+8625 83681369. delay to obtain some cellular contents,and to help store- E-mail addresses:sheng@nju.edu.cn (S.Zhang).jiewu@temple.edu carry-forward them.Traffic offloading then can be realized (J.Wu).qzz@nju.edu.cn (Z.Qian).sanglu@nju.edu.cn (S.Lu). http://dx.doi.org/10.1016/j.comnet.2015.03.011 1389-1286/2015 Elsevier B.V.All rights reserved
MobiCache: Cellular traffic offloading leveraging cooperative caching in mobile social networks Sheng Zhang a,⇑ , Jie Wu b , Zhuzhong Qian a , Sanglu Lu a a State Key Laboratory for Novel Software Technology, Nanjing University, China bDepartment of Computer and Information Sciences, Temple University, USA article info Article history: Received 3 November 2014 Received in revised form 10 February 2015 Accepted 2 March 2015 Available online 20 March 2015 Keywords: Cellular traffic offloading Content floating Cooperative caching Mobile social networks abstract Offloading cellular traffic through mobile social networks has arisen as a promising way for relieving cellular networks. Prior studies mainly focused on caching data in a number of pre-selected helpers. However, such a strategy would fail when mobile users enter and leave the target area over time. 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, and we design an offloading framework, MobiCache, for maximizing cellular operators’ revenues and minimizing the overhead imposed on mobile devices. On the user side, we propose a content floating-based cooperative caching strategy that caches data in geographical floating circles, instead of selected helpers in previous studies, to cope with the dynamics. A geographical routing scheme is designed for delivering data and queries towards floating circles. We also develop a cache replacement scheme to improve caching cost-effectiveness inside floating circles. On the operator side, query history and feedback are maintained for cellular operators to optimize framework parameters that maximize their revenues. Extensive trace-driven simulations show that, compared with a state-of-the-art scheme, MobiCache offloads up to 52% more traffic with 15% shorter delay and 6% less forwarding cost. 2015 Elsevier B.V. All rights reserved. 1. Introduction The past few years have witnessed the explosive popularity of smart-phones and tablets. According to Cisco Visual Networking Index (VNI) [1], the mobile data traffic generated in 2014 was nearly 30 times the size of the entire global Internet in 2000, and global mobile traffic will grow at a compound annual growth rate of 57 percent from 2014 to 2019; in other words, it will increase 10-fold and reach 24.3 exabytes per month by 2019. This huge amount of data traffic, as a consequence, has degraded service quality and created immense pressure on the limited spectrum of cellular networks. For example, AT&T has already made several measures for throttling its customers [2]. One straightforward solution to tackling this problem would be deploying more base stations to expand cellular network capacity [3], which is limited, however, since it requires high financial input but gets low and diminishing returns. Addressing this problem needs some paradigm-altering approaches. Due to the inherent proximity-based sharing ability of mobile devices and the delay-tolerant nature of many cellular contents, offloading cellular traffic through mobile social networks (MSNs) [4] has arisen recently as a promising method for relieving cellular networks [5–11]. When users are rewarded with proper incentives [9,10], it is very likely that they will be willing to wait for a predetermined delay to obtain some cellular contents, and to help storecarry-forward them. Traffic offloading then can be realized http://dx.doi.org/10.1016/j.comnet.2015.03.011 1389-1286/ 2015 Elsevier B.V. All rights reserved. ⇑ Corresponding author. Tel.: +86 25 83681369. E-mail addresses: sheng@nju.edu.cn (S. Zhang), jiewu@temple.edu (J. Wu), qzz@nju.edu.cn (Z. Qian), sanglu@nju.edu.cn (S. Lu). Computer Networks 83 (2015) 184–198 Contents lists available at ScienceDirect Computer Networks journal homepage: www.elsevier.com/locate/comnet
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’ subscription 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 perform 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 system, 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 estimations based on the following principle: similar data attracts similar users. In doing so, the computation-intensive 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 density and/or unpredictable node mobility. To cope with the intermittent connectivity, epidemic routing [13] is proposed to deliver packets via flooding; however, this incurs an extremely high forwarding cost. Some later work [14,15] reduces this cost through intelligent relay selection. Intentional routing [16] translates an administratorspecified 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 limited memories is investigated in [5,21,22] with different goals: maximizing the total size of offloaded data, minimizing total access cost, and maximizing the probability of retrieving a file that contains multiple erasure blocks, respectively. The publish/subscribe based caching is investigated in [12]. Content floating technique [23,24] maintains 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, provided 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
186 S.Zhang et aL /Computer Networks 83(2015)184-198 MobiCache is the first system that supports offloading in There are already some incentive mechanisms 9,10, dynamic areas without any stationary nodes'assistance which motivate users to tolerate a predetermined tolerable (e.g.throwboxes [26,27]).More specifically,the con- delay or to help in forwarding data.We will not discuss the tributions of this paper are summarized as follows.(1) design of such mechanisms,as it is orthogonal to the focus MobiCache intentionally maintains data availability within of this paper.Notations are summarized in Fig.1 for geographical floating circles to overcome the dynamics; reference. (2)we propose a ticket-based geographical routing scheme for delivering data items and queries;(3)a dynamic pro- 3.2.Motivations gramming-based caching replacement policy is designed for improving caching cost-effectiveness;and (4)we pro- 3.2.1.Popular regions vide a set of effective heuristics for operators to optimize We examine the Dartmouth trace[29 to better under- framework parameters to maximize their revenues. stand user mobility patterns.The trace consists of two parts:access point (AP)locations which provides the loca- 3.Background and motivations tions of 623 APs (only 507 of them are valid)on the Dartmouth campus,and client-AP associations which pro- This section overviews the assumptions and models vides the association information of 6022 clients over a used in this paper and motivates the offloading design of period of 703 days.After proper preprocessing on the raw MobiCache based on two observations. data,we find that most of the association records emerge during the last one-fourth of the duration,and most of 3.1.Models and assumptions the clients only have a small number of associations over 703 days.Therefore,we only use the mobility trace of 78 We denote by MobiArea the dynamic area of interest. clients collected from the 525th day to the 703th day. Denote a mobile user that has emerged in the MobiArea Fig.2 shows the locations of 340 APs that have associa- as ng.In this paper,mobile nodes,users,and devices will tions with at least one of the 78 clients during that time be interchangeably used.Users n and ny can communicate period.The number of associations of an AP is indicated with each other through a wireless interface (WiFi or by the type of the corresponding marker that represents Bluetooth)if and only if their distance is not larger than the AP.We see that,there are several extremely popular a fixed range.This range,and the physical size of each APs.These popular regions will facilitate MobiCache,as mobile user,are assumed to be negligibly small compared MobiCache would need to maintain data availability at geo- to the dimensions of the MobiArea. graphical floating circles for future data queries. As assumed in prior studies [5.12,21.22],most users are not willing to contribute all of their mobile storage to cach- 3.2.2.Pricing gap ing cellular data,thus,we denote the available buffer size Since users have to tolerate some delay before getting of user n as B.We also assume that each user is equipped data through offloading,this charge should be cut down with a GPS to determine his position;this can be easily to some extent.For example,Verizon charges a user achieved,since almost all of the smart-phones and tablets roughly 8 USD for 1 GB data [30].i.e.,0.8 cents for 1 MB nowadays have a rich set of sensors.We will discuss how data:if a user gets a data item via offloading.Verizon to deal with errors in positioning and how to reduce may charge it 0.4si cents,where si is the size of the data energy consumption for positioning in Section 7. in MB. Denote a data item as d,and its size as si.For simplicity. When a user contributes one forwarding of a data item, we assume that all necessary data transfer can be com- the cellular operator rewards the user with a few cents, pleted during any contact.If sy is too large to be transferred which should at least compensate for the energy consump- during a contact,then we can divide d into several small tion in forwarding the data.The data transfer rate between segments,each of which follows the assumption.The seg- mobile devices is assumed to be 1 MB/s (the typical rate of mentation overhead is discussed in Section 7. Bluetooth v1.2 [31]).thus,transmitting a data item of s MB User n is associated with an interest vector li.repre- lasts about s seconds.According US Energy Information sented by a M x 1 vector [p.p2.....Pul,where M denotes Administration report[32].the average price of residential the size of the keywords universe and p[0,1]indicates electricity in the US was about 12 cents per kW h in 2013. the probability of this user to be interested in the hth key- Based on measurements in [33].the energy consumption word ]The sum is normalized to 1.Similarly. rate of a mobile phone during transmission is about 2 W. data item d is associated with a characteristic vector Cj. Therefore,an operator should pay (12 x(2 x s))/(1000x represented by a Mx1 vector C=g,e以,e,where 3600)6.67sx 10-5 cents to a user who forwards a data item with a size of s in MB one time. ek[0,1]indicates the extent to which the hth keyword We see that,cellular operators could still make profit,as can characterize this data.Also,>Me=1.Then,the long as the forwarding times of a data item is less than probability that n is interested in d,is defined as: (0.4s)/6.67s×10-6)≈59,970,which is sufficiently large for mobile users to cooperatively cache data in geographi- cal floating circles.As evidenced in Section 8,the average =1 forwarding number of a data item is approximately
MobiCache is the first system that supports offloading in dynamic areas without any stationary nodes’ assistance (e.g., throwboxes [26,27]). More specifically, the contributions of this paper are summarized as follows. (1) MobiCache intentionally maintains data availability within geographical floating circles to overcome the dynamics; (2) we propose a ticket-based geographical routing scheme for delivering data items and queries; (3) a dynamic programming-based caching replacement policy is designed for improving caching cost-effectiveness; and (4) we provide a set of effective heuristics for operators to optimize framework parameters to maximize their revenues. 3. Background and motivations This section overviews the assumptions and models used in this paper and motivates the offloading design of MobiCache based on two observations. 3.1. Models and assumptions We denote by MobiArea the dynamic area of interest. Denote a mobile user that has emerged in the MobiArea as ni. In this paper, mobile nodes, users, and devices will be interchangeably used. Users ni and nj can communicate with each other through a wireless interface (WiFi or Bluetooth) if and only if their distance is not larger than a fixed range. This range, and the physical size of each mobile user, are assumed to be negligibly small compared to the dimensions of the MobiArea. As assumed in prior studies [5,12,21,22], most users are not willing to contribute all of their mobile storage to caching cellular data, thus, we denote the available buffer size of user ni as Bi. We also assume that each user is equipped with a GPS to determine his position; this can be easily achieved, since almost all of the smart-phones and tablets nowadays have a rich set of sensors. We will discuss how to deal with errors in positioning and how to reduce energy consumption for positioning in Section 7. Denote a data item as di, and its size as si. For simplicity, we assume that all necessary data transfer can be completed during any contact. If si is too large to be transferred during a contact, then we can divide di into several small segments, each of which follows the assumption. The segmentation overhead is discussed in Section 7. User ni is associated with an interest vector Ii, represented by a M 1 vector ½pi 1; pi 2; ... ; pi M T , where M denotes the size of the keywords universe and pi h 2 ½0; 1 indicates the probability of this user to be interested in the hth keyword [28]. The sum PM h¼1pi h is normalized to 1. Similarly, data item dj is associated with a characteristic vector Cj, represented by a M 1 vector Cj ¼ ½ej 1; ej 2; ... ; ej M T , where ej h 2 ½0; 1 indicates the extent to which the hth keyword can characterize this data. Also, PM h¼1ej h ¼ 1. Then, the probability that ni is interested in dj is defined as: Pij ¼ I T i Cj ¼ XM h¼1 pi h ej h: ð1Þ There are already some incentive mechanisms [9,10], which motivate users to tolerate a predetermined tolerable delay or to help in forwarding data. We will not discuss the design of such mechanisms, as it is orthogonal to the focus of this paper. Notations are summarized in Fig. 1 for reference. 3.2. Motivations 3.2.1. Popular regions We examine the Dartmouth trace [29] to better understand user mobility patterns. The trace consists of two parts: access point (AP) locations which provides the locations of 623 APs (only 507 of them are valid) on the Dartmouth campus, and client-AP associations which provides the association information of 6022 clients over a period of 703 days. After proper preprocessing on the raw data, we find that most of the association records emerge during the last one-fourth of the duration, and most of the clients only have a small number of associations over 703 days. Therefore, we only use the mobility trace of 78 clients collected from the 525th day to the 703th day. Fig. 2 shows the locations of 340 APs that have associations with at least one of the 78 clients during that time period. The number of associations of an AP is indicated by the type of the corresponding marker that represents the AP. We see that, there are several extremely popular APs. These popular regions will facilitate MobiCache, as MobiCache would need to maintain data availability at geographical floating circles for future data queries. 3.2.2. Pricing gap Since users have to tolerate some delay before getting data through offloading, this charge should be cut down to some extent. For example, Verizon charges a user roughly 8 USD for 1 GB data [30], i.e., 0.8 cents for 1 MB data; if a user gets a data item via offloading, Verizon may charge it 0:4si cents, where si is the size of the data in MB. When a user contributes one forwarding of a data item, the cellular operator rewards the user with a few cents, which should at least compensate for the energy consumption in forwarding the data. The data transfer rate between mobile devices is assumed to be 1 MB/s (the typical rate of Bluetooth v1.2 [31]), thus, transmitting a data item of si MB lasts about si seconds. According US Energy Information Administration report [32], the average price of residential electricity in the US was about 12 cents per kW h in 2013. Based on measurements in [33], the energy consumption rate of a mobile phone during transmission is about 2 W. Therefore, an operator should pay ð12 ð2 siÞÞ=ð1000 3600Þ 6:67si 106 cents to a user who forwards a data item with a size of si in MB one time. We see that, cellular operators could still make profit, as long as the forwarding times of a data item is less than ð0:4siÞ=ð6:67si 106 Þ 59; 970, which is sufficiently large for mobile users to cooperatively cache data in geographical floating circles. As evidenced in Section 8, the average forwarding number of a data item is approximately 186 S. Zhang et al. / Computer Networks 83 (2015) 184–198
S.Zhang et aL /Computer Networks 83 (2015)184-198 187 Notation Definitions n a mobile user/node/device B available buffer size of user n L the interest vector of user ni the size of data d, the characteristic vector of data di P the probability that n;is interested in d, a data item cj the 2-D coordinates of the floating circle center of d; i the radius of the floating circle of d the lifetime of the floating circle of di of tickets for delivering di to its circle k of tickets for delivering n,'s request for di's circle Fig.1.Main notations are summarized for reference 441510 4.41 4.405 0 。89 4.4 0039 0 4.395 80 ● 4.39 6 0 4.385 438 8 4.37 .17 8.18 8.19 8.2 8.21 8.22 8.23 x coordinate x10 Fig.2.The locations(indicated by the centers of markers)and the number of associations(circle:0-100:triangle:100-1000:square:1000-10.000:star: 10,000)of the selected 340 access points in Dartmouth trace [29]. 250-800 in MobiCache,which is much smaller than the 4.1.On the cellular operator side maximum allowable number of forwarding times.This tremendous gap allows us to design a cooperative To maximize the cellular operator's revenues caching-based method for efficient offloading. (Section 6.2),MobiCache estimates the following parame- ters that guide the set-up of the floating circle for d:(1) 4.MobiCache overview The coordinates of the circle center.c1=(c.c) (Section 6.3).which should be determined to minimize Our objective is to offer a practical and feasible offload- the total access delay of all potential requesters of d.For ing service at dynamic areas without any stationary infras- example,there are more potential requesters of d in the tructure assistance.We provide an overview of MobiCache northwest part in this figure,so the circle center for d is through an illustrative example in Fig.3.After user n suc- chosen near that part.(2)The radius of the floating circle, cessfully downloads data d via cellular networks,the cel- r(Section 6.3).A large radius is beneficial to maintaining lular operator detects that this is the first download of d in the availability of d,but incurs unnecessary forwarding the MobiArea.Based on history and feedback information cost.(3)The lifetime of the floating circle,h(Section 6.4). collected in the past (Section 6.1).the cellular operator As time goes on,the potential requesters of di become learns that there may be many forthcoming requests for fewer,while the maintenance cost becomes greater. d:for example,the nodes with horizontal lines are poten- MobiCache should carefully determine h to maximize tial requesters of d.To relieve the crowded cellular net- operators'revenue.When a floating circle expires,all work but,meanwhile,satisfy those upcoming requesters, devices involved in the circle are free to delete the the cellular operator resorts to caching d in a geographical corresponding data.(4)The maximum number of copies floating circle. of d when delivering d to its circle,k(Section 6.5).The
250–800 in MobiCache, which is much smaller than the maximum allowable number of forwarding times. This tremendous gap allows us to design a cooperative caching-based method for efficient offloading. 4. MobiCache overview Our objective is to offer a practical and feasible offloading service at dynamic areas without any stationary infrastructure assistance. We provide an overview of MobiCache through an illustrative example in Fig. 3. After user n1 successfully downloads data d1 via cellular networks, the cellular operator detects that this is the first download of d1 in the MobiArea. Based on history and feedback information collected in the past (Section 6.1), the cellular operator learns that there may be many forthcoming requests for d1; for example, the nodes with horizontal lines are potential requesters of d1. To relieve the crowded cellular network but, meanwhile, satisfy those upcoming requesters, the cellular operator resorts to caching d1 in a geographical floating circle. 4.1. On the cellular operator side To maximize the cellular operator’s revenues (Section 6.2), MobiCache estimates the following parameters that guide the set-up of the floating circle for d1: (1) The coordinates of the circle center, c1 ¼ ðc x 1 ; c y 1 Þ (Section 6.3), which should be determined to minimize the total access delay of all potential requesters of d1. For example, there are more potential requesters of d1 in the northwest part in this figure, so the circle center for d1 is chosen near that part. (2) The radius of the floating circle, r1 (Section 6.3). A large radius is beneficial to maintaining the availability of d1, but incurs unnecessary forwarding cost. (3) The lifetime of the floating circle, l1 (Section 6.4). As time goes on, the potential requesters of d1 become fewer, while the maintenance cost becomes greater. MobiCache should carefully determine l1 to maximize operators’ revenue. When a floating circle expires, all devices involved in the circle are free to delete the corresponding data. (4) The maximum number of copies of d1 when delivering d1 to its circle, k1 (Section 6.5). The Fig. 1. Main notations are summarized for reference. 8.17 8.18 8.19 8.2 8.21 8.22 8.23 x 105 4.375 4.38 4.385 4.39 4.395 4.4 4.405 4.41 4.415 x 105 x coordinate y coordinate Fig. 2. The locations (indicated by the centers of markers) and the number of associations (circle: 0–100; triangle: 100–1000; square: 1000–10,000; star: P10,000) of the selected 340 access points in Dartmouth trace [29]. S. Zhang et al. / Computer Networks 83 (2015) 184–198 187
188 S.Zhang et aL /Computer Networks 83 (2015)184-198 Query User History Feedback d n Parameter Estimation ● Circle Center Circle Radius 18 cle Lifetime ● Ticket No MobiArea Cellular Operator Fig.3.The big picture of MobiCache.c and r specify the floating circle for d(i=1,2 in this example).The nodes with horizontal and vertical lines denote potential requesters of d,and d2.respectively.The cellular operator estimates framework parameters based on query history and user feedback collected over time. operator can use k to control the tradeoff between the 4.2.4.Data query from users and response from floating circles delivery cost (i.e.,the number of data replicates)and the When node nz requests d from cellular networks,the delivery latency. operator detects that there is already a floating circle for d.so the operator offers a choice to nz:obtain the data either from the cellular network immediately,or from 4.2.On the user side the floating circle of d within a predetermined system- specified delay.If n accepts the latter,the operator returns Due to resource constraints of mobile devices.e.g..bat- ci and k17 to nz.Depending on the degree of interest,n tery lifetime and slow processing speed,MobiCache also can freely choose either to physically move to the circle tries to shift computation-intensive tasks to the cellular and get d,or to send queries (Section 5.4).If the latter operator side,so as to reduce the computational overhead happens.nz employs the geographical routing scheme in on mobile devices. Section 5.1 with k tickets to deliver queries to the circle of d,then waits for a response.The operator also guarantees 4.2.1.Delivering data to its floating circle to push d to nz via cellular networks once the system- With proper incentive mechanisms,the cellular opera- specified delay passes. In the next two sections,we provide the design details tor then sends these parameters to n and asks n to deliver of MobiCache on the user side and the cellular operator side, d to the specified circle.User n employs the geographical routing scheme in Section 5.1 to deliver d to its floating respectively. circle. 5.MobiCache on the user side 4.2.2.Maintaining data availability in floating circles In this section,we present the details of the proposed When the first copy of d enters its circle,d would get framework on the user side.Section 5.1 provides a routing replicated whenever a node with it contacts another node scheme for a user sending a data item or query to a geo- without it inside the circle (Section 5.2).When a critical graphical circle.Section 5.2 introduces how to maintain condition is met,the expected availability of d can be suf- data availability in floating circles.Section 5.3 deals with ficiently long,as demonstrated in [23,24].The reason for pairwise encounters within floating circles.Section 5.4 using the circle shape for content floating is that a circle shows how to get data from floating circles.Most parame- can be accurately expressed by its center and radius,yield- ters involved in this section are estimated by cellular ing little additional information that needs to be operators,which will be explained in Section 6. transmitted. 5.1.Delivering data to a floating circle 4.2.3.Cache replacement policy for pairwise encounters Some prior studies [14-16]focused on delivering data As there are some other data items,nodes with limited packets to mobile destinations;different from them,we buffers may meet inside the intersection of two or more are interested in routing data items or queries to geo- circles(e.g.ns and ne in Fig.3).A cache replacement strat- graphical regions.In the following,we propose a simple egy(Section 5.3)is then designed to improve cache cost- scheme based on active positioning.By "active position- effectiveness. ing"we mean that,mobile users actively record their
operator can use k1 to control the tradeoff between the delivery cost (i.e., the number of data replicates) and the delivery latency. 4.2. On the user side Due to resource constraints of mobile devices, e.g., battery lifetime and slow processing speed, MobiCache also tries to shift computation-intensive tasks to the cellular operator side, so as to reduce the computational overhead on mobile devices. 4.2.1. Delivering data to its floating circle With proper incentive mechanisms, the cellular operator then sends these parameters to n1 and asks n1 to deliver d1 to the specified circle. User n1 employs the geographical routing scheme in Section 5.1 to deliver d1 to its floating circle. 4.2.2. Maintaining data availability in floating circles When the first copy of d1 enters its circle, d1 would get replicated whenever a node with it contacts another node without it inside the circle (Section 5.2). When a critical condition is met, the expected availability of d1 can be suf- ficiently long, as demonstrated in [23,24]. The reason for using the circle shape for content floating is that a circle can be accurately expressed by its center and radius, yielding little additional information that needs to be transmitted. 4.2.3. Cache replacement policy for pairwise encounters As there are some other data items, nodes with limited buffers may meet inside the intersection of two or more circles (e.g., n5 and n6 in Fig. 3). A cache replacement strategy (Section 5.3) is then designed to improve cache costeffectiveness. 4.2.4. Data query from users and response from floating circles When node n7 requests d1 from cellular networks, the operator detects that there is already a floating circle for d1, so the operator offers a choice to n7: obtain the data either from the cellular network immediately, or from the floating circle of d1 within a predetermined systemspecified delay. If n7 accepts the latter, the operator returns c1 and k1;7 to n7. Depending on the degree of interest, n7 can freely choose either to physically move to the circle and get d1, or to send queries (Section 5.4). If the latter happens, n7 employs the geographical routing scheme in Section 5.1 with k1;7 tickets to deliver queries to the circle of d1, then waits for a response. The operator also guarantees to push d1 to n7 via cellular networks once the systemspecified delay passes. In the next two sections, we provide the design details of MobiCache on the user side and the cellular operator side, respectively. 5. MobiCache on the user side In this section, we present the details of the proposed framework on the user side. Section 5.1 provides a routing scheme for a user sending a data item or query to a geographical circle. Section 5.2 introduces how to maintain data availability in floating circles. Section 5.3 deals with pairwise encounters within floating circles. Section 5.4 shows how to get data from floating circles. Most parameters involved in this section are estimated by cellular operators, which will be explained in Section 6. 5.1. Delivering data to a floating circle Some prior studies [14–16] focused on delivering data packets to mobile destinations; different from them, we are interested in routing data items or queries to geographical regions. In the following, we propose a simple scheme based on active positioning. By ‘‘active positioning’’ we mean that, mobile users actively record their Fig. 3. The big picture of MobiCache. ci and ri specify the floating circle for di (i ¼ 1; 2 in this example). The nodes with horizontal and vertical lines denote potential requesters of d1 and d2, respectively. The cellular operator estimates framework parameters based on query history and user feedback collected over time. 188 S. Zhang et al. / Computer Networks 83 (2015) 184–198