[發(fā)明專利]一種復雜網(wǎng)絡拓撲中心節(jié)點的搜索算法

有效

• 申請?zhí)枺?/td>: 201710455259.9
• 申請日: 2017-06-16
• 公開（公告）號: CN107040467B
• 公開（公告）日: 2020-04-07
• 發(fā)明（設計）人: 魯智勇;杜靜;龐訓龍;劉喆;李鵬飛;白勇強;焦波;晉伊燦;歲賽;王金鎖;秦富童;袁學軍
• 申請（專利權(quán)）人: 中國洛陽電子裝備試驗中心
• 主分類號: H04L12/733
• 分類號: H04L12/733;H04L12/751;H04L12/753;H04L29/06;H04J3/06
• 代理公司: 洛陽市凱旋專利事務所 41112
• 代理人: 陸君

1.一種復雜網(wǎng)絡拓撲中心節(jié)點的搜索算法，其特征是：其步驟如下：

1)、網(wǎng)絡拓撲結(jié)構(gòu)獲取，掃描目標網(wǎng)絡，發(fā)現(xiàn)活動主機，獲取網(wǎng)絡拓撲結(jié)構(gòu)；

2)、節(jié)點無向圖獲取，將步驟1得到的目標網(wǎng)絡拓撲結(jié)構(gòu)的各節(jié)點及連通性用簡單無向連通網(wǎng)絡結(jié)構(gòu)G＝(V,E)表示，其中V和E分別為節(jié)點和邊的集合；

3)、節(jié)點遍歷度求解，對步驟2得到的簡單無向連通網(wǎng)絡結(jié)構(gòu)G＝(V,E)中求解節(jié)點v∈V到其它節(jié)點的最短路徑，選取最短路徑的最大值為節(jié)點遍歷度；設節(jié)點v₁,v₂∈V在圖G的最短路徑長度為P_L(v₁,v₂)，則節(jié)點v在網(wǎng)絡結(jié)構(gòu)G的節(jié)點遍歷度為：N_d(v)＝max_u∈V(P_L(u,v))；

4)、網(wǎng)絡遍歷度求解，依據(jù)步驟3，求解簡單無向連通網(wǎng)絡結(jié)構(gòu)G＝(V,E)中每個節(jié)點v的節(jié)點遍歷度，選取節(jié)點遍歷度的最小值為網(wǎng)絡遍歷度；網(wǎng)絡結(jié)構(gòu)G的網(wǎng)絡遍歷度為：N_d＝min_v∈V(N_d(v))；

5)、網(wǎng)絡拓撲中心節(jié)點求解，依據(jù)步驟4，若節(jié)點v∈V的節(jié)點遍歷度等于網(wǎng)絡遍歷度，即N_d(v)＝N_d，則判定節(jié)點v為網(wǎng)絡拓撲中心節(jié)點；

其中所述網(wǎng)絡拓撲存在中心節(jié)點，根據(jù)定義1、2和3，網(wǎng)絡必定存在網(wǎng)絡中心節(jié)點，構(gòu)造僅包含兩個節(jié)點的網(wǎng)絡結(jié)構(gòu)G，則網(wǎng)絡結(jié)構(gòu)G中存在兩個網(wǎng)絡中心節(jié)點，即網(wǎng)絡結(jié)構(gòu)G的中心節(jié)點不唯一；定義1節(jié)點遍歷度：網(wǎng)絡中，節(jié)點到其它各個節(jié)點的最短路徑，最少跳數(shù)的最大值；定義2網(wǎng)絡遍歷度：網(wǎng)絡中所有節(jié)點遍歷度的最小值；定義3網(wǎng)絡拓撲中心節(jié)點：節(jié)點遍歷度等于網(wǎng)絡遍歷度的節(jié)點稱為網(wǎng)絡拓撲中心節(jié)點；

其中以網(wǎng)絡拓撲中心節(jié)點為起點，遍歷整個網(wǎng)絡的遍歷深度最小，遍歷深度是指遍歷樹中節(jié)點與網(wǎng)絡中心節(jié)點的最大距離；依據(jù)廣度優(yōu)先遍歷原則，以網(wǎng)絡中心節(jié)點v∈V為起點的遍歷路徑，對應于網(wǎng)絡結(jié)構(gòu)G中以v為根節(jié)點的生成樹T；采用歸納法證明：對于任意節(jié)點u∈V，若在網(wǎng)絡結(jié)構(gòu)G中P_L(u,v)＝k，則節(jié)點u在且僅在以v為起點的根節(jié)點的第k次遍歷時加入生成樹T，且第k次遍歷獲得生成子樹中節(jié)點與節(jié)點v的最大距離為k；

