中国指挥与控制学会会刊 
过去几十年,对于复杂网络的研究大多集中在单个、孤立的网络上,即从宏观角度,面向整个网络体系分析单一网络的动态演化、遭受攻击时的级联失效、单个网络的鲁棒性等问题。而现实世界中许多网络都不是孤立的,是与其他网络之间有着互相依赖、合作或是竞争的关系[1],即“网络的网络”,如物联网。随着科学技术的进步和数据获取能力的增强,人们开始开展对网络间相关理论的研究。
相依网络理论最初应用在电网、计算机网络之间。相互发生联系的两个或多个网络中,如果其中某个网络中节点发生故障,网络之间的联系会将故障的影响传播和放大,且有机会影响其他网络的功能,最终一个很小的故障很有可能对整个体系造成不可估量、不可挽回的后果。产生这种“网络多米诺骨牌效应”现象的根源就是网络间存在的相互依赖性,具有这种特性的网络就是相依网络[2](Interdependent Networks)。典型事例就是2003年9月23日意大利的停电事故。
通过归纳总结近五年内不同学者对相依网络理论的有关研究,文章概括介绍相依网络的结构特征、鲁棒性测度、攻击方式、遭受不同攻击时的鲁棒性变化及其负载重分配等方面的现状,分析当前研究的短板与不足,阐述有待加强的研究方向,最后就相依网络理论的应用领域进行合理展望。
1 相依网络理论
2010年,Buldyrev等在Nature上发表了题为《相依网络中的灾难性级联失效》[3]的论文,针对相依网络级联失效的现象,提出全相依的相依网络模型,也就是两个网络的节点之间存在一一对应的相依关联。如果其中一个网络的节点发生故障,另一个网络的节点也会遭受影响,随即发生故障,这种“多米诺骨牌”故障过程如图1 所示。图1 中,实心节点代表一个网络,空心节点代表另外一个网络,实线代表网络内部的连接关系,虚线代表两个网络之间的相依关系,这种相依关系可以体现为信息联系、资源联系、地理联系等,两个网络构成相依网络。当攻击空心网络中的一个节点导致该节点发生故障,则与该节点相依的另一网络中节点可能就会发生相依故障而失效;网络内部的相邻节点可能会发生负载超限而失效;经过几个步骤的迭代增殖,故障不再传递,网络达到稳定状态,最终维持最大连通子图运作。如果最大连通子图仍然能够维持网络整体的基本功能,那么网络仍可以发挥其作用;如果最大连通子图不具备功能,那么就等同于全网崩溃。
导致上述不同于单个复杂网络的崩塌式级联失效后果原因主要是网络的拓扑结构不同。相依网络根据拓扑结构的不同,可以划分为不同的种类。从相依节点的对应情况区分,相依网络可以分为一一对应相依网络(图2 a)、多(一)对多相依网络(图2 b);从相依边的方向性区分,可以分为单向相依网络(图2 c)、双向相依网络(图2 d);从相依边的数目区分,可以分为部分耦合相依网络(图2 e)、全耦合相依网络(图2 f)。区别于相依网络,有学者提出层次网络的概念,例如一个城市的道路交通网和公交线路网。某一交通线路的故障,会影响公交线路的布局分配,公交线路的布局调整,也会影响道路交通网的拥塞状况。
式中,E为连边集合,<i,j>∈E表示节点i和节点j之间存在连边,ki, kj表示节点i和节点j的度值。
在装备保障网络中,维修子网络和储存供应(储供)子网络恰恰可以看作相依网络的两个子网络。因此,研究装备保障网络的一些特性可以运用相依网络理论很好的解决。
2 相依网络鲁棒性分析
鲁棒性是相依网络演化与生长过程中的一个重要参数。鲁棒性越高的网络,其抵抗故障的能力也越高。研究相依网络的鲁棒性,尤其是遭受不同方式攻击后的鲁棒性变化是当前研究的前沿热点。
2.1 鲁棒性测度
对于不同拓扑结构的相依网络,选择不同的鲁棒性测度可能会得到不同的实验结果。当前对于鲁棒性测度主要有以下几种:
1)最大连通子图。最大连通子图是网络级联失效结束达到稳定状态时节点的规模大小。其规模值与原网络节点总数之比可以用来表征鲁棒性大小,该值越大代表网络鲁棒性越好。例如,文献[7]等针对BA复杂网络的现实特征,构建基于正/负度相关的BA无标度相依网络模型(BA-ALD、BA-DLD和BA-AL),定义测度网络鲁棒性的参数,最终极大连通子图比例P,相依节点比例F和相依冗余度K,如图3 中,F=0.4, K=2, P值如公式(2);并通过基于度的蓄意攻击与随机攻击两种方式仿真分析相依网络的鲁棒性,得出其鲁棒性与F呈负相关,与K呈正相关。
式中,NA和NB分别是两个子网络初始节点总数;N'A 和N'B 分别是两个子网络级联失效稳定后的节点总数。
2)平均失效规模。平均失效规模是从网络整体衡量其鲁棒性的,选取网络中一条边删除,网络稳定后节点的失效规模为S,然后依次删除网络中其余的边,S的平均值即为平均失效规模。可见,平均失效规模与网络鲁棒性成反比关系。文献[8]中就利用平均失效规模测度网络鲁棒性。
4)自然连通度。用代数连通度测度鲁棒性有一个前提就是网络是连通的,如果网络不连通,那么代数连通度就不适用了。吴俊[12]解决了代数连通度不适用的问题,建立了网络谱测度理论与方法,提出了自然连通度。自然连通度可以由网络的邻接矩阵经过计算得出。
5)渗流阈值。网络级联失效的一阶相变与二阶相变之间存在一个渗流阈值。该值越小,其鲁棒性越好。
在装备保障网络中,其保障效率不仅与网络的规模相关,还受到网络传递效率的制约。因此,度量装备保障网络的鲁棒性时要联合网络最大连通子图和网络传递效率来确定参数指标。
2.2 攻击方式
分析相依网络的鲁棒性,就不可避免地要选择网络的攻击方式。
根据获取的敌方信息精度不同,目前主要攻击方式有
1)随机攻击方式。随机攻击方式即完全不知晓敌方信息,没有目标性地随机选择攻击对象。
2)蓄意攻击方式。蓄意攻击方式即知晓敌方的全部信息,有目标、有针对性地选择攻击目标。
3)基于不完全信息的灰色攻击方式。灰色攻击方式即知晓敌方的部分信息。朱潜[13]定义了信息精度参数μ,μ∈[0,1],Ω为攻击方所获取的待攻击区域范围,那么μΩ为待攻击节点数量。假设节点vi的度值为ki,攻击范围内最大度值和最小度值分别为kmax和kmin。假定攻击方观测到节点vi的度值为Δki,Δki为区间[ki-(ki-kmin)(1-μ),ki+(kmax-ki)(1-μ)]的随机变量,也就是,
Δki=ki-(ki-kmin)(1-μ)+(kmax-kmin)(1-μ)ρ
式中:ρ是在[0,1]上满足均匀分布的一个随机变量。敌方按照其观测节点度值大小选择被攻击节点,即为灰色攻击策略。此攻击策略在装备保障网络演化过程中较为契合实际。
根据获取敌方信息的种类不同,主要攻击方式有
1)基于节点度的攻击方法。该方法是以节点度值作为节点信息的参考,优先攻击度值大的节点。
2)基于节点介数的攻击方法。该方法以节点介数衡量节点信息,首先攻击介数大的节点。
式中:0≤λ≤1, α≥0, β≥0为可调参数,代表不同的权重,ki表示节点i的度值,bi表示节点i的介数值。
2.3 鲁棒性分析与提高
相依网络鲁棒性的影响因子主要有网络的耦合方式、鲁棒性的测度、网络攻击方式、连边的属性特征等。对鲁棒性进行研究,就是分别对前述影响因子进行研究,分析其对鲁棒性的影响关系及影响大小,从而有针对性地改进网络结构,提高鲁棒性。目前,已研究的可以提高网络鲁棒性的方法主要有以下几种:
式中:eij为网络A中的节点i与网络B中节点j相连的概率。实质上,rAB和同配系数r有着类似的描述作用。
式中:M为两网络相依边的总数,tj为网络A中的节点j与网络B中节点j之间的相依边数。
3)改善网络的拓扑结构。例如,增加相依网络连通边和相依边或者改变网络k-core层次结构。连通边和相依边是相依网络中存在的两种类型连边,已研究的改善相依网络拓扑结构的添加连边策略主要有随机加边策略(Random Addition Strategy,RA)、优先节点度低的加边策略(low Degree Addition Strategy,LD)、优先节点介数低的加边策略(Low Betweenness Addition Strategy,LB)和基于代数连通度的加边策略(Algebraic Connectivity Based Link Addition Strategy,ACB)等。与上述添边方法不同,文献[20]定义网间相依节点度差(Inter Degree-degree Difference,IDD),提出低网间节点度差加边策略(Low Inter Degree-degree Difference Addition Strategy,LIDD)和随机网间节点度差加边策略(RIDD),并通过随机网络、小世界网络和无标度网络模型进行数值验证,表明LIDD策略和RIDD策略能够在一定程度上提升网络的鲁棒性。文献[21]针对已有加边策略RA,LD,LIDD进行改进提高,提出PRA,PLD,PLIDD等加边策略。文献[22]针对影响网络鲁棒性的网络度分布和故障节点等因素,提出邻近节点优先连接的局部最优化策略(Neighbor Node Priority Connection, NPC),较同配耦合连接、异配耦合连接和随机耦合连接策略对于提高相依网络鲁棒性有很大优势。文献[23-24]分析了k-core结构层次深度对相依网络鲁棒性的影响,k-core层次深度越小,相依网络的鲁棒性越高。与k-core对应的一个概念是k-shell。文献[25-26]阐述网络的shell结构特点,构建出ER-ER相依网络,模拟攻击方式为按照shell层次移除部分节点,得到渗流阈值以及网络的鲁棒性不但与相依边的数量有关,还与网络的平均度有关等结论。
综上,鲁棒性作为表征相依网络在遭受攻击时网络稳定状态的一个指标。对其进行分析和探究可以更好地理解网络拓扑结构,发现网络中脆弱节点和薄弱环节,进而指导现实网络的构建。针对鲁棒性的研究,通常是利用已有的单个网络模型构建出相依网络模型,选择不同的网络攻击方式及恰当的鲁棒性测度指标,进而分析鲁棒性的变化趋势,提出防护策略。
3 负载重分配策略与鲁棒性提高
相依网络的级联失效与单个复杂网络的失效模式不同。在相依网络中主要存在2类失效原因:一类是相依边的失效导致节点的失效由一个网络传至另一个网络;另一类是一个节点的失效会将其原有负载传递至其他节点,如果超出其他节点的承载容量,就会导致其他节点负载超出而失效。
3.1 负载-容量模型
负载是在网络运转过程中节点实际承担的资源、信息等流量大小。负载是引发级联失效的外因;容量是节点的固有能力,是导致级联失效的内因。研究相依网络的级联失效过程就是对负载与容量的探究。
对节点负载与容量的定义,大都是围绕着节点的度值与介数值进行的。一种是基于节点度的定义方法,认为节点度分为内部度和相依度,节点的负载应该综合考虑两种度值的影响。例如文献[28]中,节点初始负载定义为
式中:Li(0)为节点i的初始负载;ki为节点i的内部连通度;di为节点i的相依外部度;θ、α、β是控制参数,控制两种不同类型度对初始负载分布的影响。
另一种是针对介数来定义负载的[29-30],该定义是基于信息及资源沿节点最短路径传递这一前提的,其表达式为
式中:Bi为节点i的介数值,q≥0,γ≥0是可变系数,控制着初始负载的分配比例。
也有学者联合节点度与介数对初始负载进行定义[31],其表达式为
$L_{i}(0)=\varphi\left(k_{i} \hat{k}^{-1}\right)^{\alpha}+(1-\varphi) B_{i}^{\beta}$
式中:ki为节点i的度值; 为节点i所在网络的平均度;Bi为节点i的介数值;φ, α, β为控制参数。
不同学者对于节点容量的定义则比较统一,都是基于节点的初始负载值,设定负载容忍系数,确保网络初始状态不会过载。容量表达式为
Ci(0)=(1+η)Li(0)
式中:Ci(0)为节点i的负载最大容量;Li(0)为节点i的初始负载;η为节点的负载容忍系数。
3.2 负载重分配策略
当移除网络中负载值较高的节点或边时,就很容易导致全网络崩溃。这时,要提高网络的鲁棒性,应改变网络负载的重分配策略。已提出的负载重分配策略主要有以下几种:
1)均匀分配。均匀分配是负载以完全相同的比例向其他节点分配。
2)随机分配。该方法是基于网络平均负载来随机分配的。
3)局部负载重分配。局部负载重分配是指在节点失效后,其负载会按照一定比例分配给其邻居节点。其过程如图4 所示。
式中:Fi为故障节点i的负载值;ΔFj为邻居节点j被分配的负载值;k为节点度;Γi为节点i的邻居节点集合。如果Fj+ΔFj大于节点j的承载能力,那么节点j就会因为超载而失效,从而引发新一轮的负载分配。
综上,相依网络中负载的全局分配和局域临近分配是负载分配时的两种极端策略。这两种分配策略的物理机理并不相同[37]。前者是基于介数的概念,而后者是基于道路交通流的分流机理和Internet网络路由规则。通常情况下,负载局域临近分配策略较全局分配策略能够更好地阻止“雪崩”式故障的发生。实际中的电网、交通网、通信网以及其他基础设施网络中的负载分配策略可能介于两种分配策略之间。当前对于负载重分配方面的研究都是针对节点故障发生后再进行负载的再分配,并没有考虑针对节点的承载能力设定阈值,如当节点负载达到最大承载能力的80%时,提前进行负载分配,来达到消除级联失效的发生。因此,如何更好地分配负载来减小级联故障规模,如何利用支援保障等方式消除故障和管理负载以及考虑故障节点修复后承载能力的变化,考虑设定节点的负载阈值提前进行负载分配以避免级联失效发生等,可以作为相依网络有关负载方向的下一步研究内容。无论是全局分配还是邻近局域分配,都是依据网络的介数或度数等静态统计描述来实施的,没有考虑网络中流的动态过程。因此,下一步可以针对相依网络中各类信息流、权重的变化研究负载的动态分配过程。
4 结束语
通过上述对国内外研究现状的分析综述,可以发现,国内外大量学者、专家在复杂网络领域投入了大量精力研究,并建立了比较成熟的理论体系,在各个行业的应用都取得了较好的效果。进入信息化时代,计算机网络将社会生活的方方面面联接起来且联系越来越紧密,各种基础设施网络间的相依性越来越明显。许多学者开始将复杂网络扩展延伸到相依网络,开始研究相依网络的结构特点、鲁棒性和抗毁性等要素指标及其在各个领域的实践应用。目前,针对相依网络的研究主要涉及电网系统、金融领域、生物领域、生态系统、疾病传播、气候变化、交通网路等,但较少涉及军事领域中的应用。相依网络理论在军事领域上的研究,是一个比较新的方向。
另外,针对相依网络遭受攻击时的级联失效模型研究也是立足于网络节点或边的二态论;也就是说,在遭受攻击前,网络中节点或边是可以完全正常工作的。当遭受攻击后,网络中节点或边完全故障不能工作。但实际网络中并不是这样。当节点遭受攻击时,可能完全故障,也可能部分故障,还能工作,只是承载能力减弱。因此,增加网络中节点或边的状态指标,遭受攻击时,节点对负载的阈值下降到某一阈值,分析网络的鲁棒性及负载重分配机制,可以作为进一步的研究方向。
多军(兵)种联合作战及网络中心战理念的提出及运用使得各作战要素、作战单元、作战系统之间联系越来越紧密,装备的数量规模与系统复杂程度增大,增加了装备保障的难度与复杂度。从网络化的视角来看,可以将各级各类维修机构、储供机构看作网络中的一个个节点,彼此之间通过指控信息、协同信息、保障资源支持、保障资源信息反馈、保障任务需求信息等关系边相互联接,构成一个纵横交错、彼此相依耦合的装备保障网络。
在整个装备保障相依网络中,主要涉及维修子网络与储供子网络,两子网络中节点之间存在异质性,不能视为同一种网络。维修子网络中实体节点包含战区修理厂、车场、修理基地、各修理营(连)以及技术保障排等;储供子网络中实体节点包含各级器材仓库、各级油料仓库、各级投送基地以及联勤保障中心等。各节点之间相互之间联系包含由上至下的指挥调度关系、同级之间的器材油料保障关系以及由下至上的信息反馈关系等。这些相互关系则构成相依保障网络的相依边及内部边,两种边引起的级联失效后果并不相同。
最后,根据现行装备保障体制及军事信息的不完全性选择不同的节点打击方式,分析装备保障网络的鲁棒性变化趋势,进一步得到装备保障活动的薄弱环节;根据协同保障、跨级保障等不同保障方式可以提出不同的节点防护策略及加边策略,研究保障资源负载的分配情况,进而指导保障资源的调度与分配。
综上所述,将相依网络理论应用到装备保障网络中具有一定的先进性与合理性,能够指导我军新型装备保障体系的构建与改革,需要更多的学者关注并进行研究。