基于CML的城市地鐵網(wǎng)絡(luò)相繼故障分析＊

張海林 張鐵巖

（交通運(yùn)輸部公路科學(xué)研究院國(guó)家智能交通系統(tǒng)工程技術(shù)研究中心1） 北京 100088）

（青島市城市規(guī)劃設(shè)計(jì)研究院2） 青島 266071）

0 引 言

同自然界多數(shù)網(wǎng)絡(luò)類似，城市地鐵網(wǎng)絡(luò)也是由線和點(diǎn)組成，是一種典型的復(fù)雜網(wǎng)絡(luò)［1］．國(guó)內(nèi)一些主要城市，如北京、上海、廣州地鐵建設(shè)已初具規(guī)模．隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，城市地鐵也會(huì)出現(xiàn)一系列問(wèn)題，例如，信號(hào)故障，乘客人數(shù)的驟增造成列車、站臺(tái)過(guò)度擁堵等等．這些節(jié)點(diǎn)或邊發(fā)生的故障會(huì)通過(guò)線路和車站之間的耦合關(guān)系擴(kuò)散開來(lái)，從而引起其他節(jié)點(diǎn)故障，最終導(dǎo)致部分節(jié)點(diǎn)甚至整個(gè)網(wǎng)絡(luò)的崩潰，這也就是通常所說(shuō)的相繼故障［2］．因此有必要對(duì)網(wǎng)絡(luò)化條 件下城市地鐵網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特性以及相繼故障發(fā)生、發(fā)展進(jìn)行研究，從而對(duì)故障的預(yù)防、控制提供理論依據(jù)．

國(guó)內(nèi)對(duì)地鐵網(wǎng)絡(luò)相繼故障已有初步研究．汪小帆等［3］在中對(duì)全局耦合網(wǎng)絡(luò)、無(wú)標(biāo)度網(wǎng)絡(luò)及小世界網(wǎng)絡(luò)中CML的相繼故障進(jìn)行了較為詳細(xì)的闡述．Bao Zhejing，Cao Yijia［4］中對(duì)局域世界網(wǎng)絡(luò)的CML的相繼故障進(jìn)行了研究．馬秀娟［5］等提出有向網(wǎng)絡(luò)CML的相繼故障，并在文獻(xiàn)［6］中對(duì)樹形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的CML相繼故障特征進(jìn)行了探討，馬福祥［7］將 CML模型應(yīng)用到km，n網(wǎng)絡(luò)中，分析了km，n中不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的魯棒性．以上研究主要集中在復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)類型方面，而對(duì)在地鐵網(wǎng)絡(luò)實(shí)例分析中則尚未涉及．本文采用基于耦合映像格子（CML）的相繼故障模型和Matlab編程仿真，對(duì)北京、上海、廣州等國(guó)內(nèi)三個(gè)城市地鐵網(wǎng)絡(luò)相繼故障進(jìn)行了研究．

1 基本概念

1.1 耦合映像格子

多數(shù)時(shí)空系統(tǒng)的時(shí)間、空間和狀態(tài)變量是連續(xù)的，適于用偏微分方程來(lái)描述．無(wú)論是進(jìn)行理論分析還是數(shù)值計(jì)算，都比較復(fù)雜，而且運(yùn)算量也大．耦合映象格子（coupled map lattice，CML）便是將時(shí)間和空間變量離散化，但狀態(tài)變量仍保持連續(xù)，這樣既克服上述缺點(diǎn)，又能從本質(zhì)上顯示出系統(tǒng)的復(fù)雜時(shí)空特性．它是一個(gè)時(shí)間、空間都離散，而狀態(tài)保持連續(xù)的非線性動(dòng)力學(xué)系統(tǒng)，已成為研究時(shí)空混沌的強(qiáng)有力工具．在過(guò)去幾十年研究中，通常假設(shè)CML具有規(guī)則的拓?fù)浣Y(jié)構(gòu)（如全耦合或最近鄰耦合）．近年來(lái)，隨著復(fù)雜網(wǎng)絡(luò)的興起，人們已經(jīng)開始研究具有小世界或無(wú)標(biāo)度拓?fù)浣Y(jié)構(gòu)的耦合映像格子中的動(dòng)力學(xué)行為，如時(shí)空混沌、分岔，同步等等［8］．

1.2 基于CML的相繼故障模型

將具有N個(gè)節(jié)點(diǎn)的CML相繼故障模型描述如下．

