網(wǎng)絡(luò)可靠性中基于指標(biāo)的BDD排序策略選擇研究.pdf

1、隨著科學(xué)技術(shù)的不斷發(fā)展進步，網(wǎng)絡(luò)逐漸成為人們生產(chǎn)和生活的一部分。對網(wǎng)絡(luò)的可靠性研究也成為一個熱點問題。在眾多網(wǎng)絡(luò)可靠性分析方法中，基于二元決策圖（binary decision diagram，BDD）的分析方法因其高效性常被用來進行網(wǎng)絡(luò)可靠性分析?；贐DD的網(wǎng)絡(luò)可靠性分析方法包含三個主要步驟，對網(wǎng)絡(luò)變量排序、構(gòu)建與原網(wǎng)絡(luò)等價的BDD模型、計算網(wǎng)絡(luò)的可靠度值。在進行網(wǎng)絡(luò)可靠度計算時，BDD分析方法性能的好壞與BDD模型的尺度直接相關(guān)。

2、大尺度的BDD模型會使BDD分析方法的效率降低。因此，在基于BDD的網(wǎng)絡(luò)可靠性分析中，使用小尺度的BDD模型進行可靠度計算是非常必要的。
　　在構(gòu)建等價BDD模型時，首先需要選擇一個啟發(fā)式邊排序策略對網(wǎng)絡(luò)變量進行排序。然而，使用不同的啟發(fā)式邊排序策略排序后構(gòu)造出的BDD模型的尺度可能存在著巨大的差異。而生成小尺度BDD模型的啟發(fā)式邊排序策略其性能較好。因此，如何選擇小尺度的BDD模型進行網(wǎng)絡(luò)可靠性計算的問題就等價成了如何尋找高性能

3、啟發(fā)式邊排序策略的問題。在使用啟發(fā)式邊排序策略進行邊排序之前，要先選擇一個排序初始點，而且使用不同的排序初始點排序后生成的BDD模型的尺度也可能存在巨大的差別。因此，如何尋找高性能的排序初始點也同樣重要。
　　本文針對如何選擇高性能的啟發(fā)式邊排序策略和初始點做了一些研究工作，具體內(nèi)容如下:
　　(1)在如何選擇一個性能較好的啟發(fā)式邊排序策略方面。首先介紹了基于指標(biāo)TSBS（Total Size of Boundary Set

4、，邊界集之和）的選擇方法，隨后介紹了新的選擇指標(biāo)Fmax與IFmax（Maximum Size of Boundary Sets，邊界集最大值;Index of Fmax，F(xiàn)max出現(xiàn)的時機），最后在復(fù)雜網(wǎng)絡(luò)中比較了兩種選擇指標(biāo)的性能。發(fā)現(xiàn)大多數(shù)情況下，基于指標(biāo)Fmax與IFmax的選擇方法比基于指標(biāo)TSBS的性能要好。不過，由于邊排序問題本身就是NP問題，而且復(fù)雜網(wǎng)絡(luò)又具有小世界性和無標(biāo)度性，所以也不能保證使用所提出的選擇方法進行網(wǎng)絡(luò)

5、可靠性分析時，每次都能得到最優(yōu)的結(jié)果，但是大多數(shù)情況下會得到較優(yōu)的結(jié)果。
　　(2)在如何選擇性能較好的排序初始點問題方面。首先介紹了在規(guī)則網(wǎng)絡(luò)中已有的選擇指標(biāo)TSBS和IFBSH（Index of First Boundary Set Hit，第一次擊中{s，t}的邊界集的索引），隨后在復(fù)雜網(wǎng)絡(luò)中應(yīng)用了兩種選擇指標(biāo)。發(fā)現(xiàn)多數(shù)情況下，使用基于指標(biāo)TSBS的選擇方法就能選出一個性能較好的排序初始點。但是，TSBS值與{s，t}點無關(guān)

6、，對于同一網(wǎng)絡(luò)、同一邊排序策略和同一初始點，不同的{s，t}點得到的TSBS值相同。而這種情況下，BDD模型的尺度往往不同，此時就要用到基于指標(biāo)IFBSH的選擇方法。不過，在選擇初始點時，首先選擇使用TSBS作為選擇指標(biāo)，IFBSH作為輔助。
　　綜上所述，本文研究了在復(fù)雜網(wǎng)絡(luò)中進行基于BDD的網(wǎng)絡(luò)可靠性分析時，如何選擇高性能邊排序策略和初始點的問題。給出了復(fù)雜網(wǎng)絡(luò)中高性能邊排序策略和初始點的選擇方法，對使用BDD方法進行復(fù)雜網(wǎng)絡(luò)