基于混合架构无线Mesh网的多路径路由协议

沈 华

(1.湖北工业大学计算机学院，湖北武汉 430068;2.武汉大学计算机学院，湖北武汉 430072)

无线 Mesh网络(wireless mesh networks，WMNs)的路由是一项关键技术［1-2］。一方面，WMNs继承了Ad hoc网络的特点，Ad hoc网络的一些路由协议可以应用到WMNs中，如基于距离矢量的按需路由协议(on-demand distance vector routing，AODV)［3］、动态源路由协议(DSR)［4-5］等;另一方面，WMNs在移动性、能量约束、业务模式等方面又有着不同于Ad hoc网络的特性。因此，如何使Ad hoc环境下的路由协议更好地适用于WMNs成为一个研究热点。同时，相对于单路径路由协议，多路径路由协议在容错、路由可靠性和QoS路由等方面有较大优势。为了进一步提高移动自组网络的路由质量，多路径路由也逐渐被广泛关注［6-10］。

基于此，提出了一种改进DSR的路由协议，即MOMDSR(mesh-oriented multipath DSR)协议。MOMDSR针对混合架构WMNs的特点并借鉴分级路由的思想，提出了一种有效减少数据报文头部源路由信息的方法，同时在路由发现过程中引入了多路径路由的思想，使得协议在路由开销、报文传输率等性能上有所改善。

1 协议概述

1.1 协议的适用环境

MOMDSR的适用环境是客户端域互不相交的混合架构WMNs，即不同客户端域中的节点之间不能直接通信，它们的通信必须通过Mesh骨干网完成。以楼宇间的WMNs为例，一栋楼中的各种 Mesh客户端(如便携式 PC、PDA、IP电话等)自组联网构成一个客户端域，它们可以通过多跳的方式互相通信。而楼宇间(即不同客户端域中)的Mesh客户端通过WMNs骨干网来实现通信，该骨干网由楼宇中的Mesh路由器构成。同时通过这个骨干网，楼宇中的节点还可以访问Internet或其他的无线网络。

1.2 引入的概念

在MOMDSR中引入了“临界Mesh路由器”和“合法路由”两个概念。

“临界Mesh路由器”是指与某个或某几个Mesh客户端直接连接的Mesh路由器。如图1中，节点B、D是客户端域Ⅰ的临界Mesh路由器;节点C、D是客户端域Ⅱ的临界Mesh路由器;节点G是客户端域Ⅲ的临界Mesh路由器。

图1 路由请求的5种情况

1.3 MOMDSR数据报文头部的路由信息

数据报文在客户端域内传输时，头部携带的是域内的源路由信息;当它在骨干网中传输时，采用逐跳路由。例如，假设客户端域Ⅰ中的节点A向客户端域Ⅱ中的节点E发送数据报文，并假设B、C分别是Ⅰ和Ⅱ的临界Mesh路由器，那么数据报文头部初始包含A到B的路由信息;到达B后，删除头部的路由信息并按B路由表中的下一跳信息进行转发;当到达C后，头部将包含从C到E的路由信息。如果Ⅰ和Ⅱ的临界路由器相同(假设都是B)，那么当数据报文到达B后，用从B到E的路由信息覆盖头部原有的路由信息。

1.4 MOMDSR中的多路径策略

客户端域内或骨干网中的多路径节点是不相关的，客户端域间或客户端域与骨干网间的多路径是链路不相关的。路径相关性的判断由目的节点和源节点共同完成。多路径路由的使用模式是替换多路径(或备份多路径)模式。

2 协议结构

2.1 协议中各报文的具体格式

(1)MOMDSR 路由请求(route request，RRQ)报文是在DSR路由请求报文的基础上增加“源节点所在客户端域标识”字段得到的。如果发起路由请求过程的是Mesh路由器，则不需要填写该字段。此外，还增加了节点类型字段，用来记录所经过节点的类型。

(2)MOMDSR 路由响应(route reply，RRP)报文是在DSR路由响应报文的基础上增加“目的节点所在客户端域标识”字段得到的。如果目的节点是Mesh路由器，则不需要填写该字段。此外，还增加了节点类型字段。

(3)MOMDSR路由确认(route acknowledgement，RAK)报文(如图2所示)帮助Mesh路由器形成逐跳路由表。

图2 路由确认报文

2.2 节点所需维护的数据结构

(1)节点信息表。节点信息表数据结构图如图3所示。

图3 节点信息表数据结构图

对于Mesh客户端而言，需要填写“所在客户端域标识”字段。对于Mesh路由器，“客户端域标识i”记录以该节点为临界路由器的客户端域标识。

