基于链路稳定性估计的HELLO报文自适应发送算法

王玥琪，张唯炯，郭世杰

(上海航天技术研究院，上海 201109)

0 引言

与传统蜂窝网络相比，Ad Hoc网络中所有节点地位平等，兼具移动终端和无线路由器的功能，并具有自组织、多点中继及支持动态拓扑等优点[1]，因此在军用和民用领域都有较高的应用前景[2]。根据路由检测方法的差异[3-4]，Ad Hoc路由协议通常分为表驱动路由协议、按需路由协议以及混合路由协议。表驱动路由协议的路由发现是节点通过周期性广播交换路由信息，每个节点维护一张或多张包含到达网络中所有节点路由信息的路由表[5]。优点在于,当节点需要发送数据分组时，只要路由表中存在去往目的节点的路由，所需的延时就很小；缺点在于,需要花费较大的开销才能使节点路由表中的路由信息及时与当前网络拓扑结构保持一致[6]。因此，合理降低网络控制报文开销是表驱动路由协议优化的重要方向之一。

标准OLSR路由协议采用HELLO控制分组与TC控制分组进行全网拓扑信息的获取[7]。其中，HELLO控制分组用于对邻居节点的探测，获取本节点的一跳与两跳邻居信息[8]。HELLO分组的发送间隔是固定的，但这样会带来路由信息无法及时更新或网络资源浪费的问题。因此，依据网络拓扑实时状态动态调整HELLO报文发送间隔是十分有必要的，目前已有较多文献对自适应调整HELLO间隔进行了研究。文献[9]提出了一种基于差分进化(Differential Evolution，DE)的自适应调节HELLO报文发送间隔的算法。仿真结果表明,在不影响数据包传输率和平均端到端延迟的情况下，该算法可以有效地改善控制报文流量开销，但由于DE算法需要对相邻节点HELLO报文发送间隔进行长时间观察后才能得到最优解，因此该算法缺乏实时性，无法根据当前网络状况及时更新HELLO发送间隔。文献[10-11]依据节点邻居表的变化情况与链路的状态，计算得到节点移动性得分与链路不稳定度，使HELLO报文发送间隔在一定时间范围内动态变化，但该算法中HELLO报文发送周期浮动范围较小，对网络开销优化效果不明显。文献[12]通过统计网络中所有节点已发送，但还没有得到接收方确认的分组个数，来判断当前网络性能的优劣并进行HELLO报文发送间隔的调节，但该算法要求无线信道必须具有理想的对称性，因此限制了算法的适用范围。

针对以上算法存在的问题，本文提出了一种基于当前链路连接稳定性度量的HELLO报文发送间隔自适应调节算法。该算法通过计算节点与邻居点之间的链路维持概率[13]，判断当前链路的稳定状态，进而实时地对HELLO报文发送间隔实施自适应调节，即链路越稳定，发送间隔越长，反之缩短发送间隔。仿真结果表明，与标准OLSR路由协议及文献[10]所提出的算法相比，该算法扩大了HELLO报文发送间隔的浮动范围，进一步降低了不必要的HELLO报文发送量，节省了网络资源。

1 相邻节点间链路维持概率

相邻节点间链路维持概率的定义是：对于任意一对相邻节点M和N，给定时间t，则节点M和节点N在经过时间t之后仍然保持连接的概率[14]。相邻节点间链路维持概率越大，说明2节点间链路越稳固，反之，相邻节点间链路维持概率越小，说明2节点间链路越不稳定，例如节点可能处于邻节点的通信范围边缘等。

通常，节点的运动遵从一定的运动规律，Ad Hoc无线自组网中有如下常见的实体移动模型：随机行走移动模型、随机方向移动模型、随机路点移动模型(Random Waypoint Model，RWP)与高斯-马尔可夫移动模型[15]。本文选择RWP对节点运动进行近似，这是一种较为实际且应用最广泛的移动模型[16-17]。

因此，当节点m与邻居节点n的当前距离为d，节点的通信半径为Rt，节点相对移动参数为αm,n，相邻节点在时间t内保持连接的概率可以通过判断两点的相对移动向量在时间t内未越过通信范围边界的概率计算[13]。即：

(1)

2 HELLO报文发送间隔自适应调节算法

2.1 算法原理

在OLSR路由协议中，各节点通过HELLO报文实现对邻居节点的探测，并获取本节点的一跳与两跳邻居信息。然而，标准OLSR协议的HELLO报文发送间隔是固定的，因此在网络拓扑相对稳定的情况下，仍然发送大量的HELLO报文会造成网络资源的浪费。反之，在网络拓扑快速变化的情况下，需要缩短HELLO报文发送间隔，及时识别邻居状态变化，及时更新网络拓扑信息。针对上述问题，本文提出一种基于当前链路连接稳定性度量，实时更新HELLO报文发送间隔的自适应算法，通过加大或缩短HELLO报文发送间隔，增强路由协议对节点邻居状态变化的及时识别能力，降低HELLO报文发送量，提高收敛速度，节省网络资源。在该算法中，本文假设所有节点的收发天线均为全向波束，各节点通过广播的方式发送HELLO报文。

本算法的工作主要包括以下3部分：

① 以链路维持概率表征相邻节点间链路稳定程度，通过对节点位置坐标的实时跟踪获取当前链路维持概率值，并结合上一次链路维持概率测量值进行平滑处理；

② 根据平滑处理后的链路维持概率，调整HELLO报文发送间隔；

③ 根据链路维持概率的计算需要，修改OLSR控制报文格式。具体而言，即根据算法需要，在HELLO控制分组中增加节点位置坐标字段。

以节点M为例，本算法的具体步骤如下：

① 节点M以等时间间隔广播发送HELLO报文进行邻居感知与初始化；

