多路径路由范文

2024-05-20

多路径路由范文（精选7篇）

多路径路由第1篇

移动Ad Hoc网络是由具有无线通信能力的移动节点组成的, 是一种不需要依靠现有固定通信网络基础设施的, 能够迅速展开使用的网络体系, 是没有任何中心实体的自组织、自愈合的网络。其中每个节点既可作为主机也可作为路由器使用, 由于其移动接点具有路由功能, 可以通过无线连接构成任意的网络拓扑, 因此路由协议的选择对Ad Hoc网络十分重要。

AODV是目前常用的无线多跳Ad Hoc网络路径选择协议。它是在主动式路由协议基础上, 结合按需路由机制进行改进后提出的。该协议采用逐跳转发分组方式, 并且加入了组播路由协议扩展, 还支持QoS的功能, 从而有效地节省了网络资源, 基本上适合网络呈拓扑结构变化的Ad Hoc网络数据传输的要求。但是, 由于该协议对每一目标节点仅仅只保存一条路径, 所以如果路径中某个连接由于各种原因发生中断, 源节点就不得不重新开启路径发现去寻找新的路径, 而重新进行路径发现的开销对拓扑结构动态变化的Ad Hoc网络来说是巨大的。

1 AODV协议的算法描述

AODV协议使用了路径发现和路径维护的基本请求机制, 在没有路径需求时去发现路径, 在路径存在时去维护路径, 从而降低形成路由的总体开销。

1.1 路由建立过程

当节点要发送数据的时候先查找路由表, 如果有到目的节点的路径, 则按路由表的下一跳转发。若没有可用路径, 则源节点向邻节点广播RREQ, 收到非重复RREQ的节点建立或更新逆向路由后再把RREQ广播出去, 直到目的节点或是有到目的节点有效路由的中间节点收到RREQ后沿着逆向路径回复一个RREP到源节点。当RREP沿着逆向路径回传时建立前向路由条目, 这样源节点收到RREP时, 从源到目的节点的路由就建立了。

1.2 路由维护过程

路由维护是指源节点通过检测网络拓扑结构是否发生变化, 从而决定已经存在的路由是否可用。当检测到路由中断时, 就发送路由错误包RERR (Route Error) , 用来告知源节点路由中断的情况。在路由发现和路由维护时, 每个节点会根据所接收到的控制包和数据包中所有在当前网络拓扑结构下的路径信息来更新路由表。其路由表由当前节点到其他节点的路径项组成, 每个路径项列出了目的节点, 从该节点出发到达目的节点的下一节点、路径序列号, 以及到达目的节点还剩的跳数。并且对于每个目的节点仅仅维护一条从节点出发的路径, 对于每一条路径赋予一生存时间, 超过这一时间限制, 该路径就不再有效。

2 改进后AODV 路由协议的算法描述

2.1 协议改进的基本思想

针对AODV 路由协议在这一方面存在的不足, 提出了一种基于AODV的多路径路由协议M-RTAODV, 其基本思想为:源节点和目的节点间建立多条路径, 并依据链路负载以及跳数综合计算决定这些路径的优先级;当源节点发送数据时, 选择具有较高优先级的路径进行通信;当主路由 (即优先级最高的路由) 中断时, 选择次高优先级的路由通信。由于源节点和目的节点间存在多条路径, 当主路由中断时, 能选择次优路径通信, 减少了重找路由的开销;同时, M-RTAODV选路时考虑了路由已承载的业务量, 能有效避免网络拥塞, 一定程度地缓解了网络拥塞程度。

2.2 AODV协议改进的关键技术

2.2.1 主路由的选择

Ad Hoc网络中, 当源节点要发送包到目标节点的时候, 如果在自己的路由缓存中没有找到这个目标的路由, 那么该节点就会发送RREQ分组启动路由发现过程。M-RTAODV协议在路由发现过程中, 并不像传统的AODV协议那样只找到一条到目标的路径, 就丢弃其它的路由信息。而是保存源节点和目的节点间的多条路径, 其中一条为主路径, 其余为备份路径, 主路径和备份路径依据优先级高低区分。主路径优先级最高, 值为1, 第一备份路径优先级次之, 值为2, 以此类推。优先级高低根据路径已用带宽和总跳数来决定。在改进算法中, 并不是一味地保存所有路径, 源节点和目的节点间建立的路径数量最多为N。主路由选择过程如下所述:

(1) 根据路由带宽和跳数计算路由偏好值根据如下公式为每条路由计算偏好值Yi。其中, BWUsedi表示第i条路由所用带宽;hopi表示该路径总跳数。MAX (BWUsedi) 表示N条路径中所有已用带宽的最大值, MAX (hopi) 表示所有跳数的最大值, a 和b分别表示带宽和跳数在选择路由时的权重系数:

$Y_{i} = a \times \frac{B W U s e d_{i}}{Μ A X (B W U s e d_{i})} + b \times \frac{h o p_{i}}{Μ A X (h o p_{i})}$

其中, $i \in (1, 2 \dots, Ν) ‚ a + b = 1$ 。

(2) 依据Yi确定路由优先级根据Yi按从小到大排序, Yi值越小表明该条路由越优, 因此, Yi值最小的路由即为主路由, 其他备份路由的优先级也按该方法依次排出。

2.2.2 目的节点的缓存机制

为有效对比源和目的节点间的多条路由, M-RTAODV协议修改了原AODV的路由机制, 即在协议中取消了中间节点回复RREQ的功能, 同时在目的节点处添加RREQ缓存。当目的节点收到第一个RREQ时, 启动RREQ缓存定时器, 在其后一段时间内缓存收到的所有RREQ;当定时器超时, 比较RREQ携带的路径信息, 根据主路由选择机制为每条路径附上优先级, 并发送RREP回复每条路由, 这样, 当源节点收到所有的RREP后, 源节点和目的节点间将建立好按优先级排序的多条路由。缓存的RREQ数目最多限制为N, 即仅保存最优的N条路由。

2.2.3 路径承载带宽计算方法

带宽是Ad Hoc研究中的热点问题, 如何更有效地反映带宽, 在很多文献中有详尽的讨论。在多路径路由中, 无线环境的信号不确定性以及路由的不确定性, 导致带宽更难计算, 文中采用了一种较粗略的方法:为每个通信流都附上流标号 (flowid) , 每个节点都保存当前已承载的业务数myflowcnt。比如, 节点S当前没有承载任何业务, 其myflowcnt为0;当该节点需要发送数据时, 其myflowcnt加1。

2.3 改进后协议的工作过程

完整的路由协议包括路由建立、路由维护以及路由中断后的处理三个部分, 以下将分别阐述。

2.3.1 路由建立过程

(1) 源节点有数据发送时, 查找自己的路由表, 如果当前没有到目的节点的路径, 则发送RREQ查找路由;源节点发送RREQ前, 需要计算当前自己承载的数据量, 并存储于发送的RREQ中。

(2) RREQ中携带所经过路径的负载情况bwuesd, 中间节点收到RREQ时, 比较当前节点已承载业务数myflowcnt和bwuesd, 将两者的较大值存储于RREQ中再转发。

(3) 为比较源节点和目的节点间的多条路径, 在改进的AODV中, 取消中间节点回复RREP的机制。即便中间节点有到目的节点的路由也不回复RREP, 由目的节点统一回复。

(4) 目的节点收到第一个RREQ时, 将启动RREQ缓存定时器, 缓存其后一段时间内收到的来自同一源节点的所有RREQ。

(5) 目的节点缓存的RREQ定时器超时, 将根据主路由选择机制计算每个RREQ对应路径的优先级, 并根据优先级高低依次回复RREP。RREP中携带对应路由的优先级rt_pri和流标识 (flowid) 。

(6) 中间节点收到目的节点回复的RREP, 将建立到目的节点的路由, 并记录RREP中携带的路径优先级rt_pri和流标识 (flowid) , 同时将本节点的承载业务数myflowcnt加1。

(7) 源节点收到目的节点回复的RREP, 建立到目的节点的路由, 并记录路径优先级;当源节点收到目的节点回复的所有RREP时, 建路过程结束。

自此, 源节点和目的节点已建立好带有优先级的多条备份路由。建路成功后, 源节点选择优先级最高的路径发送数据。

2.3.2 路径维护过程

M-RTAODV协议的主路由以及备份路由的维护与AODV原有机制基本类似。为了维护路由, 及时发现因节点移动或其它原因而中断的路由, 每个包含路由的节点周期地广播Hello 消息, Hello 消息的生成时间即TTL 值为1, 因此只能在相邻节点间传播。一个节点收到一个Hello 就可以新建一个邻居条目或者知道一个邻居与自己依然保持连接。如果在一定时间内收不到一个邻居的Hello 消息, 则认为该邻居与自己不再连接, 以这个节点为下一跳的路由都不能再用来传送数据, 因此将这些路由设置为无效状态。和AODV路由协议一样, M-RTAODV协议也允许局部维修, 在局部修复中, 修复节点将启动路由发现过程, 广播RREQ以便建立新路由, 如果在给定时间里能重新建立起有效路由, 就接着发送数据, 如果建立路由不成功, 则向上游发送RERR, 表明路由不可用。

2.3.3 路由中断后的处理

对于原AODV, 路由中断后, 将启动重新找路过程。在M-RTAODV中, 由于保存了多条路径, 当主路由中断时, 只要源节点和目的节点间仍存在其他路径, 就不发送RREQ重新找路;而是根据多条备用路径的优先级, 将先选择优级高的路径通信, 其次才选择优先级较低的路径通信。只有当源节点和目的节点间的所有可用路径均中断时, 才重新发送RREQ重新找路。

3 改进后协议的仿真和分析

由于改进后的M-RTAODV协议拥有多条路由路径, 在以下的仿真分析中, 分别设置路由路径数目分别为1、2、3, 以M-RTAODV1、M-RTAODV2以及M-RTAODV3来表示。利用UC Berkeley开发的NS-2仿真工具对AODV 协议和M-RTAODV协议在分组递交率、端到端的平均时延和网络开销三个方面进行了性能比较, 其指标定义如下:

