王茜竹 ，李 楠

1.“新一代信息網(wǎng)絡(luò)與終端”重慶市協(xié)同創(chuàng)新中心，重慶400065

2.重慶郵電大學 電子信息與網(wǎng)絡(luò)工程研究院，重慶 400065

1 引言

隨著無人機、VR智能體感設(shè)備、無人駕駛汽車等新型多樣化的智能終端設(shè)備迅速普及開發(fā)，對無線數(shù)據(jù)業(yè)務(wù)需求也提出了新的挑戰(zhàn)。面對車聯(lián)網(wǎng)、虛擬現(xiàn)實、人工智能新技術(shù)的蓬勃發(fā)展，原有的無線接入網(wǎng)絡(luò)暴露出頻譜資源短缺的嚴重問題。為了更好地解決上述問題，大規(guī)模MIMO技術(shù)橫空出世[1]。憑借著基站端配置上百根天線的優(yōu)勢，空間自由度大幅提升，大規(guī)模MIMO技術(shù)不僅可以提高頻譜效率與信道容量，而且可以顯著改善能耗效率[2]。但是大規(guī)模MIMO系統(tǒng)中上行鏈路信號檢測算法復雜度隨著天線數(shù)量增加呈指數(shù)增加，原有的信號檢測算法無法應(yīng)用在實際工程中。于是近些年業(yè)內(nèi)相應(yīng)提出了許多適用于大規(guī)模MIMO系統(tǒng)的復雜度較低的信號檢測算法[3]，在這其中基于啟發(fā)式思想的主動禁忌搜索（Reactive Tabu Search，RTS）算法憑借著近似于原有算法性能和復雜度較低的優(yōu)勢脫穎而出。由于RTS算法具備避免陷入局部極值，得到全局最優(yōu)解性能，所以該算法性能優(yōu)于其他基于局部近似搜索的檢測算法[4]。

在Chockalingam的專著[5]中指出RTS算法性能主要取決于鄰域函數(shù)定義和初始值算法的選擇。初始值算法中最大似然檢測（Maximum-Likelihood，ML）算法性能最優(yōu)，可是因為其復雜度過高無法在工程中實現(xiàn)，目前通常使用的是迫零（ZF）和最小均方誤差（MMSE）算法。由于天線數(shù)量上升到上百根，而ZF和MMSE算法不可避免地涉及到矩陣的求逆，所以傳統(tǒng)基于MMSE求得初始值的RTS算法還是存在初始值計算復雜度過高的問題?；谶@一問題，本文提出基于迭代算法求解初始值的改進RTS算法，并給出仿真結(jié)果和分析。

2 大規(guī)模MIMO系統(tǒng)模型

本文考慮的是單個小區(qū)上行鏈路的大規(guī)模多用戶MIMO系統(tǒng)，在基站一側(cè)配置M根天線，同時為天線總數(shù)為K的單天線或多天線用戶服務(wù)。基于大規(guī)模MIMO系統(tǒng)上行鏈路特性，通常M?K，發(fā)射天線個數(shù)為NK和接收天線個數(shù)為NM。假設(shè)信道模型為平坦衰落信道下的基帶時域離散信號模型，則該系統(tǒng)復數(shù)模型為：

這里發(fā)射信號向量xc∈?NK，xc=[x1x2…xNK]T。接收信號向量信道增益矩陣Hc∈?NK×NM，假設(shè) Hc中的所有元素服從獨立同分布的復高斯分布，均值為0，方差為1。噪聲向量nc∈?NM，假設(shè)nc中所有元素服從獨立同分布的復高斯分布，均值為0，方差為 表示發(fā)射信號平均能量，γ為接收天線平均信噪比。為了便于分析，將式（1）化為實數(shù)型系統(tǒng)模型：

其中yr為一個2M×1維實數(shù)接收信號矩陣，xr為一個2K×1維發(fā)送信號矩陣，nr為一個2M×1維噪聲信號向量，Hr為一個2M×2K維信道向量矩陣。上行鏈路信號檢測任務(wù)就是從接收到的信號向量yr中估計出發(fā)送的信號向量xr，本文應(yīng)用場景假設(shè)基站對接收端信道狀態(tài)信息完全已知，也就是Hr基站接收端已知。

