RWA算法的研究【畢業(yè)論文絕對(duì)】

1、rwa算法的研究摘要：本文研究了 wdm網(wǎng)中的選路與波長(zhǎng)分配(rwa)問題。主要針對(duì)的是 有波長(zhǎng)一致性限制的網(wǎng)絡(luò)。首先簡(jiǎn)單介紹了 wdm光傳送網(wǎng)的一些基本概念。然 后對(duì)wdm傳送網(wǎng)的選路與波長(zhǎng)分配(rwa)|nj題進(jìn)行了分類，并綜述了各種條件 下的rwa算法，對(duì)其進(jìn)行了分類、比較。最后在對(duì)以往算法分析和比較的基礎(chǔ) 上，提出了一個(gè)新的rwa算法。新算法中考慮了多個(gè)網(wǎng)絡(luò)設(shè)計(jì)優(yōu)化目標(biāo)，對(duì)網(wǎng) 絡(luò)運(yùn)營(yíng)商有一定的參考價(jià)值。關(guān)鍵詞：wdm；選路與波長(zhǎng)分配；優(yōu)化算法;啟發(fā)式算法abstractthis study focuses on the routing and wavelength assignment

2、 (rwa) problem in wdm networks. most of the attention is devoted to such networks operating under the wavelength-continuity constraint. some concepts on wdm optical networking are studied first. then we studied the associated research problems and challenges. various rwa approaches are examined and

3、compared. finally, we proposed a new rwa algorithm, which include many factors of the wdm network and may be useful to a network maker.keyword： wdm ； rwa； optimal algorithm； heuristic algorithm第一章 引 言波分復(fù)用(wavelength division multiplexing一wdm)網(wǎng)絡(luò)利用了光纖傳輸 鏈路的巨大帶寬，隨著wdm技術(shù)日趨成熟，wdm傳輸技術(shù)已經(jīng)進(jìn)入實(shí)用化和 商用化階段。wdm全光通

4、信網(wǎng)是光纖通信未來(lái)發(fā)展的主要方向之一。由于光網(wǎng) 絡(luò)對(duì)傳輸信號(hào)的速率和格式透明，具有靈活的波長(zhǎng)選路和動(dòng)態(tài)資源配置能力，可 以實(shí)現(xiàn)網(wǎng)絡(luò)的動(dòng)態(tài)重構(gòu)，被認(rèn)為是通信網(wǎng)絡(luò)升級(jí)的首選方案。如何利用現(xiàn)有的和 即將敷設(shè)的光纖連網(wǎng)，構(gòu)成未來(lái)高速、大容量、多業(yè)務(wù)的wdm網(wǎng)絡(luò)已經(jīng)成為光 通信領(lǐng)域小的一個(gè)重大問題。wdm網(wǎng)絡(luò)節(jié)點(diǎn)處采用光分插復(fù)用器(oadm)或 光交叉連接設(shè)備(oxc)在光層建立光連接，即光通道(optical path),為高層 的多個(gè)邏輯電網(wǎng)絡(luò)提供了高速、人容量的信息傳送平臺(tái)。光通道的建立，要求在 傳送網(wǎng)的物理結(jié)構(gòu)中選擇一條曲業(yè)務(wù)源點(diǎn)到宿點(diǎn)的路出，并為其分配一定的波長(zhǎng) 信道(參見圖l.do考慮到波長(zhǎng)

5、資源的重利用以及提高網(wǎng)絡(luò)的阻塞性能，優(yōu)化光 通道的選路和波長(zhǎng)分配(routing and wavelength assignment rwa)方案成為 光通道層設(shè)計(jì)的核心問題。rwa解決如何尋找一條合適的光通道并合理地分配 通道所使用的波長(zhǎng)，使有限的資源充分發(fā)揮作用，以提供盡可能大的通信容量。圖1.1 wdm網(wǎng)建立的光通道在以下的文章中，首先介紹了 wdm網(wǎng)絡(luò)中與rwa問題有關(guān)的一些基本概 念。然后對(duì)rwa問題進(jìn)行了分類討論，并對(duì)已提出的rwa算法進(jìn)行了研究、 總結(jié)。在文章最后針對(duì)網(wǎng)狀網(wǎng)提出了一種新的rwa算法、詳細(xì)描述了該算法， 并把它和其它算法進(jìn)行了比較。2.1 wdm的定義光波分復(fù)用（w

6、dm： wavelength division multiplexing）技術(shù)是在一根光纖 屮同時(shí)傳輸多波長(zhǎng)光信號(hào)的一項(xiàng)技術(shù)。其基本原理是在發(fā)送端將不同波長(zhǎng)的光信 號(hào)組合起來(lái)（復(fù)用），并耦合到光纜線路上的同一根光纖中進(jìn)行傳輸，在接收端 乂將組合波氏的光信號(hào)分開（解復(fù)用），并作進(jìn)一步處理，恢復(fù)出原信號(hào)后送入 不同的終端，因此將此項(xiàng)技術(shù)稱為光波長(zhǎng)分割復(fù)用，簡(jiǎn)稱光波分復(fù)用技術(shù)。wdm 技術(shù)相當(dāng)于在同一根光纖上創(chuàng)造了許多虛擬光纖，從而數(shù)倍乃至數(shù)十倍的提高了 傳輸容量。2.2 wdm光傳送網(wǎng)的分層結(jié)構(gòu)分層結(jié)構(gòu)是定義和研究光傳送網(wǎng)的基礎(chǔ)。己發(fā)布的g.872建議（草案），以 明確在光傳送網(wǎng)絡(luò)加入光層，按建議

7、，光層由光信道層，光復(fù)用段層和光傳輸層 組成，如圖2.2.1 o光傳送網(wǎng)絡(luò)電路層電通道層電復(fù)用段層光信道層光復(fù)用段層光傳輸段層物理層（光纖）圖221光通信網(wǎng)的分層結(jié)構(gòu)2.2.1光信道層光信道層（optical channel layer）負(fù)責(zé)為來(lái)fl電復(fù)用段層的客戶信息選擇路由 和分配波長(zhǎng)，為靈活的網(wǎng)絡(luò)選路安排光信道連接，處理光信道開銷，提供光信道層的檢測(cè)，管理功能。并在故障發(fā)生吋，通過(guò)重新選路或直接把工作業(yè)務(wù)切換到 預(yù)定的保護(hù)路由來(lái)實(shí)現(xiàn)保護(hù)倒換和網(wǎng)絡(luò)恢復(fù)。2.2.2光復(fù)用段層光復(fù)用段層(optical multiplexing section layer)保證相鄰兩個(gè)波長(zhǎng)復(fù)用傳輸設(shè) 備間多波

8、長(zhǎng)復(fù)用光信號(hào)的完整傳輸，為多波長(zhǎng)信號(hào)提供網(wǎng)絡(luò)功能。其主要包括： 為靈活的多波長(zhǎng)網(wǎng)絡(luò)選路重新安排光復(fù)用段功能；為保證多波長(zhǎng)光復(fù)用段適配信 息的完整性處理光復(fù)用段開銷；為網(wǎng)絡(luò)的運(yùn)行和維護(hù)提供光復(fù)用段的檢測(cè)和管理 功能。2.2.3光傳輸段層光傳輸段層(optical transmission section layer*)為光信號(hào)在不同類型的光傳輸 媒質(zhì)(如g.652,g.653,g.655光纖等)上提供傳輸能力，同時(shí)實(shí)現(xiàn)對(duì)光放人器或中 繼器的檢測(cè)和控制功能等。通常會(huì)涉及以下問題：功率均衡問題、edfa增益控 制問題和色散的積累和補(bǔ)償問題。2.3 wdm光傳送網(wǎng)的拓?fù)浣Y(jié)構(gòu)任何通信網(wǎng)絡(luò)都存在兩種拓?fù)浣Y(jié)