· 分组递交率F 业务源产生的数据包个数与目的节点接收到的数据包个数之比:

$F = \frac{接收到的数据包个数}{发送的数据包个数}$

· 端到端的平均时延md 它包括路由查找时延、数据包在接口队列中的等待时延, 传输时延及MAC层的重传时延:

$m d = \frac{\sum (接收到数据包的时间 - A G Τ 发送数据包的时间)}{发送的数据包个数}$

· 路由协议开销oh 所有路由分组所含字节数, 单位为字节 (bytes) 。对于经多跳传输的数据包, 该包的每一次传输 (每一跳) 就认为是一次传输:

oh=总的路由开销

网络环境设置如下:30个无线节点均匀分布在一平面矩形区域内 (750m×750m) , 仿真时间为300s;应用层采用cbr业务源, cbr业务源个数为20;数据分组大小恒为512字节;节点移动模型为NS-2自带的random waypoint模型, pause time为0;节点移动速度为2m/s。由于缓解网络拥塞程度是要解决的主要问题, 在仿真中通过改变发包速率来比较网络负载对M-RTAODV以及AODV的影响。以下各图是发包速率分别为1, 3, 5, 7, 10 (/s) 时的仿真结果。

3.1 分组递交率

如图1分组递交率对比所示, 随着发包速率增加AODV的分组递交率急剧下, 且下降程度最明显;其次是M-RTAODV1;而M-RTAODV2和M-RTAODV3随发包速率增加而下降缓慢, 且两者性能基本相等。

从图1分析得到:AODV因为仅选择跳数最短的路径, 并未考虑到网络拥塞情况。随着网络负载加重, 网络中大量数据包由于网络拥塞被丢弃, 造成性能急剧下降。M-RTAODV1与AODV的区别在于:选择路径时同时考虑负载和跳数两项指标, 所选路由能有效避免网络拥塞点, 因此, 从图1能看到, 随着网络负载加重, M-RTAODV1的分组递交率虽然略有下降, 但下降趋势并不如AODV剧烈。从AODV与M-RTAODV1的比较能看出, M-RTAODV的路径选择策略能回避网络中的拥塞点, 缓解网络拥塞情况。而M-RTAODV2以及M-RTAODV3不仅考虑了路由负载, 同时缓存了备份路径, 其性能又明显高于AODV和M-RTAODV1。

3.2 端到端时延

如图2端到端时延对比所示, M-RTAODV1、M-RTAODV2以及M-RTAODV3较AODV都有所改善, 且三者基本相等。在网络拥塞的环境中, 分组的排队时延是影响端到端时延的主要因素。AODV并未考虑网络负载, 不能避开网络拥塞点, 导致数据分组大量阻塞在队列中, 不仅使得分组递交率下降, 也增加了分组的端到端时延。M-RTAODV虽然增加了找路时延, 但由于其在选路时有效避开网络拥塞点, 其端到端时延明显优于AODV。

3.3 路由开销

如图3路由开销对比所示:AODV与M--RTAODV开销基本相等。因为, 在本次仿真中, 路由开销主要由于AODV本身的Hello 机制导致, 而Hello分组是定时发送, 其开销仅与仿真时间有关。

4 结论

本文考虑了网络负载变化对AODV协议性能的影响, 进而提出了多路径路由协议M-RTAODV, 并且通过从分组递交率、端到端的平均时延和网络开销三方面比较了改进前后协议的性能。

从仿真结果可得出以下结论:在网络负载较轻时, M-RTAODV与AODV性能基本一致;而随着网络负载加重, AODV性能急剧下降, 而M-RTAODV性能下降缓慢, 且明显优于AODV。当网络拥塞较严重时, AODV性能下降显著, 而M-RTAODV由于在选路时考虑了路径负载, 其性能远好于AODV。而且由于AODV本身的Hello机制, 导致AODV与M-RTAODV开销基本相等。

但是, 要想使M-RTAODV路由协议在实际中很好地应用, 还需要做很多工作, 如QoS保障、路由安全等, 这些都是今后研究的方向。

摘要：由于Ad Hoc网络中, AODV (Ad Hoc On-Demand Distance Vector) 路由协议只保存单一路由路径, 因此提出一种基于多路由路径的改进AODV路由协议 (M-RTAODV) 。通过NS-2平台对该协议进行了仿真实验和分析表明与AODV相比较, M-RTAODV协议可以更有效地提高网络数据包传输的成功率, 降低网络中路由工作带来的网络开销。

关键词：移动自组网,主动式路由协议,多路径路由份AODV协议,NS-2

参考文献

[1]Li Layuan, Li Chunlin.AQoS-guaranteed multicast routing protocol[J]Computer Communications, 2004, 27 (1) :59, 69.

[2]David Espes, Zoubir Mammeri.Routing networks[C]//Icniconsmcl 2006:66-71.

[3]许力, 沈海红, 李峰.自组网中基于移动代理的具有移动和能量感知的AODV路由协议[J].小型微型计算机, 2006, 24 (2) :211-214.

[4]郑凯, 王能, 刘爱芳.基于JiST/SWANS平台的仿真软件的设计[C]//系统仿真技术及应用.第7卷—2005系统仿真技术及其应用学术会议论文集.合肥:中国科技大学出版社, 2005:310-314.

[5]肖百龙, 郭伟, 刘军, 等.AODV的本地修复算法[J].计算机应用研究, 2007, 24 (3) :231-237.

多路径路由第2篇

十年前, 互联网上出现了各种应用, 推动网络流量年增长率至30%以上[1]。为了满足日益增长的应用和带宽需求, 互联网服务需要从尽力服务模型转移到一个完善的, 在数据, 语音, 视频应用等各种情况下考虑不同的QoS需求的模型[2]。路径的多样性作为一个有效的网络资源集中机制而被提出[2,3,8]。如图1所示, 流客户端可以获得积聚的媒体流量来获得更好的用户体验。

可伸缩视频编码 ( Scalable Video Coding, 简称SVC) [4, 5]是一个H.264/AVC的可伸缩扩展, 支持空间, 通用和质量放缩。使用一个分层的视频编码, SVC可以将视频编码为一个基层 ( BL) 和一些增强层 ( ELs) 。各个层可以被独立地传输和接收。基层允许流客户端恢复一个低质量的视频, 增强层接收的越多, 则视频的播放质量会越高。这个特性同多径部署策略一起, 可以提供一个启发性的, 有前景的解决方案: 将视频流化传输给异质的, QoS需求不同的客户[6]。

本文设计了一个云计算网络体系架构, 它可以利用网络中的计算和存储能力感知网络状态并为基于可伸缩视频编码的视频串流提供多路径传输服务。基于SVC编码的特性, 我们定义了一个带宽分配粒度, 且设计了第一个基于最大流和辅助图的部署算法。该算法在静态和动态网络环境中的模拟表明, 它们可以在阻塞率, 带宽利用率, 包延迟, 丢包率和视频播放质量上获得有效的性能提升。

2 异质网络中云协助的 SVC 视频流多路径传输机制

2. 1 问题描述

图2展示了在本文讨论的网络基础设施。云在服务提供商网络的核心, 异质客户可以通过各种各样的连接场景连接到流服务。众所周知, 云的一个最大的优势在于它的弹性, 比如它的存储资源和计算力可以被动态地, 经济地分配到每个任务。假设云的弹性系统可以主动收集视频资源和网络状态。为了适应客户的异质性, 云使用SVC编码视频内容, 并存储到一个或者多个合适的服务器。因为视频编码框架已经被集中地研究[7,8,9], 通过权衡大量的计算和存储资源, 云收集并分析网络状态来为每一个请求, 计算一个优化的QoS感知多路径部署策略。通过一个集中式源路由机制, SVC视频流服务采用MPLS建立在网络层[8]。尤其需要指出, 云为每个编码SVC包的内容服务器分配了指定的标签, 并令路由器在多径标签交换路径上转发包。当网络状态改变时, 云会重新计算路径并执行更新。因为路径计算由云完成而不是由路由器完成, 我们不必重新设计路由器, 并且可以节省大量的协议开销。

图3展示了维护网络元素设置和云协助的SVC流会话之间的通信关系。此处, 假设云和网络由同一个操作员控制。在操作期间, 云收集网络状态如延迟和链路的可用带宽, 这是由现有的路由协议传播的 ( 如OSPF - TE) 。需要注意, 因为太频繁地广播网络状态会导致显著的开销, 缩小网络可扩展性, 我们需要在设计算法和协议时对网络监控和低控制层开销之间做一个权衡。当一个视频服务器收到一个流请求时, 它转发这个请求到云来获得部署策略的建议。云于是给这个请求计算一个多径部署策略, 定位流路径的标签, 并返回一个策略到一个或者多个服务器。当一个服务器收到部署策略时, 它开始用云提供的标签对视频内容进行打包。与此同时, 云使用MPLS消息沿着标签交换路径配置路由器。这些任务都完成之后, 一个流会话就建立了。云于是一直监视着网络, 当网络状态发生改变时, 通过重新配置路由器执行必要的LSP调整。

2. 2 多路径策略

对于每个视频请求, 首先根据最大流的方法计算请求源目的节点之间的最大带宽, 从而获得拓扑中的所有增广路径 ( Augmenting Path) 。根据增广路径我们构造最大流拓扑, 并在最大流拓扑中计算出多路径。构造辅助图, 辅助图中每个节点为一条路径, 节点之间相连表明两条路径之间满足时延抖动限制, 即路径之间时延差小于设定阈值。我们在辅助图里计算最大团, 从而获得所需的多路径。最后, 根据请求的带宽需求, 在多条路径上分配合适的带宽[10]。例如, 在如图4所示的最大流拓扑中, 针对一个三层SVC视频请求 ( 请求带宽分别为1, 1和2, 实验抖动限制为不超过1) , 根据上述方法, 获得如图5所示的多路径传输策略。

3 性能评估

