基于阴影域的搜索树检测算法

doi:10.11772/j.issn.1001-9081.2018102174

计算机应用 ›› 2019, Vol. 39 ›› Issue (5): 1400-1404.DOI: 10.11772/j.issn.1001-9081.2018102174

基于阴影域的搜索树检测算法

李小文, 范艺芳, 侯宁宁

重庆邮电大学通信与信息工程学院重庆 400065

收稿日期:2018-10-29 修回日期:2018-12-29 发布日期:2019-05-14 出版日期:2019-05-10
通讯作者: 范艺芳
作者简介:李小文(1955-),男,重庆人,研究员,硕士,主要研究方向:协议栈开发与测试;范艺芳(1994-),女,河南洛阳人,硕士研究生,主要研究方向:物理层协议及算法;侯宁宁(1994-),女,河北邯郸人,硕士研究生,主要研究方向:物理层协议及算法。
基金资助:
国家科技重大专项（2017ZX03001021-004）。

Search tree detection algorithm based on shadow domain

LI Xiaowen, FAN Yifang, HOU Ningning

School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, China

Received:2018-10-29 Revised:2018-12-29 Online:2019-05-14 Published:2019-05-10
Supported by:
This work is partially supported by the National Science and Technology Major Special Project of China (2017ZX03001021-004).

摘要/Abstract

摘要： 大规模多输入多输出（MIMO）系统中，随着天线数目的增加，传统的信号检测算法的检测性能大幅度下降，复杂度呈指数增长，且不适用于高阶调制。针对大规模MIMO场景，基于阴影域思想提出一种结合二次规划（QP）与分支界限（BB）算法的搜索树检测算法。首先，构造QP模型，并针对一阶QP算法后的解向量，提取落入阴影域的不可靠符号；然后，将落入阴影域的不可靠符号进行BB搜索树检测以求得最优解；同时，为了降低复杂度，提出三种搜索树修剪策略，在性能和复杂度之间折中选择。仿真结果表明，在大规模MIMO场景下，在调制阶数为6的正交幅度调制（QAM）时，提出的基于阴影域搜索树检测算法比QP算法提升了约20 dB的性能增益，在256QAM调制时，比QP算法提升了约21 dB的性能增益，验证了算法对高阶调制的适应性，同时，与传统的搜索树算法相比，使用相同修剪策略，复杂度降低了50%左右。

关键词: 多输入多输出, 二次规划, 阴影域, 分支界限, 高阶调制

Abstract: In massive Multiple-Input-Multiple-Output (MIMO) system, as the increse of antenna number, traditional detection algorithms have lower performance, higher complexity, and they are not suitable for high order modulation. To solve the problem, based on the idea of shadow domain, a search tree detection algorithm combining Quadratic Programming (QP) and Branch and Bound (BB) algorithm was proposed. Firstly, with QP model constructed, the unreliable symbols from solution vector of first-order QP algorithm were extracted; then, BB search tree algorithm was applied to the unreliable symbols for the optimal solution; meanwhile three pruning strategies were proposed to reach a compromise between complexity and performance. The simulation results show that the proposed algorithm increases 20 dB performance gain compared with the traditional QP algorithm in 64 Quadrature Amplitude Modulation (QAM) and increases 21 dB performance gain compared with QP algorithm in 256 QAM. Meanwhile, applying the same pruning strategies, the complexity of the proposed algorithm is reduced by about 50 percentage points compared with the traditional search tree algorithm.

Key words: Multiple-Input-Multiple-Output (MIMO), Quadratic Programing (QP), shadow domain, Branch and Bound (BB), high order modulation

中图分类号:

TN929.5

李小文, 范艺芳, 侯宁宁. 基于阴影域的搜索树检测算法[J]. 计算机应用, 2019, 39(5): 1400-1404.

LI Xiaowen, FAN Yifang, HOU Ningning. Search tree detection algorithm based on shadow domain[J]. Journal of Computer Applications, 2019, 39(5): 1400-1404.

参考文献

