基于ADMM的分布式功率分配和接入控制联合优化算法

林静然，姜昌旭，利 强，邵怀宗，李玉柏



基于ADMM的分布式功率分配和接入控制联合优化算法

林静然，姜昌旭，利 强，邵怀宗，李玉柏

(电子科技大学通信与信息工程学院 成都 611731)

传统网络节能问题在给定的服务质量(QoS)限制下实现传输功耗最小化。在此基础上引入接入控制，通过联合优化接入用户和发射功率进一步实现网络节能。当网络无法满足所有用户的QoS要求时，接入控制使网络服务尽可能多的用户。它还能对用户进行分类和挑选，以较低功耗代价满足接入用户的QoS条件，提高传输功效。在将原问题转换成一个近似的凸稀疏优化问题后，利用交错乘子法(ADMM)对其进行分布式迭代求解。该算法的每一步都具有闭合解，因此运算量很低。计算机仿真验证了该算法的正确性和有效性。

用户接入控制; 交错方向乘子法; 分布式算法; 绿色网络; 功率分配; 稀疏优化

作为无线通信网络管理的关键问题之一，网络节能或绿色通信受到了广泛的关注[1]。最常用的节能方法是功率分配，它在一定的服务质量(quality of service，QoS)限制条件下，通过优化各链路的传输功率使网络的功耗最小[2-3]。随着无线网络的快速发展，网络管理变得更加复杂和更具挑战，单纯依赖功率分配来实现网络节能越来越困难。事实上，人们普遍认为应该将功率分配和其他的网络管理手段(如波束形成[4-6]、用户调度[7]和协作处理[8-11]等)结合起来，共同实现网络节能。

除了上述方法外，接入控制也是一种非常有效的网络管理手段[12-16]。它通过有选择地接入某些用户来为网络优化提供更多的灵活性和更大的性能提升空间。由于问题本身的复杂性，接入控制往往作为独立的网络管理问题被单独研究，如分别以负载均衡[12]、系统容量[13]或阻塞概率[14]为目标制定相应的接入控制方案等。近年来，研究人员开始考虑将接入控制和其他网络管理方法联合起来进行网络优化。如文献[15]利用接入控制和波束形成等方法进行联合优化，提升网络频谱效率。文献[16]将接入控制和功率分配结合起来降低网络的功耗。

本文研究了与文献[16]相似的问题，即通过功率分配和接入控制的联合优化来实现网络节能，但采用了不同的接入控制策略和求解算法。文献[16]要求接入尽可能多的用户，并为此设计了基于交替紧缩搜索和功率分配的求解算法。具体而言，它首先固定发射功率，逐个排除无法满足QoS条件的用户；然后，基于固定的接入用户求解传统功率分配问题，更新发射功率；以此类推，直到交错优化过程收敛。与文献[16]不同，本文从稀疏优化的角度来描述功率分配和接入控制的联合优化问题，并在接入控制中采用一种更灵活的软策略。与之相对，文献[16]强制要求接入所有QoS可能被满足的用户，这可以看作是一种硬策略。软策略的灵活性主要体现在两方面：1) 当网络无法满足所有用户的QoS条件时，接入控制促使网络转而去服务尽可能多的用户，而非简单地拒绝所有用户。这提高了网络服务时间和用户接入概率。2) 在此基础上可以通过权重因子控制接入用户的数量。如果某个用户处于较差的信道环境，网络需要大大增加对应链路的发射功率以满足该用户的QoS条件。而这又对其他链路造成干扰，相应地其他链路也会增大发射功率，最终显著增加整个网络的功耗。软策略可以有选择地挑选用户接入，以相对较低的功耗代价满足接入用户的QoS条件，提升了功效。显然，与绝对功耗相比，功效是更为合理的节能指标。

算法方面，本文采用分布式求解策略。随着无线网络规模的增加，优化问题维数越来越大，分布式求解策略显然更具吸引力，即依赖于局部信道信息，或进行简单数据交换后，各基站可以自行决定是否接入对应用户。基于这一思路，本文对原始优化问题进行转换，使用交错方向乘子法(alternating direction method of multipliers，ADMM[5,17])将其分解成几个简单子问题进行分布式迭代求解。求解算法具有低运算量，每一步都有闭合解。

本文的主要工作为：1) 在传统功率分配问题中引入接入控制，进行联合优化实现网络节能，并通过接入控制软策略和稀疏优化完成用户分类和挑选，提高网络的传输功效。2) 基于ADMM框架设计分布式求解算法，在进行少量数据交换后，各链路自行决定是否建立连接，且分布式算法复杂度低，每一步都有闭合解。

