[發明專利]一種基于分層圖的靜態選路與波長分配方法

有效

• 申請號: 201010109610.7
• 申請日: 2010-02-12
• 公開（公告）號: CN101808254A
• 公開（公告）日: 2010-08-18
• 發明（設計）人: 王汝言;張普釗;吳大鵬;黃勝;隆克平
• 申請（專利權）人: 重慶郵電大學
• 主分類號: H04Q11/00
• 分類號: H04Q11/00;H04J14/02;G06F17/50
• 代理公司: 重慶市恒信知識產權代理有限公司 50102
• 代理人: 劉小紅

1.一種基于分層圖的靜態選路與波長分配方法，其特征在于，根據公式?確定使用波長總數F，其中，根據公式?判斷是否使用了新的波長，根據公式?限定一次路由請求所經過的鏈路數最多為?，根據公式?限定各節點波長的使用情況，根據公式?限定出口節點處理波長數最多為|W|，根據公式?限定在一條光纖中最多可用|W|個波長，根據公式?限定入口節點處理波長數最多為|W|，通路P_i使用ij鏈路中的光纖則?為1，否則為0；分層圖生成模塊為網絡拓撲G(V,E,W,F)生成分層圖模型矩陣LG(V^*,E^*)，分層圖模型的每一層為一個波長層，編號為λ₁,λ₂,...λ?_W；靜態業務生成模塊為網絡隨機生成業務請求集合矩陣D＝{D₁,D₂,...,D_|D|}，要求矩陣D中的每個業務都包括源節點s_i和目的節點d_i，并且業務從源節點s_i到其它節點的概率均等，目的節點d_i的選取服從均勻分布；業務選擇模塊從生成的業務請求集合矩陣中選取單個業務；選路與波長分配模塊在生成的分層圖模型上對選取業務Di＝(s_i,d_i)采用最短路徑算法、或隨機選取算法、或最長路徑優先算法進行選路和波長分配運算，確定光通路矩陣和波長使用數，其中，L為網絡中的鏈路數，V表示節點集合，E表示兩條光纖形成的雙向鏈路集合，W為每條光纖所包含的波長數。

2.根據權利要求1所述的靜態選路與波長分配方法，其特征在于，生成分層圖模型矩陣具體包括：將網絡拓撲復制W份，形成分層圖中的W層，所對應的分層圖模型矩陣為LG(V^*,E^*)，將網絡拓撲中節點集合V中的任一節點v_i對應分層圖中各層的節點?網絡拓撲中雙向鏈路集合E中的鏈路e_i對應分層圖中各層的鏈路

3.根據權利要求1所述的靜態選路與波長分配方法，其特征在于，選路方法如采用最短路徑算法，對于每個業務，首先找到該業務在物理拓撲上的最短路徑，然后按最短路徑在波長分層圖上對其進行選路，具體包括步驟，靜態業務生成模塊為D中的每一個業務進行編號：即D＝{D?₁,D₂,...,D_|D|}按編號順序從業務矩陣D中選取業務，對于D中的每個業務D_i，在網絡拓撲上為其尋找最短路徑h_i，并從中選定可用路徑p_i；選路與波長分配模塊在生成的分層圖上對選取的業務D_i=(s_i,d_i)進行選路和波長分配運算，每分配一個波長，按F=F+1更新波長占用總數F；對于業務D_i，在分層圖上按照從λ₁層到λ_|D|層的順序，首先在λ₁層檢查其最短路徑h_i是否可用，若h_i在前λ_m-1層均不可用，但第λ_m層可用，則更新波長分層圖LG(V^*,E^*)和D，使E^*=E^*-p_i，D=D-D_i，該請求被分配的波長為λ_m；若F≤m,則F=m,否則，F保持不變，直到D=φ。