劉青霞,王 邦

1華中科技大學(xué)電子信息與通信學(xué)院 武漢 中國 430074

1 引言

現(xiàn)實世界的系統(tǒng)和網(wǎng)絡(luò)并不總是穩(wěn)定。2003年8月 14日,美國東北部以及加拿大東部地區(qū)出現(xiàn)的嚴(yán)重停電事故,就是因為少量輸電線路的故障破壞了電網(wǎng)穩(wěn)定性,最終導(dǎo)致大范圍的電網(wǎng)崩潰[1]。2017年5月12日,全球范圍爆發(fā)的Wannacry病毒勒索事件,源于病毒利用微軟操作系統(tǒng)漏洞進(jìn)行大規(guī)模傳播,從而導(dǎo)致超過 20萬臺電腦主機遭受到攻擊[2]。計算機網(wǎng)絡(luò)、通信網(wǎng)絡(luò),以及交通系統(tǒng)、電力系統(tǒng)等具有網(wǎng)絡(luò)化結(jié)構(gòu)的基礎(chǔ)設(shè)施等,在內(nèi)部故障或外部攻擊下處于低效率的工作狀態(tài)甚至完全崩潰,對社會的運轉(zhuǎn)和人們的生活有著巨大影響。

研究者們基于復(fù)雜網(wǎng)絡(luò)理論對網(wǎng)絡(luò)失效機制進(jìn)行了深入研究[3]。隨機故障或蓄意攻擊造成一些網(wǎng)元失效(即節(jié)點、連邊失效),而失效的網(wǎng)元會影響其相鄰網(wǎng)元的工作狀態(tài),并引發(fā)更多網(wǎng)元失效,即失效在網(wǎng)絡(luò)中傳播,形成網(wǎng)絡(luò)的級聯(lián)失效過程。網(wǎng)元失效使得網(wǎng)絡(luò)的連通度降低,而當(dāng)失效網(wǎng)元數(shù)量達(dá)到一定比例時,網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)突然崩潰,不再存在較大尺度的巨連通集團,網(wǎng)絡(luò)功能不再能滿足網(wǎng)絡(luò)的基本運行要求,這也稱之為網(wǎng)絡(luò)的滲流相變。從攻擊的角度,大量的研究建模了網(wǎng)絡(luò)的級聯(lián)失效過程和滲流相變現(xiàn)象[4-7],也提出了多種攻擊策略,目的是為了高效破壞網(wǎng)絡(luò),加快崩潰進(jìn)程,如: 基于節(jié)點中心性的攻擊[8]、基于關(guān)節(jié)節(jié)點的攻擊[9]、基于節(jié)點集體影響力的攻擊[10]、基于節(jié)點集合的攻擊[11-12]等。

另一方面,網(wǎng)絡(luò)恢復(fù)機制主要研究網(wǎng)絡(luò)失效后應(yīng)采取何種策略治愈失效網(wǎng)元,從而盡快恢復(fù)網(wǎng)絡(luò)的正常功能,這對于保護重要網(wǎng)絡(luò)和基礎(chǔ)設(shè)施的正常運行具有極為重要的意義。研究者們提出網(wǎng)絡(luò)彈性的概念,用以描述網(wǎng)元失效時的網(wǎng)絡(luò)防護和恢復(fù)能力。針對不同的網(wǎng)絡(luò)類型和失效機制,近年來一些研究提出了不同的網(wǎng)絡(luò)恢復(fù)策略用以增強網(wǎng)絡(luò)彈性。本文重點關(guān)注在網(wǎng)絡(luò)失效過程中的網(wǎng)絡(luò)應(yīng)急恢復(fù)機制。首先介紹網(wǎng)絡(luò)彈性的概念,接著梳理了最近幾年網(wǎng)絡(luò)恢復(fù)機制的相關(guān)研究,并以基礎(chǔ)設(shè)施網(wǎng)絡(luò)舉例說明網(wǎng)絡(luò)恢復(fù)策略的應(yīng)用,最后對未來研究發(fā)展方向進(jìn)行了展望。

2 網(wǎng)絡(luò)彈性

2.1 相關(guān)概念

彈性通用于表示實體或系統(tǒng)承受、適應(yīng)破壞,并從中恢復(fù)的能力[13]。本文探討的網(wǎng)絡(luò)彈性主要是指當(dāng)網(wǎng)絡(luò)出現(xiàn)級聯(lián)失效時,網(wǎng)絡(luò)維持或恢復(fù)原有功能的能力(性能可能有所降低)。例如,基礎(chǔ)設(shè)施安全合作協(xié)會[14]這樣定義具有彈性的基礎(chǔ)設(shè)施網(wǎng)絡(luò): 網(wǎng)絡(luò)能預(yù)防、應(yīng)對或緩解任何預(yù)期或意料之外的重大安全事件,并能以最小的損失迅速恢復(fù)并重新配置關(guān)鍵資源和服務(wù)。

網(wǎng)絡(luò)彈性主要體現(xiàn)在兩個方面: 在網(wǎng)元失效后,控制網(wǎng)絡(luò)級聯(lián)失效規(guī)模的防護能力,以及在發(fā)生級聯(lián)失效時,網(wǎng)絡(luò)的快速恢復(fù)能力。網(wǎng)元失效的原因很多,大體上可以分為三種,即隨機故障、蓄意攻擊和局部破壞。隨機故障往往表現(xiàn)為網(wǎng)絡(luò)中節(jié)點或連邊的內(nèi)部故障,具有自發(fā)性、不確定性。蓄意攻擊則是外部為破壞網(wǎng)絡(luò)功能而利用某種策略選擇性攻擊特別的節(jié)點或連邊。隨機故障和蓄意攻擊針對全局網(wǎng)絡(luò)而言,失效網(wǎng)元分布在整個網(wǎng)絡(luò)。局部破壞則體現(xiàn)在使得某一特定地理區(qū)域內(nèi)子網(wǎng)絡(luò)的所有節(jié)點和連邊聚集性失效,例如現(xiàn)實中自然災(zāi)害(如地震等)或大規(guī)模攻擊(如轟炸等)而造成某一地區(qū)的網(wǎng)絡(luò)失效。

少量網(wǎng)元失效可能引發(fā)大規(guī)模的網(wǎng)絡(luò)級聯(lián)失效,甚至造成網(wǎng)絡(luò)崩潰。在網(wǎng)元失效后,網(wǎng)絡(luò)的防護機制通過實施預(yù)設(shè)的防護策略來減緩網(wǎng)絡(luò)的失效過程,阻止大規(guī)模級聯(lián)失效甚至網(wǎng)絡(luò)崩潰的產(chǎn)生。網(wǎng)絡(luò)的防護主要通過預(yù)測脆弱的、可能失效的網(wǎng)元,針對性地進(jìn)行重點保護或資源調(diào)控來實現(xiàn)。針對不同的網(wǎng)絡(luò)類型和運行模式,近些年提出了許多防護策略。一些防護策略依據(jù)中心性指標(biāo)來選擇網(wǎng)絡(luò)中的重要節(jié)點進(jìn)行特別保護,通過防止這些節(jié)點在攻擊下失效來實現(xiàn)對級聯(lián)失效規(guī)模的控制[15-16]。Wang等[17]根據(jù)節(jié)點負(fù)荷分布來選擇一些特定的節(jié)點進(jìn)行保護,減少這些節(jié)點過載時的負(fù)荷,使其不易失效,維持正常工作狀態(tài)。一些預(yù)防機制通過設(shè)置一些備份連邊,平時不啟用,而只有在網(wǎng)絡(luò)結(jié)構(gòu)遭到破壞時才啟用來替代失效連邊,從而維持網(wǎng)絡(luò)的連通性和功能[18-20]。一些預(yù)防機制則從網(wǎng)絡(luò)結(jié)構(gòu)出發(fā),對于具有耦合機制的相依網(wǎng)絡(luò),通過改變不同網(wǎng)絡(luò)間的依賴程度和相依連邊的類型等來增強抵御攻擊的能力[21-25]。特別地,Motter[26]提出一種預(yù)防性移除的防護策略。當(dāng)出現(xiàn)失效網(wǎng)元時,提前移除一些正常節(jié)點,阻止失效節(jié)點將原來所承載的網(wǎng)絡(luò)負(fù)荷傳導(dǎo)到更多節(jié)點,從而預(yù)防更大規(guī)模的網(wǎng)絡(luò)級聯(lián)失效。

