This paper addresses linear quadratic control with state-dependent noise for singularly perturbed stochastic systems (SPSS). First, the asymptotic structure of the stochastic algebraic Riccati equation (SARE) is established for two cases. Second, a new iterative algorithm that combines Newton's method with the fixed point algorithm is established. As a result, the quadratic convergence and the reduced-order computation in the same dimension of the subsystem are attained. As another important feature, a high-order state feedback controller that uses the obtained iterative solution is given and the degradation of the cost performance is investigated for the stochastic case for the first time. Furthermore, the parameter independent controller is also given in case the singular perturbation is unknown. Finally, in order to demonstrate the efficiency of the proposed algorithm, a numerical example is given for the practical megawatt-frequency control problem.

Bloom filters are widely used for various network applications. Because of the limited size of on-chip memory and the large volume of network traffic, Bloom filters are often required to update their contents incrementally. Two techniques have been used for this purpose: cold cache and double buffering. Cold cache outperforms double buffering in terms of the average cache ratio. However, double buffering works much better than cold cache for the worst-case cache hit ratio. In this paper, we propose a new updating scheme for Bloom filters, which updates the contents of Bloom filter incrementally while the assigned memory space is fully utilized. The proposed scheme works better than cold cache in terms of the average cache hit ratio. At the same time, it outperforms double buffering for the worst-case cache hit ratio.

Recently multi-car elevator (MCE) consisting of several elevator cars in a single elevator shaft received great interest as transportation systems for high-rise buildings. Algorithms for efficiently controlling elevator cars are necessary to put MCEs to practical use. We propose an algorithm for controlling MCEs to reduce passenger-waiting time. A feature of our algorithm is the introduction of a simple function estimating efficiency of passenger transport and a procedure checking assignability of a car. We evaluate the performance of our algorithm using a simulation and show that it performs better compared with a previous algorithm.

The minimum initial marking problem of Petri nets (MIM) is defined as follows: "Given a Petri net and a firing count vector X, find an initial marking M0, with the minimum total token number, for which there is a sequence δ of transitions such that each transition t appears exactly X(t) times in δ, the first transition is enabled at M0 and the rest can be fired one by one subsequently." In a production system like factory automation, economical distribution of initial resources, from which a schedule of job-processings is executable, can be formulated as MIM. AAD is known to produce best solutions among existing algorithms. Although solutions by AMIM+ is worse than those by AAD, it is known that AMIM+ is very fast. This paper proposes new heuristic algorithms AADO and AMDLO, improved versions of existing algorithms AAD and AMIM+, respectively. Sharpness of solutions or short CPU time is the main target of AADO or AMDLO, respectively. It is shown, based on computing experiment, that the average total number of tokens in initial markings by AADO is about 5.15% less than that by AAD, and the average CPU time by AADO is about 17.3% of that by AAD. AMDLO produces solutions that are slightly worse than those by AAD, while they are about 10.4% better than those by AMIM+. Although CPU time of AMDLO is about 180 times that of AMIM+, it is still fast: average CPU time of AMDLO is about 2.33% of that of AAD. Generally it is observed that solutions get worse as the sizes of input instances increase, and this is the case with AAD and AMIM+. This undesirable tendency is greatly improved in AADO and AMDLO.

In this paper, we propose a low-complexity, high-efficiency two-dimensional look-up table (2D LUT) for carrying out the sum-product algorithm in the decoding of low-density parity-check (LDPC) codes. Instead of employing adders for the core operation when updating check node messages, in the proposed scheme, the main term and correction factor of the core operation are successfully merged into a compact 2D LUT. Simulation results indicate that the proposed 2D LUT not only attains close-to-optimal bit error rate performance but also enjoys a low complexity advantage that is suitable for hardware implementation.

The algebra of communicating shared resources (ACSR) is a timed process algebra which extends classical process algebras with the notion of a resource. In analyzing ACSR models, the existing techniques such as bisimulation checking and Hennessy-Milner Logic (HML) model checking are very important in theory of ACSR, but they are difficult to use for large complex system models in practice. In this paper, we suggest a framework to verify ACSR models against their requirements described in an expressive timed temporal logic. We demonstrate the usefulness of our approach with a real world case study.

This paper considers the problem of target location estimation in heterogeneous wireless sensor networks and proposes a novel algorithm using a factor graph to fuse the heterogeneous measured data. In the proposed algorithm, we map the problem of target location estimation to a factor graph framework and then use the sum-product algorithm to fuse the heterogeneous measured data so that heterogeneous sensors can collaborate to improve the accuracy of target location estimation. Simulation results indicate that the proposed algorithm provides high location estimation accuracy.

The ratio of two probability densities is called the importance and its estimation has gathered a great deal of attention these days since the importance can be used for various data processing purposes. In this paper, we propose a new importance estimation method using Gaussian mixture models (GMMs). Our method is an extention of the Kullback-Leibler importance estimation procedure (KLIEP), an importance estimation method using linear or kernel models. An advantage of GMMs is that covariance matrices can also be learned through an expectation-maximization procedure, so the proposed method--which we call the Gaussian mixture KLIEP (GM-KLIEP)--is expected to work well when the true importance function has high correlation. Through experiments, we show the validity of the proposed approach.

