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

朱瑞鑫，金小萍，馮會(huì)真

(中國(guó)計(jì)量學(xué)院信息工程學(xué)院，浙江杭州310018)

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

朱瑞鑫，金小萍，馮會(huì)真

(中國(guó)計(jì)量學(xué)院信息工程學(xué)院，浙江杭州310018)

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

MIMO;概率排序;存儲(chǔ)約束屬性搜索

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

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

1 系統(tǒng)模型

文中采用MIMO多天線系統(tǒng)，接收與發(fā)送天線數(shù)目分別為NR=1和NT=2，系統(tǒng)框圖如圖1所示，其中譯碼器部分就是本文的研究重點(diǎn)。

圖1 MIMO系統(tǒng)框圖

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

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

進(jìn)行差分編碼之后，系統(tǒng)通過空時(shí)天線矩陣，采用不同的多徑信道模型進(jìn)行發(fā)送。設(shè)某時(shí)刻t的接收信號(hào)為

假設(shè)多符號(hào)差分檢測(cè)的觀察窗口長(zhǎng)度為N，即在多符號(hào)差分檢測(cè)系統(tǒng)中，接收機(jī)連續(xù)接收N個(gè)符號(hào)來檢測(cè)。傳統(tǒng)度量值判決式為

2 PSMCTS算法

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

本文利用文獻(xiàn)［10］中的思想，針對(duì)式(4)進(jìn)行優(yōu)化，將其轉(zhuǎn)化為利用數(shù)學(xué)統(tǒng)計(jì)概率密度來進(jìn)行度量的判決式為

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

1)根據(jù)系統(tǒng)要求設(shè)置發(fā)送、接收天線數(shù)目NR和NT、調(diào)制星座點(diǎn)數(shù)L等參數(shù)，初始化可用存儲(chǔ)空間M，M≥(N-1)(L-1)+1。初始化多符號(hào)窗口長(zhǎng)度N，將分組長(zhǎng)度為N的接收信號(hào)輸入到PSMCTS檢測(cè)器中。

2)設(shè)樹的層數(shù)變量K=N，表示從樹根(對(duì)應(yīng)的度量值為0)開始，如果K≠2，擴(kuò)展根節(jié)點(diǎn)到L個(gè)子節(jié)點(diǎn)，然后把這L個(gè)子節(jié)點(diǎn)存入列表，按照式(5)通過轉(zhuǎn)化的判決度量式來進(jìn)行MCTS算法思想的搜索過程。

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

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

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

PSMCTS和MCTS算法的節(jié)點(diǎn)搜索演示分別如圖2、圖3所示。

圖2 PSMCTS樹形節(jié)點(diǎn)分析圖

圖3 MCTS樹形節(jié)點(diǎn)分析圖

圖中，表示未訪問的節(jié)點(diǎn) ，表示訪問節(jié)點(diǎn) ，表示最佳節(jié)點(diǎn)。圖2為PSMCTS樹形節(jié)點(diǎn)分析圖，其中數(shù)值為概率度量值，括號(hào)內(nèi)為傳統(tǒng)度量值。當(dāng)?shù)\(yùn)算至N3節(jié)點(diǎn)進(jìn)行拓展后，此時(shí)存儲(chǔ)的點(diǎn)為N2，N4，N5，N6。傳統(tǒng)度量值的排序?yàn)镹2，N6，N4，N5，會(huì)選擇N2為最佳節(jié)點(diǎn)進(jìn)行返溯，但是按照本文算法度量值的排序?yàn)镹6，N4，N5，N2，會(huì)直接選擇N6為最佳節(jié)點(diǎn)進(jìn)行下一輪的迭代并進(jìn)行拓展，大大減少了搜索的節(jié)點(diǎn)訪問數(shù)。圖3為MCTS樹形節(jié)點(diǎn)分析圖，圖中數(shù)值為傳統(tǒng)度量值，通過對(duì)比可以直觀地表現(xiàn)出PSMCTS算法訪問節(jié)點(diǎn)數(shù)少的優(yōu)勢(shì)。另外，為了更加直觀地體現(xiàn)出搜索過程的優(yōu)勢(shì)，表1和表2分別列出了PSMCTS與MCTS算法的具體搜索存儲(chǔ)狀態(tài)，其中黑體表示選擇拓展的訪問節(jié)點(diǎn)。

表1 PSMCTS搜索狀態(tài)表

表2 MCTS搜索狀態(tài)表

