Algorithms for Routing and Centralized Scheduling in IEEE 802.16 Mesh Networks

IEEE 802.16 standards for Wireless Metropolitan Area Networks (WMANs) include a mesh mode of operation for improving the coverage and throughput of the network. In this paper, we consider the problem of routing and centralized scheduling for such networks. We first fix the routing, which reduces the network to a tree. We then present a finite horizon dynamic programming framework. Using it we obtain various scheduling algorithms depending upon the cost function. Next we consider simpler suboptimal algorithms and compare their performances.

On generating optimal signal probabilities for random tests: A genetic approach

Genetic Algorithms are robust search and optimization techniques. A Genetic Algorithm based approach for determining the optimal input distributions for generating random test vectors is proposed in the paper. A cost function based on the COP testability measure for determining the efficacy of the input distributions is discussed, A brief overview of Genetic Algorithms (GAs) and the specific details of our implementation are described. Experimental results based on ISCAS-85 benchmark circuits are presented. The performance pf our GA-based approach is compared with previous results. While the GA generates more efficient input distributions than the previous methods which are based on gradient descent search, the overheads of the GA in computing the input distributions are larger. To account for the relatively quick convergence of the gradient descent methods, we analyze the landscape of the COP-based cost function. We prove that the cost function is unimodal in the search space. This feature makes the cost function amenable to optimization by gradient-descent techniques as compared to random search methods such as Genetic Algorithms.

Probabilistic design of retaining walls.

Retaining walls are one of the important structures in nearshore environment and are generally designed based on deterministic approaches. The present paper focuses on the reliability assessment of cantilever retaining walls with due consideration to the uncertainties in soil parameters. Reliability analysis quantifies the level of reliability associated with designs and the associated risk. It also gives the formalisation of a design situation that is normally recognised by experienced designers and provides a greater level of consistency in design. The results are also examined in terms of a simple cost function. The study shows that sliding mode is the critical failure mode and the consequent failure costs are also higher. The study also shows that provision of shear key results in improved reliability and reduction in expected costs.

A risk-estimation-based formulation for speech enhancement and its relation to Wiener filtering

The goal of speech enhancement algorithms is to provide an estimate of clean speech starting from noisy observations. The often-employed cost function is the mean square error (MSE). However, the MSE can never be computed in practice. Therefore, it becomes necessary to find practical alternatives to the MSE. In image denoising problems, the cost function (also referred to as risk) is often replaced by an unbiased estimator. Motivated by this approach, we reformulate the problem of speech enhancement from the perspective of risk minimization. Some recent contributions in risk estimation have employed Stein's unbiased risk estimator (SURE) together with a parametric denoising function, which is a linear expansion of threshold/bases (LET). We show that the first-order case of SURE-LET results in a Wiener-filter type solution if the denoising function is made frequency-dependent. We also provide enhancement results obtained with both techniques and characterize the improvement by means of local as well as global SNR calculations.

Channel estimation relying on the minimum bit-error-ratio criterion for BPSK and QPSK signals

The authors consider the channel estimation problem in the context of a linear equaliser designed for a frequency selective channel, which relies on the minimum bit-error-ratio (MBER) optimisation framework. Previous literature has shown that the MBER-based signal detection may outperform its minimum-mean-square-error (MMSE) counterpart in the bit-error-ratio performance sense. In this study, they develop a framework for channel estimation by first discretising the parameter space and then posing it as a detection problem. Explicitly, the MBER cost function (CF) is derived and its performance studied, when transmitting binary phase shift keying (BPSK) and quadrature phase shift keying (QPSK) signals. It is demonstrated that the MBER based CF aided scheme is capable of outperforming existing MMSE, least square-based solutions.

Robust Reentry Guidance of a Reusable Launch Vehicle Using Model Predictive Static Programming

A robust suboptimal reentry guidance scheme is presented for a reusable launch vehicle using the recently developed, computationally efficient model predictive static programming. The formulation uses the nonlinear vehicle dynamics with a spherical and rotating Earth, hard constraints for desired terminal conditions, and an innovative cost function having several components with associated weighting factors that can account for path and control constraints in a soft constraint manner, thereby leading to smooth solutions of the guidance parameters. The proposed guidance essentially shapes the trajectory of the vehicle by computing the necessary angle of attack and bank angle that the vehicle should execute. The path constraints are the structural load constraint, thermal load constraint, bounds on the angle of attack, and bounds on the bank angle. In addition, the terminal constraints include the three-dimensional position and velocity vector components at the end of the reentry. Whereas the angle-of-attack command is generated directly, the bank angle command is generated by first generating the required heading angle history and then using it in a dynamic inversion loop considering the heading angle dynamics. Such a two-loop synthesis of bank angle leads to better management of the vehicle trajectory and avoids mathematical complexity as well. Moreover, all bank angle maneuvers have been confined to the middle of the trajectory and the vehicle ends the reentry segment with near-zero bank angle, which is quite desirable. It has also been demonstrated that the proposed guidance has sufficient robustness for state perturbations as well as parametric uncertainties in the model.

