基于多維幀頻譜感知的軍用光網(wǎng)絡(luò)資源分配算法

田相軒，石志強，劉娟，呂瑩

(陸軍裝甲兵學(xué)院，北京 100072)

軍用光網(wǎng)絡(luò)在民用光纖技術(shù)的帶動下有了長足的發(fā)展，不僅在通信容量上，而且在信息傳輸速率與業(yè)務(wù)種類上都有了迅速的增長。光網(wǎng)絡(luò)資源的有效調(diào)度成為制約提高部隊各固定作戰(zhàn)單元通信信道利用率/性能的重要制約因素。整個光網(wǎng)絡(luò)的帶寬是固定的。彈性光網(wǎng)絡(luò)具有高效頻譜資源利用率、動態(tài)適應(yīng)帶寬調(diào)整、靈活調(diào)度業(yè)務(wù)占用頻譜資源以及梳理業(yè)務(wù)傳輸速度與調(diào)制格式等優(yōu)勢，能高效地利用光網(wǎng)絡(luò)頻譜資源[1]。在彈性光網(wǎng)絡(luò)中，頻譜資源分配需滿足頻譜一致性原則和頻譜鄰接性原則，頻譜級的資源分配提高了頻譜利用率，但在細(xì)粒度的頻譜資源分配的策略下，頻譜碎片大量產(chǎn)生，增加了資源分配的復(fù)雜性，降低了資源的可用性[2-3]。

針對此類問題，目前主要有3種優(yōu)化策略，分別是碎片整理、光疏導(dǎo)和頻譜分割策略。碎片整理策略是指在業(yè)務(wù)請求資源已分配或業(yè)務(wù)請求被阻塞的情況下，通過釋放占用的頻隙，少占用新的頻隙實現(xiàn)光路連通，分兩種情況：第一種情況重新分配鏈路與頻譜資源，會打亂現(xiàn)有業(yè)務(wù)請求傳輸光路；第二種情況在光路繼續(xù)保持的狀態(tài)下進(jìn)行頻譜調(diào)整[4-6]。光疏導(dǎo)策略的目的是減少光轉(zhuǎn)發(fā)器的使用與頻譜保護(hù)帶的插入，提高頻譜資源的利用率，提出將業(yè)務(wù)請求占用帶寬最大的優(yōu)先分配，采用高于業(yè)務(wù)請求的調(diào)制等級等方法，缺少對網(wǎng)絡(luò)頻譜資源現(xiàn)有、實時狀態(tài)的考慮，不能實現(xiàn)對業(yè)務(wù)請求的合理分配[7-9]。頻譜分割方法(Split Spectrum Approach，SSA)在彈性光網(wǎng)絡(luò)中出現(xiàn)任務(wù)請求速率太高導(dǎo)致堵塞的情況，將任務(wù)請求分解成一組低速率的任務(wù)請求，綜合多種因素，包括占用的時隙數(shù)量以及調(diào)制的格式、資源分配帶來的新的頻譜碎片數(shù)量以及業(yè)務(wù)請求分割的數(shù)量，來確定路徑、頻隙和調(diào)制格式的選擇，能夠有效提高傳輸效率，減輕頻譜碎片化，降低數(shù)據(jù)阻塞率(Bit Blocking Rate，BBR)。SSA應(yīng)用在兩種場景：一是在光網(wǎng)絡(luò)鏈路中，沒有連續(xù)的頻譜來承擔(dān)所需要的帶寬；二是在傳輸調(diào)制或傳輸過程中出現(xiàn)信號損失，使任務(wù)請求的速率無法滿足[10-12]。

