S.Zhang et aL /Computer Networks 83(2015)184-198 191 We note that,users may not be willing to decide,on a T per-item basis,whether to use cellular networks or 8 C offloading.To make the procedure seamless,we allow cost bene; Ci users to setup their policies in our framework,e.g.,"down- load Facebook stuff as fast as possible,and optional soft- o to p0t0 ware updates as cheaply as possible".In doing so.when flagy users get data from floating circles,the service they experi- ence is still seamless. In this section,we see that the computation overhead at mobile devices is small.We shall see in the next section that,the computation-intensive task,e.g.,parameter esti- Fig.6.The information maintained by the cellular operator for each data mation,is shifted to the cellular operator side. item d.Parameters in white grids can be obtained based on history and feedback:parameters in shadow grids need to be estimated. 6.MobiCache on the cellular operator side 6.2.Revenue maximization This section presents the details of MobiCache on the operator side.We first introduce the query history and user Denote by bene the benefit that the operator gains from feedback information maintained by cellular operators in delivering data d to user j:denote by cost the reward that Section 6.1,and presents the revenue maximization prob- the operator offers to user j for forwarding data d,one time. lem in Section 6.2.In Sections 6.3-6.5.we explain how to We note that,each data item d would be forwarded many optimize framework parameters based on the collected times during the lifetime of its floating circle;the cellular information. operator tracks how many times a user forwards a data item through feedback,as shown in Fig.6.We define them 6.1.Query history and user feedback as follows: Fig.6 shows the information maintained by a cellular 0. if the delivery is via cellular networks. bene= operator for data di.In the first row,s is the size:Ci is 0.4si,otherwise.(si is the size of di.) the characteristic vector;T is the point of time when the (6) cellular operator starts to set up the floating circle for d:q and f are the number of requests for d and the num- 0 if the delivery is via cellular networks. ber of forwardings that d experiences from time T to cost 6.67s x 10-5.otherwise. T+,respectively.In the second row,cost and bene will (7) be introduced in the next subsection. The third row records the first request for d:user no If the delivery is via cellular networks,we have sends a request for di at time to at position pos and bene=cost=0;this is reasonable,since delivering d to receives d via cellular networks;the cellular operator asks user j via cellular networks implies that,cellular networks no to deliver d to the respective floating circle with k tick- may fail to satisfy another user somewhere,due to its con- ets.Recall the definition of Ti.we have Tto. gestion.Otherwise,we set benef and cost according to the Each following row corresponds to a request for d;dur- pricing gap in Section 3.We see that,for two different ing the period from T to T+:user n (j=1.2.....q) users ny and nk,bene bene and cost costf.therefore, sends a request for di at time ty at position pos.then without causing any confusion,bene and bene will be the operator informs ny to send a query to the respective used interchangeably,and the same holds for cost and circle with ky tickets,finally n receives di at time t at posi- cost.The revenue of an operator is defined as follows: tion pos via offloading (flag,=1)or cellular networks R=>(bene-cost). (8) 1ag=0) diny When users send requests or receive data,they are asked to provide feedback:geographical positions and To maximize R,an operator should offload as much cellu- the number of forwardings that they have helped in the lar traffic as possible,while incurring as little forwarding past(including forwardings inside and outside floating cir- cost as possible.In the next three subsection,we present cles).We mention that,feedback may violate the privacy of how to achieve this goal through parameter optimization, users;we do not consider privacy issues as they are out of based upon query history and user feedback information. the scope of this paper.In doing so,the operator obtains the white fields in Fig.6:the rest of this section then 6.3.Circle center and radius focuses on determining the fields in shadow. At the beginning,there is no query history or user feed- The center position c of data di should be chosen to back for the proposed framework to estimate framework minimize the sum of distances between c and the posi- parameters.We propose to either use part of the trace as tions of potential requesters while they are sending warm-up period to accumulate necessary information,or ini- requests.But how can we know who would download d tialize the settings with empirical values. and where they are in advance?The basic principle is that,We note that, users may not be willing to decide, on a per-item basis, whether to use cellular networks or offloading. To make the procedure seamless, we allow users to setup their policies in our framework, e.g., ‘‘down￾load Facebook stuff as fast as possible, and optional soft￾ware updates as cheaply as possible’’. In doing so, when users get data from floating circles, the service they experi￾ence is still seamless. In this section, we see that the computation overhead at mobile devices is small. We shall see in the next section that, the computation-intensive task, e.g., parameter esti￾mation, is shifted to the cellular operator side. 6. MobiCache on the cellular operator side This section presents the details of MobiCache on the operator side. We first introduce the query history and user feedback information maintained by cellular operators in Section 6.1, and presents the revenue maximization prob￾lem in Section 6.2. In Sections 6.3–6.5, we explain how to optimize framework parameters based on the collected information. 6.1. Query history and user feedback Fig. 6 shows the information maintained by a cellular operator for data di. In the first row, si is the size; Ci is the characteristic vector; Ti is the point of time when the cellular operator starts to set up the floating circle for di; qi and fi are the number of requests for di and the num￾ber of forwardings that di experiences from time Ti to Ti þ li, respectively. In the second row, costi and benei will be introduced in the next subsection. The third row records the first request for di: user n0 sends a request for di at time t0 at position posn0 t0 and receives di via cellular networks; the cellular operator asks n0 to deliver di to the respective floating circle with ki tick￾ets. Recall the definition of Ti, we have Ti  t0. Each following row corresponds to a request for di dur￾ing the period from Ti to Ti þ li: user nj (j ¼ 1; 2; ... ; qi) sends a request for di at time tj at position posnj tj , then the operator informs nj to send a query to the respective circle with kij tickets, finally nj receives di at time t 0 j at posi￾tion posnj t0 j via offloading (flagj ¼ 1) or cellular networks (flagj ¼ 0). When users send requests or receive data, they are asked to provide feedback: geographical positions and the number of forwardings that they have helped in the past (including forwardings inside and outside floating cir￾cles). We mention that, feedback may violate the privacy of users; we do not consider privacy issues as they are out of the scope of this paper. In doing so, the operator obtains the white fields in Fig. 6; the rest of this section then focuses on determining the fields in shadow. At the beginning, there is no query history or user feed￾back for the proposed framework to estimate framework parameters. We propose to either use part of the trace as warm-up period to accumulate necessary information, or ini￾tialize the settings with empirical values. 6.2. Revenue maximization Denote by benej i the benefit that the operator gains from delivering data di to user j; denote by costj i the reward that the operator offers to user j for forwarding data di one time. We note that, each data item di would be forwarded many times during the lifetime of its floating circle; the cellular operator tracks how many times a user forwards a data item through feedback, as shown in Fig. 6. We define them as follows: benej i ¼ 0; if the delivery is via cellular networks; 0:4si; otherwise: ðsi is the size of di:Þ ð6Þ costj i ¼ 0; if the delivery is via cellular networks; 6:67si 106 ; otherwise: ð7Þ If the delivery is via cellular networks, we have benej i ¼ costj i ¼ 0; this is reasonable, since delivering di to user j via cellular networks implies that, cellular networks may fail to satisfy another user somewhere, due to its con￾gestion. Otherwise, we set benej i and costj i according to the pricing gap in Section 3. We see that, for two different users nj and nk; benej i ¼ benek i and costj i ¼ costk i , therefore, without causing any confusion, benej i and benei will be used interchangeably, and the same holds for costj i and costi. The revenue of an operator is defined as follows: R ¼ X di;nj ðbenej i  costj iÞ: ð8Þ To maximize R, an operator should offload as much cellu￾lar traffic as possible, while incurring as little forwarding cost as possible. In the next three subsection, we present how to achieve this goal through parameter optimization, based upon query history and user feedback information. 6.3. Circle center and radius The center position ci of data di should be chosen to minimize the sum of distances between ci and the posi￾tions of potential requesters while they are sending requests. But how can we know who would download di and where they are in advance? The basic principle is that, Fig. 6. The information maintained by the cellular operator for each data item di. Parameters in white grids can be obtained based on history and feedback; parameters in shadow grids need to be estimated. S. Zhang et al. / Computer Networks 83 (2015) 184–198 191