李丹鏑

(中國電子科技集團公司第五十四研究所，河北石家莊050081)

0 引言

通信網(wǎng)根據(jù)應(yīng)用需求通常分為干線網(wǎng)和接入網(wǎng)。由于受到使用規(guī)模、使用環(huán)境和組網(wǎng)設(shè)備等因素的限制，在設(shè)計通信網(wǎng)絡(luò)拓撲時，首先要對干線節(jié)點的布設(shè)進行優(yōu)化，用以實現(xiàn)廣域覆蓋，同時要對接入網(wǎng)進行優(yōu)化設(shè)計，以滿足用戶入網(wǎng)及業(yè)務(wù)流量的需求，最終的結(jié)果是保證使用時的業(yè)務(wù)需求。這就提出了如何合理、可靠、迅捷地進行通信網(wǎng)網(wǎng)絡(luò)規(guī)劃的問題。

通信網(wǎng)設(shè)計主要應(yīng)用2個設(shè)計原則:①優(yōu)化網(wǎng)絡(luò)拓撲，求解目標(biāo)為最小鏈路消耗和費用;② 受限資源約束，求解目標(biāo)為網(wǎng)絡(luò)的高抗毀性。以上2條設(shè)計原則是相互沖突的，要達到最小費用，最便捷的措施便是減少網(wǎng)絡(luò)的冗余鏈路和備份鏈路，這會在一定程度上影響網(wǎng)絡(luò)的抗毀性;另一方面提高網(wǎng)絡(luò)抗毀性的主要措施便是增加冗余鏈路和備份鏈路，此措施會影響鏈路消耗增加費用。基于通信網(wǎng)的設(shè)計提出了一種在費用和抗毀性能之間綜合考慮、優(yōu)化折衷的設(shè)計方法，設(shè)計目標(biāo)是具有一定抗毀性能的最小費用網(wǎng)絡(luò)拓撲。

1 通信網(wǎng)絡(luò)模型化基本原理

1.1 通信網(wǎng)絡(luò)的模型化

通信網(wǎng)通常布設(shè)成柵格狀或準(zhǔn)柵格狀，如圖1所示［1］，用于覆蓋相應(yīng)的地域范圍。在進行網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計時，把實際的通信網(wǎng)利用圖論理論來進行模型化，即把通信網(wǎng)表示為一個帶有權(quán)值的圖G，如圖2所示，權(quán)值包括4個部分［V，E，M，L］。

圖1 通信網(wǎng)網(wǎng)絡(luò)結(jié)構(gòu)

圖2 通信網(wǎng)模型化

其中，V表示非空節(jié)點集合，用于抽象化網(wǎng)絡(luò)節(jié)點;E表示邊集合，用于抽象化節(jié)點間的有效鏈路;M與L存在映射關(guān)系，表示為M:E→N×N。L與E也存在映射關(guān)系，表示為L:E→Li(Li是標(biāo)號的集合Li=a，b，c…)。

1.2 網(wǎng)絡(luò)抗毀度定義

通信網(wǎng)完成特定任務(wù)的有效程度與其底層傳送網(wǎng)的穩(wěn)定性密切相關(guān)，同時穩(wěn)定性又是影響網(wǎng)絡(luò)抗毀性的主要因素。影響網(wǎng)絡(luò)抗毀性的2個方面為［2］:① 在網(wǎng)絡(luò)出現(xiàn)阻塞或異常流量分布時網(wǎng)絡(luò)的承受能力;②由于自身設(shè)備故障和受敵方攻擊時產(chǎn)生的物理故障。在進行網(wǎng)絡(luò)設(shè)計時，需要定義一個精確估算網(wǎng)絡(luò)抗毀性的量度。

從通信網(wǎng)的抗毀角度考慮，網(wǎng)絡(luò)最差的情況是節(jié)點間完全分離。為了能夠定量地分析、評估網(wǎng)絡(luò)的抗毀性能，提出了節(jié)點抗毀因子(Node Invulnerability Factor，NIF)、鏈路抗毀因子(Link Invulnerability Factor，LIF)［3］，這 2 個因子用來表示網(wǎng)絡(luò)從連通狀態(tài)變?yōu)槿蛛x狀態(tài)的復(fù)雜程度。為了從局部來衡量一個節(jié)點或一條鏈路對網(wǎng)絡(luò)抗毀性能的影響程度，定義了節(jié)點分割因子(NSI)和鏈路分割因子(LSI)來分別定義每個節(jié)點和鏈路對維持網(wǎng)絡(luò)連通性貢獻的量度。

