基于局域信息的無標(biāo)度網(wǎng)絡(luò)路由策略研究.pdf

1、隨著互聯(lián)網(wǎng)的普及和計算機技術(shù)的發(fā)展，出現(xiàn)了各種大規(guī)模網(wǎng)絡(luò)形態(tài)如社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、電力網(wǎng)絡(luò)等，這些網(wǎng)絡(luò)形態(tài)有著很多的共性，學(xué)術(shù)界統(tǒng)稱“復(fù)雜網(wǎng)絡(luò)”，復(fù)雜網(wǎng)絡(luò)如今已經(jīng)成為一種很熱門的交叉學(xué)科。復(fù)雜網(wǎng)絡(luò)表現(xiàn)小世界效應(yīng)、無標(biāo)度性、聚類特性等。Internet網(wǎng)絡(luò)同樣符合這樣的統(tǒng)計特性，復(fù)雜網(wǎng)絡(luò)的發(fā)展有助于對Internet網(wǎng)絡(luò)的深入研究。Internet上表現(xiàn)無標(biāo)度特性、高聚類性質(zhì)，這些對Internet上的路由策略研究有著重要意義。

2、隨著當(dāng)今Internet網(wǎng)絡(luò)規(guī)模的膨脹，傳統(tǒng)的最短路徑路由算法已經(jīng)很難滿足需求，學(xué)術(shù)界和工業(yè)界正在尋求更好的可擴展的路由策略。針對這一困境，本文主要對基于局域信息無標(biāo)度網(wǎng)絡(luò)路由策略進(jìn)行了一系列研究工作。研究的方向主要有兩塊:緊湊路由策略和圖嵌入貪婪路由策略。具體研究工作如下:
　　 1.實證分析了2000年和2006年Internet AS圖這樣的無標(biāo)度網(wǎng)絡(luò)的網(wǎng)絡(luò)特性。網(wǎng)絡(luò)特性表明Internet AS呈現(xiàn)小世界特性，高的聚類系

3、數(shù)，度分布冪率特征。
　　 2.在TZ緊湊路由算法的基礎(chǔ)上重新構(gòu)建了地標(biāo)節(jié)點集合。提出了基于度和基于PageRank兩種地標(biāo)節(jié)點集合構(gòu)建機制，在2000年和2006年Internet AS圖上仿真表明改進(jìn)的路由算法均有較好的表現(xiàn)。具體表現(xiàn)如下:基于節(jié)點度和基于PageRank算法的緊湊路由算法相對于TZ算法，平均路由表大小都大大降低了，其中2000年Internet AS圖上平均路由表大小均降低了17％，2006年AS圖上平均路

4、由表大小均降低了21％，且隨著網(wǎng)絡(luò)規(guī)模的增加，差距越來越明顯。
　　 3.基于隨機游走理論和降維技術(shù)構(gòu)建圖嵌入的貪婪路由策略。通過隨機游走構(gòu)建節(jié)點的轉(zhuǎn)移矩陣和降維技術(shù)(PCA)得到節(jié)點的隱式空間坐標(biāo)，解決網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和空間坐標(biāo)的對應(yīng)關(guān)系。通過節(jié)點連接關(guān)系和空間坐標(biāo)，進(jìn)行貪婪路由。通過在一系列無標(biāo)度網(wǎng)絡(luò)如足球俱樂部網(wǎng)絡(luò)，BA無標(biāo)度網(wǎng)絡(luò)，P2P網(wǎng)絡(luò)，Internet AS網(wǎng)絡(luò)上進(jìn)行仿真實驗來測量路由性能。主要衡量了3個路由參數(shù):成功