Naoto YANAI Eikoh CHIDA Masahiro MAMBO
Verifying the signing order is sometimes very important in multisignature schemes. A multisignature scheme in which the signing order can be verified is called structured multisignature scheme and many such schemes have been proposed so far. However, there are not many structured multisignature schemes utilizing an algebraic structure of underlying algebraic operation. Ohmori, Chida, Shizuya and Nishizeki have proposed a structured multisignature scheme by utilizing a non-commutative ring homomorphism. Since their scheme does not fully reflect the structure of signers and its rigorous security analysis is not provided, we construct an improved structured multisignature scheme overcoming these problems by utilizing the non-commutative ring homomorphism in a different way and discuss its rigorous security against various attacks, including signer structure forgery, rogue key attack and attack-0 under the discrete logarithm assumption. As far as we know, the scheme in [30], which does not use non-commutative ring homomorphism, guarantees the most rigorous security but the number of signers is restricted in order to prevent attack-0. In contrast, our scheme overcomes attack-0 by virtue of a ring homomorphism and no restriction is imposed on the number of signers.
Although a large number of query processing algorithms in spatial network database (SNDB) have been studied, there exists little research on route-based queries. Since moving objects move only in spatial networks, route-based queries, like in-route nearest neighbor (IRNN), are essential for Location-based Service (LBS) and Telematics applications. However, the existing IRNN query processing algorithm has a problem in that it does not consider time and space constraints. Therefore, we, in this paper, propose IRNN query processing algorithms which take both time and space constraints into consideration. Finally, we show the effectiveness of our IRNN query processing algorithms considering time and space constraints by comparing them with the existing IRNN algorithm.
In optical packet switches, the overhead of reconfiguring a switch fabric is not negligible with respect to the packet transmission time and can adversely affect switch performance. The overhead increases the average waiting time of packets and worsens throughput performance. Therefore, scheduling packets requires additional considerations on the reconfiguration frequency. This work intends to analytically find the optimal reconfiguration frequency that minimizes the average waiting time of packets. It proposes an analytical model to facilitate our analysis on reconfiguration optimization for input-buffered optical packet switches with the reconfiguration overhead. The analytical model is based on a Markovian analysis and is used to study the effects of various network parameters on the average waiting time of packets. Of particular interest is the derivation of closed-form equations that quantify the effects of the reconfiguration frequency on the average waiting time of packets. Quantitative examples are given to show that properly balancing the reconfiguration frequency can significantly reduce the average waiting time of packets. In the case of heavy traffic, the basic round-robin scheduling scheme with the optimal reconfiguration frequency can achieve as much as 30% reduction in the average waiting time of packets, when compared with the basic round-robin scheduling scheme with a fixed reconfiguration frequency.
Toshiya NAKAKURA Yasuyuki SUMI Toyoaki NISHIDA
This paper proposes a system called Neary that detects conversational fields based on similarity of auditory situation among users. The similarity of auditory situation between each pair of the users is measured by the similarity of frequency property of sound captured by head-worn microphones of the individual users. Neary is implemented with a simple algorithm and runs on portable PCs. Experimental result shows Neary can successfully distinguish groups of conversations and track dynamic changes of them. This paper also presents two examples of Neary deployment to detect user contexts during experience sharing in touring at the zoo and attending an academic conference.
In this paper, we propose a simple but effective way of improving the performance of channel estimation (CE) for pilot cyclic prefixed single carrier (PCP-SC) system. The proposed method utilizes the property that the shifting signal of the PCP pilot signal can also be utilized to estimate the channel information. The receiver can continuously estimate the channel information by just shifting the received pilot signal. Regardless of the signal-to-noise ratio (SNR) and the pilot type, the proposed method can achieve about a 1.72 dB performance gain in terms of the mean squared error (MSE) of channel estimation with a slight increase in computational complexity. The BER performance with the proposed CE improvement are evaluated in a multipath fading channel using a zero-forcing (ZF) equalizer and an minmum mean squared error (MMSE) equalizer by computer simulation. It is shown that the proposed CE improvment method using an MMSE equalizer which has an unbiased vlaue of noise variance (NV) estimator gives a promising BER performance. The proposed method also benefits the estimation of the SNR for the single carrier system.
In this letter, we propose a Partially Observable Markov Decision Process (POMDP) based Distributed Adaptive Opportunistic Spectrum Access (DA-OSA) Strategy for Cognitive Ad Hoc Networks (CAHNs). In each slot, the source and destination choose a set of channels to sense and then decide the transmission channels based on the sensing results. In order to maximize the throughput for each link, we use the theories of sequential decision and optimal stopping to determine the optimal sensing channel set. Moreover, we also establish the myopic policy and exploit the monotonicity of the reward function that we use, which can be used to reduce the complexity of the sequential decision.
Clocked cascade voltage switch logic (C2VSL) circuits with gated feedback were newly designed for synchronous systems. In order to investigate single event transient (SET) effects on the C2VSL circuits, SET effects on C2VSL EX-OR circuits were analyzed using SPICE. Simulation results have indicated that the C2VSL have increased tolerance to SET.
Mengshu HUANG Leona OKAMURA Tsutomu YOSHIHARA
An area efficiency hybrid decoupling scheme is proposed to suppress the charge pump noise during F-N tunneling program in non-volatile memory (NVM). The proposed scheme is focused on suppressing the average noise power in frequency domain aspect, which is more suitable for the program error reduction in NVMs. The concept of active capacitor is utilized. Feed forward effect of the amplifier is firstly considered in the impedance analysis, and a trade-off relation between in-band and out-band frequency noise decoupling performance is shown. A fast optimization based on average noise power is made to achieve minimum error in the F-N tunneling program. Simulation results show very stable output voltage in different load conditions, the average ripple voltage is 17 mV with up to 20 dB noise-suppression-ratio (NSR), and the F-N tunneling program error is less than 5 mV for a 800 µs program pulse. A test chip is also fabricated in 0.18 µm technology. The area overhead of the proposed scheme is 2%. The measurement results show 24.4 mV average ripple voltage compared to 72.3 mV of the conventional one with the same decoupling capacitance size, while the noise power suppression achieves 15.4 dB.
This letter presents a new automatic musical genre classification method based on an informative song-level representation, in which the mutual information between the feature and the genre label is maximized. By efficiently combining distance-based indexing with informative features, the proposed method represents a song as one vector instead of complex statistical models. Experiments on an audio genre DB show that the proposed method can achieve the classification accuracy comparable or superior to the state-of-the-art results.
Chongbin XU Hao WANG Xiaokang LIN
We study the transmission techniques in orthogonal frequency division multiplexing (OFDM) systems with imperfect channel state information at the transmitter (CSIT). We focus on the issue of utilizing the available CSIT by a single forward error control (FEC) code. We first analyze the system performance for the ideal coding case. We then develop a simple but efficient scheme for the practical coding case, which is based on joint FEC coding and linear precoding at the transmitter and iterative linear minimum-mean-square-error (LMMSE) detection at the receiver. Numerical results show that significant performances gains can be achieved by the proposed scheme.
Hirotoshi HONMA Yutaro KITAMURA Shigeru MASUYAMA
In an undirected graph, the feedback vertex set (FVS for short) problem is to find a set of vertices of minimum cardinality whose removal makes the graph acyclic. The FVS has applications to several areas such that combinatorial circuit design, synchronous systems, computer systems, VLSI circuits and so on. The FVS problem is known to be NP-hard on general graphs but interesting polynomial solutions have been found for some special classes of graphs. In this paper, we present an O(n2.68 + γn) time algorithm for solving the FVS problem on trapezoid graphs, where γ is the total number of factors included in all maximal cliques.
Yuya ONO Takuichi HIRANO Kenichi OKADA Jiro HIROKAWA Makoto ANDO
In this paper we present eigenmode analysis of the propagation constant for a microstrip line with dummy fills on a Si CMOS substrate. The effect of dummy fills is not negligible, particularly in the millimeter-wave band, although it has been ignored below frequencies of a few GHz. The propagation constant of a microstrip line with a periodic structure on a Si CMOS substrate is analyzed by eigenmode analysis for one period of the line. The calculated propagation constant and characteristic impedance were compared with measured values for a chip fabricated by the 0.18 µm CMOS process. The agreement between the analysis and measurement was very good. The dependence of loss on the arrangement of dummy fills was also investigated by eigenmode analysis. It was found that the transmission loss becomes large when dummy fills are arranged at places where the electromagnetic field is strong.
Bin SONG Hao QIN Xuelu PENG Yanhui QIN
An adaptive selective retransmission algorithm for video communications based on packet importance value is proposed. The algorithm can adaptively select the retransmission threshold in realtime and efficiently manage the retransmission process in heavy loaded networks while guaranteeing acceptable video quality at the receiver.
Jianxiong HUANG Taiyi ZHANG Runping YUAN Jing ZHANG
This letter investigates the performance of amplify-and-forward relaying systems using maximum ratio transmission at the source. A closed-form expression for the outage probability and a closed-form lower bound for the average bit error probability of the system are derived. Also, the approximate expressions for the outage probability and average bit error probability in the high signal-to-noise ratio regime are given, based on which the optimal power allocation strategies to minimize the outage probability and average bit error probability are developed. Furthermore, numerical results illustrate that optimizing the allocation of power can improve the system performance, especially in the high signal-to-noise ratio regime.
John Paul TORREGOZA Pham Ngoc THAI Won Joo HWANG Yun Sop HAN Fumio TERAOKA Martin ANDRE Hiroaki HARAI
Cognitive radio in network core devices, such as basestations, is being considered as a spectrum management solution for future society's communication demands. Aside from new resource allocation algorithms, efficient inter- and intra-protocol processing should be considered. In this paper, we propose an opportunistic cross layer architecture called COmmon Layer Architecture (COLA) for information exchange between arbitrary layers in New Generation Networks with network-oriented cognitive radio. COLA provides a means for faster information exchange between OSI layers by introducing abstraction at each layer and designing primitives for communication between each abstraction layer. Emulation and simulation results showed improvements, compared to conventional networks, in disrupted service (42% reduction), average delay (47% reduced) and packet drop ratio (22% reduced) in the scenario analyzed.
Orthogonal frequency division multiplexing has emerged as a promising air interface scheme for wireless broadband communications. For OFDM systems, frame synchronization has received much attention in the literature, though simple correlators are still widely used in real systems. In this letter, we present the analytical expression of the optimal frame synchronizer for OFDM systems. Frame synchronization is posed as a maximum a posteriori probability estimation. We show that the resulting frame synchronizer consists of a correlation term and a correction term. The correction term accounts for the random data surrounding a synchronization word. Numerical results show the performance gain of the proposed frame synchronizer over a correlation scheme.
Jianjun MU Xiaopeng JIAO Jianguang LIU Rong SUN
Trapping sets have been identified as one of the main factors causing error floors of low-density parity-check (LDPC) codes at high SNR values. By adding several new rows to the original parity-check matrix, a novel method is proposed to eliminate small trapping sets in the LDPC code's Tanner graph. Based on this parity-check matrix extension, we design new codes with low error floors from the original irregular LDPC codes. Simulation results show that the proposed method can lower the error floors of irregular LDPC codes significantly at high SNR values over AWGN channels.
Masato HAYASHI Susumu MATSUI Naoki WAKAMIYA Masayuki MURATA
The delay/disruption tolerant network (DTN) has been researched actively in the last years because of its high applicability to ubiquitous network services such as sensor networks and intelligent transport system (ITS) networks. An efficient data forwarding method for those network services is one of the key components in DTN due to the limitation of wireless network resources. This paper proposes a new DTN scheme for vehicle network systems by introducing the parameter, “approach ratio”, which represents node movement history. The proposal utilizes passive copy strategy, where nodes within one hop area of packet forwarders receive, copy and store packets (namely, passive copies) for future forwarding, in order to obtain higher delivery rate and lower delivery delay whilst suppressing the network resource consumption. Depending on its approach ratio, a node with passive copy decides whether it forwards the passive copy or not by referring to the approach ratio threshold. The approach ratio allows our proposal to adjust the property of both single-copy type scheme, that can lower network resource consumption, and multi-copy type scheme, that can enhance the performance of delivery rate and delay time. In simulation evaluation, the proposal is compared with three typical existing schemes with respect to network consumption, delivery rate and delivery delay. Our proposal shows the superior performance regarding the targeted purpose. It is shown that the approach ratio plays the significant role to obtain the higher delivery rate and lower delay time, while keeping network resource consumption lower.
We introduce a “generalized small inverse problem (GSIP)” and present an algorithm for solving this problem. GSIP is formulated as finding small solutions of f(x0, x1, ..., xn)=x0 h(x1, ..., xn)+C=0 (mod ; M) for an n-variate polynomial h, non-zero integers C and M. Our algorithm is based on lattice-based Coppersmith technique. We provide a strategy for construction of a lattice basis for solving f=0, which is systematically transformed from a lattice basis for solving h=0. Then, we derive an upper bound such that the target problem can be solved in polynomial time in log M in an explicit form. Since GSIPs include some RSA-related problems, our algorithm is applicable to them. For example, the small key attacks by Boneh and Durfee are re-found automatically.
We propose a statistical method for counting pedestrians. Previous pedestrian counting methods are not applicable to highly crowded areas because they rely on the detection and tracking of individuals. The performance of detection-and-tracking methods are easily degraded for highly crowded scene in terms of both accuracy and computation time. The proposed method employs feature-based regression in the spatiotemporal domain to count pedestrians. The proposed method is accurate and requires less computation time, even for large crowds, because it does not include the detection and tracking of objects. Our test results from four hours of video sequence obtained from a highly crowded shopping mall, reveal that the proposed method is able to measure human traffic with an accuracy of 97.2% and requires only 14 ms per frame.