Cours étude et conception d’algorithmes pour les réseaux mobiles et ad hoc, tutoriel & guide de travaux pratiques en pdf.

La mobilité dans les réseaux sans ®l : état de l’art

Le GSM devrait céder sa place aux services GPRS et l’UMTS qui offrent des débits plus élevés et d’autres modes de communications en plus de la voix. Comme indiqué dans son nom, l’UMTS se veut universel. Il faut cependant se rendre à l’évidence : principalement à cause de sa bande passante assez limitée, cette 3ème génération ne sera pas la dernière, loin de là. L’usage de la solution WLAN nécessite une utilisation d’une bande de fréquence jusque là consacrée à la défense national, la migration de celle-ci vers de nouvelles bandes de fréquence est lente, ce qui empêche le WLAN de se développer librement. Dans ce contexte et afin de mieux positionner cette thèse, nous faisons une classification des réseaux mobiles et sans fil selon l’étendue géographique et la topologie. Cette classification va nous permettre d’introduire la notion d’une structure hiérar-chique des réseaux mobiles et sans fil dans le chapitre suivant. Nous nous intéressons à l’aspect de l’évolution des systèmes sans fil et leurs caractéristiques pour mieux comprendre le besoin d’une nouvelle génération.

Historique, évolution et applications des réseaux sans ®l

