復(fù)雜網(wǎng)絡(luò)抗毀性優(yōu)化算法的設(shè)計與實現(xiàn)課件

1、復(fù)雜網(wǎng)絡(luò)抗毀性優(yōu)化算法的設(shè)計與實現(xiàn)馮顏 張琨 黃奉孝 鄒勇鑫南京理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院南京理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院目 錄 引 言1 復(fù)雜網(wǎng)絡(luò)抗毀性優(yōu)化算法2 算法分析與實現(xiàn)3 實 例 分 析4南京理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院1. 引 言 研究意義無尺度網(wǎng)絡(luò)的雙重特性： 對隨機失效的魯棒性&對選擇性攻擊的脆弱性復(fù)雜網(wǎng)絡(luò)抗毀性優(yōu)化算法的設(shè)計與實現(xiàn)對提高現(xiàn)實世界中各種網(wǎng)絡(luò)的抗毀性有著更為重要的應(yīng)用價值。兩個關(guān)鍵技術(shù)一、生成高度為K/2的最小生成樹： 滿足網(wǎng)絡(luò)的節(jié)點間跳數(shù)不大于K的要求；二、對高度為K/2的最小生成樹進(jìn)行優(yōu)化： 滿足連通度為2的要求。南京理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院1. 引

2、言在現(xiàn)實應(yīng)用中，幾乎所有的復(fù)雜系統(tǒng)都可以抽象為復(fù)雜網(wǎng)絡(luò)模型。隨著復(fù)雜網(wǎng)絡(luò)的小世界效應(yīng)及無標(biāo)度特性的發(fā)現(xiàn)，復(fù)雜網(wǎng)絡(luò)研究逐漸成為多個學(xué)科共同關(guān)注的前沿?zé)狳c。一旦網(wǎng)絡(luò)的某個關(guān)鍵節(jié)點發(fā)生故障，將會給網(wǎng)絡(luò)的用戶帶來不便，有時甚至?xí)?dǎo)致非常嚴(yán)重的后果。為了使在蓄意破壞的情況下，網(wǎng)絡(luò)故障帶給用戶的損失減到最小，必須采取一定的措施使網(wǎng)絡(luò)在發(fā)生故障后能夠繼續(xù)提供一定的服務(wù)。1. 引 言南京理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院2. 復(fù)雜網(wǎng)絡(luò)抗毀性優(yōu)化算法 2.1 抗毀性優(yōu)化算法設(shè)計目標(biāo)主要手段：在網(wǎng)絡(luò)中增加足夠多的備份鏈路和備份設(shè)備。設(shè)計目標(biāo)：忽略網(wǎng)絡(luò)帶寬的因素，用最少的成本建設(shè)一個最小連通度為2的網(wǎng)絡(luò)。該網(wǎng)絡(luò)中任意一條

3、傳輸鏈路中斷后，任意兩個節(jié)點間的最大跳數(shù)仍不超過K。圖論表示：給定的無向圖G(V，E)以及每條邊的開銷Ce，尋找一個最小連通度為2的最小開銷子圖；去除子圖中任意一條邊后，子圖中任意兩個節(jié)點間的跳數(shù)不大于K。目前在國內(nèi)這類算法主要有劉麗娟提出的優(yōu)化IE模型算法、Wang等提出的熵優(yōu)化模型算法以及劉嘯林提出的基于生成樹優(yōu)化算法等。南京理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院2. 復(fù)雜網(wǎng)絡(luò)抗毀性優(yōu)化算法 2.2 算法思想考慮實際的建網(wǎng)開銷和網(wǎng)絡(luò)使用過程情況，抗毀性優(yōu)化后的網(wǎng)絡(luò)應(yīng)至少符合以下四點要求：（1）連通度為2；（2）網(wǎng)絡(luò)的節(jié)點間跳數(shù)不能大于K值；（3）建網(wǎng)總開銷值相對較??；（4）網(wǎng)絡(luò)實際使用時，與網(wǎng)絡(luò)的一

4、個節(jié)點vi相連的一條邊故障后，需通過另一條邊即備份鏈路進(jìn)行通信，以保持網(wǎng)絡(luò)正常工作；同時還需要保證其他各點到vi的開銷和相對較小。基于上述四點要求，算法涉及的相關(guān)定義如下：南京理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院2. 復(fù)雜網(wǎng)絡(luò)抗毀性優(yōu)化算法定義1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)：用鄰接矩陣表示的無向圖G(V，E)；頂點集合V=(v1, v2, vn)，邊集合e=(e1, e2, en ) ，eij=；定義2 旁親父節(jié)點：比節(jié)點vi的層次值小（即級別比vi高），且不在同一條枝上的所有其他節(jié)點。例如圖1(b)中節(jié)點v3的旁親父節(jié)點為v0，v1，v5。定義3 最佳生成樹： 滿足高度為K/2，且開銷和相對最小的生成樹。圖1 (

5、a) 給定一個無向圖 (b) 根為v6時的最小生成樹南京理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院2. 復(fù)雜網(wǎng)絡(luò)抗毀性優(yōu)化算法定義4 節(jié)點vi的層次Qi： 生成樹的根定義為第0層，與根節(jié)點直接連接的節(jié)點定義為第l層，依此類推生成樹的葉子節(jié)點為第D層Qd。對節(jié)點的優(yōu)化又分為下述兩種情況：(1) 對葉子節(jié)點vd進(jìn)行優(yōu)化，增加邊edj，節(jié)點vj要滿足下述條件: 節(jié)點vj的層次Qj D-1； 節(jié)點vj與vd的公共父節(jié)點只有一個，而且僅是根節(jié)點v0，或vj就是根節(jié)點v0 。(2) 對非葉子節(jié)點vi進(jìn)行優(yōu)化，增加邊edj，節(jié)點vj要滿足下述條件: 若節(jié)點vi的層次Qi k，那么節(jié)點vj的層次Qj k，此條件保證不會由于

