本文關鍵詞：網絡可靠性中基于指標的BDD排序策略選擇研究

  更多相關文章： 二元決策圖 網絡可靠性 邊排序 初始點 復雜網絡

【摘要】：隨著科學技術的不斷發(fā)展進步,網絡逐漸成為人們生產和生活的一部分。對網絡的可靠性研究也成為一個熱點問題。在眾多網絡可靠性分析方法中,基于二元決策圖(binary decision diagram, BDD)的分析方法因其高效性常被用來進行網絡可靠性分析。基于BDD的網絡可靠性分析方法包含三個主要步驟,對網絡變量排序、構建與原網絡等價的BDD模型、計算網絡的可靠度值。在進行網絡可靠度計算時,BDD分析方法性能的好壞與BDD模型的尺度直接相關。大尺度的BDD模型會使BDD分析方法的效率降低。因此,在基于BDD的網絡可靠性分析中,使用小尺度的BDD模型進行可靠度計算是非常必要的。在構建等價BDD模型時,首先需要選擇一個啟發(fā)式邊排序策略對網絡變量進行排序。然而,使用不同的啟發(fā)式邊排序策略排序后構造出的BDD模型的尺度可能存在著巨大的差異。而生成小尺度BDD模型的啟發(fā)式邊排序策略其性能較好。因此,如何選擇小尺度的BDD模型進行網絡可靠性計算的問題就等價成了如何尋找高性能啟發(fā)式邊排序策略的問題。在使用啟發(fā)式邊排序策略進行邊排序之前,要先選擇一個排序初始點,而且使用不同的排序初始點排序后生成的BDD模型的尺度也可能存在巨大的差別。因此,如何尋找高性能的排序初始點也同樣重要。本文針對如何選擇高性能的啟發(fā)式邊排序策略和初始點做了一些研究工作,具體內容如下：(1)在如何選擇一個性能較好的啟發(fā)式邊排序策略方面。首先介紹了基于指標TSBS (Total Size of Boundary Set,邊界集之和)的選擇方法,隨后介紹了新的選擇指標Fmax與(Maximum Size of Boundary Sets,邊界集最大值；Index of Fmax,Fmax出現(xiàn)的時機),最后在復雜網絡中比較了兩種選擇指標的性能。發(fā)現(xiàn)大多數情況下,基于指標Fmax與IFmax的選擇方法比基于指標TSBS的性能要好。不過,由于邊排序問題本身就是NP問題,而且復雜網絡又具有小世界性和無標度性,所以也不能保證使用所提出的選擇方法進行網絡可靠性分析時,每次都能得到最優(yōu)的結果,但是大多數情況下會得到較優(yōu)的結果。(2)在如何選擇性能較好的排序初始點問題方面。首先介紹了在規(guī)則網絡中已有的選擇指標TSBS和IFBSH (Index of First Boundary Set Hit,第一次擊中{s,t}的邊界集的索引),隨后在復雜網絡中應用了兩種選擇指標。發(fā)現(xiàn)多數情況下,使用基于指標TSBS的選擇方法就能選出一個性能較好的排序初始點。但是,TSBS值與{s,t)點無關,對于同一網絡、同一邊排序策略和同一初始點,不同的{s,t)點得到的TSBS值相同。而這種情況下,BDD模型的尺度往往不同,此時就要用到基于指標IFBSH的選擇方法。不過,在選擇初始點時,首先選擇使用TSBS作為選擇指標,IFBSH作為輔助。綜上所述,本文研究了在復雜網絡中進行基于BDD的網絡可靠性分析時,如何選擇高性能邊排序策略和初始點的問題。給出了復雜網絡中高性能邊排序策略和初始點的選擇方法,對使用BDD方法進行復雜網絡的可靠性分析具有一定的指導作用。
【關鍵詞】：二元決策圖 網絡可靠性 邊排序 初始點 復雜網絡
【學位授予單位】：浙江師范大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：O157.5
【目錄】：

• 摘要3-5
• ABSTRSCT5-9
• 1 緒論9-17
• 1.1 研究背景和意義9-10
• 1.2 研究現(xiàn)狀10-14
• 1.2.1 網絡可靠性研究現(xiàn)狀10-12
• 1.2.2 排序策略選擇研究現(xiàn)狀12-14
• 1.3 本文主要工作和組織結構14-16
• 1.3.1 本文的主要工作14-15
• 1.3.2 本文的結構安排15-16
• 1.4 本章小結16-17
• 2 排序策略選擇研究基礎17-28
• 2.1 網絡基礎知識17-22
• 2.1.1 規(guī)則網絡模型18-19
• 2.1.2 隨機網絡模型19
• 2.1.3 復雜網絡模型19-22
• 2.2 BDD相關知識22-24
• 2.3 邊界集BS(Boundary Set)24-25
• 2.4 啟發(fā)式邊排序策略25-27
• 2.4.1 DFS25
• 2.4.2 BFS25-26
• 2.4.3 NDS26-27
• 2.5 本章小結27-28
• 3 邊排序策略選擇方法28-43
• 3.1 基于TSBS的選擇方法28-29
• 3.2 基于~(F_(max))與~(IF_(max))的選擇方法29-30
• 3.3 指標性能分析與比較30-42
• 3.3.1 基于波士頓交通網的性能分析和比較30-34
• 3.3.2 基于美國佛羅里達州電力網的性能分析和比較34-38
• 3.3.3 基于貴州省電力網的性能分析和比較38-42
• 3.4 本章小結42-43
• 4 初始點選擇方法43-51
• 4.1 基于TSBS的選擇方法43-47
• 4.1.1 基于TSBS的初始點選擇方法43-44
• 4.1.2 應用性能分析44-47
• 4.1.2.1 基于美國波士頓交通網的性能分析44-46
• 4.1.2.2 基于貴州省電力網的性能分析46-47
• 4.2 基于IFBSH的選擇方法47-50
• 4.2.1 基于IFBSH的初始點選擇方法47-48
• 4.2.2 應用性能分析48-50
• 4.3 本章小結50-51
• 5 工作總結與展望51-53
• 5.1 工作總結51-52
• 5.2 工作展望52-53
• 參考文獻53-59
• 攻讀學位期間取得的研究成果59-60
• 致謝60-62

【相似文獻】

中國期刊全文數據庫 前3條

1 曾令國;莫毓昌;;PMS故障樹分析中的變量排序策略庫研究[J];計算機工程;2011年20期

2 潘竹生;莫毓昌;趙建民;;網絡可靠度BDD分析中2種邊排序策略的性能比較[J];浙江師范大學學報(自然科學版);2013年01期

3 ;[J];;年期

中國碩士學位論文全文數據庫 前4條

1 伍歡;基于BDD的網絡可靠性分析中邊排序策略研究[D];浙江師范大學;2015年

2 付玉書;網絡可靠性中基于指標的BDD排序策略選擇研究[D];浙江師范大學;2016年

3 王中鋒;多Agent英式序貫拍賣排序策略研究[D];鄭州大學;2007年

4 曲克偉;基于熱點話題發(fā)現(xiàn)的BBS檢索排序策略研究[D];北京郵電大學;2013年

，

本文編號：968744