鄧 川，唐家銀，譚啟濤

（西南交通大學(xué) 數(shù)學(xué)學(xué)院，成都 611756）

0 引言

科技進(jìn)步和交互型模式的發(fā)展使得網(wǎng)絡(luò)系統(tǒng)扮演著越來越重要的角色。供電網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、計算機信息網(wǎng)絡(luò)等網(wǎng)絡(luò)系統(tǒng)的失效會引起很大的社會經(jīng)濟(jì)損失，甚至造成安全事故。所以網(wǎng)絡(luò)系統(tǒng)可靠性的評估是值得關(guān)注的研究領(lǐng)域。網(wǎng)絡(luò)系統(tǒng)可靠性研究方法以概率真值表法、全概率分解法、最小路集法等為代表；且多數(shù)基于最小路集研究網(wǎng)絡(luò)系統(tǒng)可靠性，在組成系統(tǒng)的單元部件獨立性失效條件下，國內(nèi)外學(xué)者已經(jīng)做了大量的研究，這些研究主要集中在求最小路和不交化上，且相關(guān)理論研究[1-9]較為成熟。

鄰接矩陣法求最小路是一種常用的方法[2]，它依靠簡單的矩陣冪運算求得二終端網(wǎng)絡(luò)系統(tǒng)的所有最小路。但是網(wǎng)絡(luò)中弧的數(shù)量較大時，矩陣的冪運算是非常繁瑣的，特別是遇到復(fù)雜的大型網(wǎng)絡(luò)，鄰接矩陣法就不再適合求最小路了。文獻(xiàn)[3]給出了余因子算法(一種基于行列式求最小路的方法)。它在鄰接矩陣的基礎(chǔ)上做了降階，并且將冪運算轉(zhuǎn)變?yōu)樾辛惺竭\算，使得計算簡化。

使用余因子算法[3]和改進(jìn)BDD算法[4]可簡便地得到不交和事件，在各部件獨立失效下，可以通過簡單的計算求系統(tǒng)的可靠性。因為通過余因子算法求出的最小路之間一般是相交的，所以為了方便計算系統(tǒng)可靠度，還需要進(jìn)行不交化。對不交化技術(shù)的大多數(shù)研究都是基于容斥原理。Sing等[5]研究了終端網(wǎng)絡(luò)可靠性問題，肯定了使用二元決策圖來確定終端網(wǎng)絡(luò)可靠性的合理性。Yeh[6]對求不交化的和的技術(shù)進(jìn)行了改進(jìn)，得到了最小的路徑結(jié)構(gòu)(MPS:Minimal Paths Structure)?；谝粋€有序二元決策圖(OBDD:Ordered Binary Decision Diagram)，Kuo等[7]為大型網(wǎng)絡(luò)的可靠性評估建模奠定了基礎(chǔ)。并且在文獻(xiàn)[8]中將二終端的情況推廣到了k終端。史玉芳等[4]改進(jìn)了BDD算法，并給出了編程的步驟與算法案例。

實際工況中，由于相同的工作環(huán)境和外部沖擊，導(dǎo)致系統(tǒng)各組成部件失效之間相互影響。獨立性僅是相關(guān)性的一個特例，忽略相關(guān)性失效可能會對模型的精確性造成影響?？紤]相關(guān)性失效下二終端網(wǎng)絡(luò)系統(tǒng)問題可靠性建模具有一定必要性，Copula相關(guān)性理論是刻畫統(tǒng)計相關(guān)性的重要工具[10-12]。

本文借助余因子算法和BDD算法，引入Copula的相關(guān)性理論和差分運算，對二終端網(wǎng)絡(luò)系統(tǒng)進(jìn)行可靠性評估，使得進(jìn)行網(wǎng)絡(luò)系統(tǒng)可靠性計算時能有效克服維數(shù)災(zāi)難。

1 二終端網(wǎng)絡(luò)系統(tǒng)的最小路

