杜永軍, 惠樹鵬, 蔡志強, 孟學(xué)煜

(1.蘭州理工大學(xué) 經(jīng)濟管理學(xué)院,甘肅 蘭州 730050; 2.西北工業(yè)大學(xué) 機電學(xué)院,陜西 西安 710072)

0 引言

K-終端網(wǎng)絡(luò)(簡稱為網(wǎng)絡(luò))是現(xiàn)代通信網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等網(wǎng)絡(luò)系統(tǒng)的抽象數(shù)學(xué)模型，其是由節(jié)點和邊組成的抽象圖，其中一些不可分割的關(guān)鍵節(jié)點組成了終端集合K。例如，在通信網(wǎng)絡(luò)中，節(jié)點可表示交換機，而邊可表示電纜。假設(shè)節(jié)點絕對可靠而邊會以一定的概率發(fā)生失效，K-終端網(wǎng)絡(luò)的可靠性定義為K中任意兩個終端都被一些運行的邊連通的概率[1]。

網(wǎng)絡(luò)可靠性分析的一個重要目標(biāo)是識別網(wǎng)絡(luò)薄弱環(huán)節(jié)以及量化網(wǎng)絡(luò)的邊對網(wǎng)絡(luò)可靠性的影響力。為此，重要度的概念被提出和研究，并被廣泛應(yīng)用于網(wǎng)絡(luò)可靠性優(yōu)化設(shè)計和維修決策。給定二態(tài)關(guān)聯(lián)系統(tǒng)，自從學(xué)者Birnbaum于1969年首次提出重要度分析方法以來，國內(nèi)外許多學(xué)者在系統(tǒng)可靠性和風(fēng)險分析領(lǐng)域，從不同的角度提出了不同的重要度以量化組件對系統(tǒng)可靠性的影響力，包括Fussell-Vesely 重要度，可靠性完成值，可靠性減少值，Barlow-Proschan 重要度，Natvig重要度，以及它們的推廣[2～5]。Zhu等人[6]研究了線形連續(xù)n中選k系統(tǒng)的基于Birnbaum重要度的系統(tǒng)組件的排序模式，并分析了該排序模式關(guān)于組件可靠性和組件總數(shù)的變化機理。崔利榮等人[7]引進了帶有一定稀疏度的連續(xù)系統(tǒng)，并利用有限馬爾可夫鏈嵌入方法建立了該系統(tǒng)的可靠性以及組件的Birnbaum重要度的方程。Hsu和Yuang[8]提出了“兩階段”算法來評估網(wǎng)絡(luò)邊的Birnbaum重要度。Page和Perry[9]定義了網(wǎng)絡(luò)的一條邊的“收縮-刪除”重要度，并利用一種基于圖論技術(shù)的分解算法來評估該重要度的值。但是，對于一般的網(wǎng)絡(luò)，其可靠性和重要度的計算均為NP-難問題，因此Gertsbakh等人[1,10]設(shè)計了基于組合計數(shù)技術(shù)的蒙特卡洛(Monte-Carlo，MC)算法，以近似評估網(wǎng)絡(luò)邊的Fussell-Vesely重要度和Birnbaum重要度。

以上重要度從不同角度量化邊可靠性和邊本身占據(jù)的位置對整個網(wǎng)絡(luò)可靠性的影響程度，其在K-終端網(wǎng)絡(luò)可靠性優(yōu)化和維修決策方面發(fā)揮了巨大的作用。但這些網(wǎng)絡(luò)重要度的計算方法存在一定的局限性，如依賴于邊的可靠性，且需要邊發(fā)生失效相互獨立的條件。對于一些實際應(yīng)用的網(wǎng)絡(luò)，一方面只存在有限的失效數(shù)據(jù)，使得難以通過數(shù)理統(tǒng)計的方法而得到邊的可靠性的值；另一方面由于級聯(lián)失效的原因，導(dǎo)致邊的失效失去獨立性。這些事實極大的限制了網(wǎng)絡(luò)重要度計算方法的應(yīng)用范圍，使得不能滿足對一些現(xiàn)實網(wǎng)絡(luò)開展重要度分析的需求。