The multiobjective route selection problem (m-RSP) is a key research topic in the car navigation system (CNS) for ITS (Intelligent Transportation System). In this paper, we propose an interactive multistage weight-based Dijkstra genetic algorithm (mwD-GA) to solve it. The purpose of the proposed approach is to create enough Pareto-optimal routes with good distribution for the car driver depending on his/her preference. At the same time, the routes can be recalculated according to the driver's preferences by the multistage framework proposed. In the solution approach proposed, the accurate route searching ability of the Dijkstra algorithm and the exploration ability of the Genetic algorithm (GA) are effectively combined together for solving the m-RSP problems. Solutions provided by the proposed approach are compared with the current research to show the effectiveness and practicability of the solution approach proposed.

In this letter we show that the dynamic optimal PCID allocation problem in LTE systems is NP-complete. Subsequently we provide a near-optimal solution using SON which models the problem using new merge operations and explores the search space using a suitable randomized algorithmic approach. Two feasible options for dynamic auto-configuration of the system are also discussed. Simulation results point out that the approach provides near-optimal auto-configuration of PCIDs in computationally feasible time.

It is known that Boolean functions used in stream ciphers should have good cryptographic properties to resist fast algebraic attacks. In this paper, we study a new class of Boolean functions with good cryptographic properties: balancedness, optimum algebraic degree, optimum algebraic immunity and a high nonlinearity.

Scheduling algorithms are crucial in radio resource management especially for multimedia networks. Many scheduling algorithms are based on the assumption of error-free connections, which is not suitable for wireless networks. Therefore, a scheduling algorithm based on the modification of Static Priority (SP) algorithm and Earliest-Due-Date (EDD) algorithm is proposed for wireless multimedia networks with link adaptation in this paper. In the proposed algorithm, various quality of service requirements, such as delay, throughput, and packet loss ratio, are considered. Particularly, the influence of error tolerance of voice communications, which is usually ignored in most scheduling algorithms, is taken into account. Simulation results show that the proposed algorithm, compared with SP, EDD, and other scheduling algorithms, succeeds in meeting the delay and packet loss ratio (PLR) requirements at much heavier traffic load.

This paper describes a novel algorithm for approximate nearest neighbor searching. For solving this problem especially in high dimensional spaces, one of the best-known algorithm is Locality-Sensitive Hashing (LSH). This paper presents a variant of the LSH algorithm that outperforms previously proposed methods when the dataset consists of vectors normalized to unit length, which is often the case in pattern recognition. The LSH scheme is based on a family of hash functions that preserves the locality of points. This paper points out that for our special case problem we can design efficient hash functions that map a point on the hypersphere into the closest vertex of the randomly rotated regular polytope. The computational analysis confirmed that the proposed method could improve the exponent ρ, the main indicator of the performance of the LSH algorithm. The practical experiments also supported the efficiency of our algorithm both in time and in space.

This paper proposes a robust adaptive fuzzy PID control scheme augmented with a supervisory controller for unknown systems. In this scheme, a generalized fuzzy model is used to describe a class of unknown systems. The control strategy allows each part of the control law, i.e., a supervisory controller, a compensator, and an adaptive fuzzy PID controller, to be designed incrementally according to different guidelines. The supervisory controller in the outer loop aims at enhancing system robustness in the face of extra disturbances, variation in system parameters, and parameter drift in the adaptation law. Furthermore, an H∞ control design method using the fuzzy Lyapunov function is presented for the design of the initial control gains that guarantees transient performance at the start of closed-loop control, which is generally overlooked in many adaptive control systems. This design of the initial control gains is a compound search strategy called conditional linear matrix inequality (CLMI) approach with IROA (Improved random optimal algorithm), it leads to less complex designs than a standard LMI method by fuzzy Lyapunov function. Numerical studies of the tracking control of an uncertain inverted pendulum system demonstrate the effectiveness of the control strategy. From results of this simulation, the generalized fuzzy model reduces the rule number of T-S fuzzy model indeed.

To achieve an automated implementation for the application-specific heterogeneous multiprocessor systems-on-chip (MPSoC), partitioning and mapping the sequential programs onto multiple parallel processors is one of the most difficult challenges. However, the existing traditional parallelizing techniques cannot solve the MPSoC-related problems effectively, so designers are still required to manually extract the concurrency potentials in the program. To solve this bottleneck, an automated application partition technique is needed. However, completely automatic parallelism is ineffective, so it is promising to explore concurrency for certain practical special structures. To settle those issues, this paper proposes a template-based algorithm to automatically partition a special load-compute-store (LCS) loop structure. Since specific-instruction customization for the application specific instruction-set processors (ASIPs) has interactions with task partitioning, the proposed algorithm integrates the dynamic pipelining and ASIP techniques using an iterative improvement strategy: first, an initial pipelining scheme is generated to obtain the maximum parallelism; second, under the primary partition results specific instructions are customized respectively for each subprogram; third, the program is repartitioned via pipelining under the specific instruction configurations. The proposed method has been implemented in the context of a commercial extensible multiprocessor design flow, using the Xtensa-based XTMP platform from Tensilica Inc. Based on a case study of Fast Fourier Transform (FFT), the experimental results indicate that the partitioned programs by the proposed method demonstrate an average speedup of 10 compared to the original sequential programs which have not been partitioned and run on the uniprocessor system.

