新穎的WDM EPON動(dòng)態(tài)帶寬調(diào)度算法

汪學(xué)舜，余少華,，戴錦友

（1.華中科技大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢 430074；2. 武漢郵電科學(xué)研究院 新一代光纖通信技術(shù)和網(wǎng)絡(luò)國家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074）

1 引言

高速 Internet接入網(wǎng)中，以太網(wǎng)無源光網(wǎng)絡(luò)(EPON)成為新出現(xiàn)的有吸引力的方法，在EPON初始階段，光線路終端OLT(optical line terminal)到光網(wǎng)絡(luò)單元 ONU(optical network unit)的下行流和上行流分別采用一個(gè)單波長(zhǎng)[1]，然而，隨著帶寬需求的增長(zhǎng)和傳輸質(zhì)量保證要求更高，在每一個(gè)方向采用多波長(zhǎng)傳輸?shù)牟ǚ謴?fù)用(WDM)技術(shù)得到越來越多的研究[2]。

WDM EPON的網(wǎng)絡(luò)結(jié)構(gòu)與傳統(tǒng)的EPON結(jié)構(gòu)類似[3]，由一個(gè)OLT、N個(gè)ONU以及一個(gè)1:N無源光纖分路器組成的樹形拓?fù)浣Y(jié)構(gòu)。OLT發(fā)送數(shù)據(jù)幀，通過光纖分路器，發(fā)送到ONU的數(shù)據(jù)傳輸，稱為下行傳輸；反之，由ONU發(fā)送到OLT的數(shù)據(jù)傳輸，稱為上行傳輸。在WDM EPON系統(tǒng)中，為了保證上行傳輸?shù)囊蕴珨?shù)據(jù)幀不發(fā)生碰撞，IEEE 802.3ah工作組提出了多點(diǎn)控制協(xié)議(MPCP)，MPCP定義2種類型控制消息，REPORT和GATE消息[4]，REPORT消息用于ONU向OLT通告自己需要傳輸?shù)臄?shù)據(jù)量，OLT收到ONU的REPORT消息之后，通過動(dòng)態(tài)帶寬分配計(jì)算(DBA)發(fā)送GATE消息，向ONU通告下一周期授權(quán)的傳輸數(shù)據(jù)量。為了區(qū)分WDM EPON系統(tǒng)中上行和下行波長(zhǎng)，McGarry等人對(duì)傳統(tǒng)的MPCP協(xié)議進(jìn)行了擴(kuò)展。

WDM EPON中的動(dòng)態(tài)帶寬分配由授權(quán)調(diào)度和授權(quán)帶寬組成。在文獻(xiàn)[5]中研究了各種授權(quán)帶寬技術(shù)，本文采用基于門限的授權(quán)帶寬技術(shù)，重點(diǎn)對(duì)WDM EPON動(dòng)態(tài)帶寬分配的授權(quán)調(diào)度進(jìn)行研究。OLT收到ONU的報(bào)告消息之后，立即進(jìn)行授權(quán)的在線調(diào)度機(jī)制，由于公平性較差，對(duì)多波長(zhǎng)傳輸，效率較低。OLT收到所有或部分ONU的報(bào)告消息之后，進(jìn)行統(tǒng)一帶寬分配的離線調(diào)度，是主要的調(diào)度方式。本文針對(duì)離線調(diào)度機(jī)制，采用調(diào)度理論方法解決授權(quán)調(diào)度問題，將授權(quán)調(diào)度和波長(zhǎng)分配結(jié)合，形式化為矩形Packing問題，由于矩形Packing問題是一個(gè)NP難問題，采用啟發(fā)式的近似算法可有效解決調(diào)度問題。

本文組織結(jié)構(gòu)如下：第2節(jié)對(duì)WDM EPON的調(diào)度策略相關(guān)研究進(jìn)行回顧；第3節(jié)對(duì)WDM EPON中ONU授權(quán)調(diào)度問題進(jìn)行模型化，并說明帶寬分配策略；第4節(jié)提出了多波長(zhǎng)高效用帶寬分配算法解決帶寬授權(quán)調(diào)度問題；第5節(jié)對(duì)算法的計(jì)算復(fù)雜性進(jìn)行分析；第6節(jié)對(duì)不同的調(diào)度技術(shù)進(jìn)行模擬實(shí)驗(yàn)，并進(jìn)行分析和比較；第7節(jié)為結(jié)束語。

2 相關(guān)研究

