Disjunctive decomposition of a large switching function into several smaller switching functions is an efficient way of solving many problems in logic design and testing areas. Finding disjunctive decomposition of an ...
详细信息
Disjunctive decomposition of a large switching function into several smaller switching functions is an efficient way of solving many problems in logic design and testing areas. Finding disjunctive decomposition of an arbitrary switching function, however, is known to be a very difficult problem for which no practical solutions have been reported. Alternatively, a practical solution is to identify maximal supergates defined by Seth er al. (1985) which represent disjunctive decomposition of a logic circuit which realises a given switching function. An algorithm is presented which identifies maximal supergates in combinational logic circuits. The algorithm is based on both the graph-theoretic algorithms and the set manipulation algorithms such as depth-first search, biconnectivity and UNION/FIND. The time complexity of the algorithm is O(n + e), where n is the number of gates and e is the number of links between gates. Finally, the authors demonstrate experimental results of maximal supergates in ISCAS85 and ISCAS89 benchmark circuits.
One of the most compelling technological advances of this decade has been the advent of deploying wireless networks of heterogeneous smart sensor nodes for complex information gathering tasks. A wireless distributed s...
详细信息
One of the most compelling technological advances of this decade has been the advent of deploying wireless networks of heterogeneous smart sensor nodes for complex information gathering tasks. A wireless distributed sensor network (DSN) is a self-organizing, ad-hoe network of a large number of cooperative intelligent sensor nodes. Due to the limited power of sensor nodes, energy-efficient DSN are essentially multi-hop networks. The self-organizing capabilities, and the cooperative operation of DSN allow for forming reliable clusters of sensors deployed near, or at, the sites of target phenomena. Reliable monitoring of a phenomenon (or event detection) depends on the collective data provided by the target cluster of sensors, and not on any individual node. The failure of one or more nodes may not cause the operational data sources to be disconnected from the data sinks (command nodes or end user stations). However, it may increase the number of hops a data message has to go through before reaching its destination (and subsequently increase the message delay). In this paper, we focus on two related problems: computing a measure for the reliability of DSN, and computing a measure for the expected & the maximum message delay between data sources (sensors) & data sinks in an operational DSN. Given an estimation of the failure probabilities of the sensors, as well as the intermediate nodes (nodes used to relay messages between data sources, and data sinks), we use a probabilistic graph to model DSN. We define the DSN reliability as the probability that there exists an operating communication path between the sink node, and at least one operational sensor in a target cluster. We show that both problems are #P-hard for arbitrary networks. We then present two algorithms for computing the reliability, and the expected message delay for arbitrary networks. We also consider two special cases where efficient (polynomial time) algorithms are developed. Finally, we present some nu
The pyramid computer was initially proposed for performing high-speed low-level image processing. However, its regular geometry can be adapted naturally to many other problems, providing effective solutions to problem...
详细信息
The pyramid computer was initially proposed for performing high-speed low-level image processing. However, its regular geometry can be adapted naturally to many other problems, providing effective solutions to problems more complex than those previously considered. We illustrate this by presenting pyramid computer solutions to problems involving component labeling, minimal spanning forests, nearest neighbors, transitive closure, articulation points, bridge edges, etc. Central to these algorithms is our collection of data movement techniques which exploit the pyramid’s mix of tree and mesh connections. Our pyramid algorithms are significantly faster than their mesh-connected computer counterparts. For example, given a black/white square picture with n pixels, we can label the connected components in θ
Wireless sensor networks (WSNs) have many applications in industry and environmental monitoring where sensor nodes are deployed at fixed places for monitoring some phenomena. One of the commonly used deterministic dep...
详细信息
ISBN:
(纸本)9781424424122
Wireless sensor networks (WSNs) have many applications in industry and environmental monitoring where sensor nodes are deployed at fixed places for monitoring some phenomena. One of the commonly used deterministic deployment topologies is a rectangular grid. In [1], a WSN reliability measure that considers the aggregate flow of sensor data into a sink node is formulated, and it has been shown that computing this measure for an arbitrary WSN is #P-hard. Thus, it is unlikely that efficient algorithms for solving the problem exist. In this paper we consider a WSN deployed on rectangular W x L grid (WSG) and show that the problem remains #P-hard even when restricted to the grid graph model. We then present a routing scheme upon which we develop an O(nL2(w)) algorithm to compute the exact WSG reliability. Therefore, for W << L (thin grid or strip area) the algorithm is polynomial in n, while for a rectangle with arbitrary dimensions the running time is O(n root n2(root n)). We also present numerical results that demonstrate some of the potential applications of the algorithm. A noteworthy finding is that significant improvement in the WSG reliability can he achieved using more reliable sensors at the two boundaries adjacent to the sink node.
This paper proposes a new optimization framework that generates the optimal cable layout design of a tactical smart microgrid. The minimization function includes power loss and fuel consumption, reliability and graph ...
详细信息
ISBN:
(纸本)9781509002610
This paper proposes a new optimization framework that generates the optimal cable layout design of a tactical smart microgrid. The minimization function includes power loss and fuel consumption, reliability and graph aesthetic issues are considered as maximization functions. By leveraging multiple technologies and strategies, a design-phase heuristic tool is proposed on the following contributions;(i) apply graphtheoretic approaches to minimize the spanning tree of a network and (ii) employ clustering methods to split the network into electro-mechanically stable islands. This paper also proposes an algorithm that takes into accounts for physical restrictions due to geographical land area. To ensure reconfiguration resiliency with respect to the number of terminals, communication reliability throughout the sectionalized network, operation sustainability from the perspective of network protection, the ability of the proposed heuristic tool is demonstrated on one line (full three phase) diagrams by utilizing the alternating Steiner point introduction method to attain the global optimal solution.
暂无评论