楊 奧, 崔利榮

(1.中國航空綜合技術(shù)研究所,北京 100028; 2.青島大學(xué) 質(zhì)量與標(biāo)準(zhǔn)化學(xué)院,山東 青島 266071)

0 引言

自20世紀(jì)50年代可靠性科學(xué)誕生起，可靠性理論飛速發(fā)展，對航空、航天、軍事、能源等重大工程的發(fā)展起到了不可替代的作用[1]。同時(shí)，隨著可靠性理論的發(fā)展，可靠性模型分析方法也發(fā)展眾多，但隨著系統(tǒng)可靠性模型越來越復(fù)雜，傳統(tǒng)方法如組合法、全概率公式法、遞推方程法和矩生成函數(shù)法等在系統(tǒng)可靠性評估與分析中往往效率不高[2]，給系統(tǒng)可靠性評估和系統(tǒng)可靠性分析帶來了一定的困難。

在20世紀(jì)90年代Fu和Koutras[3]提出有限馬爾可夫嵌入法一度成為計(jì)算系統(tǒng)可靠性研究熱點(diǎn)。該方法可作為解決系統(tǒng)可靠性評估、部件重要度分析、故障率函數(shù)計(jì)算和新可靠性試驗(yàn)分析的優(yōu)秀工具[4]。如Koutras[5]、趙和崔[6]等人均利用該方法解決了許多與可靠性相關(guān)的問題，尤其對于復(fù)雜冗余系統(tǒng)可靠性求解，有限馬爾可夫嵌入法已取得較為廣泛的應(yīng)用。

另一方面，網(wǎng)絡(luò)系統(tǒng)作為系統(tǒng)可靠性研究領(lǐng)域中的重要分支，一直被各路學(xué)者廣泛關(guān)注。XingLiu-dong曾多次討論多階段系統(tǒng)[9,10]和網(wǎng)絡(luò)系統(tǒng)可靠性[9,10]，馬洪偉[11]研究了隨機(jī)交通網(wǎng)絡(luò)的網(wǎng)絡(luò)漸進(jìn)聯(lián)通可靠性。呂靖[12]則引入不確定變量研究了原油海運(yùn)網(wǎng)絡(luò)連通可靠性?；蛘邔⒕W(wǎng)絡(luò)系統(tǒng)可靠性作為優(yōu)化問題的優(yōu)化要素，如呂彪[13]研究了考慮路網(wǎng)可靠性和空間公平性的次優(yōu)擁擠收費(fèi)模型。樹狀系統(tǒng)作為網(wǎng)絡(luò)系統(tǒng)中的一部分在生活中隨處可見，如運(yùn)輸系統(tǒng)，網(wǎng)絡(luò)信息傳輸，中央倉庫分貨系統(tǒng)等。但現(xiàn)階段關(guān)于網(wǎng)絡(luò)可靠性研究較少，其中日本研究員Aki曾在1999年[14]和2016年[15]分別發(fā)表論文探究用游程及概率母函數(shù)法求解樹狀系統(tǒng)，但該方法要求各網(wǎng)絡(luò)節(jié)點(diǎn)工作概率相同，具有一定實(shí)際應(yīng)用的局限性。因此，結(jié)合現(xiàn)階段在系統(tǒng)可靠性應(yīng)用廣泛的有限馬爾可夫嵌入法，本文提出基于變形有限馬爾可夫嵌入法的n中連續(xù)取k樹狀系統(tǒng)可靠性求解方法。填補(bǔ)這一研究領(lǐng)域空白。

1 樹狀系統(tǒng)建模

現(xiàn)階段關(guān)于樹狀系統(tǒng)可靠性研究通常從確定圖入手，如Aki[14]。但針對確定的樹狀系統(tǒng)可靠性求解難以進(jìn)行算法復(fù)雜度分析，同時(shí)無法對隨機(jī)樹系統(tǒng)進(jìn)行有效的可靠性求解。因此本文給出一種更一般的樹狀圖表示形式。