網(wǎng)絡(luò)發(fā)生失效后,網(wǎng)絡(luò)的恢復(fù)機制通過治愈失效網(wǎng)元或增加新網(wǎng)元等方式恢復(fù)網(wǎng)絡(luò)的部分或完整功能。本文關(guān)注網(wǎng)元失效引發(fā)級聯(lián)失效時,采用何種策略使得能盡可能短的時間內(nèi)應(yīng)急恢復(fù)網(wǎng)絡(luò)結(jié)構(gòu)和功能。網(wǎng)絡(luò)恢復(fù)機制近幾年得到了重視和研究,主要的恢復(fù)策略可以分為兩種類型: 自發(fā)性恢復(fù)(spontaneous recovery)和指向性恢復(fù)(targeted recovery)。自發(fā)性恢復(fù)主要指的是級聯(lián)失效發(fā)生時,網(wǎng)絡(luò)中受損的部分自發(fā)地恢復(fù)功能的過程。指向性恢復(fù)是指當(dāng)網(wǎng)絡(luò)無法自動恢復(fù)功能或在一定時間內(nèi)無法復(fù)原時,外部合理分配資源對網(wǎng)絡(luò)中嚴(yán)重受損的部分進(jìn)行恢復(fù)的過程。相關(guān)文獻(xiàn)總結(jié)如表1所示。下一章將分別從這兩個方面介紹網(wǎng)絡(luò)的恢復(fù)機制。

表1 網(wǎng)絡(luò)恢復(fù)機制的文獻(xiàn)分類Table 1 Classification of the literature in network recovery mechanism

2.2 評估方法

由于網(wǎng)絡(luò)類型和功能應(yīng)用的多樣性,當(dāng)前對網(wǎng)絡(luò)彈性的具體評價指標(biāo)尚未達(dá)成共識。考慮到一個彈性的網(wǎng)絡(luò)應(yīng)能承受一定數(shù)量的網(wǎng)元失效、控制級聯(lián)失效時的網(wǎng)絡(luò)受損規(guī)模、以及在網(wǎng)絡(luò)受損后能盡快恢復(fù)原有功能,近年來一些文獻(xiàn)提出了幾種概念性的網(wǎng)絡(luò)彈性評估方法,主要結(jié)合網(wǎng)絡(luò)的失效過程和恢復(fù)過程來定義。圖1示意了網(wǎng)絡(luò)失效和恢復(fù)過程中性能的變化,其中橫坐標(biāo)為時間,縱坐標(biāo)為某種網(wǎng)絡(luò)性能度量。以下對幾種網(wǎng)絡(luò)彈性的評估方法進(jìn)行簡介。

Henry等[27]關(guān)注不同階段網(wǎng)絡(luò)的狀態(tài)。如圖1所示,t1之前網(wǎng)絡(luò)為初始狀態(tài),(t1,t2)為網(wǎng)絡(luò)失效過程,(t2,t3)為網(wǎng)絡(luò)破壞待修狀態(tài),(t3,t4)為網(wǎng)絡(luò)恢復(fù)過程,t4之后網(wǎng)絡(luò)恢復(fù)為正常工作狀態(tài)。他們提出了一種網(wǎng)絡(luò)瞬時彈性指標(biāo),該指標(biāo)將t時刻的彈性R(t)量化為恢復(fù)與損失的比率,表示如下:

圖1 網(wǎng)絡(luò)彈性過程示意圖Figure 1 Schematic diagram of the network resilience process

其中,P(t2)是網(wǎng)絡(luò)處于破壞待修狀態(tài)時的性能。

Bruneau等[28]提出當(dāng)級聯(lián)失效發(fā)生后,網(wǎng)絡(luò)性能隨時間改變的大小來衡量網(wǎng)絡(luò)的彈性R。如圖1中陰影所示,陰影的面積越小,網(wǎng)絡(luò)彈性越強。具體數(shù)學(xué)表示如下:

其中t1是級聯(lián)失效發(fā)生的時間,t4是網(wǎng)絡(luò)恢復(fù)正常狀態(tài)的時間。0P是發(fā)生級聯(lián)失效前,網(wǎng)絡(luò)正常運行時的原始性能,通常為常數(shù),P(t)是時刻t的網(wǎng)絡(luò)性能。

Ouyang等[29]將整個過程分為三個階段,如圖1所示,t1之前為災(zāi)難預(yù)防階段,(t1,t2)為損害傳播階段,(t2,t4)為評估和恢復(fù)階段。這三個階段可以分別反映災(zāi)難攻擊下系統(tǒng)的抵抗能力,吸收能力和恢復(fù)能力,這些能力共同決定了整個階段內(nèi)的系統(tǒng)彈性。進(jìn)一步,彈性被定義為一定階段時間(t1,t4)內(nèi)網(wǎng)絡(luò)理想正常工作性能與攻擊下真實工作性能的比值:

崔瓊等[30]依據(jù)不同階段下網(wǎng)絡(luò)的性能P(t),分別度量網(wǎng)絡(luò)的狀態(tài)保持能力a,吸收擾動的能力b和恢復(fù)能力c,并定義網(wǎng)絡(luò)的彈性為R=a?b?c,其中:

3 自發(fā)性恢復(fù)

自發(fā)性恢復(fù)主要表現(xiàn)為網(wǎng)絡(luò)中的每個節(jié)點或連邊在失效之后均有機會自行恢復(fù)到正常工作狀態(tài),即具有本地決策和獨立修復(fù)的特性。本節(jié)對自發(fā)性恢復(fù)的相關(guān)研究進(jìn)行梳理,重點介紹基礎(chǔ)的自發(fā)性恢復(fù)模型,包括網(wǎng)絡(luò)失效和網(wǎng)絡(luò)恢復(fù)等。

自發(fā)性恢復(fù)的研究中,較為常見的失效與傳播可以建模為如下兩個過程: (1)內(nèi)部自生故障: 一個節(jié)點在時間間隔t內(nèi)獨立地依概率p發(fā)生故障; (2)外部誘發(fā)故障: 未發(fā)生內(nèi)部故障的節(jié)點為正常節(jié)點。如果一個正常節(jié)點的鄰居節(jié)點在時間間隔t中因故障失效的比例大于某一閾值,則該節(jié)點也可能依概率p′發(fā)生故障。

網(wǎng)絡(luò)的自發(fā)性恢復(fù)依據(jù)節(jié)點能否完全自愈可以建模為兩種基礎(chǔ)類型: (1)完全恢復(fù): 失效節(jié)點在時間段τ≠0之后能從內(nèi)部自生故障完全恢復(fù)為正常狀態(tài),在時間段τ′≠0之后能從外部誘發(fā)故障完全恢復(fù)[31];(2)概率恢復(fù): 失效節(jié)點依概率q或概率q′分別從內(nèi)部和外部故障自發(fā)恢復(fù)[32]。研究發(fā)現(xiàn),相比概率恢復(fù),完全恢復(fù)策略更能增強網(wǎng)絡(luò)抵御大規(guī)模網(wǎng)絡(luò)故障的能力[33]。

基于上述自發(fā)性恢復(fù)模型,研究者們主要關(guān)注整個網(wǎng)絡(luò)隨時間的動態(tài)演化過程[31]。初始階段內(nèi)部自生故障占主導(dǎo),失效傳播引發(fā)更多的外部誘發(fā)故障,導(dǎo)致網(wǎng)絡(luò)的級聯(lián)失效。通過控制內(nèi)部失效概率和外部失效概率得到相圖,發(fā)現(xiàn)引入完全恢復(fù)過程會導(dǎo)致網(wǎng)絡(luò)具有一階相變和遲滯(hysteresis)的臨界行為,即自發(fā)地崩潰和恢復(fù),出現(xiàn)狀態(tài)切換現(xiàn)象。如圖2所示,綠色區(qū)域中網(wǎng)絡(luò)處于高性能狀態(tài),橙色區(qū)域中網(wǎng)絡(luò)處于低性能狀態(tài),兩者重疊的紫色區(qū)域則為遲滯區(qū)域,即兩種狀態(tài)均可能存在。

圖2 動態(tài)恢復(fù)過程下的相圖(來自文獻(xiàn)[31])Figure 2 Phase diagram under dynamic recovery process(from[31])

文獻(xiàn)[34]對相依網(wǎng)絡(luò)上的自發(fā)恢復(fù)過程進(jìn)行了研究。特別地,對于一對一連接的相依網(wǎng)絡(luò),需要考慮故障通過兩個網(wǎng)絡(luò)間的相依連邊傳播的可能性,即相依故障: 如果網(wǎng)絡(luò)中的一個節(jié)點發(fā)生故障,則有一定的概率p′′,在時間t內(nèi)使得通過相依連邊連接在另一個網(wǎng)絡(luò)中的節(jié)點發(fā)生故障。對應(yīng)地,在完全恢復(fù)模型中,節(jié)點會在時間段τ′′≠0之后從相依故障中恢復(fù)。研究發(fā)現(xiàn)相依網(wǎng)絡(luò)中的相位變換變得更加復(fù)雜,如圖3相依網(wǎng)絡(luò)相圖所示,四種不同顏色的曲線劃分出相互重疊的不同區(qū)域,網(wǎng)絡(luò)在區(qū)域中存在的不同狀態(tài)之間轉(zhuǎn)換。而網(wǎng)絡(luò)相互依賴的特性使子網(wǎng)絡(luò)間的狀態(tài)相互影響,即一個網(wǎng)絡(luò)狀態(tài)的轉(zhuǎn)變會引發(fā)另一個網(wǎng)絡(luò)狀態(tài)的轉(zhuǎn)變。

圖3 相依網(wǎng)絡(luò)中的完整相圖(來自文獻(xiàn)[34])Figure 3 Phase diagram in interdependent network(from[34])

