DTN是一种特殊的无线网络，这种网络往往具有以下部分或全部特征：通信节点运动剧烈、通信链路带宽受限、通信环境条件恶劣、通信过程容易被遮挡和受到干扰，存在多种通信模式的异构子网等^[1]。DTN在实际中具有广泛的应用，主要应用在军事上的战术互联网^[2]、城市中的车辆网^[3]、各种各样复杂环境下的传感网^[4]等领域。

DTN的特点最终表现为整个网络不能维持稳定的基于TCP/IP的通信，传统路由协议性能下降，无法完成拓扑维护和组网要求。针对DTN的特点，文献^{[5, 6, 7, 8]}提出了一些新的路由算法和机制，并均采用了存储转发技术和多副本路由。这些算法尽管提高了性能，但是在提高某一性能指标上存在较大的偶然性^[9]。为了提高算法对某度量的确定性，文献^[9]提出的RAPID算法通过构造针对某度量的优化函数，优先保证效能函数最优的报文的递交和复制，并在实践中进行了成功应用。然而该算法采用指数分布作为节点间的相遇时间，只是为了计算方便，没有理论依据，在其他场景下是否足够和可行尚未可知。一些研究把位置信息应用到DTN的路由中来，文献^[10]中的节点通过从锚节点周期性的接收信标报文获得节点的定位和移动信息，提高递交成功率，其实质是一种有中心的拓扑结构，当锚节点失效时网络将陷于瘫痪。文献^[11]中仅预测了目标节点的位置，且当副本数为1时采用贪婪转发，导致副本数量增加，影响了算法的性能。文献^[12]中利用了独立的general packet radio service(GPRS)网络模块获取各节点的位置信息，形成全局拓扑，但需要额外GPRS网络的支持，增加了系统的复杂性和费用，对于GPRS网络覆盖不到的地方无法应用，不适用于独立DTN的部署。文献^[13]提出了一种基于位置信息的DTN城域公交网络，该网络借助于bus information system(BIS)数据库的支持获得精确的目的节点方向，并在该方向转发数据，获得良好的性能，但对于BIS的依赖限制了其应用范围。文献^[14]利用了节点的位置信息、速度和移动方向，通过计算更容易接近目的节点的中间节点来转发数据，获得较好的性能，但算法中采用最近一次和目的节点相遇的节点的信息来决定转发方向，若相遇后经过时间太长，其所采用的位置信息已经失去参考价值，算法性能急剧下降。

针对以上算法的优缺点，借鉴文献^[9]的思路，本文研究仅继承了RAPID的流程，完全抛弃了其最核心的效能函数计算方法，重新设计了基于位置信息的效能函数模型，该模型的设计思路是尽可能把报文复制给向目的节点方向移动的中间节点，随着向目的节点方向的移动，目的节点的信息越来越精确，报文就更容易被递交。

当节点X和Y相遇时，协议流程如图 1所示。

图1

图1PRR协议流程图

对于图 1中任意节点 $V$ ，其报文 $i$的效能函数定义为：

式中， ${{x}_{V}},{{y}_{V}} $ 是节点V的横纵坐标； ${{x}_{D}},{{y}_{D}} $ 是报文i的目的节点D的横纵坐标；R是目的节点D的传输半径。

在式(1)中，当节点V在目的节点D的传输范围内时，可以直接传输到目的节点，设置其效能函数为负无穷大，这样就能保证 $\delta {{U}_{i}} $ 足够大，从而使该目的的报文优先被复制。当节点V不在节点D的传输范围时，设置效能函数为节点V预期达到目的节点D传输范围内的时间，该时间t计算方法如图 2所示，图中V₁、D₁分别节点V和目的节点D的移动方向矢量。

图2

图2效能函数计算示意

节点V到点 $(x,y) $ 的时间t由以下方程组求出：