求解二終端網(wǎng)絡(luò)系統(tǒng)問題的可靠度，對于理論研究和工程推廣應(yīng)用都有價值。如何計算系統(tǒng)正常的最小路，是研究系統(tǒng)可靠度的基礎(chǔ)。曹晉華等[2]給出了求最小路的鄰接矩陣法。在網(wǎng)絡(luò)系統(tǒng)中弧的數(shù)量較少時，此方法能方便地給出最小路的集合，它所用到的知識也是較完備的矩陣?yán)碚摚脆徑泳仃嚨膬邕\算。當(dāng)系統(tǒng)弧的數(shù)量較多時，矩陣維數(shù)相應(yīng)增大，矩陣乘法的難度呈指數(shù)化增長。即使使用計算機運算，由于算法的繁瑣，也會影響計算速度。引入一種余因子算法，將計算簡化為矩陣行列式的運算。

網(wǎng)絡(luò)系統(tǒng)G是有n個節(jié)點l條弧的二終端網(wǎng)絡(luò)系統(tǒng)。C是G的鄰接矩陣，I是與C維數(shù)相同的單位矩陣，則G的廣義鄰接矩陣為C+I，（即每個節(jié)點增加一個權(quán)為1的自環(huán)[3]）。

假設(shè)輸入節(jié)點為i，輸出節(jié)點為j。余因子算法步驟如下：

（1）根據(jù)網(wǎng)絡(luò)系統(tǒng)G寫出對應(yīng)的廣義鄰接矩陣C+I；

（2）刪除矩陣C+I的第j行和第i列，得到余因子矩陣Mji；

（3）計算Mji對應(yīng)的行列式值，記為|Mji|；

（4）|Mji|是一些弧序列的和，需要先對這些序列做類似于鄰接矩陣法里的去除冗余項處理，然后取純真值，得到的每一個弧序列就是一條最小路。

如文獻(xiàn)[2]中橋形網(wǎng)絡(luò)的廣義鄰接矩陣與余因子矩陣為：

基于上面的步驟，將最小路記為Ai(i=1，2，…m),令中事件的并記為S，即系統(tǒng)正常這一事件。

余因子算法的合理性、適應(yīng)性(對任何無向、有向和混合網(wǎng)絡(luò)都適合)在文獻(xiàn)[3]中給出了具體的證明。在二終端的網(wǎng)絡(luò)系統(tǒng)問題中，對比鄰接矩陣法求最小路集，余因子法有利于編程實現(xiàn)，并能提高運算效率，具有易操作的特點。

2 基于改進(jìn)的二元決策圖法化S為不交和

從橋形網(wǎng)絡(luò)的案例可以得到Ai(i=1，2，…m)之間并不是互斥事件，根據(jù)網(wǎng)絡(luò)的特點也不難發(fā)現(xiàn)A中事件一般不是互不相容的。為了方便計算系統(tǒng)G的可靠性，需要將事件Ai(i=1，2，…m)進(jìn)行不交化。改進(jìn)的二元決策圖算法[4](后文都簡記為BDD算法)可以方便快捷地得到不交和。

系統(tǒng)可靠度R為：

直接求可靠度R是有困難的，將A中元素不交化有利于簡化計算，下面就將A中事件化為不交和。

記f為系統(tǒng)的布爾函數(shù)，，如橋形網(wǎng)絡(luò)：f=ab+cd+ade+bce，其中f是關(guān)于弧a，b，c，d，e的函數(shù)。對于n個節(jié)點l條弧的二終端網(wǎng)絡(luò)系統(tǒng)，布爾函數(shù)為：f(x1，x2，…，xl)。將布爾函數(shù)進(jìn)行0-1分解有：

其中i∈(1，2，…，l)。

如果E(xi)表示f中包含弧xi的弧序列的集合，令L(xi)為E(xi)中最短弧序列中弧的數(shù)量。如橋形網(wǎng)絡(luò)中，E(a)為{ab，ade}，L(a)=2。由BDD算法[4]，化不交和的算法步驟可以簡記如下：