在上述自發(fā)恢復(fù)模型的基礎(chǔ)上,研究者們提出了許多改進(jìn)模型,更進(jìn)一步地建模網(wǎng)絡(luò)的自發(fā)恢復(fù)過程,并通過調(diào)整模型參數(shù)設(shè)計更好的恢復(fù)策略。考慮到現(xiàn)實網(wǎng)絡(luò)中存在網(wǎng)元的重復(fù)失效情況,即網(wǎng)元失效自愈后再次失效,且隨著失效自愈次數(shù)的增多,網(wǎng)元再次失效的概率也可能逐漸降低。文獻(xiàn)[35]定義節(jié)點v的失效概率為,其中x為節(jié)點v的失效次數(shù),0﹤p﹤1為故障參數(shù)。此外,失效傳播建模為每個失效節(jié)點以概率致使其鄰居節(jié)點失效。對應(yīng)地,自發(fā)恢復(fù)過程建模為概率q恢復(fù)和τ時長后完全恢復(fù)兩種類型。

文獻(xiàn)[36]進(jìn)一步考慮到現(xiàn)實網(wǎng)絡(luò)中故障傳播的時延性,描述網(wǎng)絡(luò)的動態(tài)失效過程為: 節(jié)點vi以概率失效,并通過連邊傳播故障,其鄰居節(jié)點vj以概率 1 - ( 1 -)kj在一定時τij(α)后失效。其中xi為節(jié)點vi的失效次數(shù),0﹤p﹤1為故障參數(shù),kj為節(jié)點vj的度。時間延遲值被認(rèn)為與失效節(jié)點和受影響節(jié)點都有關(guān)系,且度越大的失效節(jié)點具有越強的抵御故障傳播的能力,能延遲其對鄰居節(jié)點的影響,定義為:其中0﹤α﹤1為可調(diào)參數(shù)。特別地,模型假定當(dāng)節(jié)點的失效次數(shù)達(dá)到某個閾值時,永久失效,從網(wǎng)絡(luò)中移除。對于自發(fā)恢復(fù)過程,失效節(jié)點vi以概率qki恢復(fù)。

對于改進(jìn)后的自發(fā)恢復(fù)模型,文獻(xiàn)[35-36]研究分析了參數(shù)變化下網(wǎng)絡(luò)級聯(lián)失效機制和魯棒性的特征。仿真結(jié)果表明,節(jié)點的恢復(fù)能力隨著恢復(fù)概率q的增大而增強,失效傳播的延遲時間隨參數(shù)α的增大而增加。增大q和α降低了級聯(lián)失效的影響,有效減小失效網(wǎng)絡(luò)的規(guī)模,提高網(wǎng)絡(luò)的魯棒性; 而隨著恢復(fù)時間τ和失效概率逐漸增大,網(wǎng)絡(luò)級聯(lián)失效過程的速度和規(guī)模都呈現(xiàn)出突變增加的趨勢,網(wǎng)絡(luò)的魯棒性也相應(yīng)變小。這些結(jié)論對于理解網(wǎng)絡(luò)的自發(fā)恢復(fù)機制,預(yù)防和控制級聯(lián)失效提供了重要的參考價值。

4 指向性恢復(fù)

指向性恢復(fù)(directional recovery)從如何高效恢復(fù)網(wǎng)絡(luò)整體的結(jié)構(gòu)和功能出發(fā),對失效網(wǎng)元依據(jù)某種策略進(jìn)行重要性排序后,按順序進(jìn)行恢復(fù)。對比自發(fā)性恢復(fù)中,每個失效網(wǎng)元獨立地進(jìn)行本地恢復(fù),指向性恢復(fù)立足于網(wǎng)絡(luò)整體,調(diào)配資源進(jìn)行優(yōu)先恢復(fù),恢復(fù)效率更高。研究者們從不同的角度提出了多種指向性恢復(fù)策略,大體可以分為兩類: 一種是基于原始網(wǎng)絡(luò)結(jié)構(gòu)的恢復(fù),通過恢復(fù)失效的節(jié)點和連邊,以達(dá)到恢復(fù)原始網(wǎng)絡(luò)結(jié)構(gòu)和功能的目的; 另一種則是改變原始網(wǎng)絡(luò)結(jié)構(gòu)的恢復(fù),通過向已損壞的網(wǎng)絡(luò)中添加新節(jié)點或新連邊以恢復(fù)網(wǎng)絡(luò)功能。

4.1 基于原始結(jié)構(gòu)的恢復(fù)

網(wǎng)絡(luò)恢復(fù)作為一種應(yīng)急機制,主要是在原始網(wǎng)絡(luò)受到破壞或遭受攻擊后展開。以下分別從網(wǎng)絡(luò)的局部破壞、全局攻擊和負(fù)荷過載這三類情況對恢復(fù)策略進(jìn)行總結(jié)。

4.1.1 局部破壞下的恢復(fù)

局部攻擊或突發(fā)災(zāi)害會使得特定區(qū)域子網(wǎng)絡(luò)的節(jié)點和連邊產(chǎn)生聚集性失效[37-38]。如圖4中A和B所示。網(wǎng)絡(luò)以紅色連邊為中心受到局部破壞,藍(lán)色和黃色的連邊隨著與紅色連邊距離的增大,受到的破壞程度逐漸減弱。兩條連邊之間的距離定義為從一條連邊的中點到另一條連邊的垂直距離?；疑珔^(qū)域的暗度越大代表受到破壞的程度越大,當(dāng)破壞超過承受閾值時連邊失效,最后網(wǎng)絡(luò)中的局部區(qū)域剩余黃色孤立節(jié)點,越大的節(jié)點具有越大的固有權(quán)重。Hu等[39]針對局部破壞后的網(wǎng)絡(luò)提出了兩種恢復(fù)策略,分別具體介紹如下。

外圍恢復(fù)策略(Periphery Recovery,PR)[39],將網(wǎng)絡(luò)巨連通分量中具有至少一條失效連邊的節(jié)點看作外圍節(jié)點,該策略優(yōu)先選擇與外圍節(jié)點之間存在失效連邊且權(quán)重最大的孤立節(jié)點,依次恢復(fù)與其相鄰接的失效連邊。如圖4中C1~C3,藍(lán)色連邊為外圍節(jié)點的失效連邊。n1為首次選擇的權(quán)重最大的孤立節(jié)點,恢復(fù)其上失效連邊m1和m2,之后繼續(xù)選擇節(jié)點n2,恢復(fù)m3和m4。第τ次選擇節(jié)點,需要恢復(fù)的連邊 集 合 Lτ為:其中eij表示節(jié)點vi和vj之間的連邊,ωj是節(jié)點vj的權(quán)重,P是外圍節(jié)點集合,Ω是孤立節(jié)點集合,A為鄰接矩陣。

圖4 局部攻擊及兩種恢復(fù)過程示意圖(來自文獻(xiàn)[39]): 圖A為局部攻擊下的受損網(wǎng)元示意圖; 圖B為攻擊后的網(wǎng)絡(luò)剩余網(wǎng)元示意圖; 圖C1~C3為PR下的恢復(fù)過程示意圖; 圖D1~D4為PRNW下的恢復(fù)過程示意圖Figure 4 Illustration of localised attack and two recovery processes(from[39])

基于節(jié)點權(quán)重的優(yōu)先恢復(fù)策略(Preferential Recovery based on Nodal Weight,PRNW)[39],該策略直接選擇權(quán)重最大的孤立節(jié)點,依次恢復(fù)其到網(wǎng)絡(luò)巨連通分量中最短路徑上的連邊。如圖4中D1~D4,首先選擇權(quán)重最大的孤立節(jié)點n3,恢復(fù)連邊m5; 然后剩余節(jié)點中權(quán)重最大的節(jié)點n4,選擇其到巨連通分量的最短路徑上的一組連邊,依次恢復(fù)連邊m6和m7; 之后選擇節(jié)點n5,恢復(fù)連邊m8。第τ次選擇節(jié)點,需要恢復(fù)的連邊集合Lτ表示為: Lτ=其中eij表示節(jié)點vi和vj之間的連邊,Path(s,t)是節(jié)點vs和vt之間的最短路徑上的一組連邊,vt是所有孤立節(jié)點中權(quán)重最大的節(jié)點,并且vs是網(wǎng)絡(luò)巨連通分量中最接近vt的節(jié)點,策略按從vs到vt的連邊順序恢復(fù)。

