基于邊擴展圖的網(wǎng)絡(luò)可靠度近似分析.pdf

1、隨著網(wǎng)絡(luò)建設(shè)規(guī)模的不斷增大，各行各業(yè)對其網(wǎng)絡(luò)可靠性的要求也在不斷的提高。網(wǎng)絡(luò)可靠性作為網(wǎng)絡(luò)建設(shè)的一項重要指標，時刻影響著其布局與規(guī)劃。如何快速、精確地計算網(wǎng)絡(luò)可靠性，始終是可信計算領(lǐng)域里的一個核心問題。
　　在網(wǎng)絡(luò)可靠性分析中，使用邊擴展圖(edge expansion diagram,EED)技術(shù)能夠在很大程度上提高性能和效率。該過程主要包含邊排序、構(gòu)建邊擴展圖、生成等價的BDD（binary decision diagram）

2、并計算網(wǎng)絡(luò)的可靠度值三個步驟。具體的，首先依據(jù)BFS(breadth-first search)邊排序策略對網(wǎng)絡(luò)的邊進行排序;然后根據(jù)邊擴展圖技術(shù)對網(wǎng)絡(luò)構(gòu)建相應的邊擴展圖;進而生成相應的BDD，并對每個節(jié)點進行可靠度的計算，最后遞歸地求出總的可靠度值。小規(guī)模的網(wǎng)絡(luò)可以快速計算出可靠度精確值，但隨著網(wǎng)絡(luò)規(guī)模的增大，可靠性精確值的計算非常困難甚至難以得出，從而研究者們提出了網(wǎng)絡(luò)可靠度的近似分析這一方法。已有的網(wǎng)絡(luò)可靠性近似分析中，多是基于割

3、集或者路集，本文從另一個方面---基于截斷邊擴展圖著手。
　　本文的主要工作是對網(wǎng)絡(luò)進行可靠度的近似分析，采用的方法是截斷邊擴展圖，其主要內(nèi)容包括:
　　在Kuo算法基礎(chǔ)上提出截斷邊擴展圖的網(wǎng)絡(luò)可靠度近似算法。Kuo算法的步驟包括邊排序，邊擴展圖的生成，BDD的生成和可靠度的計算。本文的近似算法是根據(jù)給定的閾值對邊擴展圖進行截斷，然后生成等價的BDD，最后計算可靠度的值。并選取多種規(guī)則網(wǎng)絡(luò)為模型進行性能分析，進一步與已存在的

4、近似算法進行性能比較，得出該算法可以使得BDD尺度大幅度減小，并且可靠度值的誤差維持在一定范圍內(nèi)這一結(jié)論，這為工程網(wǎng)絡(luò)的可靠度近似分析奠定了基礎(chǔ)。
　　將基于截斷邊擴展圖的網(wǎng)絡(luò)可靠度近似算法應用于工程網(wǎng)絡(luò)中。選取北京軌道交通網(wǎng)、河南電力網(wǎng)及社交網(wǎng)絡(luò)三個工程網(wǎng)絡(luò)為模型，對每一個網(wǎng)絡(luò)模型，針對不同的{s，t}，記錄可靠性分析過程中的實驗參數(shù)，包括可靠度的精確值和近似值、BDD尺度以及誤差大小，并與Kuo算法進行比較，大量的實驗結(jié)果驗證