A hinge vertex is a vertex in an undirected graph such that there exist two vertices whose removal makes the distance between them longer than before. Identifying hinge vertices in a graph can help detect critical nodes in communication network systems, which is useful for making them more stable. For finding them, an O(n3) time algorithm was developed for a simple graph, and, linear time algorithms were developed for interval and permutation graphs, respectively. Recently, the maximum detour hinge vertex problem is defined by Honma et al. For a hinge vertex u in a graph, the detour degree of u is the largest value of distance between any pair of x and y (x and y are adjacent to u) by removing u. A hinge vertex with the largest detour degree in G is defined as the maximum detour hinge vertex of G. This problem is motivated by practical applications, such as network stabilization with a limited cost, i.e., by enhancing the reliability of the maximum detour hinge vertex, the stability of the network is much improved. We previously developed an O(n2) time algorithm for solving this problem on an interval graph. In this study, we propose an algorithm that identifies the maximum detour hinge vertex on a permutation graph in O(n2) time, where n is the number of vertices in the graph.

This paper presents the effect of transmit diversity on the initial and neighboring cell search time performance and the most appropriate transmit diversity scheme based on system-level simulations employing synchronization signals for the Long Term Evolution (LTE) downlink. The synchronization signals including the primary synchronization signal (PSS) and secondary synchronization signal (SSS) are the first physical channel that a set of user equipment (UE) acquires at the initial radio-link connection. The transmit diversity candidates assumed in the paper are Precoding Vector Switching (PVS), Cyclic Delay Diversity (CDD), Time Switched Transmit Diversity (TSTD), and Frequency Switched Transmit Diversity (FSTD), which are all suitable for simple blind detection at a UE. System-level simulation results show that transmit diversity is effective in improving the detection probabilities of the received PSS timing and PSS sequence in the first step and those of the SSS sequence and radio frame timing in the second step of the cell search process. We also show that PVS achieves fast cell search time performance of less than approximately 20ms at the location probability of 90% regardless of the inter-cell site distance up to 10km. Hence, we conclude that PVS is the best transmit diversity scheme for the synchronization signals from the viewpoint of decreasing the initial and neighboring cell search times.

Verification of a design with respect to its requirement specification is important to prevent errors before constructing an actual implementation. The existing works focus on verifications where the specifications are described using temporal logics or using the same languages as that used to describe the designs. Our work considers cases where the specifications and the designs are described using different languages. To verify such cases, we propose a framework to check if a design conforms to its specification based on their simulation relation. Specifically, we define the semantics of the specifications and the designs commonly as labelled transition systems (LTSs). We appreciate LTSs since they could interpret information about the system and actions that the system may perform as well as the effect of these actions. Then, we check whether a design conforms to its specification based on the simulation relation of their LTS. In this paper, we present our framework for the verification of reactive systems, and we present the case where the specifications and the designs are described in Event-B and Promela/Spin, respectively. We also present two case studies with the results of several experiments to illustrate the applicability of our framework on practical systems.

This paper proposes a novel greedy algorithm, called Creditability-Estimation based Matching Pursuit (CEMP), for the compressed sensing signal recovery. As proved in the algorithm of Stagewise Orthogonal Matching Pursuit (StOMP), two Gaussian distributions are followed by the matched filter coefficients corresponding to and without corresponding to the actual support set of the original sparse signal, respectively. Therefore, the selection for each support point is interpreted as a process of hypothesis testing, and the preliminarily selected support set is supposed to consist of rejected atoms. A hard threshold, which is controlled by an input parameter, is used to implement the rejection. Because the Type I error may happen during the hypothesis testing, not all the rejected atoms are creditable to be the true support points. The creditability of each preliminarily selected support point is evaluated by a well-designed built-in mechanism, and the several most creditable ones are adaptively selected into the final support set without being controlled by any extra external parameters. Moreover, the proposed CEMP does not necessitate the sparsity level to be a priori control parameter in operation. In order to verify the performance of the proposed algorithm, Gaussian and Pulse Amplitude Modulation sparse signals are measured in the noiseless and noisy cases, and the experiments of the compressed sensing signal recoveries by several greedy algorithms including CEMP are implemented. The simulation results show the proposed CEMP can achieve the best performances of the recovery accuracy and robustness as a whole. Besides, the experiment of the compressed sensing image recovery shows that CEMP can recover the image with the highest Peak Signal to Noise Ratio (PSNR) and the best visual quality.

