一種基于結(jié)點聚類的網(wǎng)絡定位算法.pdf

1、大規(guī)模的網(wǎng)絡服務應用系統(tǒng)已經(jīng)在全世界的范圍內(nèi)得到運行和使用，例如：P2P文件共享系統(tǒng)、覆蓋網(wǎng)絡多播系統(tǒng)以及內(nèi)容分發(fā)服務系統(tǒng)。這些大規(guī)模的網(wǎng)絡應用系統(tǒng)能夠從一些性能較好的路由選擇算法以及鄰居結(jié)點選擇算法中獲益。這是因為延遲和帶寬等網(wǎng)絡性能參數(shù)與大規(guī)模網(wǎng)絡應用密切相關(guān)，測量這些網(wǎng)絡性能參數(shù)值將對這些算法性能的提高有幫助。然而，在真實的網(wǎng)絡環(huán)境下，由于大規(guī)模網(wǎng)絡應用存在數(shù)量巨大的端到端連接，如果對每一個連接都進行測量，則會帶來巨大的物理開銷和

2、時間消耗。為了解決這個問題，可以通過一定的算法來預測端到端的網(wǎng)絡距離，而不用在真實的網(wǎng)絡環(huán)境里進行測量，這樣可以極大的減小網(wǎng)絡開銷。當前已經(jīng)出現(xiàn)了一些網(wǎng)絡定位算法來預測網(wǎng)絡結(jié)點間的距離，在這些算法當中已經(jīng)證明了網(wǎng)絡坐標是簡單并且實用的。網(wǎng)絡坐標能夠表示出網(wǎng)絡中某個主機的位置，并且從某種意義上來說，還能夠表示網(wǎng)絡的拓撲結(jié)構(gòu)。 本文提出了一種基于結(jié)點聚類的網(wǎng)絡定位算法——Dumpling算法。該算法包括了兩個核心機制：結(jié)點聚類機制和

3、整體坐標移動機制。Dumpling算法致力于在更短的時間內(nèi)對虛擬坐標空間中的誤差進行收斂；在更少的顯式測量內(nèi)收斂更多的系統(tǒng)誤差；盡量避免虛擬坐標系統(tǒng)的波動現(xiàn)象給帶來的定位精度的影響。除了從理論上分析了Dumpling的優(yōu)勢外，本論文還經(jīng)過仿真實驗表明，Dumpling可以較好的達到上述三個目標，并且在最后的Dumpling整體性能測試中，表明Dumpling在真實的網(wǎng)絡拓撲下，也能達到一定的效果。Dumpling是一個分布式的虛擬網(wǎng)絡坐