蟻群算法多用戶檢測用于MC-CDMA系統

摘 要:在MC-CDMA系統中檢測技術是影響系統性能的關鍵技術之一。這里首先對最優多用戶檢測方法做出了簡要的分析，然后引入蟻群算法多用戶檢測，使用最優多用戶檢測的判決準則作為蟻群算法中的目標函數，并對蟻群算法多用戶檢測和其他多用戶檢測性能做了仿真比較。結果表明蟻群算法多用戶檢測和其他次優多用戶檢測相比，具有較好的性能;和最優多用戶檢測相比具有很低的復雜度。在多用戶檢測的實際應用中表現出了很大的優勢。

關鍵詞:MC-CDMA; 最優多用戶檢測; 次優多用戶檢測; 蟻群算法; 復雜度

中圖分類號:TP274文獻標識碼:A

文章編號:1004-373X(2010)08-0157-03

Ant Colony Optimization Multi-user Detection Used in MC-CDMA System

YANG Yu-bing LUAN Ying-zi

(Xidian University， Xi’an710071， China)

Abstract:The detection technology is one of the key technologies which affects the systematic performance ofmulti-carrier code division multiple access (MC-CDMA) systems. The method of the optimum multi-user detection is analysed briefly. Taking the judge criterion of the optimum multi-user detection as its objective function， the performance of the multi-user detection of ant colony algorithm is compared to that of others multi-user detections. The result proves that the ant colony optimization multi-user detection has strong points of low-complexity comparing to the optimum multi-user detection， and has higher performance than MMSE detection in practical application.

Keywords:MC-CDMA; optimum multi-user detection; sub- optimummulti-user detection; ant colony algorithm; complexity

多載波碼分多址(MC-CDMA)系統將正交頻分復用(OFDM)與碼分多址(CDMA)結合，具有較高的頻譜效率與系統容量。在MC-CDMA系統上行鏈路中，由于多個用戶的信號在不同子載波上經歷了相互獨立的衰落，從而破壞了不同用戶特征序列的正交性，導致了嚴重的多址干擾。多址干擾是影響MC-CDMA無線通信系統性能的主要因素，而使用多用戶檢測技術可有效消除多址干擾。因此各種多用戶檢測方法成了MC-CDMA系統的研究熱點。1986年Verdu提出的最優多用戶檢測由于具有非常高的復雜度而無法采用，因此，次優檢測器的研究成為必要的任務。在此提出的蟻群算法多用戶檢測正是一種具有低復雜度并且性能很好的次優多用戶檢測器。

1 MC-CDMA系統模型

MC-CDMA發射機和接收機的框圖如圖1所示。其中xj是第j個用戶的符號數據，Cj=[c1j，c2j，…，cNCj]T是第j個用戶的的擴頻碼。每個信息符號先與擴頻序列各位相乘，相乘后的每路信號調制到每個子載波上，若擴頻碼長為N則調制到N個子載波上。也就是說，一個原始數據符號通過擴頻后，成為多個碼片，每個碼片在一個子載波上傳輸。這樣一個符號的信息就在多個子載波上并行傳輸。經過信道后的接收信號進行和發送端相反的操作[1]。

圖1 MC-CDMA發射機和接收機的框圖

MC-CDMA系統中的多用戶檢測器實現框圖如圖2所示。

圖2 多用戶檢測器實現框圖

考慮采用BPSK調制的MC-CDMA系統，在同步的條件下，接收信號r可以用矩陣形式表示為:

r=hcAb+n(1)

式中:r是接收信號的向量;h是信道頻域響應;c是用戶的擴頻碼矩陣;b是用戶發送的比特數據，b∈{-1，+1};A為接收到的用戶幅度對角陣;n為與發送數據不相關的均值為0，方差為σ的高斯白噪聲。判決信號的充分統計量為匹配濾波器組的輸出:

y=RAb+n(2)

式中:y是匹配濾波器的輸出向量;R是所有用戶的擴頻波形的歸一化自相關矩陣[2]。

1.1 最優多用戶檢測算法

1986年 Verdu首先提出利用已知擴頻碼的結構信息與統計信息來克服多個用戶之間干擾的多用戶檢測理論與方案。最優多用戶檢測器是根據最大似然序列檢測(Maximum Likelihood Sequence Detection，MLSD)提出的。它采用的是Bayes后驗概率最大原理，因此是一種最大似然估計算法。假設用戶數為K，最優檢測器可以看作在2K個解中尋找使下式的函數值最大的解:

J(b)=2bTAr-bTHb(3)

式中:b和A分別為用戶發送的信息比特向量和幅度對角陣;r為匹配濾波器的輸出信號向量;H為歸一化的相關函數[2-3]。最優多用戶檢測器的復雜度和用戶數成指數關系，根據最優多用戶檢測器的判決準則尋找最優多用戶的檢測結果成了一個解決組合優化的NP完全問題[4]。

