MoDiVHA: A Hierarchical Strategy for Distributed Test Assignment

Distributed diagnosis allows a set of fault-free nodes to monitor the state of all nodes of a given system. Diagnosis is based on the results of tests, which are assigned among system nodes. Hierarchical testing assignments lead to efficient and scalable diagnosis algorithms, both in terms of the number of tests executed, and the latency. In this work we present a novel hierarchical testing strategy, called MoDiVHA. By obtaining as much diagnostic information as possible from each test, and avoiding tests on nodes about which information has been already obtained, MoDiVHA executes less tests in comparison with previously proposed assignments. Experimental results are presented from three series of simulations conducted to compute the number of tests and diagnosis latency for various system sizes and fault situations.     

一种高效的基于BC图的t/k-诊断算法

为了提高系统级故障诊断中的诊断度,人们以牺牲很小一部分结点不能正确诊断为代价,提出了t/k-故障诊断策略.BC图是包括了超立方体和多种变形立方体的一类图.对于结点总数为N的BC图,本文提出了一个O(N log2N)的t/k-故障诊断算法.目前尚未有相关t/k-故障诊断算法的文章发表,但与著名的悲观一步t-故障诊断算法(t/k-故障诊断算法在k=1时的情况)的O(N2.5)相比较,在时间复杂度上本文算法是高效的.     

星图的自适应诊断

自适应性诊断的目的,是正确辨别出结点的性质。没有公共点的两对结点可以在同一个诊断周中出现。文中构造了星图的一个递归的哈密尔顿自适应诊断方法。在出错结点数不超过n-1个的情况下,这种方法只需要个诊断周。在最好和最坏的情况下,它分别需要n!+(n-2)和(2n-1)(n-1)!次诊断。     

基于互测PMC模型的故障诊断方法及其应用

PMC模型是一种基于测试的系统级故障模型.针对传统诊断算法的弱点,作者于2003年建立起了PMC模型方程诊断算法的框架.本文的主要工作是:(1)对以往的理论进一步补充完善;(2)给出一个直接求绝对故障基的简便方法;(3)通过引入直和的概念,将高维PMC故障模型分拆成低维模型进行诊断;(4)举例说明方程诊断算法的应用.     

A Distributed Algorithm for Dynamic Channel Allocation

Recent demand for mobile telephone service has been growing rapidly while the electro-magnetic spectrum of frequencies allocated for this purpose remains limited. Any solution to the channel assignment problem is subject to this limitation, as well as the interference constraint between adjacent channels in the spectrum. Channel allocation schemes provide a flexible and efficient access to bandwidth in wireless and mobile communication systems. In this paper, we present an efficient distributed algorithm for dynamic channel allocation based upon mutual exclusion model, where the channels are grouped by the number of cells in a cluster and each group of channels cannot be shared concurrently within the cluster. We discuss the algorithm and prove its correctness. We also show that the algorithm requires at most (worst case) O(N _gN _n logN _n) messages, where N _g is the number of groups and N _n is the number of neighbors. This is compared to Choy's algorithm which requires O(N _g ²N _n), where N _g is the number of groups and N _n is the number of neighboring cells in the system. We report our algorithm's performance with several channel systems using different types of call arrival patterns. Our results indicate that significant low denial rate, low message complexity and low acquisition time can be obtained using our algorithm.     

系统级故障诊断的研究现状与发展前景

随着大数据时代的到来,人们对于计算机系统的稳定性要求日益增高,如何快速而准确地找出系统中的故障点,成为了人们的研究热题,对系统级故障诊断算法的研究逐渐受到了人们的重视。本文首先对现有的系统级故障诊断算法进行了分类,进而阐述了系统级故障诊断算法的近期主要研究成果,最后预测了该领域的未来研究方向与发展前景。     

A distributed battery recovery aware topology control algorithm for wireless sensor networks

