一种基于跨层的无线Mesh网络路由协议

　　摘 要:无线Mesh网络的很多技术特点和优势来自于Mesh多跳路由。因此,路由协议的研究与设计是无线Mesh网络技术的一个重要课题。由于无线Mesh网络有自身负载均衡、路由容错与网络容量等要求,因此运用跨层设计,采用更好的路由参数,使用多径路由等方法已经成为无线Mesh网络路由协议设计的重要思路。根据无线Mesh的网络特点,按照其路由协议的设计要求,分析了路由协议DSR在Mesh网络中的不足,引入跨层设计的方法,提出了采用路由质量路径帧投递率(PFDR)为路由准则,并具有负载平衡、拥塞避免的路由协议CMRP。分析和仿真结果表明,CMRP在保持Mesh网络自身优点的同时,比起DSR在网络性能上有了较大的提升,在吞吐率方面有了很大的提高,相应的时延、抖动参数均有了大幅的下降,更加适用于无线Mesh网络。
　　关键词:路由协议;无线Mesh网络(WMN);跨层设计;链路帧投递率(LFDR)
　　中图分类号:TN915.02文献标识码:A
　　文章编号:1004-373X(2009)19-027-03
　　
　　Routing Protocol of Wireless Mesh Network Based on Cross-layer
　　SHAO Yan,SU Jie,XIAO Mingbo
　　(Xiamen University,Xiamen,361005,China)
　　Abstract:Wireless Mesh Network (WMN) is a technology with outstanding technical characteristics and advantages,many of which originate from the muti-hop routing.Therefore,the study and design of routing protocol is of utmost importance for WMN.In order to satisfy the requirements of WMN such as load balancing,fault tolerance,network capacity,techniques such as cross-layer design and multi-path routing may have to be considered in protocol design for WMN.The deficiencies of Dynamic Source Routing(DSR) protocol applied in WMN is analysed,and an improved routing protocol Cross-layer Multi-path Routing Protocol(CMRP) is proposed,using PFDR (Path Frame Deliver Rate) as the measure.Analysis and simulation results show that CMRP greatly improved the network performance,in load balancing,congestion avoidance,link failure sensing mechanism and the capability of multi-path routing.
　　Keywords:routing protocol;wireless Mesh network;cross-layer design;link frame deliver rate
　　
　　0 引 言
　　无线Mesh网络(WMN)是在移动自组织网络(MANET)和无线局域网(WLAN)基础上发展起来的一项网络技术,它作为下一代因特网核心网的无线版本,有效地解决“最后一公里”瓶颈问题[1],是一种具有动态自组织、自配置、高速率、高容量等特性的分布式宽带无线网络。
　　当前,WMN的MAC协议大多采用IEEE 802.11,使用这种MAC协议的Mesh网络也称为Wi-Mesh。跨层设计的主要思想在网络各层共享相关的信息,对无线网络进行整体设计,因此所有层间可以交互信息,使得协议栈能够以全局的方式适应特定应用所需的QoS 和网络状况的变化,并根据系统的约束条件和网络特征来进行综合优化,实现对网络资源的有效分配,提高网络的综合性能[2]。跨层路由[3]便是将跨层的设计思想引入路由的设计中,进而提高网络性能。WMN的很多技术特点和优势来自于Mesh多跳路由[4],该文的目的就是在尽量保持网络分层结构的基础上,运用跨层的方法设计出一个适用于Wi-Mesh(后文中直接统称WMN)的高性能路由协议。
　　动态源路由(DSR)是一种以最小跳数为度量,基于源路由机制,采用按需路由策略的路由协议,它允许节点从多跳无线网络中动态地发现一条通向任何目的节点且跳数最少的路由。DSR的路由发现与维护按需进行,不需周期性传递控制包,可节省大量带宽,但DSR在路由选择时采用的最小跳数度量准则,可能导致每一跳传输距离过大,从而导致接收端信号减弱,给网络带来不必要的重传,而且DSR没有充分利用所获得的多径路由,也没考虑负载平衡来提高网络性能。这里对DSR进行适当的改进,希望既保持DSR的优点,又避免上述缺陷。
　　1 改进的路由协议CMRP
　　1.1 新路由准则:路径帧投递率(PFDR)
　　用来表征链路质量的参数有多种,如 mETX[5],ENT [5]等,这些链路质量参数都可从网络层直接获得,文献[6]分析了上述参数的优劣。网络层的链路质量参数主要都是基于一个最基本的链路性能:链路包投递率(Link Packet Deliver Rate,LPDR)。LPDR表征了数据包经过某条链路时,在网络层可成功传送的概率。但仅限于网络层不足以精确衡量某一链路的质量,而在MAC层则可相对客观地反映链路的质量。对于无线网络,当信号差、误码率较高,接收的数据帧多次校验错误,使多次重传失败时的丢包能较好地反映链路质量。此时链路质量与节点位置、距离、发射功率、调制技术等有关,路由协议根据此情况下获得的参数,可得到较优的路由。文中采用跨层交互的方法,在MAC层计算出与LPDR类似的参数:链路帧投递率(Link Frame Deliver Rate,LFDR),作为度量链路质量和选路的参数。
　　一般来说,LFDR是由链路的前向节点计算的,在按需式路由的路由请求中,上游节点要将全部已知下游节点的地址与相应的链路质量都加入请求信息包中,这大大增加了请求信息包长度,且使其长度变得很不稳定。CMRP采用后向计算的方法获得LFDR,整条路由的PFDR就是路由中每段链路LFDR的连乘[7]。
　　对于链路中的两个节点,当下游节点接收到上游节点发给它的RTS时,说明上游节点成功获得预定信道,将有数据帧发送给此下游节点。下游节点用计数器Ttran记录接收到的此类RTS的次数。Ttran表示下游节点感知到的上游节点传送给它的数据帧的发送次数。
　　每当下游节点成功接收到上游节点发送的数据帧并校验无错时,表明上游节点成功将数据帧发送给此下游节点。下游节点使用一个计数器Trec记录接收到的此类帧次数。Trec表明下游节点成功接收来自上游节点的数据帧次数。
　　
　　因此,链路的后向帧传递率计算公式为:
　　LFDR=(Trec/Ttran)×100%
　　(1)
　　式(1)中的LFDR就是链路帧传递率。
　　(1) 路径帧传递率(Path Frame Deliver Rate,PFDR)
　　LFDR只能反映某条链路情况,而由概率知识可知,整条路由的PFDR与路由中的每段链路LFDR的关系是:
　　PFDR=∏n-1i=1LFDRi,i+1
　　(2)
　　式中:n表示此路径的节点总各数;i表示此路径从源节点起算的第i个中间节点,i=1表示源节点,i=n 表示目的节点;LFDRi,i+1则表示第i个节点到第i+1个节间的链路帧传递率。
　　(2) PFDR参数与CMRP的结合
　　CMRP主要选路原则:最优的PFDR。
　　LFDR的获取:在CMRP中,每个节点都维护着其他节点到本节点的LFDR信息。LFDR是按需更新的,当需要(收到RREQ)时,节点提取从MAC计算出来的LFDR,存放到自身状态变量中。
　　PFDR的获取:在CMRP的路由发现过程中,中间节点收到RREQ后,在做任何处理前,先将本节点LFDR值与RREQ中的PFDR值相乘,用相乘结果更新RREQ的路由质量值。
　　PFDR的使用1:在CMRP的路由发现过程中,目的节点会收到多条从源节点发来经过不同路径的同一类RREQ,通过这些RREQ中的路由质量信息,CMRP可以选择优质路由。
　　PFDR的使用2:在CMRP的源路由数据包传输过程中,通过路由质量信息,可以基于路由质量的变化情况对路由进行主动维护。
　　PFDR的使用3:在CMRP的源路由数据包传输过程中,若存在非相关多径路由,源节点可以通过路由质量信息分配流量给这些路径。
　　1.2 拥塞避免
　　WMN的数据业务具有很大的随机性与突发性,使得网络中容易出现某些节点的负载突然加重,局部发生拥塞。队列长度是拥塞的主要标志, MAC层的剩余带宽、延迟等参数也主要由队列长度决定。再加上队列的长度相对于其他MAC层参数变化慢,能较稳定地反映网络拥塞程度,许多文献都以节点队列长度所定义的节点负载度来衡量拥塞的程度[8]。因此,该文选用MAC层接口队列来度量节点负载。
　　节点负载度与拥塞系数:
　　当MAC层输出队列的长度到达一定程度(拥塞门限)时,记为Qth b,网络出现拥塞。定义此时MAC层输出队列的长度Qth与最大长度Qmax b的比值为拥塞系数ρ:
　　ρ=Qth/Qmax, ρ≤1
　　(3)
　　将MAC输出队列当前长度Q b与最大长度Qmax的比值,定义为节点负载度Ld:
　　Ld=Q/Qmax
　　(4)
　　这样,当队列当前长度Ld<ρ时,网络未出现拥塞;当Ld≥ρ时,网络出现拥塞。
　　通过建模和分析可以得出拥塞系数ρ的参考值,它可用仿真时的指导。根据文献[9],可以取ρ=Smax,其中Smax为MAC层的最大归一化吞吐率。另外,在CMRP中还通过引入预警门限Pre(Pre值略小于ρ),增加了预测拥塞的能力。
　　1.3 CMRP的其他性能改进
　　在CMRP中除了提出新的路由准则PFDR和拥塞避免参数Ld之外,还在非相关多径路由、断链判定和主动路由方面进行了考虑,进一步提高网络的性能。中间节点通过对RREQ的转发次数进行限制,使目的节点可以根据PFDR选择最优非相关路由进行回复。在CMRP中,根据下游节点是否可以收到上游节点的RTS情况来判断是否断链,并且在断链的上游节点处进行维护。除此之外,CMRP还改进了侦听路由缓存机制,CMRP将按需路由与主动路由相结合,适用于节点变化小而业务要求高的WMN中。
　　2 网络仿真与分析
　　本文使用QualNet网络仿真工具[10],对改进的CMRP与原DSR进行路由协议的性能进行仿真比较,以证实改进思路的正确性与改进结果的有效性。仿真中采用的性能参数分别是网络平均吞吐率、网络平均时延、网络平均抖动。
　　WMN是准静态网络,仿真场景中节点全部设置静态,如图1所示,场景中节点分布呈8×8的正方形网格结构,节点间距为180 m,仿真中比较的是DSR与CMRP的性能,仿真时间设定为200 s。
　　图1 随机业务模型场景
　　为了更加真实地模拟因特网数据业务流的情况,突出业务流的随机特性与突发特性,采用Quanet中的应用层协议Traffic Gen来产生具有某种分布特性的随机业务流。根据研究,以Pareto分布,ON/OFF模型生成业务流的叠加符合因特网业务流的特性[11] 。
　　随机选取16条Traffic Gen业务流,ON期间比例分别为20%,40%,60%,80%,100%,也就是Traffic Gen业务流的发送概率从0.2增加到1.0,相应业务流的突发性就越来越低了。第二组随机选取16条Traffic Gen业务流,其余设置同于第一组。Traffic Gen的ON期间长度分布由均一分布改为Pareto分布。仿真结果如图2~图4所示。
　　图2 平均吞吐率-发包率的性能曲线
　　图3 平均时延-发包率的性能曲线
　　图4 平均抖动-发包率的性能曲线
　　从图2~图4可以看出,对于重负载下16条随机业务流的情况,DSR与CMRP的差距非常明显,CMRP的性能优越更加体现出来。CMRP在保持性能平稳的同时,平均吞吐量约为DSR的三倍,而平均时延及平均抖动都在DSR的40%以下。
　　仿真结论如下:
　　为了真实地模拟因特网数据业务流量特性,设置了16条随机连接的ON/OFF业务流场景中,比较平均吞吐率、平均时延、平均抖动三个网络性能参数可以看到,CMRP的性能比起DSR有了极大的提高,能够适应网络中业务流的随机特性与突发特性。
　　3 结 语
　　根据WMN的节点准静态特性,基于DSR设计了一种跨层多径路由协议CMRP,在其中添加主动路由的思想,增加了链路质量判决、拥塞避免及多径路由、路由断链判定等机制。仿真结果表明,比起原来的DSR,CMRP在平均吞吐率、平均时延、平均抖动等网络性能上都有较大的提高,达到了预期的目标,可以更好地适用于WMN。
　　
　　参考文献
　　[1]方旭明.下一代无线因特网技术:无线Mesh网络[M].北京:人民邮电出版社,2005.
　　[2]罗明胜,黄联芬,姚彦.无线网络跨层设计的研究现状及展望 [J].移动通信,2005,29(7):95-98.
　　[3]方旭明,马忠建.无线Mesh网络的跨层设计理论与关键技术[J].西南交通大学学报,2005(12):711-719.
　　[4]Bruno R,Conti M,Gregori E.Mesh Networks:Commodity Multihop Ad Hoc Networks [J].IEEE Communications Magazine,2005,43(3):123 -131.
　　[5]Koksal C E,Balakrishnan H.Quality Aware Routing Me-trics for Time-varying Wireless Mesh Networks[J].IEEE Journal on Selected Areas in Communications,2006:1 984-1 994.
　　[6]Ekram Hossain,Kin K Leung.Wireless Mesh Networks:Architectures and Protocols[M].Springer,2007.
　　[7] 沈强,方旭明.无线Mesh网中一种基于综合准则的DSR扩展路由方法[J].电子学报,2007,35(4):614-620.
　　[8]郭嘉丰,张信明,谢飞,等.基于节点空闲度的自适应移动Ad Hoc网络路由协议[J].软件学报,2005,16(5):960-969.
　　[9]于明刚.论无线网状网路由分组接收率的提高与网络性能的改进[D].长春:吉林大学,2007.
　　[10]Scalable Network Technologies[EB/OL].http:/www.QualNet.com,2005.
　　[11]Hans-Peter Schwefel,Lester Lipsky.Impact of Aggregated,Self-Similar ON/OFF traffic on Delay in Stationary Queueing Models (Ext.Version)[A].Performance Evaluation[OL].2000.