Faculté informatique et communications IC, Section des systèmes de communication, Institut de systèmes de communication ISC (Laboratoire pour les communications informatiques et leurs applications 2 LCA2)

A cross-layer design of wireless ad-hoc networks

Radunovic, Bozidar ; Le Boudec, Jean Yves (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2005 ; no 3301.

Ajouter à la liste personnelle
    Summary
    We consider a cross-layer design of wireless ad-hoc networks. Traditional networking approaches optimize separately each of the three layers: physical layer, medium access and routing. This may lead to largely suboptimal network designs. In this work, we propose a jointly optimal design of the three layers, and we show a significant performance improvement over the conventional approach. In the first part of this thesis, our goal is to select appropriate performance metrics for the joint optimization problem. To that respect, we analyze several existing rate-maximization performance metrics for wireless ad-hoc networks: maximizing the sum of rates, max-min fairness and proportional fairness. We first show with several examples that it is not clear if and how max-min fairness can be defined on each one of the examples. We give a formal proof that the max-min fair rate allocation exists on a large class of sets of feasible rates, among which are the feasible-rate sets of all known ad-hoc networking examples. We also give a centralized algorithm to compute the max-min fair allocation whenever it exists. Next, we compare the three metrics for ad-hoc scenarios in terms of efficiency and fairness. We prove that, similar to wired networking,maximizing the sum of rates leads to gross unfairness and starvation of all but the flows with the best channel conditions. We also prove that, contrary to wired networking, max-min fairness yields all flows having the same rate, thus causing large inefficiencies. These findings offer theoretical explanations to the inefficiency and unfairness phenomena previously observed in the contexts of 802.11 and UWB networks. Finally, we show that proportional fairness achieves a good trade-off between efficiency and fairness and is a good candidate for a rate-based performance metric in wireless ad-hoc settings. Having shown that the proportional fairness is an appropriate optimization objective for our problem, in the second part of the thesis we consider a joint optimization of rates, transmission powers, medium access (scheduling) and routing, where the goal of the optimization is to achieve proportional fairness. We first analyze networks built on physical layers that have a rate which is a linear function of SNR at the receiver (such as UWB or low-gain CDMA systems). We find that the optimal solution is characterized by the following principles: (1)Whenever a node transmits, it has to transmit with the maximum power; otherwise it has to remain silent (0 - PMAX power control). (2) Whenever data is being sent over a link, it is optimal to have an exclusion region around the destination, in which all nodes remain silent during transmission, whereas nodes outside of this region can transmit in parallel, regardless of the interference they produce at the destination. (3) When a source transmits, it adapts its transmission rate according to the level of interference at the destination due to sources transmitting in parallel. (4) The optimal size of this exclusion region depends only on the transmission power of the source of the link, and not on the length of the link nor on positions of nodes in its vicinity. As for the routing, we restrict ourselves to a subset of routes where on each successive hop we decrease the distance toward the destination. We also show that (5) relaying along a minimum energy and loss route is better than using longer hops or sending directly, which is not obvious since we optimize rate and not power consumption. Finally (6), the design of the optimal MAC protocol is independent of the choice of the routing protocol. We present a theoretical proof of optimality of 0 - PMAX power control, and the remaining findings we show numerically on a large number of random network topologies. Next, we consider narrow-band networks, where rate function is a strictly concave function of SNR. There, previous findings do not always hold. We show that in some cases, the size of the exclusion region and the optimal routing depend on transmission powers, and that the optimal MAC design depends on the choice of routing. Nevertheless, as we show with the example of 802.11 networks, a significant improvement over the existing 802.11 MAC can be achieved even with simpler, suboptimal strategies. Although this result is shown by simulations on a simplified model, it still gives further directions on how to improve the performance of RTS/CTS based protocols.
    Résumé
    Nous nous intéressons à la conception multi-couche de réseaux sans fils auto-organisés. Avec une approche traditionnelle, la couche physique, celle d'accès au canal et la couche de routage sont traitées et optimisées de façon disctinctes, ce qui tend à entraîner la création d'architectures largement sous optimales. Nous proposons au contraire d'optimiser ces trois couches de manière jointe et nous démontrons que cette approche apporte un gain de performance significatif par rapport à une approche conventionelle. Dans la première partie de ce travail, notre objectif est de sélectionner une mesure de performance appropriée pour le problème d'optimisation sous-jacent. A cette fin, nous analysons plusieurs mesures de performance existantes pour les réseaux sans fils auto-organisés telles que: maximisation de la somme des débits, équité max-min et équité proportionelle. Premièrement, nous démontrons à travers plusieurs examples que la définition d'équité max-min ne va pas de soit pour tous les examples. En effet, il existe des exemples pour lesquels l'équité max-min ne peut être formellement définie. Nous exhibons la classe des ensemble d'allocations de débits atteignables pour laquelle une équité max-min est définie. De plus, nous montrons que cette classe comprend les ensembles de débits atteignables pour tous les cas de réseaux auto-organisés. Nous décrivons également un algorithme centralisé permettant de calculer les allocations de débits satisfaisant une équité max-min lorsqu'elles existent. Deuxièmement, nous comparons efficacité et équité des troismesures de performance sélectionnées dans le cas de réseaux sans-fils auto-organisés. De manière similaire aux réseaux cablés, maximiser la somme des débits entraîne une large perte d'équité ainsi qu'une famine importante pour tous les liens avec un canal de mauvaise qualité. Dans le cas de l'équité max-min, tous les liens obtiennent un débit équivalent provoquant une perte d'efficacité significative. Il est intéressant de noter que ce résultat est largement différent de celui obtenu dans le cas d'un réseau cablé. Cet ensemble de résultats offre des explications théoriques à plusieurs phénomènes observés dans le cas de réseaux sans-fils 802.11 ou à large bande. Pour terminer cette première partie, nous montrons qu'une équité proportionelle permet d'atteindre un juste milieu entre efficacité et équité et que cette dernière est une bonne candidate comme mesure de performance pour des réseaux sans-fils auto-organisés. Dans la seconde partie de ce travail, nous nous attachons à optimiser de façon jointe dans un réseau sans-fils auto-organisé les débits, puissances de transmission, instants d'accès au canal et routage en utilisant comme mesure de performance l'équité proportionelle précedemment sélectionnée. Nous commençons avec des réseaux construits sur des couches physique dont le débit est une fonction linéaire du rapport signal sur bruit au récepteur (par exemple avec une couche physique à large bande ou alors une couche physique "CDMA" à faible gain). La solution optimale obtenue est caractérisée par les principes suivants: (1) Lorsqu'un noeud transmet, c'est avec la puissance maximale (contrôle de puissance 0 - PMAX) (2) Lorsqu'un noeud envoit des données, il est optimal d'avoir une région d'exclusion autour de la destination. Tous les noeuds présent à l'intérieur de cette région d'exclusion doivent rester silencieux lors de la transmission. A l'inverse, les noeuds à l'exterieur de cette région d'exclusion peuvent transmettrent en parallèle quelque soit le niveau d'interférence qu'ils créent. (3) Lorsqu'une source transmet, elle adapte son débit au niveau d'interférence mesuré à la destination. (4) La taille optimale de la région d'exclusion ne dépend ni de la distance entre la source et la destination, ni de la position des noeuds voisins de la destinationmais uniquement de la puissance de transmission. En ce qui concerne le routage, nous nous restreignons à un sous-ensemble de routes ou à chaque relais, la distance à la destination est diminuée. Nous démontrons également que (5) le relayage en utilisant la route qui minimise l'énergie et les pertes est plus efficace que de favoriser des longs relais ou bien encore que de transmettre directement à la destination. Finalement (6), la conception du protocol optimal d'accès au canal est indépendent du choix du protocol de routage. Nous présentons également une preuve de l'optimalité du contrôle de puissance 0 - PMAX et vérifions nos résultats de façon numérique sur une large palette de topologies. Pour terminer, nous traitons le cas des réseaux a bande étroite où le débit est une fonction strictement concave du rapport signal sur bruit. Dans ce cas, les résultat presentés auparavant ne sont pas toujours valides. Nous montrons que dans certains cas, la taille de la région d'exclusion peut dépendre de la position et de la puissance de transmission des sources concurrentes. De même il se peut que l'architecture optimale d'accès au medium tienne compte du protocole de routage utilisé. Néanmoins, à travers un example utilisant un réseau sans-fil 802.11, nous montrons que des améliorations substantielles peuvent être atteintes en utilisant certaines stratégies sous-optimales. Quand bien même ces résultats sont obtenus par simulation avec des modèles simplifiés, ils indiquent les directions à prendre pour améliorer la performance des réseaux de type 802.11.