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

2、的模擬退火進化規劃檢測器。 關鍵詞：CDMA；多用戶檢測器；模擬退火；進化規劃中圖分類號：TN914.53文獻標識碼：A國家標準學科分類代碼：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 引 言碼分多址是近年來用于數字蜂窩移動通信的一種先進的無線擴頻通信技術。然而多址干擾及由它引起的遠近效應卻成為制約其發展的致命瓶頸1。克服多址干擾最根本方法是尋找完全正交的地址碼。然而在異步信道中, 隨著用戶數增加, 要找到這樣的地址碼是極為困難。于是人們開始研究各種多用

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

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

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

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

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

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

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

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

15、t從圖4和圖5可以看到, 基于模擬退火并行進化規劃的多用戶檢測器無論在多址干擾還是在遠近效應存在的條件下, 其收斂速度優于基于單種群的模擬退火進化規劃檢測器。5 結 論本文構造了模擬退火并行進化規劃的多用戶檢測器, 通過上述分析比較得出：模擬退火并行進化規劃的多用戶檢測器在抗多址干擾性能和抗遠近效應性能都優于基于單種群的模擬退火進化規劃檢測器的檢測性能, 并且新的檢測器能夠快速收斂。參考文獻：1 尤肖虎. 第三代移動通信系統發展現狀與展望J. 電子學報, 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.電子測量與儀器學報, 2007, 21(4): 108-111.XU L F, HU M. Multi-user detector based on parallel evolutionary programmingJ. Journal of Electronic