基于改进权重的D-S证据理论的动态负载平衡算法

邰滢滢,庞 影,段苛苛,付云鹏

(辽宁大学,信息学院, 沈阳 110036)(*通信作者电子邮箱yingyt216@126.com)

0 引言

以互联网产业为代表的中国信息行业蓬勃发展,已成为国民经济和社会发展的重要组成部分,其中网络游戏产业的发展最为惊人,它已经成为网络时代娱乐行业的领跑者。游戏的发展历经单机游戏、局域网游戏和大型多人在线游戏(Massively Multiplayer Online Game, MMOG),越来越强调玩家之间的实时互动。

MMOG以主从架构模式进行处理,所有玩家连接到服务器。服务器采用负载均衡策略负责将并发访问或数据流量分摊到多台节点上分别处理[1]。目前MMOG主要采用业务分离集群。因为有各种各样的业务(聊天、散步、交易、情节、战斗等),如果服务器负载过重,将一些业务从主服务器分离到单个服务器上就可以有效地减少每个服务器的负担,或增加游戏服务器的数量以均摊其他服务器的负担。为了在请求高峰时产生大量的业务响应,一般主服务器都要采用一些负载平衡策略[2]。

MMOG系统的特点有:1)高度交互性。MMOG是实时交互的应用程序,不应该过于频繁地执行负载均衡算法,同时也不能导致过多的服务器处于超载状况,因为这些服务器需要负责服务大量的客户端。2)系统规模庞大。为了可以使几十万玩家同时在线、操作游戏,MMOG需要大量的服务器来支撑其运行。因此,负载均衡算法应避免搜集服务器负载信息开销过大的情况。3)负载可能层叠迁移。当超载服务器的所有邻居服务器达到极限时,邻居服务器需要将其部分负载迁移到另一个邻居服务器,以便减轻负载。由此可见,涉及到的服务器数量越多,迁移的客户总数就越大。因此,MMOG中的负载均衡算法应该尽量限制负载迁移所涉及到的服务器数量[3]。

基于以上的分析可以看出,在服务器集群系统中,各服务器负载能力差异较大,选择好的负载均衡算法[4]对提高集群系统资源利用率有着重要的意义。很多信息融合的方法对本问题的解决都有借鉴意义。信息融合的本质是将多源信息进行融合,形成比单一信息源更准确和完全的估计和判决。在决策级融合中,贝叶斯概率法和D-S(Dempster/Shafer)证据理论法一直占有主要地位。其中：基于贝叶斯概率的方法,要求条件较高,需要统一的知识框架和事物的先验概率；D-S证据理论是在证据理论的基础上发展的一种推理理论，它不需要知道事件的先验概率,依靠证据的积累不断缩小假设集,最终进行判别,已经被广泛用来处理不确定信息的决策问题。而本文正是考虑历史参数的不断积累对服务器性能的影响,这符合D-S证据理论解决问题的初衷。所以本文提出改进权重的D-S证据论证的方法,在计算过程中,结合历史因素,动态调整权重,不断预测集群中各服务器下一时刻的负载情况。因此当集群接收到请求时,能够立即响应,不用查找当前服务器的各参数重新计算负载情况,再进行决策,节省了计算延时时间,避免了时间积累引起的权重变化使原调度算法的正确性受到影响,而且在该算法的执行次数较少的情况下,能够比以往的负载均衡算法更快速准确地执行,找到集群中的超载节点。

1 相关研究

负载均衡算法的目标是实现快速的事务处理能力和响应能力。它一般用于响应网络请求的网页服务器或者代理服务器。执行负载均衡算法的服务器会在接到任一请求时,在集群中找到当前拥有请求较少且不繁忙的服务器,把请求转移到这些轻载服务器上。负载均衡算法使得MMOG这类大型游戏系统中的各节点能够平衡分摊端口负载或网络流量负载；而且当网络服务器应用程序接收了无法及时处理的大量入网流量时,会通过各个服务器之间的快速信息交流和负载均衡算法对多个节点分配任务,提高服务器的处理性能[5],实现在各节点之间动态分配负载,最终达到网络负载平衡的目的。

负载均衡算法一般分为以下两大类:①静态负载均衡算法。该算法在实际运行中不考虑各服务器的负载情况,仅根据预先设定对客户端发送的请求进行分配。②动态负载均衡算法。该算法能够根据服务器当前的负载能力作为分配的准则,动态地调整各服务器的负载能力,缩短用户请求的响应时间。由于动态负载均衡算法相对于静态负载均衡算法的优势显而易见,因此,动态负载均衡算法更适合于MMOG这类系统。

