基于模擬退火的并行進(jìn)化規(guī)劃多用戶檢測算法

1、基于模擬退火的并行進(jìn)化規(guī)劃多用戶檢測算法許良鳳 丁志中 趙 燁(合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院通信所, 合肥 230009)摘 要：模擬退火和多種群并行進(jìn)化規(guī)劃是2種較好的改進(jìn)進(jìn)化算法性能的方法。將這2種思想有機(jī)地結(jié)合起來, 提出了一種基于模擬退火的并行進(jìn)化規(guī)劃多用戶檢測算法。在該算法中, 進(jìn)化在多個(gè)不同的子群中并行進(jìn)行, 利用模擬退火算法的爬山性能, 避免單種群進(jìn)化過程中出現(xiàn)的過早收斂現(xiàn)象, 提高整個(gè)算法的收斂速度。仿真結(jié)果表明, 這種新的多用戶檢測算法抗多址干擾和抗遠(yuǎn)近效應(yīng)能力都優(yōu)于單種群的模擬退火進(jìn)化規(guī)劃多用戶檢測算法, 并且在多址干擾和遠(yuǎn)近效應(yīng)存在的條件下, 其收斂速度明顯優(yōu)于基于單種群

2、的模擬退火進(jìn)化規(guī)劃檢測器。 關(guān)鍵詞：CDMA；多用戶檢測器；模擬退火；進(jìn)化規(guī)劃中圖分類號(hào)：TN914.53文獻(xiàn)標(biāo)識(shí)碼：A國家標(biāo)準(zhǔn)學(xué)科分類代碼：510.50Multi-user detection algorithm based on simulated annealing parallel evolutionary programmingXu Liangfeng Ding Zhizhong Zhao Ye(School of Computer and Information, Hefei University of Technology, Hefei 230009)Abstract: Simu

3、lated annealing and multi-group parallel evolutionary programming are two helpful methods which can improve the performance of evolutionary algorithm. The two ideas are well combined a new multiuser detection, that is the parallel evolutionary programming algorithm based on simulated annealing, is p

4、roposed in the paper. In the algorithm, the evolutions of subgroup is performed in parallel with the hill climbing performance of simulated annealing, so this algorithm can avoid the premature convergence of the alone group evolutionary process and improves the convergence speed of the algorithm. Th

5、e simulation results show that the new algorithm not only is superior to the multi-user algorithm based on the alone group simulated annealing evolutionary programming, but also can faster convergence than the detector based on the alone group simulated annealing evolutionary programming in the term

6、s of multiple-access interfere and near-far resistance.Keywords: code division multiple access; multi-user detector; Simulated annealing; evolutionary programming1 引 言碼分多址是近年來用于數(shù)字蜂窩移動(dòng)通信的一種先進(jìn)的無線擴(kuò)頻通信技術(shù)。然而多址干擾及由它引起的遠(yuǎn)近效應(yīng)卻成為制約其發(fā)展的致命瓶頸1?？朔嘀犯蓴_最根本方法是尋找完全正交的地址碼。然而在異步信道中, 隨著用戶數(shù)增加, 要找到這樣的地址碼是極為困難。于是人們開始研究各種多用

7、戶檢測方法來克服或減輕多址干擾和遠(yuǎn)近效應(yīng)2。近年來許多學(xué)者提出了一系列基于遺傳算法3和神經(jīng)網(wǎng)絡(luò)等智能算法的多用戶檢測器4, 這些方法都可使計(jì)算復(fù)雜度有較大下降, 性能也優(yōu)于傳統(tǒng)檢測器。但都存在著一些不足如收斂速度問題。進(jìn)化計(jì)算是一種模擬自然進(jìn)化過程的隨機(jī)優(yōu)化方法。進(jìn)化規(guī)劃5是進(jìn)化計(jì)算中的代表算法之一, 但大量的研究證明, 該算法存在的缺點(diǎn)6是進(jìn)化容易出現(xiàn)過早收斂, 從而陷入局部極值點(diǎn), 即早熟現(xiàn)象; 進(jìn)化后期, 個(gè)體之間的競爭趨于緩慢因而導(dǎo)致算法后期的搜索效率降低。針對這些弱點(diǎn)利用進(jìn)化規(guī)劃能全局尋優(yōu)的優(yōu)勢和模擬退火算法的爬山性能設(shè)計(jì)了基于模擬退火的并行進(jìn)化規(guī)劃多用戶檢測算法, 在該多用戶檢測算

