ＭＭＯＧ中的一種動態負載共享算法

摘要：針對MMOG中的服務器超載問題，提出一種動態負載共享算法，使得一個超載的服務器能夠方便地將它的一部分負載遷移到沒有超載的服務器上。同時在基于預訂區域概念的基礎上，通過擴大鄰居服務器的范圍，提出一種客戶端遷移方案來減少該算法的開銷，從而提高系統的響應速度和性能。

關鍵詞：負載共享；負載均衡；大型多人在線游戲；網絡游戲

中圖分類號：TP301．06文獻標志碼：A

文章編號：1001－3695(2007)07－0249－03

0引言

近年來，隨著網絡的發展，MMOG（大型多人在線游戲）作為一種新型的娛樂產業受到越來越多的關注。MMOG可以容納幾萬人甚至幾十萬人同時在線游戲，由于玩家數量巨大而網絡資源有限，MMOG也面臨著一些挑戰。例如，網絡中大量不確定的消息傳輸延遲可能引起玩家之間感覺上的矛盾，從而影響游戲的交互性。而且，游戲中玩家數量的大量增加可能引起嚴重的可擴展性問題。目前大部分MMOG都采用一種分布式C/S結構。在這種結構中，多個服務器相互之間通過高速連接設備，并且各個客戶端可以根據它們在現實世界中的物理位置或者在虛擬世界中的虛擬位置，連接到其中的一個服務器上。

本文主要討論并解決了采用基于虛擬世界分割方法的分布式C/S結構的MMOG中的服務器端負載遷移問題。提出一種負載共享算法以便于一個超載的服務器能夠將它的一部分負載遷移到沒有超載的服務器上。同時，提出一種客戶端遷移方案來減少該負載共享算法運行時的開銷。

1相關工作

在過去幾十年中，分布式系統中的負載分配問題已被廣泛研究。

文獻[1]使用一種客戶端數量和客戶端之間的交流相應增加的圖表分割方法在分布式服務器中分配負載。但是這種方法會占用太多的時間，并不適合于像MMOG這樣的大型實時應用程序。

文獻[2]在X軸上垂直劃分虛擬世界，每一個游戲服務器管理其中一個分區。通過沿著X軸重新定位分區線來達到動態負載均衡。一個超載的服務器只能向它的兩個相鄰的服務器遷移負載。但是，如果這兩個服務器均已超載，那就可能出現負載層疊遷移的現象，這會導致大量的客戶端遷移，增加系統開銷，損害整個游戲的互動性。文獻[3]將虛擬世界中共享相同邊界線的子空間互稱為鄰居服務器，并且優先遷移靠近邊界線的客戶端。但是在這種方式下，一個服務器最多只有四個鄰居服務器，同樣容易發生負載層疊遷移。

本文在玩家視野范圍的基礎上定義一個預訂區域，虛擬世界中共享相同邊界線或相同頂點的子空間均互稱為鄰居服務器，這樣就可以有八個鄰居服務器，并且優先遷移預訂區域中的客戶端。實驗表明，擴大鄰居服務器范圍可以有效提高系統效率。

2MMOG系統的特點

對于一個典型的MMOG系統，主要有以下幾個特點：

（1）高度交互性。MMOG是實時交互應用程序。它的負載分配算法不應該被頻繁執行，也不應該導致太多的服務器超載，因為這些服務器忙于服務大量的客戶端。

（2）系統規模龐大。為了支持幾十萬玩家同時在線，MMOG需要大量的服務器。因此，設計一個負載分配算法還應仔細考慮避免花費在服務器負載信息搜集上的成本過多。

（3）負載可能層疊遷移。因為每一個服務器管理虛擬世界的一個劃分區域，所以負載只能直接從一個服務器遷移到它的鄰居服務器。當一個超載的服務器的所有鄰居服務器也都達到極限時，鄰居服務器為了能夠接收負載，需要將它的一部分負載遷移到另外的鄰居服務器上。很明顯，在負載層疊遷移情況下，涉及到的服務器數量越多，總的客戶端遷移數量就越大。因此，MMOG中的負載分配算法應該盡量限制負載遷移中所涉及到的服務器數量。

