基于邊值多值決策圖的多狀態系統可靠性評估方法

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

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

0 引言

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

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

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

1 概述

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

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

2 評估方法

本文提出的直接構造EVMDD的多狀態系統可靠性評估方法主要包含以下四個部分。

2.1 根據系統的多性能水平狀態，構建系統的多值結構函數

構造多狀態系統的結構函數就是構造組件狀態與系統狀態之間的各種映射。結構函數可以用表格、解析式或算法表示。本文中為了顯示直觀，用表格表示多狀態系統的結構函數。下面說明結構函數的具體構建步驟：

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

多狀態系統的可靠性（狀態）取決于組件狀態和系統的結構函數：

步驟2：若系統、分系統和單元的狀態監測數據是連續值，則需要根據不同的數據范圍與步驟1中定義的離散狀態值建立映射關系，即用一個離散的值表示單元性能的某個區間值。若系統、分系統和單元的狀態監測數據本身是離散值，則直接與步驟1中的狀態值建立一一對應關系即可。這樣就可以得到多組單元、分系統和系統的狀態組合關系，將這些組合關系以表格的形式進行表示，表中的每一行表示了一種組合關系。

在實際應用中，一個組件的退化會影響系統的性能，即使系統不會立即發生明顯退化，所以多狀態系統的結構函數可以看作一個單調遞增函數。

2.2 根據系統的多性能水平狀態，構建系統的多值結構函數

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

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

ti是第i個組件的狀態空間

si是ti確定的系統狀態值，

ni是ti中的狀態數量；

L是組件狀態與系統狀態之間的映射關系的數量；

pi是EVMDD中一條路徑；

wij是路徑pi的第j個節點的權重值；

k是一個臨時變量；

i是下標變量；

根據EVMDDs的特點和多值函數的定義，可以得出EVMDD的構建過程包括以下七個步驟：

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

步驟2：當i＞L時，過程結束；否則轉第三步；

步驟3：根據結構函數構造EVMDD的第i條路徑；令k=ni，如果組件狀態是0，將0賦值給節點引出邊的邊值；否則賦值為1；

步驟5：根據系統狀態更新路徑pi的邊值。如果第k邊的值是0，轉步驟6；否則通過下面的公式驗證權值：然后轉步驟7；

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

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

2.3 應用兩個簡化規則減少EVMDD模型節點的數量，提高計算效率

規則1：共享子圖

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

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

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

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

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

2.4 EVMDD模型進行多狀態系統的可靠性評估

多狀態系統可靠性與系統當前性能水平有關，多狀態系統可靠性計算使用下面的公式：

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

3 具體實施方式

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

3.1 構建多狀態系統的結構函數

通過對系統每個單元所包含的不同狀態進行分析，進而得到整個多狀態系統的結構函數。下面結合具體實例進行說明：

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

表1 各單元發電能力參數表

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

表2 G1機組的三種狀態的性能參數及每種狀態發生概率

表3 G2機組的三種狀態的性能參數及每種狀態發生概率

表4 G3機組三種狀態的性能參數及每種狀態發生概率

表5 電力和供熱系統的容量分配

因此，對應多狀態系統的結構函數可以由系統中每個單元的狀態組合得到，如表6所示：

表6 熱電系統結構函數

3.2 建系統的EVMDD模型

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

ti是第i個組件的狀態空間

si是ti確定的系統狀態值，

ni是ti中的狀態數量；

L是組件狀態與系統狀態之間的映射關系的數量，L=27；

pi是EVMDD中一條路徑；

wij是路徑pi的第j個節點的權重值；

k是一個臨時變量；

i是下標變量；

具體構建步驟描述如下：

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

步驟2：當i＞L時，過程結束；否則轉第三步；

步驟3：根據結構函數構造EVMDDs的第i條路徑；令k=ni，如果組件狀態是0，將0賦值給節點引出邊的邊值；否則賦值為1；

步驟5：根據系統狀態更新路徑pi的邊值。如果第k邊的值是0，轉步驟6；否則通過下面的公式驗證權值：然后轉步驟7；步驟6：令k=k-1，返回步驟5；

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

3.3 減少節點數量、提高算法效率

依照上述步驟遍歷結構函數表格中所有向量，構建出系統所有路徑，并應用兩個簡化規則，將相同子圖保留一個，刪除對系統無影響的節點，對EVMDD進行簡化，最終得到多狀態系統的EVMDD結構

3.4 EVMDD模型進行多狀態的可靠性評估

根據n中取k多狀態系統中每個機組的狀態概率分布（表7），可以得到多狀態系統在不同狀態下的聯合概率分布，如表7所示：

表7 多狀態系統狀態概率分布表

則該n中取k的多狀態系統的可靠度是0.89925

4 結語

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

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