移动Ad Hoc网络下协作缓存策略研究

蒋 泉，潘沛生

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

0 引 言

移动自组织网络[1](mobile Ad Hoc networks,MANET)，是一种与传统的有基站网络相对的无中心移动网络，MANET网络可以应用在无法架设基础设施或者基础设施昂贵的环境中，因此，开展MANET的研究具有很高的科学价值，同时也能够产生较好的社会经济效益。目前，国内外对于MANET的研究重心大多放在动态路由协议的开发上。例如，Maheswary A等[2]提出在路由协议中添加加密信件来确保MANET路由协议的安全；Dodke S等[3]研究了无线自组网按需平面向量协议(Ad Hoc on-demand distance vector routing,AODV)[4]和动态源路由协议(dynamic source routing,DSR)[5],在不同节点密度的条件下，对比了两者在端到端延迟、能耗以及数据包传递率等性能上的优劣。

作为MANET网络的最终目的，保持移动节点对数据的访问能力，保证网络中数据的可用性，依然是研究MANET网络的重要内容。协作缓存[6],允许在多个节点间共享和协调缓存数据，以提高Web性能。由于无线连接的成本不同于有线连接，所以决定在哪缓存数据，如何获得缓存数据将是研究MANET缓存的重要部分。

文中对支持MANET数据访问的协作缓存放置策略及发现策略进行设计和评估。提出了两种基本的缓存放置方案：Data-Cache、Path-Cache，然后根据两种基本缓存方案提出一种集基本方案优势于一身的Adaptive缓存放置方案；同时，也将对已有的COOP缓存策略[7]进行改进优化，引入核心节点的概念，以降低缓存发现的响应延迟和能量损耗，提高网络吞吐量。

1 Adaptive缓存策略

1.1 系统模型

图1显示了自组织网络的一部分，其中的一些移动节点具有类似于卫星网络中连接其他网络的外部接口。这些接口可用作网关，允许其他节点与外部网络进行通信。数据中心可以驻留在MANET内部或者外部，移动节点可以从数据中心读取数据。

图1 MANET网络系统模型

在MANET网络中，当节点发出一个数据请求时，一般会通过多跳的方式传到数据中心，由数据中心发回所需要的数据包。AODV、目标序列距离路由矢量算法(destination sequenced distance vector，DSDV)[8]是适用于MANET网络的两种底层路由协议，它们可以在路由层寻找到达目的节点的最佳路径，尽可能减少带宽损耗和访问延迟，但是本身也会存在一些限制。为此，提出两种基本的协作缓存方案：Data-Cache和Path-Cache。

1.2 基本协作缓存

Data-Cache是指节点缓存流经该节点中流行度较高的数据项。根据图1，假设N6和N7先后向数据中心请求了数据项di，在响应过程中都经过了节点N5，N5判断此数据项当前的流行度较高，于是缓存在本地。此后如果N3、N4或者N5有同样的请求，就可以直接由N5来服务。在数据项到达时，节点会首先判断数据项的流行度，再决定是否缓存，但是无论在何种情况下，请求节点本身都是会缓存所请求的数据项。

Path-Cache的思想同样可以用图1的模型来说明。节点N1向数据中心请求了数据项di，在数据源发回数据包时经过节点N3，如果N3缓存了节点N1的路径，此后若N2请求di时，N3可以计算出其距离数据中心有三跳而距离N1只有短短的一跳(AODV和DSR等都具有计算源节点到目的节点跳数的功能)，这样N3就会响应N1，从而节省了带宽和延迟。当网络拓扑相对稳定，数据更新率较低时，假设节点与请求节点的距离用H(i,j)表示，与数据中心的距离用H(i,C)表示，H(i,j)应该小于H(i,C)，表示如下:

Hsave=H(i,C)-H(i,j)

(1)

其中，Hsave为减少的跳数，系统的阈值称为TH，Hsave在大于TH时可以选择Path-Cache方案。

每个从数据中心发出的数据项都会被分配一个生存时间值[9](time to live，TTL)，并且使用TTL方案来保持客户端缓存和数据中心缓存的一致性。只要缓存时间未超过TTL值，数据项就被认为是有效的。

1.3 Adaptive缓存算法

Data-Cache和Path-Cache都只能适用于一种特殊的MANET环境，当面临它们不擅长的环境时，基本方案不仅发挥不了它们的优势，有时更是适得其反，增加了网络的拥塞，降低网络的吞吐量，增加了查询延迟和能量损耗。

为此，在结合两种基本缓存方案优势的基础上，提出了一种Adaptive缓存放置策略。该策略的思想为，当数据项到达节点时，该节点可以动态地依据某些标准来采用Data-Cache方案或者Path-Cache方案，或者是不进行缓存而转发。这些标准应该包括数据项的大小Si，TTL持续时间TTLi以及Hsave。系统会分配给每个节点有关这三个标准的阈值[10]，分别为：Ts，TTTL，TH。

由此，提出了Adaptive缓存放置算法，见图2。

图2 Adaptive算法流程

2 E-COOP缓存策略