當k＝1時，以v為起點的第1次遍歷，將與v相鄰的所有節(jié)點均加入生成樹T，即若P_L(u,v)＝1則節(jié)點u在且僅在以v為起點的第1次遍歷時加入生成樹T，且第1次遍歷獲得生成子樹中節(jié)點與節(jié)點v的最大距離為1成立；

假設k≤l時成立，下面證明k＝l+1時成立：

設L＝v,v₁,v₂,…,u₁,u為節(jié)點v,u之間的任意一條最短路徑；易知L₁＝v,v₁,v₂,…,u₁為節(jié)點v,u₁之間的最短路徑，且P_L(u₁,v)＝l；根據(jù)假設條件，節(jié)點u₁在且僅在以v為起點的第l次遍歷時加入生成樹T，且第l次遍歷獲得生成子樹中節(jié)點與節(jié)點v的最大距離為l；

(1)若節(jié)點u在前l(fā)次遍歷時已加入生成樹T：因為前l(fā)次遍歷獲得生成子樹中節(jié)點與節(jié)點v的最大距離不大于l，所以節(jié)點v,u之間的最短距離不大于l，與P_L(u,v)＝l+1矛盾，即節(jié)點u在前l(fā)次遍歷時已加入生成樹T不成立；

(2)若節(jié)點u在前l(fā)次遍歷時沒有加入生成樹T：

設集合U＝{u₁|u₁與u相鄰，且u₁在v與u之間的最短路徑上}，并設前l(fā)次遍歷獲得生成子樹為， 易知因為邊集{(u₁,u)|u₁∈U}均包含于網(wǎng)絡結(jié)構(gòu)G且節(jié)點u不包含于T′，所以節(jié)點u在且僅在以v為起點的根節(jié)點的第l+1次遍歷時加入生成樹T，且第l+1次遍歷獲得生成子樹中節(jié)點與節(jié)點v的最大距離為l+1；

因此，若在網(wǎng)絡結(jié)構(gòu)G中P_L(u,v)＝k，則節(jié)點u在且僅在以v為起點的根節(jié)點的第k次遍歷時加入生成樹T，且第k次遍歷獲得生成子樹中節(jié)點與節(jié)點v的最大距離為k；

易知若網(wǎng)絡結(jié)構(gòu)G中節(jié)點與節(jié)點v的最大距離為k，則以v為起點的根節(jié)點的遍歷深度為k；設節(jié)點v為網(wǎng)絡結(jié)構(gòu)G的網(wǎng)絡中心節(jié)點，即節(jié)點v的節(jié)點遍歷度最小，因此，以v為起點，遍歷整個網(wǎng)絡的遍歷深度最小。

2.根據(jù)權(quán)利要求1所述的一種復雜網(wǎng)絡拓撲中心節(jié)點的搜索算法，其特征是：所述網(wǎng)絡遍歷度不小于最大的節(jié)點遍歷度的一半；設L＝v₁,v₂,…,v_n為網(wǎng)絡結(jié)構(gòu)G的直徑，即L為節(jié)點v₁,v_n之間的最短路徑，且L為網(wǎng)絡結(jié)構(gòu)G中的最長最短路徑；則網(wǎng)絡遍歷度不小于最大節(jié)點遍歷度的一半；

易知，最大節(jié)點遍歷度為n；設v為網(wǎng)絡結(jié)構(gòu)G中的任意節(jié)點，設N_d(v)為v的節(jié)點遍歷度，并設L₁＝v,u₁,u₂,…,v₁和L₂＝v,u′₁,u₂′,…,v_n分別為節(jié)點v至v₁和v_n的最短路徑；易知L₁和L₂的長度均不大于N_d(v)；因L為節(jié)點v₁,v_n之間的最短路徑，所以路徑L₁∪L₂＝v₁,…,u₁,v,v,u′₁,…,v_n的長度不小于n；因此，2·N_d(v)不小于L₁∪L₂的長度，且L₁∪L₂的長度不小于n，即N_d(v)≥n/2；

因此，網(wǎng)絡結(jié)構(gòu)G中任意節(jié)點的節(jié)點遍歷度均不小于最大節(jié)點遍歷度的一半；網(wǎng)絡中心節(jié)點是網(wǎng)絡結(jié)構(gòu)G中的節(jié)點，且網(wǎng)絡遍歷度為網(wǎng)絡中心節(jié)點的節(jié)點遍歷度，即網(wǎng)絡遍歷度不小于最大節(jié)點遍歷度的一半。