針對(duì)隨機(jī)網(wǎng)絡(luò)可靠性的遞歸重要性分層抽樣方法

對(duì)隨機(jī)網(wǎng)絡(luò)可靠性估計(jì)的抽樣方法

----遞歸重要性和分層抽樣AsimplerecursiveimportanceandstratifiedsamplingschemeforstochasticnetworkreliabilityestimationWei-NingYang*,Wei-LingShih,JihChunYeh指導(dǎo)老師：徐光偉學(xué)生：楊延彬

時(shí)間：2015/06目錄問題提出一研究現(xiàn)狀二算法設(shè)計(jì)三性能評(píng)估四總結(jié)五2一、問題提出研究背景

大多數(shù)計(jì)算機(jī)通信系統(tǒng)可以被當(dāng)做隨機(jī)網(wǎng)絡(luò)模型，其網(wǎng)絡(luò)的可靠性經(jīng)常作為系統(tǒng)性能的一個(gè)衡量標(biāo)準(zhǔn)。但是由于網(wǎng)絡(luò)的復(fù)雜性，分析模型和數(shù)值評(píng)估是不可行的，因?yàn)殡S著網(wǎng)絡(luò)復(fù)雜性的增長，其可靠性的計(jì)算代價(jià)過高。問題提出計(jì)算機(jī)仿真是評(píng)估網(wǎng)絡(luò)可靠性的一個(gè)可行的替代選擇，但由于計(jì)算機(jī)仿真依賴于試驗(yàn)統(tǒng)計(jì)，所以需要解決仿真過程中的抽樣誤差。原始的蒙特卡洛抽樣是活的網(wǎng)絡(luò)可靠性估計(jì)的基本技術(shù)，但是對(duì)于可靠性比較好的網(wǎng)絡(luò)，需要進(jìn)行大量的實(shí)驗(yàn)才可以活的比較明顯的結(jié)果。為了緩解這種限制，出現(xiàn)了很多技術(shù)來縮減評(píng)估的方差又不用增加樣本容量。3二、研究現(xiàn)狀4大多數(shù)的方差縮減技術(shù)是通過人工地誘導(dǎo)輸出回應(yīng)之間的相關(guān)性或者檢索輸入變量和輸出回應(yīng)之間固有的相關(guān)性來提高統(tǒng)計(jì)的有效性。原始的蒙特卡洛方法是獲得網(wǎng)絡(luò)可靠性的最基本仿真技術(shù)，但是對(duì)于可靠性比較高的網(wǎng)絡(luò)，需要非常多的實(shí)驗(yàn)才可以獲得比較明顯的結(jié)果；Kumamotoetal.引進(jìn)了一種誘導(dǎo)副本之間的負(fù)相關(guān)性的匕首抽樣設(shè)計(jì)來改進(jìn)原始的蒙特卡洛估計(jì)；konaketal.使用塊抽樣來改進(jìn)匕首抽樣方法；Rubinstein&Samorodnitsky通過運(yùn)用公共隨機(jī)數(shù)和對(duì)偶變量技術(shù)來誘導(dǎo)副本之間的相關(guān)性；karp&Luby使用系統(tǒng)的失敗集的知識(shí)來充分利用其內(nèi)部固有的相關(guān)性來改進(jìn)可靠性評(píng)估；Easton&Wong提出了一種順序結(jié)構(gòu)和destruction技術(shù)，其可以充分利用抽樣序列的排列屬性并保證減小可靠性估計(jì)的方差；Elperinetal.提出了一種將邊緣排列空間分區(qū)并在數(shù)值上計(jì)算考慮到邊緣排列的條件網(wǎng)絡(luò)可靠性的排列蒙特卡洛方法。Elperinetal.在評(píng)估高可靠性網(wǎng)絡(luò)的可二、研究現(xiàn)狀5靠性時(shí)使用一個(gè)歸并進(jìn)程來構(gòu)造條件蒙特卡洛估計(jì)；Cristian使用分層抽樣，充分利用輸出回應(yīng)和用來將輸入空間劃分為可管理的更小的空間的分層變量之間的相關(guān)性來估計(jì)去故障覆蓋的可能性。

