一种基于移动预测和时延预测的OLSR路由方法及系统

摘要

本发明提供了一种基于移动预测和时延预测的OLSR路由方法，包括簇成员节点路由表计算过程和簇头节点路由表的计算过程，所述簇成员节点路由表计算过程为：采用卡尔曼滤波算法建立移动预测模型，并通过此模型来选择稳定性高的邻节点作为下一跳节点，以此来建立簇内成员节点路由表；所述簇头节点路由表的计算过程为：将数据包在簇头节点MAC层的排队时延作为路由选择的度量因子，通过ARMA算法建立排队时延的预测模型，以此模型来计算簇头节点的路由表。本发明方法可以减弱由于簇内成员节点高速移动带来的路由不稳定问题，同时降低簇头节点网络拥塞的概率，提升路由的鲁棒性，降低端到端时延。

说明书

技术领域

本发明涉及OLSR路由协议技术领域，具体的，涉及一种基于移动预测和时延预测的OLSR路由方法及系统

背景技术

移动Ad-hoc网络是一种无基础设施的无线网络，它因具有分布式的网络结构、动态的网络拓扑、良好的网络扩展性等特点，被广泛应用。近年来，随着物联网技术的兴起，Ad-hoc网络在民用领域展现出了广阔的应用前景。在该网络中，各个节点都能够通过无线介质与其它节点进行通信。但是当网络规模较大时，转发数据包的业务需求就会增多，转发所占用的无线资源也会相应地增多，造成网络拥塞的可能性就会增大，同时为了维护网络，节点发送控制消息的规模也会变大。为了克服这种弊端，分簇Ad-hoc网络应运而生。在分簇Ad-hoc网络中，同一簇内成员之间的通信在簇内即可完成，不同簇成员之间的通信通过簇头完成，从而在保证各簇相对独立的情况下，完成簇间的信息交互，这使得网络管理的难度降低，网络的扩展性也更好。在分簇Ad-hoc网络中，由于簇内各个节点独立运动，网络的拓扑结构始终在动态变化，在这种情况下，节点之间的通信链路不稳定，极易断开，从而造成数据传输的失败。同时由于簇头节点承担着本簇和簇外的通信任务，所以簇头节点的负载较大，当簇头网络为多跳网络时，簇头节点处的瓶颈效应就会对网络通信造成不利影响。所以分簇Ad-hoc网络中的一个重要的挑战就是在网络拓扑频繁变化的场景下实现稳定的簇内通信，同时保证簇头网络的负载均衡，这就对网络采用的路由协议提出了很高的要求。

OLSR是一种先应式路由协议，节点通过周期性地交换拓扑消息来进行路由发现和维护，并保持一张到网络中其它节点的路由表。相比于其它先应式路由协议，由于采用了MPR(多点中继)机制，OLSR协议能够有效减少控制分组的洪泛，降低网络开销。相比于反应式路由协议，由于OLSR始终保持一张到其它节点的路由表，因此在节点发送数据包时不需要发送路由发现信息，只需查表即可，这在一定程度上降低了数据包的端到端时延。但是当OLSR应用于Ad-hoc网络中时，OLSR只是周期性地更新网络拓扑信息，由于网络拓扑的动态性，当网络更新频率慢于网络拓扑变化速率时，就有可能出现因通信链路断开而造成数据包丢失的情况。同时由于Ad-hoc网络应用场景的复杂性，其对OLSR的时延性能也提出了很高的要求。因此，如何在Ad-hoc网络中提升OLSR路由协议的鲁棒性和时延性，并且使其适配于分簇Ad-hoc网络，已经引起了越来越多人的关注和讨论。

