Petite broderie autour des jeux du sans-fil - Focus sur le contrôle de puissance distribué

06/03/2017
Auteurs : Samson Lasaulce
Publication REE REE 2017-1
OAI : oai:www.see.asso.fr:1301:2017-1:18860

Résumé

Petite broderie autour des jeux du sans-fil - Focus sur le contrôle  de puissance distribué

Métriques

207
4
485.35 Ko
 application/pdf
bitcache://380eb5b3acba37203e58915c2c4fe7e21d6d7436

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/1301:2017-1/18860</identifier><creators><creator><creatorName>Samson Lasaulce</creatorName></creator></creators><titles>
            <title>Petite broderie autour des jeux du sans-fil - Focus sur le contrôle  de puissance distribué</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Mon 6 Mar 2017</date>
	    <date dateType="Updated">Mon 6 Mar 2017</date>
            <date dateType="Submitted">Tue 22 May 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">380eb5b3acba37203e58915c2c4fe7e21d6d7436</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>31920</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

17 REE N°1/2017 LES GRANDS PRIX 2016 DE LA SEE La Médaille Blondel récompense des travaux de recherche et dévelop- pement contribuant aux progrès de la science et des industries électriques et électroniques, menés avec le même souci d’approfondisse- ment et de rigueur que ceux d’André Blondel, pionnier du transport de l’énergie électrique à grande dis- tance et à très haute tension, initiateur de la construction de l’usine hydroélectrique de Génissiat sur le Rhône et créateur des premiers radiophares en 1911. Samson Lasaulce Médaille Blondel Directeur de Recherche CNRS – L2S – CentraleSupélec Petite broderie autour Focus sur le contrôle de puissance distribué Le but de cet article est double. Il vise à la fois à présenter de manière didactique le problème de contrôle de puissance distribué dans les réseaux sans fil et à décrire deux contributions scientifiques de l’auteur et de ses col- lègues qui concernent ce problème. Le problème de contrôle de puissance peut se modéliser comme un jeu au sens mathématique dans lequel les joueurs sont les émetteurs et les actions des joueurs sont données par les niveaux de puissance d’émission. L’esprit de cet article suit ainsi l’approche retenue pour la présentation donnée lors de la cérémonie de remise des prix de la SEE en 2016. Le contrôle de puissance distribué. C’est quoi ? Pourquoi est-ce important ? Pourquoi ne voit-on pas les étoiles lorsqu’il fait jour et que le ciel est par- faitement dégagé ? La raison est qu’il y a une étoile dominante qui empêche de voir toutes les autres, c’est le soleil. Dans un réseau sans fil, si plusieurs émetteurs radio opèrent sur la même bande de fréquence, le même type d’effet peut se produire à savoir qu’un émetteur qui se trouve trop près d’un récepteur empêche ce dernier de « voir » les autres émetteurs. Pour remé- dier à ce problème d’éblouissement, on utilise le contrôle de puissance. Un émetteur doit adapter son niveau de puissance à la qualité du lien de com- munication qui le relie à son récepteur d’intérêt. Typiquement, si l’émetteur est près du récepteur, le premier n’a pas besoin d’émettre à pleine puissance. Dans les réseaux de type 3G et dans ses versions avancées, le contrôle de puissance est réalisé de manière centralisée. C’est la station de base qui va spécifier aux terminaux mobiles qui y sont connectés le niveau de puissance avec lequel chaque mobile doit émettre. A contrario, dans un réseau Wi-Fi, un point d’accès (une « box » typiquement) doit sélectionner de manière autonome la bande de fréquence sur laquelle il émet ; il n’y a pas de station de base ou de terminal qui va spécifier au point d’accès quelle bande il doit utiliser. On dit que la décision est distribuée ou décentralisée. Le problème de sélection de bande en Wi-Fi est en fait un problème de contrôle de puis- sance distribué. Le caractère distribué du contrôle de puissance permet de rendre le déploiement d’un réseau aisé du fait de la non-nécessité de ter- minaux centraux de coordination, mais il peut entraîner en contrepartie une perte significative d’efficacité d’utilisation des ressources radio. Ce problème de perte d’efficacité n’est pas encore crucial dans les réseaux Wi-Fi actuels, mais avec l’augmentation du nombre d’objets communicants opérant dans les bandes Wi-Fi, l’augmentation des débits induite par le déploiement de la fibre optique et par les usages de plus en plus « débivores », le problème d’efficacité prendra certainement davantage d’importance. 18 REE N°1/2017 LES GRANDS PRIX 2016 DE LA SEE Les objectifs ambitieux affichés pour les réseaux 5G (mul- tiplier les débits par 1 000 tout en réduisant la consomma- tion énergétique d’un facteur 100 à 1 000) se fonderont sur des changements majeurs dans les réseaux sans fil. Un des changements attendus est le déploiement de petites cellules (“small cells”), c’est-à-dire d’un très grand nombre de petites stations de bases 5G (de la taille d’une « box »). Ces petites stations seront beaucoup plus rapprochées que ne le sont les stations de bases actuelles et il sera essentiel d’implanter des mécanismes de contrôle de puissance pour gérer l’inter- férence entre toutes les communications. La situation sera comparable à celle d’un restaurant d’entreprise ou une can- tine où tout le monde parle très fort pour se faire entendre. Pour des raisons de complexité au niveau des petites stations de base et parce qu’il ne sera pas possible de contrôler une multitude de stations de manière centralisée, le contrôle de puissance devra là-aussi être distribué. Enfin, pour conclure sur l’importance du problème du contrôle de puissance, il faut rappeler que le manque de savoir-faire dans la mise en œuvre du contrôle de puissance a été un des éléments tech- nologiques qui a retardé le déploiement des réseaux 3G. Le problème d’efficacité du contrôle de puissance distribué. Pour obtenir de l’efficacité, une approche en rupture avec l’existant Distribué mais pas efficace, pourquoi ? Explication sur un exemple Tout d’abord essayons de comprendre sur un exemple simple le lien entre la distribution des décisions de contrôle de puissance et la perte d’efficacité. Considérons deux émet- teurs qui ont chacun le choix d’émettre avec une puissance faible ou forte. Selon le choix des émetteurs, ceux-ci bénéfi- cient alors d’un certain débit de communication indiqué dans le tableau 1. L’émetteur 1 (resp. 2) choisit la ligne (resp. la colonne) du tableau. Il en résulte un couple de débits de communication (par exemple en Mbit/s), la première (resp. la deuxième) composante correspondant au débit de l’émet- teur 1 (resp. 2). Si les émetteurs implantent un algorithme distribué, le point de fonctionnement qui risque d’être ob- tenu est le point (10,10) qui est moins intéressant que le point (30,30) pour les deux émetteurs ; on dit que le point (10 ,10) n’est pas Pareto-efficace (c’est-à-dire qu’il existe un autre point tel que tout le monde fasse mieux). A partir d’un raisonnement particulier, expliquons pourquoi le point (10, 10) est un point typiquement attracteur. Supposons que les deux émetteurs opèrent à puissance faible. Si un émetteur, par exemple l’émetteur 1 met à jour sa décision, il verra son débit monter à 40 Mbit/s en passant à puissance forte, et ce tant que l’autre émetteur maintient sa décision de départ. Mais l’émetteur 2 verra alors son débit chuter à 1 Mbit/s. L’émetteur 1 étant à puissance forte, l’émetteur 2 refera monter son débit en émettant à puissance forte également. Et il est facile à vérifier que toute mise à jour individuelle (distribuée donc) ne fera plus quitter les émetteurs du point (10,10). Un défi technique récurrent dans les réseaux sans fil est de concevoir un algorithme de contrôle de puissance qui soit distribué (au sens de la décision mais aussi au sens de l’infor- mation) et soit efficace par exemple au sens de Pareto ou au sens du débit-somme (ici on aurait 60 Mbits/s au mieux). Une approche complètement nouvelle a été proposée dans [1][2] au travers de l’idée innovante de contrôle de puis- sance codé. C’est l’une des contributions scientifiques-clé qui sera présentée dans cet article. Contrôle de puissance codé Expliquons le problème et la solution proposée pour le cas particulier de deux émetteurs et deux récepteurs (figure 1). Chaque émetteur veut communiquer avec son récepteur respectif (flèches en trait plein) et chaque récepteur reçoit le signal qui lui est utile mais aussi les émissions de l’autre émet- teur (flèches en pointillés). Pour analogie, imaginez vous dans un carré TGV en train de parler à la personne en face de vous alors que la conversation des deux personnes d’à côté est sans intérêt pour votre locuteur. Cette conversion représente de l’in- terférence pour la personne qui vous écoute. Pour gérer l’inter- férence de manière la plus efficace possible, il faudrait qu’il y ait un lien de communication entre les émetteurs pour que ceux-ci se coordonnent. Or, dans un réseau sans fil distribué ce lien est typiquement inexistant. Par exemple, il n’existe aucun lien de communication explicite entre les points d’accès Wi-Fi tels que les « boxes » que nous avons à la maison. Il en sera très vraisemblablement de même pour les petites stations de bases des réseaux à petites cellules des réseaux 5G. Sans coordination, nous avons vu au travers de l’exemple du tableau 1, que les émetteurs risquent de mal exploiter les ressources radio, par exemple en émettant à pleine puissance, sur toute Puissance forte Puissance faible Puissance forte (10,10) (40,01) Puissance faible (01,40) (30,30) Tableau 1: Illustration du problème d’efficacité dans les réseaux distribués. Le point (10,10) est un point attracteur pour de nombreux algorithmes distribués et ce point n’est pas Pareto-efficace. L’unité des débits peut par exemple être le Mbit/s. REE N°1/2017 19 Petite broderie autour des jeux du sans fil la bande de fréquence disponible et peut-être même tout le temps. Comment induire de la coordination sans possibilité de communication ? L’idée innovante sur laquelle repose le contrôle de puis- sance codé [1][2] est de gérer l’interférence en utilisant celle- ci comme un canal de communication entre les émetteurs et en codant la puissance pour qu’elle transporte de l’infor- mation. En effet, lorsqu’un émetteur modifie sa puissance d’émission, cela produit un effet sur l’interférence perçue par le récepteur gêné. Or, beaucoup de systèmes sans fils possèdent une voie de retour qui donne à l’émetteur une image de l’interférence subie par son récepteur ; par exemple un retour de type ACK/NACK (acknowledgement/non-ac- knowledgment) indiquant à l’émetteur si le récepteur a bien reçu un paquet de données est une image binaire du rap- port signal-à-interférence plus bruit. Pour revenir à l’exemple du carré TGV, c’est comme si vous ne changiez pas votre discours pour votre locuteur mais moduliez la puissance de votre voix pour communiquer avec votre voisin qui gêne votre locuteur. Ici, l’explication est triviale mais pour le contrôle de puissance, il faut revisiter le problème de la modulation et du codage pour obtenir des stratégies de contrôle de puis- sance qui permettent d’obtenir un système de communica- tion distribué et efficace. Il faut revoir en particulier le codage parce que le critère de performance de la communication (implicite) n’est pas un taux d’erreur binaire ou un rendement informatif comme c’est le cas classiquement. Le critère de performance est un critère de performance arbitraire donné par le problème d’allocation de ressources radio considéré (le débit-somme du réseau, l’énergie consommée par le réseau, la latence du réseau, etc.). La figure 2 permet de quantifier l’apport du contrôle de puissance codé par rapport à l’état de l’art. Elle représente le débit-somme du système de la figure 1 en fonction du rapport signal-à-bruit. La courbe du bas correspond à l’état de l’art et est obtenue avec l’algorithme « iterative water-filling » [3]. La courbe du haut est une borne supérieure qui serait obtenue s’il y avait un lien de communication parfait entre les deux émetteurs. Les trois courbes intermédiaires correspondent aux Figure 1 : Scénario de communication illustrant le problème d’interférence. L’idée innovante sur laquelle repose le contrôle de puissance codé est de gérer l’interférence en utilisant celle-ci comme un canal de communication entre les émetteurs et en codant la puissance pour qu’elle transporte de l’information. Figure 2 : Débit-somme (en bit/s par Hz) en fonction du rapport signal-à-bruit. Comparaison entre le contrôle de puissance distribué classique (courbe du bas) et le contrôle de puissance codé. Le scénario est celui de la figure 1 [2]. 20 REE N°1/2017 LES GRANDS PRIX 2016 DE LA SEE performances du contrôle de puissance codé (avec un code de taille 1, un code de taille 3 et le meilleur code de grande taille). Ces courbes intermédiaires sont obtenues en faisant une analyse non-triviale des performances limites fondée sur la théorie de Shannon [1] [2] ; l’établissement d’un lien entre le contrôle de puissance et la théorie de Shannon a été un résultat surprenant et mis en évidence pour la première fois dans [1]. L’effet de saturation lié au fait que les émetteurs dis- tribués peuvent émettre à pleine puissance est évité. Mais sur- tout, les émetteurs échangent de l’information via leurs actions (à savoir les niveaux de puissance d’émission). L’information échangée concerne principalement la qualité des liens de communication. Plus d’information sur cette technique peut être trouvée dans [1][2][4][5]. « Moins j’ai le choix, mieux je me porte » Dans la section précédente, le problème était de conce- voir des stratégies de contrôle de puissance les plus efficaces possible, l’espace d’action des émetteurs étant donné. Dans cette section nous allons discuter l’influence de l’espace d’ac- tion sur l’efficacité globale et relater un résultat contre-intuitif et important pour l’ingénieur du sans fil ; ce résultat a été démontré dans différents scénarios [6][7]. Pour augmenter le débit des communications Wi-Fi entre le point d’accès et le terminal (disons un ordinateur), la so- ciété américaine Codeon [8] propose une solution logicielle dont l’idée-clé est d’élargir la bande exploitée. En effet, actuel- lement, les systèmes Wi-Fi tels que les « boxes » n’utilisent qu’une seule bande de fréquence ou canal. La société Codeon a donc proposé d’exploiter plusieurs canaux pour augmenter le débit. Ceci est rendu possible en plaçant plusieurs « dongles » sur les ports USB de l’ordinateur et sur le point d’accès. La so- ciété propose un logiciel qui permet de gérer cette communi- cation multiports et d’offrir un débit multiplié par le nombre de ports utilisés. Mais en pratique, le débit peut être en effet aug- menté mais aussi diminué par rapport à la solution à un seul canal ! Ce résultat surprenant a été démontré dans [6][7]. Le résultat est surprenant au sens de l’optimisation puisque plus l’espace d’optimisation est grand et meilleures sont les perfor- mances. Le problème est qu’ici nous avons affaire à un réseau distribué dans lequel les décisions ne sont pas centralisées et choisies par une seule entité ou un seul optimiseur et le caractère distribué fait que relation ressources-performances n’est plus monotone (croissante classiquement). Pour com- prendre l’intuition de la démonstration de [6], considérons l’exemple du tableau 1. Supposons que les émetteurs n’aient qu’un seul choix : émettre à puissance faible. Alors, les deux émetteurs peuvent opérer à 30 Mbit/s chacun. Or, si on laisse aussi le choix à l’émetteur d’émettre à puissance forte, nous avons expliqué que typiquement le point de fonctionnement sera tel que les deux émetteurs émettront à puissance forte et donc obtiendront chacun un débit de 10 Mbit/s. Ainsi, nous voyons que si l’espace d’optimisation grandit dans un réseau distribué, la solution résultant peut s’avérer moins bonne pour tous les émetteurs. C’est ce type de phénomène qui se pro- duit pour l’exemple du Wi-Fi. Il s’agit d’une instanciation d’un phénomène qu’on appelle le paradoxe de Braess et qui avait été observé dans d’autres domaines. Le phénomène avait été Figure 3: Mise en évidence d’un paradoxe de Braess dans les réseaux sans fil. En ayant accès à plus de bande, chaque émetteur peut voir ses performances se dégrader dans un réseau distribué [7]. REE N°1/2017 21 Petite broderie autour des jeux du sans fil observé dans le transport routier (à Stuttgart) dans la fin des années 60 : le fait d’avoir construit une route avait dégradé le trafic dans la zone concernée. L’enseignement est donc impor- tant pour l’ingénieur du sans fil : dès lors que les décisions sont distribuées, donner plus de ressources à un terminal (par exemple plus de bande, de puissance, de durée de transmis- sion ou d’antennes) peut dégrader ses performances. La figure 3 montre le débit-somme en fonction du rapport signal-à-bruit pour un réseau sans fil distribué avec interférence. La figure donne le rapport des performances du cas multi-bande sur les performances du cas à une seule bande. Lorsque ce rap- port est inférieur à un, les performances du cas multi-bande sont moins bonnes et donc avoir plus de bande conduit à une dégradation des performances. Conclusion Dans cet article nous avons vu un problème concret d’ap- plication de la théorie des jeux aux réseaux sans fil distribués. Le jeu de contrôle de puissance est un jeu car les perfor- mances d’un émetteur dépendent de ses décisions mais aussi des décisions des autres émetteurs. Dans un jeu de contrôle de puissance, les joueurs sont les émetteurs et les actions des joueurs sont les puissances (ou vecteurs de puis- sance) d’émission. Les raisonnements de la théorie des jeux permettent de concevoir des stratégies innovantes dans les réseaux sans fil et d’éviter des pièges dans lesquelles l’ingé- nieur peut facilement tomber en suivant les raisonnements classiques de l’optimisation. Pour illustrer la première partie de cette assertion, nous avons vu comment exploiter l’idée fondamentale qu’un joueur communique de l’information en agissant. Cette idée bien qu’assez commune en théorie des jeux n’avait jamais été exploitée pour les problèmes d’alloca- tion de ressources et celle-ci conduit à la notion de commu- nication implicite dont la mise en œuvre demande à revisiter le problème du codage, ouvrant ainsi de nombreuses pers- pectives en termes d’innovations. Pour illustrer la seconde partie de l’assertion, nous avons mis en évidence l’existence d’un paradoxe de Braess dans les réseaux sans fil distribués : donner plus de ressources à un émetteur peut le conduire à avoir des performances individuelles moins bonnes. Ce genre de paradoxes sera à éviter dans les réseaux émer- gents tels que les réseaux 5G qui auront un caractère distri- bué assez marqué. Références [1] B. Larrousse and S. Lasaulce, “Coded Power Control: Performance Analysis”, IEEE Intl. Symposium on Information Theory (ISIT), Istanbul, Turkey, July 2013. L’AUTEUR Samson Lasaulce est actuellement directeur de recherche au CNRS, au Laboratoire des signaux et systèmes (Gif-sur-Yvette). Avant de rejoindre le CNRS, il a été ingénieur R&D, d’abord à Motorola Labs puis à Orange Labs. Ses travaux de recherche actuels portent sur les réseaux distribués de communication et d’énergie pour lesquels il utilise des outils tels que la théorie des jeux, la théorie de l’information et de l’apprentissage. 22 REE N°1/2017 LES GRANDS PRIX 2016 DE LA SEE [2] B. Larrousse, S. Lasaulce, and M. Bloch, “Coordination in distributed networks via coded actions with application to power control”, IEEE Transactions on Information Theory, to appear. [3] W. Yu, G. Gini et J. M. Cioffi, “Distributed multiuser power control for digital subscriber lines,” IEEE J. Sel. Areas Commun., vol. 20, no. 5, pp. 1105–1115, May 2002. [4] V. Varma, S. Lasaulce, C. Zhang, and R. Visoz, “Power Modulation: Application to Inter-Cell Interference Coordi- nation”, IEEE Proc. of the EUSIPCO conference, Nice, France, Aug.-Sep. 2015. [5] C.Zhang,V.Varma,S.Lasaulce,andR.Visoz,“Implementing Coordination in Interference Networks through Power Domain Channel Estimation”, IEEE Transactions on Wireless Communications, to appear. [6] S. M. Perlaza, S. Lasaulce, and M. Debbah, “Equilibria of Channel Selection Games in Parallel Multiple Access Channels”, EURASIP Journal on Wireless Communications and Networking (JWCN), Jan. 2013. [7] C. Zhang, S. Lasaulce, and E. V. Belmega, “Using more channels can be detrimental to the global performance in interference networks, IEEE International Conference on Communications (ICC), London, UK, June 2015. [8] Codeon: http://www.codeontechnologies.com/technology/ [9] Braess, D., 1969. Ueber ein Paradoxon aus der Verkehrs Unternehmens Forsch. 24 (5), 258–268.