机会网络中一种低缓存占用的Epidemic路由算法

左成章，刘智虎，孙希胜，索建伟

（重庆邮电大学移动通信技术重庆市重点实验室，重庆 400065）

机会网络中一种低缓存占用的Epidemic路由算法

左成章，刘智虎，孙希胜，索建伟

（重庆邮电大学移动通信技术重庆市重点实验室，重庆 400065）

由于机会网络中节点的缓存空间有限，容易导致数据分组丢失和时延增加。针对部分数据分组已经到达目的节点，但是该类分组仍在网络中其它节点存储、传输问题，提出一种低缓存占用的Epidemic路由算法（RBER）。该算法通过SV运算进行节点缓存清理，从而避免这类冗余数据分组对缓存的占用。理论分析和仿真结果表明，该机制能够降低网络开销、数据分组的发送和缓存占用。

机会网络；路由算法；缓存；清理

机会网络(Opportunistic Networks)[1]是一种不需要源节点和目的节点之间存在完整路径，利用节点移动带来的相遇机会实现网络通信的自组织网络。网络拓扑结构频繁改变，不能保证连通性，信息源节点与目的节点之间不一定存在传输路径。在机会网络路由算法中，应用和研究较为广泛的是基于复制的路由算法。在机会网络中为了能够有效的进行数据的传输，“存储-携带-转发”的路由模式成为优先考虑的一种机制。在这种机制中，节点在收到数据分组时，通常将数据分组存储到本节点，携带着数据分组一起移动，当遇到合适的节点时再将数据分组转发出去。数据分组在节点相遇时被多次的转发，网络中存在多个数据分组的副本。

其中，最为典型的算法就是Epidemic路由算法[2]。该算法因其较高的投递率和较低的时延特性而备受关注。但是，该算法类似于泛洪机制，对网络资源的要求比较高，在苛刻的机会网络环境中，算法性能的提升受到限制。

为此，本文提出一种低缓存占用的Epidemic路由（RBER，Reduce Buffer overhead based Epidemic Routing）算法，通过优先删除目的地址为对方节点的数据分组，减少了网络中数据分组副本的扩散，降低网络资源开销，提高缓存利用率。

1 相关工作

Harras等提出了Controlled Flooding路由算法[3]。该算法假定每个节点只知道自身以及自己携带的消息信息，并且能够完全自主作出转发决策。该算法通过意愿概率、生存时间 (TTS，Time-To-Send)和死亡时间(TTL，Time-To-Live)3个参数来控制消息泛洪。此外，通过广播免疫信息来及时删除已达目的节点的数据分组。该算法在保证可靠投递的同时减少了网络开销。

Epidemic路由算法是一种基于洪泛策略和复制的路由协议。每一个携带数据的节点都将数据的副本传递给它所遇到的未带有该消息节点，通过“存储-携带-转发”逐跳传递将消息送达目的节点。每个节点维护一个摘要矢量(SV，Summary Vector)，当两个节点能够连接时通过交换消息向量来彼此交换较少的消息。经过一段时间，网络中的每个节点将接收到所有的消息。优点是不需要额外的拓扑控制信息，同时可以取得高的消息投递率和低的端到端时延，无需对链路状态进行预测与估计，实施起来较为简单。缺点是网络中存在大量的冗余副本将导致节点能耗增加和缓存溢出，进而导致网络的资源利用率低和网络性能下降。

MRRMR(Message Redundancy Removal of Multi-copy Routing)算法[4]在ER算法的基础上为每一个网络节点增加一个相遇计数器。该计数器记录节点遇到的带有相同消息拷贝的不同节点的数目。如果计数器的值达到了所设置的门限值，则节点将该消息拷贝从缓存中移除，并且之后不再接收该消息拷贝。通过设置合理的门限值，可以在保证消息投递成功率和不增加控制分组开销的同时，将冗余拷贝高效的控制在一个相对低的水平并且可以显著减少节点缓存占用。但是，由于节点移动的随机性，合理门限值的选定比较困难。并且，消息拷贝的过早移除，还会导致传输时延的增加。