Fast simulation techniques of large scale RLC networks with nonlinear devices are presented. Generally, when scale of nonlinear part in a circuit is much less than the linear part, matrix or circuit partitioning approach is known to be efficient. In this paper, these partitioning techniques are used for the conventional transient analysis using an implicit numerical integration and the circuit-based finite-difference time-domain (FDTD) method, whose efficiency and accuracy are evaluated developing a prototype simulator. It is confirmed that the matrix and circuit partitioning approaches do not degrade accuracy of the transient simulations that is compatible to SPICE, and that the circuit partitioning approach is superior to the matrix one in efficiency. Moreover, it is demonstrated that the circuit-based FDTD method can be efficiently combined with the matrix or circuit partitioning approach, compared with the transient analysis using an implicit numerical integration.

In recent years, various applications based on propagation characteristics have been developed. They generally utilize the locality of the fading characteristics of multipath environments. On the other hand, if a received signal at a remote location can be estimated beyond the correlation distance of the multipath fading environment, a wide variety of new applications can be possible. In this paper, we attempt to estimate a received signal at a remote location using the MUSIC method and the least squares method. Based on the plane wave assumption for each arriving wave, multipath environment is analyzed through estimation of the directions of arrival by the MUISC method and the complex amplitudes of the received signals by the least squares method, respectively. We present evaluation results on the estimation performance of the method by computer simulations.

This report describes a robust method of instantaneous heart rate (IHR) extraction from noisy electrocardiogram (ECG) signals. Generally, R-waves are extracted from ECG using a threshold to calculate the IHR from the interval of R-waves. However, noise increases the incidence of misdetection and false detection in wearable healthcare systems because the power consumption and electrode distance are limited to reduce the size and weight. To prevent incorrect detection, we propose a short-time autocorrelation (STAC) technique. The proposed method extracts the IHR by determining the search window shift length which maximizes the correlation coefficient between the template window and the search window. It uses the similarity of the QRS complex waveform beat-by-beat. Therefore, it has no threshold calculation process. Furthermore, it is robust against noisy environments. The proposed method was evaluated using MIT-BIH arrhythmia and noise stress test databases. Simulation results show that the proposed method achieves a state-of-the-art success rate of IHR extraction in a noise stress test using a muscle artifact and a motion artifact.

Tonal signals are shown as spectral peaks in the frequency domain. When the number of spectral peaks is small and the spectral signal is sparse, Compressive Sensing (CS) can be adopted to locate the peaks with a low-cost sensing system. In the CS scheme, a time domain signal is modelled as $oldsymbol{y}=Phi F^{-1}oldsymbol{s}$, where y and s are signal vectors in the time and frequency domains. In addition, F-1 and $Phi$ are an inverse DFT matrix and a random-sampling matrix, respectively. For a given y and $Phi$, the CS method attempts to estimate s with l0 or l1 optimization. To generate the peak candidates, we adopt the frequency-domain information of $ esmile{oldsymbol{s}}$ = $oldsymbol{F} esmile{oldsymbol{y}}$, where $ esmile{y}$ is the extended version of y and $ esmile{oldsymbol{y}}left(oldsymbol{n} ight)$ is zero when n is not elements of CS time instances. In this paper, we develop Gaussian statistics of $ esmile{oldsymbol{s}}$. That is, the variance and the mean values of $ esmile{oldsymbol{s}}left(oldsymbol{k} ight)$ are examined.

Recently, we proposed an interference-aware channel segregation based dynamic channel assignment (IACS-DCA). In IACS-DCA, each base station (BS) measures the instantaneous co-channel interference (CCI) power on each available channel, computes the moving average CCI power using past CCI measurement results, and selects the channel having the lowest moving average CCI power. In this way, the CCI-minimized channel reuse pattern can be formed. In this paper, we introduce the autocorrelation function of channel reuse pattern, the fairness of channel reuse, and the minimum co-channel BS distance to quantitatively examine the channel reuse pattern formed by the IACS-DCA. It is shown that the IACS-DCA can form a CCI-minimized channel reuse pattern in a distributed manner and that it improves the signal-to-interference ratio (SIR) compared to the other channel assignment schemes.

