Loading [MathJax]/jax/output/HTML-CSS/jax.js
高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

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

完全可编程阀门阵列生物芯片下容错导向的高阶综合算法

朱予涵 刘博文 黄兴 刘耿耿

左燕, 陈志猛, 蔡立平. 基于约束总体最小二乘的单站DOA/TDOA联合误差校正与定位算法[J]. 电子与信息学报, 2019, 41(6): 1317-1323. doi: 10.11999/JEIT180655
引用本文: 朱予涵, 刘博文, 黄兴, 刘耿耿. 完全可编程阀门阵列生物芯片下容错导向的高阶综合算法[J]. 电子与信息学报, 2024, 46(11): 4141-4150. doi: 10.11999/JEIT240049
Yan ZUO, Zhimeng CHEN, Liping CAI. Single-observer DOA/TDOA Registration and Passive Localization Based on Constrained Total Least Squares[J]. Journal of Electronics & Information Technology, 2019, 41(6): 1317-1323. doi: 10.11999/JEIT180655
Citation: ZHU Yuhan, LIU Bowen, HUANG Xing, LIU Genggeng. Fault-tolerance-oriented High-level Synthesis Algorithm for Fully Programmable Valve Array Biochips[J]. Journal of Electronics & Information Technology, 2024, 46(11): 4141-4150. doi: 10.11999/JEIT240049

完全可编程阀门阵列生物芯片下容错导向的高阶综合算法

doi: 10.11999/JEIT240049
基金项目: 福建省杰出青年科学基金(2023J06017)
详细信息
    作者简介:

    朱予涵:女,博士生,研究方向为微流体生物芯片设计自动化

    刘博文:男,博士生,研究方向为微流体生物芯片设计自动化

    黄兴:男,博士,教授,研究方向为微流体生物芯片及超大规模集成电路设计自动化

    刘耿耿:男,博士,教授,研究方向为微流体生物芯片及超大规模集成电路设计自动化

    通讯作者:

    刘耿耿 liugenggeng@fzu.edu.cn

  • 中图分类号: TN402; TP391.41

Fault-tolerance-oriented High-level Synthesis Algorithm for Fully Programmable Valve Array Biochips

