The explosive growth of multimodal web data demands communication that transmits meaning rather than raw bits. Existing semantic-communication systems often fail under noise, missing modalities, and distribution shifts because they optimize surface features instead of modality-invariant knowledge. We present Grasp, a knowledge-centric framework for cross-modal communication. Grasp segments streams into semantic blocks and builds a graph over them; a lightweight Graph Neural Networks (GNN) produces schedulable, importance-weighted representations. At its core is knowledge purification : we minimize a conditional mutual information upper bound to perform a three-way disentanglement—strongly related, weakly related, and task-irrelevant components—so that only essential semantics are transmitted while non-essential factors are suppressed. To maintain synchrony, we introduce one-to-two temporal contrastive learning to achieve triple alignment of video, audio, and text despite sampling asynchrony. For efficient transmission, Grasp uses a cross-modal shared vector-quantization codebook—a discrete knowledge codebook —updated by multimodal attention. At the receiver, a soft-recovery mechanism leverages this shared knowledge to robustly reconstruct semantics under low signal-to-noise ratio (SNR) or missing modalities, yielding graceful degradation. Across web tasks—including cross-modal retrieval and missing-modality inference—Grasp improves knowledge consistency, semantic fidelity, and downstream performance over strong baselines while maintaining low latency. These results show that communication structured around purified knowledge is key to building robust, semantic-aware systems for the modern web.

The traditional, well-known system-level fault diagnosis is to precisely identify faulty nodes in a network via mutual testing between the nodes, and thediagnosabilityis the maximum allowed number of faulty nodes for correct diagnosis.This paper proposes a new scheme that focuses on detecting whether a given critical substructure (e.g., a specific cycle or path) contains any faulty node. If the detecting outcome is “Yes”, the entire substructure is deemed as faulty, regardless of how many faulty nodes, and where they are in the substructure. This approach is often more cost-effective and technically feasible than pinpointing every faulty node. We name the maximum allowed number of faulty nodes for this strategy to work as theDetectabilityof the network, as opposed to the diagnosability.We study the detectability for the hypercube$Qn$, under the PMC model. We will show that in$Qn$(n ≥ 7), the detectability is2n − 1for the minimal bipartite subgraphK1,1, and4n − 5for the 4-node cycleC4. Notably, detectability consistently exceeds traditional diagnosability, tolerating more faulty nodes. We have also designed, validated, and implemented detection algorithms ofO(n·2n−1)complexity to detect faultyK1,1andC4inQn. Simulations show a 100% detection rate, with effectiveness maintained even in lower-dimensionalQnwhere theoretical assumptions do not fully hold.

Data center DCell networks are particularly well-suited for large, reliability-critical data centers due to their scalability, fault tolerance, and efficient bandwidth utilization. The reliability and diagnosis of DCell networks are of paramount importance in ensuring smooth operation and continuous availability of data center services. Traditional fault diagnosis models, which focus on global fault detection, are more suited to simpler networks. In contrast, complex DCell networks require fault diagnosis under specific conditions to accommodate dynamic changes and constraints. This paper studies the cyclic diagnosability of DCell networks under different system-level diagnostic models, which is a novel fault diagnosis strategy. Cyclic diagnosability, denoted as$ct_{c}(G)$, represents the maximum size of a set of fault vertices$D$in a network$G$, so that the self-diagnosis system can identify all vertices in$D$under the condition that at least two connected components of$G-D$contain a cycle. We show that for$k$-dimensional DCell with$n$-port switches$DCell_{k,n}$, when$k \geq 2$,$3 \leq n \leq 5$, or$k \geq \frac {n}{2} + 1$,$n \geq 6$, the cyclic diagnosability is$4k+2n-5$under the PMC and MM* models based on the indistinguishability of the constructed set and the linear multiple fault analysis technology. Additionally, we propose two practical cyclic fault diagnosis algorithms with low time complexity: PMC-Based Cyclic Fault Diagnosis (PMCCFD) and MM*-Based Cyclic Fault Diagnosis (MMCFD) for the PMC and MM* models to improve fault detection and recovery in large-scale DCell networks. We also implement the PMCCFD and MMCFD algorithms on both synthetic and real data. Furthermore, we verify the availability/efficiency of algorithms PMCCFD and MMCFD in terms of accuracy rate, recall, false negative rate, negative predictive value, and F1Score.