8、法中, 一方面利用了并行進(jìn)化規(guī)劃將并行計(jì)算機(jī)的高速并行性和進(jìn)化規(guī)劃天然并行性相結(jié)合, 極大地提升了進(jìn)化規(guī)劃的求解速度和質(zhì)量; 另一方面通過Boltzmann機(jī)制來接收子代, 這樣做有利于優(yōu)良個(gè)體的保留。隨著進(jìn)化過程的進(jìn)行, 溫度逐漸下降, 接收劣質(zhì)解的概率逐漸減小, 即利用模擬退火算法的爬山性能提高整個(gè)算法的收斂速度。仿真結(jié)果表明, 該檢測算法在抗多址干擾的能力和抗遠(yuǎn)近效應(yīng)的能力優(yōu)于單種群的模擬退火進(jìn)化規(guī)劃檢測算法, 收斂速度更快。文中著重于同步CDMA系統(tǒng)的研究。2 CDMA系統(tǒng)接收模型假設(shè)一個(gè)CDMA通信系統(tǒng)的用戶數(shù)為K, 傳輸信道為高斯信道。則基站接收到的信號(hào)為：(1)式中: 和Ak分別

9、是第個(gè)用戶發(fā)送的 信息比特和信號(hào)幅度, T是碼元間隔, 是第個(gè)用戶的特征波形, n(t)是具有單位功率譜密度的加性高斯白噪聲。同步高斯信道K個(gè)用戶匹配濾波器輸出為(2)將式(1)代入式 (2) 并寫成向量形式, 即 y=RAb+n式中: 是不同用戶擴(kuò)頻波形的相關(guān)矩陣, 為用戶信息向量, n為高斯白噪聲向量。最佳多用戶檢測就是采用最大似然序列估計(jì)為準(zhǔn)則找出一個(gè)接收信號(hào)序列, 使給定輸出序列的似然函數(shù)最大, 最佳多用戶檢測器輸出向量為7 (3)式中: H= ARA。3 基于模擬退火并行進(jìn)化規(guī)劃的多用戶檢測算法并行進(jìn)化規(guī)劃主從處理器的結(jié)構(gòu)圖如文獻(xiàn)8所示。由式(3)可知, 多用戶檢測是一個(gè)組合優(yōu)化問題

10、, 結(jié)合模擬退火及并行進(jìn)化規(guī)劃特點(diǎn), 提出一種基于模擬退火并行進(jìn)化規(guī)劃的CDMA多用戶檢測問題的優(yōu)化處理方法。每個(gè)處理器運(yùn)行的模擬退火進(jìn)化規(guī)劃的主循環(huán)詳細(xì)流程圖如圖1所示。圖1 每個(gè)處理器運(yùn)行的模擬退火進(jìn)化規(guī)劃的主循環(huán)流程圖Fig. 1 Main loop flow chart of each processor movement based on simulated annealing evolutionary programming3.1 適應(yīng)度函數(shù)定義解空間稱為一種群體, 為種群的規(guī)模。x中的任意一個(gè)元素稱為染色體, xi中的或-1, 稱為基因, K為用戶數(shù)。多用戶檢測問題的目標(biāo)就是要獲

11、得使達(dá)到最大時(shí)的xi值, 因此代價(jià)函數(shù)應(yīng)為 (4)為了保證個(gè)體的適應(yīng)度是正值,由代價(jià)函數(shù)所構(gòu)造的適應(yīng)度函數(shù)為 (5)3.2 編 碼由于多用戶檢測器的輸出是雙極性信號(hào)(+1和 -1), 所以不需要編碼。3.3 種群初始化為了加速收斂速度和減小計(jì)算復(fù)雜度, 將傳統(tǒng)檢測器的輸出作為初始種群的一個(gè)個(gè)體, 其余個(gè)體從解空間中隨機(jī)產(chǎn)生。3.4 變 異對子種群中的個(gè)體進(jìn)行高斯變異得到N個(gè)新個(gè)體式中 Nk (0,1)是均值為0, 方差為1的高斯隨機(jī)變量。3.5 選 擇將變異前的個(gè)體和變異后的子代組成臨時(shí)種群, 并計(jì)算臨時(shí)種群中2N個(gè)個(gè)體的適應(yīng)度函數(shù), 使用隨機(jī)q競爭法則, 選取排在前面N個(gè)個(gè)體組成新的種群作為

12、下一代進(jìn)化的初始種群。4 實(shí)驗(yàn)結(jié)果與分析討論一個(gè)12個(gè)用戶的同步DS-CDMA通信系統(tǒng), 假設(shè)擴(kuò)頻序列采用31位Gold序列, 采用高斯信道, 并用MATLAB軟件進(jìn)行仿真。實(shí)驗(yàn)中, 模擬退火的并行進(jìn)化規(guī)劃的參數(shù)如下：從處理器的個(gè)數(shù)為2, 每個(gè)從處理器處理種群的個(gè)體總數(shù)為8, 變異概率為, 溫度冷卻系數(shù)=0.9, 退火初始溫度T=999, 每個(gè)用戶發(fā)送5 000個(gè)bit。4.1 嚴(yán)格功率控制下的誤碼率的檢測在嚴(yán)格功率控制下, 接收到所有用戶的功率相同, 并選擇每一個(gè)用戶信噪比(SNR)從-6 dB增加到4 dB來比較基于模擬退火并行進(jìn)化規(guī)劃的多用戶檢測器和基于單種群的模擬退火進(jìn)化規(guī)劃檢測器在不

