1、第4 3卷 第1期桂 林 电 子 科 技 大 学 学 报V o l.4 3,N o.1 2 0 2 3年2月J o u r n a l o f G u i l i n U n i v e r s i t y o f E l e c t r o n i c T e c h n o l o g yF e b.2 0 2 3收稿日期:2 0 2 2-0 4-0 7基金项目:广西自然科学基金(2 0 1 5 G X N S F D A 1 3 9 0 0 3)通信作者:马峻(1 9 7 7-),男,教授,博士,研究方向为信号处理、机器视觉、图像处理、神经网络、光电测试。E-m a i l:m a j
2、u n g u e t.e d u.c n引文格式:许益镇,马峻,曾轲.基于A C O算法在可重构扫描网络中搜索最优测试链路的应用J.桂林电子科技大学学报,2 0 2 3,4 3(1):2 0-2 6.基于A C O算法在可重构扫描网络中搜索最优测试链路的应用许益镇1,马 峻1,2,曾 轲1(1.桂林电子科技大学 电子工程与自动化学院,广西 桂林 5 4 1 0 0 4;2.桂林电子科技大学 广西自动检测技术与仪器重点实验室,广西 桂林 5 4 1 0 0 4)摘 要:为了实现在可重构扫描网络中求解对嵌入式仪器测试时的最优测试链路问题,提出了一种基于A C O算法的必测点约束最优测试链路求解方
3、法。首先,将扫描网络中的整体元素抽象为计算机可以识别的节点网络结构。其次,针对网络中的环路问题,提出“活性”禁忌表,在搜索到必测的节点时释放禁忌表中的节点数据,使得被搜索过的节点能再次被搜索。最后,为了能够更好地搜索最优测试链路,引入信息素系数变化因子,将信息素的更新与网络规模结合,以减小信息素更新幅度,避免搜索后期信息素浓度过度增强导致陷入局部最优。此外,在链路搜索过程中采用自适应的信息素挥发系数,保证算法的收敛速率,提高全局搜索能力。仿真实验结果表明,该算法可以有效地实现可重构扫描网络中必测点最优测试链路的求解,与传统A C O算法相比,该算法的搜索效率更高,具有一定的实用性和适用性。关键
4、词:可重构扫描网络;信息素;A C O算法;环路;必测点最优测试链路中图分类号:T P 1 8 文献标志码:A 文章编号:1 6 7 3-8 0 8 X(2 0 2 3)0 1-0 0 2 0-0 7A p p l i c a t i o n o f A C O a l g o r i t h m f o r s e a r c h i n g o p t i m a l t e s t l i n k i n r e c o n f i g u r a b l e s c a n n i n g n e t w o r k sX U Y i z h e n1,MA J u n1,2,Z E
5、N G K e1(1.S c h o o l o f E l e c t r o n i c E n g i n e e r i n g a n d A u t o m a t i o n,G u i l i n U n i v e r s i t y o f E l e c t r o n i c T e c h n o l o g y,G u i l i n 5 4 1 0 0 4,C h i n a;2.G u a n g x i K e y L a b o r a t o r y o f A u t o m a t i c D e t e c t i n g T e c h n o l
6、 o g y a n d I n s t r u m e n t s,G u i l i n U n i v e r s i t y o f E l e c t r o n i c T e c h n o l o g y,G u i l i n,5 4 1 0 0 4,C h i n a)A b s t r a c t:I n o r d e r t o s o l v e t h e o p t i m a l t e s t l i n k p r o b l e m w h e n t e s t i n g e m b e d d e d i n s t r u m e n t s i
7、 n r e c o n f i g u r a b l e s c a n n i n g n e t-w o r k,a m e t h o d b a s e d o n A C O a l g o r i t h m i s p r o p o s e d.F i r s t l y,t h e o v e r a l l e l e m e n t s i n t h e s c a n n i n g n e t w o r k a r e a b s t r a c t e d i n t o a n o d e n e t w o r k s t r u c t u r e t
8、 h a t c a n b e r e c o g n i z e d b y t h e c o m p u t e r.S e c o n d l y,a i m i n g a t t h e l o o p p r o b l e m i n t h e n e t w o r k,a n a c t i v e t a b u t a b l e i s p r o p o s e d t o r e l e a s e t h e n o d e d a t a i n t h e t a b u t a b l e w h e n t h e d e s i g n a t e
9、 d-t e s t-p o i n t i s s e a r c h e d,s o t h a t t h e s e a r c h e d n o d e s c a n b e s e a r c h e d a g a i n.F i n a l l y,i n o r d e r t o m a k e t h e o p t i m a l t e s t l i n k b e t t e r s e a r c h e d,t h e p h e r o-m o n e c o e f f i c i e n t c h a n g e f a c t o r i s i
10、 n t r o d u c e d t o c o m b i n e t h e p h e r o m o n e u p d a t e w i t h t h e n e t w o r k s c a l e t o r e d u c e t h e p h e r o-m o n e u p d a t e r a n g e,s o a s t o a v o i d f a l l i n g i n t o l o c a l o p t i m i z a t i o n d u e t o e x c e s s i v e e n h a n c e m e n t
11、 o f p h e r o m o n e c o n c e n t r a t i o n i n t h e l a t e r s t a g e o f s e a r c h.M e a n w h i l e,t h e a d a p t i v e p h e r o m o n e v o l a t i l i z a t i o n c o e f f i c i e n t i s a d o p t e d t o e n s u r e t h e c o n v e r g e n c e r a t e o f t h e a l g o r i t h m
12、 a n d i m p r o v e t h e g l o b a l s e a r c h a b i l i t y.T h e s i m u l a t i o n r e s u l t s s h o w t h a t t h e a l g o r i t h m c a n e f f e c t i v e l y s o l v e t h e o p t i m a l t e s t l i n k o f t h e d e s i g n a t e d-t e s t-p o i n t s i n t h e r e c o n f i g u r a
13、 b l e s c a n n i n g n e t w o r k.A n d c o m p a r e d w i t h t h e b a s-i c A C O a l g o r i t h m,i t h a s h i g h e r s e a r c h e f f i c i e n c y,p r a c t i c a b i l i t y a n d a p p l i c a b i l i t y.K e y w o r d s:r e c o n f i g u r a b l e s c a n n i n g n e t w o r k s;p h
14、 e r o m o n e;A C O a l g o r i t h m;r i n g r o a d;o p t i m a l t e s t l i n k o f d e s i g n a t e d-t e s t-p o i n t sDOI:10.16725/45-1351/tn.2023.01.004第1期许益镇等:基于A C O算法在可重构扫描网络中搜索最优测试链路的应用 集成电路产业飞速发展,S o C的设计正在变得日益复杂,芯片上集成了大量不同功能的嵌入式仪器。为了解决对嵌入式仪器测试时的访问难题,保证芯片测试接口的通用性和复用性,I E E E 1 6 8 7测
15、试标准采用可重构扫描网络(r e c o n f i g u r a b l e s c a n n i n g n e t-w o r k s,简称R S N s)结构实现对复杂芯片系统嵌入式仪器的访问与测试1,在扫描网络中,测试链路选择是否优越极大地影响测试效率,如何选择最优测试链路就显得尤为重要。最优测试链路选择是指在对芯片上的嵌入式仪器进行访问操作时,在可获得实际的扫描网络中,根据仪器间的连接关系网络更快地实现对仪器的测试而做出的链路选择。对仪器进行测试时,数据的输入输出口是固定的,将被测试的仪器抽象为必测点,那么最优测试链路问题实际为必测点最优测试链路问题,也可看作是必经点最优路径问
16、题。D i j k s t r a算法是经典的路径算法,对于解决最优路径问题有显著效果2。黄书力等3采用D i j k s t r a算法和贪心理论将复杂的问题分解成几个子问题来解决,将网络中的节点分为源节点、必经节点和目的节点3个子集,由局部最优解最终推导全局最优解,实现对经过指定中间节点集的最优路径问题求解;但是,该算法只能应用于无向无环网络图中。王小会等4为解决交通诱导问题,反复迭代基本D i j k s t r a算法,实现在路网结构中对K个必经点最优路径的寻找,以满足用户的出行需要;但该算法搜索最优路径时耗大,内存占用大,不适用大规模的网络。康文雄等5设计多层D i j k-s t r a算法,通过分层回溯结构寻找局部最优解来快速求得全局最优解或次优解,出解速度快;但是采取回溯的方法将会增加路径搜索时间消耗,而且搜索到的路径可能并非是最优的路径。由于在扫描网络中仪器的顺序性和特殊性,网络内部测试链路会有环路的存在,同时,对芯片上仪器的访问具有顺序性,因此必测点最优测试链路为有向带环路的链路。采用D i j k s t r a算法求解必测点最优有向带环链路时存在搜索效率差、灵活