L’histoire des communications radio-mobiles peut être découpée en trois grandes phases. La première concerne les découvertes théoriques et la mise en évidence de l’existence des ondes ra-dios. Cette phase débute en 1678 avec les travaux de Huygens sur les phénomènes de réflexion et de réfraction de la lumière. C’est Fresnel qui, en 1819 en démontre la nature ondulatoire. En 1865, Maxwell établit les célèbres formules unifiant phénomènes électrique, magnétiques et lumineux mais ce n’est qu’en 1887 que Hertz met en évidence pour la première fois la possibilité d’émis-sion/détection d’une onde électromagnétique entre deux points distants de quelques mètres. À la fin du siècle, en 1897, Ducretet étend cette distance en établissant une liaison radio de quelques kilomètres de porté. Après avoir montré la possibilité de communications radio-mobile entre un bateau et une île en 1898, Macroni met en place la première radio trans-Atlantique entre l’Europe et les Etats-Unis trois ans plus tard. Il marque ainsi le point de départ des premiers systèmes de communications radio.
La seconde phase est constituée par le développement et l’évolution des équipements et des techniques mais pour des usages encore réservés à certaines catégories de la population. Les sta-tions radio d’émission/réception sont au début du 20e siècle de taille imposante. Par exemple en 1902, une station radio militaire pour le télégraphe était constitué d’un moteur à essence pour tracer le système de communications consistant en générateur de 1kW monté sur une remorque suivie d’une seconde remorque pour l’émetteur et le récepteur. C’est l’évolution des techniques et des équipements (taille, poids, la porté des communications et les services radiotéléphonie) qui permettra aux systèmes radios d’acquérir la dimension mobile. La seconde guerre mondiale va accélérer le développement des systèmes qui vont, dans les années 1950, se multiplier pour les applications civiles (compagnies de taxis et ambulances par exemple). Les équipements restent cependant encore lourds et occupent une place importante puisqu’ils sont généralement installés dans les coffres des véhicules.
Les progrès techniques et développement des systèmes de communications vont faire entrer les systèmes de communications sans fil et mobiles dans le domaine grand publique (la troisième phase). Les premiers types de systèmes de communications disponibles au plus grand nombre sont les systèmes cellulaires. Conçu comme réponse à l’augmentation de la demande et à la faible disponibilité du spectre radio, les systèmes cellulaires analogiques se développent dans la décennie 1970. En 1979, le premier système cellulaire AMPS (Advanced Mobile Phone Service) est installé à Chicago, suivi en 1980 par le HCMTS (Hight Capacity Mobile Telephone System) à Tokyo. La décennie 1980 va voir ainsi se généraliser l’implantation de systèmes cellulaires analogiques dans de nombreux pays. Parallèlement, les systèmes sans cordon, se développent et connaissent des taux de croissance impressionnants. Toutefois, c’est réellement le système cellulaire numérique GSM (voir section 2.3.1), avec les services de type RNIS (Réseau Numérique à Intergration de Services) et la possibilité de roaming international, qui constitue le représentant le plus significatif de la révolution des mobiles de la décennie 1990. les systèmes sans fil et mobiles vont toucher progressivement tous les domaines d’activités économiques et intégrer peu à peu tous les types de services de télécommunications.
Comme on l’a déjà mentionné, plusieurs facteurs ont contribué à l’évolution rapide de ces dernières années. En effet, la miniaturisation des composants a permis de réduire la taille des produits électroniques sans fil en général (GPS, téléphone sans fil, …) et le matériel informatique en particulier. Les ordinateurs portables sont de plus en plus légers et puissant en même temps, génération après génération. Cette miniaturisation s’est accompagnée avec une évolution d’autonomie et une baisse de consommation. Un autre facteur important qui aide beaucoup à rendre la technologie sans fil plus populaire est la baisse des prix ainsi que la disponibilité des bandes radios ISM (Industrial Scientific and Medical) et UNII (Unlicensed National Information Infrastructure) à 800 MHz, 2.4 GHz et 5 GHz, qui peuvent être utilisées gratuitement et sans autorisation (malgré quelques différences dans la législation d’un pays à un autre).
Avec la récente évolution des technologies de communication sans fil. On s’attend à un développement rapide des réseaux locaux sans fil et leur utilisation sera de plus en plus fréquente. Bien que les projets aient souvent débuté dans un cadre militaire pur, le domaine d’application des réseaux sans fil s’étend bien au-delà. En effet, les réseaux sans fil offrent une grande flexibilité ainsi qu’une rapidité et facilité de mise en place. Ils seront d’un grand apport lors des catastrophes naturelles, des incendies, où il sera indispensable de disposer rapidement d’un réseau pour organiser les secours et les opérations de sauvetage.
Les réseaux sans fil sont plus faciles à implanter dans des bâtiments, où il est impossible d’installer des câbles convenablement ; tel que les vieux bâtiments, les sites classés (exemple : châteaux et monuments historiques), lors des manifestations temporaires (congrès, foires, salons, expositions, le tour de France, et autre manifestation sportives). On peut aussi avoir recours à ce type de réseau lorsqu’on veut interconnecter des bâtiments à moindre coût (i.e., sans location d’une liaison spéciale chez un opérateur). On peut imaginer une application industrielle, où les nœuds seront en fait des robots mobiles qui pourront se déplacer librement dans l’usine. Ou bien encore,
dans des environnements hostiles à l’homme tels que des cratères de volcans pour surveiller leur activités ou bien le long d’une faille géologique. Dans les campus universitaires, l’utilisation des réseaux sans fil peut être très utile pour les étudiants qui pourront se connecter sur leurs comptes et travailler à partir de la bibliothèque ou leurs chambres.

Problèmes des transmissions radios et des réseaux sans ®l

