基于相似度傳播聚類算法的地標路由算法研究.pdf

1、互聯(lián)網(wǎng)規(guī)模的急劇增加給傳統(tǒng)路由算法帶來了巨大的挑戰(zhàn),學者們在努力的設(shè)計能夠大大降低路由表長度,同時又具有較小伸長系數(shù)的路由方法。本文在全面分析比較各種路由算法特別是各種緊湊路由算法的基礎(chǔ)上,提出了一種以網(wǎng)絡(luò)社團結(jié)構(gòu)劃分為核心思想,利用AP(Affinity Propagation)聚類算法對互聯(lián)網(wǎng)自治系統(tǒng)層拓撲結(jié)構(gòu)進行社團結(jié)構(gòu)劃分,從而現(xiàn)實緊湊路由的算法,可稱為APCR(Affinity Propagation Compact Rout

2、ing)算法。
　　 本文主要做了以下工作:
　　 通過全面總結(jié)各種路由算法特別是各種緊湊路由算法的性能和優(yōu)缺點,發(fā)現(xiàn)地標路由具有廣闊的前景,而地標路由的核心問題就是將網(wǎng)絡(luò)進行恰當?shù)纳鐖F結(jié)構(gòu)劃分,并且找到每個社團內(nèi)部的地標(landmark)。通過對各種社團劃分算法尤其是AP算法的分析總結(jié),發(fā)現(xiàn)利用AP算法不僅能將網(wǎng)絡(luò)進行劃分,而且能找到每個類中的基點,即地標。因此本文把AP算法和地標路由結(jié)合起來,提出了APCR算法。<

3、br>　　 在APCR算法中,對網(wǎng)絡(luò)中任一節(jié)點,考慮它的近鄰,并給出該節(jié)點到它的這些近鄰的相似度度量。采用兩點間的負距離度量相似度,從而得到網(wǎng)絡(luò)的相似度矩陣?；谙嗨贫染仃?利用AP算法對網(wǎng)絡(luò)進行劃分,得到每個聚類簇的基點。在聚類后的網(wǎng)絡(luò)上進行地標路由。
　　 通過對互聯(lián)網(wǎng)自治系統(tǒng)層網(wǎng)絡(luò)拓撲數(shù)據(jù)進行大量實驗,確定了APCR算法中偏好參數(shù)的取值范圍,并分析了該參數(shù)與伸長系數(shù)和路由表長度的關(guān)系。實驗結(jié)果表明該算法可以同時獲得很小的