基于改進(jìn)的模擬退火算法的頻譜受限序列設(shè)計(jì)

趙 琴，李旭東

(西華大學(xué) 理學(xué)院，成都 610039)

在準(zhǔn)同步碼分多址(Quasi-Synchronous Code-Division Multiple-access，QS-CDMA)系統(tǒng)中，影響其性能的是零時(shí)延附近的部分?jǐn)U頻序列相關(guān)函數(shù)[1]，其自相關(guān)性決定了多徑干擾，互相關(guān)性決定了多址干擾。擴(kuò)頻序列要求在同步誤差范圍內(nèi)(零時(shí)延附近)具有理想的相關(guān)特性，零相關(guān)區(qū)(Zero-Correlation Zone，ZCZ)序列能夠滿足這樣要求。一般情況下，非周期序列設(shè)計(jì)比周期序列設(shè)計(jì)更加困難[2]，且具有良好非周期相關(guān)特性的序列通常也具有良好的周期相關(guān)特性，但反之則不一定成立。此外，為了避免非線性副作用并充分利用可用的傳輸功率，通常需要具有理想峰均功率比(Peak-to-Average Power Ratio，PAPR)特性的通信序列。然而，傳統(tǒng)的ZCZ序列(假設(shè)整個(gè)光譜帶的可用性)不能被使用，因?yàn)樗鼈兊牧己孟嚓P(guān)特性會(huì)被CR通道中的頻譜約束所破壞/丟失[3]。

認(rèn)識到這一設(shè)計(jì)挑戰(zhàn)，He等[4]采用數(shù)值方法設(shè)計(jì)認(rèn)知雷達(dá)系統(tǒng)中預(yù)定阻帶的低頻譜功率和低相關(guān)的單模序列。在此基礎(chǔ)上，Tsai等[5]利用凸優(yōu)化和GS(Gerchberg-Saxton)算法研究了低自相關(guān)和低PAPR的認(rèn)知序列。Liu等[6]通過在頻域上的凸優(yōu)化，給出了單通道和多通道頻譜受限序列集(Spectrum Constrained Sequences，SCSs)的周期性和非周期性相關(guān)下界，并指出一個(gè)未來的任務(wù)是構(gòu)造最優(yōu)的SCSs，這些SCSs具有一致低的自相關(guān)和互相關(guān)特性，無論是數(shù)值上還是分析上的都接近其導(dǎo)出的邊界值。然而，文獻(xiàn)[4-5]中的方法可能不適用于構(gòu)建具有低/零互相關(guān)性的認(rèn)知序列。到目前為止，具有低/零相關(guān)特性的認(rèn)知序列的系統(tǒng)構(gòu)造仍然是開放的。

本文在傳統(tǒng)的模擬退火算法[7]上利用線性遞減策略設(shè)置降溫函數(shù)，給出新的Metropolis更新準(zhǔn)則，提升算法的全局搜索能力；設(shè)計(jì)新的相位突變函數(shù)使算法具有自適應(yīng)性。從頻域角度出發(fā)，推導(dǎo)基于FFT的目標(biāo)函數(shù)，結(jié)合凸優(yōu)化算法，搜索具有低非周期自相關(guān)特性和低峰均功率比的單個(gè)頻譜受限序列。同時(shí)，還搜索了具有良好的非周期自相關(guān)特性和互相關(guān)特性的頻譜受限序列集。此外，本文還研究了序列長度和序列數(shù)目對算法性能的影響。

1 序列理論基礎(chǔ)

1.1 定義及基本性質(zhì)

其中0≤k≤N-1，(·)*表示復(fù)共軛。(n-k)N表示整數(shù)n-k模N。實(shí)際上，當(dāng)m1=m2時(shí)，Cmm被稱為非周期自相關(guān)函數(shù)(Aperiodic Autocorrelation Function，AACF)。類似地，Rmm被稱為周期自相關(guān)函數(shù)(Periodic Crosscorrelation Function，PACF)。非周期自相關(guān)和互相關(guān)函數(shù)統(tǒng)稱為非周期相關(guān)函數(shù)，周期自相關(guān)和互相關(guān)函數(shù)統(tǒng)稱為周期相關(guān)函數(shù)。

定義4(PAPR)單個(gè)序列x的峰均功率比定義為

性質(zhì)1一致低的周期自相關(guān)函數(shù)是一致低的非周期自相關(guān)函數(shù)的必要條件。

性質(zhì)2維納辛欽定理表明時(shí)域序列的PACF和功率譜是離散傅里葉變換對，時(shí)域序列x在時(shí)延τ處的PACF滿足Rx(τ)=FH(τ,:)r,τ∈{1,2,…,N-1}。

