基于分支定界和有效集的信號檢測算法

李貴勇，李思遠，于 敏

(重慶郵電大學 通信與信息工程學院，重慶 400065)

0 引 言

大規(guī)模多輸入多輸出(multi-input multi-output，MIMO)技術，可以在保持發(fā)射功率與頻譜資源的情況下，提升系統(tǒng)吞吐量與容量，是5G系統(tǒng)的關鍵技術之一[1-2]。其中信號檢測的性能關乎大規(guī)模 MIMO系統(tǒng)是否可靠，信號檢測復雜度關乎系統(tǒng)的是否易于實現，所以信號檢測成為大規(guī)模 MIMO系統(tǒng)中至關重要的一部分。

為了提高大規(guī)模MIMO系統(tǒng)的性能，學者們提出了多種信號檢測算法。如最大似然(maximum likelihood，ML)算法[3]、最小均方誤差 (minimum mean squared error，MMSE) 算法、文獻[4]提出的K-best球形檢測算法和文獻[5]提出的多階段球形譯碼(sphere decoding，SD)檢測算法。SD算法系統(tǒng)性能可以接近ML算法，但其復雜度會隨著調制階數和天數數量增長呈指數增加。而且從本質上來說，它屬于一種分支定界(branch and bound，BB)算法[6]，它在每個分支節(jié)點上，都考慮了最小二乘問題。在BB算法的每個節(jié)點上，必須解決二次規(guī)劃子問題。在非線性優(yōu)化理論中有很多算法可以解決二次規(guī)劃(quadratic programming，QP)問題，例如：梯度投影法和內點法。但梯度投影法復雜度高，搜索速度較慢；內點法算法中心路徑設置困難，往往很難達到預期效果。文獻[7]提出的主動禁忌搜索(reactive tabu search，RTS) 算法和文獻[8]提出的似然上升搜索 (likelihood ascend search，LAS)算法，對進行判斷得到較為良好的初始向量進行局部的相鄰域搜索，平衡了天線數量增加而帶來的復雜度增長和性能衰減的問題，但其系統(tǒng)性能還是會隨著調制階數的增長而快速惡化。文獻[9]提出的似然搜索樹檢測(likelihood based tree search，LBTS)算法相對于BB算法進行了節(jié)點的篩選，不對所有節(jié)點進行計算，從而降低了復雜度，但當調制階數增加時，性能會明顯惡化。

為了解決傳統(tǒng)算法不能很好地解決復雜度和系統(tǒng)性能上的均衡，本文就BB算法和QP算法進行了重點分析研究。首先，本文基于ML檢測構建出QP命題，并且對一階QP命題所得解向量進行二次判斷，將落入陰影區(qū)域的符號判斷為不可靠符號；然后，對一階QP命題解中的不可靠符號進行具有可變二分法的深度優(yōu)先分支定界算法檢測，從而形成第二次QP檢測；最后，為了降低BB算法復雜度，提出了一種針對上界的修剪策略，并且引入了近似因子，改善了算法性能，在復雜度和性能之間進行了更好的折中。并且，本文算法中涉及的QP命題的求解，均使用原始有效集算法[10]。

1 系統(tǒng)模型

(1)

(2)

(2)式中：Re為復值向量的實部；Im為復值向量的虛部。

(3)

在本文中，必須解決凸二次規(guī)劃的求解問題。有效集法(active set method，ASM)在求解約束條件較少的QP命題時，顯示出了相當好的性能，可以用于大規(guī)模MIMO系統(tǒng)。原始有效集方法從一個迭代開始逐步解決子問題，在該子問題中，QP問題的不等式約束和所有等式約束被強加為等式[11]。

這里通過忽略上標考慮一般的QP子問題

(4)

原始有效集算法步驟如下。

初始化：給出初始可行點x0，將空集W0設置為x0處的有效集

fork= 0,1,2,…,do

解式(4)，求出pk;

ifpk=0

stopx*=xk;

else

end if

else

xk+1←xk+αkpk;

if 存在阻塞約束

選擇阻塞約束或阻塞約束中的一個加入有效集Wk生成Wk+1。

else

Wk+1←Wk;

end if

end if

end for

2 基于QP優(yōu)化問題應用分支定界和有效集法的信號檢測算法

2.1 2QP算法和陰影區(qū)域介紹

(5)

(6)

2.2 基于陰影區(qū)域的BB搜索樹算法

傳統(tǒng)BB算法是基于二叉樹搜索的檢測算法。例如將(6)式作為根節(jié)點問題，傳統(tǒng)BB算法會選擇每層第一個非整數元素處[14]，分支為2個互斥的子搜索空間，且作為子節(jié)點約束，這樣分支后的下一層節(jié)點元素中至少有一個更接近最優(yōu)解。然后逐層進行分支，縮小范圍，最終就可以找到最優(yōu)解。若解向量所有數值均為整數，則為最優(yōu)解;否則，不是最優(yōu)解。而且對有較大誤差的符號進行分支可以較快地收斂，可以盡可能地減少分支次數，從而降低了算法復雜度。

(7)

圖1 分支定界搜索樹Fig.1 Branch and bound search tree

如果搜索二叉樹的所有節(jié)點，直至出現最優(yōu)解，則復雜度非常高。假設在搜索樹搜索到d層才出現最優(yōu)解，則整體需要解QP的次數為2(d+1)-1。所以本文首先采用了2種針對于分支定界過程中深度和寬度的修剪的方法。

1)深度修剪。人為規(guī)定搜索的層數，即使搜索到規(guī)定的層數沒有出現最優(yōu)解 ，也強制不再進行后續(xù)分支，并尋找目標函數值最接近最優(yōu)解的解向量。

