劉京和

(總參信息化部軍事代表局,北京100840)

0 引言

通信網(wǎng)可靠性分析是目前被廣泛研究的課題之一。在種種不同的網(wǎng)絡(luò)可靠性問(wèn)題中,端對(duì)端可靠性是研究得最多的課題。在該問(wèn)題中,往往是給出具有2個(gè)規(guī)定節(jié)點(diǎn)(源和匯)的網(wǎng)絡(luò)G以及節(jié)點(diǎn)和鏈路的故障概率,求源和匯之間至少有一條通路的概率。

無(wú)向網(wǎng)絡(luò)端對(duì)端可靠性與有向網(wǎng)不同,具有不可靠節(jié)點(diǎn)的有向網(wǎng)能夠比較容易地轉(zhuǎn)化成具有完全可靠節(jié)點(diǎn)的有向網(wǎng),而無(wú)向網(wǎng)目前還不能進(jìn)行上述轉(zhuǎn)化,因此端對(duì)端可靠性算法對(duì)有向網(wǎng)是通用的,而對(duì)無(wú)向網(wǎng)卻不能通用。目前,大量文獻(xiàn)研究解決的是假定節(jié)點(diǎn)完全可靠、鏈路不可靠情況下無(wú)向網(wǎng)絡(luò)端對(duì)端可靠度分析算法。該文提出了一種無(wú)向網(wǎng)絡(luò)中通用的可靠性算法,無(wú)論節(jié)點(diǎn)和鏈路可靠與否,都可直接進(jìn)行分析和計(jì)算。

1 分解定理

為了對(duì)無(wú)向網(wǎng)進(jìn)行簡(jiǎn)化和分解,首先對(duì)幾個(gè)關(guān)鍵的定理進(jìn)行推導(dǎo)。定理中的參數(shù)表示如下。

G(V,E)：網(wǎng)絡(luò) G,其中 V為節(jié)點(diǎn),E為鏈路;

G-x：從網(wǎng)絡(luò)G中刪去x后的網(wǎng)絡(luò);

G*x：從網(wǎng)絡(luò)G中吸收掉x后的網(wǎng)絡(luò);

s：網(wǎng)絡(luò)的源節(jié)點(diǎn);

t：網(wǎng)絡(luò)的目標(biāo)(匯)節(jié)點(diǎn);

vi：網(wǎng)絡(luò)中的第 i個(gè)節(jié)點(diǎn);

ei,j：網(wǎng)絡(luò)中節(jié)點(diǎn)vi和vj之間的鏈路;

{ei,j}：與節(jié)點(diǎn) vi連接的鏈路集;

pi,qi：網(wǎng)絡(luò)中節(jié)點(diǎn)vi可靠、故障的概率;

pi,j,qi,j：網(wǎng)絡(luò)中鏈路 ei,j可靠、故障的概率;

R(G)：不包括節(jié)點(diǎn)vs和vt的端對(duì)端s-t可靠度;

Rs-t(G,pv,pe)：G的端對(duì)端 s-t可靠度,即Rs-t(G,pv,pe)=R(G)?ps?pt。

定義網(wǎng)絡(luò)G為單調(diào)關(guān)聯(lián)系統(tǒng),有結(jié)構(gòu)函數(shù) φ,φ∈{CS}。

定理1 設(shè) φ∈{CS},則對(duì)任意的 i∈N和 x,有：

上式稱為 φ的分解公式。

證明：因?yàn)?/p>

上式右端即定理1中公式右端。

定理2 網(wǎng)絡(luò)G可靠度分解公式

其中 G-x為從網(wǎng)絡(luò)G中刪去x后的網(wǎng)絡(luò),G*x為從網(wǎng)絡(luò)G中吸收掉x后的網(wǎng)絡(luò)。

證明：由定理1分解公式

φ(x)=xiφ(1i,x)+(1-xi)φ(0i,x),再由網(wǎng)絡(luò)部件獨(dú)立性即得證。

定理3 設(shè)網(wǎng)絡(luò)G中存在一條s-t通路

s-t通路的鏈路是 ei-1,i,0≤i≤k,節(jié)點(diǎn)是vi,1≤i≤k-1。

式中,R(G*e0,1*v1*e1,2*v2*…*vk-1*ek-1,k)=1,最后該條s-t通路收縮成一條完全可靠的鏈路。

證明：如果G中不存在s-t通路,Rs-t(G)=0。如果有s-t通路,可以對(duì)鏈路e0,1進(jìn)行分解。因此：

在G*e0,1中,節(jié)點(diǎn)s和v1視為用概率為1的鏈路連接,同時(shí)把節(jié)點(diǎn)v1與其相連接的鏈路都刪去,有

類似地,對(duì)k條鏈路和k-1個(gè)節(jié)點(diǎn)應(yīng)用分解定理2k-1次,有定理3。

2 分解算法與流程

2.1 分解算法

