Présentation des réseaux ad hoc (extrait du rapport de bibliographie)

Les différences entre les réseaux sans fil avec infrastructure et ceux sans infrastructure

Les réseaux sans fil les plus répandus et les plus connus sont ceux se basant sur une infrastructure. Cela est notamment dû au fait qu'ils sont utilisés pour fournir des services de haut niveau, par exemple une connexion à Internet. Comme leur nom l'indique, les réseaux sans fil avec infrastructures sont construits de manière logique, en respectant une infrastructure globale stable, notamment au niveau de la gestion du réseau. Ainsi, toutes les fonctionnalités d'administration du réseau, du routage, sont gérées par exemple par un fournisseur d'accès à Internet, ce qui offre un service fiable et simple.

Les réseaux sans fil sans infrastructure sont des réseaux qui se construisent d'eux mêmes, à la différence des réseaux utilisant actuellement la technologie WiFi et pour lesquels il existe un réseau d'administration (pour notamment la gestion des services) pré-établi. Ces réseaux (appelées MANET [11], Mobile Ad hoc NETwork) se basent sur des stations faisant partie du réseau pour assurer tous les besoins nécessaires au bon fonctionnement du réseau, notamment les politiques de routage. La gestion est donc dynamique et dé- pendante du réseau lui-même.

Ces réseaux offrent de nouveaux services, comme la possibilité de déployer rapidement des systèmes, sans avoir à prévoir une structure d'administration proprement dite (on pourrait par exemple penser au déploiement d'un réseau de capteurs communiquants, l'administration étant dans ce cas répartie entre les difféents capteurs). Mais, bien entendu, l'absence d'infrastructure engendre des faiblesses, lesquelles peuvent être exploitées pour attaquer la disponibilité du réseau (voir la section 3). Un des problèmes évidents est que les autres noeuds sont également responsables d'une partie de l'administration. Or, un noeud n'a pas forcément de connaissance à priori sur les autres, la confiance n'est donc pas aussi simple que dans le cas des réseaux classiques.

Les différents protocoles de routage dans les réseaux ad hoc

Les différents problèmes posés par les réseaux ad hoc (forte mobilité des noeuds, faible espace mémoire, batterie limitée, ...) font que plusieurs grandes catégories de protocoles ont été étudiées. Ces catégories sont résumées dans la figure 1. Les deux grandes catégories de protocoles de routage sont les protocoles uniformes et les protocoles non-uniformes, lesquelles peuvent être également divisés en sous-catégories (présentées dans les sections suivantes). Les protocoles se distinguent par le fait que les noeuds jouent tous (ou non) le même rôle. Il est à noter qu'il existe une classification transversale des protocoles en fonction de la périodicité de calcul des routes : les protocoles proactifs calculent les routes à différents intervalles, tandis que les protocoles réactifs calculent les routes à la demande, c'est-à-dire lorsqu'un message doit être propagé par le noeud (les protocoles intermédiaires étant appelés hybrides).

Les protocoles non-uniformes

Les protocoles non-uniformes se distinguent par le fait que tous les noeuds n'ont pas le même rôle au sein du réseau. Classiquement, certains interviendront directement dans la gestion du routage, et d'autres non. Parmi ces protocoles, on distingue ceux dits à partitionnement (avec par exemple CBRP [7]), dans lesquels un noeud maître est choisi pour chaque sous-partie du réseau, de ceux dits à sélection de voisins. Les protocoles à sélection de voisins sont les plus utilisés, avec en autres le protocole OLSR [13] qui possède plusieurs implémentations3 et fait l'objet de nombreuses études. Cette deuxième catégorie de protocoles repose sur la désignation de noeuds voisins responsables du routage.

Les protocoles uniformes

