邰瀅瀅,龐 影,段苛苛,付云鵬

(遼寧大學,信息學院, 沈陽 110036)(*通信作者電子郵箱yingyt216@126.com)

0 引言

以互聯(lián)網(wǎng)產(chǎn)業(yè)為代表的中國信息行業(yè)蓬勃發(fā)展,已成為國民經(jīng)濟和社會發(fā)展的重要組成部分,其中網(wǎng)絡游戲產(chǎn)業(yè)的發(fā)展最為驚人,它已經(jīng)成為網(wǎng)絡時代娛樂行業(yè)的領跑者。游戲的發(fā)展歷經(jīng)單機游戲、局域網(wǎng)游戲和大型多人在線游戲(Massively Multiplayer Online Game, MMOG),越來越強調(diào)玩家之間的實時互動。

MMOG以主從架構模式進行處理,所有玩家連接到服務器。服務器采用負載均衡策略負責將并發(fā)訪問或數(shù)據(jù)流量分攤到多臺節(jié)點上分別處理[1]。目前MMOG主要采用業(yè)務分離集群。因為有各種各樣的業(yè)務(聊天、散步、交易、情節(jié)、戰(zhàn)斗等),如果服務器負載過重,將一些業(yè)務從主服務器分離到單個服務器上就可以有效地減少每個服務器的負擔,或增加游戲服務器的數(shù)量以均攤其他服務器的負擔。為了在請求高峰時產(chǎn)生大量的業(yè)務響應,一般主服務器都要采用一些負載平衡策略[2]。

MMOG系統(tǒng)的特點有:1)高度交互性。MMOG是實時交互的應用程序,不應該過于頻繁地執(zhí)行負載均衡算法,同時也不能導致過多的服務器處于超載狀況,因為這些服務器需要負責服務大量的客戶端。2)系統(tǒng)規(guī)模龐大。為了可以使幾十萬玩家同時在線、操作游戲,MMOG需要大量的服務器來支撐其運行。因此,負載均衡算法應避免搜集服務器負載信息開銷過大的情況。3)負載可能層疊遷移。當超載服務器的所有鄰居服務器達到極限時,鄰居服務器需要將其部分負載遷移到另一個鄰居服務器,以便減輕負載。由此可見,涉及到的服務器數(shù)量越多,遷移的客戶總數(shù)就越大。因此,MMOG中的負載均衡算法應該盡量限制負載遷移所涉及到的服務器數(shù)量[3]。

基于以上的分析可以看出,在服務器集群系統(tǒng)中,各服務器負載能力差異較大,選擇好的負載均衡算法[4]對提高集群系統(tǒng)資源利用率有著重要的意義。很多信息融合的方法對本問題的解決都有借鑒意義。信息融合的本質(zhì)是將多源信息進行融合,形成比單一信息源更準確和完全的估計和判決。在決策級融合中,貝葉斯概率法和D-S(Dempster/Shafer)證據(jù)理論法一直占有主要地位。其中：基于貝葉斯概率的方法,要求條件較高,需要統(tǒng)一的知識框架和事物的先驗概率；D-S證據(jù)理論是在證據(jù)理論的基礎上發(fā)展的一種推理理論，它不需要知道事件的先驗概率,依靠證據(jù)的積累不斷縮小假設集,最終進行判別,已經(jīng)被廣泛用來處理不確定信息的決策問題。而本文正是考慮歷史參數(shù)的不斷積累對服務器性能的影響,這符合D-S證據(jù)理論解決問題的初衷。所以本文提出改進權重的D-S證據(jù)論證的方法,在計算過程中,結(jié)合歷史因素,動態(tài)調(diào)整權重,不斷預測集群中各服務器下一時刻的負載情況。因此當集群接收到請求時,能夠立即響應,不用查找當前服務器的各參數(shù)重新計算負載情況,再進行決策,節(jié)省了計算延時時間,避免了時間積累引起的權重變化使原調(diào)度算法的正確性受到影響,而且在該算法的執(zhí)行次數(shù)較少的情況下,能夠比以往的負載均衡算法更快速準確地執(zhí)行,找到集群中的超載節(jié)點。

