陸志毅 周云 王璟玢

（1.中國(guó)人民解放軍海軍裝備部駐上海地區(qū)軍事代表局 上海市 200241 2.中國(guó)航空無(wú)線電電子研究所 上海市 200241）

網(wǎng)絡(luò)可靠性概念最先針對(duì)通信網(wǎng)絡(luò)提出，其評(píng)估模型基于圖論和設(shè)備物理失效，研究主要集中于改進(jìn)算法和降低計(jì)算復(fù)雜度。20世紀(jì)90年代開(kāi)始網(wǎng)絡(luò)可靠性研究成為熱點(diǎn)，提出了包括連通可靠性在內(nèi)的很多網(wǎng)絡(luò)可靠性概念，以及基于二元決策圖(Binary Decision Diagram，BDD)等算法的方法論。21世紀(jì)后，對(duì)無(wú)線移動(dòng)網(wǎng)絡(luò)可靠性的研究成為熱點(diǎn)，同時(shí)針對(duì)復(fù)雜網(wǎng)絡(luò)的一些研究方法和成果也給復(fù)雜系統(tǒng)可靠性研究帶來(lái)新的啟發(fā)。

BDD作為一種描述布爾函數(shù)的數(shù)據(jù)結(jié)構(gòu)，最早由AKERS提出，用來(lái)操作大數(shù)據(jù)函數(shù)[1]。之后，BRYANT給出了BDD的基本操作及算法[2]，BDD得以廣泛應(yīng)用于硬件電路驗(yàn)證、組合優(yōu)化、規(guī)劃調(diào)度等研究領(lǐng)域中。

可靠性分析方面，COUDERT最早研究將BDD方法用于可靠性分析[3]，并且BDD在網(wǎng)絡(luò)連通可靠性分析領(lǐng)域的應(yīng)用研究獲得了大量的成果，實(shí)驗(yàn)證明利用BDD能夠有效提升網(wǎng)絡(luò)可靠性分析的性能。在一般的可靠性分析中，RAUZY等在內(nèi)的大部分設(shè)計(jì)研究人員，主要將BDD用作故障樹(shù)定量分析的工具[4]，這雖然體現(xiàn)了BDD技術(shù)高效、精確的優(yōu)勢(shì)，但是就整個(gè)可靠性分析過(guò)程而言，仍較為繁瑣。

任務(wù)可靠性是航電系統(tǒng)的重要指標(biāo)，主要的分析方法有GO法，Petri網(wǎng)，以及包括可靠性框圖、故障樹(shù)和Markov分析等在內(nèi)的典型可靠性建模分析方法。GO法依靠操作符和信號(hào)流建立GO圖，然后按照信號(hào)流向和操作符運(yùn)算規(guī)則進(jìn)行計(jì)算。Petri網(wǎng)方法在系統(tǒng)功能性能設(shè)計(jì)基礎(chǔ)上進(jìn)行系統(tǒng)狀態(tài)分析，進(jìn)一步建立表征系統(tǒng)狀態(tài)轉(zhuǎn)變的Petri網(wǎng)模型，依靠對(duì)每次狀態(tài)轉(zhuǎn)換的定量分析，最終實(shí)現(xiàn)全過(guò)程的可靠性分析。以上方法建模分析過(guò)程較為復(fù)雜，部分存在狀態(tài)爆炸的問(wèn)題。

本文在BDD的網(wǎng)絡(luò)連通可靠性分析方法，和傳統(tǒng)的任務(wù)可靠性分析方法基礎(chǔ)上，提出了一種基于網(wǎng)絡(luò)模型的任務(wù)可靠性分析方法。將產(chǎn)品的可靠性特征抽象為網(wǎng)絡(luò)模型，并利用基于BDD的網(wǎng)絡(luò)連通可靠性分析方法，來(lái)對(duì)其進(jìn)行分析，省略了前級(jí)的故障樹(shù)分析過(guò)程，具有建模過(guò)程簡(jiǎn)單、分析高效準(zhǔn)確、便于計(jì)算機(jī)自動(dòng)化分析等優(yōu)點(diǎn)。

1 BDD算法

1.1 基本概念

BDD是基于香農(nóng)分解的有向無(wú)環(huán)圖，是BDP（Binary Decision Program）的圖形化表示，是對(duì)香農(nóng)分解的簡(jiǎn)約化表達(dá),可直觀反映函數(shù)的邏輯結(jié)構(gòu)。其數(shù)據(jù)結(jié)構(gòu)空間高效合理，操作方法省時(shí)有效。

