一種基於結點連接的隨機網絡拓撲結構生成方法
2023-08-22 10:28:56
一種基於結點連接的隨機網絡拓撲結構生成方法
【專利摘要】本發明提供的是一種基於結點連接的隨機網絡拓撲結構生成方法，首先生成隨機數用於確定網絡結點的數目N，對於每個接點隨機生成一個隨機數M，表明該結點將與M節電發生通信，同時調整隨機數保證生成連接中不存在雙向和自連接的情況。本發明使用隨機數生成模擬隨機網絡，突出模擬網絡的隨機性，並且克服隨機網絡拓撲很難貼近真實網絡的缺點，生成一種更加貼近真實網絡結構特性的網絡拓撲。
【專利說明】一種基於結點連接的隨機網絡拓撲結構生成方法
(-)【技術領域】
[0001 ] 本發明涉及的是一種基於結點連接的隨機網絡拓撲結構生成方法。
(二)【背景技術】
[0002]在計算機網絡研究中，經常需要對新的應用程式、體系結構或者協議等進行評估，因此基於真實網絡的網絡模擬就成了計算機網絡研究的一種重要方法。由於網絡存在多樣性和複雜性，影響網絡模擬穩定性的重要因素就是所使用的網絡拓撲模型。用儘量能反映真實網絡的模型作為對真實網絡環境的一種抽象，使之作為網絡模擬的基本輸入，是取得正確結果的必要條件。
[0003]目前網絡拓撲的生成存在三種方法:人為指定或者人工的從網絡拓撲庫中選擇，以一定的模型和算法為基礎由計算機輔助生成；隨機生成。其中，前兩種方法基本是以傳統的網絡拓撲和一些著名的網絡拓撲結構為基礎的，生成的網絡結構僅能反映過去和現在網絡的特性，不能反映將來可能出現的與過去和現在不同的網絡結構，前兩種方法對生成的網絡拓撲結構對於網絡的研究而言，不具有普遍性。
[0004]通過上面的分析，為保證產生的網絡拓撲更具有通用性，我們提出了一種隨機網絡拓撲的生成方法:生成隨機數，用於確定網絡結點的數目N，對於每個接點隨機生成一個隨機數M，表明該結點與M間存在一條連接通路，同時調整隨機數保證生成連接中不存在雙向和自連接的情況，這樣就模擬了一種隨機網絡拓撲的生成。
(三)
【發明內容】
[0005]本發明的目的在於提供一種基於結點連接的隨機網絡拓撲結構生成方法。該方法使用隨機數生成模擬隨機網絡，突出模擬網絡的隨機性，每次產生的模型網絡從頂點分布到連接方式都不盡相同。並且克服隨機網絡拓撲很難貼近真實網絡的缺點，生成一種更加貼近真實網絡結構特性的網絡拓撲。
[0006]本發明的目的是這樣實現的:
[0007]一種基於結點連接的隨機網絡拓撲結構生成方法，其特徵在於:本發明的目的是這樣實現的:本發明的目的是這樣實現的:設生成隨機整數N為網絡拓撲中網絡結點的數目，遍歷每一個結點，為每一個結點生成隨機數M,表示該結點與M個結點有連接，M〈N ;使用N*N維矩陣G記錄網絡結點連接關係的拓撲圖，矩陣中元素Gu，1≤≤i，j≤N的值為O或者1，O表示網絡結點i和結點j不存在連接通路，I表示網絡結點i和結點j之間存在連接通路，任意兩個結點件只保留一條直接連接通路；初始化矩陣G，使得矩陣G中所有元素的值為O ;對網絡中的每個結點Ni,生成隨機數M表示Ni將與M個結點進行連接，隨機生成M個整數組成集合A= (A1,…，AM},滿足Ai e {1，2，...，N}且Ai古Ni ;這樣最終生成矩陣G表示優化的網絡拓撲，模擬生成了一種基於結點連接的隨機網絡拓撲；
[0008]具體步驟為:
[0009](1)用戶輸入隨機網絡結點數目N，表示隨機網絡結點集合位N= {K，N2, , Nj ;[0010](2)初始化生成N*N維零矩陣G，G中元素均為0，用於描述網絡拓撲結構；
[0011](3)初始化 i=l;
[0012](4)生成隨機數M，M〈N ；
[0013](5) NUM=O;
[0014](6)隨機生成 M-NUM 個隨機數集合 A=隊，A2, , AiramUiMAi e {1，2，...，N}且Ai古隊，初始化j=l ；
[0015](7)從集合A取出Aj;
[0016](8)如果G ,、=1,則執行步驟10，否則執行步驟9 ；
[0017](9)對6 f X賦值為I，對仏為賦值為I ;
[0018](10) j值加I ;如果j> (M-NUM)執行步驟11，否則執行步驟7 ；
[0019](11)修改NUM為矩陣G中第i列中I的個數；
[0020](12)如果NUM〈M則執行步驟6否則執行步驟13 ；
[0021](13) i的值加I ;如果i>N，執行步驟4，否則執行步驟14 ；
[0022](14)矩陣G中記錄了一個完整的隨機網絡拓撲結構，程序結束。
[0023]本發明的關鍵在於如何保證網絡結點和網絡連接的隨機性。為此，通過隨機數確定網絡結點和連接來生成整個拓撲網絡，並將不滿足現實連接的數值重新生成調整，在保證網絡拓撲隨機的基礎上，還使生成的網絡更加貼近真實的網絡。
[0024]其主要特點如下:
[0025]1、使用隨機數生成方法來確定網絡拓撲的結點和連接，對於網絡中的每個接點生成隨機連接,體現網絡拓撲的普遍性；
[0026]2、控制隨機數的生成，保證生成的拓撲網絡中不存在自連接和雙向連接，同時為每個結點生成有效連接，避免隨機網絡中孤兒結點的存在。
(四)【專利附圖】
【附圖說明】
[0027]圖1:一種基於結點連接的隨機網絡拓撲結構生成方法
(五)具體的實施方式
[0028]下面結合附圖距離對本發明作更詳細的描述:
[0029]本發明所述方法的特徵在於:
[0030]設生成隨機整數N為網絡拓撲中網絡結點的數目，遍歷每一個結點，為每一個結點生成隨機數M,表示該結點與M個結點有連接，M〈N ;使用N*N維矩陣G記錄網絡結點連接關係的拓撲圖，矩陣中元素Gu，1 ≤ i, j≤ N的值為O或者1，O表示網絡結點i和結點j不存在連接通路，I表示網絡結點i和結點j之間存在連接通路，任意兩個結點件只保留一條直接連接通路；初始化矩陣G，使得矩陣G中所有元素的值為O ;對網絡中的每個結點Ni,生成隨機數M表示Ni將與M個結點進行連接,隨機生成M個整數組成集合A= (A1,…，AmI ,滿足Ai e {I, 2,...,N}且Ai古Ni ;這樣最終生成矩陣G表示優化的網絡拓撲，模擬生成了一種基於結點連接的隨機網絡拓撲；具體步驟為:
[0031](I)用戶輸入隨機網絡結點數目N，表示隨機網絡結點集合位N= {K，N2, , Nj ;[0032](2)初始化生成N*N維零矩陣G，G中元素均為0，用於描述網絡拓撲結構；
[0033](3)初始化 i=l ;
[0034](4)生成隨機數M，M〈N ；
[0035](5) NUM=O ；
[0036](6)隨機生成 M-NUM 個隨機數集合 A= (A1, A2, , Am_nJ，滿足 Ai e {1，2，...，N}且Ai古隊，初始化j=l ；
[0037](7)從集合A取出Aj;
[0038](8)如果G'、= I，則執行步驟10，否則執行步驟9 ；
[0039](9)對、賦值為1，對賦值為I ;
[0040](10) j值加I ;如果j> (M-NUM)執行步驟11，否則執行步驟7 ；
[0041](11)修改NUM為矩陣G中第i列中I的個數；
[0042](12)如果NUM〈M則執行步驟6否則執行步驟13 ；
[0043](13) i的值加I ;如果i>N，執行步驟4，否則執行步驟14 ；
[0044](14)矩陣G中記錄了一個完整的隨機網絡拓撲結構，程序結束。
[0045]其具體實施模式是這樣的:
[0046]首先生成網絡結點數N，然後對於每個結點生成一個隨機數M，表明該結點與M個結點之間存在連接通路，對於每一個網絡結點，隨機生成M個結點，若生成的結點中與該結點的值相同則重新生成，否則查看記錄網絡拓撲的矩陣中，是否已存在一條相同的連接，如果已存在則默認已有連接，不再重新生成，這樣是為了保證最後生成的網絡拓撲中不存在自連接和雙向連接，最後將合法的連接影射記錄入拓撲矩陣，這樣便使用矩陣記錄了一個完整的隨機網絡拓撲結構。
【權利要求】
1.一種基於結點連接的隨機網絡拓撲結構生成方法，其特徵在於:本發明的目的是這樣實現的:設生成隨機整數N為網絡拓撲中網絡結點的數目，遍歷每一個結點，為每一個結點生成隨機數M,表示該結點與M個結點有連接，M〈N ;使用N*N維矩陣G記錄網絡結點連接關係的拓撲圖，矩陣中元素Gu，I ^ i, j ^ N的值為O或者1，O表示網絡結點i和結點j不存在連接通路，I表示網絡結點i和結點j之間存在連接通路，任意兩個結點件只保留一條直接連接通路；初始化矩陣G，使得矩陣G中所有元素的值為O ;對網絡中的每個結點Ni,生成隨機數M表示Ni將與M個結點進行連接,隨機生成M個整數組成集合A= (A1,…，AmI ,滿足Ai e {I, 2,...,N}且Ai古Ni ;這樣最終生成矩陣G表示優化的網絡拓撲，模擬生成了一種基於結點連接的隨機網絡拓撲； 具體步驟為: (1)用戶輸入隨機網絡結點數目N，表示隨機網絡結點集合位N=汍，N2,,NJ ; (2)初始化生成N*N維零矩陣G，G中元素均為O，用於描述網絡拓撲結構； (3)初始化i=l； (4)生成隨機數M，M〈N;
(5)NUM=O； (6)隨機生成M-NUM 個隨機數集合 A=M1, A2,, Am_nJ，滿足 Ai e {1，2，...，N}且Ai古隊，初始化j=l ； (7)從集合A取出Aj; (8)如果=I，則執行步驟10，否則執行步驟9 ； (9)對Gw賦值為1，對6 ~賦值為I ; (10)j值加I ;如果j> (M-NUM)執行步驟11，否則執行步驟7 ； (11)修改NUM為矩陣G中第i列中I的個數； (12)如果NUM〈M則執行步驟6否則執行步驟13； (13)i的值加I ;如果i>N，執行步驟4，否則執行步驟14 ； (14)矩陣G中記錄了一個完整的隨機網絡拓撲結構，程序結束。
【文檔編號】H04L12/751GK103457859SQ201310395170
【公開日】2013年12月18日 申請日期:2013年9月3日 優先權日:2013年9月3日
【發明者】姚文斌, 韓司, 盧亮 申請人:北京郵電大學