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

（1.上海微系統(tǒng)與信息技術(shù)研究所 上海 200050；2.上海無線通信研究中心 上海201210；3.上海科技大學(xué) 上海201210）

LTE/WLAN 網(wǎng)絡(luò)下基于比例公平的資源分配算法研究

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

（1.上海微系統(tǒng)與信息技術(shù)研究所 上海 200050；2.上海無線通信研究中心 上海201210；3.上海科技大學(xué) 上海201210）

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

異構(gòu)網(wǎng)絡(luò)；資源分配；比例公平；LTE/WLAN；次模函數(shù)

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

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

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

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

1　系統(tǒng)模型

文中，考慮圖1所示的異構(gòu)網(wǎng)絡(luò)場(chǎng)景，即一個(gè)LTE基站和NAP個(gè)WLAN接入點(diǎn)（AP），這NAP個(gè)AP都在LTE基站的覆蓋范圍內(nèi)。假設(shè)每個(gè)用戶終端（User Equipment，UE）可以同時(shí)連接LTE基站和一個(gè)AP，并且用戶的兩條鏈路上都有數(shù)據(jù)傳輸。

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

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

下面分別分析每個(gè)用戶在LTE和WLAN系統(tǒng)中的吞吐量計(jì)算模型。

圖1　LTE/WLAN異構(gòu)網(wǎng)絡(luò)場(chǎng)景示意圖

1）LTE

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

其中，α1和α2是LTE信道利用率和SINR實(shí)現(xiàn)效率的參數(shù)，則ωc表示子信道的帶寬。

2）WLAN

假設(shè)第u個(gè)用戶成功傳輸時(shí)所需傳輸?shù)钠骄鶖?shù)據(jù)量為L(zhǎng)u，Te，n和 Tc，n分別表示第n個(gè) AP的空閑時(shí)隙長(zhǎng)度和傳輸數(shù)據(jù)的平均時(shí)長(zhǎng)，τu，n表示用戶u∈Un（Un是第n個(gè)AP所關(guān)聯(lián)的用戶的集合）與第n個(gè)AP關(guān)聯(lián)并可以在某一隨機(jī)時(shí)隙（slot）傳輸數(shù)據(jù)的概率，那么第u個(gè)用戶在WLAN側(cè)的吞吐量可以表示為[10]：

其中，ps，u，n表示在該時(shí)隙內(nèi)用戶u成功傳輸?shù)母怕?，Pe，n該時(shí)隙空閑的概率。這兩個(gè)概率可以用τu，n表示如下：

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

為進(jìn)一步簡(jiǎn)化式（2），假設(shè)對(duì)于所有用戶來說，退避窗長(zhǎng)CWmin=CWmax，那么對(duì)于任意的u∈U，。根據(jù)文獻(xiàn)[11]，令，則式（2）可以改寫成：

其中，X（x）=Te，n＋（1＋xk）-1，因?yàn)閤k=x對(duì)所有用戶成立，所以X（x）=Te，n＋（1＋xk）∣Un∣-1，∣Un∣表示與用戶u關(guān)聯(lián)的AP服務(wù)的用戶數(shù)。

為了基于比例公平的前提下獲取得最佳的信道和節(jié)點(diǎn)選擇方案，以達(dá)到整體網(wǎng)絡(luò)的吞吐量最大化，結(jié)合定義的關(guān)聯(lián)狀態(tài)矩陣X和Y，將目標(biāo)函數(shù)用數(shù)學(xué)方式表達(dá)成：

約束條件：

約束條件描述的物理意義是指對(duì)用戶和LTE信道以及WLAN接入點(diǎn)之間的關(guān)聯(lián)數(shù)的限制，即每個(gè)用戶只能接入一個(gè)LTE信道和一個(gè)WLAN接入點(diǎn)，且每個(gè)WLAN接入點(diǎn)所關(guān)聯(lián)的用戶數(shù)不超過m個(gè)，m是常數(shù)。

2　算法設(shè)計(jì)

根據(jù)優(yōu)化目標(biāo)，需要在式（7）～（10）的限制下，輸出使式（7）達(dá)到最大值的矩陣X和Y，即用戶與信道和AP的關(guān)聯(lián)關(guān)系。這是一個(gè)組合問題，組合問題一般都存在一個(gè)最優(yōu)算法，但是通常會(huì)以時(shí)間為代價(jià)，所以文中希望在設(shè)計(jì)算法的時(shí)候盡量減少迭代過程。通過對(duì)式（7）～（10）進(jìn)行一定的轉(zhuǎn)化，可以證明這是一個(gè)次模函數(shù)求解問題，從而應(yīng)用基于次梯度的次模問題算法來降低計(jì)算的復(fù)雜度。因?yàn)榇文：瘮?shù)的自變量是集合，對(duì)其求解可以很大地提高運(yùn)算效率。

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

約束條件：

