移动机会网络中接触时间感知的协作缓存策略

郑 啸 高 汉 王修君 秦 锋

(安徽工业大学计算机科学与技术学院 安徽马鞍山 243002)(xzheng@ahut.edu.cn)

随着移动智能终端设备的普及，通过此类终端设备获取数据服务的需求也变得越来越多.如何快速高效地为移动用户提供数据服务，降低网络基础设施负担，也备受到人们的关注.协作缓存技术通过在网络中选取一组节点作为缓存节点，并让缓存节点持有原始数据的拷贝为后续的数据请求提供响应.通过协作缓存技术能够有效地减少用户访问延迟和通信开销，但如何有效地利用协作缓存技术提高移动环境中数据访问效率还存在着诸多问题：

1) 移动节点所能够缓存的数据量是不同的，每个节点缓存数据所能带来的收益也是不同的，因此必须合理地选择数据缓存节点来进行数据缓存.

2) 移动环境中的节点具有高度自主移动性，这使得节点间接触时间各不相同，且具有一定的限制.当网络中数据量较大时往往不能够在一次接触过程中传输完成，造成节点间接触机会的浪费.

3) 移动环境中的节点往往是由手持智能终端设备扮演，因此存在缓存容量受限的问题.当节点缓存过多数据而导致无法在一次接触中完成传输时，则会对缓存空间造成浪费.因此，要合理确定缓存节点的缓存边界以限定节点的缓存数据量，从而减少缓存空间的消耗和浪费.

针对上述问题，本文提出了相应的对策：

1) 移动机会网络中节点之间的连接是间断的、不连续的，因此节点之间的连通性十分重要.本文根据节点联通性提出了一个度量标准来评判节点的重要程度，并以此来解决缓存节点的选择问题.

2) 由于接触时间的限制，数据无法在一次接触过程中传输完成.本文通过对数据进行分片处理来降低接触时间的影响，并为每个节点确定缓存边界来合理利用节点中有限的缓存空间.

1 相关工作

在移动机会网络中，节点具有高度的自主移动性，使得网络拓扑结构动态变化，如何合理有效地放置缓存数据提高用户获取内容资源和网络资源的利用率得到了普遍的关注.文献[1-3]根据节点的位置将网络拓扑结构划分为多个协作区域，并通过缓存控制判断是否接纳数据，最后由区域中心分配数据缓存节点.但是中心节点必须保存组内节点已缓存数据的信息，来避免组内缓存数据的重复问题.刘外喜等人[4]提出了一种在分布式缓存机制中嵌入中心式缓存决策的机制，它把内容的放置、发现、替换统一起来考虑，实现内容的有序缓存.Wei等人[5]提出了一种支持平等性感知的协作缓存协议，通过选取节点的亲密节点集合来缓存数据并实现协作的功能.文献[6]为提高命名数据网络(named data networking, NDN)中的缓存利用率，提出了一种基于蚁群替换算法的邻居协作缓存管理策略.文献[7]通过对高热度内容进行分布式缓存实现缓存节点间的协作，并在内容请求过程中利用跟踪节点实现缓存内容的定位.文献[8]提出一种基于缓存迁移的协作缓存机制，在缓存节点选择时考虑节点的中心性,保证内容尽可能缓存在位置更重要的节点.Nuggehalli等人[9]和Tang等人[10]对缓存放置问题进行了数学建模,并研究了缓存放置问题的计算复杂度,最后给出了求解缓存放置问题的近似算法.文献[11]建立了移动节点缓存容量的预测模型，并提出了基于蚁群算法的协作缓存策略.上述文献都很好地解决了移动环境中协作缓存的问题，但都没有考虑到节点间接触时间对缓存的影响.文献[12]利用已有的节点接触模型以及节点接触时间持续模型提出了基于社会网络的数据协同缓存策略，在该方案中解决了节点接触时间对缓存的影响，但没有考虑数据恢复时遇到的赠券收集问题.文献[13]中考虑了容迟网络中接触时间对接触过程中传输数据量的影响，提出了自适应接触量预测模型，并用实验验证了该模型在处理一次接触中高效传输数据的重要性.本文分析了节点间的接触历史信息，充分考虑了接触时间对缓存的影响，提出了接触时间感知的协作缓存策略.

2 问题定义

2.1 网络模型

2.2 主要思想及问题

