, 王一帆1, 朱志良1, 任涛11.东北大学 软件学院, 辽宁 沈阳 110819;
2.东北大学 计算机科学与工程学院, 辽宁 沈阳 110819
收稿日期: 2015-12-23
基金项目: 国家自然科学基金资助项目(61473073, 61374178, 61300019);辽宁省博士启动基金资助项目(201501141);辽宁省教育厅一般项目(L2014097).
作者简介: 朱潜(1984-), 女, 辽宁铁岭人, 东北大学讲师, 博士研究生;
朱志良(1962-), 男, 辽宁沈阳人, 东北大学教授, 博士生导师。
摘要: 研究了双层相依网络在灰色信息攻击下的鲁棒性，讨论了在该模型上的数据包传输问题，建立了一个由节点负荷过载而引发的级联失效动态模型.通过一个可调参数来控制攻击网络节点信息的精度，随机失效和蓄意攻击是该模型的两种极端情况.分别对不同类型网络和不同耦合方式情况下的双层相依网络鲁棒性进行了研究.仿真实验发现，降低攻击信息的精度能提高网络的鲁棒性，而且攻击信息的精度存在着临界现象.
关键词：级联失效相依网络鲁棒性灰色信息攻击
Robustness of Interdependent Networks Under Grey Information Attacking
ZHU Qian1,2
, WANG Yi-fan1, ZHU Zhi-liang1, REN Tao11.School of Software, Northeastern University, Shenyang 110819, China;
2.School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China
Corresponding author: ZHU Qian, E-mail: zhuq@mail.neu.edu.cn
Abstract: The robustness of interdependent networks was researched under grey information attacking, in which the associated data-packet transport problem was discussed. A cascading failure model was established due to the traffic overload. The accuracy of the attacking information was controlled by using tunable parameter. The random failure and intentional attack were the two extreme situations of the proposed model. The robustness of the interdependent networks was studied under different network types and different coupling preferences. The simulation results verified that the robustness of interdependent networks can be intensified by decreasing the precision of attacking information, and there exists a critical phenomenon for the accuracy of the attacking information.
Key Words: cascading failureinterdependent networksrobustnessgrey informationattacking
在现代社会, 随着信息技术的高速发展, 许多关键的网络基础设施日趋完善, 比如:因特网、电力网络、通信网络、航空网络等.这些网络之间的耦合和相依关系也大幅度增加, 然而这些网络的安全性问题也受到了极大关注.在过去十年里, 专家对单层网络的鲁棒性进行了深入研究, 取得了大量研究成果.这为网络抵御攻击提供了有效方法[1-4], 然而这些方法却忽略了网络之间的相依关系.现代基础设施网络很多是耦合在一起彼此相互作用的.Buldyrev等[5]对这种典型的电力和通信相依网络模型进行了研究, 基于渗流模型研究了耦合网络的脆弱性, 这个突破性的工作引发了大量学者对双层耦合网络鲁棒性问题的关注, 主要是研究网络的耦合类型[6]、耦合强度[7]和网络结构[8]对耦合网络鲁棒性的影响.在这些耦合网络中, 它们依靠着某种特定的相依关系彼此连接.一个网络中的节点失效除了能引起自身网络中的负荷发生变化, 还能引起与它耦合的相依网络中相对应的节点失效.这两种情况相互作用, 进而能引发一系列大规模的级联失效.
先前的研究成果主要是基于随机攻击或者蓄意攻击, 在现实生活中, 这两种情况都是极端的特殊情况.当知道网络结构的准确信息时, 攻击者更倾向于移除网络的核心节点, 称这种攻击策略是蓄意攻击.当人们对网络的结构一无所知的时候, 就会随机移除网络中的一个节点, 相应的攻击策略就是随机攻击.然而在实际情况中, 仅仅能够获取网络的部分信息, 攻击的信息可能是不精确的, 称之为不完全信息或者模糊信息.一些已有的攻击策略就是基于这种思想[9-10], 李俊等[9]研究了基于灰色信息攻击的单层网络的鲁棒性, 然而这种攻击仅仅考虑了网络的静态特性, 忽略了网络的全局动态特性.丁琳等[10]研究了单层BA网络和ER网络在灰色信息攻击下的鲁棒性, 仅基于单层网络, 没有考虑现实世界中网络的耦合特性.与以上两个模型不同, 本文构建了一个由节点负荷过载而引发的双层相依网络的级联失效模型, 考虑了网络的全局动态特性, 探讨了在灰色信息攻击下双层相依网络的鲁棒性.
1 相依网络系统和级联失效模型相依网络系统是由两个网络组成的, 为了简化, 假设耦合的网络A和B具有相同的大小, NA=NB=N, 并且具有相同的度分布PA(k)=PB(k).本文考虑的是完全耦合的网络, 在网络A中的每个节点与网络B中的一个节点有相依的关系, 反之亦然.这样就在两个网络之间建立了一个一对一的相依关系[11].在迭代的失效过程中, 如果节点Ai失效, 那么与它有相依关系的节点Bi也会随之失效.本文主要研究由于交通负荷过载而引发的网络级联失效问题.负荷表示一个节点能够传输的交通流数值, 通常依赖于经过它的最短路径的条数.因此一个节点的负荷可以用它的介数来表示:
 | (1) |
