基于增強蟻群優(yōu)化算法與排序的MIMO檢測算法

葉卓映

(廈門城市職業(yè)學院 電子與信息工程系，福建 廈門 361008)

?

基于增強蟻群優(yōu)化算法與排序的MIMO檢測算法

葉卓映

(廈門城市職業(yè)學院 電子與信息工程系，福建 廈門 361008)

摘要：基于最大似然比的多輸入多輸出(multiple input multiple output,MIMO)檢測算法的計算復雜度隨著天線陣的規(guī)模呈指數(shù)級增加，提出一種計算復雜度較優(yōu)的MIMO檢測算法。采用基于對數(shù)似然比的排序QR分解技術(shù)將信道矩陣分解為正交矩陣與上三角矩陣，相應(yīng)地修改信號的發(fā)射順序，降低錯誤判斷引起的錯誤傳播效應(yīng)；為傳統(tǒng)人工蟻群優(yōu)化算法的信息素更新策略引入負信息素概念，有效地控制系統(tǒng)的擁塞；根據(jù)優(yōu)化路徑的距離積累了信息素。該方法設(shè)計了基于負信息素的信息素更新策略，增加MIMO系統(tǒng)的擁塞控制能力，考慮信道的衰落本性，基于路徑的距離積累信息素。為了測試該算法的性能，進行了多組對比實驗，結(jié)果表明，誤碼率性能優(yōu)于其他智能優(yōu)化算法，且對于64×64等大規(guī)模天線陣，該算法的計算復雜度隨天線規(guī)模增長較小。

關(guān)鍵詞：蟻群優(yōu)化；多輸入輸出系統(tǒng)；檢測排序；計算復雜度；誤碼率

0引言

多輸入多輸出(multiple input multiple output,MIMO)系統(tǒng)采用2N×2N的天線陣發(fā)送與接收信號，MIMO具有較高的頻譜、能量利用率，應(yīng)用較為廣泛[1]。若天線陣的規(guī)模較大，信號檢測算法的復雜度呈指數(shù)級增加，因此，MIMO系統(tǒng)對信號檢測的計算復雜度要求極高[2]。

文獻[3]提出一種低復雜度最大似然(maximum likelihood,ML)信號檢測算法——雙向最大似然檢測算法，該算法通過建立可雙向最大似然檢測的候選發(fā)射向量集來縮小ML向量的搜索范圍，從而降低信號檢測的復雜度。文獻[4]提出了一種接近最優(yōu)檢測性能的低復雜度并行MIMO檢測算法，該算法基于信道分組檢測的思想，對通過受噪聲干擾嚴重的子信道信號采用遍歷所有空間映射點的方式進行檢測，對其余信號則采用新的基于格基約減的線性并行檢測算法進行檢測。文獻[5]提出了一種基于改進蟻群優(yōu)化算法與減格輔助技術(shù)獲得檢測性能與計算復雜度的權(quán)衡，獲得了較好的性能，稱為格規(guī)約-蟻群優(yōu)化(lattice reduction-ant colony optimization, LR-ACO)。文獻[6]提出了一種基于改進粒子群優(yōu)化的MIMO檢測優(yōu)化算法—修改的粒子群優(yōu)化(changed particle swarm optimization, CPSO)，該算法在保持較低誤碼率的前提下，具有較低的計算復雜度。

文獻[3]的算法針對2×2的天線陣，具有較好的效果，但是對于大規(guī)模天線陣效果較差。文獻[4-6]的信號檢測算法則可應(yīng)用于大規(guī)模MIMO系統(tǒng)，但其性能仍有改進的空間。

本文針對MIMO系統(tǒng)的檢測技術(shù)，為人工蟻群算法引入負信息素的更新策略，并采用基于對數(shù)似然比的排序QR分解技術(shù)對信號檢測流程進行排序，提出了一種低誤碼率的MIMO信號檢測算法。仿真試驗結(jié)果表明，本文算法信號檢測性能優(yōu)于其他的MIMO信號檢測算法。

本文算法與其他基于人工智能的優(yōu)化算法差異主要有以下3點：①針對MIMO系統(tǒng)的擁塞控制，設(shè)計了基于負信息素的信息素更新策略；②采用排序的檢測來降低錯誤傳播現(xiàn)象；③考慮信道的衰落性質(zhì)，基于路徑的距離積累信息素。