設(shè)T為一有向樹，V為節(jié)點(diǎn)向量，表示T中全部節(jié)點(diǎn)，樹中節(jié)點(diǎn)按層序遍歷編號，vi表示其中編號為i的節(jié)點(diǎn)。定義樹T包含三類參數(shù)：樹T的層數(shù)l；層-節(jié)點(diǎn)向量A=[a1,a2,…,al]1×l，其中，aj表示第j層節(jié)點(diǎn)總數(shù)，a1通常取1；父-子節(jié)點(diǎn)矩陣Gl×max{A}，其中G(α,β)=k表示第α層第β個(gè)節(jié)點(diǎn)共有k-1個(gè)子節(jié)點(diǎn)，其中，對于矩陣第l行有

圖1 樹T1示意圖

現(xiàn)討論給定樹Tn上任一節(jié)點(diǎn)vt的子節(jié)點(diǎn)搜索模式。

設(shè)ch(vt)={vt1,vt2,…vtz}表示vt的子節(jié)點(diǎn)集合。若G(αt,βt)=1，則vt為葉節(jié)點(diǎn)(子節(jié)點(diǎn)數(shù)為0)；若G(αt,βt)≠1有

(1)

(2)

通過公式(1)與公式(2)可確定任一給定節(jié)點(diǎn)vt的子節(jié)點(diǎn)集合ch(vt)。因此，按本文樹狀圖定義模式可實(shí)現(xiàn)節(jié)點(diǎn)定位及子節(jié)點(diǎn)查找?，F(xiàn)討論遞歸樹形式。

定義1對于確定樹Tn(l,A,G)以其中任意一非葉節(jié)點(diǎn)vt開始及延其傳播方向上全部節(jié)點(diǎn)組成的樹狀結(jié)構(gòu)稱為Tn的子樹，記作subTn(vt)，其中vt為subTn(vt)的根節(jié)點(diǎn)。若vt為葉節(jié)點(diǎn)subTn(vt)為葉節(jié)點(diǎn)本身。

定義2樹Tn(l,A,G)的根節(jié)點(diǎn)為vk，vk的子節(jié)點(diǎn)分別為vk1,vk2,…,vkz。利用1中子樹定義，將樹Tn(l,A,G)表示為:

Tn(vk)={vk|subTn(vk1),subTn(vk2),…,subTn(vkz)}

(3)

因此，利用式(3)對子樹進(jìn)行表示，可得到樹的遞歸形式。

以樹T1為例。用遞歸形式表示樹T1。

T1={v1|subT1(v2),subT1(v3),subT1(v4)}；

subT1(v3)={v3|subT1(v5),subT1(v6)}；

subT1(v5)={v5|subT1(v7),subT1(v8),subT1(v9)}；

subT1(v6)={v6|subT1(v10)}；

subT1(v8)={v8|subT1(v11)}；

subT1(v9)={v9|subT1(v12),subT1(v13)}；

subT1(v10)={v10|subT1(v14),subT1(v15),subT1(v16)}

2 樹狀系統(tǒng)可靠性求解

根據(jù)第1節(jié)定義，若存在一有向樹T，且T上任一節(jié)點(diǎn)vt(1≤t≤sal)處存在唯一二元部件Xt與之對應(yīng)，則稱由全體Xt組成的系統(tǒng)為樹狀系統(tǒng)，記作Tsys(X[1,sal])，其中X[1,sal]為樹狀系統(tǒng)中全部部件組成的集合。

常見的系統(tǒng)失效形式有以下幾種:

1)n中連續(xù)取k失效準(zhǔn)則：當(dāng)系統(tǒng)中存在連續(xù)k個(gè)或k個(gè)以上部件失效時(shí)，系統(tǒng)被視為失效。

2)n中取k失效準(zhǔn)則：當(dāng)系統(tǒng)中存在k個(gè)或k個(gè)以上部件失效時(shí)，系統(tǒng)被視為失效。

3)(n,f,k)失效準(zhǔn)則：當(dāng)且僅當(dāng)在系統(tǒng)中有f或f以上個(gè)單元失效或有連續(xù)k個(gè)或連續(xù)k個(gè)以上部件失效時(shí)，系統(tǒng)被視為失效。