方差縮減技術(shù)除了人工誘導(dǎo)或者利用其內(nèi)部固有的相關(guān)性之外，重要性抽樣方法通過強(qiáng)調(diào)抽樣軌跡來增強(qiáng)器統(tǒng)計(jì)有效性。對(duì)于稀有事件的仿真，重要性抽樣技術(shù)是最有潛力實(shí)現(xiàn)將方差縮減幾個(gè)數(shù)量級(jí)的技術(shù)。Fishman&Shaw第一次使用分解程序?qū)顟B(tài)機(jī)分成可操作集、失敗集和不確定集，并將所有的抽樣工作分配給不確定集中。Cancela&Khadiri基于連接到目的結(jié)點(diǎn)的狀態(tài)將網(wǎng)絡(luò)遞歸的劃分為幾個(gè)子網(wǎng)，并對(duì)明顯失敗的子網(wǎng)不分配任何的抽樣工作，雖然每一階段節(jié)約的抽樣工作是有限的，但是累積的抽樣節(jié)約可以明顯的縮減方差。Cancela&Khadiri又進(jìn)一步使用了串并聯(lián)縮減技術(shù)來縮減子網(wǎng)的大小。他們有通過避免相同的多余計(jì)算，使得執(zhí)行時(shí)間明顯減小。（續(xù)）三、算法設(shè)計(jì)6問題描述對(duì)于一個(gè)無向的通信網(wǎng)絡(luò)，由節(jié)點(diǎn)集V，m條鏈接集E，目的節(jié)點(diǎn)集K。如果在K中的所有節(jié)點(diǎn)都是可鏈接的，那么網(wǎng)絡(luò)G就是K-connected。如果網(wǎng)絡(luò)G是K-connected，那么其對(duì)應(yīng)的系統(tǒng)就是認(rèn)為是可以工作的，我們的目標(biāo)就是估計(jì)系統(tǒng)可以工作的概率。網(wǎng)絡(luò)G的各個(gè)操作是相互獨(dú)立的并被認(rèn)為是隨機(jī)的出現(xiàn)故障。令，是相互獨(dú)立的伯努利隨機(jī)變量且第i條鏈接是可以工作的其他i=1,2,…,m令是第i條鏈接可以工作的概率。三、算法設(shè)計(jì)7代表狀態(tài)向量，其對(duì)應(yīng)的系統(tǒng)回應(yīng)是：如果狀態(tài)為X的網(wǎng)絡(luò)G是K-connected,其他。那么其對(duì)應(yīng)的系統(tǒng)可靠性為：其中其他三、算法設(shè)計(jì)8簡(jiǎn)單抽樣由于隨著m的增大，對(duì)于R(G)的窮舉計(jì)算是不可行的，因此可以用根據(jù)X對(duì)應(yīng)的f(X)對(duì)狀態(tài)集進(jìn)行抽樣來估計(jì)R(G)。n為樣本容量。對(duì)應(yīng)的可靠性估計(jì)為：對(duì)應(yīng)的方差：重要性抽樣對(duì)于一個(gè)普通的網(wǎng)絡(luò)，在目的節(jié)點(diǎn)中任意的挑選一個(gè)，在E中存在個(gè)鏈接：，根據(jù)這個(gè)鏈接將網(wǎng)絡(luò)G劃分為+1個(gè)子網(wǎng)，子網(wǎng)是鏈接不能正常工作，而可以正常工作。是這個(gè)鏈接都不能工作的子網(wǎng)，很明顯和是相互排斥的。然后將所有的n個(gè)抽樣工作分配給，而中不用做任何抽樣。三、算法設(shè)計(jì)9令，j=2,3,…,然后將n個(gè)樣本按照比例額分配給各個(gè)子網(wǎng)，子網(wǎng)對(duì)應(yīng)的樣本良好為