1 相關研究

負載均衡算法的目標是實現(xiàn)快速的事務處理能力和響應能力。它一般用于響應網(wǎng)絡請求的網(wǎng)頁服務器或者代理服務器。執(zhí)行負載均衡算法的服務器會在接到任一請求時,在集群中找到當前擁有請求較少且不繁忙的服務器,把請求轉(zhuǎn)移到這些輕載服務器上。負載均衡算法使得MMOG這類大型游戲系統(tǒng)中的各節(jié)點能夠平衡分攤端口負載或網(wǎng)絡流量負載；而且當網(wǎng)絡服務器應用程序接收了無法及時處理的大量入網(wǎng)流量時,會通過各個服務器之間的快速信息交流和負載均衡算法對多個節(jié)點分配任務,提高服務器的處理性能[5],實現(xiàn)在各節(jié)點之間動態(tài)分配負載,最終達到網(wǎng)絡負載平衡的目的。

負載均衡算法一般分為以下兩大類:①靜態(tài)負載均衡算法。該算法在實際運行中不考慮各服務器的負載情況,僅根據(jù)預先設定對客戶端發(fā)送的請求進行分配。②動態(tài)負載均衡算法。該算法能夠根據(jù)服務器當前的負載能力作為分配的準則,動態(tài)地調(diào)整各服務器的負載能力,縮短用戶請求的響應時間。由于動態(tài)負載均衡算法相對于靜態(tài)負載均衡算法的優(yōu)勢顯而易見,因此,動態(tài)負載均衡算法更適合于MMOG這類系統(tǒng)。

目前,對于負載均衡算法有很多研究,例如：加權循環(huán)算法[6],保證了處理能力強的服務器可以接受更多的任務,在一定程度上避免了處理能力低的服務器由于任務過多而癱瘓這一現(xiàn)象的產(chǎn)生；但是沒有考慮到處理請求時間的變化,可能導致集群中各服務器之間負載的不均衡。最快響應速度算法[7]確保了最短的服務器響應時間, 使任務在較短的時間內(nèi)得到分配處理, 不會產(chǎn)生因響應時間過長使任務延時的情況；此算法能較好地反映服務器當前運行狀態(tài), 但最快響應時間僅僅指的是負載均衡器與服務器間的最快響應時間, 而不是客戶端與服務器間的最快響應時間。對數(shù)最小平方矩陣的優(yōu)先級算法[8],為處理器和業(yè)務設置合理的優(yōu)先級,提高了基于遺傳算法的負載均衡調(diào)度效率；但是遺傳算法采用隨機選取處理器為用戶提供服務,可能會有負載不均衡這一狀況的發(fā)生。改進的加權最小連接算法[9]在僅考慮服務器當前連接數(shù)作為負載情況這一缺點上作了改進,將服務器前1 min的負載情況作為一個負載因子,這樣使算法更加準確了解當前服務器的負載信息;該算法雖然考慮了服務器的實際負載情況,但是在服務器權值的設置方面需要考慮的因素較多且復雜。針對異構集群設計的基于索引的負載均衡算法[10],雖然考慮了集群中每個節(jié)點的內(nèi)核數(shù)量和每個內(nèi)核的計算能力不同這兩方面來實現(xiàn)集群服務器的負載均衡,但忽略了節(jié)點的實際負載情況。

