多径路由机制范文

多径路由机制范文（精选5篇）

多径路由机制 第1篇

随着网络技术的迅猛发展, 网络中所存在的具有复杂连通关系的节点也逐渐增多。同时, 网络无标度性[1]和六度空间理论[2]的进一步研究, 也使得网络的容错抗毁性成为共同关注的热点。

在现有的通信网络服务模式中, 基本上都是一种网络支撑一种业务, 而这种网络模式在一定程度上为人们提供了高效便捷的网络服务。然而, 随着网络业务越发多样化的发展趋势, 单一的网络模式已经无法满足网络及服务的多样化需求, 这就出现了对各种业务都能提供良好支持的新型的多业务可信网络。多业务可信网络是与传统的一种网络支持一种业务的网络模式完全不同的新型网络体系架构, 其设计理念是一种网络支持多种业务, 这种网络结构能够提供多业务支持的能力和网络可信性的保障, 能够为人们提供更为方便快捷高效地信息交互的网络服务。

本文就是在新型多业务可信网络模式下, 针对传统的单径路由的局限性, 提出了基于边界网关协议 (BGP) [3]路由协商的自治系统 (AS) 级多径路由工作机制, 为新型网络环境中高质量、高可靠性的信息传输提供了一定的借鉴意义。

1 多径路由问题分析

新型网络体系架构的设计理念就是支持普适化服务的多业务可信网络架构, 从而便于为用户提供一体化的网络服务[4]。该体系结构能够支持固定终端、移动终端以及移动子网等多种类型用户的统一接入, 并且能够为各类型的用户提供分布式的网络资源共享和数据资源的查询服务。在新型网络体系架构中, 主要分为接入路由器和交换路由器两类, 接入路由器负责固定终端、移动终端以及移动子网等各类用户的统一接入, 为接入网络的用户分配接入标识和路由标识, 并将用户所要传输的数据信息传送到核心网, 而交换路由器则是根据数据报文中的路由标识将数据信息在核心网中进行转发[5]。而在数据的传输和转发过程中, 多径路由是相对于单径路由而提出的概念, 指的是为通信节点之间的可达性提供多条可用的路径, 而节点主机可根据其策略对这些可用路径的自主选用。由多径路由所组成的网络被称为多径路由网络, 该网络中的路由器执行多径路由算法, 多径路由算法用来为节点间通信提供多条路径, 并确保发往其中一条路径的数据经由该路径到达目的网络。

随着网络通信技术的快速发展, 核心骨干网络的带宽越来越高, 这就为多径路由技术的深入研究提供了基础。随着FIND, Planet Lab, GENI, CABO等下一代网络 (NGN) 项目研究逐步深入, 势必会对网络技术产生更为深远的影响。同时, 路由模块可操作性以及可编程路由器的进一步发展、各类网络设备和网络技术的迅猛发展等等, 这些都为多径路由的研究提供了便捷条件。

在具体的新型网络核心层环境中, 各个交换路由器都具有路由功能, 因而随时能为核心层中的各个交换路由器节点对建立一条或多条替换路径, 那么从宏观上就能有效地提高整个网络的路由可靠性和容错性, 同时网络资源也能得到充分利用, 从而改善了网络的通信性能。所以为改善核心层网络服务质量, 避免单径路由给网络节点可能带来的拥塞或高负荷状态, 消除核心层路由层面的不稳定因素, 本文的设计是在交换路由器部署应用多径路由扩展机制。

2 BGP多径路由的设计

网络最基本的功能就是报文信息的传输, 而新型的多业务可信网络对网络传输更是有着安全性、可靠性、容错性等多样化的网络服务要求。然而, 当前网络传统的传输模式是单径路由, 也就是每个网络传输节点都只向指定的其单下一跳结点转发传输数据的。这种单径路由工作模式很容易导致如下情况的发生, 即网络中的某些节点和链路处于高负荷或拥塞状态, 而另一些节点和链路的负载相对较低, 从而出现各个传输节点和传输链路负载失衡的网络状况。另一方面, 简单的单径路由协议在当前网络规模逐渐复杂的网络环境下很难有效地满足容错、路由可靠性、Qo S路由等高层次的路由要求[6], 尤其是应用于网络核心传输层负责大规模域间路由工作的BGP协议, 简单的单径路由更不能满足大量的各种数据报文在核心路由器之间信息传输的要求, 从而影响到网络中核心路由的稳定性。因而, 多径路由的设计与应用成为新型多业务可信网络体系中路由传输层面的研究重点。

2.1 设计思想

针对新型网络能够满足各种不同服务类型终端统一接入的需求, 其核心层网络所需要传输数据包的信息量则显著增多, 这就要求部署应用于核心层的BGP路由协议能够完成核心层大量的路由选路和信息交换工作。而传统的单径路由机制在出现网络拥塞或是负荷过大的情况时就很难满足核心层网络性能方面的要求, 从而造成网络潜在的不稳定状态。

BGP多径路由扩展机制的设计思想是:提出一种支持多路径的可选域间路由协议解决方案, 该方案通过引导核心层传输AS域的交换路由器根据选路策略进行路由的双边协商, 从而灵活地选择或通告合适的AS级替换路径, 以此对网络通信量进行有效地负载平衡控制以及拥塞控制, 满足数据通信和映射信息传输的路由层面的性能要求。可以看出, 由于AS域在向相邻域通告路由之前, 会将自己的AS号码添加到该路由的AS_PATH属性中, 所以该机制是一种基于AS级别的路径矢量路由方案, 能够实现简单化的路径选择, 并且对传输AS域交换路由器之间的协商控制是通过选择输出额外的替换路径来实现的。

2.2 AS间BGP多径路由的双边协商

在传统的BGP路由系统中, 大多数AS域和终端/子网对于BGP提供的现有路由感到满意, 路由层面也能够处于大致稳定的运行状态。而当某个AS域有替换路由时, 该AS域是向所有的相邻体通告该替换路由的, 这种向所有AS邻居通告替换路由的机制将会在一定程度上影响到域间最优路由的选择, 从而破坏网络中整体路由的稳定性。因此, AS级多径路由机制是在AS域需要的时候允许其灵活地请求替换路径, 而不是强行地把替换路径通告给所有的AS域邻居。首先, 给出请求AS域和响应AS域的概念: (1) 请求AS域:根据路由策略向AS邻居发出请求信息以得到适当的替换路由的AS域; (2) 响应AS域:收到AS邻居发送来的得到适当替换路由的请求消息后, 根据过滤规则选择输出合适的替换路由给该AS邻居的AS域。

针对以上概念构造出AS间BGP多径路由的双边协商模型, 如图1所示:

其中, 模型图中的五个圆圈分别表示的是五个自治系统, 其自制系统号分别是1~5, 圆圈间的连接表示自治系统间的BGP会话。假设AS1到AS5的最优路由为<1235>。这时如果AS1根据自己的路由策略不再希望通过现有路由<1235>达到AS5, 而是想寻求一条替换路由, 那么AS1则向其下一跳自治系统AS2发出路由请求消息, 请求AS2通告一条到达AS5的替换路由, 而在这个请求消息中可能会包含AS1的路由策略, 如避免路由经过AS3。在收到AS1的请求后, AS2会根据自己的路由策略将具有较高优先级的替换路由通告给AS1。此过程即为BGP多径路由的双边协商模型。其中AS1为请求AS域, AS2为响应AS域。

BGP多径路由的双边协商模型是请求AS域与响应AS域之间的路由层面的模型框架, 因而也需要有相应的路由协商管理策略进行有效地策略支持。这里, 针对多径路由的协商模型设计如下的路由协商管理策略:在请求AS域中, 如果当前的最优路由不能满足本域的需求则触发协商, 若此时刚巧有邻居AS发送来的路由更新消息使得最优路由发生变化, 那么抑制所要触发的路由协商;而在响应AS域中规定只有来自于可信AS对等体的路由协商请求才能被接受, 允许协商的建立, 并根据自己的路由策略选择出合适的最优的替换路由发送给请求AS域。

2.3 多径路由隧道封装

