基于邊值多值決策圖的多狀態(tài)系統(tǒng)可靠性評(píng)估方法

李煥，徐立立，杜勝杰，張明，明志茂

（廣州廣電計(jì)量檢測(cè)股份有限公司，廣東 廣州 510656）

0 引言

隨著現(xiàn)代社會(huì)對(duì)產(chǎn)品可靠性要求的提高，很多系統(tǒng)通過(guò)增加系統(tǒng)單元備份來(lái)提高可靠性水平，如計(jì)算機(jī)服務(wù)器系統(tǒng)，通信系統(tǒng)，水、氣和電力分配系統(tǒng)。對(duì)于這樣的系統(tǒng)，當(dāng)一個(gè)單元故障發(fā)生時(shí)，系統(tǒng)仍可在可接受的或者降級(jí)的狀態(tài)繼續(xù)工作，體現(xiàn)出多性能狀態(tài)特性。因此如何表征系統(tǒng)的多性能狀態(tài)特性逐漸成為可靠性理論研究的重點(diǎn)，表征多狀態(tài)系統(tǒng)的可靠性模型也層出不窮。

針對(duì)多狀態(tài)系統(tǒng)的可靠性評(píng)估，研究人員已經(jīng)提出了多種多狀態(tài)系統(tǒng)的可靠性建模和評(píng)估方法。其中MDD模型是從傳統(tǒng)的二元決策圖（Binary Decision Diagram，BDD）擴(kuò)展而來(lái)的解決多狀態(tài)系統(tǒng)的有效方法，已經(jīng)得到了廣泛地研究。但是，當(dāng)系統(tǒng)狀態(tài)數(shù)量較多時(shí)，MDD模型的規(guī)模會(huì)急劇增長(zhǎng)。針對(duì)這種情況有學(xué)者提出了EVMDD模型，該模型能夠降低MDD模型的復(fù)雜度[1]。

但是目前的EVMDD模型都是由MDD模型轉(zhuǎn)換而來(lái)，實(shí)際應(yīng)用中仍然需要先構(gòu)建MDD模型，對(duì)于節(jié)點(diǎn)多、狀態(tài)多的系統(tǒng)構(gòu)建MDD模型的過(guò)程將特別復(fù)雜，這也限制了EVMDD在實(shí)際工程中的應(yīng)用。本文研究一種直接構(gòu)造EVMDD的方法，不需要先構(gòu)建MDD模型可以直接生成EVMDD模型，對(duì)具有節(jié)點(diǎn)數(shù)量多、系統(tǒng)狀態(tài)多的復(fù)雜多狀態(tài)系統(tǒng)分析更加高效。

1 概述

最近，人們引入了不同的多狀態(tài)模型來(lái)表示各種多狀態(tài)系統(tǒng)的惡化過(guò)程，如計(jì)算機(jī)服務(wù)器系統(tǒng)、電信系統(tǒng)、水、氣、配電系統(tǒng)。這些數(shù)學(xué)方法可以分為兩類:基于狀態(tài)空間的方法和組合方法。多值決策圖是結(jié)構(gòu)函數(shù)的一種緊湊表示形式。MDDs作為一種解決多狀態(tài)系統(tǒng)的有效方法，在許多文獻(xiàn)中得到了廣泛的研究。此外，還提出了基于擴(kuò)展形式的MDDs，以減少節(jié)點(diǎn)的數(shù)量。通過(guò)給邊緣賦值，比MDDs具有更緊湊的形式。Nagayama提出了EVMDDs中邊緣數(shù)的最小化算法，用于多狀態(tài)系統(tǒng)的快速分析。通過(guò)引入EVMDDs約簡(jiǎn)規(guī)則，進(jìn)一步提高了計(jì)算速度[2]。

