有色噪声下GNSS空时抗干扰算法的性能分析和改进

赵辰乾; 刘益辰; 刘欣

doi:10.11999/JEIT210174

有色噪声下GNSS空时抗干扰算法的性能分析和改进

doi: 10.11999/JEIT210174

中国船舶工业系统工程研究院北京 100094

详细信息

作者简介:
赵辰乾：男， 1994年生，工程师，研究方向为抗干扰、电子对抗

刘益辰：男， 1992年生，工程师，研究方向为电子对抗

刘欣：男， 1987年生，高级工程师，研究方向为电子对抗

通讯作者:
赵辰乾　757026583@qq.com

中图分类号: TN967.1
计量
- 文章访问数: 812
- HTML全文浏览量: 680
- PDF下载量: 90
- 被引次数: 6
出版历程
- 收稿日期: 2021-02-25
- 修回日期: 2021-08-27
- 录用日期: 2021-08-27
- 网络出版日期: 2021-12-19
- 刊出日期: 2022-04-18

Effect of Colored Noise on STAP Algorithm for GNSS Anti-jamming and Algorithm Improvement

System Engineering Research Institute, CSSC, Beijing 100094, China

摘要

摘要: 在全球卫星导航(GNSS)阵列天线抗干扰理论中，系统噪声通常被视为理想白噪声(AWGN)。但在实际工程中发现系统噪声通常是有色噪声且会影响空时自适应处理(STAP)算法的性能。该文首先推导得出了有色噪声功率谱与空时抗干扰后卫星导航信号相关峰的理论关系，然后通过仿真实验验证了该理论关系的正确性，同时分析了噪声功率谱的等效带宽和谱峰偏移对相关峰的影响，最后发现噪声功率谱能量越集中于卫星导航信号的功率谱谱峰处，空时抗干扰后的卫星导航信号相关峰衰减越大。针对上述问题，该文提出了对角加载和子空间投影方法，两种方法通过对噪声协方差矩阵的特征值进行一致化处理实现有色噪声的白化，从而消除了有色噪声的影响。最后通过仿真实验验证了所提方法的有效性。
- 卫星导航 /
- 空时自适应处理 /
- 有色噪声 /
- 影响分析 /
- 算法改进
Abstract: In adaptive array processing for Global Navigation Satellite System (GNSS) anti-jamming, system noise is usually modeled as AWGN(Additive White Gauss Noise). But in engineering, system noise is generally non-white and colored noise has a great impact on the performance of STAP (Space-Time Adaptive Processing) algorithm. Firstly, the theoretical relationship between the power spectrum of noise and the correlation peak of GNSS signal after space-time anti-jamming is derived, then the theoretical relationship is verified by simulation experiment which simultaneously analyzes the effect of equivalent bandwidth and spectrum peak shift of noise on GNSS signal’s correlation peak. Experimental results show the more the noise power spectrum energy is concentrated at the peak of the power spectrum of GNSS signal, the lower the correlation peak of the GNSS signal after space-time anti-jamming. For the above problem, diagonal loading and subspace projection methods are proposed in this paper, and the two methods achieve the whitening of colored noise by consistent processing of the eigenvalues of the noise covariance matrix, so that the effect of colored noise is eliminated. Finally, method is verified by experiments.
- GNSS /
- Space-Time Adaptive Processing (STAP) /
- Colored noise /
- Effect analysis /
- Algorithm improvement

HTML全文

1. 引言

近年来，现场可编程门阵列(Field Programmable Gate Array, FPGA)广泛应用于各个领域，如深度学习^[1]、云计算^[2]和芯片设计的验证问题^[3]。复杂的专用集成电路(Application Specific Integrated Circuit, ASIC)芯片设计需要通过多种验证方法保证设计的正确性。验证的主要方法有软件仿真、形式化验证和硬件仿真。随着芯片设计越来越复杂，软件仿真需要花费大量的运行时间仿真每个逻辑电路，形式化验证难以适用于大型ASIC设计的验证问题，同时传统的硬件仿真方法需要花费大量的成本来实现验证。而基于FPGA原型验证的硬件仿真方法可以解决大型ASIC设计的验证问题，并且能够在成本和运行时间之间做到平衡。因此，许多先进的微处理器制造商在其验证过程中使用了基于FPGA原型验证的硬件仿真方法。

ASIC设计随着规模的不断扩大，越来越难在单个FPGA上实现逻辑验证^[4,5]。因此，大型的ASIC设计将根据设计需求被划分到多个FPGA内。与单FPGA系统相比，多FPGA系统逻辑复杂性更高，设计能力更强。高速收发器被运用于FPGA系统中，可以提高FPGA间的数据交换速度。随着FPGA内部构造越发复杂，FPGA间信号数量会远远超过I/O引脚数量。而时分复用(Time-Division Multiplexing, TDM)技术被广泛运用于解决I/O引脚数量不足的问题。然而，TDM技术会造成FPGA间的信号延迟，导致系统时延的增加。因此，减少TDM技术所导致的系统时延是十分重要的问题。

时分复用比率是用来衡量系统时钟周期使用情况的数值。在多FPGA原型系统的设计流程中，TDM比率通常是在FPGA布线后确定的。文献[6]提出了同时进行信号分割和分组的方法，可以优化分区和TDM比率。为了解决FPGA间的布线问题，文献[7]和文献[8]使用Pathfinder迭代地优化FPGA间的布线问题。然而，这两类工作都未考虑线网组的概念。文献[9]通过减少线长优化FPGA间的布线结果。然而，多FPGA系统的优化目标不仅仅是线长，TDM的比率分配也非常重要，因为系统性能很大程度上受到FPGA间线网的延迟影响。为了优化TDM比率，文献[10]提出了一种基于整数线性规划(Integer Linear Programming, ILP)的优化算法，但ILP只适合解决较小尺寸的问题。此外，以往工作中的TDM比率通常是任意整数，并不符合实际情况。

