朱翠涛，孟 帆

(中南民族大学 电子信息工程学院,武汉 430074)

多层异构蜂窝网络中一种快速最优资源分配算法

朱翠涛，孟 帆

(中南民族大学 电子信息工程学院,武汉 430074)

利用最大化系统下行链路总容量问题模型中隐含的单调结构，将由于干扰存在使得构建的最优资源分配为非线性非凸的问题转换为单调优化问题，提出了一种改进的Polyblock外逼近法对其进行求解.该算法针对Polyblock外逼近法在求解过程中顶点值的个数呈指数倍增长，导致计算量较大、收敛速度较慢等缺陷，改用分枝定界法划分可行域区域，并以最大利益优先的方式进行节点扩展和搜索，边分枝边剪除不符合条件的枝，使可行域范围越来越小，最终逼近最优解.实验结果表明：改进算法提高了收敛速度和逼近最优解的效果.

资源分配；单调优化；Polyblock外逼近法；分枝定界法

探索高效的无线资源分配方法对于提高异构蜂窝网络性能具有十分重要意义.由于随机、异构、超密集、多天线、规模日益扩大、干扰等因素，使得构建的最优资源分配问题常常是非线性非凸的，难以求解.对此，人们已做了大量研究工作，文献[1]通过将多个相邻子载波分组到块中，可以在OFDMA系统中通过组块来执行资源分配.在文献[2]中，为了更好地利用频谱资源，结合认知无线电和OFDMA相关技术来研究蜂窝系统中感测和接收.文献[3]提出了一种基于OFDMA的认知无线电系统中的副载波和功率分配的最佳方案，但其将以一定量的传输速率为代价来保证被感知用户之间的一定公平性，因此该方案中传输速率不是最优解，而且没有考虑任何通道感测错误.文献[4]提出了基于图论的启发式算法，但该算法的复杂度较高且所求的结果不一定为最优解；在文献[5]中，为了降低基于图论的启发式算法较高的复杂度，提出了一个含有多项式时间的启发式子信道分配算法，运用该算法复杂度有所降低，然而通过该算法求解得到的最大值的精度不高；在文献[6]中，由于多用户OFDMA系统的子信道分配和传输功率控制问题是一个耦合混合整数非凸问题，采用Polyblock外逼近法求解最大信道容量的上下界，但是算法实用行不强；在文献[7]中，通过用户关联策略和基站功率控制的协同优化来最大化系统容量， 但这些基站功率控制上的研究工作并没有考虑基站之间的负载均衡.文献[8]描述了针对由多小区干扰削弱的下行链路扇区化OFDMA系统的在功率控制和子载波分配方面的最优资源分配，并提出了一种低复杂度的分布式实用资源分配算法，但该算法实用性不强.

本文针对多层异构多用户OFDMA系统中子信道分配和功率控制建立了资源分配模型，利用最大化系统下行链路总容量问题模型中隐含的单调结构，将原问题转换为单调优化问题，并提出了一种改进的Polyblock外逼近法对其进行求解.该算法针对Polyblock外逼近法在求解过程中顶点值的个数呈指数倍增长，导致计算量较大、收敛速度较慢等缺陷，改用分枝定界法划分可行域区域，并以最大利益优先的方式进行节点扩展和搜索，边分枝边剪除不符合条件的枝，使可行域范围越来越小，最终逼近最优解.

1 问题描述

设在多层异构蜂窝网络中，包含一个宏蜂窝，即主基站(PB)，K个二级蜂窝，即认知基站(SB)，认知基站SBk服务的移动终端数为Mk，mk表示认知基站SBk服务的第k个移动终端.根据小区的业务需求提供所需的信道资源，设定主基站提供信道数集合为D1，di表示第i个子信道；每个认知基站提供子信道数集合为D2，dj表示其中第j个子信道.建立同一服务需求条件下的多小区OFDMA系统中下行链路资源分配模型.

PB子信道di分配指示变量：

(1)

SB子信道dj分配指示变量：

(2)

假定每个移动终端只能划分一条子信道，用不等式表示为：

(3)

(4)

其中pmax是SBk最大的发射总功率，则每条子信道必须满足：

(5)

与SBk对应的mk在子信道dj上的信干噪比(SINR)表示成：

(6)

建立SBk和与之对应的mk之间的子信道dj的链路容量，由香农容量定律表示为：

(7)

则mk与SBk之间总的链路容量为：

(8)

于是，得到该系统中下行链路的总容量：

(9)

为了得到最优化系统容量的总和，需要考虑到PB和SB分配信道的约束和SB对各个子信道传输功率的控制.问题模型描述为：

2 单调优化方法及算法的描述