Battery recovery effect is a phenomenon that the available capacity of a battery could increase if the battery can sleep for a certain period of time since its last discharging. Accordingly, the battery can work for a longer time when it takes some rests between consecutive discharging processes than when it works all the time. However, this effect has not been considered in the design of energy‐efficient topology control algorithms for wireless sensor networks. In this paper, we propose a distributed battery recovery effect aware connected dominating set constructing algorithm (BRE‐CDS) for wireless sensor networks. In BRE‐CDS, each network node periodically decides to join the connected dominating set or not. Nodes that have slept in the preceding round have priority to join the connected dominating set in the current round while nodes that have worked in the preceding round are encouraged to take sleep in the current round for battery recovery. Detailed algorithm design is presented. The computational complexity of BRE‐CDS is deduced to be O(D²), where D is node degree. Simulation results show that BRE‐CDS can significantly prolong the network lifetime as compared with existing work. Copyright © 2016 John Wiley & Sons, Ltd.     

Scheduling Algorithms for Star-Coupled WDM Networks with Tunable Transmitter and Tunable Receiver Architecture

This paper presents the design and analysis of two scheduling algorithms for a reservation-based medium access control (MAC) protocol for wavelength division multiplexed (WDM) multi-channel optical networks. The network architecture is based on a passive star topology with one tunable transmitter and receiver (TT-TR) per node. The main objective of scheduling algorithm design is to reduce the computation time while maximizing the utilization of the network resources. In this paper, we propose two scheduling schemes called SEQSAM (SEQuential Scheduling AlgorithM) and BALSAM (BALanced Scheduling AlgorithM). Let M denote the number of nodes, C the number of channels, and K the maximum number of packets transmitted by one node to another. SEQSAM uses the M × M traffic demand matrix--obtained during the reservation phase of the MAC protocol--to compute a collision-free schedule for the nodes of the network. BALSAM uses the modified MULTI-FIT algorithm (MMFT) [1] to convert the M × M matrix into a corresponding M × C matrix, which is input to the IBS (Interval Based Scheduling) algorithm [2] that schedules the requests of the nodes. The overall time complexity of SEQSAM is O(M ³) compared to BALSAM algorithm's time complexity of O(M ² CK + M ² + MlogM). Note that the lower bound for any scheduling algorithm operating on a M × M matrix is O(M ²). A simulation-based performance study that considers network utilization, computation time, tuning latency, average packet latency and throughput for 1.2 Gbps and 2.4 Gbps data streams is presented.     

Fast optimal diagnosis procedures for k-out-of-n:G systems

A k-out-of-n:G system consists of a set of components, where each component is either faulty or fault-free. The system is working if at least k components are fault-free. The problem of finding an optimal diagnosis procedure for a given k-out-of-n:G system has been considered in several research fields including medical diagnosis, redundant-system testing, and searching data-files. A polynomial-time algorithm for this problem was presented first by Salloum, and later by Salloum and Breuer, and independently by Ben-Dov. This paper implements the Salloum-Breuer-Ben-Dov algorithm, leading to an optimal diagnosis procedure that can determine the state of any given system in O(n·log(n)) time complexity and O(n) space complexity. The efficiency is achieved by using a generalized radix sorting procedure that uses a heap data structure. For some k-out-of-n:G systems, including those with equal testing costs for all components, the components along the leftmost and rightmost paths in the optimal diagnostic tree uniquely determine the other components in the tree. This property is used to devise a faster optimal diagnosis procedure than the one for the general k-out-of-n:G system. With regard to complexity, these procedures are the best solutions for the problem under consideration. This conjecture is supported by the fact that all these procedures require a sorting operation which has O(n·log(n)) as a lower bound on its time complexity     

低占空比传感网中分布式的环状流水线工作调度研究

低占空比传感网中节点的长时间睡眠会导致数据查询延迟的增加.如何调度节点唤醒时间从而最小化延迟,是一个难解的组合优化问题.提出一个分布式的环状流水线调度算法,不用长时间等待即可进行数据传输.分析表明,算法可获得较低的延迟和更长的网络生命周期.     

A new recursive algorithm for the reliability evaluation of a distributed program

The reliability of a distributed program is very sensitive to the ways of file distribution, and communication system topology. It is usually much more complex to analyze the reliability of distributed program than that of the network reliability. This paper presents a distributed program reliability analysis algorithm that is developed based on the concept of sharp operation. The algorithm provides a (E−n+2) * E memory space requirement and O(n+E+E*N_t) computation time, where E is the number of edges, n is the number of nodes, and N_t is the number of file spanning trees in the corresponding graph of distributed system, respectively. Compared with existing algorithms, the proposed algorithm is considered more economic both in time and space.     

