一种多无线电系统中基于公平性和精细化带宽分配的资源分配算法

潘 甦曹跑跑刘胜美

①(南京邮电大学无线通信江苏省重点实验室 南京 210003)

②(东南大学移动通信国家重点实验室 南京 210096)

一种多无线电系统中基于公平性和精细化带宽分配的资源分配算法

潘 甦*①②曹跑跑①刘胜美①

①(南京邮电大学无线通信江苏省重点实验室 南京 210003)

②(东南大学移动通信国家重点实验室 南京 210096)

该文针对以OFDMA(Orthogonal Frequency Division Multiple Access)为多址接入方式的多无线电系统中用户比例公平性和系统效率问题进行了研究，提出一种联合资源分配算法，不仅保证了用户比例公平性下系统的吞吐量，还充分考虑了分配的带宽是子信道带宽整倍数的特点，对分配给每个终端的带宽进行子信道整数倍调整。最后通过仿真对比，从系统吞吐量和公平性两方面给出了算法的性能。

多无线电系统；联合资源分配；比例公平性；子信道带宽整数倍；最优化

1 引言

随着无线通信的飞速发展，出现了多种无线网络以及多模终端，下一代无线通信将是一种融合了多种无线接入技术(Radio Access Technology, RAT),如Wimax, LTE, WCDMA, TD-SCDMA, WLAN等的异构无线网络[1]。异构网络融合的关键在于将不同接入网络的无线资源进行联合管理，实现频谱资源在各无线接入网络之间的共享，从而提高频谱资源利用率，提高系统吞吐量。在异构网络中有多种多址接入技术，其中OFDMA技术广泛应用于各种主流无线网络(LTE, Wimax等)中，由于底层资源都是基于OFDMA的时频块，所以使用OFDMA方式的异构网络更容易进行资源联合管理[25]-。

目前对于异构网络资源分配有着广泛的研究，大致可分为两类，一类是垂直切换[68]-，用户同一时刻只能接入一种网络，这类算法根据接收信号强度、用户偏好、移动速度等多种因素做出判决选择切换；另一类是并行接入，用户可以同时接入多种异构网络，通常情况下，并行接入方法的系统吞吐量要大于单一网络接入的系统吞吐量[8]。本文重点研究并行接入场景下的资源分配，文献[9]在异构网络中提出了一种基于最大化上行吞吐量的联合资源分配算法；文献[10]在文献[9]的基础上进行了深入研究，改进了求解中使用的牛顿迭代法，这些研究的总体最优化目标都是最大化系统吞吐量，信道质量较好的用户能够得到较大的网络带宽，这对于信道质量差的用户很不公平；文献[11]提出了一种考虑公平性的分为两步的资源分配算法，首先根据信道质量为每一个用户分配子载波，然后再进行发射功率的分配，这种非联合资源分配算法必定会损失部分系统吞吐量；总体来说，以上涉及到OFDMA异构网络系统的文献中都没有很好地解决公平性和系统效率之间的关系，同时假设了带宽是连续性变量且分配时没有考虑带宽是子信道整数倍的特点。

本文的创新点主要有以下两点：一是考虑了多系统用户联合资源分配公平性和系统效率平衡的问题，提出了一种新的系统吞吐量损失较小的公平资源分配优化模型，最大限度优化公平效率问题；二是考虑了在以OFDMA为多址方式的系统中网络端分配给用户的带宽是子信道带宽整倍数的特点，对收集取整后的剩余带宽进行了重新分配，充分利用了带宽资源，提高了系统吞吐量。

2 系统模型

系统模型如图1所示，同一空间存在多种不同类型的无线网络重叠覆盖，网络系统中有t(t=1,2,…,T)种无线网络，这些无线网络均采用OFDMA多址接入技术，但它们采用不同的网络技术(Network Technology, NT)，属于不同的网络类型(如LTE, Wimax等等)；网络系统中有s(s=1 2,…,S)个用户终端(User Equipment, UE), UE均为多模终端，即具有处理不同无线接入技术的能力，并能够同时接入多种无线网络。

