蓄意攻击下城市地铁网络级联失效仿真

Cascading Failure Simulation of Metro Network under Deliberate Attacks

摘要: 由于人群密集、进出方便、通风条件有限且环境相对封闭等特征，城市地铁网络成为不法分子实施蓄意攻击，制造伤害事件的重要场所之一。本文基于负载-能力模型进行地铁网络级联失效仿真，模拟不同蓄意攻击策略下城市地铁网络抗毁性，通过设置4个并得出以下结论：1) 地铁网络在随机多节点攻击下的抗毁性低于单节点随机攻击；2) 对节点度最大的节点进行攻击，将会破坏网络的连通性，导致大量客流转移至其他交通方式，因此并不一定会产生级联失效；3) 对介数最大的节点进行攻击将会导致严重的级联失效；4) 增加节点容量能够有效抑制级联失效。

Abstract: Due to the characteristics of dense crowd, convenient access, limited ventilation conditions and relatively closed environment, metro network has become one of the important targets for criminals to carry out intentional attacks and create injuries. In this paper, the cascading failure simulation of metro network is carried out based on the load capacity model. We set up three scenarios, composed of random attacks and deliberate attacks. We get a series of conclusions from the results of simulation, which are: 1) The resistance of metro network to single-node attack is higher than that of multi-nodes attack; 2) The attack on the nodes with the highest degree doesn’t always cause cascading failure in metro network; 3) The attack on the node with the highest betweenness will cause serious cascading failure; 4) The increase of node capacity can effectively restrain cascading failure of the network.

1. 引言

由于人群密集、进出方便、通风条件有限且环境相对封闭，城市地铁网络成为不法分子实施蓄意攻击，制造伤害事件的重要场所之一。蓄意攻击是指人为主动地攻击城市地铁车站或区间，使网络破坏效果最大。2001年以来，世界各国已发生近400起针对公共交通设施的蓄意攻击事件，约占各类恐怖事件总数的13% [1]。比较著名的四起地铁蓄意攻击案件分别是：1995年3月20日日本东京地铁沙林袭击案件，造成12人死亡，5000余人受伤，地铁系统停运；2005年7月7日英国伦敦地铁连环爆炸造成43遇难，上百人受伤，整个伦敦地铁全部瘫痪；2010年3月29日莫斯科地铁爆炸袭击事件，造成40人死亡；2011年4月11日，白俄罗斯地铁恐怖袭击事件，伤亡十分惨重。在地铁运营区域内发生的恐怖袭击会对社会造成巨大影响、由于人员密集所以伤亡惨重，并且事故的处置和人员的救援都十分困难，严重影响了政治的稳定、生命的安全和财产的损失。

城市地铁网络具有强连通性、高负载等典型特征，一旦遭受蓄意攻击，节点的失效便会引起整个网络负载流量的重新分配，进而导致某些节点和边上的负载超过其容量而失效，这些节点的失效又可能导致其他节点和边的级联失效 [2]。网络关键节点的失效可能触发整个网络的崩溃，即级联崩溃。随着地铁运营里程的增加，国内外大量学者对地铁网络开展研究 [3] [4] [5] [6]。本文在负载–能力模型的基础上进行地铁网络蓄意攻击下的级联失效仿真，通过设置4种袭击场景，以揭示不同蓄意攻击策略下城市地铁网络抗毁性。

2. 地铁网络级联失效模型

地铁网络可以表示为无向图 $G=\left(L,N,E\right)$，L为线路集合，N为车站集合，E为边的集合。对于 $\forall l\in L$，

线路l可以表示为线路车站集合，即 $l=\left\{n_{l,1},n_{l,2},\cdots ,n_{l,i},\cdots ,n_{l,\left|l\right|}\right\}$。车站 $n_{l,i}\in N$ 是线路l的第i个车站。由

于地铁网络OD对之间的可行路径有限，假设乘客在地铁网络上选择最短路出行。

2.1. 初始负载

初始负载即蓄意攻击发生时地铁网络各节点的客流分布。借鉴文献 [7]，本文根据交通流分配的方法进行初始负载流量分配。令 $A_{l,i}\left(0\right)$ 表示节点 $n_{l,i}\in N$ 的初始负载， $D_{jk}$ 为节点j和k之间的客流量。 ${\beta }_{l,i,jk}$ 为0~1变量，当车站 $n_{l,i}$ 在OD对(j, k)的最短路上时， ${\beta }_{l,i,jk}=1$，否则 ${\beta }_{l,i,jk}=0$ 初始负载 $A_{l,i}\left(0\right)$ 可按下式进行计算：

