Shigeyuki ASAMI Masashi YOSHIDA Kenichi KAGOSHIMA
The Multi-Point Relay (MPR) of the Optimized Link State Routing protocol reduces the flooding overhead compared with classic flooding. To select MPR nodes, HELLO messages are used. In dense population environments, the overhead of HELLO messages is critical because the HELLO messages carry all adjacent node IDs in the classical manner. Consequently, wireless bandwidth is consumed for data communications. One solution for this problem is to compress HELLO messages using a differential technique. However, few, if any, studies have applied a differential technique to HELLO messages. We introduce the novel Differential HELLO technique to reduce the overhead of the HELLO messages. The Differential HELLO technique consists of two kinds of compression methods: Chronological Compression and Topological Compression. In addition, the inconsistency problems of the 1-hop node information in adjacent nodes caused by packet loss are discussed. As solutions to the inconsistency problems, No Compression Acknowledgement (NC-ACK) and HELLO Information Forecast (HIF) have been examined. Our simulation has taken the efficiency of the Differential HELLO technique into consideration. The HELLO message overhead was reduced to 29.1 IDs from 75.8 IDs using the Differential HELLO technique at a packet loss rate of 10-4 under random node arrangement. This result reveals that the Differential HELLO technique reduces the classic HELLO overhead by 38%. In environments with lower packet-loss rates, the Differential HELLO technique promises to offer even better performance.
Md. Saidur RAHMAN Noritsugu EGI Takao NISHIZEKI
A plane graph is a planar graph with a fixed embedding. In a no-bend orthogonal drawing of a plane graph, each vertex is drawn as a point and each edge is drawn as a single horizontal or vertical line segment. A planar graph is said to have a no-bend orthogonal drawing if at least one of its plane embeddings has a no-bend orthogonal drawing. In this paper we consider a class of planar graphs, called subdivisions of planar triconnected cubic graphs, and give a linear-time algorithm to examine whether such a planar graph G has a no-bend orthogonal drawing and to find one if G has.
Min-Hung WENG Cheng-Yuan HUNG Hung-Wei WU
The investigation presents a low cost and low insertion loss X-band dual mode bandpass filter (BPF) based on inexpensive commercial FR4 substrate. The proposed filter at a central frequency f0 of 11.3 GHz has high filter performance filter with a fractional bandwidth of 14%, the insertion loss of -2.7 dB, and two transmission zeros. The designed procedures are presented in this letter and the fabricated filter verifies the proposed designed concept.
In this paper, we study trellis properties of the tensor product (product code) of two linear codes, and prove that the tensor product of the lexicographically first bases for two linear codes in minimal span form is exactly the lexicographically first basis for their product code in minimal span form, also the tensor products of characteristic generators of two linear codes are the characteristic generators of their product code.
Shinji WATANABE Yasuhiro MINAMI Atsushi NAKAMURA Naonori UEDA
A Shared-State Hidden Markov Model (SS-HMM) has been widely used as an acoustic model in speech recognition. In this paper, we propose a method for constructing SS-HMMs within a practical Bayesian framework. Our method derives the Bayesian model selection criterion for the SS-HMM based on the variational Bayesian approach. The appropriate phonetic decision tree structure of the SS-HMM is found by using the Bayesian criterion. Unlike the conventional asymptotic criteria, this criterion is applicable even in the case of an insufficient amount of training data. The experimental results on isolated word recognition demonstrate that the proposed method does not require the tuning parameter that must be tuned according to the amount of training data, and is useful for selecting the appropriate SS-HMM structure for practical use.
The purpose of this study is to provide a new approach for detection using bio-impedance. This impedance is measured by the four-electrode method. As the impedance changes resulting from ankle, knee, and hip movements depended heavily on electrode placement, we determined the optimal electrode configurations for those movements by searching for high correlation coefficients, large impedance changes, and minimum interferences in ten subjects (Age: 204). Our optimal electrode configurations showed very strong relationships between the ankle joint angle and ankle impedance (γ = -0.9130.03), between the knee joint angle and knee impedance (γ = 0.9440.02), and between the hip joint angle and hip impedance (γ = 0.8230.08). This study showed the possibility that lower leg movement could be easily measured by impedance measurement system with two pairs of skin-electrodes.
This paper discusses real-time language recognition by 1-dimensional one-way cellular automata (OCAs) and two-way cellular automata (CAs), focusing on limitations of the parallel computation power. To clarify the limitations, we investigate real-time recognition of cyclic strings of the form uk with u {0,1}+ and k 2. We show a version of pumping lemma for recognizing cyclic strings by OCAs, which can be used for proving that several languages are not recognizable by OCAs in real time. The paper also discusses the real-time language recognition of CAs by prefix and postfix computation, in which every prefix or postfix of an input string is also accepted, if the prefix or postfix is in the language. It is shown that there are languages L
Ruey-Shun CHEN Duen-Kai CHEN Szu-Yin LIN
The traffic congestion problem in urban areas is worsening since traditional traffic signal control systems cannot provide] efficient traffic regulation. Therefore, dynamic traffic signal control in Intelligent Transportation System (ITS) recently has received increasing attention. This study devised a multi-agent architecture, the Adaptive and Cooperative Traffic light Agent Model (ACTAM), for a decentralized traffic signal control system. The proposed architecture comprises a data storage and communication layer, a traffic regulation factor processing layer, and a decision-making layer. This study focused on utilizing the cooperation of multi-agents and the prediction mechanism of our architecture, the Forecast Module, to forecast future traffic volume in each individual intersection. The Forecast Module is designed to forecast traffic volume in an intersection via multi-agent cooperation by exchanging traffic volume information for adjacent intersections, since vehicles passing through nearby intersections were believed to significantly influence the traffic volume of specific intersections. The proposed architecture can achieve dynamic traffic signal control. Thus, total delay time of the traffic network under ACTAM can be reduced by 37% compared to the conventional fixed sequence traffic signal control strategy. Consequently, traffic congestion in urban areas can be alleviated by adopting ACTAM.
Satoshi SUYAMA Hiroshi SUZUKI Kazuhiko FUKAWA
When the multipath delay difference exceeds the guard interval (GI), the performance of MIMO-OFDM transmission suffers severely from both the inter-symbol interference (ISI) from the adjacent OFDM symbols and the inter-carrier interference (ICI) within the same symbol. This paper therefore proposes a MIMO-OFDM receiver employing the low-complexity turbo equalization. The proposed receiver initially separates the data streams and suppresses ICI by linear processing. In the iterative processing, it cancels the other data streams as well as ISI and ICI. The MIMO-OFDM turbo equalizer consists of an ISI canceller, an ICI canceller, an optimal detection filter, and a MAP detector. The proposed receiver can improve the transmission performance by exploiting the log-likelihood ratio that the decoding process produces for canceling both ISI and ICI and separating of the spatially multiplexed streams. Computer simulations, which apply the wireless LAN to MIMO, demonstrate that the proposed receiver can provide excellent performance in the severe multipath channels where the delay difference is greater than GI.
Huey-Min SUN Chia-Mei CHEN LihChyun SHU
In this study, we propose an object-based multimedia model for specifying the QoS (quality of service) requirements, such as the maximum data-dropping rate or the maximum data-delay rate. We also present a resource allocation model, called the net-profit model, in which the satisfaction of user's QoS requirements is measured by the benefit earned by the system. Based on the net-profit model, the system is rewarded if it can allocate enough resources to a multimedia delivery request and fulfill the QoS requirements specified by the user. At the same time, the system is penalized if it cannot allocate enough resources to a multimedia delivery request. We first investigate the problem of how to allocate resources efficiently, so that the QoS satisfaction is maximized. However, the net-profit may be distributed unevenly among the multimedia delivery requests. Thus, the second problem discusses how to allocate the resource efficiently so that the net-profit difference is minimized between any two multimedia requests. A dynamic programming based algorithm is proposed to find such an optimal solution with the minimum net-profit differences.
Jianqing WANG Tetsuji TSUCHIKAWA Osamu FUJIWARA
The use of metal-coated plastics is increasing as shielding materials of electronic and information products due to their lightweight. In this paper, a finite-difference time-domain (FDTD) algorithm, based on the derivation of a time-domain representation of the surface impedance of an equivalent resistive film, was developed to analyze the electromagnetic penetration of pulsed electromagnetic fields through metal-coated plastics. The validity of the proposed algorithm, in both the far-field and near-field cases, was verified by comparing the calculated penetrated electromagnetic fields or shielding effectiveness with theoretical and measured ones. Good agreement between them demonstrated the usefulness of the FDTD algorithm.
This paper presents a computer-aided design procedure of simulated annealing algorithm to optimize dual-wideband microstrip line filters with symmetrical at least 500 MHz bandwidths respectively. This method demonstrates the superiority of designing microstrip line dual-band filters. The value of characteristic impedances and electrical lengths of transmission lines synthesizing 2.4 GHz and 5.2 GHz dualband filters with a single input and a single output are adjusted to the annealing process by the optimization algorithm. The fabricated dual-wideband spectral transmittance and reflectance curves of these filters applying this method all effectively achieved desired high performances and resulted in a lower cost dual-band filters and open the way to commercial mass production. The method is applicable not only in 2.4 GHz and 5.2 GHz, but can be applied to any other multi-frequency bands.
Kaoru KUROSAWA Tetsu IWATA Quang Viet DUONG
In the key recovery variant of the interpolation attack, exhaustive search is required to find the last round key Km. Therefore, this attack is almost impractical if the size of Km is too large. In this paper, we show that Km can be very efficiently obtained if F(K,x) can be approximated by a low degree polynomial gx(K) in K for any fixed x, where F is a round function of Feistel type block ciphers.
Takaharu HIRAOKA Yoshiaki NEISHI Tetsuo ANADA Jui-Pang HSU
A detailed investigation of the electromagnetic field distributions in high frequency printed circuits and high-speed interconnects is very useful for physical understanding, studies of electromagnetic coupling effects for EMC and EMI and for optimization of electromagnetic circuit designs. The aim of this paper is to show how to measure the electric field distributions in electromagnetic circuits. An electromagnetic analysis for microstrip-line circuits is carried out by using a finite-difference time domain technique and its measurement is carried out by using a small probe antenna. The measurement results are in fairly good agreement with those of the numerical analysis using the FDTD method. Thus, the measurement system offers a valid means for predictions in the theoretical analysis of more complicated discontinuity problems.
Enjian BAI Xiaotong FU Guozhen XIAO
In this letter we first introduce a new generalized cyclotomic sequence of order four with respect to pq, then we calculate the linear complexity and minimal polynomial of this sequence. Our results show that the new binary sequence is quite good from the linear complexity viewpoint.
Hiroki SEKINE Tetsuro NOSAKA Yasuo HATANO Masaki TAKEDA Toshinobu KANEKO
This paper reports the strength of a pseudorandom number generator MUGI, which was published as a stream cipher by Hitachi, Ltd. in 2001, against linear cryptanalysis. MUGI is one of the recommended ciphers of CRYPTREC, which is a project for the e-Government in Japan. It has two internal states called state and buffer, which are updated by a linear function λ and a non-linear function ρ. The non-linear function ρ and the linear function λ have already been analyzed, independently. In this paper, whole MUGI is analyzed by truncated linear cryptanalysis. The analysis of λ function is based on the state variables method. The result is combined to the result of the analysis of ρ function to make a trellis diagram. Viterbi search is conducted on the diagram to find the best possible linear path under 64-bit truncated linear cryptanalysis. As the result, the upper bound of the maximum linear characteristic probability is estimated as less than 2-138. Therefore, MUGI is secure against linear cryptanalysis.
Young-Hwan YOU Min-Goo KANG Han-Jong KIM Pan-Yuh JOO Hyoung-Kyu SONG
One of the main disadvantage of multi-carrier CDMA (MC-CDMA) signals is the high peak power of the transmitted signals which limits their applications. To account for this issue, we provide a simple signal processing for reducing the high crest factor (CF) of MC-CDMA signals. Using this modified MC-CDMA signal, the high CF due to Walsh spreading sequences can be mitigated without explicit side information and degradation in the detection performance.
In this study, we construct balanced Boolean functions with a high nonlinearity and an optimum algebraic degree for both odd and even dimensions. Our approach is based on modifying functions from the Maiorana-McFarland's superclass, which has been introduced by Carlet. A drawback of Maiorana-McFarland's function is that their restrictions obtained by fixing some variables in their input are affine. Affine functions are cryptographically weak functions, so there is a risk that this property will be exploited in attacks. Due to the contribution of Carlet, our constructions do not have the potential weakness that is shared by the Maiorana-McFarland construction or its modifications.
Norio ADACHI Satoshi AOKI Yuichi KOMANO Kazuo OHTA
The PayWord Scheme, invented by Rivest and Shamir, is an efficient micropayment scheme utilizing a hash function. We point out that the scheme has the following problem: a malicious customer can damage the bank by purchasing in excess of the customer's credit which the bank has guaranteed by issuing a certificate. Generally, there are two positions of the bank with regard to the certificate. Position 1: the bank takes full responsibility for the certificate and compensates all payments created by the customer's purchases; and Position 2: the bank does not redeem payments exceeding a limit set for the customer and shares the loss with the shop if trouble occurs. In the PayWord Scheme, the bank can reduce its risk by adopting Position 2 rather than Position 1. However, this paper points out that the bank can damage the shop in Position 2 by impersonating an imaginary customer and making the shop share the loss with the bank. We propose a micropayment scheme (countermeasure) that overcomes these problems.
Jun CHOI Deukjo HONG Seokhie HONG Sangjin LEE
One of Kaliski and Robshaw's algorithms, which is used for the linear attack on block ciphers with multiple linear approximations and introduced as Algorithm 2M in this paper, looks efficient but lacks any theoretical and mathematical description. It means there exists no way to estimate the data complexity required for the attack by the algorithm except experiments of the reduced variants. In this paper we propose a new algorithm using multiple linear approximation. We achieve the theoretical and mathematical analysis of its success probability. The new algorithm needs about 240.6 plaintexts to find 12 bits of secret key of 16-round DES with a success probability of about 86%.