WDM EPON網(wǎng)絡(luò)中的波長(zhǎng)和帶寬動(dòng)態(tài)分配可分為2個(gè)部分：授權(quán)大小和授權(quán)調(diào)度[6]，每一個(gè)ONU可分配的帶寬大小取決于授權(quán)大小(即帶寬分配)，過去幾年，有很多高效的算法，值得注意的是：?jiǎn)涡诺?EPON提出的自適應(yīng)周期交叉輪循機(jī)制(IPACT)，已經(jīng)擴(kuò)展到WDM EPON網(wǎng)絡(luò)中，在文獻(xiàn)[7]中，Kwong等人提出多個(gè)上行波長(zhǎng)的IPACT方式，稱之為WDM IPACT-ST，其中ST表示單個(gè)輪循表。該算法對(duì)所有上行波長(zhǎng)的可用時(shí)間進(jìn)行跟蹤，一旦收到ONU的報(bào)告消息，OLT將第一個(gè)可用波長(zhǎng)的帶寬或傳輸窗口分配給ONU，同時(shí)假定每一個(gè)ONU支持所有的波長(zhǎng)。文獻(xiàn)[8]提出了一種類似于WDM IPACT的調(diào)度，選擇下一個(gè)ONU可用波長(zhǎng)進(jìn)行調(diào)度，而WDM IPACT-ST不支持這種適應(yīng)性。

Dhaini等人在文獻(xiàn)[9]中對(duì)基本的WDM PON結(jié)構(gòu)中動(dòng)態(tài)波長(zhǎng)和帶寬分配(DWBA)算法進(jìn)行了研究，提出了以下 3種可變動(dòng)態(tài)波長(zhǎng)和時(shí)間的帶寬分配。1) DWBA-1在一個(gè)周期內(nèi)，所有報(bào)告消息收到之后進(jìn)行調(diào)度，DWBA-1對(duì)過量帶寬進(jìn)行公平分配。2)DWBA-2對(duì)輕載ONU，在收到報(bào)告消息之后，立即調(diào)度，對(duì)重載ONU，收到所有ONU報(bào)告消息之后，進(jìn)行調(diào)度。當(dāng)限制授權(quán)大小的時(shí)候，對(duì)輕載ONU的多余帶寬，由重載ONU進(jìn)行分配，所有的報(bào)告消息必須在一個(gè)周期內(nèi)傳送，以便確定該周期中超過部分。因此，OLT能感知重載ONU，并能分配合適的授權(quán)大小。3) DWBA-3需要收到所有ONU的報(bào)告消息，采用2個(gè)授權(quán)，當(dāng)收到ONU的報(bào)告消息之后，立即授權(quán)最小帶寬，收到所有ONU報(bào)告消息之后，對(duì)超過部分進(jìn)行授權(quán)。這個(gè)方法有2個(gè)問題：1)每一個(gè)過載ONU收到2個(gè)授權(quán)，由于增加了保證時(shí)隙而降低了效率；2)分為2個(gè)授權(quán)，由于幀邊界，致使不必要的時(shí)延，因此DWBA-2效率更高。

以上基于WDM IPACT進(jìn)行變化的算法并沒有考慮到授權(quán)調(diào)度問題，使用第一次適應(yīng)的時(shí)間和波長(zhǎng)進(jìn)行分配，僅針對(duì)超過帶寬進(jìn)行授權(quán)調(diào)度。

文獻(xiàn)[10]提出的實(shí)時(shí)調(diào)度機(jī)制(JIT)考慮了WDM EPON網(wǎng)絡(luò)中的有效授權(quán)調(diào)度問題，指出調(diào)度機(jī)制的選擇受到平均隊(duì)列時(shí)延和可用波長(zhǎng)利用率的影響，引入由調(diào)度機(jī)制和調(diào)度策略組成的分層調(diào)度方法，調(diào)度機(jī)制用于確定OLT何時(shí)開始調(diào)度計(jì)算，被當(dāng)作在線調(diào)度和離線調(diào)度之間的連續(xù)集合，在線JIT定義為調(diào)度池，請(qǐng)求帶寬的ONU加入到調(diào)度池中，一旦有可用波長(zhǎng)，池中的ONU開始進(jìn)行調(diào)度。另一方面，調(diào)度策略是指OLT進(jìn)行調(diào)度的方法，每一個(gè)ONU可以當(dāng)作為一項(xiàng)作業(yè)，授權(quán)大小定義為處理時(shí)間，EPON中傳輸?shù)牟ㄩL(zhǎng)表示加工的機(jī)器，這樣，調(diào)度策略可歸納為一系列作業(yè)的調(diào)度，要求在指定時(shí)間內(nèi)，在一系列機(jī)器上進(jìn)行優(yōu)化執(zhí)行。對(duì)其他各種調(diào)度策略或者他們的組合都進(jìn)行了驗(yàn)證，如并行機(jī)模型(PM)、下一個(gè)可用支持波長(zhǎng)(NASC)等，在PM模型中，WDM EPON授權(quán)調(diào)度問題形式化為PMiΣCi，其中P表示相同的并行機(jī)，Mi表示ONU i支持的波長(zhǎng)集合，Ci表示ONU i完成傳輸?shù)臅r(shí)間，優(yōu)化目標(biāo)是使得經(jīng)過EPON傳輸?shù)臄?shù)據(jù)幀排隊(duì)時(shí)延最小，增加資源利用率。

