基于缓冲区占用率的DTN散发等待路由算法

马蓓蕾，王贵竹，朱妍娟，丁安平

（安徽大学计算智能与信号处理教育部重点实验室，合肥230039）

基于缓冲区占用率的DTN散发等待路由算法

马蓓蕾，王贵竹，朱妍娟，丁安平

（安徽大学计算智能与信号处理教育部重点实验室，合肥230039）

传统容滞网络散发等待路由算法的节点副本数是确定的，使得获得节点的转发次数具有一定的盲目性，不能很好地适应网络环境，降低了递交率。针对该问题，研究节点的最终平均缓冲区占用率和副本数的关系，提出一种基于缓冲区占用率的路由算法。该算法由节点的最终平均缓冲区占用率动态调整初始化副本数。在节点的最终平均缓冲区占用率较低的情况下，增大报文的初始化副本数，以提高递交率，在节点的最终平均缓冲区占用率较高的情况下，减小报文的初始化副本数，以避免拥塞的发生。仿真结果表明，与二分法散发等待路由算法相比，当网络中节点的平均缓存占用率较低时，该算法能改善递交率和降低网络平均延时。当网络中节点的平均缓存占用率较高时，在改进递交率的同时，能降低整个网络的开销。

容滞网络；路由；散发等待；缓冲区占用率；副本数

1 概述

容滞网络（Delay Tolerant Network，DTN）［1-2］，是一种位于区域网络（各种不同类型的网络，包括因特网）之上的覆盖网［3］，以克服受限网络环境下频繁的网络断开、高延迟和异构性［4］等问题。由于容滞网络中端到端的路径可能是不存在的，传统的路由算法将不再适合这种新型的网络结构。容滞网络采用存储-携带-转发［5］的方式来进行报文的转发。在这个网络中节点是稀疏的，因此，节点在递交报文之前需要将报文存储一段时间，通过节点的移动将报文转发给其他中继节点［6］或信宿节点。

本文根据节点移动模式和活动性的差异，提出一种基于缓冲区占用率的自适应散发等待路由算

法，动态更新初始化副本数。

2 相关工作

DTN中节点是随机移动的，节点间的连接是不可预知的，因此，DTN是一个机会网络［7］。节点间将通过机会连接来实现报文的转发。DTN采用多拷贝路由机制［8］来增加报文被递交到信宿节点的概率及减小延迟。其中，DTN多拷贝路由中最具代表性的路由协议有：蔓延（Epidemic）路由［9］，概率路由［10］及散发等待（Spray and Wait，SAW）路由［11］。

二分散发等待（Binary Spray and Wait，BSW）路由协议中，节点每次转发自身报文副本数的一半给相遇节点，只有遇到信宿节点时才会转发此报文。

但二分散发等待路由协议报文的初始化副本数是一定的，具有盲目性。本文提出最终平均缓冲区占用率的概念，并提出基于缓冲区占用率的散发等待路由算法，与二分法散发等待路由算法相比更能够适应网络环境的变化。

3 散发等待路由算法

散发等待路由中的初始化副本数都是确定的，所以，节点在生成报文时有一定的盲目性。首先要通过当前节点与历史相遇节点的缓冲区占用率来计算当前节点的最终平均缓冲区占用率。然后根据节点的最终平均缓冲区占用率调节报文的初始化副本数：当节点的最终平均缓冲区占用率比较低时，应该增加报文的初始化副本数，以提高整个网络的递交率，降低平均时延；而在节点的最终平均缓冲区占用率比较高时，应该减少此节点生成的报文的初始化副本数，提高网络的递交率，减少网络开销率。

基于缓冲区占用率的散发等待路由（Spray and Wait Routing Concerned on Buffer Occupancy，SAWBO）算法分为3步：

（1）每次相遇时，节点更新列表。

（2）计算当前节点的最终平均缓冲区占用率。

（3）根据节点的最终平均缓冲区利用率，计算节点的生成报文的初始化副本数散发报文。

3.1 节点记录相遇节点的列表

每个节点都有一个记录，每个记录有很多列表，这个列表里面有3个属性值：节点ID，节点的平均缓冲区利用率和相遇时间。

当每次节点相遇时，节点根据以下 3步更新记录：

（1）在初始化时，每一节点的列表中为空。每次节点相遇，计算当前节点最终缓冲区占用率并更新到列表中。

（2）当两节点 A，B相遇，则比较两节点的节点列表：

1）A，B节点列表中，节点ID不同的，分别补充到A，B节点列表中。

2）A，B节点列表中，节点ID相同的，保留更新时间较近的节点信息。

