Hop-timing detection is of extreme importance for the reception of frequency hopping (FH) signals. Any error in the hop-timing detection has a deleterious effect on the performance of the receiver in frequency hopping (FH) communication systems. However, it is not easy to detect the hop-timing under low signal to noise power ratio (SNR) environments. Adaptive array antennas (AAA) have been expected to improve the performance of FH communication systems by beamforming for the direction of arrival of the desired signal. Since the conventional AAA exploits at least the coarse synchronization for dehopping of FH signals before achieving the beamforming, any fault in the hop-timing detection causes the deterioration of the performance of AAA. Using AAA based on the constant modulus algorithm (CMA), this paper proposes a new method for blind beamforming and hop-timing detection for FH signals. The proposed method exploits both the spatial and temporal characteristics of the received signal to accomplish the beamforming and detect the hop-timing without knowing any a priori information such as fine/coarse time synchronization and training signal. The performance verifications of the proposed method based on pertinent simulations are presented.

Power-aware X-filling is a preferable approach to avoiding IR-drop-induced yield loss in at-speed scan testing. However, the ability of previous X-filling methods to reduce launch switching activity may be unsatisfactory, due to low effect (insufficient and global-only reduction) and/or low scalability (long CPU time). This paper addresses this reduction quality problem with a novel GA (Genetic Algorithm) based X-filling method, called GA-fill. Its goals are (1) to achieve both effectiveness and scalability in a more balanced manner and (2) to make the reduction effect of launch switching activity more concentrated on critical areas that have higher impact on IR-drop-induced yield loss. Evaluation experiments are being conducted on both benchmark and industrial circuits, and the results have demonstrated the usefulness of GA-fill.

In this paper, we present a numerical method for the equiripple approximation of IIR digital filters. The conventional rational Remez algorithm quickly finds the squared magnitude response of the optimal IIR digital filters, and then by factorizing it the equiripple filter is obtained. Unlike the original Remez algorithm for FIR filters, it is difficult for the rational Remez algorithm to explicitly control the ratio of ripples between different bands. In the conventional lowpass filter design, for example, when different weights are given for its passband and stopband, one needs to iteratively design the filter by manually changing the weights in order to achieve the ratio of the weights exactly. To address this problem, we modify the conventional algorithm and make it possible to directly control the ripple ratio. The method iteratively solves eigenvalue problems with controlling the ripple ratio. Using this method, the equiripple solutions with desired weights are obtained automatically.

The Medium Access Control (MAC) protocol that uses non-overlapping multiple channels, called the multi-channel MAC protocol, was proposed in order to increase the capacity of ad hoc networks. Since the number of packet interfaces on each node is less than the number of channels in ad hoc networks in general, the node needs to select a suitable channel for data transmission. This means that the multi-channel MAC protocol must be provided with a good channel selection algorithm. In this paper, we design a channel selection algorithm called Conditionally Randomized Channel Selection (CRCS) based on Extended Receiver Directed Transmission (xRDT) protocol that only uses one packet interface. Briefly, CRCS uses the acitve channel for data transmission until the amount of data packets reaches a threshold, at which point it selects one of the available channels other than the active channel. Although CRCS is a very simple channel selection algorithm, by using network simulator we find that CRCS is effective to increase the capacity of ad hoc networks and to keep the load balance of all channels compared to the other channel selection algorithms.

This paper creates a new hybrid Space-Time Adaptive Processing (STAP) algorithm that combines Direct Data Domain (D3) method and Space-Time Multiple-Beam (STMB) algorithm, which can effectively suppress discrete interference in the nonhomogeneous clutter environment. In the proposed hybrid algorithm, the D3 method is applied to process the discrete interference in the primary range cell, and the residual clutter is suppressed by the STMB algorithm. The performance of the proposed hybrid STAP algorithm is demonstrated in a simulation.

In femto/macro cellular networks, the stability and fairness problems caused by the unplanned and random characteristic of femtocells must be solved. By applying queueing theory in IP based femto/macro cellular networks, we found the stability condition, and described two kinds of cell section policies of users. As a main contribution, we provided the adaptive channel distribution algorithm which minimizes the average packet sojourn time at transmitting systems and keeps the whole systems stable and fair among cells. Through experiments in various environments, we analyzed the influence of channel reuse factor, cell selection policies, and the number of femtocells on system performance.

