大規(guī)模多階段任務(wù)系統(tǒng)馬爾可夫可靠性模型的存儲(chǔ)和計(jì)算

閆華，高黎，王魁，漆磊

（后勤工程學(xué)院后勤信息與軍事物流工程系，重慶401311）

大規(guī)模多階段任務(wù)系統(tǒng)馬爾可夫可靠性模型的存儲(chǔ)和計(jì)算

閆華，高黎，王魁，漆磊

（后勤工程學(xué)院后勤信息與軍事物流工程系，重慶401311）

由于馬爾可夫模型在進(jìn)行多階段任務(wù)系統(tǒng)的可靠性分析時(shí)，系統(tǒng)狀態(tài)隨部件增加呈指數(shù)增長(zhǎng)，從而導(dǎo)致大規(guī)模條件下模型求解所需的存儲(chǔ)量和計(jì)算量十分巨大。而根據(jù)馬爾可夫模型中轉(zhuǎn)移速率矩陣Q的取值規(guī)律和稀疏特性，給出了矩陣Q中元素qij基于狀態(tài)二進(jìn)制表示的計(jì)算公式，并提出了一種Q矩陣壓縮存儲(chǔ)（QMCS）方法。在模型壓縮存儲(chǔ)的基礎(chǔ)上，進(jìn)一步提出了基于Krylov子空間的可靠性求解算法。通過(guò)算例對(duì)比了不同壓縮存儲(chǔ)方案和不同求解算法的存儲(chǔ)量、計(jì)算時(shí)間和可靠性結(jié)果，分析表明基于QMCS和Krylov子空間的模型求解方法具有較高的存儲(chǔ)和計(jì)算效率，特別是在矩陣規(guī)模較大的情況下，該方法的計(jì)算耗時(shí)優(yōu)于其他方法，且結(jié)果精度也能滿(mǎn)足可靠性計(jì)算需求。

系統(tǒng)評(píng)估與可行性分析；可靠性評(píng)估；多階段任務(wù)系統(tǒng)；壓縮存儲(chǔ)；Krylov子空間

0　引言

基于馬爾可夫模型進(jìn)行多階段任務(wù)系統(tǒng)（PMS）的可靠性分析時(shí)，主要涉及到t時(shí)刻系統(tǒng)處于各狀態(tài)的概率向量［1］，狀態(tài)概率向量的求解需要對(duì)轉(zhuǎn)移速率矩陣（或稱(chēng)無(wú)窮小生成子）Q進(jìn)行運(yùn)算。由于馬爾可夫模型中的狀態(tài)空間呈指數(shù)增長(zhǎng)，當(dāng)系統(tǒng)中單元數(shù)目較多時(shí)，Q矩陣的維數(shù)將非常大，導(dǎo)致存儲(chǔ)量和計(jì)算量都十分巨大［2-3］。針對(duì)大規(guī)模馬爾可夫可靠性模型的求解，可從模型預(yù)處理和模型求解算法兩方面進(jìn)行研究，提高模型的存儲(chǔ)和運(yùn)算效率。

