Optimal fault-tolerant Hamiltonicity of star graphs with conditional edge faults

The star graph is viewed as an attractive alternative to the hypercube. In this paper, we investigate the Hamiltonicity of an n-dimensional star graph. We show that for any n-dimensional star graph (n≥4) with at most 3n−10 faulty edges in which each node is incident with at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result improves on the previously best known result for the case where the number of tolerable faulty edges is bounded by 2n−7. We also demonstrate that our result is optimal with respect to the worst case scenario, where every other node of a cycle of length 6 is incident with exactly n−3 faulty noncycle edges.     

Adaptive checkpointing strategy to tolerate faults in economy based grid

In this paper, we develop a fault tolerant job scheduling strategy in order to tolerate faults gracefully in an economy based grid environment. We propose a novel adaptive task checkpointing based fault tolerant job scheduling strategy for an economy based grid. The proposed strategy maintains a fault index of grid resources. It dynamically updates the fault index based on successful or unsuccessful completion of an assigned task. Whenever a grid resource broker has tasks to schedule on grid resources, it makes use of the fault index from the fault tolerant schedule manager in addition to using a time optimization heuristic. While scheduling a grid job on a grid resource, the resource broker uses fault index to apply different intensity of task checkpointing (inserting checkpoints in a task at different intervals). To simulate and evaluate the performance of the proposed strategy, this paper enhances the GridSim Toolkit-4.0 to exhibit fault tolerance related behavior. We also compare “checkpointing fault tolerant job scheduling strategy” with the well-known time optimization heuristic in an economy based grid environment. From the measured results, we conclude that even in the presence of faults, the proposed strategy effectively schedules grid jobs tolerating faults gracefully and executes more jobs successfully within the specified deadline and allotted budget. It also improves the overall execution time and minimizes the execution cost of grid jobs.     

Stochastic allocation and scheduling for conditional task graphs in multi-processor systems-on-chip

Embedded systems designers are turning to multicore architectures to satisfy the ever-growing computational needs of applications within a reasonable power envelope. One of the most daunting challenges for MultiProcessor System-on-Chip (MPSoC) platforms is the development of tools for efficient mapping multi-task applications onto hardware platforms. Software mapping can be formulated as an optimal allocation and scheduling problem, where the application is modeled as a task graph, the target hardware is modeled as a set of heterogeneous resources, and the objective function represents a design goal α (e.g. minimum execution time, minimum usage of communication resources, etc.). Conditional task graphs, where inter-task edges represent data as well as control dependencies, are a well-known computational model to describe complex real-life applications where alternative execution paths, guarded by conditionals, can be specified. Each condition has a probability associated with each possible outcome.     

A recursive genetic framework for evolutionary decision-making in problems with high dynamism

Communication and coordination are the main cores for reaching a constructive agreement among multi-agent systems (MASs). Dividing the overall performance of MAS to individual agents may lead to group learning as opposed to individual learning, which is one of the weak points of MASs. This paper proposes a recursive genetic framework for solving problems with high dynamism. In this framework, a combination of genetic algorithm and multi-agent capabilities is utilised to accelerate team learning and accurate credit assignment. The argumentation feature is used to accomplish agent learning and the negotiation features of MASs are used to achieve a credit assignment. The proposed framework is quite general and its recursive hierarchical structure could be extended. We have dedicated one special controlling module for increasing convergence time. Due to the complexity of blackjack, we have applied it as a possible test bed to evaluate the system’s performance. The learning rate of agents is measured as well as their credit assignment. The analysis of the obtained results led us to believe that our robust framework with the proposed negotiation operator is a promising methodology to solve similar problems in other areas with high dynamism.     

Reliable ℋ∞ filtering for LPV systems with sensor faults in finite frequency domain

This article deals with the reliable ?_∞ filtering problem for linear parameter varying continuous-time systems with bounded disturbances and sensor faults. Different from existing approaches, a parameter-dependent filter is designed in finite frequency range, which is important in practice since full frequency approaches are conservative to some extent for the case when frequency ranges of disturbances are known beforehand. With the aid of Generalised Kalman–Yakubovich–Popov lemma, the filter design problem is formulated into solving a set of linear matrix inequalities problem. A numerical example is given to illustrate the effectiveness of the proposed methods.     

Self-suppression of limit cycles in non-linear sampled-data systems with transportation lag†

This paper extends the principle of self-suppression of oscillations employed in continuous systems to non-linear sampled-data systems with transportation lag. The principle is based on the proper design of a. minor feedback loop to generate an oscillation with the desired frequency and amplitude. The type of response of the system is shown to depend entirely on the gain of the inner feedback path. Further it is shown that larger values of delay require larger gains to be employed in the inner feedback path to suppress the inherent oscillation. The results clearly indicate that by proper adjustment of the gain a response said to be optimum in regard to Borne performance index can be obtained.     

