一種擴展的單播多播業(yè)務聯(lián)合調(diào)度算法設計與仿真＊

楊樹偉

（濰坊學院，山東 濰坊 261061）

新一代無線通信網(wǎng)絡的核心網(wǎng)基于IP已成為一種共識，各種網(wǎng)絡在核心網(wǎng)互融互通成為可能。同時，隨著IEEE802.16e、IEEE802.20等各種寬帶無線接入技術的涌現(xiàn)，推動了三網(wǎng)融合發(fā)展的趨勢。隨著業(yè)務的日益增多，用戶的需求不斷增加，一個用戶可能同時接收兩路或多路多播業(yè)務。由于多播業(yè)務大部分為多媒體業(yè)務，因此終端在接收多播業(yè)務時需要消耗更多的電量。然而大多數(shù)終端都由電池供電，電池電量有限，因此，如何有效的使用電池電量，提高終端能耗效率，成為無線通信系統(tǒng)設計與評價系統(tǒng)總體性能的主要目標?；诖耍覀冊谖墨I［1］中設計了兩種多播業(yè)務調(diào)度算法，在保證用戶QoS的同時，達到了降低終端能耗的目的。對于單播數(shù)據(jù)，文中指出在多播超幀的單播傳輸時隙內(nèi)進行調(diào)度，但具體如何調(diào)度并沒有討論。文獻［2］提出了一種基于調(diào)度集合的單播多播業(yè)務聯(lián)合調(diào)度SSBIS算法，但此算法在用戶同時接收多路多播業(yè)務場景下并非十分理想?；诖耍疚脑O計了一種用戶同時接收多路多播業(yè)務場景下的單播多播業(yè)務聯(lián)合調(diào)度算法。

1 系統(tǒng)建模

本文基于無線城域網(wǎng)中點到多點的網(wǎng)絡架構，以下行傳輸為例進行研究，超幀結構如圖1所示。每個超幀包含C個子幀，每個子幀進一步劃分為邏輯信道和單播傳輸時隙，MS請求的各多播業(yè)務在超幀的C個邏輯廣播信道內(nèi)進行調(diào)度，單播業(yè)務在單播傳輸時隙內(nèi)傳輸。最小數(shù)據(jù)速率是一個簡單有效的保證MS服務質(zhì)量的參數(shù)，所以我們用最小數(shù)據(jù)速率來保證MS的服務質(zhì)量，文中用時隙來衡量。

圖1 多播超幀結構

定義如下變量：

◆i：用戶索引號；

◆j：多播業(yè)務索引號；

◆k：邏輯信道索引號，；

◆M：MS數(shù)目；

◆N：多播業(yè)務數(shù)；

◆Paw：MS處于清醒狀態(tài)時，每個時隙的平均能耗。本文假定當MS處于休眠狀態(tài)時，每個時隙的平均能耗為0；

◆Pm：MS由休眠轉變?yōu)榍逍褷顟B(tài)的平均能耗，因為清醒轉變?yōu)樾菝郀顟B(tài)的平均能耗很小，文中假定為0；

◆ri：一個調(diào)度周期后所獲得的數(shù)據(jù)速率；

◆Rmi：為保證MSiQoS的最小數(shù)據(jù)速率要求；

◆ui：MSi因接收單播數(shù)據(jù)而從休眠轉變到清醒狀態(tài)的次數(shù)；

◆mi：MSi因接收多播數(shù)據(jù)而從休眠轉變到清醒狀態(tài)的次數(shù)；

◆Tj：為多播業(yè)務j分配的時隙數(shù)；

◆Ttn：時間閥值。

同時定義終端業(yè)務矩陣MT、業(yè)務信道矩陣TC以及終端信道矩陣MC，表示如下：

終端業(yè)務矩陣MT代表MS對多播業(yè)務的需求情況，若MSi需要接收多播業(yè)務j，MTij＝1；否則為0。業(yè)務信道矩陣TC代表各多播業(yè)務在邏輯信道間的調(diào)度情況，由文獻［1］中的PPMS調(diào)度算法確定，若多播業(yè)務j分配到了邏輯廣播信道k中，TCjk＝1；否則為0。由式（1）與式（2），可以得到終端信道矩陣MC，MC表示為：

MSi在一段時間T內(nèi)，本文用超幀數(shù)量來衡量，假設一共n個超幀，總能耗表示為：

我們的目標就是在滿足MS服務質(zhì)量的同時，降低終端總能耗，表示為：