式中：xi（t）為第i個(gè)節(jié)點(diǎn)在t時(shí)刻的狀態(tài)．N個(gè)節(jié)點(diǎn)的連接信息用鄰接矩陣A ＝ （ai，j）N×N表示．若節(jié)點(diǎn)i和j之間有邊相連，則aij＝aji＝1，否則aij＝aji＝0．這里規(guī)定任意2個(gè)不同的節(jié)點(diǎn)之間至多只能有1條邊，且不允許節(jié)點(diǎn)和自身相連；k（i）是節(jié)點(diǎn)i的度；ε∈（0，1）為耦合強(qiáng)度；非線性函數(shù)f表征節(jié)點(diǎn)自身的動(dòng)態(tài)行為，這里選擇為混沌Logistic映射：f（x）＝4x（1－x），當(dāng)0≤x≤1時(shí)，0≤f（x）≤1；式中的絕對(duì)值符號(hào)保證各節(jié)點(diǎn)的狀態(tài)非負(fù)．

如果節(jié)點(diǎn)i的狀態(tài)在m個(gè)時(shí)序內(nèi)始終在（0，1）范圍內(nèi)，即0＜xi（t）＜1，t≤m，那么稱節(jié)點(diǎn)i處于正常狀態(tài)．如果在m時(shí)刻，節(jié)點(diǎn)i的狀態(tài)xi（m）≥1，那么稱節(jié)點(diǎn)在此刻發(fā)生故障，節(jié)點(diǎn)在以后的任意時(shí)刻狀態(tài)恒等于零，即xj（t）≡0，t＞m．在節(jié)點(diǎn)狀態(tài)按照公式（1）迭代演化的網(wǎng)絡(luò)中，如果所有N個(gè)節(jié)點(diǎn)的初始狀態(tài)都在（0，1）范圍內(nèi)，并且沒(méi)有外部擾動(dòng)，那么所有的節(jié)點(diǎn)將永遠(yuǎn)保持正常狀態(tài)．

假設(shè)在m時(shí)刻給某個(gè)節(jié)點(diǎn)c施加一個(gè)外部擾動(dòng)R≥1，如式（2）所示．

在這種情況下，節(jié)點(diǎn)c在第m 時(shí)刻發(fā)生故障．因此，對(duì)所有的t＞m 有xc（t）≡0．在第m＋1時(shí)刻，與c直接相鄰的節(jié)點(diǎn)都將受到m時(shí)刻c節(jié)點(diǎn)的狀態(tài)xc（m）的影響，并且這些節(jié)點(diǎn)的狀態(tài)值按照式（1）計(jì)算得出．此時(shí)計(jì)算出來(lái)的節(jié)點(diǎn)狀態(tài)值也有可能大于1，從而會(huì)引起新一輪的節(jié)點(diǎn)故障．這個(gè)過(guò)程反復(fù)進(jìn)行，節(jié)點(diǎn)故障就可能擴(kuò)散，最終導(dǎo)致網(wǎng)絡(luò)的崩潰．

1.3 復(fù)雜網(wǎng)絡(luò)特征參數(shù)簡(jiǎn)介

直徑與平均路徑長(zhǎng)度：網(wǎng)絡(luò)中2點(diǎn)之間的距離定義為連接2點(diǎn)的最短路徑邊數(shù)，其中任意兩點(diǎn)之間距離的平均值稱為網(wǎng)絡(luò)的平均路徑長(zhǎng)度，記為L(zhǎng)，任意兩個(gè)節(jié)點(diǎn)之間的距離的最大值稱為網(wǎng)絡(luò)的直徑，記為D；度是節(jié)點(diǎn)在復(fù)雜網(wǎng)絡(luò)中的一個(gè)重要屬性，是指與該節(jié)點(diǎn)連接的邊數(shù)；聚類系數(shù)Ci又叫做群聚系數(shù)，定義為與該節(jié)點(diǎn)直接相鄰的實(shí)際邊數(shù)目與最多可能邊數(shù)之比，整個(gè)網(wǎng)絡(luò)的聚類系數(shù)＜C＞即為網(wǎng)絡(luò)中所有節(jié)點(diǎn)聚類系數(shù)的平均值；節(jié)點(diǎn)介數(shù)是指網(wǎng)絡(luò)中通過(guò)該節(jié)點(diǎn)的最短路徑的數(shù)目．

2 相繼故障仿真結(jié)果分析