由于问题(P1)为混合整数非线性非凸问题，一般难以求解，本文利用问题(P1)中隐含的单调性将其转换为个单调优化问题，然后通过所提出的改进算法进行求解.

2.1 目标函数单调化

于是链路容量(7)式可以表示成为：

subject toz∈Z

其中,

Z=

由于函数F(x)=log2(x)是单调函数，则问题(P2)被转化为一个单调优化问题.

定义 (箱子[9])对于给定的x1,x2∈Rn且x1

根据箱子的定义，问题(P2)中可行域Z可以表示成无限多个箱子单元.简化后表示为：

Z=z{1≤z≤1+ρ·a·γ(p)},

2.2 算法描述

由于问题(P2)具有单调性，其最优解在可行域边界上取得，本文针对Polyblock外逼近法在求解过程中顶点值的个数呈指数倍增长，导致运算量较大，收敛速度较慢等缺陷，提出了一种改进的Polyblock外逼近法.此算法借鉴了分枝定界法[10]的思想，该算法并不盲目的扩展节点，而是以最大利益优先的方式进行节点扩展和搜索，边分枝边剪除不符合条件的枝，使其计算效率高，收敛速度快.该改进算法的主要过程为：原始区间为初始化的箱子，取得在该箱子上对应的目标函数上界，连接箱子的对角线，该直线段会与可行域外边界相交于一点，利用二分法搜索该点，会得到可行域边界上一点x1，如图3所示，由点x1将原始的箱子划分成4个箱子.不包含可行域边界的箱子可以舍去，这样就可以得到2个包含可行域边界的箱子，将新得到的箱子上界对应目标函数值进行比较.目标函数值较大，则与之对应的箱子则保留，目标函数值较小，则与之对应的箱子舍去.假定以w1为顶点的箱子对应的目标值大一些，则舍去以w2为顶点的箱子，并连接保留箱子的对角线与可行域相交于x2.依此类推，箱子越来越小，最终逼近最优解.

本文先介绍运用二分法求解两个单个变量的单调函数的交点，然后在此基础上将二分法演变，使其变为能求解多个变量的单调函数的最优解.

图1 一维情况下的二分法Fig.1 Dichotomy in one-dimensional case

图1为运用二分法求两单调函数的交点.设H(x)=f(x)-g(x),x∈[x1,x2].由H(x1)=f(x1)-g(x1)>0，H(x2)=f(x2)-g(x2)<0，即H(x1)H(x2)<0，则f(x)与g(x)在[x1,x2]之间有交点.点x3为x1，x2的中点，求得H(x3).若H(x3)H(x2)<0，则求解区间可以缩小到[x3,x2]之间；若H(x2)H(x1)<0，则求解区间可以缩小到[x1,x3]之间.

图2 多维情况下的二分法Fig.2 Dichotomy in multi-dimensional case

当二分法发展到多维情况时，如图2所示.图2中i,j分别表示坐标轴的横轴和纵轴，其中箱子为[l1,w].假定目标函数f(x)为单调增函数，连接l，w两点，通过这两点的直线为l.点l1在i轴上投影的点i(1)；点g3在i轴上投影的点为i(3).由f(g1)-f(l1)>0,f(w)-f(g3)<0可知直线l可行域边界交点在箱子[g1,g3]所包含的弧线段之间.令i(2)为i(1)和i(3)之间的中点，i(2)为可行域边界和直线l对应的交点分别为g2，l2，若f(g2)-f(l2)<0则直线l与可行域边界的交点在小箱子[g2,g3]所包含的弧线段上；若f(g2)-f(l2)<0,则直线l与可行域边界的交点在小箱子[g1,g2]所包含的弧线段上.

图3 求解顶点值Fig.3 Solving the vertex values

由于问题P(2)为单调函数，可行域Z为：

Z={z|I≤z≤1+p·a·γ(p)}.

令向量a=1,β=1+p·a·γ(p)，则可行域Z表示成Z=[α,β]，即初始化的箱子为[α,β]，所对应目标函数的上界为f(β).

设得到新箱子为[αi,βi]，β1∈[αi,βi]，且在可行域内最大值fmax=f(β1).连接αi,βi两点，得到直线l，下界最小值用fmax表示.x为直线l上的一点，点x的集合设为r，表示为：

(10)

如果点x在可行域边界上，设定线性搜索的精度为δ，通过二分法搜索该点，设该点所对应箱子的下界r.由于目标函数已经具有单调性，在[αi,x]区域的边界上得到r，则箱子下界对应的目标函数值为f(r).按照此方法可以得到多个下界，设箱子下界fmin=f(rmin).上界表示成{β(1),…,β(K)}，每一个上界β(i)为向量β-(βi-ri)ei中的第i个元素，其中ei表示第i个元素为1，其他均为0的向量.