本文主要對第一種失效形式展開討論。其中，對于樹狀系統(tǒng)sal中連續(xù)取k失效準(zhǔn)則要求失效零部件分布滿足有向樹傳播方向。以第1節(jié)樹T1為例，給出一種T1-sys(X[1,16])連續(xù)取k(k=3)連續(xù)失效示意圖，如圖2所示。其中，“●”表示部件失效。

圖2 一種T1-sys(X[1,16])失效模式

現(xiàn)討論在給定失效準(zhǔn)則下樹狀系統(tǒng)sal中連續(xù)取k可靠性計(jì)算公式。

考慮sal個(gè)單元1,2,…,sal組成的一個(gè)樹狀可靠性系統(tǒng)。假設(shè)每個(gè)單元假設(shè)每個(gè)單元有兩種狀態(tài)：工作狀態(tài)和失效狀態(tài)。系統(tǒng)的狀態(tài)完全取決于它的單元的狀態(tài)，因此系統(tǒng)共由2sal種可能的狀態(tài)。根據(jù)可靠性系統(tǒng)的特點(diǎn)，定義一個(gè)齊次馬爾可夫鏈{X(t),t=0,1,…}，再將系統(tǒng)可靠性問題轉(zhuǎn)化為馬爾可夫鏈的問題，依據(jù)馬爾可夫鏈的已知結(jié)果，給出可靠性問題的結(jié)果。其中對于線性系統(tǒng)，已有學(xué)者利用馬爾可夫嵌入法給出可靠性計(jì)算方法。

對于一個(gè)由n個(gè)單元組成的線性系統(tǒng)X，給定參數(shù)k及各單元在馬爾可夫鏈上的一步轉(zhuǎn)移概率pij(t)=P{X(t)=j|X(t-1)=i}(1≤i≤n)，構(gòu)造相應(yīng)的轉(zhuǎn)移概率矩陣Λ(t)=(pij(t))(k+1)×(k+1)，其中p(k+1)j=0,(j≠k+1),p(k+1)(k+1)=1。因此，得到嵌入馬爾可夫鏈的可靠性系統(tǒng)的一般公式[2]為

(4)

其中，π=(π0,π1,…,πk)1×(k+1)表示該馬爾科夫鏈的初始概率，向量U的作用是將系統(tǒng)處于工作狀態(tài)的概率進(jìn)行求和，從而得到系統(tǒng)可靠度。通常對于一個(gè)新系統(tǒng)，π=(1,0,…,0)；U=(1,1,…,1,0)1×(k+1)。

將(4)式第一項(xiàng)展開，

(5)

設(shè)Am=[0,0,…,1,0,…,0]1×(k+1)，其中第m項(xiàng)為1(1≤m≤k+1，余下同)，Am表示系統(tǒng)初始狀態(tài)向量。

(5)式可改寫為

(6)

因此，(6)式可改寫為

Rsys(X,k)=R1(X[1,n],k)

=[p1,q1][R1(X[2,n],k),R2(X[2,n],k)]T

(7)

式(7)表明系統(tǒng)X[1,n]可靠度可拆解為X1部件狀態(tài)向量與X[2,n]系統(tǒng)與對應(yīng)的狀態(tài)可靠度的內(nèi)積。將(7)式推廣到一般，對n中連續(xù)取k失效準(zhǔn)則，若給定線性系統(tǒng)X[i,j]初始狀態(tài)為m及參數(shù)k有系統(tǒng)可靠度為

Rm(X[i,j],k)

=[pk,qk][R1(X[i+1,j],k),Rm+1(X[i+1,j],k)]T

(8)

式(8)稱作線性系統(tǒng)可靠性迭代公式。將其推廣到樹狀系統(tǒng)。對于樹狀系統(tǒng)，在父節(jié)點(diǎn)狀態(tài)確定的條件下，子節(jié)點(diǎn)狀態(tài)相互獨(dú)立，即子樹系統(tǒng)狀態(tài)相互獨(dú)立。因此，樹狀系統(tǒng)可靠度可表示為根節(jié)點(diǎn)部件的狀態(tài)向量與余下子樹系統(tǒng)可靠性的積。

