基于选播机制的无线Mesh网络网关选取路由算法*

李陶深，丘小兰，葛志辉

（广西大学计算机与电子信息学院 南宁 530004）

1 引言

无线Mesh网络（wireless mesh network,WMN）与因特网互连成为近年来研究的热点。为了完成WMN与因特网的互连，通常在一个WMN中配备多个Mesh网关。若节点有连接因特网的需求，它首先要找到所有可连接的网关，然后通过有效的网关选取策略在这些备选网关中根据一定的判定标准选择一个最佳网关接入因特网。然而，由于现实的WMN中流量分布明显不均，网内大部分业务流量都汇聚于网关，使得一部分网关负载过重，容易造成局部网络拥塞，所以网关节点往往是形成网络拥塞的热点区域及网络性能的瓶颈[1]。因此，网关选择策略是优化Mesh网络吞吐量、改善网络性能的主要途径。

目前在WMN网关选取策略方面的解决方案主要有3类：第1类是以移动节点到网关的跳数为选择标准[2]，这种策略简单、易实现、收敛快、时延小，但在网络出现拥塞时会导致网络性能严重下降[3]；第2类是将跳数和其他因素综合起来作为选取标准，如参考文献[4]提出将跳数和网络的拥塞水平、信道争用水平综合起来考虑，参考文献[5]则用跳数和网关负载作为网关选择和切换的标准；第3类是将跳数之外的因素作为选择标准，如参考文献[6]提出的WMN网关选取策略着重于如何把终端分配到各个网关。这3类网关选取策略在寻找路径或更新路由时，基本上都采用泛洪的方式，当网内节点数较多、负载很大时，这些协议寻径和更新路由的控制开销迅速增多，不仅严重阻塞网络，而且大大减少数据发送成功率，降低路由算法的性能。

选播是一种新的网络服务通信模式，己被IPv6定义为标准的通信服务[7]。选播的关键在于，对于一个给定的应用和一组可提供相同服务的服务器，它能够为客户端有效地寻找到性能“最好”的服务器。本文将研究基于选播思想的WMN网关选取优化问题，将网关的选取问题看作网络选播通信来处理，并提出了基于选播机制的网关选取路由模型，设计实现相关的协议与算法，分析比较其性能。

2 网络模型与选播路由树

2.1 网络模型

本文把WMN抽象为一个无向图G=(V，E)，其中，V表示WMN中有限节点的集合，这些节点在一定范围内通过无线信道进行通信，其中一些节点是通过有线电缆与因特网直接相连的网关节点,用G(A)={g1,g2,…,gk}表示；E表示网络中连接节点对的通信链路集合。如果节点u和v之间的距离小于或等于节点通信的有效距离r，则称这两个节点互为邻居节点且它们之间存在一条边（即有路由链路相连）。

WMN网关选取的路由问题可以描述如下：给定一个WMN网络G=(V，E)和一个选播 QoS请求Q=(C，G(A)，Req)，其中，C是请求服务的Mesh客户节点，G(A)表示网关组（选播组）节点集合，Req为QoS参数约束。这样就可以将WMN的网关选取问题转化为QoS约束的路由选择问题。

2.2 选播模型

WMN中有若干网关节点时，终端用户需要选择一个合适的网关节点接入因特网，这就属于典型的网络选播通信问题。为了提高网络服务的可用性和健壮性，本文将选播机制引入网关选取路由，如图1所示，将所有接入因特网的网关节点抽象成一个选播组，这些网关节点分布在网络的各个部分，每个网关节点都是这个选播组成员。当带QoS约束的用户端需要服务时，通过有效的选播机制能够自适应地选择最优的网关节点为其服务，从而节省网络带宽，减少阻塞，保证WMN良好的接入性能。

2.3 选播路由树

选播路由树（也称网关树）模型如图2所示，它包含3类节点。第1类是网关组（即选播组）组长节点，此节点所在的网络区域的单播地址空间必须与其所拥有的选播地址空间相同，即目的地址为单播地址的数据分组，可以按照正常的单播路由方式被路由到此组长节点。在本模型中，组长主要负责维护网关组的序列号码，以及在路由模块中自适应地选择“最优”的网关节点为请求节点提供服务。第2类节点是中间节点，也称作树成员节点，它们不能提供接入因特网服务而只用于支撑网关树框架，这类节点一般都是路由器。第3类节点是叶子节点，也称作网关组成员节点，这类节点是可以提供接入因特网服务的节点，一般都是网关。在本模型中，组长节点与叶子节点都可以提供接入因特网服务，具有一个共同的选播地址。

