Stratégies de mobilité optimisées pour la tolérance aux perturbations dans les réseaux sans fil

Perception traditionnelle de la mobilité dans les réseaux sans fil

Nous nous intéressons dans un premier temps aux formes couramment rencontrées de mobilité dans les réseaux MANET et DTN, tels que nous les avons tous deux introduits dans le chapitre précédent. Il est nécessaire de souligner que dans cette section, nous gardons une vision générique de la notion de nœud mobile : nous assimilons en effet ici un nœud à un équipement de télécommunications doté d’une capacité de déplacement lui permettant de parcourir un sous-ensemble de la surface ou du volume d’exploration.

Taxonomie des motifs de mobilité couramment rencontrés

Une remarque préalable au sujet d’une quelconque mobilité rencontrée dans un environnement de déploiement réaliste est qu’elle rentrera difficilement, dans la totalité du motif observé, dans un système de classification existant. En effet, de par leur variété et leur complexité, les mobilités réelles apparaissent souvent impropres à une caractérisation totalement fidèle et exhaustive. En revanche, il est plus aisé de s’appuyer sur des modèles de mobilité permettant de rendre compte de mouvements caractéristiques, afin de déterminer à quel modèle un mouvement réel est apparenté. À ce sujet, la classification des différents modèles de mobilité observés dans les réseaux auto-organisés comme Modèles de mobilité Modèles déterministes Modèles avec dépendances Modèles à base de traces Dépendance géographique Dépendance spatiale Dépendance temporelle Modèles aléatoires FIGURE 2.1 – Vue simplifiée d’un système de classification des mobilités d’un nœud réseau. les réseaux MANET et DTN est en général structurée selon deux embranchements principaux : les modèles de mobilité aléatoire et les modèles avec dépendance, que celle-ci soit par exemple temporelle, spatiale ou géographique . On peut rajouter cependant, comme illustré dans la Fig.2.1, un troisième embranchement, celui des modèles déterministes, cherchant au contraire à tenter de mieux capturer la complexité des mouvements en s’appuyant par exemple sur l’enregistrement préalable de la trajectoire d’un nœud en situation de déploiement. Les modèles de mobilité aléatoire Ces modèles représentent des nœuds dont les vitesses, coordonnées de destination et directions sont choisies de manière aléatoire. Dans ce large ensemble de modèles, trois ont été particulièrement étudiés et utilisés : les modèles de marche aléatoire (MA), à points de repère aléatoires (RWP) et à directions aléatoires (RD). Le modèle MA. Il s’agit de l’un des modèles de mobilité les plus utilisés avec RWP pour représenter, lors de simulations, le déplacement des nœuds d’un réseau auto-organisé. Plus généralement, c’est un modèle préexistant aux réseaux de télécommunications, à l’origine construit et utilisé dans le but de caractériser le mouvement brownien d’une particule immergée dans un fluide [19]. Selon ce modèle, un nœud doté de la capacité de se mouvoir dans une zone d’exploration Ze se déplace de ses coordonnées actuelles vers de nouvelles coordonnées en choisissant une direction dans [0, 2π] et une vitesse dans un intervalle [vmin, vmax ], les distributions de directions et de vitesses pouvant être uniformes ou non. Lorsque l’on cherche à mettre en œuvre une telle mobilité dans un contexte de simulation, chaque déplacement constitue une époque, c’est-à-dire une itération. Celle-ci est calculée sur la base d’une distance constante parcourue par le nœud (on dit alors que que la MA est en mode distance), soit sur la base d’un temps constant (on dit que la MA est en mode temps) entre deux changements de direction. Un nœud arrivant en bordure de surface Ze rebondit avec un angle dépendant de la direction précédente. Il continuera sur cette trajectoire le temps de finir l’époque en cours. La Fig. 2.2 en donne une représentation d’exemple que nous avons obtenue au moyen du simulateur réseau ns-3 [20] dans sa version 3.23. Ici, la marche aléatoire est configurée en mode temps, les nœuds parcourant 10 m avant de changer d’époque. FIGURE 2.2 – Représentation d’un exemple de MA, en mode distance (10 m), sur une surface Ze de 600×300 m2. Les trajectoires du nœud entre deux époques successives sont colorées au moyen de la carte de couleurs correspondant au temps de simulation, de 0 à 36000 s. Le modèle RWP. Les modèles MA et RWP sont des modèles proches, avec cependant quelques différences. À chaque époque, un nœud possédant un motif de mobilité de type RWP change en effet de trajectoire, non pas en choisissant une direction, mais une nouvelle position. Plus précisément, ce nœud détermine de nouvelles coordonnées dans la zone d’exploration Ze vers lesquelles se déplacer à une vitesse choisie dans un intervalle [vmin, vmax ]. De la même manière, les deux distributions aléatoires peuvent être uniformes (ce qui est la plupart du temps le cas) ou non. De plus, les nœuds peuvent marquer un temps d’arrêt entre chaque époque. Ce modèle est très souvent utilisé lors de simulations, en partie parce qu’il permet aux nœuds de disposer d’un motif de mobilité relativement réaliste, en particulier lorsque ceux-ci représentent des utilisateurs supposés se déplacer à des vitesses modérées, dans le contexte applicatif de manifestations en intérieur par exemple, où ce motif de mobilité peut raisonnablement imiter le mouvement d’un piéton passant d’un point d’intérêt à l’autre [21]. Dans le cadre de cette thèse, nous utilisons également le motif de mobilité RWP lorsque nous souhaitons simplement faire parcourir à un ensemble de nœuds une zone d’exploration. Ce sera le cas dans le Chapitre 4 avec les nœuds dits supplémentaires, et dans les Chapitres 5 et 6, avec ceux que nous désignerons par les termes nœuds de trafic et nœuds de surveillance, à l’exception du Paragraphe 6.2.5 dans lequel ces derniers possèdent une mobilité plus complexe). Le modèle RD. Ce modèle, proposé par Belding [22], est proche de RWP, mais diffère sur la manière dont est sélectionnée une direction en début de nouvelle époque : dans un premier temps, RD détermine une direction dans un intervalle uniformément distribué [0,2π], puis un point à l’intersection avec la bordure de la surface d’exploration Ze . Le nœud se déplace jusqu’à ces coordonnées, marque un temps de pause, puis choisit à nouveau une direction dans un intervalle cette fois-ci uniformément distribué dans [0,π] (on suppose en effet dans l’étude originale que Ze est rectangulaire ; un tel intervalle de direction permet donc d’atteindre, depuis la bordure, n’importe quel point de cette surface). On notera que la détermination des vitesses est réalisé de manière similaire à celle 12 Chapitre 2. État de l’art sur la mobilité contrôlée de RWP. De plus, plusieurs extensions notables de ce modèle ont été récemment proposées, dont le modèle à changements progressifs de direction (ST) [23], qui permet de définir des trajectoires relativement réalistes, notamment dans le contexte aérien. Selon le modèle ST en effet, un nœud changeant de direction détermine un point appartenant à la direction perpendiculaire à sa direction en cours, puis tourne autour jusqu’à un prochain changement de direction, produisant ainsi une série de mouvements en arcs de cercle. Les modèles avec dépendances La caractéristique principale de cette catégorie de modèle est que le calcul d’une nouvelle trajectoire d’un nœud ne s’appuie pas simplement sur la détermination de valeurs dans des intervalles, comme c’est le cas avec les modèles aléatoires. Ici, cette nouvelle trajectoire dépend d’un facteur de corrélation qui peut être de différente nature : il peut en particulier s’agir d’une dépendance temporelle, spatiale ou géographique. Les modèles avec dépendance temporelle. De manière générale, avec ce type de motif de mobilité, aussi parfois appelé modèle à mémoire [18], le calcul de la nouvelle trajectoire d’un nœud dépend d’un ou plusieurs de ses états antérieurs. Parmi ceux-ci, le modèle de mobilité de Gauss-Markov [24] est souvent utilisé dans les études où il est attendu que les trajectoires suivies par les nœuds soient relativement réalistes en regard des contraintes physiques imposées sur ces derniers, qu’il s’agisse par exemple de limitations en termes d’accélération, de vitesse et de mouvements. En effet, la vitesse d’un nœud est ici décrite par un processus de Gauss-Markov et permet d’aboutir à des motifs de mobilité pour lesquels les trajectoires sont dénuées de brusques changements de direction et de vitesse. En conséquence, ce modèle est régulièrement utilisé dans des études supposant la mise en œuvre concrète de véhicules roulants robotisés ou aériens [25, 26], pour lesquels il faut tenir prendre en compte des contraintes sur les trajectoires suivies. Dans la même optique, des extensions à ce modèle, comme le modèle de Gauss-Markov Amélioré [27], ont été proposées afin de rendre les trajectoires suivies encore plus réalistes, notamment à l’approche des bordures de la surface d’exploration [28]. D’autres travaux reposent sur l’utilisation d’un processus de décision markovien pour concevoir leur propositions de modèle de mobilité avec dépendance temporelle. C’est en particulier le cas de l’étude de Kuiper [29], pour lequel, à chaque intervalle de temps prédéfini, une action est décidée sur la base de probabilités dépendant de l’action précédente. Cette étude applique par exemple cette approche à des véhicules aériens par une modélisation sommaire de la gouverne de direction, c’est-à-dire la mise en œuvre de palonniers afin de contrôler l’angle de lacet, qui est l’angle issu de la rotation de ces véhicules autour d’un axe vertical. La Table 2.1 illustre le processus de décision, permettant d’aboutir à une action parmi 3 possibles : virer à gauche, continuer tout droit et virer à droite. Comme on le voit, les probabilités liées à la décision de l’action dépendent de l’action précédente.

 Propriété de prévisibilité des mobilités

