復雜網(wǎng)絡抗毀性優(yōu)化算法的設計與實現(xiàn)-資料課件

復雜網(wǎng)絡抗毀性優(yōu)化算法的設計與實現(xiàn)馮顏張琨黃奉孝鄒勇鑫南京理工大學計算機科學與技術(shù)學院復雜網(wǎng)絡抗毀性優(yōu)化算法的設計與實現(xiàn)馮顏張琨黃奉孝南京理工大學計算機科學與技術(shù)學院目錄引言1復雜網(wǎng)絡抗毀性優(yōu)化算法2

算法分析與實現(xiàn)3實例分析4南京理工大學計算機科學與技術(shù)學院目錄引2南京理工大學計算機科學與技術(shù)學院1.引言研究意義無尺度網(wǎng)絡的雙重特性：

對隨機失效的魯棒性&對選擇性攻擊的脆弱性復雜網(wǎng)絡抗毀性優(yōu)化算法的設計與實現(xiàn)對提高現(xiàn)實世界中各種網(wǎng)絡的抗毀性有著更為重要的應用價值。兩個關(guān)鍵技術(shù)一、生成高度為K/2的最小生成樹：

滿足網(wǎng)絡的節(jié)點間跳數(shù)不大于K的要求；二、對高度為K/2的最小生成樹進行優(yōu)化：

滿足連通度為2的要求。南京理工大學計算機科學與技術(shù)學院1.引言研究意義3南京理工大學計算機科學與技術(shù)學院1.引言在現(xiàn)實應用中，幾乎所有的復雜系統(tǒng)都可以抽象為復雜網(wǎng)絡模型。隨著復雜網(wǎng)絡的小世界效應及無標度特性的發(fā)現(xiàn)，復雜網(wǎng)絡研究逐漸成為多個學科共同關(guān)注的前沿熱點。一旦網(wǎng)絡的某個關(guān)鍵節(jié)點發(fā)生故障，將會給網(wǎng)絡的用戶帶來不便，有時甚至會導致非常嚴重的后果。為了使在蓄意破壞的情況下，網(wǎng)絡故障帶給用戶的損失減到最小，必須采取一定的措施使網(wǎng)絡在發(fā)生故障后能夠繼續(xù)提供一定的服務。1.引言南京理工大學計算機科學與技術(shù)學院1.引言1.引言4南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法

2.1抗毀性優(yōu)化算法設計目標主要手段：在網(wǎng)絡中增加足夠多的備份鏈路和備份設備。設計目標：忽略網(wǎng)絡帶寬的因素，用最少的成本建設一個最小連通度為2的網(wǎng)絡。該網(wǎng)絡中任意一條傳輸鏈路中斷后，任意兩個節(jié)點間的最大跳數(shù)仍不超過K。圖論表示：給定的無向圖G(V，E)以及每條邊的開銷Ce，尋找一個最小連通度為2的最小開銷子圖；去除子圖中任意一條邊后，子圖中任意兩個節(jié)點間的跳數(shù)不大于K。目前在國內(nèi)這類算法主要有劉麗娟提出的優(yōu)化IE模型算法、Wang等提出的熵優(yōu)化模型算法以及劉嘯林提出的基于生成樹優(yōu)化算法等。南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法5南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法

2.2算法思想考慮實際的建網(wǎng)開銷和網(wǎng)絡使用過程情況，抗毀性優(yōu)化后的網(wǎng)絡應至少符合以下四點要求：（1）連通度為2；（2）網(wǎng)絡的節(jié)點間跳數(shù)不能大于K值；（3）建網(wǎng)總開銷值相對較小；（4）網(wǎng)絡實際使用時，與網(wǎng)絡的一個節(jié)點vi相連的一條邊故障后，需通過另一條邊即備份鏈路進行通信，以保持網(wǎng)絡正常工作；同時還需要保證其他各點到vi的開銷和相對較小?；谏鲜鏊狞c要求，算法涉及的相關(guān)定義如下：南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法6南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法定義1網(wǎng)絡拓撲結(jié)構(gòu)：用鄰接矩陣表示的無向圖G(V，E)；頂點集合V=(v1,v2,…,vn)，邊集合e=(e1,e2,…,en)，eij=<vi,vj>；定義2旁親父節(jié)點：比節(jié)點vi的層次值?。醇墑e比vi高），且不在同一條枝上的所有其他節(jié)點。例如圖1(b)中節(jié)點v3的旁親父節(jié)點為v0，v1，v5。定義3