经检索文献发现，Stefano Rosati等人在《IEEE Transactionson VehicularTechnology,2016》上发表的“Dynamic Routing for Flying Ad Hoc Networks”文章中提出了一种基于OLSR的改进协议P-OLSR，该协议引入了ETX度量因子，通过综合考虑节点之间的相对速度和节点发送数据包的成功率来选择路由。但是在现实应用中，节点发送数据包的成功率往往很难统计，同时当节点数量较多时，此路由算法的复杂度会大幅度增加。ArnauRovira-Sugranes等人在《IEEE International Conference on Wireless forSpaceand Extreme Environments(WiSEE),2017》上发表的“Predictive Routing forDynamic UAV Networks”文章中在选择中继节点时，考虑了节点所处的位置，并基于Dijkstra最短路径算法建立排队通信系统来优化路由协议，这在一定程度上可以选出一条时延较小的路径。但是该算法仅从时延的角度来优化路由算法，当网络拓扑的动态性较高时，难以发挥其优势。吕娜、张步硕等人申请的专利《一种面向航空集群网络的低时延高可靠路由协议》(申请号：201810228928.8)中，对OLSR的MPR选择机制进行了改进，同时基于虚拟骨干网络设计了链路负载均衡机制，减少了网络中控制分组的洪泛，降低了网络发生拥塞的概率。但是该专利仅考虑了骨干网络的负载情况，没有考虑由于节点高速移动给网络带来不利影响，对于高动态网络的适配性还有待讨论。

发明内容

针对现有技术中的缺陷，本发明的目的是提供一种基于移动预测和时延预测的OLSR路由方法，为了解决OLSR协议应用在高动态的分簇Ad-hoc网络中，由于节点快速移动而产生的路由失败问题和由于簇头节点网络信息拥塞带来的高时延问题，提升簇内网络通信的稳定性，同时实现簇头网络的负载均衡，降低不同簇成员间通信的端到端时延。

本发明提供一种基于移动预测和时延预测的OLSR路由方法，包括簇成员节点路由表计算过程和簇头节点路由表的计算过程，所述簇成员节点路由表计算过程为：采用卡尔曼滤波算法建立移动预测模型，并通过此模型来选择稳定性高的邻节点作为下一跳节点，以此来建立簇内成员节点路由表；所述簇头节点路由表的计算过程为：将数据包在簇头节点MAC层的排队时延作为路由选择的度量因子，通过ARMA算法建立排队时延的预测模型，以此模型来计算簇头节点的路由表。

进一步地，因为原始的OLSR协议中，在计算节点的路由表时仅考虑了到目的节点的跳数，当簇内网络的动态性较高时，一旦所选的下一跳节点出现链路断开的情况，节点发送的数据包将无法通过邻节点转发，从而造成簇内通信时数据包丢失的情况。为了解决这一问题，本发明所述簇成员节点路由表计算过程包括如下步骤：

S10.对簇成员节点的Hello消息帧格式进行修改，修改方式为，在Hello信息域中插入节点的位置信息和速度信息，用(pos_x_now，pos_y_now，pos_z_now)和(vel_x，vel_y，vel_z)分别表示节点当前的位置坐标和速度矢量，(pos_x_pre，pos_y_pre，pos_z_pre)为预测得到的2秒后的节点位置坐标；

S11.对簇内成员节点当前时刻的位置信息和速度信息进行采集，并将得到的位置信息记录在Hello消息帧格式对应的(pos_x_now，pos_y_now，pos_z_now)信息域中，利用卡尔曼滤波算法预测2秒之后节点的运动位置；

S12.将得到的簇成员节点位置预测信息封装在Hello消息对应的信息域中，并通过Hello消息的周期性广播将节点自身的运动状态告知其同簇内的邻节点；

S13.当簇成员节点收到来自同簇邻节点的Hello消息后，对其进行信息提取，在完成邻节点发现和链路检测功能之后，根据收到的邻节点的位置和速度信息来计算链路的连接时间，将链路连接时间作为计算下一跳节点的一个度量因子；

S14.在计算簇成员节点的路由表时，综合考虑和邻居链路的连接时间、邻居节点的连接度以及邻居节点到目的节点的跳数，通过设置Ns值来综合反映这三方面的要素，并把预测得到的节点位置信息作为一个判决门限，若预测2秒(Hello消息的发送周期)之后邻节点会移动出本节点的通信范围，则将邻节点的Ns值置为零，即此邻节点被选为下一跳节点的概率最低；

