基于邏輯確定性的BDD變量排序方法

崔譜龍 葉華平 閆 華

（陸軍勤務(wù)學(xué)院 重慶 400000）

1 引言

從多階段任務(wù)系統(tǒng)的角度，對(duì)戰(zhàn)時(shí)油料保障任務(wù)可靠性進(jìn)行分析，能夠發(fā)現(xiàn)系統(tǒng)中的薄弱環(huán)節(jié)，并據(jù)此改進(jìn)任務(wù)配置，提高油料保障的任務(wù)可靠性。但是，由于戰(zhàn)時(shí)油料保障任務(wù)時(shí)間跨度長(zhǎng)、任務(wù)復(fù)雜，且隨作戰(zhàn)要求的變化其裝備配置也在不斷變化，因此，對(duì)其可靠性的分析變得非常復(fù)雜。目前，多階段任務(wù)系統(tǒng)的可靠性分析方法主要有兩類：1）組合模型法，常用的如二維決策圖法（Binary Decision Diagram，BDD）［1～4］；2）狀態(tài)空間法［5～8］，如Markov法和Petri網(wǎng)法?；跔顟B(tài)空間的方法能夠有效描述多階段任務(wù)的動(dòng)態(tài)行為并解決部件的跨階段依賴問題，但存在狀態(tài)空間爆炸的問題?；贐DD的分析方法比傳統(tǒng)的組合模型及狀態(tài)空間模型在存儲(chǔ)空間和計(jì)算效率都有明顯的優(yōu)勢(shì)［9］，其通過階段代數(shù)和微元替代法解決跨階段依賴問題。但隨著階段數(shù)和微部件的增加，生成BDD的規(guī)模會(huì)不斷增大，需要確定合理的變量排序方法進(jìn)一步縮減BDD的規(guī)模。

利用BDD對(duì)油料保障任務(wù)可靠性進(jìn)行分析時(shí)，變量排序方法直接影響最終可靠性模型的規(guī)模大小，其不僅包括階段內(nèi)變量的排序，還包括各階段之間變量的排序。對(duì)于階段內(nèi)變量的排序，現(xiàn)在排序方法一般可以分為兩類：基于結(jié)構(gòu)的方法和基于權(quán)重的方法?；诮Y(jié)構(gòu)的排序方法［10～11］根據(jù)從上至下、從左至右或深度優(yōu)先等方式對(duì)故障樹進(jìn)行遍歷，根據(jù)變量的訪問順序?qū)ψ兞颗判?；基于?quán)重的方法［12］，一般需要對(duì)變量進(jìn)行兩次遍歷，根據(jù)不同的賦權(quán)規(guī)則對(duì)第一次遍歷的變量賦權(quán)，第二次遍歷再根據(jù)變量的權(quán)重進(jìn)行排序。這兩類方法主要是借鑒對(duì)單階段變量排序的方法，沒有考慮變量在不同階段的跨階段依賴性，對(duì)不同結(jié)構(gòu)的多階段任務(wù)，排序的性能波動(dòng)較大。對(duì)于階段之間變量的排序，現(xiàn)有的排序方法，根據(jù)變量順序與階段順序關(guān)系可分為向前PDO和向后PDO，研究證明向后PDO能自動(dòng)刪除共同部件，比向前PDO生成更小規(guī)模的BDD［13］。將相同部件的變量排在一起，有利于處理變量的階段依賴性，但存在相鄰實(shí)變量邏輯確定性不強(qiáng)從而產(chǎn)生重復(fù)節(jié)點(diǎn)的問題，需要進(jìn)一步優(yōu)化。將相同階段的變量排在一起，重復(fù)節(jié)點(diǎn)較少，但構(gòu)造BDD時(shí)，需要執(zhí)行輔助的移除過程來處理變量的階段依賴性，因?yàn)锽DD本身的化簡(jiǎn)操作會(huì)使這一過程變得很復(fù)雜。

