Adaptive reliability satisfaction in wireless sensor networks through controlling the number of active routing paths

The number of active paths in multipath routing scenarios (with concurrent data transmission over the established paths) affects the provided reliability degree as well as the imposed overhead of path management. Since the reliability of individual links varies over the time, adaptively setting the sufficient number of active paths turns out to be essential. In this paper, we first propose a Reliability Estimation for WSNs (RE-WSNs) algorithm, based on ordered binary decision diagram (OBDD) data structure, which gives the network reliability in terms of the reliability of all individual links. Second, we propose a novel algorithm called adaptive reliability satisfaction–multipath routing (ARS–MR) which adaptively sets the sufficient number of active paths, aiming at keeping the network reliability within a desired quantitative range and minimizing path management overhead. In activation/inactivation process it further takes into account energy efficiency considerations. The proposed ARS–MR algorithm can be used in conjunction with any arbitrary multipath algorithm in WSNs. Simulation results with NS-2 reveal that ARS–MR is quite successful in timely reacting to variations of links reliability. Indeed, it manages the number of active paths and keeps the reliability of the network satisfactory over the course of network lifetime.     

OBDD-based network reliability calculation

An efficient method for evaluating the terminal-pair reliability based on an edge expansion tree and using an OBDD (ordered binary decision diagram) is presented. The effectiveness of the algorithm is demonstrated on the larger benchmarks collected in previous work. One notable case of the experimental results for a 2×20 lattice network is that the number of nodes in the OBDD is linearly proportional to the number of stages. This is significantly superior to previous algorithms which are based on the sum of disjoint products and has exponential complexity     

OBDD-based evaluation of k-terminal network reliability

An efficient approach to determining the reliability of an undirected k-terminal network based on 2-terminal reliability functions is presented. First, a feasible set of (k-1) terminal-pairs is chosen, and the 2-terminal reliability functions of the (k-1) terminal-pairs are generated based on the edge expansion diagram using an OBDD (ordered binary decision diagram). Then the k-terminal reliability function can be efficiently constructed by combining these (k-1) reliability expressions with the Boolean and operation. Because building 2-terminal reliability functions and reducing redundant computations by merging reliability functions can be done very efficiently, the proposed approaches are much faster than those which directly expand the entire network or directly factor the k-terminal networks. The effectiveness of this approach is demonstrated by performing experiments on several large benchmark networks. An example of appreciable improvement is that the evaluation of the reliability of a source-terminal 3/spl times/10 all-terminal network took only 2.4 seconds on a SPARC 20 workstation. This is much faster than previous factoring-algorithms.     

Efficient symbolic computation of generalised spectra

An efficient algorithm is presented for the calculation of any generalised spectrum represented as an algebraic decision diagram (ADD) from an ordered binary decision diagram (OBDD) of a Boolean function, and vice versa     

Determining terminal-pair reliability based on edge expansiondiagrams using OBDD

For calculating terminal-pair reliability, most published algorithms are based on the sum of disjoint products. However, these tree-based partitions lack the capability to avoid redundant computation due to the isomorphic sub-problems. To overcome these problems, an efficient methodology to evaluate the terminal-pair reliability, based on edge expansion diagrams using OBDD (ordered binary decision diagram) is presented. First, the success path function of a given network is constructed based on OBDD by traversing the network with diagram-based edge expansion. Then the reliability of the network is obtained by directly evaluating on this OBDD recursively. The effectiveness of this approach is demonstrated by performing experiments on benchmarks collected by previous works including the larger networks (from 4 to 2 ⁹⁹ paths). A dramatic improvement, as demonstrated by the experimental results for a 2-by-n lattice network is that the number of OBDD nodes is only linearly proportional to the number of stages, and is much better than previous algorithms which have exponential complexity by using the sum of disjoint products. The CPU time of reliability calculation for a 100-stage lattice network is only about 2.5 seconds with 595 nodes generated on a SPARC 20 workstation with 128 MBytes of memory. Thus, with this approach, the terminal-pair reliability of large networks can be efficiently evaluated better than thought possible     

