路径规划算法的高层综合设计研究

赖李洋; 郑锫骏; 梁海成; 李华伟

doi:10.11999/JEIT240210

路径规划算法的高层综合设计研究

doi: 10.11999/JEIT240210

1.
汕头大学电子系汕头 515063
2.
中国科学院计算技术研究所计算机体系结构国家重点实验室北京 100190

基金项目: 国家自然科学基金(62090024)，广东省自然科学基金(2022A1515011084)，广东省扬帆计划紧缺拔尖人才项目(140-14600602)，计算机体系结构国家重点实验室开放课题(CARCH201912, 140-15220011)

详细信息

作者简介:
赖李洋：男，副教授，硕士生导师，博士，研究方向为集成电路可测试性设计、电子设计自动化、容错计算、芯片设计

郑锫骏：男，硕士生，研究方向为FPGA设计、集成电路可测试性设计

梁海成：男，硕士，研究方向为FPGA设计、电子设计自动化

李华伟：女，研究员，博士生导师，博士，研究方向为数字电路设计自动化、测试验证、智能计算、近似计算

通讯作者:
赖李洋　lylai@stu.edu.cn

中图分类号: TN47; TP391.72
计量
- 文章访问数: 296
- HTML全文浏览量: 137
- PDF下载量: 39
- 被引次数: 7
出版历程
- 收稿日期: 2024-03-27
- 修回日期: 2024-06-15
- 网络出版日期: 2024-06-19
- 刊出日期: 2024-11-01

Case Study of High Level Synthesis on Path Planning Algorithm

1.
Department of Electronics and Information Engineering, Shantou University, Shantou 515063, China
2.
State key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China

Funds: The National Natural Science Foundation of China(62090024), The Natural Science Foundation of Guangdong Province(2022A1515011084), Guangdong Province Yangfan Program for Shortage and Top-notch Talents (140-14600602), Open Project of State Key Laboratory of Computer Architecture (CARCH201912, 140-15220011)

摘要

摘要: 随着机器人自动导航技术的快速发展，基于软件实现的路径规划算法在实时性上已无法满足许多应用场景的需求，这就要求对算法进行快速高效的硬件定制，从而获得低延时的性能加速。该文以机器人路径规划中的经典A*算法为对象，通过构建面向硬件设计的C/C++数据结构和函数流程优化，采用高层综合(HLS)实现快速的硬件架构探索和选取较优的设计方案，并完成硬件FPGA综合。实验数据表明，相较于传统寄存器传输级(RTL)开发模式，基于HLS开发模式的路径规划算法在FPGA实现上在开发效率、硬件性能和资源占用率上都有显著提升，验证了高层综合在硬件定制中的可行性和成本优势。
- 机器人自动导航 /
- 路径规划算法 /
- 高层综合 /
- 算法硬件加速
Abstract: With the advancement of robot automatic navigation technology, software-based path planning algorithms can no longer satisfy the needs in scenarios of many real-time applications. Fast and efficient hardware customization of the algorithm is required to achieve low-latency performance acceleration. In this work, High Level Synthesis (HLS) of classic A* algorithm is studied. Hardware-oriented data structure and function optimization, varying design constraints are explored to pick the right architecture, which is then followed by FPGA synthesis. Experimental results show that, compared to the conventional Register Transfer Level (RTL) method, the HLS-based FPGA implementation of the A* algorithm can achieve better productivity, improved hardware performance and resource utilization efficiency, which demonstrates the advantages of high level synthesis in hardware customization in algorithm-centric applications.
- Robot automatic navigation /
- Path panning algorithm /
- High Level Synthesis(HLS) /
- Hardware acceleration

HTML全文

1. 引言

波达方向估计(Direction Of Arrival, DOA)在雷达、通信、电子对抗、生物医学等领域有着广泛的应用。在现有的DOA估计方法中，基于稀疏重构的估计算法适用于非均匀阵列，能估计出比阵元数更多的信源个数，并且在低信噪比、低快拍、相干信源条件下具有优良的性能，因此得到了广大学者的关注^[1-20]。

基于稀疏重构的DOA估计方法需要选择一个稀疏度量，在预定义的离散字典网格上进行信号的重构。一些方法利用正则化系数综合重构精度与稀疏程度，这往往会导致估计结果精度无法保证^[3,4]。为了消除正则化系数的干扰，一系列无参数的估计方法被提出，如基于稀疏迭代的协方差估计(SParse Iterative Covariance based Estimation, SPICE)、迭代自适应(Iterative Adaptive Approach, IAA)、基于似然的稀疏参数估计(LIkelihood-based Estimation of Sparse parameters, LIKES)等^[5-7]，这些方法能在预定义的网格上重构信号，然而实际上待估计信源的位置往往不会正好定位在网格上，导致估计结果误差较大。

