毫微微小區(qū)中一種基于分組的資源分配方法*

張海波，彭焦陽，陳善學(xué)

（重慶郵電大學(xué)移動通信技術(shù)重慶市重點實驗室，重慶　400065）

毫微微小區(qū)中一種基于分組的資源分配方法*

張海波，彭焦陽**，陳善學(xué)

（重慶郵電大學(xué)移動通信技術(shù)重慶市重點實驗室，重慶400065）

為有效解決毫微微小區(qū)間（Femtocell）干擾，采用分布式方式對毫微微小區(qū)進行資源管理。首先，對毫微微接入點（FAPs）進行分組?；贚ingo數(shù)學(xué)建模的思想，提出了一種解決分組優(yōu)化問題的算法。該算法在使用分支定界算法尋找最優(yōu)解的同時，通過建立單純形表剪去偏離最優(yōu)解方向的分支；其次，每組選擇一個簇頭為本組內(nèi)FAPs分配資源，為此，提出了新的子信道分配方法，該方法根據(jù)干擾指示矩陣修正子信道分配的情況。仿真結(jié)果表明：和其他算法相比，提出的算法不僅能找到分組優(yōu)化問題的最優(yōu)解，并且效率更高；另外，提出的資源分配算法不僅減小了用戶間干擾，而且提高了戶間速率公平。

毫微微小區(qū)；資源分配；分組優(yōu)化；用戶間干擾；速率公平

1　引　言

研究表明，近90%的數(shù)據(jù)業(yè)務(wù)和60%的語音業(yè)務(wù)是在室內(nèi)發(fā)生的，因此，需要及時解決室內(nèi)信號覆蓋的問題［1］。毫微微小區(qū)技術(shù)作為室內(nèi)無線通信最有前景的技術(shù)之一，近年來得到了廣泛的研究。與傳統(tǒng)的宏蜂窩網(wǎng)絡(luò)架構(gòu)相比，嵌入毫微微基站的網(wǎng)絡(luò)架構(gòu)可以提高系統(tǒng)性能。

文獻［2］采用分割頻譜的方式有效地解決了雙層網(wǎng)絡(luò)間的干擾問題，但是頻譜利用率太低，在LTE系統(tǒng)頻譜資源匱乏情況下，這種算法并不可行。文獻［3］中毫微微基站采用開放式模式，雖然提高了系統(tǒng)部分性能，但是干擾協(xié)調(diào)的方式過于復(fù)雜。文獻［4］提出了一種基于認(rèn)知無線電的分布式博弈資源分配算法，雖然在提高毫微微用戶吞吐量的同時降低了干擾，但是并未針對毫微微小區(qū)間干擾進行分組優(yōu)化。文獻［5-7］提出了一種分組優(yōu)化和聯(lián)合資源分配的方法，雖然減小了同層間的干擾，提高了系統(tǒng)性能，但是并沒有考慮最優(yōu)組尺寸問題。文獻［8］提出了一種基于CVX平臺的Semidefinite Programming（SDP）和隨機舍入算法，雖然考慮了組尺寸的問題，但是所提算法效率并不高，隨著毫微微基站數(shù)目增加，并不一定能找到最優(yōu)解。另外，其資源分配方法不但沒有有效地解決用戶間平均干擾問題，而且也沒有考慮用戶間速率公平問題。

針對上述問題，本文提出了聯(lián)合分組的資源分配算法。首先，構(gòu)造分組優(yōu)化和資源分配問題，由于該問題是NP-hard問題，所以并不能通過毫微微網(wǎng)關(guān)（Femto Gateway，F(xiàn)GW）解決該類問題。因此，將NP-hard問題劃分為兩個子問題，即分組優(yōu)化問題和資源分配問題。其次，毫微微網(wǎng)關(guān)檢測毫微微小區(qū)的信息，根據(jù)分組算法將毫微微基站分配到不同的組。然后，每組選擇一個毫微微基站作為簇頭，負(fù)責(zé)本組的資源分配。本文分別提出了一種Lingo數(shù)學(xué)建模的思想和新的資源分配方法。仿真結(jié)果表明，和其他算法相比，提出的算法不僅找到分組優(yōu)化問題的最優(yōu)解，而且算法求解的效率更高。另外，提出的資源分配算法不僅降低了用戶間的干擾，而且提高了用戶間的速率公平。

