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

1、rwa算法的研究摘要：本文研究了 wdm網(wǎng)中的選路與波長分配(rwa)問題。主要針對的是 有波長一致性限制的網(wǎng)絡(luò)。首先簡單介紹了 wdm光傳送網(wǎng)的一些基本概念。然 后對wdm傳送網(wǎng)的選路與波長分配(rwa)|nj題進(jìn)行了分類，并綜述了各種條件 下的rwa算法，對其進(jìn)行了分類、比較。最后在對以往算法分析和比較的基礎(chǔ) 上，提出了一個新的rwa算法。新算法中考慮了多個網(wǎng)絡(luò)設(shè)計優(yōu)化目標(biāo)，對網(wǎng) 絡(luò)運(yùn)營商有一定的參考價值。關(guān)鍵詞：wdm；選路與波長分配；優(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)是光纖通信未來發(fā)展的主要方向之一。由于光網(wǎng) 絡(luò)對傳輸信號的速率和格式透明，具有靈活的波長選路和動態(tài)資源配置能力，可 以實(shí)現(xiàn)網(wǎng)絡(luò)的動態(tài)重構(gòu)，被認(rèn)為是通信網(wǎng)絡(luò)升級的首選方案。如何利用現(xiàn)有的和 即將敷設(shè)的光纖連網(wǎng)，構(gòu)成未來高速、大容量、多業(yè)務(wù)的wdm網(wǎng)絡(luò)已經(jīng)成為光 通信領(lǐng)域小的一個重大問題。wdm網(wǎng)絡(luò)節(jié)點(diǎn)處采用光分插復(fù)用器(oadm)或 光交叉連接設(shè)備(oxc)在光層建立光連接，即光通道(optical path),為高層 的多個邏輯電網(wǎng)絡(luò)提供了高速、人容量的信息傳送平臺。光通道的建立，要求在 傳送網(wǎng)的物理結(jié)構(gòu)中選擇一條曲業(yè)務(wù)源點(diǎn)到宿點(diǎn)的路出，并為其分配一定的波長 信道(參見圖l.do考慮到波長

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

6、dm： wavelength division multiplexing）技術(shù)是在一根光纖 屮同時傳輸多波長光信號的一項(xiàng)技術(shù)。其基本原理是在發(fā)送端將不同波長的光信 號組合起來（復(fù)用），并耦合到光纜線路上的同一根光纖中進(jìn)行傳輸，在接收端 乂將組合波氏的光信號分開（解復(fù)用），并作進(jìn)一步處理，恢復(fù)出原信號后送入 不同的終端，因此將此項(xiàng)技術(shù)稱為光波長分割復(fù)用，簡稱光波分復(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é)為來fl電復(fù)用段層的客戶信息選擇路由 和分配波長，為靈活的網(wǎng)絡(luò)選路安排光信道連接，處理光信道開銷，提供光信道層的檢測，管理功能。并在故障發(fā)生吋，通過重新選路或直接把工作業(yè)務(wù)切換到 預(yù)定的保護(hù)路由來實(shí)現(xiàn)保護(hù)倒換和網(wǎng)絡(luò)恢復(fù)。2.2.2光復(fù)用段層光復(fù)用段層(optical multiplexing section layer)保證相鄰兩個波長復(fù)用傳輸設(shè) 備間多波

8、長復(fù)用光信號的完整傳輸，為多波長信號提供網(wǎng)絡(luò)功能。其主要包括： 為靈活的多波長網(wǎng)絡(luò)選路重新安排光復(fù)用段功能；為保證多波長光復(fù)用段適配信 息的完整性處理光復(fù)用段開銷；為網(wǎng)絡(luò)的運(yùn)行和維護(hù)提供光復(fù)用段的檢測和管理 功能。2.2.3光傳輸段層光傳輸段層(optical transmission section layer*)為光信號在不同類型的光傳輸 媒質(zhì)(如g.652,g.653,g.655光纖等)上提供傳輸能力，同時實(shí)現(xiàn)對光放人器或中 繼器的檢測和控制功能等。通常會涉及以下問題：功率均衡問題、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)的一個例子。1116為物理鏈路，每根光纖上可采 用多個波長。c)接入點(diǎn)a-e oxc11 16物理鏈路圖231網(wǎng)路的物理拓?fù)鋱D2.3.2(a)為上圖建立光路的例子。在一根光纖上不能為不同光路分配相同 波長。圖2.3.2(a)的光路連接用圖2.3.2(b)表示即為邏輯拓?fù)?。例如圖2.3.2(a)中， 節(jié)點(diǎn)b與節(jié)點(diǎn)e間的光路是經(jīng)過節(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路由和波長分配（b）邏輯結(jié)構(gòu)圖2.3.2 光路舉例實(shí)際設(shè)計中，一種rwa情況是：提出所需建立的光路，為這種光路選取物 理路由并分配相應(yīng)的波長。例如，圖2.3.2（b）中提岀要建立5條光路，圖2.3.2（a） 就是一種選路和波長分配方案。2.4 wdm光傳送網(wǎng)拓?fù)浣Y(jié)構(gòu)的主耍議題在研究rwa問題的文獻(xiàn)屮，通常將網(wǎng)絡(luò)支持的業(yè)務(wù)分為兩類：1）靜態(tài)業(yè) 務(wù)：給定一組連接建立請求，需要為這些請求尋找路由并在其路由上分配波長， 以使某些性能指標(biāo)達(dá)到最優(yōu)（如全網(wǎng)吞吐量最大、所需波長數(shù)和光纖數(shù)最少等 等:2）動態(tài)業(yè)務(wù)：光路請求隨機(jī)到達(dá)和離開網(wǎng)絡(luò)，相應(yīng)當(dāng)性能指標(biāo)通常是光路 的阻

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

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

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

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

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

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

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

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

