王鯨魚，冉金志，王 平

(1.國(guó)防科學(xué)技術(shù)大學(xué) 信息通信學(xué)院，陜西 西安 710106；2.西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論與關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071)

隨著信息技術(shù)的高速發(fā)展，網(wǎng)絡(luò)帶寬需求多樣化和網(wǎng)絡(luò)中傳輸?shù)男畔⒘砍时ㄊ皆鲩L(zhǎng)[1-2]，傳統(tǒng)的波分復(fù)用技術(shù)采用固定頻譜間隔來分配頻譜，導(dǎo)致頻譜資源浪費(fèi)嚴(yán)重。彈性光網(wǎng)絡(luò)(Elastic Optical Network，EON)由于能夠更靈活地利用頻譜資源，受到越來越多的關(guān)注[3-7]。路由選擇與頻譜分配(Routing and Spectrum Assignment，RSA)問題是彈性光網(wǎng)絡(luò)中的核心問題，其目標(biāo)是為每個(gè)到達(dá)的業(yè)務(wù)計(jì)算并分配合理的帶寬和路由，從而優(yōu)化頻譜利用率[2]。由于頻譜分配需要遵守一致性和連續(xù)性約束[3-4]，在網(wǎng)絡(luò)的動(dòng)態(tài)建立與拆除過程中，可能會(huì)產(chǎn)生大量的頻譜碎片，而降低頻譜資源的利用率并提升網(wǎng)絡(luò)的阻塞率[4-8]。針對(duì)這一問題，已經(jīng)提出了一些頻譜整理的方法。文獻(xiàn)[5]通過在頻譜分配時(shí)增加不同業(yè)務(wù)間的保護(hù)帶寬最小化業(yè)務(wù)帶寬阻塞率，但是只適用固定調(diào)制方式，易造成帶寬資源浪費(fèi)，頻譜利用率低。文獻(xiàn)[8]提出了一種基于連接保持時(shí)間的非破壞性碎片整理方案。文獻(xiàn)[9]在將頻譜碎片整理方法分為串行方式與并行方式的基礎(chǔ)上主要研究了彈性光網(wǎng)絡(luò)的并行頻譜碎片整理。文獻(xiàn)[10]主要介紹了跳躍重整、推挽重整和先接后斷三種非中斷頻譜碎片整理方法并比較了它們的優(yōu)缺點(diǎn)。

雖然目前提出了很多碎片整理的算法，但大多僅考慮滿足當(dāng)前到達(dá)業(yè)務(wù)能夠建立，沒有考慮整理碎片和業(yè)務(wù)建立后鏈路狀態(tài)對(duì)后續(xù)業(yè)務(wù)建立的影響?；诖耍P者提出一種基于多準(zhǔn)則決策(Multiple Criteria Decision Making，MCDM)[11-13]的彈性光網(wǎng)絡(luò)頻譜整理算法，在整理頻譜碎片的過程中，當(dāng)涉及到碎片的移動(dòng)或重路由等選擇性問題時(shí)，傳統(tǒng)做法是將業(yè)務(wù)連接移動(dòng)至空閑頻隙即可，而該過程可能會(huì)導(dǎo)致移動(dòng)后網(wǎng)絡(luò)的碎片率增加，反而降低了網(wǎng)絡(luò)的容量。筆者擬利用多準(zhǔn)則決策的方法對(duì)碎片整理過程中遇到的選擇性問題綜合考慮各種指標(biāo)做出決策，從而在最大程度上整理頻譜碎片，降低網(wǎng)絡(luò)的阻塞率。

1 相關(guān)定義

為了方便算法的描述，首先對(duì)相關(guān)術(shù)語進(jìn)行解釋和定義。

(1) 額外空間中的額外頻隙

將頻譜末端的一些空間也就是每個(gè)鏈路中超出主要頻譜部分的一些空間稱為額外空間。額外空間中的頻隙稱為額外頻隙。為了給主要頻譜部分留出空間，需要將一些移動(dòng)后可以改善頻譜的連接移動(dòng)到額外空間。額外空間中額外頻隙的長(zhǎng)度應(yīng)至少等于連接請(qǐng)求的最大值，并且額外空間不能建立連接請(qǐng)求。

