Ce projet de recherche doctorale est publié a été réalisé par Christophe Le Martret

Description d'un projet de recherche doctoral

Organisation et allocation de ressources dans les réseaux radio ad hoc

Mots clés :

Résumé du projet de recherche (Langue 1)

Le principe de la méthode d’accès multiple à répartition dans le temps (AMRT, TDMA en anglais) consiste à ordonnancer les différents utilisateurs à des instants différents. Comparativement à la famille des accès multiples en compétition, elle permet de fournir de meilleures garanties de QoS et peut mieux tolérer les réseaux où la densité de noeuds du réseau est importante. Cette stratégie est utilisée dans certains réseaux tactiques, comme par exemple [2], et est celle considérée dans la thèse. Les travaux réalisés dans cette thèse se situent donc dans le contexte des couches liaison de données et physique, selon la terminologie de l’OSI, conjointement appelées accès radio. En raison de gains importants [1] qu’elle apporte, c’est l’approche intercouches (cross-layer en anglais) qui sera considérée dans la thèse. Une problématique clef dans les réseaux ad hoc est l’allocation de ressources aux différents noeuds, qui va déterminer qui transmet vers qui, quand et comment. Le comment dépend des capacités de l’accès radio. Lorsqu’il est flexible il est possible de prendre en compte par exemple le schéma de modulation et codage (Modulation and Coding Scheme - MCS - en anglais), la puissance d’émission, ou même le schéma régissant le protocole de retransmission HARQ. Le sujet d’allocation de ressources est largement traité par la littérature dans le cas des réseaux cellulaires, mais l’est beaucoup moins dans le cas des réseaux ad hoc mobiles. Le sujet de la thèse est celui de l’allocation de ressources pour les réseaux tactiques ad hoc large bande. Il regroupe deux grandes problématiques que sont l’organisation du réseau et l’allocation des ressources aux noeuds. Les capacités des équipements radio qui influent sur les protocoles de communication sont nombreuses. Dans le contexte de la thèse les équipements seront considérés comme monovoie et duplexés en temps (TDD). La couche physique choisie sera de type multi-porteuses (par exemple SC-FDMA [3] ou OFDMA [4]), avec plusieurs MCS. La largeur de la canalisation sera variable, dépendante de l’environnement spectral. Enfin il sera possible de faire varier la puissance en transmission. La couche liaison de données considérée sera du type TDMA avec prise en compte la dimension fréquentielle (par exemple TDMA/OFDMA ou TDMA/SC-FDMA). Organisation des réseaux Pour l’organisation du réseau trois grandes approches existent. Tout d’abord celle où le réseau est dit « à plat », puis celle où l’allocation est centralisée, et enfin l’organisation hybride. Dans le cas du réseau « à plat », chaque noeud du réseau est considéré égal aux autres. Les ressources sont allouées via des négociations à portée locale entre les nœuds impliqués. Cette stratégie peut impliquer un fort surcoût protocolaire et manquer de réactivité car elle implique de nombreux échanges entre les noeuds pour gérer les conflits résultants des allocations faites par chacun. La seconde approche est celle où un noeud parmi tous les autres a un rôle privilégié, c’est lui qui alloue les ressources pour l’ensemble du réseau. Un avantage de cette façon de procéder est que le noeud privilégié dispose d’un maximum d’informations et peut optimiser l’allocation. Il le fait au prix des délais importants entre le moment où l’allocation réalisée par le noeud allocateur est décidée et celui où elle est mise en oeuvre sur chaque noeud du réseau, distants de plusieurs bonds radio. De plus cet asynchronisme fait que le noeud allocateur peut se tromper sur la manière d’allouer les ressources, de par le caractère parfois obsolète des informations dont il dispose. Dans l’approche hybride les noeuds des réseaux sont regroupés en grappes, appelés clusters en anglais [5]. A l’intérieur de ces clusters un noeud appelé chef de cluster (cluster head en anglais - CH) peut avoir le rôle d’allocateur de ressources. L’intérêt de cette approche est de simultanément bénéficier d’une information importante et d’une bonne proximité entre le CH qui décide de l’allocation des ressources et les noeuds sur lesquelles elles sont allouées. Cette approche rappelle la structure des réseaux cellulaires mais s’en écarte par la possibilité d’établir des communications ad hoc de pair à pair, à l’intérieur et entre les clusters. C’est l’approche du réseau de clusters qui est principalement étudiée dans la thèse. On trouve deux types de cluster, ceux dans lesquels les noeuds membres d’un cluster sont tous situés à un bond radio du CH et ceux dans lesquels ils sont situés à au plus k bonds, avec k>1. L’avantage des petits clusters est la rapidité avec laquelle ils peuvent échanger des informations avec leur CH. L’atout des plus grands clusters est leur plus grande stabilité. Dans un réseau clusterisé, une fois les CH choisis il faut encore que les autres noeuds, dits ordinaires ou membres, s’affilient aux CH. Lorsqu’un noeud peut appartenir à plusieurs clusters, on parle de clusters recouvrant et le noeud en question peut être un noeud passerelle. Dans ce cas la communication entre les clusters peut se faire via les noeuds passerelles, aux prix toutefois d’une certaine inefficacité. Tout d’abord, considérant des équipements à capacité half-duplex, un noeud passerelle appartenant à n clusters ne peut communiquer qu’une fois sur n dans chaque cluster. De plus les transmissions point à multipoint sont difficiles lorsque tous les destinataires à 1 bond ne se trouvent pas dans le même cluster. Lorsque par construction les clusters son non recouvrant, il n’existe pas de solution simple et efficace pour la communication inter-clusters. Allocation de ressources Une fois l’organisation du réseau en clusters réalisée, il faut allouer les ressources radio pour permettre les communications et pour assurer les QoS requises. Ceci doit se faire à deux niveaux : entre les clusters, et à l’intérieur des clusters. Pour réaliser l’allocation des ressources entre les clusters l’objectif à atteindre est que les communications qui se produisent dans deux clusters différents et voisins n’interfèrent pas entre elles. De nombreuses techniques ont été investiguées dans le domaine des communications cellulaires. Les techniques les plus complexes envisagent une allocation coordonnée entre les cellules où les allocations de fréquences sont déterminées conjointement, et fréquemment. Ces stratégies impliquent une signalisation importante et à très faible latence entre les stations de base des cellules, ce qui les rend difficiles à implémenter. D’autres techniques plus pratiques et moins complexes n’impliquent aucun échange de signalisation entre les stations de bases et consistent en une coordination totalement distribuée entre les cellules. Une approche simple est d’allouer des fréquences différentes aux cellules voisines, c’est le problème de la coloration de graphe. Cette approche n’opère que lorsque suffisamment de fréquences sont disponibles. Une autre approche appelée FFR (« Fractional Frequency Reuse » en anglais) consiste à utiliser plusieurs fréquences dans une cellule [9], chaque fréquence étant allouée sur des critères géographiques (e.g. proximité de la station de base). Lorsque peu de ressources fréquentielles sont disponibles, comme c’est le cas dans le contexte des communications militaires tactiques large bande, il est possible de définir des ensembles disjoints de ressources sur une autre dimension que celle des fréquences. Il est possible de considérer le temps, comme par exemple pour les noeuds qui assurent la communication entre les piconets dans un réseau Bluetooth. Cette approche apporte de la flexibilité à la fonction d’allocation de ressources, au prix d’une complexité accrue. Lorsque chaque CH dispose de ressources pour son cluster, il doit les allouer aux noeuds membres. Cette opération est complexe en raison de la diversité entre les types de QoS requises (délai, débit et taux d’erreur principalement) et est souvent posée comme un problème d’optimisation [10] [11]. La difficulté liée à la résolution de ce type de problème vient de sa non-convexité (nombre fini de MCS, quantification de la puissance allouable en transmission, allocation en groupes de sous-porteuses, etc.). Unende complexité calculatoire. D’autres travaux moins complexes ne visent pas l’optimum tout en offrant de bonnes performances. Un exemple de ce type d’approche est de décomposer la fonction d’allocation de ressources en plusieurs étapes : allocation de lien, puis allocation de bande passante, puis éventuellement allocation de sous porteuses, et enfin allocation de MCS conjointement à la puissance. De manière à les sécuriser et à augmenter leur robustesse face aux évanouissements, dans les réseaux tactiques les communications sont à évasion rapide de fréquence. Ceci augmente la difficulté de l’apprentissage fin du canal. Pour cette raison, bien que les gains théoriques sont importants, il semble complexe de mettre en oeuvre une allocation sélective en fréquences. Une alternative consiste à considérer un canal moyen sur toute la bande de fréquences. Une connaissance fine sur l’état du système (canal radio, position des noeuds, ressources utilisées dans le voisinage radio, etc.) permet de mieux l’optimiser et d’atteindre de meilleures performances. Cependant l’acquisition de cette connaissance nécessite l’échange d’un surcroit de signalisation sur le réseau, au détriment du trafic utile. Un compromis est donc requis entre la quantité de signalisation générée et l’information requise pour permettre une allocation de ressources performante.

