Physical Layer Cooperation | EPFL Graph Search

Information theory has long pointed to the promise of physical layer cooperation in boosting the spectral efficiency of wireless networks. Yet, the optimum relaying strategy to achieve the network capacity has till date remained elusive. Recently however, a relaying strategy termed Quantize-Map-and-Forward (QMF) was proved to achieve the capacity of arbitrary wireless networks within a bounded additive gap. This thesis contributes to the design, analysis and implementation of QMF relaying by optimizing its performance for small relay networks, proposing low-complexity iteratively decodable codes, and carrying out over-the-air experiments using software-radio testbeds to assess real-world potential and competitiveness. The original QMF scheme has each relay performing the same operation, agnostic to the network topology and the channel state information (CSI); this facilitates the analysis for arbitrary networks, yet comes at a performance penalty for small networks and medium SNR regimes. In this thesis, we demonstrate the benefits one can gain for QMF if we optimize its performance by leveraging topological and channel state information. We show that for the N-relay diamond network, by taking into account topological information, we can exponentially reduce the QMF additive approximation gap from $\Theta(N)$ bits/s/Hz to $\Theta(\log N)$ bits/s/Hz, while for the one-relay and two-relay networks, use of topological information and CSI can help to gain as much as $6$ dB. Moreover, we explore what benefits we can realize if we jointly optimize QMF and half-duplex scheduling, as well as if we employ hybrid schemes that combine QMF and Decode-and-Forward (DF) relay operations. To take QMF from being a purely information-theoretic idea to an implementable strategy, we derive a structure employing Low-Density-Parity-Check (LDPC) ensembles for the relay node operations and message-passing algorithms for decoding. We demonstrate through extensive simulation results over the full-duplex diamond network, that our designs offer a robust performance over fading channels and achieves the full diversity order of our network at moderate SNRs. Next, we explore the potential real-world impact of QMF and present the design and experimental evaluation of a wireless system that exploits relaying in the context of WiFi. We deploy three main competing strategies that have been proposed for relaying, Amplify-and-Forward (AF), DF and QMF, on the WarpLab software radio platform. We present experimental results--to the best of our knowledge, the first ones--that compare QMF, AF and DF in a realistic indoor setting. We find that QMF is a competitive scheme to the other two, offering in some cases up to 12% throughput benefits and up to 60% improvement in frame error-rates over the next best scheme. We then present a more advanced architecture for physical layer cooperation (termed QUILT), that seamlessly adapts to the underlying network configuration to achieve competitive or better performance than the best current approaches. It combines on-demand, opportunistic use of DF or QMF followed by interleaving at the relay, with hybrid decoding at the destination that extracts information from even potentially undecodable received frames. We theoretically quantify how our design choices affect the system performance. We also deploy QUILT on WarpLab and show through over-the-air experiments up to $5$ times FER improvement over the next best cooperative protocol.

Fundamental limits and optimal operation in large wireless networks

Ayfer Özgür Aydin

Wireless adhoc networks consist of users that want to communicate with each other over a shared wireless medium. The users have transmitting and receiving capabilities but there is no additional infrastructure for assisting communication. This is in contrast to existing wireless systems, cellular networks for example, where communication between wireless users heavily relies on an additional infrastructure of base stations connected with a high-capacity wired backbone. The fact that they are infrastructureless makes wireless adhoc networks inexpensive, easy to build and robust but at the same time technically more challenging. The fundamental challenge is how to deal with interference: many simultaneous transmissions have to be accommodated on the same wireless channel when each of these transmissions constitutes interference for the others, degrading the quality of the communication. The traditional approach to wireless adhoc networks is to organize users so that they relay information for each other in a multi-hop fashion. Such multi-hopping strategies face scalability problems at large system size. As shown by Gupta and Kumar in their seminal work in 2000, the maximal communication rate per user under such strategies scales inversely proportional to the square root of the number of users in the network, hence decreases to zero with increasing system size. This limitation is due to interference that precludes having many simultaneous point-to-point transmissions inside the network. In this thesis, we propose a multiscale hierarchical cooperation architecture for distributed MIMO communication in wireless adhoc networks. This novel architecture removes the interference limitation at least as far as scaling is concerned: we show that the per-user communication rate under this strategy does not degrade significantly even if there are more and more users entering into the network. This is in sharp contrast to the performance achieved by the classical multi-hopping schemes. However, the overall picture is much richer than what can be depicted by a single scheme or a single scaling law formula. Nowadays, wireless adhoc networks are considered for a wide range of practical applications and this translates to having a number of system parameters (e.g., area, power, bandwidth) with large operational range. Different applications lie in different parameter ranges and can therefore exhibit different characteristics. A thorough understanding of wireless adhoc networks can only be obtained by exploring the whole parameter space. Existing scaling law formulations are insufficient for this purpose as they concentrate on very small subsets of the system parameters. We propose a new scaling law formulation for wireless adhoc networks that serves as a mathematical tool to characterize their fundamental operating regimes. For the standard wireless channel model where signals are subject to power path-loss attenuation and random phase changes, we identify four qualitatively different operating regimes in wireless adhoc networks with large number of users. In each of these regimes, we characterize the dependence of the capacity on major system parameters. In particular, we clarify the impact of the power and bandwidth limitations on performance. This is done by deriving upper bounds on the information theoretic capacity of wireless adhoc networks in Chapter 3, and constructing communication schemes that achieve these upper bounds in Chapter 4. Our analysis identifies three engineering quantities that together determine the operating regime of a given wireless network: the short-distance signal-to-noise power ratio (SNRs), the long-distance signal-to-noise power ratio (SNRl) and the power path-loss exponent of the environment. The right communication strategy for a given application is dictated by its operating regime. We show that conventional multi-hopping schemes are optimal when the power path-loss exponent of the environment is larger than 3 and SNRs ≪ 0 dB. Such networks are extremely power-limited. On the other hand, the novel architecture proposed in this thesis, based on hierarchical cooperation and distributed MIMO, is the fundamentally right strategy for wireless networks with SNRl ≫ 0 dB. Such networks experience no power limitation. In the intermediate cases, captured by the remaining two operating regimes, neither multi-hopping nor hierarchical-MIMO achieves optimal performance. We construct new schemes for these regimes that achieve capacity. The proposed characterization of wireless adhoc networks in terms of their fundamental operating regimes, is analogous to the familiar understanding of the two operating regimes of the point-to-point additive white Gaussian noise (AWGN) channel. From an engineering point of view, one of the most important contributions of Shannon's celebrated capacity formula is to identify two qualitatively different operating regimes on this channel. Determined by its signal-to-noise power ratio (SNR), an AWGN channel can be either in a bandwidth-limited (SNR ≫ 0 dB) or a power-limited (SNR ≪ 0 dB) regime. Communication system design for this channel has been primarily driven by the operating regime one is in.

