您的当前位置：首页正文

基于调度集合的多播单播数据联合调度算法

来源：意榕旅游网

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

基于调度集合的多播单播数据联合调度算法

田霖1,3+, 杨育波1,3, 方更法1, 石晶林1, DUTKIEWICZ Eryk 2 123

∗

(中国科学院计算技术研究所下一代互联网研究中心,北京 100190)

(Wireless Technologies Laboratory, University of Wollongong of Australia, Australia) (中国科学院研究生院,北京 100049)

A Scheduling Set Based Integrated Scheduling Algorithm for Unicast and Multicast Traffic *

TIAN Lin1,3+, YANG Yu-Bo1,3, FANG Geng-Fa1, SHI Jing-Lin1 , DUTKIEWICZ Eryk 2

(Next Generation Internet Research Center, Institute of Computing Technology, The Chinese Academy of Sciences, Beijing 100190, China)

(Wireless Technologies Laboratory, University of Wollongong of Australia, Australia) (Graduate University, The Chinese Academy of Sciences, Beijing 100049, China)

+ Corresponding author: E-mail: tianlindd@ict.ac.cn

Tian L, Yang YB, Fang GF, Shi JL, Dutkiewicz E. A scheduling set based integrated scheduling algorithm for unicast and multicast traffic. Journal of Software, 2008,19(12):3196−3206. http://www.jos.org.cn/ 1000-9825/19/3196.htm

Abstract: A new problem is addressed, which is how to improve energy efficiency for both unicast and multicast services without violating QoS requirements of mobile stations in 802.16e wireless networks. To solve this problem, a scheduling set based integrated scheduling (SSBIS) algorithm is proposed. SSBIS partitions all the mobile stations into multicast scheduling sets and a unicast scheduling set. All the unicast data of the mobile stations in the multicast scheduling sets are transmitted in the adjacent intervals of their multicast data transmission periods, and for the mobile stations in the unicast scheduling set, longest sleep duration based (LSDB) scheduling scheme is obtained using convex optimization to improve energy efficiency of the whole system. Numerical results show that SSBIS can save overall energy significantly and guarantee the minimum data rates of mobile stations at the same time.

Key words: IEEE 802.16e; energy efficiency; integrated scheduling; multicast; scheduling set

摘要: 首先定义和分析了IEEE 802.16e无线城域网中的一个新问题,即如何在保证移动终端服务质量的前提下,通过合理地调度终端的单播业务和多播业务来降低终端能耗.针对该问题,提出一种基于调度集合的联合调度算法(scheduling set based integrated scheduling,简称SSBIS).SSBIS算法将所有移动终端划分到多播调度集合或单播调度集合中,并利用多播数据的传输特点,在多播数据传输的相邻时隙内发送多播调度集合中所有终端的单播数据,而对于单播调度集合中的终端,则通过凸优化方法求得使终端休眠时间最长的单播业务调度方案,以达到降低终端能耗的目的.仿真实验显示,SSBIS算法在满足移动终端的最小数据速率要求的同时,可以明显地降 ∗

Supported by the National Natural Science Foundation of China under Grant No.90604016 (国家自然科学基金)

Received 2007-05-31; Accepted 2007-12-24

田霖等:基于调度集合的多播单播数据联合调度算法

低终端能耗.

关键词: IEEE 802.16e;省电;联合调度;多播;调度集合中图法分类号: TP393 文献标识码: A

3197

随着无线通信技术的发展,移动终端支持的业务日益丰富,例如,3G网络不仅支持语音通信,而且可以支持数据、多媒体等不同种类的业务.然而,由于很多移动终端都是由电池供电,电池有限的电量将极大地影响丰富多样的业务开展.因此,如何有效地使用电池能量,提高终端能耗效率,从而降低终端能耗成为无线通信系统设计的主要目标之一,能耗效率也成为评价系统总体性能的重要指标.

IEEE 802.16e[1]是一种新兴的宽带无线接入技术,它以低成本、高带宽、提供服务质量保证、支持终端移动及IP接入等特点,成为第四代移动通信标准的备选方案之一.802.16e协议也特别关注了能耗效率问题,其中定义的休眠模式[1]即为一种降低移动台(mobile station,简称MS)能耗的机制.在休眠模式中,MS有两种状态:清醒状态和休眠状态.当基站(base station,简称BS)和移动台之间没有数据传输时,MS可以进入休眠状态,关闭某些物理部件(如射频模块等)以减小能耗.其中,休眠时间长度由BS和MS通过MOB-SLP_REQ消息和MOB-SLP_RSP消息进行协商.802.16e中的休眠模式被提出以后,迅速成为新的研究热点,国内外专家学者开始研究IEEE 802.16e中的休眠模式及相关算法,包括对休眠模式的分析、改进及休眠参数选择等[2−4].