在这部分, 设计了模拟实验来评估那些推荐的部署算法。首先, 在一个没有背景流变化的静态网络中, 基于最大流和辅助图, 在一个随机产生的拓扑上模拟了一系列的随机请求来评估多路径部署算法的性能。假设网络没有背景流变化, 在一个带有30个结点的随机产生的网格拓扑上比较了三个部署算法 ( 如: 单路径, 不考虑差分延迟约束的多路径和考虑差分延迟约束的多路径) 。每一个请求的源和目的端都是随机被选择的。每个请求的其他参数也是随机产生的, 如: 最大延迟请求、差分延迟请求和带宽请求。表1展示了仿真参数。单路径的算法在带宽和最大延迟的约束下尽可能的找到单一的可行路径, 而多路径的算法能给一个请求分配多条路径。在仿真中, 为了获得足够的统计精确度, 我们模拟了64个请求集并且平均了结果得到了图6, 图7的每一个数据点。图6、图7展示了阻塞的可能性和带宽的利用率。注意, 如果在多路径的情况下差分延迟的要求不能满足, 我们就把它当做一个阻塞的例子。可以看出, 随着请求的增加, 多路径的算法以更低的阻塞可能性优于单路径。在两个多路径算法中, 本文的算法提供最低的阻塞可能。从图7也可以看出, 本文的算法实现了最好的网络带宽利用率。图8详细地展示了两种多路径情况的差分延迟分布。考虑差分延迟约束的情形, 在低于预设阈值的情况下成功地控制了多路径部署请求的差分延迟。

4 结束语

本文提出了一种可以利用自身计算和存储能力更好地感知网络状态的云体系架构, 并且根据该体系架构设计了SVC视频流多路径传输机制。仿真结果表明, 与传统的单路径传输相比, 所提出的多路径机制可以获得更好的阻塞率和带宽利用率。

参考文献

[1]A.M.Odlyzko.Internet traffic growth:Sources and implications[J].Proc.SPIE, 2003, (5247) :1-15

[2]P.Frossard et al..Media streaming with network diversity[J].Proc.IEEE, 2008, 96 (1) :39-53

[3]J.Apostolopoulos et al..Path diversity for enhanced media streaming.IEEE Commun.Mag., 2004, (42) :80-87

[4]W.Li.Overview of fine granularity scalability in MPEG-4 video standard[J].IEEE Trans.Circuits Syst.Video Technol., 2001, 11 (2) :301-307

[5]D.Marpe et al..Overview of the scalable video coding extension of the H.264/AVC standard[J].IEEE Trans.Circuits Syst.Video Technol., 2007, 17 (9) :1103-1120

[6]T.Schierl et al..Using H.264/AVC-based scalable video coding (SVC) for real time streaming in wireless IP networks[C].in Proc.ISCAS, 2007:3455-3458

[7]N.Franchi et al..Multiple description video coding for scalable and robust transmission over IP[J].IEEE Trans.Circuits Syst.Video Technol., 2005, 15 (2) :321-334

[8]G.Wang et al..Multiple-description coding for overlay network streaming[J].IEEE Multimedia, 2007, 14 (1) :74-82

[9]C.Hsu et al..Partitioning of multiple fine-grained scalable video se-quences concurrently streamed to heterogeneous clients[J].IEEE Trans.Multimedia, 2008, (10) :457-469

多路径路由第3篇

无线Mesh网络[1] (Wireless Mesh Network, 简称WMN) 是一种新型的无线通信网络。WMN结合了无线自组织网络Ad hoc和无线局域网WLAN的网络特点, 和Ad hoc网络的主要区别是节点的移动性较低。目前, 无线mesh网络以其鲁棒性强、覆盖区域广、低成本、接入便利等特点日益成为无线接入网络的主要形式, 被称为是Internet的无线版本。无线Mesh网络具有自组织和自愈的特点, 并且具备有效的移动用户和跟踪机制, 是一种多跳的宽带无线网络, 也是一种高容量、高速率的分布式网络。本文主要研究如何充分利用无线mesh网络的网络资源, 提高数据的传输效率。

2. AOMDV协议

AOMDV[2]是按需多路径距离矢量路由协议, 是在AODV单路径路由协议的基础上扩展的多路径路由协议, 因此保留了AODV的许多特性, 两者最主要的区别在于AOMDV在路由发现过程中是发现建立了多条可用的路径。因此AOMDV在移动自组织网络中有较强的适应性, 可扩展性好。

按需路由算法的一个主要特点是由源节点启动路由发现过程, 只有当网络中某一个节点 (称为源节点) 有数据流要到另一个节点 (称为目标节点) 时, 源节点就通过发送到此目标节点的路由请求分组启动一次路由发现过程, 然后等待目标节点的路由回复。每次路由发现都会带来很大的延迟与路由开销, 这一点对于要成为无线接入网络的WMN来说, 终端用户对此是很难接受的。与单路径路由算法相比, 多路径路由算法在保持较低的路由发现频率方面做得非常出色, 可以有效地降低端-端的延迟和降低整个网络的开销。按需多路径路由算法每次路由过程都可以在源节点和目标节点之间建立多条路径, 只有在这些路径都失效时, 源节点才会启动新的路由发现过程;与此相反的是, 单路径路由算法的一次路由发现过程只建立唯一一条路径, 当这条路径失效时, 源节点便再次启动路由发现过程, 这无疑将大大增加路由开销。

3. AOMDV路由改进及实现

3.1 改进协议描述

3.1.1 系统模型

图1表示的是从源节点到目标节点之间存在n条不完全交叉的可达路径。这里, “不完全交叉”主要是说明了路径的选择方式, 在前面, 我们已经知道AOMDV路由算法是选择链路不相交以及节点不相交的可用路径作为可替换路径, 但是由于在无线Mesh骨干网络中, 相当部分节点 (如MR) 资源和能量都非常丰富, 不像移动Ad hoc网络中, 节点的资源和能量都有限, 如果多个数据流同时从一个节点通过, 这个节点就容易成为瓶颈节点。

所以, AOMDV路由算法针对移动Ad hoc网络的这一特性, 路径的选择只能是链路不相交或者节点不相交。而在无线Mesh网络中, 如何更有效地、更充分地利用MR的优势来转发数据流, 是体现一个算法性能的重要表现。

在图1中, 我们假设对于源节点S来说, 某一条已知路径pk的带宽容量为ck, 设定数据流以平均速度λ到达源节点, λ服从泊松分布。之所以规定数据流的速度方式, 主要是为了能更有针对性地考虑数据流按比例分配后在各条路径上传输的性能, 而不用源节点S对数据流的处理能力。

3.1.2 路径质量计算

本文采用路径延时[2,3]来对路径的质量进行计算。在有数据流到达源节点, 源节点在没有路径可以到达目标节点的情况下, 源节点会在网络中广播一个路径询问消息 (RREQ) , 目标节点最终收到这个请求, 它也会发送一个路径回复消息 (RREP) 经反向路径传播给源节点, 从而在源节点到目标节点之间建立起可通信的路径。在这两个消息中, 都会包含有路径质量参数Plji (D (lij) , BW (lij) , C (lij) ) , 而这其中就已经包含了路径的延时参数D (lij) 。因此本文考虑将延迟作为路径质量的衡量, 可以简化路由算法的设计, 从而降低整个算法的开销。

定义1路径的长度:从源节点广播出路径询问消息到源节点最终收到目标节点的路径回复消息的延时的一半, 称为某条可达路径的路径长度。

那么第k条路径的长度为:

从源节点广播询问消息到源节点最终接收到目标节点的回复消息的延时最小, 也就是说这条路径的距离最短, 那么把这条路径称为源节点到目标节点的最短路径。把这条最短路径记为:lmin (s, d) 。在源节点到目标节点的其中一条路径上, 对于该路径上的链路 (i, j) , 如果节点j到目标节点的最短长度比节点到目标节点的最短长度更小, 即lmin (j, d)

经过节点i的有效路径越多, 有可能节点的负担越重, 质量状况相对也会更差。k的值取决于经过节点i的有效链路数, 通常情况下k的取值范围在3.0～3.5之间。因此可以得到有效链路 (i, j) 的权值为:

由前面的分析很容易推出节点i的权值:

根据上面的分析, 由表达式 (1) (2) (3) 可以推出各条路径的权值为:

这样一来, 一条路径的权值, 不是简单考虑从源节点广播路径询问消息到收到路径回复消息的延时, 而是综合路径上各节点的实际质量状况, 有根据地推导出该路径的整体权值。因此, 这个权值可以认为如实反应了路径当前的实际质量情况。

路径权值事实上也就是路径可靠性的体现, 很明显, 路径的权值越大, 它的可靠性也就越强。通过对路径可靠性的量化, 可以更加简单地选择可靠性高的路径来进行数据流的传输, 从而更有利地保证数据传输的可靠性, 同时还降低了端到端的延时。而表达式中对有效链路的定义, 更是以一种几乎不增加路由算法开销的方式解决了算法中路由环的问题。

一条路径上最终要分配多少数据流量, 有了路径的权值后, 这个问题就很好办了, 权值越大的, 分配到数据流量也越多。如果权值很小的路径, 可以不选择用来进行数据流的传输, 这样就提供一个很好的方式来解决并发数据流会在质量差的路径上产生较大延时的问题。

3.2 数据流量分配比例计算

对于权值小的路径, 说明它的可靠性也不高, 分配给它的数据流量相应也要更少, 并且, 如果一条路径的权值太小, 可靠性太低, 那么应考虑放弃对它的使用, 不给它分配数据流量, 充分利用权值更大、可靠性更高的路径来为数据流量的传输提供高效的服务。因此对于可使用的路径p=pmin∪palt, 虽然每条路径都可到达目标节点, 但是根据路径的实际质量情况, 最终用于数据流传输的一组全格路径pelg中的n条权值较大、可靠性很高的路径。这样就能确保数据流量的可靠传输。

假设rpk为分配到路径pk上的流量比例, 那么显然会有rpk>rpk+1, 而每条合格路径上最终分配到流量比例为:

由于无线Mesh网络动态拓扑特性, 网络拓扑结构经常发生变化, 因此路径的质量状况也会随之而动态变化, 质量状况发生变化后, 权值的大小也会跟着变化。如果数据流量的比例一直按照权值大小进行分配, 而不管路径变化是不行的, 必须周期性地进行更新, 这样才能保证每条路径上分配到的流量比例是确实按照当前的路径质量状况进行计算的。

4. 路由发现过程

当RREQ分组到达目标节点时, 目标节点就会用反向路径发送一个路径回复消息RREP分组到源节点。同样地, 当RREP分组沿着反向路径往回转发时, 中间节点记录这条路径到自己的缓存中。由于一个中间节点会收到多个RREP分组拷贝, 在AOMDV路由算法中, 已经有了很好的机制防止出现RREP分组风暴。本文对目标节点转发RREP分组的总数做一个限制, 当目标节点收到同一个节点过来的RREQ分组超过RREP分组的阈值时, 就丟弃这个RREQ, 不再为这个RREQ分组创建RREP消息。中间节点根据收到的RREP来建立多条不完全相交的到目标节点的路径。当RREP到达源节点时, 源节点就把这条路径记录到缓存中。图2是目标节点回复RREP分组的过程。图3是中间转发RREP分组的过程。

4.1 路由维护过程

在无线Mesh网络中, 由于终端节点的移动性, 经常会造成链路的突然中断, 在本文的算法中, 当一个节点突然失效时, 它的上游节点便沿着反向路径向源节点发送一个路径出错分组RRER消息。当源节点收到这个RRER分组时, 并不启动路由修复程序对失效的路径进行修复, 而是直接丟弃与该节点有关的路径, 然后从可替换路径中选出权值较大的路径来继续发送数据流量, 直到路由表中没有可替换路径可以选择时, 源节点才启动新的路由发现程序。如此一来就大大减少了路径发现频率, 数据流量也不用等待, 立即可以通过其它路径转发到目标节点, 从而也极大地降低了端到端的延时。

如果路径在缓存中停留的时候很长, 很难知道它是否依然有效, 因此, 本文的算法中, 所有的节点均采用分布式推进方法交换信息, 每个节点保留它能侦听到的相邻节点的IP地址, 每个节点规则地广播一个HELLO消息。这个消息会包括以下内容:{节点i的地址, 相邻节点j的地址, 链路 (i, j) 状态参数Plji (D (lij) , BW (lij) , C (lij) ) }, 当节点i收到相邻节点j返回的HELLO消息时, 可以得到链路 (i, j) 的延时参数, 以这个参数来更新节点中记录的路由状态信息的延时参数, 从而更新路径的权值, 确保权值是对当前路径质量状况的真实反应, 是适时地反应了当前的网络拓扑信息。当一个节点i连续三次收到其邻居节点j的HELLO消息时, 就认为这一段链路已经断开, 链路的延时为无穷大, 权值此时为0。

5. 仿真模型

仿真在一个封闭的矩形平面区域里进行。为了更直观地反应无线Mesh网络的实际特点, 在仿真的过程将10个节点设置为静止, 也就是说这10个节点当成Mesh路由器 (MR) , 以这样的方式在仿真中构成一个无线Mesh骨干网络, 其余的节点在封闭的矩形平面区域内随机移动。每个节点的有效范围设置为250 m, 信息容量为2 Mbps, 无线电物理模型采用914 MHz的朗讯Wave Lan模式[5,6]。使用IEEE802.11的DCF作为媒体接入控制协议, 通过暂停时间 (pause time) 来反映网络的移动性, 节点的移动速度为0-10m/s。接口队列 (IFQ) 在路由层对路由包和数据包进行排队, IFQ的最大范围是50个包, 排队的原则是先入先出 (FIFO) 原则, 路由包的优先级高于数据包。

6. 仿真结果

移动性是无线Mesh网络一个很重要的特征, 在NS-2仿真环境下, 通过节点的移动速度和节点的暂停时间来描述节点的移动性。当节点的移动速度增加时, 说明节点的移动性增强, 此时网络拓扑的变化也随之增加, 0 m/s表示节点是静止, 当节点以10 m/s的速度进行移动时, 说明节点的移动性最大。

6.1 吞吐量分析

对多路径路由算法AOMDV和优化的AOMDV-DATD路由算法来说, 节点的移动性的增加对吞吐量的影响不会太明显。这是因为采用多条路径对数据包进行转发的过程中, 由于节点的移动性可能会造成其中的一条或者多条路径断开或质量不稳定, 但是路径断开后并不需要再次进行路由发现, 而是把数据包自动的分配到其他备用路径来进行传输, 这样就可以大大提高网络吞吐量。

6.2 端到端的平均延时分析

如图5所示, 从图中可以发现, 采用多路径的方式对数据包进行转发, 数据包从源节点到目标节点的延时很小, 这是因为多条路径共同承担了数据流量的转发, 让数据包通过质量好的路径快速地转发到目标节点。

6.3 丟包率分析

从图6可以看出, 优化后的AOMDV-DATD路由算法采用不完全相交路径策略, 最大限量地获得源节点到目标节点之间的可用路径, 而且由于对路径的质量进行计算, 将数据流量按路径权值大小将数据流按比例分配到多条路径上进行传输, 这样可以充分利用质量好的路径 (权值大) 来承担更多的传输任务, 有效地降低丟包率。

7. 结语

本章通过N S-2对本文所提出多路径路由算法AOMDV-DATD的性能进行了验证。对仿真环境进行了描述, 给出了仿真结果, 并对结果进行分析, 归纳本文内容, 我们可以得出如下结论:AOMDV-DATD算法有效地提高了网络的吞吐量, 降低了端到端的平均延时, 并将丟包率控制在了一个较小的范围。

参考文献

[1]K.Rayner, “Mesh WirelessNetworking, ”IEEE Communications En-gineer, Vol.1, No.5, pp.44-47, 2003.

[2]T.Nguyen and S.Cheung.Multimedia streaming with multiple TCP connections.In Proc.ofIPCCC, Phoenix, AZ, April2005.

[3]P.Sambasivam, A.Murthy, and E.Belding-Royer.Dynamically adaptive multipath routing based on AODV.In Proc.ofMedHocNet, Bo-drum, Turkey, June2004.

[4]杨俊丽, 刘明等.基于相关因子的节点不相交的ad hoc多路径路由算法[J].小型微型计算机系统, 2006, 27 (9) :1669-1672.

[5]Li Li, Ramjee, R, Buddhikot M., Miller, S..Network Cod-ing-Based Broadcast in Mobile Ad-hoc Networks.IEEE.INFOCOM2007.26th IEEE International Conference on Computer Communications.2007.1739-1747.

多路径路由第4篇

在网络QoS(Quality of Service，服务质量)业务提供中面临的一个重要问题是QoS路由问题，即如何决定一条满足多个QoS约束的路由，并同时高效地利用网络资源[1]。研究表明，寻找一条满足两个或者多个独立的QoS约束条件的路径问题属于NP完全问题[1,2]。而带宽与时延约束的路由(Delay and Bandwidth Constraint Based Routing,DBCBR)问题属于一个累加型与一个瓶颈型约束的QoS路由问题，由于带宽与时延的相关性，这类约束路由问题并不是NP完全问题。Wang-Crowcroft曾提出过一种用于解决带宽-延迟约束的路由算法[3]，其以带宽作为限制条件，以时延为操作尺度(Metric)，剪枝(Prune)条件是剪去剩余带宽小于某个级别带宽量化值(用户要求带宽)的链路，然后在满足的剩余链路中根据链路传输时延(Propagation Delay)用Dijkstra算法计算最短路径。这种处理，对于最高级别的带宽是没有问题的，但对于其它较低级别的带宽，有可能大多数业务会选择与高级别带宽路径相同的链路，从而造成大多数流聚集到可利用的高带宽链路上的情况，导致网络资源使用的不均衡，可能的后果就是网络拥塞。同时，其算法没有考虑结点处理速度的问题，对于现在的高速网络来说，忽略结点的因素就不能很好的抽象出网络特性，因为当距离足够长时，带宽造成的时延与媒体传输时延相比可能不再占主要地位。

该文研究了基于MPLS(Multi-Protocol Label Switching，多协议标记交换)网络的带宽时延约束路由问题，在Wang-Crowcroft算法的路由约束基础上引入中间节点负荷率限制，提出一种基于MPLS网络的带宽时延约束路由算法(DBCBR Based on MPLS)，从网络供需平衡、减少拥塞角度对原算法进行了一定的改进。

2 MPLS网络中的约束路由实现机制

MPLS从优化网络整体性能角度提供了对QoS的支持，包括面向连接的QoS支持和流量工程(TE)两个方面[4]。为了在MPLS上有效地部署TE，需要通过可执行的一些约束路由标记分配来实现，如CR-LDP和RSVP-TE。约束路由的框架结构如图1所示。由增强的IGP(内部网关协议)随时搜集来自网络的状态变化，搜集来的链路状态信息保存在TE数据库中，所有TE的操作、判断都基于这些原始数据。带宽管理器会从TE数据库中提取这些链路状态信息的变化，并提供给MPLS信令作为标记交换路径(LSP)建立的依据。MPLS的信令CR-LDP根据带宽管理器提供的链路信息资源同TE策略管理器一起选择出合适的标记交换路径。最后，路径选择部分需要把选择的路径资源占用情况告知TE数据库，改变数据库中相关数据。

MPLS能很好地支持约束路由，约束路由的应用可以让基于需求驱动的路由规范与基于拓扑驱动的逐跳式路由规范共存于同一网络中。约束路由使用的输入信息有流量中继主干线属性、资源属性和其它拓扑状态信息。基于这些信息，每个节点上的约束路由处理模块自动为该节点的每个流量中继主干线计算显式路由(Explicit Route,ER)。这种情况下，流量中继主干线的显式路由就是能满足干线属性要求、服从路由资源有效性、管理策略以及其它拓扑状态信息的限制的LSP。约束路由的使用促进了基于MPLS的流量工程的发展和实现，可以大幅度地减轻手工配置工作，减少人工对流量工程的干预。