根据实际应用中的设计，本文提出一种用于时分复用技术的多阶段协同优化FPGA布线(Multi-Stage Co-optimization FPGA Routing, MSCOFRouting)方法，旨在满足TDM比率约束的前提下，布线拓扑生成阶段、TDM比率分配阶段和TDM比率优化阶段3个阶段协同优化FPGA间的可布线性和TDM比率。本文的主要贡献如下：

(1) 提出一种自适应布线算法，以避免布线拥塞，解决FPGA间布线优化问题，有力减少系统时延。

(2) 提出一种基于拉格朗日松弛(Lagrangian Relaxation, LR)的TDM比率分配算法，使小规模线网组获得较大TDM比率，大规模线网组获得较小TDM比率，有效解决TDM比率分配问题。

(3) 提出了一种TDM比率优化算法，缩减线网组和FPGA连接对的TDM比率。

(4) 将多线程并行化方法运用到上述3个算法，进一步提高MSCOFRouter的运行效率。

(5) 实验结果表明，本文算法不仅能满足TDM约束条件，而且可以获得比同类工作更好的解决方案。

后文组织如下：第2节介绍了时分复用技术和问题模型；第3节阐述了MSCOFRouting的整体框架。第4节给出本文相关策略的有效性验证及实验结果的比较分析。第5节总结全文。

2. 问题模型

2.1 时分复用技术

使用时分复用技术可以有效地解决I/O引脚数量不足的问题，使得多个信号可以在不同时间段共用一个I/O引脚。然而，使用时分复用技术会造成系统时延的增加。TDM比率是用来衡量系统时钟周期使用情况的数值，可以作为衡量系统时延的指标。系统时延与TDM比率呈单调递增关系。因此，通过降低TDM比率可以有效减少系统时延。FPGA连接对p上边e的时分复用比率如式(1)所示。

${\text{TR}}(e) = \frac{{{\text{DN}}(p)}}{{{\text{Cap}}(p)}}$

(1)

其中，DN(p), Cap(p)和TR(e)分别代表通过FPGA连接对p的信号数、FPGA连接对p的容量和边e的TDM比率。由于一个FPGA连接对间只有一根物理导线，所以FPGA连接对的容量固定为1。

图1是时分复用技术的示意图。图中的长方形、正方形和圆形分别表示转换器、实例和分区。红色箭头、蓝色箭头和绿色箭头分别表示3种不同的信号，两个FPGA中间的黑色箭头表示两个FPGA之间唯一的物理导线。在未使用时分复用技术的情况下，一个系统时钟周期内，一条物理导线只能传输一种信号。这会导致FPGA系统运行效率的下降。为了提升FPGA系统的运行效率，时分复用技术被运用在FPGA系统中，使得在一个系统时钟周期内可以传输3种不同的信号。

图 1 时分复用技术的示意图

下载: 全尺寸图片幻灯片

2.2 FPGA间的布线问题

2019年ICCAD比赛^[11,12]提出的FPGA间布线问题将FPGA系统中的FPGA抽象为节点，忽略了一些FPGA的特殊性，着重解决FPGA间的布线问题。本文常用的符号如表1所示。

表 1 常用符号

符号	含义
NG	所有线网组
N	所有线网
P	所有FPGA连接对
E	所有线网的边
Ne	经过边e的所有线网
ng_i	NG中第i个线网组
n_j	N中第j个线网
p_k	P中第k个FPGA连接对
ngl_j	包含n_j的线网组，ngl_j ⊆NG
ng_j,m	ngl_j中的第m个线网组
e_j,k	n_j中使用p_k的边
el_k	p_k的边
el_j	n_j的边
nl_i	ng_i的线网
α	线网组的数量
mng_j	ngl_j中带有最大TDM比率的线网组

下载: 导出CSV

| 显示表格

本节通过图2和表2的例子介绍FPGA间的布线问题。给定一组线网N和一组线网组NG。线网组是根据设计目的给定的。例如，具有相似属性或相同功耗的线网将在同一个线网组中。同时，给定一个无向图G，其中包括了多个由F表示的FPGA和多个由P表示的FPGA连接对。问题目标是根据无向图G对所有线网进行布线，并且为每条边分配合理的TDM比率，以最小化线网组的最大TDM比率。

图 2 TDM比率分配示意图

下载: 全尺寸图片幻灯片

表 2 线网组信息

线网组	线网	FPGA	示例
NG₁	N₁	F₃, F₄
NG₁	N₂	F₁, F₄
NG₂	N₃	F₁, F₂
NG₂	N₄	F₁, F₂
NG₃	N₁	F₃, F₄
NG₄	N₅	F₁, F₂
NG₅	N₆	F₂, F₃

下载: 导出CSV

| 显示表格

表2给出了线网N和线网组NG的信息，其中，不同的线网用不同颜色表示。图2(a)是一个结构图。f_i代表第i个FPGA，p_k代表第k个FPGA连接对。图2(b)是表1基于图2(a)所生成的布线结果。e_j,k代表线网n_j经过连接对p_k所布的边。连接对p_k间边的数量就是通过连接对p_k的信号数量。为了分析系统时延，每条边e_j,k应该被分配一个TDM比率。一个FPGA连接对应该满足TDM比率约束，如式(2)所示。