Parameter variations in nanometer process technology are one of the major design challenges. They cause delay to be increased on the critical path and may change the logic level of internal nodes. The basic concept to solve these problems at the circuit level, design-for-variability (DFV), is to add an error handling circuit to the conventional circuits so that they are robust to nanometer related variations. The state-of-the-art variation-aware flip flops are mainly evolved from aggressive dynamic voltage and frequency scaling (DVFS) -based low-power application systems which handle errors due to the scaled supply voltage. However, they only detect the timing errors and cannot correct the errors. We propose a variation-aware flip flop which can detect and correct the timing error efficiently. The experimental results show that the proposed variation-aware flip flop is more robust and lower power than the existing approaches.

In wireless networks, interference from adjacent nodes that are concurrently transmitting can cause packet reception failures and thus a significant throughput degradation. The interference can be simply avoided by assigning different orthogonal channels to each interfering node. However, if the number of orthogonal channels is smaller than that of interfering nodes, some adjacent nodes have to share the same channel and may interfere with each other. This interference can be mitigated by reducing the transmit power of the interfering nodes. In this paper, we propose to jointly coordinate the transmit power and the multi-channel allocation to maximize the network throughput performance by fully exploiting multi-channel availability. This coordination enables each node to use high transmission power as long as different orthogonal channels can be assigned to its adjacent nodes. Then, we propose a simple multi-channel media access control (MAC) protocol that allows the nodes on different channels to perform efficient data exchanges without interference in multi-channel networks. We show that the proposed scheme improves the network throughput performance in comparison with other existing schemes.

Function speculation design with error recovery mechanisms is quite promising due to its high performance and low area overhead. Previous work has focused on two-stage function speculation and thus lacks a systematic way to address the challenge of the multistage function speculation approach. This paper proposes a multistage function speculation with adaptive predictors and applies it in a novel adder. We deduced the analytical performance and area models for the design and validated them in our experiments. Based on those models, a general methodology is presented to guide design optimization. Both analytical proofs and experimental results on the fabricated chips show that the proposed adder's delay and area have a logarithmic and linear relationship with its bit number, respectively. Compared with the DesignWare IP, the proposed adder provides the same performance with 6-17% area reduction under different bit lengths.

A proxy signature scheme allows an entity to delegate his signing capabilities to another. Many schemes have been provided for use in numerous applications such as distributed computing, grid computing, and mobile communications. In 2003, Boldyreva et al. introduced the first formal security model of proxy signatures and also proposed a generic construction secure in their model. However, an adversary can arbitrarily alter the warrants of the proxy signatures because the warrants are not explicitly considered in their model. To solve this problem, Huang et al. provided an enhanced security model of proxy signatures in 2005. Some proxy signatures secure in this security model have been proposed but there is no generic construction yet. In this paper, we redefine and improve the Huang et al.'s security model in terms of multi-user and then provide a new generic construction of proxy signatures secure against our enhanced security model based on ID-based signatures. Moreover, we can make a lattice-based proxy signature scheme in the standard model from our result.

In a proxy re-signatures (PRS) scheme, a semi-trusted proxy is given some information which allows it to translate a user i's signature on a message m into another user j's signature on the same message m. However, the proxy cannot, on it own, compute signatures for either i or j. This notion introduced by Blaze et a. at EUROCRYPT 1998, and then revisited by Ateniese and Hohenberger at CCS 2005. The existence of multi-use unidirectional PRS scheme is an open problem left by AH05. Whereafter, at CCS 2008, Libert and Vergnaud constructed the first multi-use unidirectional PRS scheme. However, there is a major drawback in the LV08 scheme that the size of the signatures is linear in the number of translations. Hence, Libert and Vergnaud said that a more challenging task would be to find out implementations of such primitives where the size of signatures and the verification cost do not grow linearly with the number of translations. In this work we resolve this task by constructing a such PRS scheme in the standard model by using indistinguishability obfuscation. A shortcoming of our construction is that the security is selective but not full.

