一种扩展的单播多播业务联合调度算法设计与仿真＊

杨树伟

（潍坊学院，山东 潍坊 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.