1.2.1 NIF

NIF從節(jié)點角度來反映網(wǎng)絡(luò)的穩(wěn)定度，即平均必須去掉NIF個節(jié)點才能使網(wǎng)絡(luò)處于完全分離狀態(tài)。定義如下:

式中，NCFj為圖G的第j個獨立部分的節(jié)點抗毀因子;n為圖G分離部分的個數(shù);Ni為第i條分解路徑所消除的節(jié)點數(shù);P(Ni)為第i條分解路徑出現(xiàn)的概率;D為各獨立部分分解路徑的總條數(shù)。

計算NIF，首先確定所有可能的關(guān)鍵割點集合(這些割點集合的消除可能導(dǎo)致網(wǎng)絡(luò)的完全分離)。接下來計算每個分割序列出現(xiàn)的概率，最后利用此概率乘以這個序列中節(jié)點的數(shù)量產(chǎn)生一個值，即得到NIF。

1.2.2 LIF

LIF用來衡量各鏈路對于網(wǎng)絡(luò)的整體連通性的影響程度，其計算公式如下:

式中，LIFi為圖G的第i個分割部分的鏈路抗毀因子;Si為第i個分割中生成樹的邊數(shù);S為圖G的生成樹所包含的邊數(shù);Ti為分割部分i的生成樹數(shù);Ei為分割部分i的邊數(shù);Ni為分割部分i的節(jié)點數(shù);n為圖G中分割部分?jǐn)?shù)。

進行LIF計算時，首先要計算網(wǎng)絡(luò)中各個部分的生成樹數(shù)量，其次計算各分割部分中各鏈路對生成樹的影響程度，最后確定各分割部分對總LIF的影響程度。

1.2.3 NSI

在網(wǎng)絡(luò)設(shè)計過程中，只定義LIF和NIF并不能提供改善網(wǎng)絡(luò)抗毀性的有效措施。為了解決此問題，提出了局部指標(biāo)NSI和LSI，用來衡量各鏈路或節(jié)點對于網(wǎng)絡(luò)連通性的影響程度。利用NSI和LSI可以判斷各節(jié)點或鏈路對于網(wǎng)絡(luò)抗毀性的重要程度，從而可以著手進行網(wǎng)絡(luò)整體抗毀性的改善。

對于一個特定節(jié)點，在不同長度路徑中的貢獻的求和就可得到其節(jié)點分割因子:

式中，m為Ki(不同路徑長度)的數(shù)量;Cni用來表示路徑長度Ki且含節(jié)點n的分割路徑占Ki所有路徑的百分比;Wi為Ki的路徑出現(xiàn)的概率;NSI(n)用來量度節(jié)點n對網(wǎng)絡(luò)連通性的影響程度。

1.2.4 LSI

為了衡量各鏈路對于網(wǎng)絡(luò)連通性的影響程度，計算此鏈路對生成樹的影響程度，即包含該鏈路的生成樹在總生成樹中的比率。具體解釋如下:

式中，Tj為含鏈路j的生成樹數(shù)量;TS為生成樹總量;LSI(j)定義了鏈路j對網(wǎng)絡(luò)連通性的影響程度。

綜上所述度，采用LIF和NIF從整體上度量網(wǎng)絡(luò)抗毀性，采用LSI和NSI從局部評估各鏈路和節(jié)點對網(wǎng)絡(luò)抗毀性的影響程度。通過分析可以發(fā)現(xiàn)，NSI值越大，則該節(jié)點對網(wǎng)絡(luò)連通性的影響程度越大;LSI越大，則該鏈路對網(wǎng)絡(luò)連通性的影響程度越大。

2 飽和割集算法

2.1 基本原理