In this paper, the performance of the induced dimension reduction (IDR) method implemented along with the method of moments (MoM) is described. The MoM is based on a combined field integral equation for solving large-scale electromagnetic scattering problems involving conducting objects. The IDR method is one of Krylov subspace methods. This method was initially developed by Peter Sonneveld in 1979; it was subsequently generalized to the IDR(s) method. The method has recently attracted considerable attention in the field of computational physics. However, the performance of the IDR(s) has hardly been studied or practiced for electromagnetic wave problems. In this study, the performance of the IDR(s) is investigated and clarified by comparing the convergence property and memory requirement of the IDR(s) with those of other representative Krylov solvers such as biconjugate gradient (BiCG) methods and generalized minimal residual algorithm (GMRES). Numerical experiments reveal that the characteristics of the IDR(s) against the parameter s strongly depend on the geometry of the problem; in a problem with a complex geometry, s should be set to an adequately small value in order to avoid the "spurious convergence" which is a problem that the IDR(s) inherently holds. As for the convergence behavior, we observe that the IDR(s) has a better convergence ability than GPBiCG and GMRES(m) in a variety of problems with different complexities. Furthermore, we also confirm the IDR(s)'s inherent advantage in terms of the memory requirements over GMRES(m).

The firefighter problem is used to model the spread of fire, infectious diseases, and computer viruses. This paper deals with firefighter problem on rooted trees. It is known that the firefighter problem is NP-hard even for rooted trees of maximum degree 3. We propose techniques to improve a given approximation algorithm. First, we introduce an implicit enumeration technique. By applying the technique to existing ()-approximation algorithm, we obtain -approximation algorithm when a root has k children. In case of ternary trees, k=3 and thus the approximation ratio satisfies ≥ 0.6892, which improves the existing result ≥ 0.6321. Second technique is based on backward induction and improves an approximation algorithm for firefighter problem on ternary trees. If we apply the technique to existing () -approximation algorithm, we obtain 0.6976-approximation algorithm. Lastly, we combine the above two techniques and obtain 0.7144-approximation algorithm for firefighter problem on ternary trees.

In a rooted graph, a vertex is designated as its root. An outerplanar graph is represented by a plane embedding such that all vertices appear along its outer boundary. Two different plane embeddings of a rooted outerplanar graphs are called symmetric copies. Given integers n ≥ 3 and g ≥ 3, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted outerplanar graphs with exactly n vertices such that the size of each inner face is at most g without delivering two symmetric copies of the same graph.

In a rooted triangulated planar graph, an outer vertex and two outer edges incident to it are designated as its root, respectively. Two plane embeddings of rooted triangulated planar graphs are defined to be equivalent if they admit an isomorphism such that the designated roots correspond to each other. Given a positive integer n, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted triangulated planar graphs with at most n vertices without delivering two reflectively symmetric copies.

The traditional spectrum auctions require a central auctioneer. Then, the secondary users (SUs) can bid for spectrum in multiple auction or sealed auction way. In this paper, we address the problem of distributed spectrum sharing in the cognitive networks where multiple owners sell their spare bands to multiple SUs. Each SU equips multi-interface/multi-radio, so that SU can buy spare bands from multiple owners. On the other hand, each owner can sell its spare bands to serval SUs. There are two questions to be addressed for such an environment: the first one is how to select bands/the owners for each SU; the second one is how to decide the competitive prices for the multiple owners and multiple SUs. To this end, we propose a two-side multi-band market game theoretic framework to jointly consider the benefits of all SUs and owners. The equilibrium concept in such games is named core. The outcomes in the core of the game cannot be improved upon by any subset of players. These outcomes correspond exactly to the price-lists that competitively balance the benefits of all SUs and owners. We show that the core in our model is always non-empty. When the measurement of price takes discrete value, the core of the game is defined as discrete core. The Dynamic Multi-band Sharing algorithm (DMS) is proposed to converge to the discrete core of the game. With small enough measurement unit of price, the algorithm can achieve the optimal performance compared with centralized one in terms of the system utility.

