基于最短路徑的網絡可靠性評估算法

李琳琳,梅 生,李 釗,李承劍

(1.第二炮兵工程學院,陜西西安710025;2.第二炮兵駐石家莊軍事代表室,河北石家莊050000)

0 引言

隨著網絡的發展,其復雜性越來越高,網絡節點和鏈路的可靠性也在不斷增強,如何更好更直觀地評估整個網絡[1],尋找出網絡的薄弱環節,讓信息得到更加可靠的傳播已有不少研究成果,如基于跳面節點法,節點收縮法以及其他一些智能方法[2],其中跳面節點法可用于解決有層次性的網絡的整體可靠性問題,但存在計算復雜以及對小網絡計算結果不理想等不足;節點收縮法可用于簡化整體網絡解決計算過程中的復雜性問題,存在計算不夠精確的不足,智能算法計算結果比較理想,但存在計算復雜度過高等問題[3]。為此在研究了網絡最短路徑的基礎上,提出了一種基于平均值的網絡可靠性計算方法,具有算法復雜度低和計算速度快等特點。

1 網絡可靠性定義及影響因素分析[4]

目前關于網絡可靠性的描述方法主要包括:網絡拓撲結構、研究對象、條件和功能等。

網絡可靠性定義主要從抗毀性和生存性2個方面描述,即在一定條件下,網絡節點和連接線路能夠正常運行和連通,保證網絡拓撲的完整性和功能的有效性不受影響。可靠性通常以平均故障修復時間、平均故障間隔時間、可靠度、可用度及失效性等等來作為評價指標?？煽啃赃€可以從拓撲結構保持連通的能力及網絡保持通信的能力2個方面描述。各種描述方法的核心思想基本一致,即網絡可靠性是指網絡在規定的條件下,在規定的時間內,完成指定功能的能力,記為R(t)。

網絡可靠性的影響因素主要包括如下幾個方面:

①網絡拓撲結構不同。相同數目節點,一般節點平均連通度越高,其網絡可靠性越可靠。在相同網絡拓撲前提下,增加節點或者鏈路將會改變原有的可靠性。所以網絡拓撲結構不同將影響整個網絡的可靠性;

②網絡節點和網絡鏈路性能不同。網絡是由節點和鏈路組成的,在相同拓撲結構前提下,節點和鏈路的可靠性越高,其抗打擊能力就越強,生存能力就越強,整個網絡的可靠性將越好。所以節點和鏈路性能不同將影響整個網絡的可靠性;

③網絡故障診斷能力和恢復能力不同。網絡的故障率越高,整個網絡的可靠性將越低,所以通過降低故障出現概率,提高網絡自我修復能力,這將有效控制故障發生,從而提升網絡可靠性;

④網絡所處環境不同。網絡是由節點和鏈路組成,網絡所處的環境將影響節點和鏈路的性能,從而影響整個網絡的可靠性,以及其他影響網絡生存性和抗毀性的因素。

2 網絡可靠性模型假設與算法分析

2.1 條件假設

網絡是連通的,網絡模型由圖G來替代,發送和接收設備用非空頂點V表示,鏈路設備用邊E表示,整個圖記為:

網絡結構中沒有重邊和自環,不存在備份節點和邊。

網絡中的節點和邊其可靠性是按一定概率工作即

式中,R(G)為節點或鏈路可靠性值;P(G)為節點或鏈路的工作概率值,并且節點與節點以及鏈路與鏈路之間相互獨立。

節點的地位相同,即節點可靠性值相同;鏈路的地位相同,即鏈路可靠性值相同。

網絡中節點和鏈路的可靠性都比較高。

2.2 算法分析

算法分析如下:

①將網絡節點按順序從1到n進行編號;②從節點1開始分別對其余節點尋找最短路徑和次短路徑;

③在多條最短路徑中有共同邊時以公共邊作為割邊進行分割,并分別計算其可靠性值,最后用串聯分布條件下進行可靠性值相乘得到2個節點之間的可靠性值;

④計算出節點1與其他節點之間最短路徑和次短路徑的可靠性值;

⑤用概率論的方法在網絡中只有一條最短路徑的前提下,將最短路徑和次短路徑的可靠性值并聯計算出節點和節點之間的可靠性值,在要求不高時,次短路徑多條時只需要用一條進行計算;在有多條最短路徑的前提下就不需要考慮此短路徑的可靠性;

⑥將一個節點與其他節點之間的可靠性值進行平均,將其作為這個節點的可靠性值;

⑦將所有節點的平均值進行再平均即可以作為整個網絡的可靠性值。

為表述簡單清楚,設定節點可靠性值為1,即完全可靠;鏈路可靠性值為β。

因為現在的網絡單條鏈路其可靠性都比較高,能達到0.9以上,所以2個節點之間的最短路徑和次短路徑可靠性值的并聯或者多條最短路徑可靠性值的并聯完全可以代替這2個節點之間的可靠性的值,如圖1和圖2所示。

圖1 有2條鏈路的節點

圖2 有3條鏈路的節點

圖1中節點a和b之間的2條鏈路可靠性值分別為0.95和0.9,那它們之間的可靠性值為:R(1)=0.995。

