摘  要： 針對當前通信網(wǎng)絡(luò)抗毀性設(shè)計問題，以連通度和跳數(shù)作為評價指標，建立了滿足指標約束條件且成本開銷最小化的網(wǎng)絡(luò)優(yōu)化設(shè)計模型，并在此基礎(chǔ)上提出了改進生成樹優(yōu)化算法求解該模型。仿真結(jié)果表明，該算法與生成樹優(yōu)化算法相比，能夠更好地權(quán)衡各項指標，在確?？箽詶l件下可有效降低成本開銷。對于通信網(wǎng)絡(luò)，特別是大型網(wǎng)絡(luò)的規(guī)劃及優(yōu)化設(shè)計，該算法具有實際應(yīng)用價值和可操作性。

　　關(guān)鍵詞： 抗毀性網(wǎng)絡(luò)設(shè)計；抗毀性指標；改進生成樹優(yōu)化；成本開銷；跳數(shù)；連通度

0 引言

　　近幾年，隨著大數(shù)據(jù)時代的到來，全球網(wǎng)絡(luò)化概念的興起，通信網(wǎng)絡(luò)在傳輸速度、信息準確性、建設(shè)成本等方面發(fā)展迅速，在國防、國民經(jīng)濟和社會生活中的各個領(lǐng)域發(fā)揮了前所未有的重要作用。通信網(wǎng)絡(luò)抗毀性（Invulnerability）作為通信網(wǎng)絡(luò)可靠性和安全性的重要方面，成為了當前網(wǎng)絡(luò)規(guī)劃設(shè)計的研究熱點。

　　通信網(wǎng)絡(luò)抗毀性是指在自然故障或遭受攻擊的條件下，通信網(wǎng)絡(luò)仍維持正常通信的能力[1]。當前，評估指標研究是網(wǎng)絡(luò)抗毀性研究的重要方面，國際上對抗毀性指標的研究成果有限[2]，大多以圖論為基礎(chǔ)，提出了一些表征連通性和效率的評價指標。例如：從連通性角度，參考文獻[3]提出網(wǎng)絡(luò)連通度、粘聚度指標；參考文獻[4]分別研究了不同類型的復(fù)雜網(wǎng)絡(luò)面對不同打擊條件下最大連通分支（Giant Component）節(jié)點數(shù)與網(wǎng)絡(luò)總節(jié)點數(shù)之比S、最大連通分支平均最短路徑L與節(jié)點移除比例f的關(guān)系；從通信能力角度，參考文獻[5]定義了網(wǎng)絡(luò)通信效率e，用于刻畫節(jié)點間的信息傳輸效率。在此基礎(chǔ)上，參考文獻[6]綜合了連通性和通信效率兩方面的考慮，以連通分支和平均最短路徑作為測度定義了連通系數(shù)，對于網(wǎng)絡(luò)抗毀性評價更加綜合全面。網(wǎng)絡(luò)的抗毀性指標為抗毀性評估提供了標準，通過數(shù)值仿真結(jié)果可以對比分析各種模型的抗毀性能[7]。

　　規(guī)劃設(shè)計滿足一定抗毀性指標要求的網(wǎng)絡(luò)稱為抗毀性網(wǎng)絡(luò)設(shè)計（Suvrivable Network Design）?？箽跃W(wǎng)絡(luò)設(shè)計工作往往是從網(wǎng)絡(luò)拓撲結(jié)構(gòu)開始的[8]。參考文獻[9]探討了在跳數(shù)限制下，構(gòu)建滿足一定連通度的抗毀網(wǎng)絡(luò)模型，并采用生成樹優(yōu)化（Spanning Tree Optimization，STO）算法求解模型。但是該算法規(guī)則復(fù)雜、不易仿真實現(xiàn)，且優(yōu)化后成本開銷較高。參考文獻[10]針對廣域測量系統(tǒng)通信網(wǎng)絡(luò)，以跳數(shù)和連通度指標構(gòu)建抗毀性網(wǎng)絡(luò)模型，結(jié)合流量狀況，采用改進的飽和割集算法求解網(wǎng)絡(luò)拓撲結(jié)構(gòu)，但該算法提出的網(wǎng)絡(luò)結(jié)構(gòu)代價相對較高，且負載均衡能力有限。

