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

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

（廣州廣電計量檢測股份有限公司，廣東 廣州 510656）

0 引言

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

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

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

1 概述

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

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

2 評估方法

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

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ù)。下面說明結(jié)構(gòu)函數(shù)的具體構(gòu)建步驟：

步驟1：確定系統(tǒng)、分系統(tǒng)和單元的任務目標，分別監(jiān)測系統(tǒng)、分系統(tǒng)和單元的降級過程，并將其具有的明顯功能降級的各個狀態(tài)用離散的數(shù)值進行表示。如一個包含n個組件的多狀態(tài)系統(tǒng)，向量表示所有n個系統(tǒng)組件的狀態(tài)；系統(tǒng)共有m個狀態(tài)：從系統(tǒng)最佳狀態(tài)（m-1狀態(tài)）到系統(tǒng)完全失效（0狀態(tài)），在一些研究中m也被稱作多狀態(tài)系統(tǒng)的可靠性水平。每個系統(tǒng)組件有m個狀態(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)測數(shù)據(jù)是連續(xù)值，則需要根據(jù)不同的數(shù)據(jù)范圍與步驟1中定義的離散狀態(tài)值建立映射關系，即用一個離散的值表示單元性能的某個區(qū)間值。若系統(tǒng)、分系統(tǒng)和單元的狀態(tài)監(jiān)測數(shù)據(jù)本身是離散值，則直接與步驟1中的狀態(tài)值建立一一對應關系即可。這樣就可以得到多組單元、分系統(tǒng)和系統(tǒng)的狀態(tài)組合關系，將這些組合關系以表格的形式進行表示，表中的每一行表示了一種組合關系。

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

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

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

首先給出方法構(gòu)建中所應用相關符號的定義：

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

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

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

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

pi是EVMDD中一條路徑；

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

k是一個臨時變量；

i是下標變量；

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

步驟1：設初值：令i=1；

步驟2：當i＞L時，過程結(jié)束；否則轉(zhuǎn)第三步；

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

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

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

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

2.3 應用兩個簡化規(guī)則減少EVMDD模型節(jié)點的數(shù)量，提高計算效率

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

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

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

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

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

兩個條件需同時滿足才可以進行刪減節(jié)點。

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

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

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

3 具體實施方式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

pi是EVMDD中一條路徑；

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

k是一個臨時變量；

i是下標變量；

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

步驟1：設定初值：令i=1；

步驟2：當i＞L時，過程結(jié)束；否則轉(zhuǎn)第三步；

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

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

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

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

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

3.4 EVMDD模型進行多狀態(tài)的可靠性評估

根據(jù)n中取k多狀態(tài)系統(tǒng)中每個機組的狀態(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é)語

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

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