對于上述兩種策略,Hu等[39]定義恢復(fù)效率為網(wǎng)絡(luò)恢復(fù)后的性能與網(wǎng)絡(luò)失效時的性能之間比值,通過計算機仿真對比策略的恢復(fù)效率。研究結(jié)果表明,在網(wǎng)絡(luò)恢復(fù)的初始階段,PR恢復(fù)效率要高于PRNW。這是由于權(quán)重最大的節(jié)點可能遠(yuǎn)離巨連通網(wǎng)絡(luò),它們之間最短路徑上恢復(fù)的大部分為權(quán)重較小節(jié)點的連邊,使得 PRNW 的恢復(fù)水平早期較低。在恢復(fù)的連邊數(shù)逐漸增多后,PRNW 的恢復(fù)效率要高于 PR,因為PR重新連接的節(jié)點不一定是網(wǎng)絡(luò)中權(quán)重最大的,對整體網(wǎng)絡(luò)性能恢復(fù)的效率較低。特別地,PRNW具有較低的計算復(fù)雜度,在提高網(wǎng)絡(luò)整體連通性上有很好的表現(xiàn)?，F(xiàn)實中自然災(zāi)害等導(dǎo)致的局部破壞往往出現(xiàn)在基礎(chǔ)設(shè)施網(wǎng)絡(luò)上,而基礎(chǔ)設(shè)施網(wǎng)絡(luò)具有較強的相互依賴性。但這兩類算法[39]主要針對單個網(wǎng)絡(luò),在實際應(yīng)用中有一定的局限性。

Gong等[40]研究了相依網(wǎng)絡(luò)上節(jié)點的局部攻擊導(dǎo)致的網(wǎng)絡(luò)級聯(lián)失效。不同于前述[39]針對連邊的局部攻擊,針對節(jié)點的局部攻擊建模為: 以一個節(jié)點為中心,一定距離內(nèi)的所有節(jié)點全部失效,而網(wǎng)絡(luò)間相依邊的存在使得失效在相依網(wǎng)絡(luò)中傳播擴散?？紤]到度越小的節(jié)點在下一時刻與巨連通分量斷開連接而失效的可能性越大,Gong等[40]提出了優(yōu)先最小度恢復(fù)策略(Healing Strategy by Prioritizing Minimum Degrees,HPMD),計算所有失效節(jié)點的正常鄰居節(jié)點對(vi,vj)之間的恢復(fù)優(yōu)先值 H (i,j) = ki+kj,其中ki表示節(jié)點vi當(dāng)前時刻的度。HPMD按恢復(fù)優(yōu)先值的升序在節(jié)點對之間建立連邊(不允許自環(huán)和重邊),通過增強較小度的節(jié)點的連通性能,阻止失效傳播規(guī)模,從而能提高網(wǎng)絡(luò)魯棒性。該策略針對相依網(wǎng)絡(luò)、利用節(jié)點的局部信息,較適用于實際網(wǎng)絡(luò)的恢復(fù)場景。

4.1.2 全局攻擊下的恢復(fù)

全局攻擊針對網(wǎng)絡(luò)中的所有節(jié)點,依據(jù)節(jié)點的重要性指標(biāo)從大到小對節(jié)點進(jìn)行排序,然后選擇節(jié)點進(jìn)行攻擊,常用的重要性指標(biāo)包括各類中心性指標(biāo),如: 度中心性,介數(shù)中心性,接近中心性,K-核指標(biāo)等[41-42]。如圖5所示,紅色的節(jié)點和連邊為基于度中心性選擇攻擊的節(jié)點及對應(yīng)的失效連邊。攻擊這些節(jié)點后,網(wǎng)絡(luò)瓦解為多個子分量,圖中用不同顏色代表。網(wǎng)絡(luò)的恢復(fù)過程可以看作網(wǎng)絡(luò)失效的逆過程,傳統(tǒng)恢復(fù)策略根據(jù)失效節(jié)點在原網(wǎng)絡(luò)的中心性指標(biāo)按照重要性從大到小對節(jié)點進(jìn)行排序,然后依次進(jìn)行恢復(fù)。該類恢復(fù)策略針對網(wǎng)絡(luò)中的所有失效節(jié)點,旨在恢復(fù)網(wǎng)絡(luò)的整體功能; 而在現(xiàn)實中,某些目標(biāo)節(jié)點的及時恢復(fù)可能比網(wǎng)絡(luò)整體的完全恢復(fù)更加重要。下面介紹近年來提出的全局攻擊下針對不同關(guān)鍵節(jié)點的恢復(fù)策略。

圖5 基于度中心性的全局攻擊示意圖Figure 5 Schematic illustration of global attacks based on degree centrality

Sun和Wang[43]考慮了不同類型的目標(biāo)節(jié)點,如:度較大的失效節(jié)點、分布在給定范圍內(nèi)的失效節(jié)點等,提出了一種基于目標(biāo)節(jié)點的局部介數(shù)中心性的恢復(fù)指標(biāo),定義為:,其中σst表示節(jié)點vs和節(jié)點vt之間最短路徑的總數(shù),σst( i)表示節(jié)點vs和節(jié)點vt之間通過節(jié)點vi的最短路徑的總數(shù),不同于常用的介數(shù)中心性,指標(biāo)中U為目標(biāo)節(jié)點集合。研究結(jié)果表明,基于局部介數(shù)中心性的恢復(fù)策略在使目標(biāo)節(jié)點功能的恢復(fù)上表現(xiàn)優(yōu)于傳統(tǒng)恢復(fù)策略。類似地,他們[43]定義節(jié)點的局部接近中心性為,提出了混合局部介數(shù)中心性和局部接近中心性的恢復(fù)指標(biāo)。該混合指標(biāo)考慮了更多的網(wǎng)絡(luò)結(jié)構(gòu)特性,在恢復(fù)網(wǎng)絡(luò)效率的效果上比單獨的局部中心性表現(xiàn)更好。該類局部中心性指標(biāo)的提出關(guān)注到了具體的恢復(fù)目標(biāo)問題,值得后續(xù)進(jìn)一步研究。

Shang[44]關(guān)注距離正常節(jié)點較近的失效節(jié)點,提出了層級恢復(fù)策略: 將完整網(wǎng)絡(luò)轉(zhuǎn)化為以一節(jié)點為中心的層次分布結(jié)構(gòu)。遭受全局攻擊后,按照距離中心節(jié)點的遠(yuǎn)近依次恢復(fù)失效節(jié)點及其連邊。該策略的出發(fā)點為,現(xiàn)實網(wǎng)絡(luò)中恢復(fù)正常工作節(jié)點鄰近的節(jié)點通常比恢復(fù)距離較遠(yuǎn)的節(jié)點更容易。具體地,層次分布結(jié)構(gòu)如圖6所示,隨機選擇一個節(jié)點作為中心節(jié)點,所有節(jié)點按照到中心節(jié)點的距離劃分為L層,圖中每層節(jié)點分布在顏色不同的虛線上。假設(shè)初始網(wǎng)絡(luò)中共有1-p比例的節(jié)點失效,圖中剩余節(jié)點為黑色。從中心到外層依次恢復(fù)失效節(jié)點,同一層的失效節(jié)點按隨機順序恢復(fù)。當(dāng)?shù)贚層的所有失效節(jié)點全部恢復(fù)后,才開始恢復(fù)第L+1層的失效節(jié)點。圖中恢復(fù)后的節(jié)點變?yōu)閷?yīng)層顏色,空心節(jié)點為當(dāng)前剩余失效節(jié)點,虛線為當(dāng)前失效連邊,圖示狀態(tài)下將繼續(xù)恢復(fù)第二層中的失效節(jié)點。研究結(jié)果表明,相比隨機恢復(fù)策略,層級恢復(fù)策略具有更高的恢復(fù)效率。值得注意的是,該策略的表現(xiàn)受網(wǎng)絡(luò)結(jié)構(gòu)特性的影響,度分布較均衡的同配網(wǎng)絡(luò)中存在“恢復(fù)阻力”使得策略效率減弱。因此,需要考慮如何設(shè)計不同屬性網(wǎng)絡(luò)下的恢復(fù)策略。

圖6 層級恢復(fù)過程示意圖(修改自文獻(xiàn)[44])Figure 6 Schematic illustration of the shell recovery process(modified from[44])

Muro等[45]關(guān)注相依網(wǎng)絡(luò)中與巨連通分量鄰近的節(jié)點,提出了共同邊界節(jié)點優(yōu)先恢復(fù)策略。將相依網(wǎng)絡(luò)中與巨連通分量有直接連邊的失效節(jié)點集合稱之為邊界。如果一個子網(wǎng)絡(luò)邊界中的節(jié)點與另一個子網(wǎng)絡(luò)中的邊界節(jié)點間有一條相依邊,則這兩個節(jié)點稱之為共同邊界節(jié)點。該策略優(yōu)先恢復(fù)共同邊界失效節(jié)點,并將其重新連接到巨連通分量中。這是考慮到恢復(fù)正常工作網(wǎng)絡(luò)鄰近的節(jié)點更容易; 此外,不在邊界內(nèi)的失效節(jié)點由于未連接到巨連通分量,在相依網(wǎng)絡(luò)間的級聯(lián)失效影響下即使恢復(fù)也將在下一時刻失效。假設(shè)初始有1-p比例的節(jié)點隨機失效,在級聯(lián)失效過程中,策略以概率γ恢復(fù)失效的共同邊界節(jié)點。如圖7所示,圖中空心節(jié)點為網(wǎng)絡(luò)邊界。共同邊界節(jié)點由灰色實線代表的相依邊連接,可以恢復(fù); 而灰色虛線代表的相依邊的兩端不為共同邊界節(jié)點,故不能恢復(fù)。研究發(fā)現(xiàn)存在一個與失效比例相關(guān)的臨界恢復(fù)概率,超過這個概率,級聯(lián)失效就會停止,網(wǎng)絡(luò)完全恢復(fù)到初始狀態(tài); 而低于這個概率,網(wǎng)絡(luò)就會突然崩潰。該策略指出網(wǎng)絡(luò)完全恢復(fù)的可能性,在恢復(fù)受損基礎(chǔ)設(shè)施網(wǎng)絡(luò)方面具有指導(dǎo)性意義。

