基于最短路徑的網(wǎng)絡(luò)可靠性評(píng)估算法

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

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

0 引言

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

1 網(wǎng)絡(luò)可靠性定義及影響因素分析[4]

目前關(guān)于網(wǎng)絡(luò)可靠性的描述方法主要包括:網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、研究對(duì)象、條件和功能等。

網(wǎng)絡(luò)可靠性定義主要從抗毀性和生存性2個(gè)方面描述,即在一定條件下,網(wǎng)絡(luò)節(jié)點(diǎn)和連接線路能夠正常運(yùn)行和連通,保證網(wǎng)絡(luò)拓?fù)涞耐暾院凸δ艿挠行圆皇苡绊憽？煽啃酝ǔＲ云骄收闲迯?fù)時(shí)間、平均故障間隔時(shí)間、可靠度、可用度及失效性等等來作為評(píng)價(jià)指標(biāo)。可靠性還可以從拓?fù)浣Y(jié)構(gòu)保持連通的能力及網(wǎng)絡(luò)保持通信的能力2個(gè)方面描述。各種描述方法的核心思想基本一致,即網(wǎng)絡(luò)可靠性是指網(wǎng)絡(luò)在規(guī)定的條件下,在規(guī)定的時(shí)間內(nèi),完成指定功能的能力,記為R(t)。

網(wǎng)絡(luò)可靠性的影響因素主要包括如下幾個(gè)方面:

①網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不同。相同數(shù)目節(jié)點(diǎn),一般節(jié)點(diǎn)平均連通度越高,其網(wǎng)絡(luò)可靠性越可靠。在相同網(wǎng)絡(luò)拓?fù)淝疤嵯?增加節(jié)點(diǎn)或者鏈路將會(huì)改變?cè)械目煽啃浴Ｋ跃W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不同將影響整個(gè)網(wǎng)絡(luò)的可靠性;

②網(wǎng)絡(luò)節(jié)點(diǎn)和網(wǎng)絡(luò)鏈路性能不同。網(wǎng)絡(luò)是由節(jié)點(diǎn)和鏈路組成的,在相同拓?fù)浣Y(jié)構(gòu)前提下,節(jié)點(diǎn)和鏈路的可靠性越高,其抗打擊能力就越強(qiáng),生存能力就越強(qiáng),整個(gè)網(wǎng)絡(luò)的可靠性將越好。所以節(jié)點(diǎn)和鏈路性能不同將影響整個(gè)網(wǎng)絡(luò)的可靠性;

③網(wǎng)絡(luò)故障診斷能力和恢復(fù)能力不同。網(wǎng)絡(luò)的故障率越高,整個(gè)網(wǎng)絡(luò)的可靠性將越低,所以通過降低故障出現(xiàn)概率,提高網(wǎng)絡(luò)自我修復(fù)能力,這將有效控制故障發(fā)生,從而提升網(wǎng)絡(luò)可靠性;

④網(wǎng)絡(luò)所處環(huán)境不同。網(wǎng)絡(luò)是由節(jié)點(diǎn)和鏈路組成,網(wǎng)絡(luò)所處的環(huán)境將影響節(jié)點(diǎn)和鏈路的性能,從而影響整個(gè)網(wǎng)絡(luò)的可靠性,以及其他影響網(wǎng)絡(luò)生存性和抗毀性的因素。

2 網(wǎng)絡(luò)可靠性模型假設(shè)與算法分析

2.1 條件假設(shè)

網(wǎng)絡(luò)是連通的,網(wǎng)絡(luò)模型由圖G來替代,發(fā)送和接收設(shè)備用非空頂點(diǎn)V表示,鏈路設(shè)備用邊E表示,整個(gè)圖記為:

網(wǎng)絡(luò)結(jié)構(gòu)中沒有重邊和自環(huán),不存在備份節(jié)點(diǎn)和邊。

網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊其可靠性是按一定概率工作即

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

節(jié)點(diǎn)的地位相同,即節(jié)點(diǎn)可靠性值相同;鏈路的地位相同,即鏈路可靠性值相同。

網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路的可靠性都比較高。

2.2 算法分析

算法分析如下:

①將網(wǎng)絡(luò)節(jié)點(diǎn)按順序從1到n進(jìn)行編號(hào);②從節(jié)點(diǎn)1開始分別對(duì)其余節(jié)點(diǎn)尋找最短路徑和次短路徑;

③在多條最短路徑中有共同邊時(shí)以公共邊作為割邊進(jìn)行分割,并分別計(jì)算其可靠性值,最后用串聯(lián)分布條件下進(jìn)行可靠性值相乘得到2個(gè)節(jié)點(diǎn)之間的可靠性值;

④計(jì)算出節(jié)點(diǎn)1與其他節(jié)點(diǎn)之間最短路徑和次短路徑的可靠性值;

⑤用概率論的方法在網(wǎng)絡(luò)中只有一條最短路徑的前提下,將最短路徑和次短路徑的可靠性值并聯(lián)計(jì)算出節(jié)點(diǎn)和節(jié)點(diǎn)之間的可靠性值,在要求不高時(shí),次短路徑多條時(shí)只需要用一條進(jìn)行計(jì)算;在有多條最短路徑的前提下就不需要考慮此短路徑的可靠性;

⑥將一個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)之間的可靠性值進(jìn)行平均,將其作為這個(gè)節(jié)點(diǎn)的可靠性值;

