存在級(jí)聯(lián)故障的雙層互依網(wǎng)絡(luò).doc

《存在級(jí)聯(lián)故障的雙層互依網(wǎng)絡(luò).doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、存在級(jí)聯(lián)故障的雙層互依網(wǎng)絡(luò)摘要有的雙層互依網(wǎng)絡(luò)存在由兩種常見(jiàn)互依類型導(dǎo)致的級(jí)聯(lián)節(jié)點(diǎn)故障，本文定義并分析了這類網(wǎng)絡(luò)的經(jīng)典的最小頂點(diǎn)覆蓋問(wèn)題。以前對(duì)于互依網(wǎng)絡(luò)的研究主要著重于從數(shù)值模擬的角度來(lái)看級(jí)聯(lián)故障問(wèn)題，而本文提出了一個(gè)準(zhǔn)確的基于優(yōu)化的方法確定的一組節(jié)點(diǎn)集的最小勢(shì)，刪除這些節(jié)點(diǎn)將通過(guò)級(jí)聯(lián)故障作用嚴(yán)重影響這兩層網(wǎng)絡(luò)。我們分析了此問(wèn)題的計(jì)算復(fù)雜度和線性0-1規(guī)則，也證明了推廣了知名的對(duì)于經(jīng)典的最小節(jié)點(diǎn)覆蓋問(wèn)題的2-近似方法的LP近似的比率結(jié)果。同時(shí)，我們介紹了“級(jí)聯(lián)深度”的概念（即，給定網(wǎng)絡(luò)的一系列級(jí)聯(lián)故障的最大可能長(zhǎng)度），并說(shuō)明對(duì)于任何問(wèn)題該參數(shù)可以再多項(xiàng)式

2、時(shí)間過(guò)程內(nèi)顯式導(dǎo)出。一、介紹現(xiàn)代設(shè)施多由復(fù)雜多樣的網(wǎng)絡(luò)系統(tǒng)構(gòu)成，比如電網(wǎng)，遠(yuǎn)程通信和交通系統(tǒng)；而且這些系統(tǒng)間相互連接（即，互依網(wǎng)絡(luò)）。只有每一個(gè)基礎(chǔ)層都運(yùn)作才能確保整個(gè)互依系統(tǒng)的運(yùn)行。此情況是一個(gè)普遍例子是，有的網(wǎng)絡(luò)依靠電力作為重要?jiǎng)恿μ峁┙o它的節(jié)點(diǎn)來(lái)保證網(wǎng)絡(luò)的運(yùn)行（如遠(yuǎn)程通信或電腦設(shè)備），而底層的電力網(wǎng)絡(luò)中的節(jié)點(diǎn)反過(guò)來(lái)受計(jì)算機(jī)/通信網(wǎng)絡(luò)（如SCADA）中的節(jié)點(diǎn)控制。通常，基礎(chǔ)設(shè)施系統(tǒng)之間的互依模式非常復(fù)雜，通過(guò)互依連接傳遞物品或者信息。幾乎所有的現(xiàn)代基礎(chǔ)設(shè)施以各種方式相互依存。因此，研究大規(guī)?；A(chǔ)設(shè)施系統(tǒng)內(nèi)的相互作用非常重要。對(duì)整個(gè)復(fù)雜系統(tǒng)的縝密量化分析

3、是很有挑戰(zhàn)性的，然而最近的研究已經(jīng)開(kāi)始分析其包括雙層網(wǎng)絡(luò)的子系統(tǒng)，比如電力與遠(yuǎn)程通信網(wǎng)絡(luò)。顯然，電力網(wǎng)絡(luò)對(duì)現(xiàn)代基礎(chǔ)設(shè)施具有極為重要的意義。對(duì)電力的極端依賴表明了安全可靠的能源供應(yīng)的決定策略所面臨的挑戰(zhàn)。隨著基礎(chǔ)設(shè)施處于臨近物理極限狀態(tài)運(yùn)作，系統(tǒng)的可靠性將減弱。最近，2011年9月8號(hào)，由短路導(dǎo)致的電力斷供影響了數(shù)百萬(wàn)人口。城區(qū)的運(yùn)輸體統(tǒng)由于電力短缺也受到極大影響。由于與其他基礎(chǔ)設(shè)施相互依賴，能源系統(tǒng)更易受到攻擊。一個(gè)最近的互依基礎(chǔ)設(shè)施級(jí)聯(lián)故障的例子發(fā)生于2003年9月28日，意大利，當(dāng)時(shí)一個(gè)電站停止工作導(dǎo)致通信網(wǎng)絡(luò)的節(jié)點(diǎn)失效，該節(jié)點(diǎn)本是用來(lái)控制電力網(wǎng)絡(luò)的，

