基于QoS效用函数的比例公平调度算法

叶 进，刘建涛，林 婧，李陶深

基于QoS效用函数的比例公平调度算法

叶 进1，刘建涛2，林 婧2，李陶深1

(1. 广西大学计算机与电子信息学院，南宁 530004；2. 桂林电子科技大学信息与通信学院，广西 桂林 541004)

比例公平调度算法应用于多媒体业务调度时，不能满足其多方面的服务质量(QoS)需求，尤其是当有业务的瞬时QoS参数值接近业务可忍受的QoS阈值时，该业务的调度优先级变化趋势不明显，使该业务不能被及时调度，降低了多媒体业务的通信质量。为此，在PF算法调度优先级判断表达式中引入QoS因子参数项，加强服务质量需求参数项对调度的影响，提出基于QoS效用函数的比例公平调度算法。实验结果证明，该算法可以迅速增加接近QoS阈值多媒体业务的调度机会，使VoIP业务的平均延时降低44%、公平性提高3%。

服务质量；调度算法；效用函数；比例公平；时延；吞吐量

1 概述

随着无线网络的飞速发展，无线网络资源匮乏与数据业务需求增加之间的矛盾日益尖锐，在无线网络资源无法增加的前提下，无线资源的调度算法成了一个突破方向[1]。目前，经典的调度算法主要有轮询调度(Round Robin, RR)算法[2]、最大载干比调度(Max Carrier to Interference, Max C/I)算法[3]、比例公平调度(Proportional Fair, PF)算法[4]。RR算法是在时间片上轮流地调度各个业务，即系统中所有业务有相同的调度优先级，保证以相等的机会为系统中所有业务分配相同数量的资源(时间或者带宽)，并且使用户按照某种约定的顺序依次调度，直到所有业务都被调度后进入下一个调度循环。Max C/I算法是一种强调系统吞吐量的调度方式，它根据信道信噪比将系统中的所有用户降序排序，系统优先调度信噪比大的业务，直至调度结束。RR算法为了用户最大公平性而牺牲系统的吞吐量，相反Max C/I调度算法为了最大的系统吞吐量而牺牲了用户公平性，它们都只按照某一个性能指标进行调度，而忽略了其他的性能指标，限制了它们在实际系统中的应用[5]。为了改善这个问题，Jalali提出了PF调度算法，该算法既考虑了业务的实时信道状态又考虑了业务传输速率之间的公平性，初始时刻每个业务的优先级都附为相同值，每次调度时总是优先调度优先级高的，但是随着某个信道质量好的业务被连续调度后，其平均吞吐量会增大，从而导致其调度优先级降低，这样就使原来低优先级的用户可以获得更多的调度机会，增加了调度算法的公平性[6]。针对比例公平调度算法在多媒体业务调度时不能满足其多方面的服务质量(Quality of Service, QoS)需求，本文提出一种基于QoS效用函数的比例公平调度算法。

2 比例公平调度算法

2.1 PF算法的不足

虽然PF算法在系统吞吐量和公平性上取得了较好的折中，使其广泛地应用在实际系统中[7]。但由于近年来无线网络中多媒体业务呈指数型增长，PF算法有2个问题：(1)不能满足业务多方面的QoS需求。(2)缺乏自适应的优先调度，即当有业务的QoS值接近最大QoS阈值时调度优先级变化趋势不明显，使该业务不能被及时调度从而造成时延超时影响业务的通信质量。所以，本文在PF算法的调度优先级中引入了基于效用函数的QoS因子(时延、丢包率、时延抖动等业务QoS需求的集合)参数项，当多媒体业务QoS因子接近最大QoS阈值时，该参数项可以迅速增加业务的调度机会，从而保证多媒体业务的通信质量。

2.2 PF-A算法的基本原理

、对()的影响如图1所示。

图1 a、c与效用函数值U(t)的关系

2.3 PF-A调度算法

本文基于以上理论提出基于服务质量效用函数的调度(PF-A)算法。PF-A算法的调度优先级定义为：

本文提出的PF-A算法考虑业务QoS需求对任务调度的影响，任务调度优先级取值与服务质量效用函数、信道状态、业务的平均吞吐量有关，最后取式(2)作为优先级的更新表达式。综上所述，本文提出的PF-A调度算法的工作步骤如下：

(3)根据式(2)计算业务的调度优先级，并按降序排列。

(4)依次调度优先级最大的业务，直至资源分配完。

(5)重复步骤(2)~步骤(4)，直到调度完成。

3 仿真结果与分析

3.1 业务模型

3.2 信道模型

