浅说网络概率的负载均衡算法

1.基于概率的路由准入

目前，门限准则模糊了所有负载描述值低于门限的节点之间的差别，也模糊了所有负载描述值高于门限的节点之间的差别，这势必对负载均衡的效果产生不利的影响。负载均衡中的路由准入算法大部分基于门限准则来实现。门限准则通过设置一个门限值来判断路由准入，低于(或高于)门限值则准入(或禁止)路由。但是可相比基于门限的路由准入机制，基于概率的算法并不直接决定是否准入路由，而是综合各种信息得到一个准入的概率，节点以这个概率进行路由准入。节点B、C和D都收到了来自源节点A的路由请求，在t1时刻节点B、C和D的负载描述值分别为8，10和12。如果门限值为7，那么三个节点的负载都高于门限值，则此门限值的设定就无法区别出节点B、C和D之间的负载差异；同样，在t2时刻B、C、D3个节点的负载描述值分别为4、6、8时，如果门限值为10，那么此门限值也无法区别出3个节点之间的差异，而实际上3个节点的负载有较大的差异。概率算法针对不同的负载描述值得到不同的路由准入概率。例如对于负载描述值8、10和12，概率算法分别给予80%、60%和30%的准入概率，那么B、C和D三个节点路由准入的结果必然不同，节点D转发RREQ将多于其它两个节点。基于概率的算法能够准确区别节点之间的负载差异，对不同负载予不同的策略。对于一个既定的负载量，要求得到一个对应的准入概率。如果把给定的负载量L作为自变量，而对应的准入概率P作为函数值，那么就可以确定负载量和准入概率之间的函数对应关系：PF(L)其中P是准入概率，L是节点的负载量，F是概率函数。给定一个负载L就可以通过上式算出路由准入的概率P。概率函数F可以用多条曲线来拟合，理论上讲，只要是单调下降的函数曲线都合适，使大的负载描述值对应小的准入概率(负载描述值越大，负载越重)，但是不同曲线对应不同的协议性能。

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。通过当前的负载值与历史负载值比较，节点很容易判断出自己的负载轻重，从而决定是否准入路由，达到负载均衡的目的。

3.H&P算法

能够描述网络负载的表征量有很多，主要的有时延、信道占用时间、路由数和缓冲区队列长度等。时延表征量是选择一条时延最短的路径；信道占用时间是以节点感知到的信道被占用的时间作为负载的度量；路由数是以经过节点的路由数目作为负载的度量；缓冲区队列长度是以节点接口队列缓冲区长度作为负载度量。不同的表征量各有特点，操作也不相同。时延和路由数表征量需要在节点之间交换表征量信息，增加了额外开销，且对负载的描述不全面；信道占用时间是一个有效的负载度量，但是需要MAC协议支持，即需要跨层设计，这增加了协议的复杂性，也破坏了负载均衡算法与协议的松散耦合；缓冲区队列长度对负载的描述简单有效，而且具有独立分布式运算、易于操作等特点。所以在H&P_DSR协议中选择缓冲区队列长度作为负载表征量。规则二：负载信息的学习与搜集。H&P算法中对网络负载状态的判读依赖节点运行时搜集的信息。节点搜集到的负载信息越多，对网络负载的分布情况判断越准确，负载均衡的效果就越好。由于开始时节点没有搜集到足够的负载信息，所以前几个周期并不进行路由准入的判断，而是正常路由，只对网络的负载情况进行采样和记录，其中包括节点运行过程中负载表增量的最大值(记为MaxL)、最小值(记为MinL)以及平均值记为AveL)。可以灵活的设置路由准入介入的时间，理论上此时间越长节点搜集到的信息越丰富，路由准入判断越准确。实际中可根据具体的应用来设计，其与节点的移动速度、通信距离等有关。在当前仿真场景下，在2000*2000m2范围内的区域内，节点的平均速度为20m/s，通信距离为400m，理论上节点从网络边缘进入到中心所用的时间大约30s。

可据此来设计路由准入介入的时间设置为30s，其他应用场景亦可据此计算。规则三：概率函数的设计。选用最常用和直观的直线来拟合概率函数。设直线函数为：PF(L)*其中和是未知的常数。那么，根据规则二中节点记录的历史负载信息，应该是大的负载对应小的准入概率，而小的负载对应大的准入概率。最小的负载为MinL，对应最大的准入概率为MaxP，则得到一个坐标点A(MinL，MaxP)，同理，最大的负载为MaxL，最小的准入概率为MinP，得到另一个坐标点B(MaxL，MinP)。把已知的坐标点A和B代入直线函数中，得到方程组：MaxMinMinMaxPLPL解此方程组可得：MinMaxMinMinMaxMinMaxMinMinMaxLLLPPPLLPP*(4)代入直线函数中，则可得到负载量和准入概率的映射函数：MinMaxMinMinMaxMinMaxMinMinMaxLLLPPLPLLPPPF(L)当节点收到路由申请的时候，可通过上式代入负载描述值而得到路由准入的概率，进而决定是否接受此路由。公式中，MaxP和MinP是可调参数，其设置的原则是首先应保证路由的正常建立，在此基础上优化路由选择，降低冗余。要始终使轻载节点有较高的准入概率，而重载节点准入概率较小。MaxP限定了节点所能获得的最大准入概率，不能太小，否则即使轻载节点也会拒绝路由申请而使路由建立失败，导致源节点发送新的路由请求，反而增加了网络开销。MinP决定了节点的最低准入概率，节点至少以此概率准入路由申请。当网络密度较小时，由于转发路由申请的节点较少，为保证路由的建立，应提高的值，保证一定数量的路由申请成功。当网络密度较大时，节点的一跳邻居较多，为有效区别开不同负载节点之间的差异，使不同负载对应不同的准入概率，应该用较小的。这样各概率能够区别地分布在概率区间内，概率算法能过滤掉重载路由而筛选出轻载路由。所以，MaxP应该设置为一个较大的数值，而应该根据网络密度进行调整，网络密度较大的环境中设置较小的值，反之应设置较大。在当前的网络仿真场景中，可近似得节点的平均邻居数为4，节点的平均准入概率如果为50%，则可保证至少有两个节点准入路由，保证了路由的建立，同时有一条备份路径，冗余控制在可接受的范围内。据此，协议中设置90%MaxP，20%MinP。节点根据当前的负载描述值，通过式可以得到路由准入的概率。

作者：王华东 侯燕 王凤春 单位：周口师范学院计算