This paper proposes a new approach for the joint processing of signal detection and channel estimation based on the expectation-maximization (EM) algorithm in orthogonal frequency division multiplexing (OFDM) mobile communications. Conventional schemes based on the EM algorithm estimate a channel impulse response using Kalman filter, and employ the random walk model or the first-order autoregressive (AR) model to derive the process equation for the filter. Since these models assume that the time-variation of the impulse response is white noise without considering any autocorrelation property, the accuracy of the channel estimation deteriorates under fast-fading conditions, resulting in an increased packet error rate (PER). To improve the accuracy of the estimation of fast-fading channels, the proposed scheme employs a differential model that allows the correlated time-variation to be considered by introducing the first- and higher-order time differentials of the channel impulse response. In addition, this paper derives a forward recursive form of the channel estimation along both the frequency and time axes in order to reduce the computational complexity. Computer simulations of channels under fast multipath fading conditions demonstrate that the proposed method is superior in PER to the conventional schemes that employ the random walk model.

Let C be a set of colors, and let ω(c) be an integer cost assigned to a color c in C. An edge-coloring of a graph G is to color all the edges of G so that any two adjacent edges are colored with different colors in C. The cost ω(f) of an edge-coloring f of G is the sum of costs ω(f(e)) of colors f(e) assigned to all edges e in G. An edge-coloring f of G is optimal if ω(f) is minimum among all edge-colorings of G. In this paper, we show that the problem of finding an optimal edge-coloring of a tree T can be simply reduced in polynomial time to the minimum weight perfect matching problem for a new bipartite graph constructed from T. The reduction immediately yields an efficient simple algorithm to find an optimal edge-coloring of T in time O(n1.5Δlog(nNω)), where n is the number of vertices in T, Δ is the maximum degree of T, and Nω is the maximum absolute cost |ω(c)| of colors c in C. We then show that our result can be extended for multitrees.

The Towers of Hanoi problem is a classical problem in puzzles, games, mathematics, data structures, and algorithms. In this letter, a least memory used algorithm is proposed by combining the source array and target array for comparing the sizes of disk and labeling the disks in the towers of Hanoi problem. As a result, the proposed algorithm reduces the space needed from 2n+2 to n+5, where n represents the disks number.

We study problems in computational geometry from the viewpoint of adaptive algorithms. Adaptive algorithms have been extensively studied for the sorting problem, and in this paper we generalize the framework to geometric problems. To this end, we think of geometric problems as permutation (or rearrangement) problems of arrays, and define the "presortedness" as a distance from the input array to the desired output array. We call an algorithm adaptive if it runs faster when a given input array is closer to the desired output, and furthermore it does not make use of any information of the presortedness. As a case study, we look into the planar convex hull problem for which we discover two natural formulations as permutation problems. An interesting phenomenon that we prove is that for one formulation the problem can be solved adaptively, but for the other formulation no adaptive algorithm can be better than an optimal output-sensitive algorithm for the planar convex hull problem. To further pursue the possibility of adaptive computational geometry, we also consider constructing a kd-tree.

In bistatic radar, it is important to suppress the undesired signals such as the direct propagated signal from transmitter and its multipath components. Conventionally, some suppression methods have been proposed. They are categorized into the method using a feedback system and the method which subtracts the replicas of the undesired signals. The former method may have the problem on the convergence of the suppression performance. The latter method requires the precise delay times of the undesired signals. In this paper we propose a new method to detect the target in digital terrestrial TV-based bistatic radar which is based on orthogonal frequency division multiplexing (OFDM), without any information on the undesired signals' delay times. In the proposed method, we adapt a scheme based on maximum signal to noise ratio (MSN) algorithm, which makes signal to interference plus noise ratio (SINR) maximum for the desired signal component. The maximum sensitivity is steered so as to match the path that exhibits the delay which relates to the target position, as if the search beam is steered along the direction in array signal processing. In the proposed method, "nulls" are also formed for other delay components to be suppressed simultaneously. In the frequency domain, the carrier components of the scattered signal divided by those of the reference signal indicate the delays caused by scattering. We call these divided carrier components "normalized received signal." The steered sensitivity and nulls are created by the weight which is applied to the normalized received signal in the frequency domain. We obtain the method to estimate the weight to achieve the maximum SINR in the delay estimation which also includes the compensation for the reduction of the weight's length caused by decorrelation among the delay components. The simulation results show that our proposed method without any information on the undesired signal's delays provides sufficient detection performance for the typical target compared to the conventional one.

