Nonlinear phenomena in spaces of algorithms

Nonlinear phenomena, which are so important in nature and society, are considered here in relation to the world of algorithms and computations. To have a mathematical model for this world, formal computability spaces are introduced. It is demonstrated that the traditional approach to algorithms, which is based on such popular models as Turing machines, results in linear subspaces of the computability space. Nonlinear phenomena appear when we go to the more powerful class of such super-recursive algorithms as inductive Turing machines. It is demonstrated how this nonlinearity imports much higher computing power of inductive Turing machines in comparison with conventional Turing machines. This provides a base to consider problems of chaos, emergent computations and infinity from the algorithmic point of view.     

Parametric Evaluation of Routing Algorithms in Network on Chip Architecture

Considering that routing algorithms for the Network on Chip (NoC) architecture is one of the key issues that determine its ultimate performance, several things have to be considered for developing new routing algorithms. This includes examining the strengths, capabilities, and weaknesses of the commonly proposed algorithms as a starting point for developing new ones.
Because most of the algorithms presented are based on the well-known algorithms that are studied and evaluated in this research. Finally, according to the results produced under different conditions, better decisions can be made when using the aforementioned algorithms as well as when presenting new routing algorithms. In this research, we first describe the existing algorithms include: XY, YX, Odd- Even and DyAD. We then evaluate each of the routing algorithms which naturally have their own strengths and weaknesses under different conditions. In the first scenario, based on the criteria of average latency, average throughput and average energy consumption in determining the final performance of the network on the chip, we show the algorithms in terms of their performance by deterministic and adaptive routing algorithms. In the second scenario, we evaluate the algorithms based on the network size and the number of cores on the chip. As a result, these algorithms can make better decisions when using these algorithms as well as when presenting new routing algorithms, considering the results produced under different condition.     

SeWDReSS: on the design of an application independent,secure, wide-area disaster recovery storage system

Distributed wide-area storage systems must tolerate both physical failure and logic errors. In particular, these functions are needed to enable the storage system to support remote disaster recovery. There are several solutions for distributed wide-area backup/archive systems implemented at application level, file system level or at storage subsystem level. However, they suffer from high deployment cost and security issues. Moreover, previous researches in literature only focus on any disk-related failures and ignore the fact that storage server linked predominantly to a Wide-Area-Network (WAN) which may be unavailable or owing to network failures. In this paper, we first model the efficiency and reliability of distributed wide area storage systems for all media, taking both network failures and disk failures into consideration. To provide higher performance, efficiency, reliability, and security to the wide-area disaster recovery storage systems, we present a configurable RAID-like data erasure-coding scheme referred to as Replication-based Snapshot Redundant Array of Independent Imagefiles (RSRAII). We argue that this scheme has benefits resulting from the consolidation of both erasure-coding and replication strategies. To this end, we propose a novel algorithm to improve the snapshot performance referred to as SMPDP (Snapshot based on Multi-Parallel Degree Pipeline). We also extend this study towards implementing a prototype system, called as SeWDReSS, which is shown to strike a tradeoff between reliability, storage space, security, and performance for distributed wide-area disaster recovery.     

A two stage heuristic algorithm for the integrated aircraft and crew schedule recovery problems

Airline disruptions incurred huge cost for airlines and serious inconvenience for travelers. In this paper, we study the integrated aircraft and crew schedule recovery problem. A two stage heuristic algorithm for the integrated recovery problem is proposed. In the first stage, the integrated aircraft recovery and flight-rescheduling model with partial crew consideration is built. This model is based on the traditional multi-commodity network model for the aircraft schedule recovery problem. The objective of this model also includes minimization of the original crew connection disruption. In the second stage, the integrated crew schedule recovery and flight re-scheduling model with partial aircraft consideration is built. We proposed a new multi-commodity model for the crew schedule recovery. The main advantage of such model is that it is much more efficient to integrate the flight-scheduling and aircraft consideration. New constraints are incorporated to guarantee that the aircraft connections generated in the stage 1 are still feasible. Two stages are run iteratively until no improvement can be achieved. Experimental results show that our method can provide better recovery solutions compared with the benchmark algorithms.     

Real-time data dissemination in mobile peer-to-peer networks