1系統(tǒng)模型

(1)

(1)式中:H表示Nr×Nt的信道矩陣；矩陣的元素{hj,i}設(shè)為均值為0、方差為1的復高斯分布，{hj,i}表示第i個發(fā)送天線與第j個接收天線之間信道的增益；n表示Nr×1大小的復高斯白噪聲向量，其每個元素設(shè)為均值為0、方差為σ2的高斯分布?？蓪⒔邮斩说膹蛿?shù)向量y轉(zhuǎn)換為實數(shù)形式

y=Hs+n

(2)

(3)

(3)式中，Α表示信號星座圖的實數(shù)分量，對于16-QAM信號，Α={-3,-1,1,3}。然后，可使用QR分解法將信道狀態(tài)信息矩陣H分解處理，從而將(2)式改寫為

y=QRs+n

(4)

QHy=QHQHs+QHn

(5)

(6)

(4)式中：Q表示2Nr×2Nt的正交矩陣；R表示2Nr×2Nt的上三角矩陣[8]。

上述模型對接收端的信道估算沒有考慮誤差，然而，對信道系數(shù)的估算存在不可忽略的誤差，其誤差模型可表示為[9]

(7)

圖1　離散MIMO系統(tǒng)模型Fig.1　Discrete MIMO system model

2基于改進蟻群優(yōu)化的MIMO檢測算法

2.1MIMO檢測問題的模型

本文將MIMO檢測問題建模為路徑搜索問題，以便于使用蟻群優(yōu)化算法求解。此外，本文借鑒文獻[10]的旅行商問題(travellingsalesmnproblem,TSP)模型建立求解模型，可將MIMO的發(fā)送天線視為TSP問題中的城市，將第i個天線所有可能發(fā)出的信號看作到達第i個城市的可行路徑。圖2為借鑒TSP問題的MIMO檢測的模型，表示了二進制相移鍵控(binaryphaseshiftkeying,BSPK)調(diào)制的4×4MIMO系統(tǒng)，問題可簡化為搜索一次性遍歷所有城市的最便宜解，即搜索最小化成本函數(shù)f(s)的向量s，成本函數(shù)可定義為

(8)

圖2　BPSK調(diào)制的MIMO檢測模型(Nt=Nr=4)Fig.2　BPSK modulated MIMO detection model(Nt=Nr=4)

2.2蟻群優(yōu)化與本文方法

本文基于文獻[7]的ACO算法進行增強，ACO使用一定數(shù)量的人工螞蟻(Nants)搜索蟻窩N與食物源F之間的最短路徑，如圖3所示。其中，線條虛實線分別表示信息素濃度的高低。螞蟻采用協(xié)同機制與環(huán)境交互，螞蟻在N與F間移動時，在路徑上灑下信息素，信息素隨時間衰減，螞蟻始終選擇信息素最濃的路徑，即從N開始、到達F的最短路徑，其返回路徑也選擇該最短路徑，導致同一條最短路徑上積累的信息素增加較快。ACO是一種迭代搜索算法，在每輪迭代中，螞蟻在其選擇的路徑上灑下信息素，每只螞蟻檢查路徑中已有的信息素，根據(jù)之前螞蟻選擇最優(yōu)路徑。算法1為基本的蟻群算法流程。

圖3　螞蟻選擇信息素最濃的路徑Fig.3　Ants select the path with most pheromone

算法1蟻群優(yōu)化算法。

初始化系統(tǒng)參數(shù)

WHILE未達到結(jié)束條件DO

建立蟻群解

局部搜索

更新信息素

ENDWHILE

在本文基于蟻群優(yōu)化的MIMO信號檢測中，使用人工蟻群搜索問題的解，設(shè)為Nants。假設(shè)共有M個到達目標城市i的路徑(16-QAM的調(diào)制中，M=4)，將每條路徑表示為sik(k=1,2,…,M;i=1,2,…,2Nt)。一個螞蟻在每個路徑sik上的移動表示了螞蟻將符號sk選為第i個發(fā)送天線估算的信號。每輪迭代中，同時僅有一個螞蟻移動，基于路徑上的信息素濃度隨機地搜索估算的發(fā)送向量。

