復雜網(wǎng)絡抗毀性研究進展與展望

al伯格教授和其他人首次研究了復雜網(wǎng)絡的抗破壞性問題。他們將兩種傳統(tǒng)的隨機網(wǎng)絡和無標量網(wǎng)絡置于兩種攻擊策略：隨機失效和主動攻擊。研究表明:隨機失效情況下,無標度網(wǎng)絡相對于隨機網(wǎng)絡具有更強的抗毀性;而在蓄意打擊情況下,無標度網(wǎng)絡則表現(xiàn)地異常脆弱,無標度網(wǎng)絡這種雙重特性(Robust-yet-Fragile)被形象地稱為“阿喀琉斯之踵”。Albert教授等人的研究開創(chuàng)了復雜網(wǎng)絡抗毀性研究的先河,此后復雜網(wǎng)絡的抗毀性研究引起了越來越多的研究人員的關注,他們從不同的角度以及采用不同的方法研究了復雜網(wǎng)絡的抗毀性。但是這些研究都集中在了建立復雜網(wǎng)絡的抗毀性測度和抗毀性模型等方面,而忽略了復雜網(wǎng)絡抗毀性研究的最終目的,即:“什么樣的網(wǎng)絡拓撲結構抗毀性好”和“怎樣提高網(wǎng)絡拓撲結構的抗毀性”———復雜網(wǎng)絡抗毀性的優(yōu)化。1構建成本及抗毀性測度首先給出復雜網(wǎng)絡的一般表示:其中V表示節(jié)點集合,E表示邊的集合。并以φ表示網(wǎng)絡構建成本,F表示網(wǎng)絡抗毀性測度。一般認為,復雜網(wǎng)絡的抗毀性優(yōu)化問題可分為三類。1.1主要研究方向系統(tǒng)結構對功能具有重要意義,因此拓撲結構優(yōu)化是目前的一個主要研究方向,主要研究思路有:a.在一定構建成本約束下尋求具有最優(yōu)抗毀性的網(wǎng)絡拓撲結構:b.給定對于抗毀性的要求,而尋求使得構建成本最少的網(wǎng)絡拓撲結構:1.2ilute問題復雜網(wǎng)絡的鏈路容量優(yōu)化主要體現(xiàn)在動態(tài)抗毀性即級聯(lián)失效(CascadingFailure)問題中。研究思路為:對于每個節(jié)點或邊分配一定的容量,同時由于容量與網(wǎng)絡構建成本有關,因此優(yōu)化的目標是滿足網(wǎng)絡節(jié)點或邊的容量需求前提件的構建成本最小,例如對于節(jié)點容量優(yōu)化:其中ci表示節(jié)點容量,α>0表示節(jié)點容量的成本因子。1.3載傳輸能力復雜網(wǎng)絡基于路由策略的抗毀性優(yōu)化主要是考慮信息在網(wǎng)絡中傳輸時通過采取不同的路由策略以提高網(wǎng)絡的負載傳輸能力,主要應用于網(wǎng)絡的阻塞控制。由于通過不同的路由對于信息傳播時間延遲等具有很大的影響,因此信息路由策略優(yōu)化是在尋找一種使得網(wǎng)絡信息傳輸收益最大(如傳輸延遲φ最小)的最優(yōu)路由:在以上三個研究方向中,目前主要的研究集中于復雜網(wǎng)絡拓撲結構優(yōu)化方面,接下來我們將分別予以討論。2復雜網(wǎng)絡拓撲結構的優(yōu)化研究2.1節(jié)點地位和網(wǎng)絡結構Cohen等最早將滲流理論引入到Internet網(wǎng)絡隨機失效的解析研究中。在研究中,他們假設機移除的節(jié)點比例存在一個相變閾值pc,當移除的節(jié)點比例p>pc時,網(wǎng)絡被分解為小規(guī)模的互不連通的子圖,并且計算了pc的解析表達式:其中κ0=<k2>/<k>,為網(wǎng)絡連通性測度,<k>為度分布均值,<k2>為度分布的二階矩。例如對于度分布為P(k)=ck-α的無標度網(wǎng)絡:其中m和K分別為節(jié)點的最小度和最大度?；谝陨侠碚?G.Paul研究了單冪律網(wǎng)絡、雙冪律網(wǎng)絡(TwoPower-lawRegimes)、雙峰分布網(wǎng)絡(TwoPeaks)的抗毀性,研究目的是如何同時提高網(wǎng)絡拓撲結構對隨機失效和蓄意攻擊的抗毀能力。在研究中,采用(6)式作為隨機失效條件下網(wǎng)絡節(jié)點相變閾值移除比例pcrand,而對于蓄意打擊采用以下形式估計其節(jié)點相變閾值:綜合移除比例:pctotal=pcrand+pctarget。通過保持網(wǎng)絡規(guī)模不變,以對邊重連的方式研究表明,對于無標度網(wǎng)絡,當其冪律分布指數(shù)α≈2.5時,pctotal達到最大值,即網(wǎng)絡抗毀性最優(yōu)。三種網(wǎng)絡相比,雙峰分布網(wǎng)絡具有最優(yōu)的抗毀性,其度分布為:k1≈<k>,k2~N2/3?；陬愃频睦碚?G.Paul又研究了復雜網(wǎng)絡對于隨機失效的抗毀性優(yōu)化問題,在研究中,假設網(wǎng)絡總節(jié)數(shù)N不變,以網(wǎng)絡度分布均值<k>代表網(wǎng)絡構建成本,并保持不變,研究發(fā)現(xiàn),最優(yōu)網(wǎng)絡拓撲結構具有以下性質(zhì):對于q個節(jié)點,其度分布為:,而剩余N-q個節(jié)點的度分布為1,實際上同樣為雙峰分布。Tanizawa等研究了將隨機失效和蓄意打擊作為波次攻擊形式同時作用在網(wǎng)絡上的抗毀性優(yōu)化問題。在波次攻擊中,假設隨機失效和蓄意打擊的移除比例分別為pt和pr,經(jīng)過m波攻擊后網(wǎng)絡達到相變閾值,此時移除的節(jié)點比例為pc=m(pt+pr),以網(wǎng)絡度分布均值<k>代表網(wǎng)絡構建成本,并保持成本不變;研究發(fā)現(xiàn),當網(wǎng)絡的度分布為雙峰分布時,pc最大,并且pc僅與pt/pr有關。在這種雙峰分布中,比例為r的節(jié)點的度分布為(<k>-1+r)/r,其余節(jié)點的度則為1,其中r與pt和pr的比值有關。Valente等將復雜網(wǎng)絡抗毀性優(yōu)化研究推廣到了更為普遍的廣義隨機網(wǎng)絡上。研究表明,單獨考慮隨機失效和選擇性攻擊時,最優(yōu)度分布為雙峰分布,但當綜合考慮隨機失效和蓄意攻擊時,最優(yōu)分布為三峰分布,即p(kmin)+p(k*)+p(kmax)=1,其中kmin<k*<kmax。與G.Paul等人的研究不同,Jian-GuoLiu等研究了無標度網(wǎng)絡中基于網(wǎng)絡結構參數(shù)的最優(yōu)網(wǎng)絡拓撲結構問題。在隨機失效過程中,把無標度網(wǎng)絡的最優(yōu)拓撲結構獲取描述為:即使得臨界移除比例最大,同時保持網(wǎng)絡的平均度分布為定值。這其中,最小度值m在結構優(yōu)化中起重要的作用,研究表明當m=1時網(wǎng)絡可以達到其最優(yōu)的抗毀性。在對于蓄意攻擊的抗毀性優(yōu)化研究中,JianGuoLiu將對于節(jié)點的蓄意打擊轉(zhuǎn)化為對于邊的隨機攻擊,此時對邊的移除概率為與其相連的節(jié)點的度與網(wǎng)絡平均度的比值,同樣利用(6)式計算邊的相變閾值。2.2抗毀性優(yōu)化模型網(wǎng)絡度分布熵是網(wǎng)絡結構異質(zhì)性的度量,由于無標度網(wǎng)絡相對于隨機網(wǎng)絡具有更高的結構異質(zhì)性,因此其度分布熵小于隨機網(wǎng)絡的度分布熵。因而我們可以認為網(wǎng)絡的度分布熵越小,其對于隨機失效具有更高的抗毀性,對于蓄意攻擊則相反?；谝陨纤悸?王冰研究了基于度分布熵的無標度網(wǎng)絡對于隨機失效的抗毀性優(yōu)化問題。假設以H(α,m,N)代表無標度網(wǎng)絡的度分布熵,即:同時以網(wǎng)絡度分布的均值作為成本約束,則優(yōu)化模型可描述為:即保持成本一定的情況下使得網(wǎng)絡的度分布熵最大,這樣得出的網(wǎng)絡拓撲結構對于隨機失效具有高的抗毀性。以上考慮了網(wǎng)絡平均度為定值,即給定一定成本約束下的網(wǎng)絡結構優(yōu)化,楊琴等基于度分布熵研究了最小化網(wǎng)絡成本約束下的無標度網(wǎng)絡在蓄意打擊情況下的優(yōu)化:把最小成本和最大度分布熵的多目標優(yōu)化轉(zhuǎn)化為單目標優(yōu)化,同時滿足了網(wǎng)絡構建成本和網(wǎng)絡抗毀性的要求。2.3基于禁忌搜索的網(wǎng)絡抗毀性優(yōu)化現(xiàn)代優(yōu)化算法,如:遺傳算法、禁忌搜索算法和模擬退火算法等是解決復雜組合優(yōu)化的有力工具。由于隨著網(wǎng)絡規(guī)模的增大,解析的方法會帶來計算復雜度的急劇增加,因此不得不在求解過程中做一些簡化,但也同時帶來了結果的精確性問題,因此通過現(xiàn)代優(yōu)化算法求解最優(yōu)的網(wǎng)絡拓撲結構成為了一個新的研究方向。王冰基于禁忌搜索算法(TabuSearch)研究了服從任意度分布的復雜網(wǎng)絡抗毀性優(yōu)化,在抗毀性優(yōu)化過程中,以網(wǎng)絡效率作為目標函數(shù),同時以網(wǎng)絡度分布的均值作為成本約束,構造網(wǎng)絡最優(yōu)拓撲結構組合優(yōu)化模型:顯然,全局耦合網(wǎng)絡具有最優(yōu)的網(wǎng)絡效率,通過禁忌搜索算法,可以在當前網(wǎng)絡與全局耦合網(wǎng)絡的拓撲網(wǎng)絡空間中搜索具有給定成本約束的最優(yōu)化網(wǎng)絡結構。但由于網(wǎng)絡效率并不是一個嚴格的單調(diào)函數(shù),為此吳俊提出了以網(wǎng)絡自然連通度作為目標函數(shù)的基于禁忌搜索算法的復雜網(wǎng)絡抗毀性優(yōu)化方法,自然連通度代表了網(wǎng)絡中連通通路的冗余度,對于網(wǎng)絡邊的增加或移除具有嚴格的單調(diào)性:Pierre等采用模擬退火算法研究了BA無標度網(wǎng)絡在蓄意攻擊下的網(wǎng)絡拓撲結構優(yōu)化問題,在優(yōu)化過程中,以對邊進行隨機重連的方式,優(yōu)化了網(wǎng)絡的拓撲結構。此外,曹繼偉采用了遺傳算法針對無標度網(wǎng)絡的抗毀性進行拓撲結構的優(yōu)化;劉麗娟將遺傳算法和網(wǎng)絡結構熵相結合對無標度網(wǎng)絡的隨機失效條件下的容錯能力進行了優(yōu)化等。2.4基于prim算法的復雜網(wǎng)絡抗毀性優(yōu)化基于圖論研究復雜網(wǎng)絡抗毀性優(yōu)化的主要思路為:首先生成網(wǎng)絡的最小生成樹,然后在此基礎上對最小生成樹進行鏈路或節(jié)點的備份,即在一定成本約束下對最小生成樹添加邊或節(jié)點。劉嘯林提出了基于生成樹的網(wǎng)絡拓撲結構抗毀性優(yōu)化,首先采用改進的Prim算法構造最小生成樹,然后對生成樹中的葉子節(jié)點以及非葉子節(jié)點在滿足連通度為2,以及節(jié)點之間最大跳數(shù)為K的情況下進行加邊操作,采用節(jié)點備份提高節(jié)點的抗毀性。采用類似的方法,馮顏等研究了基于最小生成樹的復雜網(wǎng)絡抗毀性優(yōu)化問題,其研究思路為:首先采用Prim算法生成高度為K/2的最小生成樹,以滿足網(wǎng)絡的節(jié)點間跳數(shù)不大于K的要求;然后對高度為K/2的最小生成樹進行優(yōu)化,以滿足連通度為2的要求。最終目的是尋找一個最小連通度為2并且去除子圖中任意一條邊后,任意兩個節(jié)點間的跳數(shù)不大于K的最小開銷子圖。在實際優(yōu)化過程中,采用對節(jié)點加邊、換路等優(yōu)化方法。2.5非空間限制網(wǎng)絡QuZe-Hui提出了兩種用以提高無標度網(wǎng)絡針對蓄意攻擊抗毀性的方法:SL(SwitchLink)和SH(SplitHub)方法。對于非空間限制網(wǎng)絡,由于其邊的連接方式可以任意改變,因此可以采用將網(wǎng)絡中集散節(jié)點的部分邊連接到其他非集散節(jié)點(SwitchLink),從而降低集散節(jié)點的連接度。而對于具有空間限制的網(wǎng)絡,可以通過將集散節(jié)點分裂成多個節(jié)點(SplitHub),以降低集散節(jié)點的連接度。3種新的容量分配算法基于拓撲結構的復雜網(wǎng)絡抗毀性優(yōu)化僅僅考慮了網(wǎng)絡結構對抗毀性的影響,而在實際情況中,由于網(wǎng)絡中節(jié)點或邊的容量限制而引起的復雜網(wǎng)絡級聯(lián)失效現(xiàn)象普遍存在,因此怎樣對網(wǎng)絡中節(jié)點或邊的容量進行分配也是復雜網(wǎng)絡抗毀性優(yōu)化的一個重要研究課題,但這方面的成果并不多,還處于研究的起始階段。在復雜網(wǎng)絡的級聯(lián)失效模型中,由于考慮構建成本限制,一般假設網(wǎng)絡節(jié)點容量與其初始負載成線性函數(shù)關系:其中Ci代表網(wǎng)絡節(jié)點容量,Li0代表網(wǎng)絡初始負載,α∈(0,1)為容限系數(shù)。即在負載分配中,以節(jié)點的初始負載為標準將容量分配給各個節(jié)點。而BeomJunKim等將網(wǎng)絡中節(jié)點容量分配推廣到一種優(yōu)化的形式:其中負載分配優(yōu)化函數(shù)λ(Li0)的目標是使得各節(jié)點的容量對于級聯(lián)失效具有高的抗毀性和低的成本消耗,他們采取了一種比較簡單的優(yōu)化函數(shù):其中Θ(x)=0(1)forx<0(>0)為海維賽德(Heaviside)階躍函數(shù),Limax為節(jié)點最大負載,α∈[0,∞),β∈[0,1]為兩個控制系數(shù),當β=0時,λ=1+α即為(15)式的形式。優(yōu)化函數(shù)的本質(zhì)是對于節(jié)點最大負載大的節(jié)點分配更多的容量,從而優(yōu)化其抗毀性能,而對于最大負載小的節(jié)點分配較小的容量,節(jié)省容量成本。通過解析計算和仿真分析表明,與(15)式相比,他們所提出的容量分配方法在復雜網(wǎng)絡級聯(lián)失效方面具有更好的抗毀性和低的容量成本。PingLi則提出了另外一種根據(jù)節(jié)點的度的容量分配方法:這種方法對連接度大的節(jié)點分配較大的容量,與(15)式所描述的容量分配方式相比,這種方式的成本消耗一樣,但容易推廣到更為一般的情況。郭遲提出了一種基于模擬退火算法的容量優(yōu)化搜索算法。在容量分配中,采用了容量相互動態(tài)補償?shù)乃枷?不依賴于任何事先規(guī)定的負荷容量關系。首先假設存在一種最優(yōu)容量分配策略,使得在冗余容量一定的情況下網(wǎng)絡具有最優(yōu)的魯棒性,在這種分配策略下,節(jié)點容量為:而對于任意一種容量分配策略Ω,假設節(jié)點的容量可以分為兩個集合,一個集合中的節(jié)點容量大于最優(yōu)容量;另一個集合中節(jié)點容量小于最優(yōu)容量:然后定義容量調(diào)整算子Θ,從Almsgivers集合中取出空閑容量分配給Almsmen結合中的節(jié)點:AlmsgiversΘAlmsmen。在分配過程中基于偏好分配原則,即總是優(yōu)先分配給容量較大的節(jié)點。通過模擬退火算法對整個容量的分配過程進行了搜索,實驗證明其所提出的容量分配方式能使網(wǎng)絡具有最優(yōu)的抗毀性。李勇在研究地域保障網(wǎng)絡節(jié)點容量優(yōu)化時,并不是對所有節(jié)點進行容量優(yōu)化,而是采用了3種優(yōu)化策略:度升序優(yōu)化策略、度降序優(yōu)化策略和隨機優(yōu)化策略以降低優(yōu)化成本,對節(jié)點容量分配采取了基于初始負載的偏好分配方式,實驗結果表明按度降序策略優(yōu)化約50%的節(jié)點可以有效提高戰(zhàn)域保障網(wǎng)絡級聯(lián)失效抗毀性。4優(yōu)化網(wǎng)絡傳輸性能的優(yōu)化策略復雜網(wǎng)絡的路由策略優(yōu)化主要是研究如何提高異構網(wǎng)絡環(huán)境下的網(wǎng)絡負載傳輸能力,以在網(wǎng)絡出現(xiàn)阻塞或需重新路由時,網(wǎng)絡保持最優(yōu)的傳輸性能。經(jīng)常采用的路由策略包括:最短路徑策略、隨機路由策略和最佳路由策略。李濤提出了一種夠顯著提高無標度復雜網(wǎng)絡負載傳輸性能的