對(duì)北京、廣州、上海地鐵網(wǎng)絡(luò)構(gòu)造說(shuō)明如下，并統(tǒng)計(jì)得到3城市地鐵網(wǎng)絡(luò)特征值：（1）分析所用數(shù)據(jù)均來(lái)自各城市地鐵運(yùn)營(yíng)公司官方網(wǎng)站，時(shí)間截止到2011年底；（2）地鐵網(wǎng)絡(luò)采用Space L構(gòu)造方法，以地鐵車站作為網(wǎng)絡(luò)節(jié)點(diǎn)，若在實(shí)際網(wǎng)絡(luò)中2站點(diǎn)之間有線路直接相連，則將其作為構(gòu)造網(wǎng)絡(luò)的1條邊，并且在網(wǎng)絡(luò)構(gòu)造過(guò)程中對(duì)部分線路和站點(diǎn)進(jìn)行了適當(dāng)處理．對(duì)于部分孤立線路，比如北京地鐵9號(hào)線、房山線和S2線，以及尚未開通站點(diǎn)均不在數(shù)據(jù)統(tǒng)計(jì)范圍之內(nèi)；（3）不考慮地鐵線路方向和列車在線路上行駛時(shí)間，將地鐵網(wǎng)絡(luò)抽象為為無(wú)向非加權(quán)網(wǎng)絡(luò)．對(duì)北京、廣州、上海地鐵網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征值統(tǒng)計(jì)見表1．其中直徑、平均路徑長(zhǎng)度、度、平均度在復(fù)雜網(wǎng)絡(luò)中均為量綱一的量，在此指代不同情形下2點(diǎn)之間邊的個(gè)數(shù)．

表1 各城市地鐵網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征值

本次仿真工具采用Matlab，圖中數(shù)據(jù)均為50次實(shí)驗(yàn)的平均值，仿真過(guò)程中取ε＝0．6，并在第10個(gè)時(shí)刻選擇攻擊節(jié)點(diǎn)施加擾動(dòng)R（R≥1）．實(shí)驗(yàn)采取兩種攻擊策略：隨機(jī)攻擊和蓄意攻擊．其中在蓄意攻擊時(shí)選取度較大的節(jié)點(diǎn)，對(duì)北京、廣州、上海分別選取西直門、廣州火車站、世紀(jì)大道作為攻擊目標(biāo)．首先讀入網(wǎng)絡(luò)鄰接矩陣，求出相應(yīng)參數(shù)，然后根據(jù)CML相繼故障模型得到仿真結(jié)果，輸出數(shù)據(jù)并畫出關(guān)系圖．

圖1顯示了城市地鐵網(wǎng)絡(luò)中在隨機(jī)攻擊和蓄意攻擊兩種策略下，擾動(dòng)幅度R與故障規(guī)模I的關(guān)系曲線，從圖中可以看出3座城市地鐵網(wǎng)絡(luò)的擾動(dòng)幅度與故障規(guī)模均有相似的變化趨勢(shì)，故障規(guī)模都會(huì)隨著擾動(dòng)幅度的增大而增加，并且在這兩種攻擊策略下均存在相似的闕值，．當(dāng)R＜時(shí)故障規(guī)模I很小（I≤0．2），并且變化非常緩慢；當(dāng)≤R≤時(shí)，故障規(guī)模I會(huì)迅速增加，并最終造成全局故障．從圖中可以看到，該相繼故障模型下，與隨機(jī)攻擊相比通過(guò)蓄意攻擊引起相繼故障進(jìn)程稍有增加，但是效果并不明顯．由文獻(xiàn)［9］已知基于Space L的地鐵網(wǎng)絡(luò)的具有一定的隨機(jī)網(wǎng)絡(luò)特征，其度近似服從Poisson分布，多數(shù)節(jié)點(diǎn)度為2，度分布較為均勻，因此在相同的擾動(dòng)幅度下，由蓄意攻擊和隨機(jī)攻擊兩種策略引起的相繼故障規(guī)模不會(huì)有明顯變化．

圖1 單目標(biāo)隨機(jī)攻擊和蓄意攻擊條件下擾動(dòng)幅度與故障規(guī)模關(guān)系

圖2 相繼故障在單目標(biāo)隨機(jī)攻擊和蓄意攻擊條件下的擴(kuò)散過(guò)程

圖3 多目標(biāo)攻擊下擾動(dòng)幅度與故障規(guī)模關(guān)系

圖4 多目標(biāo)攻擊下相繼故障擴(kuò)散過(guò)程

圖2 是單個(gè)節(jié)點(diǎn)相繼故障在地鐵網(wǎng)絡(luò)中的擴(kuò)散過(guò)程，圖2a），2b）分別表示了網(wǎng)絡(luò)在隨機(jī)攻擊和蓄意攻擊2種策略下故障規(guī)模的傳播曲線，其中取擾動(dòng)幅度R＝12．可以看到在同一攻擊策略下地鐵網(wǎng)絡(luò)的相繼故障擴(kuò)散過(guò)程也呈現(xiàn)出相似的變化趨勢(shì)．在第0時(shí)刻施加擾動(dòng)后，蓄意攻擊策略下在各個(gè)時(shí)刻引起的節(jié)點(diǎn)故障規(guī)模總是大于隨機(jī)策略，并且故障規(guī)模一開始便有較快的增長(zhǎng)速度，變化呈現(xiàn)出先快后慢的趨勢(shì)；而隨機(jī)攻擊策略下網(wǎng)絡(luò)故障規(guī)模呈現(xiàn)出“慢—快—慢”的變化趨勢(shì)．同小世界網(wǎng)絡(luò)相比，地鐵網(wǎng)絡(luò)在兩種攻擊策略下的相繼故障傳播均需要較長(zhǎng)時(shí)間，這也驗(yàn)證了地鐵網(wǎng)絡(luò)具有較大的平均最短路徑拓?fù)浣Y(jié)構(gòu)特征．