为了解决网格与信源位置不匹配的问题，一类方法是提高网格的密集度，但这会导致算法复杂度急剧上升^[8]；另一类方法是自适应的网格细化方法，徐文先等人^[9]在IAA算法的估计的基础上细化网格，进行自适应的字典校正，能准确估计出偏离网格的信源角度，但是细化网格会带来较大运算负担，并且当网格间的相关度过高时，根据有限等距性质(Restricted Isometry Property, RIP)准则，此时算法的估计能力反而大大降低^[10]。针对该问题，近年来国内外学者提出了基于偏移量的离网格稀疏重构估计方法^[11-15]。Gretsistas等人^[11]基于正交匹配的原则提出了同步正交匹配追踪(Simultaneous Orthogonal Matching Pursuit, SOMP)方法，交替优化信号分量和网格偏移量，实现了离网格的DOA估计，但是其计算量过高，并且部分情况下精度无法保证；Yang等人^[12]提出了一种离网稀疏贝叶斯推理(Off-Grid Sparse Bayesian Inference, OGSBI)的方法。在OGSBI方法基础上，一系列基于贝叶斯框架内的估计算法被提出，如Wu等人^[13]提出的基于期望最大化的改进稀疏贝叶斯推理方法等。然而上述方法大多涉及非凸优化，只能保证局部收敛，并且具有较大计算复杂度。Ma等人^[14]提出了一种基于迭代相位偏移校正的估计方法(Iterative Phase Offset Correction, IPOC)，该方法利用虚拟阵的等效单快拍接收数据结构进行DOA估计，应用在稀疏阵上能在增大阵列自由度的同时减小算法复杂度，但应用在均匀阵时估计精度受限；王洪雁等人^[15]提出了一种基于协方差矩阵重构的离网格DOA方法，但其功率求解涉及凸优化问题，具有较高的计算复杂度。与此同时，一类基于原子范数最小化及Toeplitz矩阵范德蒙德分解的无网格方法也被提出^[16-18]，但是这类方法仅适用于均匀阵列。对于非均匀阵列，Zhou等人^[19,20]提出了基于阵元内插的Toeplitz矩阵重构方法，并在互质阵列上取得了良好的效果。然而阵元内插不可避免地带来额外的估计误差，并且半定规划问题求解具有较高的计算复杂度。

针对上述算法存在的问题，本文将离网格的思想引入到IAA算法中，并对IAA算法功率计算进行修正，提出了一种基于修正IAA功率谱的离网格DOA估计算法(Off-Grid Iterative Adaptive Approach, OGIAA)。该算法可以解决信源位置与网格不匹配等问题，并且能够进行全局寻优以实现高精度的DOA估计。算法可以分为基于修正IAA算法功率谱的粗估计和基于最小平方误差准则的偏移量求解两个部分。首先，对IAA方法求出的功率谱进行修正，得到预定义网格上更加准确的信号功率分量和噪声功率分量；之后，基于最小平方误差准则构建代价函数，利用泰勒二次展开并最小化代价函数得到初始偏移量；最后，交替优化功率分量和网格偏移量，直至满足收敛条件。仿真验证了算法的有效性。

2. 基于修正IAA功率谱算法的粗估计

本文分别在第2节和第3节推导了OGIAA算法的两个步骤。首先，通过修正IAA算法求出的空域功率谱得到信号功率和波达角方向的粗估计结果。假设存在一个M元均匀线阵，各个阵元全向同性且阵元间距为d，远场处有K个信号 ${{\boldsymbol{s}}_k}$ 以角度 ${\theta _k}$ 抵达线阵，则阵列接收到的窄带信号数据可以表示为

$y(n) = \sum\limits_{k = 1}^K {{\boldsymbol{A}}({\theta _k}){{\boldsymbol{s}}_k}(n)} + {\boldsymbol{e}}(n),n = 1,2, \cdots ,N$

(1)

其中，N是快拍数， ${\boldsymbol{A}}$ 是大小为M×K的导向矢量矩阵， ${\boldsymbol{A}} = ({\boldsymbol{a}}({\theta _1}),{\boldsymbol{a}}({\theta _2}), \cdots ,{\boldsymbol{a}}({\theta _K}))$ ，在远场条件下，导向矢量 ${\boldsymbol{a}}({\theta _k}) = {{\text{e}}^{ - {\text{j}}2\pi md\sin {\theta _k}/\lambda }}$ ，则有限快拍下的信号协方差矩阵可以表示为

${\boldsymbol{R}} = \frac{1}{{\boldsymbol{N}}}{\boldsymbol{y}}{{\boldsymbol{y}}^{\text{H}}} = {\boldsymbol{AP}}{{\boldsymbol{A}}^{\text{H}}}$

(2)

其中， ${\boldsymbol{P}} = {\rm{diag}}({\boldsymbol{p}})$ ， ${\boldsymbol{p}}$ 表示K个信源的功率分量组成的向量。此外，除了期望信号 ${{\boldsymbol{s}}_k}$ 之外的干扰和噪声的协方差矩阵 ${\boldsymbol{Q}}({\theta _k})$ 可以表示为

${\boldsymbol{Q}}({\theta _k}) = {\boldsymbol{R}} - p({\theta _k}){\boldsymbol{a}}({\theta _k}){{\boldsymbol{a}}^{\text{H}}}({\theta _k})$

(3)

接下来根据基于加权最小二乘法 (Weighted Least Squares, WLS)的代价函数 ${J_{{\rm{WLS}}}}$ ^[21]得到波达角方向为 ${\theta _k}$ 的信号分量 ${{\boldsymbol{s}}_k}$

$\begin{split} {J_{{\rm{WLS}}}} =& \sum\limits_{n = 1}^N {{({\boldsymbol{y}}(n) - {\boldsymbol{a}}^{\text{H}}({\theta _k}){{\boldsymbol{s}}_k}(n))}}{Q^{ - 1}}({\theta _k})\\ & \cdot({\boldsymbol{y}}(n) - {\boldsymbol{a}}({\theta _k}){{\boldsymbol{s}}_k}(n)) ,n = 1,2, \cdots ,N \end{split}$

(4)

最小化式(4)得到

${{\boldsymbol{s}}_k}(n) = \frac{{{{\boldsymbol{a}}^{\text{H}}}({\theta _k}){{\boldsymbol{Q}}^{ - 1}}{\boldsymbol{y}}(n)}}{{{{\boldsymbol{a}}^{\text{H}}}({\theta _k}){{\boldsymbol{Q}}^{ - 1}}{\boldsymbol{a}}({\theta _k})}},n = 1,2, \cdots ,N$

