基于BDD的網絡可靠性分析方法研究
發(fā)布時間:2018-02-25 06:07
本文關鍵詞: 網絡可靠性 二元決策圖 性能改進 邊排序 出處:《浙江師范大學》2014年碩士論文 論文類型:學位論文
【摘要】:隨著人類文明的不斷發(fā)展進步,網絡逐漸成為人們生產和生活的重要工具。大數據時代的網絡系統(tǒng)變得極其龐大復雜,因而亟需加強網絡可靠性的建設。 利用二元決策圖(BDD)技術分析網絡可靠性能夠大大提高分析性能和工作效率。該過程主要包含尋找一種性能較好的網絡變量排序、構建與原網絡等價的BDD、計算網絡的可靠度值三個步驟。選擇一種優(yōu)秀的策略對網絡中的邊和節(jié)點進行排序,能夠極大地提升網絡可靠性BDD分析算法的性能。根據既定的變量排序規(guī)則,可以利用網絡分解原理等方法生成與原網絡可靠度等價的BDD。根據生成的BDD計算出每個節(jié)點的可靠度值,并且通過遞歸方法計算出整個BDD的可靠度值。通常對算法的評價主要以時間復雜度和空間復雜度為依據,這兩個復雜度恰好與BDD的路徑長度和節(jié)點數目一一對應。因此在保證所測試信息完整和準確的前提下,對算法進行性能優(yōu)化以及研究變量排序時,應以盡量減小BDD節(jié)點數目和縮短BDD路徑長度為目標。 提高網絡可靠度BDD分析方法的性能是當前研究領域的一個熱點,本文在提高分析性能上做出一些研究,具體工作主要包括: (1)依據Sy-Yen Kuo等提出的利用邊擴展技術的自底向上BDD構建算法,提出算法改進工作,主要從兩個方面著手:第一,提出一種更加簡潔高效的同構子網判別方法——子網“核”方法,可用于判斷在網絡解構過程中產生的子網是否同構。第二,關于冗余消除,提出s-t非連通邊擴展路徑和冗余節(jié)點型邊擴展路徑的概念,并且實現了這兩類無效擴展路徑的消除。 (2)依據Gary Hardy提出的基于邊收縮和邊刪除操作的自頂向下BDD構建算法作出改進。Hardy算法的核心思想是“分區(qū)劃分”,采用邊界分區(qū)Partition標識網絡。Partition不僅可以判斷同構子網,而且對網絡信息的存儲更加簡潔準確。改進Gary Hardy算法的工作主要包括:在“相同邊界分區(qū)的兩個同層子網相同”這一定理的基礎上,實現一種帶冗余消除的自頂向下K端可靠度BDD構建算法。在BDD構建過程中使用哈希操作實現子網共享,大大提升了算法性能。 (3)實現同構識別、冗余消除以及子圖共享等技術之后,BDD構建算法的性能得到較大提升,網絡生成的BDD節(jié)點數目有所減小,但是規(guī)模依然較大由于邊排序的質量極大地影響所構建的BDD節(jié)點數目,并且BDD邊排序問題是一個NP難問題,因此本文第五章基于普通廣度優(yōu)先排序策略研究邊排序問題,討論規(guī)則網絡、最近鄰網絡中的性能最佳排序起點和最差排序起點。研究網絡排序起點對BDD算法的性能影響,為研究啟發(fā)式邊排序提供了重要參考依據。 綜上所述,本文圍繞基于BDD的網絡可靠性分析方法,針對Kuo和Hardy算法作了性能改進工作,并基于廣度優(yōu)先邊排序策略研究排序起點對分析性能的影響,爭取選取最優(yōu)變量排序,創(chuàng)建具有良好時空性的BDD。利用自底向上和自頂向下的算法,提出同構子圖判定、冗余子圖判定及消除方法。從邊排序和冗余子圖消除兩個角度對BDD分析算法進行優(yōu)化,大大提高了網絡可靠性分析方法的性能。
[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.
【學位授予單位】:浙江師范大學
【學位級別】:碩士
【學位授予年份】:2014
【分類號】:TP393.08
【參考文獻】
相關期刊論文 前5條
1 孫艷蕊,張祥德;利用二分決策圖計算網絡可靠度的一個有效算法[J];東北大學學報;1998年05期
2 楊意,潘中良;一種用二元判決圖求網絡可靠度的方法[J];華南師范大學學報(自然科學版);2004年03期
3 李東魁;;網絡系統(tǒng)可靠度的BDD算法[J];通信技術;2009年11期
4 武小悅,張維明,沙基昌;通信網絡可靠性分析的GOOPN模型[J];系統(tǒng)工程與電子技術;2000年03期
5 武小悅,沙基昌;網絡系統(tǒng)可靠度的BDD算法[J];系統(tǒng)工程與電子技術;1999年07期
,本文編號:1533276
本文鏈接:http://www.sikaile.net/guanlilunwen/ydhl/1533276.html
最近更新
教材專著