[發明專利]一種基于多參數認知的快速網絡拓撲推斷方法

有效

• 申請號: 201310293511.2
• 申請日: 2013-07-12
• 公開（公告）號: CN103326904A
• 公開（公告）日: 2013-09-25
• 發明（設計）人: 徐友云;李來扛;李寧;謝威;張冬梅
• 申請（專利權）人: 中國人民解放軍理工大學
• 主分類號: H04L12/26
• 分類號: H04L12/26
• 代理公司: 南京天華專利代理有限責任公司 32218
• 代理人: 夏平

1.一種基于多參數認知的快速網絡拓撲推斷方法，其特征在于它包括以下步驟：首先對探測報文時延及探測報文丟失感知，對探測報文時延參數進行差值分析，通過計算葉節點間的相似度來判斷葉節點的關系并推測得到葉節點拓撲結構，將葉節點拓撲與原拓撲對比判斷其相似度是否滿足適當的閾值要求，若不滿足要求則反饋調整探測報文參數，完成認知循環；若滿足要求則分析父節點丟包參數，計算父節點間的Hamming距離作為其相似度，根據相似度推斷節點關系，進而推斷網絡拓撲結構。?

2.如權利要求1所述的基于多參數認知的快速網絡拓撲推斷方法，其特征在于該方法具體包括以下步驟：?

a、在無線網絡中構建樹狀網絡拓撲結構，其中包含根節點、中間節點和葉節點，記錄各節點之間的父子、兄弟、孤立關系；兄弟節點在其上層擁有同一個父節點，而此兄弟節點稱作是父節點的子節點，孤立節點在本層無兄弟關系節點；?

b、由根節點連續向所有葉節點組播探測報文；每個葉節點記錄所有探測報文丟失情況并計算每個探測報文的時延；?

c、對各葉節點探測報文的時延數據進行差值分析，并計算各葉節點的相似度；?

d、根據葉節點的相似度，判斷葉節點的關系是兄弟節點或孤立節點，進而得到葉節點拓撲結構，并判斷葉節點拓撲與原拓撲的相似度即判斷各節點之間的父子、兄弟、孤立關系與步驟a中的構建的關系是否吻合，網絡拓撲的相似度等于節點集中被正確識別出的節點數量與節點集中總的節點數量的比值；?

如果相似度達到閾值要求，則進行步驟e；?

如果相似度達不到閾值要求，則反饋調整探測報文參數，減小發送探測報文的時間間隔，返回步驟b；?

e、根據子節點報文丟失情況推測父節點的報文丟失情況，進而計算父節點及孤立節點間的Hamming距離，若節點間的Hamming距離滿足給定的關系式則視為兄弟節點，否則視為非兄弟節點，以此推斷節點間的關系，進而得到網絡邏輯拓撲結構。?

3.如權利要求2所述基于多參數認知的快速網絡拓撲推斷方法，其特征在于，所述步驟a中無線樹狀網絡拓撲結構中，根節點組播m個探測報文給所有葉節點，探測報文間有一定的時間間隔。?

4.如權利要求2所述基于多參數認知的快速網絡拓撲推斷方法，其特征在于，所述步驟b?中每個葉節點都用一個隨機過程來表示探測報文丟失情況，其中表示第i個探測報文在節點k處的丟失情況，如果節點k接收到探測報文，則否則用表示節點k處第i個探測報文的時延。?

5.如權利要求2所述基于多參數認知的快速網絡拓撲推斷方法，其特征在于，所述步驟c中具體包括：?

計算各葉節點的相似度：針對任意兩個葉節點k、l，首先計算m個時延數據的平均值，記為選擇合適門限值δ，將兩個葉節點k、l的相應的m個時延數據與?進行比較，若滿足將位置i的值置為1，否則為0，寫入對應的時延差值類數據庫中，并統計其中1的個數，記為n_kl，采用公式1計算任意兩個葉節點k、l的相似度；前述門限值δ根據實驗數據設置；?

。

6.如權利要求2所述基于多參數認知的快速網絡拓撲推斷方法，其特征在于，所述步驟d中，根據步驟c計算得到的葉節點相似度，并選擇合適門限值ε，滿足的視為兄弟節點，若不滿足則葉節點中無兄弟節點，稱之為孤立節點，通過判斷將葉節點分為兄弟節點和孤立節點兩類，進而推測得到葉節點拓撲結構，并將葉節點拓撲與原拓撲對比，若網絡拓撲的相似度滿足適當的閾值要求，則執行步驟e，否則反饋調整探測報文參數，減小發送探測報文的時間間隔，返回步驟b；前述門限值ε和閾值根據實際精度需求進行設置。?

7.如權利要求6所述基于多參數認知的快速網絡拓撲推斷方法，其特征在于，網絡拓撲的相似度閾值的范圍是70-99%；門限值δ的范圍是

8.如權利要求2所述基于多參數認知的快速網絡拓撲推斷方法，其特征在于，所述步驟e中，根據子節點探測報文丟失情況推斷其父節點的探測報文丟失情況，父節點的探測報文丟失情況為所有子節點報文丟失情況的并集，任一節點k的報文丟失情況用來表示，它的子節點為節點1,2,...,s，則節點u與節點v之間的Hamming距離表示為為異或運算，m是探測報文的數量。根據父節點探測報文丟失情況計算父節點及孤立節點間的Hamming距離，選擇Hamming距離最小的兩個節點k、l作為兄弟節點，再判斷其他節點k′是否與節點k、l是兄弟節點，若?滿足視為兄弟節點，否則不是兄弟節點，這里ξ=1-α_min，α_min鏈路的最小丟包率，在識別出所有兄弟節點后，從節點集合中去掉所有的兄弟節點，加入其父節點。重復步驟e直至葉節點集合內剩下一個節點為止。?