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

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

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

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

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

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

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

7、。 在第三章，研究了笛卡爾乘積圖G1×G2的最小強(qiáng)半(直)徑，證明了如下結(jié)果：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)成立的三個(gè)充分條件，并由所給出的充分條件確定了一些特殊笛卡爾乘積圖的最小強(qiáng)直徑的值；確定了SDIAM(Km×Kn)的確切值，SDIAM(pM×P

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

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