Structure connectivity and substructure connectivity are innovative indicators for assessing network reliability and fault tolerance. Similarly, fault diameter evaluates fault tolerance and transmission delays in networks. This paper extends the concept of fault diameter by introducing two new variants: structure fault diameter and substructure fault diameter, derived from structure connectivity and substructure connectivity respectively. For a connected graph $G$ with $W$-structure connectivity $κ(G;W)$ or $W$-substructure connectivity $κ^s(G;W)$, the $W$-structure fault diameter $D_f(G;W)$ and $W$-substructure fault diameter $D_f^s(G;W)$ are defined as the maximum diameter of any subgraph of $G$ resulting from removing up to $κ(G;W)-1$ $W$-structures or $κ^s(G;W)-1$ $W$-substructures. For the $n$-dimensional hypercube $Q_n$ with $n \geq 3$ and $1 \leq m \leq n - 2$, we determine both $D_f(Q_n;Q_m)$ and $D_f^s(Q_n;Q_1)$. These findings generalize existing results for the diameter and fault diameter of $Q_n$, providing a broader understanding of the hypercube's structural properties under fault conditions.

Modern large-scale computing systems always demand better connectivity indicators for reliability evaluation. However, as more processing units have been rapidly incorporated into emerging computing systems, existing indicators (e.g.,$\ell$-component edge connectivity and$\ell$-extra edge connectivity) have gradually failed to provide the required fault tolerance. In addition, these indicators require, for example, that the faulty network should have at least$\ell$components (or that each component should have at least$\ell$nodes). These fault assumptions are not flexible enough to deal with diversified structural demands in practice circumstances. In order to address these challenges simultaneously, this article proposes two novel indicators for network reliability by utilizing the partition matroid technique, named matroidal connectivity and conditional matroidal connectivity. We first investigate the accurate values of (conditional) matroidal connectivity of$k$-ary$n$-cube$Q_{n}^{k}$, which is an appealing option as the underlying topology for modern parallel computing systems. Moreover, we propose an$O(k^{n-1})$algorithm for determining structural features of minimum edge sets whose cardinality is the conditional matroidal connectivity of$Q_{n}^{k}$. Simulation results are presented to verify our algorithm's correctness and further investigate the distribution pattern of edge sets subject to the restriction of partition matroid. We also present comparative analyses illustrating the superior edge fault tolerance of our findings in relation to prior research, which even exhibits an exponential enhancement when$k\geq 4$.

The$k$-ary$n$-cube$Q_{n}^{k}$is one of the most popular interconnection networks engaged as the underlying topology of data center networks, on-chip networks, and parallel and distributed systems. Due to the increasing probability of faulty edges in large-scale networks and extensive applications of the Hamiltonian path, it becomes more and more critical to investigate the fault tolerability of interconnection networks when embedding the Hamiltonian path. However, since the existing edge fault models in the current literature only focus on the entire status of faulty edges while ignoring the important information in the edge dimensions, their fault tolerability is narrowed to a minimal scope. This article first proposes the concept of the partitioned fault model to achieve an exponential scale of fault tolerance. Based on this model, we put forward two novel indicators for the bipartite networks (including$Q^{k}_{n}$with even$k$), named partition-edge fault-tolerant Hamiltonian laceability and partition-edge fault-tolerant hyper-Hamiltonian laceability. Then, we exploit these metrics to explore the existence of Hamiltonian paths and unpaired 2-disjoint path cover in$k$-ary$n$-cubes with large-scale faulty edges. Moreover, we prove that all these results are optimal in the sense that the number of edge faults tolerated has attended to the best upper bound. Our approach is the first time that can still embed a Hamiltonian path and an unpaired 2-disjoint path cover into the$k$-ary$n$-cube even if the faulty edges grow exponentially.

The matroidal connectivity and conditional matroidal connectivity are novel indicators to measure the real faulty tolerability. In this paper, for the$n$-dimensional alternating group graph$AG_{n}$, the structure properties and (conditional) matroidal connectivity are studied based on the dimensional partition of$E(AG_{n})$. We prove that for$S\subseteq E(AG_{n})$under some limitation on the number of faulty edges in each dimensional edge set, if$|S|\leq (n-1)!-1$, then$AG_{n}-S$is connected. We study the value of matroidal connectivity and conditional matroidal connectivity of$AG_{n}$. Furthermore, simulations have been carried out to compare the matroidal connectivity with other types of conditional connectivity in$AG_{n}$. The simulation result shows that the matroidal connectivity significantly improves these known fault-tolerant capability of alternating group graphs.