2　系統(tǒng)模型

圖1是系統(tǒng)模型圖。在本模型中，毫微微基站被均勻分布在40 m×40 m的范圍里，并且采用閉合模式。假設(shè)毫微微用戶和宏用戶都在室內(nèi)，并且毫微微基站及其所屬用戶之間信道的傳播條件都很好，毫微微基站以平均功率發(fā)送信號，毫微微基站和用戶之間的總路損L1=15.3+37.6lgR+L+Ls-La。其中參數(shù)見表1。

圖1　系統(tǒng)模型圖Fig.1 The model of the femto-macro system

表1　系統(tǒng)參數(shù)Tab.1 System parameters

由于毫微微基站f和它服務(wù)的用戶kf之間距離很短，毫微微基站j和用戶kf之間的信道增益近似等于毫微微基站f和j之間的信道增益，即≈，很顯然毫微微基站間建立的信道增益矩陣是對稱的，即=［8］。

3　構(gòu)造分組優(yōu)化問題

首先建立一個無向圖G1=（V1，E1），V1為頂點，代表毫微微基站，E1為鏈接各頂點的邊，ω和ω是非負(fù)的鏈接權(quán)值［8］。分組優(yōu)化的目標(biāo)是根據(jù)ω的值將彼此間存在嚴(yán)重干擾的毫微微基站分成一組，如果兩個毫微微基站之間存在嚴(yán)重的干擾，那么它們之間的鏈接權(quán)值ω是很大的。同樣地，將ω作為兩個毫微微基站不在同一組的懲罰因子。另外，如果兩個毫微微基站i、j之間有高的信道增益g，那么它們之間也存在很大的干擾。由于信道增益和路損成反比，因此本文可以設(shè)ω=1/L1。

綜上，本文的目的是尋找一種分組方法，使毫微微基站間鏈接權(quán)值和懲罰因子之和最大。令ω的值相同，即ω=ω，ω的取值范圍為F，n=，對任意的ω有

式中∶xi，j是FAP分組指示矩陣，如果FAP i和j在相同的組，xi，j=1，否則，xi，j=0；C1表示毫微微基站i與其本身在一組；C2表示毫微微基站j與i一組；j必與i一組；C3表示毫微微基站i與j一組，j與k一組，i必與k一組；C4表示每組毫微微基站數(shù)不超過可用信道數(shù)；C5表示xi，j為二進制數(shù)。

下面給出本文提出的分組優(yōu)化算法（以下稱算法1）的步驟。

Step 1 將上述優(yōu)化問題轉(zhuǎn)化為Lingo模型［9-11］。

Step 2 運用直接求解程序?qū)δＰ偷牡仁郊s束項進行處理。約束C1中變量的值為固定值，將這些變量處理成常量，并從約束中劃除。

Step 3 運用Lingo識別模型種類，本文為整數(shù)線性規(guī)劃。

Step 4 運用提出的算法如下∶

令c*為當(dāng)前最大目標(biāo)函數(shù)值，p為分支層，p*為相對c*工件的順序，p1為當(dāng)前節(jié)點，即目前需要分支的節(jié)點。

（1）首先初始化，令p=0，p1=A（空集），c*=∞，此時，當(dāng)前節(jié)點為p1（即根節(jié)點）；

（2）從當(dāng)前節(jié)點開始分支得到各個子節(jié)點，計算各子節(jié)點的下界值，按對應(yīng)的各子節(jié)點下界值從小到大排序。更新p，令p=p+1；

（3）以各分支節(jié)點為初始值，建立單純形表。由于最優(yōu)解在邊界取得，且非基變量對應(yīng)的檢驗數(shù)非正［9-10］，對不滿足此條件的分支或偏離邊界方向的分支進行剪支，更新p；

（4）如探測完所有的當(dāng)前節(jié)點，更新p，令p=p-1，轉(zhuǎn)入第7步；否則，將當(dāng)前層（第p層）各子節(jié)點中具有最大下界值的節(jié)點標(biāo)記為Q，并在節(jié)點p1的末尾加入Q所對應(yīng)第p位置上的工件，此時令當(dāng)前節(jié)點為Q轉(zhuǎn)到第5步；