設(shè)存在一樹狀系統(tǒng)Tsys(X[i,j])，其中，Xi為樹的根節(jié)點(diǎn)處部件。Rm(Tsys(X[i,j]),k)表示樹狀系統(tǒng)Tsys(X[i,j])在給定參數(shù)k及初始狀態(tài)為m的可靠度，有

Rm(Tsys(X[i,j]),k)

(9)

其中，Rm(subT(Xr),k)，表示以vr為根節(jié)點(diǎn)所構(gòu)成的子樹系統(tǒng)，且當(dāng)前狀態(tài)m時(shí)的系統(tǒng)可靠度。當(dāng)樹狀系統(tǒng)為線性系統(tǒng)時(shí)式(4)依然成立。特別地，當(dāng)子樹系統(tǒng)為葉結(jié)點(diǎn)時(shí)，即subT(Xlf)=Xlf，有

(10)

其中，對于任意系統(tǒng)X，當(dāng)m=k+1時(shí)

Rm(X,k)=0

(11)

對于系統(tǒng)X層數(shù)lX，當(dāng)lX滿足lX+m≤k時(shí)

Rm(X,k)=1

(12)

綜上，利用樹狀系統(tǒng)迭代公式(9)與式(4)、式(10)、式(11)與式(12)可對任意樹狀系統(tǒng)連續(xù)取k模型進(jìn)行可靠性計(jì)算。下文給出數(shù)值算例。

3 數(shù)值算例

本章通過幾類典型例子對算法應(yīng)用加以說明。

3.1 完全樹系統(tǒng)

完全樹系統(tǒng)是部件排布滿足完全樹形式的可靠性系統(tǒng)。現(xiàn)給出一完全二叉樹系統(tǒng)T2(l,A,G)，其中l(wèi)=5，A=[1,2,4,8,16]

有樹T2如圖3所示。

圖3 完全樹系統(tǒng)T2示意圖

其中，對于部件Xi(1≤i≤31)，有工作狀態(tài)概率為pi=1-0.01i，給定初始狀態(tài)m=1，k=4，利用第2節(jié)公式可得樹狀系統(tǒng)T2的系統(tǒng)可靠度為

R1(Tsys(X[1,31]),4)

由于subT(X2)與subT(X3)結(jié)構(gòu)完全一致，因此僅對subT(X2)的可靠性展開求解。現(xiàn)直接給出可靠度計(jì)算結(jié)果，其中，第四層全部節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹系統(tǒng)可靠度如表1所示。

表1 第四層全部節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹系統(tǒng)可靠度

利用表1數(shù)據(jù)計(jì)算以第三層全部節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹系統(tǒng)可靠度，如表2所示。

表2 第三層全部節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹系統(tǒng)可靠度

利用表2數(shù)據(jù)繼續(xù)計(jì)算得到以第二層全部節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹系統(tǒng)可靠度，有

R1(subT(X2),4)=0.999878081637186
R2(subT(X2),4)=0.999672055888000
R1(subT(X3),4)=0.999511580343489
R2(subT(X3),4)=0.999021124753600

因此，樹狀系統(tǒng)T2系統(tǒng)可靠度為

R1(Tsys(X[1,31]),4)

=0.999382759329300

3.2 長鏈條系統(tǒng)

長鏈條系統(tǒng)是指包含多個(gè)子樹為線性系統(tǒng)的樹狀系統(tǒng)，一般常見于管道運(yùn)輸，微波信號傳輸?shù)认到y(tǒng)?，F(xiàn)給出一樹狀系統(tǒng)T3(l,A,G)，其中l(wèi)=8，A=[1,3,3,5,6,6,6,6]

樹T3如圖4所示。

圖4 T3長鏈條系統(tǒng)示意圖

其中，對于部件Xi(1≤i≤36)，有工作狀態(tài)概率為pi=1-0.01i，給定初始狀態(tài)m=1，k=5，有樹狀系統(tǒng)T3的系統(tǒng)可靠度為