Résumé du projet de recherche (Langue 2)

Organisation des réseaux

Un cas particulièrement difficile à traiter est le cas des réseaux très denses où chaque noeud du réseau possède de nombreux (au moins plusieurs dizaines) noeuds voisins à 1 bond radio. Au cours de la thèse des protocoles et algorithmes seront proposés pour améliorer la gestion des réseaux tactiques très denses. Il s’agira de rechercher :

• Des algorithmes de construction de clusters à nombre de noeuds limité en suivant l’approche distribuée proposée dans [6]. Il s’agit de former une bi-clique à nombre de liens maximum, où l’un des deux sous-graphes composant la bi-clique est composé des noeuds du cluster et où la constitution du second sous-graphe doit permettre de limiter le nombre de noeuds du cluster tout en garantissant la connectivité du réseau. La notion de communauté d’intérêts sera une des métriques prise en compte pour la constitution des clusters de manière à regrouper ensemble les noeuds du réseau qui partagent des attributs communs.

• Des protocoles pour créer un réseau constitué d’un ensemble de clusters à nombre maximum de noeuds, tels que celui proposé dans [7] qui propose une approche distribuée en cinq phases aboutissant à la création d’un scatternet Bluetooth dont les piconets sont identifiables à des clusters.

Ces deux approches visent à limiter le nombre de noeuds dans un cluster, quitte à aboutir à la construction de clusters géographiquement co-localisés.