Funds: Fujian Science Fund for Distinguished Young Scholars (2023J06017)
  • 摘要: 作为新一代流式微流控生物芯片,完全可编程阀门阵列(FPVA)生物芯片具有更高的灵活性和可编程性,已经成为一种流行的生物化学实验平台。然而,由于环境或人为因素,制造过程中通常存在一些物理故障,如通道阻塞和泄漏,这无疑会影响生化检测的结果。此外,高阶综合作为架构综合的首要阶段,其结果的质量直接影响着后续设计的优劣。因此,该文首次研究了FPVA生物芯片高阶综合过程中的容错问题,提出了单元功能转换方法、双向冗余方法、故障映射方法等动态容错技术,为实现高效的容错设计提供了技术保障。通过将这些技术集成到高阶综合设计中,进一步实现了一种高质量的FPVA生物芯片下容错导向的高阶综合算法,包括故障感知的实时绑定策略和故障感知的优先级调度策略,为实现芯片架构的鲁棒性和检测结果的准确性奠定了良好的基础。实验结果显示,所提算法能够得到一个FPVA生物芯片下高质量且容错的高阶综合方案,为后续实现容错物理设计方案提供了有力保障。
  • 外辐射源雷达利用第三方(广播、电视、卫星、通信基站等外辐射源)发射的电磁信号辐射源实现对“无线电静默”目标的探测与定位,具有隐蔽性高、抗干扰能力强、监视范围广、成本低等优点[1]。因此,近年成为雷达探测领域的研究热点[24]

    目前,外辐射源雷达定位系统利用观测量对目标进行无源定位,主要包括基于到达角度(Direction Of Arrival, DOA)、到达时差(Time Difference Of Arrival, TDOA)、到达频差(Frequency Difference Of Arrival, FDOA)以及联合其中2种或者3种观测信息的定位体制[57]。其中,联合DOA 和TDOA定位体制因其定位精度高,在工程上被广泛采用。

    外辐射源雷达系统DOA/TDOA定位需要来自同一目标的所有的量测值是无偏的,而实际问题中外辐射源雷达量测中存在系统偏差[8]。引起偏差产生的因素主要有3个方面:(1)外辐射源之间信号发射时钟不同步,存在时钟偏差[9,10];(2)外辐射源信号传播时受信号阻塞和多径影响,使得参考信号的路径与直达波路径不一致,引起到达时差量测的偏差[11];(3)雷达观测站天线坐标非水平且方位角零值未对准,造成方位角测量偏差。忽视系统偏差的影响会导致目标定位估计性能严重下降,甚至产生虚假目标。因此,研究系统偏差下外辐射源DOA/TDOA定位非常必要。

    极大似然估计[12]、最大期望估计[13]和最小二乘估计[14]等配准方法已广泛应用于主动单基雷达网误差校正。由于主/被动雷达定位体制不同,上述方法不能直接应用于被动定位系统的误差校正。Wang和Ho[15]针对目标辐射源TDOA定位系统,考虑固定时钟偏差和传感器位置随机误差的影响,提出了两步加权最小二乘的估计算法。随后,文献[16]将到达增益比(Gain Ratio Of Arrival, GROA)量测信息加入TDOA定位体制中,采用最小二乘算法联合估计目标位置和系统偏差。上述目标辐射源被动定位和误差校正方法根据观测量和待估计量(目标位置及系统偏差)之间的代数特征,推导出相应的伪线性方程,基于此提出闭式求解或迭代优化算法。

    本文研究基于外辐射源雷达系统单站DOA/TDOA无源定位和误差校正问题。与目标辐射源定位系统不同,外辐射源雷达采用双基/多基结构,其量测方程非线性程度增强,而系统偏差的存在使得目标位置和系统偏差估计方程的建立更加困难。外辐射源雷达系统无源定位和误差校正问题本质是一个高维非线性估计问题,受目标辐射源定位方法[15,16]的启发,在多基外辐射源雷达观测方程中引入线性化处理,构造量测值与待估计值(目标位置及系统偏差)之间的伪线性方程。文献[8]研究了多基被动雷达TDOA定位下系统偏差校正问题,利用双基距非线性量测函数的代数特征构造伪线性方程,并提出了一种关联后验迭代最小二乘估计算法联合估计目标位置和系统偏差。该方法对双基距量测方程进行线性化处理后,伪线性估计方程中系统矩阵出现噪声分量统计相关特性,而所提的求解算法在噪声分量统计相关时并不能获得最优解。

    对此,本文针对多基外辐射源雷达单站DOA/TDOA定位系统,提出一种基于约束总体最小二乘(Constrained Total Least Squares, CTLS)的无源定位和误差校正方法。将DOA信息引入到TDOA定位体制中,通过协同多域观测信息改善对目标定位性能。利用多基外辐射源雷达DOA和TDOA的代数特征,引入辅助变量进行伪线性处理。同时考虑了伪线性化处理后出现噪声分量统计相关的问题,将目标定位和系统偏差校正联合估计建立为CTLS模型,并利用牛顿迭代法求解。在此基础上,考虑辅助变量与目标位置的关联性,提出一种关联最小二乘算法提高目标位置估计精度,并通过后验迭代方法进一步提高系统偏差的估计精度。最后对算法进行了理论分析和仿真验证。

    考虑某基于外辐射源的无源定位系统,该系统由M个外辐射源和1个观测站共同组成,对P个目标进行定位。不失一般性,以观测站为原点,建立空间直角坐标系。第m个外辐射源位置已知为qm=[xm,ym]T (m=1,2,···,M),第p个目标的坐标位置为rtarp=[xtarp,ytarp]T(p=1,2,···,P)。假设信号的传播速度为c=3×108 m/s,则外辐射源m的直达信号与其经目标p反射后的回波信号到达观测站的时差为

    tm,p=t0m,p+Δtm+etm,p (1)

    其中,t0m,p=(rtarpqm+rtarpqm)/c为到达时差的真实值,Δtm为对应的系统偏差,etm,p为对应的量测误差,服从均值为0,方差为σ2m,p的高斯分布。

    由于外辐射源的位置和观测站的位置通常是先验已知,因此TDOA又可转化为目标到达外辐射源与到达观测站的距离和(即双基距)的量测值

    um,p=u0m,p+δm+eum,p (2)

    其中,um,p=rtarpqm+rtarp为目标p距外辐射源m与观测站距离和的真实值;δm=cΔtm为外辐射源m的双基距系统偏差;eum,p=cetm,p为对应的量测噪声,服从均值为0,方差为c2σ2m,p的高斯分布。

    假设目标p到观测站的方位角为θp,根据目标与观测站的几何关系,得到方位角θp的观测方程为

    θp=arctanytarpxtarp+Δθp+eθp (3)

    其中,θp为目标p到观测站的方位角量测值,Δθp为该方位角系统偏差,eθp为对应的量测噪声,服从均值为0,方差为σ2θp的高斯分布。

    令辅助变量rm,p=(xtarpxm)2+(ytarpym)2, Rp=(xtarp)2+(ytarp)2,代入式(2)中,并结合式(4)

    (Rp+rm,p)(Rprm,p)=2xmxtarp+2ymytarpx2my2m (4)

    消去辅助变量rm,p,整理可得

    l2xmxtarp2ymytarp+2ˉum,pRp+(δm+2ˉum,p2Rp)δm=ˉu2m,px2my2m (5)

    其中,ˉum,p=um,peum,p

    将式(3)在量测值θp进行1阶泰勒展开,忽略高阶项,得到式(6)

    tanˉθpxtarpytarpxpcos2ˉθpΔθp=0 (6)

    其中,ˉθp=θpeθp

    将目标位置(xtarp,ytarp)、系统偏差δmΔθp,以及辅助变量Rp作为待求变量,联立式(5)和式(6)构造伪线性量测定位方程,矩阵形式如式(7)

    ˉZ=ˉHX (7)

    式中,

    X=[xtar1ytar1R1Δθ1···xtarPytarPRPΔθPδ1···δM]T  
    ˉZ=[0(ˉu21,1x21y21)···(ˉu2M,1x2My2M)···0(ˉu2M,1x21y21)···(ˉu2M,Px2My2M)]T
    ˉH=[blkdiag{h1LS(1)···h1LS(P)}[h2LS(1)···h2LS(P)]T]
    h1LS(p)=[tanˉθp10xtarpcos2ˉθp2x12y12ˉu1,p02xM2yM2ˉuM,p0]  
    h2LS(p)=[O1×M, diag[δ1+2ˉu1,p2Rp···δM+2ˉuM,p2Rp]]T

    该2维系统估计模型中有M个发射源与P个目标,可以获得个(M+1)P个量测数据,而量测方程中有4P+M个未知量。因此,目标和发射源数量必须满足如下要求:(M+1)P4P+M

    考虑量测误差对系数矩阵ˉHˉZ的影响,式(7)中ˉHˉZ可以表示为数据矩阵和扰动矩阵之和,其中ˉHˉZ做如下变化

    ˉH=H+[F1E  F2E···FLE],ˉZ=Z+FL+1E (8)

    则式(7)可以表示为

    Z+FL+1E=(H+[F1E  F2E  ···  FLE])X (9)

    式中,L为向量X的长度

    Fi(j,k)=HjiEk (i=1,2,···,L;j,k=1,2,···,(M+1)P)
    FL+1(j,k)=ZjEk (i=1,2,···,L;j,k=1,2,···,(M+1)P)
    E=[eθ1eu1,1···euM,1···eθPeu1,P···euM,P]T 
    Z=[0(u21,1x21y21)···(u2M,1x2My2M)···0(u2M,1x21y21)···(u2M,Px2My2M)]T
    H=[blkdiag{h1CT(1)···h1CT(P)}[h2CT(1)···h2CT(P)]T]
    h1CT(p)=[tanθp10xtarpcos2θp2x12y12u1,p02xM2yM2uM,p0]
    h2CT(p)=[O1×M, diag[δ1+2u1,p2Rp···δM+2uM,p2Rp]]T

    将上述联合误差校正和目标定位问题转换为CTLS估计问题

    minX,E[F1E···FLEFL+1E]2F,s.t.  [HZ][X1]+[F1E···FLEFL+1E][X1]=0 (10)

    将上述约束优化问题转化为无约束优化问题

    minX[X1]TCT(HXG1HTX)1C[X1] (11)

    式中,C=[HZ], HX=Lj=1xjFjFL+1, G=L+1j=1FTjFj,xjX 的第 j 个分量。

    f(X)=[HXZ]T(HXG1HTX)1[HXZ],则f(X)X 处的梯度向量为

    Tk=[f(X)x1···f(X)xL]T=2(UTDHXUTB1) (12)

    式中,U=(HXG1HTX)1C[X1], DHX(HXZ)X的1阶求导,具体形式为

    [HI1+Hx1XHI2+Hx2X···HIL+HxLX],
    B1=[HXG1FT1UHXG1FT1U···HXG1FTLU]

    Hesse矩阵Hk

    Hk=2f(X)XXT=2UU×DHXX2DHXX(HXG1HTX)1(B1+B2)+2DHX(HXG1HTX)1DHTX2BT2(HXG1HTX)1DHTX+2BT2(HXG1HTX)1(B1+B2)2BT3G1B3+2BT1(HXG1HTX)1(B1+B2)2DHX(HXG1HTX)1B1 (13)

    式中,DHXX(HXZ)的2阶导数,UU=[U···U], B2=[F1G1HTXUF2G1HTXU···FLG1HTXU], B3=[FT1UFT2U···F TLU]

    则无约束优化问题式(11)可以通过牛顿迭代法进行求解,其迭代公式如式(14)

    (ˆXCT)k+1=(ˆXCT)kH1kTk (14)

    设CTLS解ˆXCT与真实值(目标位置与系统偏差)X之间的误差为ΔXCT=ˆXCTX,通过1阶小噪声扰动分析方法来推导CTLS算法的理论误差,得到估计误差和误差协方差如式(15)和式(16)

    ΔXCT=[HT(HXG1HTX)1H]1HT×(HXG1HTX)1ΔC[X1] (15)
    cov(ˆXCT)=(HT(HXG1HTX)1H)1 (16)

    式中,ΔC=[F1E  ···  FLE  FL+1E]

    上述CTLS算法中假设X中的变量相互独立的,然而辅助变量Rp=(xtarp)2+(ytarp)2与目标位置xtarpytarp相关,式(14)得到的估计值ˆXCT并不精确。对此,本节提出一种关联最小二乘估计对上述估计结果进行改进。

    考虑辅助变量Rp和目标位置(xtarp,ytarp)的相关性,选择目标位置的平方(xtarp)2, (ytarp)2以及系统偏差Δθp, δm为变量,构建估计模型如式(17)

    Z=HX+BΔXCT (17)

    式中,Z=[(ˆXCT)21(ˆXCT)22···(ˆXCT)24P3(ˆXCT)24P2(ˆXCT)4P···(ˆXCT)4P+M]T, X=[(xtar1)2(ytar1)2 ··· (xtarP)2 (ytarP)2 Δθ1 ··· ΔθPδ1 ··· δM]T, H=blkdiag{h···hP,IP,IM}, h=[100111],B= diag{2xtar1,2ytar1,2R1,···,2xtarP,2ytarP,2RP,1,···,1P+M}

    对式(17)采用加权最小二乘估计求解,得到估计值如式(18)

    ˆX=(HTW1H)1HTW1Z (18)

    其中,W=Bcov(ˆXCT)B

    关联最小二乘估计ˆX的估计误差协方差矩阵如式(19)

    cov(ˆXCT)=(HTW1H)1 (19)

    由于估计值ˆX中变量为目标位置的平方项(xtarp)2(ytarp)2(p=1,2,···,P),对其开方,在2维空间得到目标位置的4组候选值,记为ˆrp=(ˆxtarp,ˆytarp)。构建性能指标函数如式(20)

    f(ˆrp)=Zpˆdpˆbp2 (20)

    其中,Zp=[θpu1,p···uM,p]T, {\hat \text{b}_p} = {\left[ {\Delta {{\hat \theta }_p}\;{{\hat \delta }_{\rm{1}}} ·\!·\!· {{\hat \delta }_M}} \right]^{\rm{T}}}, {\hat \text{d}_p} \,= \left[ \,{\arctan\displaystyle\frac{{\hat x_p^{{\rm{tar}}}}}{{\hat y_p^{{\rm{tar}}}}},\  \sqrt {{{(\hat x_p^{{\rm{tar}}} - {x_1})}^2} \,+\, {{(\hat y_p^{{\rm{tar}}} \,-\, {y_1})}^2}}}\,+\right.(ˆxtarp)2+(ˆytarp)2,···,(ˆxtarpxM)2+(ˆytarpyM)2+(ˆxtarp)2+(ˆytarp)2]T

    由式(20)计算候选目标位置估计值ˆrp下的性能指标f(ˆrp),从中选择最佳目标位置估计值˜rp=(˜xtarp,˜ytarp)

    ˜rp=argminˆrpf(ˆrp) (21)

    ˆXDLS=[˜xtar1˜ytar1···˜xtarP˜ytarPΔθ1···ΔθPδ1···δM]T ,则   ˆXDLS 的估计误差协方差矩阵为

    cov(ˆXDLS)=Jcov(ˆX)J (22)

    式中,JˆXDLSˆX的雅克比矩阵,即

    J=diag{12xtar1,12ytar1,···,12xtarp,12ytarp2P,1,···,1P+M}

    将系统偏差估计带入量测方程进行校正,进行后验迭代估计,第i+1次迭代量测信息为

    u(i+1)m,p=u(i)m,pˆδ(i)m  (23)
    θ(i+1)p=θ(i)pΔˆθ(i)p (24)

    其中,ˆδ(i)m, Δˆθ(i)p分别为第i次双基距偏差和方位角偏差的估计。最终双基距偏差和方位角偏差估计值为

    ˆδm=iˆδ(i)m (25)
    Δˆθp=iΔˆθ(i)p (26)

    具体算法流程如下:

    步骤 1 初始化,令迭代次数i=0, ˆδm(0)=0, Δˆθp=0, ˆRp(0)=12MMm=1ˉum,p

    步骤 2 基于CTLS算法的估计:

    (1) 令k=0,采用LS结果作为CTLS算法的初值,即(ˆXCT)0=(ˉHTˉH)1ˉHTˉZ

    (2) 采用牛顿迭代算法计算CTLS的估计值(ˆXCT)k+1=(ˆXCT)kH1kTk,更新目标位置ˆxtarp(k), ˆytarp(k), ˆRp(k),以及偏差Δˆθp(k), ˆδm(k)

    (3) 判断maxm=1,···,M{|ˆδm(k)ˆδm(k1)|}ε1maxp=1,···,P{|Δˆθp(k)Δˆθp(k1)|}ε2,若不满足,则转步骤2(2);否则,得到估计值ˆXCT=(ˆXCT)k, ε1ε2为阈值,转步骤3;

    步骤 3 关联最小二乘估计:

    (1) 根据式(18)计算,得到(ˆxtarp)2(k), (ˆytarp)2(k), Δˆθ(i)p(k)ˆδ(i)m(k)

    (2) 对上述结果(ˆxtarp)2(k), (ˆytarp)2(k),采用式(21)计算得到目标位置ˆxtarp(k), ˆytarp(k)

    步骤 4 误差校正下后验迭代估计:

    (1) 根据式(25)和式(26)计算偏差Δˆθpˆδm

    (2) 根据式(23)和式(24)更新量测数据u(i)m,pθ(i)p;更新迭代次数i=i+1

    (3) 当maxm=1,,M{|ˆδ(i)m|}ε3maxp=1,,P{|Δθ(i)p|}ε4, ε1ε2为阈值,迭代停止,转步骤5,否则转步骤2;

    步骤 5 获得偏差估计值ˆδmΔˆθp,以及目标位置估计值ˆxtarpˆytarp

    本节通过仿真实验评估本文算法的定位性能,仿真场景设置如下:场景中有10个外辐射源,1个观测站,8个待估计目标,外辐射源的位置随机分布在60 km×60 km的平面,几何分布图见图1

    图 1  目标、接收站和发射源位置关系图

    双基距系统偏差设为[3, 1, 5, 3, 4, 4, 1, 2, 3, 4],单位为km;方位角系统偏差设为[0.04, 0.04, 0.02, 0.02, 0.03, 0.03, 0.01, 0.01],单位为rad。方位角和双基距的测量误差设置均服从零均值的高斯分布。方位角测量误差标准差σθ为0.02 rad,到达时间测量误差标准差στ设置为0.1 ns。

    目标位置的估计精度用均方根误差(RMSE)来衡量,定义如式(27)

    RMSE=1LLl=1((ˆxtar(l)x)2+(ˆytar(l)y)2) (27)

    其中,ˆxtar(l)ˆytar(l)表示第l次蒙特卡洛仿真参数估计值,L表示蒙特卡洛次数,本实验中蒙特卡洛仿真次数设置为200。

    为比较分析系统偏差校正对目标定位的影响。首先,将本文提出的误差校正下DOA/TDOA目标定位和未考虑系统偏差校正下目标定位方法[5]进行仿真比较分析,仿真结果如图2所示。

    图 2  考虑和未考虑误差校正下目标定位估计性能

    图2可知,系统偏差对目标定位精度影响较大。本文提出的误差校正下DOA/TDOA目标定位算法估计精度较好,在测量误差较小时,估计均方根误差RMSE满足克拉美罗下界(CRLB)。

    假设目标按某一直线做匀速运动(见图3),分析运动状态下误差校正下DOA/TDOA目标定位算法对目标位置估计性能。由图3可知,未考虑系统偏差影响下对目标位置估计将会产生偏差,使得估计轨迹偏离实际轨迹。而系统偏差校正下DOA/TDOA目标定位算法在杂波较少的环境下具有良好的目标跟踪性能。

    图 3  考虑和未考虑误差校正下目标跟踪轨迹

    为了验证不同估计算法对目标定位性能的影响。将本文提出的基于关联后验CTLS算法与文献[15]中两步加权最小二乘(简称两步WLS)算法和文献[8]中关联后验迭代最小二乘(简称关联后验ILS)算法进行比较。仿真结果见图4

    图 4  目标位置估计均方根误差比较图

    图4可知,本文提出的关联后验CTLS算法定位精度可逼近CRLB,在噪声分量统计相关时克服两步加权WLS不能达到最优解的问题。比较3种不同估计算法下的目标定位精度,根据图4的结果得到:本文提出的关联后验CTLS算法定位精度优于关联后验迭代最小二乘算法和两步加权最小二乘算法。关联后验关联后验迭代最小二乘算法在两步加权最小二乘算法基础上通过后验迭代提高了目标位置的估计精度,但对系统偏差值估计影响较小。本文提出的关联后验CTLS算法考虑了量测噪声结构化和相关性,定位精度显著提高。

    为了进一步分析量测噪声对本文提出的关联后验CTLS算法对定位误差的影响,考虑不同到达时差量测噪声与不同方位角量测噪声下的不同目标的位置估计均方误差。设置方位角的量测标准差σθ为10–6~0.1 rad;到达时差的测量标准差στ设置为10–5~105 ns,仿真结果如图5图6所示。

    图 5  不同到达时差量测方差下目标位置估计误差
    图 6  不同方位角量测方差下目标位置估计误差

    图5图6分别给出了3种算法在不同到达时差量测噪声与不同方位角量测噪声下目标的位置估计均方误差。从图中可以看出,随着测量误差的增加,各算法的均方误差都有所增加。当测量误差较大时,两步加权最小二乘算法的均方误差急剧上升,主要是由于迭代初始值偏离真实值较远,导致算法局部收敛,甚至发散。关联后验迭代最小二乘算法在测量误差较大时性能优于两步加权最小二乘算法,设计后验迭代进一步校正,提高了目标位置估计精度。本文提出的关联后验CTLS算法克服了上述两种算法在噪声分量统计相关时不能达到最优的不足,在测量噪声适中时可以达到CRLB。在量测误差较大时,关联后验CTLS算法明显优于两步加权最小二乘算法和关联后验迭代最小二乘算法,具有更准确且鲁棒性好的定位精度。

    本文研究了误差校正下外辐射源雷达无源定位问题,提出了一种基于CTLS的单站DOA/TDOA联合误差校正和定位算法。通过引入辅助变量,将非线性的DOA和TDOA量测方程变成伪线性定位方程。考虑伪线性化后量测噪声结构化和相关性,采用CTLS算法得到目标位置的高精度估计。在此基础上利用辅助变量与目标位置的关联性,设计关联最小二乘算法对CTLS算法估计值进一步改进。最后,将系统偏差估计值带入量测方程进行校正,通过后验迭代,获得校正下目标位置估计。仿真结果表明:本文提出的关联后验CTLS算法在测量噪声适中时可以达到CRLB。在量测误差较大时,关联后验CTLS算法明显优于两步WLS算法和关联后验迭代最小二乘算法,具有更准确且鲁棒性好的定位精度。本文研究的误差校正下的无源定位算法未考虑多目标数据关联,系统偏差的数据关联和校正也是下一步需要研究的工作。

  • 图  1  FPVA架构及其拓扑连接图

    图  2  制造缺陷示例[11]

    图  3  FPVA生物芯片高阶综合示例

    图  4  FPVA下容错导向的高阶综合算法流程图

    图  5  动态容错技术示例

    1  动态容错绑定算法

     输入:FPVA单元集C,操作集O,组件数量为NM的组件库M,物理故障位置Fi(包括合并单元、故障单元及包含故障连接的单元)
     输出:一个容错的绑定方案
      //初始绑定阶段
      for each operation Oi of O do
       Banding(Oi,Mj) = Random(0, NM–1);//将操作Oi随机绑定到一个组件Mj
      end for
      for each cell Ci of C do
       if Ci == Fi then
         Ci_state = –1;//标记为不可用单元
        Continue;
        else
         Ci_state = 0;//标记为空闲单元
         Continue;
       end if
      end for
      //绑定调整阶段
      for each module Mj of M do
       for each cell Ck of Mj do
        if Ck_state == –1 then //Ck为不可用单元
         Construct_spare_module(Mj);//根据双向冗余技术从空闲单元中选择备用单元
         Banding(Oi,Mj);
        end if
        if Done(Mj) == True do //组件上的操作已执行完成
          Ck_state = 0; //根据单元功能转换将组件Mj占据单元转换为空闲单元
         end if
       end for
      end for
    下载: 导出CSV

    2  动态容错调度算法

     输入:FPVA单元集C, 操作集O,操作间的依赖关系,每个操作执行时间te(Oj),和输入流体,物理故障位置Fi(包括故障单元以及包
     含故障连接的单元)
     输出:一个容错的调度方案
     //初始调度顺序生成
      for each operation Oi of O do
      pri(Oi)=Ojson(Oi)te(Oj)+tc×|son(Oi)1|;//计算操作Oi的优先级
      end for
      Sorting(O);//根据调度优先级由大到小将操作排序
      for each cell Ci of C do
       if Ci == Fi then
        Ci_state = –1;//标记为不可用单元
        Continue;
       else
        Ci_state = 0;//标记为空闲单元
        Continue;
       end if
      end for
      //调度顺序调整
       for each operation Oi of O do
        for each fluid rj of Oi do
         for each cell Ck of rj do
         if Ck_state == –1 then // Ck为不可用单元
          Construct_spare_path(rj);//根据双向冗余技术从空闲单元中选择备用单元
         end if
         if Reached (rj) == True do //输入流体已到达目标组件
          Ck_state = 0;//根据单元功能转换将流体rj占据单元转换为空闲单元
         end if
        end for
       end for
      end for
    下载: 导出CSV

    表  1  图3对应的绑定与调度方案

    时间(s) 动作
    0tc 分别运输输入流体r1, r3, r5
    组件M1, M2, M3
    tc2tc 分别运输输入流体r2, r4到组件M1, M2
    2tc~(2tc+4) 执行混合操作O1, O2
    (2tc+4)(3tc+4) 运输O1, O2的混合产物到混合器M3
    (3tc+4)(3tc+8) 执行混合操作O3
    下载: 导出CSV

    表  2  策略有效性对比结果

    测试用例 (输入流体数,输出流体数,
    混合操作数)
    FPVA
    尺寸
    生物测定完成时间(s) 流体运输路径总长度(mm)
    基准算法 本文算法 优化(%) 基准算法 本文算法 优化(%)
    PCR (8,1,7) ×8×8 14.5 13.8 4.8 56.9 54.4 4.4
    IVD1 (12,6,6) 8×8× 7.2 6.5 9.7 84.0 82.3 2.0
    IVD2 (18,9,9) 10×10× 8.8 8.4 4.5 174.3 171.3 1.7
    ProteinSplit1 (14,2,12) 10×10× 27.4 26.9 1.8 126.4 122.5 3.1
    ProteinSplit2 (32,4,23) 13×13 35.4 33.8 4.5 491.6 486.6 1.0
    Synthetic1 (5,1,4) 8×8 13.5 12.8 5.2 37.2 35.8 3.8
    Synthetic2 (13,1,12) 10×10× 22.6 21.8 3.5 121.6 116.8 3.9
    Synthetic3 (18,1,17) 12×12 28.1 27.4 2.5 217.6 210.7 3.2
    Synthetic4 (22,1,21) 13×13 27.4 26.6 2.9 312.6 305.4 2.3
    Synthetic5 (27,1,26) 13×13 29.9 28.7 4.0 386.9 377.2 2.5
    平均值 4.3 2.8
    下载: 导出CSV

    表  3  与RAS-FT[5]的性能对比结果

    测试用例生物测定完成时间(s)流体运输路径总长度(mm)容错成功率(%)
    RAS-FT[5]基于本文算法的
    架构综合算法
    优化(%)RAS-FT[5]基于本文算法的
    架构综合算法
    优化(%)RAS-FT[5]基于本文算法的
    架构综合算法
    优化
    PCR21.213.834.982.854.434.3100.053.047.0
    IVD111.56.543.5121.982.332.5100.040.060.0
    IVD214.38.441.3239.8171.328.6100.038.062.0
    ProteinSplit138.726.930.5173.1122.529.2100.013.087.0
    ProteinSplit250.133.832.5732.0486.633.5100.03.097.0
    Synthetic118.112.829.357.135.837.3100.029.071.0
    Synthetic230.021.827.3181.8116.835.8100.025.075.0
    Synthetic336.427.424.7327.4210.735.6100.016.084.0
    Synthetic435.826.625.7401.6305.424.0100.011.089.0
    Synthetic538.528.725.5505.3377.225.4100.08.092.0
    平均值31.531.676.4
    下载: 导出CSV
  • [1] VERPOORTE E and DE ROOIJ N F. Microfluidics meets MEMS[J]. Proceedings of the IEEE, 2003, 91(6): 930–953. doi: 10.1109/JPROC.2003.813570.
    [2] HU Kai, DINH T A, HO T Y, et al. Control-layer routing and control-pin minimization for flow-based microfluidic biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017, 36(1): 55–68. doi: 10.1109/TCAD.2016.2568198.
    [3] POLLACK M G, SHENDEROV A D, and FAIR R B. Electrowetting-based actuation of droplets for integrated microfluidics[J]. Lab on A Chip, 2002, 2(2): 96–101. doi: 10.1039/b110474h.
    [4] 陈志盛, 朱予涵, 刘耿耿, 等. 考虑流端口数量约束下的连续微流控生物芯片流路径规划算法[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.
    [5] TSENG T M, LI Bing, HO T Y, et al. Reliability-aware synthesis for flow-based microfluidic biochips by dynamic-device mapping[C]. 2015 52nd ACM/EDAC/IEEE Design Automation Conference, San Francisco, USA, 2015: 1–6. doi: 10.1145/2744769.2744899.
    [6] FIDALGO L M and MAERKL S J. A software-programmable microfluidic device for automated biology[J]. Lab on A Chip, 2011, 11(9): 1612–1619. doi: 10.1039/c0lc00537a.
    [7] LI Bing and SCHLICHTMANN U. Reliability-aware synthesis and fault test of fully programmable valve arrays (FPVAs)[C]. 2017 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems, Cambridge, UK, 2017: 1–1. doi: 10.1109/DFT.2017.8244449.
    [8] HUANG Xing, HO T Y, GUO Wenzhong, et al. Computer-aided design techniques for flow-based microfluidic lab-on-a-chip systems[J]. ACM Computing Surveys (CSUR), 2022, 54(5): 97. doi: 10.1145/3450504.
    [9] 刘耿耿, 叶正阳, 朱予涵, 等. 连续微流控生物芯片下一种多阶段启发式的流层物理协同设计算法[J]. 电子与信息学报, 2023, 45(9): 3401–3409. doi: 10.11999/JEIT221155.

    LIU Genggeng, YE Zhengyang, ZHU Yuhan, et al. A multi-stage heuristic flow-layer physical codesign algorithm for continuous-flow microfluidic biochips[J]. Journal of Electronics & Information Technology, 2023, 45(9): 3401–3409. doi: 10.11999/JEIT221155.
    [10] 朱予涵, 黄鸿斌, 林泓星, 等. 连续微流控生物芯片下基于序列对的流层物理设计算法[J]. 计算机辅助设计与图形学学报, 2022, 34(4): 535–544. doi: 10.3724/SP.J.1089.2022.19445.

    ZHU Yuhan, HUANG Hongbin, LIN Hongxing, et al. Sequence-pair-based flow-layer physical design algorithm for continuous-flow microfluidic biochips[J]. Journal of Computer-Aided Design & Computer Graphics, 2022, 34(4): 535–544. doi: 10.3724/SP.J.1089.2022.19445.
    [11] HU Kai, YU Feiqiao, HO T Y, et al. Testing of flow-based microfluidic biochips: Fault modeling, test generation, and experimental demonstration[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2014, 33(10): 1463–1475. doi: 10.1109/TCAD.2014.2336215.
    [12] ESKESEN M C, POP P, and POTLURI S. Architecture synthesis for cost-constrained fault-tolerant flow-based biochips[C]. 2016 Design, Automation & Test in Europe Conference & Exhibition, Dresden, Germany, 2016: 618–623.
    [13] DUBROVA E. Fault-Tolerant Design[M]. New York: Springer, 2013: 185. doi: 10.1007/978-1-4614-2113-9.
    [14] CHOUDHARY G, PAL S, KUNDU D, et al. Transport-free module binding for sample preparation using microfluidic fully programmable valve arrays[C]. 2020 Design, Automation & Test in Europe Conference & Exhibition, Grenoble, France, 2020: 1335–1338. doi: 10.23919/DATE48585.2020.9116370.
    [15] KUNDU D, GIRI J, MARUYAMA S, et al. Fluid-to-cell assignment and fluid loading on programmable microfluidic devices for bioprotocol execution[J]. Integration, 2021, 78: 95–109. doi: 10.1016/j.vlsi.2020.12.004.
    [16] SU Y S, HO T Y, and LEE D T. A routability-driven flow routing algorithm for programmable microfluidic devices[C]. 2016 21st Asia and South Pacific Design Automation Conference, Macao, China, 2016: 605–610. doi: 10.1109/ASPDAC.2016.7428078.
    [17] LAI Guanru, LIN Chunyu, and HO T Y. Pump-aware flow routing algorithm for programmable microfluidic devices[C]. 2018 Design, Automation & Test in Europe Conference & Exhibition, Dresden, Germany, 2018: 1405–1410. doi: 10.23919/DATE.2018.8342232.
    [18] YING Shuaijie, ROY S, HUANG J D, et al. Design for restricted-area and fast dilution using programmable microfluidic device based Lab-on-a-Chip[C]. 2021 24th Euromicro Conference on Digital System Design, Palermo, Italy, 2021: 488–494. doi: 10.1109/DSD53832.2021.00079.
    [19] GRIMMER A, KLEPIC B, HO T Y, et al. Sound valve-control for programmable microfluidic devices[C]. 2018 23rd Asia and South Pacific Design Automation Conference, Jeju, Korea (South), 2018: 40–45. doi: 10.1109/ASPDAC.2018.8297280.
    [20] LIN Y H, HO T Y, LI Bing, et al. Block-flushing: A block-based washing algorithm for programmable microfluidic devices[C]. 2019 Design, Automation & Test in Europe Conference & Exhibition, Florence, Italy, 2019: 1531–1536. doi: 10.23919/DATE.2019.8715125.
    [21] YU H C, LIN Y H, CHEN Zhiyang, et al. Contamination-aware synthesis for programmable microfluidic devices[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41(11): 5016–5029. doi: 10.1109/TCAD.2021.3134892.
    [22] DATTA P, CHAKRABORTY A, and PAL R K. Design optimization for programmable microfluidic devices integrating contamination removal and capacity-wastage-aware washing[J]. IETE Journal of Research, 2020, 66(6): 781–796. doi: 10.1080/03772063.2020.1811784.
    [23] LIANG Siyuan, LI Mengchu, TSENG T M, et al. CoMUX: Combinatorial-coding-based high-performance microfluidic control multiplexer design[C]. 2022 IEEE/ACM International Conference on Computer Aided Design, San Diego, USA, 2022: 1–9.
    [24] HUANG Xing, CAI Huayang, GUO Wenzhong, et al. Control-logic synthesis of fully programmable valve array using reinforcement learning[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2024, 43(1): 277–290. doi: 10.1109/TCAD.2023.3309740.
    [25] CAI Huayang, LIU Genggeng, GUO Wenzhong, et al. Adaptive control-logic routing for fully programmable valve array biochips using deep reinforcement learning[C]. 2024 29th Asia and South Pacific Design Automation Conference, Incheon, Korea, 2024: 564–569. doi: 10.1109/ASP-DAC58780.2024.10473962.
    [26] LIU Chunfeng, LI Bing, BHATTACHARYA B B, et al. Testing microfluidic fully programmable valve arrays (FPVAs)[C]. Design, Automation & Test in Europe Conference & Exhibition, Lausanne, Switzerland, 2017: 91–96. doi: 10.23919/DATE.2017.7926964.
    [27] LIU Chunfeng, LI Bing, BHATTACHARYA B B, et al. Test generation for microfluidic fully programmable valve arrays (FPVAs) with heuristic acceleration[C]. 2018 International Conference on IC Design & Technology, Otranto, Italy, 2018: 97–100. doi: 10.1109/ICICDT.2018.8399765.
    [28] LIU Chunfeng, LI Bing, BHATTACHARYA B B, et al. Test generation for flow-based microfluidic biochips with general architectures[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(10): 2530–2543. doi: 10.1109/TCAD.2019.2948904.
    [29] BERNARDINI A, LIU Chunfeng, LI Bing, et al. Efficient spanning-tree-based test pattern generation for programmable microfluidic devices[J]. Microelectronics Journal, 2018, 79: 38–45. doi: 10.1016/j.mejo.2018.06.011.
    [30] BERNARDINI A, LIU Chunfeng, LI Bing, et al. Fault localization in programmable microfluidic devices[C]. 2019 Design, Automation & Test in Europe Conference & Exhibition, Florence, Italy, 2019: 1607–1610. doi: 10.23919/DATE.2019.8715023.
    [31] LIU Genggeng, ZENG Yuqin, ZHU Yuhan, et al. Towards automated testing of multiplexers in fully programmable valve array biochips[C]. 2024 29th Asia and South Pacific Design Automation Conference, Incheon, Korea, 2024: 570–575. doi: 10.1109/ASP-DAC58780.2024.10473918.
    [32] LIU Genggeng, ZHU Yuhan, GUO Wenzhong, et al. Fault-tolerance-oriented physical design for fully programmable valve array biochips[C]. 2023 60th ACM/IEEE Design Automation Conference, San Francisco, USA, 2023: 1–6. doi: 10.1109/DAC56929.2023.10247720.
    [33] HUANG Xing, GUO Wenzhong, CHEN Zhisheng, et al. Flow-based microfluidic biochips with distributed channel storage: Synthesis, physical design, and wash optimization[J]. IEEE Transactions on Computers, 2022, 71(2): 464–478. doi: 10.1109/TC.2021.3054689.
  • 期刊类型引用(18)

    1. 韩辉,王东方,弓羽箭,徐贵洲,焦进星,刘杨. 基于MEM和TS-PSO的输电线路单点电晕放电定位方法研究. 电瓷避雷器. 2024(03): 1-7 . 百度学术
    2. 戎俊樵,仇洪冰,李燕龙. RSS和AOA融合的单站低空无线电辐射源定位算法. 计算机应用与软件. 2024(08): 126-131+174 . 百度学术
    3. 曾懿辉,舒应军,麦俊佳,李彬,吴新桥. 基于ARM模型的交流微电网故障北斗定位方法. 电网与清洁能源. 2023(04): 99-104 . 百度学术
    4. 赵玉超,袁宏拓,孙铭. 基于单步加权最小二乘的战场集结定位算法. 河北科技大学学报. 2022(01): 42-49 . 百度学术
    5. 宋辉,姬晓文,高琦,缑鹏超,王志强. 基于数据驱动的不规则用电检测误差校正系统设计. 电子设计工程. 2022(06): 109-112+117 . 百度学术
    6. 陈宇航,饶云华,潘宇盈,万显荣,吴敏渊. 分时多频外辐射源雷达发射站定位方法. 雷达科学与技术. 2022(03): 335-341+354 . 百度学术
    7. 杨军,庄文德,张育辉. 基于数据挖掘的电能误差数据自动化校正方法. 电子设计工程. 2022(24): 153-156+161 . 百度学术
    8. 丁超,陈喆,张宗堂,程玉胜. 一种互谱相位在时延估计中的应用方法. 电子与信息学报. 2021(03): 803-808 . 本站查看
    9. 左燕,蒋陶然,陈志猛,彭冬亮. 误差校正下单站多外辐射源BR/BRR多目标定位算法. 电子与信息学报. 2021(04): 1162-1169 . 本站查看
    10. 潘海瑞,刘传清,韦朴,周康,袁航. 面向地下变电站的UWB-CGN-BPNN定位算法研究. 电力信息与通信技术. 2021(05): 82-88 . 百度学术
    11. 秦宁宁,王超,杨乐,孙顺远. 基于多元高斯混合模型的离线指纹数据库. 电子与信息学报. 2021(06): 1772-1780 . 本站查看
    12. 衣晓,杜金鹏. 雷达与电子支援措施异步抗差航迹关联算法. 电子与信息学报. 2021(07): 1947-1953 . 本站查看
    13. 戴敏. 结合正则化求解的机场场面多点定位方法. 计算机工程与设计. 2021(10): 2995-3001 . 百度学术
    14. 明月,黄言言,刘罡. 基于迭代校正的视频图像亚像素角点检测仿真. 计算机仿真. 2021(11): 450-453+494 . 百度学术
    15. 张琳,张涛,郭希蕊,李福昌. 智能室内定位系统研究. 邮电设计技术. 2020(03): 28-32 . 百度学术
    16. 王建强,代阳. 基于高斯牛顿迭代估计的无线网络节点定位算法. 测绘工程. 2020(06): 8-12 . 百度学术
    17. 汤建龙,郭立博,董阳阳. 基于到达时间和到达方向联合定位的机动有源诱偏方法. 兵工学报. 2020(10): 2088-2095 . 百度学术
    18. 杨熠. 基于误差校正的自由空间光通信降噪方法研究. 电子设计工程. 2020(23): 120-124 . 百度学术

    其他类型引用(14)

  • 加载中
图(5) / 表(5)
计量
  • 文章访问数:  176
  • HTML全文浏览量:  97
  • PDF下载量:  26
  • 被引次数: 32
出版历程
  • 收稿日期:  2024-01-24
  • 修回日期:  2024-09-04
  • 网络出版日期:  2024-09-17
  • 刊出日期:  2024-11-01

目录

/

返回文章
返回