割集是所有可將連通圖變?yōu)榉指顖D的鏈路集合［4］。如果割集中所有鏈路容量均與額定容量相等，則此割集為飽和割集。正常情況下，網(wǎng)絡(luò)中有許多割集，隨著業(yè)務(wù)量的不斷加載，其中之一的割集首先處于飽和狀態(tài)。如果去掉這些飽和鏈路，則會造成網(wǎng)絡(luò)的分割。這種情況下如果想增加系統(tǒng)的總?cè)萘?，只能增加單一鏈路容量或增加其他鏈路，這便是運用了飽和割集的基本原理［5］。

在實際網(wǎng)絡(luò)運行過程中，可以統(tǒng)計得到各鏈路利用率，如果將利用率高的鏈路斷掉，則會使網(wǎng)絡(luò)分割成2個部分，這2個分割部分的總業(yè)務(wù)量非常接近于飽和割集鏈路的總流量。即

式中，NDi為分割部分i中節(jié)點數(shù);Ke為節(jié)點對間的業(yè)務(wù)量;fi為割集鏈路的總流量。

綜上可以看出，飽和割集即是網(wǎng)絡(luò)總?cè)萘康臉O值。Ke的理論上限為:

式中，Sj為最小割集;S為割集。由于飽和割集的總流量與容量相近，利用式(6)有:

從式(7)可以得出結(jié)論，Ke值與理論上限非常接近;增加Ke的唯一途徑是增加割集容量。

因此，在任一分割部分內(nèi)部增加新鏈路并不能增加割集容量，從而也不會改善網(wǎng)絡(luò)的吞吐量。所以，通過增加鏈路來提高網(wǎng)絡(luò)吞吐量，必須考慮到連接2個分離部分的潛在鏈路。

2.2 算法流程

飽和割集法的主要流程如下:①修正網(wǎng)絡(luò)后執(zhí)行路由算法，產(chǎn)生新的鏈路流量;②確定飽和割集;③對網(wǎng)絡(luò)吞吐量進行判斷，若不滿足指標(biāo)要求，則執(zhí)行ADD-ONLY算法，從而產(chǎn)生新的干線流量;④執(zhí)行DELETE-ONLY算法，選擇連接2個部分中費用最小的鏈路;⑤ 判斷網(wǎng)絡(luò)抗毀性能，若能夠滿足抗毀性指標(biāo)，則停止運算，否則轉(zhuǎn)到①。

2.3 飽和割集確定和消除

飽和割集體現(xiàn)了網(wǎng)絡(luò)中流量最大的位置。如果不能夠滿足網(wǎng)絡(luò)吞吐量要求，可增加最少費用鏈路，從而在飽和割集中去除業(yè)務(wù)量。

2.3.1 鏈路增加算法——ADD-ONLY

采用 ADD-ONLY 算法［6］來確定節(jié)點 K1、K2的位置。增加新鏈路要滿足以下約束條件:連接2個分割部分且費用最小。假設(shè)所有鏈路容量相同，則滿足此約束條件的將是最短鏈路。事實上啟用最短鏈路對割集位置的改變很小，對吞吐量的改善也非常有限。

另一個可采用的方法是連接2個分割部分中業(yè)務(wù)最繁忙的“中心節(jié)點”。但是對于較大規(guī)模網(wǎng)絡(luò)，割集與“中心節(jié)點”的距離較遠，連接它們之間鏈路的費用極高。

DISTANCE2算法采用啟發(fā)式算法來得到“中心節(jié)點”。在增加鏈路時，鏈路兩端的節(jié)點與割集節(jié)點至少要相距2條鏈路。如果不可能的話(部分體積過小)，至少保留與割集節(jié)點鄰接的節(jié)點(一個單位距離)。

2.3.2 鏈路刪除算法——DELETE-ONLY

DELETE-ONLY算法的起始拓撲是高連通拓撲。當(dāng)網(wǎng)絡(luò)吞吐量大于指標(biāo)要求時，每次迭代只需消除一條鏈路，從而達到吞吐量和總費用的要求。用Ei來表示鏈路利用率和費用，定義如下:

式中，di為鏈路i的費用;Ci為鏈路 i的容量;fi為鏈路i的流量;(Ci－fi)/Ci為相對的剩余容量。

