一种基于链路稳定性的最小MPR选择算法

吴佳琪，任 智，王 磊，赵子军

(重庆邮电大学 通信与信息工程学院，重庆 400065)

1 引 言

移动自组织网络[1]领域的快速发展使移动节点可以形成一个自我创建，自我组织和自我管理的无线网络.它的动态配置，灵活性，低成本以及各种吸引人的功能使其成为未来趋势环境的重要组成部分[2].由于其缺少任何预先存在的基础架构，节点可以自由移动到任何方向，可以与任何设备随时通信，不受任何控制的独立性以及其它特征是其获得广泛关注的关键[3].虽然近些年来在Ad-hoc[4,5]研究上取得一些的成果，但是MANET网络仍然存在动态拓扑变化、链路带宽资源有限、能量持续消耗、网络不安全等一系列问题[6].

OLSR(Optimized Link State Routing)专门为自组织网络设计，是一种主动的链路状态路由协议，其体现在需要传输数据分组时能快速提供路由.通过要求较少的节点转发信息来减少泛洪链路状态信息的开销，使用HELLO和TC消息来发现，然后在整个移动自组织网络中分发链路状态信息，各个节点使用此拓扑信息用最短的跳数转发路径为网络中的所有节点计算下一跳[7].

为了克服由于节点快速移动引起整个网络链路不稳定的问题，首先要解决的是去量化移动性，然后将其集成到路由过程中.许多研究者已经对此主题进行了研究，Loutfi A等人提出了一种与节点通信范围附近的链路状态变化有关的量化节点密度方法去选择MPR(multipoint relays)集，不是以优先节点的覆盖度大的节点作为MPR节点，而是选择具有高密度邻居的节点作为MPR节点，虽然两者含义相差不大，但是需要去统计计算一段时间内节点局部邻居变化情况，并没有节点的当前覆盖度更直观的反响当前邻居链路的连接情况，也不能保证MPR集最小[8].文献[9]提出EMP-OLSR协议它通过记录收到HELLO消息时的信号能量和持续时间，然后根据两射线地面模型中的信号能量损失公式，计算出节点之间的相对距离之后，当节点发送下一个HELLO消息时，将估计该节点的位置.然后根据估计的结果，节点计算出的路由选择更稳定可靠的转发下一跳.文献[10]提出了一种用于UAV Ad-hoc网络的移动性和负载感知OLSR(MLOLSR)协议引入了移动感知算法和负载感知算法，在选择MPR中避免选择高速节点作为MPR，并且避免通过高速和拥塞的节点进行路由以发现更稳定的路由.Moussaoui A等人提出了一种ST_OLSR[11]协议，计算了节点相对于其邻居的移动程度，将稳定性函数用作主要路径选择标准，同时在选取MPR的过程中首先选取保真度FND值最大作为MPR，在几个节点的FND值相等的情况下，具有最大可达性的节点选为MPR.从而使MPR节点和拓扑结构更稳定，极大地减少了MPR的重新计算和路由表的重新计算过程.

文献[12]提出了一种ADLB-OLSR协议，引入了吸收度机制和负载均衡机制去减少网络中TC分组的数目和平衡网络拥塞，吸收度机制中选取吸收度更高的节点作为MPR节点，但是吸收度低的节点更容易被其它节点选为MPR节点，所以并不会减少整个网络MPR集的数量.

针对无人机的移动性带来链路不稳定的问题，李灿提出了一种基于位置感知和邻居感知的OLSR路由协议[13].该协议将节点的位置信息添加到HELLO数据包中在计算MPR集的时候通过节点的位置和邻居改变率(NCR)的组合设置意愿值，去提高MPR节点选取的稳定性.但会增加网络中的MPR数量，从而增大了整个网络的控制开销.