(2) 標(biāo)簽

在算法運(yùn)行過程中，不同階段整理不同類型的業(yè)務(wù)連接，“標(biāo)簽”是指對(duì)不同連接根據(jù)類型的不同對(duì)它們進(jìn)行標(biāo)記。

① “不移動(dòng)”標(biāo)簽?！安灰苿?dòng)”標(biāo)簽標(biāo)記的是頻譜開始端的邊緣的連接且如果一個(gè)連接的左側(cè)超過1/2(含1/2)相鄰于另一個(gè)“不移動(dòng)”連接，則它也將標(biāo)簽為“不移動(dòng)”標(biāo)簽。在碎片整理過程中，“不移動(dòng)”連接不會(huì)移到任何地方。如圖1所示，因?yàn)檫B接A和連接B在頻譜開始端，所以標(biāo)記為“不移動(dòng)”連接；因?yàn)檫B接C相鄰于連接A，所以C也被標(biāo)記為 “不移動(dòng)”連接；因?yàn)檫B接D占用了兩個(gè)鏈路，其中在鏈路3上的連接相鄰于連接B，滿足超過1/2(含1/2)相鄰于標(biāo)記有“不移動(dòng)”連接的條件，所以連接D也被標(biāo)記為“不移動(dòng)”連接。

圖1 “不移動(dòng)”連接示意圖

② “消失”標(biāo)簽。如果連接的剩余時(shí)間小于預(yù)定義的閾值(例如2 s)，則將該連接標(biāo)簽為“消失”。

③ “左移”標(biāo)簽。如果可以將連接移到更好的位置(即更靠近頻譜的開始側(cè))，則將該連接標(biāo)記為“左移”。

④ “右移”標(biāo)簽。此標(biāo)簽用于標(biāo)記連接無法移到更好的地方或重新路由到其他路由的連接。

⑤ “重新路由”標(biāo)簽。不可移動(dòng)的連接可以通過在其他可用路由進(jìn)行重路由，從而有第二次機(jī)會(huì)設(shè)置在更好的位置，因此筆者將可重路由的連接標(biāo)記為“重新路由”。

⑥ “縮短”標(biāo)簽：當(dāng)業(yè)務(wù)連接被重新路由后，該連接所占用的鏈路數(shù)會(huì)減少，使得業(yè)務(wù)連接的傳輸占用的頻隙數(shù)量減少，將這樣的連接標(biāo)記為“縮短”連接。

(3) 連接干擾

為了將空閑頻譜塊聚合到每個(gè)鏈路的頻譜末端，所以當(dāng)一條連接干擾到其他連接向頻譜開始端移動(dòng)時(shí)，將這條連接稱為“干擾源”?！案蓴_源”的判斷條件為：

① 該連接沒有被標(biāo)簽為“不移動(dòng)”，因?yàn)椤安灰苿?dòng)”連接在整理的過程中不會(huì)被移動(dòng)并且處于頻譜的開始端，不會(huì)影響其他連接前移；

② 該連接所占的頻隙數(shù)和與該連接相鄰的空閑頻隙數(shù)之和大于該連接右側(cè)第一個(gè)連接的大??；

③ 該連接之前的空閑頻隙數(shù)量小于該連接之后第一個(gè)連接所占的頻隙數(shù)量。

圖2 連接干擾示意圖

例如圖2中，連接A沒有被標(biāo)簽為“不移動(dòng)”，連接A所占用的頻隙數(shù)和相鄰空閑頻隙之和大于連接B的大小且連接A之前的空閑頻隙數(shù)小于連接B所占用的頻隙數(shù)，所以連接A干擾連接B。

(4) 空閑相鄰空間的總和

空閑相鄰空間的總和表示連接之前和之后的相鄰空閑頻隙的數(shù)量總和。

(5)鏈路碎片率

鏈路碎片率(L)與鏈路中的空閑頻隙有關(guān)。計(jì)算一個(gè)具有N個(gè)空閑區(qū)域鏈路的碎片率：

(1)