根據(jù)式（2）可以得到性能最優(yōu)的最大似然檢測（ML）算法公式為：

這里ML算法代價函數(shù)為：

3 RTS算法

3.1 算法介紹

主動禁忌搜索算法是由Battiti和Tecchiolli將主動搜索（Reactive Search，RS）算法引入到禁忌搜索（Tabu Search）算法中得到的。RTS算法是一種基于機器學習和人工智能思想的檢測算法，具備反饋機制，同時也是一種啟發(fā)式算法。相比于同樣基于本地鄰域搜索的似然上升搜索（Likelihood Ascent Search，LAS）算法，它們共同點都是從一個初始解向量開始，接著不斷嘗試從當前解向量的鄰域內(nèi)尋找更優(yōu)的解。不同點是LAS算法缺陷是容易陷入局部死循環(huán)，而RTS算法通過利用禁忌表這一反饋機制避免陷入死循環(huán)[6]。面對上百根天線數(shù)量的大規(guī)模MIMO系統(tǒng)，RTS算法憑借著高檢測性能和復雜度低的優(yōu)勢成為業(yè)內(nèi)研究的熱點[7]。

3.2 算法實現(xiàn)過程

適用于大規(guī)模用于MIMO信號檢測的RTS算法從初始解向量開始，這里初始解向量計算通常還是基于MIMO中傳統(tǒng)線性信號檢測算法。然后根據(jù)鄰域定義的準則定義初始解向量周圍的鄰域，在鄰域中基于上式（8）ML代價函數(shù)選出代價函數(shù)最小的最優(yōu)解，即使最佳鄰近向量在ML代價函數(shù)方面表現(xiàn)不如當前解向量，也將當前初始解向量移動到鄰域向量中的最佳向量，這一舉措實現(xiàn)了算法跳出局部最優(yōu)解，得到全局最優(yōu)解的效果。這樣的過程經(jīng)過一定數(shù)量的迭代之后，該算法被終止并得到全局最優(yōu)解向量。

上述過程中解向量的鄰域的定義是基于一定數(shù)量的迭代實現(xiàn)的，RTS算法通過標記過去幾次迭代中已經(jīng)移動過的解向量生成“禁忌表”（禁止再次移動到這些解向量），以確保在搜索解向量空間中避免陷入局部死循環(huán)。這些迭代的數(shù)值被定義為“禁忌周期”，其數(shù)值根據(jù)在搜索路徑中觀察到的解向量的重復次數(shù)動態(tài)地改變。而禁忌周期系數(shù)是為了提高算法收斂速度，提高算法性能。

4 基于RTS的改進算法

4.1 改進算法原理以及整體流程圖

傳統(tǒng)的RTS算法是從初始解向量開始的，初始解向量算法的選擇很大程度決定了RTS算法的最終性能和算法實現(xiàn)復雜度。通過對RTS算法實現(xiàn)過程的分析，發(fā)現(xiàn)RTS算法初始解向量求解一般基于線性信號檢測算法，這是因為在天線數(shù)為數(shù)十根的條件下，線性信號檢測算法在復雜度方面不是很高的前提下可以獲得比較優(yōu)良的性能。然而當天線數(shù)量達到上百根的條件下，線性信號檢測算法不可避免地進行矩陣求逆計算，信道矩陣規(guī)模大幅增加，矩陣求逆帶來的算法復雜度增加問題不容小視[8]。所以本文引入基于迭代算法的信號檢測算法替換傳統(tǒng)的線性信號檢測算法，應(yīng)用在RTS算法中作為初始解向量求解算法。具體的基于迭代算法的改進RTS算法整體流程圖如圖1所示。

圖1 改進的RTS流程圖

4.2 線性信號檢測算法求解初始解向量

