邊排序質(zhì)量影響因素研究＊

潘竹生，莫毓昌

（浙江師范大學數(shù)理與信息工程學院，浙江 金華321004）

1 引言

可靠性是電力網(wǎng)、給水網(wǎng)、交通網(wǎng)和通信網(wǎng)等生命系統(tǒng)網(wǎng)絡的重要特性，最近三十年來展開了廣泛 研 究，其 中 基 于BDD（Binary Decision Diagram）［1，2］的網(wǎng)絡可靠性分析方法成為研究熱點。網(wǎng)絡可靠度BDD 分析方法包含邊排序、等價BDD生成和可靠度計算三個基本過程，其中生成緊湊的等價BDD 為核心。文獻［3］介紹了BDD 在雙端網(wǎng)絡可靠度計算中的具體實現(xiàn)，為BDD 在網(wǎng)絡可靠性計算中的應用奠定了基礎。Kuo S Y［4～6］基于邊擴展技術提出了自底向上的二端可靠度和K 端可靠度BDD 分析算法，利用邊擴展EP（Edge expansion）技術有效識別同構子圖，進而構建等價BDD，為大型網(wǎng)絡可靠度的計算奠定了基礎。Hardy G［7，8］提出了自頂向下的全端可靠度和K端可靠度BDD 分析算法，該算法利用分區(qū)等價類有效識別同構子網(wǎng)，較Kuo S Y［4～6］算法更為有效，能計算更大規(guī)模網(wǎng)絡可靠度。Herrmann J U［9～11］針對Hardy G［7，8］算法中需要存儲大量BDD 節(jié)點而無法適用更大規(guī)模網(wǎng)絡的不足，提出了一階段完成的OBDD－A 算法，不再事先構建完整BDD，而是邊構造邊計算可靠度值。Kuo S Y 和Hardy G 算法利用邊擴展技術或分區(qū)等價類技術，高效識別同構子網(wǎng)，從而構造緊湊BDD。Herrmann J U 利用OBDD 本身特性，邊構造邊計算可靠度值，只保留必要的BDD 節(jié)點，從而節(jié)省存儲空間，適用更大規(guī)模的網(wǎng)絡可靠度計算，但該算法無法得到完整緊湊的BDD。以上算法從BDD 構建角度，較好地解決了存儲空間問題，然而，BDD 所占存儲空間還嚴重依賴邊排序質(zhì)量［12］，高質(zhì)量的邊排序指導生成最簡的BDD。在相同的構建方法下，不同質(zhì)量的邊排序?qū)е翨DD尺度（節(jié)點數(shù)目）變化跨越幾個數(shù)量級［14］。

然而，尋找最優(yōu)邊排序問題已被證明是一個NP完全問題［13，14］，在已有研究中以Friedman S J等［12，15］提出的最優(yōu)排序算法性能最好，時間復雜度為O（n2·3n）。在實際的網(wǎng)絡可靠性分析中，大多采 用 啟 發(fā) 性 策 略［4～11，16～19］，如 廣 度 優(yōu) 先 遍 歷BFS（Breadth－First－Search）和深度優(yōu)先遍歷DFS（Depth－First－Search）。文獻［5，8，20］用實驗數(shù)據(jù)驗證了“規(guī)則網(wǎng)絡中BFS 策略優(yōu)于DFS 策略”。那么，在其他類型的網(wǎng)絡中，BFS策略是否依然優(yōu)于DFS策略？如果是，指標數(shù)據(jù)是什么？根據(jù)該指標是否能找到更優(yōu)的邊排序策略？

本文利用邊界集（Boundary Set）思想，提出“邊界長度BSL（Boudary Set Length）”概念，并用邊界長度BSL 刻畫邊排序質(zhì)量指標，從實驗角度揭示邊界長度BSL 和BDD 尺度（節(jié)點數(shù)目）之間的依賴關系，為邊排序質(zhì)量的判定提供重要依據(jù)。

2 邊排序和邊界集

定義1 三元組G＝（V，E，K）稱為一個K端網(wǎng)絡，其中：

（1）V＝｛V1，V2，…，Vn｝，稱為頂點集；

（2）E?V×V，稱為邊集；

（3）K?V，稱為K點集。

為了便于描述，對于E中的點對〈a，b〉，a，b∈V，通常賦予另一個名稱ei。