Les ondes radios (notées RF pour Radio Frequency) se propagent en ligne droite dans plusieurs directions. La vitesse de propagation des ondes dans le vide est de 3:108 m/s. Lorsqu’une onde radio rencontre un obstacle, une partie de son énergie est absorbée et transformée en énergie (thermique par exemple), une partie continue à se propager de façon atténuée et une dernière peut éventuellement être réfléchie. L’atténuation augmente avec l’augmentation de la fréquence ou de la distance. De plus lors de la collision avec un obstacle, la valeur de l’atténuation dépend fortement du matériel composant l’obstacle. Généralement les obstacles métalliques provoquent une forte réflexion, tandis que l’eau absorbe le signal.
Les réseaux sans fil utilisent des ondes radios ou infrarouges afin de transmettre des données. Les transmissions radios dans les réseaux sans fil sont toutefois soumises à de nombreuses contraintes, liées à la nature de la propagation des ondes radios et aux méthodes de transmissions, rendant ce type de transmission non suffisante. Le signal transmis est sujet à nombreux phénomènes dont la plupart ont un effet de dégradation sur la qualité du signal. Cette dégradation se traduit en pratique par des erreurs dans les messages reçus qui entraînent des pertes d’informations pour l’usager ou le système. Ces contraintes sont notamment :
☞ débit plus faible que celui du filaire. La bande passante est une ressource rare, il faut minimiser la portion utilisée pour la gestion du réseau, afin de pouvoir laisser le maximum de bande passante pour les communications ;
☞ les brouillages dus aux interférences : les liens radios ne sont pas isolés, deux transmission simultanées sur une même fréquence ou, utilisant des fréquences proches peuvent interférer. De plus, les interférences peuvent venir d’autres types de machine non dédiées aux télécom munications. Par exemple, les fréquences utilisées dans les fours à micro-ondes sont dans les fréquences de la bande ISM ;
☞ les brouillages dus au bruit ambiant (que nous distinguons des interférences), provenant d’émission d’autres systèmes par exemple ;
☞ les évanouissements (ou fadings) dans la puissance du signal dus aux nombreux effets induits par le phénomène de multitrajets ;
☞ erreurs de transmission : les erreurs de transmission radio sont plus fréquentes que dans les réseaux filaires ;
☞ liens versatiles : les transmissions radios sont très sensibles aux conditions de propagation, ce que les rend versatiles. Un contrôle de la qualité des liens est obligatoire afin de pouvoir les exploiter convenablement pour les communications radios ;
☞ puissance du signal : la puissance du signal diminue avec la distance, et la puissance utilisée est sévèrement réglementée par les autorités compétentes des pays ;
☞ les pertes de propagation dues à la distance parcourue par l’onde radio, ou affaiblissement de parcours (pathloss) ;
☞ les atténuations de puissance du signal dues aux effets de masques (shadowing) provoqués par les obstacles rencontrés par le signal sur le trajet parcouru entre l’émetteur et le récepteur ;
☞ nœuds cachés : ce phénomène est très particulier à l’environnement sans fil. Les nœuds qui ne s’entendent pas, à cause d’un obstacle qui empêchent la propagation des ondes, peuvent provoquer des collisions ;
☞ impossibilité de détecter les collisions au cours d’une transmission. Pour détecter une collision, une station doit être capable de transmettre et d’écouter en même temps. Or, dans les systèmes radios, il ne peut y avoir transmission et écoute simultanées ;
☞ consommation d’énergie : qui dit sans fil, dit aussi mobilité, et donc autonomie. Pour maximiser la durée de vie des batteries, il faut économiser autant que possible les transmissions inutiles ;
☞ sécurité : les détecteurs des signaux et les récepteurs passifs peuvent espionner les communications radio si ces dernières ne sont pas protégées ;
☞ mobilité et topologie dynamique : la disparition ou l’apparition d’un nœud ou un lien entre deux nœuds peut être le résultat d’un déplacement, c’est aussi parce que la batterie est épuisée ou lorsqu’une panne survient.

Les réseaux mobiles et sans ®l

