Towards intrinsically universal asynchronous CA

We consider asynchronous one-dimensional cellular automata (CA). It is shown that there is one with von Neumann neighborhood of radius 1 which can simulate each asynchronous one-dimensional cellular automaton. Analogous constructions are described for α-asynchronous CA (where each cell independently enters a new state with probability α, and for “neighborhood independent” asynchronous CA (where never two cells are updated simultaneously if one is in the neighborhood of the other). This also gives rise to a construction for so-called fully asynchronous CA (where in each step exactly one cell is updated).     

The SR-GCWS hybrid algorithm for solving the capacitated vehicle routing problem

The capacitated vehicle routing problem (CVRP) is a well known problem which has long been tackled by researchers for several decades now, not only because of its potential applications but also due to the fact that CVRP can be used to test the efficiency of new algorithms and optimization methods. The objective of our work is to present SR-GCWS, a hybrid algorithm that combines a CVRP classical heuristic with Monte Carlo simulation using state-of-the-art random number generators. The resulting algorithm is tested against some well-known benchmarks. In most cases, our approach is able to compete or even outperform much more complex algorithms, which is especially interesting if we consider that our algorithm does not require any previous parameter fine-tuning or set-up process. Moreover, our algorithm has been able to produce high-quality solutions almost in real-time for most tested instances. Another important feature of the algorithm worth mentioning is that it uses a randomized constructive heuristic, capable of generating hundreds or even thousands of alternative solutions with different properties. These alternative solutions, in turn, can be really useful for decision-makers in order to satisfy their utility functions, which are usually unknown by the modeler. The presented methodology may be a fine framework for the development of similar algorithms for other complex combinatorial problems in the routing arena as well as in some other research fields.     

一种基于未知发射功率的室内定位优化算法

在基于RSSI的室内定位中,未知的发射功率会降低节点的定位性能。针对实际应用中发射功率未知的问题,基于真实室内环境下RSSI的变化情况,提出了一种基于未知发射功率的室内定位优化算法。该算法将发射功率看成一个未知的变量,把一个定位问题转化为一个非线性优化问题,并通过将其中的非线性项进行线性逼近,最终采用最小二乘法求出了目标节点的坐标。仿真和实验结果表明,提出的算法在发射功率未知的情况下,要明显优于传统的定位算法,具有很好的定位性能。     

A design of generalized minimum-state-change FSSP algorithms and their implementations

The firing squad synchronization problem (FSSP) on cellular automata has been studied extensively for more than 50 years, and a rich variety of FSSP algorithms has been proposed. Here we consider the FSSP from a view point of state-change complexity that models the energy consumption of SRAM-type storage with which cellular automata might be built. In the present paper, we propose minimum-state-change generalized FSSP (GFSSP) algorithms for synchronizing any one-dimensional (1D) cellular automaton, where the initial synchronization operation is started by any cell in the array. First, we construct two minimum-time, minimum-state-change GFSSP implementations on finite state automata: one is based on Goto’s algorithm, known as the first minimum-time FSSP algorithm that was reconstructed again recently in Umeo et al. (A new reconstruction and the first implementation of Goto’s FSSP algorithm, 2017), and the other is based on Gerken’s (Diplomarbeit, Institut für Theoretische Informatik, Technische Universität Braunschweig, pp 1–50, 1987) one. These implementations are optimal not only in time but also in the state-change complexity. The implementations of the minimum-time GFSSP algorithms are the first ones having the minimum-state-change complexity. In addition, we also present a six-state 145-rule non-minimum-time, minimum-state-change GFSSP implementation. The implemented GFSSP algorithm is the smallest one, known at present, in number of states of the finite state automaton.     

A clock synchronization algorithm for the performance analysis of multicomputer systems

The paper deals with the implementation of global time in multicomputer systems. After a formalization of the synchronization problem, techniques to estimate the synchronization delay and to compensate the drift error are proposed. Then SYNC_WAVE, a clock synchronization algorithm where the values of a reference clock are diffused in a wave-like manner, is described. SYNC_WAVE has no provision for fault-tolerance and is specially designed to introduce low CPU and communication overhead, in order to support performance analysis applications efficiently. An implementation of the devised algorithm in a transputer-based system is presented, showing the accuracy results obtained. Finally SYNC_WAVE is compared to other synchronization algorithms and several of its possible applications are suggested.     

Extension of cellular automata via the introduction of an algorithm for the recursive estimation of neighbors

This study focuses on an extended model of standard cellular automaton (CA), which includes an extra index, comprising a radius that defines a perception area for each cell in addition to the radius defined by the CA rule. Such an extension can be realized by introducing a recursive algorithm called the “Recursive Estimation of Neighbors.” The extended CA rules form a sequence ordered by this index, which includes the CA rule as its first term. This extension aims to construct a model that can be used within the CA framework to study the relation between information processing and pattern formation in collective systems. Even though the extension presented here is merely an extrapolation to a CA having a larger rule neighborhood identical to the perception area, the extra radius can be interpreted as an individual attribute of each cell. The novel perspective to CA provided here makes it possible to build heterogeneous CAs, which contain cells having different extra radii. Several pattern formations in the extension of one-dimensional elementary CAs and two-dimensional Life-like CAs are presented. It is expected that the extended model can be applied to various simulations of complex systems and in other fields.     

Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem

We present a new approximation algorithm for the two-dimensional bin-packing problem. The algorithm is based on two one-dimensional bin-packing algorithms. Since the algorithm is of next-fit type it can also be used for those cases where the output is required to be on-line (e. g. if we open an new bin we have no possibility to pack elements into the earlier opened bins). We give a tight bound for its worst-case and show that this bound is a parameter of the maximal sizes of the items to be packed. Moreover, we also present a probabilistic analysis of this algorithm.     

An evolutionary approach to the design of controllable cellular automata structure for random number generation

Cellular automata (CA) has been used in pseudorandom number generation for over a decade. Recent studies show that two-dimensional (2-D) CA pseudorandom number generators (PRNGs) may generate better random sequences than conventional one-dimensional (1-D) CA PRNGs, but they are more complex to implement in hardware than 1-D CA PRNGs. In this paper, we propose a new class of 1-D CA - controllable cellular automata (CCA)-without much deviation from the structural simplicity of conventional 1-D CA. We first give a general definition of CCA and then introduce two types of CCA: CCA0 and CCA2. Our initial study shows that these two CCA PRNGs have better randomness quality than conventional 1-D CA PRNGs, but that their randomness is affected by their structures. To find good CCA0/CCA2 structures for pseudorandom number generation, we evolve them using evolutionary multiobjective optimization techniques. Three different algorithms are presented. One makes use of an aggregation function; the other two are based on the vector-evaluated genetic algorithm. Evolution results show that these three algorithms all perform well. Applying a set of randomness tests on the evolved CCA PRNGs, we demonstrate that their randomness is better than that of 1-D CA PRNGs and can be comparable to that of 2-D CA PRNGs.     

A New and Improved Algorithm for Fault-Tolerant Clock Synchronization

Synchronous clocks are an essential requirement for a variety of distributed system applications. Many of these applications are safety-critical and require fault tolerance. In this paper, a new "Sliding Window" clock synchronization algorithm is presented. It offers two significant advantages. First, it can tolerate considerably higher percentages of faults than any known algorithm. In addition, it achieves clock synchronization tightness that is tighter than or as tight as that of other algorithms. A comprehensive simulation environment is used for an evaluation and comparison of the Sliding Window Algorithm with other clock synchronization algorithms. A quantitative evaluation using this environment outlines the achievable tightness under different conditions and shows that the Sliding Window Algorithm is capable of tolerating more than 50% of the nodes being faulty at any time as well as short fault bursts that affect all nodes. The evaluation also shows that our algorithm synchronizes up to 38% tighter than other algorithms. Finally, it is proven that the algorithm is able to guarantee synchronization in an n-node system even if the number of Byzantine faults is n/4.     

A statistical study of a class of cellular evolutionary algorithms.

Parallel evolutionary algorithms, over the past few years, have proven empirically worthwhile, but there seems to be a lack of understanding of their workings. In this paper we concentrate on cellular (fine-grained) models, our objectives being: (1) to introduce a suite of statistical measures, both at the genotypic and phenotypic levels, which are useful for analyzing the workings of cellular evolutionary algorithms; and (2) to demonstrate the application and utility of these measures on a specific example-the cellular programming evolutionary algorithm. The latter is used to evolve solutions to three distinct (hard) problems in the cellular-automata domain: density, synchronization, and random number generation. Applying our statistical measures, we are able to identify a number of trends common to all three problems (which may represent intrinsic properties of the algorithm itself), as well as a host of problem-specific features. We find that the evolutionary algorithm tends to undergo a number of phases which we are able to quantitatively delimit. The results obtained lead us to believe that the measures presented herein may prove useful in the general case of analyzing fine-grained evolutionary algorithms.     

Computation of the structured stability radius via matrix sign function

Robustness of perturbed state space models of the form is considered, where B, C are given matrices, A is an asymptotically stable matrix and D is the unknown perturbation matrix. An efficient algorithm to compute the complex structured stability radius, which is based on the properties of the matrix sign function, is presented. A comparison with previous algorithms shows the efficiency of the new algorithm     

一种处于任意时延非线性动态网络中的时钟振荡器快速平均同步算法

研究了处于任意时延非线性动态网络中的时钟振荡器的同步问题. 首先, 提出了一种基于一致性控制策略的动态同步算法, 即快速平均同步算法(FASA)来找到同步解. 该算法能够补偿时钟节点间的时钟偏移和时钟偏差, 使得和以前的同步方法比较后在较短的时间内实现时钟节点的同步. 其次, 由于FASA的动态特性, 我们从具有任意时延的分割动态系统角度来刻画这个算法. 该算法保证在动态网络中的所有时钟节点收敛到李亚普诺夫稳定平衡点. 最后, 数值仿真和实验结果证明了FASA的正确性和有效性, 这意味着时钟节点能达到全局一致, 并且使同步误差精度达到纳秒级别.     

一种改进的OFDM符号定时同步算法

针对先前一些算法存在定时模糊以及干扰峰峰值较大的问题,提出了一种改进的OFDM符号定时同步算法。分析了先前算法问题产生的根源,设计了两种同时具备频偏估计能力的新训练符号,并给出了相应的定时尺度函数。对新算法的定时尺度函数进行了分析,得知它的定时尺度非常尖锐,几乎不存在干扰峰,而且不受循环前缀长度的影响。仿真结果表明新算法克服了已有算法的缺点,有效地提高了定时估计的精度。当信噪比大于5dB,在加性白高斯噪声信道下定时估计的均值与方差都为零,可以实现精确的定时同步。     

QoS-driven multicast tree generation using Tabu search

Many multimedia communication applications require a source to transmit messages to multiple destinations subject to Quality-of-Service (QoS) delay constraint. The problem to be solved is to find a minimum cost multicast tree where each source to destination path is constrained by a delay bound. This problem has been proven to be NP-complete. In this paper, we present a Tabu Search (TS) algorithm to construct a minimum cost delay bounded multicast tree. The proposed algorithm is then compared with many existing multicast algorithms. Results show that on almost all test cases, TS algorithm exhibits more intelligent search of the solution subspace and is able to find better solutions than other reported multicast algorithms.     

Adaptive algorithms for the rejection of sinusoidal disturbances with unknown frequency

Two algorithms are presented for the rejection of sinusoidal disturbances with unknown frequency. The first is an indirect algorithm where the frequency of the disturbance is estimated, and the estimate is used in another adaptive algorithm that adjusts the magnitude and phase of the input needed to cancel the effect of the disturbance. A direct algorithm that uses the concept of a phase-locked loop is also presented in which frequency estimation and disturbance cancellation are performed simultaneously. Approximate analyses are presented for both schemes and the results are found useful for the selection of the design parameters. Simulations are given which demonstrate the validity of the analytical results and the ability of the algorithms to reject sinusoidal disturbances with unknown frequency. The indirect algorithm is found to have a larger capture region for the parameter estimates, whereas the direct algorithm has superior convergence properties locally about the optimum parameter estimates     

On the power of synchronization between two adjacent processes

We study the power of local computations on labelled edges (which allow two adjacent vertices to synchronize and to modify their states simultaneaously in function of their previous states) through the classical election problem. We characterize the graphs for which this problem has a solution. As corollaries we characterize graphs which admit an election algorithm for two seminal models: Angluin’s model and asynchronous systems where processes communicate with synchronous message passing (i.e., there is a synchronization between the process sending the message and the one receiving it).     

Parallel Algorithms for Discovery of Association Rules

Discovery of association rules is an important data mining task. Several parallel and sequential algorithms have been proposed in the literature to solve this problem. Almost all of these algorithms make repeated passes over the database to determine the set of frequent itemsets (a subset of database items), thus incurring high I/O overhead. In the parallel case, most algorithms perform a sum-reduction at the end of each pass to construct the global counts, also incurring high synchronization cost. In this paper we describe new parallel association mining algorithms. The algorithms use novel itemset clustering techniques to approximate the set of potentially maximal frequent itemsets. Once this set has been identified, the algorithms make use of efficient traversal techniques to generate the frequent itemsets contained in each cluster. We propose two clustering schemes based on equivalence classes and maximal hypergraph cliques, and study two lattice traversal techniques based on bottom-up and hybrid search. We use a vertical database layout to cluster related transactions together. The database is also selectively replicated so that the portion of the database needed for the computation of associations is local to each processor. After the initial set-up phase, the algorithms do not need any further communication or synchronization. The algorithms minimize I/O overheads by scanning the local database portion only twice. Once in the set-up phase, and once when processing the itemset clusters. Unlike previous parallel approaches, the algorithms use simple intersection operations to compute frequent itemsets and do not have to maintain or search complex hash structures. Our experimental testbed is a 32-processor DEC Alpha cluster inter-connected by the Memory Channel network. We present results on the performance of our algorithms on various databases, and compare it against a well known parallel algorithm. The best new algorithm outperforms it by an order of magnitude.     

Cellular automaton-based algorithms for the dispersion of mobile wireless sensor networks

Due to the advent of sensor technology and its applications, mobile wireless sensor networks (MWSNs) have gained a significant amount of research interest. In a typical MWSN, sensors can move within the network. We develop a set of probabilistic and deterministic cellular automaton (CA)-based algorithms for motion planning problems in MWSNs. First, we consider a scenario where a group of sensors are deployed and they need to disperse in order to maximise the area covered by the network. In this variant of the problem we do not explicitly consider that the sensors should maintain the connectivity of the network while they move. Second, we consider a scenario where the sensors are initially randomly distributed and they need to disperse autonomously to both maximise the coverage of the network and maintain its connectivity. We carry out extensive simulations of both deterministic and randomised variants of the algorithms. For the first variant of the problem we compare our algorithms with one previous algorithm and find that our algorithm yields better network coverage than the earlier algorithm. We also find that probabilistic algorithms have better overall performance for the second variant. CA algorithms rely only on local information about the network and, hence, they can be used in practice for MWSN problems. On the other hand, locality of the algorithm implies that maintaining connectivity becomes a non-trivial problem.     

Learning Occupancy Grid Maps with Forward Sensor Models

This article describes a new algorithm for acquiring occupancy grid maps with mobile robots. Existing occupancy grid mapping algorithms decompose the high-dimensional mapping problem into a collection of one-dimensional problems, where the occupancy of each grid cell is estimated independently. This induces conflicts that may lead to inconsistent maps, even for noise-free sensors. This article shows how to solve the mapping problem in the original, high-dimensional space, thereby maintaining all dependencies between neighboring cells. As a result, maps generated by our approach are often more accurate than those generated using traditional techniques. Our approach relies on a statistical formulation of the mapping problem using forward models. It employs the expectation maximization algorithm for searching maps that maximize the likelihood of the sensor measurements.