基于故障樹的無線傳感器網絡可靠度符號計算

聶晨華，高 西，董榮勝

（桂林電子科技大學 廣西可信軟件重點實驗室，廣西 桂林541004）

0 引 言

故障樹分析 （fault tree analysis，FTA）是一種分析無線傳感器網絡 （wireless sensor network，WSN）［1］可靠性的方法之一。Kim 等提供了一個基于簇型的三層WSN 模型上的一種綜合可靠性評估方法：頂層是WSN 的網絡故障樹模型，中間層是傳感器節點的故障樹模型，底層是傳感器節點組件的馬爾科夫鏈模型，并使用SHARPE 軟件工具計算了傳感器節點以及WSN 的可靠度［2］；Bruneo提供了一種基于Non－Markovian 隨機Petri網 （NMSPN）分析方法，研究了在WSN 可靠性中能量控制的問題，提供了用故障樹來計算WSN 失效概率的方法［3］；Silva等用SHARPE 動態生成故障樹，并用不交和 （SDP）的方法對故障樹中的最小割集進行處理來計算WSN 的可靠度［4］。

由于應用不交和 （SDP）的方法在故障樹上計算系統可靠度，存在最小割集 （MCS）的不交化處理過程，該過程是一個NP－hard問題。基于香農分解的BDD （binary decision diagram）本身具有不交化的特性，能夠有效控制故障樹不交化處理過程中的組合爆炸，BDD 表示的故障樹包含了其所有的MCSs［5］。為此本文將BDD 技術引入到基于故障樹求WSN 可靠性的處理中，以應用通信可靠性 （application communication reliability，ACR）［6］的通信模式為背景，利用故障樹模型中的事件元素與邏輯門元素，建立基于故障樹的WSN 可靠性結構。采用BDD 技術，利用BDD 中的ite操作技術，用遞歸的方法給出從WSN 可靠性結構轉換到BDD 結構的算法，遍歷BDD 計算WSN 的可靠度，優化可靠度計算過程，降低WSN 可靠度計算的復雜性。以分層簇型網絡中可用路徑以及節點冗余下的應用通信可靠性問題為例，給出其可靠性結構，通過給出的算法轉換為BDD 結構，并計算以上兩種情況下的WSN 可靠度。

1 基于故障樹的WSN 可靠性結構

1.1 WSN 拓撲模型

社會、經濟和技術方面很多的系統結構都可以抽象成網絡形式，可以用節點表示系統實體，邊表示系統實體之間的物理鏈路或相關鏈路。

最基本的WSN 拓撲模型是用一個二元組表示的網絡拓撲結構圖。

定義1 G ＝（V，E）表示由n 個節點和m 條邊組成的網絡的拓撲結構圖，V ＝（v1，v2，…，vn）表示網絡的節點集合，E ＝（e1，e2，…，em）表示網絡中邊的集合且E V×V 。

1.2 基于加權圖的WSN 可靠性模型

一般采用加權圖 （probabilistic weighted network，PWN）對網絡中與節點或邊有關的屬性構造網絡模型進行研究。

定義2 G＝（V，E，W），其中G，V，E 的含義與定義1相同，W ＝（f（v），g（e）），v∈V，e∈E，f 表示與節點有關的權的函數，g 表示與邊有關的權的函數。

在研究與節點或邊有關的可靠性問題時，常把與節點和邊有關的可靠性屬性作為權值，用加權圖構造具有可靠性屬性的模型。基于加權圖的可靠性屬性模型依托WSN 原有的拓撲結構。為了更加直觀地反映WSN 可靠性問題本身的結構性，本文引入故障樹中事件與邏輯門兩種表示方式來構造基于故障樹的WSN 可靠性結構。接下來先介紹一般故障樹模型的形式化定義，然后給出基于故障樹的WSN 可靠性結構的形式化定義。

1.3 一般故障樹模型

故障樹用圖形和數學相結合的方法表示系統發生故障的事件之間的邏輯關系。故障樹分為靜態故障樹和動態故障樹兩種類型，本文選擇靜態故障樹進行建模。一般靜態故障樹形式化定義為：

定義3 Ftree＝（T，L），其中T＝（tt，tm，tx）表示故障樹事件的集合，事件的狀態值為 ｛0，1｝，其中tt為頂事件，在文中指WSN 系統的工作狀態，tm為中間事件，tx為底事件。L ＝（AND，OR，n＿out＿m），AND 是與門，OR是或門，n－out－of－m 是異或門。

