基於范諾圖之同儕式網路虛擬環境狀態管理

Voronoi Diagram Based State Management for Peer-to-Peer Virtual Environments

張少榛(Shao-Chen Chang)

指導教授 ： 江振瑞

國立中央大學/資訊電機學院/資訊工程學系/碩士(2008年)

摘要

如同像大型多人線上遊戲 (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

參考文獻

[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.

Becker. Consistency management for peer-to-peer-based massively multiuser vir-

Massively Multiuser Virtual Environments, pages 14–18, March 2008.