Energetically consistent simulation of simultaneous impacts and contacts in multibody systems with friction

This paper presents a methodology for treating energy consistency when considering simultaneous impacts and contacts with friction in the simulation of systems of interconnected bodies. Hard impact and contact is considered where deformation of the impacting surfaces is negligible. The proposed approach uses a discrete algebraic model of impact in conjunction with moment and tangential coefficients of restitution (CORs) to develop a general impact law for determining post-impact velocities. This process depends on impulse–momentum theory, the complementarity conditions, a principle of maximum dissipation, and the determination of contact forces and post-impact accelerations. The proposed methodology also uses an energy-modifying COR to directly control the system’s energy profile over time. The key result is that different energy profiles yield different results and thus energy consistency should be considered carefully in the development of dynamic simulations. The approach is illustrated on a double pendulum, considered to be a benchmark case, and a bicycle structure.     

Encryption of speech signal with multiple secret keys in time and transform domains

This paper introduces a new speech cryptosystem, which is based on permutation and masking of speech segments using multiple secret keys in both time and transform domains. The main key is generated, randomly, using a Pseudo Noise (PN) sequence generator, and two other keys are generated from the main key to be used in the subsequent rounds of encryption. Either the Discrete Cosine Transform (DCT) or the Discrete Sine Transform (DST) can be used in the proposed cryptosystem to remove the residual intelligibility resulting from permutation and masking in the time domain. In the proposed cryptosystem, the permutation process is performed with circular shifts calculated from the key bits. The utilized mask is also generated from the secret key by circular shifts. The proposed cryptosystem has a low complexity, small delay, and high degree of security. Simulation results prove that the proposed cryptosystem is robust to the presence of noise.     

Adaptive-resolution reinforcement learning with polynomial exploration in deterministic domains

We propose a model-based learning algorithm, the Adaptive-resolution Reinforcement Learning (ARL) algorithm, that aims to solve the online, continuous state space reinforcement learning problem in a deterministic domain. Our goal is to combine adaptive-resolution approximation schemes with efficient exploration in order to obtain polynomial learning rates. The proposed algorithm uses an adaptive approximation of the optimal value function using kernel-based averaging, going from coarse to fine kernel-based representation of the state space, which enables us to use finer resolution in the “important” areas of the state space, and coarser resolution elsewhere. We consider an online learning approach, in which we discover these important areas online, using an uncertainty intervals exploration technique. In addition, we introduce an incremental variant of the ARL (IARL), which is a more practical version of the original algorithm with reduced computational complexity at each stage. Polynomial learning rates in terms of mistake bound (in a PAC framework) are established for these algorithms, under appropriate continuity assumptions.     

Managing peer-to-peer networks with human tactics in social interactions

Small-world phenomena have been observed in existing peer-to-peer (P2P) networks which has proved useful in the design of P2P file-sharing systems. Most studies of constructing small world behaviours on P2P are based on the concept of clustering peer nodes into groups, communities or clusters. However, managing additional multilayer topology increases maintenance overhead, especially in highly dynamic environments. In this paper, we present Social-like P2P systems (Social-P2Ps) for object discovery by self-managing P2P topology with human tactics in social networks. In Social-P2Ps, queries are routed intelligently even with limited cached knowledge and node connections. Unlike community-based P2P file-sharing systems, we do not intend to create and maintain peer groups or communities consciously. In contrast, each node connects to other peer nodes with the same interests spontaneously by the result of daily searches.     

Fractional Path Coloring in Bounded Degree Trees with Applications

This paper studies the natural linear programming relaxation of the path coloring problem. We prove constructively that finding an optimal fractional path coloring is Fixed Parameter Tractable (FPT), with the degree of the tree as parameter: the fractional coloring of paths in a bounded degree trees can be done in a time which is linear in the size of the tree, quadratic in the load of the set of paths, while exponential in the degree of the tree. We give an algorithm based on the generation of an efficient polynomial size linear program. Our algorithm is able to explore in polynomial time the exponential number of different fractional colorings, thanks to the notion of trace of a coloring that we introduce. We further give an upper bound on the cost of such a coloring in binary trees and extend this algorithm to bounded degree graphs with bounded treewidth. Finally, we also show some relationships between the integral and fractional problems, and derive a 1+5/3e≈1.61—approximation algorithm for the path coloring problem in bounded degree trees, improving on existing results. This classic combinatorial problem finds applications in the minimization of the number of wavelengths in wavelength division multiplexing (wdm) optical networks.     

