本文選題：交叉立方體　切入點(diǎn)：扭N立方體　出處：《廣西大學(xué)》2014年碩士論文

【摘要】：進(jìn)入信息化社會(huì)后,強(qiáng)大的網(wǎng)絡(luò)需求一直督促網(wǎng)絡(luò)結(jié)構(gòu)不斷發(fā)生變化。為了滿足這一需求,提出了立方體網(wǎng)絡(luò)的概念,其中超立方體網(wǎng)絡(luò)是一種最受歡迎的新型網(wǎng)絡(luò)結(jié)構(gòu)。很多學(xué)者針對(duì)超立方體網(wǎng)絡(luò)進(jìn)行深入研究,并得到了很多關(guān)于其的優(yōu)秀結(jié)論。但是隨著研究的深入,也暴露了超立方體網(wǎng)絡(luò)的一些缺陷,對(duì)其進(jìn)行改進(jìn)得到了諸多變體結(jié)構(gòu)。本文在結(jié)合交叉立方體和扭N立方體兩種結(jié)構(gòu)的基礎(chǔ)上提出了一種新型網(wǎng)絡(luò)結(jié)構(gòu),在各方面都有改進(jìn)。具體工作如下： (1)本文通過研究交叉立方體和扭N立方體的結(jié)構(gòu),提出了交叉扭立方體的定義,并給出了相應(yīng)的拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)圖,證明了交叉扭立方體部分子網(wǎng)與超立方體網(wǎng)絡(luò)同構(gòu),同時(shí)研究了交叉扭立方體的網(wǎng)絡(luò)直徑、連通度等問題。通過上述拓?fù)浣Y(jié)構(gòu)基本性質(zhì)的研究,得到了交叉扭立方體的性能優(yōu)于扭N立方體的重要結(jié)論。 (2)為了更深入研究交叉扭立方體模擬其他網(wǎng)絡(luò)結(jié)構(gòu)的能力,本文研究交叉扭立方體互連網(wǎng)絡(luò)上的圈嵌入問題,證明了任何長度為L(3L≤2n)的圈均能以擴(kuò)張1嵌入到交叉扭立方體中,同時(shí)證明了交叉扭立方體是Hamilton連通圖,然后提出時(shí)間復(fù)雜度為O(L)的交叉扭立方體的圈嵌入算法。 (3)由于圖嵌入主要包括圈和樹嵌入兩個(gè)方面,所以在研究圈嵌入后,本文選擇繼續(xù)研究樹的嵌入性質(zhì)。首先引入完全二項(xiàng)樹和完全四項(xiàng)樹的概念,其次給出交叉扭立方體的3D視圖,最后得出了N階完全二項(xiàng)樹可以以擴(kuò)張為2嵌入到N維交叉扭立方體中的重要結(jié)論,并且證明了N階完全四項(xiàng)樹可以以擴(kuò)張2嵌入到2N-1維的交叉扭立方體中的結(jié)論。 (4)在之前已有的研究結(jié)果基礎(chǔ)上,本文更加深入研究此種變體的路由屬性。首先通過研究交叉扭立方體的局部連通性來確定其容錯(cuò)性,證明了它即使在錯(cuò)誤節(jié)點(diǎn)分布不均勻的情況下仍然能夠保持網(wǎng)絡(luò)的正常工作；其次根據(jù)其結(jié)構(gòu)特征提出適合此種結(jié)構(gòu)的路由算法,證明路由算法找到的路徑長度接近兩個(gè)節(jié)點(diǎn)間的最短路徑長度,并且經(jīng)過分析計(jì)算出算法的時(shí)間復(fù)雜度為O(n),通過對(duì)比發(fā)現(xiàn)提出的新算法要優(yōu)于Efe提出的交叉立方體路由算法。
[Abstract]:After entering the information society, the strong network demand has been urging the network structure to change constantly.In order to meet this demand, the concept of cube network is proposed, in which hypercube network is the most popular new network structure.Many scholars have studied hypercube network deeply and got many excellent conclusions about it.However, with the development of research, some defects of hypercube network have been exposed, and many variants have been obtained by improving the hypercube network.In this paper, a new network structure is proposed based on the combination of cross cube and torsional N cube, which has been improved in all aspects.The specific work is as follows:1) by studying the structure of crossed cube and twisted N cube, the definition of cross twisted cube is proposed, and the corresponding topological structure network diagram is given. It is proved that the partial subnet of cross twisted cube and the network of hypercube are isomorphic.At the same time, the network diameter and connectivity of cross-twisted cubes are studied.Based on the study of the basic properties of the above topological structure, it is concluded that the performance of the crossed twisted cube is better than that of the twisted N-cube.In order to further study the ability of cross-twisted cubes to simulate other network structures, the problem of loop embedding on cross-twisted cubes interconnection networks is studied in this paper.It is proved that any cycle of L ~ 3L 鈮，

本文編號(hào)：1719796