Design strategy for optimizing power consumption of sensor node with Min(N,T) policy M/G/1 queuing models

Energy saving is an important issue in wireless sensor networks for majority of sensor nodes equipped with non‐rechargeable batteries. To prolong the lifetime of sensor nodes, most research works have focused on how to tune the duty cycling schemes among nodes to save the communication cost using multifarious wake‐up strategies. To this aim, we propose a novel design strategy for mitigating the average power consumption of sensor node using the Min(N,T) policy M/G/1 queuing theory. The basic point of our approach is that Min(N,T) dyadic policy would mitigate the total average times of medium contention by having both a counter (N) and a timer (T) for the control of triggering on a radio server to transmit queued packets, and then the power consumption of communication can be alleviated. A comprehensive mathematical analysis on the optimal control parameters had been made. Much data analysis and simulations had been conducted to validate the proposed model. In this article, we show how the improvement level on power consumption can be achieved through analytical and simulation results. With little or no extra management cost, the proposed add‐on power‐saving technique can provide a design strategy to optimize relevant system parameters including power consumption and latency delay. Copyright © 2011 John Wiley & Sons, Ltd.     

DUCR: Distributed unequal cluster‐based routing algorithm for heterogeneous wireless sensor networks

Designing energy efficient communication protocols for wireless sensor networks (WSNs) to conserve the sensors' energy is one of the prime concerns. Clustering in WSNs significantly reduces the energy consumption in which the nodes are organized in clusters, each having a cluster head (CH). The CHs collect data from their cluster members and transmit it to the base station via a single or multihop communication. The main issue in such mechanism is how to associate the nodes to CHs and how to route the data of CHs so that the overall load on CHs are balanced. Since the sensor nodes operate autonomously, the methods designed for WSNs should be of distributed nature, i.e., each node should run it using its local information only. Considering these issues, we propose a distributed multiobjective‐based clustering method to assign a sensor node to appropriate CH so that the load is balanced. We also propose an energy‐efficient routing algorithm to balance the relay load among the CHs. In case any CH dies, we propose a recovery strategy for its cluster members. All our proposed methods are completely distributed in nature. Simulation results demonstrate the efficiency of the proposed algorithm in terms of energy consumption and hence prolonging the network lifetime. We compare the performance of the proposed algorithm with some existing algorithms in terms of number of alive nodes, network lifetime, energy efficiency, and energy population.     

An efficient clustering and load balancing of distributed cloud data centers using graph theory

The prime focus of the Cloud Service Providers is enhancing the service delivery performance of the distributed cloud data centers. The clustering and load balancing of distributed cloud data centers have significant impact on its service delivery performance. Hence, this paper models distributed cloud data center environment as a network graph and proposes a two‐phase cluster‐based load balancing (CLB) algorithm based on a graph model. The first phase proposes a Cloud Data Center Clustering algorithm to cluster the distributed cloud data centers based on their proximity. The second phase proposes a Client‐Cluster Assignment algorithm to perform uniform distribution of the client requests across the clusters to enable load balancing. To assess the performance, the proposed algorithms are compared with other K‐constrained graph‐based clustering algorithms namely, graph‐based K‐means and K‐spanning tree algorithms on a simulated distributed cloud data center environment. The experimental results reveal that the proposed CLB algorithm outperforms the compared algorithms in terms of the average clustering time, load distribution, and fairness index and hence improves the service delivery performance of the distributed cloud data centers.     

Distributed diagnosis for homogeneous systems

This article presents a distributed fault-diagnosis algorithm for identifying faulty and fault-free units (processors, PEs, cells) in homogeneous systems. It is based on local comparison among units in a system and dissemination of the test results. Each unit performs comparison with its neighbors by using its own comparator. Unlike other approaches, the algorithm does not assume that diagnostic circuits are fault free. The algorithm is simple enough to be realized with small circuit overhead. The results are especially useful in locating faulty units in processor arrays implemented on a single chip or wafer. Computer simulation has shown that even for low unit yields, extremely high performance (fault coverage) can be obtained by adjusting algorithm parameters.     