Recently, Gan and Luo have proposed a direction-of-arrival estimation method for uncorrelated and coherent signals in the presence of multipath propagation [3]. In their method, uncorrelated and coherent signals are distinguished by rotational invariance techniques and the property of the moduli of eigenvalues. However, due to the limitation of finite number of sensors, the pseudo-inverse matrix derived in this method is an approximate one. When the number of sensors is small, the approximation error is large, which adversely affects the property of the moduli of eigenvalues. Consequently, the method in [3] performs poorly in identifying uncorrelated signals under such circumstance. Moreover, in cases of small number of snapshots and low signal to noise ratio, the performance of their method is poor as well. Therefore, in this letter we first study the approximation in [3] and then propose an improved method that performs better in distinguishing between uncorrelated signals and coherent signals and in the aforementioned two cases. The simulation results demonstrate the effectiveness and efficiency of the proposed method.

This letter deals with the carrier frequency offsets (CFO) estimation problem for orthogonal frequency division multiple access (OFDMA) uplink systems. Combined with centro-symmetric (CS) trimmed autocorrelation matrix and weighting subspace projection, the proposed estimator has better estimate performance than MVDR, MUSIC, CS-MUSIC, and ESPRIT estimators, especially in relatively less of OFDMA blocks and low SNR situations. Simulation results are presented to verify the efficiency of the proposed estimator.

Presently, many identity-based proxy signature (IBPS) schemes have been proposed, but most of them require high computational costs and the proposed security model for IBPS is not enough complete. To overcome this weakness, Gu et al. recently proposed a framework and a detailed security model for IBPS. They also proposed an efficient IBPS scheme and proved the unforgeability of their scheme in the standard model. However, in this letter, we demonstrate that Gu et al.'s scheme fails to satisfy the property of unforgeability because it can not resist the following attacks: after getting a private key, an adversary behaving as a malicious signer can forge a private key on any identity without the help of the private key generator (PKG); after getting a delegation, an adversary behaving as a malicious proxy signer can forge a proxy signing key on any delegation without the agreement of the original signer; after getting a signature, an adversary behaving as a malicious user can forge a signature on any identity without the private key or forge a proxy signature on any warrant without the proxy signing key.

A multicode transmission (MC) system can transmit multiple data streams at one time. However, the amplitude of the transmission signal has sharp fluctuations. To avoid this problem, constant amplitude (CA) signaling schemes were studied, and some MC systems were developed such as the MC system with CA signaling (MC-CA) and the parallel combinatory MC system with CA signaling (PCMC-CA). In this paper, extension systems of PCMC-CA system are developed. In particular, two demodulation methods are discussed for the extension systems. Then, the bit error rate (BER) and data transmission rate are theoretically analyzed. The results shows that the extension systems has a better performance than the MC-CA system in both of the BER and data transmission rate.

The dynamic routing and wavelength assignment (RWA) problem in wavelength division multiplexing (WDM) optical networks with sparse wavelength conversion has been a hot research topic in recent years. An optimized algorithm based on a multiple-layered interconnected graphic model (MIG) for the dynamic RWA is presented in this paper. The MIG is constructed to reflect the actual WDM network topology. Based on the MIG, the link cost is given by the conditions of available lightpath to calculate an initial solution set of optimal paths, and by combination with path length, the optimized solution using objective function is determined. This approach simultaneously solves the route selection and wavelength assignment problem. Simulation results demonstrate the proposed MIG-based algorithm is effective in reducing blocking probability and boosting wavelength resource utilization compared with other RWA methods.

In this work, the differential received signal strength based localization problem is addressed. Based on the measurement model, we present the constrained weighted least squares (CWLS) approach, which is difficult to be solved directly due to its nonconvex nature. However, by performing the semidefinite relaxation (SDR) technique, the CWLS problem can be relaxed into a semidefinite programming problem (SDP), which can be efficiently solved using modern convex optimization algorithms. Moreover, the SDR is proved to be tight, and hence ensures the corresponding SDP find the optimal solution of the original CWLS problem. Numerical simulations are included to corroborate the theoretical results and promising performance.