下界表示为{α(i1),…,α(ik)}，具体表示为：

(11)

由每个上界和该上界对应的下界组成一个小箱子，该箱子表示为[α(is),β(is)].总的[α(is),β(is)]表示为：

(12)

(13)

设定算法精度η，当fmax-fmin≤η时，迭代停止，算法运行结束.

算法为：

1) 初始化fmin=max(α·β0)，fmax=f(β0)设置收敛条件的精度η，二分法算法精度δ;

2) 当fmax-fmin>η时，[α,β]根据fmax=max[α,β]∈Zf(β)和向量a的可行域对进行重新划分;

3) 判断所得下界是否可行，然后由式(11)将[α,β]划分为K个新的箱子;

4) 用式(12)进行更新箱子，并用式(13)进一步对下界进行修正;

5) 直到fmax-fmin≤η，结束循环;

6) 获得fmin,fmax.

最终得到以fmin,fmax为最优解的上下界，定义归一化差值为ω，表示为：

3 算法性能的分析

通过上一节中的归一化差值ω可以用来分析Polyblock外逼近和改进算法的性能.此外，还可以通过算法的内在因素来分析.原Polyblock外逼近法逼近最优解的程度除了与算法精度值以外，还与其初始可行域下界有关，但其可行域下界在逼近过程中是不变的.改进算法针对原Polyblock外逼近法的缺陷，用分枝定界法有选择地划分可行域区域，最大利益优先的方式进行节点扩展和搜索，边分枝边剪除不符合条件的枝，其箱子的下界是可变的.在逼近最优解的过程中用二分法进行搜索最优解的点，由此得到的箱子更小一些，更逼近最优解.

从算法的复杂度这个角度也可以分析两个算法的性能.由上面分析可知两算法的初始向量集相同，因此主要比较算法迭代过程中的计算量.设问题规模为N，由于Polyblock外逼近法的顶点是呈级数增长的，其计算量为O(log2N)，之后还需要将得到的顶点进行比较，计算量为O(N)；改进算法中采用的分枝定界法来处理顶点值，采取边分枝边剪除不符合条件的枝，其计算量O(log2N).由于O(log2N)

4 仿真结果与分析

在本模型中，有一个主基站和7个认知基站，每个认知基站服务4个移动终端.相邻基站之间的距离为1.0km，噪声系数为10dB.路径损耗模型为128+37.6lg(d)，其中d为认知基站与移动终端之间的距离，单位：km.认知基站与移动终端之间的信道服从瑞利信道衰落，噪声功率谱密度为-174dBm/Hz.

在总的最大功率相等的情况下，为了比较Polyblock外逼近法与改进算法的逼近效果，通过仿真得到图4.由该图可以得出，随着基站的最大总发射功率的增大，改进算法和Polyblock外逼近法的归一化差值均是逐渐下降.这也表明了在Polyblock外逼近算法和改进算法下所得到的最大信道容量和的上限和下限逐渐逼近，并且总的发射功率越大逼近效果越好.改进算法的曲线一直都在Polyblock外逼近法的下面，这说明了当总的最大发射功率相等时，改进算法的逼近效果比Polyblock外逼近法好.

图4 归一化差值与最大总发射功率的曲线图Fig.4 The normalized difference vs. the maximum total transmit power

为了比较Polyblock算法和改进后算法之间的性能，通过图5可以得出当总的发射功率为某一定值时，改进算法上下界之差与Polyblock外逼近法的上下界之差相比明显小一些.同时也可以看出了改进算法的归一化差值比Polyblock外逼近法的归一化差值小，这也间接的说明了图4的正确性.此外，随着总的最大的发射功率增大时，Polyblock外逼近法和改进算法的上下界均随着增大.改进算法的上下界在Polyblock外逼近法之间，说明它们均逼近最优解，改进算法逼近的上下界更加紧凑一些，这说明改进算法逼近效果更好一些.

图5 总的最大发射功率与总的最大信道容量的上下界之间的曲线图Fig.5 The total maximum transmit power and the upper vs. lower bounds of the total maximum channel capacity

为了研究认知基站与移动终端之间的距离对系统中下行链路总的最大信道容量的影响，设定每个认知基站周围有4个等距离的移动终端，如图6所示.

图6 相邻认知基站与其周围的移动终端Fig.6 Neighbor cognitive base station and the surrounding mobile terminals

通过改变移动终端与认知基站之间的距离，可以得到该距离与总的最大信道容量上下界之间的曲线图如图7.由该图可以得出，当移动终端与基站之间的距离增大时，总的最大信道容量逐渐减小.用改进算法求得的总的最大信道容量上下界曲线位于Polyblock外逼近法求得的总的最大信道容量的上下界曲线之间，并且改进算法求得的总的最大信道容量的上下界之间的距离明显比用Polyblock外逼近法求得的小，这也说明了改进算法的逼近效果比Polyblock外逼近法的逼近效果好.