其中，F(xiàn)i表示第i個(gè)空閑區(qū)域中空閑塊的數(shù)量。鏈路碎片率越大，該鏈路就越難再加入新連接。

最大碎片率(M)指的是鏈路中出現(xiàn)空閑頻隙與有業(yè)務(wù)的頻隙交叉排列。設(shè)一條鏈路具有N個(gè)頻隙，當(dāng)可用頻隙的數(shù)量為奇數(shù)而被占用的頻隙為偶數(shù)時(shí)，鏈路的碎片率最大，此時(shí)需要利用上限函數(shù)來計(jì)算其大小。此時(shí)M為

(2)

例如當(dāng)N=11時(shí)，鏈路中的空閑頻隙為6，則M=62=36。

連接碎片率(C)是一個(gè)連接在鏈路中的碎片率，由L平均后得到

(3)

其中，i表示連接的第i個(gè)連接，Q表示連接的總數(shù)。

為了達(dá)到比較碎片的連接速率，并方便觀察，將碎片率進(jìn)行指標(biāo)化，使得其范圍為[0，1]。首先將鏈路碎片率(L)及式(1)由式(4)進(jìn)行歸一化，得到指標(biāo)化鏈路碎片率(NL)：

(4)

然后，將NL除以連接的總數(shù)，得到指標(biāo)化碎片率N：

(5)

2 基于多準(zhǔn)則決策的頻譜碎片整理算法描述

2.1 基于多準(zhǔn)則決策的頻譜碎片整理算法

頻譜碎片整理是將空閑頻隙聚合在可用頻譜的末尾，將到達(dá)剩余時(shí)間的連接與不可移動(dòng)的連接轉(zhuǎn)移至規(guī)定的額外空間中以實(shí)現(xiàn)頻譜碎片整理。而在移動(dòng)頻譜碎片的過程中，移動(dòng)不同的頻譜碎片對(duì)網(wǎng)絡(luò)的影響不同，有的可能會(huì)降低網(wǎng)絡(luò)的碎片率，有的則有可能適得其反。所以，在每次選擇時(shí)，采用多準(zhǔn)則決策對(duì)頻譜碎片進(jìn)行整理，可以基于網(wǎng)絡(luò)此時(shí)的狀態(tài)在每個(gè)階段中做出最佳決策來進(jìn)行頻譜碎片的整理。

基于多準(zhǔn)則決策的彈性光網(wǎng)絡(luò)頻譜碎片整理算法分為5個(gè)階段。這5個(gè)階段中，每個(gè)階段都會(huì)用不同的標(biāo)簽標(biāo)記不同類型的連接，并根據(jù)多準(zhǔn)則決策所設(shè)置的權(quán)重對(duì)連接進(jìn)行判斷，最后采取最佳的方案。

第1個(gè)階段，通過判斷剩余時(shí)間，將滿足設(shè)定時(shí)間閾值的連接標(biāo)簽為“消失”，然后通過預(yù)先定義的權(quán)重將標(biāo)簽“消失”的連接轉(zhuǎn)移到額外空間，直到額外空間被填滿或沒有標(biāo)簽為“消失”的連接，這一階段完成后，主要頻譜中就會(huì)出現(xiàn)一些空閑的空間。

第2個(gè)階段，通過重新路由的方法，減少連接的數(shù)量以便騰出更多的空閑頻隙。

第3個(gè)階段，利用首次命中算法將“左移”連接移動(dòng)到頻譜的開始端，并將滿足“不移動(dòng)”連接指標(biāo)的連接標(biāo)簽為“不移動(dòng)”連接。

圖3 算法總流程圖

第4個(gè)階段，利用K-最短路徑法對(duì)“不移動(dòng)”連接進(jìn)行重新路由。如果“不移動(dòng)”連接不能被重新路由，則更新其標(biāo)簽為“右移”連接。

第5個(gè)階段，首先將“右移”連接移動(dòng)到額外空間，然后返回到第3個(gè)階段進(jìn)行循環(huán)，直到不執(zhí)行操作或者所有的連接都標(biāo)簽為“不移動(dòng)”連接。

總流程如圖3所示。5個(gè)階段的流程如圖4至圖8所示。

圖4 第1階段算法流程

