Tài liệu D'eploiement récursif des robots mobiles dans un ŕeseau de substitution luận văn ths. công nghệ thông tin

Rapport de stage Master Informatique Option Reseaux & Systemes Communicants Déploiement récursif des robots mobiles dans un réseau de substitution Hanoi, Octobre 2013 Auteur: razafimandimby A. Jean Cristanel Encadreurs: Tahiry razafindralambo Dimitrios Zorbas Table des matières REMERCIEMENTS 4 RESUME 5 ABSTRACT 6 1 INTRODUCTION 7 2 Le réseau de substituion 8 2.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Avantages d'un réseau de substitution . . . . . . . . . . . . . . . . . . . . . 10 3 Etat de l'art sur les placements des n÷uds relais 11 3.1 Placement des n÷uds relais dans un réseau de capteur . . . . . . . . . . . . 11 3.2 Déploiement d'un réseau maillé sans l . . . . . . . . . . . . . . . . . . . . . 11 3.3 Déploiement des n÷uds relais dans un réseau de substitution . . . . . . . . 12 4 Solution proposée 13 4.1 Mesure de la qualité du lien . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.2 Calcul de la nouvelle position . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.3 Déplacement vers la position calculée . . . . . . . . . . . . . . . . . . . . . . 15 5 Évaluation et discussion des résultats 17 5.1 Paramètres de simulation . . . . . . . . . . . . . . . . . 5.2 Les résultats obtenus pour le premier scénario . . . . . . 5.2.1 Évaluation du borne inférieure (µ) . . . . . . . . 5.2.2 Déploiement statique . . . . . . . . . . . . . . . . 5.2.3 Résultats avec la puissance du signal reçu (RSS) 5.2.4 Résultats avec le débit de transmission (TxRate) 5.2.5 Résultats avec le temps d'aller-retour (RTT) . . . 5.2.6 Avec la métrique hybride . . . . . . . . . . . . . . 5.3 Les résultats obtenus pour le deuxième scénario . . . . . 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 18 18 18 19 20 21 22 24 Conclusion 27 ANNEXES 32 I. Le projet RESCUE 32 2 Table des gures 2.1 WiFiBoT (http ://www.wibot.com) . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Déploiement d'un réseau de substitution avec la mobilité contrôlée . . . . . 9 2.3 Cas d'utilisation typique pour un réseau de base et un réseau de substitution[19] 9 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10 5.11 5.12 5.13 5.14 5.15 5.16 5.17 5.18 Scénario d'évaluation simple . . . . . . . . . . . . . . . . . . . . . . Le débit obtenu en utilisant diérentes positions statiques . . . . . . . Evolution de l'emplacement du relais mobile avec RSS . . . . . . . . . Energie consommée pendant la simulation avec RSS . . . . . . . . . . Débit avec RSS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Evolution de l'emplacement du relais mobile avec TxRate . . . . . . . Energie consommée pendant la simulation avec TxRate . . . . . . . . . Débit avec TxRate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Evolution de l'emplacement du relais mobile avec RTT . . . . . . . . . Débit avec RTT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Energie consommée pendant la simulation avec RTT . . . . . . . . . . Evolution de l'emplacement du relais mobile avec la métrique hybride . Débit avec la métrique hybride . . . . . . . . . . . . . . . . . . . . . . Comparaison de la consommation d'énergie . . . . . . . . . . . . . . . Scénario avec du load balancing . . . . . . . . . . . . . . . . . . . . . . Load balancing utilisant la métrique RSS . . . . . . . . . . . . . . . . Load balancing utilisant la métrique TxRate . . . . . . . . . . . . . . . Load balancing utilisant la métrique Hybride . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 18 19 19 20 20 21 21 22 22 22 23 23 24 24 25 26 26 6.1 Architecture du projet RESCUE . . . . . . . . . . . . . . . . . . . . . . . . 33 3 REMERCIEMENTS Je tiens tout d'abord à remercier M. David Simplot-Ryl , Directeur du centre Inria Lille, de m'avoir accueilli comme stagiaire au sein d'Inria Lille. Je remercie également Nathalie Mitton , responsable de l'équipe FUN Inria Lille, de m'avoir accepté au sein de son équipe. Je tiens à exprimer ma profonde gratitude et mes sincères remerciements à mes encadreurs Tahiry Razandralambo et Dimitrios Zorbas pour tout le temps qu'ils m'ont consacré, pour leurs directives précieuses et pour la qualité de leur suivi tout au long de la réalisation de ce travail. Je tiens à remercier particulièrement Karen Miranda , doctorante d'Inria Lille, pour l'attention et l'aide qu'elle m'a apporté durant mon stage. Enn, je tiens à remercier le personnel administratif d'Inria Lille et l'ensemble de l'équipe FUN pour leur accueil, leur bonne humeur et leur disponibilité pendant la durée de mon stage. 4 RESUME L e déploiement d'un réseau de substitution avec des routeurs mobiles sans l est devenu un nouveau challenge dans les domaines des réseaux et de la robotique. L'objectif est de fournir un déploiement ou redéploiement autonome des routeurs mobiles. Ainsi, une conception particulière de certains algorithmes est nécessaire pour la procédure de déploiement et de redéploiement. Dans ce travail, nous avons proposé un algorithme ecace pour déployer/redéployer les routeurs mobiles en tenant compte d'une approche de déploiement rapide, de la consommation d'énergie et d'une métrique hybride. Nous avons considéré un scénario où nous avons deux routeurs dans un réseau xe et dont la connectivité entre ces deux routeurs doit être restaurée par un ou plusieurs routeurs mobiles sans l. L'objectif principal des routeurs mobiles sans l est d'augmenter les performances du réseau tel que le débit en agissant comme un n÷ud relais entre les deux routeurs du réseau xe. Pour ce faire, nous avons utilisé une approche rapide, adaptative et localisée qui prend en compte diérentes métriques tels que la puissance du signal reçu (RSS), le temps d'aller-retour d'un paquet (RTT) et le débit de transmission entre le routeur mobile sans l et les deux routeurs du réseau xe. Notre approche a amélioré les performances d'une précédente approche APA (Adaptive Positioning Algorithm)[12, 13] en réduisant le temps de déploiement, en augmentant le débit et en consommant moins d'énergie dans certains cas spéciques. A ce jour, notre travail est accepté à la 10ème conférence internationale d'ACM sur l'évaluation de la performance des réseaux ad hoc sans l , des réseaux de capteurs et des réseaux ubiquitaires (PE-WASUN 2013). Mots clés Réseau de substitution, déploiement d'un robot mobile, ecacité énergétique 5 ABSTRACT I n this work, we propose an algorithm to eciently (re)-deploy the wireless mobile routers of a substitution network by considering the energy consumption, a fast deployment scheme and a mix of the network metric. We consider a scenario where we have two routers in a xed network and where connectivity must be restored between these two routers with one or many wireless mobile router. The main objective of the wireless mobile router is to increase the communication performance such as the throughput by acting as relay node between the two routers of the xed network. We present a fast, adaptive and localized approach which takes into account dierent network metrics such as Received Signal Strength (RSS), Round-Trip Time (RTT) and the Transmission Rate, between the wireless mobile router and the two routers of the xed network. Our method outperforms the previous approach called APA (Adaptive Positioning Algorithm)[12, 13] by shortening the deployment time, increasing the throughput, and consuming less energy in some specic cases. To date, our work is accepted at the 10th ACM International Symposium on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks (PE-WASUN 2003). Keywords substitution network, robot deployment, energy eciency 6 1 INTRODUCTION D e nos jours, presque toutes les entités publiques et privées dépendent de la disponi- bilité des réseaux de communication. La coupure de ces réseaux peut engendrer un énorme préjudice surtout si cela dure longtemps. Ainsi, dans les pays développés, les réseaux de secours sont déployés chaque fois qu'il est possible de le faire. Malheureusement, pour des raisons nancières, mettre en place une telle infrastructure redondante n'est pas toujours possible dans les pays émergents. Pour pallier à ce manque de réseaux de secours, l'utilisation d'un réseau de substitution s'avère être une alternative possible et intéressante. Un réseau de substitution est un réseau constitué par un ensemble de routeurs mobiles pouvant être déployés de manière opportune et pendant une durée limitée pour assister un réseau (dit réseau de base) subissant des dicultés dues à une insusance de capacité, à une surcharge du réseau ou à une défaillance d'un élément du réseau. Contrairement à d'autres solutions (réseaux ad hoc ou réseaux maillés), un réseau de substitution ne vise pas à fournir des nouveaux services aux clients, mais plutôt de rétablir et maintenir au moins quelques-uns des services disponibles avant la panne du réseau de base. En outre, un réseau de substitution n'est pas déployé directement pour les clients mais est utilisé pour aider le réseau de base à fournir les services aux clients. Lors de la panne du réseau de base, les emplacements optimaux des routeurs mobiles sans l ou la topologie optimale du réseau sont inconnus. De ce fait, le déploiement d'un réseau de substitution avec des routeurs mobiles est devenu un nouveau challenge et constitue l'objet de notre travail. Le but de notre algorithme, qui sera décrit dans ce présent rapport, est de fournir un déploiement/redéploiement autonome des routeurs mobiles an de procurer la qualité de service (QoS) ou la qualité d'expérience (QoE) dans un environnement dynamique et évolutif pour répondre aux exigences spéciques de l'application. En outre, les contraintes énergétiques devraient être également considérées vu que les routeurs mobiles sans l sont autonomes et doivent fonctionner jusqu'à ce que le réseau de base soit réparé. Ce présent rapport est organisé comme suit : la section 2 présente, avec plus de détaille, le concept du réseau de substitution. Nous verrons dans la section 3 l'état de l'art sur les réseaux rapidement déployables (RDN : Rapidly Deployable Networks ). La section 4 décrit notre algorithme de déploiement tandis que la section 5 présente les résultats obtenus. La section 6 sera dédiée à la conclusion et les perspectives. 7 2 Le réseau de substituion 2.1 Description Le concept d'un réseau de substitution a été initialement proposé dans [19] et a été également l'objectif de base du projet ANR VERSO RESCUE(ANR-10-VERS- 003) 1 . Dans ce contexte, le réseau de substitution est déni comme une solution sans l dont le but est de restaurer la connectivité ou maintenir le service d'un réseau (dit réseau de base) subissant une défaillance d'élément ou une surcharge du réseau. Le réseau de base peut être un réseau d'accès ou un réseau métropolitain et peut être basé sur la technologie sans l ou laire. Contrairement, aux réseau ad hoc et réseau maillé, le réseau de substitution ne fournit pas de nouveau service aux clients. L'approche derrière le réseau de substitution est de déployer, dans un temps limité, un réseau sans l constitué de routeurs mobiles (appelés routeurs mobiles de substitution) de façon à maintenir le réseau de base opérationnel. Les routeurs mobiles de substitution sont donc les pièces maîtresses du réseau de substitution. Des robots mobiles comme WiFiBoT (cf. Figure 2.1) peuvent assurer le rôle des routeurs mobiles sans l. Figure 2.1: WiFiBoT (http ://www.wibot.com) Basés sur la mobilité contrôlée, les routeurs mobiles de substitution peuvent se déplacer pour adapter leur topologie à l'évolution du trac ou aux exigences de qualité de service (QoS). La gure ci-dessous illustre un exemple du déploiement d'un réseau de substitution avec l'utilisation de la mobilité contrôlée. Dans cette gure, l'un des liens (représenté par une ligne mince) est en diculté et ne peut pas supporter la charge de trac. Un réseau de substitution a été déployé pour aider à transporter le trac. En raison de la nature dynamique du trac, le réseau de substitution adapte sa topologie pour continuer à fournir la meilleure qualité de service possible. 1. http ://rescue.lille.inria.fr/ 8 Figure 2.2: Déploiement d'un réseau de substitution avec la mobilité contrôlée Il a été prouvé dans [1] que la capacité atteinte par le réseau de substitution, dont la technologie devrait être intégrée dans les routeurs mobiles, est très basse. Il est donc important de contrôler le trac passant par le réseau de substitution, ce qui suscite la mise en place des politiques de qualité de service (QoS) pour les ux entrants et sortants (tels que le contrôle d'admission, les mécanismes de hiérarchisation, etc). Ainsi, pour améliorer la capacité et assurer la QoS dans le réseau de substitution, [19] a proposé une nouvelle architecture du réseau de substitution en introduisant un nouveau type de routeur appelé bridge router . Les bridge router  sont essentiellement des passerelles reliant le réseau de base et le réseau de substitution et ils sont responsables de la fourniture, la maintenance et l'adaptation de la QoS à l'intérieur et entre le réseau de base et le réseau de substitution. La gure 2.3 ci-dessous illustre un exemple de déploiement possible d'un réseau de substitution avec la nouvelle architecture proposée dans [19]. Les bridge router  sont déployés en même temps que le réseau de base. En cas de panne, les routeurs mobiles de substitution sont déployés pour former un réseau de substitution aidant le réseau de base à rétablir les services de base tel que la connectivité. Figure 2.3: Cas d'utilisation typique pour un réseau de base et un réseau de substitution[19] 9 La gure 2.3 ci-dessus illustre un exemple de l'utilisation d'un réseau de substitution. Dans cette gure, les bridge router sont déployés conjointement avec le réseau de base (Fig. 2.3a). Au départ, le réseau de base fonctionne sans l'aide des routeurs mobiles de substitution. En cas de problème dans le réseau de base (gure 2.3b), les routeurs mobiles de substitution sont déployés. Dans l'architecture du projet RESCUE (cf. Annexe), la détection de défaillance et le déploiement sont eectués de façon autonome par le réseau de base lui-même. Les routeurs mobiles de substitution essayent de trouver une position optimale pour rétablir la connectivité des services et assurer la qualité de service pour certains ux (Fig. 2.3c). Dans certains cas, un redéploiement peut s'avérer nécessaire pour améliorer la qualité de service et pour s'adapter à la condition du réseau qui est en constante évolution (Fig. 3d). 2.2 Avantages d'un réseau de substitution Nous pouvons cité plusieurs avantages d'un réseau de substitution : 1. les ressources du réseau de substitution sont utilisées uniquement lorsque cela est nécessaire ce qui est diérent d'un réseau de secours permanent qui ne sera même pas utilisé très souvent. La réutilisation et la réduction des coûts : 2. La capacité de déploiement : le réseau de substitution a la capacité d'aider les parties du réseau de base où il n'y a pas de redondance. Le déploiement de réseaux de substitution n'est pas opposé au fait d'avoir des réseaux de secours traditionnels. Au contraire, le réseau de substitution doit être considéré comme étant un réseau complémentaire. 3. Capacité d'adaptation : la topologie du réseau de substitution peut être adapté à l'évolution du trac de sorte qu'un service ecace peut être fourni. 10 3 Etat de l'art sur les placements des n÷uds relais Au cours de ces dernières années, de nombreuses recherches sur les placements des n÷uds relais ont été réalisées. Ces recherches ont été étudiées dans diérents domaines d'application à savoir les réseaux de capteurs, les réseaux maillés sans l et le plus récemment le réseau de substitution sur lequel un robot mobile joue le rôle de relais pour assurer la connectivité du réseau de base. 3.1 Placement des n÷uds relais dans un réseau de capteur Ces dernières années, de nombreux travaux ont été proposés pour améliorer les performances du réseau en plaçant des relais sans l dans des positions spéciques. Dans [5, 21], des stratégies statiques de déploiement aléatoire des n÷uds sans l ont été présentées. Plus précisément, dans [2, 10, 18], le placement est calculé en fonction de l'environnement spécique et l'objectif à atteindre. Un aperçu complèt est présenté dans [24]. Le placement des n÷uds dans le réseau de capteur est considéré comme un problème d'optimisation. La plupart des travaux de recherches dans ce domaine se focalisent sur la consommation d'énergie et la maximisation de la zone de couverture. Par exemple, les auteurs de [14] et [17] ont proposé des algorithmes de placement des n÷uds an de minimiser la consommation moyenne d'énergie par n÷ud et de maximiser la durée de vie du réseau. Un autre déploiement consiste à faire déplacer les n÷uds à un nouvel emplacement. Dans [25], les auteurs ont présenté un mécanisme centralisé permettant de repositionner les capteurs après un déploiement initial selon la densité désirée. Dans [8], les auteurs ont présenté un algorithme distribué qui laisse, dans un premier temps, les capteurs déterminer le meilleur placement, puis les conduit par la suite vers des emplacements calculés. Ces deux travaux visent à maximiser la durée de vie des réseaux de capteurs. Dans [26] et [4], les auteurs ont mis l'accent sur l'utilisation de la mobilité contrôlée an d'optimiser les paramètres de QoS. Dans [15], les auteurs ont proposé un algorithme basé sur la mobilité contrôlée pour déplacer les n÷uds capteurs multimédia sans l vers des positions optimales en termes de consommation d'énergie. 3.2 Déploiement d'un réseau maillé sans l Le concept du réseau sans l rapidement déployable est introduit dans [9]. Les auteurs ont décrit une infrastructure déployable à la demande pour les communications mil- 11 itaires. Suite à ce travail, de nombreux projets de déploiement (militaire ou civile) ont été proposés dans la littérature. Dans [3], les auteurs ont présenté une méthode permettant de déployer rapidement un réseau backbone ad hoc sans aucune planication préalable. Le déploiement prend en compte les mesures sur la qualité du lien tel que le rapport signal sur bruit et le taux de perte des paquets. Les auteurs de [23] ont proposé un algorithme basé sur une évaluation rapide de la couche physique eectuée par un mobile sans l. Le relais mobile établit une communication à un saut en diusant en permanence des paquets sonde (probe packets) à ses relais prédécesseurs . Lorsque certains relais dans la même zone répondent avec un paquet sonde d'accusé de réception, le mobile mesure la puissance du signal reçu via le paquet sonde d'accusé de réception qu'il a reçu. Si la puissance du signal reçu est en dessous d'un seuil donné, alors un nouveau relais doit être déposé. 3.3 Déploiement des n÷uds relais dans un réseau de substitution Toutes les approches que nous avons vu jusqu'ici ne sont pas adaptées au réseau de substitution étant donné qu'elles dépendent sur un déploiement pré-planié des n÷uds mobiles. Conscients de cet inconénient, Karen Miranda et al. dans [12, 13] ont présenté une autre approche de déploiement pour les robots mobiles de substitution. Un des problèmes de déploiement qui a été soulevé est de savoir la direction de déplacement du robot mobile pour éviter la déconnexion ou la dégradation de la qualité du service. Pour ce faire, les auteurs ont proposé un algorithme de positionnent adaptatif (APA : Adaptive Positioning Algorithm ) se basant sur les informations locales des routeurs mobiles. Cette nouvelle approche s'adapte aux changements de la topologie et à l'évolution des caractéristiques du réseau grâce à la connaissance du voisinage à un saut. Dans leurs travaux, Miranda et al. n'ont pas pris en considération la consommation d'énergie des routeurs mobiles sans l. De plus, les auteurs n'ont considéré que les métriques réseau individuelles, tels que la puissance du signal reçu (RSS), le taux de transmission (TxRate) et le temps aller-retour (RTT) pour évaluer la qualité du lien. On constate également que le robot mobile met beaucoup de temps pour atteindre son emplacement optimale avec l'algorithme APA. Cela est causé par le fait que APA se déplace toujours d'un pas xe pour chaque mouvement. 12 4 Solution proposée La solution que nous allons proposer et que nous nommerons F-APA (Fast-Adaptive Positioning Algorithm) par la suite se base sur APA. F-APA est un algorithme localisé capable d'adapter la position du routeur mobile en utilisant seulement l'information de voisinage à un saut et son objectif est d'égaliser la qualité du lien entre le routeur mobile et les deux routeurs du réseau xe en un minimum de temps possible. Cependant, il est à noter qu'avoir une position où les deux mesures (sur la qualité de lien) sont égaux ne signie pas que le débit est maximisé. En eet, la corrélation entre les paramètres du lien et de la position repose sur plusieurs changements environnementaux. Toutefois, le débit peut être considérablement amélioré. Nous espérons donc, avec notre solution, obtenir des gains en terme de temps, de débit et de la consommation énergétique. Comme avec APA, an de s'adapter aux conditions actuelles du réseau, les routeurs mobiles devraient se déplacer ou se redéployer à la demande. Les diérences de F-APA par rapport à APA sont la façon dont F-APA calcule le step de déplacement et les paramètres utilisés pour estimer la qualité du lien. L'idée de base reste toujours la même. Pendant la durée de vie du réseau, chaque routeur mobile sans l du réseau de substitution détermine sa nouvelle position en se basant sur les informations de la qualité du lien provenant de ses voisins. On suppose que deux noeuds sont voisins s'ils se trouvent dans la même zone de communication. On suppose également que certains n÷uds sont xes et le trac doit donc être transféré entre deux noeuds xes. Ainsi les routeurs sans l de substitution se déplacent de manière dynamique dans le scénario et agissent comme des relais. Et enn, on suppose que chaque noeud connaît sa propre position en utilisant le GPS ou un autre système de localisation. Sur la base des hypothèses ci-dessus, F-APA sera exécuté sur chaque noeud en trois étapes : (1) mesure de la qualité du lien, (2) calcul de la nouvelle position et (3) déplacement vers la position calculée. Aucune connaissance préalable de l'emplacement optimale des routeurs mobiles n'est supposé. 4.1 Mesure de la qualité du lien Au cours de cette première phase, les routeurs mobiles envoient des requêtes vers ses voisins en incluant un numéro de séquence et son adresse MAC. Chaque station voisine répond à cette demande par un message de réponse qui contient l'adresse MAC et les informations concernant la qualité de lien. Plusieurs paramètres peuvent être utilisés pour estimer la qualité de lien à savoir RSS, RTT et TxRate. An d'améliorer la prédiction de la qualité du lien et améliorer ainsi la QoS, nous avons utilisé aussi un paramètre hybride qui combine les points forts (et atténue les faiblesses) de tous ces paramètres. Les routeurs mobiles maintiennent une table des temps d'envoi de chaque paquet et ne tiennent pas compte des réponses qui seront reçues après texp . A la n du temps 13 d'observation, les routeurs mobiles calculent la valeur moyenne du paramètre de lien pour tous les paquets qu'ils ont reçu. Il est à noter que les paquets sonde de requête et de réponse ont une priorité d'accès plus élevée que les autres paquets. Plus précisément, lorsqu'un paquet sonde est généré, il sera mis à la tête de la le d'attente de la couche de liaison. Cependant, ces paquets ne peuvent pas remplacer une transmission déjà prévue dans la couche MAC. 4.2 Calcul de la nouvelle position Chaque noeud calcule sa nouvelle position sur la base des paramètres du lien de ses voisins chaque kÖt secondes, où k est le nombre de paquet sonde permettant d'assurer que des mesures susantes sont utilisées pour obtenir des statistiques cohérentes sur la prédiction de la qualité du lien. Une fenêtre glissante est utilisée pour calculer les statistiques, et une politique FIFO est utilisée pour supprimer les anciennes valeurs des paramètres de lien. Contrairement à APA, F-APA ajuste le pas de déplacement du routeur mobile en utilisant la diérence entre les valeurs moyennes du paramètre de lien (4P L). L'idée est que si la diérence de qualité entre les noeuds voisins est très importante dans ce cas le routeur mobile va faire un grand déplacement vers sa destination. Sinon, si la diérence est minime le routeur mobile eectuera un petit déplacement. Considérant par exemple deux noeuds S et D voisins d'un routeur mobile R. Soit P LSavg et P LD avg les valeurs moyennes des paramètres obtenus sur les liens S-R et R-D. Le pas de déplacement peut être calculé par : step = α Avec RNc 2 P LSavg − P LD 4P L avg = α= | max(dif f ) | | max(dif f ) | (4.1) (4.2) Nc = {S, D} Nc : le noeud cible RNc : la distance entre les noeuds R et Nc max(dif f ) : la valeur maximale obtenue pendant le temps d0 observation t Si α est positif, le routeur va aller en avant (c-à-d vers D). Par contre, il va revenir en arrière si α est négatif. Nous attribuons aussi une borne inférieure µ pour le step de déplacement an d'éviter le déplacement inutile pour les petites distances. Il est intéressant de souligner que le routeur fait la moitié de la distance maximale à la n du premier déplacement. 14 Le paramètre de lien ne peut pas être modié dans un seul déploiement et pour l'utilisation du paramètre hybride, la formule (4.2) devient : α= 4P L1 |max(dif f1 )| + 4P L2 |max(dif f2 )| + ... + 4P Lk |max(dif fk )| k (4.3) où k correspond à k diérents paramètres de la qualité de lien (RSS, RTT, TxRate). Il est également important de noter que tous ces paramètres peuvent être obtenus localement et sont directement disponibles sur les cartes réseaux sans l commerciales. Nous considérons que toutes les valeurs obtenues par la carte réseau sont positives. Il est à noter que, contrairement à RSS et TxRate, si la valeur du RTT est plus élevée entre la source et le routeur mobile qu'entre la destination et le routeur mobile, le routeur mobile se déplace vers la source. Les débits de transmission possibles pour chaque paquet est de 11, 5.5, 2 et 1 Mbps selon le standard 802.11b. Ces taux de transmission sont adaptés automatiquement en fonction des conditions du réseau an d'accroître la abilité du lien [11]. Nous avons choisi quatre paramètres de lien : Puissance du signal reçu (RSS), débit de transmission (TxRate), temps aller-retour (RTT) et hybride pour évaluer la performance de notre algorithme sur les diérentes couches du modèle OSI. RSS est une métrique de la couche physique, Txrate est une métrique de la couche liaison, RTT est une métrique de la couche réseau et hybride est une métrique qui combine les trois. 4.3 Déplacement vers la position calculée La dernière étape à faire est de se déplacer vers la nouvelle position calculée cidessus. Pendant cette phase, nous évaluerons également l'énergie consommée (en Joules) par le routeur mobile par l'équation :  25 ∗ d + 2 si le routeur mobile est en déplacement 8 si le routeur mobile ne bouge pas où d est la distance de déplacement en mètres et on ajoute 2 joules pour l'accélération du robot. La vitesse du robot est de 0,9 m/s. Il est important de noter que la consommation d'énergie et la vitesse du robot ont été expérimentalement calculées en utilisant wibot 1 L'algorithme F-APA est décrit par l'algorithme 4.1 ci-dessous. 1. http ://www.wibot.com/ 15 Algorithme 4.1 Algorithme F-APA Partie I : Mesure de la qualité du lien (1) for i = 1 to n do (2) Send packet pi ; (3) ttx i = CLOCK_TIME_NOW ; (4) end for (5) set expire time texp ; (6) P Lavg = 0; (7) while true do (8) Receive packet pj ; (9) trx j = CLOCK_TIME_NOW ; tx (10) if trx j − texp > ti then (11) Drop paquet ; (12) n = n - 1; (13) else (14) P Lavg = P Lavg + P Lj ; (15) end if (16) end while (17) P Lavg = P Lnavg Partie II : Calcul de la nouvelle position (1) Calculer α en utilisant la formule (4.2) ou (4.3) (2) Calculer step en utilisant la formule (4.1) (3) if step > 0 and step > µ then (4) Déplacera de step mètres vers la destination (D) ; (5) else if step < 0 and | step |> µ then (6) Déplacera de | step | mètres vers la source (S) ; (7) else (8) step = 0; (9) end if Partie III : Déplacement (1) Déplacer de | step | mètres vers la source ou la destination ; 16 5 Évaluation et discussion des résultats Dans cette section, nous présentons les résultats de simulation de notre algorithme. Nous décrivons d'abord les paramètres de simulation et puis nous présenterons les résultats des simulations individuelles avec RTT (Round-Trip Time), débit de transmission (TxRate), puissance du signal reçu (RSS) et la version hybride combinant toutes ces métriques. Nous comparons également notre algorithme à l'algorithme APA décrit dans [12, 13]. 5.1 Paramètres de simulation Nos simulations ont été réalisées avec le simulateur NS2.29 [22] contenant des patchs qui reètent la propagation sans l réelle, la couche physique sans l réelle et un mécanisme de régulation de débit (AARF: adaptive autorate fallback) [11]. AARF adapte le taux de transmission en fonction de l'état du réseau an d'augmenter la abilité de la liaison. Nous avons ajouté également dans le simulateur une propagation de canal réaliste et un modèle d'erreur. Ces derniers prennent en compte l'eet des interférences et les diérents bruits thermiques [16]. Le tableau ci-dessous illustre tous les paramètres utilisés pendant notre simulation. Propagation Error model Antennas gain physical Antennas height Min received power Communication range 802.11b MAC Basic rate Auto rate fallback LL Queue size Policy Routing Static Routing trac Transport and Flow application Packet size Statistics Number of sample Simulation time Broadcast period Mobility Movement step Two ray ground Real Gt = Gr = 1 ht = hr = 1 m P = 6.3 nW 240 m Standard compliant 2 Mbps 1, 2, 5.5, 11 Mbps 50 pkts Drop tail Dijkstra None CBR/UDP 512B 10 3000s 0.1s cf. formule (4.1) Table 5.1: Paramètres de simulation 17 5.2 Les résultats obtenus pour le premier scénario La gure 5.1 illustre le premier scénario que nous avons utilisé pour évaluer les deux algorithmes (F-APA et APA). Figure 5.1: Scénario d'évaluation simple Dans cette topologie, le n÷ud destination (D) est placé à 250 mètres du n÷ud source (S). Au début de la simulation, le robot mobile est placé à 10 mètres du n÷ud source et il commence à se déplacer en utilisant notre algorithme F-APA. 5.2.1 Évaluation du borne inférieure (µ) µ est l'un des paramètres les plus importants de notre algorithme. En eet, sa valeur peut augmenter la consommation d'énergie si µ est trop petit mais il peut également modier le comportement de l'algorithme en s'abstenant de déplacer si µ est trop grand. An de trouver la valeur appropriée de µ, nous avons exécuté plusieurs simulations et nous avons découvert que la meilleure valeur pour µ est de 3 mètres. Nous ne montrons pas ces résultats ici car ils ne fournissent aucune informations intéressantes mais nous avons testé toutes les valeurs de µ entre [1;20]m avec un pas de 0.5 m pour tous les paramètres de lien étudiés dans ce rapport. 5.2.2 Déploiement statique Debit [kbps] An de trouver la borne supérieure du débit atteint, nous avons placé manuellement le routeur dans diérentes positions statiques sans le déplacer tout au long du processus. Cinq positions diérentes ont été testés et les résultats sont illustrés par la gure 5.2 ci-dessous. Le meilleur débit est obtenu lorsque le routeur est proche du milieu (c-à-d 125 mètres) ou plus près de la destination (exemple 200 m). Ce comportement est dû à l'asymétrie du trac (seulement un trac dans un sens). La performance dégrade quand le routeur est placé plus près de la source (exemples 20, 40 mètres). 2400 2200 2000 1800 1600 1400 1200 1000 800 600 0 20 m 40 m 500 1000 1500 2000 2500 3000 Temps de la simulation [s] 200 m 120 m 240 m Figure 5.2: Le débit obtenu en utilisant diérentes positions statiques 18 5.2.3 Résultats avec la puissance du signal reçu (RSS) La gure 5.3 illustre l'évolution du relais mobile, en utilisant RSS, pendant toute la durée de la simulation. Cette gure nous montre que F-APA et APA ont atteint leur emplacement optimal. Ce pendant, on constate qu'avec F-APA le déploiement est beaucoup plus rapide. Ce déploiement rapide conduit à une amélioration de la performance du débit (cf. gure 5.5) qui converge rapidement vers le débit obtenu par le déploiement statique. La meilleure performance de F-APA est atteint en consommant la même énergie que APA (cf. gure 5.4). Avec cette métrique, il n'est pas surprenant que le routeur mobile trouve sa position optimale (le point milieu entre la source et la destination pour notre scénario) vue que la formule (4.2) tente toujours d'égaliser les valeurs de P LSavg et P LD avg . En fait, la puissance du signal reçu est strictement liée à la distance étant donné que la puissance utilisée pour la transmission est constante et le modèle de propagation est la même pour toutes les entités sans l. Distance a la source [m] 250 APA avec RSS F-APA avec RSS 200 150 100 50 0 0 500 1000 1500 2000 2500 3000 Temps de la simulation [s] Figure 5.3: Evolution de l'emplacement du relais mobile avec RSS Energie consommee [J] 25000 APA avec RSS F-APA avec RSS 20000 15000 10000 5000 0 0 500 1000 1500 2000 2500 3000 Temps de la simulation [s] Figure 5.4: Energie consommée pendant la simulation avec RSS 19 4000 APA avec RSS F-APA avec RSS Deploiement statique 3500 Debit [kbps] 3000 2500 2000 1500 1000 500 0 0 500 1000 1500 2000 2500 3000 Temps de la simulation [s] Figure 5.5: Débit avec RSS 5.2.4 Résultats avec le débit de transmission (TxRate) Distance a la source [m] Les gures 5.9, 5.10 et 5.11 illustrent les résultats obtenus avec la métrique TxRate. F-APA atteint le milieu très rapidement mais le robot mobile ne reste pas en un point précis puisque le débit de transmission change continuellement. Cela est dû au fait que le débit de transmission est aecté par diérent état du réseau tels que le nombre de collisions (Voir [11]). En dépit de cette uctuation, le débit global est meilleur que celui obtenu avec APA. En revanche, le mouvement continu du robot augmente la consommation d'énergie. Il est également important de noter que malgré le mouvement constant du routeur mobile le débit obtenu est assez stable avec F-APA. Ce comportement montre comment l'algorithme s'adapte rapidement aux conditions changeantes du réseau tout en maintenant le débit très bien. APA avec TxRate F-APA avec TxRate 250 200 150 100 50 0 0 500 1000 1500 2000 2500 3000 Temps de la simulation [s] Figure 5.6: Evolution de l'emplacement du relais mobile avec TxRate 20