本站小編為你精心準備了混合模型網絡拓撲論文參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

1網絡拓撲推斷模型

本文將待推斷的網絡拓撲建模為有向邏輯樹T[7]，令T(V,E)，V為節點集合，對應網絡中的物理設備(主機、路由器等)，V由根節點s、葉子節點集合D(NrD為葉子節點數目)以及內部節點集合I構成；E為邊集合,對應網絡中的鏈路。令根節點s為源節點，樹的葉子節點集合D為接收節點。令UsD為端節點，易得U中所有節點的度都為1(假設每個端節點僅與一個路由器相連)。該邏輯樹中除根節點之外的所有非葉子節點均至少有兩個孩子節點，除根節點之外的任一節點vID均有唯一的父節點f(v)；令(f(v),v),f(v),vV表示v與其父節點之間的鏈路；令(s,v)為根節點s與節點v之間的鏈路；令a(i,j),ij,i,jD為節點對{i,j}最深(距根節點最遠)的公共父節點；令P(i,j)為{(s,i),(s,j)}的共享鏈路，即P(i,j)(s,a(i,j))，如圖1中節點1和2的最深公共父節點為13，則1和2的共享鏈路為0,13。定義兩葉子節點的相關性為((,))ijNPij，N(P(i,j))表示節點對(i,j)共享鏈路上的某種性能(排隊時延方差、丟包率方差等)的度量，有N(P(i,j))P(i,j)，可見拓撲樹中兩個葉子節點的共享鏈路越長，則其相關性越大。葉子節點相關性滿足以下條件[3-5]：1)單調性：若P(i,j)為P(k,l)的子鏈路，i,j,k,lD且ij,kl，則有ijkl。2)一致性：若P(i,j)與P(k,l)為同一鏈路，即a(i,j)a(k,l)，i,j,k,lD且ij,kl，則ijkl。令葉子節點i,j的相關性ij的估計值為ˆij。只要得到樹狀拓撲中葉子節點的相關性集合{ˆ,,}ijijD，就可以利用節點之間的相關性測度來推斷出樹狀拓撲結構。

2穩健的網絡拓撲推斷算法

基于單播的拓撲推斷需要向網絡發送大量的探測包，這將給目標網絡帶來較大的流量，因此減少推斷網絡拓撲需要發送的探測包數目是將層析成像拓撲推斷方法推向實際應用的關鍵。文獻[8]提出了基于DFS排序的高效層析成像拓撲推斷算法——Margin-Based算法，較以往的算法大大減少了需要測量的相關性數據，但其需要設置固定門限來對節點進行DFS排序，不同的門限對算法的拓撲推斷性能影響較大，且該文沒有給出一種可行的最優門限選擇方法。針對這一問題，本節提出一種基于有限混合模型聚類的穩健高效層析成像拓撲推斷算法(RobustMethod)，該算法與Margin-Based算法的本質區別是，該算法通過葉子節點逐步分類獲得樹狀拓撲，而Margin-Based算法是通過多次對葉子節點二分對葉子節點進行深度優先排序(DFS)，然后通過比較相鄰葉子節點的相關性大小對排序后的葉子節點合并獲得樹狀拓撲。

算法思想其中D為葉子節點集合，V為拓撲圖的頂點集合，\表示刪除,f()N表示集合中所有節點的父節點指定為N節點，表示集合中元素個數，表示右邊賦值給左邊。偽代碼中(2)-(5)處理聚類結果為1的情況，此時在鏈路(0,i)上只有一個內部節點。(6)-(17)處理聚類結果不為1的情況，此時在鏈路(0,i)上有多個內部節點。(7)-(16)分別對每個內部節點進行處理。

3仿真實驗及結果分析

實驗1本實驗在不同方差因子條件下比較Margin-Based和RobustMethod算法的拓撲推斷性能。仿真所用樹狀拓撲如圖3所示，對每一對葉子節點(i,j)，使用Matlab生成滿足單調性和一致性條件的節點相似度采樣數據，W200。這些采樣數據為節點對共享鏈路上的所有子鏈路的測度數據之和。每條子鏈路的測度數據服從均值為l，方差為l的高斯分布。其中~uniform(1,5)l，(1/2)l，為方差因子，N10，normNW/N20。使用推斷拓撲與原拓撲的樹編輯距離評價算法性能。樹編輯距離[5,6]定義為從一個樹圖映射到另外一個樹圖所需的編輯操作之和，樹編輯距離越小，表示兩樹圖越相似，即推斷樹狀拓撲與原樹狀拓撲的樹編輯距離越小，拓撲推斷的效果越好。為了體現不同的初始參考節點的對算法性能影響，每一次實驗都隨機選取初始參考點。本實驗檢驗Margin-Based和RobustMethod在方差因子從1到7的拓撲推斷性能，每個方差因子下獨立進行1000次蒙特卡羅實驗。

