[發明專利]一種基于總體布局的隨機網絡拓撲結構生成方法

有效

• 申請號: 201310395219.1
• 申請日: 2013-09-03
• 公開（公告）號: CN103457860A
• 公開（公告）日: 2013-12-18
• 發明（設計）人: 姚文斌;韓司;姚翔
• 申請（專利權）人: 北京郵電大學
• 主分類號: H04L12/751
• 分類號: H04L12/751;H04L12/28
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于總體布局的隨機網絡拓撲結構生成方法，其特征在于：本發明的目的是這樣實現的：設生成隨機整數N,N>1為網絡結點的數目，生成隨機整數M為需要網絡中邊的數目，滿足0<M≤(N×(N-1))2，否則重新生成M；使用N*N維矩陣G記錄網絡結點連接關系的拓撲圖，矩陣中元素G_ij（1<i,j≤N）的值為0或者1，0表示網絡結點i和結點j不存在連接通路，1表示網絡結點i和結點j之間存在連接通路，任意兩個結點間只保留一條直接連接通路；初始化矩陣G，使得矩陣G中所有元素的值為0；生成M對隨機數{A₁,B₁}…{A_i,B_i}…{A_m,B_m}，其中A_i,B_i∈{1,2,...,N}且A_i≠B_i；{A_i,B_i}表示結點A_i和結點B_i間存在一條連接通路，填充矩陣G中的元素G_AiBi=1；這樣生成了一個隨機網絡拓撲圖G，由于隨機數中可能存在兩對隨機數{A_i,B_i},{A_j,B_j}有A_i=B_j，B_i=A_j的情況，這說明在生成的拓撲圖中出現了兩結點存在一條以上連通鏈路的情況，為此，將矩陣G中滿足j小于等于i的所有元素Gij置為0，然后計算矩陣G中1的個數NUM，此時NUM是已經生成的隨機網絡中連接邊數；如果NUM<M，則生成M-NUM對隨機數，填充矩陣G，并將矩陣G中滿足j小于等于i的所有元素Gij置為0，再次計算矩陣G中1的個數NUM，如果NUM<M則重復本步驟直至NUM的值等于M；如果矩陣G中存在一行或一列的值均為0，即存在Gij=0（j=1,2…n）或者Gij=0（i=1,2….n），表明結點i或者結點j不與其它結點連通，則將該結點刪除，最終用矩陣G表示優化的網絡拓撲結構，這樣就生成了一種基于總體布局的網絡拓撲結構；

具體步驟為：

(1)生成隨機數N，用于表示網絡結點數；

(2)生成隨機數M，用于表示網絡中連接邊數；

(3)如果0<M≤(N×(N-1))2，則執行步驟4；否則執行步驟2；

(4)初始化生成N*N維矩陣G，G中元素均為0；

(5)初始化NUM=0，用于表示矩陣G中元素1的個數；

(6)生成隨機數{A_i,B_i}；

(7)如果滿足條件A_i≠B_i，則執行步驟8；否則執行步驟6；

(8)如果滿足條件1≤A_i≤N，則執行步驟9；否則執行步驟6；

(9)如果滿足條件1≤B_i≤N，則執行步驟10；否則執行步驟6；

(10)填充矩陣G中元素G_AiBi=1；

(11)將矩陣G中所有j小于等于i的元素G_ij置為0；

(12)計算矩陣G中1的個數并保存在NUM中，如果NUM<M執行步驟6；否則執行步驟13；

(13)如果矩陣G中存在G_ij=0，對于j=1,2…n，則刪除矩陣中第i行；

(14)如果矩陣G中存在G_ij=0，對于i=1,2….n則刪除矩陣中第j列；

(15)矩陣G中保存了基于總體布局的隨機網絡拓撲結構信息，生成程序結束。