Energy-Efficient Routing Protocol for Wireless Sensor Networks with Static Clustering and Dynamic Structure

Data gathering is an essential operation in wireless sensor networks. For periodic data gathering applications, each sensor node has data that must be sent to a distant base station in a round of communication. Due to the limited battery power of sensor nodes, each sensor node transmitting its sensed data to the base station directly significantly consumes its energy. This work presents a hierarchical ring-based data gathering (HRDG) scheme for dense wireless sensor networks. A hierarchical grid structure is constructed, and only some sensor nodes are elected as grid heads for gathering data, subsequently reducing the total energy consumption per round. Grid heads are then organized into hierarchical rings to decrease the transmission delay of a round. The proposed HRDG scheme focuses on reducing the energy × delay cost in a round of data gathering. Moreover, the energy × delay cost of HRDG is analyzed. Simulation results indicate that the proposed HRDG scheme outperforms other data gathering schemes in terms of the number of rounds, the energy × delay cost and coverage ratio.     

Round reduction-based fault attack on SM4 algorithm

A novel method of fault attack based on round reduction against SM4 algorithm was proposed.Faults were in-jected into the last four rounds of the SM4 encryption algorithm,so that the number of the algorithm's rounds can be re-duced.In known-ciphertext scenario,four traces are enough to recover the total 128 bit master key by screening these faults easily.The proposed attack is made to an unprotected SM4 smart card.Experiment shows that this attack method is efficient,and which not only simplifies the existing differential fault attack,but also improves the feasibility of the attack.     

Spanning tree based algorithms for low latency and energy efficient data aggregation enhanced convergecast (DAC) in wireless sensor networks

Many wireless sensor networks (WSNs) employ battery-powered sensor nodes. Communication in such networks is very taxing on its scarce energy resources. Convergecast – process of routing data from many sources to a sink – is commonly performed operation in WSNs. Data aggregation is a frequently used energy-conversing technique in WSNs. The rationale is to reduce volume of communicated data by using in-network processing capability at sensor nodes. In this paper, we address the problem of performing the operation of data aggregation enhanced convergecast (DAC) in an energy and latency efficient manner. We assume that all the nodes in the network have a data item and there is an a priori known application dependent data compression factor (or compression factor), γ, that approximates the useful fraction of the total data collected.The paper first presents two DAC tree construction algorithms. One is a variant of the Minimum Spanning Tree (MST) algorithm and the other is a variant of the Single Source Shortest Path Spanning Tree (SPT) algorithm. These two algorithms serve as a motivation for our Combined algorithm (COM) which generalized the SPT and MST based algorithm. The COM algorithm tries to construct an energy optimal DAC tree for any fixed value of α (= 1 − γ), the data growth factor. The nodes of these trees are scheduled for collision-free communication using a channel allocation algorithm. To achieve low latency, these algorithms use the β-constraint, which puts a soft limit on the maximum number of children a node can have in a DAC tree. The DAC tree obtained from energy minimizing phase of tree construction algorithms is re-structured using the β-constraint (in the latency minimizing phase) to reduce latency (at the expense of increasing energy cost). The effectiveness of these algorithms is evaluated by using energy efficiency, latency and network lifetime as metrics. With these metrics, the algorithms’ performance is compared with an existing data aggregation technique. From the experimental results, for a given network density and data compression factor γ at intermediate nodes, one can choose an appropriate algorithm depending upon whether the primary goal is to minimize the latency or the energy consumption.     

基于系统级诊断理论的卫星网络故障诊断

本文将系统级诊断引入到卫星网络的故障诊断领域.针对卫星可以具有多个通信方向且可以部分通信失效的特性,提出了一种新颖的卫星网络建模方法——双层节点图,设计了基于广播的卫星网络系统级诊断方案,并对其通信开销进行了理论分析.测试中充分利用了卫星广播和一对多的通信模式,使本方案不但适用于任意类型的网络拓扑,而且可以节省通信量.仿真结果表明诊断的通信开销随网络中可通信端口数量的减少而下降.