Efficient pairing-free CP-ABE based on ordered binary decision diagram

To improve the computational efficiency of ABE,its access structure was optimized and a pairing-free CP-ABE scheme based on ordered binary decision diagram (OBDD) was proposed.Based on the elliptic curve cryptography,the complex bilinear pairing operation in traditional CP-ABE was replaced with the relatively lightweight scalar multiplication,thus the overall computation overhead was reduced.And OBDD was used as the access structure of CP-ABE,which can not only represent any Boolean expression about attributes,but also support both positive and negative attributes.The length of the key was independent of the number of attributes and the length of the ciphertext was only related to the number of valid paths in the access policy.The security and performance analysis show that the scheme can resist chosen plaintext attack under the decisional Diffie-Hellman (DDH) assumption,and the computation efficiency can meet the practical application requirements of Internet of things.     

一种基于有序二元决策图和布尔函数性质计算网络可靠性的算法

有序二元决策图(OBDD)被广泛用到网络可靠度的计算中,在基于OBDD计算网络可靠度时,其计算时间主要取决于参与操作的OBDD的大小,而OBDD的大小严重依赖于OBDD的变量序。该文根据布尔函数的性质和OBDD原理提出一种优化计算网络可靠性的算法(BF-OBDD),提高计算网络可靠性的效率。实验结果表明改进的算法有较少的 OBDD节点数量,在计算网络可靠性时,花费的时间较少。     

Exact ordered binary decision diagram size when representing classes of symmetric functions

An ordered binary decision diagram (OBDD) is a canonical, graphical representation of a switching function. The space complexity of this representation as well as the time complexity for manipulating functions in this form is determained by the number of vertices in the OBDD. Symmetric functions are a class of functions which include the basic Boolean gates such as NOT, AND, NAND, NOR, XOR, etc., as well as less basic functions, such as voter logic for redundant circuit implementations. Symmetric functions exploit the most powerful properties of OBDDs to a very great extent. OBDDs have been shown to have size of O(n²), where n is the number of switching variables. However, this says little of the actual performance of OBDDs in practice. Exact equations of OBDD size are derived for the common classes of symmetric functions, as well as an exact equation for the largest OBDD that can exist for any arbitrary symmetric function. It is shown that OBDDs are (n ²) for the majority of functions from each common class of symmetric functions beyond the simplest Boolean gates. Since most functions can be expected to be more complex to represent than symmetric functions, this result has profound implications to the straightforward application of OBDDs to large functional problems.This work was supported by the National Science Foundation under Grant MIP-8552537.     

Using ordered binary decision diagrams to factorize multi-level logic

A novel approach that employs ordered binary decision diagrams (OBDDs) is contributed to factorize multi-level logic functions by requiring as few literals as possible. A logic function with PLA format is represented as an OBDD form first. A heuristic decision method of variable ordering, called theorder lookahead method, is derived for the construction of OBDDs. This method is based on the constant cofactor and the number of erasable logic terms for each input variable. The total execution time of the OBDD construction by the above ordering decisions is very fast for some MCNC benchmarks. With the above OBDDs, we introduce a simple yet effective graph manipulation, calledEXT, to obtain a minimal number of literals in the Boolean function. This greedyEXT algorithm consists mainly of two phases. The first phase, calledgraph analysis, identifies the similarities between nodes on the same level in the OBDD. The second phase, calledtree analysis, utilizes the above features to extract the common parts of the nodes. TheEXT procedure runs from the bottom level up to the top level of the OBDD. The computational complexity depends on the number of nodes in the OBDD. The results of simulations show thatEXT has a very fast CPU execution time and a competitive literal ratio with other methods for some MCNC benchmarks.EXT will produce the smallest literal number, especially for structured or symmetric circuits.This work was supported, in part, by the National Science Council, Republic of China, under contract number NSC 83-0404-E009-010.     

An ROBDD-Based Combinatorial Method for the Evaluation of Yield of Defect-Tolerant Systems-on-Chip

