基于QoE的彈性光網(wǎng)絡(luò)頻譜分配優(yōu)化方法

楊其欽,劉壽強(qiáng)

(1. 廣州應(yīng)用科技學(xué)院計(jì)算機(jī)學(xué)院,廣東 廣州 511300;2. 華南師范大學(xué)人工智能學(xué)院,廣東 廣州 510631

1 引言

隨著信息化的不斷進(jìn)步,光通信技術(shù)以極快的速度發(fā)展[1-2],并被視為光傳輸網(wǎng)絡(luò)中的主流[3]。相比于傳統(tǒng)的WDM網(wǎng)絡(luò),彈性光網(wǎng)絡(luò)具有靈活分配頻譜資源和有效利用光纖寬帶等優(yōu)勢,可以大幅度提高頻譜資源的利用率。然而隨著物聯(lián)網(wǎng)和其他大帶寬應(yīng)用以及用戶對網(wǎng)絡(luò)傳輸提出的更高要求,造成網(wǎng)絡(luò)頻譜資源短缺,用戶請求直接被拒絕,從而影響了用戶體驗(yàn)[4]。因此需要對光網(wǎng)絡(luò)頻譜進(jìn)行分配,在分配過程中遵循頻譜的連續(xù)性和一致性兩個(gè)基本約束條件,但由于連接請求的建立與刪除,導(dǎo)致頻譜資源碎片化,使頻譜不連續(xù),為了解決頻譜資源浪費(fèi)問題,大量文獻(xiàn)針對頻譜分配優(yōu)化進(jìn)行了研究。

文獻(xiàn)[5]建立了一種混合整數(shù)線性模型,考慮到業(yè)務(wù)差異化和DS技術(shù),設(shè)計(jì)了基于DS和自適應(yīng)相結(jié)合的動態(tài)RSA算法,采用DS損失函數(shù)和窗口選擇策略對頻譜的位置和資源進(jìn)行合理分配,并通過網(wǎng)絡(luò)收益函數(shù)提高頻譜的收益,該方法可以大幅度降低光網(wǎng)絡(luò)業(yè)務(wù)的阻塞率。文獻(xiàn)[6]從路由選擇和頻譜分配兩方面進(jìn)行考慮,采用KSP算法求出源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑長度,按照頻譜資源數(shù)量,對路徑進(jìn)行分配,該方法能夠提高頻譜資源的利用率。文獻(xiàn)[7]對最小化降級頻次、等級和傳輸時(shí)間損失進(jìn)行綜合考慮,建立混合整數(shù)線性化模型,在最優(yōu)DS串口中引入降級恢復(fù)方法,在恢復(fù)光網(wǎng)絡(luò)空閑頻域的同時(shí),確保網(wǎng)絡(luò)最大化收益,該方法可以提高降級業(yè)務(wù)的成功率。

基于以上研究,本文考慮用戶不同的QoE需求,設(shè)計(jì)了基于QoE的彈性光網(wǎng)絡(luò)頻譜分配優(yōu)化方法。當(dāng)光網(wǎng)絡(luò)中存在多任務(wù)請求時(shí),依據(jù)網(wǎng)絡(luò)的資源使用情況和空閑狀態(tài)確定出多維幀矩陣,并結(jié)合網(wǎng)絡(luò)資源多維幀矩陣計(jì)算出頻譜的復(fù)用率,選擇出最優(yōu)的頻譜。并結(jié)合啟發(fā)式算法選擇出頻譜資源最少以及占用時(shí)隙總量最小的分配方法。

2 模型的建立

基于用戶QoE請求對網(wǎng)絡(luò)資源的實(shí)際情況進(jìn)行分配,在網(wǎng)絡(luò)資源分配過程中遵循4個(gè)原則,分別如下:

1)流量限制原則:用戶業(yè)務(wù)請求速率不得高于業(yè)務(wù)請求源節(jié)點(diǎn)中調(diào)制解調(diào)器的總速率,公式表示為

(1)

其中,x表示請求的任務(wù);n表示任務(wù)請求分解個(gè)數(shù);Vreq表示業(yè)務(wù)請求速率;Vpro表示保護(hù)帶寬速率;V(y)表示調(diào)制解調(diào)器的速率;m表示源節(jié)點(diǎn)中調(diào)制解調(diào)器的個(gè)數(shù)。

2)頻譜一致性原則:用戶業(yè)務(wù)請求任務(wù)過程中,源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間必須用同一個(gè)頻譜。