筆者采取頻譜分割的思路，基于頻譜的大小與任務(wù)請求對光網(wǎng)絡(luò)帶寬資源的實際需求情況，解決彈性光網(wǎng)絡(luò)中多任務(wù)請求資源調(diào)度的資源利用率低、頻譜碎片化程度高的問題，提出了基于多維幀頻譜感知的多任務(wù)請求資源分配算法(The Algorithm of the Multi-task Resource Scheduling Based on the Multi-dimensional Frame Matrix of the Cognitive Spectrum,MRSA-MFM)，當(dāng)多任務(wù)請求到達(dá)網(wǎng)絡(luò)時，根據(jù)網(wǎng)絡(luò)的實時資源占用和空閑狀態(tài)確定網(wǎng)絡(luò)資源多維幀矩陣，利用資源多維幀矩陣計算k條路徑的頻譜復(fù)用率，確定任務(wù)請求分裂度，選定最優(yōu)分配的頻譜，提高光網(wǎng)絡(luò)資源的可用性和延展性，最大程度的降低頻譜資源的碎片化。

1 模型設(shè)定

1.1 流量限制原則

業(yè)務(wù)請求的速率應(yīng)小于業(yè)務(wù)請求源節(jié)點調(diào)制解調(diào)器的調(diào)制速率之和。

(1)

式中：DP為任務(wù)請求分解的數(shù)量；m為源節(jié)點處調(diào)制解調(diào)器的數(shù)量；Q(y)為調(diào)制解調(diào)器速率；Qs為業(yè)務(wù)請求的速率，即業(yè)務(wù)請求的最大速率應(yīng)小于調(diào)制解調(diào)器的可調(diào)制最大速率，并且當(dāng)業(yè)務(wù)請求分解成DP個子請求，業(yè)務(wù)請求的速率與保護(hù)帶寬QG的和也應(yīng)小于調(diào)制解調(diào)器的可調(diào)制的最大速率。

1.2 頻譜一致性原則

頻譜一致性原則要求在任務(wù)請求的源節(jié)點到目的節(jié)點之間只能使用同一頻譜，即在光路第1段鏈路確定頻隙序列后，剩余的所有鏈路段必須使用相同的頻隙序列。

1.3 頻譜鄰接性原則

對一個業(yè)務(wù)請求或者一條光路的建立，在頻譜的分配中頻隙的使用必須是連續(xù)的、相鄰的。在業(yè)務(wù)請求的可用頻譜塊Bq,k，表示任務(wù)請求q的可用的連續(xù)空閑頻隙，即可用頻譜塊(Wass,Fs,wass,i,j)，頻譜塊的起始與終止節(jié)點分別為i,j，Wass是指所占用的波長，F(xiàn)s為時隙,wass為時隙的數(shù)量，其中：

j-i=wass.

(2)

1.4 頻譜沖突限制

頻譜沖突限制要求同一頻隙在同一光纖鏈路上只能被一個任務(wù)請求占用，因此同一光纖鏈路上傳輸?shù)膬尚盘柌荒芡瑫r占用同一頻隙。

2 具體算法

MRSA-MFM算法主要是基于多任務(wù)請求對光網(wǎng)絡(luò)資源的實際需求狀態(tài)，資源分配完畢后頻譜資源的碎片化程度，考慮任務(wù)請求的負(fù)載容量、路由跳數(shù)、頻譜完整度和任務(wù)分裂度這4個因素，評定對剩余資源分配的影響，從而提高資源的利用效率?；舅惴ㄖ饕譃闃?gòu)建網(wǎng)絡(luò)資源多維幀矩陣、業(yè)務(wù)請求分解策略和頻譜復(fù)用率計算3個部分，其中通過構(gòu)建多維幀矩陣，描述多任務(wù)請求的資源情況，從而構(gòu)建多任務(wù)請求的優(yōu)先級評定確定資源的分配順序，合理的資源分配順序能夠有效地利用網(wǎng)絡(luò)的寬度和資源的深度。其次，針對網(wǎng)絡(luò)資源的實際狀態(tài)，以及任務(wù)請求的資源需求情況，合理的確定任務(wù)請求分解方案，在滿足用戶需求的前提下，最大化提高帶寬利用率。

2.1 資源多維幀描述