（4）客戶端遷移任務的繁重性。MMOG中的負載分配是通過在服務器之間轉移客戶端來實現的。基本上客戶端不得不斷開它與當前服務器（老的服務器）之間的連接，然后與另一個服務器（新的服務器）建立一個新的連接，這個過程要花費一些時間。新的服務器可能并不能立即提供該客戶端的更新，這樣，游戲的交互性就可能受到破壞。因此，MMOG的負載分配算法應該盡量限制客戶端遷移的數量，這就需要一個客戶端平滑遷移的方法。

基于以上的分析可以看出，負載共享算法比負載均衡算法更適合于MMOG系統。因為負載共享算法只是試圖避免服務器的超載而不要求各服務器之間達到負載平衡。總的來說，負載共享算法可以相對減少客戶端遷移數量，并且能夠比負載均衡算法更快地執行。下面將提出一種新的有效的動態負載共享算法。

3一種動態負載共享算法

3．1系統模型

整個虛擬世界被分割成一個由N個大小相同的正方形單元組成的網格，如圖1所示。服務器的數量是n，這里n≤N。每一個服務器管理一組相鄰的單元，這組相鄰的單元叫做一個分區。首先，假設所有的分區有同樣的大小，即它們有同樣數量的單元。服務器用S1，S2，…， Sn來表示。同樣地，各個單元被表示成C1，C2，…， CN。為簡便起見，如圖2所示，將每一個服務器管理的分區表示為一個單獨的正方形，雖然每一個分區的大小都可能隨著時間的改變而改變。圖2顯示了怎樣用一組（36個）服務器來管理整個虛擬世界，此虛擬世界被分割成36個分區。

以32個服務器，每個服務器的極限為50為例，將本文算法（DLS）與一般的局部負載均衡算法（LLB）以及文獻[3]中的全局負載均衡算法（GLB）作比較，實驗結果如圖4、5所示。從圖中可以看出，GLB與DLS算法的超載減少率均為1，這是因為執行算法之后系統中沒有超載服務器，而LLB的超載減少率則比較小；LLB算法的遷移率最低，但是因為該算法只在局部范圍內分配負載，所以系統無法有效減少服務器的超載，而與GLB算法相比，DLS算法具有較低的遷移率。從實驗結果得知，該DLS算法具有較高的超載減少率和較低的遷移率，可以有效滿足MMOG類型應用程序的要求。

5結束語

提出一種適用于MMOG的動態負載共享算法，同時，提出一種客戶端遷移方案來減少該算法的開銷。通過比較分析，該算法具有較好的性能。下一步將在基于分布式C/S結構的大規模互聯網在線游戲中實現該動態負載共享算法。

參考文獻：

［1］JOHN C，LUI S， CHAN M F.An efficient partitioning algorithm for distributed virtual environment systems[J].IEEE Transaction on Parallel and Distributed Systems， 2002，13(3):193－211.

[2]MIN D，CHOI E， DONGHOON L，et al.A load balancing algorithm for a distributed multimedia game server architecture[C]//Proc of the IEEE lnternational Conference on Multimedia Computing and Systems.[S.l.]:[s.n.]，1999:882－886.

[3]NGUYEN T， DUONG B， ZHOU S.A dynamic load sharing algorithm for massively multiplayer on－line games[C]//Proc of the 11th IEEE International Conference on Networks.[S.l.]:[s.n.]，2003:131－136.

[4]SHINYA Y，YOSHIHIRO M， KEIICHI Y，et al.A distributed event delivery method with load balancing for MMORPG[C]//Proc of the 4th ACM SIGCOMM Workshop on Network and System Support for Games NetGames’05.[S.l.]:[s.n.]，2005:214－218.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”