基于改进的模拟退火算法的频谱受限序列设计

赵 琴，李旭东

(西华大学 理学院，成都 610039)

在准同步码分多址(Quasi-Synchronous Code-Division Multiple-access，QS-CDMA)系统中，影响其性能的是零时延附近的部分扩频序列相关函数[1]，其自相关性决定了多径干扰，互相关性决定了多址干扰。扩频序列要求在同步误差范围内(零时延附近)具有理想的相关特性，零相关区(Zero-Correlation Zone，ZCZ)序列能够满足这样要求。一般情况下，非周期序列设计比周期序列设计更加困难[2]，且具有良好非周期相关特性的序列通常也具有良好的周期相关特性，但反之则不一定成立。此外，为了避免非线性副作用并充分利用可用的传输功率，通常需要具有理想峰均功率比(Peak-to-Average Power Ratio，PAPR)特性的通信序列。然而，传统的ZCZ序列(假设整个光谱带的可用性)不能被使用，因为它们的良好相关特性会被CR通道中的频谱约束所破坏/丢失[3]。

认识到这一设计挑战，He等[4]采用数值方法设计认知雷达系统中预定阻带的低频谱功率和低相关的单模序列。在此基础上，Tsai等[5]利用凸优化和GS(Gerchberg-Saxton)算法研究了低自相关和低PAPR的认知序列。Liu等[6]通过在频域上的凸优化，给出了单通道和多通道频谱受限序列集(Spectrum Constrained Sequences，SCSs)的周期性和非周期性相关下界，并指出一个未来的任务是构造最优的SCSs，这些SCSs具有一致低的自相关和互相关特性，无论是数值上还是分析上的都接近其导出的边界值。然而，文献[4-5]中的方法可能不适用于构建具有低/零互相关性的认知序列。到目前为止，具有低/零相关特性的认知序列的系统构造仍然是开放的。

本文在传统的模拟退火算法[7]上利用线性递减策略设置降温函数，给出新的Metropolis更新准则，提升算法的全局搜索能力；设计新的相位突变函数使算法具有自适应性。从频域角度出发，推导基于FFT的目标函数，结合凸优化算法，搜索具有低非周期自相关特性和低峰均功率比的单个频谱受限序列。同时，还搜索了具有良好的非周期自相关特性和互相关特性的频谱受限序列集。此外，本文还研究了序列长度和序列数目对算法性能的影响。

1 序列理论基础

1.1 定义及基本性质

其中0≤k≤N-1，(·)*表示复共轭。(n-k)N表示整数n-k模N。实际上，当m1=m2时，Cmm被称为非周期自相关函数(Aperiodic Autocorrelation Function，AACF)。类似地，Rmm被称为周期自相关函数(Periodic Crosscorrelation Function，PACF)。非周期自相关和互相关函数统称为非周期相关函数，周期自相关和互相关函数统称为周期相关函数。

定义4(PAPR)单个序列x的峰均功率比定义为

性质1一致低的周期自相关函数是一致低的非周期自相关函数的必要条件。

性质2维纳辛钦定理表明时域序列的PACF和功率谱是离散傅里叶变换对，时域序列x在时延τ处的PACF满足Rx(τ)=FH(τ,:)r,τ∈{1,2,…,N-1}。

由性质1知，序列的低AACF优化问题可以转化为序列的PACF的次优化问题，这里使用周期自相关峰值旁瓣PSL′来衡量序列的AACF，即

(1)

这里FH(τ,:)表示IDFT矩阵FH的第τ行。

1.2 新的序列设计准则

衡量序列x的相关性能好坏的常用度量为集成旁瓣水平ISL和峰值旁瓣水平PSL，前者侧重考虑在任何时延处的序列相关性能的整体优化，表示旁瓣总能量；后者侧重考虑最大相关旁瓣对序列性能的影响，可用来评估序列相关旁瓣与其上界的接近程度[2]。在复杂电磁环境及QS-CDMA系统中，联合优化序列集的归一化总自相关峰值旁瓣水平和归一化总互相关峰值旁瓣水平作为SCSs设计准则是更好的选择。

1.3 约束条件

1.3.1 能量约束

1.3.2 频谱约束

