Shapley值的LTE系統下行QoS感知資源調度

王 妍，馬秀榮，單云龍

1.天津理工大學 電氣電子工程學院，天津300384

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

1 引言

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

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

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

2 系統模型

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

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

圖1 LTE下行資源調度模型

3 基于博弈論的資源調度算法設計

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

3.1 MLWDF及其改進算法

以下將介紹MLWDF及其改進算法，并分析算法性能。

（1）MLWDF

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

（2）QH-MLWDF

其中，qi(t)表示虛擬令牌機制下第i個用戶在t時刻的令牌桶隊列長度，即傳輸隊列長度信息，意味著發送數據的緩沖器中等待發送的數據越多，其調度優先級越高。虛擬令牌的引入，對非實時業務有了最小吞吐量保證。

（3）MLWDF2

（4）DPVT-MLWDF

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

3.2 提出的調度算法

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

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

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

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

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

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

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

算法流程偽代碼如下：

1.各參量初始化設置

2.計算用戶業務種類數N和各類業務傳輸數據總量Qn

3.根據式（7）計算各聯盟特征函數值vcg(A)

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

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

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

插入調度數據流可進行該業務的RB資源調度；

else

對其他業務進行RB資源調度；

end if

7.更新各用戶業務傳輸量

8.end

9.結束資源分配過程，進行數據傳輸；

4 仿真結果與分析

4.1 仿真環境

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

表1 仿真參數設置

4.2 仿真結果

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

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

圖4 三種業務類型丟包率對比圖

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

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

圖5 兩種實時業務平均時延對比圖

圖5表示兩類實時業務的時延隨著用戶數量的變化關系。幾種算法的時延均控制在70 ms以下，較好地保證了兩實時業務的實時性。加入博弈論Shapley值的信道資源控制方法的時延比原始算法略有上升，因為非實時業務分配了相對更多的資源，使實時業務的等待時間略有上浮。

5 結束語

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