R1(Tsys(X[1,36]),5)

其中，對于子樹系統(tǒng)subT(X2)為線性系統(tǒng)，因此可直接利用公式(4)計(jì)算出系統(tǒng)可靠度?，F(xiàn)直接給出可靠度計(jì)算結(jié)果，其中，subT(X14)和subT(X15)系統(tǒng)可靠度如表3所示。

表3 subT(X14)和subT(X15)系統(tǒng)可靠度

迭代計(jì)算得

R1(subT(X3),5)=0.999474172768361,
R2(subT(X3),5)=0.999440090884361

同理可計(jì)算出

R1(subT(X4),5)=0.998471715071798,
R2(subT(X4),5)=0.998353251697900

因此，樹狀系統(tǒng)Tsys(X[1,36])系統(tǒng)可靠度為

R1(Tsys(X[1,36]),5)=0.997773770874255

3.3 一般(隨機(jī))樹系統(tǒng)

一般樹系統(tǒng)又稱隨機(jī)樹系統(tǒng)，即通過生成隨機(jī)樹的方式生成樹狀系統(tǒng)。本文生成一隨機(jī)樹T4(l,A,G)，其中l(wèi)=8，A=[1,3,7,11,9,7,1,1]

有樹T4如圖5所示。

圖5 T4隨機(jī)樹系統(tǒng)示意圖

其中，對于部件Xi(1≤i≤40)，設(shè)工作狀態(tài)概率為pi=1-0.01i。給定初始狀態(tài)m=1，k=3。直接給出樹狀系統(tǒng)T4的系統(tǒng)可靠度為

R1(Tsys(X[1,40]),3)=0.793062318995683

4 討論

4.1 算法復(fù)雜度分析

本章對本文提出的算法運(yùn)算復(fù)雜度進(jìn)行分析，即考慮在給定樹狀系統(tǒng)結(jié)構(gòu)參數(shù)G和失效準(zhǔn)則參數(shù)k下算法需要進(jìn)行的加法運(yùn)算次數(shù)與乘法運(yùn)算次數(shù)。

將公式(9)展開得

Rm(Tsys(X[i,j]),k)

(13)

定義矩陣內(nèi)元素求和函數(shù)sum(·)。其中，sum(N)=n，表示對矩陣N內(nèi)非零元素求和，求和結(jié)果為n。

定義矩陣內(nèi)非零元素個(gè)數(shù)和函數(shù)count(·) 。其中，count(N)=c，表示對矩陣N內(nèi)非零元素個(gè)數(shù)求和，矩陣非零元素個(gè)數(shù)和為c。

由式(13)可知，計(jì)算Rm(Tsys(X[i, j]),k)時(shí)需進(jìn)行2·(iq-i1)次乘法運(yùn)算，1次加法運(yùn)算。當(dāng)給定失效準(zhǔn)則參數(shù)k(k≥1)時(shí)，由式(12)可知，對一般樹狀系統(tǒng)需對式(13)計(jì)算k次(m分別取1,2,…,k)。因此，由G′可知，對于樹狀系統(tǒng)Tsys(X[1,sal])求解可靠度時(shí)需進(jìn)行2k·sum(G′)次乘法，k·count(G′)次加法。即算法乘法復(fù)雜度為O(2k·sum(G′))；加法復(fù)雜度為O(k·count(G′))，分別為子節(jié)點(diǎn)數(shù)量矩陣G′和失效準(zhǔn)則參數(shù)k的線性階。

以圖5中樹T4為例，有

其中，sum(G′)=39;count(G′)=20。因此，對于給定k=3，利用本文算法計(jì)算由T4組成的樹狀結(jié)構(gòu)可靠度需進(jìn)行2×3×39=234次乘法運(yùn)算；3×20=60次加法運(yùn)算。

現(xiàn)討論兩類特殊樹狀系統(tǒng)：線性系統(tǒng)與完全h叉樹系統(tǒng)。

對于線性系統(tǒng)，有sum(G′)=l-1；count(G′)=l-1。因此，對于給定k有線性系統(tǒng)算法乘法復(fù)雜度：O(2k(l-1))；加法復(fù)雜度：O(k(l-1))。