② 当节点M与网内一跳范围内部分节点建立邻居关系后，启动HELLO报文发送间隔自适应调节算法；

③ 当节点M在当前HELLO间隔内接收到其他节点发来的嵌有其位置坐标的HELLO报文后，计算当前时刻这些链路的维持概率；

④ 节点M计算连续2次链路维持概率的加权和，即

Pm,i=α*pn(m,i)+β*pn-1(m,i) (α+β=1,α>β)，

(2)

式中，pn(m,i)为当前所得的链路维持概率；pn-1(m,i)为上一次报文所得的链路维持概率;

⑤ 根据标准OLSR路由协议[18]以及文献[10-11]对HELLO报文发送间隔的设置方法，将HELLO报文发送间隔设置为如下形式：

(3)

式中，Pmin为在当前HELLO报文发送间隔内，节点已知的所有链路维持概率的最小值，即：

Pmin=min{Pm,1,Pm,2,Pm,3,…,Pm,i,…,Pm,n};

(4)

⑥ 节点M按调整后的发送间隔向所有邻居节点发送HELLO报文。

2.2 HELLO报文修改方法

假定节点均配有GPS或北斗等导航系统，因此,节点可以实时获取自身所处位置的横纵坐标，同时假定所有节点最大通信范围固定且一致。上述节点实时位置信息被封装在HELLO控制分组中以便于邻居节点计算链路维持概率。

为实现本文提出的改进算法，参照RFC3626标准文档[18]中规定的OLSR数据结构，对标准OLSR路由协议的HELLO控制分组进行修改。

具体而言，相比于标准HELLO控制分组，如图1(a)所示，改进的HELLO控制分组中增加了节点的横纵坐标字段，其基本格式如图1(b)所示。

(a)标准HELLO控制分组

(b)改进后的HELLO控制分组

3 算法仿真验证

3.1 仿真环境

通过仿真，对本文改进算法与文献[10]所提出算法以及标准OLSR路由协议在不同仿真时长与节点运动速率下的HELLO报文发送总量以及吞吐量方面进行比较与分析。上述性能指标的定义分别为：

① HELLO报文发送总量(HELLO Traffic Sent)：所有节点发送的HELLO报文量之和，单位为bits/s。

② 吞吐量(Throughput)：所有目的节点在单位时间内接收到的报文量，单位为bits/s。该参数反映了网络对数据业务的承载能力。

本仿真实验采用OPnet14.5作为网络仿真实验平台。仿真场景设置20个节点随机分布在5 km×5 km的矩形区域内，每个节点的无线传输半径为2.5 km。仿真选择随机路点移动模型作为节点的移动模型。单个直线运动的速率服从(0,vmax)(m/s)的均匀分布，其中，vmax分别取5，10，15，20，25，30 m/s；单个直线运动的持续时间服从参数为10 s的指数分布；单个直线运动的方向角服从(0,2π)的均匀分布；仿真时间为500 s；自适应算法中，取α=0.7，β=0.3。具体仿真环境参数如表1所示。

表1 网络仿真参数

参数值仿真平台版本OPnet14.5节点运动模型RWP仿真范围/km25∗ 5最大通信范围/km2.5仿真时间/s500节点停留时间/s0λi(节点运动时间分布)/s10

3.2 仿真结果

采用新的HELLO报文发送机制后，组网通信正常，与文献[10]所提出算法以及标准OLSR路由协议在HELLO报文发送总量与吞吐量方面的仿真比较如图2～图4所示。

(1)不同仿真时长下HELLO报文发送总量分析

图2给出了在节点最大运动速率为10 m/s时，本文改进算法、标准OLSR路由协议以及文献[10]所提出算法的HELLO报文发送总量随仿真时长变化的仿真结果。相比标准OLSR路由协议，本文改进算法在HELLO报文发送总量方面平均下降10.27%；相比文献[10]所提出算法，本文改进算法在HELLO报文发送总量方面平均下降5.39%。

图2 不同仿真时长下HELLO报文发送数量对比

(2)不同运动速率下HELLO报文发送总量分析

图3给出了本文改进算法、标准OLSR路由协议以及文献[10]所提出算法的HELLO报文发送总量随节点不同最大运动速率变化的仿真结果。由图3可以看出，节点最大运动速率的增加会带来网络拓扑的快速变化，因此3种算法均随节点运动速率的提升而呈上升趋势。同时，相比标准OLSR路由协议，本文改进算法在HELLO报文发送总量方面平均下降13.08%；相比文献[10]所提出算法，本文改进算法在HELLO报文发送总量方面平均下降9.96%。

图3 不同最大运动速率下HELLO报文发送数量对比

(3)不同运动速率下吞吐量分析

图4给出了本文改进算法、标准OLSR路由协议以及文献[10]所提出算法的吞吐量随节点不同最大运动速率变化的仿真结果。随着节点最大速率的增加，网络拓扑不稳定度提高，因此3种算法的吞吐量均呈下降趋势。同时，相比标准OLSR路由协议，本文改进算法在吞吐量方面平均提升32.83%；相比文献[10]所提出算法，本文改进算法在吞吐量方面平均提升14.07%。

图4 不同最大运动速率下吞吐量结果对比

4 结束语

本文基于对相邻节点间链路稳定性的估计，提出了一种基于链路维持概率的HELLO报文自适应发送机制。该机制通过HELLO报文探测得知邻居节点的最新位置信息，并计算当前链路维持概率，调整下一次HELLO报文发送间隔。仿真结果表明，相比于标准OLSR路由协议以及其他相关改进算法，本文提出的改进算法一定程度上降低了HELLO报文总发送量，节省了网控报文开销，增大了吞吐量，提升了网络性能。