Tutorials

 

Tutorial 1: Performance vs. Algorithmic Complexity in MIMO and Cooperative Communications

SpeakerS: Prof. Petros Elia (EURECOM, France) and Joakim Jaldén (KTH, Sweden)

ABSTRACT

  General MIMO and cooperative techniques bring about substantial gains in rate-reliability performance, although usually at the expense of prohibitive algorithmic complexity (commonly measured in floating point operations, i.e., flops).  In the multi-dimensional delay- and - outage-limited channels - brought to the fore by cognitive radio networks, the aspects of rate, reliability and algorithmic complexity constitute interrelated bottlenecks that need to be jointly analyzed and handled.

 Towards this end, the tutorial will seek to provide a unified exposition of important results from a plethora of authors, put in the context of fundamental limits with respect to performance and complexity.  This unified exposition treats a variety of multi-dimensional cognitive radio-related scenarios, such as cooperative communications, single-user and multi-user MIMO with or without feedback, as well as a broad set of statistics for network channels. 

 In conjunction with an extensive overview of relevant work on transceivers and protocols the tutorial, building on recent results, further explores fundamental questions such as:

What is the price to pay, in algorithmic complexity (flops), for fast and reliable communications?
What is the best tradeoff between rate, reliability, and worse case algorithmic/computational complexity?
What is the tradeoff achieved by existing encoders and decoders?
What are reliable and efficient transceivers for different cooperative protocols?
What are the optimal diversity gains per complexity costs?
What is the optimal goodput per (watt) x (flop)?
What are meaningful MIMO-related measures of algorithmic complexity?
What policies can regulate complexity at a limited loss of performance?
What are meaningful measures of the performance and efficiency capabilities of different transceivers and policies?
What are the fundamental limits to these interrelated capabilities?
Are these optimal limits practically achievable?

OUTLINE

Biography

  Petros Elia received the M.Sc. and Ph.D. in electrical engineering from the University of Southern California (USC), Los Angeles, in 2001 and 2006 respectively. From October 2006 to December of 2007 he was a postdoctoral researcher at the University of California San Diego, and at FTW Vienna. Since February 2008 he has been an Assistant Professor with the Department of Mobile Communications at EURECOM in Sophia Antipolis, France.
His research interests include combining approaches from different sciences, such as mathematics, physics, and from information theory, complexity theory, and game theory, towards analysis and algorithmic design for distributed and decentralized communication networks.
His latest research deals with MIMO transceivers, complexity of communication, isolation and connectivity in dense networks, queueing theory and cross-layer design, coding theory, and information theoretic limits in cooperative communications.
 

 Joakim Jaldén received the M.Sc. and Ph.D. in electrical engineering from the Royal Institute of Technology (KTH), Stockholm, Sweden in 2002 and 2007 respectively. From July 2007 to June 2009 he held a post-doctoral research position at the Vienna University of Technology, Vienna, Austria. He also studied at Stanford University, CA, USA, from September 2000 to May 2002, and worked at ETH, Zürich, Switzerland, as a visiting researcher, from August to September, 2008. In July 2009 he joined the Signal Processing Lab within the School of Electrical Engineering at KTH, Stockholm, Sweden, as an Assistant Professor.

His research interests include the analysis of physical layer communication techniques with focus on wireless communication. For his work on MIMO communications and complexity, Joakim has been awarded the IEEE Signal Processing (SP) Society's 2006 Young Author Best Paper Award and the first price in the Student Paper Contest at the 2007 International Conference on Acoustics, Speech and Signal Processing (ICASSP). He is also a recipient of the Ingvar Carlsson Award issued in 2009 by the Swedish Foundation for Strategic Research.
 

Tutorial 2: Opportunistic Routing in Wireless Networks: A Stochastic/Adaptive Control Approach

Speaker: Prof. Tara Javidi (UC San Diego)

 

ABSTRACT and OUTLINE
 

 Opportunistic routing for multi-hop wireless networks has seen recent research interest to overcome deficiencies of traditional routing. Specifically, the routing decisions are made opportunistically, choosing the next relay based on the actual transmission outcomes in addition to an expected sense of future opportunities. First, we, briefly, cast opportunistic routing as a Markov decision problem (MDP) and introduce as a unifying stochastic framework for almost all versions of opportunistic routing such as SDF, GeRaF, and EXOR.

 

 In the second part of the tutorial, we touch upon the issue of congestion and throughput optimality by contrasting the opportunistic MDP-based schemes with opportunistic versions of back-pressure routing. We propose a modification of the MDP framework to arrive at a throughput-optimal policy, aka ORCD, that exhibits significant delay improvements over the existing candidates in the literature. In the process of proving the throughput optimality of ORCD, we introduce a new Lyapunov function construction which characterizes a large class of throughput optimal policies. The proposed class includes backpressure and ORCD as simple special cases. We also make connections to various delay optimal routing solutions in literature.

 

 To formulate and identify the optimal routing strategy, MDP formulations rely on the availability of probabilistic (Markov) models.  In the third part of the talk, we build on  our earlier work on sensitivity analysis for opportunistic schemes and use a reinforcement learning framework to propose an adaptive opportunistic routing algorithm. The proposed scheme minimizes the expected average cost per packet independently of the initial knowledge about the channel quality and statistics across the network.

 

 In the fourth part of the talk, we briefly discuss practical issues arising in the context of opportunistic routing: cross-layer issues (MAC, network, and transport layers), implementation on off-the-shelf 802.11 radios, ACK explosion, and overhead versus performance trade-off.  Lastly and time permitting, we contrast and compare the above solutions to the network-coding-based solutions in the literature. In particular, we make connections to the critical question of optimal coding rate and block length.

 