1.4 基于故障樹的WSN 可靠性結構

WSN 的網絡拓撲結構會對網絡的連通性和組織結構產生影響。目前，作為典型的WSN 拓撲結構有星型，mesh型和簇型結構［7］。研究網絡可靠性，在節點或邊上加入相應的可靠性屬性，形成一個網絡靠性模型。本文從WSN 的拓撲結構出發，利用故障樹的事件和邏輯門元素，建立基于故障樹的一種直觀WSN 的可靠性結構。

WSN 可靠性結構的形式化定義：

定義4 F－WSN＝（V，Ftree，Fd＿i，Op，Fv，Pop＿v）

（1）Vnode，表示WSN 系統中的各類節點Node，Vnode＝（sink；CH1，…，CHi；Gw1，…，Gwj；S1，…，Sm），其中sink是匯聚節點，CH 是簇頭節點，Gw 是網關節點，S是普通傳感器節點Sensor nodes，下文中都用這些縮寫字母表示，且本文約定節點Node的狀態只有正常和失效兩種，并假設相鄰節點之間的鏈路是可靠的。

（2）Ftree＝ （T，L），其中T ＝（tt，tm，tx）表示故障樹事件的集合，事件的狀態取值為 ｛0，1｝，其中tt為頂事件，在文中指WSN 系統的工作狀態，tm為中間事件，tx為底事件。L ＝（AND，OR，n＿out＿m），AND 是與門，OR是或門，n－out－of－m 是異或門。在WSN 故障樹模型中底事件tx由網絡中的各類節點Node的狀態構成。

（3）Fd＿i，Fd表示傳感器節點的軟硬件設備，且該節點的冗余度為i。

（4）Op＝（op＿1，op＿2，…op＿i）表示網絡中節點的可用路徑集合。其中op＿i表示第i條可用路徑。

（5）Fv＝（Fv1，Fv2，…Fvi）表示網絡中的節點設備失效率集合，其中Fvi表示節點vi的失效概率，失效的原因是由節點自身設備故障導致，Rvi＝1－Fvi表示節點vi的可靠度。

（6）Pop＿v＝（Pop＿v1，Pop＿v2，…，Pop＿vi）表示網絡中節點的可用路徑的失效率集合，其中Pop＿vi表示節點vi的可用路徑的失效概率，Rop＿vi＝1－Pop＿vi表示節點vi到目標節點可用路徑的可靠度。

本文以單播模式下的應用通信可靠性 （ACR）研究為背景，建立基于簇型拓撲 （hierarchical clustering topology）特性下的WSN 可靠性模型。基于簇的分層拓撲中，所有傳感器節點S都處于最底層level－0 （第0層），傳感器節點S通過自組織與周圍的節點形成若干個簇Ci（i＝1，2，…m），并按分簇算法為每個簇選出一個簇頭，用表示level－k的簇頭節點。在level－0 的基礎上選出來的所有又形成高一級的簇level－1，再在這個level－1 簇中再選出一個簇頭，簇中的網關節點Gwi也是同樣分層，這個過程反復執行，直到選出處于網絡體系中最高層的。最高層的CH（t）i往往是離sink較近的節點，t表示WSN 體系中的最高層level－t。分層簇形拓撲節點之間的通信包含了多跳的meth網路由，以及簇和簇之間的通信要經過中間的路由節點即網關節點Gwi。選擇從傳感器節點到sink節點的數據傳播路徑步驟是：處于level－0中的傳感器節點S要將數據傳輸給sink節點，首先它要將信息通過多跳的方式發送給本簇中的，然后再將信息以同樣的方式發送給本簇中的網關節點，在與處在高一層簇中的網關節點通信，再將信息發送給，最后直接送入sink節點。根據以上簇型拓撲的特性給出分層簇WSN 失效定義。

（1）含有m 個簇的WSN，若m 中有多于s個簇失效，則WSN失效；一個簇中含有n個傳感器節點S，若有多于k個S失效，或者該簇中的簇頭CH（0）i失效，則么該簇失效。

（2）sink失效，則WSN 失效。

（3）與sink直接通信的簇中若n 個傳感器節點S中有多于k個節點失效或簇頭失效，則WSN 失效。

