淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1507200901525000
中文論文名稱 大型分散式虛擬實境的負載平衡演算法
英文論文名稱 Load Balance Algorithm for Large Scale Virtual Reality Environment
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 97
學期 2
出版年 98
研究生中文姓名 林永祥
研究生英文姓名 Gary Lin
學號 696410108
學位類別 碩士
語文別 中文
第二語文別 英文
口試日期 2009-06-12
論文頁數 58頁
口試委員 指導教授-陳瑞發
委員-陳瑞發
委員-王英宏
委員-簡志宇
中文關鍵字 虛擬實境  分散運算  負載平衡  線上遊戲  遊戲伺服器  空間切割 
英文關鍵字 Virtual Reality  Distributed Computing  Load Balance  Online Game  Game Server  Space Cutting 
學科別分類 學科別應用科學資訊工程
中文摘要 大型虛擬實境系統,能應用在許多不同的領域,例如軍事演練,交通模擬,最常見的應用就是目前流行的多人角色扮演線上遊戲(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
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2009-07-23公開。
  • 同意授權瀏覽/列印電子全文服務,於2009-07-23起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信