[發(fā)明專(zhuān)利]一種基于模擬退火算法的多自主體網(wǎng)絡(luò)容侵能力評(píng)估方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201910421411.0
• 申請(qǐng)日: 2019-05-21
• 公開(kāi)（公告）號(hào): CN110278108B
• 公開(kāi)（公告）日: 2021-10-29
• 發(fā)明（設(shè)計(jì)）人: 伍益明;徐明;鄭寧;王廣;喬通
• 申請(qǐng)（專(zhuān)利權(quán)）人: 杭州電子科技大學(xué)
• 主分類(lèi)號(hào): H04L12/24
• 分類(lèi)號(hào): H04L12/24
• 代理公司: 杭州君度專(zhuān)利代理事務(wù)所(特殊普通合伙) 33240
• 代理人: 楊舟濤

1.一種基于模擬退火算法的多自主體網(wǎng)絡(luò)容侵能力評(píng)估方法，其特征在于：包括以下步驟：

1)條件設(shè)置：采用圖論中的節(jié)點(diǎn)表示多自主體，圖論中的邊表示自主體之間的通信鏈路；給定有向圖D＝(V,E)，其中V為節(jié)點(diǎn)集合，E為邊集；令A(yù)(D)為有向圖D的鄰接矩陣，再給定初始溫度為T(mén)₀，終止溫度為T(mén)_f，降溫溫度為ΔT，迭代次數(shù)q，令實(shí)時(shí)溫度T_t為初始溫度T₀；設(shè)置初始健壯性數(shù)值為(r_min，s_min)；令r_min＝min{δⁱⁿ(D)，[n/2]}，s_min＝n，其中δⁱⁿ(D)表示有向圖D的最小入度，n表示有向圖中的節(jié)點(diǎn)個(gè)數(shù)；

2)獲取初解：在節(jié)點(diǎn)集V中隨機(jī)產(chǎn)生一對(duì)非空不相交子集對(duì)S₁,S₂，進(jìn)行健壯性計(jì)算f(A(D)，S₁，S₂，r_min，s_min)，得到子集對(duì)S₁,S₂滿(mǎn)足的最優(yōu)健壯性數(shù)值(r，s)；

子集對(duì)滿(mǎn)足的最優(yōu)健壯性計(jì)算方法包括：

(2.1)已知n表示圖D節(jié)點(diǎn)個(gè)數(shù)，令r＝r_min，s＝s_min；

(2.2)假如健壯性值r＞0，則進(jìn)行健壯性有效函數(shù)RobustHolds(A(D)，S₁，S₂，r，s)判定；如果判定結(jié)果為真，那么當(dāng)前健壯性數(shù)值(r，s)即為節(jié)點(diǎn)子集對(duì)S₁,S₂滿(mǎn)足的最優(yōu)健壯性值；如果判定結(jié)果為假，則健壯性數(shù)值s減小1，值r不變；當(dāng)值s減至0時(shí)，健壯性值r減小1，值s變?yōu)閚；假如值r＝0，運(yùn)算結(jié)束；

步驟(2.2)關(guān)于RobustHolds判定的方法主要包括以下步驟：

(2.2.1)計(jì)算非空子集S₁中有入度鄰節(jié)點(diǎn)數(shù)大于等于r個(gè)的節(jié)點(diǎn)數(shù)，記k₁；

(2.2.2)計(jì)算非空子集S₂中有入度鄰節(jié)點(diǎn)數(shù)大于等于r個(gè)的節(jié)點(diǎn)數(shù)，記k₂；

(2.2.3)當(dāng)k₁＝S₁或者k₂＝S₂或者(k₁+k₂)＝s時(shí)，RobustHolds判定為真，否則判定為假；

3)產(chǎn)生新解：更新子集對(duì)S₁,S₂形成新的子集對(duì)S’₁，S’₂，再次進(jìn)行健壯性計(jì)算f(A(D)，S’₁，S’₂，r_min，s_min)，得到子集對(duì)S’₁，S’₂滿(mǎn)足的最優(yōu)健壯性數(shù)值(r’，s’)；

4)將初解與新解進(jìn)行比較計(jì)算，記Δr＝(r’-r)×n+(s’-s)；假如新解優(yōu)于初解，即Δr＜0，直接接受新解(S’₁，S’₂，r’，s’)；如果新解劣于初解，即Δr≥0，按照Metropolis準(zhǔn)則接受新解(S’₁，S’₂，r’，s’)；

Metropolis準(zhǔn)則包括以下步驟：

(4.1)生成隨機(jī)數(shù)ξ∈U(0,1)；

(4.2)假如exp(–Δr/Tt)ξ，接受新解(S’₁，S’₂，r’，s’)；否則保持初解(S₁，S₂，r，s)；

5)(r_min，s_min)數(shù)值更新：假如步驟4)中得到結(jié)果為新解，那么令r_min＝r’，s_min＝s’；假如步驟4)中得到結(jié)果為初解，那么令r_min＝r，s_min＝s；

6)當(dāng)?shù)螖?shù)達(dá)到設(shè)定上限時(shí)，實(shí)時(shí)溫度降低ΔT，即T_t←T_t-ΔT，轉(zhuǎn)步驟7)；否則轉(zhuǎn)步驟2)；

7)當(dāng)實(shí)時(shí)溫度T_t大于算法終止溫度T_f時(shí)，轉(zhuǎn)步驟2)；否則運(yùn)算結(jié)束。

2.根據(jù)權(quán)利要求1所述的一種基于模擬退火算法的多自主體網(wǎng)絡(luò)容侵能力評(píng)估方法，其特征在于：步驟3)中，子集對(duì)S1和S2的更新方法包括：

(3.1)初始化S₁的鄰居集合S_neighbors；

(3.2)生成隨機(jī)數(shù)ξ∈U(0,1)；當(dāng)隨機(jī)數(shù)ξ小于1/3時(shí)，從S₁中隨機(jī)挑選一個(gè)節(jié)點(diǎn)替換為從S_neighbors中隨機(jī)挑選出的一個(gè)節(jié)點(diǎn)；當(dāng)隨機(jī)數(shù)ξ大于等于1/3并且小于2/3時(shí)，從S_neighbors中隨機(jī)挑選一個(gè)節(jié)點(diǎn)添加到集合S₁中；當(dāng)隨機(jī)數(shù)ξ大于等于2/3并且小于1時(shí)，隨機(jī)從S₁中刪除一個(gè)節(jié)點(diǎn)；

(3.3)從集合S₁的差集進(jìn)行采樣獲取新的S₂集合。