一个节点的容量是这个节点能够承受的最大负荷值, 节点i的容量通常被定义为Ci, 当节点的负荷超过它的容量时, 这个节点就会失效.假设节点i的容量正比于它的初始负荷Li, 即
 | (2) |
本文主要考虑网络的三种耦合方式:同配耦合、异配耦合、随机耦合[12].为了衡量网络的鲁棒性, 采用网络失效之后最终达到稳定状态时的最大连通子图的相对大小G来衡量.最大连通子图之外的节点, 认定会失效.
 | (3) |
研究表明, 最大连通子图的相对大小G与网络的容许参数β有着很大的关系[12], G随着β值的增加而变大.这与人们的直觉是一致的, 网络的冗余越多, 那么它的鲁棒性就会越强.因此, 在本文中, 网络的容许参数值β设置成一个固定的值, 重点关注于网络的攻击方式.因为在现实中, 控制攻击的信息比改变网络的结构和性能要更容易一些.
2 灰色信息攻击方式随着网络规模的增加, 人们能了解网络的更多信息, 但是这些信息可能是不精确的.设α为信息的模糊度, 在三种不同的耦合网络情况下, 研究最大连通子图的相对大小G与模糊度α之间的关系.更具体地, 本文研究了网络在遭受攻击或者自身失效之后最大连通子图相对大小G与节点的移除比例f之间的关系.为了进一步分析, 需要定义一些符号变量.假设节点vi的负荷值为li, 网络中节点的最大负荷和最小负荷分别用L和l表示.定义
现在假设
 |
对于相依网络来说, 当一个节点从网络中移除的时候, 这会产生两种影响.一方面, 节点的移除会影响自身内网中其他节点对之间的最短路径发生变化, 那么经过这些节点的数据包就会发生变化, 因此节点的负荷值会发生相应的变化.那些节点负荷值超过自身最大容量的节点会失效, 进一步引发负荷值的不断变化, 直到网络中剩余节点的负荷值都低于它们各自节点的容量时, 网络最终达到一个稳定的状态.另外一方面, 在A网络中的节点被移除, 能够引发与它有相依关系的B网络中相应的节点失效. B网络中的这个失效节点也会同样引起B网络中发生级联反应.事实上, 在相依网络级联失效的整个过程中, 这两种因素是彼此相互作用的.因此, 可以看出这种相依关系使得双层网络的级联失效过程变得非常复杂.
3 仿真分析和数据结果对灰色信息攻击下双层网络的鲁棒性进行数据仿真验证.考虑到负荷过载时的计算成本, 设网络规模为NA=NB=1 000, 网络的平均度为
首先研究最大连通子图的相对大小G和模糊度α在不同的耦合网络类型下的关系, 如图 1所示.由图 1可知, 无论对于何种耦合方式, ER网络的鲁棒性明显强于BA网络, 并且单层ER网络的鲁棒性要强于双层ER-ER网络.对于BA网络来说, 在这三种耦合类型下, BA-BA和BA-ER网络的鲁棒性基本一致, 单层BA网络的鲁棒性要强于BA-BA和BA-ER网络.对于ER-BA网络来说, 网络的鲁棒性是异配耦合>随机耦合>同配耦合.这是由于对于异配耦合来说, 先攻击ER网络中的一个度大的节点之后, 和它相依的BA网络度小的节点失效, 对自身网络的影响较小, 这样的话, 反射到ER网络的影响也会较小, 网络的变化不大, 因此鲁棒性最强.同配耦合的鲁棒性最差, 是由于ER网络中一个度大的节点失效之后, 和它有相依关系的BA网络中度大的节点也会失效, 这样在BA网络中较多的节点失效, 和这些节点有相依关系的ER网络中的节点也会失效, 这样引起ER-BA网络的失效节点就会比较多.
图 1(Fig. 1)
 | 图 1 最大连通子图的相对大小G和模糊度α在不同的耦合类型下的关系Fig.1 Correlation between relative size of giant component G and ambiguous parameter α with different coupling preference |