节点选择Ns值最大的邻节点作为下一跳节点存于路由表中，当簇内所有的成员节点的路由表建立后，进行簇内通信时，数据包将会沿着稳定性较高的通信路径进行传输。

进一步地，所述步骤S11中，结合匀加速直线运动的定理，节点运动轨迹以如下所示的卡尔曼滤波方程表示：

其中：

表示节点当前的移动状态矢量，为输出矢量，表示下一个时刻节点的移动状态矢量，Φ为状态传输矩阵，B表示加速度矩阵，为加速度矢量，服从均值为零且方差为的正态分布，为观测矢量，即由观测设备得到的节点运动状态矢量，H为观测矩阵，表示观测噪声，服从均值为零且方差为的正态分布，k表示节点发送Hello消息的时刻。

进一步地，所述步骤S11中，利用卡尔曼滤波算法的预测过程如下：

(1)初始化状态传输矩阵Φ和观测矩阵H，后验初始状态

(2)预测阶段：依公式预测得到下一个Hello消息发送时刻的运动状态矢量并将预测得到的位置信息写入Hello消息对应的信息域中，其中，“+”表示后验状态，“-”表示先验状态；

(3)测量阶段：利用节点装备的定位设备，测量节点的运动状态信息，计算卡尔曼增益，通过得到的卡尔曼增益，估算后验的运动状态矢量

(4)自适应地调整节点加速度的方差，增加k，返回阶段(2)执行下一时刻运动状态的预测。

进一步地，所述步骤S13中，将同簇成员节点之间的相对运动映射到二维平面，当节点i收到来自节点j的Hello消息之后，提取有效信息，在完成链路检测和邻居发现功能之后，计算2秒之后两节点之间的距离：

在完成上述计算的基础上，利用如下公式估算节点j链路连接时间：

其中，表示由节点i指向节点j的距离矢量，R为节点的通信半径，为节点j和节点i之间的相对速度矢量，α为矢量和矢量之间的夹角。

进一步地，所述步骤S14中，节点i在计算下一跳节点时，首先计算邻节点j的稳定程度Ns，将Ns作为选择下一跳节点的度量因子，

ΔT_ij为邻节点的链路连接时间、Rb_j为邻节点连接度，即邻节点连接的两跳邻节点数目，α和β为权重参数，分别用来调整邻节点链路连接时间和邻节点连接度的权重，N_hop为邻节点到目的节点的跳数，当邻节点到目的节点不可达时，N_hop值置为无穷大，为步骤S13中预测得到的2秒之后两节点之间的距离，R为通信半径，节点i选择Ns值最大的邻节点作为下一跳节点加入到路由表中，直至簇内所有的节点被覆盖，簇成员节点的路由表计算过程结束。

进一步地，在原始的OLSR协议中，路由表的计算采用Dijkstra算法，这是一种最短路径算法，其计算得到的路径具有最小的跳数，然而，在分簇Ad-hoc网络中，簇头节点网络的负载往往较大，数据包在簇头网络中传输时，在中继簇头节点MAC层的排队时延是端到端时延的重要组成部分，所以原始的OLSR协议中选出的最小跳数路径不一定是时延最小的路径。为了实现簇头网络的负载均衡，选出时延最小的路径，并将其存于簇头节点的路由表之中，本发明所述簇头节点路由表的计算过程包括如下步骤：

S21.通过时间戳管理的方式记录数据包在簇头节点MAC层插入队列和离开队列的时刻，并以此来计算数据包在簇头节点MAC层的平均排队时延Q_T，然后对收集得到的历史周期内平均排队时延进行去均值化处理；

S22.采用ARMA算法来预测此簇头节点在下一个TC消息周期中MAC层数据包的平均排队时延；

S23.将预测得到的簇头节点MAC层的平均排队时延Q_T插入到其TC消息域中的Reversed字段处，并插入表示消息的有效期字段T_e，通过TC消息的周期性广播将簇头节点自身MAC层排队时延信息告知其它簇头；