馬爾可夫可靠性模型的轉(zhuǎn)移速率矩陣Q中包含大量零元素，是稀疏矩陣。因此，可利用稀疏矩陣壓縮存儲(chǔ)方法對(duì)矩陣Q進(jìn)行預(yù)處理。稀疏矩陣壓縮儲(chǔ)存大致可分為兩類(lèi):通用存儲(chǔ)方案和特殊矩陣存儲(chǔ)方案［4］。通用存儲(chǔ)方案對(duì)矩陣中非零元素分布不作任何假設(shè)，如行壓縮存儲(chǔ)（CRS）［5］；特殊矩陣存儲(chǔ)方案針對(duì)某些具有特殊結(jié)構(gòu)的矩陣，如帶狀矩陣存儲(chǔ)方法［6］。根據(jù)存儲(chǔ)的基本單元，又可分為基于元素的存儲(chǔ)方案和基于塊的存儲(chǔ)方案。CRS即為基于元素的存儲(chǔ)方案；基于塊的存儲(chǔ)方案包括固定塊存儲(chǔ)（FBS）和按行壓縮分塊存儲(chǔ)（BCRS）［7］等。上述方法各有優(yōu)劣，CRS通用性較強(qiáng)，F(xiàn)BS適合于矩陣中非零塊長(zhǎng)度相同的情形，BCRS適合于矩陣中存在很多非零塊且塊大小各不相同。同時(shí)，文獻(xiàn)［8-9］基于CRS、FBS和BCRS等通用壓縮存儲(chǔ)方案，對(duì)不同壓縮方案下的PMS任務(wù)可靠性分析方法進(jìn)行了研究，但并沒(méi)有提出一種針對(duì)馬爾可夫模型特點(diǎn)的高效壓縮方法；文獻(xiàn)［10］提出了一種基于相似狀態(tài)的轉(zhuǎn)移概率矩陣壓縮方法，但該方法的前提是已知模型的轉(zhuǎn)移概率矩陣，因此并不適用于基于馬爾可夫過(guò)程的任務(wù)可靠性計(jì)算。

馬爾可夫模型的常用計(jì)算方法包括一致化方法［11］、常微分方程方法［12］和迭代計(jì)算方法［13］等。上述算法通常只適合于小規(guī)模矩陣計(jì)算，對(duì)于大規(guī)模問(wèn)題計(jì)算效率較低。Lu等［14］提出了一種基于任務(wù)成功路徑的馬爾可夫可靠性模型求解方法，該方法能夠有效降低模型的計(jì)算復(fù)雜度，但主要問(wèn)題是計(jì)算精度較低，且任務(wù)成功路徑數(shù)隨階段數(shù)增加而迅速增大。Krylov子空間方法是一種空間投影技術(shù)，通過(guò)將大規(guī)模問(wèn)題投影至小規(guī)模子空間，得到問(wèn)題的近似解。因此，在模型壓縮存儲(chǔ)的基礎(chǔ)上，可利用Krylov子空間技術(shù)推導(dǎo)轉(zhuǎn)移速率矩陣的近似求解算法，提高馬爾可夫模型的求解效率。

本文給出了轉(zhuǎn)移速率矩陣Q在系統(tǒng)狀態(tài)二進(jìn)制表示方法下的計(jì)算公式，總結(jié)了矩陣Q中元素的取值規(guī)律；提出了Q矩陣壓縮存儲(chǔ)（QMCS）方法；并在QMCS基礎(chǔ)上，提出了壓縮存儲(chǔ)和Krylov子空間相結(jié)合的PMS可靠性分析方法。通過(guò)算例對(duì)QMCS的壓縮存儲(chǔ)效率和Krylov子空間方法的計(jì)算效率進(jìn)行了對(duì)比分析，結(jié)果證明本文所提方法能夠有效提高模型的存儲(chǔ)和計(jì)算效率。

1　轉(zhuǎn)移速率矩陣的壓縮存儲(chǔ)方法

1.1基于狀態(tài)二進(jìn)制表示的Q矩陣計(jì)算

以Si表示系統(tǒng)的第i個(gè)狀態(tài)，則Si可以由一個(gè)二進(jìn)制字符串c1c2…cn表示。其中，ck為系統(tǒng)中第k個(gè)單元的狀態(tài)，正常為1，失效為0.為便于描述馬爾可夫模型中轉(zhuǎn)移速率矩陣Q的取值規(guī)律，定義狀態(tài)相交權(quán)重的概念。

令Si和Sj為任意的兩個(gè)狀態(tài)（i≠j），狀態(tài)字符串的長(zhǎng)度等于系統(tǒng)中單元數(shù)，記為n.令cik、cjk分別表示狀態(tài)Si和Sj中第k位（0＜k≤n）元素，若存在cik=cjk，則稱(chēng)狀態(tài)Si和Sj相交。定義相交元素的個(gè)數(shù)之和為狀態(tài)相交權(quán)重，記為wij.例如，假設(shè)S3= 10011，S5=00111，則兩狀態(tài)中具有相同元素的位數(shù)分別為第2、4和5位，因此，狀態(tài)相交權(quán)重w35=3.

