节点缓存感知的DTN 概率路由算法

钟 贇，夏靖波，付 凯，尹 译，李智伟

（1.空军工程大学 信息与导航学院，陕西 西安710077；2.75150部队，湖南 衡阳421131）

0 引 言

在容迟容断网络 （DTN）［1］中，节点分布稀疏、移动频繁且缓存和能量有限，传统的路由算法并不适用。消息的传递主要采用 “store－carry－forward” （存储－携带－转发）机制，通过中继节点传送给目的节点，常用于农地数据收集网络［2］、车载网络［3］和水下网络［4］等延迟较大、网络拓扑多变的网络环境。

目前，研究人员提出的典型DTN 路由算法包括Epidemic算法、PROPHET 算法以及Spray and Wait算法。Epidemic传染机制算法中，每个节点都将消息副本复制给相遇节点，但由于节点能量和缓存受限，容易造成消息的大量重传和丢弃，网络开销大［5］；PROPHET 算法根据节点运动的规律，利用历史相遇信息预测到达目的节点的概率，将消息复制给完成数据传递概率更大的节点，从而限制了消息副本的数量，降低了网络资源消耗［6，7］；Spray and Wait算法限制消息转发的上限数目n，这种机制避免产生过多的消息，从而造成网络开销的爆发式增长［8］。

DTN 网络资源受限的特性，决定了节点的缓存状况是制约路由算法效能的关键因素。文献 ［9］提出一种考虑由于节点缓存不足出现拥塞情况的概率路由算法，结合节点相遇概率和节点拥塞时间得到消息的递交概率，提高了消息的递交率，但是节点拥塞时间是动态变化的，难以实时准确统计；文献 ［10］考虑了在网络节点因缓存不足出现拥塞时，丢弃低优先级消息以保证高优先级消息传输，并没有考虑网络拥塞发生之前缓存大小的影响作用；文献［11］为了缓解DTN 中热点区域的拥塞状况，定义了节点的拥塞率，依据对接触历史、节点预期缓存的分析，重新进行了转发效用整合，但算法的计算复杂度较高。

针对现有算法的不足，本文关注节点缓存状况对DTN路由算法的影响，设计了基于节点缓存剩余率的DTN 概率路由算法，在计算相遇概率值和消息丢弃时考虑节点缓存状况，并在消息转发和丢弃时设置合理阈值，避免了网络拥塞造成的网络性能下降，提高了消息递交率，降低了网络开销。

1 相关工作

1.1 问题描述

当网络中节点缓存受限时，往往不能无限制地接受其它节点的消息转发，而是要选择性地进行接收。PROPHET 算法没有采用洪泛机制进行消息转发，而是根据节点记录的历史相遇消息确定是否进行转发，能够有效地降低网络资源的消耗［6］，但还存在一定的问题。设想以下场景：节点a携带发往节点d的消息，节点b和c都进入了节点a的通信范围，且两节点的转发概率基本相同，而节点b的缓存较大，节点c的缓存较为有限。在此种条件下，节点c可能会在以后与其它节点的接触中出现拥塞，从而影响消息的转发。PROPHET 算法单纯以历史相遇概率作为转发依据，则a将消息转发给b和c的概率基本相同，而没有考虑节点缓存的影响，实际上节点b为较为理想的转发节点。

为避免上述情况的发生，本文基于PROPHET 算法，提出一种考虑节点缓存状况的节点缓存感知算法NBAPR（node buffer－aware probabilistic routing algorithm），该算法在计算转发效用时引入了节点缓存的影响，在转发消息有两个备选转发节点时，尽量选择节点缓存剩余比值较高的节点进行转发，从而减少因节点缓存不足造成的消息丢失。

1.2 节点缓存受限的网络模型

DTN 中每个节点都有一个缓存单元用于存储等待转发的消息，各个节点的缓存大小都是有限的。每个节点的初始缓存记为Binit，节点的剩余缓存记为Bcur，节点剩余缓存率记为BE。显然，有BE＝Bcur／Binit。

本文根据节点缓存剩余率设置节点状态，定义节点缓存剩余率门限η1、η2，按照节点缓存占用率，将节点划分为高缓存节点 （HBN）、中缓存节点 （MBN）和低缓存节点 （LBN），特别地，当节点的剩余缓存率为0时，则称节点进入拥塞状态。节点状态的划分规则定义为

式中：Node（i）——节点i所属的节点类型。

2 算法描述和参数设置

2.1 转发概率的计算

