Stratégies de routage multi-chemin dans les réseaux sans fil multi-sauts

Enjeux dans une stratégie multi-chemin

Suite à notre étude sur les solutions de routage MC proposées dans la littérature, nous avons identifié, dans la section précédente, de nombreuses caractéristiques à considérer lors du déploiement d’une stratégie MC. Ces caractéristiques sont importantes pour concevoir une technique MC fiable qui s’adapte aux contraintes des réseaux sans fil multisauts. Dans le reste de cette section, nous discutons les principaux enjeux et défis soulevés par les différents composants d’un routage MC. Cette discussion, qui dépasse l’état de l’art, doit nous permettre de décider des problématiques les plus intéressantes à traiter dans la suite de notre travail.

Découverte de chemins multiples

L’indépendance des chemins est un critère fondamental. Plusieurs critères d’indépendance sont considérés : – Les chemins sont disjoints sur le graphe. Ils ne comportent comme nœuds communs que la source et la destination dans le cas d’une disjonction par les nœuds sinon nous parlons de chemins à liens disjoints. – Les chemins sont le plus indépendants possible sur le plan radio. De tels chemins sont constitués d’un maximum de nœuds qui peuvent transmettre en parallèle et dont les transmissions induisent le moins de collisions possibles. Si les chemins sont indépendants d’un point de vue graphe, cela ne signifie pas que les chemins sont indépendants d’un point de vue radio. Le nombre de chemins indépendants est limité et est fonction de la topologie du réseau. La limitation du nombre de chemins est fréquemment imposée par le nombre de voisins au niveau de la source et de la destination, là o`u les chemins divergent puis convergent [37]. En ce qui concerne l’indépendance d’un point de vue graphe, le nombre de chemins à nœuds disjoints est plus petit que celui à liens disjoints. Dans le cas o`u la source ou la destination est un nœud pendant (voir figure 2.9), c’est-à-dire un nœud ne possédant qu’un voisin, il n’existe pas de chemins disjoints. On peut aussi noter que dans le cadre de réseaux mono-interface et mono-canal basés sur une approche CSMA, il y a forcément dépendance des chemins à la source et à la destination d’un point de vue radio. La recherche de chemins disjoints à tout prix n’est peut-ˆetre pas la stratégie la plus adaptée, car elle peut limiter grandement le nombre de chemins possibles. En outre, mˆeme en supposant qu’il existe un nombre de chemins disjoints plus grand que le nombre de chemins recherchés, l’impératif d’indépendance peut conduire à la sélection de chemins très longs. Or, plus un chemin est long, plus il est vulnérable aux ruptures de liens et le délai d’acheminement des données peut ˆetre important. La recherche de chemins disjoints dans le cas de la figure 2.10-(a) conduit à sélectionner un chemin long, qui peut s’avérer au final moins performant que le chemin sélectionné dans la figure 2.10-(b), mˆeme si celui-ci exploite un lien déjà utilisé. Par conséquent, en absence de chemins totalement disjoints, les chemins choisis peuvent partager des liens. Ce partage d’un lien entre les chemins peut ˆetre acceptable si le lien n’est pas stauré ou trop chargé. On peut alors parler dans ce cas de chemins partiellement disjoints.

ENJEUX DANS UNE STRATEGIE MULTI-CHEMIN 

En conclusion, les trois critères suivants semblent intéressants à prendre en compte pour la découverte de chemins indépendants : – trouver des chemins suffisamment disjoints (par les nœuds si possible, par les liens sinon) ; – éviter des chemins trop longs ; – limiter les interférences. Figure 2.9 — Nœud pendant. Figure 2.10 — Chemin plus long sous contrainte de disjonction : (a) Chemin 2 long mais disjoint (b) chemin 2 court mais non disjoint. Concevoir une métrique adéquate pour la sélection de chemins multiples est importante afin de construire les meilleurs chemins selon les conditions du réseau multi-saut. La majorité des protocoles de routage MC déjà proposés se basent sur le nombre de sauts. Cependant pour un routage MC d’autres critères comme, par exemple, la robustesse aux interférences ou la qualité d’un lien semblent plus intéressants à exploiter. 