System diagnosis is process of identifying faulty nodes in a system. An efficient diagnosis is crucial for a multiprocessor system. The BGM diagnosis model is a modification of the PMC diagnosis model, which is a test-based diagnosis. In this paper, we present a specific structure and propose an algorithm for diagnosing a node in a system under the BGM model. We also give a polynomial-time algorithm that a node in a hypercube-like network can be diagnosed correctly in three test rounds under the BGM diagnosis model.

A set of$k$spanning trees in a graph$G$are called completely independent spanning trees (CISTs for short) if the paths joining every pair of vertices$x$and$y$in any two trees have neither vertex nor edge in common, except for$x$and$y$. The existence of multiple CISTs in the underlying graph of a network has applications in fault-tolerant broadcasting and secure message distribution. In this paper, we investigate the construction of CISTs in a server-centric data center network called BCube connected crossbars (BCCC), which can provide good network performance using inexpensive commodity off-the-shelf switches and commodity servers with only two network interface card (NIC) ports. The significant advantages of BCCC are its good expandability, lower communication latency, and higher robustness in component failure. Based on the structure of compound graphs of BCCC, we provide efficient algorithms to construct$\lceil \frac{n}{4}\rceil$CISTs in the logical graph of BCCC, denoted by$L$-$BCCC(n,k)$, for$n\geqslant 5$. As a by-product, we obtain a fault-tolerant routing that takes the constructed CISTs as its routing table. We then evaluate the performance of the fault-tolerant routing through simulation results.

Abstract Connectivity is a classic measure for reliability of a multiprocessor system in the case of processor failures. Extra connectivity and component connectivity are two important indicators of the reliability of a multiprocessor system in presence of failing processors. The $h$-extra connectivity $\kappa _{h}(G)$ of a graph $G$ is the minimum number of nodes whose removal will disconnect $G$, and every remaining component has at least $h+1$ nodes. Moreover, the $h$-component connectivity $c\kappa _{h}(G)$ of $G$ is the minimum number of nodes whose deletion results in a graph with at least $h$ components. However, the extra connectivity and component connectivity of many well-known networks have been independently investigated. In this paper, we determine the relationship between extra connectivity and component connectivity of general networks. As applications, the extra connectivity and component connectivity are explored for some well-known networks, including complete cubic networks, hierarchical cubic networks, generalized exchanged hypercubes, dual-cube-like networks, Cayley graphs generated by transposition trees and hierarchical hypercubes as well.

Sensing data fusion is one of the most important technologies in autonomous driving. Its performance depends on advance communication technology. Cellular-Vehicle to Everything (C-V2X) initially defined as LTE V2X in 3GPP Release 14 is a solution for vehicle communication that includes Vehicle-to-Infrastructure (V2I), Vehicle-to-person (V2P), and Vehicle-to-Vehicle (V2V). Although 4G LTE and 5G provides high-speed transmission, packet loss and delay are still inevitable. Packet loss and delay affect the safety of autonomous driving, especially for the judgment of emergency. In this paper, we compare the accuracy of data fusion under different rate of packet loss and broadcast frequency on the simulated platform CALAR. And we propose a skill to improve accuracy. Experiments show that the proposed skill significantly alleviates the effect of communication packet loss and delay on the accuracy of V2X data fusion.

For a network, edge/node-independent spanning trees (ISTs) can not only tolerate faulty edges/nodes, but also be used to distribute secure messages. As important node-symmetric variants of the hypercubes, the augmented cubes have received much attention from researchers. The n-dimensional augmented cube AQn is both (2n ‒ 1)-edge-connected and (2n ‒ 1)-nodeconnected (n ≢ 3), thus the well-known edge conjecture and node conjecture of ISTs are both interesting questions in AQn. So far, the edge conjecture on augmented cubes was proved to be true. However, the node conjecture on AQn is still open. In this paper, we further study the construction principle of the node-ISTs by using the double neighbors of every node in the higher dimension. We prove the existence of 2k − 1 node-ISTs rooted at node 0 in A Q n ( 00...0 ︸ n−k )(n≥k≥4) by proposing an ingenious way of construction and propose a corresponding O(NlogN) time algorithm, where N = 2k is the number of nodes in A Q n ( 00...0 ︸ n−k ) .