无线信道的不稳定性会给传输时延和时延抖动带来很大的影响，为了更方便地测量时延，本文的无线信道模型采用四状态FSMC信道，FSMC信道状态只允许在相邻状态转换。信道状态转换参数为=0.2(信道状态由好变为不好的概率)，=0.3(信道状态由不好变为好的概率)，信道状态维持不变1-状态改变之和(最好信道为、最差信道为批，其他信道为+。

3.3 算法仿真

为了验证PF-A算法在服务实时业务(本文的VoIP业务)时的优点，本文对PF、DRC、APF算法和基于服务质量效用函数的PF-A算法从公平性、系统吞吐量、业务时延3个方面进行了性能对比。

本文采用Jain’s公平性准则[12]，从图2看出，PF-A算法的公平性大于其他PF算法，且几种算法的公平性都随着调度次数的增加而增加。公平性随调度次数增加而变好主要是调度次数越大，系统业务的吞吐量越趋于平衡(因为PF算法都照顾信道条件不好的业务)，所以系统公平性变好。而PF算法公平性大于其他算法是因为PF-A算法考虑了业务时延对调度优先级的影响，更加兼顾信道质量差的业务(信道质量差，相同的无线资源发送的数据量小业务延时大)使业务的吞吐量更加趋于平衡进而使Jain’s公平性最大。

图2 Jain’s公平性

从图3看出，PF-A算法的时延明显小于PF、 DRC、APF 3种算法，主要是PF-A算法在调度优先级中加入了时延因子，从而更兼顾信道质量差的业务，使业务时延降低44%。证明PF-A算法适用于具有时延约束的多媒体业务。

图3 算法时延

PF、DRC、APF、PF-A算法的系统吞吐量分别为 7 201 Kb/s、7 363 Kb/s、7 419 Kb/s、6 933 Kb/s。PF-A算法的吞吐量比PF算法大概低4%，主要是PF-A算法考虑业务的QoS时延因素，增加信道质量较差业务的调度机会，在相同情况下传输较少的数据，从而导致系统吞吐量降低。

4 结束语

本文提出一种基于服务质量效用函数的比例公平调度算法，设计思想是在PF算法的调度优先级判断表达式引入与服务质量相关的参数项。仿真结果表明，该算法通过效用思想改进了实时业务的调度机会，以牺牲小部分系统吞吐量降低VoIP业务的时延，并提高了系统公平性。下一步研究的重点是在吞吐量损失和多媒体业务服务质量保证之间取得更好的折中。

[1] 袁东风, 张海霞, 马艳波. 无线通信跨层设计——从原理到应用[M]. 北京: 人民邮电出版社, 2010.

[2] Xian Yongju, Tian Fengchun, Xu Changbiao. Analysis of M-LWDF Fairness and an Enhanced M-LWDF Packet Scheduling Mechanism[J].The Journal of China Universities of Posts and Telecommunications, 2011, 18(4): 82-88.

[3] Driouch E. Efficient Scheduling Algorithms for Multi-antenna CDMA Systems[J]. IEEE Transactions on Vehicular Tech- nology, 2012, 61(2): 521-532.

[4] Data J A. Throughput of CDMA-HDR a High Efficiency-high Data Rate Personal Communication Wireless System[C]//Proc. of Vehicular Technology Conference. Tokyo, Japan: [s. n.], 2000: 206-210.

[5] Marques A G. Optimal Cross-layer Resource Allocation in Cellular Networks Using Channel and Queue State Infor- mation[J]. IEEE Transactions on Vehicular Technology, 2012, 61(6): 2789-2807.

[6] 胡 莹, 黄永明, 俞 菲. 基于能效优化的用户调度与资源分配算法[J]. 电子与信息学报, 2012, 34(8): 1950-1955.

[7] Wang Jun. A Scheduling Algorithm Based on Communication Delay for Wireless Network Control System[J]. Research Journal of Applied Sciences Engineering and Technology, 2012, 20(4): 3891-3895.

[8] 曾宇辉, 朱光喜. LTE系统中提高TCP性能的资源调度算法研究[J]. 小型微型计算机系统, 2012, 33(5): 1018-1022.

[9] 陆巍炜. LTE中QoS调度算法研究[D]. 西安: 西安电子科技大学, 2009.

[10] Zhou Nan, Zhu Xu, Huang Yi. Low Complexity Cross-layer Design with Packet Dependent Scheduling for Heterogeneous Traffic in Multi-user OFDM Systems[J]. IEEE Transactions on Wireless Communications, 2010, 9(6): 1912-1923.

[11] Yang Li, Pan Chengsheng, Liu Haiyan. A New Class of Priority-based Weighted Fair Scheduling Algorithm[J]. Physics Procedia, 2012, 33(5): 942-948.

[12] 冯慧芳, 赵 亮, 陈媛媛. 基于信道状态的WIMAX系统实时调度算法[J]. 计算机应用研究, 2013, 30(1): 60-65.

编辑 索书志

Proportional Fair Scheduling Algorithm Based on QoS Utility Function

YE Jin1, LIU Jian-tao2, LIN Jing2, LI Tao-shen1

(1. School of Comput er and Electronic Information, Guangxi University, Naning 530004, China; 2. School of Information and Communication, Guilin University of Electronic Technology, Guilin 541004, China)

The proportional fair scheduling algorithm in multimedia service schedule does not meet the various Quality of Service(QoS) needs. Especially, when the business instantaneous QoS parameter values are close to the business accepted maximum QoS thresholds, the variation tendency of the scheduling priority of the business is not obvious, and the business can not be timely scheduled and the quality of multimedia business communication is reduced. According to this instance, this paper draws the QoS factor parameters into the algorithm of PF scheduling priority judgments expression. It enhances the impact of scheduling with the demand for QoS parameters. It proposes a proportional fair scheduling algorithm based on the QoS utility function. Experimental results show that the scheduling algorithm can quickly increase scheduling opportunities closed to the multimedia business of the service quality thresholds. Therefore, the delay of the VoIP business is reduced by 44% and the justice of the VoIP business is raised by 3%.

Quality of Service(QoS); scheduling algorithm; utility function; proportional fair; delay; throughput

1000-3428(2014)03-0120-03

A

TP391

国家自然科学基金资助项目(61163060, 61103204)；广西自然科学基金资助重点项目(2011GXSFD01802)。

叶 进(1970－)，女，教授，主研方向：网络协议优化；刘建涛、林 婧，硕士；李陶深，教授。

2013-01-21

2013-03-20 E-mail：yejin@guet.edu.cn

10.3969/j.issn.1000-3428.2014.03.024