文献[5]提出n-epidemic路由算法，仅当节点当前拥有的邻居节点个数达到一个特定的门限值时，才进行数据传输，这就可以使用较少的传输次数获取较多的接收，减少数据传输次数。但是，由于未能充分利用节点之间短暂的相遇机会，导致数据分组不能及时传递，投递时延增加。

2 Epidemic路由算法

Epidemic算法中，每个移动节点都设有一个缓存区用于存储数据。注入网络中的每一个数据分组都有一个全局标识符，节点以该标识符为键值，为缓存中所有的数据分组建立了一张哈希索引表。同时，节点还维护一个一维比特数组，即SV用于标示该节点当前缓存中的数据分组存储情况。节点周期性的广播Hello消息进行邻居发现，某一时刻，节点X和节点Y相遇，其数据交互过程如图1所示。

图1 Epidemic算法数据交互过程

（1）节点X向节点Y发送摘要矢量SVX，告知节点Y节点X当前缓存中存有的数据分组。

（2）节点Y收到SVX后，通过与自己保存的SVY作如下位运算：

通过上述运算，节点Y获得节点X缓存中有而本身没有的数据分组信息，并向节点X发送RequestX控制分组来请求这些数据分组。

（3）节点X收到RequestX后，向节点Y发送对应的请求分组。

（4）节点Y收到数据分组后，更新自己的SVY。此外，若该数据分组的目的地址为自己，则将其上传至应用层；否则，放入自己的缓存中，进行存储、转发。

上述4个过程以X、Y两个节点为例，描述了网络中节点间数据分组的传输过程。

3 RBER路由算法

RBER算法通过对SV信息运算进行节点缓存清理的具体操作如下。

当节点X收到节点Y发送的SVY，进行如下位运算：

矢量SVZ显示的是节点X、Y都存有的数据分组。

节点X遍历SVZ中显示的数据分组，查询各数据分组所对应的目的节点是否为Y，如果是，则删除该数据分组（节点Y中已存有该分组副本，即该分组已达目的节点Y，无需在网络中继续扩散）并且更新其分组已达信息列表ReachX；从而达到清理节点缓存、减少存储开销和资源消耗的效果。

RBER算法通过Request控制分组实现分组已达信息通告的具体操作如下：

（1）当节点X收到节点Y发送的SVY，进行如下位运算：

比特矢量RequestX显示的是节点Y中存有而节点X中没有的数据分组信息。

（2）节点X之后做如下位运算：

节点X发送RequestX’，其中包含了待请求的数据分组信息以及部分分组到达信息。该机制能够在未增加控制开销的条件下，实现分组已达信息的通告，提高缓存管理效率，降低网络开销和缓存占用。

4 仿真结果及分析

采用OPNET 14.5软件进行建模和仿真，在相同的仿真条件下，从网络开销、数据分组发送次数以及平均缓存占用等方面，将RBER算法与Epidemic算法进行性能比较与分析。

4.1 仿真场景设置

设置100个节点在1 500 m×600 m的矩形范围内采用Random Waypoint运动模型移动。随机选择其中的55个节点作为中间转发节点，其余的45个节点产生数据分组，其中每个节点产生44个数据分组分别发往其它44个节点，总计1 980个数据分组。每个数据分组大小为1 KB，数据分组产生间隔为1 s。节点通信半径为10 m、25 m、50 m、75 m、100 m，仿真时间为3 000 s。节点缓存大小为3 000 KB，最大数据速率为54 Mbit/s，移动速度v∈[1，19](m/s)。

4.2 仿真结果分析

仿真中主要从网络开销、数据分组发送次数、平均缓存占用率等3个性能参数对所提算法的性能进行评估。

4.2.1 网络开销

网络开销是指网络运行时间内，所有节点发送的分组（Hello分组、SV分组、Request分组和数据分组）所包含的总比特数。其值为：

