無向通信網端對端可靠性通用算法

劉京和

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

0 引言

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

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

1 分解定理

為了對無向網進行簡化和分解,首先對幾個關鍵的定理進行推導。定理中的參數表示如下。

G(V,E)：網絡 G,其中 V為節點,E為鏈路;

G-x：從網絡G中刪去x后的網絡;

G*x：從網絡G中吸收掉x后的網絡;

s：網絡的源節點;

t：網絡的目標(匯)節點;

vi：網絡中的第 i個節點;

ei,j：網絡中節點vi和vj之間的鏈路;

{ei,j}：與節點 vi連接的鏈路集;

pi,qi：網絡中節點vi可靠、故障的概率;

pi,j,qi,j：網絡中鏈路 ei,j可靠、故障的概率;

R(G)：不包括節點vs和vt的端對端s-t可靠度;

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

定義網絡G為單調關聯系統,有結構函數 φ,φ∈{CS}。

定理1 設 φ∈{CS},則對任意的 i∈N和 x,有：

上式稱為 φ的分解公式。

證明：因為

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

定理2 網絡G可靠度分解公式

其中 G-x為從網絡G中刪去x后的網絡,G*x為從網絡G中吸收掉x后的網絡。

證明：由定理1分解公式

φ(x)=xiφ(1i,x)+(1-xi)φ(0i,x),再由網絡部件獨立性即得證。

定理3 設網絡G中存在一條s-t通路

s-t通路的鏈路是 ei-1,i,0≤i≤k,節點是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通路,可以對鏈路e0,1進行分解。因此：

在G*e0,1中,節點s和v1視為用概率為1的鏈路連接,同時把節點v1與其相連接的鏈路都刪去,有

類似地,對k條鏈路和k-1個節點應用分解定理2k-1次,有定理3。

2 分解算法與流程

2.1 分解算法

為求具有長度為2k-1的s-t通路網絡可靠度R(G),把網絡G分解成2k-1個子網絡,一直分解下去,最終可遞歸解出R(G)。可見,至少有一條s-t通路的每個子網絡要比原先網絡簡單。

在式(1)中,若網絡G的節點完全可靠,式(1)可以被簡化為：

同樣,若網絡G的鏈路完全可靠,式(1)可以被簡化為：

最終可得網絡G規定節點對s-t之間的可靠度為：

2.2 分解流程

根據式(1),無向網絡G化簡分解算法簡述如下：

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

②去掉第x個部件,得到子圖G-x。把子圖及相關數據pi放入堆棧中;

③如果可利用化簡規則的話,進行deg(v)=1和deg(v)=2化簡;

④如果G-x仍有s-t通路,回到第1步,否則從堆棧中取出相應數據計算R;

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

其流程圖如圖1所示。

每個網絡在找s-t通路之前,都先進行化簡。這樣才能有效地減低子網絡的復雜程度。對每個子網絡反復利用上述算法,遞歸解出它們,然后再將其合并就是最終的結果。由于具有失效概率為q的單元部件(鏈路和/或節點)的數量每步至少減少1個,每次遞歸中,循環深度由網絡單元部件數量決定,遞歸算法需要內存為O(#節點數2?#單元部件數)。可見,對每個子網絡尋找一條最短的s-t通路是使算法最優的重要條件之一。

圖1 網絡端到端可靠性計算的簡化流程圖

3 端到端可靠度計算

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

Wood討論了計算機網絡可靠度的化簡方法[2]。對無向網絡端對端可靠度的計算,常用的化簡方法有節點degree-1,degree-2及并聯化簡。化簡必須保證不改變網絡的可靠度為原則。

令網絡G(V,E)化簡后的網絡為G'(V',E'),對應的可靠度有如下的關系：

式中,C0是化簡常數。

對無向網絡端對端可靠度計算中化簡規則給出如下。

3.1 Degree-1化簡

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

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

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

3.2 Degree-2化簡

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

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

3.3 并聯化簡

4 算法分析

圖2給出了3個有代表性的無向網絡[1]。

圖2 3種代表性的無向網絡

圖2分別為最簡網絡 G1、中等復雜網絡 G2和較大復雜網絡G3。如表1所示,對應以下3種情況計算網絡G1、G2、G3的可靠度：網絡中節點完全可靠,鏈路不可靠;鏈路完全可靠、節點不可靠;以及節點和鏈路均不可靠。網絡部件故障率分別為10%、20%和30%。表2摘錄了文獻報道的算法、語言、運算時間開銷與該文相應結果的比較。

表1 網絡可靠性計算結果

表2 無向網絡端對端s-t的算法的比較

通過對算法的分析,表1給出網絡可靠性計算結果。不難看出,該文中的算法優于參考文獻中的算法。

5 結束語

針對無向網絡端對端可靠性算法不通用的特點,對傳統可靠性算法進行優化,無論節點和鏈路可靠與否,都可直接進行分析和計算。該算法大大降低計算的復雜度,在無向網絡端對端可靠性的分析和計算中,簡化了計算流程,大大減少計算時間,適用性好,可作為無向網絡端對端可靠性分析的通用算法。

[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.