式中， ${{\alpha }_{V}},{{\beta }_{V}}$是矢量V₁的方向角； $ {{\alpha }_{D}},{{\beta }_{D}}$是矢量D₁的方向角；${{v}_{D}},{{v}_{V}} $是节点D和节点V的移动速度。

由式(2)可获得关于t的二元一次方程，若方程有解，则选取最小的一个值作为t值；若方程无解，选取 $+\infty $ 作为t值。在应用中，根据应用场景设置一个足够大的数 $U\_\text{MAX} $ 作为 $+\infty $ ，则 $-U\_\operatorname{MAX} $ 作为 $-\infty $ ，当节点X和Y相遇时，在同等大小报文条件下，会产生以下报文复制优先级情况，如表 1所示。

表1

表1 报文复制优先级分布

表1 报文复制优先级分布 $U_{X}^{i}$ 有解 $U\_\text{MAX} $ (无解) $U_{Y}^{i} $ 有解 $U\_\text{MAX} $ $-U\_\text{MAX} $ 有解 $U\_\text{MAX} $ $-U\_\operatorname{MAX} $ $U_{X}^{i}-U_{Y}^{i} $ >0 ≤0 趋于 $-\infty $ $+\infty $ 》0 0 $+\infty $ 优先级 较高 低 最低 最高 高 较低 最高

需要说明的是， $U_{Y}^{i} $ 为 $-U\_\text{MAX} $时，节点Y位于到目的节点的最后一跳，不管 $U_{X}^{i}$的值如何，此时的优先级都是最高。此外， $U_{X}^{i}$的值不可能为 $-U\_\text{MAX} $，(若为该值，表示节点X在目的节点D的传输范围之内，按照协议设计，报文已直接被递交，不需要复制)。

为了实现上述效能函数的计算，节点之间在相遇时需要交换足够的信息，节点在运动中通过不断收集这些元数据，完成效能函数的计算，节点X需要从节点Y获得的元数据(反之亦然)包括：1) 节点Y的平均速度，由节点在运动过程中周期性测定；2) 节点Y的当前位置坐标，由节点内的内置GPS模块提供；3) 节点Y缓存的报文的编号；4) 节点Y的邻居节点位置列表，该列表包括节点Y经历过的所有邻居的最近N个采样周期内的位置信息，若采样数量不足N，则Y中存储实际次数；若采样数量大于N，则Y中存储最近的N次。对于每个邻居的位置信息，其数据结构如图 3所示。

图3

图3节点位置数据结构

在图 2对效能函数的计算中，需要知道节点的移动矢量，即要获得节点的 $ {{\alpha }_{V}} $和 $ {{\beta }_{V}} $。对于相遇的两个节点X和Y，由于有实时的运动数据，可以通过最近的两次位置采样数据计算出来。然而对于某个报文的目的节点D的运动方向 $ {{\alpha }_{D}} $和 ${{\beta }_{D}}$，如果有其最近的两次采样时间的位置信息，则可以直接计算，否则需要预测其最近两次采样时间的位置信息来完成计算。

每个节点在加电启动后，都会每隔T时间对本节点的位置信息采样一次，每个节点在缓存中保存最近的N次采样，如果节点X中保存的节点D的最新位置信息的时间戳是 $ {{T}_{D}} $，当前时间为 $ {{T}_{C}} $，则需要预测节点D的 $ ({{T}_{C}}-{{T}_{D}})/T $个位置信息，并利用最新的两个信息来确定节点D的移动矢量。

本研究中采用灰色预测方法来预测目的节点的位置信息。灰色预测法是一种对含有不确定因素的系统进行预测的方法，对在一定范围内变化的、与实践有关的灰色过程进行预测，具有宽广的应用领域^[15]。采用该方法主要是因为是灰色预测方法简单易行，适用于在一定范围内波动的数据预测，对数据分布没有具体的要求。

