基于拉格朗日乘子优化传输控制消息间隔的OLSR协议*

黄煜栋， 郝 平

(1.杭州科技职业技术学院 信息工程学院， 浙江 杭州 311402； 2.浙江工业大学 计算机学院， 浙江 杭州 310014)

0 引 言

从节点或链路失效中快速恢复路由(失效恢复)是链路状态路由算法的关键性能[1～4]。一些重要网络常启用冗余机制提升对失效节点的检测速度。然而，对于一些自组织网络，如移动无线Mesh网络，启用冗余机制并不可能。因此，失效恢复仍取决于三层控制消息的交互。

虽然Dijkstra算法能够计算最短路径的权值[5]，但基于Dijkstra协议的收敛性(convergence)仍受到两个因子的制约：1)失效恢复；2)新拓扑信息的传播。在多数链路状态路由中，这两个因子交互都是利用不同的周期信息实现的：HELLO消息(HELLO message,H_M)以及链路状态广播消息(link state advertisement message,LSA_M)。在每个网络接口、每个节点传输H_M，进而发现邻居节点；而每个节点传输LSA_M是为了更新路由。LSA_M在整个网络内传播，允许每个节点建立并维护路由表。一旦节点失效，所有遍历该节点的路由将失效，此外，在信息被正确地传播至整个网络之前，失效节点可能还会导致路由临时性循环[6～8]。

本文对收敛性与网络开销的权衡问题进行了形式化表述，并进行求解。利用节点在网络拓扑中的中心度，计算每个节点的广播H_M和LSA_M的间隔，进而最大化网络性能。此外，为了验证模型的有效性，将该模型应用于最优链路状态路由(optimized link state routing, OLSR)，并分析其路由性能。

1 网络模型及问题描述

1.1 问题描述

考虑如图1所示的网络。假定节点n1利用节点n2作为连接目的节点n4的下一跳节点，n0～n4的最短路径可表述为p0,4={n0,n1,n2,n3,n4}。本文引用pi,j={ni,…,nj}表示从节点ni至节点nj最短路径。

图1 网络模型

节点n3在网络内的位置决定着其失效对整个网络性能的影响：若处于网络关键位置，则该节点一旦失效，将影响大量路由。如图1所示，相比于节点n3，节点n0失效所产生的影响要小得多。

本文针对链路状态路由的节点失效问题，展开分析，先建立优化模型，然后再利用拉格朗日乘子求解，最后将该模型应用于OLSR协议，并分析改进后的路由协议性能。

1.2 网络模型

考虑网络图G(φ,ε), 其中φ为顶点集，而ε为边集，且‖φ‖=N,‖ε‖=E。图G(φ,ε)代表一个多跳网络，每个顶点对应一个节点，每条边对应一条链路。链路对应于IP层的逻辑接口[9]，因此，在无线网络中两条或多条链路可能分享同一个物理资源。

假定节点ni广播H_M和LSA_M的间隔分别表示为tH(i)和tA(i)。通过一跳广播H_M消息发现并维持邻居节点。每条H_M消息包含了一个时效区域。节点通过设置定时器检测链路的时效性。当节点ni的邻居节点nj收到来自ni的H_M消息后，就设置定时器。若在定时器计时完毕后，节点nj没有收到来自ni的新消息，则节点nj认为其与ni的链路{ni,nj}已失效(断裂)。

定时器的定时时间通常为tH(i)的倍数关系。因此，定时时间通常等于VHtH(i),VH为常数。此外，节点ni以周期为tA(i)广播LSA_M消息，通常tH(i)

2 基于拉格朗日乘子优化传输控制消息间隔模型

建立基于拉格朗日乘子优化传输控制消息间隔模型(Lagrange multiplier-based optimal control message timers model,LMM)模型的目的在于优化节点传输H_M和LSA_M消息的间隔[10]，进而在维持一定的网络开销时，保证数据传输的流畅性。整个LMM模型框图如图2所示。

图2 LMM模型框图

2.1 目标函数建立

2.1.1 基于H_M消息的目标函数

以图1为例，若节点n3在时刻T0失效，节点n2和n4在定时时间VHtH(i)结束后，就能发现节点n3的失效。节点n2和n4需重新构建路由。考虑到最糟糕的情况：节点n3一广播H_M消息，就失效,导致节点n2和n4需要经历Td=T0+VHtH(3)才能检测到节点n3失效。

1)给定网络内最短路径pi,j={ni,…,nj}，定义节点nk的最短路径中间性(the shortest path betweenness)bk

(1)

式中bk为通用的基于图论变量[11]，被广泛使用。当图表示一个IP网络，在每一个瞬间，从节点ni至节点nj间只有1条最短路径，即‖{pi,j}‖=1。

