通信網(wǎng)絡(luò)級聯(lián)失效建模與仿真分析

趙剛，周磊

（中國電子科技集團(tuán)公司第二十研究所，西安 710068）

0　引言

21世紀(jì)是一個以網(wǎng)絡(luò)為核心的信息時代，以“數(shù)字化、網(wǎng)絡(luò)化、信息化”為重要特征[1]。通信網(wǎng)絡(luò)是實現(xiàn)信息傳輸與共享的基礎(chǔ)，離開通信網(wǎng)絡(luò)，一切無從談起。當(dāng)今興起的物聯(lián)網(wǎng)、云計算、大數(shù)據(jù)等新興技術(shù)正在日益蓬勃發(fā)展，正在不斷改善信息世界[2]-[3]。在國防建設(shè)中，通信網(wǎng)絡(luò)的重要性不言而喻，通信網(wǎng)絡(luò)作為信息化條件下的“神經(jīng)網(wǎng)絡(luò)”，將分布在不同空間與平臺的傳感器、指揮控制和武器系統(tǒng)連接成為一個有機(jī)、統(tǒng)一、高效的巨型系統(tǒng)，實現(xiàn)戰(zhàn)場態(tài)勢信息和武器共享。以數(shù)據(jù)鏈為代表的軍用通信網(wǎng)絡(luò)正在悄然決定一個國家的國防與作戰(zhàn)能力[4]-[5]，通過數(shù)據(jù)鏈，將所有戰(zhàn)場人員信息、作戰(zhàn)平臺分布信息、武器信息等所有信息實現(xiàn)快速、全面、可靠共享，作戰(zhàn)人員可以迅速了解瞬息萬變的戰(zhàn)場環(huán)境、接受指揮人員的實時指令，快速利用戰(zhàn)場資源，發(fā)揮作戰(zhàn)人員的核心優(yōu)勢[6]。

通信網(wǎng)絡(luò)的核心部件是路由交換設(shè)備，眾多設(shè)備由鏈路連接組成通信網(wǎng)絡(luò)。數(shù)據(jù)包在通信網(wǎng)絡(luò)可能需要經(jīng)過多個中間節(jié)點的轉(zhuǎn)發(fā)才能到達(dá)目的節(jié)點。然而，網(wǎng)絡(luò)中的路由設(shè)備或者鏈路經(jīng)常發(fā)生長時間或短暫故障，造成網(wǎng)絡(luò)狀態(tài)變化，容易造成網(wǎng)絡(luò)時延增加、中斷、甚至故障傳播效應(yīng)而導(dǎo)致的大規(guī)模癱瘓事件。這種由于一個或者少量網(wǎng)絡(luò)要素（節(jié)點或鏈路）超負(fù)載或者故障而導(dǎo)致其他網(wǎng)絡(luò)或網(wǎng)內(nèi)節(jié)點出現(xiàn)相繼超負(fù)載或者故障，且造成較大規(guī)模的網(wǎng)絡(luò)遭受影響的現(xiàn)象，被稱為“雪崩”或“級聯(lián)”現(xiàn)象，也稱為級聯(lián)失效[4]-[5]。

級聯(lián)失效造成的后果非常嚴(yán)重。在其他諸如電力網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等網(wǎng)絡(luò)空間中對級聯(lián)現(xiàn)象均有所深入探究，級聯(lián)失效在通信網(wǎng)絡(luò)中的傳播機(jī)理研究對改進(jìn)網(wǎng)絡(luò)魯棒性具有關(guān)鍵作用，分析通信網(wǎng)絡(luò)中的級聯(lián)現(xiàn)象傳播的原理，可以為設(shè)置應(yīng)對措施奠定基礎(chǔ)。從而減少或避免網(wǎng)絡(luò)擁塞或失效事件出現(xiàn)的概率，進(jìn)而在一定程度上降低級聯(lián)現(xiàn)象帶來的經(jīng)濟(jì)損失。此外，網(wǎng)絡(luò)魯棒性的提高，不僅可以提高用戶體驗，還可增強(qiáng)網(wǎng)絡(luò)應(yīng)對級聯(lián)風(fēng)險的能力，進(jìn)而增強(qiáng)通信網(wǎng)絡(luò)系統(tǒng)的抗毀性[4]-[5]。

