移动自组织网络中基于概率的负载均衡算法

移动自组织网络中基于概率的负载均衡算法

0基于路由准入的负载均衡算法移动自组织网络（移动应用程序网络）的无线通道体积有限。如果网络负载较大，网络负载容易过载，网络性能就会下降。经典的按需路由协议AODV［1］和DSR［2］等在网络轻负载情况下表现良好,但在负载较重的情况下性能都急剧恶化［3］。主要是由于协议在路径选择时倾向于使用相同的节点作为中间节点,大量的数据通过少量节点必然引起网络的拥塞。随着业务流负载强度的增大,拥塞导致路由信息的丢失将很快触发更多路由控制分组的产生,从而进一步加重网络拥塞。网络拥塞带来的网络性能下降使负载均衡技术受到越来越多的关注。目前,负载均衡一般在路由层实现,主要的负载均衡技术有蚁群算法、基于感知的负载均衡算法等。蚁群算法由意大利学者提出,是一种优良的启发式随机优化算法,采用正反馈机制实现分布式全局优化,通过信息素的不断更新最终收敛于最优路径上,其固有的并行计算特性有利于实现分散控制。现在蚁群算法已经以多种方式应用于路由协议中［4，5］。另一种研究得较多的算法是基于感知的负载均衡算法。文献提出一种基于统计量的负载度量方法,节点统计接收到的数据包数,并以此设计了一个统计量LVC(loadcoefficientofvariance)作为负载的度量,然后在网络中选择一条最优度量值的路径,从而达到负载均衡的目的。文献提出一种负载均衡算法,其以节点的空闲时间和邻居节点的空闲时间作为联合度量,既考虑了节点本身的负载情况,同时也考虑了其他发送节点竞争信道时带来的影响。文献提出一种基于信道占用率的负载均衡算法,其以节点感知到的信道占用率作为负载度量值。这些负载均衡算法都以队列长度、时延、信道繁忙度等一个或几个参数作为负载轻重的度量,其思想都是在路由建立过程中携带负载信息,目的节点选择负载较轻的路径建立路由。蚁群算法需要向网络中发送蚂蚁分组来进行负载均衡,而基于感知的负载均衡算法需要在节点间传播负载信息。无论哪种算法都需要占用额外的信道资源,尤其大部分负载信息需要在网络中以广播方式存在,占用大量的信道资源,将对网络的性能带来严重影响［9］。本文对基于路由准入的负载均衡算法进行研究。基于路由准入的算法不需要占用额外的信道资源,并且能够有效控制路由时广播包的洪泛,减少对信道资源的占用,与路由协议的松散耦合也使算法应用更加灵活。文献就路由准入算法有了一些论述,并提出一种基于路由准入的负载均衡算法,其以接口队列长度作为负载度量,以一个固定的队列长度值作为路由准入的门限。但是,基于门限的算法适应性不强,算法对高于门限或低于门限的度量值一并处理,不够准确;由于缺乏与网络负载状态的横向比较,其调度算法也不准确。本文提出了一种新的基于路由准入的负载均衡算法———H&P(historicalandprobability)算法。该算法由基于历史信息的负载映射机制和基于概率的路由准入组成,算法能有效解决路由准入中负载状态判断不准和门限准入规则适应性不强的问题,并把H&P算法与经典的按需路由协议DSR相结合,设计了H&P_DSR协议。1算法描述1.1节点按负载描述的安全评估目前,负载均衡中的路由准入算法大部分基于门限准则来实现［11］。门限准则通过设置一个门限值来判断路由准入,低于(或高于)门限值则准入(或禁止)路由。但是可以看到,门限准则模糊了所有负载描述值低于门限的节点之间的差别,也模糊了所有负载描述值高于门限的节点之间的差别,这势必对负载均衡的效果产生不利的影响。相比基于门限的路由准入机制,基于概率的算法并不直接决定是否准入路由,而是综合各种信息得到一个准入的概率,节点以该概率进行路由准入。如图1所示,节点B、C和D都收到了来自源节点A的路由请求,在t1时刻节点B、C和D的负载描述值分别为8、10和12。如果门限值为7,那么三个节点的负载都高于门限值,则此门限值的设定就无法区别出节点B、C和D之间的负载差异;同样,在t2时刻B、C、D三个节点的负载描述值分别为4、6、8时,如果门限值为10,那么此门限值也无法区别出三个节点之间的差异,而实际上三个节点的负载有较大的差异。概率算法针对不同的负载描述值得到不同的路由准入概率。例如对于负载描述值8、10和12,概率算法分别给予80%、60%和30%的准入概率,那么B、C和D三个节点路由准入的结果必然不同,节点D转发RREQ将多于其他两个节点。基于概率的算法能够准确区别节点之间的负载差异,对不同负载给予不同的策略。对于一个既定的负载量,要求得到一个对应的准入概率。如果把给定的负载量L作为自变量,而对应的准入概率P作为函数值,那么就可以确定负载量和准入概率之间的函数对应关系:其中:P是准入概率,L是节点的负载量,F是概率函数。给定一个负载L就可以通过式(1)算出路由准入的概率P。概率函数F可以用多条曲线来拟合,理论上讲,只要是单调下降的函数曲线都合适,使大的负载描述值对应小的准入概率(负载描述值越大,负载越重),但是不同曲线对应不同的协议性能。1.2节点在网络区域内的负载状态变化基于路由准入的负载调度算法是完全分布式运算的,节点之间没有任何的负载信息交互。因此节点对网络状态感知的准确性就成为负载均衡的关键之一。基于历史信息的负载映射利用节点的历史负载信息来映射网络的负载状态,为节点的路由准入提供有效的参考。研究发现节点负载强度与节点在网络中的位置有很大的关系,当节点处在网络的中心区域时,由于经过的路由数比较多,所以节点负载一般较高;相反,当节点处在网络边缘时,负载较低。又由于节点的移动,节点在网络中的位置不断发生变化,从而节点的负载状态也在不断改变。在一定的网络区域内,以节点随机移动为例,理论上经过足够长的时间,节点会遍历网络,经历网络的各种负载状态,称之为节点的网络各态历经性。也就是在经过足够的时间后,节点能够掌握足够丰富的网络负载信息,而这些信息与当前时刻其他节点的负载高度相关。所以,节点在历经各种网络负载状态时,记录下相应时刻的负载描述值,作为路由准入时的横向比较参考,使路由准入更准确。图2是四个相隔不远时刻的网络拓扑,图中着色的节点为同一个节点A。从图中可以看到,从t1时刻到t4时刻这段时间内,节点A由网络的中心运动到了网络的边缘(其他节点也会移动,只是笔者并不关心),而节点移动之后的位置被其他节点取代。如图2(b)中的t2时刻,节点B运动到了节点A在t1时刻的位置,其他几个图同理。节点在网络中位置的变化导致节点的负载状态改变,在t1、t2、t3、t4四个时刻,节点A的负载描述值分别为9、7、5和3,可见节点的负载在逐渐降低。而在这个过程中,节点不断记录负载信息,包括变化过程中负载的最大值、最小值以及整个过程中的负载平均值等。节点A记录的负载最大值是t1时刻,其负载描述值为9,负载的最小值是在t4时刻,其负载描述值为3,整个过程负载的平均值为(9+7+5+3)/4=6。节点利用这些历史负载信息来映射网络的负载状态。如节点记录的历史最大负载描述值为9,那么很可能此时网络中的其他某个节点的负载值为9。通过当前的负载值与历史负载值比较,节点很容易判断出自己的负载轻重,从而决定是否准入路由,达到负载均衡的目的。1.3负载信息的设计DSR(dynamicsourcerouting)是MANET中的经典按需源路由协议,鉴于其研究的广泛性和代表性,本节在DSR协议中实现H&P算法,添加了H&P算法的新协议称为H&P_DSR协议。H&P_DSR协议的路由过程类似于DSR协议。当源节点没有到达目的节点的路由时,广播RREQ发起路由寻找,中间节点利用H&P算法决定是否准入路由。准入路由的节点转发RREQ,其他节点丢弃路由申请,目的节点收到RREQ之后回送路由应答RREP,最终形成源节点到目的节点的路由。H&P_DSR协议中的H&P算法主要通过以下几个规则实现:规则1负载表征量的设计。能够描述网络负载的表征量有很多,主要的有时延、信道占用时间、路由数和缓冲区队列长度等。时延表征量是选择一条时延最短的路径;信道占用时间是以节点感知到的信道被占用的时间作为负载的度量;路由数是以经过节点的路由数目作为负载的度量;缓冲区队列长度是以节点接口队列缓冲区长度作为负载度量。不同的表征量各有特点,操作也不相同。时延和路由数表征量需要在节点之间交换表征量信息,增加了额外开销,且对负载的描述不全面;信道占用时间是一个有效的负载度量［12］,但是需要MAC协议支持,即需要跨层设计,这增加了协议的复杂性,也破坏了负载均衡算法与协议的松散耦合;缓冲区队列长度对负载的描述简单有效,而且具有独立分布式运算、易于操作等特点。所以在H&P_DSR协议中选择缓冲区队列长度作为负载表征量。规则2负载信息的学习与搜集。H&P算法中对网络负载状态的判读依赖节点运行时搜集的信息。节点搜集到的负载信息越多,对网络负载的分布情况判断越准确,负载均衡的效果就越好。由于开始时节点没有搜集到足够的负载信息,所以前几个周期并不进行路由准入的判断,而是正常路由,只对网络的负载情况进行采样和记录,其中包括节点运行过程中负载表增量的最大值(记为Lmax)、最小值(记为Lmin)以及平均值(记为Lave)。可以灵活地设置路由准入介入的时间,理论上此时间越长节点搜集到的信息越丰富,路由准入判断越准确。实际中可根据具体的应用来设计,其与节点的移动速度、通信距离等有关。在当前仿真场景下,在2000×2000m2范围内的区域内,节点的平均速度为20m/s,通信距离为400m,理论上节点从网络边缘进入到中心所用的时间大约为30s。可据此来设计路由准入介入的时间设置为30s,其他应用场景亦可据此计算。规则3概率函数的设计。选用最常用和直观的直线来拟合概率函数。设直线函数为其中:α和β是未知的常数。那么,根据规则2中节点记录的历史负载信息,应该是大的负载对应小的准入概率,而小的负载对应大的准入概率。最小的负载为Lmin,对应最大的准入概率为Pmax,则得到一个坐标点A(Lmin,Pmax),同理,最大的负载为Lmax,最小的准入概率为Pmin,得到另一个坐标点B(Lmax,Pmin)。把已知的坐标点A和B代入直线函数中,得到方程组:解此方程组可得:代入直线函数中,则可得到负载量和准入概率的映射函数:当节点收到路由申请的时候,可通过式(5)代入负载描述值而得到路由准入的概率,进而决定是否接受此路由。式(5)中,Pmax和Pmin是可调参数,其设置的原则是首先应保证路由的正常建立,在此基础上优化路由选择,降低冗余。要始终使轻载节点有较高的准入概率,而重载节点准入概率较小。Pmax限定了节点所能获得的最大准入概率,Pmax不能太小,否则即使轻载节点也会拒绝路由申请而使路由建立失败,导致源节点发送新的路由请求,反而增加了网络开销。Pmin决定了节点的最低准入概率,节点至少以此概率准入路由申请。当网络密度较小时,由于转发路由申请的节点较少,为保证路由的建立,应提高Pmin的值,保证一定数量的路由申请成功。当网络密度较大时,节点的一跳邻居较多,为有效区别开不同负载节点之间的差异,使不同负载对应不同的准入概率,应该用较小的Pmin。这样各概率能够区别地分布在概率区间内,概率算法能过滤掉重载路由而筛选出轻载路由。Pmax应该设置为一个较大的数值,而Pmin应该根据网络密度进行调整,网络密度较大的环境中设置较小的Pmin值,反之Pmin应设置较大。在当前的网络仿真场景中,可近似得节点的平均邻居数为4,节点的平均准入概率如果为50%,则可保证至少有两个节点准入路由,保证了路由的建立,同时有一条备份路径,冗余控制在可接受的范围内。据此,协议中设置PMax=90%,PMin=20%。节点根据当前的负载描述值,通过式(5)可以得到路由准入的概率。2仿真结果及验证本章在Qualnet仿真平台上仿真验证H&P_DSR协议的性能,首先仿真比较基于概率的和基于门限的准入算法,然后对H&P_DSR协议的性能进行验证。仿真主要通过网络吞吐量和平均端到端时延两个指标来衡量协议的性能。2.1负载表征及仿真本节通过仿真比较基于概率的路由准入和基于门限的路由准入。仿真参数设置如表1所示。仿真中设置32个节点分布在2000×2000的区域内,应用层配置16对CBR流,CBR流数据包的长度随机选择,通过改变发送数据的间隔来调整CBR流添加到网络中的负载。路由协议采用H&P_DSR协议,其中分别采用基于门限和基于概率的算法。目前,门限算法中门限值一般根据经验或采取实验的方法手工设定［10］。公平起见,首先通过实验获得负载表征量的参考数据来设置门限算法中的门限值。在当前仿真设置下,设置重载和轻载两种网络负载情况,采用没有均衡的DSR协议,在网络稳定时,分别测得重载和轻载状态下某个时刻各节点的负载表征值分别如图3和4所示。图中横坐标对应节点,纵坐标是各节点对应的负载表征值,图中直线为所有节点的平均负载表征值。由图可见,无论在重载还是轻载时,节点间的负载差异均较大。即使在网络重载时,也有负载很轻的节点。计算得到重载情况下平均负载表征值为10.096,在轻载情况下平均负载表征值为5.115,故门限算法中分别设置两个门限值A=10和B=5,以使门限能够区别开不同负载的节点,起到负载均衡的作用。对基于门限和概率的算法进行仿真,仿真30次取平均值,结果如图5和6所示。图5是网络吞吐量曲线图,图6是平均端到端时延曲线图,其中横坐标都是归一化的网络负荷,纵坐标分别是网络吞吐量和平均端到端时延。图中基于门限A的曲线其判决门限为10,基于门限B的曲线其判决门限为5。当网络轻载时,节点的平均负载表征值为5,这时大部分节点的负载描述值都在门限5上下波动,判决门限5时对网络状态的变化较为敏感,能够反映网络不同部分之间负载的差异,所以能够对网络的负载起到均衡的作用;当门限为10时,因为网络负载较轻,绝大部分节点的负载描述值都低于10,所以判决门限10无法通过路由的准入对网络的负载进行有效的均衡,影响了均衡的效果。当网络负载逐渐加重后,各节点的负载描述值在10上下波动,这时判决门限10能够准确地区别开不同节点之间的负载差异;相反判决门限5将普遍低于绝大部分节点的负载描述值,其无法有效地对网络的负载进行均衡,此时网络的吞吐量和时延性能都不同程度地下降。从仿真曲线可以看到,在网络轻载时,门限值为5的算法性能更好,在网络重载时,门限值为10的算法性能更好。对比门限算法曲线和概率算法曲线,可以看到概率算法无论在网络吞吐量还是网络时延方面都好于门限算法。尤其在网络重载时,优势更加明显。概率算法以连续曲线的方式对待不同的负载,能够有效区别负载之间的差异,并根据这种差异采取不同的准入控制;而门限算法只能对门限值附近的负载状态进行有效的区分,当节点感知到的负载都低于或高于判决门限时,都采取同样的判断结果,影响了负载均衡的准确性。2.2路由协议仿真本节通过仿真比较H&P_DSR和DSR协议的性能。仿真场景和参数设置如2.1节,路由协议分别为H&P_DSR和DSR。仿真30次取平均值,结果如图7和8所示。仿真结果与理论分析一致,H&P_DSR协议中的负载均衡算法能够准确有效地工作,这使H&P_DSR协议无论在网