Mobile peer-to-peer networks have found many uses such as streaming of audio and video data. There are circumstances, such as emergency situations and disaster recovery, when real-time delivery is a fundamental requirement. The problem is challenging due to the limited network capacity, the variable transmission rates and the unpredictability with respect to the network conditions in the mobile peer-to-peer network.In this paper we address the problem of real-time data dissemination of multimedia streams in mobile peer-to-peer networks. Four routing algorithms are proposed based on a packet's deadline, priority or a combination of these metrics. They are simulated under different setups in a mobile peer-to-peer network with Bluetooth connectivity and nodes broadcasting audio and video streams using different priorities. We compare the performance of the algorithms using a number of metrics. Detailed experimental results are presented. Based on these results, propositions on the usage of the algorithms and the design of network requirements are presented.     

Unmanned Ground Vehicle Navigation in Coordinate-Free and Localization-Free Wireless Sensor and Actuator Networks

We present a set of algorithms for the navigation of Unmanned Ground Vehicles (UGVs) towards a set of pre-identified target nodes in coordinate-free and localization-free wireless sensor and actuator networks. The UGVs are equipped with a set of wireless listeners that provide sensing information about the potential field generated by the network of actuators. Two main navigation scenarios are considered: single-UGV, single-destination navigation and multi-UGV, multi-destination navigation. For the single-UGV, single-destination case, we present both centralized and distributed navigation algorithms. Both algorithms share a similar two-phase concept. In the first phase, the system assigns level numbers to individual nodes based on their hop distance from the target nodes. In the second phase, the UGV uses the potential field created by the network of actuators to move towards the target nodes, requiring cooperation between triplets of actuator nodes and the UGV. The hop distance to the target nodes is used to control the main moving direction while the potential field, which can be measured by listeners on the UGV, is used to determine the UGV’s movement. For the multi-UGV, multi-destination case, we present a decentralized allocation algorithm such that multiple UGVs avoid converging to the same destination. After each UGV determines its destination, the proposed navigation scheme is applied. The presented algorithms do not attempt to localize UGVs or sensor nodes and are therefore suitable for operating in GPS-free/denied environments. We also present a study of the communication complexity of the algorithms as well as simulation examples that verify the proposed algorithms and compare their performances.     

移动群智感知下的交通流速缺失数据恢复算法

GPS等设备的普及使得基于大规模车辆数据的城市级道路状态评估成为可能,本文研究移动群智感知下的交通流速缺失数据恢复问题.首先,利用探测车收集车辆数据,设计了基于网格密度提取路网的方法;其次,针对GPS数据特点设计一种自适应的路段流速计算方法,得到交通流速矩阵;再次,对交通状况评估时存在的数据缺失情形进行分类,基于数据时...     

Joint timing recovery and decoding algorithms for non-binary LDPC coded systems

In this paper, we present two joint timing recovery and decoding algorithms for non-binary low-density parity-check (LDPC) coded systems. To estimate the timing offset, the first algorithm utilizes the percentage of the satisfied check nodes (SCNs), while the second algorithm utilizes the soft decision metrics (SDMs). Both SCNs and SDMs are fed back from the LDPC decoder, which can be implemented by either the well-known q-ary sum-product algorithm (QSPA) or other low complexity algorithms, such as the X-EMS algorithms. Simulation results show that the proposed algorithms suffer from a little performance degradation compared with the perfect timing system. Simulation results also show that X-EMS algorithms aided by the timing recovery algorithm using SDMs outperform QSPA aided by the timing recovery algorithm using SCNs, but with a much lower complexity. This implies that the performance is mainly affected by the timing recovery algorithms.     

New nonleast-squares neural network learning algorithms forhypothesis testing

Hypothesis testing is a collective name for problems such as classification, detection, and pattern recognition. In this paper we propose two new classes of supervised learning algorithms for feedforward, binary-output neural network structures whose objective is hypothesis testing. All the algorithms are applications of stochastic approximation and are guaranteed to provide optimization with probability one. The first class of algorithms follows the Neyman-Pearson approach and maximizes the probability of detection, subject to a given false alarm constraint. These algorithms produce layer-by-layer optimal Neyman-Pearson designs. The second class of algorithms minimizes the probability of error and leads to layer-by-layer Bayes optimal designs. Deviating from the layer-by-layer optimization assumption, we propose more powerful learning techniques which unify, in some sense, the already existing algorithms. The proposed algorithms were implemented and tested on a simulated hypothesis testing problem. Backpropagation and perceptron learning were also included in the comparisons.     

Dual modularity optimization for detecting overlapping communities in bipartite networks

