This paper presents a comprehensive approach to federated learning in wireless networks. We discuss communication strategies that address packet loss and bitrate limitations in both uplink and downlink transmissions, and introduce FABLE, a novel optimization algorithm designed to operate effectively under these network constraints. The algorithm also supports non-smooth regularizers and accommodates heterogeneous data distributions across clients. We provide theoretical convergence guarantees under gradient compression and asynchronous operation, and demonstrate the efficiency of our approach through numerical experiments.

We propose a novel asynchronous bundle method to solve distributed learning problems. Compared to existing asynchronous methods, our algorithm computes the next iterate based on a more accurate approximation of the objective function and does not require any prior information about the maximal information delay in the system. This makes the proposed method fast and easy to tune. We prove that the algorithm converges in both deterministic and stochastic (mini-batch) settings, and quantify how the convergence times depend on the level of asynchrony. The practical advantages of our method are illustrated through numerical experiments on classification problems of varying complexities and scales.

Decentralized training of deep neural networks has attracted significant attention for its theoretically superior scalability compared to synchronous data-parallel methods like All-Reduce. However, realizing this potential in multi-node training is challenging due to the complex design space that involves communication topologies, computation patterns, and optimization algorithms. This paper identifies three key factors that can lead to speedups over All-Reduce training and constructs a runtime model to determine when and how decentralization can shorten the per-iteration runtimes. To support the decentralized training of transformer-based models, we introduce a decentralized Adam algorithm that overlaps communications with computations, prove its convergence, and propose an accumulation technique to mitigate the high variance caused by small local batch sizes. We deploy our solution in clusters with up to 64 GPUs, demonstrating its practical advantages in both runtime and generalization performance under a fixed iteration budget. The experiment code is open-source at [https://github.com/WangZesen/Decentralized-Training-Exp](https://github.com/WangZesen/Decentralized-Training-Exp), and the extension code is open-source at [https://github.com/WangZesen/Decent-DP](https://github.com/WangZesen/Decent-DP).

This paper proposes a locally differentially private federated learning algorithm for strongly convex but possibly nonsmooth problems that protects the gradients of each worker against an honest but curious server. The proposed algorithm adds artificial noise to the shared information to ensure privacy and dynamically allocates the time-varying noise variance to minimize an upper bound of the optimization error subject to a predefined privacy budget constraint. This allows for an arbitrarily large but finite number of iterations to achieve both privacy protection and utility up to a neighborhood of the optimal solution, removing the need for tuning the number of iterations. Numerical results show the superiority of the proposed algorithm over state-of-the-art methods.

We propose a novel algorithm for solving the composite Federated Learning (FL) problem. This algorithm manages non-smooth regularization by strategically decoupling the proximal operator and communication, and addresses client drift without any assumptions about data similarity. Moreover, each worker uses local updates to reduce the communication frequency with the server and transmits only a d-dimensional vector per communication round. We prove that our algorithm converges linearly to a neighborhood of the optimal solution and demonstrate the superiority of our algorithm over state-of-the-art methods in numerical experiments.

Many machine learning tasks, such as principal component analysis and low-rank matrix completion, give rise to manifold optimization problems. Although there is a large body of work studying the design and analysis of algorithms for manifold optimization in the centralized setting, there are currently very few works addressing the federated setting. In this paper, we consider nonconvex federated learning over a compact smooth submanifold in the setting of heterogeneous client data. We propose an algorithm that leverages stochastic Riemannian gradients and a manifold projection operator to improve computational efficiency, uses local updates to improve communication efficiency, and avoids client drift. Theoretically, we show that our proposed algorithm converges sub-linearly to a neighborhood of a first-order optimal solution by using a novel analysis that jointly exploits the manifold structure and properties of the loss functions. Numerical experiments demonstrate that our algorithm has significantly smaller computational and communication overhead than existing methods.

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

We propose a delay-agnostic asynchronous coordinate update algorithm (DEGAS) for computing operator fixed points, with applications to asynchronous optimization. DEGAS includes novel asynchronous variants of ADMM and block-coordinate descent as special cases. We prove that DEGAS converges with both bounded and unbounded delays under delay-free parameter conditions. We also validate by theory and experiments that DEGAS adapts well to the actual delays. The effectiveness of DEGAS is demonstrated by numerical experiments on classification problems.

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.

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 Krasnoselskii–Mann iterations, and to quantify the convergence rates for totally asynchronous iterations under various assumptions on communication delays and update rates.

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.

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.

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.

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 communication-efficiency is now needed in a variety of different system architectures, from high-performance clusters to energy-constrained IoT devices. In the current practice, compression levels are typically chosen before training and settings that work well for one task may be vastly suboptimal 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.

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 $\mathcal{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.

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.

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 $\mathcal{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.

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.

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.

Anderson acceleration is a well-established and simple technique for speeding up fixed-point computations with countless applications. This work introduces novel methods for adapting Anderson acceleration to proximal gradient algorithms. Under some technical conditions, we extend existing local convergence results of Anderson acceleration for smooth fixed-point mappings to the proposed non-smooth setting. We also prove analytically that it is in general, impossible 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. Finally, we provide the first applications of Anderson acceleration to non-Euclidean geometry.

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 not been obtained for problems beyond those that are convex or 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 tuning 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.

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.

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% up to 64 workers can be expected.

The veritable scale of modern data necessitates information compression in parallel/distributed big-data optimization. Compression schemes using memory-based error compensation have displayed superior performance in practice, however, to date there are no theoretical explanations for these observed advantages. This paper provides the first theoretical support for why such compression schemes yields higher accuracy solutions in optimization. Our results cover both gradient and incremental gradient algorithms for quadratic optimization. Unlike previous works, our theoretical results explicitly quantify the accuracy gains from error compensation, especially for ill-conditioned problems. Finally, the numerical results on linear least-squares problems validate the benefit of error compensation and demonstrate tightness of our convergence guarantees.

This paper introduces a novel technique for nonlinear acceleration of first-order methods for constrained convex optimization. Previous studies of nonlinear acceleration have only been able to provide convergence guarantees for unconstrained convex optimization. In contrast, our method is able to avoid infeasibility of the accelerated iterates and retains the theoretical performance guarantees of the unconstrained case. We focus on Anderson acceleration of the classical projected gradient descent (PGD) method, but our techniques can easily be extended to more sophisticated algorithms, such as mirror descent. Due to the presence of a constraint set, the relevant fixed-point mapping for PGD is not differentiable. However, we show that the convergence results for Anderson acceleration of smooth fixed-point iterations can be extended to the non-smooth case under certain technical conditions.

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.

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 \emph{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.

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.

Device-to-device (D2D) communication is a promising technology for improving the performance of proximity-based services. This paper demonstrates how the integration of D2D communication in cellular systems operating under dynamic time division duplex (TDD) can improve energy efficiency. We perform joint optimization of mode selection, uplink/downlink transmission period, and power allocation to minimize the transmission energy consumption while satisfying a traffic requirement. Solutions are developed for two scenarios: with and without interference among D2D communications. Both formulations are expressed as mixed-integer nonlinear programming problems, which are NP-hard in general. We exploit problem structure to develop efficient solutions for both scenarios. For the interference-free case, we design algorithms that find the optimal solution in polynomial time. When considering interference, we propose a customized solver based on branch-and-bound that reduces the search complexity by taking advantage of the problem-specific proprieties. We complement this solver by a more practical heuristic algorithm. Simulation results demonstrate that D2D communications in dynamic TDD systems can yield significant energy savings and improved spectral efficiency compared with the traditional cellular communication. Furthermore, we give analytical characterizations of the receiver locations relative to a given transmitter where D2D communication is optimal. These regions can be surprisingly large and not necessarily circular.

This paper investigates the subcarrier allocation problem for uplink transmissions in a multi-cell network, where device-to-device communications are enabled. We focus on maximizing the aggregate transmission rate in the system accounting for both inter- and intra-cell interference. This problem is computationally hard due to its nonconvex and combinatorial nature. However, we show that it can be described by a potential game, and thus a Nash equilibrium can be found using iterative algorithms based on best/better response dynamics. In particular, we propose a simple iterative algorithm with limited signaling that is guaranteed to converge to an equilibrium point, corresponding to a local maximum of the potential function. Using extensive simulations, we show that the algorithm converges quickly also for dense networks, and that the distance to the true optimum is often small, at least for the small-sized networks for which we were able to compute the true optimum.

In this paper, we propose novel relay selection policies that aim at reducing the average delay by incorporating the buffer size of the relay nodes into the relay selection process. More specifically, we propose two delay-aware protocols that are based on the max - link relay selection protocol. First, a delay-aware only approach while it reduces the delays considerably it starves the buffers and increases the outage probability of the system. Towards this end, we propose a delay- and diversity-aware buffer-aided relay selection policy that aims at reducing the average delay considerably and at the same time maintaining good diversity. The protocols are analyzed by means of Markov Chains and expressions for the outage, throughput and delay are derived. The performance and use of our proposed algorithms is demonstrated via extensive simulations and comparisons.

We develop optimal sleeping and harvesting policies for radio frequency (RF) energy harvesting devices, formalizing the following intuition: when the ambient RF energy is low, devices consume more energy being awake than what can be harvested and should enter sleep mode; when the ambient RF energy is high, on the other hand, it is essential to wake up and harvest. Toward this end, we consider a scenario with intermittent energy arrivals described by a two-state Gilbert-Elliott Markov chain model. The challenge is that the state of the Markov chain can only be observed during the harvesting action, and not while in sleep mode. Two scenarios are studied under this model. In the first scenario, we assume that the transition probabilities of the Markov chain are known and formulate the problem as a partially observable Markov decision process (POMDP). We prove that the optimal policy has a threshold structure and derive the optimal decision parameters. In the practical scenario where the ratio between the reward and the penalty is neither too large nor too small, the POMDP framework and the threshold-based optimal policies are very useful for finding non-trivial optimal sleeping times. In the second scenario, we assume that the Markov chain parameters are unknown and formulate the problem as a Bayesian adaptive POMDP and propose a heuristic posterior sampling algorithm to reduce the computational complexity. The performance of our approaches is demonstrated via numerical examples.

Gossip 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 tremendous research effort has been devoted to analyzing and improving the asymptotic rate of convergence for gossip algorithms. In this work we study finite-time convergence of deterministic gossiping. 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 an asymmetric gossip algorithm with finite-time convergence, independent of the number of nodes. For n=2mnodes, we prove that a fastest convergence can be reached in nm=nlog2 n node updates via symmetric gossiping. On the other hand, under asymmetric gossip among n=2m+r nodes with , 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.

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.

In this paper, we present a relay selection scheme which combines the spectral efficiency of successive opportunistic relaying with the robustness of single-link relay selection. More specifically, we propose a scheme that minimizes the total energy expenditure per time slot under an inter-relay interference cancellation scheme. The new relay selection policy is analyzed in terms of outage probability and diversity by modeling the evolution of relay buffers as a Markov Chain. We construct the state transition matrix of the Markov Chain and obtain its stationary distribution, which in turn, yields the outage probability. The proposed scheme outperforms relevant state-of-the-art relay selection schemes in terms of throughput, diversity, energy efficiency and average delay, as demonstrated via representative numerical examples.

We investigate energy-efficient communications for time-division multiple access (TDMA) multiple-input multiple-output (MIMO) cognitive radio (CR) networks operating in underlay mode. In particular, we consider the joint optimization over both the time resource and the transmit precoding matrices to minimize the overall energy consumption of a single cell secondary network with multiple secondary users (SUs), while ensuring their quality of service (QoS). The corresponding mathematical formulations turn out to be non-convex, and thus of high complexity to solve in general. We give a comprehensive treatment of this problem, considering both the cases of perfect channel state information (CSI) and statistical CSI of the channels from the SUs to the primary receiver. We tackle the non-convexity by applying a proper optimization decomposition that allows the overall problem to be efficiently solved. In particular, we show that when the SUs only have statistical CSI, the optimal solution can be found in polynomial time. Moreover, if we consider additional integer constraints on the time variable which is usually a requirement in practical wireless system, the overall problem becomes a mixed-integer non-convex optimization which is more complicated. By exploring the special structure of this particular problem, we show that the optimal integer time solution can be obtained in polynomial time with a simple greedy algorithm. When the SUs have perfect CSI, the decomposition based algorithm is guaranteed to find the optimal solution when the secondary system is under-utilized. Simulation results show that the energy-optimal transmission scheme adapts to the traffic load of the secondary system to create a win-win situation where the SUs are able to decrease the energy consumption and the PUs experience less interference from the secondary system. The effect is particularly pronounced when the secondary system is under-utilized.

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. Copyright © 2013 John Wiley & Sons, Ltd.

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.

In this paper, we study a simple X-relay configuration where the shared relay operates in full-duplex (FD) mode. The relay node may have limited spatial degrees of freedom, and as a result, it may not be able to handle both the loop interference and the multiuser interference. Hence, a decision on the precoding scheme is necessitated. It is often the case that the relay does not have the option of real-time switching between different precoding schemes, either due to hardware limitations of the relay or increased complexity of the problem. Hence, we investigate a “static” precoding decision where the relay node decides on its precoding scheme based only on statistical knowledge of the channel conditions. To perform this decision, the behavior of the system is formulated as a Markov chain and the outage probability of the system is derived in a closed-form with the precoding decision as a parameter. The outage probability is minimized by optimally choosing the precoding scheme, using easily verifiable conditions on the statistical knowledge of the channel conditions. Simulations validate the investigated scheme.

Opportunistic routing is widely known to have substantially better performance than unicast routing in wireless networks with lossy links. However, wireless sensor networks are usually duty cycled, that is, they frequently enter sleep states to ensure long network lifetime. This renders existing opportunistic routing schemes impractical, as they assume that nodes are always awake and can overhear other transmissions. In this article 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 traditional unicast routing. In addition, we evaluate the performance of ORW 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.

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

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.

We investigate the problem of neighbor discovery in multichannel wireless ad hoc and sensor networks with epidemic information dissemination. Previous works have considered neighbor discovery in a single channel where at most one node can be discovered per time instant. To reduce the effect of collisions observed in single channel solutions, we formulate models for multichannel neighbor discovery and 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 evaluations that the expected neighbor discovery time is reduced considerably compared to single channel neighbor discovery solutions.

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.

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

Convergecast, in which data from a set of source devices is delivered to a single data sink, is a critical functionality in 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 convergecast schedules with latency close to that of the optimal schedules.

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.

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 geometric convergence rates. We show that many power control laws from the literature are contractive and derive, sometimes for the first time, convergence rate estimates for these algorithms. Finally, we show that although standard interference functions are not contractive, they are paracontractions with respect to a certain metric space. Extensions to two-sided scalable interference functions are also discussed.

Interference and link dynamics constitute great concerns for stability and performance of protocols in WSNs. In this paper we evaluate the impact of channel hopping and adaptive routing on delay and reliability focusing on delay critical applications.

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 difficult to adapt to link dynamics and introduces delays while waiting for the next hop to wake up.

Opportunistic routing is widely known to have substantially better performance than 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 always awake and can overhear other transmissions. 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 source to destination. We devise distributed algorithms that find the EDC-optimal forwarding, 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 ETX-optimal single path routing in both simulations and testbed-based experiments.

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 the existence and uniqueness of fixed-points along with linear convergence of iterates. We show that many power control laws from the literature are contractive and derive, sometimes for the first time, analytical convergence rate estimates for these algorithms. We also prove that contractive interference functions converge when executed totally asynchronously and, under the assumption that the communication delay is bounded, derive an explicit bound on the convergence time penalty due to increased delay. Finally, we demonstrate that although standard interference functions are, in general, not contractive, they are all para-contractions with respect to a certain metric. Similar results for two-sided scalable interference functions are also derived.

This paper studies the problem of optimal forwarding for reliable and energy-efficient real-time communication over multi-hop wireless 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.

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 amounts of data in which traditional backoff-based contention resolution mechanisms fail or induce high latency and energy costs. We analyze and optimize Strawman, a receiver-initiated contention resolution mechanism that copes with hidden terminals. We propose new techniques to boost the performance of Strawman while keeping the resolution overhead small. We finally validate our improved mechanism via experiments.

Link-state routing protocols are widely used for intradomain routing in the Internet. These protocols are simple to administer and automatically update paths between sources and destinations when the topology changes. However, finding link weights that optimize network performance for a given traffic scenario is computationally hard. The situation is even more complex when the traffic is uncertain or time-varying. We present an efficient heuristic for finding link settings that give uniformly good performance also under large changes in the traffic. The heuristic combines efficient search techniques with a novel objective function. The objective function combines the network performance with a cost of deviating from desirable features of robust link weight settings. We assess performance of our method using traffic data from an operational IP backbone.

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.

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.

Emerging applications in industrial automation and medical care demand support for uninterrupted connectivity and reliable data transfer from mobile sensors. We present MobiSense, an energy-efficient system for reliable data transfer supporting IPv6 micro-mobility and fast handovers. We demonstrate that a two-way end-to-end IPv6 UPD session between two mobile nodes can achieve an end-to-end reliability of up to 96% while guarateeing a hand-over latency below 2 seconds.

The increased industrial interest in wireless sensor networks demands a shift from optimizing protocols for energy-efficient reporting of sporadic events to developing solutions for high-rate real-time data collection and dissemination. We study time-optimal convergecast under the communication constraints of commodity sensor network platforms, and propose a novel convergecast model in which packet copying between the microcontroller and the radio transceiver is separated from packet transmission, thereby improving channel utilization and system throughput. Based on this model, we establish tight lower bound on the number of time slots for convergecast in networks with tree routing topology, and present both centralized and distributed algorithms for generating time-optimal convergecast schedules. Our scheme is also memory-efficient as each node needs to buffer at most one packet at any time. We evaluate our scheme in simulation and on real hardware, and show that our scheme can achieve a throughput of 203 kbit/s (86.4% of the theoretical upper bound) and up to 86.24% improvement compared with traditional TDMA-based convergecast. With optimal routing tree and maximum MAC layer payload, convergecast in a network with 20 sensor nodes can be completed in only 100 ms.

Link estimation provides a long-term estimate of the quality of a link based on its past history. However, this need for a history of past packets is also its main drawback: First, most link estimators only adapt slowly to changing link conditions, being mainly designed to identify long-term stable links. As a result they leave out bursty, potentially long ranging links [2, 4]. Second, in low traffic environments, as seen in many of today's typically heavily duty-cycled application-slink estimates are potentially outdated as they are based on old packets. Finally, it requires to store estimates, i.e., state information, for its neighbors, and (4) relies on beacons to probe links.

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.

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.

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.

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.

This paper presents a novel cross-layer design for joint power and end-to-end rate control optimization in DS-CDMA wireless networks, along with a detailed implementation and evaluation in the network simulator ns-2. Starting with a network utility maximization formulation of the problem, we derive distributed power control, transport rate and queue management schemes that jointly achieve 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, and uses simplified power control mechanisms with reduced signalling requirements. We argue that these features are critical for a successful real-world implementation. To validate these claims, we present a detailed implementation of a cross-layer adapted networking stack for DS-CSMA 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 evaluate the alternatives in extensive simulations.

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 lceilN/2rceil. 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 . For both cases, we present jointly time- and channel-optimal scheduling policies with complexity O(N2). Numerical results demonstrate that our schemes are also efficient in terms of memory utilization.

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.

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.

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.

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.

We 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 single- carrier wireless networks. We pose the problem as a utility maximization problem subject to link-rate constraints, power control and transmission scheduling 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.

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.

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.

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.

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

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-to-end communication rates. Using realistic models of several rate and power adaption schemes, 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, and prove that it converges to the globally optimal solution. 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.

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.

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 Netflow traces, we use a unique data set of complete traffic matrices from a global IP network measured over five-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.

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.

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.

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.