图7 距离与总的最大信道容量的上下界之间的曲线图Fig.7 Distance vs. the upper and lower bounds of the total maximum channel capacity

5 结语

为了解决异构蜂窝网络中多小区OFDMA系统中下行链路资源分配问题，建立了一个多层异构蜂窝网络结构，得到一个混合整数非线性非凸问题.该问题隐含有单调性，可以将其转化问单调优化问题.利用提出改进算法对隐含单调性的函数求取最优解，该算法为改进的Polyblock外逼近法，将最终得到的最优解与用Polyblock外逼近法求解的结果进行比较.由仿真结果可以看出，改进算法相比Polyblock外逼近法收敛速度更快，逼近最优解的效果更好.

[1] Zhu H, Wang J. Chunk-based resource allocation in OFDMA systems - Part II : Joint chunk, power and bit allocation[J]. IEEE Transactions on Communication, 2012, 60(2):499-509.

[2] Karunakaran P, Gerstacker W. A reference signal based GLRT for simultaneous sensing and reception in cognitive LTE-A systems[C]//Gerstacker Wolfgang H.Computer Science Bibliography:2016 IEEE Wireless Communications and Networking Conference.Piscataway:IEEE,2016:1-6.

[3] Shanthy K R,Suganthi M,Kumaran S. Resource allocation for OFDMA based cognitive radio system using joint overlay and underlay spectrum access mechanism[J]. ARPN Journal of Engineering and Applied Sciences,2015,10(8):3694-3701.

[4] Chang R, Tao Z, Zhang J, et al. Multicell OFDMA downlink resource allocation using a graphic framework[J]. IEEE Transactions on Vehicular Technology,2009,58(7):3494-3507.

[5] Pischella M,Belfiore J. Weighted sum throughput maximization in multicell OFDMA Networks[J]. IEEE Transactions on Vehicular Technology, 2010,59(2):896-905.

[6] Kim S Y,Kwon J A, Lee J W. Resource allocation for the multi-cell OFDMA system and its capacity bounds[C]//Zheng Xiaokun.Interference Management Research in DCF Infrastructure Networks Based on Boolean Model:2013 11th International Symposium and Workshops on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt).Switzerland:Springer,2013:326-336.

[7] Liang Z Y, Chew Y, Ko C.On the modeling of a non-cooperative multicell OFDMA resource allocation game with integer bit-loading[C]//Ko Chi Chung.Computer Science Bibliography:2009 Global Telecommunications Conference(GLOBECOM).Piscataway:IEEE,2009:1-6.

[8] Ksairi N, Bianchi P, Ciblat P, et al.Resource allocation for downlink cellular OFDMA systems-Part II : Practical algorithms and optimal reuse factor[J]. IEEE Transactions on Signal Processing, 2010,58(2):735-749.

[9] 黎健玲，孙小玲.连续与离散单调优化和不定二次规划算法研究[D].上海:上海大学，2006.

[10] 高岳林，徐成贤.边界约束非凸二次规划问题的分枝定界方法[J].运筹学学报，2001,5(4):81-89.

A Fast Optimal Resource Allocation Algorithm for Multi- Layer Heterogeneous Cellular Networks

ZhuCuitao,MengFan

( College of Electronic and Information Engineering,South-Central University for Nationalities,Wuhan， 430074,China)

By utilizing monotonic structure in the model of total capacity of downlink in maximum system,the optimal resource allocation problem is transformed into a nonlinear nonconvex problem due to the existence of the interference, and this paper puts forward an improved Polyblock outer approximation method to solve it.The outer approximation algorithm for Polyblock in the process of solving the number of vertices value exponentially increased, resulting in a large amount of computation, slowing down convergence and other defects.The improved algorithm uses the branch and bound method to divide the feasible region and in the best interests of the priority ways to expand and search nodes.By removing unnecessary branches that do not contain the optimal solution, the feasible region is getting smaller and smaller, and finally it is close to the optimal solution.The experimental results show that the improved algorithm can improve the convergence speed and the effect of approximating the optimal solution.

resource allocation;monotonic optimization; Polyblock; branch and bound algorithm

2017-01-04

朱翠涛(1967-)，男，教授，博士，研究方向：认知无线电网络及分布式计算，E-mail: cuitaozhu@scuec.edu.cn

国家自然科学基金资助项目(61671483)；湖北省自然科学基金资助项目(2016CFA089);中央高校基本科研业务费专项资金项目(CZW15046)

TN911

A

1672-4321(2017)02-0091-06