香農(nóng)分解定理：令f是基于變量集X(X∈Bn)的布爾表達(dá)式，且x為變量集X中的任一變量，則：

其中在fx=1表示x=1時(shí)f的值。

香農(nóng)分解是BDD分析和求解的基礎(chǔ)。為簡(jiǎn)化表達(dá)香農(nóng)分解，引入ite算子，香農(nóng)分解定義為：

圖1：BDD示例

其中F1=fx=1，F(xiàn)2=fx=0

BDD表示為G=，G為一個(gè)有向無(wú)環(huán)圖，V 為圖中節(jié)點(diǎn)的集合，E 為邊的集合。BDD的節(jié)點(diǎn)分為終節(jié)點(diǎn)和非終節(jié)點(diǎn)。終節(jié)點(diǎn)位于BDD圖的末端，狀態(tài)只能表示為0或1；每個(gè)非終節(jié)點(diǎn)標(biāo)識(shí)一個(gè)輸入變量，分別有1和0兩條輸出邊，1邊表示節(jié)點(diǎn)取1時(shí)的分支fx=1，0邊表示節(jié)點(diǎn)取0時(shí)的分支fx=0。如圖1所示，一般作圖時(shí)，非終節(jié)點(diǎn)用圓表示，而終節(jié)點(diǎn)都由方框來(lái)表示。

在BDD的基礎(chǔ)上，對(duì)變量順序施加約束后生成有序二元決策圖（Ordered BDD，OBDD）。對(duì)OBDD進(jìn)行約簡(jiǎn)，使其不包含同構(gòu)子圖，且節(jié)點(diǎn)的兩條邊指向不同節(jié)點(diǎn)，得到約簡(jiǎn)的OBDD（Reduced and Ordered BDD，ROBDD）。ROBDD對(duì)布爾函數(shù)的表達(dá)更為簡(jiǎn)潔有效，沿根節(jié)點(diǎn)向下索引時(shí)，每個(gè)節(jié)點(diǎn)在每條邊上出現(xiàn)不多于1次，且為升序。

對(duì)ROBDD的構(gòu)造而言，首先需要對(duì)變量順序施加約束，為所有變量分別創(chuàng)建索引，并且保持變量索引順序在整個(gè)構(gòu)造過(guò)程中不發(fā)生改變。例如xi

1.2 排序策略

BDD規(guī)模和計(jì)算量依賴于變量排序，不合適的排序會(huì)使BDD規(guī)模變得很龐大。目前針對(duì)BDD排序有很多算法，如精確變量排序算法，動(dòng)態(tài)變量排序算法，啟發(fā)式變量排序算法，優(yōu)先排序變量和道路排序分解策略等等。其中，廣度優(yōu)先排序策略（BFS）和優(yōu)先級(jí)排序策略(POS)應(yīng)用比較廣泛。

1.2.1 廣度優(yōu)先排序策略(BFS)

廣度優(yōu)先邊排序策略，是基于廣度優(yōu)先原則索引所有網(wǎng)絡(luò)節(jié)點(diǎn)，并在索引過(guò)程中對(duì)未排序的邊實(shí)施排序。

圖2：BFS排序示例

圖3：POS排序示例

圖4：某綜合處理設(shè)備功能原理圖

對(duì)給定網(wǎng)絡(luò)G=(V，E)，廣度優(yōu)先排序的過(guò)程如下：

（1）取?u∈V作為廣度優(yōu)先排序的起點(diǎn)，標(biāo)記u 狀態(tài)為已檢索，并將u 放入FIFO；

（2）若FIFO中存在元素，取元素u，檢索與u 關(guān)聯(lián)的邊ei=(u，vi)并進(jìn)行排序，如果vi未標(biāo)記為已訪問(wèn)則完成標(biāo)記后放入FIFO；

（3）重復(fù)步驟ii至FIFO為空，即完成排序。

以3×3晶格網(wǎng)絡(luò)為例，對(duì)各邊進(jìn)行廣度優(yōu)先排序，圖2為排序結(jié)果。

1.2.2 優(yōu)先級(jí)排序策略(POS)

優(yōu)先級(jí)排序策略的主要過(guò)程為：先按節(jié)點(diǎn)優(yōu)先級(jí)規(guī)則完成節(jié)點(diǎn)排序，若關(guān)聯(lián)多條邊的兩個(gè)節(jié)點(diǎn)都已排序，則以邊優(yōu)先級(jí)規(guī)則對(duì)這些邊排序。優(yōu)先級(jí)排序策略的節(jié)點(diǎn)優(yōu)先級(jí)規(guī)則如下:

（1）關(guān)聯(lián)的節(jié)點(diǎn)中已排序節(jié)點(diǎn)數(shù)量多的優(yōu)先；

（2）關(guān)聯(lián)的節(jié)點(diǎn)中已排序節(jié)點(diǎn)數(shù)量相同時(shí)，其關(guān)聯(lián)已排序節(jié)點(diǎn)排序靠前的節(jié)點(diǎn)優(yōu)先。

優(yōu)先級(jí)排序策略的邊優(yōu)先級(jí)規(guī)則如下:與邊關(guān)聯(lián)的已排序節(jié)點(diǎn)排序靠前的邊優(yōu)先。以3×3晶格網(wǎng)絡(luò)為例，對(duì)各邊進(jìn)行優(yōu)先級(jí)排序，圖2為排序結(jié)果。

表1：模型信息

1.3 基本運(yùn)算

為了計(jì)算的方便，BDD的運(yùn)算一般不直接進(jìn)行香農(nóng)分解，主要直接采用一些基本運(yùn)算規(guī)則。

令布爾表達(dá)式P和H如下：

◇表示任意邏輯運(yùn)算，則P和Q之間的邏輯運(yùn)算用 BDD 運(yùn)算表示如下，：

2 任務(wù)可靠性預(yù)計(jì)

2.1 網(wǎng)絡(luò)結(jié)構(gòu)模型

連通可靠性是最早開(kāi)始的網(wǎng)絡(luò)可靠性研究，與傳統(tǒng)可靠性一致，以概率統(tǒng)計(jì)理論為基礎(chǔ)，輔以圖論作為網(wǎng)絡(luò)“拓?fù)涮厥狻钡闹С郑悄壳熬W(wǎng)絡(luò)可靠性中最被認(rèn)可的部分。

本文探討的任務(wù)可靠性網(wǎng)絡(luò)模型，主要思想是將與系統(tǒng)任務(wù)完成相關(guān)的功能流和數(shù)據(jù)流關(guān)系，以有源網(wǎng)絡(luò)形式進(jìn)行表達(dá)，將任務(wù)可靠性分析問(wèn)題轉(zhuǎn)化為有源網(wǎng)絡(luò)源端到終端的兩端連通可靠性問(wèn)題。任務(wù)可靠性網(wǎng)絡(luò)模型可表達(dá)為：

其中N表示模型的節(jié)點(diǎn)集合，L表示模型的邊集合，R表示節(jié)點(diǎn)可靠度集合。