设标记向量S=[S0,S1,…,SN-1]，该向量描述了每个子载波可用状态，当子载波被占用或需要避免时，Si=0；反之，则子载波可用，记为Si=1。记Ω为不可用子载波集合，其中Ω={k|Sk=0}，则定义频谱约束为B(i)=0,i∈Ω，称满足上述条件的序列为频谱受限序列，记为SCS。给定一组序列，如果每个序列都满足频谱约束，称这样的序列集为频谱受限序列集，记为SCSs。

2 频谱受限序列设计的优化问题

2.1 具有低AACF和低PAPR的SCS优化问题

给定单个频谱受限序列x的频域序列B，设计具有良好AACF的SCS旨在最小化非周期自相关峰值旁瓣PSL，此外，还期望获得SCS的其他性能，比如PAPR，相应的目标函数分别为：

设惩罚因子为ρ，考虑联合设计具有低AACF和低PAPR的单个SCS，其优化问题如下：

(2)

上述优化问题是基于快速傅里叶变换(FFT)的以N点频域序列B为自变量的非线性多变量优化问题，解空间为包含许多局部解的复空间，He等[8]提出了用局部最小化算法即CAN算法来设计无谱约束下的具有良好AACF的单模序列，故我们在此基础上引入频谱约束，从频域角度提出了一种基于改进的模拟退火的智能进化算法来设计频谱约束下的具有低AACF和低PAPR的认知序列。

2.2 具有低ACF的SCSs的优化问题

借鉴最优化理论中最小最大化优化问题的应用背景：通过抑制最突出的成分来达到对整体的一个优化，这在通信方面具有重要理论意义。因此，本文在优化过程中，以一定权重λ(λ∈[0,1])同时优化SCSs的归一化总自相关峰值旁瓣水平APSL和归一化总互相关峰值旁瓣水平CPSL，而不是直接优化非周期集成旁瓣水平ISL。其优化问题如下：

(3)

将上述SCSs设计问题表述为一个高阶、多变量、非线性的约束优化问题。可通过调整参数λ，来实现SCSs的自相关特性和互相关特性的权衡，当λ>0.5时，SCSs设计问题更倾向于优化其自相关特性。反之，上述优化问题倾向于优化SCSs的互相关特性。

3 SCSs设计算法

鉴于频谱受限序列设计问题是一种非线性NP-hard问题，直接求解是很困难的，相比无谱约束下的迭代直接搜索序列设计算法思想，模拟退火算法更加适用于解决频谱受限序列设计问题，是近年来求解复杂非线性多变量函数的最优或近似最优解的有力工具。而频域序列最重要的2个特征是幅度和相位，因此可分2步走设计有效的算法来搜索任意频谱受限序列的最优幅度和最优相位。

3.1 改进的模拟退火算法

本文在传统SA算法的基础上，设计了动态的降温函数和灵活的相位点突变函数。经查阅文献和数值实验，发现传统SA算法在前期遍历解空间的范围不够大，导致后期搜索过程中没有得到全局最优解或近似解，对此，本文设计了新的Metroplis准则：在预定义的迭代次数内，以一定概率接受差解，充分遍历解空间；在算法后期，不再接受差解。这样不仅使算法具有逃脱局部极值和避免过早收敛的全局优化能力，而且降低了时间复杂度。此外，在内循环过程中增加记忆矩阵，找到内循环过程中的最优解以作为下次迭代的初始解，有效提高了全局解的质量。改进的模拟退火算法(Modified Simulated annealing，MSAA)如下：

1)动态降温函数：借用粒子群算法的线性权重递减策略[10]，设计了灵活的降温函数

其中T0为初始温度，Tend为终止温度，Time为总降温次数，count为当前迭代次数，T为下次迭代温度。

2)相位点突变函数：在文献[11]中，突变位的数目类似于步长。一种自适应技术是在早期搜索过程中使用更多的变异位来提高搜索效率，并在以后的搜索过程中减少突变数，以达到足够的精度[12]。如果突变数过小，特别的当突变数为1时，搜索进程较缓慢，不容易遍历解空间跳出局部解，同样突变数过大，则搜索可能退化成随机搜索，本文在搜索过程中依目标函数值变化构建了具有自适应的相位点突变函数，如下：

其中G为1到N-|Ω|中任意整数。

3)新解函数：本文采用替换操作为主新解函数，交换、翻转操作为次新解函数，分别隔一定时间调用，不断引入新个体，增加解的多样性，扩大全局搜索范围。

3.2 非周期下SCSs的频域序列的最优相位优化算法

