基于吞吐率的Prophet路由在DTN中的应用

马 慧，李 涛

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

0 引 言

延迟容忍网络(delay tolerant network，DTN)[1]作为一种新型的网络架构，有别于传统的TCP/IP网络，是一种间歇性连接的网络，大多数情况不存在端到端的传输路径。即使存在端到端的传输路径，也比较容易中断[2]。由于DTN网络的间断性连接，易中断的特殊通信环境，传统的TCP/IP协议并不适用于该网络。为了更高效地传递消息，DTN网络主要采用存储-携带-转发的机制[3]。随着DTN网络受到越来越多的关注，DTN的应用领域也越来越广泛，如野生动物追踪和栖息地检测传感器网络[4]、乡村通信网络[5]、星际网络[6-7]、激光通信[8]等。

DTN网络的路由协议、节点传输协议和安全等方面受到了专家和学者的重视。DTN路由[9]作为DTN网络研究的重要方面，面临的主要挑战是如何在时延大、误码率高、节点分布较稀疏和不对称的数据速率的网络中消耗更少的网络资源，传递更多的消息。而在传统的TCP/IP路由协议中，消息转发则是一个相对较容易的任务，消息转发给到达目的节点最短路径上的一个邻居节点，路径的可靠性相对较高，传递成功率也相对较高。而在DTN网络中，这些传统的路由协议是不适用的。经过多年的研究，国内外的专家和学者们给出了很多适合于DTN网络的各具特色的路由算法。其中，比较典型的主要有：DirectDelivery[10]、Epidemic[11]、Prophet[12]和Spray-and-Wait[13]。

直接传输(DirectDelivery)在DTN网络当中是最简单的一种单拷贝路由方式。直接传输的主要原理是源节点持有传输消息，直到源节点遇到目的节点，源节点才将该消息发送给目的节点。直接传输的主要缺点在于消息完全依赖于源节点和目的节点的直接相遇，由于DTN网络的特殊环境导致消息的传输延迟较大，消息易丢失，投递率较低。传染路由(Epidemic)的主要原理是携带消息的节点将消息复制转发给相遇的所有节点，试图用更多的传递次数来换取消息的投递成功率。

显然，相比直接传输，虽然传染路由不依赖于源节点和目的节点的直接相遇，但是由于传染路由的传染性，会导致网络中消息过多，占用太多的系统资源，网络开销较大。对于Prophet路由算法，概率路由比传染路由在算法上要复杂很多，主要是利用节点到目的节点的历史传递概率来计算节点当前到目的节点的传递概率。当两个节点相遇时，通过比较两节点与目的节点的接触概率，来决定携带消息的节点是否要把消息传递给相遇节点。Spray-and-Wait是一种基于消息拷贝的路由算法。通过控制传递消息副本的数量来减少报文在网络当中的冗余量，同时增加了消息的传递成功率。

在上述研究的基础上，文中给出了基于节点的历史吞吐率的Prophet路由策略，并对其进行了仿真。

1 Prophet路由

Prophet是一种基于概率的路由协议。Prophet路由认为，节点的移动并不是盲目的和随机的，而是遵循一定的规律。当一个节点在某一时刻遇到另一个节点，那么这两个节点可能在之后的一段时间内还可能以某一概率相遇。所以在Prophet路由算法中，每个节点都会维护一张转发概率表，当一个携带节点遇到另一个节点，节点并不是盲目地将消息转发给相遇节点，而是通过概率转发表来预先估计节点到达目的节点的传送预测概率，通过比较概率值来决定是否要把消息传递给相遇节点。

在Prophet路由中，一个主要的性能指标是P(a,b)∈[0,1]，它表示节点A能够传输消息到节点B的预测概率。当节点A和节点C相遇时，两个节点相互交换各自的预测向量，用来决定是否要把消息传输给相遇节点。其中，预测向量包含了节点到达其他所有节点的传递概率预测信息。也就是当携带消息的节点A和节点C相遇时，通过预测概率判断节点A和节点C与目的节点B的接触概率，如果节点C传输消息到达目的节点B的预测概率大于节点A传输消息到达目的节点B的预测概率时，节点A将会把消息传输给节点C。

传递概率的计算过程主要包括三个步骤:

(1)当两个节点相遇时，更新节点的预测向量。相遇越频繁的节点，传递的可能性越高，如式1所示。

P(a,b)=P(a,b)old+(1-P(a,b)old)×Pinit

(1)

其中，Pinit∈[0,1]是初始化常数，通常取值为0.98；P(a,b)old表示节点a和节点b上一状态的相遇概率。

(2)当两个节点长时间没有相遇，那么，两个节点的传递概率就会降低。所以随着时间的推移，两节点的传递概率不断减少。式2描述了两节点的传递概率随时间的变化关系。

P(a,b)=P(a,b)old×γk

(2)

其中，γ是一个时间老化常数，在[0,1)间取值;k是本次距离上次更新的时间间隔。

