基于概率排序的存儲約束樹形搜索算法的研究

朱瑞鑫，金小萍，馮會真

(中國計量學院信息工程學院，浙江杭州310018)

基于概率排序的存儲約束樹形搜索算法的研究

朱瑞鑫，金小萍，馮會真

(中國計量學院信息工程學院，浙江杭州310018)

鑒于目前MIMO系統中大多數多符號差分檢測算法對于大容量存儲空間的需求和高計算復雜度的缺點，提出了一種概率排序的存儲約束樹搜索(Probabilistic Sorting Memory Constrained Tree Search，PSMCTS)算法，利用概率排序的性能優勢與MCTS的存儲優勢來解決此問題。經過理論分析與仿真驗證，該算法能夠繼承MCTS算法的優勢，能夠動態地適應預設的存儲空間，適合硬件實現，而排序算法提高了檢測性能，在固定的存儲需求下，性能表現更加逼近ML算法，同時能夠解決MCTS算法在小存儲容量條件下低信噪比區域計算復雜度仍比較高的問題。因此，PSMCTS可以作為一種有效的方案應用在通信系統中。

MIMO;概率排序;存儲約束屬性搜索

目前，大多的多符號差分檢測算法［1］是基于樹形檢測，而ML檢測［2］是一種BER性能最優的檢測算法，但窮搜索使得復雜度與分組長度和天線數等均呈指數關系，從而導致它根本無法在實際中運用。因而一些低復雜度的檢測算法相繼被提出來解決這個關鍵難題［3-8］。大體有3種搜索策略:深度優先、寬度優先和度量值優先。球形譯碼就是典型的以深度優先搜索策略為主的檢測算法［3-4］，這種算法由于不斷地回溯導致在不同的信道環境下具有不同的吞吐量，且并行和流水線操作困難。寬度優先搜索策略［5］，如K-Best算法，具有高吞吐量和穩定的復雜度，并且適于流水硬件實現，但是由于K值的約束會帶來一定的性能損失。而以度量值優先搜索策略為主的Stack算法［6］，又叫Dijkstra's算法［7-8］，它總是擴展列表中度量值最小的節點，這種策略是眾多搜索策略中訪問節點最少的。

這些算法的硬件需求通常較大，計算復雜度較高，而硬件的固定存儲空間會限制了其性能。MCTS算法［9］能夠在任意給定的存儲空間約束條件下，逼近最大似然檢測的性能，同時能夠降低計算復雜度。但該算法在較小存儲空間的限制下，復雜度依然很大。DSPS(Dijkstra’s Search with Probabilistic Sorting)算法［10-11］是由Ronald Y.Chang等人提出的一種新的樹搜索算法，利用數學統計概率來進行對節點度量值的比較，相比窮搜索的傳統Dijkstra’s算法，大大降低了所需訪問的節點數，并且有效地提高了性能表現，在節省存儲空間和降低復雜度方面有著很高的研究價值。本文綜合以上問題，提出一種新的存儲約束搜索算法——PSMCTS，利用DSPS算法判決準確度高以及搜索訪問點數少的優勢，優化MCTS算法的存儲循環策略，降低了對存儲空間的需求，同時提升了系統性能。

1 系統模型

文中采用MIMO多天線系統，接收與發送天線數目分別為NR=1和NT=2，系統框圖如圖1所示，其中譯碼器部分就是本文的研究重點。

圖1 MIMO系統框圖

St滿足St=I2。為了進行差分編碼，需設定一個參考矩陣C0，該矩陣不攜帶任何數據信息。令C0=，數據進行空時編碼之后進入差分編碼器，其編碼方式為

式中:Ct表示差分編碼矩陣。

進行差分編碼之后，系統通過空時天線矩陣，采用不同的多徑信道模型進行發送。設某時刻t的接收信號為

假設多符號差分檢測的觀察窗口長度為N，即在多符號差分檢測系統中，接收機連續接收N個符號來檢測。傳統度量值判決式為

2 PSMCTS算法

在MCTS算法中，采用式(4)的度量值判決，被訪問節點的選擇總是受限于存儲空間和度量值，它總是先訪問不超過存儲空間需求的度量值最小的節點，使得MCTS算法的搜索策略取決于預設的存儲空間大小。存儲需求對于硬件實現來說是一個很重要的因素，需求越小越容易實現。在小存儲空間條件下，MCTS趨向于深度優先搜索策略，即趨向于深度優先球形譯碼算法，仍然需要大量的回溯訪問，計算復雜度依然相對較大。

本文利用文獻［10］中的思想，針對式(4)進行優化，將其轉化為利用數學統計概率密度來進行度量的判決式為

利用Dijkstra’s算法特點，基于MCTS步驟［9］進行改進，得出PSMCTS的搜索步驟如下:

