基于分布估計蜂群算法的多用戶檢測器

劉 婷，張立毅,2，張晉斌

(1.天津商業(yè)大學信息工程學院, 天津 300134；2.天津大學電子信息工程學院,天津 300072；3.宜昌測試技術研究所,湖北 宜昌 443003)

1 引言

多用戶檢測技術是降低多址干擾、克服遠近效應的有效方法之一，是碼分多址CDMA(Code Division Multiple Access)系統(tǒng)的關鍵技術。它在傳統(tǒng)檢測基礎上，充分利用多址干擾的先驗信息對目標用戶進行聯(lián)合檢測，具有較理想的抗多址干擾和抗遠近效應能力。Verdú S[1]提出的最優(yōu)多用戶檢測技術具有理論上的最佳性能，但計算復雜度隨用戶數(shù)的增加呈指數(shù)增長，幾乎無法實現(xiàn)。從組合優(yōu)化的角度考慮，最優(yōu)多用戶檢測屬于非確定多項式NP(Non-Deterministic Polynomial)問題，經(jīng)典優(yōu)化算法對此類大規(guī)模復雜優(yōu)化問題顯得無能為力，因此人們往往采用智能優(yōu)化算法進行求解，如基于魚群算法的多用戶檢測器[2]、基于蟻群優(yōu)化算法的多用戶檢測器[3]以及基于粒子群優(yōu)化算法的多用戶檢測器[4，5]等。

人工蜂群算法ABC(Artificial Bee Colony)是Karaboga D[6]于2005年提出的一種模仿蜂群智能采蜜行為的新型智能優(yōu)化算法，它通過角色間的轉換使算法具有較強的全局和局部搜索能力，增加了找到最優(yōu)解的概率且在很大程度上避免了早熟現(xiàn)象。由于其具有收斂速度較快、控制參數(shù)少、易于實現(xiàn)等優(yōu)點[7]，被廣泛應用于數(shù)字濾波器設計[8]、神經(jīng)網(wǎng)絡訓練[9]和數(shù)據(jù)挖掘[10]等領域。標準ABC算法主要用于連續(xù)優(yōu)化領域，為求解組合優(yōu)化問題，Marinakis Y等[11]于2009年提出了一種稱為BinABC的二進制人工蜂群算法。2012年，Liu Ting等[12]將BinABC算法用于求解多用戶檢測問題，提出了基于BinABC算法的多用戶檢測方案，但該方案存在收斂速度慢、易早熟等缺點。

分布估計算法EDA(Estimation of Distribution Algorithm)[13]是一種基于概率模型的智能優(yōu)化算法，它從統(tǒng)計學習角度出發(fā)，依據(jù)概率模型描述整個群體的進化，利用種群的全局信息進行建模，具有良好的全局探索能力。本文將分布估計算法與人工蜂群算法相結合，提出一種基于分布估計的二進制人工蜂群算法，并應用于求解最優(yōu)多用戶檢測問題。所提算法利用了人工蜂群算法具有較強搜索能力和有效避免局部最優(yōu)的優(yōu)勢，結合分布估計算法可獲得全局群體信息的特點，增強算法性能，更有效地求解最優(yōu)多用戶檢測問題。仿真結果表明，所提多用戶檢測方案的收斂性能、誤碼率性能和抗遠近效應性能均明顯優(yōu)于傳統(tǒng)檢測器。

2 多用戶檢測模型

考慮具有K個用戶共享的同步基帶CDMA信道，信號經(jīng)高斯信道傳輸，接收端接收到的基帶信號為：

(1)

其中，Ak為第k個用戶的幅度；bk∈{-1,+1}為第k個用戶的信息比特值；T為碼元持續(xù)時間；sk(t)為第k個用戶具有單位功率的特征波形；z(t)為具有單位功率譜密度的加性高斯白噪聲AWGN(Additive White Gaussian Noise)；σ2為噪聲的方差。

接收信號通過匹配濾波器組進行相干處理，第q個匹配濾波器的輸出yq為:

(2)

y=RAb+z

(3)

(4)

最優(yōu)多用戶檢測器采用Bayes后驗概率最大原理，其目的是在解空間尋找字符矢量b使得以下函數(shù)最大化:

J(b)=2bTAy-bTHb

(5)

其中，H=ARA。

3 人工蜂群算法

人工蜂群算法包括三種角色：引領蜂、跟隨蜂和偵察蜂。它的基本原理為：引領蜂首先飛出蜂巢，在對應食物源周圍進行鄰域搜索并利用“貪婪原則”進行選擇。回到蜂巢后，引領蜂將食物源信息通過跳搖擺舞的形式傳遞給跟隨蜂，跟隨蜂觀察引領蜂的食物源信息，選擇優(yōu)秀食物源進行跟隨，并再次在其附近進行鄰域搜索和“貪婪選擇”。當某個食物源被放棄，與之對應的引領蜂成為偵察蜂，開始尋找新食物源。

利用ABC算法求解最大化問題時，蜜蜂采蜜與函數(shù)優(yōu)化間的對應關系如表1所示。

ABC算法的具體實現(xiàn)過程如下。

(1)初始化。

Table 1 Relationships between honeybee foraging and function optimization表1 蜜蜂采蜜與函數(shù)優(yōu)化對應關系

設置最大循環(huán)次數(shù)MCN和引領蜂轉換為偵察蜂的次數(shù)limit，隨機生成SN個初始食物源(解)x=(x1,x2,…,xi,…,xSN)，計算每個食物源的食物濃度。Karaboga D等[14]認為，引領蜂的數(shù)量應與跟隨蜂相同，都等于食物源數(shù)量；偵察蜂的數(shù)量為1。

第i個食物源表示為xi=(xi1,xi2,…,xiD)，其中D為問題維數(shù)，它由以下方式初始化:

xid=xid,min+(xid,max-xid,min)rand1

(6)

其中，d∈{1,2,…,D}，xid,max和xid,min分別是xid的上、下限；rand1為(0，1)之間的隨機數(shù)。

利用式(7)計算第i個食物源的食物濃度(適應度值):

(7)

其中，f為對應優(yōu)化問題的目標函數(shù)。

(2)引領蜂行為。

引領蜂首先在對應食物源上進行一次鄰域搜索，并采用“貪婪”原則進行選擇。對食物源xi進行鄰域搜索，產(chǎn)生新食物源vi=(vi1,vi2,…,viD)的公式為:

(8)

其中，l為[1,SN]的隨機整數(shù)且l≠i；drand為[1,D]的隨機整數(shù)；rid∈[-1,1]是一個隨機數(shù)，控制鄰域搜索的范圍。

(3)跟隨蜂行為。

引領蜂完成搜索后，回到舞蹈區(qū)把食物源的信息傳達給跟隨蜂。跟隨蜂根據(jù)“輪盤賭”方式選擇食物源。食物濃度越高的引領蜂招募到的跟隨蜂越多。第i個食物源被選中的概率為:

(9)

其中，Pi稱為轉移概率。

跟隨蜂也在選中食物源附近進行鄰域搜索和“貪婪”選擇。若跟隨蜂搜索新食物源的食物濃度大于原引領蜂的舊食物源時，替換原引領蜂的舊食物源，完成角色互換；反之，保持不變。

(4)偵察蜂行為。

為了增加種群多樣性，防止算法陷入局部最優(yōu)，當某食物源的食物濃度連續(xù)limit次沒有被更新，應該被放棄，與之對應的引領蜂變?yōu)閭刹旆洌⒏鶕?jù)式(6)隨機生成新食物源。

(5)結束。

判斷是否滿足算法結束條件，若滿足，輸出目前找到的最優(yōu)食物源；若不滿足，返回繼續(xù)執(zhí)行引領蜂、跟隨蜂和偵察蜂行為。ABC算法的結束條件通常設為循環(huán)次數(shù)遞減至零或滿足允許的誤差值。