設(shè)N中有m個(gè)節(jié)點(diǎn)，則任意節(jié)點(diǎn)ni(ni∈N，1

從節(jié)點(diǎn)np到節(jié)點(diǎn)nq的任意邊lj=（np，nq），lj∈L，表示為保證任務(wù)的完成，節(jié)點(diǎn)np到節(jié)點(diǎn)nq間的功能或數(shù)據(jù)流。

任意元素ri∈R，表示節(jié)點(diǎn)ni的可靠度,規(guī)定幾點(diǎn)S和T的可靠度值為1。

在本文的模型中有以下假設(shè)：

（1）任一節(jié)點(diǎn)ni只存在正常（即ni=1）和故障（即ni=0）兩種狀態(tài)；

（2）任兩個(gè)節(jié)點(diǎn)間的故障是相互獨(dú)立的；

（3）任一邊lj為正常狀態(tài)；

（4）布置表征任務(wù)開(kāi)始的網(wǎng)絡(luò)源節(jié)點(diǎn)S；

（5）布置表征任務(wù)成功的網(wǎng)絡(luò)端節(jié)點(diǎn)T；

（6）對(duì)任務(wù)可靠性分析層次相應(yīng)設(shè)備進(jìn)行編號(hào)，將已編號(hào)設(shè)備布置為中間節(jié)點(diǎn)；

（7）根據(jù)任務(wù)活動(dòng)，添加網(wǎng)絡(luò)的邊，使源端節(jié)點(diǎn)S連接到終端節(jié)點(diǎn)T。

2.2 任務(wù)可靠性預(yù)計(jì)

圖5：任務(wù)可靠性網(wǎng)絡(luò)模型

圖6：任務(wù)可靠性網(wǎng)絡(luò)模型BDD

基于網(wǎng)絡(luò)模型預(yù)計(jì)任務(wù)可靠性，即為計(jì)算網(wǎng)絡(luò)模型源端節(jié)點(diǎn)S到終端節(jié)點(diǎn)T的連通可靠性?；赗OBDD的網(wǎng)絡(luò)模型任務(wù)可靠性分析，基本思想為：先由網(wǎng)絡(luò)的最小路集求得網(wǎng)絡(luò)的BDD，然后根據(jù)BDD求解連通可靠性的不交化積和表達(dá)式，最終完成任務(wù)可靠性預(yù)計(jì)。

假設(shè)有向網(wǎng)絡(luò)的節(jié)點(diǎn)集為N={ni}(i=1，2，…，s)，邊集為L(zhǎng)={li}(i= 1，2，…，t)，若要求n1到nt的可靠度，算法過(guò)程如下：

（1）從源節(jié)點(diǎn)開(kāi)始，利用BFS或POS等排序策略對(duì)任務(wù)可靠性網(wǎng)絡(luò)模型各邊進(jìn)行排序；

（2）求出n1到nt的最小路集。設(shè)已求出為為網(wǎng)絡(luò)模型最小路集的邏輯結(jié)構(gòu)函數(shù).其中，m表示最小路集數(shù)，fj表示某條最小路集j的所有節(jié)點(diǎn)布爾值的與；

（3）按照排序結(jié)果，作f的BDD；

（4）在邏輯結(jié)構(gòu)函數(shù)f的BDD上搜索從根節(jié)點(diǎn)到葉結(jié)點(diǎn)為1的路徑，則可獲得F的不交化最小路集其中g(shù)i表示最小路集經(jīng)變換后得到的不交和，p表示變換后得到的不交和項(xiàng)的項(xiàng)數(shù)。

任務(wù)可靠度可用下面的概率和公式直接進(jìn)行計(jì)算：

2.3 案例分析

考慮某綜合處理設(shè)備，其功能原理如圖4所示。

該綜合處理設(shè)備主要完成數(shù)據(jù)處理任務(wù)，具有雙余度電源設(shè)計(jì)，由主控制模塊進(jìn)行資源調(diào)度，由三個(gè)處理模塊提供數(shù)據(jù)處理的硬件資源，主控制模塊視當(dāng)前資源占用情況，調(diào)用其中一個(gè)完成當(dāng)前數(shù)據(jù)處理需求。

任務(wù)可靠性分析在模塊層面進(jìn)行，對(duì)各模塊進(jìn)行編碼，并求得時(shí)刻t的可靠度，如表1所示。并建立任務(wù)可靠性網(wǎng)絡(luò)模型，利用POS排序策略對(duì)模型中各邊進(jìn)行排序，如圖5所示。

列出圖5所示網(wǎng)絡(luò)，其邏輯結(jié)構(gòu)函數(shù)為：

進(jìn)一步作出該表達(dá)式對(duì)應(yīng)的BDD見(jiàn)圖6。

由BDD列出ST連通可靠性的不交化和表達(dá)式，即綜合處理設(shè)備的任務(wù)可靠性表達(dá)式：

計(jì)算得任務(wù)可靠度R=0.9995772，與使用可靠性框圖模型求解的結(jié)果一致。

3 總結(jié)

BDD方法被廣泛用于網(wǎng)絡(luò)連通可靠性求解，對(duì)復(fù)雜的邏輯關(guān)系計(jì)算呈現(xiàn)出較高的效率和準(zhǔn)確度。本文在網(wǎng)絡(luò)連通可靠性基礎(chǔ)上，提出了一種根據(jù)產(chǎn)品功能流和數(shù)據(jù)流建立的網(wǎng)絡(luò)模型，并將產(chǎn)品任務(wù)可靠性轉(zhuǎn)化為網(wǎng)絡(luò)連通可靠性進(jìn)行求解的方法，給出了模型建立和基于BDD進(jìn)行求解的方法。最后本文介紹了一個(gè)示例，說(shuō)明該方法是可靠的。任務(wù)可靠性網(wǎng)絡(luò)模型BDD如圖6。

該方法尚需進(jìn)行更多的模型轉(zhuǎn)化、模型規(guī)范等方面的研究，但是提供了面對(duì)復(fù)雜系統(tǒng)的任務(wù)可靠性預(yù)計(jì)的一種新思路，有以下兩方面可能的優(yōu)勢(shì)：

（1）模型建立方式簡(jiǎn)單，便于利用各種語(yǔ)言和建模方式描述的功能性能模型直接轉(zhuǎn)化而來(lái)，便于與基于模型的系統(tǒng)工程結(jié)合。

（2）計(jì)算方式高效，準(zhǔn)確，利于計(jì)算機(jī)進(jìn)行計(jì)算，方便形成計(jì)算機(jī)輔助分析的工具鏈。