最佳生成樹：滿足高度為K/2，且開銷和相對最小的生成樹。圖1(a)給定一個無向圖 (b)根為v6時的最小生成樹南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法7南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法定義4節(jié)點vi的層次Qi：

生成樹的根定義為第0層，與根節(jié)點直接連接的節(jié)點定義為第l層，依此類推生成樹的葉子節(jié)點為第D層Qd。對節(jié)點的優(yōu)化又分為下述兩種情況：(1)對葉子節(jié)點vd進行優(yōu)化，增加邊edj，節(jié)點vj要滿足下述條件:①節(jié)點vj的層次Qj≤D-1；

②節(jié)點vj與vd的公共父節(jié)點只有一個，而且僅是根節(jié)點v0，或vj就是根節(jié)點v0。(2)對非葉子節(jié)點vi進行優(yōu)化，增加邊edj，節(jié)點vj要滿足下述條件:

①若節(jié)點vi的層次Qi＝k，那么節(jié)點vj的層次Qj≤k，此條件保證不會由于與節(jié)點vj的連接而導致跳數(shù)超限；

②節(jié)點vj與vi的公共父節(jié)點只有一個，而且僅是根節(jié)點v0，或vj就是根節(jié)點v0。南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法8南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法定義5網(wǎng)絡開銷和addCost(G)：帶權(quán)無向圖G的各邊權(quán)值總和。如圖1(a)所代表的網(wǎng)絡開銷和為19。定義6節(jié)點vi的開銷和addCost(vi)：網(wǎng)絡中所有其他節(jié)點到vi節(jié)點的鏈路開銷之和。例如，addCost(v3)=2+(1+2)+(1+2)+(1+1+2)+(1+1+2)+(2+1+2)=21定義7換路：當層次值Qi>K/2的節(jié)點與其父節(jié)點的連接斷開時，從原無向圖中重新選擇一條邊并連接，使得節(jié)點vi在新圖中的層次值Qi′∈[1,K/2]，并且保證這條新的邊是權(quán)值相對最小的一條。圖1(b)根為v6時的最小生成樹 圖2換路后得到的圖南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法9南京理工大學計算機科學與技術(shù)學院3.算法分析與實現(xiàn)3.1求最佳生成樹的三種求法(1)“修改過的prim算法”算法思想：在prim生成樹的每步過程中判斷加入的節(jié)點的層次，如果大于K/2就停止此步，通過其他的相對最小的邊連接此節(jié)點，并繼續(xù)判斷，直到結(jié)束。時間復雜度：O(N×N

2)(2)“prim算法試探+換路”的方法”算法思想：對給出的一個完全圖MG，每個節(jié)點都作為根執(zhí)行prim算法進行試探，找到使生成樹高度達到最小的那個根節(jié)點。找到此根節(jié)點后，對此生成樹中高度大于K/2的節(jié)點進行“換路”。時間復雜度：O(N×N

2)。南京理工大學計算機科學與技術(shù)學院3.算法分析與實現(xiàn)3.110南京理工大學計算機科學與技術(shù)學院3.算法分析與實現(xiàn)3.1求最佳生成樹的三種求法(3)“一次prim+換路”的方法”算法思想：對一個給出的完全圖MG，任意選取一個節(jié)點作為根，執(zhí)行prim算法求最小生成樹，然后扭轉(zhuǎn)此樹，找到使得生成樹高度達到最小的那個根節(jié)點。尋根前后樹的拓撲結(jié)構(gòu)是不變的。時間復雜度：O(N

2)通過時間復雜度的比較，本文采用第三種方法。南京理工大學計算機科學與技術(shù)學院3.算法分析與實現(xiàn)3.111南京理工大學計算機科學與技術(shù)學院3.算法分析與實現(xiàn)3.2生成樹節(jié)點的優(yōu)化得到高度為K/2的“最佳生成樹之后”，針對K是奇數(shù)或偶數(shù)兩種情況對節(jié)點進行優(yōu)化：K為偶數(shù)(1)對葉子節(jié)點vi的優(yōu)化方法：從旁親父節(jié)點集合中選擇一個最優(yōu)的vj節(jié)點(開銷值最小)，增加邊eij；(2)對非葉子節(jié)點vi的優(yōu)化方法：從相同層次值或?qū)哟沃敌∮谧约旱呐灾?jié)點集合中選擇一個最優(yōu)的vj節(jié)點，增加邊eij。K為奇數(shù)從同級別（即高度相同）或比自己級別高（節(jié)點層次值小于自己）的節(jié)點集合中選擇一個最優(yōu)的vj節(jié)點，增加邊eij。根節(jié)點無需優(yōu)化，實際網(wǎng)絡中對重要的根節(jié)點進行信息備份即可。南京理工大學計算機科學與技術(shù)學院3.算法分析與實現(xiàn)3.212南京理工大學計算機科學與技術(shù)學院3.算法分析與實現(xiàn)3.3兩種優(yōu)化參數(shù)的方法及比較在節(jié)點優(yōu)化算法過程中，本文給出兩種從備選節(jié)點集合{vj}中尋找最優(yōu)備份鏈路的方法。兩種方法的區(qū)別在于選取備份鏈路時界定“最優(yōu)”的標準不同，也具有不同的實際意義。根據(jù)“最小開銷值”這種方法很簡單，且目的性很明確，直接比較vi與備選節(jié)點集合{vj}中的各個節(jié)點之間鏈路的開銷，選取最小的那條鏈路作為備份。優(yōu)點：實現(xiàn)簡單；缺點：只能保證建網(wǎng)的初始開銷較小，沒有完全考慮鏈路出現(xiàn)故障后的實際情況。根據(jù)“節(jié)點vi的開銷和”用“節(jié)點vi的開銷和”來評估vj節(jié)點，這個值越小越好，根據(jù)這個值選擇出最佳的那個vj。優(yōu)點：網(wǎng)絡不僅在建網(wǎng)初期開銷值較小，而且在網(wǎng)絡出現(xiàn)故障時，仍能通過最節(jié)省開銷的備份鏈路，維護網(wǎng)絡的正常工作。南京理工大學計算機科學與技術(shù)學院3.算法分析與實現(xiàn)3.313南京理工大學計算機科學與技術(shù)學院4.實例分析原始網(wǎng)絡以一個節(jié)點數(shù)為9的帶權(quán)無向圖為例，開銷矩陣如表1；優(yōu)化目標：K=4，尋找一個最小連通度為2的最小開銷子圖，同時在去除子圖中任意一條邊后，子圖中任意兩個節(jié)點間的跳數(shù)不大于4。v0v1v2v3v4v5v6v7v8v0025157448v12063129105v2560257645v31320610783v4515604362v57271040258v6496732047v74104865409v8855328790表1網(wǎng)絡的開銷矩陣南京理工大學計算機科學與技術(shù)學院4.實例分析原始網(wǎng)絡v0v114南京理工大學計算機科學與技術(shù)學院4.實例分析三種方法求最佳生成樹圖3三種方法求最佳生成樹(a)修改過的prim算法(b)最佳根節(jié)點為v0(c)換路后的生成樹南京理工大學計算機科學與技術(shù)學院4.實例分析三種方法求最佳生15南京理工大學計算機科學與技術(shù)學院4.實例分析用兩種參數(shù)優(yōu)化生成樹圖4用兩種參數(shù)優(yōu)化生成樹(a)根據(jù)“最小開銷值”選擇備份鏈路(b)根據(jù)“節(jié)點vi的開銷和”選擇備份鏈路南京理工大學計算機科學與技術(shù)學院4.實例分析用兩種參數(shù)優(yōu)化生16南京理工大學計算機科學與技術(shù)學院結(jié)束語本文用最少的成本建設了一個連通度為2的網(wǎng)絡，并且保證當網(wǎng)絡中一條傳輸鏈路中斷后，任意兩個節(jié)點間的最大跳數(shù)不超過K。該算法在對大中型網(wǎng)絡的規(guī)劃設計或者優(yōu)化擴容時具有一定的實際應用價值。現(xiàn)有對節(jié)點失效的研究中，很少考慮節(jié)點本身具有一定的主動防御能力和自我修復能力。本課題組下一步的工作將從此方向展開。南京理工大學計算機科學與技術(shù)學院結(jié)束語17ThankYou!ThankYou!復雜網(wǎng)絡抗毀性優(yōu)化算法的設計與實現(xiàn)馮顏張琨黃奉孝鄒勇鑫南京理工大學計算機科學與技術(shù)學院復雜網(wǎng)絡抗毀性優(yōu)化算法的設計與實現(xiàn)馮顏張琨黃奉孝南京理工大學計算機科學與技術(shù)學院目錄引言1復雜網(wǎng)絡抗毀性優(yōu)化算法2

