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

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

Abstract

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

CLC Number:

O221
TN92

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

References

[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.

Two optimization problems in wireless communication system design and related optimization methods

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 4

Recommended Articles

Metrics

Comments

[1]	HE Cheng, HAN Xinxin. Two-agent scheduling on an unbounded parallel-batching machine to minimize maximum cost and makespan [J]. Operations Research Transactions, 2018, 22(3): 109-116.
[2]	CHEN Xujin, XU Dachuan, ZHANG Guochuan. New perspectives of several fundamental problems in combinatorial optimization [J]. Operations Research Transactions, 2014, 18(1): 149-158.
[3]	GAO Jingzhen, GAO Bo. Chinese postman problem over 50 years [J]. Operations Research Transactions, 2013, 17(1): 17-28.
[4]	XU Jian-Teng, ZHANG Yu-Zhong, BAI Qing-Guo. A Polynomial Time Algorithm for the Economic Lot-size Problem with Multiple Suppliers and Multiple Retailers [J]. Operations Research Transactions, 2011, 15(4): 102-114.