因此本文提出了一种链路稳定性考虑的最小MPR选择算法(A Link-Stability-Based Minimum MPR Selection Algorithm，LSB-MPR)，在保证不增大网络中MPR数量的前提条件下，通过延长了MPR节点集的有效时间，提升整个OLSR协议中节点通信的稳定性.

2 MPR选择算法介绍与问题描述

优化链路状态路由协议中MPR算法主要目的是减少TC消息洪泛开销，其中TC消息只会在MPR节点间进行转发，网络中的MPR集越小，整体TC消息洪泛到全网被转发的次数就越少.另外网络中节点两跳以上路由路径计算也是通过与已有路径相连且被选为MPR集的节点进行构建，所以MPR集稳定性也间接关系到数据分组传递稳定性.

2.1 MPR算法介绍

设节点N的一跳邻居集合为M1(i)，节点的两跳邻居集为M2(i).MPR算法的宗旨是选取最小一跳对称邻居集合S中继所有的两跳对称邻居.RFC3626[7]中MPR算法的流程如下：

连接度D(y):初始一跳对称节点覆盖的两跳对称节点的数量；

步骤 1.初始化集合S为空集；

步骤 2.将N中所有意愿值为WILL_ALWAYS的节点加入到S中；

步骤 3.计算 N中所有节点的连接度D(y)；

步骤 4.将M1(i)中的节点添加到S中其中，只有通过该节点才能中继到M2(i)的节点；从M2(i)中删除由S中节点所覆盖的节点.

步骤 5.若M2(i)为空，执行步骤6；否则计算M1(i)中还没有加入到S中所有节点的覆盖度；在覆盖度为非0的节点中选择N_willingness最高的节点加入到MPR集中；若意愿值相同的情况下选择覆盖度大的节点加入到S中；若意愿值和覆盖度都相同的情况下，选择D(y)更大的节点加入到MPR集中，从M2(i)中删除由选定节点所覆盖的节点，跳转到步骤4.

步骤 6.若初始的两跳邻居中的所有节点仍由S中的至少一个节点覆盖(不包括节点y)，并且节点y的N_Willing小于will_always则可以从S中删除节点y.

2.2 问题描述

上述MPR选择算法的前5步在选取最小MPR集是一个NP完全问题[14]，如果不执行第6步的优化，那么可能存在MPR节点冗余问题.针对MPR节点可能存在冗余的问题文献[15]提出了一种基于OLSR协议的最小MPR选择算法，该算法在每次选择MPR节点的时候依次检测剔除覆盖度最低的节点看是否存在孤立的两跳节点，若存在就说明该节点不能被剔除就将其加入到MPR集中.其实质上是将原始算法的第6步的优化工作融入到了MPR选择之中，在理想情况下与原始算法前5步时间复杂度相同都为O(nlg(n))[16].另外，这两种算法在选取MPR节点的过程中都会存在初始覆盖度和当前覆盖度都相同的节点，此时就会随机选择一个节点作为MPR节点，如图1所示.

图1 节点0选择MPR集Fig.1 Node 0 selects the MPR set

如节点0在执行上述MPR算法选取MPR节点有两种情况分别为：{1,2,4}、{1,3,4}.这样就会随机选择一种情况，并没有考虑节点2，3的稳定性，若节点3在链路的有效保持时间的下一个时刻脱离节点0，而节点0需要在节点3链路保持时间结束的前一个时刻计算MPR集，所以节点0在计算MPR的时候还是认为节点3没有脱网还是双向链路，若节点0选取节点3作为MPR节点，就会带来链路的不稳定性.

3 LSB-MPR选择算法

为解决上述问题，提出一种基于节点稳定性优化的最小MPR选择算法—LSB-MPR，选择具有更稳定链路的节点作为MPR.

链路保持时间问题在RFC3626[7]中建议了每个节点邻居链路(包括一跳邻居和两跳邻居)保持时间是3个HELLO消息间隔：

HEIGHB_HOLD_TIME=3×HELLO_INTEVAL=6s

(1)

刷新检查时间为：