13、同信噪比下的誤碼率(BER)情況, 結(jié)果如圖2所示。圖2 功控下的誤碼率Fig. 2 BER under power control由圖2可以看到, 本文方法的抗誤碼性能比基于單種群的模擬退火進(jìn)化規(guī)劃檢測器好。4.2 抗遠(yuǎn)近效應(yīng)能力實(shí)驗(yàn)參數(shù)：設(shè)定第二個(gè)用戶的信噪比(SNR2)從6 dB增加到4 dB, 其他用戶的SNR固定在6 dB, 來比較不同檢測器抗遠(yuǎn)近效應(yīng)能力, 結(jié)果如圖3所示。由圖3可以看到, 本文方法的抗遠(yuǎn)近干擾性能比基于單種群的模擬退火進(jìn)化規(guī)劃檢測器好。圖3 遠(yuǎn)近效應(yīng)下的誤碼率Fig. 3 BER comparison of near-far effect4.3 收斂速度在考察算法

14、的收斂速度時(shí), 最大的迭代代數(shù)設(shè)為50。首先考察在嚴(yán)格功率控制下, 所有用戶的信號(hào)功率相等, 信噪比為-2dB, 不同的迭代次數(shù), 基于模擬退火并行進(jìn)化規(guī)劃的多用戶檢測器和基于單種群的模擬退火進(jìn)化規(guī)劃檢測器的誤碼率和迭代次數(shù)的關(guān)系如圖4所示。圖4 功控下的收斂曲線Fig. 4 Convergent curve of power control在遠(yuǎn)近效應(yīng)下, 除了用戶1其他用戶設(shè)為干擾用戶, 目標(biāo)用戶的信噪比為-2dB, 干擾用戶功率相同, 用戶1的誤碼率和迭代次數(shù)的關(guān)系如圖5所示。圖5 遠(yuǎn)近效應(yīng)下的收斂曲線Fig. 5 Convergent curve under near-far effec

15、t從圖4和圖5可以看到, 基于模擬退火并行進(jìn)化規(guī)劃的多用戶檢測器無論在多址干擾還是在遠(yuǎn)近效應(yīng)存在的條件下, 其收斂速度優(yōu)于基于單種群的模擬退火進(jìn)化規(guī)劃檢測器。5 結(jié) 論本文構(gòu)造了模擬退火并行進(jìn)化規(guī)劃的多用戶檢測器, 通過上述分析比較得出：模擬退火并行進(jìn)化規(guī)劃的多用戶檢測器在抗多址干擾性能和抗遠(yuǎn)近效應(yīng)性能都優(yōu)于基于單種群的模擬退火進(jìn)化規(guī)劃檢測器的檢測性能, 并且新的檢測器能夠快速收斂。參考文獻(xiàn)：1 尤肖虎. 第三代移動(dòng)通信系統(tǒng)發(fā)展現(xiàn)狀與展望J. 電子學(xué)報(bào), 1999, 27: 1-10.YOU X H. A perspective of the third generation mobile c

16、ommunications systemJ.  Acta Electronica Sinica, 1999, 27: 1-10.2 BELLLCORE S M. Multiuser detection for DS-CDMA communicationsJ. IEEE Communications Magazine, 1996, 34(10): 124-135. 3 ERGUN C, HACIOGLU K. Multiuser detection using a genetic algorithm in CDMA communications systemJ. IEEE Trans.

17、 Communications, 2000, 48(8): 1374-1383.4 KECHRIOTIS G, MANOLAKOS E S. Hopfield neural network implementation of the optimal CDMA multiuser detectorJ. IEEE Trans. on Neural Networks, 1996, 7(1): 131-141.5 LIM H S, RAO M V C, TAN A W C, et al. Multi-user detection for DS-CDMA systems using evolutiona

18、ry programmingJ. IEEE Communications Letters, 2003, 7(3): 101-103.6 YAO X, LIU Y, LIN G. Evolutionary programming made fasterJ. IEEE Transactions on Evolutionary Computation, 1999, 3(2): 82-88.7 VERDU S. Minimum probability of error for asynchronous gaussian multiple access channelsJ. IEEE Transaction on Information Theory, 1986, 32(1) :85-96.8 許良鳳, 胡敏. 基于并行進(jìn)化規(guī)劃的多用戶檢測器J.電子測量與儀器學(xué)報(bào), 2007, 21(4): 108-111.XU L F, HU M. Multi-user detector based on parallel evolutionary programmingJ. Journal of Electronic