資源描述:
《hypermesh 網(wǎng)絡的超邊連通度》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、Hypermesh網(wǎng)絡的超邊連通度朱強,李剛平,王新科,程廣蘭(西安電子科技大學理學院,陜西西安710071)摘要:超邊連通度是對傳統(tǒng)邊連通度的推廣,而且是度量互連網(wǎng)絡容錯性的一個重要參數(shù).Hypermesh網(wǎng)絡由于具有良好的性能,而受到廣泛的研究和關(guān)注.本文通過對Hypermesh網(wǎng)絡容錯性質(zhì)的考察,證明了當,時,它的超邊連通度是.關(guān)鍵詞:Hypermesh網(wǎng)絡;超邊連通度;點割;邊割Superedge-connectivityofHypermeshNetworkZHUQiang,LIGang-ping,WANGXin-ke,CHENGGu
2、ang-lan(DepartmentofMathematics,XidianUniversity,Xi'an,710071,China)Abstract:Asageneralizationofclassicaledge-connectivity,thesuperedge-connectivitycanprovidemoreaccuratemeasureoffault-toleranceforinterconnectionnetworks.TheHypermeshnetwork,duetoitsgoodperformance,hasbeenwi
3、delystudied.Inthispaper,weinvestigatethefault-tolerantpropertiesofHypermeshnetwork,andprovethatthesuperedge-connectivityofk-aryn-dimensionalHypermeshnetworkis2n(k-1)-2forn≥2andk≥3.Keywords:Hypermeshnetwork;superedge-connectivity;vertex-cut;edge-cut1引言隨著科學技術(shù)、VLSI技術(shù)的飛速發(fā)展使得實現(xiàn)大
4、規(guī)模的、高度復雜的互連網(wǎng)絡成為可能,這些互連網(wǎng)絡已被廣泛應用于廣播網(wǎng)、局域網(wǎng)、電信網(wǎng)以及其他分布式計算機系統(tǒng)的設(shè)計中,且成為現(xiàn)代并行處理系統(tǒng)的核心組成部分,在很大程度上決定著整個系統(tǒng)的性能.顯然,互連網(wǎng)絡可以用圖來表示.圖的頂點表示系統(tǒng)中的元件,圖的邊表示元件之間的物理連線,其中有向邊表示單向通信連線,無向邊表示雙向通信連線,而關(guān)聯(lián)函數(shù)指定了元件之間的連接方式.這樣的圖稱為互連網(wǎng)絡拓撲結(jié)構(gòu),或者簡稱網(wǎng)絡拓撲.反之,圖也可以看成是某個互連網(wǎng)絡的拓撲結(jié)構(gòu).從拓撲上講,圖和互連網(wǎng)絡是一回事.將網(wǎng)絡、元件和連線說成是圖、頂點和邊,反之亦然.圖是有向的
5、還是無向的,根據(jù)通信連線是單向的還是雙向的決定[1].因此,我們用一個連通的無向圖作為互連網(wǎng)絡的拓撲結(jié)構(gòu),它是決定網(wǎng)絡性能的一個重要因素,而網(wǎng)絡的可靠性和容錯性是網(wǎng)絡設(shè)計者所追求的目標之一.通常人們用連通度和邊連通度來衡量網(wǎng)絡系統(tǒng)的可靠程度[3].然而隨著對計算機網(wǎng)絡拓撲結(jié)構(gòu)的深入研究,人們發(fā)現(xiàn)用連通度和邊連通度來度量網(wǎng)絡的容錯性有三個缺陷.首先,兩個圖的連通度(或邊連通度)即使相同,它們的可靠性也不一定一樣,因為它們的最小點割數(shù)(或最小邊割數(shù))可能不同.其次,這兩個參數(shù)不能區(qū)別按不同方式移去個點(或條邊)后產(chǎn)生的不同連通分支的情況.這說明連
6、通度和邊連通度不能反映由于處理器或通訊信道損壞造成的系統(tǒng)損壞程度.因而這兩個參數(shù)在某些應用上不夠精確.第三,在分析和應用這兩個參數(shù)時我們都不言而喻的假定了系統(tǒng)的任何部分都可能同時出現(xiàn)故障,也就是說對這些參數(shù)沒有加任何限制.然而,在帶有某種類型故障診斷算法的計算機互連網(wǎng)絡中,人們可以安全的假定網(wǎng)絡組件的某些子集不會同時出現(xiàn)故障,或者對這些參數(shù)加上某些限制.對于這樣的網(wǎng)絡,經(jīng)典的連通度和邊連通度就不能精確的度量其可靠性了.事實上,我們在確定圖的連通度和邊連通度時,只考慮使得(或)不連通的點割(或邊割)的最小數(shù),忽略的相應的集合(或)同時發(fā)生故障的
7、可能性.換句話說,在連通度和邊連通度的定義中,對(或)的分支和點割(或邊割)沒有加任何條件或限制.所以為了彌補以上缺陷,人們自然會想到對(或)的分支和點割(或邊割)加上一些條件或限制,從而推廣了經(jīng)典連通度和邊連通度的概念.在1983年,Harary[16]首先提出了條件連通度的概念.1988年,Esfahanian和Hakimi[5]把條件具體化,提出了限制連通度的概念.一個網(wǎng)絡的限制(邊)連通度是限制其任何一個節(jié)點的所有鄰點(邊)不會同時出故障的情況下,網(wǎng)絡中最少需要多少個節(jié)點(邊)發(fā)生故障才能使其變得不再連通。因為在以立方體等互連網(wǎng)絡為拓
8、撲結(jié)構(gòu)的多處理器系統(tǒng)中一個節(jié)點的所有鄰點或者鄰邊發(fā)生故障的可能性非常小,因此限制(邊)連通度能更精確的分析這些互連網(wǎng)絡的可靠性.近幾年來,它們引起了理論計算機科學工