上述標準ABC算法只適用于連續(xù)優(yōu)化領域，而最優(yōu)多用戶檢測屬于二進制優(yōu)化問題，需要采用二進制人工蜂群算法BABC(Binary Artificial Bee Colony)算法。

(10)

(11)

(12)

(13)

其中，rand2和rand3均為(0，1)的一個隨機數(shù)。

BinABC算法的其他實現(xiàn)過程與標準ABC算法相同。

4 分布估計算法

分布估計算法是一種基于概率模型的進化算法，與傳統(tǒng)進化算法不同，它不采用交叉、變異等操作，而是根據(jù)當前種群的概率分布產(chǎn)生下一代種群[17]。在分布估計算法中，先對個體進行統(tǒng)計分析，按照某種準則建立概率模型，然后采樣產(chǎn)生下一代種群，如此反復直到找到最優(yōu)解。

分布估計算法的實現(xiàn)步驟如下[18]：

(1)初始化種群；

(2)選擇：根據(jù)適應度值選擇優(yōu)勢群體；

(3)建模：根據(jù)優(yōu)勢群體，采用某種準則建立概率模型；

(4)抽樣：根據(jù)概率模型，隨機抽樣產(chǎn)生新一代種群；

(5)判斷是否滿足結束條件，若滿足，輸出種群中的適應值最好的個體，若不滿足，返回執(zhí)行(2)。

分布估計算法包括多種概率模型，其中最簡單且應用最廣的是基于群體的增量學習PBIL(Population-Based Incremental Learning)算法，本文采用PBIL來建模。

5 基于分布估計二進制人工蜂群算法的多用戶檢測技術

5.1 基于分布估計的二進制人工蜂群算法

本文把分布估計算法思想引入二進制人工蜂群算法，提出一種基于分布估計的二進制人工蜂群算法EDBABC(Estimation of Distribution Binary Artificial Bee Colony)，并將其用于優(yōu)化最優(yōu)多用戶檢測問題。

EDBABC算法能把EDA獲得的全局群體信息和BABC得到的局部個體信息相結合，提高算法性能。在EDBABC算法中，采用概率矢量P=(P1,P2,…,Pd,…,PD)表示優(yōu)質解空間分布的概率模型，其中Pd(d=1,2,…,D)表示優(yōu)質解空間第d維取1的概率，初始時刻Pd均為0.5。

EDBABC算法的具體實現(xiàn)過程如下。

(1)初始化。

(2)引領蜂行為。

引領蜂在對應食物源上進行一次鄰域搜索，并采用“貪婪”原則進行選擇。鄰域搜索方式是整個EDBABC算法的核心，新的鄰域搜索公式為：

(14)

(15)

其中，rand5為(0，1)的隨機數(shù)。上式說明，概率矢量P引導著食物源的更新，因此EDBABC算法具有更好的全局特性。

(3)更新概率矢量。

按照以下方式更新概率矢量P：選擇Z(Z=SN/2)個適應度值較高的優(yōu)秀解組成優(yōu)秀解空間{x′1,x′2,…,x′i,…,x′Z}，其中x′i=(x′i1,x′i2,…,x′id,…,x′iD)，根據(jù)PBIL模型構建概率矢量更新公式:

(16)

其中，α表示學習速率，0<α<1，它可以平衡算法全局探索能力和局部開采能力[18]。

(4)跟隨蜂行為。

跟隨蜂選擇食物源后，仿照引領蜂，采用式(14)、式(15)進行鄰域搜索、完成“貪婪”選擇。

(5)更新概率矢量。

選擇Z個優(yōu)秀解，利用式(16)更新概率矢量。

(6)偵察蜂行為。

判斷是否有需要放棄的解，如果有，引領蜂變成偵察蜂，為了增加種群多樣性，仍采用隨機生成的0、1代替舊解，找到新解后偵察蜂又變?yōu)橐I蜂。

(7)結束。

5.2 基于分布估計二進制人工蜂群算法的多用戶檢測技術

