基于半衰期的剩余路径投递时间估计优化

2018-07-18吴比王菲姜胜明

现代计算机 2018年18期

吴比，王菲，姜胜明

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

0 引言

无线自组织网络[1]中由于节点具有较强的移动性使得网络自身动态性很强，如何才能提供更优的服务质量（Quality of Service,QoS）成为了无线自组织网络面临的一个重要问题。差分队列服务[2][3]（Differentiated Queueing Service,DQS）作为一种以数据包为粒度的队列调度算法，可在无线自组织网络这种环境下根据服务质量要求和路径状况调整包的发送次序，致力于将真正紧急的数据分组优先转发。路径状况主要指剩余路径的投递时间，即该数据分组在离开本节点到达目的节点这段路径上还需要的时间信息。由此，如何进行剩余投递时间估计成了差分队列服务的核心问题。

文献[4]给出了机会网络是一种源节点和目的节点之间不需要存在完整链路，而是利用节点移动所带来的相遇机会实现通信的自组织网络。具体表现形式就是，机会网络中节点依靠移动形成通信机会，进行逐跳地传输消息，以“存储-携带-转发”的路由模式实现节点间通信。

文献[5]提出了一种应用于DQS的基于半衰期的剩余路径投递时间的估计方法，该方法包含了一种基于半衰期的历史信息有效性计算方法，但是在该方法中半衰期值是根据场景参数计算得来的固定值，无法适用动态拓扑网络的变化，本文提出一种自适应的半衰期获取方法，通过仿真测试了优化前后剩余路径投递时间估计方法的精度。

1 相关方法与优化

1.1 一种基于半衰期的剩余投递时间估计方法

（1）基于半衰期的历史信息有效性计算方法

历史信息有效性是指在当前时间，一个历史信息用于估计或预测时所具有的价值。该方法依据历史信息记录的登记时间距离当前时间的跨度，每经过一个半衰期时间信息有效性减半的原则，计算历史信息记录在当前时间的有效性。信息有效性υ的数值范围是（0，1）。

设网络场景的平均通信半径为l,单位为米，场景面积为r单位平方米,网络系统中节点个数为n，单位米，网络节点的平均移动速度为s单位为秒，半衰期λ的计算公式如下：

信息有效性v的计算公式如下：

公式中，τn表示该信息的登记时间m与当前时间tn的时长差，即τn=tn-m。

在实现过程当中，网络节点需要记录当前时间与数据分组在源节点的生成时间之差并将其作为一个历史信息记录，即当前节点与源节点之间所在路径上的历史实际投递时间，从源节点到当前节点的相反路径方向定义为反向路径，当有数据分组经过此节点到达源节点时，此记录作为该分组的一次剩余路径时间。

（2）剩余路径投递时间估计方法介绍

一个分组剩余投递时间的估计值等于其剩余路径的反向路径上的历史实际投递时间以其信息有效性为权重的加权均值。例如，从本节点到目的节点d的投递时间估计值：

其中τd,j表示保存在此节点上的从d节点到本节点的第j个历史实际投递时间，vd,j表示反向路径历史实际投递时间τd,j所对应的历史信息有效性。

在实现的过程中，数据分组需要在头部携带两个字段：该数据分组的最大端到端时延与源节点的生成时间。数据分组的离开时间等于数据分组生成时间加上其自身最大端到端时延，然后减去剩余路径时间，最后节点依据数据分组的离开时间进入队列，使紧急的数据分组优先转发。

虽然这种估计方法在相对短暂且稳定的时间内有较好的准确性，但是这种方法是基于半衰期值计算历史信息记录有效性的，而半衰期值使用的是基于场景参数计算而来，包括了场景面积、节点数量、移动速度，节点通信半径等，该半衰期值是一个固定值。而无线自组织网络中，节点移动具有很强的随机性，难以获取这些参数信息，因而这种半衰期在实际部署时不具有可行性。而且，当中间节点没有有效的历史信息记录时，该方法失去了估计的依据，而变得不再可用。

1.2 剩余投递时间估计方法的优化过程

（1）自适应半衰期的获取方法

原方法中半衰期使用网络场景参数通过计算获得，是一个固定值，虽然基于网络场景参数，却难以适应动态拓扑网络环境造成的历史信息记录准确性较低的情况，因而提出一种自适应的半衰期[6]获取方法，自适应网络的变化。

为了方便介绍该自适应半衰期获取方法，引入以下变量：

表1 自适应半衰期获取方法中变量名称与含义

其中，关于thalf的计算公式如下：

然后在历史信息记录表中选择登记时间与thalf时间最接近那条历史信息记录，设其登记时间tmid。则当历史信息记录条目数量大于等于3时可得半衰期值：

而当历史记录数只有一条，其信息衰减的意义不大，半衰期可以设为一个任意大于零的常数。因为在这种情况下，在对一条历史信息记录求加权均值，其有效性大小不影响最终结果。当历史记录数只有两条时：

历史信息记录表中所有历史信息记录的登记时间跨度为信息有效性的衰减过程，将中间值时间定义为半衰时间，即thalf，找到临近中间时间的历史信息记录条目，可认为该历史记录为半衰的历史信息记录条目，即tmid，当前时间与其相减得出半衰期值。为了更直观地描述上述自适应半衰期方法，如图1中，在整个历史信息记录表中，最新历史信息记录到最旧历史信息记录，其信息有效性依次衰减。其中ti最接近中间时间，则认为ti到tn的时间跨度为一个半衰期值：

