預防道路交通網絡級聯失效的交叉口擴容策略

黃 帥，王正武，周振宇

（長沙理工大學交通運輸工程學院，湖南長沙 410004）

道路交通網絡作為城市交通活動的載體，是國民經濟和城市運行的主動脈，是確保城市生命線系統正常運轉的子系統。然而，當網絡中的一個或少數幾個節點（邊）受到內部、外部因素的干擾而失效或故障后，這些失效節點（邊）會通過節點和邊的耦合關系引起其周邊的節點和邊的失效，這種連鎖效應可能導致整個網絡發生崩潰，這種現象被稱為級聯失效。級聯失效雖然不經常發生，但其后果非常嚴重［1］。因此，預防道路交通網絡的級聯失效具有重要意義。

目前，復雜網絡級聯失效的預防與控制措施研究集中在3個方面：①節點容量優化。李勇［2］等人提出了基于級聯失效的戰域保障網絡節點容量優化模型。劉漳輝［3］等人探討了如何選取非線性負荷－容量模型的參數，以達到最大化網絡魯棒性和最小化網絡投入代價的目的。彭晶波［4］等人提出了一種針對無線網絡的單節點容量最大化方法，尋找一個最優的歸一化信號幅度γopt，以獲得最大化的節點容量C。②邊增加或刪除。Motter［5］等人認為無標度網絡受到初始攻擊后，可以通過刪除一部分低（高）負載節點（邊）來控制級聯失效的傳播。在此基礎上，Zhao［6］等人獲得了最優刪除策略。相反地，Hayashi［7］等人提出了增加邊的級聯失效控制策略。③均勻負載等其他方法。Schafer［8］等人提出了一種增加網絡級聯失效抗毀性的設計方法，并通過減少網絡總負載來提高網絡抗毀性。Motter［9］等人認為，網絡的抗毀魯棒性與節點介數分布相關，介數分布越同質，其魯棒性越強；可通過保護介數較大的節點或均勻負載分布來預防級聯失效。趙暉［10］提出了通過導航策略來預防輸運網絡的級聯失效。這3種方法中，節點容量優化和邊增加或刪除是通過對網絡中節點（邊）重要度的測算、排序，找到網絡中的關鍵節點（邊）。然后再對關鍵節點（邊）采取保護策略，從而達到預防級聯失效的目的。這2種方法針對性較強，能夠有效利用有限的資源，較大程度地改善了路網通行能力。而均勻負載則是通過研究網絡中負載和容量的分布特點以及節點之間的路由規則和負載分配原則，控制整個網絡的“承載極限”來達到預防級聯失效的目的。該方法資源消耗較大，但能更為徹底地改善整個路網的通行能力。

擴大節點容量預防級聯失效的現有研究［11］表明：在網絡拓撲結構一定的條件下，節點容量越大，級聯失效抗毀性越強，這為通過交叉口擴容來預防道路交通網絡級聯失效提供了理論基礎。現有的預防復雜網絡級聯失效的節點容量擴大措施還只是定性地認為擴容有利于預防級聯失效，但還沒有解決2個關鍵問題：①通過擴容哪些交叉口來預防級聯失效；②交叉口擴容多少更有利于減輕級聯失效的后果。本研究擬構建交叉口擴容的優化算法予以解決。

1 道路交通網絡級聯失效模型

道路交通網絡級聯失效模型采用負荷－容量模型［9］，該模型可描述為：

1）初始狀態：路網中的路段（交叉口）都處于正常狀態，即各路段（交叉口）的初始流量均小于實際容量。

2）初始攻擊：刪除某個路段（交叉口）。

3）流量分配：路段（交叉口）的刪除將導致出行網絡的OD流在道路網絡中重新分配，路段（交叉口）流量發生變化。

4）計算飽和度并判斷：路段（交叉口）流量的變化導致其交通狀態也發生變化。如果所有路段（交叉口）飽和度均小于1，則停止；否則，轉5）。

5）更新路網：將飽和度大于1的過載路段（交叉口）刪除，更新路網，并轉模型。該模型：邊的容量采用文獻［12］的變化規律，即

式中：Cj（τ）為節點j在τ時間步的容量（假設交叉口容量是相交道路最大容量的0.9倍）；qj（τ）為節點j在τ時間步的流入量，即qj（τ）＝∑iqij（τ）。

6）失效節點的判斷依據：以節點飽和度來描述節點是否失效。節點飽和度定義為節點各關聯路段進口道的負荷系數加權值，即