　　本文依據(jù)通信網(wǎng)絡(luò)抗毀性需求，從網(wǎng)絡(luò)拓撲結(jié)構(gòu)出發(fā)，利用圖論的方法，結(jié)合連通性和通信效率兩方面的考慮，建立了以連通性和跳數(shù)約束為抗毀性指標的優(yōu)化模型，提出了改進生成樹優(yōu)化（Improved Spanning Tree Optimization，ISTO）算法，實現(xiàn)對預(yù)定規(guī)模的通信網(wǎng)絡(luò)進行抗毀性設(shè)計。

1 抗毀性網(wǎng)絡(luò)模型構(gòu)建

　　1.1 抗毀性指標分析

　　在抗毀性網(wǎng)絡(luò)設(shè)計前，需將網(wǎng)絡(luò)的抗毀性指標作為一個重要的衡量因素考慮進去，定義適合的抗毀性指標。根據(jù)網(wǎng)絡(luò)抗毀性定義，抗毀性網(wǎng)絡(luò)設(shè)計是使網(wǎng)絡(luò)在自然災(zāi)害或遭受攻擊的情況下，能夠保持連通以維持正常通信，因此連通性是網(wǎng)絡(luò)抗毀性的重要方面。連通度是衡量連通性的重要指標。

　　此外，網(wǎng)絡(luò)在受攻擊后信息的通信效率是決定網(wǎng)絡(luò)性能的關(guān)鍵因素之一，也是網(wǎng)絡(luò)抗毀性指標建立中需要考慮的。通信網(wǎng)絡(luò)的節(jié)點間信息傳輸一部分是通過跳傳實現(xiàn)，傳輸時延與服務(wù)質(zhì)量與經(jīng)過的節(jié)點數(shù)量有關(guān)。跳數(shù)是衡量節(jié)點間信息傳輸經(jīng)過節(jié)點數(shù)量的指標。例如，以無線電波和光作為傳輸介質(zhì)的網(wǎng)絡(luò)，傳輸時延主要集中在節(jié)點設(shè)備上，如果節(jié)點間的跳數(shù)太多，就會增加通信設(shè)備的中轉(zhuǎn)及路由開銷，延長數(shù)據(jù)傳輸時間，降低傳輸質(zhì)量。因此，在抗毀性通信網(wǎng)絡(luò)設(shè)計時，兩節(jié)點間跳數(shù)需要有一定的限制，以滿足其傳輸需求，確保網(wǎng)絡(luò)通信效率。

　　1.2 抗毀性網(wǎng)絡(luò)設(shè)計模型

　　通信網(wǎng)絡(luò)拓撲結(jié)構(gòu)設(shè)計首先要確定各節(jié)點地理位置、各節(jié)點間構(gòu)建線路的復(fù)雜情況以及節(jié)點間通信業(yè)務(wù)量，以此作為構(gòu)建網(wǎng)絡(luò)的成本開銷。將其抽象為成本開銷w。將通信網(wǎng)絡(luò)的各子網(wǎng)、路由交換設(shè)備、調(diào)度中心等抽象為點集V，兩點間構(gòu)建鏈路所需的成本開銷抽象為邊集E，由此共同構(gòu)成了通信網(wǎng)絡(luò)構(gòu)建的成本開銷網(wǎng)絡(luò)G（V，E）。

　　通信網(wǎng)絡(luò)的抗毀性設(shè)計目標就是要設(shè)計出滿足一定抗毀性指標要求，且成本開銷最小化的網(wǎng)絡(luò)[10]。針對一般通信網(wǎng)絡(luò)的特性，抗毀性網(wǎng)絡(luò)設(shè)計模型需要滿足以下抗毀性指標條件：

