延时容忍网络中基于内容的信息传播机制研究

彭 涛

0 引言

延时容忍网络(Delay-tolerant Network)在搜救和战场等环境中有着广泛的应用，是移动自组织网络（Mobile Ad Hoc Network）的一个重要分支。延时容忍网络是一种受限的移动自组织网络，这种网络模型具有网络拓扑高度变化、网络分割、节点能力受限等特点。和众多自组织网络一样，延时容忍网络中的核心问题是路由，即信息传播机制。移动自组织网络中，没有中心节点，每个节点既充当终端节点，又充当中继节点。随着移动自组织网络中节点的移动，网络拓扑也会随时变动，而且会出现网络分割。这就构成了延时容忍网络和传统移动自组织网络的最大区别。在延时容忍网络中，节点间端到端的通信路径并不存在，或者只是短时间存在，因此，要完成信息的传播，需要借助其它节点的存储转发。

在延时容忍网络中，传统的存储转发路由协议如OLSR、AODV、DSR，并不能有效运作。因为在这些路由协议中，当信息下一跳的节点不可达时，中继节点会将所获得的信息抛弃。然而，在延迟容忍网络中，不能保证信息传播完整路径的存在，这就是这些路由协议在延时容忍网络中应用的一大障碍。针对这个问题，一种常见的解决方法是采用存储携带转发机制代替存储转发机制，在存储携带转发机制中，节点会保存它转发的信息直到下一跳节点可达，再将信息转发给下一跳节点。这种改进措施利用了节点的移动性来弥补网络分割带来的挑战，它将时间因素和网络拓扑因素进行了综合的考虑，利用不同时间存在的子路径来构造端到端的完整通信路径，从而为信息的传播提供了途径。

然而，在延时容忍网络中，由于节点能力的限制，其存储能力一般是较小的，因此如何决定是否对某个信息进行存储携带仍然是一个问题。对这个问题，Epidemic[1]协议中每个节点对于它所收到的信息均进行存储，当遇到其它节点时，再将这些信息进行简单的广播。这种解决方案带来的好处是通信延时较小，然而其付出的通信和存储开销是巨大的，而且它会带来广播风暴，可扩展性不好。因此 Epidemic协议在延时容忍网络中并不实用。

另外一种解决方案是OCBD[2]协议，在这个协议中，每个信息具有一个标识，用来表示信息的种类。在网络中，一些节点作为信息产生源，另一些节点会对某些种类的信息感兴趣。这样一来，信息的源节点和目的节点完成了解耦合，这样信息的传播将不再是基于目的节点的地址，而是基于信息的内容。在该协议中，每个节点定时的广播它所存储的信息的标识，只有在遇到信息的目的节点时才进行信息的转发。这样的好处是能将信息传播的开销降低，但是所付出的代价是通信延时很大，因为它没有利用其它节点的中继功能，而只是利用节点之间的移动。

针对以上不足，提出了一种基于内容的信息传播机制，综合利用了延时容忍网络中的节点移动和存储携带转发功能，从而获得较低的通信延时以及信息开销。并通过对比试验对该机制有效性进行验证，为实际应用提供参考。

1 实现原理

1.1 节点模型

每个节点具有移动能力，能够在一定区域内自主运动。同时，它们具有通信能力，能够和一定范围内的临近节点进行通信。此外，每个节点具有一定的存储能力，能够维护一些需要的数据或者接收的信息。每个节点维护3个位数组，分别是：Iinterest、Ihave和NeighInterest。Iinterest表示当前节点对哪些信息感兴趣，这个信息由算法初始阶段指定。Ihave表示当前节点存储了哪些信息，一个节点所存储的信息包括由它自己产生的信息和它所接收到的信息组成。NeighInterest表示当前节点维护的邻居节点对哪些信息感兴趣，这个位数组的内容不断的更新，它用来记录临近节点对哪些信息感兴趣，为是否接收某种类型的信息提供判断依据。

1.2 运动模型

在移动通信网络中，节点的移动模型往往对网络通信的性能有着较大的影响，因此，如何选取切合实际的运动模型显得很重要。本文中采用了由Johnson 和 Maltz[3]首先提出的随机点移动模型。这个模型自提出以来，由于其模型简单且具有很广的应用范围，很快成为评估移动自组织网络协议的一个基准模型。随机点移动模型是一个基于随机过程的运动模型，它描述了网络中每个节点的位置、速度和运动方向的变换过程。

具体来说，随机点移动模型中。每个节点首先随机的选取一个位置作为当前运动的目的节点，然后以的速度 V运动到该选定的位置。速度V是随机选取的，它的值满足从0到Vmax的平均分布，Vmax为允许的最大速度值。当到达选定的点后，节点重复上述过程。在该模型中，每个节点的速度和方向是独立选取的，从而保证了整个移动模型的随机性。

1.3 算法描述

本文所提出的基于内容的信息传播机制包括以下 4个步骤：

步骤1：广播查询信息。每个节点在运动的同时，会以一定频率广播信息。广播的信息包括Iinterest和Ihave 位数组，它们表示当前节点所感兴趣的信息种类和当前节点所存储了的信息种类。

