一种基于mesh网络的多径路由协议

徐婷,李珊君

（四川大学 电气信息学院，四川 成都 610065）

一种基于mesh网络的多径路由协议

徐婷,李珊君

（四川大学 电气信息学院，四川 成都 610065）

针对无线mesh网络的特点提出了一种基于源节点建立、目的节点维护的多径路由协议。该协议采用目的节点更新mesh结构的机制，能实时维护最优路径和其余多条路径，当节点移动或其他原因造成链路断开时，不需要路由修复或重建，从而降低了丢包率和端到端时延，且通过基于源节点建立路由的方式有效地减少了控制开销。仿真结果表明，该算法具有良好的性能。

无线mesh网络；路由算法；多径

近年来，无线 mesh网络（WMN）由于其灵活性和实用性受到越来越多的关注与应用。WMN是一种高容量、高速率的分布式网络。它不同于任何传统的有线或无线网络，正是网络的特殊性使得传统网络的路由技术无法直接应用于WMN，使WMN路由算法的探讨成为这个领域的研究热点。而多径路由因其有效利用带宽、减小拥塞和增加传输可靠性、实现负载和能耗均衡等一系列优点，得到了广泛的重视。

目前存在的多径路由协议基本上可以分为两类：一类是表驱动协议（如 QOLSR[1]）。在该类协议中，各节点通过周期性的广播路由信息分组，交换路由信息，主动发现路由，同时，节点必须维护去往全网所有节点的路由；另一类是按需路由协议 （如 AOMDV[2]、MSR[3]和MRABM[4]），这类协议仅在源节点要发送分组但没有去往目的节点的路径时，才“按需”进行路由发现。这些路由协议都在不同程度上提高了网络的路由性能，但仍存在一定不足。除MRABM以外，其余几种路由协议均是基于源节点或中间节点维护的路由协议，当所有路径都失效时，再重新发起路由建立过程。这样，当网络拓扑变化较快或网络负载较高时，将面临严重的丢包问题，最重要的是不能实时维护到目的节点的最优路径。而MRABM采用的基于目的节点维护mesh结构的方法，则能很好地解决实时维护最优路径这个问题。但由于该算法的路径建立也采用基于目的节点的方法，将产生较大的控制开销。本文结合以上两点，提出一种基于源节点建立、目的节点维护mesh结构的路由协议。该协议既能为源节点建立到目的节点的实时最优路径，有效利用网络资源，减少网络拥塞，降低丢包率，又能尽量减少控制开销。

1 mesh网络模型

由多个节点互联而成的mesh结构中，每个节点既是主机，也是路由器。当源节点与目的节点不能直接通信时，就需要其他中间节点通过存储转发帮助完成通信，这样便构成了多跳网络。而mesh结构中两个节点之间具有不只一条路径的特性，使得网络中任何一条链路的中断或任何一个节点的离开均不会导致通信的中断。mesh结构示意图如图1所示。

图1 mesh结构示意图

链路AC断开后，上游节点A由于收不到下游节点C的联络信息便可知道链路AC已中断，这条路由已不可用，从而不再把数据发给节点C，转而把数据发给它的另一个相邻节点B，节点B将沿它到节点D的最优路径把数据发送至目的节点D。可见，链路AC的中断不会导致通信的中断。

2 多径路由协议

在无线 mesh网络中，数据从需要发送到发送完毕，主要经历mesh的建立、mesh的完善、mesh的维护、数据发送和mesh结构的消失几个阶段。

2.1 mesh的建立

当源节点要向目的节点发送数据时，首先检查自己的路由缓冲器，如果有到达目的节点的路径，就开始发送数据；若没有，就通过广播路由请求分组RREQ（route request）发起路由发现过程，RREQ报文格式如图2所示。

图2 RREQ报文格式

接收到路由请求分组的中间节点，检查它是否有到达目的节点的路径。若有，就沿反向路径发送路由回复分组RREP（route reply），并将 RREQ沿其最短路径传送至目的节点；若无，则判断是否第一次收到该 RREQ分组，如果是，就将该节点添加到路由信息表中，继续广播路由请求分组，否则就丢弃该分组。直到RREQ分组到达的节点有到目的节点的路径或RREQ分组到达目的节点为止，然后该节点或目的节点返回路由回复分组RREP，并将RREQ沿其最优路径传送至目的节点（若已是目的节点则不需要传送）。RREP格式如图3所示。

图3 RREP报文格式

源节点收到RREP后，开始传送数据。

2.2 mesh的完善