　?。?）網(wǎng)絡(luò)連通度至少為2。連通度為2的要求能夠保證網(wǎng)絡(luò)在任意單條鏈路中斷的情況下仍保持連通。

　?。?）任意兩節(jié)點最小跳數(shù)不大于K。跳數(shù)約束可確保網(wǎng)絡(luò)正常狀態(tài)的時延要求，而在兩點間最小跳數(shù)鏈路遭遇毀傷后，用戶可能不在乎時延是否有所延長，而更加關(guān)心信息能否順利送達。因此，最小跳數(shù)不大于K的要求能夠確保通信網(wǎng)絡(luò)業(yè)務(wù)傳輸?shù)目箽浴?/p>

　　基于此，本文構(gòu)建的抗毀性網(wǎng)絡(luò)設(shè)計模型如下：

　　wij為節(jié)點間建立鏈路的成本開銷矩陣W中的元素，代表在節(jié)點vi、vj的成本開銷；N為節(jié)點總數(shù)；為節(jié)點連通度；Dij是節(jié)點vi與vj最短路徑的跳數(shù)。

2 改進生成樹優(yōu)化算法

　　2.1 算法步驟

　　本文在求解模型的過程中，利用圖論的相關(guān)理論，基于生成樹增加邊的設(shè)計思想，對模型的部分指標進行了轉(zhuǎn)化，進一步提出了ISTO算法。

　　算法的基本流程如圖1所示。

　　首先在已知的成本開銷網(wǎng)絡(luò)中選取一個節(jié)點作為根節(jié)點，然后構(gòu)建一棵深度為D=K/2（若K是奇數(shù)，則D=（K-1）/2）的最小生成樹，其中K是任意兩點之間的跳數(shù)上限，生成樹能夠滿足網(wǎng)絡(luò)連通度為1的要求；然后在生成樹基礎(chǔ)上進行加邊優(yōu)化，使其能夠滿足連通度為2的要求；最后得到最小跳數(shù)不大于K的2-連通最小開銷網(wǎng)絡(luò)。

　　具體步驟如下：

　　輸入：帶權(quán)網(wǎng)絡(luò)W，跳數(shù)上限K。

　　輸出：優(yōu)化后的網(wǎng)絡(luò)鄰接矩陣B；權(quán)值w。

　?。?）令i=1；

　?。?）構(gòu)建以vi為根節(jié)點，帶跳數(shù)限制的最小生成樹Ti；

　?。?）基于Ti進行加邊優(yōu)化，得到優(yōu)化后網(wǎng)絡(luò)鄰接矩陣Bi；

　　（4）求Bi邊的權(quán)值和wi，若i<N，i++，則執(zhí)行步驟（2）；若i=N，則執(zhí)行下一步；

　?。?）選出B1到BN中連接邊權(quán)和最小的結(jié)構(gòu)Bj，令其為B。

　　2.2 帶跳數(shù)約束的最小生成樹構(gòu)建

　　構(gòu)建最小生成樹是在已知一個加權(quán)無向圖G（V，E）的前提下，求出以節(jié)點n為根節(jié)點，深度為D的最小生成樹。構(gòu)造過程采用改進的Prim算法。改進的Prim算法與標準Prim算法的區(qū)別在于，在待入選邊染成藍色的選擇過程中，引入了與待入選邊相連的未入選節(jié)點與根節(jié)點的跳數(shù)判斷。若滿足跳數(shù)限制D的要求，則按標準Prim算法步驟繼續(xù)執(zhí)行；若超出了跳數(shù)限制，則將與該入選節(jié)點相連的所有未入選邊染成紅色。

　　具體步驟如下：

　　輸入：G（V，E，L）的鄰接矩陣A；所選根節(jié)點n；最大跳數(shù)限制D；

　　輸出：帶跳數(shù)約束的最小生成樹T。

　?。?）取G（V，E，L）節(jié)點n作為初始藍子樹T，初始淺藍與藍子樹的集合C，置i=0；并把與T關(guān)聯(lián)的長度邊（n，j）著以淺藍色，其中j?埸T，C=C∪（n，j）；