图2 选播路由树模型示意

3 基于最小时延的WMN网关选取路由算法

本文提出的基于最小时延的网关选取路由算法（DGRA）是在AODV协议上的选播扩展，由选播路由树的构造、选播路由树的维护、路由分析3部分组成。

3.1 选播路由树的构造

选播路由树构造的具体步骤如下。

·将源节点S放入集合U中，TE=Null。

·在所有 u∈U 且 u埸G’(A),v∈P的边（u,v）中，找出时延小于源节点S对业务提出的最小时延限制的所有边，计算树上所有节点的不在树上的邻居节点若加入后的所有可能干扰度，然后从中选出干扰度最小的节点v。将节点v并入U中，并将节点v与它的父节点间的链路加入集合TE。

·若P为空，在选播树T上选择从源节点S到网关选播组成员中时延最小的一条路径，转下一步。否则，转上一步继续构造选播树T。

·输出在网中建立的以源节点S为根的选播路由树T=(U,TE)，过程结束。

3.2 选播路由树的维护

本模块主要完成节点加入网关组、节点离开网关组、树的链路断开时的处理、树的重建等工作。

（1）节点加入网关组其操作步骤大致如下。

·当节点欲加入网关组时，将广播带有J_flag标志的路由请求信息分组RREQ。不是网关组成员的中间节点收到此RREQ后，再把这个RREQ广播给邻节点。该节点将建立逆向路由条目，更新选播路由表。

·选播组成员节点收到RREQ后，更新路由和选播表，单播RREP给源节点。路径上节点更新路由表和选播表，建立前向路由。

·源节点选择最大序列号和时延最小的路由，并激活所选择路由的下一跳信息，然后沿着所选路径选播激活信息（AACT）。

（2）节点离开网关组

如果欲离开的网关组成员节点不是树中的叶子节点，则只需把组地址置0；如果节点是树的叶子节点,则单播P_flag标志的AACT分组信息到上游节点并删除自己对应的路由表项,将自己从树中删除,上游节点收到这个P_flag标志的AACT后将删除选播表中的有关项；如果自己是组成员或不是叶节点，剪枝过程就结束，否则继续给自己的上游节点发送P_flag标志的AACT。

（3）树的链路断开时的处理

其操作步骤如下。

·下游节点广播带有J_flag标志的RREQ重新加入网关组，扩展域Agroup_delay为自己到组长的时延，只有具有最新的序列号且到群首的时延小于此RREQ中的Agroup_delay的树成员才能回复。

·如果响应的上游节点不是组成员或是叶子节点，则设置定时器等待树枝通过它重建，如果一段时间后没有对应组激活的下游节点，则发送剪枝消息将自己从树中剪去。

·如果链路修复失败，网络被分割，新分出来的网络需要新的组长。如果发起修复的节点是组成员，则成为新组长，否则通过发送GL_flag标志的AACT选择新的组长。

（4）树的重建

当原本已分开的网络部分又连接在一起时，就会带来分开的树又合并的问题。节点会收到一个hello分组，它所包含的信息与节点所保持的信息有所不同。如果节点是网关组的成员且是含有地址较低的组长的那部分树的成员，那么它就会启动树的重新构造过程。

3.3 路由分析

路由分析模块主要完成产生路由请求RREQ分组、处理和传输RREQ、处理路由请求、产生路由应答RREP、转发RREP、网关组的维护等任务。下面是路由协议的具体实现过程。

·若源节点需要向网关组成员发送数据，它首先查询单播路由表。如果有到该组相关成员的路由项，则直接选择一条时延最小的路由返回即可；如果没有路由项，则源节点发送RREQ报文。

·如果接收到RREQ的中间节点不是选播组成员，则检查自己是否有到该选播组的路由。如果有此路由项，则选择一条最新时延最小的路由即可；如果没有，则该节点重新广播收到的RREQ，在选播路由表中添加到源节点的路由项，并把下一跳设置成将RREQ发送给它的节点。

·如果接收到RREQ的中间节点是选播组成员，则更新选播路由表，并把本节点的时延信息发送给网关组组长。组长节点可能会收到多个带有时延信息的信息分组。

·网关组组长记录这段时间内收到的最大序列号、最小时延的路由请求信息分组，等待时间到达后，向源节点发送RREP消息。

·转发RREP。RREP以单播的方式沿RREQ传播时所建立的反向路径发送到源节点，这样就建立了源节点到网关组某成员的正向路径。

4 仿真实验与算法性能

4.1 NS2仿真场景设置

