一種擴展的單播多播業務聯合調度算法設計與仿真＊

楊樹偉

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

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

1 系統建模

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

圖1 多播超幀結構

定義如下變量：

◆i：用戶索引號；

◆j：多播業務索引號；

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

◆M：MS數目；

◆N：多播業務數；

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

◆Pm：MS由休眠轉變為清醒狀態的平均能耗，因為清醒轉變為休眠狀態的平均能耗很小，文中假定為0；

◆ri：一個調度周期后所獲得的數據速率；

◆Rmi：為保證MSiQoS的最小數據速率要求；

◆ui：MSi因接收單播數據而從休眠轉變到清醒狀態的次數；

◆mi：MSi因接收多播數據而從休眠轉變到清醒狀態的次數；

◆Tj：為多播業務j分配的時隙數；

◆Ttn：時間閥值。

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

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

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

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

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

2 算法設計

2.1 SSBIS算法

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

2.2 ESSBIS算法

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

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

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

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

（1）調度集合劃分

因邏輯信道內MS接收多播業務的不連續性，我們將邏輯信道的相鄰時隙區間定義為兩部分。邏輯信道k前相鄰時隙區間定義為：

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

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

圖2 ESSBIS算法區間劃分示意圖

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

（2）邏輯信道中MS狀態轉換

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

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

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

表1 某一超幀中的醒來次數

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

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

圖3 MS接收多播業務醒來次數統計流程圖

3 仿真及性能分析

3.1 仿真場景及參數

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

3.2 仿真結果及分析

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

圖4 AEE隨MS數目的變化規律

4 結束語

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

［1］楊樹偉，田霖，石晶林.單小區多播業務調度算法設計與仿真［J］.系統仿真學報，2009，21（18）：5672－5676.

［2］田霖，楊育波，方更發，等.基于調度集合的多播單播數據聯合調度算法［J］.軟件學報，2008，19（12）：3196－3206.

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