文獻(xiàn)[11]使用調(diào)度理論的方法，研究了多波長(zhǎng)光接入網(wǎng)傳輸授權(quán)機(jī)制，將動(dòng)態(tài)帶寬調(diào)度問題的模型轉(zhuǎn)化為一個(gè)開放式車間調(diào)度方法，對(duì)調(diào)度和波長(zhǎng)分配進(jìn)行形式化，并將其統(tǒng)一為一個(gè)線性規(guī)劃問題，引入啟發(fā)式的禁忌搜索算法來解決這個(gè)問題，可改善波長(zhǎng)分配和減少調(diào)度時(shí)間。但該算法需要用到的分發(fā)規(guī)則為盡早在一個(gè)波長(zhǎng)上調(diào)度ONU，以保證與其他已經(jīng)調(diào)度的ONU不發(fā)生重疊。這些調(diào)度只能在某些特定場(chǎng)景下，產(chǎn)生最優(yōu)解，一般情況下，不能產(chǎn)生最優(yōu)解。

3 帶寬分配策略

3.1 網(wǎng)絡(luò)模型

設(shè)WDM EPON網(wǎng)絡(luò)中有N個(gè)ONU，第i個(gè)ONU的發(fā)送上行流速率為Rui(bit/s)，接收下行流速率為Rdi(bit/s)，ONU可在任一波長(zhǎng)上傳輸，也可在任一波長(zhǎng)上接收，ONU通過半導(dǎo)體光放大器(RSOA)實(shí)現(xiàn)帶寬旁通過濾，可同時(shí)發(fā)送和接收數(shù)據(jù)，一個(gè)ONU在一個(gè)周期只能在一個(gè)波長(zhǎng)上傳輸，2個(gè)ONU不能同時(shí)在同一個(gè)波長(zhǎng)上傳輸。另外，每一個(gè)ONU的負(fù)載不能超過波長(zhǎng)的傳輸能力，OLT能夠同時(shí)接收所有上行波長(zhǎng)數(shù)據(jù)。

OLT通過MPCP協(xié)議獲取所有ONU的帶寬需求，對(duì)給定的ONU帶寬請(qǐng)求，通過某些算法，如門限機(jī)制，可以確定授權(quán)大小。OLT每一個(gè)周期在每一個(gè)波長(zhǎng)上進(jìn)行授權(quán)大小確定和授權(quán)調(diào)度，周期長(zhǎng)度由特定波長(zhǎng)上，每一個(gè)ONU分配的最小帶寬保證確定，每一個(gè)周期進(jìn)行調(diào)度計(jì)算。定義Ci為波長(zhǎng)λi在一個(gè)周期的傳輸時(shí)間長(zhǎng)度。

結(jié)合授權(quán)調(diào)度和波長(zhǎng)分配(P)，以及使周期最短或者最大傳輸時(shí)間Cmax最短的目標(biāo)，其模型定義為

P min(Cmax)

其中，Cmax=max{Ci}。

3.2 高效用帶寬分配策略

根據(jù)文獻(xiàn)[10]和文獻(xiàn)[11]，對(duì)于波長(zhǎng)數(shù)量大于3，WDM EPON中傳輸調(diào)度和波長(zhǎng)分配是一個(gè)NP難題，為解決這類問題，提出了采用啟發(fā)式算法獲取最優(yōu)解。本文提出了一種新的基于擬人策略的啟發(fā)式算法——多波長(zhǎng)高效用帶寬分配算法。