mesh初步结构建立以后，源节点便具有了至少一条通往目的节点的路径。源节点沿已有的路径向目的节点发送数据包。同时，目的节点接收到RREQ后，将向周围节点广播一种叫做RRTB的消息分组，RRTB消息分组的内容包括：

（1）RRTB:控制分组的类型;

（2）源节点id:发送RREQ消息的节点标示;

（3）目的节点id:发送该RRTB消息的节点标示;

（4）序列号:该RRTB分组的序列号;

（5）距离目的节点的跳数:该节点距离目的节点的跳数;

旅游业发展水平的分析应包括入境旅游和国内旅游两部分，限于资料统计口径的问题，本文仅摘录入境旅游统计数据进行旅游业发展水平分析。从国际旅游外汇收入变化特征、入境旅游者变化特征、人均天消费变化特征、平均停留天数变化特征四个方面分析。

（6）父节点 id:发送该RRTB消息分组到该节点的节点标示。

目的节点为RRTB消息产生的节点，所以其距离目的节点的跳数为0，其父节点id为目的节点标示。序列号由目的节点更新，采用序列号逐渐增大的方式。

中间节点收到RRTB消息分组后，检查是否第一次收到该消息分组，若是则修改路由表：在路由表中增加一个路由条目；若不是则丢弃。该路由条目的源节点为发送RREQ的节点,目的节点为发送RRTB的节点，并建立与邻居节点的关系。中间节点建立路由表的内容有：

（1）源节点id:发送RREQ消息的节点标示;

（2）目的节点id:发送RRTB消息的节点标示;

（3）邻居节点 id:发送该 RRTB消息到本节点的节点标示;

（4）距离目的节点的跳数:邻居节点距离目的节点的跳数;

（6）收到时间:本节点收到该RRTB消息分组的时间。

中间节点选择到目的节点最少跳数的邻居节点为最优路径,且作为本节点的RRTB消息分组的内容,向周围节点广播。以此类推，直到源节点收到邻居节点发送的RRTB消息，建立源节点到邻居节点的路由表,而不再向周围节点广播自己的RRTB消息分组。这样,源节点和中间节点都建立了到目的节点的最优路径和其他路径，mesh结构得到了进一步完善。

中间节点在收到第一个RTBB消息后，延时一段时间再向周围节点广播自己的RRTB消息分组，以获得足够的路由信息来选出最优路径。为了防止路由表膨胀，节点仅记录符合一定跳数条件的RRTB消息携带的路径信息，否则丢弃该RRTB消息。

2.3 mesh的维护

mesh结构的更新采用事件驱动的方式。在数据传输过程中，如果某个中间节点没有到达目的节点的路由时，就广播路由错误分组RERR（route error），RERR仅广播一跳，邻居节点收到该分组后，将从路由表中删除该节点，并沿最优路径首先向目的节点传输该消息分组，目的节点收到该分组后，将启动路由更新，向周围节点广播新的RRTB消息分组，中间节点和源节点将根据新收到的RRTB消息分组更新自己的路由表，建立新的最优路径和其余多条路径。

可见,这样的路由维护方式不需要源节点发起RREQ的重建过程，只需要目的节点发起RRTB消息分组，比一般的路由重建时间少，且采用事件驱动更新方式，更新次数少，直接进行路由更新避免了路由陈旧问题。

2.4 数据传送

源节点收到周围节点发送来的RRTB消息,建立到目的节点的完善的路由表。低负载时,源节点可以选择一条到目的节点的最优路径传送数据,也可以选择多条路径传送数据。高负载时,源节点可以选择多条路径甚至所有的路径同时传送数据。各路径可以等概率传输,也可以按需传输。数据分配采用每包分配粒度。

若某个中间节点与其所有下游节点的链路都断开,则该节点将向上游节点回传数据分组,上游节点收到回传的数据分组,就沿其他路径传送数据,并删除到该节点的路由,从而尽量减少数据分组的丢失。

若节点移动造成网络分割,而数据包在网络分割点上时,则该节点首先缓存该数据分组。若超过mesh结构的更新时间仍没有收到目的节点的更新分组,便丢弃该数据分组。

2.5 mesh结构的消失

当源节点向目的节点的传送完数据以后,源节点沿最短路径向目的节点发送 stop消息分组,目的节点收到该 stop消息分组后,将停止发送 mesh更新消息分组。stop消息格式如图4所示。

图 4 stop消息分组格式

中间节点若在超时范围内仍没有收到目的节点的更新消息分组，则自动从路由表中删除本项路由信息。