9、構(gòu)，即物理拓?fù)浜瓦壿嬐負(fù)?也稱為虛拓 撲)。其中物理拓?fù)浔碚骶W(wǎng)絡(luò)節(jié)點(diǎn)的物理結(jié)構(gòu)；邏輯拓?fù)浔碚骶W(wǎng)絡(luò)節(jié)點(diǎn)間業(yè)務(wù)分 布情況。圖2.3.1屮網(wǎng)絡(luò)物理結(jié)構(gòu)的一個(gè)例子。1116為物理鏈路，每根光纖上可采 用多個(gè)波長(zhǎng)。c)接入點(diǎn)a-e oxc11 16物理鏈路圖231網(wǎng)路的物理拓?fù)鋱D2.3.2(a)為上圖建立光路的例子。在一根光纖上不能為不同光路分配相同 波長(zhǎng)。圖2.3.2(a)的光路連接用圖2.3.2(b)表示即為邏輯拓?fù)洹＠鐖D2.3.2(a)中， 節(jié)點(diǎn)b與節(jié)點(diǎn)e間的光路是經(jīng)過(guò)節(jié)點(diǎn)a屮的oxc轉(zhuǎn)接的，在圖2.3.2(b)屮用04表示。圖2.3.2（b）屮，04,01是屮間有0xc轉(zhuǎn)接的；02,03,05

10、是直接光路。a-e 0xcae 0xc路由和波長(zhǎng)分配（b）邏輯結(jié)構(gòu)圖2.3.2 光路舉例實(shí)際設(shè)計(jì)中，一種rwa情況是：提出所需建立的光路，為這種光路選取物 理路由并分配相應(yīng)的波長(zhǎng)。例如，圖2.3.2（b）中提岀要建立5條光路，圖2.3.2（a） 就是一種選路和波長(zhǎng)分配方案。2.4 wdm光傳送網(wǎng)拓?fù)浣Y(jié)構(gòu)的主耍議題在研究rwa問題的文獻(xiàn)屮，通常將網(wǎng)絡(luò)支持的業(yè)務(wù)分為兩類：1）靜態(tài)業(yè) 務(wù)：給定一組連接建立請(qǐng)求，需要為這些請(qǐng)求尋找路由并在其路由上分配波長(zhǎng)， 以使某些性能指標(biāo)達(dá)到最優(yōu)（如全網(wǎng)吞吐量最大、所需波長(zhǎng)數(shù)和光纖數(shù)最少等 等:2）動(dòng)態(tài)業(yè)務(wù)：光路請(qǐng)求隨機(jī)到達(dá)和離開網(wǎng)絡(luò)，相應(yīng)當(dāng)性能指標(biāo)通常是光路 的阻

11、塞率。因此按照所支持的業(yè)務(wù)類型劃分，rwa問題可分為靜態(tài)rwa問題和 動(dòng)態(tài)rwa問題。在研究wdm全光網(wǎng)的拓?fù)浣Y(jié)構(gòu)時(shí)，有兩類相關(guān)的主要問題需要解決。第 一類問題稱為“網(wǎng)絡(luò)設(shè)計(jì)”問題，即通過(guò)網(wǎng)絡(luò)的業(yè)務(wù)需求分布（可以使業(yè)務(wù)流分 布）和物理拓?fù)洌_定網(wǎng)絡(luò)的配置，包括光纖對(duì)數(shù)、節(jié)點(diǎn)交叉連接的規(guī)模、需要 的光放大器以及光載波分插復(fù)用器等。研究該問題可以在靜態(tài)業(yè)務(wù)條件下優(yōu)化波 長(zhǎng)資源，使網(wǎng)絡(luò)需要的波長(zhǎng)數(shù)日最小。由于在大多數(shù)實(shí)際場(chǎng)合屮每根光纖復(fù)用的 波長(zhǎng)數(shù)忖是固定的，如果一對(duì)光纖（雙向傳輸）不能傳輸某鏈路上所有預(yù)分配的 業(yè)務(wù)，那么在該線路方向上將需要更多的光纖對(duì)，因此問題研究的優(yōu)化目標(biāo)轉(zhuǎn)化 為最小化光纖數(shù)口

12、或交叉連接節(jié)點(diǎn)的規(guī)模等內(nèi)容，或者是上述兩方面的組合。最 終的優(yōu)化測(cè)度應(yīng)當(dāng)是網(wǎng)絡(luò)的成本相應(yīng)可以通過(guò)每條鏈路需要的光纖數(shù)目以及光 纖鏈路長(zhǎng)度等參數(shù)來(lái)衡量。如果從光通道層來(lái)建立的角度分析，靜態(tài)業(yè)務(wù)下的選 路和波長(zhǎng)分配（rwa）問題相當(dāng)于這一類“網(wǎng)絡(luò)設(shè)計(jì)”問題。第二類wdm全光網(wǎng)的拓?fù)浣Y(jié)構(gòu)問題成為“網(wǎng)絡(luò)運(yùn)營(yíng)”問題。即對(duì)給定的 網(wǎng)絡(luò)（已知拓?fù)浜唾Y源），在已知和可以預(yù)測(cè)業(yè)務(wù)量的平均分布情況下，假設(shè)實(shí) 際業(yè)務(wù)需求的變化是隨機(jī)的，則網(wǎng)絡(luò)可能存在一定的阻塞率。反應(yīng)動(dòng)態(tài)的選路和 波長(zhǎng)選擇算法質(zhì)量的指標(biāo)是在給眾利用度條件下的阻塞概率。曲于具有波長(zhǎng)變換 功能的節(jié)點(diǎn)可以提高光通道中波長(zhǎng)的選擇能力，因此在波長(zhǎng)資源相同的情

13、況下， vwp網(wǎng)絡(luò)比wp網(wǎng)絡(luò)具有更好的性能?！熬W(wǎng)絡(luò)運(yùn)營(yíng)”問題可以看作動(dòng)態(tài)業(yè)務(wù)條件 下的rwa問題。2.5基于光路的rwa與基于運(yùn)送分組業(yè)務(wù)的rwawdm光傳送網(wǎng)既可以支持傳送電路交換方式的業(yè)務(wù)，乂可以支持傳送分組 交換方式的業(yè)務(wù)。在傳送不同類型的業(yè)務(wù)時(shí)，光通道層拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)有著不同的 特點(diǎn)。當(dāng)光傳送網(wǎng)用于傳送電路交換型業(yè)務(wù)時(shí)，和傳統(tǒng)當(dāng)電話交換網(wǎng)的接續(xù)比較 類似。此時(shí)，業(yè)務(wù)需求以單一波長(zhǎng)信道的容量為單位，通過(guò)路由選擇和配置波長(zhǎng) 建立用于業(yè)務(wù)傳送的端到端光連接。電路交換型光傳送網(wǎng)面向的是連接型業(yè)務(wù)， 而未來(lái)的光網(wǎng)絡(luò)還需耍支持支持分組數(shù)據(jù)（無(wú)連接型業(yè)務(wù)）的傳送。由于兩種業(yè) 務(wù)類型有著本質(zhì)的區(qū)別，因此

14、在光層網(wǎng)絡(luò)的優(yōu)化目標(biāo)和優(yōu)化策略方面存在明顯不 同。支持分組交換業(yè)務(wù)的光傳送網(wǎng)，其設(shè)計(jì)的核心是解決最優(yōu)化網(wǎng)絡(luò)虛拓?fù)涞膯?題。2.6波長(zhǎng)通道網(wǎng)絡(luò)和虛波長(zhǎng)通道網(wǎng)絡(luò)電復(fù)用段一個(gè)單位的信息（如sdh信號(hào)、pdh信號(hào)甚至模擬視頻信號(hào)）在 光網(wǎng)絡(luò)中傳送始，需更為它選一條路由并分配波長(zhǎng)（rwa）o由于一根光纖中能夠 復(fù)用的波長(zhǎng)數(shù)有限，且任何兩路信號(hào)在一根光纖屮不能使用相同波長(zhǎng)，所以波長(zhǎng) 資源的分配是光層管理的一項(xiàng)重耍內(nèi)容。根據(jù)oxc能否提供波長(zhǎng)轉(zhuǎn)換功能，光 通道可以分為波長(zhǎng)通道（wp: wavelength path）和虛波長(zhǎng)通道（vwp: virtual wavelength path）o波長(zhǎng)通道是指oxc

