基于QoS效用函數(shù)的比例公平調度算法

葉 進，劉建濤，林 婧，李陶深

基于QoS效用函數(shù)的比例公平調度算法

葉 進1，劉建濤2，林 婧2，李陶深1

(1. 廣西大學計算機與電子信息學院，南寧 530004；2. 桂林電子科技大學信息與通信學院，廣西 桂林 541004)

比例公平調度算法應用于多媒體業(yè)務調度時，不能滿足其多方面的服務質量(QoS)需求，尤其是當有業(yè)務的瞬時QoS參數(shù)值接近業(yè)務可忍受的QoS閾值時，該業(yè)務的調度優(yōu)先級變化趨勢不明顯，使該業(yè)務不能被及時調度，降低了多媒體業(yè)務的通信質量。為此，在PF算法調度優(yōu)先級判斷表達式中引入QoS因子參數(shù)項，加強服務質量需求參數(shù)項對調度的影響，提出基于QoS效用函數(shù)的比例公平調度算法。實驗結果證明，該算法可以迅速增加接近QoS閾值多媒體業(yè)務的調度機會，使VoIP業(yè)務的平均延時降低44%、公平性提高3%。

服務質量；調度算法；效用函數(shù)；比例公平；時延；吞吐量

1 概述

隨著無線網(wǎng)絡的飛速發(fā)展，無線網(wǎng)絡資源匱乏與數(shù)據(jù)業(yè)務需求增加之間的矛盾日益尖銳，在無線網(wǎng)絡資源無法增加的前提下，無線資源的調度算法成了一個突破方向[1]。目前，經(jīng)典的調度算法主要有輪詢調度(Round Robin, RR)算法[2]、最大載干比調度(Max Carrier to Interference, Max C/I)算法[3]、比例公平調度(Proportional Fair, PF)算法[4]。RR算法是在時間片上輪流地調度各個業(yè)務，即系統(tǒng)中所有業(yè)務有相同的調度優(yōu)先級，保證以相等的機會為系統(tǒng)中所有業(yè)務分配相同數(shù)量的資源(時間或者帶寬)，并且使用戶按照某種約定的順序依次調度，直到所有業(yè)務都被調度后進入下一個調度循環(huán)。Max C/I算法是一種強調系統(tǒng)吞吐量的調度方式，它根據(jù)信道信噪比將系統(tǒng)中的所有用戶降序排序，系統(tǒng)優(yōu)先調度信噪比大的業(yè)務，直至調度結束。RR算法為了用戶最大公平性而犧牲系統(tǒng)的吞吐量，相反Max C/I調度算法為了最大的系統(tǒng)吞吐量而犧牲了用戶公平性，它們都只按照某一個性能指標進行調度，而忽略了其他的性能指標，限制了它們在實際系統(tǒng)中的應用[5]。為了改善這個問題，Jalali提出了PF調度算法，該算法既考慮了業(yè)務的實時信道狀態(tài)又考慮了業(yè)務傳輸速率之間的公平性，初始時刻每個業(yè)務的優(yōu)先級都附為相同值，每次調度時總是優(yōu)先調度優(yōu)先級高的，但是隨著某個信道質量好的業(yè)務被連續(xù)調度后，其平均吞吐量會增大，從而導致其調度優(yōu)先級降低，這樣就使原來低優(yōu)先級的用戶可以獲得更多的調度機會，增加了調度算法的公平性[6]。針對比例公平調度算法在多媒體業(yè)務調度時不能滿足其多方面的服務質量(Quality of Service, QoS)需求，本文提出一種基于QoS效用函數(shù)的比例公平調度算法。

2 比例公平調度算法

2.1 PF算法的不足

雖然PF算法在系統(tǒng)吞吐量和公平性上取得了較好的折中，使其廣泛地應用在實際系統(tǒng)中[7]。但由于近年來無線網(wǎng)絡中多媒體業(yè)務呈指數(shù)型增長，PF算法有2個問題：(1)不能滿足業(yè)務多方面的QoS需求。(2)缺乏自適應的優(yōu)先調度，即當有業(yè)務的QoS值接近最大QoS閾值時調度優(yōu)先級變化趨勢不明顯，使該業(yè)務不能被及時調度從而造成時延超時影響業(yè)務的通信質量。所以，本文在PF算法的調度優(yōu)先級中引入了基于效用函數(shù)的QoS因子(時延、丟包率、時延抖動等業(yè)務QoS需求的集合)參數(shù)項，當多媒體業(yè)務QoS因子接近最大QoS閾值時，該參數(shù)項可以迅速增加業(yè)務的調度機會，從而保證多媒體業(yè)務的通信質量。

2.2 PF-A算法的基本原理

、對()的影響如圖1所示。