在進(jìn)行多目標(biāo)攻擊時(shí)隨機(jī)選取兩個(gè)目標(biāo)作為攻擊對(duì)象，并施加擾動(dòng)．同樣取耦合強(qiáng)度ε＝0．6，圖3為多目標(biāo)攻擊下故障規(guī)模隨擾動(dòng)幅度變化關(guān)系曲線，從圖中可以看到同單目標(biāo)攻擊相比，故障規(guī)模沒(méi)有明顯變化，這是因?yàn)閷?duì)于單目標(biāo)攻擊而言，當(dāng)某個(gè)站點(diǎn)發(fā)生故障并向外傳播時(shí)便出現(xiàn)和多目標(biāo)攻擊相似的情形，因此造成兩類攻擊除初始時(shí)刻之外并沒(méi)有較大差別．圖4為多目標(biāo)攻擊條件下相繼故障規(guī)模隨時(shí)間的變化情形，在這里同樣取R＝12．可以看到在多目標(biāo)隨機(jī)攻擊時(shí)故障規(guī)模的變化趨勢(shì)明顯快于單目標(biāo)情況．同單目標(biāo)隨機(jī)攻擊相比，在進(jìn)行多目標(biāo)攻擊時(shí)3城市地鐵網(wǎng)絡(luò)達(dá)到全局故障的時(shí)間提前約40%．以上表明對(duì)于地鐵網(wǎng)絡(luò)多目標(biāo)攻擊只是加快了相繼故障的傳播速率，但對(duì)最終引起的網(wǎng)絡(luò)故障規(guī)模并沒(méi)有太大影響．

3 結(jié)束語(yǔ)

通過(guò)對(duì)北京、廣州、上海地鐵網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和相繼故障分析得到以下結(jié)論：同許多其他網(wǎng)絡(luò)類似，在進(jìn)行單目標(biāo)攻擊時(shí)，地鐵網(wǎng)絡(luò)CML蓄意攻擊下故障擴(kuò)散過(guò)程比隨機(jī)攻擊要?jiǎng)×遥哂休^快的傳播速度；但當(dāng)相繼故障經(jīng)過(guò)充分傳播時(shí)，通過(guò)蓄意攻擊造成網(wǎng)絡(luò)故障規(guī)模效果并不明顯；同單目標(biāo)攻擊相比，地鐵網(wǎng)絡(luò)的多目標(biāo)攻擊只是加快了其相繼故障的擴(kuò)散進(jìn)程，對(duì)于最終引起的故障規(guī)模則影響不大．

本文只是在城市地鐵網(wǎng)絡(luò)物理層面分析其相繼故障，而未考慮運(yùn)營(yíng)交路、乘客換乘等諸多復(fù)雜情況，需要結(jié)合地鐵網(wǎng)絡(luò)實(shí)際情況做進(jìn)一步研究．

［1］BARABASI A L．Linked：the new science of networks［M］．Massachusetts：Persus Publishing，2002．

2CRUCITTI PLATORA VMARCHIORI M．Model for cascadingfailures in complex networks［J］．Physica A，2007，386：407－413．

［3］汪小帆，李 翔，陳關(guān)榮．復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用［M］．北京：清華大學(xué)出版社，2006．

［4］BAO Zhejing，CAO Yijia．Cascading failures in localworld evolving networks （English）［J］．Zhejiang Univ，Sci．A，2008，9（10）：1336－1340．

［5］馬秀娟，趙海興，馬福祥．基于耦合映像格子的有向網(wǎng)絡(luò)相繼故障［J］．計(jì)算機(jī)應(yīng)用，2011，31（7）：1952－1955．

［6］馬秀娟，馬福祥．樹形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)CML的相繼故障［J］．青海師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2010（3）：35－38．

［7］馬福祥，馬秀娟．基于CML模型的km，n網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相繼故障分析［J］．濟(jì)南大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，24（2）：185－188．

［8］陳雍君，周磊山．基于時(shí)延耦合映象格子的相繼擁堵模型［J］．電子與信息學(xué)報(bào)，2008，30（4）：988－990．

［9］汪 濤，方志耕，吳 卉，等．城市地鐵網(wǎng)絡(luò)的復(fù)雜性分析［J］．軍事交通學(xué)院報(bào)，2008，10（3）：24－28．