An Efficient Algorithm for Modelling Duration in Hidden Markov Models, with a Dramatic Application

For many years, the hidden Markov model (HMM) has been one of the most popular tools for analysing sequential data. One frequently used special case is the left-right model, in which the order of the hidden states is known. If knowledge of the duration of a state is available it is not possible to represent it explicitly with an HMM. Methods for modelling duration with HMM’s do exist (Rabiner in Proc. IEEE 77(2):257–286, [1989]), but they come at the price of increased computational complexity. Here we present an efficient and robust algorithm for modelling duration in HMM’s, and this algorithm is successfully used to control autonomous computer actors in a theatrical play.     

Reliable H∞ control for nonlinear discrete-time systems with multiple intermittent faults in sensors or actuators

This study proposes a fault-tolerant control method for stochastic systems with multiple intermittent faults (IFs) and nonlinear disturbances, and both sensor and actuator faults are considered. The occurrence and disappearance of IFs are governed by Markov chain, and its transition probabilities are partly known. Hence, the faulty system can be described by a Markovian jump system (MJS). In order to ensure that the MJS is stochastically stable and satisfies H_∞ performance index, mode-dependent output feedback controllers are modelled using linear matrix inequalities. Numerous sufficient conditions for stochastic stability are obtained on the basis of Lyapunov stability theory. Finally, the effectiveness of the developed method is evaluated on the three-tank system.     

Scalable multimedia delivery with QoS management in pervasive computing environment

People are increasingly demanding rich-media and bundled services. However, the diverse terminals, heterogeneous networks as well as various user requirements constrain the multimedia access to low quality in the pervasive computing environment. In order to enable rich-media delivery across a wide range of devices and networks, multimedia adaptation with scalable QoS management is an important issue. Our research introduces a Scalable Multimedia Delivery (SMD) framework with QoS management. This framework utilizes the CAM4Home metadata model to aggregate multimodal rich media services into a bundle. MPEG-21 metadata is integrated into the CAM4Home model to enforce interoperable QoS management. The issues in supporting QoS are addressed on both fidelity and modality. We further develop the SMD system in IP Multimedia Subsystem (IMS) architecture, where multimedia adaptation is implemented through application-level QoS negotiation.     

Short Cycles Make W-hard Problems Hard: FPT Algorithms for W-hard Problems in Graphs with no Short Cycles

We show that several problems that are hard for various parameterized complexity classes on general graphs, become fixed parameter tractable on graphs with no small cycles. More specifically, we give fixed parameter tractable algorithms for Dominating Set, t -Vertex Cover (where we need to cover at least t edges) and several of their variants on graphs with girth at least five. These problems are known to be W[i]-hard for some i≥1 in general graphs. We also show that the Dominating Set problem is W[2]-hard for bipartite graphs and hence for triangle free graphs. In the case of Independent Set and several of its variants, we show these problems to be fixed parameter tractable even in triangle free graphs. In contrast, we show that the Dense Subgraph problem where one is interested in finding an induced subgraph on k vertices having at least l edges, parameterized by k, is W[1]-hard even on graphs with girth at least six. Finally, we give an O(log p) ratio approximation algorithm for the Dominating Set problem for graphs with girth at least 5, where p is the size of an optimum dominating set of the graph. This improves the previous O(log n) factor approximation algorithm for the problem, where n is the number of vertices of the input graph. A preliminary version of this paper appeared in the Proceedings of 10th Scandinavian Workshop on Algorithm Theory (SWAT), Lecture Notes in Computer Science, vol. 4059, pp. 304–315, 2006.     

A dynamic holding strategy in public transit systems with real-time information

Holding strategies are among the most commonly used operation control strategies in transit systems. In this paper, a dynamic holding strategy is developed, which consists of two major steps: (1) judging whether an early bus should be held, and (2) optimizing the holding times of the held bus. A model based on support vector machine (SVM), which contains four input variables (time-of-day, segment, the latest speed on the next segment, and the bus speed on the current segment) for forecasting the early bus departure times from the next stop is also developed. Then, in order to determine the optimal holding times, a model aiming to minimize the user costs is constructed and a genetic algorithm is used to optimize the holding times. Finally, the dynamic holding strategy proposed in this study is illustrated with the microscopic simulation model Paramics and some conclusions are drawn.

On the determination of limit cycles in relay control systems with additional saturation type non-linear elements†

Exact and approximate methods of determination of limit cycles in a relay control system including an actuator with PI transfer function and limited output are given. No restrictions are imposed on the order of the plant transfer function. The stability of the limit cycles may be checked using one of the well-known methods, using the describing function concept. With the help of an example it is indicated that the methods suggested give reliable results in eases where the use of the conventional describing function fails.