以上負載調(diào)度算法雖然在一定程度上實現(xiàn)了集群的負載均衡,動態(tài)地將請求任務均攤到其他服務器上,但是一些負載均衡算法都是依賴當前服務器某個(某些)信息的采集來計算服務器負載情況,均不考慮歷史因素的影響,也就是說無論這臺服務器歷史上的負載情況如何,只要當前這個(這些)因素沒有達到設定閾值,都認為該服務器可以響應下一時刻的請求。這樣可能會導致一個新的問題,就是歷史上某個因素在某一時刻對負載情況的影響雖然較小,但是隨著時間的積累,它的影響逐漸增大,最終導致該服務器超載,那么這些調(diào)度算法計算所得結(jié)果有可能不準確。也就是說,以單純的某一因素為判別條件,很有可能會導致局部判別不確定,使得決策中的最優(yōu)準則未必產(chǎn)生全局最優(yōu)。本文提出的負載均衡算法考慮了影響服務器性能的眾多主要因素,引入歷史條件,采用了區(qū)間估計,而不是點估計,對不確定信息進行描述,利用D-S證據(jù)理論的組合規(guī)則,對得到結(jié)果進行融合判斷,解決了服務器集群的快速準確響應問題。

2 基于權重修正的D-S證據(jù)理論的負載平衡方法

D-S證據(jù)理論的基本概念[11]包括:

1)識別框架。由互不相容的基本命題組成的完備集合,用來表示對某一問題的所有答案的集合,有且僅有一個答案是正確的。

2)基本信任分配函數(shù)。定義集合A為集合D的子集,M為2D上的基本信任分配函數(shù)(mass函數(shù)),m(A)表示對A的信度程度大小。M:2Ω→[0,1],函數(shù)M滿足以下兩種情況的映射：當不可能事件的基本概率是0時,用M(?)=0表示;當2Ω中全部元素的基本概率之和為1時,用∑M(A)=1表示,A∈Ω。其中：M(A)稱為A的基本概率函數(shù),表示對A的精確信任。

3)合成規(guī)則。設M1,M2是2Ω上兩個概率分配函數(shù),則其正交和M=M1+M2定義為:

其中:

本文把D-S證據(jù)理論應用于集群均衡負載方面,在D-S證據(jù)理論的基礎上,引入了動態(tài)權重的概念,實時改變當前權重,使決策結(jié)果更加準確,并采用基于推理的數(shù)據(jù)融合方法,即結(jié)合歷史數(shù)據(jù)與實時數(shù)據(jù)相融合的方法來計算動態(tài)權重,再依據(jù)動態(tài)權重與原始信度二者建立的基本信任函數(shù)決策方法進行證據(jù)合成,最終辨別服務器是否超載。

本文算法中,將判斷服務器是超載還是輕載作為識別框架,那么D-S證據(jù)理論整體合成規(guī)則如圖1所示。

圖1 D-S證據(jù)理論整體合成規(guī)則Fig.1 Rules of D-S evidence synthesis

本文通過初始構造識別框架即設置四種判據(jù)組成的集合設為E={1,2,3,4},根據(jù)不同判據(jù)的判斷結(jié)果定義識別框架Θ={超載,輕載}。定義基本信任函數(shù)Mi、焦元Ai以及各個證據(jù)之間沖突的程度K,再利用證據(jù)合成規(guī)則進一步融合,若最終沖突程度小即說明合成結(jié)果可信,則根據(jù)組合后的信任函數(shù)進行判斷,判別出服務器是否超載。

2.1 動態(tài)權重計算方法

節(jié)點的動態(tài)權重是根據(jù)節(jié)點的相關參數(shù)計算出來的,由于本文中實驗是以MMOG為背景的,系統(tǒng)參數(shù)中的CPU、內(nèi)存、磁盤和占用帶寬這四項參數(shù)在MMOG中為影響集群性能的主要參數(shù)，而其他參數(shù)對于服務器集群的影響較小,因此本文選取這四項參數(shù)為實驗判據(jù)。