圖1中的K端網(wǎng)絡G對應的三元組為（｛0，1，2，3，4，5，6｝，｛e1，e2，e3，e4，e5，e6，e7，e8，e9，e10｝，｛0，3，6｝）。

Figure 1 Network 1and edge ordering圖1 網(wǎng)絡1和邊排序

定義2 三元組G的邊排序Order是E至整數(shù)集合｛1，2，…，｜E｜｝上的一一對應函數(shù)，Order：E→｛1，2，…，｜E｜｝。

根據(jù)定義可知，G的邊排序可以有｜E｜！種不同的可能。通常獲得邊排序的方法有BFS和DFS。

圖1中的K端網(wǎng)絡G，以節(jié)點“0”為排序起點，則對應的一種廣度優(yōu)先排序Order為：〈e1，e2，e3，e4，e5，e6，e7，e8，e9，e10〉。

圖1中的K端網(wǎng)絡G，以節(jié)點“0”為排序起點，則對應的一種深度優(yōu)先排序Order為：〈e1，e4，e8，e6，e2，e5，e3，e7，e10，e9〉。

定義3 給定K端網(wǎng)絡G＝（V，E，K），定義第k（0≤k≤｜E｜）層邊界集，F(xiàn)k：

圖1所示網(wǎng)絡，約定邊排序為e1＜e2＜…＜e10，則各層邊界集如表1所示。

Table1 Boundary sets of the Network 1表1 網(wǎng)絡1各層邊界集

定義4 給定K端網(wǎng)絡G＝（V，E，K）和邊排序Order，定義邊界長度BSL：

圖1 所示網(wǎng)絡，約定邊排序為e1＜e2＜…＜e10，則BSL＝0＋2＋3＋3＋3＋3＋3＋3＋3＋2＋0＝25。

3 相同策略下BSL與BDD尺度相關

選擇經(jīng)典的DFS和BFS啟發(fā)性邊排序策略，在Square Lattice、Torus Lattice、DeBruijn 和NearestNeighbor規(guī)則網(wǎng)絡中，求解二端網(wǎng)絡連通可靠度，考察BSL和BDD 尺度之間的關系。實驗過程為：生成規(guī)則網(wǎng)絡，指定｛s，t｝點對；根據(jù)不同排序起點完成邊排序，生成等價BDD，計算指定｛s，t｝點對的可靠度值，記錄BDD 尺度（節(jié)點數(shù)目）和BSL，實驗結果如表2 和表3 所示。統(tǒng)計取最小BSL時對應的BDD 尺度在結果集中的位序（取前三），統(tǒng)計取最大BSL時對應的BDD尺度在結果集中的位序（取后三），實驗結果如表4和表5所示。

Table 2 Results for（s，t）＝（0，15）in 4×4Square Lattice networks表2 4×4Square Lattice network 實驗結果（s，t）＝（0，15）

Tables 3 Results for（s，t）＝（0，9）in the nearest neighbor networks（nodes＝10degree＝6）表3 Nearest neighbor network（10節(jié)點6度）實驗結果（s，t）＝（0，9）

Table 4 Relationship between BSLvalues and BDD sizes for DFS表4 DFS策略下BSL 與BDD尺度之間的關系

Table 5 Relationship between BSLvalues and BDD sizes for BFS表5 BFS策略下BSL 與BDD尺度之間的關系

表2 和 表3 中，“StartNode”表 示 排 序 起 點，“BDDSize”表 示BDD 節(jié) 點 數(shù) 目（尺 度），“BDDOrder”表示按BDDsize由小到大排序后得到的序號，“BSLOrder”表示按BSL由小到大排序后得到的序號。由表1 數(shù)據(jù)可得：對于Square Lattice網(wǎng)絡，在相同策略下，BSL較大時，對應的BDDSize較大；當BSL最大時，對應的BDDSize最大；BSL較小時，對應的BDDSize較?。划擝SL最小時，對應的BDDSize最小，如圖2所示。由表3數(shù)據(jù)可得：對于Nearest Neighbor網(wǎng)絡，在BFS策略下，結論與Square Lattice網(wǎng)絡相同；在DFS策略下，結論不明顯。

Figure 2 Correlation distribution of BSLOrderand BDDOrder圖2 BSLOrder 與BDDOrder 序號相關性分布

