190 S.Zhang et aL/Computer Networks 83(2015)184-198 Mobile nodes enter and leave the MobiArea over time. Even if we cache data in some popular nodes,and let these nodes hand over their cached data to other nodes when they leave the MobiArea,what do we actually get?The answer is caching data in a region,and the region is,in fact the entire MobiArea. Some other studies[26,27]have proposed to strategi- cally deploy throwbox,a kind of stationary wireless node that acts as a relay,to improve DTN throughput.Why not place some throwboxes in the MobiArea for caching? There are several concerns.First and foremost,throwboxes are expensive and cannot be massively deployed.Second throwboxes restrict our choice of caching positions to a Fig.5.Cache replacement.The weight of a data item da for user n is limited set of candidate locations-locations of throw- determined by the remaining lifetime rle before the floating circle of de boxes,which may result in performance degradation,indi- expires and the chord length cl. cated by the total access delay over all requesters decisions separately.Taking n for example,we formulate 5.3.Cache replacement policy for pairwise encounters the cache replacement as the following Knapsack problem [351: This section focuses on cache replacement for pairwise encounters inside floating circles,and does not take into max account data or query copies incurred by GAP(Section 5.1) k=1 or other routing protocols(Section 5.4).Ideally,a mobile user m maintains a data item if this user is geographically inside subject to X5k≤B时 (5) the floating circle of this data item.However,user n has k=1 a limited buffer of size B;therefore,user n has to strategi- k∈{0,1}，k∈{1,2，，m} cally select a subset of items for caching. The cache replacement occurs when two mobile users where xy indicates whether d would be cached in n.and with different sets of data items have a contact.In Fig.5, the product(rlk.cl)serves as the weight of dk for n. user n meets another user n at time ky:without loss of Observing that sk and Bi are integers,we can use dynamic generality,the union set of data items cached at these programming to solve this problem in O(mB time. two users is assumed to be s={d,d2.....dm).The cache replacement decision is based on remaining lifetime and 5.4.Data query from users and response from floating circles chord length.The remaining lifetime rl of data d represents the remaining time before the floating circle of d expires. When a mobile user np requests de from the cellular The chord length clu of data dk for a user n denotes the operator,if the cellular operator detects that there is length that n would travel in the floating circle of dy if n already a floating circle of dk.the operator offers two keeps its moving direction unchanged.Fig.5 illustrates choices:directly download the data from cellular net- cl and clhi.Given the center position and radius of a float- works,or indirectly get the data via opportunistic device- ing circle,the current position and the moving direction of to-device connections within a predetermined delay.If n a user,the chord length can be easily attained by plane chooses the latter,the operator replies with Ck.ck,rk,and geometry. ku(see Fig.1 for notations).User n then checks the interest We note that the popularity of a data item is not consid- probability Pa(see Eq.(1)).Depending on Pik,n can choose ered here.The reason is implicit,if somewhat subtle:the either to physically move to the circle,or to send queries lifetime (Section 6.4)of a floating circle already reflects and wait for a response. the popularity of the respective data,ie..the floating circle If n chooses to send queries,it employs GAP to send of a more popular data has a longer lifetime queries with ku tickets towards the floating circle of dk. We have the following argument:both of n and ny are Any user ny inside the circle of dk exploits existing DTN inside the floating circle of every data item in S.Recall that. routing algorithms,e.g..Spray and Wait [14]and del- each user is free to delete a data item after he leaves the egation forwarding [15].for delivering de to n upon receiv- respective circle,which implies,if a node caches d.this ing the query.Before n receives any response from the node is inside the floating circle of di.In addition,as we floating circle,n might get a copy of dk when contacting assumed in Section 3.1,the transmission range and the another user who happens to have a copy of dk.Anyway, physical size of every mobile user are negligibly small user n can send the request again to the cellular operator compared to the size of the MobiArea;taking these two for free if he does not receive dy after the predetermined sys- facts together completes the argument. tem-specified delay passes,the operator then pushes da to n Each data item has four options:cached at both nodes, directly via cellular networks. at n.at n.or at neither of them,which makes the problem untractable.We propose to approximate it as follows: 1As the physical position ofn is not fixed.we cannot use GAP in this regarding s as the selection pool,n and ny make their response process.Mobile nodes enter and leave the MobiArea over time. Even if we cache data in some popular nodes, and let these nodes hand over their cached data to other nodes when they leave the MobiArea, what do we actually get? The answer is caching data in a region, and the region is, in fact, the entire MobiArea. Some other studies [26,27] have proposed to strategi￾cally deploy throwbox, a kind of stationary wireless node that acts as a relay, to improve DTN throughput. Why not place some throwboxes in the MobiArea for caching? There are several concerns. First and foremost, throwboxes are expensive and cannot be massively deployed. Second, throwboxes restrict our choice of caching positions to a limited set of candidate locations—locations of throw￾boxes, which may result in performance degradation, indi￾cated by the total access delay over all requesters. 5.3. Cache replacement policy for pairwise encounters This section focuses on cache replacement for pairwise encounters inside floating circles, and does not take into account data or query copies incurred by GAP (Section 5.1) or other routing protocols (Section 5.4). Ideally, a mobile user maintains a data item if this user is geographically inside the floating circle of this data item. However, user ni has a limited buffer of size Bi; therefore, user ni has to strategi￾cally select a subset of items for caching. The cache replacement occurs when two mobile users with different sets of data items have a contact. In Fig. 5, user ni meets another user nj at time kci ; without loss of generality, the union set of data items cached at these two users is assumed to be S ¼ fd1; d2; ... ; dmg. The cache replacement decision is based on remaining lifetime and chord length. The remaining lifetime rld of data d represents the remaining time before the floating circle of d expires. The chord length clki of data dk for a user ni denotes the length that ni would travel in the floating circle of dk if ni keeps its moving direction unchanged. Fig. 5 illustrates clki and clhi. Given the center position and radius of a float￾ing circle, the current position and the moving direction of a user, the chord length can be easily attained by plane geometry. We note that the popularity of a data item is not consid￾ered here. The reason is implicit, if somewhat subtle: the lifetime (Section 6.4) of a floating circle already reflects the popularity of the respective data, i.e., the floating circle of a more popular data has a longer lifetime. We have the following argument: both of ni and nj are inside the floating circle of every data item in S. Recall that, each user is free to delete a data item after he leaves the respective circle, which implies, if a node caches di, this node is inside the floating circle of di. In addition, as we assumed in Section 3.1, the transmission range and the physical size of every mobile user are negligibly small compared to the size of the MobiArea; taking these two facts together completes the argument. Each data item has four options: cached at both nodes, at ni, at nj, or at neither of them, which makes the problem untractable. We propose to approximate it as follows: regarding S as the selection pool, ni and nj make their decisions separately. Taking ni for example, we formulate the cache replacement as the following Knapsack problem [35]: max Xm k¼1 xk  rlk  clki subject to Xm k¼1 xk  sk 6 Bi xk 2 f0; 1g; 8k 2 f1; 2; ... ; mg ð5Þ where xk indicates whether dk would be cached in ni, and the product ðrlk  clkiÞ serves as the weight of dk for ni. Observing that sk and Bi are integers, we can use dynamic programming to solve this problem in OðmBiÞ time. 5.4. Data query from users and response from floating circles When a mobile user ni requests dk from the cellular operator, if the cellular operator detects that there is already a floating circle of dk, the operator offers two choices: directly download the data from cellular net￾works, or indirectly get the data via opportunistic device￾to-device connections within a predetermined delay. If ni chooses the latter, the operator replies with Ck; ck;rk, and kki (see Fig. 1 for notations). User ni then checks the interest probability Pik (see Eq. (1)). Depending on Pik; ni can choose either to physically move to the circle, or to send queries and wait for a response. If ni chooses to send queries, it employs GAP to send queries with kki tickets towards the floating circle of dk. Any user nj inside the circle of dk exploits existing DTN routing algorithms,1 e.g., Spray and Wait [14] and del￾egation forwarding [15], for delivering dk to ni upon receiv￾ing the query. Before ni receives any response from the floating circle, ni might get a copy of dk when contacting another user who happens to have a copy of dk. Anyway, user ni can send the request again to the cellular operator for free if he does not receive dk after the predetermined sys￾tem-specified delay passes, the operator then pushes dk to ni directly via cellular networks. j i Fig. 5. Cache replacement. The weight of a data item dk for user ni is determined by the remaining lifetime rlk before the floating circle of dk expires and the chord length clki. 1 As the physical position of ni is not fixed, we cannot use GAP in this response process. 190 S. Zhang et al. / Computer Networks 83 (2015) 184–198