基于半正定松弛的MIMO盲檢測

李 浩 彭 華

?

基于半正定松弛的MIMO盲檢測

李 浩*彭 華

(解放軍信息工程大學信息系統工程學院 鄭州 450001)

為解決MIMO系統盲檢測問題，該文以最大似然序列檢測為估計準則，通過推導建立了一種新的半正定松弛(SemiDefinite Relaxation, SDR)求解模型，使得到的松弛解的秩等于發送天線數。為了解決了松弛解秩大于1時估計原始發送序列的難題，該文提出一種特征向量近似法和隨機法相結合的方法。通過限定目標函數的取值上限，使算法能夠根據目標函數值自適應判斷求解發送序列個數，從而減少每次求解的約束個數和SDR的求解次數，分析表明算法的計算復雜度與發送天線數成線性關系。最后，通過仿真表明所提算法能夠在與秩1的算法性能保持相當的條件下減少計算時間，并驗證了算法計算復雜度與發送天線數成線性關系。

多輸入多輸出；盲檢測；半正定松弛

1 引言

近年來，半正定松弛由于其低計算復雜的特點被廣泛應用于信號處理和通信領域[1,2]，對于一些十分困難的優化問題，半正定松弛是一種十分有效的次最優算法，通常在計算復雜度和性能上具有較好的折中。BPSK信號的MIMO檢測可以看作布爾二次規劃(Boolean Quadratic Program, BQP)問題，對其做適當的替換和松弛就能夠變為半正定規劃(semidefinite program)，從而將NP-Hard問題轉變為凸優化問題，該問題可以用內點法(interior point method)進行求解，而計算復雜度僅為多項式級，這種對原問題進行松弛、通過對半正定規劃求解的方法被稱為半正定松弛。

半正定松弛(SemiDefinite Relaxation, SDR)應用于MIMO非盲檢測的文獻出現在本世紀初[3]。緊接著，文獻[4,5]對利用SDR實現MIMO軟檢測進行了討論。之后，文獻[6,7]分別利用SDR實現了對M-PSK信號和高階QAM信號的MIMO檢測，文獻[8]對高階信號檢測的各種方法的性能與復雜度進行了分析與比較。與此同時，許多學者與對基于SDR的MIMO檢測算法做了性能分析，其中文獻[9,10]對SDR檢測與最大似然(Maximum Likelihood, ML)檢測的等價準則進行了討論，給出了SDR算法與ML的等價條件。另外一些研究人員[11,12]則對算法在不同信噪比等條件下的檢測性能進行了討論，證明了許多重要的結論與定理，并對誤碼性能的理論限做了分析，進一步完善了基于SDR的MIMO檢測算法的理論體系。

針對MIMO盲檢測問題，文獻[13]利用OSTBC的正交性實現了基于SDR的OSTBC盲最大似然檢測，但對于BLAST (Bell Labs Layered Space Time)方案則無法應用。文獻[14]通過加入信源相關性的約束條件用SDR實現了已知符號集的盲源分離，該算法可以應用于MIMO信號的盲檢測，但算法建立的SDR模型的秩僅為1，對每一個信源都要進行一次求解，因此計算復雜度較高，為敘述方便我們稱這種算法為秩1的盲檢測算法。

本文致力于MIMO系統的盲檢測問題，安排如下：第1節為前言；第2節介紹MIMO盲檢測的信號模型和估計準則；第3節將MIMO盲檢測問題轉換為二次約束的二次規劃(Quadratically Constrained Quadratic Program, QCQP)問題，并做適當的松弛建立一種新的MIMO盲檢測SDR求解模型；第4節提出一種主特征向量和隨機法相結合的方法估計原始問題的解，解決了松弛解秩大于1條件下估計原始問題解的難題；第5節通過分析SDR模型目標函數的誤差上限來設定檢測序列個數門限，加入信源相關性的約束條件，設計了松弛解的個數能夠自適應變化的SDR MIMO盲檢測算法，并對算法的計算復雜度了進行分析；第6節給出算法的仿真結果與對比；最后對全文算法進行總結。

2 信號模型

考慮MIMO系統接收端的接收信號模型，假設信號精確同步(包括載波同步和定時同步等)，系統中有個接收天線和個發送天線，每個天線發送個符號，且不失一般性假設各信源獨立，定義：