（3）节点会丢弃超时的节点信息（例如2 h外），因此，每个节点就记录着在一段时间内相遇的所有节点的列表。

3.2 参数计算

在每次相遇时，首先把相遇节点的列表更新到当前节点的记录中，丢弃相遇时间在2 h之外的节点列表。列表中的平均缓冲区占用率的计算如下：

（1）相遇时间在2 h～0.5 h之内的列表个数为m，缓冲区占用率为 β′，那么计算2 h内节点的平均缓冲区占用率Aνgm，如式（1）所示：

（2）相遇时间在0.5 h之内的列表个数 n，缓冲区占用率为β″，那么计算2 h内节点的平均缓冲区占用率Aνgn，如式（2）所示：

（3）计算当前节点的最终平均缓冲区占用率Aνg，如式（3）所示：

其中，0.5＜α＜1，把0.5 h内的记录作为着重的参考指标来考虑。

每次相遇当前节点计算最终平均缓冲区占用率，把当前节点相遇时间和最终平均缓冲区占用率更新到相遇节点的记录中，相遇节点也是如此更新记录。

最终平均缓冲区占用率是更新当前节点的生成报文的初始化拷贝份数的重要指标。在最终平均缓冲区占用率低时，认为当前节点缓冲区空闲。

3.3 参数之间的关系

在缓冲区空闲时，应该迅速增加二分法散发等待路由的初始化副本数，使得缓冲区得到充分利用，则在节点的最终平均缓冲区占用率低时，快速增大初始化副本数。在缓冲区忙碌时，应该减少二分法散发等待路由的初始化副本数，释放缓冲区的空间，于是在节点的平均缓冲区利用率低时，使得初始化副本数快速减少来减少拥塞。在缓冲区占用率极高时，副本数减少到一定程度就不再减少了，以保持报文的递交率。

假设节点的报文的初始化副本数为L，关系图如

图1所示。

图1 初始化副本数与节点平均缓冲区占用率的关系

由图1可知（0＜P＜q＜1）：

（1）当节点的最终平均缓冲区占用率 Aνg≤P时，节点的初始化副本数迅速增加到 a×L（a＞1），这时缓冲区占用率比较低，需要增加副本数会提高递交率，并且降低平均延迟。

（2）当节点的最终平均缓冲区占用率P≤Aνg＜q时，节点的初始化副本数迅速降低到b×L，这时缓冲区占用率比较高，减少副本数会提高递交率，且降低网络开销。

（3）当节点的最终平均缓冲区占用率q≤Aνg＜1时，这时缓冲区占用率极高，为了保证递交率，同时在一定程度上抑制报文数，把节点的报文生成的初始化副本数稳定在b×L（0＜b＜1）。

4 仿真结果与分析

4.1 仿真参数设置

本文使用THE ONE（The Opportunistic Network Environment Simulator）［12］仿真器对方案进行仿真。其中，通过仿真发现，BSW中在副本数L=16仿真效果最好，SAW-BO中在P=0.8，q=0.95，a=4，b=0.25，仿真效果最优。本文采用的是的随机路点（Random Waypoint）模型。地图大小为1 000 m× 1 000 m，共放置了100个节点，这些节点只有1个组。在报文生成间隔为1 s和30 s时分别做了仿真。具体参数如表1所示。

表1 仿真环境参数

在上述仿真环境下，分别比较报文生成间隔为30 s和1 s时，Epidem ic，BSW及本文算法在报文递交率、平均延迟及网络开销率上随时间的变化情况：

（1）递交率：递交成功的报文数量与总的投递报文数量的比值。

（2）平均延迟：递交成功的所有报文从源节点到信宿节点的时间之和与总的报文个数之比。

（3）开销率：被中继的报文与成功递交的报文之差再与成功递交的报文之比。

4.2 结果分析

4.2.1 报文生成间隔为30 s的仿真结果

从图2可以看出，报文生成间隔为30 s时，本文算法的递交率最高。由于报文生成的慢，缓冲区比较空闲，因此本文算法增加报文的副本数，从而使报文在节点之间传输的次数变高，提高了递交率。

图2 报文生成间隔为30 s时递交率随时间的变化

从图3可以看出，报文生成间隔为30 s时，本文算法的平均时延最低。此时大部分节点的最终缓冲区占用率较低，本文算法会增加报文的副本数，此时，报文转发的可能性增加，导致网络中报文递交的平均延迟比较小。

图3 报文生成间隔为30 s时平均延迟随时间的变化

从图4可以看出，报文生成间隔为30 s时，本文算法的开销率介于Epidemic与BSW之间。因为这