目前,对于负载均衡算法有很多研究,例如：加权循环算法[6],保证了处理能力强的服务器可以接受更多的任务,在一定程度上避免了处理能力低的服务器由于任务过多而瘫痪这一现象的产生；但是没有考虑到处理请求时间的变化,可能导致集群中各服务器之间负载的不均衡。最快响应速度算法[7]确保了最短的服务器响应时间, 使任务在较短的时间内得到分配处理, 不会产生因响应时间过长使任务延时的情况；此算法能较好地反映服务器当前运行状态, 但最快响应时间仅仅指的是负载均衡器与服务器间的最快响应时间, 而不是客户端与服务器间的最快响应时间。对数最小平方矩阵的优先级算法[8],为处理器和业务设置合理的优先级,提高了基于遗传算法的负载均衡调度效率；但是遗传算法采用随机选取处理器为用户提供服务,可能会有负载不均衡这一状况的发生。改进的加权最小连接算法[9]在仅考虑服务器当前连接数作为负载情况这一缺点上作了改进,将服务器前1 min的负载情况作为一个负载因子,这样使算法更加准确了解当前服务器的负载信息;该算法虽然考虑了服务器的实际负载情况,但是在服务器权值的设置方面需要考虑的因素较多且复杂。针对异构集群设计的基于索引的负载均衡算法[10],虽然考虑了集群中每个节点的内核数量和每个内核的计算能力不同这两方面来实现集群服务器的负载均衡,但忽略了节点的实际负载情况。

以上负载调度算法虽然在一定程度上实现了集群的负载均衡,动态地将请求任务均摊到其他服务器上,但是一些负载均衡算法都是依赖当前服务器某个(某些)信息的采集来计算服务器负载情况,均不考虑历史因素的影响,也就是说无论这台服务器历史上的负载情况如何,只要当前这个(这些)因素没有达到设定阈值,都认为该服务器可以响应下一时刻的请求。这样可能会导致一个新的问题,就是历史上某个因素在某一时刻对负载情况的影响虽然较小,但是随着时间的积累,它的影响逐渐增大,最终导致该服务器超载,那么这些调度算法计算所得结果有可能不准确。也就是说,以单纯的某一因素为判别条件,很有可能会导致局部判别不确定,使得决策中的最优准则未必产生全局最优。本文提出的负载均衡算法考虑了影响服务器性能的众多主要因素,引入历史条件,采用了区间估计,而不是点估计,对不确定信息进行描述,利用D-S证据理论的组合规则,对得到结果进行融合判断,解决了服务器集群的快速准确响应问题。

2 基于权重修正的D-S证据理论的负载平衡方法

D-S证据理论的基本概念[11]包括:

1)识别框架。由互不相容的基本命题组成的完备集合,用来表示对某一问题的所有答案的集合,有且仅有一个答案是正确的。

2)基本信任分配函数。定义集合A为集合D的子集,M为2D上的基本信任分配函数(mass函数),m(A)表示对A的信度程度大小。M:2Ω→[0,1],函数M满足以下两种情况的映射：当不可能事件的基本概率是0时,用M(∅)=0表示;当2Ω中全部元素的基本概率之和为1时,用∑M(A)=1表示,A∈Ω。其中：M(A)称为A的基本概率函数,表示对A的精确信任。

3)合成规则。设M1,M2是2Ω上两个概率分配函数,则其正交和M=M1+M2定义为:

其中:

本文把D-S证据理论应用于集群均衡负载方面,在D-S证据理论的基础上,引入了动态权重的概念,实时改变当前权重,使决策结果更加准确,并采用基于推理的数据融合方法,即结合历史数据与实时数据相融合的方法来计算动态权重,再依据动态权重与原始信度二者建立的基本信任函数决策方法进行证据合成,最终辨别服务器是否超载。

本文算法中,将判断服务器是超载还是轻载作为识别框架,那么D-S证据理论整体合成规则如图1所示。

图1 D-S证据理论整体合成规则Fig.1 Rules of D-S evidence synthesis

本文通过初始构造识别框架即设置四种判据组成的集合设为E={1,2,3,4},根据不同判据的判断结果定义识别框架Θ={超载,轻载}。定义基本信任函数Mi、焦元Ai以及各个证据之间冲突的程度K,再利用证据合成规则进一步融合,若最终冲突程度小即说明合成结果可信,则根据组合后的信任函数进行判断,判别出服务器是否超载。