。遞歸重要性抽樣如果僅僅對(duì)網(wǎng)絡(luò)G是用這種重要性抽樣，而對(duì)于子網(wǎng)仍使用原始的抽樣方法估計(jì)其可靠性，那么整個(gè)網(wǎng)絡(luò)G的可靠性R(G)可以表示為：三、算法設(shè)計(jì)10其對(duì)應(yīng)的方差為：針對(duì)子網(wǎng)中的不可確定網(wǎng)絡(luò)，可以看作為一單獨(dú)普通的網(wǎng)絡(luò)，并對(duì)其使用重要性抽樣方法評(píng)估其可靠性，那么整個(gè)網(wǎng)絡(luò)G的可靠性為：這種重要性抽樣方法被遞歸的應(yīng)用到每一個(gè)子網(wǎng)上，直到子網(wǎng)的狀態(tài)是確定的（failed或者K-connected）。對(duì)于高可靠性的網(wǎng)絡(luò)而言，雖然在明顯失敗的網(wǎng)絡(luò)中沒有浪費(fèi)抽樣工作的效益不很明顯，但是在遞歸工作中的累計(jì)效果可已達(dá)到明顯的方差縮減效果。三、算法設(shè)計(jì)11預(yù)分配由于分層抽樣需要在每一層內(nèi)進(jìn)行抽樣，那么當(dāng)網(wǎng)絡(luò)處于確定狀態(tài)，或者抽樣預(yù)算不足以在每一不確定子網(wǎng)對(duì)應(yīng)的普通網(wǎng)絡(luò)中進(jìn)行抽樣時(shí)，會(huì)造成分成抽樣方法的停止。因此對(duì)于每一個(gè)不確定的子網(wǎng)進(jìn)行預(yù)分配兩個(gè)“抽樣名額“，并使用我們提出的重要性分層抽樣方案來估計(jì)網(wǎng)絡(luò)的可靠性。預(yù)分配不僅可以對(duì)方差進(jìn)行估計(jì)，同時(shí)可以推遲遞歸分層抽樣進(jìn)程的終止，因此增強(qiáng)了分層的有效性。串并聯(lián)縮減

當(dāng)進(jìn)行遞歸重要性分層抽樣時(shí)，使用Cacela&Khadir提出的串并聯(lián)縮減技術(shù)來簡(jiǎn)化網(wǎng)絡(luò)，以此來增強(qiáng)計(jì)算的有效性。串聯(lián)縮減技術(shù)是指，當(dāng)某一普通節(jié)點(diǎn)的度為2時(shí)，可以用一個(gè)連接代替原來鏈接次普通節(jié)點(diǎn)的兩條鏈接，其成功的概率是原來兩條鏈接成功的概率之積，并移除該普通節(jié)點(diǎn)；并聯(lián)縮減技術(shù)是指，當(dāng)出現(xiàn)兩條平行的鏈接，用一條鏈接代替原來的兩條鏈接，其成功的概率為原來兩條鏈接至少有一條鏈接正常的概率。三、算法設(shè)計(jì)12重要性抽樣算法（ImportanceSampling，IS）AlgorithmIS() 1.檢測(cè)遞歸的終止條件：

（a）如果是那么就直接返回。

（b）如果是那么將加到上，將

加到上并返回。 2.對(duì)網(wǎng)絡(luò)進(jìn)行串并聯(lián)簡(jiǎn)化操作。 3.在中任意選擇一個(gè)目的節(jié)點(diǎn)，依據(jù)鏈接到選擇的目的節(jié)點(diǎn)的b條鏈

接的狀態(tài)將網(wǎng)絡(luò)劃分為子網(wǎng)和目標(biāo)集。 4.令 5.將抽樣樣本按照比例分配給b個(gè)子網(wǎng)。 6.對(duì)于每一個(gè)子網(wǎng)調(diào)用IS()。

三、算法設(shè)計(jì)13重要性分層抽樣算法（ImportanceandstratifiedSampling，IS+ST）AlgorithmIS+ST()： 1.檢測(cè)遞歸的終止條件：

（a）如果是那么就直接返回。

（b）如果是那么將加到上。 2.對(duì)網(wǎng)絡(luò)進(jìn)行串并聯(lián)簡(jiǎn)化操作。 3.在中任意選擇一個(gè)目的節(jié)點(diǎn)，依據(jù)鏈接到選擇的目的節(jié)點(diǎn)的b條鏈

接的狀態(tài)將網(wǎng)絡(luò)劃分為子網(wǎng)和目標(biāo)集。 4.令

下面是經(jīng)判斷抽樣任務(wù)是否足夠預(yù)分配，如果不夠那么就調(diào)用重要性抽樣

方法，否則則遞歸調(diào)用重要性分層抽樣方法。三、算法設(shè)計(jì)14重要性分層抽樣算法（續(xù)）

