Shapley值的LTE系統(tǒng)下行QoS感知資源調(diào)度

王 妍，馬秀榮，單云龍

1.天津理工大學(xué) 電氣電子工程學(xué)院，天津300384

2.光電器件與通信技術(shù)教育部工程研究中心，天津300384

1 引言

隨著多媒體業(yè)務(wù)流、網(wǎng)絡(luò)游戲和基于IP的話音傳輸（Voice over Internet Protocol，VoIP）等新興業(yè)務(wù)的出現(xiàn)，通信系統(tǒng)傳輸技術(shù)需日益完善。改善不同用戶傳輸業(yè)務(wù)的服務(wù)質(zhì)量（Quality of Service，QoS）是長(zhǎng)期演進(jìn)（Long Term Evolution，LTE）[1]系統(tǒng)中基站（eNodeB）需要執(zhí)行的一項(xiàng)重要任務(wù)。下行資源調(diào)度算法[2]是通信系統(tǒng)中的研究熱點(diǎn)，調(diào)度算法中使用由信道質(zhì)量指示（Channel Quality Indicator，CQI）反饋的信道感知[3-4]信息和QoS感知[5]信息實(shí)現(xiàn)了復(fù)雜度和性能之間的均衡。因非實(shí)時(shí)（Non-Real-Time，NRT）與實(shí)時(shí)（Real-Time，RT）業(yè)務(wù)的QoS性能差距較大，有必要設(shè)計(jì)一種有效的調(diào)度算法來平衡各業(yè)務(wù)之間的QoS需求，這也是本文的研究目標(biāo)。

在最近的研究中，已提出了不同類型的分組調(diào)度算法來滿足LTE系統(tǒng)中各業(yè)務(wù)的QoS需求，從而提升系統(tǒng)性能。文獻(xiàn)[6]在改進(jìn)的最大加權(quán)延時(shí)優(yōu)先（Modified Largest Weighted Delay First，MLWDF）算法的基礎(chǔ)上提出虛擬隊(duì)列概念，引入反映用戶業(yè)務(wù)數(shù)據(jù)突發(fā)特性和某種QoS特性的數(shù)據(jù)隊(duì)列狀態(tài)信息，為用戶提供最小吞吐量保證，提升了實(shí)時(shí)性業(yè)務(wù)的吞吐量及公平性。文獻(xiàn)[7]在其算法的基礎(chǔ)上引入了時(shí)延門限與隊(duì)首時(shí)延差因子，用時(shí)延門限值來約束分組數(shù)據(jù)包的傳輸時(shí)延，減小業(yè)務(wù)數(shù)據(jù)因超出截止時(shí)間而產(chǎn)生的丟包率。文獻(xiàn)[8]在MLWDF算法的基礎(chǔ)上加入虛擬令牌隊(duì)列信息、時(shí)延門限和隊(duì)首時(shí)延差因子，使業(yè)務(wù)的實(shí)時(shí)性需求得到很好的保證。但幾種算法均犧牲了非實(shí)時(shí)業(yè)務(wù)的部分傳輸性能，提升了實(shí)時(shí)業(yè)務(wù)的傳輸性能，從而造成了非實(shí)時(shí)類業(yè)務(wù)具有較差的用戶公平性及系統(tǒng)業(yè)務(wù)吞吐量。

本文提出一種基于合作博弈論的Shapley值的信道資源初始分配方法。該方法通過將不同類型業(yè)務(wù)占用信道資源看成合作競(jìng)爭(zhēng)關(guān)系，根據(jù)各業(yè)務(wù)傳輸數(shù)據(jù)量大小計(jì)算得到聯(lián)盟邊界貢獻(xiàn)值，再使用Shapley值相對(duì)公平地計(jì)算各業(yè)務(wù)占用信道資源的數(shù)據(jù)量大小，實(shí)現(xiàn)對(duì)各業(yè)務(wù)占用信道資源的初始分配，防止個(gè)別業(yè)務(wù)過多地占用信道資源現(xiàn)象。LTE-Sim[9]的仿真結(jié)果表明，該算法提升了非實(shí)時(shí)業(yè)務(wù)公平性及吞吐量，同時(shí)保證了實(shí)時(shí)業(yè)務(wù)的傳輸性能，并在原算法上有小幅度改善。

