K终端可靠度分解算法中多边形→链简化定理的完善

无向网络K终端可靠度的分解算法中,包括多边形→链简化在内的等可靠度简化和分解定理结合,可以降低算法的复杂度。本文完善了边随机无向网络和混合随机无向网络的4#,6#,7#型多边形→链简化定理。计算机编程验证了其正确性。     

Factoring and reductions for networks with imperfect vertices

Factoring and reductions are effective methods for computing the K-terminal reliability of undirected networks, but they have been applied mostly to networks with perfect vertices. However, in real problems, vertices may fail as well as edges. Imperfect vertices can be factored like edges, but the complexity then increases exponentially with their number. A technique has been developed to account for the failure of vertices with small additional cost, using a modified method of factoring and reductions. This technique is very easy to integrate into a factoring algorithm. It consists of factoring not on a single element (e.g., a single edge) but on a set of elements (e.g., an edge and its endpoints). The problem is that random variables associated with the elements of the network are no longer independent. This can be handled by choosing factoring edges that have at least one perfect endpoint. This technique leaves the factoring algorithm practically unchanged. The only difference is that some supplementary probability values are kept for the imperfect vertices of the original and the induced graphs. For algorithms using simple reductions, it has negligible computational cost     

A Unified Formula for Analysis of Some Network Reliability Problems

A topological formula is derived for solving a variety of network reliability problems such as vertex-to-vertex communication from a source to a terminal; from a source to some specified subset of the vertices or else all vertices; between any given vertex-pair; between all vertex-pairs within a given subset of the vertices; or else between all vertex-pairs. The formula applies to networks consisting of imperfect (unreliable) vertices and/or links, and with failure events s-independent or not. The formula explicitly characterizes the structure of both cancelling and noncancelling terms in the reliability expression obtained by Inclusion-Exclusion, and involves only noncancelling terms. Earlier topological formulas for the source-to-terminal problem and the source-to-all-vertices problem are shown to be special cases of this new one.     

Reliability evaluation for distributed computing networks withimperfect nodes

This paper examines two compensating methods that: (1) account for imperfect nodes, and (2) can be embedded in most symbolic network reliability algorithms that presume perfect nodes. The Aggarwal method can be exponential in time with the number of links, whereas the Torrieri method is always linear. However the Torrieri method can yield incorrect results for some undirected networks. This paper points out such incorrectness and then proposes an efficient reliability evaluation algorithm (ENR/KW) accounting for imperfect nodes in distributed computing networks. Based on the concept of network partition, ENR/KW exploits some simple efficient techniques to handle the unreliable nodes, for directly computing the network reliability expression considering imperfect nodes instead of using any compensating method. The basic idea of ENR/KW is to partition the network directly into a set of smaller disjoint subnetworks by only considering link elements as if all nodes are perfect. Each disjoint subnetwork is generated by maintaining a specific directed graph structure to consider the effect of imperfect nodes. Therefore, the reliability expression for imperfect nodes can be obtained directly from the disjoint subnetwork and the specific directed graph. ENR/KW can be generalized to evaluate various network reliability measures considering imperfect nodes such as terminal-pair reliability, K-terminal reliability, and distributed-program reliability. Many experiments for evaluating the terminal-pair reliability and distributed-program reliability were performed on a SUN workstation to show the efficiency of ENR/KW in terms of the number of generated subnetworks and overall computation time     

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.     

Reliability analysis of redundant-path interconnection networks

The reliability of some redundant-path multistage interconnection networks is characterized. The classes of networks are the generalized indra networks, merged delta networks, and augmented C-networks. The reliability measures are terminal reliability and broadcast reliability. Symbolic expressions are derived for these reliability measures in terms of component reliabilities. The results are useful in comparing network designs for a given reliability requirement     

On finding minimum cost tree for multi-resource manycast in mesh networks

We investigate the problem of multi-resource manycast in mesh networks. The problem of multi-resource manycast extends the traditional manycast problem or k-Steiner tree problem, which finds a minimum cost tree spanning any k vertices. For the traditional manycast, all the vertices in the set of candidate destinations will be regarded as identical. However, the computing capability of the resource at each vertex may be not equivalent in the realistic networks. In this paper, we consider the problem of multi-resource manycast, in which the computing capability of the resource at a vertex is decomposed into discrete units. That is, each vertex may have multiple units of computing resources. The objective is to find a minimum cost tree spanning any k units of computing resources distributed in the networks. We show that multi-resource manycast is NP-Complete. The ILP formulation and approximation analysis are given for this problem. Simple polynomial-time heuristic algorithms are also proposed for the problem of multi-resource manycast. We investigate various approaches to implement multi-resources manycast in mesh networks, and verify the effectiveness of the approaches through simulation.     

利用因子分解方法计算网络的根通信可靠性