圖2中節點c和d之間的2條鏈路可靠性值分別為0.95、0.9和0.6,那它們之間的可靠性值為:R(2)=0.997。

比較可以得出:R(1)≈R(2)。所得出的結果表示在節點和鏈路可靠性值比較高時,節點之間由最短路徑和次短路徑計算得到的網絡可靠性值約等于整個網絡的可靠性值。

3 模型建立與其可靠性計算

3.1 節點和邊分析

將圖3記為式(1)形式,其節點從上到下從左到右依次編號為1～6。

圖3 網絡模型圖

由于假設圖中各個節點的地位不相同,每條鏈路的可靠性一致,所以在此對節點和鏈路采用主觀賦值法。節點可靠性設為P(V(*)),原本作為割點的關鍵節點可靠性應該要高于普通節點,而為表達清楚和簡化計算將 P(V(*))設為1。鏈路可靠性設為P(E(*)),原本作為割邊的可靠性要高于普通邊,不同的通信鏈路介質有不同的可靠性,而為表達清楚和簡化計算將每條鏈路可靠性設為一致,即

式中,β的值可以按網絡情況不同而自行設定并且0≤β≤1。

3.2 節點可靠性計算

以節點1為例,節點1到節點2的最短路徑為:＜1,2＞,次短路徑為:＜1,5＞、＜5,2＞;其最短路徑可靠性值記為:R(最短)=P(最短)=β。其次短路徑可靠性值記為:R(次短)=P(次短)=β2。

根據概率論中的知識可知:R(1,2)=P(1,2)=1-((1-R(最短))*(1-R(次短)))=1-((1-β)*(1-β2))。

為方便表述,假設 β=0.9,所以可以求得:R(1,2)=P(1,2)=0.981表示節點1到節點2之間的可靠性值為0.981。

同理可以求得:

R(1,3)=0.981,R(1,4)=0.949,R(1,5)=0.996,R(1,6)=0.949,R(1,1)=1。

以上是以節點1為例,根據上面介紹的方法可以求出其他節點的可靠性值。節點1到節點6的可靠性值如表1所示。

表1 節點間的可靠性值

表1中描述的是節點與節點之間的可靠性值,其中節點對自身的可靠性值為 1,即完全可靠。R(1,X)表示節點1和節點X之間的可靠性值,其數值越大,表示節點之間越可靠。在表1中以節點1為例,節點1與自身的可靠性值為1,與節點2的可靠性值為0.981,與節點3的可靠性值為0.981,與節點4的可靠性值為0.949,與節點5的可靠性值為0.996,與節點6的可靠性值為0.949,并由表中的第一行表示。

3.3 網絡可靠性評價

從以上論述可以知道,一個節點到其他節點的可靠性指數越高,這個節點對整個網絡的可靠性貢獻越大[5],說明這個節點越靠近信息傳輸中心節點,所以可以用各個節點與其他節點的可靠性值的平均值作為這各節點的一個綜合可靠性值,而整個網絡的可靠性值,在所有節點地位相同的條件下將它們也進行平均,即可以得到整個網絡的可靠性值。

以節點1為例,R(1平均)=R(1,2)+R(1,3)+R(1,4)+R(1,5)+R(1,6)=0.975 9。

R(1平均)表示節點1到其余各節點的平均可靠性值,其值越大表示節點對整個網絡的可靠性的貢獻越大。

以上例為例可以求得節點1～6到其余各節點的平均可靠性值:

根據上文所述,將R(X平均)取均值即表示整個網絡的可靠性值,用R(G)=R(節點平均)表示,其值越高表示整個網絡越可靠。

整個網絡的可靠性值為:R(G)=R(節點平均)=0.944 1,這表示整個網絡的可靠性值為0.9441。

4 結束語

現在網絡越來越復雜,拓撲結構也越來越復雜,而節點和鏈路的可靠性卻越來越高,每一個節點自身的可靠性都將影響整個網絡的可靠性,所以可以通過該描述的方法進行整個網絡可靠性評估的同時,也能將網絡中薄弱節點找出來,在以后的網絡改進時能夠有目的地進行加強。該描述的方法在現在網絡硬件發展迅速的時代不能算是復雜,而且效果比較好,精確性也比較高,能夠提高整個網絡的評估效果。然而不足之處是對于大型復雜網絡這種方法不太適合,這將是下一步研究的重點。

[1]YEHW C.A Path-based Algorithm for Evaluating the K-outof-n flow Network Reliability[J].Reliability Engineering and System Safety,2005,87(2):243-251.

[2]HARDY G,LUCET C,LIMNIOS N.K-terminal Network Reliability Measures with Binary Decision Diagrams[J].IEEE Transactions on Reliability,2007,56(3):506-515.

[3]TAO YU Tao,CHEN Shanzhi,AI Ming.A Framework for Reliability Computation of the IP Network[C].8th ACIS International Conference on Software Engineering,Artificial Intelligence,Networking,and Parallel/Distributed Computing,2007:323-327.

[4]馮海林.網絡系統中可靠性問題的研究[D].西安:西安電子科技大學,2004:33-36.

[5]羅景峰.全終端計算機通信網絡可靠性模型及算法研究[D].沈陽:沈陽工業大學,2007:42-46.