无线通信系统设计中的两个优化问题和相关优化方法

doi:10.15960/j.cnki.issn.1007-6093.2019.03.004

摘要/Abstract

摘要： 无线通信系统设计中的许多问题可建模为优化问题.一方面，这些优化问题常常具有高度的非线性性，一般情况下难于求解；另一方面，它们又有自身的特殊结构，例如隐含的凸性、可分性等.利用优化的方法结合问题的特殊结构求解和处理无线通信系统设计问题是近年来学术界研究的热点.本文重点讨论无线通信系统设计中的两个优化问题和相关优化方法，包括多用户干扰信道最大最小准则下的联合传输/接收波束成形设计和多输入多输出（Multi-Input Multi-Output，MIMO）检测问题，主要介绍现代优化技术结合问题的特殊结构在求解和处理上述两个问题的最新进展.

关键词: 半正定松弛, 变量交替最优化, 多用户干扰信道, 联合传输/接收波束成形设计, 计算复杂性, 紧松弛, MIMO检测, 无线通信系统

Abstract: Many problems arising from wireless communication system design can be formulated as optimization problems. On the one hand, these optimization problems are often non-convex and highly nonlinear and thus are difficult to solve; on the other hand, these problems have their own special structures such as (hidden) convexity and separability. Recently applying mathematical optimization methods to solve/deal with these problems while judiciously taking care of their special structures is a hot research topic. This (survey) paper aims to introduce two optimization problems in wireless communication system design, max-min fairness linear transceiver design problem and MIMO detection problem, and related optimization methods. This paper will focus on the above two problems and overview recent advances of applying mathematical optimization techniques to solve/deal with them by exploiting their special structures.

Key words: semi-definite relaxation, alternating optimization, multiuser interference channel, transceiver beamforming design, computational complexity, tight relaxation, MIMO detection, wirelesscommunication system

中图分类号:

O221
TN92

刘亚锋. 无线通信系统设计中的两个优化问题和相关优化方法[J]. 运筹学学报, 2019, 23(3): 47-62.

LIU Yafeng. Two optimization problems in wireless communication system design and related optimization methods[J]. Operations Research Transactions, 2019, 23(3): 47-62.

参考文献