REFRESH_INTEVAL=HELLO_INTEVAL=2s

(2)

虽然网络中的每个节点可以根据自己运动状态改变HELLO消息的发射速率(链路的有效保持时间validity time也随之改变)，但增大该速率会增大网络的控制开销，而减小该速率会造成链路感知迟钝，所以选取建议的固定统一HELLO发射周期进行分析.

针对图1中节点0在选取2、3节点作为MPR过程中的相应链路保持时间进行分析.

图2为节点0针对接收到节点2和节点3的HELLO消息后保存时间的一个过程.假设在t0时刻节点收到了节点3的 HELLO消息，在t2时刻收到节点2的HELLO消息，若在t1时刻还没有收到节点3的HELLO消息，那么已经有两个周期还没有收到该节点的HELLO消息了.在t2时刻，节点2的邻居保持时间2_hold_time′=3T，节点3的邻居保持时间3_hold_time′2T.当在时间段(t2，t4)之间任意一个时刻t3计算节点的MPR集时，两节点当前链路保持时间差为：

2_hold_time-3-hold_time=
2_hold_time′-3_hold_time′>2T

图2 节点0的时间轴Fig.2 Timeline of node 0

针对上述分析，节点0是能够计算当前周围一跳邻居链路剩余保持时间，根据此依据定义当前链路稳定性评判标准为LSij(Link-Stability)表示节点i检测与节点j的链路稳定性级别，分3个等级：

(3)

等级α:节点i检测到与节点j链路在目前来说是危险链路，已经有两个HELLO消息间隔内节点i没有收到节点j发送过来的HELLO消息；

等级β:节点i检测到与节点j链路在目前来说是潜伏链路，已经有一个HELLO消息间隔内节点i没有收到节点j发送的HELLO消息；

等级γ:节点i检测到与节点j链路目前来说是相对稳定链路，在节点j的HELLO消息间隔内已经检查到了节点i收到节点j的HELLO消息.

定义：

γ-β=β-α=1

(4)

节点0在2、3节点之一选择一个作为MPR节点的时候，需要计算两条链路稳定性差值ΔLS(ΔLS=LS02-LS03),如表1所示.

对ΔLS≥0的情况进行讨论：

I)若ΔLS=2，此时LS02=γ，LS03=α.可以推知2_hold_time-3_hold_time>2*HELLO_INTEVAL节点0收到节点2最新的HELLO消息包时间比节点3早2个周期，也就是说节点0有2个周期没有收到节点3的HELLO消息包，如果节点0在下一个少于一个周期时间内还是没有收到节点3的HELLO消息包后，就将该链路删除.若此前节点0选择节点3而不是节点2作为MPR节点，那么节点3就会被删除，重新计算MPR集，此时选择的MPR集为{1、2、4}.这一更换MPR节点的过程会使先前节点3产生包含节点0地址信息部分的TC消息失效了，而节点2的TC消息却要添加节点0地址信息，这种改变需要重新广播TC消息转发到整个网络中，从而造成网络不稳定.如果选择节点2作为MPR节点，那么节点0至少要等两个以上的HELLO消息间隔没收到才会将节点链路删除，所以为了维持网络中的MPR集稳定可以优先选择2号节点作为MPR节点，给了整个网络更多缓冲等待时间去判断链路通断.

表1 链路稳定性级别差值ΔLSTable 1 Link stability level difference ΔLS

II)若ΔLS=1，此时LS02=β，LS03=α或者LS03=β，LS02=α.可以推知2*HELLO_INTEVAL>2_hold_time-3_hold_time>HELLO_INTEVAL节点0收到节点2最新的HELLO消息包时间比节点3早一个周期，也就是说，相对于节点2来说节点0有一个周期没有收到节点3的HELLO消息包，如果节点0在下两个周期内还是没有收到节点3的HELLO消息包后，就将该链路删除，不参与MPR节点集的计算.这样节点3参与MPR计算的稳定性相对于节点2来说更不稳定.