As the core infrastructures in the information systems, the data center networks carry a large number of tasks of data processing and storage. In a data center network, intermittent faults are often difficult to be found and dealt with in time because of their hiddenness and uncertainty. Once these faults accumulate to a certain extent, they can cause serious network outages and even lead to the collapse of the entire data center. In order to discover and resolve these potential problems in a timely manner, it is crucial to apply intermittent fault diagnosis, thus ensures the continuous and stable operation of the data center. In this paper, we propose the intermittent fault diagnosabilitytPMCI(Cn) for ann-dimensional data center network CSDC under the Preparata/Metze/Chien model (PMC model) by establishing the fault tolerance of the network. Additionally, under the PMC model, we propose a probabilistic multiple intermittent fault diagnosis algorithm (PMIFDPMC) with time complexityO(nN) by preferentially generating weighted multiple test networks (GWMTN) whereNis the scale of CSDC. Moreover, we apply the algorithm PMIFDPMC to a 7-dimensional CSDC and a real-world dataset of the Internet of Things. Across different scenarios of intermittent fault nodes, we calculate the Accuracy, Recall, FNR, G-mean, and F1-score using various testing iterations. The experimental results demonstrate that, as the number of testing iterations of algorithm PMIFDPMC increases, the quantity of intermittent fault nodes that are correctly diagnosed also increases. This highlights the favorable performance and effectiveness of algorithm PMIFDPMC on the real-world dataset of the Internet of Things.

With the scale of multiprocessor systems constantly increasing, the large number of interconnected processors (or nodes) makes faulty nodes inevitable. The fault diagnosis of multiprocessor systems therefore is a key technique for the system’s robustness. In this paper, we first propose a novel diagnostic metric, the$h$-extra$r$-component diagnosability, denoted$ECD^{h}_{r}(G)$, which characterizes one special pattern of faults. We derive some theoretical results for the ECD of hypercube, denoted$ECD^{h}_{r}(Q_{n})$, under the PMC model. Diagnostic algorithms is proposed and implemented to detect faulty nodes that will disconnect hypercube$Q_{n}$into$r$components each containing at least$h+1$nodes. We also test the ECD-PMC algorithm to the hypercube network with different number of faulty processors satisfying the$h$-extra$r$-component condition. Extensive simulation results show that our proposed method achieves very good performance in terms of ACCR, TPR, FPR, and TNR.

A network can contain numerous spanning trees. If two spanning trees T i , T j do not share any common edges, T i and T j are said to be pairwisely edge-disjoint. For spanning trees T 1 , T 2 ,…, T m , if every two of them are pairwisely edge-disjoint, they are called completely edge-independent spanning trees (CEISTs for short). CEISTs can facilitate many network functionalities, and constructing CEISTs as maximally allowed as possible in a given network is a worthy undertaking. In this paper, we establish the maximal number of CEISTs in the locally twisted cube network, and propose an algorithm to construct ⌊ n 2 ⌋ CEISTs in LTQ n , the n -dimensional locally twisted cube. The proposed algorithm has been actually implemented, and we present the outputs. Network broadcasting in the LTQ n was simulated using ⌊ n 2 ⌋ CEISTs, and the performance compared with broadcasting using a single tree.

The robustness of subnetworks for the interconnection network of a computer system is an important consideration for the system performance. It can be measured by the extent to which subnetworks can stay fault-free when faults are present in the system. In this paper, we evaluate the subnetwork robustness for then-dimensional split-star network$S_{n}^{2}$. Let$S_{n-m}^{2}, 1 \leq m \leq n-3$, be a subnetwork of$S_{n}^{2}$, and letpbe the node reliability, the probability that a single node remains fault-free. We determine two values that reflect how robust$S_{n-m}^{2}$subnetworks are, from two perspectives. We first establish the upper/lower bounds for$\mathcal{F}_{m} (S_{n}^{2})$, the minimum number of faulty nodes to make all$S_{n-m}^{2}$subnetworks faulty. Then, we determine the subnetwork reliability, denoted by$\mathcal{R}_{m} (S_{n}^{2}, p)$, which is the probability that at least one fault-free$S_{n-m}^{2}$subnetwork exists in$S_{n}^{2}$, given the node reliabilityp. The upper/lower bounds and an approximation expression for$\mathcal{R}_{m} (S_{n}^{2}, p)$are obtained. We also propose a simulation method to estimate$\mathcal{R}_{m} (S_{n}^{2}, p)$. The experimental results show that a) whenpis relatively low,$\mathcal{R}_{m} (S_{n}^{2}, p)$can be approximated by the mean value of its upper and lower bounds, or the estimation value by the approximation expression; b) whenpis high,$\mathcal{R}_{m} (S_{n}^{2}, p)$can be more accurately estimated by our simulation method.