本文所考虑的异构无线网络采用分流控制方法，将业务分为若干个子业务流分配给不同的无线网络进行传输，最终在用户终端重聚，这种方式能够平衡网络负载，大幅提高业务吞吐量[12]。

数据传输过程中，每一种NT都会为各个UE分配不同的带宽资源和发射功率，假设信道衰落是慢变的且网络t分配给用户s的子信道带宽是连续的，则异构系统中UEs(s=1,2,…,S)的吞吐量可表示为[9]：

图1 系统模型

其中rst为UEs在NTt内的数据速率，ηst(0≤ηst≤1)为UEs到NTt的平均误比特率[13]，其值为远远小于1的正数，βt(0≤βt≤1)为NTt的系统效率[14]，其值和信道的编码方式有关，xst为网络NTt分配给UE的带宽，p为UE在NT的发射功率，表sstst示信道传输增益，Nst表示此时的噪声功率谱密度。

下面我们将提出一种比例公平性算法，即使得速率sR在不同的用户间在某种意义上是公平的，同时使得系统总速率在一定意义上最大。

3 保证用户比例公平性的联合资源分配算法

首先定义比例公平，文献[15]提出了一种单系统MAC层中调度比例公平性的定义，我们将其扩展到异构分流系统的资源分配中来。

定义1 比例公平性：多无线电系统中，用户的数据传输速率分配R(J)(…)是比例公平的，当且仅当对于任何其它可行的资源分配算法R(K)(…)来说，式(3)成立：

现在我们需要做的是找到一种资源分配方法使得式(3)成立，大多数文献在考虑公平性时，没有考虑在多无线电系统中同时兼顾公平性和系统效率的问题，我们提出了一种方法，使得系统吞吐量在一定意义下最大，同时满足式(3)。 为此我们定义函数F(R(J))：

定义2 F(R(J))：

F(R(J))是用户对数速率的和，一定意义上反映了系统吞吐量的大小。

将式(3)进行变形可得其中∇代表对函数求取一阶导数，因此我们将得到如下定理：

定理1 比例公平性资源分配算法：存在这样一种比例公平性资源分配算法，它使得用户对数速率的和F(R(J))最大，同时满足比例公平性要求。

证明 首先证明这个最大化问题有唯一解。函数F(R(J))是凹函数(对数函数是凹函数)的线性组合，所以它本身也是凹函数，又因为可行集(网络带宽和发射功率的限制条件)是凸集，所以函数F(R(J))的任何局部最大值一定是全局最大值。一方面，通过求F(R(J))的二次导数可知其Hesse矩阵是负定的，因此F(R(J))是严格的凹函数，而一个严格的凹函数在凸集上最多只有一个最大值；另一方面，F(R(J))是连续性的，并且其可行域是一个有界限的集合(实数集合的子集)，所以它在可行域上至少有一个最大值。上述两点证明了F(R(J))在可行域上有且仅有一个最大值，并且任何局部最大值一定就是全局最大值。 证毕

下面证明F(R(J))最大化时的唯一解也满足比例公平性要求。假设对于任意δ，R(J)+δ均是可行解。

由于F(R(J))是严格的凹函数，∇2F(R(J))是一个负数，所以对于充分小的||δ||来说，式(7)成立：

由式(6)可知F(R(J)+δ)-F(R(J))＜0，所以函数F(R(J))在R(J)处有局部最大值，也就是全局最大值。

同样，假设函数F(R(J))在R(J)处有全局最大值，令R(K)是任意一个可行解，把D记作：

由于可行集是凸集，所以D又可以表示为

由假设可知函数F(R(J))在R(J)处有全局最大值，所以D≤0，由式(3)，式(5)和式(9)知用户数据传输速率分配R(J)是比例公平的。 证毕

