搜索
您的当前位置:首页适用于全IP移动通信系统的比例资源调度算法

适用于全IP移动通信系统的比例资源调度算法

来源:飒榕旅游知识分享网
维普资讯 http://www.cqvip.com 第28卷第6期 2 0 0 6年12月 铁 道 学 报 Vo1.28 No.6 JOURNAL OF THE CHINA RAILWAY SOCIETY December 2006 文章编号:IOOl一8360(2006)06—0079—04 适用于全IP移动通信系统的比例资源调度算法 赵 红 礼 (北京交通大学电子信息工程学院,北京 100044) 摘要:未来的全IP移动通信系统能够提供多种不同QoS要求的业务,资源调度对保证QoS和提高资源利用 效率起关键作用 动态规划方法可以求解满足QoS保证的最优调度,但是它对运算速度和存储容量要求很高, 难以在实际中应用。为此本文提出一种比例资源调度算法,将QoS保证映射为接纳控制阶段的比例资源分配。 由子信道的相关特性已经在接纳控制阶段进行了考虑,而且资源分配比例是时不变的,因此将动态规划问题简化 为线性规划问题。文中采用吞吐量最大化调度作为比较基准,仿真了比例资源调度算法的性能,结果表明:由动 态规划转化为线性规划带来的性能损失很小,另外当平均信噪比较小时,调度增益较大,并且调度增益随用户数 的增加而增大。 关键词:比例资源调度,QoS;动态规划方法 中圈分类号:TN929.5 文献标识码:A Proportion Resource Scheduling Algorithm Suitable for IP Mobile Telecommunication System ZHAO Hong—li (School of Electronics and Information Engineering, Beijing Jiaotong University,Beijing 100044,China) Abstract:Future mobile telecommunication will be all—IP—based,it can provide different QoS services.Radio re— source scheduling plays a key role in guaranteeing QoS and enhancing utilizing efficiency of radio resources. The dynamic programming method can figure out the best scheduling to guarantee QoS.But it is difficult to use in practice because it requires very high operation speeds and big memory capacity.So this paper proposes a proportion resource scheduling algorithm,it can map QoS guarantee to proportion resource distribution in the phase of call admission contro1.Owing to the fact that the specialties of channels have been considered in the phase of call admission control,and the proportion of resource distribution is not changed by time,dynamic programming is simplified into linear programming.This paper simulates the performance of the proportion re- source scheduling algorithm,by adopting the best throughput scheduling as the benchmark.The result indi— cates:The performance loss is very small by transforming dynamic programming to linear programming;the scheduling gain is large when the average SNR is small。and the scheduling gain is enhanced by the increase of users. Key words:proportion resource scheduling;quality of service(OoS);dynamic programming method 未来的移动通信(bey0nd3G/4G)系统将采用全 理算法能有效进行负荷控制和资源调度,充分发掘不 IP端刊端结构,空中接口也将基于分组交换,它能够 同的业务特征和无线链路特性,尽可能满足多种业务 提供多种业务并保证各类业务的QoS。但多业务分 的不同质量要求并使系统吞吐量最大化。目前无线资 组无线通信系统存在许多随机因素,另外无线链路的 源调度领域的研究大多集中在单服务器模型上[卜引。 传输具有位置和时间相关特性,这就要求无线资源管 对于无线网络来说,单服务器模型的主要适用对象是 段稿日期:2005—07 15:修回日期:2005—10-20 TDMA和Slotted-CDMA系统。但是在未来的全IP 作者筒介:赵红¥L(1973--),男,河南兰考人,硕士,讲师。  ̄mall:1iwyzhao@126.colll 移动通信系统中,基站可以利用多个信道同时为多个 分组提供服务,属于并发服务系统。对于CDMA系统 维普资讯 http://www.cqvip.com 8O 铁 道 学 报 第28卷 中的分组调度而言,多服务器和多链路状态是两个重 QoS的限制条件下,最小化时间平均信道利用率。最 小化在集合{ (f))中进行,如下式所示 1 N K 要问题,目前这方面的研究工作仍然很少[ ,多服务器 和多链路状态资源调度面临的高复杂度,是研究中面 临的主要困难之一。 min÷∑ ∑∑ (£)] 。l=O H!l^一1 (3) 本文对并发服务系统中的无线资源调度进行了研 约束条件为 究,提出了一种比例资源调度算法,通过在接纳控制阶 段进行固定比例资源分配,可以将动态规划问题转化 为线性规划问题。分析表明,均匀分配是接纳控制阶 段的最优资源分配方法。 1面向Oos保证的资源调度 已有研究表明单信道和多信道中采用多用户分集 可以使系统容量最大化,多用户分集所对应的选取最 优用户进行调度的方式,称为吞吐量最大化调度 ]。 但吞吐量最大化调度只根据信道的变化情况进行调 度,而没有体现用户各自不同的服务质量需要,因此只 适合提供非QoS保证类服务。 面向QoS的最优调度应该在满足用户QoS要求 的前提下,尽量减少资源的占用。为了便于讨论,假设 数据传输采用流模型,即下行信道帧可以在多个用户 之间共享,基站可以在每一个信道帧中为用户分配不 同比例。以C (£)(bits/symbo1)表示信道 中用户愚 的信道容量;以 , (£)(O≤ , (£)≤1)表示基站在 帧/时隙t,为用户矗在信道 中实际分配的容量比例, 该容量用于Q0S保证,它只与{Ck。 (£),愚≤K)有关。 对于每个信道 ,其剩余容量全部按照吞吐景最大化 调度分配给非QoS保证用户,从而在QoS保证的基 础上,提高系统的资源利用效率。设非QoS保证用户 和K个QoS保证用户的信道增益独立,则可利用剩 余容量c 的期望为 N K E(C ):E[∑(1一∑∞ (£))cK+ (£)] n一1 ^一1 (1) 式中,CK (£)为信道押中具有最大信道增益的非 QoS保证用户的容量,它独立于{ . (£),愚≤K),因此 也独立于{ . (£),惫≤K)。对多天线系统,可认为各 信道增益同分布,因此E[CK+。. (£)]一 CK+ (£)],式 (1)可表示为 Ⅳ K E( ) ∑[(;= 1一E[∑叫 (£)])E[ 。. (£)]]一 Ⅳ K EECK. (£)]×(N—El-∑∑ .^ l上E1  (£)])(2) Ⅳ K 当E[∑∑ .;  (£)]最小时,剩余容量 最大。 可以得到面向QoS保证的最优调度为在满足用户 K ∑ (£)≤1 V佗 (4) 同时 N P{∑ (£) 。 (£)> )≥1一占 y k(5) 式(5)要求为每个用户所分配的 N ∑ (t)Ck. (£) 可以保证该用户的统计性QoS。其中,C 为满足用 户愚的QoS要求所需要的容量;艿为给定的QoS坏损 概率。常用的统计性QoS要求包括最小速率和最大 时延两种,在这里采用最小速率描述QoS,以R表示 用户愚要求的最小速率, 表示容量的实际利用效率。 为了满足式(5)中每个用户的QoS要求,需要保证 Ⅳ P{∑ (£) . (f)>Rk/17)≥1一 V矗 =1 (6) 在上述最优化调度中,为了满足K个用户的QoS 要求,对每一个用户,调度器都需要用一个状态变量对 该用户得到的服务总量进行跟踪,并在每帧中根据当 前的状态,按照最小化时间平均信道利用率的要求,进 行TM.k。 (£)资源调度。对于这类多阶段的最优化问题, 动态规划是自然的求解方法。但是动态规划问题计算 的复杂性,使得这样的最优调度不具有实用价值。 2基于比例资源分配的调度 文献[7]提出了一种M—LWDF调度算法,该调度 算法利用接纳控制对提供QoS保证的可行域进行限 制。在此可行域内,通过简单队列加权的方法寻求优 化某个QoS参数,例如吞吐量。这种方法启发我们可 以利用接纳控制的限制来简化上述最优调度,寻找一 种局部最优方法来得到较高的信道利用率 根据这个思路,可以假设在接纳控制阶段,系统采 用了一种简单的比例分配方法:对用户愚在信道 中 预留非时变的固定比例信道容量口( , ∈[o,1]),使 得用户愚所拥有的时变信道容量 。。。。——ak,.C (£)满足 n=l 其QoS要求 L P{ : , (£)Ck. (£)>R^/'7)≥1一占V愚(7) 维普资讯 http://www.cqvip.com 第6期 适用于全IP移动通信系统的比例资源调度算法 81 式中,∑ , <1,V n。通过比例接纳控制假设,满 调度的状态变量需要包含N×K个衰落信道的状态 信息,由于大量状态信息的存在,动态规划对于计算速 足用户QoS要求的任务被归于接纳控制阶段,利用资 度和存贮容量的要求很高;而基于比例资源分配的调 源的比例分配来保证QoS。由于QoS限制已经包含 度器不需要这样做,因为信道的衰落已经在接纳控制 在固定的分配比例{ . )中,因此,QoS约束条件可以 中考虑了。这样一个动态规划问题就简化为线性规划 表示为 问题,可以通过单纯型法和多项式法求解,复杂度将明 N N ∑ (^正1 t)Ck, ( )≥∑ ,n一1  (z)C^, ( ) V k 显降低。 (8) 3性能比较和仿真 式(8)表明,在每一个时刻t,只要调度器分配给用户 N 因为吞吐量最大化调度是系统容量的上限,所以 五的容量不少于∑ ,1  (t)Ck, ( ),就可以保证约定的 采用吞吐量最大化调度的调度增益L 作为比较基 一统计性QoS。利用式(8),基于比例资源分配的调度 准,评判基于比例资源分配的调度器的性能。在仿真 器的优化问题总结如下 中假设:(1)信道增益服从指数分布,各信道独立同分 布,且信道增益在各帧之间相互独立;(2)调度器可以 min∑∑ ,确知每帧中信道增益{g (z))和信道容量{Ck. ( ))。 ^ 1 1  ( ) (9) 约束条件为 3.1调度增益与平均SNR K 调度增益与平均SNR的关系如图l所示。图中 ∑ (1  )≤1 V (10) “一single”和“equal”分别表示单信道分配和均匀信道分 N N ∑ (t)Ck. ( )≥∑ (t)Ck ,( ) Y k 配情况。从图1可以发现,当平均SNR从一20dB增 加到15dB时,用户数K越大,调度增益下降越快。当 (11) 平均SNR较高时,即使选择信道条件最好的用户进 这种在接纳控制阶段先进行固定资源分配的调度 行传输,也很难得到比较大的调度增益。此外,均匀信 方法可以称为基于比例资源分配的调度。与最优调度 道分配可以带来比单信道分配更大的调度增益。 进行比较可以发现:如果不同的帧之间是相关的,最优 轷 轷 霉 照 一2O —l5 —1O -5 0 5 10 15 平均SNR/dB 平均SNRldB (a)K=4,8 (b)K=32,64 图1调度增益和平均SNR的关系 3.2调度增益与用户数 加到64时,调度增益随之增加。另外在各种情况下, 在不同SNR下,调度增益和不同用户数的关系 调度增益曲线都和基准曲线L 相差很少,表明基于 如图2所示。图中“single”和“equal”与图1同, 比例资源分配的调度性能已经非常接近于吞吐量最大 “benchmark”表示作为比较基准的吞吐量最大化调度 化调度器的性能,从而说明由动态规划转化为线性规 的调度增益L 。从图2可以发现,当用户数从2增 划过程中带来的性能损失是相当小的。 维普资讯 http://www.cqvip.com 82 铁 道 学 报 第28卷 辩 露 磬 娶 用户数 (a)平均SNR=-20 dB 用户数K (b)平均SNR=O dB 图2调度增益和不同用户数的关系 algorithms to wireless networks[Al1.In:ACM/IEEE MO‘ 4 结论 在全IP移动通信系统中,基于最小化信道使用率 分析,得到满足QoS保证的最优调度的表示形式。动 BIC0M’98[C].Dallas。TX.1—9. [3]Shakkottai S,Srikant R.Scheduling real—time traffic with deadlines over a wireless channel[A].In:Proc.ACM w0Mw0M’99[C].Seattle:WA,1999.35—42. [4]Yaxin Cao,Victor 0 Li.Scheduling Algorithms in Broad— band Wireless Networks[J].IEEE Proceedings of the IEEE。2001,89(1):77—87. 态规划方法理论上最适合求解此最优化问题,但是由 于它对于运算速度和存贮容量要求很高,难以在实际 中运用。为此本文提出了一种基于比例资源分配的调 度方法。它的主要思路是将QoS保证映射为接纳控 [5]Knopp R,Humblet P A.Information capacity and power control in single-cell multiuser communications[A].IEEE 制阶段的比例资源分配,这样就可以在接纳控制域上 进行局部最优化。由于信道的相关特性已经在接纳控 制阶段进行了考虑,而且资源分配比例是时不变的,因 此可将一个动态规划问题转化为线性规划问题。 参考文献: International Conference on Communications(ICC95)[C]. Seattle。USA:June 1995.331—335. [6]Tse D.Optimal Power Allocation over Parallel Gaussian Broadcast Channels[A].In:IEEE Trans.Info.Theory [C].ULM,GERMANY.1997:27. [7]Andrews M,Kumaran K,Ramanan K,Stolyar A,et a1. [1]Lu S,Bharghavan V.Fair scheduling in wireless packet networks[J:】.IEEE/ACM Trans.Networking,1999,7 (4):473—489. Providing quality of service over a shared wireless link[J]]. IEEE Communications Magzine,2001,39(2):150--154. (责任编辑江峰) [2-1 Ramanathan P,Agrawal P.Adapting packet fair queueing 

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

Top