命名数据网络中利用缓存决策的PAWF策略*

叶小琴，　杨　震，　鲜　敏，　赵　丽

(1.四川省装备制造业机器人应用技术工程实验室，四川 德阳 618000;2.山西大学 软件学院，山西 太原 030013)

命名数据网络(named data networking，NDN)[1]在未来互联网的信息中心架构和无线自组织网络方面具有非常广阔的前景.NDN的特点是对易错信道和时变拓扑结构进行广播，然而，现有的转发策略对NDN网络性能造成了诸多不利影响[2]，需要考虑新的NDN转发准则以应对无线链路和节点移动性问题.有文献提出了主动式转发[3]，就是各节点周期性地通过网络传输来控制数据包.每一个数据发送请求都能迅速地获取源节点与目的地节点之间的路由.然而，这种持续主动的传输方式不适用于移动节点，且会导致大量的信息开销.在反应式转发中，节点在需要时才会传输其控制的数据包，这样就可以节约更多带宽.但是在路由发送数据之前，节点不得不等待相当长的一段时间才能对该路由进行评估.盲目转发(blind forwarding，BF)方式[4]，则是通过一种最简单的拓扑结构未知策略，以解决低效广播风暴问题，但是BF策略仅采用包监听和延迟定时器以支撑多条转发，虽然能够减少广播风暴的发生率，但是不能消除拥堵和冗余度[5].因此，本文提出了利用缓存决策技术的提供商感知转发(provider aware forwarding，PAWF)策略，该策略在转发决策过程中利用一个或多个内容来源的额外信息，即在转发中融合了兴趣/数据包的额外字段，而在额外字段中携带了准提供商的信息，使得提供商信息位于网络的每个节点，并基于该额外信息做出最终转发决策.仿真结果表明，PAWF可以进一步提高NDN信息传送的性能.

1　提供商感知转发策略

PAWF是一种基于先侦后播(listen first broadcast later，LFBL)[6]和E-CHANET策略的方法.LFBL最初的设计目的是作为多跳无线网络的一种转发策略，此处的多跳无线网络采用数据为中心的寻址方式，并没有对NDN体系结构进行具体参考，即在最初的文献中并没有提到NDN表，包括转发信息库(forwarding information base，FIB)、内容存储(content store，CS)以及待定兴趣表(pending interest table，PIT).唯一的强制性数据结构是距离表(distance table，DT)，距离表中记录了每个节点和通信端点间的距离信息[7].LFBL有三种包类型：数据请求REQ、数据回应REP，以及确认应答ACK.数据检索步骤为：首先，在网络中利用控制洪泛策略传送REQ以发现可利用的提供商；然后，用户选取一个提供商，并生成ACK包确认；最后，采用基于距离的转发策略确认每个中间节点是否通过检查其DT转发后续REQ.类似地，在E-CHANET中也采用了一种基于距离的转发策略.与LFBL方法不同的是，E-CHANET中参考了NDN的体系结构.

如图1所示，给出了PAWF的主要处理过程.PAWF采用了LFBL和E-CHANET策略的主要原理，在BF机制上进行设计，并且融合了其他的NDN模型(缓存和数据结构).除了传统的NDN表之外，网络中每个节点均保存DT、提供商标识符(provider identifier，ID)和跳距离.根据分层NDN命名策略，假设一组常见的数据内容如视频、文本或图像等，与一个唯一的持久层次名称如视频Trip/Alice 2016相关联.而该给定的内容可以划分成多个碎片，这些碎片分布在多个数据包之中，对这些数据包进行连续编号，如视频Trip/Alice 2016/0、视频Trip/Alice 2016/1等.用户C对第一个有兴趣即进行视频Trip/Alice 2016/0传播请求，并且根据BF策略在网络中对其进行散播.提供商P接收到这个请求，则以应答数据包进行回复，数据包含有两个额外的字段以传输唯一ID，并且将跳距离初始化为1.一旦节点接收到数据，则每个维护PIT条目的节点N在DT过程中存储整体数据内容的名称、视频Trip/Alice 2016、P的标识符和到节点的距离.然后，N增加一条距离字段，并且通过计算TData的延迟时间周期性地对数据进行重新广播.接收到数据之后，用户在其DT中包含了提供商的信息，并且通过将提供商ID和到用户的距离包含到兴趣包中进行发送.利用Tinterest和TData的时间值分别表示兴趣和数据的重播事件.由于NDN通信的局部多跳特性，可以发现多个提供商，用户C能够在这些提供商中选取距离自身最近的提供商.每个中间节点接收到兴趣之后对DT进行检查，这是为了验证该中间节点到提供商的距离是否小于用户到提供商的距离.如果验证结果为真，则对距离字段进行更新，并计算出Tinterest的延迟时间以对兴趣进行广播.利用延迟窗口DW随机地计算出Tinterest和TData，并利用一个整数表示时间间隔的长度，计算过程如下：

TData=rand[0,DW-1]-Ts,Tinterest=(DW+rand[0,DW])·Ts,

式中Ts延迟时隙表示一个较短的时间间隔.在不相交的间隔中选取Tinterest和TData，通过Tinterest>TData可以获取对数据包的较高存取优先级.TData对提供商来说就是一个拥堵避免定时器，而Tinterest对于转发者来说是一个拥堵避免定时器，利用Tinterest可以进行兴趣抑制.