With the growing role of multiprocessor systems in big data, artificial intelligence, as well as cloud computing and high-performance computing, the expansion in system scale and complexity has inevitably led to an increase in processor failures (or faults). To enhance the system’s fault diagnosis capability, a novel approach termed$t/s$-diagnosis has been proposed timely. In this article, we delve into the relationship between a general network’s component connectivity and$t/s$-diagnosability under the MM* diagnostic model, and subsequently apply the metric to a variety of networks, including bubble sort graphs, complete cubic networks, hierarchical hypercubes, and generalized exchanged hypercubes. To detect all faulty nodes, we propose the largest connected component under MM* model (LCC-MM*) algorithm along with the analysis of time complexity. In addition, we evaluate the$t/s$-diagnosability of a variety of networks, accompanied by contrasting$t/s$-diagnosability with other conditional diagnosabilities under the MM* diagnostic model. Meanwhile, we conduct experiments on real data to assess the effectiveness and performance of the LCC-MM* algorithm.

The$k$-ary$n$-cube$Q_{n}^{k}$is one of the most important interconnection networks for building network-on-chips, data center networks, and parallel computing systems owing to its desirable properties. Since edge faults grow rapidly and the path structure plays a vital role in large-scale networks for parallel computing, fault-tolerant path embedding and its related problems have attracted extensive attention in the literature. However, the existing path embedding approaches usually only focus on the theoretical proofs and produce an$n$-related linear fault tolerance since they are based on the traditional fault model, which allows all faults to be adjacent to the same node. In this paper, we design an efficient fault-tolerant Hamiltonian path embedding algorithm for enhancing the fault-tolerant capacity of$k$-ary$n$-cubes. To facilitate the algorithm, we first introduce a new conditional fault model, named Partitioned Edge Fault model (PEF model). Based on this model, for the$k$-ary$n$-cube$Q_{n}^{k}$with$n\geq 2$and odd$k\geq 3$, we explore the existence of a Hamiltonian path in$Q_{n}^{k}$with large-scale edge faults. Then we give an$O(N)$algorithm, named HP-PEF, to embed the Hamiltonian path into$Q_{n}^{k}$under the PEF model, where$N$is the number of nodes in$Q_{n}^{k}$. The performance analysis of HP-PEF shows the average path length of adjacent node pairs in the Hamiltonian path constructed by HP-PEF. We also make comparisons to show that our result of edge fault tolerance has exponentially improved other known results. We further experimentally show that HP-PEF can support the dynamic degradation of average success rate of constructing Hamiltonian paths when increasing faulty edges exceed the fault tolerance.

The past decade has seen growing importance being attached to theCompletely Independent Spanning Trees(CISTs). The CISTs can facilitate many network functionalities, and the existence and construction schemes of CISTs in various networks can be an indicator of the network's robustness. In this paper, we establish the number of CISTs that can be constructed in theline graphof the complete graph$K_n$(denoted$L(K_n)$, for$n\geq 4$), and present an algorithm to construct the optimal (i.e., maximal) number of CISTs in$L(K_n)$. The$L(K_n)$is a special class of SWCube [13], an architectural model proposed for data center networks. Our construction algorithm is also implemented to verify its validity.

The attackers in a network may have a tendency of targeting on a group of clustered nodes, and they hope to avoid the existence of significant large communication groups in the remaining network, such as botnet attack, DDoS attack, and Local Area Network Denial attack. Current various kinds of connectivity do not well reflect the fault tolerance of a network under these attacks. This observation inspires a new measure for network reliability to resist the block attack by taking into account of the dispersity of the remaining nodes. Let$G$be a network,$C\subset V(G)$and$G[C]$be aconnected subgraph. Then$C$is called an$h$h-faulty-blockof$G$if$G-C$is disconnected, and every component of$G-C$has at least$h+1$nodes. The minimum cardinality over all$h$-faulty-blocks of$G$is called$h$h-faulty-block connectivityof$G$, denoted by${FB}\kappa _h(G)$. In this article, we determine${FB}\kappa _h(Q_n)$for$n$-dimensional hypercube$Q_n$($n\geq 4$), a classic interconnection network. We establish that${FB}\kappa _h(Q_n)=(h+2)n-3h-1$for$0\leq h\leq 1$, and${FB}\kappa _h(Q_n)=(h+2)n-4h+1$for$2\leq h\leq n-2$, respectively. Larger$h$-faulty-block connectivity implies that an attacker will have to stage an attack to a bigger block of connected nodes, so that each remaining components will not be too small, which will in turn limit the size of large components. In other words, there will not be great disparity in sizes between any two remaining components, and hence there will less likely be a significantly large remaining communication group. The larger the$h$-faulty-block, the more difficult for an attacker to achieve that goal. As a consequence, the resistance of the network against the attacker will increase. Our experiments also show that as$h$increases, the$h$-faulty-block gets larger, and the size disparity between any two remaining components decreases. In turn, as expected, the size of the largest remaining communication group becomes smaller.

