毫微微小区中一种基于分组的资源分配方法*

张海波，彭焦阳，陈善学

（重庆邮电大学移动通信技术重庆市重点实验室，重庆　400065）

毫微微小区中一种基于分组的资源分配方法*

张海波，彭焦阳**，陈善学

（重庆邮电大学移动通信技术重庆市重点实验室，重庆400065）

为有效解决毫微微小区间（Femtocell）干扰，采用分布式方式对毫微微小区进行资源管理。首先，对毫微微接入点（FAPs）进行分组。基于Lingo数学建模的思想，提出了一种解决分组优化问题的算法。该算法在使用分支定界算法寻找最优解的同时，通过建立单纯形表剪去偏离最优解方向的分支；其次，每组选择一个簇头为本组内FAPs分配资源，为此，提出了新的子信道分配方法，该方法根据干扰指示矩阵修正子信道分配的情况。仿真结果表明：和其他算法相比，提出的算法不仅能找到分组优化问题的最优解，并且效率更高；另外，提出的资源分配算法不仅减小了用户间干扰，而且提高了户间速率公平。

毫微微小区；资源分配；分组优化；用户间干扰；速率公平

1　引　言

研究表明，近90%的数据业务和60%的语音业务是在室内发生的，因此，需要及时解决室内信号覆盖的问题［1］。毫微微小区技术作为室内无线通信最有前景的技术之一，近年来得到了广泛的研究。与传统的宏蜂窝网络架构相比，嵌入毫微微基站的网络架构可以提高系统性能。

文献［2］采用分割频谱的方式有效地解决了双层网络间的干扰问题，但是频谱利用率太低，在LTE系统频谱资源匮乏情况下，这种算法并不可行。文献［3］中毫微微基站采用开放式模式，虽然提高了系统部分性能，但是干扰协调的方式过于复杂。文献［4］提出了一种基于认知无线电的分布式博弈资源分配算法，虽然在提高毫微微用户吞吐量的同时降低了干扰，但是并未针对毫微微小区间干扰进行分组优化。文献［5-7］提出了一种分组优化和联合资源分配的方法，虽然减小了同层间的干扰，提高了系统性能，但是并没有考虑最优组尺寸问题。文献［8］提出了一种基于CVX平台的Semidefinite Programming（SDP）和随机舍入算法，虽然考虑了组尺寸的问题，但是所提算法效率并不高，随着毫微微基站数目增加，并不一定能找到最优解。另外，其资源分配方法不但没有有效地解决用户间平均干扰问题，而且也没有考虑用户间速率公平问题。

针对上述问题，本文提出了联合分组的资源分配算法。首先，构造分组优化和资源分配问题，由于该问题是NP-hard问题，所以并不能通过毫微微网关（Femto Gateway，FGW）解决该类问题。因此，将NP-hard问题划分为两个子问题，即分组优化问题和资源分配问题。其次，毫微微网关检测毫微微小区的信息，根据分组算法将毫微微基站分配到不同的组。然后，每组选择一个毫微微基站作为簇头，负责本组的资源分配。本文分别提出了一种Lingo数学建模的思想和新的资源分配方法。仿真结果表明，和其他算法相比，提出的算法不仅找到分组优化问题的最优解，而且算法求解的效率更高。另外，提出的资源分配算法不仅降低了用户间的干扰，而且提高了用户间的速率公平。

2　系统模型

图1是系统模型图。在本模型中，毫微微基站被均匀分布在40 m×40 m的范围里，并且采用闭合模式。假设毫微微用户和宏用户都在室内，并且毫微微基站及其所属用户之间信道的传播条件都很好，毫微微基站以平均功率发送信号，毫微微基站和用户之间的总路损L1=15.3+37.6lgR+L+Ls-La。其中参数见表1。

图1　系统模型图Fig.1 The model of the femto-macro system

表1　系统参数Tab.1 System parameters

由于毫微微基站f和它服务的用户kf之间距离很短，毫微微基站j和用户kf之间的信道增益近似等于毫微微基站f和j之间的信道增益，即≈，很显然毫微微基站间建立的信道增益矩阵是对称的，即=［8］。