2.1 动态权重计算方法

节点的动态权重是根据节点的相关参数计算出来的,由于本文中实验是以MMOG为背景的,系统参数中的CPU、内存、磁盘和占用带宽这四项参数在MMOG中为影响集群性能的主要参数，而其他参数对于服务器集群的影响较小,因此本文选取这四项参数为实验判据。

对于权重修订有两种思路：第一种为完全依赖当前获取的参数来计算动态权重,虽然简化了计算量,但是没有考虑参数的动态变化对系统的影响,所以不能完全准确地描述出节点的负载情况,容易造成误判的结果;第二种为依靠历史数据来计算动态权重,这种修正方法在一定程度上避免了第一种方法的不足,但是如果对历史数据的依赖过强,则累计的误差会比较大,而且也会增加计算量。所以参与计算的历史参数既不能太多,又不能太少,本文选取最近两次的历史数据进行融合计算权重,即可满足要求。

2.2 信度计算方法

D-S证据理论的常用决策有三种:基于信任函数的决策、基于基本可信度赋值的决策和基于最小风险的决策。基于信任函数的决策方式作为不确定性信息处理的重要数学模型具有广泛应用,能够区分不确定和未知的差异,从而很好地表示不确定和未知等认知学上的概念,且推理形式简单,而本文正是利用历史数据因素来进一步推断服务器超载还是轻载的不确定结果,因此本文采用基于信任函数的决策方法。

在基本信任分配函数中定义K为多个证据之间的冲突系数,用来表示各个证据之间的冲突程度。当冲突系数K接近或等于1,也就是证据出现严重冲突,会导致融合结果不可信。为避免这一情况,在决策过程中要不断更新信任函数。本文的信任函数选择方式与原始信度和权重有关,更新方法为:

其中:m表示信任函数;w表示权重。

2.3 融合决策方法

通过上两节提出的动态权重以及原始信度,多个证据信息的mass函数m1、m2、…、mn对于识别框架D的合成规则,运用式(1)计算证据合成：

(1)

运用式(2)计算冲突系数K,K称为多个证据之间的冲突系数,可用于定义各个证据之间冲突的程度,K越大,说明证据间冲突程度越大;K越小,说明证据间冲突程度越小。若K等于1或者趋近于1,则不能用D-S证据组合规则进行数据融合。

(2)

经过证据合成的比较即系统参数增加或者减少的对比,若证据合成结果相等,则该节点负载平衡,无需增加或减少任务量;若证据合成比较的结果为增加,则该节点超载,应适当较小任务量;若证据合成比较的结果为减少,则该节点轻载,应适当增加任务量。最终使系统中每个节点均衡负载,考虑集群中每个节点的实时负载和响应能力,调整任务分配比例,以便在某些节点收到大量请求时避免过载,从而提高服务器集群的总体吞吐量。

2.4 算法实现步骤

根据动态调整权重的策略在D-S证据理论中的应用,以下说明本文算法的计算过程:

1)设置实时采集权值的周期,周期短而频繁采集,这样会给负载均衡器和节点带来负担,增加额外的网络负荷。在实践过程中要适当地调整采集负载信息的周期,一般周期设置在5～10 s,根据服务器系统情况获取节点的四种判据的值。

2)根据每次采集四种判据的数值与设置的阈值进行比较,若判据判断参数增加则用“○”表示,若判据判断参数减小则用“×”表示,建立基于动态临近历史数据融合方法示意表。

3)基于动态临近历史数据多判据融合策略,选取最近两次四种判据的正判率统计,利用2.2节中的动态权重计算方法,对当前的权重进行修正,建立权重修正表。

4)根据步骤3)得出的动态权重利用2.3节中信度计算方法,原始信度与权重的函数关系计算出原始信度,建立信度表。

5)重复步骤1)～4),采集出每次动态权重计算出的信度表。

6)经过步骤5)得出信度表,利用式(2)计算冲突系数,若计算出的冲突系数接近于1或等于1,则融合结果不可信;若计算出的冲突系数不等于1或接近于1,利用式(1)计算证据合成,计算出每次合成结果即增加或减少。

