LTE/WLAN 網絡下基于比例公平的資源分配算法研究

俞 涵，張武雄，裴 冬，趙 鋮，張婷婷

（1.上海微系統與信息技術研究所 上海 200050；2.上海無線通信研究中心 上海201210；3.上海科技大學 上海201210）

LTE/WLAN 網絡下基于比例公平的資源分配算法研究

俞 涵1，3，張武雄1，2，裴 冬1，3，趙 鋮1，3，張婷婷1，3

（1.上海微系統與信息技術研究所 上海 200050；2.上海無線通信研究中心 上海201210；3.上海科技大學 上海201210）

近年來，為滿足移動數據爆發性的增長需求，LTE與WLAN共同組成的異構網絡逐漸成為研究的焦點。在這樣的場景下，當每個用戶同時配備LTE和WLAN收發器時，用戶體驗更能獲得巨大的改善。然而，由于兩個系統之間的協同存在障礙，聯合管理無線資源比較困難。因此，文中考慮同時優化LTE系統中的信道分配和WLAN系統中的用戶關聯的問題，證明了這兩個問題都可以轉化成相交擬陣下的次模函數，并利用了一個基于次梯度的算法對這兩個問題分別求解，最終通過LTE和WLAN系統中交替使用該優化算法提高全網吞吐量。

異構網絡；資源分配；比例公平；LTE/WLAN；次模函數

隨著智能終端的迅猛發展，移動蜂窩網絡面臨著不斷增長的負載壓力和巨大的數據需求（比如網頁瀏覽和視頻點播等等），預計5年內全球的移動數據量將增長10倍左右[1]。因此，對于移動運營商來說，及時有效的增加網絡容量和減輕網絡擁擠是至關重要的。但是，傳統蜂窩網的解決辦法（比如獲取更多的授權頻譜資源，部署更多的小區以及更新硬件技術等等），并不能跟上數據量的增長速度。在原有蜂窩網絡的基礎上部署小功率節點構成異構網絡，并對移動數據進行卸載分流，可以有效解決蜂窩網容量問題。目前常見的小功率站點包括Femto站點和WLAN接入點 （Access Point，AP）兩種，由于WLAN接入點高速經濟的性能，本文將以蜂窩網絡中具有代表性的LTE（Long Term Evolution，長期演進）網絡與WLAN組成的異構網絡作為研究目標。

在LTE/WLAN異構網中，資源分配對網絡整體性能有著重要的影響。其中，用戶對網絡接入點的選擇是資源分配的重要一環。網絡選擇問題一般都會基于一個效用函數，然后通過各種數學方法進行求解[2-3]。文獻[4]中系統調研了異構網中的網絡選擇問題，并總結了幾種解決網絡選擇問題的常用數學模型，如多屬性決策、模糊邏輯、馬爾科夫鏈等等。最終，文中提出一種以多屬性決策為核心的集成網絡選擇算法。文獻[5]中同時考慮用戶費用和以文件傳輸時間為特征的QoS （Quality of Service，服務質量），提出一種單調DAWN（Delay-Aware WLAN Offloading and Network Selection）算法。然而，在這些算法中，大部分對于用戶的假設都是指的多模用戶（Multi-mode UE）[4]。

在異構網中，多模用戶終端最多只可以關聯一個可用的無線接入技術（Radio Access Technologies，RAT），而多址用戶終端（Multi-homing UE）可以同時連接多個RAT[4]。當用戶同時處在LTE與WLAN的覆蓋范圍內時，如果能同時接入兩個系統，用戶吞吐量和體驗將得到很大的提高。實際上，在最近的3GPP會議中，已經開始定義這樣的網絡架構[6]，其結構類似于LTE系統中的雙鏈接（Dual Connectivity），即用戶可以同時接入LTE和WLAN系統并可以從LTE中卸載部分流量以減輕LTE基站的負擔。文獻[7]中提出了一種研究流量聚合的框架，作者分析了非理想的回程條件下，多RAT異構網絡中聚合數據流量的優化算法，但是作者并沒有分析低復雜度的網絡選擇算法。文獻[8]中提出在上行聯合每個用戶的流量調度和功率控制的優化問題，并且考慮了移動用戶的資源限制和互相之間的干擾。但是文中沒有考慮到多個AP存在時的網絡選擇問題，多AP存在的場景會使資源分配比下行更復雜。