在DTN 的实际网络环境中，PROPHET 算法只考虑了节点的相遇概率，而没有考虑影响制约消息传输性能的节点缓存状况。因此，本文算法在PROPHET 算法上针对更新公式和老化公式进行了改进。

首先，在更新公式中引入节点剩余缓存占比的影响，若节点的剩余缓存占比越高，则更新后概率越高，从而缓存剩余率较高的节点更有可能被选择为消息传输节点。具体计算方法如下

式中：Pinit——初始概率值，BE——节点的剩余缓存占比，D——缓存剩余率对转发概率的影响因子 （D＞1，Pinit×D＜1）。

其次，节点转发效用的老化不仅受节点间未相遇时间间隔的影响，而且与节点的剩余缓存率有关，节点的剩余缓存率越高，则对该节点的递交效用老化的速率也就越慢。如下式所示

式中：γ——节点转发概率的老化因子，控制节点转发概率老化的速度；k 是两节点上次相遇时刻到当前时刻的时间间隔。

再次，传递公式反映了消息递交概率的传递性。当节点a、b经常相遇，b、c两节点也经常相遇，则可以认为节点b是a、c的良好中继节点，节点a、c间的概率定义如下

式中：β——转移因子，取值范围为 （0，1］，表示概率传递性对消息递交概率的影响大小。

本文算法需要每个节点维护一个节点缓存剩余率表，用于记录该节点可用缓存占总缓存的比值。为了便于研究，假设节点缓存剩余率表的大小相对于消息大小来说较小，并不占用缓存空间。

2.2 消息转发策略

对于DTN 网络来说，节点的缓存状况很大程度上会影响网络性能。因此，在每次进行消息转发之前，对自身节点和对方节点的状态检测可以有效减少因为盲目转发而造成低缓存节点陷入拥塞的机率，从而提高节点转发的效率。具体的转发策略规定如下。

（1）在自身为低缓存或中缓存节点，对方为高缓存节点时，判断对方节点的转发效用P（b，c）＞ρ1 是否成立，若成立，则进行转发。ρ1 是一个非负常量，表明节点b的转发概率必须多大时才能从低缓存节点获得消息。设置合理的ρ1 值可以避免发送节点陷入拥塞状态后进行消息丢弃策略后删除消息，从而导致消息递交率的降低，并且在一定程度上有利于缓解自身的低缓存状况。

（2）在检测对方节点为低缓存节点时，判断对方节点的转发效用P（b，c）＜ρ2 是否成立，若成立，则不进行转发。ρ2 是一个非负常量，表明节点b的转发概率必须多小时才拒绝接收消息。设置合理的ρ2 值可以避免消息转发后加重对方节点的低缓存状况，以致陷入拥塞。

（3）在其它情况下，消息进行正常转发，按照转发效用的相对大小决定消息是否进行转发。

2.3 消息丢弃策略

节点的缓存资源是有限的，在缓存达到饱和状态时，必须进行消息丢弃，以释放缓存空间，减少不必要的资源浪费。目前，丢弃消息的策略主要包括：①DF （drop front）：丢弃缓存空间中存在时间最长的消息；②DO （drop oldest）：丢弃缓存空间中生存时间最小的消息；③DY （drop youngest）：丢弃缓存空间中生存时间最大的消息。

本文提出一种综合考虑消息TTL和消息进入缓存时长的组合丢弃策略，定义消息生存度值

式中：RTTL——消息的TTL剩余率，TB——消息进入节点缓存的时长。消息的MSD 值越小，则消息的生存性越差，消息的缓存利用效率越低，因此在出现节点拥塞时优先丢弃MSD 值最小的消息，减少刚进入节点缓存和剩余生存时间较长的消息就被删除的可能性。

2.4 冗余副本删除策略

传统的PROPHET 路由算法是多副本路由算法，节点将消息转发后将继续保存该消息副本直至节点缓存达到饱和，然后节点对缓存内的消息进行相应的丢弃策略，这种缓存管理机制势必会造成缓存资源的浪费。节点将消息转发后，合理地删除保存在自身缓存中的消息副本，能够充分利用节点的缓存资源，减小网络资源的消耗。本文算法设置副本删除阈值Pth，当更新后的转发概率P（b，c）＞Pth时，认为节点b将消息转发至目的节点的概率较大，a无需再进行消息的保存。

2.5 参数D的设置

参数D 为节点缓存剩余率对转发概率的影响因子，当节点的剩余缓存比较多时，即BE趋近于1，缓存对转发概率的影响较小，则D 的取值应该相应较小；反之，节点缓存对转发概率的影响较大，则D 的取值应该相应较大。本文近似认为D 的取值与节点缓存剩余率成线性关系，D 值定义如下