终端能否进入休眠状态是由其数据传输情况决定的,而调度算法在很大程度上决定了数据传输情况.例如,若调度算法频繁地为终端调度数据,虽然每次调度的数据量很小,但终端为接收数据需要一直处于清醒状态,不能进入休眠,此时休眠模式就不能发挥作用.因此,休眠模式的省电性能需要通过合理地设计系统中的调度算法进行优化.针对该问题,文献[5]提出一种降低终端能耗的单播业务调度算法,该算法以虚拟突发(virtual burst)的方式为MS调度数据包,在不影响其他MS服务质量的前提下,为每个MS一次传输尽可能多的数据,并让未参与调度的MS进入休眠状态以达到省电的目的.文献[6]考虑了如何进行多播业务的调度以降低终端能耗,旨在解决802.16e网络中多播数据的传输吞吐量与能耗之间的权衡问题.它首先定义了“多播超帧”的概念,基于“多播超帧”提出了一种多播数据的传输方法,该方法可以使终端仅在需要接收的多播数据的传输时隙内处于清醒状态,其他时间可以进入休眠,以降低能耗.目前的研究表明,可降低终端能耗的调度算法的基本思想是以突发的方法传输数据,即将某一终端的数据一次集中地发送完毕,使得该终端在较长的一段时间内不必进行数据收发,从而可以进入休眠,达到降低终端能耗的目的[5−8].此外,由于IEEE 802.16e协议中的业务有服务质量(quality of service,简称QoS)要求,终端的休眠不能影响其上业务的服务质量,因此,突发传输方式需要在不影响其他终端服务质量的前提下,尽可能长时间地为某一终端连续发送数据包.

然而,目前的算法都是在考虑终端上只存在单播业务或多播业务的情况下设法降低终端能耗,而没有考虑单播和多播两种类型的业务共存的情况.随着多媒体应用的普及,多播和单播业务越来越多地同时存在于一个MS上.此时,若不同时考虑多播业务和单播业务的传输特点,只针对一种业务类型设计调度算法是不能实现最大化降低终端能耗的,这可以通过下面的例子进行简要说明.图1给出在不同调度方式下MS需要接收的数据的传输时间.MS1,MS2和MS3除了要接收单播数据以外,还要接收同一个多播业务的数据,MS4仅接收单播数据,它们在无数据接收时均进入休眠状态.若单播和多播数据被孤立地调度,则MS1,MS2和MS3都需要醒来两次以分别接收属于自己的单播数据和多播数据,如图1(a)所示;若调度算法能够综合考虑单播和多播数据的传输特点,则可以尽量在多播业务传输时隙的相邻时隙内为MS1,MS2和MS3调度单播数据,如图1(b)所示,从而MS1,MS2和MS3只需要醒来一次便可以接收完单播数据和多播数据,与图1(a)相比,减少了MS在清醒状态和休眠状态之间的转换次数,从而降低了MS在状态转换中耗费的电量.

通过以上分析可知,多播、单播联合调度算法在提高终端能耗效率方面的必要性主要体现在两个方面:首先,由于所有接收相同多播业务的MS都需要在接收该业务的时隙内醒来,因此,如果一个调度算法可以充分利用多播数据传输时隙的相邻时隙为接收该多播业务的MS传输单播数据,将会节省终端的电量,如图1所示,其二,多播业务的存在给单播数据的突发传输方式[5−8]带来了限制,突发长度的确定受多播传输模式的影响,因此

3198

Journal of Software 软件学报 Vol.19, No.12, December 2008

传统的针对单播数据的突发调度算法是不完全适用的.由此可见,多播单播联合调度算法在提高终端能耗效率方面很有必要,但目前在宽带无线通信领域尚未提出相关的算法.为此,本文提出一种基于调度集合的联合调度算法(scheduling set based integrated scheduling,简称SSBIS),该算法首先将所有的MS划分到单播调度都集合(unicast scheduling set)或多播调度集合(multicast scheduling set)中,多播调度集合中MS的所有单播数据均在多播数据传输的相邻时隙内调度;对于单播调度集合,将根据由凸优化方法求得的使单播调度集合中MS休眠时间最长的时隙分配方案,基于突发的方式为MS调度单播数据.SSBIS算法的核心思想就是充分利用多播数据的传输特点,结合突发调度方法,达到节省MS电量的目标.

tttt

t t t t

Fig.1 Scheduling samples for unicast and multicast traffic

图1 单播数据和多播数据的调度示例

的问题.第2节针对该问题给出SSBIS算法的设计.第3节对算法进行仿真和分析.第4节进行总结.

本文第1节在给定的系统模型下,根据单播业务和多播业务的传输特点分析调度算法如何降低终端能耗

1 系统模型与问题分析

本文基于IEEE 802.16e无线城域网中点到多点的网络架构,以下行传输为例进行研究.802.16e标准将下行数据业务划分为以下5种类型:UGS,RT-VR,ERT-VR,BE和NRT-VR[1].其中,UGS,RT-VR和ERT-VR属于实时业务,为保证其实时性,若终端上存在这3种类型的业务,一般不进入休眠状态.因此,本文与大部分研究802.16e中休眠问题的文献[2−5]一样,只讨论终端上存在BE和NRT-VR这两类非实时业务的情况.在该情况下,最小数据速率是一个简单、有效的可以保证MS服务质量的参数[9].基于此,本文采用最小数据速率作为MS的QoS要求.本文中的带宽以时隙(time slot)来衡量,并假设每个时隙所能传输的数据速率对一个MS来说是固定的,用ci表示MS i在每个时隙上所能获得的数据速率.

