一種基于圖論的網(wǎng)絡(luò)路由新算法

［摘 要］ 本文介紹了一種易于多處理器并行運(yùn)算的快速路由算法，然后給出了新算法的正確性與合理性論證，最后對該算法并行運(yùn)算的可行性進(jìn)行了論述。

［關(guān)鍵詞］ 快速路由算法；正確性；合理性；并行

［中圖分類號］F270.7；TP393.03［文獻(xiàn)標(biāo)識碼］A［文章編號］1673-0194（2008）14-0095-03

網(wǎng)絡(luò)路由新算法可以說是對圖論方法的豐富與補(bǔ)充，適合計算無向、有向以及無向有向交叉混合等各種類型和各種拓?fù)浣Y(jié)構(gòu)的通信網(wǎng)絡(luò)路由，且得到的路由結(jié)果不會出現(xiàn)閉環(huán)，完全符合通信傳輸規(guī)定。它不僅適合通信網(wǎng)絡(luò)路由計算，而且還可以用于像公路、鐵路交通網(wǎng)等各種類型網(wǎng)絡(luò)的路由計算。

1 網(wǎng)絡(luò)路由新算法

新算法采用各節(jié)點(diǎn)的關(guān)聯(lián)分組之間變換、整合以及逐步刪除所有中間節(jié)點(diǎn)分組方法計算。對于具有n個節(jié)點(diǎn)的網(wǎng)絡(luò)只需（n-2）次運(yùn)算，就可以求出兩個節(jié)點(diǎn)之間所有路由，且結(jié)果中不會出現(xiàn)違反通信傳輸規(guī)則的閉環(huán)路由。算法要求的唯一已知條件是節(jié)點(diǎn)之間的直接連接關(guān)系。算法唯一涉及的運(yùn)算是邏輯代數(shù)運(yùn)算。具體計算步驟、方法與規(guī)則如下：

（1）建立關(guān)聯(lián)分組并確定元素的初始表達(dá)式。設(shè)網(wǎng)絡(luò)有n個節(jié)點(diǎn)，節(jié)點(diǎn)序號為1，2，…，n。假設(shè)1為源節(jié)點(diǎn)，n為目的節(jié)點(diǎn)。建立除了節(jié)點(diǎn)n以外的（n-1）個節(jié)點(diǎn)的關(guān)聯(lián)分組，M1 = [m12，m13，…，m1n ]，M2= [m22，m23，…，m2n ]，…，Mn - 1 = [m（n - 1） 2，m（n - 1） 3，…，m（n - 1） n ]。其中，Mi表示i節(jié)點(diǎn)的關(guān)聯(lián)分組，mij為該分組中的元素，代表i和j兩節(jié)點(diǎn)的連接關(guān)系。i和j的取值范圍為：i= 1，2，…，n-1； j=2，3，…，n。分組中元素mi INT（RiRj）= ×100。j的初始表達(dá)式按照如下定義得到：

當(dāng)i= j時，表示節(jié)點(diǎn)本身，則元素初始表達(dá)式為：mii=1；

當(dāng)節(jié)點(diǎn)i到j(luò)方向無直接連接鏈路時，則元素初始表達(dá)式為：mij =0；

當(dāng)Xij為節(jié)點(diǎn)i到j(luò)方向的直接連接鏈路時，則元素初始表達(dá)式為：mij = Xij；

當(dāng)Xij1，Xij2，…，Xijy等為節(jié)點(diǎn)i到j(luò)方向存在的多條并聯(lián)直接連接鏈路時，則元素初始表達(dá)式為：mij = Xij1+Xij2+…+Xijy。