序列的功率谱保留了频域序列的幅度信息，利用文献[13]的凸优化算法最小最大化单个SCS的PACF，根据性质1可以得到最优功率谱，即频域序列B的最优幅度。本文主要有两个设计任务，一是利用本文提出的MSAA算法搜索单个SCS的最优相位。二是利用本文提出的MSAA算法搜索SCSs的最优相位，除了初始化步骤不同外，其他步骤和单个SCS设计类似。MSSA算法的伪代码如下：

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

计算T0,Time

whileT>Tend

count=count+1

fori=1:iterdo

根据突变数和新解函数，计算新解B_sa

计算“突变”前后的目标函数的变化量ΔE

在预定义迭代次数下

if ΔE≤0 then

B0=B_sa

else产生一个随机数q=rand(0,1),P>q

B0=B_sa

end if

记录内循环下每次循环后的解和对应的目标函数值

end for

选取内循环中最好的解B_best作为下次温度迭代下的初始解，并记录该最优解B_best及对应的目标函数值E_best

end While

输出：B，并利用N点DFT，得到频谱受限序列SCSs，即对应的时域序列集x

4 数值举例

考虑先利用凸优化算法最小化(1)式，得到SCS的最优频域幅度并固定其幅度，以(2)式中的E1为目标函数，利用本文提出的MSAA算法来搜索SCS的最优相位，假设SCS的序列长度为N=64，惩罚因子ρ=0.95，设子载波标记向量为S=[114,06,120,08,116]，则Ω={14,…,19}∪{40,…,47}，多次运行后的MSAA算法的优化趋势见图1，将搜索到的SCS的AACF和PAPR与文献[13]进行比较见图2。从图1可以看出，MSAA算法是快速收敛且有效的，图2显示了SCS的时域、频域幅度和AACF水平。与文献[13]相比，本文提出的MSAA算法所优化的AACF和PAPR都相对较好。为了更好地衡量SCS的AACF和PAPR，本文还探究了序列长度为N=25,…,210对序列设计结果的影响，并将MSAA算法和HL算法[13]生成的SCS的PSL和Welch界[14]、Liu界[5]进行比较(图3)，两种算法下的SCS的PAPR与理想PAPR的比较见图4。结果表明，MSAA算法性能随着序列长度增大呈现良好稳定的性能，但时间复杂度会升高。事实上，MSAA算法的优点不仅在于设计的SCS具有较好的低相关性和低PAPR(使用不同初始化)，计算时间上也是可行的，且SCS的AACF与PAPR之间相互制约。可通过调节权重因子ρ的大小，改善序列的相关特性和PAPR。这些随机分布的SCS在某些领域如QS-CDMA和信道估计中是有用的。由于算法全程都有FFT的参与计算，因此计算效率较高，且该算法对任意SCS的序列设计具有普适性，可以用来设计频谱限制下的二进制序列、多相序列、单模序列等。

此外，进一步研究了优化问题(3)，在序列数目为M=2，序列长度为N=25,…,210和序列数目为M=2,…,7，序列长度为N=64两种参数设置下，利用本文提出的MSAA算法来设计具有低AACF和ACCF的SCSs，将其与文献[5]中的频谱受限下的非周期相关旁瓣理论界Liu界和Welch界进行比较，分别见图5、图6，可以看出，随着序列参数的变化，本文利用MSAA算法所优化得到的SCSs都具有良好的AACF和ACCF，且都接近相关理论界。

此外，还研究了MSAA算法随序列参数变化的性能即频谱受限序列的相关下界的可实现性，这里主要通过计算时间来表现，具体情况见表1，当序列长度较大时，MSAA的计算时间也是可行的，比传统SA算法快得多，这在长序列的搜索上是一个很大的优势。

表1 MSAA和SA算法随序列参数变化的运行时间

5 结 论

由于频谱政策的影响，传统的ZCZ序列无法满足认知无线电系统，它在频谱约束下的良好相关特性将会被破坏或丢失，基于此，为了实现无干扰的CR-CDMA通信，本文提出了一种基于改进的模拟退火算法的全局优化算法，联合优化单个SCS的AACF和PAPR两大指标，所提出的SCS很好地满足Welch界和Liu界，具有较强的实用价值。该算法的时间复杂度与空间复杂度相对较低，不依赖于初始解，具有较好的鲁棒性。此外，设计了具有低非周期自相关和互相关特性的SCSs以支持多用户传输，研究了序列参数对MSAA算法性能的影响。数值实验证明该算法可行且高效。