(2)Mesh客户端的路由表。Mesh客户端的路由表数据结构图如图4所示。

在进行驾驶行为评价的过程中，各个状态之间没有明确界限，具有模糊性. 选择函数性质稳定、控制平缓、分辨度高的梯形隶属度函数. 根据采集到的驾驶行为影响因素分布情况，分析其平均值、中位数、四分位数等关键数据，结合专家修正意见，建立急加速次数、急减速次数、长时怠速次数、长时加速次数的隶属度函数，如图2所示.

图4 Mesh客户端的路由表数据结构图

根据合法路由的定义可知，＜节点1，节点2，…，节点M＞记录的要么是该节点到目的节点的路由，要么是该节点到某个临界路由器的路由。

(3)Mesh路由器的路由表。如果下一跳是Mesh路由器，则记录下一跳的地址;否则记录从下一跳开始的后继路由。

3 协议工作过程

3.1 MOMDSR的路由发现过程

当源节点的路由表中不存在到达目的节点的路由时，源节点通过广播RRQ来启动路由发现过程。根据所讨论的环境，可知有以下5种情况:源节点和目的节点属于同一客户端域，如图1中的F和E;源节点是Mesh客户端，目的节点是Mesh路由器，如图1中的A和G;源节点是Mesh路由器，目的节点是Mesh客户端，如图1中的G和E;源节点和目的节点均是Mesh路由器，如图1中的B和G;源节点和目的节点属于不同客户端域，如图1中的A和E。

当一个节点接收到RRQ时，采用以下步骤进行处理:

(1)如果该节点是目的节点，那么首先判断该RRQ中的路由跳数是否大于之前收到的路由跳数，如果大于，则丢弃该RRQ;否则继续判断RRQ中的路由与之前收到路由的相关性，如果相关，则丢弃该 RRQ;否则，向源节点返回一个RRP。如果该节点的路由表中没有到达源节点的路由，那么将启动路由发现过程。如果该节点不是目的节点，则进入步骤(2)。

(2)检查RRQ的路由记录是否已包含该节点，若包含，则丢弃该RRQ;否则，进入步骤(3)。

(3)判断RRQ的路由记录在加入该节点后是否合法，如果不合法，则丢弃该RRQ;否则，进入步骤(4)。

(4)判断该RRQ是否是重复RRQ，如果不是，则进入步骤(5);否则，接着判断该RRQ中的路由跳数是否小于第一次收到的RRQ中的路由跳数。如果小于，则继续转发该RRQ;否则，丢弃该RRQ。

(5)在路由请求表中记录该RRQ的相关信息;再将自己的地址和类型附加到RRQ后，转发该报文。

3.2 MOMDSR的路由确认过程

第一个到达源节点的RRP将触发MOMDSR路由确认过程的开始。有以下3种情况:①源节点在接收到一个从目的节点发来的RRP之前没有收到过从中间节点发来的RRP。在这种情况下，源节点将判断RRP返回的源路由中是否包含Mesh路由器，如果包含，则根据RRP的内容形成RAK，并发送该RAK;否则，将直接存储该路由。②源节点在接收到一个从目的节点发来的RRP之前收到过中间节点发送的RRP。在这种情况下，源节点首先判断RRP返回的路由与中间节点返回的路由是否相关，如果相关，则丢掉该路由;否则，进入情况①的处理过程。③源节点在收到某个中间节点发送来的RRP之前，已经收到过目的节点返回的RRP或其他中间节点返回的RRP。在这种情况下，源节点首先判断该中间节点返回的路由与已收到路由的相关性，如果相关，则丢掉该路由;否则，进入情况①的处理过程。需要说明的是，RAK根据源路由进行发送。

下面说明中间节点处理RAK的过程。

如果是客户端节点接收到RAK，那么它将直接向下一跳节点进行转发;如果是Mesh路由器接收到RAK，且下一跳仍是Mesh路由器，那么它将RAK中的目的节点地址、剩余跳数和下一跳节点地址等信息填写到自己路由表的相应字段中;如果下一跳是客户端节点，那么它将RAK中的目的节点地址、剩余跳数、从下一跳节点开始到目的节点的路由等信息填写到路由表的相应字段中;然后，向下一跳转发该RAK。例如，当包含如下路由信息C(1)-D(1)-E(1)-F(1)-G(0)-M(0)-N(0)(Ⅱ)的RAK在到达节点N之后，路由上各Mesh路由器的路由表为:C(N，6，D);D(N，5，E);E(N，4，F);F(N，3，G-M-N)。并且在源节点A的路由表中关于该路由的记载为(N，8，B-C)。