15、沒有波長(zhǎng)轉(zhuǎn)換功能，光通道在不同的波長(zhǎng) 復(fù)用段中必須使用相同波長(zhǎng)實(shí)現(xiàn)。為了建立一條波長(zhǎng)通道，光通道層必須找到一 條鏈路，在構(gòu)成這條鏈路的所有波長(zhǎng)復(fù)用段屮，存在一個(gè)共同的空閑波長(zhǎng)。如果 找不到這樣一條鏈路，該通道創(chuàng)建請(qǐng)求失敗。虛波長(zhǎng)通道是指利用oxc的波長(zhǎng) 轉(zhuǎn)換功能，使光通道在不同的波長(zhǎng)復(fù)用段可以占用不同的波長(zhǎng)，從而提高了波長(zhǎng) 的利用率。建立虛波長(zhǎng)通道時(shí)，光通道層只需找到一條鏈路，其中每個(gè)波長(zhǎng)復(fù)用 段都有空閑波長(zhǎng)即可。波長(zhǎng)通道方式要求光通道層在選路和分配波長(zhǎng)時(shí)采用集屮 控制方式，因?yàn)橹挥性谡莆樟苏麄€(gè)網(wǎng)絡(luò)所有復(fù)用段占用情況后，才可能為一個(gè)新 傳送請(qǐng)求選一條合適的路由。在虛波長(zhǎng)通道運(yùn)作方式下，確定通道

16、的傳送鏈路后， 各波長(zhǎng)復(fù)用段的波長(zhǎng)可以逐個(gè)分配，因此可以進(jìn)行分布式控制。這種方法可以大 大降低光通道層選路的復(fù)雜性。由于復(fù)雜網(wǎng)絡(luò)中任何兩個(gè)節(jié)點(diǎn)間都可能存在多條 路由，因此必需有一套有效的rwa算法，根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和冃前的狀態(tài)， 為新傳送請(qǐng)求選路并分配波長(zhǎng)。另外，當(dāng)光通道層中允許接入分組信息時(shí)，還需 要相應(yīng)的分組交換型的選路算法。與wp方案相比，vwp方案的一個(gè)顯著特點(diǎn)是通道由經(jīng)過(guò)的光交叉連接(0x0節(jié)點(diǎn)具有波長(zhǎng)轉(zhuǎn)換的能力。wp方案存在波長(zhǎng)全局分配的問題，增加了 光通道實(shí)現(xiàn)的復(fù)雜性；vwp方案不存在這一問題。從網(wǎng)絡(luò)和通道的擴(kuò)展能力上 看，vwp技術(shù)優(yōu)于wp技術(shù)。采用vwp技術(shù)的網(wǎng)絡(luò)，波長(zhǎng)的重

17、利用率和路由 選擇的自由度都要高于采用wp技術(shù)的網(wǎng)絡(luò)。所以，在某一物理網(wǎng)絡(luò)中建立相同 數(shù)量的光通道，與vwp方案相比，wp方案需要使用更多的波長(zhǎng)，換句話說(shuō)， 對(duì)相同物理網(wǎng)絡(luò)結(jié)構(gòu)和同樣數(shù)目的波長(zhǎng)，vwp網(wǎng)絡(luò)可以建立更多的光通道。從 通道波長(zhǎng)的管理幷度比較，wp方案要求對(duì)全網(wǎng)進(jìn)行集中控制，而vwp方案可 能采取鏈路到鏈路的分布式控制。在整個(gè)網(wǎng)絡(luò)范i韋i內(nèi)，wp技術(shù)要求波長(zhǎng)絕對(duì)精 確，vwp技術(shù)則只要保證波長(zhǎng)從鏈路到鏈路相對(duì)精確即可。在wp方案中，如 果無(wú)法找到一條從源節(jié)點(diǎn)到目的節(jié)點(diǎn)由相同空閑波長(zhǎng)的光通道，就會(huì)發(fā)生波長(zhǎng)阻 塞，而使通道建立努力失?。欢鴙wp方案只在通道中某個(gè)鏈路沒有空閑的波長(zhǎng) 信道時(shí)

18、才會(huì)使通道建立請(qǐng)求失敗。綜上可知,rwa問題可以相應(yīng)的分為基于wp網(wǎng)絡(luò)的rwa問題與基于vwp 網(wǎng)絡(luò)的rwa問題與wp網(wǎng)絡(luò)相比vwp網(wǎng)絡(luò)求解rwa問題需增加波長(zhǎng)一致性 的限制，相鄰?fù)ǖ婪峙洳煌牟ㄩL(zhǎng)，其物理意義是對(duì)任意一條光路徑而言，在它 經(jīng)過(guò)的所有鏈路段上必須保持同一波長(zhǎng)信道。2.7波長(zhǎng)變換器作用波長(zhǎng)變換器是解決全光網(wǎng)中波長(zhǎng)路出競(jìng)爭(zhēng)的關(guān)鍵器件，是充分發(fā)揮wdm帶 寬資源的必要手段。為了對(duì)波長(zhǎng)變換的用途和作用有一個(gè)直觀的了解，首先讓我 們來(lái)考慮圖2.7.1的網(wǎng)絡(luò)，它包含兩個(gè)交叉連接節(jié)點(diǎn)和5個(gè)接入點(diǎn)（a到e）。若 要建立兩節(jié)點(diǎn)之間的全光連接，例如a和c的連接，如果沒有波長(zhǎng)變換器，這 條光路上的所

19、有連接必須采用同一波長(zhǎng)，這就是所謂的波長(zhǎng)連續(xù)性限制。對(duì)電路 交換網(wǎng)而言，僅當(dāng)該級(jí)別的鏈路容量都被片用時(shí)，才會(huì)發(fā)生阻塞，而對(duì)于波長(zhǎng)路 由網(wǎng)絡(luò)，卻遠(yuǎn)非如此。如圖2.7.2（a）所示，在網(wǎng)絡(luò)屮建立了兩個(gè)光通道，節(jié)點(diǎn)1 和2之間采用人波長(zhǎng)，節(jié)點(diǎn)2和3之間的波長(zhǎng)是«，現(xiàn)在假設(shè)要在1、3之間 建立一條光通道，即使節(jié)點(diǎn)1、3之間的每個(gè)鏈路都有空閑的波長(zhǎng)也不一定能建 立這個(gè)光通道，這是因?yàn)樵趦蓚€(gè)鏈路上可得到的波長(zhǎng)是不同的。因此，與電路交 換網(wǎng)絡(luò)和比，波長(zhǎng)路由網(wǎng)絡(luò)將遭受更大的阻塞。竹戀! 節(jié)點(diǎn)2 節(jié)點(diǎn)3<a）設(shè)冇浹k理袂技的憂形竹點(diǎn)1 苗點(diǎn)2 節(jié)血3（1>）兵有跛性變換黯的悄寵圖2.7.1

20、全光波長(zhǎng)路由網(wǎng)絡(luò)圖2.7.2波長(zhǎng)連續(xù)性限制如果能在中間節(jié)點(diǎn)進(jìn)行波長(zhǎng)變換，從一個(gè)波長(zhǎng)轉(zhuǎn)換到另一個(gè)波長(zhǎng)，對(duì)光網(wǎng) 絡(luò)將是非常有利的。如圖2.7.2（b）所示，節(jié)點(diǎn)2的波長(zhǎng)變換器把波長(zhǎng)從人變換到 入，在節(jié)點(diǎn)1、2中間應(yīng)用禺波長(zhǎng)，在節(jié)點(diǎn)2、3中間應(yīng)用入波長(zhǎng)，從節(jié)點(diǎn)1 到節(jié)點(diǎn)3的光通道便可建立。在含有波長(zhǎng)變換器的網(wǎng)絡(luò)中，光通道能在不同的鏈 路上用不同的波長(zhǎng)而建立，從而人人提高網(wǎng)絡(luò)的靈活性，消除光通道的波長(zhǎng)沖突。 引入波長(zhǎng)變換技術(shù)，可以實(shí)現(xiàn)波長(zhǎng)的再利用，更有效地進(jìn)行路由的選擇，降低網(wǎng) 絡(luò)阻塞率，從而提高wdm網(wǎng)的靈活性和可擴(kuò)充性。波長(zhǎng)變換器對(duì)wdm光網(wǎng)絡(luò)的性能究竟有多大的改善，是近年來(lái)的一個(gè)熱 點(diǎn)課題。現(xiàn)在