為求具有長(zhǎng)度為2k-1的s-t通路網(wǎng)絡(luò)可靠度R(G),把網(wǎng)絡(luò)G分解成2k-1個(gè)子網(wǎng)絡(luò),一直分解下去,最終可遞歸解出R(G)?？梢?jiàn),至少有一條s-t通路的每個(gè)子網(wǎng)絡(luò)要比原先網(wǎng)絡(luò)簡(jiǎn)單。

在式(1)中,若網(wǎng)絡(luò)G的節(jié)點(diǎn)完全可靠,式(1)可以被簡(jiǎn)化為：

同樣,若網(wǎng)絡(luò)G的鏈路完全可靠,式(1)可以被簡(jiǎn)化為：

最終可得網(wǎng)絡(luò)G規(guī)定節(jié)點(diǎn)對(duì)s-t之間的可靠度為：

2.2 分解流程

根據(jù)式(1),無(wú)向網(wǎng)絡(luò)G化簡(jiǎn)分解算法簡(jiǎn)述如下：

①尋找G中最短的一條s-t通路,令x=1;

②去掉第x個(gè)部件,得到子圖G-x。把子圖及相關(guān)數(shù)據(jù)pi放入堆棧中;

③如果可利用化簡(jiǎn)規(guī)則的話,進(jìn)行deg(v)=1和deg(v)=2化簡(jiǎn);

④如果G-x仍有s-t通路,回到第1步,否則從堆棧中取出相應(yīng)數(shù)據(jù)計(jì)算R;

⑤從堆棧中取出子圖G,令x=x+1,如果x≤2k-1,回到第2步,如果 x=2k結(jié)束。

其流程圖如圖1所示。

每個(gè)網(wǎng)絡(luò)在找s-t通路之前,都先進(jìn)行化簡(jiǎn)。這樣才能有效地減低子網(wǎng)絡(luò)的復(fù)雜程度。對(duì)每個(gè)子網(wǎng)絡(luò)反復(fù)利用上述算法,遞歸解出它們,然后再將其合并就是最終的結(jié)果。由于具有失效概率為q的單元部件(鏈路和/或節(jié)點(diǎn))的數(shù)量每步至少減少1個(gè),每次遞歸中,循環(huán)深度由網(wǎng)絡(luò)單元部件數(shù)量決定,遞歸算法需要內(nèi)存為O(#節(jié)點(diǎn)數(shù)2?#單元部件數(shù))?？梢?jiàn),對(duì)每個(gè)子網(wǎng)絡(luò)尋找一條最短的s-t通路是使算法最優(yōu)的重要條件之一。

圖1 網(wǎng)絡(luò)端到端可靠性計(jì)算的簡(jiǎn)化流程圖

3 端到端可靠度計(jì)算

把該算法表述為一個(gè)函數(shù)UNRP。子程序PATH(G,found,path,length)是尋找一條s-t通路,對(duì)dijkstra或floyd算法略加修改即可。假定G中至少存在一條s-t通路的話,置變量found為真,并利用變量length返回該通路的長(zhǎng)度。該通路上的單元部件序列用一維數(shù)組變量path(i)返回。計(jì)算程序所需的輸入數(shù)據(jù)用一個(gè)加權(quán)鄰接矩陣表示,二維數(shù)組變量為 entry(i,j)。i≠j時(shí),代表從節(jié)點(diǎn)vi到vj鏈路的可靠度;i=j時(shí),代表節(jié)點(diǎn) vi的可靠度。網(wǎng)絡(luò)化簡(jiǎn)在計(jì)算機(jī)的端對(duì)端可靠度過(guò)程中,對(duì)減少網(wǎng)絡(luò)狀態(tài)數(shù)和占機(jī)CPU運(yùn)行時(shí)間起著重要的作用。

Wood討論了計(jì)算機(jī)網(wǎng)絡(luò)可靠度的化簡(jiǎn)方法[2]。對(duì)無(wú)向網(wǎng)絡(luò)端對(duì)端可靠度的計(jì)算,常用的化簡(jiǎn)方法有節(jié)點(diǎn)degree-1,degree-2及并聯(lián)化簡(jiǎn)?；?jiǎn)必須保證不改變網(wǎng)絡(luò)的可靠度為原則。

令網(wǎng)絡(luò)G(V,E)化簡(jiǎn)后的網(wǎng)絡(luò)為G'(V',E'),對(duì)應(yīng)的可靠度有如下的關(guān)系：

式中,C0是化簡(jiǎn)常數(shù)。

對(duì)無(wú)向網(wǎng)絡(luò)端對(duì)端可靠度計(jì)算中化簡(jiǎn)規(guī)則給出如下。

3.1 Degree-1化簡(jiǎn)

令Let deg(vi)=1,vi∈V

