網絡拓撲結構層析成像的改進算法研究.pdf

1、網絡拓撲結構識別對于網絡的監(jiān)測、管理、控制以及內部鏈路參數(shù)的估計都有重要意義。通常有兩種方法進行網絡拓撲識別：利用內部節(jié)點協(xié)作的傳統(tǒng)方法和網絡層析成像方法。網絡層析成像方法由于不需要內部節(jié)點的協(xié)作，引起了學術界和工業(yè)界的高度重視。
　　現(xiàn)今的網絡拓撲結構層析成像識別算法有很多種，基于最大似然的拓撲估計算法和鄰居節(jié)點加入樹拓撲估計算法是其中的兩種算法。這兩種算法都有很高的拓撲估計準確率，但是，前者在對大規(guī)模網絡拓撲進行識別時會產生很

2、大的計算量，后者對門限值的選取有很大的依賴性，好的門限值不僅能夠減少探測包的數(shù)量而且能夠提高拓撲估計準確率。針對上述兩種算法存在的問題，本文提出了三種改進的網絡拓撲結構層析成像識別方法，具體工作如下：
　　1、首先針對基于最大似然的拓撲估計方法計算量大的問題（對大規(guī)模網絡拓撲結構進行估計時），提出了改進的基于最大似然的快速拓撲估計方法，降低了計算復雜度。主要工作包括：1）證明了拓撲估計似然函數(shù)是單峰的且峰值為最大值。2）利用拓撲估

3、計似然函數(shù)的單峰性，用MCMC算法搜索拓撲空間時只需一直沿著似然函數(shù)上界值增大的方向進行即可，找到的似然函數(shù)最大值是全局最大值。改進算法搜索到的中間拓撲數(shù)目減少了，由于計算量主要集中在對搜索到的拓撲樹的似然函數(shù)上界值的計算上，因此計算量也減小了。3）模型仿真和網絡仿真驗證了改進算法的性能。
　　2、現(xiàn)有網絡拓撲結構層析成像識別方法假設所有的內部節(jié)點都不協(xié)作，然而在網絡中可能存在一些內部節(jié)點是可協(xié)作的，利用這些協(xié)作信息可以提高網絡拓

4、撲結構層析成像的工作效率，為此本文提出了一種基于端到端測量的快速網絡拓撲估計方法，主要工作包括：1）提取協(xié)作節(jié)點的協(xié)作信息。在內部協(xié)作節(jié)點上對數(shù)據(jù)流進行采樣，獲取從源節(jié)點經過該中間節(jié)點能夠到達的目的節(jié)點的集合，以此作為該節(jié)點的協(xié)作信息。2）利用協(xié)作信息構建約束條件，在拓撲搜索過程中，不滿足約束條件的拓撲樹直接被拋棄。由于需要計算似然函數(shù)上界值的拓撲樹減少了，計算量減少了。3）將拓撲估計似然函數(shù)的單峰特性和協(xié)作信息的約束結合起來，進一步減

5、小計算量。4）模型仿真和網絡仿真驗證了算法的性能。
　　3、為了減少探測包的發(fā)送數(shù)量，在一般的葉子節(jié)點加入樹拓撲估計算法基礎上，提出了門限分等級的葉子節(jié)點加入樹拓撲估計算法，主要工作包括：1）根據(jù)經驗確定經驗門限值。2）將經驗門限值分為n個等級。對于門限的每一個等級，分別利用一般葉子節(jié)點加入樹拓撲估計算法估計出相應的拓撲，利用最大似然方法計算出該拓撲的似然函數(shù)上界值。3）比較得到的n個拓撲的似然函數(shù)上界值，似然函數(shù)上界值最大的拓撲