根據(jù)系統(tǒng)狀態(tài)的二進(jìn)制表示和狀態(tài)相交權(quán)重，推導(dǎo)了轉(zhuǎn)移速率矩陣Q的計(jì)算方法。矩陣Q中元素qij表示當(dāng)系統(tǒng)處于狀態(tài)Si，轉(zhuǎn)移至狀態(tài)Sj的速率，其一般表示方法為qij=viPij［15］.其中，vi為系統(tǒng)在狀態(tài)Si處的轉(zhuǎn)移速率，Pij為系統(tǒng)由狀態(tài)Si轉(zhuǎn)移至Sj的概率。

通常假設(shè)在極短的時(shí)間Δt內(nèi)，系統(tǒng)只能發(fā)生一次故障或修復(fù)，因此，對(duì)于狀態(tài)Si和Sj，只有當(dāng)wij=n-1時(shí)系統(tǒng)才有可能發(fā)生轉(zhuǎn)移。假設(shè)從Si到Sj，發(fā)生故障或修復(fù)的為第k個(gè)單元，對(duì)應(yīng)其在初始狀態(tài)Si中的單元狀態(tài)為cik.并假設(shè)各單元的失效與修復(fù)時(shí)間均服從指數(shù)分布，分別以λk和μk表示單元的失效率與修復(fù)率，則有

（1）式表示在狀態(tài)Si處，可能發(fā)生的轉(zhuǎn)移有n種，因此，所有單元的的轉(zhuǎn)移速率之和就是系統(tǒng)在狀態(tài)Si處的轉(zhuǎn)移速率vi；（2）式表示第k個(gè)單元發(fā)生轉(zhuǎn)移的速率與總的轉(zhuǎn)移速率之比，即為系統(tǒng)由Si轉(zhuǎn)移至Sj的概率。

綜合（1）式、（2）式，可得到如下qij的計(jì)算公式:

式中:wij=n，表示qij為矩陣Q中的對(duì)角線(xiàn)元素，根據(jù)Q中對(duì)角線(xiàn)元素等于該行所有非零元素之和的相反數(shù)，可得qii=-∑jqij（j≠i）.

根據(jù)轉(zhuǎn)移速率矩陣Q的計(jì)算公式，總結(jié)qij取值規(guī)律如下:1）吸收態(tài)對(duì)應(yīng)行中的元素全為0，吸收態(tài)即為表示系統(tǒng)任務(wù)失敗的狀態(tài)；2）若兩狀態(tài)相交權(quán)重wij=n或wij=n-1，則對(duì)應(yīng)qij為非零元素，否則對(duì)應(yīng)qij為零元素。

1.2Q矩陣壓縮存儲(chǔ)方案

根據(jù)轉(zhuǎn)移速率矩陣中元素qij的取值規(guī)律及其計(jì)算公式，提出一種QMCS方法。Q矩陣每行與每列均對(duì)應(yīng)一個(gè)狀態(tài)，將狀態(tài)按照其二進(jìn)制字符串對(duì)應(yīng)的十進(jìn)制值從小到大依此排列，狀態(tài)對(duì)應(yīng)的十進(jìn)制值即代表了矩陣元素的行索引和列索引。以4個(gè)狀態(tài)的系統(tǒng)為例，假設(shè)狀態(tài)00為吸收態(tài)。矩陣Q及其對(duì)應(yīng)的行狀態(tài)和列狀態(tài)如下:

由狀態(tài)的二進(jìn)制表示可以推出其行索引，因此，采用3個(gè)數(shù)組存儲(chǔ)非零元素:1）數(shù)組RStates存儲(chǔ)系統(tǒng)中的所有正常狀態(tài)的二進(jìn)制字符串，并按照狀態(tài)的十進(jìn)制值從小到大依此存儲(chǔ)，狀態(tài)的十進(jìn)制值代表了該狀態(tài)所對(duì)應(yīng)的行索引，數(shù)組SysStates的數(shù)據(jù)類(lèi)型為字符型；2）數(shù)組UnitMTBF存儲(chǔ)系統(tǒng)中n個(gè)單元的失效率，數(shù)據(jù)類(lèi)型為浮點(diǎn)型；3）數(shù)組UnitMTTR存儲(chǔ)系統(tǒng)n個(gè)單元的修復(fù)率，數(shù)據(jù)類(lèi)型為浮點(diǎn)型。當(dāng)qij非零時(shí)，可通過(guò)比較行狀態(tài)和列狀態(tài)，根據(jù)（3）式計(jì)算得到qij，所需數(shù)據(jù)從數(shù)組UnitMTBF和UnitMTTR中獲取。以（4）式中的矩陣Q為例，QMCS下的數(shù)據(jù)結(jié)構(gòu)如表1所示。

表1　Q矩陣壓縮存儲(chǔ)方案下的數(shù)據(jù)結(jié)構(gòu)示例Tab.1 Data structure of Q matrix in compressed storage scheme

以行狀態(tài)01為例，該狀態(tài)對(duì)應(yīng)行索引為1，根據(jù)qij取值規(guī)律，該行中非零元素對(duì)應(yīng)的列狀態(tài)應(yīng)分別為00和11，對(duì)應(yīng)矩陣元素為q10和q13，再加對(duì)角線(xiàn)上的非零元素，則該行中的所有非零元素為q10、q11和q13，且根據(jù)（3）式可得q10=λ2，q13=μ1，q11= -（μ1+λ2）.

為了便于對(duì)各方法的存儲(chǔ)量進(jìn)行分析，定義以下記號(hào):因矩陣Q為方陣，記N為Q的維數(shù)；n為系統(tǒng)中的單元數(shù)，由此可知N=2n；nnz為Q中非零元素的數(shù)目，r為系統(tǒng)中正常狀態(tài)的數(shù)量。稀疏矩陣存儲(chǔ)時(shí)，非零元素的值采用浮點(diǎn)型數(shù)據(jù)存儲(chǔ)，其他的輔助數(shù)組采用整型存儲(chǔ)。并假設(shè)浮點(diǎn)型數(shù)據(jù)需要8個(gè)字節(jié)，整型數(shù)據(jù)需要4個(gè)字節(jié)，字符型數(shù)據(jù)需要8個(gè)字節(jié)。若令M1表示QMCS方案下所需的存儲(chǔ)量，則有

由此可見(jiàn)，在QMCS方案下，所需的存儲(chǔ)量?jī)H與正常狀態(tài)的數(shù)量和單元數(shù)量有關(guān)，具體的qij值可以在使用過(guò)程中，由（3）式進(jìn)行動(dòng)態(tài)計(jì)算。與其他存儲(chǔ)方案相比，由于不需要直接存儲(chǔ)非零元素值，因此，該方案能夠有效地節(jié)省存儲(chǔ)空間。

2　壓縮存儲(chǔ)模型的K rylov子空間求解方法

PMS可靠性模型的求解可以歸結(jié)為對(duì)模型中狀態(tài)概率向量d（t）的計(jì)算。對(duì)于馬爾可夫模型，根據(jù)Chapman-Kolmogorov后向方程得到d P（t）/d t= QP（t），可推得P（t）=eQt，其中P（t）為t時(shí)刻的轉(zhuǎn)移概率矩陣。若令d（0）表示系統(tǒng)初始時(shí)刻的狀態(tài)概率向量，根據(jù)d（0）P（t）=d（t）可得

式中:當(dāng)矩陣Q較大時(shí)，其計(jì)算將十分困難。

Krylov子空間是指由形如p（A）d的向量張成的子空間［16］，A為矩陣，p（A）為由矩陣A構(gòu)成的多項(xiàng)式，則子空間Km（A，d）可表示為

對(duì)于（6）式，若令A(yù)=QT，u（t）=dT（t），z=

u（t）的任意m-1階多項(xiàng)式展開(kāi)都是Krylov子空間Km（A，z）中的元素，因此，基于Krylov子空間投影，可得到如下的近似計(jì)算公式［17］:

式中:p=‖z‖2；Bm=［b1，b2，…，bm］為子空間Km（A，p）中的一組標(biāo)準(zhǔn)正交基，由Arnoldi過(guò)程構(gòu)造［16］；Hm為m×m階的上Hessenberg矩陣，也由Arnoldi過(guò)程得到；e1=（0，…，0，1）T.

由（9）式可以看出，其中基本運(yùn)算為矩陣與向量的乘積運(yùn)算。因此，根據(jù)上節(jié)QMCS方案，給出在該方案下的矩陣向量乘積運(yùn)算的算法如下所示。

算法 QMCS下矩陣與向量乘積運(yùn)算

Step1:For k←0 to r-1 Do

Step2: Si=SysStates［k］；

Step3: 計(jì)算行狀態(tài)Si對(duì)應(yīng)的十進(jìn)制索引值RIndex，并令i=RIndex；

Step4: For l←0 to n-1 Do

Step5: 根據(jù)wij=n-1的原則構(gòu)造列狀態(tài)Sj；

Step6: 計(jì)算列狀態(tài)Si對(duì)應(yīng)的十進(jìn)制索引值CIndex，并令j=CIndex；

Step7: If cl=0

Step8: qij=μl=UnitMTTR［l］；

Step9: Else

Step10: qij=λl=UnitMTBF［l］；

Step11: End If

Step12: y［i］+=qijx［j］；

Step13: qii+=-qij；

Step14: End For

Step15: y［i］+=qiix［i］；

Step16:End For

其中，Si為Q矩陣中第i行對(duì)應(yīng)的狀態(tài)，Sj為第j列對(duì)應(yīng)的狀態(tài)。對(duì)于正常狀態(tài)Si，只有Si與Sj的相交權(quán)重wij=n或wij=n-1時(shí)，對(duì)應(yīng)qij為非零元素。wij=n時(shí)，即有Si=Sj，對(duì)應(yīng)qij是矩陣Q中對(duì)角線(xiàn)上的元素；wij=n-1即與行狀態(tài)Si相比只有一位發(fā)生變化的狀態(tài)。

QMCS實(shí)現(xiàn)了對(duì)模型中轉(zhuǎn)移速率矩陣的高效壓縮存儲(chǔ)，同時(shí)，上述算法實(shí)現(xiàn)了QMCS下的矩陣向量計(jì)算，為利用（9）式進(jìn)行投影后的模型近似求解提供了運(yùn)算基礎(chǔ)。

3　算例分析

CRS是最為通用的方法［18］，對(duì)矩陣中非零元素的分布不作任何假設(shè)；Haque［7］通過(guò)實(shí)驗(yàn)得出結(jié)論:在各種稀疏矩陣存儲(chǔ)方案中，F(xiàn)BS的性能最優(yōu)。FBS通常可記為FBS l，其中l(wèi)為規(guī)定的非零塊長(zhǎng)度，l的長(zhǎng)度取決于具體的計(jì)算平臺(tái)，常用的有FBS2和FBS3.因此，算例分析部分采用CRS方案、FBS2方案和FBS3方案與QMCS方案進(jìn)行對(duì)比。

令M2、M3分別表示CRS方案和FBS l方案下的存儲(chǔ)量，βl表示矩陣Q中長(zhǎng)度為l的非零塊的個(gè)數(shù)，則有［7］

采用文獻(xiàn)［9］中算例對(duì)QMCS壓縮存儲(chǔ)與該存儲(chǔ)方案下的Krylov子空間求解方法進(jìn)行分析。記該多階段任務(wù)為T(mén)，包括兩個(gè)任務(wù)階段P1和P2，且各階段任務(wù)持續(xù)時(shí)間均為10min.假設(shè)系統(tǒng)中各單元的平均修復(fù)時(shí)間和平均故障間隔時(shí)間均為30min和30 000min.任務(wù)T各階段的系統(tǒng)故障樹(shù)分別如圖1和圖2所示，其中A1、A2，…，A13為系統(tǒng)部件。

圖1　任務(wù)T中階段P1的系統(tǒng)故障樹(shù)Fig.1 System fault tree of Phase P1in Task T