其中，Ctotal为总的网络开销，SH和NH分别对应Hello分组的长度和总的发送个数。同样，SSV和NSV分别对应SV分组的长度和总的发送个数；SR和NR分别对应Request分组的长度和总的发送个数；SD和ND分别对应数据分组的长度和总的发送个数。仿真结果如图2所示。

图2 网络开销对比

由图2可知，随着通信范围的增大，节点相遇机会和相遇持续时间都会增加，导致各算法中相应的操作和网络开销增加。RBER算法的网络开销在各个场景都略低于Epidemic算法，这是由于RBER算法引入节点缓存清理机制，删除本地缓存中已经到达目的节点的数据分组，减少了不必要的数据分组在网络中的发送。

4.2.2 数据分组发送次数

节点发送的数据分组包括节点自身产生并发送的数据分组以及为其它节点转发的数据分组。数据分组发送次数是指在网络运行时间内，所有节点发送的数据分组总次数。其值为：

其中，Ntotal为总的数据分组发送次数，NS和NT分别对应节点自身产生并发送的数据分组次数和节点为其它节点转发的数据分组次数。仿真结果如图3所示。

图3 数据分组发送次数对比

由图3可知，RBER算法的数据分组发送次数在各个场景低于ER算法，这是由于RBER算法引入节点缓存清理机制，删除本地缓存中已经到达目的节点的数据分组，减少了不必要的数据分组在网络中的发送。

图4 平均缓存占用对比

4.2.3 平均缓存占用

仿真结果如图4所示。

由图4可知，RBER算法的平均缓存占用在各个场景下都低于Epidemic算法。这是由于RBER算法引入节点缓存清理机制，删除本地缓存中已经到达目的节点的数据分组，减少了不必要的数据分组在网络中的发送，减少这类分组在网络中的传播和其它节点的缓存占用。

[1] PELUSI L, PASSARELLA A, CONTI M, et al. Opportunistic networking: data forwarding in disconnected mobile ad hoc networks[J]. IEEE Communications Magazine, 2006, 44(11): 134-141.

[2] VAHDAT A, BECKER D. Epidemic routing for partially connected ad hoc networks[R]. Technical Report CS-200006, Duke University, 2000.

[3] Harras K A, Almeroth K C, Belding-royer E M. Delay Tolerant Mobile Networks (DTMNs): Controlled Flooding in Sparse Mobile Networks[C]. Proceedings of the 4th International conference on networking. Waterloo: IEEE Press, 2005: 1180-1192.

[4] Yu H Z, Ma J F, Bian H. Message redundancy removal of multicopy routing in delay tolerant MANET[J]. The Journal of China Universities of Posts and Telecommunications, 2011, 18(1): 42-48.

[5] Lu X F, Hui P. An Energy-Efficient n-Epidemic Routing Protocol for Delay Tolerant Networks[A]. 2010 Fifth IEEE International Conference on Networking, Architecture, and Storage[C]. Macau, China, 2010: 341-347.

Kind of reduce buffer overhead Epidemic routing algorithm for opportunistic networks

ZUO Cheng-zhang, LIU Zhi-hu, SUN Xi-sheng, SUO Jian-wei
(Chongqing Key Lab of Mobile Communications Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

To address the problem in opportunistic network that the existing epidemic-mechanism-based routing algorithms incur redundant communication overhead during the transmission of data packets, which is part of the data packets have already arrived at the destination nodes, but the data is still in the network storage and transmission, a kind of reduce buffer overhead Epidemic routing algorithm for opportunistic networks, called RBER was proposed. The algorithm based on SV information operation, to avoid redundant data takes up the cache. Theoretical analysis and simulation results show that the mechanism can reduce network overhead, redundant data packet sending and cache usage.

opportunistic networks; routing algorithm; buffer; clean

TP393

A

1008-5599（2014）02-0085-04

2014-01-01