M_bius立方體互連網(wǎng)絡條件連通度研究.pdf

1、并行處理系統(tǒng)是當今計算機科學研究的主要方向之一。多處理機互連網(wǎng)絡（Interconnection Networks），簡稱互連網(wǎng)絡，是指由若干個處理機按一定方式相互連接而構成的網(wǎng)絡，它是并行處理系統(tǒng)的核心。對互連網(wǎng)絡拓撲結構及其性質(zhì)的研究是并行處理系統(tǒng)的一個重要課題。M(o)bius立方體具有很多優(yōu)越的性質(zhì)，已經(jīng)被用作多種并行機中處理機連接的拓撲結構并引起了國際上許多研究者的研究興趣。
　　互連網(wǎng)絡中的許多處理機在同時高速運行著，

2、處理機之間經(jīng)常要進行信息傳送。隨著多處理機系統(tǒng)中的處理機數(shù)目的增多和系統(tǒng)規(guī)模的增大，處理機發(fā)生故障是難以避免的。然而，實際上，一個互連網(wǎng)絡的容錯度相對于互連網(wǎng)絡的規(guī)模（頂點數(shù)）一般是很小的。為了提高系統(tǒng)的容錯度，研究者考慮了互連網(wǎng)絡處理機故障發(fā)生的或然率，即假定每個處理機的所有鄰接頂點同時發(fā)生故障的情形是不可能的，也就是說每個頂點至少有一個鄰接頂點是無故障的，在此條件下，本文將以M(o)bius立方體作為網(wǎng)絡拓撲結構圍繞其條件連通度及其

3、相關問題進行研究。
　　本文首先以0-M(o)bius立方體為例證明了M(o)bius立方體在其任一頂點至少有一個鄰接頂點是無故障的情況下，M(o)bius立方體的條件連通度為2n-2，即1-safe條件下M(o)bius立方體的條件連通度為2n-2，其容錯度為2n-3。
　　然后，本文給出M(o)bius立方體互連網(wǎng)絡上基于條件連通度的一個容錯路由選擇算法，分析該算法的時間復雜度為O(n)，并且證明在1-safe條件下的M