由性質(zhì)1知，序列的低AACF優(yōu)化問題可以轉(zhuǎn)化為序列的PACF的次優(yōu)化問題，這里使用周期自相關(guān)峰值旁瓣P(guān)SL′來衡量序列的AACF，即

(1)

這里FH(τ,:)表示IDFT矩陣FH的第τ行。

1.2 新的序列設(shè)計(jì)準(zhǔn)則

衡量序列x的相關(guān)性能好壞的常用度量為集成旁瓣水平ISL和峰值旁瓣水平PSL，前者側(cè)重考慮在任何時(shí)延處的序列相關(guān)性能的整體優(yōu)化，表示旁瓣總能量；后者側(cè)重考慮最大相關(guān)旁瓣對序列性能的影響，可用來評估序列相關(guān)旁瓣與其上界的接近程度[2]。在復(fù)雜電磁環(huán)境及QS-CDMA系統(tǒng)中，聯(lián)合優(yōu)化序列集的歸一化總自相關(guān)峰值旁瓣水平和歸一化總互相關(guān)峰值旁瓣水平作為SCSs設(shè)計(jì)準(zhǔn)則是更好的選擇。

1.3 約束條件

1.3.1 能量約束

1.3.2 頻譜約束

設(shè)標(biāo)記向量S=[S0,S1,…,SN-1]，該向量描述了每個(gè)子載波可用狀態(tài)，當(dāng)子載波被占用或需要避免時(shí)，Si=0；反之，則子載波可用，記為Si=1。記Ω為不可用子載波集合，其中Ω={k|Sk=0}，則定義頻譜約束為B(i)=0,i∈Ω，稱滿足上述條件的序列為頻譜受限序列，記為SCS。給定一組序列，如果每個(gè)序列都滿足頻譜約束，稱這樣的序列集為頻譜受限序列集，記為SCSs。

2 頻譜受限序列設(shè)計(jì)的優(yōu)化問題

2.1 具有低AACF和低PAPR的SCS優(yōu)化問題

給定單個(gè)頻譜受限序列x的頻域序列B，設(shè)計(jì)具有良好AACF的SCS旨在最小化非周期自相關(guān)峰值旁瓣P(guān)SL，此外，還期望獲得SCS的其他性能，比如PAPR，相應(yīng)的目標(biāo)函數(shù)分別為：

設(shè)懲罰因子為ρ，考慮聯(lián)合設(shè)計(jì)具有低AACF和低PAPR的單個(gè)SCS，其優(yōu)化問題如下：

(2)

上述優(yōu)化問題是基于快速傅里葉變換(FFT)的以N點(diǎn)頻域序列B為自變量的非線性多變量優(yōu)化問題，解空間為包含許多局部解的復(fù)空間，He等[8]提出了用局部最小化算法即CAN算法來設(shè)計(jì)無譜約束下的具有良好AACF的單模序列，故我們在此基礎(chǔ)上引入頻譜約束，從頻域角度提出了一種基于改進(jìn)的模擬退火的智能進(jìn)化算法來設(shè)計(jì)頻譜約束下的具有低AACF和低PAPR的認(rèn)知序列。

2.2 具有低ACF的SCSs的優(yōu)化問題

借鑒最優(yōu)化理論中最小最大化優(yōu)化問題的應(yīng)用背景：通過抑制最突出的成分來達(dá)到對整體的一個(gè)優(yōu)化，這在通信方面具有重要理論意義。因此，本文在優(yōu)化過程中，以一定權(quán)重λ(λ∈[0,1])同時(shí)優(yōu)化SCSs的歸一化總自相關(guān)峰值旁瓣水平APSL和歸一化總互相關(guān)峰值旁瓣水平CPSL，而不是直接優(yōu)化非周期集成旁瓣水平ISL。其優(yōu)化問題如下：

(3)

將上述SCSs設(shè)計(jì)問題表述為一個(gè)高階、多變量、非線性的約束優(yōu)化問題?？赏ㄟ^調(diào)整參數(shù)λ，來實(shí)現(xiàn)SCSs的自相關(guān)特性和互相關(guān)特性的權(quán)衡，當(dāng)λ>0.5時(shí)，SCSs設(shè)計(jì)問題更傾向于優(yōu)化其自相關(guān)特性。反之，上述優(yōu)化問題傾向于優(yōu)化SCSs的互相關(guān)特性。

3 SCSs設(shè)計(jì)算法

鑒于頻譜受限序列設(shè)計(jì)問題是一種非線性NP-hard問題，直接求解是很困難的，相比無譜約束下的迭代直接搜索序列設(shè)計(jì)算法思想，模擬退火算法更加適用于解決頻譜受限序列設(shè)計(jì)問題，是近年來求解復(fù)雜非線性多變量函數(shù)的最優(yōu)或近似最優(yōu)解的有力工具。而頻域序列最重要的2個(gè)特征是幅度和相位，因此可分2步走設(shè)計(jì)有效的算法來搜索任意頻譜受限序列的最優(yōu)幅度和最優(yōu)相位。