把最優(yōu)多用戶檢測搜索最佳字符矢量的過程看作是分布估計二進制人工蜂群算法尋找最優(yōu)解的過程，可得到基于分布估計二進制人工蜂群算法的多用戶檢測(EDBABC-MUD)。

(17)

(18)

(19)

基于EDBABC算法的多用戶檢測的具體實現(xiàn)步驟為：

(1)初始化。

(2)執(zhí)行循環(huán)。

③ 更新概率矢量：選擇Z個優(yōu)秀解，利用式(16)更新概率矢量。

⑤ 依據(jù)轉移概率，跟隨蜂選擇引領蜂進行跟隨，并利用式(14)和式(15)進行鄰域搜索，完成“貪婪”選擇。

⑥ 更新概率矢量：選擇Z個優(yōu)秀解，利用式(16)更新概率矢量。

⑦ 判斷是否有需要放棄的解。如果有，引領蜂變成偵察蜂，利用隨機生成的0、1代替舊解。

⑧ 記錄到目前為止的最優(yōu)解。判斷是否滿足算法的終止條件。若滿足，輸出找到的最優(yōu)解(注意，需要映射到-1、1空間)，否則繼續(xù)循環(huán)。

6 計算機仿真

考慮高斯同步DS-CDMA通信系統(tǒng)，采用31位Gold序列來擴展頻譜，選用以下檢測器進行性能比較：基于EDBABC算法的多用戶檢測器(EDBABC-MUD)、基于BinABC算法的多用戶檢測器[12](BinABC-MUD)、基于PBIL的多用戶檢測器(PBIL-MUD)、解相關多用戶檢測器(Decorr)、匹配濾波器(Match)和最優(yōu)多用戶檢測器(OMD)。

6.1 收斂性能

EDBABC-MUD、BinABC-MUD和PBIL-MUD的平均誤碼率BER(Bit Error Rate)與迭代次數(shù)的關系曲線如圖1所示。仿真中各用戶信噪比SNR(Signal to Noise Ratio)相同并固定在14 dB，其他參數(shù)為：K=10時，SN=10，MCN=100，limit=10，MR=0.4，α=0.5；K=20時，SN=20，MCN=200，limit=20，MR=0.4，α=0.5。

從圖1可以看出，由于更強的全局性能和多維鄰域搜索策略，EDBABC-MUD的收斂速度最快；PBIL-MUD收斂速度次之，但由于PBIL算法易陷入局部最優(yōu)，使得PBIL-MUD并未收斂到零；BinABC-MUD具有最慢的收斂速度，如K=10時，EDBABC-MUD迭代12次即可收斂，而BinABC-MUD則需要迭代48次，EDBABC-MUD的速度是BinABC-MUD的4倍。K=20時，BinABC-MUD需要181次才能收斂而EDBABC-MUD只需要21次，EDBABC-MUD的速度是BinABC-MUD的8.6倍。BinABC-MUD要想獲得更好的收斂性能，必須增加MCN或者SN。

Figure 1 Curves of convergence performance圖1 收斂性能曲線

6.2 誤碼率性能

設各用戶的SNR相同，均從0 dB變化到20 dB，通過統(tǒng)計各用戶的平均誤碼率BER檢驗各種檢測器在不同信噪比下的誤碼率性能，仿真結果如圖2所示。仿真參數(shù)為：K=10時，SN=10，MCN=50，limit=10，MR=0.4，α=0.5；K=20時，SN=20，MCN=50，limit=10，MR=0.4，α=0.5。

Figure 2 Curves of BER performance圖2 誤碼率性能曲線

從圖2可以看出，Match檢測器受多址干擾影響較大，性能最差；PBIL-MUD由于未收斂到零，誤碼率性能也較差；BinABC-MUD的BER性能改善不明顯，在SNR達到一定值后，BER基本趨于平穩(wěn)，沒有明顯下降，這主要是由于在較低SN或MCN條件下，BinABC-MUD并未收斂造成的。BinABC-MUD要想獲得更好的誤碼率性能需要增加MCN或者SN。更高的MCN或者SN意味著更高的復雜度；Decorr也具有較好的誤碼率性能；EDBABC-MUD由于具有較快的收斂速度，隨著SNR的增加，BER下降最快，性能最接近OMD。