S24.当簇头节点收到来自其它簇头节点的TC消息后，对其进行信息提取，在完成网络拓扑的更新之后，将收到的其它簇头节点处的排队时延的预测信息作为TC消息源节点业务拥塞程度的一个度量，并在计算路由表时引入该度量因子；

S25.簇头节点在计算路由表时，综合考虑中继簇头节点处的排队时延和到目的节点的跳数，在具有最小跳数的路径之中，选出一条排队时延最小的路径存于路由表中，以此来实现簇头网络通信的负载均衡，从而降低数据包的端到端时延。

进一步地，所述步骤S22中，采用ARMA算法的预测过程如下：

(1)利用AIC准则识别模型阶数p和q；

(2)利用最小二乘法计算回归系数和滑动平均系数θ；

(3)依据得到的参数建立预测平均排队时延的ARMA模型，得到下一个TC周期内此节点MAC层处的排队时延。

进一步地，所述步骤S22中，建立如下所示的ARMA模型对下一个周期内的平均排队时延进行预测：

其中，Q_t表示去均值化后的Q_T，表示回归系数，θ表示滑动平均系数，e_t表示高斯白噪声，p和q为模型阶数，i和j表示整数。

与现有技术相比，本发明具有如下的有益效果：

1、本发明的基于移动预测和时延预测的OLSR路由方法，首先考虑了由于簇内成员节点高速移动而给路由带来的不利影响，利用采集到的节点历史位置信息和速度信息，采用卡尔曼滤波算法来预测簇成员节点的运动状态，并将预测得到的运动状态信息作为建立簇内路由表的一个度量因子，以此来提升路由的稳定性。

2、本发明的基于移动预测和时延预测的OLSR路由方法，考虑了簇头网络中的中继簇头节点MAC层的排队时延对端到端时延的影响，利用时间戳管理方式采集得到历史周期内的平均排队时延，利用ARMA模型来预测下一个周期内簇头节点处的平均排队时延，将此预测得到的时延作为簇头网络路由表计算的一个度量因子，从而实现簇头网络的负载均衡，进而降低数据包传输的端到端时延。

3、本发明的基于移动预测和时延预测的OLSR路由方法，虑了簇成员节点的移动状态和簇头节点MAC层的排队时延信息，针对簇头节点和簇成员节点，在路由协议中引入不同的预测机制，依据不同的预测方式分别建立簇头网络路由表和簇成员网络路由表，减弱由于簇内成员节点高速移动带来的路由不稳定问题，同时降低簇头节点网络拥塞的概率，提升路由的鲁棒性，提升簇内网络通信的稳定性，提升其在高动态分簇Ad-hoc网络中的适用性，有效减少数据包的丢失率，降低数据包传输的端到端时延。

附图说明

通过阅读参照以下附图对非限制性实施例所作的详细描述，本发明的其它特征、目的和优点将会变得更明显：

图1是本发明分簇网络架构示意图；

图2是本发明改进后的簇成员节点的Hello消息帧格式；

图3是本发明簇成员节点相对位移图；

图4是本发明改进后的簇头节点的TC消息帧格式。

具体实施方式

下面结合具体实施例对本发明进行详细说明。以下实施例将有助于本领域的技术人员进一步理解本发明，但不以任何形式限制本发明。应当指出的是，对本领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干变化和改进。这些都属于本发明的保护范围。

实施例

本实施例中，本发明的基于移动预测和时延预测的OLSR路由方法，介绍如下：包括簇成员节点路由表计算过程和簇头节点路由表的计算过程，所述簇成员节点路由表计算过程为：采用卡尔曼滤波算法建立移动预测模型，并通过此模型来选择稳定性高的邻节点作为下一跳节点，以此来建立簇内成员节点路由表；所述簇头节点路由表的计算过程为：将数据包在簇头节点MAC层的排队时延作为路由选择的度量因子，通过ARMA算法建立排队时延的预测模型，以此模型来计算簇头节点的路由表。

接下来对本发明进行详细的描述。