2 系統(tǒng)模型

LTE系統(tǒng)分為用戶面和控制面，其中用戶面用來傳輸演進(jìn)型基站（eNodeB）與用戶終端設(shè)備（UE）之間的用戶數(shù)據(jù)信息[10]，在整個(gè)系統(tǒng)中起到十分重要的作用。用戶面協(xié)議棧通過研究用戶面MAC層中的資源調(diào)度過程來進(jìn)行信道資源分配，從而達(dá)到提升系統(tǒng)傳輸性能，滿足用戶體驗(yàn)等相關(guān)目的。MAC層的物理資源占用最小單位為RB，其時(shí)域表示一個(gè)子幀的時(shí)間，占用14個(gè)（或12個(gè)）OFDM符號(hào)，頻域表示連續(xù)的12個(gè)子載波，占用帶寬為180 kHz[11]。

圖1為L(zhǎng)TE下行資源調(diào)度的模型，對(duì)不同用戶業(yè)務(wù)的MAC隊(duì)列數(shù)據(jù)包進(jìn)行信道資源的調(diào)度[12]。資源調(diào)度算法在確定資源分配時(shí)，需考慮多種因素，如反映信道質(zhì)量狀況的CQI反饋信息，反映用戶當(dāng)前緩沖區(qū)狀態(tài)的信息和反映用戶體驗(yàn)性能的QoS等信息，根據(jù)這些因素進(jìn)行資源調(diào)度算法度量值的計(jì)算，將每個(gè)TTI中的RB資源根據(jù)度量值的大小分配給用戶業(yè)務(wù)數(shù)據(jù)。度量值越大則其越可能優(yōu)先占用信道資源進(jìn)行數(shù)據(jù)傳輸。度量值表達(dá)如式（1），其中mi,j(t)[13]表示第i個(gè)用戶業(yè)務(wù)在第j個(gè)RB上的度量值，為具有最大度量值的用戶業(yè)務(wù)，則將該RB資源分配給該用戶。

圖1 LTE下行資源調(diào)度模型

3 基于博弈論的資源調(diào)度算法設(shè)計(jì)

因無線傳輸信道資源有限，為更好地將有限的信道資源分配給用戶業(yè)務(wù)，優(yōu)化用戶業(yè)務(wù)的傳輸性能，根據(jù)用戶業(yè)務(wù)傳輸數(shù)據(jù)量大小提出基于博弈論的Shapley值的信道資源控制方法，將該方法應(yīng)用于MLWDF改進(jìn)算法上，以改善用戶業(yè)務(wù)傳輸性能。以下分別進(jìn)行介紹。

3.1 MLWDF及其改進(jìn)算法

以下將介紹MLWDF及其改進(jìn)算法，并分析算法性能。

（1）MLWDF

其中，δi表示用戶業(yè)務(wù)流所能承受的隊(duì)列延時(shí)超過閾值而引起的最大丟包率；τi表示時(shí)延門限值；DHOL,i表示業(yè)務(wù)隊(duì)頭數(shù)據(jù)包延時(shí)；ri,j(t)表示第j個(gè)RB上第i個(gè)用戶的瞬時(shí)比特速率表示第i個(gè)用戶在t時(shí)刻之前的平均吞吐量。該算法在PF（Proportional Fair）算法[6]的基礎(chǔ)上引入QoS參數(shù)δi、τi和DHOL,i，保障實(shí)時(shí)業(yè)務(wù)的QoS性能。

（2）QH-MLWDF

