多路径路由研究论文

2024-07-30

多路径路由研究论文（共9篇）

多路径路由研究论文篇1

在对传统路由协议的分析中,由于传统路由协议大多采用单路径的路由方案。对于多点对多点的网络拓扑结构来说,单路径路由具有不稳定性,不能使网络资源得到充分的利用,使网络的利用率降低,不能实现网络负载的均衡分配。同时对于那些对网络服务质量QoS有很高要求的新兴业务来说,设计一种带有多个服务质量QoS约束的路由协议来优化网络资源就显得尤为重要。

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网络性能的优化来说,无线路由协议的研究是一项十分重要的内容。

关键词：无线Mesh网络,独立多路径,负载均衡,节点不相交

多路径路由研究论文篇2

无线传感器网络和Adhoc网络一样，是无线自组织网络的一种，因此，它的路由协议也可以从无线Adhoc网络得到一些启发。本节首先对无线Adhoc网络的路由协议AODV进行研究，详细介绍其路由实现原理。然后详细介绍北京交通大学下一代互联网互联设备国家工程实验室代写计算机职称论文自行研制和开发的路由协议MSRP，MSRP借鉴了AODV的思想，但是又做了很大的简化。本论文所设计的多径路由机制是在MS即的基础上做了创新和改进。本节评价了它的优点和缺点，指出了需要改进的地方。

1.AODV路由协议AODVI’jj(AdhoeOndemandDistanceVectorRouting)是一种按需驱动的路由协议，它能够在移动节点之间建立动态多跳路由并维护一个Adhoc网络。AODV能让节点快速建立到新目的节点的路由，而且不需要节点维护处于非活动状态路径的路由。在链路损坏或者网络拓扑发生变化时，网络中多个移动节点能够及时做出反应，网络能够快速自愈。当网络链路出现断裂时，AODV能够通知所有受影响的节点，让它们及时删除使用该链路的路由。AODV一个很重要的创新点是对每一条路由使用了一个目的序列号，任何一个路由表项必须包含到目的节点的最新的序代写计算机硕士论文列号信息。目的节点序列号由目的节点产生。每一个目的节点在它发送给请求节点的任何路由信息中都会包含这个序列号，使用目的序列号可以保证路由无环路，也利于编程实现。当出现两条路由到达目标节点时，请求节点会选择序列号比较大的路由。节点收到任何有关报文，只要其中有关于目的序列号的信息，该目的节点的序列号就会更新。网络中的节点各自保存和维护自己的序列号。一个目的节点在下列两种情况下产生自己的序列号:

1、在建立一个路由发现之前，它产代写计算机毕业论文生自己的序列号，避免与以前建立的到无线传感器网络路由协议的研究该源节点的反向路由冲突;

2、在产生一个RREP回复双EQ之前，将自己节的序列号更新为目前节点的序列号和路由请求中该节点序列号两者的最大值。下一跳链路丢失时，序列号不再更新。这时候，对于使用该下一跳的每一条路由，节点都将其目的序列号加一，并将该路由标计为失效。只有再次收到“足够新”路由信息时(序列号等于或大于该记录的序列号)，该节点才会将路由表中相应信息更新。AoDv定义了三种报文类型:路由请求(RREQs)、路由回复(RREPs)、路错误(计算机专业职称论文RERRs)。这些消息包装在uDP报文中，端口654，并使用通常的IP报头，请求节点使用自己的IP地址作为路由消息中的“源IP地址”字段。对于广播消息，使用IP广播地址255.255.255.255。这意味着这些消息不会被盲目的转发。但是，AODV确实需要某些报文(例如路由请求消息)能够大范围甚至在整个网络中洪，IP报文的TTL字段可以用来限定传播范围。只要通信的两个端有到对方的有效路由，那么AODV就不参与。当节点需一个到新目的节点的路由时，该节点会广播路由请求进行寻找。当该路由请求达目的节点，或者一个中间节点具有一个到目的节点的“足够新，的路由时，这条路由便可以确定下来。每一个收到路由请求的节点都会缓存一个到源节点的反路由，这样，“路由回复”便会从最终目的节点或者满足请求条件的中间节点顺利递到源节点。节点会监测有效路由下一条链路的状态。当监测到有链路发生断裂时，节会发送路由错误消息来通知其他节点:链路已经丢失，需要重新寻找路由。“路错误”消息用来表明一些节点通过该断裂的链路己经不可达。为了采用这种错误告的机制，所有节点保存一个“前驱列表”，前驱列表包含一些邻居的IP地址，些邻居节点可能使用本节点作为到达目的地的下一跳。前驱列表的信息可以很易的在路由回复的时候获取，因为从定义上来说，“路由回复”就是要发送给前歹J表中的节点的。AODv是个路由协议，因此它有自己的路由表管理机制。即使是暂时的路信息(例如到路由请求源节点的暂时的反向路由)，也需要在路由表中保存。AOD的路由表有以下几个组成部分:目的IP地址、目的序列号、有效目的序列号标以及其他的标志(如有效、无效、可修复、正在修复中)、网络接口、跳数、下跳、前驱列表、生命期(路由表的失效或删除时间)。

