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.

This paper proposes an adaptive antenna using a combination of on-off and CMA algorithms. With the proposed technique, the on-off algorithm is first employed to search for a desired signal direction in which maximum received power is achieved. Then, interference is suppressed by performing CMA. Simulations are conducted according to the potential application of the proposed adaptive antenna. The simulation results show the SINR improvement implying that the proposed adaptive antenna can be applied to microwave RFID systems in order to resolve reader collision. Furthermore, the proposed adaptive antenna is implemented and then experimented. The experimental results verify that the proposed adaptive antenna can reduce interference resulting in the collision problem.

Recent works on MIMO receiver design were mainly focused on sphere decoding, which provides a trade-off between the performance and complexity by suitably choosing the “radius” or the number of candidates in the search space. Meanwhile, another approach, called poly-diagonalization and trellis detection, has been proposed to compromise the complexity and performance. In this paper, we compare various MIMO receiver algorithms in terms of both performance and complexity. The performance is evaluated in a frequency selective fading channel environment on the basis of orthogonal frequency division multiplexing with channel coding, for which the generation of soft decision values is crucial. The simulations show that the poly-diagonalization approach matches the performance of sphere decoding at similar computational complexity.

Network on Chip (NoC) is proposed as a new intra-chip communication infrastructure. In current NoC design, one related problem is mapping IP cores onto NoC architectures. In this paper, we propose a performance-aware hybrid algorithm (PHA) for mesh-based NoC to optimize performance indexes such as latency, energy consumption and maximal link bandwidth. The PHA is a hybrid algorithm, which integrates the advantages of Greedy Algorithm, Genetic Algorithm and Simulated Annealing Algorithm. In the PHA, there are three features. First, it generates a fine initial population efficiently in a greedy swap way. Second, effective global parallel search is implemented by genetic operations such as crossover and mutation, which are implemented with adaptive probabilities according to the diversity of population. Third, probabilistic acceptance of a worse solution using simulated annealing method greatly improves the performance of local search. Compared with several previous mapping algorithms such as MOGA and TGA, simulation results show that our algorithm enhances the performance by 30.7%, 23.1% and 25.2% in energy consumption, latency and maximal link bandwidth respectively. Moreover, simulation results demonstrate that our PHA approach has the highest convergence speed among the three algorithms. These results show that our proposed mapping algorithm is more effective and efficient.

The aggregate throughput of wireless mesh networks (WMNs) can be significantly improved by equipping the mesh routers with multiple radios tuned to orthogonal channels. Not only the links using orthogonal channels can be activated at a time, but some links in the same channel also can be activated concurrently if the Signal-to-Interference-and-Noise Ratio (SINR) at their receivers is not lower than the threshold, which is the spatial-reuse characteristic. STDMA is considered as one of the medium access schemes that can exploit spatial reuse to improve network throughput. Past studies have shown that optimizing the performance of STDMA is NP-Hard. Therefore, we propose a STDMA-based scheduling algorithm that operates in a greedy fashion for WMNs. We show that the proposed algorithm enhances not only the throughput but also the fairness by capturing the essence of spatial-reuse approach of STDMA and giving medium access opportunities to each network element based on its priority. We furthermore validate our algorithm through theoretical analysis and extensive simulations and the results show that our algorithm can outperform state-of-the-art alternatives.

A zig-zag Gardner algorithm with parallel architecture is presented in this letter. This algorithm performs timing adjustment in each individual burst independently for high speed wireless burst communication with a short guard. Over sampling data are stored in RAM initially and read forward and backward alternately later. The proposed algorithm has distinct symmetric characteristic in the forward and backward process, which makes the alternate sequences achieve nearly the same effect as a continuous sequence. The performance of the proposed algorithm is very close to the theoretical curve.

Vehicle routing is an important combinatorial optimization problem. In real transport networks,the travel speed and travel time of roads have large time-variability and randomness. The study of vehicle routing problem in time-dependent network has even more practical value than static network VRP problem. This paper combines the features of time-dependent networks and gives the mathematical models of the time-dependent vehicle routing problem. On this basis, the traditional ant colony optimization algorithm is improved. A new path transfer strategy of ants and new dynamic pheromone update strategy applicable to time-dependent network are proposed. Based on these strategies, the improved ant colony algorithm is given for solving the vehicle routing problem in time-dependent networks. The simulation results show that the algorithm can effectively solve the vehicle routing problem in time-dependent network and has better computational efficiency and convergence speed.

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.

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.

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 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.

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.

This research aims to accelerate the computation module in max-plus algebra using CUDA technology on graphics processing units (GPUs) designed for high-performance computing. Our target is the Kleene star of a weighted adjacency matrix for directed acyclic graphs (DAGs). Using a inexpensive GPU card for our experiments, we obtained more than a 16-fold speedup compared with an Athlon 64 X2.

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.

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.

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.

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).

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.

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.