在并行分布式系統(tǒng)中,多處理器之間連接的拓?fù)浣Y(jié)構(gòu)(互連網(wǎng)絡(luò))至關(guān)重要,它直接影響到并行分布式系統(tǒng)的性能和功能的實(shí)現(xiàn)。k-元n-立方體網(wǎng)絡(luò)是最常用的互連網(wǎng)絡(luò)之一,它具有許多好的性質(zhì),比如易運(yùn)行、低延遲、高帶寬等。許多并行分布式系統(tǒng)都是用k-元n-立方體網(wǎng)絡(luò)(表示為Q_n~k)作為其連接模式,如IBM BlueGene/L超級(jí)計(jì)算機(jī),J-machine,Cray T3D 和Cray T3E�；ミB網(wǎng)絡(luò)可以表示為一個(gè)圖,圖的頂點(diǎn)表示系統(tǒng)中的處理器,邊表示處理器之間的通信鏈路。在實(shí)際的應(yīng)用系統(tǒng)中,設(shè)備或通信鏈路發(fā)生故障是在所難免的。當(dāng)網(wǎng)絡(luò)出現(xiàn)故障時(shí),如何使得網(wǎng)絡(luò)能夠正常地工作,原網(wǎng)絡(luò)的性能如何得到最大程度的保持,即容錯(cuò)性,是互連網(wǎng)絡(luò)研究必須考慮的問(wèn)題。網(wǎng)絡(luò)中存在多少數(shù)量的故障元素,網(wǎng)絡(luò)仍然是連通的(即連通度問(wèn)題),任意兩個(gè)無(wú)故障頂點(diǎn)之間是否存在無(wú)故障路徑與如何構(gòu)造(即容錯(cuò)路由問(wèn)題),是否存在包含每一個(gè)無(wú)故障頂點(diǎn)一次且僅一次的路或者圈(即容錯(cuò)哈密頓性質(zhì)問(wèn)題)。這些都是互連網(wǎng)絡(luò)容錯(cuò)性研究中需要首先解決的問(wèn)題。本文從這三個(gè)方面研究k-元n-立方體網(wǎng)絡(luò)的容錯(cuò)性。已有的容錯(cuò)性研究主要是針對(duì)故障元素是頂點(diǎn)或者邊。在實(shí)際應(yīng)用中,故障點(diǎn)和邊的分布可能比較集中或局部化,即故障元素可以看成是圖的子結(jié)構(gòu),這類故障稱為結(jié)構(gòu)故障。本文研究在存在結(jié)構(gòu)故障的情況下,k-元n-立方體網(wǎng)絡(luò)的容錯(cuò)性,包含以下內(nèi)容:1.k-元n-立方體網(wǎng)絡(luò)的結(jié)構(gòu)連通度和子結(jié)構(gòu)連通度(1)證明了當(dāng)k = 3時(shí),k-元n-立方體網(wǎng)絡(luò)的K_(1,1)-結(jié)構(gòu)連通度和K_(1,1)-子結(jié)構(gòu)連通度都是n;當(dāng)k= 4時(shí),k-元n-立方體網(wǎng)絡(luò)的K_(1,1)-結(jié)構(gòu)連通度和K_(1,1)-子結(jié)構(gòu)連通度都是2n-1;當(dāng)k≥5時(shí),k-元n-立方體網(wǎng)絡(luò)的K_(1,1)-結(jié)構(gòu)連通度和K_(1,1)-子結(jié)構(gòu)連通度都是2n。(2)證明了k-元n-立方體網(wǎng)絡(luò)的K1,2-結(jié)構(gòu)連通度和K1,2-子結(jié)構(gòu)連通度都是n。(3)證明了k-元n-立方體網(wǎng)絡(luò)的K_(1,3)-結(jié)構(gòu)連通度和K_(1,3)-子結(jié)構(gòu)連通度都是n。2.在存在結(jié)構(gòu)故障的情況下,k-元n-立方體網(wǎng)絡(luò)(表示為Q_n~k)的容錯(cuò)哈密頓性(1)證明了在k-元n-立方體中,當(dāng)至多存在n-2個(gè)故障元素并且每個(gè)故障元素在圖Q_n~k中的導(dǎo)出子圖都同構(gòu)于K_(1,3)的一個(gè)連通子圖的生成母圖時(shí),任意兩個(gè)無(wú)故障頂點(diǎn)之間存在無(wú)故障的哈密頓路。(2)證明了當(dāng)至多存在n-1個(gè)故障元素并且每個(gè)故障元素在圖Q_n~k中的導(dǎo)出子圖都同構(gòu)于K_(1,3)的一個(gè)連通子圖的生成母圖時(shí),在k-元n-立方體中存在無(wú)故障的哈密頓圈。3.給出了在存在結(jié)構(gòu)故障的情況下k-元n-立方體網(wǎng)絡(luò)中容錯(cuò)路由、容錯(cuò)哈密頓圈和容錯(cuò)哈密頓路的構(gòu)造算法,并通過(guò)模擬實(shí)驗(yàn)給出了實(shí)驗(yàn)結(jié)果。綜上所述,本文研究了在存在結(jié)構(gòu)故障的情況下,k-元n-立方體網(wǎng)絡(luò)的容錯(cuò)性,對(duì)于k-元n-立方體網(wǎng)絡(luò)的應(yīng)用提供了理論依據(jù)。
【學(xué)位單位】：蘇州大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位年份】：2018
【中圖分類】：O157.5;TP393.0
【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 引言
    1.2 互連網(wǎng)絡(luò)研究概述
    1.3 研究?jī)?nèi)容
    1.4 本文組織結(jié)構(gòu)
