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

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

0 引言

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

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

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

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

1 相關(guān)研究

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

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

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

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

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

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

1)識(shí)別框架。由互不相容的基本命題組成的完備集合,用來(lái)表示對(duì)某一問(wèn)題的所有答案的集合,有且僅有一個(gè)答案是正確的。

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

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

其中:

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

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

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

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

2.1 動(dòng)態(tài)權(quán)重計(jì)算方法

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

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

2.2 信度計(jì)算方法

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

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

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

2.3 融合決策方法

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

(1)

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

(2)

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

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

根據(jù)動(dòng)態(tài)調(diào)整權(quán)重的策略在D-S證據(jù)理論中的應(yīng)用,以下說(shuō)明本文算法的計(jì)算過(guò)程:

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

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

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

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

5)重復(fù)步驟1)～4),采集出每次動(dòng)態(tài)權(quán)重計(jì)算出的信度表。

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

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

3 實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(3)

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

計(jì)算各節(jié)點(diǎn)的負(fù)載比例L(Ni),利用式(4)計(jì)算如下:

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

(4)

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

利用式(5)計(jì)算節(jié)點(diǎn)最終權(quán)值W(Ni),公式如下:

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

(5)

由式(5)計(jì)算出最終權(quán)值進(jìn)行比較,權(quán)值最大的即為超載節(jié)點(diǎn),應(yīng)適當(dāng)減小任務(wù)量。

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

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

由表5可知,各服務(wù)器的負(fù)載權(quán)值不相上下,對(duì)比5次實(shí)驗(yàn)結(jié)果可知,服務(wù)器2負(fù)載最重,即可看作為超載節(jié)點(diǎn)。

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

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

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

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

4 結(jié)語(yǔ)

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