为了提高协作缓存的效率，应当优先选择具有较高缓存能力的节点作为缓存节点，然而在计算节点的缓存能力时，传统的解决方案大都假定缓存数据能够在缓存节点与请求节点间的一次接触过程中传输完成.但是由于节点之间有限的接触时间使得每次接触所能传输的数据量存在限制，因此这一假设并不存在普适性.由于节点的数据传输无法全部完成，当在节点中缓存的数据较多时就会降低缓存的效能.图1表明了接触时间对缓存的影响.图1中节点A为数据请求节点，并且其所请求的数据包含8个数据分片.同时节点A在移动过程中会相继接触节点B，C，D，并且在接触的过程中分别能够传输5个、3个和2个数据分片.在图1(a)所示的场景中，整个数据被作为一个缓存单元，同时节点B被选择作为缓存节点.在这种情况下，节点A仅仅能够通过在与节点B的接触过程中获取5个数据分片，另外缓存的3个数据分片并不能获取，同时由于节点C，D上没有缓存数据，节点A与节点C，D之间的接触机会都被浪费，降低了缓存的效率.然而，如图1(b)所示，若将一个数据分片作为缓存单元并假定节点B缓存5个数据分片，节点C缓存2个，节点D缓存1个，那么整个数据所有的8个数据分片都能够获取到，从而能够恢复所请求的数据.在这种情况下节点的缓存空间以及节点之间接触机会都得到了更好的利用.基于这一思想，本文必须解决2个问题：

1) 如何根据节点的缓存能力合理地选择缓存节点.

2) 如何确定缓存节点所能缓存的数据量.

本文提出了一个新的评价标准来计算节点的缓存能力，在此基础上解决了缓存节点的选择问题；然后根据每个节点的接触历史确定节点的缓存上限，有效地利用节点的缓存空间，同时限定数据在网络中的副本数量，减少同一数据占用的缓存资源.

Fig. 1 The impact of contact duration on cache nodes图1 接触时间对缓存的影响

3 缓存协议设计

本文首先对研究问题进行了分析及形式化描述，并在此基础上提出了移动环境中接触时间感知的协作缓存协议.

3.1 问题分析

在移动机会网络环境中，节点获取网络数据大都存在时延，本文假定用户容忍的最大时延为T.为了有效地评价缓存效率，本文定义在时间限制T内，节点能够向数据请求者发送的数据包数量为该节点所能获得的缓存收益.

定义1. 节点缓存收益.节点i为节点j提供数据而获得的收益Bij定义为

Bij=gsij，

(1)

其中，g为数据包的大小，sij是节点i在时间T内能够向节点j发送的数据包的个数.

定义2. 区域缓存收益.社区中所有缓存节点在时间T内获得的缓存收益之和Bcom定义为

(2)

当网络中区域缓存收益越大时，节点需要从AP上下载数据包的可能性就越小，并能够减少获取数据的延迟，提高数据访问的命中率.

定义3. 缓存代价.网络中缓存的编码后的数据包数目与该数据包含的原始数据包数目的比值定义为缓存代价γ.

假设某数据包含8个原始数据包，同时在整个网络中缓存了16个该数据的编码数据包，那么该数据的缓存代价γ=16/8=2.

协作缓存的目标是为每个缓存节点确定缓存的数据分片数目以使得区域缓存收益最大，即：

∀i,si≤sdata，

(3)

其中,sdata表示数据data所包含的原始数据包数量，si(i=1,2,…,M)表示节点i缓存的编码数据包的数量.

网络节点间的数据传输发生在节点的接触过程中，而节点间的接触往往是间断性的.为了评价网络中节点的缓存能力，本文提出了一个新的度量标准来计算节点在整个网络中的重要程度，该标准不仅表明了节点的连通性，还暗示了节点具有更多的接触时间用于数据传输.

定义4. 节点重要度.将节点的连通性作为衡量节点重要程度的标准并记为I，那么

I=E(TC)/(E(TC)+E(TI))，

(4)

其中,E(TC)为节点与其他节点接触时间的均值，E(TI)为节点与其他节点接触间隔时间的均值.

(5)

(6)

式(6)表明节点间所传输的数据量不能超过该节点缓存的数据总量.因此在接触时间限制条件下，节点i为节点j提供数据而获得的缓存收益为

Bij=E(Uij)=

(7)

3.2 数据分片与编码策略