(3)考虑到节点的传递性，设想下面一种情况:如果节点A经常遇到节点B，节点B经常遇到节点C，那么，有理由相信节点A和节点C的相遇概率也应该较高一些。根据式3可以计算出节点A和节点C之间的传递概率。

P(a,c)=P(a,c)old+(1-P(a,c)old)×

P(a,b)×P(b,c)×β

(3)

其中，β是一个放大常数，决定了节点的传递性对节点的传递概率将产生多大的影响。

2 改进的Prophet路由算法(Enhanced Prophet，E-Prophet)

DTN网络特殊的网络环境使得节点的性能受到很大的影响。网络中节点的能量、带宽和自身缓存等的限制可能会导致节点不能成功地把消息传递给目的节点。而节点的历史吞吐率在一定程度上反映了一个节点性能的好坏。所以文中考虑了节点自身的历史吞吐率[14]对节点消息转发概率的影响，在原有Prophet路由的基础上做出改进。把节点的历史吞吐率定义为：一个节点在当前时间之前所成功传输消息的数据总和与该节点作为中继节点接收到的消息和该节点自身产生的消息的数据总和的比值。

设想下面一种情况，一个节点携带消息，试图在网络中传递该消息给目的节点，当前节点遇到一个中继节点时，假设在Prophet路由算法当中经过计算得知，该节点和相遇的中继节点传递该消息到目的节点的概率相同，但是如果相遇的中继节点的历史吞吐率比当前节点的历史吞吐率大，那么有理由相信历史吞吐率较高的相遇节点应该要比历史吞吐率相对较低的当前节点拥有更高的传递概率，所以当前节点应该把消息传递给相遇节点。文中就是在此假设的基础上，把节点的历史吞吐率作为Prophet路由算法的一个影响因子，通过改进Prophet路由算法，使得消息的传递效率比之前要提高一些。

具体实现是：在每一个节点当中记录该节点在当前时间之前成功转发的所有消息数据大小与该节点作为中继节点接收到的所有消息数据大小和节点产生的所有消息数据大小的比值，即节点的历史吞吐率。把计算出的历史吞吐率这一性能指标作为一个增长因子加入式1。

节点作为中继节点接收到的消息的计算公式为：

(4)

当节点作为一个中继节点成功接收到一个消息时，获取该消息的大小，并计算在当前时间之前该节点接收到的所有消息的数据总和。Received{mi.getsize()}表示在当前时间之前收到的一个消息的数据大小；n1表示当前时间之前该节点成功接收到的消息总数。

节点作为源节点产生的消息的计算公式为：

(5)

当节点产生一个消息时，获取该消息的数据大小，并计算在当前时间之前该节点产生的所有消息的数据总和。Created{mi.getsize()}表示该节点在当前时间之前产生的一个消息的数据大小；n2表示当前时间之前该节点产生的所有消息总数。

节点成功传输的消息的计算公式为：

(6)

当节点成功传送了一个消息时，获取该消息的大小，并计算当前时间之前该消息成功传送的所有消息的数据总和。Transferred{mi.getsize()}表示该节点在当前时间之前成功传送的一个消息的数据大小；n3表示当前时间之前该节点成功传输的所有消息的总数。

所以节点的历史吞吐率的计算公式为：

(7)

式1改进后为：

P(a,b)=P(a,b)old+(1-P(a,b)old)×

Pinit×α

(8)

其中

α=(1+HtHt)/2

(9)

其中，Ht表示节点的历史吞吐率。由于Ht≤1,所以1+HtHt≤2，(1+HtHt)/2≤1,由此保证了P(a,b)≤1。当该节点未成功传送消息时，式8将退化为式1。

当携带消息的节点遇到一个中继节点，在携带消息的节点到目的节点的传递概率和中继节点到目的节点的传递概率相同的情况下，当中继节点的历史吞吐率比当前携带消息的节点的历史吞吐率大时，由式8可知，由该中继节点传送成功的概率大于自身节点直接传送的概率，那么携带消息的节点应该把消息传递给相遇的中继节点，经由该中继节点把消息传送到目的节点。通过仿真可以看出，改进后的概率路由算法相比原始的概率路由算法在消息的递交率、传输时延和开销率都有所提高。

3 仿 真

3.1 仿真环境设置

文中采用one仿真[15-16]平台来评估Prophet路由和E-Prophet路由的性能。one是基于Java语言开发的专用于仿真DTN路由的一款仿真工具。仿真采用one自带的赫尔辛基市的地图。区域大小为4 500 m×3 400 m。在区域中放置了126个节点，这些节点被分为6组。其中第一组和第三组为行人，每一组包含40个节点，共80个节点，移动速度范围为0.5～1.5 m/s，节点缓存大小为5 MB，移动模型为基于地图最短路径移动；第二组为出租车，含有40个节点，移动速度范围为2.7～13.9 m/s，节点缓存大小为5 MB，移动模型为基于地图最短路径移动；第四组、第五组和第六组为有轨电车，每一组包含2个节点，总共6个节点，移动速度范围为7～10 m/s，缓存大小为50 MB，移动模型为基于地图的固定路径移动；消息产生的时间间隔设置为25～35 s；消息的大小设置为350～500 k；节点采用蓝牙设备进行传输，其传输范围为10 m，传输速度为250 Kbit/s。当缓冲区已满时，节点不会再接收新消息，直到一些旧的消息从缓冲区被删除。