刪除節(jié)點的策略為:①每次去掉鏈路Ei值最大的一條，即去除的鏈路是最高費用、最低利用率的;②如果消除此鏈路產(chǎn)生了獨立節(jié)點，則不消除此鏈路;③如果初始網(wǎng)絡(luò)是K-連通的，則經(jīng)過DELETEONLY算法后產(chǎn)生的網(wǎng)絡(luò)也應(yīng)是個K-連通的，否則不消除此鏈路;④如果Ei最大的鏈路存在于飽和割集中，則不消除此鏈路。

3 抗毀通信網(wǎng)設(shè)計原理

如前所述，網(wǎng)絡(luò)的抗毀性和費用是相互制約的，同時在進行網(wǎng)絡(luò)設(shè)計時又必須重點考慮這2個因素。分別設(shè)計了針對費用效益比、鏈路容量和網(wǎng)絡(luò)抗毀性能的綜合網(wǎng)絡(luò)模型。

模型中已知節(jié)點的位置和節(jié)點間的業(yè)務(wù)量需求。設(shè)計最小費用連通網(wǎng)絡(luò)是在滿足初始條件的情況下使所有節(jié)點連通，這樣問題就變成了如何求解全連通網(wǎng)絡(luò)下最小權(quán)值和的生成樹。這正是所要求的具有最佳費用效益比的初始連通網(wǎng)絡(luò)拓撲結(jié)構(gòu)。

在具體的通信網(wǎng)設(shè)計過程中鏈路權(quán)值可以具有多重含義，可用于表示兩點間的距離、地形復(fù)雜度等。具體定義如下:

式中，dij為節(jié)點 i、j間的實際距離;Pij為節(jié)點 i、j間的地形復(fù)雜度;mij為節(jié)點i、j之間的業(yè)務(wù)量總和;α為調(diào)整因子。

首先得到全連通網(wǎng)絡(luò)(具有邊權(quán)值)，再利用如下算法尋找最佳費效比的生成樹。

①選擇節(jié)點i、j之間的連接，使其邊權(quán)值盡可能小;

② 若已選定 e1，e2，…，ei+1，則能從 E{e1，e2，…，ei+1}({e1，e2，…，ei+1}的補集)中選項取 ei+1，使得W(ei+1)最小的權(quán)且滿足G為無環(huán)路圖。

③當(dāng)?shù)冖诓綗o解時則終止。

這樣便得到了初始連通拓撲的生成樹，其中邊權(quán)同時考慮了業(yè)務(wù)量和費用的約束，初始連通拓撲包含了費用需求和業(yè)務(wù)量需求的雙重因素。

網(wǎng)絡(luò)設(shè)計應(yīng)該是在初始連通網(wǎng)絡(luò)拓撲的基礎(chǔ)上，通過增加/刪除鏈路來改善網(wǎng)絡(luò)綜合性能，下面提出增加/刪除鏈路的原則。

如前所述，消除所有飽和的割邊，將使網(wǎng)絡(luò)分離成2個部分K1、K2，對這2個部分的所有節(jié)點組合計算下列值:

增加鏈路的原則是:選擇AL(i，j)最大的一對鏈路節(jié)點間追加一條鏈路，這樣不僅均衡了節(jié)點的抗毀性，同時也考慮了業(yè)務(wù)量需求、地形復(fù)雜度和實際距離等因素。

當(dāng)網(wǎng)絡(luò)達到一定的規(guī)模后，將產(chǎn)生許多冗余的資源，這些冗余的資源并不一定都是必要的，這時就要依據(jù)一定的原則刪除一些鏈路，為每一條現(xiàn)存的鏈路定義一個稱為鏈路冗余度LC的值，其定義如下:

式中，Wij為虛擬全連通網(wǎng)絡(luò)下的邊權(quán)值;LSI(i，j)為節(jié)點i至節(jié)點j的鏈路分割因子;Cij為鏈路容量;fij為在一定路由法則下鏈路上的流量;Cij－fij/Cij為相對剩余容量。刪除一條鏈路的原則為:刪除具有最大LC(i，j)值的鏈路。很明顯:這樣的刪除原則必將刪除那些對網(wǎng)絡(luò)的抗毀性、承載的業(yè)務(wù)量和資源的節(jié)省等方面最沒有貢獻的鏈路。