A set of spanning trees T1; T2;. .. ; Tk in a network G are Completely Independent Spanning Trees (CISTs) if for any two nodes u and v in V (G), the paths between u and v in any two trees have no common edges and no common internal nodes. CISTs have important applications in data center networks, such as fault-tolerant multi-node broadcasting, fault-tolerant one-to-all broadcasting, reliable broadcasting, secure message distribution, and so on. The augmented cube AQn is a prominent variant of the well-known hypercube Qn, and having the important property of scalability, and both Qn and AQn have been proposed as the underlying structure for a data center network. The data center network based on AQn is denoted by AQDNn, and the logic graph of AQDNn is denoted by L-AQDNn. In this article, we study how to construct n - 1 CISTs in L-AQDNn. The constructed n - 1 CISTs are optimal in the sense that n - 1 is the maximally allowed CISTs in L-AQDNn. The correctness of our construction algorithm is proved. It is the first time a direct relationship is established between the dimension of a hypercube-family network and the number of CISTs it can host.

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.

The h-extra node-connectivity of a graph G is the size of a minimal node-set, whose removal will disconnect G, but each remaining component has no fewer h + 1 nodes. Based on h-extra node-connectivity, the h-extra conditional fault-diagnosability of networks has been proposed for a better, more realistic measure of networks' fault-tolerability. It is the maximal x such that G is h-extra conditionally x-fault-diagnosable. This paper will establish a relationship between the h-extra node-connectivity and h-extra conditional fault-diagnosability for a regular graph G, under the classic PMC diagnostic model. We will apply the newly found relationship to a variety of well-known regular networks, to directly obtain their h-extra conditional fault-diagnosability. The significance of the paper's work is that it relates the notions of h-extra node-connectivity and h-extra conditional fault-diagnosability, so that a regular network's h-extra conditional fault-diagnosability may be known once its h-extra node-connectivity is known.

A network's diagnosability is the maximum number of faulty vertices the network can discriminate solely by performing mutual tests among the vertices. It is an important measure of a network's robustness. The original diagnosability without any condition is often rather low because it is bounded by the network's minimum degree. Several conditional diagnosability have been proposed in the past to increase the allowed faulty vertices, and hence enhancing the diagnosability of the network. The g-good-neighbor conditional diagnosability is the maximum number of faulty vertices a network can guarantee to identify, under the condition that every fault-free vertex has at least g fault-free neighbors (i.e., good neighbors). In this paper, we establish the g-good-neighbor conditional diagnosability for the (n; k)-arrangement graph network An;k. We will show that, under both the PMC model and the comparison model, the An;k's g-good-neighbor conditional diagnosability is [(g + 1)k - g](n - k), which can be several times higher than the An;k's original diagnosability.

As the size and complexity of a multiprocessor system increases, reliability evaluation becomes an important issue. The performability of a multiprocessor system heavily depends on the application program and the underlying architecture. In multitasking multiprocessor system, the problem of dynamically assigning a given dimensional subsystem to a special task is considered as a reallocation in the presence of node and/or link failures. This paper takes the generalization of star graph, (n, k)-star graph, as an empirical object. In order to measure the reliability of (n, k)star graph, the analytical model introduces mean time to failure (MTTF) to show the time that the appearance of a certain number of faulty Sn-1,k-1costs. The higher the MTTF, the better the robustness. So, the way to evaluate the robustness of an (n, k)-star is to count how much the MTTF is. In fact, an (n, k)-star can be partitioned along any dimension (except the first one) with corresponding identification code. So, we will explore the reliability of (n, k)-star graph when it is partitioned along any dimension (except the first one) under node and/or link fault model. Comparisons among the simulation results under two partitioning models reveal that the MTTF is higher under liberal partition model, which better reflect the steady state of an interconnection network that can persist when the network is destroyed.

As the cardinality of multiprocessor systems grows, the probability of arising malfunctioning or failing processors in the system is bound to increase. It is then of both practical and theoretical importance to know the reliability of the system as a whole. One metric for a system's overall reliability is the measurement of the collective effect of its subsystems becoming faulty. However, a challenge of this approach is that the subsystems often interact with each other in a complex manner, making the analysis difficult. Wu and Latifi (Int. Sci., vol. 178, pp. 2337-2348, Oct. 2008) proposed two schemes to evaluate the system reliability of the Star graph network under a probabilistic fault model. The first scheme computes the combinatorial probability of subgraphs to obtain an upper-bound on the reliability by considering the intersection of no more than three subgraphs. The second scheme computes an approximate combinatorial probability by completely neglecting the intersection among subgraphs. Recently, Lin et al. have applied this approach to investigate the reliability of the multiprocessor system based on the arrangement graph (IEEE Trans. Rel., vol. 62, no. 2, pp. 807-818, Jun. 2015). In this paper, we extend the above approach by computing both upper- and lower-bounds and considering the difference of the two, to establish the reliability of the (n, k) -Star graph, another extensively studied interconnection network for multiprocessor systems. More specifically, we compute a lower-bound and an upper-bound on the reliability by taking into account the intersection of no more than four or three subgraphs, respectively. The empirical study shows that the upper- and lower-bounds are both very close to the approximate results. Especially, the lower the single-node reliability goes, the closer the approximate reliability is to both lower- and upper-bounds.