圖7 邊界節(jié)點恢復(fù)過程示意圖(修改自文獻(xiàn)[45])Figure 7 Schematic illustration of the boundary nodes recovery process(modified from[45])

考慮到現(xiàn)實網(wǎng)絡(luò)資源的有限性,吳佳鍵等[46]對共同邊界節(jié)點優(yōu)先恢復(fù)策略進(jìn)行了改進(jìn)。利用共同邊界節(jié)點在巨連通分量內(nèi)外的連接邊數(shù)定義邊界節(jié)點的重要性,提出一種基于連接邊的擇優(yōu)恢復(fù)算法。在恢復(fù)過程中,遍歷相依網(wǎng)絡(luò)中某一子網(wǎng)絡(luò)上的共同邊界節(jié)點,計算節(jié)點的邊界重要指數(shù),按降序恢復(fù)比例γ的節(jié)點,對應(yīng)子網(wǎng)絡(luò)的耦合節(jié)點同樣恢復(fù)正常。邊界失效節(jié)點vi的重要指數(shù)Ii定義為:,其中表示邊界失效節(jié)點vi與同網(wǎng)絡(luò)的巨連通分量內(nèi)正常節(jié)點存在的失效連邊數(shù),表示邊界節(jié)點vi與同網(wǎng)絡(luò)的巨分量外節(jié)點存在的失效連邊數(shù),參數(shù) β ? [ 0,1]代表兩類連邊的比重。該算法在資源有限的情況下,能高效的恢復(fù)更重要的邊界節(jié)點,從而提高網(wǎng)絡(luò)的結(jié)構(gòu)連通性并控制相依網(wǎng)絡(luò)間的級聯(lián)失效。

4.1.3 負(fù)荷過載下的恢復(fù)

前述的局部破壞和全局攻擊下的網(wǎng)絡(luò)失效模型可以理解為靜態(tài)網(wǎng)絡(luò)的失效過程: 一個節(jié)點失效,則與其相鄰的連邊同時失效; 一條連邊失效,如果其兩端連接的某個節(jié)點變成孤立節(jié)點,則該節(jié)點也失效。除此之外,還有一種負(fù)荷容量模型下的動態(tài)失效模型[47]: 在靜態(tài)的網(wǎng)絡(luò)結(jié)構(gòu)之上,節(jié)點和連邊還承載一定的負(fù)荷,如電力系統(tǒng)的電流,計算機網(wǎng)絡(luò)的數(shù)據(jù)流等。網(wǎng)元承載的負(fù)荷不能超過其容量限制,當(dāng)一個節(jié)點或連邊失效,其鄰接網(wǎng)元不一定失效,但該失效網(wǎng)元會將其原始承載的負(fù)荷按照某種預(yù)設(shè)策略分配到其鄰接網(wǎng)元或其他正常網(wǎng)元上。若這些正常網(wǎng)元的負(fù)荷超過自身的容量限制,再次產(chǎn)生網(wǎng)元失效和負(fù)荷重分配。該過程可能反復(fù)進(jìn)行下去,導(dǎo)致更多網(wǎng)元的承載負(fù)荷超過容量限制,產(chǎn)生網(wǎng)絡(luò)的級聯(lián)失效現(xiàn)象。如圖8所示,藍(lán)色節(jié)點的大小代表其負(fù)荷,在此圖中被定義為通過該節(jié)點的最短路徑的數(shù)量,黑色圓圈代表節(jié)點的容量。在t=1時,箭頭指向的節(jié)點發(fā)生故障,這將改變其余節(jié)點的負(fù)荷,在之后的時刻,部分節(jié)點負(fù)荷超過其容量失效,網(wǎng)絡(luò)出現(xiàn)級聯(lián)失效現(xiàn)象。負(fù)荷容量模型下的恢復(fù)機制可以從恢復(fù)概率和恢復(fù)時間兩個角度進(jìn)行建模?；诨謴?fù)概率,李釗等[49]

圖8 負(fù)荷容量模型下網(wǎng)絡(luò)的時間演化示意圖(修改自文獻(xiàn)[48])Figure 8 Schematic illustration of the time evolution of the network under load-capacity model(modified from[48])

建模網(wǎng)絡(luò)的應(yīng)急恢復(fù)機理為節(jié)點在過載失效后的每個時刻都有一定概率ρ能夠恢復(fù)正常。在基礎(chǔ)的負(fù)荷容量模型下,某一節(jié)點移除后,其鄰居網(wǎng)元按比例承擔(dān)一定負(fù)荷?？紤]到實際網(wǎng)絡(luò)中部分節(jié)點在其負(fù)荷超出容量的時候不會立即失效,而可能以過載狀態(tài)低效率工作。李釗等依據(jù)負(fù)荷和容量之間的關(guān)系提出了不同的失效概率,分別對應(yīng)不同的節(jié)點狀態(tài): 當(dāng)負(fù)荷沒有超出容量時,節(jié)點失效概率為 0,處于正常狀態(tài); 當(dāng)負(fù)荷超出容量規(guī)定比例時,節(jié)點失效概率為 1,處于失效狀態(tài); 而當(dāng)負(fù)荷大小處于兩者之間時,失效概率隨負(fù)荷線性增長,節(jié)點處于過載狀態(tài)。研究結(jié)果表明,恢復(fù)概率ρ對網(wǎng)絡(luò)效率和網(wǎng)絡(luò)故障率有很大的影響,越大的恢復(fù)概率越能有效減緩網(wǎng)絡(luò)效率的降低速度和網(wǎng)絡(luò)節(jié)點故障率的增長速度。

基于恢復(fù)時間,Fu等[50]將恢復(fù)機制建模為依據(jù)中心性指標(biāo)選擇的失效節(jié)點在τ時刻后恢復(fù)正常。為減少失效節(jié)點對網(wǎng)絡(luò)功能恢復(fù)的影響,恢復(fù)后的節(jié)點在恢復(fù)自身功能的基礎(chǔ)上還應(yīng)同時承擔(dān)其他失效節(jié)點的部分負(fù)荷。具體地,恢復(fù)節(jié)點vi承擔(dān)的失效節(jié)點的負(fù)荷為:,其中Пi為節(jié)點vi的失效鄰居節(jié)點集合,來自失效節(jié)點vj的負(fù)荷,Li為節(jié)點vi的初始負(fù)荷,Гj為節(jié)點vj的鄰居節(jié)點集合。當(dāng)來自失效節(jié)點的負(fù)荷超出恢復(fù)節(jié)點的冗余容量時,該節(jié)點將再次失效。研究發(fā)現(xiàn),延時恢復(fù)策略可以降低對外部資源的需求,且延時時間越大需求越小,但同時網(wǎng)絡(luò)的恢復(fù)效率隨之降低,選擇合適的恢復(fù)延時可以有效緩解網(wǎng)絡(luò)恢復(fù)效率與外部資源之間的矛盾。

和上述模型類似,文獻(xiàn)[51-52]提出一種動態(tài)的層修復(fù)策略(Shell Repair Strategy,SRS): 首先根據(jù)失效節(jié)點之間的關(guān)系構(gòu)建失效網(wǎng)絡(luò); 依據(jù)度中心性指標(biāo)對失效節(jié)點按降序排列,依次判斷節(jié)點恢復(fù)后所承擔(dān)的負(fù)荷是否超過其容量; 若沒有超過,則正?；謴?fù)。否則通過增大容量的方法,使其能夠承擔(dān)已失效節(jié)點的負(fù)荷。可以看到,該策略能動態(tài)對恢復(fù)節(jié)點進(jìn)行選擇判斷,找到那些容量較難承擔(dān)負(fù)荷的節(jié)點并進(jìn)行擴容處理,從而降低了節(jié)點恢復(fù)后再次失效的可能性,提高了網(wǎng)絡(luò)恢復(fù)的效率。

同時考慮失效節(jié)點的恢復(fù)時間和恢復(fù)概率,文獻(xiàn)[30,53]建模了如下恢復(fù)機制: 每個失效節(jié)點在時間段τ后以概率ρ恢復(fù)。研究結(jié)果表明,恢復(fù)時間的增加使得網(wǎng)路的級聯(lián)失效規(guī)模增大,網(wǎng)絡(luò)的彈性減弱。當(dāng)恢復(fù)所需時間大到一定程度之后,網(wǎng)絡(luò)的恢復(fù)效率幾乎沒有增大。相比之下,恢復(fù)概率的影響要大于恢復(fù)時間,增加恢復(fù)概率能顯著提升網(wǎng)絡(luò)的恢復(fù)效率。文獻(xiàn)[54-55]中采用單次恢復(fù)機制: 當(dāng)?shù)竭_(dá)時間tr時,隨機選擇網(wǎng)絡(luò)中在tr時失效的ρ比例節(jié)點恢復(fù)。研究發(fā)現(xiàn)存在最佳的恢復(fù)時間點使得網(wǎng)絡(luò)能維持較好的功能。這些研究更多的關(guān)注模型參數(shù)變化對網(wǎng)絡(luò)恢復(fù)效率的影響,并在不同類型的網(wǎng)絡(luò)上進(jìn)行對比實驗,得到的結(jié)論有助于今后恢復(fù)模型的設(shè)計與優(yōu)化。

