基于改進生成樹優(yōu)化算法的抗毀性網(wǎng)絡設計研究*

劉 言 ，趙 銳 ，杜 磊 ，李 華

（1.軍事交通學院 研究生管理大隊，天津 300161；2.軍事交通學院 基礎部，天津 300161；3.武警指揮學院 管理與后勤系，天津 300250）

0 引言

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

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

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

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

1 抗毀性網(wǎng)絡模型構建

1.1 抗毀性指標分析

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

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

1.2 抗毀性網(wǎng)絡設計模型

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

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

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

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

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

其中，xij是所求拓撲結構的鄰接矩陣X的元素，滿足：

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

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

2.1 算法步驟

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

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

圖1 ISTO算法基本流程

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

具體步驟如下：

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

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

（1）令 i=1；

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

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

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

（5）選出 B1到 BN中連接邊權和最小的結構 Bj，令其為B。

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

構建最小生成樹是在已知一個加權無向圖G（V，E）的前提下，求出以節(jié)點n為根節(jié)點，深度為 D的最小生成樹。構造過程采用改進的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。

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

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

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

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

（5）置 i=i+1；

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

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

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

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

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

如圖2所示，TA與TB為連接了同一棵樹中的葉子節(jié)點后的網(wǎng)絡，且TA與TB均增加了兩條邊。TA與TB的不同之處在于，TA仍是一個1-連通網(wǎng)絡，而 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。

圖2 兩種懸掛點增加邊的方式

因此，在加邊優(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é)點，這時應選擇該葉子節(jié)點與旁支的節(jié)點加邊。

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

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

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

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

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

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

（3）分下列 4種情況：

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

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

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

④若 di≥2，則執(zhí)行下一步；

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

（5）返回結果圖 B。

3 算法分析

3.1 實例分析

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

圖3 某智能園區(qū)通信網(wǎng)絡成本開銷矩陣

其中，矩陣中i行j列對應的是wij的值。

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

圖4 節(jié)點間跳數(shù)不大于4的最小生成樹

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

圖5 加邊優(yōu)化后生成的抗毀性網(wǎng)絡G1

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

表1 選取不同根節(jié)點生成的抗毀網(wǎng)絡開銷列表

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

3.2 比較分析

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

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

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

圖6 基于STO算法構建的網(wǎng)絡拓撲結構G2

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

4 結束語

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

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

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

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

[3]FRANK H，F(xiàn)RISCH 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： StatisticalMechanics and its Applications，2003，320： 622-642.

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

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

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

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

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