1.2 蟻群算法多用戶檢測

基于蟻群算法在解決NP完全問題上表現出的優異性能[5]，可以把這種智能算法引入到多用戶檢測問題上來[6-7]。本文主要闡述使用蟻群算法的多用戶檢測模型，誤碼率性能和復雜度比較。

1.2.1 蟻群算法用于多用戶檢測的模型

蟻群算法是意大利學者M.Dorigo于1991年在他的博士論文中首次系統地提出了一種基于螞蟻種群的新型優化算法——蟻群算法(Ant Colony Optimization，ACO)，并用該方法解決了一系列的組合優化問題。該算法受到自然界中真實蟻群的集體行為的啟發，采用的正反饋機制具有較強的魯棒性，優良的分布式計算機制，易于與其他方法結合等優點，在解決許多復雜優化問題方面已經展現出優異的性能和巨大的發展潛力。蟻群算法雖然是從研究求解旅行商問題(TSP)開始提出的，但它現在已經在求解多種組合優化問題中獲得了廣泛應用。像TSP問題、機器人領域、生命科學問題、網絡路由問題、圖像處理以及車輛路徑問題等。蟻群算法已經成為國際智能計算領域中備受關注的研究熱點和前沿性課題[8-9]。

本文通過對MC-CDMA中多用戶檢測問題(Mutiuser Detection，MUD)的分析，建立了一個基于蟻群算法的多用戶檢測問題模型，通過分析多用戶檢測問題與TSP問題的異同，針對多用戶檢測問題提出一種更為簡單的蟻群算法實現思想。該思想可以描述如下:在TSP問題中，每一只螞蟻所要完成的任務就是找到一條經過n個城市的一條路徑。在每到達一城市后，螞蟻都要先檢查隨身攜帶的禁忌表(Tabulist)，然后依據轉移概率在沒有經過的城市中選擇下一個將要到達的城市，并將這個城市添加到禁忌表中。在多用戶檢測中不失一般性，可以讓螞蟻按照從第1個用戶到第K個用戶的順序進行判斷，直到螞蟻走完規定的節點數即用戶數。這樣在設計程序時就可以拋棄在基本蟻群算法中的禁忌表，降低程序的復雜度[7]。另外，因為每個用戶的數據只有1或者-1兩種可能，相當于螞蟻每一次經過一個節點只有兩條供選擇的路徑，轉移概率的公式也會比TSP問題簡單。在TSP問題中，往往是把城市之間的距離作為啟發信息;在多用戶檢測問題中，因為各個用戶之間的獨立性以及每個用戶所發送數據的平穩隨機性，很難尋找到類似于TSP問題中城市間距離這樣的啟發信息，所以本文中直接將啟發信息拋棄，僅利用信息素強度進行轉移概率計算。由此可得到第m只螞蟻從第i個分支上節點轉移到第j個分支上節點的轉移概率公式為:

pmij(t)=τij(t)/∑k∈1，2τik(t)(4)

至此就可以用蟻群算法的思想將多用戶檢測問題描述成如圖3所示的一個路徑選擇問題。

圖3 螞蟻隨機選擇的路徑

在這個模型中，K個節點代表著K個用戶，上下兩條路徑分支上的節點分別代表第K個用戶的數據+1和-1，螞蟻按照一定的概率確定下一個節點是上面的節點還是下面的節點，每個螞蟻走完規定的節點數K就得到一條路徑。如下所示的是螞蟻隨機選擇的兩條路徑:

路徑1:+1 +1 -1 +1 -1 +1…

路徑2:-1 -1 +1 -1 +1 -1…

1.2.2 蟻群算法的改進

本文從三個方面對蟻群算法進行改進:

(1) 為了使算法能夠更好更快的找到問題的最優解，對螞蟻初始路徑的尋找做出了干擾。通過在匹配濾波器的輸出做硬判決的值的這條路徑上放置更多的信息素使螞蟻趨向于選擇某些節點。其他路徑節點上信息素初值為一個正常數。

(2) 只給最優路徑上增加信息素。即使用精英螞蟻策略。每一次螞蟻選完路徑，根據一定的準則找出最優的幾條路徑，只給這幾條路徑的節點上增加信息素。這樣可以更好地利用螞蟻的正反饋信息更快的找到最優的路徑。

(3) 設定最小最大信息素值，既擴大蟻群的搜索范圍又不會很快陷入局部最優。

1.2.3 算法描述及步驟

(1) 蟻群算法初始參數設置，根據用戶數設定螞蟻個數及迭代個數，信息素揮發系數，初始信息素常數等;

(2) 計算節點上信息素的量，根據式(3)計算選擇概率;

(3) 每個螞蟻根據選擇概率選擇自己的路徑;

(4) 完成路徑選擇之后調整每個節點的信息素量在設定的范圍之內;

(5) 給最優路徑上增加信息素;

(6) 信息素揮發;