3 半正定松弛(SDR)求解模型

將式(6)代入式(5)可得發送信號的最大似然序列估計式等價為

該問題是一個凸優化問題，文獻[1,8]給出了用內點法、CVX工具箱等求解算法和工具，由此可以得到松弛解。上面論述雖然以BPSK信號為例進行說明，但是QPSK, 16QAM等復信號和多模的PAM信號也能夠通過變量代換、實虛分解等變換得到QCQP模型并通過松弛得到式(10)，只是模型維數有所增加，具體方法可以參考文獻[16]等。

4 原始問題求解

4.1 特征向量近似

4.2隨機法

另外，信源之間雖然獨立，但是因為數據長度有限，任意兩個發送序列通常具有相關性，所以需要通過相關系數的大小判定兩個序列是否“獨立”。序列的期望為0，方差為1，根據相關系數的公式可得

5 算法分析與總結

由此可以得出以下兩個結論：(1)最小的目標函數值對應的發送序列的估計值最準確誤碼率最低；(2)如果其他發送序列估計值與最小的目標函數值對應的發送序列估計值具有相近的誤碼率，則兩者的目標函數值相差不大。因此，可以通過其他目標函數值與最小的目標函數值的差值來判斷該發送序列估計值的誤碼率能否與最優的估值序列相近。令

步驟2 加入表示發送序列“獨立”的約束條件，令待求解序列的相關性與已求解序列的相關性小于相關閾值，即，其中，由此得到新的SDR模型：

下面對算法的計算復雜度進行分析，每次SDR求解算法內點法在給定計算精度的條件下計算復雜度為，一般為常數，因而記為，其中表示約束條件個數，式(24)中對角線元素的約束互不相關，因而可看作1個約束條件。上述算法中特征值分解的計算復雜度是，秩1的算法和上述算法所應用的Cholesky分解的計算復雜度是，兩種算法中每次SDR求解的隨機的計算復雜度均是，由此可以看出兩種算法的計算消耗主要集中在內點法求解。秩1算法做了次SDR求解，每次求解的約束條件個數都增加1個，可得次SDR求解的計算復雜度為

6 仿真實驗

為了對比本文提出的算法(Rank-adaptive)和秩1的算法(Rank-1)的性能給出以下仿真實驗，每組實驗進行500次蒙特卡洛仿真，實驗條件如下：(1)發送序列：發送序列為相互獨立的隨機序列，若無特殊說明則信號長度為100(即)，發送信號是調制方式為BPSK的信號；(2)發送接收天線數：若無特殊說明接收天線數與發送天線數相等，一般選取；(3)隨機信道：試驗采用隨機信道，則每次蒙特卡洛仿真中MIMO信道矩陣的系數隨機產生，各元素(若信道為復信道則實部和虛部獨立)均服從均值為0、方差為1的高斯分布；(4)信噪比：定義信噪比為

第1組實驗對比本文提出的算法和秩1的算法在不同信噪比條件下的性能，實驗進行了500次蒙特卡洛仿真，每次仿真的發送序列和信道系數均按上述方法產生。圖1給出了該組實驗的仿真結果，圖中縱軸表示誤比特率，橫軸表示信噪比，4條曲線分別表示秩1的算法、本文提出的算法在,和時的性能曲線。由結果可以看出在相同的發送接收環境下，本文提出的算法在時與秩1算法的誤比特性能幾乎相同，算法性能隨的增長而下降。由第5節的分析可知，兩種算法的計算消耗主要集中在內點法求解過程，因此本文以SDR求解的次數和求解時間作為對比標準。表1給出了4種算法在不同信噪比下SDR平均求解次數，從仿真結果可以看出本文算法在時的SDR求解次數減少50% 以上，且隨的增長而下降，當時則只需1次SDR求解。表2 給出了4種算法在不同信噪比下CVX工具箱求解SDR的平均時間，從求解時間來看計算復雜度降低了56%以上，比SDR求解次數降低的比例更高。這是因為SDR求解的計算復雜度隨約束條件個數成多項式級增加，而求解次數與約束條件有線性關系，所以求解時間會隨求解次數成多項式級增加，表1和表2中的數據恰好反映了這一關系。

表1 4 種算法在不同信噪比下SDR平均求解次數

表2 4種算法在不同信噪比下平均求解時間(s)

