本論文將提出一個以同儕運算概念為基礎的網路虛擬環境，透過分散式的處理以及同儕運算來達到提升NVE中參與者的目的。架構上以Voronoi-based Overlay Network(VON)與forwarding訊息為基礎，並使其能運用於建立異質性的可擴展式(scalable)網路虛擬環境。
因為VON direct-connection model存在傳輸時間過長的疑慮，此架構運用平行傳輸的概念，透過此一方式來改善硬體傳輸時間的消耗。並提供最佳化機制，使透過Area of Interest(AOI)大小的調整來控制傳輸量，確保AOI較小的node會能有較小的傳輸量，而AOI較大的node則需要較大的傳輸量，藉由此一機制達到傳輸量的有效控制。

This thesis proposed a peer-to-peer architecture to upscale the number of users in the NVE. It can be used to build a heterogeneous scalable NVE. This  architecture is based on Voronoi-based Overlay Network (VON) and uses forwarding method to transfer messages. 
The VON direct-connection model on transferring will cost much time, this architecture supports a parallel transmission, the cost of sending message is less than VON direct-connection model, and each node can adjust its AOI-radius to control transmission size by using optimize mechanism.

目錄
第一章 緒論  	1 
1.1 研究動機  	1
1.2 研究目的  	1
1.2.1建構網路虛擬環境的元素  	2
1.2.2 架構重心  	2
1.3 論文架構  	3
第二章 相關研究  	5
2.1 Client-server Systems  	5
2.1.1 RING  	5
2.1.2 Massively Multiplayer Online Games(MMOG)  	5
2.2 Peer-to-Peer Systems  	6
2.2.1 Solipsis  	6
2.2.2 SimMud  	7
2.2.3 Neighbor-list exchange  	8
2.2.4 Voronoi-based Overlay Network  	9
第三章 系統架構  	12
3.1 Voronoi Diagram  	12
3.2 Direction-Connection Model問題探討  	13
3.3系統設計  	15
3.3.1 Join Procedure  	16
3.3.2 Move Procedure  	19
3.3.2.1 Maintain Enclosing Neighbors  	20
3.3.2.2 Maintain AOI Neighbors  	21
3.3.3 Leave Procedure  	28
3.3.4 Optimization  	30
3.4 架構分析  	33
第四章 模擬架構  	36
4.1模擬環境設定  	36
4.1.1 軟體架構  	36
4.1.2 硬體架構  	36
4.2 模擬數據定義  	36
4.2.1 Consistency  	37
4.2.2 Drift Distance  	37
4.2.3 Average Neighbor Size  	37
4.3 模擬數據  	38
4.3.1基本數據  	38
4.3.1.1 Scalability  	38
4.3.1.2 Consistency  	44
4.3.2 特徵數據  	49
第五章 結論  	52
5.1可擴展式網路虛擬環境  	52
5.1.1相異性  	52
5.1.2特性  	53
5.2架構應用  	54
5.3未來發展  	54
5.3.1 Voronoi-based Overlay Network的問題  	55
5.3.2 Forwarding Model的未來發展  	55
5.3.3 Voronoi-based Overlay Network的未來發展  	56
相關文獻  	57
英文論文  	59
 