其中，Dinit＝1，代表通信进入初始阶段，各节点剩余缓存率接近于1，转发概率更新公式退化为经典PROPHET 算法中的公式，显然有D＞1，Pinit×D＝1－ （1－Pinit）×BE＜1。

3 仿真实验与结果分析

本文采用ONE 仿真平台［12］，它是基于Java开发的，可以实现节点移动模型、路由算法的可配置图形化仿真，并可以提供结果报告和分析模型；使用OpenJUMP软件绘制WKT 格式的节点运动地图文件，模拟了空中信息网络飞行节点的运动路径。

3.1 仿真场景构建

仿真场景的设置对实验结果的影响是显著的，本文采取的仿真区域大小为2000×2000 m，模拟了实际通信环境。包含24个节点，共分为3组，其中临近空间飞行节点10个，高空飞行节点9个，低空飞行节点5个，均采用基于地图路线的移动模型，各组节点按照其功能特点设置对应的通信范围和移动速度。设置仿真时间为12h，消息生成间隔时间为60s，消息大小为0.5 MB。表1为本文算法的参数配置，其它算法采用默认配置。

表1 本文算法参数

3.2 性能指标

（1）消息递交率：衡量DTN 网络性能的主要指标包括消息递交率、网络开销和平均时延，DTN 路由设计的目的就是最大化消息递交率，最小化平均时延和网络开销。消息递交率是其中最重要的指标，消息递交率定义为

式中：Nt——网络中产生的消息总数，Nr——网络中被目的节点成功接收的消息总数。

（2）网络开销：网络开销是指网络中未被中继节点转发到目的节点的消息数目与成功被转发到目的节点消息数目的比值。网络开销定义为

式中：Np——中继的消息数量，Nr——成功递交的消息数量。

（3）平均时延：平均时延是指所有被目的节点成功接收的消息从源节点发送至目的节点所花费的平均时间。平均时延定义为

式中：Ti，t——第i个消息由源节点发送的时间，Ti，r——第i个消息被目的节点接收的时间，n——所有被递交的消息数。

3.3 实验结果分析

仿真实验首先对比了NBAPR、PROPHET 和Epidemic这3种算法下网络性能指标受消息生存时间 （TTL）影响的情况，然后对比了3种算法在不同链路带宽下的性能差异。

3.3.1 消息生存时间因素

图1和图2显示，随着消息生存时间的增大，网络中的消息数目越来越多，包括节点缓存在内的大量网络资源被占用，网络开销随之渐增，消息的传递效率相应降低。Epidemic算法性能最差，说明在资源受限的真实场景中，洪泛式的转发算法并不能取得良好的效果；NBAPR 算法在进行消息转发时，引入了节点缓存状况的影响，调整了消息丢弃策略和副本删除策略，很好地控制了消息的复制数目，提升了节点缓存的利用效率，从而实现了网络开销的下降和消息递交率的提高；PROPHET 算法在消息递交率上略优于Epidemic算法，在网络开销上介于Epidemic和NBAPR 算法之间。

图1 TTL对递交率的影响

图2 TTL对网络开销的影响

图3显示，随着消息生存时间的增大，3种算法的平均时延总体上呈现增长态势。由于Epidemic算法采用洪泛机制，容易使网络陷入拥塞，所以平均时延增长较快；NBAPR算法在进行消息转发时，在对中继节点的选择上条件更加苛刻，从而导致了NBAPR 算法的平均时延要大于PROPHET 算法；PROPHET 算法在消息生存时间大于2h时，平均时延变化不大，趋于稳定。

图3 TTL对平均时延的影响

3.3.2 链路带宽因素

图4描述了此场景下的消息递交率变化情况。NBAPR算法比PROPHET 算法平均提升了14.7%，且随着链路带宽的提高有逐渐扩大的趋势；当带宽在2 Mbps－5 Mbps区间内时，Epidemic算法的消息递交率高于PROPHET 算法，但当带宽达到6 Mbps左右时，PROPHET 算法的递交率出现了跃升。

图4 链路带宽对交付率的影响

图5显示，NBAPR 算法在网络开销方面同样表现最好，比PROPHET 算法平均提升了44%，且随着链路带宽的提高，NBAPR 算法的网络开销下降趋势较为明显；Epidemic算法在网络开销方面的性能则远逊于NBAPR 和PROPHET 算法。

