網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)層析成像的改進(jìn)算法研究.pdf

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

2、大的計(jì)算量，后者對(duì)門限值的選取有很大的依賴性，好的門限值不僅能夠減少探測(cè)包的數(shù)量而且能夠提高拓?fù)涔烙?jì)準(zhǔn)確率。針對(duì)上述兩種算法存在的問題，本文提出了三種改進(jìn)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)層析成像識(shí)別方法，具體工作如下：
　　1、首先針對(duì)基于最大似然的拓?fù)涔烙?jì)方法計(jì)算量大的問題（對(duì)大規(guī)模網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行估計(jì)時(shí)），提出了改進(jìn)的基于最大似然的快速拓?fù)涔烙?jì)方法，降低了計(jì)算復(fù)雜度。主要工作包括：1）證明了拓?fù)涔烙?jì)似然函數(shù)是單峰的且峰值為最大值。2）利用拓?fù)涔?/p>

3、計(jì)似然函數(shù)的單峰性，用MCMC算法搜索拓?fù)淇臻g時(shí)只需一直沿著似然函數(shù)上界值增大的方向進(jìn)行即可，找到的似然函數(shù)最大值是全局最大值。改進(jìn)算法搜索到的中間拓?fù)鋽?shù)目減少了，由于計(jì)算量主要集中在對(duì)搜索到的拓?fù)錁涞乃迫缓瘮?shù)上界值的計(jì)算上，因此計(jì)算量也減小了。3）模型仿真和網(wǎng)絡(luò)仿真驗(yàn)證了改進(jìn)算法的性能。
　　2、現(xiàn)有網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)層析成像識(shí)別方法假設(shè)所有的內(nèi)部節(jié)點(diǎn)都不協(xié)作，然而在網(wǎng)絡(luò)中可能存在一些內(nèi)部節(jié)點(diǎn)是可協(xié)作的，利用這些協(xié)作信息可以提高網(wǎng)絡(luò)拓

4、撲結(jié)構(gòu)層析成像的工作效率，為此本文提出了一種基于端到端測(cè)量的快速網(wǎng)絡(luò)拓?fù)涔烙?jì)方法，主要工作包括：1）提取協(xié)作節(jié)點(diǎn)的協(xié)作信息。在內(nèi)部協(xié)作節(jié)點(diǎn)上對(duì)數(shù)據(jù)流進(jìn)行采樣，獲取從源節(jié)點(diǎn)經(jīng)過該中間節(jié)點(diǎn)能夠到達(dá)的目的節(jié)點(diǎn)的集合，以此作為該節(jié)點(diǎn)的協(xié)作信息。2）利用協(xié)作信息構(gòu)建約束條件，在拓?fù)渌阉鬟^程中，不滿足約束條件的拓?fù)錁渲苯颖粧仐?。由于需要?jì)算似然函數(shù)上界值的拓?fù)錁錅p少了，計(jì)算量減少了。3）將拓?fù)涔烙?jì)似然函數(shù)的單峰特性和協(xié)作信息的約束結(jié)合起來，進(jìn)一步減

5、小計(jì)算量。4）模型仿真和網(wǎng)絡(luò)仿真驗(yàn)證了算法的性能。
　　3、為了減少探測(cè)包的發(fā)送數(shù)量，在一般的葉子節(jié)點(diǎn)加入樹拓?fù)涔烙?jì)算法基礎(chǔ)上，提出了門限分等級(jí)的葉子節(jié)點(diǎn)加入樹拓?fù)涔烙?jì)算法，主要工作包括：1）根據(jù)經(jīng)驗(yàn)確定經(jīng)驗(yàn)門限值。2）將經(jīng)驗(yàn)門限值分為n個(gè)等級(jí)。對(duì)于門限的每一個(gè)等級(jí)，分別利用一般葉子節(jié)點(diǎn)加入樹拓?fù)涔烙?jì)算法估計(jì)出相應(yīng)的拓?fù)?，利用最大似然方法?jì)算出該拓?fù)涞乃迫缓瘮?shù)上界值。3）比較得到的n個(gè)拓?fù)涞乃迫缓瘮?shù)上界值，似然函數(shù)上界值最大的拓?fù)?/p>