Minho SEO Wonik CHOI Yoo-Sung KIM Jaehyun PARK
We propose LPDD (Lifetime Prediction Directed Diffusion), a novel energy-aware routing protocol for sensor networks that aims at increasing network survivability without a significant increase in latency. The key concept behind the protocol is the adaptive selection of routes by predicting the battery lifetime of the minimum energy nodes along the routes.
Hiroshi KAWAGUCHI Danardono Dwi ANTONO Takayasu SAKURAI
Closed-form expressions for a crosstalk noise amplitude and worst-case delay in capacitively coupled two-line and three-line systems are derived assuming bus lines and other signal lines in a VLSI. Two modes are studied; a case that adjacent lines are driven from the same direction, and the other case that adjacent lines are driven from the opposite direction. Beside, a junction capacitance of a driver MOSFET is considered. The closed-form expressions are useful for circuit designers in an early stage of a VLSI design to give insight to interconnection problems. The expressions are extensively compared and fitted to SPICE simulations. The relative and absolute errors in the crosstalk noise amplitude are within 63.8% and 0.098 E (where E is a supply voltage), respectively. The relative error in the worst-case delay is less than 8.1%.
Hiroaki KOZAWA Kiyoharu HAMAGUCHI Toshinobu KASHIWABARA
For formal verification of large-scale digital circuits, a method using satisfiability checking of logic with equality and uninterpreted functions has been proposed. This logic, however, does not consider specific properties of functions or predicates at all, e.g. associative property of addition. In order to ease this problem, we introduce "equivalence constraint" that is a set of formulas representing the properties of functions and predicates, and check the satisfiability of formulas under the constraint. In this report, we show an algorithm for checking satisfiability with equivalence constraint and also experimental results.
Phanumas KHUMSAT Apisak WORAPISHET
A compact OTA suitable for low-voltage active-RC and MOSFET-C filters is presented. The input stage of the OTA utilises the NMOS pseudo-differential amplifier with PMOS active load. The output stage relies upon the dual-mode feed-forward class-AB technique (based on an inverter-type transconductor) with common-mode rejection capability that incurs no penalty on transconductance/bias-current efficiency. Simulation results of a 0.5-V 100-kHz 5th-order Chebyshev filter based on the proposed OTA in a 0.18 µm CMOS process indicate SNR and SFDR of 68 dB and 63 dB (at 50 kHz+55 kHz) respectively. The filter consumes total power consumption of 60 µW.
Shangce GAO Zheng TANG Hongwei DAI Jianchen ZHANG
The clonal selection algorithm (CS), inspired by the basic features of adaptive immune response to antigenic stimulus, can exploit and explore the solution space parallelly and effectively. However, antibody initialization and premature convergence are two problems of CS. To overcome these two problems, we propose a chaotic distance-based clonal selection algorithm (CDCS). In this novel algorithm, we introduce a chaotic initialization mechanism and a distance-based somatic hypermutation to improve the performance of CS. The proposed algorithm is also verified for numerous benchmark traveling salesman problems. Experimental results show that the improved algorithm proposed in this paper provides better performance when compared to other metaheuristics.
For coherent detection, decoding Orthogonal Space-Time Block Codes (OSTBC) requires full channel state information at the receiver, which basically is obtained by channel estimation. However, in practical systems, channel estimation errors are inevitable and may degrade the system performance more as the number of antennas increases. This letter shows that, using fewer receive antennas can enhance the performance of OSTBC systems in presence of channel estimation errors. Furthermore, a novel adaptive receive antenna selection scheme, which adaptively adjusts the number of receive antennas, is proposed. Performance evaluation and numerical examples show that the proposed scheme improves the performance obviously.
Takao FUJII Isao OHTA Tadashi KAWAI Yoshihiro KOKUBO
This paper presents some structures of artificial coplanar waveguide with very slow phase velocity and their applications to a design of compact 3-dB branch-line couplers. The slow-wave structure is constructed by periodically loading both of series inductance and shunt capacitance. First, a basic miniature branch-line coupler is designed and consequently considerable size-reduction of about 1/4 is obtained. Next, a broadband design technique is described using open-circuited quarter-wavelength series-stubs added at each port as a matching network. By size-reducing the series-stubs and branchline sections, a very compact broadband coupler with a good hybrid performance over a wide bandwidth of 31 percent or more is realized. The design concepts and procedures are verified both numerically and experimentally.
Jun'ichi YURA Hiroshi SAKAKIBARA Jin NAKAZAWA Hideyuki TOKUDA
We have been investigating a new class of ubiquitous services, called Activity Logging, which takes advantage for private and public sensors and the RFID tags on real-world objects. The purpose of Activity Logging is to digitally record users' interests with real-world objects and users' context to describe the users' activity. Such digital information acquired from a range of sensors and tags, if being accumulated, forms a great data source for users to recall their activities later or to share the activities with others. This paper explores the design space to realize Activity Logging, and proposes a simple mobile device called Activity Recorder that marries public and private sensors to provide a powerful Activity Logging service. An Activity Recorder contains a range of private sensors, and has communication capability to work with public sensors around the user.
Microwave measurement methods necessary to characterize copper-clad dielectric laminate substrates are reviewed to realize more precise design of planar circuits: that is, the balanced-type circular disk resonator method for the relative complex permittivity in the normal direction εrn and tan δn, the cavity resonator method and the cut-off waveguide method for one in the tangential direction εrt and tan δt, and the dielectric resonator method for the surface and interface conductivity of copper foil σs and σi. The measured results of the frequency and temperature dependences of these parameters are presented for a PTFE substrate and a copper-clad glass cloth PTFE laminate substrate.
One method for achieving high-speed waveform digitizing uses time-interleaved A-D Converters (ADCs). It is known that, in this method, using multiple ADCs enables sampling at a rate higher than the sampling rate of the ADC being used. Degradation of the dynamic range, however, results from such factors as phase error in the sampling clock applied to the ADC, and mismatched frequency characteristics among the individual ADCs. This paper describes a method for correcting these mismatches using a digital signal processing (DSP) technique. This method can be applied to any number of interleaved ADCs, and it does not require any additional hardware; good correction and improved accuracy can be obtained simply by adding a little to the computing overhead.
This paper addresses a new surface reconstruction scheme for approximating the isosurface from a set of tomographic cross sectional images. Differently from the novel Marching Cubes (MC) algorithm, our method does not extract the iso-density surface (isosurface) directly from the voxel data but calculates the iso-density point (isopoint) first. After building a coarse initial mesh approximating the ideal isosurface by the cell-boundary representation, it metamorphoses the mesh into the final isosurface by a relaxation scheme, called shrink-wrapping process. Compared with the MC algorithm, our method is robust and does not make any cracks on surface. Furthermore, since it is possible to utilize lots of additional isopoints during the surface reconstruction process by extending the adjacency definition, theoretically the resulting surface can be better in quality than the MC algorithm. According to experiments, it is proved to be very robust and efficient for isosurface reconstruction from cross sectional images.
Md. MAMUN-OR-RASHID Muhammad Mahbub ALAM Md. Abdur RAZZAQUE Choong Seon HONG
Congestion in WSN increases the energy dissipation rates of sensor nodes as well as the loss of packets and thereby hinders fair and reliable event detection. We find that one of the key reasons of congestion in WSN is allowing sensing nodes to transfer as many packets as possible. This is due to the use of CSMA/CA that gives opportunistic medium access control. In this paper, we propose an energy efficient congestion avoidance protocol that includes source count based hierarchical and load adaptive medium access control and weighted round robin packet forwarding. We also propose in-node fair packet scheduling to achieve fair event detection. The results of simulation show our scheme exhibits more than 90% delivery ratio even under bursty traffic condition which is good enough for reliable event perception.
Ubiquitous computing and the upcoming broadcast-and-communication convergence require networks that provide very complex services. In particular, networks are needed that can service several users or terminals at various times or places with various application-layer functions that can be changed at a high response speed by adding high-speed processing at the network edge. I present a query-transaction acceleration appliance that uses a dynamic reconfigurable processor (DRP) and enables high-speed stateful packet-by-packet self-reconfiguration to achieve that requirement. This appliance processes at high speeds, has flexible application layer functions that are changeable with a high-speed response, and uses direct packet I/O bypassing memory, hierarchical interconnection of processors, and stateful packet-by-packet self-reconfiguration. In addition, the DRP enables the fabrication of a compact and electric-power-saving appliance. I made a prototype and implemented several transport/application layer functions, such as TCP connection control, auto-caching of server files, uploading cache data for server, and selection/insertion/deletion/update of data for a database. In an experimental evaluation in which four kinds of query-transactions were continually executed in order, I found that the appliance achieved four functions changeable at a high response speed (within 1 ms), and a processing speed (2,273 transactions/sec.) 18 times faster than a PC with a 2-GHz processor.
Miyuki HANAOKA Makoto SHIMAMURA Kenji KONO
Exploiting layer7 context is an effective approach to improving the accuracy of detecting malicious messages in network intrusion detection/prevention systems (NIDS/NIPSs). Layer7 context enables us to inspect message formats and the message exchanged order. Unfortunately, layer7-aware NIDS/NIPSs pose crucial implementation issues because they require full TCP and IP reassembly without losing 1) complete prevention, 2) performance, 3) application transparency, or 4) transport transparency. Complete prevention means that the NIDS/NIPS should prevent malicious messages from reaching target applications. Application transparency means not requiring any modifications to and/or reconfiguration of server and client applications. Transport transparency is not to disrupt the end-to-end semantics of TCP/IP. To the best of our knowledge, none of the existing approaches meet all of these requirements. We have developed an efficient mechanism for layer7-aware NIDS/NIPSs that does meet the above requirements. Our store-through does this by forwarding each out-of-order or IP-fragmented packet immediately after copying the packet even if it has not been checked yet by an NIDS/NIPS sensor. Although the forwarded packet might turn out to be a part of an attack message, the store-through mechanism can successfully defend against the attack by blocking one of the subsequent packets that contain another part of attack message. Testing of a prototype in Linux kernel 2.4.30 demonstrated that the overhead of our mechanism is negligible compared with that of a simple IP forwarder even with the presence of out-of-order and IP-fragmented packets. In addition, the experimental results suggest that the CPU and memory usage incurred by our store-through is not significant.
Our purpose is to estimate conditional probabilities of output labels in multiclass classification problems. Adaboost provides highly accurate classifiers and has potential to estimate conditional probabilities. However, the conditional probability estimated by Adaboost tends to overfit to training samples. We propose loss functions for boosting that provide shrinkage estimator. The effect of regularization is realized by shrinkage of probabilities toward the uniform distribution. Numerical experiments indicate that boosting algorithms based on proposed loss functions show significantly better results than existing boosting algorithms for estimation of conditional probabilities.
M. Julius HOSSAIN M. Ali Akber DEWAN Oksam CHAE
This paper presents an automatic edge segment based algorithm for the detection of moving objects that has been specially developed to deal with the variations in illumination and contents of background. We investigated the suitability of the proposed edge segment based moving object detection algorithm in comparison with the traditional intensity based as well as edge pixel based detection methods. In our method, edges are extracted from video frames and are represented as segments using an efficiently designed edge class. This representation helps to obtain the geometric information of edge in the case of edge matching and shape retrieval; and creates effective means to incorporate knowledge into edge segment during background modeling and motion tracking. An efficient approach for background edge generation and a robust method of edge matching are presented to effectively reduce the risk of false alarm due to illumination change and camera motion while maintaining the high sensitivity to the presence of moving object. The proposed method can be successfully realized in video surveillance applications in home networking environment as well as various monitoring systems. As, video coding standard MPEG-4 enables content based functionality, it can successfully utilize the shape information of the detected moving objects to achieve high coding efficiency. Experiments with real image sequences, along with comparisons with some other existing methods are presented, illustrating the robustness of the proposed algorithm.
Toshihiro KATASHITA Yoshinori YAMAGUCHI Atusi MAEDA Kenji TODA
The present paper describes an implementation of an intrusion detection system (IDS) on an FPGA for 10 Gigabit Ethernet. The system includes an exact string matching circuit for 1,225 Snort rules on a single device. A number of studies have examined string matching circuits for IDS. However, implementing a circuit that processes a large rule set at high throughput is difficult. In a previous study, we proposed a method for generating an NFA-based string matching circuit that has expandability of processing data width and drastically reduced resource requirements. In the present paper, we implement an IDS circuit that processes 1,225 Snort rules at 10 Gbps with a single Xilinx Virtex-II Pro xc2vp-100 using the NFA-based method. The proposed circuit also provides packet filtering for an intrusion protection system (IPS). In addition, we developed a tool for automatically generating the Verilog HDL source code of the IDS circuit from a Snort rule set. Using the FPGA and the IDS circuit generator, the proposed system is able to update the matching rules corresponding to new intrusions and attacks. We implemented the IDS circuit on an FPGA board and evaluated its accuracy and throughput. As a result, we confirmed in a test that the circuit detects attacks perfectly at the wire speed of 10 Gigabit Ethernet.
Shinji KITA Seiichi OZAWA Satoshi MAEKAWA Shigeo ABE
In this paper, we present a new method to enhance classification performance of a multiple classifier system by combining a boosting technique called AdaBoost.M2 and Kernel Discriminant Analysis (KDA). To reduce the dependency between classifier outputs and to speed up the learning, each classifier is trained in a different feature space, which is obtained by applying KDA to a small set of hard-to-classify training samples. The training of the system is conducted based on AdaBoost.M2, and the classifiers are implemented by Radial Basis Function networks. To perform KDA at every boosting round in a realistic time scale, a new kernel selection method based on the class separability measure is proposed. Furthermore, a new criterion of the training convergence is also proposed to acquire good classification performance with fewer boosting rounds. To evaluate the proposed method, several experiments are carried out using standard evaluation datasets. The experimental results demonstrate that the proposed method can select an optimal kernel parameter more efficiently than the conventional cross-validation method, and that the training of boosting classifiers is terminated with a fairly small number of rounds to attain good classification accuracy. For multi-class classification problems, the proposed method outperforms both Boosting Linear Discriminant Analysis (BLDA) and Radial-Basis Function Network (RBFN) with regard to the classification accuracy. On the other hand, the performance evaluation for 2-class problems shows that the advantage of the proposed BKDA against BLDA and RBFN depends on the datasets.
Mohammad Ali BADAMCHIZADEH Sohrab KHANMOHAMMADI Ghasem ALIZADEH Ali AGHAGOLZADEH Ghader KARIMIAN
This paper deals with stability analysis of hybrid systems. Such systems are characterized by a combination of continuous dynamics and logic based switching between discrete modes. Lyapunov theory is a well known methodology for the stability analysis of linear and nonlinear systems in control system literature. Construction of Lyapunov functions for hybrid systems is generally a difficult task, but once these functions are defined, stabilization of the system is straight-forward. The sum of squares (SOS) decomposition and semidefinite programming has also provided an efficient methodology for analysis of nonlinear systems. The computational method used in this paper relies on the SOS decomposition of multivariate polynomials. By using SOS, we construct a (some) Lyapunov function(s) for the hybrid system. The reduction techniques provide numerical solution of large-scale instances; otherwise they will be practically unsolvable. The introduced method can be used for hybrid systems with linear or nonlinear vector fields. Some examples are given to demonstrate the capabilities of the proposed approach.
The antidictionary of a string is the set of all words of minimal length that never appear in this string. Antidictionaries are in particular useful for source coding. We present a fast and memory-efficient algorithm to construct an antidictionary using a suffix tree. It is proved that the complexity of this algorithm is linear in space and time, and its effectiveness is demonstrated by simulation results.