3 一种基于MPLS网络的DBCBR算法

针对MPLS的约束路由与流量工程，我们研究了Wang-Crowcroft算法，在原算法的基础上，改进了剪枝(约束)条件，加入了新的节点与链路约束条件，引入了中间结点负荷率的约束，以提高网络资源利用率、平衡网络负载和减少拥塞为目的，提出一种基于MPLS网络的带宽时延约束路由算法(DBCBR Based on MPLS)。

在网络中，业务流通过节点的时延D=1/(1-α)·T，其中T为轻负载时路由器的转发处理时间，α为节点负荷率。当在一定的节点负荷的范围内，时延随着节点负荷率的增大而增大，节点负荷率代表了通过该节点的时延[5]。这说明了可以通过限制节点的负荷率，来得到一个可预测的时延上界，有较好的时延保证，同时又可以平衡网络负载，得到较好的网络资源利用率。

算法的思路是：当一个数据流到达网络后，采用改进的剪枝策略先期剪枝，引入节点负荷率门限值，当某LSR(Label Switching Router，标记交换路由)节点上负荷较大时，则剪去该节点，使得流量能绕过负荷较大的节点，映射到其他负荷较轻的节点，然后用Dijkstra算法计算最短路径。算法采用源路由策略。

以一个有向图G=(V,E)来表示网络，V、E分别表示节点集和链路集，|V|=n与|E|=m分别表示网络的节点数和链路数。设(u,v)∈E,从源结点s到目的结点d的路径为p。

1)链路剩余带宽

设B(u,v)表示链路(u,v)上的可用带宽，B0是带宽约束值，要求选定的路径p上带宽满足：。

2)链路时延

设D(u,v)表示链路(u,v)上的时延，D0是时延约束值，要求选定的路径p上时延满足：。

对于坌(u,v)∈E，算法采取的剪枝策略是：

(1)如果B(u,v)

(2)如果D(u,v)>D0，则剪去链路(u,v);

(3)如果D(u,v)=D0&&(u!=s||v!=d)/*即u,v不是源、目的结点的情况*/，则剪去链路(u,v);

(4)如果在链路集中(u,v)的度数为1(即u只有一个邻居结点v)，并且u,v都不是源、目的结点时，则剪去链路(u,v);

(5)如果α>α0,并且u,v都不是源、目的结点时，则剪去链路(u,v);α0为预先给定的结点负荷率阈值。

算法描述如下：

(1)初始化;

(2)对所有链路信息进行扫描，得到各链路的状态信息。将所有的标记交换路径LSP按照优先级从高到低，时延要求从小到大的顺序排序;

(3)计算各结点的负荷率α，结点的负荷率定义为：

(4)根据改进的剪枝策略剪去相应的链路和节点;

(5)在新的网络拓扑中，以节点的负荷率为权值，用Dijkstra算法计算路径;

(6)验证时延。

(7)如果没有找到满足约束的路径，则拒绝请求;如果找到多条可行路径，则返回其中最小跳路径为最终路径。

程序流程图如图2所示。

4 仿真实验

在NS-2中用MNS建立MPLS仿真实验环境，从请求的吞吐量(Throughput)、请求的阻塞率(Call Blocking Rate)以及端到端时延(End to End Delay)几个方面对改进算法与Wang-Crowcroft算法进行比较。仿真实验的网络拓扑结构如图3所示。S为数据源，产生BE(Best Effort)和EF(Expedited Forwarding)两种类型的数据，其在NS-2中的流量参数(Traffic Parametre)配置如表1所示;D为目的节点，负责接收数据。用脚本文件控制请求的到达时间间隔为0.5s，在一定程度上模仿突发性。设立各LSR节点的负荷率阈值均为0.5。两种算法的比较是在同一网络中分别实现的，网络中的各项参数相同。

仿真结果图4反映了分别采用Wang-Crowcroft算法与改进算法后，BE流与EF流请求的吞吐量与时间尺度的关系。可以看出，随着时间的增长，节点与链路上流量增多，使用改进算法因为引入了节点负荷率的限制，使得流量较均衡地分布到各个LSP，能最终达到更高的吞吐量，从而提高了网络的整体性能。

图5给出了分别采用Wang-Crowcroft算法与改进算法后，BE流与EF流请求的阻塞率随网络流量变化的关系。请求的阻塞率(Call Blocking Rate)等于某类流的请求包拒绝数除以已接纳的该类流请求包总数。其反映的是为请求建立通路的成功率。可以看出，在负载较轻时，BE流与EF流没有拒绝包，阻塞率为0;随着网络负载的不断增加和网络资源的不断消耗，请求包的阻塞率会越来越高。因为改进算法在处理中，加入了负荷率的限制，当某个LSR节点上负荷较大时，会主动地将BE流映射到其它的LSR节点，从而减少了某个节点负荷过大而造成拥塞的可能性，网络中整体流量较为均衡，更多的流能到达目的节点，从而使得在更多的负载下，阻塞率依旧保持为0，并且在网络负载增大时，同样高负载的情况下的EF流与BE流阻塞率均较Wang-Crowcroft算法要低。可以得出，使用改进算法能提高通路建立的成功率。

从仿真结果图6可以看出，负载均衡使得网络中的EF流与BE流的端到端时延都有比较明显的改善，从EF流的曲线来看，改进算法的端到端时延变化较为平缓，从而从一定程度上可以减弱时延的抖动，这点对于实时流与多媒体数据的传输是非常重要的。

5 结束语

改进的DBCBR算法引入了节点负荷率的限制，将QoS约束路由与资源预留结合在一起，克服了因网络动态变化而造成的通路建立失败，同时，当最优通路上某个节点负荷过大时，改进算法能将流量映射到其它的LSR节点，降低了网络拥塞率，并且提高了整体的网络吞吐量，从而提高了网络性能。从仿真实验可以得出，改进的算法在请求吞吐量、通路建立成功率以及端到端时延等方面较Wang-Crowcroft的DBCBR算法有一定的优越性。

摘要：针对MPLS网络,提出一种带宽时延约束路由改进算法,引入节点负荷率的限制,在路由时避开负载较重的链路,在保证用户业务带宽与时延约束的前提下,为一部分流量寻找一条相对较长但负载较轻的路径,以使得整个网络的流量分布更加均衡,从一定程度上可以减少网络拥塞。从仿真实验结果来看,改进后的算法在吞吐量、请求建立的成功率以及端到端时延等性能方面有比较好的表现。

关键词：多协议标记交换,服务质量路由,多约束路径,节点负荷率,流量工程

参考文献

[1]Chen S G,Nahrstedt K.On Finding Multi-constrained Paths[J].IEEE Communications Magazine,1998:874-879.

[2]Vasilakos A,Saltouros M P.Optimizing QoS Routing in Hierarchical ATM Networks Using Computational Intelligence Techniques[J].IEEE Transations on systems and Cybernetics-part C:Applications and Reviews,2003,33(3):297-312.

[3]Wang Z,Crowcroft J.QoS Routing for Supporting Resource Reservation[J].IEEE Journal on Selected Areas in Communications,1996,14(7):1288-1294.

[4]刘韵洁,张云勇,张智江.下一代网络服务质量技术[M].北京:电子工业出版社,2005.

多路径路由第5篇

AODV协议作为一种开销小、按需路由的新型网络技术,成为近年来路由协议的研究热点[1]。文献[1]提出了基于路由可用性预算的LAP-AODV路由协议,旨在预测节点发生的可能性。文献[2]考虑网络节点的电池电量问题, 提出了AODV-BR路由协议,以节点的某一阈值作为协议评价指标之一,实现路由转发。文献 [3]针对网络传统AODV协议存在的链路不稳定、路由修复率低问题,提出了链路时间可用的LAT-AODV协议。文献[4]提出了基于模糊数学理论的DADOAV路由协议,旨在提高路由节点的可信服务质量。文献[5]针对网络安全机制提出了基于可用信任模型的ATAODV路由协议。

当网络拓扑频繁发生变化时,路由发现过程频繁,导致路由发现过程不断重启,产生了较大路由开销。如何通过网络仿真平台验证网络协议的正确性,并通过网络仿真工具测试相应网络协议的性能,已成为AODV路由协议研究的重点之一。在无线Mesh网络中,应用传统AODV路由协议,无法降低节点频繁移动导致的路由重启产生的开销[6]。

目前,国内外网络协议仿真软件主要有NS2、Opnet、 Matlab等。NS2(Network Simulator version 2,NS2)网络仿真工具[6]源于美国加州大学伯克利分校开发的开放源代码网络仿真软件,以面向对象、自备虚拟时钟、所有仿真结果均由离散时间驱动为特色。基于NS2网络平台验证AODV路由协议、评估算法、协议可行性,能实现网络拓扑的鲁棒性、健全性[7]。

本文重点研究如何降低路由重启发现过程产生的路由开销,并提升无线Mesh网络数据的分组投递率。

1NS2基本结构

NS2网络仿真平台作为一种具有时间离散驱动的开发工具,由时间调度器、网络组件对象库、网络构建模型库构成。其中,仿真时间计算由事件调度器完成,分组数据由网络组件缓冲。C++类、OTCL类构成了网络构建模型,C++类是算法和协议的具体实现。OTCL对象是用户接口对象,主要建立OTCL对象、设置属性、通过事件调度器调度网络模拟事件发生。

NS2allinone包含有多个开源模块,软件安装目录如图1所示。其中,目录结构中最重要的是ns2-allinone2.30/ns-2.30。而仿真实验中常用的网络协议、C++源代码存在于NS-2.30目录中,OTCL源码则位于ns-2. 30/tcl/lib目录。通过NS2平台设计改进的算法、协议,需要以C++和OTCL代码为基础,重新编译ns-2.30目录下的相关代码。

如何利用NS2网络平台展开网络仿真是NS2应用的关键。网络仿真结果通过TCL编写的模拟脚本所产生的Trace文件,以动画效果呈现在NAM模块上。通常,利用AWK分析Trace文件,并用gnuplot进行仿真结果图形绘制,NS2基本结构如图2所示。