现实世界中的很多实际网络都符合BA网络的特性, 所以固定第一个网络是BA网络, 用BA和ER网络分别和它进行不同方式的耦合, 研究这些相依类型网络在不同的模糊度α之下BA网络的鲁棒性.无论与何种类型网络进行耦合, 都考虑了同配、异配和随机耦合这三种耦合方式.通过对比发现, 随着模糊度α的增大, 网络的鲁棒性下降非常明显, 见图 2.当α=0.6, 节点移除比例f约为1%时, 所有不同类型和耦合方式的网络都几乎完全崩溃, 可见攻击信息的精度α对网络鲁棒性的影响非常大.事实上, α的值越大, 攻击的方式越接近于蓄意攻击, 蓄意攻击是攻击网络中负荷最大的节点, 这个节点失效之后, 所有经过这个节点的节点对之间的最短路径条数也会发生改变, 这会引发更为严重的负荷过载, 因此网络的失效程度较大.从α=0和α=0.2这两幅图中, 还可以明显地看出对于改善双层相依网络的鲁棒性的最优连接类型顺序依次是BA-BA (HH)>BA-BA (HL)>BA-BA (RL)和BA-ER (HH)>BA-ER (HL)>BA-ER (RL).BA-BA和BA-ER在三种耦合方式下的鲁棒性几乎一致, 是由于ER的鲁棒性较强, 无论是随机攻击还是蓄意攻击对它的鲁棒性影响都较小(见图 1).通过图 2还可以看出, 单层网络的鲁棒性要强于双层相依网络.
图 2(Fig. 2)
 | 图 2 最大连通子图的相对大小G和节点移除比例f在不同模糊度α下的关系Fig.2 Correlation between relative size of giant component G and removal fraction f with different ambiguous parameter values α |
由图 2可知, 对于每个固定的模糊度α值, 都存在着一个相应的节点临界移除比例.然而在现实的网络世界中, 节点完全失效的情况很难发生.为了能够使实验更符合实际情况, 引入了一个新的性能指标f0.5来衡量网络的鲁棒性, 它表示当网络中有一半的节点失效时所对应的节点临界移除比例, 也就是此时最大连通子图的相对大小G=0.5.图 3为临界移除比例f0.5和模糊度α之间的函数关系.由图 3可知, 无论BA网络和BA还是和ER网络进行耦合的时候, 在三种耦合方式之下, f0.5都随着α的增大而下降.这存在着一个临界现象αc ≈0.4.当α>0.4时, 无论对于何种类型的耦合方式, f0.5随着α的增大几乎保持不变.此时, 基于灰色信息攻击的方式和蓄意攻击的效果几乎是一样的.这是因为在模糊度达到0.4时, 网络中的核心节点能够被准确地找到, 它的失效能引起网络中几乎一半的节点迅速失效, 而再移除其他节点对网络的最大连通子图的大小影响很小.因此, 此时网络攻击的效果和α=1时攻击的效果是一样的.这与文献[9]的研究结果是不同的, 他们的结果是当α>0.4时, 临界移除比例依然随着α的增加而下降.这主要是因为在本文模型中, 考虑的是攻击网络中的一个节点之后, 整个网络产生的级联失效的最终状态, 研究的是网络的全局动态变化过程.文献[9]的模型研究的是网络的静态鲁棒性, 忽略了网络的动态变化特性.而且本文模型研究的是双层相依网络模型, 而文献[9]的模型仅仅研究了单层网络模型.
图 3(Fig. 3)
 | 图 3 节点临界移除比例f0.5和模糊度α在不同的网络耦合类型下的关系Fig.3 Correlation between critical removal fraction f0.5 and ambiguous parameter value α with different networks coupling preference |
