李明陽，柏 鵬，彭衛(wèi)東，李淑婧

(1.空軍工程大學裝備管理與安全工程學院，陜西西安710051;2.空軍工程大學綜合電子信息系統(tǒng)與電子對抗技術研究中心，陜西西安710051)

0 引言

具有較好相關特性的序列集在擴頻通信［1］、多輸入多輸出(multiple input multiple output，MIMO)雷達［2］等系統(tǒng)中具有重要應用價值。文獻［3］基于進化機制生成了具有較低副峰的非周期二相序列，文獻［4-5］分別利用遺傳算法、粒子群算法、蜂群算法和模擬退火算法等生成適用于MIMO雷達的多相碼。研究表明，在整個移位周期范圍內，自相關副峰(autocorrelation sidelobe peak，ASP)和互相關峰(cross-correlation peak，CP)不能同時得到有效抑制［6］。文獻［7］提出的零相關區(qū)(zero correlation zone，ZCZ)序列不要求在整個移位周期范圍內具有理想的ASP和CP，相對于完全正交序列具有更加靈活的參數。文獻［8］將零相關區(qū)序列應用于MIMO雷達系統(tǒng)，獲得較高的距離分辨率和探測性能。類似地，低相關區(qū)序列集要求在一定范圍內具有較低的ASP和CP。LCZ和ZCZ序列的構造方法通常包括最優(yōu)化搜索方法［9-11］、交織方法［12，13］、代數方法［14］等。交織方法和代數方法依然受到較為嚴格的參數限制，無法生成任意長度的LCZ/ZCZ序列，最優(yōu)化搜索方法雖然不能生成理論最優(yōu)或次優(yōu)的序列，但可選參數更靈活。

本文將遺傳算法和禁忌算法相結合，提出一種低相關區(qū)序列集的智能搜索方法。該方法將禁忌算法嵌入到遺傳算法的變異操作中，設置變異位為禁忌對象，防止某位頻繁變異。進化過程中，根據當前全局最小的最大ASP和最大CP動態(tài)調節(jié)交叉點，使交叉點數隨全局ASP和CP的逐漸縮小而減少，從而在進化前期保證進化速度，在進化后期保證收斂。每一輪進化前檢驗序列的移位等價性，剔除移位等價序列，從而提高種群多樣性，防止早熟。最后，通過數值仿真證明了本文方法的有效性。

1 基本定義和定理

(1)式中，*表示對復數共軛運算。

類似地，序列集的周期相關函數定義為

如果i=j，(1)式和(2)式稱為序列xi的非周期/周期自相關函數，否則(1)式和(2)式稱為序列xi和xj的非周期/周期互相關函數。

定義2 對于定義1中的序列集X，如果X中任意2個序列相關函數滿足如下條件

則稱X為低相關區(qū)長度為ZLC的LCZ(P，L，M，ZLC，σa，σc)序列集。

(3)式中:P表示序列集的進制;σa和σc分別表示序列集的最大ASP和最大CP。

2 基于遺傳-禁忌算法的LCZ序列集搜索方法

2.1 問題的優(yōu)化模型

在LCZ序列集參數P，L，M和ZLC固定的條件下，σa和σc的絕對值越小，LCZ序列集的相關特性越好。以上參數固定條件下，搜索σa和σc的絕對值較小的問題可以歸結為求使(4)式中目標函數E最小的序列集X。

(4)式中，ωa，ωc為加權系數。如果 σa≠ σc，且σc/σa=λ，則取系數ωa=λ，ωc=1。

2.2 遺傳-禁忌混合算法搜索步驟

使(4)式最小化的序列集的求解是一個多元非線性NP問題，如果采用窮舉法，其計算量為2MLP。對于NP問題，一種可行的方法是利用智能算法獲得近似最優(yōu)解，遺傳算法和禁忌算法都是求解NP問題的啟發(fā)式算法。其中，遺傳算法具有較好的全局搜索能力，禁忌算法對初值的依賴較大，但是局部“爬坡”能力很強，將二者結合可以利用遺傳算法實現(xiàn)粗搜索，利用禁忌算法獲得更精確搜索。文獻［15］利用遺傳－禁忌混合算法獲得了相對于單純遺傳算法［10］更優(yōu)的搜索性能，但是該方法只是將遺傳算法和禁忌算法進行簡單的級聯(lián)，不能充分發(fā)揮2種算法的優(yōu)點。因為遺傳算法的局部搜索能力主要源自變異操作，所以本文中將禁忌算法嵌入到遺傳的變異操作中，將所有一點變異作為鄰域，在該鄰域內用禁忌算法搜索，從而提高變異的局部搜索能力。基于遺傳-禁忌混合算法LCZ序列集搜索方法的實現(xiàn)流程如圖1所示。

