發(fā)布時間：2020-11-06 09:46

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

【相似文獻】

相關期刊論文 前10條

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

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

3 李建喜;郭繼明;邵慰慈;;給定團數(shù)的連通圖的最小代數(shù)連通度[J];應用數(shù)學學報;2016年06期

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

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

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

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

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

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

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

相關博士學位論文 前10條

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

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

3 楊超;乘積圖的連通度和容錯直徑的研究[D];中國科學技術大學;2007年

4 李瑋;完全多部圖的廣義連通度[D];南開大學;2012年

5 田應智;圖的超連通性和限制性連通度[D];新疆大學;2012年

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

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

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

9 李莎莎;圖的廣義連通度若干問題的研究[D];南開大學;2012年

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

相關碩士學位論文 前10條

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

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

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

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

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

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

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

8 白燕茹;邊鄰域連通度達到最大的極圖的刻畫[D];新疆大學;2012年

9 萬敏;星圖的一種條件連通度[D];新疆大學;2008年

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

本文編號：2872976

boshi