葉 進(jìn)，劉建濤，林 婧，李陶深

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

葉 進(jìn)1，劉建濤2，林 婧2，李陶深1

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

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

服務(wù)質(zhì)量；調(diào)度算法；效用函數(shù)；比例公平；時(shí)延；吞吐量

1 概述

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

2 比例公平調(diào)度算法

2.1 PF算法的不足

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

2.2 PF-A算法的基本原理

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

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

2.3 PF-A調(diào)度算法

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

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

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

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

(5)重復(fù)步驟(2)~步驟(4)，直到調(diào)度完成。

3 仿真結(jié)果與分析

3.1 業(yè)務(wù)模型

3.2 信道模型

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

3.3 算法仿真

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

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

圖2 Jain’s公平性

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

圖3 算法時(shí)延

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è)務(wù)的QoS時(shí)延因素，增加信道質(zhì)量較差業(yè)務(wù)的調(diào)度機(jī)會(huì)，在相同情況下傳輸較少的數(shù)據(jù)，從而導(dǎo)致系統(tǒng)吞吐量降低。

4 結(jié)束語

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

[1] 袁東風(fēng), 張海霞, 馬艷波. 無線通信跨層設(shè)計(jì)——從原理到應(yīng)用[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)化的用戶調(diào)度與資源分配算法[J]. 電子與信息學(xué)報(bào), 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性能的資源調(diào)度算法研究[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2012, 33(5): 1018-1022.

[9] 陸巍煒. LTE中QoS調(diào)度算法研究[D]. 西安: 西安電子科技大學(xué), 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)實(shí)時(shí)調(diào)度算法[J]. 計(jì)算機(jī)應(yīng)用研究, 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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61163060, 61103204)；廣西自然科學(xué)基金資助重點(diǎn)項(xiàng)目(2011GXSFD01802)。

葉 進(jìn)(1970－)，女，教授，主研方向：網(wǎng)絡(luò)協(xié)議優(yōu)化；劉建濤、林 婧，碩士；李陶深，教授。

2013-01-21

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

10.3969/j.issn.1000-3428.2014.03.024