賴麗萍
(閩江學(xué)院 互聯(lián)網(wǎng)創(chuàng)新研究中心, 福建 福州 350108)
魯棒性在出現(xiàn)偶然性、危機性、不確定性、必然性事件時已經(jīng)成為系統(tǒng)持續(xù)生存的關(guān)鍵因素。魯棒性健壯則會讓系統(tǒng)可靠性、穩(wěn)定性同步提升,從而保證外界因素在攻擊系統(tǒng)時,能夠確保系統(tǒng)服務(wù)功能不受影響[1-2]。地鐵線網(wǎng)的魯棒性是指:當?shù)罔F網(wǎng)絡(luò)遭到針對性攻擊或者發(fā)生意外事件時,網(wǎng)絡(luò)可以替代路線,從而保證交通功能發(fā)揮。文中以復(fù)雜網(wǎng)絡(luò)為理論基礎(chǔ),建立一個完善并且適用于地鐵線網(wǎng)魯棒性評價的指標體系,并以北京2015年地鐵線網(wǎng)為案例,進行攻擊模擬,分析該指標體系評價地鐵線網(wǎng)魯棒性的合理性。
外界因素攻擊或內(nèi)部故障干擾復(fù)雜網(wǎng)絡(luò)時,其連通性同應(yīng)變能力保持正比。因此,文中選擇網(wǎng)絡(luò)連通度作為地鐵線網(wǎng)魯棒性的評價指標之一。
連通度是網(wǎng)絡(luò)實際邊數(shù)目與理論最大邊數(shù)目的比值。與聚集系數(shù)的區(qū)別在于連通度是面向整個網(wǎng)絡(luò),而不是網(wǎng)絡(luò)中某個節(jié)點的域[3]。連通度的計算公式如下:
(1)
式中:D----地鐵線網(wǎng)拓撲結(jié)構(gòu)圖中邊的數(shù)目;
Vd----地鐵線網(wǎng)拓撲結(jié)構(gòu)圖中節(jié)點的數(shù)目,換乘、終點車站總量。
最大連通子圖是依靠最少數(shù)量的邊,從而連接起所有節(jié)點所形成的子圖。最大連通子圖的相對大小是子圖中節(jié)點總數(shù)量同網(wǎng)絡(luò)中所有節(jié)點數(shù)量的比值。
原始網(wǎng)絡(luò)最大連通子圖同網(wǎng)絡(luò)兩者的節(jié)點數(shù)比值等于1。如果網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu)出現(xiàn)變動、外界攻擊影響下,網(wǎng)絡(luò)拓撲結(jié)構(gòu)會被動分裂為多個子圖,而最大連通子圖相對大小同樣會出現(xiàn)縮小。最大連通子圖如圖1所示。
圖1 最大連通子圖
節(jié)點A、B被破壞,這時原始網(wǎng)絡(luò)會分裂為四個小集體以及最大連通子圖。
地鐵線網(wǎng)的最大連通子圖的相對大小S的數(shù)學(xué)表達式如下:
(2)
|Vd|----初始地鐵線網(wǎng)拓撲結(jié)構(gòu)圖中的節(jié)點數(shù)目,即地鐵線網(wǎng)中換乘車站和終點車站的總數(shù)目。
該指標反映了地鐵線網(wǎng)遭到破壞或發(fā)生內(nèi)部故障前后其拓撲結(jié)構(gòu)的變化情況,集中表現(xiàn)地鐵線網(wǎng)破壞程度。
近段時間,國內(nèi)外學(xué)術(shù)界在探究復(fù)雜網(wǎng)絡(luò)連通可靠性過程中,最常見的評價指標為網(wǎng)絡(luò)平均路徑長度:如果長度越小,則連通可靠性越高;如果長度越大,則連通可靠性就會越低。
如果系統(tǒng)被破壞超過臨界值,網(wǎng)絡(luò)就會出現(xiàn)孤立節(jié)點。這時初始網(wǎng)絡(luò)平均路徑長度則會被最大連通子圖平均路徑長度所替代。這種情況的出現(xiàn)代表了網(wǎng)絡(luò)在遭受一定破壞后,連通可靠性相比于原始網(wǎng)絡(luò)要高。而現(xiàn)實情況卻是一旦遭受破壞,其可靠性也會受損,網(wǎng)絡(luò)孤立節(jié)點同其它節(jié)點會斷絕連通[4]。
可見,利用網(wǎng)絡(luò)的平均路徑長度評價器連通可靠性是不全面的。
相比平均路徑長度,網(wǎng)絡(luò)全局效率在反映內(nèi)部故障、外部攻擊前后,復(fù)雜網(wǎng)絡(luò)連通可靠性變動時極為準確。全局效率直接代表著連通可靠性,最顯著特征便是全局效率同連通可靠性間存在正比關(guān)系。網(wǎng)絡(luò)擁有較高的可替代路徑提供力,則魯棒性越高。如果出現(xiàn)內(nèi)部故障或外部攻擊情況時,連通可靠性受此影響會下降,且全局效率同步下降,網(wǎng)絡(luò)可替代路徑提供力以及魯棒性都會很低。
全局效率Eglob(G)數(shù)學(xué)表達式如下:
(3)
顯然,0≤Eglob(G)≤1。當Eglob(G)=1時,表示地鐵線網(wǎng)的拓撲結(jié)構(gòu)圖中任意兩節(jié)點之間都是直接相連的,網(wǎng)絡(luò)連通可靠性進入最大峰值后,網(wǎng)絡(luò)可替代路徑提供能力同樣會升到最大值,這時魯棒性會達到最大;當Eglob(G)=0時,表示地鐵線網(wǎng)的拓撲結(jié)構(gòu)圖中所有節(jié)點都是不連通的,即每個節(jié)點相比于其他節(jié)點都是獨立存在的。這時的連通可靠性達到最低值,網(wǎng)絡(luò)沒有提供可替代路徑的能力,網(wǎng)絡(luò)魯棒性數(shù)值為零[3]。
城市地鐵系統(tǒng)魯棒性指標集中反映出網(wǎng)絡(luò)所擁有的可替代路徑提供能力。用Berge定義中的圈數(shù)μ來代表可提供的替代路徑[4]:
μ=|D|-|Vd|+1(4)
城市軌道交通網(wǎng)絡(luò)規(guī)模逐漸擴大后,圈數(shù)同樣增加,不過這并不代表網(wǎng)絡(luò)規(guī)模越大就會擁有越強魯棒性。原因在于:地鐵線網(wǎng)規(guī)模增大后,其節(jié)點數(shù)量會隨之增加,出現(xiàn)內(nèi)部故障或外部攻擊概率會增加[3]。因此,應(yīng)該用圈數(shù)率反映地鐵線網(wǎng)的魯棒性:
(5)
以2015年北京地鐵線網(wǎng)作為魯棒性研究對象,進行隨機性攻擊和選擇性攻擊模擬。
2015年北京市地鐵線網(wǎng)拓撲結(jié)構(gòu)如圖2所示。
圖2 北京市2015年地鐵線網(wǎng)拓撲結(jié)構(gòu)圖
在模擬攻擊前,作如下假設(shè):
1)為了更具體地觀察圖2遭受攻擊時其魯棒性各項指標的變化過程,每次攻擊僅針對一個車站,也就是說,每次攻擊僅破壞一個節(jié)點[5];
2)如果拓撲結(jié)構(gòu)圖受到破壞且分裂成多個獨立子圖后,求取最大連通子圖平均最短路徑長度,并將此作為破壞后的拓撲圖平均路徑值[6];
3)當拓撲結(jié)構(gòu)圖被破壞分裂成若干個獨立子圖時,相對于最大連通子圖,其他子圖發(fā)揮的作用甚小,因此,下一次攻擊對象為最大連通子圖[7];
4)網(wǎng)絡(luò)出現(xiàn)崩潰時,魯棒性指標均為零。
現(xiàn)實情況是地鐵網(wǎng)絡(luò)遭受到一定程度攻擊后,全局效率會下降到極低程度,網(wǎng)絡(luò)作用近乎于零。因此可以認為,當Eglob(G)=0時,網(wǎng)絡(luò)崩潰[2]。
文中在Visual Studio 2010環(huán)境中借助ArcEngine進行攻擊模擬。
2015年北京地鐵線網(wǎng)遭到隨機性攻擊時,全局效率下降程度較為均勻,下降期間也沒有出現(xiàn)太多起伏。選擇性攻擊網(wǎng)絡(luò)期間,網(wǎng)絡(luò)全局效率出現(xiàn)下降時遭遇到兩次大幅度下降,隨機性攻擊和選擇性攻擊下地鐵網(wǎng)絡(luò)全局效率變化曲線如圖3所示。
當網(wǎng)絡(luò)受到隨機性攻擊時,車站遭受攻擊概率同樣是隨機的。攻擊期間,最大連通子圖相對大小會出現(xiàn)較為均勻的變化,波動幾乎為零。同隨機性攻擊模式相比,這種攻擊模式中,節(jié)點所遭受的攻擊將會按照相應(yīng)策略和順序,從而確保網(wǎng)絡(luò)可以在短時間內(nèi)遭受到較大程度損壞。隨機性攻擊和選擇性攻擊下網(wǎng)絡(luò)最大連通子圖相對大小變化曲線如圖4所示。
圖3 隨機性攻擊和選擇性攻擊下地鐵網(wǎng)絡(luò)全局效率變化曲線
圖4 隨機性攻擊和選擇性攻擊下網(wǎng)絡(luò)最大連通子圖相對大小變化曲線
由此可見,地鐵線網(wǎng)對選擇性攻擊的反應(yīng)比隨機性攻擊強烈。
攻擊模式出現(xiàn)變化時,2015年北京地鐵網(wǎng)絡(luò)連通度變化曲線有著很大相似性,隨機性攻擊和選擇性攻擊下連通度變化曲線如圖5所示。
圖5 隨機性攻擊和選擇性攻擊下連通度變化曲線
遭受到攻擊的節(jié)點數(shù)量逐漸增多后,連通度會出現(xiàn)均勻下降。如果是遭受到選擇性攻擊,相比于隨機性攻擊,其連通度下降較為顯著。此情況說明,城市軌道交通網(wǎng)絡(luò)在遭受外部攻擊時,選擇性攻擊破壞速度更快。
2015年北京地鐵網(wǎng)絡(luò)在兩種不同攻擊模式下網(wǎng)絡(luò)圈數(shù)率的變化曲線如圖6所示。
圖6 隨機性攻擊和選擇性攻擊下圈數(shù)率變化曲線
遭受到攻擊的節(jié)點數(shù)量逐漸增多后,圈數(shù)率短時間內(nèi)快速下降。選擇性攻擊模式相比于隨機性攻擊模式,其圈數(shù)率下降速度更為顯著。不管現(xiàn)實中地鐵網(wǎng)絡(luò)遭受何種攻擊,只要經(jīng)過幾次攻擊,那么地鐵網(wǎng)絡(luò)就會失去回路,最嚴重時會出現(xiàn)網(wǎng)絡(luò)崩潰,圈數(shù)率為零[7]。
定義了適用于地鐵線網(wǎng)的魯棒性概念,網(wǎng)絡(luò)在遭受針對性攻擊或發(fā)生意外事故時提供替代路徑的能力。同時,構(gòu)建了適用于地鐵線網(wǎng)魯棒性的評價指標體系:圈數(shù)率;連通度;最大連同子圖的相對大??;網(wǎng)絡(luò)全局效率。然后詳細介紹和定量化描述這四個指標。并借助Visual Studio 2010和ArcGIS10.0模擬2015年北京地鐵線網(wǎng)拓撲圖受到的隨機性攻擊和選擇性攻擊,并計算不同攻擊模式下攻擊過程的各魯棒性指標值。最后,對不同模式下各指標值的變化情況進行分析比較,得出作為典型復(fù)雜網(wǎng)絡(luò)的地鐵線網(wǎng)面對隨機性攻擊時抵抗力稍強[8]。不過在遭受到選擇性攻擊后,線網(wǎng)在短時間內(nèi)會出現(xiàn)較大波動,充分表明網(wǎng)絡(luò)對選擇性攻擊抵抗力弱。