Abstract.

Abstract.

Abstract. We present an efficient algorithm for regularized optimal transport. In contrast to previous methods, we use the Douglas-Rachford splitting technique to develop an efficient solver that can handle a broad class of regularizers. The algorithm has strong global convergence guarantees, low per-iteration cost, and can exploit GPU parallelization, making it considerably faster than the state-of-the-art for many problems. We illustrate its competitiveness in several applications, including domain adaptation and learning of generative models.

Abstract.

Abstract.

Abstract.

Abstract.

Abstract. In machine learning applications, it is well known that carefully designed learning rate (step size) schedules can significantly improve the convergence of commonly used first-order optimization algorithms. Therefore how to set step size adaptively becomes an important research question. A popular and effective method is the Polyak step size, which set step size adaptively for gradient descent or stochastic gradient descent without the need to estimate the smoothness parameter of the objective function. However, there has not been a principled way to generalize the Polyak step size for algorithms with momentum accelerations. This paper presents a general framework to set the learning rate adaptively for first-order optimization methods with momentum, motivated by the derivation of Polyak step size. It is shown that the resulting methods are much less sensitive to the choice of momentum parameter and may avoid the oscillation of the heavy-ball method on ill-conditioned problems. These adaptive step sizes are further extended to the stochastic settings, which are attractive choices for stochastic gradient descent with momentum. Our methods are demonstrated to be more effective for stochastic gradient methods than prior adaptive step size algorithms in large-scale machine learning tasks.

Abstract. This paper presents informative battery charging, a novel approach for battery model parameter estimation during fast charge. Our solution comprises three distinct contributions: first, we develop a semi-explicit solution to an optimal fast charging problem for equivalent circuit models with health-conscious voltage constraints; second, we design optimal experiments for battery model parameter estimation; and third, we suggest a strategy for how the fast charging and experimentation currents can be combined while still satisfying constraints and maintaining acceptable charging times. Numerical results show that model parameters can be identified with lower variance if an optimal experiment is added to the charging procedure.

Abstract. The curvature-aided IAG (CIAG) algorithm is an efficient asynchronous optimization method that accelerates IAG using a delay compensation technique. However, existing step-size rules for CIAG are conservative and hard to implement, and the Hessian computation in CIAG is often computationally expensive. To alleviate these issues, we first provide an easy-to-implement and less conservative step-size rule for CIAG. Next, we propose a modified CIAG algorithm that reduces the computational complexity by approximating the Hessian with a constant matrix. Convergence results are derived for each algorithm on both convex and strongly convex problems, and numerical experiments on logistic regression demonstrate their effectiveness in practice.

Abstract. Predicting the origin-destination (OD) probability distribution of agent transfer is an important problem for managing complex systems. However, prediction accuracy of associated statistical estimators suffer from underdetermination. While specific techniques have been proposed to overcome this deficiency, there still lacks a general approach. Here, we propose a deep neural network framework with gated recurrent units (DNNGRU) to address this gap. Our DNNGRU is network-free, as it is trained by supervised learning with time-series data on the volume of agents passing through edges. We use it to investigate how network topologies affect OD prediction accuracy, where performance enhancement is observed to depend on the degree of overlap between paths taken by different ODs. By comparing against methods that give exact results, we demonstrate the near-optimal performance of our DNNGRU, which we found to consistently outperform existing methods and alternative neural network architectures, under diverse data generation scenarios.

Abstract. We introduce novel convergence results for asynchronous iterations that appear in the analysis of parallel and distributed optimization algorithms. The results are simple to apply and give explicit estimates for how the degree of asynchrony impacts the convergence rates of the iterates. Our results shorten, streamline and strengthen existing convergence proofs for several asynchronous optimization methods and allow us to establish convergence guarantees for popular algorithms that were thus far lacking a complete theoretical understanding. Specifically, we use our results to derive better iteration complexity bounds for proximal incremental aggregated gradient methods, to obtain tighter guarantees depending on the average rather than maximum delay for the asynchronous stochastic gradient descent method, to provide less conservative analyses of the speedup conditions for asynchronous block-coordinate implementations of Krasnosel'skii–Mann iterations, and to quantify the convergence rates for totally asynchronous iterations under various assumptions on communication delays and update rates.

Abstract. This paper studies the class of logarithmically completely monotonic (LCM) functions. These functions play an important role in characterising externally positive linear systems which find applications in important control problems such as non-overshooting reference tracking. Conditions are proposed to ensure a rational function is LCM, a result that enables the known space of linear continuous-time externally positive systems to be enlarged and an efficient and optimal pole-placement procedure for the monotonic tracking controller synthesis problem to be developed. The presented conditions are shown to be less conservative than existing approaches whilst being computationally tractable.

Abstract. Facing the upcoming era of Internet-of-Things and connected intelligence, efficient information processing, computation, and communication design becomes a key challenge in large-scale intelligent systems. Recently, Over-the-Air (OtA) computation has been proposed for data aggregation and distributed computation of functions over a large set of network nodes. Theoretical foundations for this concept exist for a long time, but it was mainly investigated within the context of wireless sensor networks. There are still many open questions when applying OtA computation in different types of distributed systems where modern wireless communication technology is applied. In this article, we provide a comprehensive overview of the OtA computation principle and its applications in distributed learning, control, and inference systems, for both server-coordinated and fully decentralized architectures. Particularly, we highlight the importance of the statistical heterogeneity of data and wireless channels, the temporal evolution of model updates, and the choice of performance metrics, for the communication design in OtA federated learning (FL) systems. Several key challenges in privacy, security, and robustness aspects of OtA FL are also identified for further investigation.

Abstract. Li-ion batteries in electric vehicles must be utilized more efficiently to lower their economic and environmental cost. To achieve this increase in efficiency, it is of large interest to develop more thorough battery management that can predict internal states in online settings and update usage and control accordingly. Electrochemical models are an important tool in achieving this, and their implementation in battery management systems is the topic of ongoing research. However, electrochemical battery management relies on accurate parametrization and thus requires re-parametrization as a battery ages. We therefore studied viability of re-parametrization for electrochemical model-based battery management. To this end, we performed global sensitivity analysis on selected Doyle–Fuller–Newman model parameters using on-board current measurements. Representative driving data was collected from several types of heavy-duty vehicles. This elucidated which model parameters should be updated periodically to conserve model accuracy and which parameters are sensitive enough to be estimated from the on-board data. Additionally, we studied how parameter uncertainty affects estimation of internal states and highlight how model-based state estimation relying on a beginning-of-life parametrization degrades as electrochemical parameters change with aging.

Abstract. This paper develops an optimization-based synthesis procedure for fixed-order output-feedback controllers, ensuring a stable closed-loop system with a monotonic step response and rejection of persistent disturbances. This result is based on a unified set of external positivity conditions for discrete-time linear systems. The conditions are derived using an alternative technique for the inverse Z-transform of rational transfer functions based on Bell polynomials and a convenient recurrence relation for the impulse response. Our approach yields a necessary and sufficient condition expressed as polynomial inequalities in the transfer function coefficients. Under additional assumptions, we derive a sequence of weaker but numerically more tractable conditions, leading to an efficient controller synthesis procedure.

Abstract. Resource allocation plays a central role in networked systems such as smart grids, communication networks, and urban transportation systems. In these systems, many constraints have physical meaning and infeasible allocations can result in a system breakdown. Hence, algorithms with asymptotic feasibility guarantees can be insufficient since they cannot ensure that an implementable solution is found in finite time. This paper proposes a distributed feasible method (DFM) for resource allocation based on barrier functions. In DFM, every iterate is feasible and safe to implement since it does not violate the physical constraints. We prove that, under mild conditions, DFM converges to an arbitrarily small neighborhood of the optimum. Numerical experiments demonstrate the competitive performance of DFM.

Abstract. Noisy gradient algorithms have emerged as one of the most popular algorithms for distributed optimization with massive data. Choosing proper step-size schedules is an important task to tune in the algorithms for good performance. For the algorithms to attain fast convergence and high accuracy, it is intuitive to use large step-sizes in the initial iterations when the gradient noise is typically small compared to the algorithm-steps, and reduce the step-sizes as the algorithm progresses. This intuition has been confirmed in theory and practice for stochastic gradient descent. However, similar results are lacking for other methods using approximate gradients. This paper shows that the diminishing step-size strategies can indeed be applied for a broad class of noisy gradient algorithms. Our analysis framework is based on two classes of systems that characterize the impact of the step-sizes on the convergence performance of many algorithms. Our results show that such step-size schedules enable these algorithms to enjoy the optimal rate. We exemplify our results on stochastic compression algorithms. Our experiments validate fast convergence of these algorithms with the step decay schedules.

Abstract. Several time-domain constraints for linear systems are characterized using a new representation of the impulse response based on symmetric polynomials. This includes the induced ∞-norm, the peak response and external positivity – performance indices that are complicated to impose in existing LMI frameworks. Each index is described by a convex constraint, explicit in terms of the system poles. Despite their simplicity, numerical examples suggest that these constraints can provide relatively tight performance bounds.

Abstract. Asynchronous optimization algorithms are at the core of modern machine learning and resource allocation systems. However, most convergence results consider bounded information delays and several important algorithms lack guarantees when they operate under total asynchrony. In this paper, we derive explicit convergence rates for the proximal incremental aggregated gradient (PIAG) and the asynchronous block-coordinate descent (Async-BCD) methods under a specific model of total asynchrony, and show that the derived rates are order-optimal. The convergence bounds provide an insightful understanding of how the growth rate of the delays deteriorates the convergence times of the algorithms. Our theoretical findings are demonstrated by a numerical example.

Abstract. We present StochasticPrograms.jl, a user-friendly and powerful open-source framework for stochastic programming written in the Julia language. The framework includes both modeling tools and structure-exploiting optimization algorithms. Stochastic programming models can be efficiently formulated using an expressive syntax, and models can be instantiated, inspected, and analyzed interactively. The framework scales seamlessly to distributed environments. Small instances of a model can be run locally to ensure correctness, whereas larger instances are automatically distributed in a memory-efficient way onto supercomputers or clouds and solved using parallel optimization algorithms. These structure-exploiting solvers are based on variations of the classical L-shaped, progressive-hedging, and quasi-gradient algorithms. We provide a concise mathematical background for the various tools and constructs available in the framework along with code listings exemplifying their usage. Both software innovations related to the implementation of the framework and algorithmic innovations related to the structured solvers are highlighted. We conclude by demonstrating strong scaling properties of the distributed algorithms on numerical benchmarks in a multinode setup.Summary of Contribution: This paper presents StochasticPrograms.jl, an open-source framework for stochastic programming implemented in the Julia programming language. The framework includes an expressive syntax for formulating stochastic programming models as well as versatile analysis tools and parallel optimization algorithms. The framework will prove useful to researchers, educators, and industrial users alike. Researchers will benefit from the readily extensible open-source framework, in which they can formulate complex stochastic models or quickly typeset and test novel optimization algorithms. Educators of stochastic programming will benefit from the clean and expressive syntax. Moreover, the framework supports analysis tools and stochastic programming constructs from classical theory and leading textbooks. We strongly believe that the StochasticPrograms.jl framework can reduce the barrier to entry for incoming practitioners of stochastic programming. Industrial practitioners can make use of StochasticPrograms.jl to rapidly formulate complex models, analyze small instances locally, and then run large-scale instances in production. In doing so, they get distributed capabilities for free without changing the code and access to well-tested state-of-the-art implementations of parallel structure-exploiting solvers. As the framework is open-source, anyone from these target audiences can contribute with new functionality to the framework. In conclusion, by providing both an intuitive interface for new users and an extensive development environment for expert users, StochasticPrograms.jl has strong potential to further the field of stochastic programming.

Abstract. In scalable machine learning systems, model training is often parallelized over multiple nodes that run without tight synchronization. Most analysis results for the related asynchronous algorithms use an upper bound on the information delays in the system to determine learning rates. Not only are such bounds hard to obtain in advance, but they also result in unnecessarily slow convergence. In this paper, we show that it is possible to use learning rates that depend on the actual time-varying delays in the system. We develop general convergence results for delay-adaptive asynchronous iterations and specialize these to proximal incremental gradient descent and block coordinate descent algorithms. For each of these methods, we demonstrate how delays can be measured on-line, present delay-adaptive step-size policies, and illustrate their theoretical and practical advantages over the state-of-the-art.

Abstract. Federated learning is an emerging framework for collaborative machine-learning on devices which do not want to share local data. State-of-the art methods in federated learning reduce the communication frequency, but are not guaranteed to converge to the optimal model parameters. These methods also experience a communication bottleneck, especially when the devices are power-constrained and communicate over a shared medium. This paper presents ECO-FedSplit, an algorithm that increases the communication efficiency of federated learning without sacrificing solution accuracy. The key is to compress inter-device communication and to compensate for information losses in a theoretically justified manner. We prove strong convergence properties of ECO-FedSplit on strongly convex optimization problems and show that the algorithm yields a highly accurate solution with dramatically reduced communication. Extensive numerical experiments validate our theoretical result on real data sets.

Abstract. We develop a fast and reliable method for solving large-scale optimal transport (OT) problems at an unprecedented combination of speed and accuracy. Built on the celebrated Douglas-Rachford splitting technique, our method tackles the original OT problem directly instead of solving an approximate regularized problem, as many state-of-the-art techniques do. This allows us to provide sparse transport plans and avoid numerical issues of methods that use entropic regularization. The algorithm has the same cost per iteration as the popular Sinkhorn method, and each iteration can be executed efficiently, in parallel. The proposed method enjoys an iteration complexity O(1/epsilon) compared to the best-known O(1/epsilon^2) of the Sinkhorn method. In addition, we establish a linear convergence rate for our formulation of the OT problem. We detail an efficient GPU implementation of the proposed method that maintains a primal-dual stopping criterion at no extra cost. Substantial experiments demonstrate the effectiveness of our method, both in terms of computation times and robustness.

Abstract. We present StochasticPrograms.jl, a user-friendly and powerful open-source framework for stochastic programming written in the Julia language. The framework includes both modeling tools and structure-exploiting optimization algorithms. Stochastic programming models can be efficiently formulated using an expressive syntax, and models can be instantiated, inspected, and analyzed interactively. The framework scales seamlessly to distributed environments. Small instances of a model can be run locally to ensure correctness, whereas larger instances are automatically distributed in a memory-efficient way onto supercomputers or clouds and solved using parallel optimization algorithms. These structure-exploiting solvers are based on variations of the classical L-shaped, progressive-hedging, and quasi-gradient algorithms. We provide a concise mathematical background for the various tools and constructs available in the framework along with code listings exemplifying their usage. Both software innovations related to the implementation of the framework and algorithmic innovations related to the structured solvers are highlighted. We conclude by demonstrating strong scaling properties of the distributed algorithms on numerical benchmarks in a multinode setup.Summary of Contribution: This paper presents StochasticPrograms.jl, an open-source framework for stochastic programming implemented in the Julia programming language. The framework includes an expressive syntax for formulating stochastic programming models as well as versatile analysis tools and parallel optimization algorithms. The framework will prove useful to researchers, educators, and industrial users alike. Researchers will benefit from the readily extensible open-source framework, in which they can formulate complex stochastic models or quickly typeset and test novel optimization algorithms. Educators of stochastic programming will benefit from the clean and expressive syntax. Moreover, the framework supports analysis tools and stochastic programming constructs from classical theory and leading textbooks. We strongly believe that the StochasticPrograms.jl framework can reduce the barrier to entry for incoming practitioners of stochastic programming. Industrial practitioners can make use of StochasticPrograms.jl to rapidly formulate complex models, analyze small instances locally, and then run large-scale instances in production. In doing so, they get distributed capabilities for free without changing the code and access to well-tested state-of-the-art implementations of parallel structure-exploiting solvers. As the framework is open-source, anyone from these target audiences can contribute with new functionality to the framework. In conclusion, by providing both an intuitive interface for new users and an extensive development environment for expert users, StochasticPrograms.jl has strong potential to further the field of stochastic programming.

Abstract. Physics-based battery models are important tools in battery research, development, and control. To obtain useful information from the models, accurate parametrization is essential. A complex model structure and many unknown and hard-to-measure parameters make parametrization challenging. Furthermore, numerous applications require non-invasive parametrization relying on parameter estimation from measurements of current and voltage. Parametrization of physics-based battery models from input–output data is a growing research area with many recent publications. This paper aims to bridge the gap between researchers from different fields that work with battery model parametrization, since successful parametrization requires both knowledge of the underlying physical system as well as understanding of theory and concepts behind parameter estimation. The review encompasses sensitivity analyses, methods for parameter optimization, structural and practical identifiability analyses, design of experiments and methods for validation as well as the use of machine learning in parametrization. We highlight that not all model parameters can accurately be identified nor are all relevant for model performance. Nonetheless, no consensus on parameter importance could be shown. Local methods are commonly chosen because of their computational advantages. However, we find that the implications of local methods for analysis of non-linear models are often not sufficiently considered in reviewed literature.

Abstract. We revisit the classical pole-placement controller design problem with the objective of ensuring non-overshooting and error-free reference tracking. To this end, we present a number of novel conditions for external positivity of discrete-time transfer functions which characterise this non-overshooting property. These conditions are both necessary and sufficient for first- and second-order systems, but only sufficient for higher-order systems. In addition, they have simple geometric interpretations in terms of allowed locations of the closed-loop poles. Based on these conditions, we propose a control design procedure that guarantees a stable closed-loop system with non-overshooting, error-free tracking of step changes in the reference.

Abstract. We develop a fast smoothing procedure for solving linear two-stage stochastic programs, which outperforms the well-known L-shaped algorithm on large-scale benchmarks. We derive problem-dependent bounds for the effect of smoothing and characterize the convergence rate of the proposed algorithm. The theory suggests that the smoothing scheme can be sped up by sacrificing accuracy in the final solution. To obtain an efficient and effective method, we suggest a hybrid solution that combines the speed of the smoothing scheme with the accuracy of the L-shaped algorithm. We benchmark a parallel implementation of the smoothing scheme against an efficient parallelized L-shaped algorithm on three large-scale stochastic programs, in a distributed environment with 32 worker cores. The smoothing scheme reduces the solution time by up to an order of magnitude compared to L-shaped.

