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

李小文 范藝芳 侯寧寧

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

關(guān)鍵詞：多輸入多輸出;二次規(guī)劃;陰影域;分支界限;高階調(diào)制

中圖分類號：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.

英文關(guān)鍵詞Key words： MultipleInputMultipleOutput （MIMO）; Quadratic Programing （QP）; shadow domain; Branch and Bound （BB）; high order modulation

0 引言

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

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

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

4 結(jié)語

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

參考文獻 （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.