Sayuri TERADA Toshimitsu USHIO
In an embedded control system, control performances of each job depend on its latency and a control algorithm implemented in it. In order to adapt a job set to optimize control performances subject to schedulability, we design several types of control software for each job, which will be called versions, and select one version from them when the job is released. A real-time system where each job has several versions is called a multiversion real-time system. A benefit and a CPU utilization of a job depend on the versions. So, it is an important problem to select a version of each job so as to maximize the total benefit of the system subject to a schedulability condition. Such a problem will be called an optimal configuration problem. In this paper, we assume that each version is specified by the relative deadline, the execution time, and the benefit. We show that the optimal configuration problem is transformed to a maximum path length problem. We propose an optimal algorithm based on the forward dynamic programming. Moreover, we propose sub-optimal algorithms to reduce computation times. The efficiencies of the proposed algorithms are illustrated by simulations.
Ying WANG Zixiong CHEN Cong SHI Ping ZHANG
With development of wireless communication technologies, users are no longer satisfied with only a single service provided per time. They are willing to enjoy multiple services simultaneously. Therefore scheduling multiple services per user becomes quite important usability issue in the area of resource management. In this paper, the multiple-service scheduling problem is firstly formulated as an integrated optimization problem based on a utility function in homogeneous service systems. Due to its NP-hard characteristic, a set of low-complexity sub-optimal algorithms is therefore proposed and used to schedule resources for multiple services per user at the downlink of Orthogonal Frequency Division Multiplexing (OFDM) systems. The proposed algorithms are capable to effectively and efficiently distribute assigned resources among multiple services for one user. Moreover the utility of our algorithms is further extended from homogeneous service systems to heterogeneous service systems. And full exploitation of multi-user diversity gain is achieved while guaranteeing quality of service (QoS). The simulation results show that the proposed algorithm outperforms traditional algorithm in terms of system best effort service throughput and fairness criterion.
Seulki LEE Jerald YOO Hoi-Jun YOO
A Real-time Capacitor Compensation (RCC) scheme is proposed for low power and continuous communication in the wearable inductive coupling transceiver. Since inductance values of wearable inductor vary dynamically with deterioration of its communication characteristics, the inductance value is monitored and its resonance frequency is adjusted by additive parallel/serial capacitors in real time. RLC Bridge for detection of the inductance variations and the Dual-edge Sampling Comparator for recognition of the variance direction are proposed. It is implemented in a 0.18 µm CMOS technology, and it occupies a 12.7 mm2 chip area. The proposed transceiver consumes only 426.6 µW at 4 Mbps data rate. The compensation time takes 4.78 µs, including 3 µs of detection and 1.78 µs for compensation process in worst case.
Binary maximal-length sequences (or m-sequences) are sequences of period 2m-1 generated by a linear recursion of degree m. Decimating an m-sequence {st} by an integer d relatively prime to 2m-1 leads to another m-sequence {sdt} of the same period. The crosscorrelation of m-sequences has many applications in communication systems and has been an important and well studied problem during more than 40 years. This paper presents an updated survey on the crosscorrelation between binary m-sequences with at most five-valued crosscorrelation and shows some of the many recent connections of this problem to several areas of mathematics such as exponential sums and Dickson polynomials.
For cyclic codes some well-known lower bounds and some decoding methods up to the half of the bounds are suggested. Particularly, the shift bound is a good lower bound of the minimum distance for cyclic codes, Reed-Muller codes and geometric Goppa codes. In this paper we consider cyclic codes defined by their defining set, and new simple derivation of the shift bound using the discrete Fourier transform with unknown elements and the Blahut theorem is shown. Moreover two examples of binary cyclic codes are given.
Yosuke HIMURA Kensuke FUKUDA Patrice ABRY Kenjiro CHO Hiroshi ESAKI
In this paper, we discuss the validity of the multi-scale gamma model and characterize the differences in host-level application traffic with this model by using a real traffic trace collected on a 150-Mbps transpacific link. First, we investigate the dependency of the model (parameters α and β, and fitting accuracy ε) on time scale Δ, then find suitable time scales for the model. Second, we inspect the relations among α, β, and ε, in order to characterize the differences in the types of applications. The main findings of the paper are as follows. (1) Different types of applications show different dependencies of α, β, and ε on Δ, and display different suitable Δs for the model. The model is more accurate if the traffic consists of intermittently-sent packets than other. (2) More appropriate models are obtained with specific α and β values (e.g., 0.1 < α < 1, and β < 2 for Δ = 500 ms). Also, application-specific traffic presents specific ranges of α, β, and ε for each Δ, so that these characteristics can be used in application identification methods such as anomaly detection and other machine learning methods.
Zhenyu LIU Dongsheng WANG Takeshi IKENAGA
Variable block size motion estimation developed by the latest video coding standard H.264/AVC is the efficient approach to reduce the temporal redundancies. The intensive computational complexity coming from the variable block size technique makes the hardwired accelerator essential, for real-time applications. Propagate partial sums of absolute differences (Propagate Partial SAD) and SAD Tree hardwired engines outperform other counterparts, especially considering the impact of supporting variable block size technique. In this paper, the authors apply the architecture-level and the circuit-level approaches to improve the maximum operating frequency and reduce the hardware overhead of Propagate Partial SAD and SAD Tree, while other metrics, in terms of latency, memory bandwidth and hardware utilization, of the original architectures are maintained. Experiments demonstrate that by using the proposed approaches, at 110.8 MHz operating frequency, compared with the original architectures, 14.7% and 18.0% gate count can be saved for Propagate Partial SAD and SAD Tree, respectively. With TSMC 0.18 µm 1P6M CMOS technology, the proposed Propagate Partial SAD architecture achieves 231.6 MHz operating frequency at a cost of 84.1 k gates. Correspondingly, the maximum work frequency of the optimized SAD Tree architecture is improved to 204.8 MHz, which is almost two times of the original one, while its hardware overhead is merely 88.5 k-gate.
Bing ZHANG Toshifumi OOTA Azman-Osman LIM Youiti KADO
Two-dimensional (2D) communication is a novel physical communication form that utilizes the surface as a communication medium to provide both data and power transmission service to the sensor devices placed on the surface's top. In previous works, we developed 2D communication systems that utilize separated channels for data and power transmission. Though this assignment of different channels can achieve strong network performance, the sensor devices must be equipped with two or more interfaces to simultaneously receive the power and data signals, which significantly complicates and enlarges those devices. Moreover, when a channel is used for the power supply, it not only continually monopolizes the wireless frequency resource, it is also likely to cause interference with the other signal source in the case of the input power continually being sent out above a certain level. In this paper, we develop a novel 2D communication sensor system by using a single-carrier frequency for both power and data transmission, equipped with the wireless module for the two together in a compact body. To enable a sensor node that concurrently receives energy and data communication, we propose an enhancement scheme based on the IEEE802.15.4 MAC protocol standard. Through both computer simulation and actual measurement of the output power, we evaluate the performance of power supply and data transmission over the developed 2D communication sensor system.
Tein-Yaw CHUNG Yung-Mu CHEN Liang-Yi HUANG
This paper proposes a cross layer wireless VoIP service which integrates an Adaptive QoS Playout (AQP) algorithm, E-model, Stream Control Transmission Protocol (SCTP), IEEE 802.21 Media Independent Handover (MIH) middleware and two user motion detection services. The proposed AQP algorithm integrates the effect of playout control and lost packet retransmission based on the E-model. Besides, by using the partial reliable transmission service from SCTP and the handoff notification from MIH services in a cross layer manner, AQP can reduce the lateness loss rate and improve speech quality under high frame error rates. In the simulations, the performance of AQP is compared with a fixed playout algorithm and four adaptive playout strategies. The simulation results show that the lateness loss rate of AQP is 2% lower than that of existing playout algorithms and the R-factor is 16% higher than the compared algorithms when a network has 50 ms wired propagation delay and 2.5% frame error rate.
Xiaohan LIU Hideo MAKINO Kenichi MASE
The need for efficient movement and precise location of robots in intelligent robot control systems within complex buildings is becoming increasingly important. This paper proposes an indoor positioning and communication platform using Fluorescent Light Communication (FLC) employing a newly developed nine-channel receiver, and discusses a new location estimation method using FLC, that involves a simulation model and coordinate calculation formulae. A series of experiments is performed. Distance errors of less than 25 cm are achieved. The enhanced FLC system yields benefits such as greater precision and ease of use.
Woong-Kee LOH Yang-Sae MOON Jun-Gyu KANG
In this paper, we emphasize the need for data cleansing when clustering large-scale transaction databases and propose a new data cleansing method that improves clustering quality and performance. We evaluate our data cleansing method through a series of experiments. As a result, the clustering quality and performance were significantly improved by up to 165% and 330%, respectively.
Mohammad BEHDADFAR Hossein SAIDI Masoud-Reza HASHEMI Ali GHIASIAN Hamid ALAEI
Recently, we have proposed a new prefix lookup algorithm which would use the prefixes as scalar numbers. This algorithm could be applied to different tree structures such as Binary Search Tree and some other balanced trees like RB-tree, AVL-tree and B-tree with minor modifications in the search, insert and/or delete procedures to make them capable of finding the prefixes of an incoming string e.g. an IP address. As a result, the search procedure complexity would be O(log n) where n is the number of prefixes stored in the tree. More important, the search complexity would not depend on the address length w i.e. 32 for IPv4 and 128 for IPv6. Here, it is assumed that interface to memory is wide enough to access the prefix and some simple operations like comparison can be done in O(1) even for the word length w. Moreover, insertion and deletion procedures of this algorithm are much simpler and faster than its competitors. In what follows, we report the software implementation results of this algorithm and compare it with other solutions for both IPv4 and IPv6. It also reports on a simple hardware implementation of the algorithm for IPv4. Comparison results show better lookup and update performances or superior storage requirements for Scalar Prefix Search in both average and worst cases.
Tian HAO Masayuki IWAI Yoshito TOBE Kaoru SEZAKI
Collecting environmental sound by utilizing high-end mobile phones provides us opportunities to capture rich contextual information in real world. The gathered information can be used for various purposes, ranging from academic research to livelihood support. Furthermore, mobility of mobile phones opens a door for easily forming a dynamic sensing infrastructure, in order to gather fine-grained, but still large-scale data from both spatial and temporal perspectives. However, collecting, analyzing, storing, and sharing of sound data usually involve large energy consumption than scalar data, and like any battery-operated device, mobile phones also face the reality of energy constraints. Because people's first priorities are naturally to use mobile phones for their own purposes, there are occasions when people will not be inclined to allow their mobile phones to be used as sensing devices fearing that they will run out of batteries. Therefore, our research focuses on energy-efficient sensing, to reduce average energy consumption and to extend overall system lifetime. In this paper, we propose a node scheduling scheme for mobile nodes. By applying this scheme, optimized sensing schedules (ACTIVE/SLEEP duty cycles) will be periodically generated at each node. Following the provided schedule during sensing, energy-efficiency can be realized while original Quality of Service (i.e. coverage rate) is retained. Unlike most previous works which were based on ideal binary disk coverage model, our proposal is designed under a probabilistic disk coverage model which takes the characteristic of sound propagation into consideration. Furthermore, this is the first scheme that is adaptable to large-scale mobile sensor networks where topology dynamically changes. An accurate energy consumption model is adopted for evaluating the proposed scheme. Simulation results show that our scheme can reduce up to 48% energy consumption in an ideal environment and up to 31% energy consumption in a realistic environment. The robustness of our scheme is also verified against different type of sensing terrains and communication environments.
Recent studies investigating the Internet topology reported that inter Autonomous System (AS) topology exhibits a power-law degree distribution which is known as the scale-free property. Although there are many models to generate scale-free topologies, no game theoretic approaches have been proposed yet. In this paper, we propose the new dynamic game theoretic model for the AS level Internet topology formation. Through numerical simulations, we show our process tends to give emergence of the topologies which have the scale-free property especially in the case of large decay parameters and large random link costs. The significance of our study is summarized as following three topics. Firstly, we show that scale-free topologies can also emerge from the game theoretic model. Secondly, we propose the new dynamic process of the network formation game for modeling a process of AS topology formation, and show that our model is appropriate in the micro and macro senses. In the micro sense, our topology formation process is appropriate because this represents competitive and distributed situation observed in the real AS level Internet topology formation process. In the macro sense, some of statistical properties of emergent topologies from our process are similar to those of which also observed in the real AS level Internet topology. Finally, we demonstrate the numerical simulations of our process which is deterministic variation of dynamic process of network formation game with transfers. This is also the new result in the field of the game theory.
Sunmi KIM Hirokazu TANAKA Takahiro OGAWA Miki HASEYAMA
In this paper, we propose a two-step error concealment algorithm based on an error resilient three-dimensional discrete wavelet transform (3-D DWT) video coding scheme. The proposed scheme consists of an error-resilient encoder duplicating the lowest sub-band bit-streams for dispersive grouped frames and an error concealment decoder. The error concealment method of this decoder is decomposed of two steps, the first step is replacement of erroneous coefficients in the lowest sub-band by the duplicated coefficients, and the second step is interpolation of the missing wavelet coefficients by minimum mean square error (MMSE) estimation. The proposed scheme can achieve robust transmission over unreliable channels. Experimental results provide performance comparisons in terms of peak signal-to-noise ratio (PSNR) and demonstrate increased performances compared to state-of-the-art error concealment schemes.
An algorithm is formulated for reconstructing a dielectric cylinder with the use of the T-matrix and the singular value decomposition (SVD) and is discussed through numerical examples under noisy conditions. The algorithm consists of two stages. At the first stage the measured data of scattered waves is transformed into the T-matrix. At the second stage we reconstruct the cylinder from the T-matrix. The singular value decomposition is applied in order to separate the radiating and the nonradiating currents, and the radiating current is directly obtained from the T-matrix. The nonradiating current and the object are reconstructed by decreasing a residual error of the current in the least square approximation, where linear equations are solved repeatedly. Some techniques are used in order to reduce the calculation time and to reduce the effects of noise. Numerical examples show us that the presented approach is simple and numerically feasible, and enables us to reconstruct a large object in a short time.
Yoshifumi KAWAMURA Takashi HIKAGE Toshio NOJIMA
The purpose of this study is to establish a whole-body averaged specific absorption rate (WB-SAR) estimation method using the power absorbed by humans; a cylindrical-external field scanning technique is used to measure the radiated RF (radio-frequency) power. This technique is adopted with the goal of simplifying the estimation of the exposure dosimetry of humans who have different postures and/or sizes. In this paper, to validate the proposed measurement method, we subject numerical human phantom models and cylindrical scanning conditions to FDTD analysis. We design a radiation system that uses a dielectric lens to achieve plane-wave irradiation of tested human phantoms in order to develop an experimental WB-SAR measurement system for UHF far-field exposure condition. In addition, we use a constructed SAR measurement system to confirm absorbed power estimations of simple geometrical phantoms and so estimate measurement error of the measurement system. Finally, we discuss the measurement results of WB-SARs for male adult and child human phantom models.
For optimization problems with irregular and complex multimodal landscapes, Estimation of Distribution Algorithms (EDAs) suffer from the drawback of premature convergence similar to other evolutionary algorithms. In this paper, we propose an adaptive niching EDA based on Affinity Propagation (AP) clustering analysis. The AP clustering is used to adaptively partition the niches and mine the searching information from the evolution process. The obtained information is successfully utilized to improve the EDA performance by using a balance niching searching strategy. Two different categories of optimization problems are used to evaluate the proposed adaptive niching EDA. The first one is solving three benchmark functional multimodal optimization problems by a continuous EDA based on single Gaussian probabilistic model; the other one is solving a real complicated discrete EDA optimization problem, the HP model protein folding based on k-order Markov probabilistic model. Simulation results show that the proposed adaptive niching EDA is an efficient method.
Chien-Ning CHEN Sung-Ming YEN SangJae MOON
Simple power analysis (SPA) can be employed in examining the power consumption trace of elliptic curve scalar multiplication to retrieve the computational sequence. However, SPA cannot distinguish point addition from point subtraction. The attacker still requires an exhaustive search to recover the private key when it is recoded in NAF or recoded by the 2-bit sliding window method. The average Hamming weight of an n-bit NAF recoded scalar is n/3, and an exhaustive search among the 2n/3 candidates is required. This paper shows that in a left-to-right NAF recoded or a left-to-right 2-bit sliding window manipulated scalar the relative position of nonzero bits will reveal their values. Our analysis skill reduces the number of candidates of the scalar from the naive search of 2n/3 to 22n/9 and 20.19n respectively for the cases of NAF and sliding window method.
Seung Hyun CHO Sang Woo KIM Woo Seok CHEONG Chun Won BYUN Chi-Sun HWANG Kyoung Ik CHO Byung Seong BAE
Oxide material can make transparent devices with transparent electrodes. We developed a transparent oscillator and rectifier circuits with oxide TFTs. The source/drain and gate electrodes were made by indium thin oxide (ITO), and active layer made by transparent material of IGZO (Indium Gallium Zinc Oxide) on a glass substrate. The RC oscillator was composed of bootstrapped inverters, and 813 kHz oscillation frequency was accomplished at VDD = 15 V. For DC voltage generation from RF, transparent rectifier was fabricated and evaluated. This DC voltage from rectifier powered to the oscillator which operated successfully to create RF. For data transmission, RF transmission was evaluated with RF from the transparent oscillator. An antenna was connected to the oscillator and RF transmission to a receiving antenna was verified. Through this transmission antenna, RF was transmitted to a receiving antenna successfully. For transparent system of RFID, transparent antenna was developed and verified sending and receiving of data.