由于發送天線數的增加會增加松弛解秩的維度，因此第2組實驗將對比不同發送天線數對算法的影響。圖2給出了該組實驗的仿真結果，圖中縱軸表示誤比特率，橫軸表示信噪比，其中兩條實線分別表示發送天線數為6時秩1算法和本文算法()的性能曲線，虛線則表示發送天線數為8時秩1算法和本文算法()的性能曲線，可以看出兩種算法的性能曲線幾乎相同，表明發送天線數對本文算法與秩1算法的影響相同。由于平均求解時間更能反映計算復雜度，因此給出了不同發送天線數在不同信噪比下平均求解時間，如表3所示?？梢钥闯霰疚乃惴ǖ钠骄蠼鈺r間在時為5.16 s，在時僅為6.95 s，與秩1算法相比，分別減少66%和72%。為更加直觀地給出算法復雜度的對比，在綜合表2，表3的數據的基礎上對,時進行算法仿真，記錄兩種算法的平均求解時間，圖3給出了仿真結果。圖中橫軸表示發送天線數，縱軸表示平均求解時間，可以看出秩1算法的平均求解時間隨發送天線數的增加近似成多項式級上升，而本文算法的平均求解時間與發送天線數則成線性關系，仿真結果驗證了第5節中對算法計算復雜度的分析。

表3算法在不同發送天線數下平均求解時間(s)

算法Es/N0(dB) 05101520平均 Nt=6秩1算法15.1415.1515.2115.3515.4415.26 Nt=6本文算法2.633.806.646.955.815.16 Nt=8秩1算法24.6824.6624.7224.8324.8824.75 Nt=8本文算法3.644.618.0910.158.356.96

第3組實驗對比一定信噪比條件下不同發送序列長度的對算法的影響，圖4給出了信噪比為15 dB時該組實驗的仿真結果，圖中縱軸表示誤比特率，橫軸表示發送序列的長度，兩條曲線分別表示秩1的算法、本文提出的算法在時的性能曲線。仿真結果可以看出算法性能隨數據量的增加而提升，該實驗結果驗證了信源“獨立”對于算法的影響，數據長度越長信源的獨立性越明顯，盲檢測的效果越好。

第4組實驗對比不同接收天線數對算法的影響，圖5給出了該組實驗的仿真結果，圖中縱軸表示誤比特率，橫軸表示信噪比，其中兩條實線分別表示接收天線數為5時秩1算法和本文算法的性能曲線，虛線則表示接收天線數為3時秩1算法和本文算法的性能曲線。仿真結果表明當接收天線數增多時，由于接收到更多的信號副本使得兩種算法的性能均得到提升，且兩種算法的性能在超定的情況下幾乎相同，但在欠定的情況下兩種算法均有較大的性能損失，并且本文算法的性能損失更為明顯，這是因為本文算法松弛解的秩與發送天線數相同，當接收天線數小于發送天線數時由于接收維度的缺失，會使松弛解的秩等于接收天線數，進而導致原始問題解的估計誤差增大、誤碼率增加。

7 總結

本文致力于MIMO系統的盲檢測問題，以最大似然序列檢測為準則，建立了一種新的SDR求解模型，使得松弛解的秩等于發送天線數，并根據松弛解的秩大于1的特點還提出了一種特征向量和隨機法相結合的估計原始問題解的方法，通過限定目標函數的取值上限，使算法自適應對多路發送序列進行檢測，且算法的計算法復雜度與發送天線數成線性關系。最后，通過仿真驗證了本文算法能夠在與秩1的算法性能保持相當的條件下降低計算復雜度，計算復雜度的改善隨發送天線數的增加而更加明顯。

圖1 不同信噪比下算法性能對比 圖2 不同發送天線數算法性能對比 圖3 不同發送天線數下平均求解時間

圖4 不同數據量算法性能對比 圖5 不同接收天線數算法性能對比

[1] LUO Zhiquan, MA Wingkin, ANTHONY S M,. Semidefinite relaxation of quadratic optimization problems[J]., 2010, 27(3): 20-34.

[2] 羅濤, 劉宏偉, 嚴俊坤, 等. 基于半正定秩松弛方法的穩健波束形成[J]. 電子與信息學報, 2014, 36(7): 1545-1551. doi: 10.3724/SP.J.1146.2013.01046.

