可靠多路径路由（精选7篇）
可靠多路径路由 篇1
1 引言
Ad hoc网络是一种具有高度动态拓扑结构,不需要固定基站支持的多跳无线网络,整个网络没有固定的基础设施,也没有固定的路由器,所有节点都是移动的、动态变化的,并且都可以以任何方式动态地保持与其他节点的联系。由于Ad hoc具有分布式、动态性、自治性、易构性和移动性,使得无线移动Ad hoc网络可以广泛应用于军事领域、自然灾害应急处理、科学考察、探险、交互式演讲、共享信息的商业会议、紧急通信等领域。在这种环境中,每一个节点都具有终端和路由的功能,它们要完成发现和维护到其他节点路由的功能,因此,路由就成为Ad hoc网络中进行数据通信的核心问题[1~5]。
多路径路由的目标是在源节点到目的节点之间建立多条路径,多条路径的形成既可以在源节点上,也可以在中间节点上。在多路径路由中,数据分组通过多条路径分流传输到目的节点。多路径路由的特点:可以为不同的服务质量要求提供不同的路径;可以为同一种类型的服务提供多条路径,经聚集可实现更高的服务质量。在数据分组传输的过程中,通过多路径选择还可以平衡网络负载。图1显示了节点不相交路径和链路不相交路径的多路径。
2典型可靠多路径路由协议
可靠多路径路由协议的目的主要是从源节点到目的节点之间提供可靠通信。这些典型的多路径路由协议有:基于邻居表多路径路由协议(NTBMR)、节点不相交多路径路由协议(NDMR)、冗余源路由(RSR)以及N-1多路径路由协议。
2.1 基于邻居表多路径路由协议
Yao等[6]提出了基于邻居表多路径路由协议(Neighbor-Table-Based Multipath Routing,NTBMR)。NTBMR不需要不相交多路径,它保持网络拓扑的动态变化,路由发现和路由维护机制使用无线链路连接的均值与生存期建立一个邻居表,邻居表中包括:时间驱动机制和数据驱动机制。在时间驱动机制下,当一个节点接收特定路线的请求消息,它设为活动路由,并已通过的请求邻居表中添加的所有节点。时间驱动机制的主要缺点是网络拓扑变化与检测此变化的时间较长。在数据驱动机制中,当一个节点检测到一个邻居不可访问时,它向所有邻居发送此消息,告诉此节点无法使用。NTBMR使用下列模型提供可靠多路径。,M和V分别表示无线链路连接的均值与生存期,Mcurrent和Vcurrent分别表示当前链路状态,。NTBMR的不足之处是产生额外的控制信息。,0<琢,茁<1
2.2 节点不相交多路径路由协议
Li等[7]提出了节点不相交多路径路由(Node-Disjoint Multipath Routing,NDMR)协议,该协议是在AODV[5]协议的基础上增加控制分组来发现多个节点不相交路径。在节点不相交路径中,没有公共节点,在链路不相交路径中,没有公共链路。在NDMR中,多路径选择不一定是最好路径,但要是最稳路径并提供了最稳路径的选择机制。
2.3 冗余源路由
Wang等[8]提出了冗余源路由(Redundant Source Routing,RSR)协议,该协议是基于分散路由方案。在分散路由方案中,分组是分区并通过不同的路径发送。RSR的关键是如果一个路径发生故障,仍有其他通向目的节点的路径发送数据。分散路由可大致分为两种主要类型:非冗余路由和冗余路由。在非冗余路由中,一个分组被分成子分组和这些子分组是通过不同的路径传送。在冗余路由中,分组也被分为子分组,但子分组的数目少于发现路径路由协议使用的数量。其路径选择分为主要路径和次要路径,在这两个路径中使用两个标识分组。RSR协议具有较低的分组丢失率和较好的时延顽健性。
2.4 N-1多路径路由协议
Lou等[9]提出了有效的N-1多路径路由协议(N-to-1 Multipath Routing Protocol),该协议设计了在传感器网络中的多路径路由,并与MANET中多径路由协议有所不同。N-1多路径路由协议的主要内容是发现从一个传感器节点到一个基站的多路径路由。若要设置多个路径从传感器到目标节点,路由发现机制与洪泛机制分两个阶段的进行操作。第一阶段被称为洪泛机制,这是一个简单的洪泛机制;在这一阶段,建立一条从传感器到基站的节点不相交路径。在下一阶段使用一种称为多路径的扩展洪泛技术;在这一阶段,一个传感器网络交换在第一阶段发现的节点不相交路径信息。
3 性能比较
可靠多路径路由协议可以较好利用网络拓扑信息,减少路由发现次数,从而减少路由开销。选择一个合适的可靠多路径路由协议是非常重要的,一般基于以下几个原因:(1)网络模型的大小;(2)网络的寿命;(3)网络的环境;(4)网络应用的类型。表1给出了基于邻居表多路径路由协议(NTBMR)、节点不相交多路径路由协议(NDMR)、冗余源路由(RSR)以及N-1多路径路由协议4种Ad hoc网络多路径路由协议的性能比较
4 结论和未来工作
在移动Ad hoc网络中,由于结点的移动性、网络拓扑结构的易变性以及网络资源和处理能力的有限性,路由成为研究的热点和难点。文本概述了Ad hoc网络可靠多路径路由存在的问题,论述了基于邻居表多路径路由协议(NTBMR)、节点不相交多路径路由协议(NDMR)、冗余源路由(RSR)以及N-1多路径路由协议4种Ad hoc网络多路径路由协议4种协议的优缺点,比较分析了4种Ad hoc网络可靠多路径路由协议的性能。
总之,在未来的Ad hoc网络多路径路由的研究中,我们将结合Ad hoc网络Qo S约束多路径路由、节能多路径路由、可信多路径路由等问题进行深入研究,以提高Ad hoc网络利用率。
参考文献
[1]Mueller S,Tsang R P,Ghosal D.Multipath routing in mobile ad hoc networks:issues and challenges.Lecture Notes in Computer Science,Vol.2965,Springer-Verlag Berlin Heidelberg,2004:209～234
[2]Tarique M,Tepe K.E,Adibi S,Erfani S.Survey of multipath routing protocols for mobile ad hoc networks.Journal of Network and Computer Applications.2009,32(6):1125～1143
[3]Perkins C E,Belding-Royerand E M,Chakeres I D.ad hoc On-Demand Distance Vector(AODV)Routing.IETF Internet Draf(tJuly2004),http://www.ietf.org/internet-drafts/draft-ietf-manet-aodv-13.txt
[4]Yao Z,Jiang J,Fan P,Cao Z,Li Vok.A neighbor table based multipath routing in ad hoc networks.57th IEEE Semiannual Vehicular Tech-nology Conference,Vol.3,April2003,1739～43
[5]Li X,Cuthbert L.Stable node-disjoint multipath routing with low overhead in mobile ad hoc networks.Proceedings of the IEEE Computer Society's12th Annual International Symposium on Modeling,Analysis,and Simulation of Computer and Telecommunications Systems(MASCOTS2004),2004:184～91
[6]Wang L,Jang S,Lee T Y.Redundant source routing for real-time services in ad hoc networks.Proceedings of IEEE International Conference on Mobile Ad hoc and Sensor Systems Conference,Washington,DC,November,2005
[7]Lou W.An efficient N-to-1multipath routing protocol in wireless sensor networks.Proceedings of the IEEE International Conference on Mobile Ad hoc and Sensor Systems Conference,Washington,DC,November2005
独立多路径负载均衡路由协议研究 篇2
1 简化的QoS路由模型
可用一个无向图G (V,E)来描述无线网络的拓扑结构,网络的链路用图的边来表示,网络的节点用图的顶点来表示。网络中所有链路的集合用E来表示,E={In,m(n,m):n,m∈V};网络中所有节点的集合用V来表示,V={ni}。用一组边{ls,1,l1,2,l2,3,…,ln,d}来表示无线Mesh网络中任意两个节点ns,nd之间的连接关系,这组边的集合为就被称为一条路由r:rs,d={ls,1,l1,2,l2,3…,ln,d}。同时也可以用节点的集合表示路由r:rs,d{nj,j=s,u,v,…d}。用Ru·v表示网络中任意两个节点u,v之间的全部路由r组成的一个集合。
设Ti为时延,Bi为节点ni的带宽,于是可得到在路由rs,d={nj,j=s,u,v,…d}上的时延T(s,d)和带宽B(s,d)的定义:
定义1:路由rs,d的时延T(s,d):在路由中所有节点进行累计的时延。单位:秒。
定义2:路由rs,d的带宽B(s,d):路由中每个节点的最小带宽值。单位:比特/秒。
在无线Mesh网络中,当需要在s,d之间对多媒体数据流D进行传送时,则必须要使D对以下QoS性能要求得到满足:T表示时延,B表示带宽,D表示丢包率。因此NBLMP路由协议要找到节点s,d之间的路由集合Rs,d,就必须需满足下面条件中的任何一个:
条件1:找到n条路由∈Rs,d满足:
(Dl(s,d)+…+Dn(s,d))
条件2:至少发现一条路由rd,s∈Rs,d满足:
B(s,d)≥B;
T(s,d)≤T;
D(s,d)≤D。
在以上的数学模型中对丢包、带宽及时延等性能参数进行了衡量。丢包率属于可乘性参数,而时延属于可加性参数,所以对多个性能参数的限定将会造成运算量的增加,而希望能得到的是一个简化的QoS模型。
通过上面的详细分析,简化的服务质量QoS模型为:第一标准为带宽,附加标准为对时延的限制,找到可适用的路径。如果可适用的路径有很多条,那么就对最短的路径进行选择。如果单条路径满足不了要求,就得用独立多路径进行数据的传送。最大限度地充分利用网络带宽的资源,使网络的吞吐量得到保证。要实现以上简化的QoS模型,NBLMP路由协议就必须满足以下条件:
条件1:路由算法要采用分布式的方式。
条件2:要能充分保证路由对时延要求的满足,并且要能对时延有效地进行估算。
条件3:新的路由协议中要能够对无线信道中节点的可用带宽进行有效的测量,接入数据流是以网络中的可用带宽资源控制,同时节点要对数据流的时延及带宽的要求有所保证。
条件4:新路由协议要能对路由失效的情况进行妥善的修复处理。
条件5:在网络中没有任何一条路径能够使数据流需求得到满足的情况下,新路由协议必须要充分衡量目前网络的状态,通过对节点不相交独立多路径进行选用以数据的传送,从而使网络带宽资源的利用率得到提高。
2 可用带宽的计算
在NBLMP路由协议中路由的可用带宽的计算是一个关键性的问题。本文采是利用对共享信道的占用率的检测来对可用带宽进行预测。节点的可用带宽是通过此节点所在信道的闲置时间表现出来的。
在IEEE802.11标准中具有能够判断信道占用状态变化的载波监听机理,可通过中断的方式将得到的信息告知网络层,以此来对可用带宽进行预测。通过对退避机制以及MAC帧所产生的开销进行衡量,同时信道的占用率与信道的剩余带宽近似成正比,需要对比例系数进行修改。可用带宽近似表达式为:
k表示修正系数:
其中,信道的空闲时间用T_idel来表示,信道总的采样周期时间用T_total来表示,MAC层的链路带宽速率用B_basic来表示。此节点可用带宽的计算方式对路由协议的开销能够大大减小。
3 路由的发现过程
在NBLMP路由协议中,由源节点负责发起路由。当上层的协议将数据流请求发送到源节点的时候,要先对本地的路由缓存表进行一次查找,看是否存在满足条件的路由,如果存在就用此路由将数据分组进行发送,否则就将路由发现过程发起,向附近节点泛洪一个中路由请求分组NRREQ。图1为中间节点对路由请求分组的处理过程的流程图。当网络中的中间节点收到一个路由请求分组NRREQ时,第一步先判断此NRREQ是否是第一次收到,如果不是第一次收到,就采用上面提到的路径选择策略对此NRREQ分组进行丢弃操作。如果是第一次收到,就要对此路由请求分组NRREQ继续进行判断。判断此NRREQ分组能不能满足数据流的时延限制,如果满足不了时延的限制就要对此NRREQ分组进行丢弃操作,如果能够满足就利用节点的可用带宽对路由请求分组中的瓶颈带宽进行替换。接着在路由请求分组中添加此节点的ID,并将此NRREQ分组继续转发出去。
4 路由的维护过程
在路由的维护方面,由于在路由发现过程中NBLMP路由协议构建的网络拓扑结构很特殊,所以对路由的恢复就通过路由分组中的备用路径来进行维护。路由的维护步骤如下:
(1)当某条路径出现问题而断开时,就会由断开的节点沿着路由路径的相反方向传送一个路由错误分组NRRER;
(2)当一个NRRER分组到达某个交叉节点时,因为此交叉节点的后继路径也具有不相关性,所以能够最快速地进行路由恢复;
(3)交叉节点要在路由表中查寻是否存在相匹配的备用路径;
(4)如果有备用路径,就将数据切换到备用路径上。如果没有备用路径就沿着路由路径的相反方向继续发送NRRER分组,然后返回Step3继续进行查寻。当NRRER分组已经抵达源节点时,就需要重新发起路由的发现过程,说明在此路径分组中不存在相匹配的备用路径;
(5)当某一个节点的可用带宽有限不能对数据分组进行发送时,源节点就会收到通知并在路由的缓存区内查找是否有通向目的节点的其他路径,如果有就直接用新路径对数据分组进行发送,否则将持续使用原路径进行发送;
(6)当节点的发送时间超过了时限,此节点就会发送一个路由错误分组NRRER到源节点,并且接着发送数据分组。
这样的维护方法可以使路由发现过程的重新发起率最大限度的降低,同时也能使网络的开销减少,使处于激活状态的数据流得到更好的保护,防止丢包的发生。
5 评价性能参数
在此次仿真实验的过程中,选择了路由协议的开销率、数据分组的丢包率以及端到端的平均时延作为性能评价的参数。
5.1 路由协议的开销率
其中控制包包括路由协议控制包和数据包。路由协议所产生的数据包如RREQ,RREP,RRER等就是控制包。此性能参数是对网络的拥塞情况和对网络协议的效率进行评估。
5.2 数据分组的丢包率
此值越小显示出成功发送到目的节点的数据分组越多,协议的性能也就越好。此性能参数是对整个网络的吞吐量以及网络中数据成功发送的效率进行评估。
5.3 端到端的平均时延
此性能参数是对网络的拥塞状况及效率进行评估。
在对路由协议的设计中,应该力求对路由的开销以及端到端的平均时延的减少,还有对数据分组的丢包率的降低。
6 仿真结果及分析
仿真环境参数设置:仿真场景大小为1000m×1000m的矩形范围内,节点数量为50个,模拟时间为1000s,数据源类型为CBR,节点移动速度为10m/s,数据分组大小为512Kb,信道的带宽为1Mbps,节点传输范围在250m。
在仿真实验过程中,业务类型为固定码率,每个数据包长度为512B,数据包的时间间隔为0.15s。
在路由开销率方面,如图2所示,可表现出NBLMP协议与DSR协议的路由开销率和网络负载之间的关系。由于DSR协议是作为NBLMP协议设计的一个基础,对DSR协议进行优化改进。所以这两种协议的路由开销率在网络负载比较低的情况下,是没有太大差异的。但是随着网络的负载不断增加,DSR路由协议就要比较频繁的重新发起路由很大程度上增加了路由控制包的数量,致使路由开销不断增大。而NBLMP路由协议在路由开销方面就有较好的表现。
在数据分组丢包率方面,由于不断增大的网络负载使NBLMP协议和DSR协议的数据分组丢包率均有变大的趋势,但是其中DSR协议的传输方式是选择最短的单路径进行数据传送,所以不能使服务质量QoS带宽的要求得到满足,从而导致数据分组的丢包率迅速上升,造成网络拥塞情况的出现。而对于NBLMP协议来说,随着网络的负载不断增大单路径服务质量QoS带宽的要求无法满足时,就会将网络的负载平均分配到多条独立路径上,通过多条节点不相交的独立多路径同时进行数据传送,从而使各条路径上的服务质量QoS要求有所降低,更好地保证了分组数据传输的有效性,同时也将数据分组的丢包率降到更低。
从端到端的平均时延性能上比较,NBLMP协议也有较好的表现。随着网络中负载的不断增加网络中的资源也越来越少,拥塞率随之增大,致使数据传输端到端的平均时延也在增大。DSR协议在网络中固定码率数据流比较少的情况下,是通过选择最短路径对数据包进行传送,与NBLMP协议相比端到端的平均时延要低一些。但是在网络中固定码率数据流的数量不断增多的情况下,NBLMP协议是通过选择节点不相交的独立多路径来同时进行数据传送,而DSR协议重新发起路由的频率要大大增加。所以NBLMP协议在数据传送端到端的平均时延方面与DSR协议相比较要有明显优势。
摘要：近年来,我国IT技术突飞猛劲的发展,无线Mesh网络(英文名称:Wireles Mesh Network,简称为WMN)也已随之迅猛地发展起来。无线Mesh网络是一种无线多跳网络,是用无线链路把终端设备与路由器连接起来,它也是一种具有高速率、高容量的多点对多点的分布式网络。针对无线Mesh网络路由协议进行研究,因为对于无Mesh网络性能的优化来说,无线路由协议的研究是一项十分重要的内容。
可靠多路径路由 篇3
无线Ad hoc网络的前身是分组无线网 (Paeket Radio Network) 。它是由一些相对独立的节点通过自我组织而形成的一种特殊新型无线网络, 其中, 节点既能充当信息接受或者发送终端, 又具备充当数据包转发的路由器的功能。
2 AODV协议
在AODV算法中, 如果源节点没有到目的节点的路径, 那么源节点将通过洪泛路由请求 (RREQ) 发起一个路由发现, 在RREQ分组的传输过程中, 中间节点只在第一次收到该分组时进行处理, 建立了一条反向路径, 反向路径条目至少要保存到RREQ分组穿越网络并且RREP反馈到源节点。如果稍后又收到相同的折RREQ分组, 则丢弃。一旦RREQ分组到达目的节点或存有到目的节点有效路由的中间节点时, 节点就回复一个路由应答 (RREP) 分组。RREP分组沿着逆向路径回传时, 此路径上的每一个节点都建立前向路由条目, 记录下当前的目的节点序列号, 同时产生到源节点的路由生存时间。不在RREP分组的回传路由上的节点建立的反向路由会因超时而被删除。由于RREP分组是采用RREQ分组建立的路由向前传送, 所以AODV算法只支持双向链路。
当节点回应RREQ分组而把RREP分组反馈到源节点时, 到发送RREQ分组的源节点的逆向路由已经建成了。如果节点收到多个RREP分组, 它会更新路由信息, 并根据目的节点序列号及跳数来决定取舍。节点只有在再次收到的RREP分组的目的节点序列号大于或等于原来的但跳数更少时, 才再次发送RREP分组。
3 改进算法
定义:路径的生存能力反映了路径的可用性能, 生存能力较大的路径更具有优越可用性。它主要由时间延时、可用带宽和路径生存活力来决定。令路径的生存能力为M, 则M可以表示为 (1) :
其中, λ, x, δ为调和系数, P为路由生存能力的平衡因子, 根据路径中数据包的探测情况而自行设定。Bandwidth、T、E分别代表路径的带宽、时间延时和路径生存活力, 而Bandwidth_B、T_B、E_B分别表示路径的带宽、时间延时和路径生存活力的估计标准值, 该值可根据实际情况进行估计。
路由建立的过程, 是一种通过请求/应答的不断循环获得多路由信息的过程。当源节点需要向目的节点发送数据且源节点又无到目的节点的路由时, 它就泛洪RREQ到整个网络。具体的传输探测包EERQ经过中间节点的过程如下:
(1) 当在传输的过程中EERQ中时延域大于有效时间域τ, 则该EERQ包由于在寻找路径的时间延时过长而失效。
(2) 根据该节点的节点记忆路由表中的存储容量标志Isfull, 其值为0的时候丢弃该EERQ包, 转 (7) 。其值为1的时候, 启动该节点的处理数据包定时器。
(3) 中间节点收到探测包RREQ后, 检查该节点的邻接表, 判断其临节点中是否有大于或者等于探测包RREQ中经过链路的带宽, 并进一步确定其值是否大于或者等于带宽域Bandwidth值。假如是, 则转 (4) ;否则, 此节点拒绝该包, 转 (7) 。
(4) 计算本节点的路径生存活力, 并将计算结果同探测包EERQ中的路径的生存活力域E进行比较。如果小于, 就更新此域值;否则, EERQ中路径的生存活力域值E保持不变。
(5) 检查该节点的处理数据包定时器是否关闭, 如果是, 则转 (7) 。根据节点自身的生存活力E来启动RREQ转发数据计数器并设定计数器的值。其生存活力E的值通过下式来计算。
(6) 再在探测包中判断自己是不是目的节点。若是, 则马上建立一个反向路由指向源节点, 并再与先前的进行比较, 假如有相同的路径, 则删除;没有, 就将EERQ存入该节点的存储器中。否则转 (8) 。
(7) 丢弃该包。
(8) 继续洪泛此EERQ探测包。
当所有探测包EERQ到达目的节点时, 形成的多路径可能存在链路的重复, 即由不同的EERQ包从源节点到目的节点的路径当中, 可能存在有重复的链路段。
4 仿真实验
网络拓扑结构是一个节点随机分布在1000 m×1000 m的平面矩形区域的网络模型, 移动节点数为50 m/s到100 m/s。MAC层采用IEEE 802.11, 采用恒定比特率 (Constant Bit Rate, CBR) 数据流, 仿真时间为900s, 其中节点最大停留时间变化范围是0s、40s、80s、120s、160s。在对AODV_MQS、DSR和AODV进行模拟性能评估时, 主要考虑如下性能参数:数据报文投递率PDF (Packet delivery fraction) , 数据报文端到端平均时延 (Average end to end delay) , 路由开销 (routing overhead) 。其主要性能参数见表1。
数据包分组成功投递率PDF:
端到端的平均时延Ta:
路由开销R_P:
由此可以看出, 三种曲线整体上都呈现出了上升的趋势, 这主要是因为随着网络节点数量的增多, 在有限的范围空间内, 节点之间相对的距离更加接近, 节点移动所带来的链路毁坏几率变小, 所以整个路径的稳定性就会上升。
5 结束语
可靠多路径路由 篇4
一、域间多路径路由协议
1.1性能指标分析
虽然多路径路由协议可以提供一种安全、可靠的网络性能解决方法, 然而域间多路径路由在部署方面还是存在一定的问题, 故对其进行设计的时候, 要从其基本的性能指标进行分析。多路径路由协议的性能指标主要包含以下几个方面:
(1) 路径多样性。指网络层路径的多样性, 主要优势是在节点出现故障或者策略发生改变时, 通过网络层拓扑存在的连接就可以保证通信不被中断。
(2) 数据平面开销。主要分为转发表信息及报文携带信息两部分, 与其紧密联系的是转发操作方式, 为保证同源同目标的报文经过不同路径传输, 需要扩展或改变路由器的转发表。
(3) 控制平面开销。主要分为路由平面开销及路由消息开销两个方面, 路由消息开销主要是相邻AS间对路由更新的数目进行交换。路由平面开销包括更新路由表的计算开销及存储路由的内存开销, 在路由消息转换的时候, 会占有一定的带宽, 在存储和计算的时候也会占用较多的存储资源及计算资源。
(4) 无环路特性。在网络动态变化时, 对路由环路进行路由协议检测的能力。转发环路会导致报文丢失或者造成资源的浪费, 所以在设计时要考虑无环路的特性。边界网关协议中采用AS路径通告保证无环路, 在多路径转发的条件下, 保证无环路特性的能力是检验路由协议的性能的重要指标。
(5) 策略表达。主要体现在AS控制路由的能力方面, 策略表达能力主要通过协议允许路由多样性的方式进行表达。
(6) 增量部署能力。是协议是否可以快速进行部署的能力指标, 表现在与BGP协议的兼容性方面。
(7) 可扩展性。由于域间路由系统较为复杂, 路由协议的可扩展性就成为衡量的指标之一。
(8) 用户控制路由的能力。多路径路由的优势在于用户可以选择多条路由, 这是与单路径路由最大的区别, 因此用户控制路由的能力非常重要, 需要注意的是用户需考虑ISP流量。
除以上这些重要性能指标外, 还有协议收敛时间、路径构造延迟及安全性等方面的性能指标, 就不一一例举分析。
1.2域间多路径路由核心问题
在多路径路由实现内部机制时, 还要对多路径的发现、选择及报文转发等问题进行综合考虑:
(1) 多路径发现。需要解决的首要问题是怎样让边缘AS对网络中的到达统一网络前缀的AS路径问题进行掌握, 根据图1, 可以看出发现多路径的方法。
第一种方法是在链路状态协议的基础上, 通过网络拓扑广播功能, 获取每个网络节点的拓扑, 整合出整个网络的拓扑。这种方法可以最大程度获取路径的多样性, 但由于域间路由系统的复杂性, 造成该种方法在扩展性方面较差。第二种方法是在路径向量协议基础上实施。BGP是一种典型的路径向量协议, 其只允许路由器通告给邻居一条好的路径, 而好的多路径发现是通告给邻居多条路径, 这就容易造成多信息出现或存储开销的增大。第三种方法是在主动多路径探测技术的基础上进行的, 这种方法通常是由边缘路由器发起, 对多路径主动进行发现。采用这种方式的协议通过对等路由器的显示对多路径信息的交换请求。
(2) 路径选择。需要解决的问题是在多条路径中如何去选择主路径与备用路径, 以此来保证在获取最大路径多样性的同时又将消息开销降至最低。一般情况下, 主路径选择采用BGP选择方法, 备用录用选择一般根据最大不相交边或不相交节点的路径, 也就是与默认路径节点或路径边不同的路径。也可以在延迟、报文丢失或带宽等路径特征的基础上进行路径选择。
(3) 报文转发。因为到达同一网络前缀的多条路径存在, 所以传统的逐跳转发方式已经不能有效的进行工作。在此背景下, 可以采用图2示意的报文转发方式进行:
在报文头上注明源路由路径信息, 经过路由器的读取, 可以分组对报文进行转发, 如果是基于目的地的路由, 可以用过路径标识的方法区分不同路径同一目的地的报文。根据设计者选择, 可全局也可局部, 此外还可以利用MPLS、IP隧道或虚拟接口等方法分组对报文进行转发。
二、域间多路径路由协议分类
虽然目前学术界对域间多路径路由研究的热度较高, 但还没有一个确切的定义。作者认为, 一个域间路由协议针对同一网络前缀报文可进行多路径转达, 那么该协议就可以被称为域间多路径路由协议。要求在转发时, 要有不同的地址支持同一个网络前缀, 还要在控制平面上支持。根据域间多路径路由协议的几个问题, 对域间多路径路由协议进行分类, 要求既要直观又要科学, 文章主要对其分为以下几个类别:
2.1单径通告多路转发协议
该协议最大的特点是各个AS针对各个网络前缀, 向邻居通告一条最佳路径, 然而报文可以通过不同的路径进行传送, 降低了路由器CPU负荷, 通信开销较低, 不足之处是限制了路径的多样性。 (1) BGP多路径。允许路由器对一个网络前缀在转发表与路由表中安装符合条件的多条路由。BGP多路径利用其发掘的路径信息进行路径的发现, 采用严格的路径比较进行路径选择, 进行流量分发达到报文转发的目的, 是一种简单的利用多路径的方法。 (2) MBGP。在BGP协议的基础上, 采用源的主动探测方法对路径的多样性进行发现。在实际操作中, 还没有一个具体的路径数量与消息开销的量化关系, 因此操作起来比较困难。 (3) 路由偏转。通过网络中规定路由器偏转规则, 在报文没有发生环路的情况下, 将报文引至非最短路径的路径上, 实现路径选择的功能。路由偏转最大的优点是方便了增量的部署。 (4) MIRO。如果一个AS需要特定路由, 需要发送请求进行搜索。该协议是在主动请求模式下对多路径进行发现的。其优点在于消息开销低, 只有在AS需要额外路由时才会产生消息开销;途径的AS可对备用设备进行策略设置;可以开发路径多样性。不足之处是MIRO多路径的建立要将延迟引入, 这就在故障发生的时候难以进行快速恢复。
2.2多径通告多路转发协议
该协议的特点是一个AS可向邻居通告多个AS路径, 增加了AS路径的多样性。但是多径通告的增加也增加了路由消息开销, 因此要对通告给邻居的AS路径数目进行控制。 (1) BGP。该协议是带ADD-PATH功能的, 该协议没有考虑到域间多路径协议设计中的诸多因素。 (2) R-BGP。该协议主要是为了降低控制平面开销及消息开销。 (3) YAMR。该协议在建立期间, 路由开销较高, 这也成为该协议部署的主要难题, 此外, 经过实验论证了该协议的正确性和有效性, 但在实际应用中尚不明确其有效性与正确性。
2.3新型域间多路径路由体系
该体系主要是路段路由和NIRA, 和上述两类协议不同, 该协议是长期的解决方案, 对兼容性不做考虑, 直接构建全新的域间多路径路由体系结构, 这种协议在短期内还实现不了, 目前尚处于方案的设计阶段。 (1) 路段路由, 指路由的一部分, 和传统BGP整条路由不同, 该协议只对部分路段进行通告, 然后对多个路段进行拼接组成整条路由。 (2) NIRA。该协议通过提出全新的路由体系结构, 并提出TIPP协议, 从而使用户可以发现路由。
三、结束语
可靠多路径路由 篇5
在有限的初始能量配置下最大限度地节省节点及网络的能量开销,以延长节点及网络的寿命,是WSN(无线传感器网络)应用研究中的一个热点课题[1]。多路径路由协议在WSN中明显优于传统的DSR(动态源路由)协议、AODV(按需距离 矢量路由)协议等,其对节点能量有效性、可扩展性和传输可靠性进行了综合考虑,采用了减少路由建立和维护的开销、提高路由可靠性等办法来降低数据分组传输的能量消耗。
网络编码融合了路由和编码的信息交换技术,核心思想在于允许网络中的节点对收到的信息进行编码操作,再转发出去,目的节点只需接收部分数据就能够解码出原始数据。网络编码在提高网络吞吐量、减少数据分组传输次数、均衡网络负载、减小传输延迟、节省网络带宽资源、降低节点能耗以及增强网络链路鲁棒性等方面均显示出优势,线性编码、随机网络编码均是较为成熟的方法。在实际应用中,如何高效地编码与解码是关键的技术手段[2,3,4,5]。
本文构建了一种新的网络编码方法,结合多路径路由技术,提出了一种WSN中新的能量有效算法,即MRAEE算法。目的是应用网络编码技术,在中继节点对数据分组进行编码,以增加数据传输的可靠性,减少分组不必要的发送频率,提高节点能量的有效使用。
1编码方案
1.1网络模型
非循环通信网络可以表示为有向图G (V,E),其中V为节点集,E为链路集;节点V的输入链路记为In(V),输出链路记为Out(V);对于任意一个节点对(d,e),xde表示(d,e)的数据流;如果节点对不相邻,则编码系 数kd,e = 0;S为源节点;KC为|E|×|E|矩阵;P表示主要理想域;ω为G维数;Jω,|E|表示ω×|E|矩阵。本文提出一种对于网络编码的可行模式,在R2(R代表矩阵G的秩)内使用泊松点过程模拟WSN,WSN内的节点随机散布在区域BR2。Φ0为区域B内的节点个数,λ0为密度,即单位面积的节点平均数。Φ1,Φ2,…,ΦN-1是N 1个二维独 立的基于 密度λ1,λ2,…,λN-1,泊松过程中 的节点描 述 ,它们独立 于Φ0,N为节点数 。假定每个节点可全向发送信号,且其自身的能量可动态调节,以控制它的发送范围。
1.2基本模型
在本文所提出的方法中,构建一个基于网络编码的多散联路由。网络编码示例如图1所示。
首先,源节点S发送数据分组a、b和c,编码这些分组形成数据1、数据2和数据3,然后将它们发送到目的节点D。这些分组将按多播特性几乎同时到达中间节点,即节点1、节点2和节点3。节点1成功收到数据1和数据2,对它们进行编码,形成数据4和数据5,然后将它们发送到下一个节点。节点2成功收到数据1和数据3,对它们进行编码,形成数据6和数据7,然后将它们发送到下一个节点。节点3成功收到数据1、数据2和数据3,对它们进行编码,形成数据8、数据9和数据10,然后将它们发送到下一个节点。目的节点D将收到三个编码过的数据分组,即数据4、数据6和数据10。当采用适当的网络编码方案后,目的节点D能够高效地还原三个原始的分组,即数据1、数据2和数据3。因此,传输的分组数无须增加,但可靠性会有很大提高,因为编码过的分组被发送到目的节点后,通过解码能快速实现分组信息的还原[6]。
2网络编码策略
在网络中,路由器或中间节点仅转发其收到的数据分组,而网络编码可让路由器或中间节点对数据分组进行编码,本文采用一种线性网络编码方案。
编码:将来自源节点的数据分组分成若干批,每一批包含N个分组,线性网络编码方案是给出编码矢量gi= (gi1,gi2,…,giN ),输入分组M =(M1,M2,…,MN)按式(1)转化成输出分组Pi:
目的节点能够解码出输入分组信息,因为编码矢量G=(g1,g2,…,gN),gij是从伽罗华域随机选择的系数,例如GF(28),输出分组数据P = (P1,P2,…,PN)可从接收到的分组信息中得到,并且存在逆矩阵于G。
解码:任何一个接收者(路由器或中间节点)都可对通过采集得到的一批分组进行解码。目的节点可用如下算法解码接收到编码分组。这些分组构造产生一个线性方程组系统,求解它们可找回原始发送的分组。解码矩阵表示这个线 性系统的系数矩阵。目的节点利用高斯-约当消去法将解码矩阵转化成一个简要的行梯次形式进行求解。假定一个节点收到属于某一批次的v个编码过的分组X1,X2,…,Xv,此处v≤ N,且代表对应某个编码过的分组的编码矢量,解码矩阵G的一般元素满足Gij=gij,此处i=1,…,v且j=1,…,N。当矩阵满秩时,R=v= N,对于传递过来给定的一批编码分组,节点能够求解线性方程组得出对应的原始分组信息。这种情形下,接收者能够复原得到由源节点发出的对应于给定的一批编码分组的原始分组内容。最终可观察到:当节点接收到一个分组时,必须检测它是否较新,即它是否增加解码矩阵G的秩,如果没有,则丢弃这个分组[7,8]。
当目的节点D收到N个以线性独立编码矢量表示的分组时,通过矩阵求逆可得到原来的分组。
3能量消耗
我们利用MRAEE算法推导出能量有效增益公式。假定源节点S需要传输信号到目标节点D,不考虑一般意义上的损耗,且假定信号发送周期为1s。
相对于非网络编码传输,基于网络编码传输的能量有效增益为GA,其定义如下:
式中,εptp为源节点S在非网络编码传输中对目标节点传输N个分组消耗的能量;εncptp为采用MRAEE算法在网络编码传输中源节点S对目标节点传输N个分组消耗的能量。接着,我们导出εptp和εncptp。εptp可表示为
式中,Pptp表示在非网络编码传输中点对点的平均传输能量。
为了用有限的平均能量传输,我们作一个限制,仅当信道的能量增益大于一个阈值时,节点才进行传输,否则,节点不传输或者处于断电状态。用ρuv表示信道在源节点与目的节点之间断电阈值,δ表示断电概率,即
式中,信道能量增益的指数分布|huv|2的概率密度函数由下式得到:
因而,式(4)可表示为
假定δ是一个固定的系统参数,我们能够从式(5)、式(6)中得到:
当未断电时,在非网络编码传输中,从节点1到节点2传输信号的平均传输能量能够计算得到,信道能量增益的指数分布|h12|2可表示为
式中,利用式(8)和式(3),可以得到:
对于MRAEE算法,节点1发送第一个编码过的分组到节点2,节点3和节点2之间的信道能量增益大于对应的断电阈值ρ32,因而,余下的分组利用MRAEE方法协同传送。
所有的能量消耗计算如下:
式中,Pnc表示未利用MRAEE算法时,在Pn1和Pn2发送期间,节点1的平均传 输能量。当它 们利用MRAEE算法进行网络编码时,分别代表节点1和节点3的平均传输能量。
4仿真实验
为有效评价MRAEE算法的性能,我们将之与著名的多路径路由协议算法EECA(基于能量高效冲突发现的多路径路由)算法[9]及NC-RMR(基于可信节点分簇网络编码多路径路由)算法[10]在能量消耗、分组传输率和网络寿命等方面做了相应的实验比较。仿真参数如下:节点总数为100,分布范围为1000s×1000s,发射距离为250m,节点平均度为3~5,仿真时间为600s,最大传输能量Ttmax为0.282 W,初始节点能量为30J,连接接收阈 值为3.652×10-10W,归避冲突 阈值为1.559×10-11W,信道带宽为1~3Mbit/s,连接延迟为20~200ms,流量类型为CBR,节点暂停时间为10s,除特别说明以外,均使用缺省值。
我们将在相同的能量模式和通信模式下对比三种路由协议的有关性能参数,主要从能量消耗、分组传输率和网络寿命三个方面进行相应的仿真比较。
(1)能量消耗:基于IEEE802.1低能量休眠模式的1-WLAN.规范,在发射层测量能量消耗。能量消耗的变化从0.013 W到0.83、1.0、1.4 W ,分别对应空闲侦听、接收和传输状态。
(2)分组传输率:分组传输率 = 接收的分组数/发送的分组数,代表某种协议的网络传输效率,是一个重要的网络量度指标。接收的分组数指任一目标节点接收的分组总数之和,发送的分组数是指任一源节点发送的分组总数之和。
(3)网络寿命:定义为网络节点的活动期,在这个时间范围内,节点能够处理、传输数据直到节点电池耗尽失效为止。
利用网络仿真软件NS2来评价计算NC-RMR协议。以BER(误码率)为参照基准来对比评述各项指标,在WSN中,BER通常在10-4~ 10-3。对于网络编码,一个代包含三个包 (即M =3)。图2比较了三种算法的能量消耗,由图可以看出,MRAEE算法的性能优于其他两种算法,它在较宽的误码率范围内表现出较低的能量消耗,说明网络编码技术对改善网络的能量效率有较好的作用。
图3比较了三种协议算法的分组传输率。从图中可以看出,对任一种流量负载类型,所有方案的性能都会受到BER增加的影响,但MRAEE比另外两种算法拥有更好的分组传输率。因为后两种算法采用的是传统的多路径结构,在分组的提取处理方面因为能量消耗过大而造成效率过低。
图4所示为网络寿命与BER的关系。当BER较小时,三种算法 差别不大;但当BER较高时,MRAEE的网络寿命远远长于另外两种算法,约有10%~ 30%的提高。
5结束语
本文通过构建一个基于网络编码的多路径路由,采用伽罗华域的编码矢量方法,利用高斯-约当行梯次矩阵求解技术,提出了一种新的基于网络编码多路径路由技术的节点能量有效算法MRAEE,并以BER为参照基准,与EECA和NC-RMR算法做了相应的比较,仿真结果表明,MRAEE算法在能量高效、网络生命延长及数据分组传递方面有较大的改进,具有较高的参考价值。
未来的工作中,我们将借助仿真技术重点考虑最优化和网络编码中解码算法的效率提高及其他参数的度量评测,以提高网络效 能,增进网络使用实效。
参考文献
[1]于宏毅,李鸥,张效义,等.无线传感器网络理论、技术与实现[M].北京:国防工业出版社,2008.
[2]王雪,王晟,马俊杰,等.无线传感网络任务分配的能效性控制策略[J].控制理论与应用,2007,24(3):127-134.
[3]Sun Baolin,Gui Chao,Song Ying.Energy Entropybased Clusterhead Selection Algorithm for Ad Hoc Networks[J].International Journal of Advancements in Computing Technology,2012,4(1):207-214.
[4]Sun Baolin,Pi Shangchao,Gui Chao,et al.Multiple Constraints QoS Multicast Routing Optimization Algorithm in MANET based on GA[J].Progress in Natural Science,2008,18(3):331-336.
[5]Sun Baolin,Gui Chao,Song Ying.Energy Entropy On-Demand Multipath Routing Protocol for Mobile Ad Hoc Networks[J].China Communications,2011,8(7):75-83.
[6]Sun Baolin,Lu Xiaocheng,Gui Chao,et al.Network Coding-Based On-Demand Multipath Routing in MANET[C]//Proceedings of 26th IEEE International Parallel&Distributed Processing Symposium(IPDPS).Shanghai:IEEE,2012:1514-1518.
[7]Anantapalli M K,Li Wei.Multipath multihop routing analysis in mobile ad hoc networks[J].Wireless Network,2010,16(1):79-94.
[8]Leinonen M,Karjalainen J,Juntti M.Distributed power and routing optimization in single-sink data gathering wireless sensor networks[C]//9th European Signal Processing Conference(EUSIPCO 2011).Barcelona,Spain:IEEE,2011:407-411.
[9]Wang Z J,Bulut E,Szymanski B K.Energy Efficient Collision Aware Multipath Routing for Wireless Sensor Networks[C]//Proceedings of IEEE ICC 2009.Xi’an:IEEE,2009:1-5.
可靠多路径路由 篇6
关键词：WIA-PA,DSR,WIA-PA多路径路由思想
工业无线网络技术是本世纪初新兴的一种面向设备间信息交互的无线网络技术,适合在恶劣的工业现场环境下使用,具有强抗扰、低功耗、实时通信等技术特征,是对现有无线技术在工业应用方向上的功能扩展和技术创新,并将最终转化为新的无线技术标准[1]。但是工业应用要求高可靠性、实时性、低功耗、低成本。怎么提高工业无线网络通信的可靠性,实时性,同时降低功耗及成本成为工业无线网络研究的关键问题。
1 WIA-PA概述
工业无线网络WIA-PA是由我国无线联盟所推出的具有自主知识产权的高可靠、超低功耗的智能多跳传感器网络技术,此技术提供一种自组织、自治愈的智能Mesh网络路由机制,能针对应用条件和环境的动态变化,保持网络性能的高可靠性和强稳定性[2]。
WIA-PA网络拓扑结构采用Start+Mesh网络的拓扑结构如图1,此技术具有支持扩频与窄带通信、超低能耗、分层组织模式、高可靠组织网络技术特征,同时兼容无线HART标准和IEEE802.15.4标准[2]。同时采用多种技术保证无线通信的高可靠性:TDMA模式保证实时性,同时使精度高达微妙级;跳频通信技术改善端到端的抗干扰能力;设备冗余提高了系统的鲁棒性;重传机制保证了数据传输的成功率;智能Mesh网络技术,有多条路径保证网络通信的可靠性[2]。
2 WIA-PA多路径算法思想的提出
2.1 DSR路由协议
DSR(Dynamic Source Routing)协议是一种典型的Ad Hoc网络按需路由协议[4]。它根据业务需要建立和维护路由,主要包括两个过程:路由建立和路由维护[4]。DSR路由协议使用源路由机制,是一种有数据分组源节点确定转发该分组的全部节点序列技术,中间节点不关心路由信息。
DSR路由协议具有路由协议设计简单;源路由机制;无环路;支持睡眠;提供多路径同时节能,针对相对比较静止的工业应用性能较优。但产容易产生失效路径,路由开销大;扩展性不强。
2.2 WIA-PA多路径算法思想的提出
WIA-PA应用于工业无线网络,因工业无线设备布局相对稳定。由于WIA-PA网络采用TDMA模式通信,采用信标的IEEE802.15.4-2006超帧结构[3]如图2,每个超帧包括多个时隙,采用此结构保证了数据的实时性和可靠传输。
WIA-PA网络的自组织、自治愈的智能Mesh网络路由机制同Ad hoc网络极为相似。在多条Mesh网络通信中,影响网络可靠性的关键因素是路由方式,因此路由算法是网络可靠性、实时性的核心。同时工业设备采用电池供电,降低功耗,延长电池寿命也成为工业应用研究的重点。结合以上DSR的特点以及WIA-PA网络的技术特征规范,该文提出一种新的多路径路由协议算法WMD-SR(WIA-PA Multi-path Dynamic source routering)思想,关键是提高网路通信的可靠性、实时性,同时降低功。
2.3 思想提出的模型研究与设计
2.3.1 数学模型
路由发现过程有多条路径,每条路径的寿命不相同,假定用L表示任意一对节点链路的寿命。从源节点到目的节点有n-1条链组成,同时Li表示第i条链路的寿命。假设每条链路是相互独立,则每条链路是串联的,当一条链路出现断路,此条路径将中断网络通信。用表Rt示一个随机路由的寿命,可以表示为:
同时设计到路径的能量问题,当中间节点能量过低时,影响网络的寿命,为此该文把能量给予分级定义,同时每条路径的寿命也有各个节点的最小能量有关。假设每个节点的剩余能量为P,第i节点的剩余能量用Pi表示,同时设定两个参数α和β,当Pi>α时表示节点剩余能量可以是网络正常通信级别;当α>=Pi>β时表示剩余能量处于警告级别;当Pi<=β时表示处于危险级别。用S表示每条路径的当前状态。可以表示为:
结合数学模型的分析,影响网络通信性能是怎么提高网络寿命,降低网络通信能耗是路由设计必须考虑的问题。
2.3.2 协议模型
该文通过改进DSR路由协议设计模型,结合节点剩余能量和平均时延,利用图论中带权有向图G(V,E)实现路由模型设计如图3所示。
该文设计的关键是保证网路通信的高可靠性、实时性同时,降低整个网络的功耗。在网络中从源节点S到目的节点D有多条路径,怎么选择最优的路径是该文设计的重点。
如图3所示,该文定义了有向图G(V,E):V表示图中的每个路由节点集合;E表示图中路由节点的边的集合;Wi权值表示相邻节点的平均时延;
DSR采用单路径通信,同时采用最短路径作为路由选择的标准。该文设计采用多路径路由备份,假定每个节点到目的节点都有一条主路径和一条或更多的备份路径。当主路径断路时,直接启动备份路径通信,从而提高可靠性,降低时延。该文路由选择标准如下表示:
公式(1)(2)分别表示了主路径与备份路径选择的公式,Tthreshold表示路由选择标准的阀门值,P(R)表示每条路径的平均消耗能量;T(R)表示每条路径总平均时延;η表示不同路径之间的相关因数。
每条路径节点的平均剩余能量P(R)表示为:
Ω:表示源节点和目的节点之间所有可选路径的集合;
L(k):源节点和目的节点之间所有可选路径的任一条路径;
e(i):表示每个节点Vi的剩余电池量;
V(i):表示第i个节点;
n:表示L(k)路径上的节点数;
每条路径总平均时延T(R)表示为:
Ω:表示源节点和目的节点之间所有可选路径的集合;
L(k):源节点和目的节点之间所有可选路径的任一条路径;
W(i):表示相邻节点端到端的平均时延;
n:表示L(k)路径上的节点数;
相关因数η的定义表示备份路径与主路径之间相交的链路个数,例如当主路径与备份路径的共享资源节点只有源节点和目的节点时,η=0;当中间节点有3个节点共享的话,η=1。
有文献[7]对路径相关性定义,相交性指路径之间的节点相交度,它分为节点不相交多路和链路不相交多路径。节点不相交多路径是相互独立的,互不影响,只有源节点与目的节点共享,而链路不相交多路径中有相交的节点,当相交的节点出现问题时,就重新发现路由。该文采用链路不相交多路径的方式。
该文设计的路由协议改变了DSR路由协议过期路由的问题,同时结合WIA-PA的要求,引入能量作为路由路径选择的判断依据。本设计的备份路径个数与设置的参数有关,不同的路由可能有不同的备份路径个数。在设定的Tthreshold范围内,符合要求的都可以选为备份路径,当中间节点的主路径断路时,直接启动备份路径,不在重新发现路由。
2.3.3 WIA-PA多路径路由实现研究
该文设计思想是基于WIA-PA网络对DSR进行改进,但是怎么实现路由设计还是一个难点。WIA-PA网络比较适合静态路由[3],WIA-PA网络采用的TDMA通信方式,同时路由更新也是该文设计的难点。
在路由设计中改进主要从两个方面改进,路由发现与路由维护。在比较成熟的路由协议设计中存在路由过期、路由更新负载大、时延高等问题。针对这些问题,同时结合WIA-PA网络协议的技术特征,通过路由发现和路由维护改进DSR路由协议,使其适合WIA-PA网络。
2.3.3. 1 路由发现
该文设计的路由发现的过程以及路由更新都在网关上进行,当一个新加入的节点成为路由后,网关会根据各个路由节点汇报节点信息,通过路由算法建立路由表,然后发送给各个路由节点。
网路路由发现的过程:源节点向自己的邻居节点发送路由请求,为了减少路由的过期路由,该文采取目的节点判断选择主路径与备份路径。当中间节点收到路由请求后,不给予源节点应答,直到目的节点根据Tthreshold大小选择路由的主路径和备份路径,选择Tthreshold最小的作为主路径,其次设定一个参数α,Tthreshold的值小于α的路径都做为备份路径。然后目的节点采用反向路由依次答复源节点,通过网关分配给每个路由。
2.3.3. 2 路由维护
路由维护是WIA-PA网络研究的难点,怎么保证备份路由是有效路由,是路由维护的重点。路由维护的过程:该文通过超帧结构采用TDMA通信方式,路由节点通过每个时隙与邻居节点通信,同时把自己的信息汇报给上级路由,当网关发现自己的路由信息不一致时,更改路由信息,然后重新分配给路由。当中间节点出现断路时,不用及时向上级路由报告,在重发时启动备份路由通信,同时下个时隙将自己的路由信息报告给网关,网关根据路由信息动态的发现路由,重新为路由节点分配路由。当路由节点没有路由变化时,网关不更新路由信息。
3 结束语
该文结合国家863重点项目“工业无线技术及网络化测控系统研究与开发”研究,根据WIA-PA网络要求,引入降低能量和平均时延因素,通过改进DSR路由协议算法使其适合WIA-PA网络,并能保证网络的可靠性、实时性,降低功耗。提出了一种多路径路由协议算法WMDSR。此算法正在研究过程中,具体的比较结果还没有完成。但通过分析与研究,其可行性和性能能够满足WIA-PA网络的需求。
参考文献
[1]于海斌,梁炜,曾鹏.工业无线网络技术体系与WIA标准[J].自动化博览,2009,26(1);17-20.
[2]工业无线网络WIA[EB/OL].http://www.industrialwireless.cn/03.asp?pd=dl&nclassid=616&anclassid=16
[3]中华人民共和国国家标准《国家工业无线网络WIA规范》.ICS25.040.GB/T[S].中华人民共和国质量监督检验检疫总局发布,2009.
[4]Johnson D B,Maltz D A,Hu Yih-Chun.The Dynamic Source Routing Protocol for Mobile Ad hoc Network(DSR)[R].draft-ietf-ma net-dsr-09,2003.
[5]彭献武.移动自组网多路径路由协议研究[D].长沙:湖南大学.2006.6;
[6]马万良,战松涛.移动Ad Hoc网络中的多路径路由技术研究[J].计算机安全,2009(4):32-36.
[7]王静.基于路由可靠性的DSR协议多路径技术研究[D].成都:电子科技大学,2008.
[8]税国军,沈树群.多路径DSR和AODV路由协议性能研究[J].计算机工程,2009,35(6):23-28.
可靠多路径路由 篇7
我们提到无线Mesh网络的路由协议可以借鉴Ad Hoc网络的路由协议。Ad Hoc网络路由协议从大的类别上不外乎分为三种:一种为先验式路由协议,也叫表驱动式路由协议;一种为反应式路由协议,也叫源驱动按需路由协议;最后一种就是二者的混合,叫混合式路由协议。无线Mesh网络也可以沿用这三种类型的路由协议。
先验式路由协议简介:
先验式路由协议又被称为表驱动路由,是一种基于表格的路由协议。在这种协议中,每个节点维护一张或多张表格,这些表格包含到达网络中其它所有节点的路由信息。当检测到网络拓扑结构发生变化时,节点在网络中发送路由更新信息。收到更新信息的节点更新自己的表格,以维护一致的、及时的、准确的路由信息。
典型特征:每个节点都要周期性广播路由信息,主动地发现并维护路由表。
表驱动:典型协议DSDV(Destination Sequenced Distance Vector)
反应式路由选择协议简介:
反应式路由选择协议又称为源启动按需路由,是一种当需要时才查找路由的路由选择方式。节点并不保存及时准确的路由信息。当源节点要向目的节点发送报文时,源节点在网络中发起路由查找过程,找到相应的路由后,才开始发送报文。为了提高效率,节点可以将找到的路由保存在缓存中供后续发送使用。
典型特征:只有在需要发送数据时,源站点才寻找路由
按需路由(事件驱动)典型协议:AODV(Ad Hoc On-demand Distance Vector)DSR(Dynamic Source Routing)
1 按需路由DSR算法
DSR是一种按需(on-demand)的路由协议,是一种基于源路由的按需路由协议,它使用源路由算法,每个节点都有一个Route Cache,记录路由的路径轨迹,当某源节点要发送数据给某一目的节点时,首先查看自己的Route Cache中是否存在现成的路径可以使用(有时甚至保存有多条),如果不存在,则启动Route Discovery过程,即广播一个RREQ请求分组,其中包含目的节点地址、源节点地址、Request ID和一个Route Record(用于按顺序逐个记录此RREQ所途经的节点地址)
算法描述:如图1所示。当节点收到Route Request时,如果在此之前已收到过同一源节点、同一ID的RREQ(表示这是重复的),则该请求分组丢弃,如果在Route Cache中发现已经有到目的节点的路径(表示自己可提供到达目的节点的路径),则把此路径加入Route Record并创建RREP应答分组,回复源节点并丢弃该请求分组,如果自己是目的节点,此时Route Record中记录的就是从源节点到目的节点的路径信息,把此路径加入RREP应答分组,回复给源节点,并丢弃该请求分组,否则,代表自己是中间节点,把自己的地址附加在Route Record中,然后再继续广播Route Discovery过程中的Route Reply过程以一条路径为例,N8-N5-N2-N1从目的节点N8回到源节点N1。
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消息,此数目可由我们自己确定。
例如,如图2所示,假设节点C已存在到达节点D的路由C-E-D和C-F-D。当节点S有数据要发送到节点D时,节点S首先发送RREQ消息,节点A和节点B收到RREQ消息后,由于A和B不是目的节点,也不存在到达目的节点的路由,则节点A和B转发RREQ消息。这样,节点C和E收到RREQ消息,节点C存在到达目的节点D的路由,同样,节点E也存在到达目的节点D的路由。可见,C和E都是中间节点,根据改进,节点C会收到两个RREQ,一个从节点A来,一个从节点B来,节点C会对这两个RREQ消息都给出回应。这样,节点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都到达,则目的节点发送给路由应答消息给源节点。具体过程见图3源节点到目的节点的带宽请求为5,在路径S-C-D,中,链路S-C和C-D都预留带宽5;在路径S-A-E-D和S-A-F-D中,在节点A处包发生分离,一部分完成带宽请求3的寻路,一部分完成带宽请求2的寻路,并找到相应路径。这样,就找到两条满足带宽请求的通路。
2.4 预约带宽方案
但是这种方法有一个问题,就是因为没有进行资源预约,可能会发现争抢带宽的现象,也即是说应该有一种方法使得链路的剩余带宽信息能很快的反馈到各个节点。
关于各个节点剩余带宽的解决方案:我们为每一个节点建立一张节点状态表;(我们称之为转发表),用于带宽估计,图4为带宽估计体系结构,表1所示为转发表结构。
在入口节点处,当有数据包到达时,查看其IP头部的源地址,以确定改数据包从哪个节点进入MESH网络,再查看转发表是否有匹配项(即是否有相应的peerEdge),如果存在匹配项,则将数据包的大小累加到相应项的recvByte中;如果不存在匹配项,则建立新的状态项,并将数据包的大小累加进其recvByte中。如果该数据包被出口节点的队列管理机制丢弃,则该数据包的大小应累加进其相应项的dropByte。recvByte和dropByte分别表示出口节点本地所接受的数据量和本地所丢弃的数据量。发送信息的源节点,在每一固定时间间隔向特定的目的节点发送探测包,链路上每一个节点在接受到探测数据包以后,查看状态表,以(recvByte-drop-Byte)/(now-lastStatTime)做为该链路上所能使用的带宽估计,并将该带宽估计反馈给源节点。同时将转发状态表中相应状态项的recvByte和dropByte置为0,将lastStatTime置为当前时间。如果在路由查找时,带宽估计够PACKET或SUB-PACKET传递,预留相应带宽,置为1,并启动一定的时间(即生存期)在过生存期后,预留带宽被释放,否则,置为0。
3 结束语
由于时间仓促,将该路由算法性能的仿真并未能完成。由于该路由算法发现多条路径,并且需要计算节点的剩余带宽,可能会出现相对较大的时延,但是该算法对多路径防止断裂,增加稳定度,有利于负载平衡,传递数据时,减少对带宽的要求,都能到很好的改善。总之,由于无线Mesh网络中节点的移动性,以及链路的易受干扰性,使得数据易丢失,采用多条路径可以在一定程度上减少和克服这种缺点,并支持QoS,不失为一种较好的解决办法。
摘要：无线MESH网络是一种高速度,高容量的多点对多点网络,是一种新型的解决“最后一英里”问题的分布式网络,可把它堪称Ad Hoc网络的简化版本。无线MESH网络中的路由是它的一项关键技术,基于此,该文为对无线MESH网络的路由协议进行了改进研究,文中首先介绍了Ad Hoc网络三种路由协议,重点研究了其中一种动态源路由协议(DSR)的具体实现过程,并在支持QoS服务基础上,对DSR协议进行了改进,并提出了一种新的路由算法MSBR多路径分流带宽算法,该算法可以在源节点和目的节点之间找到多条路径并解决单条路径上不能满足的带宽请求时分配到多条路径上的问题。
关键词：无线MESH,动态源路由协议DSR,QoS,MSBR
参考文献
[1]刘正蓝,朱淼良.基于边界到边界带宽估计的数据包标记器[J].通信学报,2003,8.
[2]王晓燕.无线Mesh网络路由协议的研究[D].西安电子科及大学,2005.
[3]樊自甫,万晓榆.新一代宽带无线网络结构[J].通信世界.2003,9:42-44.