基于改進入侵雜草算法的多用戶檢測

國 強，張金程，周 凱

(哈爾濱工程大學 信息與通信工程學院，黑龍江 哈爾濱 150001)

0 引言

在DS-CDMA系統[1]中，由于擴頻序列的非完全正交性、各用戶的隨機接入以及實際信道的異步傳輸等原因，使得用戶之間產生多址干擾。當用戶數量達到一定程度，多址干擾成為主要的系統干擾，采用傳統檢測器(Conventional Detector，CD)會使系統容量降低，通信質量下降，嚴重影響系統性能。多用戶檢測技術[2-3]是克服多址干擾的關鍵技術之一。最優多用戶檢測器(Optimal Multi-user Detection，OMD)[4]雖然具有良好的檢測性能，但是其計算復雜度隨著用戶數的增加成指數增長，當用戶數量較多時計算復雜度極高，工程上難以實現。DS-CDMA系統的多用戶檢測問題可以看作是一個組合優化問題，通過智能算法來求解[5-8]。

入侵雜草算法(Invasive Weed Optimization，IWO)[9]是Mehrabian和Lucas在2006年提出的一種仿生優化算法，模擬自然環境中雜草的生長擴散過程，具有收斂速度快、魯棒性好、結構簡單以及易于實現等特點[10]。IWO算法在多目標優化[11]、陣列天線稀布[10，12]和能源負荷動態調度[13]等領域得到廣泛應用。這些應用大多屬于連續空間或者整數空間優化問題，而利用IWO算法求解二進制離散空間問題的研究相對較少。

本文主要研究DS-CDMA系統的多用戶檢測，為解決最優多用戶檢測器復雜度過高問題，引入入侵雜草優化算法。并從抗多址干擾能力、抗遠近效應能力和收斂性等方面進行仿真分析。

1 系統模型

1.1 同步DS-CDMA系統模型

假設一個具有K個用戶的DS-CDMA系統，所有用戶采用二進制相移鍵控調制(Binary Phase Shift Keying，BPSK)，系統的信道噪聲為加性高斯白噪聲，在不考慮信道衰落和多徑效應的情況下，假設捕獲跟蹤條件理想，即忽略載波調制解調，則通信系統接收端的信號模型為：

(1)

式中，SF表示擴頻序列長度；Ak表示用戶k的信號幅度；bk表示用戶k發送的比特信息；Tb表示碼元間隔；T表示傳輸信息的周期間隔；τk表示用戶k的延時；n(t)表示均值為0，能量為σ2的加性高斯白噪聲；sk(t)表示用戶k的擴頻序列，其波形是持續時間為Tb的矩形波，并且具有歸一化能量，即

(2)

若所有用戶的延時均為0，式(1)變為同步DS-CDMA系統的信號模型，簡化擴頻序列，則可表示為：

(3)

1.2 傳統檢測器

傳統檢測器，利用用戶的擴頻序列對接收到的信號進行相關接收。相關處理后的信號表示為：

(4)

式中，nk為信道噪聲經過匹配濾波器k后的剩余噪聲；MAIk為干擾用戶對期望用戶產生的多址干擾；ρjk為用戶j和用戶k擴頻序列的歸一化互相關系數。

(5)

對相關處理后的信息進行硬判決，得到：

bk=sign(yk) 。

(6)

1.3 最優多用戶檢測器

最優多用戶檢測算法的基本思想是充分利用所有用戶信息，對用戶信號進行聯合檢測，相當于用戶比特信息先驗概率相等條件下的最大似然序列檢測，性能能夠接近單用戶系統。檢測得到的結果要使式(7)的似然函數最大化。

(7)

經過推導，上式可等效為使式(8)最大化。

(8)

式中，H=ARA，A為以用戶幅度為元素的對角陣。

OMD檢測器的運算復雜度為O(2k)，與用戶數量成指數關系。當用戶數較多時，以現有的硬件水平難以實現。