初始解向量直接影響RTS算法最終的性能和復雜度，所以算法的選擇至關(guān)重要。目前RTS算法初始解向量主要還是應(yīng)用線性信號檢測算法，比如迫零（ZF）算法[9]和最小均方誤差（MMSE）算法。這里MMSE算法因為考慮到噪聲因素所以性能高于ZF算法，假設(shè)發(fā)射天線數(shù)量為K，復雜度為Ο(K3)。根據(jù)文獻[10]MMSE算法估計的發(fā)射信號向量x表示為：

這里定義：

所以

選取MMSE作為RTS算法初始解向量算法復雜度為Ο(K3)，隨著大規(guī)模MIMO系統(tǒng)中小區(qū)用戶數(shù)量增加，應(yīng)用在實際工程中還是存在復雜度過高的問題，所以考慮基于迭代算法求解初始解向量，從而避免大規(guī)模矩陣的求逆過程。

4.3 基于迭代算法求解初始解向量

在大規(guī)模MIMO系統(tǒng)中，隨著發(fā)射和接收兩端天線數(shù)量增加，天線間信道趨向正交，MMSE算法的矩陣W為對稱正定性矩陣[11]?；谶@一特點，考慮使用迭代算法去求MMSE算法近似發(fā)射向量x，從而降低初始值向量求解過程算法復雜度。

目前提出的迭代算法有：Neumann算法（Neumann series approximation）[12]、Richardson 算法[13]、SOR（Successive Over Relaxation）算法[14]和 GS（Gauss-Seidel）算法[15]。這些算法通過應(yīng)用在大規(guī)模MIMO系統(tǒng)下RTS算法仿真得出，隨著迭代次數(shù)增加Neumann算法復雜度過高，Richardson算法性能居中，而SOR和GS算法可以得到近似于MMSE的初始解向量結(jié)果。雖然SOR算法收斂速度最快，但是相比GS算法復雜度高，所以本文選擇GS迭代算法作為RTS算法初始解向量求解算法。并在GS算法基礎(chǔ)上提出塊分星座圖的BC-GS（Block-Constellations GS）優(yōu)化算法，從而進一步降低算法復雜度。

GS算法應(yīng)用在求解N維線性方程：

其中A是N×N維Hermitian正定矩陣，x是N×1解向量，b是N×1向量。不同于傳統(tǒng)方法直接計算A-1b得到x，GS方法可以通過迭代方法求解方程Ax=b，降低復雜度。當小區(qū)基站天線數(shù)為M，小區(qū)用戶天線總數(shù)為K，MMSE轉(zhuǎn)換矩陣W是2K×2K維Hermitian正定矩陣，公式（13）和公式（14）也是一樣類型，綜上所述，可以分解W為：

這里D代表矩陣W的對角元素組成的矩陣，L代表矩陣W的嚴格下三角元素組成的矩陣，U代表矩陣W的嚴格上三角元素組成的矩陣。根據(jù)GS算法公式（14）可以得到：

通常當i=0，作為GS迭代算法的初始解向量x(0)=為2K×1的零向量矩陣[16]。提出基于塊分星座圖的思想重新定義初始值，從而進一步提高GS迭代算法性能，并且BC-GS算法可以更好地應(yīng)用在高階調(diào)制中。

首先定義xi和為發(fā)射向量x和接收向量 y的第i個元素，而表示矩陣W的第i行和第 j列元素。

根據(jù)文獻[17]得到，大規(guī)模MIMO隨著天線增多，出現(xiàn)信道硬化的趨勢，即矩陣W為對角元素占優(yōu)矩陣（對角元素相對于非對角元素數(shù)值大很多），當然W-1也是對角占優(yōu)矩陣。又因為W是對稱正定矩陣，對角元素都是正數(shù)。得出：

根據(jù)上式可以判斷接收向量的正負，從而判斷發(fā)射向量xi的正負，基于這一點再將映射的星座圖劃分為A塊，然后界定每塊區(qū)域的邊界值，通過算法確定xi屬于哪個小區(qū)域，然后選取該區(qū)域的中心點最為初始解向量?；趬K分星座圖定義初始值實現(xiàn)過程如下：