2AODV路由算法性能分析

AODV[7]路由协议在DSDV、DSR的基础上增加了按需距离矢量,产生了路由发现、路由维护两种机制。 AODV路由协议路由发现过程步骤如下:

步骤1:一旦源节点与目的节点存在通信,源节点可以通过查找路由表是否有到达目的节点的路径,来判断路由信息。如发现,则直接发送数据包;否则,发送RREQ路由请求,分组发起路由发现过程,进入步骤2。

步骤2:如果由收到RREQ路由请求分组信息,则该节点发送已知的对比序列号。如果该节点已包含此路由请求分组信息,则丢弃该分组,反之,进入步骤3。

步骤3:先在网络拓扑上建立反向路由,广播该路由请求分组信息。如果目的节点收到RREQ分组,则将发送路由应答分组RREP,建立由源节点到目的节点的路径;如果源节点收到RREP则表示路由建立完毕。

AODV路由协议路由维护方式以本地修复、源节点路由重建为主要特点。主要步骤为:

步骤1:以一定周期广播HELLO报文,用以检测链路通信状态。如果一定时间内,未收到来自邻居节点的Hello响应报文,表示该链路已经断开,进入步骤2。

步骤2:启用本地修复机制。如果失败,则删除缓存中源节点发送的数据包,发送RRER错误分组信息至源节点,源节点重新发起路由发现过程。

AODV路由协议在一定程度上降低了路由开销、网络覆盖率,但对于仅有一条路径需要维护、双向信道传输、超时删除路由、拓扑变化频繁等问题,AODV仍然存在缺陷[8]。

3AODV协议改进算法

AODV路由协议无法处理路径断裂带来的网络开销问题,同时无线Mesh网络节点频繁参与路由建立和数据传输,使得传统的AODV无法建立最短跳数范围内的路由发现和路由回复。

针对传统AODV的不足,本文提出在路由发现过程中通过路由请求(RREQ)消息,发现源节点到目的节点的路径。根据目的节点收到最新的RREQ,优先处理向源节点回复路由响应(RREP)。源节点收到RREP消息后,启动RREQ缓存定时器。对此时间段内收到的所有不同的RREP进行缓存,并对其进行排序。确定主路径,通知应用层开始发送数据。当主路径拥塞,长时间未响应时,切换优先级高的有效路径。在路由发现过程建立一条或者多条从源节点到目的节点的备用路径。比较各可行路径的负载情况和跳数综合评价指数,取最好的路径作为主路径,其余为备用路径。考虑到维护多条备用路径会消耗过多资源,再次备用路径只取1条。具体流程图如图3所示。根据路由的优先级情况,得到基于优先级的AODV协议PBMAODV[9]协议。

根据上述路由协议流程,建立基于优先级的AODV路由协议。假设网络拓扑为二维平面拓扑,可将无线Mesh网络拓扑抽象为带权双向图G(V,E),其中V为节点集合,节点个数n=|V|,vi∈V,i=1,2...n,其中各节点等待队列的数目与其等待队列最大长度的比值,表示节点负载程度。即:

其中,qvi表示等待队列的长度,Qvi表示等待队列的最大长度。

定义1:可行路径。给定网络G(V,E),如果从源节点S(Source)通过多跳存在一条路径到目的节点D (Destination),p = {S,...D},则p称为一条可行路径。

定义2:路径参数。给定一条可行路径p = {v1,... vn},其中路径包含的节点数为n。则网络拓扑上的路径负载中,最大的网络负载率为:

定义3:对于给定一条路径p = {v1,...vn},结合定义二参数,给定优先级函数f(p)定义如下:

其中,max(hopcount)为网络接受最大的跳数; hopcount为从源节点到目的节点的条数;,β均为 (0,1) 空间的任意参数。

4仿真分析

仿真网络由50个移动结点构成,各结点随即分布在1000×1000的平面矩形框内,结点无限传输距离为250m,随即以均匀分布最大速度20m/s向任意方向移动, 结点之间的最大连接数目为30,源节点数量为3,6,…, 18,每秒发送4个CBR分组,Mac层协议采用IEEE802. 11,模拟时间为900s,不同运动场景中,结点到达目的地点后的停留时间分别为0,100,200,300,…,900结点停留时间越少,整个网络拓扑的变化越频繁。具体仿真参数如表1所示。分别对AODV、AOMDV和本文提出的改进PBMAODV协议在分组投递率、平均端到端时延和归一化路由开销3个方面进行比较。

从图4可以看出:1当源节点数目低于10时,3种路由协议的端到端时延保持一致。随着源节点数目的增加, 端到端时延结果AODV最高,AOMDV比AODV的端到端时延略低,PBMAODV端到端时延最低;2当节点移动速度提升至9m/s后,3种算法端到端时延逐渐清晰,其中PBMAODV路由协议具有最小的端到端时延。

从图5可以看出,随着时间推移,3种算法的路由开销逐渐降低:1当时间为100s时,AODV协议路由开销最大,AOMDV与PBMAODV路由协议具有相同的开销;2当时间大于100s时,PBMAODV路由协议具有最低路由开销。综合分析曲线图,PBMAODV和AOMDV则比AODV的归一化路由开销有大幅度的降低,并且PBMAODV表现的比AOMDV好。

从图6可以看出,随着时间推移,3种算法得到的分组投递率军稳定变化。综合分析3条曲线,发现PBMAODV和AOMDV在分组投递率上明显高于AODV, 并且PBMAODV优于其它两种算法。

5结语

多路径路由第6篇

在无线传感器网络资源受限的环境中将感知数据从源节点安全、有效地传输到汇聚节点具有一定挑战。很多研究尝试解决资源受限的WSN环境中的数据转发问题。这些研究选择源和汇聚节点之间能够满足资源受限 (如能量、带宽和计算能力) 需求的最优路径, 并考虑最小跳数、最小传输代价和最大剩余能量等方面因素来进行数据转发。还有一些路由协议试图在数据转发过程中通过减少节点能量消耗来增加网络寿命。然而, 这些方式在能量利用效率等方面性能均低于多路径路由协议。多路径路由协议搜索源和汇聚节点之间所有的可用路径。

由于数据被分配在多条路径上传输, 所以传输能耗也相应地被均衡到不同的路径上。多路径路由协议通过基于有效的负载均衡机制在不同路径中分配数据传输量以此更大程度地均衡网络能量, 增加数据传输的可靠性, 保证Qo S需求, 以及适应WSN资源受限的特性。

另外, WSN中路由协议很容易受到恶意节点的安全威胁。特别地, 容易遭受多种网络攻击, 如篡改攻击、选择转发攻击、污水池攻击和女巫攻击等。本文提出一种安全和能量高效的节点不相交多路径路由协议———EEMRP。EEMRP是汇聚节点发起的主动路由协议。协议基于最大路径效用原则确定源和汇聚节点之间的主路径和备用路径, 从而有效均衡网络能量, 延长网络寿命以及实现应用所需的Qo S保证。EEMRP采用椭圆曲线密码和MD5确保数据传输的私密性、完整性、认证性和不可否认性。它能有效抵御WSN中篡改攻击、路由转发攻击和污水池攻击等各种攻击。

2 能量高效节点不相交多路径协议 (EEMRP)

2.1模型假设

对本模型进行如下假设。

1假设WSN网络为无向连接图G (V, E) , 其中, V是节点集合, E是边集合。如果节点i和j能够互相通信, 则链路 (i, j) ∈E。2网络中包括传感器节点、网关节点和汇聚节点三类节点, 所有节点随机部署。其他节点通过多跳方式向汇聚节点发送信息。3根据通信距离、传感器节点数量和地理位置, 将网络划分为簇结构。每个簇中包含且仅包含一个负责数据融合和节点管理的网关节点, 网关节点能量远远大于传感器节点。所有传感器节点均具有相同的能量, 相同的感知、计算和通信能力。汇聚节点的能量和处理能力不受任何限制。4每个传感器节点都具有固定的传输范围R。网络中源节点和汇聚节点之间有多条节点不相交路径, 源节点基于最大路径效用原则选择到达汇聚节点的主路径和备用路径。5每个节点都具有唯一的私钥和公钥, 且均可以使用MD5算法。

2.2 EEMRP路由生成

EEMRP是一种基于簇结构的主动式节点不相交多路径路由协议。EEMRP由汇聚节点发起路由生成过程。在路由生成阶段, 节点通过交换路由建立数据包 (RFP) 搜索到达汇聚节点的所有节点不相交路径, 同时建立并维护路由表。

如果到达汇聚节点的大量路径以某节点Ni作为中间节点或者Ni处理数据量较大, 则相应地, Ni的能量消耗也会较高。因此, 为了更大化路径效用, 均衡节点能耗及延长网络寿命, 同时保证路径具有低时延、高可靠和高吞吐量性能, EEMRP中每个节点基于最大路径效用原则从多条节点不相交路径中选择主路径。最大路径效用原则考虑了路径能耗、节点剩余能量和链路时延等重要参数。为了确定路径效用, 每个节点需对这些参数进行测量和估计。如果路径效用低, 则表明由于路径上节点剩余能量不足或路径能耗较高等原因, 此路径不适合作为主路由路径。

路由建立具体过程如下:

1汇聚节点向所有网关节点组播RFP数据包, 启动路由生成过程。

2每个网关节点将RFP跳数设为1, 并广播RFP。

3对于接收到RFP的传感器节点, 如果路由表中不存在到汇聚节点的路径, 则转到步骤5, 否则继续。

4传感器节点计算自己的节点效用Nutility并检查RFP。如果其跳数大于路由表中的跳数或者其节点效用低于效用阈值, 则丢弃数据包, 否则继续。

5传感器节点存储并更新RFP:a将跳数加1;b更新前向节点ID并其加入到路径中;c更新路径效用;d更新路由表。

6这个过程重复到所有传感器节点都建立了用于存储到达汇聚节点路径的路由表。

