S.Zhang et aL /Computer Networks 83(2015)184-198 193 the delivery delay is too long.some subsequent requests the assumption.Let us take a look at the segmentation from other users may happen before the floating circle is overhead.Denote by cc the communication capacity set up:if it is too short,the floating circle may have to wait between two nodes,and by hd the length of the for a long time before any request arrives,which incurs Bluetooth protocol header.For a data item d of size s,if unnecessary forwarding cost.It is hard to analyse the s+hd cc.then we divide it into [ainadl segments. relationship between ticket number,delivery delay,and Remember that,the proposed framework uses ticket coun- forwarding cost;furthermore,estimating the generation ters to restrict the number of replications of any item to be time of subsequent requests seems impossible.We there- not larger than the number of tickets k(see Section 5.1). fore resort to the following heuristic. Therefore,the overall forwarding or storing overhead incurred by segmentation is not larger than [hd.k. 6.5.1.Delivering a data item to a floating circle Though this value increases as the length of protocol This happens when setting up a floating circle.A data header hd increases,in the current design of Bluetooth pro- delivery can be characterized by its start and end positions. tocols,hd is far less than cc.Thus,the segmentation over- The degree of similarity between two data deliveries can head is negligible. be measured by the Euclidean distance between their start and end points.For example,user ng is asked to send d 7.2.Active vs.passive positioning towards c at time ty:given a threshold n.we can select a set of data items:for each item d,in this set,1)the dis- Location information is used in three aspects in the pro- tance between pos and where the first requester of dx posed framework.One is to help the framework determine sends a request for dx,is not larger than 1s.2)the distance whether the moving direction of a mobile user deflect between cx and ci is not larger than 1s.Denote this set as much from the direction of a floating circle(Section 5.1); then the ticket number k can be estimated as the second one is to help the framework determine whether a mobile user is within the floating circle of a data item(Sections 5.2 and 5.3):and the last one is to provide (14) the location feedback when a user sends a query or receives a data item at the end (Section 5.4). The current design of MobiCache uses active positioning. where S denotes the cardinality of the set.Note that, ie.,mobile users actively record their positions over time. In fact,when there is energy concern,we can switch to after the circle of d,expires,k should be updated as fol- passive positioning,ie.,mobile users record their positions lows:k=k+1,if the floating circle is set up too late that only when necessary.Specifically.for the first aspect some data requests have to retrieve data via cellular net- above,we can use Spray and Wait [14]or Delegation works;otherwise,k=k-1. Forwarding [15],both of which do not need geographical information,instead of GAP:for the second and third 6.5.2.Delivering a data query to a floating circle aspects,mobile users turn on their GPS only when encoun- This happens when a user ny sends a data request tering the others,sending data queries or finally receiving towards the floating circle of di.Using the same method data items.We see that,this kind of passive positioning as above,we can estimate ky.The only difference is that, decreases the dependence on location information,and data di has only one k,because the first requester of di is meanwhile conserve energy to some extent. unique;but there are many k's,since there are many sub- Besides,when there are positioning errors,for the sec- sequent requesters.When user ny eventually receives d.it ond aspect above,we just need to set the radius of a float- informs the cellular operator of the delay he experienced. ing circle to be the one calculated in Section 6.3 plus the Then,ku is updated as follows:k=ky+1,if n obtains d maximum positioning error,which can guarantee that via cellular networks;otherwise,k=ky-1. the critical condition in Eg.(4)is still met.For the third The expositions hitherto focus on the scenario where aspect,position errors would not be amplified when decid- one data item has only one floating circle.However,when ing the center of a circle.Therefore,passive positioning can there is some sort of extremely popular data that users mitigate the negative impact of position errors. wish to have in a very small delay.multiple floating circles could be set up within a mobiArea to reduce access delay. 8.Performance evaluation The main idea of MobiCache can adapt naturally to this new context. In this section,we conduct extensive trace-driven sim- ulations to evaluate our design under different network 7.Discussion settings and reveal insights of the proposed design performance. 7.1.Segmentation overhead 8.1.Realistic traces and baseline algorithms We have assumed that all necessary data transfer can be completed during any contact in Section 3.1.If a data Our evaluations are conducted on three realistic traces, item is too large to be transferred in one contact,then where Bluetooth-enables devices (e.g.,iMotes)periodically we can divide it into several small segments which follow detects their peers nearly and record the contacts overthe delivery delay is too long, some subsequent requests from other users may happen before the floating circle is set up; if it is too short, the floating circle may have to wait for a long time before any request arrives, which incurs unnecessary forwarding cost. It is hard to analyse the relationship between ticket number, delivery delay, and forwarding cost; furthermore, estimating the generation time of subsequent requests seems impossible. We there￾fore resort to the following heuristic. 6.5.1. Delivering a data item to a floating circle This happens when setting up a floating circle. A data delivery can be characterized by its start and end positions. The degree of similarity between two data deliveries can be measured by the Euclidean distance between their start and end points. For example, user nk is asked to send di towards ci at time tk; given a threshold g3, we can select a set of data items: for each item dx in this set, 1) the dis￾tance between posnk tk and where the first requester of dx sends a request for dx, is not larger than g3, 2) the distance between cx and ci is not larger than g3. Denote this set as Sdi njtj , then the ticket number ki can be estimated as ki ¼ X dx2Sdi nj t j kx 0 BB@ 1 CCA , jSdi njtj j ð14Þ where jSdi njtj j denotes the cardinality of the set. Note that, after the circle of di expires, ki should be updated as fol￾lows: ki ¼ ki þ 1, if the floating circle is set up too late that some data requests have to retrieve data via cellular net￾works; otherwise, ki ¼ ki  1. 6.5.2. Delivering a data query to a floating circle This happens when a user nj sends a data request towards the floating circle of di. Using the same method as above, we can estimate kij. The only difference is that, data di has only one ki, because the first requester of di is unique; but there are many kij’s, since there are many sub￾sequent requesters. When user nj eventually receives di, it informs the cellular operator of the delay he experienced. Then, kij is updated as follows: kij ¼ kij þ 1, if nj obtains di via cellular networks; otherwise, kij ¼ kij  1. The expositions hitherto focus on the scenario where one data item has only one floating circle. However, when there is some sort of extremely popular data that users wish to have in a very small delay, multiple floating circles could be set up within a MobiArea to reduce access delay. The main idea of MobiCache can adapt naturally to this new context. 7. Discussion 7.1. Segmentation overhead. We have assumed that all necessary data transfer can be completed during any contact in Section 3.1. If a data item is too large to be transferred in one contact, then we can divide it into several small segments which follow the assumption. Let us take a look at the segmentation overhead. Denote by cc the communication capacity between two nodes, and by hd the length of the Bluetooth protocol header. For a data item d of size s, if s þ hd > cc, then we divide it into d s cchde segments. Remember that, the proposed framework uses ticket coun￾ters to restrict the number of replications of any item to be not larger than the number of tickets k (see Section 5.1). Therefore, the overall forwarding or storing overhead incurred by segmentation is not larger than d s cchde  hd  k. Though this value increases as the length of protocol header hd increases, in the current design of Bluetooth pro￾tocols, hd is far less than cc. Thus, the segmentation over￾head is negligible. 7.2. Active vs. passive positioning Location information is used in three aspects in the pro￾posed framework. One is to help the framework determine whether the moving direction of a mobile user deflect much from the direction of a floating circle (Section 5.1); the second one is to help the framework determine whether a mobile user is within the floating circle of a data item (Sections 5.2 and 5.3); and the last one is to provide the location feedback when a user sends a query or receives a data item at the end (Section 5.4). The current design of MobiCache uses active positioning, i.e., mobile users actively record their positions over time. In fact, when there is energy concern, we can switch to passive positioning, i.e., mobile users record their positions only when necessary. Specifically, for the first aspect above, we can use Spray and Wait [14] or Delegation Forwarding [15], both of which do not need geographical information, instead of GAP; for the second and third aspects, mobile users turn on their GPS only when encoun￾tering the others, sending data queries or finally receiving data items. We see that, this kind of passive positioning decreases the dependence on location information, and meanwhile conserve energy to some extent. Besides, when there are positioning errors, for the sec￾ond aspect above, we just need to set the radius of a float￾ing circle to be the one calculated in Section 6.3 plus the maximum positioning error, which can guarantee that the critical condition in Eq. (4) is still met. For the third aspect, position errors would not be amplified when decid￾ing the center of a circle. Therefore, passive positioning can mitigate the negative impact of position errors. 8. Performance evaluation In this section, we conduct extensive trace-driven sim￾ulations to evaluate our design under different network settings and reveal insights of the proposed design performance. 8.1. Realistic traces and baseline algorithms Our evaluations are conducted on three realistic traces, where Bluetooth-enables devices (e.g., iMotes) periodically detects their peers nearly and record the contacts over S. Zhang et al. / Computer Networks 83 (2015) 184–198 193