（4）每個簇中所有的網關節點失效則該簇失效，與sink直接通信的簇中的所有網關失效，則WSN失效。

下面給出WSN 網絡可靠度定義及其它相關定義。

定義5 節點設備可靠度：節點設備可靠度針對的是節點的軟件和硬件功能正常工作的概率。

用一個非負隨機變量X 來描述節點v 的壽命，X 相應的分布函數為Fv（t）＝P｛X ≤t｝（t≥0），Fv（t）稱為節點v的失效函數，即t時刻時的失效概率，那么在時刻t以前都不失效的概率即網絡節點在時刻t 的生存概率Rv（t）＝P｛X＞t｝＝1－Fv（t）＝（t），式中Rv（t）稱為節點設備在時刻t的可靠度函數或可靠度。

定義6 可用路徑失效Op：在具有多跳路由的WSN中，可用路徑是源節點和目標節點保持連通的路徑，即從一個節點到目標節點的路徑上經過的每一個節點都是必不可少的，若路徑上經過的任何一個節點因為其設備發生故障，源節點和目標節點都不連通，即認為此條路徑失效。

定義7 節點失效：當節點的設備出現永久性故障或者在該節點和目標節點之間不存在可用路徑而無法進行通信的情況下認為該節點失效。

定義8 WSN 可靠度：WSN 可靠度記為RWSN是衡量WSN 網絡可靠性的一個重要指標，那么WSN 失效概率為PWSN＝1－RWSN。本文中計算的WSN 失效概率PWSN指WSN 在特定的拓撲結構下，根據其失效條件發生網絡的整體失效而無法正常工作的概率。

根據以上給出的節點失效定義和可用路徑Op失效的定義來構建WSN 網絡節點的故障樹模型如圖1所示，圖中的Node可以是節點CH，Gw，S。Fd＿0 表示該節點的冗余度為0。

網絡節點易失效，這種失效往往能夠被冗余設備所容納，并且當節點發生故障時，冗余設備可以替代原節點完成原有功能，且冗余設備與原節點具有相同的失效概率。其故障樹模型如圖2 所示，圖中的Node可以是節點CH，Gw，S。Fd＿0…Fd＿j表示該節點共有j個冗余設備。

圖1 不含冗余設備的節點故樟樹

圖2 含有冗余設備的節點故樟樹

根據上文中的形式化模型和相關定義給出一個分層簇型的WSN 的例子。含有3個簇的2層WSN 拓撲圖如圖3所示，其基于故障樹的可靠性結構如圖4所示。其中傳感器節點S，簇頭節點CH，網關節點Gw 是中間事件，這些節點的故障樹模型如圖1或圖2所示。

圖3 WSN 分層簇型拓撲

2 WSN 節點和可用路徑失效概率的計算

根據節點設備可靠度定義，由于節點的設備發生故障，可以引起的節點的失效，假設組成WSN 的4 種節點（sink，CH，Gw，S）的失效函數都符合指數分布，由于它們在網絡中的位置和功能的不同，因此各種節點設備的失效率λ 是不同的，普通的傳感器節點S 的失效率最高，Gw，CH，sink的失效率依次降低，并且可以通過平均壽命MTTF 計算出節點設備失效率，根據

式中：λ——節點設備的失效率，當MTTF（hours）為2年時，λ5e－5，將以上的計算出來的節點設備失效率λ作為傳感器節點S的失效率，Gw，CH，Sink的失效率依次降低一個數量級，然后將各節點的失效率λ帶入指數分布函數F（t）＝1－e－λt，λ＞0，t≥0中就可以計算出時刻t下的節點設備失效概率。

圖4 基于故障樹的分層簇型WSN 可靠性結構

根據可用路徑Op的定義，引起節點所在的可用路徑失效Op的原因是路徑上的存在由于設備故障引起的失效節點，計算可用路徑Op的失效概率時，運用組合數學中的容斥原理，首先要枚舉源節點v 到目標節點的所有可用路徑Op，然后運用容斥原理進行不交化求解，得到可用路徑Op可靠度Rop＿v，那么Op的失效概率即Pop＿v＝1－Rop＿v。設opi表示節點v 到達目的節點的第i條可用路徑，若節點v到達目的節點有n 條可用路徑，則這n條可用路徑中至少有一條可用的概率為

那么節點v 的可用路徑opv全部失效的概率Pop＿v＝1－Rop＿v。