Reliable broadcasting for a network can be obtained by using completely independent spanning trees(CISTs). Locally twisted cubes are popular networks which have been studied widely in the literature. In this paper, we study the problem of using CISTs to establish reliable broadcasting in locally twisted cubes. We first propose an algorithm, named LTQCIST, to construct two CISTs in locally twisted cubes, then exemplify the construction procedures to construct CISTs. Finally, we prove the correctness of Algorithm LTQCIST and simulate CISTs with JUNG.

The${{t/k}}$-diagnosis is a diagnostic strategy at system level that can significantly enhance the system’s self-diagnosing capability. It can detect up to${{t}}$faulty processors (or nodes, units) which might include at most${{k}}$misdiagnosed processors, where${ {k}}$is typically a small number. Somani and Peleg (, 1996) claimed that an$n$-dimensional Star Graph (denoted${{S_n}}$), a well-studied interconnection model for multiprocessor systems, is${{((k + 1)n - 3k - 2)/k}}$-diagnosable. Recently, Chen and Liu (, 2012) found counterexamples for the diagnosability obtained in, without further pursuing the cause of the flawed result. In this paper, we provide a new, complete proof that an${\mbi {n}}$-dimensional Star Graph is actually${{((k + 1)n - 3k - 1)/k}}$-diagnosable, where${{1 \leq k \leq 3}}$, and investigate the reason that caused the flawed result in. Based on our newly obtained fault-tolerance properties, we will also outline an${ {O(N \log N)}}$diagnostic algorithm (${ {N = n!}}$is the number of nodes in${{S_n}}$) to locate all (up to${ {(k + 1)n - 3k - 1}}$) faulty processors, among which at most${ {k\, (1 \leq k \leq 3)}}$fault-free processors might be wrongly diagnosed as faulty.

Extra connectivity, diagnosability, and conditional diagnosability are all important measures for a multiprocessor system's ability to diagnose and tolerate faults. In this paper, we analyze the fault tolerance ability for the alternating group graph, a well-known interconnection network proposed for multiprocessor systems, establish the h-extra connectivity, where 1 ≤ h ≤ 3, and prove that the conditional diagnosability of an n-dimensional alternating group graph, denoted by AGn, is 8n - 27 (n ≥ 4) under the PMC model. This is about four times of the AGn's traditional diagnosability. As a byproduct, the strong diagnosability of AGnis also obtained.

As the size of a multiprocessor computer system grows, the probability of having faulty (i.e., malfunctioning or failing) processors in the system increases. It is then important to quantify how the faults collectively affect the entire system. The reliability of subsystems in a system, defined as the probability that a fault-free subsystem of a certain size still exists when the system has faults, is a measure for the faults' effect on the whole system. It can be used as an indicator of system health. In this paper, we will present two schemes to calculate the reliability of an$(n-1,k-1)$-subgraph in the$(n,k)$-Arrangement Graph$A_{n,k}$, an extensively studied interconnection network proposed for multiprocessor computers. The first scheme will use a probability fault model and the Principle of Inclusion-Exclusion to establish an upper-bound of the reliability, by taking into account the intersection of not more than three subgraphs. The second scheme uses basically the same idea, but completely neglects the intersection among subgraphs to calculate an approximate reliability. The results of the two schemes are compared, and are shown to be in good agreement, especially as the single-node reliability$p$goes low.

Obtaining spectrum information efficiently is key to cognitive radio networks (CRNs). The database-driven approach has emerged recently as an alternative or supplement for spectrum sensing, and has been quickly adopted by the government and the industry. Within database-driven CRNs, master devices obtain spectrum information by direct connection to a spectrum database, while slave devices can only access spectrum information indirectly via masters. Out-of-band connections with a second network interface which do not depend on the primary spectrum channels can be used for the communication of spectrum information among masters and slaves. Alternatively, the in-band approach completely based on primary spectrum channels can be used, which eliminates the need for out-of-band connections and eases the adoption of the database-driven spectrum sharing. In this paper, we study the in-band bootstrapping process for database-driven multi-hop CRNs, where master/slave devices form a multi-hop networks and slaves need multi-hop communications to obtain spectrum information from the master during bootstrapping. We propose several protocols to reduce the bootstrapping time and protocol overhead. According to the analysis and simulation results, our proposed protocols can greatly improve the performance.