在平均时延方面，图6显示了3种路由算法的平均时延均随着链路带宽的增大而减小。在网络资源有限的条件下，Epidemic算法的平均时延较大；NBAPR 算法受链路带宽影响较大，链路带宽在2 Mbps－4 Mbps时，平均时延出现陡降，随后平均时延趋于稳定，与PROPHET 算法接近；PROPHET 算法的平均时延受链路带宽的影响不像另外两种算法大，总体上较为稳定。

图5 链路带宽对网络开销的影响

图6 链路带宽对平均时延的影响

4 结束语

DTN 网络环境苛刻，其网络资源受限的特性给设计合理高效的路由协议带来了极大的挑战，如何充分考虑节点能量、缓存等网络资源状况，以较少的网络资源消耗实现较高的网络性能，是DTN 路由协议设计的重要方向。

本文结合PROPHET 算法，综合考虑节点缓存状况和历史相遇信息计算节点转发效用，合理设置消息转发策略中的递交阈值控制消息的复制；同时，在缓存管理策略和冗余副本删除策略也做出对应的优化。在网络性能评估中，本文算法在消息递交率和网络开销两个性能指标上得到了较大提升，同时网络的平均延迟也控制在较好水平。下一步的研究重点是如何设置更加科学合理的递交阈值，实现算法在不同环境中性能提升的普适性。

［1］SU Jinshu，HU Qiaolin，ZHAO Baokang，et al.Routing techniques on delay／diaruption tolerant networks［J］.Journal of Software，2010，21 （1）：119－131 （in Chinese）.［苏金树，胡乔林，赵宝康，等.容延容断网络路由技术 ［J］.软件学报，2010，21 （1）：119－131.］

［2］Ochiai H，Ishizuka H，Kawakami Y，et al.A dtn－based sensor data gathering for agricultural applications［J］.IEEE Sensors Journal，2011，11 （11）：2861－2868.

［3］Li Xu，Shu Wei，Li Minglu，et al.DTN routing in vehicular sensor networks［C］／／Proceedings of IEEE Global Telecommunications Conference.New Orleans，USA：IEEE，2009：1－5.

［4］Guo Z，Wang B，Cui J H.Prediction assisted single－copy routing in underwater delay tolerant networks ［C］／／Proc of IEEE Globecom.Piscataway，NJ：IEEE，2010：1－6.

［5］Voyiatzis A.A survey of delay and diarupion tolerant networking applications［J］.Journal of Internet Engineering，2012，5 （1）：331－344.

［6］Huang T，Lee C，Chen L.PRoPHET ＋：An adaptive PRoPHET－based routing protocol for opportunistic network［C］／／Proceedings of 24th International Conference on Advanced Information Networking and Applications.Piscataway：IEEE，2010：112－119.

［7］Karvo J，Ott J.Time scales and delay－tolerant routing protocols［C］／／Proceedings of the Third ACM Workshop on Challenged Networks，2008：33－40.

［8］Huang W，Zhang S，Zhou W.Spray and Wait routing based on position prediction in opportunistic networks ［C］／／Proceedings of 3rd International Conference on Computer Research and Development.Shanghai：IEEE，2011：232－236.

［9］SONG Xin，HU Yong，WANG Bingting.Probabilistic routing algorithm based on node congestion in DTN ［J］.Application Research of Computers，2012，29 （4）：1493－1496 （in Chinese）.［宋鑫，胡勇，王炳庭.一种考虑节点拥塞情况的DTN 概率路由算法［J］.计算机应用研究，2012，29 （4）：1493－1496.］

［10］WANG Guizhu，XU Zhenghuan，LI Xiaofeng.Congestion control strategy based on quality of message in DTN ［J］.Computer Engineering and Applications，2012，48 （9）：74－77 （in Chinese）. ［王贵竹，徐正欢，李晓峰.DTN 中依据报文质量的拥塞控制策略 ［J］.计算机工程与应用，2012，48 （9）：74－77.］

［11］REN Shanshan，XU Futian，SUI Jingqi.Congestion perception forwarding algorithm in DTN ［J］.Computer Engineering and Design，2012，33 （8）：2961－2965 （in Chinese）.［任姗姗，徐夫田，隋敬麒.DTN 中的拥塞感知转发算法［J］.计算机工程与设计，2012，33 （8）：2961－2965.］

［12］Ari Kernen，Jrg Ott，Teemu Krkkinen.The ONE simulator for DTN protocol evaluation ［C］／／Proceeding of the 2nd International Conference on Simulation Tools and Techniques.Rome，Italy：ACM Press，2009：1－10.