PMC模型下EQn,k和Q(d1,d2)的條件診斷度.pdf

1、計算機大規(guī)模處理數(shù)據(jù)有多種方式，伴隨著因特網(wǎng)的普及和云計算的高速發(fā)展，網(wǎng)絡(luò)與計算機更緊密的結(jié)合在了一起。在龐大的網(wǎng)絡(luò)環(huán)境中散布著大量的處理終端和服務(wù)器，發(fā)生錯誤或者物理性故障是不可避免的。如何在發(fā)生故障時依靠網(wǎng)絡(luò)系統(tǒng)自身的能力進(jìn)行錯誤判別，并且不額外增加系統(tǒng)資源的投入和消耗就變得非常具有現(xiàn)實意義。
　　應(yīng)用圖論中的無向圖理論對計算機網(wǎng)絡(luò)進(jìn)行抽象分析是普遍的方法。將網(wǎng)絡(luò)中的處理器抽象成頂點，將通信鏈路抽象成無向邊，即可構(gòu)造出系統(tǒng)所對

2、應(yīng)的圖。如果系統(tǒng)中某些處理器或者服務(wù)器錯誤，那么如何通過一定的算法將錯誤節(jié)點查找出來就是網(wǎng)絡(luò)診斷問題。這一類算法已經(jīng)有過比較深入系統(tǒng)的研究，可以應(yīng)用于復(fù)雜網(wǎng)絡(luò)系統(tǒng)的診斷，也可以應(yīng)用于多處理器系統(tǒng)的診斷。
　　對于一些特殊網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的研究比較成熟，比如超立方圖Qn就已經(jīng)在IBM大型機上得到實際應(yīng)用。擴展超立方體EQn,k是經(jīng)典的超立方體網(wǎng)絡(luò)Qn的一種改進(jìn)和推廣，廣義立方體Q(d1，d2，…，dn）是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的更一般化的推廣。他

3、們不但繼承了超立方體網(wǎng)絡(luò)的優(yōu)點，還在某些方面大大的改進(jìn)了網(wǎng)絡(luò)性質(zhì)。本文通過對小規(guī)模圖進(jìn)行分析歸納找到規(guī)律，再通過嚴(yán)格的數(shù)學(xué)證明來研究上述兩類網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的診斷性質(zhì)，得出診斷度:
　　(1)當(dāng)n≥3，k≥3的情況下，EQn,k的條件診斷度為4n-3。
　　(2)當(dāng)n≥3，k=2的情況下，EQn,k的條件診斷度為4n-7。
　　(3)當(dāng)d2≤2d1的情況下，有tc(Q(d1，d2))=2d1+2d2-7。
　　(4)