一種改進的基于禁忌搜索算法的空時多用戶檢測技術

摘要：本文致力于計算智能方法在多用戶檢測中的應用研究。探討了禁忌搜索(TS)算法，為了能更有效的減輕延時擴展及多徑衰落，改進CDMA移動通信系統的容量和質量，進一步降低誤碼率，提出一種改進的基于禁忌搜索算法的空時多用戶檢測。該算法具有較低的復雜度和良好的誤碼率性能，易于工程實現，并給出了相應的計算機仿真結果。

關鍵詞：多用戶檢測；碼分多址；空時處理；禁忌搜索

Abstract: Study of an improved space-time multiuser detection technology based on tabu search

This paper is dedicated to the application of computational intelligence methods to solve the difficult issue of MUD design. researching tabu search algorithm， In order to alleviate effectively delay and multiway decline ，improving effectively capacity and quality of CDMA communication system， depress further BER， proposing an improved space-time multi-user Detection algorithm based on tabu search algorithm. This new algorithm has lower complexity and lower BER， and is prone to project implement.

Keywords: Key words：Multi-user Detection; CDMA; Space-Time Processing; Tabu Search

引言

最優多用戶檢測算法是Verdu于1986年提出來的。這種檢測器可以達到理論上的最小錯誤概率，并且具有最優越的抗遠近能力。它采用的是Bayes后驗概率最大的原理，是一種最大似然序列估計算法。最優多用戶檢測可以抽象為一個非線性組合優化問題，要求在用戶傳遞數據空間中，尋找一個最優越的數據組合，實現似然函數的最大化[1]。最優多用戶檢測己經被證明是NP完備問題。采用Verdu提出的方法，其計算復雜度隨著用戶數量增加成指數增長，這在工程上難以實現。因此人們試圖尋找到具有工程上可容忍計算復雜度的、能夠實現最優檢測全局尋優過程的方法。

1 信號模型

在DS-CDMA系統中假定第q個用戶的異步多徑數為Lq，則q第個用戶的發射機到基站天線陣的信道響應陣列矢量表示為：

(1)

其中，，為第q個用戶第l條多徑信號的信道衰減及對應DOA為θql的M維陣列響應矢量，，那么基站接收的信號寫成矢量形式為：

2 基于禁忌搜索算法的空時多用戶檢測

由文獻[5]可知，基于禁忌搜索算法的多用戶檢測技術得到了廣泛的研究，但是這些研究不能更有效的減輕延時擴展及多徑衰落，相較之下誤碼率也比較高。由于解相關多用戶檢測器(DEC)消除了各用戶信號間的多址干擾，因此它具有很優秀的抗遠近效應性能。但同時也增大了噪聲功率，導致它的比特誤碼率(BER)較高。

因此，本章提出了基于禁忌搜索算法的空時多用戶檢測技術，利用空時二維處理技術能有效的減輕延時擴展及多徑衰落，有效的改進CDMA移動通信系統的容量和質量，能進一步降低誤碼率，且有利于工程的實現。

對由參考文獻[2]可知，最優空時多用戶檢測方法就是選擇b使似然函數Ω(b)取最大化，似然函數Ω(b)表示如下：

在這里設任一用戶的最大多徑時延擴展為△個符號間隔，其中△是一個正整數，即：

(10)

綜合前面的分析，在這里我們提出基于禁忌搜索的解相關空時多用戶檢測器(TSDEC-STMUD)，檢測器的結構如圖1所示。

這里依據禁忌搜索原理，根據多用戶檢測的實際問題設計具體算法。TS算法要求從一個初始解開始，每次迭代產生一個新的解，有限次迭代后，所有解中最好的一個作為最后的結果。因此首先我們需要選擇初始解，應用TS算法可以用圖1中的解相關檢測器的輸出作為y的值。很明顯，為了不增加額外的處理負擔并且能較快地收斂至最優解，我們可以直接選擇解相關檢測器輸出所得解sign(y)作為初始值b0。

TSDEC-STMUD多用戶檢測器的檢測性能很大程度上取決于使用的禁忌搜索算法的檢測性能，根據CDMA通信系統及其信號的特點，TS算法有關問題設計如下[3，4]:

(1)初始點的選擇：采用解相關多用戶檢測器的輸出作為初始點；

(2)鄰域的設計：在每次迭代中，新的解從當前解的鄰域中產生，因此鄰域的選擇非常重要，鄰域的選擇方式直接影響到算法搜索的有效性。針對多用戶檢測的實際問題，根據CDMA通信系統的信號的雙極性特性，解是由+1和-1組成的向量，所以，我們可以采用漢明距（即兩碼組各對應位不相同碼元的位數）來度量向量之間的距離。在MUD問題中，我們選擇與解 的漢明距為1的所有碼組的集合為 的鄰域[5]，即

(11)

這里，dH為漢明距。這樣的鄰域選擇方式使得搜索能夠沿著與最優解的漢明距越來越小的方向進行。

(3)評價函數：在TSDEC-STMUD多用戶檢測器中，我們采用代價函數作評價函數。即評價函數為p(b)，代價函數為C(b)，則評價函數為p(b)=C(b) (12)

CDMA多用戶檢測中的代價函數為：

(13)

(4)更新當前解：設當前最優解為best鄰域中滿足禁忌要求且評價值最佳的局部最優解為bnext，如果p(bnext)>p(bbest)，則bbest=bnext，否則bbest=bbest 。