通過總結(jié)現(xiàn)有排序方法中影響B(tài)DD規(guī)模的因素，本文提出了一種多階段任務(wù)系統(tǒng)BDD變量的排序方法。該方法通過化簡(jiǎn)系統(tǒng)故障樹減少實(shí)變量，基于邏輯確定性排序減少實(shí)變量重復(fù)節(jié)點(diǎn)，從而有效減少BDD模型中的節(jié)點(diǎn)數(shù)量。最后，通過實(shí)例驗(yàn)證方法的有效性。

2 基于邏輯確定性變量排序方法

2.1 排序思想

在多階段任務(wù)中，實(shí)變量的個(gè)數(shù)會(huì)因階段數(shù)增加而增多，因?yàn)橥徊考赡茉诙鄠€(gè)階段重復(fù)出現(xiàn)。同一部件的工作狀態(tài)可能對(duì)不同階段產(chǎn)生不同的影響，但任一階段任務(wù)的失敗都會(huì)導(dǎo)致整個(gè)任務(wù)的失敗。根據(jù)多階段任務(wù)這種結(jié)構(gòu)特點(diǎn)，提出系統(tǒng)故障樹化簡(jiǎn)和基于邏輯確定性的BDD排序方法，通過減少實(shí)變量的個(gè)數(shù)和增加共享的BDD節(jié)點(diǎn)數(shù)，以減少BDD結(jié)構(gòu)的的重復(fù)節(jié)點(diǎn)，從而減小BDD的規(guī)模。通過對(duì)現(xiàn)有排序方法［14～16］的分析，影響邏輯確定性的因素有變量的層次、子樹變量數(shù)目、最小相鄰變量和變量重復(fù)度。變量在故障樹中的層次越高，越靠近頂事件，邏輯確定性越高；變量所在子樹的變量數(shù)目越少，邏輯確定性越高；最小相鄰變量已排序，邏輯確定性越高；變量的重復(fù)度越低，邏輯確定性越高。

2.2 排序原則

要生成系統(tǒng)的排序，需要按一定的方式將元變量排序，再用實(shí)變量代替元變量則是系統(tǒng)。對(duì)于實(shí)變量在階段之間的排序方式，采用向后PDO排序的方式：以變量A為例，在各階段的實(shí)變量排序?yàn)椋篈nAn-1，…，A。現(xiàn)在主要確定元變量的排序原則。

定義1：邏輯確定性在多階段任務(wù)中，變量的失效狀態(tài)對(duì)其所在階段或整個(gè)任務(wù)成敗影響的大小稱為邏輯確定性。影響越大則邏輯確定性越強(qiáng)，對(duì)于邏輯確定性強(qiáng)的變量給予較高的排序優(yōu)先級(jí)。

定義2：最小相鄰變量是在故障樹中與同一邏輯門（或門或者與門）相連的變量。

對(duì)于影響邏輯確定性的影響因素：變量的層次、子樹變量數(shù)目、最小相鄰變量和變量重復(fù)度依次給予較低的優(yōu)先級(jí)。具體的優(yōu)先規(guī)則如下：

1）優(yōu)先規(guī)則一：變量的層次，變量在故障樹中的層次越高，邏輯確定性強(qiáng)，其排序優(yōu)先級(jí)越高。

2）優(yōu)先規(guī)則二：子樹變量數(shù)目，變量所在子樹的變量數(shù)目越少，邏輯確定性強(qiáng)，其排序優(yōu)先級(jí)高。

3）優(yōu)先規(guī)則三：最小相鄰變量，如果變量的最小相鄰變量已排序，已排序的最小相鄰變量越靠前，邏輯確定性強(qiáng)，其排序優(yōu)先級(jí)高。

4）優(yōu)先規(guī)則四：變量重復(fù)度，變量在各個(gè)階段重復(fù)的次數(shù)越少，邏輯確定性強(qiáng)，其排序優(yōu)先級(jí)高。

2.3 排序流程

圖1 子樹選擇判定流程

圖2 變量選擇流程