Abstract. The convergence of stochastic gradient descent is highly dependent on the step-size, especially on non-convex problems such as neural network training. Step decay step-size schedules (constant and then cut) are widely used in practice because of their excellent convergence and generalization qualities, but their theoretical properties are not yet well understood. We provide convergence results for step decay in the non-convex regime, ensuring that the gradient norm vanishes at an O(ln(T)/sqrt(T)) rate. We also provide near-optimal (and sometimes provably tight) convergence guarantees for general, possibly non-smooth, convex and strongly convex problems. The practical efficiency of the step decay step-size is demonstrated in several large-scale deep neural network training tasks.

Abstract. Distributed resource allocation is a central task in network systems such as smart grids, water distribution networks, and urban transportation systems. When solving such problems in practice it is often important to have non-asymptotic feasibility guarantees for the iterates, since overall-location of resources easily causes systems to break down. In this paper, we develop a distributed resource reallocation algorithm where every iteration produces a feasible allocation. The algorithm is fully distributed in the sense that nodes communicate only with neighbors over a given communication network. We prove that under mild conditions the algorithm converges to a point arbitrarily close to the optimal resource allocation. Numerical experiments demonstrate the competitive practical performance of the algorithm.

Abstract. The emergence of big data has caused a dramatic shift in the operating regime for optimization algorithms. The performance bottleneck, which used to be computations, is now often communications. Several gradient compression techniques have been proposed to reduce the communication load at the price of a loss in solution accuracy. Recently, it has been shown how compression errors can be compensated for in the optimization algorithm to improve the solution accuracy. Even though convergence guarantees for error-compensated algorithms have been established, there is very limited theoretical support for quantifying the observed improvements in solution accuracy. In this paper, we show that Hessian-aided error compensation, unlike other existing schemes, avoids accumulation of compression errors on quadratic problems. We also present strong convergence guarantees of Hessian-based error compensation for stochastic gradient descent. Our numerical experiments highlight the benefits of Hessian-based error compensation, and demonstrate that similar convergence improvements are attained when only a diagonal Hessian approximation is used.

Abstract. We study the preservation of impulse response non-negativity, also known as external positivity, for general discretization methods. The results yield new subsets in the space of transfer function coefficients which ensure external positivity. Consequently, linear programming approaches for designing controllers ensuring monotonic step responses are derived for both continuous and discrete-time systems.

Abstract. An explicit relation between the open- and closed-loop system responses is established directly in the time domain by means of Bell polynomials. This relation is used to derive necessary and sufficient conditions on the open-loop impulse response that guarantees that its closed-loop impulse response under unity feedback is non-negative in a given time range. Based on these conditions, a new design technique for PID controllers is presented that guarantees a monotonic closed-loop step response over a desired time interval. The results hold for any (possibly infinite-dimensional) discrete-time LTI system with a known impulse response. Numerical examples are provided to assess the contribution.

Abstract. Stochastic gradient algorithms are often unstable when applied to functions that do not have Lipschitz-continuous and/or bounded gradients. Gradient clipping is a simple and effective technique to stabilize the training process for problems that are prone to the exploding gradient problem. Despite its widespread popularity, the convergence properties of the gradient clipping heuristic are poorly understood, especially for stochastic problems. This paper establishes both qualitative and quantitative convergence results of the clipped stochastic (sub)gradient method (SGD) for non-smooth convex functions with rapidly growing subgradients. Our analyses show that clipping enhances the stability of SGD and that the clipped SGD algorithm enjoys finite convergence rates in many cases. We also study the convergence of a clipped method with momentum, which includes clipped SGD as a special case, for weakly convex problems under standard assumptions. With a novel Lyapunov analysis, we show that the proposed method achieves the best-known rate for the considered class of problems, demonstrating the effectiveness of clipped methods also in this regime. Numerical results confirm our theoretical developments.

Abstract. Coordinating the mobile production fleet in underground mines becomes increasingly important as the machines are more and more automated. We present a scheduling approach that applies to several of the most important production methods used in underground mines. Our algorithm combines constraint programming with a large neighborhood search strategy that dynamically adjusts the neighborhood size. The resulting algorithm is complete and able to rapidly improve constructed schedules in practice. In addition, it has important benefits when it comes to the acceptance of the approach in real-life operations. Our approach is evaluated on public and private industrial problem instances representing different mines and production methods. We find significant improvements over the current industrial practice.

Abstract. Noise is inherited in many optimization methods such as stochastic gradient methods, zeroth-order methods and compressed gradient methods. For such methods to converge toward a global optimum, it is intuitive to use large step-sizes in the initial iterations when the noise is typically small compared to the algorithm-steps, and reduce the step-sizes as the algorithm progresses. This intuition has been con-firmed in theory and practice for stochastic gradient methods, but similar results are lacking for other methods using approximate gradients. This paper shows that the diminishing step-size strategies can indeed be applied for a broad class of noisy gradient methods. Unlike previous works, our analysis framework shows that such step-size schedules enable these methods to enjoy an optimal O(1/k) rate. We exemplify our results on zeroth-order methods and stochastic compression methods. Our experiments validate fast convergence of these methods with the step decay schedules.

Abstract. With the increasing scale of machine learning tasks, it has become essential to reduce the communication between computing nodes. Early work on gradient compression focused on the bottleneck between CPUs and GPUs, but communicationefficiency is now needed in a variety of different system architectures, from high-performance clusters to energyconstrained IoT devices. In the current practice, compression levels are typically chosen before training and settings that work well for one task may be vastly sub-optimal for another dataset on another architecture. In this paper, we propose a flexible framework which adapts the compression level to the true gradient at each iteration, maximizing the improvement in the objective function that is achieved per communicated bit. Our framework is easy to adapt from one technology to the next by modeling how the communication cost depends on the compression level for the specific technology. Theoretical results and practical experiments indicate that the automatic tuning strategies significantly increase communication efficiency on several state-of-the-art compression schemes.

Abstract. One of the main advantages of second-order methods in a centralized setting is that they are insensitive to the condition number of the objective function's Hessian. For applications such as regression analysis, this means that less pre-processing of the data is required for the algorithm to work well, as the ill-conditioning caused by highly correlated variables will not be as problematic. Similar condition number independence has not yet been established for distributed methods. In this paper, we analyze the performance of a simple distributed second-order algorithm on quadratic problems and show that its convergence depends only logarithmically on the condition number. Our empirical results indicate that the use of second-order information can yield large efficiency improvements over first-order methods, both in terms of iterations and communications, when the condition number is of the same order of magnitude as the problem dimension.

Abstract. Motivated by large-scale optimization problems arising in the context of machine learning, there have been several advances in the study of asynchronous parallel and distributed optimization methods during the past decade. Asynchronous methods do not require all processors to maintain a consistent view of the optimization variables. Consequently, they generally can make more efficient use of computational resources than synchronous methods, and they are not sensitive to issues like stragglers (i.e., slow nodes) and unreliable communication links. Mathematical modeling of asynchronous methods involves proper accounting of information delays, which makes their analysis challenging. This article reviews recent developments in the design and analysis of asynchronous optimization methods, covering both centralized methods, where all processors update a master copy of the optimization variables, and decentralized methods, where each processor maintains a local copy of the variables. The analysis provides insights into how the degree of asynchrony impacts convergence rates, especially in stochastic optimization methods.

Abstract. Manual short-term scheduling in underground mines is a time-consuming and error-prone activity. In this work, we present a Constraint Programming approach capable of automating the short-term scheduling process in a cut-and-fill mine. The approach extends previous work by accounting for fleet travel times, and thus captures an important aspect of the real-world machine scheduling problem. We introduce two models: one that directly solves the original interruptible scheduling problem, and one that is based on solving a related uninterruptible scheduling problem and transforming its solution back to the original domain. Large Neighborhood Search is also employed with a domain-specific neighborhood definition that helps to find high-quality schedules faster. Problem instances derived from an operational mine are used to demonstrate the efficacy of our approach.

Abstract. High-quality production scheduling is increasingly important in modern industry operations. We study a class of scheduling problems where jobs take place at predefined locations, as is common in mining, forestry and logistics. The proposed neighborhood selection algorithm is able to find high- quality solutions fast and guarantees that a globally optimal solution is eventually found. Preliminary results are promising.

Abstract. One approach for State-of-health estimation onboard electric vehicles is to train a data-driven virtual battery on operational data and use this model, rather than the actual battery, for performance tests. A temperature-dependent continuous-time output-error (OE) model is proposed as virtual battery and identified and validated on real operational data from electric buses. The proposed model is compared to discrete-time and parameter-invariant models and shows better performance on all data sets. In addition, the OE model structure is shown to be superior to a conventional Auto Regressive eXogenous (ARX) model for the purpose of modeling the battery voltage response. Finally, challenges regarding vehicle log data are identified and improvements to the model are suggested in order to capture observed un-modeled phenomena.

Abstract. Stochastic gradient methods with momentum are widely used in applications and at the core of optimization subroutines in many popular machine learning libraries. However, their sample complexities have never been obtained for problems that are non-convex and non-smooth. This paper establishes the convergence rate of a stochastic subgradient method with a momentum term of Polyak type for a broad class of non-smooth, non-convex, and constrained optimization problems. Our key innovation is the construction of a special Lyapunov function for which the proven complexity can be achieved without any tunning of the momentum parameter. For smooth problems, we extend the known complexity bound to the constrained case and demonstrate how the unconstrained case can be analyzed under weaker assumptions than the state-of-the-art. Numerical results confirm our theoretical developments.

Abstract. Anderson acceleration is a well-established and simple technique for speeding up fixed-point computations with countless applications. Previous studies of Anderson acceleration in optimization have only been able to provide convergence guarantees for unconstrained and smooth problems. This work introduces novel methods for adapting Anderson acceleration to (non-smooth and constrained) proximal gradient algorithms. Under some technical conditions, we extend the existing local convergence results of Anderson acceleration for smooth fixed-point mappings to the proposed scheme. We also prove analytically that it is not, in general, possible to guarantee global convergence of native Anderson acceleration. We therefore propose a simple scheme for stabilization that combines the global worst-case guarantees of proximal gradient methods with the local adaptation and practical speed-up of Anderson acceleration.

Abstract. We present POLO.jl — a Julia package that helps algorithm developers and machine-learning practitioners design and use state-of-the-art parallel optimization algorithms in a flexible and efficient way. POLO.jl extends our C++ library POLO, which has been designed and implemented with the same intentions. POLO.jl not only wraps selected algorithms in POLO and provides an easy mechanism to use data manipulation facilities and loss function definitions in Julia together with the underlying compiled C++ library, but it also uses the policy-based design technique in a Julian way to help users prototype optimization algorithms from their own building blocks. In our experiments, we observe that there is little overhead when using the compiled C++ code directly within Julia. We also notice that the performance of algorithms implemented in pure Julia is comparable with that of their C++ counterparts. Both libraries are hosted on GitHub under the free MIT license, and can be used easily by pulling the pre-built 64-bit architecture Docker images.

Abstract. We present a novel framework for dynamic cut aggregation in L-shaped algorithms. The aim is to improve the parallel performance of distributed L-shaped algorithms through reduced communication latency and load imbalance. We show how optimality cuts can be aggregated into arbitrary partitions without affecting convergence of the L-shaped algorithm. Furthermore, we give a worst-case bound for L-shaped algorithms with static cut aggregation and then extend this result for dynamic aggregation. We propose a variety of aggregation schemes that fit into our framework, and evaluate them on a collection of large-scale stochastic programming problems. All methods are implemented in our open-source framework for stochastic programming, StochasticPrograms.jl, written in the Julia programming language. In addition, we propose a granulated strategy that combines the strengths of dynamic and static cut aggregation. Major performance improvements are possible with our approach in distributed settings. Our experimental results suggest that the granulated strategy can consistently yield high performance on a range of test problems. The experimental results are supported by our worst-case bounds.

Abstract. This paper focuses on the design of a robust model predictive control law for dynamic positioning (DP) of marine vessels in the presence of actuator saturation and environmental disturbances. The proposed solution is a tube-based MPC ensuring robustness and constraint fulfillment. Formulation of the tube-based MPC relies on a sufficient robust invariant set condition, along with a linear matrix inequality (LMI) synthesis procedure, and an efficient analytical Pontryagin set difference computation. Simulation results show the effectiveness and satisfactory behaviour of the proposed controller.

Abstract. Serverless runtimes provide efficient and cost-effective environments for scalable computations, thanks to their event-driven and elastic nature. So far, they have mostly been used for stateless, data parallel and sporadic computations. In this work, we propose exploiting serverless runtimes to solve generic, large-scale optimization problems. To this end, we implement a parallel optimization algorithm for solving a regularized logistic regression problem, and use AWS Lambda for the compute-intensive work. We show that relative speedups up to 256 workers and efficiencies above 70 percent up to 64 workers can be expected.

Abstract.

Abstract. This paper introduces an efficient second-order method for solving the elastic net problem. Its key innovation is a computationally efficient technique for injecting curvature information in the optimization process which admits a strong theoretical performance guarantee. In particular, we show improved run time over popular first-order methods and quantify the speed-up in terms of statistical measures of the data matrix. The improved time complexity is the result of an extensive exploitation of the problem structure and a careful combination of second-order information, variance reduction techniques, and momentum acceleration. Beside theoretical speed-up, experimental results demonstrate great practical performance benefits of curvature information, especially for ill-conditioned data sets.

Abstract.

Abstract.

Abstract.

Abstract.

Abstract.

Abstract.

Abstract.

Abstract. Distributed training of massive machine learning models, in particular deep neural networks, via Stochastic Gradient Descent (SGD) is becoming commonplace. Several families of communication-reduction methods, such as quantization, large-batch methods, and gradient sparsification, have been proposed. To date, gradient sparsification methods - where each node sorts gradients by magnitude, and only communicates a subset of the components, accumulating the rest locally - are known to yield some of the largest practical gains. Such methods can reduce the amount of communication per step by up to three orders of magnitude, while preserving model accuracy. Yet, this family of methods currently has no theoretical justification. This is the question we address in this paper. We prove that, under analytic assumptions, sparsifying gradients by magnitude with local error correction provides convergence guarantees, for both convex and non-convex smooth objectives, for data-parallel SGD. The main insight is that sparsification methods implicitly maintain bounds on the maximum impact of stale updates, thanks to selection by magnitude. Our analysis and empirical validation also reveal that these methods do require analytical conditions to converge well, justifying existing heuristics.

Abstract.

Abstract.

Abstract. The profitability of an underground mine is greatly affected by the scheduling of the mobile production fleet. Today, most mine operations are scheduled manually, which is a tedious and error-prone activity. In this contribution, we present and formalize the underground mine scheduling problem, and propose a CP-based model for solving it. The model is evaluated on instances generated from real data. The results are promising and show a potential for further extensions.

Abstract.

Abstract. This paper studies online shortest path routing over multihop networks. Link costs or delays are time varying and modeled by independent and identically distributed random processes, whose parameters are initially unknown. The parameters, and hence the optimal path, can only be estimated by routing packets through the network and observing the realized delays. Our aim is to find a routing policy that minimizes the regret (the cumulative difference of expected delay) between the path chosen by the policy and the unknown optimal path. We formulate the problem as a combinatorial bandit optimization problem and consider several scenarios that differ in where routing decisions are made and in the information available when making the decisions. For each scenario, we derive a tight asymptotic lower bound on the regret that has to be satisfied by any online routing policy. Three algorithms, with a tradeoff between computational complexity and performance, are proposed. The regret upper bounds of these algorithms improve over those of the existing algorithms. We also assess numerically the performance of the proposed algorithms and compare it to that of existing algorithms.

Abstract. We analyze stability properties of monotone nonlinear systems via max-separable Lyapunov functions, motivated by the following observations: first, recent results have shown that asymptotic stability of a monotone nonlinear system implies the existence of a max-separable Lyapunov function on a compact set; second, for monotone linear systems, asymptotic stability implies the stronger properties of D-stability and insensitivity to time delays. This paper establishes that for monotone nonlinear systems, equivalence holds between asymptotic stability, the existence of a max-separable Lyapunov function, D-stability, and insensitivity to bounded and unbounded time-varying delays. In particular, a new and general notion of D-stability for monotone nonlinear systems is discussed, and a set of necessary and sufficient conditions for delay-independent stability are derived. Examples show how the results extend the state of the art.

Abstract. We study a cooperative network with a buffer-aided multi-antenna source, multiple half-duplex (HD) buffer-aided relays and a single destination. Such a setup could represent a cellular downlink scenario, in which the source can be a more powerful wireless device with a buffer and multiple antennas, while a set of intermediate less powerful devices are used as relays to reach the destination. The main target is to recover the multiplexing loss of the network by having the source and a relay to simultaneously transmit their information to another relay and the destination, respectively. Successive transmissions in such a cooperative network, however, cause inter-relay interference (IRI). First, by assuming global channel state information (CSI), we show that the detrimental effect of IRI can be alleviated by precoding at the source, mitigating or even fully cancelling the interference. A cooperative relaying policy is proposed that employs a joint precoding design and relay-pair selection. Note that both fixed rate and adaptive rate transmissions can be considered. For the case when channel state information is only available at the receiver side (CSIR), we propose a relay selection policy that employs a phase alignment technique to reduce the IRI. The performance of the two proposed relay pair selection policies are evaluated and compared with other state-of-the-art relaying schemes in terms of outage and throughput. The results show that the use of a powerful source can provide considerable performance improvements.

Abstract.