在缓存系统中，有一种常用的缓存发现策略是Hop-by-Hop策略，当数据请求在被转发至数据中心的过程中，转发节点先检查其本地的缓存，如果转发节点本地有该请求的缓存，则响应请求节点，否则，继续转发至数据中心。但是随着请求节点与数据中心的跳数增加，网络连接的可靠性和吞吐量将会下降。而COOP缓存发现策略，利用了兴趣局部性原理，即相邻节点间可能存在同样的需求，请求节点先以限制性洪泛法在其邻居节点中查找数据，如果没有，再以Hop-by-Hop的方案查找。E-COOP缓存发现策略是对COOP缓存发现策略的改进，它不仅发挥了协作缓存提取数据的优势，更是引入了核心节点，提高缓存的发现效率。

COOP方案中节点的协作区域由1-Hop范围内的邻节点组成。其执行过程如下：请求节点发出请求，若本地缓存持有请求数据，则会直接响应；否则请求节点在1-Hop区域内广播请求信息；如果请求数据不在协作区域内，请求节点进行Hop-by-Hop方案将请求消息发往数据中心。

2.1 E-COOP系统架构

E-COOP系统架构如图3所示，它驻留在网络层与应用层之间，为应用层的用户请求和网络层的通信提供代理作用。

图3 E-COOP系统架构

E-COOP的执行过程如下：当节点发出一个数据请求时，其先在本地缓存中查找，如果本地缓存能够提取数据，则用户直接访问，否则，请求节点在协作区域内广播数据请求，如果数据不在协作区域内，请求信息以Hop-by-Hop方案转发至数据中心。如果在转发过程中，节点为核心节点，则查询该节点1-Hop范围内邻节点的缓存目录，发现请求数据时，响应请求节点并停止转发。

2.2 核心节点选择模型

假设V={v1,v2,…,vN}是MANET网络中节点的集合，λuv为节点u和节点v之间最短路径的条数，λuv(ω)为从节点u到节点v最短路径且经过节点w∈V的条数。节点w∈V的重要程度为：

(2)

其中，Ew为节点w剩余的能量；γ为大于等于0的常数，对于能量敏感的MANET网络，γ的值可以设得较大。一个节点的重要程度越大，说明这个节点可以以相对短的路径到达其他节点并且这个节点的剩余能量相对较高。

在MANET中，每个节点都可以获取其一跳范围内的其他邻节点信息(通过周期性的请求数据包获得)，包括周围节点所持有的数据项ID、数据项的TTL值、节点的剩余能量等。节点会周期性计算周围节点和本节点的重要程度K，如果本节点与周围其他节点相比重要度较大，则该节点是核心节点，否则为普通节点。

2.3 E-COOP缓存替换策略

由于缓存空间的有限性，当一个新的数据项要被缓存，而缓存空间不足时，必然要有旧的缓存被踢出，缓存替换策略[11]就是研究如何替换旧的缓存。缓存替换的目的是增加系统缓存的命中率，这很大程度上取决于缓存的容量，对于协作缓存而言，缓存替换考虑的不仅仅是本地缓存的命中率，而是整个MANET缓存系统。因此，E-COOP缓存替换策略试着减少协作区域中缓存数据的副本数量，从而最优化缓存系统。由于在Adaptive缓存放置算法中，当节点需要缓存的数据项事先存在于节点时，节点只会更新其TTL值而不会实际再次缓存数据副本，这样做的好处之一就是节省了缓存控件，减少冗余。

E-COOP策略会将缓存数据标记为主要副本和次要副本。当节点获取到数据时，如果该数据来自协作区域以外，则该数据标记为主要副本。否则，如果该数据来自协作区域内，需要进一步考虑其主次性：如果在之前的请求，该数据已经被标记为主要副本，考虑到减少副本的数量，所以这次的请求标记其为次要副本。另一方面，该数据前一次请求时被标记为次要副本，则本次请求被标记为主要副本。E-COOP区分缓存数据的原因是减少缓存缺失的成本，跟随节点的流行趋势而应需缓存。E-COOP缓存替换执行过程如下：(1)当缓存空间满时，先踢出空间中的次要副本，如果剩余空间能够满足新的缓存数据，则进行缓存，否则进入(2)；(2)节点为每个缓存空间中的主要副本i计算成本函数cost(i)，如下：

(3)

其中，Si为数据项i的大小;TTLi为数据项的生存值;Tkth-access为主要副本i第k次被访问的时间戳。

选择cost(i)值最大的副本进行替换。将该副本被替换的消息发送给核心节点，由核心节点更新1-Hop邻节点缓存目录。

3 仿真与性能分析

在Linux平台上使用NS-2[12]仿真器中的CMU无线扩展模型[13]进行网络仿真，仿真区域为500 m×1 500 m，50个节点在区域内随机移动，节点移动速度范围在0～20 m/s，信道的带宽为2 Mb/s，节点的通信范围为250 m，无线传播模型为Two Ray Ground，节点采用全向天线(OmniAntenna)，队列为PriQueue，底层路由协议为AODV，MAC层协议为IEEE802.11[14]，数据项的大小范围在1～10 KB之间，邻节点范围为1-Hop。Adaptive缓存的阈值设置为：TH=2，Ts=4.4，TTTL=5 000(阈值根据相同环境仿真得来)。