PAWF采用了网络中缓存决策技术，从而提高数据传输性能，一个保存了数据缓存副本的中间节点N能够回应请求，且过程并不需要将兴趣转发给选取的提供商.

考虑N个节点和L个链路组成的NDN.网络拓扑可使用无向图G={N,L}表示，N={1,2,…,N},L={1,2,…,L}.令γk为链路k的数据传输率，k∈L，令F表示流量，则有

式中ρi,j表示节点i与j之间利用PAWF转发的路径，第i个节点的权重ωi定义为：

此外，在PAWF中还采用了一种额外特征，允许用户知晓一些数据包或者所有数据内容，但前提是这个节点位于其CS之中.如果节点N拥有所有数据内容或者所有内容的缓存，则将其标识符放置到数据包中，这样用户C即能够选其为提供商完成后续的请求.如果节点N仅存储了部分的数据内容，则这个节点就将最初提供商的ID包含在数据包中，以避免用户错误地将这个节点选作为提供商.如果节点的DT之中并不存在任何提供商的ID信息，那么节点N在其相关字段中不指定任何提供商，用户C不对其DT中的信息进行更新.如果提供商没有在指定的时间内对兴趣进行回复，则用户认为这个提供商不可到达，然后在其DT之中选取其他的提供商作为其提供商.如果DT之中不存在任何的信息，那么用户C重新开始盲目转发.

可见，PAWF有助于减少冗余度，而且由于存在隐含终端，PAWF不会完全阻止数据副本的存在，这些数据副本可以提高传送的鲁棒性.

2　仿真实验及结果

为了对所提出的策略设计方法的性能进行测试和比较，需要采用一个仿真框架，这个仿真框架可以对一个NDN节点的数据结构即CS、PIT和FIB进行复制，仿真框架中构思的转发策略需建立在IEEE 802.11之上，并且可以使用户在不同的无线场景中移动.本文采用NDN软件模块，即ndnSIM[8]，这是一种最近发布的面向ns-3的网络仿真，仿真环境遵从NDN通信模型，从而能够确保获取精确的试验结果以及可再现性.实验基于上述仿真环境对BF与PAWF两种转发策略的性能进行比较.

实验采用的仿真场景环境为：Nn个配备有IEEE 802.11g接口的移动节点通过模拟拓扑结构中的多条路径进行通信，这些节点采用Levy-Walk模型以行人行走的速度移动.将这些节点的一个子集和NC个节点作为用户，每个用户都发出不同的内容初始化请求，每个内容存储在单个提供商中.提供商放置在尺寸为600 m×600 m的模拟拓扑结构中.每个节点采用的传输和接收设置中，名义上的覆盖半径为150 m，并通过瑞利衰落分布对传播过程进行建模以模拟信道衰减.

实验选择在不同流量负载条件下对BF和PAWF策略的性能进行比较，其中用户个数NC在2和20之间变化，拓扑结构中的节点个数选取Nn=60、120.如图2所示，网络中流量负载的增加对BF策略的性能产生了较大的影响，随着NC的增加，BF完成时间大幅度增加，在节点密集场景中完成时间变得更长.PAWF的完成时间随着NC的增加而变化不大，且在节点密集场景时完成时间也没有大幅增长.因此，相比于BF策略，PAWF策略拥有更短的完成时间.

节点密度的变化会影响两个策略的数据冗余度[9].如图3所示，当节点密度增加时，可以观察到BF和PAWF策略数据冗余度的值均有增加，但是BF策略增加得更为明显，这是由于潜在转发者的个数增大，BF需要处理更多的内容请求；而节点密度的变化对PAWF策略几乎没有产生任何的影响，这是因为PAWF策略试图在用户和提供商之间设置一个单一的路径，避免了大量的内容请求.因此，相比于BF策略，PAWF策略具有较低的数据冗余.

[1]周芸韬. 基于MQAAR的移动自组织网络路由方案[J]. 湘潭大学自然科学学报, 2016, 38(3): 69-73.

[2]QIAO X, NAN G, PENG Y, et al. NDNBrowser: an extended web browser for named data networking [J]. Journal of Network & Computer Applications, 2015, 50(6): 134-147.

[3]黄绍城, 马林华, 宋博,等. 基于QOS的MPR优化选择算法[J]. 计算机仿真, 2015, 32(7):281-285.

[4]LANDICHO J A. VOISEE COMMUNICATOR: An android mobile application for hearing-impaired and blind communications[J]. International Journal of Interactive Mobile Technologies,2016, 10(4): 22-26.

[5]杨静, 龚玲玲, 杨正川,等. 带有模糊控制的机会网络数据转发控制策略[J]. 系统工程与电子技术, 2016, 38(2): 392-399.

[6]AMADEO M, CAMPOLO C, MOLINARO A, et al. Content-centric wireless networking: A survey[J]. Computer Networks, 2014, 72(7): 1-13.

[7]DELAYE A, LEE K. A flexible framework for online document segmentation by pairwise stroke distance learning[J]. Pattern Recognition, 2015, 48(4): 1197-1210.

[8]刘总真, 葛敬国, 唐海娜,等. 命名数据网络中面向移动用户的内容预取方法[J]. 计算机应用研究, 2016, 33(5): 1441-1445.

[9]陈树, 韩进, 蒋伟. 低冗余度WSN非均匀分簇算法应用研究[J]. 计算机工程, 2014, 40(8): 10-14.