$\quad \sum\limits_{{{\text{e}}_{j,k}} \in {\text{e}}{{\text{l}}_k}} {\frac{1}{{{\text{et}}{{\text{r}}_{j,k}}}} \le 1}$

(2)

$\quad {\text{et}}{{\text{r}}_{j,k}} \in \left\{ {x\left| {x = 1 \times y,y \in {N^*},2 \le x} \right.} \right\}$

(3)

其中，etr_j,k表示e_j,k的TDM比率。如图1所示，由于所有的信号必须在半个周期内完成1次传输，故etr_j,k的值必须是偶数。每条边的TDM比率分配结果如图2(c)所示，对于p₁, e_2,1, e_3,1, e_4,1和e_5,1的TDM比率分别是4, 6, 6和10。由于1/4+1/6+1/6+1/10 <1，所以p₁满足TDM比率约束。

线网n_j的TDM比率和线网组ng_j的TDM比率定义为

${\text{nt}}{{\text{r}}_j} = \sum\limits_{{e_{j,k}} \in {\text{e}}{{\text{l}}_j}} {{\text{et}}{{\text{r}}_{j,k}}}$

(4)

${\text{gt}}{{\text{r}}_j} = \sum\limits_{{n_j} \in {\text{n}}{{\text{l}}_i}} {{\text{nt}}{{\text{r}}_j}}$

(5)

其中，ntr_j和gtr_j分别表示n_j的TDM比率和ng_i的TDM比率。如图2(c)所示，线网n₂上的边有e_2,1=4和e_2,3=2，所以ntr₂=etr_2,1+etr_2,3=2+4=6。线网组ng₂的包括n₃和n₄，所以gtr₂是12。

本文的优化目标是最小化TDM比率最大线网组的TDM比率，从而优化系统时延，具体如式(6)所示。

${\text{min}}:{\text{gmt}} = \left\{ {x|x = \max \left( {{\text{gt}}{{\text{r}}_1},\cdots,{\text{gt}}{{\text{r}}_a}} \right)} \right\}$

(6)

其中，gmt代表了TDM比率最大的线网组的TDM比率。如图2(c)所示，gmt是12。

3. 总体框架

用于时分复用技术的多阶段协同优化FPGA布线方法的总体框架如图3所示，分别为布线拓扑生成阶段、TDM比率分配阶段和TDM比率优化阶段3个阶段。具体地，第1阶段根据问题定义的线网和线网组进行布线，得到未分配TDM比率的布线结果。第2阶段使用拉格朗日松弛的方法为FPGA连接对的每条边分配初始的TDM比率。第3阶段通过松弛TDM比率较小的线网组，减小TDM比率倒数之和相对较小的FPGA连接对的最大TDM比率来优化TDM比率比较大的线网组。MSCOFRouting通过上述3个阶段协同优化FPGA的可布线性和TDM比率分配结果。

图 3 MSCOFRouting总体流程图

下载: 全尺寸图片幻灯片

3.1 布线拓扑生成

布线拓扑生成阶段的目标是根据给定的线网和线网组定义将每个线网的FPGA连接在一起。布线生成的Steiner树的质量会影响后续的TDM比率分配。由于Dijkstra算法可以有效构建Steiner树^[13,14]，因此本文使用基于Dijkstra算法的FPGA间布线算法连接所有线网，解决FPGA间的布线优化问题，使可布线性得到优化。算法中各变量的定义如下，f_s代表从F_n中选择的第1个FPGA、F_n表示线网n_j必须连接的目标FPGA、d表示两个FPGA间的布线代价、F_all表示所有FPGA、f_u表示与f_s布线代价最小的FPGA，f_v表示f_u的每个邻居FPGA, sp_v表示该线网的Steiner树。

自适应布线算法如下所示。由于线网所在的线网组中的线网数量和线网需要连接的FPGA数量对于线网的布线方案有重要的影响。所以所有线网都按照这两个指标进行排序。然后，初始化布线图，每个FPGA连接对的初始布线代价为1。最后，对所有的线网进行迭代布线。

对所有的线网进行迭代布线的具体步骤如下。首先，从F_n中选择一个FPGA赋值给f_s。其次，初始化F_n中各FPGA与f_s的距离。然后，集合F_all等于集合F。最后，通过Dijkstra算法构造Steiner树。Dijkstra算法首先找到与F_all中与f_s代价最小的FPGA f_u，然后更新集合F_all，最后更新f_u的所有邻居节点的布线代价d_v。当找到所有目标FPGA后，Steiner树被构造出来，把sp_x记录下来。Steiner树所使用的FPGA连接对的布线代价更新公式为

${\text{Tp}}'_k = \left\{ \begin{gathered} {\text{T}}{{\text{p}}_k} + {t_e},{\text{N}}{{\text{p}}_k} = 2t \\ {\text{T}}{{\text{p}}_k} + {t_o},{\text{N}}{{\text{p}}_k} = 2t + 1 \\ \end{gathered} \right.$

(7)

其中，Tp_k代表FPGA连接对的布线代价，Np_k代表FPGA连接对上已布线的边数，t_e和t_o分别表示FPGA连接对上已布线的边数为偶数和奇数的更新代价。实验得出t_e, t_o分别取0.81和1.19时优化效果最好。

图4只考虑两个FPGA间的布线情况。两个FPGA间有1条或者2条边时，每条边分配的TDM比率都是2，最大TDM比率都是2；当两个FPGA间有3条边时，每条边分配的TDM比率分别是2, 4, 4。当两个FPGA间有4条边时，每条边分配的TDM比率分别是4, 4, 4, 4。最大TDM比率都是4。由此可以得出结论：设i为奇数，当两个FPGA间有i条边时，布下1条边之后，最大TDM比率不变，为i+1；当两个FPGA间有i+1条边时，布下1条边之后，最大TDM比率值增加2，为i+3。所以布线代价更新式(7)可以减少两个FPGA间奇数条边的情况，优化布线结果，减少最大的TDM比率。

