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—），女，江苏南通人，硕士。研究方向：下一代移动通信网络。