其中，qi(t)表示虛擬令牌機(jī)制下第i個(gè)用戶在t時(shí)刻的令牌桶隊(duì)列長(zhǎng)度，即傳輸隊(duì)列長(zhǎng)度信息，意味著發(fā)送數(shù)據(jù)的緩沖器中等待發(fā)送的數(shù)據(jù)越多，其調(diào)度優(yōu)先級(jí)越高。虛擬令牌的引入，對(duì)非實(shí)時(shí)業(yè)務(wù)有了最小吞吐量保證。

（3）MLWDF2

（4）DPVT-MLWDF

以上介紹的MLWDF及其改進(jìn)算法均通過引入時(shí)延門限、隊(duì)首時(shí)延、最大容忍丟包率等QoS參數(shù)信息，保障了實(shí)時(shí)業(yè)務(wù)的QoS性能。對(duì)于用戶業(yè)務(wù)中同時(shí)存在實(shí)時(shí)業(yè)務(wù)與非實(shí)時(shí)業(yè)務(wù)的情況，對(duì)非實(shí)時(shí)業(yè)務(wù)雖能達(dá)到其最小吞吐量保證，但對(duì)于其總體傳輸性能并不能達(dá)到較好的效果。為提升非實(shí)時(shí)業(yè)務(wù)的傳輸公平性及吞吐量，針對(duì)各業(yè)務(wù)的待傳輸數(shù)據(jù)量大小，提出一種基于合作博弈論的Shapley值信道資源初始控制方法。以下將對(duì)該算法進(jìn)行詳細(xì)介紹。

3.2 提出的調(diào)度算法

在多用戶多業(yè)務(wù)共存條件下，為提供實(shí)時(shí)業(yè)務(wù)的實(shí)時(shí)性、公平性及吞吐量，設(shè)計(jì)的資源調(diào)度算法會(huì)在保證非實(shí)時(shí)業(yè)務(wù)基本性能的條件下優(yōu)先考慮實(shí)時(shí)業(yè)務(wù)的性能優(yōu)化，對(duì)非實(shí)時(shí)業(yè)務(wù)造成公平性及吞吐量等性能較差的影響。為相對(duì)公平地為多種不同類型的業(yè)務(wù)提供信道資源，在MAC層RB資源調(diào)度之前利用合作博弈論的Shapley值[14]進(jìn)行信道資源的初始控制，通過對(duì)有限的信道資源根據(jù)業(yè)務(wù)量的大小進(jìn)行初始資源劃分，可實(shí)現(xiàn)對(duì)各業(yè)務(wù)占用信道資源的初始分配，解決因個(gè)別業(yè)務(wù)量過大而占用過多信道資源使其他業(yè)務(wù)因得不到信道資源而丟包率、吞吐量和公平性等性能下降的問題。該調(diào)度算法在多用戶多業(yè)務(wù)存在的條件下對(duì)各用戶業(yè)務(wù)具有較好的公平性，保障了系統(tǒng)各業(yè)務(wù)的基本性能。

提出算法為了將合作博弈論的概念轉(zhuǎn)化為信道帶寬資源分配問題，假設(shè)多種不同類型的用戶業(yè)務(wù)為合作聯(lián)盟競(jìng)爭(zhēng)關(guān)系，每類業(yè)務(wù)被視為單獨(dú)的游戲玩家，共同競(jìng)爭(zhēng)有限的信道資源。有限的信道資源使用自適應(yīng)調(diào)制與編碼（Adaptive Modulation and Coding，AMC）模型中50個(gè)RB對(duì)應(yīng)的傳輸塊大小表示，根據(jù)協(xié)議規(guī)定在一個(gè)調(diào)度時(shí)間間隔內(nèi)該值大小為36 696 bit。為清楚地闡述基于合作博弈論的Shapley值信道資源分配過程，以多業(yè)務(wù)共存的場(chǎng)景為例。假設(shè)存在三種業(yè)務(wù)類型，即N=3，其對(duì)應(yīng)的業(yè)務(wù)類型為實(shí)時(shí)業(yè)務(wù)Video和VoIP，非實(shí)時(shí)業(yè)務(wù)BE，分別用RT1、RT2、NRT來表示。根據(jù)合作博弈中特征函數(shù)（式（6））求得聯(lián)盟中參與者所獲得的效益。

