- 學位論文
叢集演算法在疊代網路之運用
The Application of Clustering Algorithm in Overlay Network
摘要
結構性的點對點疊代網路(P2P overlay network)，提供一個可伸縮性且分散式多元應用的新平臺，諸如檔案的分享（file sharing）和多媒體的串流（multi-media streaming）。然而疊代網路是邏輯實體網路的呈現，在資料搜尋與索引未能考慮到各個節點的實體位置，因此我們利用網路鄰近位置的資訊來對節點分群，以改善整個搜尋效能和路由繞送的效能。本論文探討四個叢集演算法之效能，其中以K-mean為基礎的重疊網路之切割網路演算法分別為K-mean、K-mean with weight 和K-mean with Exchange；另一個以Matching為主的演算法CMA（Cluster Matching Algorithm）。這些演算法使用GBT（Gravity Based Topology），以重心（Gravity）和節點能力值（Power Index）來進行叢集。此拓墣結構之穩定度對整個應用的效能有巨大的影響並以此達到一個穩定且節點平均分佈的切割網路。模擬結果顯示，CMA演算法與K-mean為基礎之相關演算法比較以叢集控制節點為中心的叢集演算法表現更為優越。
並列摘要
Structural P2P overlay network offers a new application platform for elasticity and distributed applications,such as file sharing and multimedia streaming. An overlay network is a logical network, whose topology changes frequently when peer nodes join and leave dynamically and thus make it hard to maintain the topology. Furthermore, if we don’t consider the physical position of each node on data search and index, the searching performance will become poor. Thus in this thesis, we use the network proximity clustering to improve the search and routing effect. This thesis compares the performance of 4 algorithms，among K-mean、K-mean with weight and K-mean with Exchange based on K-mean algorithm；the other is CMA（Cluster Matching Algorithm）based on Matching Algorithm. We use the gravity and computing power to cluster peer nodes so that suitable and compact clusters can be achieved and average in this topology. According to the result of simulation, CMA and K-mean related algorithms is superior to the algorithms based on cluster headers.