基于陰影域的搜索樹檢測算法

李小文 范藝芳 侯寧寧

摘 要：大規模多輸入多輸出（MIMO）系統中，隨著天線數目的增加，傳統的信號檢測算法的檢測性能大幅度下降，復雜度呈指數增長，且不適用于高階調制。針對大規模MIMO場景，基于陰影域思想提出一種結合二次規劃（QP）與分支界限（BB）算法的搜索樹檢測算法。首先，構造QP模型，并針對一階QP算法后的解向量，提取落入陰影域的不可靠符號; 然后，將落入陰影域的不可靠符號進行BB搜索樹檢測以求得最優解; 同時，為了降低復雜度，提出三種搜索樹修剪策略，在性能和復雜度之間折中選擇。仿真結果表明，在大規模MIMO場景下，在調制階數為6的正交幅度調制（QAM）時，提出的基于陰影域搜索樹檢測算法比QP算法提升了約20dB的性能增益，在256QAM調制時，比QP算法提升了約21dB的性能增益，驗證了算法對高階調制的適應性，同時，與傳統的搜索樹算法相比，使用相同修剪策略，復雜度降低了50%左右。

關鍵詞：多輸入多輸出;二次規劃;陰影域;分支界限;高階調制

中圖分類號：TN929.5

文獻標志碼：A

Abstract： In massive MultipleInputMultipleOutput （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 firstorder 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 20dB performance gain compared with the traditional QP algorithm in 64 Quadrature Amplitude Modulation （QAM） and increases 21dB 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： MultipleInputMultipleOutput （MIMO）; Quadratic Programing （QP）; shadow domain; Branch and Bound （BB）; high order modulation

0 引言

大規模多輸入多輸出（MultipleInputMultipleOutput， MIMO）是5G的關鍵技術之一[1]，可實現更高的傳輸速率，提升系統容量。該系統在信道估計、天線相關性、硬件實現，以及低復雜度的信號檢測方面是非常具有研究意義的[2-3]。人們在傳統的MIMO系統中提出了許多線性檢測和接近最大似然檢測算法，例如，在文獻[4]提出的多階段球形譯碼檢測算法與文獻[5]提出的Kbest球形檢測算法，能夠達到近似最大似然（Maximum Likelihood， ML）檢測算法的性能，但其復雜度隨天線數目和調制階數的增加呈指數增長;另一方面，低復雜度的檢測算法，例如最小均方誤差（Minimum Mean Square Error， MMSE）算法，其性能隨天線數目的增加而惡化。

針對大規模MIMO系統，為了平衡因天線數目增加而帶來的性能流失以及復雜度問題，主動禁忌搜索算法（Reactive Tabu Search， RTS）[6]以及似然上升搜索（Likelihood Ascend Search， LAS）檢測算法[7]被提出，它們是基于一些良好的初始向量局部鄰域的搜索，例如MMSE向量，當天線數目達到上百時，其也能達到接近單天線的加性高斯白噪聲（Additive Gaussian White Noise， AWGN）性能，每個接收向量的復雜度為O（NT3）（NT為發射天線數量），但其性能隨調制階數的增加而惡化。文獻[8]提出的似然搜索樹檢測（Likelihood Based Tree Search， LBTS）算法，相對于傳統分支界限（Branch and Bound， BB）搜索樹，避免了在每個節點求最優解，而是運用節點選擇策略，在每個節點對符號出錯概率進行評估，大幅降低了計算復雜度，當調制階數增加時，性能惡化明顯。文獻[9]針對大規模多用戶多輸入多輸出（MultiUser MIMO， MUMIMO）系統基站檢測復雜度高的問題，提出了一種基于強迫收斂算法的可變節點全信息高斯消息傳遞迭代檢測算法，降低了算法的復雜度，但帶來了性能的相對損失，且在高階調制時，性能流失嚴重。文獻[10]提出的二階二次規劃（Twostage Quadratic Programing， 2QP）算法，在二次規劃（Quadratic Programing， QP）的基礎上，加入判定標準，對不可靠符號進行2QP算法，相對于一階QP算法，提高了可靠性。文獻[11]結合多種迭代算法，提出適用于大規模MIMO優化的近似迭代檢測算法，以增加復雜度來換取迭代的優化，但性能隨調制階數增加而惡化。

本文結合QP與BB搜索樹算法[12]，并結合陰影域思想，提出一種基于陰影域的搜索樹檢測算法。首先構造QP模型，針對一階QP算法后的解向量，提取落入陰影域的不可靠符號;然后將落入陰影域的不可靠符號進行BB搜索樹檢測;同時，為了降低復雜度，提出三種搜索樹修剪策略，可調整修剪方案在復雜度和檢測性能之間折中選擇。通過仿真驗證本文方案在性能和復雜度之間的折中優化以及在高階調制下的性能優勢。

4 結語

本文針對大規模MIMO系統，基于陰影域思想，并結合QP模型與BB搜索樹算法，考慮了高階調制的檢測性能，提出了一種基于陰影域的搜索樹檢測算法：首先，根據ML最優算法模型構造QP算法模型;其次，結合陰影域思想，提取落入陰影域的不可靠符號;然后，將不可靠符號進行搜索樹檢測;同時，提出三種修剪策略，可以在復雜度和性能之間折中選擇，增加了靈活性。仿真結果驗證了本文算法不僅提升了性能增益，且可在復雜度和性能之間折中優化，且適用于高階調制。

參考文獻 （References）

[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 largescale 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 Kbest 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. Randomrestart reactive tabu search algorithm for detection in largeMIMO systems[J]. IEEE Communications Letters， 2010， 14（12）： 1107-1109.

[7] ??? LI P， MURCH R D. Multiple output selectionLAS 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 largescale 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 interiorpoint 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 branchandbound algorithm for unit commitment[J]. IEEE Transactions on Power Apparatus & Systems， 1983， PER3（2）： 34-35.