式中：λ為整個節點的飽和度；n為節點關聯路段進口系數；qi為第i條關聯路段進口道的負荷系數（當量交通和通行能力之比），即該關聯路段進口道的飽和度；Qi為第i條關聯路段進口道的交通量。

7）采用阻塞程度指標J［13］描述級聯失效的后果，即

式中：qij（τ）為路段（i，j）在τ時刻的流量，pcu／s；tij（τ）為路段（i，j）在τ時刻的阻抗，s；qij（0）為初始交通分配后路段（i，j）的流量，pcu／s；tij（0）為初始交通分配后路段（i，j）阻抗，s。

路段阻抗采用BPR等函數。流量分配可采用用戶最優和系統最優等交通分配算法。

2 考慮級聯失效的交叉口擴容策略

根據擴容后道路交通網絡節點狀態來判斷應該擴容哪些交叉口，根據擴容后的阻塞程度指標來確定交叉口適合的擴容量［4］。提出的擴容算法為：

1）初始化。給定道路交通網絡模型，將出行OD對在道路網絡中進行分配，記錄此時的阻塞程度指標J（0）。

2）攻擊。攻擊路網中的一個或多個節點。

3）調用級聯失效流程，判斷級聯失效后果J1。如果沒有引起級聯失效，不需擴容，結束算法；否則，轉4）（采用擴容策略來防止級聯失效）。

4）擴容。

①在攻擊后的網絡中，選擇飽和度最大的交叉口I1擴容K1倍。調用級聯失效流程，計算級聯失效后果，判斷擴容K1倍的效果；繼續擴大擴容倍數至K2＝K1×P，調用級聯失效流程，并判斷擴容K2的效果；繼續擴容，直至前、后效果不明顯。

②在擴容Ke倍后，比較Je和J1。如果效果明顯，則交叉口I1擴容Ke倍，并更新網絡；否則，交叉口I1不擴容。

③對更新網絡進行評價。如果沒有引起大規模的級聯失效，則結束算法；否則，到①中選擇飽和度最大的、未擴容的交叉口I2擴容K1倍。

算法中，P為交叉口擴容倍數的增長因子，初始取值范圍為1.5＞P＞1；K1為交叉口的初始擴容倍數，初始取值范圍為2＞K1＞1；Ke為交叉口的最佳擴容倍數；Je為交叉口擴容最佳倍數Ke后的路網阻塞程度指標。試算時，取值間隔視具體情況而定，以路網有明顯改善為準。攻擊可以是單個節點（邊）的攻擊、也可以是多個節點（邊）的攻擊。本研究的擴容量通過試算法優化確定，同時未考慮擴容的約束；如果要考慮擴容量的約束，則在①中限制最大擴容倍數即可。算法中，若交叉口Ii擴容Ke倍（Ke較大）后，Je不收斂或震蕩，考慮資源有限，則結束算法，擴容其他交叉口Ik，并與Ii進行比較。若同樣擴大Ke倍，擴大交叉口Ii的效果好于Ik的，則擴容交叉口Ii；反之，則擴大交叉口Ik。

3 仿真試驗

以長沙市雨花區主干路網為例，開展試驗研究。該路網共有22條邊，15個節點，路網如圖1所示，節點容量見表1。設出行網絡共有8個OD對，出行網絡OD見表2。各路段容量和自由流阻抗見表3。

圖1 路網示意Fig.1 Road network

表1 各初始節點容量Table 1 Initial capacity of each node

表2 初始OD流量Table 2 Initial OD flow

表3 各路段容量和自由流阻抗Table 3 Each link capacity and the free flow impedance

案例中，交通分配采用UE準則，初始路網的阻塞程度指標為J（0）＝1.109。節點2被攻擊失效后，將引起級聯失效，其阻塞程度指標J（1）＝1.593，節點2失效后各節點的飽和度見表4。

表4 節點2失效后各節點的飽和度Table 4 Each node saturation degree after node 2failed

對飽和度最大的節點14擴容，取K1＝1.5，P＝1.1，擴容后阻塞程度的變化如圖2所示。

從圖2中可以看出，當Ke＝2.92時，阻塞程度指標J收斂。此時，J（3）＝1.160，各節點飽和度見表5。

圖2 節點14擴容后阻塞程度變化的趨勢Fig.2 Changes in trends in the degree of obstruction after expansion of node 14

表5 節點14擴容Ke后各節點飽和度和阻塞程度指標Table 5 Each node saturation degree and obstruction index after expansion Keof node 14