WDM EPON中ONU j在波長(zhǎng)λi上傳輸?shù)臄?shù)據(jù)，用矩形來表示，其中矩形寬為波長(zhǎng)λi的上行傳輸速率，矩形的長(zhǎng)為傳輸時(shí)間 tj，則矩形面積為一個(gè)周期內(nèi)ONU j在波長(zhǎng)λi中上行傳輸?shù)臄?shù)據(jù)量。在一個(gè)周期中，OLT收到所有ONU的帶寬請(qǐng)求后，在多個(gè)波長(zhǎng)上進(jìn)行分配，類似于矩形Packing問題[12]，其中一個(gè)周期可分配的帶寬為大矩形，寬為所有波長(zhǎng)上行傳輸速率之和，長(zhǎng)為一個(gè)周期的傳輸時(shí)間。每一個(gè)ONU請(qǐng)求的上傳數(shù)據(jù)用小矩形表示，寬為某一波長(zhǎng)的上行傳輸速率，長(zhǎng)為對(duì)應(yīng)波長(zhǎng)的傳輸時(shí)間。一個(gè)ONU的上行傳輸可以分配給任意波長(zhǎng)，由于每一個(gè)波長(zhǎng)上行傳輸速率不同，每一個(gè) ONU請(qǐng)求上傳數(shù)據(jù)表示的小矩形不同，但在一個(gè)周期中，只采用一種進(jìn)行傳輸。因此WDM EPON動(dòng)態(tài)帶寬的分配目標(biāo)為可分配的帶寬(大矩形)中盡量裝入更多的ONU帶寬請(qǐng)求(小矩形)，使可分配的帶寬中空閑面積最小，或者為傳輸所有ONU上行數(shù)據(jù)，使最長(zhǎng)傳輸時(shí)間波長(zhǎng)的傳輸時(shí)間最短，即傳輸相同數(shù)據(jù)，使傳輸時(shí)間（周期長(zhǎng)度）最短。

在解決矩形 Packing問題的過程中，根據(jù)生活經(jīng)驗(yàn)，一般采取先占角，然后占邊，最后占中心的方法。受這種思想的啟發(fā)，對(duì)于WDM EPON帶寬分配問題，優(yōu)先選擇高效用的 ONU帶寬分配。對(duì)于當(dāng)前分配狀態(tài)中所有的ONU帶寬分配，若對(duì)等待分配的 ONU帶寬請(qǐng)求進(jìn)行分配以后，其與已經(jīng)分配的某一固定矩形(除初始的分配外)之間的歐氏距離最小，就認(rèn)為該 ONU帶寬分配的效用最高，優(yōu)先考慮該 ONU帶寬分配，這就是基于擬人策略的多波長(zhǎng)高效用 ONU帶寬分配策略。

已知2個(gè)ONU帶寬分配請(qǐng)求，用矩形R1、R2表示，矩形的2條邊分別為傳輸速率和傳輸時(shí)間，在 R1、R2中任取一條邊 e1和邊 e2，將 e1、e2進(jìn)行向兩邊延長(zhǎng)，其交點(diǎn)為O，并得到4個(gè)區(qū)域，定義可用分配為存在某個(gè)區(qū)域中只含ONU帶寬分配矩形R1、R2的這2條邊e1、e2。圖1所示為2個(gè)可用分配示例。

圖1 可用分配構(gòu)成示意圖

設(shè)一個(gè)周期中全部帶寬分配能力構(gòu)成的矩形框的4個(gè)頂點(diǎn)為A、B、C、D，寬AC為所有波長(zhǎng)帶寬能力之和，AB為一個(gè)周期的傳輸時(shí)間，矩形ABCD為帶寬分配區(qū)域。第k個(gè)分配狀態(tài)是指在某個(gè)時(shí)刻有k個(gè)ONU帶寬請(qǐng)求已被放進(jìn)帶寬分配區(qū)域，其中k小于ONU帶寬請(qǐng)求個(gè)數(shù)n。k=0時(shí)為初始分配狀態(tài)；k=n時(shí)為終止分配狀態(tài)；正在處理的分配狀態(tài)為當(dāng)前分配狀態(tài)。

在第k個(gè)分配狀態(tài)下，稱分配區(qū)域外尚未被置入的n–k個(gè)ONU帶寬請(qǐng)求為等待分配塊，稱已被置入分配區(qū)域內(nèi)的k個(gè)ONU帶寬分配為已分配塊。

在第k個(gè)分配狀態(tài)下，ONU帶寬請(qǐng)求等待分配塊M占據(jù)了當(dāng)前分配狀態(tài)中的某一個(gè)可用分配，且該等待分配塊與分配狀態(tài)中的其他任一已分配塊重疊面積為0，則稱等待分配塊M做了一個(gè)分配。對(duì)等待分配塊M進(jìn)行一次分配，如果等待分配塊M的兩垂直邊與形成可用分配中的2個(gè)ONU帶寬請(qǐng)求矩形的兩邊均相交(接觸長(zhǎng)度大于0)，則稱等待分配塊M進(jìn)行了一次合法分配；否則稱等待分配塊M進(jìn)行了一次非法分配。

設(shè)ai、bi分別為等待分配的ONU帶寬請(qǐng)求M在某一波長(zhǎng)上的傳輸時(shí)間和該波長(zhǎng)傳輸速率，di為M與所有已分配ONU帶寬請(qǐng)求之間的最小歐氏(Euclidian)距離(如圖 2 所示)，稱Di=1–2×di/(ai+bi)為等待分配的ONU帶寬請(qǐng)求M進(jìn)行合法分配后的效用。