本文使用因子分解(factoring)的方法计算网络的根通信可靠性(存在从根点到每一个其它结点正常运行道路的概率)。我们充分利用无圈有向网络的拓扑结构提出了两个新的可靠性保护缩减(Reliability-Preserving Reduction)和一个进行因子分解的选边规则。在此基础上,给出一个因子分解算法(factoring algorithm)。对于不是非常稠密的网络,该算法是非常有效的。     

Reliability optimization of communication networks using simulated annealing

Two concepts of communication network reliability are considered. The first one, the ‘s-t’ reliability, is relevant for communication between a source station and a terminal station as in the case of a two way telephone communication. The second one, the overall reliability, is a measure of simultaneous connectedness among all stations in the network. An algorthm is presented which selects the optimal set of links that maximizes the overall reliability of the network subject to a cost restriction, given the allowable node-link incidences, the link costs and the link reliabilities. The algorithm employs a variaton of the simulated annealing approach coupled with a hierarchical strategy to achieve the gobal optimum. For complex networks, the present algorithm is advantageous over the traditional heuristic procedures. The solutions of two representative example network optimization problems are presented to illustrate the present algorithm. The potential utilization of parallel computing strategies in the present algorithm is also identified.     

Transmit selection diversity with maximal-ratio combining for multicarrier DS-CDMA wireless networks over Nakagami-m fading channels

We propose the scheme to integrate transmit selection diversity/maximal-ratio combining (TSD/MRC) with multicarrier (MC) direct-sequence code-division multiple access (DS-CDMA) for various wireless networks. Applying this TSD/MRC-based scheme, the transmitter jointly selects the optimal subcarrier-and-antenna pair to significantly decrease the peak-to-average power ratio (PAPR), which is one of the main problems inherently associated with MC DS-CDMA communications. Over the frequency-selective Nakagami-m fading channels, we develop the unified analytical framework to analyze the symbol-error rate (SER) of the scheme implemented in different types of wireless networks, while dealing with the perfect and imperfect channel state information (CSI) feedbacks, respectively. The imperfect feedbacks we focus on include delayed feedbacks and erroneous feedbacks. Taking the imperfectness of the feedback into account, the resultant SER is compared with that of both conventional selection diversity (SD)/MRC-based and space-time block coding (STBC)/MRC-based schemes. Our analyses show that in a wide variation of the feedback imperfectness, our proposed TSD/MRC-based scheme has significant advantages over the other two schemes for both downlink cellular networks and ad hoc wireless networks. However, our analytical findings indicate that TSD/MRC-based scheme cannot always outperform SD/MRC-based and STBC/MRC-based schemes even when the perfect CSI feedbacks are available.     

Error probabilities of noncoherent and coherent FSK in the presence of frequency and phase offsets for two-hop relay networks

We analyze the error performance of two-hop relay networks adopting frequency shift keying (FSK) over frequencyflat Rayleigh fading channels. It is assumed that relay networks consist of a source, a relay, and a destination without a direct path signal from the source to the destination and the relay adopts the amplify-and-forward protocol with a fixed gain. Firstly, considering imperfect frequency and phase synchronization, we obtain the exact error probability expressions for noncoherent and coherent binary FSK (BFSK). Secondly, assuming perfect frequency and phase synchronization, we derive a closed-form error probability approximation for coherent M-ary FSK (MFSK). The proposed methods can also be used for the error performance analysis of classical one-hop FSK systems with perfect/imperfect frequency and phase synchronization. The obtained error probability expressions will help the design of two-hop relay networks adopting FSK in determining the system parameters such as the transmission power at the source, the amplifying coefficient at the relay, and the maximum affordable frequency and phase offsets to satisfy the required error performance.     

Distributed differential space-time coding for asynchronous two-way relaying networks with Nakagami-m fading

A signal detection scheme was proposed for two-way relaying networks (TWRNs) using distributed differential space-time coding (DDSTC) under imperfect synchronization. Unlike most existing work perfect with synchronization assumed, a relative delay between the signals transmitted from both sources to the relay was considered. Since perfect channel state information (CSI) is difficult to be acquired in fast fading, the scenarios and computation complexity will be increased especially when there appear multiple relays, CSI is assumed unavailable at all nodes. Therefore, the article proposes a differential signal detection scheme based on estimating and cancelling the imperfect synchronization component in the received signal at the two source nodes, followed by a least square (LS) decoder. Simulations, using the Nakagami-m fading channel due to its versatile statistical distribution property, show that the proposed scheme for both source nodes are effective in suppressing the inter-symbol interference (ISI) caused by imperfect synchronization while neither the source nodes nor the relay nodes have any knowledge of CSI.     

Two unit repairable redundant standby system

The Laplace-Stieltjes (LS) transform for the distribution of time to first system failure (TFSF), transition probability, availability and mean time to system failure have been derived for two unit repairable redundant standby system with perfect as well as imperfect switchover condition. General expressions for computing various reliability performance indices have been obtained by using Markov Renewal techniques considering general distributions for time to failure and time to repair for the units.     

