面向地面DTN网络的Prophet路由算法的优化与仿真*

朱人杰 谷代平 李莎莎 魏松杰 黄 炎 胡莹熏

（南京理工大学计算机科学与工程学院 南京 210094）

1 引言

延迟容忍网络（Delay Tolerant Networks，DTN）［1］提供了一种基于节点中继、托管、转发的，容迟容断的网络服务，最早被用于星际网络（Interplanetary Network，IPN）中，以应对IPN中节点间歇性连接、易中断、高误码率的情况。但随着研究越来越深入，野生动物追踪网络、战地网络、乡村网络等等地面的挑战网络（Challenged Networks）场景下的DTN都成为了新的研究方向。

针对DTN网络，研究者们提出了很多种路由算法：直接传递路由、基于洪泛的路由、基于概率的路由等。

直接传递路由，只有在携带消息的节点与目的节点能够产生单跳连接时，携带消息的节点才会将消息传递给目的节点。这种路由方式消耗最少的网络资源，全网只有一个副本，但是到达率也最低。

基于洪泛的路由，最典型的是Spray and Wait算法［2～3］、Epidemic［4］算法。Epidemic算法通过节点的接触，无限制地将副本复制到没有该副本的节点，最终将副本复制到目的节点，从而以巨大的资源代价完成消息的传递。而Spray and Wait则在Epidemic的基础上限制了副本的数量，控制了网络资源的浪费。

基于效用的路由。DTN路由算法的目的是让数据包能尽快、尽可能地被目地节点接收，实现这一目的的其中一种办法，就是将数据包转发给更适合的中转节点，而如何度量适合，则需要引入效用函数。最为著名的基于效用量化的路由算法是Lindgren A等提出的Prophet路由算法［5］，在Epi⁃demic算法的基础上，引入了预测投递概率作为效用函数，Bundle将仅被复制至预测投递概率更高的节点。

基于社会性的路由。基于社会的路由可以视作是基于效用路由的演进。与一般的效用路由算法不同的是，社会路由算法将人类社会与DTN进行类比，以人与人之间的社会关系类比节点与节点之间的关系，利用社会学得到的社会知识进行路由选择。典型的基于社会性的路由有Bubble Rap［6］算法。通过节点运动的社会性，优先将消息副本传递给与目的节点处于相同社交圈或者接近其社交圈的节点。这种算法将DTN网络看作人的社交网络，控制了网络中的副本数，到达率适中。

在地面环境的DTN使用中，存在着诸如乡村网络、救援网络、会议网络、野生动物追踪网络等等使用环境，此类DTN网络往往节点网络资源有限并且节点运行不规律，难以形成群落，因此基于洪泛以及社会性的路由方法都难以适用于此类网络。此时，基于效用的路由算法是一个好的解决方案。本文基于经典的效用量化路由算法——Prophet路由算法，在其基础上充分考虑节点的性能差异、状态差异，通过节点的传输速率、缓存区大小以及历史平均转发成功率，在保证传输性能、存储性能的基础上再进一步规避了Prophet路由算法的“停车场问题”［7］，从而提升了传输的效率以及成功率。

2 相关工作

2.1 延迟容忍网络

2007年，由IRTF的DTNRG研究 组发 布 的 与DTN网络体系结构相关的规范文档RFC4838，分析了TCP/IP协议栈在受限网络环境下失效的原因，并在此基础上提出了区别于TCP/IP协议栈的DTN协议栈［8］，如图1所示。

图1 DTN协议栈

通过Bundle协议的托管重传机制、后绑定机制，LTP协议的区分红绿数据、红部数据接收检查等功能，DTN实现了消息的逐跳、容迟容断传输、不基于连接的安全传输等功能。

虽然方案最初是面向空间网络，但是在地面受限网络环境，如战场环境［9～10］、救援环境［11～12］、车联网［13］、野生动物追踪［14］等应用场景中，高延时、时断时续的链路、高误码率等因素也与空间网络十分相似，因此DTN也被在这些背景下被广泛研究。

2.2 Prophet路由算法

Prophet路由算法由三个主要公式构成，分别为相遇概率增加公式、相遇概率衰减公式以及传递概率公式。针对Prophet路由算法的优化一般是对相遇概率增加公式的优化。

1）式（1）给出了Prophet原有的相遇概率的增加规律，两个节点的每一次相遇，它们都会更新自己与对方的相遇概率，在原有基础上进行增加：

其中P(a，b)old为a节点与b节点的原有相遇概率，Pinit∈[0，1]为初始化常量，本文中取其值为0.45。

2）两个节点的相遇概率随着时间的推移衰减。式（2）给出了相遇概率随时间衰减的规律。