4.2 算法對比

現(xiàn)階段關(guān)于樹狀系統(tǒng)可靠性的研究較為有限，其中日本學(xué)者Aki[14]用條件概率母函數(shù)法成功求解了樹狀系統(tǒng)連續(xù)取k失效準(zhǔn)則和(n,f,k)失效準(zhǔn)則。在此本文針對n中連續(xù)取k失效準(zhǔn)則，對Aki提出的算法與本文算法進(jìn)行對比。

本文引用Aki 1999年論文[14]中所構(gòu)造的樹狀的系統(tǒng)，設(shè)存在一樹狀系統(tǒng)T5(l,A,G)，其中l(wèi)=4,A=[1,3,6,8]

有樹T5如圖6所示。

圖6 樹狀系統(tǒng)T5示意圖

設(shè)給定系統(tǒng)中零件工作概率pi=p(1≤i≤18)，失效準(zhǔn)則參數(shù)k=3。分別采用本文算法和條件概率母函數(shù)法對樹狀系統(tǒng)T5的可靠性進(jìn)行求解，結(jié)果如表4所示。

表4 部件工作概率為p時(shí)兩類算法計(jì)算系統(tǒng)可靠度

由表4可以看出，本文算法與條件概率母函數(shù)法在求解樹狀系統(tǒng)連續(xù)取k可靠度問題上結(jié)果完全一致，從側(cè)面印證了本文算法的正確性?，F(xiàn)在從算法復(fù)雜度和算法適用情況兩個(gè)方面討論此兩種算法的使用效果。

算法復(fù)雜度方面，本文算法運(yùn)算復(fù)雜度在第4.1小結(jié)中已有討論，乘法復(fù)雜度與加法復(fù)雜度分別為樹子節(jié)點(diǎn)數(shù)量矩陣G′和失效準(zhǔn)則參數(shù)k的線性階。對于條件概率母函數(shù)法，在采用本文樹狀系統(tǒng)定義的條件下，其求解樹狀系統(tǒng)n中連續(xù)取k失效概率準(zhǔn)則系統(tǒng)可靠度的運(yùn)算復(fù)雜度與本文算法一致。但應(yīng)用條件概率母函數(shù)法時(shí)，需對失效準(zhǔn)則參數(shù)k進(jìn)行討論(分k=1和k>1兩種情況)，而本文算法則實(shí)現(xiàn)了k取值時(shí)公式的統(tǒng)一，減少了算法空間復(fù)雜度。

算法適用情況方面，條件概率母函數(shù)法需要求根節(jié)點(diǎn)下所有子節(jié)點(diǎn)工作概率相同，否則算法運(yùn)算復(fù)雜度趨近于各單元狀態(tài)窮舉。而本文算法復(fù)雜度是部件工作概率的線性階，即不同部件的概率取值不影響算法運(yùn)算復(fù)雜度。因此，本算法在求解樹狀系統(tǒng)考慮n中連續(xù)取k失效準(zhǔn)則的系統(tǒng)可靠性問題上有更好的適應(yīng)性。

5 結(jié)論

本文運(yùn)用有限馬爾可夫嵌入法研究了樹狀系統(tǒng)考慮n中連續(xù)取k準(zhǔn)則可靠度求解方法，并成功應(yīng)用其進(jìn)行數(shù)值算例求解。同時(shí)與Aki[14]概率母函數(shù)法進(jìn)行對比，本方法在求解效率及應(yīng)用范圍上更為廣泛。

本研究提供了一種樹狀系統(tǒng)考慮n中連續(xù)取k準(zhǔn)則可靠性求解的高效算法，在管道運(yùn)輸、信息傳輸?shù)葘?shí)際領(lǐng)域進(jìn)行系統(tǒng)可靠性分析提供有力支持。未來將繼續(xù)探索在不同準(zhǔn)則下樹狀系統(tǒng)或是復(fù)雜網(wǎng)絡(luò)系統(tǒng)可靠性求解問題。