3.1 改進(jìn)的模擬退火算法

本文在傳統(tǒng)SA算法的基礎(chǔ)上，設(shè)計(jì)了動(dòng)態(tài)的降溫函數(shù)和靈活的相位點(diǎn)突變函數(shù)。經(jīng)查閱文獻(xiàn)和數(shù)值實(shí)驗(yàn)，發(fā)現(xiàn)傳統(tǒng)SA算法在前期遍歷解空間的范圍不夠大，導(dǎo)致后期搜索過程中沒有得到全局最優(yōu)解或近似解，對此，本文設(shè)計(jì)了新的Metroplis準(zhǔn)則：在預(yù)定義的迭代次數(shù)內(nèi)，以一定概率接受差解，充分遍歷解空間；在算法后期，不再接受差解。這樣不僅使算法具有逃脫局部極值和避免過早收斂的全局優(yōu)化能力，而且降低了時(shí)間復(fù)雜度。此外，在內(nèi)循環(huán)過程中增加記憶矩陣，找到內(nèi)循環(huán)過程中的最優(yōu)解以作為下次迭代的初始解，有效提高了全局解的質(zhì)量。改進(jìn)的模擬退火算法(Modified Simulated annealing，MSAA)如下：

1)動(dòng)態(tài)降溫函數(shù)：借用粒子群算法的線性權(quán)重遞減策略[10]，設(shè)計(jì)了靈活的降溫函數(shù)

其中T0為初始溫度，Tend為終止溫度，Time為總降溫次數(shù)，count為當(dāng)前迭代次數(shù)，T為下次迭代溫度。

2)相位點(diǎn)突變函數(shù)：在文獻(xiàn)[11]中，突變位的數(shù)目類似于步長。一種自適應(yīng)技術(shù)是在早期搜索過程中使用更多的變異位來提高搜索效率，并在以后的搜索過程中減少突變數(shù)，以達(dá)到足夠的精度[12]。如果突變數(shù)過小，特別的當(dāng)突變數(shù)為1時(shí)，搜索進(jìn)程較緩慢，不容易遍歷解空間跳出局部解，同樣突變數(shù)過大，則搜索可能退化成隨機(jī)搜索，本文在搜索過程中依目標(biāo)函數(shù)值變化構(gòu)建了具有自適應(yīng)的相位點(diǎn)突變函數(shù)，如下：

其中G為1到N-|Ω|中任意整數(shù)。

3)新解函數(shù)：本文采用替換操作為主新解函數(shù)，交換、翻轉(zhuǎn)操作為次新解函數(shù)，分別隔一定時(shí)間調(diào)用，不斷引入新個(gè)體，增加解的多樣性，擴(kuò)大全局搜索范圍。

3.2 非周期下SCSs的頻域序列的最優(yōu)相位優(yōu)化算法

序列的功率譜保留了頻域序列的幅度信息，利用文獻(xiàn)[13]的凸優(yōu)化算法最小最大化單個(gè)SCS的PACF，根據(jù)性質(zhì)1可以得到最優(yōu)功率譜，即頻域序列B的最優(yōu)幅度。本文主要有兩個(gè)設(shè)計(jì)任務(wù)，一是利用本文提出的MSAA算法搜索單個(gè)SCS的最優(yōu)相位。二是利用本文提出的MSAA算法搜索SCSs的最優(yōu)相位，除了初始化步驟不同外，其他步驟和單個(gè)SCS設(shè)計(jì)類似。MSSA算法的偽代碼如下：

輸入：(N,S,B0),Tend,count,iter,num

計(jì)算T0,Time

whileT>Tend

count=count+1

fori=1:iterdo

根據(jù)突變數(shù)和新解函數(shù)，計(jì)算新解B_sa

計(jì)算“突變”前后的目標(biāo)函數(shù)的變化量ΔE

在預(yù)定義迭代次數(shù)下

if ΔE≤0 then

B0=B_sa

else產(chǎn)生一個(gè)隨機(jī)數(shù)q=rand(0,1),P>q

B0=B_sa

end if

記錄內(nèi)循環(huán)下每次循環(huán)后的解和對應(yīng)的目標(biāo)函數(shù)值

end for

選取內(nèi)循環(huán)中最好的解B_best作為下次溫度迭代下的初始解，并記錄該最優(yōu)解B_best及對應(yīng)的目標(biāo)函數(shù)值E_best

end While

輸出：B，并利用N點(diǎn)DFT，得到頻譜受限序列SCSs，即對應(yīng)的時(shí)域序列集x