其中时间老化常数γ∈(0，1)，k是当前距离上次相遇的时间间隔。

3）虽然DTN中的路由算法是逐跳计算的路由算法，但是依然需要考虑消息的传递概率。如果节点a需要传递消息给节点b，当它遇到经常与节点b相遇的节点c，将节点c作为中继节点是一个好的选择。式（3）说明了节点的传递概率是如何影响相遇概率的。

其中传递常量β∈(0，1)，决定了传递概率对相遇概率的影响的大小。

3 基于节点差异的Prophet-BSAS路由算法

3.1 算法改进逻辑

Prophet路由算法进行下一跳节点路由判断的基准在于P（A，destination）与P（B，destination）的比较，即A节点与目标节点相遇的预测概率和B节点与目标节点相遇的预测概率的比较。当携带消息的节点A与节点B相遇，节点B能够将数据包的传输到目标节点的概率高于A，则A将数据包的副本传输给节点B。

但是不同于空间DTN网络，这些新的应用领域已经发生了极大的变化，同时也产生了许多新的挑战。与空间DTN相比，新的应用场景通常节点运动不规律、轨迹难以预测，信息产生不均匀且信息量较大，节点种类更加多样、性能差异较大。即便是具有相同相遇概率的节点，它们的性能差异与各自当前的状态差异也会造成传输成功率的巨大差异，所以只是简单通过相遇次数计算相遇概率的Prophet算法有很多其他可以考虑的因素，可以在保证可靠性的同时提升传输的效率与成功率。

首先，考虑到各节点本身带宽资源、传输能力的差别，通过将节点传输峰值速率加入考量范畴，可以优先选择传输速率更快的节点，提升传输的效率。在有限的接触次数与接触时间内，将节点缓存的数据最多地传输到更优节点。

其次，考虑节点的缓存区大小，优先选择剩余缓存区大的节点，从而防止因为缓存区充满导致的消息丢失。

最后，是节点数据平均转发成功率的考虑。Prophet算法在进行下一跳节点的选择时，考虑的仅仅是下一跳节点与目标节点的相遇次数，忽略了相遇之后，节点之间连接维系的时间、连接的稳定性。在地面网络中，各个节点的性能、运动参数往往更为复杂，所以经常出现一些“伪优质”节点，这类节点可能虽然经常接触到可传输的下一跳节点，但是由于接触时间短、CPU性能差等原因，传输的成功率却很低，也就是前文所提到的“停车场问题”。而将节点数据平均转发成功率加入考虑，可以尽可能地去规避这样的“伪优质”节点。

3.2 算法整体流程

如图2所示，当携带消息的节点A在运动过程中遭遇一个新的节点B，节点A将通过以下流程决定是将消息转发给节点B还是继续运动，等待更优质的节点。

图2 判断流程图

3.3 具体改进

1）节点传输速率的处理。要将节点传输峰值速率加入到P(a，b)的考量中，需要对峰值速率V进行归一化处理，本文中使用线性函数归一化处理峰值速率。

其中Vmin是传输速度的最低值，停止发送时速度最低，所以Vmin为0。Vmax为节点自身能达到的数据传输上限，它通常由节点CPU性能、网口速率等因素中的短板决定。

2）节点剩余缓存区的计算。各个节点将节点剩余缓存区的容量进行归一化处理，在归一化后得到变量MbufferNorm，该变量与节点剩余缓存区容量成正比。MbufferNorm越大的节点，越容易被选择为下一跳节点。

其中Mrest剩余缓存区的大小，单位为MB。这里MbufferNorm∈[0，1)。

3）节点数据平均转发成功率的计算。节点需要进行处理的数据总量与成功转发的数据总量的统计，即进入节点的数据包的数据总量与节点自己产生的数据包的数据总量之和以及成功转发的数据总量：

m.getsize()表示获取数据包的大小，n、m、p分别表示截至目前时间，节点接收到的数据包总数，节点产生的数据包总数以及成功转发的数据包总数。在得到这两个数据后，计算本节点平均转发成功率。

4）在得到这些数据之后，我们可以将节点的传输速率、节点中消息的平均排队时间以及节点数据包转发的历史成功率的计算加入到相遇概率P(a，b)的计算中，对式（1）优化：其中变量μ∈[0，1]，且满足Pinit+μ∈[0，1]。本文中μ的值取为0.4。

4 仿真实验

4.1 仿真环境

实验使用的仿真工具为ONE-1.5.1。仿真采用的数据集是INFOCOM06数据集，INFOCOM06数据集是在2006年巴萨罗纳INFOCOM会议上收集的，数据集包含了各节点在会议期间的连接信息。节点包括了17个布置在整个区域内的设备，3个长期放置在电梯内的设备以及78个由参会的人员携带的设备。具体参数如表1所示。