每輪迭代選擇最優(yōu)向量的方法為

(9)

對(9)式進行擴展，可得

(10)

將路徑sik到第i個城市的距離設(shè)為dik，即dik表示第k個路徑至第i個城市的距離。

(11)

(12)

因為ηik與dik成反比，ηik隨dik增加而降低，因此，積累的信息素將降低；而ηik隨dik降低而增加，因此，累積的信息素將升高。

基于路徑中的信息素濃度計算路徑選擇的概率，因此，路徑選擇概率pik的矩陣定義為

(13)

(13)式中，τik表示路徑sik(螞蟻的目標城市為i)的信息素等級(表示第i個天線發(fā)送的信號)。參數(shù)α是一個正的常量，表示了信息素等級的權(quán)重。當螞蟻經(jīng)過某條路徑時，將信息素置于該路徑中，基于當前的信息素等級更新路徑的總信息素值。本文算法設(shè)計了一種新的信息素更新策略，本策略使用了負信息素。本信息素更新方法為

(14)

(14)式中，ρ∈(0,1]為一個常量，該常量用于減少對應(yīng)路徑的信息素，即控制路徑中負信息素的量，以此實現(xiàn)擁塞控制。信息素基于參數(shù)ω積累，ω值不能設(shè)置過高，否則會導致早熟收斂且縮小搜索空間；ω值也不可設(shè)置過小，否則導致收斂速度過慢，因此，本文將ω設(shè)置較為適中。計算方法為

(15)

(15)式中，Δτik表示了路徑sik上累積的信息素(第i個天線的第k個信號)。

因為本算法按順序檢測信號，所以，如果初始化階段出現(xiàn)判斷錯誤將導致剩余天線發(fā)送信號的檢測錯誤，即錯誤傳播現(xiàn)象。為了防止錯誤傳播，本算法按順序進行天線檢測，本文使用文獻[11]的基于對數(shù)似然比(log likelihood ratio,LLR) 的排序QR分解技術(shù)(sorted QR decomposition, SQRD)，將本文蟻群算法的信道矩陣H進行QR分解。算法2為本文算法，首先對輸入?yún)?shù)進行初始化，執(zhí)行LLR-SQRD算法將H分解為正交矩陣Q與上三角矩陣R，并且相應(yīng)地修改信號的發(fā)射順序，從而降低錯誤判斷引起的錯誤傳播效應(yīng)。

本文算法與其他的人工蟻群優(yōu)化算法存在3點主要差異：①針對MIMO系統(tǒng)的擁塞控制，設(shè)計了基于負信息素的信息素更新策略；②采用排序的檢測來降低錯誤傳播現(xiàn)象；③考慮信道的衰落性質(zhì)，基于路徑的距離積累信息素，如(15)式所示。

算法2本文蟻群優(yōu)化的MIMO檢測算法。

輸入：y,H,Nt,Nant,α,ρ,ω

輸出：最優(yōu)解向量x(sol)

3x(int)：初始化解向量

4 WHILEj≤NantDO

5FORi≤2NtDO

6 FORk≤MDO

10END FOR

11FORk≤MDO

12 計算Δτik

13τik=τik-ρτik+ωΔτik//更新信息素

14ENDFOR

15 ENDFOR

18x(sol)=x(j)// 最優(yōu)解向量

19x(int)=x(j)

21 ELSE

22x(sol)=x(int)

23 ENDIF

24ENDWHILE

3仿真實驗與結(jié)果分析

對本文算法進行仿真實驗，測試了算法的誤碼率性能、算法的計算復雜度變化情況。實驗中，MIMO系統(tǒng)均采用4-QAM，天線陣分別設(shè)為6×6，8×8，16×16，32×32。假設(shè)本文算法中H的元符合均值為0、方差為1的高斯分布?；贛ATLAB進行仿真，每組實驗共計數(shù)2 000個錯誤比特來獲得平均誤碼率。

3.1誤碼率性能的比較