對于權重修訂有兩種思路：第一種為完全依賴當前獲取的參數(shù)來計算動態(tài)權重,雖然簡化了計算量,但是沒有考慮參數(shù)的動態(tài)變化對系統(tǒng)的影響,所以不能完全準確地描述出節(jié)點的負載情況,容易造成誤判的結(jié)果;第二種為依靠歷史數(shù)據(jù)來計算動態(tài)權重,這種修正方法在一定程度上避免了第一種方法的不足,但是如果對歷史數(shù)據(jù)的依賴過強,則累計的誤差會比較大,而且也會增加計算量。所以參與計算的歷史參數(shù)既不能太多,又不能太少,本文選取最近兩次的歷史數(shù)據(jù)進行融合計算權重,即可滿足要求。

2.2 信度計算方法

D-S證據(jù)理論的常用決策有三種:基于信任函數(shù)的決策、基于基本可信度賦值的決策和基于最小風險的決策?；谛湃魏瘮?shù)的決策方式作為不確定性信息處理的重要數(shù)學模型具有廣泛應用,能夠區(qū)分不確定和未知的差異,從而很好地表示不確定和未知等認知學上的概念,且推理形式簡單,而本文正是利用歷史數(shù)據(jù)因素來進一步推斷服務器超載還是輕載的不確定結(jié)果,因此本文采用基于信任函數(shù)的決策方法。

在基本信任分配函數(shù)中定義K為多個證據(jù)之間的沖突系數(shù),用來表示各個證據(jù)之間的沖突程度。當沖突系數(shù)K接近或等于1,也就是證據(jù)出現(xiàn)嚴重沖突,會導致融合結(jié)果不可信。為避免這一情況,在決策過程中要不斷更新信任函數(shù)。本文的信任函數(shù)選擇方式與原始信度和權重有關,更新方法為:

其中:m表示信任函數(shù);w表示權重。

2.3 融合決策方法

通過上兩節(jié)提出的動態(tài)權重以及原始信度,多個證據(jù)信息的mass函數(shù)m1、m2、…、mn對于識別框架D的合成規(guī)則,運用式(1)計算證據(jù)合成：

(1)

運用式(2)計算沖突系數(shù)K,K稱為多個證據(jù)之間的沖突系數(shù),可用于定義各個證據(jù)之間沖突的程度,K越大,說明證據(jù)間沖突程度越大;K越小,說明證據(jù)間沖突程度越小。若K等于1或者趨近于1,則不能用D-S證據(jù)組合規(guī)則進行數(shù)據(jù)融合。

(2)

經(jīng)過證據(jù)合成的比較即系統(tǒng)參數(shù)增加或者減少的對比,若證據(jù)合成結(jié)果相等,則該節(jié)點負載平衡,無需增加或減少任務量;若證據(jù)合成比較的結(jié)果為增加,則該節(jié)點超載,應適當較小任務量;若證據(jù)合成比較的結(jié)果為減少,則該節(jié)點輕載,應適當增加任務量。最終使系統(tǒng)中每個節(jié)點均衡負載,考慮集群中每個節(jié)點的實時負載和響應能力,調(diào)整任務分配比例,以便在某些節(jié)點收到大量請求時避免過載,從而提高服務器集群的總體吞吐量。

2.4 算法實現(xiàn)步驟

根據(jù)動態(tài)調(diào)整權重的策略在D-S證據(jù)理論中的應用,以下說明本文算法的計算過程:

1)設置實時采集權值的周期,周期短而頻繁采集,這樣會給負載均衡器和節(jié)點帶來負擔,增加額外的網(wǎng)絡負荷。在實踐過程中要適當?shù)卣{(diào)整采集負載信息的周期,一般周期設置在5～10 s,根據(jù)服務器系統(tǒng)情況獲取節(jié)點的四種判據(jù)的值。

2)根據(jù)每次采集四種判據(jù)的數(shù)值與設置的閾值進行比較,若判據(jù)判斷參數(shù)增加則用“○”表示,若判據(jù)判斷參數(shù)減小則用“×”表示,建立基于動態(tài)臨近歷史數(shù)據(jù)融合方法示意表。