时网络中大部分节点的缓冲区比较空闲，本文算法会增加报文的副本数，增大了开销率，但报文转发次数比Epidemic少，所以本文算法的开销率比BSW大，比Epidemic小。

图4 报文生成间隔为30 s时开销率随时间的变化

在网络中节点分布均匀时，本文算法通过更改节点的缓冲区大小来比较系统性能，此时，设置仿真时间为 40 000 s，图 5将递交率增大为原来的1 000倍，开销率增大为20倍后作图。由图5～图7可知，在报文生成间隔为30 s时，随着缓冲区的增大，递交率明显提高，平均延迟先上升后下降并趋于稳定，开销率增大。在报文生成间隔为30 s时，缓冲区相对空闲，本文算法增加报文的初始化副本数，增加报文的转发次数，当缓冲区增大到一定程度，由于报文副本上限一定，延迟稳定。

图5 报文生成间隔为30 s时递交率随缓冲区的变化

图6 报文生成间隔为30 s时平均延迟随缓冲区变化

图7 报文生成间隔为30 s时开销率随缓冲区变化

在报文生成间隔为30 s的仿真情况下，且网络中节点分布不均匀时，通过节点的分布比例1来比较系统性能，此时设置仿真时间为40 000 s。分布比例1的计算公式如下：

其中，m为缓冲区为50 MB的节点个数；n为缓冲区为10 MB的节点个数。

由图8～图10可知，本文算法在报文生成间隔为30 s时，随着缓冲区大的节点分布比例1的增大，网络中缓冲区相对空闲的节点变多，增加的文的初始化副本数的节点，增加了报文的转发次数，从而递交率增大，平均延迟降低，开销率增大。

图8 报文生成间隔为30 s时递交率随分布比例1的变化

图9 报文生成间隔为30 s时平均时延随分布比例1的变化

图10 报文生成间隔为30 s时开销率随分布比例1的变化

4.2.2 报文生成间隔为1 s的仿真结果

从图11可以出，当报文生成间隔为1 s时，在8 000 s之后，本文算法的递交率高于另2种路由算法。在8 000 s之后，随着报文生成的越来越多，节点缓冲区溢出，网络拥塞严重，本文算法减少报文的初始化副本数，进而缓解了网络拥塞，提高了递交率。

图11 报文生成间隔为1 s时递交率随时间变化

从图12可以看出，当报文生成间隔为1 s时，本文算法的开销率介于Epidemic与BSW之间。此时，大部分节点的最终缓冲区占用率较高，本文算法会减少报文的初始化副本数，从而使报文在节点之间传输的次数变少导致网络中报文递交的平均延迟比较大。

图12 报文生成间隔为1 s时平均延迟随时间的变化

从图13可以看出，报文生成间隔为1 s时，在4 000 s之后，本文算法的开销率比Epidem ic与BSW都要低。在4 000 s之前，仿真刚刚开始，缓冲区比较空闲，本文算法会增加报文的初始化副本数，从而增大开销；在4 000 s之后，随着仿真的进行，网络极度拥塞，本文算法会减少报文的初始化副本数，与BSW相比减少了开销率。

图13 报文生成间隔为1 s时开销率随时间的变化

在网络中节点分布均匀时，本文算法通过节点的缓冲区大小来比较系统性能，此时设置仿真时间为40 000 s。

由图14～图16可知，在报文生成间隔为1 s时，随着缓冲区的增大，缓冲区相对空闲，增加报文的初始化副本数的节点，增加了报文的转发次数，从而递交率增大，平均延迟降低并趋于稳定，开销率增大。

图14 报文生成间隔为1 s时递交率随缓冲区变化

图15 报文生成间隔为1 s时平均延迟随缓冲区变化

图16 报文生成间隔为1 s时开销率随缓冲区变化

在报文生成间隔为1 s的仿真情况下，且网络中节点分布不均匀时，通过节点的分布比例2来比较系统性能，此时设置仿真时间为40 000 s。分布比例2的计算公式如下：

其中，m′为缓冲区为400 MB的节点个数；n′为缓冲区为50 MB的节点个数。

由图17～图19可知，在报文生成间隔为1 s时，随着缓冲区大的节点分布比例2的增大，网络中缓冲区相对空闲的节点变多，增加报文的初始化副本数的节点，增加了报文的转发次数，从而递交率增大，平均延迟降低，开销率增大。

图17 报文生成间隔为1 s时递交率随分布比例2的变化

图18 报文生成间隔为1 s时平均延迟随分布比例2的变化

图19 报文生成间隔为1 s时开销率随分布比例2的变化

5 结束语