1AODV路由建立过程当一个节点发现自己需要路由却不存在路由信息的时候，它发起路由请RREQ，RREQ中的目的节点序列号是从路由表中的目的节点序列号域中拷贝过来的，是最新的。如果序列号未知，那么路由请求报文中U位(未知序列号，表明发送路由请求的节点对目的序列号一无所知)置1。路由请求报文中，源节点序列号是节点自身的序列号，在插入到该路由请求报文中之前会进行加一操作。路由请求ID也是在最新的ID号上面进行加一操作，每一个节点仅仅维护一个路由请求ID。广播路由请求之前，源节点将缓存该路由请求ID和源节点IP地址，这样，当该节点再次收到相同的路由请求时，会忽略该请求，从而避免广播包风暴。类类型型JJJRRRGGGDDDUUU保留留跳数数路路由请求IDDD目目的IP地址址目目的序列号号源源IP地址址源源序列号号路由请求报文格式FigZ一3RREQmessageformat节点收到RREQ之后，首先会创建或者更新到上一跳的路由，然后检查是否在PATHDISCOVERYTIME时间内收到过相同的路由请求。如果收到源IP和请求ID相同的路由请求，那么节点会直接丢弃路由请求。如果收到不同的路由请求，节点增加路由请求报文中的跳数字段，然后节点查询到源节点的反向路由，如果没有，会创建一条路由，如果找到，可能会更新路由表中的序列号。当节点接收到一个传给源节点的路由回复时，报文将沿着反向路由发送到源节点。同时，收到RREQ的中间节点，查看自己的路由表中是否有到目的节点的有效的路由，即路由表中的目的节点的序列号不小于RREQ中携带的序列号;若没有，中间节点更新路由表并向其邻居转发RREQ;若存在到目的节点的路由或该中间节点就是目的节点，将发送RREP报文给源节点，RREP中包含新的目的序列号和路由，转发RREP的节点更新路由表。源节点收到后，就获得了到目的节点的路由。节点在以下两种情况下产生路由回复，节点本身是目的节点;2)节点是中间节点，有到目的节点的路由，该路由有效，并且序列号等于或者大于路由请求报文中的目的序列号。无线传感器网络路由协议的研究类类型型RRRAAA保留留前缀缀跳数数目目的IP地址址目目的序列号号源源IP地址址生生命期期路由回复报文FigZ一4RREpmessageformat如果目的节点产生路由回复，并且路由请求中的序列号等于节点序列号，么节点将增加自己的序列号。目的节点将自己的序列号放入路由回复报文中，将其中的跳数字段设置为O。如果中间节点产生路由回复，那么该节点将把自己知道的目的节点的序列号拷贝到路由回复报文中。同时，中间节点把路由表中该节点到目的节点的跳数拷贝到路由回复的跳数字段中。在路由回复向源节点递的过程中，每经过一个节点，跳数字段加一。源节点与目的节点之间可能需要建立双向通信链路，此时仅仅建立一条从节点到目的节点的路由是不够的，目的节点也需要建立一条反向路由。为此，节点将RREQ中的G位(免费路由回复标志;表明是否需要发送免费路由回复到标IP地址)设为1，这样中间节点就得知源节点需要和目的节点建立双向通信。一般来说，一个节点收到路由请求并且向源节点发送路由回复之后，会直将路由请求报文丢弃。如果路由请求报文中’G’字段被置1，那么中间节点还需向路由请求的目的节点发送“免费路由回复”。免费路由回复从中间节点逐跳传到目的节点，就好像目的节点发起过到源节点的路由请求，中间节点发起了路回复。中间节点接收到路由回复之后，首先会在路由表中查找到上一跳的路由，果没有找到，会创建一条没有有效序列号的路由表项。然后，节点给路由回复跳数字段值加一。如果到目的地址的路由表不存在，节点会建立一条到目的地的路由表项。如果到目的节点的路由表存在，那么中间节点会比较路由表中目序列号和路由回复报文中的序列号，比较之后，更新路由表中的序列号。这样，当前节点就可以用这条路由来转发到目的节点的数据包。如果当前点不是路由请求的源节点，那么节点转发该路由回复到去往路由请求源节点的一跳。节点发送路由回复时，到目的地的前驱列表也被更新，即把路由回复的一跳节点放入到前驱列表中。AODV路由维护过程节点通过广播本地HELLO消息来提供链路的链接信息。每次经过HELLOINTERVAL时间间隔，节点检查自己在这段时间内有没有发过广播包，如果没有发过，则发送一个TTL值为1的HELLO报文。节点可以通过监听从邻居发来的HELLO数据包来确定链路连接性。如果规定的时间内，节点收到邻居的HELLO报文，经历一段时间后再也没有收到该邻居发来的任何信息，那么节点会认为该邻居节点已经失效。每次节点收到来自邻居的HELLO报文，节点应该确保自己有一条到邻居的路由。如果没有的话要创建路由，如果有的话需要更新生命期。当节点检测到路由回复失败后，会将这样的节点放入到黑名单中。检测的方式可以采用链路层或者网络层的ACK。节点在经过规定的时间后会从黑名单列表中清除。一般来说，路由错误和链路断裂的处理需要一下几个步骤:l)将已有的路由表项设为无效2)列出所有受影响的路由3)决定哪一个邻居节点可能受到影响4)将合适的路由错误消息发送给相应的邻居节点路由错误消息可以多种方式传播。前驱节点个数很多情况下，一般采用广播的形式，如果前驱节点只有一个，可采用单播，如果不适合采用广播，可以依次单播到每一个前驱节点。类类型型NNN保留留不可达目的节点序列号号不不可达目的节点IP地址址不不可达目的节点序列号号其其他不可达目的节点IP地址址其其他不可达目的节点序列号路由错误报文FigZ一5RERRmessageformat节点在以下情况下会发送路由错误消息:l)在利用有效路由发送数据时检测到下一跳失效，此时，节点在自己的路由表中搜寻所有利用下一跳的路由表项;无线传感器网络路由协议的研究2)收到一个数据包，但路由表中没有相应的路由;3)收到邻居的路由错误消息。对于第一种情况，节点会搜索路由表，列出所有因为邻居失效而不可达的终目的节点。对于第二种情况，只有一个最终目的节点不可达，即数据包的最地址。对于情况三，节点也会搜索路由表，当找到邻居节点为下一跳路由时也将其加入列表。列表中的一些不可达地址可能会被邻居节点使用，因此必要时向邻居发送路由错误消息。当一条链路断裂时，如果到目的节点的跳数不超过上限，断裂的上游节点以采取本地修复的策略。节点先缓存数据包，然后把该不可达目的序列号加一，发起到该目的节点的路由请求，节点会一直等待路由回复。如果本地修复没有功，那么节点将发送路由错误消息。本地修复可能引起到目的节点的路径比较长而且可能会增加传送到目的节点的数据包的数量，因为当发送路由错误消息时，数据包是不会被丢弃的。本地修复之后再发起路由错误消息可能会让源节点找更好的路径。

多路径路由研究论文篇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