3)基于動態(tài)臨近歷史數(shù)據(jù)多判據(jù)融合策略,選取最近兩次四種判據(jù)的正判率統(tǒng)計,利用2.2節(jié)中的動態(tài)權重計算方法,對當前的權重進行修正,建立權重修正表。

4)根據(jù)步驟3)得出的動態(tài)權重利用2.3節(jié)中信度計算方法,原始信度與權重的函數(shù)關系計算出原始信度,建立信度表。

5)重復步驟1)～4),采集出每次動態(tài)權重計算出的信度表。

6)經(jīng)過步驟5)得出信度表,利用式(2)計算沖突系數(shù),若計算出的沖突系數(shù)接近于1或等于1,則融合結(jié)果不可信;若計算出的沖突系數(shù)不等于1或接近于1,利用式(1)計算證據(jù)合成,計算出每次合成結(jié)果即增加或減少。

7)根據(jù)每次得出的合成結(jié)果,比較增加與減少次數(shù),確定最終節(jié)點是輕載還是超載。若增加次數(shù)多,則該節(jié)點為超載節(jié)點,應適當減小任務量;若減少次數(shù)多,則該節(jié)點為輕載節(jié)點,應適當增加任務量。最終使集群負載均衡,達到提高服務器集群的吞吐量以及系統(tǒng)性能的目的。

3 實驗與分析

本實驗在大型多人在線游戲(王者榮耀)的情景下,搭建集群,其中有1臺均衡器,3臺服務器,征集10位玩家在同一時刻玩游戲,以此來模擬MMOG系統(tǒng)。使用的3臺服務器和均衡器均為Windows 7 64位4 GB內(nèi)存,其余10位玩家所玩機器為客戶端,均為Windows 7 32位,內(nèi)存4 GB。在10位玩家玩游戲一段時間后,均衡器向3臺服務器發(fā)送請求獲取當前集群中各服務器的4種參數(shù)情況,當服務器接收到均衡器的請求后向其發(fā)送數(shù)據(jù)。實驗將檢測基于改進權重的D-S證據(jù)理論算法與當前比較推崇的基于負反饋機制的動態(tài)算法與加權循環(huán)算法兩種動態(tài)負載平衡算法在游戲運行時對服務器是否超載的正判率的對比以及各算法執(zhí)行時間的對比來比較兩種算法作用下的負載判別情況。

3臺服務器各采集出7組數(shù)據(jù)作為實驗樣本。服務器1、服務器2、服務器3采集出的樣本數(shù)據(jù)如表1所示。

表1 服務器1、服務器2、服務器3采集的數(shù)據(jù)Tab. 1 Collected data in server 1, server 2, server3

表2 服務器1、服務器2和服務器3基于動態(tài)臨近歷史數(shù)據(jù)融合方法示意表Tab. 2 Criterion results of server 1, server 2, server 3 based on dynamic proximity historical data fusion method

四種判據(jù)的初始權重設置為1/4,將每四種判據(jù)的判別結(jié)果按照先后順序排列,假設四種判據(jù)設置的初始閾值分別為30.000 000%、17.000 000%、70.000 000%、0.100 000%,將四種判據(jù)采集的數(shù)據(jù)分別與對應的閾值作比較,若判據(jù)判斷參數(shù)增加則用“○”表示,若判據(jù)判斷參數(shù)減小則用“×”表示,建立基于動態(tài)臨近歷史數(shù)據(jù)融合方法示意表,最終四種判據(jù)的判別結(jié)果如表2所示。

選取前兩次的歷史數(shù)據(jù)進行權重計算,如表2中,服務器1數(shù)據(jù)融合方法表中第三次的權重依賴于第一次和第二次獲取的歷史結(jié)果,采用數(shù)據(jù)融合的方法,對第三次的權重進行調(diào)整,參照2.2節(jié)的調(diào)整方法,第三次的權重依次為:

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

依此類推,在每次權重部分都應用上述計算方法,對各判據(jù)對應的權重進行調(diào)整,為下一次判斷作準備。

