[發明專利]基于無尺度網絡的路由級拓撲建模方法

有效

• 申請號: 201210356951.3
• 申請日: 2012-09-21
• 公開（公告）號: CN102904815A
• 公開（公告）日: 2013-01-30
• 發明（設計）人: 陳鵬
• 申請（專利權）人: 中國電子科技集團公司第二十八研究所
• 主分類號: H04L12/751
• 分類號: H04L12/751
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 柏尚春

1.一種基于無尺度網絡的路由級拓撲建模方法，其特征在于，包括：

在初始路由級拓撲上，根據無尺度網絡的增長和擇優連接特性，將新增節點連接到已經有較多連接的舊有節點上，使路由級拓撲中的節點呈現冪律分布；

根據功能和組織關系按節點種類將路由級拓撲中節點分為核心層core、葉子層leaf和主體層main三層；所述核心層為最內圈承擔骨干互聯的節點，所述葉子層為最外圈只具有對上連接的節點；除核心層和葉子層以外的層次稱為主體層，主體層可繼續細化拆解為多個層次；

把路由級拓撲壓扁到一個平面上后，利用雷達圖進行連接象限的劃分；所述象限內部可繼續細化拆分；

對于路由級拓撲，使其所有節點呈現冪律分布的同時，還需按比率向各個層次/象限增加新節點，即根據權重進行概率計算來決定新增節點的歸屬區域；所述節點在各層次、各象限中的數目分布有對應的比率，即該區域中的節點數與節點總數的比值，稱之為權重。

2.如權利要求1所述的基于無尺度網絡的路由級拓撲建模方法，其特征在于：所述初始路由級拓撲的建立和在路由級拓撲中按比率向各個層次/象限增加新節點的具體步驟為初始化算法步驟和循環算法步驟；

初始化算法步驟：

(11)按層次每個象限依序號產生m₀個節點，重復步驟L×Q次；

(12)核心層每個初始化節點依序號順序連接m個同層節點；

(13)主體層初始化節點與上級(L-1)Q區域中節點建立δ(δ≥1)條連接，與同一LQ內節點建立m-δ條連接；其中，第L層Q象限所在區域簡稱LQ；

(14)葉子層初始化節點對上級(L-1)Q區域節點建立1或m條連接，結束初始化算法；

其中，L為節點是層數，Q為象限數，m為新增節點與舊有節點的新建連接數，m₀為每個LQ中的初始節點數，m<m₀，δ為主體層節點與上級節點的連接數。

循環算法步驟：

(21)投入新節點n，以wL為概率，判斷本次投點歸屬的層次；若新點歸屬核心層，跳轉步驟(23)，若歸屬主體層，跳轉步驟(27)；若歸屬葉子層，跳轉步驟(29)；

(22)以wQ為概率，判斷新節點n歸屬的象限；

(23)產生一個隨機數，作為新節點本次的連接概率p′；

(24)從核心層中隨機選取節點i，按照公式(1)計算p(ki)；

p(ki)=ki1+ϵ/Σjkj1+ϵ---(1)]]>

(25)比較p(k_i)與p′，若p(ki)>p′則連接n、i，若p(k_i)<p′則不進行連接；

(26)重復步驟(23)~(25)完成m次連接；

(27)產生隨機數p′，在對上級(L-1)Q內節點隨機選取節點i計算p(ki)，按步驟(25)進行判定并重復δ次；

(28)產生隨機數p′，對同LQ內節點隨機選取節點i計算p(ki)，按步驟(25)進行判定并重復m-δ次；

(29)產生隨機數p′，在對上級(L-1)Q內節點隨機選取節點i計算p(ki)，按步驟(6)進行判定并重復1或m次；

(30)重復(21)~(29)步驟N次；

其中，N為基于無尺度網絡的路由級拓撲的節點總數，wL為層次的權重，wQ為象限的權重。