2)定义因节点nk失效而引起的路由损失L(k),即因节点失效导致断裂路由数和对数据传输时延的影响，L(k)=VHtH(k)N(N-1)bk。可知，实际上，L(k)是因节点nk失效所导致断裂路径的条数与路径断裂时间的乘积。

可知，重建路由所需的时间与H_M消息间隔呈线性关系。因此，平均损失L也随tH(k)增加。此外，节点中心度越高，其失效所引起的断裂路径条数越多。

为了提高路由的收敛性，应减少tH(k)值。但将因此增加开销。节点ni因H_M消息所产生的开销等于H_M消息条数与H_M消息的尺寸乘积。LMM模型不修改H_M和LSA_M消息尺寸，只是通过控制消息条数实现减少开销目的。

在ni参与的所有链路中，ni均广播H_M消息。因此，每秒所产生的H_M消息数可简化Oi=ci/tH(i),ci为ni的中心度。由文献[12]，ni的中心度定义为

(2)

式中N为网络内总的节点数，λij为节点i与j间相遇率,T为观察时间。可知，节点i的中心度Ci表示在特定时间T内节点i与网络内其他节点相遇的平均概率。

利用L和OH建立目标函数。开销一定情况下，最小化路由损失，分别实现最小化网络损失和约束开销

(3)

2.1.2 基于LSA_M消息的目标函数

类似地，在开销一定情况下，最小化损失

(4)

2.2 基于 拉格朗日乘子优化算法

首先，考虑到H_M消息的定时器，在这种情况下，x=[tH(1),tH(2),…,tH(N)],f(x),g(x)由式(3)计算,有

(5)

3 基于LMM-OLSR路由

OLSR邻居节点感知过程如图3所示。节点n1广播H_M消息，若节点n2接收后，建立邻居表，并将节点n1地址加入其H_M消息中，再向节点n1传输。节点n1接收了消息后，表明节点n2是自己一跳邻居节点，再建立邻居表。

图3 邻居节点感知过程

在传统的OLSR协议中，所有节点采用固定时间间隔传输H_M消息，并未依据节点个体特性,此外，该协议在传输LSA_M消息时也是采用固定周期。为此，本文先引用LMM模型优化tH(i)和tA(i)，进而改进OLSR路由协议的性能，且将此路由记为LMM-OLSR。

4 性能分析

4.1 实验环境

考虑300 m×300 m移动网络场景。总节点数32个，其中移动节点数10个，其余22个节点静止。10个移动节点随机移动，且移动速度服从正态分布[V-2.5,V+2.5],其中V表示数值仿真图的横轴。节点传输半径为250 m，IEEE 802.11速率为4 Mbit/s，控制包类型为CBR，且数据包尺寸为512 B，数据包传输速率为50 packets/s。

此外，为了更好地分析LMM-OLSR协议性能，选择传统的OLSR[13]和AFE-OLSR[14]进行比较分析。主要分析数据包端到端传输时延、数据包丢失率以及路由开销。每次仿真独立重复100次，取平均值作为最终的仿真数据。

4.2 实验数据分析

1)端到端传输时延

首先分析数据包端到端传输时延随节点移动速度的变化曲线，节点移动速度从0～30 m/s变化，实验数据如图4所示。可知，LMM-OLSR的端到端传输时延最低。此外，在节点低速运动时，AFE-OLSR和OLSR协议的端到端传输时延性能相近，但随着移动速度的增加，且当移动速度大于5 m/s时，AFE-OLSR协议的端到端时延低于OLSR协议，这说明：在节点高速移动的环境下，AFE-OLSR协议更能快速地找到路由，缩短了端到端传输时延。

图4 端到端传输时延随节点移动速度的变化情况

2) 数据包丢失率

数据包丢失率越大，路由性能越差。3个协议的数据包丢失率数据如图5所示。

图5 数据包丢失率随节点移动速度的影响

可知，数据包丢失率随移动速度的增加而下降，但下降速度变缓慢。这说明：最初，随着节点速度的增加，节点移动活跃，为路由选择提供了方便，进而提高了选择有效路由的概率。与OLSR和AFE-OLSR协议相比，提出的LMM-OLSR协议的数据包丢失率最低。说明， LMM-OLSR协议能够有效地提高数据包传输性能。

3)路由开销

实验数据如图6所示，可知，在移动速度较小时，提出的LMM-OLSR协议的路由开销小于OLSR和AFE-OLSR。但随着移动速度的增加，LMM-OLSR协议的路由开销高于OLSR和AFE-OLSR协议。主要因为：当移动速度的增加，加剧网络拓扑的变化，为了提高路由协议性能，需要缩短传输H_M和LSA_M消息的间隔，必然加大了路由开销。

图6 路由开销

5 结 论

提出了基于拉格朗日乘子优化传输控制消息间隔模型LMM，仿真结果表明，提出的LMM模型能够有效地抑制路由开销，降低因节点失效而产生的路由损失，进而有效地提高数据传输效率，并降低了端到端传输时延。