图 4 FPGA之间不同布线情况示意图

下载: 全尺寸图片幻灯片

3.2 TDM比率分配

TDM比率分配阶段需要为每条边分配满足约束的TDM比率并且使TDM比率最大的线网组的TDM比率最小化。在这一阶段，本文提出了一种基于拉格朗日松弛算法的TDM比率分配方法。

由于优化目标是将线网组中最大的TDM比率最小化，所以问题模型可以写成

$\left.\begin{aligned} & \mathop {{\text{min}}}\limits_{\text{t}} {\text{ gmt }} \\ & {\text{s}}{\text{.t}}{\text{. }}\sum\limits_{n \in N} {\sum\limits_{e \in E} {{\text{t}}{{\text{r}}_{{\text{ne}}}} \le {\text{gmt}}} } \\ & \quad\;\; \sum\limits_{n \in {\text{Ne}}} {\frac{1}{{{\text{t}}{{\text{r}}_{{\text{ne}}}}}} \le 1} \end{aligned}\right\}$

(8)

其中，gmt是布线图中TDM比率最大的线网组的TDM比率，tr_en是线网n中边e的TDM比率。本文将此公式称为主问题(Primal Problem, PP)。为了解决这个NP难问题，算法松弛第1个约束并引入非负拉格朗日乘数λ。λ作为违反约束的惩罚值。式(8)引入λ后可以得到

$L\left( {t,\lambda ,{\text{gmt}}} \right){\text{ = gmt + }}\sum\limits_{{\text{ng}} \in {\text{NG}}} {\lambda \left( \sum\limits_{n \in N} {\sum\limits_{e \in E} {{\text{t}}{{\text{r}}_{{\text{ne}}}}} } - {\text{gmt}}\right)}$

(9)

对于给定的拉格朗日乘数，拉格朗日乘数子问题LRS(λ)如式(10)所示。

$\left.\begin{aligned} & \mathop {{\text{min}}}\limits_{\text{t}} {\text{ }}L\left( {t,\lambda ,{\text{gmt}}} \right){\text{ }} \\ & {\text{s}}{\text{.t}}{\text{. }}\sum\limits_{n \in {\text{Ne}}} {\frac{1}{{{\text{t}}{{\text{r}}_{{\text{ne}}}}}} \le 1} \end{aligned}\right\}$

(10)

通过应用Karush-Kuhn-Tucker (KKT)条件以获得最优解，LRS(λ)问题可以简化为

$\left.\begin{aligned} & \mathrm{LRS}\text{*}\left(\lambda \right)：\underset{\text{t}}{\text{min}}\text{ }{\displaystyle \sum _{e\in E}{\displaystyle \sum _{n\in \text{Ne}}{\displaystyle \sum _{g\in {\text{NG}}_{n}}\lambda \times {\text{tr}}_{\text{ne}}}}}\\ & \qquad\qquad\quad \text{s}\text{.t}\text{. }{\displaystyle \sum _{n\in \text{Ne}}\frac{\text{1}}{{\text{tr}}_{\text{ne}}}\le 1} \end{aligned}\right\}$

(11)

拉格朗日对偶问题(Lagrangian Dual Problem, LDP)可以定义为

$\left.\begin{aligned} & {\text{max LRS*}}\left( \lambda \right) \\ & {\text{s}}{\text{.t}}{\text{. }}\sum\limits_{n \in {\text{Ne}}} {\frac{{\text{1}}}{{{\text{t}}{{\text{r}}_{{\text{ne}}}}}} \le 1} \end{aligned}\right\}$

(12)

对给定λ集合，求解LDP就是求解下界的最大值。LDP的主要目的是找到合适的λ集合惩罚PP中违反的约束。拉格朗日乘子根据时序弧的时序临界性更新，以满足KKT条件^[15-17]。更新公式为

${\lambda _i} = {\lambda _i} \times {\left( {{\text{TD}}{{\text{M}}_{i,g}}} \right)^{{K_{i,g}}}}$

(13)

其中，TDM_i,g为第i次迭代线网组g与最大线网组的TDM比率之比，K_i,g为第i次迭代的加速因子。加速因子越大，收敛速度越快，但是收敛效果越差。λ越接近目标值，加速因子应该越小。K_i,g的更新公式为

${K_{i,g}} = \frac{1}{{1 - ({{{\text{gm}}{{\text{t}}_i} - {\text{str}}}})/{{{\text{str}}}}}}$

(14)

其中，str是由用户定义的gmt的优化目标。

TDM比率分配算法如下所示。首先，计算边e_j,k的所在FPGA连接对边的数量。接着，计算线网组ng_i的λ_i。然后，根据λ集合计算线网n_i的snλ_i值，计算分配给每条边的TDM比率，再更新λ集合。最后，根据式(13)更新λ_i并根据式(14)更新K_i,g。

3.3 TDM比率优化

在TDM比率分配阶段，通过拉格朗日松弛算法得到的初始TDM比率并非最优解，还存在优化空间。因此，TDM比率优化阶段可以通过增加TDM比率较小的线网组边的TDM比率以减少TDM比率较大的线网组边的TDM比率，并可以针对具体连接对进行优化系统时延，从而使TDM比率最大的线网组的TDM比率最小化。

