故障诊断中传感器配置优化的复杂性分析

摘要

为分析故障诊断中传感器(或测试点)配置优化问题的复杂性,在系统有向图模型中引入传感器配置掩码,定义了系统掩码有向图模型和多故障源集合的传感器配置掩码,利用传感器集合运算表达式形式化描述了系统故障可检测性和多故障可分辨性两个诊断性能指标,在此基础上提出了故障诊断传感器最优配置存在问题为NP困难问题的复杂性定理.通过归约到可满足问题(SAT)对提出的定理进行了严格证明,并设计一种自底向上的搜索算法寻找满足多故障可诊断性的传感器近似优化配置.%To analyze the complexity of the sensors (or monitor location) selection in fault diagnosis, the sensor selection mask is integrated into the directed graph model, and the definitions of mask directed graph (MDG) model and mask for multi-faults sources set are proposed, and two capabilities of diagnosis, the fault detectability and multi faults distinguishability are formally described with sensors set expressions. And based on these, as a complexity theorem, it is proposed that whether the most optimized sensor selection can be achieved is a NP hard problem, and this theorem is proved strictly by reducing it to a SAT problem, which is a typical NP hard problem. Finally, a down-up search algorithm is proposed to find the approximately optimum sensor locations.