使用2.3節(jié)中所提到的信度計算方法,得到第三次決策的四種判據(jù)根據(jù)融合權重修正后的信度,如表3所示。

表3 第三次決策信度結(jié)果Tab. 3 Reliability of the third time

根據(jù)式(1)～(2)計算證據(jù)合成及沖突系數(shù)K。

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

(m1?m2?m3?m4)(減少)=0.381

因為計算出的沖突系數(shù)K=0.889≠1,所以融合結(jié)果可信。因此有(m1?m2?m3?m4)(增加)>(m1?m2?m3?m4)(減少),最終判別結(jié)果為增加。

依此類推,其他判別結(jié)果的計算方法與第三次判別結(jié)果計算方法完全相同。表4為服務器1、服務器2和服務器3中各判據(jù)結(jié)果對比。

表4 服務器1、服務器2和服務器3上各判據(jù)結(jié)果對比Tab. 4 Comparison of criterion results in server 1, server2, server3

由表4所知,服務器1在各次融合結(jié)果均可信的前提下,判據(jù)結(jié)果增加次數(shù)多于判據(jù)結(jié)果減小次數(shù),因此判斷判據(jù)增加即服務器超載,應適當減少任務量。

服務器2和服務器3在各次融合結(jié)果均可信的前提下,判據(jù)結(jié)果減小次數(shù)多于判據(jù)結(jié)果增加次數(shù),因此判斷判據(jù)減小即服務器輕載,應適當增加任務量或減少集群中的節(jié)點數(shù)量。

本實驗與基于負反饋機制的動態(tài)均衡算法進行比較?；谪摲答仚C制的動態(tài)均衡算法基本原理:Winit(Ni)表示節(jié)點Ni的初始權值,使用CPU的計算能力、系統(tǒng)I/O速率、內(nèi)存總?cè)萘恳约熬W(wǎng)絡接口速率這四種參數(shù)計算節(jié)點的初始權值。計算公式[12]如下:

(3)

其中:Lf(Ni)表示節(jié)點Ni某一參數(shù)的當前值；Ki表示節(jié)點i的處理器數(shù)量；BASEcpu、BASEI/O、BASEnet、BASEm中參數(shù)的基準值以BASEf來表示，這些基準值可以根據(jù)各節(jié)點的實際情況統(tǒng)計確定；Ri為每個參數(shù)設定的可調(diào)系數(shù),∑Ri=1。

計算各節(jié)點的負載比例L(Ni),利用式(4)計算如下:

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

(4)

其中:Ucpu、Um、Udisk、Ubandwidh分別表示CPU剩余率、內(nèi)存剩余率、磁盤剩余率和占用帶寬。

利用式(5)計算節(jié)點最終權值W(Ni),公式如下:

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

(5)

由式(5)計算出最終權值進行比較,權值最大的即為超載節(jié)點,應適當減小任務量。

將服務器1、服務器2、服務器3獲取的五次參數(shù)用基于負反饋機制的動態(tài)均衡算法計算,得到表5結(jié)果。

表5 服務器1、服務器2和服務器3基于負反饋機制算法的動態(tài)權值Tab. 5 Dynamic weights calculated by negative feedback mechanism algorithm for server 1, server2, server3

由表5可知,各服務器的負載權值不相上下,對比5次實驗結(jié)果可知,服務器2負載最重,即可看作為超載節(jié)點。

由表1獲取的參數(shù)可知,服務器1相對于服務器2和服務器3而言,磁盤剩余率和占用帶寬不相上下,而CPU剩余率和內(nèi)存剩余率相對于另兩臺服務器參數(shù)較高,因此在三者之間,服務器1超載,而服務器2與服務器3相對于服務器1輕載。在基于改進權重的D-S證據(jù)理論的動態(tài)負載平衡算法中,計算出服務器1超載,服務器2與服務器3輕載;而由基于負反饋機制的動態(tài)均衡算法計算出服務器2超載,因此使用基于負反饋機制的動態(tài)均衡算法計算結(jié)果與真實結(jié)果不符,本文使用的基于改進權重的D-S證據(jù)理論的動態(tài)負載平衡算法計算結(jié)果更符合實際情況。