21、比較一致的觀點(diǎn)是：波長(zhǎng)變換器對(duì)一個(gè)波長(zhǎng)數(shù)星固定，且業(yè)務(wù)量接 近飽和的網(wǎng)絡(luò)的作用不人；對(duì)于集中管理的網(wǎng)絡(luò)和環(huán)形網(wǎng)的彫響也不明顯，而對(duì) 大容量的網(wǎng)格形網(wǎng)，波長(zhǎng)變換器的加入?yún)s能大大降低網(wǎng)絡(luò)的阻塞率。如果節(jié)點(diǎn)的 數(shù)目加大，效果會(huì)更明顯。事實(shí)上，波長(zhǎng)變換器的作用與wdm光網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)、 波長(zhǎng)數(shù)、波長(zhǎng)從源到宿所經(jīng)過(guò)的節(jié)點(diǎn)數(shù)及業(yè)務(wù)量都密切相關(guān)。鑒于波長(zhǎng)轉(zhuǎn)換器還未達(dá)到實(shí)用水平，木文主要針對(duì)無(wú)波長(zhǎng)轉(zhuǎn)換、基于光路交換網(wǎng)絡(luò)的rwa問題進(jìn)行了研究。第三章靜態(tài)rwa算法基于光路的靜態(tài)rwa算法是給定多條光路的連接需求和物理拓?fù)浜鬄槊織l 光路選取路由并分配波長(zhǎng)。3.1設(shè)計(jì)時(shí)的優(yōu)化目標(biāo)：1）給定網(wǎng)絡(luò)資源而最人化網(wǎng)絡(luò)的某些特

22、性，如可以建立的連接數(shù)、波長(zhǎng)的 復(fù)用率、可獲得的利潤(rùn)等。2）給定光連接數(shù)冃而最小化所需要的網(wǎng)絡(luò)資源數(shù)冃或代價(jià)。3.2設(shè)計(jì)時(shí)的約束條件：1）波長(zhǎng)一致性限制：即每一個(gè)光通路所使用的波長(zhǎng)在從源節(jié)點(diǎn)到冃的節(jié)點(diǎn)的 所有連路上都是相同的，這一限制是由網(wǎng)絡(luò)的物理?xiàng)l件造成的。2）同一光纖屮的不同光通道必須分配不同的波長(zhǎng)，這是保證網(wǎng)絡(luò)能夠正常運(yùn) 行的限制條件。3.3解決方案：方案一：選路與波長(zhǎng)分配作為一個(gè)整體的問題來(lái)解決rwa 這個(gè)優(yōu)化問題是一個(gè) npc（nondeterministic polynomial omplete,非 確定型多項(xiàng)式一完全）組合優(yōu)化問題，可以用整數(shù)線性規(guī)劃（ilp）來(lái)尋找最優(yōu) 解，但這

23、種優(yōu)化方法的復(fù)雜性隨網(wǎng)絡(luò)規(guī)模的增大而急劇增加，當(dāng)網(wǎng)絡(luò)規(guī)模較大 時(shí)因運(yùn)算時(shí)間太長(zhǎng)而無(wú)法接受。因此工程上常將rwa問題拆成選路了問題和波 長(zhǎng)分配子問題。方案二：選路與波長(zhǎng)分配作為兩個(gè)子問題來(lái)解決選路和波長(zhǎng)分配這兩個(gè)子問題也都是典型的np-c組合優(yōu)化問題。圖331是對(duì)口前已有算法的分類:圖3.3.1算法分類這里首先把求解過(guò)程分成選路和波長(zhǎng)分配兩部分。每一子問題中乂分成兩 步，即尋找與選擇，最后按照所用的具體算法進(jìn)行分類。圖332、333分別給出了解決選路和波長(zhǎng)分配問題的算法的具體實(shí)現(xiàn)方法。尋找選擇尋找方法尋找順序選擇順序選擇規(guī)則最短路徑法加權(quán)最短路徑最人流量?jī)?yōu)先 隨機(jī)k-最短路徑隨機(jī) 固定 最長(zhǎng)優(yōu)先

24、 最短優(yōu)先隨機(jī) 固定 概率 最小順序算法(貪婪算法)隨機(jī)循環(huán)(random rounding)啟發(fā)式組合算法整數(shù)線性規(guī)劃最優(yōu)化圖3.3.2選路算法(1)選路算法：在選路問題中，考慮所有可能的源目的對(duì)是不實(shí)際的，因?yàn)橛?jì)算時(shí)間隨著網(wǎng)絡(luò)規(guī)模的增長(zhǎng)成指數(shù)增長(zhǎng)。因此，尋找功能通常由最短路徑算法及它的變種(variations)實(shí)現(xiàn)。在k 最短路徑算法中(即：有多個(gè)備選路由)，選擇功能 由順序算法或組合優(yōu)化算法來(lái)實(shí)現(xiàn)。順序算法（也叫貪焚算法）是最簡(jiǎn)單的一種。 它按順序?yàn)槊恳粭l光路進(jìn)行選擇，這其中需要考慮兩方面：選擇順序、選擇規(guī)則。 選擇順序是指先為哪一個(gè)光連接選擇路由，選擇規(guī)則是從備選路由中選擇的標(biāo) 準(zhǔn)。

25、圖3.3.2解釋了選路算法：最短路徑（sp shortest path）：最短路徑算法尋找從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的 一條最短的光路。加權(quán)最短路（wspweighted shortest path）:加權(quán)最短路算法是一種最短 路算法，但是鏈路代價(jià)可以隨著已建立的路由數(shù)動(dòng)態(tài)的變化。因此，它需要一個(gè) 尋找順序。例如：最人業(yè)務(wù)量?jī)?yōu)先（largest traffic first）：從需要建立的光路中優(yōu)先選擇業(yè) 務(wù)量最人的光路來(lái)尋找路由；隨機(jī)（random）機(jī)制以隨機(jī)的順序來(lái)選擇需要建立的光路。但是這種方法不需要選擇功能，因?yàn)樗彩侵粸槊總€(gè)源目的對(duì)選擇一個(gè)路 由。 k最短路徑（kspkshortest pat

26、h）: k最短路徑算法為每一源目的對(duì) 尋找多個(gè)路徑，k個(gè)備選路由增加了選路的靈活性。然而，選路問題變成了選擇 問題：為所有的源目的對(duì)選擇一個(gè)代價(jià)（跳數(shù)或鏈路代價(jià)）最小的路由。選擇功能如下：1）順序算法（貪婪算法）選擇順序*隨機(jī)（random）機(jī)制從所有未建立路由的光連接中以隨機(jī)的方式選擇；*固定（fixed）機(jī)制把光連接按某種規(guī)則排序（如按鏈路數(shù)降序），然后依 次選取；*最長(zhǎng)路優(yōu)先（longest-first）機(jī)制把光通路按通路的長(zhǎng)度（跳數(shù)或代價(jià)） 由大到小排序，先選長(zhǎng)路由；*最短路優(yōu)先（shortest-first）機(jī)制把光通路按通路的長(zhǎng)度（跳數(shù)或代價(jià)） 由人到小排序，先選短路由。選擇規(guī)則*

27、隨機(jī)機(jī)制：從備選路由中隨機(jī)選取一條。* ff(first-fit)機(jī)制：從備選路由中選擇第一個(gè)符合條件的路由。*概率(probability)機(jī)制：依一定的概率從備選路由屮選擇一條路由。*鏈路最小權(quán)重(minimumweighted link)優(yōu)先機(jī)制：選擇所有鏈路上已 經(jīng)建立的路由數(shù)最小的路由。2)組合算法最優(yōu)化算法(optimal algorithm)：這是一個(gè)多商品流問題，用整數(shù)線 性規(guī)劃可以得到最優(yōu)解。最優(yōu)化選擇可得到最優(yōu)的結(jié)果，但是網(wǎng)絡(luò)規(guī)模較大時(shí)計(jì) 算的復(fù)雜程度是無(wú)法忍受的。啟發(fā)式算法(heuristic algorithm)：?jiǎn)l(fā)式算法是根據(jù)概念推出的優(yōu) 化算法，能得到較優(yōu)的結(jié)果，