1 系统模型和问题描述

1.1 系统模型

考虑一个由多个单天线基站和用户组成的无线通信网络。简便起见，假设基站和用户的数量均为，且用户指定接入到基站，= 1,2,…,。考虑下行链路，p表示基站的实际发射功率，P表示该基站发射功率上限。定义= [1,2,…,p]T为网络的实际发射功率矢量。

在此基础上，假设h,m为基站与用户之间的传输增益，,= 1,2,…,。以用户端的信号干扰噪声比(signal to interference plus noise ratio, SINR)来衡量网络服务质量QoS，假设用户的QoS门限为，则QoS条件表示为：

1.2 问题描述

传统的网络节能问题可以描述为：

在实际应用中该策略有两点不足。首先，由于发射功率存在上限，网络可能无法满足所有用户的QoS条件，导致(P1)没有可行解，整个网络停止工作。这种由于少量用户QoS无法满足，导致所有用户都不能接入的处理方式并不合理。更具实际意义的策略是，在网络无法满足所有用户的QoS条件时，应该尝试服务尽可能多的用户。其次，与绝对功耗相比，功效更能体现网络的节能程度，它描述了消耗单位功率实现的传输速率。如果某个用户位于恶劣的信道环境中，网络需要显著增加传输功率以满足该用户的QoS条件，并对抗由此给其他用户造成的干扰，会降低整个网络的功效。因此，需要在接入用户数和功效之间折衷，有选择地挑选某些用户优先接入。

基于上述考虑，在(P1)中融合接入控制，并以能否满足QoS条件作为用户接入依据。式等价为：

如果用户的QoS条件满足，则式成立；反之式不成立，它的左边应为正数。为了覆盖这两种情况，引入变量s = [1,2,…,s]T，s≥0，=1,2,…,，得到如下功率分配和接入控制联合优化问题，有：

对于优化后的结果，如果s= 0，有SINR=；如果s> 0，则SINR<，用户的QoS无法满足，不能接入。矢量的稀疏度||||0指示了接入的用户数量；> 0为权重因子，用于平衡接入用户数和传输功率，体现了接入控制软策略。

稀疏惩罚项中含有非凸的0范数，常用方法是将它松弛成1范数，即：

在(P3)中为各个|s|分配了不同的权重因子> 0，使问题的处理更加灵活。

2 分布式求解算法

(P3)是一个凸问题，可以利用软件包(如CVX[18]等)直接进行集中式求解。另一方面，随着用户和基站的增加，网络规模越来越大，(P3)的维数变高。集中式地求解高维优化问题增大了主处理器的负担。在这种情况下，分布式求解算法更具吸引力，其目的是依赖局部信息，在简单数据交换后，基站能自行决定是否接入对应用户。但是，由于功率变量p和接入变量s在QoS条件中耦合，直接对(P3)分布式求解十分困难。

2.1 问题转换

为了书写简便，将(P3)写成矩阵和矢量的形式，则有：

式中，矩阵ÎR´M和矢量ÎR´ 1定义如下：

与(P3)相比，(P4)去掉了s的非负限制。事实上，去掉限制s≥0并不影响(P3)的求解，或者说(P4)的最优解自动满足非负性。利用反证法，假设是(P4)的最优解，且存在,1≤≤，即：

对于用户，≠，用户的传输功率由降为，相当于减少了干扰，因此其QoS条件仍然满足。即将(*,*)中的换成，可以得到一个新的矢量对，表示为，它仍然位于(P4)的可行集内。显然，对应的目标函数值更小，因此，(*,*)不是(P4)的最优解，推出矛盾。

2.2 基于ADMM框架的分布式求解算法

使用增广拉格朗日(augmented lagrangian)方法[17]，(P4)的解可以通过求解(P5)获得，有：

式中，c > 0为惩罚因子；= [1,2, …,μ]T为限制条件+=对应的拉格朗日乘子；L(,,)为增广拉格朗日函数，定义为：

于是，可以将变量{,}分成{}和{}，在此基础上利用如下的ADMM框架[17]迭代求解(P5)，有：

式中，为迭代序号。由此变量和变量可以分开求解。进一步地，更新、和的过程还可以通过分布式的方式完成。

2.2.1 功率变量p的更新

更新等效于求解如下问题，有：