4、這樣反過(guò)來(lái)又引發(fā)電力網(wǎng)絡(luò)更大的故障，結(jié)果導(dǎo)致一系列災(zāi)難性的級(jí)聯(lián)故障。這類雙層互依網(wǎng)絡(luò)類似的說(shuō)明性例子如圖1所示。電力系統(tǒng)網(wǎng)絡(luò)用著名的IEEE118節(jié)點(diǎn)測(cè)試情況說(shuō)明，它表示了1960年的美國(guó)中西部州部分電力系統(tǒng)網(wǎng)絡(luò)。為了更具說(shuō)明性，SCADA網(wǎng)絡(luò)按冪律度分布隨機(jī)產(chǎn)生，并離散放置在圖中?；ヒ肋B邊連接了兩個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)（僅僅部分此類邊為了說(shuō)明情況而表示出來(lái)）。通常，多重的互依連接為外出或者進(jìn)入一個(gè)節(jié)點(diǎn)，因此，在不同網(wǎng)絡(luò)中的節(jié)點(diǎn)中將可能出現(xiàn)“一到多”或者“多到一”的關(guān)系，這在模式Buldyrev（2010）產(chǎn)生了“一到一”的關(guān)系。有可能導(dǎo)致級(jí)聯(lián)故障的相應(yīng)的互依類型

5、將會(huì)在隨后的部分規(guī)范化，關(guān)于定義此問(wèn)題時(shí)的說(shuō)明性例子的計(jì)算性實(shí)驗(yàn)也將會(huì)被呈現(xiàn)。雖然網(wǎng)絡(luò)魯棒性的量化分析可由多種觀點(diǎn)得出，但經(jīng)典且直觀的魯棒性測(cè)量標(biāo)準(zhǔn)是最小節(jié)點(diǎn)數(shù)（絕對(duì)或相對(duì)地取決于整個(gè)網(wǎng)絡(luò)的規(guī)模），即整個(gè)網(wǎng)絡(luò)的功能喪失所需要破壞的節(jié)點(diǎn)個(gè)數(shù)。顯然，如果該數(shù)相比于整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)較小的話，則可得出此網(wǎng)絡(luò)面對(duì)攻擊較脆弱的結(jié)論，然而如果該數(shù)與整個(gè)網(wǎng)絡(luò)的規(guī)模相當(dāng)，則該網(wǎng)絡(luò)相比于隨機(jī)或定向中斷更具魯棒性。從優(yōu)化的觀點(diǎn)來(lái)看，如果敵人擁有一個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的完整信息，那么他可以解決確定節(jié)點(diǎn)最集的最小基數(shù)的優(yōu)化問(wèn)題，這些節(jié)點(diǎn)是他為了要限制殘余網(wǎng)絡(luò)運(yùn)行功能所需要破壞的節(jié)點(diǎn)。例如

6、，如果要求是以L為閾值限制剩余連接部分，此問(wèn)題在cardinality-constrainedcriticalnodedetectionproblem有論述。在L=1的特殊情況下，此問(wèn)題變?yōu)榈湫偷淖钚」?jié)點(diǎn)覆蓋問(wèn)題，那些“觸摸”了網(wǎng)絡(luò)中所有邊的節(jié)點(diǎn)集的最小基數(shù)，故而在所有最小覆蓋節(jié)點(diǎn)都被破壞之后就剩下沒(méi)有邊存在的殘余網(wǎng)絡(luò)。本文中，我們定義并分析了雙層互依網(wǎng)絡(luò)情況下的最小節(jié)點(diǎn)覆蓋問(wèn)題，考慮了由兩種常見(jiàn)連接類型導(dǎo)致的級(jí)聯(lián)故障的可能性。據(jù)我們所知，這是第一份將經(jīng)典優(yōu)化問(wèn)題拓展至互依網(wǎng)絡(luò)結(jié)構(gòu)的研究。確定出那些如果被刪除將嚴(yán)重破壞整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)的集的最小基數(shù)，這無(wú)論在

7、攻擊還是預(yù)防角度都是極為有用的。在以前的構(gòu)想中，攻擊者確定出最應(yīng)該摧毀的節(jié)點(diǎn)集，然而在之后的構(gòu)想中，保護(hù)者有機(jī)會(huì)去保護(hù)這些已確認(rèn)出的節(jié)點(diǎn)集并防止受到可能出現(xiàn)的級(jí)聯(lián)故障傳播的干擾。在分析互依網(wǎng)絡(luò)魯棒性方面已經(jīng)有大量的工作被做，包括一般的和挑戰(zhàn)性的，互依網(wǎng)絡(luò)在節(jié)點(diǎn)或邊被移除情況下的性能及相對(duì)危險(xiǎn)率的評(píng)估問(wèn)題，還有分析和仿真的方法研究互依網(wǎng)絡(luò)的級(jí)聯(lián)故障?？傊蠖鄶?shù)之前的研究主要集中于仿真，缺少基于優(yōu)化的精確方法。本文在此方面探索。文章結(jié)構(gòu)。本文后續(xù)組織結(jié)構(gòu)如下。第二部分概括了將用到的基本定義；第三部分提出了數(shù)學(xué)分析結(jié)構(gòu)并證明了所考慮問(wèn)題的相關(guān)分析結(jié)果；第四部分

8、證明了所有考慮問(wèn)題的NP完備性的推斷；第五部分給出了計(jì)算性實(shí)驗(yàn)的結(jié)