摘 要:最优诊断树是电子可测性设计与分析的重要研究内容,也是电子系统故障隔离的基础.针对国内对最优故障诊断树研究和应用的需求,介绍了采用启发式AO*(AOstar)算法求解最优故障诊断树的方法,并将该算法封装实现为COM组件.与国外可测性分析软件TEAMS生成的诊断树结果对比分析,表明结果准确,组件易扩展,可以方便的嵌入到可测性设计与分析以及故障诊断软件之中.
关 键 词 :最优诊断树;故障诊断;AO*算法;启发函数
最优诊断树是一种将电子系统故障形成的原因由总体至部分按树枝状逐级细化并隔离出故障的分析方法,也是隔离复杂系统发生的故障的一种简单、有效、很有发展前途的方法.故障诊断树的生成和优化涉及到测试点的选取、目标函数的确定、生成算法等多方面的问题.文献[1]研究了AO*启发式最优诊断树搜索算法,国外可测性分析软件TEAMS已经实现了故障诊断树生成功能[2],但存在技术封锁问题,国内仍缺乏相关的最优诊断树生成组件或软件平台[3]~[7].本文针对国内最优诊断树研究、应用的需求,实现了AO*最优诊断树算法,并封装为COM组件,可以方便嵌入到可测性设计与分析软件以及故障诊断软件之中.
1.最优诊断树生成算法
诊断树(也称测试序列)是诊断故障时的测试先后顺序.对系统进行测试时,最好在实现故障诊断的同时达到测试时间少、费用低等要求.而最优诊断树是在考虑测试结果、测试代价及故障率的同时,使测试代价最小的有效的序列.
求解测试序列(也可称为最优诊断树),可将问题用简洁的形式定义为五元组{S,P,T,C,D}之间的关系[3].其中
S等于[s0,s1,s2,等,]是系统状态的有限集合,s0为系统的无故障状态,而si(1≤i≤m)分别表示系统的m个不同故障状态;
P等于[p(s0),p(s1),等,p()]T是系统各状态的先验概率(也称故障率)向量集;
T等于[t1,t2,等,tn]是n个可选的测试集;
C等于[c1,c2,等,]T是测试代价向量集,由测试时间、人力需求及其他经济因素决定;
D等于[dij]是由故障集和测试集的二元依赖关系得到矩阵,其中系统无故障状态s0对应的行dij(1≤j≤n)值始终为0.
某系统含故障率和测试代价的依赖矩阵如表1所示.
1.1 启发评估函数
启发函数HEF是一个容易计算的最优测试代价的启发式评估函数h(x).本文的结合信息论和启发式搜索方法,将Huffman平均编码长度作为启发函数HEF[1].
检测设模糊集x的故障概率降序排序为p(s0)≥p(s1)≥等≥p(),其si∈x中,则与概率向量P等于[p(s0),p(s1),等,p()]T对应的最优Huffman编码长度向量为ω等于[1,2,等,m-1,m,m].模糊子集x的平均Huffman编码长度w*(x)为
一般地检测设测试代价按升序排序为0≤c1≤c2≤等≤,则h(x)的下限HEF如公式(2)
式中:w′(x)为w*(x)的整数部分,cj为测试成本.
1.2 AO*搜索算法
AO*算法是一种有序的、最佳优先的搜索算法.它根据启发式估值函数h(x)自顶向下扩展搜索图中的最有希望达到目标节点的节点x,本文使用公式(2)作为评估函数h(x).当扩展至底部时,采用下述公式(3)计算模糊集y的实际测试代价,并用公式(4)修正模糊集y的最小测试代价e,选择最合适的测试,即自底向上回溯.具体运算步骤参见文献[1].
)
(3)(4)式中:Eyj为采用tj展开模糊集y的实际测试代价,cj为tj的固有测试成本,yjp为模糊集y通过测试tj的子集,yif为未通过测试tj的子集,p(yjp)、p(yif)分别为模糊子集yjp、yjf的概率,E(yjp)、E(yjf)分别为模糊子集yjp、yjf的实际测试成本,Πy为前续测试已经使用过了的测试集.
2.软件设计及实现
本软件基于Windows操作系统,使用Visual C++6.0开发工具和面向对象的方法进行设计和开发.结构图如图1所示.
考虑到组件的独立性、平台移植性及整个软件的易扩展性,整体采用COM技术进行封装.如果按功能属性进行划分,可以大致分为AO*最优诊断树生成模块、显示交互模块.为了保障各子模块间内存数据的独立性,各子模块均包含独立的内部缓冲区,子模块间的数据传递是通过拷贝实现的.组件接口定义及模块设计介绍如下.
使用本组件时,只需要调用接口函数SetData(int* D,int m,int n,double* P,double* C)即可完成生成诊断树所需的{S,P,T,C,D}数据初始化.其中D为待分析系统的故障-测试依赖矩阵(也称D矩阵),m为故障源数(D矩阵的行数),n为测试数(D矩阵的列数),P为故障先验概率,C为测试成本.
AO*最优诊断树生成计算模块,是整个组件的核心部分.此模块的二叉树数据结构、启发函数F(x)及AO*最优诊断树递归搜索等所有元素的实现均是使用面向对象编程方法,自主独立设计开发的,与编译平台和操作系统无关,有较强的代码重用性和扩展性.AO*最优诊断树递归搜索算法实现的流程图如图2所示,图中curSelTest为当前节点所选的“最优”测试,S为故障集,T为测试集,虚线表示递归调用过程,点线表示逻辑传递.
诊断树显示、交互模块.显示绘制生成的最优诊断树结果,及处理人机交互时的操作事件.此模块是以MFC[9]基础搭建的,绘图部分采用GDI绘图方式实现,事件响应部分继承了MFC基本窗口类CWnd的事件响应机制,因为和诊断树生成模块是互为独立的,需要时只需单独对此模块进行升级即可.当AO*最优诊断树生成模块对接收到的初始化数据进行递归搜索计算后,将生成的二叉诊断树显示出来.包含中间节点、叶子节点、连接线,及显示树节点备注信息的提示标签,方便用户查看诊断信息.
COM组件对象模型(Component Object Model),是一种以组件为发布单元的对象模型,这种模型使各组件可以用一种统一的方式进行交互,是不同语言协作开发的一种标准.它具备模块独立性、代码重用性、语言无关性等优点.COM组件的应用程序的创建大体可分为六步,具体参考文献[8].
3.应用验证
针对故障-测试依赖矩阵为表1的系统,分别采用国外可测性分析软件TEAMS和本文开发的COM组件进行处理分析,并对生成的两个最优诊断树结果对比分析.
图3所示为国外可测性分析软件TEAMS故障诊断树模块的显示效果.其生成的测试序列为t4;t2,t5;t2,t3,最终生成11个节点,隔离出的故障状态依次为s0;s4,s1;s3,s2;s5,测试代价为2.18.
图4所示为本组件嵌入到可测性设计与分析软件的效果.整过过程回调了一次,生成的测试序列为t2;t4,t3;t3,t5,搜索过程生成了25个节点,最终生成2×m+1等于11个节点,隔离出的故障状态依次为s0;s3,s2;s4,s1;s5.测试代价为2.18,其值与TEAMS的结果一致.
进一步对比分析发现,隔离故障概率较高的状态s0,s5同样只需两步测试就能,而要隔离状态s4,s1,s3,s2均需要三步.与TEAMS的结果一致.
4.结束语
本文实现了启发式搜索AO*算法,并设计封装为COM组件.组件算法计算速度快,结果准确,接口简单易用,人机交互界面友好.可以方便嵌入到可测性设计与分析软件以及故障诊断软件之中.