博碩士論文 955202049 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:29 、訪客IP:35.175.121.230
姓名 張少榛(Shao-Chen Chang)  查詢紙本館藏   畢業系所 資訊工程學系
論文名稱 基於范諾圖之同儕式網路虛擬環境狀態管理
(Voronoi Diagram Based State Management for Peer-to-Peer Virtual Environments)
相關論文
★ 以IEEE 802.11為基礎行動隨意無線網路之混合式省電通訊協定★ 以范諾圖為基礎的對等式網路虛擬環境相鄰節點一致性研究
★ 行動隨意網路可調適及可延展之位置服務協定★ 同儕式網路虛擬環境高效率互動範圍群播
★ 巨量多人線上遊戲之同儕網路互動範圍語音交談★ 利用多變量分析 之多人線上遊戲信任使用者選擇
★ 無位置資訊無線感測網路之覆蓋及連通維持★ 同儕網路虛擬環境3D串流同儕選擇策略
★ 一個使用802.11與RFID技術的無所不在導覽系統U-Guide之設計與實作★ 同儕式三維資料串流
★ IM Finder: 透過即時通訊網路線上使用者找尋解答★ 無位置資訊無線感測網路自走車有向天線導航與協調演算法
★ 多匯點無線感測網路省能及流量分散事件輪廓追蹤★ 頻寬感知同儕式3D串流
★ 無線感測網路旋轉指向天線定位法★ 網路虛擬環境多重伺服器動態負載平衡
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 如同像大型多人線上遊戲 (Massively Multi-player Online Games, MMOGs) 這樣的網路虛擬環境 (Networked Virtual Environments, NVEs) 隨著時間逐漸變得越來越受歡迎。現在的系統大多採用以伺服器為主的主從式架構 (Client-server architectures),但此架構也因為同一伺服器所能同時服務人數有限,進而限制了可能的同時最大使用者。另一方面,同儕式 (Peer-to-peer) 網路逐漸被證明它可被用來解決許多網路應用的可擴充性 (Scalability) 問題。透過分享與使用網路節點 (Peer) 的資源,同儕式網路將可提供資源解決伺服器資源不足的問題。
我們提出了以同儕式網路為基礎之網路虛擬環境狀態管理系統,稱之為范諾圖狀態管理 (Voronoi State Management, VSM),主要用以解決以同儕網路為基礎的虛擬世界中的物件管理問題。本系統使用范諾圖 (Voronoi Diagram) 來分割環境,並將狀態管理成本分散至化身物件處於鄰近的節點上。當系統負載正常時,所有的使用者可透過直接連線的方式交換狀態更新資訊,但在需要時(系統負載過重,或是使用者電腦資源不足以負擔該區的管理所需時),將會尋找並喚起能力較強之使用者電腦來擔任集中管理者(Aggregator,簡稱集管者)。集管者將會同時管理多個小區域來減輕其他使用者電腦之負載過重情形;同時也會動態地調整其管理區域的大小來平衡系統負載。透過模擬結果顯示,本系統可支援一個網路虛擬環境所需的一致性 (Consistency) 、可擴充性和負載平衡 (Load balancing) 等特性。
摘要(英) Networked Virtual Environments (NVEs), such as Massively Multi-player Online Games (MMOGs), have become more and more popular nowadays. Current systems use server-based architectures which possess bottlenecks for the number of concurrent online users on a single server. Peer-to-Peer (P2P) systems have been shown as a feasible solution to scalability in many network applications. Through the resource sharing of peers, P2P systems can be seen as an additional source of resources for improving the lack of server resources.
We propose a state management strategy for supporting P2P-based virtual environments called Voronoi State Management (VSM). By using Voronoi diagram to divide the environment, VSM can distribute the management loading of the system onto selected nodes. Every peer in VSM represents as one site on the Voronoi diagram, and manages the nearest Voronoi cell. When load increases due to a higher density of objects/peers, VSM promotes a capable node called aggregator to join the overloaded area and take over the loads. An aggregator also dynamically adjusts its covering area according to system load. Simulation results show that VSM can achieve the NVE property of consistency, scalability, and load balancing.
關鍵字(中) ★ 狀態管理
★ 同儕式網路
★ 網路虛擬環境
★ 范諾圖
關鍵字(英) ★ Peer-to-Peer
★ NVE
★ Voronoi diagram
★ State Management
論文目次 Chinese abstract i
Abstract ii
Table of Contents iii
List of Figures v
1 Introduction 1
2 Related Work 4
2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.1 Requirements of P2P NVE . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.2 Network Model and Consistency Model . . . . . . . . . . . . . . . . 6
2.1.3 Server-cluster State Management Schemes . . . . . . . . . . . . . . 8
2.2 P2P-based Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Discovery Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Peer-to-Peer State Management . . . . . . . . . . . . . . . . . . . . 10
3 Problem Formulation 15
4 Proposed Scheme 17
4.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.2 Detailed Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2.1 Consistency Control . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2.2 Load Balancing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.3 Additional Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5 Evaluation 23
5.1 Simulation Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.2 Simulation Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.3 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6 Conclusion 30
References 31
參考文獻 [1] World of warcraft. http://www.worldofwarcraft.com/.
[2] Second life. http://www.secondlife.com/.
[3] S.Y. Hu, J.F. Chen, and T.H. Chen. VON: a scalable peer-to-peer network for virtual
environments. Network, IEEE, 20(4):22–31, 2006.
[4] Gregor Schiele, Richard Suselbeck, Arno Wacker, Tonio Triebel, and Christian
Becker. Consistency management for peer-to-peer-based massively multiuser vir-
tual environments. In MMVE ’08: Proceedings of 1st International Workshop on
Massively Multiuser Virtual Environments, pages 14–18, March 2008.
[5] Richard M. Fujimoto. Parallel discrete event simulation. Commun. ACM, 33(10):30–
53, 1990.
[6] Eric Cronin, Anthony R. Kurc, Burton Filstrup, and Sugih Jamin. An efficient
synchronization mechanism for mirrored game architectures. Multimedia Tools Appl.,
23(1):7–30, 2004.
[7] Stefano Ferretti and Marco Roccetti. Fast delivery of game events with an opti-
mistic synchronization mechanism in massive multiplayer online games. In ACE
’05: Proceedings of the 2005 ACM SIGCHI International Conference on Advances in
computer entertainment technology, pages 405–412, 2005.
[8] P. Morillo, S. Rueda, J.M. Orduna, and J. Duato. A latency-aware partitioning
method for distributed virtual environment systems. IEEE Transactions on Parallel
and Distributed Systems, 18(9):1215–1226, September 2007.
[9] D.T. Ahmed, S. Shirmohammadi, J.C. de Oliveira, and J. Bonney. Supporting
large-scale networked virtual environments. Virtual Environments, Human-Computer
Interfaces and Measurement Systems, 2007. VECIMS 2007. IEEE Symposium on,
pages 150–154, 25-27 June 2007.
[10] David Kushner. Engineering everquest. IEEE Spectrum, 2005.
[11] Bjorn Knutsson et al. Peer-to-peer support for massively multiplayer games. In
INFOCOM 2004: Proceeding of 23th AnnualJoint Conference of the IEEE Computer
and Communications Societies, pages 96–107, March 2004.
[12] Joaquin Keller and Gwendal Simon. Solipsis: A massively multi-participant virtual
world. In PDPTA ’03: Proceedings of International Conference on Parallel and
Distribued Techniques and Applications, volume 1, pages 262–268, 2003.
[13] D.A. Tran, K.A. Hua, and T. Do. Zigzag: an efficient peer-to-peer scheme for media
streaming. In INFOCOM 2003:Proceedings of Twenty-Second Annual Joint Confer-
ence of the IEEE Computer and Communications Societies, volume 2, pages 1283–
1292 vol.2, April 2003.
[14] Shun-Yun Hu, Ting-Hao Huang, Shao-Chen Chang, Wei-Lun Sung, Jehn-Ruey Jiang,
and Bing-Yu Chen. FLoD: A Framework for Peer-to-Peer 3D Streaming. In to appear
in INFOCOM 2008: The 27th Conference on Computer Communications, April 2008.
[15] Skype. http://www.skype.com/.
[16] Bittorrent. http://www.bittorrent.com/, 2001-2005.
[17] J. Keller and G. Simon. Toward a peer-to-peer shared virtual reality. In ICDCSW
’02: Proceedings of 22th International Conference on Distributed Computing Systems
Workshops, pages 695–700, 2002.
[18] Ashwin Bharambe, Jeffrey Pang, and Srinivasan Seshan. Colyseus: a distributed
architecture for online multiplayer games. In NSDI’06: Proceedings of the 3rd con-
ference on 3rd Symposium on Networked Systems Design & Implementation, pages
12–12, 2006.
[19] Y. Kawahara, T. Aoyama, and H. Morikawa. A Peer-to-Peer Message Exchange
Scheme for Large-Scale Networked Virtual Environments. Telecommunication Sys-
tems, 25(3):353–370, 2004.
[20] A.P. Yu and S.T. Vuong. MOPAR: a mobile peer-to-peer overlay architecture for
interest management of massively multiplayer online games. In NOSSDAV ’05: Pro-
ceedings of the international workshop on Network and operating systems support for
digital audio and video, pages 99–104, 2005.
[21] Sunghwan Ihm Tcaesvk Gim Jinwon Lee, Hyonik Lee and Junehwa Song. APOLO:
Ad-hoc Peer-to-Peer Overlay Network for Massively Multi-player Online Games.
Technical report, Korea Advanced Institute of Science and Technology (KAIST),
2006.
[22] P. Morillo, W. Moncho, J.M. Orduna, and J. Duato. Providing Full Awareness to
Distributed Virtual Environments Based on Peer-To-Peer Architectures. Springer
LNCS, 4035:336–347, June 2006.
[23] Gregor Schiele, Richard Suselbeck, ArnoWacker, Jorg Hahner, Christian Becker, and
Torben Weis. Requirements of peer-to-peer-based massively multiplayer online gam-
ing. CCGRID ’07: Seventh IEEE International Symposium on Cluster Computing
and the Grid, pages 773–782, May 2007.
[24] Jui-Fa Chen, Wei-Chuan Lin, Tsu-Han Chen, and Shun-Yun Hu. A forwarding model
for voronoi-based overlay network. 2007 International Conference on Parallel and
Distributed Systems, 2:1–7, Dec. 2007.
[25] Luther Chan, James Yong, Jiaqiang Bai, Ben Leong, and Raymond Tan. Hydra: a
massively-multiplayer peer-to-peer architecture for the game developer. In NetGames
’07: Proceedings of the 6th ACM SIGCOMM workshop on Network and system sup-
port for games, pages 37–42, 2007.
[26] D. Frey, J. Royan, R. Piegay, A.-M. Kermarrec, E. Anceaume, and F. Le Fessant.
Solipsis: A decentralized architecture for virtual environments. In MMVE ’08: 1st
International Workshop on Massively Multiuser Virtual Environments, pages 29–33,
March 2008.
[27] Franz Aurenhammer. Voronoi diagrams - a survey of a fundamental geometric data
structure. ACM Computing Surveys (CSUR), 23(3):345–405, 1991.
[28] E. Buyukkaya and M. Abdallah. Data management in voronoi-based p2p gaming.
In Consumer Communications and Networking Conference, 2008. CCNC 2008. 5th
IEEE, pages 1050–1053, 2008.
[29] S. Singhal and M. Zyda. Networked Virtual Environments. ACM Press, 1999.
[30] Paul Bettner and Mark Terrano. 1500 archers on a 28.8: Network programming in
Age of Empires and beyond. Proc. GDC, 2001.
[31] Claudio E. Palazzi, Stefano Ferretti, Stefano Cacciaguerra, and Marco Roccetti.
Interactivity-loss avoidance in event delivery synchronization for mirrored game ar-
chitectures. IEEE Transactions on Multimedia, 8(4):874–879, August 2006.
[32] Marios Assiotis and Velin Tzanov. A distributed architecture for mmorpg. In
NetGames ’06: Proceedings of 5th ACM SIGCOMM workshop on Network and sys-
tem support for games, page 4, 2006.
[33] Jehn-Ruey Jiang, Jiun-Shiang Chiou, and Shun-Yun Hu. Enhancing neighborship
consistency for peer-to-peer distributed virtual environments. In ICDCSW ’07: Pro-
ceedings of 27th International Conference on Distributed Computing Systems Work-
shops, pages 71–71, June 2007.
[34] Jehn-Ruey Jiang, Yu-Li Huang, and Shun-Yun Hu. Scalable AOI-Cast for Peer-to-
Peer Networked Virtual Environments. In CDS ’08: Proceedings of 28th International
Conference on Distributed Computing Systems Workshops (ICDCSW) Cooperative
Distributed Systems, Jun. 2008.
[35] Wikipedia: Voronoi diagram. http://en.wikipedia.org/wiki/Voronoi diagram.
[36] Chi-Chang Chen and Cheng-Jong Lee. A dynamic load balancing model for the
multi-server online game systems. In HPC Asia, Poster, 2004.
[37] A. Rowstron and P. Druschel. Pastry: Scalable, distributed object location and
routing for large-scale peer-to-peer systems. IFIP/ACM International Conference
on Distributed Systems Platforms (Middleware), 11:329–350, 2001.
[38] M. Castro, M.B. Jones, A.-M. Kermarrec, A. Rowstron, M. Theimer, H. Wang, and
A. Wolman. An evaluation of scalable application-level multicast built using peer-to-
peer overlays. In INFOCOM 2003. Twenty-Second Annual Joint Conference of the
IEEE Computer and Communications Societies. IEEE, volume 2, pages 1510–1520
vol.2, 2003.
[39] Ashwin R. Bharambe, Mukesh Agrawal, and Srinivasan Seshan. Mercury: supporting
scalable multi-attribute range queries. In SIGCOMM ’04: Proceedings of the 2004
conference on Applications, technologies, architectures, and protocols for computer
communications, pages 353–366, 2004.
[40] Vast project. http://vast.sourceforge.net/.
指導教授 江振瑞(Jehn-Ruey Jiang) 審核日期 2008-7-19
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明