28、但不一定是最優(yōu)。它降低了組合空間(combination space),在所設(shè)計(jì)的規(guī)則指導(dǎo)下修改所選的路出，多次循環(huán)以靠近優(yōu)化目標(biāo)，直 到循環(huán)無(wú)法得到更優(yōu)結(jié)果為止。尋找選擇尋找順序?qū)ふ乙?guī)則選擇順序選擇規(guī)則所有波長(zhǎng)隨機(jī) 固定 最長(zhǎng)優(yōu)先 最短優(yōu)先隨機(jī)ff(first fit) 最少使用 最多使用順序算法(貪焚算法)ga (遺傳算法)sa (模擬退火算法)random rounding (隨機(jī)循環(huán))tabu (禁忌搜索)啟發(fā)式組合算法窮盡式搜索程序最優(yōu)化圖3.3.3波長(zhǎng)分配算法(2)波長(zhǎng)分配算法:對(duì)于沒有波長(zhǎng)轉(zhuǎn)換功能的網(wǎng)絡(luò)，波長(zhǎng)分配算法為已選定的路由分配波長(zhǎng)，需 滿足波長(zhǎng)一致性的要求。波長(zhǎng)分配問題可

29、以轉(zhuǎn)化為一個(gè)輔助圖的著色問題。從圖3.3.2屮可見，波長(zhǎng)分配問題也可分為尋找和選擇。任何一個(gè)可用波長(zhǎng) 都可以分配給已選路出，所以尋找問題很簡(jiǎn)單。剩下的問題就是怎樣可用波長(zhǎng)中 進(jìn)行選擇：哪一個(gè)可以最大化波長(zhǎng)的利用率。同選路問題相似，選擇可以進(jìn)一步 分為順序算法和組合算法。1) 順序算法(貪婪算法)選擇順序*鄰居數(shù)最大優(yōu)先(largest number of neighbor-first)機(jī)制選擇鄰居數(shù)最大 的路由首先分配波長(zhǎng)。*可用波長(zhǎng)最大優(yōu)先(largest available wavelength-first)機(jī)制把路由按可用 波長(zhǎng)數(shù)多少?gòu)拇蟮叫∨判颍?業(yè)務(wù)量最大優(yōu)先(largest tra

30、ffic-first)機(jī)制按路由業(yè)務(wù)量大小確定波長(zhǎng)分 配順序。*最長(zhǎng)路優(yōu)先(longest path-first)機(jī)制依每條路中的跳數(shù)(hop count)順序 來(lái)選路。*最短路優(yōu)先(shortest path-first)機(jī)制按與最長(zhǎng)路優(yōu)先機(jī)制現(xiàn)反的順序選 路。*隨機(jī)機(jī)制以隨機(jī)的方式選路。選擇規(guī)則* ff(first fit)機(jī)制依波長(zhǎng)編號(hào)選第一個(gè)可用波長(zhǎng)。*最多使用優(yōu)先(most used first)機(jī)制為當(dāng)前路出選擇最多使用的波長(zhǎng)。*最少使用優(yōu)先(least used first)機(jī)制為當(dāng)前路由選擇最少使用的波氏。*隨機(jī)機(jī)制：隨機(jī)的分配一個(gè)波長(zhǎng)。2) 組合算法最優(yōu)化算法：可以采用窮盡式

31、(exhaustive)搜索，但由于這是一個(gè)npc 問題，不適用于大規(guī)模的網(wǎng)絡(luò)。啟發(fā)式算法：?jiǎn)l(fā)式算法可以有效地用于圖著色問題，進(jìn)一步分為：*遺傳算法(gagenetic algorithm)：遺傳算法仿用生物的進(jìn)化與遺傳， 根據(jù)“優(yōu)勝劣汰”原則，使所耍求解決的問題從初始解逐步地逼進(jìn)最優(yōu)解。在許 多情況下，遺傳算法優(yōu)于傳統(tǒng)的優(yōu)化方法。該算法允許所求得的問題是非線形的 和不連續(xù)的，并能從整個(gè)可行解空間尋找全局最優(yōu)解，避免只得出局部最優(yōu)解。 同時(shí)，由于其搜索最優(yōu)解的過(guò)程是有指導(dǎo)性的，避免了一般優(yōu)化算法的維數(shù)災(zāi)難 問題。*模擬退火算法(sa-simulated annealing algorithm

32、)：模擬退火算法是局 部搜索算法的擴(kuò)展。它不同于局部搜索之處是以一定的概率選擇領(lǐng)域中費(fèi)用值人 的狀態(tài)。理論上說(shuō)它是一個(gè)全局最優(yōu)算法。*禁忌搜索算法(tabu algorithm)：禁忌算法是局部領(lǐng)域搜索算法的推廣, 是人工智能在組合優(yōu)化算法屮的一個(gè)成功應(yīng)用o禁忌算法的特點(diǎn)是采用了禁忌技 術(shù)。所謂禁忌技術(shù)就是禁止垂復(fù)前面的丁作。為了冋避局部領(lǐng)域搜索陷入局部最 優(yōu)的主要不足，禁忌搜索算法用一個(gè)禁忌表記錄下已經(jīng)到達(dá)過(guò)的局部最優(yōu)點(diǎn)，在 下一次搜索屮，利用禁忌表中的信息不再或有選擇地搜索這些點(diǎn)，一次來(lái)跳出局 部最優(yōu)點(diǎn)。文獻(xiàn)5中對(duì)以上幾種啟發(fā)式算法應(yīng)用于圖著色問題進(jìn)行了研究，對(duì)比表明禁 忌搜索算法的性能最

33、好。第四章動(dòng)態(tài)rwa算法4.1動(dòng)態(tài)rwa問題分析所謂動(dòng)態(tài)rwa問題，是指在實(shí)時(shí)業(yè)務(wù)條件下的光通道路曲選擇和波長(zhǎng)分配 優(yōu)化問題。此時(shí)光通道的連接請(qǐng)求是隨機(jī)到達(dá)的，并口已建立的連接在維持任意 一段時(shí)間后會(huì)被撤銷，這一點(diǎn)和普通電話網(wǎng)中的呼叫處理過(guò)程十分類似。由于需 要建立的光通道數(shù)量和位置是不固定的，并且隨時(shí)在不斷變化，因此以資源優(yōu)化 （最小化波長(zhǎng)數(shù)冃）為冃標(biāo)已不能反映實(shí)際情況的要求，根據(jù)動(dòng)態(tài)業(yè)務(wù)的特點(diǎn)應(yīng) 當(dāng)選擇服務(wù)性能指標(biāo)（呼損率/阻塞率）作為動(dòng)態(tài)rwa問題的優(yōu)化冃標(biāo)。建立連 接時(shí)選擇阻塞率最小的方案，同時(shí)也意味著在有限的網(wǎng)路資源下能夠支持建立數(shù) 量盡可能多的光通道連接。4.2動(dòng)態(tài)rwa解決方案：

34、方案一：選路與波長(zhǎng)分配作為一個(gè)整體的問題來(lái)解決采用分層圖（layered-graph）的方法可以將選路和波長(zhǎng)分配一步完成。oxc 屮的光開關(guān)是空間域的連接，波長(zhǎng)分配是頻率域的連接，從提供通道的角度看， 空域和頻域的作用是一致的。分層圖將空域和頻域結(jié)合起來(lái)，繪出一張新的通道 圖，動(dòng)態(tài)rwa問題成為在分層圖中選取一條通道的問題。各種動(dòng)態(tài)選路的算法 都可考慮，fl標(biāo)是阻塞率最小。方案二：選路與波長(zhǎng)分配作為兩個(gè)子問題來(lái)解決通常由于計(jì)算量的問題，對(duì)于大型網(wǎng)絡(luò)的rwa方案一不可行。即使是啟發(fā) 式算法計(jì)算量也非常人。更實(shí)際的方法是把它分成選路和波長(zhǎng)分配兩個(gè)子問題， 這樣做的代價(jià)是結(jié)果不如以方案一來(lái)求解優(yōu)化。