在比較算法執(zhí)行時間方面,選取基于負反饋的動態(tài)均衡算法和加權循環(huán)算法與本文算法相比較。由圖2～3可以看出,基于負反饋機制的動態(tài)均衡算法和加權循環(huán)算法波動較大,在算法執(zhí)行開始時,其執(zhí)行時間相比D-S證據(jù)理論算法的執(zhí)行時間短,但隨著執(zhí)行次數(shù)的增加,其執(zhí)行時間也會隨之波動,執(zhí)行時間普遍偏高。而基于改進權重的D-S證據(jù)理論算法波動較小,在開始執(zhí)行的幾次實驗中,雖然其執(zhí)行時間較高,但隨著執(zhí)行次數(shù)的增加,接下來幾次算法的執(zhí)行時間趨近于0。正是因為D-S證據(jù)理論算法的權重部分受歷史因素的影響,在多次執(zhí)行算法之后,能夠根據(jù)前幾次的負載結(jié)果推斷出來,所以在一段時間內(nèi),該算法的執(zhí)行時間相比另外兩種算法的執(zhí)行時間短。而后,隨著大量實驗次數(shù)的增加以及集群中各服務器負載情況的變化,三種算法對各服務器的負載狀況也會隨之更新并且重判,再次找到集群中的超載節(jié)點,三種算法的執(zhí)行時間又如圖2～3所示,因此該實驗從算法執(zhí)行時間上驗證基于D-S證據(jù)理論的算法相比另外兩種算法的總執(zhí)行時間更短,更適合在MMOG情景下,在短時間內(nèi)能夠準確地反映出集群中各服務器的負載情況。

圖2 本文算法與基于負反饋機制的動態(tài)均衡算法執(zhí)行時間的比較Fig. 2 Running time comparison of the proposed algorithm and the dynamic balancing one based on negative feedback

圖3 本文算法與加權循環(huán)算法執(zhí)行時間的比較Fig. 3 Running time comparison of the proposed algorithm and the weighted loop one

4 結(jié)語

本文提出一種在MMOG情景下基于改變權重的D-S證據(jù)理論的負載平衡算法,從發(fā)展的角度,結(jié)合歷史因素,動態(tài)調(diào)整權重,不斷預測服務器的負載情況,準確判斷節(jié)點是否超載,將歷史數(shù)據(jù)與實時數(shù)據(jù)相結(jié)合,采用多判據(jù)融合,選取最近兩次的正判率統(tǒng)計,按照“判斷正確權重增加,判斷錯誤權重不變”的準則,不斷修正各因素的權重,然后計算各因素的信度函數(shù)。基于信任函數(shù)的決策方式,為避免證據(jù)出現(xiàn)嚴重沖突,根據(jù)權重不斷調(diào)整信任結(jié)果,最后對多個因素的信任結(jié)果進行融合,融合結(jié)果增加,則判斷該點為超載,否則為輕載。MMOG網(wǎng)絡集群中,服務器的數(shù)量和性能與客戶的要求和實際連接數(shù)有很大關系,在這種大型網(wǎng)絡中,參與工作的節(jié)點要由實際情況決定,網(wǎng)絡規(guī)模和服務器數(shù)量隨時都可能發(fā)生改變,但是無論怎么改變都是小規(guī)模的網(wǎng)絡組成大規(guī)模的網(wǎng)絡。所以本文模擬一個小型MMOG系統(tǒng)進行實驗。雖然本實驗平臺與以MMOG系統(tǒng)為基準的目標平臺存在一定差距,但是在本實驗平臺上,本文算法可以快速準確地找到集群中超載的節(jié)點,達到了解決問題的目的,而且決策結(jié)果可以維持一段時間不變,然后根據(jù)需要再進行運算判斷。