結(jié)構(gòu)故障下k—元n—立方體網(wǎng)絡的容錯哈密頓圈嵌入模擬實驗

呂雅麗

摘要：該文給出了在存在結(jié)構(gòu)故障的情況下，k-元n-立方體網(wǎng)絡容錯哈密頓圈嵌入的構(gòu)造算法及實驗結(jié)果。在這些實驗中，得到了相應的數(shù)據(jù)，為互連網(wǎng)絡多播算法的應用提供了依據(jù)。

關(guān)鍵詞：結(jié)構(gòu)故障；k-元n-立方體網(wǎng)絡；哈密頓圈

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2018）27-0217-02

1 概述

隨著高性能計算機在國防太空、生物制藥、天氣預報等領(lǐng)域應用的不斷深入，迫切需要速度更快的高性能計算機系統(tǒng)，進而開辟了并行分布式系統(tǒng)的研究領(lǐng)域。在并行分布式系統(tǒng)中，多處理器之間連接的拓撲結(jié)構(gòu)（稱為互連網(wǎng)絡）至關(guān)重要?；ミB網(wǎng)絡的選擇直接影響到并行分布式系統(tǒng)的性能和功能的實現(xiàn)。迄今，已有許多著名的互連網(wǎng)絡被相繼提出。例如：超立方體、類超立方體（BC網(wǎng)絡）、星圖、k-元n-立方體、蝶形圖等。k-元n-立方體網(wǎng)絡是一類重要的網(wǎng)絡。它具有許多優(yōu)良的性質(zhì)，例如直徑小、正則性、迭代性等。它包含一些重要的網(wǎng)絡拓撲作為它的子類，如環(huán)網(wǎng)絡，mesh，torus和超立方體網(wǎng)絡。目前許多并行分布式系統(tǒng)都是用k-元n-立方體網(wǎng)絡作為其連接模式，例如IBM BlueGene/L超級計算機、Cray T3D、Cray T3E以及J-machine等。

互連網(wǎng)絡可以表示為一個圖，圖的頂點表示系統(tǒng)中的處理器，邊表示處理器之間的通信鏈路。在實際的應用系統(tǒng)中，設備或通信鏈路發(fā)生故障是在所難免的。當網(wǎng)絡出現(xiàn)故障時，如何使得網(wǎng)絡能夠正常地工作，原網(wǎng)絡的性能如何得到最大程度的保持，即容錯性，是互連網(wǎng)絡研究必須考慮的問題。評估互連網(wǎng)絡容錯性的一個重要參數(shù)是連通度。圖G的連通度，記為[κ]（G），是使得圖G不連通或成為平凡圖所需刪除的最小頂點數(shù)。連通度常常用于評價一個系統(tǒng)的容錯性。這一評價存在明顯的缺點。它假設一個頂點的所有鄰接點可能同時出現(xiàn)故障。Esfahanian指出在實際多處理器系統(tǒng)中，一個無故障頂點的所有鄰接點同時出現(xiàn)故障的情況是幾乎不存在的[1]。為了討論更一般性的故障情形，Harary提出條件連通度的概念，對刪除故障頂點后的圖加上了一定的限制條件[2]。隨后，多種條件連通度被相繼提出并得以廣泛研究，比如g-超連通度與Rg-連通度。至今，關(guān)于容錯性的研究主要關(guān)注于單個頂點或者單個邊出現(xiàn)故障，沒有考慮一個頂點的狀態(tài)（故障與否）與它的鄰接點的狀態(tài)的關(guān)聯(lián)。實際應用中，故障點和邊的分布可能比較集中或局部化。同樣，隨著片上網(wǎng)絡的提出和發(fā)展，一個或一些頂點出現(xiàn)故障，就認為其所在“片”不可用。這些都啟發(fā)我們在研究容錯性時，不能僅考慮頂點故障，還應考慮圖的某些子圖或子結(jié)構(gòu)故障，這類故障稱為結(jié)構(gòu)故障。