從表中可以看出，要達(dá)到準(zhǔn)確輸出，PSMCTS算法在搜索樹層時(shí)，每層的存儲(chǔ)空間中最多需保留3個(gè)分支節(jié)點(diǎn)，而MCTS最少需保留4個(gè)［9］，這使得PSMCTS算法在降低存儲(chǔ)空間需求量方面存在著進(jìn)一步優(yōu)化的空間，并且這一優(yōu)勢(shì)會(huì)隨著星座點(diǎn)數(shù)的增多逐漸擴(kuò)大。表中也體現(xiàn)出了PSMCTS算法在搜索步驟簡(jiǎn)化上的優(yōu)勢(shì)，由于可以更加準(zhǔn)確地表示出節(jié)點(diǎn)的度量值并將存儲(chǔ)空間進(jìn)行縮小，使得存儲(chǔ)的節(jié)點(diǎn)數(shù)降低并加速了樹搜索過程，使得該算法更加快速和有效。

3 復(fù)雜度與性能分析

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

3.1 復(fù)雜度分析

在MCTS算法中，為了保證該算法能夠?qū)崿F(xiàn)，M必須有個(gè)最小的取值界限。根據(jù)文獻(xiàn)［9］中對(duì)M值最小值的取值證明，可相應(yīng)地將多符號(hào)差分系統(tǒng)中的M值最小界限取為(N-1)(L-1)+1，L為星座點(diǎn)數(shù)。在本文研究的系統(tǒng)中，分析以分組長(zhǎng)度N=4，QPSK調(diào)制L=4，存儲(chǔ)空間M≥(N-1)(L-1)+1并取最小值。對(duì)于ML算法，訪問點(diǎn)數(shù)為L(zhǎng)0+…+LN-1=(LN-1)/(L-1)，MCTS算法以及本文中提出的PCMCTS算法的訪問點(diǎn)數(shù)通過仿真訪問次數(shù)來計(jì)算得出，仿真結(jié)果如圖4所示。

圖4對(duì)文中涉及的各類算法在分組長(zhǎng)度為4的情況下進(jìn)行了對(duì)比，橫縱坐標(biāo)分別為信噪比和運(yùn)算點(diǎn)數(shù)。

圖4 復(fù)雜度分析對(duì)比圖

結(jié)果表明，在分組長(zhǎng)度和預(yù)設(shè)存儲(chǔ)空間相同的情況下，針對(duì)同一種調(diào)制方式，PSMCTS在整體上均表現(xiàn)出對(duì)MCTS的優(yōu)勢(shì)，尤其是在低信噪比時(shí)優(yōu)勢(shì)更為明顯，有利于系統(tǒng)平均復(fù)雜度的降低。

3.2 性能分析

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

圖5 性能對(duì)比分析圖

4 小結(jié)

本文基于MCTS算法，鑒于硬件存儲(chǔ)空間約束以及在小存儲(chǔ)空間的情況下，計(jì)算復(fù)雜度相對(duì)較大的問題，提出了改進(jìn)型PSMCTS算法，該算法能夠很好地利用DSPS算法與MCTS算法的優(yōu)勢(shì)，提供更好的性能表現(xiàn)。總體來說，PSMCTS算法既有較低的存儲(chǔ)空間需求，便于硬件實(shí)現(xiàn)，又能在低信噪比區(qū)域降低計(jì)算復(fù)雜度，有利于降低系統(tǒng)的平均復(fù)雜度，同時(shí)能夠逼近ML的檢測(cè)性能，因此，它是一種較優(yōu)的檢測(cè)算法。

［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，F(xiàn)ISCHER 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，F(xiàn)UKUDA 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］應(yīng)櫻果，金小萍，金寧.多符號(hào)差分檢測(cè)的低復(fù)雜度球形譯碼設(shè)計(jì)［J］.計(jì)算機(jī)工程與應(yīng)用，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，F(xiàn)ENG 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

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

國(guó)家自然科學(xué)基金項(xiàng)目(61071119);浙江省自然科學(xué)基金項(xiàng)目(Y1091155;LQ12F01010);東南大學(xué)國(guó)家移動(dòng)通信研究實(shí)驗(yàn)室開放性研究基金項(xiàng)目(2011D18)

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

金小萍(1978—)，碩士生導(dǎo)師，主研移動(dòng)通信網(wǎng)絡(luò)技術(shù)、編碼與檢測(cè)等;

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