为了分析算法的性能，采用Linux下的NS-2.31版本进行仿真。首先在1 000×1 000 m2的区域内生成6×5个节点的拓扑结构，如图3所示，节点4、15、19为网关节点。各节点都是WMN骨干层的MR，包括网关节点，处于静止状态。节点间的通信范围是250 m，相邻节点直线距离是190 m。业务流类型为CBR（恒定比特率，属于UDP业务流），流量为每秒发送8个数据分组，分组大小为512 byte。业务流数目分别为 3、6、9、12、15、20 条，仿真时间为 300 s。

4.2 实验结果与分析

以不同业务流数目下协议的分组投递率、端到端时延和平均路由控制开销为性能指标，对本文的DGRA算法和AODV算法进行比较。其中，分组投递率是指实际收到和期望收到的分组数的比值，用于反映网络所能支持的最大吞吐量，从而在一定程度上刻画了算法的完整性和正确性；端到端时延则表示从数据源发送数据分组起到所有目的节点接收到该数据分组时的平均时间间隔，时延越小，说明响应越快，网络性能越好；平均路由开销是指路由控制分组数目与网络层业务数据分组数目之比。

图3 仿真拓扑结构

图4给出了分组投递率的实验比较情况。从图4可以看出，AODV算法根据跳数选择路由，网络中某些节点容易形成热点区域，导致拥塞，使得经过这些热点区域的分组丢失率增大。而本文引入选播机制的DGRA算法能平衡网络负载，从众多路径中选择最优路径，从而避免拥塞区域，因此分组投递率高于AODV。

图4 分组成功投递率对比

图5给出了端到端时延的实验比较情况。从图5可以看出，随着网络拥塞程度的增加，AODV数据分组的时延增加明显，而DGRA在算法中支持了时延约束的要求，能够进行局部路由重构以尽快找到新的到达网关节点的QoS路由，整体上降低了网络中传输的时延。

图5 端到端时延对比

图6 平均路由开销对比

图6为不同业务流数目下平均路由控制开销的变化情况。从图6可看出，当网络负载比较轻时，DGRA算法的平均路由控制开销比AODV高，其原因是：DGRA通过选播树实现对选播组成员的管理与维护，算法将产生大量的路由开销。但是当网络负载较重时，由于DGRA算法采用选播机制，源节点能够自适应选择更可靠的传输路径，在传输过程中能够减少链路发生断裂的概率，使得路由协议的开销减少。

5 结束语

本文对无线Mesh网络网关选取策略进行研究，将选播通信机制应用于多网关选取路由的问题中，并针对实时性要求比较高的传输业务，设计了一种基于最小时延的无线Mesh网络网关选取路由算法。该算法在引入选播机制的网关选取模型的基础上，以时延为度量，为客户节点提供响应最快的高质量的因特网无线宽带接入。仿真实验结果表明，在WMN中，通过选播路由机制DGRA算法，能有效地解决多网关选取问题，保持较高的分组传递率、较低的数据分组时延，使接入网络稳定高效地运行。这在应用中具有很大的现实意义，能有效满足网络规模扩大的因特网流量需求。当WMN规模增大到一定程度时，可平衡往来于因特网的网络流量负载，通过本文算法的选播机制就近选择最优的网关出口为用户提供接入服务。

1 葛志辉,李陶深,张继成.无线Mesh网络逐层信道分配策略研究.广西大学学报(自然科学版),2010,35(6):13～17

2 Shin C,Kim S,An S.Stable gateway selection scheme based on MANET with Internet.In:The Sixth IEEE International Conference on Computer and Information Technology,Dhaka,Bangladesh,2006

3 Brannstrom R,Ahlund C,Zaslavsky A.Maintaining gateway connectivity in multi-hop ad hoc networks.In:The IEEE Conference on LocalComputerNetworks30th Anniversary,Sydney,Australia,2005

4 宋文,方旭明.无线Mesh网络公平感知路由算法设计与仿真.系统仿真学报,2007,19(18):4 320～4 325

5 Draves R,Padhye J,Zill B.Routing in multi-radio,multi-hop wireless mesh networks. In: ACM Annual International Conference on Mobile Computing and Nerworking,Philadelphia,USA,September 2004

6 Kim Y,Jeong Y,Seo M,et al.Load-balanced Mesh portal selection in wireless mesh network.In:Military Communications Conference,Orlando,USA,Oct 2007

7 Li Taoshen，Zhao Zhigang. An adaptive particle swarm optimization algorithm for anycast routing. Journal of Computational Information Systems,2011,7(5):1 559～1 566