一種多無線電系統(tǒng)中基于公平性和精細化帶寬分配的資源分配算法

潘 甦曹跑跑劉勝美

①(南京郵電大學無線通信江蘇省重點實驗室 南京 210003)

②(東南大學移動通信國家重點實驗室 南京 210096)

一種多無線電系統(tǒng)中基于公平性和精細化帶寬分配的資源分配算法

潘 甦*①②曹跑跑①劉勝美①

①(南京郵電大學無線通信江蘇省重點實驗室 南京 210003)

②(東南大學移動通信國家重點實驗室 南京 210096)

該文針對以OFDMA(Orthogonal Frequency Division Multiple Access)為多址接入方式的多無線電系統(tǒng)中用戶比例公平性和系統(tǒng)效率問題進行了研究，提出一種聯(lián)合資源分配算法，不僅保證了用戶比例公平性下系統(tǒng)的吞吐量，還充分考慮了分配的帶寬是子信道帶寬整倍數(shù)的特點，對分配給每個終端的帶寬進行子信道整數(shù)倍調(diào)整。最后通過仿真對比，從系統(tǒng)吞吐量和公平性兩方面給出了算法的性能。

多無線電系統(tǒng)；聯(lián)合資源分配；比例公平性；子信道帶寬整數(shù)倍；最優(yōu)化

1 引言

隨著無線通信的飛速發(fā)展，出現(xiàn)了多種無線網(wǎng)絡以及多模終端，下一代無線通信將是一種融合了多種無線接入技術(Radio Access Technology, RAT),如Wimax, LTE, WCDMA, TD-SCDMA, WLAN等的異構無線網(wǎng)絡[1]。異構網(wǎng)絡融合的關鍵在于將不同接入網(wǎng)絡的無線資源進行聯(lián)合管理，實現(xiàn)頻譜資源在各無線接入網(wǎng)絡之間的共享，從而提高頻譜資源利用率，提高系統(tǒng)吞吐量。在異構網(wǎng)絡中有多種多址接入技術，其中OFDMA技術廣泛應用于各種主流無線網(wǎng)絡(LTE, Wimax等)中，由于底層資源都是基于OFDMA的時頻塊，所以使用OFDMA方式的異構網(wǎng)絡更容易進行資源聯(lián)合管理[25]-。

目前對于異構網(wǎng)絡資源分配有著廣泛的研究，大致可分為兩類，一類是垂直切換[68]-，用戶同一時刻只能接入一種網(wǎng)絡，這類算法根據(jù)接收信號強度、用戶偏好、移動速度等多種因素做出判決選擇切換；另一類是并行接入，用戶可以同時接入多種異構網(wǎng)絡，通常情況下，并行接入方法的系統(tǒng)吞吐量要大于單一網(wǎng)絡接入的系統(tǒng)吞吐量[8]。本文重點研究并行接入場景下的資源分配，文獻[9]在異構網(wǎng)絡中提出了一種基于最大化上行吞吐量的聯(lián)合資源分配算法；文獻[10]在文獻[9]的基礎上進行了深入研究，改進了求解中使用的牛頓迭代法，這些研究的總體最優(yōu)化目標都是最大化系統(tǒng)吞吐量，信道質量較好的用戶能夠得到較大的網(wǎng)絡帶寬，這對于信道質量差的用戶很不公平；文獻[11]提出了一種考慮公平性的分為兩步的資源分配算法，首先根據(jù)信道質量為每一個用戶分配子載波，然后再進行發(fā)射功率的分配，這種非聯(lián)合資源分配算法必定會損失部分系統(tǒng)吞吐量；總體來說，以上涉及到OFDMA異構網(wǎng)絡系統(tǒng)的文獻中都沒有很好地解決公平性和系統(tǒng)效率之間的關系，同時假設了帶寬是連續(xù)性變量且分配時沒有考慮帶寬是子信道整數(shù)倍的特點。

本文的創(chuàng)新點主要有以下兩點：一是考慮了多系統(tǒng)用戶聯(lián)合資源分配公平性和系統(tǒng)效率平衡的問題，提出了一種新的系統(tǒng)吞吐量損失較小的公平資源分配優(yōu)化模型，最大限度優(yōu)化公平效率問題；二是考慮了在以OFDMA為多址方式的系統(tǒng)中網(wǎng)絡端分配給用戶的帶寬是子信道帶寬整倍數(shù)的特點，對收集取整后的剩余帶寬進行了重新分配，充分利用了帶寬資源，提高了系統(tǒng)吞吐量。