情形1：i=s或j=t。網(wǎng)絡(luò)G中有鏈路ei,j和節(jié)點(diǎn)vi(或 vj),ei,j∈E,vi(vj)∈V。那么,吸收掉 ei,j和vi(或 vj)獲得網(wǎng)絡(luò) G'。對(duì)于 j=t,C0=pi,jpj,V'=V-vj,E'=E-ei,j,對(duì)于 i=s,C0=pipi,j,V'=V-vi,E'=E-ei,j。

情形2：i≠s(或 t)。網(wǎng)絡(luò) G中有鏈路,ei,j,和節(jié)點(diǎn),vi(或vj),ei,j∈E,vi(vj)∈V。那么,刪去 ei,j和vi(或vj)獲得網(wǎng)絡(luò) G'。C0=1,V'=V-vi,E'=E-ei,j。

3.2 Degree-2化簡(jiǎn)

情形1：網(wǎng)絡(luò)G中的鏈路完全可靠時(shí),設(shè)在節(jié)點(diǎn)va和vb之間存在2個(gè)串聯(lián)節(jié)點(diǎn)vi和vj,deg(vi)=deg(vj)=2,ea,i,ei,j,ej,b∈E,vi,vj∈V。那么,用一個(gè)新的節(jié)點(diǎn)vc代替vi,ei,j和vj,得到網(wǎng)絡(luò)G'。C0=1,pc=pi,jpj,V'=V-vi-vj+vc,E'=E-ei,j。

情形2：其他。設(shè)網(wǎng)絡(luò)G中有兩條串聯(lián)的鏈路ei,j和ej,k,其中 deg(vj)=2,ei,j,ej,k∈ E,vj∈ V。那么,用一條新的鏈路ei,k代替ei,j,vj和ej,k,得到網(wǎng)絡(luò)G'。C0=1,pi,k=pi,jpjpj,k,V'=V-vj,E'=E-ei,j-ej,k+ei,k。

3.3 并聯(lián)化簡(jiǎn)

4 算法分析

圖2給出了3個(gè)有代表性的無(wú)向網(wǎng)絡(luò)[1]。

圖2 3種代表性的無(wú)向網(wǎng)絡(luò)

圖2分別為最簡(jiǎn)網(wǎng)絡(luò) G1、中等復(fù)雜網(wǎng)絡(luò) G2和較大復(fù)雜網(wǎng)絡(luò)G3。如表1所示,對(duì)應(yīng)以下3種情況計(jì)算網(wǎng)絡(luò)G1、G2、G3的可靠度：網(wǎng)絡(luò)中節(jié)點(diǎn)完全可靠,鏈路不可靠;鏈路完全可靠、節(jié)點(diǎn)不可靠;以及節(jié)點(diǎn)和鏈路均不可靠。網(wǎng)絡(luò)部件故障率分別為10%、20%和30%。表2摘錄了文獻(xiàn)報(bào)道的算法、語(yǔ)言、運(yùn)算時(shí)間開(kāi)銷與該文相應(yīng)結(jié)果的比較。

表1 網(wǎng)絡(luò)可靠性計(jì)算結(jié)果

表2 無(wú)向網(wǎng)絡(luò)端對(duì)端s-t的算法的比較

通過(guò)對(duì)算法的分析,表1給出網(wǎng)絡(luò)可靠性計(jì)算結(jié)果。不難看出,該文中的算法優(yōu)于參考文獻(xiàn)中的算法。

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

針對(duì)無(wú)向網(wǎng)絡(luò)端對(duì)端可靠性算法不通用的特點(diǎn),對(duì)傳統(tǒng)可靠性算法進(jìn)行優(yōu)化,無(wú)論節(jié)點(diǎn)和鏈路可靠與否,都可直接進(jìn)行分析和計(jì)算。該算法大大降低計(jì)算的復(fù)雜度,在無(wú)向網(wǎng)絡(luò)端對(duì)端可靠性的分析和計(jì)算中,簡(jiǎn)化了計(jì)算流程,大大減少計(jì)算時(shí)間,適用性好,可作為無(wú)向網(wǎng)絡(luò)端對(duì)端可靠性分析的通用算法。

[1]KALIMULINA E Y.A parallel Algorithm forReliability Optimization of Communications Systems[C]∥SIBCON(Siberian Conference on Control and Communications),2009：22-24.

[2]WOOD R K.Factoring algorithm for computing K-terminal network reliability[J].IEEE Trans.Reliability,1986,35：269-278.

[3]BUZACOTT J A.A recursive algorithm for finding reliability related to The connection of nodes in graph[J].Network,1980,10：38-43.

[4]PROVAN J S,BALL M O.Computing network reliability in time polynomial in the number of cuts[J].Operations Research,1984,32：65-70.

[5]BAILEY M P,KULKAMI V G.A recursive algorithm for computing exactreliabilitymeasures[J].IEEE Trans.Reliability,1986,35：36-40.

[6]PAGE L B,PERRY J E.A practical implementation of the factoring theorem for network reliability[J].IEEE Trans.Reliability,1988,37：259-267.