基于局域信息的無標度網絡路由策略研究.pdf

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

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

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

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