圖1 基于遺傳-禁忌算法搜索LCZ序列集的流程圖Fig.1 Flow chart of searching method of LCZ sequence set based on genetic-taboo algorithm

基于遺傳-禁忌混合算法LCZ序列集搜索方法實現(xiàn)步驟和關鍵技術如下。

1)編碼。采用P進制級聯(lián)編碼，用一個長度為ML的P進制序列表示一個序列集X。

2)初始化。假設種群數量為pop_size，則隨機產生pop_size個編碼序列，預先設定交叉概率pc和變異概率pm。

3)遺傳操作。

①選擇。假設第l個編碼序列的目標函數為El，按照輪盤賭選擇法，第l個編碼序列依概率遺傳到下一代。

②交叉。從種群中任意選擇2個編碼序列，假設2個相關序列對應位相等的位數為n+，對應位不等的位數為n－，對于P元序列最多需要變化(n+－n－)/(2lb P)位則有可能獲得最小的相關值。所以，從種群中任意選擇2個編碼序列，隨機選擇n個交叉點進行多點交叉。其中

③禁忌搜索。將種群中每個子序列的所有一點變異作為該序列的鄰域，利用禁忌算法進行搜索。設置變異點為禁忌對象，禁忌長度為LT。如果變異不被禁忌，則根據當前序列目標函數和變異序列目標函數的大小判斷是否變異。當且僅當禁忌表中對象的目標函數小于當前全局最優(yōu)解時，對當前禁忌解禁，更新禁忌表。

4)評估種群。利用(4)式評估種群。

5)結束判斷。智能算法收斂后目標函數將不再變化，所以可以假定目標函數保持不變后算法收斂。定義(4)式中目標函數跳變間隔為目標函數2個不相等值間隔的進化代數，設定跳變間隔的最大值，當超過該最大值仍不跳變則認為已經收斂到最優(yōu)解。根據經驗，本文中設定最大跳變間隔為進化代數的1/10。

6)剔除移位等價序列。為了消除移位等價序列［16］對種群多樣性的破壞，本文設計了快速剔除移位等價序列的方法。根據FFT變換的性質，序列及其循環(huán)移位序列具有相同的FFT包絡，所以對種群矩陣進行一維FFT變換，對相同包絡的序列只保留其中一個，然后將保留編碼序列組成新種群。

3 數值仿真及分析

選擇參數，設定M=4，L=40，P=4，低相關區(qū)Z=40，搜索非周期序列集，種群大小設為pop_size=200，進化代數為50，交叉概率為pc=0.3和變異概率為pm=0.03，禁忌長度為LT=5。所得到的序列集X={xii∈(0，1，2，3)}為

(5)式中，0—3分別表示相位{0，π/2，π，3π/2}。

表1 序列集的最大ASP和最大CPTab.1 Maximum ASP and CP of the sequence set

圖2 非周期自相關函數Fig.2 Aperiodic auto correlation function

序列集的相關副峰和互相關峰值最大值為0.175，相比文獻［15］中序列集的相關副峰和互相關峰值最大值為0.215 1，多址干擾更小。

設定M=1，其余參數不變，進化所得到的序列為x=(2，2，1，3，1，1，2，1，1，2，3，2，2，2，3，1，1，3，3，0，3，1，0，1，3，1，2，1，2，3，0，0，0，2，3，0，0，0，2，1)。

序列x自相關函數的最大副峰為0.05，可以在通信、定位系統(tǒng)中作為多相測距、同步碼使用。圖4為序列x的自相關函數曲線。

設定P=2，L=40，Z=40，搜索周期低相關區(qū)序列集，其余參數不變。進化所得到的序列集，按照16進制表示為

圖3 非周期互相關函數Fig.3 Aperiodic cross correlation function

圖4 非周期自相關函數Fig.4 Aperiodic auto correlation function

序列集X的周期最大ASP和最大CP如表2所示。

表2 序列集的最大ASP和最大CPTab.2 Maximum ASP and CP of the sequence set

在低相關區(qū)內，序列集Y的周期最大ASP和最大CP都為0.2。序列集X和Y的部分相關函數曲線如圖5所示。

圖5 不同低相關區(qū)序列的相關值對比Fig.5 Correlation comparison of different LCZ sequences

對比Z=40和Z=20時序列集的相關函數值，可以發(fā)現(xiàn)低相關區(qū)縮小后，最大ASP和最大CP由0.3降為0.2。所以適當地降低低相關區(qū)，可以一定程度上抑制序列自身和序列間干擾。

4 結束語

本文提出基于一種遺傳－禁忌混合算法的多相低相關區(qū)周期序列集的搜索方法。遺傳算法具有全局搜索能力，但是局部搜索性能相對較差;禁忌算法局部搜索能力很強，但是對初始解依賴較大。將二者結合可以取長補短，有效提高序列集搜索性能。

