游戲網格服務劃分算法研究
2009-01-01 00:00:00薛勝軍張小華
計算機應用研究 2009年1期
（南京信息工程大學 計算機與軟件學院， 南京 210044）
摘 要：為了充分利用游戲網格的計算資源，使用其強大的并行計算能力，部署在游戲網格的網絡游戲必須要劃分成可以并行的多個服務。提出了一種基于動態二叉樹的游戲網格服務劃分算法；討論了如何采用二叉樹的數據結構來組織服務節點并根據服務節點的負載動態調整其服務劃分；最后實現一個模擬游戲網格環境，通過實驗結果證明該算法可以取得良好的性能。
關鍵詞：游戲網格； 服務劃分； 負載平衡
中圖分類號：TP301.6 文獻標志碼：A
文章編號：10013695(2009)01008203
Study on game grid service partitioning algorithm
XUE Shengjun， ZHANG Xiaohua
(College of Computer Software， Nanjing University of Information Science Technology， Nanjing 210044， China)
Abstract:In order to make the most of computing resources and computing power of game grid， the network game， deployed in game grid， should be divided into several parallel services. This paper put forward a game grid service partitioning algorithm based on dynamical binary space partitioning tree. It discussed how to use data structure of binary space partitioning tree to organize service node and adjusted service division dynamically according to the load of service node， thus achieving a simulative game grid environment. In the end， the paper demonstrated the good performance of the game grid service partitioning algorithm through experiments.
Key words：game grid; service partition; load balance
大型多人角色扮演游戲(massively multiplayer online role playing games，MMORPG)經常有百萬數量的游戲玩家同時在線參與游戲。任何單一的服務器都沒有能力處理百萬游戲玩家同時在線，這就需要通過網格技術[1]來解決。網格技術可以提供強大的計算資源和很好的可擴展性，可以減少網絡游戲的初始投資，降低游戲運營的風險，很好地解決當游戲玩家大量增加或減少時對計算資源的動態需求。
目前只能通過將整個MMORPG劃分成多個小的游戲服務來將其部署到游戲網格上。可以對整個游戲采用邏輯功能劃分得到多個功能服務，如數據庫服務、網關服務等。這些服務不能再加以邏輯劃分，而只能同時運行多個服務實例來提高游戲整體性能。但是游戲場景服務是一類特殊的游戲服務，它不能采用直接運行多個實例的方式，因為整個游戲的場景必須保持實時一致，如果多個服務器運行整個游戲場景，則多個場景服務器之間的通信代價將遠遠大于其并行邏輯計算帶來的好處。游戲網格服務劃分就成為一個非常重要的問題。
1 游戲服務劃分的關鍵問題和研究現狀
游戲服務劃分需要考慮的問題有[2]：
a)連通性。游戲世界類似于真實的世界，它所劃分的小區域都與其他的小區域互相連通或者存在邏輯聯系，孤立存在的小區域很少。這些小區域可能不是運行在同一個服務器上，但是在一個小區域內的游戲對象所產生的活動和事件可能會對其他鄰近小區域的游戲對象產生影響，或同時對幾個小區域內的游戲對象產生影響的事件也是存在的。任何一種游戲世界劃分方法都必須保證整個游戲世界的完整性和游戲狀態的一致性。
b)數據交換。整個游戲只由一臺服務器運行就不會存在數據交換的需求，但是這也就不能充分利用網格并發帶來的優勢。由于游戲世界劃分成了很多小區域，這些區域可以在多個游戲服務器上同時運行，為了保持游戲狀態的一致性，在多個游戲服務器之間必須進行數據交換。
c)劃分粒度。游戲世界劃分的一個關鍵問題是確定劃分的游戲區域的大小，也就是游戲世界劃分的粒度。如果區域劃分太大，這樣并行的區域服務器相應很少，當游戲中的玩家聚集在某一個區域時，可能導致該區域服務器過載；而區域劃分太小，會產生很多小的區域，假設一個區域只運行在一個服務器上，這樣會造成服務器之間的狀態同步需求過多而降低系統的整體性能。所以選擇一個有效的劃分粒度既要考慮服務器數量的上限，也要考慮游戲世界中各個區域之間的耦合程度。
目前這方面的研究已經取得了很多成果。Vleeschauwer等人[3]提出了microcell的概念以及動態將microcell分配給服務器的一組算法、平衡算法、Clustering算法、模擬退火劃分算法和最優算法。
RING[4]支持一種將虛擬世界劃分成部分區域的模型，每一個被劃分的部分區域只能由事先綁定好的服務器來運行，不能進行動態調整。
Cyberwalk[5，6]是一種基于網頁的多服務器分布式游戲，游戲世界被有規律地劃分成大量的三角形單位，每一個服務器處理一定數量的三角形所組成的游戲區域，每個游戲區域都可以動態調整其大小。每個服務器處理的區域大小可以根據服務器的負載動態進行調整，但是如果在一個服務器中同時存在幾個熱點，這將對服務器的性能產生嚴重的影響。因為負載只能在相鄰服務器之間進行平衡，而且根據數據分解的負載平衡的效果很有限。這是因為這種負載模式是基于當服務首次被分配時預留的資源。
Deen等人將Quake Ⅱ游戲進行修改并部署在游戲網格上。它的游戲世界被有規律地分成大量OPC（original process cell），然后將多個互相連通的OPC組織成OPC集合；多個OPC集合由一個服務器處理；OPC集合作為負載平衡的基本單位[7]。這種方式的缺點是算法必須要知道游戲世界的組織方式才能進行游戲服務劃分，缺乏通用性且OPC集合的大小很難得到合理的數值。
通過對目前的研究成果進行分析，可以將服務劃分方法歸納為兩種：靜態服務劃分與動態服務劃分。
靜態服務劃分方法是根據網絡游戲的某一固有特性將游戲世界劃分成為大量的小區域，如RING采用的方法。靜態服務劃分方法實現簡單，但不能進行負載平衡，因此不能充分地利用網格資源。
動態服務劃分方法是游戲世界被有規律地劃分成大量的游戲區域，每一臺服務器處理一定數量的游戲區域，每個游戲區域都可以在服務運行過程中根據預先定義好的條件動態調整其大小，如平衡算法、Clustering算法和模擬退火劃分算法等。
動態服務劃分方法可以充分利用網格資源動態分配的優勢，但是目前的動態服務劃分算法都存在一定的缺點：平衡算法和Clustering算法都沒有考慮游戲世界的連通性；模擬退火劃分算法求解方法太復雜，求解時間不確定，對網絡游戲的一致性產生很大的影響；最優算法只在理論上存在；Deen等人提出的算法雖然考慮了游戲世界的連通性，但是必須知道游戲世界的組織方式，需要預先定義好OPC，缺乏通用性。
2 游戲網格服務劃分問題的形式化定義
游戲網格由游戲實例、運行游戲服務的資源，以及游戲玩家在游戲中的角色組成，符號化為G={W，R，P}。其中：G表示游戲網格；W表示一個游戲世界；R表示網格中的資源；P表示游戲玩家角色。
游戲世界劃分為W={W1，W2，…，Wk}，M個資源R={R1，R2，…，Rm}，J個玩家角色P={P1，P2，…，Pj}，N個服務T={T1，T2，…，Tn}。服務Ti=∑Ki=1Wi+∑Jj=1Pj (1＜i＜K，1＜j＜P)表示Ti是由K個游戲世界的小部分即游戲場景和在游戲場景上的J個游戲玩家組成，每個服務僅能分配到一個資源上執行。設Cimax表示第i個資源能承受的最大負載，Cij表示第i個服務在資源j上的執行負載。L(i)=j表示第i個服務分配到資源j上執行。L(i)M(t)=c表示在t時刻，第i個服務中所產生的消息數量，Mc=∑ni=1L(i)∑mt=1M(t)表示游戲運行過程中產生的消息總數量。
游戲網格服務劃分的目標是將W劃分為K個場景加入到N個服務中，N個服務分配到M個資源的一組映射關系S，Ti=∑Ki=1Wi+∑Jj=1Pj(1＜i＜K，1＜j＜P)，S={L(1)，L(2)，…，L(i)，L(n)}（1＜L(i)＜M，1＜i＜n）使得在服務執行過程中沒有超載的資源（為方便后文引述記為基本問題1）:
Ti∈T，Cij＜Cimax
而且游戲的處理延遲最小即要求游戲因服務劃分而產生的消息總數量Mc最小(基本問題2):
Mc=∑ni=1 L(i)∑mt=1M(t)(1＜i＜n，1＜t＜m)
minimize Mc(S)=∑ni=1Mci(1＜i＜n)
問題1表示服務劃分的可行性，如果找不到能滿足基本問題1的解，則表示該算法是不成功的。基本問題2是在基本問題1的基礎上提出的最優解。這樣網格服務劃分問題可以進一步詳細定義為以下優化問題：
在服務執行過程中，沒有超載資源和消息數量不超過預先給定值Mctotal的前提下，將W劃分為K個場景加入到N個服務，N個服務分配到M個資源的一組映射關系S：
minimize Mc(S)=∑ni=1Mci(1＜i＜n)
Mc=∑ni=1L(i)∑mt=1M(t)(1＜i＜n，1＜t＜m)
Ti∈T，Cij＜Cimax
映射關系S就是所求的解。
3 算法的求解過程
動態二叉樹服務劃分方法使用二叉樹的數據結構L={N1，…，Nk}來劃分游戲場景，使用雙向鏈表L={N1，…，Nm}組織游戲場景。二叉樹的內部節點與葉子節點是不相同的。內部節點不包含游戲場景或者其他游戲對象的相關信息，只保持整個樹的結構信息；而一個葉子節點上有它包含的游戲場景所有的游戲狀態信息，它與一個服務場景一一對應。最初只有一個服務場景，用二叉樹的根節點表示，隨著玩家的增多，節點負載加大，當負載增加到一定的程度時，啟動游戲負載平衡服務，將節點一分為二，形成兩個葉子節點，所有的游戲狀態信息也同時分到兩個葉子節點上。以后負載平衡服務將負載達到一定程度的節點再分成兩個葉子節點。分裂采用二叉樹的結構進行操作。
當負載平衡服務檢測到同一個父親節點的兩個葉子節點的負載都小時，就將這兩個葉子節點合并成為一個葉子節點，即收縮。如果收縮之后的兩個葉子節點仍然可以合并，這時會再次進行合并。由于劃分和收縮都是在連通的場景內進行，不會出現孤立的幾個場景在一個節點上，這樣就可以使整個游戲負載沒有過大，或者過小的節點存在，使游戲性能維持在一個比較好的水平。收縮采用雙向鏈表的結構進行操作。雙向鏈表L={N1，…，Nm}就是所要求的解S。
動態二叉樹服務劃分算法的具體步驟，如圖1所示。
具體步驟說明如下：
a)參數初始化。設定時間t=0，Rmax=const，Cimax(t)=const。其中：const表示常數；Rmax表示最大資源數量。生成二叉樹R的root節點，將游戲場景W分成場景單元W={W1，W2，…，Wk}，加載游戲對象P={P1，P2，…，Pj}數據。生成服務T1={W1，…，Wk}+{P1，…，Pj}，T1→R1（時間復雜度為O(n)）。
b)游戲玩家開始進入游戲，檢查各個節點的Cij或兩兄弟節點的Cij判斷是否需要進行負載平衡。需要負載平衡繼續下一步，否則轉至步驟e)（時間復雜度為O(n)）。
c)對Cij＞Cimax的節點進行分裂操作。如果需求的資源Rneed＞Rmax，則先開始資源調整操作，轉到步驟e)。根據節點分裂的標準將Ti分裂為T2i+1={Wk1，…，Wkn}+{Pj1，…，Pjn}，T2i+1→Ri，T2i+2={Wk1，…，Wkn}+{Pj1，…，Pjn}并加入到二叉樹（時間復雜度為O(n2)）。
d)對服務T2i+1和T2i+2，當C2i+1+C2i+2＞Cimax進行合并操作。如果合并后的Ti仍可以與其兄弟節點合并，則繼續合并操作。合并操作完成后繼續下一步對資源進行調整（時間復雜度為O(n)）。
e)檢查資源是否需要進行調整，若不需要則轉至步驟g)，并對資源進行調整（時間復雜度為O(n)）。
f)檢查游戲是否停止，若沒有則轉至步驟b)；否則進入下一步（時間復雜度為O(1)）。
g)游戲停止，算法結束（時間復雜度為O(1)）。
在步驟c)中，如果場景單元n很大時，則一次分裂操作時間相應也會很大。這里可以考慮使用一次匹配方法減少時間復雜度，但會對服務劃分算法的效果產生影響。基本場景單元規模為n的MMORPG動態二叉樹服務劃分算法的總時間復雜度為O(n2)。
4 算法實驗分析
實驗對象：實驗以本文提出的MMORPG動態二叉樹服務劃分算法(以下簡稱B算法)以及Vleeschauwer等人提出的平衡算法和Clustering算法作為實驗研究的對象。因為模擬退火劃分算法求解方法太復雜，求解時間不確定，不能保證網絡游戲的一致性，最優算法只在理論上存在，而Deen等人提出的算法必須了解游戲世界的組織方式，需要預先定義好OPC，所以本文在實驗中不考慮這幾種算法。
實驗目的：通過實驗來檢驗算法的性能。
實驗硬件條件：CPU AMD雙核1.6 GHz，內存1 GB。
實驗環境：本文開發了一個模擬環境提供服務劃分算法的實驗分析。實驗環境中的游戲世界用游戲地圖來表示，玩家的初始游戲地點和游戲動作都是隨機產生。游戲開始時，游戲玩家按順序依次加入游戲；然后隨機進行動作；最后再依次退出游戲。隨機數產生器使用標準C語言程序庫的隨機數函數rand()。
為了評價不同的服務劃分算法的性能，需要選取相應的評價參數。本實驗采用的評價參數有：
a)處理消息數量Msum=∑ni=1Pi(t)(1＜i＜n，1＜t)。游戲玩家在游戲過程中由于動作會產生相應的消息，游戲玩家產生的消息根據是否需要本地服務節點處理還是其他節點處理會產生不同的消息權重，所有權重折算之后的消息總和為處理消息數量。算法的性能主要通過該參數來衡量，在產生相同動作的情況下，性能良好的算法會盡量減少因服務調度而產生的消息數量，所以其值越小，表示算法的性能越好。
b)負載平衡移動游戲玩家數量Asum=∑ni=1Pi∑mj=1Tj(t)(1＜i＜n，1＜j＜m，1＜t)。負載平衡在服務節點調整時移動游戲玩家的數量。其值越小，表示算法的性能越好。
c)負載平衡調整次數Bsum=∑ni=1Ti(t)(1＜i＜n，1＜t)。在一段時間內游戲網格負載平衡的次數。其值越小，表示算法的性能越好。
d)最大的服務器需求量Ti total。在一段時間內游戲網格使用過的最多的服務器數量。其值越小，表示算法的性能越好。
實驗結果如圖2~5所示。
從上面的對比可以看出，隨著玩家角色數量增加，產生的消息總數、對服務器的需求量和負載平衡的次數也呈線性增長，但是負載平衡時移動游戲玩家角色的數量沒有明顯增加。這是因為沒有游戲玩家角色增加是按概率分布的，沒有大量玩家角色聚集在一個小部分區域。所有的算法都能夠很好地處理這種問題，但Clustering算法處理時的各項指標都會出現很不穩定的波動并且波動幅度非常大，這也主要是因為Clustering算法的負載分布不均衡，主要負載都集中在少量幾個服務器上。
平衡算法比其他算法在服務器需求上表現要好，但是與B類算法相差很小。B類算法從產生的消息總數、負載平衡時移動游戲玩家角色的數量和負載平衡的次數上都明顯優于平衡算法和Clustering算法。
5 結束語
本文提出了一種新的游戲網格服務劃分方法，并且在模擬環境中通過實驗驗證了該方法的可行性和有效性。下一步的工作是將這個方法在實際游戲網格中運行，并根據實際運行的效果提出進一步的改進方案。
參考文獻：
［1］FOSTER I， KESSELMAN C. 網格計算[M].金海， 袁平鵬， 石柯，譯. 2版. 北京：電子工業出版社， 2004.
[2]DEEN G， HAMMER M， BETHENCOURT J， et al. Running quake Ⅱ on a grid[J]. IBM Systems Journal， 2006，45（1）：2144.
[3]VLEESCHAUWER B D， BOSSCHE B V D， VERDICKT T， et al. Dynamic microcell assignment for massively multiplayer online gaming[C]//Proc ofNetGames. 2005.
[4]ASSIOTIS M， TZANOV V. A distributed architecture for MMORPG[C]//Proc ofthe 5th ACM SIGCOMM Workshop on Network and System Support for Games. 2006.
[5]FUNKHOUSER T A. RING：a clientserver system for multiuser virtual environments[C]//Proc of Symp on Interactive 3D Graphics. 1995：8592.
[6]BEATRICE N， ANTONIO S， RYNSON L， et al. A multiserver architecture for distributed virtual walkthrough[C]//Proc of ACM Symposium on Virtual Reality，Software and Technology. Hong Kong:[s.n.]， 2002.
[7]CHIM J， LAU R W H， LEONG H V， et al. Cyber walk:a Webbased distributed virtual walkthrough environment multimedia[J]. IEEE Trans on Multimedia ， 2003，5(4):503515.