2 基本的入侵雜草優化算法

入侵雜草優化算法是模擬自然界中雜草的繁殖、擴散和消亡的過程而得到的一種尋優算法。其中每一個雜草代表要求解問題的一個可行解，子代雜草為雜草通過空間擴散得到的新解。在尋優過程中，雜草根據自身適應度值的大小產生一定數量的種子，種子以正態分布的步長分布在父代雜草的周圍區域，成長為代雜草。在每一級迭代中，通過比較所有父代雜草和子代雜草的適應度值，保留適應度好的雜草進行下一代繁殖擴散。其過程主要包括3個步驟[10]：

① 種子繁殖。雜草xi根據其適應能力產生不同數量的種子，適應度值好的雜草產生較多的種子，適應度值差的雜草產生較少的種子。對于求解最大化問題，生成種子的數量根據式(9)確定：

(9)

式中，f(xi)表示雜草xi的適應度值；fmax和fmin表示當前迭代中所有種子的最大適應值和最小適應值；Smax和Smin表示一個種子能夠產生的最大種子數量和最小種子數量。

② 空間擴散。種子按照均值為0、標準差為σ正態分布步長生長成雜草，分布在父代雜草的周圍空間。每一代標準差σiter的大小按照式(10)確定：

(10)

式中，iter表示當前的迭代次數；itermax表示最大的迭代次數；σini和σfin表示標準差的初始值和最終值(一般初始值大于最終值)；n是非線性調和因子，通常情況下n=3[14]。

雜草i產生的第s個種子的位置可以表示為：

(11)

③競爭排除。在種子的繁殖擴散過程中，當雜草的數量達到最大種群規模Pmax后，將父代雜草和子代雜草按適應度值大小進行排序，保留適應值較好的Pmax個雜草，淘汰其余的雜草。

3 基于改進IWO算法的多用戶檢測

3.1 改進的IWO算法

3.1.1 映射函數

在標準的IWO算法中，種子的擴散空間是圍繞在父代雜草周圍的高斯分布。在調制方式為BPSK的DS-CDMA系統中所傳輸的信息為{-1，+1}，所以標準IWO算法中的擴散方式不能直接應用于二進制雜草個體的擴散，需要通過恰當的方式進行映射，把擴散值轉換成雜草某一維度的變異概率。

(12)

式中，sigmokd(x)=1/(1+e-1)。

由映射產生的變異概率，得到該維度的變異標志flag，表示為：

(13)

式中，rand為(0，1)之間的隨機數。

則其子代雜草第k維的值為：

(14)

3.1.2 改進的標準差變化曲線

在標準的IWO算法中，正態分布的標準差按式(10)計算，從圖1可以看出隨著進化代數的增加，標準變化曲線下降緩慢。若最大迭代次數為30代，則當迭代次數達到25時，標準差才能接近最小值。在二進制多用戶檢測系統的進化前期，較大的標準差可以使子代雜草分布在距離父代雜草較遠的位置，即子代雜草與父代雜草的漢明距離比較大，有利于全局搜索。但是在進化中后期，種群分布在最優解的附近，較大的變異概率不利于提高尋優精度。為此設置標準差的變化曲線如式(15)所示，圖1中改進變化曲線為其示意圖。可以看出，改進的進化曲線在進化前期可以使算法在整個空間進行全局搜索，之后迅速在較小區域進行局部搜索。

σiter=tanh(-iter+4)+2.5。

(15)

圖1 正態分布標準差變化曲線

3.2 基于改進IWO算法的多用戶檢測器

改進IWO算法的多用戶檢測器步驟：

① 參數設置。設置種群的初始規模和最大規模；種子繁殖的最大數量和最小數量等參數。

② 種群初始化。為了保證初始種群的多樣性，采用均勻分布方式產生初始種群，使初始雜草隨機分布在整個搜索空間。