圖2 矩形之間的歐式距離

根據(jù)先占角，然后占邊，最后占中心的原則，多波長(zhǎng)高效用帶寬分配的策略如下：1) 僅考慮等待分配ONU帶寬請(qǐng)求矩形的所有合法分配；2) 選擇效用最大的合法分配；3) 若2個(gè)等待分配ONU帶寬請(qǐng)求所做的不同合法分配得到相同的效用，則優(yōu)先考慮帶寬請(qǐng)求數(shù)據(jù)量大的；4) 若 2個(gè)等待分配ONU帶寬請(qǐng)求數(shù)據(jù)量也一樣大，則考慮2個(gè)等待分配ONU帶寬請(qǐng)求分配的坐標(biāo)，先比較對(duì)應(yīng)波長(zhǎng)的數(shù)據(jù)傳輸能力，再比較開始傳輸時(shí)間，數(shù)值小者優(yōu)先。根據(jù)以上策略，可使ONU帶寬請(qǐng)求分配之間盡可能從左下角開始，進(jìn)行緊湊分配。另外在選取等待分配ONU帶寬請(qǐng)求矩形時(shí)，其矩形高度（波長(zhǎng)速率）需與傳送波長(zhǎng)速率一致。

完全無人值班模式的實(shí)現(xiàn)對(duì)提高水電站管理效率具有重要意義，必須要加強(qiáng)對(duì)此方面的管理，結(jié)合水電站運(yùn)行特點(diǎn)，確定系統(tǒng)模式建立的要點(diǎn)以及要求，從多個(gè)方面進(jìn)行分析，爭(zhēng)取不斷提高水電站管理效率。

4 多波長(zhǎng)高效用帶寬分配算法

為了利用多波長(zhǎng)高效用帶寬分配算法進(jìn)行計(jì)算時(shí)的空閑時(shí)間，同時(shí)減少多波長(zhǎng)高效用帶寬分配算法的復(fù)雜性，將N個(gè)ONU分成2個(gè)相等大小的不相交子群，OLT通過一個(gè)標(biāo)志位區(qū)分哪一個(gè)子群ONU上行數(shù)據(jù)幀，對(duì)每個(gè)子群，OLT在接收完子群的全部帶寬請(qǐng)求之后，進(jìn)行多波長(zhǎng)高效用帶寬分配算法分配下一周期波長(zhǎng)和帶寬。OLT交替的從2個(gè)子群接收數(shù)據(jù)，在接收一個(gè)子群發(fā)送上行數(shù)據(jù)幀時(shí)，同時(shí)對(duì)另一個(gè)ONU子群進(jìn)行波長(zhǎng)和帶寬分配計(jì)算，避免了空閑時(shí)間，降低了時(shí)延。由于2個(gè)子群的帶寬分配算法完全一樣，后面對(duì)波長(zhǎng)和帶寬的分配僅針對(duì)一個(gè)子群進(jìn)行說明。

在多波長(zhǎng)ONU動(dòng)態(tài)帶寬分配問題中，由于調(diào)度時(shí)間的任意性，每個(gè)等待分配的ONU帶寬請(qǐng)求分配方法有無窮多種，在本文分配策略中，在第 k個(gè)分配狀態(tài)下，可用分配最多不會(huì)超過 2個(gè)。另外，首先挑選效用最高的合法分配進(jìn)行分配，這是一種貪心的方法，采用這種方法可以在帶寬分配區(qū)域內(nèi)分配盡可能多的ONU帶寬請(qǐng)求。

4.1 效用分配算法

效用分配算法的主要過程如下。

首先，在當(dāng)前分配狀態(tài)下，計(jì)算出所有等待分配的ONU帶寬請(qǐng)求在帶寬分配區(qū)域內(nèi)的合法分配，并計(jì)算進(jìn)行所有合法分配后的效用。

然后，對(duì)效用最大的合法分配所對(duì)應(yīng)的等待分配ONU帶寬請(qǐng)求進(jìn)行分配。

分配完成后，更新當(dāng)前分配狀態(tài)，得到新的分配狀態(tài)。

重復(fù)以上過程直到所有等待分配ONU帶寬請(qǐng)求全部置入帶寬分配區(qū)域內(nèi)，或等待分配ONU帶寬請(qǐng)求個(gè)數(shù)不為0但沒有合法分配為止。

4.2 多波長(zhǎng)帶寬分配算法