本文提供了一種不需要從MDD轉(zhuǎn)換即可直接構(gòu)造EVMDD進(jìn)行多狀態(tài)系統(tǒng)可靠性評(píng)估的方法。本文的目的和解決的問(wèn)題是：根據(jù)系統(tǒng)的結(jié)構(gòu)函數(shù)，直接構(gòu)建多狀態(tài)系統(tǒng)的EVMDD模型，評(píng)估系統(tǒng)可靠性。該方法首先分析系統(tǒng)結(jié)構(gòu)特征，構(gòu)建系統(tǒng)的結(jié)構(gòu)函數(shù)，并以表格形式表示。之后，根據(jù)本文提出的直接構(gòu)造EVMDD的方法，得到多狀態(tài)系統(tǒng)的可靠性評(píng)估模型。構(gòu)造EVMDD的核心思想是如何計(jì)算EVMDD邊值，系統(tǒng)的狀態(tài)由從根節(jié)點(diǎn)到終端節(jié)點(diǎn)的邊值之和表示。因此，我們可以使用深度優(yōu)先搜索并假定初始值來(lái)獲得完整的EVMDD。當(dāng)完成一條路徑的遍歷時(shí)，邊值之和應(yīng)等于系統(tǒng)的狀態(tài)。如果值不相等，則反向更新邊值。最后，利用本文提出的構(gòu)建方法，對(duì)于多狀態(tài)系統(tǒng)可靠性進(jìn)行評(píng)估。

2 評(píng)估方法

本文提出的直接構(gòu)造EVMDD的多狀態(tài)系統(tǒng)可靠性評(píng)估方法主要包含以下四個(gè)部分。

2.1 根據(jù)系統(tǒng)的多性能水平狀態(tài)，構(gòu)建系統(tǒng)的多值結(jié)構(gòu)函數(shù)

構(gòu)造多狀態(tài)系統(tǒng)的結(jié)構(gòu)函數(shù)就是構(gòu)造組件狀態(tài)與系統(tǒng)狀態(tài)之間的各種映射。結(jié)構(gòu)函數(shù)可以用表格、解析式或算法表示。本文中為了顯示直觀，用表格表示多狀態(tài)系統(tǒng)的結(jié)構(gòu)函數(shù)。下面說(shuō)明結(jié)構(gòu)函數(shù)的具體構(gòu)建步驟：

步驟1：確定系統(tǒng)、分系統(tǒng)和單元的任務(wù)目標(biāo)，分別監(jiān)測(cè)系統(tǒng)、分系統(tǒng)和單元的降級(jí)過(guò)程，并將其具有的明顯功能降級(jí)的各個(gè)狀態(tài)用離散的數(shù)值進(jìn)行表示。如一個(gè)包含n個(gè)組件的多狀態(tài)系統(tǒng)，向量表示所有n個(gè)系統(tǒng)組件的狀態(tài)；系統(tǒng)共有m個(gè)狀態(tài)：從系統(tǒng)最佳狀態(tài)（m-1狀態(tài)）到系統(tǒng)完全失效（0狀態(tài)），在一些研究中m也被稱作多狀態(tài)系統(tǒng)的可靠性水平。每個(gè)系統(tǒng)組件有m個(gè)狀態(tài)每種狀態(tài)的概率為：

多狀態(tài)系統(tǒng)的可靠性（狀態(tài)）取決于組件狀態(tài)和系統(tǒng)的結(jié)構(gòu)函數(shù)：

步驟2：若系統(tǒng)、分系統(tǒng)和單元的狀態(tài)監(jiān)測(cè)數(shù)據(jù)是連續(xù)值，則需要根據(jù)不同的數(shù)據(jù)范圍與步驟1中定義的離散狀態(tài)值建立映射關(guān)系，即用一個(gè)離散的值表示單元性能的某個(gè)區(qū)間值。若系統(tǒng)、分系統(tǒng)和單元的狀態(tài)監(jiān)測(cè)數(shù)據(jù)本身是離散值，則直接與步驟1中的狀態(tài)值建立一一對(duì)應(yīng)關(guān)系即可。這樣就可以得到多組單元、分系統(tǒng)和系統(tǒng)的狀態(tài)組合關(guān)系，將這些組合關(guān)系以表格的形式進(jìn)行表示，表中的每一行表示了一種組合關(guān)系。