根據(jù)文獻(xiàn)［9］中的實(shí)驗(yàn)結(jié)果，相比Runge-Kutta方法和前向Euler方法，一致化方法（UM）具有較高的計(jì)算效率。因此，為了驗(yàn)證Krylov子空間算法的有效性，采用UM算法與Krylov子空間算法進(jìn)行對(duì)比。

任務(wù)T中兩個(gè)階段參與任務(wù)的單元數(shù)分別為7和13，階段矩陣Q1和Q2的規(guī)模分別為128×128和8 192×8 192，非零元素分別為208和37 128，兩個(gè)階段系統(tǒng)中的正常狀態(tài)數(shù)分別為26和2 652.矩陣Q1和Q2中長(zhǎng)度為2的非零塊數(shù)目為26和2 652；長(zhǎng)度為3的非零塊數(shù)目為17和1 478.可得矩陣Q1和Q2在CRS方案、FBS2方案、FBS3方案和QMCS方案下的存儲(chǔ)量如表2所示。

圖2　任務(wù)T中階段P2的系統(tǒng)故障樹(shù)Fig.2 System fault tree of Phase P2in Task T

表2　Q1和Q2在不同存儲(chǔ)方式下所需的存儲(chǔ)量比較Tab.2 Storage space of Q1and Q2

Krylov子空間算法和UM算法在CRS方案、FBS2方案、FBS3方案和QMCS方案存儲(chǔ)方式下各階段的可靠性計(jì)算時(shí)間如表3所示，兩種算法的可靠性計(jì)算結(jié)果如表4所示。由于采用矩陣壓縮存儲(chǔ)對(duì)模型進(jìn)行預(yù)處理，因此，表3中的可靠性計(jì)算時(shí)間分別為:t1表示模型預(yù)處理時(shí)間，即對(duì)矩陣的壓縮處理；t2為求解算法運(yùn)行時(shí)間，不包括模型預(yù)處理時(shí)間；t3表示可靠性計(jì)算的整個(gè)耗時(shí)，包括預(yù)處理時(shí)間和算法運(yùn)行時(shí)間，即t3=t1+t2.表3中CRS-Krylov方案表示模型預(yù)處理采用CRS壓縮方案，任務(wù)可靠性求解采用Krylov子空間算法；CRS-UM方案表示模型壓縮采用CRS方法，并利用UM算法求解任務(wù)可靠性。表3中其他符號(hào)具有類(lèi)似的含義。

表3　不同存儲(chǔ)方式下利用Krylov子空間算法和UM算法的可靠性計(jì)算時(shí)間比較（s）Tab.3 Computation times of Krylov subspace and UM algorithms in different storage modes（s）

表4　基于Krylov子空間算法和UM算法的任務(wù)可靠性計(jì)算結(jié)果Tab.4 Calculated task reliabilities of Krylov subspace and UM algorithms

對(duì)比表2～表4中存儲(chǔ)量、計(jì)算時(shí)間和任務(wù)可靠性等計(jì)算結(jié)果，可以得到如下結(jié)論:

1）CRS、FBS2、FBS3和QMCS 4種存儲(chǔ)方案中，QMCS方案所需存儲(chǔ)量最?。ㄒ?jiàn)表2），有效提高了模型中轉(zhuǎn)移速率矩陣的存儲(chǔ)效率。

2）在QMCS方案下，并未直接存儲(chǔ)轉(zhuǎn)移速率矩陣Q中的非零元素qij，qij是在模型求解過(guò)程中動(dòng)態(tài)生成。因此，若只考慮算法運(yùn)行時(shí)間（即表3中t2），由于QMCS方案下需要額外的qij計(jì)算過(guò)程，不論Krylov算法或是UM算法，QMCS方案下的算法運(yùn)行時(shí)間t2都大于同階段的其他存儲(chǔ)方案（見(jiàn)表3）；但是，CRS方案和FBS l方案下均包含繁瑣的矩陣壓縮處理過(guò)程，該過(guò)程耗時(shí)（表3中t1）相對(duì)算法運(yùn)行時(shí)間，通常不可忽略。因此，若對(duì)比不同存儲(chǔ)方案下可靠性計(jì)算的整個(gè)耗時(shí)（表3中t3），同一任務(wù)階段中QMCS方案的計(jì)算耗時(shí)均要優(yōu)于其他存儲(chǔ)方案，且矩陣規(guī)模越大時(shí)其優(yōu)勢(shì)越明顯（見(jiàn)表3）。綜上所述，相比CRS方案、FBS2方案和FBS3方案，QMCS方案在存儲(chǔ)和計(jì)算耗時(shí)方面均更高效。