Optical Flow based on Approximate Nearest Neighbor Field

In this work, we propose an algorithm for optical flow estimation using Approximate Nearest Neighbor Fields (ANNF). Proposed optical flow estimation algorithm consists of two steps, flow initialization using ANNF maps and cost filtering. Flow initialization is done by computing the ANNF map using FeatureMatch between two consecutive frames. The ANNF map obtained represents a noisy optical flow, which is refined by making use of superpixels. The best flow associated with each superpixel is computed by optimizing a cost function. The proposed approach is evaluated on Middlebury and MPI-Sintel optical flow dataset and is found to be comparable with the state of the art methods for optical flow estimation.

Simultaneous perturbation methods for adaptive labor staffing in service systems

We consider the problem of optimizing the workforce of a service system. Adapting the staffing levels in such systems is non-trivial due to large variations in workload and the large number of system parameters do not allow for a brute force search. Further, because these parameters change on a weekly basis, the optimization should not take longer than a few hours. Our aim is to find the optimum staffing levels from a discrete high-dimensional parameter set, that minimizes the long run average of the single-stage cost function, while adhering to the constraints relating to queue stability and service-level agreement (SLA) compliance. The single-stage cost function balances the conflicting objectives of utilizing workers better and attaining the target SLAs. We formulate this problem as a constrained parameterized Markov cost process parameterized by the (discrete) staffing levels. We propose novel simultaneous perturbation stochastic approximation (SPSA)-based algorithms for solving the above problem. The algorithms include both first-order as well as second-order methods and incorporate SPSA-based gradient/Hessian estimates for primal descent, while performing dual ascent for the Lagrange multipliers. Both algorithms are online and update the staffing levels in an incremental fashion. Further, they involve a certain generalized smooth projection operator, which is essential to project the continuous-valued worker parameter tuned by our algorithms onto the discrete set. The smoothness is necessary to ensure that the underlying transition dynamics of the constrained Markov cost process is itself smooth (as a function of the continuous-valued parameter): a critical requirement to prove the convergence of both algorithms. We validate our algorithms via performance simulations based on data from five real-life service systems. For the sake of comparison, we also implement a scatter search based algorithm using state-of-the-art optimization tool-kit OptQuest. From the experiments, we observe that both our algorithms converge empirically and consistently outperform OptQuest in most of the settings considered. This finding coupled with the computational advantage of our algorithms make them amenable for adaptive labor staffing in real-life service systems.

Accelerating Information Diffusion in Social Networks Under the Susceptible-Infected-Susceptible Epidemic Model

Standard Susceptible-Infected-Susceptible (SIS) epidemic models assume that a message spreads from the infected to the susceptible nodes due to only susceptible-infected epidemic contact. We modify the standard SIS epidemic model to include direct recruitment of susceptible individuals to the infected class at a constant rate (independent of epidemic contacts), to accelerate information spreading in a social network. Such recruitment can be carried out by placing advertisements in the media. We provide a closed form analytical solution for system evolution in the proposed model and use it to study campaigning in two different scenarios. In the first, the net cost function is a linear combination of the reward due to extent of information diffusion and the cost due to application of control. In the second, the campaign budget is fixed. Results reveal the effectiveness of the proposed system in accelerating and improving the extent of information diffusion. Our work is useful for devising effective strategies for product marketing and political/social-awareness/crowd-funding campaigns that target individuals in a social network.

Sampling Period Selection of Control Application Connected to FlexRay Bus

Flexray is a high speed communication protocol designed for distributive control in automotive control applications. Control performance not only depends on the control algorithm but also on the scheduling constraints in communication. A balance between the control performance and communication constraints must required for the choice of the sampling rates of the control loops in a node. In this paper, an optimum sampling period of control loops to minimize the cost function, satisfying the scheduling constraints is obtained. An algorithm to obtain the delay in service of each task in a node of the control loop in the hyper period has been also developed. (C) 2015 The Authors. Published by Elsevier B.V.

PLUTO plus : Near-Complete Modeling of Affine Transformations for Parallelism and Locality

