DTN中基于Epidemic路由的拥塞控制策略研究

汪佩佩 李 涛 王汝传

1(南京邮电大学通信与信息工程学院 江苏 南京 210003)2(南京邮电大学计算机学院 江苏 南京 210003)

0 引 言

DTN，即延迟容忍网络，源自于对行星际通信网络[1]的描述，现在通常指在消息传输过程中不能确保端到端路径的无线网络。DTN网络主要有生态环境监控网络[2]、无线车载自组织网络[3]、PeopleNet[4]等。

DTN网络具有连接间断、节点移动频繁、延迟大、递交率低、存储容量有限等特点[5]，又因为其特殊的传输保管机制，使得该网络极易产生拥塞。因此，有必要针对现有的路由算法，改进相应的拥塞控制策略，从而实现消息更高效率的转发，避免拥塞的产生，以及在拥塞发生后采取合理的缓存管理策略，选择合适的消息丢弃以使拥塞节点获得足够容纳新消息的空间，缓解网络拥塞。

本文在Epidemic路由算法[6]的基础上，给出一种拥塞控制策略RBCCS，从下一跳节点选择和缓存管理策略两个方面入手，避免和缓解网络的拥塞状况。仿真结果显示，RBCCS使DTN网络在消息递交率、平均时延和开销率等网络性能方面的表现均有所提高。

1 相关工作

DTN网络中关于拥塞控制策略的研究可大致分为主动、被动和混合型三类[7]：

主动拥塞控制策略：主动拥塞控制指通过特定的策略控制消息的传输，预防网络发生拥塞。如文献[8]根据节点的的剩余缓存和能量将节点划分为不同的级别，接收消息时根据不同级别采取不同的接收策略,避免节点陷入拥塞。文献[9]则将网络中的消息分为普通消息和特殊消息,其中特殊消息要求更高的传输率。然后根据节点的拥塞程度将节点状态分为三个等级,每个节点根据自己所处的等级和消息的情况自主决策消息的接收行为，实现了更好的网络性能。

被动拥塞控制策略：当拥塞发生时采取一定的丢包策略来减轻节点负载，缓解或消除网络的拥塞情况。如文献[10]提出了一种基于效用值的缓冲管理策略(UBM)，UBM根据节点的兴趣和消息的投递概率计算出消息的效用值，然后基于该效用值提出整体缓冲管理策略， 实现通过较小的网络成本获得更高的传输率和更低的延迟。文献[11]提出根据节点的本地知识，计算出消息的权重，基于消息权重的丢包策略。文献[12]针对多播类型的DTN网络提出的基于效用函数的丢弃和调度策略。

混合型拥塞控制策略：混合型拥塞控制将主动与被动型拥塞控制相结合。如文献[13]根据节点在运动过程中所获得的一些历史信息,以直接获取及间接推荐的方式准确地感知网络中各个节点的拥塞状态,进而以分布式的方式动态地为数据选择中继节点,达到更加合理地利用有限的网络资源以及避免和缓解网络的拥塞情况的目的。文献[14]提出一种采用机器学习技术的框架Smart-DTN-CC，该框架中节点从环境获得输入(例如其缓存占用，邻居集等)，并且基于这些信息，从一组将要执行的行动集中选择要采取的行动。然后根据采取的行动在拥塞控制方面的有效性给予该动作相应激励，以期最大限度地提高整体激励，从而最大限度地减少拥塞。

2 Epidemic路由

Epidemic路由算法是由Vahdat等首次提出的。在Epidemic路由中，节点通过周期性地广播Hello消息来发现在其通信范围内的邻居节点，在与邻居节点通信时，节点不进行路由决策，而是将消息副本洪泛至所有的邻居节点。该路由算法为网络中的每一个消息维持一个全局标识符(ID)，用于在整个网络中唯一标识该消息。节点以消息ID为键，对消息进行哈希运算后以键值对的形式存储，并用一个摘要矢量SV(summary vector)标识哈希表中每一个消息的“有”或“无”。若节点有某消息，则SV对应位置为1，否则为0。某一时刻，节点A和节点B进行通信的过程如图1所示。

