一种自适应路径状态探测方法

夏铭远，吴比，王菲，姜胜明

（上海海事大学信息工程学院，上海201306）

0 引言

机会网络是一种特殊的移动自组织网络[1]，源于延迟容忍网络[2]和移动自组网[3]。其主要的特点是其不依赖于固定的基础设施，节点之间的通信完全是靠节点自身的移动带来通信范围的重合。由于机会网络的这种通信方式，导致传输时延长，且传输成功率较低。路径的选择在提高传输成功率和降低传输时延中具有极其重要的作用，因此准确地获取路径以及节点的相关信息对于更好地辅助路由选择具有十分重要的意义[4]。

在之前的研究中，基于发送探测包的方法探测路径和节点信息在路径寻找中虽然起到一定作用，但是针对不同长度的数据包，探测信息的收集方法没有较好的自适应性[5]。本文针对上述问题提出一种自适应路径状态探测方法，可以更加准确地反映路径状况，更加可靠地用于估算后续不同长度数据包的时延信息，从而更好地辅助路由选择。

1 相关方法与优化

1.1 基于探测包的机会网络信息收集方法

（1）基于探测包的机会网络连通性量化方法

机会网络的连通性量化方法的基本思想是：源节点向目的节点发送探测包，然后根据收到的目的节点发送的返回包ACK 来大致估算网络的连通性。图1为测量连通性方法流程图，一共包括下面三个部分：①发送探测包，其中探测包的发包频率由源节点根据收包和发包的关系来进行变化和调整；②应答探测包，其中应答探测包分为两种，一种发送方是目的节点，另一种发送方是非目的节点；③源节点根据收到的应答包数量与发送的探测包数量的比值来衡量网络连通状态。

源节点在T 时间段内向目的节点发送探测包，探测包的发送频率为fs，发送数量为num 个，若目的节点向源节点发送的连通应答包为m 个，那么在时间T 内的数据成功传输概率为P=m/num。由此，使用此比值P 来量化机会网络连通性，同时也用P 来衡量机会网络中两个节点之间路径存在的机会程度[6]。

图1 连通性测试流程图

（2）基于探测包的剩余路径投递时间估计

在剩余路径投递时间的研究中，路径中的所有经历的节点都发送带有时间戳的探测包给其邻居节点，当邻居节点收到探测包以后，同时加入自己的时间戳，并将探测包继续转发给其他邻居节点，这样根据两个时间戳的差值即可得到一个单向的时延[7-8]，节点不仅可以获取到自身的时延还可以获取到邻居节点发送数据分组的时延。所有节点共同维护一个时延表，节点可以通过广播时延表的操作使邻居节点收到表后立即更新自己的时延表，并且将时延表中改变的部分继续广播给其他节点。

这种基于发送探测包的剩余路径投递时间估计方式主要特点在于可以利用所有节点共同维护的时延表来估计剩余路径的投递时间[9]。

（3）探测包研究方法分析

利用探测包获取网络信息存在的最大的问题是由探测包和数据包长度的不同而带来的在网络中的差异，无法对数据包有较好的适用性，想要将发送探测包探测的结果应用到后续发送不同数据包的过程中具有一定的困难。

1.2 基于发送探测包的自适应性路径信息的探测方法

（1）探测包在路径中探测的信息及具体探测方法

为了提高探测信息对数据包的适用性，本文提出的一种基于发送探测包的自适应性路径信息的收集方法。该方法主要通过源节点向目的节点发送探测包，目的节点接收到探测包后将探测信息以回复包的方式反馈给源节点实现的。其中，探测包在路径中所收集的信息主要包括路径上节点的总发送时延倒数之和、路径的平均等待时延以及链路可靠性。探测收集到的信息可以用于估算后续发送不同长度的数据包所经历的时延信息，同时可以更加精确地获取节点以及路径状况，源节点可以通过探测包收集到的信息进行不同路径的选择。

①路径总发送时延的信息收集及其方法

针对路径中总发送时延的信息收集方法，即源节点通过探测包计算发送不同数据包时路径中的总发送时延，这里所述的计算不同数据包在路径中总发送时延的方法是：将探测包所经历所有节点的发送速率的倒数进行求和，且用S 表示：

然后用上述求和结果S 与H 的乘积求出发送不同长度的数据包时路径中总发送时延Ts，即：

其中Vi代表探测包在第i 个节点的发送速率，H代表发送的不同数据包长度。

②路径平均等待时间的信息收集及其方法

源节点通过探测包获取路径的平均等待时间，这里所述路径的平均等待时间是用路径中所有节点的平均等待时间之和计算的，假设路径中每个节点的平均等待时间为，路径平均等待时间为

路径中每个节点的平均等待时间，是指经历某个节点的所有包的等待时间的平均值，具体计算方法是：将到达某一节点的所有包的发送时刻与到达时刻分别求和并相减，最后除以包的数量，假设n 个包经历某一节点时，到达时刻分别为t1,t2,…,tn，即将发送的时刻分别为T1,T2,…,Tn，该节点的平均等待时间为：

②链路可靠性信息的收集及其方法

链路可靠性反映的是某条路径的可靠程度，本文将其具体量化为目的节点的收包数量与源节点发包数量的比值。相对于源节点的发包数量而言，目的节点收到的包的数量越多，说明这条路径上的丢包率越少，路径越可靠。节点转发数据分组并进行选路的过程中也更倾向于选择这样相对稳定的路径。因此，我们用目的节点收到的探测包数量a 与源节点的发出探测包的数量b 的比值P 来反映该链路的可靠性，即：

