基于抗毀性和最小費(fèi)用的網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)方法

李丹鏑

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

1.2.1 NIF

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

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

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

1.2.2 LIF

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

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

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

1.2.3 NSI

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

對(duì)于一個(gè)特定節(jié)點(diǎn)，在不同長(zhǎng)度路徑中的貢獻(xiàn)的求和就可得到其節(jié)點(diǎn)分割因子:

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

1.2.4 LSI

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

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

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

2 飽和割集算法

2.1 基本原理

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

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

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

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

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

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

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

2.2 算法流程

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

2.3 飽和割集確定和消除

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

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

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

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

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

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

DELETE-ONLY算法的起始拓?fù)涫歉哌B通拓?fù)?。?dāng)網(wǎng)絡(luò)吞吐量大于指標(biāo)要求時(shí)，每次迭代只需消除一條鏈路，從而達(dá)到吞吐量和總費(fèi)用的要求。用Ei來(lái)表示鏈路利用率和費(fèi)用，定義如下:

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

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

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

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

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

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

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

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

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

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

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

這樣便得到了初始連通拓?fù)涞纳蓸洌渲羞厵?quán)同時(shí)考慮了業(yè)務(wù)量和費(fèi)用的約束，初始連通拓?fù)浒速M(fèi)用需求和業(yè)務(wù)量需求的雙重因素。

網(wǎng)絡(luò)設(shè)計(jì)應(yīng)該是在初始連通網(wǎng)絡(luò)拓?fù)涞幕A(chǔ)上，通過(guò)增加/刪除鏈路來(lái)改善網(wǎng)絡(luò)綜合性能，下面提出增加/刪除鏈路的原則。

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

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

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

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

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

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

②進(jìn)行初始網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)時(shí)，采用式(9)和最優(yōu)生成樹算法;

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

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

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

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

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

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

4 結(jié)束語(yǔ)

上述提出了滿足一定業(yè)務(wù)需求的抗毀網(wǎng)絡(luò)設(shè)計(jì)概念，給出了抗毀網(wǎng)絡(luò)設(shè)計(jì)、求解模型的主要流程。網(wǎng)絡(luò)的性能并不是各設(shè)備性能的簡(jiǎn)單代數(shù)和，優(yōu)化的網(wǎng)絡(luò)設(shè)計(jì)模型可利用性能不佳的設(shè)備構(gòu)建性能相對(duì)好的網(wǎng)絡(luò)，特別是針對(duì)目前經(jīng)費(fèi)、技術(shù)受限情況進(jìn)行網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)研究其意義更加重大。通信網(wǎng)絡(luò)設(shè)計(jì)與具體使用需求密切相關(guān)。因此文章的設(shè)計(jì)思路并不普適于所有網(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］.合肥:中國(guó)科學(xué)技術(shù)大學(xué)出版社，2004:171－254.

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

［5］張中偉，陳建國(guó).抗毀通信網(wǎng)絡(luò)設(shè)計(jì)［J］.無(wú)線電通信技術(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］.電子對(duì)抗技術(shù)，2003，18(1):35－38.