图1 Epidemic路由数据通信过程

(1) 节点A向节点B发送A的摘要矢量SVA，告诉B自己缓存中有哪些消息；

(2) B收到SVA后执行运算:

Request=SVA&(～SVB)

(1)

Request为节点A缓存中有而节点B缓存中没有的消息的矢量，然后B将Request发往A；

(3) 节点A收到Request后，按要求逐个发送消息给节点B；

(4) 节点B收到请求的消息后，更新SVB。若B收到的消息中有目的节点是自己的，就将其上传应用层并从缓存中丢弃。

3 拥塞控制策略RBCCS

3.1 下一跳节点的选择策略

Epidemic 路由没有对下一跳节点加以选择，而是向所有在传播范围内的邻居节点洪泛消息副本。但是由于DTN网络节点的移动性强、通信范围有限以及消息发送时延大等特点，导致发送机会十分宝贵，盲目洪泛会浪费有限的网络资源。另外，DTN网络的节点缓存空间通常是有限的，一旦缓存被占满后就会产生拥塞，网络中较多节点陷入拥塞将使网络陷入传输瓶颈，大大降低网络性能。

因此，RBCCS提出一种下一跳节点的选择策略。该策略采用一个参数缓存空闲率BC作为下一跳节点选择的依据，其定义如下：

(2)

式中：Bfree表示节点的剩余缓存大小，Binit表示节点初始化时的缓存大小。缓存空闲率大，则表示该节点在拥塞前能接收的消息越多。在选择下一跳节点时以本节点BC为选择阈值，只将消息发送到BC值大于该阈值的邻居节点，若邻居节点的BC均小于该阈值，就放弃本次机会。

3.2 缓存管理策略

传统的缓存管理策略主要有以下几种：DLA(Drop-Largest)，丢弃缓存中最大的消息；DLR(Drop-Least-Recently-Received)，丢弃在缓存中存在时间最长的消息；DO(Drop-Oldest)，丢弃缓存中在网络中存在时间最久的消息；DY(Drop-Youn- gest)，丢弃剩余生存时间最长的消息。它们大都只考虑到消息的单一属性，简单而片面,具有一定的局限性。

RBCCS提出的缓存管理策略则综合考虑消息的生存时间TTL、已转发次数和被当前节点接收的时刻，给出综合度量三者的一种归一化参数，即消息冗余度MR：

(3)

式中：TTL表示消息的生存时间，TTLinit表示消息的初始化生存时间,Fc表示消息M已经被转发的次数，Fmax是网络中消息被转发的最大次数，Tr为消息被当前节点接收的时刻，Ts为仿真的总时长。w1、w2和w3分别表示上述三个元素对于MR的权重大小，w1+w2+w3=1。TTL和Tr越小、Fc越大的消息在网络中存在的时间越长，已被传送给网络中较多的节点，则其在网络中的副本数也越多，已被成功递交到目的节点的概率也越高，因此该消息的冗余度也越大。当节点陷入拥塞时，RBCCS策略会率先丢弃冗余度大的消息，以释放节点缓存。

权重的大小决定了消息各属性在决定冗余度时所占的比例，为权衡各属性的利弊，经大量仿真实验确定，当w1=0.15、w2=0.35、w3=0.50时，所得效果最好。

4 仿真结果及分析

4.1 仿真环境设置

ONE[15-16](Opportunistic Network Environment) 是基于Java语言的一款专门用于DTN网络路由仿真的工具。本文采用ONE分别在Epidemic路由算法基础上对DLA、DLR、DO和RBCCS拥塞控制策略进行仿真，以评估各种拥塞控制策略对DTN网络性能指标的影响。仿真采用自带的赫尔辛基市地图，节点类型全部为行人，运动模型采用基于地图最短路径模型。具体参数设置如表1所示。

表1 仿真参数设置

4.2 结果分析

为了能更好地分析上述几种拥塞控制策略对DTN网络的影响，需要采用一些合理的网络性能指标进行评估。本文主要采用消息递交率、开销率和平均时延三个指标来判断应用各种拥塞控制策略时DTN网络的性能。

