负载容量模型

1、负载容量模型负载容量线性模型将复杂网络建模为无向无权的简单连通图G,其中V = 叩i = 1,2,房代表 顶点集；E =Lek= (V , v), k = 1,2,.,疽代表边集；其顶点数和边数为N (G)和 M(G) ； A = 0 )为图G的邻接矩阵(如果顶点v连接v则a =1，否则a =0)。 ij nxnij ijijMotter等28假设网络节点的容量与负载之间呈线性关系，并提出了 ML模型。 模型的表达形式为：C = (1+a Li = 1,2N其中，C为容量，错误！未找到引用源。为容量参数，N为网络规模(网络 的总节点数)，错误！未找到引用源。为初始负载，它是以该节点的介数来表示

2、 的。网络节点的介数如是指通过该节点的所有最短路径的数目和，其表达式为：L = B凌错误！未找到引用源。i 丰 j=1 stx为节点V与节点V之间最短路径的总数目，x 为节点V与节点V的所有 ststst (i)st最短路径中经过节点V,的最短路径数目。当网络中某个节点遭受随机失效或故意 攻击时，节点将会被移除，失效节点上的负载根据最短路径策略进行全局重分配。 模型是针对网络节点失效进行展开的，但其同样可以应用于边失效的情况，此时 可将模型改成C = (1+a )L。为了研究加权特征与级联失效之间的关系，文献42提出局部负载重分配原 则，并以节点的度的乘积作为边的权值，其表达式为：L = a

3、(kk )0错误！未找到引用源。ij ij i j其中，0为权值调节参数。文献采用上述分配方法以及ML模型在典型网络 (NW小世界网络、BA无标度网络)上进行模拟仿真，发现在随机攻击时，当0 =1 时，几种网络均达到了抵御级联失效的最强鲁棒性能。针对加权方式，Mirzasoleiman等36提出将介数代替度进行网络边的加权，表 达式为：匕=a (BB )0错误！未找到引用一源。其中，B、B分别为节点V、v的介数。同时提出以网络边的介数作为其i ji j权值，并对三种不同的加权方式进行级联失效仿真，发现使用点的介数进行加权 时错误！未找到引用源。，网络抵御级联失效的鲁棒性更强。负载容量非线性模型

4、文对实际的高速公路网、供电线路网、航空运输网和因特网进行了负载容量 分析，通过采集实际数据模拟其分布趋势，发现在实际网络中，负载与容量之间 呈现非线性分布，且网络中负载较小的边拥有较大比例的容量。其负载容量非线 性模型为：错误!未找到引用源。F = (1- w)R (C.) + wS,(C)错误！未找到引用源。其中，R为鲁棒性测度，S为成本测度，C和F分别为网络的负载和容量，iii i错误！未找到引用源。为调节参数。针对网络中负载和容量之间的非线性关系，基于ML模型，文献33提出了一 种新的负载容量非线性模型，通过理论和仿真证明了在一定的参数下网络在抵御 级联失效和减缓交通拥堵方面具有很好的效

5、果，可以获得良好的鲁棒性能。模型 中负载与容量的关系为：C, =a +。错误！未找到引用源。错误！未找到引用源。其中a 0错误！未找到引用源。和错误！未找到引用源。为容量参数。该 模型是针对网络节点失效进行展开的，但其同样可以应用于边失效的情况，此时 可将模型改成C =a + p 同样的，在ML模型的基础上，窦炳琳等34提出一种负载容量呈现非线性的 模型，并将其与ML模型在BA无标度网络和Internet AS级网络上进行仿真对比， 发现其在实现网络鲁棒性方面要远远优于ML模型。模型中负载与容量的关系为：C =匕+ 错误！未找到引用源。错误！未找到引用源。其中a和3都是容量参数。级联失效网络%

6、和网络Gb构成的相依网络模型及节点，失效后的网络模型 当网络中节点，遭受攻击时彳将其从网络中移除，与之相连的边也会相继的失效，由于相依网络的相互作用，节点j、k的功能依赖于节点Z，所以节点z的失效会 触发节点k (节点j的功能同时依赖于节点m，所以不会失效)，同样的，与节点k相 连接的边也会相继失效，节点移除后的状态如图(b)所示，此时的网络不会出现 新的节点或边发生失效的情况，已经达到稳定状态。级联失效负载重分配方法1.均匀分配文献38 1.均匀分配文献38 假定网络边在失效之后，边上的负载以相同的比例向其他边进行分 配，L为节点V与节点V之间的初始负载。定义一个均匀分配方法U(l)，其条

7、ijij件范围是0 l 1，表达形式如下：1还，, 1、2 G - E)，时： 0.5其中：l；整个网络的为平均负载值，由均匀分配方法U(l)可知，网络中边的 最小初始负载受到非零的平均网络负载值的限制，且羽 0.5，这也意味着网络 中所有边的负载值都要大于这个平均值。2.随机分配F (F (l) = (l)：,-11)(1 ll尽管两种分配方法在网络负载值大小方面有区分，但其在本质上还是具有相 同的特性。(2-9)1 -2),l e0,1(2-9)3.局部负载重分配原则为了研究加权特征与级联失效之间的关系，Wang等42提出局部负载重分配 原则(Local Weighted Flow Red

8、istribution Rule，LWFRR)，其重分配过程的示意图 如图2-1所示。图2-2复杂网络负载重分配示意图Fig.2-2 The scheme of local weighted flow redistribution rule当边e失效，其邻接边获得的额外负载为：mnAL = L *尸匕5(2-10)mn mn / L +Lm人刀其中，m和错误！未找到引用源。分别为点vm和匕的邻接节点集(其中rm 不包含点vn错误！未找到引用源。，rn不包含点错误！未找到引用源。)。Lmn为边emn的 初始负载，.为边e从边e处获得的额外负载。边容量匕决定了该边所拥有 的最大负载。当任意一条边e

