強定向圖的強距離及網(wǎng)格的容錯自適應路由.pdf

1、1736年，Euler解決哥尼斯堡七橋問題標志著圖論的誕生.今天，圖論在計算機科學、通訊科學、化學、生物學、物理學等學科的應用已經(jīng)是眾所周知的。 在交通系統(tǒng)中應用單行道不僅是改善城市交通堵塞狀況的經(jīng)濟而有效的方法，而且提高了交通安全，減輕了交通管理工作.單行道問題的圖論模型最初由Robbins提出，單行道問題可以歸結為圖的定向問題.Chartrand等人提出了強定向圖中強距離的概念.設G是一個二邊連通圖，D是G的一個強定向.D中

2、任兩個頂點u，υ間的強距離sd(u，υ)為D中包含u，υ的最小強有向子圖的弧數(shù).點u的強離心率se(u)定義為u與圖中其他所有點的強距離的最大值.強定向圖D的強半徑srad(D)(強直徑sdiarn，(D))定義為圖中所有點的強離心率的最小值(最大值).二邊連通圖G的最小強半徑srad(G)(最大強半徑SRAD(G))為G的所有強定向圖的強半徑的最小值(最大值).相應地，G的最小強直徑sdiam(G)(最大強直徑SDIAM(G))為G的

3、所有強定向圖的強直徑的最小值(最大值).確定一個圖G的srad(G)、SRAD(G)、sdiam(G)和SDIAM(G)這四個參數(shù)的問題是圖論研究中有重要應用背景的前沿課題。 由于對計算機運算性能日益增長的需求，多處理器計算機正在被廣泛使用.網(wǎng)格結構是多處理器計算機系統(tǒng)互連的拓撲結構，它已被證明擁有許多吸引人的特性.并行計算機使用網(wǎng)格作為基本架構已有多年.網(wǎng)絡中的路由是指將消息從源節(jié)點(處理器)經(jīng)過一些中間節(jié)點最終傳遞到目標節(jié)點

4、的過程.當網(wǎng)絡中存在故障時，設計路由算法使消息繞過故障點最終到達目標點具有客觀重要意義。 本文研究強定向圖的強距離及網(wǎng)格的容錯自適應路由.對滿足Ore條件的圖，給出了最小強半(直)徑、最大強半(直)徑的上、下界；對笛卡爾乘積圖G1×G2，確定了G1×G2的最小強半(直)徑與G1×G2的半(直)徑以及G1和G2的最小強直徑之間的關系，并進而確定了一些特殊笛卡爾乘積圖的最小強直徑的值，確定了SDIAM(Km×Kn)的值，SDIAM(

5、Pm×Pn)的下界，SRAD(Km×Kn)和SRAD(Pm×Pn)相應的上、下界.對于以網(wǎng)格作為并行計算機拓撲結構的多處理器計算機系統(tǒng)的容錯自適應路由的研究，本文提出了裂痕故障塊模型，在此模型下，所有的故障都包含在塊的內部.當塊形成時，可以由每個節(jié)點的狀態(tài)判斷該點所處的位置-在塊的邊界、塊的內部或塊的外部.對塊的內部點及邊界點設計了新的特殊路由，對塊外部的點仍采用一般路由方案，并證明所給的路由方案一定能克服活鎖狀態(tài)將消息送到目標節(jié)點。

6、 全文共分為五章。 在第一章，我們首先給出本文的基本概念和符號，綜述了本文研究領域的已有結果和本文的主要結論。 在第二章，我們研究Ore圖G的最小強半(直)徑srad(G)(sdiam(G))、最大強半(直)徑sRAD(G)(sDIAM(G))的上、下界，得到以下結論：g≤srad(G)≤5， g≤sdiam，(G)≤9，[n2]≤SRAD(G)≤n， n≤SDIAM(G)≤n+1，其中n，g分別為G的頂點數(shù)和圍長

7、。 在第三章，研究了笛卡爾乘積圖G1×G2的最小強半(直)徑，證明了如下結果：srad(G1×G2)=2r(G1×G2)，sdiam，(G1×G2)≤min{sdiam(G1)+sdiam(G2)，2d(G1×G2)，4r(G1×G2))；給出sdiam(G1×G2)=2d(G1×G2)成立的三個充分條件，并由所給出的充分條件確定了一些特殊笛卡爾乘積圖的最小強直徑的值；確定了SDIAM(Km×Kn)的確切值，SDIAM(pM×P

8、n)的下界， SRAD(Km×Kn)和SRAD(Pm×Pn)的上、下界。 在第四章，我們給出了二維網(wǎng)格的容錯自適應路由.當網(wǎng)格中存在故障時，原有的貪婪路由方案不一定能將信息送到目標點，可能陷入活鎖狀態(tài)(信息在網(wǎng)絡的某子網(wǎng)絡循環(huán)，到不了目標點).為此，我們設計了算法，用以構造網(wǎng)絡中的不交的極小故障塊，使得塊的邊界和塊外部沒有故障，同時，當塊形成時每個節(jié)點有相應的穩(wěn)定狀態(tài)，可以根據(jù)點的穩(wěn)定狀態(tài)判斷它的位置一位于塊的外部、塊的邊界或塊

9、的內部.在我們的容錯路由方案里，處于塊邊界及內部的點都有特殊的路由，并證明了給出的路由方案一定能克服潛在的活鎖狀態(tài)，將信息送到目標點.與這方面的現(xiàn)有算法最大的區(qū)別在于，在我們的方案里，故障塊內部的點也可以成為目標點或源點.這是網(wǎng)絡容錯性方面的一個顯著的提高。 在第五章中，我們將二維網(wǎng)格中的故障塊模型推廣到多維網(wǎng)格中，給出相應的容錯自適應路由，并證明了所給出的自適應路由不會產生活鎖狀態(tài)。 另外，在每一章中，我們都給出了相關