基于无循环转发的NSR改进路由

崔炳德，裴祥喜

(河北水利电力学院，河北 沧州 061001)

0 引 言

随着光纤技术快速发展，基于光纤的宽带网络被广泛使用。目前，光纤已成城乡的主干网络，而无线Mesh网络(Wireless Mesh Networks, WMNs), 作为高速率、高容量的多点对多点的分布式网络，已受到广泛关注[1-2]。由于具有快速部署和自组织特点，WMNs非常适应于临时的按需网络部署场景。然而，WMNs的自组织性、高容量和高速率特性，给路由算法提出了挑战。

现存的WMNs多数路由是基于移动AdHoc网络，然而这些路由并没有充分考虑WMNs的特点。WMN性能容易受到干扰和网关拥塞的影响，这会导致数据包丢失和高时延[3-4]。为了提高WMNs的路由性能，研究人员提出多个不同的路由方案，如Stine提出基于方向和智能天线方案、Cao提出的协作通信、Canada提出节点稳定的路由(Node Stability-based Routing, NSR)。

路由方案对网络性能有重要的影响。确实，路由的主要目的就是寻找最佳路由。为了获取最佳的网络性能，路由指标应具有1)不影响网络稳定；2)融合了Mesh网络特性;3)避免转发循环。其中路由循环对网络性能有重要的影响。而目前多数路由并没有考虑。

为此，本文以NSR路由为基础，提出无循环转发算法的NSR路由NSR-LFFA。NSR-LFFA路由以图论为基础，再构建生成生成树，通过生成生成树转发数据包，从而降低循环路由的概率[5]。实验数据表明，提出NSR-LFFA路由有效降低时延，并提高吞吐量。

1 网络模型

考虑多跳WMNs，将节点分为两类：Mesh路由MRs和网关GWs，如图1所示。MRs形成多跳无线主干网，完成用户与Internet间的流量传输。为了将流量传输至Internet，流量需通过网关传输。每个MR装备了多个无线接口，且每个接口上具有多个信道。假定MR的接口有多个不同的信道。

图1 典型的无线网状网络WMNs结构

将主干WMN为一个图论G=(V,E)，其中V为节点集(MRs和GWs)，E为链路集。令ij表示两个MRs(υi、υj)间的链路，且υi、υj∈V。此外，通过GWs连通Internet。

2 基于无循环转发的NSR路由

路由循环是分布式路由协议的严重问题。当数据包无限地通过相同路由传输时，就产生路由循环[6-9]。一旦发生路由循环，就会增加网络开销、数据包丢失以及宽带可用率下降。

为了阻止路由无循环，引用无循环转发算法(Loop-Free Forwarding Algorithm, LFFA)。LFFA的思路就是寻找一系列链路向给定网关转发数据包。为此，此寻找问题定义为图理论问题。

假定WMNs为网络图G(V,E),其中V={1,…,n}为节点集，而E为有向网络链路集。令GW⊆V为WMN的网关集。将每个GW的网关g构成一个有向树Tg,其以网关g为根。树的边集为ETg,所有顶点集为Vg={V/GW}∪g。

构建有向树Tg的过程就是决定有向链路EFg⊂E集的过程，致使有向图Fg=(V;ETg∪EFg)是无循环的。LFFA的伪代码如图2所示。

图2 LFFA的伪代码

最初，以顶点集V和边集ETg构建以网关g为根的生成 树。利用生成树，可产生源节点与网关间的有序拓扑树[10-12]，同时确保每个节点与其相应网关间的最短路径链路加入于可用的转发集内。

因此，第一步先选择一个网关(假定网关为g)，再以网关为根节点建立生成树Tg。具体而言，先设E*={E-ETg}，然后令dg表示树Tg的深度。相应地，定义节点集Li，其表示离网关距离为i的节点集，再引入变量k=dg。

第二步，从Lk中选择一个节点u，致使其满足式(2)：

δ(u)=minu′∈Lkδ(u′)

(2)

其中δ(u)表示节点度。从式(2)可知，节点u表示在Lk集中，节点度最小的节点。

第三步，将已选节点的外向链路加入可转发节点集内，如式(3)所示：