Abstract. The practical performance of stochastic gradient descent on large-scale machine learning tasks is often much better than what current theoretical tools can guarantee. This indicates that there is an inherent structure in these problems that could be exploited to strengthen the analysis. In this paper, we argue that data sparsity is such a property. We derive explicit expressions for how data sparsity affects the range of admissible step-sizes and the convergence factors of minibatch gradient descent. Our theoretical results are validated by solving least-squares support vector machine problems on both synthetic and real-life data sets. The experimental results demonstrate improved performance of our update rules compared to the traditional mini-batch gradient descent algorithm.

Abstract. Device-to-device communication is a technology that allows users in close proximity to establish a direct communication link instead of passing through the base station. Because direct communications are likely to have a strong line- of- sight component in the received signal, it is reasonable to model the direct channel with Rician fading. In this paper, we propose a power- control scheme for device-to-device communications on a shared channel. Our allocation minimizes the total power consumption while limiting the link outage probability due to Rician fast fading. By leveraging the concept of conditional-value-at-risk from the field of finance, we obtain a linear programming formulation which can be efficiently solved. Through simulation results we show the benefit of the proposed power allocation compared to a deterministic power control that does not account for the random channel variations. Moreover, we provide insights into how the network topology and the parameter settings affect the performance and feasibility of the power allocation.

Abstract. In cellular systems, the combination of Device-to- Device (D2D) communication and relaying is an efficient means for improving network coverage and transmissions quality without additional infrastructure deployment. It enables communication between user pairs in situations when both their direct D2D transmission and the traditional communication via the base station experience poor channel quality. In this paper, we propose a joint relaying-operation selection and power-allocation scheme, herein called HyD2D, for relay-assisted D2D communication in Rician fading environment. The target is to choose the set of communication links that minimizes the power consumption, while ensuring a minimum success probability. To overcome the nonconvexity of the outage probability constraints under Rician fading, we use the concept of coherent-measure- of-risk from the field of finance. We therefore obtain a linear programming formulation that we can efficiently solve. Simulations show that HyD2D selects the most energy- efficient relaying operation that satisfies the success probability requirement, while leveraging only statistical channel state information.

Abstract.

Abstract. Abstract We study a tournament format that extends a traditional double round-robin format with divisional single round-robin tournaments. Elitserien, the top Swedish handball league, uses such a format for its league schedule. We present a constraint programming model that characterizes the general double round-robin plus divisional single round-robin format. This integrated model allows scheduling to be performed in a single step, as opposed to common multistep approaches that decompose scheduling into smaller problems and possibly miss optimal solutions. In addition to general constraints, we introduce Elitserien-specific requirements for its tournament. These general and league-specific constraints allow us to identify implicit and symmetry-breaking properties that reduce the time to solution from hours to seconds. A scalability study of the number of teams shows that our approach is reasonably fast for even larger league sizes. The experimental evaluation of the integrated approach takes considerably less computational effort to schedule Elitserien than does the previous decomposed approach.

Abstract. The aim of this paper is to approximate a Finite-State Markov (FSM) process by another process defined on a lower dimensional state space, called the approximating process, with respect to a total variation distance fidelity criterion. The approximation problem is formulated as an optimization problem using two different approaches. The first approach is based on approximating the transition probability matrix of the FSM process by a lower-dimensional transition probability matrix, resulting in an approximating process which is a Finite-State Hidden Markov (FSHM) process. The second approach is based on approximating the invariant probability vector of the original FSM process by another invariant probability vector defined on a lower-dimensional state space. Going a step further, a method is proposed based on optimizing a Kullback-Leibler divergence to approximate the FSHM processes by FSM processes. The solutions of these optimization problems are described by optimal partition functions which aggregate the states of the FSM process via a corresponding water-filling solution, resulting in lower-dimensional approximating processes which are FSHM or FSM processes. Throughout the paper, the theoretical results are justified by illustrative examples that demonstrate our proposed methodology.

Abstract.

Abstract.

Abstract.

Abstract.

Abstract.

Abstract.

Abstract.

Abstract. Gossiping algorithms are widely used in modern distributed systems, with applications ranging from sensor networks and peer-to-peer networks to mobile vehicle networks and social networks. A tremenedous research effort has been devoted to analyzing and improving the asymptotic rate of convergence of gossip algorithms. In this work we study finite-time convergence of deterministic gossiping. We show that there exists a symmetric gossip algorithm that convergence in finite time if and only if the number of network nodes is a power of two, while there always exists an assymetric gossip algorithm with finite-time convergence, independent of the number of nodes. For n=2^m nodes, we prove that a fastest convergence can be reached in nm=nlog2(n) node updates via symmetric gossiping. On the other hand, under assymetric gossip algorithm among n=2^m+r nodes with 0<=r<=2^m, it takes at least mn+2r node updates for achieving finite-time convergence. It is also shown that the existence of finite-time convergent gossiping often imposes strong structural requirements on the underlying interaction graph. Finally, we apply our results to gossip algorithms in quantum networks, where the goal is to control the state of a quantum system via pairwise interactions. We show that finite-time convergence is never possible for such systems.

Abstract.

Abstract.

Abstract.

Abstract. Relays receive and retransmit signals between one or more sources and one or more destinations. Cooperative relaying is a novel technique for wireless communications that increases throughput and extends the coverage of networks. The task of relay selection serves as a building block to realize cooperative relaying. Recently, relays with buffers have been incorporated into cooperative relaying providing extra degrees of freedom in selection, thus improving various performance metrics, such as outage probability, power reduction, and throughput, at the expense of tolerating an increase in packet delay. In this survey, we review and classify various buffer-aided relay selection policies and discuss their importance through applications. The classification is mainly based on the following aspects: 1) duplexing capabilities, 2) channel state information (CSI), 3) transmission strategies, 4) relay mode, and 5) performance metrics. Relay selection policies for enhanced physical-layer security and cognitive communications with reduced interference are also discussed. Then, a framework for modeling such algorithms is presented based on Markov Chain theory. In addition, performance evaluation is conducted for various buffer-aided relay selection algorithms. To provide a broad perspective on the role of buffer-aided relay selection, various issues relevant to fifth-generation (5G) networks are discussed. Finally, we draw conclusion and discuss current challenges, possible future directions, and emerging technologies.

Abstract.

Abstract.

Abstract. We study the evolution of opinions (or beliefs) over a social network modeled as a signed graph. The sign attached to an edge in this graph characterizes whether the corresponding individuals or end nodes are friends (positive link) or enemies (negative link). Pairs of nodes are randomly selected to interact over time, and when two nodes interact, each of them updates her opinion based on the opinion of the other node in a manner dependent on the sign of the corresponding link. Our model for the opinion dynamics is essentially linear and generalizes DeGroot model to account for negative links -- when two enemies interact, their opinions go in opposite directions. We provide conditions for convergence and divergence in expectation, in mean-square, and in almost sure sense, and exhibit phase transition phenomena for these notions of convergence depending on the parameters of our opinion update model and on the structure of the underlying graph. We establish a no-survivor theorem, stating that the difference in opinions of any two nodes diverges whenever opinions in the network diverge as a whole. We also prove a live-or-die lemma, indicating that almost surely, the opinions either converge to an agreement or diverge. Finally, we extend our analysis to cases where opinions have hard lower and upper limits. In these cases, we study when and how opinions may become asymptotically clustered, and highlight the impact of the structural properties (namely structural balance) of the underlying network on this clustering phenomenon.

Abstract. This paper presents optimal scaling of the alternating directions method of multipliers (ADMM) algorithm for a class of distributed quadratic programming problems. The scaling corresponds to the ADMM step-size and relaxation parameter, as well as the edge-weights of the underlying communication graph. We optimize these parameters to yield the smallest convergence factor of the algorithm. Explicit expressions are derived for the step-size and relaxation parameter, as well as for the corresponding convergence factor. Numerical simulations justify our results and highlight the benefits of optimally scaling the ADMM algorithm.

Abstract.

Abstract. Most algorithms for distributed averaging only guarantee asymptotic convergence. This work introduces a distributed protocol that allows nodes to find the exact average of the initial values in a finite and minimum number of steps on interconnection topologies described by strongly connected directed graphs (digraphs). More specifically, under the assumption that each component has knowledge of the number of its out-going links (i.e., the number of components to which it sends information), we show that the average value can be computed based on local observations over a finite time interval. The average can be obtained in a finite number of steps even when the information exchange is subject to delays. The proposed algorithm is the first in the literature that allows for distributed computation of the exact average in digraphs in finite time, with and without delays.

Abstract. Mini-batch optimization has proven to be a powerful paradigm for large-scale learning. However, the state of the art parallel mini-batch algorithms assume synchronous operation or cyclic update orders. When worker nodes are heterogeneous (due to different computational capabilities or different communication delays), synchronous and cyclic operations are inefficient since they will leave workers idle waiting for the slower nodes to complete their computations. In this paper, we propose an asynchronous mini-batch algorithm for regularized stochastic optimization problems with smooth loss functions that eliminates idle waiting and allows workers to run at their maximal update rates. We show that by suitably choosing the step-size values, the algorithm achieves a rate of the order O(1/T‾‾√) for general convex regularization functions, and the rate O(1/T) for strongly convex regularization functions, where T is the number of iterations. In both cases, the impact of asynchrony on the convergence rate of our algorithm is asymptotically negligible, and a near-linear speedup in the number of workers can be expected. Theoretical results are confirmed in real implementations on a distributed computing infrastructure.

Abstract. Recent results in the literature have shown that particular classes of positive monotone systems are insensitive to time-varying delays, giving the impression that the delay-insensitivity property stems from the fact that the system is positive. Nonetheless, it has been lately shown that a linear cone-invariant system is insensitive to time-varying delays, asserting that the property of delay-independence may stem from the fact that the system is cone-invariant rather than positive. In this paper, we attest this claim by showing that a significant class of cone-invariant monotone systems, which includes linear cone-invariant systems as a special case, is globally asymptotically stable for any bounded time-varying delays if the corresponding delay-free system is globally asymptotically stable.

Abstract. This paper considers the problem of distributed neighbor discovery in multi-channel wireless networks. We propose a protocol in which nodes randomly select a channel and decide whether to transmit or listen {for neighbor discovery beacons}. When nodes transmit, they use epidemic information dissemination {to spread knowledge} about all the nodes they have discovered so far. Theoretical guarantees on discovery times are complemented by extensive simulations and practical implementations. The evaluations show that multi-channel communication effectively {reduces} the number of collisions between nodes in the network (especially in dense networks) and that epidemic information dissemination yields both significant speed-ups and increased resilience to packet losses. Finally, we also show that our protocol compares favorably to previously proposed solutions in the literature.

Abstract.

Abstract. This paper investigates the stability of discrete-time linear systems with stochastic delays. We assume that delays are modeled as random variables, which take values in integers with a certain probability. For the scalar case, we provide an analytical bound on the probability to guarantee the stability of linear systems. In the vector case, we derive a linear matrix inequality condition to compute the probability for ensuring the stability of closed-loop systems. As a special case, we also determine the step size of gradient algorithms with stochastic delays in the unconstrained quadratic programming to guarantee convergence to the optimal solution. Numerical examples are provided to show the effectiveness of the proposed analysis techniques.

Abstract. This paper establishes global convergence and provides global bounds of the convergence rate of the Heavy-ball method for convex optimization problems. When the objective function has Lipschitz-continuous gradient, we show that the Cesaro average of the iterates converges to the optimum at a rate of O(1/k) where k is the number of iterations. When the objective function is also strongly convex, we prove that the Heavy-ball iterates converge linearly to the unique optimum.

Abstract. Multi-agent optimization problems arise in a wide variety of networked systems, and are often required to be solved in an asynchronous and uncoordinated way. However, existing asynchronous algorithms for constrained multi-agent optimization do not have guaranteed convergence rates and, thus, lack performance guarantees in on-line applications. This paper addresses this shortcoming by developing randomized coordinate descent algorithms for solving the dual of a class of constrained multi-agent optimization problems. We show that the algorithms can be implemented asynchronously and distributively in multi-agent networks. Moreover, without relying on the standard assumption of boundedness of the dual optimal set, the proposed dual coordinate descent algorithms achieve sublinear convergence rates of both its primal and dual iterates in expectation. The competitive performance is demonstrated numerically on a constrained optimal rendezvous problem.

Abstract. The dimensioning of wireless communication protocols for networked control involves a non-trivial trade-off between reliability and delay. Due to the lossy nature of wireless communications, there is a risk that sensor messages will be dropped. The end-to-end reliability can be improved by retransmitting dropped messages, but this comes at the expense of additional delays. In this work, we determine the number of retransmissions that strikes the optimal balance between communication reliability and delay, in the sense that it achieves the minimal expected linear-quadratic loss of the closed-loop system. An important feature of our setup is that it accounts for the random delays and possible losses that occur when lossy communication is combatted with retransmissions. The resulting controller dynamically switches among a set of infinite-horizon linear-quadratic regulators, and is simple to implement. Numerical simulations are carried out to highlight the trade-off between reliability and delay.

Abstract. Network-assisted Device-to-Device (D2D) communication is a promising technology for improving the performance of proximity-based services. This paper demonstrates how D2D communication can be used to improve the energy-efficiency of cellular networks, leading to a greener system operation and a prolonged battery life of the mobile devices. Assuming a flexible TDD system, we develop optimal mode selection policies for minimizing the energy cost (either from the system or from the device perspective) while guaranteeing a certain rate requirement. The jointly optimal transmit power and time allocation, as well as the optimal mode selection, is found by solving a small convex optimization problem. Special attention is given to the geometrical interpretation of the obtained results. We show that when network energy is the primary concern, D2D mode is preferable in a large portion of the cell. When the device energy consumption is most important, on the other hand, the area where D2D mode is preferable shrinks and becomes close to circular. Finally, we investigate how network parameters affect the range where direct communication is preferred.

Abstract. Recent studies from social, biological, and engineering network systems have drawn attention to the dynamics over signed networks, where each link is associated with a positive/negative sign indicating trustful/mistrustful, activator/inhibitor, or secure/malicious interactions. We study asymptotic dynamical patterns that emerge among a set of nodes that interact in a dynamically evolving signed random network. Node interactions take place at random on a sequence of deterministic signed graphs. Each node receives positive or negative recommendations from its neighbors depending on the sign of the interaction arcs, and updates its state accordingly. Recommendations along a positive arc follow the standard consensus update. As in the work by Altafini, negative recommendations use an update where the sign of the neighbor state is flipped. Nodes may weight positive and negative recommendations differently, and random processes are introduced to model the time-varying attention that nodes pay to these recommendations. Conditions for almost sure convergence and divergence of the node states are established. We show that under this so-called state-flipping model, all links contribute to a consensus of the absolute values of the nodes, even under switching sign patterns and dynamically changing environment. A no-survivor property is established, indicating that every node state diverges almost surely if the maximum network state diverges.

Abstract.

Abstract.

Abstract. The alternating direction method of multipliers (ADMM) has emerged as a powerful technique for large-scale structured optimization. Despite many recent results on the convergence properties of ADMM, a quantitative characterization of the impact of the algorithm parameters on the convergence times of the method is still lacking. In this paper we find the optimal algorithm parameters that minimize the convergence factor of the ADMM iterates in the context of l2-regularized minimization and constrained quadratic programming. Numerical examples show that our parameter selection rules significantly outperform existing alternatives in the literature.

Abstract. Convergecast, in which packets originating from multiple sources are reported to a single sink, is a fundamental primitive for data collection in wireless sensor networks. This paper investigates the time-optimal link scheduling problem for TDMA-based convergecast, aiming to minimize the amount of time required to complete convergecast. We observe that packet copying between the microcontroller and the radio transceiver in existing sensor platforms has a big impact on the packet forwarding delay, and propose a novel model for convergecast in which packet copying is separated from packet transmission and reception. We establish tight lower bounds on the number of time slots required for convergecast in networks with line and tree routing topologies, and present both centralized and distributed algorithms for constructing the time-optimal con- vergecast schedules. We evaluate our scheme in both simulations and experiments on hardware. The results show that our scheme can achieve a system throughput (defined as the number of data bits received by the sink per second) of 202.8 kbit/s, which is 86.31\% of the theoretical bound. In comparison with the traditional TDMA-based convergecast schemes, our scheme can achieve up to 86.22\% improvement on system throughput.

Abstract. This paper considers multiaccess control for the uplink in orthogonal frequency division multiple access wireless networks. To avoid the extensive information exchange associated with centralized approaches, we formulate the decentralized access control problem with the contention power constraint as a Bayesian game, mapping time-varying channel state information into contention strategies. By exploiting the problem structure, a strategy where users access the channels with probability one if the observed channel gain is above a predetermined threshold is shown to be optimal. It is also shown that the energy consumption of the threshold strategy will not exceed that of randomized strategies. The game is then equivalently reformulated as one of finding the threshold value in a distributed manner, and the existence and uniqueness of Bayesian Nash equilibria is established. A distributed algorithm based on Lagrange duality is proposed to approach the unique equilibrium, and the algorithm is shown to be globally stable. In a homogeneous system, the performance loss of the proposed scheme is proved to be bounded compared with a centralized channel allocation scheme. Contrary to other proposals, our method allows for heterogeneous channel state information and achieves a comparable throughput with reduced power.

Abstract. In this paper, we investigate the problem of aggregating a given finite-state Markov process by another process with fewer states. The aggregation utilizes total variation distance as a measure of discriminating the Markov process by the aggregate process, and aims to maximize the entropy of the aggregate process invariant probability, subject to a fidelity described by the total variation distance ball. An iterative algorithm is presented to compute the invariant distribution of the aggregate process, as a function of the invariant distribution of the Markov process. It turns out that the approximation method via aggregation leads to an optimal aggregate process which is a hidden Markov process, and the optimal solution exhibits a water-filling behavior. Finally, the algorithm is applied to specific examples to illustrate the methodology and properties of the approximations.

Abstract. This paper presents a unifying convergence result for asynchronous iterations involving pseudo-contractions in the block-maximum norm. Contrary to previous results which only established asymptotic convergence or studied simplified models of asynchronism, our result allows to bound the convergence rates for both partially and totally asynchronous implementations. Several examples are worked out to demonstrate that our theorem recovers and improves on existing results, and that it allows to characterize the solution times for several classes of asynchronous iterations that have not been addressed before.