因此我们得到了一种考虑了公平性和效率平衡的多系统用户联合资源分配算法，本文的最优化问题可抽象为式(11)所示。约束条件(d)是本文充分考虑了带宽为子信道整数倍的特点后得出的，也是区别于其他文献的地方。式(11)中优化目标为关于{x,p}的凹函数，由文献[11]知其局部最优解即为全局最优解。

4 优化问题求解

对于以上最优化问题的求解，本文采取的策略是先忽略约束条件(d)，求取近似最优解，然后再考虑网络端分配给用户的带宽是子信道带宽整倍数的特点并收集取整后的剩余带宽进行重新分配，以满足条件(d)的需求。本文通过梯度法求得近似最优解。

本文最优化问题的拉格朗日函数为

其中λ=· ·λ1λ2…λm· ·是与接入点带宽分配约束相关的乘子向量，而μ=[μ1μ2…μn]是与用户端发射功率约束相关的乘子向量。

利用KKT条件[16]求得带宽分配与功率分配之间的关系，其中[a ]+=max{a,0}。

本文采用梯度法更新带宽[16]，选取合适的步长a则xst,∀s,t可收敛：

在已知xst,∀s,t下，根据式(13)，则可求得pst,∀s,t。

同样采用梯度法更新拉格朗日乘子λ和μ，如下：

其中k为迭代轮次，b和c为迭代步长。通过选取合适的迭代步长理论上可以保证收敛。

由式(13)我们可以看到，功率分配stp，带宽分配stx和用户当前速率sR之间相互关联，因此需要采用式(17)的迭代方法求解。sR更新如下：

其中m为速率迭代次数，d是UEm速率更新迭代步长。通过选取合适的迭代步长可以保证速率的收敛性。

综上所述，本文提出了联合资源分配算法，主要由两部分组成：步骤(1)～步骤(6)在忽略条件(d)的前提下，通过梯度法求得近似最优解；步骤(7)～步骤(9)考虑条件(d)，将网络分配带宽调整为子信道带宽的整数倍。算法具体实现步骤示于表1。

可以看出，通过以上算法，得到了联合功率和带宽分配问题的近似最优解，并在考虑了公平性之后对带宽资源进行了相应的调整。

5 仿真结果和分析

考虑到现实用户终端功率的差异性，本文仿真过程中为不同的UE共随机初始化了5个不同的最大功率值20 mW, 25 mW, 30 mW, 35 mW, 40 mW，选择了Wimax, TD-LTE, FDD-LTE 3种不同的网络，总带宽分别为10 MHz, 20 MHz, 30 MHz。为了说明算法性能，本文对以下几种算法进行了仿真对比：

对比算法1：最大化系统吞吐量算法[9]，为了贴近实际，将该算法中的带宽调整为子信道整数倍。

本文算法：考虑公平性和吞吐量的平衡，对带宽进行子信道整数倍调整，并收集剩余带宽重新分配。

表1 联合资源分配算法实现步骤

对比算法2：考虑公平性，对带宽进行向下取整，但没有收集剩余带宽重新分配的本文算法。

对比算法3：分为两步的资源分配算法[11]，首先根据信道质量为每一个用户分配子载波，然后再进行发射功率的分配，并将带宽调整为子信道整数倍。

图2给出了4种算法下系统吞吐量随着用户数目的变化曲线。可以看出，4种算法的系统吞吐量都随着用户数目的增加而增大，其中曲线最高的是对比算法1，因为此算法的唯一优化目标就是最大化系统吞吐量，在此种算法下，信道质量较好的用户能够得到较大的网络带宽，整个系统充分利用了带宽资源；本文算法的系统吞吐量略低于对比算法1，一方面本文算法考虑了公平性，信道质量差的用户对于带宽资源的利用率不高，导致了系统吞吐量有所下降，另一方面本文算法调整带宽为子信道整数倍之后又收集了剩余带宽进行重新分配，充分利用了带宽资源，提高了系统吞吐量；对比算法2的系统吞吐量低于本文算法，因为其未收集剩余带宽进行重新分配，浪费了一定的带宽资源；对比算法3的系统吞吐量最低，因为这种非联合资源分配算法必定会损失部分系统吞吐量，而且此算法也未收集剩余带宽重新分配，没有充分利用带宽资源；总的来说，本文算法既考虑了公平性，又很好地利用了剩余带宽，贴近现实应用。