（1）確定塊分星座圖區(qū)域個數(shù)A，根據(jù)調(diào)制確定映射星座圖Q值和

（2）定義塊分小區(qū)域邊界值為：

（3）根據(jù)進行判定所在區(qū)域：大于0，并選取該區(qū)域的中心點作為；如果當小于0，xi?選取該區(qū)域的中心點作為

（4）結(jié)束。

下面通過具體實例對上述過程說明基于塊分星座圖思想定義初始值過程。假設(shè)應(yīng)用64QAM調(diào)制方式，所以xi可能是{ }-7,-5,-3,-1,+1,+3,+5,+7 ，即Q=8。定義A=4，也就是塊分為4個小區(qū)域，所以根據(jù)步驟（2）得到區(qū)域邊界值a=4,4。然后根據(jù)的值確定所在區(qū)域，比如假設(shè)，并且范圍就在[0，4]之間，選取=2；如果-Wa<0，范圍就在[4，8]之間，選取=6；當<0則反之。通過圖2可以清楚地發(fā)現(xiàn)通過對GS算法引入塊分星座圖思想，初始值向量到發(fā)射向量距離d1明顯比零向量到發(fā)射向量距離d2小，從而提高精確度，減少迭代次數(shù)，提高算法性能。

圖2 BC-GS算法與傳統(tǒng)GS算法初始解對比

所以根據(jù)公式（15）、（16），可以得到基于塊分星座圖思想定義的BC-GS算法流程如下：

（1）W矩陣分解為W=D+L+U；

（2）基于塊分星座圖思想求解GS算法初始解向量：

（3）計算（i表示迭代次數(shù)）：

（4）i=i+1；

（5）重復進行步驟（1）～（4），得到向量序列 x(i)；

（6）結(jié)束。

5 改進的RTS算法復雜度分析

由于本文的改進RTS算法主要是對初始解向量算法進行優(yōu)化，即提出BC-GS算法來替換MMSE算法作為初始解向量算法，從而減低RTS算法整體復雜度，提高算法性能。于是改進的RTS算法和傳統(tǒng)的RTS復雜度的對比其實也就是BC-GS和MMSE算法復雜度的對比。

BC-GS算法復雜度主要分為兩部分：（1）GS迭代算法本身的復雜度；（2）基于塊分星座圖思想改進的初始解向量算法帶來的復雜度。

首先計算GS算法本身的復雜度。根據(jù)公式（16），可以將迭代方程變化為：

上式中左式2K×2K維矩陣(D +L)和2K維矩陣x(i+1)相乘次數(shù)為2K2+K，等式右邊2K×2K維矩陣U和2K×1維矩陣x(i)相乘次數(shù)為2K2-K。所以進行一次GS算法需要4K2次相乘。

其次分析基于BC思想初始值求解復雜度。這部分算法復雜度主要集中在這一步驟。W為一個2K×2K維矩陣，而a為一個2K×1維只有第i個元素為常數(shù)，其他元素為0的矩陣。所以相乘次數(shù)為2K。

綜上所述進行一次BC-GS算法所需4K2+2K次計算。而MMSE算法復雜度為K3。具體兩種算法對比如表1所示。

表1 計算復雜度對比

引入塊分星座圖思想求解初始值的BC-GS算法不僅使GS算法更適用于64QAM高階調(diào)制方式，而且使復雜度相比傳統(tǒng)GS算法也有所降低。例如圖3中，經(jīng)過兩次迭代GS算法復雜度為18K2+4K，而BC-GS算法復雜度為8K2+2K。從圖3中，可以發(fā)現(xiàn)隨著迭代次數(shù)增加，GS和BC-GS算法復雜度都有所增加，而在三種算法中MMSE算法的復雜度是最高的，GS算法復雜度居中，而改進的BC-GS算法復雜度最低。例如在小區(qū)用戶數(shù)為35（這里默認小區(qū)用戶都為單天線用戶，小區(qū)用戶數(shù)等同于小區(qū)用戶天線數(shù)）的條件下，MMSE復雜度為4.25×104，而迭代次數(shù)為4的GS和BC-GS算法復雜度為2.5×104和1.4×104。具體MMSE、GS、BC-GS三種算法復雜度對比如圖3所示。