算法分析與實現(xiàn)3實例分析4南京理工大學計算機科學與技術(shù)學院目錄引20南京理工大學計算機科學與技術(shù)學院1.引言研究意義無尺度網(wǎng)絡的雙重特性：

對隨機失效的魯棒性&對選擇性攻擊的脆弱性復雜網(wǎng)絡抗毀性優(yōu)化算法的設計與實現(xiàn)對提高現(xiàn)實世界中各種網(wǎng)絡的抗毀性有著更為重要的應用價值。兩個關(guān)鍵技術(shù)一、生成高度為K/2的最小生成樹：

滿足網(wǎng)絡的節(jié)點間跳數(shù)不大于K的要求；二、對高度為K/2的最小生成樹進行優(yōu)化：

滿足連通度為2的要求。南京理工大學計算機科學與技術(shù)學院1.引言研究意義21南京理工大學計算機科學與技術(shù)學院1.引言在現(xiàn)實應用中，幾乎所有的復雜系統(tǒng)都可以抽象為復雜網(wǎng)絡模型。隨著復雜網(wǎng)絡的小世界效應及無標度特性的發(fā)現(xiàn)，復雜網(wǎng)絡研究逐漸成為多個學科共同關(guān)注的前沿熱點。一旦網(wǎng)絡的某個關(guān)鍵節(jié)點發(fā)生故障，將會給網(wǎng)絡的用戶帶來不便，有時甚至會導致非常嚴重的后果。為了使在蓄意破壞的情況下，網(wǎng)絡故障帶給用戶的損失減到最小，必須采取一定的措施使網(wǎng)絡在發(fā)生故障后能夠繼續(xù)提供一定的服務。1.引言南京理工大學計算機科學與技術(shù)學院1.引言1.引言22南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法