2 系統(tǒng)模型

系統(tǒng)模型如圖1所示，同一空間存在多種不同類型的無線網(wǎng)絡重疊覆蓋，網(wǎng)絡系統(tǒng)中有t(t=1,2,…,T)種無線網(wǎng)絡，這些無線網(wǎng)絡均采用OFDMA多址接入技術，但它們采用不同的網(wǎng)絡技術(Network Technology, NT)，屬于不同的網(wǎng)絡類型(如LTE, Wimax等等)；網(wǎng)絡系統(tǒng)中有s(s=1 2,…,S)個用戶終端(User Equipment, UE), UE均為多模終端，即具有處理不同無線接入技術的能力，并能夠同時接入多種無線網(wǎng)絡。

本文所考慮的異構無線網(wǎng)絡采用分流控制方法，將業(yè)務分為若干個子業(yè)務流分配給不同的無線網(wǎng)絡進行傳輸，最終在用戶終端重聚，這種方式能夠平衡網(wǎng)絡負載，大幅提高業(yè)務吞吐量[12]。

數(shù)據(jù)傳輸過程中，每一種NT都會為各個UE分配不同的帶寬資源和發(fā)射功率，假設信道衰落是慢變的且網(wǎng)絡t分配給用戶s的子信道帶寬是連續(xù)的，則異構系統(tǒng)中UEs(s=1,2,…,S)的吞吐量可表示為[9]：

圖1 系統(tǒng)模型

其中rst為UEs在NTt內(nèi)的數(shù)據(jù)速率，ηst(0≤ηst≤1)為UEs到NTt的平均誤比特率[13]，其值為遠遠小于1的正數(shù)，βt(0≤βt≤1)為NTt的系統(tǒng)效率[14]，其值和信道的編碼方式有關，xst為網(wǎng)絡NTt分配給UE的帶寬，p為UE在NT的發(fā)射功率，表sstst示信道傳輸增益，Nst表示此時的噪聲功率譜密度。

下面我們將提出一種比例公平性算法，即使得速率sR在不同的用戶間在某種意義上是公平的，同時使得系統(tǒng)總速率在一定意義上最大。

3 保證用戶比例公平性的聯(lián)合資源分配算法

首先定義比例公平，文獻[15]提出了一種單系統(tǒng)MAC層中調(diào)度比例公平性的定義，我們將其擴展到異構分流系統(tǒng)的資源分配中來。

定義1 比例公平性：多無線電系統(tǒng)中，用戶的數(shù)據(jù)傳輸速率分配R(J)(…)是比例公平的，當且僅當對于任何其它可行的資源分配算法R(K)(…)來說，式(3)成立：

現(xiàn)在我們需要做的是找到一種資源分配方法使得式(3)成立，大多數(shù)文獻在考慮公平性時，沒有考慮在多無線電系統(tǒng)中同時兼顧公平性和系統(tǒng)效率的問題，我們提出了一種方法，使得系統(tǒng)吞吐量在一定意義下最大，同時滿足式(3)。 為此我們定義函數(shù)F(R(J))：

定義2 F(R(J))：

F(R(J))是用戶對數(shù)速率的和，一定意義上反映了系統(tǒng)吞吐量的大小。

將式(3)進行變形可得其中?代表對函數(shù)求取一階導數(shù)，因此我們將得到如下定理：

定理1 比例公平性資源分配算法：存在這樣一種比例公平性資源分配算法，它使得用戶對數(shù)速率的和F(R(J))最大，同時滿足比例公平性要求。

證明 首先證明這個最大化問題有唯一解。函數(shù)F(R(J))是凹函數(shù)(對數(shù)函數(shù)是凹函數(shù))的線性組合，所以它本身也是凹函數(shù)，又因為可行集(網(wǎng)絡帶寬和發(fā)射功率的限制條件)是凸集，所以函數(shù)F(R(J))的任何局部最大值一定是全局最大值。一方面，通過求F(R(J))的二次導數(shù)可知其Hesse矩陣是負定的，因此F(R(J))是嚴格的凹函數(shù)，而一個嚴格的凹函數(shù)在凸集上最多只有一個最大值；另一方面，F(xiàn)(R(J))是連續(xù)性的，并且其可行域是一個有界限的集合(實數(shù)集合的子集)，所以它在可行域上至少有一個最大值。上述兩點證明了F(R(J))在可行域上有且僅有一個最大值，并且任何局部最大值一定就是全局最大值。 證畢

