Nobuo FUNABIKI Jun KAWASHIMA Kiyohiko OKAYAMA Toru NAKANISHI Teruo HIGASHINO
With the explosive growth of the Internet system, demands for broadband communication networks have rapidly increased to provide high quality network services. For this purpose, the IEEE 802.6 MAC standard protocol defines the distributed-queue dual bus (DQDB) for metropolitan area networks (MANs). The isochronous channel reuse problem (ICRP) has been studied for efficient use of DQDB by finding proper channel assignments to incoming connection requests. In this paper, we first define the generalized isochronous channel reuse problem (GICRP) as a generalization of ICRP, to afford demands of simultaneously satisfying plural connection requests such as for multicast applications, where certain sets of connection requests must be assigned channels simultaneously. We prove the NP-completeness of its decision problem. Then, we propose a minimum dead space (MDS) algorithm as a heuristic approach to GICRP. The extensive simulation results show that with shorter computation time, our MDS algorithm can always find better channel assignments reducing the waiting time for packet transmissions than the best existing algorithm for conventional ICRP.
Tomohiro HACHINO Hitoshi TAKATA
This paper deals with an on-line identification method based on a radial basis function (RBF) network model for continuous-time nonlinear systems. The nonlinear term of the objective system is represented by the RBF network. In order to track the time-varying system parameters and nonlinear term, the recursive least-squares (RLS) method is combined in a bootstrap manner with the genetic algorithm (GA). The centers of the RBF are coded into binary bit strings and searched by the GA, while the system parameters of the linear terms and the weighting parameters of the RBF are updated by the RLS method. Numerical experiments are carried out to demonstrate the effectiveness of the proposed method.
The WDM optical networks currently being deployed are opaque optical networks, in which each link is optically isolated by transponders. To reduce the number of expensive transponders and switching ports, a hierarchical optical architecture consisting of all-optical waveband switching and opaque OEO switching has been proposed. Although this architecture requires fewer transponders and ports, it also requires a large number of wavelength (waveband) multiplexers and demultiplexers. Switching the optical path solely at the fiber level (i.e., by using fiber cross-connects, or FXCs) is desirable as a way to reduce the total node cost. If all the core nodes in an optical network are FXCs, however, the grooming of wavelengths for the optical fibers is only possible at the edge nodes. This leads to poor utilization of wavelength resources when there is only demand for small numbers of wavelengths, and as a result, the link cost increases. This problem can be solved by adding an OEO grooming function to some of the FXCs. In this paper, we propose an algorithm for designing optical cross-connect (OXC) functions on the basis of the FXC, thus minimizing the total network cost.
Kazuhiko KINOSHITA Hideaki TANIOKA Tetsuya TAKINE Koso MURAKAMI
In future high-speed networks, provision of diverse multimedia services with strict quality-of-service (QoS) requirements, such as bandwidth, delay and so on, is desired. QoS routing is a possible solution to handle these services. Generally, a path selection for QoS routing is formulated as a shortest path problem subject to multiple constraints. However, it is known to be NP-complete when more than one QoS constraint is imposed. As a result, many heuristic algorithms have been proposed so far. The authors proposed a path selection algorithm Fallback+ for QoS routing, which focuses not only on the path selection with multiple constraints but also on the efficient use of network resources. This paper proposes an enhanced version of Fallback+, named Enhanced Fallback+, where in a shrewd way, it keeps tentative paths produced in the conventional Fallback algorithm with Dijkstra's algorithm. Simulation experiments prove the excellent performance of Enhanced Fallback+, compared with the original Fallback+ and other existing path selection algorithms.
Seong-Joon BAEK Jinyoung KIM Dae-Jin KIM Dong-Soo HAR Kiseon KIM
In this paper, we propose a robust adaptive algorithm for impulsive noise suppression. The perturbation of the input signal as well as the perturbation of the estimation error are restricted by M-estimation. The threshold used in M-estimation is obtained from the proposed adaptive variance estimation. Simulations show that the proposed algorithm is less vulnerable to the impulsive noise than the conventional algorithm.
Yoshihiko SUSUKI Takashi HIKIHARA Hsiao-Dong CHIANG
This paper discusses stability boundaries in an electric power system with dc transmission based on a differential-algebraic equation (DAE) system. The DAE system is derived to analyze transient stability of the ac/dc power system: the differential equation represents the dynamics of the generator and the dc transmission, and the algebraic equation the active and reactive power relationship between the ac system and the dc transmission. In this paper complete characterization of stability boundaries of stable equilibrium points in the DAE system is derived based on an energy function for the associated singularly perturbed (SP) system. The obtained result completely describes global structures of the stability boundaries in solution space of the DAE system. In addition the characterization is confirmed via several numerical results with a stability boundary.
Wen-Jun CHEN Bin-Hong LI Tao XIE
An empirical formula of resonant frequency of bow-tie microstrip antennas is presented, which is based on the cavity model of microstrip patch antennas. A procedure to design a bow-tie antenna using genetic algorithm (GA) in which we take the formula as a fitness function is also given. An optimized bow-tie antenna by genetic algorithm was constructed and measured. Numerical and experimental results are used to validate the formula and GA. The results are in good agreement.
Takatoshi JITSUHIRO Tomoko MATSUI Satoshi NAKAMURA
We propose a new method to introduce the Minimum Description Length (MDL) criterion to the automatic generation of non-uniform, context-dependent HMM topologies. Phonetic decision tree clustering is widely used, based on the Maximum Likelihood (ML) criterion, and only creates contextual variations. However, the ML criterion needs to predetermine control parameters, such as the total number of states, empirically for use as stop criteria. Information criteria have been applied to solve this problem for decision tree clustering. However, decision tree clustering cannot create topologies with various state lengths automatically. Therefore, we propose a method that applies the MDL criterion as split and stop criteria to the Successive State Splitting (SSS) algorithm as a means of generating contextual and temporal variations. This proposed method, the MDL-SSS algorithm, can automatically create adequate topologies without such predetermined parameters. Experimental results for travel arrangement dialogs and lecture speech show that the MDL-SSS can automatically stop splitting and obtain more appropriate HMM topologies than the original one.
Yoshiki SAMESHIMA Hideaki SAISHO Kazuko OYANAGI Tsutomu MATSUMOTO
The authors present a multiparty signature generation (MSG) scheme of the Digital Signature Algorithm (FIPS 186-1). The scheme is based on a simple idea, however, it is much more convenient in usability in the real world than existing MSGs. The scheme has the following properties: (1) valid signatures are generated with odd n split private keys, (2) broadcast messages between the key holders are hidden from them, so that the n key holders do not need to process signature generation simultaneously, (3) even if up to t (= ) split keys are stolen, the adversary can get no information on the private key, (4) the scheme is as secure as the original signature algorithm against chosen message attack, and (5) the scheme is efficient in the sense that an implementation on smart card has demonstrated practical performance for interactive use with human user.
We propose a novel wavelength assignment algorithm that can establish lightpaths requiring the least wavelength conversions by chaining a minimum number of wavelength-continuous segments. Simulations show that our algorithm outperforms both first-fit and most-used schemes with large margins. Besides, moderate computational requirement and insignificant signaling overhead are also advantages of our algorithm.
Diagonal algebraic space time (DAST) block codes was proved to achieve the full transmit diversity over a quasi-static fading channel and to maintain 1 symbol/s/Hz. When the number of transmit antennas employed is larger than 2, DAST codes outperform the codes from orthogonal design with the equivalent spectral efficiency. However, due to the limitation on the signal constellation with complex integer points, no good 3bits/symbol DAST block code was given previously. In this paper, we propose a general form of 8-star-PSK constellations with integer points and present some theoretical results on the performance of the equivalent 8-star-PSK modulations. By using our proposed 8-star-PSKs, we present a searching algorithm to construct DAST codes with 3 bits per symbol under some criteria and investigate their performances over flat Rayleigh fading channels. It is shown that (5,2) 8-star-PSK scheme has a comparable performance to conventional 8PSK over additive white Gaussian noise (AWGN) channel and the corresponding DSAT codes constructed can achieve significant performance gain over flat Rayleigh fading channel.
Shoji YAMAMOTO Shuichi ICHIKAWA Hiroshi YAMAMOTO
Subgraph isomorphism problems have various important applications, while generally being NP-complete. Though Ullmann and Konishi proposed the custom circuit designs to accelerate subgraph isomorphism problem, they require many hardware resources for large problems. This study describes the design of data-dependent circuits for subgraph isomorphism problem with evaluation results on an actual FPGA platform. Data-dependent circuits are logic circuits specialized in specific input data. Such circuits are smaller and faster than the original circuit, although it is not reusable and involves circuit generation for each input. In the present study, the circuits were implemented on Xilinx XC2V3000 FPGA, and they successfully operated at a clock frequency 25 MHz. In the case of graphs with 16 vertices, the average execution time is about 7.0% of the software executed on an up-to-date microprocessor (Athlon XP 2600+ of 2.1 GHz clock). Even if the circuit generation time is included, data-dependent circuits are about 14.4 times faster than the software (for random graphs with 16 vertices). This performance advantage becomes larger for larger graphs. Two algorithms (Ullmann's and Konishi's) were examined, and the data-dependent approach was found to be equally effective for both algorithms. We also examined two types of input graph sets, and found that the data-dependent approach shows advantage in both cases.
Many algorithms have been introduced to obtain giga-bit routing performance by reducing searching time. As most of them, however, have not considered the importance of update time and memory requirement seriously, they couldn't work well in real networks. We propose a flexible and fast IP lookup algorithm, named FFILA, considering these factors and compare the performance of our scheme with that of the conventional scheme of Patricia trie.
Kyungmi PARK Jinhan SONG Saewoong BAHK
We propose a new dynamic routing algorithm that uses traffic and network state information to minimize the blocking rate and link congestion level. Our scheme uses the currently available link capacity in calculating the link weight by modifying Wang's approach, and computes the shortest path when a new call comes into the network. We consider the blocking count based update mechanism and the timer based mechanism, and conclude that the former is better than the latter in terms of efficiency and complexity.
Eiko SUGAWARA Masaru FUKUSHI Susumu HORIGUCHI
This paper addresses the issue of reconfiguring multi-layer neural networks implemented in single or multiple VLSI chips. The ability to adaptively reconfigure network configuration for a given application, considering the presence of faulty neurons, is a very valuable feature in a large scale neural network. In addition, it has become necessary to achieve systems that can automatically reconfigure a network and acquire optimal weights without any help from host computers. However, self-reconfigurable architectures for neural networks have not been studied sufficiently. In this paper, we propose an architecture for a self-reconfigurable multi-layer neural network employing both reconfiguration with spare neurons and weight training by GAs. This proposal offers the combined advantages of low hardware overhead for adding spare neurons and fast weight training time. To show the possibility of self-reconfigurable neural networks, the prototype system has been implemented on a field programmable gate array.
Rui CHEN Mohammad Reza ASHARIF Iman TABATABAEI ARDEKANI Katsumi YAMASHITA
The conventional algorithms in the echo canceling system have drawback when they are faced with double-talk condition in noisy environment. Since the double-talk and noise signal are exist, then the error signal is contaminated to estimate the gradient correctly. In this paper, we define a new class of adaptive algorithm for tap adaptations, based on the correlation function processing. The computer simulation results show that the Correlation LMS (CLMS) and the Extended CLMS (ECLMS) algorithms have better performance than conventional LMS algorithm. In order to implement the ECLMS algorithm, the Frequency domain Extended CLMS (FECLMS) algorithm is proposed to reduce the computational complexity. However the convergence speed is not sufficient. In order to improve the convergence speed, the Wavelet domain Extended CLMS (WECLMS) algorithm is proposed. The computer simulation results support the theoretical findings and verify the robustness of the proposed WECLMS algorithm in the double-talk situation.
Satoshi KONISHI Megumi SHIBUYA Shinichi NOMOTO
Electronic mail (email) is one of the most popular services using Internet Protocol (IP). Emails are now sent to and from portable phones in addition to laptop computers. The volume of emails is increasing because of the recent addition of attached electronic files. In addition, short message delivery services (SMS) that send email header information and the essence of email contents are also commonly used. Global short message delivery services via satellites are considered attractive for meeting the demand of increased short message delivery services. To establish a communications link for indoor subscribers, it is preferable to concentrate high transmission power into a spot-beam even using a non-geostationary satellite orbit (non-GSO) satellite system with low Earth orbits. The idea can be realized by a kind of TDMA scheme where only a single spot-beam per satellite is fired at a timeslot in an efficiently scheduled manner. This paper proposes a global short message delivery scheme and a scheduling algorithm that enables each satellite to concentrate its power into a spot-beam illuminating the addressed area in a prescribed timeslot, so that a subscriber in the area can efficiently receive a message addressed to the subscriber. Since the algorithm must guarantee that the spot-beam assignment causes no interference with other spot-beams from adjacent satellites, numerical evaluations are given for a 6-hour period MEO system, as an example, to demonstrate the efficacy and performance.
This paper proposes the use of the ratio of wavelet extrema numbers taken from the horizontal and vertical counts respectively as a texture feature, which is called aspect ratio of extrema number (AREN). We formulate the classification problem upon natural and synthesized texture images as an optimization problem and develop a coevolving approach to select both scalar wavelet and multiwavelet feature spaces of greater discriminatory power. Sequential searches and genetic algorithms (GAs) are comparatively investigated. The experiments using wavelet packet decompositions with the innovative packet-tree selection scheme ascertain that the classification accuracy of coevolutionary genetic algorithms (CGAs) is acceptable enough.
Jeng-Shyang PAN Min-Tsang SUNG Hsiang-Cheh HUANG Bin-Yih LIAO
A new scheme for watermarking based on vector quantization (VQ) over a binary symmetric channel is proposed. By optimizing VQ indices with genetic algorithm, simulation results not only demonstrate effective transmission of watermarked image, but also reveal the robustness of the extracted watermark.
In this paper, the optimal assignment problem which assigns cells in PCS (Personal Communication Service) to switches on ATM (Asynchronous Transfer Mode) network is investigated. The cost considered in this paper has two components: one is the cost of handoff that involves two switches, and the other is the cost of cabling. This problem assumes that each cell in PCS can be assigned to two switches in ATM network. This problem is modelled as dual-homing cell assignment problem, which is a complex integral linear programming (ILP) problem. Since finding an optimal solution of this problem is NP-hard, a hybrid method which combines several heuristics and a stochastic search method (based on a simulated annealing(SA) approach) is proposed to solve this problem. The solution method consists of three phases: Primary Assignment Decision Phase (PADP), Secondary Assignment Decision Phase (SADP) and Refinement Phase (RP). The PADP and SADP are used to find good initial assignment, then domain-dependent heuristics are encoded into perturbations of SA in Refinement Phase to improve the result. Simulation results show that the proposed hybrid method is robust for this problem.