LUO Tao, LIU Hongwei, YAN Junkun,. Robust beamforming via semidefinite rank relaxation[J].&, 2014, 36(7): 1545-1551. doi: 10.3724/SP.J.1146.2013.01046.

[3] MA Wingkin, DAVIDSON T N, WONG K M,. Quasi- maximum-likelihood multiuser detection using semi-definite relaxation with application to synchronous CDMA[J]., 2002, 50(4): 912-922.

[4] STEINGIMSSON B, LUO Zhiquan, and WONG K. Soft quasi-maximum-likelihood detection for multiple-antenna wireless channels[J]., 2003, 51(11): 2710-2719.

[5] NEKUII M, KISIALIOU M, DAVIDSON T N,. Efficient soft-output demodulation of MIMO QPSK via semidefinite relaxation[J]., 2011, 5(8):1426-1437.

[6] MA Wingkin, CHING Pakchung, and DING Zhi. Semidefinite relaxation based multiuser detection for M-ary PSK multiuser systems[J]., 2004, 52(10): 2862-2872.

[7] WIESEL A, ELDAR Y C, and SHAMAI S.Semidefinite relaxation for detection of 16-QAM signaling in MIMO channels[J]., 2005, 12(9):653-656.

[8] SHAO Z Y, CHEUNG S W, and YUK T I. Comparison of semidefinite relaxation detectors for high-order modulation MIMO systems[J]., 2014, 6(3): 1-8.

[9] JALDEN J, MARTIN C, and OTTERSTEN B. Semidefinite programming for detection in linear systems-optimality conditions and space-time decoding[C]. Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, Hong Kong, 2003: 9-12.

[10] KIM Minjoon, PARK Jangyong, KIM Kilhwan,. Exact ML criterion based on semidefinite relaxation for MIMO systems[J]., 2014, 21(3): 343-346.

[11] JALDEN J and OTTERSTEN B.The diversity order of the semidefinite relaxation detector[J]., 2008, 54(4): 1406-1422.

[12] XU Zi, HONG Mingyi, and LUO Zhiquan. Probabilistic analysis of semidefinite relaxation for binary quadratic minimization[J]., 2014, 24(3): 1265-1293.

[13] 韓飛. 正交空時分組碼的最大似然盲檢測算法研究[D]. [碩士論文], 西南交通大學, 2014.

[14] LI Qingyu, BAI Erwei, and DING Zhi. Blind source separation of signals with known alphabets using epsi- approximation algorithms[J]., 2003, 51(1): 1-10.

[15] MANUEL A and MIGUEZ V J. Maximum-likelihood sequence detection in time- and frequency-selective MIMO channels with unknown order[J]., 2009, 58(1): 499-504.

[16] 薛江. 基于多通道接收的短波信道盲均衡算法研究[D]. [碩士論文], 解放軍信息工程大學, 2012.

Blind Detection of MIMO via Semidefinite Relaxation

LI Hao PENG Hua

(,,450001,)

In order to solve the problem of blind detection of MIMO system, this paper takes maximum-likelihood sequence detection as the criterion and derives the formulas to get a model based on SemidDefinite Relaxation. The rank of SDRsolution equals to the number of the transmit antennas. For the rank of SDRsolution is greater than 1, a new method is proposed to approximate the solution of the original problem, which combines the eigenvector approximation method and randomization method. By setting the upper limit of objective function, the proposed method could judge the number of detection sequence adaptively and reduce constrains number and the number of solving SDR. The analysis shows that the computation complexity of proposed method has linear relationship with the number of transmit antennas. At last, simulation results indicate that compared with Rank-1 algorithm, the proposed detector could provide the same bit error performance with decrease of computation cost, and validate the linear relationship between the computation complexity and the number of transmit antennas.

Multiple-Input Multiple-Output (MIMO); Blind detection; SemiDefinite Relaxation (SDR)

TN92

A

1009-5896(2016)11-2893-07

10.11999/JEIT151444

2015-12-22；改回日期：2016-07-08；

2016-09-30

李浩 leo.lihao@163.com

國家自然科學基金(61401511)

The National Natural Science Foundation of China (61401511)

李 浩： 男，1986年生，博士生，研究方向為通信信號處理、盲信號處理.

彭 華： 男，1973年生，教授，研究方向為通信信號處理、軟件無線電.