　　（2）在所有淺藍色邊中，選擇最小長度邊（i，j）（其中，i∈T，j?埸T），將其著成藍色，置T=T∪（i，j）；

　　（3）若節(jié)點pC，且在圖T中，j到n點的跳數(shù)<D，則把（j，p）著為淺藍色；否則將與點j關(guān)聯(lián)的?埸T的邊都著紅色，重新執(zhí)行步驟（3）；

　?。?）如果存在與p關(guān)聯(lián)的一條淺藍色邊（w，p），且（j，p）為淺藍色，l（w，p）>l（j，p），則把邊（w，p）著成紅色，C=C∪（j，p）；否則，不作任何處理；

　?。?）置i=i+1；

　?。?）如果i=N-1，則算法終止；若i<N-1，則返回步驟（2）。

　　最后得到的藍子樹T即為任意兩節(jié)點跳數(shù)不大于K的最小生成樹。

　　對于跳數(shù)的計算，采用的是將所有邊的權(quán)賦值為1，然后應(yīng)用Dijkstra算法求兩點的最短路徑，所得到的結(jié)果即為該兩點間的跳數(shù)。

　　2.3 基于最小生成樹的加邊優(yōu)化

　　由于最小生成樹已滿足跳數(shù)約束要求，因此加邊優(yōu)化的目標是增加盡可能少的邊，使優(yōu)化后的網(wǎng)絡(luò)連通度為2。由圖論可知，一個節(jié)點數(shù)量大于2的網(wǎng)絡(luò)的連通度至少為2（當且僅當網(wǎng)絡(luò)中不存在割點）。而一棵樹除了葉子節(jié)點（度為1的節(jié)點），其他所有節(jié)點都是割點。因此要使生成樹通過加邊優(yōu)化達到2-連通網(wǎng)絡(luò)要求，首先要消除其割點。本文采用葉子節(jié)點之間增加邊的方式，能夠利用盡可能少的邊，消除更多的割點，從而用更少的開銷，達到連通度為2的目的。

　　如圖2所示，TA與TB為連接了同一棵樹中的葉子節(jié)點后的網(wǎng)絡(luò)，且TA與TB均增加了兩條邊。TA與TB的不同之處在于，TA仍是一個1-連通網(wǎng)絡(luò)，而TB是2-連通的。顯然TB達到了優(yōu)化目標。通過分析發(fā)現(xiàn)，TA與TB的區(qū)別是TA中選擇相連的葉子節(jié)點v4與v5以及v6與v7，在原樹中的通路v4-v2-v5沒有經(jīng)過根節(jié)點v1，v6-v3-v7也沒有經(jīng)過v1，而TB中v5與v6在原樹中通路為v5-v2-v1-v3-v6經(jīng)過了根節(jié)點v1，同理，v4與v7的通路也經(jīng)過了v1。

　　因此，在加邊優(yōu)化之前，需判定兩葉子節(jié)點在原樹中的通路是否經(jīng)過根節(jié)點。只有經(jīng)過了根節(jié)點的兩點才進行加邊優(yōu)化。例如圖2的TB中，優(yōu)化前因v5與v6之間的通路經(jīng)過了v1，因此可以為v5與v6增加邊。此外，若葉子節(jié)點數(shù)量為奇數(shù)，則在兩兩加邊優(yōu)化后還剩余一個葉子節(jié)點，這時應(yīng)選擇該葉子節(jié)點與旁支的節(jié)點加邊。

　　加邊優(yōu)化具體步驟如下：

　　假設(shè)T（V，E）是一棵無權(quán)最小生成樹，其鄰接矩陣為A，節(jié)點數(shù)量為N。

　　輸入：最小生成樹的鄰接矩陣A，生成樹根節(jié)點n；

　　輸出：優(yōu)化后的網(wǎng)絡(luò)圖鄰接矩陣B；

　?。?）初始化TB=T，求出網(wǎng)絡(luò)中各節(jié)點的度，按度從小到大的順序?qū)⒐?jié)點進行排序，其節(jié)點分別為v1，v2，…，vN，統(tǒng)計度d=1的點的個數(shù)為L；置i=1；執(zhí)行下一步；