假定在當(dāng)前分配狀態(tài)下，等待分配ONU帶寬請(qǐng)求M做了一個(gè)合法分配P，得到一個(gè)新的分配狀態(tài)，然后按效用分配算法依次將等待分配ONU帶寬請(qǐng)求放入帶寬分配區(qū)域內(nèi)，此時(shí)帶寬分配區(qū)域內(nèi)所有已分配ONU帶寬請(qǐng)求的數(shù)據(jù)量之和定義為P的價(jià)值度。

圖3為多波長(zhǎng)高效用帶寬分配算法具體描述。

圖3 多波長(zhǎng)高效用帶寬分配算法

為了有效地進(jìn)行多波長(zhǎng)動(dòng)態(tài)帶寬分配，首先對(duì)各ONU請(qǐng)求分配帶寬進(jìn)行判斷，對(duì)于超過保證帶寬門限值的部分，只對(duì)保證帶寬門限部分參與分配，對(duì)于ONU請(qǐng)求帶寬分配小于門限，則按照實(shí)際帶寬請(qǐng)求進(jìn)行分配。初始給定的傳輸周期長(zhǎng)度能保證各 ONU帶寬請(qǐng)求全部按照門限分配進(jìn)行傳輸?shù)臅r(shí)間，使得利用多波長(zhǎng)高效用帶寬分配算法可以把這n個(gè)事先給定的等待分配 ONU帶寬請(qǐng)求全部互不重疊地放入帶寬分配區(qū)域內(nèi)，然后逐漸減少帶寬分配區(qū)域的時(shí)間長(zhǎng)度，采用多波長(zhǎng)高效用帶寬分配算法分配所有等待分配 ONU帶寬請(qǐng)求，直到不能再減小傳輸時(shí)間長(zhǎng)度為止，此時(shí)的帶寬分配區(qū)域就是傳輸周期最短的分配。

5 算法的計(jì)算復(fù)雜性

由于任意2個(gè)ONU請(qǐng)求帶寬分配之間最多產(chǎn)生2個(gè)可用分配，在第k個(gè)分配狀態(tài)下，可用分配的個(gè)數(shù)u不會(huì)超過 2 ×。在效用分配算法中，包含以下 3個(gè)部分：1）判斷所有合法分配的時(shí)間，主要為計(jì)算一個(gè)ONU帶寬請(qǐng)求是否在帶寬分配區(qū)域內(nèi)以及計(jì)算2個(gè)ONU請(qǐng)求帶寬之間是否重疊；2）計(jì)算所有合法分配效用的時(shí)間，主要是計(jì)算 2個(gè)ONU請(qǐng)求帶寬之間的歐拉距離；3）為在所有合法分配中，查找最大效用合法分配時(shí)間。因此效用分配算法處理當(dāng)前分配狀態(tài)的計(jì)算時(shí)間為

從上式可以看出，當(dāng)前分配狀態(tài)的計(jì)算時(shí)間復(fù)雜度為Tk=O(k4)。設(shè)n為一個(gè)子群ONU請(qǐng)求帶寬分配的個(gè)數(shù)，效用分配算法的計(jì)算時(shí)間復(fù)雜度為，即T=O(n5)。

下面分析多波長(zhǎng)高效用帶寬分配算法的計(jì)算復(fù)雜性。

設(shè)當(dāng)前分配狀態(tài)是第k個(gè)分配狀態(tài)，且有u個(gè)合法分配。根據(jù)定義以及效用分配算法分析，計(jì)算一個(gè)合法分配價(jià)值度的時(shí)間為 tp=O(n5)。與效用分配算法的分析相比，多波長(zhǎng)高效用帶寬分配算法處理當(dāng)前分配狀態(tài)的時(shí)間只需將 2）中計(jì)算所有合法分配效用的時(shí)間修改為計(jì)算所有合法分配價(jià)值度的時(shí)間，因此其計(jì)算時(shí)間復(fù)雜度可計(jì)算如下：

將u和tp代入上式，可得TBk=O(n8)，因此多波長(zhǎng)高效用帶寬分配算法的計(jì)算時(shí)間至多為= O ( n9)，即多波長(zhǎng)高效用帶寬分配算法的計(jì)算復(fù)雜度為O(n9)。

實(shí)際上，如果將已被分配ONU請(qǐng)求帶寬占用的帶寬分配區(qū)域去掉，則處理當(dāng)前分配狀態(tài)中合法分配的個(gè)數(shù)遠(yuǎn)少于分析值。另外，如果當(dāng)前分配狀態(tài)下某個(gè)合法分配的價(jià)值度等于n個(gè)ONU請(qǐng)求帶寬的數(shù)據(jù)量之和，則立刻成功停止。

6 實(shí)驗(yàn)結(jié)果

