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

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

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

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

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