④方法的优点与合理性

机会网络中由于探测包较短而数据包较长，使得探测包探测的数据一直没有较好的方法可以应用数据包。而上述提出新的方法可以通过向目的节点发送探测包来获取整个链路的总发送时延、平均等待时延以及链路可靠性，并且这种方法对于数据包具有较强的适应性，可以用于估算后续不同长度的数据包所经历的时延信息，获取的结果具有广泛性和准确性。同时，可以更加准确地获取节点以及路径状况，大大提高通信效率，这对于机会网络中路由的选择和路径的评价具有十分重要的意义。

（2）探测包信息收集过程

源节点根据探测包收集的信息进行不同路径的选择首先需要得到目的节点的反馈信息，因此我们将路径总发送时延信息、路径平均等待时延信息以及链路可靠性信息全部放在目的节点发送的反馈包中一起返回给源节点。

源节点只有在收到目的节点发来的反馈信息才能得到整个链路的信息。但是在探测包被转发过程中可能会由于丢包等问题无法到达目的节点，此时目的节点将无法向源节点发送反馈包，该条记录的信息收集失败。所以探测包在每到达一个节点时首先要判断当前节点是否为目的节点，然后做出相应回复。

①若当前节点为目的节点，则目的节点回复一个带有所有节点发送速率的倒数求和S、路径平均等待时间和目的节点实际收包数量b 信息的确认包给源节点，如图2；

图2 目的节点回复确认包示意图

②若当前节点为非目的节点，则侦听在Δσ时间里是否有其他节点转发该探测包，若没有，当前节点回复失败反馈包给源节点，说明该探测包无法到达目的节点，若有，则继续转发探测包，如图3；

图3 非目的节点回复失败反馈包示意图

其中上述Δσ 的取值为源节点平均每发送两个探测包之间的时间间隔，若源节点在Time 时间内发送m个数据包，Δσ 取值为

具体探测过程如图4 所示。

图4 节点转发探测包流程图

2 仿真和结果

利用探测包估计的数据包总发送时延的精度的大小作为网络路径信息收集方法性能的主要评价参数，在对提出的基于发送探测包的自适应性路径信息的收集方法的性能测试中，本文将其作为主要的评判标准。

2.1 仿真场景及参数设置

为了搭建符合机会网络特征的仿真场景，验证探测包估计的数据包时延信息与发送真实数据包的时延信息的差异性，分别在节点静止和节点随机移动的场景中进行试验。两个场景的基本参数大致相同，表1为场景一的基本参数信息，表2 为场景二的基本参数信息，分别在EXata 仿真平台上进行五次实验。

表1 场景一参数设置

表2 场景二参数设置

2.2 仿真结果

实验主要是通过控制节点保持静止或运动这两个状态下，研究发送数据包的总发送时延的真实值与通过探测包估计的值之间的差异。静态实验的设计是为了模拟在网络拓扑不发生变化的情况下，研究探测估计值的准确性。通常情况下静态属于机会网络中的一个短暂的中间状态，这样的实验设计有利于分析估计精度与两个状态之间存在关系，从而更加全面的分析探测结果的准确性。

图5 场景一估计值与真实值对比图

在场景一中节点保持静止状态的实验中，五次试验的估计值并无明显差异，且较为稳定；而真实值虽然有略微变化，但变化不大。从纵向上来看，每次试验结果的真实值与估计值都无显著差异。这个结果说明在拓扑结构不发生改变时，用探测包估计的数据包路径总发送时延与真实时延并无较明显差异，估计值较为准确，可以用探测包的方法来估计数据包在路径中的总发送时延。

图6 场景二估计值与真实值对比图

在场景二中节点保持运动状态的实验中，五次试验的估计值无明显差异，且较为稳定；而真实值虽然有略微变化，但变化不大。从纵向上来看，每次试验结果的真实值与估计值都无显著差异。这个结果说明在拓扑结构发生变化时，用探测包估计的数据包路径总发送时延与真实数据包仿真结果也无较明显差异，且估计值较为准确，可以用探测包的方法来估计拓扑结构发生变化的网络中数据包在路径中的总发送时延。

图7 两个场景误差比对比图

为了将估计的总发送时延与真实数据包在路径中总发送时延进行比较，并得到误差的准确情况，本节将探测包估计的总时延Te和数据包实际发送的总时延Ta之差与数据包实际发送的总时延之Ta比求得误差比B作为衡量估计精度的性能指标：

通过上述图7 可以看出：横向上，场景一和场景二中五次试验的误差比虽然都有差异，但是由于其误差比数值差别较小，并且两个场景的五次试验误差比有差异的原因可能是由于网络中环境位置等因素所带来的影响，因此在拓扑结构不发生变化的情况下，认为实验一中两个场景的五次试验其各自的误差比无显著差异。从纵向上看，五次试验中场景二的误差比总是高于场景一，反映了本方法在动态网络的估计精度相对于静态网络要低一些，产生这样结果的主要还是由于动态网络中节点的移动、找路、转发等过程带来的影响。

3 结语

通过仿真实验，分析了优化后的基于探测包的自适应性路径信息收集方法在静态和动态拓扑环境下的性能。实验证明，无论是在静态拓扑结构还是动态拓扑结构的网络中，本文提出的基于发送探测包的自适应性路径信息的收集方法都具有较好的性能，其探测信息可以应用到预估数据包的发送过程中。