（2）關(guān)聯(lián)分組間的變換與整合運(yùn)算。算法進(jìn)行一次變換與整合運(yùn)算所采取的方法、遵循的規(guī)則為：假設(shè)準(zhǔn)備要刪除編號為k（k≠1）的中間節(jié)點(diǎn)分組Mk，則應(yīng)以Mk分組為參考，按照圖1箭頭所示的順序，對其他分組Mi （i=1，2，…，n-1，i≠k）中的元素進(jìn)行變換運(yùn)算。Mi分組中除了畫圈的元素Mik之外，組中的其他元素均需要進(jìn)行變換與整合運(yùn)算。每兩個首尾連續(xù)的箭頭為一個變換與整合單元組，從畫圈的元素Mik出發(fā)，第一個箭頭代表先進(jìn)行邏輯“與”運(yùn)算，第二個箭頭代表再進(jìn)行邏輯“或”運(yùn)算。圖中大箭頭代表變換與整合運(yùn)算后關(guān)聯(lián)分組Mi發(fā)生的變化，即Mk與Mi整合運(yùn)算后的結(jié)果M′i。以兩個虛線箭頭所示的變換與整合單元組運(yùn)算規(guī)律為例，變換與整合后的元素m′i3為：

m′i3 = mik × mk3 + mi3。

當(dāng)Mk與其他關(guān)聯(lián)分組逐一完成變換與整合運(yùn)算后，刪除關(guān)聯(lián)分組Mk以及其他組中帶有k腳標(biāo)的元素實(shí)現(xiàn)此次整合。完成一次整合后所剩余的關(guān)聯(lián)分組，不僅分組的數(shù)量減少一組，而且每組中元素的個數(shù)也減少一個。如圖1所示，整合后不僅分組Mk被刪除而消失，而且M′k關(guān)聯(lián)分組中元素m′ik也不再出現(xiàn)。

通過以上介紹可總結(jié)出進(jìn)行一次變換與整合運(yùn)算，各分組中元素的變換、整合計算公式為：

m′ij = mik × mkj +mij（1）

式中，mij、mik、mkj表示整合前分組中的元素表達(dá)式，

m′ij代表整合之后分組中的新元素表達(dá)式，其中，i=1，2，…，n-1； j=2，3，…，n，且i， j≠k。

需要說明的是，變換運(yùn)算及整合過程中必須利用邏輯化簡公式及規(guī)則簡化每一個元素表達(dá)式，使之始終保持為最簡“與或”邏輯表達(dá)式。

（3）求得兩節(jié)點(diǎn)間全部路由。對于有n個節(jié)點(diǎn)的網(wǎng)絡(luò)，除了源節(jié)點(diǎn)和目的節(jié)點(diǎn)以外，將有（n-2）個中間節(jié)點(diǎn)。算法需要按照第（2）步介紹的方法，逐一刪除所有中間節(jié)點(diǎn)的關(guān)聯(lián)分組，最終只剩下源節(jié)點(diǎn)的關(guān)聯(lián)分組，且該組也僅剩下一個元素。此時元素表示的就是源節(jié)點(diǎn)和目的節(jié)點(diǎn)連接關(guān)系，其“與或”邏輯表達(dá)式的每一個邏輯乘積項(xiàng)就是一條路由，所有邏輯乘積項(xiàng)的集合就是要尋找的源節(jié)點(diǎn)到目的節(jié)點(diǎn)間全部路由。需要說明的是，刪除（n-2）個中間節(jié)點(diǎn)分組的先后順序可以任意，并不會影響最終計算結(jié)果。

2 新算法正確性與合理性論證

由于算法是按照圖1所示方式、采用公式（1）逐步進(jìn)行變換與整合及刪除計算，并且在計算過程中利用邏輯化簡公式及規(guī)則，不斷化簡元素表達(dá)式，使其始終保持為最簡“與或”邏輯式，因此，如果采用這些運(yùn)算方法和運(yùn)算手段保證能得到所需結(jié)果，則算法的正確性就得到證明。論證過程如下：

建立各節(jié)點(diǎn)關(guān)聯(lián)分組后，第一次取出任意一個中間節(jié)點(diǎn)，假如k節(jié)點(diǎn)關(guān)聯(lián)分組進(jìn)行變換與整合運(yùn)算。由于，這時元素mik表示從節(jié)點(diǎn)i到k的直接連接關(guān)系，而元素mkj又表示從節(jié)點(diǎn)k到j(luò)的直接連接關(guān)系，因此，很明顯按照邏輯與運(yùn)算mik × mkj 計算所得到的結(jié)果，就是節(jié)點(diǎn)i需通過節(jié)點(diǎn)k才能達(dá)到節(jié)點(diǎn)j的連接路由。如果再把節(jié)點(diǎn)i和j之間直接連接路由Mij考慮進(jìn)去，并表示為邏輯或的方式，那么按照公式（1）計算，得到整合后的元素m′ij必然包含從節(jié)點(diǎn)i到j(luò)直接的連接以及需經(jīng)過中間節(jié)點(diǎn)k串聯(lián)連接的路由。