文献[6]提出的多播传输模型可以在多播数据吞吐率和终端的能耗效率之间取得很好的折衷,因此,本文采用文献[6]中的静态模型作为多播业务的传输方式,它提前确定多播业务和逻辑广播信道之间的对应关系.逻辑广播信道为每一帧中传输广播和多播数据的区域,紧随前序头[6].如图2所示,多播业务#1在逻辑广播信道#1上传输,多播业务#2在逻辑广播信道#2上传输,依此类推.假设系统中存在G个多播业务,则需要G个逻辑广播信道,逻辑广播信道的大小固定,并且每G个连续的帧组成一个“多播超帧”.根据MS接收的多播业务将MS划分到对应的多播业务组中,例如多播业务组1中的MS接收多播业务#1,依此类推.因此,多播业务组j中的MS应在逻辑广播信道#j内处于清醒状态以接收多播业务#j的数据.

在讨论MS的能耗问题之前,首先给出以下假设:一个小区中有M个MS,使用标志符i索引(i=1,2,…,M);一个小区中包含G个不同的多播业务组,用j来索引(j=1,2,…,G),本文中一个MS在某一时刻只能属于一个多播业务组;Paw表示处于清醒状态的MS在每个时隙上的平均能耗,Ptn表示MS从休眠状态转换到清醒状态过程的平均能耗,由于MS从清醒状态转化到休眠状态的能耗及处于休眠状态时的能耗很小,因此可以忽略[10];ni表示MS i为接收单播数据而从休眠状态转化到清醒状态的次数;di表示一个调度周期内分配给MS i的时隙数量,ri为一个调度周期后MS i所获得的数据速率;MS i为保证其服务质量的最小数据速率要求为Rimin.

田霖等:基于调度集合的多播单播数据联合调度算法

3199

…

Frame

Fig.2 Multicast traffic transmission mode

图2 多播数据传输方式

基于以上分析和假设,一个MS的能耗由其处于清醒状态的时间和从休眠状态到清醒状态的转换次数来决定.属于一个多播业务组的MS不仅需要在接收单播数据时醒来,而且需要在相应的逻辑广播信道中醒来,以接收多播数据.因此,MS i在一段时间T内(T足够长)的总能耗Pi可以表示为

Pi =⎨

⎧⎪PMj + DiPaw+ (mj+ni)Ptn,i∈BGj

(1)

, otherwiseDP+ nP⎪itn⎩iaw

其中,BGj={i:MS i属于多播业务组j}.PMj是多播业务组j中的一个MS在T内接收该多播业务所消耗的能量,mj是接收该多播业务所需的从休眠状态到清醒状态的转换次数,等于时间T内逻辑广播信道#j的数量.由于本文中多播数据传输方式是提前确定的,因此,时间T内,PMj和mj的值固定不变.Di是MS i在时间T内除接收多播数据的时隙外处于清醒状态的时隙数量.

降低MS能耗的调度算法的目标是在保证每个MS服务质量的同时,最小化所有MS的平均能耗(在足够长的时间T内).本文以最小数据速率作为MS的服务质量要求,因此,调度算法的目标可以形式化为

min

∑Pi

i = 1

(2)

s.t. ri≥Rimin; i=1,2,...,M

为获得最优化的结果,调度算法应该同时考虑多播业务和单播业务的传输特点.基于该思想,本文将在第2节中阐述解决优化问题(2)的调度算法.

2 基于调度集合的联合调度算法(SSBIS算法)

2.1 相邻时隙区间和调度集合

文献[5]将MS处于清醒状态而未接收数据的情形定义为空闲状态,并且指出MS处于空闲状态时是在浪费电量.因此,若MS能够在处于清醒状态时一直收发数据,一旦无数据传输则进入休眠状态,便可以避免处于空闲状态时的能耗.但由于MS从休眠状态转换到清醒状态也需要耗电,如果MS处于空闲状态的时间比较短,导致状态转换的能耗大于空闲状态的能耗,则MS不必进入休眠状态.因此,MS进入休眠状态的条件是MS预期处于空闲状态的能耗大于状态转换的能耗,即

Pidle⋅t>Ptn⇒t>Ptn/Pidle (3)

其中,Pidle代表处于空闲状态的MS在每个时隙上的平均能耗,t代表处于空闲状态的预期时间(以时隙衡量).定

义Ttn为空闲时间阈值,若处于空闲状态的预期时间大于Ttn,则MS需要进入休眠状态.综上可得:

Ttn = Ptn/Pidle (4)

根据式(4),本文定义在一个多播超帧内,逻辑广播信道#j的相邻时隙区间Sj为Sj = (ts−Ttn, ts) ∪ (te, te+Ttn),其中ts和te分别为逻辑广播信道#j在该多播超帧内的开始时隙和结束时隙.

假设i∈BGj且ti代表某次基站为MS i发送单播数据的开始时隙.若ti∈Sj,则MS i在本次接收多播数据和单

3200

Journal of Software 软件学报 Vol.19, No.12, December 2008