Many algorithms have been designed to discover community structure in networks. These algorithms are mostly dedicated to detecting disjoint communities. Very few of them are intended to discover overlapping communities, particularly the bipartite networks have hardly been explored for the detection of such communities. In this paper, we describe a new approach which consists in forming overlapping mixed communities in a bipartite network based on dual optimization of modularity. To this end, we propose two algorithms. The first one is an evolutionary algorithm dedicated for global optimization of the Newman’s modularity on the line graph. This algorithm has been tested on well-known real benchmark networks and compared with several other existing methods of community detection in networks. The second one is an algorithm that locally optimizes the graph Mancoridis modularity, and we have adapted to a bipartite graph. Specifically, this second algorithm is applied to the decomposition of vertices, resulting from the evolutionary process, and also characterizes the overlapping communities taking into account their semantic aspect. Our approach requires a priori no knowledge on the number of communities searched in the network. We show its interest on two datasets, namely, a group of synthetic networks and real-world network whose structure is also difficult to understand.     

Wrapper positive Bayesian network classifiers

In the information retrieval framework, there are problems where the goal is to recover objects of a particular class from big sets of unlabelled objects. In some of these problems, only examples from the class we want to recover are available. For such problems, the machine learning community has developed algorithms that are able to learn binary classifiers in the absence of negative examples. Among them, we can find the positive Bayesian network classifiers, algorithms that induce Bayesian network classifiers from positive and unlabelled examples. The main drawback of these algorithms is that they require some previous knowledge about the a priori probability distribution of the class. In this paper, we propose a wrapper approach to tackle the learning when no such information is available, setting this probability at the optimal value in terms of the recovery of positive examples. The evaluation of classifiers in positive unlabelled learning problems is a non-trivial question. We have also worked on this problem, and we have proposed a new guiding metric to be used in the search for the optimal a priori probability of the positive class that we have called the pseudo F. We have empirically tested the proposed metric and the wrapper classifiers on both synthetic and real-life datasets. The results obtained in this empirical comparison show that the wrapper Bayesian network classifiers provide competitive results, particularly when the actual a priori probability of the positive class is high.     

Two regularizers for recursive least squared algorithms infeedforward multilayered neural networks

Recursive least squares (RLS)-based algorithms are a class of fast online training algorithms for feedforward multilayered neural networks (FMNNs). Though the standard RLS algorithm has an implicit weight decay term in its energy function, the weight decay effect decreases linearly as the number of learning epochs increases, thus rendering a diminishing weight decay effect as training progresses. In this paper, we derive two modified RLS algorithms to tackle this problem. In the first algorithm, namely, the true weight decay RLS (TWDRLS) algorithm, we consider a modified energy function whereby the weight decay effect remains constant, irrespective of the number of learning epochs. The second version, the input perturbation RLS (IPRLS) algorithm, is derived by requiring robustness in its prediction performance to input perturbations. Simulation results show that both algorithms improve the generalization capability of the trained network.     

一种实用、高效的虚拟远程超级计算环境

远程计算是指用户在本地计算机上通过互联网利用远程超级计算机上计算资源的技术.传统的远程计算方式是用户通过telnet协议登录到远程机器上完成各项任务.这种方式在高速、稳定的网络环境下效率是很高的.但是当网络条件比较差时,如在低带宽、不稳定的网络上,这种方式会严重影响用户的工作效率.提出并实现了一个远程虚拟计算环境,它所采用的计算方式可有效完成在低带宽、不稳定的网络环境下效率较低甚至无法完成的远程计算,其中使用了如检查点设置/恢复、压缩传送、目录树传送等技术以达到尽量减少网络流量的目的.实践证明,这在我国当前的网络条件下是一种高效的远程计算方法.     

Automatic design of fuzzy logic controllers for medium access control in wireless body area networks – An evolutionary approach

Soft computing techniques including fuzzy logic have been successfully applied to wireless body area networks (WBANs). However, most of the existing research works rely on manual design of the fuzzy logic controller (FLC). To address this issue, in this paper, we propose an evolutionary approach to automate the design of FLCs for cross layer medium access control in WBANs. With the goal of improving network reliability while keeping the communication delay at a low level, we have particularly studied the usefulness of three coding schemes with different levels of flexibility during the evolutionary design process. The influence of fitness functions that measure the effectiveness of each possible FLC design has also been examined carefully in order to achieve a good balance between reliability and performance. Moreover, we have utilised surrogate models to improve the efficiency of the design process. In consideration of practical usefulness, we have further identified two main design targets. The first target is to design effective FLCs for a specific network configuration. The second target focuses on designing FLCs to function across a wide range of network settings. In order to examine the usefulness of our design approach, we have utilised two widely used evolutionary algorithms, i.e. particle swarm optimisation (PSO) and differential evolution (DE). The FLC designed by our approach is also shown to outperform some related algorithms as well as the IEEE 802.15.4 standard.     