階段間的排序采用的向后PDO的排序方法，從最后一階段的故障樹開始對(duì)各階段故障樹依次遍歷。根據(jù)以上四個(gè)優(yōu)先規(guī)則，對(duì)各階段故障樹進(jìn)行子樹選擇和變量選擇。如果以上規(guī)則都無法確定優(yōu)先級(jí)，則按照故障樹結(jié)構(gòu)，從左至右的方式進(jìn)行排序。在故障樹的遍歷過程中，首先確定子樹，然后對(duì)子樹中包含的變量進(jìn)行排序。子樹的判定過程如圖1所示，首先按照優(yōu)先規(guī)則一優(yōu)先選擇包含層次最少的子樹；如果都相同則按照優(yōu)先規(guī)則二優(yōu)先選擇包含變量數(shù)少的子樹；如果都相同按照優(yōu)先規(guī)則三選擇包含最小相鄰變量且變量排序靠前的變量的子樹；如果都相同則按照從左至右的順序選擇子樹。

變量的選擇過程如圖2所示，首先按照優(yōu)先規(guī)則一，層次越高的變量排序優(yōu)先級(jí)越高；如果都相同，則按照優(yōu)先規(guī)則三，具有最小相鄰變量且變量排序靠前的變量?jī)?yōu)先排序；如果都相同，則按照從左至右的順序進(jìn)行變量排序。

2.4 步驟分析

假設(shè)多階段任務(wù)由n個(gè)變量，j個(gè)階段組成：Di代表故障樹第i階段門事件所包含變量數(shù)目集；C代表變量的最小相鄰變量集；R代表變量的重復(fù)度集；Oi代表故障樹元變量在第i階段的排序結(jié)果。

步驟一：根據(jù)共同失效變量對(duì)多階段任務(wù)系統(tǒng)故障樹化簡(jiǎn)。

步驟二：對(duì)系統(tǒng)故障樹進(jìn)行遍歷，得到各個(gè)階段故障樹門事件所包含變量數(shù)目集Di、變量的重復(fù)度集R、變量的最小相鄰變量集C。

步驟三：從第j個(gè)階段的最高層開始，按照邏輯確定性的四個(gè)優(yōu)先規(guī)則對(duì)變量進(jìn)行選擇判定，對(duì)子樹進(jìn)行選擇判定。具體過程是，先將最高層中的變量排序，然后進(jìn)行子樹選擇，再進(jìn)行下一層變量排序，子樹排序完成后再回溯至上一層進(jìn)行子樹選擇，變量排序，直至第j階段故障樹所有變量都被排序，生成階段排序Oi。

圖3 排序方法流程圖

步驟四：對(duì)i-1階段中沒有參與排序的變量繼續(xù)排序。排序的方法同步驟三，直到各個(gè)階段的變量都已排序，得到排序各階段的排序結(jié)果分別有O1，O2，…，Oj表示。

步驟五：得到多階段任務(wù)元變量的排序Oj?…?O2?O1，按照向后PDO的方式將元變量用實(shí)變量代替則得到多階段任務(wù)實(shí)變量的排序。整個(gè)過程排序流程如圖3所示。

2.5 算例分析

為了更好地說明基于邏輯確定性BDD變量的排序方法的排序過程，本文對(duì)經(jīng)過簡(jiǎn)化的油料保障案例，如圖4，用文中的排序方法進(jìn)行變量排序。

圖4 油料保障案例

1）BDD變量排序

步驟一：根據(jù)共同失效變量對(duì)多階段任務(wù)系統(tǒng)故障樹化簡(jiǎn)。故障樹中存在共同失效變量A，在階段1中，A與B通過與門連接則將A與G1門事件對(duì)應(yīng)的子樹刪去；在階段2中，A與G3門事件通過與門連接則將A與G3門事件對(duì)應(yīng)的子樹刪去；在階段3中將A刪去，G6與G8對(duì)應(yīng)的子樹是共同失效模塊，G8在階段4中且與或門相連則將G6對(duì)應(yīng)的子樹刪去。通過上述化簡(jiǎn)后對(duì)故障樹進(jìn)行重新整理，可以得到新的故障樹，如圖5。

圖5 化簡(jiǎn)后的故障樹