III)若ΔLS=0，此时LS03=LS02=α或者LS03=LS02=β或者LS03=LS02=γ.LS03和LS02链路稳定性评判等级相同，可以推知|2_hold_time-3_hold_time|

(5)

其中j为节点一跳对称邻居的数目，i_hold_time为与节点i的当前链路保持时间，NRR ∈(0,1).此时对计算MPR的节点来说，需要比较的两个备选MPR节点初始覆盖度和当前覆盖度是相同的，可以推知这两个备选节点的一跳对称邻居数目也肯定是相等(j值相等)，j值越大NRR值越小.

节点间通过HELLO消息的交互获知周围节点的邻居保持率，同时，将HELLO数据包中Resserve保留字段更为NRR如图3.

图3 改进的HELLO消息格式Fig.3 Improved HELLO message format

整个LSB-MPR算法优化部分是步骤5将链路的保持时间影响链路稳定性的因素结合到算法中去，同时优化步骤6的具体实施过程，让算法执行第优化速度更快，具体过程为：

步骤 1.初始化集合S为空集；

步骤 2.将N中所有意愿值为WILL_ALWAYS的节点加入到S中；

步骤 3.计算 N中所有节点的初始覆盖度D(y)；

步骤 4.将M1(i)中的节点添加到S中其中，只有通过该节点才能中继到M2(i)的节点；从M2(i)中删除由S中节点所覆盖的节点.

步骤 5.若M2(i)为空，执行步骤6；否则计算M1(i)中还没有加入到S中所有节点的覆盖度，在覆盖度为非0的节点中选择N_willingness最高的节点加入到MPR集中；若意愿值相同的情况下选择覆盖度大的节点加入到S中；若意愿值和覆盖度都相同的情况下，选择D(y)更大的节点加入到MPR集中，若出现了覆盖度与初始覆盖度D(y)相同两个节点a,b时，执行如下操作：

计算节点i 的LSia、LSib、ΔLS=LSia-LSib；

If ΔLS==0

选NRR更大的节点；

else if

ΔLS≥1

选a节点作为MPR节点；

else

选b节点作为MPR节点；

从M2(i)中删除由选定节点所覆盖的节点，跳转到步骤4.

步骤 6.依次检测退出S中意愿值N_Willing小于will_always且D(y)最大的节点，若该节点覆盖的两跳邻居能被S中的其它节点完全覆盖，则将该节点从S中剔除.

算法步骤5的执行并没有增大整个网络的控制开销，同时利用图4对算法的步骤6优化进行说明.

节点0执行MPR算法的前5步选取的MPR节点为{d,a,b,f}，再执行第6步的时候要优化冗余节点，此时是随机的依次检测每个节点剔除的可能性，虽然最后都能得到最优的MPR集为{d,b,f}，但是优化的速度并不快.考虑到MPR算法在选取时候是优先选取覆盖度高的节点作为MPR节点而没有考虑其覆盖的邻居是否能完全被其它节点所覆盖，再剔除已经覆盖的两条邻居，那么接下来选择的覆盖度次之节点所覆盖的两跳邻居中一定存在上一个覆盖度高的节点所不能覆盖的邻居节点，其原因是先加入MPR集中的节点是按照覆盖度更高，后面加入MPR集中的节点约束条件更多，其被剔除的级别相对于上一个覆盖度高的节点来说更低，所以选取的集合S中覆盖度更高的节点是冗余节点的概率更高，应该优先被排查，这样可以加快MPR算法的计算时间，使其效率更高.

图4 节点0选取MPR节点Fig.4 Node 0 selects the MPR node

4 仿真分析

选取标准OLSR路由协议中MPR选择算法，LSB-MPR选择算法，以及文献[15]中OP-MPR选择算法作为分析比较对象，通过仿真实验分析它们之间的控制开销、端到端时延、吞吐量、丢包率这些性能指标.