因此得到第一個結(jié)論，即按照圖1所示方式，當(dāng)用Mi組中元素mik同k節(jié)點(diǎn)關(guān)聯(lián)分組Mk中除mkk之外的其他元素分別進(jìn)行邏輯“與”運(yùn)算，并用該計算結(jié)果再分別同Mi組中位置相對應(yīng)的元素進(jìn)行邏輯“或”，所得到變換與整合后的關(guān)聯(lián)分組M′i（其中m′ik元素將不再出現(xiàn)）中所有元素，不僅存在按元素下腳標(biāo)標(biāo)注順序的直接連接路由，而且還包含有需經(jīng)過中間節(jié)點(diǎn)k的串聯(lián)連接路由。

按照該方法用mk 處理完所有分組后，各分組中所有元素表達(dá)式必然都會包含直接連接路由以及需經(jīng)過中間節(jié)點(diǎn)k而發(fā)生的串聯(lián)連接路由。也就是把mk 分組中元素所表示的連接完全整合到其他分組中，使得這些分組中每個元素表達(dá)式都含有需經(jīng)過k節(jié)點(diǎn)的串聯(lián)連接路由。

因此得到第二個結(jié)論，即按照該方法完成所有分組與mk分組的變換與整合之后，刪除k節(jié)點(diǎn)關(guān)聯(lián)分組mk，以及刪除其他原分組Mi 中表示與k節(jié)點(diǎn)連接的元素mij（i =1，2，…，n-1），完全能夠保證各節(jié)點(diǎn)同k節(jié)點(diǎn)發(fā)生的連接關(guān)系，不丟失地被合理整合到新關(guān)聯(lián)分組M′i的各元素m′ij（i =1，2，3，…，n-1； j=2，3，…，n；i， j≠k）之中。

如果刪除節(jié)點(diǎn)數(shù)量沒達(dá)到（n-2）個，就需要繼續(xù)刪除其他中間節(jié)點(diǎn)。為了便于討論第二次變換及整合運(yùn)算， 把求解公式改寫為“m″ij = m′ik ×m′kj +m′ij”形式，即用元素上角標(biāo)注區(qū)分變換與整合運(yùn)算進(jìn)行的次數(shù)。元素下腳標(biāo)中的k表示本次處理要刪除的中間節(jié)點(diǎn)編號。

由于元素m′ik、m′kj以及m′ij經(jīng)過第一次變換與整合處理，已包含有從節(jié)點(diǎn)i到j(luò)直接的和需經(jīng)過中間節(jié)點(diǎn)k串聯(lián)連接的路由。因此按照“m′ik ×m′kj”計算，所得到的結(jié)果必然包含從節(jié)點(diǎn)i到j(luò)需經(jīng)過節(jié)點(diǎn)h串聯(lián)路由，以及需經(jīng)過兩個節(jié)點(diǎn)k與h串聯(lián)連接路由。如果再考慮到邏輯或元素m′ij包含了從節(jié)點(diǎn)i到j(luò)直接連接的路由以及需經(jīng)過k節(jié)點(diǎn)的串聯(lián)連接的路由，那么得到整合后新元素m″ij（i=1，2，…，n-1； j=1，2，…，n。i， j≠k；i， j≠h）將可能包含4種連接形式的路由， 分別為：從節(jié)點(diǎn)i到j(luò)直接連接路由，只需經(jīng)過中間節(jié)點(diǎn)k串聯(lián)連接路由，只需經(jīng)過中間節(jié)點(diǎn)h串聯(lián)連接路由， 以及需要經(jīng)過k， h兩個中間節(jié)點(diǎn)串聯(lián)連接路由。當(dāng)然這4種連接形式的路由是否在表達(dá)式中都出現(xiàn)， 完全取決于網(wǎng)絡(luò)是否存在這樣的連接。

