基于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