本節(jié)通過模擬方式，對(duì)WDM EPON中不同授權(quán)調(diào)度技術(shù)進(jìn)行模擬比較，使用 NS2網(wǎng)絡(luò)模擬工具，對(duì)本文提出的基于歐氏距離多波長(zhǎng)高效用ONU帶寬分配調(diào)度算法(UDWBA)與其他 2種研究較多的帶寬和波長(zhǎng)分配算法：文獻(xiàn)[8]提出的多個(gè)上行波長(zhǎng)交叉輪循算法(WDM IPACT)和文獻(xiàn)[11]提出的基于禁忌搜索算法的 WDM 動(dòng)態(tài)帶寬分配算法(Tabu DWBA)進(jìn)行比較。主要比較的性能包括系統(tǒng)利用率和分組時(shí)延等。

在模擬實(shí)驗(yàn)中，OLT執(zhí)行授權(quán)大小和調(diào)度，并將分組轉(zhuǎn)發(fā)到網(wǎng)絡(luò)中，授權(quán)大小門限按照每一個(gè)ONU的全部帶寬請(qǐng)求確定。實(shí)驗(yàn)中數(shù)據(jù)幀規(guī)定如下：60%為低優(yōu)先級(jí)的64byte幀，5%為高優(yōu)先級(jí)的300byte幀，10%為中等優(yōu)先級(jí)的580byte幀，25%為1 518byte幀，用自相似傳輸源產(chǎn)生以上數(shù)據(jù)分組，爆發(fā)參數(shù)為0.75，RTT均勻分布在[13μs, 100μs]中，OLT與ONU間距離為2～15km。授權(quán)調(diào)度中最大循環(huán)周期為2ms，使用UDWBA計(jì)算最小保證帶寬為Bmin。由于調(diào)度的限制，一個(gè)周期可能超過2ms(與分配時(shí)長(zhǎng)有關(guān))，但一個(gè)ONU在一個(gè)周期中分配帶寬不能超過Bmin。所有波長(zhǎng)的周期長(zhǎng)度相同，同一波長(zhǎng)的2個(gè)ONU傳輸之間由12byte幀間隔分開，使用以下參數(shù)：1個(gè)OLT，4個(gè)波長(zhǎng)，每一個(gè)波長(zhǎng)支持C=1Gbit/s傳輸速率，128個(gè)WDM ONU，OLT緩存大小為10MB，ONU緩存大小為1MB。

圖 4為算法 UDWBA、WDM IPACT和 Tabu DWBA的各波長(zhǎng)平均上行流帶寬利用率，從圖中可以看出， UDWBA的利用率高于 WDM IPACT和Tabu DWBA。在低負(fù)載下，WDM IPACT利用率較高，這是由于所有波長(zhǎng)的完成時(shí)間并不相同，使得各算法的傳輸周期不同，在WDM IPACT某些波長(zhǎng)直到下一周期開始，一直處于空閑狀態(tài)，而UDWBA和Tabu DWBA傳輸周期更短，空閑時(shí)段較長(zhǎng)，導(dǎo)致波長(zhǎng)利用率較低。隨著負(fù)載的增加，波長(zhǎng)利用率超過73%左右，WDM IPACT傳輸數(shù)據(jù)量不再增加，波長(zhǎng)利用率開始波動(dòng)，但不再增長(zhǎng)，WDM IPACT低利用率主要是由波長(zhǎng)的帶寬浪費(fèi)造成的，而算法UDWBA和Tabu DWBA波長(zhǎng)利用率增加，但在高負(fù)載時(shí)，UDWBA的波長(zhǎng)利用率比Tabu DWBA高20%左右，比WDM IPACT高25%左右，波長(zhǎng)利用率超過95%，這說明UDWBA的波長(zhǎng)利用率更高，其性能接近最優(yōu)解。

圖4 WDM波長(zhǎng)利用率