1　通信網(wǎng)絡(luò)級聯(lián)失效模型

網(wǎng)絡(luò)是級聯(lián)效應(yīng)賴以傳播的基礎(chǔ)。通常情況下，一個網(wǎng)絡(luò)由節(jié)點和鏈路組成，網(wǎng)絡(luò)規(guī)模N為網(wǎng)絡(luò)中的節(jié)點數(shù)，如圖1所示。鏈路可以是有向的，也可以是無向的，網(wǎng)絡(luò)中的鏈路總數(shù)量記為m。鏈路可以有線的，也可以是無線的。

圖1　網(wǎng)絡(luò)級聯(lián)失效模型

在某個時刻，網(wǎng)絡(luò)中節(jié)點i可能遭受自然災(zāi)害、惡意攻擊或隨機(jī)故障而失效，網(wǎng)絡(luò)中的其他節(jié)點也可能因此而受影響發(fā)生失效。一般我們可以知道哪個節(jié)點在什么時候發(fā)生了失效，記為 ti，表示節(jié)點i在ti時刻發(fā)生了失效。那么在一次觀察中，比如一次失效事件，或者在一定的觀察周期內(nèi)，所有失效節(jié)點的發(fā)生失效的時間可以被記錄下來。那么，一個級聯(lián)c可以被定義為c={t1, t2, t3,…, tN}，假設(shè)t>0。若t=0，則表示未發(fā)生失效。

在通信網(wǎng)絡(luò)中，最短路徑路由是常用的路由機(jī)制。每對節(jié)點之間均采用路徑最短的路徑作為傳輸路徑。網(wǎng)絡(luò)中的鏈路網(wǎng)絡(luò)是有向的，因此節(jié)點有入度和出度之分，分別用表示節(jié)點i的入度與出度，如圖2所示，節(jié)點i的入度和出度分別為3和2。

通信網(wǎng)絡(luò)模型中，重點考慮故障發(fā)生時，流量或負(fù)載的再次平衡問題。當(dāng)某個路由器發(fā)生故障時，一般會采取基于局部的負(fù)載平衡方法，即將失效節(jié)點的負(fù)載交由近鄰節(jié)點承擔(dān)。

圖2　通信網(wǎng)絡(luò)級聯(lián)失效傳播模型

為了評估節(jié)點在通信網(wǎng)絡(luò)中的重要性，提出介數(shù)，即經(jīng)過一個節(jié)點的最短路徑的條數(shù)來表示，即節(jié)點v的介數(shù)定義為式（1）

那么所有節(jié)點的容量需要不小于其穩(wěn)態(tài)負(fù)載才能保證網(wǎng)絡(luò)中所有的節(jié)點不發(fā)生緩存溢出或擁塞。通常假定節(jié)點的容量與穩(wěn)態(tài)負(fù)載或稱為初始負(fù)載成比例，表示為

α為節(jié)點的可接收來在其他節(jié)點負(fù)載能力的系數(shù)。

在穩(wěn)態(tài)時，所有節(jié)點均可正常運轉(zhuǎn)，節(jié)點容量可以很及時處理節(jié)點上的所有負(fù)載。然而，節(jié)點經(jīng)常受到惡意攻擊（針對某些特征的節(jié)點，比如度最大節(jié)點）或隨機(jī)故障，導(dǎo)致節(jié)點發(fā)生失效。失效后，鄰居節(jié)點可以檢測到該失效，并為該失效節(jié)點分擔(dān)流量負(fù)載以保證網(wǎng)絡(luò)的正常運行。在通信網(wǎng)絡(luò)中，數(shù)據(jù)包是從上游節(jié)點發(fā)送給下游節(jié)點，比如圖2中，節(jié)點j2可以將數(shù)據(jù)包轉(zhuǎn)發(fā)給i節(jié)點，反之則不可。那么j2節(jié)點檢測到i失效后，則j2節(jié)點需要分擔(dān)由其轉(zhuǎn)發(fā)給i節(jié)點的負(fù)載，而不是分?jǐn)偨o所有的鄰居節(jié)點。圖2中，當(dāng)節(jié)點i失效后，其上游節(jié)點j1, j2,j3可以局部地為節(jié)點 i分擔(dān)負(fù)載，每個鄰居節(jié)點可以承擔(dān)的部分可以用式（4）表示