在實(shí)際應(yīng)用中，一個(gè)組件的退化會(huì)影響系統(tǒng)的性能，即使系統(tǒng)不會(huì)立即發(fā)生明顯退化，所以多狀態(tài)系統(tǒng)的結(jié)構(gòu)函數(shù)可以看作一個(gè)單調(diào)遞增函數(shù)。

2.2 根據(jù)系統(tǒng)的多性能水平狀態(tài)，構(gòu)建系統(tǒng)的多值結(jié)構(gòu)函數(shù)

本文采用深度優(yōu)先和假定初始值的方法來(lái)獲得多狀態(tài)系統(tǒng)的EVMDD模型。每條路徑邊值之和就是系統(tǒng)的一種狀態(tài)。判斷得到的邊值是否與結(jié)構(gòu)函數(shù)表中系統(tǒng)狀態(tài)值對(duì)應(yīng)，如果不對(duì)應(yīng)就反向更新邊值，直到等于系統(tǒng)狀態(tài)值[4]。

首先給出方法構(gòu)建中所應(yīng)用相關(guān)符號(hào)的定義：

ti是第i個(gè)組件的狀態(tài)空間

si是ti確定的系統(tǒng)狀態(tài)值，

ni是ti中的狀態(tài)數(shù)量；

L是組件狀態(tài)與系統(tǒng)狀態(tài)之間的映射關(guān)系的數(shù)量；

pi是EVMDD中一條路徑；

wij是路徑pi的第j個(gè)節(jié)點(diǎn)的權(quán)重值；

k是一個(gè)臨時(shí)變量；

i是下標(biāo)變量；

根據(jù)EVMDDs的特點(diǎn)和多值函數(shù)的定義，可以得出EVMDD的構(gòu)建過(guò)程包括以下七個(gè)步驟：

步驟1：設(shè)初值：令i=1；

步驟2：當(dāng)i＞L時(shí)，過(guò)程結(jié)束；否則轉(zhuǎn)第三步；

步驟3：根據(jù)結(jié)構(gòu)函數(shù)構(gòu)造EVMDD的第i條路徑；令k=ni，如果組件狀態(tài)是0，將0賦值給節(jié)點(diǎn)引出邊的邊值；否則賦值為1；

步驟5：根據(jù)系統(tǒng)狀態(tài)更新路徑pi的邊值。如果第k邊的值是0，轉(zhuǎn)步驟6；否則通過(guò)下面的公式驗(yàn)證權(quán)值：然后轉(zhuǎn)步驟7；

步驟6：令k=k-1，返回步驟5；

步驟7：判斷節(jié)點(diǎn)的所有的邊是否都構(gòu)造完成，如果已經(jīng)完成，判斷節(jié)點(diǎn)是否已經(jīng)存在。如果節(jié)點(diǎn)已經(jīng)存在，刪除節(jié)點(diǎn)并讓引進(jìn)的邊連接到已經(jīng)存在的節(jié)點(diǎn)。然后令i=i+1并返回步驟2。

2.3 應(yīng)用兩個(gè)簡(jiǎn)化規(guī)則減少EVMDD模型節(jié)點(diǎn)的數(shù)量，提高計(jì)算效率

規(guī)則1：共享子圖

當(dāng)2個(gè)節(jié)點(diǎn)引出邊的邊值完全對(duì)應(yīng)相同，且所有的邊連接到相同的節(jié)點(diǎn)或者對(duì)應(yīng)相等的系統(tǒng)狀態(tài)值的情況下，這兩個(gè)節(jié)點(diǎn)就是完全相同的，可以簡(jiǎn)化為一個(gè)節(jié)點(diǎn)。

規(guī)則2：刪除滿足以下兩個(gè)條件的非終端節(jié)點(diǎn)，并將指向已刪除節(jié)點(diǎn)的邊重新指向節(jié)點(diǎn)V。

（1）它的引出邊都指向同一個(gè)節(jié)點(diǎn)V；