3)頻譜鄰接性原則:在頻譜分配中,一個(gè)用戶業(yè)務(wù)請求的頻隙必須是連續(xù)且鄰接的,光網(wǎng)絡(luò)的時(shí)隙數(shù)量可表示為

atime=bend-bstart

(2)

其中,bend表示頻譜塊的終止節(jié)點(diǎn);bstart表示頻譜塊的起始節(jié)點(diǎn)。

4)頻譜沖突限制性原則:在同一個(gè)光纖鏈路上的同一頻隙只能處理一個(gè)任務(wù)請求。

基于以上原則,本文構(gòu)建資源多維幀矩陣和頻譜分配策略,在滿足任務(wù)請求和用戶需求的前提下,提高彈性光網(wǎng)絡(luò)的利用率。

2.1 資源多維幀矩陣的建立

當(dāng)用戶的多個(gè)任務(wù)請求同時(shí)抵達(dá)網(wǎng)絡(luò)時(shí),按照用戶請求光路建立由網(wǎng)絡(luò)資源和光網(wǎng)絡(luò)同時(shí)確定的鄰接矩陣。通過設(shè)置波長、建立資源狀態(tài),實(shí)現(xiàn)對多維幀矩陣的描述,光網(wǎng)絡(luò)拓?fù)溧徑泳仃嚳杀硎緸?/p>

(3)

其中,c表示網(wǎng)絡(luò)中當(dāng)前的節(jié)點(diǎn)數(shù)量;i表示鏈路中某個(gè)源節(jié)點(diǎn);j表示鏈路中某個(gè)目的節(jié)點(diǎn);A(i,j)表示鏈路聯(lián)通狀態(tài)。光網(wǎng)絡(luò)資源狀態(tài)矩陣可表示為

(4)

其中,Bi,j表示鏈路A(i,j)的光網(wǎng)絡(luò)資源狀態(tài)矩陣。Bi,j矩陣中每個(gè)元素可表示為

(5)

其中,m表示光網(wǎng)絡(luò)鏈路波長個(gè)數(shù);n表示光網(wǎng)絡(luò)鏈路頻隙的個(gè)數(shù)。以復(fù)雜網(wǎng)絡(luò)理論和圖論為基礎(chǔ),結(jié)合無線網(wǎng)絡(luò)連通度的計(jì)算方式。假設(shè)光網(wǎng)絡(luò)拓?fù)渲懈鱾€(gè)節(jié)點(diǎn)具有相同的優(yōu)先級,按照網(wǎng)絡(luò)節(jié)點(diǎn)連通程度,描述路由層面的光網(wǎng)絡(luò),公式表示為

(6)

其中,j表示光網(wǎng)絡(luò)拓?fù)渲械牡趈個(gè)中心節(jié)點(diǎn);xi表示子圖的劃分個(gè)數(shù);ci表示第i個(gè)子圖的節(jié)點(diǎn)個(gè)數(shù);di表示第i個(gè)子圖到第j個(gè)中心節(jié)點(diǎn)的平均連通距離。若光網(wǎng)絡(luò)連通度較高的情況下,用戶業(yè)務(wù)請求的速率對光路影響相對于路由長短較大;若光網(wǎng)絡(luò)連通度較低的情況下,用戶業(yè)務(wù)請求的路由長度對光路影響相對于業(yè)務(wù)請求速率較大,因此設(shè)定優(yōu)先級,采用最短路徑計(jì)算方法對多條路徑進(jìn)行選擇,優(yōu)先等級可表示為

(7)

其中,fe,k表示光網(wǎng)絡(luò)中業(yè)務(wù)請求e對應(yīng)的路徑個(gè)數(shù)。

2.2 頻譜分配策略

為了利用多維幀矩陣對頻譜資源進(jìn)行有效判斷,提出頻譜復(fù)用率,并通過用戶業(yè)務(wù)請求與網(wǎng)絡(luò)資源空閑狀態(tài)使光網(wǎng)絡(luò)資源利用率最大化,頻譜碎片程度最低化。依據(jù)優(yōu)先等級的設(shè)定,用戶業(yè)務(wù)請求資源矩陣可表示為

(8)

其中,x是用戶業(yè)務(wù)請求的起始節(jié)點(diǎn);y表示用戶業(yè)務(wù)請求的目的節(jié)點(diǎn);B(m,n)表示光網(wǎng)絡(luò)鏈路中第m個(gè)波長對應(yīng)的第n個(gè)空閑的頻隙。與資源狀態(tài)矩陣進(jìn)行交集處理后,可以求出光網(wǎng)絡(luò)中可用的資源狀態(tài)矩陣

(9)

