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

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

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

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