BGP多径路由机制导致了AS域向相邻体通告替换路径的路由行为, 这会妨碍域间最优路由的选择, 破坏整体路由环境的稳定性。因此, 为了不打破原有优选路由环境的格局, 提出了隧道封装的设计方法, 即在AS域根据自己的路由策略请求到替换路由后, 请求AS域与响应AS域之间对于该替换路由达成了一致。若请求AS域要求使用替换路由向目的终端/子网发送数据包, 则在两个AS域之间建立一条隧道, 通过隧道机制使用替换路由发送数据包, 从而在该隧道中进行信息的传输。

隧道的建立是对于替换路由的协商达成一致后在请求AS域与响应AS域之间进行的。其具体实现过程是:请求AS域和响应AS域对于替换路由达成一致时, 若请求AS域需要将数据信息通过替换路由发送到目的终端/子网时, 即使用隧道封装技术, 首先向响应AS域建立隧道的通告消息, 响应AS域收到通告后回复一个确认。这时, 请求AS域就可以使用数据隧道封装技术将数据包进行适当的封装后发送给响应AS域。响应AS域接收到数据包, 识别出替换路由的下一条AS以及对数据包进行解封装操作, 再将数据包通过协商好的替换路由发送出去。

另一方面, 可以通过设置隧道计时器的方法对长时间不被使用的隧道进行拆除。比如通信AS域之间在隧道计时器的计时范围内没有标有隧道标识符的信息相互传输, 则认为隧道不再被使用, 即可进行拆除。同时, 若请求AS域与响应AS域之间的路径出现错误, 请求AS域就会拆除隧道;若到达目的终端/子网的替换路由发生了故障, 响应AS域将会拆除隧道。

3 结论

本文在分析当前传统网络环境中单径路由所存在的劣势的基础上, 针对新型网络路由稳定性的需求, 提出了基于BGP路由协商的AS级多径路由机制, 该机制通过BGP路由的协商可以为新型网络中任何一个层次的AS域提供一条可选的AS级替换路由, 使得AS域在策略允许的情况下可以灵活地选择AS路由, 从而能够很好地避免因单径传输、链路拥塞或负载失衡而带来的路由稳定性问题, 为新型网络尤其是其核心层创造了稳定可靠的路由环境。

参考文献

[1]Barabasi A L, Albert R.Emergence of scaling in random networks[J].Science, 1999.

[2]Watts D J, Stroga S H.Collective dynamics of‘small-world’networks[J].Nature, 1998.

[3]Huston G.Analyzing the Internet’s BGP Routing Table[J], The Internet Protocol Journal, 2001.

[4]王上.一体化网络接入交换路由器分离映射的设计与实现[D].北京交通大学, 2008.

[5]侯宁, 贺伟, 宋宇鲲.支持虚拟电路机制的包连接电路路由器[J].合肥工业大学学报自然科学版, 2015.

无线mesh网络多径路由算法研究 第2篇

无线mesh网络是一种新型的宽带无线接入系统, 是由无线链路连接路由器和终端设备的静态多跳无线网络。它可以看做是WLAN和移动Ad hoc网络的融合, 因此, 无线mesh网络结合了Ad hoc和WLAN网络的拓扑特点, 具有可靠性、自组织性和自愈性的特点。随着人们对互联网依赖和移动通信需求的不断提高, 人们希望在任何时间、任何地点都能够与任何人进行快速、高质量的通信, 而且能够连接到互联网随时随地地获取互联网上丰富的资源和服务, 无线mesh网络技术的逐渐成熟加速了宽带无线互联网时代的到来。

由于无线mesh网络是一种具有自组织、自管理的智能型网络, 它不需要主干网就可以构造出动态的、富有弹性的网络结构, 具有前期投入少、覆盖范围广、抗干扰能力强、扩展能力强、网络结构灵活、维护方便、可靠性高和兼容性好等特点。

路由技术向来是任何网络结构中的研究重点与难点, 是保证网络得以部署和运行的关键。目前, 无线mesh网络中主要采用的单路径路由算法。单路径是否最优并不重要, 由于无线mesh网络动态性较强, 若花费太多的代价去寻找最优路径, 那么可能该路径还没有使用就失效了。在单路径环境中, 自适应的路由方式还容易产生振荡现象。因此, 单路径路由算法很难对网络的拥塞进行控制。针对无线mesh网络本身的特性, 国内外不少专家学者开始对多路径技术进行研究, 主要思路是在源节点与目标节点之间建立多条路径进行传输, 来实现网络负载均衡、充分利用网络资源。本文在这个基础上提出一种基于无线mesh网络中自适应流量分配算法。它从无线mesh网络路径的动态信息中得到各路径的权值, 根据权值大小自适应地按比例分配数据流量到各条路径上进行传输。

2 系统模型的建立及权值的计算

图1为一个简单的网络拓扑结构, 从图中可以看到, 从源节点 (s) 到目标节点 (d) 之间存在n条跳数最小的路径, pmin表示跳数最小的路径集, 用palt表示可选路径集。那么所有可用的路径集为p=pminUpalt。这里源节点s和目标节点d之间由n条非交叉的路径1p、p2、、pn相连。假设对于源节点s来说已知路径pk的带宽容量为ck, 并且设定源节点s的数据流以平均速度λ到达, 服从泊松分布;停留时间为, 服从指数分布。为了方便, 设定每个流消耗1单位的带宽, 也就是说, 路径pk能在任何时间供给ck条流。

于是, 问题转化成研究如何沿着这n条路径传输数据流使得整体的阻塞可能性最小, 吞吐率最大。本文的思路是根据源节点s和目标节点d之间不同路径的权值来调整各路径中的流量分配。即根据路径权值的大小按比例分配数据流量, 从而解决流量分配的均衡问题。

路径可靠性的权值, 这里选择延时参数, 这是由于路径询问消息 (RREQ) 和路径回复 (RREP) 中的路径质量参数都包含了延时参数。对于任意节点, 可以得到2个相对于目标节点的最小延时值, 一个是RREQ消息的延时时间, 另一个是RREP的延时时间, 本文取两者的平均值, 假设从源节点到目标节点第k条路径的传输延时为该路径的长度, 其大小为源节点收到的RREP消息累计延时的一半记为

假设从源节点到目标节点的最短延时为最短长度, 记为lmin (s, d) , 对于链路 (i, j) , 如果lmin (j, d)

于是可以得到有效链路 (i, j) 的权值为

其中, 记为与节点i相连的所有有效路径的平均长度, k为分配参数, 由与节点相连的链路数决定取值, 通常取3.0～3.5。

综上可知, 节点i的权值为节点i所邻接的各有效链路的权值之和

得出各路径的权值为

可靠性与路径的权值直接相关, 路径的权值越大, 可靠性就越大, 这是对每条路径进行数据流量分配的基础。

3 路径选择

在源节点与目标节点之间可能存在多条跳数最小的路径pmin和可选路径palt。因此, 所有可用的路径为p=pminUpalt。不过, 这中间可能有部分路径的性能很差, 以至于不能用来传输数据, 在分配流量时, 就不再使用这些路径。也就是说在分配流量比例的时候, 只需要用到那些性能比较可靠的路径。对于一组合格的路径pelg, 采用加权轮询路径选择方式, 根据它的权值选出一条路径p∈pelg, 算法选择使用一个确定的算法来保证流量比例维持在一个尽可能小的时间窗内。它采用确定的路径队列, 队列中的路径都以一个与流量比例相近似的频率周期性地发布。它通过生成一个路径队列来实现, 这些路径在尽可能小的时间窗内维持流量比例。这个队列由加权轮询路径选择方式快速地产生, 对于每个流入的数据, 加权轮询路径选择方式生成队列中的下一条路径, 数据流量分布到这条路径上去, 具体过程用程序表示如图2:

4 流量分配比例计算

根据前面建立的多路径模型以及计算得出的所有路径的权值, 按照路径权值的大小顺序进行排序, 确定使用的n条路径为权值排在前列的n条路径。显然, 流量分配比例与路径的权值大小成正比, 即权值越大的路径分配到的流量比例也相应越大, 权值小的路径相应分配的流量比例也小, 甚至由于部分路径的权值太小而导致性能太差, 可能根本不会使用。因此, 在这里设rpk为分配到路径pk的流量比例, 则有rpk>rpk+1。

