城市軌道交通網絡攻擊策略和脆弱性分析

王碧瑤 朱大鵬

(蘭州交通大學交通運輸學院 蘭州 730070)

0 引言

城市軌道交通是城市公共交通體系的重要組成部分,其促進了城市經濟的快速發展,具有綠色、迅速、運量大和準時等優點,是可持續發展的必然選擇。但洪水、火災、地震等自然災害及公共衛生事件等因素,都會影響城市軌道交通網絡的連通性,進而影響客流運輸效率。因此,基于復雜網絡相關理論研究城市軌道交通網絡脆弱性具有很重要的現實意義。

目前,國內外已有眾多學者對各類運輸網絡的脆弱性和魯棒性展開研究。Yang等[1]認為軌道交通網絡的脆弱性是其面對惡意攻擊時的生存性。牟能治等[2]基于復雜網絡相關知識構建重要度評價模型,研究全國快遞網絡的脆弱性。張振江等[3]考慮線路等級計算關鍵節點,分析級聯失效情況下鐵路快捷貨運網絡的脆弱性。Rodríguez—Núez等[4]發現邊的位置和客流是影響公交網絡脆弱性的重要因素。馮樹民等[5]考慮了網絡受到攻擊的嚴重程度,探索城市軌道交通網絡的抗毀性。張蘭霞等[6]通過構建高鐵服務網、車流網和地理網模型,分析其網絡特性及地理網絡的可靠性,從規劃和運輸組織的角度提出保證網絡穩定性的建議。Dellible等[7]研討了多個城市軌道交通網絡的魯棒性,針對不同規模的軌道交通網絡提出相應措施以提高其魯棒性。李搏志等[8]采用LeaderRank算法識別高速鐵路網絡關鍵節點,并對網絡進行優化。呂文紅等[9]論述了通過復雜網絡相關理論分析各類交通運輸網絡可靠性的研究現狀。

許多學者通過探索網絡中的重要部分研究網絡的脆弱性。Luathep等[10]認為脆弱性分析需要識別網絡的關鍵部分,分析這部分受攻擊時對網絡的影響。Sun等[11]通過計算軌道交通網絡特征參數尋找關鍵節點,構建模型分析級聯失效時加權網絡的客流分配。于寶等[12]通過構建重要度綜合評價指標,識別不同時期高鐵網絡的關鍵節點,探索其突發事件下的抗毀性和可靠性。文略等[13]通過構建我國西北地區鐵路網絡拓撲結構,識別關鍵節點并分析網絡可靠性。薛峰等[14]利用TOSIS法和灰色關聯構建節點重要度評價體系,為尋找關鍵節點提供參考。趙志剛等[15]通過多種攻擊策略識別復雜供應鏈的關鍵節點并研究其魯棒性。

既有研究多采用攻擊節點的方式研究軌道交通網絡的脆弱性,攻擊方式過于單一?；诖?筆者結合節點重要度和邊重要度計算方法,提出一種基于重要度的混合攻擊方法,并構建北京軌道交通網絡拓撲結構圖,識別關鍵節點和關鍵邊,模擬節點攻擊、邊攻擊和混合攻擊時最大連通子圖和網絡效率的變化,分析軌道交通網絡的脆弱性。

1 攻擊策略

針對節點的攻擊也被稱為節點攻擊,節點攻擊會造成對應節點失效,導致與該節點連接的邊均失效,攻擊后應將與該節點連接的邊移除。一個簡單網絡的節點攻擊如圖1所示。

針對邊的攻擊也被稱為邊攻擊,邊攻擊會造成對應邊失效,將該邊從網絡中移除即可。一個簡單網絡的邊攻擊如圖2所示。

圖2 邊攻擊前后網絡拓撲變化

除上述節點攻擊和邊攻擊,章鵬等[16]提出了一種混合攻擊策略,同時攻擊網絡中一條邊和兩端節點,避免兩端節點通過其他路徑連通。這種攻擊下,邊失效會造成兩端節點失效,從而導致與兩端節點連接的邊均失效。一個簡單網絡的混合攻擊如圖3所示。