35、冃前已提出了許多種啟發(fā)式方 法，現(xiàn)總結(jié)如下。（1）選路子問題:有三種基本的方法來(lái)解決此問題：固定路由、固定一備用路由和自適應(yīng)路由o 固運(yùn)路由(fixed routing)：對(duì)丁給定的源冃的對(duì)最簡(jiǎn)單的方法是選固定路由。 通常用固定最短路由。用標(biāo)準(zhǔn)的最短路徑算法(如dijkstra或bellman-ford算法) 預(yù)先為每個(gè)源冃的對(duì)算出最短路由。當(dāng)請(qǐng)求到達(dá)時(shí)，用預(yù)先決立的路由來(lái)建立光 路。顯然，這種方法的缺點(diǎn)是選路決定不是依據(jù)網(wǎng)絡(luò)當(dāng)前的狀態(tài)。這可能導(dǎo)致網(wǎng) 絡(luò)屮的一些鏈路過(guò)分擁塞，而其他的鏈路空閑。這將導(dǎo)致高的阻塞率。固定一備用路±1 (fixed-alternate routing)：這

36、是固定路由的一種改進(jìn)，一個(gè)請(qǐng) 求的路由從預(yù)先決定的固定路曲列表中選擇。這種方法叫固定一備用路曲選路。 當(dāng)請(qǐng)求到達(dá)時(shí)，源節(jié)點(diǎn)將要通過(guò)一些標(biāo)準(zhǔn)(如最小跳數(shù))在被選路由屮選擇一個(gè) 最佳路由，然后在該路由上建立光通道。這種方法比固定路由的阻塞率低。自適應(yīng)路fh(adaptive routing)：自適應(yīng)路由中，源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由由 當(dāng)前網(wǎng)絡(luò)的狀態(tài)(即所有進(jìn)行中的連接信息)決定。自適應(yīng)路由的一個(gè)典型形式 是口適應(yīng)最矩一代價(jià)路徑(adaptive shortest-cost-path)選路。當(dāng)一個(gè)連接請(qǐng)求到 達(dá)時(shí)，源節(jié)點(diǎn)根據(jù)網(wǎng)絡(luò)當(dāng)前狀態(tài)計(jì)算連接的最短路徑，如果沒有可用路由則阻塞。 這種方法的優(yōu)勢(shì)是它降

37、低了阻塞率。(2)波長(zhǎng)分配子問題：當(dāng)連接請(qǐng)求到達(dá)時(shí)，必須運(yùn)用在線(on-line)算法來(lái)分配波長(zhǎng)以使阻塞率最 小。到日前為止已有提出了許多啟發(fā)式算法，下面介紹兒種常見的：隨機(jī)(random)波長(zhǎng)分配：從該路由上已建光路所使用的波長(zhǎng)z外，隨 機(jī)地另選一個(gè)波長(zhǎng)。最先適用(first fit-ff)波長(zhǎng)：將波長(zhǎng)編號(hào)，從低到高依次觀察是否已 在該路由上建立光路使用，首先找到的就被使用。最大總數(shù)(maxsiumms)算法：思路是按分配后網(wǎng)絡(luò)屮仍可容納的光路 數(shù)最大為冃標(biāo)來(lái)分配波長(zhǎng)。采用該算法的阻塞率優(yōu)于ff算法(但有時(shí)差別不大), 代價(jià)是增加復(fù)雜性。最少使用波長(zhǎng)(least usedlu)：這種方法是為

38、了使波長(zhǎng)的負(fù)載均衡而 提hit,它優(yōu)先選用利用率小的波長(zhǎng)來(lái)滿足連接請(qǐng)求。但是這種機(jī)制引入了大量 的通信開銷來(lái)搜集有關(guān)信息計(jì)算波氏的利用情況，因此此方案不可取。最多使用波長(zhǎng)(most used -mu)：與lu相反，這種方法優(yōu)先選用利用率 高的波長(zhǎng)。由于mu保留了極少使用的波長(zhǎng)，節(jié)省了空閑資源，因而它的性能 會(huì)比lu好。mu的通信開銷與lu相同。在參考文獻(xiàn)2屮共介紹了 11種波長(zhǎng)分配算法，并對(duì)這些方法進(jìn)行了比較。 對(duì)于將選路和波長(zhǎng)分配分兩步進(jìn)行的算法，仿真表明，影響阻塞率的主要是選路 算法問。好的選路算法會(huì)顯著地減小阻塞率，而各種波長(zhǎng)分配算法的性能差別 不大。因此，在工程上可采用-種自適應(yīng)算法加

39、簡(jiǎn)易的ff波長(zhǎng)分配算法何。第五章一種新的rwa算法5.1新算法的提出以往rwa問題的研究提出了許多優(yōu)化冃標(biāo)，包括全網(wǎng)吞吐量最大、所需波 長(zhǎng)數(shù)和光纖數(shù)最少等等。在文獻(xiàn)9屮提出一種新的優(yōu)化口標(biāo)：最大化連接可得 的總利潤(rùn)。在該文中給出和應(yīng)的rwa算法可描述如下：hl dijkstra算法給出利 潤(rùn)最人的路徑，然后用貪婪算法來(lái)分配波長(zhǎng)。但該文中并沒有考慮網(wǎng)絡(luò)的其它參 數(shù)（如路徑長(zhǎng)度等），實(shí)際屮網(wǎng)絡(luò)運(yùn)營(yíng)商往往希望在獲得最大利潤(rùn)的同時(shí)能節(jié)省 資源。因此本文針對(duì)無(wú)波長(zhǎng)轉(zhuǎn)換wdm網(wǎng)絡(luò)提出了一種新的rwa算法，它的優(yōu) 化目標(biāo)為：在有限的資源下，建立的光路連接可獲得最大利潤(rùn)、最短路徑并盡量 減少所用的波長(zhǎng)數(shù)冃。我

40、們提出新算法的fl的有兩個(gè)：一是盡量把多fl標(biāo)結(jié)合起 來(lái)，折中考慮；二是針對(duì)這個(gè)目標(biāo)給出一個(gè)比較完善的算法描述。路徑最短即要求光通道經(jīng)過(guò)的光纖長(zhǎng)度最小，這對(duì)有許多節(jié)點(diǎn)紐成，但節(jié)點(diǎn) z間距離校大的網(wǎng)絡(luò)是非常重要的，因?yàn)檫@可以減少色散和噪聲積累。波長(zhǎng)是網(wǎng) 絡(luò)的一個(gè)重要資源，所以應(yīng)盡量減少波長(zhǎng)使用的數(shù)口。5.2問題的數(shù)學(xué)描述5.2.1網(wǎng)絡(luò)的假設(shè)：1）所有光纖中的復(fù)用波長(zhǎng)數(shù)相同；2）網(wǎng)絡(luò)節(jié)點(diǎn)無(wú)波長(zhǎng)轉(zhuǎn)換功能；3）對(duì)于給定的鏈路用無(wú)論用哪個(gè)波長(zhǎng)成本都是相同的。5.2.2符號(hào)定義輸入?yún)?shù)：無(wú)向圖g（v,a）：對(duì)于一給定網(wǎng)絡(luò)，其物理拓?fù)淇捎盟硎?。其中v為節(jié)點(diǎn) 集，a為邊集；n=|vi,l=iai, n表示節(jié)

41、點(diǎn)個(gè)數(shù)，l表示邊的個(gè)數(shù)。則v二 % ,嶺，匕a= a，仏，,血；d：流量矩陣=2表示在節(jié)點(diǎn)a和節(jié)點(diǎn)0之間有兩個(gè)連接請(qǐng)求；l：長(zhǎng)度矩陣；如果（q 0）纟a貝0 l郵=g；c：開銷矩陣；如果連接（& 0）纟a貝uc妙= oo；e：收入矩陣表示滿足節(jié)點(diǎn)q和節(jié)點(diǎn)0z間的連接請(qǐng)求所得的收入;a：表示每一鏈路可用波長(zhǎng)數(shù)；厶喚：允許光通道的最人氏度（由傳輸系統(tǒng)的物理?xiàng)l件限制）。常量：r妒 表示節(jié)點(diǎn)&和節(jié)點(diǎn)0之間的備用路由數(shù)；c；表示在第1個(gè)路由上連接節(jié)點(diǎn)理到節(jié)點(diǎn)0的開銷;s:表示在第r個(gè)路由上連接節(jié)點(diǎn)。到節(jié)點(diǎn)0的路徑長(zhǎng)度;場(chǎng)：如果第j條邊用來(lái)做從節(jié)點(diǎn)q到節(jié)點(diǎn)0第個(gè)路由則煬=1否則切=0。變量