第二章 相關(guān)知識(shí)
    2.1 基本概念和符號(hào)表示
    2.2 k-元n-立方體
    2.3 本章小結(jié)
n
k的結(jié)構(gòu)連通度和子結(jié)構(gòu)連通度'>第三章 Q_{n
k的結(jié)構(gòu)連通度和子結(jié)構(gòu)連通度
1}-結(jié)構(gòu)連通度和K₁-子結(jié)構(gòu)連通度'>    3.1 K₁-結(jié)構(gòu)連通度和K₁-子結(jié)構(gòu)連通度
1.1-結(jié)構(gòu)連通度和K_1.1-子結(jié)構(gòu)連通度'>    3.2 K_1.1-結(jié)構(gòu)連通度和K_1.1-子結(jié)構(gòu)連通度
1.2-結(jié)構(gòu)連通度和K_1.2-子結(jié)構(gòu)連通度'>    3.3 K_1.2-結(jié)構(gòu)連通度和K_1.2-子結(jié)構(gòu)連通度
1.3-結(jié)構(gòu)連通度和K_1.3-子結(jié)構(gòu)連通度'>    3.4 K_1.3-結(jié)構(gòu)連通度和K_1.3-子結(jié)構(gòu)連通度
    3.5 本章小結(jié)
n
3中基于結(jié)構(gòu)故障的容錯(cuò)哈密頓性質(zhì)'>第四章 Qn
3中基于結(jié)構(gòu)故障的容錯(cuò)哈密頓性質(zhì)
    4.1 預(yù)備知識(shí)
n
3中基于K_1.1-結(jié)構(gòu)故障的容錯(cuò)哈密頓性質(zhì)'>    4.2 Qn
3中基于K_1.1-結(jié)構(gòu)故障的容錯(cuò)哈密頓性質(zhì)
n
3中基于K_1.2-結(jié)構(gòu)故障的容錯(cuò)哈密頓性質(zhì)'>    4.3 Qn
3中基于K_1.2-結(jié)構(gòu)故障的容錯(cuò)哈密頓性質(zhì)
n
3中基于K_1.3-結(jié)構(gòu)故障的容錯(cuò)哈密頓性質(zhì)'>    4.4 Qn
3中基于K_1.3-結(jié)構(gòu)故障的容錯(cuò)哈密頓性質(zhì)
    4.5 本章小結(jié)
n
k（k≥5）中基于結(jié)構(gòu)故障的容錯(cuò)哈密頓性質(zhì)'>第五章 Qn
k（k≥5）中基于結(jié)構(gòu)故障的容錯(cuò)哈密頓性質(zhì)
    5.1 預(yù)備知識(shí)
n
k（k≥5）中基于K_1.1-結(jié)構(gòu)故障的容錯(cuò)哈密頓性質(zhì)'>    5.2 Qn
k（k≥5）中基于K_1.1-結(jié)構(gòu)故障的容錯(cuò)哈密頓性質(zhì)
n
k（k≥5）中基于K_1.2-結(jié)構(gòu)故障的容錯(cuò)哈密頓性質(zhì)'>    5.3 Qn
k（k≥5）中基于K_1.2-結(jié)構(gòu)故障的容錯(cuò)哈密頓性質(zhì)
n
k（k≥5）中基于K_1.3-結(jié)構(gòu)故障的容錯(cuò)哈密頓性質(zhì)'>    5.4 Qn
k（k≥5）中基于K_1.3-結(jié)構(gòu)故障的容錯(cuò)哈密頓性質(zhì)
    5.5 本章小結(jié)
第六章 模擬實(shí)驗(yàn)
n
k中基于結(jié)構(gòu)故障的容錯(cuò)路由的構(gòu)造'>    6.1 Qn
k中基于結(jié)構(gòu)故障的容錯(cuò)路由的構(gòu)造
        6.1.1 容錯(cuò)路由的構(gòu)造算法
        6.1.2 實(shí)驗(yàn)結(jié)果
n
k中基于結(jié)構(gòu)故障的容錯(cuò)哈密頓圈的構(gòu)造'>    6.2 Qn
k中基于結(jié)構(gòu)故障的容錯(cuò)哈密頓圈的構(gòu)造
        6.2.1 容錯(cuò)哈密頓圈的構(gòu)造算法
        6.2.2 實(shí)驗(yàn)結(jié)果