（2）所有引出邊的邊值都為0。

兩個(gè)條件需同時(shí)滿足才可以進(jìn)行刪減節(jié)點(diǎn)。

2.4 EVMDD模型進(jìn)行多狀態(tài)系統(tǒng)的可靠性評(píng)估

多狀態(tài)系統(tǒng)可靠性與系統(tǒng)當(dāng)前性能水平有關(guān)，多狀態(tài)系統(tǒng)可靠性計(jì)算使用下面的公式：

s(t)表示系統(tǒng)當(dāng)前性能水平下的狀態(tài)，s(t)表示系統(tǒng)的性能需求。本文中將系統(tǒng)的連續(xù)性能指標(biāo)離散化，與離散的系統(tǒng)狀態(tài)進(jìn)行映射。

3 具體實(shí)施方式

實(shí)施方式說(shuō)明：提供了一種基于系統(tǒng)、分系統(tǒng)和單元的狀態(tài)監(jiān)測(cè)數(shù)據(jù)自動(dòng)學(xué)習(xí)系統(tǒng)可靠性模型和失效參數(shù)，并對(duì)系統(tǒng)進(jìn)行可靠性進(jìn)行評(píng)估的方法，具體實(shí)施方式說(shuō)明如下。

3.1 構(gòu)建多狀態(tài)系統(tǒng)的結(jié)構(gòu)函數(shù)

通過(guò)對(duì)系統(tǒng)每個(gè)單元所包含的不同狀態(tài)進(jìn)行分析，進(jìn)而得到整個(gè)多狀態(tài)系統(tǒng)的結(jié)構(gòu)函數(shù)。下面結(jié)合具體實(shí)例進(jìn)行說(shuō)明：

一個(gè)多狀態(tài)n中取k系統(tǒng)，由三臺(tái)熱電聯(lián)產(chǎn)機(jī)組組成的區(qū)域電力和供熱系統(tǒng)，可同時(shí)產(chǎn)生電力和熱能，該系統(tǒng)為負(fù)荷提供電能和熱能。在該系統(tǒng)中在該系統(tǒng)中，G1是一個(gè)GPC-180D氣體單元，G2和G3是GPC-70D氣體單元。三個(gè)燃?xì)鈾C(jī)組的額定發(fā)電能力列于表1。

表1 各單元發(fā)電能力參數(shù)表

每個(gè)發(fā)電機(jī)組包含三種狀態(tài)：0；1；2，三種機(jī)組狀態(tài)對(duì)應(yīng)的性能等級(jí)及該性能水平發(fā)生概率如下表格2所示：

表2 G1機(jī)組的三種狀態(tài)的性能參數(shù)及每種狀態(tài)發(fā)生概率

表3 G2機(jī)組的三種狀態(tài)的性能參數(shù)及每種狀態(tài)發(fā)生概率

表4 G3機(jī)組三種狀態(tài)的性能參數(shù)及每種狀態(tài)發(fā)生概率

表5 電力和供熱系統(tǒng)的容量分配

因此，對(duì)應(yīng)多狀態(tài)系統(tǒng)的結(jié)構(gòu)函數(shù)可以由系統(tǒng)中每個(gè)單元的狀態(tài)組合得到，如表6所示：

表6 熱電系統(tǒng)結(jié)構(gòu)函數(shù)

3.2 建系統(tǒng)的EVMDD模型

本文采用深度優(yōu)先和假定初始值的方法來(lái)獲得多狀態(tài)系統(tǒng)的EVMDD模型。通過(guò)遍歷每條路徑，得到相應(yīng)的邊值，每條路徑上的邊值之和對(duì)應(yīng)多狀態(tài)系統(tǒng)的一種狀態(tài)。判斷路徑的邊值之和是否與結(jié)構(gòu)函數(shù)表中系統(tǒng)狀態(tài)值對(duì)應(yīng)，如果不對(duì)應(yīng)就反向更新邊值，直到等于系統(tǒng)狀態(tài)值就完成當(dāng)前路徑，繼續(xù)下一條路徑[5]。