式中，'N表示幸存節(jié)點的數(shù)量。也可以用幸存網(wǎng)絡(luò)中最大組件規(guī)模來評估網(wǎng)絡(luò)魯棒性，表示為

（1）基于度的選取，選取度最大的一個節(jié)點作為初始故障點；

（2）隨機(jī)選取。

在隨機(jī)選取方式中，大多采用平均法，即假設(shè)網(wǎng)絡(luò)中的每個節(jié)點都作為初始故障點，將得到的結(jié)果求平均來表示。即

式中，ig表示節(jié)點i作為初始失效節(jié)點時得到的網(wǎng)絡(luò)魯棒性的值。式（3）中的α值直接影響網(wǎng)絡(luò)抵御級聯(lián)故障傳播的能力。一般α值越大，網(wǎng)絡(luò)的魯棒性越好。隨著α值從0開始逐漸增加時，網(wǎng)絡(luò)存在一個相變過程，當(dāng)α＞αc時出現(xiàn)最大幸存組件或一組節(jié)點。

2　仿真分析

基于以上構(gòu)建的通信網(wǎng)絡(luò)級聯(lián)失效模型，假設(shè)某通信網(wǎng)絡(luò)的網(wǎng)絡(luò)規(guī)模N=1000，參數(shù)初始的 m0個節(jié)點全連通，m=2，得到的網(wǎng)絡(luò)的平均度網(wǎng)絡(luò)的魯棒性采用級聯(lián)失效發(fā)生后最終網(wǎng)絡(luò)中幸存的節(jié)點的比例來表示。首先評估節(jié)點在惡意攻擊（即網(wǎng)絡(luò)中節(jié)點的度最大的節(jié)點失效）下，網(wǎng)絡(luò)魯棒性的變化情況。式（3）中的α值是保證節(jié)點可以抵御級聯(lián)失效的關(guān)鍵參數(shù)。但是在實際網(wǎng)絡(luò)中不可能是無限大，因為網(wǎng)絡(luò)資源往往是有限而寶貴的。α在從小到大的增長過程中，會出現(xiàn)一個關(guān)鍵值cα使得網(wǎng)絡(luò)的狀態(tài)出現(xiàn)一個相變過程，即從網(wǎng)絡(luò)完全癱瘓到出現(xiàn)幸存節(jié)點。當(dāng)然，cα越小，表示網(wǎng)絡(luò)的魯棒性越好。

圖3的結(jié)果是采用了10幅同等規(guī)模的網(wǎng)絡(luò)模型仿真后計算得到的平均值。可以看出當(dāng)0.6α＞時，網(wǎng)絡(luò)中出現(xiàn)幸存節(jié)點。當(dāng)然，我們期望α值越大越好，越大可以越好地提高網(wǎng)絡(luò)的魯棒性。但事實并非如此，在網(wǎng)絡(luò)部署的過程中，部署代價是關(guān)鍵因素。但是，在部署中，應(yīng)該提前充分考慮級聯(lián)現(xiàn)象出現(xiàn)的幾率，提前預(yù)留一定的資源來盡量避免級聯(lián)現(xiàn)象造成嚴(yán)重的后果，從而實現(xiàn)對網(wǎng)絡(luò)的保護(hù)，提高網(wǎng)絡(luò)的質(zhì)量。