Abstract. We derive the optimal step-size and overrelaxation parameter that minimizes the convergence time of two ADMM-based algorithms for distributed averaging. Our study shows that the convergence times for given step-size and over-relaxation parameters depend on the spectral properties of the normalized Laplacian of the underlying communication graph. Motivated by this, we optimize the edge-weights of the communication graph to improve the convergence speed even further. The performance of the ADMM algorithms with our parameter selection are compared with alternatives from the literature in extensive numerical simulations on random graphs.

Abstract. There are several results on the stability of nonlinear positive systems in the presence of time delays. However, most of them assume that the delays are constant. This paper considers time-varying, possibly unbounded, delays and establishes asymptotic stability and bounds the decay rate of a significant class of nonlinear positive systems which includes positive linear systems as a special case. Specifically, we present a necessary and sufficient condition for delay-independent stability of continuous-time positive systems whose vector fields are cooperative and homogeneous. We show that global asymptotic stability of such systems is independent of the magnitude and variation of the time delays. For various classes of time delays, we are able to derive explicit expressions that quantify the decay rates of positive systems. We also provide the corresponding counterparts for discrete-time positive systems whose vector fields are non-decreasing and homogeneous.

Abstract. This paper studies a flexible algorithm for minimizing a sum of component functions, each of which depends on a large number of decision variables. Such formulations appear naturally in ``big data'' applications, where each function describes the loss estimated using the data available at a specific machine, and the number of features under consideration is huge. In our algorithm, a coordinator updates a global iterate based on delayed partial gradients of the individual objective functions with respect to blocks of coordinates. Delayed incremental gradient and delayed coordinate descent algorithms are obtained as special cases. Under the assumption of strong convexity and block coordinate-wise Lipschitz continuous partial gradients, we show that the algorithm converges linearly to a ball around the optimal value. Contrary to related proposals in the literature, our algorithm is delay-insensitive: it converges for any bounded information delay, and its step-size parameter can be chosen independently of the maximum delay bound.

Abstract. This work presents a distributed framework for coordination of flexible electricity consumption for a number of households in the distribution grid. Coordination is conducted with the purpose of minimizing a trade-off between individual concerns about discomfort and electricity cost, on the one hand, and joint concerns about grid losses and voltage variations on the other. Our contribution is to demonstrate how distributed coordination of both active and reactive consumption may be conducted, when consumers are jointly coupled by grid losses and voltage variations. We further illustrate the benefit of including consumption coordination for grid operation, and how different types of consumption present different benefits.

Abstract. This paper presents a new incremental gradient algorithm for minimizing the average of a large number of smooth component functions based on delayed partial gradients. Even with a constant step size, which can be chosen independently of the maximum delay bound and the number of objective function components, the expected objective value is guaranteed to converge linearly to within some ball around the optimum. We derive an explicit expression that quantifies how the convergence rate depends on objective function properties and algorithm parameters such as step-size and the maximum delay. An associated upper bound on the asymptotic error reveals the trade-off between convergence speed and residual error. Numerical examples confirm the validity of our results.

Abstract. We consider the joint design of packet forwarding policies and controllers for wireless control loops where sensor measurements are sent to the controller over an unreliable and energy-constrained multi-hop wireless network. For fixed sampling rate of the sensor, the co-design problem separates into two well-defined and independent subproblems: transmission scheduling for maximizing the deadlineconstrained reliability and optimal control under packet loss. We develop optimal and implementable solutions for these subproblems and show that the optimally co-designed system can be efficiently found. Numerical examples highlight the many trade-offs involved and demonstrate the power of our approach.

Abstract. This work develops a stability analysis framework for general classes of continuous-time power control algorithms under time-varying bounded delays. Our first set of results establish global asymptotic stability of power control laws involving two-sided scalable interference functions, and include earlier work on standard interference functions as a special case. We then consider contractive interference functions and demonstrate that the associated continuous-time power control laws always have unique fixed points, which are exponentially stable even under bounded heterogeneous time-varying delays. For this class of interference functions, we derive explicit bounds on the decay rate that allow us to quantify the impact of delays on the convergence time of the algorithm. Numerical simulations illustrate our theoretical results.

Abstract. In this work, we present a buffer-aided successive opportunistic relaying scheme (herein called BA-SOR) that aims at improving the average capacity of the network when inter-relay interference (IRI) arises between relays that are selected for simultaneous transmission and reception.We propose a relay selection policy that, by exploiting the benefits of buffering at the relays, decouples the receiving relay at the previous time slot to be the transmitting relay at the next slot. Furthermore, we impose an interference cancellation (IC) threshold allowing the relay that is selected for reception, to decode and subtract the IRI. The proposed relaying scheme selects the relaying pair that maximizes the average capacity of the relay network. Its performance is evaluated through simulations and comparisons with other state-of-the-art half- and full-duplex relay selection schemes, in terms of outage probability, average capacity and average delay. The results reveal that a tradeoff has to be made between improving the outage at the cost of reduced capacity and increased delay and vice versa. Finally, conclusions are drawn and future directions are discussed, including the need for a hybrid scheme incorporating both halfand full-duplex characteristics.

Abstract. We show that a sub-homogeneous positive monotone system with bounded heterogeneous time-varying delays is globally asymptotically stable if and only if the corresponding delay-free system is globally asymptotically stable. The proof is based on an extension of a delay-independent stability result for monotone systems under constant delays by Smith to systems with bounded heterogenous time-varying delays. Under the additional assumption of positivity and sub-homogenous vector fields, we establish the aforementioned delay insensitivity property and derive a novel test for global asymptotic stability. If the system has a unique equilibrium point in the positive orthant, we prove that our stability test is necessary and sufficient. Specialized to positive linear systems, our results extend and sharpen existing results from the literature.

Abstract. In this paper, we study finite-time convergence of gossip algorithms. We show that there exists a symmetric gossip algorithm that converges in finite time if and only if the number of network nodes is a power of two, while there always exists a globally finite-time convergent gossip algorithm despite the number of nodes if asymmetric gossiping is allowed. For n = 2 to the power of m nodes, we prove that a fastest convergence can be reached in mn node updates via symmetric gossiping. On the other hand, for n=2 to the power of m +r nodes, with 0<= r< =2m,it requires at least mn + 2r node updates for achieving a finite-time convergence in cooperation with asymmetric interactions.

Abstract. In this work, we study a cooperative network with multiple full-duplex buffer-aided relays. A hybrid cooperative relaying policy is proposed that employs power adaptation and consists of two alternative schemes: (i) full-duplex transmission through the relay which requires the least total power expenditure and loop interference is mitigated through power adaptation; (ii) buffer-aided max - link selection with power adaptation, when full-duplexity is not feasible. Aiming to reduce the overhead of channel state information (CSI) acquisition and processing, we propose a suboptimal distributed method for relay selection, for which the network performance is not degraded significantly. We show that power adaptation offers reduced overhead of CSI acquisition. Numerical results and comparisons with other state-of-the-art relaying schemes are provided and performance evaluation in terms of throughput, power minimization and switching rate, show the benefits of the proposed hybrid scheme.

Abstract. This paper studies online shortest path routing over dynamic multi-hop networks. Link costs or delays are time-varying and modelled by independent and identically distributed random processes, whose parameters are initially unknown. The parameters, and hence the optimal path, can only be estimated by routing packets through the network and observing the realized delays. Our aim is to find a routing policy that minimizes the regret (the cumulative delay difference) between the path chosen by the policy and the unknown optimal path. We formulate the problem as a combinatorial bandit optimization problem and consider several scenarios that differ in where routing decisions are made and in the information available when making the decision. For each scenario, we derive the tight asymptotic lower bound on the regret that has to be satisfied by any online routing policy. These bounds help us to understand the performance improvements we can expect when (i) taking routing decisions at each hop rather than at the source only, and (ii) observing per-link costs rather than aggregate path costs. In particular, we show that (i) is of no use while (ii) can have a spectacular impact. Efficient algorithms are proposed and evaluated against the state-of-the art.

Abstract. We analyze a sports league that wishes to augment its traditional double round-robin tournament into a longer season. The method for doing so, chosen by the top Swedish handball league Elitserien, is to form two divisions which hold an additional single round-robin tournament to start the season. This format introduces new constraints since pairs of teams in the same division meet three times during the season, while others only meet twice. Though motivated by the concerns of a specific league, the requirements addressed are general enough to be useful for other leagues. We enumerate the number of minimum break home-away pattern sets that satisfy the league's requirements, not all of which are schedulable. We propose a sequence of increasingly restrictive necessary conditions that remove most of the unschedulable home-away pattern sets from consideration. We lastly discuss the final steps of assigning teams to a schedulable home-away pattern set; such an approach was used to construct the 2013-14 Elitserien schedule.

Abstract. While the asymptotic stability of positive linear systems in the presence of bounded time delays has been thoroughly investigated, the theory for nonlinear positive systems is considerably less well-developed. This paper presents a set of conditions for establishing delay-independent stability and bounding the decay rate of a significant class of nonlinear positive systems which includes positive linear systems as a special case. Specifically, when the time delays have a known upper bound, we derive necessary and sufficient conditions for exponential stability of (a) continuous-time positive systems whose vector fields are homogeneous and cooperative, and (b) discrete-time positive systems whose vector fields are homogeneous and order preserving. We then present explicit expressions that allow us to quantify the impact of delays on the decay rate and show that the best decay rate of positive linear systems that our bounds provide can be found via convex optimization. Finally, we extend the results to general linear systems with time-varying delays.

Abstract. Previous approaches for scheduling a league with round-robin and divisional tournaments involved decomposing the problem into easier subproblems. This approach, used to schedule the top Swedish handball league Elitserien, reduces the problem complexity but can result in suboptimal schedules. This paper presents an integrated constraint programming model that allows to perform the scheduling in a single step. Particular attention is given to identifying implied and symmetry-breaking constraints that reduce the computational complexity significantly. The experimental evaluation of the integrated approach takes considerably less computational effort than the previous approach.

Abstract. This paper develops a comprehensive stability analysis framework for continuous-time power control algorithms in wireless networks under bounded time-varying communication delays. Our first set of results establish global asymptotic stability of power control laws involving two-sided scalable interference functions, and include earlier work on standard interference functions as a special case. We then consider contractive interference functions and demonstrate that the associated continuous-time power control laws always have unique fixed points, which are exponentially stable even in the presence of bounded heterogeneous time-varying delays. For this class of interference functions, we derive explicit bounds on the decay rate that allow us to quantify the impact of delays on the convergence time of the algorithm. Numerical simulations illustrate our theoretical results.

Abstract. There are several results on the stability analysis of positive linear systems in the presence of constant or timevarying delays. However, most existing results assume that the delays are bounded. This paper studies the stability of discretetime positive linear systems with unbounded delays. We provide a set of easily verifiable necessary and sufficient conditions for asymptotic stability of positive systems subject to a general class of heterogeneous time-varying delays. For two particular classes of unbounded delays, explicit expressions that bound the decay rate of the system are presented. We demonstrate that the best bound on the decay rate that our results can guarantee can be found via convex optimization techniques. Finally, the validity of the results is demonstrated via numerical examples.

Abstract. Distributed algorithms for average consensus in directed graphs are typically asymptotic in the literature. In this work, we propose a protocol to distributively reach average consensus in a finite number of steps on interconnection topologies (digraphs). The average consensus value can be computed based on exclusively local observations at each component by running a protocol that requires each component to observe and store its own value over a finite and minimal number of steps, and to have knowledge of the number of its out-going links (i.e., the number of components to which it sends information). Both delay-free and delayed scenarios are considered and the proposed algorithms are demonstrated via illustrative examples.

Abstract. In this paper we address the problem of balancing the processing load of MapReduce tasks running on heterogeneous1 clusters. We present a fully decentralised algorithm, based on ratio consensus, where each mapper decides the amount of workload data to handle for a single user job using only job specific local information, i.e., information that can be collected from directly connected neighboring mappers, regarding their current workload and capacity. The proposed algorithm, in contrast to other algorithms in the literature, can be deployed in heterogeneous networks and can operate asynchronously in both directed and undirected communication topologies. The performance of the proposed algorithm is demonstrated via simulation experiments on largescale strongly connected topologies.

Abstract. This paper addresses the optimal scaling of the ADMM method for distributed quadratic programming. Scaled ADMM iterations are first derived for generic equalityconstrained quadratic problems and then applied to a class of distributed quadratic problems. In this setting, the scaling corresponds to the step-size and the edge-weights of the underlying communication graph. We optimize the convergence factor of the algorithm with respect to the step-size and graph edge-weights. Explicit analytical expressions for the optimal convergence factor and the optimal step-size are derived. Numerical simulations illustrate our results.

Abstract. We study convergence properties of a randomized consensus algorithm over a graph with both attractive and repulsive links. At each time instant, a node is randomly selected to interact with a random neighbor. Depending on if the link between the two nodes belongs to a given subgraph of attractive or repulsive links, the node update follows a standard attractive weighted average or a repulsive weighted average, respectively. The repulsive update has the opposite sign of the standard consensus update. In this way, it counteracts the consensus formation and can be seen as a model of link faults or malicious attacks in a communication network, or the impact of trust and antagonism in a social network. Various probabilistic convergence and divergence conditions are established. A threshold condition for the strength of the repulsive action is given for convergence in expectation: when the repulsive weight crosses this threshold value, the algorithm transits from convergence to divergence. An explicit value of the threshold is derived for classes of attractive and repulsive graphs. The results show that a single repulsive link can sometimes drastically change the behavior of the consensus algorithm. They also explicitly show how the robustness of the consensus algorithm depends on the size and other properties of the graphs.

Abstract. We consider a class of inequality and equality constrained optimization problems with a strongly convex but not necessarily differentiable objective function. To solve such a problem, we adopt the Lagrangian dual approach and use the gradient projection method to solve the corresponding dual problem. We construct an approximate primal solution and focus on studying its convergence properties. More specifically, we derive error bounds for the approximate primal solution and show that it converges to the primal optimal solution at a rate no worse than O(1/sqrt(k)) where k is the number of iterations. Finally, we illustrate that via dual decomposition and the dual gradient projection method, a multi-agent optimization problem with non-identical node constraints can be solved in a decentralized way, whereby all the node estimates are guaranteed to converge to the optimal solution at rate O(1/sqrt(k)).

Abstract. This paper proposes a supervisory control structure for networked systems with time-varying delays. The control structure, in which a supervisor triggers the most appropriate controller from a multi-controller unit, aims at improving the closed-loop performance relative to what can be obtained using a single robust controller. Our analysis considers average dwell-time switching and is based on a novel multiple Lyapunov-Krasovskii functional. We develop stability conditions that can be verified by semi-definite programming, and show that the associated state feedback synthesis problem also can be solved using convex optimization tools. Extensions of the analysis and synthesis procedures to the case when the evolution of the delay mode is described by a Markov chain are also developed. Simulations on small and large-scale networked control systems are used to illustrate the eectiveness of our approach.

Abstract. The increasing demand for wireless cyber-physical systems requires correct design, implementation and validation of computation, communication and control methods. Traditional simulation tools, which focus on either computation, communication or control, are insufficient when the three aspects interact. Efforts to extend the traditional tools to cover multiple domains, e.g., from simulating only control aspects to simulating both control and communication, often rely on simplistic models of a small subset of possible communication solutions. We introduce GISOO, a virtual testbed for simulation of wireless cyber-physical systems that integrates two state-of-the art simulators, Simulink and COOJA. GISOO enables users to evaluate actual embedded code for the wireless nodes in realistic cyber-physical experiments, observing the effects of both the control and communication components. In this way, a wide range of communication solutions can be evaluated without developing abstract models of their control-relevant aspects, and changes made to the networking code in simulations is guaranteed to be translated into production code without errors. A double-tank laboratory experimental setup controlled over a multi-hop relay wireless network is used to validate GISOO and demonstrate its features.

Abstract. We consider a class of multi-agent optimization problems, where each agent is endowed with a strongly convex (but not necessarily differentiable) loss function and is subject to individual constraints composed of linear equalities, convex inequalities, and convex set constraints. We derive a novel algorithm that allows the agents to collaboratively reach a decision that minimizes the sum of the loss functions over the intersection of the individual constraints. The algorithm is based on a projected dual gradient technique and exploits the structure of the individual constraint sets to avoid costly projections. A convergence rate analysis shows that the primal iterates produced by individual agents under our algorithm converge to the primal optimal solution at a rate that is superior to alternatives in the literature. Finally, we provide a thorough comparison of our algorithm with alternatives in terms of both theoretical and algorithmic aspects.

Abstract. We investigate the problem of neighbor discovery in multichannel wireless ad hoc and sensor networks with epidemic information dissemination. In previous works, a single channel neighbor discovery is adopted (i.e., all nodes either transmit or receive a single packet in a single channel), and hence only one node discovery can occur per time instant. To reduce the effect of collisions observed in the single packet reception model, we formulate models for multichannel neighbor discovery and in addition we allow for epidemic dissemination of information. As a result, nodes can discover all their neighbors faster, either directly or indirectly by hopping between orthogonal channels and exploring the neighbors in each of them. We show analytically, by simulations, and by experimental evaluation that the expected neighbor discovery time is reduced considerably, when compared to the single channel neighbor discovery model.

Abstract. In this paper we consider a simple cooperative network consisting of a source, a destination and a cluster of decode-and-forward relays characterized by the half-duplex constraint. At each time-slot the source and (possibly) one of the relays transmit a packet to another relay and the destination, respectively. When the source and a relay transmit simultaneously, inter-relay interference is introduced at the receiving relay. In this work, with the aid of buffers at the relays, we mitigate the detrimental effect of inter-relay interference through either interference cancellation or mitigation. More specifically, we propose the min-power opportunistic relaying protocol that minimizes the total energy expenditure per time slot under an inter-relay interference cancellation scheme. The min-power relay-pair selection scheme, apart from minimizing the energy expenditure, also provides better throughput and lower outage probability than existing works in the literature. The performance of the proposed scheme is demonstrated via illustrative examples and simulations in terms of outage probability and average throughput.