n
k中基于結(jié)構(gòu)故障的容錯(cuò)哈密頓路的構(gòu)造'>    6.3 Qn
k中基于結(jié)構(gòu)故障的容錯(cuò)哈密頓路的構(gòu)造
        6.3.1 容錯(cuò)哈密頓路的構(gòu)造算法
        6.3.2 實(shí)驗(yàn)結(jié)果
    6.4 本章小結(jié)
第七章 總結(jié)與展望
    7.1 工作總結(jié)
    7.2 研究展望
參考文獻(xiàn)
攻讀博士學(xué)位期間發(fā)表的論文和參與的科研項(xiàng)目
致謝

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 段滿珍;米雪玉;董博;軋紅穎;;基于建筑傾倒優(yōu)勢(shì)方向的疏散路網(wǎng)連通度模型[J];重慶交通大學(xué)學(xué)報(bào)(自然科學(xué)版);年期

2 蔡學(xué)鵬;艾爾肯·吾買(mǎi)爾;;交叉立方體的限制性連通度（英文）[J];曲阜師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2018年03期

3 李建喜;郭繼明;邵慰慈;;給定團(tuán)數(shù)的連通圖的最小代數(shù)連通度[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2016年06期

4 晉亞男;林上為;;有向笛卡爾積圖的k-限制弧連通度[J];河南科學(xué);2017年03期

5 謝春萍;梁家榮;;星型網(wǎng)絡(luò)的額外連通度[J];廣西科技大學(xué)學(xué)報(bào);2015年03期

6 王萬(wàn)禹;孟吉翔;趙雪冰;;線圖的限制性鄰域連通度[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2012年02期

7 江凈超;陳江平;余潔;;道路網(wǎng)的實(shí)況連通度指標(biāo)[J];測(cè)繪與空間地理信息;2010年01期

8 趙雪冰;張昭;;線圖的鄰域連通度(英文)[J];新疆大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年04期

9 潘登斌;關(guān)于二分圖的線連通度的一個(gè)結(jié)論[J];廣西科學(xué)院學(xué)報(bào);2003年01期

10 潘登斌;關(guān)于二分圖的線連通度的一個(gè)結(jié)論[J];廣西師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2002年03期

相關(guān)博士學(xué)位論文 前10條

1 胡曉敏;互聯(lián)網(wǎng)絡(luò)的容錯(cuò)性與故障診斷[D];新疆大學(xué);2018年

2 呂雅麗;基于結(jié)構(gòu)故障的k-元n-立方體網(wǎng)絡(luò)的容錯(cuò)性研究[D];蘇州大學(xué);2018年

3 楊超;乘積圖的連通度和容錯(cuò)直徑的研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2007年

4 李瑋;完全多部圖的廣義連通度[D];南開(kāi)大學(xué);2012年

5 田應(yīng)智;圖的超連通性和限制性連通度[D];新疆大學(xué);2012年

6 袁煒罡;關(guān)于圖的幾種指數(shù)的研究[D];上海交通大學(xué);2015年

7 熊瑋;幾類圖參數(shù)的研究[D];新疆大學(xué);2014年

8 洪艷梅;圖連通度與非分離子圖[D];上海大學(xué);2012年

9 李莎莎;圖的廣義連通度若干問(wèn)題的研究[D];南開(kāi)大學(xué);2012年

10 何利;高性能計(jì)算機(jī)中互連網(wǎng)絡(luò)的可靠性研究[D];重慶大學(xué);2014年

相關(guān)碩士學(xué)位論文 前10條

1 張倩華;類超立方體網(wǎng)絡(luò)的廣義連通度[D];山西大學(xué);2017年

2 羅祖文;兩類Cayley圖的條件連通度和極大局部連通度[D];集美大學(xué);2018年

3 趙樹(shù)麗;超立方體與折疊立方體的分支連通性[D];太原理工大學(xué);2017年

4 蔡學(xué)鵬;折疊交叉立方體的超連通度和交叉立方體的限制性連通度[D];新疆大學(xué);2017年

5 周嬋嬋;有向圖的條件弧連通度[D];山西大學(xué);2017年

6 賈勇;基于圖數(shù)據(jù)的Steiner分量發(fā)現(xiàn)方法研究[D];燕山大學(xué);2017年

7 趙雪冰;（有向）圖的鄰域連通度的研究[D];新疆大學(xué);2012年

8 白燕茹;邊鄰域連通度達(dá)到最大的極圖的刻畫(huà)[D];新疆大學(xué);2012年

9 萬(wàn)敏;星圖的一種條件連通度[D];新疆大學(xué);2008年

10 張佳;互連網(wǎng)絡(luò)的h-額外連通度和h-額外條件可診斷數(shù)研究[D];西安電子科技大學(xué);2017年

本文編號(hào)：2872976

boshi