EFg=EFg∪e(u,ω)

(3)

其中u为已选节点，而e(u,ω)为u与ω间的链路。

第四步，将已选节点的流入链路从可转发集内删除。然后，再判断LK集是否为空，如果LK=φ，则将K=K-1。随后，再判断k值是否为零。如果K≠0，则返回到第二步，否则执行第五步。

第五步，构建有向转发图Fg=(V,ETg∪EFg)。然后将网关g从集GW*内删除。最后，判断GW*是否为空。如果不为空，说明还有另一个网关需要建立生成树，需要执行第一步，否则停止算法。

为了更好地理解LFFA算法，示例说明。如图3所示，两个网关G1和G2，5个Mesh路由，分别为1、2、3、4和5。a、b、c、d、e、f、g、h、i、j、k、l分别表示有向链路，例如，d表示由于MR1指向MR4的有向链路。将网关集GW={G1,G2}和以G1、G2为根生成树作为算法2(LFFA)的输入。

图3 无循环的拓扑示例

图4(a)显示了构建以网关G1为根的生成树。表1总述了这个具体过程。第一步，计算E*={E-ETg}={b,c,d,g,k}，且其树深度dG1=3。L1={2,4},L2={5,3},L3={1}。

表1 建立网关G1为根的生成树过程

先以K=3为例。第二步，将从L3中选择节点MR1成为节点u；第三步构成EFG1={d,c}；第四步，建立E*={b,g},L3={}。然后执行K=K-1=2，再重复上述过程，直到K=0，再执行第五步，最终形成EFG1={a,e,f,i,j,b,c,d,g}，如图4(b)所示。完成了以网关G1的转发集后，再执行以网关G2的转发集。

图4 以G1为根的生成树

3 仿真及分析

利用NS-2仿真器建立仿真平台[14-15]。考虑在1000×1000区域内随机部署16个MRs和3个GWs的无线Mesh网络。引用基于IEEE 802.11的MAC层协议。链路数据率为11 Mbps、频率为9.14e+08 Hz、流量类型为CBR、数据包尺寸为1000bytes。仿真时间为100 s，每次实验独立重复20次，取平均值作为最终实验数据。

首先，分析节点稳定的路由(Node Stability-based Routing, NSR)和NSR-LFFA的传输时延，实验数据如图5所示。

图5 传输时延

NSR协议总是选择最稳定的节点作为向所选择的网关转发流量。从图5可知，与NSR路由相比，提出的NSR-LFFA路由的时延得到有效控制。主要原因在于：NSR-LFFA引用生成树避免了转发循环，并建立了连通给定网关的可用链路集。与NSR路由相比，NSR-LFFA路由中每个节点着力于向稳定节点发送数据流量，并且解决了这些稳定节点间的乒乓效应。此外，仅利用一个稳定节点建立有效路由是不足够的。

接下来，分析NSR协议和NSR-LFFA协议的吞吐量，实验数据如图6所示。

图6 吞吐量随数据率的变化情况

从图6可知，数据率的增加提升了协议的吞吐量。原因在于：数据率的增加，加大了单位时间内所传输的数据量，最终也增加了网络内平均吞吐量。此外，与NSR相比，提出的NSR-LFFA路由的吞吐量得到较好地提升，且平均吞吐量提高了近7%。

最后，分析数据包丢失率随数据率变化影响，实验数据如图7所示。

图7 数据包丢失率随数据率的变化情况

从图7可知，数据率的增加破坏了数据包传输的流畅性，使用得数据包丢失率呈增加趋势。原因在于：数据率的增加，加大网络内传输的数据量，也增加网络拥塞的概率，最终提高了数据包丢失率。不过，与NSR相比，NSR-LFFA协议的数据包丢失率得到控制，且平均数据包丢失率下降约3%。

4 结 语

针对无线Mesh网络WMNs的路由循环问题，提出LFFA算法，并将LFFA算法应用于NSR路由。通过建立生成树，降低路由循环的概率。实验数据表明，通过LFFA算法，有效地避免路由循环，进而降低端到端传输时延，也提高了系统吞吐量。