表4和表5數(shù)據(jù)為相關網(wǎng)絡考慮所有｛s，t｝點對時的統(tǒng)計結果。其中，Best表示“在BSL最小時，對應的BDDSize也最小”的出現(xiàn)次數(shù)；Worst表示“在BSL最大時，對應的BDDSize也最大”的出現(xiàn)次數(shù)；Ratio＿B表示“BSL最小時，對應的BDDSize取前三小”的占比；Ratio＿W表示“BSL最大時，對應的BDDSize取后三大”的占比。顯然，在給定的四類網(wǎng)絡中，邊界集長度和BDDSize保持了相似的關系。由此得到結論：

結論1 相同策略下，取較小BSL，可以獲得較小BDD 尺度；反之，取較大BSL時，所得BDD尺度較大；一般情況下，BSL取最值時，BDD 尺度可以取到最值（或接近最值）。

4 不同策略下BSL 與BDD 尺度相關性

為了更好地進行比較研究，引入FGS（Fastest－Growth－Strategy）邊排序。該策略對前｜V｜/2條邊排序時，每排一條邊，BSL增加2；之后，BSL保持不變或減小，直到所有邊被排序。實驗過程為：在Square Lattice、Torus Lattice、DeBruijn 和NearestNeighbor規(guī)則網(wǎng)絡中，隨機選擇｛s，t｝點對，在不同的邊排序策略下（僅僅策略不同），生成等價BDD，記錄BDD 尺度（節(jié)點數(shù)目）和BSL如表6～表9所示。

Table 6 Relationship between BSL values and BDD sizes in the 4×4square lattice networks表6 4×4Square Lattice BSL與BDD尺度之間的關系

Table 7 Relationship between BSLvalues and BDD sizes in 4×4Torus Lattice networks表7 4×4Torus Lattice BSL 與BDD尺度之間的關系

Table 8 Relationship between BSLvalues and BDD sizes in DeBruijn（Order＝4）表8 DeBruijn（4Order）BSL 與BDD尺度之間的關系

Table 9 Relationship between BSLvalues and BDD sizes in the Nearest Neighbor networks（nodes＝10，degree＝8）表9 Nearest Neighbor network（Nodes＝10，Degree＝8）BSL 與BDD尺度之間的關系

分析表6中數(shù)據(jù)得圖3和圖4。圖3中不同策略在相同｛s，t｝點對時有不同BSL，其中，F(xiàn)GS對應的BSL最 大，DFS 次 之，BFS 最 小。圖4 中不同策略在相同｛s，t｝點對時有不同BDD 尺度，除｛5，9｝點對外，保持了與BSL相同（或相似）的變化特性。聯(lián)合圖3和圖4可得，BDD 尺度與BSL有緊密相關性。

表7～表9 中，ΔBDD1 表 示FGS 和DFS 下BDD 尺度的縮減比，ΔBDD2表示DFS和BFS下BDD 尺 度 的 縮 減 比，ΔBS1 表 示FGS 和DFS 下BSL的縮減比，ΔBS2表示DFS和BFS下BSL的縮減比。由統(tǒng)計結果可得：對于Torus Lattice，比較FGS和DFS，BSL縮減36%以上，對應的BDD尺度縮減9.3%（如｛2，9｝點對）到59.9%（如｛5，10｝點對）不等；比較DFS 和BFS，BSL縮減16%以上，對應的BDD 尺度縮減65%以上；對于De－Bruijn網(wǎng)絡如表7 所示，一般情況下，BSL減小時，BDD 尺 度 也 減 小，BSL增 大 時，BDD 尺 度 增大，｛4，13｝點對除外；對于Nearest Neighbor網(wǎng)絡如表8 所示，與Torus Lattice網(wǎng)絡有相似特性?？偨Y四種不同類型的規(guī)則網(wǎng)絡，可得結論2。

Figure 3 Graphic representation of the BSLvalues in 4×4square Lattice networks圖3 4×4Square Lattice BSL 變化

Figure 4 Graphic representation of the BDD sizes in 4×4square Lattice networks圖4 4×4Square Lattice中BDD 尺度變化

結論2 不同策略下，BSL較小時，對應的BDD 尺度較小；反之，BSL較大時，對應的BDD 尺度較大；BSL與BDD 尺度保持穩(wěn)定（或基本穩(wěn)定）的正相關性。

5 應用