由于h,m为独立分布的随机信道，矩阵通常是满秩的，因此L(,(),())为关于的严格凸函数。此外，各个p具有独立的可行集。以上条件确保了坐标下降(coordinate descend，CD)法的收敛性[19]。因此，可以使用CD法求解该问题，即依次求解p,= 1,2,…,，直到收敛。在求解p时，将其他的p，≠，作为已知参数。

具体而言，以为CD法的迭代序号，p(,)为第轮ADMM迭代过程中，第次CD迭代后基站的传输功率，第+1次CD迭代过程如下：

1) 引入临时变量=(,) +–()；

2) 开始迭代，令=1,2,…,，重复如下操作：

①令=–p(,)b；

②求解如下优化问题，获得p(,+1)，有：

利用一阶最优条件，求得p(,+1)的最优解为：

3) 如果收敛，输出(+ 1) =(,)；否则，=+1，回到步骤2)；

因此，更新的工作可以由各个基站依次分布式完成，在当前基站完成更新后，只需要将传输给下一个基站即可。

2.2.2 接入变量s的更新

更新等效于求解如下的无限制优化问题，有：

它可以分解成个关于s的独立子问题，有：

同样，利用一阶最优条件，最优解s(+ 1)满足：

式中，∂|s(+ 1)|表示非连续的绝对值函数|s(+ 1)|的次梯度(sub-gradient)[20]，表示为：

为了表述简洁，令：

将式和式代入式(9)，可得：

因此，可以通过式更新s，=1,2,…,。上述过程可以分布式进行，即各基站基于式(11)并行地计算y，并根据|y|的大小更新s，由此自行决定是否接入用户。另外，式表明了的稀疏性，并且越大，表明稀疏惩罚项的权重越大，s越趋向为0，用户接入的概率也越大。

2.2.3 拉格朗日乘子μ的更新

利用式更新，它同样可以分布式进行，即独立地计算μ(+ 1)，= 1,2,…,，有：

2.3 分布式算法小结

基于ADMM的分布式功率分配和接入控制联合算法如下：

1) 令= 0；

2) 更新

①= 0；

②=(,) +–()；

③ for= 1:

=–p(,)；

=+p(,+ 1)；

end

④如果收敛，(+ 1) =(,+ 1)；

否则，=+ 1, 转到②；

3) 更新

for= 1:

end

4) 更新

for= 1:

end

5) 如果、和收敛，输出结果，停止；

否则，=+ 1, 转到步骤2)。

该算法的优点在于其主要步骤，更新、和等，都可以交给个基站分布式进行，同时仅需要很少的数据即可完成。其中，更新需要在各个基站间依次进行，而更新和则可以完全并行地分布式进行。该算法的每一步都通过闭合式直接计算，因此复杂度低。在每轮迭代中，每个基站的运算量仅为()，是一种高效的分布式求解算法。

另一方面，与并行更新接入矢量不同，在更新功率矢量的每一轮迭代中，需要依次更新p，=1, 2,…,。尽管更新p的运算非常简单，但当较大时，每一轮迭代等待时间会较长。因此，本文的后续工作是进一步研究并行更新p的算法，其主要难点是如何确保并行更新算法的收敛性。

3 计算机仿真

考虑一个正六边形的小区，相邻顶点的间距为1 000 m。内部有= 9个基站和相同数量的用户，且基站和用户在小区内随机分布。基站和用户间的传输信道, 其中d,m为基站和用户之间的距离，为路径损耗，本文取= 3.7，L,m～(0, 64)为阴影衰落因子。此外，假设用户端有0 dB的高斯白噪声，即2= 1，所有基站具有相同的功率上限1=2=…=9= 1 000，所有用户具有相同的接入优先级，即1=2=…=9。

为了直观地体现接入控制的效果，首先基于50个信道样本进行仿真。图1给出了仿真所得的用户接入状态。图中横轴为仿真序号，纵轴为用户序号；黑色小方格表示在该次仿真中，对应用户无法接入，白色表示能接入。在没有进行接入控制时，系统无法区别用户，所有用户要么全部接入，要么都无法接入。在图中的50次仿真中，只有20次用户能够接入。融合接入控制后，当网络无法满足所有用户的QoS要求时，可以挑选某些信道环境较好的用户进行接入，并且调整可以控制接入用户的数量。如对于本次仿真的第2个信道样本，系统无法满足所有用户，但引入接入控制后，当= 1时，有3个用户可以接入，当= 50时，接入用户数增加到6。