2)寬度修剪。與傳統(tǒng)算法在每層節(jié)點的第一個非整元素處進行分支不同，本文首先對每層各個節(jié)點對應的目標函數值進行降序排序，保留前W個節(jié)點進行分支，其余節(jié)點刪除。因此，在算法分支的每個節(jié)點處都需要更新目標函數值的最大值。

其次，如果解節(jié)點優(yōu)化問題所得目標函數值超過設定的目標函數最大值，則說明該節(jié)點及其之后的各分支節(jié)點不可能生成最優(yōu)解，所以要在后續(xù)的節(jié)點列表中去除該節(jié)點。為了加快收斂速度，降低復雜度，本文根據此原理提出了一種分支定界過程中的針對上界的修剪原則。

根據MMSE得出的信號估計值來規(guī)定目標函數的最大值，然后使用該估計值來計算BB搜索樹的起始上界。

(8)

(8)式中：f(up)表示為代價函數的起始上界；xmmse為MMSE得到的信號估計值。該起始上界將在樹內被更新。因此，例如，每當f(m)>f(up)時，節(jié)點m就被修剪，f(m)為目標函數值。這種方法的優(yōu)點是①整個樹只需要一次計算；②在高信噪比的情況下，它可以作為緊密邊界，加快搜索過程。但是在符號較多且低信噪比時，它需要更多的計算量。

(9)

綜上所述，算法步驟可以總結為算法初始化：解式(3)得到集合γ與公式(6)。

步驟1初始化節(jié)點列表為空，由(8)式得出f(up);定義深度為L和寬度為W并輸入對應數值;將(6)式加載到節(jié)點列表上，開始搜索;初始化層數l=0。

步驟6令l=l+1，跳轉到步驟2。

步驟7終止算法。

2.3 復雜度分析

3 仿真分析

在仿真實驗中，信道環(huán)境設置為瑞利平坦衰落信道，設置接收天線和發(fā)送天線均為32根。規(guī)定BB(16,3)表示搜索樹搜索深度為16，每層保留節(jié)點數為3。為了比較本文算法的性能，我們在分析本文算法性能的同時也跟MMSE算法、QP算法、2QP算法、BB算法進行分析比較。

設置調制方式為16QAM，δ=0.25，φ=0.001。仿真結果如圖2所示。根據圖2可得，在低信噪比情況下傳統(tǒng)的BB算法的性能差于QP算法和2QP算法。在信噪比為25 dB左右時，傳統(tǒng)的BB算法的性能才優(yōu)于2QP算法。但是本文算法，在低信噪比時性能也優(yōu)于QP算法和2QP算法。在誤比特率(bit error rate，BER)為10-4時，本文算法比2QP算法有著約3 dB的增益；比傳統(tǒng)BB算法提升了約為2 dB。在BER=10-5時，本文算法仍保持較好的性能，與傳統(tǒng)BB算法相比有著約為2.5 dB的增益。

圖2 32×32 16QAM BER性能比較Fig.2 Performance comparison of 32×32 16QAM BER

與圖2相比，改變調制方式為64QAM，φ更改為0.000 1，其他條件保持不變，仿真結果如圖3所示。當BER=10-4時，本文算法與2QP算法相比，有著約5.5 dB的增益；與傳統(tǒng)BB算法相比，有著約1.8 dB的增益。

圖3 32×32 64QAM BER性能比較Fig.3 Performance comparison of 32×32 64QAM BER

最后提高調制階數，使用256QAM調制來驗證本文算法在高階調制的性能，其他條件保持不變，仿真結果如4所示。當BER=10-4時，本文算法比2QP算法有著約為6 dB的增益；當BER=10-5時，本文算法比BB算法有著約為3 dB的增益。從圖2—圖4中的性能比較上可以看出，本文算法在不同的QAM調制階數上，性能穩(wěn)定，均優(yōu)于傳統(tǒng)的QP算法、2QP算法和BB搜索樹算法。

圖4 32×32 256QAM BER性能比較Fig.4 Performance comparison of 32×32 256QAM BER

如果在本文算法中放寬修剪條件fm≥fup，在一階QP算法后的分支定界算法中會減少求解的節(jié)點數，從而導致精確度減少性能下降，但同時求解節(jié)點數的減少也會帶來復雜度的降低，這就給我們在性能和復雜度之間的折中提供了的新思路。在這本文引入一個近似因子e(e∈[0,1])。將修剪條件替換為fm≥(1-e)fup。顯然，當e=0時，與精確的本文算法相同。當e=1時，與根節(jié)點的初始解相同。圖5為調制方式為16QAM，δ=0.25，φ=0.001時的天線數目32×32 MIMO信道的性能。當BER=10-4時，精確的本文算法比近似因子e為0.3、0.6的本文算法分別有著約為0.5 dB、1.2 dB的增益。雖然引入了修剪因子后的算法性能降低了，但是從圖5中還是可以看出，性能相較于傳統(tǒng)BB、2QP算法依舊有著提升。

4 結 論

本文基于QP檢測器提出了一種適用于高階調制的大規(guī)模MIMO系統(tǒng)的低復雜度檢測算法。本文算法應用了有效集法和具有可變二分法的深度優(yōu)先分支定界算法，結合陰影區(qū)域，將不可靠符合進行搜索樹檢測；提出了一種修剪策略，同時引入了近似因子，改善了傳統(tǒng)QP檢測器的性能。結果表明，本文算法與BB算法相比復雜度較低，特別是在高信噪比和高QAM調制的情況下，并且本文算法在性能上均優(yōu)于傳統(tǒng)QP算法、2QP算法和BB搜索樹算法。

圖5 引入近似因子e后與其他算法性能的比較Fig.5 Performance comparison with other algorithms after introducing approximation factor e