首先，將本文算法與LR-ACO，CPSO，基本ACO算法的誤碼率進行比較，結(jié)果如圖4、圖5所示，其天線陣為6×6。從圖4可看出，本文算法優(yōu)于其他3種算法，在10-3的誤碼率處，本算法的信噪比比LR-ACO高出5dB左右，且明顯優(yōu)于其他2種算法，從圖5中可看出，本算法也具有明顯優(yōu)勢。本文的排序檢測、負信息素方案有效地控制了系統(tǒng)擁塞以及錯誤傳播效應(yīng)，從而獲得了較低的誤碼率性能。

圖4　4-QAM與6×6天線陣下的誤碼率比較Fig.4　Bit error rate for 4-QAM and 6×6 antenna matrix

圖5　4-QAM與8×8天線陣下的誤碼率比較Fig.5　Bit error rate for 4-QAM and 8×8 antenna matrix

然后，測試了蟻群大小與信道估算誤差(e)對算法性能的影響，結(jié)果分別如圖6和圖7所示?？煽闯觯伻捍笮≡酱?，算法的優(yōu)化性能越好，誤碼率越低。從圖7中可看出，算法的誤碼率性能與螞蟻數(shù)量Nants的關(guān)系，對于SNR=14dB,Nt=Nr=8，16，32,3種情況，結(jié)果可看出，0≤Nants≤250下的誤碼率變化比Nants≥300劇烈，可基于目標誤碼率來設(shè)置本算法的蟻群大小。同時亦可看出，天線數(shù)量越多，收斂速度越快。

3.2計算復雜度性能分析

圖8為本算法的計算復雜度與天線數(shù)量的關(guān)系,圖8中,比較了8×8,32×32,64×64,3種天線陣下排序與未排序的計算次數(shù)比較,結(jié)果可看出,當Nants較小時,排序算法對本算法的計算復雜度有少量的影響,當Nants較大時,則幾乎無影響。此外，天線越多，計算復雜度越高。

圖6　4-QAM下8×8,16×16,32×32的MIMO系統(tǒng)(蟻群大小為100,500)Fig.6　Bit error rate of 8×8,16×16,32×32 MIMO system for 4-QAM(ant colony size is 100 and 500)

圖7　Nt=Nr=8,16,32,SNR=14 dB,4-QAM的MIMO系統(tǒng)收斂性分析Fig.7　Converge analysis for MIMO system for Nt=Nr=8,16,32,SNR=14 dB,4-QAM

圖8　4-QAM,SNR=14 dB下計算復雜度與蟻群大小的關(guān)系Fig.8　Relationship between computational complexity and ant colony size for MIMO system with 4-QAM,SNR=14 dB

4結(jié)論

本文針對MIMO系統(tǒng)的檢測技術(shù)，為人工蟻群算法引入負信息素的更新策略，并采用基于對數(shù)似然比的排序QR分解技術(shù)對信號檢測流程進行排序，提出了一種低誤碼率的MIMO信號檢測算法。本文設(shè)計的信息素更新策略充分考慮了MIMO系統(tǒng)的擁塞控制，是網(wǎng)絡(luò)保持較低的擁塞，從而進一步降低系統(tǒng)的誤碼率。最終，本算法獲得了較好的誤碼率性能，且對于大規(guī)模的天線陣，本算法的計算復雜度增長較慢，具有一定的優(yōu)勢。

未來，將針對人工蟻群算法的收斂速度做進一步研究，以期在保持較高誤碼率性能的同時，加速收斂，從而進一步降低算法的復雜度。

參考文獻：

[1]陳發(fā)堂, 侯彥莊. 基于MIMO-OFDM系統(tǒng)的一種低復雜度球型譯碼檢測算法[J]. 計算機應(yīng)用研究, 2011, 28(9):3436-3438.

CHEN Fatang,HOU Yanzhuang.Low complexity sphere decoding detection algorithm based on MIMO-OFDM system[J].Application Research of Computers,2011,28(9):3436-3438.

[2]鄭俊松, 周曉方. 一種格縮減輔助MIMO檢測的組合量化誤差校正方法[J]. 小型微型計算機系統(tǒng), 2013, 34(8):1926-1929.

ZHENG Junsong, ZHOU Xiaofang.Quantization Error Correction Scheme for Lattice-reduction Aided MIMO Detection[J].Mini-micro Systems,2013,34(8): 1926-1929.