（1）計算f中每個弧xi的L(xi)，取最小的L(xi)對應(yīng)的xi，對此弧進(jìn)行布爾代數(shù)的0-1分解，并用二叉樹表示。二叉樹的左枝為1，弧xi正常；右枝為0，弧xi失效。如果最小的L(xi)有多個，則在這些相等的里面取在f中出現(xiàn)最多的xi進(jìn)行；其余情況任取。

（2）更新布爾函數(shù)f：當(dāng)xi取1(或0)時，f中對應(yīng)的xi取1（或0）。將f中xi取1的布爾函數(shù)賦給左葉節(jié)點，將f中xi取0的布爾函數(shù)賦給右葉節(jié)點。

（3）重復(fù)步驟（1）、（2），直到所有葉節(jié)點對應(yīng)的布爾函數(shù)出現(xiàn)1這一項或布爾函數(shù)等于0。1表示此葉節(jié)點到根節(jié)點是一條不交化的最小路，0表示此葉節(jié)點到根節(jié)點不是最小路。

經(jīng)過上述不交化處理，可以容易得到不交化的最小路集。將之記為B1，B2，…，Bh，其中h為葉節(jié)點中取1的個數(shù)。網(wǎng)絡(luò)系統(tǒng)G的可靠性可以表示為在不交化的過程中，該算法可以進(jìn)一步簡化為只對那些弧數(shù)量小于n-1的最小路不交化，其他最小路只需要添上未出現(xiàn)弧的失效狀態(tài)。

3 相關(guān)性失效下二終端網(wǎng)絡(luò)系統(tǒng)G的可靠度計算

對B1，B2，…，Bh的研究，國內(nèi)外都是基于弧與弧失效之間相互獨立，將弧序列Bj中的弧xi用Ri替換，xˉi用1-Ri替換，就可以得到網(wǎng)絡(luò)的可靠性。由于受到相同的沖擊以及處在同樣的工作環(huán)境中，使獨立情形下的可靠度計算結(jié)果存在偏差，從而考慮網(wǎng)絡(luò)G的組成弧之間的相關(guān)性是非常有必要的。因此，引入Copula函數(shù)的相關(guān)理論，解決相關(guān)性失效下的二終端網(wǎng)絡(luò)系統(tǒng)系統(tǒng)可靠性的問題。Copula理論預(yù)備知識如下：

定義1[15]：n維Copula是一個函數(shù)C：[0，1]n→[0，1]，而且滿足：

（1）?u∈[0，1]n，C(u)=0，如果u至少存在在一個分量為0；C(u)=uk，如果除uk外，其余分量全為1；

（2）對任一屬于[0，1]n的a，b，使得a≤b(對應(yīng)的坐標(biāo)分量ak≤bk)，有：VC([a，b])≥0。

Sklar定理[15]：令H是n維隨機變量 (X1，X2，…，Xn)的聯(lián)合分布函數(shù)，其邊緣分布分別為F1，F(xiàn)2，…，F(xiàn)n，則存在唯一一個n維Copula函數(shù)Cθ(u1，u2，…，un)，使得對所有Rˉn中定義域上的點(x1，x2，…，xn)有下式成立：

基于不交化的最小路集，得到網(wǎng)絡(luò)G的可靠性為：現(xiàn)在將求二終端網(wǎng)絡(luò)系統(tǒng)G的可靠性分解為求Bi的可靠性P(Bi)。不妨設(shè)弧xi的壽命為Ti，事件Bi中正常弧的數(shù)量有k條，失效有q條，未出現(xiàn)有l(wèi)-k-q條。由概率論的知識有：

其中A表示事件{Ti1≤t}，…，{Tik≤t}的并。將事件記為B。

在不同的事件Bi中，下標(biāo)k和q取不同的值。下標(biāo)i1，…，ik是與事件Bi中正常的k條弧一一對應(yīng)的一個排列。失效時的下標(biāo)類似可得。則由加法公式[16]和式（4）有：