19、有連接必須采用同一波長，這就是所謂的波長連續(xù)性限制。對電路 交換網(wǎng)而言，僅當(dāng)該級別的鏈路容量都被片用時，才會發(fā)生阻塞，而對于波長路 由網(wǎng)絡(luò)，卻遠(yuǎn)非如此。如圖2.7.2（a）所示，在網(wǎng)絡(luò)屮建立了兩個光通道，節(jié)點(diǎn)1 和2之間采用人波長，節(jié)點(diǎn)2和3之間的波長是«，現(xiàn)在假設(shè)要在1、3之間 建立一條光通道，即使節(jié)點(diǎn)1、3之間的每個鏈路都有空閑的波長也不一定能建 立這個光通道，這是因?yàn)樵趦蓚€鏈路上可得到的波長是不同的。因此，與電路交 換網(wǎng)絡(luò)和比，波長路由網(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、全光波長路由網(wǎng)絡(luò)圖2.7.2波長連續(xù)性限制如果能在中間節(jié)點(diǎn)進(jìn)行波長變換，從一個波長轉(zhuǎn)換到另一個波長，對光網(wǎng) 絡(luò)將是非常有利的。如圖2.7.2（b）所示，節(jié)點(diǎn)2的波長變換器把波長從人變換到 入，在節(jié)點(diǎn)1、2中間應(yīng)用禺波長，在節(jié)點(diǎn)2、3中間應(yīng)用入波長，從節(jié)點(diǎn)1 到節(jié)點(diǎn)3的光通道便可建立。在含有波長變換器的網(wǎng)絡(luò)中，光通道能在不同的鏈 路上用不同的波長而建立，從而人人提高網(wǎng)絡(luò)的靈活性，消除光通道的波長沖突。 引入波長變換技術(shù)，可以實(shí)現(xiàn)波長的再利用，更有效地進(jìn)行路由的選擇，降低網(wǎng) 絡(luò)阻塞率，從而提高wdm網(wǎng)的靈活性和可擴(kuò)充性。波長變換器對wdm光網(wǎng)絡(luò)的性能究竟有多大的改善，是近年來的一個熱 點(diǎn)課題。現(xiàn)在

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

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

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

24、 最短優(yōu)先隨機(jī) 固定 概率 最小順序算法(貪婪算法)隨機(jī)循環(huán)(random rounding)啟發(fā)式組合算法整數(shù)線性規(guī)劃最優(yōu)化圖3.3.2選路算法(1)選路算法：在選路問題中，考慮所有可能的源目的對是不實(shí)際的，因?yàn)橛嬎銜r間隨著網(wǎng)絡(luò)規(guī)模的增長成指數(shù)增長。因此，尋找功能通常由最短路徑算法及它的變種(variations)實(shí)現(xiàn)。在k 最短路徑算法中(即：有多個備選路由)，選擇功能 由順序算法或組合優(yōu)化算法來實(shí)現(xiàn)。順序算法（也叫貪焚算法）是最簡單的一種。 它按順序?yàn)槊恳粭l光路進(jìn)行選擇，這其中需要考慮兩方面：選擇順序、選擇規(guī)則。 選擇順序是指先為哪一個光連接選擇路由，選擇規(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)最短路算法是一種最短 路算法，但是鏈路代價可以隨著已建立的路由數(shù)動態(tài)的變化。因此，它需要一個 尋找順序。例如：最人業(yè)務(wù)量優(yōu)先（largest traffic first）：從需要建立的光路中優(yōu)先選擇業(yè) 務(wù)量最人的光路來尋找路由；隨機(jī)（random）機(jī)制以隨機(jī)的順序來選擇需要建立的光路。但是這種方法不需要選擇功能，因?yàn)樗彩侵粸槊總€源目的對選擇一個路 由。 k最短路徑（kspkshortest pat

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