其中，N表示參與者的個(gè)數(shù)；A是N的子集，指參與者之間的聯(lián)盟；gi表示不在聯(lián)盟子集A中的參與者的索賠矢量；C表示可分享給合作競(jìng)爭(zhēng)者的成本資源總和；特征函數(shù)vcg替代(N,vcg)表示一個(gè)合作博弈；特征函數(shù)vcg(A)表示聯(lián)盟A中參與者所獲得的效益。在信道資源分配過程中用該特征值計(jì)算各聯(lián)盟的特征函數(shù)，根據(jù)O’Neil方法，每個(gè)聯(lián)盟參與者的邊界貢獻(xiàn)值個(gè)數(shù)為2N-1個(gè)，通過特征函數(shù)公式進(jìn)行計(jì)算，當(dāng)存在三種業(yè)務(wù)類型時(shí)，共有七種可能的聯(lián)盟排列：

其中，Qn表示業(yè)務(wù)類型n在當(dāng)前調(diào)度時(shí)間間隔TTI內(nèi)所有用戶需傳輸?shù)臄?shù)據(jù)量大小，其計(jì)算過程由業(yè)務(wù)類型n的各用戶業(yè)務(wù)流的數(shù)據(jù)隊(duì)列大小求和得到。Shapley值是將每一個(gè)參與者所分擔(dān)的收益或者成本等于該參與者為其參與的所有聯(lián)盟（包括大聯(lián)盟N和所有子聯(lián)盟A）帶來的邊界貢獻(xiàn)值（邊界收益或邊界成本）的期望值，其計(jì)算公式如下：其中，A是合作聯(lián)盟N中包含的所有子聯(lián)盟；n表示合作聯(lián)盟N中參與者；||

A表示子聯(lián)盟A中所包含的參與者個(gè)數(shù)；vcg(A)表示合作聯(lián)盟中子聯(lián)盟A的成本，即通信系統(tǒng)中在一個(gè)調(diào)度周期內(nèi)子聯(lián)盟A需占用的期望信道資源總量；vcg(A/n)表示子聯(lián)盟A與扣除參與者n后其他參與者所構(gòu)成子聯(lián)盟的占用成本；vcg(A)-vcg(A/n)表示給參與者n提供所需服務(wù)而額外增加的成本，即參與者n的邊際貢獻(xiàn)值。根據(jù)式（3）中的Shapley值對(duì)各用戶業(yè)務(wù)類型所占用的信道資源量的期望值進(jìn)行計(jì)算：

其中，φRT1(vcg)、φRT2(vcg)、φNRT(vcg)參數(shù)分別表示RT1（Video）、RT2（VoIP）和NRT（BE）三種業(yè)務(wù)被相對(duì)公平分配的信道資源數(shù)據(jù)量大小；vcg(?)=0。公式中的分?jǐn)?shù)部分表示根據(jù)Shapley值給每個(gè)業(yè)務(wù)類型分配信道資源帶寬所使用的比例系數(shù)，根據(jù)式（4）中各業(yè)務(wù)所分配的數(shù)據(jù)量大小可證實(shí)式（10），不同業(yè)務(wù)類型所占用的信道資源總和等于在該調(diào)度周期內(nèi)的信道容量大小。

通過以上基于合作博弈論Shapley值的計(jì)算過程，每種業(yè)務(wù)類型在RB資源調(diào)度之前均被分配了一定量的信道資源，在RB資源調(diào)度過程則根據(jù)各業(yè)務(wù)類型所分配信道資源量對(duì)用戶業(yè)務(wù)類型數(shù)據(jù)量傳輸進(jìn)行控制，若超過所分配業(yè)務(wù)量大小，則將信道資源分配給其他業(yè)務(wù)類型進(jìn)行傳輸，以保證各業(yè)務(wù)相對(duì)公平地進(jìn)行數(shù)據(jù)傳輸。在RB資源調(diào)度過程中，資源調(diào)度算法則采用3.1節(jié)所介紹的MLWDF改進(jìn)型資源調(diào)度算法。