The ability of identifying all the faulty devices in a multiprocessor system is known as diagnosability. The PMC model is the test-based diagnosis with a processor performing the diagnosis by testing the neighboring processors via the links between them. In this paper, we discuss the diagnosability of a ( K 4 – { e})-free graph under the PMC model.

We propose two new measures of conditional connectivity to be the extension of R g -connectivity and R g -edge-connectivity. Let G be a connected graph. A set of vertices (edges) F is said to be a conditional ( g, d, k)(-edge)-cut of G if (1) G – F is disconnected; (2) every vertex in G – F has at least g neighbors; (3) deg G–F ( p) + deg G–F ( q) ≥ 2 g + k for every two distinct vertices p and q in G – F with d( p, q) ≤ d. The ( g, d, k)-conditional(-edge)-connectivity, denoted by κ g,d,k ( λ g,d,k ), is the minimum cardinality of a conditional ( g, d, k)(-edge)-cut. Based on these requirements, we obtain κ 1,1, k , κ 1, d,2 , λ 1,1,1 and λ 1, d,2 for the hypercubes.

The generalized hypercube (GH) is one key interconnection network with excellent topological properties. It contains many other interconnection topologies, such as the hypercube network, the complete graph, the mesh network, and the k-ary n-cube network. It can also be used to construct some data center networks, such as HyperX, BCube, FBFLY, and SWCube. However, the construction cost of GH is high since it contains too many links. In this paper, we propose a novel low cost interconnection architecture called the exchanged generalized hypercube (EGH). We study the properties of EGH, such as the number of edges, the degree of vertices, connectivity, diameter, and diagnosability. Then, we give a routing algorithm to find the shortest path between any two distinct vertices of EGH. Furthermore, we design an algorithm to give disjoint paths between any two distinct vertices of EGH. In addition, we propose two local diagnosis algorithms: LDTEGH and LDWBEGH in EGH under PMC model and MM model, respectively. Simulation results demonstrate that even if the proportion of faulty vertices in EGH is up to 25 percent, the probability that these two diagnosis algorithms can successfully determine the status of vertices is more than 90 percent. As far as the number of edges is concerned, the analysis shows that the construction cost of EGH is much less than that of GH. We could regard this work as the basis for proposing future new high performance topologies.

In the cloud computing environment with massive information services and decision-making resources, the accuracy and reliability of information are more important than previous single closed systems. Therefore, ensuring the reliability of information and the stable operation of the system are the core problems in the research fields such as the Internet Plus and the Internet of Things. The connectivity and diagnosability are two important measures for the fault tolerance of multiprocessor systems. The g -good-neighbor conditional connectivity ( Rg -connectivity) is the minimum number of nodes that make the graph disconnected, and each node has at least g neighbors in every remaining component. The g -good-neighbor conditional diagnosability ( g -GNCD) is the maximum number of faulty processors that has been correctly identified in a system, and any fault-free processor has no less than g fault-free neighbors. Exchanged X -cubes are a class of irregular networks, obtained by deleting links from hypercubes and some variant networks of hypercubes ( X -cubes). They not only combine the advantages of X -cubes but also reduce the interconnection complexity. Exchanged X -cubes classify its nodes into two different classes clusters with a unique connecting rule. In this paper, we propose the generalized exchanged X -cubes framework so that architecture can be constructed by different connecting rules. Furthermore, we study the Rg -connectivity and g -GNCD of generalized exchanged X -cubes under the PMC and MM ∗ models. As applications, the Rg -connectivity and g -GNCD of generalized exchanged hypercubes, dual-cube-like networks, generalized exchanged crossed cubes, and locally generalized exchanged twisted cubes are determined, respectively.