進(jìn)一步地,研究者們考慮在網(wǎng)絡(luò)恢復(fù)過程中,通過投入外部資源來動態(tài)調(diào)整網(wǎng)元的恢復(fù)概率和恢復(fù)時間。李樹棟等[56]研究了邊攻擊下的應(yīng)急恢復(fù)機制。具體地,根據(jù)負(fù)荷與容量的關(guān)系,假設(shè)連邊可能處于三種狀態(tài): 正常、擁塞和失效。每條連邊都有初始恢復(fù)概率,在級聯(lián)失效過程中,當(dāng)負(fù)荷超過容量時,其會在恢復(fù)概率的作用下一定程度地減小; 若負(fù)荷仍然超過容量,連邊會按其固有權(quán)重比例得到一定量的外部資源,使得其恢復(fù)概率增大,從而負(fù)荷進(jìn)一步地減小。該模型反映了現(xiàn)實中外部資源越多網(wǎng)絡(luò)恢復(fù)概率越大的現(xiàn)象,并對不同的資源分配方式下的模型表現(xiàn)進(jìn)行了研究,對啟發(fā)理解現(xiàn)實網(wǎng)絡(luò)如何從級聯(lián)故障中恢復(fù)有一定幫助。

Xu等[57]建模了失效網(wǎng)元的恢復(fù)時間與資源投入之間的關(guān)系。假定在發(fā)生級聯(lián)失效前為節(jié)點vi分配的恢復(fù)資源為,其中R為資源總量,V為網(wǎng)絡(luò)節(jié)點集合,ki為節(jié)點vi的度; β的不同值表示不同的資源分配方法: 為0時,平均分配; 為1時,按節(jié)點度的比例分配。失效的節(jié)點vi將在一定時間段τi后從故障中恢復(fù),考慮到分配了更多恢復(fù)資源的失效節(jié)點將比那些分配了較少資源的節(jié)點更快恢復(fù),τi定義為服從泊松分布且均值為1ri的隨機變量,即:τi~ Poisson( 1 ri)。此外,為了減少已恢復(fù)的節(jié)點再次失效的風(fēng)險,恢復(fù)的節(jié)點將被分配更大的容量。Xu等[57]在資源總量固定的約束下,研究不同資源分配參數(shù)對網(wǎng)絡(luò)恢復(fù)性能的影響。結(jié)果表明,恢復(fù)過程受資源分配方法的影響很大,存在一定范圍內(nèi)的參數(shù)使得網(wǎng)絡(luò)的恢復(fù)效率加快,分析發(fā)現(xiàn)適當(dāng)為度更大的節(jié)點分配更多資源能有效提高網(wǎng)絡(luò)的彈性。這些結(jié)論為進(jìn)一步分析復(fù)雜網(wǎng)絡(luò)中的級聯(lián)失效與動態(tài)恢復(fù)過程提供了理論基礎(chǔ)。

4.2 改變原始結(jié)構(gòu)的恢復(fù)

前述恢復(fù)策略均致力于恢復(fù)原始網(wǎng)絡(luò)中的失效網(wǎng)元?？紤]到現(xiàn)實中存在無法完全恢復(fù)或在短時間內(nèi)很難恢復(fù)的失效網(wǎng)元,如: 航空網(wǎng)絡(luò)中,部分飛行線路受各種因素而取消。研究者們考慮建立新的連邊,以連接網(wǎng)絡(luò)中的剩余子分量,進(jìn)而恢復(fù)網(wǎng)絡(luò)整體連通性。以下介紹通過增加連邊改變了網(wǎng)絡(luò)原始結(jié)構(gòu)的恢復(fù)策略。

文獻(xiàn)[58]提出的恢復(fù)策略中,節(jié)點根據(jù)自身的連邊損耗來決定是否和一定距離內(nèi)的節(jié)點建立新的連邊。具體恢復(fù)過程為: 初始網(wǎng)絡(luò)中比例為p的節(jié)點被移除后,每個剩余節(jié)點確定其原始鄰居中正常節(jié)點的比例q: 若比例小于閾值qc,則該節(jié)點和距離rmax以內(nèi)的任意一個正常節(jié)點建立新連邊,距離以原始完整網(wǎng)絡(luò)中的路徑長度來衡量; 如果最大距離內(nèi)沒有正常節(jié)點,則該節(jié)點放棄建立新連邊。如圖9所示,圖(a)為原始網(wǎng)絡(luò),紅色節(jié)點為移除的失效節(jié)點,紅色連邊為對應(yīng)的失效連邊; 圖(b)為失效后進(jìn)行恢復(fù)的網(wǎng)絡(luò),其中黃色節(jié)點為正常鄰居節(jié)點比例小于等于 qc= 0.5的節(jié)點,黃色連邊為黃色節(jié)點和距離rmax=2內(nèi)的正常節(jié)點建立的新連邊,可以看到部分黃色節(jié)點無法在有效距離內(nèi)建立新連邊。該策略一個明顯的優(yōu)勢是利用局部信息,即節(jié)點只需要知道其鄰居節(jié)點的狀態(tài)信息就可以自主做出恢復(fù)決策,因此成本更低; 此外,節(jié)點能實時監(jiān)測自身的連邊損耗,在攻擊過程中立即進(jìn)行恢復(fù),相比攻擊結(jié)束后的恢復(fù)更加有效。盡管網(wǎng)絡(luò)重要節(jié)點的失效使得網(wǎng)絡(luò)分解為多個子分量,但通過增加本地連邊能很好的恢復(fù)網(wǎng)絡(luò)的連通性。

圖9 局部信息下的恢復(fù)過程示意圖(修改自文獻(xiàn)[58])Figure 9 Schematic illustration of the recovery process under local information(modified from[58])

文獻(xiàn)[59]提出了利用網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)信息來添加連邊的恢復(fù)策略。其出發(fā)點在于,僅利用本地局部信息的恢復(fù)的質(zhì)量較低,而網(wǎng)絡(luò)全局信息指導(dǎo)下的恢復(fù)策略計算復(fù)雜度較大。該策略中,將由蓄意攻擊產(chǎn)生的孤立子連通分量看作社區(qū),每個社區(qū)選擇其中一個節(jié)點作為代表; 將不同社區(qū)的代表節(jié)點之間的所有可能建立的連邊作為候選連邊,依據(jù)每個候選連邊添加后對整個網(wǎng)絡(luò)恢復(fù)效率的貢獻(xiàn)對其進(jìn)行排序,選擇最有效的候選連邊進(jìn)行構(gòu)建。策略中代表節(jié)點的選擇也有多種方式,如: 選擇度最大節(jié)點作為代表節(jié)點等。如圖10所示,圖(a)為原始網(wǎng)絡(luò),紅色節(jié)點為移除的失效節(jié)點,紅色連邊為對應(yīng)的失效連邊; 圖(b)為失效后進(jìn)行恢復(fù)的網(wǎng)絡(luò)?？梢詫⑹Ш蟮木W(wǎng)絡(luò)劃分為三個社區(qū),橙色節(jié)點為每個社區(qū)中的代表節(jié)點,橙色連邊為候選連邊; 通過計算可以知道綠色和黃色社區(qū)間的候選連邊最重要,故選擇建立該連邊。該策略將局部恢復(fù)概念擴展到社區(qū)范圍內(nèi)的恢復(fù),能較好地平衡恢復(fù)策略的計算效率和恢復(fù)質(zhì)量,并能取得較好的網(wǎng)絡(luò)恢復(fù)效率。之后的研究可以進(jìn)一步分析社區(qū)檢測方法對恢復(fù)性能的影響等更多問題。

圖10 社區(qū)結(jié)構(gòu)下的恢復(fù)過程示意圖(修改自文獻(xiàn)[59])Figure 10 Schematic illustration of the recovery process under community structures(modified from[59])

