基于ｋ－最短路由的ｍｅｓｈ光網絡ｐ圈構造方法

摘要：P－cycle是mesh光網絡中一種十分優秀的保護算法，圈構造算法是p圈法設計的前提。首先介紹了圈的概念及常見圈構造算法和基于k－最短路由的p圈啟發式算法，提出了基于k－最短路改進metaDijkstra的圈構造算法。實驗仿真表明該方案比較適合網狀光網絡中的圈構造。

關鍵詞：網狀；光網絡；p圈；保護 ；k－最短路由；圈構造

網絡生存性(network survivability)是指網絡恢復受到失效影響的業務的能力，是設計網絡特別是骨干網絡時需要考慮的重要問題。隨著DWDM技術不斷發展，復用的光信道數不斷增加，光傳送網的承載容量和傳輸速率急劇擴大，鏈路傳輸速率已達數10 Gbps，這使光網絡的可靠性和生存能力受到很大的挑戰。在眾多的保護算法中，p圈法(preconfiguration cycle，p－cycle)是一種十分優秀的路由保護算法。它既具有環型網絡通路倒換快的優點，又具有網狀網絡保護設計一樣的容量利用率高的優點[1]。而在p圈法設計過程中，首先要做的事情就是在網狀光網絡中構造出一系列容量利用率高的圈。

1圈的概念及常見p圈構造算法

一個圖，如果它既沒有自環(self－loop)也沒有重邊(parallel edge)，則稱該圖為簡單圖。本文討論的光纖網絡就是典型的簡單圖。若簡單圖G中一條途徑W的邊互不相同，則稱為跡；如果途徑W的頂點互不相同，則稱為路。而起點與終點重合的通路叫做圈或者回路。如果一個圈除了其起點和終點重合外其他所有的節點都不重復，稱為簡單圈。

常用的圈構造算法有圈矢量空間法（circuit vector space）、回溯法（backtracking algorithms）以及其他啟發式算法（heuristics algorithms）[2]。由于連通圖的任一回路均可用若干基本圈的和來表示，圈矢量空間法首先通過求基本回路的算法找出連通圖G的所有基本圈，再利用基本圈的線性組合來構造連通圖G中的其他非基本圈，因此圈矢量空間法通常需要枚舉所有的圈。

回溯法也稱為試探法，該方法是根據約束條件逐一枚舉和檢驗，當發現當前路徑不可能達到目標時，就退回一步重新選擇。這樣走不通就退回再走稱為回溯，而滿足回溯條件的某個狀態的點稱為回溯點。實際上常用的回溯構造圈法有DFS深度優先搜索及Johnson算法等，如果要尋找到最優圈，同樣需要枚舉所有的圈。

啟發式算法與傳統需要枚舉所有圈的方法不同，只需要根據約束條件找到其中一部分性能比較好的圈，因此運算速度比傳統需要枚舉的方法快得多，并且找到的圈具有良好的性能。常用的啟發式算法有環節點路由算法（ring node routing）、非成環覆蓋（incapacitated ring cover）、節點分離路由（node disjoint routing）等。

2基于k－最短路由的p圈構造啟發式算法

2．1常用的k－最短路徑算法

k－最短路徑算法可以同時求出長度從小到大排列的k條最短路。k－最短路徑問題有兩種解決思路：a）在最短路徑(稱為第一最短路)的基礎上，求解一條次最短路徑(稱為第二最短路)，重復此過程k-1次，就可得到k條最短路徑，此方法稱為遞推求解法；b)直接求出k條最短路徑，稱為直接求解法。

4結束語

p圈法設計過程中，首先要做的事情就是在網狀光網絡中構造圈。本文提出了基于改進metaDijkstra的圈構造算法，并且對比分析了k－最短路Ranking算法和k－最短路改進meta－Dijkstra算法，得出結論k－最短路改進meta－Dijkstra算法更適合圈構造算法的需要，而且比metaDijkstra算法能構造更多的圈，只是算法的執行效率稍微有所下降。為了使圈的性能更加適合p圈法設計，可以在這些圈上實施圈擴張算法，使其具有更好的性能。

參考文獻：

［1］GROVER W E，DOUCETTE J.New option and insights for survivable transport networks[J].IEEE Communications Magazine，2002，40(1):34-41.

［2］ZHANG Han－xi，YANG O.Finding protection cycles in DWDM networks[C]//Proc of IEEE International Conference on Communications.New York:IEEE，2002:2756-2760.

［3］劉家壯，王建方.網絡最優化[M].武漢:華中工學院出版社，1987:50-56.

［4］SKISCIM C C，GOLDEN B L.Computing k－shortest path lengths in Euclidean networks [J].Networks，1987，17(3):341-352.

［5］MacGREGIR M H，GROVER W D.Optimized k－shortest paths algorithm for facility restoration[J].Software － Practice Experience，1994，24(9):823-834.

［6］MARTINS E Q V，OASCOAL M，SANTOSJ L E.A new algorithm for ranking loopless paths［EB/OL］.[1997].http://www.mat.uc.pt/~eqvm.

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