Fault-tolerance is an important parameter to measure the performance of a network. However, most works only consider the fault of single vertex and ignore the structure-fault of a network. The generalized hypercube G(mr,mr−1,…,m1) is one key interconnection network with excellent topological properties. In this paper, we study the H-structure fault-tolerance of G(mr,mr−1,…,m1) network by studying its H-structure connectivity and H-substructure connectivity for H∈{K1,M,C3,C4,K4}⁠. Since the generalized hypercube network can be used to construct some data center networks, such as BCube, HyperX, and FBFLY, the results in this paper can be applied not only to interconnection networks but also to data center networks.

With the rapid development of cloud computing, many large-scale data centers are being built to provide increasingly popular online application services. This leads to the proposal of data center networks (DCNs) supporting millions of servers with high-network capacity by using only commodity switches. The k-dimensional DCell with n-port switches and tk,n servers, Dk,n⁠, has been proposed as a model for a large-scale DCN with a server-centric structure. In this paper, we study the diagnosability and the g-good-neighbor conditional diagnosability of Dk,n⁠. We prove that: (i) Dk,n is (n+k−1)-diagnosable under the precise diagnosis strategy and (2k+n−2)/(2k+n−2)- diagnosable under the pessimistic diagnosis strategy; (ii) the g-good-neighbor conditional diagnosabilities of Dk,n under the PMC model and the MM* model are both (g+1)k+n−1 (resp. (n+k−g)tg−n+1,n−1) with 0≤g≤n−1 (resp. n≤g≤n+k−2⁠), which is almost (g+1) (resp. tg−n+1,n⁠) times of the traditional diagnosability. These results provide a quantitative evaluation for a large-scale DCN’s reliability and availability.

In wireless sensor networks (WSNs), the sensing data of nodes have spatial similarity, so the network fault diagnosis can be done by comparing the data of neighbor nodes. When sending data, the node may send erroneous data because of the interference of the signal, thereby affecting the diagnostic accuracy of the network. This paper presents a parallel and local diagnostic algorithm (PLD) for WSN. In order to avoid the problem of signal collision, this paper constructs a special diagnosis structure, which effectively avoids the influence of signal collision on node diagnosis. The algorithm can be divided into three parts: generate the candidate sub-node set, establish the fault diagnosis structure and the diagnostic test. Diagnostic test contains four rounds. The first three rounds quickly compare perceived data of adjacent nodes in parallel, greatly reduces the time of diagnosis. In the fourth round, the most reliable node is tested with the first three rounds. Simulation results show that the proposed algorithm can guarantee higher diagnostic accuracy.

The k-ary n-cube is one of the most attractive interconnection networks for parallel and distributed computing systems. In this paper, we investigate hamiltonian cycle and path embeddings in k-ary n-cubes Qnk based on structure faults, which means each faulty element is isomorphic to any connected subgraph of a connected graph. Let H be a connected graph with H∈{K1,K1,1,K1,2,K1,3}⁠. We show that for two arbitrary distinct healthy nodes of a faulty Qnk⁠, there exists a fault-free hamiltonian path connecting these two nodes if the number of faulty element is at most a certain number and each faulty element is isomorphic to a connected subgraph of H. We also show that there exists a fault-free hamiltonian cycle if the number of faulty element is at most a certain number and each faulty element is isomorphic to a connected subgraph of H. These results mean that the k-ary n-cube Qnk can tolerate up to 4(n−2) faulty nodes such that Qnk−V(F) is still hamiltonian and hamiltonian-connected, where F denotes the faulty set of Qnk⁠.

Target traversing has been an important research topic in wireless sensor networks. Most works in this area consider the coverage issues of the target's moving paths. The support path is to find a path among sensors so that the target's support from the sensors is minimized, where support of the target from a sensor is defined as the inversely proportional to the distance of the target from the sensor. Most existing algorithms ensure the target to stay as close as possible from sensors or deploy sensors to enhance the coverage to the target. In this paper, we take into account the situation where the target must trave the sensor networks within time constraint. We propose some algorithms for the target to not only stay as close as possible from sensors, but also traverse the sensing field within time constraint. Simulations show that the proposed algorithms can solve the traversal path in wireless sensor networks.