階段1：

(1) 為每個(gè)源到目標(biāo)節(jié)點(diǎn)預(yù)先進(jìn)行計(jì)算儲(chǔ)存K條最短路徑；

(2) 將所有剩余時(shí)間小于t的連接標(biāo)簽為“消失”連接；

(3) 對(duì)于所有的“消失”連接，如果額外空間中有空閑空間，則進(jìn)行下一步；

(4) 利用MCDM計(jì)算“消失”連接的得分，并將最佳連接轉(zhuǎn)移到額外空間，直到所有“消失”連接轉(zhuǎn)移完畢或額外空間沒有空閑空間。

圖5 第2階段算法流程圖

階段2：

(1) 根據(jù)K-最短路徑篩選出可以重新路由的連接并且標(biāo)記為“縮短”連接；

(2) 對(duì)于所有“縮短”連接，利用MCDM計(jì)算其得分，得分最高的進(jìn)行重路由，直到?jīng)]有“縮短”連接；

(3) 更新連接的標(biāo)簽。

圖6 第3階段算法流程圖

階段3：

(1) 將在頻譜第一個(gè)邊緣或與頻譜第一個(gè)邊緣的連接相鄰或1/2相鄰的連接標(biāo)記為“不可移動(dòng)”連接；

(2) 將連接前有空閑空間的連接標(biāo)記為“左移”連接；

(3) 對(duì)于所有“左移”連接，利用MCDM計(jì)算其得分；

(4) 將得分最高的連接利用首次命中算法將其進(jìn)行左移，直到?jīng)]有“左移”連接。

圖7 第4階段算法流程圖

階段4：

(1) 對(duì)于所有標(biāo)記“不可移動(dòng)”連接，利用K-最短路徑篩選出可以重新路由的連接并且更新其標(biāo)簽為“重路由”連接；

(2) 將不可重新路由的“不可移動(dòng)”連接更新其標(biāo)簽為“右移”連接；

(3) 對(duì)于所有“重路由”連接，利用MCDM計(jì)算其得分，將最佳連接進(jìn)行重路由，直到?jīng)]有“重路由”連接。

階段5：

(1) 如果額外空間有空閑空間，則進(jìn)行下一步；

(2) 對(duì)于所有標(biāo)記“右移”連接，利用多準(zhǔn)則決策計(jì)算其得分，將最佳連接轉(zhuǎn)移到額外空間；

(3) 直到所有“右移”連接都轉(zhuǎn)移或額外空間，沒有空閑空間。

2.2 基于MCDM的頻譜碎片整理算法中指標(biāo)與權(quán)重設(shè)定

相關(guān)文獻(xiàn)和電信業(yè)務(wù)數(shù)據(jù)表明各個(gè)指標(biāo)在不同階段中起到的作用不同，同一指標(biāo)在不同的階段中可能是肯定指標(biāo)，也可能是否定指標(biāo)。例如連接的大小(Sx)這一指標(biāo)，表示連接x所需要的頻隙數(shù)量，在選擇最佳“消失”連接中，Sx是一個(gè)肯定指標(biāo)，因?yàn)楫?dāng)連接具有更多的頻隙時(shí)，它在轉(zhuǎn)移后釋放的頻隙也就更多；而在選擇最佳“左移”連接時(shí)，Sx是一個(gè)否定指標(biāo)，因?yàn)轭l隙數(shù)量少的連接比頻隙數(shù)量多的連接更容易得到匹配。因此，同樣的指標(biāo)在不同階段中具有不同的權(quán)重和作用。以選擇最佳“消失”連接為例，影響選擇“消失”連接的指標(biāo)有：

① 連接的大小(Sx)：連接x所需的頻隙數(shù)量?？隙ㄖ笜?biāo)，因?yàn)楫?dāng)連接具有更多頻隙時(shí)，它將在傳輸后釋放更多頻隙。

② 連接的數(shù)量(Lx)：連接x的連接數(shù)量。肯定指標(biāo)，因?yàn)檫B接的數(shù)量越多，則占用網(wǎng)絡(luò)中的空間就越多，轉(zhuǎn)移后釋放的空間就越多。

