隹Isl^iSls V1
2021年第02期
(总第218期)
韩露霜
(西华大学理学院，四川成都610039)
摘要：具有良好相关特性的多相序列是许多有源传感和通信系统的组成部分。由于该序列的搜索是一个非线性多变量的优化问题，寻高效的搜索方法至关重要。为了获得相关性好的多相序列，文章提出将具有全局优化能力的模拟退火算法引入到多相序列的搜索问题中。基本原理是为序列搜索建立适当的目标函数，调试出适当的退火和停止规则。通过大量对搜索性能和收敛参数进行的数值实验结果来看，文章显示采用模拟退火算法来设计具有良好相关性的多相序列是可行且有效的，特别是当优化问题的参数数量较大时。 关键词：多相序列；模拟退火；相关函数；优化算法；雷达信号设计
中图分类号:TN929.5文献标识码:B文章编号:2096-9759(2021)02-0052-04
Polyphase Sequence Search Based on Simulated Annealing Algorithm
Han Lushuang
(School of Science,Xihua University,Chengdu610039,China)
Abstract:Polyphase sequence with good correlation characteristics are an integral part of many active sensing and communication systems.Since the search of the sequence is a nonlinear multivariable optimization problem，社is very important to find an efficient search method.In order to obtain the polyphase sequence with good correlation,the paper introduces the simulated annealing algorithm with global optimization ability into the search problem of poly-phase sequence.The basic principle is to establish the appropriate objective function for sequence search and debug the appropriate annealing and stopping rules.Through a large number of numerical experiments on search performance and convergence parameters,the paper shows that it is feasible and effective to use simulated annealing algorithm to design polyphase sequence with good correlation,especially when the number of parameters of optimization problem is large
Key words:Polyphase sequence;Simulated annealing;Correlation function;Optimization algorithm;Radar signal design
现代雷达釆用脉冲压缩波形来获得目标探测所需的足够能量和所需的距离分辨率叫为了避免在强目标的旁瓣中遮挡小目标，减少相关多径或分布杂波的干扰。脉冲压缩波形的旁瓣(发射脉冲的自相关函数)应尽可能低叫低旁瓣相位编码波形可以提高雷达波形的灵活性，在多干扰、强杂波等情况下提高雷达的性能。 相位编码波形可分为二进制序列和多相序列。二进制码是雷达最常用的脉冲压缩信号之一，因为它具有信号生成和处理简单的m特性。然而，在相同码长情况下，多相信号比二进制信号具有更大的副瓣主峰值比。此外，多相波形具有更复杂的信号结构，因此，更难以被敌人的电子支援措施(ESMs)探测和分析。随着数字信号处理技术的成熟，多相信号的产生和处理变得越来越容易，成本也越来越低。因此，多相序列的设计已经逐步成为研究的重点，比如,Frank序列［4\Golomb 序列叭多相Barker序列冏等。也还有许多文献［7-9］釆用了一些其他先进算法来进行多相序列集的设计。为了评估相位编码波形的性能，最常用的指标是集成旁瓣水平(Integrated Sidelobe Level,ISL)和峰值旁瓣水平(Peak Sidelobe Level,PSL)<, ISL度量最小化的设计方法包括皿梯度下降法、基于快速傅里叶变换的新循环算法(Cyclic Algorithm-New,CAN)1111>单调最小化集成旁瓣水平嗣等。
然而，较长多相序列需要更大的相位选择范围，这使得穷举搜索的可能性不大。具有良好相关性的多相序列的合成是一个非线性多变量优化问题，通常很难解决。模拟退火(Simulated Annealing,SA)技术，由Kirkpatrick et al［131介绍，被证明是一个有效和强大的工具。如果应用得当，模拟退火是一种很有效的多变量优化算法。它是通过在成本函数中寻最小值和物质在能量最小化时改变状态的物理过程之间的类比而提出的。从著名的旅行商问题(Travel Agent Problem,TSP)和图划分问题，到VLSI设计、图像处理、生物和代码设计阿等工程问题，它被证明在广泛的应用中是成功且有效的。本文釆用一种有效的模拟退火算法来搜索具有良好相关性质的多相序列。
1模拟退火算法
在固态物理学的材料处理中，有一种称为退火的热处理方法。将该材料加热到熔点温度，然后使其缓慢冷却以达到结晶状态。在此过程中，固体内部自由能最小。SA算法是模拟此过程的一种组合优化算法。
在多参数组合优化问题中，将目标函数视为固体中的自由能存储，我们可以设计如下退火过程：首先，设置较大的人工温度参数(相当于熔点温度)。然后按照某些规则缓慢降低此参数，就像退火过程的温度缓慢降低一样。通过适当地控制该过程，目标函数收敛到最小或尽可能最小，该方法称为SA 算法。
收稿日期：2020-12-2］
作者简介：韩露霜(1996-)，女，研究生，主要研究方向：应用数学和无线通信。
52
美丽曲线
1.2数学描述
在多参数组合优化问题的求解过程中，将目标函数f 映射
为物质E 的状态能量。相对于物质分子结构的每个状态，优 化问题的每个可能解得到一简单描述一下这个过程：(s,f)表 示一个优化问题。i 和j 是这个问题的两个解，/<i)和/tj)是成
本因子。从i 到j 的接受标准由接收概率设计：个特殊的表述
i，其能量为E ”并施加扰动得到下一个表述j，其能量为E ”如
果Ej 小于E ”则接收场为能量状态，否则我们也可以根据一
定的概率来决定是否接收。这个标准叫做Metropolis 标准，这
个过程叫做Metropolis 过程。
简单描述一下这个过程：($,/>表示一个优化问题。i 和j
是这个问题的两个解，/<i)和/V )是成本因子。从i 到j 的接受 标准由接收概率设计：
i /(/)5)
其中T 是控制参数，在控制参数逐渐减小的条件下，SA
算法是Metropolis 过程的迭代。每个还原过程将产生L 个可
能的解，以形成长度为L 的马尔科夫链，因此每个控制参数(温
度)都有L 个Metropolis 过程。随着控制参数的减小，搜索范
围逐渐缩小，算法将停止直到满足收敛条件。
从SA 算法的数学描述可以看出，整个算法的操作数取决
于控制参数(温度)、马尔科夫链长度和停止标准。
SA 算法的三个方面描述如下:①目标函数非常重要。精 确地描述我们将要处理的问题必须是简单而容
易的。②内部 变换规则，包括新参数的生成和接收规则，必须简单、有效、方 便地计算和准确地描述参数空间。确保新参数能够覆盖整个
解空间，接收规则的选择可以使算法从局部最优解跳跃到全
局最优解。大多数SA 算法都是使用Metropolis 准则作为新
参数的接收规则。③退火规则控制SA 算法的基本方向，确定 算法的控制参数和停止规则。
2基于模拟退火算法的多相序列搜索
»•(*)=
N _
工 x(n)x*(»-i) = r(—k)
1)
mQ+l
其中，“mod ”为取模运算：
(p-\_p/N]N, p 不是A 啲整数倍
pmod Ar =<
[n ,
其他
其集成旁瓣水平度量分别为：
k=l
册甘(吋
*=1
⑹
(7)
(8)
(9)
在本文中，用矩阵F 表示(逆)傅里叶矩阵，其中第&刃
个元素为：
r ,
1 j 竺切
[F]^ ~~^y e N » k,p = l,L,N
(10)
且&为序列兀的离散傅里叶变换，
” = LL,N
(⑴
«=1
根据Hao He 的文章问，可以用基于傅里叶变换的式子来
表示序列的周期自相关集成旁瓣水平，即：
应=£|的冷劄X 』-，阴
(⑵
而对于非周期的情况，为了能更快地搜索到较长序列，我
们推导出基于傅里叶变换的式子来表示其自相关集成旁瓣, 设序歹lb = [x(l)x(2)L xWf, x z =[x(l)x(2)L x(N)0L 0丁氓并且用 Y
表示2Nx2N 的右循环矩阵：
x(l)工(2) L x(N) 0 L
000M M
HN)M
侶1)
M M .x(2)
巩3)
L L
x(l)
则关于序列x 的相关矩阵为:
(13)
'7(0)
7(1) 7(2) L r(^-l) 0
7(1)・ ；(0) ；(1) 7(42)M
数字大炮
O
O
地震的模拟实验r(X-l) O
M
O
r(l) r(2)
L 0 r(X-l)* L 7(2)・
M
M
7(1)・ ；(0)
(3)
一条长度为N 的多相序列可以用一个复数序列表示：
{x 何= /«")』=12丄"} (2)
其中，0(”)是序列x 的第n 个元素的相位，且其取值范围
为0到2兀之间。如果序列中每个元素可选择的不同相位数为
M，则每个元素的相位只能从以下允许值中选择：
,(”)・{碍,2寻丄,("-1序
{MV"]
对于码长为N 、相位数为M 的多相序列x，可以用IM 的
相位矩阵简明地表示x 的相位值：
@ = [,(1),,(2)丄 0(N)]
(4)
比如：如果M=4，那么闿，必,…，算的取值就分别为0,7t/2,n
和3兀/2。
2.1目标函数
序列{x("),”=l,2,…,N}的周期O(Q)和非周期(『(£))自 相关定义如下：
r k =
N
^x(n)x e ((n —k)modN )t
⑸
(14)
设戶是2NX2N (逆)离散傅里叶矩阵，其中第(k,p)个元素
为：
,
k,p = 1,2,L ,2N
(15)
且E ，= £x(”)「益",p = l, 2.L, 2N 为序列X 啲离散傅里叶
B=1
变换。
由任意循环矩阵都可以被傅里叶变换矩阵对角化知:
y =f h df
X x
其中，
Q= 花
.o
周施雄x w
又由(14)和(16)可得：
(16)
(17)
53
7⑴
”2)'”<0
r(2) L r(^-l) 0 L
九)・
M 7(0)7(1)
r(N-2)
7(2)・
如).0
侶2)・
o
M 7(1)M 0
o
M
0 L ；(1)' 7(0)
^YY n •DD^F
(18)
从而有:
7(0)
FT
M 比3
M
訂(NT)，
M
(19)
7(n -i )
M
松下手机7(0)
所以，对于非周期的情况，其基于傅里叶变换的相关集成献血法
旁瓣水平为：
因此，使得多相序列相关集成旁瓣水平最小的序列优化
问题就可以总结为：在满足序列的元素模量为1
1,2丄，"})的约束下，使(12)和(20)式所给出的表达式的值最
小。然后我们目标函数就可以设为：
周期的情况：
咔鼬「-伽］}
(21)
非周期的情况：
丽{击级卜¥}
(22)
2.2接收规则和退火规则
式⑴中表示的Metropolis 规则为接收规则，接收概率计
算函数为：
P=°P (晋］
C23)
退火规则为：
= aT t
C24)
在以上设置中,AE 为目标函数的变化量;T*是控制参数;a
为常数，在本次设计中,a 取0.99； k 为Metropolis 过程中的循
环指数，为模拟退火的第k 个阶段。
2.3基于SA 的多相序列搜索算法
搜索一条序列长度为N 、不同相位数为M 的最佳多相序
列的数量级为0，该数量级随着序列长度和相位集合大小呈
指数增长。因此，多相序列的数值优化问题是一个NP-完全问 题。在多相码集优化过程中，通过序列相位值“突变”进行随 机搜索，即在⑷中随机选取一个条目，用不同的允许值替换
它。对于每个相位“突变"，计算相位变化前后的目标函数，釆
用(23)计算的概率接受相位变化。更具体地说，多相码集Q 的相位值“突变”如下：首先，初始化(4)所示的多相序列相位
集Q ；在该相位集中随机选择一个相位条目，然后将所选的相
位值替换为从其他M 个可能的相位值0，专，2筹，专
中随机选择的相位值。为了成功实施SA，需要确定退火过程
的几个关键参数或标准。这些是起始温度、温度的降低速率，
即冷却时间表、在每个温度下的平衡条件的确定以及退火停
止标准。在这项工作中，起始温度通过设置基于一组随机
目标函数值的标准偏差b 确定：
T 0=-3a/Zn(0.6) C25)
在温度T*O>0)下，字母序列不断“突变”并按(23)的概率
接收，直到目标函数分布达到平衡状态。然后根据(24)将温 度降至T h ，重复编码''突变"，直到在更新后的温度下达到新
的平衡状态。
如果在连续三次温度降低中都没有“突变”的相位被接受
或g (其中£为最小停止温度)，则退火过程停止。选择的£值
是 0.01。
算法具体流程如下：
步骤1：设置初始温度八、马尔科夫链长度Z (固定)、初始 相位矩阵Q 。；
步骤2：对相位矩阵进行随机“突变”，产生新的相位矩阵；步骤3：计算“突变”前后目标函数的变化量AE，以Metrop
olis 规则决定是否接收新的相位矩阵；
步骤4：重复步骤2-3，如果迭代次数大于定义的马尔科夫
链长度，则根据退火规则降低温度；
步骤5：重复步骤2-4，如果连续三次温度降低中都没有突
变的“相位”被接受或T<0.01，则退火结束。
3序列搜索结果
使用SA 算法搜索一条相位数M 为8192，序列长度N 为
128的多相序列。优化的目标函数基于(21)(22)。图1和图
2分别显示了这条序列的周期自相关特性和非周期自相关特
性。图3和图4又分别显示了 ISL 在SA 算法中的收敛趋势。 可以看出，通过SA 我们搜索到了一条周期集成旁瓣水平为
2.2973、非周期集成旁瓣水平为412.7575的多相序列，且算法 收敛性较好。
序列的周期自相关特性
图1序列的周期自相关特性
54
序列的41■：周期向+B关特性
图2序列的非周期自相关特性
迭代次数«104
ISL在SA中的收敛曲线（非周期）
图3ISL在SA中的收敛趋势（周期）
图4ISL在SA中的收敛趋势（非周期）
4结语
模拟退火是设计具有特定特性的多相序列的一种高效工具。利用本文所述算法，对具有良好周期自相关和非周期自相关性质的多相序列进行了优化，合成的序列在雷达波形敏捷性、多址通信系统等方面具有一定的实用价值。
统计优化算法的全局收敛性和鲁棒性都在序列设计中得到了体现。在设计中没有挖掘算法的全部潜力，
通过更慎重地选择退火控制参数可能会得到更好的结果。模拟退火的缺点是消耗大量的CPU时间。实验表明，在占用较多CPU时间的情况下，通常可以得到较好的结果。在合成序列的特性和程序运行时间之间有一个折衷。
参考文献：
[1]KRETSCHMER F.F,GERLACH K.Low Sidelobe Radar
Waveforms Derived from Orthogonal Matrices[J].IEEE TYansactions on Aerospace and Electronic Systems,1991, 27(1):92-102.
[2]KERAHROODIM.A,AUBRY A,MAIO A.D,et al.A Co
ordinate-Descent Framework to Design Low PSL/ISL Se-quences[J].IEEE Transactians on Signal Processing,2017, 65(22):5942-5956.
[3]FARNETT E.C,STEVENS G.H,Radar Handbook[M].
Second ed.New York:McGraw-Hill,1990.
[4]FRANK R.Polyphase Codes with Good Nonperiodic Cor
relation Properties[J].IEEE Transactions on Infonnation Theory,1963,9(1):43-45.
[5]ZHANG N,GOLOMB S.W.Polyphase Sequence with Low
Autocoirelations[J].IEEE Transactians an Information Theory,1993,39(3):1085-1089.
[6]BRENNER A.R.Polyphase Barker Sequences up to Length
45with Small Alphabets!!].Electronics Letters,1998,34
(16):1576-1577.
[7]FERGUSON R,BORWEIN P.Polyphase Sequences with
Low Autocarrelation[J].IEEE Transactions on Information Theory,2005,51(4):1564-1567.
[8]HOU K,REN毎LIU Q.Majorizatian Minimization based
Memetic Algorithm for Designing Polyphase Sequences with Good Correlation Properties[C].Chongqing,China: IEEE,2019.
[9]ZHANG D.Zero Correlatian Zane Sequences from a Unifi
ed Construction of Perfect Polyphase Sequences[C].Paris, France:IEEE,2019.
[10]TAN U,RABASTE O,ADNET C,et al.Optimization Me
thods for Solving the Low Autocorrelation Sidelobes Prob-lem[C].Krakow:IEEE,2016.
[11]STOICA P,HE H,LI J.New Algorithms for Designing Uni-
modular Sequences With Good Correlation Properties[J].
IEEE TYansactions on Signal Processing,2009,57(4): 1415-1425.
[12]SONG J,BABU I>EALOMAR D.P.Optimization Methods
for Designing Sequences With Low Autocorrelation Sidelo-bes[J].IEEE TYansactions on Signal Processing,2015,63
(15):3998-4009.
[13]KIRKPATRICK S,GELAIT C.D,VECCHIM.P.Optimi
zation by Simulated Annealing[J].Science,1983,220 (4598):671-680.
[14]GAMAL A.E,HEMACHANDRA L,SHPERLING I,et al.
Using Simulated Annealing to Design Good Codes[J].IEEE Transactions on Information Theory,1987,33(1):116-123.
[15]STOICA HE H,LI J.On Designing Sequences with Im
pulse-Like Periodic Correlation[J].IEEE Signal Processing Letters,2009,16(8):703-706.
55
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议