The complete binary tree is an important network structure for parallel and distributed computing, which has many nice properties and is often used to be embedded into other interconnection architectures. The locally twisted cube LTQn is an important variant of the hypercube Qn. It has many better properties than Qn with the same number of edges and vertices. In this paper, we prove that the complete binary tree CBTn can be embedded with dilation 2 and congestion 1 into LTQn. Furthermore, it is proven that if there exists an arbitrary faulty node in LTQn, then both the dilation and congestion values will become 2 after reconfiguring CBTn, while if there are two arbitrary faulty nodes in LTQn, then both the dilation and congestion values will become 3 after reconfiguration.

Smart devices have become essential in modern world. Nowadays, people conduct various social activities on smart devices, such as exchanging name cards, slides, or files. Traditionally, it would require URLs or flash drives to achieve this goal. However, these conventional means lack intuitive physical interaction and are sometimes hard to perform on smart devices, especially when people wish to interact with a target of physical meanings, e.g., “the man sitting on the opposite side of the table”. This paper proposes to integrate file sharing with localization of the target devices. A device-to-device (D2D) relative positioning method is introduced. The basic idea is to combine the orientations of devices with an acoustic ranging mechanism to determine their relative locations. The result allows users to drag files instinctively on their screens to destined receivers, and then release to initiate the file sharing in a network group. A prototype system is developed to verify the feasibility of our approach.

In microprocessor-based systems, such as the cloud computing infrastructure, high reliability is essential. As multiprocessor systems become more widespread and increasingly complex, system-level diagnosis will increasingly be adopted to determine their robustness. In this paper, we consider a pessimistic diagnostic strategy for hypermesh multiprocessor systems under the PMC model. The pessimistic strategy is a diagnostic process whereby all faulty processors are correctly identified and at most one fault-free processor may be misjudged to be a faulty processor. We first determine the pessimistic diagnosability of a hypermesh to be${2}{{n}}({{k}} - {1}) - {{k}}$. We then propose an efficient pessimistic diagnostic algorithm to identify at most${ 2}{{n}}({{k}} - { 1}) - {{k}}$faults in${{O}}({{N}})$time, where${\mbi{k}}$is the radix,${\mbi{n}}$is the number of dimensions, and${{N}} = {{k^n}}$is the total number of processors. This result is superior to the best precise diagnostic algorithm, which runs in${{O}}({{N}}{\log _{{k}}}{{N}})$time. Furthermore, the Cartesian product network, a subgraph of the hypermesh and the proposed algorithm can be employed to determine faults in the product network.

Addressing in wireless sensor networks is to assign each newly-joining device a unique address. However, to allot the naming space in a large-scale distributed wireless sensor network is not an easy task. ZigBee is a popular communication standard for wireless sensor networks. It suggests a distributed address assignment mechanism. A parent device can calculate network addresses for its child devices without communicating with other devices. However, the parameter configuration of this mechanism strictly restricts the number of children of a device and the depth of the network. ZigBee does not recommend suitable parameters. The improper parameter configuration usually makes many devices isolated from the network which become orphan devices. In this paper, we propose two automatic parameter selection schemes for ZigBee address assignment scheme by probing the network and then selecting parameters in advance to alleviate the orphan problem. They can automatically suggest proper parameters for different network topologies and thus help the original ZigBee address assignment mechanism to effectively reduce orphans.

System-level diagnosis is a crucial subject for maintaining the reliability of multiprocessor interconnected systems. Consider a system composed of N independent processors, each of which tests a subset of the others. Under the PMC diagnosis model, Dahbura and Masson proposed an O(N2.5) algorithm to identify the set of faulty processors in a t-diagnosable system, in which at most t processors are permanently faulty. In this paper, we establish some sufficient conditions so that a t-regular system can be conditionally (2t-1)-diagnosable, provided every fault-free processor has at least one fault-free neighbor. Because any t-regular system is no more than t-diagnosable, the approached diagnostic capability is nearly double the classical one-step diagnosability. Furthermore, a correct and complete method is given which exploits these conditions and the presented branch-of-tree architecture to determine the fault status of any single processor. The proposed method has time complexity O(t2), and thus can diagnose the whole system in time O(t2N). In short, not only could the diagnostic capability be proved theoretically, but also it is feasible from an algorithmic perspective.