另一類策略則以一定的概率添加特定的連邊。文獻(xiàn)[60]研究了相依網(wǎng)級聯(lián)失效過程中的恢復(fù)策略:當(dāng)一個節(jié)點被移除或受相依連邊影響而失效后,其鄰居中任意兩個正常工作的節(jié)點間會以固定的概率建立新的連邊以繞過該失效節(jié)點?？紤]到相依網(wǎng)絡(luò)中,與巨連通分量斷開連接的子連通分量中的節(jié)點會由于缺少連邊支持而產(chǎn)生故障,文獻(xiàn)[61]提出以一定概率在孤立子分量與網(wǎng)絡(luò)巨連通分量之間建立新的連邊,從而保護子分量,增大巨連通分量,維持網(wǎng)絡(luò)連通性。需要注意的是,為了維持網(wǎng)絡(luò)的初始度分布,連邊的建立優(yōu)先選擇具有失效連邊的節(jié)點; 而為了減小子分量再次孤立的概率,在規(guī)模大于1的子分量和巨分量之間添加兩條連邊。如圖11所示,圖(a)為原始網(wǎng)絡(luò),紅色節(jié)點為移除的失效節(jié)點,紅色連邊為對應(yīng)的失效連邊; 圖(b)為失效后進(jìn)行恢復(fù)的網(wǎng)絡(luò),黃色的連邊為子分量和巨分量間建立的新連邊。上述策略作用下的網(wǎng)絡(luò)產(chǎn)生新的拓?fù)鋸亩柚辜壜?lián)失效并延遲網(wǎng)絡(luò)的崩潰。研究結(jié)果表明,隨著恢復(fù)概率的增加,網(wǎng)絡(luò)的彈性變大,當(dāng)恢復(fù)概率大于臨界值時可能完全抑制網(wǎng)絡(luò)的級聯(lián)失效。

圖11 相依網(wǎng)絡(luò)的恢復(fù)過程示意圖(修改自文獻(xiàn)[61])Figure 11 Schematic illustration of the recovery process under in interdependent networks(modified from[61])

文獻(xiàn)[62]研究了訪問受限的相依網(wǎng)絡(luò)上的加邊恢復(fù)策略?？紤]到某些現(xiàn)實多層相依網(wǎng)絡(luò)中并非所有層級的網(wǎng)絡(luò)都允許外部訪問,該加邊策略只能作用在允許訪問的網(wǎng)絡(luò)層中。具體地,初始每層網(wǎng)絡(luò)中一定比例的節(jié)點失效后,失效通過相依邊在網(wǎng)絡(luò)間進(jìn)行傳播。在允許訪問的網(wǎng)絡(luò)層中,每一個失效節(jié)點與同層網(wǎng)絡(luò)中若干個隨機選擇的節(jié)點添加新的連邊。失效節(jié)點可能主動建立連邊,也可能被動與其他失效節(jié)點建立連邊。若通過新建連邊,失效節(jié)點能夠重新與網(wǎng)絡(luò)巨連通分量相連,則該節(jié)點得到恢復(fù),且其他網(wǎng)絡(luò)中與之耦合的節(jié)點也得到恢復(fù)。研究結(jié)果表明,通過對允許訪問的網(wǎng)絡(luò)節(jié)點進(jìn)行加邊恢復(fù),可以有效的增強整個多層網(wǎng)絡(luò)的魯棒性。該策略具有較強的現(xiàn)實意義,如: 在由物理層和信息傳輸層組成的網(wǎng)絡(luò)物理網(wǎng)絡(luò)中,前者由于難以修改其結(jié)構(gòu)而無法控制,但現(xiàn)實中后者的結(jié)構(gòu)可以隨時調(diào)整,因此可以通過操縱信息層來實現(xiàn)物理層的相關(guān)性能。

5 基礎(chǔ)設(shè)施網(wǎng)絡(luò)恢復(fù)

前述網(wǎng)絡(luò)恢復(fù)的問題建模與策略設(shè)計主要基于復(fù)雜網(wǎng)絡(luò)的相關(guān)理論,研究過程中做了較多簡化假設(shè),如: 無限可用的外部資源、規(guī)則的網(wǎng)絡(luò)模型等。在實際中,許多基礎(chǔ)設(shè)施網(wǎng)絡(luò)上的恢復(fù)過程往往要考慮更多的現(xiàn)實因素,如: 恢復(fù)對象、時間、成本、目標(biāo)等。研究者們針對不同的約束條件,提出了許多恢復(fù)機制,以下進(jìn)行簡單介紹。

通信網(wǎng)絡(luò)在軟件錯誤或自然災(zāi)害的影響下可能出現(xiàn)大規(guī)模故障,在有限的維修和人力資源下,無法同時修復(fù)所有的故障物理組件,往往要分為多個階段?？紤]到存在部分物理鏈路在沒有完全失效的情況下仍能維持低速率傳輸,且不同物理組件的重要性和完全修復(fù)所需要的資源不同,Wang等[63]定義通信網(wǎng)絡(luò)恢復(fù)問題為: 在每一恢復(fù)階段,可用資源有限,如何從眾多待恢復(fù)的物理組件中進(jìn)行最佳的選擇,從而最大化恢復(fù)網(wǎng)絡(luò)的總流量。通過對問題進(jìn)行數(shù)學(xué)建模,求解得到最優(yōu)的組件恢復(fù)順序。結(jié)果表明,多階段策略在該類恢復(fù)場景下能較好的解決問題,值得進(jìn)一步研究。

另一方面,通信網(wǎng)絡(luò)中的服務(wù)需求也很重要,僅以網(wǎng)絡(luò)總流量最大化為目標(biāo)的恢復(fù)策略可能會導(dǎo)致網(wǎng)絡(luò)中邏輯鏈路的傳輸流量不均衡,即在某一恢復(fù)階段某些邏輯鏈路上的流量比預(yù)期的要多,而部分邏輯鏈路上傳輸?shù)牧髁坎蛔慊驗榱恪enda等[64]提出了基于服務(wù)需求的多階段通信網(wǎng)絡(luò)恢復(fù)策略:在選擇待恢復(fù)物理組件順序時,平衡網(wǎng)絡(luò)上總流量的需求和各邏輯鏈路上的流量需求。特別地,現(xiàn)實中為受影響地區(qū)迅速提供服務(wù)是網(wǎng)絡(luò)大規(guī)模故障后的關(guān)鍵需求,即使通信質(zhì)量會在一定程度上下降; 因為人們需要在受災(zāi)地區(qū)內(nèi)外盡可能多地進(jìn)行通信,傳遞災(zāi)難警告,疏散警報,救援請求等信息?？紤]到這一現(xiàn)實因素,Genda等[65]將恢復(fù)網(wǎng)絡(luò)的服務(wù)作為優(yōu)先目標(biāo),同時考慮合理的流量恢復(fù),提出了目標(biāo)分解的算法解決恢復(fù)問題,確定最佳的恢復(fù)順序。該策略降低了計算復(fù)雜度,能更好的應(yīng)用以解決現(xiàn)實問題。

進(jìn)一步地,網(wǎng)絡(luò)中不同服務(wù)的重要性不同,且物理組件在不同服務(wù)中起到的作用不同。為在有限的資源下盡快恢復(fù)網(wǎng)絡(luò)中的重要服務(wù),Jia等[66]提出了面向不同服務(wù)需求的鏈路重要性指標(biāo),并依據(jù)其降序確定優(yōu)先恢復(fù)的鏈路順序。仿真結(jié)果表明,該算法適用于大規(guī)模故障下的恢復(fù),但是與網(wǎng)絡(luò)能達(dá)到的最佳的恢復(fù)性能之間仍存在一定差距。類似地,Bartolini等[67]提出了基于服務(wù)需求的中心性來衡量節(jié)點相對于多個服務(wù)需求的重要性。為了使得恢復(fù)成本最低,提出了一種新穎的迭代拆分和修剪啟發(fā)式算法,可以在多項式時間內(nèi)計算節(jié)點恢復(fù)順序。實驗結(jié)果表明,該算法在恢復(fù)次數(shù)和執(zhí)行時間上優(yōu)于其他方法。

現(xiàn)實中,基礎(chǔ)設(shè)施網(wǎng)絡(luò)之間往往相互依賴[68],如: 水力系統(tǒng)中的水泵等需要電源才能正常運行,其與電力系統(tǒng)物理上聯(lián)系緊密; 多個系統(tǒng)共享地理空間,在同一個局部破壞性事件下往往會相互影響。圖12所示為不同基礎(chǔ)設(shè)施網(wǎng)絡(luò)之間相互依賴關(guān)系,和局部破壞下的網(wǎng)絡(luò)發(fā)生級聯(lián)失效。盡管存在這些相互依賴關(guān)系,但基礎(chǔ)設(shè)施網(wǎng)絡(luò)之間很少有通信,往往獨立地制定其各自的恢復(fù)策略。不同網(wǎng)絡(luò)的恢復(fù)優(yōu)先級的差異,可能導(dǎo)致利益沖突,影響相依網(wǎng)絡(luò)的整體恢復(fù),如: 一基礎(chǔ)設(shè)施系統(tǒng)在恢復(fù)其他基礎(chǔ)設(shè)施的需求之前,可能更愿意先為其優(yōu)先級較高的客戶恢復(fù)服務(wù)。

圖12 不同基礎(chǔ)設(shè)施網(wǎng)絡(luò)之間相互依賴關(guān)系和攻擊下的級聯(lián)失效的示意圖(修改自文獻(xiàn)[69])Figure 12 Illustration of the interdependent relationship among different infrastructure networks and cascading failure under attack(modified from[69])