為了更好地驗證以上結論，設計一種新的邊排序策略（記為BSMFS），該策略的核心思想為最小邊界長度優(yōu)先，即邊排序過程中盡可能保持最小邊界長度。驗證在獲得更小BSL時，對應的BDD 尺度是否更小。首先在Square Lattice網(wǎng)絡中，隨機選擇｛s，t｝點對，在不同的邊排序策略下，生成等價BDD，記錄BDD 尺度（節(jié)點數(shù)目）和BSL，實驗結果如表10所示。

分析表6 和表10 中數(shù)據(jù)，比較BSMFS 策略和BFS策略所對應的BSL和BDD 尺度，除了｛2，6｝點對在BSL減小時BDD 尺度有所增加外，其余所 有 點 對 隨 著BSL減 小，BDD 尺 度 減 ?。籅SL不變，BDD 尺度保持不變，保持上述結論。進一步地，在實際工程網(wǎng)絡（Net1為土耳其Bursa市水網(wǎng)示意模型［20］，Net2為生命線網(wǎng)絡模型［21］，Net3為日本Kobe市的供水網(wǎng)絡［22］）中，隨機選擇｛s，t｝點對，在不同的邊排序策略下，生成等價BDD，記錄BDD節(jié)點數(shù)目（尺度）和BSL，實驗結果如表11所示。

分析表11中數(shù)據(jù)得圖5和圖6。圖5為工程網(wǎng)絡中，相同｛s，t｝點對時不同邊排序策略下不同的BSL分布，由圖可得FGS 對應的BSL最大，BSMFS對 應 的BSL最 小，DFS 和BFS 對 應 的BSL接近且交錯分布。圖6為相同｛s，t｝點對時不同邊排序策略下不同的BDD 尺度分布，一般情況下，F(xiàn)GS 對 應 的BDD 尺 度 較 大，BSMFS 對 應 的BDD 尺度較小，DFS和BFS對應的BDD尺度接近且分布有所交錯。比較策略FGS和BSMFS，BSL較大時，得到較大BDD 尺度，BSL較小時，BDD 尺度較小，BSL和BDD 尺度有相似的變化曲線。比較DFS和BFS，在隨機得到的12組｛s，t｝點對中，有9 組 保 持“BSL小，對 應 的BDD 尺 度 ?。籅SL大，對應的BDD 尺度大”相關性，占75%；點對｛2，5｝，BSL和BDD 尺度都非常接近；另外2組如｛3，4｝｛4，10｝，BSL接近，但BSL較大時BDD 尺度反而小。

Table 10 Results of BSMFS in 4×4Square networks表10 BSMFS策略在Square Lattice中的指標數(shù)據(jù)

Table 11 Results of BSMFS in practical networks表11 BSMFS策略在實際工程網(wǎng)絡中的指標數(shù)據(jù)

Figure 5 Graphic representation of the BSL values in engineering network圖5 工程網(wǎng)絡中BSL 尺度變化

Figure 6 Graphic representation of the BDD sizes in engineering network圖6 工程網(wǎng)絡中BDD 尺度變化

6 結束語

本文用邊界長度BSL刻畫邊排序質(zhì)量，在規(guī)則網(wǎng)絡中研究了邊界長度BSL與BDD 尺度之間的關系，得出“邊界長度BSL與BDD 尺度具有正相關性”，即較小BSL對應的BDD 尺度較小，較大BSL對應的BDD 尺度較大，多數(shù)情況下，BSL取最值時，BDD 尺度能取到（或接近）最值。并以此為依據(jù)設計新策略最小邊界長度優(yōu)先BSMFS，在規(guī)則網(wǎng)絡和工程網(wǎng)絡中的進一步實驗表明，邊界長度BSL指標數(shù)據(jù)，能從宏觀角度刻畫邊排序質(zhì)量，這為特定網(wǎng)絡選擇（或設計）高性能邊排序提供了重要的參考依據(jù)。下一步研究工作：（1）尋找其他指標數(shù)據(jù)，從微觀角度進一步刻畫邊排序質(zhì)量；（2）圍繞新的指標數(shù)據(jù)，設計更優(yōu)邊排序策略。

［1］ Akers B.Binary decision diagrams［J］.IEEE Transactions on Computers，1978，C－27（6）：509－516.

［2］ Bryant R E.Symbolic boolean manipulation with ordered binary－decision diagrams［J］.ACM Computing Surveys，1992，24（3）：293－318.