算法流程偽代碼如下：

1.各參量初始化設(shè)置

2.計(jì)算用戶業(yè)務(wù)種類數(shù)N和各類業(yè)務(wù)傳輸數(shù)據(jù)總量Qn

3.根據(jù)式（7）計(jì)算各聯(lián)盟特征函數(shù)值vcg(A)

4.根據(jù)式（8）計(jì)算各業(yè)務(wù)可占用信道資源量的期望值φn(v)

5.while信道RB可用資源!=0或者傳輸數(shù)據(jù)!=0；do

6. if某業(yè)務(wù)傳輸量<該業(yè)務(wù)的φn(v)then

插入調(diào)度數(shù)據(jù)流可進(jìn)行該業(yè)務(wù)的RB資源調(diào)度；

else

對(duì)其他業(yè)務(wù)進(jìn)行RB資源調(diào)度；

end if

7.更新各用戶業(yè)務(wù)傳輸量

8.end

9.結(jié)束資源分配過程，進(jìn)行數(shù)據(jù)傳輸；

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

4.1 仿真環(huán)境

本文仿真使用近年來研究LTE系統(tǒng)資源調(diào)度算法的主流平臺(tái)之一的開源LTE-Sim。該平臺(tái)基于C++語言，具有較高的運(yùn)行效率及數(shù)據(jù)可靠性。仿真參數(shù)設(shè)置如表1所示，采用的LTE系統(tǒng)帶寬為10 MHz，RB數(shù)為50，基站個(gè)數(shù)和小區(qū)個(gè)數(shù)均為1，仿真用戶數(shù)從5到50進(jìn)行仿真，其變化間隔數(shù)為5，用戶移動(dòng)速度大小為3 km/h。仿真中使用混合業(yè)務(wù)模型，包括實(shí)時(shí)業(yè)務(wù)Video（使用標(biāo)準(zhǔn)H.264編碼器）[15]、VoIP（使用G.729編碼器）和非實(shí)時(shí)業(yè)務(wù)Inf-Buf（盡力而為業(yè)務(wù)）。

表1 仿真參數(shù)設(shè)置

4.2 仿真結(jié)果

在仿真過程中，對(duì)MLWDF2、QH-MLWDF、DPVTMLWDF三種算法及在三種算法上加上基于博弈論Shapley值的初始信道資源控制方法的SV-MLWDF、SVVT-MLWDF、SV-DPVT-MLWDF算法進(jìn)行對(duì)比分析。仿真結(jié)果的輸出使用QoS度量標(biāo)準(zhǔn)[16]進(jìn)行分析和討論，如每個(gè)業(yè)務(wù)的用戶Jain公平性指數(shù)、業(yè)務(wù)流吞吐量、丟包率（PLR）和平均時(shí)延。

如圖2所示，根據(jù)Jain公平性準(zhǔn)則，對(duì)各個(gè)業(yè)務(wù)進(jìn)行用戶公平性的仿真。從圖中結(jié)果分析可知，引入基于Shapley值的信道資源控制方法比原始算法的公平性均有所提升。對(duì)于實(shí)時(shí)業(yè)務(wù)VoIP，因其數(shù)據(jù)量較小且具有周期性，幾種算法公平性變化不明顯。對(duì)于實(shí)時(shí)業(yè)務(wù)Video，其數(shù)據(jù)量較大，所分配的信道資源充足，可保證該業(yè)務(wù)的公平性，對(duì)比原始算法，公平性有所提升。對(duì)于非實(shí)時(shí)盡力而為業(yè)務(wù)，因其對(duì)時(shí)延要求較低，與實(shí)時(shí)業(yè)務(wù)相比具有較低的優(yōu)先級(jí)，信道資源優(yōu)先分配給實(shí)時(shí)業(yè)務(wù)，其公平性較低，但通過Shapley值的信道資源業(yè)務(wù)量控制，對(duì)三種用戶業(yè)務(wù)類型的數(shù)據(jù)量進(jìn)行相對(duì)公平的劃分，給予非實(shí)時(shí)業(yè)務(wù)更多占用信道資源的機(jī)會(huì)，提升了用戶公平性。