42、:x：肚 必=1表示從節(jié)點(diǎn)理到節(jié)點(diǎn)0的連接占用第個(gè)路由、第k個(gè)波長(zhǎng)。5.2.3數(shù)學(xué)模型:冃標(biāo)函數(shù)：max(1)(2)"工工嘉工工心-工畸工心a=l 0=1r=l k=lr=lk=l式子（1）表示總利潤(rùn)（總收入一總開銷）最大minimize cr= £££厶£坊a=i 卩= r=l k=l式了（2）表示光通道總長(zhǎng)度最短。如果假設(shè)每段路徑的長(zhǎng)度相等（不妨都取為1）則上式表示光通道的跳數(shù)最小，此時(shí)優(yōu)化目標(biāo)就變?yōu)楣馔ǖ赖奶鴶?shù)最小。為了算法簡(jiǎn)單我們考慮把兩個(gè)h標(biāo)綜合在一起化成單h標(biāo)問題來(lái)解決，這里采用的是將連接所得利潤(rùn)與該連接的路徑長(zhǎng)度相比作為優(yōu)化目標(biāo)，

43、即max8(7上式的物理意義可以理解為單位長(zhǎng)度的利潤(rùn)最大或利潤(rùn)率最大，當(dāng)何段路徑 的長(zhǎng)度相等時(shí)可以理解為單位跳數(shù)的利潤(rùn)最大。minimize £££©£；a=l 0=1 r=l "1在各個(gè)鏈路上建立的光連接所用波長(zhǎng)數(shù)最小。約束條件：工工舄將 z，0r=l =1在節(jié)點(diǎn)q和節(jié)點(diǎn)0之間建立的光路數(shù)，不超過(guò)連接請(qǐng)求數(shù)目。n ” £叭久工工工爲(wèi)工心5 2 0冃，丄«=1 0=1 r=l a=1對(duì)每條鏈路jea,在該鏈路上建立的光連接數(shù)不能超過(guò)可用波長(zhǎng)數(shù)兄。厶仏 ,0，r每條光通道的長(zhǎng)度必須小于最人允許的光通道長(zhǎng)度lniax

44、oft h£££監(jiān)心 si vj=l,.l, vk=l,j (7) a=l /?=! r=l波長(zhǎng)一致性限制。兀；=(0,1)x/q,0,r, k(8)變量的整數(shù)限制。5.3新算法描述：為了使算法適用于規(guī)模較大的網(wǎng)絡(luò)，這里把選路與波長(zhǎng)分配分成兩個(gè)了問題 并分別用啟發(fā)式算法來(lái)解決，假設(shè)有n個(gè)連接請(qǐng)求。5.3.1算法的具體描述stepl：用dijkstra算法為業(yè)務(wù)矩陣屮的每個(gè)結(jié)點(diǎn)對(duì)尋找到利潤(rùn)率最高的一條路徑，并記住這些路徑的利潤(rùn)p與長(zhǎng)度l的比值（單位長(zhǎng)度的利潤(rùn)）。step2：把找到的所有路徑存儲(chǔ)在列表z中。z二z, z2,z?v,其中zj代表第i個(gè)源a的節(jié)點(diǎn)對(duì)之間利潤(rùn)

45、率最大的一條路徑。step3：把z生成一個(gè)輔助圖（生成規(guī)則參見5.3.2）。用禁忌搜索法找到輔助 圖g（v,e）的一個(gè)最小劃分設(shè)為叫，v2, v,如果kw 2則問題解決，輸 解即為%,嶺，v,其屮匕屮的所有節(jié)點(diǎn)所代表的源口的節(jié)點(diǎn)對(duì)對(duì)應(yīng)的 路徑都使用第i個(gè)波氏。如果k>2,那么并不是所有的請(qǐng)求都能滿足，所以只能 從%, v2,匕選出幾個(gè)作為輸出解。至于怎樣選擇可以作為一個(gè)背包問題 來(lái)解決（參見5.3.2）。這一問題已有成熟的算法來(lái)解決何，可以求出一個(gè)最佳解。5.3.2算法的一些解釋：1）stepl做的是選路工作，滿足前兩個(gè)目標(biāo)：選出利潤(rùn)最人和路徑最短的路 徑，也可以說(shuō)成是單位長(zhǎng)度的利潤(rùn)最大

46、。2）step3中的輔助圖的生成規(guī)則如下：i 輔助圖的節(jié)點(diǎn)代表連接的源目的節(jié)點(diǎn)對(duì)（不妨也相應(yīng)的用乙來(lái)表示）；ii 如果兩個(gè)連接中有共用的鏈路，則這兩個(gè)連接所對(duì)應(yīng)的源目的節(jié)點(diǎn)對(duì)所 生成的輔助圖的節(jié)點(diǎn)間存在一條邊，參見圖5.3.1。圖5.3.1中，左面是一個(gè)網(wǎng)絡(luò)的物理結(jié)構(gòu)，中間是選好的路曲及分配的波長(zhǎng), 右面是我們需要著色的輔助圖。為了避免網(wǎng)絡(luò)中的波長(zhǎng)沖突，輔助圖中相鄰的節(jié) 點(diǎn)必須染成不同的顏色。這樣波長(zhǎng)分配問題就轉(zhuǎn)化為輔助圖的著色問題。圖5.3.1輔助圖的生成3）圖著色問題:圖的點(diǎn)著色問題是一個(gè)npc問題,所以必須采用啟發(fā)式算法來(lái)獲得實(shí)用解?，F(xiàn)在已提出許多啟發(fā)式算法，如貪焚算法(greedy a

47、lgorithms)>模擬追火算法(sasimulated annealing)、遺專 算去(gagenetic algorithms)> 禁忌紫 (ts-tabu search)等。其中禁忌搜索的性能最好(參見圖5.3.2 5.3.3)。(注 圖中的dsatur是貪婪算法的一種)10'lolo2心|0,:-10 運(yùn)時(shí)間單國(guó)秒i:聖m刪熊:二:ii iiiiiiiiiiiiki1ki11 vcfllllllllllllllllll . tot <3bt±iiiiiaiiiiiiiiuiiiii aiee卸ill mu mu lim mu mu nai mu

48、mu iiiiciim mu mu biiiiiii awww10 010020030040050060c節(jié)點(diǎn)個(gè)數(shù)圖5.3.2齊種圖著色算法運(yùn)行時(shí)間對(duì)比90201030100200300400500600節(jié)點(diǎn)個(gè)數(shù)顏色個(gè)數(shù)算法的運(yùn)行時(shí)間圖5.3.3不同算法著色所需顏色數(shù)對(duì)比4) 用禁忌搜索方法解圖著色問題用禁忌搜索方法解圖著色問題，可得出使所有的節(jié)點(diǎn)都被著色所需的最小顏 色數(shù)k。算法中應(yīng)用禁忌搜索算法，就是要對(duì)第三個(gè)冃標(biāo)(波長(zhǎng)數(shù)最小)進(jìn)行優(yōu) 化。設(shè)輔助圖為g(v,e),其中v是節(jié)點(diǎn)集v=l,2,-,n,e是邊集，e= (i,j)li,j gv, (i,j)表示連接i,j的一個(gè)邊。若匕uv、v=u