多路径误差是影响高精度GPS测量定位成果精度的`主要误差源.本文阐述了多路径误差的特点、影响的规律性以及消除或削弱多路径误差影响的方法和措施,为从事高精度GPS测量定位及其科研工作提供参考.

作者：郭英起黄声享 GUO Ying-qi HUANG Sheng-xiang 作者单位：郭英起,GUO Ying-qi(黑龙江工程学院测绘工程系,哈尔滨,150050;武汉大学测绘学院,武汉,430079)

黄声享,HUANG Sheng-xiang(武汉大学测绘学院,武汉,430079)

多路径路由研究论文篇5

关键词：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.

多路径路由研究论文篇6

移动自组织网络(简称移动Ad Hoc网[1])作为一个临时性多跳自治系统,是由一组带有无线收发装置的可移动节点所组成,并且不依赖于预设的基础设施,具有可临时组网、快速展开、无控制中心、抗毁性强等特点,在军事和民用方面都具有广阔的应用前景,是目前网络研究中的热点问题。近年来,随着无线通信技术的迅速发展,语音、视频等多媒体业务也逐渐应用于移动Ad Hoc网,因而如何在移动Ad Hoc网中提供高质量的QoS保障[2,3]是当前亟待解决的问题。同时值得注意的是,在Ad Hoc网中,数据的传输主要通过单路径路由的方式进行,对于大流量数据业务来说,该方式无论在容错能力上还是在带宽利用率[4]上都远远无法满足需求。因此本文将针对移动Ad Hoc网中多路径QoS路由进行研究,通过推导证明提出路径长度限制的路径稳定的约束关系,引入QoS的判定因子对该确定性的最优权值约束算法进行实例化,并在该路由算法的基础上提出基于QoS保障的多路径[5]路由协议(MP-QAODV)。

1 网络模型及数学描述

本文采用通过一个有向图G(V,E)表示一个网络,V为节点集合,E为边集合,e=u→v表示节点v到节点u的链路,其中每条链路e都关联k个相互独立的权值w1(e),w2(e),…,wk(e),

∈R+,∀1≤j≤k 。向量W(e)=[w1(e),w2(e),…,wk(e)]表示链路e的权值矩阵。向量W(p)=[w1(p),w2(p),…,wk(p)]表示路径p的权值矩阵,其中每条路径p的权值wj(p)可以通过简单累加路径中的每一条边的权值来获得,即

$w_{j} (p) = \sum_{i = 1}^{n} w_{j} (v_{i - 1} \to v_{i})$

定义1:假设图G(V,E)有k个不同的权值,其中k≥2,src表示源节点,dest表示目的节点,多约束条件限制问题(Multi-Constrained Problem,MCP)就是找出一条从src到dest的路径p,其中w1(p)≤c1,w2(p)≤c2,…,wk(p)≤ck,c1,c2,…,ck表示k个约束条件。当k=2时,转换成两个约束条件问题。

定义2:假设图G(V,E)有k个不同的权值,存在两条从相同源节点到相同目的节点的路径p和q,如果W(p)<W(q),那么有路径p主导路径q,也可以说q被p主导。如果路径p在从相同的源节点到相同的目的节点的路径上不被任何路径主导,那么就有路径p为非主导路径。由此可知,当k≥2时,图中存在不止一条非主导路径。当k=1时,该非主导路径也就是最优路径。

性质1:如果从源节点到目的节点存在一条满足所有QoS约束的路径,那么必然至少存在一条从源节点到目的节点并且满足这些约束的非主导路径。一个性能较佳的QoS路由算法仅仅只需要考虑从源节点到目的节点的非主导路径。

2 基于QoS约束的路由算法描述

2.1 路径长度限制的路径稳定的路由算法

通常来讲,路径的稳定度直接影响网络性能,尤其在无线网络环境下,对路径的稳定度要求更高。但是路径的稳定度和对应节点跳数要有一个权衡,往往由大量节点跳数组成的稳定路径的网络性能都不尽如人意。本算法意在对路径长度和路径稳定度进行权衡,从而寻找出一条满足两个限制条件的最佳路径。下面定义两个权值:

假设权值w1∈N*表示路径中的节点跳数,对于任意e∈E,存在w1(e)=1;对于任意路径p=(scr=u0)→u1→…→(un=dest),存在权值 $w_{1} (p) = \sum_{i = 0}^{n - 1} w_{1} (u_{i} \to u_{i + 1}) = n$ 。

假设权值w2∈R+表示路径稳定度。为了定量分析路径稳定度,设定一个范围值,1表示稳定度最高,0表示稳定度最低,同时规定路径中一条边的存在仅在两个端节点的通信范围R之内,这样路径中边的稳定度判定条件为

$\lim_{d_{x, y} \to 0} ψ (e) = 1 ‚ \lim_{d_{x, y} \to R} ψ (e) = 0 (1)$

式中:dx,y表示端节点x,y之间的距离值。通过数学变换,式(1)可以转化成

$ψ (e) {\begin{cases} (R - d_{x, y}) / R, d_{x, y} \leq R \\ 0, d_{x, y} > R \end{cases} (2)$

一条路径由多条边构成,因而路径稳定度可表示成

$ψ (Ρ) = ψ (s, d) = \prod_{e_{i} \in S_{s, d}} ψ (e_{i}) (3)$

式中:路径P=(s,d),而s,d分别表示源节点和目的节点;集合Ss,d表示构成路径的边的集合。

假设集合Πs,d表示从源节点s到目的节点d的所有路径,那么稳定度最高的路径Popt可以表示为

$Ρ_{o p t} = \arg \max_{p \in Π_{s, d}} ψ (Ρ) (4)$

由于自然对数(ln)严格遵循单调递增,可得

$Ρ_{o p t} = \arg \max_{p \in Π_{s, d}} \ln ψ (Ρ) (5)$

由式(3)和(5)进一步转化可得

$Ρ_{o p t} = \arg \min_{p \in Π_{s, d}} \sum_{e_{i} \in Ρ} - \ln (ψ (e_{i})) (6)$

将式(6)化简,每条边稳定度的权值可以表示为

w2(e)=-lnψ(e) (7)

根据以上的数学推导过程可以得出路径长度和路径稳定度的关系,即路径长度越短,其稳定度越高。

2.2 确定性的最优权值约束算法描述

通过上述算法,可以获取路径长度因子和路径稳定因子两个限制权值w1,w2。下面将通过本算法解决在两个权值限定的基础上获取最佳路径的问题,即为具有相同源节点和目的节点的路径寻找一条最优权值约束的路径。集合PATH(u)用来存储任意节点与节点u相关联并且满足权值w1的限制条件的非主导路径,而寻找一条最优权值约束的路径就是在集合PATH(dest)中挑选满足另一权值w2限制条件的非主导路径。

算法具体实现的伪代码如下所示:

1:for i=1 to |V(G)| do

2: PATH(i)←Φ

3:end for

4:PATH(src)←{src}

5:for i=1 to |V(G)| do //Note:W=(w1,w2)

6: for all(u,v)∈E(G) do //u and v are neighbors

7: for all p∈PATH(u) do

8: if(w1((u,v))+w1(p))≤C then

9: for all q∈PATH(v) do

10: if(W((u,v))+W(p)≤W(q)) then

11: delete q from path(v)

12: end if

13: r←p+(u,v)

14: if w1(r)≥w1(q) and w2(r)>w2(q) then

15: delete r

16: Ignore p

17: break

18: else

19: add r to PATH(V)

20: end if

21: end for

22: end if

23: end for

24: end for

25: end for

26:

27:if PATH(dest) is empty then

28: return NUL

29:end if

30:

31:Shortest_Path←First element of PATH(dest)

32:for all p∈PATH(dest) do

33: if W(p)≤W(Shortest_Path)then

34: Shortest_Path←p

35: end if

36:end for

37:return Shortest_Path

上述代码中:第1~4行是路径的初始化过程,该过程除了源节点src以外,其他任何节点的PATH集合都设置为空。第5~25行是构建满足约束条件的路径集合PATH,该集合中不仅包括从源节点src到目标节点的所有非主导路径,而且还包括用于计算非主导路径的其他路径。由此可知,从源节点src到任意节点n的多数非主导路径存储在集合PATH(n)中,而算法的第2个权值限制条件w2,主要为了在集合PATH(n)中寻找最佳路径(w2权值最小的路径也就是最短路径)。当节点n为dest节点时,寻找出来的最佳路径就是从源节点到目的节点的最佳路径,第27~37行为在集合PATH(n)中取最佳路径的过程。

3 基于QoS 的多路径路由协议描述

前面提出了一种路径长度和路径稳定度限制的路由算法,通过数学推导得出路径长度和路径稳定度的关系,并将QoS判定因子实例化到算法中。将算法应用于AODV[6]协议后,仅加入一个路径长度衡量标志就可确保从源节点到目的节点满足QoS要求的路径。但是单路径的路由协议在网络利用率和容错性上仍不能满足现有大流量数据传输业务的QoS需求,因此采用多路径的方式来克服单路径路由存在的缺陷。本节将对现有的AODV协议进行修改,从而提出一种基于QoS的节点不相交备份多路径路由协议MP-QAODV。

3.1 路径长度限制的路径稳定的路由算法

MP-QAODV协议对路由请求包RREQ和路由应答包都作了修改。RREQ包中添加了Distance Sign字段,该字段存储了节点通过配备GPS设备获取所处位置的坐标信息。源节点s到目的节点d的距离可以根据公式 $d i s = \sqrt{(d_{x} - s_{x})^{2} + (d_{y} - s_{y})^{2}}$ 得到,根据前面算法中路径长度和路径稳定度的关系,直接通过路径长度判断路径稳定度。

同时,RREQ又添加了1 bit的标志位“F”,该标志位主要用来区分路由发现阶段主路径的数据包(RREQ,RREP)和备选路径的数据包(RREQ_2,RREP_2),如图1所示。

3.2 MP-QAODV路由协议描述

3.2.1 路由发现过程

MP-QAODV源节点开始广播ID值为1的路由请求包RREQ到目的节点。当中间节点接收到RREQ包后,将把ID值以及有关源节点的路由信息保存在本地路由表中。目的节点将沿着反向路由将RREP包发送给源节点。

图1 MP-QAODV RREQ包格式和RREP包格式

中间节点收到RREP包后将对保存在路由表中的RREQ ID进行递增。协议通过递增RREQ ID值的过程确保备份路径不占用主路径中的任意一个节点。

当源节点接收到RREP包后,就完成了主路径建立的过程,这时源节点开始一边发送数据包一边广播RREQ_2包(RREQ ID值递增后为2)来寻找备用路径。其中RREQ_2是备份路径的路由请求包,它的标志位F设置为1。

当RREQ_2包传递到中间节点时,中间节点就在本地路由表中查询RREQ包的ID值与RREQ_2包进行比较。若相同,则丢弃该数据包;否则将转发该数据包。由于主路径在建立过程中都对各个节点路由表中的RREQ ID值进行了递增,所以如果RREQ_2 ID值与中间节点路由表中RREQ ID值相同,说明中间节点是主路径中的一个节点,这样协议在选择备用路径时将放弃该节点(MP-QAODV属于节点不相交的备用多路径路由协议)。

当RREQ_2包到达目的节点后,目的节点将沿着反向路由方向发送RREP_2(标志位F设置为1)包到源节点。源节点收到RREP_2包后,备份路径的建立过程完成。在整个备份路由发现过程中,路径中的节点将不会递增路由表中的RREQ ID值,但主路径节点路由表中的RREQ ID值必须递增。即在协议完成路由发现过程之后,主路径节点路由表中的RREQ ID值为3,而备份路径中的为2,总是要比备份路径的值大1。图2所示为MP-QAODV协议的流程图。

3.2.2 路由维护过程

MP-QAODV协议的路由维护过程存在两种情况:

1) 当主路径发生断裂[7]时,源节点会收到返回错误信息包RERR。同时备份路径将取代主路径来进行数据包的传输,而主路径将初始化并重新建立路由。主路径重新发起路由发现之前,需要将RREQ ID值在备份路径的基础上递增1个单位,由此来区分重新建立主路径和备份路径。

2)当备份路径发生断裂时,源节点仍然需要接收返回错误信息包RERR,为了判断该错误信息包是来自主路径还是备份路径问题,协议在源节点的本地路由表中增添了一个表项Route_flag。如图3所示,Route_flag值为0和1,分别代表主路径和备份路径。所以源节点收到RERR包后,通过核对路由表中的“Route_flag”表项来判断是主路径还是备份路径。

图3 源节点的本地路由表

备份路径重新建立过程只需要初始化源节点,同开始建立备份路由过程一样重新进行路由发现,这样备份路由中的RREQ ID值相比主路径的值仍然小于1,从而与主路径相区别。如图4所示,MP-QAODV协议路由维护过程流程图。

4 仿真评估

本文采用NS2仿真场景来衡量MP-QAODV,AOMDV和AODV协议的性能[8]。同时本文采用IEEE802.11 DCF(Distrbuted Coordination Function) MAC协议的CSMA/CA技术来传输分组数据;传输信道带宽设置为2 Mbit/s;无线信道范围为R=250 m。节点的移动模型采用双径地面反射模型(Two-ray Ground Reflection,TGR),在R=250 m的网络覆盖范围内,发送天线和接收天线的高度为1.5 m,收发天线的增益为1,最低接收功率3.65×10-10 W;节点的移动速度为[0 m/s,30 m/s],仿真时间为900 s。具体参数如表1所示。

本仿真场景主要对比节点移动状态下3种路由协议的性能,分别对比端到端时延、分组投递率、归一化路由开销和路由发现频率4个参数,测试场景具体参数如表2所示。

如图5所示,随着节点移动速度的增加,AODV,AOMDV和MP-QAODV三种路由协议的端到端平均时延也相应增加,这是由于节点的移动增大了路径失效的概率,从而数据分组不能有效传输到目的端,导致端到端的时延增加。对于多路径路由协议AOMDV和MP-QAODV来说,由于采用了备份路由机制,比单路径路由协议的路由发现次数要少,进而端到端的平均时延也要小于AODV。同时MP-QAODV引入了路径稳定性的路由算法,增强了网络路径的稳定性,路径的失效概率要小于AOMDV协议,因而其端到端的平均时延最小。

由图6可知,当节点接近静止时,3种协议的分组投递率非常相近,但随着移动速度的增加,它们的分组投递率都有所下降,其中AOMDV下降程度明显高于其他两种协议。这是因为AOMDV协议采用备份路由方式,即在所有路径都失效后才发起新的路由请求,并且分组数据在主路径传输时没有对备份路径进行有效的维护,从而很容易造成备份路径在启动前失效后主路径在路径间来回切换,最后导致丢失更多的数据分组。对于同样是多路径的MP-QAODV协议来说,因为它是基于AODV协议改进的,其备份路径的建立与主路径发送数据分组在同一过程并且该协议仅维护一条备份路径,不存在主路径和失效路径的频繁切换,因而分组投递率要高于AOMDV和AODV协议。

如图7所示,随着节点移动速度的增加,AODV,AOMDV和MP-QAODV三种路由协议的归一化路由开销也相应增加。AOMDV协议相对于其他两种协议的路由开销要大些,这是因为AOMDV在路由发现过程中建立了多条备份路径,在节点移动速度增加的时候,其备份路径失效的可能性增加,从而维护路由分组消息将大大增加,同时根据图6可知,AOMDV在较快的节点移动速度时分组投递率相对较低,从而导致AOMDV的归一化路由开销明显高于其他两种协议。对于多路径路由协议MP-QAODV,它仅仅维护一条备份路由协议,并且在AODV的基础上加入了路径稳定性算法,在移动速度增加情况下路径失效的可能性大大减少,同时相对于AODV协议,它的控制分组数明显要小一些,再加上相对较高的分组投递率,因而MP-QAODV的归一化路由开销要小一些。

由图8可知,AODV,AOMDV和MP-QAODV三种协议的路由发现频率随着节点移动速度的增加而增加。对于多路径路由协议AOMDV和MP-QAODV,一次路由发现会找到多条路径,所以路由发现频率相对于单路径路由协议AODV要明显低很多。同时,与AOMDV在路由发现阶段选择多条备份路径相比, MP-QAODV仅选择一条备份路径,因而MP-QAODV的路由发现频率略高于AOMDV。

仿真结果表明,随着节点移动速度的变化,AODV,AOMDV和MP-QAODV三种路由协议端到端的平均时延、分组投递率、归一化路由开销以及路由发现频率都有相应的变化。同时由以上分析可知,MP-QAODV协议在端到端的平均时延、分组投递率以及归一化路由开销所表

现出来的网络性能要优于其他两种协议。尽管在路由发现频率上略高于AOMDV协议,但是并不影响其整体的网络性能。

5 结束语

本文针对当前移动Ad Hoc网络不能有效满足大流量业务情况,提出了一种基于QoS保障的多路径路由协议(MP-QAODV),该协议采用路径长度限制的路径稳定的路由算法,其平均端到端时延、分组投递率以及归一化路由开销3项性能指标都优于AODV和AOMDV协议,仅在路由发现频率上略高于AOMDV协议。因此,下一步的主要工作是研究如何降低该协议的路由发现频率,从而达到更好的网络性能。

摘要：针对现有移动Ad Hoc网在大流量业务下无法提供高质量QoS保障的问题,通过推导证明提出了路径长度限制的路径稳定的约束关系,进而将QoS的判定因子引入一种确定性的最优权值约束路由算法进行实例化,并在该路由算法的基础上提出了基于QoS保障的多路径路由协议(MP-QAODV)。通过仿真,验证了MP-QAODV协议在平均端到端时延、端到端数据分组投递率、归一化路由开销等方面优于AODV和AOMDV协议。

关键词：移动Ad Hoc,QoS保障,多路径路由协议,MP-QAODV

参考文献

[1]JOHNSON D B,MALTZ D A.Dynamic source routing in Ad Hoc wirelessnetworks[M]//IMIELINSKI T,KORTH H F.Mobile Computing:TheKluwer International Series in Engineering and Computer Science.[S.l.]:Springer US,1996:153-181.

[2]MUELLER S,TSANG R P,OHOSAL D.Multipath muting in mobile AdHoc networks:issues and challenges[EB/OL].[2012-05-05].http://alumni.cs.ucr.edu/～ibasaran/research/Multipath%20Routing%20in%20Mobile%20Ad%20Hoc%20Networks%20Issues%20and%20Challenges.pdf.

[3]SHENG M,LI J D,SHI Y.Routing protocol with QoS guarantees for ad-hoc network[J].Electronics Letters,2003,9(1):143-145.

[4]JULIAN D,CHIANG M.QoS and fairness constrained convex optimiza-tion of resource allocation for wireless cellular and Ad Hoc networks[C]//Proc.21st Almual Joint Conf.IEEE Computer and Communica-tions Societies.[S.l.]:IEEE Press,2002:477-486.

[5]WU K,HARMS J.Multipath routing for mobile ad hoc networks[J].Journal Of Communications And Networks,2002,4(1):48-58.

[6]RFC3561,Ad Hoc on-demand distance vector(AODV)routing[S].2003.

[7]魏明磊,王浩,李云,等.基于DSR路由协议的无线Ad hoc网络实验[J].重庆邮电大学学报:自然科学版,2005,17(6):714-717.

多路径路由研究论文篇7

无线传感器网络是继个人计算机、计算机网络和无线通信技术之后的IT技术第4次革命, 其低布局和低维护成本、更换升级的便易性、无需任何电缆连接的可自由移动性和物机交互的灵活性都满足了物联网要求的遍及性, 极大地促进了物联网的发展与普及, 将对21世纪人类的生活产生重大的影响。

1无线传感器网络

无线传感器网络是由部署在检测区域内的大量微型传感器节点通过无线通信形成的一个多跳自组织网络系统, 目的是协作感知、采集和处理网络覆盖区域被检测对象的信息, 并发送给观察者。无线传感器网络主要特点包括大规模、自组织、多跳路由、动态网络、可靠网、以数据为中心和应用相关性等。与传统网络不同, 无线传感器网络的应用因其使用环境和软硬件特点原因而具有不少约束, 主要约束包括:①传感器节点携带的电池能量有限;②无线通信能力有限;③传感器节点的计算和存储能力有限。

针对无线传感器网络的以上特点和约束, 其相关的技术研究主要集中在组网理论、路由算法、接入控制和安全管理等几个方面, 其中路由算法的研究目的主要是如何高效使用能量来最大化网络生命周期、提高WSN的无线通信能力、利用有限的资源完成更多的协同任务。近年来研究人员对不同应用领域的传感器网络提出了各种不同的路由协议, 比较经典的路由协议有:基于聚簇LEACH 协议、TEEN协议、PEGASIS协议;以数据为中心的SPIN 协议、DD (Directed DiffusiON) 协议、GBR (gradient based routing) 协议、Rumor 协议;基于地理位置的GPSR 协议、GEM (Graph Embedding) 协议;基于能量感知的EAR (energy aware routing) 协议;基于QoS 的SAR协议和SPEED协议等。

无线传感器网络路由协议的基本目的都是解决能耗问题和最大化网络生命周期, 但大部分路由协议都采用的单路径路由, 能导致某一路径或者区域过热, 节点提前死亡, 从而缩短网络寿命。而全局能耗平衡方法虽然能有效降低不同路径或者区域之间的能耗差异, 但由于没有考虑路径或者区域内各节点之间的能耗平衡, 同样缩短了网络寿命。因此, WSN路由研究应该进一步强调路由的多路径、数据传输效率、QoS和路由安全等方面技术。本文针对这个目的提出了一种基于事件的多路径能耗均衡路由算法, 并对该算法中的类间最佳路径选择方法进行了描述和证明。

2基于事件的分类多路径能耗均衡路由算法

假定无线路由器网络中唯一的基站位于网络外较远位置, 事件相关的传感器节点都分布在以该事件源为中心的范围内, 类内部所有节点都能感知同一个事件源, 且类内各节点感知并转发自身测量数据的能耗近似相等。

本路由算法是以网络寿命为指标同时实现局部和全局能耗平衡的分级能耗平衡方法, 具体步骤如下。

(1) 组建类。

将同一事件感知相关的所有传感器节点组织成一个类。若有h个事件源由休眠转为活动, 则在这h个区域中传感器节点分别形成了以事件源H为中心的h个类, 以同心圆为等值线, 类中的节点按检测值逐级递减由内往外分布 (见图1) 。

(2) 选择类首领。

某事件区域中的传感器节点向其邻居广播其测量值, 各节点比较接收到的测量值和其自身测量值, 将大于自身测量值的邻居节点放入自己的父母辈列表, 将小于自身测量值的邻居节点放入自己的子女列表, 测量值相似则放入兄弟列表。父母辈列表为空而子女列表非空的节点为候选类首领;其子女列表为空的节点为类边沿节点;其父母辈列表和子女列表都非空的节点为中继节点。若有多个候选类首领, 则指定一个与类内所有其他节点平均距离较小的候选类首领为正式类首领, 否则直接定为正式类首领。正式类首领告知其子女列表中的所有传感器节点和所有其它的候选类首领最终的类首领选举结果, 以便这些传感器节点把测量值转发给同一聚合节点。

(3) 建立类内多路径。

为了平衡类内等值线上兄弟节点之间的能耗并减少能耗平衡的控制开销, 采用多路径传输。仅有一个父母辈的子节点为单亲子节点, 来自单亲子节点的输入链路为必选输入链路;拥有多个父母辈节点的子节点为多亲子节点, 来自多亲子节点的输入链路为可选输入链路;每个多亲子节点统计其各个父母辈节点当前的必选输入链路数, 选择当前输入链路数最小的父母辈节点为其下一跳中继节点, 并将其输入链路数加1。当相邻传输路径存在较大的能耗差异时, 可以使高能耗路径中的多亲子节点尽可能通过可选输入链路输出部分数据到低能耗路径, 从而实现类内路径间的动态能耗平衡。同时本方法还采用单跳和多跳相结合的混合传输模式降低节点间的能耗差异。

(4) 建立类之间的多路径。

为了降低类之间路径与其他类内路径的能耗差, 类间路径采用弧线形以切割更多的类内径向路径, 将类之间路径的能耗分摊到各条类内路径, 在类内路径中采用混合传输技术尽量减少类内路径和类间路径的交叉节点数据负荷差异, 从而实现被切割的类内路径中各节点的能耗平衡。

(5) 基站选择类间传输最佳路径。

假设类首领的残余能量表示该类节点的平均残余能量, 当每个类与邻居类建立类间路径之后, 类首领将本类的标识、邻居类标识和自身的残余能量报告给基站, 基站根据这些信息推导出以各个类首领为源节点以基站为目的节点的多条传输路径, 从多条传输路径中选择寿命最长的路径作为该类的最佳传输路径, 从而较好地实现了基于多径的类间能耗平衡。

3类间传输的路由选择

下面描述和证明基类在类间多路径中的选择最佳路径的方法。

定义1 路径寿命是该路径包含的所有节点残余能量的最小值。

设P (l) 为某一传输路径, 通过在该传输路径上增加节点可形成原路径的扩展路径EP (l) 。基站接收到所有类的自身标识、邻居类标识和类残余能量级之后, 理论上需计算以各个类首领为源节点以基站为目的节点几乎所有可能的路径。为了减少计算复杂性, 采用先计算靠近基站的内层类的最佳传输路径, 再以这些路径为基础, 进行路径扩展的原则, 逐步生成全网所有类的最佳传输路径。

定义2 第一层类是指与基站直接相邻的类, 第二层类是指与第一层类直接相邻而与基站不直接相邻的类, 依此类推第n (n>2) 层类是指与第n-1 (n>2) 层类直接相邻而与任何第m (0

定义3 设第n层共有m个类, 其中某个类最佳传输路径寿命在第n层类中第k长 (0

定义4 第n层中与第n-1 (n>1) 层第k优先类直接相邻而与任何第n-1层第j (0

定义5 设第n+1层邻k类为nd (n+1, k) , 第n+1层第 k优先类为rnd (n+1, k) 。第n+1层邻k类与第n层第k优先类最佳传输路径Pn, k组成的扩展路径称为第n+1层邻k连续扩展路径记为CEPn+1, k=nd (n+1, k) JHJPn, k;第n+1层邻k类跨越若干类与第n层第j优先类最佳传输路径Pn, j组成的扩展路径称为第n+1层邻k第j优先分离扩展路径记为nd (n+1, k) ～Pn, j;第n+1层邻k类跨越若干类与第n+1层邻j连续扩展路径CEPn+1, j组成的扩展路径称为第n+1层邻k邻j分离扩展路径记为nd (n+1, k) ～CEPn+1, j。

为了便于比较源于同一节点的各路径的寿命, 我们定义不包含源节点的路径寿命为该路径的纯寿命。设P (l) 为某一传输路径, 则该路径的纯寿命记为PLfP (l) 。以下是证明第2层的邻1类选择第1层第1优先类作为下一跳宏节点时其传输路径为最佳。

证明:设第1层共有m个类, 其中第1优先类最佳传输路径寿命为该类的残余能量Ernd (1, 1) , 其他类的最佳传输路径寿命为相应类的残余能量Ernd (1, k) (0

根据第k优先类的定义有

undefined

即第2层邻1类选择第1层第1优先类作为下一跳宏节点时其传输路径最佳。

证毕。

设第二层包含q个类, 同理第二层邻2连续扩展路径的纯寿命不短于邻2第k (2

undefined

(1) 如果Ernd (1, 2) ≥Lfnd (2, 1) JHJrnd (1, 1) (7)

则PLfnd (2, 2) JHJrnd (1, 2) =Ernd (1, 2) ≥Lfnd (2, 1) JHJrnd (1, 1) ≥PLfnd (2, 2) ～nd (2, 1) JHJrnd (1, 1) , 即第2层邻2连续扩展路径更佳。

(2) 如果Ernd (1, 2)

在第2层邻2类和邻1类之间寻找一条路径, 该路径记为nd (2, 2) ～nd (2, 1) 。如果存在一条路径nd (2, 2) ～nd (2, 1) , 使得

undefined

由于undefined

即第2层邻2邻1分离扩展路径更佳。

反之如果对于所有的路径nd (2, 2) ～nd (2, 1) , 存在如下的不等式:

undefined

则undefined

即第2层邻2连续扩展路径更佳。

为了降低寻找邻2类和邻1类之间合适路径的复杂性, 可以限定该路径的长度。

同理对于第2层邻k类, 我们根据第2层邻k连续扩展路径和邻k邻j (0

4性能分析

无线传感器网络的基于事件的分类多路径能耗均衡路由算法, 是通过采用单跳和多跳传输相结合的混合传输模式、相邻路径间的数据转发以及在多条类间路径中选择高残余能量路径等技术, 有效地降低类内节点间能耗差异, 实现了类内多路径和类间多路径间的能耗均衡, 从而延长了网络寿命, 具有很好的可用性和实用性。

5结束语

应用在不同领域的无线传感器网络的各种路由技术针对性地解决了一些实际问题, 虽然都考虑了网络能耗均衡和网络寿命问题, 但还有不足之处, 参考某些经典路由技术的特点, 本文提出了一种基于事件的分类多路径能耗均衡路由算法, 描述该算法的步骤, 证明了基地选择类间最佳传输路径的方法的可行性。但是本路由算法在节点移动、QoS和路由安全方面还不能满足实际应用的需求, 因此还需要不断完善。

摘要：无线传感器网络的广泛应用使其路由技术成为当今研究界的研究热点。介绍了无线传感器网络的特点和典型路由技术及其存在的问题, 提出了基于事件的分类多路径能耗均衡路由算法, 简单描述了该算法的步骤, 分析并证明了该算法中对类间最佳路径选择的方法。

关键词：无线传感器网络,分类,多路径,能耗均衡,路由算法

参考文献

[1]杨海波, 唐颖, 姚庆栋.分级能耗平衡法[J].浙江大学学报, 2008 (3) .

[2]王志良, 粉花.物联网工程概论[M].北京:机械工业出版社, 2011.

[3]杨海波, 邱宁, 陈友荣.无线传感器网络动态秘钥管理方案[J].传感技术学报, 2008 (9) .

[4]崔逊学, 左从菊.无线传感器网络简明教程[M].北京:清华大学出版社, 2009.

[5]李建中, 高宏.无线传感器网络的研究进展[J].计算机研究与发展, 2008 (9) .

多路径路由研究论文篇8

近些年来,互联网得到迅猛的发展,中国网民规模已经突破4.2亿[1],然而,作为其基础支持的路由系统却面临着极大的挑战。路由条目急剧增加,严重地消耗了路由器的计算资源,同时网络阻塞、拥挤、攻击等也会引起网络的失效或不稳定, 它们都在很大程度上影响互联网的性能。

一体化网络网[2]的提出,可以有效地解决上述问题。一体化网络是一种新的基于身份位置分离思想的网络体系架。一体化网络体系模型与理论提出接入标识、交换路由标识及其映射理论,建立广义交换路由的概念与机制,在支持安全和移动的基础上实现网络一体化。

延续一体化网络的设计思想,本文实现了一种基于路径标识的多路径域间路由方案。

1 研究背景

针对核心网域间路由,传统网络主要存在可扩展性和可靠性两方面的问题。路由可扩展性[3]主要关注于转发表(FIB)的大小和路由更新的频率。网络用户的剧增、流量工程、策略路由等技术的应用,导致路由前缀不可聚合,使得路由条目呈非线性增长,是限制路由可扩展性的主要原因;路由可靠性[4]主要关注于网络拓扑改变时,路由协议能否快速收敛,提供持续通信的能力。现有域间路由协议BGP只提供一条最佳路由,在路径失效时,需要等待下次收敛才能继续通信,而且域间路由更新的频率十分高,使得收敛时间长达几分钟至十几分钟,是降低路由可靠性的几点原因。

针对上述两个问题,在一体化网络中采用了域内与域间路由相分离,核心网和接入网路由相分离的多路径域间路由方案。核心网域内采用本地标识进行路由,域间采用自治域号(AS)进行路由,保证路由条目的稳定和缓慢增长,提高了路由可扩展性。同时域间路由引入路径标识(PID)标识多条转发路径,在原先的路径失效时可以快速地切换到其他路径,保证了路由的可靠性。

2 基于路径标识的多路径域间路由方案的设计

多路径路域间路由方案主要分为控制层和转发层两部分,其中控制层基于目前经典的域间路由协议(BGP),主要实现路由的发现、通告和更新。转发层基于Linux内核协议栈,主要实现通告路由的数据包封装解封和转发以及链路失效时的快速收敛。

2.1 控制层的设计

边界网关路由协议(BGP)[5]是目前主流的域间路由协议,它是一种路径向量协议,在AS之间传递网络可达性,并且可以通过检查AS_PATH属性来避免环路。多路径路由方案在域间采用AS号路由,为了标识多条路径引入了路径标识(PID)和下一跳路径标识(NEXT_PID),从而可以在AS之间通告多条路径。其中PID为从源AS到目的AS之间顺次经过的所有AS号的哈希值,而NEXT_PID为此路径下一跳AS到目的AS之间所有AS号的哈希值。

基于图1的拓扑图,分析AS 100和AS 200之间传递的UPDATE包的NRLI信息,其基本通信流程为:

(1) 首先AS100和AS 200分别计算本地的AS号生成本地路由信息,并且在建立邻居关系以后直接发送给对等体路由器。如AS 100就将〈100,HASH(100),HASH(100)〉发送给AS 200。

(2) AS 100和AS200在收到AS 300通告的路由后,会在邻居关系建立后,将收到AS 300的路由的PID替换为NEXT_PID,将本地AS号加入路径属性中,重新计算PID,然后传递给对等体路由器。如AS 100将〈300,HASH(100,300),HASH(300)〉发送给AS 200。

(3) 在下次通告时,AS100和AS 200获得了到达对端路由器的信息,及时地通告给对等体路由器,如AS 100将〈200,HASH(100,300,200)〉发送给AS 200,这时AS 200就知道了两条可以到达AS 200的路径,实现了简单的多路径。

2.2 转发层的设计

目前的路由器基本都运行在Linux系统中。因为Linux内核[6]提供了完善的网络功能,本方案也是基于Linux内核协议栈。Linux内核协议栈是指网络中各层协议的总和,从上到下依次为应用层、传输层、网络层和网络接口层。其中网络层负责处理网络中的数据包,包括数据包路径的查找、转发、接收等工作。多路径域间路由方案的数据包头主要由传统数据包头和PID、AS号和Local Identifier组成。其中PID和AS号字段用于域间路由使用,Local Identifier用于域内路由使用。

多路径域间路由数据包转发的示意图如图2所示。

收到数据包需要按如下步骤进行转发:

(1) 检查PID字段是否为空,如果为空,则匹配AS号,根据匹配项填充PID字段,根据查询到的PID进行平面查找内核路由表,并将数据包转发到相应的端口上。

(2) 如果PID字段不为空,则用平面查找方式匹配PID,如果有匹配项,路由器根据匹配项转发到对应端口;如果没有匹配的PID,再根据标志位,置位的路由器可以按匹配目的AS号的方法对数据包进行转发,没有置位的则将数据包丢弃。

(3) 当数据包跨出本AS域转发到下一个AS域时,PID字段需替换成路由条目中NEXT_PID;当PID为本地AS的哈希值时,表明数据包此时已经到达目的AS,此时需交由域内路由协议用Destination Local Identier进行转发。

3 基于路径标识的多路径域间路由方案的实现

多路径域间路由方案实现模块图如图3所示,其中控制层模块主要实现UPDATE消息的产生、交互和处理,并且提供了一些配置和显示命令。在多路径域间路由方案中只需要修改NLRI模块、UPDATE消息处理模块、平面路由表模块和配置、显示命令模块,其他部分可以沿用BGP的设计。RTM模块主要实现控制层和转发层之间的交互,原始数据包的提交和路由信息的下发。转发层模块实现平面转发表的构建、数据包的封装和解封,以及具体的数据包转发流程。

3.1 NRLI模块

该模块主要实现在AS之间传递路由可达消息。在BGP中被设计成〈长度,前缀〉二元组,为了兼容多路径域间路由方案,需要修改成〈长度,前缀,PID,AS〉四元组,使之既可以满足多路径域间路由的需要,也可以兼容现有的路由方式。

3.2 UPDATE消息处理模块

该模块主要实现UPDATE消息的发送和接收。在BGP当中用来在对等体之间传递可用路由前缀、撤销路由等,在多路径域间方案中需要修改数据包发送函数和接收函数,使之能够正常地传递新的网络可达性信息,同时需要修改包安全性检查等函数,使之能够不被错误地丢弃。

3.3 平面路由表模块

该模块主要实现在控制层维护核心路由表,并向转发层下发最佳转发信息。BGP的路由表是基于最长前缀匹配的方式查找的,用二叉树具体组织。在多路径域间路由方案中需要将其平面化,利用PID和AS号来检索域间路由,利用HASH算法将路由节点信息存储在一个双向链表上面,实行了精确查找。

3.4 配置、显示和调试命令模块

该模块主要实现多路径域间路由协议的配置,并且提供了一些显示核心路由表、对等体状态等的显示命令,还有一些路由器故障时的调试命令。相对于BGP,在多路径域间路由方案中添加了以下的命令:

(1) 路由显示命令

通过该命令可以遍历多路径域间路由协议的核心路由表,显示具体路由信息,即到目的AS的具体路由信息,包括PID、NEXT_PID和具体路径显示。

(2) 路径选择命令

因为在多路径路由方案中,在控制层可以发现多条路径,通过该命令可以选择控制层向转发层通告的最佳路径,在当前链路失效时选择备份路径下达到转发层,实现链路的快速收敛,最终完成了转发路径的可控。

3.5 RTM模块

该模块主要实现转发层模块和控制层模块之间的消息交互。多路径域间路由协议在控制层拥有自己的核心路由表,但最终对转发其作用的是转发层的内核路由表,但是控制层不能对内核路由表直接起作用,该模块实现了两者之间的信息交互。它们之间的通信是通过套接字NETLINK起作用的,在公共消息格式中添加标识路由所需的PID、AS号和NEXT_PID等信息,满足标识路由在转发层的需要。

3.6 平面转发表模块

该模块主要实现多路径域间路由在转发层核心路由表的维护,当需要出路网络流量的发送和接收时查询该路由表。

Linux内核的转发表是基于网络掩码的HASH表组织的,根据不同的网络掩码长度被组织成不同的HASH表。因为IPv4使用32位地址,所以IPv4中有33个不同的网络掩码长度,可对应于一个IP地址。fib_table数据结构来描述路由表。fib_table结构包含一个由33个指针组成的向量,每个指针对应一个网络掩码并指向一个类型为fn_zone的数据结构。Fn_zone结构将路由组织成HASH表,因此通向目的网络的路由,如果网络掩码长度相同,就被放在同一个HASH表内。每个单独的子网对应一个fib_node实例,用变量fn_key(网络掩码)识别,它的值就表明该子网。在查找函数fn_hash_lookup中,也是通过遍历路由表搜索关键词fn_key,获得最终结果。

多路径路由方案中,转发时需要检查PID,并根据PID进行检索和转发,因此需要修改转发表,使之可以根据关键词PID进行查找。在查找时,只需要根据PID进行精确匹配,而不用计算网络掩码。在修改后的路由节点fib_bgp_node中,添加了PID的信息,使得修改后的路由表fib_bgp_table可以根据PID为关键词索引。路由表结构如图4所示。

3.7 数据包封装解封模块

该模块主要实现数据包中标识的转换,Linux内核中采用IP地址进行路由,而在多路径域间路由方案中,在域间有需要才用AS号路由,因此需要在发送数据包时,添加PID、目的AS号和源AS号等信息,但为了兼容现有的网络架构,方便现有网络其他服务的处理,在数据包进入网络层前,去除PID、目的AS号、源AS号等扩展选项。只是在数据包离开网络层后,才增减以上扩展选项。修改后的数据包头如图5所示。

3.8 数据包转发处理模块

该模块主要实现基于PID的数据包转发,同时维护一个PID、AS号和NEXT_PID一一对应的查询表,实现到目的AS路径标识PID的填充。Linux内核是基于IP地址前缀路由的,而在多路径域间路由方案中是基于AS号,在查询平面转发表要使用PID,如果数据包是终端第一次经过路由器时,不存在PID等信息,需要根据目的AS号添加PID等信息,还有域内路由时根据设计要使用Local Identifier,只有在数据包进入Linux内核网络层前,进行了该模块处理,才能完成标识路由的功能。

4 基于路径标识的多路径域间路由方案的功能验证

多路径域间路由方案的功能验证,主要包括控制层基于路径标识的多路径路由发现和转发层基于路径标识的数据包正常转发。

4.1 测试平台及拓扑

全部系统采用普通的x86系列的PC;测试环境的核心网路由器配置至少两个以上的网卡,无线或有线均可;所有充当路由器都应该安装Linux操作系统,内核版本为2.6.28;测试的拓扑如图6所示,对各个功能实体进行地址和路由配置,在所有路由器都需要安装文中提到的修改后的BGP路由软件和相应的内核软件。

4.2 控制层基于路径标识的多路径路由发现

AR1为AS号为100的一台路由器,AR2,AR3分别为AS号为200,300的路由器,其中AR1的BGP配置如图7所示。

其他路由器配置与AR1类似,通过配置使得AR1,AR2,AR3之间建立了EBGP关系对等体关系,通过show ip bgp命令查看AR1的路由表,内容如图8所示。

AR1学习到了到达3个AS域的路由信息,学习到了到本地AS域100的路由,其中PID和NEXT_PID一致,并且默认权重为32 768;到达AS域300的路径则有两条,分别为“300 i”和“200 300 i”,表明到达AS域300的路径可以是直接到达AS域300,PID为f78aac78,NEXT_PID为809d3a90,也可以是通过AS域200到达AS域300,PID为7a5f1fe8,NEXT_PID为33f960c4,可见PID和NEXT_PID均不一致,可以通过PID和NEXT_PID区分不同的路径,通过测试,可以看出本方案在控制层可以正确地发现基于路径标识的多条路径。

4.3 转发层基于路径标识的数据包正常转发

基于路径标识的数据包转发是多路径域间路由的重要功能,首先用AR1向AR2发送ping包,也就是AS域100向AS域200发送ping包,在AS 200的内核编写打印语句,打印出数据包添加的PID,NEXT_PID和AS号,结果如图9所示。

可见,在ping包已经正确地添加了域间路由所需的PID,NEXT_PID和AS号等信息。利用wireshark抓包工具进行测试,可以成功地获取icmp包,证明两个AS域之间可以实现基于路径标识的数据包转发。

5 结语

在实际搭建的拓扑中,实现了基于路径标识的多路径路由方案,并且进行了功能验证。结果表明,可以正确地发现多路径路由,并且可以实现基于路径标识PID的数据包转发。本文实现了基于路径标识的多路径域间路由方案,快速实现链路失效时的重新收敛,将成为下一步研究的重点。

参考文献

[1]FULLER V.Scaling issues with routing+multihoming[C].[S.l.]:Plenary session at APRICOT,the AsiaPacifcRegional Internet Conference on OperationalTechnologies,2007.

[2]张宏科,苏伟.新网络体系基础研究:一体化网络与普适服务[J].电子学报,2007,35(4):593-598.

[3]MEYER D,ZHANG L,FALL K.Report from the IABworkshop on routing and addressing.IETF RFC 4984[EB/OL].[2007-09-21].http://www.ietf.org/rfc/rfc4984.txt.

[4]CAESAR M,SUBRAMANIAN L,KATZ R H.Rootcause analysis of internet routing dynamics.Technical Re-port UCB/CSD-04-1302[R].U.C.Berkeley:Departmentof Computer Science,2003.

[5]REKHTER Y,LI T,HARES S.A border gateway proto-col 4(BGP-4).IETF RFC4271[EB/OL].[2006-01-16].http://www.ietf.org/rfc/rfc4271.txt.

[6]BENVENUTI Christian.深入理解Linux网络技术内幕[M].夏安,译.北京:中国电力出版社,2009.

[7]郭华明.标识路由关键技术研究[D].北京:北京交通大学,2010.

[8]王立平,崔智林,马力.基于OPNET仿真平台的MANET路由协议性能分析[J].现代电子技术,2011,34(14):71-74.

多路径路由研究论文篇9

一、域间多路径路由协议

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协议, 从而使用户可以发现路由。

三、结束语

【多路径路由研究论文】推荐阅读：

可靠多路径路由09-03

多约束QoS组播路由05-16

多路径算法06-09

多路径传输07-09