步驟二：對(duì)系統(tǒng)故障樹進(jìn)行遍歷，得到各個(gè)階段故障樹門事件所包含變量數(shù)目集Di、變量的重復(fù)度集R、變量的最小相鄰變量集C。遍歷結(jié)果如下表1所示。

步驟三：從階段4的最高層開始，變量A是故障樹第0層的唯一變量故首先對(duì)A進(jìn)行排序。第0層存在唯一門事件G8故確定了子樹，變量C和變量F是最小相鄰變量，F(xiàn)的重復(fù)度小于C故先對(duì)F排序后對(duì)C排序，生成階段4排序O4｛A?F?C｝。

步驟四：對(duì)階段3中沒有參與排序的變量繼續(xù)排序。變量E是階段3故障樹第0層的唯一變量故首先對(duì)E進(jìn)行排序。第0層存在唯一門事件G5故確定了子樹，變量B和變量D是最小相鄰變量，B的重復(fù)度小于D故先對(duì)B排序后對(duì)D排序，生成階段3的排序O3｛E?B?D｝。至此所有的元變量都已排序。

步驟五：得到多階段任務(wù)元變量的排序O4?O3｛A?F?C?E?B?D｝，按照向后PDO的方式將元變量用實(shí)變量代替則得到整個(gè)任務(wù)實(shí)變量的排序?yàn)?/p>

A4? F4? C4? C1? E3? B3? D3? D1

2）BDD構(gòu)造

根據(jù)本文BDD變量的排序，構(gòu)造出整個(gè)任務(wù)的BDD，如圖6所示，實(shí)變量有8個(gè)，BDD圖中只包括9個(gè)節(jié)點(diǎn)，只有E3變量重復(fù)出現(xiàn)了一次。

圖6 本文方法生成BDD圖

下面運(yùn)用傳統(tǒng)的深度優(yōu)先法對(duì)本例進(jìn)行排序，從階段1至階段4，按照從左至右、從上至下并考慮變量重復(fù)度的方法進(jìn)行排序。通過對(duì)比BDD的規(guī)模，體現(xiàn)基于邏輯確定性排序方法的優(yōu)勢(shì)。通過改進(jìn)的深度優(yōu)先法，對(duì)本例的排序結(jié)果為C4?C2?C1?D3?D2?D1?E3?E2?B3?B1?A4?A3?A2?A1?F4。構(gòu)造BDD如圖7所示，節(jié)點(diǎn)數(shù)為16個(gè)。通過對(duì)比可以發(fā)現(xiàn)傳統(tǒng)排序方法生成的BDD中實(shí)變量個(gè)數(shù)多，相同的實(shí)變量的重復(fù)次數(shù)也比用本文的方法生成的BDD多。E3、D3、A4分別重復(fù)了5次、3次和2次，相鄰變量D3和B3分別重復(fù)了3次和2次。在本文排序方法中，根據(jù)邏輯確定性將失效會(huì)直接導(dǎo)致任務(wù)失敗的變量A優(yōu)先排序，將相鄰變量D和B相鄰排序，將重復(fù)次數(shù)較多D和C給予較低的排序優(yōu)先級(jí)，所以構(gòu)造的BDD中有更多的共享節(jié)點(diǎn)，減少了重復(fù)出現(xiàn)的節(jié)點(diǎn)數(shù)，從而減小了BDD的規(guī)模，有利于提高可靠性計(jì)算的效率。

圖7 傳統(tǒng)方法生成BDD圖

3 結(jié)語

基于二維決策圖的戰(zhàn)時(shí)油料保障任務(wù)可靠性分析，其變量排序?qū)DD的規(guī)模以及計(jì)算效率有重要的影響。通過總結(jié)現(xiàn)有研究方法中對(duì)BDD規(guī)模的影響因素，提出一種改進(jìn)的變量排序方法?；谶壿嫶_定性對(duì)變量的層次、子樹變量數(shù)目、最小相鄰變量和變量重復(fù)度依次給予較低的優(yōu)先級(jí)，從而增加BDD中的共享節(jié)點(diǎn)，有助于減小BDD的規(guī)模，提高戰(zhàn)時(shí)油料保障任務(wù)可靠性分析的效率。