在工程實踐中，當(dāng)網(wǎng)絡(luò)處于運行或失效狀態(tài)時，其發(fā)生失效的邊的數(shù)目為一隨機變量，且該隨機變量應(yīng)該滿足一定的概率分布，這就急需開展基于該概率分布的網(wǎng)絡(luò)可靠性建模和重要度計算方法的研究。因此，面向以上網(wǎng)絡(luò)重要度評估的需求，為了突破傳統(tǒng)網(wǎng)絡(luò)重要度計算需已知網(wǎng)絡(luò)邊的可靠性，且邊發(fā)生失效相互獨立的條件限制，本文在給定失效邊數(shù)的概率分布的背景下，構(gòu)建網(wǎng)絡(luò)可靠性模型，并據(jù)此推導(dǎo)出網(wǎng)絡(luò)重要度的計算方法。

1 K-終端網(wǎng)絡(luò)可靠性建模

網(wǎng)絡(luò)中的譜在網(wǎng)絡(luò)可靠性和重要度研究中發(fā)揮著重要的作用，它分為D-譜和C-譜。令隨機變量X表示網(wǎng)絡(luò)中發(fā)生失效的邊的總數(shù)目，從網(wǎng)絡(luò)失效的角度，可定義網(wǎng)絡(luò)的D-譜為F(k)=P(φ=0│X=k)，而邊i的D-譜是F(k,0i)=P(φ=0,xi=0│X=k)，以及F(k,1i)=P(φ=0,xi=1│X=k)，k=1,2,…,n。這些D-譜的概率意義可作如下解釋：當(dāng)給定恰好k條邊發(fā)生失效時，F(xiàn)(k)是網(wǎng)絡(luò)發(fā)生失效的概率；F(k,0i)是網(wǎng)絡(luò)和邊i都發(fā)生失效的概率；F(k,1i)是網(wǎng)絡(luò)失效且邊i運行的概率；注意F(k)=F(k,0i)+F(k,1i)。

相似的，從網(wǎng)絡(luò)運行的角度可定義網(wǎng)絡(luò)C-譜是：F′(k)=P(φ=1│X=n-k)，而邊i的C-譜是：F′(k,1i) =P(φ=1,xi=1│X=n-k)和F′(k,0i)=P(φ=1,xi=0│X=n-k)。這些C-譜的概率意義解釋如下：當(dāng)給定網(wǎng)絡(luò)中恰好有k條邊運行(即n-k條邊恰好發(fā)生失效)時，F(xiàn)′(k)是網(wǎng)絡(luò)運行的概率；F′(k,1i)是網(wǎng)絡(luò)和邊i均運行的概率；F′(k,0i)是網(wǎng)絡(luò)運行且邊i失效的概率。同時需注意F′(k)=F′(k,1i)+F′(k,0i)。

需要指出的是，本文假設(shè)網(wǎng)絡(luò)中所有的邊失效同分布，故D-譜和C-譜的數(shù)量值僅依賴網(wǎng)絡(luò)結(jié)構(gòu)，故又稱為網(wǎng)絡(luò)結(jié)構(gòu)不變量[1]。在網(wǎng)絡(luò)所有全部邊失效同分布的背景下，根據(jù)組合計數(shù)原理，可得P(xi=0│X=k)=k/n。注意，網(wǎng)絡(luò)全部邊失效時，即X=k=n，邊i必然發(fā)生失效，即P(xi=0│X=n)=n/n=1；當(dāng)全部邊運行時，即X=k=0，邊i必運行，即P(xi=0│X=0)=0/n=0。因此，利用全概率公式，可得邊i的失效概率的方程:

(1)

結(jié)合全概率公式和網(wǎng)絡(luò)中的D-譜的定義，可得到下列三個概率方程。

網(wǎng)絡(luò)的失效概率方程：

(2)

網(wǎng)絡(luò)和邊i均失效的概率方程可寫作：

P(φ=0,xi=0)

(3)

此外，網(wǎng)絡(luò)失效且邊i運行的概率方程可寫作：