（5）當(dāng)前節(jié)點是同層同父節(jié)點中具有最大下界值的節(jié)點，如果當(dāng)前節(jié)點的下界值不小于C*，則不需要再搜索當(dāng)前節(jié)點和同層同父的節(jié)點。因此，當(dāng)前節(jié)點的父節(jié)點被探測完畢，更新p，令p=p-1。然后去掉p1中最后一個工件，再轉(zhuǎn)第7步；否則，轉(zhuǎn)入第6步；

（6）假設(shè)這時p=n，此時得到一個較優(yōu)順序。令P*=p1，其中c*是當(dāng)前節(jié)點的下界值，更新p，令p=p-1，然后去掉p1中最后一個工件，轉(zhuǎn)入第7步；否則，跳轉(zhuǎn)第2步；

（7）此時如果p≠0，則去掉p1最后一個工件后，再跳轉(zhuǎn)第4步；否則，算法終止。C*就是最優(yōu)的目標(biāo)函數(shù)值，P*即為最優(yōu)解。

4　構(gòu)造資源分配問題

構(gòu)造如下信道分配問題∶

由于文獻［8］中的資源分配方法并未有效地解決用戶間干擾和用戶速率公平問題，因此，在保證用戶數(shù)據(jù)速率的情況下，針對上述問題提出以下方法，即子信道分配算法（以下稱算法2）。

算法2步驟如下∶

（1）將毫微微基站編號，利用算法1將毫微微基站分組；

（2）建立子信道分配指示矩陣T=zeros（N，fue），干擾指示矩陣G=（fue，fue，N）；

（6）從本組的第一個用戶開始，檢測前幾組與該用戶在同一子信道的用戶k1，檢測本組用戶與k1的干擾是否在干擾門限內(nèi)，如超出門限，根據(jù)T判斷k1的子信道數(shù)如大于一，則從k1中剔除干擾的信道；重復(fù)步驟6直至本組用戶檢測完畢。

5　仿真結(jié)果與分析

根據(jù)3GPP標(biāo)準(zhǔn)，仿真系統(tǒng)參數(shù)如表2所示。本文實驗環(huán)境∶軟件為MATLAB R2013a，操作系統(tǒng)為Windows XP，處理器為Intel Pentium Dual CPT T3200 2.00 GHz。

平均速率、平均干擾和速率公平分別為

本次仿真采用平均功率Pfmax/N，其中，K為總的用戶數(shù)。

表2　仿真參數(shù)Tab.2 The simulation parameters

圖2中，根據(jù)提出的分組優(yōu)化算法進行分組后，采用文獻［8］中的資源分配算法，分別和文獻［8］的分組方法（SDP Clustering）及未分組時在相同的資源分配方法下做對比。這里我們采用平均功率，干擾門限=10-11，可以很明顯地看到在使用相同的資源分配算法下，當(dāng)毫微微基站數(shù)在10個以下時，提出的分組優(yōu)化算法和文獻［8］的分組方法相比，平均用戶速率是一樣的，但當(dāng)毫微微基站數(shù)繼續(xù)增加，提出的分組優(yōu)化算法逐漸優(yōu)于文獻［8］的分組算法。這是因為隨著基站數(shù)目的增加文獻［8］的分組算法找不到最優(yōu)解了。未分組的情況下，平均用戶速率最低。另外，平均用戶速率是隨著毫微微基站數(shù)目的增多而降低的。

圖2　毫微微基站數(shù)目與用戶平均速率對比Fig.2 Average data rate vs.the number of FAPs

從圖3中我們可以看到∶在采用文獻［8］中的信道分配算法情況下，使用提出的分組優(yōu)化算法和文獻［8］中的分組算法（SDP Clustering）相比，用戶的平均干擾更低；在采用提出的分組優(yōu)化算法情況下，提出的子信道分配算法和文獻［8］中的信道分配算法（HAS）相比，用戶的平均干擾仍然更低；在同時使用提出的分組優(yōu)化算法和子信道分配算法的情況下，與文獻［8］的分組和信道分配方法相比，用戶的平均干擾是極低的。另從圖3中還可以看到，提高干擾門限的時候，用戶間平均干擾值的趨勢是遞增的，但當(dāng)干擾門限提高到閥值時（本文為Rf）就不再變化。這是因為干擾門限越大，可分的有效信道數(shù)越多，這樣平均干擾就越大，但當(dāng)干擾門限增加到閥值的時候，毫微微用戶之間的干擾均在干擾門限以下，也就不需考慮干擾。因此，在干擾門限繼續(xù)提高的時候，信道分配情況不再變化。