3 基于故障樹WSN 可靠性結構的BDD 算法

3.1 二元決策圖 （BDD）

BDD 可以實現狀態空間或者變量組合的隱式表示和搜索，減緩或者部分程度上避免狀態空間爆炸問題［8］。

定義9 OBDD：一個有序二叉決策圖 （OBDD）表示一簇從｛0，1｝n到｛0，1｝的布爾函數f（x1，x2，…，xi，…，xn）的有向無環圖，其形式化定義可以用一個八元組來表示［9］：

OBDD ＝（Root，Node，T，var，fu，u.high，u.low，π）。

新的BDD 的生成，通常采用已有的BDD 通過故障樹中的邏輯門如AND，OR，EX－OR 等來進行連接。若給一個給定的故障樹來構造它的BDD，首先要為每個基本事件構建BDD，然后解析連接基本事件的邏輯關系，將已有的BDD 進行連接形成新的組合BDD。這個過程可以用三元邏輯運算工具ite（If－Then－Else）來實現。

定義10 ite：若布爾變量x，y，z 滿足關系式：xy ＋，則定義映射法則ite 使

ite（If－Then－Else）是一個含有3 個布爾變量的操作，描述了布爾變量x 以兩種可能狀態 （可以理解為事件的正常狀態和和故障狀態）傳遞給子節點y 和z。由于BDD 的基本依據是香農分解原理，布爾函數的BDD 表示實質就是一個三元組（xi；fxi＝0；fxi＝1）的遞歸表示，而香農分解原理f＝xi·fxi＝1＋·fxi＝0又可寫成ite操作的形式，即可以將一個布爾函數描述為f ＝ite（xi；fxi＝0；fxi＝1），其中fxi＝0，fxi＝1可以繼續用ite 操作遞歸地分解下去，所以ite 操作也是BDD 的一個基本操作。若知道了兩個BDD 結構，則可以通過下面兩個重要的ite連接規則來將某種邏輯操作下的兩個子BDD 連接起來。

定理1 ite 連接規則：設兩個子BDD 結構分別為M＝ite（xi，A1，A2）和N ＝ite（xj，B1，B2），則

式中： “◇”——任意邏輯運算 （如 “且AND/或OR”）。運用該規則關鍵要判斷兩個子BDD 根節點的排序大小。

3.2 WSN 可靠性結構BDD＿Faulttree算法

本文基于故障樹的WSN 可靠性結構給出BDD＿Faulttree算法，以分層簇拓撲結構下的WSN 可靠性為例分析。該算法分為兩步，首先用遞歸法實現WSN 可靠性結構向BDD 的轉化，然后遍歷BDD 計算WSN 可靠度。本文利用Colorado大學的CUDD 軟件包［10］中ite 操作給出用遞歸方法實現構建WSN 可靠性結構的BDD 算法。此外，將故障樹轉換為BDD 之前，須對基本事件進行排序，本文采用的是深度優先 （DFS）的方式搜索WSN 可靠性結構來確定基本事件的順序。

基于遞歸法的BDD＿Faulttree算法是將基本事件用ite表示，形成一個基本事件的BDD 結構，然后解析最低一層的邏輯門事件，并用ite 的連接規則將每一層邏輯門事件的BDD 結構進行連接，以此類推，由下至上遞歸置換，最后可以得到WSN 可靠性結構的BDD 結構。

WSN 系統的BDD 結構精確地描述了基本事件 （網絡節點的工作狀態）影響頂事件 （WSN 系統）的狀態及路徑。在BDD 中，頂事件的所有從根節點到葉子節點值為“1”，并且不包括葉節點的路徑就是故障樹的不交化割集（MCS）。用深度優先搜索 （DFS）的方法可以找到所有的不交路徑，WSN 系統失效的發生概率就等于BDD 上所有的不交路徑之和。通過深度優先 （DFS）搜索遍歷BDD 求WSN 系統的失效概率，應用下述公式

在構造好的BDD 結構中會存在相同結構的BDD 子圖，因此在遍歷BDD 的過程中，會在這些子圖上重復遍歷并計算可靠性，這樣會造成大量的冗余計算。為此在算法中應用哈希表的結構，把已計算好的下一層子節點上的失效概率值存儲在哈希表中，使算法的時間復雜度降為O（n），提高了算法的效率。

給定F－WSN 算法步驟如下：