(5)禁忌表設計：在TS-STMUD多用戶檢測器中，禁忌對象是解的簡單變化，即若記禁忌鄰域中滿足禁忌要求且評價值最佳的局部最優解為bnext，則禁忌表記錄的是選出的局部最優解=bnext。

(6)禁忌長度:即被禁對象不允許被選取的迭代次數。由于禁忌對象選取的是解的簡單變化，這種變化引起的被禁對象的范圍是很小的，故算法中對象一旦被禁則不允許解禁。

(7)終止規則:設定一個較大的正常數N，經過N次迭代后則算法停止搜索。

為避免迭代過程的循環，對當前迭代，過去所有得到的解均是被禁忌（tabu）的，因此禁忌表是變長的，隨迭代次數增加不斷增長。另外，由于解空間是由離散的解構成，因此我們在每次迭代中是直接將新產生的解放入禁忌表中，禁忌表中的解均被訪問過，故此時我們將不再考慮藐視準則，即為空集。

若采用有限次迭代次數為N0的算法流程為：

bTSD為禁忌搜索空時多用戶檢測的結果。

在上面采用的鄰域中，當用戶數較少的情況下可以適用，但當用戶數較多時此鄰域結構就不在適用，這是因為前面的鄰域設置只是允許有一個用戶的數據出錯，而多個數據不能同時出錯，所以當用戶數較多時，上面提出的鄰域結構將不在適用。因此本文對鄰域結構提出了改進，直接采用用戶數作為鄰域中漢明距的界限，即：

(14)

在每次迭代中，都要產生漢明距為1，2，…，的解向量作為鄰域空間。要比文獻[5]提出的鄰域要合理。

3 算法復雜度分析

采用禁忌搜索檢測方法，需要確定迭代次數N0。在多用戶檢測問題中，迭代次數N0與解空間的規模有關。解空間中共有2NQ個點，故N0的選擇與維數NQ有關。設N0=aNQ，a可以取一個正常數。在第j次迭代中，首先需要確定bj-1的鄰域中的NQ個點，然后與集合{b0，b1，……，bj-2}中的點進行比較以判斷鄰域中哪些點禁止搜索，比較次數為（j-1）NQ，共有N0次迭代，總的比較次數為。在第j次迭代中，如果有tj個點被禁止搜索，則將其排除并對剩下(NQ-tj)個點分別計算目標函數值，求最好的一個作為bj，總的計算數為。分析可知，計算復雜度為：

(15)

4 仿真與分析

在仿真實驗中，我們對前面提出的基于禁忌搜索的空時多用戶檢測算法進行計算機仿真。假定仿真CDMA系統用戶數Q=6，每個用戶到達天線陣有4條可分的多徑，每條多徑包絡均服從瑞利分布，通過偽隨機m序列產生每個用戶的擴頻碼，且每個用戶的擴頻增益為K=31。用戶比特數據隨機產生，且每個用戶的DOA均勻分布在[0，2π]。基站采用線性天線陣，陣元數為M，陣元間距d為半個波長。由于每個用戶多徑增益的強度不等，故接收到的信號功率也不相等，從而造成的誤碼率特性也有差異。

圖2是用戶數為1時誤碼性能隨迭代次數增加的收斂曲線，由圖可知，誤碼率隨著迭代次數的增加具有穩定的收斂性。在仿真中選擇使收斂曲線趨于穩定的迭代次數，故選擇N0=18。

圖3是當陣元數M=4用戶數Q=6時空時匹配濾波檢測、空時解相關檢測和改進的基于禁忌搜索的空時多用戶檢測的誤碼率隨輸入信噪比的關系曲線。由圖可知，改進的基于禁忌搜索算法的空時多用戶檢測具有良好的檢測性能。

圖4是當陣元數M=1、4、8用戶數Q=10時基于禁忌搜索的空時多用戶檢測誤碼率隨輸入信噪比的關系曲線。可以看出，本章提出的改進的基于禁忌搜索的空時多用戶檢測具有良好的檢測性能，同時采用天線陣比單個天線性能也要好得多，從而驗證了本章推出的改進的基于禁忌搜索的空時多用戶檢測算法。

5結論

本文基于禁忌搜索原理和多用戶檢測的具體問題. 提出了一種改進的基于禁忌搜索算法的空時多用戶檢測器，該算法具有較低的復雜度，即:具有多項式的計算復雜度，有良好的抗遠近效應的能力，有良好的誤碼率性能，易于工程實現。并給出了相應的計算機仿真結果。

參考文獻

[1]S.Verdu，\"Minimum Probability of Error for Asynchronous Gaussian Multiple access Channels\".IEEE Trans on IT，Jan 1986:85-96P

[2]Xiaodong wang，H.Vincent Poor．無線通信系統-信號接收與處理的高級技術[M].北京：電子工業出版社，2005：179-227頁．

[3]王 凌．智能優化算法及其應用[M]．北京：清華大學出版社，2004：62-82頁．

[4]Cvijovic D，Klinowski，J.Tabu Search:An Approach to the Multiple Minima Prohlean[J].Science，1995，267(2):664-666.

[5]溫萬惠，劉光遠.一種基于可變禁忌長度的多用戶檢測方法[J].信號處理，2005，Vol.21.No.4.389-391．