③ 連接受到的干擾數(shù)(Ix)：連接x受干擾的連接數(shù)。肯定指標(biāo)，因?yàn)楦蓴_連接會(huì)阻止其他連接移動(dòng)到更好的位置。干擾連接x的數(shù)量越多，傳輸該連接越好。

④ 剩余時(shí)間(Rx)：連接x的剩余時(shí)間。否定指標(biāo)，因?yàn)檫B接的剩余時(shí)間越短，該連接將會(huì)越快的被釋放，因此，剩余時(shí)間越長(zhǎng)的連接，占用頻隙的時(shí)間也就越長(zhǎng)，該連接便越值得被移動(dòng)。

⑤ 移動(dòng)后的總空閑時(shí)隙之和(Tx)：表示連接x的所有鏈路中所有相鄰空閑時(shí)隙(在連接之前和之后)的總和?？隙ㄖ笜?biāo)，因?yàn)閮蓚?cè)都具有較多自由空間的連接，可以在傳輸后釋放的整體性空間更多。

通過簡(jiǎn)單加性加權(quán)的方法對(duì)每個(gè)指標(biāo)的重要程度進(jìn)行確定(范圍為1～10)。

對(duì)這5個(gè)指標(biāo)進(jìn)行排序，在“消失”連接的轉(zhuǎn)移過程中，起決定性作用的是轉(zhuǎn)移后對(duì)網(wǎng)絡(luò)空間的影響，所以連接受到的干擾數(shù)(Ix)這一指標(biāo)最為重要，而移動(dòng)后的總空閑時(shí)隙之和(Tx)代表著移動(dòng)連接后網(wǎng)絡(luò)空出的頻隙數(shù)，雖然也體現(xiàn)了對(duì)網(wǎng)絡(luò)的影響，但是Ix的影響程度遠(yuǎn)大于Tx，因?yàn)橐苿?dòng)的連接受到的干擾數(shù)越多，代表著這個(gè)連接對(duì)網(wǎng)絡(luò)的影響程度越大，移動(dòng)后網(wǎng)絡(luò)的改善情況就越好。因此，為了凸顯其決定性的作用，筆者將連接受到的干擾數(shù)(Ix)的重要程度設(shè)置為10，本階段其他4個(gè)指標(biāo)的重要程度設(shè)置為：移動(dòng)后的總空閑時(shí)隙之和(Tx)為5；連接的大小(Sx)為4；連接的數(shù)量(Lx)和剩余時(shí)間(Rx)均為3(表示Lx和Rx重要程度相同)。最終選擇“消失”連接的指標(biāo)的重要程度表，如表1所示。

表1 選擇“消失”連接的指標(biāo)的重要程度表

然后利用層次分析法列出滿足一致性的矩陣，如表2所示。

表2 選擇“消失”連接的成對(duì)比較矩陣表

再規(guī)范表2，將表中的值除以總和，如表3所示。

表3 AHP法加權(quán)后的結(jié)果

最后通過求平均值，確定出篩選最佳“消失”的每個(gè)指標(biāo)的權(quán)重，如表4所示。

表4 選擇“消失”連接的指標(biāo)及權(quán)重

通過同樣的方法確定其他階段中應(yīng)選擇的最佳連接的指標(biāo)和權(quán)重。

選擇最佳“縮短”連接的指標(biāo)與權(quán)重：

① 連接差(Cx)：表示新路由和當(dāng)前連接路由的連接數(shù)量之間的差?？隙ㄖ笜?biāo)，因?yàn)槿绻B接可以移動(dòng)到連接數(shù)量較少的路線，將會(huì)釋放更多的頻隙。

② 連接的大小(Sx)：連接x所需的頻隙數(shù)量。否定指標(biāo)，因?yàn)橛捎陬l隙數(shù)量的限制，要找到一個(gè)需要頻隙較多的新連接比較困難。

③ 連接的數(shù)量(Lx)：連接x的連接數(shù)量。肯定指標(biāo)，因?yàn)檫B接的數(shù)量越多，則占用網(wǎng)絡(luò)中的空間就越多，轉(zhuǎn)移后釋放的空間就越多。