图2对100次仿真中各用户的平均接入概率进行了统计。用户接入概率随着QoS要求的增加而降低。没有进行接入控制的算法具有最低的用户接入概率。接入控制显著提高了用户接入概率。文献[16]的方法强制要求接入所有QoS能满足的用户，因此具有最高的用户接入概率。而本文提出的方法可以通过调节来实现不同程度的用户接入策略。可以看作是用户接入优先级，或者是拒绝一个用户带来的损失。它的值越大，网络越趋向接入更多的用户。图2的结果表明，在实际应用中进行接入控制是十分必要的，并且本文的方法在接入控制上比文献[16]的方法更灵活，可以通过增大的值来提高接入概率。在本例中，当= 100时，本文的方法与文献[16]方法的结果基本一致。

图3对网络传输功效进行了统计，传输功效为传输总速率和传输总功率之比，描述了消耗单位功率能实现的传输速率。在没有接入控制时，只统计所有用户都能接入时的传输功效。此时网络功效很低，因为接入所有用户使网络中同时传输的链路较多，它们相互干扰，网络必须增大传输功率以满足所有用户的QoS。引入接入控制使得网络挑选某些用户优先接入，能以较小的传输功率满足优先接入用户的QoS，提高了传输功效。另一方面，随着增大，接入用户数增加，相互之间干扰也更严重，传输功效相应降低。与文献[16]的方法相比，本文方法更灵活，可以通过调节来优选用户，提高网络传输功效。当=100时，二者的结果一致，因为此时二者接入用户的数量基本相同；然而，本文的方法还可以通过降低进一步优选用户，提高传输功效。在实际应用中，需要根据具体情况仔细选择，在传输功效和接入用户数之间实现平衡。该参数的选择与信道、QoS以及功率上限等诸多因素相关，目前难以获得解析表达式。如果网络希望接入更多的用户，可以设置较大的值，但此时功耗增加，功效降低；如果更看重传输功效，则需要减小，此时网络仅选择少量优质用户进行接入。

图4进一步比较了不同接入策略的传输功效。图中3种方案具有相同的用户接入数，由本文方法在=10时确定。由图可知，本文方法的性能远远优于随机选择接入用户的方法，其性能非常接近穷举搜索法。后者通过搜索所有的接入可能获得问题的最优解，但代价是其运算量随着网络规模呈指数增加。因此，本文的分布式算法以()的运算量，获得了原始优化问题的一个高效次优解。

4 结束语

本文研究了接入控制和功率分配的联合优化问题，以期在功效和接入用户数之间实现平衡。在将原问题近似成一个凸稀疏优化问题后，利用交错乘子法设计求解算法。该算法将求解任务分配给各个基站，进行分布式迭代求解，并且迭代过程的每一步都具有闭合解。本文的算法是一种高效的分布式算法，特别适合于大规模无线通信网络。

参 考 文 献

[1] 郭秉义. 绿色通信网络的节能算法研究[D]. 广州: 华南理工大学, 2014. GUO Bing-yi. Energy saving research for green communications networks[D]. Guangzhou: South China University of Technology, 2014.

[2] YATES R D. A framework for uplink power control in cellular radio systems[J]. IEEE Journal on Selected Areas in Communications, 1995, 13(7): 1341-1347.

[3] FOSCHINI G J, MILJANIC Z. A simple distributed autonomous power control algorithm and its convergence[J]. IEEE Trans Vehicular Technology, 1993, 42(4): 641-646.

[4] SCHUBERT M, BOCHE H. Solution of multiuser downlink beamforming problem with individual SINR constraints[J]. IEEE Trans Vehicular Technology, 2004, 53(1): 18-28.

[5] LIN J R, LI Y B, PENG Q C. Joint power allocation, base station assignment and beamformer design for an uplink SIMO heterogeneous network[C]//IEEE Int’l Conf on Acoustics Speech, and Signal Processing (ICASSP). Florence: IEEE, 2014: 434-438.

[6] SIDIROPOULOS N D, DAVIDSON T N, LUO Z Q. Transmit beamforming for physical-layer multicasting[J]. IEEE Trans Signal Processing, 2006, 54(6): 2239-2251.

[7] 黄晓燕, 毛玉明, 吴凡, 等. 中继增强的无线蜂窝多小区系统的联合调度与功率控制算法[J]. 电子与信息学报, 2012, 37(7): 1665-1671. HUANG Xiao-yan, MAO Yu-ming, WU Fan, et al. Coordinated scheduling and power control algorithm for relay-enhanced cellular network with multicells[J]. Journal of Electronics & Information Technology, 2012, 37(7): 1665-1671.