In this paper, we develop a combinatorial method for the evaluation of the functional yield of defect-tolerant systems-on-chip (SoC). The method assumes that random manufacturing defects are produced according to a model in which defects cause the failure of given components of the system following a distribution common to all defects. The distribution of the number of defects is arbitrary. The yield is obtained by conditioning on the number of defects that result in the failure of some component and performing recursive computations over a reduced ordered binary decision diagram (ROBDD) representation of the fault-tree function of the system. The method has excellent error control. Numerical experiments seem to indicate that the method is efficient and, with some exceptions, allows the analysis with affordable computational resources of systems with very large numbers of components.      

Combinatorial methods for the evaluation of yield and operational reliability of fault-tolerant systems-on-chip

In this paper we develop combinatorial methods for the evaluation of yield and operational reliability of fault-tolerant systems-on-chip. The methods assume that defects are produced according to a model in which defects are lethal and affect given components of the system following a distribution common to all defects; the method for the evaluation of operational reliability also assumes that the fault-tree function of the system is increasing. The distribution of the number of defects is arbitrary. The methods are based on the formulation of, respectively, the yield loss and the operational unreliability as the probability that a given Boolean function with multiple-valued variables has value 1. That probability is computed by analyzing a ROMDD (reduced ordered multiple-value decision diagram) representation of the function. For efficiency reasons, a coded ROBDD (reduced ordered binary decision diagram) representation of the function is built first and, then, that coded ROBDD is transformed into the ROMDD required by the methods. We present numerical experiments showing that the methods are able to cope with quite large systems in moderate CPU times.     

Reliability Evaluation of Phased-Mission Systems With Imperfect Fault Coverage and Common-Cause Failures

This paper proposes efficient methods to assess the reliability of phased-mission systems (PMS) considering both imperfect fault coverage (IPC), and common-cause failures (CCF). The IPC introduces multimode failures that must be considered in the accurate reliability analysis of PMS. Another difficulty in analysis is to allow for multiple CCF that can affect different subsets of system components, and which can occur s-dependently. Our methodology for resolving the above difficulties is to separate the consideration of both IPC and CCF from the combinatorics of the binary decision diagram-based solution, and adjust the input and output of the program to generate the reliability of PMS with IPC and CCF. According to the separation order, two equivalent approaches are developed. The applications and advantages of the approaches are illustrated through examples. PMS without IPC and/or CCF appear as special cases of the approaches     

OBDD variable ordering by interleaving compacted clusters

An effective method for variable ordering of OBDDs (ordered binary decision diagrams) based on the interleaving of the compacted clusters is proposed. The novelty of this method lies in the application of the divide-and-conquer approach to efficiently find a good variable ordering for circuits with a large number of I/Os. One notable result from this method is that the OBDD is able to be built using the cs38417 circuit, the remaining unreported circuit in the ISCAS89 benchmark     

Lossless image compression using ordered binary-decision diagrams

A lossless compression algorithm for images based on ordered binary-decision diagrams (OBDDs) is presented. The algorithm finds an OBDD which represents the image exactly and then codes the OBDD efficiently. The results obtained show a great improvement with respect to a previous work     

A BDD-based algorithm for reliability analysis of phased-missionsystems

This paper presents a new algorithm (PMS-BDD) based on the binary decision diagram (BDD) for reliability analysis of phased-mission systems (PMS). PMS-BDD uses phase algebra to deal with the dependence across the phases, and a new BDD operation to incorporate the phase algebra. Due to the nature of the BDD, cancellation of common components among the phases can be combined with the BDD generation, without additional operations; and the sum of disjoint products (SDP) can be implicitly represented by the final BDD. Several examples and experiments show that PMS-BDD is more efficient than the algorithm based on SDP, in both computation time and storage space; this efficiency allows the study of some practical, large phased-mission systems     

Hierarchical Tree Alternative Path (HTAP) algorithm for congestion control in wireless sensor networks