④ 連接受到的干擾數(shù)(Ix)：連接x干擾的連接數(shù)。肯定指標(biāo)，因?yàn)楦蓴_連接會(huì)阻止其他連接移動(dòng)到更好的位置。干擾連接x的數(shù)量越多，傳輸該連接越好。

⑤ 剩余時(shí)間(Rx)：連接x的剩余時(shí)間。肯定指標(biāo)，因?yàn)槭Ｓ鄷r(shí)間較少的連接將更快完成，并在鏈接上生成片段；但是剩余時(shí)間更多的連接將保留更多的時(shí)間，因此對(duì)其進(jìn)行縮短操作。

⑥ 移動(dòng)后的總空閑時(shí)隙之和(Tx)：表示連接x的所有鏈路中所有相鄰空閑時(shí)隙(在連接之前和之后)的總和。這是一個(gè)肯定的指標(biāo)，因?yàn)閮蓚?cè)都具有較多自由空間的連接，可以在傳輸后釋放的整體性空間更多。

選擇最佳“縮短”連接的指標(biāo)的重要程度如表5所示。權(quán)重的設(shè)定如表6所示。

表5 選擇最佳“縮短”連接的指標(biāo)的重要程度

表6 選擇最佳“縮短”連接的指標(biāo)與權(quán)重

選擇最佳“左移”連接的指標(biāo)與權(quán)重：

① 移動(dòng)后的總空閑時(shí)隙之和(Tx)：表示連接x的所有鏈路中所有相鄰空閑時(shí)隙(在連接之前和之后)的總和?？隙ㄖ笜?biāo)，因?yàn)閮蓚?cè)都具有較多自由空間的連接，可以在傳輸后釋放的整體性空間更多。

② 連接的大小(Sx)：連接x所需的頻隙數(shù)量。否定指標(biāo)，因?yàn)樾∵B接有更多機(jī)會(huì)找到比大地方更好的地方。

③ 剩余時(shí)間(Rx)：連接x的剩余時(shí)間。肯定指標(biāo)，因?yàn)槭Ｓ鄷r(shí)間較少的連接將更快完成，并在鏈接上生成片段；但是剩余時(shí)間更多的連接將保留更多的時(shí)間，因此對(duì)其進(jìn)行縮短操作。

④ 距離(Dx)：連接x與頻譜開始端的距離?？隙ㄖ笜?biāo)，越靠近頻譜的開始端，越容易被移動(dòng)。

⑤ 連接的數(shù)量(Lx)：連接x的鏈接數(shù)。否定指標(biāo)，因?yàn)殒溄訑?shù)較少的連接找到空閑頻隙的機(jī)會(huì)比鏈接數(shù)較多的連接大。

⑥ 移動(dòng)后碎片改善率(Fx)：新的Lx與現(xiàn)有Lx的差異。因?yàn)橐苿?dòng)一個(gè)連接可以降低其鏈接的碎片率，所以這是一個(gè)肯定指標(biāo)。

⑦ 連接受到的干擾數(shù)(Ix)：受連接x干擾的連接數(shù)?？隙ㄖ笜?biāo)，因?yàn)楦蓴_連接會(huì)阻止其他連接移動(dòng)到更好的位置。干擾越高，傳輸該連接越好。

⑧ 從起點(diǎn)開始的新距離(Nx)：連接點(diǎn)x的新位置距光譜起點(diǎn)的距離。否定指標(biāo)，因?yàn)楣P者的目標(biāo)是將占用的頻隙移到頻譜的開始端，將空閑頻隙移到頻譜的末尾端。因此，離頻譜開始端較近的位置比距離較遠(yuǎn)的位置更好。

選擇“左移”連接的指標(biāo)的重要程度如表7所示。權(quán)重的設(shè)定如表8所示。

表7 選擇“左移”連接的指標(biāo)的重要程度

表8 選擇“左移”連接的指標(biāo)與權(quán)重