Abstract. We develop multi-step gradient methods for network-constrained optimization of strongly convex functions with Lipschitz-continuous gradients. Given the topology of the underlying network and bounds on the Hessian of the objective function, we determine the algorithm parameters that guarantee the fastest convergence and characterize situations when significant speed-ups can be obtained over the standard gradient method. Furthermore, we quantify how the performance of the gradient method and its accelerated counterpart are affected by uncertainty in the problem data, and conclude that in most cases our proposed method outperforms gradient descent. Finally, we apply the proposed technique to three engineering problems: resource allocation under network-wide budget constraints, distributed averaging, and Internet congestion control. In all cases, we demonstrate that our algorithm converges more rapidly than alternative algorithms reported in the literature.

Abstract. This paper develops a theoretical framework for quantifying the trade-off between communication cost and control performance in event-triggered control over lossy networks. We consider a system where the communication between controller and actuator is dictated by a threshold-based eventtriggering algorithm, and develop a Markov-chain model that describes the attempted and successful transmissions of control messages over the lossy communication channel. A particular feature of our model is that it considers retransmissions of unsuccessful messages and that it accounts for the delay associated with such retransmissions. Combining this model with an analytical model of the closed-loop performance yields a systematic framework for analyzing the trade-off between the communication rate and control performance and for optimal tuning of the event threshold. Numerical examples demonstrate the effectiveness of the proposed framework.

Abstract. In this work, a set of conditions are presented for establishing exponential stability and bounds on the convergence rates for both general and positive linear systems with heterogeneous time-varying delays. First, a sufficient condition for delay-independent exponential stability of general linear systems is derived. When the time delays have a known upper bound, we present an explicit expression that bounds the decay rate of the system. We demonstrate that the best decay rate that our bound can provide, can be easily found via convex optimization techniques. Finally, for positive linear systems, we show that the stability condition that we have developed is also necessary. The validity of the results is demonstrated via simple examples.

Abstract. Opportunistic routing is widely known to have substantially better performance than unicast routing in wireless networks with lossy links. However, wireless sensor networks are heavily duty-cycled, i.e. they frequently enter sleep states to ensure long network life-time. This renders existing opportunistic routing schemes impractical, as they assume that nodes are always awake and can overhear other transmissions. In this paper we introduce ORW, a practical opportunistic routing scheme for wireless sensor networks. ORW uses a novel opportunistic routing metric, EDC, that reflects the expected number of duty-cycled wakeups that are required to successfully deliver a packet from source to destination. We devise distributed algorithms that find the EDC-optimal forwarding and demonstrate using analytical performance models and simulations that EDC-based opportunistic routing results in significantly reduced delay and improved energy efficiency compared to the traditional unicast routing. We compare the performance of the ORW protocol with other alternatives in both simulations and testbed-based experiments. Our results show that ORW reduces radio duty cycles on average by 50\% (up to 90\% on individual nodes) and delays by 30\% to 90\% when compared to the state of the art.

Abstract. In this work, we propose a buffer-aided successive opportunistic relaying scheme that aims to improve the average capacity of the network when inter-relay interference arises between relays that are selected for transmission and reception. In order to exploit the benefits of buffering at the relays, we propose a relay-pair selection policy that decouples the receiving relay at the previous time slot from being the transmitting relay at the next slot. Furthermore, we impose an interference cancellation threshold allowing the relay that is selected for reception, to decode and subtract the inter-relay interference. The proposed relaying scheme selects the relaying pair that maximizes the average capacity of the relay network. The performance of the proposed scheme is evaluated via simulation and comparisons with other state-of-the-art half and full-duplex relay selection schemes, in terms of outage probability, average capacity and average delay. The results reveal the need for a tradeoff between improving the outage on the cost of reduced capacity and increased delay, and vice versa. Finally, conclusions are drawn and future directions are discussed, including the need for a hybrid scheme incorporating both half and full-duplex characteristics.

Abstract. The dynamics of an agreement protocol interacting with a disagreement process over a common random network is considered. The model can represent the spreading of true and false information over a communication network, the propagation of faults in a large-scale control system, or the development of trust and mistrust in a society. At each time instance and with a given probability, a pair of network nodes are selected to interact. At random each of the nodes then updates its state towards the state of the other node (attraction), away from the other node (repulsion), or sticks to its current state (neglect). Agreement convergence and disagreement divergence results are obtained for various strengths of the updates for both symmetric and asymmetric update rules. Impossibility theorems show that a specific level of attraction is required for almost sure asymptotic agreement and a specific level of repulsion is required for almost sure asymptotic disagreement. A series of sufficient and/or necessary conditions are then established for agreement convergence or disagreement divergence. In particular, under symmetric updates, a critical convergence measure in the attraction and repulsion update strength is found, in the sense that the asymptotic property of the network state evolution transits from agreement convergence to disagreement divergence when this measure goes from negative to positive. The result can be interpreted as a tight bound on how much bad action needs to be injected in a dynamic network in order to consistently steer its overall behavior away from consensus.

Abstract. Convergecast, in which data from a set of sources is delivered to a single data sink, is a critical functionality of networks deployed for industrial monitoring and control. We address the latency-optimal link scheduling problem for convergecast in networks operating according to the recent WirelessHART standard. When there is no restriction on the number of channels, we present a latency-optimal scheduling policy in which each routing node is required to buffer at most one packet at any point in time. For networks with a limited number of channels, we first establish a lower bound on the number of channels for latency-optimal convergecast and a lower bound on latency for convergecast using a fixed number of channels, and then present a heuristic scheme for channel-constrained latency-optimal convergecast scheduling. Simulation results confirm that, at much modest computational cost, our heuristic scheme can construct schedules with convergecast latency very close to that of the optimal schedules.

Abstract. Device-to-device (D2D) communications integrated into cellular networks is a means to take advantage of the proximity of devices and thereby to increase the user bitrates and system capacity. D2D communications has recently been proposed for the 3GPP Long Term Evolution (LTE) system as a method to increase the spectrum- and energy-efficiency. Such systems support a wide range of power control schemes based on a combination of open-loop and closed-loop components and there is a need to set the associated control parameters such that spectrum- and energy- efficiency targets are met. In this paper we study the performance of various power control strategies applicable to D2D communications in LTE networks and compare them with a utility function maximization approach that balances spectrum efficiency and the total transmission power. Our reference scheme is based on a fully distributed algorithm that iteratively sets the signal-to-interference-plus-noise (SINR) targets and corresponding transmit power levels. We find that the LTE-based power control approach performs close to the optimal scheme provided that the associated parameters are properly set.

Abstract. This paper considers real-time packet forwarding over wireless multi-hop networks with lossy and bursty links. Our objective is to maximize the probability that individual packets reach their destination before a hard deadline. The loss processes on links are modeled by finite-state Markov chains. While the parameters of the Markov chains are assumed to be known, the instantaneous channel states are not accessible but have to be estimated from observations of successes and failures of actual packet transmissions. We formulate the forwarding problem as a partially observable Markov decision process and derive the optimal forwarding policy. A novel technique, based on maximum-volume inscribed ellipsoids, for computing approximate solutions with reduced implementation complexity is proposed. We further discuss structural properties of the value function and the optimal actions. Finally, numerical examples illustrate the power of the developed techniques.

Abstract. Graphical Gaussian Models (GGMs) are a promising approach to identify gene-regulatory networks. Such models can be robustly inferred by solving the sparse inverse covariance selection (SICS) problem. With the high dimensionality of genomics data, fast methods capable of solving large instances of SICS are needed. We developed a novel network modeling tool, Ultranet, that solves the SICS problem with significantly improved efficiency. Ultranet combines a range of mathematical and programmatical techniques, exploits the structure of the SICS problem, and enables computation of genome-scale GGMs without compromising analytic accuracy.

Abstract. This paper studies minimum-energy packet forwarding policies for communicating sensor measurements from plant to controller over an unreliable multi-hop network so as to guarantee that the optimal controller achieves a prespecified closed-loop performance. For fixed sampling interval, we demonstrate that the minimal linear-quadratic control loss is monotonically decreasing in the reliability of the sensor-to-controller communication. This allows us to decompose the overall design problem into two separate tasks: finding the minimum end-to-end reliability that allows to achieve a prespecified linear-quadratic loss, and developing minimum-energy packet forwarding policies under a deadline-constrained reliability requirement. We develop optimal solutions for both subproblems and show how the co-designed system with minimum forwarding energy cost and guaranteed LQG control performance can be found by a one-dimensional search over admissible sampling periods. The paper ends with a numerical example which demonstrates the effectiveness of the proposed framework.

Abstract. This paper studies an asynchronous randomized gossip algorithm under unreliable communication. At each instance, two nodes are selected to meet with a given probability. When nodes meet, two unreliable communication links are established with communication in each direction succeeding with a time-varying probability. It is shown that two particularly interesting cases arise when these communication processes are either perfectly dependent or independent. Necessary and sufficient conditions on the success probability sequence are proposed to ensure almost sure consensus or epsilon-consensus. Weak connectivity is required when the communication is perfectly dependent, while double connectivity is required when the communication is independent. Moreover, it is proven that with odd number of nodes, average preserving turns from almost forever (with probability one for all initial conditions) for perfectly dependent communication, to almost never (with probability zero for almost all initial conditions) for the independent case. This average preserving property does not hold true for general number of nodes. These results indicate the fundamental role the node interactions have in randomized gossip algorithms.

Abstract. We propose a regularized saddle-point algorithm for convex networked optimization problems with resource allocation constraints. Standard subgradient methods suffer from slow convergence and require excessive communication when applied to problems of this type. Our approach offers an alternative way to address these problems, and ensures that each iterative update step satisfies the resource allocation constraints. We derive step-size conditions under which the distributed algorithm converges geometrically to the regularized optimal value, and show how these conditions are affected by the underlying network topology. We illustrate our method on a robotic network application example where a group of mobile agents strive to maintain a moving target in the barycenter of their positions.

Abstract. Many properties of interest in graph structures are based on the nodes' average degree (i.e., the average number of edges incident to/from each node). In this work, we present asynchronous distributed algorithms, based on ratio consensus, that can be used to accurately estimate the number of nodes in a multi-component system whose communication topology is described by a directed graph. In addition, we describe an asynchronous distributed algorithm that allows each node to introduce or terminate links in order to reach a target average degree in the network. Such an approach can be useful in many realistic scenarios; for example, for the introduction and removal of renewable energy resources in a power network, while maintaining an average degree that fulfils some structural and dynamical properties and/or optimises some performance indicators of the network. The effectiveness of the proposed algorithms is demonstrated via illustrative examples.

Abstract. This paper studies the problem of optimal forwarding for reliable and energy-efficient real-time communication over lossy networks. We impose a strict per-packet latency bound and develop forwarding policies that maximize the probability that the packet is delivered within the specified deadline minus a transmission energy cost. A solution to this problem allows to characterize the set of achievable latency-reliability pairs and to trace out the Pareto frontier between achievable deadline-constrained reliability and transmission energy cost. We develop dynamic programming-based solutions under a finite state Markov channel model. Particular instances with Bernoulli and Gilbert-Elliot loss models that admit numerically efficient solutions are discussed and our results are demonstrated on several examples.

Abstract. The alternating direction method of multipliers is a powerful technique for structured large-scale optimization that has recently found applications in a variety of fields including networked optimization, estimation, compressed sensing and multi-agent systems. While applications of this technique have received a lot of attention, there is a lack of theoretical support for how to set the algorithm parameters, and its step-size is typically tuned experimentally. In this paper we consider three different formulations of the algorithm and present explicit expressions for the step-size that minimizes the convergence rate. We also compare our method with one of the existing step-size selection techniques for consensus applications.

Abstract. This paper develops a controller synthesis method for distributed LQG control problems under output-feedback. We consider a system consisting of three interconnected linear subsystems with a delayed information sharing structure. While the state-feedback case has previously been solved, the extension to output-feedback is nontrivial as the classical separation principle fails. To find the optimal solution, the controller is decomposed into two independent components: a centralized LQG-optimal controller under delayed state observations, and a sum of correction terms based on additional local information available to decision makers. Explicit discrete-time equations are derived whose solutions are the gains of the optimal controller.

Abstract. Opportunistic routing is widely known to have substantially better performance compared to traditional unicast routing in wireless networks with lossy links. However, wireless sensor networks are heavily duty-cycled, i.e. they frequently enter deep sleep states to ensure long network life-time. This renders existing opportunistic routing schemes impractical, as they assume that nodes are continuously awake and can overhear other transmissions in the network. In this paper, we introduce a novel opportunistic routing metric that takes duty cycling into account. By analytical performance modeling and simulations, we show that our routing scheme results in significantly reduced delay and improved energy efficiency compared to traditional unicast routing. The method is based on a new metric, EDC, that reflects the expected number of duty cycled wakeups that are required to successfully deliver a packet from the source to the destination. We devise distributed algorithms that find the EDC-optimal forwarding path, i.e. the optimal subset of neighbors that each node should permit to forward its packets. We compare the performance of the new routing with traditional ETX-optimal single path routing in both simulations and testbed-based experiments.

Abstract. This paper proposes a supervisory control structure for networked systems with time-varying delays. The control structure, in which a supervisor triggers the most appropriate controller from a multi-controller unit, aims at improving the closed-loop performance relative to what can be obtained using a single robust controller. Our analysis considers average dwelltime switching and is based on a novel multiple Lyapunov-Krasovskii functional. We develop analysis conditions that can be veri ed by semi-defi nite programming, and show that the associated state feedback synthesis problem also can be solved using convex optimization. Small and large scale networked control systems are used to illustrate the effectiveness of our approach.

Abstract. Multichannel communication has been proposed as alternative to adaptive (single-channel) routing protocols for mitigating the impact of interference and link dynamics in wireless sensor networks. While several studies have advocated features of both techniques (not without running up against contradicting arguments) a comprehensive study that aligns these results is still lacking. This paper aims at filling this gap. We present an experimental test bed setup used to perform extensive measurements for both single-channel and multichannel communication. We first analyze single-channel and multichannel communication over a single-hop in terms of packet reception ratio, maximum burst loss, temporal correlation of losses, and loss correlations across channels. Results show that multichannel communication with channel hopping significantly reduces link burstiness and packet loss correlation. For multi-hop networks, multi-channel communication and adaptive routing show similar end-to-end reliability in dense topologies, while multichannel communication can outperform adaptive routing in sparse networks with bursty links.

Abstract. This paper studies minimum-energy packet forwarding over multi-hop lossy networks under deadline and reliability constraints. We assume a routing topology in the form of a directed graph with packet loss processes on links described by finite-state Markov chains, and formulate the forwarding problem as a finite-horizon constrained Markov decision process. We show that the minimum energy forwarding policy under hard deadline and reliability constraint can be computed using dynamic programming, and that the optimal forwarding policy is a randomized policy over two history-independent and deterministic policies. Closed-form optimal policies are derived for some particular scenarios. Numerical examples show that the transmission energy cost of achieving reliabilities close to the maximum can be significant when links are bursty. In addition, transmission power adjustments can further reduce energy cost. Finally, we develop simple heuristic policies with a good balance between transmission energy cost and reliability.

Abstract. The standard interference functions introduced by Yates have been very influential on the analysis and design of distributed power control laws. While powerful and versatile, the framework has some drawbacks: the existence of fixed-points has to be established separately, and no guarantees are given on the rate of convergence of the iterates. This paper introduces contractive interference functions, a slight reformulation of the standard interference functions that guarantees existence and uniqueness of fixed-points and linear convergence rates.Even though some power control algorithms in the literature were shown to be contractive, to the best of our knowledge it is the first time that a general link between interference functions and contraction mappings is established in linear scale, that immediately provides the convergence rate.

Abstract. Traditionally, routing in wireless sensor networks consists of two steps: First, the routing protocol selects a next hop, and, second, the MAC protocol waits for the intended destination to wake up and receive the data. This design makes it dicult to adapt to link dynamics and introduces delays while waiting for the next hop to wake up. In this paper we introduce ORW, a practical opportunistic routing scheme for wireless sensor networks. In a dutycycled setting, packets are addressed to sets of potential receivers and forwarded by the neighbor that wakes up rst and successfully receives the packet. This reduces delay and energy consumption by utilizing all neighbors as potential forwarders. Furthermore, this increases resilience to wireless link dynamics by exploiting spatial diversity. Our results show that ORW reduces radio duty-cycles on average by 50\% (up to 90\% on individual nodes) and delays by 30\% to 90\% when compared to the state of the art.

Abstract. We generalize stochastic subgradient descent methods to situations in which we do not receive independent samples from the distribution over which we optimize, instead receiving samples coupled over time. We show that as long as the source of randomness is suitably ergodic - it converges quickly enough to a stationary distribution - the method enjoys strong convergence guarantees, both in expectation and with high probability. This result has implications for stochastic optimization in high-dimensional spaces, peer-to-peer distributed optimization schemes, decision problems with dependent data, and stochastic optimization problems over combinatorial spaces.

Abstract. Resource management schemes in multicell orthogonal frequency division multiplexing (OFDM) networks typically assume perfect channel knowledge at the transmitter or employ a statistical channel estimation error. In this paper we propose a model that explicitly captures the inherent tradeoff between the power allocated to transmitting data and pilot signals in multicell single input multiple output (SIMO) systems. We first study the asymptotic behavior of the required data power to reach a predefined signal-to-noise ratio (SNR) target as a function of the employed pilot power in a single OFDM cell, then develop a distributed multicell algorithm that strives to minimize the multi-cell sum data power with respect to a predefined signal-to-interference-and-noise-ratio (SINR) target vector. The results provide new insights in dimensioning the pilot and data transmit power levels and serve as a basis for developing distributed power control schemes in multicell systems.

