Cross-Layer Based Analysis of Multi-Hop Wireless Networks

In this work, we revisit classical packet radio networks with a modern treatment of physical-layer (PHY) procedures, medium-access (MAC) and geographic channel-driven routing protocols. Our network model assumes that nodes are randomly distributed on the plane according to a homogeneous spatial Poisson process, using which we provide a novel representation of interference statistics resulting from packet collisions. Using this representation, we develop a cross-layer analysis methodology which allows multi-hop routing protocols to be treated using generic information-theoretic models for the underlying PHY/MAC procedures. These models inherently characterize modern procedures such as channel code rate adaptation, incremental redundancy and packet combining/capture. These models further allow for the assessment of the tradeoff between spatial throughput, measured in bit-meters per signal-space dimension, the range of each transmission and the average transmission delay. A generic formulation based on system parameters, such as system bandwidth, propagation models, etc., is given to analyze this tradeoff in an operational setting which can be used to build system simulators for such networks. Finally, from a purely PHY perspective, the results of this work show that coding and incremental retransmission provide a means for reliable communication coupled with a completely decentralized multiple-access strategy.

Schemes and architectures for wireless ad hoc networks and cooperative communication

Tarik Tabet

The focus of this thesis is on the study of decentralized wireless multi-hop networks. We are particularly interested in establishing bounds on the traffic-carrying capabilities of wireless ad hoc networks and conditions on the scalability of such networks with node mobility. This theoretical investigation brings forward challenges on the design of such networks. This leads to a second part of this thesis that considers the feasibility and the design of physical layer architectures and schemes for decentralized wireless multi-hop networks. In the first part of this thesis, bounds on the capacity of wireless ad hoc networks with two types of non-uniform traffic patterns are established. We focus on the impact of traffic patterns where local communications predominate and show the improvement in terms of per user-capacity over ad hoc networks with unbounded average communication distances. We then study the capacity of hybrid wireless networks, where long-distance relaying is performed by a fixed overlay network of base-stations. We investigate the scaling of capacity versus the number of nodes and the density of base-stations in the area of the network. It is shown that the gain in performance is mainly due to the reduction in the mean number of hops from source to destination. Then, we investigate the impact of mobility on the ad hoc network capacity. We propose a set of necessary and sufficient conditions under which the long-term averaged throughput in an ad hoc network can remain constant as the number of nodes increases. The main idea is to use a connectivity graph that does not represent the actual physical network, but rather the available communication resources. This graph also allows to translate the problem of maximizing the throughput in ad hoc networks to the multi-commodity flow problem and directly apply related results. In contrast to these macroscopic studies, in the second part we focus on a microscopic analysis of ad hoc wireless networks. We are interested in characterizing the performance of decentralized multiple-access and retransmission schemes for multi-hop wireless networks with the goal of drawing conclusions on cross-layer design. We investigate different transmission strategies in order to assess the tradeoff between spatial density of communications and the range of each transmission. We present tools for characterizing the spatial throughput as a function of topological parameters (e.g node population density) and system parameters (propagation, bandwith etc). The results of this work also show that coding and retransmissions provide means of reliable communication coupled with a completely decentralized multiple-access strategy. Finally, an efficient protocol for the delay-limited fading Automatic Retransmission reQuest (ARQ) single relay channel is considered for cooperative communications. The proposed protocol exploits two kinds of diversity: (i) space diversity available through the cooperative (relay) terminal, which retransmits the source's signals, (ii) ARQ diversity obtained by leveraging the retransmission delay to enhance the reliability. The performance characterization is in terms of the achievable diversity, multiplexing gain and delay tradeoff for a high signal-to-noise ratio (SNR) regime. Then, by letting the source's power level vary over the retransmission rounds, we show the benefits of power control on the diversity.

EPFL2007

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

DCC-MAC: A Decentralized MAC Protocol for 802.15.4a-like UWB Mobile Ad-Hoc Networks Based on Dynamic Channel Coding

Jean-Yves Le Boudec, Ruben Merz, Jörg Widmer

We present a joint PHY/MAC architecture (DCC-MAC) for 802.15.4a-like networks based on PPM-UWB. Unlike traditional approaches it fully utilizes the specific nature of UWB to achieve high rates at low protocol complexity. It is the first MAC protocol that adapts the channel code (and thus the bit rate) to interference from concurrent transmissions instead of enforcing exclusion. In order to avoid a complex mutual exclusion protocol at the MAC layer, we propose an interference mitigation scheme. The scheme is based on a modification of the physical layer that cancels much of the interfering energy, in particular from nearby interferers. We further use dynamic channel coding to combat the remaining interference. Sources constantly adjust their channel codes to the level of interference and send incremental redundancy as required. Contention between sources sending to the same destination is solved by a private MAC protocol that involves only the nodes that want to talk to the same destination. The private MAC does not use any common channel; this avoids the issues of hidden and exposed terminals altogether. We show by simulation that our MAC protocol fully satisfies the application requirements of 802.15.4a in terms of link lengths, rates and mobility. We further show that it achieves a significant increase in network throughput, compared to traditional MAC protocols like 802.15.4, that are separated from the physical layer.

2004

Schemes and architectures for wireless ad hoc networks and cooperative communication

Tarik Tabet

EPFL2007