Affine transformations have proven to be very powerful for loop restructuring due to their ability to model a very wide range of transformations. A single multi-dimensional affine function can represent a long and complex sequence of simpler transformations. Existing affine transformation frameworks like the Pluto algorithm, that include a cost function for modern multicore architectures where coarse-grained parallelism and locality are crucial, consider only a sub-space of transformations to avoid a combinatorial explosion in finding the transformations. The ensuing practical tradeoffs lead to the exclusion of certain useful transformations, in particular, transformation compositions involving loop reversals and loop skewing by negative factors. In this paper, we propose an approach to address this limitation by modeling a much larger space of affine transformations in conjunction with the Pluto algorithm's cost function. We perform an experimental evaluation of both, the effect on compilation time, and performance of generated codes. The evaluation shows that our new framework, Pluto+, provides no degradation in performance in any of the Polybench benchmarks. For Lattice Boltzmann Method (LBM) codes with periodic boundary conditions, it provides a mean speedup of 1.33x over Pluto. We also show that Pluto+ does not increase compile times significantly. Experimental results on Polybench show that Pluto+ increases overall polyhedral source-to-source optimization time only by 15%. In cases where it improves execution time significantly, it increased polyhedral optimization time only by 2.04x.

Selection of Optimal Time-to-go in Generalized Vector Explicit Guidance

A new method of selection of time-to-go (t(go)) for Generalized Vector Explicit Guidance (GENEX) law have been proposed in this paper. t(go) is known to be an important parameter in the control and cost function of GENEX guidance law. In this paper the formulation has been done to find an optimal value of t(go) that minimizes the performance cost. Mechanization of GENEX with this optimal t(go) reduces the lateral acceleration demand and consequently increases the range of the interceptor. This new formulation of computing t(go) comes in closed form and thus it can be implemented onboard. This new formulation is applied in the terminal phase of an surface-to-air interceptor for an angle constrained engagement. Results generated by simulation justify the use of optimal t(go).

IMAGE DENOISING IN MULTIPLICATIVE NOISE

We address the problem of denoising images corrupted by multiplicative noise. The noise is assumed to follow a Gamma distribution. Compared with additive noise distortion, the effect of multiplicative noise on the visual quality of images is quite severe. We consider the mean-square error (MSE) cost function and derive an expression for an unbiased estimate of the MSE. The resulting multiplicative noise unbiased risk estimator is referred to as MURE. The denoising operation is performed in the wavelet domain by considering the image-domain MURE. The parameters of the denoising function (typically, a shrinkage of wavelet coefficients) are optimized for by minimizing MURE. We show that MURE is accurate and close to the oracle MSE. This makes MURE-based image denoising reliable and on par with oracle-MSE-based estimates. Analogous to the other popular risk estimation approaches developed for additive, Poisson, and chi-squared noise degradations, the proposed approach does not assume any prior on the underlying noise-free image. We report denoising results for various noise levels and show that the quality of denoising obtained is on par with the oracle result and better than that obtained using some state-of-the-art denoisers.

Discriminative language model adaptation for Mandarin broadcast speech transcription and translation

This paper investigates unsupervised test-time adaptation of language models (LM) using discriminative methods for a Mandarin broadcast speech transcription and translation task. A standard approach to adapt interpolated language models to is to optimize the component weights by minimizing the perplexity on supervision data. This is a widely made approximation for language modeling in automatic speech recognition (ASR) systems. For speech translation tasks, it is unclear whether a strong correlation still exists between perplexity and various forms of error cost functions in recognition and translation stages. The proposed minimum Bayes risk (MBR) based approach provides a flexible framework for unsupervised LM adaptation. It generalizes to a variety of forms of recognition and translation error metrics. LM adaptation is performed at the audio document level using either the character error rate (CER), or translation edit rate (TER) as the cost function. An efficient parameter estimation scheme using the extended Baum-Welch (EBW) algorithm is proposed. Experimental results on a state-of-the-art speech recognition and translation system are presented. The MBR adapted language models gave the best recognition and translation performance and reduced the TER score by up to 0.54% absolute. © 2007 IEEE.

Towards a perceptually optimal spectral amplitude estimator for audio signal enhancement

We present a statistical model-based approach to signal enhancement in the case of additive broadband noise. Because broadband noise is localised in neither time nor frequency, its removal is one of the most pervasive and difficult signal enhancement tasks. In order to improve perceived signal quality, we take advantage of human perception and define a best estimate of the original signal in terms of a cost function incorporating perceptual optimality criteria. We derive the resultant signal estimator and implement it in a short-time spectral attenuation framework. Audio examples, references, and further information may be found at http://www-sigproc.eng.cam.ac.uk/~pjw47.