Sensor network design based on system-wide reliability criteria. Part I: Objectives

Reliability based criteria are quite popular for optimal sensor network design. We present a modified definition of system reliability for sensor network design for two applications: reliable estimation of variables in a steady state linear flow process, and reliable fault detection and diagnosis for any process. Unlike the weakest-link based definition of system reliability in the literature, the proposed definition considers the entire system and is consistent with the reliability concept used in classical reliability literature. For each application, dual approaches for defining system reliability are proposed, and their analogy with the reliability problem in the classical reliability literature is established. Using examples and stochastic simulations, the advantage of using the proposed system reliability in contrast to the existing definition is illustrated. Part II of this series of articles presents methods for efficient generation of the system reliability function and its use in optimization-based approaches for designing optimal sensor networks.     

A constraint programming approach to cutset problems

We consider the problem of finding a cutset in a directed graph G=(V,E)$G=(V,E)$, i.e., a set of vertices that cuts all cycles in G  . Finding a cutset of minimum cardinality is NP-hard. There exist several approximate and exact algorithms, most of them using graph reduction techniques. In this paper, we propose a constraint programming approach to cutset problems and design a global constraint for computing cutsets. This cutset constraint is a global constraint over boolean variables associated to the vertices of a given graph and states that the subgraph restricted to the vertices having their boolean variable set to true is acyclic. We propose a filtering algorithm based on graph contraction operations and inference of simple boolean constraints, that has a linear time complexity in O(|E|+|V|)$O(|E|+|V|)$. We discuss search heuristics based on graph properties provided by the cutset constraint, and show the efficiency of the cutset constraint on benchmarks of the literature for pure minimum cutset problems, and on an application to log-based reconciliation problems where the global cutset constraint is mixed with other boolean constraints.     

电力系统振荡中心的暂态能量解析

根据结构保持的多机电力系统模型分析了电力系统大扰动后暂态能量在网络中的分布特性,重点研究了故障后系统振荡中心处暂态能量的变化规律,在单机系统中给出了证明,并在多机系统中进行了仿真验算.研究结果表明:随着系统稳定程度的恶化,系统的振荡中心附近是故障后暂态能量冲击最严重的区域,系统沿振荡中心所处的割集"撕裂".     

利用割集实现矿井通风系统中调节点的转移

矿井通风系统调整是矿井生产的日常工作之一，调整方案的优劣直接关系到矿井的安全生产。文章根据矿井的实际，利用通风网络图割集的性质，实现了通风系统中调节点的转移，为通风系统调整提供了多种解决方案，并给出了应用实例。     

Separators in Graphs with Negative and Multiple Vertex Weights

A separator theorem for a class of graphs asserts that every graph in the class can be divided approximately in half by removing a set of vertices of specified size. Nontrivial separator theorems hold for several classes of graphs, including graphs of bounded genus and chordal graphs. We show that any separator theorem implies various weighted separator theorems. In particular, we show that if the vertices of the graph have real-valued weights, which may be positive or negative, then the graph can be divided exactly in half according to weight. If k unrelated sets of weights are given, the graph can be divided simultaneously by all k sets of weights. These results considerably strengthen earlier results of Gilbert, Lipton, and Tarjan: (1) for k=1 with the weights restricted to being nonnegative, and (2) for k>1 , nonnegative weights, and simultaneous division within a factor of (1+ε ) of exactly in half. Received November 21, 1995; revised October 30, 1997.     

求图的约束最小割集的一个有效算法及其应用

本文提出确定把无向连通图G(V,E)切割为两个子图G_1(V_1,E_1)和G_2(V_2,E_2)且满足顶点集V_1和V_2的顶点数|V_1|和|V_2|为给定值的约束最小割集的一种有效算法。该算法理论比较简单,步骤简捷有效,并能保证在多项式时间内获得最优解;此外,本文举例说明该算法具体步骤过程并介绍该算法在计算机辅助电路分析和设计中的某些实际应用。     

计算机辅助装配顺序生成方法研究

装配顺序生成是装配设计自动化中的一个重要而复杂的问题。本文在分析现有装配模型的基础上，引入虚拟子装配体的概念，提出了装配层状关系模型，采用割集法和与／或图产生可行装配顺序，给出了二级圆柱齿轮减速器装配工艺规划的应用实例。