播数据之间不必进入休眠,这是因为MS i预期处于空闲状态的时间在ti和te(或ts)之间,小于Ttn.若MS i每次单播数据的传输开始时隙均处于Sj内,则ni=0.在式(1)中,PMj和mj是确定的值,因此Pi仅由Di和ni决定.如果ni=0,则通过适当的调度策略可以使Di最小,并且最小值接近于传输MS i的单播数据所需的总时隙数.因此,当ni=0时,Pi可以取得最小值.

基于以上分析,联合调度算法需要使尽可能多的接收多播数据的MS满足ni=0以降低系统总能耗,不能满足ni=0条件的接收多播数据的MS将与不属于任何多播业务组的MS一起调度.据此,本文提出基于调度集合的联合调度算法(SSBIS),为不同类型的MS分配时隙.其中,调度集合的定义是:一个调度集合由将在同一组时隙内以相同策略被调度的多个MS组成.一个MS属于且仅属于一个调度集合.调度集合分为两类:多播调度集合和单播调度集合.

SSBIS算法将系统中所有的MS划分到一个单播调度集合Cu和G个多播调度集合Cj(j=1,2,…,G)中.多播

调度集合Cj由属于多播业务组j且可以在逻辑广播信道#j的相邻时隙区间Sj内完成单播数据接收的MS组成.不属于任何多播调度集合的MS组成单播调度集合Cu.Cj中MS的单播数据将在逻辑广播信道#j的相邻时隙区间Sj内被调度完毕,Cu中MS的单播数据将在除逻辑广播信道#j(j=1,2,…,G)及其所有相邻时隙区间外的其余时隙内被调度,这些时隙统一定义为Su.图3给出了Sj,Su和逻辑广播信道的分布关系.本文将一个调度周期定义为一组连续的时隙,这组时隙包括一个Su、一个逻辑广播信道及其相邻时隙区间.基于以上分析,SSBIS算法需要解决以下两个主要问题:(a) 如何决定MS属于哪个调度集合;(b) 针对不同类型的调度集合设计不同的调度策略.本文将在第2.2节和第2.3节中分别阐述解决问题(a)和问题(b)的方法.

…

Fig.3 Distribution of Su, Sj and logical broadcast channel

图3 Su,Sj和逻辑广播信道的分布

2.2 调度集合划分

根据多播调度集合Cj的定义,Cj的生成原则是从多播业务组j中选择尽可能多的MS组成,这些MS都能在

Sj中调度完毕且满足ni=0的条件.因为当ni=0时,Pi最小,所以Cj的生成原则可以使最多的MS能耗达到其最小值.以下将根据Cj的生成原则设计一种多播调度集合的生成方法.假设i∈BGj,SLi代表一个调度周期后MS i的最长休眠时间.根据普遍采用的滑动窗口机制,SLi的计算方法如下:

⎛⎛RiminSLi⎞min1 = rSL=L−⇒⎜⎟iRiisw⎜1−

Lrisw⎠⎝⎝⎞

⎟ (5) ⎠

其中,Lsw代表滑动窗口的大小.本文定义Tj为逻辑广播信道#j的循环周期,即一个多播超帧的长度.SLi≥Tj是ni=0的必要条件,因为若SLiri≥

Rimin

(6)

1−TjLsw

根据滑动窗口机制,可以计算出为获得数据传输率ri需要为MS i分配的时隙数di:

Rimin(Lsw−di)cidi(ri−Rimin)Lsw

+ = ri ⇒ di= ;(ci󰀕Rimin) (7)

LswLswci

由式(7)可以看出,di与ri成正比.因此,当ri取得最小值,即SLi=Tj时,di最小,其最小值可表示为

田霖等:基于调度集合的多播单播数据联合调度算法

di=

RiminTjLsw(Lsw−Tj) ci

3201

(8)

假设多播业务组j中共有M′个MS,根据式(8)计算出这M′个MS的di值并按升序排列,得到集合A= {d1,d2,...,dM′}.令Kj=maxk:∑m = 1dm≤2Ttn,则在Sj内最多能为Kj个MS传输数据,并保证它们的休眠时间等于Tj.下面证明Kj为多播业务组j中能够达到能耗最小值的MS的最大数量.

证明:假设存在K′个MS可以在Sj中调度完毕且K′>Kj.因为Kj=maxk:∑m = 1dm≤2Ttn,所以K′>MS中至少有一个MS k,dk<(RkminTjLsw)((Lsw−Tj) ck).因为SLk根据以上分析,本文提出的调度集合划分方法是对于每一个多播业务组j,根据式(8)计算出其中所有MS的

}{k

}di值并按升序排列,计算Kj并选择排列中前Kj个MS组成多播调度集合Cj.当所有的多播调度集合生成后,剩余的未属于任何多播调度集合的MS将组成单播调度集合Cu.

一旦多播调度集合Cj生成,则需要为Cj中的每个MS分配的时隙数也随之确定.根据每个MS应分配的时隙数,在Sj上为其连续分配时隙,则可完成对多播调度集合中MS的单播业务的调度.