为了衡量用户比例公平性，我们引入Jain公平性因子(Fairness Index, FI)[17]来表示算法的公平性，FI定义为

可以看出，FI为小于1的正数，并且其取值越接近于1，说明算法的用户比例公平性越好。

图2 系统吞吐量随用户数目变化曲线

图3给出了4种算法在不同用户数下公平性因子的变化曲线。图3中可以看出，在不同用户数目下，本文算法的用户公平性因子是最大的，一方面是因为本文算法使用了数据传输速率的对数和形式，考虑了用户比例公平性，另一方面本文算法还进行了倾向于用户比例公平性的带宽调整过程；对比算法2的公平性也明显高于其他算法，正是因为该算法在求解最大化系统吞吐量的过程中考虑了用户公平性问题；对比算法3的公平性略低于本文算法和对比算法2，虽然此算法系统吞吐量不大，但是它考虑了公平性，因此公平性因子明显大于对比算法1；对比算法1的公平性最低，这是因为该算法中信道质量较好的用户总是能够得到较大的网络带宽，没有考虑公平性因素；仿真结果说明了带宽调整的有效性。

图3 公平性因子随用户数目变化曲线

6 结束语

本文针对以OFDMA为多址接入方式的多无线电系统中用户比例公平性和系统效率问题进行了研究，提出了一种联合功率和系统带宽的资源分配算法，既保证了用户比例公平性，又在一定程度上优化了吞吐量性能，同时考虑了分配的带宽是子信道带宽整倍数的特点，对分配给每个终端的带宽进行整数倍调整，以求贴近OFDMA系统的实际，并充分利用取整后的剩余带宽。仿真结果表明，本文算法在吞吐量相对损失较小的情况下，保持了较高的用户公平性，最大限度优化了公平性和系统效率问题，同时也说明了本文所提带宽调整过程的有效性。

[1] Piamrat K, Ksentini A, Bonnin J M, et al.. Radio resource management in emerging heterogeneous wireless networks[J]. Computer Communications, 2011, 34(9): 1066-1076.

[2] Kim Sung-yeon, Jeong-ahn Kwon, and Lee Jang-won. Resource allocation for the multi-cell OFDMA system and its capacity bounds[C]. 2013 11th International Symposium on Modeling & Optimization in Mobile, Ad Hoc & Wireless Networks (WiOpt), Tsukuba Science City, Japan, 2013: 326-332.

[3] Bashar S and Zhi Ding. Admission control and resource allocation in a heterogeneous OFDMA wireless network[J]. IEEE Transactions on Wireless Communications, 2009, 8(8): 4200-4210.

[4] Zhang Xing, Fu Lei, Wu Xin, et al.. On the study of radio resource allocation of heterogeneous services with soft QoS traffics in OFDMA-based wireless networks[C]. 2010 IEEE 10th International Conference on Computer and Information Technology (CIT), Bradford, UK, 2010: 2556-2561.

[5] Zhu Hui-ling. Radio resource allocation for OFDMA systems in high speed environments[J]. IEEE Journal on Selected Areas in Communications, 2012, 30(4): 748-759.

[6] Ajay, Gurjar D, and Purohit N. An optimized network selection scheme for heterogeneous wireless networks[C]. 2013 Sixth International Conference on Contemporary Computing (IC3), Noida, India, 2013: 196-201.