③ 根據式(8)計算每個種子的適應度值，按照式(9)計算每一個雜草產生種子的數量，完成種子繁殖。

④ 通過雜草擴散的正態分布標準差，計算每一維度的擴散值，通過式(12)得到變異概率，產生變異標志，然后進行維度變異、完成空間擴散。

⑤ 計算子代雜草的適應度值，和父代雜草一起進行排序，進行競爭排除，淘汰較差個體。

⑥ 判斷是否到達結束條件。若滿足結束條件，則輸出用戶的估計值；否則繼續執行步驟③。

4 仿真分析

假設一個用戶數為10的同步DS-CDMA系統，采用BPSK調制，擴頻序列采用長度為31的Gold碼，最大歸一化互相關系數為9/31。為了方便討論，假定系統具有嚴格的功率控制，擴頻序列和用戶幅度估計準確。

為了驗證基于改進IWO(Improved IWO，IIWO)算法多用戶檢測器的有效性，使用CD檢測器、解相關檢測器(De-correlation Detector，DEC)、OMD檢測器、基于基本遺傳算法(Genetic Algorithm，GA)、基本PSO算法和基本IWO算法的多用戶檢測器進行對比。GA的種群規模設置為10，交叉概率設置為0.8，變異概率設置為0.05；PSO多用戶檢測器的參數設置參考文獻[15]，種群規模設置為10，加速度因子分別設置為2，最大加速度設置為6；IWO算法的最大種群規模設置為5，雜草產生的最大種子數量為4，最小數量為0，初始標準差為4，最終標準差為1.5，非線性調和因子為3；IIWO算法的最大種群規模設置為5，雜草產生的最大種子數量為4，最小數量為0，標準差按式(15)變化。智能算法的最大迭代次數設置為30。

仿真實驗1：檢測器在不同信噪比下的誤碼率如圖2所示。從圖中可以看出，在上述參數設置下，IWO和IIWO檢測器接近OMD檢測器的性能，而信噪比大于8 dB時，PSO和GA檢測器在30次迭代內未尋找到最優解。

圖2 檢測性能隨信噪比變化情況

仿真實驗2：為了驗證算法的抗遠近效應能力，假設除用戶1外其他用戶的信息幅度為1，信噪比為8 dB，用戶1與其他用戶的幅度比A1/Ai從0.1～10變化。所有用戶的平均誤碼率如圖3所示。從圖中可以看出，IIWO檢測器的誤碼率比DEC檢測器約低1.5 dB，具有良好的抗遠近效應能力。

仿真實驗3：為了驗證算法的收斂特性，設置信噪比為8 dB，最大進化代數為30。不同檢測器的平均誤碼率隨進化代數的變化情況如圖4所示。由圖4中可以看出，IIWO檢測器的收斂性能明顯優于PSO檢測器、IWO檢測器和GA檢測器，在進化代數為10時，即可找到最優解。

仿真實驗4：為驗證檢測器性能隨用戶數量的變化情況，設信噪比為8 dB，最大進化代數為30。所有用戶的平均誤碼率變化情況如圖5所示。可以看出，IIWO算法的誤碼率最低。

圖3 不同檢測器抗遠近效應能力對比

圖4 不同檢測器收斂性能對比

圖5 檢測性能隨用戶數量變化情況

5 結束語

為了將入侵雜草優化算法應用于多用戶檢測，本文在算法中引入映射函數，針對基本正態分布標準差收斂速度慢的問題，提出改進的標準差變化曲線。仿真結果表明，該方法在抗多址干擾、抗遠近效應能力方面接近最優多用戶檢測；收斂速度優于基本GA，PSO，IWO算法；當用戶數量變化時，檢測性能優于CD、DEC和其他3種基于智能算法的檢測器；而且計算復雜度要明顯低于OMD檢測器。下一步將研究IWO算法與其他智能算法相結合的多用戶檢測器，進一步提高檢測器的收斂速度和魯棒性。