PPMS算法確定了各多播業(yè)務在邏輯信道間的調(diào)度情況，因此公式（4）中MTij和Tj是確定值，同時Paw與Ptn也可看作定值，所以Pi的值可看作與ui、oi、mi以及Pwaste相關。為降低總的能耗，需要盡可能最小化這些變量的值。ui的值與調(diào)度集合劃分有關，由于多路多播業(yè)務的連續(xù)傳輸，SSBIS算法調(diào)度集合的劃分已不適用，我們需要給出調(diào)度集合的重新劃分方案，盡可能使值最?。焕没谧铋L休眠的時間算法可以得到最小的oi值；MSi接收多播業(yè)務時浪費的能耗受Pwaste與mi影響，不同的mi值對應不同的Pwaste值，如何合理調(diào)度，是我們函待解決的問題。

2 算法設計

2.1 SSBIS算法

SSBIS算法主要分為三步：首先，定義邏輯信道相鄰時隙區(qū)間；其次，根據(jù)滑動窗口機制將MS劃分成1個單播調(diào)度集合和C個多播調(diào)度集合，每個邏輯信道分配一路多播業(yè)務，多播調(diào)度集合中MS的單播數(shù)據(jù)在邏輯信道的相鄰時隙區(qū)間內(nèi)進行調(diào)度；最后，基于最長休眠時間調(diào)度算法對單播調(diào)度集合的單播數(shù)據(jù)調(diào)度。

2.2 ESSBIS算法

本文在PPMS算法的基礎上，借鑒SSBIS算法思想，設計MS同時接收多路多播業(yè)務場景下的聯(lián)合調(diào)度算法，稱之為擴展的基于調(diào)度集合單播多播業(yè)務聯(lián)合調(diào)度ESSBIS（Extended Scheduling Set Based Integrated Scheduling）算法。ESSBIS算法中，每個邏輯信道不再僅包含一路多播業(yè)務，而是包含多路。我們假定在某個邏輯廣播信道中分配了5路多播業(yè)務，MSi需要接收其中的第一、二、四路多播業(yè)務。這種MS需求業(yè)務調(diào)度的不連續(xù)性，帶來了兩個問題：

第一，從舉例中可以看到，MSi并不需要接收此邏輯信道內(nèi)的最后一路多播業(yè)務，因此，MSi接收完第四路多播業(yè)務后可以進入休眠狀態(tài)，在第五路多播業(yè)務調(diào)度完畢的前一刻沒必要重新醒來。所以，對ESSBIS而言，SSBIS算法的調(diào)度集合劃分方法不再適用，我們需要給出新的調(diào)度集合劃分方案。

第二，邏輯信道內(nèi)MS接收多播業(yè)務的不連續(xù)性，需要考慮MS在邏輯信道內(nèi)何時進入休眠狀態(tài)。對上面的舉例而言，若為第三路業(yè)務分配的時隙數(shù)大于時間閥值Ttn，MSi就應進入休眠，否則MSi保持清醒狀態(tài)，這樣可以最大化的節(jié)約能耗。

下面就這兩個問題分別給出解決方案：

（1）調(diào)度集合劃分

因邏輯信道內(nèi)MS接收多播業(yè)務的不連續(xù)性，我們將邏輯信道的相鄰時隙區(qū)間定義為兩部分。邏輯信道k前相鄰時隙區(qū)間定義為：

邏輯信道k后相鄰時隙區(qū)間定義為：

其中tks與tke代表邏輯信道k的開始時隙和結束時隙。這樣，每個超幀劃分為2C個多播調(diào)度集合，而非SSBIS算法劃分的C個多播調(diào)度集合，ESSBIS算法區(qū)間劃分如圖2所示。

圖2 ESSBIS算法區(qū)間劃分示意圖

如果不能劃分到第一個多播調(diào)度集合，可試圖將其劃分到其它多播調(diào)度集合。同樣，我們假定每個MS只能劃分到一個多播調(diào)度集合。

（2）邏輯信道中MS狀態(tài)轉換

MSi需要在某個邏輯信道醒來，并不意味著MSi接收此邏輯信道中的所有多播數(shù)據(jù)。當MSi遇到不需要接收的多播業(yè)務時，我們就需要進行判斷。如果不需要一個或連續(xù)多個多播業(yè)務分配時隙和大于時間閥值，MSi就應進入休眠狀態(tài)；否則，MSi保持清醒狀態(tài)。

