This page is an attempt to organize a few papers into distinct and substantial research areas, and to give an accessible overview of our work in these fields. Naturally, the page is selective both in terms of research areas and the papers listed. For a more complete picture, please see the publications page and the individual home pages of the students, postdocs and collaborators listed under "Group".

Distributed optimization


An asynchronous mini-batch algorithm for regularized stochastic optimization
H. R. Feyzmahdavian, A. Aytekin and M. Johansson
IEEE Transactions on Automatic Control, Vol. 61, No. 12, pp. 3740-3754, December 2016.

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/sqrt(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.
On the convergence rate of asynchronous iterations
H. R. Feyzmahdavian and M. Johansson
IEEE Conference on Decision and Control, Los Angeles, CA, pp. 153-159, December 2014.

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.
Convergence analysis of approximate primal solutions in dual first-order methods
J. Lu and M. Johansson
SIAM Journal on Optimization, Vol. 26, No. 4, pp. 2430-2467, 2016.

Abstract. Dual first-order methods are powerful techniques for large-scale convex optimization. Although an extensive research effort has been devoted to studying their convergence properties, explicit convergence rates for the primal iterates have only been established under global Lipschitz continuity of the dual gradient. This is a rather restrictive assumption that does not hold for several important classes of problems. In this paper, we demonstrate that primal convergence rate guarantees can also be obtained when the dual gradient is only locally Lipschitz. The class of problems that we analyze admits general convex constraints including nonlinear inequality, linear equality, and set constraints. As an approximate primal solution, we take the minimizer of the Lagrangian, computed when evaluating the dual gradient. We derive error bounds for this approximate primal solution in terms of the errors of the dual variables, and establish convergence rates of the dual variables when the dual problem is solved using a projected gradient or fast gradient method. By combining these results, we show that the suboptimality and infeasibility of the approximate primal solution at iteration k are no worse than O(1/sqrt(k)) when the dual problem is solved using a projected gradient method, and O(1/k) when a fast dual gradient method is used.
Optimal parameter selection for the alternating direction method of multipliers (ADMM): quadratic problems
E. Ghadimi, A. Teixeira, I. Shames and M. Johansson
IEEE Transactions on Automatic Control, Vol. 64, No. 2, pp. 290-305, 2016.

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.
A randomized incremental subgradient method for distributed optimization in networked systems
B. Johansson, M. Rabi and M. Johansson
SIAM Journal on Optimization, Vol. 20, No. 3, pp. 1157-1170, 2009.

Abstract. We present an algorithm that generalizes the randomized incremental subgradient method with fixed stepsize due to Nedić and Bertsekas (SIAM J. Optim., 12 (2001), pp. 109–138). 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 only local information. We provide a detailed convergence analysis of the proposed algorithm and compare it with existing, both deterministic and randomized, incremental subgradient methods.
Ergodic mirror descent
J. Duchi, A. Agarwal, M. Johansson and M. I. Jordan
SIAM Journal on Optimization, Vol 22, No. 4, pp 1549-1578, 2012

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.
Multi-step gradient methods for networked optimization
E. Ghadimi, I. Shames and M. Johansson
IEEE Transactions on Signal Processing, Vol. 61, No. 21, pp. 5417-5429, 2013.

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.
Subgradient methods and consensus algorithms for solving convex optimization problems
B. Johansson, T. Keviczky, K. H. Johansson and M. Johansson
Proceedings IEEE Conference on Decision and Control, Cancun, Mexico, December 2008.

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 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 the proposed scheme using results from consensus theory and approximate subgradient methods. The framework is illustrated on an optimal distributed finite-time rendezvous problem.

Complex control systems


Piecewise linear control systems -- a computational approach
M. Johansson
Lecture notes in control and information sciences, Springer Verlag, Heidelberg, Germany, July 2002.

Abstract. This book treats analysis and design of piecewise linear control systems. Piecewise linear systems capture many of the most common nonlinearities in engineering systems, and they can also be used for approximation of other nonlinear systems. Several aspects of linear systems with quadratic constraints are generalized to piecewise linear systems with piecewise quadratic constraints. It is shown how uncertainty models for linear systems can be extended to piecewise linear systems, and how these extensions give insight into the classical trade-offs between fidelity and complexity of a model. Stability of piecewise linear systems is investigated using piecewise quadratic Lyapunov functions. Piecewise quadratic Lyapunov functions are much more powerful than the commonly used quadratic Lyapunov functions. It is shown how piecewise quadratic Lyapunov functions can be computed via convex optimization in terms of linear matrix inequalities. The computations are based on a compact parameterization of continuous piecewise quadratic functions and conditional analysis using the S-procedure. A unifying framework for computation of a variety of Lyapunov functions via convex optimization is established based on this parameterization. Systems with attractive sliding modes and systems with bounded regions of attraction are also treated. Dissipativity analysis and optimal control problems with piecewise quadratic cost functions are solved via convex optimization. The basic results are extended to fuzzy systems, hybrid systems and smooth nonlinear systems. It is shown how Lyapunov functions with a discontinuous dependence on the discrete state can be computed via convex optimization. An automated procedure for increasing the flexibility of the Lyapunov function candidate based on linear programming duality is suggested.
Computation of piecewise quadratic Lyapunov functions for hybrid systems
M. Johansson and A. Rantzer
IEEE Transactions on Automatic Control, Vol. 43, pp. 555-559, April 1998.

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.
Piecewise quadratic stability of fuzzy systems
M. Johansson, A. Rantzer and K.-E. Arzen
IEEE Transactions on Fuzzy Systems, Vol. 7, pp. 713-722, December 1999.

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.
Piecewise quadratic estimates of domains of attraction for linear systems with saturation
M. Johansson
IFAC World Congress, Barcelona, Spain, July 2002.

Abstract. We show how piecewise quadratic Lyapunov functions can be used to compute estimates of regions of attraction for linear systems with saturation. The central issues of local analysis and optimization of the "size" of the domain of attraction are addressed, and the approach is demonstrated on several examples. We observe that the piecewise quadratic Lyapunov functions yield significant improvements over recently proposed methods based on the Circle and Popov criteria.
Modular design of jointly optimal controllers and forwarding policies for wireless control
B. Demirel, Z. Zou, P. Soldati and M. Johansson
IEEE Transactions on Automatic Control, Vol. 59, No. 12, pp. 3252 - 3265, August 2014.

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 deadline-constrained 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.
PID controller tuning rules for varying time-delay systems
L. M. Eriksson and M. Johansson
Proceedings of the American Control Conference, July 2007.

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.
Joint optimization of communication rates and linear systems
L. Xiao, M. Johansson, H. Hindi, S. Boyd and A. Goldsmith
IEEE Transactions on Automatic Control, January 2003.

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.
Exponential stability of homogeneous positive systems of degree one with time-varying delays
H.R. Feyzmahdavian, T. Charalambous and M. Johansson
IEEE Transactions on Automatic Control, Vol. 59, No. 6, pp. 1594-1599, June 2014.

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.
Asymptotic stability and decay rates of homogeneous positive systems with bounded and unbounded delays
H. Feyzmahdavian, T. Charalambous and M. Johansson
SIAM Journal on Control and Optimization, Vol. 52, No. 4, pp. 2623-2650, 2014.

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.

Real-time and sensor networking


Low power, low delay: opportunistic routing meets duty cycling
O. Landsiedel, E. Ghadimi, S. Duquennoy and M. Johansson
ACM IPSN, Beijing, China, April 2012.

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 difficult 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 duty-cycled setting, packets are addressed to sets of potential receivers and forwarded by the neighbor that wakes up first 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.
Opportunistic routing in low duty-cycled wireless sensor networks
E. Ghadimi, O. Landsiedel, P. Soldati, S. Duquennoy and M. Johansson
ACM Transactions on Sensor Networks, Vol. 10, No. 4, June 2013.

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 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.
Optimal link scheduling and channel assignment for convergecast in Wireless HART Networks
H. Zhang, P. Soldati and M. Johansson
Proceedings WiOpt, June 2009.

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 ⌈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 . 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.
Deadline-constrained transmission scheduling and data evacuation in WirelessHART networks
P. Soldati, H. Zhang and M. Johansson
European Control Conference, June 2009.

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 in 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 always achieves the lower bound on evacuation time. We evaluate our scheduling algorithm through numerical simulations, and the results verify that our algorithm minimizes the evacuation time with the least number of channels.
Energy-efficient deadline-constrained maximum reliability forwarding in lossy networks
Z. Zou, P. Soldati, H. Zhang and M. Johansson
IEEE Transactions on Wireless Communications, Vol. 11, No. 10, pp. 3474-3483, October 2012.

Abstract. 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.
MobiSense: power-efficient micro-mobility in wireless sensor networks
A. Gonga, O. Landsiedel and M. Johansson
Distributed computing in sensor systems and workshops (DCOSS), p 1-8, Barcelona, Spain, June 2011.

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.

Large-scale coordination


On decentralized negotiation of optimal consensus
B. Johansson, A. Speranzon, M. Johansson and K. H. Johansson
Automatica, Vol. 44, No. 4, pp. 1175-1179, April 2008.

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.
Distributed coordination of household electricity consumption
M. Juelsgaard, A. Teixeira, M. Johansson, R. Wisniewski and J. D. Bendtsen
IEEE Multi-conference on Systems and Control, Antibes, France, October 2014.

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.
The evolution of beliefs over signed social networks
G. Shi, A. Proutiere, M. Johansson and K.-H. Johansson
Operations Research, February 2016.

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 links) or enemies (negative links). Pairs of nodes are randomly selected to interact over time, and when two nodes interact, each of them updates its opinion based on the opinion of the other node and the sign of the corresponding link. This model 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 the 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 to the belief boundaries, and highlight the crucial influence of (strong or weak) structural balance of the underlying network on this clustering phenomenon.
How agreement and disagreement evolve over random dynamic networks
G. Shi, M. Johansson and K.H. Johansson
IEEE Journal on Selected Areas in Communications, Vol. 31, No. 6, 2013.

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.
Finite-time convergent gossiping
G. Shi, B. Li, M. Johansson and K.H. Johansson
IEEE/ACM Transactions on Networking, Vol. 2, No. 4, pp. 370-381, 2015.