Parmi ces protocoles, on distingue deux sous-catégories : les protocoles orientés topologie (link-state protocols ) avec par exemple FSR [10], lesquels reposent sur l'état des connexions avec les voisins, et les protocoles orientés destination (distant-vector protocols). Cette deuxième catégorie de protocoles est proche des protocoles de routage utilisés sur les réseaux filaires. Dans ce cas, les noeuds maintiennent des informations sur la distance (en nombre de sauts) les séparant des noeuds destination, ainsi que le prochain noeud à atteindre. L'un des protocoles les plus connus, AODV [2], fait partie de cette catégorie.

Comparaison des catégories de protocoles

Bien entendu, chaque catégorie possède des points forts et des points faibles, lesquels dépendent de la topologie du réseau déployé.
Les protocoles proactifs permettent l'envoi rapide de messages, mais nécessitent une gestion périodique des routes, ce qui est coûteux en énergie. Les protocoles réactifs uniformes ne sont pas efficaces sur des réseaux à grande échelle ou fortement mobiles. Le protocole OLSR est celui sur lequel de nombreuses études ont été menées et est également l'un des protocoles les plus prometteurs (il est par exemple déjà défini comme RFC par l'IETF, ce qui n'est pas le cas de tous). Le but de la section suivante est de présenter ce protocole, mais également d'introduire les spécificités des réseaux ad hoc à travers cet exemple.

Figure 1

Présentation du protocole OLSR

Notions de base

Le protocole Optimized Link State Routing est une extension pour les réseaux ad hoc des protocoles du type Link State Routing (avec notamment le protocole OSPF [14], Open Shortest Path First) déployé sur les réseaux classiques. Il s'agit d'un protocole proactif non uniforme dont les noeuds assurant la diffusion des messages sont appelés MPRs (MultiPoint Relay, relai multipoint), les autres noeuds ayant pour fonction de choisir ces MPRs. les sites http ://www.olsr.org et http ://hipercom.inria.fr/OOLSR/ proposent des informations et des implémentations de ce protocole.

Il se base sur deux types de messages, Hello et TC (que nous décrivons dans les sections suivantes). L'état d'un lien entre deux noeuds peut être Inexistant, Unidirectionnel ou Bidirectionnel. Les états varient lors des échanges de messages entre les noeuds (Inexistant ! Unidirectionnel ! Bidirectionnel).

Structure des messages

Les messages HELLO

Les messages HELLO sont échangés périodiquement entre les voisins, mais non propagés. Ils contiennent des informations sur l'état des liens entre les noeuds voisins. Un message HELLO contient trois listes, définissant les noeuds à liens bidirectionnels, unidirectionnels, et les noeuds MPRs du noeud à l'origine du message.

Les messages TC

Les messages TC (Topology Control) sont propagés par inondation sur tout le réseau. Ils ont pour but de signaler l'état global du réseau. A noter que ces deux types de messages contiennent des informations redondantes utilisées par certaines versions sécurisées du protocole pour effectuer des contrôles.

Sélection des noeuds MPR

Le but d'un noeud MPR est de propager les données émises par un de noeuds MPR l'ayant sélectionné comme noeud MPR (on parle de MPR Selector ), pour assurer la propagation des messages dans le réseau. Afin d'avoir un fonctionnement optimal, la sélection des noeuds MPR par un noeud se fait de la manière suivante : d'après l'ensemble des messages HELLO reçus, chaque noeud connaît tous les autres noeuds accessibles en deux sauts. En utilisant un algorithme d'optimisation, chaque noeud choisit un ensemble minimal de noeuds à un saut, lequel permet de couvrir tous les noeuds accessibles en deux sauts. Par récurrence, on arrive à couvrir tout le réseau.

Cet algorithme n'est pas forcément optimal, notamment s'il y a des choix arbitraires, mais il permet d'assurer un recouvrement total pour chaque noeud. La figure 2 illustre le fonctionnement de ce protocole sur un réseau en étoile. Les noeuds MPRs indiqués sont ceux choisis par le noeud central.

Figure 2