通過PPMS算法，可以得到各多播業(yè)務在邏輯信道間的調(diào)度情況。為了便于描述，我們假定每個邏輯信道均包含n路多播業(yè)務。各多播業(yè)務的分配可表示如下：

其中，Aky代表邏輯信道k的第y個多播業(yè)務標識。對MSi，我們建立Fk＝［fk1，fk2，…，fkn］。若MSi請求了多播業(yè)務Aky，fky＝1；否則為0。為求解MS醒來次數(shù)，每一個邏輯信道MS請求的第一個與最后一個多播業(yè)務之間，如果未請求的一個或連續(xù)多個多播業(yè)務時隙和小于時間閥值Tm，將Fk中對應的元素設為1。經(jīng)比較后，F(xiàn)k變?yōu)镕′k，F(xiàn)′k＝［f′k1，f′k2，…，f′kn］。

表1 某一超幀中的醒來次數(shù)

表1給出了在MSi各邏輯信道中的醒來次數(shù)示例，1表示MSi需要接收的多播業(yè)務，0表示MSi不需要接收的多播業(yè)務，而加粗帶字符底紋的1表示經(jīng)過比較后MSi不需要進行狀態(tài)轉換。由表1可以看出，在第k個邏輯信道中，MSi醒來次數(shù)等于F′k中1的個數(shù)減去出現(xiàn)連續(xù)1的次數(shù)。因此，MSi在任意超幀中醒來次數(shù)可以用圖3所示的流程來得到。

通過以上方案，我們就可以按照SSBIS算法思想對用戶同時接收多路多播業(yè)務場景下的單播多播業(yè)務進行合理調(diào)度。

圖3 MS接收多播業(yè)務醒來次數(shù)統(tǒng)計流程圖

3 仿真及性能分析

3.1 仿真場景及參數(shù)

仿真基于IEEE 802.16e系統(tǒng)幾個蜂窩小區(qū)組成的單頻網(wǎng)，假定單頻網(wǎng)內(nèi)共有6路多播業(yè)務，終端除了接收多播業(yè)務外，還有最小數(shù)據(jù)速率要求的單播業(yè)務，單播業(yè)務的最小速率要求分別為10kbps、20kbps、30kbps。同時，我們假定一個超幀長度為5ms，共包含300個時隙，每個超幀包含2個邏輯信道，MS從休眠轉換為清醒狀態(tài)時需要消耗2個時隙的能耗。本文用平均能耗效率（Average energy efficiency，AEE）來衡量能耗效率［3］。AEE定義如下：

3.2 仿真結果及分析

圖4仿真了AEE隨MS數(shù)目的變化規(guī)律。從圖中可以清楚的看到，當MS數(shù)目較小時，SSBIS算法可以取得較好的效果，當MS數(shù)目增多到一定數(shù)值后，ESSBIS算法將優(yōu)于SSBIS算法。原因在于，SSBIS算法每個超幀中有較多的邏輯信道相鄰時隙可供MS的單播數(shù)據(jù)進行調(diào)度，MS數(shù)目較少時，MS接收的單播數(shù)據(jù)可以很好的在邏輯信道內(nèi)調(diào)度，能耗效率較高。隨著用戶數(shù)目的增多，由于用戶可以同時接收多路多播業(yè)務，此時多播業(yè)務在邏輯信道間的分配取得的收益將大于因調(diào)度集合重新劃分所造成接收單播業(yè)務時的損耗。

圖4 AEE隨MS數(shù)目的變化規(guī)律

4 結束語

本文在SSBIS算法思想的基礎上，針對用戶同時接收多路多播業(yè)務場景，設計了一種擴展的單播多播業(yè)務聯(lián)合調(diào)度算法。仿真結果表明，當用戶達到一定數(shù)量，ESSBIS算法平均能耗效率優(yōu)于SSBIS算法。

［1］楊樹偉，田霖，石晶林.單小區(qū)多播業(yè)務調(diào)度算法設計與仿真［J］.系統(tǒng)仿真學報，2009，21（18）：5672－5676.

［2］田霖，楊育波，方更發(fā)，等.基于調(diào)度集合的多播單播數(shù)據(jù)聯(lián)合調(diào)度算法［J］.軟件學報，2008，19（12）：3196－3206.

［3］Shi J L，F(xiàn)ang G F，Sun Y，etal.Improving Mobile Station Energy Efficiency in IEEE 802.16eWMAN by Burst Scheduling［C］／／IEEE Globecom，2006：1－5.