TDM比率优化算法包括3个步骤。第1步是缩减操作。具体是增加TDM比率较小的线网组的TDM比率，减少TDM比率较大的线网组的TDM比率。第2步是合法化操作。经过缩减步骤后，TDM比率增加的FPGA连接对可能会违反TDM比率约束。因此，违反约束的FPGA连接对需要进行合法化操作。第3步是针对性优化操作。经过上述步骤后，所有FPGA连接对的TDM比率的倒数和与最大值1还有一定距离。通过减少连接对中TDM比率最大的etr_j,k的方式，使得每个FPGA连接对的TDM比率倒数和更接近1，从而使TDM比率最大的线网组的TDM比率更小。

缩减操作的具体步骤如下所示。首先，所有线网按其所在线网组的最大TDM比率从大到小排序。然后，线网n_j中每条边的TDM比率 ${\text{etr}}{'_{j,k}}$ 根据以下公式更新。

$\begin{split} & {\text{etr}}{'_{j,k}} \\ & = \left\{ \begin{gathered} {\text{et}}{{\text{r}}_{j,k}} + {f} \left( {\left( {\frac{{{\text{mn}}{{\text{g}}_j}}}{{{\text{str}}}} - 1} \right) \times {\text{et}}{{\text{r}}_{j,k}}} \right),{\text{mn}}{{\text{g}}_j} < {\text{str}} \\ {\text{et}}{{\text{r}}_{j,k}} - {g} \left( {\left( {1 - \frac{{{\text{mn}}{{\text{g}}_j}}}{{{\text{str}}}}} \right) \times {\text{et}}{{\text{r}}_{j,k}}} \right),{\text{mn}}{{\text{g}}_j} > {\text{str}} \\ \end{gathered} \right. \end{split}$

(15)

其中， ${\text{etr}}{'_{j,k}}$ 是e_j,k新的TDM的比率。f(x)表示大于等于x的最小偶数，g(x)表示小于等于x的最大偶数。

线网n_j的TDM比率减少后，更新ngl_j中各线网组的TDM比率，有利于后续的缩减。

第2步是对FPGA连接对进行合法化操作。经过缩减步骤，TDM比率增加的边e_j,k可以直接使用新的TDM比率 ${\text{etr}}{'_{j,k}}$ ；对于TDM比率减小的边e_j,k，如果p_k满足TDM比率约束，则用 ${\text{etr}}{'_{j,k}}$ 替换对应的p_k中的每条边的etr_j,k。然而，如果p_k不满足TDM比率约束，应由式(16)合法化。

${\text{etr}}{''}_{j,k} = \frac{{{\text{etr}}'_{j,k} \times {\text{rec}} \times ({\text{rec}} + {\text{ad}})}}{{1 - {\text{ad}}}}$

(16)

其中，rec是 ${\text{etr}}'_{j,k}$ 减少的倒数之和，ad是 ${\text{etr}}'_{j,k}$ 增加的倒数之和。

算法第3步是减小具体FPGA连接对的最大TDM比率。经过前两个阶段后，当FPGA连接对边的TDM比率倒数和res_k小于0.95时，这个FPGA连接对的最大TDM比率由式(17)进行更新。

${\text{elt}}'_{k,{\rm{max}}} = \frac{{{\text{el}}{{\text{t}}_{k,\max }}}}{{\left( {1 - {\text{re}}{{\text{s}}_k}} \right) \times {\text{el}}{{\text{t}}_{k,\max }} + 1}}$

(17)

其中，res_k是FPGA连接对p_k上TDM比率倒数和，elt_k,max是FPGA连接对p_k上最大的TDM比率。

如果在缩减步骤中，当mng_j > str，减少的部分都向下取偶数会使得当前FPGA连接对的TDM倒数和更小，更有利于第3步FPGA连接对中最大TDM比率的减小。比如，当有3个线网组的TDM比率为4, 14和24，优化的目标值为8。如果不论mng_j是否大于str，变化值都向上取偶数，经过缩减阶段得出的TDM比率是6, 10和16，TDM倒数和为0.329；如果按照式(15)优化TDM比率，得到的TDM比率是6, 12和16，TDM倒数和为0.25。后者TDM比率倒数和小于前者，更有利于第3步FPGA连接对最大TDM比率的减小。所以选择式(15)的缩减方式。

3.4 多线程并行化

为了提高布线器的效率，使用并行编程模型OpenMp在布线器的各个阶段集成多线程并行化方法。编译器通过识别编译制导语句自动创建线程进行并行化，从而有效提高算法的效率。在布线拓扑生成阶段，各线网的布线操作可以并行执行。在TDM比率分配阶段，每个线网的TDM比率分配都是完全独立的。因此，这个阶段可以对不同线网进行并行化操作。在系统时延优化阶段，每个线网的缩减操作都是并行的。合法化操作和针对性优化中不同FPGA连接对可以并行处理。但是，由于不同线网之间存在资源冲突，自适应布线算法的记录sp_x操作和TDM比率优化算法的更新ngl_j中各线网组的TDM比率操作应该加锁。通过对上述3个阶段使用多线程并行化方法可以有效减少算法运行时间。

4. 实验结果

所提出的优化框架采用C/C++语言实现，并在Intel Xeon Linux服务器上运行。本文在2019年的ICCAD竞赛^[12]发布测试用例上展开实验。该测试用例将FPGA系统中的FPGA抽象为节点，忽略了一些FPGA的特殊性，着重解决FPGA间的布线问题。所以本文算法可以解决不同FPGA的布线问题，具有普适性。表3为测试用例具体信息，其中#FPGA表示FPGA数量，#Net表示线网数量，#NG表示线网组数量，#Edge表示FPGA连接对数量。

表 3 测试用例信息

测试用例	#FPGA	#Net	#NG	#Edge
S1	43	68456	40552	214
S2	56	35155	56308	157
S3	114	302956	334652	350
S4	229	551956	464867	1087
S5	301	881480	879145	2153
S6	410	785539	910739	1852
H1	73	54310	50417	289
H2	157	610675	501594	803
H3	487	720520	886720	2720

下载: 导出CSV

| 显示表格

4.1 与ALIFRouter及MSFRoute的实验比较

本节参考ICCAD2019比赛^[12]的计算评估分数公式将MSCOFRouting与ALIFRouter^[11]及MSFRoute^[18]进行比较。为了强调运行时间的影响，计算评估分数时考虑了运行时间。评估分数sco计算公式为

${\text{sco}} = {\text{TR}} \times \left( {1 + \lg \frac{{{\text{RT}}}}{{{\text{MRT}}}} \times 0.01} \right)$

(18)

其中，TR为TDM最大的线网组的TDM比率，RT为运行时间，MRT为3个布线器运行时间的中位数。sum为所有测试用例的sco之和。布线器的sum越小表示它的优化效果越好。

如表4所示，MSCOFRouting获得了最好的sum，并且达到了最好的TDM比率和运行时间。与MSFRoute和ALIFRouter相比，MSCOFRouting的TDM比率分别降低了4.57%和1.05%，运行时间分别缩短了20.8%和0.44%。由于每个标准测试用例涉及多个线网组，总的布线边数量非常多，因此时钟周期数的基数很大，TDM比率数值很大。虽然TDM比率的优化率较小，但是TDM比率优化值较大，系统时延的优化效果较好，所以实验结果表明MSCOFRouting可以有效优化系统时延。

表 4 本文算法与ALIFRouter及MSFRoute的实验比较(TR为TDM Ratio)

测试用例	MSFRoute			ALIFRouter			本文算法
测试用例	TR(10³)	RT	sco	TR(10³)	RT	sco	TR(10³)	RT	sco
S1	39	34.32	39	38	24.88	38	37	30.58	37
S2	32097	20.51	32097	31736	19.58	31730	31671	20.86	31673
S3	129396	289.91	129375	127826	304.50	127832	127046	300.99	127046
S4	7301	642.51	7301	6466	641.62	6466	6312	619.88	6311
S5	5370	1673.51	5371	4766	1558.48	4766	4618	1570.51	4618
S6	15759857	4536.33	15757896	15751307	4668.18	15751307	15747236	4845.90	15749791
H1	409654	76.86	409661	409026	76.54	409026	408487	66.81	408246
H2	45947775	1322.96	45947798	45942757	1322.81	45942757	45934257	1217.81	45917758
H3	4871917	5283.91	4868324	4866484	6593.58	4867575	4861401	6261.79	4861401
sum	–	–	62289539	–	–	62273922	–	–	62245480
Normalized	1.0457	1.0208	–	1.0105	1.0044	–	1.0000	1.0000	–

下载: 导出CSV

| 显示表格

4.2 多线程并行化方法的有效性验证

MSCOFRouting在不同线程数下的运行时间如图5所示。不同的线段表示不同测试用例的运行时间。本节在具有典型性的中等规模测试用例S3, S4和H2上展开实验。通过使用8个线程、16个线程、24个线程和多线程并行化方法，MSCOFRouting分别可以得到3.11倍、3.82倍和4.08倍的加速。各线网间存在共用同一变量的情况。为了避免多个线程同时修改变量而导致数据错误，则需要对共享变量进行加锁操作。如果同时运行中的线程需要用到已使用的共享变量，则需要等待正在使用该资源的线程运行结束。所以随着线程数的增多，等待共享变量的时间逐渐增加，运行时间的优化率逐渐减少。

图 5 并行化方法有效性折线图

下载: 全尺寸图片幻灯片

4.3 自适应布线算法有效性验证

为了验证自适应布线算法的有效性，本节将采用不同更新代价的自适应布线算法与未采用自适应布线算法的最大TDM比率进行比较。表5为采用不同权重值的自适应布线算法的实验结果。数据都是从同一环境中由8个线程运行的程序中获得的。表5中△TR的优化率的计算公式为

表 5 自适应布线算法有效性验证

测试用例	采用(t_e=1, t_o=1)		采用(t_e=0.21, t_o=1.79)		采用(t_e=0.2, t_o=1.8)		采用(t_e=0.19, t_o=1.81)		采用(t_e=0.18, t_o=1.82)
测试用例	△TR(10³)	Ratio	△TR(10³)	Ratio	△TR(10³)	Ratio	△TR(10³)	Ratio	△TR(10⁴)	Ratio
S1	1	1.0000	1	1.0000	1	1.0000	2	2.0000	1	1.0000
S2	375	1.0000	417	1.1120	423	1.1280	428	1.1413	412	1.0987
S3	1841	1.0000	1864	1.0125	1948	1.0581	1986	1.0788	1941	1.0543
S4	832	1.0000	857	1.0300	931	1.1190	950	1.1418	927	1.1142
S5	604	1.0000	627	1.0381	697	1.1540	717	1.1871	687	1.1374
S6	11574	1.0000	13614	1.1763	12001	1.0369	12009	1.0376	12004	1.0372
H1	798	1.0000	801	1.0038	807	1.0113	812	1.0175	808	1.0125
H2	7742	1.0000	7785	1.0056	7795	1.0068	7821	1.0102	7801	1.0076
H3	6214	1.0000	6245	1.0050	9521	1.5322	10098	1.6250	9457	1.5219
平均	–	1.0000	–	1.0426	–	1.1163	–	1.2488	–	1.1093

下载: 导出CSV

| 显示表格

$\Delta {\text{T}}{{\text{R}}_{{t_e} = x}} = {\text{T}}{{\text{R}}_{{t_e} = x}} - {\text{T}}{{\text{R}}_{{\text{MSF}}}}$

(19)

不同的更新代价分别将△TR比率的优化率增加4.26%, 11.63%, 4.88%和10.93%。根据实验结果可知，当t_e=0.19, t_o=1.81时，自适应布线算法效果最好。由于较好的布线结果较少出现布线拥塞的情况，从而减少最大TDM比率。因此通过这些△TR的优化率可以得出自适应布线算法可以有效避免布线拥塞的情况出现，解决FPGA间的布线优化问题，优化布线结果，有效地减少系统时延。

4.4 LR分配算法和TDM比率优化算法有效性验证

本节将TDM比率分配算法和TDM比率优化算法运用到当前最先进的FPGA布线器ALIFRouter中进行比较。表6为LR分配算法和多层次的TDM比率优化算法的实验结果，并与ALIFRouter的实验数据进行对比。数据都是从同一环境中由8个线程运行的程序中获得的。表格中△TR的优化率是由MSFRoute在各测试用例上得到的线网组的最大TDM比率减去使用ALIFRouter、使用TDM比率分配算法和使用TDM比率优化算法后获得的最大TDM比率计算得到的。与ALIFRouter相比，两种算法可分别将ΔTR比率的优化率增加8.85%和10.39%。这些ΔTR的优化率表明LR分配算法和TDM比率优化算法可以有效地降低系统时延。

表 6 LR分配算法(即TDM比率分配算法)和TDM比率优化算法有效性验证

测试用例	ALIFRouter		只使用LR分配算法		只使用TDM比率优化算法
测试用例	△TR(10³)	Ratio	△TR(10³)	Ratio	△TR(10³)	Ratio
S1	1	1.0000	1	1.0000	1	1.0000
S2	384	1.0000	421	1.0964	419	1.1607
S3	1877	1.0000	1960	1.0442	2155	1.3726
S4	848	1.0000	889	1.0483	937	1.1222
S5	621	1.0000	635	1.0225	690	1.1424
S6	11994	1.0000	18550	1.5466	11989	1.4022
H1	799	1.0000	804	1.0063	804	0.0022
H2	7775	1.0000	7776	1.0001	7776	1.5496
H3	6220	1.0000	6419	1.0320	6429	1.1833
平均	–	1.0000	–	1.0885	–	1.1039

下载: 导出CSV

| 显示表格

5. 结束语

针对FPGA系统中运用TDM技术后导致系统时延增加的问题，本文提出了一种用于时分复用技术的多阶段协同优化FPGA布线方法，通过布线拓扑生成阶段、TDM比率分配阶段和TDM比率优化阶段3个阶段协同优化FPGA的可布线性和TDM比率分配结果。首先，为了生成高质量的布线拓扑，避免布线拥塞，解决FPGA间的布线优化问题，提出了自适应布线算法。其次，使用基于拉格朗日松弛的TDM比率分配算法，为布线图的边分配系统时延更小的初始TDM比率。然后，为了进一步减小最大线网组的TDM比率，通过一种多层次的TDM比率优化算法，同时缩减线网组和FPGA连接对的TDM比率。并且，为了提高MSCOFRouting的运行效率，在上述3个算法中使用多线程并行化方法，降低算法的运行时间。实验结果表明，与同类布线器相比，本文提出的MSCOFRouting能够获得最佳的系统时延优化质量。未来的工作中，将扩展本文算法应用到考虑带高速收发器的FPGA系统的TDM比率优化问题。

图 1 空时滤波器结构

下载: 全尺寸图片幻灯片

图 2 不同等效带宽下噪声信号的功率谱

下载: 全尺寸图片幻灯片

图 3 噪声等效带宽与PI抗干扰后卫星导航信号相关峰的关系

下载: 全尺寸图片幻灯片

图 4 噪声等效带宽与MVDR抗干扰后卫星导航信号相关峰的关系

下载: 全尺寸图片幻灯片

图 5 不同谱峰偏移的噪声信号功率谱

下载: 全尺寸图片幻灯片

图 6 噪声谱峰偏移与PI算法抗干扰后卫星导航信号相关峰的关系

下载: 全尺寸图片幻灯片

图 7 噪声谱峰偏移与MVDR算法抗干扰后卫星导航信号相关峰的关系

下载: 全尺寸图片幻灯片

图 8 对角加载量与相关峰衰减的关系

下载: 全尺寸图片幻灯片

图 9 原始PI算法和对角加载、子空间投影后算法性能的比较

下载: 全尺寸图片幻灯片

图 10 原始MVDR算法和对角加载、子空间投影后算法性能的比较

下载: 全尺寸图片幻灯片

参考文献(15)

[1]	ISSAM S M, ADNANE A, and MADIABDESSALAM A. Anti-jamming techniques for aviation GNSS-based navigation systems: Survey[C]. 2020 IEEE 2nd International Conference on Electronics, Control, Optimization and Computer Science (ICECOCS), Kenitra, Morocco, 2020: 1–4.
[2]	WANG Haiyang, YAO Zhicheng, FAN Zhiliang, et al. A robust STAP beamforming algorithm for GNSS receivers in high dynamic environment[J]. Signal Processing, 2020, 172: 107532. doi: 10.1016/j.sigpro.2020.107532
[3]	李成城, 李鹏程. 卫星导航自适应调零天线抗干扰技术[J]. 电子信息对抗技术, 2020, 35(6): 59–63. doi: 10.3969/j.issn.1674-2230.2020.06.017 LI Chengcheng and LI Pengcheng. Anti-jamming technology of adaptive nulling antenna of satellite navigation[J]. Electronic Information Warfare Technology, 2020, 35(6): 59–63. doi: 10.3969/j.issn.1674-2230.2020.06.017
[4]	LU Zukun, CHEN Feiqiang, LIN Honglei, et al. A novel method of distortionless correlation function after STAP for BOC[C]. Proceedings of the 2020 9th International Conference on Software and Computer Applications, Langkawi, Malaysia, 2020: 237–241.
[5]	聂俊伟, 牟卫华, 葛锐, 等. GNSS空时最大SINR天线阵抗干扰算法机理分析[J]. 信号处理, 2011, 27(7): 1030–1033. doi: 10.3969/j.issn.1003-0530.2011.07.011 NIE Junwei, MOU Weihua, GE Rui, et al. Analysis for mechanism of MaxSINR spatial-timal antijam array algorithm in GNSS[J]. Signal Processing, 2011, 27(7): 1030–1033. doi: 10.3969/j.issn.1003-0530.2011.07.011
[6]	CHEN Feiqiang, LU Zukun, LIU Zhe, et al. Tracking bias of navigation signal on performance of post-correlation MMSE anti-jamming algorithm[C]. China Satellite Navigation Conference (CSNC) 2020 ProceedingsChengdu, China. 2020: 646–655.
[7]	聂俊伟, 葛锐, 李敏, 等. 窄带假设对GNSS天线阵抗干扰性能评估的影响分析[J]. 国防科技大学学报, 2011, 35(5): 128–133. doi: 10.3969/j.issn.1001-2486.2011.05.024 NIE Junwei, GE Rui, LI Min, et al. The influence analysis of narrowband hypothesis to GNSS array anti-jamming performance evaluation[J]. Journal of National University of Defense Technology, 2011, 35(5): 128–133. doi: 10.3969/j.issn.1001-2486.2011.05.024
[8]	ZATMAN M. How narrow is narrowband?[J]. IEE Proceedings - Radar, Sonar and Navigation, 1998, 145(2): 85–91. doi: 10.1049/ip-rsn:19981670
[9]	FERNÁNDEZ-PRADES C, ARRIBAS J, and CLOSAS P. Robust GNSS receivers by array signal processing: Theory and implementation[J]. Proceedings of the IEEE, 2016, 104(6): 1207–1220. doi: 10.1109/JPROC.2016.2532963
[10]	RANKIN M L, O'BRIEN A, and GUPTA I J. Effects of sampling rate on STAP-based RFI suppression systems[C]. 2006 IEEE Antennas and Propagation Society International Symposium, Albuquerque, USA, 2006: 1425–1428.
[11]	黄国胜, 易争荣, 帅涛, 等. 多点约束空时抗干扰算法的研究[J]. 通信学报, 2012, 33(6): 157–163. doi: 10.3969/j.issn.1000-436X.2012.06.019 HUANG Guosheng, YI Zhengrong, SHUAI Tao, et al. Study on a multi-satellite constrained space-time anti-jam algorithm[J]. Journal on Communications, 2012, 33(6): 157–163. doi: 10.3969/j.issn.1000-436X.2012.06.019
[12]	ROSS J T, LEVA J L, and YODER S. Effect of partial-band interference on receiver estimation of C/N0: Measurements[C]. The 2001 National Technical Meeting of the Institute of Navigation, Long Beach, USA, 2001: 829–838.
[13]	O'BRIEN A J and GUPTA I J. Comparison of output SINR and receiver C/N_0 for GNSS adaptive antennas[J]. IEEE Transactions on Aerospace and Electronic Systems, 2009, 45(4): 1630–1640. doi: 10.1109/TAES.2009.5310324
[14]	马辰. 北斗卫星导航空间信号质量监测评估关键技术与实践[D]. [硕士论文], 西安电子科技大学, 2019. MA Chen. Key technology and practice of satellite navigation signal performance evaluation and monitoring[D]. [Master dissertation], Xidian University, 2019.
[15]	范特里斯, 毛士艺, 周荫清, 张其善, 译. 检测、估计和调制理论-卷1, part I-检测、估计和线性调制理论[M]. 北京: 电子工业出版社, 2007. VAN TREES H L, MAO Shiyi, ZHOU Yinqing, and ZHANG Qishan, translation. Detection, Estimation, and Modulation Theory[M]. Beijing: Publishing House of Electronics Industry, 2007.

施引文献

期刊类型引用(4)

1.	李贵勇，贾璐，宋利利. 宽带太赫兹大规模MIMO系统中的混合预编码. 重庆邮电大学学报(自然科学版). 2024(02): 220-228 . 百度学术
2.	叶子绿，许魁，夏晓晨，邓诚，魏琛，谢威. 基于强化学习的STAR-RIS辅助的通信抗干扰方法. 移动通信. 2024(06): 69-74 . 百度学术
3.	江浩，石旺旗，朱秋明，束锋，WANG Jiangzhou. 面向6G可重构智能超表面使能的近场海洋通信信道建模与信号传播机理研究. 电子与信息学报. 2024(12): 4383-4390 . 本站查看
4.	孙艺玮，顾琪，苏鑫，王菡凝，袁弋非. 可重构智能表面与网络控制中继器的性能比较. 移动通信. 2023(11): 33-38 . 百度学术