1)根據系統要求設置發送、接收天線數目NR和NT、調制星座點數L等參數，初始化可用存儲空間M，M≥(N-1)(L-1)+1。初始化多符號窗口長度N，將分組長度為N的接收信號輸入到PSMCTS檢測器中。

2)設樹的層數變量K=N，表示從樹根(對應的度量值為0)開始，如果K≠2，擴展根節點到L個子節點，然后把這L個子節點存入列表，按照式(5)通過轉化的判決度量式來進行MCTS算法思想的搜索過程。

(2)由上層的最佳節點進行拓展，得到L個拓展的子節點，并存入存儲空間中。在低存儲空間的情況下，可預存分支節點數，直接選擇拓展子節點的最佳分支，進行下一層的搜索;如果K=1，直接輸出最小值。如果存儲空間足夠，可保留多層的分支節點度量值，將最佳子節點的拓展分支加入到空間，在存儲空間集合中進行堆棧算法，重復以上步驟進行回溯運算，重復此步驟，直到尋找出本層的最佳子節點，以此為根節點進行拓展至下一層的搜索;如果K=1，直接輸出最小值。

(3)重復以上搜索步驟，直至搜索到最底層，并輸出最佳路徑值。

3)如果K=2，那么找到一個該訪問節點下的最佳葉子節點，并用其替換列表中的訪問節點，然后根據列表中最佳的葉子節點進行更新列表，輸出最佳路徑。

PSMCTS和MCTS算法的節點搜索演示分別如圖2、圖3所示。

圖2 PSMCTS樹形節點分析圖

圖3 MCTS樹形節點分析圖

圖中，表示未訪問的節點 ，表示訪問節點 ，表示最佳節點。圖2為PSMCTS樹形節點分析圖，其中數值為概率度量值，括號內為傳統度量值。當迭代運算至N3節點進行拓展后，此時存儲的點為N2，N4，N5，N6。傳統度量值的排序為N2，N6，N4，N5，會選擇N2為最佳節點進行返溯，但是按照本文算法度量值的排序為N6，N4，N5，N2，會直接選擇N6為最佳節點進行下一輪的迭代并進行拓展，大大減少了搜索的節點訪問數。圖3為MCTS樹形節點分析圖，圖中數值為傳統度量值，通過對比可以直觀地表現出PSMCTS算法訪問節點數少的優勢。另外，為了更加直觀地體現出搜索過程的優勢，表1和表2分別列出了PSMCTS與MCTS算法的具體搜索存儲狀態，其中黑體表示選擇拓展的訪問節點。

表1 PSMCTS搜索狀態表

表2 MCTS搜索狀態表

從表中可以看出，要達到準確輸出，PSMCTS算法在搜索樹層時，每層的存儲空間中最多需保留3個分支節點，而MCTS最少需保留4個［9］，這使得PSMCTS算法在降低存儲空間需求量方面存在著進一步優化的空間，并且這一優勢會隨著星座點數的增多逐漸擴大。表中也體現出了PSMCTS算法在搜索步驟簡化上的優勢，由于可以更加準確地表示出節點的度量值并將存儲空間進行縮小，使得存儲的節點數降低并加速了樹搜索過程，使得該算法更加快速和有效。

3 復雜度與性能分析

為了驗證PSMCTS算法的有效性，本文進行了BER性能仿真分析和復雜度分析。信道與噪聲選擇均服從N(0，1)的高斯分布。

3.1 復雜度分析

在MCTS算法中，為了保證該算法能夠實現，M必須有個最小的取值界限。根據文獻［9］中對M值最小值的取值證明，可相應地將多符號差分系統中的M值最小界限取為(N-1)(L-1)+1，L為星座點數。在本文研究的系統中，分析以分組長度N=4，QPSK調制L=4，存儲空間M≥(N-1)(L-1)+1并取最小值。對于ML算法，訪問點數為L0+…+LN-1=(LN-1)/(L-1)，MCTS算法以及本文中提出的PCMCTS算法的訪問點數通過仿真訪問次數來計算得出，仿真結果如圖4所示。

圖4對文中涉及的各類算法在分組長度為4的情況下進行了對比，橫縱坐標分別為信噪比和運算點數。

圖4 復雜度分析對比圖

結果表明，在分組長度和預設存儲空間相同的情況下，針對同一種調制方式，PSMCTS在整體上均表現出對MCTS的優勢，尤其是在低信噪比時優勢更為明顯，有利于系統平均復雜度的降低。

3.2 性能分析

對各種算法在測試環境下進行了性能仿真分析，仿真結果如圖5。從圖5可以看出，以性能最佳的ML最大似然算法為對比基礎，本文提出的PSMCTS算法，由于有效地利用了概率排序算法的性能優勢，在固定存儲空間相同的情況下，其性能相比較MCTS有了一定提升，更加逼近ML算法。

