基于效用的机会网络缓存替换策略∗

周盼，张振宇

(新疆大学 信息科学与工程学院，新疆 乌鲁木齐830046)

0 引言

随着无线自组网应用的快速发展，出现了大量短距离、低成本、智能化的无线通信设备，这些无线设备在一定的网络环境下能够进行接触，机会网络[1]是利用移动节点之间的逐跳转发将数据从源节点传输到目标节点.由于节点密度较低和节点移动不可预测性，机会网络不会一直处于连通状态，且难以维持端到端的通信链路，机会网络的数据传输采用了“存储-携带-转发”的方式.同时，机会网络存在网络资源紧张、移动节点存储空间的局限性，因此移动节点间的协作缓存显得十分重要.

由于机会网络中数据传输延迟较大，其在网络中滞留的时间很长，而移动节点存在缓冲区资源有限等特点，从而在数据量传输较大的情况下很容易产生节点缓存区溢出和缓存数据过期的情况.这将导致网络中的存储空间会被很快消耗掉，使得节点有限的缓存空间矛盾比传统移动自组网环境下更为突出.因此，当节点缓存空间满时，如何设计相应的缓存替换策略是一个关键问题.

在研究缓存替换策略时，要解决的问题就是网络中的哪些节点应该缓存数据，以及这些节点应该缓存什么样的数据.目前已经有许多基于无线自组网络环境下提出的缓存替换研究工作：文献[2]提出了FloodCache，其基本思想是利用有限的洪泛来查找附近节点是否缓存有其所需的数据项，从而避免频繁远程访问，利用较高的通信代价来降低数据延迟，该策略主要用于对数据延迟要求较高的多媒体应用；文献[3]提出一种可量测的缓存一致性校验的策略，并相应地对缓存数据替换成本做了评估；文献[4]考虑到利用节点间的协作关系来避免单个节点缓存有限的问题，并据此设计了一种相应的缓存替换策略；文献[5]提出了Greedy-Dual-Size，该策略同时考虑了本地数据的成本、大小和延迟.然而大多数现有的缓存替换策略研究是以数据的相关访问信息作为替换标准，如访问次数、最后一次访问时间、数据项尺寸大小等作为标准来对数据项替换策略进行设计，而对于数据的流行度考虑不够，并未将其列为重要因素进行设计.目前针对机会网络的节点缓存替换策略研究比较少，才刚刚开始起步，文献[6]提出一种基于相遇节点和目标节点之间平均接触频率的策略，并采用了基于消息副本数量的删除策略；文献[7]提出一个分布式算法，使用统计学估计全局的网络信息；文献[8]提出了PSEPHOS，其基本思想是对可能缓存的数据进行“投票”，将“投票”最高的内容分布式的放入缓存，对于网络中每个数据项，数据所缓存的位置是要通过缓存替换策略来进行动态调整.

传统的无线自组网中的缓存替换策略不能有效的解决机会网络中数据缓存问题，虽然目前已有机会网络缓存替换策略研究，然而绝大多数的策略并未讨论数据的流行度和机会路径[9,10].结合机会网络的特点，作者设计了一个基于效用的缓存替换策略，可以更好地解决节点的缓存空间紧张问题.

1 缓存设计

首先详细说明基本设计思路，随后讨论了实现方面具体涉及的问题.本文基于数据项的效用值这一标准来对数据进行替换，通过流行度和机会路径这两个指标算出数据的效用值.

1.1 数据流行度

数据流行度是一个概率估计，是基于在T1−TK时间内对数据有K个请求，假设这种情况下的数据请求是遵循泊松分布的一个参数，并且数据的流行度被定义为在数据过期之前，数据在将来有再一次被请求的概率.如果di在te时间内过期，它的流行度ωi=1−e−λd(te−tk)，要计算ωi，一个节点只需要递归的维持已发生数据请求的两个时间值，并可以忽略不计空间上的开销.

1.2 机会路径

首先定义机会接触图G=(V,E)，机会路径PAB=(VP,EP),节点A和B之前包括一个节点集合V P={A,N1,N2,Nr−1,···,B}∈V，边集EP={e1,e2,···,er}∈E，边权重{λ1,λ2,···,λ3}，PAB(T)是在T时间内数据机会的从节点A传输到B的概率.节点Nk和Nk+1在PAB上的间接触时间Xk遵循指数分布的概率密度函数因此，从A到B的传输时间遵循亚指数分布其中系数为机会路径为

