一种基于双层信息流传递的网络关键点分析方法

1.一种基于双层信息流传递的网络关键点分析方法，其特征在于，包括以下步骤：步骤1，获取基于图结构的双层网络数据，根据所述网络数据构造双层信息流传递网络；所述信息流传递网络包含节点阻断增加的第一传输时延以及边阻断增加的第二传输时延；步骤2，对所述双层信息流传递网络进行预处理，根据所述第一传输时延和所述第二传输时延建立网络攻击方以传输时间最长为目标的第一优化目标函数和网络运营方的以传输时间最短为目标的第二优化目标函数；步骤3，根据所述第一优化目标函数和所述第二优化目标函数构建博弈模型，所述博弈模型为二层规划模型，内层为所述网络运营方寻找基于信息流传递时间的最短路径，外层为所述网络攻击方寻找最大化内层最短路径的阻断方案；步骤4，考虑双层网络的关联关系，根据所述博弈模型得到所述网络攻击方角度的双层网络信息流阻断模型，将所述双层网络信息流阻断模型中的阻断节点确定为网络关键节点；所述双层网络信息流阻断模型如式(1)所示：式中，Z是最大化上层逻辑网络信息传递最短时延，y (i,j) 是上层逻辑网络的边，c (i,j) 是上层逻辑网络路径的时延，w (i,j) 是下层物理网络路径的时延，q (i,j) 是下层物理网络攻击后增加的时延，e (i,j) 是下层物理网络路径的时延，x (i,j) 网络攻击方要攻击的路径，E up 是上层逻辑网络路径集，N up 是上层逻辑网络节点集，E down 是下层物理网络路径集，N down 是下层物理网络节点集；所述双层网络信息流阻断模型的求解算法为基于局部贪心算法求解，分多个步骤分别求解阻断方案，每个步骤求解最优结果作为局部最优方案，将每个步骤的方案合并得到整体阻断方案。 2.根据权利要求1所述的一种基于双层信息流传递的网络关键点分析方法，其特征在于，所述双层网络包括上层逻辑网络和下层物理网络，其中，所述上层逻辑网络包括感知网络、融合网络、指控网络以及火力网络，信息流依次从感知网络、融合网络、指控网络最终传递到火力网络；所述上层逻辑网络的边是虚拟边，其信息流传递依赖于下层物理网络且任一节点对应一个或多个下层物理网络节点；上层逻辑网络两点之间的信息流传递通过下层物理网络对应节点之间的信息流传递实现。 3.根据权利要求1所述的一种基于双层信息流传递的网络关键点分析方法，其特征在于，步骤2中，所述建立网络攻击方以传输时间最长为目标的第一优化目标函数和网络运营方的以传输时间最短为目标的第二优化目标函数中，网络运营方选择信息流传输时间最短的路径，所述网络运营方的目标函数如式(2)所示：式中，D (i,j) 是边(i,j)的第二传输时延，D k 是节点k的第一传输时延，y (i,j) 是网络运营方信息流传输路径中的边，y k 是网络运营方信息流传输路径中的节点，网络攻击方的目标是最大化网络运营方的信息流传输时间，所述网络攻击方的目标函数如式(3)所示：式中，d (i,j) 是边(i,j)被阻断后所增加的第二传输时延，d k 是节点k被阻断后所增加的第一传输时延，x (i,j) 是网络攻击方选择阻断的边，x k 是网络攻击方选择阻断的节点。 4.根据权利要求1所述的一种基于双层信息流传递的网络关键点分析方法，其特征在于，步骤3中，所述根据所述第一优化目标函数和所述第二优化目标函数构建博弈模型包括：构建问题场景：网络运营方选择感知网络任意节点和火力网络任意节点分别作为信息流传递的起点和终点，选择最短路径进行信息流传递，网络攻击方通过对网络关键节点进行攻击从而阻断信息流传递，并最大化起点到终点之间的最短路径；在该场景下，网络运营方要实现的是信息流从起点到终点的最短路径传递，网络攻击方要实现的则是阻断网络运营方的信息流传递，即最大化网络运营方的最短路径。 5.根据权利要求4所述的一种基于双层信息流传递的网络关键点分析方法，其特征在于，所述博弈模型的目标函数如式(4)所示： 6.根据权利要求1所述的一种基于双层信息流传递的网络关键点分析方法，其特征在于，基于局部贪心算法求解所述双层网络信息流阻断模型的算法问题，分多个步骤分别求解阻断方案，每个步骤求解最优结果作为局部最优方案，将每个步骤的方案合并得到整体阻断方案；将信息流传递的过程分为三个阶段：第一阶段，感知网络-融合网络；第二阶段，融合网络-指控网络；第三阶段，指控网络-火力网络；第一阶段只有起点，没有终点，在融合网络中加入一个虚拟节点作为终点，融合网络中的每个节点都生成流向虚拟节点的边，可转化为单层网络信息流阻断模型的算法问题；第一阶段的终点作为第二阶段的起点，同样在指控网络中生成虚拟节点作为终点；而第二阶段的终点作为第三阶段的起点；每个阶段分别调用求解单层网络信息流阻断模型的算法求得局部最优解，合并局部最优的解拟作为最终解。 7.根据权利要求6所述的一种基于双层信息流传递的网络关键点分析方法，其特征在于，基于本德斯分解算法求解所述单层网络信息流阻断模型的算法问题，并将所述算法问题分解为两个互斥的子问题，对两个所述子问题分别进行求解，据此得到分解规划模型如式(5)所示：式中， 是分解所得子问题，用于求解在阻断方案向量 下起点到终点的最短路径，输入是网络攻击方的阻断方案向量 输出是最短路径向量 和函数值z，如果函数值z大于算法的下界z down ，则更新算法的下界z down ，令z down ＝z； 是分解所得主问题，用于求解在最短路径集合 中使得传输时延最大的阻断方案，输入为最短路径方案 的集合 输出为阻断方案 和目标函数值Z，如果函数值Z小于算法的上界z up ，则更新算法的上界z up ，令z up ＝Z；所述 和 两个问题交替迭代求解，并不断更新算法上下界z up 和z down ，当z up 与z down 相等时，表示网络运营方所能选取的最短路径和时延和网络攻击方阻断下的最短路径一致，得到网络攻击方的阻断方案最优解x * ，在该阻断方案下网络运营方的最短路径y * ，以及此时的最短路径传输时延z＝Z＝z down ＝z up 。 8.根据权利要求7所述的一种基于双层信息流传递的网络关键点分析方法，其特征在于，求解所述单层网络信息流阻断模型的算法single-model(G2,s,X,R)进一步包括：步骤11，初始化参数： z down ←-∞；z up ←∞；步骤12，对子问题 进行求解，输出最短路径向量 目标函数值 如果 如果z down ＝z up ：则跳转至步骤14；步骤13，对主问题 进行求解，输出阻断方案向量 目标函数值 如果z up ＞z down ：则跳转至步骤12；步骤14，x * ←x down ，输出并返回结果，阻断方案下的最短路径时延 阻断方案x * 。 9.根据权利要求8所述的一种基于双层信息流传递的网络关键点分析方法，其特征在于，求解所述双层网络信息流阻断模型的算法，即double-model(G2,s,X,R)进一步包括：步骤21，加入虚拟节点：V←X；加入第一阶段虚拟边：E←Y (B,X) ；调用单层网络阻断求解算法：single-model(G2,s,X,R)并获取该阶段最短路径终点X的前驱节点作为下一阶段起点：s1；步骤22，删除第一阶段虚拟边：deleteY (B,X) from E；加入第二阶段虚拟边：E←Y (C,X) ；调用单层网络阻断求解算法：single-model(G2,s1,X,R)并获取下一阶段起点：s2；步骤23，deleteY (B,X) from E；delete X from V；调用单层网络阻断求解算法：single-model(G2,s2,X,R)。