(5)

根据式(3)和矩阵求逆定理，式(5)可以进一步化简为

${{\boldsymbol{s}}_k}(n) = \frac{{{{\boldsymbol{a}}^{\text{H}}}({\theta _k}){{\boldsymbol{R}}^{ - 1}}{\boldsymbol{y}}(n)}}{{{{\boldsymbol{a}}^{\text{H}}}({\theta _k}){{\boldsymbol{R}}^{ - 1}}{\boldsymbol{a}}({\theta _k})}},n = 1,2, \cdots ,N$

(6)

要求出信号在空域上的功率谱，首先基于等角度划分的原则在空间域上设置过完备表示的离散网格 $\varPhi = ({\phi _1},{\phi _2}, \cdots ,{\phi _Q})$ ，其中 $Q \gg M \gt K$ ，网格角度对应的导向矢量矩阵为 ${{\bar {\boldsymbol{A}}}}(\varPhi ) = ({\boldsymbol{a}}({\phi _1}), {\boldsymbol{a}}({\phi _2}), \cdots , {\boldsymbol{a}}({\phi _Q}))$ ，根据式(1)的信号模型，对每个网格点对应的功率分量进行初始估计

$\begin{split} {{{\bar {\boldsymbol{p}}}}^{(1)}}({\phi _q}) &= \frac{1}{N}\sum\limits_{n = 1}^N {{{\left| {{{{{\bar {\boldsymbol{s}}}}}^{(1)}}({\phi _q},n)} \right|}^2} } \\ & =\frac{1}{{{{\boldsymbol{a}}^{\text{H}}}({\phi _q}){\boldsymbol{a}}({\phi _q})N}}\sum\limits_{n = 1}^N {{{\left| {{{\boldsymbol{a}}^{\text{H}}}({\phi _q}){\boldsymbol{y}}(n)} \right|}^2}} \end{split}$

(7)

其中， ${\boldsymbol{\bar s}}({\phi _q},n)$ , ${\boldsymbol{\bar p}}({\phi _q})$ 分别是字典角度 ${\phi _q}$ 对应的信号分量和功率分量，根据式(6)进一步更新网格上的功率谱，在第i次迭代有

${{{\bar {\boldsymbol{R}}}}^{(i)}} = {{\bar {\boldsymbol{A}}}}(\varPhi ){{{\bar {\boldsymbol{P}}}}^{(i)}}(\varPhi ){{\bar {\boldsymbol{A}}}}(\varPhi )$

(8)

${{\boldsymbol{\bar s}}^{(i + 1)}}({\phi _q},n) = \frac{{{{\boldsymbol{a}}^{\text{H}}}({\phi _q}){{{\boldsymbol{\bar R}}}^{ - 1(i)}}{\boldsymbol{y}}(n)}}{{{{\boldsymbol{a}}^{\text{H}}}({\phi _q}){{{\boldsymbol{\bar R}}}^{ - 1(i)}}{\boldsymbol{a}}({\phi _q})}},n = 1,2, \cdots ,N$

(9)

${{\boldsymbol{\bar p}}^{(i + 1)}}({\phi _q}) = \frac{1}{N}\sum\limits_{n = 1}^N {{{\left| {{{{\boldsymbol{\bar s}}}^{(i + 1)}}({\phi _q},n)} \right|}^2}}$

(10)

其中， ${\boldsymbol{\bar P}}(\varPhi ) = {\rm{diag}}({\boldsymbol{\bar p}})$ ，循环至满足收敛条件 $\left\| {{{{\boldsymbol{\bar p}}}^{(i + 1)}}(\varPhi ) - {{{\boldsymbol{\bar p}}}^{(i)}}(\varPhi )} \right\|_2^2 \lt \varepsilon$ ，得到信号在预置网格上的功率谱。

如果信源数已知，则可以直接根据功率谱得到对应的功率谱峰值分量 ${\bar p_k}$ 和对应的粗估计结果 ${\bar \theta _k}$ 。如果信源数未知，则可以根据贝叶斯信息准则(Bayesian Information Criterion, BIC)^[22]进行粗估计。

$\begin{split} & {\text{BIC}}(\eta )\\ & \quad{\text{ = }}2MN\ln \left( {\sum\limits_{n = 1}^N {\left\| {{\boldsymbol{y}}(n) - \sum\limits_{k \in \{ J \cup j\} } {{\boldsymbol{a}}({\phi _k}){\boldsymbol{\hat s}}({\phi _k},n)} } \right\|} _2^2} \right) \\ & \qquad + \eta \ln (2MN) \\[-10pt] \end{split}$

(11)

其中， $\eta$ 是剩余的峰值数，j是功率谱峰值对应的网格位置，J是选中网格的集合。

假设附加噪声 $e(n)$ 为高斯白噪声，文献[]直接利用 $M \cdot \min ({\boldsymbol{\bar p}}({\bar \theta _k}))$ 求解噪声功率，但是这一表达式得到的噪声功率估计结果并不准确。本文利用IAA求解过程中得到的信号分量估计出噪声分量

$\bar e(n) = y(n) - \sum\limits_{k = 1}^K {A({{\bar \theta }_k})\bar s({{\bar \theta }_k},n)}$

(12)

求出噪声分量 ${\boldsymbol{\bar e}}(n)$ 的方差，就能得到估计更为准确的噪声功率 $\bar \sigma _n^2$ ，此时进一步对功率谱修正，得到修正后的峰值处功率分量 ${\hat p_k}$

${\hat p_k} = {\bar p_k} - \frac{{\bar \sigma _n^2}}{M}$