其中,Ex,y表示光網(wǎng)絡(luò)業(yè)務(wù)請求。光網(wǎng)絡(luò)頻譜資源的復(fù)用率公式表示為

(10)

3 頻譜分配的優(yōu)化

通過以上方法建立的模型,在光網(wǎng)絡(luò)規(guī)模較大時(shí),求解難度相對較高,無法滿足用戶QoE需求,因此提出啟發(fā)式算法對頻譜分配進(jìn)行優(yōu)化。本文將啟發(fā)式算法分為三個(gè)分配階段:單路徑單業(yè)務(wù)、單路徑多業(yè)務(wù)和多路徑多業(yè)務(wù),為了能夠節(jié)約頻譜資源,在頻譜優(yōu)化時(shí),先嘗試第一個(gè)分配階段,若失敗再進(jìn)入第二、三個(gè)階段。

3.1 單-單分配方式

為了滿足用戶QoE請求,根據(jù)光網(wǎng)絡(luò)中源節(jié)點(diǎn)和目的節(jié)點(diǎn)選擇出備選路徑,該過程需要保證請求具有最低頻隙開銷,全部頻隙開銷的計(jì)算方式為

(11)

其中,Bnet表示光網(wǎng)絡(luò)中頻隙的帶寬;vtran表示業(yè)務(wù)傳輸速率。根據(jù)每條備選路徑的頻譜使用情況,構(gòu)建可以確定光網(wǎng)絡(luò)路徑中連續(xù)空閑頻隙的矩陣,構(gòu)造的矩陣表示為

(12)

其中,lω,τ表示鏈路。通過現(xiàn)有全部路徑,求解各種情況下QoE的可能頻隙數(shù)量和頻隙總數(shù)量,分別表示為

(13)

其中,pr表示任意兩節(jié)點(diǎn)中距離最短的r條路徑。若當(dāng)前路徑?jīng)]有可分配方式,那么對下一條路徑進(jìn)行處理;若所有路徑均不可分配,那么進(jìn)入單路徑多業(yè)務(wù)的分配方式。根據(jù)每種分配方式下使用時(shí)隙總量,選擇最小路徑與用戶業(yè)務(wù)進(jìn)行連接。時(shí)隙總量用公式可表示為

(14)

其中,tstar,QoEi和tend,QoEi分別表示實(shí)際分配時(shí)起始和結(jié)束的時(shí)隙。

3.2 單-多分配方式

如果業(yè)務(wù)在第一階段的所有路徑均不能分配,那么將QoE請求分割成多個(gè)業(yè)務(wù),業(yè)務(wù)分割方式可表示為

RQoE＿i=r1·φ1+r2·φ2+r3·φ3

(15)

其中,r1、r2和r3分別為被分割業(yè)務(wù)的傳輸速率;φ1、φ2和φ3分別為整數(shù)系數(shù)。在處理過程中,將φ1作為參照,采取降序處理,當(dāng)具有相同φ1的情況下,再將φ2作為參照,同理進(jìn)行下去,直至完成全部排列。

在單路徑多業(yè)務(wù)分配方式中,對備選路徑中被分割業(yè)務(wù)的處理按照累計(jì)頻隙的方法進(jìn)行。在發(fā)現(xiàn)所在路徑不可分配時(shí),將分配目標(biāo)轉(zhuǎn)移至其余路徑。在QoE的路徑全部失效時(shí),則采取多路徑多業(yè)務(wù)分配方式。對于可以建立連接的路徑,需要按照頻隙總量最小的路徑分配方式建立業(yè)務(wù)連接,所有業(yè)務(wù)分配路徑使用的頻隙總量用公式可表示為

(16)

當(dāng)發(fā)現(xiàn)兩種方法具有一致的累計(jì)頻隙開銷時(shí),就要對著兩種方法光網(wǎng)絡(luò)實(shí)際使用的累計(jì)時(shí)隙開銷采取進(jìn)一步求解,公式表示為

(17)

選擇光網(wǎng)絡(luò)實(shí)際使用時(shí)隙最小路徑,以此來構(gòu)造業(yè)務(wù)鏈路。此過程中,當(dāng)出現(xiàn)若干種分配方案時(shí),采取完成頻隙最少的編號來構(gòu)造業(yè)務(wù)鏈路。

3.3 多-多分配方式

通過切割操作得到m個(gè)業(yè)務(wù)之后,再將候選路徑的前m個(gè)路徑進(jìn)行排序,排序集合表示為

seq=〈p1,p2,…,pm〉

(18)

