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

有效

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

本申請提供一種無規則網絡拓撲結構生成方法及裝置，計算已有網絡中每一個節點的平均最短路徑長度，確定平均最短路徑長度最小的一個第一節點和平均最短路徑長度最大的一個第二節點；在與所述第一節點直接相連的節點中，確定平均最短路徑長度最小的一個第三節點；在與所述第二節點直接相連的節點中，確定平均最短路徑長度最大的一個第四節點，以及直接相互連接的第五節點和第六節點；依據上述確定的節點確定三個備選接入位置，然后從三個備選接入位置中確定一個位置為待接入設備的接入位置。節省了計算量，提高了無規則網絡拓撲結構的生成速度。

技術領域

本發明涉及通信技術領域，尤其涉及一種無規則網絡拓撲結構生成方法及裝置。

背景技術

網絡的拓撲結構分為規則拓撲結構和無規則拓撲結構，其中，無規則拓撲結構的網絡由于其較好的網絡特性而被廣泛關注。

目前常用的一種無規則網絡拓撲結構生成方法是，在已有網絡上，當需要添加新設備時，通過隨機選擇的方式多次選出兩個設備節點（簡稱節點），將待接入設備接入所選擇的兩個節點之間，然后計算連接后的網絡總體性能（性能參數一般為網絡整體的平均路徑長度），在多次隨機選擇出來的計算結果中選出性能最好的一次連接作為設備連接。

而接入網絡的設備通常存在多個可接入網絡的端口，每次設備接入網絡時，只選取兩個端口，因此，一個設備如果完整的接入網絡需要若干次選取接入位置，可見，應用目前的無規則網絡拓撲生成方法需要若干次隨機計算才能將待接入設備完整地接入網絡，使得無規則網絡拓撲結構生成速度較慢。

發明內容

本發明實施例提供了一種無規則網絡拓撲結構生成方法及裝置，以提高無規則網絡拓撲結構生成速度。

本發明的第一方面提供一種無規則網絡拓撲結構生成方法，包括：

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

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

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

在所述三個備選接入位置中確定一個位置為所述待接入設備的接入位置。

結合第一方面，在第一方面的第二種可能的實現方式中，所述在所述三個備選接入位置中確定一個位置為所述待接入設備的接入位置包括：

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

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

結合第一方面，在第一方面的第三種可能的實現方式中，所述在所述三個備選接入位置中確定一個位置為所述待接入設備的接入位置包括：

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

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

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