由以上分析可知,多播调度集合中MS的数量越多,能耗达到其最小值的MS就越多,系统的能耗效率也就越高.多播调度集合中MS的数量是由多播业务与单播业务的共存情况决定的,包括多播业务与单播业务的比例及在时间上的分布.其中,多播业务在系统中所占的比例可以通过多播业务的数量及接收每个多播业务的

MS个数来体现,若多播业务的数量较少或接收每个多播业务的MS个数较少,则将造成多播调度集合中MS的数量较少;多播业务与单播业务在时间上的分布主要体现在MS是否可以同时接收两种业务,若由于MS上单播业务的服务质量要求或多播业务与单播业务未同时存在,使得MS无法同时接收两种业务,则MS无法划入多播调度集合,从而减少了多播调度集合中MS的数量.多播调度集合中MS数量的减少将降低相邻时隙区间调度方法带来的省电效果.同时,多播调度集合中MS数量的减少将使单播调度集合中MS的数量增加.因此,为保证

SSBIS算法在多播调度集合中MS数量较少时也能达到较高的能耗效率,本文也需要针对单播调度集合设计一种省电的调度算法,尽量降低单播调度集合中MS的总能耗.第2.3节将针对单播调度集合Cu设计一种基于最长休眠时间的调度算法.

2.3 基于最长休眠时间的调度算法(longest sleep duration based,简称LSDB)

LSDB算法的设计思想是在多播传输模式的限制下,充分利用突发传输的思想,使Cu中所有MS的总休眠时间最长,从而达到总能耗最小.tiawake代表MS i为保证其服务质量最晚应该醒来接收数据的时间,可以通过SLi 来计算.LSDB算法为Cu中每个MS记录该时间,并在每次为MS i分配完时隙后更新其tiawake值.根据tiawake可判断MS i是否需要在当前Su内调度.假设在当前Su中,MS i(i=1,…,K)需要被调度,则调度算法的目标就是在保证这K个MS的服务质量的同时,使它们的总能耗最小.在突发传输方式下,这K个MS的总休眠时间最长,则它们的总能耗最小.因此,该问题可以表示为如下优化问题:

⎛Rmin

max∑SLi⇒max∑Lsw⎜1−i

rii=1i=1⎝

⎞

⎟ (9a) ⎠

s.t. ∑di=Tc (9b)

i=1

SLi≥Lmin

RiminLsw

⇒ri≥ (i=1,2,...,K) (9c)

Lsw−Lmin

其中,Tc是当前Su的长度,Lmin为MS休眠的最小时间,即紧随当前Su的逻辑广播信道#j及其相邻时隙区间Sj的长度之和.这是因为该逻辑广播信道及其相邻时隙区间中的时隙不能分配给Cu中的MS i,因此,MS i的休眠时间必须大于Lmin才能保证其服务质量,这就是条件(9c)的含义.目标函数(9a)代表调度的目标是使MS i

(i=1,…,K)的总休眠时间最长.条件(9b)的意义是保证本次调度为这K个MS分配的时隙总数等于当前Su的长

3202

度.根据式(7),条件(9b)可以用ri表示如下:

Journal of Software 软件学报 Vol.19, No.12, December 2008

∑i=1ri=(Tc⋅ci)

目标函数(9a)的等价函数为

Lsw+ ∑i=1Rimin.

Rimin

min (fr) = ∑r (9a′)

i=1i

可以证明,以(9a′)为目标函数的非线性优化问题(9)是一个凸规划问题(决策变量为r1,r2,…,rK),这类问题可

以通过内点法[11]有效地解决.为使用内点法,需要先寻找优化问题(9)的一个严格可行解[11].设

r(0)=(b1+δ, +b2δ, ..., bK−1+δ, bK+δ)T,

其中,bi = (RiminLsw)(Lsw−Lmin),δ=(Tc⋅ci)Lsw+ ∑i=1(Rimin−bi)

)K.如果δ≤0,则表示系统已经超负荷,不能满

足每个MS的服务质量要求,此时问题(9)不存在可行解,这种情况可以通过系统的接纳控制等机制避免.除此异常情况以外,r(0)始终是问题(9)的严格可行解,因此可以基于r(0)利用内点法求得优化问题(9)的最优解r*.

利用式(7)可以将r*转换为在本次调度中需要分配给MS的时隙数di(i=1,…,K).但依此求出的di可能不是整数,因此需要将di取整,可直接采用四舍五入的方法.di取整后,若∑i=1di>Tc,则本算法通过减少分配给休眠时间最长的MS的时隙数来满足条件(9b),否则直接将取整后的di(i=1,…,K)作为最终的时隙分配结果.

基于突发传输思想和上述为MS应分配时隙数的计算方法,给出在一个Su中应用LSDB调度算法的步骤:

1) 从Cu中选择需要在当前Su内调度的MS,假设选择结果为MS i(i=1,…,K).hi代表本次调度中已经为MS

i分配的时隙数,n代表已经完成调度的MS的数量,Tu代表当前调度时隙.在调度开始时,n=0,hi=0,Tu为Su的开始时隙.

2) 计算优化问题(9)的最优解r*,根据r*计算di (i=1,…,K),并在限制条件(9b)和(9c)下将di (i=1,…,K)取整. 3) 选择当前未完成调度的MS中最晚醒来时间最小的MS,设为MS j.

