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 theiroperator 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., bat￾tery 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 opera￾tor 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, yield￾ing 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 strat￾egy (Section 5.3) is then designed to improve cache cost￾effectiveness. 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 system￾specified 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 system￾specified 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 geo￾graphical 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 parame￾ters 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 geo￾graphical regions. In the following, we propose a simple scheme based on active positioning. By ‘‘active position￾ing’’ 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