其他階差分算子以此類推。

令H(x)為網(wǎng)絡(luò)G所有l(wèi)條弧的聯(lián)合分布函數(shù)，則由Sklar定理存在一個l維的Copula函數(shù)為C(u1，u2，…，ul)，ui(i=1，…l)為弧xi的分布函數(shù)Fi(xi)，使得：

當(dāng)k=1時容易得到：

當(dāng)k=2時不難得到：

根據(jù)歸納假設(shè)不難證明事件的概率為：

節(jié)點不可靠的時候考慮網(wǎng)絡(luò)的相關(guān)性，只需要將節(jié)點視為弧，并進(jìn)行相同的可靠度建模。此時Copula函數(shù)的維數(shù)會增加n維，但是這并沒有給計算增加多少難度。對于任何一個Bi，只需要在節(jié)點可靠的基礎(chǔ)上，對連接弧的節(jié)點做相應(yīng)的差分運算，其中F(t)是節(jié)點的分布函數(shù)，要取遍所有在Bi中出現(xiàn)的節(jié)點。對沒有出現(xiàn)的節(jié)點和弧做差分運算，實際運算過程中，由Copula函數(shù)的性質(zhì)不難發(fā)現(xiàn)，這些弧與節(jié)點對應(yīng)的變量都取1就可以了，其余差分按定義計算結(jié)果易得。

4 Copula函數(shù)的統(tǒng)計選擇

在變量相關(guān)的情況下求聯(lián)合分布函數(shù)是很困難的，但變量相關(guān)結(jié)構(gòu)Copula擬合的統(tǒng)計捕捉相對較易。由Copula的優(yōu)良性質(zhì)知式（7）是容易計算的。而Copula函數(shù)C(u1，u2，…，ul)的選擇需根據(jù)實際的網(wǎng)絡(luò)系統(tǒng)弧壽命數(shù)據(jù)樣本擬合得到。一般需要擬合出各弧壽命邊緣分布函數(shù)Fi(xi)，根據(jù)(ui，uj)的散點圖可以初步判斷兩變量相關(guān)結(jié)構(gòu)剖面，依據(jù)剖面特征尋找出一族備選Copula。記備選Copula函數(shù)族為C0={C1，C2，…，Cq}。

利用已知的樣本數(shù)據(jù)和極大似然估計，可給出每個備選函數(shù)中參數(shù)向量θ0的估計。對備選函數(shù)可以計算Jeffreys’離散測度[17]，求得最優(yōu)模型。但是該方法對相關(guān)系數(shù)較大的案例并不適合。由文獻(xiàn)[18]知，可以利用Bootstrap技術(shù)對備選函數(shù)抽樣得到“原始數(shù)據(jù)”，然后從中重復(fù)抽取，每次都可以得到一個似然函數(shù)值，最后根據(jù)這些數(shù)據(jù)構(gòu)造擬合優(yōu)度檢驗統(tǒng)計量，尋找最佳的Copula函數(shù)。

常見的Copula函數(shù)族：如表1所示：

表1 幾類典型Copula函數(shù)族

Copula函數(shù)的統(tǒng)計選擇算法如下：

（1）根據(jù)部件間關(guān)系的初步分析，確定一族備選Copula函數(shù){C1，C2，…，Cq}。

（2）對每個備選Copula函數(shù)Cj，j=1，…，q，將樣本數(shù)據(jù)帶入似然函數(shù)，利用極大似然估計求得參數(shù)θ?j。

（3）從備選函數(shù)中選擇兩個進(jìn)行似然比檢驗，根據(jù)統(tǒng)計量的值和顯著性水平排除一個。

（4）從剩下的備選函數(shù)中選一個與上次檢驗剩下的函數(shù)再進(jìn)行似然比檢驗。

（5）重復(fù)步驟（4）直到找到最優(yōu)的Copula函數(shù)。

5 仿真案例

