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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.如果{

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

同時將增加到，將增加到}

否則{

令

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

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

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

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

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