圖3　用戶平均干擾對比圖Fig.3 Average interference at an FUE vs.interference threshold

圖4中，在使用文獻［8］中的信道分配方法下，提出的分組優(yōu)化算法和文獻［8］的分組方法相比，隨著干擾門限的減小，用戶速率公平性逐漸高于使用文獻［8］的分組方法。其次，在使用提出的分組優(yōu)化算法的情況下，提出的子信道分配算法與文獻［8］的信道分配算法相比，用戶的速率公平性更高。

圖4　干擾門限和數(shù)據(jù)速率公平性對比Fig.4 Data rate faireness vs.interference threshold

另外，從圖4中可看出，在同時使用提出的分組優(yōu)化算法和子信道分配算法的情況下，與文獻［8］中的分組和信道分配方法相比，仍然有優(yōu)越的速率公平性。隨著干擾門限的減小，速率公平的曲線趨勢是降低的，這是因為干擾門限減少，用戶間的干擾數(shù)增多，可分有效信道數(shù)減小。

6　結(jié)束語

本文針對密集分布的毫微微基站，分別討論了femtocell網(wǎng)絡(luò)的分組問題和子信道分配問題。分別采用了不同的分組管理思想和子信道分配策略進行對比，其中基于CVX平臺的隨機舍入算法，隨著毫微微基站的增加，算法的效率降低。同樣地，啟發(fā)式的子信道分配算法并不能有效解決用戶間干擾和用戶間速率公平問題。本文提出了一種新的分組管理思想和子信道分配算法，和其他算法相比，取得了很好的效果。仿真結(jié)果表明本文所提算法不僅使用戶的平均干擾更低，而且在具有更高數(shù)據(jù)速率的同時又提高了用戶間速率公平。然而，本文研究的是單用戶下femtocell同頻干擾和子信道分配的問題，多用戶情況下的干擾問題還需進一步討論。

［1］ MA W M，ZHENG W，ZHANG H J，et al.Utility-based fairness power control scheme in OFDMA femtocell networks［J］.Journal of Electronics&Information Technology，2012，34（10）∶2287-2292.

［2］ LI J，MENG Y，LI H，et al.Graph-based fair resource allocation scheme combining interference alignment in fem-tocell networks［J］.IET Communications，2015，9（2）∶211-218.

［3］ YUN S，YI Y，CHO D，et al.Open or close∶on the sharing of femtocells［C］//Proceedings of 2011 IEEE International Conference on Computer Communications.Shanghai∶IEEE，2011∶116-120.

［4］ ATTAR A，KRISHNAMURTHY V.Collaborative subchannel allocation in cognitive LTE femtocells∶a cooperative game-theoretic approach［J］.IEEE Transactions on Communications，2013，61（1）∶325-334.

［5］ HATOUM A，LANGAR R，AITSAADI N，et al.Clusterbased resource management in OFDMA femtocell networks with QoS guarantees［J］.IEEE Transactions on Vehicular Technology，2014，63（5）∶2378-2391.

［6］ WEI L，WEI Z，XIANGMING W，et al.Dynamic clustering based sub-band allocation in dense femtocell environments［C］//Proceedings of 2012 75th IEEE Vehicular Technology Conference.Yokohama∶IEEE，2012∶1-5.

［7］ PRAMUDITO W，ALSUSA E.A hybrid resource management technique for energy and QOS optimization in fractional frequency reuse based cellular networks［J］.IEEE Transactions on Communications，2013，61（12）∶4948-4960.

［8］ ABDELNASSER A，HOSSAIN E，IN KIM D.Clustering and resource allocation for dense femtocells in a two-tier cellular OFDMA network［J］.IEEE Transactions on Wireless Communications，2014，13（3）∶1628-1641.

［9］ 鄭義建.線性規(guī)劃問題最優(yōu)解集的結(jié)構(gòu)與僅有唯一基最優(yōu)解的充分條件［J］.應(yīng)用數(shù)學(xué)與計算數(shù)學(xué)學(xué)報，1992，6（1）∶86-91.