Maintenance des chemins

Durant cette phase, il faut d’abord choisir le moment à partir duquel déclencher la découverte des chemins. Si la découverte d’un nouveau chemin est déclenchée à chaque fois qu’une route tombe en panne, cela induit un surcoˆut en termes de messages de contrˆole dans le réseau. Si en revanche la découverte est déclenchée une fois que tous les chemins sont tombés en panne, cela induit un délai additionnel avant de pouvoir router les paquets qui pourra affecter négativement les performances des applications. Un situation intermédiaire possible est de déclencher la découverte lorsque k chemins tombent en panne sur un ensemble de n chemins (1 ≤ k ≤ n). Déterminer la valeur de k est un compromis entre une estimation du surcoˆut induit en termes de paquets de contrˆole et de délai. La valeur de k peut ˆetre définie aussi selon le besoin de l’application. D’autre part, il est intéressant de disposer d’un mécanisme qui détecte rapidement les pannes. Un tel mécanisme permet d’offrir plus de réactivité face aux changements de topologie dus à des déconnexions de liens, à un épuisement d’énergie d’un nœud, à des ressources limitées, etc. Nous avons détaillé cette problématique dans le chapitre 4. 2.6.3 Allocation du trafic Nous pouvons distinguer trois principales possibilités d’allocation du trafic pour le routage MC : – Plusieurs chemins entre une source et une destination, mais un seul chemin est utilisé à la fois pour router les paquets en cours. Les autres chemins restent pour le secours en cas de rupture de route. – Plusieurs chemins entre une source et une destination, et si nous disposons de plusieurs flux en cours entre ces deux stations, ils peuvent ˆetre routés sur des chemins différents. En revanche, les paquets d’un mˆeme flux sont toujours routés sur la mˆeme route. – Plusieurs routes entre une source et une destination, et les paquets d’un mˆeme flux sont routés sur des chemins différents. La proportion des paquets par chemin est à définir de préférence selon la qualité de chacun des chemins afin d’utiliser au mieux les ressources disponibles. Ces trois approches semblent graduelles dans la complexité. Notons qu’une répartition par paquets sur plusieurs chemins résulte généralement en leurs arrivées en désordre à la destination [20]. Dans ce cas, une technique de réordonnancement adaptée doit ˆetre  utilisée. Cette opération doit non seulement ˆetre implémentée correctement mais elle risque d’induire des délais supplémentaires, ce qui peut avoir un impact négatif sur les applications temps réel comme le streaming par exemple. Il existe des solutions qui gèrent le délai entre les chemins trouvés de fa¸con à éviter le plus possible le déséquencement des paquets à l’arrivée [39]. La deuxième technique qui route un flux par chemin semble ˆetre un cas intermédiaire intéressant entre le mono-chemin et le MC par paquets qui demande un réordonnancement à la destination. En distribuant les flux sur un ensemble de chemins, d’une part le nombre total de nœuds intermédiaires qui participent au routage augmente et d’autre part le risque de congestion de certains nœuds est réduit. Plusieurs travaux comme [4], [22] et [23] ont également montré que la répartition des données d’un flux sur des chemins multiples, au lieu d’acheminer le flux sur un seul chemin, peut réduire la congestion. Dans ce contexte, les principaux travaux [33], [23], [13] s’intéressent à cette problématique et proposent des extensions MC respectivement d’OLSR, d’AODV et de DSR avec un équilibrage de charge. Nous discutons ces diverses solutions ainsi que l’impact de la répartition des données sur MP-OLSR dans le chapitre 5. 

Métriques de routage

