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