EPFL2009

Rate Performance Objectives of Multi-hop Wireless Networks

Jean-Yves Le Boudec

We consider the question of what performance metric to maximize when designing adhoc wireless network protocols such as routing or MAC. We focus on maximizing rates under battery lifetime and power constraints. Commonly used metrics are total capacity (in the case of cellular networks) and transport capacity (in the case of adhoc networks). However, it is known in traditional wired networking that maximizing total capacity conflicts with fairness, and this is why fairness oriented rate allocations, such as max-min fairness, are often used. We review this issue for wireless ad-hoc networks. Indeed, the mathematical model for wireless networks has a specificity that makes some of the findings different. It has been reported in the literature on Ultra Wide Band that gross unfairness occurs when maximizing total capacity or transport capacity, and we confirm by a theoretical analysis that this is a fundamental shortcoming of such metrics in wireless ad-hoc networks, as it is for wired networks. The story is different for max-min fairness. Although it is perfectly viable for a wired network, it is much less so in our setting. We show that, in the limit of long battery lifetime, the max-min allocation of rates always leads to strictly equal rates, regardless of the MAC layer, network topology, choice of routes and power constraints. This is due to the ``solidarity

2004

Function Computation over Networks

Chien-Yi Wang

This thesis looks at efficient information processing for two network applications: content delivery with caching and collecting summary statistics in wireless sensor networks. Both applications are studied under the same paradigm: function computation over networks, where distributed source nodes cooperatively communicate some functions of individual observations to one or multiple destinations. One approach that always works is to convey all observations and then let the destinations compute the desired functions by themselves. However, if the available communication resources are limited, then revealing less unwanted information becomes critical. Centered on this goal, this thesis develops new coding schemes using information-theoretic tools. The first part of this thesis focuses on content delivery with caching. Caching is a technique that facilitates reallocation of communication resources in order to avoid network congestion during peak-traffic times. An information-theoretic model, termed sequential coding for computing, is proposed to analyze the potential gains offered by the caching technique. For the single-user case, the proposed framework succeeds in verifying the optimality of some simple caching strategies and in providing guidance towards optimal caching strategies. For the two-user case, five representative subproblems are considered, which draw connections with classic source coding problems including the Gray-Wyner system, successive refinement, and the Kaspi/Heegard-Berger problem. Afterwards, the problem of distributed computing with successive refinement is considered. It is shown that if full data recovery is required in the second stage of successive refinement, then any information acquired in the first stage will be useful later in the second stage. The second part of this thesis looks at the collection of summary statistics in wireless sensor networks. Summary statistics include arithmetic mean, median, standard deviation, etc, and they belong to the class of symmetric functions. This thesis develops arithmetic computation coding in order to efficiently perform in-network computation for weighted arithmetic sums and symmetric functions. The developed arithmetic computation coding increases the achievable computation rate from

\Theta((\log L)/L)

\Theta(1/\log L)

, where

L

is the number of sensors. Finally, this thesis demonstrates that interaction among sensors is beneficial for computation of type-threshold functions, e.g., the maximum and the indicator function, and that a non-vanishing computation rate is achievable.

EPFL2015