4.1 仿真参数设置

本文使用Windows XP平台上OPENT Modeler 14.5 仿真软件，设置了4个仿真场景.假设每个节点的发射、接收功率以及通信范围均相同；所有节点HELLO消息和TC消息的发射周期都为固定值分别为2s和5s，N_willingness值设置为默认值3.主要考察节点不同移动速度对各性能指标的影响，其具体数值如表2所示.

表2 仿真参数设置Table 2 Simulation parameter settings

4.2 仿真结果分析

4.2.1 控制开销

图5表明：LSB-MPR选择算法与另外两种MPR算法在控制开销上基本是相同的，原因是OP-MPR选择算法是对标准MPR算法执行过程的改进，LSB-MPR选择算法是对标准MPR算法的稳定性进行丰富，两者并没有引入新的消息类型或者控制字段，LSB-MPR选择算法虽然修改了MPR集的选择减少了不稳定链路的节点成为MPR机率，但是步骤5的执行并不会减少MPR集，而控制消息都是周期性发送，其大小并不会改变.

图5 控制开销对比Fig.5 Control overhead comparison

4.2.2 吞吐量

图6表明：LSB-MPR选择算法的吞吐量平均高出另外两种算法0.08Mbps，虽然其并没有减少网络控制开销，但是使网络中的MPR节点链路更稳定，数据分组在传送时会在整个网络的MPR节点间转发到达目的节点，从而间接的优化了路由的稳定性，而节点移动速度越快，整个网络链路越不稳定，数据分组传送时丢失机率更大，接收端成功接收数据更小，吞吐量下降越明显.

图6 吞吐量对比Fig.6 Throughput comparison

4.2.3 端到端平均时延

图7表明：在OLSR协议中运行LSB-MPR选择算法比运行标准MPR选择算法、OP-MPR选择算法的平均端到端时延低，原因是LSB-MPR选择算法考虑了存在备选MPR节点链路的稳定性，选取了链路更稳定的节点作为MPR节点，减少了选择不稳定MPR节点切换为稳定MPR节点的频次，提升了链路局部的MPR节点稳定性.而当节点移动速度为40m/s时，系统开始出现运行不稳定了，此时运行LSB-MPR选择算法协议的端到端时延相较来说波动较小，说明其在节点移动速度较大时效果较明显.

图7 端到端平均时延对比Fig.7 End-to-end average delay comparison

4.2.4 丢包率

图8表明：LSB-MPR选择算法丢包率较低的原因是MPR节点链路更稳定，数据分组传送时丢失的概率更低，而标准MPR算法和OP-MPR算法两者丢包率接近，OP-MPR算法是最小MPR集计算的另一种方式，与标准MPR算法的步骤6优化效果是一样的，所以两者丢包率接近.

图8 丢包率对比Fig.8 Comparison of packet loss rates

5 结束语

本文针对现有OLSR路由协议中MPR算法在选取MPR节点时，对中继节点周围链路的稳定性进行了考虑，在保证不增大网络MPR节点数量的前提下，选取网络中更稳定的MPR节点，避免了部分不稳定MPR节点频繁切换引起网络路由震荡.提出了一种基于链路稳定性优化的最小MPR选择算法，通过计算链路稳定级别LSij根据级别差值ΔLS选取更稳定的节点加入MPR集，若稳定性级别相同则根据邻居保持率去选择更稳定的MPR节点，同时在原始算法上加快了剔除MPR集中冗余节点的执行过程.仿真结果表明，本文提出的算法在节点不同移动速度上使端到端时延、吞吐量、丢包率这些性能指标得到改善，提升了整个网络的稳定性.下一步考虑不将标准MPR算法中节点当前覆盖度作为选取MPR节点的首要依据，将节点链路稳定性和当前覆盖度相结合一起作为首选依据，去在延长整个MPR集保持时间同时尽量优化该过程中照成MPR集增大的问题.