图1 实际路径时间信息有效性衰减信息图

这样处理，一方面有利于提高历史信息记录表的利用率，更加符合半衰期定义的本意，同时，无需得知网络场景中诸如节点移动速度、节点数量、场景面积等等复杂又难以获取的参数信息，可以适应网络中不同的数据分组传输速率，都将进行信息有效性区分。

（2）目的节点向源节点的回包机制

具体方法：当节点收到一个数据分组，而节点在本地又缺乏有效历史信息记录，通过改变该数据分组携带的“标记位”，并最终转发到目的节点，目的节点识别该“标记位”后，会反向给源节点回复一个数据分组，其回复的数据分组采用与接收到的分组同样的大小。因此该回复数据分组机制将有利于补充中间节点缺乏历史信息记录的情况，从而增强该估计方法的应用性。

其中“标记位”的结构如图2，次末位置1代表节点无该数据分组的路由：

图2 数据分组携带的信息标记位

该方法具体处理过程可用下面的流程图说明，如图3所示。

信息有效性总和是否为0的判断，在于确定节点历史信息记录是否已全部老化，当历史信息记录过于陈旧则进行剩余路径投递时间估计时精度难以保证。因此需要回包机制以补充有效的历史信息记录，提高剩余路径投递时间的估计精度。

图3 目的节点向源节点回包机制流程图

该回复数据分组的机制不同于广播探测包的过程[7-8]，而是普通的源节点与目的节点之间正常的单播发送数据包过程，而且如图3所示的控制机制，可以有效控制发包量，仅仅进行最低限度的发包，在一定程度上可以避免增大网络拥塞。但是可以有效获得剩余路径投递时间，创建有效的历史信息记录，提高该基于半衰期剩余路径投递时间估计方法的应用性。

2 仿真和结果

2.1 仿真参数

本文所涉及的所有实验都使用的是EXata，此平台由美国SNT公司所开发的，允许用户更加快速真实地评估网络性能。本文将机会网络的链路连通性低、拓扑结构变化频繁这个特点用节点移动速度的改变来模拟，从而测试在五个不同场景下的剩余投递时间估计方法优化前后的估计精度。

考察数据分组剩余路径投递时间估计方法的估计精度关键在于估计值与实际值的差异。这两者差异越小可认为估计的剩余路径投递时间准确性越高。因此，为了将剩余路径投递时间的估计值与数据分组实际的剩余路径投递时间进行比较，并得到其误差情况，本节将估计误差比当作估计精度的性能指标：

本实验主要分五个场景：

2.拓宽绿色通道范围。在活畜禽流通免收过路费的基础上，对鲜畜禽产品运输及当日当次返空车辆实行“绿色通道”。

表2 场景参数设置

表3 仿真场景节点平均移动速度参数信息

2.2 仿真结果

在实验中，通过调节节点的平均移动速度，得到各个场景数据分组的估计精度区间。需要说明的是，在本节仿真实验中，将优化后与优化前基于半衰期剩余路径投递时间估计方法的差分队列服务分别设为DQS1和DQS2。此外，在估计精度区间结果图中，横坐标10代表估计精度10%以内，20代表估计精度位于10%到20%之间，30代表估计精度位于20%到30%之间，40代表估计精度位于30%到40%之间。而50代表了所有估计精度大于40%的情况。

DQS1的估计结果如图4所示，DQS2的估计结果如图5所示。

图4 DQS1估计精度结果图

图5 DQS2估计精度结果图

通过观察图4与图5可以大致看出，估计精度位于10%到40%之间，其比例都比较小，位于10%以内的比例最大，因此可以大致认为，该基于半衰期的剩余路径投递时间估计方法在多数情况下，估计精度较高。而同时，仍然有较高比例其估计精度大于40%，说明存在着较大的估计误差。并且，优化前后其估计精度在10%以内和大于40%以外的差异最为明显，分别代表着估计最准确和最不准确的比例。也是最能体现估计精度差异的两个精度区间，下面图6与图7分别对比这两个估计精度区间的情况。图6为其估计精度在10%以内的比例，图7其为估计精度在40%以外的比例：

图6 实验一中DQS1与DQS2估计精度在10%以内对比图

图7 实验一中DQS1与DQS2估计精度在40%以内对比图

从横向看，场景一到场景五，节点移动速度在持续增大，而不同的节点移动速度下节点相遇的情况是不同的，拥塞程度、信道竞争激烈程度也有差异，因而各个仿真场景中的仿真结果不具有必然的联系。从纵向看，每一个仿真场景中节点的运动轨迹是固定的，拓扑结构的变化是固定的。观察估计精度10%以内的情况，DQS1的比例要高于DQS2的，在估计精度大于40%的情况看，DQS1的比例要低于DQS2的。因此，从总体而言，优化后的基于半衰期剩余路径投递时间估计方法，其估计精度是有所提高的，具体表现为：估计精度较高比例有所提高的同时，其估计精度较低的比例明显下降。