文中將綜合已有的研究背景，考慮多址用戶存在的場景，兼顧LTE中的信道分配和WLAN中的節點選擇問題，并且在考慮比例公平的前提下，最大化整體網絡的容量。

1　系統模型

文中，考慮圖1所示的異構網絡場景，即一個LTE基站和NAP個WLAN接入點（AP），這NAP個AP都在LTE基站的覆蓋范圍內。假設每個用戶終端（User Equipment，UE）可以同時連接LTE基站和一個AP，并且用戶的兩條鏈路上都有數據傳輸。

如果N={1，2，…，NAP}、U={1，2，…，NUE}以及C={1，2，…，NCH}分別表示AP、用戶終端以及LTE信道的集合。那么，用戶u∈U可以同時占用一個LTE信道c∈C并接入一個WLAN接入點n∈N。定義變量xu，c=1表示用戶u選擇信道c，xu，c=0表示用戶u不選擇信道c，那么用戶與信道的分配關系可以用矩陣X表示：

同理，用戶與AP之間的選擇關系可以用矩陣Y表示：

下面分別分析每個用戶在LTE和WLAN系統中的吞吐量計算模型。

圖1　LTE/WLAN異構網絡場景示意圖

1）LTE

基站第c個子信道與第u個用戶之間的信噪比（SNR）表示成βu，c，假設沒有頻率復用，那么根據香農公式[9]，第u個用戶在LTE側的吞吐量可以表示為：

其中，α1和α2是LTE信道利用率和SINR實現效率的參數，則ωc表示子信道的帶寬。

2）WLAN

假設第u個用戶成功傳輸時所需傳輸的平均數據量為Lu，Te，n和 Tc，n分別表示第n個 AP的空閑時隙長度和傳輸數據的平均時長，τu，n表示用戶u∈Un（Un是第n個AP所關聯的用戶的集合）與第n個AP關聯并可以在某一隨機時隙（slot）傳輸數據的概率，那么第u個用戶在WLAN側的吞吐量可以表示為[10]：

其中，ps，u，n表示在該時隙內用戶u成功傳輸的概率，Pe，n該時隙空閑的概率。這兩個概率可以用τu，n表示如下：

其中，pf，u，n表示傳輸失敗的概率。

為進一步簡化式（2），假設對于所有用戶來說，退避窗長CWmin=CWmax，那么對于任意的u∈U，。根據文獻[11]，令，則式（2）可以改寫成：

其中，X（x）=Te，n＋（1＋xk）-1，因為xk=x對所有用戶成立，所以X（x）=Te，n＋（1＋xk）∣Un∣-1，∣Un∣表示與用戶u關聯的AP服務的用戶數。

為了基于比例公平的前提下獲取得最佳的信道和節點選擇方案，以達到整體網絡的吞吐量最大化，結合定義的關聯狀態矩陣X和Y，將目標函數用數學方式表達成：

約束條件：

約束條件描述的物理意義是指對用戶和LTE信道以及WLAN接入點之間的關聯數的限制，即每個用戶只能接入一個LTE信道和一個WLAN接入點，且每個WLAN接入點所關聯的用戶數不超過m個，m是常數。

2　算法設計

根據優化目標，需要在式（7）～（10）的限制下，輸出使式（7）達到最大值的矩陣X和Y，即用戶與信道和AP的關聯關系。這是一個組合問題，組合問題一般都存在一個最優算法，但是通常會以時間為代價，所以文中希望在設計算法的時候盡量減少迭代過程。通過對式（7）～（10）進行一定的轉化，可以證明這是一個次模函數求解問題，從而應用基于次梯度的次模問題算法來降低計算的復雜度。因為次模函數的自變量是集合，對其求解可以很大地提高運算效率。

根據矩陣X、Y，定義兩個基礎集合Ω={（u，c）:u∈U，c∈C} 和Ω’={（u，n）:u∈U，n∈N}，并且對于任意的子集：G?Ω，G’?Ω’。對應第c個信道子集定義為G（c）={（u，c）:u∈U}，同時第n個AP對應的子集為G’（n）={（u，n）:u∈U}。類似地，對每個用戶來說也存在兩個子集G（u）={（u，c）:c∈C}和G’（u）={（u，n）:n∈N}。因此，式（7）～（10）可以改寫成：

約束條件：

文中目標是在靜態初始化連接的基礎上，迅速找出局部最優解Ω*和Ω’*。

