This work addresses fault-tolerant distributed decision fusion in the presence of sensor faults when local sensors sequentially send their local decisions to a fusion center. This work also proposes a collaborative sensor fault detection (CSFD) scheme for eliminating unreliable local decisions when performing distributed decision fusion. In particular, the concept of pseudo-sensor faults is presented. Due to the difficulty in determining pseudo-sensor faults in real time based on the minimization of the error probability, an upper bound is established on the fusion error probability, where distributions of local decisions are not necessarily identical. Given a pre-designed fusion rule under the assumption of identical local decision rules in fault-free environments, this bound can then characterize the fusion error probability when local decisions are no longer identical due to sensor faults. Hence, a criterion is proposed based on this error bound to determine a set of pseudo-faulty nodes at each time. Once the fusion center identifies the pseudo-faulty nodes, all corresponding local decisions are removed from the computation of likelihood ratios adopted to make the final decision. To enhance the efficiency of the proposed search criterion, another, less complex criterion is developed by integrating the Kullback-Leibler distance. Simulation results indicate that this less complex criterion provides even better fault-tolerance capability in some situations when sensor faults significantly deviate from normally operating sensors. Performance evaluation results also indicate that the fault-tolerance capability of the proposed approach employing a CSFD scheme is superior to conventional decision fusion.

This work addresses the design of a distributed fault-tolerant decision fusion in the presence of sensor faults when the local sensors sequentially send their decisions to a fusion center. A collaborative sensor fault detection (CSFD) scheme is proposed here to eliminate unreliable local decisions when performing distributed decision fusion. Based on the pre-designed fusion rule, assuming identical local decision rules and fault-free environments, an upper bound is established on the fusion error probability. According to this error bound, a criterion is proposed to search the faulty nodes. Once the fusion center identifies the faulty nodes, all corresponding local decisions are removed from the computation of the likelihood ratios that are adopted to make the final decision. Performance evaluation results indicate a significant improvement in fault-tolerance capability from the proposed approach over the conventional decision fusion without utilizing CSFD.

Abstract Ann‐dimensional hierarchical cubic network [denoted by HCN(n)] contains 2nn‐dimensional hypercubes. The diameter of the HCN(n), which is equal ton+ ⌊(n+ 1)/3⌋ + 1, is about two‐thirds the diameter of a comparable hypercube, even though it uses about half as many links per node. In this paper, a maximal number of node‐disjoint paths are constructed between every two distinct nodes of the HCN(n). Their maximal length is bounded above byn+ ⌊n/3⌋ + 4, which is nearly optimal. The (n+ 1)‐wide diameter andn‐fault diameter of the HCN(n) are shown to ben+ ⌊n/3⌋ + 3 orn+ ⌊n/3⌋ + 4, which are about two‐thirds those of a comparable hypercube. Our results reveal that the HCN(n) has a smaller wide diameter and fault diameter than those of a comparable hypercube. © 2002 Wiley Periodicals, Inc.

Routing functions have been shown effective in deriving disjoint paths in the hypercube. In this paper, using a minimal routing function, k+1 disjoint paths from one node to another k+1 distinct nodes are constructed in a k-dimensional folded hypercube whose maximal length is not greater than the diameter plus one, which is minimum in the worst case. For the general case, the maximal length is nearly optimal (/spl les/ the maximal distance between the two end nodes of these k+1 paths plus two). As a by-product, the Rabin number of the folded hypercube is obtained, which is an open problem raised by S.C. Liaw and G.J. Chang (1999).

An n-dimensional hierarchical cubic network (denoted by HCN(n)) contains 2/sup n/ n-dimensional hypercubes. The diameter of an HCN(n), which is equal to n+[(n+1)/3]+1, is about two-thirds the diameter of a comparable hypercube, although it uses about half as many links per node. In this paper, a maximal number of node-disjoint paths are constructed between every two distinct nodes of an HCN(n). Their maximal length has an upper bound of n+[n/3]+4, which is nearly optimal. The (n+1)-wide diameter and n-fault diameter of an HCN(n) are shown to be n+[n/3]+3 or n+[n/3]+4, which are about two-thirds those of a comparable hypercube. Our results reveal that an HCN(n) has shorter node-disjoint paths, wide diameter, and fault diameter than a comparable hypercube.

A recursive network can be constructed with basic building blocks in a recursive manner. For example the hypercube is a recursive network because an n-dimensional hypercube consists of two (n-1)-dimensional hypercubes. A recursive network is said to be with complete connection if the subnetwork that constitute it are connected as a complete graph. A general broadcasting scheme is proposed for recursive networks with complete connection. The scheme is simple, efficient, and easy to be implemented. Moreover, no redundant message will be generated. Four networks: WK-recursive networks, hypercomplete networks, hypernet networks, and star networks, are taken as examples to show the effectiveness of the scheme.