[7] Sibanda C C L and Bagula A B. Network selection for mobile nodes in heterogeneous wireless networks using Knapsack problem Dynamic algorithms[C]. 2012 20th, Telecommunications Forum (TELFOR), Belgrade, Serbia, 2012: 174-177.

[8] Han Peng, Tian Hua, Xie Wei, et al.. Network selection in heterogeneous wireless networks using learning automata[C]. 2012 International Conference on Wireless Communications & Signal Processing (WCSP), Huangshan, 2012: 1-6.

[9] Choi Yonghoon, Kim Hoon, Han Sang-wook, et al.. Joint resource allocation for parallel multi-radio access in heterogeneous wireless networks[J]. IEEE Transactions on Wireless Communications, 2010, 9(11): 3324-3329.

[10] Sundar R S and Kumar S N. Performance improvement of heterogeneous wireless networks using modified newton method[J]. International Journal of Software Engineering & Applications (IJSEA), 2012, 3(3): 79-90.

[11] Shaat M and Bader F. Efficient resource allocation algorithm for uplink in multicarrier-based cognitive radio networks with fairness consideration[J]. IET Communications, 2011, 5(16): 2328-2338.

[12] 赵远林. 无线泛在网络下虚拟终端系统若干关键技术研究[D].[硕士论文], 南京邮电大学, 2013. Zhao Yuan-lin. Research on several key technologies of virtual terminal system in wireless ubiquitous networks[D]. [Master dissertation], Nanjing University of Posts and Telecommunications, 2013.

[13] Stoer J, Bulirsch R, Bartels R, et al.. An Introduction to Numerical Analysis[M]. 3rd Edition, Germany, Springer-Verlag, 2002: 289-363.

[14] 3G Americas white paper (2008, Sep.). EDGE, HSPA, LTE –Broadband Innovation[OL]. Available: http://www. 3gamericas.org. 2008.

[15] Kelly F P, Maulloo A K, and Tan D K H. Rate control for communication networks: shadow prices, proportional fairness and stability[J]. The Journal of the Operational Research Society, 1998, 49(3): 237-252.

[16] Stephen Boyd and Lieven Vandenberghe. Convex Optimization[M]. New York, Cambridge University Press, 2004: 466-483.

[17] Jain R, Hawe W, and Chiu D. A quantitative Measure of fairness and discrimination for resource allocation in shared computer systems[R]. DEC-TR-301. Maynard, MA, USA, DEC, 1984.

潘 甦： 男，1969年生，教授，博士，研究方向为无线通信、移动互联网技术.

曹跑跑： 男，1989年生，硕士生，研究方向为无线通信.

刘胜美： 女，1977年生，副教授，博士，研究方向为异构无线网络移动性管理、资源管理、运动预测等关键技术研究.

A Resource Allocation Algorithm Based on Proportional Fairness and Refined Bandwidth Allocation for Multi-radio Systems

Pan Su①②Cao Pao-pao①Liu Sheng-mei①

①(College of Telecommunications and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China)
②(National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China)

A joint resource allocation algorithm is proposed to solve the problem of the proportional fairness and the system efficiency in multi-radio systems based on OFDMA (Orthogonal Frequency Division Multiple Access). The algorithm optimizes the system throughput under the fairness constraint, and considers that the allocated bandwidth should be integer times of the subchannel bandwidth. The bandwidth allocated to each terminal is adjusted according to this consideration. The performance of the proposed algorithm is evaluated by simulations in terms of the system throughput and the fairness.

Multi-radio systems; Joint resource allocation; Proportional fairness; Integer times of the subchannel bandwidth; Optimization

TN929.5

A

1009-5896(2015)02-0399-06

10.11999/JEIT140339

2014-03-13收到，2014-07-09改回

国家自然科学基金(61271235)，东南大学国家移动通信重点实验室开放基金(2011D07)和江苏省工业支撑计划(NJHB2011-10)资助课题

*通信作者：潘甦 supan@njupt.edu.cn