如果节点在时间T内的每次接触过程中都能够传输最大的数据量，那么在整个传输过程中传输的数据量将是最大的.为了使得每次传输的数据量最大，本文根据节点的接触历史，计算出节点与其他节点接触的最短时间tmin以及最长时间tmax.并以最短时间的均值E(tmin)为单位对数据进行分片，使得每次接触都能够传输数据，并尽可能地利用节点间的接触机会.同时根据节点的tmax与E(tmin)的比值来限定节点的缓存界限，记为CB.因为超过该比值数量的数据包在任何一次接触中都不能传输完成，从而造成缓存资源的浪费.

由于接触时间的限制，本文根据节点的接触历史信息，采用上述的分片大小对数据进行分片处理.如果仅仅简单地将数据分割为多个连续的数据片，那么为了恢复数据就必须收集所有的数据片，而这就会导致赠券收集问题的出现.

假设将数据分割为n个不同的数据片，并且每个数据片被请求者接收到的概率相同，那么数据请求者为了恢复原始数据就必需收集到n个不同的数据包.为了收集n个不同的数据包，数据请求者所需要收集数据包的数目往往远大于原始数据片的数目n.

定理1. 若原始数据具有n个不同数据分片，且每个分片收集到的概率相同，那么恢复数据所需要收集的总数据分片数目为Θ(nlbn).

证明. 假设n个数据片收集到的概率相同，并从收集到i-1个不同的数据分片到i个所需要收集的数据分片数目为ni，比如从收集到0个数据分片到收集到1个不同的数据分片需要收集n1=1个数据分片.现假设节点收集到i-1个不同的数据分片，那该节点收集到的下一个数据分片是第i个不同的数据分片的概率p为

(8)

那么，该数据分片不是第i个的概率q=1-p.因此从第i-1个不同的数据分片到第i个所需要收集的数据片期望为

(9)

那么收集n个不同的数据分片所需要收集的数据分片数目E(n)为

E(n)=E(n1)+E(n2)+…+E(nn)=

n(lbn+o(1)).

(10)

证毕.

为了解决简单分片所带来的问题，本文采用了随机线性网络编码技术.首先，在AP上将数据P分割成大小相同的n个数据包，即P=(p1,p2,…,pn)，并从伽罗瓦域中随机生成编码系数向量集αj=(αj 1,αj 2,…,αj n)，最终计算数据P的随机线性组合：

(11)

然后AP将编码后的数据包发送给数据请求者.通过随机线性网络编码技术，网络中的每个数据包的地位都是等同的，数据请求者只需要收集n个线性无关的数据包就可以恢复原始的数据.

(12)

式(12)又可表示为

(13)

最后可解方程得出原始的数据分片pi(i=1,2,…,n)为

(14)

通过这种编码方式能够有效地减少数据恢复时所需要收集的数据包数量，减少了网络的负载，提高了数据访问的效率.

3.3 缓存节点选择

网络中每个移动节点都维持一张缓存信息表，该信息表记录了网络中的缓存节点信息.缓存信息表包含移动节点ID、节点重要度I、节点缓存边界CB、节点当前缓存的数据量Cached、以及表示数据更新的时间戳t等表项.其可以被定义为一个五元组，即CacheInfoTab=(ID,I,CB,Cached,t).

当网络中2个节点接触时，它们互相交换所维持的缓存信息表，并基于所收到的信息更新各自所维持的信息表.具体地说，节点首先更新本地信息表中的数据信息，然后将接收到的信息表剩余部分与本地信息表进行合并.在合并时以具有较新时间戳的数据条目替换时间戳较早的数据条目.

本文通过贪心算法得到初始缓存节点.首先根据本文提出的节点重要度I对网络节点进行降序排序，然后迭代选取I值最大的节点来缓存数据直到达到该节点的缓存上限值.整个迭代过程一直当达到整个网络的最大缓存代价为止.

本文缓存协议中，移动节点在下面2种情况下有可能成为缓存节点：1)当节点是路由节点或数据请求节点时，将会被动地缓存数据成为缓存节点；2)当节点与具有较低重要性的缓存节点相遇时，将会主动地从该缓存节点获取数据成为新的缓存节点.

路由节点或数据请求节点接收到数据后，将会被动地判断是否缓存数据.如果缓存节点的当前缓存数据量Cached小于所能缓存的最大数据量CB时，该缓存节点就缓存该数据包；反之就舍弃该数据包不进行缓存.由于这种被动缓存节点的节点重要度可能并不高，当网络中具有较高重要度的节点与该缓存节点相遇时，将主动从缓存节点上获取数据进行缓存来提高整体的缓存效益，即缓存数据主动重新分配.