46、。2）step3中的輔助圖的生成規(guī)則如下：i 輔助圖的節(jié)點(diǎn)代表連接的源目的節(jié)點(diǎn)對（不妨也相應(yīng)的用乙來表示）；ii 如果兩個連接中有共用的鏈路，則這兩個連接所對應(yīng)的源目的節(jié)點(diǎn)對所 生成的輔助圖的節(jié)點(diǎn)間存在一條邊，參見圖5.3.1。圖5.3.1中，左面是一個網(wǎng)絡(luò)的物理結(jié)構(gòu)，中間是選好的路曲及分配的波長, 右面是我們需要著色的輔助圖。為了避免網(wǎng)絡(luò)中的波長沖突，輔助圖中相鄰的節(jié) 點(diǎn)必須染成不同的顏色。這樣波長分配問題就轉(zhuǎn)化為輔助圖的著色問題。圖5.3.1輔助圖的生成3）圖著色問題:圖的點(diǎn)著色問題是一個npc問題,所以必須采用啟發(fā)式算法來獲得實(shí)用解。現(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)時間單國秒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)個數(shù)圖5.3.2齊種圖著色算法運(yùn)行時間對比90201030100200300400500600節(jié)點(diǎn)個數(shù)顏色個數(shù)算法的運(yùn)行時間圖5.3.3不同算法著色所需顏色數(shù)對比4) 用禁忌搜索方法解圖著色問題用禁忌搜索方法解圖著色問題，可得出使所有的節(jié)點(diǎn)都被著色所需的最小顏 色數(shù)k。算法中應(yīng)用禁忌搜索算法，就是要對第三個冃標(biāo)(波長數(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的一個邊。若匕uv、v=u

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

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

51、化特赦。因?yàn)槟繕?biāo)值為非負(fù)整數(shù)，條件/（x）</（x*）-l表示x 的口標(biāo)值小于當(dāng)前最優(yōu)解x*的口標(biāo)值。這屬于基于評價值的規(guī)則。程序框架如下:已知劃分集合數(shù)k,解的形式s,冃標(biāo)函數(shù)解的變化，鄰域映射n (s),禁 忌長度，忖標(biāo)值下界廠，兩個忖標(biāo)值沒有改進(jìn)的最大允許迭代次數(shù)nbmaxo開始：任選一個初始解；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)時，計算nbiter： = nbiter +1 ；產(chǎn)生n(s)的一個候選集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é)束。輸出：計算中的最優(yōu)解。5）背包問題及其在算法屮的應(yīng)用背包問題是指有不同價值、不

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

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

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