This paper presents flexible inner-outer Krylov subspace methods, which are implemented using the fast multipole method (FMM) for solving scattering problems with mixed dielectric and conducting object. The flexible Krylov subspace methods refer to a class of methods that accept variable preconditioning. To obtain the maximum efficiency of the inner-outer methods, it is desirable to compute the inner iterations with the least possible effort. Hence, generally, inaccurate matrix-vector multiplication (MVM) is performed in the inner solver within a short computation time. This is realized by using a particular feature of the multipole techniques. The accuracy and computational cost of the FMM can be controlled by appropriately selecting the truncation number, which indicates the number of multipoles used to express far-field interactions. On the basis of the abovementioned fact, we construct a less-accurate but much cheaper version of the FMM by intentionally setting the truncation number to a sufficiently low value, and then use it for the computation of inaccurate MVM in the inner solver. However, there exists no definite rule for determining the suitable level of accuracy for the FMM within the inner solver. The main focus of this study is to clarify the relationship between the overall efficiency of the flexible inner-outer Krylov solver and the accuracy of the FMM within the inner solver. Numerical experiments reveal that there exits an optimal accuracy level for the FMM within the inner solver, and that a moderately accurate FMM operator serves as the optimal preconditioner.

Inter-vehicle communication (IVC) system using 700 MHz band to prevent car crashes has been proposed recently. In this paper, we first apply the FDTD method to the analyses of propagation characteristics at an intersection for IVC. We investigate the propagation characteristics considering the electrical conductivities, thickness and windows of building wall and pedestrians. As a result, it is shown that the electrical conductivities and thickness of building wall have a slight influence. In contrast, windows and pedestrians have a great influence on the propagation characteristics. Furthermore, the azimuth delay profiles are obtained by using the MUSIC algorithm.

Routing is still a challenging issue for wireless sensor networks (WSNs), in particular for WSNs with a non-uniform deployment of nodes. This paper introduces a Node Aggregation Degree-aware Random Routing (NADRR) algorithm for non-uniform WSNs with the help of two new concepts, namely the Local Vertical Aggregation Degree (LVAD) and Local Horizontal Aggregation Degree (LHAD). Our basic idea is to first apply the LVAD and LHAD to determine one size-proper forwarding region (rather than a fixed-size one as in uniform node deployment case) for each node participating in routing, then select the next hop node from the size-proper forwarding region in a probabilistic way, considering both the residual energy and distribution of nodes. In this way, a good adaptability to the non-uniform deployment of nodes can be guaranteed by the new routing algorithm. Extensive simulation results show that in comparison with other classical geographic position based routing algorithms, such as GPSR, TPGF and CR, the proposed NADRR algorithm can result in lower node energy consumption, better balance of node energy consumption, higher routing success rate and longer network lifetime.

Recently, pairing-based cryptographic application sch-emes have attracted much attentions. In order to make the schemes more efficient, not only pairing algorithm but also arithmetic operations in extension field need to be efficient. For this purpose, the authors have proposed a series of cyclic vector multiplication algorithms (CVMAs) corresponding to the adopted bases such as type-I optimal normal basis (ONB). Note here that every basis adapted for the conventional CVMAs are just special classes of Gauss period normal bases (GNBs). In general, GNB is characterized with a certain positive integer h in addition to characteristic p and extension degree m, namely type-⟨h.m⟩ GNB in extension field Fpm. The parameter h needs to satisfy some conditions and such a positive integer h infinitely exists. From the viewpoint of the calculation cost of CVMA, it is preferred to be small. Thus, the minimal one denoted by hmin will be adapted. This paper focuses on two remaining problems: 1) CVMA has not been expanded for general GNBs yet and 2) the minimal hmin sometimes becomes large and it causes an inefficient case. First, this paper expands CVMA for general GNBs. It will improve some critical cases with large hmin reported in the conventional works. After that, this paper shows a theorem that, for a fixed prime number r, other prime numbers modulo r uniformly distribute between 1 to r-1. Then, based on this theorem, the existence probability of type-⟨hmin,m⟩ GNB in Fpm and also the expected value of hmin are explicitly given.