多任務(wù)請求同時到達(dá)網(wǎng)絡(luò)時，根據(jù)業(yè)務(wù)請求光路建立所占用的光網(wǎng)絡(luò)資源的多少與光網(wǎng)絡(luò)的連通狀態(tài)確定鄰接矩陣；設(shè)置波長，確定資源狀態(tài)矩陣，實現(xiàn)資源從節(jié)點到波長的多維描述。

1)建立光網(wǎng)絡(luò)拓?fù)溧徑泳仃?/p>

(3)

式中：E為網(wǎng)絡(luò)拓?fù)溧徑泳仃?；V是指存在的節(jié)點數(shù)量；i,j為鏈路的某一個源節(jié)點和目的節(jié)點；Ei,j表示鏈路連通狀態(tài)，Ei,j=0表示鏈路Ei,j未連通，Ei,j=1表示鏈路Ei,j連通。

2)建立光網(wǎng)絡(luò)資源狀態(tài)矩陣

(4)

式中：Wi,j為鏈路Ei,j的資源狀態(tài)矩陣。式(4)基于式(3)建立，若兩節(jié)點之間有連接，構(gòu)建資源的非零表示參數(shù)Wi,j，否則為0；式(4)中矩陣的每個元素的展開項為

(5)

式中：m,n為光路鏈路中波長的數(shù)量與頻隙的數(shù)量；Wm,n為二元數(shù)，Wm,n=0表示光路鏈路中第m個虛擬波長的第n個頻隙空閑,Wm,n=1表示光路鏈路中第m個虛擬波長的第n個頻隙被占用。虛擬波長只是界定的一個頻率范圍與在這個頻率范圍上的頻隙，不再受限于波長一致性原則。

基于復(fù)雜網(wǎng)理論與圖論的基本原理，借鑒無線網(wǎng)絡(luò)中的連通度計算方法，假定拓?fù)渲械娜我夤?jié)點的優(yōu)先級相同，根據(jù)網(wǎng)絡(luò)節(jié)點之間的連通程度，設(shè)定光網(wǎng)絡(luò)拓?fù)涞倪B通度，在路由的層面上，對光網(wǎng)絡(luò)進(jìn)行定量的描述:

(6)

式中：j為拓?fù)渲械趈節(jié)點，作為中心節(jié)點；yj為第j節(jié)點作為中心節(jié)點時劃分子圖的數(shù)量；Vi為第i子圖的節(jié)點數(shù)量；li為第i子圖到中心節(jié)點的平均連通距離。

在光網(wǎng)絡(luò)連通度較高的狀態(tài)下(連通度Crate=1)，即任意兩節(jié)點之間都能互連，則路由的長短對光路的建立影響較小，業(yè)務(wù)請求的速率對光路的影響較大；反之，當(dāng)網(wǎng)絡(luò)的連通度較低的狀態(tài)下，業(yè)務(wù)請求路由的長度，對光路的建立影響較大，任務(wù)請求速率對光路建立的影響降低。設(shè)定優(yōu)先等級計算如式(7)所示，式中多條路徑的選取通過最短路徑算法獲得：

(7)

式中，hq,k表示任務(wù)請求q相對應(yīng)可用路徑的跳數(shù)。為降低計算復(fù)雜度，設(shè)定k=5(經(jīng)仿真分析，若分裂次數(shù)大于5，復(fù)雜度急劇上升)。

2.2 業(yè)務(wù)分割與頻譜分配策略

提出頻譜復(fù)用率的度量參數(shù)，創(chuàng)新性地利用資源的多維幀矩陣判定資源的有效使用情況，通過業(yè)務(wù)請求的資源與目前網(wǎng)絡(luò)資源的空閑情況計算，獲取網(wǎng)絡(luò)資源利用率最大且頻譜碎片化程度較低的頻譜分配方案，提高頻譜資源利用率，減少頻譜碎片化。