討論至此完全可以得出第三個結(jié)論， 即公式（1）中邏輯“與”運(yùn)算式保證被刪除的中間節(jié)點(diǎn)所發(fā)生的連接完全被整合到其他分組中而形成串聯(lián)路由，且隨著被刪除節(jié)點(diǎn)的增加，余下的關(guān)聯(lián)分組中元素表達(dá)式將逐步積累并保持與所有被刪除節(jié)點(diǎn)相關(guān)的串聯(lián)連接路由， 同時公式（1）中的邏輯“或”運(yùn)算式保證將保留不需要經(jīng)過此次被刪除節(jié)點(diǎn)就已存在的連接路由。因此按此方式進(jìn)行變換與整合運(yùn)算，當(dāng)所有中間節(jié)點(diǎn)被刪除后， 必然能夠得到從源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間所有可能連接路由。

再有，在變換與整合運(yùn)算過程中，算法是按照逐步刪除節(jié)點(diǎn)方式運(yùn)算，并且利用邏輯化簡公式及規(guī)則不斷化簡分組中元素的表達(dá)式， 使表達(dá)式始終保持為最簡“與或”邏輯形式，即元素表達(dá)式中邏輯乘積項(xiàng)個數(shù)為最少且每個邏輯乘積項(xiàng)變量數(shù)最少。

根據(jù)最簡“與或”邏輯表達(dá)式的性質(zhì)，可得到第四個結(jié)論，即由于每個邏輯乘積項(xiàng)包含連接鏈路數(shù)量最少，因此保證不會出現(xiàn)從某一個節(jié)點(diǎn)出發(fā)多次重復(fù)經(jīng)過某一條或某幾條鏈路又返回到該節(jié)點(diǎn)的閉環(huán)問題。又由于邏輯乘積項(xiàng)個數(shù)為最少， 因此保證不存在冗余連接鏈路及冗余路由問題， 即每條路由必然包含有只屬于它的鏈路， 也不會產(chǎn)生不構(gòu)成路由的鏈路出現(xiàn)在乘積項(xiàng)中， 更不會出現(xiàn)較短路由被較長回路的路由所包含的冗余問題。再由于算法是按照逐步刪除節(jié)點(diǎn)方式運(yùn)算， 避免了多次重復(fù)經(jīng)過某節(jié)點(diǎn)而形成閉環(huán)問題，因此，最終得到的源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間的路由，必然是最簡的且不存在閉環(huán)。

通過以上討論可以得出結(jié)論：在整個計算過程中，算法不僅考慮了經(jīng)過節(jié)點(diǎn)及鏈路的全面性和完整性，而且又避免了出現(xiàn)冗余和閉環(huán)問題，證明算法完全能夠保證正確且合理地得到網(wǎng)絡(luò)兩節(jié)點(diǎn)間全部路由。

3 新算法并行運(yùn)算的可行性

所謂算法適合多處理器并行運(yùn)算， 就是指算法可以方便地做到在每個運(yùn)算階段， 可以把計算任務(wù)劃分為幾部分，交由多個處理器去完成，各處理器運(yùn)算不存在前后相互依賴關(guān)系，工作是相對獨(dú)立的，把各處理器的運(yùn)算結(jié)果匯總，就得到本階段計算結(jié)果。

從算法的運(yùn)算步驟和運(yùn)算規(guī)律上可以明顯看出，每一次變換與整合運(yùn)算都可以作為一個處理階段，在每個處理階段參加計算的各分組僅與被刪除分組有關(guān)。如果把關(guān)聯(lián)分組分成幾個相對獨(dú)立的組合，并把被刪除分組多復(fù)制幾個，按照向量分配方法分派給這幾個相對獨(dú)立的組合， 就很容易做到每一次運(yùn)算各組合之間的運(yùn)算互不相關(guān)， 因而可以很方便地交由不同的處理器完成。因此， 說明該算法采用并行運(yùn)算是完全可行的。

主要參考文獻(xiàn)

[1] 蘭家隆，劉軍. 應(yīng)用圖論及算法[M]. 成都:電子科技大學(xué)出版社，1995.

[2] 肖位樞. 圖論及其算法[M]. 北京:航空工業(yè)出版社，1993.

[3] 郝柏林，張淑譽(yù). 生物信息學(xué)手冊[M]. 上海:上海科學(xué)技術(shù)出版社，2000.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”