3）以任務(wù)階段P2為例，采用Krylov子空間算法求解時(shí)，其運(yùn)行時(shí)間（表3中t2）的最大值和最小值分別為0.671 s和0.024 s；而UM算法運(yùn)行時(shí)間的最大值和最小值分別為2.028 s和0.078 s（見(jiàn)表3）。從中可以看出，相比UM算法，Krylov子空間算法的計(jì)算速度更快。對(duì)比階段P1的相關(guān)數(shù)據(jù)，也可以得到同樣的結(jié)論。

4）對(duì)比Krylov子空間和UM兩種算法的可靠性計(jì)算結(jié)果，任務(wù)階段P1和P2的可靠性結(jié)果誤差分別為7.00×10-11和8.20×10-11.由此可知，Krylov子空間算法也具有較高的計(jì)算精度。

4　結(jié)論

在馬爾可夫模型中，當(dāng)系統(tǒng)單元數(shù)量較多時(shí)，其狀態(tài)空間呈指數(shù)增長(zhǎng)，如單元數(shù)量為20時(shí)，轉(zhuǎn)移速率矩陣Q的維數(shù)就達(dá)到了百萬(wàn)級(jí)。本文針對(duì)大規(guī)模馬爾可夫模型的存儲(chǔ)和計(jì)算問(wèn)題，提出了基于矩陣壓縮存儲(chǔ)技術(shù)的可靠性求解方法。實(shí)例分析表明，相比CRS、FBS2和FBS3 3種壓縮存儲(chǔ)方案，QMCS方案所需的存儲(chǔ)空間最?。煌瑫r(shí)，對(duì)比分析了不同壓縮存儲(chǔ)方案下Krylov子空間算法和UM算法的運(yùn)行耗時(shí)和計(jì)算精度，結(jié)果表明QMCS方案下的Krylov子空間方法具有較高的計(jì)算效率，特別是在矩陣規(guī)模較大的情況下，其計(jì)算耗時(shí)優(yōu)于UM算法。綜上所述，QMCS方案和Krylov子空間技術(shù)相結(jié)合的求解方法較好地解決了大規(guī)模馬爾可夫模型的存儲(chǔ)和計(jì)算問(wèn)題。

（References）

［1］ Alam M，Al-Saggaf U M.Quantitative reliability evaluation of repairable phased-mission systems using Markov approach［J］.IEEE Transactions on Reliability，1986，35（5）:498-503.

［2］ Peng R，Zhai Q，Xing L D.Reliability of demand-based phasedmission systems subject to fault level coverage［J］.Reliability Engineering and System Safety，2014，121（1）:18-25.

［3］ Wu X Y，Wu X Y.Extended object-oriented Petri net model for mission reliability simulation of repairable PMS with common cause failures［J］.Reliability Engineering and System Safety，2015，136（4）:109-119.

［4］ Shahnaz R，Usman A，Chughtai IR.Review of storage techniques for sparse matrices［C］∥2005 Pakistan Section Multitopic Conference.Karachi，Pakistan:IEEE，2005.

［5］ Zhang J，Wan J，Li F.Efficient sparse matrix-vector multiplication using cache oblivious extension quadtree storage format［J］. Future Generation Computer Systems，2016，54（1）:490-500.

［6］ Golub G H，Loan C F V.Matrix computations［M］.4th ed.Baltimore，US:Johns Hopkins University Press，2013.

