基于改進生成樹優化算法的抗毀性網絡設計研究*

劉 言 ，趙 銳 ，杜 磊 ，李 華

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

0 引言

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

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

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

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

1 抗毀性網絡模型構建

1.1 抗毀性指標分析

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

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

1.2 抗毀性網絡設計模型

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

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

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

（2）任意兩節點最小跳數不大于K。跳數約束可確保網絡正常狀態的時延要求，而在兩點間最小跳數鏈路遭遇毀傷后，用戶可能不在乎時延是否有所延長，而更加關心信息能否順利送達。因此，最小跳數不大于K的要求能夠確保通信網絡業務傳輸的抗毀性。

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

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

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

2 改進生成樹優化算法

2.1 算法步驟

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

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

圖1 ISTO算法基本流程

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

具體步驟如下：

輸入：帶權網絡W，跳數上限K。

輸出：優化后的網絡鄰接矩陣B；權值w。

（1）令 i=1；

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

（3）基于 Ti進行加邊優化，得到優化后網絡鄰接矩陣Bi；

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

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

2.2 帶跳數約束的最小生成樹構建

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

具體步驟如下：

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

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

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

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

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

（4）如果存在與 p關聯的一條淺藍色邊（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即為任意兩節點跳數不大于K的最小生成樹。

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

2.3 基于最小生成樹的加邊優化

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

如圖2所示，TA與TB為連接了同一棵樹中的葉子節點后的網絡，且TA與TB均增加了兩條邊。TA與TB的不同之處在于，TA仍是一個1-連通網絡，而 TB是 2-連通的。顯然TB達到了優化目標。通過分析發現，TA與TB的區別是TA中選擇相連的葉子節點v4與v5以及v6與v7，在原樹中的通路v4-v2-v5沒有經過根節點 v1，v6-v3-v7也沒有經過 v1，而 TB中 v5與 v6在原樹中通路為 v5-v2-v1-v3-v6經過了根節點v1，同理，v4與v7的通路也經過了v1。

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

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

加邊優化具體步驟如下：

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

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

輸出：優化后的網絡圖鄰接矩陣B；

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

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

（3）分下列 4種情況：

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

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

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

④若 di≥2，則執行下一步；

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

（5）返回結果圖 B。

3 算法分析

3.1 實例分析

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

圖3 某智能園區通信網絡成本開銷矩陣

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

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

圖4 節點間跳數不大于4的最小生成樹

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

圖5 加邊優化后生成的抗毀性網絡G1

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

表1 選取不同根節點生成的抗毀網絡開銷列表

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

3.2 比較分析

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

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

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

圖6 基于STO算法構建的網絡拓撲結構G2

比較后發現，G1的成本開銷僅是 G2的 36.2%，即使以最大的v1為根節點，以ISTO算法生成的智能園區網絡也僅是G2的79.5%。因此，本文提出的ISTO算法更具有易于實現、成本開銷低的優點。

4 結束語

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

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

[1]陳建國，張永靜.通信網絡拓撲抗毀性評估算法研究[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，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： StatisticalMechanics and its Applications，2003，320： 622-642.

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

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

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

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

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