-
随着移动互联网的高速发展,不断增长的数据业务对蜂窝网络的容量和速率的要求逐渐增加。近年来,蜂窝网络架构逐渐向异构化方向演进,通过在宏基站覆盖区域内大量架设低功率低能耗的小基站 (SBS),形成异构网络 (HetNets)[1],为用户提供更多的频谱资源,从而提升用户速率和系统容量。
在传统的蜂窝网络中,终端用户仅和宏基站关联,由于宏基站数量有限,相邻小区间的干扰可控,因此终端用户通常通过测量各宏基站的参考信号功率来选择信号最强的基站并与之关联。然而由于宏基站的覆盖范围内有大量的低功率小基站存在,通过测量参考信号来选择小区基站,必然造成大量的用户仍然选择和大功率的宏基站关联,使得宏基站和小基站的负载呈现较大差异,从而导致大量的资源浪费。因此需要将终端用户主动的和小基站关联,实现宏基站和小基站之间的负载均衡,从而更有效地利用小基站的无线资源[2]。宏基站和大量的小基站共享频谱资源,在下行链路中宏基站将对与小基站关联的用户形成强烈的干扰,导致这些用户的信号与噪声加干扰比 (signal to interference plus noise ratio, SINR) 降低,从而降低服务质量。因此用户关联策略也应考虑到基站负载均衡和网络服务质量的折中。
近年来,异构蜂窝网络中的用户关联策略已成为学术界和业界研究的热点。一种较简单的方案是小区范围扩展[3]。终端用户所接收的来自小基站的参考信号功率被人为放大,使得更多的用户选择与小基站关联。然而功率放大系数难以确定最优值。文献[4-5]提出了一种求解对数效用函数最优化问题来获取最优关联策略的方法,通过松弛约束条件转化为凸优化问题并对其拉格朗日对偶问题求解。然而获取的最优解要求允许用户可以同时和多个基站关联,难以实现。另一类方法则是用组合优化的方法来求解[6-9]。文献[7-8]通过求解基于二分图的匹配问题来获取用户关联策略,然而其用户关联策略并非以基站负载均衡为目的。文献[9]提出用贪心算法来求解效用函数最大化问题的次优解,并指出效用函数的最大化问题可转换为基于二分图的匹配问题,但没有考虑基站负载均衡和网络服务质量的折中。
本文提出了一种负载均衡度可调的用户关联策略,将用户与基站的关联建模为可调系数的效用函数最优化问题,以达到基站负载均衡和网络服务质量的折中。通过将该效用函数最大化问题转化成一个基于二部图的最大匹配问题,利用匈牙利算法求得最优解。实验结果表明,这种方法和传统的基于最大SINR的用户关联策略相比,实现了宏基站与小基站之间的负载均衡,通过调节系数,达到了基站负载和用户QoS之间的折中。
-
考虑一个异构蜂窝网络的下行链路部分,该异构蜂窝网络包含宏基站和一系列小基站。假定在小区覆盖范围内总共有M个基站和N个用户。集合$U=\left\{ 1,2,\cdots ,N \right\}$代表所有用户,集合$B=\left\{ 1,2,\cdots ,M \right\}$代表所有基站。基站$j\in B$的传输功率为Pj。所有的基站均工作在同一频段并且频率复用系数为1。系统带宽为W,信道取均值为1的瑞利衰落信道。
若用户i与基站j关联,则基站j到用户i的下行链路上的SINR可以表达为:
$$ \text{SIN}{{\text{R}}_{ij}}=\frac{{{P}_{j}}{{G}_{ij}}{{F}_{ij}}}{\sum\limits_{k\in B/j}{{{P}_{k}}{{G}_{ik}}{{F}_{ik}}+{{\sigma }^{2}}}} $$ (1) 式中,${{G}_{ij}}$是路径衰落、阴影效应等大尺度衰落产生的信道传输系数;${{F}_{ij}}$是瑞利衰落带来的信道传输系数,由于用户关联策略考虑较长时间内的系统性能,因此${{F}_{ij}}$取均值1。同时假设该网络为一个干扰受限的网络,此时信号干扰远大于噪声,噪声项${{\sigma }^{2}}\approx 0$。
用0-1变量${{x}_{ij}}$来表示用户i是否与基站j关联,${{x}_{ij}}=1$表示用户i与基站j关联,反之${{x}_{ij}}=0$。则与基站j关联的用户数量为$\sum\limits_{i\in U}{{{x}_{ij}}}$。由于基站j的资源由这些用户所共享,因此此时基站j到用户i的下行链路速率${{c}_{ij}}$为[5]:
$$ {{c}_{ij}}=\frac{W}{\sum\limits_{i\in U}{{{x}_{ij}}}}{{\log }_{2}}(1+\text{SIN}{{\text{R}}_{ij}}) $$ (2) 在后续的讨论中,假定信道带宽W归一化为1。由于用户i仅和单个基站关联,因此:
$$\sum\limits_{j\in B}{{{x}_{ij}}}=1$$ (3) 要获取用户与基站的关联策略,即求解关联策略变量x,其为$N\times M$的矩阵,各元素取值为$\left\{ 0,1 \right\}$。一种常见的方法是将用户-基站关联过程建模为一个效用函数最大化问题[4],其目标函数以用户速率${{c}_{ij}}$为自变量,而${{c}_{ij}}$与x有关:
$$ {{\max }_{\mathbf{x}}}f\left( \sum\limits_{j\in B}{{{c}_{ij}}} \right) $$ (4) 式中,$f(\cdot )$为效用函数。为鼓励用户与小基站关联并实现宏基站与小基站之间的负载均衡,取$f(\cdot )$为$\alpha $公平的目标函数,$\alpha $为公平性因子,当$\alpha =1$时目标函数即为对数函数,实现了用户速率的比例公平 (proportional fairness, PF)[4]。令${{s}_{ij}}={{\log }_{2}}(1+\text{SIN}{{\text{R}}_{ij}})$,此时该效用函数最大化问题建模为[5]:
$$ \begin{align} & {{\max }_{\mathbf{x}}}\sum\limits_{i\in U}{\sum\limits_{j\in B}{{{x}_{ij}}\log }}\left( \frac{{{s}_{ij}}}{\sum\limits_{i\in u}{{{x}_{ij}}}} \right) \\ & \ \ \ \ \ \ \text{s}\text{.t}\text{. }{{x}_{ij}}\in \left\{ 0,1 \right\} \\ & \ \ \ \ \ \ \ \ \ \ \sum\limits_{j\in B}{{{x}_{ij}}}=1 \\ \end{align} $$ (5) 然而式 (5) 是一个组合优化问题并且是NP困难问题。用穷举法列出x的所有可能取值需要$O({{M}^{N}})$的复杂度,而若将约束条件松弛为连续变量${{x}_{ij}}\in \left[ 0,1 \right]$,则式 (5) 转为凸优化问题,但是约束条件$\sum\limits_{j\in B}{{{x}_{ij}}}=1$导致所得的解要求一个用户同时与多个基站关联,并且所得的极值必然大于等于离散变量约束条件下的极值,因此是上限值。因此有必要考虑利用组合优化中的理论方法去求解该问题。同时,由于用户与小基站关联后导致用户SINR的降低,从而影响网络服务质量,因此所得出的用户关联策略应实现基站负载均衡和用户QoS之间的折中并且这种折中应当可以调整。
-
为实现基站负载均衡,仍然保留对数函数作为效用函数。首先式 (5) 中的约束条件可以导出隐式约束条件:
$$ \sum\limits_{i\in U}{\sum\limits_{j\in B}{{{x}_{ij}}}}=N $$ (6) 注意到式 (5) 的目标函数可以写成:
$$ \sum\limits_{i\in U}{\sum\limits_{j\in B}{{{x}_{ij}}\log ({{s}_{ij}})}}-\sum\limits_{j\in B}{\left( \sum\limits_{i\in U}{{{x}_{ij}}} \right)}\log \left( \sum\limits_{i\in U}{{{x}_{ij}}} \right) $$ (7) 对式 (7) 前半部分求极值,所得的最优解将导致用户和信号最强的基站关联 (此时${{s}_{ij}}$最大)。令$\sum\limits_{i\in U}{{{x}_{ij}}}={{K}_{j}}$,式 (7) 后半部分则可改写成$-\sum\limits_{j\in B}{{{K}_{j}}\log ({{K}_{j}})}$,结合隐式约束条件$\sum\limits_{j\in B}{{{K}_{j}}}=N$,对${{K}_{j}}$归一化后则对该部分求极值转换为熵最大化问题[10],所得的最优解将导致${{K}_{j}}$取均值,即用户在各基站之间均匀分布。因此可以将式 (5) 推广为一个双目标优化问题:
$${{\max }_{x}}\left( \sum\limits_{i\in U}{\sum\limits_{j\in B}{{{x}_{ij}}\log ({{s}_{ij}}),}}-\sum\limits_{j\in B}{\left( \sum\limits_{i\in U}{{{x}_{ij}}} \right)}\log \left( \sum\limits_{i\in U}{{{x}_{ij}}} \right) \right)$$ (8) 将式 (8) 线性化后,该优化问题表达为:
$$\begin{matrix} {{\max }_{x}}\beta \sum\limits_{i\in U}{\sum\limits_{j\in B}{{{x}_{ij}}\log ({{s}_{ij}})}}- \\ \text{(}1-\beta \text{)}\sum\limits_{j\in B}{\left( \sum\limits_{i\in U}{{{x}_{ij}}} \right)}\log \left( \sum\limits_{i\in U}{{{x}_{ij}}} \right) \\ \text{s}\text{.t}\text{. }{{x}_{ij}}\in \left\{ 0,1 \right\} \\ \sum\limits_{j\in B}{{{x}_{ij}}}=1 \\ \end{matrix}$$ (9) 式中,$0\le \beta \le 1$为可调系数。可以看出,式 (5) 是式 (9) 在$\beta =0.5$时的特例。当$0\le \beta < 0.5$时,式 (9) 的最优解将更偏向于子问题${{\max }_{x}}\left( \sum\limits_{j\in B}{\left( \sum\limits_{i\in U}{{{x}_{ij}}} \right)} \right.\times $ $\log \left. \left( \sum\limits_{i\in U}{ij} \right) \right)$,即所得的用户关联策略更偏向于基站之间的负载均衡。而当$0.5 < \beta \le 1$时,最优解将更偏向于子问题${{\max }_{x}}\left( \sum\limits_{i\in U}{\sum\limits_{j\in B}{{{x}_{ij}}\log ({{s}_{ij}})}} \right)$,即所得的用户关联策略更偏向于将用户和信号最强的基站关联。利用可调系数$\beta $,可以在负载均衡和用户QoS之间达到折中:若过多用户与小基站关联,QoS恶化而达不到需求时,可以选择调节$\beta $使得用户关联策略偏向于和最强信号基站关联,从而提高用户的SINR。式 (9) 仍然是一个组合优化问题。将式 (9) 进行转化后用组合优化中的最优匹配理论去求解。
-
首先将式 (9) 转化为用无向图来描述。由于基站集合$ B$与用户集合$ U$互不相交,因此定义图$G=(V,E)$,顶点$V=B\bigcup U$,若$ E$中的边一端连接$ B$中的顶点,另一端连接$ U$中的顶点,则基站与用户的关联可视为图$ G$的一个边集$L\subseteq E$,同时图$ G$也称为二部图。此时式 (9) 可视为对边集的权值之和求最大值,其中每条边的权值${{w}_{ij}}=\beta \log {{s}_{ij}}-(1-$ $\beta )\log \left( \sum\limits_{i\in U}{{{x}_{ij}}} \right)$。可以看出边的权值${{w}_{ij}}$与基站j的负载有关。式 (9) 的约束条件表明U中的每个顶点只能与一条边关联,而$ B$中的顶点可以同时与多条边关联。因此$ U$中的顶点和$B $中的顶点是多对一的映射关系。考虑将式 (9) 转化为一对一的映射并且将权值化为与${{x}_{ij}}$无关。
定义 1 图$G=(V,E)$的匹配是一个边集$ L$,使得$ G$的顶点无法与$ L$中多边关联。
为使得用户和基站的关联符合匹配的定义,将基站j用一个虚拟基站的集合${{B}^{(j)}}$来替代,由于基站j最多与N个用户关联,因此$\left| {{B}^{(j)}} \right|=N$。此时基站j与多个用户关联转化为每个用户与单个虚拟基站$l\in {{B}^{(j)}}$关联。因此基站和用户的关联,转化为二部图${G}'=({V}',{E}')$中的匹配,其中${V}'=\left( \bigcup\limits_{j=1}^{M}{{{B}^{(j)}}} \right)\bigcup U$,边集${E}'$中的边一端连接虚拟基站集合$\bigcup\limits_{j=1}^{M}{{{B}^{(j)}}}$中的顶点,另一端连接用户集合$ U$中的顶点。图 1说明了这种转换关系。
如图 1所示,基站1用虚拟基站集合${{B}^{(1)}}$替代,${{B}^{(1)}}$由4个虚拟基站组成。此时3个用户和基站1关联转化为这3个用户分别和基站1对应的虚拟基站集合${{B}^{(1)}}$中的3个虚拟基站匹配。接下来可以将用户与基站多对一关联下的权值求和转化为用户与虚拟基站的匹配权值之和。文献[9]提出了一种权值之和转化的方法。在此基础上,假设有q个用户和基站j关联,为便于表述,假定这q个用户编号从1~q。基站j对应的虚拟基站集合为${{B}^{(1)}}$,其中有N个虚拟基站。则定义任意用户i与虚拟基站$l\in {{B}^{(j)}}$关联的权值${{w}_{ij}}^{(l)}$如式 (10) 所示。
$$ \begin{matrix} {{w}_{ij}}^{(l)}= \\ \left\{ \begin{array}{*{35}{l}} \beta \log {{s}_{ij}}\text{ }l=1 \\ \beta \log {{s}_{ij}}+(1-\beta )((l-1)\log (l-1)-l\log l)\text{ }2\le l\le N \\ \end{array} \right. \\ \end{matrix} $$ (10) 定理 1 假设有q个用户和基站j关联,则其权值${{w}_{ij}}$之和等同于这q个用户与${{B}^{(j)}}$中前q个虚拟基站匹配的权值${{w}_{ij}}^{(l)}$之和。
证明:由于基站j与q个用户关联,因此基站j的负载$\sum\limits_{i\in U}{{{x}_{ij}}}=q$。此时这q个用户与基站j关联的权值之和为$\sum\limits_{i=1}^{q}{\beta \log {{s}_{ij}}-(1-\beta )q\log q}$。而若这q个用户与${{B}^{(j)}}$中前q个虚拟基站匹配,其权值之和:
$$ \begin{matrix} \sum\limits_{i=l=1}^{q}{wi{{j}^{(l)}}=\beta \log {{s}_{1j}}+\beta \log {{s}_{2j}}-(1-\beta )2\log 2}+\cdots + \\ \beta \log {{s}_{qj}}+(1-\beta )((q-1)\log (q-1)-q\log q)= \\ \sum\limits_{i=1}^{q}{\beta \log {{s}_{ij}}-(1-\beta )q\log q} \\ \end{matrix} $$ (11) 文献[9]已证明若匹配的权值满足定理1的性质,则用户与基站之间的关联问题等价于用户与虚拟基站之间的最大匹配问题,因此有如下结论。
推论 1 式 (9) 等价于以下二部图最优匹配问题:
$${{\max }_{\mathbf{x}}}\sum\limits_{i\in U}{\sum\limits_{j\in B}{\sum\limits_{l=1}^{N}{{{w}_{ij}}^{(l)}{{x}_{ij}}^{(l)}}}}$$ (12) $$ \text{s}\text{.t}\text{. }\sum\limits_{j\in B}{\sum\limits_{l=1}^{N}{{{x}_{ij}}^{(l)}}}=1,\forall i $$ (12a) $$\begin{matrix} \sum\limits_{i\in U}{{{x}_{ij}}^{(l)}}\le 1,\forall i,\forall l \\ {{x}_{ij}}^{(l)}\in \{0,1\} \\ \end{matrix}$$ (12b) 式 (12) 中,约束条件 (12a) 保证用户i只与单个虚拟基站关联,约束条件 (12b) 保证虚拟基站$l $最多只和一个用户关联。因此式 (12) 是一个二部图最大匹配问题,并且由于虚拟基站的数目大于用户数目,这种匹配是非完美匹配。
-
求解式 (12) 中的二部图最优匹配问题,可以使用文献[11]中提出的针对长方矩阵变量的匈牙利算法。匈牙利算法在求解二部图中的最优匹配时的复杂度为$O({{(\max (N,K))}^{3}})$,N,K为2个集合的维数。由于式 (12) 中虚拟基站的数量为$NM$,因此匈牙利算法在求解式 (12) 时复杂度为$O({{(NM)}^{3}})$,其复杂度仍远低于穷举法的复杂度$O({{M}^{N}})$。求出式 (12) 的解$x_{ij}^{(l)}$后,将矩阵按照列等分成M部分,每部分为N列,再观测矩阵第i行第j部分是否有1值,如果是则将${{x}_{ij}}$置为1。遍历每行后即获得了用户与基站的关联。算法描述如下所示。
1) 初始化:按照式 (10) 生成$N\times NM$维的权值矩阵w,初始化$N\times M$维的用户-基站关联矩阵X并置0。
2) 用匈牙利算法求解式 (12),求得的解${{X}^{*}}$为$N\times NM$维的用户-虚拟基站匹配矩阵。
3) for i=1~N
for k=1到$N\times M$
if $x_{ik}^{*}$为1且$(j-1)M+1\le k\le jM$
将${{x}_{ij}}$置为1
Break
End if
End for
End for
4) 输出X。
-
由于式 (9) 等价于式 (12),用匈牙利算法求得的二部图匹配式 (12) 的最优解,也是组合优化问题式 (9) 的最优解。由于式 (5) 是式 (9) 的特例,文献[4-5]提出将约束条件松弛为${{x}_{ij}}\in [0,1]$,从而将式 (5) 转化为凸优化问题求解。由于等式约束条件$\sum\limits_{j\in B}{{{x}_{ij}}}=1$的存在,对于用户i,求得的最优解中可能存在多个${{x}_{ij}}>0$。为保证用户和单个基站关联,文献[4-5]提出对最优解取整,即选取基站$j=\arg \underset{j\in B}{\mathop{\max }}\,\{{{x}_{ij}}\}$与用户i关联,从而获得式 (5) 的一个可行解。然而,这种做法导致效用函数值降低,同时,如果最优解中存在和用户i对应的多个相同的${{x}_{ij}}$最大值,则这种取整的方案只能随机选取其中一个基站与用户关联。因此,文献[4-5]中使用的凸优化-取整方案获得了式 (5) 的次优解。另一方面,文献[9]中提出使用贪心算法求解式 (5),但只证明了贪心算法获得的解接近最优解,因此求出的解仍然是次优解。
User Association in Heterogeneous Cellular Networks Via the Hungarian Method
-
摘要: 在异构蜂窝网络中使用传统的小区选择方法会导致宏基站和小基站的负载失衡,而与小基站关联的用户面临服务质量 (QoS) 的降低的问题。针对该问题,提出了一种基于效用函数最大化的用户与基站关联方法。该方法将用户与基站的关联过程建模为双目标优化问题并且线性化为系数可调的效用函数最大化问题,以实现基站负载均衡和用户QoS之间的折中。通过设计权值系数,将该效用函数最大化问题转化为基于二部图的最大匹配,并用匈牙利算法求得最优解。仿真结果表明,该方法实现了异构蜂窝网络中宏基站与小基站之间的负载均衡,并且通过系数调节,达到了基站负载均衡和用户QoS之间的折中。Abstract: In heterogeneous cellular networks, traditional user association schemes based on reference signal power result in load imbalances between macro cell base stations (MBSs) and small cell base stations (SBSs). Meanwhile, offloading users to SBSs face the quality of service (QoS) degradation. In this paper, we propose a utility maximization framework to address the user association problem. In order to strike a tradeoff between load balancing and user QoS experiences, a bi-criterion optimization problem is formulated to solve the user association problem. The bi-criterion optimization problem is then linearized as a utility maximization problem with a tunable parameter. In addition, we show that the utility maximization problem can be reformulated as a maximum bi-partite matching problem and can be solved in polynomial time by using the Hungarian method. Simulation results show that our proposed method achieves load balancing and can strike tradeoffs between load balancing and user QoS by tuning the optimization parameter.
-
Key words:
- bipartite matching /
- cell association /
- heterogeneous networks /
- Hungarian method /
- load balancing
-
[1] ANDREWS J G. Seven ways that HetNets are a cellular paradigm shift[J]. IEEE Communications Magazine, 2013, 51(3):136-144. doi: 10.1109/MCOM.2013.6476878 [2] ANDREWS J G, SINGH S, YE Qiao-yang, et al. An overview of load balancing in HetNets:Old myths and open problems[J]. IEEE Communications Magazine, 2014, 52(4):18-25. doi: 10.1109/MCOM.2014.6807942 [3] DAMNJANOVIC A, MONTOJO J, WEI Yong-bin, et al. A survey on 3GPP heterogeneous networks[J]. IEEE Wireless Communications Magazine, 2011, 18(3):10-21. doi: 10.1109/MWC.2011.5876496 [4] YE Qiao-yang, RONG Bei-yu, CHEN Yu-dong, et al. User association for load balancing in heterogeneous cellular networks[J]. IEEE Transactions on Wireless Communications, 2013, 12(6):2706-2716. doi: 10.1109/TWC.2013.040413.120676 [5] SHEN Kai-ming, YU Wei. Downlink cell association optimization for heterogeneous networks via dual coordinate descent[C]//Proceedings of IEEE Int. Conf. on Acoustics, Speech and Signal Processing. Vancouver, BC, Canada:IEEE, 2013:4779-4783. [6] GU Yun-an, SAAD W, BENNIS M, et al. Matching theory for future wireless networks:Fundamentals and applications[J]. IEEE Communications Magazine, 2015, 53(5):52-59. doi: 10.1109/MCOM.2015.7105641 [7] MISHRA S, RANGENENI S, MURTHY C. Exploiting an optimal user association strategy for interference management in HetNets[J]. IEEE Communications Letter, 2014, 18(10):1799-1802. doi: 10.1109/LCOMM.2014.2350502 [8] TAEJOON K, DONG Miao-miao. An iterative Hungarian method to joint relay selection and resource allocation for D2D communications[J]. IEEE Wireless Communication Letters, 2014, 3(6):625-628. doi: 10.1109/LWC.2014.2338318 [9] PRASAD N, ARSLAN M, RANGARAJAN S. Exploiting cell dormancy and load balancing in LTE HetNets:Optimizing the proportional fairness utility[J]. IEEE Transactions on Communications, 2014, 62(10):3706-3722. doi: 10.1109/TCOMM.2014.2359873 [10] BOYD S, VANDENBERGHE L. Convex optimization[M]. Cambridge:Cambridge University Press, 2004. [11] BOURGEOIS F, LASSALLE J C. An extension of the Munkres algorithm for the assignment problem to rectangular matrices[J]. Communications of the ACM, 1971, 14(12):802-804. doi: 10.1145/362919.362945