为了评估本研究中用到的仿真模型对灰色预测的适用情况，对研究中采用的random waypoint移动模型产生的数据进行了灰色预测分析，来观察灰色预测对random waypoint移动模型坐标的预测情况。在NS仿真工具下，放置一个节点按照random waypoint模型进行运动，在500 m×500 m区域内，节点运动速度10 m/s，暂停时间1 s，每隔40 s记录一次节点的X轴坐标，如表 2所示。

表2

表2 random waypoint 坐标数据

表2 random waypoint 坐标数据 时间/s 0 40 80 120 160 200 240 280 320 360 400 坐标值/m 143.4 90.8 70.4 30.3 56.4 110.5 208.2 174.6 324.3 143.3 360.1

根据上述数据，采用GM(1,1)模型，获得预测方程：

方差比 $ C=0.574<0.65 $，残差概率 $ P=1 $。

由结果可知，模型精度基本合格，所以采用灰色预测模型对节点的运动方向进行预测是可行的。

本文采用NS网络仿真工具对本文提出的PRR算法和RAPID算法的性能进行比较，仿真主要用到的参数如表 3所示，其他没有列出的参数同文献^[9]。

表3

表3 仿真参数表

表3 仿真参数表 仿真参数 值 区域大小 1 500 m×1 500 m Mac协议 IEEE 802.11 DCF 物理层模型 PHY802.11b 最近位置采样值数量N 10 采样时间间隔T/ min 1 报文大小/Byte 512 仿真时间/s 600

图 4～图 6是在20个节点情况下的仿真结果，节点移动速度为10 m/s，横轴为每50 s源和目的节点产生的报文数。每个成功到达报文的平均延迟的比较结果如图 4所示，可看出随着报文产生数量的增加，在节点密度不变的情况下，缓存中等待的报文数增加，延迟增加。RAPID算法由于无法较为准确的估计节点间的相遇时间，而本文的算法直接向节点的移动方向发送报文而获得更少的延迟。两种算法成功递交率的比较效果如图 5所示，可看出本文的算法由于在大概方位上的确切计算，使得报文在被丢弃前更容易在某个方向上到达目标节点，但随着报文数的增加，成功递交率下降。

图4

图4平均延迟的比较(产生报文数变化的情况)

图5

图5成功递交率的比较(产生报文数变化的情况)

图6

图6消息复制个数的比较(产生报文数变化的情况)

图 6显示了本文的算法在保证性能的情况下具有更小的消息复制数，这主要基于两个原因：1) 本文算法消息的传播具有方向性，在一定时间内沿某一方向复制；2) 制定了更详尽的消息复制规则，对报文复制有了更详细的限定，可以有效减少消息的复制数量。

图 7和图 8是在移动速度为10 m/s，每个源和目的节点对每秒产生1个CBR流的情况下的仿真结果，横轴是网络中的节点数。和图 4、图 5相比，在网络产生报文数不变的情况下，随着节点的增多，每个节点获得更多的到目的节点的信息，效能函数的计算值更精确，到目的节点的转发路径更多，这些均导致到达目的节点的延迟更少，报文被成功递交的概率更高，如图 7和图 8所示。

图7

图7平均延迟的比较(节点数变化的情况)

图8

图8递交率的比较(节点数变化的情况)

图9

图9复制消息数的比较(节点数变化的情况)

图 9描述了当前仿真条件下消息复制数量的变化情况，由于节点数增加，参加消息复制的节点数增加，消息被复制的数量增大。但当节点密度增加到一定程度后，由于有更精确的到达目的节点的路径信息，此时有些节点就不需要做无用的复制，所以尽管节点数增加，但消息的复制数量反而有所下降。

本文在RAPID的算法的基础上，借鉴了原算法的效能函数的概念克服DTN路由算法的偶然性问题，通过引入位置信息预测和设计新的效能函数计算方法改进RAPID算法中的效能函数的不确定性。仿真表明，本文提出的算法在提高网络性能的同时，减少了消息复制的数据量，获得较满意的效果。