3.3 MOMDSR的路由维护过程

在路由建立后，就进入路由维护阶段。MOMDSR采用的是一种混合式的路由维护，即在客户端域内采用按需式路由维护，在骨干网中采用主动式路由维护。这样可使Mesh路由器的路由表得到及时更新并降低路由维护的整体开销。

4 仿真实验和性能分析

4.1 仿真模型

对DSR、MOMDSR协议进行了仿真实验，所采用的仿真平台是Windows+cygwin+nsallinone-2.28。

仿真模拟了一个有50个移动节点的WMNs，并且这些节点随机分布在一个1500 m×300 m的矩形区域内，整个仿真时间为450 s。在仿真中，移动节点按照Random Waypoint移动模型移动，并且采用CBR(constant bit rate)流量源来产生通信量，以4个/s的速率发送报文，在该仿真中含有20个CBR源。

这里仿真的协议性能是暂停时间的函数，并且针对两种节点移动速度的最大值(1 m/s和20 m/s)。在仿真中，定义了7个不同暂停时间的移动模型，分别为 0 s，20 s，40 s，70 s，150 s，300 s和450 s。暂停时间为0，表示连续不断地移动;暂停时间为450 s，表示节点静止。

4.2 协议性能比较参数

(1)报文传输率=成功接收到的数据报文数/发送的数据报文数。

(2)路由开销=路由报文数。

4.3 仿真结果及分析

在图5(a)中，可以看到在移动速度最大值为1 m/s时，有7个暂停时间处MOMDSR的报文传输率要略高于DSR协议。从图5(c)中可以看出在较高移动速度下，MOMDSR在报文传输率性能上的优化要更加明显。

图5 MOMDSR和DSR的报文传输率和路由开销的比较(分别在1 m/s和20 m/s两种移动速度下)

比较图5(b)和图5(d)发现，在较低或较高移动速度下，都是在移动较频繁时，MOMDSR的路由开销要小于DSR，但在节点相对稳定时，MOMDSR的路由开销要略高于 DSR。总体上看，MOMDSR的路由开销性能略优于DSR。

5 结论

提出了一种基于混合构架无线Mesh网络的多路径路由协议MOMDSR。在MOMDSR中，引入了路由确认阶段，修改或设计了相关数据结构，实现了Mesh骨干网中的逐跳路由，使得数据报文在骨干网中传输时，不用携带路由信息，而在客户端域内传输时，只需携带部分源路由信息，缩短了DSR中数据报文头部的路由信息。在MOMDSR的路由发现过程中引入了临界Mesh路由器、合法路由等概念，实现了多条路由的发现。仿真结果表明，MOMDSR在路由开销、报文传输率等方面略优于DSR。

［1］AKYILDIZ I F，WANG X D，WANG W L.Wireless mesh networks:a survey［J］.Computer Networks，2005，47(4):445-487.

［2］RAYNER K.Mesh wireless networking［J］.IEEE Communications Engineer，2003，1(5):44-47.

［3］PERKINS C E，BHAGWAT P.Highly dynamic destination-sequenced distance-vector routing(DSDV)for mobile computers［J］.Comp Comm Rev，1994(10):234-244.

［4］JOHNSON D，MALTZ D.Dynamic source routing algorithm for mobile wireless networks［C］//IEEE NFOCOM1997.［S.l.］:［s.n.］，1997:1405-1413.

［5］JOHNSON D B，MALTZ D A.The dynamic source routing protocol for mobile Ad Hoc networks［ED/OL］.［2011-07-05］.http://www3.ietf.org/proceedings/02nov/I-D/draft-ietf-manet-dsr-07.txt.

［6］NASIPURI A，DAS S R.On-demand multipath routing for mobile Ad Hoc networks［C］//Proc IEEE ICCCN.［S.l.］:［s.n.］，1999:64-70.

［7］LEE S J，GERIA M.Split multipath routing with maximally disjoint paths in Ad Hoc networks［J］.IEEE，2001，10(6):3201-3205.

［8］PHAM P P，PERREAU S.Increasing the network performance using multi-path routing mechanism with load balance［J］.Ad Hoc Networks，2004，2(4):433-459.

［9］LEI W.Multipath source routing in wireless Ad Hoc networks［C］//2000 Canadian Conference on Electrical and Computer Engineering.［S.l.］: ［s.n.］，2000:479-483.

［10］MUELLER S，GHOSAL D.Multipath routing in mobile Ad Hoc networks:ssues and challenges［R］.［S.l.］:Invited Paper in Lecture Notes in Computer Science，2004.