Abstract. We consider the joint design of transmission schedules and controllers for networked control loops that use WirelessHART communication for sensor and actuator data. By parameterizing the design problem in terms of the sampling rate of the control loop, the co-design problem separates into two well-defined subproblems which admit optimal solutions: transmission scheduling should be done to maximize the delay-constrained reliability while the control design should optimize closed-loop performance under packet loss. We illustrate how these problems can be solved and demonstrate our co-design framework for the case of linear-quadratic control.

Abstract. Achieving low-power operation in wireless sensor networks with high data load or bursty traffic is challenging. The hidden terminal problem is aggravated with increased data and traditional backoff-based contention resolution mechanisms fail or induce high latency and energy costs. We model and analyze Strawman, a receiver-initiated contention resolution mechanism that copes with hidden terminals. We discuss parameter selection and propose improvements of the basic Strawman mechanism that achieves better scalability and higher throughput. We finally compare our improved protocol with traditional sender-initiated slotted CSMA, and show that it outperforms CSMA in both throughput and scalability.

Abstract. Routing configurations that have been optimized for a nominal traffic scenario often display significant performance degradation when they are subjected to real network traffic. These degradations are due to the inherent sensitivity of classical optimization techniques to changes in model parameters combined with the significant traffic variations caused by demand fluctuations, component failures and network reconfigurations. In this paper, we review important sources for traffic variations in data networks and describe tractable models for capturing the associated traffic uncertainty. We demonstrate how robust routing settings with guaranteed performance for all foreseen traffic variations can be effectively computed via memory efficient iterative techniques and polynomial-time algorithms. The techniques are illustrated on real data from operational IP networks.

Abstract. Fast convergecast is a critical functionality for wireless networks deployed for industrial monitoring and control. We address the time- and channel-optimal link scheduling problem for convergecast in multi-line networks, operating according to the recent WirelessHART standard. We first establish the lower bound on convergecast time and the lower bound on the number of channels for time-optimal convergecast. Then we present optimal scheduling policy for time-optimal convergecast and near-optimal policy for jointly time- and channel-optimal convergecast. Numerical and simulation results show that our scheme can provide fast convergecast inWirelessHART networks.

Abstract. We generalize stochastic subgradient descent methods to situations in which we do not receive independent samples from the distribution over which we optimize, but instead receive samples that are coupled over time. We show that as long as the source of randomness is suitably ergodic - it converges quickly enough to a stationary distribution - the method enjoys strong convergence guarantees, both in expectation and with high probability. This result has implications for stochastic optimization in high-dimensional spaces, peer-to-peer distributed optimization schemes, and stochastic optimization problems over combinatorial spaces.

Abstract. This paper explores the use of accelerated gradient methods in networked optimization. Optimal algorithm parameters and associated convergence rates are derived for distributed resource allocation and consensus problems, and the practical performance of the accelerated gradient algorithms are shown to outperform alternatives in the literature. Since the optimal parameters for the accelerated gradient method depends on upper and lower bounds of the Hessian, we study how errors in these estimates influence the convergence rate of the algorithm. This analysis identifies, among other things, cases where erroneous estimates of the Hessian bounds cause the accelerated method to have slower convergence than the corresponding (non-accelerated) gradient method. An application to Internet congestion control illustrates these issues.

Abstract. Emerging applications in industrial automation as well as tracking and monitoring applications of humans, objects or animals share common requirements: micro-mobility, high-throughput, and two-way end-to-end communications. In this paper we present MobiSense, a MAC layer and routing architecture for micro-mobility environments providing reliable and energy-efficient communication and low-latency handoffs. MobiSense's energy-efficiency and reliability comes from a set of carefully chosen design elements: rapid network information gathering, rapid network (re)admission and convergence, distributed network formation, and dynamic scheduling. Testbed evaluations show that a mobile sensor achieves: (i) reliability above 95% even in scenarios with high data rates of 6pps/node; (ii) low latency-handoffs typically below 1 second; (iii) a high aggregate system throughput of more than 95kbps; (iv) two-way communication without the need for flooding; and (v) communication at very low duty-cycles below 4% at 6pps/node.

Abstract. This paper studies the problem of joint routing and transmission scheduling for reliable real-time communication over lossy networks. The authors impose a strict latency bound on the packet delivery from source to destination and develop transmission scheduling policies that maximize the probability that the packet is delivered within the specified deadline. A solution to this problem allows to characterize the set of achievable latencies and packet loss probabilities for a given network. They develop dynamic programming-based solutions for deadline-constrained maximum reliability routing under Bernoulli and Gilbert-Elliot packet loss models.

Abstract. The traditionally wired automation infrastructure is quickly migrating to more flexible and scalable wireless solutions. To cope with the stringent requirements of process automation in terms of latency and reliability, the network resources must be optimized to ensure timely and reliable communication. This paper considers the joint routing and transmission scheduling problem for reliable real-time communication over lossy networks. Specifically, we impose a strict latency bound for packet delivery from source to destination, and devise optimal transmission scheduling policies that maximize the success probability of delivering the packet within the specified deadline. A solution to this problem allows to characterize the set of achievable latencies and packet reliability for a given network. We offer a complete understanding of the problem when erasure events on links are independent and follow a Bernoulli process. We consider both static and dynamic resource allocation policies, and compare them in numerical examples.

Abstract. There has been a recent surge in research activities related to networked control of large-scale systems. These "cyber-physical" systems can be found throughout society, from industrial production plants, to water and energy distribution networks and transportation systems. They are characterized by tight coordination of a pervasive sensing infrastructure, distributed computing elements, and the physical world. Developed from work presented at the 3rd WIDE PhD School on Networked Control Systems held in Siena in July 2009, Networked Control Systems contains tutorial introductions to key research topics in the area of networked control. Classroom pdf slides used in the PhD school presentations can be downloaded from www.springer.com/ISBN to assist academic teachers in using the material with their own classes. The contributing authors are renowned experts in the field so that the book provides a single point of entry to a diverse and exiting research area. PhD students and researchers in control and industrial communications, as well as practitioners in the area of large-scale control systems will find the contents of this volume highly informative.

Abstract. This chapter discusses technologies and models for low power wireless industrial communication. The aim of the text is to narrow the gap between the models used in the theoretical control literature with models that arise when tools from communication theory are used to model emerging standards for industrial wireless. The chapter provides a tutorial overview covering basic concepts and models for wireless propagation, medium access control, multi-hop networking, routing and transport protocols. Throughout, an effort is made to describe both key technologies and associated models of control-relevant characteristics such as latency and loss. Some existing and emerging specifications and standards, including Zigbee, WirelessHART and ISA100, are described in some detail, and links are made between the developed models and useful network abstractions for control design.

Abstract. This chapter provides a tutorial overview of distributed optimization and game theory for decision-making in networked systems. We discuss properties of first-order methods for smooth and non-smooth convex optimization, and review mathematical decomposition techniques. A model of networked decision-making is introduced in which a communication structure is enforced that determines which nodes are allowed to coordinate with each other, and several recent techniques for solving such problems are reviewed. We then continue to study the impact of noncooperative games, in which no communication and coordination are enforced. Special attention is given to existence and uniqueness of Nash equilibria, as well as the efficiency loss in not coordinating nodes. Finally, we discuss methods for studying the dynamics of distributed optimization algorithms in continuous time.

Abstract. Recent technological developments and the need for global control strate- gies to meet with stringent performance requirements rendered the use of wireless sensor networks (WSN) of prime importance for today's automa- tion. Such communication devices heavily affect the information transport, especially when a multi-hop configuration is introduced to minimize theWSN energy consumption. The associated time-delays are strongly varying and ne- cessitate the design of a dedicated control approach for remote regulation, as proposed in this chapter. First, the communication process is analyzed and illustrated with the Breath protocol, which results in a description of the de- lay in the frequency domain. Such analysis motivates the use of a CUMSUM Kalman filter to estimate the delay from round-trip-time (RTT) measure- ments while selecting the desired frequencies. This estimation then allows for the setup of a state-predictor that ensures a finite spectrum assignment (FSA) on the closed loop spectrum. The efficiency of this approach and the impact of packet losses is finally investigated on an inverted pendulum using experimental network measurements.

Abstract. This paper considers multiaccess control for the uplink in orthogonal-frequency-division-multiple-access (OFDMA) wireless networks. To avoid extensive information exchange with the access point in centralized approaches, we propose a distributed threshold-based scheme, where each user accesses multiple channels simultaneously based on a comparison between measured channel gains and a channel gain threshold. Each user will adapts its channel gain threshold based on local measurements of collision on each channel and the energy consumption for channel contention. The problem is formulated as a constrained non-cooperative game. We show existence and uniqueness of the Nash equilibrium. A gradient-based algorithm is proposed to update the channel gain threshold. Furthermore, the convergence of this algorithm is proved. In addition, for heterogeneous systems, our proposed scheme can maintain multiuser diversity gains considering the time-varying channel gain and energy consumption. Compared with peer distributed OFDMA schemes and random channel selection algorithms, our proposed schemes reduce overhead and achieve a higher throughput.

Abstract.

Abstract. Network multiple input, multiple output (MIMO) systems are built around a broadband backbone network that allows for the fast communication of channel state information (CSI) as well as user data between different base stations. Previous works have shown that multicell channel adaptive (opportunistic) power control can minimize the sum power or maximize the sum rate when the backbone is used for the exchange of CSI in network MIMO systems. In this work we investigate the gains of multicell opportunistic power control under per user fairness constraints when both CSI and user data are shared between multiple sites. We find that multicell opportunistic power control working in concert with uplink joint signal detection is an efficient means both for the capacity and the power control problems that not only minimizes sum power or maximizes overall capacity, but is also able to provide arbitrary level of fairness.

Abstract. We consider the problem of setting the uplink signal-to-noise-and-interference (SINR) target and allocating transmit powers for mobile stations in multicell spatial multiplexing wireless systems. Our aim is twofold: to evaluate the potential of such mechanisms in network multiple input multiple output (MIMO) systems, and to develop scalable numerical schemes that allow real-time near-optimal resource allocation across multiple sites. We formulate two versions of the SINR target and power allocation problem: one for maximizing the sum rate subject to power constraints, and one for minimizing the total power needed to meet a sum-rate target. To evaluate the potential of our approach, we perform a semianalytical study in Mathematica using the augmented Lagrangian penalty function method. We find that the gain of the joint optimum SINR setting and power allocation may be significant depending on the degree of fairness that we impose. We develop a numerical technique, based on successive convexification, for real-time optimization of SINR targets and transmit powers. We benchmark our procedure against the globally optimal solution and demonstrate consistently strong performance in realistic network MIMO scenarios. Finally, we study the impact of near optimal precoding in a multicell MIMO environment and find that precoding helps to reduce the sum transmit power while meeting a capacity target.

Abstract. This paper studies networked estimation over a communication channel shared by a contention-based medium access protocol. A collection of N identical and physically decoupled scalar systems are sampled without sensor noise and transmitted over a common channel, using a contention-based medium access mechanism. We first carry out a calculation of the average distortion in estimation with irregular samples. Given the rate of packet generation at sensors, we characterize the traffic characteristics of the some contention-based MAC schemes. This lets us derive the statistics of inter-arrival times which in turn allows us to compute the packet loss rates and also the statistics of delay within a sample period. Using these results, we track the estimation performance as the sample generation rate and the number of contending nodes are varied. We provide a heuristic rule-of-thumb for choosing the sampling interval which minimizes the average distortion. By combining the network traffic characterization with that of the estimation performance, we show this rule performs pretty well. Carrying along the same lines, we are able to compute the scaling limits of estimation performance with respect to the number of contending nodes.

Abstract. Current proposals for joint power and rate allocation protocols in ad hoc networks require a large signaling overhead, and do not adhere to the natural time-scales of transport and power control mechanisms. We present a solution that overcomes these issues. We pose the protocol design as a network utility maximization problem and adopt primal decomposition techniques to devise a novel distributed cross-layer design for transport and physical layer that achieves the optimal network operation. Our solution has several attractive features compared to alternatives: it adheres to the natural time-scale separation between rapid power control updates and slower end-to-end rate adjustments; it allows simplified power control mechanisms with reduced signalling requirements, and distributed slow rate cross-layer signalling mechanisms; and it maintains feasibility at each iteration. We validate the theoretical framework and compare the solution alternatives with numerical examples.

Abstract. We consider the problem of setting the uplink signal-to-noise-and-interference (SINR) target and allocating transmit powers for mobile stations in multicell spatial multiplexing wireless systems. Our aim is twofold: to evaluate the potential of such mechanisms in coordinated multipoint transmission (CoMP) systems, and to develop scalable numerical schemes that allow real-time near-optimal resource allocation across multiple sites. We formulate two versions of the SINR target and power allocation problem: one for maximizing the sum rate subject to power constraints, and one for minimizing the total power needed to meet a sum-rate target. To evaluate the potential of our approach, we perform a semi-analytical study in Mathematica using the augmented Lagrangian penalty function method. We find that the gain of the joint optimum SINR setting and power allocation may be significant depending on the degree of fairness that we impose. We develop a numerical technique, based on successive convexification, for real-time optimization of SINR targets and transmit powers. We benchmark our procedure against the globally optimal solution, and demonstrate consistently strong performance in realistic CoMP scenarios.

