互連網(wǎng)絡(luò)的條件嵌入與容錯.pdf

1、電子計(jì)算機(jī)的出現(xiàn)引起了信息科學(xué)突飛猛進(jìn)的發(fā)展.信息量的增加和計(jì)算量的日益增大，迫切要求計(jì)算機(jī)存儲能力和運(yùn)算速度的提升.單臺計(jì)算機(jī)的性能提升即將遇到集成電路制作工藝的瓶頸，這加劇了并行計(jì)算機(jī)系統(tǒng)的誕生.并行計(jì)算機(jī)系統(tǒng)通常以某種具有優(yōu)秀性質(zhì)的互連網(wǎng)絡(luò)作為拓?fù)浣Y(jié)構(gòu)，將多個處理機(jī)互連，并行處理，以期大幅提升系統(tǒng)的性能.在眾多的互連網(wǎng)絡(luò)中，路和圈以其簡單的結(jié)構(gòu)成為最為基礎(chǔ)也最為重要的兩種網(wǎng)絡(luò)拓?fù)?在設(shè)計(jì)和選擇互連網(wǎng)絡(luò)時，路和圈的可嵌入性是一個非常

2、重要的因素.因此，互連網(wǎng)絡(luò)中路和圈的嵌入問題成為一個頗具吸引力的研究領(lǐng)域.
　　在實(shí)際的系統(tǒng)中，元器件和通信信道故障在所難免，對應(yīng)在互連網(wǎng)絡(luò)中，節(jié)點(diǎn)（頂點(diǎn)）故障和通信連線（邊）故障是不可避免的.這就要求在嵌入路和圈時，這些路和圈不能夠通過故障邊，即“規(guī)避嵌入”.另外，如果某些元器件或通信線路出現(xiàn)故障，那么原網(wǎng)絡(luò)將遭到一定程度的破壞.在此情形下，人們希望網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)性質(zhì)得到最大程度的保持.因此，網(wǎng)絡(luò)的容錯能力的度量成為一個重要的課

3、題.另一方面，在某些情形下，人們在選擇路由時，希望路由線路通過某些特定的信道，這就使得“指定嵌入”意義非凡.
　　本文共分六章.第一章介紹論文的研究內(nèi)容和意義、一些基本概念和性質(zhì)、相關(guān)的研究進(jìn)展及論文獲得的主要結(jié)果.第二章到第四章研究了k元n立方網(wǎng)絡(luò)中穿越某些指定子圖（線性森林和路）的圈嵌入問題.后兩章分別研究了Bubble-sort網(wǎng)絡(luò)和Star網(wǎng)絡(luò)的容錯能力.
　　在無故障k元n立方網(wǎng)絡(luò)中穿越指定線性森林的哈密爾頓圈的嵌

4、入問題上，我們在第二章證明了對于k元n立方網(wǎng)絡(luò)（n≥2，k≥3）中的任意一個邊數(shù)不超過2n-1的線性森林，這一k元n立方中可以嵌入一個穿越該線性森林的哈密爾頓圈.這推廣了Wang等在文獻(xiàn)[97]中的部分結(jié)果.
　　在只有故障邊的3元n立方網(wǎng)絡(luò)中穿越指定線性森林的哈密爾頓圈的嵌入問題上，我們在第三章證明了對于3元n立方網(wǎng)絡(luò)（n≥2）中的任意一個邊數(shù)m≤2n-1的線性森林L，若故障邊數(shù)不超過n-(「)m/2」-1，則這一3元n立方中可

5、以嵌入一個穿越L的無故障哈密爾頓圈.這一結(jié)論將Chen在文獻(xiàn)[59]中關(guān)于故障超立方網(wǎng)絡(luò)的指定嵌入的結(jié)果推廣到了3元n立方網(wǎng)絡(luò)中.
　　泛圈性是比哈密爾頓性更強(qiáng)的網(wǎng)絡(luò)性質(zhì).在k元n立方網(wǎng)絡(luò)中穿越指定路的泛圈性問題上，我們在第四章證明了對于k元禮立方網(wǎng)絡(luò)（n≥2為整數(shù)，k≥5為奇數(shù)）中的任意一個邊數(shù)不超過2n-1的路P，在該k元n立方中可以嵌入長從(k-1)(n-1)/2+k到kn且穿越P的圈.
　　網(wǎng)絡(luò)的容錯能力常用在出現(xiàn)一

6、定數(shù)目的故障頂點(diǎn)或故障邊的情況下，網(wǎng)絡(luò)的優(yōu)良拓?fù)湫再|(zhì)的保存程度來度量.在Bubble-sort網(wǎng)絡(luò)的容錯參數(shù)的研究方面，我們研究了在n-維的Bubble-sort網(wǎng)絡(luò)中使得所有的(n-k)-維子Bubble-sort網(wǎng)絡(luò)都發(fā)生故障所需要的最小頂點(diǎn)數(shù)FB（n，k）和最小邊數(shù)fB（n，k）.對于一些特殊的k，我們得到了這兩個參數(shù)的確切值.而在k=2時，我們使用一種巧妙的構(gòu)造映射的方法，得到了FB（n，2）和fB(n，2)的一個上界;并使用這

7、一思想，得到了FB（n，k）和fB（n，k）的一個上界.
　　連通度在一定程度上也可以度量互連網(wǎng)絡(luò)的容錯能力.在這一方面，由于在迭代的網(wǎng)絡(luò)發(fā)生故障時，網(wǎng)絡(luò)可能不再連通，在此情形下，我們希望故障互連網(wǎng)絡(luò)的每個連通分支都有和原網(wǎng)絡(luò)具有相同拓?fù)湫再|(zhì)的小規(guī)模的非故障的子網(wǎng).基于這種考慮，我們提出了迭代網(wǎng)絡(luò)的k-嵌入限制連通度的概念，并以Star網(wǎng)絡(luò)為例研究了嵌入限制連通度和其它一些連通度之間的關(guān)系;對于某些k，得到了Star網(wǎng)絡(luò)的k-嵌入