7)根据每次得出的合成结果,比较增加与减少次数,确定最终节点是轻载还是超载。若增加次数多,则该节点为超载节点,应适当减小任务量;若减少次数多,则该节点为轻载节点,应适当增加任务量。最终使集群负载均衡,达到提高服务器集群的吞吐量以及系统性能的目的。

3 实验与分析

本实验在大型多人在线游戏(王者荣耀)的情景下,搭建集群,其中有1台均衡器,3台服务器,征集10位玩家在同一时刻玩游戏,以此来模拟MMOG系统。使用的3台服务器和均衡器均为Windows 7 64位4 GB内存,其余10位玩家所玩机器为客户端,均为Windows 7 32位,内存4 GB。在10位玩家玩游戏一段时间后,均衡器向3台服务器发送请求获取当前集群中各服务器的4种参数情况,当服务器接收到均衡器的请求后向其发送数据。实验将检测基于改进权重的D-S证据理论算法与当前比较推崇的基于负反馈机制的动态算法与加权循环算法两种动态负载平衡算法在游戏运行时对服务器是否超载的正判率的对比以及各算法执行时间的对比来比较两种算法作用下的负载判别情况。

3台服务器各采集出7组数据作为实验样本。服务器1、服务器2、服务器3采集出的样本数据如表1所示。

表1 服务器1、服务器2、服务器3采集的数据Tab. 1 Collected data in server 1, server 2, server3

表2 服务器1、服务器2和服务器3基于动态临近历史数据融合方法示意表Tab. 2 Criterion results of server 1, server 2, server 3 based on dynamic proximity historical data fusion method

四种判据的初始权重设置为1/4,将每四种判据的判别结果按照先后顺序排列,假设四种判据设置的初始阈值分别为30.000 000%、17.000 000%、70.000 000%、0.100 000%,将四种判据采集的数据分别与对应的阈值作比较,若判据判断参数增加则用“○”表示,若判据判断参数减小则用“×”表示,建立基于动态临近历史数据融合方法示意表,最终四种判据的判别结果如表2所示。

选取前两次的历史数据进行权重计算,如表2中,服务器1数据融合方法表中第三次的权重依赖于第一次和第二次获取的历史结果,采用数据融合的方法,对第三次的权重进行调整,参照2.2节的调整方法,第三次的权重依次为:

w1=(1+2)/(4+4)=3/8

w2=(1+1)/(4+4)=2/8

w3=(1+1)/(4+4)=2/8

w4=1/(4+4)=1/8

依此类推,在每次权重部分都应用上述计算方法,对各判据对应的权重进行调整,为下一次判断作准备。

使用2.3节中所提到的信度计算方法,得到第三次决策的四种判据根据融合权重修正后的信度,如表3所示。

表3 第三次决策信度结果Tab. 3 Reliability of the third time

根据式(1)～(2)计算证据合成及冲突系数K。

(m1⨁m2⨁m3⨁m4)(增加)=0.619

(m1⨁m2⨁m3⨁m4)(减少)=0.381

因为计算出的冲突系数K=0.889≠1,所以融合结果可信。因此有(m1⨁m2⨁m3⨁m4)(增加)>(m1⨁m2⨁m3⨁m4)(减少),最终判别结果为增加。

依此类推,其他判别结果的计算方法与第三次判别结果计算方法完全相同。表4为服务器1、服务器2和服务器3中各判据结果对比。

表4 服务器1、服务器2和服务器3上各判据结果对比Tab. 4 Comparison of criterion results in server 1, server2, server3

由表4所知,服务器1在各次融合结果均可信的前提下,判据结果增加次数多于判据结果减小次数,因此判断判据增加即服务器超载,应适当减少任务量。

服务器2和服务器3在各次融合结果均可信的前提下,判据结果减小次数多于判据结果增加次数,因此判断判据减小即服务器轻载,应适当增加任务量或减少集群中的节点数量。

本实验与基于负反馈机制的动态均衡算法进行比较。基于负反馈机制的动态均衡算法基本原理:Winit(Ni)表示节点Ni的初始权值,使用CPU的计算能力、系统I/O速率、内存总容量以及网络接口速率这四种参数计算节点的初始权值。计算公式[12]如下:

(3)

其中:Lf(Ni)表示节点Ni某一参数的当前值；Ki表示节点i的处理器数量；BASEcpu、BASEI/O、BASEnet、BASEm中参数的基准值以BASEf来表示，这些基准值可以根据各节点的实际情况统计确定；Ri为每个参数设定的可调系数,∑Ri=1。