对于每条路径的流量比例分配, 应考虑到流量小的情况。如果数据流量较小, 根本不需要使用多条路径来进行传输, 因为较小的数据流量采用多条路径进行传输, 所花费的开销过大, 效率反而不高甚至更低。所以在数据流量较小的情况下, 我们选择其中的最优路径来传输, 也就是权值最大的第一条路径。即这条路径此时的传输比例为1。多路径主要是针对数据流量较大的业务。分配给各条路径的流量比例计算方式如下:

这里, 考虑到由于无线mesh网络的动态性, 网络拓扑结构经常发生变化, 路径状况必然也是经常改变。所以对路径权值的计算要周期的进行更新。

本文的算法中, 所有节点均采用分布式推进方法交换信息, 每个节点保留它能侦听到的相邻节点的IP地址。每个节点规则地广播一个HELLO消息。HELLO消息包括以下几个域:{节点i的地址, 相邻节点j的地址, 链路 (i, j) 状态参数。当节点i收到相邻节点j返回的HELLO消息时, 可得到链路 (i, j) 的延时参数, 以这个参数更新节点中记录的路由状态信息的延时参数, 从而更新路径权值, 保证路径权值能适时的反应当前的网络拓扑情况。当一个节点i连续三次没有收到其邻居节点j的HELLO消息时, 就认为它们之间的连接中断, 链路延时为无穷大, 权值相应变为0。

网络拓扑每次发生变化就马上进行权值的更新, 其代价很大没有必要。本文设置一个时间周期, 在每个时间周期结束时就重新计算流量的分配比例{rpk, pk∈P}。一个时间周期由η个循环组成, η是用来控制统计流量的健壮性和稳定性的可配置的系统参数, 主要由网络拓扑变化情况和负荷稳定程度来确定, 如果变化较慢就设置值大一些, 变化快时设置值相对小一些。流量分配得越正确, 时间周期就越稳定。η的取值一般在1～3之间。在每一个时间周期里, 如果网络拓扑不发生巨大变化, 每条路径分配的流量比例就相应的稳定。在一个时间周期结束后, 才根据更新后的权值重新计算流量比例。

如果在一个时间周期内网络拓扑发生巨大变化, 比如说多数路径都中断了, 这时必须重启路径发现程序, 触发权值计算过程, 重新计算各路径的数据流量分配比例。

5 仿真结果及分析

本文采用NS-2仿真平台对算法进行验证。利用random waypoint model作为节点的移动模型。主要参数设置为:MAC层使用IEEE802.11协议, 信道带宽为2Mbit/s, 节点数量为50个;在区域1km1km上的数据包发送率为10包/s, 数据包大小为64B;业务流类型为CBR (constant bit rate) ;移动距离为250m, 整个仿真时间为300s。仿真结果如图3～图5所示:

从图3可以看出AODV算法与本文提出的算法ADMR的负载情况。ADMR有效地限制了控制包的洪泛区域, 也减少了路由的负载。并且由于ADMR根据路径权值的大小去掉了不稳定及效率低的路径, 所以有更小的路由负载。

图4显示了节点移动的速度对路径平均延迟的影响:ADMR的路由平均延迟随速度的增加比AODV的增加明显更小。

两个算法的数据包投递率如图5所示。随着速度的增加, AODV的数据包投递率也有一定的下降。ADMR采用多条路径进行传输, 减少了丢包的可能性, 并且高质量的路由也保证了数据包的高投递率。

6 结论

本文提出的基于动态网络拓扑的自适应流量分配算法ADMR, 通过计算各路径的权值, 根据权值去掉不稳定及效率低的路径;流量依据权值的大小按比例自适应的分配到各条路径进行传输, 保证了数据包稳定传输, 提高了网络的数据包的高投递率。

摘要：无线mesh网络以其鲁棒性、覆盖区域广、低成本、接入便利等特点日益成为无线接入网络的主要形式, 在无线通信技术中扮演越来越重要的角色。针对无线mesh网络的特点, 本文提出一种基于动态拓扑的多路径自适应流量分配算法。此算法根据路径质量的权值动态地给各路径分配数据流量比例。仿真结果表明, 此算法保证了数据包的稳定传输以及提高了数据包的投递率。

关键词：多路径,mesh网络,自适应

参考文献

[1]Jun J, Sichitiu M L.The nominal capacity of wireless mesh networks[J].IEEE Wireless Communication, 2003, 10 (5) :8-14

[2]Xiao J T, Kunz T.Traffic balancing in wireless mesh networks[C]//2005International Conference on Wireless Networks, Communications and Mobile Computing.Las Vegas, USA, 2005:169-174

[3]Whitehead P.Mesh networks:a new architecture forbroadband wireless access systems[C]//2000IEEE Radio and Wireless Conference.Denvor, USA, 2000:43-46

[4]Lee S J, Gerla M.Split multipath routing with maximally disjoint paths in ad hoc networks[C]//Proceedings of the IEEE ICC.Helsinki:IEEE Press, 2001:3201-3205

[5]Peter P P.Congestion Avodiance Using Multipath Routing and Power Control In Mobile ad hoc Network[D].Adelaide, University of South Australia, 2002

[6]An H Y, Lu X C, Peng W.A cluster-based multipathrouting for MANET[A].Proc of Med-Hoc-Net2004[C].Bordum, 2004.405-413

[7]Wang L.Multipath source routing in wireless ad hoc networks[J].Canadian Conf Elec Comp Eng.2000 (1) :479-483

多径路由机制 第3篇

一、智能电网的概念与特征

智能电网就是电网的智能化, 通过将大量智能装置接入电力系统来实现智能化、自动化电网运行。智能电网建立在通信网络基础上, 通过智能控制技术、传感技术、测量技术、设备技术、决策支持系统技术来实现电网的高效、可靠、安全、经济运行, 从而降低供电损耗, 提高供电质量, 构建坚强智能电网。智能电网由:智能变电站、智能交互终端、智能配电网、智能发电系统、智能储能系统、智能调度系统、智能电能表等几大部分组成[1]。截止二零一五年, 我国智能电网建设已初具规模, 国内电力智能化、自动化水平有明显提高。

二、智能电网通信要求及通信网路由特点

通过前文对智能电网特征分析可以知道, 智能电网具有一定特殊性与传统电网工作模式明显不同。智能电网需要以高效、双向、集成通信网络为基础, 离不开完善的通信网络[2]。智能电网通信网络需对电能生产、输送、分配、消费等多种信息进行快速处理、传输、控制。电力通信网络根据传输信息和速率的不同, 可分为:终端接入网络和骨干通信网络两大部分。通信基本业务需求有:图形业务、数据业务等等, 具体根据系统要求不同也可能涉及到其他特殊业务, 但基本业务需求内容相同。电力通信对通信质量有着较高要求, 若通信质量差出现错误, 将可能对供电质量造成影响, 甚至导致电力系统出现误动, 引起故障, 造成非计划停电。智能电网通信网络根据电网布局可分为:线型和树型两种结构。通信中不仅业务量大, 且通信节点多, 业务联系密切, 数据流向变化大, 对实时性有着较高要求。由于电力通信的特殊性, 决定着电力通信路由结构的特殊性, 目前基本结构大多为星型控制结构。星型控制结构容易实现, 控制简单, 且易于维护和故障诊断, 某一节点故障并不会造成整体网络瘫痪, 网络稳定性好, 中心节点压力小。具有较强可靠性和稳定性, 有效改善了单一路由造成的网络脆弱性问题。

三、面向智能电网的新型电力通信网动态多径路由研究

1、动态多径路由算法。目前智能电网通信网的路由算法大多为静态路由算法, 这种算法下往往路由表固定不变, 而网络扩容时却需要整个路由表更新。这种情况下如通信节点过多, 就会造成路由表庞大而复杂, 十分利于快速寻址, 将影响寻址速度。因此, 为了实现快速寻址, 提高路由性能, 降低时延, 应利用多级混合地质驱动寻址, 进一步优化路由算法的寻址方式, 加快寻址速度。

2、多级分层设计。智能电网具有较强复杂性, 涉及到众多节点, 整个通信网络就是一个有机的通信链路组合, 节点涉及到:转接点、交换点、端节点等。为了满足电力生产、输出、分配、消费各环节中信息交换任务要求, 实现动态多径路由寻址, 应构建分层路由节点结构[3]。结构形式可分为:环形结构与星型结构。星型结构运算效率高, 但大规模传递易出现拥堵, 因此必须选择简明而高效的路由算法。环形结构通信延时性好, 能够实现多条路径最快寻址, 但稳定性有待提高, 具体设计中应对主干线路和节点进行优化, 从而保障整个系统的稳定性。

3、寻址策略。寻址策略影响着路由寻址速度和路由性能发挥, 大节点寻址应明确各自物理位置, 以物理地址作为寻址依据, 即坐标路由寻址。大节点设置要根据系统复杂程度, 具体分为:网络编号法和编址坐标法。通常每一设备点都要根据通信条件和通信速度进行编址, 利用物理地址表达极坐标, 以满足路由寻址需要。寻址策略设置中, 要尽量减少参与路由路由的节点数量, 从而提高处理速度和寻址速度, 压缩路由表规模, 降低故障率, 解决拥堵问题。

结束语:新时代背景下电能需求越拉越大, 传统电网模式已不能满足电力发展需求。智能电网的推广大大降低了供电成本, 提高了供电质量。但智能电网实现需要以完善、可靠的电力通信网络为基础, 而动态多径路由则大大提高了电力通信网络通信质量, 加快了寻址速度, 解决了单一路由的网络脆弱性问题。

摘要：现代社会对电力需求越来越大, 但传统电网稳定性较差, 故障率高, 时常发生非计划性停电, 已难以满足日益增长的用电需求。智能电网则能够提供高质量供电服务, 容许各种不同发电形式的接入, 且具有自愈能力, 能够抵御攻击, 电网稳定性和可靠性更强, 推广智能电网具有重要意义。智能电网以集成的双向通信网络为基础, 因此对电力通信网络有着一定要求。本文将针对智能电网的新型电力通信网络动态多径路由展开研究和分析, 以促进我国智能电力发展。

关键词：智能电网,电力系统,通信系统,多径路由

参考文献

[1]董雪源.基于互联网技术的电力系统广域保护通信系统研究[D].西南交通大学, 2012, 13 (11) :119-124.

[2]熊小萍.电力系统广域通信网络可靠性分析及优化设计[D].广西大学, 2014, 11 (14) :132-135.

多径路由机制 第4篇

文献[3]指出多信道算法缓解无线网络拥堵的可行性。多信道算法作为提高网络性能的重要技术已广泛应用于无线基础设施网络,802. 11b /g作为目前应用最为广泛的无线电标准,工作在2. 4 G无线电频段,国际标准将此频段划分给11 ~ 13 个无线信道,802. 11 工作组对2. 4 GHz和5 GHz的频谱划分是多信道研究的先决条件[4]。在ad hoc中进行多信道研究也越来越受到国内外学者的重视,在不改变现有MAC层协议的条件下,由路由代理对底层信道进行分配,实现路由层与底层的跨层优化是灵活解决ad hoc中吞吐瓶颈问题的有效方案[5]。目前的多信道研究主要集中于多信道路由度量算法,Draves[6]等学者首先提出基于多信道传输时延期望的路由度量指标WCETT,也有学者在此基础上研究了多径路由下的MWCETT[7]。

虽然多信道多径路由度量的研究充分考虑了全网资源,但随着数据发送速率需求的增加,链路内的多信道资源仍得不到有效利用,对相邻节点间进行合理的信道分配是最大化信道使用率的有效途径。信道分配算法按分配颗粒度划分,可以分为数据包级别、链路级别、数据流级别和段级别信道分配[5]。在信道分配效率上,数据包/流级别与链路级别信道分配需要相应的同步调度算法,从而使下一跳邻居节点切换到相应信道,而段级别信道分配不需考虑信道同步调度与维护邻居信道使用表。因此,段级别信道分配避免了信道切换延时,具有更好的性能。

综上,为了解决高负载MANET环境下现有多信道多径路由性能恶化的问题,本文提出一种基于段级别信道切换路由的优化算法。通过添加分配子层实现底层信道的切换动态机制,对控制与数据分组进行信道分配管理,并对数据分组的发送信道进行自适应实时切换,实现了信道自适应负载均衡。本文在NS-2 仿真平台上实现了相应的可切换信道拓展模型,通过仿真对比,验证了优化算法的有效性。

1 算法设计

表1、表2 分别描述了本文涉及的相关符号与协议说明。

算法的设计主要分为两个方面的优化:

( 1) 降低MAC冲突时延导致的频繁路径切换,提高多径利用率。

( 2) 降低分组由于网络拥塞导致的丢包,利用多信道优势实现负载均衡,提高信道利用率。

1. 1 路由与信道初始化

3c-AOMDV全信道与全链路泛洪的广播机制会导致严重的冗余、竞争及碰撞。若在当前网络环境下未在路由层对底层信道进行指定,则所有报文将在信道间竞争收发,势必造成广播报文风暴与数据报文丢失为了有效降低广播报文的泛洪规模,3cAOMDV + 算法规定: 当有通信需求时,由源节点首先初始化路由请求,同时将生成的RREQ报文经由三个信道广播。邻居节点将第一次收到路由请求报文的接收信道初始化为发送信道,若此邻居节点为路由请求的目的节点,则直接经由RREQ接收信道向源节点发送RREP报文; 否则,将收到的RREQ分组从初始化信道转发出去,直到目标节点收到RREQ并返回RREP报文,中间节点丢弃其他接收信道的RREQ分组。这种优化算法通过降低RREQ报文的信道占空比,从而降低信道中收发数据与RREQ报文之间的不必要冲突。路由与信道的初始化流程如图1 所示。

图2 表示优化后的11 节点MANET中路由与信道的初始化过程。设第1 组连接为节点1 ~ 节点10,随后第2 组连接开始建立。优化后的3c-AOMDV + 通过在路由协议中实现对RREQ发送信道的限制,降低了不必要的信道使用,使信道分配更为合理。

1. 2 基于负载均衡的路由层信道切换

本文提出的3c-AOMDV + 算法,在路由与信道初始化阶段限制了RREQ分组使用的信道,降低了并发分组导致的MAC冲突,有利于空闲信道的检测。在此基础上,本文进一步提出一种信道拥塞切换机制。由于切换算法实现于路由层。优化算法的节点路由表如表3 所示。在AOMDV节点路由表的基础上,增加了信道使用列表,包括当前段连接使用的信道编号Ch N与当前节点的非阻塞信道编号Ch Fre,通过查找节点的相关信道信息进行信道切换。

多信道路由协议在一定程度上缓解了网络负荷。但是对于3c-AOMDV路由协议,在数据发送过程中,当节点负载过高时,继续在此信道上进行数据转发可能导致网络拥塞,从而造成缓冲区溢出、数据分组被丢弃。信道的切换过程见图3,算法规定: 节点在每次发送数据分组之前,检测包括当前使用信道在内的所有信道的负载水平。当检测到当前使用信道对应的接口缓存队列长度超过最大缓存队列长度时,且当前节点具有非阻塞信道,则将工作信道切换到该信道。

2 基于NS2 的多信道路由建模

为了在现有的模拟器NS2 上实现多信道[8]切换路由模型,该方案需要对现有的仿真系统作如下改变:

( 1) 改变移动节点模型的TCL脚本,由tcl脚本实现信道的创建过程。

(2)添加对应系统组件的C++代码支持。

(3)优化路由协议实现信道切换算法。

2. 1 拓展NS2 仿真架构

节点由底层向上实现模型拓展,区别于Ramam[9]模型从多接口的角度创建多信道的分析方法,优化模型直接从最底层信道开始由下向上进行拓展,如下所示:

Step1: 改变节点配置( node-config) 与无线移动节点创建( create-wireless-node ) 的配置脚本,在node-config中添加信道拓展代码,拓展的初始化变量为信道数变量chan Num_,在create-wireless-node中添加相应信道的接口拓展代码,拓展参数包括与该信道相连接的接口、缓存队列及MAC组件。

Step2: 为了实现在编写的仿真脚本中的灵活初始化信道数变量chan Num_,所以在ns-lib. tcl中添加chan Num{ } 过程,由该过程获得仿真脚本中定义的信道数并初始化为chan Num_。

Step3: 为了实现拓展模型对单信道的支持,在ns-lib. tcl中添加get-chanNum{ } 过程,用于在脚本中获得拓展后的信道数目,并判断仿真脚本中是否指定了信道拓展。若仿真脚本中没有定义chanNum_,则只执行单信道路由协议。

Step4: 在ns-mobilenode. tcl中为各接口初始化链路组件,先通过getchan Num{ } 过程获得信道数目chan Num_,根据信道总数初始化相应接口的链路组件ll( i) 及对应的target( i) ,其中i ≤chan Num,并为对应接口的分配ARP代理服务。

Step5: 修改移动节点的C ++ 代码,以适应节点的多信道拓展要求。

Step6: 在仿真脚本中通过设置信道数目chanNum_并执行add-channel{ } 过程实现多信道创建。

2. 2 拓展NS2 移动节点的底层组件

在标准的NS2 仿真模型中,移动节点模型Mobile Node仅配置一组底层组件,包括: ARP、接口队列、MAC、相应信道,路由算法也只支持单信道路由协议,并不支持多信道多接口。

NS2 在单信道单接口( SISC) 下的链路模拟如图4 所示。发送报文q直接通过Rt Agent传向下层target,由target_对应的底层组件down-target指针处理报文q向下传输,Simple Link负责模拟相邻节点链路的队列、时延与发送带宽,最终由链路对端节点B通过Simple Link接收报文q,节点B的target将up-target指针处理后的报文q向上传给B的Rt Agent。在此模型中,路由代理下的底层组件是唯一的。

为了实现MIMC要求,首先要对节点的底层组件进行拓展。如图5 所示,拓展后的节点结构保留了原路由代理Rt Agent与MAC层的全部功能。

2. 3 实现路由层对信道的切换要求

在ad hoc网络中,多信道切换的研究主要集中于路由层切换和底层切换。路由层切换主要为路由代理对接口的切换,而底层切换又可以分为MAC层对接口的切换与接口对信道的切换。文献[6]中的基于联合信道分配的MAC层对接口的切换方案需要复杂的算法处理RTS /CTS控制报文,且算法的实现需要改变现有MAC层的硬件结构,因此该方案并不理想。接口对信道的切换研究则主要针对于网络接口数小于信道数的无线模型,移动节点必须通过维护信道使用列表,并执行相应的信道调度算法将工作信道切换到相应接口,故切换算法带来了巨大的控制代价与切换延时。随着网络接口硬件成本的下降,无线设备配置多个网络接口成为可能,当网络接口数与信道数相等时,若将信道与接口实现对应,并在路由层通过切换接口实现信道切换,就能很大程度上避免上述问题的发生,区别于底层信道切换,在路由层的实现方案则具有更大的灵活性,节点可以充分考虑信道利用率与路径代价,实现全网资源的有效利用。

路由层实现信道切换伪代码如下所示:

Procedure:

路由代理rtagent;

信道索引channel(i);

接口索引interface(i);

路由表中记录的接口编号rt-if;

在NS2 中,事件( event) 的发生是由时间调度器( Scheduler) 控制实现的,Scheduler通过Schedule函数将目标事件交给处理器( Handler) ,而路由层所发生的事件是报文( q) 的存储转发,由target处理q的链路层流向。所以,为实现路由层对链路层组件与相应接口队列的访问,在路由代理Rt Agent的设计中需要添加targetlist[]与ifqueuelist[]指针数组,从而实现了通过控制信道参数ch来控制报文传输所相应的信道流向。

设信道总数为N,则当前节点的Rt Agent下对应的底层组件总数为N,故在路由协议中应添加对下层组件的分配指定。节点通过调用schedule( targetlist( i) ,p) 函数对报文进行调度,targetlist( i) 的索引值i决定了底层信道索引,所以底层模块的添加改变了原有模型从路由层到链路层的数据流向,模型以较小的切换复杂度实现信道切换。

3 优化协议的仿真

3. 1 仿真参数设置

本文采用ns-2. 34 对该优化多信道多径路由协议进行了仿真比较分析。其中,无线通信距离为250 m,载波侦听范围为550 m。分别由setdest与cbrgen生成节点移动模型与流量模型,50 个移动节点随机分布在800 m × 800 m的区域中,最大移动速度为20 m/s,暂停时间为0。网络从2 s开始建立第1 组UDP连接,以后每间隔15 s随机增加一组连接,研究以50 packets/s的发送速率模拟高负载网络环境,包大小为512 B,持续发送70 s,全程仿真时间为210 s,故当第6 组UDP连接加入网络时,第1组UDP数据已经发送完毕。以次类推,即从第5 组UDP开始,全网保持五组源目节点对进行数据发送。

3. 2 仿真结果与数据分析

仿真的统计结果定义为从第1 组UDP连接开始发送到第i组UDP连接发送完成的平均值,从丢包率、吞吐量、时延三个方面对MPR( AOMDV) 、3cMPR( 3c-AOMDV) 、3c-MPR + ( 3c-AOMDV + ) 进行对比分析。仿真结果表明,当Flow( i) 的数据发送速率需求较高且Fnum≥2 时,信道拥塞程度加剧。

3. 2. 1 吞吐量

图6 为吞吐量对比图。其中,虚线表示从第1组UDP连接开始到第i组UDP连接发送完成的平均数据发送速率,表示单位时间内发送数据比特数目。吞吐量定义为单位时间内接收数据比特数目,所以网络中吞吐量曲线越接近虚线说明性能越优。从吞吐量对比图可以看出,MPR表现极差,最大吞吐量仅为250 Kb /s,3c-MPR与3c-MPR + 在网络中连接数目小于等于3 时,曲线基本与发送速率曲线接近,当第4 组数据连接加入网络,基于自适应信道负载均衡策略的3c-MPR + 的性能明显优于3cMPR,且更接近于数据发送速率曲线。

3. 2. 2 丢包率

图7 对丢包率进行了对比分析。从第1 组UDP连接发送开始到第2 组UDP发起之前,以AOMDV为代表的MPR丢包率为9. 51% ,3c-MPR与3cMPR + 的丢包率均为0。间隔15 s,第2 组UDP连接开始发送数据,MPR的丢包率随连接数目的增加急剧增加,网络已经基本处于瘫痪状态,由于多信道优势,3c-MPR与3c-MPR + 的分组投递性能均优于MPR。当网络中连接数目低于或等于信道数目,3cMPR与3c-MPR + 分组投递可靠性基本一致。从45s开始,第4 组数据连接加入网络,3c-MPR的丢包率迅速增加到18% ,而3c-MPR + 丢包率不到1% 。因此,3c-MPR + 的分组投递性能更为优秀,满足较高可靠性网络的通信需求。

3. 2. 3 时延

图8 为时延对比图。MPR的平均端端时延随连接数目的增加迅速增加。由于3c-MPR与3cMPR + 三个信道可以同时进行数据收发,所以平均端端时延明显低于单信道MPR。优化后的3c-MPR +由于限制广播路由报文的泛洪次数,提高了空闲信道比例,在一定程度上避免了路由广播控制报文在MAC层与数据报文的冲突。 一方面降低了由于MAC冲突造成的丢包现象,另一方面降低了由于冲突在MAC层的退避算法带来的时延。从三个路由协议的时延对比中可以发现,优化后的3c-MPR + 大大降低了传统多信道路由协议的时延,平均时延低于0. 2 s,性能较3c-MPR提高了0. 2 ~ 0. 4 s。

4 结束语

本文针对以AOMDV为代表的多径路由协议在高负载网络下存在的问题,提出利用多信道改善网络性能,并在传统多信道路由协议的基础上提出一种适用于MANET的自适应多信道路由分配算法。优化后的多信道协议通过在路由代理中添加对底层信道的切换机制,对路由控制报文与数据发送报文进行信道分配管理,一方面限制广播控制报文的发送次数,通过降低控制报文在MAC层与数据报文的冲突次数,提高了时延性能与投递可靠性,另一方面通过检测信道空闲情况,对数据发送报文的传输信道进行实时切换,将数据传输信道切换到空闲信道,实现了信道自适应负载均衡。同时,由于协议降低了由于MAC层冲突避免时延过大带来的错误反馈导致的频繁路径切换,因此提高了路径可靠性,有效降低了路由发起频率,降低了全网数据发送端端时延。

仿真结果表明,优化后的切换算法在时延与分组投递水平等反方面均优于传统多径路由与传统多信道多径路由,适用于高数据发送速率需求的MANET。

参考文献

[1]王鲁光,贾智平,李新.AODV和AOMDV路由协议性能分析与比较.计算机应用,2010;30(3):740—744Wang Luguang,Jia Zhiping,Li Xin.Performance analysis and comparison of AODV and AOMDV routing protocols.Journal of Computer Applications,2010;30(3):740—744

[2] Beltagy I,Youssef M,El-Derini M.A new routing metric and protocol for multipath routing in cognitive networks.Wireless Communications and Networking Conference,Mexico:IEEE Press,2011:974—979

[3] Lo B F.A survey of common control channel design in cognitive radio networks.Physical Communication,2011;4(1):26—39

[4] Raniwala A,Tzicker Chuieh.Architecture and algorithms for an IEEE 802 .11-based multi-channel wireless mesh network.INFOCOM.USA:IEEE Press,2005:2223—2224

[5] Bian K,Park J.Segment-based channel assignment in cognitive radio ad hoc networks.The 2nd International Conference on Cognitive Radio Oriented Wireless Networks and Communications,USA:IEEE Press,2007:327—335

[6] Draves R,Padhye J,Zill B.Routing inmulti-radio,multi-hop wireless mesh networks.The 10th Annual International Conference on Mobile Computing and Networking.USA:ACM Press,2004:114—128

[7] 乔平安,邵凯,刘运爽.基于无线ad hoc的多路径多信道路由度量准则.电子科技,2015;28(8):60—62Qiao Pingan,Shao Kai,Liu Yunshuang.Research on multi-path multi-channel routing metrics in wireless ad hoc networks.Electronic Sci&Tech,2015;28(8):60—62

[8] 符琦,陈志刚,蒋云霞.基于NS-2的多接口多信道仿真模型扩展研究.计算机工程,2013;39(4):113—117Fu Qi,Chen Zhinggang,Jiang Yunxia.Research onmulti-interface multi-channel simulation model extension based on NS-2.Computer Engineering,2013;39(4):113—117

多径路由机制 第5篇

移动Ad hoc网络是不依赖于任何固定基础设施的多跳临时的自组织网络。由于移动Ad hoc网络具有拓扑动态变化、自组织、能量和带宽有限等特点,使得它在灵活和实用的同时也存在着一些问题,其中节能和稳定的路由协议更是成为研究的热点与难点。AODV[1] 是Ad Hoc网络中按需生成路由方式的典型协议,节点要给目的节点发送数据分组时建立路由,是一种单径路由协议。 文献[2]基于多路径的思想对AODV进行扩展,提出了AOMDV,它是一种典型的按需多径路由协议,“多径路由”能够使网络负载均衡并提供很好的容错能力,减轻网络拥塞的状况。

本文结合多径路由[3]和扩展环搜索[4]的思想提出了一种基于主备链路稳定性的节能多径路由协议AOMDV-ES,通过转发状态的设置来减少二次搜索时的盲目洪泛开销,并通过对历史跳数记录的提取和计算,得到估算的到目的节点的跳数,从而确定恰当的搜索范围,减少路由发现过程中控制消息的洪泛,节省路由发现的能量。在选路径阶段,综合考虑节点的能量、队列、路径跳数,并采用主备链路的方式,不仅能够选择较优的稳定链路,而且减少大量的维护多条路径的开销,从而提高网络的稳定性和整体性能。

1 AOMDV-ES协议

AOMDV协议在路由发现阶段寻找多条开环的和链路不相交的路由,在路由维护阶段维护多条路径,在主路径失效的时候使用备份路径(冗余路径)来取代中断路径,快速有效地恢复路由,能够提供很好的容错能力。但是AOMDV的洪泛路由发现方式会导致控制开销过大;选择的最短时延路径不够稳定;如果动态维护多条路径则开销更大,多径的优势会被中和掉[5]。针对这些问题,本文结合扩展环搜索的思想提出一种基于主备链路稳定性的节能多径路由协议。

扩展环搜索(ERS)是一种能够避免广播风暴的可控制的洪泛技术。为了控制移动Ad hoc网络的洪泛规模,ERS算法在路由发现阶段,在RREQ消息中用一个预先定义的TTL值指定一个洪泛初始范围。如果没有发现有效路由,源节点就会在之后增大TTL值并广播一个更新后的RREQ来进行一个更大范围的搜索。

1.1 基于节能方案的ERS初始化设置

在AOMDV-ES协议的路由发现阶段要进行两方面的初始化,一个是节点状态参数的初始化,另一个是基于历史记录的初始化。

(1) 节点状态参数的初始化

AOMDV-ES协议在路由发现阶段对节点的状态进行设置,实现一种可控制的洪泛技术。为了避免多轮次的扩展环搜索造成不必要的节点重复接收和转发路由请求消息,在AOMDV-ES协议中为每个节点设置了状态参数,将节点的状态参数保存到一个节点数据结构中:Tran是布尔类型(初始值为True),记录节点是否转发RREQ消息;Pre是前驱节点的地址,是节点收到的第一个RREQ消息的前驱节点地址,源节点将Pre的值设置为它本身的地址,中间节点的Pre值设置为发送给中间节点路由请求消息的节点的地址;FT是布尔类型(初始值为True),标识节点是否是第一次转发RREQ。此外,在RREQ消息中增加一个前驱节点地址,用来记录每次收到广播消息的前驱节点,增加一个标志位用来标识此次路由发现进行的是否是第一个轮次的搜索过程。

在路由发现阶段会进行多轮次的扩展环搜索,在第一轮的搜索中只负责记录节点的状态参数,在第二轮以及以后的路由发现中节点可以使用这些状态参数来决定是否参与路由请求消息的转发。

在第一轮的扩展环搜索中,每个节点在发送路由请求消息的时候都不需要考虑Tran状态,只需要根据收到的消息的Pre字段,来对节点的Tran值进行设置。

如图1所示,当有一个节点S有数据想要发送到目前还没有到达路由的目的节点的时候,节点需要发起一次路由发现过程,发送一个路由请求(RREQ)消息,源节点S将Pre值设置为本身的地址,S给所有的邻居节点广播一个RREQ消息并将自己的FT值设为False。邻节点A、B、C首先收到这个RREQ, 然后查看各自的路由表,是否有到目的节点的路由,如果有则对S节点做出响应,如果没有,将自己的Pre值设为S,并将本节点的地址封装到RREQ消息中,继续广播RREQ消息。

节点C在广播RREQ消息之后将自己的FT值设为False。节点S和节点E收到该消息并对消息进行处理。节点S收到该RREQ判断前驱节点为S,和自己的地址相同,那么S将自己的Tran状态设为True。节点E也对该路由请求消息做出处理,首先它判断自己是第一次收到这个RREQ,那么只将自己的Pre字段设为节点C的地址,并将Pre封装到RREQ头部,继续进行转发。当节点C第二次收到RREQ这个消息时,判断消息中的Pre字段和自己的地址相同,那么将Tran字段设置为True。按照这种初始化过程,节点的最终状态如图2所示。可以看到此时节点S、节点B和节点C的Tran值为True,在第二轮和以后的搜索中,节点S、节点B和节点C可以转发路由请求消息,而节点A在下一次搜索中不参与转发。依照这种方法,节点能够自适应地改变自己的状态,避免在多轮次的搜索中,多次重复转发路由请求消息,节省能量,减少网络负载,同时也在网络中减少很多的消息碰撞。

(2) 基于历史记录的初始化

我们知道最好的情况就是TTL的值等于到目的节点的距离,但是通常很难估算合适的TTL值。在提出的新协议中,节点根据历史记录来动态地调整搜索的参数,可以计算出更合适的初始生存时间、每次扩大搜索范围的步进值以及搜索范围的最大门限值。

现设到目的节点的距离为L,其取值由两方面信息决定,一个是即时的跳数信息,一个是历史记录获得的平均跳数信息,分别记为Hops_Last和$\overline{{\rm H}ops{}_{{\rm N}}}$。

$L=\alpha {\rm H}ops\_Last+\beta \overline{{\rm H}ops{}_{{\rm N}}}$ (1)

其中α和β表示归一化系数,并且α+β=1。

下面我们将讨论如何得到归一化系数。主要考虑如下两个方面:

(1) 时间因素

在移动Ad hoc网络中,节点在任意时刻可以向任意方向移动,但是距离当前时间最近的时间里,节点所记录的节点跳数信息能较好地反映节点现在的状态,进而更好地估计距离目的节点的跳数距离。反之,如果距离当前时间的时间间隔较长,节点所记录的节点跳数信息会在很大程度上与节点现在的状态偏差很大。因此,我们引入一个参数η,表示时间因素。时间因素η的计算方法如下:

$\eta =\lambda {}^{\frac{{\rm T}{}_{now}-{\rm T}{}_{last}}{{\rm T}{}_{unitage}}}$ (2)

其中,Tnow表示当前的时间,Tlast表示节点所记录的最近一条跳数信息的时间,Tunitage 是一个小的时间段。λ是一个范围为( 0, 1 ]的常数,初始值设为0.7,以后可以适当地进行调整。η可以从时间因素的方面表示节点当前的状态信息与节点所维护的节点跳数信息表中的最后一次记录的关系的强弱。

(2) 节点跳数信息的平均情况

我们引入方差的计算,计算方法如下:

$D{}_{{\rm H}{\rm O}{\rm P}S}{}_{{\rm N}}=\frac{E(D{}_{{\rm H}ops{}_{{\rm N}}-1+\overline{{\rm H}ops}{}_{{\rm N}}{}^2})+{\rm H}ops\_Last{}_{{\rm N}}{}^2}{{\rm N}}-\overline{{\rm H}ops}{}_{{\rm N}}{}^2$ (3)

在这里,为了保持单位的一致,使用方差的算术平方根$\sqrt{D{}_{{\rm H}ops{}_{{\rm N}}}}$。显然,若标准差越大,说明波动情况较大,即节点的状态越不稳定,那么计算出的到目的节点的距离越不准确。

可以知道,在与记录上一条节点跳数信息的时间间隔较短时,上一条节点跳数信息在估算到目的节点距离时有很大的参考价值,而当节点移动性比较小,或者说当节点跳数信息表中记录的跳数信息比较稳定的时候,我们得到的节点平均跳数信息能比较好发挥估算到目的节点距离的作用。通过这两个因素的计算,可以得到归一化系数的计算方式:

$\alpha =\frac{\eta }{\eta +1/\sqrt{D{}_{hops}{}_{{\rm N}}}}$ (4)

$\beta =\frac{1/\sqrt{D{}_{hops}{}_{{\rm N}}}}{\eta +1\sqrt{D{}_{hops}{}_{{\rm N}}}}$ (5)

将式(4)和式(5)代入到式(1)中,可以得到:

$L=\frac{\eta }{\eta +1/\sqrt{D{}_{hops}{}_{{\rm N}}}}{\rm H}ops\_Lost+$

$\frac{1/\sqrt{D{}_{hops}{}_{{\rm N}}}}{\eta +1/\sqrt{D{}_{hops}{}_{{\rm N}}}}\overline{{\rm H}ops{}_{{\rm N}}}(6)$

由于在搜索过程中TTL的选择直接影响到搜索到目的节点的效率,如果能把TTL值恰好等于节点到目的节点的距离,那么就可以只进行一次搜索就找到目的节点,显然这是最好的选择。本文中通过式(6)可以很好地估计到目的节点的距离。因此,这里设置初始生存时间的初值为L。即: (TTL)=L。

如果节点在第一轮的搜索中没有找到目的节点或者到目的节点的路由,就会增加一个步进值,步进值的选取需要考虑到节点的稳定程度,综合考虑,将计算得到的标准差作为搜索时的步进值。即:搜索时的步进值=$\sqrt{D{}_{{\rm H}ops}{}_{{\rm N}}}$。

当然,搜索过程不可能无限制地进行下去,当搜索的范围达到门限值的时候,就会采取洪泛的方式。选择这个门限值的时候要综合考虑到估算出的到达目的节点的距离以及记录的节点跳数信息的稳定程度,将门限值定义为:搜索范围的门限值$=L+2\sqrt{D{}_{{\rm H}ops{}_{{\rm N}}}}$。

综上所述,节点的初始化设置:Tran=False;FT=True;Pre=NULL(源节点的Pre字段初始化为源节点自己的地址)。搜索初始化设置:初始生存时间(TTL)=L;搜索时的步进值$=\sqrt{D{}_{{\rm H}ops{}_{{\rm N}}}}$;搜索范围的门限值$=L+2\sqrt{D{}_{{\rm H}ops{}_{{\rm N}}}}$。

1.2 AOMDV-ES的节能路由发现过程

当一个节点需要一条到达某个目的节点的路由,但是没有现成的可用路由的时候,该节点就发送一条路由请求消息,发起一次路由发现过程。下面给出路由发现的实现过程:

① 初始设置节点状态参数:Tran=False,FT=True,Pre=NULL(源节点的Pre初始化为源节点自己的地址)。

② 设置搜索的初始化状态:初始生存时间(TTL)=L;搜索时的步进值$=\sqrt{D{}_{{\rm H}ops{}_{{\rm N}}}}$;搜索范围的门限值$=L+2\sqrt{D{}_{{\rm H}ops{}_{{\rm N}}}}$;超时时间=当前时间+源节点可以等待RREP的时间。

③ 源节点发起一次路由发现过程,广播RREQ消息。

④ 接收RREQ消息,判断是否是源节点接收到该消息,如果是,先将Tran的值设为True,再丢弃该RREQ消息,结束处理过程。

⑤ 如果收到的是重复的RREQ消息,判断Pre的值和自己的地址是否相同,如果相同,将Tran的值设为True。如果不同,则丢弃该RREQ消息,结束处理过程。

⑥ 建立反向路由。如果有到目的节点的地址,则返回RREP,并进行数据传送。

⑦ 如果设定的超时时间小于当前时间,就重启节点状态,将Tran的值设为False,将FT的值设为True。

⑧ 如果Tran=False并且FT=False并且TTL>2,就把这个RREQ丢弃,结束此次搜索过程。

⑨ 如果节点生存时间(TTL)已经减少到0,那么丢弃这个RREQ消息,结束处理过程。

⑩ 更新节点Pre字段,TTL=TTL-1,重新广播RREQ消息后,将FT值设为False,重新设置超时时间,继续进行搜索。

1.3 AOMDV-ES的路径选择方案

由于移动Ad hoc网络中的节点能量有限而且拓扑结构动态变化,在这种条件下一定要考虑稳定性的问题,选择稳定的路由,减少由于路径的断开导致的路由重构,从而延长网络的存活时间,提供更好的传输服务。

传统的AOMDV路由协议维护多条路径,传输数据的主路径采用最短时延的路径,对多条路径的维护会在控制包的数目、存储空间等方面产生很大的开销,如果开销过大,多径带来的优势就会被这些开销折中掉。而且,如果有关键的节点从网络中移除,很可能造成所有链路发生故障,这样仍然需要重新发起路由发现过程,这也将带来端到端延时的增大。因此,AOMDV-ES协议在路径的选择方面还考虑了稳定性的因素。

在AOMDV-ES协议中主备稳定链路的实现主要考虑了能量因素、队列长度因素、路径跳数三个方面。下面将就这三个方面作具体介绍。

(1) 能量因素

由于移动Ad hoc网络中的节点能量极其有限,而处理消息和数据会消耗大量能量,如果在路由选择阶段选择能量较少的节点,必然会加快其能量的耗尽,这样的链路更易断开,造成不稳定。如式(7)所示作为节点的能量消耗参数:

$C{}_i\left(n\right)=\frac{E{}_r^i}{E{}_c^i}$ (7)

其中,$C{}_i\left(n\right)$即为节点i的能量消耗参数,E${}_r^i$表示节点i的剩余能量,E${}_c^i$表示节点i已经消耗的能量。节点i的剩余能量可以通过式(8)计算:

$E{}_r^i=E{}_0^i-{\displaystyle \sum _{k=1}^j{\rm P}}{}_k^i$ (8)

其中,E${}_0^i$表示节点i的初始能量,P${}_k^i$表示节点i传送第k个数据分组消耗的能量。

(2) 队列长度因素

如果队列中缓存的数据分组过多,就会使得节点的处理任务繁重而消耗能量过多,稍后到达的数据分组就也可能会因队列满而被丢弃,这样会增大丢包率和端到端延时。因此,在进行路径的选择时要尽量选择那些队列的处理能力比较强的节点。队列的繁忙程度可以表示为:

$B{}_i(n)=1-\frac{Q{}_c^i}{Q{}_0^i}$ (9)

其中,Bi(n)表示节点i的队列繁忙程度,Q${}_c^i$表示节点i的已经使用的队列长度,Q${}_0^i$表示节点i整个队列长度。

(3) 路径的跳数

因为较少跳数的路径在进行数据传输时具有相对稳定、延迟较小、不容易发生断路的特点,所以在路径选择的时候考虑到跳数因素可以有效地减少由于再次进行路由发现引起的数据重传。现设Hi为路由ri的跳数,$\overline{{\rm H}}$为所有路由上的跳数的均值,计算$\overline{{\rm H}}$的公式如下:

$\overline{{\rm H}}=\frac{{\displaystyle \sum _{i=1}^{{\rm N}}{\rm H}}{}_i}{{\rm N}}$ (10)

最后,综合选择路由时需考虑的这三个因素经过归一化计算得到路由代价函数:

${\rm P}{}_i(n)=\alpha C{}_i(n)+\beta B{}_i(n)+\gamma \frac{{\rm H}{}_i}{\overline{{\rm H}}}$ (11)

其中Pi(n)表示路由代价,α、β、γ为和为1的归一化系数。使用这个路由代价函数综合考虑了节点的能量消耗、队列的繁忙程度以及路由的跳数,期望找到的路由能够满足节点生存时间长、能量消耗和繁忙程度低、路由总跳数少,选择的路由比较稳定,可以减少网络中断路和重新进行路由发现的次数,减轻整个网络的负担,延长网络的生存时间。

因为过多的路径会在控制包的数目和存储空间方面增加开销,所以在AOMDV-ES中主要采用两条路径,一条作为主路径,一条作为备用路径。不仅能够选择较优的稳定链路,而且减少了大量的维护多条路径的开销,从而提高了网络的稳定性和整体性能。

当一个节点能量耗尽或者移动导致链路断开时,就向其上一跳节点发送一个RRER消息。RRER消息中会包含到达源节点的路由、链路中断处节点上一跳地址、中断处节点的下一跳地址。源节点收到这条RRER消息后会将路由表中使用这个有中断部分的路由断开,使用备用路由来继续传送数据分组。

2 实验仿真及结果分析

2.1 仿真环境

本文在NS2[6]平台上采用的仿真场景是:1000m1000m的场地,共设置了50个移动节点,每个移动节点的信号覆盖范围为200m,初始能量为300J,节点间信道带宽为2Mb/s,仿真时间为500s。仿真选择CBR(Constants Bit Rate)数据源来产生UDP数据,最大连接数是10,发包速度为4packet/s,数据分组的大小为512字节。传输模型采用Two-Ray Reflection Ground Model,移动模型是Random WayPoint Model。在模拟实验中采用的是NS2平台的setdest工具来设置节点的运动场景,再使用cbrgen工具来生成数据流。

2.2 仿真结果分析

本文在进行模拟实验时主要改变了节点的最大移动速度以及节点的间歇停留时间两个因素,仿真结果是10次实验得到的平均值。

(1) 节点的最大移动速度对协议性能的影响

网络中节点的最大移动速度从0m/s每次递增5m/s,直到30m/s。在这个过程中,AOMDV-ES和AOMDV协议的各方面性能都有不同程度的下降,因为节点移动性的增大会导致网络拓扑频繁变化。从图3(a)中可以看出,AOMDV-ES总体的平均端到端时延小于AOMDV。但是当节点移动速度过大时,AOMDV-ES协议中历史记录信息的参考价值降低,还会造成多轮次的重新搜索,因此平均端到端延时比AOMDV略高。从图3(b)中可以看出,两个协议的递交率都随着节点最大移动速度的增大而小幅度地降低。但从图中可以看出,AOMDV-ES协议的递交率从整体上高于AOMDV协议。从图3(c)可以看出,随着节点最大移动速度的增大, AOMDV-ES协议比AOMDV协议的标准化路由开销增大的幅度要小,而且更平稳。

(2) 移动节点的间歇停留时间对协议性能的影响

移动节点的间歇停留时间从0s增加到300s,每次增加50s,AOMDV-ES和AOMDV路由协议的各方面性能都有所上升,因为随着网络中移动节点的间歇时间变大,网络拓扑结构就会变化缓慢,相对来说就比较稳定。在间歇停留时间不同时的平均端到端延时的比较如图4(a)所示。随着移动节点间歇停留时间的增大,两种协议的平均端到端延时整体上都呈递减趋势。当节点间歇停留时间较小时,移动性相对较大,AOMDV-ES的性能更好。从图4(b)中可以看出,随着节点间歇停留时间的增大,AOMDV-ES和AOMDV协议都表现出了分组递交率的增加,AOMDV-ES协议的分组递交率更高,变化更平稳。从图4(c)中可以看出,随着节点间歇停留时间的增大,两个协议的标准化路由开销均下降,而且AOMDV-ES协议比AOMDV协议开销更少。这是因为随着节点间歇停留时间的增大,网络拓扑变化较慢,用来动态建立和维护路由的开销就会减少。

结果总体显示,在不同的节点最大移动速度和不同的间歇停留时间场景下,AOMDV-ES协议的性能在总体上优于AOMDV协议。

3 结 语

本文提出了一个基于主备链路稳定性的节能多径路由协议,在路由发现和路径选择方面进行了改进。最后根据仿真实验显示AOMDV-ES协议提高了分组递交率,降低了端到端平均时延和标准化路由开销,并在整体性能上优于AOMDV协议。由于AOMDV-ES在路由发现时主要根据节点的稳定状态参数和历史跳数信息来进行,需要开辟空间来存储额外的数据结构,所以下一步工作是如何节省空间和简化计算过程方面存在较大的研究空间。

摘要：移动Ad hoc网络中的AOMDV协议是典型的多径按需距离矢量路由协议。由于移动Ad hoc网络资源有限,AOMDV协议洪泛路由发现方式会导致控制开销过大,选择的最短时延路径不够稳定,如果动态维护多条路径则开销更大,会抵消多径路由协议的优势。针对以上问题,结合多径路由和扩展环搜索的思想提出一种基于主备链路稳定性的节能多径路由协议(AOMDV-ES)。通过对AOMDV-ES协议和AOMDV协议在不同场景下进行仿真分析比较,结果显示AOMDV-ES协议的整体性能在路由开销、分组递交率和平均端到端延时方面较AOMDV协议有所改进。

关键词：MANET,AOMDV,扩展环搜索,节能,稳定

参考文献

[1]Perkins C,Belding-Royer E,Das S.Ad hoc On-Demand Distance Vec-tor(AODV)Routing[S].rfc3561.txt,2003.

[2]Marina M K,Das S R.On-demand Multipath Distance Vector Routing for Ad Hoc Networks[C]//Proceedings of IEEE International Confer-ence on Network Protocols,200l:14-23.

[3]Maysam Y,Hossein M,Nasser Y.Multipath Routing in Mobile Ad Hoc Networks:Design Issues[C]//12th International CSI Computer Con-ference(CSIC’07),Tehran,Iran,2007.

[4]Hassan J,Jha S.Optimising Expanding Ring Search for Multi-hop Wire-lessNetworks[C]//Proc.of IEEE Global Telecommunications Confer-ence.[S.1.]:IEEE Press,2004:1061-1065.

[5] Tekaya M,Tabbane N,Tabbane S.Multipath routing mechanism with load balancing in Mobile Ad hoc network [C]//2010 International Conference on Computer Engineering and Systems, 2010: 67-72.