基于多径路由负载均衡的动态源路由协议

1、多径路由是一种解决负载平衡的方法。所谓多径路由就是指一次路由发现的过程后可以发现多条到达目的节点的路由,然后根据需要使用这些路由来传输数据,以提高整个网络资源的利用率。近年来出现的一些多径路由协议大都是在DSR或是AODV的基础上改进得到的,如SMR8、AOMDV9、MSR10 、AODVBR11、NDM12等。 本文提出了一种具有较高负载均衡能力的多径路由协议。首先,研究了现有的无线WMN路由metric与多径路由协议解决平衡问题的方法。其次,在DSR协议的基础上提出基于多径路由负载均衡的源路由协议(load balancing dynamic source routing protocol

2、 based on multipath routing, LBDSRM。LBDSRM协议采用开销小的综合链路状态路由判据算法,并同时使用多径传输数据,有效地解决了网络动态负载均衡问题,实现网络资源的充分利用。最后,在网络仿真工具NS2环境下对LBDSRM、MSR以及DSR协议进行仿真模拟,比较了在相同环境下这几种路由协议的性能。实验结果表明,LBDSRM协议在诸多性能上,特别是动态负载均衡问题的处理上较其他协议更具优势。 1 相关研究现状 现有多径路由有两种基本的使用模式:a同时使用多条路径(同时多径;b先使用主路径,当主路径失效后再使用其替换路径(替换多径。在解决负载平衡问题上,同时多径模式

3、要优于替换多径模式。 基于DSR协议的MSR与SMR是典型的同时多径协议。MSR10是DSR的一种多径扩展,把按需、多径和源路由结合起来。协议的重点是降低分组发送延迟,提高整个网络的负载均衡能力。该协议以延迟作为路径规格的度量,并通过RTT的方式感知路径的状态,根据探测结果采用带权重的循环调度算法,合理地把数据流分摊在多条互相独立的路径上,从而达到负载平衡、充分利用网络资源的目的。SMR8也是一种按需路由协议,其采用分流的处理方法,即在两条特殊的路径上分配数据包,其中一条是最短路径,另一条是与最短路径具有最大独立性的路径。这种分流的办法不但能更有效地利用网络资源,提高整个网络的负载均衡能力,而

4、且还可以在传输负载很大的情况下,有效地防止网络拥塞。 在AODV协议的基础上扩展而来的有AOMDV9 、AODVBR11、NDM12等。AOMDV(按需多路径距离矢量路由协议在路由发现过程获取多条无环且链路不相交路径,它能够充分利用AODV中已有的路由信息,所以在计算多路径时只需要增加少量的额外开销。AODVBR(后备路由协议在回送路由应答消息过程中引入一些新思想,在不增加控制信息个数的条件下,维护了多条到目的节点的路由。NDM协议中增加了路由请求节点表,用于记录从源节点s到目的节点d所经过的 每个中间节点;NDM的RREP中返回独立的路由,考虑到路由开销及复杂度的因素,它一般都根据具体情况选

5、择路径条数。 现有的多径协议都存在一些缺陷,如MSR 的缺点是发包时的处理开销明显增加;SMR 存在传输RREQ 包过多, 给目的节点带来额外的数据包排序等问题;AOMDV也存在数据传输中经常不能使用最短路径等问题。所以,对多径路由协议的优化还有较大的空间。 2 LBDSRM设计 DSR采用源路由方法,源主机确定地知道它有哪些可以到达目标主机的路径,可以自由地从中选择合适的路径来发送数据包,因此,本文基于DSR设计多径路由负载均衡的动态源路由协议(LBDSRM。 2.1 负载平衡的metric WMN路由协议中的路由判据包括跳数、RTT、每跳包对时延、ETT、ETX、 WCETT13等。跳数是

6、通过统计链路中节点的个数来衡量链路质量。RTT(单跳往返时间是通过测量单播侦测分组的往返时间来衡量链路质量。每跳包对时延是通过测量一个节点连续发给邻居节点两个数据包之间的时延来分析链路状态。ETX(期望传输次数是通过统计邻居节点广播测试分组的丢失率来估算发送单播数据分组的重传次数。WCETT(加权累计ETT是结合了整条通路的吞吐量会受控于瓶颈信道的影响与跳数增加对资源的消耗两种思想来找出加权平均值。 对于以跳数作为判据标准的算法,虽然非常简单,但是在密集网络中可能会存在有很多相同跳数的最短路径,如果在很多最小跳数判据中只是任意选择路由,这就很可能没有选到最优链路。而采用RTT、每跳包对时延、E

7、TX等算法作为路由选择标准时,虽然在许多方面比采用跳数作为路由标准有了很大的进步,但是由于它们都是以发送探测数据包的方式来收集链路的状态信息,会给整个网络系统带来一定的额外开销。作为在多信道系统的基础上使用的WCETT,能够很好地解决吞吐量、带宽、跳数、时延等诸多因素的平衡,但仍没有解决收集链路信息开销大的问题。 在LBDSRM协议中,本文设计了一种开销小的综合节点状态的路由判据(metric,以提高协议的运行效率。Metric计算基于节点信息采集,包括带宽、发送数据量、缓存空间等信息。 节点的实时网卡带宽在一定程度上能够反映节点的通信链路状况。定义无线路由节点i的实时网卡带宽为Bi。同时记录

8、节点i的接收(Ri和发送(Si数据的数量,定义无线路由节点i的吞吐性能为Ci=Ri+Si。 数据发送与接收缓冲队列中的待处理数据包的数量能够反映节点链路的状态,如:当路由节点i的发送队列长度与队列最大长度之比超过60%时,拥塞指数定义为SQi=1;当路由节点i的发送队列长度与 队列最大长度之比超过80%时,其拥塞指数定义为SQi=2;其他情况下,SQi=0。节点i的接收队列饱和程度RQi也是如此。 因为路由的计算与最后路由的使用之间有一段时延,路由判据中最好要有对未来一段时间内拥塞趋势的预判能力,所以在路由判据的计算中引入拥塞预判机制。具体方法是把当前的饱和度总和(包括接收队列与发送队列与前一

9、次统计的饱和度总和作一个对比,并定义一个预判因子Pi与饱和度差值阈值,有: a当前的饱和度总和前一次统计的饱和度总和,且差值,那么Pi=1; b当前的饱和度总和前一次统计的饱和度总和,且差值,那么Pi =-1; c当前的饱和度总和与前一次统计的饱和度总和差距,那么Pi=0。 根据上面收集的关于节点的数据,可以定义节点i与其邻居节点之间的综合链路权重值为Wi,其计算方法为 Wi=CiBi10+SQi+RQi+Pi 为了使没有拥塞节点的链路相对于有拥塞节点的链路更具优势,采用一种超限累加的机制来改善这一特殊情况下路由选择的处理。具体方法是:计算单个节点的权重值时,根据网络具体情况设置一个拥塞阈值n

10、,当单个节点的权重值超过拥塞阈值时,认为该节点发生拥塞,并用超出部分的数值来衡量拥塞程度,在计算权重值时将超出部分累加到最终的权重值Wi中。改进后节点的权重值计算方法为#p#分页标题#e# a当Wi n时,Wi= Wi+(Wi-n ; b当Wi n时,Wi= Wi。 综上所述,对于有着k个节点的路径的权重总值Wp的计算式如下: Wp=ki=1(CiBi10+SQi+RQi+Pi 2.2 负载均衡的多径路由机制 LBDSRM协议中负载均衡的多径路由算法的主要思想是:在路由发现过程后,按每条路径的综合链路总权值大小来按比例分配发送任务,同时使用多条较优路径发送数据;在发送数据的同时,每个节点实时监

11、控自己状态,一旦有较大变化及时通知源节点进行必要的调整。算法还使用了适时退避机制,使多径传输任务与只能单径传输任务在发生网络资源争用的情况下具有一定的网络公平性,同时也能有效避免这种情况下瓶颈节点的拥塞。算法较好地实现了网络动态负载均衡,大大提高了整个网络资源的利用率。 算法中需要设置多个参数值,经过多次仿真比较,发现在不同网络环境下算法的最佳配置值有所不同。现以仿真的网络环境为例进行最佳配置,并描述如下: 设源节点S在路由发现过程中共发现到达目的节点D有K条有效路径,并按累计的权值大小排列顺序,依次为P1,P2,PK。 a当K=1时,只有一条路径,该路径P1的任务分配比例为100%。 b当K

12、=2时,有两条路径,设X=(WP2- WP1 / WP1,有: 当X5%时,P1与P2的任务分配比例分别为50%; 当20%X5%时,P1的任务分配比例为70%, P2的为30%; 当40%X20%时,P1的任务分配比例为90%, P2的为10%; 当X40%时,P1的任务分配比例为100%, P2的为0%。 c当K=3时,有三条路径,设X= (WP2- WP1/ WP1 (先将P2、 P3看成一个整体,有: 当X5%时,P1与P2、P3的任务分配比例分别为50%。 当20%X5%时,P1的任务分配比例为70%,P2、P3的为30%。 当40%X20%时,P1的任务分配比例为90%, P2、P

13、3的为10%。 当X40%时,P1的任务分配比例为100%, P2、P3的为0%。 对于P2与 P3的任务分配,参照K=2时的算法进行计算分配。 d当K3时,选取最佳的前三条路径,按照K=3时的算法进行计算分配。 当能够多径传输的任务与只能单径传输的任务在某个节点或某段链路上发生争用的情况下,为了使只有单径路由的节点在发送数据时具有一定的网络公平性,节点就启动适时退避算法,具体描述为:如果节点当前W 为了避免在路由发现过程中产生过多的路由响应,协议还规定了产生路由响应的次数。LBDSRM协议中最多只使用三条路径,所以路由发现中不需要找到太多的路径。对于中间节点一个RREQ只能响应一次,而对于目

14、的节点一个RREQ可响应最先到达的三次。这样即能使源节点获得较好的多条路径信息,又不至于导致路由响应泛滥而影响网络的性能。 多径路由负载均衡算法的流程如图1所示。 2.3 LBDSRM协议的工作实例 如图2所示,当节点S有数据需发送至D时,在路由发现中发现了通往节点D的三条路径(当前无其他节点争用,其表明路径状态的综合链路权值分别为路径1=18、路径2=24、路径3=15。根据LBDSRM协议中多径路由算法三条路径被分别分配了27%、3%、70%的传输任务,主要任务放在了状态最佳的路径3上,并开始按此比例在三条路径上同时发送数据。 如图3所示,当运行一段时间后节点A需要发送数据至B,其只发现了

15、一条通往目的节点的路径(与S节点任务使用的路径3重合。为了使多径传输任务与只能单径传输任务在发生网络资源争用的情况下具有一定的网络公平性,所以节点A向该路径上的其他节点发送回避通告,使节点E、F的状态权值从2变为拥塞极限值6,并通告给节点S,这时节点S的发送任务还未完成,所以它将使用新的链路状态数据重新分配三条路径的发送任务。新的路径状态的综合链路权值分别为路径1=18、路径2=24、路径3=23。根据LBDSRM协议中多径路由算法三条路径被分别分配了70%、15%、15%的传输任务,主要任务放在了路径1上。这样有效地减轻了有争用节点的路径3 路状态与节点权值记录表所记录的并正在使用的历史记录

16、权值差距达到链路变化通报的阈值f时,表示当前的链路状态与原来的状态相比产生了较大变化,这时通过向源节点发送路由节点状态变化通告报文,来通知源节点根据报告的内容有效调整源节点多径路由的任务比例。多径路由机制与节点变化报告机制的结合可以有效地降低网络负载不均的概率。 c节点实时监控单径路由与多径路由的链路竞争。节点在检测到自己是单径路由任务与多径路由任务的竞争节点时,根据节点的实时状态修改其W值并向多径路由的源节点发送节点状态变化通告报文,来通知多径路由的源节点根据报告的内容有效调整其多条路径的传输任务比例,采用这样的适时退避机制,来使多径路由任务预先适度地避开使用这条竞争路径,以减少拥塞发生的可

17、能性,提高系统整体的性能,达到负载均衡的目的。 3 协议仿真与分析 3.1 仿真环境与参数设置 在仿真参数选择时,尽量使用系统的缺省设置,如802.11的基本数据带宽为2 Mbit。在包大小的选择上,使用了CBR业务发生器,该发生器所产生的包大小即为512 Byte。每个路由协议采用相同的仿真场景,在600 m600 m网络中随机布置50个节点,每个节点具有相同的节点移动模型,节点移动速度设置在20 m/s内随机均匀分布,节点停顿的时间分别取0、10、20、40、100 s进行五次仿真。在改进的路由协议参数配置时,根据多次试验数据得到的结果选取了较好的设置参数,如拥塞阈值n取值设置为6,饱和度差值阈值为0.05, 链路变化通报的阈值f取值为0.2,其余参数都使用前文描述的值。 3.2 仿真结果与分析 在设置好的NS2环境下对LBDSRM、DSR与MSR协议进行了仿真模拟,得到了平均端到端延迟和归一化路由开销的数据,并对仿真结果进行了分析。平均端到端时延是衡量最优负载均衡路由算法最重要的指标。归一化路由开销是指目的节点每成功接收一个数据包所需要的路由管理包的数量,可用总的路由开销/目的节点