圖4的結(jié)果展示了隨機(jī)故障下網(wǎng)絡(luò)魯棒性隨α的變化情況。假定每幅網(wǎng)絡(luò)中每個節(jié)點都作為初始失效節(jié)點后得到的節(jié)點再求平均，共計 10幅網(wǎng)絡(luò)最終求平均。可以看出，在隨機(jī)故障中，網(wǎng)絡(luò)可以較好地抵御隨機(jī)故障。

圖3　網(wǎng)絡(luò)魯棒性在蓄意攻擊下的變化情況

一般度大的節(jié)點在網(wǎng)絡(luò)中的重要性比較大，不同度的節(jié)點作為初始失效節(jié)點時得到的結(jié)果亦不同，針對不同度的節(jié)點作為初始失效節(jié)點的結(jié)果進(jìn)行對比仿真，結(jié)果如圖 5所示。整體上可以看出，網(wǎng)絡(luò)的魯棒性與節(jié)點的度k與參數(shù)α密切相關(guān)。同樣，當(dāng) k值相同時，α值越大，網(wǎng)絡(luò)魯棒性越好。α相同時，節(jié)點度越小，網(wǎng)絡(luò)的魯棒性會略好。

選取網(wǎng)絡(luò)中度分別為2、10、50的節(jié)點進(jìn)行仿真，從仿真的結(jié)果（如圖 6）可以看出，初始失效節(jié)點的度越大，造成的網(wǎng)絡(luò)失效后果越嚴(yán)重，cα值隨著度增大而增大。在實際通信網(wǎng)絡(luò)中，度大的節(jié)點往往處于網(wǎng)絡(luò)比較核心的地方，也應(yīng)該是網(wǎng)絡(luò)服務(wù)商重點保護(hù)的節(jié)點。節(jié)點越重要，受攻擊時網(wǎng)絡(luò)受到的損失往往也是越嚴(yán)重的。

為了進(jìn)一步驗證結(jié)果，針對網(wǎng)絡(luò)魯棒性隨初始失效節(jié)點度的變化情況進(jìn)行了仿真。從仿真結(jié)果（如圖 7）上看，初始節(jié)點的度越大，網(wǎng)絡(luò)的魯棒性越小。

圖4　隨機(jī)故障下網(wǎng)絡(luò)魯棒性的演進(jìn)情況

圖5　網(wǎng)絡(luò)魯棒性隨著度k與參數(shù)的變化情況

圖6　網(wǎng)絡(luò)魯棒性在不同度k下隨α的變化情況

圖7　網(wǎng)絡(luò)魯棒性在不同α下隨度的變化情況

3　結(jié)論

本文建立了通信網(wǎng)絡(luò)的級聯(lián)失效模型，并對網(wǎng)絡(luò)在蓄意攻擊和隨機(jī)故障下的魯棒性進(jìn)行了仿真分析，發(fā)現(xiàn)網(wǎng)絡(luò)在蓄意攻擊和隨機(jī)故障下，隨著節(jié)點負(fù)載能力的增加，網(wǎng)絡(luò)的魯棒性均可以變好，但在蓄意攻擊下，網(wǎng)絡(luò)會有一個相變過程，在實際部署通信網(wǎng)絡(luò)時，應(yīng)該給網(wǎng)絡(luò)中的節(jié)點負(fù)載留有足夠的裕量，用以提升網(wǎng)絡(luò)在遭受蓄意攻擊和隨機(jī)故障情況下的魯棒性。通過對不同節(jié)點負(fù)載能力與度對網(wǎng)絡(luò)魯棒性影響的仿真分析發(fā)現(xiàn)，初始失效節(jié)點的度越大，造成網(wǎng)絡(luò)級聯(lián)失效的后果越嚴(yán)重，因此，在實際的網(wǎng)絡(luò)維護(hù)中，需要重點保護(hù)網(wǎng)絡(luò)中度較大的節(jié)點，以提升網(wǎng)絡(luò)的魯棒性。