圖5 性能對比分析圖

4 小結

本文基于MCTS算法，鑒于硬件存儲空間約束以及在小存儲空間的情況下，計算復雜度相對較大的問題，提出了改進型PSMCTS算法，該算法能夠很好地利用DSPS算法與MCTS算法的優勢，提供更好的性能表現。總體來說，PSMCTS算法既有較低的存儲空間需求，便于硬件實現，又能在低信噪比區域降低計算復雜度，有利于降低系統的平均復雜度，同時能夠逼近ML的檢測性能，因此，它是一種較優的檢測算法。

［1］WEIR Y.Differential encoding by a look-up table for quadrature-amplitudemodulation［J］.IEEE Trans.Communications，2013，59(1): 84-94.

［2］KIMJS，MOON SH，LEE I.A new reduced complexity ML detection scheme for MIMO systems［J］.IEEE Trans.Communications，2010，58 (4):1302-1310.

［3］SCHENKN，FISCHER R F R.A stopping radius for the sphere decoder:complexity reduction in multiple-symbol differential detection［C］//Proc.International ITG Conference on Source and Channel Coding(SCC).Siegen:［s.n.］，2010:1-6.

［4］ TAKAHASHI T，FUKUDA T，SUN C K.An appropriate radius for reduced-complexity sphere decoding［C］//Proc.International Conference on Communications，Circuits and System.Chengdu:［s.n.］，2010:41-44.

［5］應櫻果，金小萍，金寧.多符號差分檢測的低復雜度球形譯碼設計［J］.計算機工程與應用，2012，48(4):135-138.

［6］ MAO Xinyu，REN Shubo.Adjustable reduced metric-first tree search［C］//Proc.InternationalConferenceonWirelessCommunications，Networking and Mobile Computing(WiCOM).Wuhan:［s.n.］，2011:1-4.

［7］KIM T，PARK I.High-throughput and area efficient MIMO symbol detection based on modified Dijkstra’s search［J］.IEEE Trans.Circuits and Systems I:Regular Paper，2010，57(7):1756-1766.

［8］JASIKA N，ALISPAHIC N，ELMA A，et al.Dijkstra’s shortest path algorithm serial and parallel execution performance analysis［C］// Proc.the 35th International Convention MIPRO.Opatija:IEEE Press，2012:1811-1815.

［9］DAIYongmei，YAN Zhiyuan.Memory constrained tree search detection and new ordering schemes［J］.IEEE Journal of Selected Topics in Signal Processing，2009，3(6):1026-1037.

［10］CHANG R Y，CHUNGW H.Efficient tree-search MIMO detection with probabilistic node ordering［C］//Proc.IEEE International Conference on Communications.Kyoto:IEEE Press，2011:1-5.

［11］CHANG R Y，CHUNGW H.Best-first tree search with probabilistic node ordering for MIMO detection:generalization and performancecomplexity tradeoff［J］.IEEE Trans.Wireless Communications，2012，11(2):780-789.

［12］CUIT，TELLAMBURA C.Bound-intersection detection formultiplesymbol differential unitary space– time modulation［J］.IEEE Trans.Communications，2005，53(12):2114-2123.

Research of M emory Constrained Tree Search Based on Probabilistic Sorting

ZHU Ruixin，JIN Xiaoping，FENG Huizhen
(Department of Information and Engineering，China Jiliang University，Hangzhou 310018，China)

Considering the current MIMO system shortcomings of large storage space requirements and high complexity inmultiple-symbol differential detection algorithm，a probabilistic sortingmemory constrained tree search algorithm(PSMCTS)using performance advantage of sorting algorithm and storage advantage of MCTS is proposed.Through theoretical analysis and simulation，PSMCTScan effectively inherit the MCTSalgorithm good advantage，dynamically adapt to the preset storage space，and suitable for hardware implementation.Using sorting algorithms improved the detection performance，and the performance is close to ML algorithm under fixed memory requirement.The algorithm also solves the high computational complexity problem of MCTSalgorithm in small storage capacity conditions under the low SNR region.Therefore，PSMCTS is a good scheme in communication systems.

MIMO;probabilistic sorting;MCTS

TN911.23

A

?? 京

2014-05-16

【本文獻信息】朱瑞鑫，金小萍，馮會真.基于概率排序的存儲約束樹形搜索算法的研究［J］.電視技術，2014，38(23).

國家自然科學基金項目(61071119);浙江省自然科學基金項目(Y1091155;LQ12F01010);東南大學國家移動通信研究實驗室開放性研究基金項目(2011D18)

朱瑞鑫(1990—)，碩士生，主研通信系統、檢測算法及軟件;

金小萍(1978—)，碩士生導師，主研移動通信網絡技術、編碼與檢測等;

馮會真(1973—)，講師，主研通信電路、射頻通信等。