Search

Ohya and Volovich discussed a quantum algorithm for the SAT problem with a chaos amplification process (OMV SAT algorithm) and showed that the number of steps it performed was polynomial in input size. In this paper, we define a generalized quantum Turing machine (GQTM) and related computational complexity. Then we show that there exists a GQTM which recognizes the SAT problem in polynomial time. Moreover, we discuss the problem of finding the quantum algorithm for a partial recursive function. [ABSTRACT FROM AUTHOR]

In this paper, we present a new computationally efficient and accurate so-called explicit modulated Lagrange adaptive frequency estimation (EMLAFE) algorithm that is based on a variable delay element of Etter and Hush and the modulated Lagrange adaptive frequency estimator (MLAFE) of Dooley and Nandi. Adopting a similar idea as in So et al., on explicit time delay estimation, we introduce explicit frequency estimation in our EMLAFE algorithm in order to speed up the frequency estimation. Our development of the EMLAFE algorithm is based on the fact that the cost function of the modulated Lagrange interpolation delay filter (MLIDF), which is used as a FIR delay system in the frequency estimator, is sinusoidal in form with respect to the product of signal frequency and time delay under a high signal to noise ratio (SNR) condition. This leads to a simple formula relating the estimated delay to the unknown frequency, and thus to an efficient frequency estimator. The superior performance of the new algorithm is demonstrated in the context of tracking and estimating a chirp or constant frequency signal in noise. We also derive the Cramér-Rao bound and the steady state variance, for the frequency estimate. [ABSTRACT FROM AUTHOR]

In this paper, we address the error probability performance of space-time block coded system (STBC) in multipath Rayleigh fading channel. We consider STBC with rate one for two transmit antennae and rate half for three transmit antennae, and present an optimal maximum-likelihood-sequence-estimation (MLSE) and a block-by-block suboptimum decoding receiver structures. The proposed receiver schemes are suitable for short-range wireless communication or wireless personal area network (WPAN), where the delay spread is usually smaller than one symbol period. A reduced-state MLSE receiver with new trellis structure is first developed for the multiple-input multiple-output (MIMO) scenario assuming availability of ideal channel state information (CSI). Then a less complex block-by-block suboptimum decoding algorithm is also developed for the unequalized multipath fading channel, as an alternative to the computationally intensive MLSE. The suboptimum receiver symbol timing is optimized in order to obtain minimum error probability for the general multipath power delay profiles. From our simulation results, we show that our proposed MLSE receiver can mitigate the multipath induced intersymbol interference (ISI) effectively and at bit error rate (BER) of 10-3, a two-transmit and two-receive (2, 2) STBC system gains as much as 11.5 dB in SNR over a single-antenna uncoded system. We also verify that the MLSE receiver always outperforms the suboptimum receiver, as expected. Error floors appear in the BER performance curves of the suboptimum receiver because ISI is not equalized, whereas no such floors appear with the MLSE receiver. [ABSTRACT FROM AUTHOR]

In this paper, we present two improved algorithms to establish lightpaths in a physical topology for the formation of a static WDM virtual topology. One of the major design issues in these networks is the volume of traffic in the intermediate nodes and the number of optical hops between network nodes so that the delay is less and at the same time greater capacity can be achieved. We first present an algorithm that is based on average weighted hop count as objective function to generate connection requests for connecting physical nodes optically. The second algorithm is a lookahead version of our first algorithm. We study the performances of the algorithms with regard to the performance metrics such as number of requests blocked, maximum hops required from a source to destination, maximum traffic to be handled in a node, average intermediate traffic and average spare wavelengths remaining after the completion of the virtual topologies. We find that on the average the lookahead scheme optimizes the objective function better, but at the cost of maximum load in any node. To improve the wavelength utilization we also discuss a wavelength assignment algorithm which uses the best alternate physical path while establishing lightpaths. We have simulated about six thousand random graphs of various sizes and densities to show how our algorithm behaves in comparison to a widely used existing algorithm. [ABSTRACT FROM AUTHOR]

The main goal of a topology control scheme in wireless sensor networks is to reduce node power consumption in order to extend network lifetime. In this paper we present an overview of a range of topology control algorithms proposed in literature for wireless sensor networks. The topology control schemes in most of the existing works can be categorized into two classes: Either multi-state or power-control. We believe that most energy savings might come from turning off redundant nodes rather than by minimizing node transmit power. However, both classes of schemes could be combined for further energy savings. Each algorithm is described in depth and compared against each other to capture their uniqueness. The most important design issues of topology control are also highlighted. [ABSTRACT FROM AUTHOR]

Recent advances in optical networking reveal that large-scale optical networks supporting heterogeneous traffic may soon become economical as the underlying backbone in wide area networks, in which optical routers play a key role. One big challenge in designing future large-scale optical systems is packet scheduling for the core optical routers. The optical router is a delay system with packets waiting at its ingress queues. A scheduler is necessary to allocate resources so that delay and jitter sensitive real-time traffic can be served with higher priority than the non-delay sensitive traffic. The system capacity should also be efficiently utilized. This is achieved by a prioritised non-blocking scalable scheduling algorithm developed in this paper. The proposed algorithm is based on a heuristic approximation of a Linear Integer Programming model. The performance evaluations in a multi-service high capacity core optical router show that the heuristic solution is close to the optimal solution most of the time, yet it is much easier to implement. [ABSTRACT FROM AUTHOR]

In ad-hoc networks the need for a distributed topology control algorithm is being widely recognized. In this paper we propose TC-ADHOC MAC, a medium access algorithm with topology control capabilities. The proposed algorithm aims at maintaining the minimum number of bidirectional neighbors of any wireless terminal very close to a certain connectivity threshold. The correctness of the algorithm is evaluated through detailed simulation and several test on the impact of different algorithm parameters are carried out in static network scenarios. Furthermore, the ability of TC-ADHOC MAC of reusing the radio resources is assessed by a detailed simulation in a dynamic traffic environment. Our results show that the topology control solution integrated at the MAC layer helps increasing the channel reuse and, consequently, the network efficiency. [ABSTRACT FROM AUTHOR]