A Design of On-chip Network with Self-adaptive Fault-Tolerant Link
-
摘要: 随着芯片制程不断深入到亚微纳米级别,技术节点的持续缩小加速了片上网络中链路故障的发生。故障链路的增多降低了可用的路由路径数量,并可能导致严重的流量拥塞甚至系统崩溃。为了保证在遭遇故障链路时数据包的正常传输,该文提出一种基于自适应容错链路的片上网络设计(AFL_NoC),它能够将遭遇故障链路的数据包转发到另一条可逆链路上。该方案包括了可逆链路的具体实现以及相应的分布式控制协议。这种动态容错链路设计充分利用了网络中空闲的可用链路资源,确保了在遭遇链路故障的情况下网络通信不会中断。与先进的容错偏转路由算法QFCAR-W相比,AFL_NoC平均延迟降低10%,面积开销减少了14.2%,功耗开销减少了9.3%。Abstract: As chip manufacturing has advanced to the sub-micro-nanometer scale, shrinking technology nodes are accelerating link failures in on-chip network, and the growth of failure links reduces the number of available routing paths and might lead to severe traffic congestion or even system crashes. The difficulty in maintaining the correctness of the on-chip system dramatically rises as the technology node shrinks. Previous schemes typically utilize deflection algorithms to bypass packets. However, they incur additional transmission latency due to hop count and raise the probability of deadlock. In order to achieve normal packet transmission when encountering faulty links, a self-Adaptive Fault-tolerant Link NoC design (AFL_NoC) is proposed, which redirects packets encountering a faulty link to another reversible link. The scheme contains a specific implementation of the reversible link and the associated distributed control protocol. The dynamic fault-tolerant link design fully utilizes the idle, available link and ensures that the network communication is not interrupted in case of link failures. Compared with the advanced fault-tolerant deflection routing algorithm QFCAR-W, AFL_NoC can reduce the average delay by 10%, the area overhead by 14.2%, and the power overhead by 9.3%.
-
Key words:
- System-on-Chip (SoC) /
- Network-on-Chip (NoC) /
- Fault-tolerance /
- Router architecture /
- Routing algorithm
-
1. 引言
现代目标跟踪系统[1-6]中,传感器的智能性和可控性越来越高,科学制定最优管理策略以控制传感器合理运行,能够很大程度上改善并优化传感器接收信息的质量,从而显著提升目标跟踪系统的整体性能,这就是传感器控制(亦称为传感器管理)的根本意义之所在。传感器控制是为了满足操作约束并完成相应的操作目标,在一个灵活可调节的传感器系统中进行相应的自由度控制[7],其目的是在正确的时间将正确平台上的可控传感器引导至最优的观测状态,从而获取最优的量测过程[8,9]。然而,复杂的多目标跟踪系统往往伴随着目标的不确定性,同时还受传感器检测的不确定性以及杂波干扰等因素的影响,使得能有效决策最优传感器控制的方法研究极为困难。
近些年,基于有限集统计(FInite Set STatistics, FISST)理论[10-12]的多目标跟踪方法因其更为科学的多目标建模方式而广受关注。在FISST理论框架下更有利于对集群目标进行跟踪估计,对于多目标跟踪估计整体优化的传感器控制决策方案的制定是极其便利的。目前已经产生了一些颇为有效的传感器控制方法并应用于目标跟踪优化,这些传感器控制方法基本可分为两大类:一种是基于信息驱动,此类方法通过多目标概率密度的信息增益来评估量测过程的优劣,而信息增益可以由各类散度函数来量化(例如Kullback-Leible散度[13]、Cauchy-Schwarz散度[14,15]、Rényi散度[16]、巴氏距离[8]等),旨在控制传感器获得最大的信息增益。另一种是基于任务驱动,此类方法基于特定任务优化而决策,通常在实际应用环境下能够发挥其重要作用,包括基于目标威胁评估[17,18]、基于目标势估计方差[19]、基于状态和势估计误差的后验期望[20]、基于目标势的后验期望[21]等。基于任务驱动的传感器控制的目标更为明确,直接针对多目标跟踪系统的预期性能和特定要求。但是如何科学设计任务规划准则,以增强滤波器在复杂环境下的多目标综合多特征估计的稳健性,显然还值得深入研究。
随着高精度传感器不断运用和被跟踪目标的集群化发展,对多扩展目标跟踪(Multiple Extended Targets Tracking, METT)[22-28]问题的深入研究已经成为现代目标跟踪领域的焦点。METT借助辨识度更高且更丰富的量测信息利用信息融合技术可获得各目标更多的特征估计,例如可从目标观测的稀疏点量测集中提取各目标的形状轮廓信息,这对目标的深度识别具有极其重要的现实意义。但是,由于METT中每个目标对应了多个量测,目标与量测之间的关联关系更加模糊和不确定,为METT的实现过程带来很大的挑战。另外,METT中借助传感器控制技术进行跟踪优化,需要在最优决策中考虑更多的特征优化(如形状估计的优化),这对科学制定传感器控制的最优任务准则提出了更为综合的要求。
鉴于此,本文利用随机矩阵(Random Matrix, RM)将扩展目标的形状轮廓建模为椭圆,这能够合理有效地描述扩展目标的大小和方向信息,将多扩展目标建模为多伯努利随机集,通过控制多扩展目标多特征的后验离差最小,使算法在优化多扩展目标运动状态估计的同时,也优化了目标形状的估计,最后采用伽马高斯逆威沙特多伯努利(Gamma Gaussian Inverse Wishart Multi-Bernoulli, GGIW-MBer)滤波器实现本文提出的多扩展目标跟踪中的传感器控制策略。值得一提的是,本文所提出的基于广义离差的优化准则也可拓展在基于多特征距离的复杂优化问题上。本文的主要贡献为:给出了加权广义最优子模式分配(Weighted Generalized Optimal Sub-Pattern Assignment, WGOSPA)距离构造多目标多特征估计的广义离差,同时研究提出了多特征融合下的传感器控制最优决策方法,优化了多扩展目标跟踪系统的整体性能。本文所提传感器控制方法的基本原理如图1所示。
2. 多扩展目标的随机集模型
假设
k−1 时刻多扩展目标的状态集合为ξk−1={ξ(i)k−1}Nξ,k−1i=1ξ(i)k−1 = (γ(i)k−1,x(i)k−1,X(i)k−1) (1) 其中,
ξk−1 表示k−1 时刻所有扩展目标的参数集,ξ(i)k−1 表示其中第i 个目标的参数集,该集合中的元素包括量测率γ(i)k−1 、运动状态x(i)k−1 和扩展状态X(i)k−1 。第
i 个扩展目标的运动状态模型为x(i)k=Fk|k−1x(i)k−1+w(i)k (2) 其中,
Fk|k−1 为状态转移矩阵,w(i)k 表示均值为零的高斯过程噪声,其协方差为Qk 。第
i 个目标的扩展状态由椭圆描述,用正定对称矩阵X(i)k 表示,即X(i)k=M(φ(i)k)((σ(i)k,1)200(σ(i)k,2)2)MT(φ(i)k) (3) M(φ(i)k)=(cos(φ(i)k)−sin(φ(i)k)sin(φ(i)k)cos(φ(i)k)) (4) 其中,目标轮廓的大小由扩展状态
X(i)k 的特征值(σ(i)k,1)2 和(σ(i)k,2)2 (椭圆半轴的2次方)确定,目标的方向角由旋转矩阵M(φ(i)k) 确定。k 时刻监控区域中所有扩展目标的量测集为Zk={z(j)k}Nz,kj=1=Θk(ξk)⋃Kk (5) 其中,
Θk(ξk) 为传感器检测到来自扩展目标的量测集,Kk 为杂波集,且杂波数服从参数为λk 的泊松分布。若z(j)k∈Θk(ξk) ,则z(j)k=h(x(i)k,xs,k(u))+e(j)k (6) 其中,
e(j)k 表示均值为零的高斯量测噪声,其协方差为X(i)k ,xs,k(u) 为k 时刻传感器控制方案u 对应的传感器位置。3. 传感器控制策略
3.1 多扩展目标跟踪中的传感器控制问题
控制量测过程最优是提高多扩展目标跟踪精度的有效方法,因此传感器控制问题即变为控制命令(或称为控制方案)子集的决策问题。考虑基于随机矩阵的多扩展目标跟踪建模,传感器控制决策必要的相关要素包括以下内容:
(1) 后验密度
fk−1+H(ξk−1+H|Z1:k−1+H) ;(2) 可实现传感器动作的控制命令集
Uk ;(3) 传感器控制评价函数
V(u) 。首先要以合理的方式建立传感器可控集合,在每个时刻传感器沿
Nθ 个方向中的某一个方向步进一到两个单位的距离,或者保持静止不动。考虑到0<Nθ<∞ ,且要保证传感器能够快速精准地运动到最佳观测点,因此取Nθ=8 ,如图2所示。图中,五角星代表当前时刻传感器的位置,其他点(含五角星)均代表下一时刻传感器可能的位置。H 增大会导致递推过程的不确定性,本文选用经典的“近视”策略(H=1 )。在传感器动作空间中,每个方案u 都有一个对应的评价函数V(u) ,它能够评估传感器控制方案的优劣。以下研究构造多扩展目标后验密度在其统计平均周围的广义离差作为评价函数,令其表达式为V(u)=D(fk(ξk|Z1:k−1,Zk(u))) (7) 其中,
D(⋅) 表示多扩展目标状态的后验密度在其统计平均周围的广义离差,它能反映综合多特征估计信息的整体质量。由式(7)可以看出,评价函数是传感器动作后,关于未来量测信息的函数,而这组量测信息显然不可预知,通用的解决方法是为每个可能的传感器动作生成一组伪量测,即预测理想量测集(Prediction Ideal Measurement Set, PIMS)[16,29]。若用
ˆuk 表示最优的传感器控制方案,则最终用式(8)确定该方案ˆuk=argminu∈UkE[V(u)] (8) 3.2 多特征广义离差的度量函数
由于需要考虑多扩展目标综合多特征(运动状态、形状等)估计的联合优化,制定合适的评价函数是多扩展目标跟踪传感器控制的核心问题。本文拟研究构造多扩展目标多特征估计在其后验统计均值周围的广义离差来评估传感器控制。为此,本文将给出一种 WGOSPA距离,该指标能够以合理的方式惩罚检测到的目标定位错误以及由于遗漏或假目标而产生的错误,鼓励滤波器尽可能少地产生估计错误和遗漏,同时,该指标能够综合多扩展目标的估计特征,以在多特征融合的条件下综合评判多扩展目标跟踪滤波性能。
(1) 广义最优子模式分配距离。令
c>0 ,0<α≤2 ,1≤p<∞ 。设d(x,y) 表示x,y∈RN 的某种距离度量,d(c)(x,y)=min(d(x,y),c) 。集合{1,2,⋯,n},n∈N 的所有排列方式记为Πn ,任意元素χ∈Πn 代表(χ(1),χ(2),⋯,χ(n)) 。设X 与Y 为RN 的有限子集。若|X|≤|Y| ,则X 与Y 的广义最优子模式分配距离[30]为d(c,α)p(X,Y)=[minχ∈Π|Y||X|∑i=1d(c)(xi,yχ(i))p+cpα(|Y|−|X|)]1p (9) 其中,
c 表示目标势估计平均距离误差,α 为势误差惩罚因子,p 表示位置误差与势误差的阶数,若|X|>|Y| ,则d(c,α)p(X,Y)=d(c,α)p(Y,X) 。(2) 加权广义最优子模式分配距离。多扩展目标真实的状态集合为
ξ(j)k ,估计的状态集合为ˆξ(i)k ,令d(ξ(j)k,ˆξ(i)k)=wγcγd(cγ)j,i+wxcxd(cx)j,i+wXcXd(cX)j,i (10) 其中,
wγ+wx+wX=1 ,d(cγ)j,i=min(cγ,|γ(j)k−ˆγ(i)k|) (11) d(cx)j,i=min(cx,‖ (12) d_{j,i}^{\left( {{c_X}} \right)} = \min \left( {{c_X},{{\left\| {{\boldsymbol{X}}_k^{\left( j \right)} - \hat {\boldsymbol{X}}_k^{\left( i \right)}} \right\|}_{\rm{F}}}} \right) (13) 其中,
{c_\gamma } ,{c_x} 和{{{c}}_X} 分别表示量测率、目标运动状态以及扩展状态的截断系数(最大期望误差),\left| \cdot \right| 表示绝对值,{\left\| \cdot \right\|_2} 表示欧几里得范数,{\left\| \cdot \right\|_{\rm{F}}} 表示弗罗贝尼乌斯范数。可以通过调整不同状态参数对应的权重大小来重点表达相应状态参数的后验离差,该离差作为传感器控制的评价函数在控制策略中表现为重点优化目标某种状态特征的估计效果。令
{{{c}}_w}{\text{ > 0}} ,M = \left| {\xi _k^{\left( j \right)}} \right| ,N = \left| {\hat \xi _k^{\left( i \right)}} \right| ,若M \le N ,则\xi _k^{\left( j \right)} 与\hat \xi _k^{\left( i \right)} 的WGOSPA距离为\begin{gathered} d_p^{\left( {{c_w},\alpha } \right)}\left( {\xi _k^{\left( j \right)},\hat \xi _k^{\left( i \right)}} \right) \\ = {\left[ {\mathop {\min }\limits_{\pi \in {\varPi _N}} \sum\limits_{i = 1}^M {d{{\left( {\xi _k^{\left( j \right)},\hat \xi _k^{\left( i \right)}} \right)}^p}} + \frac{{{{\left( {{c_w}} \right)}^p}}}{\alpha }\left( {N - M} \right)} \right]^{\frac{1}{p}}} \\ \end{gathered} (14) 若
M > N ,则d_p^{\left( {{c_w},\alpha } \right)}\left( {\xi _k^{\left( j \right)},\hat \xi _k^{\left( i \right)}} \right) = d_p^{\left( {{c_w},\alpha } \right)} \left( {\hat \xi _k^{\left( i \right)},\xi _k^{\left( j \right)}} \right) 。值得注意的是,由于式(9)是严格意义上的距离(证明过程见文献[30]),而式(10)也是严格意义上的距离,因此WGOSPA距离亦符合严格意义上的距离的定义。
3.3 评价函数的构建与最优数值求解
已知
k - 1 时刻多扩展目标的后验密度{f_{k - 1}}\left( { \cdot | \cdot } \right) ,根据多扩展目标跟踪滤波器进行预测,得到k 时刻预测的多扩展目标密度{f_{k|k - 1}}\left( { \cdot | \cdot } \right) ,然后提取预测状态(注:{\text{Sef}} 表示状态提取操作){\hat \xi _{k|k - 1}} = {\text{Sef}}\left\{ {{f_{k|k - 1}}\left( { \cdot | \cdot } \right)} \right\} (15) 在传感器的检测概率
{p_{\rm{D}}}\left( {{\xi _k}} \right) = 1 且在零杂波和零噪声的理想情况下,根据{\hat \xi _{k|k - 1}} 为每一个可能的传感器控制方案u 构造多扩展目标PIMS{{\boldsymbol{Z}}_k}\left( u \right) = \bigcup\limits_{u \in {U_k}} {\left\{ {h\left( {{{\hat \xi }_{k|k - 1}},{{\boldsymbol{x}}_{{\rm{s}},k}}\left( u \right)} \right)} \right\}} (16) 利用
{{\boldsymbol{Z}}_k}\left( u \right) 对{f_{k|k - 1}}\left( { \cdot | \cdot } \right) 进行伪更新,进而得到传感器控制方案u 对应的伪更新后验多扩展目标密度{f_{k,u}}\left( { \cdot | \cdot } \right) ,然后提取多扩展目标后验状态{\xi _{k,u}} = {\text{Sef}}\left\{ {{f_{k,u}}\left( { \cdot | \cdot } \right)} \right\} (17) 用
d_p^{\left( {{c_w},\alpha } \right)}\left( {{\xi _{k,u}},\mathbb{E}\left[ {{\xi _{k,u}}} \right]} \right) 表示{\xi _{k,u}} 和\mathbb{E}\left[ {{\xi _{k,u}}} \right] 之间的后验广义离差,则评价函数构造为\mathcal{V}\left( u \right) = \mathbb{E}\left[ {d_p^{\left( {{c_w},\alpha } \right)}\left( {{\xi _{k,u}},\mathbb{E}\left[ {{\xi _{k,u}}} \right]} \right)} \right] (18) 利用序贯蒙特卡罗(Sequential Monte Carlo, SMC)方法计算式(18)的数值为
\begin{split} \mathcal{V}\left( u \right) =& \int {d_p^{\left( {{c_w},\alpha } \right)}\left( {{\xi _{k,u}},\mathbb{E}\left[ {{\xi _{k,u}}} \right]} \right){f_{k,u}}\left( {{\xi _{k,u}}} \right)\delta {\xi _{k,u}}} \\ = &\int {d_p^{\left( {{c_w},\alpha } \right)}\left( {{\xi _{k,u}},{{\bar \xi }_{k,u}}} \right)\frac{1}{L}\sum\limits_{i = 1}^L {{\delta _{\xi _{k,u}^{\left( i \right)}}}\left( {{\xi _{k,u}}} \right)} \delta {\xi _{k,u}}} \\ =& \frac{1}{L}\sum\limits_{i = 1}^L {d_p^{\left( {{c_w},\alpha } \right)}\left( {\xi _{k,u}^{\left( i \right)},{{\bar \xi }_{k,u}}} \right)} \\[-21pt] \end{split} (19) 4. GGIW-MBer实现
假设
k - 1 时刻第i 个目标的运动状态{\boldsymbol{x}}_{k - 1}^{\left( i \right)} 服从高斯分布f\left( {{\boldsymbol{x}}_{k - 1}^{\left( i \right)}|{\boldsymbol{X}}_{k - 1}^{\left( i \right)},{{\boldsymbol{Z}}_{1:k - 1}}} \right) = \mathcal{N}\left( {{\boldsymbol{x}}_{k - 1}^{\left( i \right)};{\boldsymbol{m}}_{k - 1}^{\left( i \right)},{\boldsymbol{P}}_{k - 1}^{\left( i \right)}} \right) (20) 其中,
{\boldsymbol{m}}_{k - 1}^{\left( i \right)} 和{\boldsymbol{P}}_{k - 1}^{\left( i \right)} 分别为{\boldsymbol{x}}_{k - 1}^{\left( i \right)} 的均值和协方差阵。假设
k - 1 时刻第i 个目标的扩展状态{\boldsymbol{X}}_{k - 1}^{\left( i \right)} 服从逆威沙特分布f\left( {{\boldsymbol{X}}_{k - 1}^{\left( i \right)}|{{\boldsymbol{Z}}_{1:k - 1}}} \right) = \mathcal{I}\mathcal{W}\left( {{\boldsymbol{X}}_{k - 1}^{\left( i \right)};v_{k - 1}^{\left( i \right)},{\boldsymbol{V}}_{k - 1}^{\left( i \right)}} \right) (21) 其中,
v_{k - 1}^{\left( i \right)} 与{\boldsymbol{V}}_{k - 1}^{\left( i \right)} 分别为逆威沙特分布的自由度和逆尺度矩阵,d 为{\boldsymbol{X}}_{k - 1}^{\left( i \right)} 的维数。第
i 个目标的扩展状态转移密度由威沙特密度表示为f\left( {{\boldsymbol{X}}_k^{\left( i \right)}\left| {{\boldsymbol{X}}_{k - 1}^{\left( i \right)}} \right.} \right) = \mathcal{W}\left( {{\boldsymbol{X}}_k^{\left( i \right)};n,\frac{{{\boldsymbol{X}}_{k - 1}^{\left( i \right)}}}{n}} \right) (22) 自由度
n 描述了状态演化的不确定性。假设第
i 个目标的量测率几乎不随时间变化, 即\gamma _k^{\left( i \right)} = \gamma _{k - 1}^{\left( i \right)} (23) 量测率通常取决于目标的大小和位置,服从参数为
\alpha _k^{\left( i \right)} 和\beta _k^{\left( i \right)} 的伽马分布。因此,单个目标的共轭先验是伽马高斯逆威沙特分布,表示为
\begin{split} {f_{k|k}}\left( { \cdot | \cdot } \right) & = \mathcal{G}\left( {r_k^{\left( i \right)};\alpha _k^{\left( i \right)},\beta _k^{\left( i \right)}} \right)\mathcal{N}\left( {{\boldsymbol{x}}_k^{\left( i \right)};{\boldsymbol{m}}_k^{\left( i \right)},{\boldsymbol{P}}_k^{\left( i \right)}} \right) \\ & \times \mathcal{I}\mathcal{W}\left( {{\boldsymbol{X}}_k^{\left( i \right)};v_k^{\left( i \right)},{\boldsymbol{V}}_k^{\left( i \right)}} \right) \\ & \triangleq \mathcal{G}\mathcal{G}\mathcal{I}\mathcal{W}\left( {\xi _k^{\left( i \right)};\zeta _k^{\left( i \right)}} \right)\\[-15pt] \end{split} (24) 由多伯努利随机集的贝叶斯滤波可以得到如下的GGIW-MBer滤波过程:
将GGIW-MBer预测过程和更新过程应用于算法1中,即可实现本文所提的传感器控制,如算法2和算法3所示。
算法1 多扩展目标跟踪基于多特征优化的传感器控制算法 输入: k - 1 时刻多扩展目标多特征信息 {\zeta _{k - 1}} 与传感器坐标
{x_{{\rm{s}},k - 1} },其中,{\zeta _{k - 1} } = \left\{ { {\alpha _{k - 1} },{\beta _{k - 1} },{{\boldsymbol{m}}_{k - 1} },{{\boldsymbol{P}}_{k - 1} },{{\boldsymbol{v}}_{k - 1} },{{\boldsymbol{V}}_{k - 1} } } \right\}。 (1) 多扩展目标跟踪的预测过程,得到 {f_{k|k - 1}}\left( { \cdot | \cdot } \right) 。 (2) 传感器控制 {\hat \xi _{k|k - 1}} = {\text{Sef}}\left\{ {{f_{k|k - 1}}\left( { \cdot | \cdot } \right)} \right\} , 确定所有可能的控制方案{{\boldsymbol{U}}_k}。 {\text{for all } }u \in {{\boldsymbol{U}}_k}{\text{ do} } 生成PIMS:{{\boldsymbol{Z}}_k}\left( u \right), 量测集划分:{\boldsymbol{\rho}} \angle {{\boldsymbol{Z}}_k}\left( u \right), 计算伪更新后验密度 {f_{k,u}}\left( { \cdot | \cdot } \right) , 提取状态的统计平均: {\bar \xi _{k,u}} \leftarrow {\text{Sef}}\left\{ {{f_{k,u}}\left( { \cdot | \cdot } \right)} \right\} , 蒙特卡罗采样: \left\{ {{\xi _{k,l}}} \right\}_{l = 1}^L \leftarrow {\text{MC}}\left( {{f_{k,u}}\left( { \cdot | \cdot } \right),L} \right) , \mathcal{V}\left( u \right) \leftarrow 0 , {\text{for }}l = 1:L \mathcal{V}\left( u \right) \leftarrow \mathcal{V}\left( u \right) + \dfrac{1}{L}d_p^{\left( { {c_w},\alpha } \right)}\left( { {\xi _{k,l} },{ {\bar \xi }_{k,u} } } \right)。 {\text{end for}} {\text{end for}}
{\hat u_k} \leftarrow \mathop {\arg \min }\limits_{u \in {U_k}} \mathcal{V}\left( u \right) 。(3) 多扩展目标跟踪的更新过程,得到 {f_{k|k}}\left( { \cdot | \cdot } \right) 。 (4) 提取状态信息 {\xi _k} ,并计算目标势 {N_k} = \left| {{\xi _k}} \right| 。 输出:目标势 {N_k} ,多扩展目标状态集 {\xi _k} , k 时刻传感器坐标
{x_{{\rm{s}},k} }。算法2 GGIW-MBer预测过程 输入: \zeta _{k - 1}^{\left( {i,j} \right)} 。 预测第 j 个GGIW分量的参数: {\boldsymbol{m}}_{k|k - 1}^{\left( {i,j} \right)} = {{\boldsymbol{F}}_{k|k - 1} }{\boldsymbol{m}}_{k - 1}^{\left( {i,j} \right)} {\boldsymbol{P}}_{k|k - 1}^{\left( {i,j} \right)} = {{\boldsymbol{F}}_{k|k - 1} }{\boldsymbol{P}}_{k - 1}^{\left( {i,j} \right)}{\boldsymbol{F}}_{k|k - 1}^{\text{T} } + {{\boldsymbol{Q}}_k} v_{k|k - 1}^{\left( {i,j} \right)} = {{\rm{e}}^{ - \frac{ { {T_{\rm{s}}} } }{\tau } } }v_{k - 1}^{\left( {i,j} \right)} V_{k|k - 1}^{\left( {i,j} \right)} = \dfrac{ {v_{k|k - 1}^{\left( {i,j} \right)} - d - 1} }{ {v_{k - 1}^{\left( {i,j} \right)} - d - 1} }V_{k - 1}^{\left( {i,j} \right)} X_{k|k - 1}^{\left( {i,j} \right)} = \dfrac{ {V_{k|k - 1}^{\left( {i,j} \right)} } }{ {v_{k|k - 1}^{\left( {i,j} \right)} - 2d - 2} } \alpha _{k|k - 1}^{\left( {i,j} \right)} = \dfrac{ {\alpha _{k - 1}^{\left( {i,j} \right)} } }{ { {\eta _{k - 1} } } } \beta _{k|k - 1}^{\left( {i,j} \right)} = \dfrac{ {\beta _{k - 1}^{\left( {i,j} \right)} } }{ { {\eta _{k - 1} } } } 输出: \zeta _{k|k - 1}^{\left( {i,j} \right)} 。 算法3 GGIW-MBer更新过程 输入: \zeta _{k|k - 1}^{\left( {i,j} \right)} ,量测集划分{\boldsymbol{W}}。 更新第 j 个GGIW分量的参数:
\bar z_k^W = \dfrac{1}{ {\left| {\boldsymbol{W} } \right|} }\displaystyle\sum\limits_{z_k^{\left( i \right)} \in W} { {\boldsymbol{z} }_k^{\left( i \right)} }{\boldsymbol{X}}_{k|k - 1}^{\left( {i,j} \right)} = \dfrac{ {{\boldsymbol{V}}_{k|k - 1}^{\left( {i,j} \right)} } }{ {v_{k|k - 1}^{\left( {i,j} \right)} - 2d - 2} } {\boldsymbol{S} }_{k|k - 1}^{\left( {i,j,W} \right)} = { {\boldsymbol{H} }_k}{\boldsymbol{P} }_{k|k - 1}^{\left( {i,j} \right)}{\boldsymbol{H} }_k^{\text{T} } + \dfrac{ { {\boldsymbol{X} }_{k|k - 1}^{\left( {i,j} \right)} } }{ {\left| {\boldsymbol{W} } \right|} } {\boldsymbol{K}}_{k|k - 1}^{\left( {i,j,W} \right)} = {\boldsymbol{P}}_{k|k - 1}^{\left( {i,j} \right)}{\boldsymbol{H}}_k^{\text{T} }{\left( {{\boldsymbol{S}}_{k|k - 1}^{\left( {i,j,W} \right)} } \right)^{ - 1} } {\boldsymbol{\varepsilon}} _{k|k - 1}^{\left( {i,j,W} \right)} = \bar {\boldsymbol{z}}_k^W - {{\boldsymbol{H}}_k}{\boldsymbol{m}}_{k|k - 1}^{\left( {i,j} \right)} {\boldsymbol{m}}_k^{\left( {i,j} \right)} = {\boldsymbol{m}}_{k|k - 1}^{\left( {i,j} \right)} + {\boldsymbol{K}}_{k|k - 1}^{\left( {i,j,W} \right)}{\boldsymbol{\varepsilon}} _{k|k - 1}^{\left( {i,j,W} \right)} {\boldsymbol{P}}_k^{\left( {i,j} \right)} = {\boldsymbol{P}}_{k|k - 1}^{\left( {i,j} \right)} - {\boldsymbol{K}}_{k|k - 1}^{\left( {i,j,W} \right)}{\boldsymbol{S}}_{k|k - 1}^{\left( {i,j,W} \right)}{\left( {{\boldsymbol{K}}_{k|k - 1}^{\left( {i,j,W} \right)} } \right)^{\text{T} } } {\boldsymbol{Z}}_k^W = \displaystyle\sum\limits_{z_k^{\left( i \right)} \in W} {\left( {{\boldsymbol{z}}_k^{\left( i \right)} - \bar {\boldsymbol{z}}_k^W} \right){ {\left( {{\boldsymbol{z}}_k^{\left( i \right)} - \bar {\boldsymbol{z}}_k^W} \right)}^{\text{T} } } } \begin{aligned} {\boldsymbol{N} }_{k|k - 1}^{\left( {i,j,W} \right)} =& {\left( { {\boldsymbol{X} }_{k|k - 1}^{\left( {i,j} \right)} } \right)^{\frac{1}{2} } }{\left( { {\boldsymbol{S} }_{k|k - 1}^{\left( {i,j,W} \right)} } \right)^{ - \frac{1}{2} } }{\boldsymbol{\varepsilon} } _{k|k - 1}^{\left( {i,j,W} \right)}{\text{ } } \times {\left( { {\boldsymbol{\varepsilon} } _{k|k - 1}^{\left( {i,j,W} \right)} } \right)^{\text{T} } }\\ & \cdot{\left(\left( { {\boldsymbol{S} }_{k|k - 1}^{\left( {i,j,W} \right)} } \right)^{ -\frac {1} {2} } \right)^{ {\rm{T} } } }\left({\left( { {\boldsymbol{X} }_{k|k - 1}^{\left( {i,j} \right)} } \right)^{\frac{ 1}{2} } }\right)^{\rm{T} }\end{aligned} v_k^{\left( {i,j,W} \right)} = v_{k|k - 1}^{\left( {i,j,W} \right)} + \left| {\boldsymbol{W}} \right| {\boldsymbol{V}}_k^{\left( {i,j,W} \right)} = {\boldsymbol{V}}_{k|k - 1}^{\left( {i,j,W} \right)} + {\boldsymbol{N}}_{k|k - 1}^{\left( {i,j,W} \right)} + {\boldsymbol{Z}}_k^W
{\boldsymbol{X} }_k^{\left( {i,j,W} \right)} = \dfrac{ { {\boldsymbol{V} }_k^{\left( {i,j,W} \right)} } }{ {v_k^{\left( {i,j,W} \right)} - 2d - 2} }\alpha _k^{\left( {i,j,W} \right)} = \alpha _{k|k - 1}^{\left( {i,j,W} \right)} + \left| {\boldsymbol{W}} \right| \beta _k^{\left( {i,j,W} \right)} = \beta _{k|k - 1}^{\left( {i,j,W} \right)} + 1 输出: \zeta _k^{\left( {i,j} \right)} 。 5. 实验论证
5.1 参数设定
为了测试本文算法对密集多扩展目标跟踪优化效果,在监控区域内设有10个椭圆形扩展目标,建立动态跟踪环境,验证本文提出方法的有效性。实验中,GOSPA距离的参数设置为
p = 1 ,c = 2 ,\alpha = 2 。WGOSPA距离的参数设置为{c_w} = 2 ,{c_\gamma } = 5 ,{c_x} = 10 ,{c_X} = 10 ,{w_\gamma } = 0.1 ,{{{w}}_x} = 0.7 ,{w_X} = 0.2 。 采样间隔{T_{\rm{s}}} = 1{\text{ s}} ,遗忘因子{\eta _k} = 8 ,杂波平均数设置为{\lambda _{{\text{FA}}}} = 5 ,目标的检测概率和存活概率分别为{p_{\rm{D}}} = 0.99 和{p_{\rm{S}}} = 0.99 ,GGIW分量的最大数量为{J_{\max }} = 100 ,时间衰减常数\tau = 5{\text{ s}} 。椭圆扩展目标的长半轴和短半轴的长度分别设定为A = 6{\text{ m}} ,a = 3{\text{ m}} ,方向角设为45°。每个采样周期内的量测个数服从参数为\lambda = 15 的泊松分布。目标的运动模型以及量测模型如式(2)和式(6)所示,其中,{{\boldsymbol{F}}_{k|k - 1}} = \left[ {\begin{array}{*{20}{c}} 1&{{T_{\rm{s}}}} \\ 0&1 \end{array}} \right] \otimes {{\boldsymbol{I}}_d}\begin{array}{*{20}{c}} ,&{{{\boldsymbol{H}}_k} = [\begin{array}{*{20}{c}} 1&0 \end{array}] \otimes {{\boldsymbol{I}}_d}} \end{array} (25) {{\boldsymbol{Q}}_k} = {\varSigma ^2}\left( {1 - {{\rm{e}}^{ - \frac{{2{T_{\rm{s}}}}}{t}}}} \right)\left[ {\begin{array}{*{20}{c}} 0&{} \\ {}&1 \end{array}} \right] \otimes {{\boldsymbol{I}}_d} (26) 其中,
t = 1{\text{ s}} ,\varSigma 取0.1,\otimes 为克罗内克积的运算符。新生目标数{J_{\Gamma ,k}} = 10 ,第j 个新生目标的权重w_{\Gamma ,k}^{\left( j \right)} = 0.1 ,其他参数初始化为{\boldsymbol{m}}_{\Gamma ,k}^{\left( j \right)} = {\left( {{\boldsymbol{m}}_0^{\left( j \right)}} \right)^{\text{T}}}\begin{array}{*{20}{c}} ,&{{\boldsymbol{P}}_{\Gamma ,k}^{\left( j \right)}} \end{array} = \left[ {\begin{array}{*{20}{c}} {100}&{} \\ {}&{25} \end{array}} \right] \otimes {{\boldsymbol{I}}_d} (27) v_{\Gamma ,k}^{\left( j \right)} = 7\begin{array}{*{20}{c}} ,&{{\boldsymbol{V}}_{\Gamma ,k}^{\left( j \right)}} \end{array} = {\text{eye}}\left( d \right) (28) \alpha _{\Gamma ,k}^{\left( j \right)} = 20 ,\beta _{\Gamma ,k}^{\left( j \right)} = 1 (29) k 时刻传感器所有可能的位置集合{{\boldsymbol{U}}_k} 为\begin{split} {{\boldsymbol{U}}_k} = &\left\{ {\left( {{x_{{\rm{s}},k - 1}} + r{v_{\rm{s}}}\frac{{{T_{\rm{s}}}}}{{{N_{\rm{R}}}}}\cos \frac{{2\pi l}}{{{N_{\text{θ}} }}},} \right.} \right. \\ &\left. {\left. {{y_{{\rm{s}},k - 1}} + r{v_{\rm{s}}}\frac{{{T_{\rm{s}}}}}{{{N_{\rm{R}}}}}\sin \frac{{2\pi l}}{{{N_{\text{θ}} }}}} \right)} \right\} \end{split} (30) 其中,
{{\boldsymbol{x}}}_{{\rm{s}},k-1}={\left[{x}_{{\rm{s}},k-1} {y}_{{\rm{s}},k-1}\right]}^{\text{T}} 为k - 1 时刻传感器的位置,r = 1,2, \cdots ,{N_{\rm{R}}} ,l = 1,2, \cdots ,{N_{\text{θ}}} ,仿真实验中,{N_{\rm{R}}} = 2 ,{N_{\text{θ}} } = 8 ,传感器运动的径向速度设为{v_{\rm{s}}} = 10{\text{ m/s}} ,初始位置为{{\boldsymbol{x}}_{{\rm{s}},0}} = {\left[ {\begin{array}{*{20}{c}} 0&0 \end{array}} \right]^{\rm T}} 。5.2 多扩展目标跟踪优化分析
本节将选用不同的控制方案与本文提出的控制方法进行比较。其中,方案1是基于柯西-施瓦茨散度[14]的传感器控制;方案2为本文提出的传感器控制方案。目标的初始参数见表1,真实轨迹见图3。
表 1 多扩展目标初始参数目标 出生时刻
(s)消亡时刻
(s)初始状态
(m; m; m/s; m/s)1 1 40 [–800; 600; 40; –15] 2 11 40 [–700; 0; 40; –10] 3 21 30 [–100; 500; –35; –20] 4 1 10 [200; 100; 10; 20] 5 1 20 [–500; 100; –15; –15] 6 31 40 [–100; 100; 20; –15] 7 6 15 [500; 300; 10; 10] 8 16 25 [–200; 300; –20; –60] 9 26 35 [–200; –300; 40; –15] 10 1 30 [300; –100; –20; –20] 图4记录了本文所提优化控制方案的传感器运动轨迹。从图中解读到,传感器自动按照多扩展目标多特征的后验密度广义离差最小化动态调节自身位置,使其在每个采样时刻都能获取最优量测过程。也注意到,目标个数发生突变的时刻,传感器的坐标也会产生明显的变化趋势,以应对由于多伯努利密度的瞬变带来的广义离差的瞬变,使传感器在最短时间内到达最优观测位置。
图5记录了100次独立的蒙特卡罗(Monte Carlo, MC)仿真实验中传感器经过的所有位置,可以看出,在相同的评价准则下由于受到环境随机因素的影响,每次MC仿真实验中的传感器运动轨迹存在一定差异。但是从图中还是可以反映出传感器优化运动所在的大致活跃区域,反映了传感器在多扩展目标跟踪系统中的最优观测轨迹的运动趋势。
图6为100次独立的MC仿真实验中多扩展目标质心位置估计的GOSPA距离统计,表2为各方案目标质心位置估计GOSPA距离的统计均值,综合图表可以分析出,本文方案对多扩展目标质心位置的估计效果是要优于方案1。
表 2 目标质心估计的GOSPA距离统计均值(m)方案1 方案2 GOSPA距离 1.1303 1.0671 为了比较清晰地对多目标形状轮廓估计效果进行比对,在图7呈现扩展目标跟踪估计的放大效果。可以分析得出,本文所提方法对目标形状的估计效果更加接近于实际,直观地体现出所提方法更好地优化了对目标扩展状态的估计。
扩展状态估计效果的优劣可由椭圆长短轴估计误差的大小来评估。鉴于此,统计得到MC实验中长短轴估计信息的GOSPA距离如图8,而表3是相应的统计平均值,由图表联合分析可得,本文方案对多扩展目标综合多特征估计的优化效果更优。
表 3 目标长短轴的GOSPA距离统计平均值(m)方案1 方案2 GOSPA距离 1.5594 1.5009 图9显示了MC仿真实验中多扩展目标势(即目标的个数)估计的统计效果,可以看出,所有传感器控制方案对目标势的估计差别并不大,由于GOSPA距离是综合评价指标(联合评价目标势和目标状态估计),结合前述各GOSPA距离统计的效果图,也突显了本文所提算法的优化效果着重体现在多扩展目标的多特征估计上。
6. 结束语
本文的主要工作和创新点是利用基于多特征距离广义离差最小化的传感器控制方法提出了一种有效的多扩展目标跟踪优化算法,使其对多扩展目标运动状态和形状的估计得到明显优化,通过仿真实验可知,各项跟踪性能指标均优于其他传感器控制方案,有效提升了多扩展目标跟踪系统的性能。所提算法的意义在于实现了多扩展目标的运动状态估计与扩展状态估计的联合优化,实现了多特征共同决策下的传感器最优控制技术,这对于精度要求更高的现代目标跟踪系统来说有着重要的理论价值。
-
[1] LIANG Huaguo, XU Xiumin, HUANG Zhengfeng, et al. A methodology for characterization of SET propagation in SRAM-based FPGAs[J]. IEEE Transactions on Nuclear Science, 2016, 63(6): 2985–2992. doi: 10.1109/TNS.2016.2620165. [2] WANG Ke and LOURI A. CURE: A high-performance, low-power, and reliable network-on-chip design using reinforcement learning[J]. IEEE Transactions on Parallel and Distributed Systems, 2020, 31(9): 2125–2138. doi: 10.1109/TPDS.2020.2986297. [3] BHOWMIK B. Maximal connectivity test with channel-open faults in on-chip communication networks[J]. Journal of Electronic Testing, 2020, 36(3): 385–408. doi: 10.1007/S10836-020-05878-1. [4] DITOMASO D, BORATEN T, KODI A, et al. Dynamic error mitigation in NoCs using intelligent prediction techniques[C]. 2016 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), Taipei, China, 2016: 1–12. doi: 10.1109/MICRO.2016.7783734. [5] CHANG Y C, GONG C S A, and CHIU C T. Fault-tolerant mesh-based NoC with router-level redundancy[J]. Journal of Signal Processing Systems, 2020, 92(4): 345–355. doi: 10.1007/S11265-019-01476-3. [6] GUO Pengxing, HOU Weigang, GUO Lei, et al. Fault-tolerant routing mechanism in 3D optical network-on-chip based on node reuse[J]. IEEE Transactions on Parallel and Distributed Systems, 2020, 31(3): 547–564. doi: 10.1109/TPDS.2019.2939240. [7] NARAYANASAMY P and GOPALAKRISHNAN S. Novel fault tolerance topology using corvus seek algorithm for application specific NoC[J]. Integration, 2023, 89: 146–154. doi: 10.1016/J.VLSI.2022.11.011. [8] SLEEBA S Z, JOSE J, and MINI M G. Energy-efficient fault tolerant technique for deflection routers in two-dimensional mesh Network-on-Chips[J]. IET Computers & Digital Techniques, 2018, 12(3): 69–79. doi: 10.1049/IET-CDT.2017.0006. [9] SAMALA J, TAKAWALE H, CHOKHANI Y, et al. Fault-tolerant routing algorithm for mesh based NoC using reinforcement learning[C]. 2020 24th International Symposium on VLSI Design and Test (VDAT), Bhubaneswar, India, 2020: 1–6. doi: 10.1109/VDAT50263.2020.9190340. [10] LIU Yi, GUO Rujia, XU Changqing, et al. A Q-learning-based fault-tolerant and congestion-aware adaptive routing algorithm for networks-on-chip[J]. IEEE Embedded Systems Letters, 2022, 14(4): 203–206. doi: 10.1109/LES.2022.3176233. [11] JAIN A, LAXMI V, TRIPATHI M, et al. TRACK: An algorithm for fault-Tolerant, dynamic and scalable 2D mesh network-on-chip routing reconfiguration[J]. Integration, 2020, 72: 92–110. doi: 10.1016/J.VLSI.2020.01.005. [12] ZHANG Ying, HONG Xinpeng, CHEN Zhongsheng, et al. A deterministic-path routing algorithm for tolerating many faults on very-large-scale network-on-chip[J]. ACM Transactions on Design Automation of Electronic Systems (TODAES), 2021, 26(1): 8. doi: 10.1145/3414060. [13] LI Jiao, QIN Chaoqun, and SUN Xuecheng. An efficient adaptive routing algorithm for the Co-optimization of fault tolerance and congestion awareness based on 3D NoC[J]. Microelectronics Journal, 2023, 142: 105989. doi: 10.1016/J.MEJO.2023.105989. [14] RIZK M, MARTIN K J M, and DIGUET J P. Run-time remapping algorithm of dataflow actors on NoC-based heterogeneous MPSoCs[J]. IEEE Transactions on Parallel and Distributed Systems, 2022, 33(12): 3959–3976. doi: 10.1109/TPDS.2022.3177957. [15] WANG K, LOURI A, KARANTH A, et al. IntelliNoC: A holistic design framework for energy-efficient and reliable on-chip communication for manycores[C]. Proceedings of the 46th International Symposium on Computer Architecture, Phoenix, USA, 2019: 589–600. doi: 10.1145/3307650.3322274. [16] ZHENG Hao and LOURI A. Agile: A learning-enabled power and performance-efficient network-on-chip design[J]. IEEE Transactions on Emerging Topics in Computing, 2022, 10(1): 223–236. doi: 10.1109/TETC.2020.3003496. [17] LAN Y C, LIN H A, LO S H, et al. A bidirectional NoC (BiNoC) architecture with dynamic self-reconfigurable channel[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2011, 30(3): 427–440. doi: 10.1109/TCAD.2010.2086930. [18] FARROKHBAKHT H, KAO H, HASAN K, et al. Pitstop: Enabling a virtual network free network-on-chip[C]. 2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA), Seoul, Korea (South), 2021: 682–695. doi: 10.1109/HPCA51647.2021.00063. [19] SUN Chen, CHEN C H O, KURIAN G, et al. DSENT-a tool connecting emerging photonics with electronics for opto-electronic networks-on-chip modeling[C]. 2012 IEEE/ACM Sixth International Symposium on Networks-on-Chip, Lyngby, Denmark, 2012: 201–210. doi: 10.1109/NOCS.2012.31. [20] ZHOU Wu, OUYANG Yiming, XU Dongyu, et al. Energy-efficient multiple network-on-chip architecture with bandwidth expansion[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2023, 31(4): 442–455. doi: 10.1109/TVLSI.2023.3244859. -