Abstract. 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=2m nodes, we prove that a fastest convergence can be reached in nm=nlog2n node updates via symmetric gossiping. On the other hand, under asymmetric gossip among n=2m+r nodes with 0<=r<2m, 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.

Communications and networking


Simultaneous routing and resource allocation via dual decomposition
L. Xiao, M. Johansson and S. Boyd
IEEE Transactions on Communications, Vol. 52, No. 7, pp. 1136-1144, 2004.

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.
Cross-layer optimization of wireless networks using nonlinear column generation
M. Johansson and L. Xiao
IEEE Transactions on Wireless Communications, Vol. 5, pp. 435-445, February 2006.

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-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.
Mathematical decomposition techniques for distributed cross-layer optimization of data networks
B. Johansson, P. Soldati and M. Johansson
IEEE Journal on Selected Areas in Communications, Vol. 24, No. 8, pp. 1535-1547, August 2006.

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.
Proportionally fair allocation of end-to-end bandwidth in STDMA wireless networks
P. Soldati, B. Johansson and M. Johansson
Proceedings of the the Seventh ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc'06, pp. 286-297, May 2006.

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.
Contractive interference functions and rates of convergence of distributed power control laws
H.R. Feyzmahdavian, M. Johansson and T. Charalambous
IEEE Transactions on Wireless Communications, Vol. 11, No. 12, pp. 4494-4502, December 2012.

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 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.
Traffic matrix estimation on a large IP backbone - a comparison on real data
A. Gunnar, M. Johansson and T. Telkamp
ACM Internet Measurement Conference (IMC), Taormina, Italy, pp. 149 - 160, October 2004.

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 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.
Data-driven traffic engineering: techniques, experiences and challenges
M. Johansson and A. Gunnar
Broadband Communications, Networks and Systems (BROADNETS), pp. 1-10, October 2006.

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.
Energy-efficient D2D communications in dynamic TDD systems
D. Della Penda, L. Fu and M. Johansson
IEEE Transactions on Communications, Vol. PP, No. 99, pp. 1-1, October 2016.