4 实验分析

为了验证本文所述的缓存协议，对其进行了实验仿真.本文实验数据采用了Haggle Project[18]收集的Infocom2006数据，其中包含了节点间接触历史信息：接触节点的信息、接触开始时间以及接触持续的时间.

4.1 实验对比方案

为了证明本文所述缓存协议在协作缓存上的优势，选择了No-Cache策略和Cache-NoFrag策略作为本协议的比较对象.No-Cache即在网络中不提供协作缓存策略，数据请求节点需从AP点获取数据；Cache-NoFrag是指网络中节点提供协作缓存但不对数据进行分片处理.在实验中本文所提出的协议表示为Cache-Frag.从Cache与No-Cache对比反映出缓存对数据访问性能的影响，从Cache-Frag与Cache-NoFrag对比反映出数据分片对数据访问性能的影响，也就是接触时间限制对数据访问的影响.

本文采用的主要性能评估指标有：

1) 交付延迟(delivery delay).定义为从用户请求开始直到接收到完整数据所花费的时间.

2) 缓存命中率(hit ratio).定义为用户的数据请求由缓存节点而非原始内容服务器响应的概率.

4.2 实验结果

1) 缓存代价的影响.

图2表明了缓存代价γ对协作缓存中缓存数据交付延迟以及缓存命中率的影响.从实验结果可知，当节点提供缓存策略时,数据交付延迟随着缓存代价的增加而逐渐降低；缓存命中率则随着缓存代价的增加而上升.同时当缓存代价较小时，这种变化越明显；随着缓存代价逐步增大,这种变化就表现得不够明显.在这种情况下节点间有限的接触机会将是缓存性能提升的一个瓶颈，缓存数据交付时间和缓存命中率并不会因为网络中数据副本的增加而出现显著的变化.因此在接下来的实验中，将限制γ=5来验证容忍延迟时间对缓存性能的影响.

Fig. 2 Performance comparison with different cache cost γ图2 不同缓存代价下的比较

Fig. 3 Performance comparison with different tolerance duration图3 不同容忍时间下的比较

2) 容忍延迟时间的影响.

图3表明了容忍延迟时间对协作缓存中缓存数据交付延迟以及缓存命中率的影响.当将缓存代价限定后，随着容忍延迟的时间从8 ks逐步递增到12 ks时，网络中提供缓存服务比不提供缓存服务的效果要好；而本文所提出的缓存协议比不考虑接触时间限制的缓存协议效果要好.这是因为在Cache-NoFrag中缓存数据作为一个整体存放于某一缓存节点，但由于节点间接触时间的限制使得在一次接触过程中数据无法传输完成，从而限制了缓存性能的提升，浪费了节点的缓存空间.在本文协议中，网络上的缓存数据根据节点间的接触时间分割为多个数据分片存放于多个缓存节点中，这增加了节点获取数据的可能性，有效地利用了节点间的接触机会；同时本文为每个节点确定了缓存上限，合理地利用了节点的缓存空间.

5 总 结

由于节点间的间断性连接以及有限的接触时间的限制,使得传统网络的数据缓存机制不能够在移动机会网络环境中得到有效应用.本文指出了接触时间对协作缓存的影响，并为每个节点确定了缓存边界来限制每个节点的缓存数据量，最后提出了数据分片策略和编码方案，设计了缓存协议，并在实验中验证了该协议能够有效地提高数据访问的效率.本文主要解决接触时间限制情况下的数据分片问题，没有涉及到缓存替换，而缓存替换策略能够更好地提高缓存的效率.本文的下一步工作将考虑如何将缓存替换策略纳入本文提出的缓存协议之中.

[1]Han Ke. Cooperative caching algorithm based on grouping nodes in mobile ad hoc networks[C] //Proc of IEEE Int Conf on Information and Automation. Piscataway, NJ: IEEE, 2010: 1294-1298

[2]Rao A, Kumar P, Chauhan N. Energy efficient dynamic group caching in mobile ad hoc networks for improving data accessibility[C] //Proc of Int Conf on Recent Trends in Information Technology. Piscataway, NJ: IEEE, 2012: 372-376

[3]Gao Wei, Cao Guohong, Iyengar A, et al. Supporting cooperative caching in disruption tolerant networks[C] //Proc of the 31st Int Conf on Distributed Computing Systems. Piscataway, NJ: IEEE, 2011: 151-161