并将MS j置于休眠状态,然后执行步骤7);否则执行 4) 如果hj≥dj,则已经完成对MS j的调度,更新tawakej

步骤5).

(i≠j)小于Tu,则将当前时隙分配给MS i,设置hi=hi+1,Tu=Tu+1,并更新tawake,然后执行步 5) 如果存在tawakejj

骤4);否则执行步骤6).

6) 将当前时隙分配给MS j,设置hj=hj+1,Tu=Tu+1,然后执行步骤4)进行下一个时隙的分配. 7) n=n+1.如果n=K,则本次调度完成,算法结束;否则执行步骤3).

此外,若系统中没有多播业务,则所有的MS均属于单播调度集合,仍可以采用LSDB算法来降低系统能耗.此时,优化问题(9)将不包括条件(9c),Tc为系统参数.其解决方法可以较容易地获得,这里不再赘述. 2.4 SSBIS算法

SSBIS算法的核心思想是将系统中所有的MS划分到不同的多播调度集合和单播调度集合中,针对多播调度集合中的MS在相邻时隙区间内进行调度,针对单播调度集合中的MS采用LSDB算法进行调度.

基于此核心思想,给出完整的SSBIS算法如下:1) 在调度开始时,首先根据第2.2节给出的调度集合划分方法将所有MS划分到多播调度集合Cj(j=1,2,…,G)或单播调度集合Cu中,并为Cj(j=1,2,…,G)确定调度方法Aj,Aj为Cj中的每个MS分配相邻时隙区间Sj上连续的时隙,应分配的时隙数量根据式(8)计算.除非多播业务组j发生改变,否则Aj始终保持不变.2) 对于每个调度周期,如果t∈Su,则根据LSDB调度算法为Cu中的MS分配时隙;如果t∈Sj,则采用调度方法Aj为Cj中的MS分配时隙;否则调度多播业务#j的数据.其中,t代表当前调度时隙,每个时隙分配完毕后则指向下一个时隙.

3 算法仿真与分析

本节将通过仿真实验来验证SSBIS算法的性能及多播业务传输情况对算法的影响.仿真系统基于IEEE

802.16e协议,包括一个BS和多个MS组成的一个小区.无线带宽为5Mbps,帧长为5ms,每帧包含200个时隙.

田霖等:基于调度集合的多播单播数据联合调度算法

3203

仿真中,终端上同时存在多播业务和有最小数据速率要求的单播数据业务,单播数据的到达遵从泊松分布,MS上单播数据业务的最小数据速率要求为10kbps~40kbps.默认情况下,每个多播业务组包括4个MS.根据文献

[10]的测量和计算结果,本仿真实验中假设MS处于空闲状态、清醒状态和从休眠状态转换到清醒状态这3种情况下在每个时隙上的平均能耗相等,且每次状态转换将消耗两个时隙单位的能量. 3.1 SSBIS算法的能耗效率

本文利用文献[5]中定义的AEE(average energy efficiency)来衡量能耗效率,AEE是终端用于数据传输的能耗与总能耗的比值.图4给出SSBIS算法和LVBF算法[5]在系统中存在不同数量的MS情况下的AEE值(此时系统中存在2个多播业务组).从图4可以看出,在能耗效率方面,SSBIS算法与LVBF算法相比提高20%以上.这主要存在3个原因:一是SSBIS算法充分利用了逻辑广播信道的相邻时隙,减少了MS状态转换的次数,因此

SSBIS算法中状态转换次数小于LVBF算法;二是在SSBIS算法中,一旦MS的预期空闲时间达到一定阈值,就进入休眠状态,而LVBF算法中总是有一些MS长时间处于空闲状态,因此,SSBIS算法相对于LVBF算法减少了MS的空闲时间;三是SSBIS算法通过凸优化方法求得的时隙分配方案使单播调度集合中所有MS的总休眠时间长于采用LVBF算法的休眠时间.以上3个原因是由SSBIS算法的两个主要组成部分,即针对多播调度集合的相邻时隙区间调度方法及针对单播调度集合的LSDB算法带来的.图5给出利用相邻时隙区间调度多播调度集合中MS的数据及采用LSDB算法分别为能耗效率带来的提高(与LVBF算法相比).在该仿真实验中,为分别得出这两部分对能耗效率的影响,本文首先为单播调度集合采用LVBF算法,只利用相邻时隙区间调度多播调度集合中MS的数据,得到其为能耗效率带来的提高;然后为单播调度集合采用LSDB算法,从而得到SSBIS算法相对于LVBF算法在能耗效率方面总的提高值,两个提高值之差即为LSDB算法为能耗效率带来的提高.如图5所示,利用相邻时隙区间调度多播调度集合中MS的数据对能耗效率的提高约占SSBIS算法总的能耗效率提高量的40%~60%.

LSDB

Adjacent interval

∆AEE User number

Fig.4 AEE vs. number of MSs Fig.5 ∆AEE vs. mumber of MSs

图4 能耗效率(AEE) vs. MS数目图5 能耗效率提高值(∆AEE) vs. MS数目

3.2 业务共存情况对能耗效率的影响