2.1抗毀性優(yōu)化算法設計目標主要手段：在網(wǎng)絡中增加足夠多的備份鏈路和備份設備。設計目標：忽略網(wǎng)絡帶寬的因素，用最少的成本建設一個最小連通度為2的網(wǎng)絡。該網(wǎng)絡中任意一條傳輸鏈路中斷后，任意兩個節(jié)點間的最大跳數(shù)仍不超過K。圖論表示：給定的無向圖G(V，E)以及每條邊的開銷Ce，尋找一個最小連通度為2的最小開銷子圖；去除子圖中任意一條邊后，子圖中任意兩個節(jié)點間的跳數(shù)不大于K。目前在國內(nèi)這類算法主要有劉麗娟提出的優(yōu)化IE模型算法、Wang等提出的熵優(yōu)化模型算法以及劉嘯林提出的基于生成樹優(yōu)化算法等。南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法23南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法

2.2算法思想考慮實際的建網(wǎng)開銷和網(wǎng)絡使用過程情況，抗毀性優(yōu)化后的網(wǎng)絡應至少符合以下四點要求：（1）連通度為2；（2）網(wǎng)絡的節(jié)點間跳數(shù)不能大于K值；（3）建網(wǎng)總開銷值相對較??；（4）網(wǎng)絡實際使用時，與網(wǎng)絡的一個節(jié)點vi相連的一條邊故障后，需通過另一條邊即備份鏈路進行通信，以保持網(wǎng)絡正常工作；同時還需要保證其他各點到vi的開銷和相對較小?；谏鲜鏊狞c要求，算法涉及的相關(guān)定義如下：南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法24南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法定義1網(wǎng)絡拓撲結(jié)構(gòu)：用鄰接矩陣表示的無向圖G(V，E)；頂點集合V=(v1,v2,…,vn)，邊集合e=(e1,e2,…,en)，eij=<vi,vj>；定義2旁親父節(jié)點：比節(jié)點vi的層次值?。醇墑e比vi高），且不在同一條枝上的所有其他節(jié)點。例如圖1(b)中節(jié)點v3的旁親父節(jié)點為v0，v1，v5。定義3