In this paper, state dependent relay channel (SD- RC) with causal channel state information (CSI) is considered. Two different cases are investigated in which causal CSI is available: 1) only at the relay node, 2) at all the nodes. The second situation is specialized to cases where causal CSI is known: at both source and relay; at both destination and relay. We established the lower bounds for these situations. Our bound contains all the bounds in previous work, and it is strictly better under some cases. In our scheme, the CSI at relay is compressed by Wyner-Ziv compression and transmitted with the message information by exploiting Shannon strategy. The transmission of CSI has twofold effect. On the one hand, it may reduce the message rate to be relayed. On the other hand, the destination can use the received CSI to help decode message from both the source and relay. Note that if the channel between the relay and destination is good enough, the relay can transmit all the message information it got and use the extra capacity to transmit compressed CSI. In this situation the transmission of CSI doesn't reduce the message rate to be relayed, and our scheme is better than compress- forward (CF) relaying with Shannon strategy.

We investigate the problem of carrier frequency offset (CFO) estimation for orthogonal frequency division multiplexing (OFDM) systems. An approximated method for CFO estimation is derived. We show that the introduction of CFO can be taken as the result of passing through a frequency domain filter, whose coefficients are functions of CFO. To estimate the CFO, we construct an estimator based on the filter coefficients. In this way, the CFO estimation problem is converted to filter coefficients estimation. We also develop a fast algorithm with lower computational complexity. We show our method is effective for channel with large Doppler spread.

In this paper we consider relay channel (RC) with non-causal channel state information (CSI) only at the relay. Three compress-forward (CF) lower bounds were established. The first one is obtained by letting the relay transmit compressed CSI and message information directly. The second bound is a special case of the first one, which is achieved by letting the relay only transmit CSI regardless of message. It is equivalent to the first one under some cases. To achieve the third bound we introduce a new coding scheme, which makes more use of the non-causal CSI. The third bound contains all previous bounds. In our scheme, the non-causal CSI is compressed and transmitted with message information. The transmission of CSI has twofold effect. On the one hand, it may reduce the message rate sent by the relay. On the other hand, the destination can decode the CSI and use it to improve decoding message from both the source and the relay. We find that our scheme is equivalent to CF strategy with Gelfand-Pinsker (GP) coding, in which the non-causal CSI is only used to improve decoding the message from the relay. Note that if the channel between the relay and destination is good enough, the relay can transmit all the message information it got and use the extra capacity to transmit compressed CSI. In this situation the transmission of CSI doesn't reduce the message rate to be relayed, and our scheme outperforms CF strategy with GP coding.

An interconnection network’s diagnosability is an important measure of its self-diagnostic capability. Based on the classical notion of diagnosability, strong diagnosability and conditional diagnosability were proposed later to better reflect the networks’ self-diagnostic capability under more realistic assumptions. In this paper, we study a class of interconnection networks called strong networks, which are$n$-regular,$(n - 1)$-connected, and with$cn$-number no more than$n - 3$. We build a relationship among the three diagnosability measures for strong networks. Under both PMC and${\rm MM}^{\ast}$models, given a strong network$G$with diagnosability$t$, we prove that$G$is strongly$t$-diagnosable if and only if$G$’s conditional diagnosability is greater than$t$. A simple check can show that almost all well-known regular interconnection networks are strong networks. The significance of this paper’s result is that it reveals an important relationship between strong and conditional diagnosabilities, and the proof of strong diagnosability for many interconnection networks under${\rm MM}^{\ast}$or PMC model is not necessary if their conditional diagnosability can be shown to be strictly larger than their diagnosability.

Abstract We present an algorithm that constructs subnetworks from an n‐dimensional crossed cube, denoted CQn, so that for any given κ, 2 ≤ κ ≤ n − 1, the algorithm can generate a κ‐connected subnetwork that contains all 2n original nodes of CQn and preserves the symmetrical structure. The κ‐connected subnetworks constructed are all optimal in the sense that they use the minimum number of links to maintain the required connectivity. Being able to construct κ‐connected, all‐node subnetworks are important in many applications, such as computing in the presence of faulty links, or diagnosing the system with a lower fault bound. Links that are not used by the induced subnetworks could be used in parallel by some other computing tasks, improving the overall resource utilization of the system. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

The crossed cube is a prominent variant of the well known, highly regular-structured hypercube. In [24], it is shown that due to the loss of regularity in link topology, generating Hamiltonian cycles, even in a healthy crossed cube, is a more complicated procedure than in the hypercube, and fewer Hamiltonian cycles can be generated in the crossed cube. Because of the importance of fault-tolerance in interconnection networks, in this paper, we treat the problem of embedding Hamiltonian cycles into a crossed cube with failed links. We establish a relationship between the faulty link distribution and the crossed cube's tolerability. A succinct algorithm is proposed to find a Hamiltonian cycle in a CQntolerating up to n-2 failed links.