下面證明F(R(J))最大化時的唯一解也滿足比例公平性要求。假設對于任意δ，R(J)+δ均是可行解。

由于F(R(J))是嚴格的凹函數(shù)，?2F(R(J))是一個負數(shù)，所以對于充分小的||δ||來說，式(7)成立：

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

同樣，假設函數(shù)F(R(J))在R(J)處有全局最大值，令R(K)是任意一個可行解，把D記作：

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

由假設可知函數(shù)F(R(J))在R(J)處有全局最大值，所以D≤0，由式(3)，式(5)和式(9)知用戶數(shù)據(jù)傳輸速率分配R(J)是比例公平的。 證畢

因此我們得到了一種考慮了公平性和效率平衡的多系統(tǒng)用戶聯(lián)合資源分配算法，本文的最優(yōu)化問題可抽象為式(11)所示。約束條件(d)是本文充分考慮了帶寬為子信道整數(shù)倍的特點后得出的，也是區(qū)別于其他文獻的地方。式(11)中優(yōu)化目標為關于{x,p}的凹函數(shù)，由文獻[11]知其局部最優(yōu)解即為全局最優(yōu)解。

4 優(yōu)化問題求解

對于以上最優(yōu)化問題的求解，本文采取的策略是先忽略約束條件(d)，求取近似最優(yōu)解，然后再考慮網(wǎng)絡端分配給用戶的帶寬是子信道帶寬整倍數(shù)的特點并收集取整后的剩余帶寬進行重新分配，以滿足條件(d)的需求。本文通過梯度法求得近似最優(yōu)解。

本文最優(yōu)化問題的拉格朗日函數(shù)為

其中λ=· ·λ1λ2…λm· ·是與接入點帶寬分配約束相關的乘子向量，而μ=[μ1μ2…μn]是與用戶端發(fā)射功率約束相關的乘子向量。

利用KKT條件[16]求得帶寬分配與功率分配之間的關系，其中[a ]+=max{a,0}。

本文采用梯度法更新帶寬[16]，選取合適的步長a則xst,?s,t可收斂：

在已知xst,?s,t下，根據(jù)式(13)，則可求得pst,?s,t。

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

其中k為迭代輪次，b和c為迭代步長。通過選取合適的迭代步長理論上可以保證收斂。

由式(13)我們可以看到，功率分配stp，帶寬分配stx和用戶當前速率sR之間相互關聯(lián)，因此需要采用式(17)的迭代方法求解。sR更新如下：

其中m為速率迭代次數(shù)，d是UEm速率更新迭代步長。通過選取合適的迭代步長可以保證速率的收斂性。

綜上所述，本文提出了聯(lián)合資源分配算法，主要由兩部分組成：步驟(1)～步驟(6)在忽略條件(d)的前提下，通過梯度法求得近似最優(yōu)解；步驟(7)～步驟(9)考慮條件(d)，將網(wǎng)絡分配帶寬調(diào)整為子信道帶寬的整數(shù)倍。算法具體實現(xiàn)步驟示于表1。

可以看出，通過以上算法，得到了聯(lián)合功率和帶寬分配問題的近似最優(yōu)解，并在考慮了公平性之后對帶寬資源進行了相應的調(diào)整。

5 仿真結果和分析

考慮到現(xiàn)實用戶終端功率的差異性，本文仿真過程中為不同的UE共隨機初始化了5個不同的最大功率值20 mW, 25 mW, 30 mW, 35 mW, 40 mW，選擇了Wimax, TD-LTE, FDD-LTE 3種不同的網(wǎng)絡，總帶寬分別為10 MHz, 20 MHz, 30 MHz。為了說明算法性能，本文對以下幾種算法進行了仿真對比：

對比算法1：最大化系統(tǒng)吞吐量算法[9]，為了貼近實際，將該算法中的帶寬調(diào)整為子信道整數(shù)倍。

本文算法：考慮公平性和吞吐量的平衡，對帶寬進行子信道整數(shù)倍調(diào)整，并收集剩余帶寬重新分配。

表1 聯(lián)合資源分配算法實現(xiàn)步驟

對比算法2：考慮公平性，對帶寬進行向下取整，但沒有收集剩余帶寬重新分配的本文算法。