文中目標(biāo)是在靜態(tài)初始化連接的基礎(chǔ)上，迅速找出局部最優(yōu)解Ω*和Ω’*。

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

定義1[12]：函數(shù)F（j|S）=F（S∪j）-F（S），其中j∈V，S?V。當(dāng)且僅當(dāng)滿足條件F（j|S）≥F（j|T），?S∈T且j?T時(shí)，F(xiàn)是一個(gè)次模函數(shù)。

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

F（G*，G′）=-log（1＋Cu（G*，G′））可以簡(jiǎn)寫成 F（G）′= -log（1＋Cu（G′）），因?yàn)镚*是固定值。結(jié)合式（6），可得：

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

假設(shè)式（11）中m=5，在場(chǎng)景中分別隨機(jī)放置15、20及25的命題B.6（Proposition B.6），當(dāng)外層函數(shù)f（φ）為非遞減凹函數(shù)且內(nèi)層函數(shù)φ（y）為次模函數(shù)時(shí)，可證明f（y）也為次模函數(shù)。

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

那么：

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

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

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

基于次梯度的算法在上述定義的基礎(chǔ)上展開，并且在LTE和WLAN兩個(gè)系統(tǒng)內(nèi)交替應(yīng)用以下算法。以下仍以WLAN系統(tǒng)為例簡(jiǎn)述該算法的過程。為了實(shí)現(xiàn)最小化，每次迭代所得的結(jié)果都需滿足以下條件：

以下為在WLAN系統(tǒng)中的算法步驟：

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

輸入：初始關(guān)聯(lián)值G’0={（u，n），u∈U，n∈N}

重復(fù)以下步驟：

1.在定義2中選擇一個(gè)次梯度定義

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

3.t←t＋1；

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

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

3　仿真結(jié)果

表格1　仿真參數(shù)

為驗(yàn)證提出的算法的性能，進(jìn)行了下述針對(duì)LTE與WLAN組成的異構(gòu)網(wǎng)絡(luò)的仿真。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)參見圖1所示場(chǎng)景。其中AP均勻地分布在LTE基站的覆蓋范圍內(nèi)，表格1個(gè)用戶，仿真時(shí)的一次迭代表示分別進(jìn)行了一次LTE和WLAN系統(tǒng)的迭代算法。圖2展示了該算法對(duì)系統(tǒng)吞吐量的改善情況，橫坐標(biāo)表示迭代的次數(shù)，為保證公平，縱坐標(biāo)為式（9）所示的效用值，從圖2可以看出該算法的收斂速度很快，基本上一次完整的迭代就能得到局部最優(yōu)解。

圖2　算法收斂速度仿真圖

圖3　每個(gè)AP接入點(diǎn)吞吐量前后對(duì)比圖

圖4　用戶AP關(guān)聯(lián)關(guān)系前后對(duì)比圖

圖3展示了5個(gè)AP站點(diǎn)經(jīng)過算法調(diào)整前后的吞吐量對(duì)比圖，第6組數(shù)據(jù)是整個(gè)WLAN網(wǎng)絡(luò)的吞吐量（前5組數(shù)據(jù)之和）。圖4展示了當(dāng)用戶數(shù)為15時(shí)，應(yīng)用該算法進(jìn)行節(jié)點(diǎn)選擇前后的關(guān)聯(lián)關(guān)系對(duì)比圖，因?yàn)橹挥?個(gè)LTE基站，因此與信道的關(guān)聯(lián)關(guān)系沒有表示出來。其中，圖4（a）所示的仿真初始狀態(tài)是通過接入點(diǎn)與用戶之間的傳輸速率大小來選擇AP的。

從圖3和圖4可以看出用戶最初根據(jù)傳輸速率進(jìn)行AP選擇，每個(gè)AP的負(fù)載不均衡，有的AP沒有接入用戶，應(yīng)用本文提出的算法之后AP負(fù)載更加均衡協(xié)調(diào)，且最終整個(gè)網(wǎng)絡(luò)的吞吐量也有明顯提高。

4　結(jié)　論

文中針對(duì)LTE和WLAN組成的異構(gòu)網(wǎng)絡(luò)提出了一種在用戶同時(shí)接入兩個(gè)系統(tǒng)的場(chǎng)景下基于比例公平的資源分配算法。該算法可以在兩個(gè)系統(tǒng)中同時(shí)應(yīng)用，從而達(dá)到整體網(wǎng)絡(luò)吞吐量得到改善的目標(biāo)。從仿真結(jié)果來看，該算法收斂速度快，而且整體的吞吐量得到了顯著的提升。

[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，F(xiàn)ast 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稿件編號(hào)：201603397

國(guó)家自然科學(xué)基金資助項(xiàng)目（61231009）；國(guó)家科技重大項(xiàng)目（2014ZX03001024）；上海市科教委項(xiàng)目（14ZR1439700）

俞 涵（1992—），女，江蘇南通人，碩士。研究方向：下一代移動(dòng)通信網(wǎng)絡(luò)。