[1] 袁亚湘, 孙文瑜. 最优化理论与方法[M]. 北京:科学出版社, 1997.
[2] Nocedal J, Wright S J. NumericalOptimization[M]. New York:Springer Science+Business Media, 2006.
[3] Bertsekas D. Nonlinear Programming[M]. Belmont:Athena Scientific, 1999.
[4] Tse D, Viswanath P. Fundamental of Wireless Communications[M]. New York:Cambridge University Press, 2005.
[5] Cover T M, Thomas J A. Elements of Information Theory[M]. NewYork:John Wiley & Sons, Inc., 2006.
[6] Goldsmith A. Wireless Communications[M]. New York:CambridgeUniversity Press, 2006.
[7] Shannon CE. A mathematical theory of communication[J]. TheBell System Technical Journal, 1948, 5:379-423, 623-656.
[8] Garey M R, Johnson D S. Computers and Intractability:A Guideto the Theory of NP-Completeness[M]. San Francisco:W. H. Freeman and Company, 1979.
[9] Luo Z Q, Yu W. An introduction to convex optimization for communications and signal processing[J]. IEEE Journal on Selected Areas in Communications, 2006, 24(8):1426-1438.
[10] Luo Z Q. Applications of convex optimization in signal processingand digital communication[J]. Mathematical Programming, 2003, 97(1-2):177-207.
[11] Luo Z Q, Ma W K, So A M C, et al. Semidefinite relaxation of quadratic optimization problems[J]. IEEE Signal Processing Magazine, 2010, 27(3):20-34.
[12] Gershman A B, Sidiropoulos N D, Shahbazpanahi S, et al. Convex optimization-based beamforming[J]. IEEESignal Processing Magazine, 2010, 27(3):62-75.
[13] Björnson E, Jorswieck E. Optimal resource allocation incoordinated multi-cell systems[J]. Foundations and Trends® in Communications and Information Theory, 2013, 9(2-3):113-381.
[14] Hong M, Luo Z Q. Signal processing and optimal resourceallocation for the interference channel[M]//Academic Press Library in Signal Processing. Elsevier, 2014, 409-469.
[15] Gesbert D, Hanly S, Huang H, et al. Multi-cellMIMO cooperative networks:A new look at interference[J]. IEEE Journal on Selected Areas in Communications, 2010, 28(9):1380-1408.
[16] 刘亚锋. 无线通信中的最优资源分配-复杂性分析与算法设计[J]. 中国科学:数学, 2013, 43(10):953-964.
[17] Schubert M, Boche H. Solution of the multiuser downlink beamforming problem with individual SINR constraints[J]. IEEE Transactions on Vehicular Technology, 2004, 53(1):18-28.
[18] Wiesel A, Eldar Y C, Shamai S. Linear precoding via conic optimization for fixed MIMO receivers[J]. IEEE Transactions on Signal Processing, 2006, 54(1):161-176.
[19] Liu Y F, Dai Y H, Luo Z Q. Coordinated beamforming for MISO interference channel:Complexity analysis and efficient algorithms[J]. IEEE Transactions on Signal Processing, 2011, 59(3):1142-1157.
[20] Xia Y. A survey of hidden convex optimization[J]. 2019. Available:https://arxiv.org/abs/1902.10921
[21] Liu Y F, Hong M, Dai Y H. Max-min fairness linear transceiver design problem for a multi-user SIMO interference channel is polynomial time solvable[J]. IEEE Signal Processing Letters, 2013, 20(1):27-30.
[22] Liu Y F. Dynamic spectrum management:A complete complexity characterization[J]. IEEE Transactions on Information Theory, 2017, 63(1):392-403.
[23] Powell M J. On search directions for minimization algorithms[J].Mathematical Programming, 1973, 4(1):193-201.
[24] Liu Y F, Dai Y H, Luo Z Q. Max-min fairness linear transceiver design for a multi-user MIMO interference channel[C]//Proceedings of IEEE International Conference on Communications (ICC), 2011, 1-5.
[25] Liu Y F, Dai Y H, Luo Z Q. Max-min fairness linear transceiver design for a multi-user MIMO interference channel[J]. IEEE Transactions on Signal Processing, 2013, 61(9):2413-2423.
[26] Yu W, Kwon T, Shin C. Adaptive resource allocation incooperative cellular networks[M]//Cooperative Cellular Wireless Networks. New York:Cambridge University Press, 2010, 233-256.
[27] Zhang J, Chen R, Andrews J G, et al. Networked MIMO with clustered linear precoding[J]. IEEE Transactions on Wireless Communications, 2009, 8(4):1910-1921.
[28] Chen E, Tao M, Liu Y F. Joint base station clustering and beamforming for non-orthogonal multicast and unicasttransmission with backhaul constraints[J]. IEEE Transactionson Wireless Communications, 2018, 17(9):6265-6279.
[29] Ng C T, Huang H. Linear precoding in cooperative MIMO cellular networks with limited coordination clusters[J]. IEEE Journal on Selected Areas in Communications, 2010, 28(9):1446-1454.
[30] Hong M, Sun R, Baligh H, et al. Joint base station clustering and beamformer design for partial coordinated transmission in heterogeneous networks[J]. IEEE Journal on Selected Areas in Communications, 2013, 31(2):226-240.
[31] Dai B, Yu W. Sparse beamforming and user-centric clustering fordownlink cloud radio access network[J]. IEEE Access, 2014, 2:1326-1339.
[32] Shi Y, Zhang J, Letaief K. Group sparse beamforming for green cloud-RAN[J]. IEEE Transactions on Wireless Communications, 2014, 13(5):2809-2823.
[33] Tao M, Chen E, Zhou H, et al. Content-centric sparse multicast beamforming for cache-enabled cloud RAN[J]. IEEE Transactions on Wireless Communications, 2016, 15(9):6118-6131.
[34] Liao W C, Hong M, Liu Y F, et al. Base station activation andlinear transceiver design for optimal resource management in heterogeneous networks[J].IEEE Transactions on Signal Processing, 2014, 62(15):3939-3952.
[35] Shen K, Yu W. Distributed pricing-based user association for downlink heterogeneous cellular networks[J]. IEEE Journal on Selected Areas in Communications, 2014, 32(6):1100-1113.
[36] Shen K, Liu Y F, Ding D Y, et al. Flexible multiple base station association and activation for downlink heterogeneous networks[J].IEEE Signal Processing Letters, 2017, 24(10):1498-1502.
[37] Sanjabi M, Razaviyayn M, Luo Z Q. Optimal joint base stationassignment and beamforming for heterogeneous networks[J].IEEE Transactions on Signal Processing, 2014, 62(8):1950-1961.
[38] Shi Q, Razaviyayn M, Luo Z Q, et al. An iteratively weighted MMSE approach to distributed sum-utility maximization for a MIMO interfering broadcast channel[J]. IEEE Transactions on Signal Processing, 2011, 59(9):4331-4340.
[39] Zhang X, Chang T H, Liu Y F, et al. Max-min fairness userscheduling and power allocation in full-duplex OFDMA systems[J]. IEEE Transactions on Wireless Communications, 2019, 18(6):3078-3092.
[40] Codreanu M, Tölli A, Juntti M, et al. Joint design ofTx-Rx beamformers in MIMO downlink channel[J]. IEEE Transactions on Signal Processing, 2007, 55(9):4639-4655.
[41] Chang T H, Liu Y F, Lin S C. QoS-based linear transceiveroptimization for full-duplex multi-user communications[J].IEEE Transactions on Signal Processing, 2018, 66(9):2300-2313.
[42] Li Q, Hong M, Wai H T, et al. Transmit solutions for MIMO wiretap channels using alternating optimization[J].IEEE Journal on Selected Areas in Communications, 2013, 31(9):1714-1727.
[43] Hong M, Li Q, Liu Y F. Decomposition by successive convexapproximation:A unifying approach for linear transceiver design in heterogeneous networks[J].IEEE Transactions on Wireless Communications, 2016, 15(2):1377-1392.
[44] Wright S J. Coordinate descent algorithms[J]. MathematicalProgramming, 2015, 151(1):3-34.
[45] Hong M, Razaviyayn M, Luo Z Q, et al. A unified algorithmic framework for block-structured optimization involving big data:With applications in machine learning and signal processing[J]. IEEE Signal Processing Magazine, 2016, 33(1):57-77.
[46] Verdú S. Multiuser Detection[M]. New York:Cambridge University Press, 1998.
[47] Yang S, Hanzo L. Fifty years of MIMO detection:The road tolarge-scale MIMOs[J]. IEEE Communication Surveys & Tutorials, 2015, 17(4):1941-1988.
[48] Verdú S. Computational complexity of optimum multiuser detection[J]. Algorithmica, 1989, 4(1-4):303-312.
[49] Kisialiou M, Luo X, Luo Z Q. Efficient implementation of quasi-maximum-likelihood detection based on semidefinite relaxation[J].IEEE Transactions on Signal Processing, 2009, 57(12):4811-4822.
[50] Fincke U, Pohst M. Improved methods for calculating vectors of shortlength in a lattice, including a complexity analysis[J].Mathematics of Computation, 1985, 44(170):463-471.
[51] Viterbo E, Boutros J. A universal lattice code decoder for fadingchannels[J]. IEEE Transactions on Information Theory, 1999,45(5):1639-1642.
[52] Damen M O, Gamal H E, Caire G. On maximum-likelihood detection andthe search for the closest lattice point[J]. IEEE Transactionson Information Theory, 2003, 49(10):2389-2402.
[53] Jaldén J, Ottersten B. On the complexity of sphere decoding indigital communications[J].IEEE Transactions on Signal Processing, 2005, 53(4):1474-1484.
[54] Lu C, Liu Y F, Zhang W Q, et al. Tightness of a new and enhanced semidefinite relaxation for MIMO detection[J].SIAM Journal on Optimization, 2019, 29(1):719-742.
[55] Lu C, Liu Y F. An efficient global algorithm for single-groupmulticast beamforming[J]. IEEE Transactions on Signal Processing, 2017, 65(14):3761-3774.
[56] Lu C, Deng Z, Zhang W Q, et al. Argument division based branch-and-bound algorithm for unit-modulus constrained complex quadratic programming[J]. Journal of Global Optimization, 2018, 70(1):171-187.
[57] Jaldén J. Detection for multiple input multiple output channels:Analysis of sphere decoding and semidefinite relaxation. Ph.D. thesis. Stockholm:KTH, 2006.
[58] Jaldén J, Martin C, Ottersten B. Semidefinite programming for detection in linear systems-Optimality conditions and space-time decoding[C]//Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2011, 9-12.
[59] Kisialiou M, Luo Z Q. Probabilistic analysis of semidefiniterelaxation for binary quadratic minimization[J].SIAM Journal on Optimization, 2010, 20(4):1906-1922.
[60] So A M C. Probabilistic analysis of the semidefinite relaxationdetector in digital communications[C]//Proceedings of twenty-first annual ACM-SIAM symposium on Discrete Algorithms (SODA), 2010, 698-711.
[61] Mobasher A, Taherzadeh M, Sotirov R, et al. A near-maximum-likelihood decoding algorithm for MIMO systems based on semi-definite programming[J]. IEEE Transactions on Information Theory, 2007, 53(11):3869-3886.
[62] Liu Y F, Xu Z, Lu C. On the equivalence of semidifinite relaxationsfor MIMO detection with general constellations[C]//Proceedings of ICASSP, 2019, 4549-4553.
[63] Lu C, Liu Y F, Zhou J. An enhanced SDR based global algorithm for nonconvex complex quadratic programs with signal processing applications[J]. arXiv:1902.04287.
[64] Liu H, Yue M C, So A M C, et al. A discrete first-order method for large-scale MIMO detection with provable guarantees[C]//Proceedings of IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), 2017, 669-673.
[65] Burer S, Monteiro R D, Zhang Y. Rank-two relaxation heuristics for max-cut and other binary quadratic programs[J].SIAM Journal on Optimization, 2002, 12(2):503-521.
[66] Luo Z Q, Luo X, Kisialiou M. An efficient quasi-maximum likelihood decoder for PSK signals[C]//Proceedings of ICASSP, 2003, 561-564.
[67] Pan J, Ma W K, Jaldén J. MIMO detection by Lagrangian dual maximum-likelihood relaxation:Reinterpreting regularized lattice decoding[J].IEEE Transactions on Signal Processing, 2014, 62(2):511-524.
[68] Lu C, Liu Y F, Zhou J. An efficient global algorithm for nonconvex complex quadratic problems with applications in wireless communications[C]//Proceedings of IEEE/CIC International Conference on Communications in China (ICCC), 2017, 1-5.
[69] Vandenberghe L, Boyd S. Semidefinite programming[J]. SIAMReview, 1996, 38(1):49-95.
[70] Pu W, Liu Y F, Yan J, et al. Optimal estimation of sensor biases for asynchronous multi-sensor data fusion[J]. Mathematical Programming, 2018, 170(1):357-386.
[71] Andrews J G, Buzzi S, Choi W, et al. What will 5G be?[J]. IEEE Journal on Selected Areas in Communications, 2014, 32(6):1065-1082.
[72] 尤肖虎, 潘志文, 高西奇, 等. 5G移动通信发展趋势与若干关键技术[J]. 中国科学:信息科学, 2014, 44:551-563.
[73] Tao M, Chen E, Yu W, et al. Cache-enabled cloud radio access networks[M]//Wireless Edge Caching:Modeling, Analysis and Optimization, Cambridge University Press, 2019.
[74] Dai B, Liu Y F, Yu W. Optimized base-station cache allocation for cloud radio access network with multicast backhaul[J]. IEEE Journal on Selected Areas in Communications, 2018, 36(8):1737-1750.
[75] Jacobsson S, Durisi G, Coldrey M, et al. Quantizedprecoding for massive MU-MIMO[J]. IEEE Transactions onCommunications, 2017, 65(11):4670-4684.
[76] Sohrabi F, Liu Y F, Yu W. One-bit precoding and constellation range design for massive MIMO with QAM signaling[J]. IEEE Journal of Selected Topics in Signal Processing, 2018, 12(3):557-570.
[77] Zhang N, Liu Y F, Farmanbar H, et al. Network slicing for service-oriented networks under resource constraints[J]. IEEE Journal on Selected Areas in Communications, 2017, 35(11):2512-2521.
[78] Domenico A D, Liu Y F, Yu W. Optimal computational resource allocation and network slicing deployment in 5G hybrid C-RAN[C]//Proceedings of IEEE International Conference on Communications (ICC), 2019.
[79] Liu L, Larsson E G, Yu W, et al. Sparse signal processing for grant-free massive connectivity:A future paradigm for random access protocols in the Internet of Things[J]. IEEE Signal Processing Magazine, 2018, 35(5):88-99.
[80] Chen Z, Sohrabi F, Liu Y F, et al. Covariance based joint activity and data detection for massive random access with massive MIMO[C]//Proceedings of IEEE International Conference on Communications (ICC), 2019.