客户端访问模型基于Zifp-like[15]函数，每个节点产生一个可读查询，产生时间服从均值为Tquery的指数分布。Zifp-like经常用来模拟不均匀的分布模型，在Zifp-like模型中，节点缓存第i(1≤i≤n)个来访数据项的概率遵循：

(4)

其中，n为数据中心的第n个数据项，当θ=1时，访问模型遵循严格的Zipf分布，当θ=0时，访问模型遵循均匀分布，θ越大，分布函数越“扭曲”。

从图4可以看出，随着缓存空间的增大，所有方案的平均延迟都会减小，因为缓存空间可以存储更多的数据项，在请求发往数据中心的过程中，更加容易命中，所以响应的延迟就会缩短。同时，由于引入核心节点，E-COOP缓存策略要优于其他三种方案。E-COOP与COOP缓存策略两条曲线近似平行，说明在E-COOP缓存策略中引入核心节点，缓存系统整体平均延迟有所降低，而并非在特定的某个点。

图4 平均响应延迟的比较

从图5可以看出，缓存空间越大，能量的消耗就越小，因为节点可以缓存更多的数据项，高概率地在本节点或者转发节点处获得请求数据。同时，E-COOP缓存策略能耗低于COOP缓存策略的能耗，前者的响应延迟又比后者低，所以经过仿真表明，E-COOP缓存策略的确比现有的COOP缓存策略更具有优越性。

图5 平均能耗的比较

4 结束语

Adaptive缓存放置策略很好地结合了Data-Cache以及Path-Cache的优势，同时规避了它们的缺点，在缓存放置方面，充分考虑了相邻节点可能具有相同需求的实际情况，各移动节点相互协作，数据共享，推进整体网络性能的提升，其中包括网络吞吐量的提升、链路断裂概率的降低等。E-COOP缓存发现策略在现有的COOP缓存发现策略的基础上引进了核心节点，提升普通节点发现请求数据的概率。在保证不增加能量的前提下，尽可能地降低缓存发现的延迟。同时，E-COOP缓存替换策略通过减少数据项副本的方法，减少冗余，提高请求响应效率。两种方案相结合，在缓存放置和发现过程都充分利用了邻节点资源，提升了移动Ad Hoc网络的缓存性能。

参考文献：

[1] 张 鹏,孙 磊,崔 勇，等.移动自组网安全技术研究[J].计算机科学,2009,36(7):1-7.

[2] MAHESWARY A,BASKAR S.Letter to shape encryption for securing MANET routing protocols[C]//IEEE international conference on computational intelligence and computing research.Chennai,India:IEEE,2016.

[3] DODKE S,MANE P B,VANJALE M S.A survey on energy efficient routing protocol for MANET[C]//2nd international conference on applied and theoretical computing and communication technology.Bangalore,India:IEEE,2016:160-164.

[4] 王忠恒,张曦煌.移动Ad Hoc网络AODV路由协议的改进[J].计算机应用,2010,30(2):333-336.

[5] 王北光,李立新,谢 涛.移动Ad Hoc网络DSR路由协议的改进[J].计算机技术与发展,2011,21(8):121-124.

[6] 刘银龙,汪 敏,马 伟,等.PSP缓存系统中总开销最小

的协作缓存策略[J].通信学报,2015,36(3):86-93.

[7] DU Yu,GUPTA S K S.COOP:a cooperative caching service in MANETs[C]//Joint international conference on autonomic and autonomous systems and international conference on networking and services.Papeete,Tahiti,French Polynesia:IEEE，2005.

[8] 许重球,李腊元.MANET典型路由协议的性能分析与仿真[J].计算机工程,2008,34(12):97-99.

[9] KARAULIA D S,BHAROT N.Dynamic TTL variance foretelling based enhancement of AODV routing protocol in MANET[C]//Fourth International conference on communication system and network technologies.Bhopal,India:IEEE,2014:244-248.

[10] YIN Liangzhong,CAO Guohong.Supporting cooperative ca-ching in Ad Hoc networks[J].IEEE Transactions on Mobile Computing,2006,5(1):77-89.

[11] 杨春贵,吴产乐,彭鸿雁.一种有效的Web代理缓存替换算法[J].计算机工程,2007,33(3):43-44.

[12] 陈亚军,肖建华.基于NS-2的网络仿真与扩展[J].计算机系统应用,2005,14(5):84-87.

[13] 王 辉.NS-2网络模拟器的原理和应用[M].西安:西北工业大学出版社,2008.

[14] 李 浩,高泽华,高 峰,等.IEEE802.11无线局域网标准研究[J].计算机应用研究,2009,26(5):1616-1620.

[15] 游荣彦.Zipf定律与汉字字频分布[J].中文信息学报,2000,14(3):60-65.