Les termes mobile et sans fil sont souvent utilisés pour décrire les systèmes existants, tels que le GSM, IS95, IEEE 802.11, Bluetooth, etc. Il est cependant important de distinguer les deux catégories de réseaux que recoupent les concepts de mobile et de sans fil de façon à éviter toute confusion. Prenez l’exemple (tiré de [7]) du téléphone sans cordon de résidence. Ce téléphone donne accès au RTC (réseau téléphonique commuté), le réseau classique de téléphone, ou au RNIS (Réseau numérique à intégration de services). Le support de communication utilise l’interface radio pour qu’un abonné puisse appeler depuis son jardin ou sa cuisine, mais ce dernier doit toujours rester au voisinage de son réseau d’abonnement. En cas de mobilité dépassant ces limites, l’utilisateur est contraint de contacter un opérateur local pour souscrire un nouvel abonnement ce genre de systèmes offrent le sans fil sans la mobilité.
Un utilisateur mobile est défini théoriquement comme un utilisateur capable de communiquer
à l’extérieur de son réseau d’abonnement tout en conservant une même adresse. Certain systèmes tels que le GSM, IS95, UMTS offrent la mobilité et sans fil simultanément.
Un autre type de mobilité est celui mis en œuvre dans un réseau IP Mobile [8,9]. Le protocole IP Mobile est une extension d’IP permettant à un nœud de rester accessible avec la même adresse, tout en étant mobile dans différents réseaux. C’est-à-dire, le nœud mobile maintient son adresse permanente de réseau d’origine (Home Address) pour l’identification des connexions de la couche transport (par exemple TCP), et utilise une adresse temporaire (Care-of-Address) de réseau visité qui permet de router les paquets jusqu’à lui à son point d’attachement actuel sur Internet. L’adresse temporaire change à chaque fois que le mobile change de réseau d’attachement.
Il est possible de classer les réseaux sans fil de plusieurs manières, selon que nous nous intéressons à un critère ou à un autres. La figure suivante présente une classification possible selon les critères suivants : l’étendue géographique, la topologie et l’infrastructure utilisée.
Le concept cellulaire consiste à diviser une zone de couverture relativement grande, généralement appelée réseau sans fil large (WWAN, pour Wireless Wide Area Network) en plusieurs zones
plus petites appelées cellules. Chaque cellule possède sa propre station de base (ou antenne relais). Chaque station de base utilise une bande de fréquence spécifique et gère l’ensemble des nœuds se trouvant dans la cellule. Les systèmes de communication cellulaires se sont développés en plusieurs générations. La première génération était analogique. La deuxième génération (2G) est numérique mais orienté mode circuit avec le standard le plus répondu dans le monde GSM (Glo-bal System for Mobile communication) qui offre un service de voix de 9,6kbits/s et qui permet un transfert de données à faible vitesse. Il existe une génération dite deux et demi (2G+) avec le GPRS (General Packet Radio Service) qui est une évolution du système GSM qui permet en agrégeant plusieurs canaux de voix d’offrir une commutation en mode paquet allant jusqu’à 115kbits/s. La troisième génération (3G) permet d’utiliser la commutation en mode paquet dans contexte multimédia. Le nom générique pour les différentes normes 3G est IMT-200 qui regroupe : (i) l’UMTS (Unuiversal Mobile Telecommunications System) en Europe qui promet un transfert des données avec un débit théorique allant jusqu’à 2 Mbps dans les configurations à courte portée (picocellules) mais généralement 100kbit/s avec des cellules plus grande (micro-cellules), (ii) CDMA2000 aux Etats-Unis qui est une évolution de CDMAOne (Code Division Multiple Access) et W-CDMA (WideBand CDMA) au japon, et (iii) EDGE (Enhanced Data rates for Global Evolution) parfois appelé E-GPRS (Enhanced GPRS) qui est une évolution du GPRS et du TDMA. Les propositions de la troisième génération ont été normalisées par les 3GPP (3rd Generation Partnership Project) et 3GPP2 [10].
Le concept du réseau local sans fil est né du besoin d’offrir par le sans fil les services habituellement accessibles par voie filaire (Ethernet). Au sein des entreprises ou des laboratoires, ces réseaux sont souvent utilisés en complément des réseaux filaires existants. Du réseau personnel (WPAN, pour wireless Personnel Area Network) au réseau local (WLAN, Wireless LAN), plusieurs standards existent : Bluetooth, IEEE 802.11, HiperLAN. Ces standards permettent aux mobiles de communiquer entre eux dans un même réseau d’accès, mais ils ne sont pas prévus généralement pour permettre de passer d’un réseau d’accès à un autre comme les systèmes mobiles cellulaires. Ils sont donc plus adaptés à des réseaux locaux dans des lieux identifiés tels qu’une salle de confé rence, un campus universitaire et des lieux de passage : aéroports, gares, etc.