3　构造分组优化问题

首先建立一个无向图G1=（V1，E1），V1为顶点，代表毫微微基站，E1为链接各顶点的边，ω和ω是非负的链接权值［8］。分组优化的目标是根据ω的值将彼此间存在严重干扰的毫微微基站分成一组，如果两个毫微微基站之间存在严重的干扰，那么它们之间的链接权值ω是很大的。同样地，将ω作为两个毫微微基站不在同一组的惩罚因子。另外，如果两个毫微微基站i、j之间有高的信道增益g，那么它们之间也存在很大的干扰。由于信道增益和路损成反比，因此本文可以设ω=1/L1。

综上，本文的目的是寻找一种分组方法，使毫微微基站间链接权值和惩罚因子之和最大。令ω的值相同，即ω=ω，ω的取值范围为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表示每组毫微微基站数不超过可用信道数；C5表示xi，j为二进制数。

下面给出本文提出的分组优化算法（以下称算法1）的步骤。

Step 1 将上述优化问题转化为Lingo模型［9-11］。

Step 2 运用直接求解程序对模型的等式约束项进行处理。约束C1中变量的值为固定值，将这些变量处理成常量，并从约束中划除。

Step 3 运用Lingo识别模型种类，本文为整数线性规划。

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

令c*为当前最大目标函数值，p为分支层，p*为相对c*工件的顺序，p1为当前节点，即目前需要分支的节点。

（1）首先初始化，令p=0，p1=A（空集），c*=∞，此时，当前节点为p1（即根节点）；

（2）从当前节点开始分支得到各个子节点，计算各子节点的下界值，按对应的各子节点下界值从小到大排序。更新p，令p=p+1；

（3）以各分支节点为初始值，建立单纯形表。由于最优解在边界取得，且非基变量对应的检验数非正［9-10］，对不满足此条件的分支或偏离边界方向的分支进行剪支，更新p；

（4）如探测完所有的当前节点，更新p，令p=p-1，转入第7步；否则，将当前层（第p层）各子节点中具有最大下界值的节点标记为Q，并在节点p1的末尾加入Q所对应第p位置上的工件，此时令当前节点为Q转到第5步；

（5）当前节点是同层同父节点中具有最大下界值的节点，如果当前节点的下界值不小于C*，则不需要再搜索当前节点和同层同父的节点。因此，当前节点的父节点被探测完毕，更新p，令p=p-1。然后去掉p1中最后一个工件，再转第7步；否则，转入第6步；

（6）假设这时p=n，此时得到一个较优顺序。令P*=p1，其中c*是当前节点的下界值，更新p，令p=p-1，然后去掉p1中最后一个工件，转入第7步；否则，跳转第2步；

（7）此时如果p≠0，则去掉p1最后一个工件后，再跳转第4步；否则，算法终止。C*就是最优的目标函数值，P*即为最优解。

4　构造资源分配问题

构造如下信道分配问题∶

由于文献［8］中的资源分配方法并未有效地解决用户间干扰和用户速率公平问题，因此，在保证用户数据速率的情况下，针对上述问题提出以下方法，即子信道分配算法（以下称算法2）。

算法2步骤如下∶

（1）将毫微微基站编号，利用算法1将毫微微基站分组；

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

（6）从本组的第一个用户开始，检测前几组与该用户在同一子信道的用户k1，检测本组用户与k1的干扰是否在干扰门限内，如超出门限，根据T判断k1的子信道数如大于一，则从k1中剔除干扰的信道；重复步骤6直至本组用户检测完毕。

5　仿真结果与分析

根据3GPP标准，仿真系统参数如表2所示。本文实验环境∶软件为MATLAB R2013a，操作系统为Windows XP，处理器为Intel Pentium Dual CPT T3200 2.00 GHz。

平均速率、平均干扰和速率公平分别为

本次仿真采用平均功率Pfmax/N，其中，K为总的用户数。

表2　仿真参数Tab.2 The simulation parameters