圖3 算法復雜度對比

6 仿真結(jié)果分析

通過仿真，從誤碼率性能方面進行算法對比，從而驗證改進的RTS算法在復雜度有所降低的前提下，性能在迭代次數(shù)一定的條件下幾乎沒有受到損失。

首先根據(jù)大規(guī)模MIMO系統(tǒng)配置初始仿真參數(shù)，具體參數(shù)配置如表2。

表2 初始仿真參數(shù)配置

這里針對表2小區(qū)用戶天線數(shù)加以說明，根據(jù)大規(guī)模MIMO系統(tǒng)在基站端布置大規(guī)模天線陣列特性，帶來的系統(tǒng)性能提升也主要來自于基站端，所以本文為了便于分析改進算法性能將初始仿真參數(shù)小區(qū)用戶天線數(shù)固定為16根。

然后根據(jù)表2的相應(yīng)參數(shù)，分別對MMSE、GS和BC-GS三種初始解向量算法進行BER對比。在圖4中可以看出MMSE的BER性能最好，隨著迭代次數(shù)增加，GS和BC-GS算法的BER性能逐漸提高。而憑借著塊分星座圖思想求解初始值的BC-GS算法在同樣迭代次數(shù)條件下，BER性能明顯好于GS算法。在迭代次數(shù)為4時，BC-GS算法的BER性能已經(jīng)十分接近MMSE算法。例如當SNR為12 dB時，迭代4次的BC-GS算法的BER僅比MMSE算法高2×10－6，但是算法復雜度確實明顯降低很多。

圖4 三種初始值算法BER對比

其次根據(jù)表2配置小區(qū)用戶天線總數(shù)為16，基站天線數(shù)目分別為32、64、128，禁忌周期為2，禁忌周期系數(shù)為0.1，設(shè)定最大迭代次數(shù)為100，最小迭代次數(shù)為25的系統(tǒng)參數(shù)下對改進的RTS算法（基于BC-GS作為初始解向量）和原來的RTS算法（基于MMSE最為初始解向量）進行BER對比。這里BC-GS初始解向量算法迭代次數(shù)為4，因為從圖4發(fā)現(xiàn)迭代次數(shù)為4時，BER性能最接近MMSE算法。從圖5中，可以看出隨著基站天線數(shù)量的增加，BER性能得到改善，比如在SNR為40 dB時，64×16的RTS算法BER比32×16降低1.9×10－4，128×16的BER比64×16降低8×10－5。而且可以看出雖然改進的RTS算法復雜度降低很多，可是BER性能卻沒有受到很大影響，不論基站天線數(shù)的改變，始終BER性能都是很接近原來的RTS算法。例如在SNR為40 dB時32×16的改進RTS的BER只比原來的RTS算法高2×10－5，64×16的改進RTS的BER比原來的RTS算法高3×10－5，而天線數(shù)128×16的改進RTS算法的BER只比原來的RTS算法高7×10－5。

圖5 改進RTS和原來RTS算法BER對比

接著分析改進算法的收斂性，通過不同迭代次數(shù)下算法性能的變化來驗證這一性質(zhì)。在表2配置的基礎(chǔ)上，又增加信噪比為30 dB這一限定條件和小區(qū)用戶天線數(shù)為32這一情況。從圖6中，可以看出隨著迭代次數(shù)的增加，不論天線數(shù)為32×16、64×16還是128×16性能都呈現(xiàn)出收斂性，特別是迭代次數(shù)超過70以后，這一趨勢更加明顯。例如，當天線數(shù)為128×16，迭代次數(shù)為70時，改進算法BER為1.1×10－4，迭代次數(shù)增加到100時，BER為0.7×10－4，只比迭代70時低4×10－5。所以隨著迭代次數(shù)的遞增，改進算法性能表現(xiàn)出穩(wěn)定和優(yōu)良的趨勢。這里選取單輸入單輸出系統(tǒng)的高斯白噪聲信道性能作為參考標準。

