As a signal transfer hub, switch matrix plays an extremely important role in the automatic test equipment (ATE). When the distance between the source node and destination node is the shortest, signals can be transmitted in a most efficient way. First, a physical model of switch matrix is presented. Then a mathematical model is constructed by using graph theory. In view of the least relay and highest reliability, the problem is considered as a shortest path search in un-weighted graph and weighted graph. These two graphs arestudied by BFS algorithm and Dijkstra algorithm, and the improvedalgorithm is put forward. An actual example shows how to build the model and find the optimum path. The improved algorithm could realize rapid automatic searchfor the optimum path, thus has potential applicationsin development of general adapters and design of software platform in ATE.
CHEN Yuqiang
,
SU Jian
,
ZHANG Lei
,
YANG Guozhen
. Optimum Path Searching Algorithm for ATE Switch Matrix[J]. Science & Technology Review, 2014
, 32(15)
: 37
-42
.
DOI: 10.3981/j.issn.1000-7857.2014.15.004
[1] Sun B J, Qin H L, Shen S T. An automatic design technique for hardware system of ATS[C]. Autotestcon 2006 IEEE, Anaheim CA, Sept 18-21, 2006.
[2] Burden J, Curry P A, Roby D, et al. Introduction to the nest generation automatic test system(NGATS) [C]. Autotestcon 2005 IEEE, Anaheim CA, Sept 26-29, 2005.
[3] Lemon R, Coulter B. Interface test adapter development & maintenance using a continuity/insulation automatic test station in large scale test systems[C]. Autotestcon 2009 IEEE, Anaheim CA, Sept 14-17, 2009.
[4] Ross W A. The impact of next generation test technology on aviation maintenance[C]. Autotestcon 2003 IEEE, Anaheim CA, Sept 22-25, 2003.
[5] Blanchard B S. Logistics. Engineering and management[M]. New York: Prentice Hall, 1992.
[6] Orlet J L, Murdock G L. NxTest augments legacy military ATE[J]. IEEE Aerospace and Electronic Systems Magazine, 2002, 17(11): 17-20.
[7] 赵劲松, 孟晓风. 一种ATE开关最短路径搜索算法[J]. 电子测量与仪 器学报, 2006, 20(3): 33-36. Zhao Jinsong, Meng Xiaofeng. A kind of BFS to search the optimum path of ATE switches[J]. Journal of Electronic Measurement and Instrument, 2006, 20(3): 33-36.
[8] 龚劬. 图论与网络最优化算法[M]. 重庆: 重庆大学出版社, 2009. Gong Qu. Optimization algorithms for network and graph[M]. Chongqing: Chongqing University Press, 2009.
[9] 赵瑞贤, 孟晓风, 王国华. 通用ATE开关资源测试路径模型及应用[J]. 北京航空航天大学学报:自然科学版, 2006, 32(2): 181-185. Zhao Ruixian, Meng Xiaofeng, Wang Guohua. General-unility testing path model of switches for ATE and application[J]. Journal of Beijing University of Aeronautics and Astronautics: Natural Science Edition, 2006, 32(2): 181-185.
[10] 王怡苹, 李文海, 文天柱. 面向信号测试的路径搜索算法研究[J]. 仪 器仪表学报, 2013, 34(7): 1650-1658. Wang Yiping, Li Wenhai, Wen Tianzhu. Research on path search algorithm for signal-oriented test[J]. Chinese Journal of Scientific Instrument, 2013, 34(7): 1650-1658.
[11] 张玮, 沈士团, 陈星. 自动测试设备多开关模型的构造方法及其实现[J]. 遥测遥控, 2003, 24(1): 25-29. Zhang Wei, Shen Shituan, Chen Xing. A kind of modeling method and implementation for multiple switch modules in ATS[J]. Journal of Telemetry Tracking and Command, 2003, 24(1): 25-29.
[12] 张海良, 苏岐芳, 林荣斐. 图论基础[M]. 北京: 清华大学出版社, 2011. Zhang Hailiang, Su Qifang, Lin Rongfei. Graph theory[M]. Beijing: Tsinghua University Press, 2011.
[13] 卢启衡, 冯晓红. 基于宽度优先搜索的路径生成算法[J]. 现代计算 机, 2006(12): 87-89. Lu Qiheng, Feng Xiaohong. Search path building algorithm based on breadth-first search[J]. Modern Computer, 2006(12): 87-89.
[14] 高利民, 李文慧, 孙慧. 双向广度搜索算法在联锁进路自动生成中的 应用[J]. 铁路计算机应用, 2007, 16(5): 43-45. Gao Limin, Li Wenhui, Sun Hui. Application of bidirectionalspan searched algorithm to automatic generating of interlocked path[J]. Railway Computer Application, 2007, 16(5): 43-45.
[15] 王国华, 杨中亮, 陈妮亚. ATE开关矩阵动态路径搜索算法[J]. 北京 航空航天大学学报: 自然科学版, 2010, 36(1): 39-42. Wang Guohua, Yang Zhongliang, Chen Niya. Dynamic path searching method for ATE switch matrix[J]. Journal of Beijing University of Aeronautics and Astronautics: Natural Science Edition, 2010, 36(1): 39-42.
[16] 王华. 基于邻接点算法的Dijkstra优化研究[J]. 计算机与数字工程, 2013(4): 518-520. Wang Hua. Improved Dijkstra algorithm based on the adjacent point in shortest path[J]. Computer & Digital Engineering, 2013(4): 518-520.