Les objectifs qui seront considérés durant les travaux sont les suivants : (1) minimiser le nombre de clusters, (2) privilégier une homogénéité de taille entre les clusters, (3) assurer que les clusters soient de taille « suffisante » pour que le bénéfice apporté par la présence du CH soit significatif (à l’extrême un réseau ou chaque cluster est réduit à un CH est un réseau à plat), et (4) garantir que la structure de cluster soit robuste en présence de mobilité. Pour ce dernier point, il faut éviter l’effet de vague (« ripple effect» en anglais) selon lequel une modification locale de topologie peut avoir des répercussions sur la structure de cluster globale du réseau.

Une autre manière de gérer la densité est de mettre en oeuvre des techniques de contrôle de topologie en adaptant la puissance de transmission des noeuds du réseau. En fonction de la topologie du réseau considéré, cette approche peut parfois permettre d’en améliorer la capacité du réseau. Par exemple les auteurs de [8] donnent quelques résultats en ce sens, mais la stratégie d’accès radio envisagée n’est que succinctement décrite et est basée sur de la détection de porteuse. Ainsi au cours de la thèse nous étudierons le contrôle de puissance pour les réseaux de type ad hoc mobiles afin de d’étendre [8] aux cas de la méthode d’accès multiple considérée.

Allocation de ressources