Recent advances in wireless sensor networks (WSNs) have lead to applications with increased traffic demands. Research is evolving from applications where performance is not considered as a crucial factor, to applications where performance is a critical factor. There are many cases in the fields of automation, health monitoring, and disaster response that demand wireless sensor networks where performance assurances are vital, especially for parameters like power, delay, and reliability. Due to the nature of these networks the higher amount of traffic is observed when the monitored event takes place. Exactly at this instance, there is a higher probability of congestion appearance in the network. Congestion in WSNs is tackled by the employment of two methods: either by reducing the load (“traffic control”), or by increasing the resources (“resource control”). In this paper we present the Hierarchical Tree Alternative Path (HTAP) algorithm, a “resource control” algorithm that attempts, through simple steps and minor computations, to mitigate congestion in wireless sensor networks by creating dynamic alternative paths to the sink. HTAP is evaluated in several scenarios in comparison with another “resource control” algorithm (TARA), as well as with a “traffic control” algorithm (SenTCP), and also the case where no congestion control exists in the network (“no CC”). Results show that HTAP is a simple and efficient algorithm capable of dealing successfully with congestion in WSNs, while preserving the performance characteristics of the network.     

Energy Efficient Adiabatic Multiplier-Accumulator Design

This paper presents a strategy for minimizing non-adiabatic dissipation in adiabatic arithmetic units. The non-adiabatic dissipation is minimized by architectural design involving a small number of complex logic gates. Circuit design of complex adiabatic gates, based on ordered binary decision diagrams (OBDD), is introduced. An optimized architecture for adiabatic parallel multipliers is proposed and savings in energy dissipation over competing architectures are estimated. Experimental results obtained from implementation of an adiabatic multiply-accumulate (MAC) unit suggest that the proposed strategy provides substantial improvement in energy efficiency over equivalent non-adiabatic and alternative adiabatic implementations, while achieving a competitive operating speed.     

BDD-based reliability analysis of phased-mission systems with multimode failures

This paper proposes a new algorithm (DEP-BDD) based on binary decision diagram (BDD) for reliability analysis of phased-mission systems (PMS) with multimode failures. DEP-BDD is a BDD-based combinatorial model which can be used to deal with more than one kind of dependences by applying dependence algebra, which is a generalization of phase algebra that handles more complex dependences. The nature of the BDD contributes the efficiency and low computational complexity of this algorithm. Two examples are analysed to illustrate the applications and advantages of our approach.     

MIMO系统中基于信号可靠性判定的OSIC检测

排序串行干扰消除（Ordered Successive Interference Cancellation,OSIC）是多输入多输出无线通信系统中一种重要的信号检测技术。为了降低该算法的计算复杂度,首先提出了基于信号可靠性判决的排序串行干扰消除算法,根据所设计的信号可靠性判决（Signal Reliability Decision,SRD）结构的判决结果选择不同的方法消除信号间的干扰。为了进一步提升SRD-OSIC算法的检测性能,提出了局部最优（Local Optimized,LO）的LO-SRD-OSIC算法。仿真结果表明,SRD-OSIC算法仅需要传统OSIC算法一半的复杂度就能获得相近的误码率性能。不仅如此,当LO-SRD-OSIC算法与SRD-OSIC算法的计算复杂度相同时,LO-SRD-OSIC算法可以获得额外3 dB的误码率性能增益。     

K-Terminal Network Reliability Measures With Binary Decision Diagrams

We present a network decomposition method using binary decision diagrams (BDD), a state-of-the-art data structure to encode, and manipulate Boolean functions, for computing the reliability of networks such as computer, communication, or power networks. We consider the K-terminal reliability measure R_K, which is defined as the probability that a subset K of nodes can communicate with each other, taking into account the possible failures of the network links. We present an exact algorithm for computing the if-terminal reliability of a network with perfect vertices in O(m^.F_max ^.2^Fmax.B_Fmax), where B_Fmax is the Bell number of the maximum boundary set of vertices F_max, and m is the number of network links. Several examples, and experiments show the effectiveness of this approach.