[8] SARAYDA C U, MANDAYAM N B, GOODMAN D J. Pricing and power control in a multicell wireless date network[J]. IEEE Journal on Selected Areas in Communications, 2001, 19(10): 1883-1892.

[9] 冯文江, 蒋卫恒, 邓艺娜, 等. 基于非信任中继协作的保密通信联合功率控制[J]. 通信学报, 2014, 35(11): 59-68. FENG Wen-jiang, JIANG Wei-heng, DENG Yi-na, et al. Joint power control for untrusted relay cooperation-based confidential communication[J]. Journal on Communica- tions, 2014, 35(11): 59-68.

[10] GESBERT D, HANLY S, HUANG H, et al. Multi-cell MIMO cooperative networks: a new look at interference[J]. IEEE Journal on Selected Areas in Communications, 2010, 28(9): 1380-1408.

[11] DAHROUJ H, YU W. Coordinated beamforming for the multi-cell multi-antenna wireless system[J]. IEEE Trans Wireless Communications, 2010, 13(7): 1332-1340.

[12] 何蓉. 无线Mesh网络高效公平接入控制技术研究[D]. 成都: 西南交通大学, 2011. HE Rong. Research on efficient and fair access control technologies in wireless mesh network[D]. Chengdu: Southwest Jiaotong University, 2011.

[13] 苏伟, 刘琪, 袁坚, 等. 基于终端移动与业务达到认知的自适应无线接入控制机制[J]. 电子学报, 2011, 39(9): 2148-2153. SU Wei, LIU Qi, YUAN Jian, et al. Adaptive radio access control scheme based on terminal mobility and service arriving cognition[J]. Acta Electronica Sinica, 2011, 39(9): 2148-2153.

[14] 王庆敏. 绿色节能通信网络中基站与用户的联合最优接入控制[D]. 大连: 大连理工大学, 2013. WANG Qing-min. Optimal joint base station and user equipment admission control for green wireless cellular networks[D]. Dalian: Dalian University of Technology, 2013.

[15] KUANG Q, SPEIDEL J, DROSTE H. Joint base-station association, channel assignment, beamforming and power control in heterogeneous networks[C]//IEEE the 75thVehicular Technology Conference. Yokuhama: IEEE, 2012: 1-5.

[16] LIU Y F, DAI Y H, LUO Z Q. Joint power and admission control via linear programming deflation[J]. IEEE Trans Signal Processing, 2013, 61(6): 1327-1338.

[17] FUKUSHIMA M. Application of the alternating direction method of multipliers to separable convex programming problems[J]. Computational Optimization and Applications, 1992, 1(1): 93-111.

[18] GRANT M C, BOYD S P. The CVX users’ guide[[J/OL]. [2014-10-24]. http://cvxr.com/cvx/.

[19] BERTSEKAS D P. Nonlinear programming[M]. Second ed. Belmont, MA, USA: Athena Scientific, 1999.

[20] KIWIEL K. Methods of descent for nondifferentiable optimization[M]. Berlin: Springer, 1985.

编 辑 黄 莘

Distributed Method for Joint Power Allocation and Admission Control Based on ADMM Framework

LIN Jing-ran, JIANG Chang-xu, LI Qiang, SHAO Huai-zong, and LI Yu-bai

(School of Communication and Information Engineering, University of Electronic Science and Technology of China Chengdu 611731)

The traditional green networks are usually achieved by minimizing the transmit power under some quality of service (QoS) constraints. In this paper, admission control is integrated with power allocation to pursue further performance improvement in green communication. This technique enables the network to serve as many users as possible when the network cannot guarantee all the users’ QoS requirements. Moreover, it classifies the users and picks out a subset of admissible users whose QoS constraints can be easily satisfied with relatively low power consumption; thus the power efficiency is improved. After approximating the original joint power and admission control problem by a convex sparse optimization problem, an efficient distributed algorithm is developed for the approximated problem by fitting it into the alternating direction method of multipliers (ADMM) framework. Specifically, each iteration of ADMM can be computed in closed form, thus giving it very low complexity. The effectiveness of the proposed algorithm is validated by a series of numerical simulations.

admission control; alternating direction method of multipliers; distributed algorithm; green network; power allocation; sparse optimization

TN911

A

10.3969/j.issn.1001-0548.2016.05.003

2015-03-28；

2015-11-27

国家自然科学基金(61471103，61401073)；四川省应用基础项目(2015JY0102)

林静然(1978-)，男，博士，副教授，主要从事现代通信信号处理方面的研究.