Lin等提出了結(jié)構(gòu)故障的概念，定義了兩種新的連通度，結(jié)構(gòu)連通度和子結(jié)構(gòu)連通度，并對超立方體網(wǎng)絡的這兩種連通度進行了研究[3]。本文作者對k-元n-立方體網(wǎng)絡的結(jié)構(gòu)連通度進行了研究[4]，同時對其結(jié)構(gòu)故障情況下的哈密頓性質(zhì)進行了研究[5]。這里我們給出結(jié)構(gòu)故障下k-元n-立方體網(wǎng)絡的容錯哈密頓圈嵌入的模擬實驗。

2 相關(guān)定義

一條路是哈密頓路當且僅當它通過G中的每一個頂點一次且僅一次。經(jīng)過圖G中所有頂點一次且僅一次的圈稱為哈密頓圈。一個圖如果包含有哈密頓圈，則稱該圖是哈密頓的。一個圖中如果任意兩個頂點之間都存在哈密頓路，則稱該圖G是哈密頓連通的?；ミB網(wǎng)絡的哈密頓性質(zhì)在網(wǎng)絡通信中具有重要的應用，哈密頓路可以用于雙路徑或多路徑的路由算法，以減少或避免死鎖或擁塞的出現(xiàn)?？疾炀W(wǎng)絡可靠性和容錯性的一個重要方面就是其容錯哈密頓性質(zhì)，即故障網(wǎng)絡中是否存在無故障的哈密頓圈和哈密頓路，以及如何構(gòu)造。當k是偶數(shù)時，k-元n-立方體網(wǎng)絡是二分圖，任何二分圖都不是哈密頓連通的，所以本文我們討論k是奇數(shù)情形下k-元n-立方體網(wǎng)絡的容錯哈密頓圈嵌入問題。

3 容錯哈密頓圈的構(gòu)造算法

在一個存在結(jié)構(gòu)故障的圖[Qkn]中，我們首先選擇一個無故障頂點s作為起始頂點，用頂點集合C記錄圈中的頂點。將頂點s加入C，然后查找任何一個與s相鄰但未加入圈C的頂點s1； 然后將頂點s1加入C，然后查找任何一個與s1相鄰但未加入圈C的頂點s2，…，直到到達一個頂點t，其所有的無故障鄰接點都已加入C為止。此時如果C中包含所有無故障頂點并且頂點t是頂點s的鄰接點，則構(gòu)造成功，C為哈密頓圈。否則選擇頂點s的其它無故障鄰接點，執(zhí)行上述過程，直到構(gòu)造成功或者頂點s的所有無故障鄰接點均查找完畢，返回失敗。算法hamiltonCycle給出了我們的構(gòu)造方法的偽代碼。

5 總結(jié)

本文我們結(jié)合前期研究的理論基礎(chǔ)，給出了在存在結(jié)構(gòu)故障的情況下，k-元n-立方體網(wǎng)絡容錯哈密頓圈嵌入的構(gòu)造算法，并編程實現(xiàn)了算法并給出了實驗結(jié)果。在這些實驗中，我們得到了相應的數(shù)據(jù)，為互連網(wǎng)絡多播算法的應用提供了依據(jù)。

參考文獻：

[1] Abdol-Hossein Esfahanian. Generalized measures of fault tolerance with application to n-cube networks[J]. IEEE Transactions on Computers， 1989， 38（11）：1586-1591.

[2] Frank Harary. Conditional connecticity[J]. Networks， 1983， 13（3）：347-357.

[3] Cheng-Kuan Lin， Lili Zhang， Dajin Wang and Jianxi Fan. Structure connectivity and substructure connectivity of hypercubes[J]. Theoretical Computer Science， 2016， 634： 97-107.

[4] Yali Lv， Jianxi Fan， D. Frank Hsu， Cheng-Kuan Lin. Structure Connectivity and Substructure Connectivity of k-Ary n-Cube Networks[J]. Information Sciences， 2018， 433：115-124.

[5] Yali Lv， Cheng-Kuan Lin， Jianxi Fan. Hamiltonian Cycle and Path Embeddings in k-Ary n-Cubes Based on Structure Faults[J]. The Computer Journal， 2017， 60（2）：159-179.

[通聯(lián)編輯：代影]