9、的容量C L +AL时，网络才不会出现级联失效 ijij ij mn现象。4.局部保护策略在以往的研究中，负载的重分配都是在节点或者边移除的情况下进行的，而 在实际的基础设施网络中，比如交通网络中，网络发生失效的现象并不是指某条 道路被删除或者封闭，而是当某路段发生拥堵的状况，而这种拥堵状态下道路上 的车辆一直都存在。因此文献44 在网络整体总成本不变的情况下，提出了局部 保护策略。该策略是指当网络中某个节点i过载时，其近邻域节点将会向过载节 点提供保护资源来解决或缓解失效情况，以确保网络能够正常运行。局部保护策 略的示意图如图2-3所示。图2-3局部保护策略示意图Fig.2-3 The sc

10、heme of the local protection method当节点v,失效时，节点v,从其邻域节点获得额外容量，其表达式为：错误！未找到引用源。(2-11)为节点v,的邻接节点集，错误！未找到引用源。节点七的初始容量，、节 点七的初始负载，p e 0,1错误！未找到引用源。为邻域节点所能提供保护的能 力。其中，网络节点的负载错误！未找到引用源。是节点七的度决定的，、=k* 错误！未找到引用源。，a为一个可调的权值参数。网络中节点七的容量满足关 系匕-Lm 、错误！未找到引用源。，这样就确保了节点七在向节点v,提供资 源的同时，其所持有的容量能大于等于初始负载而不至于使得本身失效。在这

11、个 方法中，由于是网络中节点之间的容量发生，整体网络的容量并没有改变，因此 此策略不存在网络成本增加的情况。上述局部保护策略对于网络鲁棒性的提高具有明显的效果，但对已投入使用 的实际交通网络而言，由其他路段向拥堵边提供容量的方法并不现实。且在某段 路程当中车辆拥堵时，造成拥堵的车辆可以根据交警指示或者导航信息进行改道 运行，从而缓解该路段的拥堵状况。因此本文提出一种新的符合实际情况的局部 负载分配策略，当边e失效，说明边上的容量已超过其额定容量，除去额定容mn量外，超出的容量向其邻接边进行分配，负载分配的示意图如图2-3所示:图2-4负载重分配示意图Fig.2-4 The scheme of

12、local weighted redistribution如图2-4,当边emn失效时，边上大于额定容量的那部分容量将向其邻域边分 配，每条边所获得负载值的表达式为：AL = kC * (2-12)mn mn / L +Lm人刀其中，rm、rn错误！未找到引用源。、ALmn的定义与上述公式(2-10)一样。 ACmn为使得边e.(边e的额定容量CQ失效的那部分负载，A% +七为边e. 当前的容量，此时边已经处于失效状态，只有当边emn上的容量小于或等于Cmn 时，才不会有失效的情况发生。复杂网络的鲁棒性测度网络的鲁棒性测度是用来衡量网络连通性能优劣的指标，不同的攻击方式和 网络模型下，鲁棒性测

13、度所度量出来的结果表现不一，有些测度在某种情况下并 不适用。因此设计出合理的相适应的鲁棒性测度显得非常的必要。不同的鲁棒性 测度能从各种角度反映着网络的连通性能。1最大连通片当网络中节点遭受攻击时，网络中部分节点被移除，由于级联失效的传播， 导致网络中其他部分的节点也失效，当级联失效结束时，网络中存在孤立节点或 者分散的连通子图，而人们选取这些子图当中最大的子图作为网络遭遇级联失效 之后网络拓扑结构，最大连通子图也即最大连通片的网络规模设为N 。针对最 大连通片，文献59提出了将最大连通片规模与原网络（未遭受到攻击时的网络） 规模N之比作为度量网络鲁棒性的指标。比例G的值越大，网络所具有的鲁棒

14、 性能越好。N(2-13)G =(2-13)N2失效规模文献42 从整个网络鲁棒性角度出发，提出了一个衡量网络失效后网络整体 鲁棒性。先从网络中移除一条边e，并计算其产生的失效规模S （级联失效停止 后，失效边的累计和），然后依次对网络中的每条边进行移除并计算其失效规模， 再取所有网络边的失效规模S的平均数，表达式如下：ij勺 S.(2-14)S =乙 j(2-14)ijM其中，S为网络的鲁棒性测度，M为网络中的边数。当S - 0时，网络边的 数量在级联失效发生前后几乎不变，具有很强的抵御级联失效的能力，即可以在 级联失效的初始阶段便阻止其进一步传播，反之，S - 1时，网络几乎完全破裂 成碎

15、片，即难以控制级联失效现象在网络中传播。3代数连通度代数连通度是一个可以用来表征网络稳定性和鲁棒性的度量方法，Fiedler 等网定义图错误！未找到引用源。的拉普拉斯矩阵错误！未找到引用源。的第 二小特征值错误！未找到引用源。为代数连通度，定义图G的拉普拉斯矩阵为 L = D - A，其邻接矩阵 A，度矩阵为 D = diagd , i = 1,2,., n，其中，d = n a。iij=1 ij研究表明，一个图中连通片的数目等于该图Laplace矩阵零特征根的重数，也就 是说当且仅当简单图G的Laplace矩阵第二小特征值大于零时网络图为一个连通 图。图G的的Laplace矩阵中所有特征根都是正实数，其大小关系为：0 = X X X 2A（2-15）12n研究表明，当网络的代数连通度X2越大，则网络的连通性能越好，鲁棒性能越强。4自然连通度在以往的研究中，多采用代数连通度来评价网络鲁棒