[發(fā)明專利]一種基于分層圖的靜態(tài)選路與波長分配方法

有效

• 申請?zhí)枺?/td>: 201010109610.7
• 申請日: 2010-02-12
• 公開（公告）號: CN101808254A
• 公開（公告）日: 2010-08-18
• 發(fā)明（設(shè)計(jì)）人: 王汝言;張普釗;吳大鵬;黃勝;隆克平
• 申請（專利權(quán)）人: 重慶郵電大學(xué)
• 主分類號: H04Q11/00
• 分類號: H04Q11/00;H04J14/02;G06F17/50
• 代理公司: 重慶市恒信知識產(chǎn)權(quán)代理有限公司 50102
• 代理人: 劉小紅

技術(shù)領(lǐng)域

本發(fā)明涉及通信技術(shù)領(lǐng)域，尤其涉及光波分復(fù)用網(wǎng)絡(luò)中的選路與波長分 配(RWA)技術(shù)。

背景技術(shù)

波分復(fù)用技術(shù)(WDM)以其傳輸容量大，對高層協(xié)議和技術(shù)適應(yīng)性強(qiáng)， 以及易于擴(kuò)展等優(yōu)點(diǎn)而備受青睞。利用WDM傳輸技術(shù)的光傳送網(wǎng)被認(rèn)為是 下一代高速廣域骨干網(wǎng)的最具競爭力的選擇。為客戶層到達(dá)的業(yè)務(wù)選擇路由 和分配波長的問題被稱為路由和波長分配(Routing?and?Wavelength Assignment)問題，簡稱RWA問題。如何在有限資源網(wǎng)絡(luò)中為業(yè)務(wù)選擇合適 的路由和分配優(yōu)化的波長將直接影響到網(wǎng)絡(luò)的傳輸效率。作為WDM網(wǎng)絡(luò)的 關(guān)鍵技術(shù)，RWA以及資源優(yōu)化問題已被大批學(xué)者研究。在特定的網(wǎng)絡(luò)拓?fù)? 下，如何為到達(dá)的連接請求分配路由及如何為路由所經(jīng)的各鏈路分配波長， 從而使得指定的性能指標(biāo)達(dá)到最優(yōu)。在WDM網(wǎng)絡(luò)中，解決RWA問題通常要 受到兩種限制：當(dāng)網(wǎng)絡(luò)中不存在波長變換器時(shí)，相同光路的所有鏈路上必須 使用相同的波長，即光路的波長連續(xù)性限制；另外，在同一條鏈路上，經(jīng)過 該鏈路的不同光路必須分配不同的波長，即不同信道分配限制。

路由和波長分配根據(jù)不同的業(yè)務(wù)可以分為兩類：

1.對于靜態(tài)業(yè)務(wù)路由和波長分配：給定網(wǎng)絡(luò)拓?fù)浜鸵唤M連接建立請求， 需要為這些請求在拓?fù)渖蠈ふ衣酚刹⒃谄渎酚缮戏峙洳ㄩL，以建立永久光路 來傳送業(yè)務(wù)。靜態(tài)業(yè)務(wù)的優(yōu)化目標(biāo)為：建立光路所消耗的資源最少(所需波長 數(shù)或光纖數(shù)最少等)，或同等資源下使全網(wǎng)吞吐量最大；

2.對于動態(tài)業(yè)務(wù)路由和波長分配：光路請求隨機(jī)達(dá)到和離開網(wǎng)絡(luò)，相應(yīng) 的主要性能指標(biāo)通常是全網(wǎng)阻塞率。

動態(tài)RWA問題與靜態(tài)RWA問題的不同在于：動態(tài)RWA問題中的業(yè)務(wù) 是隨機(jī)到達(dá)的，服從泊松分布，并且業(yè)務(wù)傳送完畢后建立的路由需要拆除， 路由的保持時(shí)間服從負(fù)指數(shù)分布；而靜態(tài)RWA問題中的業(yè)務(wù)是已知的，并且 所建立的路由在網(wǎng)絡(luò)拓?fù)洳话l(fā)生變化的情況下一般不需要更新。

現(xiàn)有技術(shù)對靜態(tài)業(yè)務(wù)路由和波長分配的解決方案主要有：1、整數(shù)線性規(guī) 劃：將靜態(tài)RWA問題歸結(jié)為一類線性規(guī)劃問題，建立以最小化波長或光纖數(shù) 為目標(biāo)的LP模型，求解LP方程實(shí)現(xiàn)網(wǎng)絡(luò)的優(yōu)化目標(biāo)。該模型屬于一個(gè)NP-C 問題，當(dāng)網(wǎng)絡(luò)的規(guī)模較小時(shí)，該方法可直接得到最優(yōu)解。該方法對于較大規(guī) 模的網(wǎng)絡(luò)則不太適合，因?yàn)樗惴ǖ膹?fù)雜度會隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大成指數(shù)遞增。 另外，其優(yōu)化目標(biāo)比較固定，且靈活性較差。2、拆分算法：由于靜態(tài)RWA 問題的復(fù)雜性，可以將其分解成路由子問題和波長分配子問題來考慮。然后 按照各種路由算法和波長分配算法來分別加以解決。這種算法需要將問題進(jìn) 行拆分，而將每個(gè)子問題的局部最優(yōu)解組合起來并非全局最優(yōu)。

解決靜態(tài)業(yè)務(wù)路由和波長分配方法的性能評估是研究RWA問題的重要環(huán) 節(jié)，目前多采用計(jì)算機(jī)建模進(jìn)行仿真分析，本發(fā)明針對靜態(tài)RWA問題的建模 與仿真分析，提出一種基于分層圖的靜態(tài)選路與波長分配方法。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問題是：針對現(xiàn)有靜態(tài)RWA算法的復(fù)雜度較高， 且需要將靜態(tài)RWA問題拆分，不能比較各種算法的優(yōu)越性等缺陷，本發(fā)明針 對靜態(tài)RWA問題進(jìn)行數(shù)學(xué)建模，并提出了一種采用分層圖來解決靜態(tài)RWA 問題的方法。該方法通過實(shí)施分層圖算法得到靜態(tài)RWA問題的解決方案。同 時(shí)，本方法所采用的分層圖模型可以避免靜態(tài)RWA問題的強(qiáng)行拆分，復(fù)雜度 也有所降低。另外，利用該方法，可以實(shí)現(xiàn)對各種靜態(tài)RWA相關(guān)算法進(jìn)行性 能評估，并通過各性能參數(shù)來選取最佳的算法和最優(yōu)的解決方案。