3 实验仿真和评价

本文采用OPNET进行仿真实验，比较本文提出的协议和MRABM、AOMDV路由协议的性能。仿真条件为40个节点在1000 m×1000 m的正方形区域内随机移动，移动符合waypoint模型。设节点的最大移动速度分别为0 m/s、2 m/s、4 m/s、6 m/s、8 m/s和10 m/s,停留时间为0 s。节点通信距离为 200 m，链路带宽为 2 Mb/s，MAC层采用IEEE802.11介质访问控制，传输层采用 UDP协议，应用层采用恒定比特率数据流，数据流为10，分组长度为512 B，产生时间间隔为0.1 s，仿真时间为1 000 s。

仿真关注以下性能参数：

（1）路由开销：路由协议建立路由和维护路由，所有节点发送的路由包。

（2）端到端延时：从源节点的网络层发送数据包，到目的节点网络层收到该数据包的时间平均值。

（3）丢包率：丢失的数据包占所发送数据包的比率。

仿真结果如图5、图6、图7所示。

从图5中可以看到，由于MRABM和本文算法均采用目的节点更新mesh结构的机制,所以在节点移动造成网络拓扑结构改变时，不会存在路由修护和路由重建过程，控制开销将保持平稳,不会急剧增长。然而MRABM的路径建立采用基于目的节点的方法,且定期进行路径更新而不是采用事件驱动，将产生大量的控制开销，本文算法基于源节点建立路径节约了大量的控制开销。

如图6所示，MRABM和本文算法的丢包率都较小，这是因为两种算法都是当一条链路断开后，节点将立即为数据分组选择另一条路径传送数据，几乎不会发生丢包现象，且它们能实时维护源节点到目的节点的最优路径和其余多条路径，所以大流量传输时，这两种算法均能有效平衡网络负载，减少网络拥塞，降低丢包率。而AOMDV采用的固定多径传输则容易造成网络拥塞。

由图7可知，MRABM和本文算法的端到端时延都较小，这是因为当节点移动造成链路断开时，这两种算法都不需要等待路径修复或路由重建过程，而AOMDV在所有路径失效后，将由源节点发起路由重建，所以端到端时延较大。

针对无线mesh网络中目前存在的几种多径路由协议的局限性，提出了一种基于源节点建立和目的节点维护mesh结构的多径路由协议。此协议中,在建立路由时,每个中间节点只需要转发一次路由请求包,以后的路由完善、路由更新和路由维护均由目的节点完成,降低了路由维护的时间。路径的最佳性和跟随拓扑变化的实时性,提高了数据包的传输率,降低了网络的平均延时。另外,基于源节点建立的路径,有效地控制了RREQ在全网的泛洪,减少了控制开销,更合理地利用了网络资源。

本文提出的算法虽在已有算法的基础上有所改进,但仍需要进一步完善和深入。

[1]BADIS H,AGHA K A.QOLSR multi-path routing for mobile Ad Hoc network based on multiple metrics:Bandwidth and delay.Vehicular Techonology Conference,2004. VTC 2004-Spring.2004 IEEE 59th.

[2]刘经纬,雷涛,徐海川,等.Ad-hoc网络多径路由协议的研究与设计.计算机工程与设计,2007，28（17）:4145-4148.

[3]WANG L.Multipath source routing in wireless Ad Hoc networks[A].Canadian Conf Elec Comp Eng.Vol 1[C]. 2000:479-83.

[4]刘丽云,陈曙,朱伟.一种新的基于mesh结构的多径路由算法.计算机工程与应用,2007,43（3）.

A multi-path routing protocal based on wireless mesh networks

XU Ting，LI Shan Jun
（Electrical Engineering and Information College,Sichuan University，Chengdu 610065,China）

A multi-path routing protocol based on the establishment with source nodes and maintenance with destination nodes is proposed in this paper.The protocol refreshes the mesh structure with destination nodes,which provides the best route and other multiple routes.The routing repairment or reconstruction is not required when the links are disconnected by the mobile nodes or any other reasons,so it can reduce the loss package and end-to-end transmission delay.Besides,the control costs are reduced effectively by the way of establishing routes with source nodes.The simulation results show a good performance in this protocol.

WMN；routing algorithm；multi-path

TP393

A

0258-7998（2010）09-0123-04

徐婷，女，1986年生，硕士，主要研究方向：系统检测与网络管理。

李珊君，女，1967年生，副教授，主要研究方向：系统检测与网络管理。