圖目錄
圖1.1  NVE示意圖	3
圖2.1  Server-cluster Architecture	5
圖2.2  Design of Solipsis	6
圖2.3  Potential Discovery Problem in Solipsis	7
圖2.4  Fixed-size Regions in SimMud	7
圖2.5  Neighbor-list Exchange示意圖	8
圖2.6  Direct-connection Model 示意圖	9
圖2.7  被動傳輸示意圖	10
圖2.8  Dynamic AOI 機制示意圖	10
圖3.1  Voronoi Diagram 機制示意圖	12
圖3.2  轉遞機制示意圖	15
圖3.3  “JOIN” 訊息傳遞示意圖	17
圖3.4  Enclosing Neighbor初始化	19
圖3.5  Enclosing Neighbor changed	20
圖3.6  Forwarding Message	21
圖3.7  Subscriber Discussion	22
圖3.8  Forwarding Path Building	23
圖3.9  Forwarding Path	24
圖3.10  Redraw Voronoi Diagram after Node Leave (1)	29
圖3.11  Redraw Voronoi Diagram after Node Leave (2)	29
圖3.12  Forwarding 最佳化	31
圖3.13  Forwarding Path 最佳化	32
圖3.14  AN Discovery Delay in Forwarding Model	34
圖4.1  Transmission Size in Forwarding Model	39
圖4.2  AN and CN in Forwarding Model	39
圖4.3  Special Case in Voronoi Diagram	40
圖4.4  Transmission Size Comparison of VONFO and Client-Server Architecture	40
圖4.5  Transmission Size Comparison of VONFO and VONDC	41
圖4.6  AN, CN Comparison of VONFO and VONDC	42
圖4.7  Transmission Size Comparison with Connection Limit	43
圖4.8  AN, CN Comparison with Connection Limit	43
圖4.9  Consistency in Forwarding Model	44
圖4.10  Drift Distance in Forwarding Model	45
圖4.11  Consistency Comparison of VONFO and VONDC	46
圖4.12  Drift Distance Comparison of VONFO and VONDC	46
圖4.13  Consistency Comparison with Connection Limit	47
圖4.14  Drift Distance Comparison with Connection Limit	48
圖4.15  Relation of AOI-radius and Transmission Size	49
圖4.16  Characteristic of VONFO and VONDC	50
圖5.1  Special Case in Voronoi Diagram	55

 
表目錄
表3.1  VONFO資料結構	16
表3.2  VONFO協定	16
表3.3  Algorithm of Join	18
表3.4  Algorithm of Movement	26
表3.5  Algorithm of Maintain EN	26
表3.6  Algorithm of Maintain AN (subscribe)	27
表3.7  Algorithm of Maintain AN(publish)	27
表3.8  Algorithm of Maintain AN Optimized	32
表5.1  VONFO與VONDC的比較(1)	52
表5.2  VONFO與VONDC的比較(2)	53

[Aurenhammer 91]
F. Aurenhammer, “Voronoi diagram – a survey of a fundamental geometric data structure, “ ACM Computing Surveys(CSUR), vol. 23, pp. 345-405, 1991.
[Diot 99]
C. Diot and L. Gautier, “A distributed architecture for multiplayer interactive applications on the Internet,” IEEE Network, vol. 13, no. 4, pp. 6-15, 1999. 
[Funkhouser 95]
T. A. Funkhouser, “RING: A client-server system for multi-user virtual environments,” in Proc. 1995 Symp. Interactive 3D Graphics., pp. 85-92, April  1995.
[Guibas 85]
L. Guibas and J. Stolfi, “Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams,” ACM Trans. Graphics, vol. 4, pp. 74-123, April 1985.
[Hu 04]
S. Y. Hu and G. M. Liao, “Scalable peer-to-peer networked virtual environment,” in Proc. ACM SIGCOMM 2004 workshops on NetGames '04,  pp. 129-133, Aug. 2004. 
[Hu 05]
S. Y. Hu, “Scalable peer-to-peer networked virtual environment,” Master’s thesis, Tamkang Univ., Taiwan, 2005. 
[Kawahara 04]
Y. Kawahara, T. Aoyama, and H. Morikawa, “A peer-to-peer message exchange scheme for large-scale networked virtual environments,” Telecommunication Systems, vol. 25, pp. 353 370,2004
[Keller 02]
J. Kelly and G. Simon, “Towards a peer-to-peer shared virtual reality,” in Proc. 22nd Int. Conf. Distributed Computing Systems(Workshops), Vienna, Austria, pp. 695-700, Jul. 2002. 
[Keller 03]
J. Kelly and G. Simon, “Solipsis: A massively multi-participant virtual world,” in Proc. Int. Conf. Parallel and Distributed Techniques and Applications (PDPTA 03), Las Vegas, pp. 262-268, Nov. 2003
[Knutsson 04]
B. Knutsson, H Lu, W. Xu, and B. Hopkins, “Peer-to-peer support for massively multiplayer games,” in Proc. IEEE INFOCOM, pp. 96-107, Mar. 2004.
[Okabe 00]
Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, “Spatial tessellations : concepts and applications of Voronoi diagrams,” Chichester, Wiley, 2000. 2nd ed. 
[ VAST 05 ]
VAST Project homepage. Available at: 
http://vast.sourceforge.net/ , 2006