根據(jù)頻譜沖突限制原則、頻譜鄰接原則、頻譜一致性原則，與優(yōu)先級設(shè)定策略中的k條路徑備用路由算法獲得業(yè)務(wù)請求的需求資源矩陣：

(8)

式中：Qx,y為業(yè)務(wù)請求所需求的資源狀態(tài)矩陣；x,y為業(yè)務(wù)請求的起始節(jié)點與目的節(jié)點；Wm,n表示業(yè)務(wù)請求需要光路鏈路中第m個波長的第n個頻隙空閑，不需要的頻隙在Qx,y中設(shè)定為1.與鏈路資源狀態(tài)矩陣求交集可得業(yè)務(wù)請求光路的可用資源狀態(tài)矩陣：

(9)

(10)

(11)

根據(jù)算法中的分解次數(shù)限制，滿足式(11)的情況下，以頻隙為最小單位進(jìn)行業(yè)務(wù)分割，基于子業(yè)務(wù)請求頻譜復(fù)用率的和最小的方案進(jìn)行業(yè)務(wù)請求分解，獲得子業(yè)務(wù)請求，分解之后的子業(yè)務(wù)請求作為獨立請求處理。

2.3 算法描述

輸入為網(wǎng)絡(luò)資源狀態(tài)矩陣與多任務(wù)請求集合；輸出為任務(wù)請求的頻譜資源分配方案，多維幀頻譜感知的多任務(wù)請求資源分配算法(MRSA-MFM)流程如圖1所示。

步驟1構(gòu)建網(wǎng)絡(luò)拓?fù)溧徑泳仃?、網(wǎng)絡(luò)資源多維幀矩陣，為路由計算與頻譜分配做準(zhǔn)備。

步驟2對服務(wù)等級相同的任務(wù)請求，根據(jù)優(yōu)先級設(shè)定策略，確定資源分配順序。

步驟3按照優(yōu)先級順序，對業(yè)務(wù)請求進(jìn)行初步篩選，設(shè)定業(yè)務(wù)請求的初始分裂次數(shù)DP=0.

步驟4業(yè)務(wù)請求速率小于起始節(jié)點調(diào)制解調(diào)器速率的直接到步驟6.

步驟5業(yè)務(wù)請求速率大于起始節(jié)點調(diào)制解調(diào)器速率或由步驟6導(dǎo)出的請求進(jìn)行業(yè)務(wù)請求分解，并對該業(yè)務(wù)請求的分裂次數(shù)DP的值加1.

步驟7當(dāng)光網(wǎng)絡(luò)為業(yè)務(wù)請求Qx,y第k條路由可提供的頻譜資源狀態(tài)矩陣滿足業(yè)務(wù)請求的帶寬需求時，計算該條路由頻譜資源分配后的頻譜復(fù)用率，否則，不予進(jìn)行計算。根據(jù)業(yè)務(wù)請求的頻譜復(fù)用率，從待選的可用頻譜塊中選取頻譜復(fù)用率最高的確定為業(yè)務(wù)請求可分配頻譜；當(dāng)業(yè)務(wù)請求無可用頻譜資源時，核查業(yè)務(wù)請求的分裂次數(shù)，若DP≤2，將該業(yè)務(wù)請求轉(zhuǎn)到步驟5，否則設(shè)定該任務(wù)請求拒絕。

步驟8待資源分配結(jié)束，實時更新資源空閑矩陣，更新業(yè)務(wù)請求的頻譜復(fù)用率。

3 仿真驗證

為驗證本文提出算法的有效性，在NSFNET(14個節(jié)點，21條雙向光纖鏈路)上進(jìn)行驗證，通過Matlab軟件仿真的方式，采用對比驗證的方式進(jìn)行驗證，相對比算法為NRSMLA和SSRSMLA[12]。假設(shè)每個光纖鏈路上有200個頻隙，頻隙帶寬為10 GHz，保護(hù)帶寬為5 GHz.調(diào)制解調(diào)器的速率分別為25，50，75，100，150，200 Gbit/s.隨機產(chǎn)生任務(wù)請求，任務(wù)請求的大小為{10,20,30,40,50,60,70,80,90,100}Gbit/s，產(chǎn)生的過程服從泊松分布。假定隨機生成7組任務(wù)請求分別為{150,175,200,225,250,275,300}，在給定的光網(wǎng)絡(luò)資源頻譜下，任務(wù)請求數(shù)量較多。