其中, 每个节点按照公式 (1) 计算自己的节点效用。

公式 (1) 中, α为归一化因子, Eresidual为节点剩余能量, Econsume为节点和链路能量消耗, Cqueue为空闲队列比例, Clink为链路和节点处理延时。

RFP中路径效用为后向路径中所有节点效用总和与最小节点效用连接值。前者为低16位, 后者为高16位。设路径效用值为x, 则效用阈值

如果节点接收RFP, 则需更新RFP的路径效用x, 具体方式为:

1更新最小节点效用。

2更新节点效用总和, 即x=x+Nutility。

2.3 EEMRP数据传输与自适应成簇

设k是节点j和汇聚节点之间的路径数, m是路径Pi上节点的数目。搜索到到达汇聚节点的所有路径后, 节点基于最大路径效用原则选择最优主路径, 其综合考虑了路径上节点效用总和及最小节点效用两个因素。

为了选择最优的主路径, 节点首先计算各路径的路径效用PCi=a* (x>>16) +b* (x&0x FFFF) 。其中, a+b=1;a、b为恒定平滑因子。为了较好的反映当前路径效用情况, 本文将a设为0.7。路径效用既考虑了路径瓶颈问题———最小节点效用, 同时也考虑了路径效用整体最大化。最终, 节点选择路径效用最大的路径作为到达汇聚节点的主路径, 即PP=max{PCi, 其中, i∈k}。

这意味着主路径能够处理最多的数据流并且路径上不会有单个节点过早死亡。主路径是所有节点不相交路径中最可靠的路径。

EEMRP根据定义1和定义2实现自适应成簇。

定义1 (簇的定义) 设网络中网关节点数目为m, 则将网络中除汇聚节点外的所有节点划分为m个簇。每个簇有且仅有一个网关节点;网关节点作为各簇的簇首, 负责簇内节点管理、数据融合和路由转发等功能。

定义2 (自适应成簇) EEMRP中路由生成过程由汇聚节点发起, 且RFP均经由网关节点发送到传感器节点。因此, 到达汇聚节点的任意路径都至少包含一个网关节点。源节点自动加入距离最近的网关节点为簇首的簇。簇首负责簇内传感器节点管理, 数据融合及数据转发等功能。每个源节点都有到达汇聚节点的唯一主路径, 由于每条主路径上有且仅有一个距离源节点最近的网关节点, 因此, 网络中所有节点均能自适应的加入唯一的一个簇中, 从而, 完成网络的自动成簇。

主路径确定后, 源节点沿主路径将感知信息发送给汇聚节点。由于主路径上的节点需要承担路由功能, 所以它会比其他节点消耗更多的能量和系统资源。为了更大程度地均衡网络能耗及保证数据传输的可靠性, 主路径需定期更新和维护。EEMRP基于两个定时器Timer1和Timer2实现主路径的更新。Timer1时间到达时, 采用备用路径作为主路径。Timer2时间到达时进行基于局部查询的路由更新或全网路由更新。

3 EEMRP的安全性

公钥密码体制是基于非对称密钥对 (公钥和私钥) 的密码体制。它的显著优点是无需密钥分发便能保证数据传输的机密性, 它通常能够更好的适用于开放的多用户环境。与公钥密码体制对应的是对称密钥密码体制, 它常用于WSN环境。然而, 对称密钥密码体制需要节点之间协商共享密钥对, 密钥的协商和管理会增加网络的控制开销。

公钥密码体制可以保证数据传输的私密性、完整性和认证性。之前, 很多学者认为公钥密码体制较高的计算开销和能量消耗使其应用于WSN显得不切实际。然而, 最近一些学者证明, 经过良好的设计公钥密码体制也可以配置在资源受限的传感器网络设备上。目前, 不少研究者试图使用公钥密码体制解决WSN中的安全问题。

EEMRP致力于保证数据传输的私密性、完整性、认证性和不可否认性。EEMRP的安全性基于椭圆曲线密码和MD5实现。椭圆曲线密码 (ECC) 仅需轻量级的计算开销和能量消耗便可保证数据传输的安全性, 非常适合特殊的WSN环境。

在EEMRP路由建立阶段, 汇聚节点向邻节点广播RFP。收到RFP后, 如果选择转发RFP, 则在转发之前邻节点先使用自己的公钥更新RFP, 然后再向它的邻节点广播REP。基于此过程, 网络中所有节点均可获知其邻节点的公钥。

如果验证正确, 则邻节点接受消息;否则, 拒绝消息并生成路由错误数据包通知发送者消息已被改变。主路径上每跳的源和目的节点都执行此过程。

网关节点接收并验证数据签名后, 使用私钥对消息M解密。经过数据融合和数据压缩等处理后, 网关节点将从簇内传感器节点收集的感知数据统一发送给汇聚节点。最终, EEMRP能够保证无线传感器网络数据传输的私密性、完整性、认证性和不可否认性。

4 仿真与分析

使用NS2.35实现了EEMRP。仿真范围为400*400m2, 网络中共有50到500个节点, 采用802.15.4 MAC层协议和Two Ray Ground传播模型。在包转发率、端到端延迟和平均能量消耗方面将EEMRP与经典的DSR相比较。

4.1 包转发率

与DSR相比, EEMRP包转发率总是更高, 即EEMRP中数据包丢失率总是小于DSR。这是因为EEMRP基于最大路径效用原则从路由表中选择主路径, 最大路径效用原则考虑了节点队列长度和链路质量等因素。如果路径上节点队列已占用率较大或链路质量较差, 则选择该路径作为主路径的几率就会相应减小。因此, EEMRP能够更为有效地避免因队列占满或无线信道恶劣而引起的数据包丢失。

4.2 端到端延迟

端到端延迟包括数据传输过程中所有可能出现的延迟, 如缓冲延迟、排队延迟、MAC层的数据转发延迟以及数据传输延迟等。当源节点向汇聚节点发送数据时, DSR和EEMRP分别产生的端到端延迟情况。与DSR相比, EEMRP的端到端延迟更小。这是由于EEMRP中所有节点均建立并维护节点不相交多路径路由表, 到达汇聚节点的路径直接可用。而DSR是被动式多路径路由协议, 当有数据需要传输时, 需先启动路由发现过程, 所以其端到端延迟会更大。另外, EEMRP在选择主路径时考虑到了链路延迟等因素, 因此, 与DSR相比, EEMRP端到端延迟会有明显减少。当节点数分别为50和500时, DSR端到端延迟分别为0.917s和4.678s, 而EEMRP端到端延迟仅分别为0.197s和2.078s。EEMRP比DSR平均延迟减少了44.17%。

4.3 平均能量消耗

无线传感器网络中平均能量消耗是评估路由协议性能的重要参数之一。与DSR相比, EEMRP平均能量消耗更少。EEMRP是主动式路由协议。在路由生成过程中, 每个节点建立维护路由表并以节点剩余能量和路由能量消耗为重点考虑来确定到达汇聚节点的主路径。因此, 与DSR相比, EEMRP路由能量消耗大大减少, 平均能量消耗减少了79.1%。

4.4 安全性分析

EEMRP协议能够有效抵御篡改攻击、女巫攻击、选择转发攻击和污水池攻击等各种攻击。EEMRP采用公钥密码体制实现数据加密及点对点消息认证。如果接收节点能够验证数据签名的正确性, 则可以有效确保消息传输的完整性、认证性和不可否认性。因此, EEMRP可以有效抵御篡改攻击。另外, 由于EEMRP中每个节点都知道其邻节点信息并且主路径选择由源节点完成, 恶意节点没有机会形成黑洞从而恶意丢弃数据包或改变网络数据流特征。因此, EEMRP能够有效抵御选择转发攻击和污水池攻击。对于共谋攻击, EEMRP也能有效防范。这是因为EEMRP中路由生成过程由汇聚节点发起, 最优主路径由源节点基于最大路径效用原则来选择, 从而可以有效避免路由环路的生成及多个被俘节点联合进行共谋攻击。可见, EEMRP由于其路由原理及公钥密码体制的采用, 大大提高了协议的安全性能。

5 结束语

本文提出安全能量高效节点不相交多路径路由协议EEMRP。协议中源节点和汇聚节点之间主路径的选择考虑了节点剩余能量、路由能量消耗以及缓存利用率等重要因素, 从而有效提高了路由的可靠性, 延长了网络寿命。EEMRP中网络节点可以自适应成簇, 进一步提高了协议的可扩展性, 在网络规模较大时仍能保证较好的网络性能。仿真结果显示, EEMRP性能比DSR更为优越。另外, EEMRP基于椭圆曲线密码体制和MD5实现加密和数字签名, 从而更好地保证了网络的安全性。EEMRP能够有效抵御篡改攻击、选择转发攻击和女巫攻击等各种攻击。一种具有链路可靠性的能量及Qo S预测机制仍待进一步研究。

摘要：无线传感器网络中能量高效路由协议的目标是尽可能延长网络生存时间。多路径路由协议可以使网络流量在多条节点不相交路径间均衡分配, 从而可以有效增加网络寿命。另外, 安全的数据传输也成为WSN广泛应用所必须的重要提前。本文提出一种无线传感器网络中基于数字签名的能量高效多路径路由协议。

关键词：无线传感器网络,多路径路由协议,数字签名

参考文献

[1]Al-Karaki J N, Kamal A E.Routing Techniques in Wireless Sensor Networks:A survey[J].Computing Network, 2004, 11 (6) :6-28.

[2]Lin Kai, Chen Min, Ge X H.Multi-Attribute Data Fusion for Energy Equilibrium Routing in Wireless Sensor Networks[J].KSII Transactions of Internet and Information Systems, 2010, 4 (1) :5-24.

[3]钱志鸿, 朱爽, 王雪.基于分簇机制的Zig Bee混合路由能量优化算法[J].计算机学报, 2013 (03) :485-493.

多约束QoS路由技术的研究第7篇

关键词：QoS,路由技术,跳数,时延