P(φ=0,xi=1)

(4)

同理，當(dāng)網(wǎng)絡(luò)全部邊失效同分布時，根據(jù)組合計數(shù)原理可得到P(xi=1│X=k)=(n-k)/n，再結(jié)合全概率公式，邊i的可靠性方程可寫作:

(5)

另外，網(wǎng)絡(luò)可靠性方程可寫作：

P(φ=1)

(6)

上面方程(6)的第一個等式是由全概率公式得到，而第二個等式由網(wǎng)絡(luò)C-譜的定義得到。同理，網(wǎng)絡(luò)和邊i均運行的概率方程可寫作如下：

P(φ=1,xi=1)

(7)

網(wǎng)絡(luò)運行且邊i失效的概率方程可寫作：

P(φ=1,xi=0)

(8)

2 K-終端網(wǎng)絡(luò)重要度計算方法

貝葉斯重要度：面向二態(tài)關(guān)聯(lián)系統(tǒng)，當(dāng)系統(tǒng)發(fā)生失效時，工程師感興趣的是究竟哪一個組件引起的系統(tǒng)失效，以及不同的組件對系統(tǒng)失效的貢獻度。為此目的，Birnbaum給出了系統(tǒng)組件貝葉斯重要度。當(dāng)系統(tǒng)失效時，定義一個組件的貝葉斯重要度為這個組件失效的概率，它的數(shù)學(xué)表達式是：BAYi=P(xi=0│φ(x)=0)。

面向K-終端網(wǎng)絡(luò)，當(dāng)給定發(fā)生失效的邊數(shù)的概率分布時，邊i的貝葉斯重要度方程BAYi可寫作：

BAYi=P(xi=0|φ=0)

(9)

Birnbaum重要度：給定一個二態(tài)關(guān)聯(lián)系統(tǒng)，定義組件i的Birnbaum要度如下：由這個組件i狀態(tài)的變化而引起的系統(tǒng)失效概率的改變量，即Ii=P(φ=0│xi=0)-P(φ=0│xi=1)。給定K-終端網(wǎng)絡(luò)，基于條件概率公式，結(jié)合方程(1)，(3)，(4)和(5)，則邊i的Birnbaum重要度Ii可寫作:

(10)

臨界可靠性重要度：當(dāng)一個二態(tài)關(guān)聯(lián)系統(tǒng)處于運行狀態(tài)時，Kuo和Zuo[11]定義了一個組件i的臨界可靠性重要度CSi為這個組件運行且對系統(tǒng)運行致命的概率，其中致命的含義是：當(dāng)該組件運行時，則該系統(tǒng)運行；當(dāng)該組件失效時，則該系統(tǒng)失效。一個組件i的臨界可靠性重要度CSi的數(shù)學(xué)方程可寫作:

(P(φ=1|xi=1)-P(φ=1|xi=0))

(11)

當(dāng)給定K-終端網(wǎng)絡(luò)發(fā)生失效的邊數(shù)的概率分布時，根據(jù)條件概率公式，再將方程(1)，(5)，(6)，(7)和(8)代入方程(11)，則得到邊i的臨界可靠性重要度CSi:

(12)

臨界失效重要度：給定一個二態(tài)關(guān)聯(lián)系統(tǒng)，當(dāng)該系統(tǒng)處于失效的狀態(tài)時，Kuo和Zuo[11]定義了一個組件i的臨界失效重要度CFi，其是該組件失效且對系統(tǒng)失效致命的概率，依據(jù)條件概率公式，整理CFi如下:

(13)

在給定K-終端網(wǎng)絡(luò)發(fā)生失效的邊數(shù)的概率分布的背景下，將方程(1)，(2)，(3)，(4)和(5)代入方程(13)，則可得邊i的臨界失效重要度:

(14)

可靠性減少值：面向二態(tài)關(guān)聯(lián)系統(tǒng)，在組件i失效的背景下，Levitin給出了“可靠性減少值”的重要度RRWi，它量化了系統(tǒng)可靠性的潛在損壞程度，其數(shù)學(xué)方程為:

(15)

在給定K-終端網(wǎng)絡(luò)發(fā)生失效的邊數(shù)的概率分布的背景下，將方程(1)，(6)，(8)，代入方程(15)，則得到:

(16)

可靠性完成值： 面向二態(tài)關(guān)聯(lián)系統(tǒng)，Vasseur等學(xué)者定義了一個組件i的可靠性完成值RAWi，其量化了由于這個組件i的運行而引起的整個系統(tǒng)可靠性增加的百分比，它的數(shù)學(xué)方程可寫作:

(17)

面向K-終端網(wǎng)絡(luò)，當(dāng)給定網(wǎng)絡(luò)發(fā)生失效的邊數(shù)目的概率分布時，依據(jù)條件概率公式，整理方程(17)，并將方程(5)，(6)，(7)，代入后，則得到RAWi的數(shù)學(xué)方程：

(18)

3 算例仿真

給定圖1所示網(wǎng)絡(luò)，其是由30條邊組成的十二面體網(wǎng)絡(luò)，該網(wǎng)絡(luò)可用于刻畫計算機網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，其運行當(dāng)且僅當(dāng)終端1和20被一些運行的邊連通，假設(shè)節(jié)點完全可靠而邊以共同的概率發(fā)生失效，且失效邊數(shù)的總數(shù)目服從參數(shù)為λ的飽和泊松分布，其概率質(zhì)量函數(shù)可寫作:

(19)

需要指出的是，由于發(fā)生失效的邊數(shù)最大值為30(該十二面體網(wǎng)絡(luò)總計只有30條邊)，故該泊松分布在k=30時發(fā)生飽和，稱為飽和泊松分布，其可用于模擬電網(wǎng)中發(fā)生失效的電線數(shù)目的概率分布。

首先利用以色列學(xué)者Gertsbakh等人[1,10]設(shè)計的Monte-Carlo仿真方法得到十二面體網(wǎng)絡(luò)的D-譜和C-譜的近似值，以此為基礎(chǔ)，再結(jié)合該網(wǎng)絡(luò)發(fā)生失效的邊數(shù)的概率質(zhì)量函數(shù)(19)，利用方程(9)，(10)，(12)，(14)，(16)，(18)，分別評估該十二面體網(wǎng)絡(luò)的貝葉斯重要度BAY，Birnbaum重要度I，臨界可靠性重要度CS，臨界失效重要度CF，可靠性減少值RRW，以及可靠性完成值RAW。當(dāng)分布中的參數(shù)λ取較小的值(λ=1)時，取中間的值(λ=15)時，取較大值(λ=40)時，表1，2，3分別報道了根據(jù)這些重要度進行排名的前10名的網(wǎng)絡(luò)邊和相應(yīng)的重要度的值。

圖1 十二面體網(wǎng)絡(luò)K={1,20}

觀察表1，2，3可知，基于同一個重要度，當(dāng)λ取不同值時，則得到不同的網(wǎng)絡(luò)邊排序。例如，基于貝葉斯重要度BAY，當(dāng)λ=1時，邊6，1，5，22，23，24為網(wǎng)絡(luò)中最重要的6條邊；但是，當(dāng)λ=40時，邊6，12，23是網(wǎng)絡(luò)中最重要的3條邊。此外，注意觀察圖1可知，至少需3條邊發(fā)生失效，才能導(dǎo)致終端節(jié)點{1，20}失去連通性，具體的，邊1，5，和6發(fā)生失效，或者邊22，23，24發(fā)生失效。注意這些邊恰為λ=1時，基于貝葉斯重要度BAY識別出的最重要的6條邊；相反，要確保終端節(jié)點{1，20}保持連通性，至少需3條邊維持運行狀態(tài)，即邊6，12，23，而這恰為λ=40時，貝葉斯重要度BAY識別出的最重要的3條邊。