ti是第i個(gè)組件的狀態(tài)空間

si是ti確定的系統(tǒng)狀態(tài)值，

ni是ti中的狀態(tài)數(shù)量；

L是組件狀態(tài)與系統(tǒng)狀態(tài)之間的映射關(guān)系的數(shù)量，L=27；

pi是EVMDD中一條路徑；

wij是路徑pi的第j個(gè)節(jié)點(diǎn)的權(quán)重值；

k是一個(gè)臨時(shí)變量；

i是下標(biāo)變量；

具體構(gòu)建步驟描述如下：

步驟1：設(shè)定初值：令i=1；

步驟2：當(dāng)i＞L時(shí)，過(guò)程結(jié)束；否則轉(zhuǎn)第三步；

步驟3：根據(jù)結(jié)構(gòu)函數(shù)構(gòu)造EVMDDs的第i條路徑；令k=ni，如果組件狀態(tài)是0，將0賦值給節(jié)點(diǎn)引出邊的邊值；否則賦值為1；

步驟5：根據(jù)系統(tǒng)狀態(tài)更新路徑pi的邊值。如果第k邊的值是0，轉(zhuǎn)步驟6；否則通過(guò)下面的公式驗(yàn)證權(quán)值：然后轉(zhuǎn)步驟7；步驟6：令k=k-1，返回步驟5；

步驟7：判斷節(jié)點(diǎn)的所有的邊是否都已經(jīng)構(gòu)造完成。若已經(jīng)完成，判斷節(jié)點(diǎn)是否已經(jīng)存在。若節(jié)點(diǎn)已經(jīng)存在，刪除節(jié)點(diǎn)并讓引進(jìn)的邊連接到已經(jīng)存在的節(jié)點(diǎn)。然后令i=i+1并返回步驟2。

3.3 減少節(jié)點(diǎn)數(shù)量、提高算法效率

依照上述步驟遍歷結(jié)構(gòu)函數(shù)表格中所有向量，構(gòu)建出系統(tǒng)所有路徑，并應(yīng)用兩個(gè)簡(jiǎn)化規(guī)則，將相同子圖保留一個(gè)，刪除對(duì)系統(tǒng)無(wú)影響的節(jié)點(diǎn)，對(duì)EVMDD進(jìn)行簡(jiǎn)化，最終得到多狀態(tài)系統(tǒng)的EVMDD結(jié)構(gòu)

3.4 EVMDD模型進(jìn)行多狀態(tài)的可靠性評(píng)估

根據(jù)n中取k多狀態(tài)系統(tǒng)中每個(gè)機(jī)組的狀態(tài)概率分布（表7），可以得到多狀態(tài)系統(tǒng)在不同狀態(tài)下的聯(lián)合概率分布，如表7所示：

表7 多狀態(tài)系統(tǒng)狀態(tài)概率分布表

則該n中取k的多狀態(tài)系統(tǒng)的可靠度是0.89925

4 結(jié)語(yǔ)

本文提出了一種直接從結(jié)構(gòu)函數(shù)構(gòu)造EVMDDs的方法，而不是使用MDDs。對(duì)于具有大量系統(tǒng)狀態(tài)的大型多狀態(tài)系統(tǒng)，該方法非常方便有效。此外，為了減少時(shí)間開銷，本文還介紹了一種基于EVMDDs的并行分析算法。該算法很容易在當(dāng)前的并行框架或庫(kù)中實(shí)現(xiàn)。通過(guò)對(duì)并行算法和直接算法效率的比較表明，隨著構(gòu)件數(shù)量和系統(tǒng)狀態(tài)數(shù)的增加，并行算法比直接算法具有更大的優(yōu)勢(shì)。

本文提出的算法沒有考慮變量的階數(shù)，因?yàn)殡A數(shù)會(huì)影響EVMDDs的大小。在以后的工作中，我們將研究變量的順序和evmdd的大小之間的關(guān)系。