圖3 混合攻擊前后網絡拓撲變化

2 城市軌道交通網絡脆弱性分析

2.1 重要度計算方法

復雜網絡可以抽象為集合G=(V,L),該網絡為無向網絡,其中V={v1,v2,…,vn}表示網絡中節點的集合,L={l1,l2,…,lm}表示網絡中邊的集合。

現有研究中蓄意攻擊一般按照節點度和節點介數攻擊節點,按照邊介數攻擊邊,但僅考慮一個參數不夠全面。根據文獻[17]中描述的方法,使用重要度衡量各節點和邊的重要性,綜合考慮節點度和節點介數兩個參數。以下為節點重要度確定方法。

首先計算網絡的節點度和節點介數,分別對它們進行線性歸一化處理。歸一化處理公式如下:

(1)

(2)

(1)(2)式中:D(i)和B(i)表示節點vi的度和介數;D'(i)和B'(i)表示歸一化后的節點vi度和介數;Dmax和Bmax表示節點度和節點介數的最大值。

將歸一化后節點度的1/2次冪和歸一化后的節點介數按權重相加,得到節點重要度,節點重要度表示為:

(3)

(3)式中:α表示加權系數,且α∈[0,1];NI(i)表示節點vi重要度。

既有研究中的邊攻擊一般分為隨機邊攻擊和按照邊介數的邊攻擊。文獻[18]認為復雜網絡邊重要度與兩端節點度的乘積呈正相關,兩端節點為vi和vj的邊重要度表示為:

(4)

(4)式中:EI(i,j)表示基于節點度的邊重要度。

通過改進文獻中的方法,根據公式(3)計算出的節點重要度,認為復雜網絡的邊重要度與兩端節點的重要度呈正相關,兩端節點為vi和vj的邊重要度如下:

(5)

(5)式中:EI'(i,j)表示基于節點重要度的邊重要度。

2.2 脆弱性評價指標

2.2.1 網絡效率

復雜網絡節點vi和vj之間距離dij的倒數可以表示兩節點間的效率,將vi和vj作為一個節點對,復雜網絡的網絡效率E(G)則為所有節點對效率的平均值,即所有節點間距離的倒數平均值。城市軌道交通網絡的網絡效率用來表示客流運輸效率,并且0≤E(G)≤1,網絡效率越高,客流運輸效率越好,當E(G)=0時,網絡不連通,當E(G)=1時,網絡中任意兩個節點都是直接相連的。網絡效率E(G)表示為:

(6)

2.2.2 最大連通子圖比

復雜網絡的節點或邊受到連續攻擊時,連通的網絡會被分割為多個獨立的子網絡,其中節點數最多、規模最大的網絡被稱為最大連通子圖。復雜網絡受到攻擊后最大連通子圖的節點數nmax和初始連通網絡的節點數n的比值被稱為最大連通子圖比,用來表示復雜網絡的連通性。城市軌道交通網絡的最大連通子圖比是用來衡量城市軌道交通網絡遭受攻擊后網絡連通性和網絡規模大小的重要指標。最大連通子圖比C表示為:

(7)

2.3 攻擊步驟

采用節點重要度和邊重要度計算方法,選用節點攻擊、邊攻擊和混合攻擊三種攻擊策略,對復雜網絡進行攻擊,計算脆弱性評價指標,研究復雜網絡的脆弱性。步驟如下:

1.計算網絡中節點度和節點介數,并對其進行歸一化處理;

2.計算所有節點的重要度;

3.判斷采用的攻擊方式是否為節點攻擊,若是則轉步驟4,否則轉步驟6;

4.按照節點重要度對網絡中所有節點進行降序排列,并分析排序結果;

5.采用節點攻擊策略,根據步驟4的排序結果連續攻擊對應節點,并計算網絡效率和最大連通子圖比,計算完成后轉步驟11;

6.計算所有的邊重要度;

7.按照邊重要度對網絡中所有邊進行降序排列,并分析排序結果;