49、：m，且匕內(nèi)部的任何兩 個(gè)節(jié)點(diǎn)沒有e中的邊直接連接，則稱（叫，v2, v,）為v的一個(gè)劃分。圖的節(jié)點(diǎn)著色問題可以描述為：求一個(gè)最小的k,使得（叫，v2,匕）為v 的一個(gè)劃分。對(duì)于給定n個(gè)節(jié)點(diǎn)的無(wú)向圖，禁忌搜索算法求解圖節(jié)點(diǎn)覆蓋問題可以分為兩 步。第一步是給定一個(gè)常數(shù)k,考慮tl標(biāo)函數(shù)/（vp v2, vk）=e （ v, ） l+l£（v2）l+ - +ie（匕）1,其中ie（匕）1 為中 直接連接兩個(gè)節(jié)點(diǎn)的邊數(shù)。（叫，嶺，匕）為v的一個(gè)劃分的充分必要條件 是/（x，v2,匕）= 0。第二步的主耍工作是：對(duì)不滿足/（v（, v2,匕）=0的（, v2,匕）進(jìn)行優(yōu)化計(jì)算，從而決定是否增

50、加子集的個(gè)數(shù)k；從滿足/（vp v2, vj = 0的劃分屮選擇最小的劃分?jǐn)?shù)ko將解的形式用下面形式表示：（ 2八s =, <i.<k, 1 <j<n1沖2幾丿其中-表示的j個(gè)節(jié)點(diǎn)在的匚集合中。解的第x個(gè)分量變化為:從原在第.集合中改變到第匚集合中。每一個(gè)解s的鄰域由那些滿足上面的變化且只有一個(gè)分量變化的解組成，共 有nk個(gè)鄰居（包含自身），每一個(gè)節(jié)點(diǎn)（分量）可以選擇k個(gè)劃分集之一。禁忌：z 、/ 、'x<lx )lxj即還原到原有狀態(tài)。這種禁忌考慮了變化的方向。特赦規(guī)則：若/是當(dāng)前最優(yōu)解，當(dāng)一個(gè)受禁的鄰居x滿足/（x）</（x*）-l時(shí)，則受禁的變

51、化特赦。因?yàn)槟繕?biāo)值為非負(fù)整數(shù)，條件/（x）</（x*）-l表示x 的口標(biāo)值小于當(dāng)前最優(yōu)解x*的口標(biāo)值。這屬于基于評(píng)價(jià)值的規(guī)則。程序框架如下:已知?jiǎng)澐旨蠑?shù)k,解的形式s,冃標(biāo)函數(shù)解的變化，鄰域映射n (s),禁 忌長(zhǎng)度，忖標(biāo)值下界廠，兩個(gè)忖標(biāo)值沒有改進(jìn)的最大允許迭代次數(shù)nbmaxo開始：任選一個(gè)初始解；n bi ter： =0； (*當(dāng)前的迭代步*)bestiter： =0； (*當(dāng)前最優(yōu)解所在的迭代步*)bestsol: =s； (*當(dāng)前的最優(yōu)解*)令 z= /(s), a(z)： =z1 ；(特赦值)初始化禁忌表h；當(dāng)(f (s)>/* )且(nbiterbestiter<

52、;nbmax)時(shí)，計(jì)算nbiter： = nbiter +1 ；產(chǎn)生n(s)的一個(gè)候選集v：要求候選元素x是非禁忌的或是特赦的/(x)<a(/(s)；在廠中選目標(biāo)值最有的解s* ；若/(s*)<a( f (s),則 a(/(s*)： = a(/(s*)-1；否則若/(s)<a(/(5*),則 a(/(s*)： = a(/(s)-1；更新禁忌表；若 /(5*)< f (bestsol),則 bestsol: = s ' ； bestiter： = nbiter；s： = s*繼續(xù)；結(jié)束。輸出：計(jì)算中的最優(yōu)解。5）背包問題及其在算法屮的應(yīng)用背包問題是指有不同價(jià)值、不

53、同重量的物品k件，求從這k件物品中選取一 部分物晶的選擇方案，使選中物晶的總重量不超過(guò)指定的限制重量，但選中物品 的價(jià)值z(mì)和為最大。當(dāng)算法中用到背包問題時(shí)，可以把算法中的參數(shù)與背包問題 做如下對(duì)應(yīng)：背包問題中的概念算法中的參數(shù)k件物品%,嶺，匕物品的總重量選出的匕的總個(gè)數(shù)物品的限雄帝量最多可用波長(zhǎng)數(shù)久物品的價(jià)值%屮所有路徑的利潤(rùn)率之和背包問題的解決及程序可見參考資料13o5.4新算法與原有算法的比較將新算法與以往算法相比較而言可得出以下結(jié)論：1. 新算法屮考慮三個(gè)網(wǎng)絡(luò)特性，是這三個(gè)特性的一個(gè)折屮?，F(xiàn)有的文獻(xiàn)大多 僅考慮眾多網(wǎng)絡(luò)優(yōu)化的冃標(biāo)中的一個(gè)，這就大大地限制了它們的應(yīng)用范圍。網(wǎng)絡(luò) 的多目標(biāo)優(yōu)

54、化將是未來(lái)rwa問題研究的一個(gè)趨勢(shì)，怎樣綜合優(yōu)化多個(gè)目標(biāo)也是 rwa算法研究的一個(gè)角度。2. 新算法在路徑確定以后分配波長(zhǎng)時(shí)是從整體考慮的，應(yīng)用了現(xiàn)代優(yōu)化算 法屮的禁忌搜索算法，并把它和背包問題結(jié)合起來(lái)而求得的解。解的優(yōu)化程度主 耍取決于禁忌搜索的性能，而對(duì)比表明禁忌搜索在解決這類問題時(shí)的性能是很好 的，所以得出的解也是接近最優(yōu)的。3. 選路算法對(duì)減小利用的波長(zhǎng)數(shù)1=1也有很大影響，而我們?cè)谛滤惴ǖ倪x路 問題中為了簡(jiǎn)單沒有考慮這個(gè)因素，只是在分配波長(zhǎng)時(shí)盡量?jī)?yōu)化這個(gè)h標(biāo)。另外, 我們?cè)谶x路和波長(zhǎng)分配問題中都采用的是啟發(fā)式算法，所以最后得到的優(yōu)化解不 一定是最優(yōu)解。結(jié)束語(yǔ)wdm光傳送網(wǎng)被認(rèn)為是下一

55、代高速?gòu)V域骨干網(wǎng)的理想選擇，就日前的研究 狀況而言，該領(lǐng)域內(nèi)的下列問題有待進(jìn)行深入研究1）文中已指出，rwa算法的動(dòng)態(tài)程度越高，其性能越好。但動(dòng)態(tài)rwa算法基 木上都是屮心式算法，需要利用全網(wǎng)信息。從簡(jiǎn)單和便于擴(kuò)展的角度出發(fā)，很有 必要研究快速，高效的分布式算法。2）是否需要在wdm網(wǎng)中引入波長(zhǎng)變換一直是光網(wǎng)研究領(lǐng)域的熱點(diǎn)問題，波長(zhǎng) 變換究竟能對(duì)網(wǎng)絡(luò)性能有多大的改善，否可用波長(zhǎng)變換替代全功能波長(zhǎng)變換以及 如何引入部分波長(zhǎng)變換等問題仍值得深入研究。3）由于實(shí)際鋪設(shè)的光纜都含有多對(duì)光纖，研究多光纖網(wǎng)以充分利用資源是十分 必要的。4）網(wǎng)絡(luò)優(yōu)化的目標(biāo)很多，但現(xiàn)有文獻(xiàn)大多僅考慮其中一個(gè)，其結(jié)果雖然在某一 網(wǎng)絡(luò)特性上達(dá)到了最優(yōu)，但網(wǎng)絡(luò)的代價(jià)由于缺少各個(gè)特性z間的均衡和折衷，并 沒有因?yàn)椴ㄩL(zhǎng)分配的優(yōu)化而降低或沒有達(dá)到最優(yōu)。因此需要研究綜合優(yōu)化指標(biāo)下 的rwa算法。5）光網(wǎng)中出現(xiàn)故障（如鏈路和節(jié)點(diǎn)故障）時(shí)，特殊設(shè)計(jì)的rwa算法能夠在一 定程度上進(jìn)行補(bǔ)償。研究支持光層口愈的高效rwa算