接下來，證明式（12）描述的是一個存在多個擬陣的次模問題，上述約束條件就是該次模函數的擬陣。

定義1[12]：函數F（j|S）=F（S∪j）-F（S），其中j∈V，S?V。當且僅當滿足條件F（j|S）≥F（j|T），?S∈T且j?T時，F是一個次模函數。

由于式（12）中有兩個變量，因此可以分別證明F（G，G’*）和F（G*，G’）為次模函數，其中假設G’*和G*為固定值。根據定義很容易證明F（G，G’*）是次模函數，因此此處只給出F（G*，G’）的證明過程如下：

F（G*，G′）=-log（1＋Cu（G*，G′））可以簡寫成 F（G）′= -log（1＋Cu（G′）），因為G*是固定值。結合式（6），可得：

其中θ表示該用戶在LTE側的吞吐量，此時為常數，因此δ=1＋θ也為常數。根據之前的假設，式（12）中只有一個變量∣Un∣，在證明過程中其他參數都是常量。令∣Un∣=y，z=x （1-pf，u，n）Lu，t=Te，n-1＜0，式（12）又能簡化成式（13）：

假設式（11）中m=5，在場景中分別隨機放置15、20及25的命題B.6（Proposition B.6），當外層函數f（φ）為非遞減凹函數且內層函數φ（y）為次模函數時，可證明f（y）也為次模函數。

首先，易得對任意的y≥1，φ（y）為非遞減的凹函數，這意味著存在：

那么：

此時，根據定義1可得Φ（G’）是次模函數。同時，f（φ）=-log（δ-φ）可證得為非遞減凹函數。因此得證F（G*，G’）為次模函數。

定義2[14]：定義三種次梯度如下：

其中，Y為子集，V為全集。

基于次梯度的算法在上述定義的基礎上展開，并且在LTE和WLAN兩個系統內交替應用以下算法。以下仍以WLAN系統為例簡述該算法的過程。為了實現最小化，每次迭代所得的結果都需滿足以下條件：

以下為在WLAN系統中的算法步驟：

算法1基于次梯度的快速次模函數求解算法

輸入：初始關聯值G’0={（u，n），u∈U，n∈N}

重復以下步驟：

1.在定義2中選擇一個次梯度定義

2.G’t＋1:argminG∈ΩgG’t（G’t）；

3.t←t＋1；

直到獲得收斂值G’t＋1=G’t

在一次完整的迭代中，LTE系統中的迭代算法與算法1類似，只需將輸入值改為G0={（u，c），u∈U，c∈C}，且G換成G’即可。

3　仿真結果

表格1　仿真參數

為驗證提出的算法的性能，進行了下述針對LTE與WLAN組成的異構網絡的仿真。網絡拓撲結構參見圖1所示場景。其中AP均勻地分布在LTE基站的覆蓋范圍內，表格1個用戶，仿真時的一次迭代表示分別進行了一次LTE和WLAN系統的迭代算法。圖2展示了該算法對系統吞吐量的改善情況，橫坐標表示迭代的次數，為保證公平，縱坐標為式（9）所示的效用值，從圖2可以看出該算法的收斂速度很快，基本上一次完整的迭代就能得到局部最優解。

圖2　算法收斂速度仿真圖

圖3　每個AP接入點吞吐量前后對比圖

圖4　用戶AP關聯關系前后對比圖

圖3展示了5個AP站點經過算法調整前后的吞吐量對比圖，第6組數據是整個WLAN網絡的吞吐量（前5組數據之和）。圖4展示了當用戶數為15時，應用該算法進行節點選擇前后的關聯關系對比圖，因為只有1個LTE基站，因此與信道的關聯關系沒有表示出來。其中，圖4（a）所示的仿真初始狀態是通過接入點與用戶之間的傳輸速率大小來選擇AP的。

從圖3和圖4可以看出用戶最初根據傳輸速率進行AP選擇，每個AP的負載不均衡，有的AP沒有接入用戶，應用本文提出的算法之后AP負載更加均衡協調，且最終整個網絡的吞吐量也有明顯提高。

4　結　論

文中針對LTE和WLAN組成的異構網絡提出了一種在用戶同時接入兩個系統的場景下基于比例公平的資源分配算法。該算法可以在兩個系統中同時應用，從而達到整體網絡吞吐量得到改善的目標。從仿真結果來看，該算法收斂速度快，而且整體的吞吐量得到了顯著的提升。