单播业务与多播业务的不同共存情况将决定多播调度集合的划分,从而影响SSBIS算法的能耗效率.本质上,单播业务与多播业务的共存情况是通过系统中多播业务的数量(即多播业务组数量)、接收每个多播业务的

MS个数及MS对单播业务的最小数据速率要求来决定多播调度集合划分的.例如,系统中多播业务组的个数一定,而接收每个多播业务的MS个数较少,从而造成每个多播调度集合中的MS个数较少,则可能无法充分利用相邻时隙区间进行调度,限制了SSBIS算法对能耗效率的提高程度.下面将通过仿真实验验证以上3个因素对

SSBIS算法能耗效率的影响.

3204

Journal of Software 软件学报 Vol.19, No.12, December 2008

图6给出了系统中多播业务组数量对SSBIS算法能耗效率的影响.该实验场景下共存在32个MS.由图6可知,随着系统中多播业务组个数的增加,AEE值基本呈上升趋势.这是由于,当系统中存在更多的多播业务组时(但未超过系统容量),逻辑广播信道数量增加,将会有更多的MS可以在逻辑广播信道的相邻时隙区间内完成调度,达到其最小能耗值,即多播调度集合中MS增多,从而提高了系统的能耗效率.但这种趋势不是绝对的,如图

6所示中,当多播业务组个数为5时,其AEE值反而小于多播业务组个数为4时的值.原因是,随着多播业务组个数的增加和逻辑广播信道数量的增多,超帧长度增大(即Tj变大),根据式(8),相邻时隙区间内需要分配给每个

MS的时隙数增加,可能导致能够在相邻时隙区间内完成调度的MS数量减少.在此仿真实验中,当多播业务组个数为4时,每个相邻时隙区间可以调度3个MS,因此所有多播调度集合中MS的总数为12;而当多播业务组个数为5时,每个相邻时隙区间只能调度2个MS,则所有多播调度集合中MS的总数为10,因此,其AEE值小于多播业务组个数为4时的值.同理,随着多播业务组个数的增加,其AEE值的增加幅度将减小,这由图7可以清楚地看出:多播业务组个数为2(G=2)时的AEE值与多播业务组个数为4(G=4)时的AEE值之差、多播业务组个数为4时与多播业务组个数为6(G=6)时的AEE值之差、多播业务组个数为6时与多播业务组个数为8(G=8)时的AEE值之差依次减小.

G G G

Fig.6 AEE vs. multicast service group number Fig.7 Comparison of AEE with different multicast service group number

图6 能耗效率vs.多播业务组数量图7 不同多播业务组数量下能耗效率比较图8给出在多播业务组个数不变、而接收每个多播业务的MS个数发生变化时,SSBIS算法的性能变化.

场景1中每个多播业务组包括2个MS,场景2中每个多播业务组包括4个MS,场景1和场景2中均存在2个多播业务组.由图8可知,当在系统中存在数量相同的MS时,场景2中AEE值总是高于场景1,这同样是由多播

Scene1Scene2

调度集合中MS的个数不同所导致.在多播业务组个数和MS的服务质量要求确定的情况下,每个逻辑广播信道的相邻时隙区间可调度的MS数量也已确定,若某多播业务组中MS的个数小于该数量,则对应多播调度集合中MS的数量将不能达到最大值,使足够多的MS达到其能耗最小值.例如,该仿真中,每个逻辑广播信道的相邻时隙区间最多可以调度4个MS,但场景1中接收每个多播业务的MS只有2个,因此不能充分利用相邻时隙区间,导致其能耗效率始终低于场景2.在该仿真中,场景1与场景2中MS的最小数据速率要求相同.若MS的最小数据速率要求不同,则即使两个场景中多播业务组包含的MS个数相同,可在逻辑广播信道的相

Fig.8 Effect of users in multicast service group 图8 多播业务组中终端数量对能耗效率的影响

田霖等:基于调度集合的多播单播数据联合调度算法

3205

邻时隙区间内完成调度的MS个数仍将不同.但这种情况与图8仿真的本质是一致的,即多播调度集合中MS个数的不同对能耗效率的影响,因此本文不再进行额外的仿真.

从本节的仿真实验中可以看出,若系统中多播业务组的数量较少,接收每个多播业务的MS个数较少,或接收多播业务的MS的最小数据速率要求较高,都将导致属于多播调度集合的MS总数减少,从而减少由相邻时隙区间调度带来的能耗效率提高量.但由图5的仿真可知,SSBIS算法的能耗效率提高不仅是由针对多播调度集合的相邻时隙区间调度方法带来的,还包括针对单播调度集合的LSDB算法带来的能耗效率提高.因此,即使在多播调度集合中MS的总数很小时(例如,图6中多播业务组个数为1时,其能耗效率约为0.6),SSBIS算法的能耗效率也明显高于LVBF算法(此时,其能耗效率约为0.4). 3.3 SSBIS算法对最小数据速率的保证