圖1 a、c與效用函數(shù)值U(t)的關系

2.3 PF-A調度算法

本文基于以上理論提出基于服務質量效用函數(shù)的調度(PF-A)算法。PF-A算法的調度優(yōu)先級定義為：

本文提出的PF-A算法考慮業(yè)務QoS需求對任務調度的影響，任務調度優(yōu)先級取值與服務質量效用函數(shù)、信道狀態(tài)、業(yè)務的平均吞吐量有關，最后取式(2)作為優(yōu)先級的更新表達式。綜上所述，本文提出的PF-A調度算法的工作步驟如下：

(3)根據(jù)式(2)計算業(yè)務的調度優(yōu)先級，并按降序排列。

(4)依次調度優(yōu)先級最大的業(yè)務，直至資源分配完。

(5)重復步驟(2)~步驟(4)，直到調度完成。

3 仿真結果與分析

3.1 業(yè)務模型

3.2 信道模型

無線信道的不穩(wěn)定性會給傳輸時延和時延抖動帶來很大的影響，為了更方便地測量時延，本文的無線信道模型采用四狀態(tài)FSMC信道，F(xiàn)SMC信道狀態(tài)只允許在相鄰狀態(tài)轉換。信道狀態(tài)轉換參數(shù)為=0.2(信道狀態(tài)由好變?yōu)椴缓玫母怕?，=0.3(信道狀態(tài)由不好變?yōu)楹玫母怕?，信道狀態(tài)維持不變1-狀態(tài)改變之和(最好信道為、最差信道為批，其他信道為+。

3.3 算法仿真

為了驗證PF-A算法在服務實時業(yè)務(本文的VoIP業(yè)務)時的優(yōu)點，本文對PF、DRC、APF算法和基于服務質量效用函數(shù)的PF-A算法從公平性、系統(tǒng)吞吐量、業(yè)務時延3個方面進行了性能對比。

本文采用Jain’s公平性準則[12]，從圖2看出，PF-A算法的公平性大于其他PF算法，且?guī)追N算法的公平性都隨著調度次數(shù)的增加而增加。公平性隨調度次數(shù)增加而變好主要是調度次數(shù)越大，系統(tǒng)業(yè)務的吞吐量越趨于平衡(因為PF算法都照顧信道條件不好的業(yè)務)，所以系統(tǒng)公平性變好。而PF算法公平性大于其他算法是因為PF-A算法考慮了業(yè)務時延對調度優(yōu)先級的影響，更加兼顧信道質量差的業(yè)務(信道質量差，相同的無線資源發(fā)送的數(shù)據(jù)量小業(yè)務延時大)使業(yè)務的吞吐量更加趨于平衡進而使Jain’s公平性最大。

圖2 Jain’s公平性

從圖3看出，PF-A算法的時延明顯小于PF、 DRC、APF 3種算法，主要是PF-A算法在調度優(yōu)先級中加入了時延因子，從而更兼顧信道質量差的業(yè)務，使業(yè)務時延降低44%。證明PF-A算法適用于具有時延約束的多媒體業(yè)務。

圖3 算法時延

PF、DRC、APF、PF-A算法的系統(tǒng)吞吐量分別為 7 201 Kb/s、7 363 Kb/s、7 419 Kb/s、6 933 Kb/s。PF-A算法的吞吐量比PF算法大概低4%，主要是PF-A算法考慮業(yè)務的QoS時延因素，增加信道質量較差業(yè)務的調度機會，在相同情況下傳輸較少的數(shù)據(jù)，從而導致系統(tǒng)吞吐量降低。

4 結束語

本文提出一種基于服務質量效用函數(shù)的比例公平調度算法，設計思想是在PF算法的調度優(yōu)先級判斷表達式引入與服務質量相關的參數(shù)項。仿真結果表明，該算法通過效用思想改進了實時業(yè)務的調度機會，以犧牲小部分系統(tǒng)吞吐量降低VoIP業(yè)務的時延，并提高了系統(tǒng)公平性。下一步研究的重點是在吞吐量損失和多媒體業(yè)務服務質量保證之間取得更好的折中。

[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] 胡 瑩, 黃永明, 俞 菲. 基于能效優(yōu)化的用戶調度與資源分配算法[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系統(tǒng)中提高TCP性能的資源調度算法研究[J]. 小型微型計算機系統(tǒng), 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] 馮慧芳, 趙 亮, 陳媛媛. 基于信道狀態(tài)的WIMAX系統(tǒng)實時調度算法[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－)，女，教授，主研方向：網(wǎng)絡協(xié)議優(yōu)化；劉建濤、林 婧，碩士；李陶深，教授。

2013-01-21

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

10.3969/j.issn.1000-3428.2014.03.024