因?yàn)橐苿?dòng)“右移”連接與“消失”連接都是以對(duì)網(wǎng)絡(luò)空間的影響大小為主，影響越大，移動(dòng)后頻譜的改善效果就越好，所以在指標(biāo)的選擇與權(quán)重的確定過程中移動(dòng)“右移”連接與移動(dòng)“消失”連接的指標(biāo)與權(quán)重相同。選擇“重路由”連接與“縮短”連接時(shí)，由于都采用的K-最短路徑算法，所以選擇“重路由”連接與“縮短”連接的指標(biāo)與權(quán)重相同。

3 仿真分析

3.1 仿真條件

為了評(píng)估算法的性能，采用美國(guó)國(guó)家科學(xué)基金會(huì)(National Science Foundation，NSF)的主干網(wǎng)絡(luò)進(jìn)行仿真，如圖9所示。該網(wǎng)絡(luò)擁有14個(gè)節(jié)點(diǎn)和21個(gè)鏈路，每個(gè)節(jié)點(diǎn)之間的距離以km為單位。每條鏈路上具有110個(gè)頻隙，其中10個(gè)作為額外頻隙，每個(gè)頻隙的大小為12.5 GHz。

圖9 NSF網(wǎng)絡(luò)拓?fù)鋱D

仿真方案：采用隨機(jī)接入一定數(shù)量的業(yè)務(wù)請(qǐng)求連接，每個(gè)業(yè)務(wù)連接大小在2～10個(gè)頻隙之間隨機(jī)產(chǎn)生，每個(gè)連接的保持時(shí)間為10 s，業(yè)務(wù)的源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)隨機(jī)生成，路由方法采用K-最短路徑法，其中K等于3。為了驗(yàn)證算法的有效性，筆者選取首次命中(K-Shortest Path with First Fit spectrum allocation，KSP-FF)算法[10]和推挽碎片整理算法(Push Pull，PP)[10]進(jìn)行比較。仿真過程中，設(shè)置“消失”連接的剩余時(shí)間閾值為10 s，對(duì)帶寬阻塞率、請(qǐng)求阻塞率和頻譜利用率進(jìn)行分析，其中帶寬阻塞率表示被阻塞的請(qǐng)求帶寬與總請(qǐng)求帶寬的比值，請(qǐng)求阻塞率表示被阻塞的連接數(shù)量與總請(qǐng)求的連接數(shù)量之比。

3.2 阻塞率分析

圖10為分別采用KSP-FF、PP和基于MCDM碎片整理算法下的網(wǎng)絡(luò)帶寬阻塞率。圖中，E為Erlang的縮寫，中文譯為“厄蘭“，話務(wù)量，意為”占線小時(shí)”。以下圖同。

圖11為基于KSP-FF和多準(zhǔn)則決策碎片整理算法的帶寬阻塞率改善對(duì)比圖。

圖10 帶寬阻塞率 圖11 帶寬阻塞率改善對(duì)比圖

從圖10可以明顯看，出當(dāng)業(yè)務(wù)連接較少時(shí)，3種算法的帶寬阻塞率差距不大，而隨著業(yè)務(wù)連接數(shù)量的增加帶寬阻塞率都呈現(xiàn)上升趨勢(shì)，而基于多準(zhǔn)則決策的算法優(yōu)于PP和KSP-FF，當(dāng)業(yè)務(wù)請(qǐng)求負(fù)載達(dá)到300 E即高負(fù)載時(shí)，基于多準(zhǔn)則決策的碎片整理算法帶寬阻塞率為36%，明顯低于PP和KSP-FF的帶寬阻塞率。同時(shí)，從圖11可以看出，當(dāng)連接數(shù)達(dá)到60時(shí)，首次命中算法的網(wǎng)絡(luò)開始出現(xiàn)阻塞情況，而基于多準(zhǔn)則決策的算法在業(yè)務(wù)連接數(shù)量達(dá)到100左右時(shí)，帶寬阻塞率才開始出現(xiàn)變化；此時(shí)基于多準(zhǔn)則決策的算法，相比首次命中的算法帶寬阻塞率改善最高可達(dá)20%；當(dāng)業(yè)務(wù)連接數(shù)量達(dá)到120左右時(shí)，可以看出，基于多準(zhǔn)則決策的算法整理后的帶寬阻塞率有所降低，當(dāng)達(dá)到140左右時(shí)發(fā)生突變；此時(shí)相比于首次命中算法，基于多準(zhǔn)則決策算法的帶寬利用率改善了約10%。隨著業(yè)務(wù)連接繼續(xù)增加，基于多準(zhǔn)則決策的頻譜碎片整理算法相比于首次命中算法帶寬阻塞率降低了約17%。