计算各节点的负载比例L(Ni),利用式(4)计算如下:

L(Ni)=R1Ucpu+R2Um+R3Udisk+R4Ubandwidh

(4)

其中:Ucpu、Um、Udisk、Ubandwidh分别表示CPU剩余率、内存剩余率、磁盘剩余率和占用带宽。

利用式(5)计算节点最终权值W(Ni),公式如下:

W(Ni)=L(Ni)·Winit(Ni)

(5)

由式(5)计算出最终权值进行比较,权值最大的即为超载节点,应适当减小任务量。

将服务器1、服务器2、服务器3获取的五次参数用基于负反馈机制的动态均衡算法计算,得到表5结果。

表5 服务器1、服务器2和服务器3基于负反馈机制算法的动态权值Tab. 5 Dynamic weights calculated by negative feedback mechanism algorithm for server 1, server2, server3

由表5可知,各服务器的负载权值不相上下,对比5次实验结果可知,服务器2负载最重,即可看作为超载节点。

由表1获取的参数可知,服务器1相对于服务器2和服务器3而言,磁盘剩余率和占用带宽不相上下,而CPU剩余率和内存剩余率相对于另两台服务器参数较高,因此在三者之间,服务器1超载,而服务器2与服务器3相对于服务器1轻载。在基于改进权重的D-S证据理论的动态负载平衡算法中,计算出服务器1超载,服务器2与服务器3轻载;而由基于负反馈机制的动态均衡算法计算出服务器2超载,因此使用基于负反馈机制的动态均衡算法计算结果与真实结果不符,本文使用的基于改进权重的D-S证据理论的动态负载平衡算法计算结果更符合实际情况。

在比较算法执行时间方面,选取基于负反馈的动态均衡算法和加权循环算法与本文算法相比较。由图2～3可以看出,基于负反馈机制的动态均衡算法和加权循环算法波动较大,在算法执行开始时,其执行时间相比D-S证据理论算法的执行时间短,但随着执行次数的增加,其执行时间也会随之波动,执行时间普遍偏高。而基于改进权重的D-S证据理论算法波动较小,在开始执行的几次实验中,虽然其执行时间较高,但随着执行次数的增加,接下来几次算法的执行时间趋近于0。正是因为D-S证据理论算法的权重部分受历史因素的影响,在多次执行算法之后,能够根据前几次的负载结果推断出来,所以在一段时间内,该算法的执行时间相比另外两种算法的执行时间短。而后,随着大量实验次数的增加以及集群中各服务器负载情况的变化,三种算法对各服务器的负载状况也会随之更新并且重判,再次找到集群中的超载节点,三种算法的执行时间又如图2～3所示,因此该实验从算法执行时间上验证基于D-S证据理论的算法相比另外两种算法的总执行时间更短,更适合在MMOG情景下,在短时间内能够准确地反映出集群中各服务器的负载情况。

图2 本文算法与基于负反馈机制的动态均衡算法执行时间的比较Fig. 2 Running time comparison of the proposed algorithm and the dynamic balancing one based on negative feedback

图3 本文算法与加权循环算法执行时间的比较Fig. 3 Running time comparison of the proposed algorithm and the weighted loop one

4 结语

本文提出一种在MMOG情景下基于改变权重的D-S证据理论的负载平衡算法,从发展的角度,结合历史因素,动态调整权重,不断预测服务器的负载情况,准确判断节点是否超载,将历史数据与实时数据相结合,采用多判据融合,选取最近两次的正判率统计,按照“判断正确权重增加,判断错误权重不变”的准则,不断修正各因素的权重,然后计算各因素的信度函数。基于信任函数的决策方式,为避免证据出现严重冲突,根据权重不断调整信任结果,最后对多个因素的信任结果进行融合,融合结果增加,则判断该点为超载,否则为轻载。MMOG网络集群中,服务器的数量和性能与客户的要求和实际连接数有很大关系,在这种大型网络中,参与工作的节点要由实际情况决定,网络规模和服务器数量随时都可能发生改变,但是无论怎么改变都是小规模的网络组成大规模的网络。所以本文模拟一个小型MMOG系统进行实验。虽然本实验平台与以MMOG系统为基准的目标平台存在一定差距,但是在本实验平台上,本文算法可以快速准确地找到集群中超载的节点,达到了解决问题的目的,而且决策结果可以维持一段时间不变,然后根据需要再进行运算判断。