大型虛擬實境系統，能應用在許多不同的領域，例如軍事演練，交通模擬，最常見的應用就是目前流行的多人角色扮演線上遊戲(mmorpg)。
    對線上遊戲的營運商來說，降低營運的成本是很重要的，如果server端能採用分散式的架構，就可以更有效率的使用硬體的效能，分散式的架構，也更容易擴充系統的運算能力，帶來更高的運算效能，並提供更多的遊戲性的發展可能。
因此本論文研究提出一個方法”幾何空間切割演算法Geometry Distribute Algorithm，簡稱GSA”， GSA根據伺服器的負載強度，來決定在2維虛擬實境空間下，將運算負載分配給適當的伺服器，以達到整個系統的負載平衡。

Large scale virtual reality system can apply in many situations. Such as military training and traffic simulation. The most popular application is massively multi player role playing game (mmorpg).

To reduce the service cost, it is very important for online game service provider. Using distributed computing architecture. That can reduce cost and make servers more efficient. Distributed computing architecture also made better scalability and more computing power. This will bring more possibility for game designing.

This thesis proposed an algorithm “Geometry Splitting Algorithm, GSA”. It can dispatch loading to servers in 2D virtual space. GSA can make each server in good loading status and whole system in loading balance.

目錄
第一章 、緒論	1
1.1 研究動機及研究目的	1
1.2 論文架構	2
第二章 、相關研究	3
2.1 Client-Server架構	3
2.2 Zone Base的世界	4
2.3 Zone Instance的世界	5
2.4 Peer ot peer的架構	6
2.5 空間切割與分散式運算	8
第三章 研究內容與方法	10
3.1 系統架構	10
3.2 將伺服器對應到二元樹的結構	13
3.3 將伺服器對應到二元樹結構的C++ code	15
3.4 將伺服器對應到二元樹的範例	16
3.5 分配空間給伺服器，使得負載平衡	18
3.6 分配空間給伺服器的C++ code	20
3.7 分配空間給伺服器的範例	25
3.8 調整伺服器分配的空間	29
3.9 調整伺服器分配的空間的C++ code	34
第四章 、模擬實作與結果討論	36
4.1 模擬實作說明	36
4.1.1 模擬實作目標	36
4.1.2 模擬實作環境	37
4.1.3 定義資料結構	37
4.1.4 實作介面說明	39
4.2 模擬結果與討論	40
4.2.1	模擬均勻負載的情況(一)	41
4.2.2	模擬負載轉移的情況(二)	42
4.2.3	模擬負載變化的情況(三)	43
4.2.4	模擬負載變化的情況(四)	44
4.2.5	模擬負載變化的情況(五)	45
4.2.6	模擬負載變化的情況(六)	46
4.2.7	模擬負載變化的情況(六)	47
第五章、結論與未來相關研究	48
5.1結論	48
5.2未來相關研究	48
參考文獻	50
附錄—英文論文	51

圖目錄
圖2.1：Client Server架構圖	3
圖2.2：Zone Base架構圖	5
圖2.3：Zone Instance架構圖	6
圖2.4：空間切割的架構	9
圖3.1：最終的對應關係	11
圖3.2：系統的運作流程	12
圖3.3：將集合S切割成兩個子集合S1,S2	13
圖3.4：建立一個binary tree	14
圖3.5：所有的leaf都無法再切割	14
圖3.6：當N=5時,第一次切割	16
圖3.7：當N=5時,第二次切割	16
圖3.8：當N=5時,第三次切割	17
圖3.9：當N=5時,切割結果	17
圖3.10：切割cell與區域分割	18
圖3.11：從root開始,將虛擬世界切割成兩個區域,使負載比=A:B	19
圖3.12：當N=5,間切割的示意圖	20
圖3.13：第一次分配	25
圖3.14：第二次分配	26
圖3.15：第三次分配	27
圖3.16：最後一次分配	28
圖3.17：最少調整的情況	29
圖3.18：負載範圍Lr	30
圖3.19：當M4超過負載,只需要調整M4,M5之間的切割線	31
圖3.20：M4負載不平衡,必須遞迴向上直到{M3,M4,M5}一起調整	32
圖3.21：第一次重新切割	32
圖3.22：重新切割結束	33
圖4.1：模擬程式的操作介面	39
圖4.2：均勻負載的情況	41
圖4.3：A的負載降低,調整切割線,使B減少部分的負載	42
圖4.4：A的負載不斷減低,調整切割線讓C,D來分擔負載	43
圖4.5：A的負載極不斷降低,最後造成全部重新切割	44
圖4.6：當A的負載增加,範圍又開始變小	45
圖4.7：A負載慢慢增加造成，{C,D}來分擔{A,B}的負載	46
圖4.8：A負載慢慢繼續增加，{E,F,G,H}來分擔{A,B,C,D}的負載	47
 
表目錄
表3.1：BuildTree Function	15
表3.2：StepSplit fFunction	21
表3.3：MakeSplitRect Function	22
表3.3：IncrementSplit Function	34
表4.1：環境平台軟硬體設備	37
表4.2：矩形物件	37
表4.3：Nnode物件	38
表4.4：樹狀結構	38

Baughman N.E., “Cheat-Proof Playout for Centralized and Peer-to-Peer Gaming” IEEE/ACM Transactions on Volume 15,  Issue 1,  Feb. 2007 Page(s):1 - 13
Dugki Min, “A Load Balancing Algorithm For a Distributed Multimedia Game Server Architecture” IEEE International Conference on Volume 2, Issue 7-11 June 1999 Page(s):882 - 886.
Hori M., “Scalability Issues of Dynamic Space Management for Multiple-Server Networked Virtual Environments”, IEEE Pacific Rim Conference Volume 1,  26-28 Aug. 2001 Page(s):200 - 203
Kyung Seob Moon, “Maintaining consistency in distributed network games”, Networks, 2005. IEEE International Conference Volume 1,  16-18 Nov. 2005 Page(s):6.
Knutsson B., “Peer-to-peer Support for Massively Multiplayer Games”, IEEE Computer and Communication Societies Volume 1, March 2004 Page(s): 7-11.
Madjid Merabti, “Peer-to-Peer Architecture and Protocol for a Massively Multiplayer Online Game” GlobeCom Workshops 2004. IEEE, 29 Nov.-3 Dec. 2004 Page(s):519 – 528
Schiele G., “Requirements of Peer-to-Peer-based Massively Multiplayer Online Gaming” Cluster Computing and the Grid, 2007. CCGRID 2007. Seventh IEEE International Symposium on,14-17 May 2007 Page(s):773 - 782
T.A. Funkhouser, “RING: A client-server system for multiuser virtual environments” Proceedings of the 1995 Symposium, on Interactive 30 Graphics,pp85-92,April,l995
Tsun-Yu Hsiao, “Practical middleware for massively multiplayer online games”, Internet Computing, IEEE,Volume 9,  Issue 5,  Sept.-Oct. 2005 Page(s):45 - 47