圖4 三種業(yè)務(wù)類型丟包率對(duì)比圖

圖3反映了各業(yè)務(wù)流吞吐量與用戶數(shù)量之間的變化關(guān)系。從仿真結(jié)果可見，對(duì)于非實(shí)時(shí)盡力而為業(yè)務(wù)而言，在MAC層RB調(diào)度之前加入基于博弈論的Shpley值的信道資源控制，使非實(shí)時(shí)業(yè)務(wù)可根據(jù)其傳輸數(shù)據(jù)量大小分配到一定的信道資源，使其在調(diào)度優(yōu)先級(jí)較低的情況下獲得了信道資源進(jìn)行傳輸，增加吞吐量。對(duì)于DPVTMLWDF算法，吞吐量最高增加了59.03%，平均增加了38.05%，對(duì)于MLWDF2算法和QH-MLWDF算法，其吞吐量增量平均為0.61%和13.50%。對(duì)于實(shí)時(shí)業(yè)務(wù)Video而言，三種算法在引入Shapley值的信道資源控制后，其吞吐量在用戶數(shù)量超過35后均有所提升。對(duì)于實(shí)時(shí)業(yè)務(wù)VoIP而言，吞吐量保證在較好的水平，幾種算法差別不明顯。

圖4反映了各業(yè)務(wù)的丟包率隨用戶數(shù)量增加的變化情況。對(duì)于非實(shí)時(shí)盡力而為業(yè)務(wù)，其在用戶較低調(diào)度優(yōu)先級(jí)的情況下獲得了基本量的信道資源，因此丟包率有所降低。對(duì)于SV-DPVT-MLWDF算法，對(duì)比DPVTMLWDF算法丟包率平均降低了4.76%，SV-MLWDF2和SV-QH-MLWDF算法丟包率均有所降低，變化幅度不明顯。對(duì)于實(shí)時(shí)業(yè)務(wù)VoIP 和Video，引入合作博弈論的Shapley 值的信道資源初始分配算法均比原始算法的丟包率有所降低，由此可見該信道資源業(yè)務(wù)劃分機(jī)制有利于降低各業(yè)務(wù)的丟包率。

圖5 兩種實(shí)時(shí)業(yè)務(wù)平均時(shí)延對(duì)比圖

圖5表示兩類實(shí)時(shí)業(yè)務(wù)的時(shí)延隨著用戶數(shù)量的變化關(guān)系。幾種算法的時(shí)延均控制在70 ms以下，較好地保證了兩實(shí)時(shí)業(yè)務(wù)的實(shí)時(shí)性。加入博弈論Shapley值的信道資源控制方法的時(shí)延比原始算法略有上升，因?yàn)榉菍?shí)時(shí)業(yè)務(wù)分配了相對(duì)更多的資源，使實(shí)時(shí)業(yè)務(wù)的等待時(shí)間略有上浮。

5 結(jié)束語

本文針對(duì)下行調(diào)度中非實(shí)時(shí)業(yè)務(wù)性能較差的特點(diǎn)，對(duì)資源調(diào)度算法進(jìn)行了設(shè)計(jì)與改善，通過各業(yè)務(wù)待傳輸數(shù)據(jù)量大小利用Shapley值來相對(duì)公平地分配信道資源，控制各業(yè)務(wù)量進(jìn)行傳輸。該方法改善了非實(shí)時(shí)業(yè)務(wù)占用信道資源較少的情況，增加了其公平性與吞吐量，同時(shí)對(duì)實(shí)時(shí)業(yè)務(wù)也體現(xiàn)了較好的傳輸性能。此外，在實(shí)際通信調(diào)度中，還需考慮調(diào)度算法的計(jì)算復(fù)雜度，如何設(shè)計(jì)合理高效的調(diào)度算法還需進(jìn)一步研究。