　?。?）置j=i+1，執(zhí)行下一步；

　?。?）分下列4種情況：

　?、偃鬱i<2，dj<2，且節(jié)點vj與vi在T中的路徑經(jīng)過根節(jié)點vn，則增加邊（vi，vj）（di與dj均+1），TB=TB∪（vi，vj），執(zhí)行下一步；

　?、谌鬱i<2，dj<2，但節(jié)點vj與vi的路徑不經(jīng)過根節(jié)點vn，或是di<2，dj≥2，j<L，則j=j+1，重新執(zhí)行步驟（3）；

　?、廴鬱i<2，dj≥2，j≥L，且節(jié)點vj與vi在T中的路徑經(jīng)過根節(jié)點vn，則增加邊（vi，v1），TB=TB∪（vi，v1），執(zhí)行下一步；

　?、苋鬱i≥2，則執(zhí)行下一步；

　?。?）若i<L，置i=i+1，返回步驟（2）；否則執(zhí)行下一步；

　?。?）返回結(jié)果圖B。

3 算法分析

　　3.1 實例分析

　　以某智能園區(qū)通信網(wǎng)絡(luò)建設(shè)為例，該園區(qū)有14個主要通信節(jié)點，其主干網(wǎng)采用萬兆光纜，因此可認為該園區(qū)網(wǎng)有足夠的鏈路冗余，不考慮流量。根據(jù)14個節(jié)點建設(shè)的地理位置、通信線路的建設(shè)成本以及建設(shè)難度等，對成本開銷進行了評估，其成本開銷網(wǎng)絡(luò)以鄰接矩陣表示，如圖3?？箽跃W(wǎng)絡(luò)的設(shè)計要求滿足至少2-連通，任意兩點間最小跳數(shù)不超過4跳，且總建設(shè)成本開銷盡可能小。

　　其中，矩陣中i行j列對應(yīng)的是wij的值。

　　首先，任意取節(jié)點（假設(shè)是節(jié)點4）作為初始樹的根節(jié)點，通過改進的Prim算法生成帶跳數(shù)限制的最小生成樹，如圖4所示。

　　圖5是通過加邊優(yōu)化后生成的網(wǎng)絡(luò)G1，圖中虛線是在最小生成樹基礎(chǔ)上增加的邊，可以看出，G1滿足2-連通且最小跳數(shù)為4的要求，且有18條邊。

　　依次選擇每一個節(jié)點作為初始樹的根節(jié)點，按照算法進行抗毀網(wǎng)絡(luò)生成后，得到網(wǎng)絡(luò)開銷比較，如表1所示。

　　由表1可見，當以節(jié)點4為初始樹根節(jié)點時，生成后的網(wǎng)絡(luò)總開銷最小，為60。因此，G1是滿足抗毀性指標且成本開銷最少的抗毀性網(wǎng)絡(luò)，達到了設(shè)計目的。

　　3.2 比較分析

　　為了進一步驗證算法性能，將ISTO算法與參考文獻[9]提出的STO算法進行比較。STO算法的基本流程同樣是在成本開銷矩陣的基礎(chǔ)上構(gòu)建一個帶跳數(shù)約束的最小生成樹，再通過加邊優(yōu)化構(gòu)建2-連通的網(wǎng)絡(luò)。

　　兩者區(qū)別在于，在加邊優(yōu)化過程中，ISTO算法不要求最后生成的網(wǎng)絡(luò)在最小跳數(shù)路徑中斷后，備用路徑也滿足跳數(shù)限制要求。這是基于兩個方面的考慮。一是在網(wǎng)絡(luò)發(fā)生故障后，重點不是保證網(wǎng)絡(luò)傳輸時延一定與毀傷前一致，而是要求網(wǎng)絡(luò)連通，重要信息能夠順利通達。二是STO算法因過于要求跳數(shù)限制，導(dǎo)致算法規(guī)則復(fù)雜、不易仿真實現(xiàn)，且優(yōu)化后的網(wǎng)絡(luò)成本開銷過大。

