本文關(guān)鍵詞： 網(wǎng)絡(luò)可靠性 二元決策圖 性能改進 邊排序　出處：《浙江師范大學(xué)》2014年碩士論文　論文類型：學(xué)位論文

【摘要】：隨著人類文明的不斷發(fā)展進步,網(wǎng)絡(luò)逐漸成為人們生產(chǎn)和生活的重要工具。大數(shù)據(jù)時代的網(wǎng)絡(luò)系統(tǒng)變得極其龐大復(fù)雜,因而亟需加強網(wǎng)絡(luò)可靠性的建設(shè)。 利用二元決策圖(BDD)技術(shù)分析網(wǎng)絡(luò)可靠性能夠大大提高分析性能和工作效率。該過程主要包含尋找一種性能較好的網(wǎng)絡(luò)變量排序、構(gòu)建與原網(wǎng)絡(luò)等價的BDD、計算網(wǎng)絡(luò)的可靠度值三個步驟。選擇一種優(yōu)秀的策略對網(wǎng)絡(luò)中的邊和節(jié)點進行排序,能夠極大地提升網(wǎng)絡(luò)可靠性BDD分析算法的性能。根據(jù)既定的變量排序規(guī)則,可以利用網(wǎng)絡(luò)分解原理等方法生成與原網(wǎng)絡(luò)可靠度等價的BDD。根據(jù)生成的BDD計算出每個節(jié)點的可靠度值,并且通過遞歸方法計算出整個BDD的可靠度值。通常對算法的評價主要以時間復(fù)雜度和空間復(fù)雜度為依據(jù),這兩個復(fù)雜度恰好與BDD的路徑長度和節(jié)點數(shù)目一一對應(yīng)。因此在保證所測試信息完整和準(zhǔn)確的前提下,對算法進行性能優(yōu)化以及研究變量排序時,應(yīng)以盡量減小BDD節(jié)點數(shù)目和縮短BDD路徑長度為目標(biāo)。 提高網(wǎng)絡(luò)可靠度BDD分析方法的性能是當(dāng)前研究領(lǐng)域的一個熱點,本文在提高分析性能上做出一些研究,具體工作主要包括： (1)依據(jù)Sy-Yen Kuo等提出的利用邊擴展技術(shù)的自底向上BDD構(gòu)建算法,提出算法改進工作,主要從兩個方面著手：第一,提出一種更加簡潔高效的同構(gòu)子網(wǎng)判別方法——子網(wǎng)“核”方法,可用于判斷在網(wǎng)絡(luò)解構(gòu)過程中產(chǎn)生的子網(wǎng)是否同構(gòu)。第二,關(guān)于冗余消除,提出s-t非連通邊擴展路徑和冗余節(jié)點型邊擴展路徑的概念,并且實現(xiàn)了這兩類無效擴展路徑的消除。 (2)依據(jù)Gary Hardy提出的基于邊收縮和邊刪除操作的自頂向下BDD構(gòu)建算法作出改進。Hardy算法的核心思想是“分區(qū)劃分”,采用邊界分區(qū)Partition標(biāo)識網(wǎng)絡(luò)。Partition不僅可以判斷同構(gòu)子網(wǎng),而且對網(wǎng)絡(luò)信息的存儲更加簡潔準(zhǔn)確。改進Gary Hardy算法的工作主要包括：在“相同邊界分區(qū)的兩個同層子網(wǎng)相同”這一定理的基礎(chǔ)上,實現(xiàn)一種帶冗余消除的自頂向下K端可靠度BDD構(gòu)建算法。在BDD構(gòu)建過程中使用哈希操作實現(xiàn)子網(wǎng)共享,大大提升了算法性能。 (3)實現(xiàn)同構(gòu)識別、冗余消除以及子圖共享等技術(shù)之后,BDD構(gòu)建算法的性能得到較大提升,網(wǎng)絡(luò)生成的BDD節(jié)點數(shù)目有所減小,但是規(guī)模依然較大由于邊排序的質(zhì)量極大地影響所構(gòu)建的BDD節(jié)點數(shù)目,并且BDD邊排序問題是一個NP難問題,因此本文第五章基于普通廣度優(yōu)先排序策略研究邊排序問題,討論規(guī)則網(wǎng)絡(luò)、最近鄰網(wǎng)絡(luò)中的性能最佳排序起點和最差排序起點。研究網(wǎng)絡(luò)排序起點對BDD算法的性能影響,為研究啟發(fā)式邊排序提供了重要參考依據(jù)。 綜上所述,本文圍繞基于BDD的網(wǎng)絡(luò)可靠性分析方法,針對Kuo和Hardy算法作了性能改進工作,并基于廣度優(yōu)先邊排序策略研究排序起點對分析性能的影響,爭取選取最優(yōu)變量排序,創(chuàng)建具有良好時空性的BDD。利用自底向上和自頂向下的算法,提出同構(gòu)子圖判定、冗余子圖判定及消除方法。從邊排序和冗余子圖消除兩個角度對BDD分析算法進行優(yōu)化,大大提高了網(wǎng)絡(luò)可靠性分析方法的性能。
[Abstract]:With the continuous development and progress of human civilization, network has gradually become an important tool for people's production and life. In the era of big data, network system has become extremely huge and complex. Therefore, it is urgent to strengthen the construction of network reliability.
Using two binary decision diagrams (BDD) analysis technology can greatly improve the work efficiency and performance analysis of network reliability. The process mainly includes looking for a better performance ranking variable of the network construction and network, the original equivalent BDD, computing network reliability value of three steps. Sort the edges and nodes in the network selection a good strategy can greatly improve the reliability of BDD network analysis of the performance of the algorithm. According to the established rules of variable ordering, can use the network decomposition principle and method of generating original network reliability equivalent BDD. based on the BDD to calculate the reliability of the value of each node, and the recursive method to calculate the reliability of the whole BDD the value of the evaluation algorithm. Usually in time and space complexity as the basis, the two complexity coincided with the number of path length and node BDD in correspondence. To ensure that the test information is complete and accurate, we should aim at minimizing the number of BDD nodes and shortening the BDD path length when optimizing the algorithm and sorting variables.
Improving the performance of network reliability BDD analysis is a hot topic in the current research field. This paper makes some researches on improving the performance of analysis.
(1) on the basis of BDD construction algorithm to use Sy-Yen Kuo proposed boundary extension technology from the bottom, put forward improvement algorithm, mainly from two aspects: first, we propose a more efficient method of isomorphic subnets subnet - "nuclear" method, can be used to judge the destructor in the network net isomorphic process. Second, a redundancy elimination, propose S-T non connected edge expansion path and the redundant node type edge expansion path, and the realization of these two kinds of invalid extension path is eliminated.
(2) according to the Gary Hardy proposed BDD top-down edge contraction and edge deletion operation based on Algorithm of improved.Hardy algorithm is the core idea of "zoning", using the boundary partition Partition.Partition identifies the network can not only determine isomorphic sub networks, and the network information storage is more concise and accurate. The improved Gary Hardy algorithm the main work including: Based on "the same boundary partition two with the same sub network" of this theorem, a top-down K eliminate the redundant end reliability BDD construction algorithm. In the process of the construction of BDD using a hash operation for sub network sharing, greatly enhance the performance of the proposed algorithm.
(3) after the implementation of isomorphism identification, and eliminate the redundancy subgraph sharing technology, the performance of BDD construction algorithm is greatly improved, the number of BDD nodes generated decreased, but the scale is still large because BDD nodes greatly influence the edge ranking number, and the edge of the BDD scheduling problem is a NP the difficult problem, so in the fifth chapter, based on the strategy of ordering preferred ordinary depth sorting problem, discuss the rules of network, recently the best performance ranking starting point in the network neighbor and worst ranking starting point. Study the influence of network on the performance of BDD algorithm of sorting starting point, provides an important reference for the research of heuristic edge ranking.
In summary, this paper focuses on the analysis method of network reliability based on BDD, according to Kuo and Hardy algorithm for performance improvement, and based on the breadth first edge effect ranking strategy research on ranking performance analysis of starting point, to select the optimal variable ordering, create a empty BDD. using the bottom-up and top-down algorithm good, put forward subgraph isomorphism judgement, redundant subgraphs judgment and elimination method. From the edge ranking and redundant subgraphs to eliminate the two angles of the BDD analysis algorithm is optimized, greatly improving the performance analysis method of network reliability.

【學(xué)位授予單位】：浙江師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP393.08

【參考文獻】

相關(guān)期刊論文 前5條

1 孫艷蕊,張祥德;利用二分決策圖計算網(wǎng)絡(luò)可靠度的一個有效算法[J];東北大學(xué)學(xué)報;1998年05期

2 楊意,潘中良;一種用二元判決圖求網(wǎng)絡(luò)可靠度的方法[J];華南師范大學(xué)學(xué)報(自然科學(xué)版);2004年03期

3 李東魁;;網(wǎng)絡(luò)系統(tǒng)可靠度的BDD算法[J];通信技術(shù);2009年11期

4 武小悅,張維明,沙基昌;通信網(wǎng)絡(luò)可靠性分析的GOOPN模型[J];系統(tǒng)工程與電子技術(shù);2000年03期

5 武小悅,沙基昌;網(wǎng)絡(luò)系統(tǒng)可靠度的BDD算法[J];系統(tǒng)工程與電子技術(shù);1999年07期

，

本文編號：1533276