Distributed Generalized Low-Density Codes for Wireless Relay Networks

Distributed generalized low-density (GLD) codes are proposed for cooperative networks with multiple relays. Specifically, every relay can decode and forward one or several constituent codes of the GLD code to cooperatively construct a distributed GLD code using the partial error-detecting and error-correcting capabilities of the GLD code. The scheme can be flexibly adjusted to the variation of the relay number and work effectively under both perfect and imperfect source-relay channels verified by simulations.     

K-terminal reliability in ring networks

The authors present a new formula for computing K-terminal reliability in a communication network whose stations and links (vertices and edges) form a network graph G having a ring topology, where K-terminal reliability is the probability R_K(G) that a subset of R specific terminal stations in G can communicate. This new formula is applied to three Fiber Distributed Data Interface (FDDI) ring-network topologies, and for each topology the authors derive closed-form polynomial expressions of R_K(G) in terms of the failure probabilities of links, network ports, and station common units. The authors define the concept of the K-minimal Eulerian circuit and use combinations of these circuits to obtain K-graphs and their resulting dominations, thus extending the use of K-graphs to ring networks in which data messages, tokens, or other control frames traverse operative network links with an Eulerian tour. Distinct K-graphs having a nonzero sum of dominations are called noncanceled K-graphs and correspond exactly to terms in closed-form polynomial expressions of R_K(G). The authors show that trees have only one K-graph and that counter-rotating dual rings and rings of trees have at most 2K+1 noncanceled R-graphs. These results contribute the first closed-form polynomial R-terminal reliability expressions for the ring-of-trees topology. The results are useful in evaluating dependability, reliability, availability, or survivability of token rings and similar networks     

Achievable Limits on the Reliability of $k$-out-of- $n$:G Systems Subject to Imperfect Fault Coverage

Systems which must be designed to achieve very low probabilities of failure often use redundancy to meet these requirements. However, redundant k-out-of-n:G systems which are subject to imperfect fault coverage have an optimum level of redundancy, n _opt. That is to say, additional redundancy in excess of nopt will result in an increase, not a decrease, in the probability of system failure. This characteristic severely limits the level of redundancy considered in the design of highly reliable systems to modest values of n. Correct modeling of imperfect coverage is critical to the design of highly reliable systems. Two distinctly different k-out-of-n:G imperfect fault coverage reliability models are discussed in this paper: Element Level Coverage (ELC), and Fault Level Coverage (FLC). ELC is the appropriate model when each component can be assigned a given coverage level, while FLC is the appropriate model for systems using voting as the primary means of selection among redundant components. It is shown, over a wide range of realistic coverage values and relatively high component reliabilities, that the optimal redundancy level for ELC systems is 2 and 4 for FLC systems. It is also shown that the optimal probability of failure for FLC systems exceeds that of ELC systems by several orders of magnitude. New functions for computing the mean time to failure for i.i.d. k-out-of-n:G ELC, and FLC systems are also presented.     

一种计算Ad hoc网络K-终端可靠性的线性时间算法

研究计算Ad hoe网络K-终端可靠性的线性时间算法,可以快速计算Ad hoe网络K-终端可靠性。为了计算Ad hoe网络分级结构尽终端可靠性,可以采用无向概率图表示Ad hoe网络的分级结构。每个簇头由已知失效率的结点表示,并且当且仅当两个簇相邻时,两个结点间的互连由边表示。这个概率图的链路完全可靠,并且已知结点的失效率。此图的K-终端可靠性为给定K-结点集是互连的概率。文中提出了基于合适区间图计算尽终端可靠性的一种线性时间算法。本算法可用来计算Ad hoe网络的K-终端可靠性。其时间复杂度为O（｜V｜＋｜E｜）。     

Statistically robust design of linear filter for non-regenerative MIMO relay systems

This paper addresses the robust linear filter design issues for non-regenerative multiple input multiple output (MIMO) relay systems with imperfect channel state information (CSI) in both or partial hops. By considering statistical Kronecker channel model involving channel mean and antenna correlation, the robust linear processing schemes in imperfect CSI scenario for both hops are first derived based on mean squared error (MSE) criterion. In addition to this, the result is also extended to two practical scenarios, i.e. imperfect CSI for relay link with perfect CSI for access link and imperfect CSI for access link with perfect CSI for relay link. Simulation results show that the proposed scheme is capable of mitigating the performance degradation caused by the imperfect CSI.     

Class of communication networks with optimal connectivity

A network has optimal connectivity if the number of alternative paths between any pair of vertices is the greatest possible with the given number of lines and vertices. A new class of optimal configurations is described, which is sufficiently extensive to enable networks to be devised with almost any required connectivity, provided that the number of vertices is factorisable. Some implications for communication networks are discussed.