[發明專利]面向定向阻斷的交通網絡關鍵節點選擇方法

有效

• 申請號: 202210729051.2
• 申請日: 2022-06-24
• 公開（公告）號: CN115102894B
• 公開（公告）日: 2023-08-04
• 發明（設計）人: 石建邁;黃金才;顧介行;劉忠;程光權;陳超;孫博良
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: H04L45/00
• 分類號: H04L45/00;H04L45/02;H04L45/12
• 代理公司: 長沙大珂知識產權代理事務所(普通合伙) 43236
• 代理人: 伍志祥

1.一種交通網絡關鍵節點選擇方法，其特征在于，包括以下步驟：

步驟1，提取面向定向阻斷的交通目標子網；

步驟2，建立面向定向阻斷的交通目標選擇模型；

步驟3，基于費效比的啟發式搜索算法求解交通目標選擇模型；

步驟4，獲得目標選擇序列；

所述的交通目標選擇模型為：

s.t.

公式(1)為目標函數，表示最小化摧毀目標節點集合的總體資源消耗，其中V＝{1，2，…，n}表示目標節點集合；x_i為決策變量，如果選擇節點i∈V作為打擊目標則取值為1，否則取值為0；C_i表示打擊節點i所消耗的資源；Z表示總體資源消耗；約束(2)確保前k短路中每條路徑上至少有一個節點被選為打擊目標，其中集合K＝{1，2，…，k}表示前k短路集合；a_ik表示第k短路是否包含節點i，當a_ik等于1時，表示包含，當a_ik等于0時，表示不包含，V_k表示第k短路包含點集合；公式(3)約束了決策變量x_i的取值范圍；

所述的基于打擊費效比的啟發式搜索算法以節點出現在前k短路的次數與打擊該節點所消耗的費用的比值作為節點重要度指標，節點i的費效比RCE_i計算公式如下：

所述的啟發式搜索算法具體包括以下步驟：

Step301：判斷集合K是否為空，如果其中仍有可行路徑，則選擇集合K中的最短路徑j∈K，計算路徑j包含的節點集合A_j；若集合K為空，結束程序；

Step302：計算節點集合A_j中所有節點的費效比，并選擇打擊費效比最高的節點i∈A_j；

Step303：判斷節點i是否為起點或者為終點，若是則選擇費效比第二高的節點，并再次判斷Step303；

Step304：添加節點i至最優選節點集合，并對集合K中所有路徑依次判斷是否包含節點i，刪除所有包含節點i的路徑，而后繼續Step301；

所述的交通目標子網為前k條最短路所包含路徑組成的子網絡，交通目標子網的提取過程包括以下步驟：

Step101：初始化：起點s，終點d，交通網絡中存在的可行路徑不得超過的路徑長度閾值θ，k＝1；

Step102：計算從節點s到節點d的最短路徑，長度標記為p_k，k＝1；

Step103：如果p_k小于既定的路徑長度閾值θ，則將該路徑加入組成所需子網的候選路徑集合，否則結束程序；

Step104：設第k路徑上有Q_k個節點，依次對于第k路徑上的第i＝1，2，...，Q_k-1個節點，假設第i點到第i+1點不可達，即d_iq＝∞，q＝i+1，d_iq表示節點i到節點q的距離，計算第i節點到終點d的最短路徑，此時第i節點稱作偏離節點，第i節點到終點d的最短路徑稱為偏離路徑，循環結束后恢復d_iq原值；

Step105：通過Step104計算的Q_k-1條偏離路徑，可得Q_k-1條從起點s到終點d的可行路徑，選擇其中最短的一條路徑，即為第k+1條最短路，長度為p_k+1，令k＝k+1，返回Step103。