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


系統識別號 U0002-1207200617460000
中文論文名稱 在Voronoi-based Overlay Network虛擬環境中樹狀群組廣播的搜尋機制
英文論文名稱 A Tree-Like Multicast Search Mechanism for a Voronoi-based Overlay Network Virtual Environment
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士在職專班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 94
學期 2
出版年 95
研究生中文姓名 陳晶萍
研究生英文姓名 Jing-Ping Chen
學號 792190083
學位類別 碩士
語文別 中文
口試日期 2006-06-08
論文頁數 58頁
口試委員 指導教授-陳瑞發
委員-陳瑞發
委員-王英宏
委員-林偉川
中文關鍵字 網路虛擬環境  同儕運算  Voronoi  搜尋機制 
英文關鍵字 Networked Virtual Environment  Peer-to-Peer  Voronoi  Search Mechanism 
學科別分類 學科別應用科學資訊工程
中文摘要 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.
論文使用權限
  • 不同意紙本論文無償授權給館內讀者為學術之目的重製使用。
  • 不同意授權瀏覽/列印電子全文服務。


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