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

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

0 引言

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

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

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

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

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

①網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不同。相同數(shù)目節(jié)點,一般節(jié)點平均連通度越高,其網(wǎng)絡(luò)可靠性越可靠。在相同網(wǎng)絡(luò)拓?fù)淝疤嵯?增加節(jié)點或者鏈路將會改變原有的可靠性。所以網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不同將影響整個網(wǎng)絡(luò)的可靠性;

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

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

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

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

2.1 條件假設(shè)

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

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

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

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

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

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

2.2 算法分析

算法分析如下:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 節(jié)點和邊分析

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

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

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

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

3.2 節(jié)點可靠性計算

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

根據(jù)概率論中的知識可知: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é)點1到節(jié)點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é)點1為例,根據(jù)上面介紹的方法可以求出其他節(jié)點的可靠性值。節(jié)點1到節(jié)點6的可靠性值如表1所示。

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

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

3.3 網(wǎng)絡(luò)可靠性評價

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

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

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

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

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

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

4 結(jié)束語

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

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