Recoverable file system for microprocessor systems

Initiation of recovery procedures, after a system failure, cannot always be expected from the users of microprocessor systems. Automatic recovery is required after system startup from a failure. The paper proposes a simple file store design such that the integrity of data is assured and the loss of data is minimized after a system failure. The concepts of check-point and shadow-page mechanisms used in databases are adopted to achieve recovery in microprocessor systems. The overhead involved in such a file system is also discussed.     

Circuit-switched broadcasting in torus networks

In this paper we present three broadcast algorithms and lower bounds on the three main components of the broadcast time for 2-dimensional torus networks (wrap-around meshes) that use synchronous circuit-switched routing. The first algorithm is based on a recursive tiling of a torus and is optimal in terms of both phases and intermediate switch settings when the start-up time to initiate message transmissions is the dominant cost. It is the first broadcast algorithm to match the lower bound of log₅ N on number of phases (where N is the number of nodes). The second and third algorithms are hybrids which combine circuit-switching with the pipelining and arc-disjoint spanning trees techniques that are commonly used to speed up store-and-forward routing. When the propagation time of messages through the network is significant, our hybrid algorithms achieve close to optimal performance in terms of phases, intermediate switch settings, and total transmission time. They are the first algorithms to achieve this performance in terms of all three parameters simultaneously     

An ant colony optimization algorithm for continuous optimization: application to feed-forward neural network training

Ant colony optimization (ACO) is an optimization technique that was inspired by the foraging behaviour of real ant colonies. Originally, the method was introduced for the application to discrete optimization problems. Recently we proposed a first ACO variant for continuous optimization. In this work we choose the training of feed-forward neural networks for pattern classification as a test case for this algorithm. In addition, we propose hybrid algorithm variants that incorporate short runs of classical gradient techniques such as backpropagation. For evaluating our algorithms we apply them to classification problems from the medical field, and compare the results to some basic algorithms from the literature. The results show, first, that the best of our algorithms are comparable to gradient-based algorithms for neural network training, and second, that our algorithms compare favorably with a basic genetic algorithm.

Learning to classify parallel input/output access patterns

Input/output performance on current parallel file systems is sensitive to a good match of application access patterns to file system capabilities. Automatic input/output access pattern classification can determine application access patterns at execution time, guiding adaptive file system policies. In this paper, we examine and compare two novel input/output access pattern classification methods based on learning algorithms. The first approach uses a feedforward neural network previously trained on access pattern benchmarks to generate qualitative classifications. The second approach uses hidden Markov models trained on access patterns from previous executions to create a probabilistic model of input/output accesses. In a parallel application, access patterns can be recognized at the level of each local thread or as the global interleaving of all application threads. Classification of patterns at both levels is important for parallel file system performance; we propose a method for forming global classifications from local classifications. We present results from parallel and sequential benchmarks and applications that demonstrate the viability of this approach.     

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.     

On basic properties of fault-tolerant multi-topology routing

Multi-topology routing has recently gained popularity as a simple yet efficient traffic engineering concept. Its basic purpose is to separate different classes of network traffic, which are then transported over disjoint logical topologies. Multi-topology routing is used as a basis for implementation of an IP fast reroute scheme called Multiple Routing Configurations (MRC).MRC has a range of attractive properties, but they do come at a cost. In order to guarantee recovery from any single link or node failure in the network, MRC has to maintain several logical topologies and thus an increased amount of routing information. The number of the logical topologies in MRC need not be large; even simple heuristic algorithms often yield good results in practice. However, why this is the case is not fully understood yet.In this paper, we introduce a theoretical framework for fault-tolerant multi-topology routing (FT-MTR). MRC is a practical implementation of FT-MTR in connectionless IP networks. We use FT-MTR to study how the internal topological structure of the communication network relates to two important problems. The first problem is minimizing the number of logical topologies and thus the routing state in FT-MTR. We show how to use the sets of nodes that separate the topology graph to devise an advanced heuristic for “intelligent” construction of the logical topologies. Finding the separating sets in a topology graph is computationally demanding; we present an algorithm that performs well in tested real network topologies. We evaluate the separation-set based heuristic for the logical topology construction and show that it outperforms the known MRC heuristics.The second problem is the FT-MTR load distribution after a failure. We use the separating sets to devise a novel algorithm for failure load distribution. This algorithm does not require knowledge of the traffic demand matrix, still, our tests indicate that it performs as good as, or better than, known MRC load-distribution algorithms that do require the demand matrix as input.