Voronoi-based Overlay Network (簡稱VON)是一種完全分散、以同儕運算 (Peer-to-Peer Computing) 及Voronoi diagram為基礎之虛擬網路，本篇論文利用此VON的網路環境，建構點對點的網路搜尋的機制。在此網路架構下，資料的搜尋不需要倚靠一台主機集中管理，只需要透過相鄰鄰居節點(Enclosing Neighbor, 簡稱EN)做資料訊息的傳遞，讓使用者能在虛擬世界中快速找到資訊。

由於在VON的架構下，經由EN做搜尋動作，會有redundancy的問題產生，造成網路頻寬上的浪費，所以本篇論文則是提出一個樹狀群組廣播的搜尋機制來做改善。透過建立APSTT (All-Path Search Tree Table)，和TPT (Transfer Path Table)，使VON網路中的每個節點透過查閱TPT得知下一個訊息發送點，如此能提昇搜尋的效能，避免網路頻寬的浪費。

This paper proposed a tree-like search mechanism that based on VON to solve the redundancy problem. Voronoi-based Overlay Network (VON) is a fully distributed peer-to-peer architecture and based on the mathematical construct Voronoi diagram. In this mechanism, one server being center controller will never be needed, and users can search data more effectively by passing query message from enclosing neighbor.

By constructing APSTT (All-Path Search Table) and TPT (Transfer Path Table), every node in VON can check TPT to pass the query message. In this way, we can improve performance and reduce the loading of network bandwidth.

目錄
第一章 序論	1
1.1 研究動機	1
1.2 研究內容	1
第二章 相關研究	3
2.1 Voronoi-based Overlap Network	3
2.1.1 Voronoi Diagram	3
2.1.2 Terminology	4
2.1.3 JOIN Procedure	5
2.1.4 MOVE Procedure	6
2.1.5 LEAVE Procedure	7
2.2 在分散式虛擬世界中的六向同步搜尋機制	7
2.2.1 搜尋層次定義	8
2.2.2 外部搜尋路徑	9
第三章 在Voronoi-based Overlay Network虛擬環境中樹狀群組廣播的搜尋機制 	12
3.1 建立搜尋路徑原理	13
3.1.1 搜尋層次定義	13
3.1.2 名詞定義	14
3.2 All-Path Search Tree Table	15
3.2.1 APSTT的概念	15
3.2.2 APSTT的資料結構	17
3.2.3 APSTT的建構	17
3.2.4 APSTT -找出原始子節點群組	19
3.3 Transfer Path Table	21
3.3.1 TPT的資料結構	22
3.3.2 由APSTT產生TPT	24
3.3.2.1 比較原始子節點	24
3.3.2.2處理重複子節點	26
3.3.2.3交換APSTT訊息	30
3.4 建立搜尋路徑流程	31
第四章 實作結果與討論	33
4.1 實作結果	33
4.2 實作討論	44
第五章 結論與未來研究方向	48
5.1 結論	48
5.2 未來研究方向	48
參考文獻	50
英文稿	52

圖目錄
圖2-1 Voronoi Diagram (1)	                  3
圖2-2 Voronoi Diagram (2)	                  4
圖2-3 JOIN procedure	                  5
圖2-4 MOVE procedure 	                  6
圖2-5 LEAVE procedure	                  7
圖2-6 虛擬世界架構                     	8
圖2-7 Hierarchical Tree	                  9
圖3-1 節點在VON架構中的分佈	                  12
圖3-2 Hierarchical Tree	                  13
圖3-3 節點與相鄰鄰居節點間的角色對應關係     16
圖3-4 圖解公式運算	                           20
圖3-5 node1與EN在VON上的分佈	         22
圖3-6 node1的四種搜尋路徑結構	         23
圖3-7 VON架構圖	                           24
圖3-8 訊息交換封包格式	                  30
圖4-1 VON架構圖(範例一)	                  34
圖4-2 範例一：Query傳遞Level 1-> Level 2	35
圖4-3 範例一：node 2的APSTT	                  36
圖4-4 範例一：node 2查閱TPT	                  36
圖4-5 範例一：Query傳遞Level 2-> Level 3	37
圖4-6 範例一：node 12的APSTT	         38
圖4-7 範例一：node 12查閱TPT	         38
圖4-8 範例一：Query傳遞Level 3-> Level 4	39
圖4-9 VON架構圖(範例二)	                  40
圖4-10 範例二：Query傳遞Level 1-> Level 2	41
圖4-11 範例二：node 2查閱TPT	         42
圖4-12 範例二：node 3查閱TPT	         42
圖4-13 範例二：node 4查閱TPT	         43
圖4-14 範例二：Query傳遞Level 2-> Level 3 (1)	43
圖4-15 範例二：Query傳遞Level 2-> Level 3 (2)	47

表目錄
表3-1 node 1之APSTT	21
表3-2 node 1之APSTT	21
表3-3 node1之TPT	         23
表3-4 node1之APSTT	         25
表3-5 node6之APSTT   	25

[1]	I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek and H. Balakrishnan, "Chord: a scalable peer-to-peer lookup protocol for Internet applications, " IEEE/ACM Trans. Networking, vol. 11, pp. 17-32, Feb. 2003.

[2]	Shun-Yun Hu, "Scalable Peer-to-Peer Networked Virtual Envir- onment, " Department of Computer Science and Information Engineering Tamkang University, Jan. 2005.

[3]	Jiung-Yao Huang, Yi-chang Du, Chien-Min Wang, "Design of the server cluster to support avatar migration, " Proceedings of 2003 IEEE Virtual Reality, pp. 7-14, March 22-26, 2003.

[4]	S. Singhal and M. Zyda, Networked Virtual Environments: Design and Implementation, ACM Press, New York, 1999.

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

[6]	F. Aurenhammer, "Voronoi diagrams—a survey of a fundamental geometric data structure, " ACM Computing Surveys (CSUR), vol. 23, pp. 345-405, 1991.

[7]	M. R. Macedonia, M. J. Zyda, D. P. Brutzman, and P. T. Barham, "Exploiting Reality with Multicast Groups: A Network Architecture for Large-scale Virtual Environments, " Proc. 1995, IEEE Virtual Reality Annual International Symposium (VRAIS95), pp. 11-15, March 1995.

[8]	Heng-Yi Chiou, "A Searching Mechanism on Distributed Virtual World: Six-Direction Simultaneous Search, " Department of Computer Science and Information Engineering Tamkang University, June 2002.

[9]	T.Imielinski and B.R.Badrinath, "Querying in highly distributed mobile environments, " in Proceedings of the 18th VLDB, pp. 41-52, August 1992.

[10]	S.DasBit and S.Mitra, "Query processing in a cellular network-a database approach, " Proc. Vehicular Technology Conference, pp. 2560-2564, May 2001.

[11]	Dolev, S., Pradhan, D. K., and Welch, J. L., "Modified Tree Structure for Location Management in Mobile Environments, " Proc. 14th Annual Joint Conference of IEEE Computer and Communication Societies (INFOCOM), pp. 530-537, April 1995.