[發明專利]基于對偶算法的備份網絡最短路阻斷方法和裝置

有效

• 申請號: 202210043448.6
• 申請日: 2022-01-14
• 公開（公告）號: CN114401137B
• 公開（公告）日: 2023-09-08
• 發明（設計）人: 朱先強;戴周璇;陸敏;朱承;周鋆;劉斌;張維明;丁兆云;黃松平
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: H04L9/40
• 分類號: H04L9/40;H04L41/14;G06F30/20
• 代理公司: 長沙國科天河知識產權代理有限公司 43225
• 代理人: 趙小龍

1.基于對偶算法的備份網絡最短路阻斷方法，其特征在于，包括：

根據節點網絡的最短路阻斷問題，建立網絡模型；所述網絡模型中攻擊方目標為在有限資源時阻斷所述節點網絡中的網絡鏈路以最大化防御方的最短路徑，防御方目標為在節點網絡中尋找由起始節點到目標節點的最短路徑；

根據所述節點網絡，建立備份網絡，以及根據所述備份網絡和所述網絡模型，得到備份網絡模型；所述備份網絡模型中節點網絡受到攻擊方阻斷后，防御方根據當前網絡狀態激活啟用備份網絡中的備份鏈路，以最小化攻擊方的攻擊效果；

根據所述備份網絡模型中的約束條件和優化目標，構建備份激活最短路阻斷模型；

基于對偶算法，對所述備份激活最短路阻斷模型進行求解；

根據所述節點網絡，建立備份網絡，以及根據所述備份網絡和所述網絡模型，得到備份網絡模型包括：

所述網絡模型包括多個節點，節點之間形成網絡鏈路，從所述網絡模型中提取鏈路備份構成所述備份網絡，根據所述網絡模型和所述備份網絡，得到備份網絡模型；

其中，備份網絡定義為G(N，A)，N＝{1，2，...，}表示節點集合，A＝{(i，j)|i，j∈N}表示網絡鏈路的集合，B＝{(i，j)|i，j∈N}表示鏈路備份的集合，B是A的真子集，i，j表示節點編號；

根據所述備份網絡模型中的約束條件和優化目標，構建備份激活最短路阻斷模型包括：

∑_k∈Sq_kz_k≤Q

式中：s表示起始節點，t表示目標節點；c_k表示鏈路k∈A的長度；r_k表示攻擊方阻斷鏈路k需要的阻斷資源，R表示阻斷資源總量；q_k表示防御方激活鏈路k需要的備份激活資源，Q表示備份激活資源總量；FS(i)表示節點i的出邊集合，RS(i)表示節點i的入邊集合；x_k為攻擊方阻斷變量，y_k為防御方路徑選擇變量，z_k為防御方備份激活變量，d_k表示當鏈路k被阻斷時其增加的長度；

所述對偶算法包括：

將所述備份激活最短路阻斷模型轉化為最小化問題并以向量形式標準化：

其中，y和z是內層路徑選擇變量和備份激活變量的向量形式，y_s是標準化時生成的非負剩余變量；T₁和T₂分別是形狀為[n*m]，[(m-l)*m]的分塊系數矩陣，n是網絡中節點數量，m是網絡中鏈路數量，l是網絡中備份鏈路數量；I₁，I₂，I₃是形狀為[m*m]的單位矩陣；a₁是系數向量，b是常數向量；

將所述內層最小化問題對偶并轉化為單層的優化問題：

ω₁,ω₂,ω₃,ω₄≥0

其中，ω為對偶變量，滿足關系b^Tω＝c^Ty。

2.根據權利要求1所述的方法，其特征在于，在基于對偶算法，對所述備份激活最短路阻斷模型進行求解之前，還包括：

對所述備份激活最短路阻斷模型進行轉換，得到形式化表述：

∑_k∈Ar_kx_k≤R

∑_k∈Sq_kz_k≤Q

3.根據權利要求1或2所述的方法，其特征在于，所述網絡模型和所述備份網絡模型均包括多個節點，所述節點之間形成網絡鏈路或者備份鏈路，所述網絡鏈路或者所述鏈路備份均具有鏈路代價。