(13)

3. 基于最小平方误差准则的偏移量求解

接下来求解网格偏移量得到精细估计的结果。首先对协方差矩阵R进行向量化

${{\bar {\boldsymbol{y}}}} = {\text{vec}}({\boldsymbol{R}}) = {{\bar {\boldsymbol{A}}}}(\theta ){{\bar {\boldsymbol{p}}}} + {\boldsymbol{\bar i}}\sigma _n^2$

(14)

其中， ${{\bar {\boldsymbol{A}}}}(\theta ) = {\boldsymbol{A}}(\theta ) \odot {{\boldsymbol{A}}^ * }(\theta )$ ， $\odot$ 表示克罗内克积， ${\boldsymbol{\bar i}}$ 是M阶的单位阵I向量化后的单位向量。

根据 ${\boldsymbol{\bar y}}$ 的表达式，结合粗估计结果，基于最小平方误差准则设置目标函数F

$F({\bar \theta _k}) = \left\| {{\boldsymbol{\bar y}} - {\boldsymbol{\bar i}}\sigma _n^2 - \sum\limits_{k = 1}^K {{{\bar {\boldsymbol{A}}}}({{\bar \theta }_k}){{\hat p}_k}} } \right\|_2^2 = {{\boldsymbol{z}}^{\text{H}}}({\bar \theta _k}){\boldsymbol{z}}({\bar \theta _k})$

(15)

其中， ${\boldsymbol{z}}({\bar \theta _k}) = {\boldsymbol{\bar y}} - {{\bar {\boldsymbol{i}}}}\sigma _n^2 - \displaystyle\sum\nolimits_{k = 1}^K {{{\bar {\boldsymbol{A}}}}({{\bar \theta }_k}){{{{\hat {\boldsymbol{p}}}}}_k}}$ ，接下来分别求解目标函数F对 ${\bar \theta _k}$ 的1阶导数和2阶导数

$F'({\bar \theta _k}) = 2{\text{real}}\left({\left( - \sum\limits_{k = 1}^K {{{\bar {\boldsymbol{A}}'}}({{\bar \theta }_k}){{\hat p}_k}} \right)^{\text{H}}}{\boldsymbol{z}}\right)$

(16)