從上述分析可以得出，基于多準(zhǔn)則決策的頻譜整理算法可以有效降低網(wǎng)絡(luò)的帶寬阻塞率。

圖12 業(yè)務(wù)請(qǐng)求阻塞率

圖13 業(yè)務(wù)請(qǐng)求阻塞率改善圖

圖14 頻譜利用率

圖12和圖13為業(yè)務(wù)請(qǐng)求阻塞率仿真結(jié)果。從圖12可以看出隨著業(yè)務(wù)連接數(shù)量的增加，3種算法的網(wǎng)絡(luò)請(qǐng)求阻塞率呈現(xiàn)上升趨勢(shì)，而基于多準(zhǔn)則決策的算法的請(qǐng)求阻塞率小于KSP-FF和PP的阻塞率；從圖13可以看出，基于多準(zhǔn)則決策的算法在業(yè)務(wù)請(qǐng)求達(dá)到120時(shí)，才出現(xiàn)請(qǐng)求阻塞的情況，當(dāng)業(yè)務(wù)請(qǐng)求達(dá)到140時(shí)，基于多準(zhǔn)則決策的算法相對(duì)首次命中算法的請(qǐng)求阻塞率得到明顯改善，此時(shí)首次命中算法整理后的請(qǐng)求阻塞率為15%左右，基于多準(zhǔn)則決策的碎片整理算法整理后的請(qǐng)求阻塞率為10%左右。由以上分析可以得出，相對(duì)于其他兩種算法，基于多準(zhǔn)則決策的算法可以有效改善彈性光網(wǎng)絡(luò)的業(yè)務(wù)請(qǐng)求阻塞率。由于多準(zhǔn)則決策增加了判決機(jī)制，算法運(yùn)行時(shí)間大于KSP-FF和PP算法，但是基于多準(zhǔn)則決策在改善業(yè)務(wù)阻塞率方面有明顯的優(yōu)勢(shì)。

3.3 頻譜利用率分析

圖14為頻譜利用率仿真圖，可以看出整理后的頻譜利用率高于整理前的頻譜利用率。

隨著接入業(yè)務(wù)連接的增多，當(dāng)達(dá)到高流量負(fù)載(業(yè)務(wù)請(qǐng)求數(shù)量達(dá)到200 E)時(shí)，基于多準(zhǔn)則決策的頻譜利用率達(dá)45%；當(dāng)業(yè)務(wù)請(qǐng)求數(shù)量達(dá)到300 E時(shí)，基于多準(zhǔn)則決策的頻譜利用率高達(dá)65%；而基于KSP-FF在高負(fù)載下，頻譜利用率最高約達(dá)38%；因此基于多準(zhǔn)則決策的頻譜碎片整理算法相比于基于首次命中的頻譜碎片整理算法的頻譜利用率，得到了很大的改善。這表明，基于多準(zhǔn)則決策的頻譜碎片整理算法，在降低帶寬阻塞率和請(qǐng)求阻塞率的同時(shí)，提高了頻譜利用率，進(jìn)而提高了網(wǎng)絡(luò)資源的利用率。

4 總 結(jié)

針對(duì)當(dāng)前彈性光網(wǎng)絡(luò)中路由選擇與頻譜分配算法的頻譜碎片整理問題，基于多準(zhǔn)則決策，筆者提出了彈性光網(wǎng)絡(luò)中頻譜碎片的整理算法降低業(yè)務(wù)帶寬阻塞率。根據(jù)層次分析法確定了算法在運(yùn)行過程中不同指標(biāo)的權(quán)重，舉例說明了多準(zhǔn)則決策的適用性，并且理論分析和仿真結(jié)果表明，基于多準(zhǔn)則決策的頻譜碎片整理算法，可以有效地提高頻譜利用率并降低網(wǎng)絡(luò)的阻塞率。