根據(jù)表1，2，3可知，當(dāng)我們固定λ的值時，重要度BAY，I，CS，CF分別導(dǎo)出了相同的排序，而重要度RRW和RAW則分別導(dǎo)出了另外一種相同的排序。注意表1，當(dāng)λ=1時，前四種重要度導(dǎo)出了最重要的10條邊均為6，1，5，22，23，24，12，11，7，13；而后兩種重要度均導(dǎo)出了最重要的10條邊為27，20，5，10，2，4，11，6，30，23。

注意在表1中，當(dāng)λ取較小值時(λ=1)，對于前4種重要度而言，基于同一重要度，不同網(wǎng)絡(luò)邊的重要度值的差異非常顯著。例如，基于貝葉斯重要度BAY，排名第1的邊6和排名第10的邊13的重要度值分別為0.51518和0.05508 ，這一重要度值的差異非常顯著的事實，使得很容易區(qū)別哪一條邊更重要。

但在表1中，對于后兩種重要度而言，給定某一重要度時，不同邊的重要度的值非常接近。例如，基于可靠性減少值RRW，排名第1的邊27與排名第10的邊23的重要度的值分別為0.36969和0.36880，這兩個值非常接近，再考慮到MC方法數(shù)值誤差的影響，以致發(fā)現(xiàn)基于可靠性減少值RRW，難以區(qū)別哪一條邊更重要。

與上述結(jié)果相反，當(dāng)λ取較大值時(λ=40), 觀察表3可知，就前4種重要度而言，基于同一重要度，不同邊的重要度值比較接近。尤其基于貝葉斯重要度BAY，排名第1的邊23和排名第10的邊11，其數(shù)值非常接近，分別為0.99603和0.99597，以致于很難區(qū)分哪一條邊更重要。

但在表3中，對于后兩種重要度而言，不同網(wǎng)絡(luò)邊的同一重要度的值的差異非常明顯，如基于可靠性減少值RRW，排名第1的邊23和排名第10的邊22，其值差異明顯，分別為6.32280和1.22449，據(jù)此，很容易區(qū)分哪一條更重要。

當(dāng)λ取中間值時(λ=15)，由表2可知，除排名第4到排名第7的邊之間排序稍有差異外，根據(jù)這6種重要度，均導(dǎo)出了相同的排序，但要注意各個重要度的物理意義不同。例如，盡管貝葉斯重要度BAY和可靠性完成值RAW均識別出邊10為第8條重要的邊，但葉斯重要度BAY告訴我們：當(dāng)該十二面體網(wǎng)絡(luò)發(fā)生失效時，邊10失效的概率為0.56651；而可靠性完成值RAW則告訴我們：當(dāng)我們確定邊10處于運行狀態(tài)時，則得到十二面體網(wǎng)絡(luò)可靠性為原十二面體網(wǎng)絡(luò)可靠性的1.22279倍。

表1 參數(shù)λ=1的各個重要度值及排序

表2 參數(shù)λ=15的各個重要度值及排序

表3 參數(shù)λ=40的各個重要度值及排序

4 結(jié)論

本文在給定K-終端網(wǎng)絡(luò)發(fā)生失效的邊數(shù)的概率分布的背景下，構(gòu)建了K-終端網(wǎng)絡(luò)可靠性模型，導(dǎo)出了K-終端網(wǎng)絡(luò)邊的貝葉斯重要度、Birnbaum 重要度、臨界失效重要度、臨界可靠性重要度、可靠性完成值、可靠性減少值等重要度的數(shù)學(xué)方程。本文研究結(jié)果突破了以往K-終端網(wǎng)絡(luò)可靠性和重要度計算方法均依賴于邊的可靠性且需邊失效相互獨立的條件的限制，其豐富了網(wǎng)絡(luò)可靠性和重要度的理論體系，并為網(wǎng)絡(luò)可靠性優(yōu)化和維修決策奠定了基礎(chǔ)。以后的研究將繼續(xù)著眼于在給定網(wǎng)絡(luò)發(fā)生失效的邊數(shù)的概率分布的背景下，探討兩條邊的聯(lián)合重要度的計算問題，闡釋概率分布中的參數(shù)對聯(lián)合重要度的影響機理，為網(wǎng)絡(luò)薄弱環(huán)節(jié)的精確識別提供新的思路。