[1]Forecast C V.Cisco Visual Networking Index:Global Mobile Data Traffic Forecast Update 2014-2019[C]//Cisco Public Information，2015.

[2]Aryafar E，Keshavarz-Haddad A，Wang M，et al.Rat selectiongames in hetnets，INFOCOM[C]//2013 Proceedings IEEE，2013：998-1006.

[3]Ismail M，Zhuang W.A distributed multi-service reso-urce allocation algorithm in heterogeneous wireless access me-dium [J].IEEE Journalon Selected Areas in Communications，2012，30（2）：425-432.

[4]Wang L.，Kuo G.-S.Mathematical modeling for network selectionin heterogeneous wireless networks-a tutorial[J]. CommunicationsSurveys&Tutorials，IEEE，2013，15（1）：271-292.

[5]Man H.C.，Huang J.Dawn:Delay-aware WLAN offloading andnetwork selection[J].IEEE Journal on Selected Areas in Communications，2015（33）：1214-1223.

[6]Intel Corp.，China Telecom，Qualcomm Inc.，LTE-WLAN radio levelintegration and interworking enhancement[C]// RP-151114，2015.

[7]Singh S.，Geraseminko M.Yeh S.，et al.Proportional Fair Traffic Splitting and Aggregation in Heterogeneous Wireless Networks[J].American Journal of Human Genetics，2015，118（6）:476-479.

[8]Y.Wu，Y.He，L.Qian，et al.Joint scheduling andpower allocations for traffic offloading via dual-connectivity[EB/OL]. http://arxiv.org/abs/1509.09241，2015.

[9]P.Mogensen，W.Na，I.Z.Kovács，et al.Lte capacitycompared to the shannon bound，Vehicular Technology Conference[C]//2007.VTC2007-Spring.IEEE 65th，2007: 1234-1238.

[10]A.Checco，D.J.Leith.ProportionalFairnessin802.11 Wireless LANs[J].IEEE Communications Letters，2011，15 （8）:807-809.

[11]D.J.Leith，V.G.Subramanian.Duffy K R.Log-convexity ofrate region in 802.11e WLANs[J].IEEE Communications Letters，2011，14（1）:57-59.

[12]Lee J，Sviridenko M，Vondrák J.Submodular Maximization over Multiple Matroids via Generalized Exchange Properties [J].Mathematics of Operations Research，2010，35（4）:795-806.

[13]F.Bach.Learning with Submodular Functions:A Convex OptimizationPerspective[J].Foundations&Trendsin Machine Learning，2011.

[14]R.Iyer，S.Jegelka，and J.Bilmes，Fast semidifferentialbased submodular function optimization:Extended version [EB/OL].http://arxiv.org/abs/1308.1006，Aug.2013.

[15]Partov B，Leith D.Utility fair rate allocation in LTE/ 802.11networks[EB/OL].http://arxiv.org/abs/1506.01058，Jun. 2015.

Proportion fairness based resource allocation in LTE/WLAN network

YU Han1，3，ZHANG Wu-xiong1，2，PEI Dong1，3，ZHAO Cheng1，3，ZHANG Ting-ting1，3
（1.Shanghai Institute of Microsystem And Information Technology，Shanghai 200050，China；2.Shanghai Research Center for Wireless Communications，Shanghai 201210，China；3.ShanghaiTech University，Shanghai 201210，China）

In order to meet the explosive mobile data demand，LTE/WLAN heterogeneous network（HetNet）has attracted a lot of attentionin recent years.In this HetNetscenario，each user equipped both LTE andWLAN transceivers can improve the users'experience dramatically.However，due to the cooperation barrier，it is difficult to managethe wireless resource jointly.In this paper，we optimized the channel allocation in LTE network and user association in WLAN network simultaneously. Moreover，we prove both of the two problems can be transformedto submodular functions with intersection of matroids，a semigradient based algorithm is applied to solve them respectively.Simulation results show that the alternative optimization between LTE and WLAN can improvethe throughput of the whole network.

heterogeneous network；resource allocation；LTE/WLAN；submodular function

TN99

A

1674－6236（2016）22-0012-04

2016-03-30稿件編號：201603397

國家自然科學基金資助項目（61231009）；國家科技重大項目（2014ZX03001024）；上海市科教委項目（14ZR1439700）

俞 涵（1992—），女，江蘇南通人，碩士。研究方向：下一代移動通信網絡。