圖6 不同迭代次數(shù)下改進算法BER對比

最后針對小區(qū)用戶天線數(shù)對算法性能的影響做簡單描述。從圖6中，通過對比天線數(shù)128×16和128×32的BER，可以看出隨著小區(qū)用戶天線數(shù)從16增加到32性能有所提升。例如在迭代次數(shù)為70時，128×32的BER比128×16低3×10－5。所以小區(qū)用戶天線數(shù)量的增加也可帶來性能的改善，不過犧牲的是復雜度的相應(yīng)提升。

7 結(jié)束語

本文首先對GS迭代算法進行改進，提出塊分星座圖思想求解初始值替換原有初始零向量的BC-GS算法，從而算法復雜度進一步降低，并且也更適用于高階調(diào)制方式下。然后基于BC-GS迭代求解算法替代原來的MMSE算法，作為RTS算法的初始解向量算法，從而在迭代次數(shù)一定的條件下，降低算法的復雜度，而改進的RTS算法的性能也沒有受到很大損失，更加利于工程實現(xiàn)。

[1]Marzetta T L.Noncooperative cellular wireless with unlimited numbers of base station antennas[J].IEEE Transactions on Wireless Communications，2010，9（11）：3590-3600.

[2]Ngo H，Larsson E，Marzetta T.Energy and spectral efficiency of very large multiuser MIMO systems[J].IEEE Transactions on Communications，2012，61（4）：1436-1449.

[3]Wu M，Yin B，Wang G，et al.Large-scale MIMO detection for 3GPP LTE：Algorithms and FPGA implementations[J].IEEE Journal of Selected Topics in Signal Processing，2014，8（5）：916-929.

[4]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.

[5]Chockalingam A，Rajan B S.Large MIMO systems[M].[S.l.]：Cambridge University Press，2014.

[6]張中山，王興.大規(guī)模MIMO關(guān)鍵技術(shù)研究及應(yīng)用[J].中國科學：信息科學，2015，45（9）：1095-1110.

[7]Yang Shaoshi，Hanzo L.Fifty years of MIMO detection：The road to large-scale MIMOs[J].IEEE Communications Surverys&Tutorals，2015，17（4）：1941-1988.

[8]Rusek F，Persson D，Lau B K，et al.Scaling up MIMO：Opportunities and challenges with very large arrays[J].Signal Processing Magazine IEEE，2013，30（1）：40-60.

[9]Gao X，Dai L，Ma Y，et al.Low-complexity near-optimal signal detection for uplink large-scale MIMO systems[J].Electronics Letters，2014，50（18）：1326-1328.

[10]Yin B，Wu M，Studer C，et al.Implementation trade-offs for linear detection in large-scale MIMO systems[C]//IEEE International Conference on Acoustics，Speech and Signal Processing（ICASSP’13），2013：2679-2683.

[11]Larsson E，Edfors O.Massive MIMO for next generation wireless systems[J].IEEE Communications Magazine，2013，52（2）：186-195.

[12]Wu M，Yin B，Vosoughi A，et al.Approximate matrix inversion for high-throughput data detection in the largescale MIMO uplink[C]//IEEE International Symposium on Circuits and Systems，2013：2155-2158.

[13]Gao X，Dai L，Yuen C.Low-complexity MMSE signal detection based on Richardson method for large scale MIMO Systems[C]//Vehicular Technology Conference（VTC Fall），2014：1-5.

[14]秦闖，鄭紫微，婁達平.基于近似信息傳遞算法的大規(guī)模MIMO信號檢測[J].電信科學，2016，32（9）：16-20.

[15]Qian M，Wang Y，Zhou Y.A super base station based centralized network architecture for 5G mobile communication systems[J].DigitalCommunicationsand Networks，2015，54（2）：152-159.

[16]Bjork A.Numerical methods in matrix computations[M]//Texts in Applied Mathematics.[S.l.]：Springer International Publishing，2015.

[17]Tulino A，Verdu S.Random matrix theory and wireless communications[J].Foundations and Trends in Communications and Information Theory，2004，1（1）：1-182.