工程網(wǎng)絡(luò)可靠性BDD分析中排序初始點的研究.pdf

1、在科學(xué)技術(shù)日新月異的今天，人類的發(fā)展進(jìn)程正在大跨步前進(jìn)。與此同時，世界范圍內(nèi)生產(chǎn)生活的舉動也在隨著科技的進(jìn)步而加快頻率。伴隨著全球生產(chǎn)力的提升，人類的交流活動以及各系統(tǒng)性工程都在以一個個網(wǎng)絡(luò)的形式急速運(yùn)行著，因此對于各種網(wǎng)絡(luò)的可靠性分析對于當(dāng)今人類的生活有發(fā)展有著重要的意義。
　　對于網(wǎng)絡(luò)的可靠性研究目前是一個熱點。二分決策圖技術(shù)(BDD)就是研究方法中非常著名的一種。該分析方法的操作過程是首先對于網(wǎng)絡(luò)中的變量進(jìn)行邊排序，然后生成

2、等價BDD，最后對生成的BDD進(jìn)行可靠度的計算。在使用BDD分析方法進(jìn)行網(wǎng)絡(luò)進(jìn)行可靠度計算時，計算過程的工作效率與生成的等價BDD規(guī)模直接相關(guān)。大規(guī)模的BDD會導(dǎo)致計算效率降低，時效性很差。因此使用與原網(wǎng)絡(luò)等價的小規(guī)模的BDD進(jìn)行計算，在網(wǎng)絡(luò)可靠性分析工作中是非常有必要的。在生成等價BDD時，我們總需要選擇一個邊排序初始點。不同的邊排序初始點排序后生成的BDD規(guī)?？赡艽嬖诰薮蟮牟顒e，生成BDD的規(guī)模越小的邊排序初始點其性能越好。因此，如

3、何選擇規(guī)模小的BDD進(jìn)行網(wǎng)絡(luò)可靠性計算問題就等價為了如何找出高性能的邊排序初始點以得到規(guī)模小的等價BDD問題。
　　在目前的網(wǎng)絡(luò)可靠性BDD計算中，提升算法的計算效率非常重要。本文針對與計算效率直接相關(guān)的高性能的邊排序初始點做了一些研究工作，具體的內(nèi)容如下所述:
　　(1)對于不同的工程網(wǎng)絡(luò)，以及不同的K節(jié)點子集，將網(wǎng)絡(luò)中所有的節(jié)點作為邊排序初始點生成BDD。研究高性能的邊排序初始點的變化情況與其分布特征。在不同的K節(jié)點子集

4、情況下，高性能邊排序初始點始終保持不變，得出結(jié)論一:高性能邊排序初始點自身具有穩(wěn)定性。并且在將高性能邊排序初始點標(biāo)注在網(wǎng)絡(luò)分區(qū)中時，這些節(jié)點都落在一個分區(qū)內(nèi)，得出結(jié)論二:高性能邊排序初始點具有匯聚性。
　　(2)提出工程網(wǎng)絡(luò)中高性能邊排序初始點的選擇方法。首先基于網(wǎng)絡(luò)中節(jié)點介數(shù)進(jìn)行網(wǎng)絡(luò)分區(qū)操作，在此給出了劃分點的定義和選取規(guī)則;然后在所得不同網(wǎng)絡(luò)分區(qū)中選擇節(jié)點對比排序性能，找出高性能邊排序初始點所在的網(wǎng)絡(luò)分區(qū)。在對工程網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)

5、分區(qū)的操作時，必須選擇合適的介數(shù)閾值以確定劃分點。選取多個實際工程網(wǎng)絡(luò)進(jìn)行實驗，實驗結(jié)果表明，此方法具有可操作性與指導(dǎo)意義。
　　(3)不同的排序策略在對工程網(wǎng)絡(luò)中所有節(jié)點的遍歷方式上是不同的。策略不同時，同一個初始點生成的BDD規(guī)?？赡芟嗖罹薮蟆τ诓煌呐判虿呗韵碌母咝阅苓吪判虺跏键c的分布特征和穩(wěn)定性進(jìn)行了對比。得出在常用的BFS策略中，高性能邊排序初始點依然具有較強(qiáng)的穩(wěn)定性和匯聚性，為其他可用策略下的高性能邊排序初始點的選擇