Au-delà de la classification générale donnée dans la sous-section précédente, il est intéressant de considérer également ces mobilités sous l’angle du caractère prévisible, ou non, des mouvements considérés. Par exemple, il apparaît immédiatement que l’ensemble des modèles purement aléatoires, comme MA, RWP, RD, aboutissent à des motifs de mobilité pour lesquels les déplacements sont totalement imprévisibles, par construction. En revanche, les autres types de modèles, en particulier ceux avec dépendances temporelles, spatiales ou géographiques, peuvent selon les cas exhiber des mobilités prévisibles, ou non. À titre d’exemple, un modèle avec dépendance spatiale comme le modèle de mobilité en poursuite précédemment mentionné, pourrait être utilisé dans des scénarios de déploiement où les trajectoires sont supposées prévisibles, pour peu que la trajectoire du nœud-cible le soit, et que les composantes de mobilité aléatoires ajoutées à la composante de mobilité de groupe soient nulles. De manière générale, bien que la prévisibilité des déplacements des nœuds ne soit pas une propriété particulièrement désirée dans les réseaux MANET, certaines solutions nécessitent cependant de connaître, par anticipation, les trajectoires à venir. C’est notamment le cas des protocoles MANET géographiques, pour lesquels la connaissance, au minimum, des trajectoires des nœuds est requise pour réaliser un acheminement correct des paquets de données vers leurs destinations respectives. Les réseaux DTN peuvent également s’appuyer sur la propriété de prévisibilité des trajectoires. C’est le cas par exemple du protocole ASCoT [40], proposé dans le contexte de l’établissement d’une liaison interplanétaire, pour communiquer par exemple avec une sonde spatiale, à travers un ensemble de satellites-relais. Ce protocole utilise la connaissance des trajectoires de ces satellites sur leur orbite pour mettre en œuvre une solution de routage nommée Positional Link State Routing, qui permet de construire des routes à sauts multiples en utilisant, par anticipation, des liens de communication qui seront établis à un instant futur. Plus généralement, une classe entière de solutions DTN, s’appuyant sur une entité nommée oracle [41, 42, 43], utilise le caractère prévisible des trajectoires des nœuds afin de limiter les effets de surcharge du réseau provoqués par les mécanismes d’inondation que l’on retrouve dans les protocoles de routage DTN de type épidémique, dont on détaillera les principes dans le Chapitre 6. Cette limitation du volume de paquets inondés dans le réseau est en effet permise par l’anticipation des trajectoires des  nœuds, et donc des futurs liens de communication, permettant de déterminer plus précisément à quels nœuds intermédiaires transmettre sélectivement les paquets de données vers une destination, au lieu de les transmettre systématiquement, par inondation, à tous les nœuds rencontrés lors des contacts successifs. Un autre exemple de réseau intermittent où la mobilité des nœuds peut être anticipée et alimenter ainsi des mécanismes de routage prédictifs est le déploiement DTN évoqué dans l’étude de Jones [44], qui met en œuvre 36 véhicules du réseau de bus de Seattle. Ces véhicules, dont on connait précisément les trajets et horaires de passage, sont supposés dotés de liens de communication avec une portée radio prédéfinie, ce qui permet à un mécanisme de routage prédictif d’estimer les contacts à venir, et d’adapter sa stratégie de relais de paquets de données en conséquence. On notera enfin que les mécanismes de routage DTN prédictifs donnés en exemple ne requièrent pas nécessairement une connaissance omnisciente des futures trajectoires de l’ensemble des nœuds du réseau. En effet, ceux-ci sont souvent conçus pour manipuler une probabilité d’acheminer avec succès un paquet de données vers sa destination à travers un nœud voisin [41]. La détermination d’un seuil de probabilité adapté permettant de prendre une décision de routage est ici un aspect essentiel, dont la pertinence peut être généralement vérifiée par l’observation du compromis entre le taux de délivrance des paquets de données, et le surcoût provoqué par la duplication implicite des paquets et leur transmission par plusieurs voisins et ainsi par différents chemins. Cependant, disposer de mobilités prévisibles permet naturellement à ces mécanismes prédictifs de prendre des décisions de routage précises, et en conséquence d’aboutir généralement à une meilleure performance en ce qui concerne le compromis évoqué. 