步骤2：发送请求。当一个节点收到它邻居节点广播的查询信息时，它首先会将自己的 Iinterest位数组和收到的Ihave 位数组进行比较，从而决定向邻居节点请求那些对方存储了并且自己感兴趣的信息。另一方面，它会检查它的NeighInterest位数组，如果其中包含某个标识，该节点会以一定的概率P向邻居节点请求该信息。概率P为一个固定值，它的取值影响了信息传播的延时和开销，在本文中，其值取为1/2。由以上两种情况来构造请求信息，同时，节点会根据收到的Ihave对自身的NeighInterest进行更新。

步骤3：处理请求。当一个节点收到它邻居节点的请求信息时，它采用广播方式将被请求的信息广播给邻居节点。采用广播方式的好处是，其它邻居节点可以通过旁听的方式来获得它们所感兴趣的信息，而不用每次都自己请求，从而减少了信息通信的开销。

步骤4：处理收到的信息。当一个节点收到它邻居节点广播的信息时，它首先对那些它自己感兴趣的信息进行存储，并相应的清除 Ihave 位数组中的位，表示该信息已经完成传播。另外，对那些不是自身感兴趣的信息，节点会根据信息的跳数N来决定是否存储，存储的概率为1/2N。

2 实验及结果分析

2.1 目标参数

在本节中，以Epidemic和OCBD协议为参考对象，从以下两方面对提出的基于内容的信息传播机制进行验证分析：

(1)信息延时。信息从源节点到达目的节点的平均耗时，它代表了信息传播机制的有效性。

(2)平均存储开销。所有节点存储信息的总量与节点数目的比值，这个数据表示了信息传播过程中的平均开销。

2.2 实验设定

本实验在NS-2仿真器下完成，采用和Xin Wang[4]以及Feng Li[5]类似的实验场景，在一个2000米乘2000米的场景中，有100个随机移动的节点。每个节点的通信范围为100米，实验中采用的具体参数设定，如表1所示：

表1 实验参数设定

实验开始时，随机选择30个节点作为信息源节点，它们分别产生30种信息，总共900种信息。另外随机选择30个节点作为信息目的节点，每个目的节点对60种信息感兴趣，实验时间为6000秒。

2.3 实验结果和分析

实验分为两组，第一组实验中，每个节点的存储空间无限，以此来对基于内容的信息传播机制的传播延时和信息开销进行评估。另一组的实验中，每个节点的存储空间是有限的，以此来观察基于内容的信息传播机制在实际应用中的有效性。实验结果，如图1、图2所示：

图1 信息延时随模拟时间的变化曲线

图2 平均存储开销随模拟时间的变化曲线

从图1和图2可以看出，Epidemic协议具有最好的传播延时，这主要是因为在该协议中，每个节点保存了所以它受到的信息，因而每个节点都作为信息的中继节点。但同时，它的平均存储开销是另外两个协议的上百倍。OCBD协议在平均存储开销上和基于内容的传播机制差不多，但是在信息延时长多了大致一半。综上所述，本文提出的基于内容的信息传播机制，利用较小的信息存储空间，使得通信延迟获得了较大的提升，如图3所示：

图3 平均存储开销随模拟时间的变化曲线

第二组实验中，由于存储空间的限制，Epidemic协议根据如何选择丢弃的信息可以分为两种类型，一种是先进先出Epidemic协议，即当存储空间满时，丢弃最先存储的信息。另一种采用随机丢弃方法。从图3中可以看出，基于内容的信息传播机制在通信延迟方面较 OCBD有较大的提升，和Epidemic协议相当。

3 结束语

本文采用基于内容的信息传播机制解决延时容忍网络中的通信问题。利用了网络中节点的移动能力，采用存储携带转发机制，克服了网络拓扑变化带来的网络分割问题。通过和Epidemic协议和OCBD协议的对比实验，可以发现，本文提出的基于内容的信息传播机制在通信延时和平均存储开销方面有所提升。下一步，本课题将结合之前的工作[6]在真实机器人平台上应用该基于内容的信息传播机制，从而验证该机制的可行性。

[1]Abdelmajid Khelil, Christian Becker, Jing Tian, Kurt Rothermel. [G]An Epidemic Model for Information Diffusion in MANETs. MSWiM, 2002.

[2]Carzaniga A., Rembert A. J, and Wolf A. L. Understanding content-based routing schemes. [M]Technical Report,University of Lugano, 2006.

[3]Broch, J; Maltz DA, Johnson DB, Hu Y-C, and Jetcheva J. A performance comparison of multi-hop wireless ad hoc network routing protocols. [C]Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom98).

[4]Xin Wang, Yantai Shu, Zhigang Jin, Qingfen Pan. Adaptive Randomized Epidemic Routing for Disruption Tolerant Networks. [G]2009 Fifth International Conference on Mobile Ad-hoc and Sensor Networks, 2009.

[5]Feng Li and Jie Wu. MOPS: Providing Content-Based Service in Disruption-Tolerant Networks. [C]ICDCS,2009.

[6]Jiang Chao, Peng Tao, Alei Liang, Haibing Guan."An Improved Content-based Data Dissemination In Human Contact-Based Network", The 7th International Conference on Mobile Ad-hoc and Sensor Networks, [C]Beijing, China, December 16-18, 2011.