Les réseaux cellulaires

La propriété d’atténuation, caractéristique de l’interface radio, a permis de développer le concept cellulaire. Dans ce modèle, la zone de couverture est divisée en cellules, à chaque cellule est affectée à une bande de fréquence. Du fait de la rareté du spectre hertzien, cette bande de fréquence est étroite, d’où la faible capacité de l’ensemble du système.
Pour faire face à l’augmentation ininterrompue du nombre d’utilisateurs des réseaux cellulaires, il a fallu tout à la fois accroître la capacité du système, diminuer la dimension des cellules et installer un nombre plus important de relais. Le GSM est le premier système cellulaire de téléphonie mobile efficace, économique et universel. Il a été très rapidement adopté par les utilisateurs ces dix dernières années. Le GSM évolue constamment vers le transfert de données (GPRS).

Le GSM
Le GSM (Global System for Mobile communication) [11] est un stadard Européen établie par l’ETSI (European Telecommunications Standards Institute), qui est conçu essentiellement pour la téléphonie mobile sans fil, mais il peut supporter des transferts de données à faible débit (14.4 Kbits/s de base). Les mobiles ne communiquent pas directement entre eux mais ils doivent passer par la station de base, même s’ils sont proches. Le réseau global est formé d’une multitude de stations de base, chacune couvrant une cellule indépendante. Les cellules adjacente doivent utiliser des fréquences différentes pour éviter les interférences entre les communications.
Le GSM utilise la méthode d’accès F-TDMA (Frequency Time Division Multiple Access). Chaque mobile doit réserver un slot dans une première phase de contrôle avant de pouvoir commencer la communication. Le GSM utilise deux plages de fréquences différentes, la première est réservée pour les communications des mobiles vers les stations de base (890-915 MHz et 1710-1785 MHz pour le GSM 1800) et la deuxième dans le sens des stations de base vers les mobiles (935-960 MHz et 1805-1880 MHz pour le GSM 1800).
Certains choix technique du GSM sont fait en conséquence, notamment en matière d’architecture réseau et de mise en forme des ondes (modulation, codage, etc). Ces choix se révèlent toutefois contraignantes pour les services de données (transfert de fichier, vidéo, etc). Pour pallier ces limitations, le standard du GSM évolue sans cesse. Dans un premier temps, le GSM a standardisé des règles pour réaliser un transfert de données en utilisant les circuits de voix. Avec le HSCSD (High Speed Circuit Switched Data), on assiste à un premier développement du standard vers des débits supérieurs, mais toujours en mode circuit.
Pour améliorer encore l’efficacité de transfert de données, une évolution majeure du GSM est normalisée sous le nom de GPRS (General Packet Radio Sevice). Fondée sur l’interface radio du GSM, mais développant un partage de ressources dynamique adapté au trafic sporadique, le GPRS introduit une architecture réseau en mode paquet. Si l’utilisateur téléphone, l’information transit par le réseau cœur de type circuit téléphonique. Si l’utilisateur émet des paquets, ces derniers sont acheminés par le réseau cœur de type paquet. Enfin, EDGE (Enhanced Data for GSM Evolution) propose des débits supérieurs par l’introduction d’une modulation plus efficace, applicable à la fois au HSCSD et au GPRS.
L’association du GPRS et d’EDGE est souvent considérée comme un system 2.5, intermédiaire entre les systèmes 2G (GSM, etc) et 3G (UMTS, CDMA2000, etc).