本发明的目的是提供一种基于移动预测和时延预测的OLSR路由方法，为了解决OLSR协议应用在高动态的分簇Ad-hoc网络中遇到的问题，提升簇内网络通信的稳定性，同时实现簇头网络的负载均衡，降低不同簇成员间通信的端到端时延。

本发明适用的高动态分簇Ad-hoc网络架构图如图1所示。发明方法中主要包括簇成员节点路由表的计算和簇头节点路由表计算两大部分。

其中簇成员节点路由表计算过程主要包括以下步骤：

步骤1：对簇成员节点的Hello消息帧格式做如图2所示的修改，灰色信息域为增加部分，其中(pos_x_now，pos_y_now，pos_z_now)和(vel_x，vel_y，vel_z)分别表示节点当前的位置坐标和速度矢量，(pos_x_pre，pos_y_pre，pos_z_pre)为预测得到的2秒后的节点位置坐标；

步骤2：簇内网络中的每个节点通过装备GPS等设备，来获得本节点当前时刻的位置信息和矢量速度信息，并将得到的位置信息记录在如图2所示的Hello消息帧格式对应的(pos_x_now，pos_y_now，pos_z_now)信息域中；图2中，灰色部分为新增的部分。(pos_x_now，pos_y_now，pos-z_now)和(vel_x，vel_y，vel_z)分别表示节点当前的位置坐标和速度矢量坐标，(pos_x_pre，pos_y_pre，pos_z_pre)为预测得到的2秒后的节点位置坐标，其余部分为0LSR协议的规范字段，

步骤3：基于当前时刻的位置和速度信息，采用卡尔曼滤波算法来预测2秒(Hello消息的发送周期)之后的节点位置信息。结合匀加速直线运动的定理，节点运动轨迹以

如下所示的卡尔曼滤波方程表示：

其中：

表示节点当前的移动状态矢量，为输出矢量，表示下一个时刻节点的移动状态矢量，Φ为状态传输矩阵，B表示加速度矩阵为加速度矢量，服从均值为零且方差为的正态分布。为观测矢量，即由观测设备得到的节点运动状态矢量，H为观测矩阵。表示观测噪声，服从均值为零且方差为的正态分布。k表示节点发送Hello消息的时刻。具体预测过程为：

(1)初始化阶段：初始化状态传输矩阵Φ和观测矩阵H，后验状态

(2)预测阶段：依公式预测得到下一个Hello消息发送时刻的运动状态矢量并预测得到的位置信息写入Hello消息对应的信息域中；

(3)测量阶段：利用节点装备的定位设备，测量节点的运动状态信息，计算卡尔曼增益，通过得到的卡尔曼增益，估算后验的运动状态矢量

(4)增加k，返回阶段(2)执行下一时刻运动状态的预测。

步骤4：如图3所示，将同簇成员节点之间的相对运动映射到二维平面，当节点i收到来自节点j的Hello消息之后，提取有效信息，在完成链路检测和邻居发现功能之后，计算2秒之后两节点之间的距离：

步骤5：如图3所示，节点i在收到来自节点j的Hello消息之后，在完成上述计算的基础上，利用如下公式估算节点j链路连接时间：

其中，表示由节点i指向节点j的距离矢量，R为节点的通信半径，为节点j和节点i之间的相对速度矢量，α为矢量和矢量之间的夹角。图3可以看作节点i固定于点A处，节点j位于点B处，且以相对速度沿着方向运动，R为节点A的通信半径，α为矢量(此处)和矢量之间的夹角，L表示节点j可以在节点i的通信半径中运动的距离。

步骤6：节点i在计算下一跳节点时，首先计算邻节点j的稳定程度(Ns)，将Ns作为选择下一跳节点的度量因子，其主要由邻节点的链路连接时间ΔT_ij、邻节点连接度Rb_j(邻节点连接的两跳邻节点数目)和邻节点到目的节点的跳数N_hop(当邻节点到目的节点不可达时，N_hop值置为无穷大)组成，定义为：