對比算法3：分為兩步的資源分配算法[11]，首先根據(jù)信道質量為每一個用戶分配子載波，然后再進行發(fā)射功率的分配，并將帶寬調(diào)整為子信道整數(shù)倍。

圖2給出了4種算法下系統(tǒng)吞吐量隨著用戶數(shù)目的變化曲線。可以看出，4種算法的系統(tǒng)吞吐量都隨著用戶數(shù)目的增加而增大，其中曲線最高的是對比算法1，因為此算法的唯一優(yōu)化目標就是最大化系統(tǒng)吞吐量，在此種算法下，信道質量較好的用戶能夠得到較大的網(wǎng)絡帶寬，整個系統(tǒng)充分利用了帶寬資源；本文算法的系統(tǒng)吞吐量略低于對比算法1，一方面本文算法考慮了公平性，信道質量差的用戶對于帶寬資源的利用率不高，導致了系統(tǒng)吞吐量有所下降，另一方面本文算法調(diào)整帶寬為子信道整數(shù)倍之后又收集了剩余帶寬進行重新分配，充分利用了帶寬資源，提高了系統(tǒng)吞吐量；對比算法2的系統(tǒng)吞吐量低于本文算法，因為其未收集剩余帶寬進行重新分配，浪費了一定的帶寬資源；對比算法3的系統(tǒng)吞吐量最低，因為這種非聯(lián)合資源分配算法必定會損失部分系統(tǒng)吞吐量，而且此算法也未收集剩余帶寬重新分配，沒有充分利用帶寬資源；總的來說，本文算法既考慮了公平性，又很好地利用了剩余帶寬，貼近現(xiàn)實應用。

為了衡量用戶比例公平性，我們引入Jain公平性因子(Fairness Index, FI)[17]來表示算法的公平性，F(xiàn)I定義為

可以看出，F(xiàn)I為小于1的正數(shù)，并且其取值越接近于1，說明算法的用戶比例公平性越好。

圖2 系統(tǒng)吞吐量隨用戶數(shù)目變化曲線

圖3給出了4種算法在不同用戶數(shù)下公平性因子的變化曲線。圖3中可以看出，在不同用戶數(shù)目下，本文算法的用戶公平性因子是最大的，一方面是因為本文算法使用了數(shù)據(jù)傳輸速率的對數(shù)和形式，考慮了用戶比例公平性，另一方面本文算法還進行了傾向于用戶比例公平性的帶寬調(diào)整過程；對比算法2的公平性也明顯高于其他算法，正是因為該算法在求解最大化系統(tǒng)吞吐量的過程中考慮了用戶公平性問題；對比算法3的公平性略低于本文算法和對比算法2，雖然此算法系統(tǒng)吞吐量不大，但是它考慮了公平性，因此公平性因子明顯大于對比算法1；對比算法1的公平性最低，這是因為該算法中信道質量較好的用戶總是能夠得到較大的網(wǎng)絡帶寬，沒有考慮公平性因素；仿真結果說明了帶寬調(diào)整的有效性。

圖3 公平性因子隨用戶數(shù)目變化曲線

6 結束語

本文針對以OFDMA為多址接入方式的多無線電系統(tǒng)中用戶比例公平性和系統(tǒng)效率問題進行了研究，提出了一種聯(lián)合功率和系統(tǒng)帶寬的資源分配算法，既保證了用戶比例公平性，又在一定程度上優(yōu)化了吞吐量性能，同時考慮了分配的帶寬是子信道帶寬整倍數(shù)的特點，對分配給每個終端的帶寬進行整數(shù)倍調(diào)整，以求貼近OFDMA系統(tǒng)的實際，并充分利用取整后的剩余帶寬。仿真結果表明，本文算法在吞吐量相對損失較小的情況下，保持了較高的用戶公平性，最大限度優(yōu)化了公平性和系統(tǒng)效率問題，同時也說明了本文所提帶寬調(diào)整過程的有效性。

[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] 趙遠林. 無線泛在網(wǎng)絡下虛擬終端系統(tǒng)若干關鍵技術研究[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年生，教授，博士，研究方向為無線通信、移動互聯(lián)網(wǎng)技術.

曹跑跑： 男，1989年生，碩士生，研究方向為無線通信.

劉勝美： 女，1977年生，副教授，博士，研究方向為異構無線網(wǎng)絡移動性管理、資源管理、運動預測等關鍵技術研究.

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)和江蘇省工業(yè)支撐計劃(NJHB2011-10)資助課題

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