5.如果{

那么調(diào)用IS()

同時(shí)將增加到，將增加到}

否則{

令

并對(duì)每一個(gè)子網(wǎng)調(diào)用IS+ST()}。重要性分層抽樣算法的調(diào)初始用過程1.設(shè)置全局變量和。2.調(diào)用IS+ST()。3.報(bào)告網(wǎng)絡(luò)的可靠性

和相應(yīng)的標(biāo)準(zhǔn)差。四、性能評(píng)估15方差分析對(duì)于最初的網(wǎng)絡(luò)G劃分的個(gè)子網(wǎng)，對(duì)于每一個(gè)子網(wǎng)來說，其可靠性為，對(duì)應(yīng)的伯努利狀態(tài)的方差為

。令。由于是明顯失敗的子網(wǎng)，所以對(duì)應(yīng)有。那么整個(gè)網(wǎng)絡(luò)的可靠性為使用原始抽樣方法對(duì)R(G)進(jìn)行估計(jì)的方差為：重要性抽樣四、性能評(píng)估16考慮不將抽樣工作浪費(fèi)在明顯失敗的子網(wǎng)那么網(wǎng)絡(luò)G的可靠性估計(jì)為：那么用原始的抽樣方法對(duì)的估計(jì)為：其中：其對(duì)應(yīng)的方差：四、性能評(píng)估17分層抽樣

分層抽樣中網(wǎng)路的可靠性估計(jì)為：對(duì)應(yīng)的方差為：其中：四、性能評(píng)估18由于可得，對(duì)于重要性抽樣方法可靠性估計(jì)為：對(duì)應(yīng)方差：四、性能評(píng)估19重要性分層抽樣類似的，重要性分層抽樣方法的重要性估計(jì)為：其對(duì)應(yīng)的方差為：四、性能評(píng)估20遞歸應(yīng)用當(dāng)重要性抽樣的思想被遞歸的運(yùn)用在劃分后求子網(wǎng)可靠性時(shí)，對(duì)應(yīng)的方差：類似的對(duì)于兩層的重要性分層抽樣來說，子網(wǎng)頁使用分層抽樣，對(duì)應(yīng)的方差：由于所以方差相對(duì)減小。四、性能評(píng)估21實(shí)驗(yàn)分析兩種實(shí)驗(yàn)?zāi)Ｐ腿缬覉D：一共20個(gè)結(jié)點(diǎn)，30條鏈接，其中源節(jié)點(diǎn)1和匯點(diǎn)20作為目的節(jié)點(diǎn)。所有鏈接可以工作的概率分別設(shè)置為p=0.50,0.90,0.99和0.999進(jìn)行仿真實(shí)驗(yàn)。四、性能評(píng)估22如右圖：一共36個(gè)結(jié)點(diǎn)，60條鏈接，其中四個(gè)角的結(jié)點(diǎn)作為目的節(jié)點(diǎn)。所有鏈接可以工作的概率分別設(shè)置為p=0.50,0.90,0.99和0.999進(jìn)行仿真實(shí)驗(yàn)。四、性能評(píng)估23預(yù)分配的影響四、性能評(píng)估24基于上述實(shí)驗(yàn)的結(jié)果可以得到如下結(jié)論：IS+ST和IS+ST0都是無偏的。IS+ST比IS+ST0統(tǒng)計(jì)上更加有效，隨著鏈接的可正常運(yùn)行概率的增長，預(yù)分配對(duì)方差的縮減更明顯，因?yàn)槲搭A(yù)分配的方法在分層抽樣時(shí)可能導(dǎo)致分層進(jìn)程很快結(jié)束。而預(yù)分配進(jìn)程在分配抽樣工作時(shí)事先對(duì)每一個(gè)子網(wǎng)預(yù)分配2個(gè)抽樣指標(biāo)，因此使得方法可以更進(jìn)一步的分層來檢索分層的統(tǒng)計(jì)有效性。

在計(jì)算時(shí)間上兩種方法之間沒有明顯差別，但有些時(shí)候預(yù)分配方法的分層進(jìn)程檢索子網(wǎng)可能會(huì)導(dǎo)致計(jì)算時(shí)間上比未預(yù)分配方法的花費(fèi)的代價(jià)要高。四、性能評(píng)估25其他方法比較（IS+ST，IS，