Abstract. We characterize the stability and achievable performance of networked estimation under correlated packet losses described by the Gilbert-Elliot model. For scalar continuous-time linear systems, we derive closed-form expressions for the mean-square distortion of the optimal estimator. The conditions for stable mean square estimation error are equivalent to those obtained previously for stability of `peak distortions'. We study how the estimator performance depends on loss probability and loss burst length, and show that the mean-square distortion remains bounded if the average burst length does not exceed a calculated bound. The main new finding is that, once we fix the mean length of loss bursts, the average packet loss rate influences the estimator's performance but not its stability.

Abstract. Networked systems are common and crucial. One of the canonical problems in such systems is distributed resource allocation. From this rather broad class of problems, we consider a convex non-smooth resource allocation problem with a global resource constraint. Specifically, the objective function is separable and consists of a sum of convex functions, each associated with a node in a given network. Each component of the objective depends on a single variable local to the associated node and the sum of all local variables must remain constant at all times. For scalability, we constrain the nodes to only communicate and exchange resources with their immediate neighbors. We propose an algorithm that combines subgradient optimization with distributed averaging. Starting the algorithm from a feasible point, the nodes iteratively exchange resources with their neighbors to get close to the optimal set while satisfying the total resource constraint at all times. We show that under mild technical conditions the algorithm converges in an epsilon-sense, as long as the stepsize is chosen sufficiently small and the distributed averaging process is sufficiently accurate. We derive expressions for how the stepsize and the number of consensus iterations affect the accuracy of the final result.

Abstract. Real-time data delivery is a critical issue in wirelessHART networks. This paper develops a novel mathematical programming framework for joint routing and link scheduling of deadline-constrained traffic in wirelessHART networks. The general framework explores dynamic network flows on a time-expanded graph model and can provide flexible solutions for a variety of real-time data delivery problems. Data evacuation, an important communication paradigm in wirelessHART networks, is a special case of this general framework. We establish the lower bound on evacuation time for line, multi-line and binary tree networks. Moreover, we design a novel scheduling algorithm for data evacuation in binary tree networks, and prove that this scheduling algorithm can always achieve the lower bound on evacuation time. We evaluate our scheduling algorithm through numerical simulations, and results show that our algorithm can always minimize the evacuation time with the least number of channels.

Abstract. This paper describes a methodology for controller and communication scheduling co-design in control systems operating over wirelessHART networks. Data collection and dissemination operations are identified and scheduled to minimize the nominal communication latency. Techniques for improving the reliability of the network when link transmissions are unreliable are discussed, and a Markov-chain model for computing the latency distribution of data collection operations for a given schedule is proposed. The resulting latency models allow to represent the networked control loop as a jump-linear system, whose performance can be analyzed using techniques from stochastic control. We demonstrate how this framework can be used to co-design a networked LQG controller for a five-by-five MIMO control loop.

Abstract. Switched systems are described by a set of continuous state-space models together with conditions that decide which model of this set is valid for the current continuous state. As an extension of the classical linear or affine state-space representations of dynamical systems, this modelling formalism has been thoroughly investigated, as this chapter shows. The identification of the model parameters, observability, and stability analysis as well as methods for stabilization and control of switched systems are surveyed. As shown in the last section, many analysis and design problems for switched systems have a high computational complexity or are even undecidable.

Abstract. We present an algorithm that generalizes the randomized incremental sub gradient method with fixed step size due to Nedic and Bertsekas. Our novel algorithm is particularly suitable for distributed implementation and execution, and possible applications include distributed optimization, e.g., parameter estimation in networks of tiny wireless sensors. The stochastic component in the algorithm is described by a Markov chain, which can be constructed in a distributed fashion using local information only. We provide a detailed convergence analysis of the proposed algorithm and compare it with existing, both deterministic and randomized, incremental sub gradient methods.

Abstract. We study the problem of routing under statistical traffic uncertainty. Models for characterizing the statistical uncertainty which arises when the traffic matrix is estimated from link loads using a maximum likelihood scheme are given, and associated optimization models are formulated for finding routing settings that are insensitive to likely estimation errors. Both statistical and worst-case ellipsoidal traffic models are treated. We demonstrate how the routing optimization can be performed in polynomial time, and compare such algorithms with alternatives based on combined constraint and column generation. The proposed techniques are evaluated in several numerical examples.

Abstract. Convergecast, in which data from a set of sources is routed toward one data sink, is a critical functionality for wireless networks deployed for industrial monitoring and control. We address the joint link scheduling and channel assignment problem for convergecast in networks operating according to the recent WirelessHART standard. For a linear network with N single-buffer devices, we demonstrate that the minimum time to complete convergecast is 2N-1 time-slots, and that the minimum number of channels required for this operation is ceil(N/2). When the devices are allowed to buffer multiple packets, we prove that the optimal convergecast time remains the same while the number of required channels can be reduced to ceil(N-sqrt(N*(N-1)/2)). For both cases, we present jointly time- and channel-optimal scheduling policies with complexity O(N^2). Numerical results demonstrate that our schemes are also efficient in terms of memory utilization.

Abstract. This paper presents efficient transmission schemes for optimal and distributed cross-layer design in DS-CDMA wireless ad-hoc networks. We pose the protocol design as a network utility maximization problem and adopt primal decomposition techniques to design novel distributed solutions for power control, transport rate and queue management that jointly achieve the optimal network operation. Compared with similar approaches, the proposed protocol adheres to the natural time-scale separation between rapid power control updates and slower end-to-end rate adjustments. We propose a simplified power control mechanisms with reduced signalling requirements and design two optimal distributed mechanisms to handle the cross-layer signalling. To validate our approach, we present a detailed implementation of a cross-layer adapted networking stack for DS-CDMA ad-hoc networks in ns-2. We describe several critical issues that arise in the implementation, but are typically neglected in the theoretical protocol design, and compare the solution alternatives in extensive simulations.

Abstract. Motivation: Multimillion-probe microarrays allow detection of gains and losses of chromosomal material at unprecedented resolution. However, the data generated by these arrays are several-fold larger than data from earlier platforms, creating a need for efficient analysis tools that scale robustly with data size. Results: We developed a new aberration caller, Ultrasome, that delineates genomic changes-of-interest with dramatically improved efficiency. Ultrasome shows near-linear computational complexity and processes latest-generation copy number arrays about 10,000 times faster than standard methods with preserved analytic accuracy. Availability: www.broad.mit.edu/ultrasome.

Abstract. Novel event-triggered sensing and actuation strategies are presented for networked control systems with limited communication resources. Two architectures are considered: one with the controller co-located with the sensor and one with the control co-located with the actuator. A stochastic control problem with an optimal stopping rule is shown to capture two interesting instances of these architectures. The solution of the problem leads to a parametrization of the control alphabet as piecewise constant commands. The execution of the control commands is triggered by stopping rules for the sensor. In simple situations, it is possible to analytically derive the optimal controller. Examples illustrate how the new event-based control and sensing strategies outperform conventional time-triggered schemes.

Abstract. In this paper we propose a subgradient method for solving coupled optimization problems in a distributed way given restrictions on the communication topology. The iterative solution procedure maintains local variables at each node and relies on local subgradient updates in combination with a consensus process. The local subgradient steps are applied simultaneously as opposed to the standard sequential or cyclic procedure. We study convergence properties of an unconstrained version of the proposed scheme using results from consensus theory and approximate subgradient methods. The framework is illustrated on an optimal distributed finite-time rendezvous problem.

Abstract. This paper considers distributed protocol design for joint sub-carrier, transmission scheduling and power management in uplink/downlink multi-cellular OFDMA wireless networks. The optimal solution to this problem is hard to achieve, both in theory and in practice. We propose a fully decentralized resource allocation scheme combining decomposition methods for convex optimization with a strategic non-cooperative game formulation of the power and sub-carrier allocation subproblem. Although the final protocols are suboptimal, they drastically reduce computation time while maintaining the overall system performance close to the optimal, exhibiting strong robustness to multiple access interference. We validate the theoretical framework and quantify the performance with numerical examples.

Abstract. We treat a problem in networked estimation where the focus is on sampling and transmitting measurements of the plant over a shared medium. The object is to choose the sampling rate at the sensor while taking the statistics of a contention based MAC protocol into account. In particular, we seek a trade-off between the reliable delivery of individual data packets and the input data load on the communication medium. Our analysis of the shared channel computes a probability of packet loss for an assumed IID loss process. This loss rate depends on the input packet stream intensities. We compute the estimation distortion with IID losses of periodically generated samples, as a function of the packet loss rate. This throws up a condition for stable estimator performance. We investigate the scalability limits of this stability as a function of the number of nodes. When stable estimation is possible, we provide a procedure that computes the input packet rate for the network that minimizes the average estimation distortion. We reproduce the analysis of estimation performance when the sensors sample asynchronously according to independent Poisson counters.

Abstract. Distributed averaging problems are a subclass of distributed consensus problems, which have received substantial attention from several research communities. Although many of the proposed algorithms are linear iterations, they vary both in structure and state dimension. In this paper, we investigate the performance benefits of adding extra states to distributed averaging iterations. We establish conditions for convergence and discuss possible ways of optimizing the convergence rates. By numerical examples, it is shown that the performance can be significantly increased by adding extra states. Finally, we provide necessary and sufficient conditions for convergence of a more general version of distributed averaging iterations.

Abstract. Distributed averaging problems are a subclass of distributed consensus problems, which have received substantial attention from several research communities. Although many of the proposed algorithms are linear iterations, they vary both in structure and state dimension. In this paper, we investigate the performance benefits of adding extra states to distributed averaging iterations. We establish conditions for convergence and discuss possible ways of optimizing the convergence rates. By numerical examples, it is shown that the performance can be significantly increased by adding extra states. Finally, we provide necessary and sufficient conditions for convergence of a more general version of distributed averaging iterations.

Abstract. We describe and evaluate a suite of distributed and computationally efficient algorithms for solving a class of convex optimization problems in wireless sensor networks. The problem class has wide applications in estimation, detection, localization, coordination and resource sharing. We focus on peer-to-peer algorithms where nodes only exchange data with their immediate neighbors, and consider three distinct alternatives: a dual-based broadcast algorithm, a novel stochastic unicast algorithm, and a linear broadcast algorithm tailored for least-squares problems. We implement the algorithms in the network simulator NS2 and present extensive simulation results for random topologies.

Abstract. A consensus problem consists of finding a distributed control strategy that brings the state or output of a group of agents to a common value, a consensus point. In this paper, we propose a negotiation algorithm that computes an optimal consensus point for agents modeled as linear control systems subject to convex input constraints and linear state constraints. By primal decomposition and incremental subgradient methods, it is shown that the algorithm can be implemented such that each agent exchanges only a small amount of information per iteration with its neighbors.

Abstract. Genomic regions with altered gene expression are a characteristic feature of cancer cells. We present a novel method for identifying such regions in gene expression maps. This method is based on total variation minimization, a classical signal restoration technique. In systematic evaluations, we show that our method combines top-notch detection performance with an ability to delineate relevant regions without excessive over-segmentation, making it a significant advance over existing methods. Software (Rendersome) is provided.

Abstract. This paper discusses tuning of PED controllers for varying time-delay systems. We analyze the properties of the AMIGO tuning rules of Astrom and Hagglund applied to varying time-delay systems and propose improved tuning rules which increase the robustness to delay variations at the expense of a small degradation in nominal performance. We suggest a tuning scheme that uses the simple AMIGO tuning on an extended plant, and define the design concepts for extending the plant. This approach allows treating the maximum time-delay as a design parameter for the tuning rules. The proposed tuning rules are compared via simulations.

Abstract. We propose a distributed algorithm that solves a special class of optimization problems using only peer-to- peer communication. One application is parameter estimation problems in sensor networks. Current decentralized algorithms for solving this class of optimization problems typically rely on passing around a parameter estimate in a ring consisting of all network nodes. In our algorithm, which extends the randomized incremental subgradient method with fixed stepsize due to Nedic and Bertsekas, nodes maintain individual estimates and need to exchange information only with their neighbors. We establish approach of the solution to an interval around the optimum value. We illustrate the algorithm's performance, in terms of convergence rate and communication cost relative to alternative schemes, through several numerical examples.

Abstract. Configuration of the routing is critical for the quality and reliability of the communication in a large IP backbone. Large traffic shifts can occur due to changes in the inter-domain routing that are hard to control by the network operator. This paper describes a framework for modeling potential traffic shifts due to BGP reroutes, calculating worst-case traffic scenarios, and finding a single routing configuration that is robust against all possible traffic shifts due to BGP reroutes. The benefit of our approach is illustrated using BGP routing updates and network topology from an operational IP network. Experiments demonstrate that the robust routing is able to obtain a consistently strong performance under large inter-domain routing changes.

Abstract. Remote control over wireless multi-hop networks is considered. Time-varying delays for the transmission of sensor and control data over the wireless network are imposed by a randomized multi-hop routing protocol. The characterstics of the routing protocol together with lower-layer network mechanisms give rise to a delay process with high variance and stepwise changing mean. A new predictive control scheme with a delay estimator is proposed in the paper. The estimator is based on a Kalman filter with a change detection algorithm. It is able to track the delay mean changes but efficiently attenuate the high frequency jitter. The control scheme is analyzed and its implementation detailed. Network data from an experimental setup are used to illustrate the efficiency of the approach.

Abstract. We have proposed an algorithm for optimal real-time routing in multi-hop communication networks for multi-source/multi-sink connection. The algorithm deals with various capacity constraints in terms of communication limits and real-time constraints expressed as deadline for each particular flow of data. The objective is to find the optimal routing in terms of energy consumption. The algorithm is based on a data flow model leading to Linear Programming formulation and therefore it ensures polynomial-time complexity. An extension handling simultaneous real-time and non real-time routing is added. An example of data collection from 100 nodes is presented and performance experiments illustrating time complexity in dependence on the number of nodes are given.

Abstract. We consider the problem of joint congestion control and resource allocation in spatial-TDMA wireless networks. The design problem is posed as a utility maximization problem subject to link rate constraints which involve both transmission scheduling and power allocation. Starting from the performance limitations of a centralized optimization based on global network information, we proceed systematically in our development of two distributed and transparent protocols that rely on local information only. In the process, we introduce a novel decomposition method for convex optimization, establish its convergence for the utility maximization problem, and demonstrate how it suggests a distributed solution based on TCP/AQM and incremental updates of the transmission schedule. We develop a two-step procedure for finding the schedule updates and suggest two schemes for distributed link scheduling and power control under realistic interference models. Although the final protocols are suboptimal, we isolate and quantify the performance losses incurred by each simplification and demonstrate strong performance in examples.

Abstract. This paper considers the design of PID controllers for systems with varying time-delays. Using the concept of jitter margin combined with the AMIGO tuning rule methodology, novel tuning rules that are robust to varying time-delays are derived. In addition, we give an expression for the expected lower bound of the jitter margin as these tuning rules are applied. Extensive numerical evaluations demonstrate that, for wide range of processes, the new tuning rules achieve significant improvements in jitter margin at the expense of only slight decreases in other performance criteria.

Abstract. We consider the problem of joint end-to-end rate optimization and radio resource management in wireless OFDMA-based mesh networks. Radio units equipped with multiple radio interfaces are combined with the OFDMA medium access scheme to make up for the classical limitations of singlecarrier wireless networks. We pose the problem as a utility maximization problem subject to link-rate constraints, power control and transmission scheduling both in terms of time slots, channels and radio interfaces. The optimal solution to this problem is in general hard to achieve, both in theory and in practice. We propose an alternative solution approach that drastically reduces the computation time, and suggest a heuristic scheme that attempts to reduce the computation time even further while maintaining the overall system performance close to the optimal. For each scheme we validate the theoretical framework and quantify the performance with numerical examples.

Abstract. Wireless sensor networks are trying to find their way from relatively undemanding applications such as environmental monitoring to applications such as industrial control, which have stronger requirements in terms of security and predictability. Predictability cannot be achieved without coordination and the coordination of distributed entities and events requires time synchronization. Towards this end, the authors present a secure time synchronization service, which as their experimental results show does not degrade time synchronization accuracy.

Abstract. Ontological analysis facilitates the interpretation of microarray data. Here we describe new ontological analysis methods which, unlike existing approaches, are threshold-free and statistically powerful. We perform extensive evaluations and introduce a new concept, detection spectra, to characterize methods. We show that different ontological analysis methods exhibit distinct detection spectra, and that it is critical to account for this diversity. Our results argue strongly against the continued use of existing methods, and provide directions towards an enhanced approach.

Abstract. This paper presents a survey on transport and routing protocols for wireless sensor networks (WSN). Research challenges regarding the problem of end-to-end reliability are addressed in particular.

Abstract. A control theoretic analysis of a simple error correction scheme for lossy packet-switched networks is presented. Based on feedback information from the error correction process in the receiver, the sender adjusts the amount of redundancy using a so called extremum-seeking controller, which do not rely on any accurate model of the network loss process. The closed-loop system is shown to converge to a limit cycle in a neighborhood of the optimal redundancy. The result are validated using packet-based simulations with data from wireless sensor network experiments.

Abstract. In this paper we discuss the opportunities of replacing wirelines by wireless connections in automation systems. However, there are several challenges inherently associated with these opportunities. One of the major challenges is how to select a proper wireless connection protocol that achieves at least the minimum requirements of the automation system. These system requirements are discussed in the paper. Some wireless communication systems which could be used for wireless automation are briefly revised. Finally, we discuss the applicability of contemporary wireless protocols for wireless automation and whether a new wireless protocol needs to be defined for wireless automation systems. The augmentation of wireless technology to automation systems will improve the performance of those systems and also many new applications may be defined.

Abstract. We consider the problem of joint end-to-end bandwidth allocation and radio resource management in WiMax single-carrier wireless networks. The design problem is posed as a utility maximization problem subject to link rate constraints which involve transmission scheduling and power allocation. Inspired by a centralized algorithm for solving the associated optimization problem, we proceed systematically in our development of distributed resource allocation mechanisms. Contrary to the centralized algorithm, the proposed solution is distributed and of low computational complexity, generates schedules of finite length and with fixed time-slot durations, and acts on local neighborhood information only. Although the final scheme is suboptimal, we isolate and quantify the performance losses incurred and demonstrate strong performance in examples.

Abstract. This paper presents a global view of measurement-driven traffic engineering, explores the interplay between traffic matrix estimation and routing optimization and demonstrates how demand uncertainties can be accounted for in the optimization step to guarantee a robust and reliable result. Based on a unique data set of complete measured traffic matrices, we quantify the demand uncertainties in an operational IP network and demonstrate how a number of robust optimization schemes allow to find fixed MPLS configurations that are close to the performance limits given by time-varying routing under full demand knowledge. We present a novel scheme for computing a sparse MPLS mesh to complement a baseline routing, and explore how the performance depends on the size of the partial mesh. Corresponding methods for robust OSPF optimization are discussed and a number of challenges are detailed.

Abstract. Network performance can be increased if the traditionally separated network layers are jointly optimized. Recently, network utility maximization has emerged as a powerful framework for studying such cross-layer issues. In this paper, we review and explain three distinct techniques that can be used to engineer utility-maximizing protocols: primal, dual, and cross decomposition. The techniques suggest layered, but loosely coupled, network architectures and protocols where different resource allocation updates should be run at different time-scales. The decomposition methods are applied to the design of fully distributed protocols for two wireless network technologies: networks with orthogonal channels and network-wide resource constraints, as well as wireless networks where the physical layer uses spatial-reuse time-division multiple access. Numerical examples are included to demonstrate the power of the approach.

Abstract. In this paper we consider the problem of designing a distributed control strategy such that a linear combination of the states of a number of vehicles coincide at a given time. The vehicles are described by linear difference equations and are subject to convex input constraints. It is demonstrated how primal decomposition techniques and incremental subgradient methods allow us to find a solution in which each vehicle performs individual planning of its trajectory and exchanges critical information with neighbors only. We explore various communication, computation, and control structures, and demonstrate the performance of the algorithms by numerical examples.

Abstract. Gene expression profiling is a powerful technique for classifying hematologic malignancies. Its clinical use is, however, currently hindered by the need to collect large sets of expression profiles at each diagnostic facility. To overcome this limitation, we introduced cross-platform classification, allowing classifier construction using pre-existing microarray datasets. As proof-of-principle, we performed cross-platform classification of acute myeloid leukemia and childhood acute lymphoblastic leukemia using expression data from four different facilities. We show that cross-platform classification of these disorders is achievable, and, strikingly, that the diagnostic accuracy can be retained. We conclude that cross-platform classification constitutes an effective and convenient way to implement microarray diagnostics.

Abstract. The use of control-based methods for resource manage- ment in real-time computing and communication systems has gained a substantial interest recently. Applications ar- eas include performance control of web-servers, dynamic resource management in embedded systems, traffic con- trol in communication networks, transaction management in database servers, error control in software systems, and au- tonomic computing. Within the European EU/IST FP6 Net- work of Exellence ARTIST2 on Embedded System Design a roadmap on Control of Real-Time Computing Systems has recently been completed. The focus of the roadmap is how flexibility, adaptivity, performance and robustness can be achieved in a real-time computing or communication system through the use of control theory. The item that is controlled is in most cases the allocation of computing and communication resources, e.g., the distribution or schedul- ing of CPU time among different competing tasks, jobs, re- quests, or transactions, or the communication resources in a network. Due to this, control of computing systems also goes under the name of feedback scheduling. The roadmap is divided into six research areas: con- trol of server systems, control of CPU resources, control of communication networks, error control of software systems, feedback scheduling of control systems, and control mid- dleware. For each area an overview is given and challenges for future research are stated. The aim of this position paper is to summarize the conclusions concerning these research challenges.

Abstract. We consider the problem of designing distributed mechanisms for joint congestion control and resource allocation in spatial-reuse TDMA wireless networks. The design problem is posed as a utility maximization subject to link rate constraints that involve both power allocation and transmission scheduling over multiple time-slots. Starting from the performance limits of a centralized optimization based on global network information, we proceed systematically in the development of distributed and transparent protocols. In the process, we introduce a novel decomposition method for convex optimization, establish its convergence for the utility maximization problem and demonstrate how it suggests a distributed solution based on flow control optimization and incremental updates of the transmission schedule. We develop a two-step procedure for finding the schedule updates and suggest two schemes for distributed channel reservation and power control under realistic interference models. Although the final protocols are suboptimal, we isolate and quantify the performance losses incurred by each simplification and demonstrate strong performance in examples.

Abstract. The use of control-based methods for resource management in real-time computing and communication systems has gained a substantial interest recently. Applications areas include performance control of web-servers, dynamic resource management in embedded systems, traffic control in communication networks, transactionmanagement in database servers, error control in software systems, and autonomic computing.Within the European EU/IST FP6 Network of Exellence ARTIST2 on Embedded System Design a roadmap on Control of Real-Time Computing Systems has recently been completed. The focus of the roadmap is how flexibility, adaptivity, performance and robustness can be achieved in a real-time computing or communication system through the use of control theory.

Abstract. For many real-time applications running over packet-switched networks, it is important to maintain delivered data quality using a limited amount of network resources. It is therefore natural to employ cost functions that allow online trade-off between the experienced application quality and the resource usage. However, minimizing such cost functions requires perfect knowledge of the network state at the transmission side, while, in general, such information is only partially available. In this paper, we introduce a new adaptive error correction algorithm that optimizes the amount of redundancy based on the available information from the application and the network. An extremum-seeking control algorithm is employed to deal with the high level of uncertainty in the network models. The validity of our approach is illustrated in simulations with varying network loads and loss correlation.

Abstract. We consider the problem of finding the jointly optimal end-to-end communication rates, routing, power allocation and transmission scheduling for wireless networks. In particular, we focus on finding the resource allocation that achieves fair end-toend communication rates. Using realistic models of several media access schemes for interference-limited channels, we show how this cross-layer optimization problem can be formulated as a nonlinear mathematical program. We develop a specialized solution method, based on a nonlinear column generation technique, that converges to the optimal solution in a finite number of steps. We present computational results from a large set of networks and discuss the insight that can be gained about the influence of power control, spatial reuse, routing strategies and variable transmission rates on network performance.

Abstract. Error correction mechanisms enable control and other real-time applications to be executed over unreliable packet-switched networks. By adding carefully adjusted redundancy to transmitted data at the sender, it is possible to recover lost data at the receiver and thereby improve effective throughput. We describe simple models for packet loss, which allow us to find the optimal redundancy as a function of packet loss probability. Two feedforward control mechanisms based on the packet loss probability are presented: one that is computed off-line and another one using an on-line algorithm. A drawback with these approaches is their dependency on accurate network state information and precise loss models. To cope with these issues, we propose a new feedback solution that tracks the optimum using gradient estimation. Simulations in ns-2 illustrate the behavior of the error correction schemes, demonstrating that the feedback solution outperforms the feedforward solution in presence of model errors.

Abstract. Several approaches for cross-layer design, e.g., coordinating the traditionally separated layers in wireless networks, have been proposed. However, protocols that are close to achieving the performance bounds are still lacking. We propose three distributed algorithms for joint congestion control and resource allocation in networks with variable capacities subject to a global resource constraint. Examples include spectrum assignment in wireless networks and wavelength allocation in optical networks. For scalability, we impose the additional constraint that nodes can only negotiate and exchange resources with their neighbors. The proposed algorithms consist of two complementary approaches based on decomposition techniques, in which congestion control and resource allocations are performed on different time-scales. Two of the algorithms can be shown to converge without network delays. Copyright 2005 IFAC

Abstract. We present an efficient approach for cross-layer optimization of a class of wireless networks equipped with multi-user detectors. For a given network, the method provides the optimal operation of transport, routing and radio link layers as well as the optimal coordination across the layers. The algorithm combines a column generation procedure with an optimal greedy resource allocation scheme into a powerful numerical method for computing the performance limits for networks of significant sizes. The method is applied to a simple network scenario and performance benefits of multi-user detectors and cross-layer coordination over alternative schemes are investigated.

Abstract. We consider a linear system, such as an estimator or a controller, in which several signals are transmitted over wireless communication channels. With the coding and medium access schemes of the communication system fixed, the achievable bit rates are determined by the allocation of communications resources such as transmit powers and bandwidths, to different channels. Assuming conventional uniform quantization and a standard white-noise model for quantization errors, we consider two specific problems. In the first, we assume that the linear system is fixed and address the problem of allocating communication resources to optimize system performance. We observe that this problem is often convex (at least, when we ignore the constraint that individual quantizers have an integral number of bits), hence readily solved. We describe a dual decomposition method for solving these problems that exploits the problem structure. We briefly describe how the integer bit constraints can be handled, and give a bound on how suboptimal these heuristics can be. The second problem we consider is that of jointly allocating communication resources and designing the linear system in order to optimize system performance. This problem is in general not convex. We present an iterative heuristic method based on alternating convex optimization over subsets of variables, which appears to work well in practice.

Abstract. This paper considers the problem of estimating the point-to- point traffic matrix in an operational IP backbone. Contrary to previous studies, that have used a partial traffic matrix or demands estimated from aggregated Net flow traces, we use a unique data set of complete trafic matrices from a global IP network measured over fi ve-minute intervals. This allows us to do an accurate data analysis on the time-scale of typical link-load measurements and enables us to make a balanced evaluation of different traffic matrix estimation techniques. We describe the data collection infrastructure, present spatial and temporal demand distributions, investigate the stability of fan-out factors, and analyze the mean-variance relationships between demands. We perform a critical evaluation of existing and novel methods for traffic matrix estimation, including recursive fanout estimation, worst-case bounds, regularized estimation techniques, and methods that rely on mean-variance relationships. We discuss the weaknesses and strengths of the various methods, and highlight differences in the results for the European and American subnetworks.

Abstract.

Abstract. In wireless data networks, the optimal routing of data depends on the link capacities which, in turn, are determined by the allocation of communications resources (such as transmit powers and bandwidths) to the links. The optimal performance of the network can only be achieved by simultaneous optimization of routing and resource allocation. In this paper, we formulate the simultaneous routing and resource allocation (SRRA) problem, and exploit problem structure to derive efficient solution methods. We use a capacitated multicommodity flow model to describe the data flows in the network. We assume that the capacity of a wireless link is a concave and increasing function of the communications resources allocated to the link, and the communications resources for groups of links are limited. These assumptions allow us to formulate the SRRA problem as a convex optimization problem over the network flow variables and the communications variables. These two sets of variables are coupled only through the link capacity constraints. We exploit this separable structure by dual decomposition. The resulting solution method attains the optimal coordination of data routing in the network layer and resource allocation in the radio control layer via pricing on the link capacities.

Abstract. We consider the problem of finding the jointly optimal end-to-end communication rates, routing, power allocation and transmission scheduling for wireless networks. We focus on throughput and fairness between end-to-end rates and formulate the associated cross-layer design problem as a nonlinear mathematical program. We develop a specialized solution method, based on a nonlinear column generation technique, that applies to a wide range of media access schemes and converges to the optimal solution in a finite number of steps. The approach is applied to a large set of sample networks and the influence of power control, spatial reuse, routing strategies and variable transmission rates on network performance is discussed.

Abstract. The optimal routing of data in a wireless network depends on the link capacities, which, in turn, are determined by the allocation of transmit powers across the network. Thus, the optimal network performance can only be achieved by simultaneous optimization of routing and power allocation. In this paper, we study this joint optimization problem in CDMA data networks using convex optimization techniques. Although link capacity constraints of CDMA systems are not jointly convex in rates and powers, we show that coordinate projections or transformations allow the simultaneous routing and power allocation problem to be formulated as (in systems with interference cancellation) or approximated by (in systems without interference cancellation) a convex optimization problem which can be solved very efficiently. We also propose a heuristic link-removal procedure based on the convex approximation to further improve the system performance.

Abstract. Piecewise linear systems have a broad applicability in a wide range of engineering sciences: systems operating in different modes or subject to physical constraints are naturally modelled as piecewise linear; some of the most common nonlinearities in control systems, such as relays and saturations, are piecewise linear; etc. Although analyses of specific piecewise linear systems appeared already in the late 1800s, it is fair to say that the circuits and systems community was the first to recognize piecewise linear systems as an interesting system class in its own right. Demanding applications, a shortage of techniques for dealing with hybrid systems and the emergence of new computational tools has now sparked a strong interest for piecewise linear systems also in the control community. The purpose of this paper is to provide a short overview of some recent results in this field.

Abstract.

Abstract. In this paper, we formulate the problem of simultaneous routing and power allocation in code-division multiple access (CDMA) wireless data networks. In CDMA systems, the capacity of a link depends on not only the power allocated to itself, but also the powers allocated to other links (due to interferences). Since the capacity constraints are not jointly convex in communication rates and power allocations (a well-known fact, see [1]), a straightforward formulation of the SRRA problem is not a convex optimization problem and thus generally very hard to solve. We suggest an approximate capacity formula for relatively high signal to interference and noise ratios (SINRs) and show how a coordinate transform yields a convex formulation. We note that the optimization is naturally interpreted as the optimal coordination of routing and SINR-target selection for a distributed power control algorithm, and show how the use of approximate capacity constraints in the optimization makes this implementation robust to link gain variations.

Abstract. We consider a linear control system in which several signals are transmitted over communication channels with bit rate limitations. With the coding and medium access schemes of the communication system fixed, the achievable bit rates are determined by the allocation of communications resources such as transmit powers and bandwidths, to different communication channels. We model the effect of bit rate limited communication channels by uniform quantization and the quantization errors are modeled by additive white noises whose variances depend on the achievable bit rates. We optimize the stationary performance of the linear system by jointly allocating resources in the communication system and tuning parameters of the controller.

Abstract. In wireless networks, the optimal routing and resource allocation problems are coupled together through link capacities, which influence data routing and are deter- mined by resource (e.g., power and bandwidth) alloca- tion. We formulate the problem of simultaneous routing and resource allocation for wireless data networks as a convex optimization problem and exploit the separable structure of the problem via dual decomposition to develop efficient solution methods.

Abstract. This book presents a computational approach to the analysis of nonlinear and uncertain systems. The main focus is systems with piecewise linear dynamics. The class of piecewise linear systems examined has nonlinear, possibly discontinuous dynamics, and allows switching rules that incorporate memory and logic. These systems may exhibit astonishingly complex behaviors. Some aspects of the successful theory of linear systems and quadratic criteria are extended here to piecewise linear systems and piecewise quadratic criteria. The book also describes numerical procedures for assessing stability, computing induced gains, and solving optimal control problems for piecewise linear systems. These developments enable researchers to analyze a large and practically important class of control systems that are not easily dealt with when using other techniques.

Abstract. This book presents a computational approach to the analysis of nonlinear and uncertain systems. The main focus is systems with piecewise linear dynamics. The class of piecewise linear systems examined has nonlinear, possibly discontinuous dynamics, and allows switching rules that incorporate memory and logic. These systems may exhibit astonishingly complex behaviors. Some aspects of the successful theory of linear systems and quadratic criteria are extended here to piecewise linear systems and piecewise quadratic criteria. The book also describes numerical procedures for assessing stability, computing induced gains, and solving optimal control problems for piecewise linear systems. These developments enable researchers to analyze a large and practically important class of control systems that are not easily dealt with when using other techniques.

Abstract. We consider a linear system, such as a controller or estimator, in which several signals are transmitted over communication chan- nels with bit rate limitations. We model the effect of bit rate limited wireless channels by conventional uniform quantization, and use a standard white-noise model for quantization errors. We focus on finding the allocation of communication resources such as transmission powers, bandwidths, or time-slot fractions, that yields optimal system performance. We show that if the linear system is fixed, the problem of allocating communication resources is often convex. We discuss optimization algorithms that exploit the problem structure, and present efficient heuris- tics for obtaining integer-valued solutions. The problem of jointly allocating communication resources and designing the linear sys- tem is in general not convex, but can be solved heuristically in a way that exploits the problem structure and appears to work well in practice.

Abstract. In wireless data networks, the optimal routing of data depends on the link capacities which, in turn, are determined by the allocation of communications resources (such as transmit powers and bandwidths) to the links. The optimal performance of the network can only be achieved by simultaneous optimization of routing and resource allocation. In this paper, we formulate the simultaneous routing and resource allocation (SRRA) problem, and exploit problem structure to derive efficient solution methods. We use a capacitated multicommodity flow model to describe the data flows in the network. We assume that the capacity of a wireless link is a concave and increasing function of the communications resources allocated to the link, and the communications resources for groups of links are limited. These assumptions allow us to formulate the SRRA problem as a convex optimization problem over the network flow variables and the communications variables. These two sets of variables are coupled only through the link capacity constraints. We exploit this separable structure by dual decomposition. The resulting solution method attains the optimal coordination of data routing in the network layer and resource allocation in the radio control layer via pricing on the link capacities.

Abstract. This paper presents an approach to state initialization of heterogeneous mode-switching controllers. It is shown how the controller initialization that achieves the minimal settling time for the closed-loop system can be computed via convex optimization. Algorithms are given that minimize the worst-case settling time for all initial values in a polytope or an ellipsoid. The approach can also account for state and control constraints. Special attention is given to systems with bias disturbance and it is shown how the worst-case settling time can be minimized also when the exact value of the bias is not known. Finally, we show how the settling times can be improved further by adding an impulsive control at the switching instant. The impulsive control can be optimized jointly with the initial value compensator to achieve a minimal settling time.

Abstract.

Abstract.

Abstract. The use of piecewise quadratic cost functions is extended from stability analysis of piecewise linear systems to performance analysis and optimal control. Lower bounds on the optimal control cost are obtained by semidefinite programming based on the Bellman inequality. This also gives an approximation to the optimal control law. An upper bound to the optimal cost is obtained by another convex optimization problem using the given control law. A compact matrix notation is introduced to support the calculations and it is proved that the framework of piecewise linear systems can be used to analyze smooth nonlinear dynamics with arbitrary accuracy.

Abstract. This paper presents an approach to stability analysis of fuzzy systems. The analysis is based on Lyapunov functions that are continuous and piecewise quadratic. The approach exploits the gain-scheduling nature of fuzzy systems and results in stability conditions that can be verified via convex optimization over linear matrix inequalities. Examples demonstrate the many improvements over analysis based on a single quadratic Lyapunov function. Special attention is given to the computational aspects of the approach and several methods to improve the computational efficiency are described

Abstract. This paper reports the development of a Matlab toolbox for computational analysis of piecewise linear systems. The analysis is based on piecewise quadratic Lyapunov functions, which are computed via convex optimization. In this way, exponential stability and system perfor mance can be assessed. The toolbox also supports effi cient simulation of systems with discontinuous dynam ics and sliding modes. A set of intuitive commands for describing piecewise linear systems is included, mak ing the analysis routines easily accessible also for the inexperienced user.

Abstract. The recently developed technique for computation of piecewise quadratic Lyapunov functions is specialized to Lyapunov functions that are piecewise linear. This establishes a unified framework for computation of quadratic, piecewise quadratic, piecewise linear and polytopic Lyapunov functions. The search for a piecewise linear Lyapunov function is formulated as a linear programming prob- lem, and duality is used to address the non-trivial issue of partition refinements.

Abstract.

Abstract.

Abstract.

Abstract. Experiments have shown that the time is now ripe for a new generation of interactive learning tools for control. The tools are based on objects which admit direct graphical manipulation. During manipulations, objects are updated instantaneously, so that relations between objects are maintained all the time. The tools are natural complements to traditional education, and allow students to quickly gain insight and motivation. A high degree of interactivity has been found to be a key issue in the design. Together with a high bandwidth in the man-machine interaction, this enhances learning significantly. Another nice feature is the possibility to hide minor issues and focus on the essentials. It is not easy to describe the power of these tools adequately in text. The best way to appreciate them is simply to use them. We believe that there is a strong pedagogical potential for the type of tools that we have described. We are also of the opinion that we are only at the very beginning in the development of learning tools of this type. The addition of sound and animation are interesting avenues that should be pursued.

Abstract. We present interactive learning tools used in courses in automatic control at Lund Institute of Technology. The learning tools are aimed at improving the understanding of and intuition for the abstract parts of the control courses. The tools, mainly dynamic interactive modules for a course in sampled-data systems, are implemented in Matlab and can be used over the Internet.

Abstract. A novel stability criterion for fuzzy systems is presented. The search for a piecewise quadratic Lyapunov function is formulated as a convex optimization problem.

Abstract. This paper presents a computational approach to stability analysis of nonlinear and hybrid systems. The search for a piecewise quadratic Lyapunov function is formulated as a convex optimization problem in terms of linear matrix inequalities. The relation to frequency domain methods such as the circle and Popov criteria is explained. Several examples are included to demonstrate the flexibility and power of the approach.

Abstract. A new parametrization of piecewise quadratic functions is presented, aimed for convex optimization of Lyapunov functions. The parametrization ensures continuity of the functions, but is also flexible enough to approximate any continuous function with arbitrary accuracy. A converse Lyapunov theorem is given, stating that all exponentially stable systems of a certain class will in principle admit a piecewise quadratic Lyapunov function, to be found by the given optimization procedure

Abstract. This paper presents a computational approach to stability analysis of nonlinear and hybrid systems. The search for a piecewise quadratic Lyapunov function is formulated as a convex optimization problem in terms of linear matrix inequalities. The relation to frequency domain methods such as the circle and Popov criteria is explained. Several examples are included to demonstrate the flexibility and power of the approach

Abstract.

Abstract. The recently developed technique for computation of piecewise quadratic Lyapunov functions is further de- veloped for performance analysis and controller synthe- sis for nonlinear systems. In this way, degree of observ- ability is estimated, L2 induced gain is computed and optimal control problems are solved. The computations are based on convex optimization in terms of linear ma- trix inequalities.

Abstract. Advances in computers and software have made it possible to construct a new generation of teaching tools for automatic control. These tools have a position somewhere between ordinary laboratory processes and conventional computational tools. The idea is to have a multiple-view representation of a system and some of the attributes available on the computer screen. The objects can be manipulated directly and relations between the objects are maintained during the manipulation. We call these tools virtual processes or virtual systems. These tools are well suited to describe abstract notions, but they can also represent problems normally dealt with in the laboratory. This paper outlines the ideas and gives a couple of illustrations.

Abstract. This paper presents an approach for a computer aided control system design (CACSD) software that is based on an extension of the spread-sheet metaphor. The spreadsheet are extended in two ways: the contents of the cells are abstract objects that can be manipulated directly, and the relations between the objects are bidirectional. Prototype implementations have been made in Matlab. The idea is illustrated by several small tools that illuminate various aspects of control system design

Abstract.

Abstract.