首先,本文定义平均QoS保证率(average QoS guarantee rate,简称AQGR)为保证了服务质量的MS数量与系统中MS总数的比值,通过计算每个时隙中达到了最小数据速率的MS数量与系统中MS总数的比值,然后求一段时间内的平均值即为AQGR.图9给出在系统中存在不同数量的MS情况下的AQGR仿真结果(此时系统中存在2个多播业务组).可以看出,当系统中不超过40个MS时,AQGR始终超过99%;而当系统中不超过15个MS时,AQGR为100%.实际上,由于平均数据速率的统计粒度远大于AQGR的统计粒度(时隙),因此,即使

AQGR不是100%,每个MS的平均数据速率也可能满足服务质量要求中定义的最小数据速率.图10给出了当系统负载增加时有不同服务质量要求的MS的平均数据速率变化情况,图中3个MS的最小数据速率要求分别为20kbps,30kbps和40kbps,系统中其他所有MS的最小数据速率要求均为30kbps.如图10所示,3个MS的数据速率始终大于其最小数据速率要求,并随着系统中MS总数量的增加而降低,将一直降低到其预定义的最小数据速率.这是由于SSBIS算法会在每个时隙都检查是否有MS的服务质量要求没有得到满足,并尽快地为未满足服务质量要求的MS分配时隙,因此只要系统未超负荷,SSBIS算法就可以保证终端的最小数据速率要求.

Fig.10 Average data rate vs. number of MSs 图10 终端的平均数据速率vs. MS数目

Fig.9 AQGR vs. number of MSs

图9 平均QoS保证率(AQGR) vs. MS数目

4 结束语

本文首先提出了目前IEEE 802.16e网络相关研究中未定义过的一个新问题,即如何在单播业务和多播业务共存的情况下降低系统能耗,同时保证MS的服务质量.然后,提出一种基于调度集合的联合调度算法(SSBIS)来解决该问题.SSBIS算法将所有MS划分到不同类型的调度集合中,并根据调度集合的特点设计不同的调度策略,以提高单播业务和多播业务共存的802.16e系统的能耗效率.仿真结果显示,SSBIS算法在保证MS最小数据速率的同时,显著降低了系统总能耗.进一步的工作将考虑终端上不同类型业务的服务质量要求,以完善SSBIS算法设计.

3206

References:

Journal of Software 软件学报 Vol.19, No.12, December 2008

[1] IEEE Standard 802.16 Working Group. IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed

and Mobile Broadband Wireless Access Systems, 2005.

[2] Xiao J, Zou S, Sun Y, Ren B, Cheng S. An enhanced energy saving mechanism in IEEE 802.16e. In: Proc. of the IEEE

GLOBECOM 2006. San Francisco: IEEE Press, 2006. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4151344

[3] Han K, Choi S. Performance analysis of sleep mode operation in IEEE 802.16e mobile broadband wireless access systems. In: Proc.

of the IEEE VTC 2006-Spring. Melbourne: IEEE Press, 2006. 1141−1145.

[4] Jang J, Han K, Choi S. Adaptive power saving strategies for IEEE 802.16e mobile broadband wireless access. In: Proc. of the

Asia-Pacific Conf. on Communications. Busan: IEEE Press, 2006. 1−5. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber= 4023113

[5] Shi J, Fang G, Sun Y, Zhou J, Li Z, Dutkiewicz E. Improving mobile station energy efficiency in IEEE 802.16e WMAN by burst

scheduling. In: Proc. of the IEEE GLOBECOM 2006. San Francisco: IEEE Press, 2006. http://ieeexplore.ieee.org/xpls/abs_all.jsp? arnumber=4151343

[6] Cohen R, Rizzi R. On the trade-off between energy and multicast efficiency in 802.16e-like mobile networks. In: Proc. of the IEEE

INFOCOM’06. Barcelona: IEEE Press, 2006. http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4146799& isnumber=4146653 [7] Havinga PJM, Smit GJM, Bos M. Energy-Efficient adaptive wireless network design. In: Proc. of the IEEE ISCC 2000. IEEE Press,

2000. 502−507.

[8] Jones CE, Sivalingam KM, Agrawal P, Chen JC. A survey of energy efficient network protocols for wireless networks.

ACM/Baltzer Journal on Wireless Networks, 2001,7(4):343−358.

[9] Andrews M, Qian L, Stolyar AL. Optimal utility based multi-user throughput allocation subject to throughput constraints. In: Proc.

of the INFOCOM 2005. Miami: IEEE Press, 2005. 2415−2424.

[10] Cui S, Goldsmith AJ, Bahai A. Energy-Constrained modulation optimization. IEEE Trans. on Wireless Conmmunications,

2005,4(5):2349−2360.

[11] Boyd S, Vandenberghe L. Convex Optimization. Cambridge. Cambridge University Press, 2003. 561−615.

田霖(1980－),女,硕士,主要研究领域为宽带无线通信MAC层,无线资源管理.

石晶林(1972－),男,博士,研究员,主要研究领域为下一代网络,无线通信.

杨育波(1981－),男,硕士,主要研究领域为宽带无线通信系统及信号处理技术, MIMO调度.

DUTKIEWICZ Eryk(1964－),男,博士,教授,主要研究领域为移动网络服务质量保证机制,移动计算.

方更法(1976－),男,博士,主要研究领域为调度算法,移动网络服务质量保证机制.

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文