分別嘗試在不同排序方式下將QoE請求映射至候選路徑,采用單-單方式完成全部業(yè)務(wù)的鏈路構(gòu)造,求解出各個(gè)業(yè)務(wù)的最優(yōu)分配方式和當(dāng)前路徑使用的頻隙總量。若QoE請求的沒有完成當(dāng)前路徑的映射,則更換其它序列繼續(xù)驗(yàn)證,直到全部路徑均無法分配,那么阻斷請求。對于全部可行分配方式,需要進(jìn)一步計(jì)算出業(yè)務(wù)處于不同路徑時(shí)使用的頻隙總量

(19)

選擇頻隙總量最小的分配方式建立路徑連接,并對頻譜使用矩陣進(jìn)行更新。

4 仿真實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文方法的有效性,選擇節(jié)點(diǎn)個(gè)數(shù)為15,光鏈路為25條的光網(wǎng)絡(luò),在Matlab仿真平臺上進(jìn)行驗(yàn)證。

假設(shè)光網(wǎng)絡(luò)鏈路上有300個(gè)頻隙,且?guī)挒?0GHz,任務(wù)請求隨機(jī)產(chǎn)生,當(dāng)光網(wǎng)絡(luò)有負(fù)載時(shí),對頻譜資源分配情況進(jìn)行仿真測試,并將MPFA算法和HTBalancing算法與本文算法進(jìn)行頻譜資源分配情況的實(shí)驗(yàn)對比,如圖1所示。

圖1 多任務(wù)請求下的光路阻塞情況

從圖中可以看出,隨著業(yè)務(wù)請求與網(wǎng)絡(luò)負(fù)載的增加,本文算法能夠在不同負(fù)載情況下降低任務(wù)請求的阻塞率,并基于頻譜資源優(yōu)先級和復(fù)用率的設(shè)計(jì),能夠使頻譜資源最大化,大大降低了頻譜的碎片化程度。當(dāng)業(yè)務(wù)請求為200條時(shí),本文方法的優(yōu)勢明顯好于其他兩種方法。而且當(dāng)業(yè)務(wù)請求達(dá)到250條左右時(shí),本文方法相對于MPFA算法和HTBalancing算法性能分別提高4.0%和7.0%左右。

為了進(jìn)一步驗(yàn)證本文算法對頻譜的利用情況,分別將MPFA算法和HTBalancing算法與本文算法進(jìn)行頻譜利用率的實(shí)驗(yàn)對比,在不同拓?fù)浣Y(jié)構(gòu)下對比結(jié)果如圖2所示。

圖2 不同算法頻譜利用率對比

從圖中可以看出,隨著網(wǎng)絡(luò)負(fù)載的不斷增加,由于業(yè)務(wù)連接所使用的頻隙數(shù)量越來越多,使三種算法的頻譜利用率呈現(xiàn)出上升趨勢,并且無論在哪種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下采用本文算法的頻譜利用率均為最高。其主要原因是HTBalancing算法只對業(yè)務(wù)間持續(xù)的時(shí)間差進(jìn)行了分析,并沒有考慮頻譜的碎片化,因此隨著負(fù)載的不斷增加,頻域和時(shí)域均產(chǎn)生了零碎的頻譜資源,導(dǎo)致頻譜利用率較低。MPFA算法綜合考慮了頻譜碎片化和多業(yè)務(wù)情況,通過MPR提高了頻譜的利用率。而本文在建立業(yè)務(wù)鏈路過程中,充分考慮了頻譜消耗與帶寬安全,盡可能保證分配性能,極大程度上提高頻譜的利用率。

5 結(jié)束語

針對光網(wǎng)絡(luò)的頻譜資源分配和用戶QoE需求問題,提出基于QoE的彈性網(wǎng)絡(luò)頻譜分配優(yōu)化方法。通過對多維幀矩陣的描述以及頻譜復(fù)用率方法實(shí)現(xiàn)光網(wǎng)絡(luò)資源的分配,降低頻譜碎片化程度。結(jié)合資源分配優(yōu)先級對業(yè)務(wù)請求進(jìn)行梳理,提高資源的利用率。為了對頻譜資源進(jìn)行優(yōu)化,分別從單-單、單-多和多-多進(jìn)行優(yōu)化設(shè)計(jì)。根據(jù)頻譜與時(shí)隙的消耗情況,完成請求連接。通過Matlab仿真平臺,將MPFA算法和HTBalancing算法與本文算法進(jìn)行對比驗(yàn)證,實(shí)驗(yàn)結(jié)果表明不同負(fù)載情況下采用本文方法可以極大程度地降低任務(wù)請求的阻塞率,使頻譜資源的利用率大幅度提高。