An efficient diagnosis is very important for a multiprocessor system. The ability to identify all the faulty devices in a multiprocessor system is known as diagnosability. In the comparison model, the diagnosis is performed by sending two identical signals from a processor to a pair of distinct neighbors, and then comparing their responses. Sengupta and Dahbura proposed a polynomial-time algorithm with time complexity O(N5) to diagnose a system with a total number N of processors under the comparison model. Recently, some concepts, such as the conditional diagnosability and the local diagnosability, are concerned with the measure which is able to better reflect fault patterns in real systems. In this paper, we propose a specific structure, the balanced wind-bell-tree, and give an algorithm to determine the fault status of each processor for conditional local diagnosis under the comparison model. According to our results, a specific t-connected network with the balanced wind-bell-tree structure is conditionally (2t-1)°-diagnosable, and the time complexity to diagnose all the faulty processors is O(N(logN)2) with our algorithm, where N is the total number of the processors in the network.

Diagnosis is an essential subject for the reliability of multiprocessor systems. Under the PMC diagnosis model, Dahbura and Masson [12] proposed a polynomial-time algorithm with time complexity O(N^{2.5}) to identify all the faulty processors in a system with N processors. In this paper, we present a novel method to diagnose a conditionally faulty system by applying the concept behind the local diagnosis, introduced by Somani and Agarwal [30], and formalized by Hsu and Tan [18]. The goal of local diagnosis is to identify the fault status of any single processor correctly. Under the PMC diagnosis model, we give a sufficient condition to estimate the local diagnosability of a given processor. Furthermore, we propose a helpful structure, called the augmenting star, to efficiently determine the fault status of each processor. For an N-processor system in which every processor has an O(\log N) degree, the time complexity of our algorithm to diagnose any given processor is O((\log N)^2), provided that each processor can construct an augmenting star structure of full order in time O((\log N)^2) and the time for a processor to test another one is constant. Therefore, the time totals to O(N(\log N)^2) for diagnosing the whole system.

Abstract Letuandvbe any two distinct nodes of an undirected graphG, which isk‐connected. A containerC(u,v) betweenuandvis a set of internally disjoint paths {P1,P2,…,Pw} betweenuandvwhere 1 ≤w≤k. The width ofC(u,v) iswand the length ofC(u,v) {written aslC(u,v) is max {l(Pi) ∣ 1 ≤i≤w}. Aw‐containerC(u,v) is a container with widthw. Thew‐wide distance betweenuandv,dw(u,v), is min {l(C(u,v)) ∣C(u,v) is aw‐container}. Aw‐containerC(u,v) of the graphGis aw*‐container if every node ofGis incident with a path inC(u,v). That means that thew‐containerC(u,v) spans the whole graph. LetSnbe then‐dimensional star graph withn≥ 5. It is known thatSnis bipartite. In this article, we show that, for any pair of distinct nodesuandvin different partite sets ofSn, there exists an (n− 1)*‐containerC(u,v) and the (n− 1)‐wide distanced(n− 1)(u,v) is less than or equal to${n!\over n-2}+1$ . In addition, we also show the existence of a 2*‐containerC(u,v) and the 2‐wide distanced2(u,v) is bounded above by${n!\over 2}+1$ . © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(4), 235–249 2006

Two hamiltonian paths P1 = 〈u1, u2,…,un(G)〉 and P2 = 〈v1, v2,…,vn(G)〉 of G from u to v are independent if u = u1 = v1, v = vn(G) = un(G), and vi ≠ ui for every 1 < i < n(G). A set of hamiltonian paths, lP1, P2,…,Pkr, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. A bipartite graph G is hamiltonian laceable if there exists a hamiltonian path joining any two nodes from different partite sets. A bipartite graph is k-mutually independent hamiltonian laceable if there exists k-mutually independent hamiltonian paths between any two nodes from distinct partite sets. The mutually independent hamiltonian laceability of a bipartite graph G, IHPL(G), is the maximum integer k such that G is k-mutually independent hamiltonian laceable. Let Sn denote the n-dimensional star graph. We prove that IHPL(S2) = 1, IHPL(S3) = 0, and IHPL(Sn) = n- 2 if n ≥ 4. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(2), 110–117 2005