8.判斷采用的攻擊方式是否為邊攻擊,若是則轉步驟9,否則為步驟10;

9.采用邊攻擊策略,根據步驟7的排序結果連續攻擊對應邊,并計算網絡效率和最大連通子圖比,計算完成后轉步驟11;

10.采用混合攻擊策略,根據步驟7的排序結果連續攻擊對應邊和節點,并計算網絡效率和最大連通子圖比,計算完成后轉步驟11;

11.結束攻擊。

以上攻擊流程如圖4所示。

圖4 基于重要度的蓄意攻擊流程圖

3 實例分析

以北京軌道交通網絡為例,模擬節點攻擊、邊攻擊和混合攻擊三種攻擊策略對復雜網絡產生的影響,模擬突發事件造成軌道交通網絡車站或線路失效的情況,分析城市軌道交通網絡的脆弱性。

北京軌道交通網絡如圖5所示,將軌道交通網絡中的車站作為復雜網絡的節點,車站與車站之間的線路作為復雜網絡的邊,二者結合構建城市軌道交通網絡拓撲圖。北京城市軌道交通網絡特征參數如表1所示。

表1 北京軌道交通網絡拓撲特性基本指標

3.1 城市軌道交通網絡重要度分析

根據上一章提到的方法計算北京軌道交通網絡中各節點重要度和邊重要度。權重系數α∈[0,1],取小數點后一位,共有11個值,對比不同取值時攻擊后的網絡效率大小,取攻擊后網絡效率最小時對應的權重,此時權重系數α=0.1。此時各節點重要度特征和邊重要度特征如表2和表3所示,其累計概率分布圖如圖6和圖7所示。按照節點重要度和邊重要度從大到小的順序依次排列,找出重要度最大的10個節點和10條邊,并標記它們,如圖5所示。

表2 北京軌道交通網絡節點重要度特征分析重要度區間節點特征(0.3,0.4)連接一個方向,即交通網絡中始末站(0.5,0.6)連接兩個方向,即交通網絡的中間站(0.6,0.7)大部分連接三個方向,即兩條線路的樞紐站(0.7,0.8)連接四個方向,即兩條線路的換乘站(0.8,1.0)大部分連接五到六個方向,即三條線路的換乘站表3 北京軌道交通網絡邊重要度特征分析重要度區間邊特征(0.10,0.20)一端為新路的始末站,一端為中間站(0.20,0.31)兩端均為連接兩個方向的中間站(0.31,0.38)一端為中間站,一端為連接三個方向的樞紐站(0.38,0.44)大部分一端為換乘站,一端為中間站(0.44,1.00)大部分兩端均為換乘站或樞紐站

3.2 攻擊方式

通過對復雜網絡進行攻擊研究城市軌道交通網絡的脆弱性,攻擊或干擾復雜網絡節點或邊可以降低復雜網絡的效率連通性,攻擊方式可以分為隨機攻擊和蓄意攻擊。攻擊方式特征對比如表4所示。

表4 攻擊方式特征對比

采用節點攻擊、邊攻擊和混合攻擊三種攻擊策略,每種攻擊策略下又分為四種攻擊方式,分別是隨機攻擊、節點度攻擊、邊介數攻擊和重要度攻擊,分別模擬軌道交通網絡受到攻擊后的指標變化情況,對比分析軌道交通網絡在不同攻擊時的脆弱性。

3.3 節點攻擊結果分析

節點攻擊時北京軌道交通網絡最大連通子圖比變化圖和網絡效率變化圖如圖8和圖9所示。

圖9 節點攻擊下北京軌道交通網絡網絡效率E(G)的變化情況

隨著攻擊節點比例逐步增加,C和E(G)不斷降低。四種攻擊方式下,隨機攻擊對C和E(G)影響較小,按照重要度攻擊時C和E(G)下降最快,攻擊50個節點,即攻擊節點比例達到13.6%時,C已下降至0.1以下,E(G)下降至0.01以下,網絡徹底癱瘓。

3.4 邊攻擊結果