為研究不同DFS門限對Margin-Based算法性能的影響，我們分別取其門限為0.5、0.7、0.9、1.1、1.3、1.5進行仿真實驗。圖3給出了兩種算法,的樹編輯距離性能，由圖3可知，隨著方差因子增加，Margin-Based算法與本文的RobustMethod算法的樹編輯距離都增大；對于不同的門限值Margin-Based算法的樹編輯距離差異較大，可見其性能對門限值較為敏感，隨著門限取值由小到大變化，Margin-Based算法的性能呈現由差到好再變差的過程，其中門限為0.9時性能近似為最優；而本文的RobustMethod算法應用了有限混合模型對葉子節點分類，無需設置比較門限，因此其拓撲推斷過程更為穩健，從圖3中可以看出，RobustMethod算法基本可以達到Margin-Based算法取最優門限時的性能。實驗2本實驗比較Margin-Based算法與RobustMethod算法所需測量的葉子節點相關性個數。在葉子節點數為5，10，15，20，25，30條件下，分別隨機生成2000，5000，10000，18000，28000，40000個任意形狀的樹狀拓撲，統計兩種算法對這些拓撲需要測量的葉子節點相關性個數，取平均。

圖4畫出了兩種算法在不同葉子節點數目條件下所需測量的葉子節點對相關性個數。從圖中可以看出對于不同葉子節點個數的樹狀拓撲，RobustMethod算法平均需要測量的節點相關性數目要略少于Margin-Based算法，葉子節點個數較少時，二者需要測量的相關性數據數目近似，而隨著拓撲節點數目增加，二者的差距逐漸增加。實驗3本實驗通過網絡仿真軟件Opnet產生網絡采樣數據，應用Margin-Based和RobustMethod兩種算法推斷網絡拓撲。網絡拓撲如圖5所示，節點0為源主機節點，其它葉子節點為目的主機節點，節點16、17、18、19、20為路由器節點，端節點與路由器之間的鏈路速率為T1(1.544Mb/s)，路由器之間的鏈路速率為E1(2.048Mb/s)。每條鏈路上的背景流量都由Opnet中自帶的ip_traffic_flow生成，端節點與路由器之間的鏈路背景流量設置為100Kb/s，路由器之間的鏈路背景流量設為300Kb/s，為體現背景流量的自相似性，背景流量都由50條ip_traffic_flow組成，每個ip_traffic_flow速率都相等，其包間隔都服從pareto分布，包大小服從負指數分布。應用三明治包方法進行葉子節點相似度采樣，其中大包和小包分別為500Byte、10Byte。在不同探測包數目W條件下，通過Opnet軟件分別采集1000組獨立的葉子節點相關性數據。為體現不同的初始參考節點的對算法性能影響，每一次實驗都隨機選取初始參考點。

為研究不同DFS門限對Margin-Based算法性能的影響，我們分別取其門限為，0.55，0.65，0.75，0.85，0.95，1.05進行仿真實驗。圖6給出了Margin-Based和RobustMethod兩種算法在不同探測包數(即第2節中的W)條件下的1000次仿真的平均樹編輯距離，可見，隨著節點對探測包個數的增加，數據集的方差逐步減小，兩種算法的性能均有所提高；不同的比較門限對Margin-Based算法的影響較為明顯，隨著門限由小到大變化，Margin-Based算法的性能也是由差變好再變差，在門限取0.75時可達到最優的性能；而本文的RobustMethod的樹編輯距離曲線與Margin-Based算法門限取0.75時近似，因此RobustMethod可以達到Margin-Based算法的最優性能。

4結束語

本文提出一種基于有限混合模型的穩健高效層析成像網絡拓撲推斷算法，較文獻[8]中提出的高效拓撲推斷算法，該算法需要測量更少的葉子節點相關性數據，其應用有限混合模型實現對節點的自適應分類，無需設定比較門限，具有更好的穩健性。但由于該算法應用了有限混合模型，在一定程度上增加了算法的運算復雜度，因此今后的工作還需要進一步較少其運算量，以更好地滿足對實時性要求。

作者：張潤生劉健李艷斌單位：中國電子科技集團公司第五四研究所中國空間技術研究院通信衛星事業部