L’UMTS
L’apparition d’une troisième génération de réseaux de mobiles a pour origine tout à la fois la saturation des systèmes actuels et le besoin d’une couverture universelle ainsi que de services évolués tendant vers ceux offerts par les infrastructures fixes. Il faudrait ajouter à ces raisons une certaine volonté émanant de pays n’ayant pas forcément d’infrastructure fixe adéquate ou ayant raté le train du GSM d’entrer rapidement dans la troisième génération.
L’UMTS (Universal Mobile Telecommunication System) [12] est un système cellulaire de troisième génération qui fait partie de la famille IMT-2000 (International Mobile Telecommunication system 2000) et dont les spécifications techniques sont développées au sein du 3GPPP. L’archi-tecture de ce système est composé essentiellement d’un réseau terrestre d’accès radio, l’UTRAN (Universal Terrestrial Radio Access Network) et d’un réseau cœur dérivé de celui spécifié pour la phase 2G+ du GSM. L’UTRAN utilise deux modes d’accès fondés sur la technologie CDMA large bande : l’UTRA/FDD (Universal Terrestrial Radio Access/Frequency Duplex Division) et l’UTRA/TDD (Universal Terrestrial Radio Access/Time Duplex Division).
L’UMTS est le résultat de plusieurs années de recherche qui ont été menées en Europe à partir de la fin des années 1980 et qui se poursuivent aujourd’hui à l’échelle mondiale. RACE (Research of Advanced Communication Technologies in Europe) a été le premier programme européen de re-cherche qui avait pour objectif de définir les principes techniques de l’UMTS [13]. Le Programme ACTS (Advanced Communication Technologies and Servies) est venu prendre le relais à partir de 1995.
L’UMTS est conçu pour pouvoir s’interconnecter et interagir avec le GSM dans toutes ses phases d’évolution. Aussi, l’UMTS peut être considéré comme l’étape la plus porteuse en terme d’innovations technologiques. Ce système se distingue en effet de ses prédécesseurs HSCSD, GPRS et EDGE, par des débits plus élevés, une couverture plus large, une capacité en termes de nombre d’abonnés plus grande et des services plus variés.

1 Introduction 
1.1 Le point de départ et sujet de thèse
1.2 Contributions et organisation du document
2 La mobilité dans les réseaux sans fil : état de l’art 
2.1 Historique, évolution et applications des réseaux sans fil
2.2 Problèmes des transmissions radios et des réseaux sans fil
2.3 Les réseaux mobiles et sans fil
2.4 Résumé
2.5 Conclusion
3 La 4G : l’interopérabilité entre les réseaux 
3.1 Les principes de la gestion de mobilité dans les réseaux sans fil et mobiles
3.2 Une structure hiérarchique des réseaux sans fil
3.3 Un exemple d’intégration : 3G/WLAN
3.4 Les handovers dans une OWN
3.5 Position des objectifs
3.6 OWN : La gestion de la mobilité
3.7 Optimisation des handovers
3.8 Les handovers inter-domaines
3.9 La mobilité rapide et faible
3.10 Évaluation des performances
3.11 Conclusion
4 Conception des algorithmes pour le routage à multiples contraintes 
4.1 Interconnexions et graphes
4.2 Les règles de composition des contraintes
4.3 Résumé des algorithmes de routage existants
4.4 Routage à contrainte simple
4.5 Routage aux contraintes multiples
4.6 Résultats de simulation
4.7 Conclusion
5 Routage ad hoc et qualité de service 
5.1 Les réseaux Ad hoc
5.2 Optimized Link State Routing protocol (OLSR)
5.3 Définition de la qualité de service
5.4 Les concepts de QoS sur IP
5.5 Les modèles de QoS pour MANETs
5.6 Systèmes de signalisation pour la QoS dans MANETs
5.7 Routage avec QoS dans MANETs
5.8 Conclusion
6 EQMM : Efficient Quality of service Model for MANETs 
6.1 Description du modèle
6.2 OLSR : QoS implicite
6.3 Le protocole de routage QOLSR
6.4 Estimation des métriques
6.5 Contrôle d’admission et de réservation
6.6 Contrôle de congestion
6.7 QOLSR : Évalutaion des performances
6.8 Conclusions
7 Conclusions et perspectives 
7.1 Conclusion
7.2 Perspectives