基于陰影域的搜索樹(shù)檢測(cè)算法

李小文 范藝芳 侯寧寧

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

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

中圖分類號(hào)：TN929.5

文獻(xiàn)標(biāo)志碼：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]，可實(shí)現(xiàn)更高的傳輸速率，提升系統(tǒng)容量。該系統(tǒng)在信道估計(jì)、天線相關(guān)性、硬件實(shí)現(xiàn)，以及低復(fù)雜度的信號(hào)檢測(cè)方面是非常具有研究意義的[2-3]。人們?cè)趥鹘y(tǒng)的MIMO系統(tǒng)中提出了許多線性檢測(cè)和接近最大似然檢測(cè)算法，例如，在文獻(xiàn)[4]提出的多階段球形譯碼檢測(cè)算法與文獻(xiàn)[5]提出的Kbest球形檢測(cè)算法，能夠達(dá)到近似最大似然（Maximum Likelihood， ML）檢測(cè)算法的性能，但其復(fù)雜度隨天線數(shù)目和調(diào)制階數(shù)的增加呈指數(shù)增長(zhǎng);另一方面，低復(fù)雜度的檢測(cè)算法，例如最小均方誤差（Minimum Mean Square Error， MMSE）算法，其性能隨天線數(shù)目的增加而惡化。

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn) （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.