[1] SHAFI M, MOLISCH A F, SMITH P J, et al. 5G: a tutorial overview of standards, trials, challenges, deployment and practice[J]. IEEE Journal on Selected Areas in Communications, 2017, 35(6): 1201-1221.
[2] YANG S, HANZO L. Fifty years of MIMO detection: the road to large-scale MIMOs[J]. IEEE Communications Surveys & Tutorials, 2015, 17(4): 1941-1988.
[3] RUSEK F, PERSSON D, LAU B K, et al. Scaling up MIMO: opportunities and challenges with very large arrays[J]. IEEE Signal Processing Magazine, 2012, 30(1): 40-60.
[4] CUI T, TELLAMBURA C. Approximate ML detection for MIMO systems using multistage sphere decoding[J]. IEEE Signal Processing Letters, 2005, 12(3): 222-225.
[5] HAN S, CUI T, TELLAMBURA C. Improved K-best sphere detection for uncoded and coded MIMO systems[J]. IEEE Wireless Communications Letters, 2012, 1(5): 472-475.
[6] DATTA T, SRINIDHI N, CHOCKALINGAM A, et al. Random-restart reactive tabu search algorithm for detection in large-MIMO systems[J]. IEEE Communications Letters, 2010, 14(12): 1107-1109.
[7] LI P, MURCH R D. Multiple output selection-LAS algorithm in large MIMO systems[J]. IEEE Communications Letters, 2010, 14(5): 399-401.
[8] AGARWAL S, SAH A K, CHATURVEDI A K. Likelihood based tree search for low complexity detection in large MIMO systems[J]. IEEE Wireless Communications Letters, 2017, 6(4): 450-453.
[9] KHAN I. A robust signal detection scheme for 5G massive multiuser MIMO systems[J]. IEEE Transactions on Vehicular Technology, 2018, 67(10): 9597-9604.
[10] ELGHARIANI A, ZOLTOWSKI M D. Low complexity detection algorithms in large-scale MIMO systems[J]. IEEE Transactions on Wireless Communications, 2016, 15(3):1689-1702.
[11] TANG C, TAO Y, CHEN Y, et al. Approximate iteration detection and precoding in massive MIMO[J]. China Communications, 2018, 15(5): 183-196.
[12] ELGHARIANI A, ZOLTOWSKI M. Branch and bound with M algorithm for near optimal MIMO detection with higher order QAM constellation[C]// Proceedings of the 2012 IEEE Military Communications Conference. Piscataway, NJ: IEEE, 2012: 1-5.
[13] RAO C V. Application of interior-point methods to model predictive control[J]. Journal of Optimization Theory & Applications, 1998, 99(3): 723-757.
[14] GONDZIO J. Interior point methods 25 years later[J]. European Journal of Operational Research, 2012, 218(3): 587-601.
[15] COHEN A I, YOSHIMURA M. A branch-and-bound algorithm for unit commitment[J]. IEEE Transactions on Power Apparatus & Systems, 1983, PER-3(2): 34-35.

基于阴影域的搜索树检测算法

Search tree detection algorithm based on shadow domain

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	雷芳, 牛永才. 基于改进广义正交匹配追踪的低地球轨道卫星MIMO-OTFS系统的信道估计方法[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2514-2520.
[2]	张奇业, 曾心蕊. 带高斯核的支持向量数据描述问题的高效积极集法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3808-3814.
[3]	张新贺, 谭浩然, 吕文博. 基于压缩感知的低复杂度广义空移键控信号检测算法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3890-3895.
[4]	刘帅, 蒋林, 李远成, 山蕊, 朱育琳, 王欣. 基于阵列处理器的最小均方误差检测算法并行设计与实现[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1524-1530.
[5]	郑鑫, 李素月, 王安红, 李美玲, MUHAIDAT Sami, 宁爱平. 协作多输入多输出环境反向散射通信系统遍历速率分析[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 974-979.
[6]	刘紫燕, 马珊珊, 白鹤. 基于改进智能水滴的正交匹配追踪混合预编码算法[J]. 计算机应用, 2021, 41(5): 1419-1424.
[7]	周围, 向丹蕾, 郭梦雨. MIMO-GFDM系统中低复杂度动态禁忌搜索检测算法的改进[J]. 计算机应用, 2019, 39(4): 1133-1137.
[8]	席皓哲, 王瑞峰. 基于天线分组的高铁大规模多输入多输出自适应波束赋形方案[J]. 计算机应用, 2019, 39(3): 839-844.
[9]	白鹤, 刘紫燕, 张杰, 万培佩, 马珊珊. 基于改进共轭梯度的大规模多输入多输出预编码[J]. 计算机应用, 2019, 39(10): 3007-3012.
[10]	李人敏, 黄劲松, 陈琛, 吴君钦. 基于改进粒子群算法的毫米波大规模MIMO混合预编码方案[J]. 计算机应用, 2018, 38(8): 2365-2369.
[11]	李松林, 贾勇, 郭勇, 钟晓玲, 崔国龙. 基于改进Camshift的穿墙雷达运动人体目标成像跟踪算法[J]. 计算机应用, 2018, 38(2): 528-532.
[12]	刘依, 胡哲, 景小荣. 多输入多输出—非正交多址接入系统融合用户调度的下行波束赋形设计[J]. 计算机应用, 2018, 38(11): 3282-3286.
[13]	刘紫燕, 唐虎, 刘世美. 基于压缩感知的多小区MASSIVE MIMO信道估计[J]. 计算机应用, 2017, 37(9): 2474-2478.
[14]	樊自甫, 胡敏, 李悦宁. 基于图着色的大规模MIMO系统中动态导频分配[J]. 计算机应用, 2017, 37(12): 3356-3360.
[15]	廖晗, 马东亚, 尹礼欣. 基于非正交多址的认知MIMO网络次用户系统容量优化[J]. 计算机应用, 2017, 37(12): 3361-3367.