[發明專利]一種無規則網絡拓撲結構生成方法及裝置

有效

• 申請號: 201310745712.1
• 申請日: 2013-12-30
• 公開（公告）號: CN104753795B
• 公開（公告）日: 2018-05-11
• 發明（設計）人: 許勝;付斌章;陳明宇;張立新
• 申請（專利權）人: 華為技術有限公司;中國科學院計算技術研究所
• 主分類號: H04L12/751
• 分類號: H04L12/751
• 代理公司: 深圳市深佳知識產權代理事務所(普通合伙) 44285
• 代理人: 唐華明

1.一種無規則網絡拓撲結構生成方法，其特征在于，包括：

計算已有網絡中每一個節點的平均最短路徑長度；

確定平均最短路徑長度最小的一個第一節點和平均最短路徑長度最大的一個第二節點；在與所述第一節點直接相連的節點中，確定平均最短路徑長度最小的一個第三節點；在與所述第二節點直接相連的節點中，確定平均最短路徑長度最大的一個第四節點；在與所述第二節點直接相連的節點中，確定直接相互連接的第五節點和第六節點；

將所述第一節點與所述第三節點之間的位置作為待接入設備的第一備選接入位置；將所述第一節點與所述第三節點之間的連接，以及所述第二節點與所述第四節點之間的連接斷開，并連接所述第一節點和所述第二節點，將所述第三節點和所述第四節點之間的位置作為待接入設備的第二備選接入位置；將所述第五節點和第六節點之間位置作為所述待接入設備的第三備選接入位置；

根據三個所述備選接入位置的平均最短路徑長度，在三個所述備選接入位置中確定一個位置為所述待接入設備的接入位置。

2.根據權利要求1所述的方法，其特征在于，所述在所述三個備選接入位置中確定一個位置為所述待接入設備的接入位置包括：

分別計算所述待接入設備接入所述三個備選接入位置中的其中一個備選接入位置后，整個網絡的平均最短路徑長度；

將整個網絡的平均最短路徑長度最小的備選接入位置確定為所述待接入設備的接入位置。

3.根據權利要求1所述的方法，其特征在于，所述在所述三個備選接入位置中確定一個位置為所述待接入設備的接入位置包括：

判斷所述第一備選接入位置是否可用；

如果不可用，則分別計算所述待接入設備接入所述第二備選接入位置后整個網絡的平均最短路徑長度，以及所述待接入設備接入所述第三備選接入位置后整個網絡的平均最短路徑長度，并將所述第二備選接入位置和所述第三備選接入位置中，使整個網絡的平均最短路徑長度最小的備選接入位置作為所述待接入設備的接入位置；

如果可用，則將所述第一備選接入位置作為所述待接入設備的接入位置。

4.根據權利要求1所述的方法，其特征在于，所述在所述三個備選接入位置中確定一個位置為所述待接入設備的接入位置包括：

判斷所述第三備選接入位置是否可用；

如果不可用，則分別計算所述待接入設備接入所述第一備選接入位置后整個網絡的平均最短路徑長度，以及所述待接入設備接入所述第二備選接入位置后整個網絡的平均最短路徑長度，并將所述第一備選接入位置和所述第二備選接入位置中，使整個網絡的平均最短路徑長度最小的備選接入位置作為所述待接入設備的接入位置；

如果可用，則將所述第三備選接入位置作為所述待接入設備的接入位置。

5.根據權利要求1所述的方法，其特征在于，所述在所述三個備選接入位置中確定一個位置為所述待接入設備的接入位置包括：

判斷在連接所述第一節點和所述第二節點之前，所述第一節點和所述第二節點之間是否已經存在連接關系，如果是，則執行第一步驟，否則，執行第二步驟；

第一步驟：則分別計算所述待接入設備接入所述第一備選接入位置后整個網絡的平均最短路徑長度，以及所述待接入設備接入所述第三備選接入位置后整個網絡的平均最短路徑長度，并將所述第一備選接入位置和所述第三備選接入位置中，使整個網絡的平均最短路徑長度最小的備選接入位置作為所述待接入設備的接入位置；

第二步驟：判斷所述第二備選接入位置是否可用，如果不可用，則執行第一步驟，如果可用，則將所述第二備選接入位置作為所述待接入設備的接入位置。