Biography

 

 Tara Javidi studied electrical engineering at Sharif University of Technology, Tehran, Iran from 1992 to 1996. She received the MS degrees in electrical engineering (systems), and in applied mathematics (stochastics) from the University of Michigan, Ann Arbor, in 1998 and 1999, respectively. She received her Ph.D. in electrical engineering and computer science from the University of Michigan, Ann Arbor, in 2002.

 

From 2002 to 2004, she was an assistant professor at the Electrical Engineering Department, University of Washington, Seattle. She joined University of California, San Diego, in 2005, where she is currently an assistant professor of electrical and computer engineering.

 

Tara Javidi was a Barbour Scholar during 1999-2000 academic year and received an NSF CAREER Award in 2004. Her research interests are in communication networks, stochastic resource allocation, stochastic control theory, and wireless communications.
 

Tutorial 3: Random Matrices in Wireless Flexible Networks

Speakers: Prof. Merouane Debbah and Romain Couillet (SUPELEC, ST-Ericsson, France)

ABSTRACT

  The generalization of multi-user multi-antenna communication systems, along with the understanding that cooperation among devices is the key for optimal bandwidth usage, has dramatically changed the nature of wireless communication problems. Researchers and engineers need now cope with large dimensional stochastic problems, while simultaneously being required to make devices smarter and able to collaborate with one another. The random parameters in these problems are no longer simple variables but potentially large vectors and matrices. The first purpose of this tutorial is to provide a rigorous introduction to the major tools of both finite and asymptotic aspects of Random Matrix Theory, and their application to the field of Wireless Communications. In a second part, examples of large dimensional problems of Flexible Networks, such as cooperative sensing of multiple information sources and self-organizing multi-user networks will be treated in the light of recent results of Random Matrix Theory. The objectives of this tutorial are therefore for the attendees to acquire a rigorous methodology to treat large dimensional problems and to bridge both Random Matrix Theory and Flexible Networks into a novel heuristic framework. The original features of this tutorial encompass:

  1. A rigorous introduction of the underlying mathematical concepts and techniques of finite-size and asymptotic Random Matrix Theory, whose usefulness for Wireless Communications will be strongly evidenced.

  2. A presentation of the major applications of Random Matrices in the field of Wireless Communications, to analyze the capacity of large dimensional channels, such as multiple-access and broadcast channels with multiple correlated antennas both at the transmitter(s) and the receiver(s).

  3. A ramp-up to the recent results relating Random Matrix Theory to Cognitive Radios, among which cooperative Bayesian signal sensing, Bayesian channel inference, optimal power allocation in self-organizing CDMA/MIMO networks.

OUTLINE

     Part 1: Fundamentals of Random Matrix Theory (historical overview, definition of the main tools, presentation of the analytical and moment-based methods, free probability,. . . )

    Part 2: Large Matrices in Wireless Communications (main results in the field: capacity analysis, eigen-inference, free deconvolution in information plus noise models,. . . )

    Part 3: Random Matrices for Cognitive Radios (applications to cooperative multi-source sensing, finite and in¯nite dimensional statistical inference, power allocation in self-organizing multi-user networks, channel inference based on maximum entropy,. . . )

Biography

  Merouane Debbah was born in Madrid, Spain. He entered the Ecole Normale Superieure de Cachan (France) in 1996 where he received the M.Sc and the Ph.D. degrees respectively in 1999 and 2002. From 1999 to 2002, he worked for Motorola Labs on Wireless Local Area Networks and prospective fourth generation systems (OFDM and MC-CDMA). From 2002 until 2003, he was appointed Senior Researcher at the Vienna Research Center for Telecommunications (ftw., Vienna, Austria) working on MIMO wireless channel modeling issues. From 2003 until 2007, he joined the Mobile Communications department of the Institute Eurecom (Sophia Antipolis, France) as an Assistant Professor. He is presently a Professor at Supelec (Gif-sur-Yvette, France), holder of the Alcatel-Lucent Chair on Flexible radio. His research interests are in information theory, signal processing and wireless communications.

 Merouane Debbah is the recipient of the 2005 Mario Boella Prize Award, the 2007 General Symposium IEEE GLOBECOM best paper award, the Wi-Opt 2009 best paper award as well as the Valuetools 2007, Valuetools 2008 and CrownCom2009 best student paper awards. He is a WWRF fellow

 Romain Couillet was born in Abbeville, France. He received his Msc. in Mobile Communications at the Eurecom Institute, France in 2007. He received his Msc. in Communication Systems in Telecom ParisTech, France in 2007. In September 2007, he joined ST-Ericsson (formerly NXP Semiconductors, founded by Philips). At ST-Ericsson, he works as an Algorithm Development Engineer on the Long Term Evolution Advanced (LTE-A) project. In parallel to his position at ST-Ericsson, he is currently a PhD student at Sup¶elec, France. His research topics include mobile communications, multi-users multi-antenna detection, cognitive radio cognitive, Bayesian probability and random matrix theory.