利用上述原則，研究了一個網(wǎng)絡(luò)設(shè)計的流程，其具體過程如下:

①輸入干線節(jié)點的位置、每條干線的容量C和網(wǎng)絡(luò)中所有節(jié)點對間的業(yè)務(wù)量;

②進行初始網(wǎng)絡(luò)拓撲設(shè)計時，采用式(9)和最優(yōu)生成樹算法;

③確定所有節(jié)點對間的最短路徑并在路徑上加載業(yè)務(wù)，直到某條鏈路成為飽和鏈路;

④消除飽和鏈路，檢查剩余網(wǎng)絡(luò)的連通性。若為連通網(wǎng)絡(luò)則以剩余容量為鏈路最大可用流量，剩余節(jié)點對間的業(yè)務(wù)量作為初始業(yè)務(wù)量，以剩余連通網(wǎng)絡(luò)為初始網(wǎng)絡(luò)，否則跳至步驟⑥;

⑤判斷是否已分配完所有節(jié)點間的業(yè)務(wù)，若是則跳至步驟⑧，否則跳至步驟③;

⑥判斷是否還有未分配的業(yè)務(wù)，若有則跳至步驟⑦，否則跳至步驟⑧;

⑦ 計算各節(jié)點的 NSI、Wij、AL(i，j)，尋找 AL(i，j)最大的節(jié)點對;在原拓樸上增加節(jié)點i’、j’間容量為C的鏈路，跳至步驟③;

⑧計算并判斷NIF、LIF是否滿足要求，若是則終止;否則計算現(xiàn)存各邊的冗余度LC，從原始拓樸中去掉LC最大的鏈路;計算每個節(jié)點對的AL(i’，j’)，找到使 AL(i’，j’)最大的節(jié)點對 i’，j’;在原拓樸上上增加節(jié)點i’、j’間容量為C的鏈路。

4 結(jié)束語

上述提出了滿足一定業(yè)務(wù)需求的抗毀網(wǎng)絡(luò)設(shè)計概念，給出了抗毀網(wǎng)絡(luò)設(shè)計、求解模型的主要流程。網(wǎng)絡(luò)的性能并不是各設(shè)備性能的簡單代數(shù)和，優(yōu)化的網(wǎng)絡(luò)設(shè)計模型可利用性能不佳的設(shè)備構(gòu)建性能相對好的網(wǎng)絡(luò)，特別是針對目前經(jīng)費、技術(shù)受限情況進行網(wǎng)絡(luò)優(yōu)化設(shè)計研究其意義更加重大。通信網(wǎng)絡(luò)設(shè)計與具體使用需求密切相關(guān)。因此文章的設(shè)計思路并不普適于所有網(wǎng)絡(luò)，要根據(jù)具體情況加以具體分析和應(yīng)用。

［1］SAKSENA V R.Topological Analysis of Packet Network［J］.IEEE Journal on Select Areas in Communications，1989，7(8):35 －38.

［2］COAN B A，LELAND W E，VECECHI M P.Using Distributed Topology Update and Preplanned Configuration to Achieve Trunk Network Survivability ［J］.IEEE Trans Relialibity，1991，40(4):404 －416.

［3］徐俊明.圖論及其應(yīng)用(第2版)［M］.合肥:中國科學(xué)技術(shù)大學(xué)出版社，2004:171－254.

［4］陳建國，姜 鋒.通信網(wǎng)基于業(yè)務(wù)的抗毀性分析［J］.無線電通信技術(shù)，1998，24(3):18 －22.

［5］張中偉，陳建國.抗毀通信網(wǎng)絡(luò)設(shè)計［J］.無線電通信技術(shù)，2000，26(2):32 －38.

［6］鐘聯(lián)炯，徐 鋒.通信網(wǎng)絡(luò)拓樸抗毀性算法［J］.火力與指揮控制，2003，28(6):113 －114.

［7］呂久明，張 于，楊曉靜.軍事通信網(wǎng)抗毀性能的神經(jīng)網(wǎng)絡(luò)方法研究［J］.電子對抗技術(shù)，2003，18(1):35－38.