6、與節(jié)點vj的連接而導(dǎo)致跳數(shù)超限； 節(jié)點vj與vi的公共父節(jié)點只有一個，而且僅是根節(jié)點v0，或vj就是根節(jié)點v0。南京理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院2. 復(fù)雜網(wǎng)絡(luò)抗毀性優(yōu)化算法定義5 網(wǎng)絡(luò)開銷和addCost(G)：帶權(quán)無向圖G的各邊權(quán)值總和。如圖1(a)所代表的網(wǎng)絡(luò)開銷和為19。定義6 節(jié)點vi的開銷和addCost(vi)：網(wǎng)絡(luò)中所有其他節(jié)點到vi節(jié)點的鏈路開銷之和。例如，addCost(v3)=2+(1+2)+(1+2)+(1+1+2)+(1+1+2)+(2+1+2)=21定義7 換路：當(dāng)層次值Qi K/2的節(jié)點與其父節(jié)點的連接斷開時，從原無向圖中重新選擇一條邊并連接，使得節(jié)點vi在新圖中的

7、層次值Qi1, K/2，并且保證這條新的邊是權(quán)值相對最小的一條。圖1 (b) 根為v6時的最小生成樹 圖2 換路后得到的圖南京理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院3. 算法分析與實現(xiàn)3.1 求最佳生成樹的三種求法(1) “修改過的prim算法”算法思想：在prim生成樹的每步過程中判斷加入的節(jié)點的層次，如果大于K/2就停止此步，通過其他的相對最小的邊連接此節(jié)點，并繼續(xù)判斷，直到結(jié)束。時間復(fù)雜度：O(NN 2)(2) “prim算法試探+換路”的方法”算法思想：對給出的一個完全圖MG，每個節(jié)點都作為根執(zhí)行prim算法進(jìn)行試探，找到使生成樹高度達(dá)到最小的那個根節(jié)點。找到此根節(jié)點后，對此生成樹中高度大于K/

8、2的節(jié)點進(jìn)行“換路”。時間復(fù)雜度：O(NN 2)。南京理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院3. 算法分析與實現(xiàn)3.1 求最佳生成樹的三種求法(3) “一次prim+換路”的方法”算法思想：對一個給出的完全圖MG，任意選取一個節(jié)點作為根，執(zhí)行prim算法求最小生成樹，然后扭轉(zhuǎn)此樹，找到使得生成樹高度達(dá)到最小的那個根節(jié)點。尋根前后樹的拓?fù)浣Y(jié)構(gòu)是不變的。時間復(fù)雜度：O(N 2) 通過時間復(fù)雜度的比較，本文采用第三種方法。南京理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院3. 算法分析與實現(xiàn)3.2 生成樹節(jié)點的優(yōu)化得到高度為K/2的“最佳生成樹之后”，針對K是奇數(shù)或偶數(shù)兩種情況對節(jié)點進(jìn)行優(yōu)化：K為偶數(shù)(1) 對葉子節(jié)點vi的優(yōu)

9、化方法：從旁親父節(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)絡(luò)中對重要的根節(jié)點進(jìn)行信息備份即可。南京理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院3. 算法分析與實現(xiàn)3.3 兩種優(yōu)化參數(shù)的方法及比較在節(jié)點優(yōu)化算法過程中，本文給出兩種從備選節(jié)點集合vj中尋找最優(yōu)備份鏈路的方法。兩種方法的區(qū)別在于選取備份鏈路時界定“最優(yōu)”的標(biāo)準(zhǔn)不同，也具有

10、不同的實際意義。根據(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)絡(luò)不僅在建網(wǎng)初期開銷值較小，而且在網(wǎng)絡(luò)出現(xiàn)故障時，仍能通過最節(jié)省開銷的備份鏈路，維護(hù)網(wǎng)絡(luò)的正常工作。南京理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院4.實例分析原始網(wǎng)絡(luò)以一個節(jié)點數(shù)為9的帶權(quán)無向圖為例，開銷矩陣如表1；優(yōu)化目標(biāo)：K=4，尋找一個最小連通度為2

11、的最小開銷子圖，同時在去除子圖中任意一條邊后，子圖中任意兩個節(jié)點間的跳數(shù)不大于4。v0v1v2v3v4v5v6v7v8v0025157448v12063129105v2560257645v31320610783v4515604362v57271040258v6496732047v74104865409v8855328790表1 網(wǎng)絡(luò)的開銷矩陣南京理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院4.實例分析三種方法求最佳生成樹圖3 三種方法求最佳生成樹(a) 修改過的prim算法 (b) 最佳根節(jié)點為v0(c) 換路后的生成樹南京理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院4.實例分析用兩種參數(shù)優(yōu)化生成樹圖4 用兩種參數(shù)優(yōu)化生成樹(a) 根據(jù)“最小開銷值”選擇備份鏈路(b) 根據(jù)“節(jié)點vi的開銷和” 選擇備份鏈路南京理工