Considérations de distribution spatiale des nœuds d’un réseau

Par définition et quel que soit le modèle de mobilité considéré, la distribution spatiale d’un ensemble de nœuds se déplaçant sur une surface d’exploration donnée varie avec le temps. Or, même pour les modèles de mobilité aléatoire, il est intéressant de s’intéresser aux propriétés asymptotiques de cette distribution, c’est-à-dire en principe mesurées sur un temps tendant vers l’infini, et concrètement, sur un temps d’observation significativement long. Il a en particulier non seulement été montré pour les modèles MA, RWP et RD qu’avec le temps de simulation, cette distribution converge vers une distribution stationnaire, mais que de plus, la distribution stationnaire des modèles MA et RD est uniforme, tandis que celle de RWP ne l’est pas [45, 46]. Cette observation peut être expliquée par le fait que la distribution des directions prises par les nœuds est uniforme par construction pour des mobilités comme MA et RD. En revanche, avec RWP, ce sont les coordonnées vers où les nœuds seront amenés à se déplacer à la prochaine époque qui sont uniformément distribuées : ainsi, un nœud se dirigeant vers une bordure aura une probabilité plus grande de choisir une nouvelle position dans la direction opposée à son mouvement, et donc, une plus grande probabilité de retourner vers le centre de la surface d’exploration. Selon les scénarios réseau considérés, ces considérations de stationnarité des distributions asymptotiques des nœuds relatives aux modèles de mobilité aléatoire peuvent avoir une importance, ou non. En effet, selon le contexte de déploiement, utiliser un modèle comme RWP dont la distribution spatiale des nœuds ne converge pas vers une distribution stationnaire uniforme, peut se transformer en biais d’interprétation si cette propriété n’a pas été prise en compte et que celle-ci a un impact notable sur les résultats de l’étude [46]. En revanche, un tel modèle peut aider à retranscrire plus fidèlement des mouvements observés qui exhibent une propriété similaire. Ainsi, dans la mesure où nous utilisons le modèle RWP pour représenter le mouvement de certains des nœuds du réseau 17 Chapitre 2. État de l’art sur la mobilité contrôlée dans la suite de ce manuscrit, nous reviendrons en fin de chapitre sur les raisons qui nous permettent de choisir ce type de mobilité sans risquer de rencontrer le biais d’interprétation évoqué