THÈSE DE DOCTORAT DE L’UNIVERSITÉ PIERRE ET MARIE CURIE Spécialité : Informatique École doctorale : « EDITE de Paris » réalisée au Laboratoire Informatique de Paris 6 présentée par Alexandre RAGALEUX pour obtenir le grade de : DOCTEUR DE L’UNIVERSITÉ PIERRE ET MARIE CURIE Sujet de la thèse : Mécanismes D’Accès Multiple dans les Réseaux Sans Fil Large Bande soutenue le 22/09/2016 devant le jury composé de : Mme Véronique Vèque Rapporteur M. Nadjib Achir Rapporteur Mme Maria Potop-Butucaru Examinateur M. Steven Martin Examinateur M. Sébastien Baey Encadrant Mme Anne Fladenmuller Directeur de thèse Version du 28 septembre 2016 Version du 28 septembre 2016 Remerciements Je dois bien l’avouer, une thèse est une aventure très riche. Pendant ces trois an- nées, j’ai eu le plaisir de vivre de nombreux moments inoubliables et de traverser une succession d’émotions, parfois négatives mais bien plus souvent positives. Avant tout, cette thèse m’a permis de resserrer les liens avec mon entourage et m’a donné la possi- bilité de rencontrer de nouvelles personnes. Cette première section est donc l’occasion pour moi d’exprimer mes remerciements les plus sincères à tous ceux qui ont contri- bué de près ou de loin à l’élaboration de ce travail. En plus, il paraît que la section « Remerciements » est la plus lue d’une thèse! Je tiens à remercier tout particulièrement Sébastien pour m’avoir fait confiance, pour ses conseils précieux et ses relectures minutieuses. Il fut un pilier indispensable à la concrétisation de mes idées et à la réussite de cette thèse. MesremerciementslesplussincèresàAnnepoursagentillesse,etpours’êtreassurée que je puisse travailler sur ma thèse dans les meilleures conditions possibles. Merci énormément pour m’avoir donné l’opportunité de voyager. Je tiens également à remercier Mme Véronique Vèque, M. Nadjib Achir, M. Steven Martin et Maria qui m’ont fait l’honneur d’accepter de faire partie de mon jury de thèse. J’adressetoutemagratitudeàl’équipeNPA.J’aipassétroisansdanscelaboratoire dont l’ambiance est propice aux échanges, aux débats et à la création. Merci à Marcelo pour avoir su conserver et maintenir une telle cohésion. Merci à Sébastien Tixeuil pour m’avoir permis de débuter par un stage et ainsi de commencer cette formidable aventure. Merci à Prométhée pour sa personnalité atypique rafraîchissante et ses histoires aussi insolites qu’hilarantes. Enfin, merci à Kim, Olivier ainsi que toute l’équipe pédagogique de la spécialité Réseaux, qui m’ont beaucoup apporté en Master. Un grand merci aux doctorants de l’équipe pour leurs bonnes humeurs et l’intérêt qu’ils ont porté à mes recherches. Ce fut un honneur de partager ces moments avec eux. Un merci tout particulier à Benjamin avec qui j’ai eu le plaisir d’effectuer toutes mesétudesuniversitaires. Cettethèsemarqueainsilafindenotrelonguecollaboration (8 ans!), mais je sais que notre amitié perdurera. Je remercie Björn pour m’avoir accueilli trois mois dans son laboratoire, en Suède, ainsi que toute son équipe pour m’avoir intégré très chaleureusement, ce qui a été nécessaire pour affronter la température extérieure... Merci à mes parents pour leur soutien inestimable. Merci à ma mère pour sa dispo- nibilité, sa lucidité et son ouverture d’esprit. Merci à mon père, pour m’avoir poussé à aller toujours plus loin et qui s’est toujours montré disponible pour m’écouter autour i Version du 28 septembre 2016 ii d’une bonne table parisienne. Bien évidemment, merci à Charline pour m’avoir supporté pendant ces trois ans. Cohabiter avec un doctorant n’est pas chose aisée, et pourtant elle a été là pour moi. Je ne pourrai quantifier rationnellement le plaisir que j’ai eu à la retrouver chaque soir. Sa présence à mes côtés fut essentielle à bien des égards. Version du 28 septembre 2016 Table des matières 1 Introduction 1 1.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Résumé des contributions . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Description du système . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3.1 Modèle et hypothèses de travail . . . . . . . . . . . . . . . . . . . 4 1.3.2 La contrainte du Single MCS . . . . . . . . . . . . . . . . . . . . 5 1.3.3 Non-linéarité du calcul du débit. . . . . . . . . . . . . . . . . . . 7 1.3.4 Spécificités relatives au sens de transmission . . . . . . . . . . . . 7 1.3.5 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Organisation de la thèse . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 État de l’art 11 2.1 Un mot sur la théorie de la complexité . . . . . . . . . . . . . . . . . . . 11 2.2 Stratégies d’allocation de ressources issues des réseaux filaires . . . . . . 13 2.2.1 Stratégies d’allocation de ressources opportunistes . . . . . . . . 14 2.3 Allocation de ressources dans les réseaux LTE . . . . . . . . . . . . . . . 17 2.3.1 Sens descendant . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3.2 Sens montant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3 Allocation de ressources dans le sens descendant 25 3.1 Formalisation du problème. . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.1.1 Le problème LTE DL FDPS . . . . . . . . . . . . . . . . . . . . . 26 3.2 Sous-problème et résultats fondamentaux . . . . . . . . . . . . . . . . . 28 3.3 Algorithme d’approximation . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3.1 Première étape : vers la résolution de P2 . . . . . . . . . . . . . 31 3.4 Deuxième étape : prise en compte du single MCS . . . . . . . . . . . . . 33 3.5 Troisième étape : extension . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.5.1 Un mot sur la complexité . . . . . . . . . . . . . . . . . . . . . . 36 3.6 Évaluation des performances . . . . . . . . . . . . . . . . . . . . . . . . 36 3.6.1 Modélisation de la couche physique . . . . . . . . . . . . . . . . . 37 3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 iii Version du 28 septembre 2016 iv TABLE DES MATIÈRES 4 Allocation de ressources avec Trafics Multimédias 45 4.1 Vers la quantification de la Qualité de Service . . . . . . . . . . . . . . . 46 4.1.1 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.2 AGSS : Schéma d’ordonnancement générique et adaptatif . . . . . . . . 50 4.2.1 Préliminaires : un point sur les stratégies d’ordonnancement . . . 50 4.2.2 Présentation d’AGSS . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.2.3 Un mot sur la complexité . . . . . . . . . . . . . . . . . . . . . . 53 4.3 Stratégie d’ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.4 Évaluation des performances . . . . . . . . . . . . . . . . . . . . . . . . 57 4.4.1 Algorithme classique vs AGSS . . . . . . . . . . . . . . . . . . . 58 4.4.2 Comparaison des stratégies d’ordonnancement . . . . . . . . . . 59 4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5 Allocation de ressources dans le sens montant 65 5.1 Formulation du problème . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.1.1 Problème du LTE UL TFDPS. . . . . . . . . . . . . . . . . . . . 67 5.1.2 Expression des stratégies d’ordonnancement et sous-problèmes . 67 5.1.3 Difficulté du problème . . . . . . . . . . . . . . . . . . . . . . . . 68 5.2 APASS : algorithme d’allocation de ressources dans le sens montant . . 69 5.2.1 Allocation de ressources pour une relaxation du problème . . . . 69 5.2.2 Sélection des utilisateurs . . . . . . . . . . . . . . . . . . . . . . . 73 5.3 Améliorations et finalisation de l’allocation . . . . . . . . . . . . . . . . 74 5.3.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.3.2 Dernière étape de l’allocation de ressources . . . . . . . . . . . . 75 5.3.3 Un mot sur la complexité . . . . . . . . . . . . . . . . . . . . . . 77 5.4 Évaluation des performances . . . . . . . . . . . . . . . . . . . . . . . . 78 5.4.1 Comparaison des stratégies d’ordonnancement . . . . . . . . . . 79 5.4.2 Comparaison des algorithmes . . . . . . . . . . . . . . . . . . . . 80 5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6 Conclusion 83 6.1 Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6.2 Perspectives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 A Description du RAN de LTE 87 A.1 L’architecture des protocoles RAN . . . . . . . . . . . . . . . . . . . . . 87 A.2 Structure de la trame LTE . . . . . . . . . . . . . . . . . . . . . . . . . . 88 A.3 Mode de duplexage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 A.4 Détermination de la taille d’un transport block . . . . . . . . . . . . . . 90 A.5 Estimation de la qualité du canal . . . . . . . . . . . . . . . . . . . . . . 91 A.5.1 Allocation dans le sens descendant . . . . . . . . . . . . . . . . . 92 A.5.2 Allocation dans le sens montant . . . . . . . . . . . . . . . . . . 92 A.5.3 Taille des Transport Blocks . . . . . . . . . . . . . . . . . . . . . 93 Version du 28 septembre 2016 TABLE DES MATIÈRES v B Publications 95 B.1 Articles publiés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 B.2 Articles en cours de soumission . . . . . . . . . . . . . . . . . . . . . . . 95 B.3 Rapports techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Bibliographie 97 Version du 28 septembre 2016 vi TABLE DES MATIÈRES Version du 28 septembre 2016 Chapitre 1 Introduction 1.1 Contexte Afin de toujours faire évoluer les débits ainsi que l’expérience des utilisateurs, les chercheurs et ingénieurs améliorent constamment l’architecture des réseaux mobiles. Les réseaux Long Term Evolution (LTE), commercialisés comme de la 4G, ont été largement déployés à travers le monde [1]. Son successeur, la 4G+ ou “la vraie 4G” (LTE-A, Releases 10-11), commence à être déployée dans les grandes villes [2]. Cette technologie offre le support de la voix et triple le débit théorique. La dernière généra- tion, la pré-5G1 (LTE-B, Release 12-13), a été conçue pour ouvrir la route de la 5G en offrant des débits encore améliorés afin de supporter les nouvelles utilisations des réseaux cellulaires (transfert massif de données). Parallèlement, de nouveaux types d’applications mobiles ont émergé. Celles-ci bé- néficient de l’augmentation des débits en utilisant massivement la bande passante et nécessitent une gestion efficace de la Qualité de Service. Pour s’adapter à ces nouvelles utilisations des réseaux cellulaires, les procédures d’allocation de ressources doivent évoluer afin de répondre aux attentes des applications. Les réseaux LTE reposent sur une méthode d’accès au canal très performante ap- pelée OFDMA (Orthogonal Frequency Division Multiple Access) qui permet de tirer pleinement parti de la diversité temporelle et fréquentielle du canal. Cependant, même une méthode d’accès efficace utilisée conjointement avec un schéma de modulation de et codage (ou MCS pour Modulation and Coding Scheme) adapté n’est généralement pas suffisante pour aboutir à des performances convenables. En effet, la façon dont les ressources sont allouées a une influcence très importante sur les performances obte- nues[3].Parconséquent,l’allocationderessourcesestdevenueundomainederecherche fondamental. Dans cette thèse, nous considérons une station de base qui communique avec plu- sieurs équipements utilisateurs (Fig. 1.1 pour le cas du sens descendant). La cellule considérée peut être indifféremment une small cell ou une macro cell. Les sens descen- dant et montant sont distingués. Dans le sens descendant, les paquets sont originaires de flux de données provenant du réseau coeur et sont mis en mémoire dans des buffers. 1. Comme cette technologie n’est pas encore disponible, le nom commercial de LTE-B n’est pas définitif. 1 Version du 28 septembre 2016 2 Chapitre 1. Introduction Nous considérons que chaque buffer est associé à un seul et unique flux. L’ordonnan- ceur a pour rôle de partager les ressources radios entre les flux afin que les paquets puissent être transmis vers leur destinataire. Le sens montant est organisé de façon analogue, i.e. les flux sont originaires des applications mobiles et les buffers se situent dans les équipements utilisateurs. Une particularité des réseaux sans fil est qu’ils sont soumis à de nombreuses défi- ciences du canal (atténuation du signal, évanouissement sélectif en fréquence, multi- trajets ...). Dans le système LTE, les ressources radios sont à la fois divisées dans le domaine temporel et dans le domaine fréquentiel. L’exploitation des variations tem- porelles et fréquentielles de la qualité des ressources est essentielle afin de fournir une connexion haut débit aux utilisateurs. En effet, à un instant donné, une ressource peut être de bonne qualité pour un utilisateur (i.e. l’utilisateur bénéficie d’un haut SNR (Signal to Noise Ratio) sur cette ressource), et de mauvaise qualité pour un autre. Dans ce contexte, les ordonnanceurs opportunistes sont apparus [4, 5, 6, 7, 8]. Ces derniers prennent en compte la qualité des liens radio dans leur procédure d’allocation de ressources. Cependant, une large majorité de ces travaux prend pour hypothèse que les buffers sont toujours pleins (infinitely backlogged buffers model). Or, la variabilité des trafics multimédias en termes de débit instantané peut être très importante. Ces types de caractéristiques doivent être pris en compte à courte échelle de temps afin d’assurer aux applications un niveau de qualité de service satisfaisant. Nous avons étudié de très près la norme 3GPP LTE afin d’identifier les contraintes qui s’appliquent au problème de l’allocation de ressources. La plus importante d’entre elles,quenousavonsappeléelacontrainteduSingle MCS,estpeupriseencomptedans la littérature mais a des conséquences notables sur la manière d’allouer les ressources. En effet, la norme autorise uniquement l’utilisation d’un seul MCS par utilisateur sur l’ensembledesressourcesquiluisontallouées.Cettecontrainteréduitconsidérablement l’exploitation de la diversité fréquentielle, et donc les performances du système. De plus, cette contrainte rend obsolètes les procédures d’allocation de ressources qui ne la prennent pas en compte. Notons que les solutions proposées dans cette thèse visent les toutes dernières versions de LTE, y compris LTE-B (LTE Release 13) qui a été publié au début de l’année 2016. 1.2 Résumé des contributions Tout d’abord, nous avons modélisé un système LTE en utilisant directement la norme comme support d’information. De plus, nous proposons une formulation gé- nérique du problème de l’allocation de ressources. Ainsi, nos solutions sont également génériquesetcouvrentdoncungrandnombred’objectifs(maximisationdelacapacité, équité entre les utilisateurs, etc...). Nous avons fait le choix d’approcher les différents problèmes à la fois de manière théorique et pratique. Pour cela, pour chaque problème considéré, la méthodologie suivante à été appliquée : – Étude de la complexité du problème et proposition d’une solution avec garantie par rapport à la solution optimale. Afin d’analyser le problème, l’hypothèse des Version du 28 septembre 2016