4 结论本文建立了一个双层相依网络级联失效模型, 并讨论了网络上的数据包传输问题, 该模型能够反映网络的全局动态特性.新提出模型的最大特征就是基于灰色信息的攻击方式, 攻击信息的精度可以通过一个可调参数来控制.仿真结果表明, 无论对于何种耦合方式和类型的网络, 降低攻击信息的精度可以提高网络的鲁棒性, 而且攻击信息精度存在着临界现象.这为现实世界中相依网络在抵御级联失效时网络结构的设计和优化提供了很好的理论依据.
参考文献
| [1] | Albert R, Jeong H, Barabasi A L. Error and attack tolerance of complex networks[J].Nature, 2000, 406(6794) : 378–382.DOI:10.1038/35019019 |
| [2] | Motter A E, Lai Y C. Cascade-based attacks on complex networks[J].Physical Review E, 2002, 66(6) : 065102.DOI:10.1103/PhysRevE.66.065102 |
| [3] | Crucitti P, Latora V, Marchiori M. Model for cascading failures in complex networks[J].Physical Review E, 2004, 69(4) : 045104.DOI:10.1103/PhysRevE.69.045104 |
| [4] | Wang W X, Chen G R. Universal robustness characteristic of weighted networks against cascading failures[J].Physical Review E, 2008, 77(2) : 026101. |
| [5] | Buldyrev S V, Parshani R, Paul G, et al. Catastrophic cascade of failures in interdependent networks[J].Nature, 2010, 464 : 1025–1028.DOI:10.1038/nature08932 |
| [6] | Parshani R, Rozenblat C, Ietri D, et al. Inter-similarity between coupled networks[J].Europhysics Letters, 2010, 92(6) : 68002.DOI:10.1209/0295-5075/92/68002 |
| [7] | Wang J W, Li Y, Zheng Q F. Cascading load model in interdependent networks with coupled strength[J].Physica A, 2015, 430 : 242–253.DOI:10.1016/j.physa.2015.02.072 |
| [8] | Gao J X, Buldyrev S V, Stanley H E, et al. Networks formed from interdependent networks[J].Nature Physics, 2011, 8(1) : 40–48.DOI:10.1038/nphys2180 |
| [9] | Li J, Wu J, Li Y, et al. Attack robustness of scale-free networks based on grey information[J].Chinese Physics Letters, 2011, 28(5) : 058904.DOI:10.1088/0256-307X/28/5/058904 |
| [10] | 丁琳, 张嗣瀛. 灰色信息下复杂负载网络的鲁棒性研究[J].计算机工程与应用, 2012, 48(13) : 5–10. ( Ding Lin, Zhang Si-ying. Research on robustness of complex load-networks with grey information[J].Computer Engineering and Applications, 2012, 48(13) : 5–10.) |
| [11] | Chen Z, Du W B, Cao X B, et al. Cascading failure of interdependent networks with different coupling preference under target attack[J].Chaos, Solitons & Fractals, 2015, 80 : 7–12. |
| [12] | Tan F, Xia Y X. Robust-yet-fragile nature of interdependent networks[J].Physical Review E, 2015, 91(5) : 052809.DOI:10.1103/PhysRevE.91.052809 |