（1）定義函數dfstraverse＿Faulttree深度遍歷故障樹確定作為基本事件的節點序列。

（2）根據節點的序列號從根節點開始，初始化故障樹每個節點FaultTree.node［i］的索引號 （作為在BDD 中的標記），子節點個數，操作邏輯，和構建當前節點的孩子節點隊列，若是葉子節點則標記其操作邏輯為－1，如果是非葉子節點則 “OR”操作標記為0， “AND”操作標記為1，定義函數buildFaultTree構建WSN 的故障樹，最后返回故障樹根節點地址。

（3）從故障樹中獲取節點FaultTree.node［i］，定義函數BDD＿Faulttree為將故障樹轉換為BDD 結構，判斷當前節點是否是葉子節點，若是則利用CUDD 包中的Cudd＿bddIthVar函數構造葉子節點的BDD 結構并將該葉子節點的索引號CTree.node［i］.data一起存入所構造的BDD 中，并返回BDD，否則繼續下一步操作。

（4）如果當前節點FaultTree.node［i］操作邏輯為“OR”門，則跳轉到 （3），則繼續訪問該節點的子節點，將返回值存入集合set1，并用ite＿or操作：Cudd＿bddite將set1中的BDD 進行 “or”連接否則繼續下一步操作。

（5）若當前節點操作邏輯為 “AND”門，則跳轉到（3），則繼續訪問該節點的子節點，將返回值存入集合set2，并用ite＿and操作：Cudd＿bddite將set2 中的BDD進行 “and”連接，否則繼續下一步操作。

（6）故障樹的BDD 的地址附給指針變量root，為BDD中節點構造哈希表HashTable并初始化。

（7）定義計算節點失效率函數computeFailureRate，從root開始深度遍歷訪問節點，若當前訪問的是葉子節點為左孩子，則返回1；如果葉子節點為右孩子，則返回0，如果為非葉子節點則繼續下一步。

（8）根據當前節點的地址作為Key在哈希表中查找，若有記錄，則返回哈希表中當前節點的失效概率，否則繼續下一步。

（9）根據下面的公式計算當前節點兩個分支上的失效概率，然后用當前節點的地址作為Key，將失效率存入哈希表中，并返回該節點失效概率。

p ＝p＊computeFailureRate（T，1，failureRateAll）＋（1－p）＊computeFailureRate（E，0，failureRateAll）

偽碼如下：r

4 算法實例

下面以圖5所示的一個簡單例子，構建對應的BDD 結構，并計算網絡失效概率。模型中的頂事件TOP 為WSN失效。分別給它們分配一個序列號：S1，S2，Gw，CH，S3，S4分別對應于x1，x2，x3，x4，x5，x6。在 運 用 遞 歸 法 時，首 先選擇底事件的指標順序，假設所選用的順序是：x1＜x2＜x3＜x4＜x5＜x6，每一層的BDD 構造過程如下：

圖5 WSN 可靠性的一般結構

由頂事件的ite 結構得到的BDD 結構如圖6所示。

圖6 WSN 可靠性結構對應的BDD 結構

深度遍歷BDD 結構求不交化割集為頂事件的所有從根節點到葉子節點值為 “1”，不包括葉節點的路徑，路徑中經過節點的0－分支，則記為，表示基本事件xi沒有發生，實例中的不交割集為：

頂事件WSN 的發生概率等于BDD 上所有的不交路徑之和，網絡失效概率計算如下，Fxi為各個序列號對應節點的失效概率

5 實驗及分析

定量分析分層簇型WSN 可靠性結構上的可靠度，應用上文介紹的BDD＿Faulttree算法假設WSN 有3 個簇，每個簇含有15個S，2個Gw 和1個CH，并假設節點間的通信路徑有一定的路由支持。簇形拓撲的特點在于節點間信息的傳播是多路徑的，從直觀上講，通信節點間不同路徑條數會影響網絡的可靠性，下面的實驗中各節點失效率λ 取在MTTF－2年，假設信息從S節點傳輸到CH，CH 到Gw，以及Gw到處在最高層簇的CH 這些過程中通信節點間都為兩跳，但原節點到目的節點間的可用路徑條數Op不同。Op分別為1條，2條，3條時的網絡失效情況如圖7所示。

圖7 節點間路徑數不同時WSN 失效率

