一種基于圖論的網絡路由新算法

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

［關鍵詞］ 快速路由算法；正確性；合理性；并行

［中圖分類號］F270.7；TP393.03［文獻標識碼］A［文章編號］1673-0194（2008）14-0095-03

網絡路由新算法可以說是對圖論方法的豐富與補充，適合計算無向、有向以及無向有向交叉混合等各種類型和各種拓撲結構的通信網絡路由，且得到的路由結果不會出現閉環，完全符合通信傳輸規定。它不僅適合通信網絡路由計算，而且還可以用于像公路、鐵路交通網等各種類型網絡的路由計算。

1 網絡路由新算法

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

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

當i= j時，表示節點本身，則元素初始表達式為：mii=1；

當節點i到j方向無直接連接鏈路時，則元素初始表達式為：mij =0；

當Xij為節點i到j方向的直接連接鏈路時，則元素初始表達式為：mij = Xij；

當Xij1，Xij2，…，Xijy等為節點i到j方向存在的多條并聯直接連接鏈路時，則元素初始表達式為：mij = Xij1+Xij2+…+Xijy。

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

m′i3 = mik × mk3 + mi3。

當Mk與其他關聯分組逐一完成變換與整合運算后，刪除關聯分組Mk以及其他組中帶有k腳標的元素實現此次整合。完成一次整合后所剩余的關聯分組，不僅分組的數量減少一組，而且每組中元素的個數也減少一個。如圖1所示，整合后不僅分組Mk被刪除而消失，而且M′k關聯分組中元素m′ik也不再出現。

通過以上介紹可總結出進行一次變換與整合運算，各分組中元素的變換、整合計算公式為：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

通過以上討論可以得出結論：在整個計算過程中，算法不僅考慮了經過節點及鏈路的全面性和完整性，而且又避免了出現冗余和閉環問題，證明算法完全能夠保證正確且合理地得到網絡兩節點間全部路由。

3 新算法并行運算的可行性

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

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

主要參考文獻

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

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

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

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