Generalized quasi-cyclic (GQC) codes form a wide and useful class of linear codes that includes thoroughly quasi-cyclic codes, finite geometry (FG) low density parity check (LDPC) codes, and Hermitian codes. Although it is known that the systematic encoding of GQC codes is equivalent to the division algorithm in the theory of Grobner basis of modules, there has been no algorithm that computes Grobner basis for all types of GQC codes. In this paper, we propose two algorithms to compute Grobner basis for GQC codes from their parity check matrices; we call them echelon canonical form algorithm and transpose algorithm. Both algorithms require sufficiently small number of finite-field operations with the order of the third power of code-length. Each algorithm has its own characteristic. The first algorithm is composed of elementary methods and is appropriate for low-rate codes. The second algorithm is based on a novel formula and has smaller computational complexity than the first one for high-rate codes with the number of orbits (cyclic parts) less than half of the code length. Moreover, we show that a serial-in serial-out encoder architecture for FG LDPC codes is composed of linear feedback shift registers with the size of the linear order of code-length; to encode a binary codeword of length n, it takes less than 2n adder and 2n memory elements.

Research of the shortest path problem in time-dependent networks has important practical value. An improved pheromone update strategy suitable for time-dependent networks was proposed. Under this strategy, the residual pheromone of each road can accurately reflect the change of weighted value of each road. An improved selection strategy between adjacent cities was used to compute the cities' transfer probabilities, as a result, the amount of calculation is greatly reduced. To avoid the algorithm converging to the local optimal solution, the ant colony algorithm was combined with genetic algorithm. In this way, the solutions after each traversal were used as the initial species to carry out single-point crossover. An improved ant colony algorithm for the shortest path problem in time-dependent networks based on these improved strategies was presented. The simulation results show that the improved algorithm has greater probability to get the global optimal solution, and the convergence rate of algorithm is better than traditional ant colony algorithm.

The purpose of the online graph exploration problem is to visit all the nodes of a given graph and come back to the starting node with the minimum total traverse cost. However, unlike the classical Traveling Salesperson Problem, information of the graph is given online. When an online algorithm (called a searcher) visits a node v, then it learns information on nodes and edges adjacent to v. The searcher must decide which node to visit next depending on partial and incomplete information of the graph that it has gained in its searching process. The goodness of the algorithm is evaluated by the competitive analysis. If input graphs to be explored are restricted to trees, the depth-first search always returns an optimal tour. However, if graphs have cycles, the problem is non-trivial. In this paper we consider two simple cases. First, we treat the problem on simple cycles. Recently, Asahiro et al. proved that there is a 1.5-competitive online algorithm, while no online algorithm can be (1.25-ε)-competitive for any positive constant ε. In this paper, we give an optimal online algorithm for this problem; namely, we give a (1.366)-competitive algorithm, and prove that there is no (-ε)-competitive algorithm for any positive constant ε. Furthermore, we consider the problem on unweighted graphs. We also give an optimal result; namely we give a 2-competitive algorithm and prove that there is no (2-ε)-competitive online algorithm for any positive constant ε.

In this paper, we present a low complexity, yet accurate adaptive algorithm for the tracking of two-dimensional (2-D) direction of arrival (DOAs) based on a uniform rectangular array (URA). The new algorithm is a novel hybrid of tracking and beamforming processes by making use of three stages of one-dimensional (1-D) DOA tracking algorithms -- in a hierarchical tree structure -- to determine the two DOA components iteratively in a coarse-fine manner. In between every other 1-D DOA tracking algorithm, a complementary orthogonal beamforming process is invoked to partition the incoming signals into appropriate groups to enhance the tracking accuracy. Since the new algorithm only involves the 1-D subspace-based DOA tracking algorithm, the overall complexity is substantially less than the direct two-dimensional (2-D) extension of the existing 1-D DOA tracking algorithms, which requires an update of higher-dimensional vectors followed by a higher-dimensional eigendecomposition or a 2-D search. Furthermore, with the tree-structured DOA tracking scheme, the tracked 2-D DOA components are automatically paired without extra computational overhead. Furnished simulations show that the new algorithm can provide satisfactory tracking performance in various scenarios.

This paper proposes a new sieving algorithm that employs a bucket sort as a part of a factoring algorithm such as the number field sieve. The sieving step requires an enormous number of memory updates; however, these updates usually cause cache hit misses. The proposed algorithm significantly reduces the number of cache hit misses when the size of the sieving region is roughly less than the square of the cache size, and the memory updates are several times faster than the straightforward implementation according to the PC experiments.