［3］ Singh H，Vaithilingam S，Anne R K.Terminal reliability using binary decision diagrams［J］.Microelectronics Reliability，1996，36（3）：363－365.

［4］ Yeh F M，Kuo S Y.OBDD－based network reliability calculation［J］.Electronics Letters，1997，33（9）：759－760.

［5］ Kuo S Y，Lu S K，Yeh F M.Determining terminal－pair network reliability based on edge expansion diagrams using OBDD［J］.IEEE Transactions on Reliability，1999，48（3）：234－246.

［6］ Yeh F M，Lu S K，Kuo S Y.OBDD－based evaluation ofk－terminal network reliability［J］.IEEE Transactions on Reliability，2002，R－51（4）：443－451.

［7］ Hardy G，Lucet C，Limnios N.Computing all－terminal reliability of stochastic networks with binary decision diagrams［C］∥Proc of the 11th International Symposium on Applied Stochastic Models and Data Analysis，2005：1468－1474.

［8］ Hardy G，Lucet C，Limnios N.K－terminal network reliability measures with binary decision diagrams［J］.IEEE Transactions on Reliability，2007，56（3）：506－515.

［9］ Herrmann J U，Soh S.A space efficient algorithm for network reliability［C］∥Proc of the 15th Asia－Pacific Conference on Communications（APCC2009）：2009：703－707.

［10］ Herrmann J U.Improving reliability calculation with augmented binary decision diagrams［C］∥Proc of IEEE Advanced Information Networking and Applications（AINA2012），2010：329－333.

［11］ Herrmann J U，Soh S.Comparison of binary and multi－variate hybrid decision diagram algorithms forK－terminal reliability［C］∥Proc of the 34th Australasian ComputerScience Conference（ACSC2010），2010：113.

［12］ Sieling D，Wegener I.Reduction of OBDDs in linear time［J］.Information Processing Letters，1993（48）：139－144.

［13］ Garey M R，Johnson D S.Computers and Intractibility：A guide to the theory of NP－completeness［M］.［S.L.］W.H.Preeman＆Co.Ltd，1979.

［14］ Bollig B，Wegener I.Improving the variable ordering of OBDDs is NP－complete［J］.IEEE Transactions on Computers，1996，45（9）：993－1002.

［15］ Friedman S J，Supowit K J.Finding the optimal variable ordering for binary decision diagrams［J］.IEEE Transactions on Computer，1990，C－39（5）：710－713.

［16］ Dutuit Y，Rauzy A，Signoret J P.Computing network reliability with reseda and aralia［C］∥Proc of ESREL’96，1996：24－28.

［17］ Pan Zhu－sheng，Mo Yu－chang，Zhao Jian－min.Comparison of two ordering edge heuristics used in BDD－based network reliability analysis［J］.Journal of Zhejiang Normal University（Natural Sciences），2013，36（1）：88－95.（in Chinese）

［18］ Pan Zhu－sheng，Mo Yu－chang，Xing Liu－dong，et al.New insights into breadth－first search edge ordering of regular networks for terminal－pair reliability analysis［J］.Journal of Risk and Reliability，2014，228（1）：83－92.

［19］ Pan Zhu－sheng，Mo Yu－chang，Zhong Fa－rong.A novel heuristic edge ordering strategy and its performance analysis［J］.Computer Engineering ＆Science，2014，36（11）：2119－2127.（in Chinese）

［20］ Sel?uk A S，Yücemen M S.Reliability of lifeline networks with multiple sources under seismic hazard［J］.Natural Hazards，2000，21（1）：1－18.

［21］ Ching J，Hsu W C.An efficient method for evaluating origin－destination connectivity reliability of real－world lifeline networks［J］.Computer－Aided Civil and Infrastructure Engineering，2007，22（8）：584－596.

［22］ Javanbarg M B，Takada S.Redundancy model for water supply systems under earthquake environments［C］∥Proc of the 5th International Conference on Seismology and Earthquake Engineering，2007：1.

附中文參考文獻：

［17］ 潘竹生，莫毓昌，趙建民.網(wǎng)絡可靠性分析中兩種邊排序策略的性能比較［J］.浙江師范大學學報（自然科學版），2013，36（1）：88－95.

［19］ 潘竹生，莫毓昌，鐘發(fā)榮.一種新的啟發(fā)式邊排序策略及其性能分析［J］.計算機工程與科學，2014，36（11）：2119－2127.