圖7中，可用路徑越多網絡的失效概率就越小。增加節點之間的路徑數能夠有效地降低網絡的失效概率，因為路徑越少，一旦鏈路受阻，就不會有其它的路徑通往目的節點，而簇型網絡的Mesh結構能提供多跳的冗余路徑，因此具有較高的容錯性。若路由節點失效或者是兩個節點之間的鏈路不可用，則網絡自動重新配置失效組件的路徑。由于重新配置路由時會增加節點能量和資源的消耗，從而使系統的開銷增加。

若給節點提供冗余，則選擇給不同類型的節點增設冗余對網絡的可靠性影響是不同的。實驗中選擇一類節點為其增設一個冗余設備 （1r），其它種類的節點不增設，對比網絡整體的失效情況，節點的平均失效時間仍為MTTF－2年，結果如圖8所示。

圖8中，在0 至1000h 內，分別給S 節點，Gw 以及CH 增設一個冗余設備時，網絡的失效情況基本相同。在1000h到2500h之間，為CH 增設冗余設備時，WSN 網絡的失效概率要比另外兩個稍低一些。在2500h以后三者出現了明顯的區別，隨著時間的延長，給S節點增設冗余設備時網絡的失效概率和給CH 節點及Gw 節點增設冗余設

圖8 含有不同冗余節點的WSN 失效概率

備相差越來越大，最大的失效概率相差3倍以上。雖然給S節點增設冗余能夠大幅度地降低網絡的失效概率，但由于S節點數量較多，所以增加冗余設備的代價要比CH 和Gw要大。2500h以后，分別給Gw 和CH 增設冗余的網絡失效情況基本呈平行狀，給S節點增設冗余設備網絡的失效概率最低。

6 結束語

WSN 可靠性分析是WSN 網絡設計、部署、驗證和維護的一個重要環節。本文基于故障樹建立了WSN 可靠性結構，形成對WSN 可靠性問題研究的整體框架的基礎模型。針對WSN 可靠性問題引入BDD 方法，將基于故障樹的可靠性結構轉換為BDD 結構，從而避免一般故障樹分析方法中存在不交化處理過程，進而形成一種新的WSN 可靠性問題研究的思路，文中還給出了利用以上思路計算WSN 應用通信可靠性 （ACR）背景下分層簇型拓撲結構WSN 可靠度的應用。

［1］AboElFotoh H M F，Iyengar S S，Chakrabarty K.Computing reliability and message delay for cooperative wireless distributed sensor networks subject to random failures［J］.IEEE Transactions on Reliability，2005，54 （1）：145－155.

［2］Kim D S，Ghosh R，Trivedi K S.A hierarchical model for reliability analysis of sensor networks ［C］//IEEE 16th Pacific Rim International Symposium on Dependable Computing，2010：247－248.

［3］Bruneo D，Puliafito A，Scarpa M.Dependability analysis of wireless sensor networks with active－sleep cycles and redundant nodes［C］//Proceedings of the First Workshop on Dynamic Aspects in Dependability Models for Fault－Tolerant Systems.ACM，2010：25－30.

［4］Silva I，Guedes L A，Portugal P，et al.Reliability and availability evaluation of wireless sensor networks for industrial applications［J］.Sensors，2012，12 （1）：806－838.

［5］Contini S，Matuzas V.Analysis of large fault trees based on functional decomposition ［J］.Reliability Engineering ＆ System Safety，2011，96 （3）：383－390.

［6］Shrestha A，Xing L.Quantifying application communication reliability of wireless sensor networks［J］.International Journal of Performability Engineering，2008，4 （1）：43－56.

［7］Bruneo D，Puliafito A，Scarpa M.Dependability evaluation of wireless sensor networks：Redundancy and topological aspects［C］//Sensors.IEEE，2010：1827－1831.

［8］Gu T，Xu Z，Yang Z.Symbolic OBDD representations for mechanical assembly sequences ［J］.Computer－Aided Design，2008，40 （4）：411－421.

［9］GU Tianlong，XU Zhoubo.Ordered binary decision diagram and its application ［M］.Beijing：Science Press，2009 （in Chinese）.［古天龍，徐周波.有序二叉決策圖及應用 ［M］.北京：科學出版社，2009.］

［10］Somenzi F.CUDD：CU decision diagram package－release2.5.0［CP/OL］.［2012－02－04］.http：//vlsi.colorado.edu/～fabio/CUDD/cuddIntro.html.