随着网络多媒体技术的飞速发展,Internet上实时多媒体应用层出不穷,如IP电话、视频会议、视频点播(VOD)、远程教育等多媒体实时业务以及电子商务在Internet上传送,Internet已逐步从单一的数据传送网向数据、语音、图像等多媒体信息的综合传输网演化。这些不同多媒体应用要求通讯网络提供高效的服务质量(QoS)。衡量服务质量包括主要参数如下:(1)时延:一个信息包在两个参考点之间传输的时间间隔;(2)时延抖动:相同路径上信息包的时延变化;(3)吞吐量:经过一个网络或网络设备的信息包的速率,可以用峰值速率或平均速率表示;(4)丢包率:一个网络丢弃信息包的最大概率。IP网络中的服务质量问题主要与IP网络的传输方式有关。IP网络采用“尽力而为(best-effort)”的传输方式,仅为数据传输找到一条通道,而对传输的结果不做任何保证。这样的传输方式会带来很多服务质量问题,例如:(1)因为传输中可能会丢失或抛弃信息,所以无法保证传输内容的完整性;(2)由于对资源实行共享和动态分配,因此不能保证传输的速率或带宽;(3)不能保证能及时响应用户。

从某种意义上说,这是IP网络分布式的、开放的环境带来的负面影响。未来IP网络上会有多种业务开展,其中多媒体业务要求非常高的传输质量,实时业务要求非常高的响应时间和传输时延控制,这是目前的网络传输环境无法达到的。为满足对QoS不同的需要,提高IP网络对服务质量的支持能力,有以下几种QoS技术:资源预留协议(RSVP)、差分服务(DiffServ)、多协议标记交换(MPLS)、虚拟专用网以及流量工程(Traffic Engineering)等技术。这些网络技术的研究主要通过两个途径提高QoS,一个是节点控制;另一个是整网或局部网络控制。节点控制在单节点或单链路完成,主要控制业务对单节点共享资源的占用,包括共享的链路、缓存区、处理器资源;节点控制主要的策略包括:业务流整形、业务调度、节点缓冲区管理。整网或局部网络控制通常通过对路由与信令的控制达到对业务流或业务在网络中传输的直接控制,因路由直接关系到网络性能,所以QoS路由成为解决QoS问题的一项关键技术。

1 QoS路由选择技术

QoS路由的概念用来刻画服务提供者与用户之间用数量或质量来定义的性能约定。一次连接的服务质量由一系列约束条件给出,如带宽约束,时延约束,抖动约束等。QoS路由的主要目标是为接入的业务选择满足其服务质量要求的传输路径,同时保证网络资源的有效利用。一般路由选择过程由两个部分组成:一是为到达业务选择路径并发送数据包的过程,本文称之为寻路过程;一是节点间路由信息的交互过程。

与传统的尽力而为的路由过程相比,QoS寻路过程涉及三个方面的问题:一是依据哪些度量参数作为寻路标准,这里简称为度量参数选择问题;另一个是在寻路标准设定后,如何找到满足业务需求的路径,并保证数据经由选定路径传输到目的节点,我们称之为寻路问题;路由信息交互过程中,由于链路传输延时的存在,每个节点获得的其他节点的状态信息总是具有一定的不准确性,这些不准确性将在一定程度上影响QoS路由算法的有效性,因此,路由信息不准确的问题,也是QoS路由中的一个主要问题。度量参数选择问题、寻路问题和路由信息不准确问题是首要解决的基本问题,也是QoS路由中的研究重点。

解决QoS路由问题就是找到一条满足一个或多个QoS条件的路径。网络服务被要求提供的QoS,对于给定路径相对于其成分链路而言一般表现如下3类性质。

1)可加性:总QoS等于构成这条路径的所有链路QoS值之和(如跳数,时延等);

2)可乘性:总QoS等于构成这条路径的所有链路QoS值之积(如误差率,丢包率等);

3)最小最大性:总QoS等于构成这条路径的所有链路QoS值中的最小者(如流量,带宽等),或者总QoS等于构成这条路径的所有链路QoS值中的最大者(如带宽利用率等)。

因此对于最小性QoS,进行路径选择之前不满足QoS的链路将不作为路径选择对象;对于乘法性QoS,可以将各链路的QoS值进行对数变化,转换为加法性QoS,保证在进行路径选择时只包括加法性QoS,以便于处理。

2 多约束条件下QoS路由模型

由于要同时满足这些性质各异的QoS是比较复杂的,Dijkstra算法只能根据单一条件来计算最短路径,在大规模的网络中则需要设置多个约束条件,使得计算的复杂度控制在多项式的时间内完成,首先根据某些条件简化网络,然后再根据某一条件计算最短路径。

为了便于处理,进行路径选择之前将不满足QoS约束的链路不作为路径选择对象,同时,对于最大最小QoS一般可以采用加权方法(或倒数)进行变换。对于乘法性QoS,将各链路的QoS,将各链路的QoS值进行对数变换,转换为加法性QoS。所以,在进行路径选择时只包括加法性QoS。这样就可以将QoS路由问题经过变换可以转化为多目标决策问题。

假设一个QoS多个约束条件为x1,x2,…,xn,分别对应业务类型,带宽,时延,链路长度,跳数,端口吞吐能力,端口缓冲能力等,则目标函数f1(x),f2(x),…,fp(x)分别代表路径p上的端到端的可利用带宽函数,传输时延函数,时延抖动函数等约束条件函数。在对瓶颈带宽和时延抖动等分别进行最大最小化处理、加权处理和对数处理后,可以得到QoS路由的一般形式:

若路径p满足上述条件就是QoS请求的可行路径。下面设计一个多约束QoS的路由算法。

3 算法设计

3.1 问题描述

为了研究算法,将网络中的交换节点、链路、链路属性抽象为图,其网络模型可以表示为G(V,E);其中V是顶点的集合,包括n个顶点,其中v∈V为图的一个节点;E是边的集合,包括m条边,e元素为一条链路。在每条链路e关联上一组相互无关的权值(w1(e),w2(e),...,wk(e)),称为链路的QoS的度量,简写为w(e),其中wi(e)为路径约束类型权值度量。

定义1:源节点s和目的节点d之间路径P跳数为,e为路径P上的链路。

定义2:对于图G中,每一链路e∈E均对应两个正实数加权值cost(e),delay(e)。cost(e)定义了链路e的代价,其值与该链路的资源使用情况有关。delay(e)定义了链路e的信息传输时延,该时延包括排队时延、传输时延和交换时延等。路由问题可描述为在图G中寻找一条包括源节点s到接受节点d的路径P,应满足以下条件:

约束条件:其中△为时延上限(或称时延约束),该参量定义了实时业务的传送延时要求,用于平衡代价与延时的路由选择策略,链路选择函数如下:

其中P(i)是路径从源节点s到目标节点i的时延,c(eij)、D(i,j)分别为链路eij的代价及时延。

3.2 算法实现机理

一般地说,最优算法无法在多项式时间内完成。采用启发式算法降低算法难度,但在性能上逼近理论算法。下面的算法就是启发式算法。根据上面的定义,该算法有几个输入变量:首先是配置链路特性(跳数,时延);其次是与这些特性相关的资源状况;第三是网络的拓扑信息。其中网络的资源和拓扑信息可以通过IGP来获得。根据链路特性传输时延识别重点链路,采用为链路赋权值的方法,根据链路的时延情况,时延长的链路赋较大的权值,时延小的赋较小权值。为了防止所选路径过长而消耗过多的网络资源,引入跳数限制,令H表示路径的最大跳数限制。在权值的基础上,综合考虑时延保证和跳数,提出一种时延、跳数受限的最小权值路由算法。主要计算步骤如下:

1)排除掉那些链路信息不全的链路,然后进行链路所属的资源类的检查,检查之后,如果发现有无效的资源所属关系的链路,就把这些链路排除掉;

2)根据删减后的拓扑计算最短距离的路径。在满足上述条件下,路径P的权值最小,P就是就是从源节点s到接受点v的路径。

3.3 算法实现

根据上面多约束条件QoS路由模型构造思想,具体条件应满足上面定义1和定义2,通过改进Prim算法来求解问题。Prim算法用于求最小生成树,Prim算法的基本思想为:在图G中,算法从U={S}(S为源点),U为其生成树的顶点集合,T=Φ开始,重复执行下列操作:在所有u∈U,v∈{V-U}的边(u,v)∈E中找一条权值最小的边(u0,v0)并入集合T,T是G上MST中边的集合,同时u0并入U,直到U=V为止。

改进算法的基本思想是:首先,用Dijkstra第k最短路径算法,计算从源节点到目的节点以时延和跳数为优化准则的路径,选择跳数Hop(p)小于H的路径,将所求的路径中最小的时延与Δ比较,若该值比Δ大则表明限制条件太苛刻,可令Δ等于该路径的时延。然后以cost最小为首要优化目标,用Prim算法求出图G的MST树。用Prim算法每生成一条边eij时,就计算由S到该边的跳数Hop(p)和累计时延,若Hop(p)

4 结束语

在基于多约束的路由选择算法中,寻找一条同时满足两个或两个以上度量约束的路径,是一个NP完全问题。该问题目前在数学上还没有统一确定的解决方法,这也意味着还没有标准的基于约束的路由算法。因此在路径选择算法,约束条件选择上具有相当的灵活性,随着今后光传输技术的发展,需要考虑的约束条件一定会随之而发生变化,我们应该根据不同的网络结构和性能需求来选择不同的参数,从而更好地适应未来智能光网络发展,这些有待跟踪研究。

参考文献

[1]吴中平.IP网络的QoS路由算法的研究[D].天津:天津大学计算机科学与技术学院,2007,1.

[2]包学才.一种多约束服务质量路由算法[J].微电子学与计算机,2008,10.

[3]崔新友.IP over DWDM网络多业务传送的路由算法[J].清华大学学报,2008,48(1).

[4]贾艳萍,孟相如.基于MPLS流量工程的多路径约束负载均衡方法[J].计算机应用,2008,27(3).

本文来自 99学术网(www.99xueshu.com)，转载请保留网址和出处

【多路径路由】相关文章：