［7］ Haque SA.Acomputational study of sparse matrix storage schemes［D］.Lethbridge，Canada:University of Lethbridge，2008.

［8］ 黎麗榮.基于Markov模型的大型PMS任務(wù)可靠性分析方法［D］.長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué)，2011. LI Li-rong.Method of mission reliability analysis of large PMS based on Markov model［D］.Changsha:National University of Defense Technology，2011.（in Chinese）

［9］ Wu X Y，Yan H，Li L R.Numerical method for reliability analysis of phased-mission system using Markov chains［J］.Communications in Statistics—Theory and Methods，2012，41（21）: 3960-3973.

［10］ 石磊，姚瑤.馬爾可夫預(yù)測(cè)模型中轉(zhuǎn)移概率矩陣的壓縮與應(yīng)用［J］.計(jì)算機(jī)應(yīng)用，2007，27（11）:2746-2749. SHI Lei，YAO Yao.Compression and application of transiton probability matrix in Markov prediction model［J］.Computer Applications，2007，27（11）:2746-2749.（in Chinese）

［11］ Moorsel A PV，Sanders W H.Transient solution of Markov models by combining adaptive and standard uniformization［J］.IEEE Transactions on Reliability，1997，46（3）:430-440.

［12］ Stewart W J.Introduction of thenumerical solution of Markov chains［M］.Princeton，NJ:Princeton University Press，1994.

［13］ Rauzy A.An experimental study on iterative methods to compute transient solutions of large Markov models［J］.Reliability Engineering and System Safety，2004，86（1）:105-115.

［14］ Lu JM，Wu X Y.Reliability evaluation of generalized phased-mission systems with repairable components［J］.Reliability Engineering and System Safety，2014，121（1）:136-145.

［15］ Ross SM.Introduction to probability models［M］.Burlington，US:Academic Press，2006.

［16］ Saad Y.Iterative methods for sparse linear systems［M］.New York，US:PWS Publishing Company，1996.

［17］ 閆華，武小悅.航天測(cè)控通信系統(tǒng)可靠性分析的改進(jìn)Krylov投影算法［J］.系統(tǒng)工程與電子技術(shù)，2012，34（10）:2180-2186. YAN Hua，WU Xiao-yue.Improved Krylov subspace projection algorithm for reliability analysis of TT＆amp;C and communication system［J］.Systems Engineering and Electronics，2012，34（10）:2180-2186.（in Chinese）

［18］ Simecek I，Langr D，Tvrdik P.Space-efficient sparse matrix storage formats for massively parallel systems［C］∥Proceedings of14th IEEE International Conference on High Performance Computing and Communications.Liverpool:IEEE，2012:54-60.

Storage and Computation of Markov Reliability Model for Large-scale Phased-mission System

YAN Hua，GAO Li，WANG Kui，QI Lei
（Department of Logistics Information＆amp;Logistics Engineering，Logistic Engineering University of PLA，Chongqing 401311，China）

When Markov model is used to analyzed the reliability of phased-mission system，the system state grows exponentially with the increase in the number of components，thus resulting in a huge storage space and calculated amount resolved by the model.According to the element value rules and sparsity of the transition rate matrix Q in Markovmodel，the formula of computing the elements qijis derived based on binary description of states，and a Q-matrix compressed storage scheme（QMCS）is proposed.A reliability computing algorithm using Krylov subspace method is proposed based on the model compressed storage scheme.Taking a practical phased-mission system for example，the required storage spaces，computation times and reliability results of different compressed storage schemes and different algorithms are compared.The analysis results show that the method combining QMCS and Krylov subspace method has higher efficiency in storage and computation.Especially in the case of a large matrix，the QMCS-Krylov method is superior to other methods both in computation time and accuracy.

system assessment and feasibility；reliability evaluation；phase-mission system；compressed storage；Krylov subspace

TP202+.1；N945.17

A

1000-1093（2016）09-1715-06

10.3969/j.issn.1000-1093.2016.09.023

2016-02-02

國(guó)家自然科學(xué)基金項(xiàng)目（71401172）

閆華（1983—），男，講師。E-mail:yanhua_8304@163.com