最佳生成樹：滿足高度為K/2，且開銷和相對最小的生成樹。圖1(a)給定一個無向圖 (b)根為v6時的最小生成樹南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法25南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法定義4節(jié)點vi的層次Qi：

生成樹的根定義為第0層，與根節(jié)點直接連接的節(jié)點定義為第l層，依此類推生成樹的葉子節(jié)點為第D層Qd。對節(jié)點的優(yōu)化又分為下述兩種情況：(1)對葉子節(jié)點vd進行優(yōu)化，增加邊edj，節(jié)點vj要滿足下述條件:①節(jié)點vj的層次Qj≤D-1；

②節(jié)點vj與vd的公共父節(jié)點只有一個，而且僅是根節(jié)點v0，或vj就是根節(jié)點v0。(2)對非葉子節(jié)點vi進行優(yōu)化，增加邊edj，節(jié)點vj要滿足下述條件:

①若節(jié)點vi的層次Qi＝k，那么節(jié)點vj的層次Qj≤k，此條件保證不會由于與節(jié)點vj的連接而導致跳數(shù)超限；

②節(jié)點vj與vi的公共父節(jié)點只有一個，而且僅是根節(jié)點v0，或vj就是根節(jié)點v0。南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法26南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法定義5網(wǎng)絡開銷和addCost(G)：帶權(quán)無向圖G的各邊權(quán)值總和。如圖1(a)所代表的網(wǎng)絡開銷和為19。定義6節(jié)點vi的開銷和addCost(vi)：網(wǎng)絡中所有其他節(jié)點到vi節(jié)點的鏈路開銷之和。例如，addCost(v3)=2+(1+2)+(1+2)+(1+1+2)+(1+1+2)+(2+1+2)=21定義7換路：當層次值Qi>K/2的節(jié)點與其父節(jié)點的連接斷開時，從原無向圖中重新選擇一條邊并連接，使得節(jié)點vi在新圖中的層次值Qi′∈[1,K/2]，并且保證這條新的邊是權(quán)值相對最小的一條。圖1(b)根為v6時的最小生成樹 圖2換路后得到的圖南京理工大學計算機科學與技術(shù)學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法27南京理工大學計算機科學與技術(shù)學院3.算法分析與實現(xiàn)3.1求最佳生成樹的三種求法(1)“修改過的prim算法”算法思想：在prim生成樹的每步過程中判斷加入的節(jié)點的層次，如果大于K/2就停止此步，通過其他的相對最小的邊連接此節(jié)點，并繼續(xù)判斷，直到結(jié)束。時間復雜度：O(N×N

2)(2)“prim算法試探+換路”的方法”算法思想：對給出的一個完全圖MG，每個節(jié)點都作為根執(zhí)行prim算法進行試探，找到使生成樹高度達到最小的那個根節(jié)點。找到此根節(jié)點后，對此生成樹中高度大于K/2的節(jié)點進行“換路”。時間復雜度：O(N×N

2)。南京理工大學計算機科學與技術(shù)學院3.算法分析與實現(xiàn)3.128南京理工大學計算機科學與技術(shù)學院3.算法分析與實現(xiàn)3.1求最佳生成樹的三種求法(3)“一次prim+換路”的方法”算法思想：對一個給出的完全圖MG，任意選取一個節(jié)點作為根，執(zhí)行prim算法求最小生成樹，然后扭轉(zhuǎn)此樹，找到使得生成樹高度達到最小的那個根節(jié)點。尋根前后樹的拓撲結(jié)構(gòu)是不變的。時間復雜度：O(N

2)通過時間復雜度的比較，本文采用第三種方法。南京理工大學計算機科學與技術(shù)學院3.算法分析與實現(xiàn)3.129南京理工大學計算機科學與技術(shù)學院3.算法分析與實現(xiàn)3.2生成樹節(jié)點的優(yōu)化得到高度為K/2的“最佳生成樹之后”，針對K是奇數(shù)或偶數(shù)兩種情況對節(jié)點進行優(yōu)化：K為偶數(shù)(1)對葉子節(jié)點vi的優(yōu)化方法：從旁親父節(jié)點集合中選擇一個最優(yōu)的vj節(jié)點(開銷值最小)，增加邊eij；(2)對非葉子節(jié)點vi的優(yōu)化方法：從相同層次值或?qū)哟沃敌∮谧约旱呐灾?jié)點集合中選擇一個最優(yōu)的vj節(jié)點，增加邊eij。K為奇數(shù)從同級別（即高度相同）或比自己級別高（節(jié)點層次值小于自己）的節(jié)點集合中選擇一個最優(yōu)的vj節(jié)點，增加邊eij。根節(jié)點無需優(yōu)化，實際網(wǎng)絡中對重要的根節(jié)點進行信息備份即可。南京理工大學計算機科學與技術(shù)學院3.算法分析與實現(xiàn)3.230南京理工大學計算機科學與技術(shù)學院3.算法分析與實現(xiàn)3.3兩種優(yōu)化參數(shù)的方法及比較在節(jié)點優(yōu)化算法過程中，本文給出兩種從備選節(jié)點集合{vj}中尋找最優(yōu)備份鏈路的方法。兩種方法的區(qū)別在于選取備份鏈路時界定“最優(yōu)”的標準不同，也具有不同的實際意義。根據(jù)“最小開銷值”這種方法很簡單，且目的性很明確，直接比較vi與備選節(jié)點集合{vj}中的各個節(jié)點之間鏈路的開銷，選取最小的那條鏈路作為備份。優(yōu)點：實現(xiàn)簡單；缺點：只能保證建網(wǎng)的初始開銷較小，沒有完全考慮鏈路出現(xiàn)故障后的實際情況。根據(jù)“節(jié)點vi的開銷和”用“節(jié)點vi的開銷和”來評估vj節(jié)點，這個值越小越好，根據(jù)這個值選擇出最佳的那個vj。優(yōu)點：網(wǎng)絡不僅