(1)

2.2. 节点能力

节点能力 $C_{l,i}$ 是车站 $n_{l,i}$ 可以容纳的最大客流量，根据“按需定容”的设计规则，借鉴文献 [2] 和 [8]，可令 $C_{l,i}$ 与初始负载的关系式(2)所示，其中 $\alpha$ 为容量备用系数。

$C_{l,i}=\left(1+\alpha \right)A_{l,i}\left(0\right)$ (2)

2.3. 负载重分配规则

一旦节点被攻击，该节点被移除，地铁网络OD对之间的最短路将会发生变化，地铁网络客流也将会重新分配。令 $\bar{W}\left(t\right)$ 表示在t时刻受影响的OD对集合，网络负载重分配的流程：

Step 1：在 $t-1$ 时刻，地铁网络某节点被攻击，移除该节点，分析网络可达性，获取受影响OD集合 $\bar{W}\left(t\right)$，并计算各受影响OD对的最短路。

Step 2：对于 $\left(u,v\right)\in \bar{W}\left(t\right)$，根据式(1)进行网络节点重加载。如果节点 $n_{l,j}$ 在OD对在 $\left(u,v\right)$ 的最短路上，则 ${\beta }_{l,j,uv}=1$，则节点 $A_{l,j}\left(t\right)$ 在t时刻的负载为：

$A_{l,j}\left(t\right)=A_{l,j}\left(t-1\right)+D_{uv}$ (3)

Step 3：重复上述过程，直至 $\bar{W}\left(t\right)$ 中的OD对全部被加载。

2.4. 节点失效的判断准则

一旦节点负载超过其容量，则该节点失效，即：

$A_{l,j}\left(t\right)>C_{lj}$ (4)

3. 地铁网络抗毁性评价指标

地铁网络节点攻击将会给网络带来两方面的影响，一是由于网络客流重分配造成的级联失效，二是由于节点移除破坏了网络的连通性，导致大量客流转移至其他交通方式。因此，本文从上述两方面构建地铁网络抗毁性评价指标。令Z表示地铁网络抗毁性评价指标， $Z_1$ 表示地铁网络级联失效后的节点存活率， $Z_2$ 表示节点移除后，地铁网络上仍保持连通的客流量。令Z为 $Z_1$ 和 $Z_2$ 的加权和，即

$Z={\phi }_1{Z}_1+{\phi }_2{Z}_2$ (5)

${\phi }_1$ 和 ${\phi }_2$ 分别表示 $Z_1$ 和 $Z_2$ 的权重系数，其中 ${\phi }_1+{\phi }_2=1$。

地铁网络级联失效后的节点存活率 $Z_1$ 可用下式进行计算，其中N表示地铁网络节点总量， $N_c$ 表示存活节点数量。

$Z_1=\frac{N_c}{N}$ (6)

令 $F_a$ 表示地铁网络节点移除后可达客流量，F表示客流总量，则 $Z_2$ 可用下式进行计算：

$Z_2=\frac{F_a}{F}$ (7)

4. 地铁网络级联失效仿真过程

地铁网络级联失效仿真过程如下图1所示：

Figure 1. Cascading failure Simulation process of metro network

图1. 地铁网络级联失效仿真流程图

5. 案例仿真

5.1. 参数和场景设置

本文采用德国汉堡市的地铁网络进行级联失效仿真分析，该网络包括U1、U2、U3和U4共四条线路，共计97个车站，其中9个为换乘站，如下图2所示：

(a) 汉堡地铁地图 (b) 汉堡地铁网络模型

Figure 2. Hamburger Metro Network

图2. 汉堡地铁网络

该网络的区间运行时分可从汉堡公共交通联盟(HVV)主页获取。假设各换乘站的换乘走行时间为5 min，各个OD对之间的客流量均为1。车站能力备用系数为0.2， ${\phi }_1$ 和 ${\phi }_2$ 均设置为0.5。本文设置以下4个蓄意攻击场景，如下：

场景1：随机单节点攻击。随机生成8个[1, 97]之间的随机数，分别进行级联失效仿真，计算这10次仿真的平均值，以此评价地铁网络在随机单节点攻击下的抗毁性。

场景2：随机多节点攻击。随机生成6组[1, 97]之间的随机数进行仿真，每组包括3个节点，取6次仿真的随机数，来评价地铁网络在随机多节点攻击下的抗毁性。