⑦將所有節(jié)點(diǎn)的平均值進(jìn)行再平均即可以作為整個(gè)網(wǎng)絡(luò)的可靠性值。

為表述簡(jiǎn)單清楚,設(shè)定節(jié)點(diǎn)可靠性值為1,即完全可靠;鏈路可靠性值為β。

因?yàn)楝F(xiàn)在的網(wǎng)絡(luò)單條鏈路其可靠性都比較高,能達(dá)到0.9以上,所以2個(gè)節(jié)點(diǎn)之間的最短路徑和次短路徑可靠性值的并聯(lián)或者多條最短路徑可靠性值的并聯(lián)完全可以代替這2個(gè)節(jié)點(diǎn)之間的可靠性的值,如圖1和圖2所示。

圖1 有2條鏈路的節(jié)點(diǎn)

圖2 有3條鏈路的節(jié)點(diǎn)

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

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

比較可以得出:R(1)≈R(2)。所得出的結(jié)果表示在節(jié)點(diǎn)和鏈路可靠性值比較高時(shí),節(jié)點(diǎn)之間由最短路徑和次短路徑計(jì)算得到的網(wǎng)絡(luò)可靠性值約等于整個(gè)網(wǎng)絡(luò)的可靠性值。

3 模型建立與其可靠性計(jì)算

3.1 節(jié)點(diǎn)和邊分析

將圖3記為式(1)形式,其節(jié)點(diǎn)從上到下從左到右依次編號(hào)為1～6。

圖3 網(wǎng)絡(luò)模型圖

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

式中,β的值可以按網(wǎng)絡(luò)情況不同而自行設(shè)定并且0≤β≤1。

3.2 節(jié)點(diǎn)可靠性計(jì)算

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

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

為方便表述,假設(shè) β=0.9,所以可以求得:R(1,2)=P(1,2)=0.981表示節(jié)點(diǎn)1到節(jié)點(diǎn)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。

以上是以節(jié)點(diǎn)1為例,根據(jù)上面介紹的方法可以求出其他節(jié)點(diǎn)的可靠性值。節(jié)點(diǎn)1到節(jié)點(diǎn)6的可靠性值如表1所示。

表1 節(jié)點(diǎn)間的可靠性值

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

3.3 網(wǎng)絡(luò)可靠性評(píng)價(jià)

從以上論述可以知道,一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的可靠性指數(shù)越高,這個(gè)節(jié)點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)的可靠性貢獻(xiàn)越大[5],說明這個(gè)節(jié)點(diǎn)越靠近信息傳輸中心節(jié)點(diǎn),所以可以用各個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)的可靠性值的平均值作為這各節(jié)點(diǎn)的一個(gè)綜合可靠性值,而整個(gè)網(wǎng)絡(luò)的可靠性值,在所有節(jié)點(diǎn)地位相同的條件下將它們也進(jìn)行平均,即可以得到整個(gè)網(wǎng)絡(luò)的可靠性值。

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

R(1平均)表示節(jié)點(diǎn)1到其余各節(jié)點(diǎn)的平均可靠性值,其值越大表示節(jié)點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)的可靠性的貢獻(xiàn)越大。

以上例為例可以求得節(jié)點(diǎn)1～6到其余各節(jié)點(diǎn)的平均可靠性值:

根據(jù)上文所述,將R(X平均)取均值即表示整個(gè)網(wǎng)絡(luò)的可靠性值,用R(G)=R(節(jié)點(diǎn)平均)表示,其值越高表示整個(gè)網(wǎng)絡(luò)越可靠。

整個(gè)網(wǎng)絡(luò)的可靠性值為:R(G)=R(節(jié)點(diǎn)平均)=0.944 1,這表示整個(gè)網(wǎng)絡(luò)的可靠性值為0.9441。

4 結(jié)束語

現(xiàn)在網(wǎng)絡(luò)越來越復(fù)雜,拓?fù)浣Y(jié)構(gòu)也越來越復(fù)雜,而節(jié)點(diǎn)和鏈路的可靠性卻越來越高,每一個(gè)節(jié)點(diǎn)自身的可靠性都將影響整個(gè)網(wǎng)絡(luò)的可靠性,所以可以通過該描述的方法進(jìn)行整個(gè)網(wǎng)絡(luò)可靠性評(píng)估的同時(shí),也能將網(wǎng)絡(luò)中薄弱節(jié)點(diǎn)找出來,在以后的網(wǎng)絡(luò)改進(jìn)時(shí)能夠有目的地進(jìn)行加強(qiáng)。該描述的方法在現(xiàn)在網(wǎng)絡(luò)硬件發(fā)展迅速的時(shí)代不能算是復(fù)雜,而且效果比較好,精確性也比較高,能夠提高整個(gè)網(wǎng)絡(luò)的評(píng)估效果。然而不足之處是對(duì)于大型復(fù)雜網(wǎng)絡(luò)這種方法不太適合,這將是下一步研究的重點(diǎn)。

[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]馮海林.網(wǎng)絡(luò)系統(tǒng)中可靠性問題的研究[D].西安:西安電子科技大學(xué),2004:33-36.

[5]羅景峰.全終端計(jì)算機(jī)通信網(wǎng)絡(luò)可靠性模型及算法研究[D].沈陽:沈陽工業(yè)大學(xué),2007:42-46.