從表5中可以看出，仍有8個節點擁堵，還需要繼續擴容。對節點4行擴容，擴容后阻塞程度的變化如圖3所示。

圖3 節點4擴容后阻塞程度變化的趨勢Fig.3 Changes in the degree of the obstruction after expansion of node 4

從圖3中可以看出，當Ke′＝1.99時，阻塞程度指標J收斂。此時，J′（3）＝1.06，各節點飽和度見表6。

此時，路網只有2個節點有輕微的擁堵，不再出現級聯失效，結束算法。

若對路網中節點14擴容2.92倍，對節點4擴容1.99倍，能有效預防節點2遭受攻擊時引起的級聯失效。同樣，若對路網其他節點或多個節點進行攻擊，也可以采用該擴容策略來預防級聯失效的發生。

表6 節點4擴容Ke后各節點飽和度和阻塞程度指標Table 6 Each node saturation degree and obstruction index after expansion Keof node 4

4 結論

針對道路交通網絡的特性，結合負荷－容量級聯失效模型，提出了一種預防級聯失效的交叉口擴容策略，即在特定攻擊下，通過優化擴容最擁擠交叉口來避免道路交通網絡的級聯失效。這種級聯失效的預防策略是特定攻擊下的預防策略。如何制定隨機攻擊下道路交通網絡級聯失效的預防策略是下階段的研究重點。

（References）：

［1］吳建軍.城市交通網絡拓撲結構復雜性研究［D］.北京：北京交通大學，2008.（WU Jian－jun.Research on the complexity of the urban traffic network topology［D］.Beijing：Beijing Jiaotong University，2008.（in Chinese））

［2］李勇，呂欣，譚躍進.基于級聯失效的戰域保障網絡節點容量優化［J］.復雜系統與復雜性科學，2009，6（1）：69－76.（LI Yong，LV Xin，TAN Yue－jin.Optimization of battle field support network node capacity based on cascading failures［J］.Complex Systems and Complexity Science，2009，6（1）：69－76.（in Chinese））

［3］劉漳輝，陳國龍，湯振立，等.加權復雜網絡相繼故障的節點動態模型研究［J］.小型微型計算機系統，2013，34（12）：2800－2804.（LIU Zhang－hui，CHEN Guo－long，TANG Zhen－li，et al.Research on node dynamic model of weighted complex networks cascading failures［J］.Small Microcomputer System，2013，34（12）：2800－2804.（in Chinese））

［4］彭晶波，衛國.無線網絡的單節點容量最大化方法［J］.小型微型計算機系統，2009（8）：1507－1509.（PENG Jing－bo，WEI Guo.Single－node method to maximize the capacity of wireless networks［J］.Small Microcomputer System，2009（8）：1507－1509.（in Chinese））

［5］Motter A E.Cascade control and defense in complex networks［J］.Physics Review Letter，2004，93（9）：1－4.

［6］Zhao L，Park K，Lai Y C，et al.Tolerance of scale－free networks against attack－induced cascades［J］.Physics Review E，2005，72：25－31.

［7］Hayashi Y，Miyazaki T.Emergent rewirings for cascades on correlated networks［J］.Disordered Systems and Neural Networks，2005，25：1－5.

［8］Sch?fer M，Scholz J，Greiner M.Proactive robustness control of heterogeneously loaded networks［J］.Physical Review Letters，2006，96（10）：108－114.

［9］Motter A E，Lai Y C.Cascade－based attacks on complex networks［J］.Physics Review E，2002，66（6）：65－70.

［10］趙暉.一般輸運網絡演化模型及動力學特征的相關研究［D］.北京：北京交通大學，2007.（ZHAO Hui.Research in general transport network evolution model and its kinetic characteristics［D］.Beijing：Beingjing Jiaotong University，2007.（in Chinese））

［11］Wu J，Gao Z，Sun H.Cascade and breakdown in scale－free networks with community structure［J］.Physical Review E，2006，74（6）：66－72.

［12］Zheng J F，Gao Z Y，Zhao X M.Modeling cascading failures in congested complex networks［J］.Physica A：Statistical Mechanics and its Applications，2007，385（2）：700－706.

［13］Li B，Li F，Wang R.Modeling capacity of road network based on level of service of network［A］.Proceedings of 2008International Conference on Intelligent Computation Technology and Automation（ICICTA）［C］.Changsha：［s.n.］，2008：626－630.