網(wǎng)絡(luò)負(fù)載重，分別調(diào)用NRSMLA、SSRSMLA算法與本文提出的MRSA-MFM算法進(jìn)行頻譜資源的分配，分配結(jié)果如圖2所示。從圖2中可看到，MRSA-MFM算法在不同負(fù)載的情況下能降低任務(wù)請求建立光路的阻塞率。隨著任務(wù)請求數(shù)量的增大，網(wǎng)絡(luò)負(fù)載加大，基于網(wǎng)絡(luò)實時動態(tài)的頻譜資源的優(yōu)先級分配實現(xiàn)了任務(wù)請求的梳理，基于頻譜復(fù)用率與業(yè)務(wù)分裂的頻譜資源分配實現(xiàn)了資源使用的最大化，降低了頻譜碎片，使得筆者提出的算法優(yōu)勢逐漸明顯；從圖2可得，當(dāng)任務(wù)請求數(shù)量達(dá)到250條左右時，本文算法的優(yōu)勢逐漸顯現(xiàn)，到任務(wù)請求數(shù)量達(dá)到300條時，相比SSRSMLA算法性能提升3.1%，相比首次命中法的NRSMLA算法性能提升6.1%.

業(yè)務(wù)請求的分解次數(shù)的平均值的變化趨勢，隨著任務(wù)請求數(shù)量的增大，業(yè)務(wù)請求分解的次數(shù)逐漸達(dá)到飽和值，業(yè)務(wù)請求的分裂對光路建立的貢獻(xiàn)達(dá)到飽和，業(yè)務(wù)請求的阻塞率不斷增加，如圖3所示。隨著網(wǎng)絡(luò)負(fù)載的不斷增大，通過業(yè)務(wù)請求的分裂實現(xiàn)了頻譜碎片的有效利用，隨著業(yè)務(wù)請求分裂次數(shù)的增加也導(dǎo)致了光路傳輸?shù)难訒r的增加，業(yè)務(wù)請求占用光路的時間延長，另一角度出發(fā)業(yè)務(wù)請求耗費的光路資源增加，降低了后續(xù)業(yè)務(wù)請求建立光路的可能性。

隨著任務(wù)請求建立光路數(shù)量的增多，3種算法的復(fù)雜度逐漸上升，延時不斷增大，如圖4所示。

從圖4可以看出，本文算法的延時均小于文獻(xiàn)中提到的兩種算法。因為算法引入了頻譜復(fù)用率的核算與優(yōu)先級的設(shè)定，雖增加了算法復(fù)雜度，但延時的表現(xiàn)仍然保持在合理的范圍。

4 結(jié)束語

筆者針對復(fù)雜網(wǎng)絡(luò)多任務(wù)請求的頻譜資源分配問題提出了基于多維幀頻譜感知的多任務(wù)請求資源分配算法，算法按照資源多維幀矩陣描述，頻譜復(fù)用率與任務(wù)分解定位頻譜的方法實現(xiàn)資源的高效分配，降低頻譜碎片化，提高資源的可用性。本文的核心在于利用資源的多維幀矩陣描述的方法計算了頻譜復(fù)用率，結(jié)合網(wǎng)絡(luò)狀態(tài)確定了資源分配優(yōu)先級與頻譜分配定位策略，實現(xiàn)了業(yè)務(wù)請求的梳理，網(wǎng)絡(luò)資源的高效利用，降低了頻譜的碎片化，對基于頻譜粒度的光網(wǎng)絡(luò)資源分配具有參考性，為提高網(wǎng)絡(luò)資源的利用率提供了參考方案。