1.3 基本策略

当两个缓存节点A和B接触时，机会的发生缓存替换，两个节点通过交换缓存数据来优化所累计的数据访问延迟，并制定以下缓存策略：

公式(1)表示替换后数据di是否被分别缓存在节点A和节点B中，Si表示数据di的大小，SA和SB是A和B的缓存大小，µi=ωi.pA和νi=ωi.pB表示数据di在节点A和B的缓存性能的效用值，ωi是数据di的流行度，PA和PB表示距离目的节点最短机会路径.假设PA>PB，节点A优先从选择池S中选择数据缓存，之后节点B缓存S中剩下的数据，通过以上公式，此问题能够使用动态规划方法解决.

1.4 概率选择算法

在缓存替换过程中，缓存数据的删除基于流行数据优先，但可能削弱数据的可达性.数据可达性并不是随着网络中缓存副本数量增加而呈线性增加.具体来说，如果缓存数据的副本数量从1增加到2，数据可达性将大大增加，但如果是从10增加到11，数据可达性增加的会很少，例如数据d1的流行度很高，它就有可能在网络中其他地方缓存许多副本，数据d2的流行度很低，在缓存替换中容易被删除，删除会造成数据d2不可获取， 如何控制副本的数量也是要解决的问题.

缓存替换策略只优化了两个接触的缓存节点在本地范围内的数据访问延迟.机会网络中，全局范围优化具有挑战性，因为维持网络中的缓存数据副本的数量是很困难的，从而提出了一个概率策略来控制全局范围的缓存数据的副本数量.通过提出概率策略，在缓存选择中，我们仍然优先考虑效用值高的流行数据，同时确保低流行度的数据能有机会被缓存.以下为概率数据选择算法

2 实验结果与分析

用本文提出的缓存替换策略(CRPBOU)与传统的缓存替换策略FIFO、LRU和GreedyDualSize相比较，我们使用了MATLAB做仿真，在800m×400m的矩形区域里随机放置了50个移动节点,节点的移动模式符合随机停靠点模型,两个移动之间移动节点停留5s，移动节点的移动速度为0～20m/s，每个移动节点的信道带宽为2Mbps，MAC层为蓝牙，每个节点对数据项的访问服从Zipf分布,θ=0181.实验分别基于节点的缓存大小为2MB、3MB、4MB、5MB、6MB、7MB、8MB、9MB、10MB的情况对性能指标进行测试.

缓存成功率的比较：图1反映了各种算法在不同缓存下缓存成功率，当数据比较小和缓存空间比较紧张时，缓存替换不会很频繁的进行.因此，传统的缓存替换策略成功率只比本文提出的策略低10%∼20%.然而，随着缓存变大，如在缓存大小为5M时，其缓存成功率比LRU高出约12%，比FIFO高出约14%左右，而在缓存大小为10M时CRPBOU缓存成功率比LRU与FIFO分别约高出18%∼20%，与GreedyDualSize相比性能大约提高5%∼8%.

缓存数据访问延时的比较：图2反映了各种算法数据访问延时.随着缓存大小不断增加时，LRU、FIFO和GreedyDualSize的数据访问延迟也不断的增加，而CRPBOU则基本没有太大的波动.

缓存数据替换次数的比较：图3反映了各种算法数据替换次数.CRPBOU的数据替换次数介于LRU和FIFO之间，随着缓存变大，数据替换逐步递减，CRPBOU在数据替换次数上没有GreedyDualSize出色，但是仍然高于FIFO和LRU.

图1 缓存成功率比较

图2 缓存数据访问延时比较

图3 缓存数据替换次数比较

3 结论

目前机会网络受到了广大研究者的关注，并且在国外已出现了一些基于机会网络的具体应用[11,12].本文对机会网络中缓存替换策略进行了深入研究，现有大多数缓存替换策略并未考虑节点流行度和机会路径.与之不同的是，本文针对机会网络中缓存空间不足，提出一个基于效用的概率缓存替换策略，仿真数据分析表明与目前常用缓存替换策略相比，表现出对机会网络数据通信特点具有良好的适应能力，能够有效地提高数据项的缓存命中率，并降低端到端的数据访问延迟.