有如圖1所示的星形網(wǎng)絡(luò)系統(tǒng)G，假設(shè)每個節(jié)點是可靠的，每條弧是服從威布爾分布，并有單向弧的失效率函數(shù)是r(t)=9.8×10-5t，雙向弧的失效率是r(t)=(7.7175×10-7t)1/2，其中時間單位是月。如果系統(tǒng)服從θ為1/2的Gumbel Copula?？紤]系統(tǒng)工作到10年后，從節(jié)點1到節(jié)點2，系統(tǒng)正常的可靠度。

圖1星形網(wǎng)絡(luò)

由余因子算法得到鄰接矩陣C和余因子矩陣C′：

去除冗余項之后得到的純真值為：

經(jīng)過步驟二BDD算法，容易得到不交化的弧序列：

上述弧序列已經(jīng)不交，將其簡記為B1，…，B15，通過Copula可以簡單計算出15個弧序列對應(yīng)的可靠度，一個簡單的求和可以得出系統(tǒng)的可靠度。經(jīng)過軟件R編程計算得到獨立時，系統(tǒng)的可靠度為R′=0.7424816，而考慮相關(guān)性失效，系統(tǒng)的可靠度為R=0.6591567。通過R繪圖可以得到圖2、圖3所示的結(jié)果：

圖2系統(tǒng)可靠度函數(shù)曲線

圖3兩種狀態(tài)下的可靠度偏差

由圖2和圖3可以地看出大約在30個月之后，獨立失效和相關(guān)性失效的可靠度曲線之間的偏差越來越大。而且相關(guān)性失效的可靠度比獨立失效要小。出現(xiàn)這種結(jié)果是由于系統(tǒng)結(jié)構(gòu)和部件相關(guān)性所導(dǎo)致的。如計算弧序列的可靠度，獨立失效下的可靠度為(1-R1)R6R7，其中R1表示弧x1在此時此刻的可靠度；而在部件相關(guān)性干涉影響下，由于部件有正相關(guān)性(Gumbel Copula屬于正相關(guān)性)作用，所以弧x6在弧x1失效的狀態(tài)下可靠性是低于獨立時的可靠度。由于這種相關(guān)性干涉的影響，使得不考慮相關(guān)性失效會造成對可靠性的高估，而這在工程里是非常危險的。這些失誤往往是以巨額經(jīng)濟(jì)利益和生命安全為代價。

對于節(jié)點不可靠的情況，可以按照上面提到的方法進(jìn)行推算，其結(jié)果是相似的。

6 結(jié)論

基于余因子算法和改進(jìn)的BDD算法，求得不交的弧序列。借助Copula函數(shù)和差分理論，本文建立了相關(guān)性失效下二終端網(wǎng)絡(luò)系統(tǒng)的可靠度評估模型。對于節(jié)點可靠的情況，已經(jīng)做了詳細(xì)論述，而對于節(jié)點不可靠的情況，本文找出了兩種情況的共性，利用已有研究結(jié)果，給出了節(jié)點不可靠的計算方法。描述了Copula函數(shù)的選擇方法與思想，為模型的建立提供了支持。

根據(jù)建立的可靠度評估模型以及仿真案例分析，得出在正相關(guān)性失效時，獨立性條件下系統(tǒng)可靠度評估值偏大。經(jīng)過對兩種狀態(tài)偏差的仿真算例分析，發(fā)現(xiàn)隨著時間的增大，偏差在尾部趨向于線性增長。進(jìn)一步可以得到在部件呈負(fù)相關(guān)時，忽略相關(guān)性，系統(tǒng)可靠度會偏小。

當(dāng)面對大型復(fù)雜網(wǎng)絡(luò)時，基于Copula函數(shù)考慮網(wǎng)絡(luò)相關(guān)性仍然是有效的，本文給出的二終端網(wǎng)絡(luò)系統(tǒng)可靠性評估模型，可以推廣至k終端情形。但由于備選函數(shù)自身的局限性，使用Copula函數(shù)刻畫部件的相關(guān)性仍然存在一些不足。