6.3 抗遠近效應性能

將移動臺離基地的遠近轉化為各移動臺發(fā)送功率的大小[19]。目標用戶1的SNR固定在6 dB，干擾用戶的SNR從6 dB變化到14 dB以得到不同的遠近比，其它仿真參數(shù)與圖2相同。通過統(tǒng)計目標用戶1的BER以檢驗各種檢測器中用戶1的抗遠近效應的能力，所得結果如圖3所示。從圖3可以看出，所有檢測器中EDBABC-MUD抗遠近效應能力最強，最接近OMD，原因是EDBABC-MUD是基于OMD模型的，OMD具有最佳的抗遠近效應能力，所以EDBABC-MUD也具有很好的抗遠近效應能力。

Figure 3 Curves of near-far resistance圖3 抗遠近效應性能曲線

7 復雜度分析

下面對EDBABC-MUD的計算復雜度進行分析。

算法復雜度主要取決于乘法的次數(shù)。EDBABC算法中涉及乘法的有：計算適應度值、計算轉移概率和更新概率矢量，其中計算轉移概率和更新概率矢量的計算量與適應度值計算相比，可忽略不計。EDBABC-MUD算法共有三次適應度值計算，其計算量約為：

QEDBABC-MUD≈MCN×SN×3Qf×N

(20)

其中，N為每個用戶發(fā)送的數(shù)據(jù)量，Qf為利用式(5)計算目標函數(shù)值的計算量。

最優(yōu)多用戶檢測的計算量約為：

QOMD=2K×Qf×N

(21)

(22)

因此，EDBABC-MUD的計算量直接取決于MCN和SN，由收斂性能的仿真參數(shù)可得當SN=K時，MCN≈K，即：

(23)

上式說明，與最優(yōu)多用戶檢測相比，EDBABC-MUD算法復雜度降低，例如K=20時，EDBABC-MUD的計算復雜度降低約873倍。

8 結束語

人工蜂群算法利用種群的個體信息實現(xiàn)尋優(yōu)，具有較好的局部開采能力。本文充分利用分布估計算法可獲得全局群體信息與二進制人工蜂群算法可獲得局部個體信息的優(yōu)勢，將二者有機結合，提出了一種改進二進制人工蜂群算法。為了加快收斂速度、降低計算復雜度，改進算法采用直接針對離散域的多維鄰域搜索策略，避免了連續(xù)域到離散域的轉換。并將改進算法應用于求解多用戶檢測問題，提出了一種基于分布估計二進制人工蜂群算法的多用戶檢測算法，實驗結果驗證了算法的有效性。

[1] Verdú S.Minimum probability of error for asynchronous Gaussian multiple-access channels[J]. IEEE Transactions on Information Theory, 1986, 32(1):85-96.

[2] Yu Yang,Yin Zhi-feng,Tian Ya-fei.Multiuser detector based on adaptive artificial fish school algorithm[J]. Journal of Electronics and Information Technology, 2007, 29(1):121-124.(in Chinese)

[3] Xu C, Maunder R G, Yang L L, et al. Near-optimum multiuser detectors using soft-output ant-colony-optimization for the DS-CDMA uplink[J]. IEEE Signal Processing Letters, 2009, 16(2):137-140.

[4] Soo K K, Siu Y M, Chan W S, et al. Particle-swarm-optimization-based multiuser detector for CDMA communications[J]. IEEE Transactions on Vehicular Technology, 2007, 56(5):3006-3013.

[5] Liu Hong-wu,Feng Quan-yuan.Particle swarm optimization-based and receive-diversity-aided multiuser detection for STBC MC-CDMA systems[J]. Journal of Electronics and Information Technology, 2009, 31(1):45-48.(in Chinese)