其中α和β为权重参数，分别用来调整邻节点链路连接时间和邻节点连接度的权重，为步骤4中预测得到的2秒之后两节点之间的距离，R为通信半径。

节点i选择Ns值最大的邻节点作为下一跳节点加入到路由表中，直至簇内所有的节点被覆盖，簇成员节点的路由表计算过程结束，这样在进行簇内通信时，数据包将会沿着稳定性较高的路径进行传输。

簇头节点路由表的计算主要包括以下步骤：

步骤1：如图1所示，簇头节点10通过时间戳管理的方式来记录数据包在其MAC层插入队列和离开队列的时刻，并以此来计算数据包在此节点MAC层的平均排队时延Q_T，对收集得到的历史周期中的平均排队时延进行去均值化处理。

步骤2：建立如下所示的ARMA模型对下一个周期内的平均排队时延进行预测：

其中，Q_t表示去均值化后的Q_T，表示回归系数，θ表示滑动平均系数，e_t表示高斯白噪声，此处i和j表示整数。

具体预测过程为：

(1)利用AIC准则识别模型阶数p和q；

(2)利用最小二乘法计算回归系数和滑动平均系数θ；

(3)依据得到的参数建立预测平均等待时延的ARMA模型，得到下一个TC周期内此节点MAC层处的排队时延。

步骤3：如图4所示，将预测得到的平均排队时延Q_T写入TC消息域中的Reversed字段处，并插入表示消息的有效期字段T_e，节点10向其它簇头节点广播此TC消息。图4中，删掉了TC消息域中的Reversed字段，灰色部分为新增字段，Q_T表示平均排队时延，T_e表示该TC消息的有效期，其余部分为OLSR协议的规范字段。

步骤4：簇头节点20收到簇头节点10发送的TC消息后，对其进行信息提取，在完成网络拓扑更新之后，将收到的节点10处的排队时延作为该节点业务拥塞程度的一个度量。

步骤5：簇头节点20在计算路由表时综合考虑到目的节点的跳数和在中继簇头节点处的排队时延，在具有最小跳数的路径之中选出一条排队时延最小的路径存于路由表中，以此来实现簇头网络通信的负载均衡，从而降低数据包的端到端时延。

图1为分簇网络结构图，其中虚线表示节点之间的通信链路，长方形图标表示簇头，椭圆图标表示簇成员节点，簇内通信存在多跳的情况，簇头间通信同样存在多跳的情况，同时每个簇头也承担着本簇成员节点与簇外成员节点通信的中继任务。

本发明的基于移动预测和时延预测的OLSR路由方法，虑了簇成员节点的移动状态和簇头节点MAC层的排队时延信息，针对簇头节点和簇成员节点，在路由协议中引入不同的预测机制，依据不同的预测方式分别建立簇头网络路由表和簇成员网络路由表，减弱由于簇内成员节点高速移动带来的路由不稳定问题，同时降低簇头节点网络拥塞的概率，提升路由的鲁棒性，提升簇内网络通信的稳定性，提升其在高动态分簇Ad-hoc网络中的适用性，有效减少数据包的丢失率，降低数据包传输的端到端时延。

本领域技术人员知道，除了以纯计算机可读程序代码方式实现本发明提供的系统及其各个装置、模块、单元以外，完全可以通过将方法步骤进行逻辑编程来使得本发明提供的系统及其各个装置、模块、单元以逻辑门、开关、专用集成电路、可编程逻辑控制器以及嵌入式微控制器等的形式来实现相同功能。所以，本发明提供的系统及其各项装置、模块、单元可以被认为是一种硬件部件，而对其内包括的用于实现各种功能的装置、模块、单元也可以视为硬件部件内的结构；也可以将用于实现各种功能的装置、模块、单元视为既可以是实现方法的软件模块又可以是硬件部件内的结构。

以上对本发明的具体实施例进行了描述。需要理解的是，本发明并不局限于上述特定实施方式，本领域技术人员可以在权利要求的范围内做出各种变化或修改，这并不影响本发明的实质内容。在不冲突的情况下，本申请的实施例和实施例中的特征可以任意相互组合。