表1 仿真参数

为了更好地分析实验结果，本文首先分析了infocom06数据集连接个数随时间的变化，结果如图3所示，在白天，整个网络中的连接数较多，在进入夜间后，网络中的连接数变少。

图3 网络中连接数

4.2 评估指标

本文选用以下四种指标对路由方法性能进行测试：数据到达率、网络开销比、传输平均时延与平均跳数。

数据到达率Psuc：成功到达的数据总量与所有节点产生的数据总量的比值，计算公式如下：

其中Dsuc表示成功到达的数据量，Dgen表示所有节点产生的数据总量。

网络开销比POverheadRatio：没有被成功投递到目标节点的消息数据总量与成功投递到目标节点的消息数据总量之差，与成功投递到目标节点的数据总量的比值，用来衡量为了成功传递消息而需要进行额外传递消息的概率。

其中Drelay表示网络中被转发的数据总量。

传输平均时延Tavg：被成功递交的消息从产生到被成功递交所用的平均时间，计算公式如下：

其中Tx，a表示第x个成功递交的数据包的到达时间，Tx，gen表示第x个成功递交的数据包的生成时间。

平均跳数CHopAvg：消息从源节点到目标节点所经历的平均跳数，计算公式如下：

其中Ck，hop表示第k个到达目的节点的数据包经历的跳数。

4.3 仿真结果

4.3.1 递交成功率

图4 给出了在不同仿真时间内，五种不同的路由协议的递交成功率，由于数据集在开始记录的1小时之后才开始收到节点的连接信息，所以仿真也在1h之后开始记录结果。从图中可以看到，在递交成功率方面，Prophet-BSAS在几乎所有时间内都优于其他路由协议。

图4 递交成功率

使得Prophet-BSAS具有较高的递交成功率的主要原因是，Prophet-BSAS考虑了节点的性能差异，优先考虑了传输速率较高、数据传输成功率较高的节点，在得到传输机会时，可以较好地将数据包进行转发；选择缓存区充足的节点，在没有传输机会或者传输中断时，可以将数据存储、等待下一次转发，不易发生数据的丢失。

4.3.2 网络开销比

图5 给出了在不同仿真时间内，五种路由协议的网络开销比的比较。Spray and Wait路由协议虽然已经人为控制了网络中的副本总数，但是副本总数的控制与递交成功率的冲突使得Spray and Wait的网络开销比不能控制在低水准。基于社交的Bubble rap与基于机会的Prophet网络开销比较为接近，而Prophet-BSAS在网络开销比方面展示了极佳性能。

图5 网络开销比

主要原因是在地面DTN网络环境中，更为全面的筛选条件在选取优质节点作为下一跳节点的同时，有效控制了网络中副本的数量。

4.3.3 平均时延

如图6所示，虽然由于在建立连接之后、传输消息之前，基于相遇概率的路由算法需要进行节点之间相遇概率的交换，所以天然地会使得传输时延有所提高，但是由于Prophet-BSAS选择的节点综合性能更为优质，传输速率较高、重传次数较少，所以Prophet-BSAS在有一定的连接时间保障的前提下，可以很好地传输大量数据。从图中可见，在平均时延方面比Prophet-BSAS比Prophet降低了1700s左右。

图6 平均时延

4.3.4 平均跳数

图7 给出了五种路由协议在平均跳数方面的比较，由于Prophet-BSAS选取的节点传输速率较高、缓存区容量充足，不容易发生数据包传输中途失败，需要重传的情况；同时，对于传输成功率低的伪优质节点的过滤，也使得传输更加高效。三者综合，Prophet-BSAS能更准确地选择出更好的下一跳，从而降低了传输的平均跳数。Prophet-BSAS的平均跳数在2.5跳左右，优于Prophet的3跳以及Bubble Rap的3.5跳。

图7 平均跳数

5 结语

本文从地面DTN网络的实际情况出发，分析了其与空间DTN网络的主要差异——节点的性能与状态更为复杂多样，进而在Prophet路由协议的基础上，针对会影响传输的性能与成功率的三点进行了优化。优先选择传输成功率高的节点，使得在短暂的连接时间中，可以传输尽可能多的数据。优先选择缓存区充足的节点，使得在没有传输机会或者传输中断时，有充足的空间缓存数据，降低数据的丢失概率。优先选择平均转发成功率高的节点，规避虽然有较高的相遇概率但是传输性能较差的节点。最后通过ONE仿真，将改进的路由算法与其他算法进行了性能对比，证明了改进后的方案提高了递交成功率，降低了网络开销比与平均跳数。