Hexagon is an ideal shape for clustering sensor networks, for it can seamlessly divide clustered areas, and is the largest regular polygon (in terms of the number of sides) that has this property. In this paper, we analyze the benefit of subdividing a hexagonal cluster for the purpose of reducing the overall power consumption in the cluster. Assuming a spatial Poisson distribution of sensor nodes in the cluster, we propose a subdivision scheme, and perform a comprehensive analytical estimate of power savings brought about by the subdivision. The analytical results show that subdivision will yield considerable saving in overall power consumption of the cluster, and the saving is heavily dependent on the nodes' transmission range and their deployment density. The limit on the depth of subdivision is also analyzed.

We investigate the use of sparse principal components for representing hyperspectral imagery when performing feature selection. For conventional multispectral data with low dimensionality, dimension reduction can be achieved by using traditional feature selection techniques for producing a subset of features that provide the highest class separability, or by feature extraction techniques via linear transformation. When dealing with hyperspectral data, feature selection is a time consuming task, often requiring exhaustive search of all the feature subset combinations. Instead, feature extraction technique such as PCA is commonly used. Unfortunately, PCA usually involves non-zero linear combinations or 'loadings' of all of the data. Sparse principal components are the sets of sparse vectors spanning a low-dimensional space that explain most of the variance present in the data. Our experiments show that sparse principal components having low-dimensionality still characterize the variance in the data. Sparse data representations are generally desirable for hyperspectral images because sparse representations help in human understanding and in classification.

We study the embedding of Hamiltonian cycle in the Crossed Cube, which is a prominent variant of the classical hypercube, obtained by crossing some straight links of a hypercube, and has been attracting much research interest in literatures since its proposal. We will show that due to the loss of link-topology regularity, generating Hamiltonian cycles in a crossed cube is a more complicated procedure than in its original counterpart. The paper studies how the crossed links affect an otherwise succinct process to generate a host of well-structured Hamiltonian cycles traversing all nodes. The condition for generating these Hamiltonian cycles in a crossed cube is proposed. An algorithm is presented that works out a Hamiltonian cycle for a given link permutation. The useful properties revealed and the algorithm proposed in this paper can find their way when system designers evaluate a candidate network's competence and suitability, balancing regularity and other performance criteria, in choosing an interconnection network.

In this paper, we rewrite the minimal-connected-component (MCC) model in 2-D meshes in a fully-distributed manner without using global information so that not only can the existence of a Manhattan-distance-path be ensured at the source, but also such a path can be formed by routing-decisions made at intermediate nodes along the path. We propose the MCC model in 3-D meshes, and extend the corresponding routing in 2-D meshes to 3-D meshes. We consider the positions of source & destination when the new faulty components are constructed. Specifically, all faulty nodes will be contained in some disjoint fault-components, and a healthy node will be included in a faulty component only if using it in the routing will definitely cause a non-minimal routing-path. A distributed process is provided to collect & distribute MCC information to a limited number of nodes along so-called boundaries. Moreover, a sufficient & necessary condition is provided for the existence of a Manhattan-distance-path in the presence of our faulty components. As a result, only the routing having a Manhattan-distance-path will be activated at the source, and its success can be guaranteed by using the information of boundary in routing-decisions at the intermediate nodes. The results of our Monte-Carlo-estimate show substantial improvement of the new fault-information model in the percentage of successful Manhattan-routing conducted in 3-D meshes.

In this paper the WSN model called COSMOS (cluster-based heterogeneous model for sensor networks) is described. A WSN model aiming at large size and scalability, COSMOS features a cluster-based, hierarchical network architecture. It comprises of a large number of low power, low cost sensors, presumably distributed in a large physical environment. The clusterheads of the whole WSN form a mesh-like topology which is equipped with more powerful transceiver that can communicate with any node within the cluster

In this paper we rewrite Wang's Minimal-Connected-Component (MCC) model in 2D meshes without using global information so that not only the existence of a minimal path can be ensured at the source, but also such a path can be formed by routing decisions at intermediate nodes along the path. We extend this MCC model and the corresponding routing in 2D meshes to 3D meshes. It is based on our early work on fault tolerant adaptive and minimal routing and the boundary information model in 3D meshes. We study fault tolerant adaptive and minimal routing from the source and the destination and consider the positions of the source and destination when the new faulty components are constructed. Specifically, all faulty nodes will be contained in some disjoint faulty components and a healthy node will be included in a faulty component only if using it in the routing will definitely cause a non-minimal routing path. A sufficient and necessary condition is proposed for the existence of the minimal routing path in the presence of our faulty components. Based on such a condition, the corresponding routing will guarantee a minimal path whenever it exists.