本文提出一种基于缓冲区占用率的散发等待路由算法。该算法利用节点的最终平均缓冲区预测周围网络环境，然后计算报文的初始化副本数。仿真结果表明，该算法在缓冲区空闲的情况下改善了递交率和平均延迟。今后将结合报文的其他特性，比如节点的能量、移动速度、运动规律，进一步完善此算法。

［1］ 林 闯，董扬威，单志广.基于DTN的空间网络互联服务研究综述［J］.计算机研究与发展，2014，51（5）：931-943.

［2］ Samaras C V.Adjusting Transport Segmentation Policy of DTN Bundle Protocol Under Synergy with Lower Layers［J］.Journal of System s&Software，2011，84（2）：226-237.

［3］ Hisamatsu T，Asaeda H.Adaptive Overlay Network for High-bandwidth Streaming［J］.Information and Media Technologies，2012，7（1）：435-447.

［4］ Chaithanya M.Performance Modeling of DTN Routing with Heterogeneous and Selfish Nodes［J］.Wireless Networks，2014，20（1）：25-40.

［5］ 樊秀梅，单志广，张宝贤，等.容迟网络体系结构及其关键技术研究［J］.电子学报，2008，36（1）：161-170.

［6］ 裴泽艮，肖明军，黄刘生.位置关联的延迟容忍网络路由算法［J］.计算机工程，2012，38（2）：123-125.

［7］ 熊永平，孙利民，牛建伟，等.机会网络［J］.软件学报，2009，20（1）：124-137.

［8］ Bulut E，Szymanski B.Secure Multi-copy Routing in Com promised Delay Tolerant Networks［J］.Wireless Personal Communications，2013，73（1）：149-168.

［9］ 张 龙，周贤伟，吴启武.容迟与容断网络路由协议的综合评估模型［J］.计算机工程，2010，36（9）：14-16.

［10］ 宋 鑫，王炳庭，胡 勇，等.基于蚁群算法的容迟网络概率路由算法［J］.计算机工程，2013，39（4）：90-93.

［11］ 王贵竹，卢华庭，徐 亮.容迟网络中基于节点能量考虑的混合散发与等待路由算法［J］.计算机工程与科学，2010，32（12）：8-11.

［12］ John W，Vania C.HYMAD：Hybrid DTN-MANET Routing for Dense and Highly Dynamic Wireless Networks［J］. Journal of Computer Communications，2010，33（13）：1483-1492.

编辑 刘 冰

Spray and Wait Routing Algorithm in in DTN Based on Buffer Occupancy Rate

MA Beilei，WANG Guizhu，ZHU Yanjuan，DING Anping
（Key Laboratory of Intelligent Computing&Signal Processing，Ministry of Education，Anhui University，Hefei 230039，China）

In traditional Spray and Wait（SAW）routing algorithm in Delay Tolerant Network（DTN），the number of copies of the message is certain，which results in some blindness about the forwarding number of the message.It causes the routing algorithm can not adapt to the network environment and cuts down the delivery ratio.To deal with this issue，it gives the relationship between the final average buffer occupancy of the node and the initial number of copies，and proposes a Spray and Wait Routing Concerned on Buffer Occupancy（SAW-BO）in DTN.The algorithm adjusts the initial number of copies dynamically based on the average buffer occupancy rate of the node.It ought to increase the initial number of copies to increase the delivery ratio when the average buffer occupancy of the node is relatively low and it should decrease the initial number of copies when the average buffer occupancy of the node is relatively high to avoid the occurrence of congestion.Simulation results show that compared with BSW routing，the proposed algorithm can significantly improve the delivery ratio and increases the average latency when the average buffer occupancy of the node is low in the network，it can also enhance the delivery ratio and reduce the network overhead when the average buffer occupancy of the node is high in the network.

Delay Tolerant Network（DTN）；routing；Spray and Wait（SAW）；buffer occupancy rate；number of copiesDO I：10.3969/j.issn.1000-3428.2015.10.017

马蓓蕾，王贵竹，朱妍娟，等.基于缓冲区占用率的 DTN散发等待路由算法［J］.计算机工程，2015，41（10）：88-93.

英文引用格式：Ma Beilei，Wang Guizhu，Zhu Yanjuan，et al.Spray and Wait Routing Algorithm in DTN Based on Buffer Occupancy Rate［J］.Computer Engineering，2015，41（10）：88-93.

1000-3428（2015）10-0088-06

A

TP393

马蓓蕾（1991-），女，硕士研究生，主研方向：无线通信；王贵竹，副教授；朱妍娟、丁安平，硕士研究生。

2014-09-15

2014-11-10E-m ail：m abeileiok@gmail.com