Certaines techniques de transmission multi-porteuses offrent une granularité accrue à l’allocation de ressources. Dans les techniques SC-FDMA ou OFDMA la deux dimensions temps et fréquence sont utilisables ce qui permet pour chaque flux d’optimiser la quantité de ressources radio allouée au besoin du flux. Ce type de techniques sera considéré dans la thèse. Un intérêt de la technique SC-FDMA est de présenter des caractéristiques de Peak Average Power Ratio (PAPR) meilleures que l’OFDMA. Ceci est vrai pour les deux schémas principaux I-FDMA (où les sous-porteuses sont allouées de façon entrelacées) et L-FDMA (où les sous-porteuses sont allouées de manière contiguës) de répartition des sous-porteuses. Au niveau de l’allocation de ressources, la contrainte principale apportée par l’utilisation du SC-FDMA par rapport à celle de l’OFDMA est que si à tout instant un récepteur peut écouter plusieurs émetteurs, pour préserver la caractéristique mono porteuse du signal (et les bonnes performances au niveau du PAPR) un émetteur ne peut transmettre que vers un seul récepteur.

Dans la thèse nous rechercherons et étudierons des algorithmes distribués pour le cas des réseaux tactiques, afin d’allouer les ressources aux clusters. La référence [12] considère un réseau de clusters et propose un algorithme distribué qui consiste à allouer une fréquence unique à chaque cluster de façon à minimiser l’interférence globale mesurée dans le réseau. Cette approche sera étendue selon les axes suivants :

• Afin d’augmenter la granularité d’allocation dans un contexte où la largeur de bande totale est limitée, la canalisation utilisée pour les transmissions sera variable. C’est à dire qu’à la place de considérer la possibilité d’allouer n1 fréquences chacune ayant une canalisation associée de B1 hertz, ce sont n2 = k.n1 (k entier) fréquences et une canalisation de B2 = B1 / k hertz qui seront considérés,

• Plusieurs fréquences pourront être allouées à chaque cluster tout en prenant garde aux écueils déjà connus dans ce contexte, comme par exemple dans le cas du water- filling itératif [12] [13],

• Dans le contexte de transmissions SC-FDMA et afin de pouvoir allouer si nécessaire toute la ressource pour une transmission lorsque plusieurs fréquences sont allouées à un cluster, la fonction d’utilité utilisée pour calculer l’allocation de ressources favorisera l’allocation de fréquences contiguës.

Dans la thèse nous rechercherons et étudierons des algorithmes et protocoles d’allocation de ressources à l’intérieur des clusters. Une attention particulière sera portée à la satisfaction de QoS évaluée selon les métriques de débit et délai, ainsi qu’à la garantie d’une certaine équité entre les flux. Plus précisément, il s’agira de rechercher plusieurs algorithmes qui vont allouer les liens internes au cluster et sur ces liens, le nombre de sous-porteuses, les sous-porteuses, le MCS et la puissance. Ils auront les caractéristiques suivantes :

• Les objectifs de QoS seront d’offrir un traitement différencié pour les flux à contrainte à long terme de débit et les flux à contrainte de délai [14], et de garantir une allocation équitable de type proportional fair [14] au sein d’une classe de trafic. Pour pouvoir traiter des flux qui présentent différentes importances opérationnelles l’allocation de ressources devra être construite de manière hiérarchique [15],

• Les contraintes à satisfaire seront de pouvoir allouer tous les liens du cluster (sans forcément passer par le chef de cluster), et de calculer l’allocation de ressources sur un nombre suffisant de time slots afin de minimiser la quantité de signalisation [16].

Afin de montrer la faisabilité d’une mise en oeuvre des solutions proposées, elles seront intégrées à une simulation de réseau dite « high fidelity » et basée sur l’outil OMNeT++ [17]. Ce type de simulation est nécessaire pour évaluer les performances de systèmes de communications conçus selon l’approche inter-couches. Il permet de modéliser finement des phénomènes dont les effets sur les communications sont très importants, tels que les surcoûts protocolaires liés à la signalisation, les asynchronismes inhérents à l’exécution de protocoles et algorithmes distribués, ou l’effet du canal radio sur la messagerie de signalisation. Dans cette simulation c’est l’accès radio qui sera modélisé le plus finement. Notamment ce modèle :

