论文部分内容阅读
摘要:无线MESH网络是一种高速度,高容量的多点对多点网络,是一种新型的解决“最后一英里”问题的分布式网络,可把它堪称Ad Hoc网络的简化版本。无线MESH网络中的路由是它的一项关键技术,基于此,本论为对无线MESH网络的路由协议进行了改进研究,文中首先介绍了Ad Hoc网络三种路由协议,重点研究了其中一种动态源路由协议(DSR)的具体实现过程,并在支持QoS服务基础上,对DSR协议进行了改进,并提出了一种新的路由算法MSBR多路径分流带宽算法,该算法可以在源节点和目的节点之间找到多条路径并解决单条路径上不能满足的带宽请求时分配到多条路径上的问题。
关键词:无线MESH;动态源路由协议DSR;QoS;MSBR;
中图分类号:TP301文献标识码:A文章编号:1009-3044(2009)22-pppp-0c
WMN网络节点的移动性使得网络拓扑结构不断变化,传统的基于因特网的路由协议无法适应这些特性,需要有专门的应用于无线Mesh 网络的路由协议。设计无线Mesh路由协议,当前主要有两种做法:一种是根据WMN 与无线Ad Hoc 网特点相似的特征,将Ad Hoc开发的路由协议如DSDV (目的序列距离矢量路由协议)、DSR(动态源路由协议)、TORA(临时按序路由算法) 和AODV(Ad Hoc按需距离矢量路由协议)移植过来用于WMN;另一种是开发无线下专用的路由协议,如PWRP(可预测的无线路由协议)、MR-LQSR(多射频链路质量源路由)等协议。单从性能角度来考察,必须开发适用于无线环境的Mesh 路由协议。然而,从实现的复杂性考虑,改进已有路由协议是最快捷的方式。
我们提到无线Mesh网络的路由协议可以借鉴Ad Hoc网络的路由协议。Ad Hoc 网络路由协议从大的类别上不外乎分为三种:一种为先验式路由协议,也叫表驱动式路由协议;一种为反应式路由协议,也叫源驱动按需路由协议;最后一种就是二者的混合,叫混合式路由协议。无线Mesh网络也可以沿用这三种类型的路由协议。
2 多路径分流带宽路由算法MDBR算法
提供Qos保障服务是无限Mesh和Internet 互联的关键问题。而在无线Mesh网络中,QoS不外乎主要包括3个方面(1)延时。(2)带宽。(3)花费。其中主要指标是前两个。提供多条路径可以在一定程度使得前两个指标得到一定改善。该文着重解决第二个方面。
多路径路由的优点:(1) 加快传输速度,减少时延;(2) 防止断裂,增加稳定度(3) 有利于负载平衡;(4) 减少对带宽的要求。
多路径算法概述:先解释一下非相关路径的概念,所谓非相关路径是指两条路径没有公用链路。我们这里提到的多路径也都指的是非相关路径。基于DSR协议进行改进是因为DSR协议可以在源节点到目的节点之间建立多条非相关路径,并接可支持单向链路。
2.1 当前DSR协议的不足
由上述DRS协议可以看到DSR协议虽然可以找到源节点到目的节点的多条路径,但这些路径不能保证非相关性:以图1.2为例,若节点C已经存在到节点D的路由,分别为C-E-D和C-F-D,这时,源节点S的RREQ分组(目的节点仍为D)到达节点C,按传统的DSR协议,则第一个到达节点C的RREQ消息被回应,其余后到得RREQ消息被摒弃。也就是说S-A-C和S-B-C只能取一条,假设为S-A-C,这样,源节点若有分组要传输,则只有一条路径可选,要么S-A-C-E-D,要么S-A-C-F-D。但两条路径不可同时用,应为这两条路径公用了S-A-C段。实际还是建立了单一的一条路径。如果源节点S要发送数据给目的节点D,带宽请求为x,而这时,若只启用一条路径,每条路径可支持带宽就不能满足带宽请求,这时就要启用两条路径同时工作,这样就可以满足带宽请求。
2.2 改进DSR建立多条路径
MDBR算法可以解决上述问题。在源节点和目的节点之间建立多条路径。对DSR协议改进如下:
传统的DSR协议只有在目的节点处才可以处理多个RREQ消息,即后到得RREQ消息不被丢弃,现在我们使目的节点和存在到目的节点路由的中间节点都可以处理多个RREQ消息,此数目可由我们自己确定。
例如,如图1.2所示,假设节点C已存在到达节点D的路由C-E-D和C-F-D 。当节点S 有数据要发送到节点D时,节点S 首先发送RREQ消息,节点A和节点B收到R R E Q消息后,由于A和B不是目的节点,也不存在到达目的节点的路由,则节点A和B转发R R E Q消息。这样,节点C和E 收到R R E Q消息,节点C存在到达目的节点D的路由,同样,节点E也存在到达目的节点D的路由。可见,C和E都是中间节点,根据改进,节点C 会收到两个R R E Q ,一个从节点A来,一个从节点B来,节点C会对这两个R R E Q消息都给出回应。这样,节点C沿两条路径发送应答消息,一条为C-A-S ,另一条为C-B-S。最后,节点S 得到拓扑图中包含节点S,A,B,C,E,F,D以及链路S-A,A-C,S-,B-C,C-E ,C-F,E-D ,F-D。 显然比原协议得到更完全的拓扑图。 这样,节点有分组要发送时,通过拓扑图就有更多的路径可以选择,比如就有两条非相关路径 S-A-C-E-D和S-B-C-F-D以供选择。
2.3 分流带宽方案
由此我们找到了多条路径,针对带宽不足的状况我们按以下算法解决:当有节点有分组要发送时,先在自己存储的拓扑图中查找到可以到达目的节点的所有路径,以这些路径为基础,需找到可以满足带宽要求的多条路径。源节点发送探测分组,此探测分组含有一定数目的PACKET,每一个包负责寻找一条通路。当探测分组到达一个节点,如果节点不是目的节点,则节点将此探测分组按照一定的策略转发给下一节点,并为这个包在转发链路上保留相应带宽。如果节点没有满足带宽请求的转发链路,则在该节点处将包分为多个SUB-PACKET,,每一个SUB-PACKET负责寻找满足部分带宽请求的路径,这样,在目的节点会收到多个PACKET和SUB-PACKET,如果一个PACKET的全部SUB-PACKET都到达,则目的节点发送给路由应答消息给源节点。具体过程见图1.4源节点到目的节点的带宽请求为5,在路径S-C-D,中,链路S-C和C-D都预留带宽5;在路径S-A-E-D和S-A-F-D中,在节点A处包发生分离,一部分完成带宽请求3的寻路,一部分完成带宽请求2的寻路,并找到相应路径。这样,就找到两条满足带宽请求的通路。
2.4 预约带宽方案
但是这种方法有一个问题,就是因为没有进行资源预约,可能会发现争抢带宽的现象,也即是说应该有一种方法使得链路的剩余带宽信息能很快的反馈到各个节点。
关于各个节点剩余带宽的解决方案:我们为每一个节点建立一张节点状态表;(我们称之为转发表),用于带宽估计,图1.5为带宽估计体系结构,表1所示为转发表结构。
在入口节点处,当有数据包到达时,查看其IP头部的源地址,以确定改数据包从哪个节点进入MESH网络,再查看转发表是否有匹配项(即是否有相应的peerEdge),如果存在匹配项,则将数据包的大小累加到相应项的recvByte中;如果不存在匹配项,则建立新的状态项,并将数据包的大小累加进其recvByte中。如果该数据包被出口节点的队列管理机制丢弃,则该数据包的大小应累加进其相应项的dropByte。recvByte和dropByte分别表示出口节点本地所接受的数据量和本地所丢弃的数据量。发送信息的源节点,在每一固定时间间隔向特定的目的节点发送探测包,链路上每一个节点在接受到探测数据包以后,查看状态表,以(recvByte-dropByte)/(now-lastStatTime)做为该链路上所能使用的带宽估计,并将该带宽估计反馈给源节点。同时将转发状态表中相应状态项的recvByte和dropByte置为0,将lastStatTime置为当前时间。如果在路由查找时,带宽估计够PACKET或SUB-PACKET传递,预留相应带宽,置为1,并启动一定的时间(即生存期)在过生存期后,预留带宽被释放,否则,置为0。
3 结束语
由于时间仓促,将该路由算法性能的仿真并未能完成。由于该路由算法发现多条路径,并且需要计算节点的剩余带宽,可能会出现相对较大的时延,但是该算法对多路径防止断裂,增加稳定度,有利于负载平衡,传递数据时,减少对带宽的要求,都能到很好的改善。总之,由于无线Mesh网络中节点的移动性,以及链路的易受干扰性,使得数据易丢失,采用多条路径可以在一定程度上减少和克服这种缺点,并支持QoS,不失为一种较好的解决办法。
参考文献:
[1] 刘正蓝,朱淼良.基于边界到边界带宽估计的数据包标记器[J].通信学报,2003,8.
[2] 王晓燕.无线Mesh网络路由协议的研究[D].西安电子科及大学,2005.
[3] 樊自甫,万晓榆. 新一代宽带无线网络结构[J].通信世界.2003,9:42-44.
[4] Guangyu Pei and Mario Gerla,Mobility Mangement in Hierarchial Multi-hop Mobile Wireless Net works,IEEE,1999.
关键词:无线MESH;动态源路由协议DSR;QoS;MSBR;
中图分类号:TP301文献标识码:A文章编号:1009-3044(2009)22-pppp-0c
WMN网络节点的移动性使得网络拓扑结构不断变化,传统的基于因特网的路由协议无法适应这些特性,需要有专门的应用于无线Mesh 网络的路由协议。设计无线Mesh路由协议,当前主要有两种做法:一种是根据WMN 与无线Ad Hoc 网特点相似的特征,将Ad Hoc开发的路由协议如DSDV (目的序列距离矢量路由协议)、DSR(动态源路由协议)、TORA(临时按序路由算法) 和AODV(Ad Hoc按需距离矢量路由协议)移植过来用于WMN;另一种是开发无线下专用的路由协议,如PWRP(可预测的无线路由协议)、MR-LQSR(多射频链路质量源路由)等协议。单从性能角度来考察,必须开发适用于无线环境的Mesh 路由协议。然而,从实现的复杂性考虑,改进已有路由协议是最快捷的方式。
我们提到无线Mesh网络的路由协议可以借鉴Ad Hoc网络的路由协议。Ad Hoc 网络路由协议从大的类别上不外乎分为三种:一种为先验式路由协议,也叫表驱动式路由协议;一种为反应式路由协议,也叫源驱动按需路由协议;最后一种就是二者的混合,叫混合式路由协议。无线Mesh网络也可以沿用这三种类型的路由协议。
2 多路径分流带宽路由算法MDBR算法
提供Qos保障服务是无限Mesh和Internet 互联的关键问题。而在无线Mesh网络中,QoS不外乎主要包括3个方面(1)延时。(2)带宽。(3)花费。其中主要指标是前两个。提供多条路径可以在一定程度使得前两个指标得到一定改善。该文着重解决第二个方面。
多路径路由的优点:(1) 加快传输速度,减少时延;(2) 防止断裂,增加稳定度(3) 有利于负载平衡;(4) 减少对带宽的要求。
多路径算法概述:先解释一下非相关路径的概念,所谓非相关路径是指两条路径没有公用链路。我们这里提到的多路径也都指的是非相关路径。基于DSR协议进行改进是因为DSR协议可以在源节点到目的节点之间建立多条非相关路径,并接可支持单向链路。
2.1 当前DSR协议的不足
由上述DRS协议可以看到DSR协议虽然可以找到源节点到目的节点的多条路径,但这些路径不能保证非相关性:以图1.2为例,若节点C已经存在到节点D的路由,分别为C-E-D和C-F-D,这时,源节点S的RREQ分组(目的节点仍为D)到达节点C,按传统的DSR协议,则第一个到达节点C的RREQ消息被回应,其余后到得RREQ消息被摒弃。也就是说S-A-C和S-B-C只能取一条,假设为S-A-C,这样,源节点若有分组要传输,则只有一条路径可选,要么S-A-C-E-D,要么S-A-C-F-D。但两条路径不可同时用,应为这两条路径公用了S-A-C段。实际还是建立了单一的一条路径。如果源节点S要发送数据给目的节点D,带宽请求为x,而这时,若只启用一条路径,每条路径可支持带宽就不能满足带宽请求,这时就要启用两条路径同时工作,这样就可以满足带宽请求。
2.2 改进DSR建立多条路径
MDBR算法可以解决上述问题。在源节点和目的节点之间建立多条路径。对DSR协议改进如下:
传统的DSR协议只有在目的节点处才可以处理多个RREQ消息,即后到得RREQ消息不被丢弃,现在我们使目的节点和存在到目的节点路由的中间节点都可以处理多个RREQ消息,此数目可由我们自己确定。
例如,如图1.2所示,假设节点C已存在到达节点D的路由C-E-D和C-F-D 。当节点S 有数据要发送到节点D时,节点S 首先发送RREQ消息,节点A和节点B收到R R E Q消息后,由于A和B不是目的节点,也不存在到达目的节点的路由,则节点A和B转发R R E Q消息。这样,节点C和E 收到R R E Q消息,节点C存在到达目的节点D的路由,同样,节点E也存在到达目的节点D的路由。可见,C和E都是中间节点,根据改进,节点C 会收到两个R R E Q ,一个从节点A来,一个从节点B来,节点C会对这两个R R E Q消息都给出回应。这样,节点C沿两条路径发送应答消息,一条为C-A-S ,另一条为C-B-S。最后,节点S 得到拓扑图中包含节点S,A,B,C,E,F,D以及链路S-A,A-C,S-,B-C,C-E ,C-F,E-D ,F-D。 显然比原协议得到更完全的拓扑图。 这样,节点有分组要发送时,通过拓扑图就有更多的路径可以选择,比如就有两条非相关路径 S-A-C-E-D和S-B-C-F-D以供选择。
2.3 分流带宽方案
由此我们找到了多条路径,针对带宽不足的状况我们按以下算法解决:当有节点有分组要发送时,先在自己存储的拓扑图中查找到可以到达目的节点的所有路径,以这些路径为基础,需找到可以满足带宽要求的多条路径。源节点发送探测分组,此探测分组含有一定数目的PACKET,每一个包负责寻找一条通路。当探测分组到达一个节点,如果节点不是目的节点,则节点将此探测分组按照一定的策略转发给下一节点,并为这个包在转发链路上保留相应带宽。如果节点没有满足带宽请求的转发链路,则在该节点处将包分为多个SUB-PACKET,,每一个SUB-PACKET负责寻找满足部分带宽请求的路径,这样,在目的节点会收到多个PACKET和SUB-PACKET,如果一个PACKET的全部SUB-PACKET都到达,则目的节点发送给路由应答消息给源节点。具体过程见图1.4源节点到目的节点的带宽请求为5,在路径S-C-D,中,链路S-C和C-D都预留带宽5;在路径S-A-E-D和S-A-F-D中,在节点A处包发生分离,一部分完成带宽请求3的寻路,一部分完成带宽请求2的寻路,并找到相应路径。这样,就找到两条满足带宽请求的通路。
2.4 预约带宽方案
但是这种方法有一个问题,就是因为没有进行资源预约,可能会发现争抢带宽的现象,也即是说应该有一种方法使得链路的剩余带宽信息能很快的反馈到各个节点。
关于各个节点剩余带宽的解决方案:我们为每一个节点建立一张节点状态表;(我们称之为转发表),用于带宽估计,图1.5为带宽估计体系结构,表1所示为转发表结构。
在入口节点处,当有数据包到达时,查看其IP头部的源地址,以确定改数据包从哪个节点进入MESH网络,再查看转发表是否有匹配项(即是否有相应的peerEdge),如果存在匹配项,则将数据包的大小累加到相应项的recvByte中;如果不存在匹配项,则建立新的状态项,并将数据包的大小累加进其recvByte中。如果该数据包被出口节点的队列管理机制丢弃,则该数据包的大小应累加进其相应项的dropByte。recvByte和dropByte分别表示出口节点本地所接受的数据量和本地所丢弃的数据量。发送信息的源节点,在每一固定时间间隔向特定的目的节点发送探测包,链路上每一个节点在接受到探测数据包以后,查看状态表,以(recvByte-dropByte)/(now-lastStatTime)做为该链路上所能使用的带宽估计,并将该带宽估计反馈给源节点。同时将转发状态表中相应状态项的recvByte和dropByte置为0,将lastStatTime置为当前时间。如果在路由查找时,带宽估计够PACKET或SUB-PACKET传递,预留相应带宽,置为1,并启动一定的时间(即生存期)在过生存期后,预留带宽被释放,否则,置为0。
3 结束语
由于时间仓促,将该路由算法性能的仿真并未能完成。由于该路由算法发现多条路径,并且需要计算节点的剩余带宽,可能会出现相对较大的时延,但是该算法对多路径防止断裂,增加稳定度,有利于负载平衡,传递数据时,减少对带宽的要求,都能到很好的改善。总之,由于无线Mesh网络中节点的移动性,以及链路的易受干扰性,使得数据易丢失,采用多条路径可以在一定程度上减少和克服这种缺点,并支持QoS,不失为一种较好的解决办法。
参考文献:
[1] 刘正蓝,朱淼良.基于边界到边界带宽估计的数据包标记器[J].通信学报,2003,8.
[2] 王晓燕.无线Mesh网络路由协议的研究[D].西安电子科及大学,2005.
[3] 樊自甫,万晓榆. 新一代宽带无线网络结构[J].通信世界.2003,9:42-44.
[4] Guangyu Pei and Mario Gerla,Mobility Mangement in Hierarchial Multi-hop Mobile Wireless Net works,IEEE,1999.