[6] Karaboga D. An idea based on honey bee swarm for numerical optimization[R]. Technical Report-TR06, Kayseri, Turkey:Erciyes University, 2005.

[7] Luo Jun, Wang Qi-ang, Fu Li. Application of modified artificial bee colony algorithm to flatness error evaluation[J]. Optics and Precision Engineering, 2012, 20(2):422-430.(in Chinese)

[8] Karaboga D. A new design method based on artificial bee colony algorithm for digital IIR filters[J]. Journal of the Franklin Institute, 2009, 346(4):328-348.

[9] Hsieh T J, Hsiao H F, Yeh W C. Forecasting stock markets using wavelet transforms and recurrent neural networks:An integrated system based on artificial bee colony algorithm[J]. Applied Soft Computing, 2011, 11(2):2510-2525.

[10] Karaboga D, Ozturk C. A novel clustering approach:Artificial bee colony (abc) algorithm[J]. Applied Soft Computing, 2011, 11(1):652-657.

[11] Marinakis Y,Marinaki M,Matsatsinis N.A hybrid discrete artificial bee colony-GRASP algorithm for clustering[C]∥Proc of International Conference on Computers Industrial Engineering, 2009:548-553.

[12] Liu Ting, Zhang Li-yi, Bao Wei-wei,et al. Multiuser detection technique based on binary artificial bee colony algorithm[C]∥Proc of the 2nd International Conference on Electronics, Communications and Control, 2012:2037-2040.

[13] Chen Tian-shi, Tang Ke, Chen Guo-liang, et al. Analysis of computational time of simple estimation of distribution algorithms[J]. IEEE Transactions on Evolutionary Computation, 2010, 14(1):1-22.

[14] Karaboga D,Akay B.A modified artificial bee colony(ABC) algorithm for constrained optimization problems[J]. Applied Soft Computing, 2011, 11(3):3021-3031.

[15] Kennedy J, Eberhart R C. A discrete binary version of the particle swarm algorithm[C]∥Proc of IEEE International Conference on Systems, Man, and Cybernetics, 1997:4104-4109.

[16] Pampara G, Engelbrecht A P, Franken N. Binary differential evolution[C]∥Proc of IEEE Congress on Evolutionary Computation, 2006:1873-1879.

[17] Wang Ling, Wang Sheng-yao, Fang Chen. A hybrid distribution estimation algorithm for solving multidimensional knapsack problem[J]. Control and Decision, 2011, 26(8):1121-1125.(in Chinese)

[18] Zhou Ya-lan, Wang Jia-hai, Yin Jian. A discrete particle swarm optimization algorithm based on estimation of distribution[J]. Acta Electronica Sinica, 2008, 36(6):1242-1248.(in Chinese)

[19] Ren Cheng, Tang Pu-ying, Fang Jun. Multiuser detector based on particle swarm optimization with stretching technique[J]. Journal of University of Electronic Science and Technology of China, 2007, 36(5):915-917.(in Chinese)

附中文參考文獻：

[2] 俞洋，殷志鋒，田亞菲．基于自適應人工魚群算法的多用戶檢測器[J]．電子與信息學報，2007，29(1)：121-124．

[5] 劉洪武，馮全源．分集接收的STBC-MC-CDMA系統(tǒng)中基于PSO算法的多用戶檢測[J]．電子與信息學報，2009，31(1)：45-48．

[7] 羅鈞，王強，付麗．改進蜂群算法在平面度誤差評定中的應用[J]．光學精密工程，2012，20(2)：422-430．

[17] 王凌，王圣堯，方晨．一種求解多維背包問題的混合分布估計算法[J]．控制與決策，2011，26(8)：1121-1125．

[18] 周雅蘭，王甲海，印鑒．一種基于分布估計的離散粒子群優(yōu)化算法[J]．電子學報，2008，36(6)：1242-1248．

[19] 任誠，唐普英，方峻．拉伸技術粒子群優(yōu)化算法的多用戶檢測器[J]．電子科技大學學報，2007，36(5)：915-917．