• Utilisera un protocole de distribution de l’allocation tirant partie de la notion de motifs d’allocation [16], afin de minimiser la quantité de signalisation,

• Mettra en oeuvre le mécanisme de détection de voisinage de [18] pour s’adapter aux cas des réseaux de forte densité.

Informations complémentaires (Langue 2)

Références

[1] D. ONeill, A.J. Goldsmith, and S.P. Boyd, “Optimizing adaptive modulation in wireless networks via utility maximization,” Best Paper Award, Proc. of International Conference on Communications (ICC), 2008, Beijing, PRC

[2] C. D. Young , “USAP multiple access: dynamic resource allocation for mobile multihop multichannel wireless networking”, MILCOM 1999

[3] Hyung G. Myung, Junsung Lim, and David J. Goodman; “Single Carrier FDMA for Uplink Wireless Transmission”; IEEE Vehicular Technology Magazine, September 2006

[4] C. Ciochina and H. Sari; “A Review of OFDMA and Single-Carrier FDMA and Some recent Results”; European Wireless Conference, April 2010

[5] K. Erciyes, O. Dagdeviren, D. Cokuslu and D. Ozsoyeller; “Graph theoretic clustering algorithms in mobile ad hoc networks and wireless sensor networks – Survey”; Applied and Computational Mathematics special Issue on Information Technologies and Applications, 2007

[6] L. Lazos, S. Liu, and M. Krunz, “Spectrum Opportunity-Based Control Channel Assignment in Cognitive Radio Networks”, in Proc. Of IEEE SECON, June 2009 [7] Z. Wang, R.J. Thomas and Z. J. Haas, “Performance comparison of Bluetooth scatternet formation protocols for multi-hops networks”, in Journal Wireless Networks Volume 15 Issue 2, February 2009

[8] Y. Wang, J.C.C. Lui and D.M. Chiu, “Understanding the Paradoxical effects of Power Control on the Capacity of Wireless Networks”, in IEEE Transactions on Wireless Communications, January 2009

[9] A.L. Stoylar, H. Viswanathan; “Self-organizing dynamic fractional frequency reuse for best effort traffic through distributed inter-cell coordination”; INFOCOM 2009

[10] Zhi-Quan Luo Wei Yu ; “An introduction to convex optimization for communications and signal processing”; IEEE journal on Selected Areas in Communications, 2006

[11] M. Andrews and L. Zhang; “Scheduling Algorithms for Multicarrier Wireless Data Systems”; IEEE/ACM Transactions on Networking, April 2011

[12] B. Babadi and V. Tarokh; GADIA: A Greedy Asynchronous Distributed Interference Algorithm; IEEE Transactions on Information Theory, Dec 2010

[13] W. Yu, G. Ginis and J. M. Cioffi; Distributed Multiuser Power Control for Digital Subscriber Lines; IEEE journal on Selected Areas in Communications, June 2002

[14] T. Girici, C. Zhu, J. R. Agre and A. Ephremides; “Proportional Fair Scheduling Algorithm in OFDMA-Based Wireless Systems with QoS Constraints”; Journal of Communications and Networks; Feb 2010

[15] X. Wang and W. Xiang; “An OFDM-TDMA/SA MAC Protocol with QoS Constraints for Broadband Wireless LANs”; ACM Journal of Wireless Networks, March 2006

[16] M. Andrews and L. Zhang; “Creating Templates to Achieve Low Delay in Multi- Carrier Frame-Based Wireless Data Systems” ; IEEE INFOCOM 2008

[17] R. Massin, C. Lamy-Bergot, C. J. Le Martret, et R. Fracchia, “OMNeT++-Based Cross-Layer Simulator for Content Transmission over Wireless Ad Hoc Networks”, EURASIP Journal on Wireless Communications and Networking, 2010

[18] P. Fouillot, R. Massin, C. Lamy-Bergot, I. Herbin and G. Multédo; “Collision Reduction in Random Access Slots for TDMA Tactical Mobile Ad Hoc Networks”; ACM SIGMOBILE MobiHoc May 2011