In [3], a hierarchical configuration for mesh was developed. The proposed scheme divides a mesh network into uniform smaller clusters. Each of these clusters contains a leader (or monitor) to communicate with the other members of the group. Leaders are then required to communicate with other leaders to form groups at higher levels. The hierarchical approach has been shown to reduce the communication cost by reducing the overall distance traveled by messages in the network [1, 2, 3]. Experiments were conducted on the hierarchical configuration to simulate different activities that it may be used for. Simulations were designed to test various sizes of the underlying mesh, as well as potential cluster sizes that may be utilized. In efforts to see if additional improvements could be made, a variety of throughputs of data were tested for the system.

We propose a new fault block model, minimal-connected-component (MCC), for fault-tolerant adaptive routing in mesh-connected multiprocessor systems. This model refines the widely used rectangular model by including fewer nonfaulty nodes in fault blocks. The positions of source/destination nodes relative to faulty nodes are taken into consideration when constructing fault blocks. The main idea behind it is that a node will be included in a fault block only if using it in a routing will definitely make the route nonminimal. The resulting fault blocks are of the rectilinear-monotone polygonal shapes. A sufficient and necessary condition is proposed for the existence of the minimal "Manhattan" routes in the presence of such fault blocks. Based on the condition, an algorithm is proposed to determine the existence of Manhattan routes. Since MCC is designed to facilitate minimal route finding, if there exists no minimal route under MCC fault model, then there will be absolutely no minimal route whatsoever. We also present two adaptive routing algorithms that construct a Manhattan route avoiding all fault blocks, should such routes exist.

We propose a deterministic fault-tolerant and deadlock-free routing protocol in 2D meshes based on Wu's fault-tolerant odd-even turn model (2000) and Wang's rectilinear-monotone polygonal fault block model. The fault-tolerant odd-even turn protocol, also called extended X-Y routing, was originally proposed to achieve fault-tolerant and deadlock-free routing among traditional, rectangular fault blocks. It does not use any virtual channels. The number of faults to be tolerated is unbounded as long as nodes outside fault blocks are connected in the mesh network. The recently proposed rectilinear-monotone polygonal fault blocks (also called minimal-connected-components or MCCs) are of the polygonal shapes, and is a refinement of rectangular fault blocks. The formation of MCCs depends on the relative locations of source and destination, and they include much fewer healthy nodes in resultant fault blocks. In this paper, we show that with a simple modification, the extended X-Y routing can also be applied to 2D meshes using extended MCCs.

A. Sengupta and A. Dahbura (1992) discussed how to characterize a diagnosable system under the comparison diagnosis model proposed by J. Maeng and M. Malek (1981) and a polynomial algorithm was given to identify the faulty processors provided that the system's diagnosability is known. However, for a general system, the determination of its diagnosability is not algorithmically easy. This paper proves that, for the important hypercube structured multiprocessor systems (n-cubes), the diagnosability under the comparison model is n when n/spl ges/5. The paper also studies the diagnosability of enhanced hypercube, which is obtained by adding 2/sup n-1/ more links to a regular hypercube of 2/sup n/ processors. It is shown that the augmented communication ability among processors also increases the system's diagnosability under the comparison model. We prove that the diagnosability is n+1 for an enhanced hypercube when n/spl ges/6.

Two algorithms are proposed to solve a reachability problem among time-dependent obstacles in 1D space. In the first approach, the motion planning problem is reduced to a path existence problem in a directed graph. The algorithm is very simple, with running time O(n/sup 2/), where n is the complexity of obstacles in space-time. The second algorithm uses a sweep-line technique and has running time O(n log/sub 2/ n). Besides, the latter algorithm can be easily modified to compute a collision-free trajectory, if such trajectories exist.

An enhanced hypercube is obtained by adding 2/sup n-1/ more links to a regular hypercube of 2/sup n/ processors. It has been shown that enhanced hypercubes have very good improvements over regular hypercubes in many measurements such as mean internode distance, diameter and traffic density. This paper proves that in the aspect of diagnosability, enhanced hypercubes also achieve improvements. Two diagnosis strategies, both using the well-known PMC diagnostic model, are studied: the precise (one-step) strategy proposed by Preparata, Metze and Chien (1967), and the pessimistic strategy proposed by Friedman (1975). Under the precise strategy, the diagnosability is shown to be increased to n+1 in enhanced hypercubes. (In regular hypercubes, the diagnosability is n under this strategy). Under the pessimistic strategy, the diagnosability is shown to be increased to 2n. (In regular hypercubes, the diagnosability under this strategy is 2n-2). Since the failure probability of one node is fairly low nowadays, so that the increase of diagnosability by one or two will considerably enhance the system's self-diagnostic capability, and considering the fact that diagnosability does not "easily" increase as the links in networks do, these improvements are noticeable.>