In our previous work, the hyper H∞ filter is developed for tracking of unknown time-varying systems. Additionally, a fast algorithm, called the fast H∞ filter, of the hyper H∞ filter is derived on condition that the observation matrix has a shifting property. This algorithm has a computational complexity of O(N) where N is the dimension of the state vector. However, there still remains a possibility of deriving alternative forms of the hyper H∞ filter. In this work, a fast J-unitary form of the hyper H∞ filter is derived, providing a new H∞ fast algorithm, called the J-fast H∞ filter. The J-fast H∞ filter possesses a computational complexity of O(N), and the resulting algorithm is very amenable to parallel processing. The validity and performance of the derived algorithm are confirmed by computer simulations.
Dan WANG Li PING Xiao Yu HU Xin Mei WANG
A fast decoding algorithm for low-density parity-check codes is presented based on graph decomposition and two-way message passing schedule. Simulations show that the convergence speed of the proposed algorithm is about twice that of the conventional belief propagation algorithm.
In order to simultaneously combat both of the inter-carrier interferences (ICIs) and multiple access interferences (MAIs) to achieve reliable performance in multi-carrier code division multiple access (MC-CDMA) systems, this letter proposes a maximum likelihood based scheme for joint frequency offset estimation and multiuser symbol detection. To reduce the computational complexity called for by the joint decision statistic without extra mechanisms, the genetic algorithm (GA) is employed to solve the nonlinear optimization involved. Due to the robustness of the GA, the joint decision statistic can be efficiently solved, and, as shown by furnished simulation results, the proposed approach can offer satisfactory performance in various scenarios.
Satoshi TAOKA Masahiro YAMAUCHI Toshimasa WATANABE
The minimum initial marking problem MIM of Petri nets is described 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." This paper proposes two heuristic algorithms AAD and AMIM + and shows the following (1) and (2) through experimental results: (1) AAD is more capable than any other known algorithm; (2) AMIM + can produce M0, with a small number of tokens, even if other algorithms are too slow to compute M0 as the size of an input instance gets very large.
In the letter, the fast one-dimensional (1-D) and two-dimensional (2-D) algorithms for realizing low-complexity 44 discrete cosine transform (DCT) for H.264 applications are developed. Through applying matrix utilizations with Kronecker product and direct sum, the efficient fast 2-D 44 DCT algorithm can be developed from the proposed fast 1-D 44 DCT algorithm by matrix decompositions. The fast 1-D and 2-D low-complexity 44 DCT algorithms requires fewer multiplications and additions than other fast DCT algorithms. Owing to regular modularity, the proposed fast algorithms can achieve real-time H.264 video signal processing with VLSI implementation.
Shyue-Horng SHIAU Chang-Biau YANG
Given a set of n stations, the initialization problem is to assign each station a unique identification number, from 1 to n. In the single-hop wireless Networks with collision detection, Nakano and Olariu proposed an algorithm to build a partition tree and solve the problem. In this paper, we shall classify the partition tree into four parts. By reviewing the classification, we find that three ideas can improve the algorithm. We show that it needs 2.88n time slots for solving the problem containing n stations. After applying our three ideas, the number of time slots will be improved to 2.46n.
To cut down the sidelobe level of radiation pattern, a novel adaptive algorithm is proposed for electronic steering parasitic antenna. The composite objective function in this algorithm takes both directivity and sidelobe level of pattern into account, and the steepest gradient algorithm is selected to search the optimum value of reactive load. Simulations are carried out to validate the algorithm, simulated results show that the levels of sidelobe are both below -4 dB in different beamforming cases, and the front to back ratios are better than 10 dB.
Katsumi SAKAKIBARA Shogo CHIKADA Jiro YAMAKITA
Most of analytical models proposed so far for the IEEE 802.11 distributed coordination function (DCF) focus on saturation performance. In this paper, we develop an analytic model for unsaturation performance evaluation of the IEEE 802.11 DCF with and without slow contention window decrease (SCWD). The model explicitly takes into account the carrier sensing mechanism and an additional backoff interval after successful frame transmission, both of which can be ignored under saturation conditions. Expressions are derived for throughput and delay characteristics by means of the equilibrium point analysis. The accuracy of our model is validated through computer simulation. Numerical results based on the IEEE 802.11b with CCK show that the SCWD can stably achieve approximately 20% performance gain over the normal 802.11 DCF under unsaturation conditions as well as saturation ones.
We propose a learning method combining query learning and a "genetic translator" we previously developed. Query learning is a useful technique for high-accuracy, high-speed learning and reduction of training sample size. However, it has not been applied to practical optical character readers (OCRs) because human beings cannot recognize queries as character images in the feature space used in practical OCR devices. We previously proposed a character image reconstruction method using a genetic algorithm. This method is applied as a "translator" from feature space for query learning of character recognition. The results of an experiment with hand-written numeral recognition show the possibility of training sample size reduction.
Golam SORWAR Manzur MURSHED Laurence DOOLEY
Though block-based motion estimation techniques are primarily designed for video coding applications, they are increasingly being used in other video analysis applications due to their simplicity and ease of implementation. The major drawback associated with these techniques is that noises, in the form of false motion vectors, cannot be avoided while capturing block motion vectors. Similar noises may further be introduced when the technique of global motion compensation is applied to obtain true object motion from video sequences where both the camera and object motions are present. This paper presents a new technique for capturing large number of true object motion vectors by eliminating the false motion vector fields, for use in the application of object motion based video indexing and retrieval applications. Experimental results prove that our proposed technique significantly increases the percentage of retained true object motion vectors while eliminating all false motion vectors for variety of standard and non-standard video sequences.
Sang-Moon SOAK David CORNE Byung-Ha AHN
A novel evolutionary algorithm is described for designing the topology of spanning tree-based communication networks. Two specific performance objectives are dealt with: the optimum communication spanning tree problem (OCSTP), and the quadratic minimum spanning tree problem (q-MST). Improved network performance is reliably obtained when using the proposed algorithm on accepted benchmark instances, in comparison with the previous best-known approaches. The same methodology can be applied straightforwardly to the design of communication networks with other objectives.
Tomohiro HACHINO Hitoshi TAKATA
This paper presents a novel method of structure selection and identification for Hammerstein type nonlinear systems. An unknown nonlinear static part to be estimated is approximately represented by an automatic choosing function (ACF) model. The connection coefficients of the ACF and the system parameters of the linear dynamic part are estimated by the linear least-squares method. The adjusting parameters for the ACF model structure, i.e. the number and widths of the subdomains and the shape of the ACF are properly selected by using a genetic algorithm, in which the Akaike information criterion is utilized as the fitness value function. The effectiveness of the proposed method is confirmed through numerical experiments.
Anycast refers to the transmission of data from a source node to (any) one member in the group of designed recipients in a network. When the physical network and the set of anycast requests are given, the Anycast Routing and Wavelength Assignment (ARWA) problem is to find a set of light-paths, one for each source, for anycasting messages to any one of the member in the anycast destination group such that not any path using the same wavelength passes through the same link. The goal of the ARWA problem is to minimize the number of used wavelengths. In this paper, the ARWA problem is formulated and studied; since ARWA problem is NP-hard, a three-phase genetic algorithm is proposed to solve it. This algorithm is used to find the close-to-optimal solution. Simulated results show that the proposed algorithm is able to achieve good performance.
Satosi KATO Hidetosi OKAMOTO Toyofumi TAKENAKA
We propose a novel routing algorithm for reverse proxy servers, called load balancing content address hashing (LB-CAH), and evaluate the performance of the proposed routing algorithm compared with that of the content address hashing (CAH) and the hash and slide (HAS) routing algorithms. The proposed LB-CAH routing algorithm calculates the popularity of pages in the load balancer using an LFU caching technique and periodically makes a popularity list. Using this popularity list, the proposed routing algorithm selects a reverse proxy server as follows. When the requested page appears in the popularity list, the request is routed according to the round robin method; otherwise, it is routed according to the content address hashing method. We evaluate and compare the LB-CAH, CAH and HAS routing algorithms by simulation experiments from the viewpoints of load balancing, consumed cache space and cache hit rate. Simulation experiments show that the proposed LB-CAH routing algorithm achieves almost the same degree of load balancing as the HAS algorithm and the same cache hit rate as the CAH algorithm for reverse proxy servers in various web site environments.
Vinh Trong LE Xiaohong JIANG Son Hong NGO Susumu HORIGUCHI
Genetic Algorithms (GA) provide an attractive approach to solving the challenging problem of dynamic routing and wavelength assignment (RWA) in optical Wavelength Division Multiplexing (WDM) networks, because they usually achieve a significantly low blocking probability. Available GA-based dynamic RWA algorithms were designed mainly for WDM networks with a wavelength continuity constraint, and they cannot be applied directly to WDM networks with wavelength conversion capability. Furthermore, the available GA-based dynamic RWA algorithms suffer from the problem of requiring a very time consuming process to generate the first population of routes for a request, which may results in a significantly large delay in path setup. In this paper, we study the dynamic RWA problem in WDM networks with sparse wavelength conversion and propose a novel hybrid algorithm for it based on the combination of mobile agents technique and GA. By keeping a suitable number of mobile agents in the network to cooperatively explore the network states and continuously update the routing tables, the new hybrid algorithm can promptly determine the first population of routes for a new request based on the routing table of its source node, without requiring the time consuming process associated with current GA-based dynamic RWA algorithms. To achieve a good load balance in WDM networks with sparse wavelength conversion, we adopt in our hybrid algorithm a new reproduction scheme and a new fitness function that simultaneously takes into account the path length, number of free wavelengths, and wavelength conversion capability in route selection. Our new hybrid algorithm achieves a better load balance and results in a significantly lower blocking probability than does the Fixed-Alternate routing algorithm, both for optical networks with sparse and full-range wavelength converters and for optical networks with sparse and limited-range wavelength converters. This was verified by an extensive simulation study on the ns-2 network simulator and two typical network topologies. The ability to guarantee both a low blocking probability and a small setup delay makes the new hybrid dynamic RWA algorithm very attractive for current optical circuit switching networks and also for the next generation optical burst switching networks.
Seok-Cheol CHANG Joung-Il YUN Ju-Sang LEE Sang-Uk LEE Nitaigour-Premchand MAHALIK Byung-Ha AHN
Over the past few years, a considerable number of studies have been conducted on modeling the bargaining game using artificial agents on within-model interaction. However, very few attempts have been made at study on the interaction and co-evolutionary process among heterogeneous artificial agents. Therefore, we present two kinds of artificial agents, based on genetic algorithm (GA) and reinforcement learning (RL), which play a game on between-model interaction. We investigate their co-evolutionary processes and analyze their parameters using the analysis of variance.
ChenGuang ZHOU Kui MENG ZuLian QIU
This paper present three characteristic functions which can express the luminance distribute characteristic much better. Based on these functions a region classification algorithm is presented. The algorithm can offer more information on regions' similarity and greatly improve the efficiency and performance of match seeking in fractal coding. It can be widely applied to many kinds of fractal coding algorithms. Analysis and experimental results proved that it can offer more information on luminance distribute characteristics among regions and greatly improve the decoding quality and compression ratio with holding the running speed.
Ji-Bum KIM Kyung-Ho SOHN Chung-Ha KOH Young-Yong KIM
In this letter, we propose an efficient transmission slot selection scheme for Band Division Multi-Carrier-CDMA (BD-MC-CDMA) systems under the constraints of packet loss and delay bound for each individual session. By utilizing channel dynamics together with the delay deadline and loss history, one can determine whether to transmit or not during each time slot, based on the prediction of future channel variations. To validate the efficiency of the proposed algorithm, we model each sub-band as a discrete time Markov Chain using a finite state Markov channel (FSMC) and derive the criteria required for transmission decision. Simulation results show that our proposed scheme can satisfy quality of service (QoS) requirements for real-time traffic with minimum use of resources, while increasing throughput of non-real-time traffic with the resources saved from real-time traffic.
Jun MURAMATSU Takafumi MUKOUCHI
The explicit construction of a universal source code for correlated sources is presented. The construction is based on a technique of simulated random coding algorithms [5]. The proposed algorithm simulates the random generation of linear codes. For every pair of correlated sources whose achievable rate region includes a given pair of encoding rates, the decoding error rate of the proposed algorithm goes to zero almost surely as the block length goes to infinity.
Katsuyuki HANEDA Jun-ichi TAKADA Takehiko KOBAYASHI
This paper introduces the concept of measuring double directional channels in ultra wideband (UWB) systems. Antenna-independent channel data were derived by doing the measurements in a wooden Japanese house. The data were useful for investigating the impact of UWB antennas and analyzing waveform distortion. Up to 100 ray paths were extracted using the SAGE algorithm and they were regarded as being dominant. The paths were then identified in a real environment, in which clusterization analyses were done using the directional information on both sides of the radio link. Propagating power was found to be concentrated around the specular directions of reflection and diffraction. This led to the observation that the spatio-temporal characteristics of extracted paths greatly reflected the structure and size of the environment. The power in the clusters indicated that the estimated 100 paths contained 73% of the total received power, while the rest existed as diffuse scattering, i.e., the accumulation of weaker paths. The practical limits of path extraction with SAGE were also discussed. Finally, we derived the scattering loss and intra-cluster properties for each reflection order, which were crucial for channel reconstrucion based on the deterministic approach.