　　以圖4中智能園區(qū)通信網(wǎng)絡(luò)為例，若采用參考文獻[9]中的STO算法，同樣以節(jié)點4為根節(jié)點，優(yōu)化后得到拓撲結(jié)構(gòu)G2（圖6）。其中，G2有24條邊，成本開銷為166。兩算法生成網(wǎng)絡(luò)的性能比較如表2所示。

　　比較后發(fā)現(xiàn)，G1的成本開銷僅是G2的36.2%，即使以最大的v1為根節(jié)點，以ISTO算法生成的智能園區(qū)網(wǎng)絡(luò)也僅是G2的79.5%。因此，本文提出的ISTO算法更具有易于實現(xiàn)、成本開銷低的優(yōu)點。

4 結(jié)束語

　　通信網(wǎng)絡(luò)抗毀性是目前通信網(wǎng)絡(luò)技術(shù)發(fā)展過程中需要重視和亟待解決的問題，連通性和通信效率尤其重要。本文提出的ISTO算法能夠用于求解連通度和跳數(shù)約束的抗毀性模型，并為抗毀性網(wǎng)絡(luò)設(shè)計提供了一個定量標準和有效的計算方法。實際通信網(wǎng)絡(luò)中情況較為復(fù)雜，抗毀性通信網(wǎng)絡(luò)設(shè)計應(yīng)與具體工程需求密切相關(guān)。而ISTO算法默認鏈路容量足夠大，不會出現(xiàn)信息擁塞，沒有考慮流量狀況。

　　下一步可以結(jié)合具體業(yè)務(wù)流量與鏈路帶寬等因素，從通信網(wǎng)絡(luò)路由算法入手，制定適合的路由策略，使網(wǎng)絡(luò)在毀傷前后都能順利選擇最優(yōu)路徑傳輸，提高網(wǎng)絡(luò)整體資源利用率，進一步提升網(wǎng)絡(luò)抗毀性。

參考文獻

　　[1] 陳建國，張永靜.通信網(wǎng)絡(luò)拓撲抗毀性評估算法研究[J].無線電通信技術(shù)，2006，32（1）：6-7.

　　[2] SAVOLA R. Towards a security metrics taxonomy for the information and communication technology industry[C]. In proceedings of the International Conference on Software Engineering Advances， ICSEA， Washington， 2007：60.

　　[3] FRANK H， FRISCH I T. Analysis and design of survivable networks[J]. IEEE Transactions on Communication Technology， 1970，8（5）：501-519.

　　[4] ALBERT R， JEONG H， BARAB?魣SI A L. Error and attack tolerance of complex networks[J]. Nature，2000，406：378-382.

　　[5] CRUCITTI P， LATORA V， MARCHIORI M， et al. Efficiency of scale-free networks： error and attack tolerance[J]. Physica A： Statistical Mechanics and its Applications， 2003，320： 622-642.

　　[6] 吳俊，譚躍進.復(fù)雜網(wǎng)絡(luò)抗毀性測度研究[J].系統(tǒng)工程學(xué)報，2005，20（2）：128-131.

　　[7] 楊琴.網(wǎng)絡(luò)拓撲模型的演化機制及抗毀性研究[D].鄭州：解放軍信息工程大學(xué)，2009.

　　[8] 張中偉，陳建國.抗毀通信網(wǎng)絡(luò)設(shè)計[J].無線電通信技術(shù)，2000，26（2）：33-38.

　　[9] 劉嘯林.帶跳數(shù)限制的抗毀性網(wǎng)絡(luò)設(shè)計[J].計算機應(yīng)用與軟件，2007，24（7）：138-139.

　　[10] 熊小萍，譚建成，林湘寧.基于改進飽和割集算法的廣域測量系統(tǒng)通信網(wǎng)絡(luò)架構(gòu)設(shè)計[J].電力系統(tǒng)自動化，2013，37（9）：97-102.