復(fù)雜網(wǎng)絡(luò)抗毀性研究進(jìn)展與展望

復(fù)雜網(wǎng)絡(luò)抗毀性研究進(jìn)展與展望

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