[4]Liu Waixi, Yu Shunzheng, Cai Jun. Scheme for cooperative caching in ICN[J]. Journal of Software, 2013, 24(8): 1947-1962 (in Chinese)(刘外喜, 余顺争, 蔡君. ICN中的一种协作缓存机制[J]. 软件学报, 2013, 24(8): 1947-1962)

[5]Wei Dongsheng, Zhu Konglin, Wang Xin. Fairness-aware cooperative caching scheme for mobile social networks[C] //Proc of IEEE Int Conf on Communications. Piscataway, NJ: IEEE, 2014: 2484-2489

[6]Dong Lili, Wang Yong, Dong Yongqiang. Collaborative cache management strategy based on ant-colony replacement algorithm in named data networking[J]. Telecommunications Science, 2014, 30(9): 45-52 (in Chinese)(董利利, 王勇, 董永强. NDN中基于蚁群替换算法的邻居协作缓存管理策略[J]. 电信科学, 2014, 30(9): 45-52)

[7]Hu Qian, Wu Muqing, Liu Hongbao. Distributed cooperative caching strategy in content centric networking[J]. Journal of Beijing University of Posts and Telecommunications, 2015, 38(2): 98-103 (in Chinese)(胡骞, 武穆清, 刘红宝. 内容中心网络中基于分布式协作的缓存策略[J]. 北京邮电大学学报, 2015, 38(2): 98-103)

[8]Luo Xi, An Ying, Wang Jianxin, et al. Cooperative caching mechanism with content migration in content-centric networking[J]. Journal of Electronics and Information Technology, 2015, 37(11): 2790-2794 (in Chinese)(罗熹, 安莹, 王建新, 等. 内容中心网络中基于内容迁移的协作缓存机制[J]. 电子与信息学报, 2015, 37(11): 2790-2794)

[9]Nuggehalli P, Srinivasan V, Chiasserini C F. Energy-efficient caching strategies in ad hoc wireless networks[C] //Proc of the 4th ACM Int Symp on Mobile Ad Hoc Networking & Computing. New York: ACM, 2003: 25-34

[10]Tang Bin, Gupta H, Das S. Benefit-based data caching in ad hoc networks[J]. IEEE Trans on Mobile Computing, 2008, 7(3): 289-304

[11]Niu Xinzheng, She Kun, Qin Ke, et al. A cooperative caching optimized policy of mobile peer-to-peer networks[J]. Journal of Computer Research and Development, 2008, 45(4): 656-665 (in Chinese)(牛新征, 佘堃, 秦科, 等. 移动P2P网络的协作缓存优化策略[J]. 计算机研究与发展, 2008, 45(4): 656-665)

[12]Zhuo Xuejun, Li Qinghua, Cao Guohong, et al. Social-based cooperative caching in DTNs: A contact duration aware approach[C] //Proc of the 8th IEEE Int Conf on Mobile Ad-Hoc and Sensor Systems. Piscataway, NJ: IEEE, 2011: 92-101

[13]Neto J B P, Lima M M, Mota E, et al. Adaptive contact volume prediction in delay tolerant networks[C] //Proc of the IEEE Symp on Computers and Communications. Piscataway, NJ: IEEE, 2013: 372-376

[14]Gao Wei, Li Qinghua, Zhao Bo, et al. Multicasting in delay tolerant networks: A social network perspective[C] //Proc of the 10th ACM Int Symp on Mobile Ad Hoc Networking and Computing. New York: ACM, 2009: 299-308

[15]Conan V, Leguay, J, Friedman T. Characterizing pairwise inter-contact patterns in delay tolerant networks[C] //Proc of the 1st Int Conf on Autonomic Computing and Communication Systems. Brussels, Belgium: ICST, 2007: No.19

[16]Wang Wei, Srinivasan V, Motani M. Adaptive contact probing mechanisms for delay tolerant applications[C] //Proc of the 13th Annual ACM Int Conf on Mobile Computing and Networking. New York: ACM, 2007: 230-241

[17]Chaintreau A, Hui Pan, Crowcroft J, et al. Pocket switched networks: Real-world mobility and its consequences for opportunistic forwarding, UCAM-CL-TR-617[R]. Cambridge, UK: University of Cambridge Computer Laboratory, 2005

[18]Lab for Communications and Applications, EPFL. Haggle Project[OL]. [2016-05-08]. http://ica1www.epfl.ch/haggle/