ZHENG Yijian.Optimal solution set structure and sufficient condition of only having unique basic optimal solution for a linear programming problem［J］.Communication Applied Mathematics and Computation，1992，6（1）∶86-91.（in Chinese）

［10］ 管谷梅，鄭漢鼎.線性規(guī)化［M］.濟南∶山東科學(xué)技術(shù)出版社，1983.

GUAN Gumei，ZHENG Handing.Linear programming［M］.Jinan∶Shandong Science and Technology Press，1983.（in Chinese）

［11］ 洪文，吳本忠.LINGO 4.0 for Windows最優(yōu)化軟件及其應(yīng)用［M］.北京∶北京大學(xué)出版社，2001.

HONG Wen，WU Benzhong.LINGO 4.0 for Windows optimal software and application［M］.Beijing∶Peking U-niversity Press，2001.（in Chinese）

張海波（1979—），男，重慶人，2013年于北京郵電大學(xué)獲博士學(xué)位，現(xiàn)為副教授，主要研究方向為無線資源管理；

ZHANG Haibo was born in Chongqing，in 1979.He received the Ph.D.degree from Beijing University of Posts and Telecommunications in 2013.He is now an associate professor.His research concerns wireless resource management.

彭焦陽（1992—），男，安徽人，碩士研究生，主要研究方向為無線資源管理；

PENG Jiaoyang was born in Anhui Province，in 1992.He is now a graduate student.His research concerns wireless resource management.

Email∶503853288@qq.com

陳善學(xué)（1966—），男，重慶人，2009年于電子科技大學(xué)獲博士學(xué)位，現(xiàn)為教授、中國電子協(xié)會會員、IEICE會員，主要研究方向為矢量量化、小波分析和數(shù)字圖像處理和檢索等。

CHEN Shanxue was born in Chongqing，in 1966.He received the Ph.D.degree from University of Electronic Science and Technology of China in 2009.He is now a professor and also a member of China Electronic Association and IEICE.His research concerns vector quantization，wavelet analysis，digital image compression and retrieval，etc.

A Clustering-based Resource Allocation Approach for Femotcell

ZHANG Haibo，PENG Jiaoyang，CHEN Shanxue
（Chongqing Key Laboratory of Mobile Communications Technology，Chongqing University of Posts and Telecommunications，Chongqing 400065，China）

∶In order to solve interference between femtocells efficiently，a distributed scheme is proposed to manage resources among femtocells.Firstly，femto access points（FAPs）are grouped.In order to solve the clustering optimization problem，an algorithm is presented based on mathematical modeling idea in Lingo. The algorithm cuts off the branches which deviate from the direction of the optimal solution by establishing the simplex tableau when the Branch-and-Bound algorithm is used to find the optimal solution.Secondly，a FAP is selected as a cluster head that is responsible for resource allocation among the femtocells in current cluster.A novel algorithm which modifies sub-channel allocation by the interference instruction matrix is proposed to allocate sub-channels.The simulation results show that the proposed algorithm for clustering optimization can not only obtain the optimal solution of the clustering optimization problem compared with other algorithms，but also improve the efficiency of searching for the optimal solution.Compared with other related schemes，the proposed resource allocation algorithm can reduce the inter-user interference and achieve the higher data rate fairness.

∶femtocells；resource allocation；clustering optimization；inter-user interference；data rate fairness

The National Natural Science Foundation of China（U1035002/L05）；The National Science and Technology Major Project（2014ZX03003001-002）

TN929.5

A

1001-893X（2016）05-0525-06

10.3969/j.issn.1001-893x.2016.05.009

張海波，彭焦陽，陳善學(xué).毫微微小區(qū)中一種基于分組的資源分配方法［J］.電訊技術(shù)，2016，56（5）∶525-530.［ZHANG Haibo，PENG Jiaoyang，CHEN Shanxue.A clustering-based resource allocation approach for femotcell［J］.Telecommunication Engineering，2016，56（5）∶525-530.］

2015-09-15；

2016-01-19Received date：2015-09-15；Revised date：2016-01-19

國家自然科學(xué)基金資助項目（U1035002/L05）；國家科技重大專項（2014ZX03003001-002）

**通信作者：503853288@qq.comCorresponding author：503853288@qq.com