(7) 判斷最大循環次數是否大于設定最大次數，是，繼續;否，進入步驟(2);

(8) 所有經過路徑中的目標函數最大值作為全局最優解。

2 仿真結果及分析

本文在MC-CDMA系統上行鏈路同步的條件下所做的仿真。調制方式采用BPSK;16倍的Walsh碼進行擴頻時系統有16個用戶;32倍的Walsh碼進行擴頻時系統有32個用戶;信道為慢衰落的瑞利信道。

圖4為16個用戶時候傳統匹配濾波器(CD)，最小均方誤差多用戶檢測(MMSE)和蟻群算法多用戶檢測(ACO)的誤碼率性能比較。

圖4 誤碼率性能比較(一)

圖5為32個用戶時候傳統匹配濾波器(CD)，最小均方誤差多用戶檢測(MMSE)和蟻群算法多用戶檢測(ACO)的誤碼率性能比較。

圖4和圖5是用戶數分別為16和32的時候的傳統匹配濾波器(CD)，最小均方誤差多用戶檢測(MMSE)和蟻群算法多用戶檢測(ACO)的誤碼率性能比較。可以看到在信噪比大于6 dB時候蟻群算法的誤碼率性能比MMSE好很多，在信噪比較小的時候二者性能相差無幾，但都比傳統的匹配濾波器的性能好。誤碼率10-3時候蟻群算法多用戶檢測性能比最小均方誤差性能改善了約3.5 dB，而且通過增加改變蟻群算法中螞蟻個數和螞蟻搜索最大代數，還可以再改善誤碼率的性能。蟻群算法的參數設置是根據多次試驗的結果最適合的配置在表1中列出。

圖5 誤碼率性能比較(二)

表1 蟻群算法的參數設置

揮發系數初始信息素啟發信息素最大/最小信息素量精英螞蟻個數

0.256610/05

其中螞蟻個數是用戶數的2倍，16個用戶數時候搜索次數是20，32個用戶時候搜索次數是30。與最優多用戶檢測進行比較，最優檢測器的復雜度在16個用戶時候是216，而蟻群算法的復雜度[6]是16×2×20=640，蟻群算法的復雜度是最優檢測器的復雜度的640/216= 9.8×10-3 。在32個用戶時候最優檢測器的復雜度是232，蟻群算法的復雜度是最優檢測器的復雜度的32×2×30/232=4.5×10-7。通過試驗表明蟻群算法用于多用戶檢測不僅可以減少復雜度，而且可以獲得很好的性能，具有很大的實用價值。

3 結 語

本文首先對MC-CDMA系統中最優多用戶檢測方法做出了簡要的分析，然后引入了蟻群算法多用戶檢測，并對蟻群算法和其他多用戶檢測性能做了比較。結果表明蟻群算法性能優于最小均方誤差多用戶檢測，并且和最優多用戶檢測復雜度比值低于10-3數量級以上，隨著系統中用戶數的增多其復雜度并不呈指數增加而是線性增加。因此蟻群算法多用戶檢測在MC-CDMA系統多用戶檢測的應用中表現出了很大的優勢，在系統用戶數很多時可以達到實時實現的目標。

參考文獻

[1]尹長川， 羅濤， 樂光新. 多載波寬帶無線通信[M]. 北京: 北京郵電大學出版社， 2004.

[2]欒英姿， 李建東， 楊家瑋. MC-CDMA系統采用多用戶檢測器的性能分析[J]. 華東理工大學學報， 2003(2): 185-190.

[3]DUA A， DESAI U B， MALLIK R K. Minimum probability of errorbased methods for adaptive multiuser detection in multipath DS-CDMA channels\\. IEEE Trans. on Wireless Commun.， 2004， 3(3):939-948.

[4]WANG S，J I X. New ant colony optimization for optimum multiuser detection problem in DSCDMA systems[C]. Heidelberg: ISICA， 2007.

[5]DORIGO M， BIRATTARI M， STUTZLE T. Ant colonyoptimization[J]. IEEE Computional Intelligence Magazine， 2006， 11: 28-38.

[6]LAIN J K，LAI J J. Ant colony optimisation-based multi-user detection for direct-sequence CDMA systems with diversity reception Communications\\. IET Commun.， 2007， 1(4): 556-561.

[7]HIJAZI SL， NATARAJAN B，DAS S. An ant colony algorithm for multi-user detection in wireless communication systems [C]. Washington: Proc. Conf. Genetic and Evolutionary Computation，2005.

[8]李士勇. 蟻群算法及其應用[M]. 哈爾濱: 哈爾濱工業大學出版社， 2004.

[9]段海濱. 蟻群算法原理及其應用[M]. 北京: 科學出版社， 2005.

[10]王彩蕓， 蔡樂才. 基于蟻群算法與中心比對算法的多序列比對研究\\. 現代電子技術， 2009， 32(12): 85-87.