Recently, WK-recursive networks have received much attention due to their many favorable properties. However, they suffered from a rigorous restriction on their sizes. Incomplete WK-recursive networks were proposed to relieve this restriction. In this paper, the topological properties of incomplete WK-recursive networks are investigated. It is shown that they contain Hamiltonian cycles if their connectivities are greater than one. A sufficient and necessary condition is also proposed for those with connectivity one to contain a Hamiltonian path. A linear-time algorithm using the prune-and-search technique is presented to compute their diameters. © 1998 John Wiley & Sons, Inc. Networks 32: 23–45, 1998

Given positive integers κ and l, let R(κ, l) denote the class of interconnection networks so that for any κ + 1 distinct nodes x, y1, y2, …, yκ there exist κ node-disjoint paths (except at x) of length at most l from x to y1, y2, …, yκ, respectively. The Rabin number of a network W with connectivity κ, denoted by rκ(W), is defined as min{l|W ∈ R(κ, l)}. The Rabin number problem is to compute rκ(W) for a given network W. Computing Rabin numbers for nontrivial networks is not easy, in general. Thus far, only the Rabin number of the hypercube has been computed. In this paper, some new results on the Rabin number problem are derived. First, a theorem relating the Rabin number with both wide diameter and fault diameter is obtained. This theorem can help in the derivation of lower bounds for the Rabin numbers of circulant networks, folded hypercubes, hierarchical folded-hypercube networks, generalized hypercubes, and WK-recursive networks. Moreover, upper bounds are also obtained for WK-recursive networks and a special class of generalized hypercubes. The Rabin numbers of a special class of circulant networks and a special class of generalized hypercubes are determined as a consequence of the derived upper and lower bounds. © 1997 John Wiley & Sons, Inc. Networks 30:219–230, 1997

The WK-recursive networks own two structural advantages: expansibility and equal degree. A network is expansible if no changes to node configuration and link connection are necessary when it is expanded, and of equal degree if its nodes have the same degree no matter what the size is. However, the number of nodes contained in a WK-recursive network is restricted to d/sup t/, where d>1 is the size of the basic building block and t/spl ges/1 is the level of expansion. The incomplete WK-recursive networks, which were proposed to relieve this restriction, are allowed to contain an arbitrary number of basic building blocks, while presenting the advantages of the WK-recursive networks. Designing shortest-path routing algorithms for incomplete networks is in general more difficult than for complete networks. The reason is that most incomplete networks lack a unified representation. One of the contributions of this paper is to demonstrate a useful representation, i.e., the multistage graph representation, for the incomplete WK-recursive networks. On the basis of it, a shortest-path routing algorithm is then proposed. With O(d/spl middot/t) time preprocessing, this algorithm takes O(t) time for each intermediate node to determine the next node along the shortest path.

The WK-recursive networks, which were originally proposed by Vecchia and Sanges, have suffered from the rigorous restriction on the number of nodes. Like the other incomplete networks, the incomplete WK-recursive networks have been proposed to relieve this restriction. In this paper, it is first shown that the structures of the incomplete WK-recursive networks are conveniently represented with multistage graphs. This representation can provide a uniform look at the incomplete WK-recursive networks. With its help, a linear-time algorithm using the prune-and-search technique is presented for computing the diameters of the incomplete WK-recursive networks.

In this paper, a new two-level interconnection network, called a hierarchical folded-hypercube network (HFN, for short), is proposed. The HFN takes folded hypercubes as basic modules which are connected in a complete manner. We investigate the topological properties of the HFN, including the diameter, cost, average distance, embedding, connectivity, container, /spl kappa/-wide diameter, and node-fault diameter. We show that the HFN can emulate algorithms which are executable on the ring or the mesh-connected computer with the same time complexities in big-O notation. Moreover, the HFN can embed a folded hypercube having the same number of nodes with constant dilation. We compute the diameter, node connectivity, best container, /spl kappa/-wide diameter, and node-fault diameter of the HFN. We present optimal routing and broadcasting algorithms for the HFN. The semigroup computation and descend/ascend algorithms can be executed as well on the HFN.>

Abstract Recently, with the support of the CAPRI (Concurrent Architecture and PRogramming environment for highly Integrated system) project, Vecchia and Sanges proposed a new general class of recursively scalable networks, termed WK‐recursive networks, and developed routing and broadcasting algorithms on them. They have also implemented the WK‐recursive networks using VLSI technology. This paper studies WK‐recursive networks by first investigating their topological properties such as diameter, connectivity, and Hamiltonicity. We then develop new and more efficient routing and broadcasting algorithms. Our routing algorithm can guarantee the shortest paths. Our broadcasting algorithm is much simpler and requires fewer extra bits to be transmitted. The broadcasting tree of our broadcasting algorithm is of minimal height (equal to the diameter), and each node receives the message exactly once. Moreover, we show the execution of descend/ ascend algorithms on the WK‐recursive networks using the bitonic sort as an illustrative example. © 1994 by John Wiley & Sons, Inc.