[3]趙新雪, 李瓊, 肖維杰,等. 低復雜度最大似然MIMO信號檢測算法[J]. 計算機工程與設(shè)計, 2014, 35(1):144-147.

ZHAO Xinxue, LI Qiong, XIAO Weijie, et al. Low-complexity ML signal detection algorithm for MIMO system[J]. Computer Engineering and Design, 2014, 35(1):144-147.

[4]芮國勝, 張海波, 張洋,等. 接近最優(yōu)檢測性能的低復雜度線性并行MIMO檢測算法[J]. 通信學報, 2013(2):8-14.

RUI Guosheng,ZHANG Haibo,ZHANG Yang,et al. Low complexity linear parallel detection algorithm for near ML detection of MIMO systems[J].Journal on Communications,2013(2):8-14.

[5]MARINELLO J C, TAUFIK A. Lattice Reduction Aided Detector for MIMO Communication Via Ant Colony Optimisation[J]. Wireless Personal Communications, 2014, 77(1):63-85.

[6]KNIEVEL C, HOEHER P A. On Particle Swarm Optimization for MIMO Channel Estimation[J]. Journal of Electrical & Computer Engineering, 2012, 2012(9):1-10.

[7]DORIGO M, STüTZLE T. Ant Colony Optimization: Overview and Recent Advances[J]. International, 2010, 17(5):227-263.

[8]HENRICI P. Bounds for iterates, inverses, spectral variation and fields of values of non-normal matrices[J]. Numerische Mathematik, 1962, 4(1):24-40.

[9]AU E K S, WANG C, SFAR S, et al. Error probability for MIMO zero-forcing receiver with adaptive power allocation in the presence of imperfect channel state information[J]. IEEE Transactions on Wireless Communications, 2007, 6(4):1523-1529.

[10] LAIN J K, CHEN J Y. Near-MLD MIMO Detection Based on a Modified Ant Colony Optimization[J]. Communications Letters IEEE, 2010, 14(8):722-724.

[11] KIM S. Transmit Antenna Selection for Spatial Multiplexing UWB MIMO Systems Using Sorted QR Decomposition[J]. Ieice Transactions on Fundamentals of Electronics Communications & Computer Sciences, 2012, 95(E95.A):1426-1429.

Enhanced ant colony optimization and ordering based MIMO system symbol detection algorithm

YE Zhuoying

(Department of Electronics and Information Engineering, Xiamen City University, Xiamen 361008, P.R. China)

Abstract:Maximum likelihood MIMO(multiple-input-multiple-output) detection algorithm has best symbol detection performance, but it’s computation complexity increases in exponential order with the scale of antenna matrix, so a MIMO detection algorithm with lower computational complexity is proposed for that problem. Firstly, log maximum likelihood based sorted QR decomposition algorithm is used to decompose channel matrix into an orthonormal matrix and the upper triangular matrix, and the transmit order is changed accordingly, and the error propagation is improved by error decision; then, negative pheromones are introduced to ant colony algorithm, and the system congestion is controlled efficiently; lastly, the pheromones are updated according to the distance of the path. The negative pheromone based pheromone updating strategy is designed to improve the ability of congestion control, and considering the faded character of channel, the pheromone is accumulated based on the distance of the path. Some compared simulation experiments are setup to test the performance of the proposed algorithm. The results show that, the bit error rate performance of the proposed algorithm is better than other artificial intelligence algorithm; the computation complexity of the proposed algorithm increase is lower with antenna number for big scale antenna matrix.

Keywords：ant colony optimization; multi-input multi-output system; detection order; computation complexity; bit error rate

DOI：10.3979/j.issn.1673-825X.2016.02.004

收稿日期：2015-06-23

修訂日期：2016-03-06通訊作者：葉卓映ye_zhuoying@163.com

基金項目：廈門城市職業(yè)學院科研項目(KYKJ2015-4)

Foundation Item：The Scientific Research Project of Xiamen City University (KYKJ2015-4)

中圖分類號：TN914;TP393

文獻標志碼：A

文章編號：1673-825X(2016)02-0162-06

作者簡介：

葉卓映(1974-)，男，江西九江人，副教授，博士，高級工程師，主要研究方向為信號與信息處理、MIMO技術(shù)、認知無線電。E-mail:ye_zhuoying@163.com。

(編輯：劉勇)