场景3：蓄意单节点攻击。选择度最大和介数最大的节点分别进行攻击。

场景4：蓄意多节点攻击。选择两组节点分别进行攻击，一组是度最大的三个节点，一组是介数最大的三个节点。

5.2. 结果分析

各场景中攻击的节点，以及各场景下的地铁网络抗毁性指标分别如表1和表2所示。在场景1中，本文选择Eppendorfer Baum、Hamburger Straße、Habichtstraße、WandsbekMarkt、Schlump、Trabrennbahn、Steinstraße和Hammer Kirche等车站分别进行攻击，节点存活率为 89.8%，可达客流比例为59.2%，网络抗毁性为0.745。其中对Trabrennbahn和Steinstraße的攻击并未引发级联失效。而对Eppendorfer Baum的攻击引发了严重的级联失效，其导致23个节点失效，节点存活率 $Z_1$ 和可达客流比例 $Z_2$ 分别为75.2%和13.3%，远低于随机攻击下的平均值。

在场景2中，本文随机选择6组车站进行攻击，如表1所示，节点存活率和可达客流比例分别为83.3%和26.6%，其低于随机单节点攻击。网络抗毁性也下降为0.549。

Table 1. Attack nodes in each scenario

表1. 各场景中的攻击节点

Table 2. Simulation result

表2. 仿真结果分析

在场景3中，本文选择度最大的车站Kellinghusenstraße和介数最大的车站HauptbahnhofSüd进行攻击。从仿真结果可以得知，对车站Kellinghusenstraße的攻击导致网络的不连通，可达客流比例下降为71.4%，由于大量客流转移至其他交通方式，致使网络并未产生级联失效。由于可以得知，对网络度最大的节点进行攻击，并不一定会产生级联失效。对HauptbahnhofSüd的攻击引发了严重的级联失效，共18个节点失效，网络节点存活率下降为80.4%，可达客流比例下降为19.04%，网络抗毁性也下降为0.497，由此可以得知，对介数最大的节点进行攻击将会引发严重级联失效。

在场景4中，我们选择两组节点进行攻击，一组是选择度最高的节点Kellinghusenstraße、Schlump和Berliner Tor。对该节点的攻击，导致网络被分割成五个不连通的子网络，如下图3所示，可达客流比例降低为33.9%，意味着76.1%的乘客无法通过地铁网络到达其目的地。由于大量客流转移至其他交通方式，地铁网络并未产生级联失效。

Figure 3. Attack result of Scenario 4(a)

图3. 场景4(a)的攻击效果图

场景4中的另一组节点是选择介数最高的三个节点，即HauptbahnhofSüd、Jungfernstieg和LübeckerStraße。对该组节点的攻击导致11个车站失效，节点存活率为85.5%，可达客流比例降低为11.8%。值得指出的是，从仿真结果可以得知引发地铁网络级联失效的节点并不一定是度最大或介数最大的节点。例如，场景1中的Eppendorfer Baum车站失效共导致23个节点失效。

5.3. 灵敏性分析

以对节点Habichtstraße进行攻击为例分析能力备用系数α对网络抗毁性的影响。如下图4所示，能力备用系数α从1.1变化为1.5时，失效节点数量从22下降为1，这意味着当数α为1.5的时候，仅有被攻击节点失效，而网络上并未产生级联失效，由此可以得知，增加能力备用系数能显著增加网络抗毁性。

(a) 能力备用系数对失效节点影响 (b) 能力备用系数对节点存活率和可达客流比例影响

Figure 4. Sensitivity analysis of capacity coefficient

图4. 能力备用系数的灵敏性分析

5. 结论分析

本文基于负载–能力模型构建了地铁网络级联失效模型，设置了随机单节点攻击、随机多节点攻击和蓄意攻击三种方式，进行汉堡地铁级联失效仿真，得出以下结论：

1) 地铁网络在随机多节点攻击下的抗毁性低于单节点随机攻击；

2) 对节点度最大的节点进行攻击，将会破坏网络的连通性，导致大量客流转移至其他交通方式，因此并不一定会产生级联失效；

3) 对介数最大的节点进行攻击将会导致严重的级联失效；

4) 选择度最大的多节点进行攻击将会加剧破坏网络的连通性；

5) 增加节点容量能够有效抑制级联失效。

基金项目

浙江省自然科学基金资助(LQ18G030012)，教育部人文社科基金资助(18YJC630190)。