Apr. 2021Vol. 42 No. 4
2021年4月 第42卷第4期
计算机工程与设计
COMPUTER ENGINEERING AND DESIGN
吴嫣媛，刘向军+
（华北电力大学电气与电子工程学院，北京102206）
摘 要：针对传统的关键节点识别方法以网络的一种或几种特征作为判定指标，存在片面性而不能普遍适用，且识别过程 中很少考虑网络的动态特性的问题，提出采用优化算法进行网络关键节点识别，考虑网络的动态性-入网络级联失效模
型，基于此构造网络鲁棒性测度用以衡量网络性能，以此为目标函数，采用以佳点集、趋化行为及列维飞行策略改进的人
工鱼算法进行优化搜索。实验分析结果表明，所提方法识别效果相比传统关键节点识别方法更为有效和优越，改进人工 鱼算法相比此领域已采用的传统智能算法效果更佳。
关键词：复杂网络；关键节点；级联失效；鲁棒性；改进人工鱼算法中图法分类号：TP393. 02
文献标识号：A 文章编号：1000-7024 （2021） 04092007
doi ： 10. 16208/j. issnl 000-7024. 2021. 04. 004
Identification of key nodes in wireless sensor networks
considering cascading failure
WU Yan-yuan , LIU Xiang-jun +
(School of Electrical and Electronic Engineering, North China Electric Power University, Beijing 102206, China)
Abstract : Aiming at the problems that the traditional key node identification methods use one or several characteristics of the net
work as the determination index, which is one-sided and cannot be universally applied, and the dynamic characteristics of the net works are rarely considered during the identification process, using optimization algorithm to identify the key nodes of the net works was proposed. Considering the dynamic properties of the network, a cascading failure model of the network was intro
duced, based on which a network robustness function to measure network performance was constructed. Using the robustness as Rheobjecivefuncion &animprovedarificialfishschoolalgorihm whichwasimprovedRhroughRhegoodpoinRseR &chemoRacic
behavior &andLevyflighRsRraRegywasusedforopimizedsearch. ExperimenRalanalysisresulsshowRhaRRheproposedmeRhod smoree f eciveandsuperbRhanRheRradiionalkeynodeidenificaionmeRhods &andRheimprovedarificialfishswarmalgorihm
smoree f eciveRhanRheRradiionalinRe l igenRalgorihmsRhaRhavebeenusedinRhisfield.
Keywords ： complex network ； key nodes ； cascading failure # robustness ； improved artificial fish swarm algorithm
2引言
目前对复杂网络节点重要性判断方法都是针对具体问
题提出的，存在一定的片面性和局限性，且会随着网络结
构的变化使识别结果存在一定误差13+
。文献*, 5］指出 了这种缺点，进而引入优化理论来进行关键节点识别，从
攻击的角度通过节点失效后网络性能下降的方法来确定节 点的重要性，以网络性能最小为目标采用禁忌搜索算法得 到节点排序，使得识别方法适用于不同结构与类型的网络。
但文献［4, 5］在构建网络抗毁性测度衡量网络性能时,
假设一个节点的失效不会影响其它节点，没有考虑拓扑结
构的改变导致网络中物质流的变化，不能很好地反映真实 的节点重要程度。文献［6-8］在计算节点失效后的网络性 能测度时引入了级联失效过程，很好地切合了实际网络的
这种动态特征。因此在关键节点识别过程中计算鲁棒性测
度衡量网络性能时，应当考虑网络级联失效过程。同时文
献［4, 5］采用的禁忌搜索算法是一种基于单点搜索的元 启发式算法，且具有对初始解依赖性较强、多样性不足
等缺点。
优化算 复杂 络的 键 识 &在
收稿日期：2020-01-17；修订日期：2020-06-04
作者简介：吴嫣媛（1995 -），女，广东茂名人，硕士研究生，研究方向为智能信息处理、复杂网络；+通讯作者：刘向军（1970-），女,
河北唐山人，博士，副教授，研究方向为智能信息处理、复杂网络、电气信息技术’E-mail ： *******************
第42卷第4期吴嫣媛，刘向军：考虑级联失效影响的复杂网络关键节点识别・921・
此基础上，考虑网络的动态性引入级联失效模型改进网络
鲁棒性测度&并禁忌算法的缺点&改进人工鱼
算法作为序列构造模型的求解算法，最
策略识别的关键 在络上的，验证策
略的和优越性。
1级联失效模型
受制于硬件成本，每个节点都具有给定的负载容纳能
力。最初，网络稳定状态，其中每个的负载-
容量。的故障，网络受到了干扰&故障改
络中流量的平衡，负载将重新分配给&并可能进
一致过载，并足起整个系统故障。级联失的是网络的动态特性，网络构的改变造成络的重新分配，此过程描述910+：
任何一个网络可由图G%(V,E)作抽象表示。V(G)是有限非空集，V中元素称为G的顶点，N%|V|表示网络中的，E(G)是V(G)中顶的边的。在很情况下，常直接或稍加作为真，量的近似值，网络的实时流量
BCx%%((E*(1) +()用于表示节点的流量o g*()定义为从节点*到*经过节点(的最短路径的o g*是从节点*到*的所有最短路。此外，自身的F也是总负载的重要部分。&(在时间f的负载为
()%F+$g*((丨g*⑵其中，表示在时间?(的总负载，L为节点(的自载。络的承载&将载的上限定义为容量G&是节点过载和性能降低
理的最大负载，用时间?=0时的负载L(()乘以容忍系数丁表示
C p%T・L((0),(%1,2,…,N(3)其中，T,1。当在时间？一1处节点(的流量负载超过C p 时，在时间？将过载。以一的随机网络为例说明这个过程，令N'100，随机移除10个节点，负载变化图1所示。以44号节点为例，网络结构发生变化载约为的1.597倍，倘若T这个数目，过载失效，其余负载增大的&从而引发新一轮负载的化。
2基于级联失效的鲁棒性测度
网络性能常用抗毁性测度衡量&通常被定义为*个节点被移，其最通分量的的变化*+。文献［11］络级失特&级失&最通分
衡络受损性能。级联失效改进网络鲁棒性测度。假使网络G中有n个，标号分别为
图1随机网络中移除10个节点负载变化
1〜n，则一个节点序列可表不为("1&2,…,"n)，是节点的一个排序。按照节点排序K%11,"2,…,"n2去逐个攻击网络G中的&当失效&执行上一型描述的级联失效过程。随的失效&该网络在失的鲁棒性R可以定义为
n
RB,K)%$C()(4)
*%1
其中，C()表示网络G中*个节点遭到攻击，网络负载重分配完毕或级联失效过程络的最通分量。R(G K)越随失越说明
络在这些节点失越容易遭到破坏&越重要&识别方法越准确。
3基于改进人工鱼算法的关键节点识别
3.1求解模型与基本人工鱼算法
基于优化理论键识别&目标是构造岀节点失络鲁棒R(G K)最重的序K R(G,K)越小，说明当节点序列K失效时网络越容易崩溃。构造方为一个优化问题$5］。
min R(G K)2⑸
其中，St_K是所有节点序列构成的集合。
复杂网络是庞大的，其中可能包括上百甚至上千上万个，这种情况序列是一个［模计算问题&人工鱼算法(AFSA)在问题中具能优化算法无的优势。目前将人工鱼算优化问题已在诸多领域取得良好效果。人工鱼算法具的局最优能力，并拥参数选感、鲁棒明显优势，已被证实相一
的智能算能更为优越*3］。&人工鱼算作为键识的优化算&并改
假设在D维的目标搜索空间中，存在着由S条人工鱼组成的种。人工鱼个体的状态可以表示为向量X%(1,(2,
•922•计算机工程与设计2021年
…，/&每个人工鱼的状态都代表一个可替代的解决方案，代表一个节点序列，两个人工鱼之间的距离用欧几里得距离0=%||X*—X,||表示，多种人工鱼共存并合作以寻求最佳解决方案。当前人工鱼位置的食物浓度为目标函数值丫。
(1)觅食行为：人工鱼的感知距离范围Vi：内随机选择一个新位置，向着对应适应度值更小的新位置移动。如果到达尝试次数后仍不满足前进条件，执行随机行为。
(2)聚行为：聚行为是指每条鱼在移动过程中趋
向于相邻伙伴的中心以避免过度拥挤的行为。当前位置和中心位置对应适应度值丫，和Y,,/为中心位置附近视野中
的人工鱼的数量，d为拥挤因子；Y。值更小且Y!”/%"Y，则前进到中心位置。不满足条件则执行觅食行为。
(3)追尾行为：追尾行为表示每条人工鱼在视觉范围内都朝着当前的最佳方向移动。假设X$是当前状态X i的邻域内最优邻居。如果Y””<Y，且Y…J n f<SY t，则人工鱼将向该方向移动一步。否则，执行觅食行为。
(4)随机行为：随机行为是在其视野中随机选择一个
新状态X”？，然后在该方向上移动一步。实际上这是默认行为。
(5)公告板：公告板用于记录鱼中的最佳状态X n?
算法完成后，最终公告板的值是系统的最佳解决方案。
3.2算法性能改进
AFSA存在一些缺陷，例如更容易陷入局部最优值和缺乏多样性等。为了弥补这一不足，对AFSA进行改进。
(1)初始解的构造：本文通过引入佳点集的方法，优化AFSA算法的初始人工鱼分布，提高AFSA算法的全局搜索性能。本质上，优化人工鱼的初始分布是为了更科学地表征解空间的特征，人工鱼体在解空间中的均匀分布是一种有效的策略，而随机产生的人工鱼体在大多数情况下不能覆盖解空间的所有状况。由数论中的佳点集理论可知，佳点集的精度与空间维度无关，可以较好地适用于高维空间中的计算，同时，对于未知分布的对象，通
过佳点集理论获得的佳点集P,(.i)的偏差远远优于通过随机方法获得的集合。因此，基于佳点集的特征，可以为
体智能算法中的体分布提供更好的初始分布方案
*4+。假
设初始人工鱼数为2在n维空间中选择2点作为人工鱼位置，作佳点集
P,()%{({&**,{&**,…，{&*i}),i%1,2,…，s}
(6)
&称为佳点，可由下式计算
&%{2cos2"),1&"&n(7)其中，P为满足'一n)/2,n的最小质数，符号1)表示数“的小数部分。由于本算法的解空间是节点序列的集合，将此佳点集映射到问题的可行域中，贝第*个可行解的第k 维的值为K(k,i)%*十P,()"(s—1),i=1,2,…,s，符号*
+表示数.的整数部分。
(2)觅食行为的改进：在迭代过程中，标准AFSA算法通过觅食行为来实现全局搜索。当适应度值提高时，算法的收敛速度降低。细菌觅食优化算法(BFOA)中的趋化行为通过翻转与游泳操作使细菌聚集在
一个更有利的环境中，能增强觅食行为，进入更大的搜索空间，并避免陷入局部最优状态。因此，采用BFOA算法的趋化行为对觅食行为进行改进。与标准AFSA算法相比，趋化行为在处理觅食行为时增加了邻域搜索的频率和范围。适应度值在翻转操作完成后进行计算。当得到的适应度值更优，人工鱼将向该方向移动几步，直到游泳步数N，达到极限值N.或适应度值重合，否则执行随机行为。觅食行为在当前位置停止觅食，并翻转为另一条人工鱼，当所有人工鱼完成翻转，该过程完成。改进的觅食行为可以加快收敛速度并增加潜在解。人工鱼的位置i可以更新如下
X,G N,•Rind•SteP•||X，'—X j|，/<Y,)
r@ndombeh@vior，otherwise
(8)其中，Step为实数。
(3)随机行为的改进：列维飞行是一种随机游走策略，是一种典型的飞行、跳跃的步长可进行变化的策略，从而使得搜索空间的结果更有效。因此，将列维飞行添加到自然启发算法中，可确保算法的改进。在AFSA中，随机行为是一种变异策略，可以防止算法陷入局部最优。在本节中，将列维飞行引入AFSA随机行为。列维飞行可简单近似为幕律行为，满足此分布的随机步长S可以通过Man-tegna方法计算为
S%j O\1$⑼其中，4和O服从正态分布如下
u%N(0,%2),o%N(0,1)(10) %%1
+(再2/2)，r(x)函数定义为
+(()%[+^f~1(r t dt(11)
令X为人工鱼i的当前状态，执行随机行为后人工鱼的新状为
X G1%X t G&.levy(12)其中，&是步长值，应与关注问题的规模相关，为了让算法适应不同的解，表示为&%&0(i—X),X=为任意解，考虑典型的步长规模，&0通常取0.01，否则列维飞行可能变得过于激进，使新的解跳出设计领域，从而浪费评估。Levy$)表示满足列维分布的S，可由式(9)计算，通常$取1.5,.为点乘。
第42卷第4期吴嫣媛，刘向军：考虑级联失效影响的复杂网络关键节点识别・923・
4实验仿真与分析
为验证本文所提的关键节点识别方法的准确性&本节在3构的典型复杂网络及真络中仿真&所改进的优化算献*
+中该领域的优化算法、AFSA算&及识另U方法的。改进人工鱼算法最大尝试次数50，最大迭代次数100,U取4,5为0.618，人工鱼每次移动的最大步长ste p取1，加s.Z取0.1。标准AFSA相同参数取相。整键识别方统采用的基的衡量方法、文献*6+方法、文献［17］方法在不络结构上分析。3种典型网络的生成参：献*8］。美国航空网络是研究负载变化的重要网络*+，本的真实网络美国航空网络*9+。复杂网络的建立及后续的实验均采用Matlab R2012a在Intel Core i7处理器配置下完成。
41不同系数关键节点的网络性能比较本小节主要探讨级联失效模型所涉及的关键参数丁下保护方法识别的关键络抗毁性能的影响，具键识别方法的性能在后述&，节作详细叙述。方法在的容忍系数丁下识别的序列中，保护前10%个&随机的网络性能如图2所示。由网络级联失效模型可知，容忍系数T 越大，络承载级联失效的能力越强。在4络中比总能，当T不断增大，由级联失发的故障越少，网络性能都有所提高。不保护任何节点的网络性能曲线波动最大，基于优化算法的曲线性能值最高，曲线最平稳。这是保护，当随机的节重要&络的影响&络性能则受影响，代络性能的鲁棒也就有所波动。使优化算法识键过程中了级联失效过程，保护络影响的关键&也相当于把引发级联失效的保护起来&每一个T的性能最高。文献*7］方法虽然在仿真中了级联失效动态特性&但键识是传统方法&方法一样识别过程中级联失效的影响，而忽略一些会引发级联失效的关键&在随机曲线有所波动，小世界网络中尤为明显。无标度网络各曲线起点值明显较高，对节加以保护的各曲线均较为平稳，也说明了当无络的键保护起，对随机失的抗毁。美国航空网络的曲线变化与无络&曲线起高曲线平稳，随机失具的鲁棒'
当T到达一定值，级联失效消失，而只有随机攻击引发的故'波动最的世界络为分
Up0.6
看0.5
禎0.4
容忍系数
(d)美国航空网络
T-文献［17］方法一1不加保护
＜基于度方法
容忍系数(a)随机网络模型嘲0.6
看0.5
铀0.4
1.4 1.6
容忍系数
(b)无标度网络模型
容忍系数
(c)小世界网络模型
本文方法标准AFSA算法
-文献⑸方法十文献［16］方法
图2不同容忍系数T 下保护关键节点的网络性能比较
・92$・
计算机工程与设计2021 年
析，基于优化算法和文献［16］综合评价方法的曲线在T 达到一定值时
稳定， 曲线波动较大，基于优化算
法的曲线 然最高，说明基于优化算法的识别方法仍然
方 确； 为文献［16］的 方法，当络级联失效的特性， 方
为准确。文献
*7］
的 质计算上只涉及了度和，与基 方法一样曲线值波动 ，说明保护关键节的网络性能 改善，识别的关键确。 能最好的 方法，和 的传统识别方法中性
能最好的文献［16］方 细分析，要 稳定所需
的T 值，本文方法在随机网络中约为T '1.4，无标度网络 中约为T '1.3，小世界网络中约为T '1.5，美国航空网 络中约为T '1.3达到的稳定值分别约为0.75, 0.85,
0.8, 0.9；文献［16］方法对应T 值分别为1.5, 1.35, 1.6 & 1.5 &稳定值分别约为0.7 & 0.8 & 0.67& 0.85&本文
方法的网络性能分别优7.14%、6.25%、19.4% & 5.88%；
稳定值所需T 值越小&亦即要排除级联失效影响需要
的容 &节省 &保护关键
能 ：改善网络性能。
42改进优化算法性能分析
将本文改进的AFSA 算法与标准AFSA 算法、文献 *］的禁忌 算 $ 络中 键 识 本
要通过对比比较算法的优劣&验证本方法改进策略
的有效性。在随机网络中选取T '1.3 &无标度网络中选取 T '1.2 &小世界网络中选取T '1.4 &美国航空网络中取 T = 1 .2。在分析
中&以第2节中鲁棒 R 为目标
函数进行搜索识别。由于所用于实验的网络及算法的目标
是相同的&
识
的差异主要受算 能的影
响。由图3
看出&基于3种优化算法的识
一
定的相似度，在无标度网络中较为接近。在$ 络结构
中基于改进人工鱼算法的网络性能下降最快&移除相同
目的 络性能最低。
为文献*］方法。 方
法的结果优势是明显的， 是相 AFSA 算法而
言。从优化算 优过程
&各算法根
的 序
序使 失效&依据适应
最小判断出最优的序列，最 的
序列应是失
未识别的网络使网络性能值最低的
序列，但优化算 能遍历所有情况， 需要不断寻求
能最佳的优化算法。本文算法在这个过程中寻的序列 最为准确，性能最好&这是由于AFSA 算法相比于禁忌搜
算 具有并 能力，加 佳 、趋
化行为和列维飞 改进策略，得到了 的
AFSA 算 识 的 键 失 络 能的影响
算法弱，在 相同的情况下& AFSA 算
优的
序列&作为相 禁忌 算 -
具有的优势也
出来&也说明了 改进策略的
T-本文方法 一■一文献⑸方法 t 一标准AFSA 算法
图3
移除不同优化算法识别的关键节点后网络性能比较
发布评论