圖5說明了不同調(diào)度算法下的各波長(zhǎng)上行高優(yōu)先級(jí)數(shù)據(jù)幀平均分組時(shí)延，很明顯，隨著負(fù)載的增加，時(shí)延增加，在低負(fù)載時(shí)，各算法的時(shí)延差別很小，這是由于在低負(fù)載下，循環(huán)周期太短的原因，所有ONU分配的帶寬等于所請(qǐng)求的帶寬，沒有分組保留在ONU的緩存中，因此可以忽略排隊(duì)時(shí)延。但隨著負(fù)載的增加，循環(huán)周期的增長(zhǎng)，WDM IPACT維持最小保證帶寬Bmin的傳輸時(shí)間超過2ms，因此，ONU不能在同一周期中傳輸所有緩存中的數(shù)據(jù)分組，某些數(shù)據(jù)分組不可避免地進(jìn)行排隊(duì)。隨著實(shí)驗(yàn)時(shí)間的增長(zhǎng)，緩存數(shù)據(jù)的增多，排隊(duì)時(shí)延變得更長(zhǎng)。在UDWBA的調(diào)度算法下，循環(huán)周期始終小于2ms，每一個(gè)ONU的帶寬分配足夠傳輸緩存中的高優(yōu)先級(jí)數(shù)據(jù)幀，因此能保證最大分組時(shí)延。從圖中可以看出，在高負(fù)載時(shí)，UDWBA的平均時(shí)延遠(yuǎn)遠(yuǎn)優(yōu)于WDM IPACT，與基于禁忌搜索算法的WDM動(dòng)態(tài)帶寬分配算法相比，平均時(shí)延降低了45%左右，這主要是由于UDWBA采取劃分2個(gè)子群進(jìn)行調(diào)度，減少了信道空閑時(shí)間。

圖5 高優(yōu)先級(jí)數(shù)據(jù)幀平均時(shí)延

7 結(jié)束語

在WDM EPON光接入網(wǎng)絡(luò)中，將授權(quán)調(diào)度和波長(zhǎng)分配進(jìn)行結(jié)合，并將其形式化為矩形Packing問題，由于該問題是一個(gè)NP難問題，只有在特定情況下，可以得到優(yōu)化解。本文提出了新的基于擬人策略的啟發(fā)式算法——多波長(zhǎng)高效用帶寬分配算法，該算法采用最大效用優(yōu)先的分配策略，通過合適的波長(zhǎng)調(diào)度，將多波長(zhǎng)傳輸能力與調(diào)度周期結(jié)合，有效地減少了信道空閑間隙，提高了信道利用率，降低了數(shù)據(jù)分組的平均時(shí)延。模擬實(shí)驗(yàn)表明系統(tǒng)利用率和分組時(shí)延兩大性能都得到較大的改進(jìn)。

[1] CHUAN H, LACHLAN A, ELAINE W, et al. FULL-RCMA: a high utilization EPON[J]. IEEE Journal on Selected Areas in Communications, 2004, 22(8): 1514-1524.

[2] AHMAD R, CHADI M. Quality of service in TDM/WDM Ethernet passive optical networks (EPONs)[A]. The 11th IEEE Symp on Computers and Communications, ISCC’06[C]. Istanbul, Turkey, 2006.616-621.

[3] JUN Z, HUSSEIN T. Media access control for Ethernet passive optical networks: an overview[J]. IEEE Communications Magazine, 2005,43(2): 145-150.

[4] IEEE Standard. 802.3ah-2004, IEEE Standard for Information Technology Telecommunications and Information Exchange Between Systems Local and Metropolitan Area Networks Specific Requirements[S].

[5] MICHAEL P. An Evolutionary Wavelength Division Multiplexing Upgrade for Ethernet Passive Optical Networks[D]. Master’s thesis,Arizona State Univ, Tempe, 2004.

[6] KYEONG S, DAVID G, FUTAI A, et al. Design and performance analysis of scheduling algorithms for WDM-PON Under SUCCESS-HPON Architecture[J]. Journal of Lightwave Technology, 2005,23(11): 3716-3731.

[7] KAE H, DAVID H, IVAN A. Dynamic bandwidth allocation algorithm for differentiated services over WDM EPONs[A]. Proc 9th Int Conf Communications Systems[C]. 2004. 116-120.

[8] MICHAEL P, MARTIN R, MARTIN M. WDM Ethernet passive optical networks[J]. IEEE Communications Magazine, 2006, 44(2):15-22.

[9] AHMAD R, CHADI M, MARTIN M, et al. Dynamic wavelength and bandwidth allocation in hybrid TDM/WDM EPON networks[J]. Journal of Lightwave Technology, 2007, 25(1): 277-286.

[10] MICHAEL P, MARTIN R, CHARLES J, et al. Just-in-time scheduling for multichannel EPONs[J]. Journal of Lightwave Technology,2008, 26(10): 1204-1216.

[11] LEHAN M, JAD E, HAMED A. A joint transmission grant scheduling and wavelength assignment in multichannel SG-EPON[J]. Journal of Lightwave Technology, 2009, 27(21): 4781-4792.

[12] 黃文奇, 許如初. 近世計(jì)算理論導(dǎo)引-NP難度問題的背景、前景及其求解算法研究[M]. 北京: 科學(xué)出版社, 2004.HUANG W Q, XU R C. Introduction of the Current Computation Theory: Background, Future and Algorithms of NP-hard Problems[M].Beijing: Sciences Press, 2004.