為解決相依基礎(chǔ)設(shè)施網(wǎng)絡(luò)的恢復(fù)問題,Sharkey等[70]對比了不同的決策環(huán)境,如: 集中式?jīng)Q策環(huán)境(僅一個機構(gòu)計劃所有基礎(chǔ)設(shè)施網(wǎng)絡(luò)的恢復(fù)工作)、分散的決策環(huán)境(每個基礎(chǔ)設(shè)施網(wǎng)絡(luò)的機構(gòu)獨立進(jìn)行恢復(fù)工作)和信息共享決策環(huán)境(基礎(chǔ)設(shè)施網(wǎng)絡(luò)之間協(xié)作完成恢復(fù)工作)。Sharkey等[70]重點研究了信息共享環(huán)境下的恢復(fù)策略,考慮不同的恢復(fù)優(yōu)先級約束,以最大化基礎(chǔ)設(shè)施服務(wù)需求為目標(biāo),設(shè)計了混合整數(shù)規(guī)劃模型計算最佳的整體恢復(fù)策略。研究結(jié)果表明,簡單的信息共享能提高整個系統(tǒng)的恢復(fù)效率。但是該研究考慮的是理想的信息共享環(huán)境,即共享的信息均準(zhǔn)確,而實際中的信息可能多次修改,未來不同類型信息共享下的恢復(fù)策略值得繼續(xù)研究。

González等[71]考慮了物理、地理等不同的相互依賴關(guān)系,以成本最小化為目標(biāo),提出了混合整數(shù)規(guī)劃模型。研究結(jié)果表明,該策略不僅能在攻擊發(fā)生后對網(wǎng)絡(luò)組件進(jìn)行恢復(fù),還能在攻擊發(fā)生前,檢測出那些易發(fā)生故障的組件,對整個系統(tǒng)彈性的增強有較大幫助。針對基礎(chǔ)設(shè)施網(wǎng)絡(luò)間的物理依賴關(guān)系,Almoghathawi等[72]考慮不同的攻擊場景,如: 隨機故障,蓄意攻擊或局部破壞,提出了一種多目標(biāo)的恢復(fù)模型,以同時提高網(wǎng)絡(luò)性能和降低恢復(fù)成本。他們指出模型只關(guān)注網(wǎng)絡(luò)組件的兩種狀態(tài): 正常和故障。而實際中的網(wǎng)絡(luò)組件可能處于半故障狀態(tài),即以低效率工作,故可以在這一方面進(jìn)行改進(jìn)。

6 總結(jié)與展望

本文介紹了網(wǎng)絡(luò)彈性的概念,并梳理了兩類網(wǎng)絡(luò)恢復(fù)機制的相關(guān)研究。網(wǎng)絡(luò)彈性用于刻畫在遭受破壞攻擊時網(wǎng)絡(luò)的防護與恢復(fù)能力,構(gòu)建和運行具有彈性的網(wǎng)絡(luò)具有重要的現(xiàn)實意義。網(wǎng)絡(luò)防護作為預(yù)防性機制,主要關(guān)注如何防止更多的網(wǎng)元失效,從而阻止更大規(guī)模的網(wǎng)絡(luò)崩潰。網(wǎng)絡(luò)恢復(fù)作為應(yīng)激性機制,主要關(guān)注如何修復(fù)已失效網(wǎng)元,從而盡快恢復(fù)網(wǎng)絡(luò)功能。本文重點分析了近年來網(wǎng)絡(luò)恢復(fù)機制的相關(guān)研究,依據(jù)失效網(wǎng)元是各自獨立進(jìn)行恢復(fù)還是整體規(guī)劃進(jìn)行恢復(fù),將網(wǎng)絡(luò)恢復(fù)策略分成自發(fā)性恢復(fù)和指向性恢復(fù)兩類。

自發(fā)性恢復(fù)的優(yōu)點是網(wǎng)元只需本地判斷狀態(tài)后自行決策恢復(fù),但缺點是針對性不強,不同重要性的網(wǎng)元有相同的恢復(fù)能力,從而網(wǎng)絡(luò)恢復(fù)效率不高;相關(guān)研究針對這些問題,考慮到恢復(fù)資源的分配問題,關(guān)注不同網(wǎng)元的影響力,設(shè)計了多參數(shù)的恢復(fù)模型,得到了許多重要的結(jié)論,有利于理解網(wǎng)絡(luò)的自發(fā)恢復(fù)機制。指向性恢復(fù)則從恢復(fù)網(wǎng)絡(luò)整體的結(jié)構(gòu)和功能出發(fā),計算失效網(wǎng)元的重要性之后依序恢復(fù),具有較好的恢復(fù)效率,但是對于大規(guī)模網(wǎng)絡(luò)其在計算復(fù)雜度上有較大局限性; 考慮到這一困難,部分研究提出基于目標(biāo)節(jié)點的恢復(fù)策略,能較好的解決特定類型網(wǎng)絡(luò)的恢復(fù)問題; 特別地,研究者們提出了一種改變網(wǎng)絡(luò)拓?fù)涞幕謴?fù)策略,添加的連邊通過分擔(dān)失效網(wǎng)元的功能能較好的進(jìn)行應(yīng)急恢復(fù),但是在現(xiàn)實網(wǎng)絡(luò)中常難以實現(xiàn)。

總體來看,當(dāng)前提出的恢復(fù)模型多基于較為理想的網(wǎng)絡(luò)和外部資源環(huán)境,而在現(xiàn)實基礎(chǔ)網(wǎng)絡(luò)設(shè)施的恢復(fù)中還需要考慮網(wǎng)絡(luò)的服務(wù)類別,以及恢復(fù)的時間成本等更多實際因素。本文也對基礎(chǔ)設(shè)施網(wǎng)絡(luò)上的部分恢復(fù)機制進(jìn)行了簡單介紹,容易發(fā)現(xiàn)不同功能類型的現(xiàn)實網(wǎng)絡(luò)的結(jié)構(gòu)特點不同,其恢復(fù)需求也不大相同,這對恢復(fù)策略的普適性要求會更高;而現(xiàn)實網(wǎng)絡(luò)的規(guī)模和失效影響范圍也較模型網(wǎng)絡(luò)更大,這又對恢復(fù)策略的計算復(fù)雜度和效率有了更高的需求。

值得注意的是,網(wǎng)絡(luò)恢復(fù)機制的研究總是伴隨著網(wǎng)絡(luò)的失效機制。網(wǎng)絡(luò)恢復(fù)致力于修復(fù)失效網(wǎng)元和受損網(wǎng)絡(luò),這與網(wǎng)絡(luò)攻擊和級聯(lián)失效互為逆過程,兩者目標(biāo)正好相反?；謴?fù)策略的設(shè)計往往會針對網(wǎng)絡(luò)的失效類型,即: 隨機故障、蓄意攻擊和局部破壞。網(wǎng)絡(luò)級聯(lián)失效在過去20年得到了大量研究[73-78],而近些年網(wǎng)絡(luò)的恢復(fù)機制得到了重視,也初步取得了一些成果,但在以下方面仍需繼續(xù)深入研究。

(1) 級聯(lián)失效進(jìn)行過程中結(jié)合防護的恢復(fù)策略。已有的恢復(fù)策略僅關(guān)注網(wǎng)絡(luò)中的失效網(wǎng)元的恢復(fù),而部分正常網(wǎng)元可能在下一時刻失效,對網(wǎng)絡(luò)崩潰造成巨大影響。因此,如何在級聯(lián)失效過程中,既考慮已失效網(wǎng)元的恢復(fù),也考慮未失效網(wǎng)元的防護,提高網(wǎng)絡(luò)的恢復(fù)效率,是網(wǎng)絡(luò)恢復(fù)策略深入研究的重點。

(2) 局部信息下基于深度強化學(xué)習(xí)的恢復(fù)策略。已有的自發(fā)性恢復(fù)策略效率不高; 全局的指向性恢復(fù)計算量大,不易實踐; 現(xiàn)有的僅利用本地局部信息的策略恢復(fù)質(zhì)量較低。深度強化學(xué)習(xí)是一種新興的決策方法,利用深度神經(jīng)網(wǎng)絡(luò)在不斷交互中做出目標(biāo)最優(yōu)的決策。因此,考慮利用深度強化學(xué)習(xí)技術(shù),根據(jù)每個網(wǎng)元一定范圍內(nèi)的鄰居信息,以網(wǎng)絡(luò)恢復(fù)時間最短和恢復(fù)程度最高為目標(biāo),設(shè)計高效的恢復(fù)策略,是網(wǎng)絡(luò)恢復(fù)策略在創(chuàng)新方面值得研究的重要問題。

(3) 資源分配下基于網(wǎng)元集合的恢復(fù)策略。已有的指向性恢復(fù)策略大多基于重要性依次為單個網(wǎng)元分配資源使其恢復(fù),而在資源約束下能恢復(fù)的節(jié)點集合對網(wǎng)絡(luò)彈性的影響有時更大,即存在資源需求小的多個網(wǎng)元比資源需求大的單個網(wǎng)元更重要的情況。因此,如何評估單個網(wǎng)元和網(wǎng)元集合的重要性,合理分配恢復(fù)資源,是網(wǎng)絡(luò)恢復(fù)策略研究面臨的挑戰(zhàn)。