$\begin{split} F''({\bar \theta _k}) =& 2{\text{real}}({( - \sum\limits_{k = 1}^K {{{\bar {\boldsymbol{A}}''}}({{\bar \theta }_k}){{\hat p}_k}} )^{\text{H}}}{\boldsymbol{z}}) \\ & + 2{\text{real}}\left({\left( - \sum\limits_{k = 1}^K {{{\bar {\boldsymbol{A}}'}}({{\bar \theta }_k}){{\stackrel \frown{p} }_k}} \right)^{\text{H}}}\right.\\ & \left.\cdot\left( - \sum\limits_{k = 1}^K {{{\bar {\boldsymbol{A}}'}}({{\bar \theta }_k}){{\stackrel \frown{p} }_k}} \right)\right) \end{split}$

(17)

其中， ${\text{real}}( \cdot )$ 表示取括号内复数变量的实部，在目标函数F中对第k个信源的粗估计结果 ${\bar \theta _k}$ 进行2阶泰勒展开，得到新的代价函数 $\bar F$

$\bar F = F({\bar \theta _k}) + F'({\bar \theta _k}){\delta _k} + \frac{1}{2}F''({\bar \theta _k})\delta _k^2$

(18)

其中， ${\delta _k}$ 是 ${\hat \theta _k}$ 的偏移量，为了求出代价函数 $\bar F$ 的最小值，将 $\bar F$ 对偏移量 ${\delta _k}$ 求导，并令导数为零，解得

$\delta _k^{(1)} = - F'({\bar \theta _k})/F''({\bar \theta _k})$

(19)

求解K次得到K个偏移量，则第1次DOA估计的结果为

$\hat \theta _k^{(1)} = {\bar \theta _k} + \delta _k^{(1)}$

(20)

将第1次估计的结果代回IAA算法中，重复式(7)—式(10)，求出新的信号功率分量和噪声功率分量，再代入式(15)—式(19)中求出新的偏移量。交替优化功率和偏移量，假设循环L次后满足收敛条件 $\delta _k^{(L)} - \delta _k^{(L - 1)} \le \beta$ ，结束循环。最终估计结果为

$\hat \theta _k^{(L)} = {\bar \theta _k} + \delta _k^{(1)} + \cdots + \delta _k^{(L)}$

(21)

综上所述，算法具体的步骤如下：

步骤1　根据式(7)—式(10)的IAA算法得到参数粗估计的结果 ${\bar \theta _k}$ ， ${\bar p_k}$ ， $\bar \sigma _n^2$ ，并且根据式(13)对功率谱进行修正，得到修正后的信号功率 ${\hat p_k}$ 。

步骤2　基于最小平方误差准则，根据粗估计的结果设置代价函数 ${\bar F^{(1)}}$ ，按式(15)—式(19)最小化 ${\bar F^{(1)}}$ 得到偏移量 $\delta _k^{(1)}$ ，根据式(20)能得到精细估计结果 $\hat \theta _k^{(1)}$ 。

步骤3　将步骤2的估计结果代回IAA算法中，更新功率谱并修正，得到 $\hat p_k^{(1)}$ , $\bar \sigma _n^{2(1)}$ 。

步骤4　利用更新后的参数重新构建目标函数 ${\bar F^{(2)}}$ ，最小化 ${\bar F^{(2)}}$ 得到新的偏移量 $\delta _k^{(2)}$ 。

步骤5　重复步骤3、步骤4，交替优化功率分量和偏移量，当满足 $\delta _k^{(L)} - \delta _k^{(L - 1)} \le \beta$ 或达到最大迭代次数 ${i_{\max }}$ 时结束循环，得到最终的估计结果 $\hat \theta _k^{(L)} = {\bar \theta _k} + \delta _k^{(1)} + \cdots + \delta _k^{(L)}$ 。

4. 仿真验证

本节首先研究OGIAA算法中的一些预定义参数，如字典间隔、最大迭代次数的取值对估计结果的影响。之后分别在均匀阵与互质阵上进行仿真实验，通过对比SOMP^[10], OGSBI^[11]和IPOC^[14]等算法，验证本文提出的OGIAA算法的有效性。

仿真1　为了探究最大迭代次数和字典网格间隔对算法估计结果的影响，设置阵元数M=10，快拍数N=100，待估计信源个数K=5，波达角方向分别为40.80°, 17.78°, 5.25°, –28.28°, –51.30°，假设估计结果 $\left| {{{\hat \theta }_i} - {\theta _i}} \right| \le {0.15^ \circ }$ 为估计正确，在每个条件下进行T=200次蒙特卡罗实验。不同迭代次数i_max和不同网格间隔r在信噪比–10～30 dB下的估计正确率分别如图1(a)、图1(b)所示。

图 1 不同参数条件下的估计正确率

下载: 全尺寸图片幻灯片

由图1可以看到，图1(a)中除了1次迭代的条件下精度明显降低，在两次迭代后几乎都能达到最高精度，可见本文所提算法具有较快的收敛速度。图1(b)中除了网格间隔为4°时在低信噪比情况下估计精度略有降低，其余网格间隔下的估计精度几乎一致，可以看出预定义字典间隔的设置对所提算法估计精度影响有限。综上所述，在计算量受限的场合，减少最大迭代次数或者增大网格间隔都是一种减少算法运算量的有效选择。

仿真2　假设存在阵元数M=10的均匀阵列，待估计信源个数K=2，信源波达角分别为 ${\theta _1}$ =40.8°, ${\theta _2}$ =–51.3°，信噪比SNR=10 dB，快拍数N=100，设置字典离散网格间隔为r=2°，图2为本文所提OGIAA算法与IAA, SOMP, OGSBI和IPOC算法的空域谱对比结果。

图 2 不同算法在空域网格上的幅度对比图

下载: 全尺寸图片幻灯片

由图2放大的部分可以看到，由于待估计信源角度不会正好定位在网格上，所以IAA算法峰值对应的网格无法正确估计出信源角度，而其余4种离网格估计方法都能得到准确的估计结果。为了进一步说明本文所提算法的有效性，将算法估计精度用均方根误差(Root Mean Squared Error, RMSE)表示

${\rm{RMSE}}{\text{ = }}\sqrt {\frac{{\displaystyle\sum\limits_{i = 1}^T {\displaystyle\sum\limits_{k = 1}^K {[{{({{\hat \theta }_{ik}} - {\theta _k})}^2}]} } }}{{TK}}}$

(22)

保持其他条件不变，在–10～30 dB的范围内改变信噪比的取值，并令快拍数N分别为200和20，在每个条件下进行T=200次蒙特卡罗实验，则不同算法的估计精度为随信噪比的变化如图3所示。

图 3 不同快拍数和信噪比下的算法估计精度

下载: 全尺寸图片幻灯片

由图3(a)可以看到，当N=200时，由于网格不匹配的原因，IAA算法估计精度最低，而OGSBI算法和SOMP算法无法做到全局寻优，导致精度受限。IPOC算法对均匀阵列的虚拟阵进行处理，虽然减少了计算量，但是估计精度受到限制。MUSIC算法虽然在高信噪比下具有较高的估计精度，然而在低信噪比下精度不足。相比之下，本文提出的OGIAA算法精度最高，并且能接近克拉默-拉奥界(Cramer-Rao Bound, CRB)。由图3(b)可以看到，当N=20时，OGSBI算法和MUSIC算法在高信噪比下能取得较好的效果，但是在低信噪比下精度就无法保证，而本文所提算法在不同信噪比和快拍数下都具有更高的估计精度，并且在高信噪比下估计精度能接近CRB。

仿真3　互质阵列由两个阵元数互质的子阵组成，利用2阶相关矩阵向量化，并删去其中重复的元素，观察剩余数据的结构，其对应的虚拟阵列具有更大的阵列口径和高达 $O({M_1}{M_2})$ 的阵列自由度，因此在近几年，基于互质阵列扩展虚拟阵列的信号处理技术得到了广大学者的关注。为了说明本文算法应用在高自由度的稀疏阵上仍然具有较高的估计精度，如所示，假设存在一个 ${M_1} = 3$ , ${M_2} = 5$ 的互质阵列，总阵元个数 $M = 7$ ，利用2阶相关矩阵向量化，可以得到阵元数 $\bar M = 21$ 的中间连续，两端稀疏的扩展虚拟阵列。

图 4 互质阵列结构

下载: 全尺寸图片幻灯片

对虚拟阵列等效单快拍接收数据 ${\boldsymbol{\tilde y}}$ 进行处理，此时更改代价函数F的表达式为

${{\tilde {\boldsymbol{y}}}} = {{{\boldsymbol{G}}\bar {\boldsymbol{y}}}} = {{\tilde {\boldsymbol{Ap}}}} + {{\bar {\boldsymbol{i}}}}\sigma _n^2$

(23)

$F = \left\| {{{\tilde {\boldsymbol{y}}}} - {{\tilde {\boldsymbol{i}}}}\sigma _n^2 - \sum\limits_{k = 1}^K {{{\tilde {\boldsymbol{A}}}}({{\bar \theta }_k}){{\hat p}_k}} } \right\|_2^2 = {{{\tilde {\boldsymbol{z}}}}^{\text{H}}}{{\tilde {\boldsymbol{z}}}}$

(24)

其中， ${{\tilde {\boldsymbol{z}}}} = {{\tilde {\boldsymbol{y}}}} - {{\tilde {\boldsymbol{i}}}}\sigma _n^2 - \displaystyle\sum\nolimits_{k = 1}^K {{{\tilde {\boldsymbol{A}}}}({{\bar \theta }_k}){{\hat p}_k}}$ ，G是大小为 $\bar M \times {M^2}$ 的选择矩阵，每行只有一个单元为1，其余单元都为0，目的是剔除 ${{\tilde {\boldsymbol{y}}}}$ 中的重复元素，构建虚拟阵列的单快拍接收数据。 ${{\tilde {\boldsymbol{A}}}}$ 是非均匀虚拟阵对应的导向矢量矩阵， ${{\tilde {\boldsymbol{i}}}}$ 是除了中间单元为1其余单元都为0的列向量。

设置信噪比SNR=20 dB，快拍数N=200，待估计信源个数K=9，其波达角方向在 ${\theta _1}$ =–60.3°， ${\theta _2}$ =60.8°间均匀分布。图5为利用虚拟阵列单快拍数据进行DOA估计的结果。可以看到，对于总阵元数为7的互质阵来说，利用本文算法对其虚拟阵列的单快拍接收数据进行DOA估计，可以准确估计出比阵元数更多的信源个数。

图 5 互质虚拟阵估计结果

下载: 全尺寸图片幻灯片

为了进一步说明本文算法在互质阵DOA估计上的优势，假设待估计信源波达角为40.8°, –51.3°，保持其他条件不变，分别改变信噪比和快拍数的取值，每个条件下进行T=200次蒙特卡罗实验，不同算法估计精度随信噪比和快拍数的变化如图6所示。由图6(a)可以看到，当N=200时，对于虚拟阵列等效单快拍接数据，SOMP和OGSBI算法无法做到全局寻优，而IPOC算法和OGIAA算法具有更高的估计精度。MUSIC算法由于只能对虚拟阵列中间连续阵元进行平滑处理，导致两端稀疏部分阵元的接收数据丢失，因此算法精度受限。由图6(b)可以看到，当N=20时，IPOC算法在低信噪比情况下精度无法保证。相比之下，OGIAA算法仍然具有较高的估计精度。综上所述，在不同信噪比和快拍数下，本文所提OGIAA算法能做到全局寻优，具有更强的估计性能。

图 6 不同快拍数和信噪比下的算法估计精度

下载: 全尺寸图片幻灯片

5. 结论

本文提出了一种基于修正IAA算法功率谱的离网格DOA估计方法，有效解决了常规稀疏重构算法字典网格与信源位置不匹配问题，实现了高精度的离网格DOA估计。本文算法以修正IAA算法得到的功率谱构建基于最小平方误差准则的代价函数，并通过泰勒展开最小化代价函数求解偏移量，原理清晰，结构简单，无正则化系数的干扰。仿真结果表明，相比其他离网格DOA估计方法，本文算法具有更高的估计精度，能准确估计出偏离网格的信源波达角方向。

图 1 实现高层综合的基本流程

下载: 全尺寸图片幻灯片

图 2 切片函数的读操作示意图

下载: 全尺寸图片幻灯片

图 3 格点信息的数据结构

下载: 全尺寸图片幻灯片

图 4 开启列表数组

下载: 全尺寸图片幻灯片

图 5 原始算法中的开启列表操作

下载: 全尺寸图片幻灯片

图 6 开启列表操作优化

下载: 全尺寸图片幻灯片

图 7 优先级队列实现的地图路径

下载: 全尺寸图片幻灯片

图 8 堆栈实现的地图路径

下载: 全尺寸图片幻灯片

图 9 队列实现的地图路径

下载: 全尺寸图片幻灯片

图 10 地图样式1

下载: 全尺寸图片幻灯片

图 11 地图样式2

下载: 全尺寸图片幻灯片

图 12 地图样式3

下载: 全尺寸图片幻灯片

图 13 地图样式4

下载: 全尺寸图片幻灯片

1 A*算法的基本流程

(1)初始化开启列表和关闭列表为空
(2)将七点插入开启列表中
(3)while(开启列表不为空)
(4) 从开启列表中取出最小F值的格点作为当前格点，并将之加　　入关闭列表
(5) 　foreach(当前格点的相邻格点)
(6) 　　if(该格点在关闭列表中或是故障格点) then(跳过该格点)
(7) 　　elsif(该格点在开启列表中) then(比较通过当前格点计算　　　　得出的F值是否更小，若更小则更新该格点的F值，设其　　　　父节点为当前节点，并将之插入开启列表)
(8) 　　elsif(该格点不在开启列表中) then(通过当前节点计算该　　　　节点的F值，设其父亲节点为当前节点，并将之插入开启　　　　列表)
(9) 　　elsif(该格点为终点) then(设其父节点为当前节点，并通　　　　过追踪父节点链条至起点，输出起点到终点的路径，算　　　　法结束)
(10) end_foreach
(11)end_while
(12)if(开启列表为空) then(路径搜索失败)

下载: 导出CSV

表 1 SOC FPGA 芯片 PL 资源

资源名称	总数
逻辑单元 LUT	87 840
LUTRAM	57 600
触发器 Flip-flop(FF)	175 680
BRAM	128
I/O 引脚	256
全局时钟缓冲器 BUFG	352

下载: 导出CSV

表 2 15×15地图下不同开启列表优化比较

数据结构	LUT个数	FF个数	BRAM个数	运行时长(ns)
优先队列	2 485	2 807	3.0	18 598
队列	2 137	2 755	2.5	44 325
堆栈	2 148	2 739	2.5	38 779

下载: 导出CSV

表 3 使用优先队列数据结构的HLS和RTL开发模式比较

FPGA开发模式	运行时间(ns)	LUT个数	FF个数	BRAM个数
HLS	483 445	3 208	3 303	34.5
RTL	523 046	7 253	7 161	59.5

下载: 导出CSV

表 4 使用堆栈数据结构的HLS和RTL开发模式比较

FPGA开发模式	运行时间(ns)	LUT个数	FF个数	BRAM个数
HLS	3 305 830	1 669	1 523	25
RTL	5 987 348	7 313	7 065	56

下载: 导出CSV

表 5 使用队列数据结构的HLS和RTL开发模式比较

FPGA开发模式	运行时间(ns)	LUT个数	FF个数	BRAM个数
HLS	3 389 425	1 756	1 555	25
RTL	5 598 080	7 317	7 053	56

下载: 导出CSV

参考文献(17)

[1]	郑岩. 改进势场蚁群算法的机器人自主导航应用研究[D]. [硕士论文], 重庆三峡学院, 2020. doi: 10.27883/d.cnki.gcqsx.2020.000061. ZHENG Yan. Application of improved potential field ant colony algorithm for autonomous robot navigation[D]. [Master dissertation], Chongqing Three Gorges University, 2020. doi: 10.27883/d.cnki.gcqsx.2020.000061.
[2]	郭炜, 魏继增, 郭筝, 等. SoC设计方法与实现[M]. 3版. 北京: 电子工业出版社, 2017: 23–24. GUO Wei, WEI Jizeng, GUO Zheng, et al. SoC Design Methodology and Implementation[M]. 3rd ed. Beijing: Publishing House of Electronics Industry, 2017: 23–24.
[3]	陈志盛, 朱予涵, 刘耿耿, 等. 考虑流端口数量约束下的连续微流控生物芯片流路径规划算法[J]. 电子与信息学报, 2023, 45(9): 3321–3330. doi: 10.11999/JEIT221168. CHEN Zhisheng, ZHU Yuhan, LIU Genggeng, et al. Flow-path planning algorithm for continuous-flow microfluidic biochips with strictly constrained flow ports[J]. Journal of Electronics & Information Technology, 2023, 45(9): 3321–3330. doi: 10.11999/JEIT221168.
[4]	CORMEN T H, LEISERSON C E, RIVEST R L, 等, 殷建平, 徐云, 王刚, 等. 译. 算法导论[M]. 3版. 北京: 机械工业出版社, 2013: 374–376. CORMEN T H, LEISERSON C E, RIVEST R L, et al, YIN Jianping, XU Yun, WANG Gang, et al. translation. Introduction to Algorithms[M]. 3rd ed. Beijing: China Machine Press, 2013: 374–376.
[5]	ABDOKASEB. A C Program to implement A* Search Algorithm[EB/OL]. https://github.com/abdokaseb/AStar-C/, 2022.
[6]	Mentor, A Siemens Business. HLS Bluebook[M]. Software Version v10. 5b, 2020.
[7]	ALTOYAN W and ALONSO J J. Investigating performance losses in high-level synthesis for stencil computations[C]. 2020 IEEE 28th Annual International Symposium on Field-Programmable Custom Computing Machines, Fayetteville, USA, 2020: 195–203. doi: 10.1109/FCCM48280.2020.00034.
[8]	潘妍, 程岳, 高雅濛. 面向FPGA的高层次综合技术综述[J]. 信息技术与信息化, 2022(3): 96–99. DOI: 10.3969/j.issn.1672-9528.2022.03.024. PAN Yan, CHENG Yue, and GAO Yameng. An overview of high-level synthesis techniques for FPGAs[J]. Information Technology and Informatization, 2022(3): 96–99. DOI: 10.3969/j.issn.1672-9528.2022.03.024.
[9]	石添介, 刘飞阳, 田径, 等. 基于高层次综合的FPGA循环神经网络加速器设计[J]. 信息技术与信息化, 2022(1): 151–153. DOI: 10.3969/j.issn.1672-9528.2022.01.042. SHI Tianjie, LIU Feiyang, TIAN Jing, et al. Design of FPGA recurrent neural network accelerator based on high-level synthesis[J]. Information Technology and Informatization, 2022(1): 151–153. DOI: 10.3969/j.issn.1672-9528.2022.01.042.
[10]	叶海雄, 陶宁蓉, 匡兴红, 等. 基于Catapult C高层次综合工具平台优化运动检测算法的研究[J]. 电子设计工程, 2017, 25(14): 1–4. doi: 10.14022/j.cnki.dzsjgc.2017.14.001. YE Haixiong, TAO Ningrong, KUANG Xinghong, et al. Optimization motion detection algorithm based on Catapult C high-level synthesis tool platform[J]. Electronic Design Engineering, 2017, 25(14): 1–4. doi: 10.14022/j.cnki.dzsjgc.2017.14.001.
[11]	徐瑞帆, 肖有为, 罗进, 等. 高层次综合综述[J]. 微纳电子与智能制造, 2021, 3(2): 74–79. doi: 10.19816/j.cnki.10-1594/tn.2021.02.074. XU Ruifan, XIAO Youwei, LUO Jin, et al. The overview of high-level synthesis[J]. Micro/Nano Electronics and Intelligent Manufacturing, 2021, 3(2): 74–79. doi: 10.19816/j.cnki.10-1594/tn.2021.02.074.
[12]	PANDA P R, SHARMA N, KURRA S, et al. Exploration of loop unroll factors in high level synthesis[C]. 2018 31st International Conference on VLSI Design and 2018 17th International Conference on Embedded Systems. Pune, India, 2018: 465–466. doi: 10.1109/VLSID.2018.115.
[13]	谢晓燕, 张玉婷, 刘镇弢. 高层次综合特征检测算法的FPGA实现[J]. 实验室研究与探索, 2018, 37(1): 93–97,117. doi: 10.3969/j.issn.1006-7167.2018.01.023. XIE Xiaoyan, ZHANG Yuting, and LIU Zhentao. FPGA implementation of feature detection algorithm based on high level synthesis[J]. Research and Exploration in Laboratory, 2018, 37(1): 93–97,117. doi: 10.3969/j.issn.1006-7167.2018.01.023.
[14]	申懿鑫, 韩跃平, 唐道光. 高层次综合的SM4算法硬件实现与优化[J]. 单片机与嵌入式系统应用, 2023, 23(8): 11–14. SHEN Yixin, HAN Yueping, and TANG Daoguang. hardware implementation and optimization of SM4 algorithm based on high-level synthesis[J]. Microcontrollers & Embedded Systems, 2023, 23(8): 11–14.
[15]	周成瑞, 杨玲玲. 基于A星算法的全向移动机器人仿真研究[J]. 电脑与信息技术, 2023, 31(3): 29–31. doi: 10.3969/j.issn.1005-1228.2023.03.008. ZHOU Chengrui and YANG Lingling. Simulation research on omnidirectional mobile robot based on A* algorithm[J]. Computer and Information Technology, 2023, 31(3): 29–31. doi: 10.3969/j.issn.1005-1228.2023.03.008.
[16]	王小丽. 基于Vivado HLS雾天图像预处理IP核设计[J]. 电脑编程技巧与维护, 2023(4): 158–161. doi: 10.16184/j.cnki.comprg.2023.04.020. WANG Xiaoli. Vivado HLS foggy sky image preprocessing IP core based design[J]. Computer Programming Skills & Maintenance, 2023(4): 158–161. doi: 10.16184/j.cnki.comprg.2023.04.020.
[17]	韦苏伦, 陶青川. 基于HLS的MobileNet加速器实现[J]. 现代计算机, 2023, 29(8): 91–97. doi: 10.3969/j.issn.1007-1423.2023.08.015. WEI Sulun and TAO Qingchuan. Realization of MobileNet accelerator based on HLS[J]. Modern Computer, 2023, 29(8): 91–97. doi: 10.3969/j.issn.1007-1423.2023.08.015.

施引文献

期刊类型引用(6)

1.	王铎澎，黄华，张生凤. 一种改进型KB-RLS算法在自干扰对消中的工程应用. 舰船电子对抗. 2024(01): 89-94 . 百度学术
2.	樊军，支俊峰，杨莹. 广播电视无线发射中多径干扰的抑制技术研究. 电视技术. 2024(06): 129-131+135 . 百度学术
3.	熊彪. 低压输电线路载波通信多耦合干扰抑制方法设计. 环境技术. 2024(06): 131-136+142 . 百度学术
4.	陆海锋，梁卓明. 基于深度卷积网络的超宽带频谱信号识别. 计算机仿真. 2024(11): 220-224 . 百度学术
5.	董秀娟，兰建平，梁西银. 用于复杂环境的多径电子通信信号抗干扰仿真. 计算机仿真. 2023(01): 218-222 . 百度学术
6.	路雷，褚建军，唐燕群，陶业荣，伍哲舜，郑承武，陈琦. 基于卷积长短时记忆深度神经网络的带内全双工非线性数字自干扰消除. 电子与信息学报. 2022(11): 3874-3881 . 本站查看

其他类型引用(1)

资源附件(0)

访问统计

图(13) / 表(6)

计量

文章访问数: 296
HTML全文浏览量: 137
PDF下载量: 39
被引次数: 7

1. 引言
2. 基于修正IAA功率谱算法的粗估计
3. 基于最小平方误差准则的偏移量求解
4. 仿真验证
5. 结论

姓名
邮箱
手机号码
标题
留言内容
验证码

留言板

路径规划算法的高层综合设计研究

doi: 10.11999/JEIT240210

通讯作者:
赖李洋　lylai@stu.edu.cn

计量

Case Study of High Level Synthesis on Path Planning Algorithm

1. 引言

2. 基于修正IAA功率谱算法的粗估计

3. 基于最小平方误差准则的偏移量求解

4. 仿真验证

5. 结论

期刊类型引用(6)

其他类型引用(1)

计量

目录

1. 引言

2. 基于修正IAA功率谱算法的粗估计

3. 基于最小平方误差准则的偏移量求解

4. 仿真验证

5. 结论

留言板

路径规划算法的高层综合设计研究

doi: 10.11999/JEIT240210

通讯作者: 赖李洋 lylai@stu.edu.cn

计量

出版历程

Case Study of High Level Synthesis on Path Planning Algorithm

1. 引言

2. 基于修正IAA功率谱算法的粗估计

3. 基于最小平方误差准则的偏移量求解

4. 仿真验证

5. 结论

期刊类型引用(6)

其他类型引用(1)

计量

出版历程

目录

1. 引言

2. 基于修正IAA功率谱算法的粗估计

3. 基于最小平方误差准则的偏移量求解

4. 仿真验证

5. 结论

通讯作者:
赖李洋　lylai@stu.edu.cn