Sasinee PRUEKPRASERT Toshimitsu USHIO
In this paper, we formulate an optimal stabilization problem of quantitative discrete event systems (DESs) under partial observation. A DES under partial observation is a system where its behaviors cannot be completely observed by a supervisor. In our framework, the supervisor observes not only masked events but also masked states. Our problem is then to synthesize a supervisor that drives the DES to a given target state with the minimum cost based on the detected sequences of masked events and states. We propose an algorithm for deciding the existence of an optimal stabilizing supervisor, and compute it if it exists.
Mohamed Hadi HABAEBI Mabruka Mohamed AGEL Alhareth ZYOUD
Accidental falling among elderly people has become a public health concern. Thus, there is a need for systems that detect a fall when it happens. This paper presents a portable real-time remote health monitoring system that can remotely monitor patients' movements. The system is designed and implemented using ZigBee wireless technologies, and the data is analysed using Matlab. The purpose of this research is to determine the acceleration thresholds for fall detection, using tri-axial accelerometer readings at the head, waist, and knee. Seven voluntary subjects performed purposeful falls and Activities of Daily Living (ADL). The results indicated that measurements from the waist and head can accurately detect falls; the sensitivity and reliability measurements of fall detection ranged between 80% and 90%. In contrast, the measurements showed that the knee is not a useful position for the fall detection.
Bin YAO Lifeng HE Shiying KANG Xiao ZHAO Yuyan CHAO
The Euler number is an important topological property in a binary image, and it can be computed by counting certain bit-quads in the binary image. This paper proposes a further improved bit-quad-based algorithm for computing the Euler number. By scanning image rows two by two and utilizing the information obtained while processing the previous pixels, the number of pixels to be checked for processing a bit-quad can be decreased from 2 to 1.5. Experimental results demonstrated that our proposed algorithm significantly outperforms conventional Euler number computing algorithms.
Yosuke WAKAMATSU Hiroyoshi YAMADA Yoshio YAMAGUCHI
The MIMO technique can improve system performance of not only communication system but also of radar systems. In this paper, we apply the MIMO radar with enhanced angular resolution to the indoor location estimation of humans. The Khatri-Rao (KR) matrix product is also adopted for further angular resolution enhancement. We show that the MIMO radar with the KR matrix product processing can increase the number of virtual elements effectively with suitable element arrangement, hence higher angular resolution can be realized. In general, the KR matrix product processing is not suitable for coherent radar because of signal correlation. However, when targets signals have enough Doppler frequency differential against each other, this approach works well because the signals are decorrelated. In addition, Doppler filtering is introduced to remove unwanted responses of stationary objects which make human detection difficult with conventional methods. Computer simulation and experimental results are provided to show performance of the proposed method.
Kentaro MURATA Naoki HONMA Kentaro NISHIMORI David M. KLYMYSHYN Hisashi MORISHITA
An analog-beamforming-based eigenmode transmission technique is proposed that employs a network of interconnected 180-degree hybrid couplers at both transmitting and receiving sides of a plane-symmetrically configured short-range MIMO system. This technique can orthogonalize MIMO channels regardless of array parameters such as antenna spacing and Tx-Rx distance, provided the MIMO array is symmetric. For verifying the effectiveness of the proposed technique in channel orthogonalization, an experiment is conducted using a 4×4 MIMO array consisting of microstrip antennas and cascade-connected rat-race hybrid couplers. The results indicate a reduction in interference by approximately -28.3dB on average compared to desired signal power, and the ability to realize four-stream parallel MIMO transmission by using only analog passive networks. The proposed technique can achieve channel capacity almost equivalent to that of eigenbeam space division multiplexing with ideal digital beamforming.
Hiroki YAMAZAKI Takuya SAKAMOTO Hirofumi TAKI Toru SATO
Microwave systems have a number of promising applications in surveillance and monitoring systems. The main advantage of microwave systems is their ability to detect targets at distance under adverse conditions such as dim, smoky, and humid environments. Specifically, the wide bandwidth of ultra-wideband radar enables high range resolution. In a previous study, we proposed an accurate shape estimation algorithm for multiple targets using multiple ultra-wideband Doppler interferometers. However, this algorithm produces false image artifacts under conditions with severe interference. The present paper proposes a technique to suppress such false images by detecting inconsistent combinations of the radial velocity and time derivative of image positions. We study the performance of the proposed method through numerical simulations of a two-dimensional section of a moving human body, and demonstrate the remarkable performance of the proposed method in suppressing false image artifacts in many scenarios.
Motomi ABE Yukihiro TAHARA Tetsu OWADA Naofumi YONEDA Hiroaki MIYASHITA
A novel directional coupler loaded with feedback capacitances on the coupled lines is presented. Its effect of enhancing the coupling is qualitatively shown by deriving an equation for the coupling. Besides, a method to compensate for the phase difference between the even and odd modes of the coupler is presented. To demonstrate, a novel tandem 3-dB coupler consisting of the proposed coupled lines is designed and described. In addition, a waveguide (rectangular coaxial line) 8×8 HYB matrix using planar double-layer structure that is composed of the proposed tandem 3-dB couplers and branch-line couplers, which is operated in S-band, is designed and fabricated showing excellent performance.
Two spanning trees T1,T2 of a graph G = (V,E) are independent if they are rooted at the same vertex, say r, and for each vertex v ∈ V, the path from r to v in T1 and the path from r to v in T2 have no common vertices and no common edges except for r and v. In general, spanning trees T1,T2,…,Tk of a graph G = (V,E) are independent if they are pairwise independent. A graph G = (V,E) is called a 2-chordal ring and denoted by CR(N,d1,d2), if V = {0,1,…,N-1} and E = {(u,v)|[v-u]N = 1 or [v-u]N = d1 or [v-u]N = d2, 2 ≤ d1 < d2 ≤ N/2}. CR(N,d1,N/2) is 5-connected if N ≥ 8 is even and d1 ≠ N/2-1. We give an algorithm to construct 5 independent spanning trees of CR(N,d1,N/2),N ≥ 8 is even and 2 ≤ d1 ≤ ⌈N/4⌉.
Kojiro TAKEYAMA Satoshi MAKIDO Yoshiko KOJIMA
In recent years, various Portable Navigation Devices (PND) such as smart-phones are becoming popular as a vehicle navigation device. To compare with a conventional built-in navigation system, PND has advantages that it is low cost and easily mounted to the vehicle. On the other hand, PND has also disadvantage that in the most case it cannot obtain the reliable vehicle speed information such as wheel pulse information and that induces degradation of vehicle trajectory estimation (dead-reckoning). The vehicle trajectory estimation is the positioning method using inertial sensors, and generally used when GPS is not available. So in urban area where GPS signals are blocked or reflected by tall buildings, the degradation of vehicle trajectory estimation may cause the severe increase of position error. Accordingly, in this study two approaches are proposed to improve vehicle trajectory estimation with PND. The first one is the accurate speed estimation using time-series tightly coupled integration of accelerometer, gyro, and Doppler shift of GPS. And the second one is the correction of trajectory error using backward refinement that can work even in real-time processing. The experimental result in Shinjuku which is dense urban city shows that the error of vehicle trajectory estimation was reduced to 1/4 compared with the previous method.
Surachai THONGKAEW Tsuyoshi ISSHIKI Dongju LI Hiroaki KUNIEDA
The Process Virtual Machine (VM) is typical software that runs applications inside operating systems. Its purpose is to provide a platform-independent programming environment that abstracts away details of the underlying hardware, operating system and allows bytecodes (portable code) to be executed in the same way on any other platforms. The Process VMs are implemented using an interpreter to interpret bytecode instead of direct execution of host machine codes. Thus, the bytecode execution is slower than those of the compiled programming language execution. Several techniques including our previous paper, the “Fetch/Decode Hardware Extension”, have been proposed to speed up the interpretation of Process VMs. In this paper, we propose an additional methodology, the “Hardware Extension with Hybrid Execution” to further enhance the performance of Process VMs interpretation and focus on Register-based model. This new technique provides an additional decoder which can classify bytecodes into either simple or complex instructions. With “Hybrid Execution”, the simple instruction will be directly executed on hardware of native processor. The complex instruction will be emulated by the “extra optimized bytecode software handler” of native processor. In order to eliminate the overheads of retrieving and storing operand on memory, we utilize the physical registers instead of (low address) virtual registers. Moreover, the combination of 3 techniques: Delay scheduling, Mode predictor HW and Branch/goto controller can eliminate all of the switching mode overheads between native mode and bytecode mode. The experimental results show the improvements of execution speed on the Arithmetic instructions, loop & conditional instructions and method invocation & return instructions can be achieved up to 16.9x, 16.1x and 3.1x respectively. The approximate size of the proposed hardware extension is 0.04mm2 (or equivalent to 14.81k gates) and consumes an additional power of only 0.24mW. The stated results are obtained from logic synthesis using the TSMC 90nm technology @ 200MHz.
Cheng JI Daisuke ANZAI Jianqing WANG Ikuko MORI Osamu FUJIWARA
We conduct, in accordance with IEC 61000-4-2, an electrostatic discharge (ESD) test for a small size battery-operated control circuit board in a myoelectric artificial hand system to investigate the influence of the induced noises by indirect ESDs from an ESD generator to a horizontal coupling plane (HCP) and a vertical coupling plane (VCP). A photo-coupler is set between the small size control board and a motor control circuit to suppress noise in the pulse width modulation (PWM) signals. Two types of ESD noise are observed at the output pins of PWM signals. One type is the ESD noise itself (called Type A) and the other one is the ESD noise superimposed over the PWM pulses (Type B). No matter which polarity the charge voltages of the ESD generator have, both types can be observed and the Type A is dominant in the output pulses. Moreover, the ESD interference in the HCP case is found to be stronger than that in the VCP case usually. In the PWM signals observed at the photo-coupler output, on the other hand, Type A noises tend to increase for positive polarity and decrease for negative polarity, while Type B noises tend to increase at -8kV test level in the HCP case. These results suggest that the photo-coupler does not work well for ESD noise suppression. One of the reasons has been demonstrated to be due to the driving capability of the photo-coupler, and other one is due to the presence of a parasitic capacitance between the input and output of the photo-coupler. The parasitic capacitance can yield a capacitive coupling so that high-frequency ESD noises pass through the photo-coupler.
Yoshikazu INAGAKI Shinya TAKAMAEDA-YAMAZAKI Jun YAO Yasuhiko NAKASHIMA
The Energy-aware Multi-mode Accelerator eXtension [24],[25] (EMAX) is equipped with distributed single-port local memories and ring-formed interconnections. The accelerator is designed to achieve extremely high throughput for scientific computations, big data, and image processing as well as low-power consumption. However, before mapping algorithms on the accelerator, application developers require sufficient knowledge of the hardware organization and specially designed instructions. They also need significant effort to tune the code for improving execution efficiency when no well-designed compiler or library is available. To address this problem, we focus on library support for stencil (nearest-neighbor) computations that represent a class of algorithms commonly used in many partial differential equation (PDE) solvers. In this research, we address the following topics: (1) system configuration, features, and mnemonics of EMAX; (2) instruction mapping techniques that reduce the amount of data to be read from the main memory; (3) performance evaluation of the library for PDE solvers. With the features of a library that can reuse the local data across the outer loop iterations and map many instructions by unrolling the outer loops, the amount of data to be read from the main memory is significantly reduced to a minimum of 1/7 compared with a hand-tuned code. In addition, the stencil library reduced the execution time 23% more than a general-purpose processor.
DTNs (Delay/Disruption-Tolerant Networks) composed of mobile nodes in low node-density environments have attracted considerable attention in recent years. In this paper, we propose a CD-BCAST (Contact Duration BroadCAST) mechanism that can reduce the number of message forwardings while maintaining short message delivery delays in DTNs composed of mobile nodes. The key idea behind CD-BCAST is to increase the probability of simultaneous forwarding by intentionally delaying message forwarding based on the contact duration distribution measured by each node. Through simulations, we show that CD-BCAST needs substantially less message forwardings than conventional mechanisms and it does not require parameter tuning under varieties of communication ranges and node densities.
Peer-to-peer (P2P)-Grid systems are being investigated as a platform for converging the Grid and P2P network in the construction of large-scale distributed applications. The highly dynamic nature of P2P-Grid systems greatly affects the execution of the distributed program. Uncertainty caused by arbitrary node failure and departure significantly affects the availability of computing resources and system performance. Checkpoint-and-restart is the most common scheme for fault tolerance because it periodically saves the execution progress onto stable storage. In this paper, we suggest a checkpoint-and-restart mechanism as a fault-tolerant method for applications on P2P-Grid systems. Failure detection mechanism is a necessary prerequisite to fault tolerance and fault recovery in general. Given the highly dynamic nature of nodes within P2P-Grid systems, any failure should be detected to ensure effective task execution. Therefore, failure detection mechanism as an integral part of P2P-Grid systems was studied. We discussed how the design of various failure detection algorithms affects their performance in average failure detection time of nodes. Numerical analysis results and implementation evaluation are also provided to show different average failure detection times in real systems for various failure detection algorithms. The comparison shows the shortest average failure detection time by 8.8s on basis of the WP failure detector. Our lowest mean time to recovery (MTTR) is also proven to have a distinct advantage with a time consumption reduction of about 5.5s over its counterparts.
Su-Jin CHOI Jeong-Yong BOO Ki-Jun KIM Hochong PARK
We propose a method of enhancing the performance of a cross-talk canceller for a four-speaker system with respect to sweet spot size and ringing effect. For the large sweet spot of a cross-talk canceller, the speaker layout needs to be symmetrical to the listener's position. In addition, a ringing effect of the cross-talk canceller is reduced when many speakers are located close to each other. Based on these properties, the proposed method first selects the two speakers in a four-speaker system that are most symmetrical to the target listener's position and then adds the remaining speakers between these two to the final selection. By operating only these selected speakers, the proposed method enlarges the sweet spot size and reduces the ringing effect. We conducted objective and subjective evaluations and verified that the proposed method improves the performance of the cross-talk canceller compared to the conventional method.
Junjun ZHENG Hiroyuki OKAMURA Tadashi DOHI
Survivability is the capability of a system to provide its services in a timely manner even after intrusion and compromise occur. In this paper, we focus on the quantitative analysis of survivability of virtual machine (VM) based intrusion tolerant system in the presence of Byzantine failures due to malicious attacks. Intrusion tolerant system has the ability of a system to continuously provide correct services even if the system is intruded. This paper introduces a scheme of the intrusion tolerant system with virtualization, and derives the success probability for one request by a Markov chain under the environment where VMs have been intruded due to a security hole by malicious attacks. Finally, in numerical experiments, we evaluate the performance of VM-based intrusion tolerant system from the viewpoint of survivability.
Yasuhiro TAKEI Hasitha Muthumala WAIDYASOORIYA Masanori HARIYAMA Michitaka KAMEYAMA
For an FPGA-based heterogeneous multicore platform, we present the design methodology to reduce the total processing time considering data-transfer. The reconfigurability of recent FPGAs with hard CPU cores allows us to realize a single-chip heterogeneous processor optimized for a given application. The major problem in designing such heterogeneous processors is data-transfer between CPU cores and accelerator cores. The total processing time with data-transfers is modeled considering the overlap of computation time and data-transfer time, and optimal design parameters are searched for.
Hon-Chan CHEN Tzu-Liang KUNG Yun-Hao ZOU Hsin-Wei MAO
In this paper, we investigate the fault-tolerant Hamiltonian problems of crossed cubes with a faulty path. More precisely, let P denote any path in an n-dimensional crossed cube CQn for n ≥ 5, and let V(P) be the vertex set of P. We show that CQn-V(P) is Hamiltonian if |V(P)|≤n and is Hamiltonian connected if |V(P)| ≤ n-1. Compared with the previous results showing that the crossed cube is (n-2)-fault-tolerant Hamiltonian and (n-3)-fault-tolerant Hamiltonian connected for arbitrary faults, the contribution of this paper indicates that the crossed cube can tolerate more faulty vertices if these vertices happen to form some specific types of structures.
Yuto MIYAKOSHI Shinya YASUDA Kan WATANABE Masaru FUKUSHI Yasuyuki NOGAMI
This paper addresses the problem of job scheduling in volunteer computing (VC) systems where each computation job is replicated and allocated to multiple participants (workers) to remove incorrect results by a voting mechanism. In the job scheduling of VC, the number of workers to complete a job is an important factor for the system performance; however, it cannot be fixed because some of the workers may secede in real VC. This is the problem that existing methods have not considered in the job scheduling. We propose a dynamic job scheduling method which considers the expected probability of completion (EPC) for each job based on the probability of worker's secession. The key idea of the proposed method is to allocate jobs so that EPC is always greater than a specified value (SPC). By setting SPC as a reasonable value, the proposed method enables to complete jobs without excess allocation, which leads to the higher performance of VC systems. We assume in this paper that worker's secession probability follows Weibull-distribution which is known to reflect more practical situation. We derive parameters for the distribution using actual trace data and compare the performance of the proposed and the previous method under the Weibull-distribution model, as well as the previous constant probability model. Simulation results show that the performance of the proposed method is up to 5 times higher than that of the existing method especially when the time for completing jobs is restricted, while keeping the error rate lower than a required value.
Asahi TAKAOKA Shingo OKUMA Satoshi TAYU Shuichi UENO
The harmonious coloring of an undirected simple graph is a vertex coloring such that adjacent vertices are assigned different colors and each pair of colors appears together on at most one edge. The harmonious chromatic number of a graph is the least number of colors used in such a coloring. The harmonious chromatic number of a path is known, whereas the problem to find the harmonious chromatic number is NP-hard even for trees with pathwidth at most 2. Hence, we consider the harmonious coloring of trees with pathwidth 1, which are also known as caterpillars. This paper shows the harmonious chromatic number of a caterpillar with at most one vertex of degree more than 2. We also show the upper bound of the harmonious chromatic number of a 3-regular caterpillar.