文中利用該方法對周期、非周期，二元以及多元序列集進行搜索，獲得了較好的效果。該方法具有一定的通用性，只需要相應改變目標函數即可滿足不同序列集的搜索需求。該方法對于QS－CDMA通信系統(tǒng)、MIMO雷達系統(tǒng)和測距系統(tǒng)中擴頻序列的設計具有一定理論意義和實用價值。

［1］曾凡鑫.適用于AS-CDMA系統(tǒng)的具有零(低)相關區(qū)的二元序列的數量擴張［J］.重慶郵電大學學報:自然科學版，2004，16(4):14-16.

ZENG Fanxin.Extension of family size of binary sequences with zero or low correlation zone for AS-CDMA system［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2004，16(4):14-16.

［2］FISHLER E，HAIMOVICH A，BLUM R，et al.Spatial diversity in radars-models and detection performance［J］.IEEE Transactions on Signal Processing，2006，54(3):823-838.

［3］SUKRU E K，ABDULLAH A.Binary Sequences With Low Aperiodic Autocorrelation for Synchronization Purposes［J］.IEEE Communications Letters，2003，7(1):36-37.

［4］LIU B，HE Z，ZENG J，et al.Polyphase orthogonal code design for MIMO radar systems［C］//IEEE.Processing of the International Conference on Radar.Shanghai:IEEE Press，2006:1-4.

［5］SUKRU E K，ABDULLAH A.Optimization of Orthogonal Polyphase Coding Waveform for MIMO Radar based on Evolutionary Algorithms［J］.Journal of Mathematics and Computer Science，2013，6(2):146-153.

［6］TANG X H，F(xiàn)AN P Z.Bounds on aperiodic and odd correlations of spreading sequences with low and zero correlation zone［J］.Electronics Letters，2001，37(19):1201-1203.

［7］FAN P Z，HAO L.Generalized orthogonal sequences their applications in synchronous CDMA systems［J］.IEICE Trans Fundamentals，2000，E83-A(11):1-16.

［8］XU L，LIANG Q.Zero Correlation Zone Sequence Pair Sets for MIMO Radar［J］.IEEE Transactions on Aerospace and Electronic Systems，2012，48(3):2100-2113.

［9］朱志華，葉飛，辛明軍，等.基于貓群優(yōu)化算法的2n周期優(yōu)秀二元序列的研究與分析［J］.電子與信息學報，2013，35(6):1365-1370.

ZHU Zhihua，YE Fei，XIN Mingjun，et al.The Research and Analysis of the Excellent 2nPeriodic Binary Sequence Based on Cat Swarm optimization［J］.Journal of Electronics＆Information Technology，2013，35(6):1365-1370.

［10］金明，廖桂生，李軍.基于遺傳算法的類零相關多相碼設計［J］.系統(tǒng)工程與電子技術，2010，32(1):14-17.

JIN Ming，LIAO Guisheng，LI Jun.Zero correlation zone like polyphase code design based on genetic algorithm［J］.System Engineering and Electronics，2010，32(1):14-17.

［11］YE L，LI C，QU L.A New Construction of Low-Correlation Zone Sequence Sets［C］//IEEE.8th International Conference on Wireless Communications，Networking and Mobile Computing(WiCOM).Shanghai:IEEE Press，2012:1-5.

［12］TANG X，F(xiàn)AN P Z，LINDNER J.Multiple binary ZCZ sequence sets with good cross-correlation property based on complementary sequence sets［J］.IEEE Transaction on Information Theory，2010，56(8):4038-4045.

［13］TU Y F，F(xiàn)AN P Z，LI H，et al.Construction of Binary Array Set with Zero Correlation Zone Based on Interleaving Technique［J］.IEICE Transaction on Fundamentals of Electronics，Communications and Computer Sciences，2011，94(2):766-772.

［14］JANG J W，KIM S H，NO J S.New Construction of Quaternary Low Correlation Zone Sequence Sets from Binary Low Correlation Zone Sequence Sets［J］.Journal of Communications and Networks，2010，12(4):330-333.

［15］王偉，趙俊杰，王輝.基于混合算法的MIMO雷達正交多相碼設計［J］.系統(tǒng)工程與電子技術，2013，35(2):294-298.

WANG Wei，ZHAO Junjie，WANG Hui.Design of orthogonal polyphase code for MIMO radar based on hybrid algorithm［J］.System Engineering and Electronics，2013，35(2):294-298.

［16］ZHOU Z C，PAN Z，TANG X H.A new family of optimal zero correlation zone sequences from perfect sequences based on interleaved technique［C］//IEEE.3rd International Workshop on Signal Design and its Applications in Communications(IWSDA).Chengdu:IEEE Press，2007:195-199.