[發明專利]一種基于模擬退火算法的多自主體網絡容侵能力評估方法

有效

• 申請號: 201910421411.0
• 申請日: 2019-05-21
• 公開（公告）號: CN110278108B
• 公開（公告）日: 2021-10-29
• 發明（設計）人: 伍益明;徐明;鄭寧;王廣;喬通
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 杭州君度專利代理事務所(特殊普通合伙) 33240
• 代理人: 楊舟濤

本發明公開了一種基于模擬退火算法的多自主體網絡容侵能力評估方法，本發明將模擬退火技術應用于網絡容侵能力評估領域，同時在傳統的模擬退火方法上綜合考慮了在網絡健壯性計算子集對更新時引入了三種備選狀態，使得子集對更新具有更大采樣隨機性。本發明具有克服大規模多自主體網絡容侵能力評估因NP難問題而無法求解的優點。

技術領域

本發明涉及網絡容侵能力評估技術領域，特別是一種基于模擬退火算法的多自主體網絡容侵能力評估方法。

背景技術

多自主體系統是指具備感知、通信、計算和執行能力的多個自主體組成的大規模網絡系統，被廣泛用作分布式協同算法的實現載體。多自主體系統不僅具備一般分布式系統所具有的資源共享、協調性好、自主性強等優點，而且由于各個自主體通過協調合作能夠解決大規模的復雜性問題，使其具備很強的魯棒性與可靠性。然而近些年，隨著網絡安全風險日益突出，網絡設計者在構建多自主體系統過程中對其網絡容侵能力的評估也越來越重視。網絡拓撲(r,s)-健壯性是目前一種衡量多自主體網絡容侵能力的有效指標。

現有的對網絡拓撲健壯性評估方法如窮舉、圖構建、線性規劃、函數關系等，對其(r,s)兩個數值的評估，都是通過窮舉和遍歷算法來求得的，這類方法需要獲取網絡通信拓撲全局的鏈路信息。然而已有文獻證明，對健壯性中的數值對(r,s)評估判定是一個NP難問題。因而上述傳統方法僅適用于節點數目較少的小型多自主體網絡，對于節點數目眾多的大規模網絡，均無法適用。

發明內容

本發明為克服現有評估技術的不足，提供了一種較為簡明、易于實現并且適用于節點數目眾多的大規模多自主體系統的網絡容侵能力評估方法。

本發明解決其技術問題所采用的技術方案是：

一種基于模擬退火算法的多自主體網絡容侵能力評估方法，包括以下步驟：

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

2)獲取初解：在節點集V中隨機產生一對非空不相交子集對S₁,S₂，進行健壯性計算f(A(D)，S₁，S₂，r_min，s_min)，得到子集對S₁,S₂滿足的最優健壯性數值(r，s)；

3)產生新解：更新子集對S₁,S₂形成新的子集對S’₁，S’₂，再次進行健壯性計算f(A(D)，S’₁，S’₂，r_min，s_min)，得到子集對S’₁，S’₂滿足的最優健壯性數值(r’，s’)；

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

Metropolis準則包括以下步驟：