4 數(shù)值舉例

考慮先利用凸優(yōu)化算法最小化(1)式，得到SCS的最優(yōu)頻域幅度并固定其幅度，以(2)式中的E1為目標(biāo)函數(shù)，利用本文提出的MSAA算法來搜索SCS的最優(yōu)相位，假設(shè)SCS的序列長度為N=64，懲罰因子ρ=0.95，設(shè)子載波標(biāo)記向量為S=[114,06,120,08,116]，則Ω={14,…,19}∪{40,…,47}，多次運(yùn)行后的MSAA算法的優(yōu)化趨勢見圖1，將搜索到的SCS的AACF和PAPR與文獻(xiàn)[13]進(jìn)行比較見圖2。從圖1可以看出，MSAA算法是快速收斂且有效的，圖2顯示了SCS的時(shí)域、頻域幅度和AACF水平。與文獻(xiàn)[13]相比，本文提出的MSAA算法所優(yōu)化的AACF和PAPR都相對較好。為了更好地衡量SCS的AACF和PAPR，本文還探究了序列長度為N=25,…,210對序列設(shè)計(jì)結(jié)果的影響，并將MSAA算法和HL算法[13]生成的SCS的PSL和Welch界[14]、Liu界[5]進(jìn)行比較(圖3)，兩種算法下的SCS的PAPR與理想PAPR的比較見圖4。結(jié)果表明，MSAA算法性能隨著序列長度增大呈現(xiàn)良好穩(wěn)定的性能，但時(shí)間復(fù)雜度會(huì)升高。事實(shí)上，MSAA算法的優(yōu)點(diǎn)不僅在于設(shè)計(jì)的SCS具有較好的低相關(guān)性和低PAPR(使用不同初始化)，計(jì)算時(shí)間上也是可行的，且SCS的AACF與PAPR之間相互制約?？赏ㄟ^調(diào)節(jié)權(quán)重因子ρ的大小，改善序列的相關(guān)特性和PAPR。這些隨機(jī)分布的SCS在某些領(lǐng)域如QS-CDMA和信道估計(jì)中是有用的。由于算法全程都有FFT的參與計(jì)算，因此計(jì)算效率較高，且該算法對任意SCS的序列設(shè)計(jì)具有普適性，可以用來設(shè)計(jì)頻譜限制下的二進(jìn)制序列、多相序列、單模序列等。

此外，進(jìn)一步研究了優(yōu)化問題(3)，在序列數(shù)目為M=2，序列長度為N=25,…,210和序列數(shù)目為M=2,…,7，序列長度為N=64兩種參數(shù)設(shè)置下，利用本文提出的MSAA算法來設(shè)計(jì)具有低AACF和ACCF的SCSs，將其與文獻(xiàn)[5]中的頻譜受限下的非周期相關(guān)旁瓣理論界Liu界和Welch界進(jìn)行比較，分別見圖5、圖6，可以看出，隨著序列參數(shù)的變化，本文利用MSAA算法所優(yōu)化得到的SCSs都具有良好的AACF和ACCF，且都接近相關(guān)理論界。

此外，還研究了MSAA算法隨序列參數(shù)變化的性能即頻譜受限序列的相關(guān)下界的可實(shí)現(xiàn)性，這里主要通過計(jì)算時(shí)間來表現(xiàn)，具體情況見表1，當(dāng)序列長度較大時(shí)，MSAA的計(jì)算時(shí)間也是可行的，比傳統(tǒng)SA算法快得多，這在長序列的搜索上是一個(gè)很大的優(yōu)勢。

表1 MSAA和SA算法隨序列參數(shù)變化的運(yùn)行時(shí)間

5 結(jié) 論

由于頻譜政策的影響，傳統(tǒng)的ZCZ序列無法滿足認(rèn)知無線電系統(tǒng)，它在頻譜約束下的良好相關(guān)特性將會(huì)被破壞或丟失，基于此，為了實(shí)現(xiàn)無干擾的CR-CDMA通信，本文提出了一種基于改進(jìn)的模擬退火算法的全局優(yōu)化算法，聯(lián)合優(yōu)化單個(gè)SCS的AACF和PAPR兩大指標(biāo)，所提出的SCS很好地滿足Welch界和Liu界，具有較強(qiáng)的實(shí)用價(jià)值。該算法的時(shí)間復(fù)雜度與空間復(fù)雜度相對較低，不依賴于初始解，具有較好的魯棒性。此外，設(shè)計(jì)了具有低非周期自相關(guān)和互相關(guān)特性的SCSs以支持多用戶傳輸，研究了序列參數(shù)對MSAA算法性能的影響。數(shù)值實(shí)驗(yàn)證明該算法可行且高效。