邊攻擊下北京軌道交通網絡最大連通子圖比變化圖和網絡效率變化圖如圖10和圖11所示,其中節點度攻擊表示基于節點度的邊重要度攻擊策略,重要度攻擊表示基于節點重要度的邊重要度攻擊策略。

圖10 邊攻擊下北京軌道交通網絡最大連通子圖比C的變化情況圖11 邊攻擊下北京軌道交通網絡網絡效率E(G)的變化圖情況

在四種攻擊方式下,隨機攻擊和邊介數攻擊時C和E(G)變化較為平緩,按照重要度攻擊時C和E(G)下降最快。按照重要度累計攻擊170條邊,即攻擊比例達到40%時,C下降至0.1以下,E(G)下降至0.01以下,軌道交通網絡徹底崩潰。對比節點攻擊,可以發現邊攻擊下C和E(G)變化較為平緩,攻擊次數相同時,節點攻擊的效率高于邊攻擊的效率。這是由于節點攻擊會導致與該節點連接的所有邊失效,邊攻擊只會使對應邊失效,而95%的節點連接兩個及兩個以上的方向,從而導致兩種攻擊策略效率不同。

3.5 混合攻擊結果

混合攻擊下北京軌道交通網絡最大連通子圖比變化圖和網絡效率變化圖如圖12和圖13所示,其中節點度攻擊表示基于節點度的邊重要度攻擊策略,重要度攻擊表示基于節點重要度的邊重要度攻擊策略?？梢悦黠@看出相比隨機攻擊,蓄意攻擊時C和E(G)的下降速度更快。三種蓄意攻擊下,按照重要度攻擊時C和E(G)變化最快,攻擊至35次,即按照邊重要度攻擊35對相鄰的節點,C下降至0.1以下,E(G)下降至0.01以下,網絡癱瘓。對比節點攻擊可以發現,攻擊次數相同的情況下,混合攻擊的效率高于節點攻擊,這是由于單次混合攻擊和節點攻擊的節點數目,因此兩種攻擊策略效率不同。

圖12 混合攻擊下北京軌道交通網絡最大連通子圖比C的變化情況圖13 混合攻擊下北京軌道交通網絡網絡效率E(G)的變化情況

3.6 城市軌道交通脆弱性分析

相比隨機攻擊,蓄意攻擊對軌道交通網絡的破壞程度更大。三種蓄意攻擊方式下,邊介數攻擊對軌道交通網絡的影響最小,節點度攻擊次之,略高于重要度攻擊,重要度攻擊下軌道交通網絡最容易崩潰。這是由于關鍵節點或邊受到攻擊會嚴重破壞網絡的連通性,從而迅速降低網絡效率和最大連通子圖比。

比較三種攻擊策略的結果分析發現,在相同的攻擊次數下,混合攻擊時軌道交通網絡更加容易崩潰,節點攻擊次之,邊攻擊對軌道交通網絡的破壞最小。由此認為混合攻擊的攻擊效率優于節點攻擊和邊攻擊。

4 結論

(1)基于復雜網絡相關理論,構建城市軌道交通網絡拓撲結構,分析北京軌道交通網絡的脆弱性。結果表明:三種攻擊策略下,蓄意攻擊對軌道交通網絡的破壞程度一般高于隨機攻擊。

(2)結合節點度和節點介數構造重要度計算方法,找到北京軌道交通網絡中的關鍵節點和關鍵邊,發現關鍵節點和關鍵邊持續失效會造成網絡迅速崩潰,應加強對應車站和區間的應急防護,制定車站和區間失效的應急策略,降低突發事件對軌道交通網絡連通性和運輸效率的影響。

(3)相比節點攻擊和邊攻擊,混合攻擊的攻擊效率更高,軌道交通網絡更加容易崩潰,但混合攻擊的攻擊成本高于其他兩種攻擊方式。

(4)雖分析了三種攻擊策略,但均未建立統一的指標度量攻擊成本,也未考慮客流對車站和線路重要性的影響,為此進一步研究這些因素對軌道交通網絡脆弱性的影響將具有實際意義。