Abstract. Network-assisted device-to-device communication is a promising technology for improving the performance of proximity-based services. This paper demonstrates how the integration of device-to-device communications and dynamic time-division duplex can improve the energy efficiency of future cellular networks, leading to a greener system operation and a prolonged battery lifetime of mobile devices. We jointly optimize the mode selection, transmission period and power allocation to minimize the energy consumption (from both a system and a device perspective) while satisfying a certain rate requirement. The radio resource management problems are formulated as mixed-integer nonlinear programming problems. Although they are known to be NP-hard in general, we exploit the problem structure to design efficient algorithms that optimally solve several problem cases. For the remaining cases, a heuristic algorithm that computes near-optimal solutions while respecting practical constraints on execution times and signaling overhead is also proposed. Simulation results confirm that the combination of device-to-device and flexible time-division-duplex technologies can significantly enhance spectrum and energy-efficiency of next generation cellular systems.
Optimal radio frequency energy harvesting with limited energy arrival knowledge
Z. Zou, A. Gidmark, T. Charalambous and M. Johansson
IEEE Journal on Selected Areas in Communications, Vol. 34, No. 12, pp. 3528-3539, December 2016.

Abstract. In this paper, we develop optimal policies for deciding when a wireless node with radio frequency (RF) energy harvesting (EH) capabilities should try and harvest ambient RF energy. While the idea of RF-EH is appealing, it is not always beneficial to attempt to harvest energy; in environments where the ambient energy is low, nodes could consume more energy being awake with their harvesting circuits turned on than what they can extract from the ambient radio signals; it is then better to enter a sleep mode until the ambient RF energy increases. Towards this end, we consider a scenario with intermittent energy arrivals and a wireless node that wakes up for a period of time (herein called the time-slot) and harvests energy. If enough energy is harvested during the time-slot, then the harvesting is successful and excess energy is stored; however, if there does not exist enough energy the harvesting is unsuccessful and energy is lost. We assume that the ambient energy level is constant during the time-slot, and changes at slot boundaries. The energy level dynamics are described by a two-state Gilbert-Elliott Markov chain model, where the state of the Markov chain can only be observed during the harvesting action, and not when in sleep mode. Two scenarios are studied under this model. In the first scenario, we assume that we have knowledge of the transition probabilities of the Markov chain and formulate the problem as a Partially Observable Markov Decision Process (POMDP), where we find a threshold-based optimal policy. In the second scenario, we assume that we don't have any knowledge about these parameters and formulate the problem as a Bayesian adaptive POMDP; to reduce the complexity of the computations we also propose a heuristic posterior sampling algorithm. The performance of our approaches is demonstrated via numerical examples.

Decision support systems


Scheduling double round-robin tournaments with divisional play using constraint programming
M. Carlsson, M. Johansson and J. Larson
European Journal of Operational Research, Vol. 259, No. 3, pp. 1180 - 1190, 2017.

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.
Cross-platform classification in microarray-based leukemia diagnostics
B. Nilsson, A. Andersson, M. Johansson and T. Fioretos
Haematologica, No. 6, June 2006.

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.
Ultrasome: Efficient aberration caller for copy-number studies of ultra-high resolution
B. Nilsson, M. Johansson, F. Al-Shahrour, A. E. Carpenter and B. L. Ebert
Bioinformatics, Vol. 25, No. 8, pp. 1078-1079, February 2009.

Abstract. 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.
Interactive tools for education in automatic control
M. Johansson, M. Gafvert and K.J. Astrom
IEEE Control Systems, Vol. 18, No. 3, pp. 33-40, June 1998.

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.