3.2 网络性能指标

在DTN中，为了能够更好地评判路由的好坏，往往采用一些合理的性能指标对不同的路由进行性能评估。文中主要采用消息递交率、网络开销率和平均时延来评价Prophet路由和E-Prophet路由的性能。

(1)消息递交率。定义为DTN网络中成功递交的消息数和总的消息投递数的比值。路由的作用就是要把一个消息送达目的节点，所以递交率是一个很重要的性能指标。

Delivery_rate=Delivered/Created

(10)

其中，Delivery_rate表示消息的递交率；Delivered表示DTN网络中成功传递到目的节点的消息总数；Created表示在源节点生成的所有消息总数。

(2)网络开销率。定义为没有被成功投递到目的节点的消息与被成功投递到目的节点的消息数量的比值。此参数用来评价成功传输消息而要额外传递的消息的概率。该参数越小，网络开销越小。

(11)

其中，Overhead_ratio表示网络的开销率；Relayed表示网络中没有被成功投递到目的节点的消息总数；Delivered表示网络中被成功投递到目的节点的消息数量的比值。

(3)平均时延。定义为所有成功递交的消息从源节点到目的节点花费的平均时间。平均时延越小，表示节点从源节点到目的节点所花费的时间越少。在DTN网络中，这是一个很重要的参数。

(12)

其中，Latency_avg表示消息的平均时延；tid表示消息i被目的节点接收到的时间；tis表示消息i在源节点生成的时间；n表示被目的节点成功接收到的消息的总数目。

3.3 仿真结果

采用one对在DTN网络中常用的Prophet路由和改进的E-Prophet路由进行了仿真和比较。两种路由协议在DTN中的消息递交率、开销率、传输时延三种性能指标的变化趋势如图1～3所示。

由图1可以看出，随着仿真时间的增加，两种协议的递交率也在增加。仿真刚开始时，节点的吞吐率并没有显现出来，这可能是因为仿真刚开始时各节点的性能差异并未显现出来。随着仿真时间的增加，各节点的性能差别逐渐显现，节点的历史吞吐率在一定程度上反映了一个节点在性能上的优劣，所以改进的Prophet路由表现了比未考虑节点吞吐率更好的性能。

图1 两种路由的消息递交率

图2 两种路由的开销率

图3 两种路由的平均时延

由图2可以看出，随着仿真时间的增加，两种协议的网络开销都在不断增加。E-Prophet的网络开销增加相比Prophet要慢。由公式可以看出，吞吐率大的节点相对概率也会高，从而路由将选择出节点性能相对更好的节点来传输消息，所以E-Prophet路由相对普通的Prophet所需要的网络开销更少。

由图3可以看出，仿真开始时，E-Prophet路由的平均时延并没有表现出很好的性能，这可能是因为首先由于路由当中加入了对节点吞吐率的判断，携带消息的节点在选择中继节点时需要计算中继节点的吞吐率，所以会导致一定的时间开销。然后，在仿真开始时节点之间的吞吐率性能差异不大，根据节点的吞吐率不能很好地判断出节点的优劣。但是随着时间的增加，各节点的吞吐率差异逐渐增大，节点的吞吐率可以在一定程度上反映一个节点的优劣，所以消息到达目的节点的时延会相对减少。平均来讲，随着仿真时间的增加，改进的E-Prophet的平均时延会比传统Prophet路由的平均时延要小。

E-Prophet路由考虑到了网络节点的历史吞吐率对消息传输概率的影响，通过改进Prophet路由算法提高了消息的传递成功率。仿真结果表明，E-Prophet路由在递交率、网络开销和平均时延上表现出了比Prophet更好的性能。

4 结束语

由于DTN中节点的特殊性及所处的特殊网络环境，节点的性能会对节点成功传递消息产生很大的影响。因此考虑节点性能对消息传输的影响是十分必要的。通过改进DTN网络原有的Prophet路由改善了节点传输消息的成功概率、开销率等。仿真实验表明，与原有的Prophet路由相比较，改进后的E-Prophet路由在递交率、网络开销和平均时延三方面都有了一定的改进。但是由于DTN网络的不稳定性，导致距离当前时间很远的节点性能对当前节点性能的参考价值不是很大，所以该方法也具有一定的不准确性。因此下一步的研究工作是根据时间分段来优化该路由策略，弱化距离当前时间很长的节点性能对当前节点性能的影响，以达到更好的路由效果。