(1) 消息递交率:

(4)

消息递交率表示网络中成功递交的消息总数与生成的消息总数的比值。式(4)中，Delivered为成功递交到目的节点的消息总数，Created为网络中生成的消息总数。图2显示当仿真时间固定为12 h，节点数固定为100，节点缓存大小从5～50 MB不等时几种策略的消息递交率。

图2 不同缓存大小时的消息递交率

由图2可知，RBCCS和DO策略在递交率上的表现优于另外两种传统策略。当缓存小于15 MB时，RBCCS与DO策略差别不大，这是因为缓存较小时，节点能携带的消息个数较少，RBCCS的缓存管理策略效果有限。缓存较大时，节点能存储携带的消息数增加，拥塞时如何从缓存中选择合适的消息丢弃更加重要。当缓存为50 MB时，RBCCS的递交率相对最好的DO策略提升了15.8%。这是因为RBCCS综合考虑了消息的生存时间、接收时刻和已转发次数这三个属性，给出了消息冗余度的概念，更加合理地评估了消息在网络中冗余的程度。优先丢弃冗余度高的消息，可以得到更好地消息递交率。另外，RBCCS增加了下一跳节点选择策略，优先将消息发送到缓存空闲率较大的邻居节点上，也能有效避免节点的拥塞。

(2) 开销率：

(5)

开销率表示网络中为了成功递交消息而额外转发的消息总数与成功递交的消息总数的比值，该参数越小则消息转发效率越高。式(5)中，Relayed表示消息被中间节点转发的总转发次数，Delivered表示网络中被成功递交到目的节点的消息总数。

图3表示不同节点数时的网络开销率。从图中可以看出，RBCCS策略的总体表现更好，缓存为50M时，相对表现最好的DO策略更是降低了14.4%。 这是因为RBCCS对下一跳节点加以决策，避免盲目地洪泛消息副本，减少了消息总体的转发次数。又在缓存管理策略上加入对消息已转发次数的考虑，已转发次数越多的消息冗余度越大，越优先被丢弃，所以网络整体的开销率有所下降。

图3 不同缓存大小时的网络开销率

(3) 平均时延：

(6)

平均时延表示所有成功递交的消息从源节点到目的节点花费的平均时间。式(6)中,tid为消息i被目的节点接收到的时刻，tis为消息i在源节点生成的时刻，n为网络中成功递交到目的节点的消息总数。

由图4可知，RBCCS的平均时延较另外几种传统策略也有所下降，相对表现最佳的DLA策略仍能下降6.8%左右。这是因为RBCCS加入的下一跳节点选择策略会将消息递交给缓存空闲率更大的节点，避免了一些可能发生的拥塞情况，所以因拥塞产生的排队消息数会减少，从而减少了消息的排队时延。而且RBCCS在拥塞发生后的缓存管理策略中，会将消息生存时间小、接收时刻早以及已转发次数较多的消息优先丢弃。这类消息在缓存中排队的时间往往更长，故而RBCCS在平均时延方面也颇具优势。

图4 不同缓存大小时的平均时延

5 结 语

本文基于Epidemic路由算法给出一种拥塞控制策略RBCCS，从消息下一跳节点选择和缓存管理策略两方面进行改进。节点与邻居节点进行通信时，只将消息投递给缓存空闲率大于自身的邻居节点，不再盲目地洪泛。 当节点发生拥塞时，综合考虑消息的生存时间、已转发次数和被节点接收时刻计算出消息冗余度，优先丢弃冗余度大的消息，缓解拥塞情况。仿真结果表明，相较于几种传统的拥塞控制策略，RBCSS能使消息递交率提升15.8%，平均时延降低6.8%，网络开销降低14.4%。但该策略在计算消息各属性对于消息冗余度的权重时，采用的是从大量仿真结果中筛选的方法，工作量较大，因此下一步的研究工作是采用一种合理的分析方法，用理论分析计算和仿真实验相结合的方法得出权重的取值比例。