La sélection des chemins multiples dépend de la métrique choisie. Cette métrique doit ˆetre adaptée non seulement au contexte de l’application mais aussi à celui du réseau. La majorité des protocoles de routage, présentée précédemment, cherche essentiellement à trouver des chemins possibles entre une source et une destination sans prendre en considération la qualité des liens. Plusieurs métriques sont considérées pour le routage ad hoc et ces métriques ont un impact sur les performances [38]. Il existe un nombre conséquent de travaux sur les métriques de routage qui dépassent le cadre de cette thèse, mais nous décrivons néanmoins, dans cette section, quelques métriques qui sont intéressantes pour la suite de notre travail, notamment pour la répartition de trafic. Dans un environnement sans fil multi-saut, il est utile de trouver des chemins multiples indépendants qui minimisent les interférences de type intra-flux et inter-flux. Le problème d’interférence inter-flux se produit lorsque deux nœuds voisins routant différents flux sont en compétition pour l’accès au medium pour transmettre sur le mˆeme canal (les nœuds 3 7, 8 et 9 du flux 2 se trouvent dans la zone d’interférence du nœud 3 du flux 1 (voir figure 2.11)). Le problème d’interférence intra-flux se produit lorsqu’au sein d’un mˆeme flux, plusieurs nœuds sont en attente pour communiquer car ils se trouvent dans la mˆeme zone d’interférence d’un nœud en communication pour router le mˆeme flux (entre le nœud 3 et les nœuds 1, 2 et 4, 5). Pour prévenir de telles situations, dans le cas multi-canaux, il suffit d’affecter différents canaux aux nœuds en se basant sur la connaissance du voisinage et des flux en cours. Plusieurs métriques dans un contexte multi-radio ont été proposées dans la littérature comme WCETT [15], MIC [18], PPTT [19], etc. Puisque dans notre travail, nous nous basons sur un réseau sans fil multi-saut mono-radio o`u les nœuds sont mono-interfaces, nous décrivons dans la suite seulement les principales métriques adaptées à un tel environnement. Figure 2.11 — Les interférences inter-flux et intra-flux [78]. 2.7.1 La métrique ETX La métrique ETX (Expected Transmission Count) [14] mesure le nombre de transmissions, retransmissions incluses, prévues pour transmettre un paquet avec succès sur un lien. La métrique ETX d’un lien est calculée comme suit : 2.7. METRIQUES DE ROUTAGE ´ 33 ET X = 1 1 − p (2.4) O`u p est la probabilité que la transmission sur le lien échoue. Pour un lien établi entre deux nœuds A et B, cette probabilité p dépend des probabilités pf de perte de paquets dans le sens (A− > B) et pr de perte de paquets dans le sens inverse tel que décrit par l’équation : p = 1 − (1 − pf ) × (1 − pr) (2.5) Pour ce faire, chaque nœud envoie, périodiquement (chaque seconde), une sonde en broadcast. La sonde contient des informations sur les sondes déjà re¸cues par les voisins. Le calcul de probabilité de perte se base sur la différence entre le nombre de sondes re¸cues dans un intervalle de temps w et le nombre total de sondes qui doivent ˆetre re¸cues dans cette mˆeme fenˆetre w. Par conséquent, chaque nœud peut déduire le taux de perte du lien dans un sens pf et celui dans l’autre sens pr. Le meilleur chemin est celui qui minimise la métrique ETX (cette dernière étant une métrique additive). La métrique ETX a été intégrée dans les RREQs du protocole de routage DSR. La route vers la destination est sélectionnée selon un ETX minimal en opérant l’algorithme de Dijkstra. La source attendra un délai additionnel avant d’initier la découverte de route afin que les nœuds accumulent les mesures des liens [14]. ETX ne considère que le taux de perte des liens et ne prend pas compte la bande passante disponible sur un lien. ETX ne permet pas de différencier des liens qui ont le mˆeme taux de pertes mais qui ont des capacités différentes.

La métrique ETT

La métrique ETT (Expected Transmission Time) [15] représente la métrique ETX sous sa forme temporelle. Cette métrique ETT correspond au temps nécessaire pour que la transmission d’un paquet sur un lien soit réussie. Elle est calculée comme suit : ET T = ET X × S B (2.6)  Avec – S : la taille du paquet à transmettre. – B : la bande passante courante du lien. Sa valeur est mesurée par la technique ”packet pair” [15] qui consiste à envoyer deux sondes sur un lien entre deux nœuds X et Y, la première de grande taille et la deuxième de petite taille, et puis à calculer la différence de leurs délais d’acheminement ; ce calcul est répété pour 10 échantillons, puis Y envoie la valeur minimale à X qui déduit par la suite la valeur de B comme l’explique la figure 2.12.