D'eploiement récursif des robots mobiles dans un r´eseau de substitution
- 33 trang
- file .pdf
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.2 Les résultats obtenus pour le premier scénario . . . . . . . . . . . . . . . . . 18
5.2.1 Évaluation du borne inférieure (µ) . . . . . . . . . . . . . . . . . . . 18
5.2.2 Déploiement statique . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.2.3 Résultats avec la puissance du signal reçu (RSS) . . . . . . . . . . . 19
5.2.4 Résultats avec le débit de transmission (TxRate) . . . . . . . . . . . 20
5.2.5 Résultats avec le temps d'aller-retour (RTT) . . . . . . . . . . . . . . 21
5.2.6 Avec la métrique hybride . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.3 Les résultats obtenus pour le deuxième scénario . . . . . . . . . . . . . . . . 24
6 Conclusion 27
ANNEXES 32
I. Le projet RESCUE 32
2
Table des gures
2.1 WiFiBoT (http ://www.wi bot.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 Scénario d'évaluation simple . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.2 Le débit obtenu en utilisant diérentes positions statiques . . . . . . . . . . 18
5.3 Evolution de l'emplacement du relais mobile avec RSS . . . . . . . . . . . . 19
5.4 Energie consommée pendant la simulation avec RSS . . . . . . . . . . . . . 19
5.5 Débit avec RSS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.6 Evolution de l'emplacement du relais mobile avec TxRate . . . . . . . . . . 20
5.7 Energie consommée pendant la simulation avec TxRate . . . . . . . . . . . . 21
5.8 Débit avec TxRate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.9 Evolution de l'emplacement du relais mobile avec RTT . . . . . . . . . . . . 22
5.10 Débit avec RTT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.11 Energie consommée pendant la simulation avec RTT . . . . . . . . . . . . . 22
5.12 Evolution de l'emplacement du relais mobile avec la métrique hybride . . . . 23
5.13 Débit avec la métrique hybride . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.14 Comparaison de la consommation d'énergie . . . . . . . . . . . . . . . . . . 24
5.15 Scénario avec du load balancing . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.16 Load balancing utilisant la métrique RSS . . . . . . . . . . . . . . . . . . . 25
5.17 Load balancing utilisant la métrique TxRate . . . . . . . . . . . . . . . . . . 26
5.18 Load balancing utilisant la métrique Hybride . . . . . . . . . . . . . . . . . 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 Raza ndralambo 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.
En n, 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 e cace
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 con-
nectivité 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éci ques. 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, e cacité énergétique
5
ABSTRACT
I n this work, we propose an algorithm to e ciently (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 ap-
proach 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 deploy-
ment time, increasing the throughput, and consuming less energy in some speci c 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 e ciency
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 mo-
biles 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 di cultés dues à une insu sance 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 con-
stitue 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 a n
de procurer la qualité de service (QoS) ou la qualité d'expérience (QoE) dans un environ-
nement dynamique et évolutif pour répondre aux exigences spéci ques 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.wi bot.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 tra c 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 di culté et ne peut pas supporter la charge de
tra c. Un réseau de substitution a été déployé pour aider à transporter le tra c. En rai-
son de la nature dynamique du tra c, 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 tra c 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. La réutilisation et la réduction des coûts : les ressources du réseau de substi-
tution 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.
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 tra c de sorte qu'un service e cace 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écem-
ment 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 per-
formances du réseau en plaçant des relais sans l dans des positions spéci ques. 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é-
ci que 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 a n 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
a n 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 au-
teurs 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 plani cation 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 communica-
tion à 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
signi e 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, a n
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 tra c 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 en n, 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. A n 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 su santes sont utilisées pour obtenir des statistiques cohérentes sur la prédic-
tion 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 :
RNc
step = α (4.1)
2
Avec
P LSavg − P LD 4P L
α=
avg
= (4.2)
| max(dif f ) | | max(dif f ) |
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 a n 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 4P L2 4P Lk
|max(dif f1 )| + |max(dif f2 )| + ... + |max(dif fk )|
α= (4.3)
k
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 locale-
ment 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 a n 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 ci-
dessus. 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 wi bot 1
L'algorithme F-APA est décrit par l'algorithme 4.1 ci-dessous.
1. http ://www.wi bot.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) ttxi = CLOCK_TIME_NOW ;
(4) end for
(5) set expire time texp ;
(6) P Lavg = 0;
(7) while true do
(8) Receive packet pj ;
(9) j = CLOCK_TIME_NOW ;
trx
(10) if trx tx
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 transmis-
sion (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 a n 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 Two ray ground
Error model Real
Antennas gain Gt = Gr = 1
physical Antennas height ht = hr = 1 m
Min received power P = 6.3 nW
Communication range 240 m
802.11b Standard compliant
MAC Basic rate 2 Mbps
Auto rate fallback 1, 2, 5.5, 11 Mbps
LL Queue size 50 pkts
Policy Drop tail
Routing Static Dijkstra
Routing tra c None
Transport and Flow CBR/UDP
application Packet size 512B
Statistics Number of sample 10
Simulation time 3000s
Broadcast period 0.1s
Mobility Movement step 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
modi er le comportement de l'algorithme en s'abstenant de déplacer si µ est trop grand.
A n 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
A n 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 tra c (seulement un tra c 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
Debit [kbps]
1800
1600
1400
1200
1000
800
600
0 500 1000 1500 2000 2500 3000
Temps de la simulation [s]
20 m 200 m 240 m
40 m 120 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 em-
placement 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.
250
APA avec RSS
Distance a la source [m]
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
25000
APA avec RSS
F-APA avec RSS
Energie consommee [J]
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
3500 F-APA avec RSS
Deploiement statique
3000
Debit [kbps]
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)
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.
250 APA avec TxRate
F-APA avec TxRate
Distance a la source [m]
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
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.2 Les résultats obtenus pour le premier scénario . . . . . . . . . . . . . . . . . 18
5.2.1 Évaluation du borne inférieure (µ) . . . . . . . . . . . . . . . . . . . 18
5.2.2 Déploiement statique . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.2.3 Résultats avec la puissance du signal reçu (RSS) . . . . . . . . . . . 19
5.2.4 Résultats avec le débit de transmission (TxRate) . . . . . . . . . . . 20
5.2.5 Résultats avec le temps d'aller-retour (RTT) . . . . . . . . . . . . . . 21
5.2.6 Avec la métrique hybride . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.3 Les résultats obtenus pour le deuxième scénario . . . . . . . . . . . . . . . . 24
6 Conclusion 27
ANNEXES 32
I. Le projet RESCUE 32
2
Table des gures
2.1 WiFiBoT (http ://www.wi bot.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 Scénario d'évaluation simple . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.2 Le débit obtenu en utilisant diérentes positions statiques . . . . . . . . . . 18
5.3 Evolution de l'emplacement du relais mobile avec RSS . . . . . . . . . . . . 19
5.4 Energie consommée pendant la simulation avec RSS . . . . . . . . . . . . . 19
5.5 Débit avec RSS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.6 Evolution de l'emplacement du relais mobile avec TxRate . . . . . . . . . . 20
5.7 Energie consommée pendant la simulation avec TxRate . . . . . . . . . . . . 21
5.8 Débit avec TxRate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.9 Evolution de l'emplacement du relais mobile avec RTT . . . . . . . . . . . . 22
5.10 Débit avec RTT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.11 Energie consommée pendant la simulation avec RTT . . . . . . . . . . . . . 22
5.12 Evolution de l'emplacement du relais mobile avec la métrique hybride . . . . 23
5.13 Débit avec la métrique hybride . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.14 Comparaison de la consommation d'énergie . . . . . . . . . . . . . . . . . . 24
5.15 Scénario avec du load balancing . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.16 Load balancing utilisant la métrique RSS . . . . . . . . . . . . . . . . . . . 25
5.17 Load balancing utilisant la métrique TxRate . . . . . . . . . . . . . . . . . . 26
5.18 Load balancing utilisant la métrique Hybride . . . . . . . . . . . . . . . . . 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 Raza ndralambo 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.
En n, 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 e cace
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 con-
nectivité 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éci ques. 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, e cacité énergétique
5
ABSTRACT
I n this work, we propose an algorithm to e ciently (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 ap-
proach 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 deploy-
ment time, increasing the throughput, and consuming less energy in some speci c 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 e ciency
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 mo-
biles 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 di cultés dues à une insu sance 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 con-
stitue 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 a n
de procurer la qualité de service (QoS) ou la qualité d'expérience (QoE) dans un environ-
nement dynamique et évolutif pour répondre aux exigences spéci ques 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.wi bot.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 tra c 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 di culté et ne peut pas supporter la charge de
tra c. Un réseau de substitution a été déployé pour aider à transporter le tra c. En rai-
son de la nature dynamique du tra c, 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 tra c 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. La réutilisation et la réduction des coûts : les ressources du réseau de substi-
tution 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.
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 tra c de sorte qu'un service e cace 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écem-
ment 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 per-
formances du réseau en plaçant des relais sans l dans des positions spéci ques. 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é-
ci que 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 a n 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
a n 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 au-
teurs 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 plani cation 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 communica-
tion à 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
signi e 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, a n
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 tra c 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 en n, 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. A n 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 su santes sont utilisées pour obtenir des statistiques cohérentes sur la prédic-
tion 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 :
RNc
step = α (4.1)
2
Avec
P LSavg − P LD 4P L
α=
avg
= (4.2)
| max(dif f ) | | max(dif f ) |
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 a n 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 4P L2 4P Lk
|max(dif f1 )| + |max(dif f2 )| + ... + |max(dif fk )|
α= (4.3)
k
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 locale-
ment 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 a n 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 ci-
dessus. 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 wi bot 1
L'algorithme F-APA est décrit par l'algorithme 4.1 ci-dessous.
1. http ://www.wi bot.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) ttxi = CLOCK_TIME_NOW ;
(4) end for
(5) set expire time texp ;
(6) P Lavg = 0;
(7) while true do
(8) Receive packet pj ;
(9) j = CLOCK_TIME_NOW ;
trx
(10) if trx tx
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 transmis-
sion (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 a n 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 Two ray ground
Error model Real
Antennas gain Gt = Gr = 1
physical Antennas height ht = hr = 1 m
Min received power P = 6.3 nW
Communication range 240 m
802.11b Standard compliant
MAC Basic rate 2 Mbps
Auto rate fallback 1, 2, 5.5, 11 Mbps
LL Queue size 50 pkts
Policy Drop tail
Routing Static Dijkstra
Routing tra c None
Transport and Flow CBR/UDP
application Packet size 512B
Statistics Number of sample 10
Simulation time 3000s
Broadcast period 0.1s
Mobility Movement step 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
modi er le comportement de l'algorithme en s'abstenant de déplacer si µ est trop grand.
A n 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
A n 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 tra c (seulement un tra c 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
Debit [kbps]
1800
1600
1400
1200
1000
800
600
0 500 1000 1500 2000 2500 3000
Temps de la simulation [s]
20 m 200 m 240 m
40 m 120 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 em-
placement 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.
250
APA avec RSS
Distance a la source [m]
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
25000
APA avec RSS
F-APA avec RSS
Energie consommee [J]
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
3500 F-APA avec RSS
Deploiement statique
3000
Debit [kbps]
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)
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.
250 APA avec TxRate
F-APA avec TxRate
Distance a la source [m]
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