图2中，根据提出的分组优化算法进行分组后，采用文献［8］中的资源分配算法，分别和文献［8］的分组方法（SDP Clustering）及未分组时在相同的资源分配方法下做对比。这里我们采用平均功率，干扰门限=10-11，可以很明显地看到在使用相同的资源分配算法下，当毫微微基站数在10个以下时，提出的分组优化算法和文献［8］的分组方法相比，平均用户速率是一样的，但当毫微微基站数继续增加，提出的分组优化算法逐渐优于文献［8］的分组算法。这是因为随着基站数目的增加文献［8］的分组算法找不到最优解了。未分组的情况下，平均用户速率最低。另外，平均用户速率是随着毫微微基站数目的增多而降低的。

图2　毫微微基站数目与用户平均速率对比Fig.2 Average data rate vs.the number of FAPs

从图3中我们可以看到∶在采用文献［8］中的信道分配算法情况下，使用提出的分组优化算法和文献［8］中的分组算法（SDP Clustering）相比，用户的平均干扰更低；在采用提出的分组优化算法情况下，提出的子信道分配算法和文献［8］中的信道分配算法（HAS）相比，用户的平均干扰仍然更低；在同时使用提出的分组优化算法和子信道分配算法的情况下，与文献［8］的分组和信道分配方法相比，用户的平均干扰是极低的。另从图3中还可以看到，提高干扰门限的时候，用户间平均干扰值的趋势是递增的，但当干扰门限提高到阀值时（本文为Rf）就不再变化。这是因为干扰门限越大，可分的有效信道数越多，这样平均干扰就越大，但当干扰门限增加到阀值的时候，毫微微用户之间的干扰均在干扰门限以下，也就不需考虑干扰。因此，在干扰门限继续提高的时候，信道分配情况不再变化。

图3　用户平均干扰对比图Fig.3 Average interference at an FUE vs.interference threshold

图4中，在使用文献［8］中的信道分配方法下，提出的分组优化算法和文献［8］的分组方法相比，随着干扰门限的减小，用户速率公平性逐渐高于使用文献［8］的分组方法。其次，在使用提出的分组优化算法的情况下，提出的子信道分配算法与文献［8］的信道分配算法相比，用户的速率公平性更高。

图4　干扰门限和数据速率公平性对比Fig.4 Data rate faireness vs.interference threshold

另外，从图4中可看出，在同时使用提出的分组优化算法和子信道分配算法的情况下，与文献［8］中的分组和信道分配方法相比，仍然有优越的速率公平性。随着干扰门限的减小，速率公平的曲线趋势是降低的，这是因为干扰门限减少，用户间的干扰数增多，可分有效信道数减小。

6　结束语

本文针对密集分布的毫微微基站，分别讨论了femtocell网络的分组问题和子信道分配问题。分别采用了不同的分组管理思想和子信道分配策略进行对比，其中基于CVX平台的随机舍入算法，随着毫微微基站的增加，算法的效率降低。同样地，启发式的子信道分配算法并不能有效解决用户间干扰和用户间速率公平问题。本文提出了一种新的分组管理思想和子信道分配算法，和其他算法相比，取得了很好的效果。仿真结果表明本文所提算法不仅使用户的平均干扰更低，而且在具有更高数据速率的同时又提高了用户间速率公平。然而，本文研究的是单用户下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］ 郑义建.线性规划问题最优解集的结构与仅有唯一基最优解的充分条件［J］.应用数学与计算数学学报，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］ 管谷梅，郑汉鼎.线性规化［M］.济南∶山东科学技术出版社，1983.

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

［11］ 洪文，吴本忠.LINGO 4.0 for Windows最优化软件及其应用［M］.北京∶北京大学出版社，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年于北京邮电大学获博士学位，现为副教授，主要研究方向为无线资源管理；

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

陈善学（1966—），男，重庆人，2009年于电子科技大学获博士学位，现为教授、中国电子协会会员、IEICE会员，主要研究方向为矢量量化、小波分析和数字图像处理和检索等。

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

张海波，彭焦阳，陈善学.毫微微小区中一种基于分组的资源分配方法［J］.电讯技术，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

国家自然科学基金资助项目（U1035002/L05）；国家科技重大专项（2014ZX03003001-002）

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